IMO 1974 Problem 6
The problem concerns the integers $k$ for which $P(k)=\pm1$.
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 7m06s
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 problem concerns the integers $k$ for which $P(k)=\pm1$. Since $P$ has integer coefficients, the differences $P(x)-1$ and $P(x)+1$ are integer polynomials. If many integers satisfy $P(k)=1$, then $P(x)-1$ has many integer roots; similarly for $P(x)+1$.
The first natural attempt is to separate the integers into two sets:
$$A={k\in\mathbb Z:P(k)=1}, \qquad B={k\in\mathbb Z:P(k)=-1}.$$
If $|A|=r$ and $|B|=s$, then $r+s=n(P)$. Since $P(x)-1$ has degree $\deg P$, one immediately gets $r\le \deg P$, and similarly $s\le \deg P$. This yields only
$$n(P)\le 2\deg P,$$
which is much weaker than required.
The next step is to exploit the interaction between the two sets. Suppose
$$a_1,\dots,a_r\in A,\qquad b_1,\dots,b_s\in B.$$
Then
$$P(x)-1=\prod_{i=1}^r(x-a_i)Q(x),$$
with $Q(x)\in\mathbb Z[x]$. Evaluating at $x=b_j$ gives
$$-2=P(b_j)-1=\prod_{i=1}^r(b_j-a_i)Q(b_j).$$
Every factor is an integer, so the product equals $-2$. This is extremely restrictive. If $r\ge3$, then the product of the differences alone usually has magnitude at least $2$, leaving almost no room for $Q(b_j)$.
Trying examples clarifies the structure. For degree $1$, the polynomial
$$P(x)=2x-1$$
satisfies $P(0)=-1$ and $P(1)=1$, so $n(P)=2$ and $n(P)-\deg P=1$.
For degree $2$, the polynomial
$$P(x)=x(x-1)-1$$
satisfies
$$P(0)=P(1)=-1,\qquad P(2)=1,$$
so $n(P)=3$ and $n(P)-\deg P=1$.
Trying to force equality $n(P)-\deg P=2$ suggests looking for four integer inputs for a quadratic. The polynomial
$$P(x)=2x(x-1)-1$$
gives
$$P(0)=P(1)=-1,\qquad P(-1)=P(2)=1.$$
Hence $n(P)=4$ and $\deg P=2$, so equality is attained.
This example reveals the key phenomenon. If $P(a)=1$ and $P(b)=-1$, then
$$P(a)-P(b)=2.$$
Since
$$P(a)-P(b)$$
is divisible by $a-b$, the integer $a-b$ must divide $2$. Thus
$$|a-b|\in{1,2}.$$
This severely constrains the arrangement of the roots. The problem becomes combinatorial.
Suppose there are $r$ integers with value $1$ and $s$ integers with value $-1$. Every difference between a $1$-point and a $-1$-point has absolute value at most $2$. Hence all such integers lie in a very short interval. It becomes plausible that there can be at most four such integers altogether.
A more algebraic route looks cleaner. Let
$$P(x)-1=A(x),\qquad P(x)+1=B(x).$$
Then
$$B(x)-A(x)=2.$$
If $A$ has $r$ integer roots and $B$ has $s$ integer roots, evaluating at roots of one polynomial forces products of integer differences to divide $2$. This should imply that one of $r,s$ is at most $2$. Then
$$r+s\le \deg P+2.$$
The most delicate step is proving rigorously that if one polynomial has at least three integer roots, then the other has at most two. A careless argument could overlook the possibility that the auxiliary factor $Q(b_j)$ equals $0$ or has large cancellation. Since $Q(b_j)$ is an integer and the total product equals $\pm2$, every factor must be controlled explicitly.
Problem Understanding
We are given a nonconstant polynomial $P\in\mathbb Z[x]$. The quantity $n(P)$ counts the distinct integers $k$ for which
$$(P(k))^2=1,$$
equivalently,
$$P(k)=1 \quad \text{or} \quad P(k)=-1.$$
The problem asks for a proof that
$$n(P)-\deg(P)\le2.$$
This is a Type B problem. The statement to be proved is already specified.
The objects involved are integer polynomials and their integer values. The difficulty comes from the fact that a polynomial of degree $d$ can easily take the same value at many integers, up to $d$ times for each fixed value. A naive argument separately bounding the number of solutions to
$$P(k)=1$$
and
$$P(k)=-1$$
gives only
$$n(P)\le2\deg(P),$$
which is insufficient.
The central insight is that the values $1$ and $-1$ differ by only $2$. For integers $a,b$ satisfying
$$P(a)=1,\qquad P(b)=-1,$$
the difference
$$P(a)-P(b)=2$$
must be divisible by $a-b$. Hence $a-b$ divides $2$. This arithmetic restriction forces all such integers to lie very close together, making it impossible to have too many of them unless the degree is correspondingly large.
Proof Architecture
The proof will use three lemmas.
Lemma 1 states that for any polynomial $F\in\mathbb Z[x]$ and any integers $u,v$, the difference $u-v$ divides $F(u)-F(v)$. This follows from the factorization
$$x-y \mid F(x)-F(y)$$
in $\mathbb Z[x,y]$.
Lemma 2 states that if $a,b\in\mathbb Z$ satisfy
$$P(a)=1,\qquad P(b)=-1,$$
then
$$a-b\in{\pm1,\pm2}.$$
This follows from Lemma 1 applied to $P(a)-P(b)=2$.
Lemma 3 states that if $A={a:P(a)=1}$ and $B={b:P(b)=-1}$ are both nonempty, then either $|A|\le2$ or $|B|\le2$. The proof fixes three distinct elements of one set and shows that no integer can simultaneously lie within distance at most $2$ from all three.
After proving the lemmas, the main argument proceeds as follows. Let
$$r=|A|,\qquad s=|B|.$$
Since $P(x)-1$ has degree $\deg P$, one has
$$r\le\deg P.$$
If $r\le2$, then immediately
$$r+s\le\deg P+2.$$
Otherwise $r\ge3$, and Lemma 3 gives $s\le2$, so again
$$r+s\le\deg P+2.$$
The most delicate point is Lemma 3. A superficial argument might claim that three integers cannot all be within distance $2$ of another integer, which is false for sets such as ${0,1,2}$. The proof must instead use the stronger divisibility information from Lemma 2 and analyze all possible configurations carefully.
Solution
Let
$$A={k\in\mathbb Z:P(k)=1},\qquad B={k\in\mathbb Z:P(k)=-1}.$$
Write
$$r=|A|,\qquad s=|B|.$$
Then
$$n(P)=r+s.$$
We first establish an elementary divisibility property of integer polynomials.
Lemma 1
For every polynomial $F\in\mathbb Z[x]$ and every pair of integers $u,v$, the integer $u-v$ divides $F(u)-F(v)$.
Proof
Write
$$F(x)=c_0+c_1x+\cdots+c_mx^m,$$
where $c_i\in\mathbb Z$.
Then
$$F(u)-F(v)=\sum_{i=1}^m c_i(u^i-v^i).$$
For each positive integer $i$,
$$u^i-v^i=(u-v)(u^{i-1}+u^{i-2}v+\cdots+v^{i-1}).$$
Hence every term $u^i-v^i$ is divisible by $u-v$, and therefore the whole sum $F(u)-F(v)$ is divisible by $u-v$. ∎
This lemma establishes the arithmetic constraint relating differences of inputs and outputs; ignoring integrality here would destroy the argument completely.
Lemma 2
If $a,b\in\mathbb Z$ satisfy
$$P(a)=1,\qquad P(b)=-1,$$
then
$$a-b\in{\pm1,\pm2}.$$
Proof
By Lemma 1, the integer $a-b$ divides
$$P(a)-P(b)=1-(-1)=2.$$
Hence $a-b$ is a divisor of $2$. Since $a\ne b$, because $P(a)\ne P(b)$, one obtains
$$a-b\in{\pm1,\pm2}.$$
∎
This lemma shows that every integer where $P$ equals $1$ lies within distance $2$ of every integer where $P$ equals $-1$; replacing divisibility by a weaker inequality would not suffice later.
Lemma 3
If both $A$ and $B$ are nonempty, then at least one of the inequalities
$$r\le2,\qquad s\le2$$
holds.
Proof
Assume for contradiction that
$$r\ge3 \quad \text{and} \quad s\ge3.$$
Choose distinct integers
$$a_1<a_2<a_3$$
from $A$.
Let $b\in B$. By Lemma 2,
$$|b-a_i|\le2$$
for each $i=1,2,3$.
Since $a_1,a_2,a_3$ are distinct integers,
$$a_3-a_1\ge2.$$
Because $|b-a_1|\le2$ and $|b-a_3|\le2$, the only possible value is
$$a_3-a_1=2.$$
Consequently,
$$a_2=a_1+1,\qquad a_3=a_1+2.$$
Again by Lemma 2,
$$b-a_i\in{\pm1,\pm2}$$
for $i=1,2,3$.
Applying this to $a_1,a_1+1,a_1+2$, one checks all possibilities for $b$.
If $b=a_1-2$, then
$$b-a_2=-3,$$
contradicting Lemma 2.
If $b=a_1-1$, then
$$b-a_3=-3,$$
contradicting Lemma 2.
If $b=a_1+1$, then
$$b-a_2=0,$$
contradicting $P(a_2)=1$ and $P(b)=-1$.
If $b=a_1+2$, then
$$b-a_3=0,$$
again impossible.
If $b=a_1+3$, then
$$b-a_1=3,$$
contradicting Lemma 2.
If $b=a_1+4$, then
$$b-a_2=3,$$
contradicting Lemma 2.
These cases exhaust all integers satisfying $|b-a_1|\le2$. Hence no such integer $b$ exists, contradicting $B\ne\varnothing$.
Therefore it is impossible that both $r\ge3$ and $s\ge3$. At least one of $r,s$ is at most $2$. ∎
This lemma establishes the decisive combinatorial restriction; the tempting shortcut of arguing only from interval lengths fails because three consecutive integers do fit inside an interval of length $2$.
We now complete the proof.
The polynomial
$$P(x)-1$$
has degree $\deg(P)$. Since it has exactly the integers in $A$ as roots,
$$r\le\deg(P).$$
If $r\le2$, then
$$n(P)=r+s\le2+s.$$
Since $s\le\deg(P)$, because $P(x)+1$ also has degree $\deg(P)$,
$$n(P)\le\deg(P)+2.$$
If $r\ge3$, then Lemma 3 yields
$$s\le2.$$
Using again
$$r\le\deg(P),$$
one obtains
$$n(P)=r+s\le\deg(P)+2.$$
Thus in all cases,
$$n(P)-\deg(P)\le2.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is Lemma 1. Re-derive it directly for monomials:
$$u^m-v^m=(u-v)\sum_{j=0}^{m-1}u^{m-1-j}v^j.$$
Every polynomial with integer coefficients is an integer linear combination of monomials, so the divisibility survives addition. A careless argument might invoke continuity or interpolation over $\mathbb R$, neither of which gives divisibility in $\mathbb Z$.
The second delicate step is the deduction in Lemma 2 that
$$a-b\in{\pm1,\pm2}.$$
The divisor $0$ must be excluded explicitly. If one forgets that
$$P(a)\ne P(b),$$
then one incorrectly allows $a=b$. The contradiction relies on the outputs being different.
The third delicate step is the exhaustion argument in Lemma 3. From
$$a_1<a_2<a_3$$
and
$$|b-a_i|\le2,$$
one cannot immediately conclude impossibility, because the set
$${a_1,a_1+1,a_1+2}$$
does fit inside an interval of radius $2$. The stronger statement from Lemma 2 is needed:
$$b-a_i\ne0.$$
Checking all six candidate positions for $b$ shows rigorously that each violates either the divisibility condition or distinctness.
Alternative Approaches
A different proof uses factorization. Let
$$P(x)-1=\prod_{i=1}^r(x-a_i)Q(x),$$
where the $a_i$ are the distinct integers satisfying $P(a_i)=1$.
For every integer $b$ with $P(b)=-1$,
$$-2=P(b)-1=\prod_{i=1}^r(b-a_i)Q(b).$$
Every factor is an integer. Hence
$$\prod_{i=1}^r|b-a_i|$$
divides $2$. If $r\ge3$, the only possibility is that the integers $a_i$ are consecutive and very tightly constrained. A careful analysis then shows that there can be at most two such integers $b$. Interchanging the roles of $1$ and $-1$ finishes the argument.
This approach is closer to algebraic number theory and factorization methods. The main proof is preferable because it isolates the essential arithmetic fact immediately through divisibility of polynomial differences and avoids auxiliary factor polynomials whose behavior must otherwise be controlled separately.