Functional equation $f(f(x))=2x$ on $\mathbb{Z}_{>0}$

Question

I have this functional equation: $$f(f(x))=2x$$ with $f: \mathbb{Z}_{>0}\rightarrow \mathbb{Z}_{>0}$. And I want to know if it is possible to list all solutions.

I already know that $f(2x)=2f(x)$, further, if $f(1)=c$, then $f(2^kc)=2^{k+1}$ by induction and $f(2^k)=2^kc$ but that doesn't really give anything. I have attempted, but I think there is a clever step I don't see. Also, since $f \circ f$ is injective, $f$ must be injective.

I actually suspect that there either no solutions or uncountably many, of which most aren't nice functions.

Answer 1

An example function satisfying this property is the function $f$ defined by $$ f((4k+1)2^i) = (4k+3)2^i\\ f((4k+3)2^i) = (4k+1)2^{i+1} $$ Fundamentally, all answers are at least somewhat similar to this. You should try to prove that for all odd $x$, $f(x)$ is either odd or twice an odd number, in which case $x = f(f(x)/2)$. You can then describe all solutions as indexed by partitions of the odd numbers into ordered pairs $(a_1, b_1), (a_2, b_2), \ldots$, where $$f(a_i2^j ) = b_i2^j\\ f(b_i2^j) = a_i2^{j+1}$$ This leads to an uncountable number of solutions.

Answer 2

To see that such a function exists let $f$ be defined as follows, if $n=2k$ is even, let $f(n)=2f(k)$, if $n=4k+1$, let $f(n)$ be $4k+3$, and if $n=4k+3$, let $f(n)=2(4k+1)$.

Then $f(f(2^j(4k+1)))=2^jf(f(4k+1))=2^jf(4k+3)=2^{j+1}(4k+1)$ as desired, and $f(f(2^j(4k+3)))=2^jf(f(4k+3))=2^jf(2(4k+1))=2^{j+1}(4k+3)$. Since any positive integer can be written in one of these forms for $j$ and $k$ nonnegative integers this function satisfies your property.

In general this construction can be done in the same way if $g$ is an involution in the positive odd integers. $g$ pairs up the odd integers with each other let $S$ be a set containing one element in each pair. Then define $f(2k)=2f(k)$, and otherwise $f(n)=g(n)$ if $n\in S$, and $f(n)=2g(n)$ if $n\not\in S$.

I'm sorry I don't have a complete characterization, but I thought I'd post this partial solution.

Answer 3

Here is a more general result.

Claim. Let $a\geq 1, k\geq 2$ be integers. Then there are infinitely many functions $f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ such that $$\overbrace{f(f(\dots f(n)\dots))}^{k \text{ times}}=an, \text{ for all }n\in \mathbb{Z}^{+}.$$ Furthermore all these functions are described by partitioning positive integers into disjoint tuples of $k$ distinct integers (for $a\geq 2$ none of these integers are multiples of $a$). For each such tuple $(n_1,n_2,\dots,n_k)$ then $f$ maps $$ a^in_1 \mapsto a^in_2 \mapsto \dots \mapsto a^in_{k-1} \mapsto a^in_{k} \mapsto a^{i+1}n_{1}. $$ for all $i \geq 0$.

Proof. We can see that all values $a^in_j$ with mapping above satisfy the functional equation and also these values cover all positive integers (note that $a^ic=a^jd$ with $a\not\mid c$, $a\not\mid d$ implies $i=j$, $c=d$).

To show that all $f$ are of the form above, pick any positive integer $b$ fixed and define a sequence $b_1=b$, $b_{i+1}=f(b_i)$. Then the equation implies $b_{i+k}=ab_i$, so we have a linear recurrence of degree $k$. This proves the claim for $a=1$. For $a\geq 2$ we can assume the initial value $b$ is such that there does not exist $c\neq b$ with $f(c)=b$ (otherwise choose $c$ as a starting point, cycles are impossible as the values increase after each $k$ steps). Now if any of the initial values is a multiple of $a$, then $an=f(f(\dots f(n)\dots))$ implies we can go back $k$ steps in the sequence, contradicting our assumption. So none of the initial values is a multiple of $a$ and $b_1,b_2,\dots,b_k$ satisfy conditions of the claim. Repeating this process for the remaining integers we get the partitioning from the claim. $\square$

Let's demonstrate the above and construct a generic example that works for all $a\geq 2$, $k\geq 2$. Since we want to avoid multiples of $a$, we can define $f(n)=af(n/a)$ when $a\mid n$ and for rest of the values we either set $f(n)=n+a$, or, if we are at the end of tuple of $k$ elements, we need to loop back. This will create blocks of size $ka$ where remainders mod $a$ are within the same loop (up to a power of $a$) of length $k$. If we put this into a function description we eventually get $$ f(n)=\begin{cases} af(\frac{n}{a}) & a \mid n \\ a(\lfloor \frac{n}{ka} \rfloor ka+n\bmod a) & \lfloor \frac{n}{a}\rfloor = \lfloor \frac{n}{ka} \rfloor k+k-1\\ n+a & \text{else} \end{cases} $$ Your problem is an instance of $a=2,k=2$, so plugging it into the above and spliting the cases based on $n \bmod 4$, we find a solution $$ f(n)=\begin{cases} 2f(\frac{n}{2}) & n\equiv 0 \pmod 2 \\ 2(n-2) & n\equiv 3 \pmod 4\\ n+2 & n\equiv 1 \pmod {4} \end{cases} $$ This is by the way A002516.