Exercise 3.3.19* ($\sum_{n=1}^p \left(\sum_{m=1}^h\genfrac{(}{)}{}{}{m+n}{p}\right)^2 = h(p-h)$)

Question

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Show that if $p$ is an odd prime and $h$ is an integer, $1 \leq h \leq p$, then
$$\sum_{n=1}^p \left(\sum_{m=1}^h \legendre{m+n}{p} ight)^2 = h(p-h).$$

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

As usual, we define $\legendre{\alpha}{p} = \legendre{a}{p}$ if $\alpha = [a]_p \in \F_p = \Z/p\Z$.
\begin{proof} 
If we expand the square, using the formula 
$$\left(\sum_{m=1}^h a_i ight)^2 = \sum_{m=1}^h a_m^2 + 2 \sum_{1 \leq i < j \leq h}a_i a_j,$$
we obtain for $a_i = \legendre{i +n}{p},\ i = 1, 2, \ldots,p$, and for any integer $n$,
\begin{align}
\left(\sum_{m=1}^h \legendre{m+n}{p} ight)^2 &=\sum_{m=1}^h \legendre{m+n}{p}^2 + 2 \sum_{1\leq i < j \leq h} \legendre{i+n}{p} \legendre{j+n}{p}.
\end{align}

We prove first that
\begin{align}
\sum_{n=1}^p \legendre{(i+n)(j+n)}{p} = 
\left\{
\begin{array}{ll}
- 1 &	ext{if }  i 
ot \equiv j \pmod p,\
p-1 &	ext{if }  i 
ot \equiv j \pmod p.
\end{array}
ight.
\end{align}
By Problem 17, for all $\alpha \in \F_p^*$,
\begin{align}
\sum_{y \in \F_p} \legendre{ y(y+ \alpha)}{p} = -1.
\end{align}
Let $\beta, \gamma$ be distinct elements of $\F_p^*$, and put $\alpha =\gamm - \beta$.
Since $\varphi : \F_p 	o \F_p$ defined by $x \mapsto y = \varphi(x)=  x + \beta$ is a bijection, we obtain by equation (3)
\begin{align*}
\sum_{x \in \F_p} \legendre{(x + \beta)(x + \gamma)}{p} &= \sum_{y \in \F_p} \legendre{ y(y+ \gamma - \beta)}{p} & (y = x + \beta)\
&=\sum_{y \in \F_p} \legendre{ y(y+ \alpha)}{p}\
&= -1.
\end{align*}
Therefore, for all integers $i,j$ such that $i
ot \equiv j \pmod p$, taking $\beta = [i]_p, \gamma = [j]_p$, we obtain $\sum\limits_{n=1}^p \legendre{(i+n)(j+n)}{p} = -1$.

Moreover, if $i \equiv j \pmod p$, then 
\begin{align*}
\sum_{i=1}^p \legendre{(i+n)(j+n)}{p} &= \sum_{i=1}^p \legendre{(i+n)^2}{p}\
&= \sum_{i=1}^p \legendre{i+n}{p}^2\
&= p- 1,
\end{align*}
because exactly one $i = i_0\in [\![1, p]\!]$ is such that $i_0 +n \equiv 0 \pmod p$, so that $\legendre{i_0 + n}{p} = 0$, and $ \legendre{i+n}{p}^2 = 1$ for the others $i 
e i_0$.

Now, using equation (1) and (2), we obtain by reversing the order of the summations
\begin{align*}
\sum_{n=1}^p \left(\sum_{m=1}^h \legendre{m+n}{p} ight)^2 & =  \sum_{n=1}^p \left(\sum_{m=1}^h \legendre{m+n}{p}^2 + 2 \sum_{1\leq i < j \leq h} \legendre{i+n}{p} \legendre{j+n}{p} ight)\
&=\sum_{m=1}^h \sum_{n=1}^p \legendre{m+n}{p}^2 +2 \sum_{1\leq i < j \leq h}  \sum_{n=1}^p \legendre{i+n}{p} \legendre{j+n}{p} \
&=\sum_{m=1}^h (p-1) + 2 \sum_{1\leq i < j \leq h} (-1)\
&= h(p-1) - 2\,  \frac{h(h-1)}{2}\
&= hp - h -h^2 + h\ 
&=h(p-h)
\end{align*}
(there are $(h(h-1))/2$ ordered pairs $(i,j)$ such that $1 \leq i < j \leq h$).

We have proved
$$\sum_{n=1}^p \left(\sum_{m=1}^h \legendre{m+n}{p} ight)^2 = h(p-h).$$
\end{proof}

Exercise 3.3.19* ($\sum_{n=1}^p \left(\sum_{m=1}^h\genfrac{(}{)}{}{}{m+n}{p}\right)^2 = h(p-h)$)

Answers

Comments

Exercise 3.3.19* ($\sum_{n=1}^p \left(\sum_{m=1}^h\genfrac{(}{)}{}{}{m+n}{p}\right)^2 = h(p-h)$)

Answers

Comments

Add answer