Polynomial interpolating sequence mod p has small degree Let $p$ be an odd prime and $a_1, a_2,...,a_p$ be integers. Prove that the following two conditions are equivalent:
1) There exists a polynomial $P(x)$ with degree $\leq \frac{p-1}{2}$ such that $P(i) \equiv a_i \pmod p$ for all $1 \leq i \leq p$
2) For any natural $d \leq \frac{p-1}{2}$, 
$$ \sum_{i=1}^p (a_{i+d} - a_i )^2 \equiv 0 \pmod p$$
where indices are taken $\pmod p$
 A: We will express our expressions in $\mathbb{F}_p$.
First notice that the statement does not change if the bound on $d$ is omitted: you may replace $d$ by $-d$, and for $d=0$ the condition is satisfied; so we may allow all $d\in\mathbb{F}_p$.
The main tool in the solution is this identity. If $0\le m<2p-2$ is a nonnegative integer then 
$$
\sum_{i\in\mathbb{F}_p} i^m = \begin{cases}
-1 & \text{if } m=p-1 \\
0 & \text{otherwise.} \\ \end{cases}
$$
(we define $0^0=1$.)
Proof: The case $m=0$ is trivial.
For $m=p-1$ we can apply Fermat's theorem. In the remaining cases take a 
primitive root $g$ modulo $p$. Then
$$ 
\sum_{\in\mathbb{F}_p} i^m  = \sum_{j=1}^{p-1} g^{jm} \equiv \frac{g^{m(p-1)}-1}{g^m-1}=0.
$$
Now let $P(x)$ be the unique polynomial with $P(i)\equiv a_i\pmod{p}$ and $D=\deg P\le p-1$. We can expand $(P(x+y)-P(x))^2$ as
$$
(P(x+y)-P(x))^2 = \sum_{k=0}^{2p-4} a_k(y) x^k
$$
with some polynomials $a_k(y)$. (Notice that $\deg_x(P(x+y)-P(x))=D-1\le p-2$.)
We focus on the coefficient $a_{p-1}(y)$.
If $D\le\frac{p-1}2$ then $\deg_x (P(x+y)-P(x))^2=2(D-1)<p-1$, so $a_{p-1}(y)=0$. Hence, for every $d$ we have
$$
\sum_{i\in\mathbb{F}_p} (P(i+d)-P(i))^2 = 
\sum_{i\in\mathbb{F}_p} \sum_{k=0}^{p-2} a_k(d) i^k =
\sum_{k=0}^{p-2} a_k(d) \sum_{i\in\mathbb{F}_p}^p i^k =
\sum_{k=0}^{p-2} a_k(d) \cdot 0 .
$$
If $D\ge\frac{p-1}2+1=\frac{p+1}2$, then we claim that the polynomial $a_{p-1}$ is nonzero. Indeed, if the leading term in $P$ is $Ax^D$, then the coefficient of $x^{p-1}y^{2D-p+1}$ in 
$(P(x+y)-P(x))^2$ is $\Big(A\binom{D}{(p-1)/2}\Big)^2\ne0$. 
The degree of $a_{p-1}(y)$ is $2D-p+1<p$.
Hence, there is a value $d$ such that $a_{p-1}(d)\not\equiv 0\pmod{p}$. For that $d$ we have
$$
\sum_{i\in\mathbb{F}_p}^p (P(i+d)-P(i))^2 = 
\sum_{i\in\mathbb{F}_p}^p \sum_{k=0}^{2p-4} a_k(d) i^k =
\sum_{k=0}^{2p-4} a_k(d) \sum_{\in\mathbb{F}_p}^p i^k =
-a_{p-1}(d) \ne 0.
$$
