= Quadratic Legendre-symbol correlation
For every <odd prime> $p$, the <Legendre symbol> correlation satisfies
$$
\sum_{x\in\mathbb F_p}\left(\frac{x(x+1)}p\right)=-1.
$$
The small negative value measures an exact dependence between neighboring square tests; it is not obtained by treating them as independent.
Count the pairs $(x,v)\in\mathbb F_p^2$ satisfying $v^2=x(x+1)$. For each $x$, their number is $1+(x(x+1)/p)$: it is one for zero, two for a nonzero <quadratic residue> and zero for a <quadratic nonresidue>. The total is therefore $p$ plus the desired sum.
Set $u=2x+1$ and $w=2v$. Since $2$ is invertible in this <finite field>, this is a <bijection> onto the solutions of
$$
u^2-w^2=1,\qquad (u-w)(u+w)=1.
$$
Choose any $r=u-w\ne0$. Then $u+w=r^{-1}$, uniquely determining $u=(r+r^{-1})/2$ and $w=(r^{-1}-r)/2$. There are exactly $p-1$ choices of $r$. Hence $p+\sum_x(x(x+1)/p)=p-1$, proving the correlation identity.
Back to article page