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

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.

• How did you prove that $f(2x)=2f(x)$ ? – Dietrich Burde May 3 '15 at 19:36
• Substitute $f(x)$: $f(f(f(x)))=2f(x)$. Apply $f$ to both sides: $f(f(f(x)))=f(2x)$, therefore $f(f(f(x)))=f(2x)=2f(x)$. – wythagoras May 3 '15 at 19:41

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.
• Indeed, proving that $f(x)$ is odd or twice an odd is the key step. Thank you for your answer. – wythagoras May 3 '15 at 19:59
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$.