Square-difference sets, Paley cliques, and an exact external-defect variance identity

Definitions and mathematical statement

For an odd prime $p$, let $Q_p=\{x^2:x\in\mathbb F_p^*\}$ be the set of nonzero quadratic residues modulo $p$. Define \[ M(p)=\max\{|A|:A\subseteq\mathbb F_p, A-A\subseteq Q_p\cup\{0\}\}, \qquad A-A=\{a-b:a,b\in A\}. \] Thus the difference of every two distinct members, in each order, must be a nonzero square. The diagonal differences are zero and are explicitly exempted. This formulation removes any ambiguity about whether zero is called a quadratic residue.

The substantive case is $p\equiv1\pmod4$. Then $-1$ is a square, and the Paley graph on $\mathbb F_p$ has an undirected edge between $a$ and $b$ exactly when $a-b\in Q_p$. The quantity $M(p)$ is its clique number: the largest number of pairwise adjacent vertices. The problem asks how large this number can be, ideally determining its sharp dependence on $p$ or sharp uniform asymptotic bounds. No assumption that $A$ is a subgroup, an interval, or a set of residues of some fixed polynomial is imposed.

For completeness, when $p\equiv3\pmod4$, both $a-b$ and $b-a$ cannot be nonzero squares, so the same definition gives $M(p)=1$. This explains why the nontrivial extremal question concerns primes congruent to one modulo four. The problem involves pairwise additive differences, even though eligibility of a difference is multiplicative.

Short English statement

How large can a subset of a prime field be when every nonzero difference between its elements is a square?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001118 (AIM-COMBINATORICS-0243), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Recent trends in additive combinatorics, item 3.6. Original workshop question underlying AIM-COMBINATORICS-0243. https://aimath.org/WWN/additivecomb/additivecomb.pdf.