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.
For an odd prime , the number of integers such that both and are quadratic residues modulo isFor example, modulo the quadratic residues are . The qualifying pairs are and , giving .
Write for the Legendre symbol. On the specified range neither input is zero, so the indicator of the required event is . Expand and sum. The complete Legendre-symbol sum givesThe quadratic Legendre-symbol correlation gives : extending to the full finite field only adds the zero terms at . Thus the count is . The first supplementary law for quadratic reciprocity identifies and completes the formula.
Articles by others on the same topic
There are currently no matching articles.