Theory of Iterative Functional Equations

How to take the square root of a function under composition — when it works, when it doesn't, and the geometry behind both.

1. Function Iteration & Half-Iterates

Function iteration is the process of applying a function repeatedly to its own output. The \(n\)-th iterate of \(f\), written \(f^{\circ n}\), is defined recursively by \[ f^{\circ 0}(x) = x, \qquad f^{\circ (n+1)}(x) = f\bigl(f^{\circ n}(x)\bigr). \] The sequence \(x,\, f(x),\, f^{\circ 2}(x),\, f^{\circ 3}(x),\dots\) is the orbit of \(x\). Integer iteration obeys the semigroup law \[ f^{\circ (m+n)} = f^{\circ m} \circ f^{\circ n}, \] so the iterates behave like a discrete-time flow indexed by \(n \in \mathbb{N}\).

An iterative functional equation turns this around: given a target \(F\), find an \(f\) such that some iterate of \(f\) equals \(F\). The question that drives this site is the simplest non-trivial one — can we interpolate the index \(n\) to a non-integer value? Taking \(n = \tfrac12\) gives the functional square root, or half-iterate: \[ f^{\circ 2}(x) = f(f(x)) = F(x). \] We are literally asking for “half a step” of \(F\): a map you apply twice to reproduce one application of \(F\).

Definition (Functional square root). A function \(f: D \to D\) is a functional square root (or half-iterate) of \(F: D \to D\) if \(f(f(x)) = F(x)\) for every \(x \in D\).

The whole idea. One full step of \(F\) (blue) is made of two equal half-iterate steps of \(f\) (purple): \(f(f(x)) = F(x)\).

Two warnings set the tone for everything below.

Existence is not automatic. A perfectly nice \(F\) may have no half-iterate of a given regularity (continuous, smooth, analytic) on a given domain. Much of this page is about why.
Uniqueness usually fails. When half-iterates exist they typically come in families — different branches, or compositions with symmetries of \(F\). “The” half-iterate is a convenient fiction; we look for natural ones (continuous, analytic, or canonical near a fixed point).

Two warm-up examples.

Translation. \(F(x) = x + 1\) has the obvious half-iterate \(f(x) = x + \tfrac12\), since \((x+\tfrac12)+\tfrac12 = x+1\).
Scaling. \(F(x) = a\,x\) with \(a > 0\) has \(f(x) = \sqrt{a}\,x\), because \(\sqrt{a}\,(\sqrt{a}\,x) = a x\). If \(a < 0\) there is no real linear half-iterate — the first hint that signs matter.

2. Fixed Points, Multipliers & Classification

A fixed point of \(F\) is a value \(x^*\) with \(F(x^*) = x^*\). Fixed points are the skeleton of a dynamical system: they are where the orbit stands still, and the local behaviour around them organises everything nearby.

Definition (Multiplier). If \(F\) is differentiable at a fixed point \(x^*\), its multiplier is the derivative \[ \lambda = F'(x^*). \] To first order, \(F(x^* + \varepsilon) \approx x^* + \lambda\,\varepsilon\): near \(x^*\) the map looks like multiplication by \(\lambda\).

The size of \(\lambda\) sorts fixed points into a few universal types. The cobweb diagram below shows the attracting case for \(F(x)=\cos x\): orbits spiral inward to the fixed point because \(|\lambda| < 1\).

Cobweb dynamics. Bounce vertically to the curve, horizontally to \(y=x\), repeat. For \(F=\cos\), \(|F'(x^*)| < 1\), so every orbit is pulled into the fixed point \(x^*\).

Multiplier \(\lambda = F'(x^*)\)	Type	Local behaviour
\(\lambda = 0\)	superattracting	quadratically fast attraction
\(0 < \|\lambda\| < 1\)	attracting	geometric attraction, ratio \(\|\lambda\|\)
\(\|\lambda\| > 1\)	repelling	geometric repulsion
\(\|\lambda\| = 1\)	neutral / parabolic	delicate; algebraically slow or rotational

Why does a page about half-iterates care so much about fixed points? Because a half-iterate inherits them, and — crucially — it inherits a constraint on its derivative.

Proposition (Inherited fixed points). Let \(f\) be a half-iterate of \(F\).

Every fixed point of \(f\) is a fixed point of \(F\): \(f(x^*)=x^* \Rightarrow F(x^*) = f(f(x^*)) = x^*\).
Every \(2\)-cycle of \(f\) is a pair of fixed points of \(F\): if \(f(a)=b\) and \(f(b)=a\), then \(F(a)=a\) and \(F(b)=b\).

Lemma (Multiplier square root). Suppose \(f\) is differentiable and fixes \(x^*\). Differentiating \(f(f(x)) = F(x)\) at \(x^*\) with the chain rule, \[ F'(x^*) = \bigl(f\circ f\bigr)'(x^*) = f'\!\bigl(f(x^*)\bigr)\,f'(x^*) = \bigl(f'(x^*)\bigr)^2 . \] Hence \(f'(x^*) = \pm\sqrt{F'(x^*)}\). In particular, a real differentiable half-iterate that fixes \(x^*\) can exist only if \(F'(x^*) \ge 0\).

This single lemma is the workhorse of the whole subject. The multiplier of \(f\) is a square root of the multiplier of \(F\). A negative multiplier \(F'(x^*) < 0\) has no real square root, so no real (differentiable) half-iterate can be anchored at that point — even when \(F\) is otherwise perfectly tame.

Compare the two functions this site keeps returning to:

\(F(x) = x^2 - 2\)

Meets \(y=x\) at \(x=-1\) and \(x=2\): two real fixed points.

\(F(x) = x^2 + 1\)

Never meets \(y=x\): no real fixed point at all.

For \(F(x)=x^2-2\) we have \(F'(x) = 2x\), so the multipliers are \(F'(2)=4\) (repelling, \(\lambda > 0\) — a real half-iterate can be anchored here) and \(F'(-1)=-2\) (repelling, but \(\lambda < 0\)). The right-hand function has no real fixed points to anchor anything. Sections 3–5 turn these observations into constructions and obstructions.

3. Local Linearization: Schröder & Koenigs

Near a fixed point, the multiplier says \(F\) looks like multiplication by \(\lambda\). The remarkable fact is that — away from the neutral case — \(F\) is not merely approximately linear but genuinely conjugate to the linear map, in a coordinate of its own choosing. This is the content of Schröder's equation and Koenigs' theorem.

Definition (Schröder's equation). A Schröder function for \(F\) at a fixed point \(x^*\) with multiplier \(\lambda\) is a map \(\sigma\), normalised by \(\sigma(x^*) = 0\) and \(\sigma'(x^*) = 1\), satisfying \[ \sigma\bigl(F(x)\bigr) = \lambda\,\sigma(x). \] In the coordinate \(u = \sigma(x)\), the map \(F\) becomes simply \(u \mapsto \lambda u\).

Theorem (Koenigs, 1884). If \(F\) is analytic near \(x^*\) and the multiplier satisfies \(\lambda \neq 0\) and \(|\lambda| \neq 1\) (the hyperbolic case), then a Schröder function \(\sigma\) exists, is analytic near \(x^*\), and is unique under the normalisation \(\sigma'(x^*)=1\). Equivalently, \[ F = \sigma^{-1} \circ (\lambda\,\cdot) \circ \sigma , \] so \(F\) is analytically conjugate to multiplication by its multiplier.

Once \(F\) is linear in the right coordinate, taking a half-iterate is trivial: halving an exponent is dividing the index by two. Multiplication by \(\lambda\) iterated is multiplication by powers of \(\lambda\); its “square root” is multiplication by \(\sqrt{\lambda}\).

Conjugacy makes iteration linear. Going around the square — coordinate \(\sigma\), multiply by \(\lambda\), coordinate back — reproduces \(F\). Replacing \(\lambda\) by \(\sqrt{\lambda}\) gives the half-iterate.

Construction (Schröder half-iterate). In the hyperbolic case, pick a square root \(\mu = \sqrt{\lambda}\) and define \[ f = \sigma^{-1} \circ (\mu\,\cdot) \circ \sigma . \] Then \[ f\circ f = \sigma^{-1}\circ(\mu^2\,\cdot)\circ\sigma = \sigma^{-1}\circ(\lambda\,\cdot)\circ\sigma = F . \] So \(f\) is a half-iterate, analytic near \(x^*\), with multiplier \(f'(x^*) = \mu = \sqrt\lambda\) — exactly as the Lemma of §2 demands.

Reality check. The square root \(\mu = \sqrt\lambda\) is real precisely when \(\lambda > 0\). For \(\lambda < 0\) the construction still works over \(\mathbb{C}\) but produces a complex \(f\). This is the local, quantitative version of “signs matter.”

This is not just theory: it is the algorithm behind the Solver's local-analytic mode (solveSchroederHalfIterate). It expands \(\sigma\) as a power series, solves Schröder's equation coefficient by coefficient using composita recurrences, multiplies by \(\sqrt\lambda\), and inverts the series — all in exact rational arithmetic so the coefficients never drift.

How the Schröder series is built (sketch)

Shift so that \(x^* = 0\) and write \(F(x) = \lambda x + a_2 x^2 + a_3 x^3 + \cdots\). Seek \(\sigma(x) = x + s_2 x^2 + s_3 x^3 + \cdots\). Substituting into \(\sigma(F(x)) = \lambda\,\sigma(x)\) and matching the coefficient of \(x^n\) gives \[ (\lambda^n - \lambda)\,s_n = (\text{polynomial in } a_2,\dots,a_n,\ s_2,\dots,s_{n-1}). \] Because \(|\lambda| \neq 0,1\), the factor \(\lambda^n - \lambda\) never vanishes for \(n \ge 2\), so each \(s_n\) is determined uniquely and recursively. The resonances \(\lambda^n = \lambda\) that would block this are exactly the roots-of-unity multipliers of the neutral case — which is why Koenigs needs \(|\lambda| \neq 1\).

The neutral case \(|\lambda| = 1\) genuinely breaks the method: Schröder's equation has no analytic solution when \(\lambda = 1\). It is replaced by Abel's equation \(\alpha(F(x)) = \alpha(x) + 1\), whose half-iterate is \(f = \alpha^{-1}(\alpha + \tfrac12)\). We return to this in §6.

4. A Solvable Case: \(f(f(x)) = x^2 - 2\)

The equation \(f(f(x)) = x^2 - 2\) is the textbook success story. The trick is to recognise a global conjugacy that linearises \(F\) not just near one fixed point but on a whole interval. Two equivalent changes of variable do the job.

The Joukowski / Chebyshev conjugacy. Substitute \(x = z + \tfrac1z\). Then \[ F(x) = x^2 - 2 = \Bigl(z + \tfrac1z\Bigr)^2 - 2 = z^2 + \tfrac{1}{z^2}. \] In other words, in the \(z\)-coordinate \(F\) is just the squaring map \(z \mapsto z^2\). Equivalently, writing \(x = 2\cos\theta\), \[ F(2\cos\theta) = 4\cos^2\theta - 2 = 2\cos(2\theta), \] so \(F\) doubles the angle \(\theta\). This is exactly the Chebyshev relation \(T_2(\cos\theta)=\cos 2\theta\) with \(T_2(x) = 2x^2-1\).

Now the half-iterate is immediate. To halve the index of “double the angle,” we need \(g\) with \(g(g(\theta)) = 2\theta\); the scaling \(g(\theta) = \sqrt2\,\theta\) works since \((\sqrt2)^2 = 2\). Translating back through \(x = 2\cos\theta\): \[ \boxed{\,f(x) = 2\cos\!\bigl(\sqrt2\,\arccos(x/2)\bigr)\,}\qquad (|x|\le 2). \] Equivalently, in the \(z\)-coordinate, \(f\) is the (real) power map \(z \mapsto z^{\sqrt2}\).

The half-iterate sits between \(y=x\) and \(F\). Starting from \(x_0\), two steps of \(f\) (green cobweb) land exactly on \(F(x_0)=x_0^2-2\). The curves all meet at the fixed point \((2,2)\).

Verification

With \(\phi(\theta) = 2\cos\theta\) (so \(\phi^{-1}(x) = \arccos(x/2)\)) and \(f = \phi \circ (\sqrt2\,\cdot) \circ \phi^{-1}\), \[ f(f(x)) = \phi\Bigl(\sqrt2 \cdot \sqrt2\,\phi^{-1}(x)\Bigr) = \phi\bigl(2\,\phi^{-1}(x)\bigr) = 2\cos\!\bigl(2\arccos(x/2)\bigr) = x^2 - 2. \] The whole computation is just “\(\sqrt2 \cdot \sqrt2 = 2\)” dressed up in a coordinate where \(F\) is linear-in-the-angle.

A subtlety worth noticing. The Lemma of §2 forbids a real half-iterate anchored at \(x^*=-1\), where \(F'(-1) = -2 < 0\). There is no contradiction: the Chebyshev \(f\) above is continuous on \([-2,2]\) but it does not fix \(-1\); instead \(-1\) sits on a \(2\)-cycle structure of the angle-doubling. The global conjugacy sidesteps the local obstruction — a recurring theme: the right coordinate can rescue a problem that looks hopeless one fixed point at a time.

5. The Hard Case: \(f(f(x)) = x^2 + 1\)

Change the constant from \(-2\) to \(+1\) and the friendly structure evaporates. The equation \[ f(f(x)) = x^2 + 1 \] has no known closed-form real solution, and the reason is visible in one line.

Proposition (No real fixed point). For all real \(x\), \[ F(x) - x = x^2 - x + 1 = \Bigl(x - \tfrac12\Bigr)^2 + \tfrac34 \ge \tfrac34 > 0, \] so \(F(x) > x\) everywhere and \(x^2 + 1 = x\) has discriminant \(1 - 4 = -3 < 0\). Thus \(F\) has no real fixed point and no real \(2\)-cycle.

With no real fixed point, every tool from §3 and §4 is unavailable over \(\mathbb{R}\): there is nowhere to anchor a Schröder coordinate, and no real conjugacy to a power map. Orbits simply escape: \(x \mapsto x^2+1 \mapsto \cdots \to +\infty\).

Escape to infinity. The graph of \(x^2+1\) stays a clear gap above \(y=x\) (at least \(\tfrac34\)), so the cobweb ratchets upward without ever settling. No fixed point means no place to linearise.

Be careful what you conclude. “\(F(x) > x\) everywhere” does not by itself forbid a half-iterate — recall \(F(x)=x+1\), which also has no fixed point yet has the half-iterate \(x+\tfrac12\). The obstruction for \(x^2+1\) is the combination of (i) no real fixed point to anchor a Schröder coordinate, and (ii) non-monotone, super-linear growth, which also defeats the monotone Abel-function approach that rescues \(x+1\). It is this conjunction — not the inequality alone — that makes the real problem hard.

So is there any half-iterate?

Yes — just not a real, closed-form one. Over \(\mathbb{C}\), \(x^2+1\) has fixed points at \(x^* = \tfrac{1 \pm i\sqrt3}{2}\) with complex multipliers \(\lambda = 2x^*\), \(|\lambda| = 2 \neq 1\). These are hyperbolic, so Koenigs' theorem applies and a local analytic half-iterate exists in the complex plane. One can also build a formal power series half-iterate around such a point. The Solver does exactly this: its composita / series mode returns the Taylor coefficients of an \(f\) with \(f(f(x)) = x^2+1\) to any requested order, even though no elementary formula sums the series. “No closed form” is a statement about expressibility, not about existence.

6. Conjugacy & the General Picture

Every success above was a conjugacy in disguise: relabel coordinates so that \(F\) becomes a map we can iterate by inspection.

Definition (Conjugacy). Functions \(F\) and \(G\) are conjugate if there is an invertible \(h\) with \[ F = h^{-1} \circ G \circ h . \] Then \(F^{\circ n} = h^{-1} \circ G^{\circ n} \circ h\) for every \(n\): conjugacy commutes with iteration.

Theorem (Multipliers are conjugacy invariants). If \(F = h^{-1}\circ G\circ h\) and \(x^*\) is a fixed point of \(F\), then \(y^* = h(x^*)\) is a fixed point of \(G\) and \[ F'(x^*) = G'(y^*). \] Proof. Differentiate \(h\circ F = G\circ h\) at \(x^*\): \(h'(x^*)F'(x^*) = G'(y^*)h'(x^*)\); since \(h'(x^*)\neq 0\), cancel it. \(\square\)

This invariance is why \(x^2-2\) and \(x^2+1\) are genuinely different and not just superficially so: any conjugacy must preserve the multiplier data, and one function has real fixed points with a nonnegative multiplier while the other has no real fixed points at all. The general recipe is then:

Locate a fixed point \(x^*\) and compute its multiplier \(\lambda = F'(x^*)\).
Choose the linearising coordinate matched to \(\lambda\) (table below).
Halve the index in that coordinate, then conjugate back.

Fixed-point type	Normal form	Linearising equation	Half-iterate
hyperbolic \((\lambda \neq 0,\ \|\lambda\|\neq 1)\)	\(u \mapsto \lambda u\)	Schröder: \(\sigma(F)=\lambda\sigma\)	\(\sigma^{-1}\!\bigl(\sqrt\lambda\,\sigma\bigr)\)
superattracting \((\lambda = 0)\)	\(u \mapsto u^{d}\)	Böttcher: \(\beta(F)=\beta^{\,d}\)	\(\beta^{-1}\!\bigl(\beta^{\sqrt d}\bigr)\)
parabolic \((\lambda = 1)\)	\(u \mapsto u + 1\)	Abel: \(\alpha(F)=\alpha+1\)	\(\alpha^{-1}\!\bigl(\alpha + \tfrac12\bigr)\)

The Chebyshev solution of §4 is simultaneously a Schröder picture (at the hyperbolic fixed point \(x^*=2\), where \(\lambda = 4\) and \(\sqrt\lambda = 2\)) and a Böttcher picture (the global conjugacy to \(z \mapsto z^2\), with half-iterate \(z \mapsto z^{\sqrt2}\)). The irrational multiplier case \(|\lambda|=1\) with \(\lambda\) not a root of unity (Siegel / Cremer) brings in small-divisor problems and is where the deepest difficulties of the subject live.

7. Summary & Where to Go Next

The decision procedure for “does \(f(f(x))=F(x)\) have a nice solution?” distils to:

Find the real fixed points of \(F\) and their multipliers \(\lambda = F'(x^*)\).
If some \(x^*\) is hyperbolic with \(\lambda > 0\): build the Schröder half-iterate \(\sigma^{-1}(\sqrt\lambda\,\sigma)\) (§3).
If a global conjugacy to a power map or angle-doubling exists, you may get a closed form on a whole interval (§4).
If there is no usable real fixed point (e.g. \(x^2+1\)): there is generally no real closed form — fall back to a formal power series via the composita method, valid as a local/complex object (§5).

Continue exploring:

Solver — compute half-iterates two ways: paper-based composita series and local-analytic Schröder coordinates.
Composita Calculator — the Kruchinin recurrence \(F^{\Delta}(n,k)\) that powers the series machinery.
Notes — worked articles on fixed points, composita half-iterates, and numerical methods.
Bibliography — Koenigs (1884), Kneser (1950), Kuczma (1968), Kruchinin & Kruchinin (2013/2014), and more.