On the equation F (x) = f(f(x))

Claudio Baiocchi

14th December 2004

1 The Problem

Following Ed Pegg Jr (see the section “Material added 21 November 04” on http://www.Mathpuzzle.com) we want to discuss the problem:

\begin{cases}which functions F have a representation of the form F (x) = f(f(x))? \\ for a given F, how many are the solutions, and how to build them? \end{cases}

We will confine ourselves to work in a polynomial framework, assuming that both F and f are polynomials. In fact the non-polynomial framework seems out of reach because unexpected non-polynomial solutions come out very often; see later on. On the other hand, we will allow complex coefficients for our polynomials F, f: as often happens, the real results easely follow from the complex ones; and the complex approach gives rise to more elegant results. Remark After reading a preliminary redaction of this paper, Ed sent me the feedback:

One interesting trick to add: (f(f(x)) − x)/(f(x) − x) always divides evenly

thus I added a last section, “Factorizations”, absent in the previous redaction.

2 Preliminary Remarks

Let us firstly deal with a somewhat anomalous case: the function F (x) = x + c has the solution f(x) = x + c/2. If c ≠ 0 we will see that this is the unique solution; however, if c = 0, for any a we can also choose f(x) = a − x. We will also see that, in the polynomial framework, the case F (x) = x is the unique one giving raise to infinitely many solutions. Remark that this F is singular even in the non-polynomial framework: for x ≠ 0 also the functions f(x) = a/x solve. A last remark on the non-polynomial case: the rational function F (x) = 2x/(1 − x^{2}) has, for |x| < 1, the trascendental solution f(x) = tan (\sqrt{2} · arctan(x)) . Let us fix some notations. For f polynomial of degree k, the polynomial f(f(x)) has degree k^{2}; thus, for a suitable k, we can represent the given F and the unknown f in the form:

F (x) = ∑_{j=0}^{k^{2}} A_{j}x^{k−j}; f(x) = ∑_{j=0}^{k} a_{j}x^{k−j}; (A_{0}, a_{0} ≠ 0);

remark that we used capital letters A_{j} for the data, and small letters a_{j} for the unknown coefficients. In other terms: we would freely choose the k^{2} + 1 coefficients of F, and impose the equation F (x) = f(f(x)) by using the k + 1 coefficients of f. It is quite natural to expect that, if k > 1, this is impossible; and in fact we will see that, generally speaking, once we fix the first k + 1 coefficients A_{0}, …, A_{k} we have no more degree of freedom.

3 Results

Let us evaluate f(f(x)) modulo the lower order terms, say the terms of order strictly less than k^{2} − k; we will use the symbol “≅” to denote that some lower order terms have been suppressed. Because of

\begin{cases}f(f(x)) ≅ a_{0} · [f(x)]^{k} + a_{1} · [f(x)]^{k−1} ; \\ a_{0} · [f(x)]^{k} ≅ a_{0} · [(a_{0} · x^{k})^{k} + k · [a_{0} · x^{k}]^{k−1} · [a_{1} · x^{k−1} + ⋯ + a_{k}]] ; \\ a_{1} · [f(x)]^{k−1} ≅ a_{1} [a_{0} · x^{k}]^{k−1} \end{cases}

we get:

f(f(x)) ≅ a_{0}^{k+1} · x^{k∗k} + k · [a_{0} · x^{k}]^{k−1} · [a_{1} · x^{k−1} + ⋯ + a_{k}] + a_{1} [a_{0} · x^{k}]^{k−1}

The comparison between the leading coefficients of F (x) and f(f(x)) gives:

A_{0} = a_{0}^{k+1};  A_{j} = k·a_{0}^{k} ·a_{j} for j = 1, …, k−1;  A_{k} = k·a_{0}^{k} ·a_{k} +a_{1} ·a_{0}^{k−1}.

In particular, from a_{0}^{k+1} = A_{0}, we have k + 1 possible choices for a_{0} (recall that A_{0} ≠ 0). Once a value for a_{0} has been fixed:

• if k = 0 we finished;

• if k = 1, we need a_{1} = A_{1}/ (a_{0} + 1), to be discussed later on;

• if k > 1 we must choose:

a_{j} = A_{j}/ (k · a_{0}^{k}) for j = 1, …, k − 1;

a_{k} = (A_{1} − a_{1} · a_{0}^{k}) / (k · a_{0}^{k}) = (A_{k} − A_{1}/k) / (k · a_{0}^{k})

the last formula following from the already known form of a_{1}.

The case k = 1, as already remarked, deserves a surprise: for A_{0} ≠ 1 we simply need to choose a_{1} = A_{1}/ (a_{0} + 1); the same formula remains true if A_{0} = 1 and we choose a_{0} = 1; however, for A_{0} = 1, if we want to choose a_{0} = −1, we need A_{1} = 0; then any value for a_{1} is allowed.

Let us summarize the results in the complex framework. Searching for representable polynomials F (x) of degree k, we have:

• If k < 2, for any choice of F (x) other than x + c, there exist exactly k + 1 solutions.

• If k ≥ 2 we can freely choose the first k +1 coefficients of F; this generates k + 1 functions f that automatically select theyr own “lower order part” for F.

Let us show how the last claim works by discussing the original example F (x) = x^{4} − 4x^{3} + 8x + 2 proposed by Ed Pegg. Our formulas force f(x) = ω · x^{2} − 2ω · x + 1 − 2ω, where ω denotes a third root of the unit. Accordingly we get f(f(x)) = x^{4} − 4x^{3} + 8x + 5 − 3ω; thus we need ω = 1, say f(x) = x^{2} − 2x − 1.

A last remark concerns the real framework: let F (x) be a real polynomial of degree k, other than x + c. Among the k + 1 complex-coefficients polynomials f we have built, the number of real f is just one if k is odd; and, for even k, is two or none, according to A_{0} > 0 or A_{0} < 0.

4 Factorizations

A somewhat different approach can be based on factorizations results; e.g. let us remark that:

F′(x)/f′(x) always divides evenly

as obvious because of F′(x) = f(f(x))′ = f′(f(x)) · f′(x). RemarkLet x_{0} be a (real or complex) value such that f(x_{0}) = x_{0}. Then:

• F′(x_{0}) = f′(x_{0})^{2}.

• F′′(x_{0}) = f′′(x_{0})f′(x_{0})^{2} + f′(x_{0})f′′(x_{0})

• For k > 2 any term appearing in F^{(k)}(x_{0}) contains a factor like f^{(j)}(x_{0}) for a j ≥ 2.

Now let us set G(x) := f(f(x)) − x and g(x) := f(x) − x. For any x_{0} with g(x_{0}) = 0 one has G(x_{0}) = 0; if one has also g′(x_{0}) = 0, say f′(x_{0}) = 1 then (see the previous remark) G′(x_{0}) = F′(x_{0}) − 1 = 0; always due to the previous remark, if g′′(x_{0}) = 0, say f′′(x_{0}) = 0, then G′′(x_{0}) = 0; and so on. In other words, any (real or complex) root of g is also a root of G with at least the same molteplicity; this implies that g(x) is a factor of G(x); say:

(f(f(x)) − x)/(f(x) − x) always divides evenly.

Let us see how these properties can be used, by treating again the example F (x) = x^{4} − 4x^{3} + 8x + 2: we confine ourselves to discuss the real case, thus the leading coefficients of f and f′ must be 1 and 2, instead of ω and 2ω. Because of F′(x) = 4(x−1)(x−1−\sqrt{3})(x−1+\sqrt{3}), for f′(x) we have to choose one among 2(x − 1), 2(x − 1 − \sqrt{3}) and 2(x − 1 + \sqrt{3}). Because of F (x) − x = (x − 2)(x + 1)(x − \frac{3+\sqrt{13}}{2})(x − \frac{3−\sqrt{13}}{2}) we have a priori six possible choices for the second degree polynomial f(x) − x; but only the choice f(x) − x = (x − \frac{3+\sqrt{13}}{2})(x − \frac{3−\sqrt{13}}{2}) = x^{2} − 3x − 1 is compatible with the formulas we got for f′(x); thus we end up with the already found solution f(x) = x^{2} − 2x − 1.