Discrete fractional iteration?

Question

I’m teaching a course in discrete mathematics and was exploring (purely for my own interest) whether there were any functions $f : \mathbb{Z} \to \mathbb{Z}$ such that $f(f(n)) = n + 1$. I then started thinking about a more general discrete version of problems like these: given some function $g : A \to A$ for a countable (or finite) set $A$, determine whether there are any functions $f : A \to A$ where $f \circ f = g$.

In reading up on this style of problem, I came across some earlier questions (1, 2, etc.) that talked about fractional iteration over real-valued and complex-valued functions. However, those techniques seem specific to continuous-values functions rather than discrete ones. And from what I’ve read these techniques were partially developed as ways to find continuous functions generalizing discrete ones (say, tetration). However, I’m simply looking for ways to find discrete-valued functions that compose to some target, which seems like it ought to be a different problem.

Is there a name for this style of problem in the discrete case, and are there any techniques known for solving this sort of problem? (And, in particular, does my original $n + 1$ case have a solution?

Answer 1

Such an $f$ would be a permutation on $\Bbb Z$ (that is a bijection $\Bbb Z\to\Bbb Z$), and that falls into cycles, possibly finite, but also possibly infinite (so a cycle like $(\cdots a_{-1}\,a_0\,a_1\,a_2\cdots)$ where the $a_i$ are distinct and $f(a_i)=a_{i+1}$).

If $f^2(n)=f(f(n))=n+1$, then $f^2$ has no finite cycles, and so $f$ doesn't, so $f$ has at least one infinite cycle. But this cycle splits into two cycles for $f^2$. But $f^2$ has only one cycle, so so such $f$ can exist.

Answer 2

Angina Seng’s argument is nicer, but one can also use a bit of brute force to show that there is no $f:\Bbb Z\to\Bbb Z$ such that $f\circ f:n\mapsto n+1$.

Such an $f$ must be a bijection with no fixed points. Suppose that $f(0)=a$; then $f(a-1)=0$, $f(-1)=a-1$, $f(a-2)=-1$, $f(-2)=a-2$, and so on. In particular, $f(-n)=a-n$ for $n\in\Bbb Z^+$. If $a>0$, this means that $f(-a)=0$.

But if $f(0)=a$ we also have $f(a)=1$, $f(1)=a+1$, $f(a+1)=2$, $f(2)=a+2$, and so on, so that $f(n)=a+n$ for $n\in\Bbb Z^+$, so that if $a<0$ we again have $f(-a)=0$.

Thus, $f(-a)=0=f(a-1)$, so $a-1=-a$, and $a=\frac12$, which is impossible, and there is therefore no such $f$.