I would like to find the set of continuous functions $f_n(x)$, where $f_n(x):\mathbb{R}\to \mathbb{R}$ satisfies $$f_n(f_n(f_n(f_n...(x)))) = x$$ where there are $n$ iterations of $f(x)$. For example $f_1(x)$ would be the solution to $f_1(x)=x$. $f_2(x)$ would be the solution to $f_2(f_2(x)) = x$.

For $f_1(x)$, the only solution is $f_1(x)=x$. For $f_2(x)$, the solutions are involutions.

For $f_3(x)$, the only answer is $f_3(x)=x$. For all other $f_n(x)$, one solution is $f_n(x) = x$.

My question: For $n \ge 3$, is $f_n(x) = x$ the only solution? If not, what are the solutions?

Edit: @MattSamuel said that any involution works for an even $n$. This is because $f_n(f_n(x))$ can be replaced with $x$. For example, $$f_2(f_2(f_2(f_2(f_2(f_2(x)))))) = f_2(f_2(f_2(f_2(x)))) = f_2(f_2(x)) = x$$ However, this does not necessarily mean that involutions are the only set of solutions for $f_{2k}(x)$.

  • 5
    $\begingroup$ Involutions work for any even number of compositions. $\endgroup$ – Matt Samuel Jul 27 '19 at 19:48
  • $\begingroup$ @MattSamuel Wow, that is true. Can functions that aren't involutions work for an even number of compositions? $\endgroup$ – Varun Vejalla Jul 27 '19 at 19:51
  • $\begingroup$ Probably, but I don't know any off hand. $\endgroup$ – Matt Samuel Jul 27 '19 at 19:52
  • 1
    $\begingroup$ @PackSciences, only real functions. $\endgroup$ – Varun Vejalla Jul 27 '19 at 19:58
  • 1
    $\begingroup$ Ok, good you edited the question $\endgroup$ – PackSciences Jul 27 '19 at 19:58

There are no monotone solution for odd $n$ other then $f_n(x) = x$. There are also no continuous solutions as any continuous injection is monotone.

There are many discontinuous solutions for any $n$. Represent any real number $x$ as $x = \lfloor x \rfloor + \{x\}$ (integer and floor part), so we now have bijection $\mathbb{R} \leftrightarrow [0, 1) \times \mathbb{Z}$. Choose your favorite bijection $g_n: \mathbb Z \leftrightarrow \mathbb Z$ of order $n$ - for example, $g_n(i) = (i + 1) \mod n + \lfloor\frac i n\rfloor$ - split $\mathbb{Z}$ into segments of length $n$ and rotate any segment. Now define $f_n(x) = \{x\} + g_n(\lfloor x \rfloor)$. It's even continuous everywhere but in points $n - 1 + kn$.

(for simplicity, I'll denote $f^n$ to be $n$-th iteration of $f$ - we will not need powers here)

The only continuous solutions are involutions - answer you linked can be extended to proof it. $f$ have to be monotonic - if it isn't - say we have $f(x) > f(y) > f(z)$ while $x > z > y$ - then it's not injective, as there is point in $q \in [z, x]$ s.t. $f(q) = f(y)$, so we will have $f^n(q) = f^n(y)$ but $q \neq y$.

If $f$ is strictly increasing, then $f(x) = x$ by @Najib's argument.

If $f$ is strictly decreasing, then $f$ has a single fixed point $x_0$. We have $f(x_0 + a) < f(x_0) = x_0$ and $f(x_0 - a) > f(x_0) = x_0$ for positive $a$. $g =f\circ f$ is continuous and injective - so monotonic. As $f(x_0 + 1) < f(x_0)$, we have $f(f(x_0 + 1)) > x_0$, so $g$ is increasing. If $g(x) \neq x$ for some $x$, we will again have $f^n(x) \neq x$. So $g(x) = x$. And thus $f$ is involution.

| cite | improve this answer | |
  • 1
    $\begingroup$ Added part about continuous functions - involutions are the only answer. $\endgroup$ – mihaild Jul 27 '19 at 21:50
  • $\begingroup$ Just to make sure I understand correctly, there are no other solutions for odd $n$ other than $f_n(x) = x$ and no other even solutions for even $n$ other than involutions? $\endgroup$ – Varun Vejalla Jul 28 '19 at 17:46
  • $\begingroup$ Yes. Also, the only involutions on $\mathbb{R}$ are $f(x) = x$ and $f(x) = a - x$. $\endgroup$ – mihaild Jul 28 '19 at 18:53
  • $\begingroup$ That doesn't sound right. Isn't $1/x$ an involution too? $\endgroup$ – Varun Vejalla Jul 28 '19 at 19:48
  • $\begingroup$ Sorry, the only continuous involutions. $1 / x$ (defined in $0$ as $0$) isn't continuous. $\endgroup$ – mihaild Jul 28 '19 at 20:06

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.