solving $f(f(x))=g(x)$

Question

This question is of course inspired by the question How to solve f(f(x))=cosx and Joel David Hamkins' answer, which somehow gives a formal trick for solving equations of the form $f(f(x))=g(x)$ on a bounded interval. [EDIT: actually he can do rather better than this, solving the equation away from a bounded interval (with positive measure)].

I've always found such questions ("solve $f(f(x))=g(x)$") rather vague because I always suspect that solutions are highly non-unique, but here are two precise questions which presumably are both very well-known:

Q1) Say $g:\mathbf{R}\to\mathbf{R}$ is an arbitrary function. Is there always a function $f:\mathbf{R}\to\mathbf{R}$ such that $f(f(x))=g(x)$ for all $x\in\mathbf{R}$?

Q2) If $g$ is as above but also assumed continuous, is there always a continuous $f$ as above?

The reason I'm asking is that these questions are surely standard, and perhaps even easy, but I feel like I know essentially nothing about them. Apologies in advance if there is a well-known counterexample to everything. Of course Q1 has nothing to do with the real numbers; there is a version of Q1 for every cardinal and it's really a question in combinatorics.

EDIT: Sergei Ivanov has answered both of these questions, and Gabriel Benamy has raised another, which I shall append to this one because I only asked it under an hour ago:

Q3) if $g$ is now a continuous function $\mathbf{C}\to\mathbf{C}$, is there always continuous $f$ with $f(f(x))=g(x)$ for all $x\in\mathbf{C}$?

EDIT: in the comments under his answer Sergei does this one too, and even gives an example of a continuous $g$ for which no $f$, continuous or not, can exist.

Related MO questions: f(f(x))=exp(x) and other functions just in the middle between linear and exponential, and Does the exponential function has a square root.

Answer 1

Q1: No. Let $g(0)=1, g(1)=0$ and $g(x)=x$ for all $x\in\mathbb R\setminus\{0,1\}$. Assuming $f\circ f=g$, let $a=f(0)$, then $f(a)=1$ and $f(1)=g(a)=a$ since $a\notin\{0,1\}$. Then $g(1)=f(f(1))=f(a)=1$, a contradiction.

Q2: No. Let $g(x)=-x$ or, in fact, any decreasing function $\mathbb R\to\mathbb R$. Then $f$ must be injective and hence monotone. Whether $f$ is increasing or decreasing, $f\circ f$ is increasing.

Answer 2

Ulm invariants.

Surely someone still knows this? Given $f \colon A \to A$ and $g \colon B \to B$, is there a bijection $\phi \colon B \to A$ such that $f(\phi(x))=\phi(g(x))$? There is a system of cardinal numbers, the Ulm invariants, associated with $f$ so that the answer is ``yes'' if and only if $f$ and $g$ have the same invariants.

If $f$ is bijective, then the Ulm invariants are just counts of how many cycles of each size there are (including the infinite cycle size modeled by the integers with $n \mapsto n+1$).

But when not bijective, the system of invariants is more complicated. You need to count how many points map to each fixed point, and how many points map to each of them, and so on. And similarly for cycles of other sizes. But I cannot tell you the details, and this box is probably not the right place to do it anyway.

So for a solution to the problem, consider what the Ulm invariants of $f(f(x))$ are in terms of those of $f$. Then compare to the Ulm inveriants of $\cos$. Or whatever you want to get.

Ulm himself may have originally done this to study isomorphism of abelian groups. Taking products, reduce to the case of a $p$-group for a given prime $p$, then your map for study is $x \mapsto x^p$. Or something like that. Ulm invariants may also be given to characterize up to isomorphism linear transformations (on possibly infinite-dimensional vector space).

Answer 3

Q2) has a negative answer. Namely, if, e.g., $g(x)=-x$ for all $x\in\mathbb{R}$, then there is no continuous $f:\mathbb{R\rightarrow\mathbb{R}}$ such that $f\circ f=g$.

---

As to Q3, see, e.g., Theorem 3 in http://yaroslavvb.com/papers/rice-when.pdf.

Answer 4

This type of equation is an "iterative functional equation." A good starting point for the literature on this subject is the book Iterative Functional Equations by Kuczma, Choczewski, and Ger, Cambridge University Press, 1990.

The most frequently asked question of this type has $g(x) = e^x$. A real-analytic solution in this case was constructed by H. Kneser, "Reelle analytische Lösungen der Gleichung $\varphi(\varphi(x))=e^x$ und verwandter Funktional-gleichungen", J. Reine Angew. Math. 187 (1949), 56-67.

Other useful keywords include "fractional iteration" and "iterative square root" (or more generally "iterative root").

Answer 5

I don't have a full answer, but I can offer here a small improvement on my other answer. Namely, what was important was not that it worked on a bounded interval, but rather, that it works outside a bounded interval.

Theorem. For any function g on the reals, there are numerous functions f such that f(f(x)) = g(x), for all x except those in a given fixed tiny interval.

Proof. Suppose g is a function on the reals and that I is a given interval, no matter how small. Let h be a bijection of R - I with I. Let f(x) = h(x), if x is outside I, and f(x) = g(h^-1(x)), if x is in I. Thus, f first translates x into I, if it is outside I, and otherwise, untranslates and computes g, if it is in I. It follows that f(f(x)) = g(x) for all x outside I. There are 2^|R| many such h's, and hence also this many f's.QED

If g is continuous, then this f can be chosen also to be continuous.

By using a Cantor set instead of an interval, one can find a function f that solves f(f(x)) = g(x) except on a set of measure zero.

Answer 6

The following is inspired by the chapter Partition Polynomials in Riordan's Combinatorial Identities where $g(x)$ is analytic and $g(0)=0$. Find the Taylor series of $f(x)$ at zero by evaluating the derivatives of $f(f(x))=g(x)$ at $0$ in succession.

Set $f(0)=0$, giving $f(f(0))=g(0)=0$.

The first derivative gives $f'(x) f'(f(x))=g'(x)$, therefore $f'(0)=\sqrt{g'(0)}$ and $f'(0)=-\sqrt{g'(0)}$. Set $f'(0)=\sqrt{g'(0)}$ for this example.

The second derivative $f'(x)^2 f''(f(x))+f'(f(x)) f''(x)=g''(x)$ produces $f''(0)=\frac{g''(0)}{g'(0)+\sqrt{g'(0)}}$.

The first few term of the Taylor series are

$f(x)=\sqrt{g'(0)}x+\frac{ g''(0)}{2 \left(g'(0)+\sqrt{g'(0)}\right)}x^2$ $+\frac{ \left(-3 g''(0)^2+g^{(3)}(0) g'(0)^{3/2}+2 g^{(3)}(0) g'(0)+g^{(3)}(0) \sqrt{g'(0)}\right)}{6 \left(\sqrt{g'(0)}+1\right)^2 g'(0) \left(g'(0)+1\right)}x^3+O(4)$.

This solution is based on $g(x)$ having a fixed point. Technically the question stated is whether there is always a solution and is focused on counter examples instead of a broad general answer as I have provided. But it does raise the question of whether there is a connection between $g(x)$ not having a fixed point and the counter examples that the other authors have provided.

Answer 7

This is a repost, and partial rewrite of an earlier deleted answer by Anixx. If you want to discuss the wisdom of that deletion, take it to the meta thread; let's keep this post focused on math only. This answer is community wiki, so that others can improve it.

If $a_k$ is any sequence of real numbers, indexed by the nonnegative integers, then define $\Delta^m(a) = \sum_{k=0}^{m} (-1)^k \binom{m}{k} a_k$. Then, for integer $n$, we have $a_n = \sum_{m=0}^{\infty} \binom{n}{m} \Delta^m(a)$. Note that the sum is finite, because all but finitely many binomial coefficients vanish. One can then try defining $$A(x) = \sum_{m=0}^{\infty} \binom{x}{m} \Delta^m(a).$$ If this sum converges, it defines a function $A$ which interpolates $a_n$. This is sometimes called Newton's interpolation formula.

Anixx points out that, $a_n = \sin^{[n]}(x)$ this method appears to give a good answer, but for $\cos^{[n]}(x)$, it appears not to.

Answer 8

A variant of the question is: Suppose that $g$ is a diffeomorphism. Can you embed $g$ into a flow? If yes, then there is $f$ with $f\circ f\circ\dots\circ f=g$ ($n$ times for any $n$).

So let $Diff_c(M)$ be the regular Lie group of all diffeomorphisms of a smooth manifold $M$. Its Lie algebra is the space $\mathfrak X_c(M)$ of all smooth vector fields with compact support, with the negative of the usual Lie bracket. The exponential mapping is the flow mapping which maps a vector field $X$ to its flow $t\mapsto Fl^X_t\in Diff_c(M)$. It satisfies $T_0\exp = Id$ but:

It is not locally surjective near $Id_M$. This has been shown by Freifeld 1967 and by Koppell 1970. The strongest result is by Grabowski, 1988, who showed the following: Suppose that $\dim M\ge 2$. Then there exists a smooth curve through $Id$ in $Diff_c(M)$ such that the points of this curve (sauf the identity) are free generators for a free subgroup of $Diff_c(M)$ (on $2^{\aleph_0}$ generators) which meets the image of the exponential mapping only at the identity. This free subgroup is arcwise connected.

See page 456 of "The convenient setting of global analysis", also for exact references.

Answer 9

I could have sworn that there was an old Monthly article that discussed precisely this question in some detail, but the closest that I could find in a few minutes on Mathscinet is the following article addressing the case $g(x) = 1/x$:

MR1641972: Cheng et al, “When does $f^{-1} = 1/f$?”, Amer. Math. Monthly 105, number 8.