Quadratic Legendre-symbol correlation
ID: quadratic-legendre-symbol-correlation
For every odd prime , the Legendre symbol correlation satisfiesThe small negative value measures an exact dependence between neighboring square tests; it is not obtained by treating them as independent.
Count the pairs satisfying . For each , their number is : it is one for zero, two for a nonzero quadratic residue and zero for a quadratic nonresidue. The total is therefore plus the desired sum.
Set and . Since is invertible in this finite field, this is a bijection onto the solutions ofChoose any . Then , uniquely determining and . There are exactly choices of . Hence , proving the correlation identity.
New to topics? Read the docs here!