17
$\begingroup$

The following problem was given at IMO 1987.

Prove that there is no function f from the set of non-negative integers into itself such that $f(f(n)) = n + 1987$ for every $n$.

So I tried to generalize the problem, and my formulation is:

Let $2 \leq a$ and $b$ be positive integers. Find the number of functions $f$ from the set of non-negative integers into itself such that $f^{(a)}(n)= n + b$ for every $n$.

where $f^{(a)}$ is $f$ iterated $a$ times.

I proved the following results :

  1. There is no function if $a\nmid b$ (does not divide) Using the same method as for the problem in IMO.

    solution(1) see here

  2. $a=2$ , if b is even then I proved that the number of possible functions is $\frac{b!}{(b/2)!}$

    solution(2) ($a=2$ and $b$ even, we determine the number of possible functions)

we have $$f(n + bm) = f(n) + bm$$ for all $n,m\in\mathbb{N}$

Now take an arbitrary integer $p$, $\; 0 \leq b \leq k−1 $, and let $f(p) = bq+r$, where $q\in \mathbb{N}$ and $0 \leq r \leq b−1$. Then $p + b = f(f(p)) = f(bq + r) = f(r) + bq$. Hence either $q = 0$ or $q = 1$ and therefore either $f(p) = r$, $f(r) = p + b$ or $f(p) = r + b$, $f(r) = p$.

In both cases we have $p \neq r$ which shows that $f$ defines a pairing of the set $A =\{0,1,...,b\}$. Note that different functions define different pairings of $A$. Conversely, any pairing of $A$ defines a function $f$ with the previous propriety. Thus the number of the functions with the given property is equal to that of all pairings of the set $A$. It is easy to see that this number is equal to $$\frac{b!}{(b/2)!}$$

Question What is the number of possible functions if $a>2$? is there any chance that the number is $\frac{b!}{(b/a)!}$?

$\endgroup$
8
$\begingroup$

Yes your guess is correct.
From your link, we have that $f(n)-n$ is constant when $n$ varies over any congruence class modulo $b$, which implies $f(b+n)=b+f(n)$ for all $n$.
Let $n$ be a nonnegative integer and let $n=bq+r$ where $0\leq r <b$, then $f(n)=bq+f(r)$, so the function $f$ is determined by its action on $B=\{0,\ldots,b-1\}$. For $i\in B$, write $f(i)=bq_i + r_i$, where $q_i\in \mathbb{Z}$ and $0\leq r_i<b$.
Firstly, we have $q_i \geq 0$, since $f(i)\geq 0$.
Secondly, we claim that $q_i \leq 1$. Let $g(n)= \lfloor n/b \rfloor$. If $n=bq+r$, then $$ g(f(n)) =g(n)+q_r\geq g(n) $$ Also, $g(f^{(a)}(n))=g(n)+1$. Now if there exists $i\in B$ such that $q_i\geq 2$, then $$ 1=g(b+i)=g(f^{(a)}(i)) \geq g(f(i)) = g(i)+q_i \geq 2 $$ which is a contradiction.
Now let $x_0,x_1,x_2,\ldots$ be the remainders when $i,f(i),f^{(2)}(i),\ldots$ are divided by $b$, resp. We can easily see that $x_{j+a}=x_j$. We claim that all $x_0,\ldots,x_{a-1}$ are distinct. Supoose $x_s = x_{s+t}$ for some $s,t<a$. Letting $m=f^{(s)}(i)$, we have $f^{(t)}(m)=m+bq_0$ for some $q_0$. Then, $$ m+abq_0=f^{(at)}(m)=m+tb $$ so we have $q_0 = t/a$ which is a contradiction since RHS is not an integer.
Define $P(i)$ as the set $\{i=x_0,\ldots,x_{a-1}\}$ where $x_j$'s are defined as above. Since $P(x_j)=\{x_j,x_{j+1},\ldots,x_{j+a-1}\}=P(i)$, we can easily see that the $P(i)$'s partition $B$ when $i$ varies over $B$.
Since $1=g(f^{(a)}(i))=q_{x_0}+\ldots+q_{x_{a-1}}$, there is precisely one $q_{x_j}$ that equals 1. The rest equals 0. Pick that $x_j$ as the representative of $P(i)=P(x_j)$, and define an $a$-tuple $Q(i)=Q(x_j)$ as $(x_{j+1},x_{j+2},\ldots,x_{j+a}=x_j)$.
What we have done so far is, when there is an $f$ satisfying the problem, we can partition $B$ into tuples of size $a$, and for each tuple $(y_0,\ldots,y_{a-1})$, we have $$ f(y_0)=y_1,f(y_1)=y_2,\ldots f(y_{a-2})=y_{a-1}\\ f(y_{a-1})=b+y_a=b+y_0 $$ Also, for every partition of $B$ into $a$-tuples, and defining $f$ as above, we get a valid $f$ satisfying the problem. The number of partition of $B$ into $a$-tuples equals $b!/(b/a)!$.

$\endgroup$
  • 1
    $\begingroup$ Thanks , that's what I'm looking for, an amazing result follows from this :Given $n\in \mathbb{N}^*$, the number of couples $(p,f)$ where $p\geq 1$ is an integer and $f:\mathbb{N}\rightarrow \mathbb{N}$ such that : $$\forall k \in \mathbb{N} \ \ \ \ \ \ \ \ \ f^{p}(k)=k+n $$ is : $$\sum_{d |n} \frac{n!}{d!}$$ $\endgroup$ – Elaqqad Feb 2 '15 at 21:01
6
+500
$\begingroup$

We can solve this while setting down the machinery to consider other functional sub-iterates. We can consider a function to be described by its functional graph - that is, a directed graph, where each vertex $v$ has an edge going to $f(v)$. For instance, we could draw $f(x)=x+1$ as

$$0\longrightarrow 1\longrightarrow 2\longrightarrow 3\longrightarrow 4\longrightarrow \cdots. $$

More generally, $f(x)=x+b$ looks like this:

$$0\longrightarrow b+0\longrightarrow 2b+0\longrightarrow 3b+0\longrightarrow \cdots$$ $$1\longrightarrow b+1\longrightarrow 2b+1\longrightarrow 3b+1\longrightarrow \cdots$$ $$\vdots$$ $$b-1\longrightarrow 2b-1\longrightarrow 3b-1\longrightarrow 4b-1\longrightarrow \cdots$$

That is, if we describe the graph of $x\mapsto x+1$ as being a chain, then the graph of $x\mapsto x+b$ is $b$ disjoint chains. If we wish to be very formal, we can define a chain $C$ to be a set such that the image $f(C)$ and preimage $f^{-1}(C)$ both equal $C$.

From here on in, let $f(x)=x+b$. Now, suppose that a function $g$ has that $g^a=f$. Several things should be clear: firstly, $f$ and $g$ commute under composition: $$g\circ f = g\circ g^{a}=g^{a+1}=g^{a}\circ g = f\circ g.$$ An important consequence of this is that if we know, for instance, $g(k)$, then we know that $g(f(k))=f(g(k))$ meaning $g(x+b)=g(x)+b$. In the functional graph this gives the following easy corollary:

If $C$ is a connected part of the functional graph (i.e. a chain), then the image $g(C)$ is a subset of a connected part of the chain. There is thus some well-defined map $G$ mapping chains to other chains such that if $x\in C$ then $g(x)\in G(C)$.

An example of the above would be that if $b=2$ and $g(x)=x+1$, then $G$ would map the set of even numbers to the set of odd numbers and vice versa - it can be interpreted as a map on equivalence classes mod $b$, but we only need the fact that it acts on chains. It is notable that clearly $G^a$ is the identity function, because if $x\in C$ then $f(x)\in C$ meaning $g^a(x)\in C$. An off-shoot of this is that $G$ is a bijection, since if an iterate of it is a bijection (i.e. the identity here), it must be a bijection too. More strongly, we have the following lemma:

There can be no $0<a'<a$ and $C$ such that $G^{a'}(C)=C$. That is, $G^a$ is the least iterate with fixed points.

To prove this, suppose $a'$ is the least such $a'$. If $a'$ does not divide $a$, then $a=k+na'$ for $0<k<a'$, then $G^{a}(C)=G^{k+na'}(C)=G^{k}(C)$. This cannot be, since $G^k$ can have no fixed points, but $G^{a}$ must be the identity. If $a'$ does divide $a$ then $a=na'$ for $n>1$. However, in this case, the restriction of $g^{a'}$ to $C$ is a map $C\rightarrow C$. However, this would mean that the $n^{th}$ iterate of $g^{a'}$ is $f$ - but $f$ restricted to $C$ is isomorphic to $x\mapsto x+1$ (because $C$ is a chain) which has no sub-iterates (as you've proven). Thus $g^{a'}$ cannot have its $n^{th}$ iterate equal to $f$ on $C$, creating a contradiction.

This means that $G$ is a permutation on the $b$ chains where each cycle has length $a$. Immediately, this gives that no functions exist if $a$ does not divide $b$. To wrap up, we consider the map $g$ restricted to a single chain $C_1$ mapping to $C_2=G(C_1)$. Since $f$ commutes with $g$, it is easy to see that this is determined. Moreover, since $C_1$ is the only chain with $G(C_1)=C_2$, due to $G$ being a bijection, it follows that the image $g(\mathbb N)\cap C_2=g(C_1)$. Since the image of $g$ must contain the image of $f$, the following follows:

If $C_1$ is the naturals equal to $k_1$ mod $b$ and $C_2$ is those equal to $k_2$ mod $b$ where $0\leq k_1,k_2 < b$, one of the following holds for all $x\in C_1$: $$g(x)=x-k_1+k_2$$ $$g(x)=x-k_1+k_2+b$$ This is because $g$ is determined by $g(k_1)$, which may either be $k_2$ or $k_2+b$, since $k_2+b$ is in the image of $f$ and would not be included in the image of $g$ if we set $g(k_1)=k_2+2b$, for instance.

We will call a chain $C_1$ where $g$ satisfies the former identity to be "static” and one where $g$ satisfies the latter to be “advancing”.

It should be clear from computation that if an orbit $C,G(C),G^{2}(C),\ldots,G^{a-1}(C)$ contains $\ell$ advancing cycles, then for $x\in C$ we have $g^{a}(C) = a + \ell b$ - thus all such orbits have exactly one advancing cycle. This is intuitively noticing that a “static” chain maps corresponding elements to corresponding elements - that is, it maps the first element of a chain to a the first element of another and so on. An advancing map is $f$ composed with a static map. The maps $g$ all commute with $f$ and the composition of a cycle of static maps must be the identity (since it maps the first element of $C$ to the first element of $C$, for instance), so clearly we have the correct equality if and only if exactly one is advancing - and, for appropriate definitions of “static” and “advancing” over arbitrary functional graphs, this holds in general.

However, then this makes the combinatorics easy. In particular, every $g$ is uniquely determined by $G$, a permutation which is the product of $(b/a)$ disjoint cycles of length $a$, and a selection of $1$ advancing chain in each cycle. This works out as:

There are $\frac{b!}{(a!)^{b/a} (b/a)!}$ ways to divide the elements into disjoint sets of size $a$. If, in each set, we write the advancing cycle $C$ followed by $G(C), G^{2}(C),\ldots G^{a-1}(C)$, we can create a bijection between potential functions $G$ and identifications of an advancing chain with the set of permutations of $a$ elements. There are thus $a!$ was to choose $g$ on each of the sets of $a$ chains. There are $b/a$ such sets, thus the answer is $$\frac{b!}{(a!)^{b/a}(b/a)!}\cdot (a!)^{b/a}=\frac{b!}{(b/a)!}.$$

We can show that $x\mapsto x+b$ taken over all of integers has infinitely many sub-iterates when $a$ divides $b$, since every appropriate map $x+k$ from one chain to another can be considered to be either static or advancing, as there is no “starting point” in the integers to count from - so in choosing those "transition maps", we get infinitely much choice. Interestingly, we can use the same method to show that, for instance, $x\mapsto 2x$ over the positive integers is infinitely many chains, so we can make infinitely many sub-iterates of it for any $a$ (and the work above suffices to characterize all of them). If we consider $x\mapsto 2x$ including $0$ in the domain, we can show that, since we end up with a connected component of the functional graph which is just a cycle from $0$ to $0$, and since we cannot map this component to any other (since it very much does not look like a chain), that this consists of a sub-iterate of $x\mapsto 2x$ over the positive integers along with the definition that $0\mapsto 0$. We can also prove that the map $x\mapsto |x+b|$ taken over the integers not divisible by $b$ has sub-iterates whenever $a$ divides $b$, as its graph looks like a chain, where every element is given an extra incoming edge from a vertex with no edges going to it (there happen to be infinitely many sub-iterates of this when they exist, though, as the new nodes with no preimages add some degree of freedom). More complicated cases make this a strong way to visualize the issue, but things can get pretty hairy when looking at the general case.

$\endgroup$
0
$\begingroup$

Consider a matrix-equation with a $2 \times 2$-matrix $F$ $$ [1,x] \cdot F = [1,f(x)] $$ which describes the map $x \to f(x)$. Of course, the iteration can be done by taking $F$ to its 2'nd power $$ \small \begin{array} {} [1,x] \cdot F &=& [1,f(x)] \\ [1,f(x)] \cdot F &=& [1,f(f(x))] & \text{ or }\\ [1,x] \cdot F^2 &=& [1,f(f(x))] \end{array}$$

Matrices with that functionality have a certain shape (and name: "Transfer-" or "Carlemanmatrix") and for a linear function $f(x)=a+bx$ are defined as $$ F = \begin{bmatrix} 1&a \\ 0 & b \end{bmatrix}$$


Now by your example, the matrix $F^2$ which performs the map $x \to f(f(x))=1987+x$ must have the form $$ \small F^2 = \begin{bmatrix} 1&1987 \\ 0 & 1\end{bmatrix}$$ so that it is true that $$ \small \begin{array} {} & \cdot & \begin{bmatrix} 1&1987 \phantom{+1x} \\ 0 & 1\end{bmatrix} \\ \begin{bmatrix} 1&x \end{bmatrix} & =&\begin{bmatrix} 1& 1987+x \end{bmatrix} \end{array}$$ The root $F$ of $F^2$ is $$ \small F = \begin{bmatrix} 1&993.5 \\ 0 & 1\end{bmatrix}$$ so by this $f(x) = 993.5+x$ which is a function giving noninteger results for integer arguments. The other root is $-F$ , but this is then no transfermatrix in the above sense, because the top-left value is not the unit so this were no solution.
So the only possible solutions is the function $f(x) = 993.5+x$ and this produces fractional values for integer arguments $x$.

$\endgroup$
  • $\begingroup$ Now I have read the answers, and this doesn't appear to be one. $\endgroup$ – Jonas Meyer Feb 7 '15 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.