5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How did you prove that $f(2x)=2f(x)$ ? $\endgroup$ – Dietrich Burde May 3 '15 at 19:36
  • 2
    $\begingroup$ 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)$. $\endgroup$ – wythagoras May 3 '15 at 19:41
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Indeed, proving that $f(x)$ is odd or twice an odd is the key step. Thank you for your answer. $\endgroup$ – wythagoras May 3 '15 at 19:59
2
$\begingroup$

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.

$\endgroup$

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.