If $f(f(x))$ is a linear function, must $f(x)$ be linear?

Question

I'm thinking of $f$ as a function either from the reals to the reals or from the naturals to the naturals.

Edit: Okay, what if $f$ is from the naturals to the naturals?

Answer 1

No. For example,$$ f(x) = \begin{cases} \displaystyle \frac{1}{x}; & x \neq 0\\ 0; & x = 0 \end{cases}. $$

Answer 2

If you want one from the naturals to the naturals, take $f(x)$ to be the function $f(1)=2,f(2)=1$, and $f(n)=n$ for $n\geq 3.$

Answer 3

As for $\Bbb N$, let $f(n)=n+1$ for odd and $=n-1$ for even $n$. One can twist this to fancier constructions by fancier partitions of $\Bbb N$.

Answer 4

This doesn't directly answer the question, but if $f$ is continuous from $\mathbb{R}\to\mathbb{R}$, it still can be nonlinear. For a concrete example, see the comments on this answer to one of my previous questions in a similar vein to this one; essentially, one can rotate the graph of

$$y=\epsilon \cos(x)$$

for small enough $\epsilon$ exactly $45^{\circ}$ counterclockwise, and it satisfies the property.

Answer 5

Another family of examples for $\mathbb N$: Let $p$ be prime, $q$ coprime to $p$. $f(n) = p n$ if the $p$-adic order of $n$ is even (i.e. $n = p^e m$ where $e$ is even and $m$ is coprime to $p$), otherwise $f(n) = q n/p$. Then $f(f(x)) = q x$.