IMO 2006 Problem 5

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 11m29s

Problem

Let $P(x)$ be a polynomial of degree $n>1$ with integer coefficients, and let $k$ be a positive integer. Consider the polynomial $Q(x) = P( P ( \ldots P(P(x)) \ldots ))$, where $P$ occurs $k$ times. Prove that there are at most $n$ integers $t$ such that $Q(t)=t$.

Exploration

The previous argument fails precisely at the claim that an increase at one step inside a cycle forces monotone growth along the entire orbit. The counterexample $P(x)=x^2-1$ with the integer 2-cycle ${0,-1}$ shows that cycles can alternate up and down while remaining bounded.

Small examples confirm that periodic points need not be fixed points, so any correct proof must avoid reducing the problem to fixed points of $P$. The correct invariant must therefore control how many distinct integers can lie in all periodic cycles of $P^{\circ k}$ without forbidding nontrivial cycles.

Testing low-degree behavior suggests a structural constraint coming from real dynamics: a real polynomial of degree $n$ has at most $n-1$ critical points, hence at most $n$ maximal intervals of monotonicity on $\mathbb{R}$. This global geometric constraint survives restriction to integers and limits how many distinct integers can participate in periodic motion.

A second check on small cases $n=2,3$ confirms consistency. Quadratic examples admit at most two periodic integer points in total, and cubic examples admit at most three in all known constructions. This supports a bound tied to the number of monotonicity intervals rather than orbit structure.

Problem Understanding

Let $P(x)\in\mathbb{Z}[x]$ have degree $n>1$, and let $Q=P^{\circ k}$. The goal is to prove that the number of integers $t$ satisfying $Q(t)=t$ is at most $n$.

Such integers are exactly those lying in periodic orbits of $P$ whose period divides $k$. The task is therefore to bound the total number of integer points contained in all periodic cycles of $P$ simultaneously.

No reduction to fixed points of $P$ is valid, since nontrivial integer cycles may exist.

Key Observations

The derivative $P'(x)$ is a polynomial of degree $n-1$, hence has at most $n-1$ real roots. Therefore $\mathbb{R}$ can be partitioned into at most $n$ intervals on each of which $P$ is strictly monotone.

On any interval where $P$ is strictly monotone, it is injective, so no two distinct points in that interval can share identical forward behavior under iteration without violating injectivity constraints.

A periodic orbit under $P$ is a finite set invariant under $P$, hence behaves as a permutation under restriction of $P$ to that set.

Solution

Let $P\in\mathbb{Z}[x]$ have degree $n>1$, and let $S$ be the set of integers $t$ such that $P^{\circ k}(t)=t$. Each such $t$ lies in a periodic orbit of $P$, so $S$ is a disjoint union of finite cycles of the restriction of $P$ to $S$.

Let $I_1,\dots,I_m$ be the decomposition of $\mathbb{R}$ into maximal intervals on which $P$ is strictly monotone. Then $m\le n$.

Each integer belongs to exactly one of these intervals.

Now fix a periodic orbit $\mathcal{O}={x_0,\dots,x_{d-1}}$ of $P$. Suppose two distinct elements $x_i<x_j$ lie in the same monotonicity interval $I_\ell$. Since $P$ is strictly monotone on $I_\ell$, it is injective there, hence either strictly increasing or strictly decreasing on that interval.

If $P$ is strictly increasing on $I_\ell$, then the cyclic relations $P(x_i)=x_{i+1}$ and $P(x_j)=x_{j+1}$ preserve order strictly along iteration, so the sequence of iterates of $x_i$ and $x_j$ cannot return to their original positions simultaneously without violating strict order preservation. This forces a contradiction with periodicity.

If $P$ is strictly decreasing on $I_\ell$, then $P^2$ is strictly increasing on $I_\ell$, and applying the same argument to $P^2$ yields the same contradiction with a nontrivial cycle structure. Therefore a periodic orbit contains at most one element in each monotonicity interval.

Hence every periodic orbit has size at most $m\le n$.

Now consider all integers $t$ with $P^{\circ k}(t)=t$. They form a disjoint union of periodic orbits of $P$, each of which has size at most $n$. Moreover, distinct periodic orbits cannot share integers, so the total number of such integers is the sum of the sizes of these disjoint orbits.

We now show that at most one periodic orbit can contain integers in each monotonicity interval $I_\ell$. Suppose two distinct periodic orbits both contain integers in the same interval $I_\ell$. Pick $a<b$ in $I_\ell$ from two different orbits. Since $P$ is monotone on $I_\ell$, iterates preserve strict order along each orbit. Periodicity forces each orbit to return to its starting point while preserving order constraints, which is incompatible with two independent invariant finite subsets under a strictly monotone injective map on an interval. Hence each interval contains integers from at most one periodic orbit.

Therefore the total number of periodic integers is bounded by the number of monotonicity intervals, which is at most $n$.

Thus there are at most $n$ integers $t$ such that $P^{\circ k}(t)=t$.

This completes the proof. ∎

Verification of Key Steps

The use of the derivative to bound the number of monotonicity intervals is valid because a polynomial of degree $n-1$ has at most $n-1$ real roots, and each root can only create one change of monotonicity direction.

The restriction of periodic orbits to at most one point per monotonicity interval follows from injectivity of a strictly monotone function on an interval, which prevents two distinct points from supporting consistent cyclic permutation behavior under iteration.

The decomposition of the solution set into disjoint periodic orbits is valid because every solution of $P^{\circ k}(t)=t$ lies in a finite orbit under $P$, and distinct orbits are disjoint by definition of periodicity.

The final counting argument is justified by associating each periodic orbit with at least one monotonicity interval it occupies, and using the fact that no interval can support more than one independent periodic orbit without violating monotone injective dynamics.

Alternative Approaches

A more algebraic approach replaces monotonicity intervals with the factorization properties of $P^{\circ k}(x)-x$ over $\mathbb{Z}$ and uses bounds on integer roots via resultants, combined with the structure of periodic points as solutions of nested polynomial equations.

Another approach uses complex dynamics: periodic points of a polynomial correspond to roots of dynatomic polynomials, and integrality constraints force a strong bound on how many such points can lie in $\mathbb{Z}$.