We begin with an useful lemma: Let $p$ be a prime then if $p-1 | k $ one has $$\sum_{i=1}^{p} i^k \equiv -1 \pmod p$$and if $p-1 \not | k$ then one has $$\sum_{i=1}^{p} i^k \equiv 0 \pmod p$$The first assertion is obvious as each term will contribute $1$ except for $p^k$ which is $0$ and for the second, let the sum be $S$ and note that $g^kS \equiv S \pmod p$ where $g$ is a primitive root $\pmod p$. Since $g^k \not \equiv 1 \pmod p$ then one must have $S \equiv 0 \pmod p$. Now lets begin with the easier assertion that 1) => 2). Fix $d$ and let $P(x)$ be the interpolating polynomial of $a_i$ and note that the sum in question is $\sum_{i=1}^{p} (P(i+d) - P(i))^2$. Note that $Q(x) = P(x+d) - P(x)$ is a polynomial of degree $< \frac{p-1}{2}$ hence if you expand the sum in terms of $i^k$ one gets a polynomial in $i$ whose degree is at most $p-2$. Thus by our lemma the sum will evaluate to $0$. For 2) = > 1), assume that the interpolating polynomial is of degree $> \frac{p-1}{2}$ and hence $Q(x)^2$ will have a $x^{p-1}$ term. It suffices to show that this is non-zero in $\pmod p$ for some $d$. Now note that the coefficients of $x^i$ are actually polynomials in $d$ and that the degree for $x^{p-1}$ is at most $2k - (p-1) < p$ where $k$ is the degree of $P(x)$. Hence if it is $0 \pmod p$ for all $d$, it must be the zero polynomial in $\pmod p$. We shall show that the leading coefficient is not divisible by $p$ which will gives us a contradiction. Let $P(x) = \sum_{i=1}^{k} a_ix^i$ where $a_k$ is non-zero $\pmod p$. Then the coefficient of $x^{p-1}$ with highest power in $d$ is $d^{2k-p+1}$ which comes from $a_k^2 (x+d)^{2k} - 2a_k^2x^k(x+d)^k$, Since it suffices to show that is non-zero, we can divide away the $a_k^2$ and reduce it to $\binom{2k}{p-1} - 2\binom{k}{2k-p+1}$. However note that the first binomial coefficient is exactly $0 \pmod p$ as $p$ divides the numerator but not the denominator and the second one clearly isn't $0 \pmod p$ as there is no factor of $p$ to be found. Thus we arrive at a contradiction and we are done.

<fattypiggy123> wrote: $Q(x) = P(x+d) - P(x)$ is a polynomial of a degree $< \frac{p-1}{2}$ Dear fattypiggy123, Can you tell me WHY?

Because if you expand it out treating $d$ as a constant, then the $x^{\frac{p-1}{2}}$ coefficients will cancel each other out

Oh, yes. thanks

fattypiggy123 wrote: Now lets begin with the easier assertion that 1) => 2). Fix $d$ and let $P(x)$ be the interpolating polynomial of $a_i$ and note that the sum in question is $\sum_{i=1}^{p} (P(i+d) - P(i))^2$. Note that $Q(x) = P(x+d) - P(x)$ is a polynomial of degree $< \frac{p-1}{2}$ hence if you expand the sum in terms of $i^k$ one gets a polynomial in $i$ whose degree is at most $p-2$. Thus by our lemma the sum will evaluate to $0$. I think this part only works for integer coefficoent polynomials $Q$.Now there are two possiblities. 1.The theory also works for $Q$ with rational coefficients(This is non trivial of course). 2.No matter the polynomial$P$ may have rational and non-integer coefficients $Q$ have integer coefficients untill $P$ gives out integers.(This result is also non-trivial) So can you explain more please about the part I wrote please?Unless I am missing something the part is trivial if $P$ had integer coefficients(Which in fact isn't nessisarily true)thanks in advance.

Somehow I only thought of integer polynomials when doing this problem. But the solution carries over to the rational coefficient case as long as $p$ does not divide the denominator of any coefficient. Then we can treat $\frac{a}{b}$ as $ab^{-1}$ mod $p$ and things will still make sense. In this case, if we Lagrange interpolate the $P(i) = a_i$, then the denominator will be a product of $j-i$ for $0 \leq i \not = j < p$ and so none of them will be a multiple of $p$.

fattypiggy123 wrote: For 2) = > 1), assume that the interpolating polynomial is of degree $> \frac{p-1}{2}$ and hence $Q(x)^2$ will have a $x^{p-1}$ term. It suffices to show that this is non-zero in $\pmod p$ for some $d$. Now note that the coefficients of $x^i$ are actually polynomials in $d$ and that the degree for $x^{p-1}$ is at most $2k - (p-1) < p$ where $k$ is the degree of $P(x)$. Hence if it is $0 \pmod p$ for all $d$, it must be the zero polynomial in $\pmod p$. We shall show that the leading coefficient is not divisible by $p$ which will gives us a contradiction. Let $P(x) = \sum_{i=1}^{k} a_ix^i$ where $a_k$ is non-zero $\pmod p$. Then the coefficient of $x^{p-1}$ with highest power in $d$ is $d^{2k-p+1}$ which comes from $a_k^2 (x+d)^{2k} - 2a_k^2x^k(x+d)^k$, Since it suffices to show that is non-zero, we can divide away the $a_k^2$ and reduce it to $\binom{2k}{p-1} - 2\binom{k}{2k-p+1}$. However note that the first binomial coefficient is exactly $0 \pmod p$ as $p$ divides the numerator but not the denominator and the second one clearly isn't $0 \pmod p$ as there is no factor of $p$ to be found. Thus we arrive at a contradiction and we are done. Dear fattypiggy123, I have some stucks, and need some explainations: Firstly, how can can you know the existence of the interpolating polynomial above. Secondly, ""Hence if it is $0 \pmod p$ for all $d$, it must be the zero polynomial in $\pmod p$ ,"" can you explain this clearly this for me. Thirdly, ""We shall show that the leading coefficient is not divisible by $p$ which will gives us a contradiction."" And this I am new to Polynomial and don't know much it's properties, thank you so much

kahliipreyta wrote: Firstly, how can can you know the existence of the interpolating polynomial above. Lagrange's interpolation tells you that given $n+1$ points, we can find an unique polynomial of degree $\leq n$ that passes through it. Furthermore, there is a formula for this polynomial. Applying it to the points $(i,a_i)$ will give you the interpolating polynomial we want. Quote: Secondly, ""Hence if it is $0 \pmod p$ for all $d$, it must be the zero polynomial in $\pmod p$ ,"" can you explain this clearly this for me. Lagrange's theorem tells you that a non-zero polynomial of degree $k$ has at most $k$ roots mod $p$. In particular, our polynomial in $d$ that represents the coefficient of $x^{p-1}$ is of degree at most $p-1$ and so if it is $0 \pmod p$ for all $d$, this implies that it has $p$ roots and thus must be the zero polynomial in mod $p$. Quote: Thirdly, ""We shall show that the leading coefficient is not divisible by $p$ which will gives us a contradiction."" For a polynomial to be the zero polynomial in mod $p$, we need $p$ to divide every coefficient. But if the leading coefficient is not divisible by $p$, this cannot be the case.

fattypiggy123 wrote: 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$ Lemma: Let $p$ be a prime then if $p-1 | k $ then $$\sum_{i=1}^{p} i^k \equiv -1 \pmod p$$and if $p-1 \not | k$ then $$\sum_{i=1}^{p} i^k \equiv 0 \pmod p$$Proof: The first sum is easy. The second one is equivalent to $\sum_{i=1}^p g^{ik}$ where $g$ is a primitive root modulo $p$ Summing up as a geometric series we get the sum equivalent to $0$ modulo $p$ First we will show the first direction i.e $A \rightarrow B$ The sum is equivalent to $\sum_{i=1}^p (P(i+d)-p(i))^2$ Since $\deg(P(i+d)-P(i))<\frac{p-1}{2}$ and we are done by Lagrange’s theorem and Lemma 1. For the second part $B \rightarrow A$,let $Q(x)$ be the interpolating polynomial of $a_1,a_2,………,a_n$ By Lagrange interpolation, construct a polynomial $P(x)=\prod a_i a_{i+d} \prod_{j \neq 1} (X-j)$ Expanding it gives,$P(x) \equiv aX^r+bX^r-1+……… \pmod p$ If $r \le \frac{p-1}{2}$,then we will be done in a similar way as the previous part,so assume that $r > \frac{p-1}{2}$ Writing $Q(x)=\sum_{i=1}^p P(i)[a(X+i)^r+b(X+i)^{r-1}+……….]$ and expanding the coefficient of $X^B$ in $Q(X)-Q(0)$ is $P(i)(a \binom{r}{{B}}i^{p-1-r}+…………$ Clearly this implies $a^2 \binom{r}{{B}} \equiv 0 \pmod p$ for all $B$,a contradiction so we are done.

We work in $\mathbb F_p$ The following lemma is well-known. Lemma 1. (i) Every function from $\mathbb F_p$ to itself can be written as a polynomial with degree at most $p-1$. (ii) A polynomial $P(x)$ in $\mathbb F_p[x]$ with degree at most $p$ satisfies $$\sum_{i=1}^pP(x)=0$$if and only if the coefficient of $x^{p-1}$ is zero. $\blacksquare$ Now $(1)$ to $(2)$ is obvious. Indeed, the polynomial $Q(i)=P(i+d)-P(i)$ is of degree at most $\frac{p-3}{2}$, hence the coefficient of $x^{p-1}$ in $Q^2$ is zero. As a result, by the lemma, $$\sum_{i=1}^p(a_{i+d}-a_i)^2=\sum_{i=1}^pQ(i)^2=0$$ Now we move on to the opposite direction. We show another lemma regarding the finite difference of polynomials. For each $f\in \mathbb F_p[x]$ define $$\Delta(f)(x)=f(x+1)-f(x)$$and $$\Delta^n(f)(x)=\Delta^{n-1}(f)(x+1)-\Delta^{n-1}(f)(x)$$It is easy to see that we can extend the condition $(ii)$ to $1\leq d\leq p$. The proof of the following lemma is well-known Lemma 2. (i) $\deg\Delta^i(f)=\deg f-i$ (ii) Suppose $\deg f=m$, then the leading coefficient of $\Delta^i(f)$ is $(m-i+1)...m$ (iii)If $\Delta (f)=\Delta(g)$ then $f$ and $g$ differs by a costant. (iv) For each polynomial $g$ with coefficients in $\mathbb F_p$, there exists $f$ such that $\Delta (f)=g$ where $\deg f=\deg g+1$. $\blacksquare$ Now define $g=\Delta(f)$. Then by the condition we have \begin{align*} \sum_{i=1}^pg(i)&=0\hspace{20pt}(1)\\ \sum_{i=1}^p(g(i)+g(i+1)+...+g(i+d))^2&=0 \text{ for each }1\leq d\leq p \end{align*}Now by induction it is easy to see that $$\sum_{i=1}^pg(i)g(i+d)=0$$for each $1\leq d\leq p$. Let the degree of $g$ be $m$, then we have $$\sum_{i=1}^pg(i)\Delta^k(g)(i+d)=0\hspace{20pt}(2)$$for each $1\leq k\leq m$. Claim. $$\sum_{i=1}^pg(i)i^j=0$$for each $1\leq j\leq m$. Proof. We induct on $j$. The case $j=0$ is given by $(1)$. Now assume all smaller cases hold. For general $j$, we see that by $(2)$, $\Delta^{m-j}$ is a degree $j$ polynomial, hence $$\sum_{i=1}^pg(i)\Delta^{m-j}(g)(i+d)=0$$Notice that all terms in $\Delta^{m-j}(g)(i+d)$ with degree less than $j$ vanishes by the inductive hypothesis. Therefore, $$\sum_{i=1}^p(m-i+1)...mg(i)i^j=0$$which verifies the inductive step and proves the claim. $\blacksquare$ Now if $m\geq \frac{p-1}{2}$ then $g(x)x^m$ will have a nonzero coefficient of the term $x^{p-1}$, which is a contradiction. Hence $m\leq \frac{p-3}{2}$. Therefore, there exists a polynomial $f$ with degree at most $\frac{p-1}{2}$ such that $$\Delta(f)=g$$by (iv) of Lemma 2. Therefore, $f$ and the function $h(i)=a_i$ differ by a constant and we are done.

fattypiggy123 wrote: Somehow I only thought of integer polynomials when doing this problem. But the solution carries over to the rational coefficient case as long as $p$ does not divide the denominator of any coefficient. Then we can treat $\frac{a}{b}$ as $ab^{-1}$ mod $p$ and things will still make sense. In this case, if we Lagrange interpolate the $P(i) = a_i$, then the denominator will be a product of $j-i$ for $0 \leq i \not = j < p$ and so none of them will be a multiple of $p$. It seems that in the original question it mentions in the condition of $(i)$ that the polynomial is of integer coefficients.

Two years ago, I did this problem in 2.5h. Today, I did it in 30 mins... Let $P(x)$ be the unique polynomial in $\mathbb{Z}_p[x]$ with degree at most $p-1$ such that $P(j)=a_j$ for all $j=0,1,\cdots,p-1$. All equalities are done in $\mathbb{Z}_p$. 1 implies 2: If $\deg P\le \frac{p-1}{2}$, then $\sum\limits_{j=0}^{p-1} (a_{j+d}-a_j)^2=\sum\limits_{j=0}^{p-1} (P(j+d)-P(j))^2= -[j^{p-1}](P(j+d)-P(j))^2 = 0$ since $P(j+d)-P(j)=A(j)$ is a polynomial of degree $\deg P-1$ in $j$ 2 implies 1: Let $Q(x)=\sum\limits_{j=0}^{p-1} (P(j+x)-P(j))^2$. We are given that $Q(0)=Q(1)=\cdots=Q(p-1)=0$, so $x^p-x\mid Q(x)$ in $\mathbb{Z}_p[x]$. Let $P(x)=\sum\limits_{j=0}^d y_jx^j$. We have $$P(j+x)-P(j) = \sum\limits_{k=0}^d y_k ((j+x)^k-j^k) = \sum\limits_{k=0}^d y_k \sum\limits_{l<k} \binom kl j^l x^{k-l}$$ Thus, $Q(x)=\sum\limits_{j=0}^{p-1} (P(j+x)-P(j))^2 = -[j^{p-1}] (P(j+x)-P(j))^2$ This polynomial has a total degree of at most $2p-2$. Therefore, the $j^{p-1}$ terms have contribution at most degree $p-1$, so this must vanish in $\mathbb{Z}_p[x]$. We can write this as $$\sum\limits_{0\le l<k\le d, 0\le n<m\le d, l+n=p-1} y_ky_m \binom kl \binom mn x^{k+m-p+1}$$ Assume $d>\frac{p-1}{2}$. When $k=m=d$, the coefficient is $y_d^2 \sum\limits_{n<d, l<d, n+l=p-1} \binom dn \binom dl $ $=y_d^2 \sum\limits_{ n+l=p-1} \binom dn \binom dl - 2\binom{d}{2d-p-1}$ $=y_d^2 (\binom{2d}{p-1} - 2\binom{d}{2d-p-1})$ Since $2d>p$, $p\mid \binom{2d}{p-1} $. However, $2\binom{d}{2d-p-1} \mid 2d!$ is not a multiple of $p$, contradiction!!!

My proof is similar to a lot of people here, but ig that was the most obvious way to do it.

$(1)\implies (2)$ $\sum_{i=1}^p (a_{i+d} - a_i )^2 = \sum_{i=1}^p (P(i+d)-P(i))^2$. Degree of this polynomial is less than $p-1$, thus by the above lemma the sum is $0$ in $\mathbb{Z}_p[x]$. $(2)\implies (1)$ [This part involves too much computation] By Lagrange's theorem we have, $d^{p}-d\mid \sum_{i=1}^p (P(i+d)-P(i))^2=Q(i)$ Let $P(k)=\sum_{i=0}^{d}{c_ik^i}$, we just have to show that the $Q(i)\neq 0 \pmod{p}$. FTSOC assume $d>\frac{p-1}{2}$. Note that $P(i+d)-P(i)=\sum_{j=0}^d c_j \sum\limits_{k<j} \binom jk i^{j-k} d^{k}$ and we will get the coefficient of $d$ when we put $j=l=d$. So we have $$c_d^2\Biggl (\binom{2d}{p-1}-2\binom{d}{2d-p-1}\Biggr) $$which is not $0\pmod{p}$. So we are done.