Improvement IMO 1988 $f(f(n))=n+1987$

Question

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)!}$?

Answer 1

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)!$.

Answer 2

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$.

Answer 3

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.