, 2024

Solution:
We claim that such polynomials exist if and only if $d \leq 3$. The following examples show that such polynomials do exist for $d \leq 3$:
$$\begin{array}{lll} d=1: & d^{2}-d=0, & P_{1}(x)=x, \\ \end{array} \begin{array}{ll} & P(0)=0 ; \end{array}$$
We can make more examples by adding constants.

Now we will show that there are no examples of degree greater than 3.
From now on we assume (without loss of generality) that the leading coefficient of our polynomial $P$ is positive and that all values $P(i)$ are positive (by adding a constant if necessary) for integers $i$ in the range $0 \leq i \leq d^{2}-d+1$.

Assume (for contradiction) that $P$ is a polynomial of degree $d \geq 4$ that satisfies the conditions of the problem and let $P(0), \ldots, P\left(d^{2}-d\right)$ take values among $p_{1}<\cdots<p_{d}$. For $i=1, \ldots, d$, let $n_{i} \geq 0$ be the number of appearances of $p_{i}$ among $P(0), \ldots, P\left(d^{2}-d\right)$.
By definition $n_{1}+\cdots+n_{d}=d^{2}-d+1$. Since $P$ has degree $d$, $n_{i} \leq d$. The key observation is now the following.

Claim 1
Make the convention that $n_{0}=n_{d+1}=0$. If $n_{i}=d$ for some $i$ in the range $1 \leq i \leq d$, then $n_{i \pm 1} \leq d-2$.

Proof. Up to scaling and hence without loss of generality, $P$ has leading coefficient $+1$. Since $n_{i}=d$, there exist non-negative integers $a_{1, i}<\cdots<a_{d, i} \leq d^{2}-d$ such that
$$P(X)=\left(X-a_{1, i}\right) \cdots\left(X-a_{d, i}\right)+p_{i}.$$
By construction, each of the $d-1$ intervals $I_{j}=\left[a_{j, i}, a_{j+1, i}\right]$ contains at least one local extremum of $P$, so contains exactly one such extremum because $P$, having degree $d$, has at most $d-1$ such extrema. Suppose that $i \leq d-1$ and that $P(m)=p_{i+1}>p_{i}$ for some $m \in\{0, \ldots, d^{2}-d\}$. Since $P$ has positive leading coefficient,
$$m \in\left(a_{d, i}, \infty\right) \cup\left(a_{d-2, i}, a_{d-1, i}\right) \cup \cdots \cup\left(a_{1, i}, a_{2, i}\right)$$
if $d$ is odd or
$$m \in\left(a_{d, i}, \infty\right) \cup\left(a_{d-2, i}, a_{d-1, i}\right) \cup \cdots \cup\left(-\infty, a_{1, i}\right)$$
if $d$ is even.

Suppose that $a_{j, i}<m<a_{j+1, i}$, for some $j \in\{1, \ldots, d-1\}$. If $a_{j, i}+1<m<a_{j+1, i}-1$, then, because $I_{j}$ contains exactly one local extremum (which is a maximum),
Either $p_{i+1}=P(m)>P\left(a_{j, i}+1\right)$ or $p_{i+1}=P(m)>P\left(a_{j+1, i}-1\right)$. Since $P\left(a_{j, i}+1\right)>P\left(a_{j, i}\right)=p_{i}$ and $P\left(a_{j, i}-1\right)>P\left(a_{j+1, i}\right)=p_{i}$, this contradicts the requirement that $P\left(a_{j, i}+1\right), P\left(a_{j+1, i}-1\right) \in\{p_{1}, \ldots, p_{d}\}$. Hence $m=a_{j, i}+1$ or $m=a_{j, i}-1$. Similarly, if $m>a_{d, i}$, then $m=a_{d, i}+1$, but if $m<a_{1, i}$ (which may arise when $d$ is even), then $m=a_{1, i}-1$. This shows that $m$ belongs to this list:
$$a_{d, i}+1, a_{d-1, i}-1, \ldots, a_{2, i}+(-1)^{d}, a_{1, i}-(-1)^{d}$$
This list contains at most $d$ different integers. It follows in particular that, if $n_{i+1}>d-2$, then either
$$P\left(a_{d, i}+1\right)=p_{i+1}=P\left(a_{d-1, i}-1\right)$$
or
$$P\left(a_{2, i}+(-1)^{d}\right)=p_{i+1}=P\left(a_{1, i}-(-1)^{d}\right)$$
with, additionally, $a_{2, i}+(-1)^{d} \neq a_{1, i}-(-1)^{d}$.

We have
$$\left|P\left(a_{1, i} \pm 1\right)-p_{i}\right|=1 \cdot\left|a_{1, i} \pm 1-a_{2, i}\right| \cdot \prod_{j=3}^{d}\left|a_{1, i} \pm 1-a_{j, i}\right|$$
and
$$\left|P\left(a_{2, i} \mp 1\right)-p_{i}\right|=\left|a_{2, i} \mp 1-a_{1, i}\right| \cdot 1 \cdot \prod_{j=3}^{d}\left|a_{2, i} \mp 1-a_{j, i}\right|.$$
As $a_{1, i}<a_{2, i}<a_{3, i}<\ldots<a_{d, i}$ we have $\left|a_{1, i} \pm 1-a_{j, i}\right| \geq\left|a_{2, i} \mp 1-a_{j, i}\right|$ with equality possible only if $a_{1, i}+1=a_{2, i}-1$. We also have $\left|a_{1, i} \pm 1-a_{2, i}\right|=\left|a_{2, i} \mp 1-a_{1, i}\right|$, which can be zero only if $a_{1, i}+1=a_{2, i}-1$. We conclude that $\left|P\left(a_{1, i} \pm 1\right)-p_{i}\right|>\left|P\left(a_{2, i} \mp 1\right)-p_{i}\right|$ or $a_{1, i}+1=a_{2, i}-1$.

Looking at the other end of the list of $\left(a_{j, i}\right)$ as $j$ varies, we have
$$\left|P\left(a_{d-1, i}-1\right)-p_{i}\right|=1 \cdot\left|a_{d-1, i}-1-a_{d, i}\right| \cdot \prod_{j=1}^{d-2}\left|a_{d-1, i}-1-a_{j, i}\right|$$
and
$$\left|P\left(a_{d, i}+1\right)-p_{i}\right|=\left|a_{d, i}+1-a_{d-1, i}\right| \cdot 1 \cdot \prod_{j=1}^{d-2}\left|a_{d, i}+1-a_{j, i}\right|$$
In these two formulas the shared factor outside the product is at least 2 and so is not 0. Now look at the factors behind the product symbols. As $a_{1, i}<a_{2, i}<a_{3, i}<\ldots<a_{d, i}$, for $j \leq d-2$ we have $\left|a_{d, i}+1-a_{j, i}\right|>\left|a_{d-1, i}-1-a_{j, i}\right|$. We conclude that $\left|P\left(a_{d, i}+1\right)-p_{i}\right|>\left|P\left(a_{d-1, i}-1\right)-p_{i}\right|$. Claim 1 is proved.

For each $i \in\{1, \ldots, d-1\}$, there are three possibilities:
- $n_{i}, n_{i+1} \leq d-1$
- $n_{i}=d$ and $n_{i+1} \leq d-2$
- $n_{i+1}=d$ and $n_{i} \leq d-2$.
In all three cases, $n_{i}+n_{i+1} \leq 2(d-1)$. If $n$ is even, this leads to the contradiction
$$d^{2}-d+1=\left(n_{1}+n_{2}\right)+\cdots+\left(n_{d-1}+n_{d}\right) \leq(d / 2)[2(d-1)]=d^{2}-d$$
This is an important staging point in the argument because we have eliminated the possibility of a polynomial of even degree $d$ satisfying the conditions of the problem if $d \geq 4$.

From now on we assume that $d \geq 5$ is odd, and
$$d^{2}-d+1=\left(n_{1}+n_{2}\right)+\cdots+\left(n_{d-2}+n_{d-1}\right)+n_{d} \leq[(d-1) / 2][2(d-1)]+d=d^{2}-d+1.$$
Equality must therefore hold throughout. Since the sum can also be grouped as
$$n_{1}+\left(n_{2}+n_{3}\right)+\cdots+\left(n_{d-1}+n_{d}\right)$$
this requires $n_{1}=n_{d}=d, n_{i}+n_{i+1}=2(d-1)$ for $i=1,2, \ldots, d-1$ i.e. $n_{i}=d$ for odd $i$ and $n_{i}=d-2$ for even $i$.

We are interested in the degree of $P$ being $d \geq 5$ and odd, and showing that no polynomial $P$ satisfying the conditions of the problem can exist. There are $d-1 \geq 4$ extremal points which alternate between local maxima and minima (in that order) as you read from left to right (we normalize so that $P$ is monic). For any $p_{i}$ with $i$ odd, the line $y=p_{i}$ (with $i$ odd) crosses the graph of $P$ in $d$ places with $x$-coordinates in the real closed interval $[0, d^{2}-d]$ at points $(z, p_{i})$ so each $z$ must be an integer. Suppose that $J$ is a real interval on the $x$-axis ending at adjacent local extrema. The function defined by $P$ is monotonic on each $J$. The line $y=p_{i}$ ($i$ odd) meets the graph at most once on $J$. Therefore it meets the graph of $P$ exactly once in the interior of each $J$ (there are $d-2$ such intervals) and at the only two possible places outside the union of these intervals.

Now consider $p_{j}$ when $j$ is even (so $n_{j}=d-2$). These $d-2$ intervals $J$ afford $d-2$ real values at which $P$ will take $p_{j}$ as a value where $j$ is fixed and even. The question is, are the corresponding arguments integers? The proof of Claim 1 tells us that in the middle of the run $\{0,1, \ldots, d^{2}-d+1\}$ all is well: the polynomial is assuming the value $p_{j}$ at an integer where the polynomial assumes the values $p_{j-1}$ and $p_{j+1}$ at adjacent integers in some order. The problem is at the ends of the run where $|P(a_{1, i}+1)-p_{i}|>|P(a_{2, i}-1)-p_{i}|$ and $|P(a_{d, i}+1)-p_{i}|>|P(a_{d-1, i}-1)-p_{i}|$. When $j$ is even, two of the roots of $P(x)-p_{j}$ are not integers, and we now know approximately where this trouble is happening (at the ends).

At this point we could finish if $d \geq 7$, because the run of regular behaviour in the middle is sufficiently long that we could obtain a contradiction. However we have to work a little harder to include the case $d=5$. We now show that the run of regular behaviour is slightly longer than we have currently established. We do this using Claim 2.

Claim 2. If $d$ is odd, and $n_{i}=d, n_{i \pm 1}=d-2$ for some $i$, then $P$ attains $p_{i \pm 1}$ precisely at the $d-2$ integers
$$a_{2, i}-1, a_{3, i}+1, \cdots, a_{d-2, i}-1, a_{d-1, i}+1$$
Proof Suppose (for contradiction) $a_{1, i}+1 \neq a_{2, i}-1$ and $P\left(a_{1, i}+1\right)=p_{i+1}$. Now $a_{1, i}<a_{2, i}$ so either $a_{1, i}+1<a_{2, i}-1$ or $a_{1, i}=a_{2, i}-1$. In the latter case, $P\left(a_{1, i}+1\right)=P\left(a_{2, i}\right)=p_{i}$, a contradiction. In the former case, the proof of Claim 1 shows that
$$|P(a_{2, i}-1)-p_{i}|<|P(a_{1, i}+1)-p_{i}|=|p_{i+1}-p_{i}|=p_{i+1}-p_{i}$$
so $P(a_{2, i}-1)<p_{i+1}$. The polynomial is decreasing on the interval $(a_{2, d}, a_{2,1})$ so $p_{i}<P(a_{2, i}-1)<p_{i+1}$ which is absurd because $P(a_{2, i}-1)=p_{j}$ for some $j$. Therefore $P(a_{2, i}-1)=p_{i+1}$ for all odd $i$. A similar argument shows that $P(a_{d-1, i}+1)=p_{i+1}$ so Claim 2 is established.

Now we have a sequence of alternating falling then rising then falling etc. full runs starting at $(a_{2, d}, p_{d})$ and ending at $(a_{d-1,1}, p_{1})$ so the initial run of $3d+1$ terms of this run of values is
$$p_{d}, p_{d-1}, \cdots p_{1}, p_{1}, p_{2}, \ldots, p_{d}, p_{d}, p_{d-1}, \cdots p_{1}, p_{1}$$
which starts at $(a_{2, d}, p_{d})$ and ends at $(a_{4,1}+1, p_{1})$ which is fine because $4 \leq d-1$.

There are now various ways we can finish.

(a) Consider the run of length $2d$ consecutive values
$$p_{d}, p_{d-1}, \cdots p_{1}, p_{1}, p_{2}, \ldots, p_{d}$$
The first $d+1$ points determine $P(x)$. The last $d+1$ values also determine $P$ but the values are in the reverse order, so $P(X)=P(c-X)$ for some constant $c$. However, the coefficients of $X^{d}$ have opposite signs ($d$ is odd) so this is absurd.

(b) The idea in (a) can be expressed in terms of Lagrange interpolation to obtain essentially the same contradiction. Construct $P$ in two ways using Lagrange interpolation on both the first $d+1$ and the last $d+1$ points. The symmetry in the data forces the graph of $P$ to have a vertical axis of symmetry. This is absurd because the degree of $P$ is odd.

(c) The initial fragment length $3d+1$ mentioned above at $(*)$ includes two identical runs of values of $P$ (in the same order) of length $d+1$. The polynomial $P$ is determined by each of them and so $P(X)=P(X+c)$ for some constant $c$ and so the polynomial defines a bounded function which is absurd.

Therefore, the only possible values are $d=1,2,3$.