Properties of $f(f(x))=g(x)$

Question

With reference to this Youtube video, I was trying to find out what important information we can gain from the equation $f(f(x))=g(x)$ [Assume all functions to be real]

One particularly interesting one that I found was this:

Consider $\text{Fix}(g)$ to be the set of all real numbers invariant under the map $g$ (which is to say that $\text{Fix}(g)=\{x:x\in\mathbb{R},g(x)=x\}$). Now, $$\begin{eqnarray} &&f(f(x))=g(x)\\ &\implies& f(f(f(x)))=f(g(x))\\ &\implies&g(f(x))=f(g(x)) \end{eqnarray}$$ This implies compositional commutativity of the 2 functions. Now for any arbitrary $x_0$ in $\text{Fix}(g)$: $$\begin{eqnarray} &&g(f(x_0))=f(g(x_0))\\ &\implies& g(f(x_0))=f(x_0) \end{eqnarray}$$ So, $f(x_0)$ must also be in $\text{Fix}(g)$, as it is invariant under $g$.

So, we can conclude that if $x_0$ is invariant under $g$, then $f(x_0)$ will also be invariant under $g$

Similarly, we can also show that if $x_0$ is invariant under $f$, then $g(x_0)$ is also invariant under $f$.

[This is particularly useful when $\text{Fix}(g)$ has only one element]

Now my question is: What are the other useful pieces of information that we can extract from $f(f(x))=g(x)$?

I know this is a little broad-ended, but I am looking for all possible perspectives to inspect this problem. I am intending for the answers and comments to this question to be a compendium of everything that we can extract from the relation.

Answer 1

I happen to have some notes about this equation. In particular, it is useful for showing that for some $g$, $f(f(x)) = g(x)$ has no solutions, by analyzing the orbits of $g$. I wrote this in order to show $$f(f(x)) = x^2 + 3x - 3$$ has no solutions $f: \mathbb{R} \to \mathbb{R}$, though the results I get are more general.

$\newcommand{\abs}[1]{\lvert #1 \rvert}$

Throughout, suppose $f(f(x)) = g(x)$, where $g$ is some given function and we want to solve for $f$.

Proposition: Let $x_0$ be a fixed point of $f$. Let $S_k$ be the set of $x$ such that $g^{(k)}(x) = x_0$. If $f(x_0) = x_0$ and $\abs{S_1} = 2$, then $S_2 = S_1$.

Proof: Let $S_1 = \{x_0, x_1\}$. Then we have $$x_0 = f(g(x_1)) = g(f(x_1)).$$ So $f(x_1) \in \{x_0, x_1\}$. But $f(f(x_1)) = x_0$, so $f(x_1) \neq x_1$. So $f(x_1) = x_0$.

Now suppose for the sake of contradiction that $x_2 \in S_2 \backslash S_1$. Then $g(x_2) \in S_1 \backslash S_0$, so $g(x_2) = x_1$. Thus $$g(f(x_2)) = f(g(x_2)) = f(x_1) = x_0.$$ So $f(x_2) \in S_1 = \{x_0, x_1\}$. But in either case, we have $g(x_2) = f(f(x_2)) = x_0$, contradiction!

$\square$

For example, let $g(x) = x^2 + 3x - 3$ and $x_0 = 1$. We have $S_1 = \{1, -4\}$ and $\abs{S_2} = 4$. So $x_0$ cannot be a fixed point of $f$.

Proposition: Let $I_k$ be the set of $x$ such that $g^{(k)}(x) = x$. Then

1. $f$ is a bijection from $I_k \backslash I_{k - 1}$ to itself.

2. It is not possible that $\abs{I_2 \backslash I_1} = 2$.

Proof: First, note that $f$ is injective on $I_k$, as $f^{(2k)}(x) = x$ holds.

Suppose $a \in I_k \backslash I_{k - 1}$. Note that $g^{(k)}(f(a)) = f(g^{(k)}(a)) = f(a)$, so $f(a) \in I_{k}$.

For the sake of contradiction, suppose $f(a) \in I_{k - 1}$. Then $f(a) = g^{(k - 1)}(f(a)) = f(g^{(k - 1)}(a))$. But $g^{(k - 1)}(a) \neq a$ and both lies in $I_k$, contradicting the injectivity of $f$!

So $f$ maps $I_k \backslash I_{k - 1}$ to itself. The inverse of $f$ is $f^{(2k - 1)}$.

If $\abs{I_2 \backslash I_1} = 2$, then since $f$ is a bijection on $I_2 \backslash I_1$, we have $g(x) = f(f(x)) = x$ for any $x \in I_2 \backslash I_1$, contradicting the fact that $x \notin I_1$.

$\square$

For example, let $g(x) = x^2 + 3x - 3$. We have $I_1 = \{1, -3\}$ and $I_2 = \{1, -3, \sqrt{3} - 2, -\sqrt{3}-2\}$. So a corresponding $f$ doesn't exist.