Problem 1765

1. **First Claim: The degree of $P$ is even.**

Proof: Suppose not, i.e., $\deg P = n$ with $n$ odd. Then there exist real numbers $u$ and $v$ such that if $x > v$, then $P(x) > P(v)$, and if $x < u$, then $P(x) < P(u)$. This is possible by taking $u$ and $v$ such that $P(v)$ is strictly greater than all local maxima and $P(u)$ is strictly smaller than all local minima.

There exists a constant $C$ such that if $Q(x) = |P(x+1) - P(x)|$, then $Q(x) > C|x|^{n-1}$ for all $|x| > C_0 > 0$, where all the roots of $Q$ belong to $(-C_0/2, C_0/2)$.

Now take a large $M$ such that $M > |u| + |v| + C + 1$. Fix a large integer $N$. For each pair of integers $(x, y)$ with $x \neq y$ such that $|P(x) - P(y)| \leq N$ (denoted as $(\star)$), we classify them as:
- Good: if $|x|, |y| \geq M$
- Bad: if exactly one of $|x|, |y|$ is less than $M$
- Whatever: if both have sizes smaller than $M$

Clearly, the number of $Whatever$ pairs is finite (for all $N$). So we shall not worry about them.

Now take a $bad$ pair. Suppose WLOG that $|x| \geq M$. Then
$$N > |P(x) - P(y)| \geq |P(x) - P(x+\epsilon)| > C|x|^{n-1},$$
where $\epsilon \in \{-1, 1\}$, and it's $1$ if $x < 0$ and $-1$ if $x > 0$.

Now take a good pair. WLOG $|x| > |y|$. So we know that
$$N > |P(x) - P(y)| \geq |P(x) - P(x+\epsilon)| > C|x|^{n-1}.$$

So we must conclude that if $(x, y)$ are a solution to $(\star)$, then both $|x|$ and $|y|$ are smaller than $C_1 N^{\frac{1}{n-1}}$ (where $C_1^{1-n} = C$). So the total number of solutions must be at most $4C_1^2 N^{\frac{2}{n-1}}$.

But we know that the number of solutions is at least $N/2$. So sending $N$ to infinity, we must have that
$$\frac{2}{n-1} \geq 1 \implies n \leq 3,$$
which is a contradiction. Hence, the degree of $P$ must be even.

2. **Second Claim: Given that the degree of $P$ is even, the majority of the solutions $(x, y)$ for $(\star)$ have $xy < 0$.**

Proof: The number of solutions where $xy \geq 0$ grows smaller than $N$. In fact, we can prove just as we did in Claim 1 that it grows with degree $\frac{2}{n-1}$. The proof uses the same arguments as in Claim 1, where we lower their difference by bringing one of them close to the other and then use the lower bound of degree $n-1$.

3. **Third Claim: There exists a unique rational number $L$ such that the polynomial $P(x) - P(L-x)$ has degree at most $n-2$.**

Proof: Let $P(x) = a_n x^n + \dots + a_0$. We can write the polynomial $P(x) - P(A-x)$ explicitly as
$$\sum_{k=0}^{n} a_k x^k - \sum_{k=0}^n a_k \sum_{i=0}^k x^i A^{k-i} \binom{k}{i},$$
which can be rewritten as
$$\sum_{k=0}^n x^k \left( a_k - \sum_{i=0}^{n-k} a_{i+k} A^i \binom{i+k}{k} \right).$$
Then $P(x) - P(A-x)$ has always degree at most $n-1$, as the coefficient of $x^n$ is $1 - (-1)^n = 0$, since $n$ is even.

The coefficient of $x^{n-1}$ is $2a_{n-1} + An$, which is $0$ if and only if $A = -\frac{2a_{n-1}}{n}$. This is our desired rational $L$.

So we conclude that the polynomial $P(x) - P(L-x)$ has degree at most $n-2$. In other words, there is a constant $C$ such that $|P(x) - P(L-x)| \leq C|x|^{n-2}$ for every $|x| > 0.1$.

4. **Fourth Claim (Naughty Lemma): We say that a pair $(x, y)$ is $naughty$ if it satisfies $(\star)$, $|x|, |y| > M$, $xy < 0$, and $x + y \neq L$.**

Proof: Suppose WLOG $|x| \geq |y|$. The intuition for proving this claim is that you can't directly come up with a bound for this difference, and as $xy < 0$, you use the fact that $P(L-y)$ is somehow close to $P(y)$, to then be able to compare their sizes. In other words, we will use the triangular inequality to say that:
$$|P(x) - P(y)| \geq |P(x) - P(L-y)| - |P(y) - P(L-y)|.$$
We already have an upper bound for $|P(y) - P(L-y)|$, so we're left with finding a bound for $|P(x) - P(L-y)|$. Let $t = 1$ if $L$ is an integer, and let $t = \min\{\{L\}, 1-\{L\}\}$ if $L$ is not an integer. So we can say that if $L-y < x$, then $|P(x) - P(L-y)| \leq |P(x) - P(x-t)|$. If $L-y > x$, then $|P(x) - P(L-y)| \leq |P(x) - P(x+t)|$. In other words, since $|x|, |L-y| > M$, we know that bringing them together will decrease the difference, as $x(L-y) > 0$. And, as $x, y$ are integers, we know that the difference between $x$ and $L-y$ is at least $t$. Since $t > 0$, we can find a constant $C_2$ such that both $|P(x) - P(x+t)|$ and $|P(x) - P(x-t)|$ are smaller than $C_2 |x|^{n-1}$. So we find that
$$N > |P(x) - P(y)| \geq |P(x) - P(L-y)| - |P(y) - P(L-y)| \geq C_2 |x|^{n-1} - C|y|^{n-2} \geq C_3 x^{n-1}$$
for some constant $C_3$ and large $|x| > M_0$. (The choice of $M$ does not interfere with $M_0$, so we may suppose as well that $M > M_0$). So this means that if a pair is naughty, then both $(x, y)$ have to be smaller than $C_4 N^{\frac{1}{n-1}}$ for some constant $C_4$, meaning that there are at most $4C_4^2 N^{\frac{2}{n-1}}$ naughty pairs.

5. **Conclusion: Combining everything we proved so far, we must conclude that there is a constant $C_5$ such that the number of solutions $(x, y)$ for $(\star)$ with $x + y \neq L$ is at most $C_5 N^{\frac{2}{n-1}}$.**

Then take $N$ sufficiently large such that $N/2.5 < N/2 - C_5 N^{\frac{2}{n-1}}$.

So for $N$ this large, the number of solutions for $(x, y)$ with $x + y = L$ must be at least $N/2.5$. Now let $Q(x) = P(x) - P(L-x)$. So this directly implies that $L$ must be an integer, and it also means that the polynomial $Q$ covers $N/2.5$ integers up to $N$. Let $d$ be the degree of $Q$. Clearly $d > 0$. We know that there is a constant $C_6$ such that $|Q(x)| > C_6 |x|^d$ for every non-zero $x$. This means that if $Q(x) < N$, then $x < C_7 N^{\frac{1}{d}}$ for some constant $C_7$. Sending $N$ to infinity, we conclude that $d \leq 1$, so $d = 1$.

Then $Q(x) = ax + b$ for some integers $a$ and $b$. (We may suppose WLOG $a > 0$. If not, we may switch $P$ by $-P$). But we know that if $0 < ax + b < N$, then $-b/a < x < N/a - b/a$. So there are at most $N/a + 1$ solutions for $(\star)$, which implies $a \leq 2.5 \implies a \leq 2$. If $a = 1$, then $Q$ covers all integers. If $a = 2$, then $Q$ must cover all even or all odd integers, concluding the problem.

$\blacksquare$