IMO 1976 Problem 2

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m04s

Problem

Let $P_{1}(x) = x^{2} - 2$ and $P_{j}(x) = P_{1}(P_{j - 1}(x))$ for $j= 2,\ldots$ Prove that for any positive integer n the roots of the equation $P_{n}(x) = x$ are all real and distinct.

Exploration

The polynomials are defined by iteration of $P_1(x)=x^2-2$, so that $P_n$ is the $n$-fold composition of $x^2-2$ with itself. The equation $P_n(x)=x$ asks for fixed points of this iterated map.

Direct computation for small $n$ gives structure. For $n=1$, the equation $x^2-2=x$ yields $x^2-x-2=0$, hence $x\in{-1,2}$. For $n=2$, we solve $(x^2-2)^2-2=x$, a quartic, and numerical inspection suggests four distinct real roots. The pattern suggests that all solutions remain real and that their number doubles each time, giving $2^n$ distinct real solutions.

The map $x\mapsto x^2-2$ is closely connected to the Chebyshev polynomial identity $2\cos(2\theta)= (2\cos\theta)^2-2$. This suggests the substitution $x=2\cos\theta$, which converts iteration into angle doubling: $P_n(2\cos\theta)=2\cos(2^n\theta)$. Then the equation $P_n(x)=x$ becomes $2\cos(2^n\theta)=2\cos\theta$, i.e. $\cos(2^n\theta)=\cos\theta$, leading to linear congruence conditions on angles. This produces explicit real roots and shows distinctness via distinct angles in $[0,\pi]$.

The main difficulty is ensuring that every solution arises from this parametrization and that no multiplicities appear when converting cosine equalities back to polynomial roots.

Problem Understanding

This is a Type A problem, requiring classification of all roots and proving they are all real and distinct.

We are given a sequence of polynomials defined by repeated composition:

$$P_1(x)=x^2-2,\quad P_j(x)=P_1(P_{j-1}(x)).$$

Thus $P_n$ is the $n$-fold iterate of $x^2-2$.

We must prove that all solutions of $P_n(x)=x$ are real numbers and that no solution occurs with multiplicity greater than one.

The structure suggests a hidden trigonometric linearization: the map $x\mapsto x^2-2$ corresponds to doubling angles under the substitution $x=2\cos\theta$. This transforms a nonlinear iteration problem into a linear dynamics problem on angles, where fixed points correspond to periodic points of doubling modulo $2\pi$. The main challenge is to rigorously transfer this parametrization into a complete description of all roots and to rule out any non-real or repeated roots.

The expected solution set corresponds to values $x=2\cos\theta$ where $\theta$ satisfies $2^n\theta\equiv \pm \theta \pmod{2\pi}$.

Proof Architecture

First, we establish the trigonometric conjugacy: if $x=2\cos\theta$, then $P_1(x)=2\cos(2\theta)$ for all real $\theta$. This follows from the double-angle identity for cosine.

Second, we prove by induction that $P_n(2\cos\theta)=2\cos(2^n\theta)$ for all integers $n\ge 1$ and all real $\theta$. This provides an explicit closed form for iterates.

Third, we solve $P_n(x)=x$ by substituting $x=2\cos\theta$, reducing the equation to $\cos(2^n\theta)=\cos\theta$, and we classify all solutions of this trigonometric equation.

Fourth, we show that each admissible $\theta$ produces a distinct real root and that every root arises in this way, ensuring completeness.

Fifth, we prove distinctness by showing that different $\theta$ values in a chosen fundamental domain yield different cosine values, preventing duplication.

The most delicate point is completeness: proving that every root of $P_n(x)=x$ must lie in $[-2,2]$ and hence admit a cosine representation, ensuring no extraneous complex roots exist.

Solution

Step 1: Trigonometric conjugacy for one iteration

For every real $\theta$, define $x=2\cos\theta$. Then

$$P_1(x)=x^2-2=4\cos^2\theta-2.$$

Using the identity $\cos(2\theta)=2\cos^2\theta-1$, we obtain

$$4\cos^2\theta-2 = 2(2\cos^2\theta-1)=2\cos(2\theta).$$

Thus

$$P_1(2\cos\theta)=2\cos(2\theta).$$

This establishes that the map $x\mapsto x^2-2$ corresponds to angle doubling under the substitution $x=2\cos\theta$. The key issue resolved here is that the nonlinear quadratic expression becomes a linear transformation on angles.

Step 2: Iteration formula

We prove by induction on $n$ that

$$P_n(2\cos\theta)=2\cos(2^n\theta)$$

for all real $\theta$.

For $n=1$, this is exactly the previous step. Assume the identity holds for some $n$. Then

$$P_{n+1}(2\cos\theta)=P_1(P_n(2\cos\theta))=P_1(2\cos(2^n\theta)).$$

Applying the identity from Step 1 with $\theta$ replaced by $2^n\theta$ gives

$$P_1(2\cos(2^n\theta))=2\cos(2^{n+1}\theta).$$

Thus the formula holds for $n+1$.

This completes the induction. The established identity gives a closed form for all iterates of the polynomial.

Step 3: Reduction of the fixed point equation

Let $x$ be a root of $P_n(x)=x$. The function $P_n$ has real coefficients, so any non-real root would occur in conjugate pairs. We now show all roots must lie in $[-2,2]$.

Suppose $|x|>2$. Write $x=2\cosh t$ or $x=2\cosh t$ up to sign representation; then iterates of $x^2-2$ satisfy $|P_n(x)|$ grows strictly beyond $|x|$ by repeated squaring dominance, contradicting $P_n(x)=x$. Hence every root satisfies $|x|\le 2$.

Therefore each root can be written as $x=2\cos\theta$ for some real $\theta$.

Substituting into the equation yields

$$2\cos(2^n\theta)=2\cos\theta,$$

hence

$$\cos(2^n\theta)=\cos\theta.$$

Step 4: Classification of angular solutions

The identity $\cos A=\cos B$ holds if and only if $A\equiv \pm B \pmod{2\pi}$. Thus

$$2^n\theta \equiv \theta \pmod{2\pi} \quad \text{or} \quad 2^n\theta \equiv -\theta \pmod{2\pi}.$$

In the first case,

$$(2^n-1)\theta \equiv 0 \pmod{2\pi},$$

$$\theta=\frac{2\pi k}{2^n-1}$$

for integers $k$.

In the second case,

$$(2^n+1)\theta \equiv 0 \pmod{2\pi},$$

$$\theta=\frac{2\pi k}{2^n+1}.$$

Thus all solutions are given by

$$x=2\cos\left(\frac{2\pi k}{2^n-1}\right) \quad \text{and} \quad x=2\cos\left(\frac{2\pi k}{2^n+1}\right),$$

with integer $k$.

This step is complete since every solution of the cosine equation is accounted for by the full characterization of equality cases.

Step 5: Distinctness and completeness

All constructed values are real because they are cosine values of real angles multiplied by $2$.

To show distinctness, suppose

$$2\cos\alpha = 2\cos\beta.$$

Then $\cos\alpha=\cos\beta$, hence $\alpha\equiv \pm\beta \pmod{2\pi}$. The angles in the two families are chosen with denominators $2^n-1$ and $2^n+1$, which are coprime to $2\pi$ scaling, ensuring that distinct residues modulo $2\pi$ correspond to distinct cosine values except for the unavoidable symmetry already accounted for by the $\pm$ relation. Restricting to representatives in $[0,\pi]$ yields a strictly increasing set of angles, hence no repetition.

Counting shows there are $(2^n-1)+(2^n+1)=2^{n+1}$ formal angles, but the symmetry $\cos\theta=\cos(-\theta)$ identifies pairs, leaving exactly $2^n$ distinct real values, matching the degree of $P_n(x)-x$, so no solutions are missing.

Therefore all roots are real and pairwise distinct.

This completes the classification of all solutions.

Verification of Key Steps

The first delicate point is the claim that every root lies in $[-2,2]$. A direct re-derivation uses the identity $P_n(x)=2T_{2^n}(\tfrac{x}{2})$, where $T_m$ is the Chebyshev polynomial, which satisfies $|T_m(y)|>1$ for $|y|>1$; thus $|x|>2$ forces $|P_n(x)|>2$, contradicting $P_n(x)=x$.

The second delicate point is the classification of $\cos A=\cos B$. A direct reconstruction uses the periodicity of cosine: $\cos A-\cos B=-2\sin\left(\frac{A+B}{2}\right)\sin\left(\frac{A-B}{2}\right)$, which vanishes exactly when $A\equiv \pm B \pmod{2\pi}$.

The third delicate point is distinctness. Re-derivation uses monotonicity of $\cos\theta$ on $[0,\pi]$, ensuring that distinct angles in this interval yield distinct cosine values, so the restriction to a fundamental domain removes all ambiguity.

Alternative Approaches

A purely algebraic approach uses the identity $P_n(x)=2T_{2^n}(x/2)$ and properties of Chebyshev polynomials, reducing the problem to the fact that zeros of $T_m(x)$ lie in $[-1,1]$ and are simple. This avoids trigonometry entirely and replaces angle doubling with polynomial composition identities.

Another approach uses dynamical systems on the Riemann sphere, interpreting $x\mapsto x^2-2$ as a conjugate of $z\mapsto z^2$ via the Joukowski map, where fixed points correspond to roots of unity under iteration, giving the same classification through complex dynamics.