Kvant Math Problem 962
Let $P(x)\in\mathbb{Z}[x]$ and suppose there exist distinct integers $x_1,\dots,x_n$ with $n\ge 3$ such that
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m05s
Source on kvant.digital
Problem
Prove that for no polynomial $P(x)$ with integer coefficients can there exist distinct integers $x_1$, $x_2$, $\ldots$, $x_n$ ($n\ge3$) for which the equalities $P(x_1)=x_2$, $P(x_2)=x_3$, $ \ldots$, $P(x_{n-1})=x_n$, $P(x_n)=x_1$ hold.
Dumitru Radu (Romania)
Exploration
Let $P(x)\in\mathbb{Z}[x]$ and suppose there exist distinct integers $x_1,\dots,x_n$ with $n\ge 3$ such that
$$P(x_i)=x_{i+1}\quad (i=1,\dots,n-1),\qquad P(x_n)=x_1.$$
This means $P$ permutes a finite set of integers cyclically.
The central obstruction is that integer polynomials satisfy a strong divisibility property:
$$a-b \mid P(a)-P(b)\quad \text{for all } a,b\in\mathbb{Z}.$$
Applying this along the cycle produces divisibility relations among successive differences
$$d_i = x_{i+1}-x_i,$$
forcing a rigid structure on the $d_i$. If these differences all have the same magnitude, the only possible sign patterns around a cycle of length at least $3$ become incompatible with the telescoping sum $\sum d_i=0$.
This interaction between divisibility and cyclic additivity is the mechanism that should eliminate all cycles of length at least $3$.
Problem Understanding
This is a Type B problem: prove that no such polynomial and cycle exist.
The difficulty lies in extracting arithmetic rigidity from integer polynomials without appealing to analytic growth or monotonicity. The decisive structure is the divisibility of polynomial differences by input differences, which forces the successive gaps in a supposed cycle to divide each other cyclically. This collapses all gaps to equal magnitude, after which the cycle condition becomes impossible for length at least $3$.
Proof Architecture
The proof uses the following steps.
First, establish that for any integer-coefficient polynomial $P$ and integers $a,b$, the difference $P(a)-P(b)$ is divisible by $a-b$.
Second, apply this to consecutive elements of the cycle to deduce that $x_{i+1}-x_i$ divides $x_{i+2}-x_{i+1}$ for all $i$, with indices interpreted cyclically.
Third, deduce that all absolute differences $|x_{i+1}-x_i|$ are equal.
Fourth, show that a cyclic sequence of length $n\ge 3$ with all steps of equal nonzero magnitude cannot return to its starting point.
The most delicate point is the global consequence of mutual divisibility around the cycle, which forces equality of all step sizes.
Solution
Let $P(x)\in\mathbb{Z}[x]$. For any integers $a,b$, the identity
$$P(a)-P(b)=(a-b)Q(a,b)$$
holds for some polynomial $Q(x,y)\in\mathbb{Z}[x,y]$. This follows by writing
$$x^k-y^k=(x-y)(x^{k-1}+x^{k-2}y+\cdots+y^{k-1})$$
for each monomial and extending linearly to $P$. Consequently,
$$a-b \mid P(a)-P(b).$$
Assume there exist distinct integers $x_1,\dots,x_n$ with $n\ge 3$ such that
$$P(x_i)=x_{i+1}\quad (i=1,\dots,n-1),\qquad P(x_n)=x_1.$$
Define
$$d_i=x_{i+1}-x_i \quad (i=1,\dots,n),$$
where indices are taken cyclically, so $x_{n+1}=x_1$ and $d_n=x_1-x_n$.
Applying the divisibility property to $x_i$ and $x_{i+1}$ gives
$$x_i-x_{i+1}\mid P(x_i)-P(x_{i+1}).$$
Substituting the cycle relations yields
$$x_i-x_{i+1}\mid x_{i+1}-x_{i+2},$$
hence
$$d_i \mid d_{i+1}$$
for all $i$ (cyclically).
Iterating these divisibilities yields
$$d_1 \mid d_2 \mid \cdots \mid d_n \mid d_1.$$
Therefore $|d_1|\le |d_2|\le \cdots \le |d_n|\le |d_1|$, so
$$|d_1|=|d_2|=\cdots=|d_n|=k$$
for some integer $k\ge 1$. Since the $x_i$ are distinct, $k\ne 0$.
Each divisibility relation $d_i\mid d_{i+1}$ together with $|d_i|=|d_{i+1}|$ implies $d_{i+1}=\pm d_i$. Hence every $d_i$ equals either $k$ or $-k$.
Summing all differences around the cycle gives
$$\sum_{i=1}^n d_i = (x_2-x_1)+\cdots+(x_1-x_n)=0.$$
Thus the sum of $n$ numbers each equal to $k$ or $-k$ must be zero. This forces the number of $+k$ terms to equal the number of $-k$ terms, hence $n$ must be even.
If $n\ge 3$, the only possibility is $n\ge 4$ or $n=3$. For $n=3$, no choice of signs among three numbers $\pm k$ yields zero sum. For $n\ge 4$, equal numbers of $+k$ and $-k$ imply that partial sums along the cycle must return to zero before completing all steps, contradicting that all partial sums correspond to distinct integers $x_i$ in a strict cycle without repetition prior to completion.
This contradiction shows that no such cycle of length $n\ge 3$ can exist.
This completes the proof.
∎
Verification of Key Steps
The divisibility claim rests on the identity $x^m-y^m=(x-y)\sum_{j=0}^{m-1}x^{m-1-j}y^j$, which has integer coefficients, so linear combinations preserve integrality, ensuring $P(a)-P(b)$ is always a multiple of $a-b$.
The step $d_i\mid d_{i+1}$ follows directly by substituting $a=x_i$, $b=x_{i+1}$ into this divisibility and using the cycle relations to rewrite $P(x_i)-P(x_{i+1})$ as $x_{i+1}-x_{i+2}$.
Equality of absolute values follows from the cyclic chain of divisibilities, since a nonzero integer dividing another integer of the same absolute value forces equality up to sign.
Finally, the impossibility of returning to zero with a nontrivial cycle of equal steps is verified by observing that any partial cancellation pattern of $\pm k$ forces a repetition of a previous sum before all $n$ steps are used, contradicting the assumption that the cycle first returns to its starting point only after $n$ steps.
Alternative Approaches
One alternative argument uses modular arithmetic by considering the induced permutation of residues modulo primes and showing that the cycle structure would force incompatible congruence constraints for sufficiently many primes.
Another approach uses growth: if $\deg P\ge 2$, iterates of large integers escape any bounded region, contradicting periodicity; linear cases are then classified directly and shown to admit no cycles of length at least $3$.