\documentclass{article}
%\documentclass[11pt]{article}
\usepackage[english]{babel}
\usepackage{amsmath,amssymb,amscd}
\begin{document}
\title{On the equation $F(x)=f(f(x))$ }
\author{Claudio Baiocchi}
\maketitle
\parindent 0pt
\section{The Problem}
Following Ed Pegg Jr (see the section ``Material added 21 November 04'' on {\sl http://www.Mathpuzzle.com}) we want to discuss the problem:
$$\begin{cases}\text{which functions $F$ have a representation of the form $F(x)=f(f(x))$?}\cr
\text{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.
{\bf Remark} {\sl After reading a preliminary redaction of this paper, Ed sent me the feedback:
\centerline{\rm\small 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.}
\section{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\ne0$ 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\ne0$ 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\left(\sqrt{2}\cdot\arctan(x)\right).$
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)=\sum\limits_{j=0}^{k^2}A_jx^{k-j};\quad f(x)=\sum\limits_{j=0}^ka_jx^{k-j};\qquad(A_0, a_0 \ne0);$$
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,\dots,A_k$ we have no more degree of freedom.
\section{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 ``$\cong$'' to denote that some lower order terms have been suppressed. Because of $$\begin{cases}f(f(x)) \cong a_0\cdot[f(x)]^k+a_1\cdot[f(x)]^{k-1}\,;\cr
a_0\cdot[f(x)]^k\cong a_0\cdot\left[\left(a_0\cdot x^k\right)^k+
k\cdot\left[a_0\cdot x^k\right]^{k-1}\cdot\left[a_1\cdot x^{k-1}+\cdots+a_k\right]\right]\,;\cr
a_1\cdot[f(x)]^{k-1}\cong a_1\left[a_0\cdot x^k\right]^{k-1}
\end{cases}$$
we get:
$$f(f(x)) \cong a_0^{k+1}\cdot x^{k*k} +
k\cdot\left[a_0\cdot x^k\right]^{k-1}\cdot\left[a_1\cdot x^{k-1}+\cdots+a_k\right]+
a_1\left[a_0\cdot x^k\right]^{k-1}$$
The comparison between the leading coefficients of $F(x)$ and $f(f(x))$ gives:
$$A_0=a_0^{k+1};\qquad A_j=k\cdot a_0^k\cdot a_j{\rm\ for\ }j=1,\dots,k-1;\qquad A_k=k\cdot a_0^k\cdot a_k+a_1\cdot 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\ne0$). Once a value for $a_0$ has been fixed:
\begin{itemize}
\item{} if $k=0$ we finished;
\item{} if $k=1$, we need $a_1=A_1/\left(a_0+1\right)$, to be discussed later on;
\item{} if $k>1$ we must choose:
\subitem{} \qquad$a_j=A_j/\left(k\cdot a_0^k\right)$ for $j=1,\dots,k-1$;
\subitem{} \qquad$a_k=\left(A_1-a_1\cdot a_0^k\right)\big/\left(k\cdot a_0^k\right)=\left(A_k-A_1/k\right)\big/\left(k\cdot a_0^k\right)$
the last formula following from the already known form of $a_1$.
% {\sl (because of the formula we got for $a_1$)}.
\end{itemize}
The case $k=1$, as already remarked, deserves a surprise: for $A_0\ne1$ we simply need to choose $a_1=A_1/\left(a_0+1\right)$; 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.
\medskip
Let us summarize the results in the complex framework. Searching for representable polynomials $F(x)$ of degree $k$, we have:
\begin{itemize}
\item{} If $k<2$, for any choice of $F(x)$ other than $x+c$, there exist exactly $k+1$ solutions.
\item{} If $k\ge2$ 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$.
\end{itemize}
Let us show how the last claim works by discussing the original example $F(x) = x^4- 4 x^3 + 8 x + 2$ proposed by Ed Pegg. Our formulas force $f(x)=\omega\cdot x^2-2\omega\cdot x +1-2\omega$, where $\omega$ denotes a third root of the unit. Accordingly we get $f(f(x))=x^4-4x^3+8x+5-3\omega$; thus we need $\omega=1$, say $f(x)=x^2-2x-1$.
\medskip
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$.
\section{Factorizations}
A somewhat different approach can be based on factorizations results; e.g. let us remark that:
\centerline{\sl $F'(x)/f'(x)$ always divides evenly}
as obvious because of $F'(x)=f(f(x))'=f'(f(x))\cdot f'(x)$.
%\smallskip
{\bf Remark}{\sl Let $x_0$ be a (real or complex) value such that $f(x_0)=x_0$. Then:
\begin{itemize}
\item{} $F'(x_0)=f'(x_0)^2$.
\item{} $F''(x_0)=f''(x_0)f'(x_0)^2+f'(x_0)f''(x_0)$
\item{} For $k>2$ any term appearing in $F^{(k)}(x_0)$ contains a factor like $f^{(j)}(x_0)$ for a $j\ge2$.
\end{itemize}}
%\smallskip
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:
\centerline{\sl $(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- 4 x^3 + 8 x + 2$: we confine ourselves to discuss the real case, thus the leading coefficients of $f$ and $f'$ must be $1$ and $2$, instead of $\omega$ and $2\omega$.
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-{3+\sqrt{13}\over2})(x-{3-\sqrt{13}\over2})$ we have a priori six possible choices for the second degree polynomial $f(x)-x$; but only the choice $f(x)-x=(x-{3+\sqrt{13}\over2})(x-{3-\sqrt{13}\over2})=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$.
\end{document}