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$
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. $$
