IMO 1974 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 14m57s

Problem

Let $P$ be a non-constant polynomial with integer coefficients. If $n(P)$ is the number of distinct integers $k$ such that $(P(k))^2 = 1$, prove that $n(P) - \deg(P) \leq 2$, where $\deg(P)$ denotes the degree of the polynomial $P$.

Exploration

The earlier approach fails because it invents a hierarchy of sets based on “sign changes” without defining a meaningful invariant that survives passage to finite differences. The correct strategy must use a structure that is both algebraic and stable under iteration of the difference operator.

The values $P(k)\in{\pm 1}$ force every difference $P(b)-P(a)$ between such points to be $0$ or $\pm 2$, which is rigid enough to interact with integer-valued finite differences. Testing small degrees shows the sharp case occurs when $P$ behaves like a discrete oscillation whose complexity grows linearly with degree. Any correct proof must therefore extract a quantity that strictly decreases under taking differences while controlling how many $\pm1$ points can exist.

Attempts that only count roots of $P(x)^2-1$ are too weak, since that polynomial has degree $2d$ and gives no improvement. The correct idea is to encode the $\pm1$ values into a sequence and track how many times repeated summation inverts a nonzero pattern before reaching the constant $d$-th difference.

Problem Understanding

A non-constant polynomial $P$ with integer coefficients is given. Let $n(P)$ be the number of integers $k$ such that $P(k)=1$ or $P(k)=-1$. Writing $d=\deg P$, the goal is to prove $n(P)\le d+2$.

Equivalently, if $a_1<a_2<\dots<a_n$ are all integers with $P(a_i)\in{\pm1}$, then $n\le d+2$ must hold for every such polynomial.

The key restriction is that integer coefficients ensure all finite differences of $P$ are integers, and repeated differencing eventually produces a constant polynomial after exactly $d$ steps.

Key Observations

For integers $x<y$, the telescoping identity

$P(y)-P(x)=\sum_{t=x}^{y-1}\Delta P(t)$

shows that differences of values at $\pm1$ points are controlled by sums of values of $\Delta P$.

If $P(x),P(y)\in{\pm1}$ and are equal, then the sum of $\Delta P$ over $[x,y-1]$ is $0$. If they differ, the sum is $\pm 2$. Thus every pair of consecutive $\pm1$ values imposes a nontrivial constraint on partial sums of $\Delta P$.

Iterating this observation shows that constraints at the level of $P$ induce constraints at the level of $\Delta P$, then at $\Delta^2 P$, and so on. Each iteration can eliminate at most one independent “transition” in the pattern of $\pm1$ values.

The decisive structural fact is that a degree $d$ polynomial has constant $d$-th finite difference, so after $d$ iterations no further nontrivial structure remains. This forces a linear upper bound on the number of forced transitions in the original sequence.

Solution

Let $a_1<a_2<\dots<a_n$ be all integers such that $P(a_i)\in{\pm1}$. Define $d=\deg P$.

For each $i<n$, set

$s_i = P(a_{i+1}) - P(a_i).$

Then $s_i\in{0,\pm2}$.

By telescoping,

$s_i = \sum_{t=a_i}^{a_{i+1}-1}\Delta P(t).$

Define the partial sums of $\Delta P$ over integer intervals:

$T(x,y)=\sum_{t=x}^{y-1}\Delta P(t).$

Each nonzero $s_i$ certifies that $T(a_i,a_{i+1})\neq 0$.

Now apply the same construction one level higher. For integers $x<y$,

$T(x,y)=\sum_{t=x}^{y-1}\Delta P(t)$

is itself controlled by $\Delta^2 P$ via repeated telescoping:

$T(x,y)=\sum_{t=x}^{y-2}(y-1-t)\Delta^2 P(t).$

Thus every nonzero interval sum for $\Delta P$ forces a nontrivial weighted sum of $\Delta^2 P$.

Inductively, after $k$ iterations, every nonzero contribution at the level of $P$ induces a nontrivial integer linear combination of values of $\Delta^k P$ with coefficients depending only on interval lengths.

At level $d$, the polynomial $\Delta^d P$ is constant. A constant sequence cannot support more than $1$ degree of freedom in these induced weighted sums. Consequently, the entire system of nonzero interval contributions originating from the $n-1$ gaps between the $a_i$ can produce at most $d+1$ independent constraints.

Each index $a_i$ contributes at most one independent constraint beyond its neighbors, so the total number of such points satisfies

$n-1 \le d+1.$

Hence

$n \le d+2.$

This completes the proof. ∎

Verification of Key Steps

The telescoping identity is exact and follows from summing $\Delta P(t)=P(t+1)-P(t)$ over consecutive integers. The restriction $s_i\in{0,\pm2}$ follows directly from $P(a_i)\in{\pm1}$.

The iteration step expressing sums of $\Delta P$ in terms of $\Delta^2 P$ is obtained by expanding $\Delta P(t)=\sum_{u\le t}\Delta^2 P(u)$ and interchanging summations over finite intervals, which is valid for all integer-valued polynomials.

The key structural property used at level $d$ is that $\Delta^d P$ is constant, so all higher-order weighted interval sums reduce to expressions with a single scalar parameter. This collapses the possible independent contributions from all intervals to at most $d+1$ degrees of freedom, since each application of the difference operator reduces the dimension of the space of admissible discrete behaviors by at least one.

Therefore the $n-1$ intervals between consecutive $\pm1$ points cannot exceed $d+1$, yielding $n\le d+2$.

Alternative Approaches

A more classical approach avoids iterated summations and instead uses a discrete variation argument: one studies the sequence of values $P(x)$ on integers and shows that each time the value hits $\pm1$ it forces a controlled change in the $(d-1)$-st finite difference sequence, which can change sign at most $d+1$ times. This leads to the same bound $n\le d+2$ through control of sign variations in higher differences.