Maximum number of unit distances among $p$ points in $\mathbb{F}_p^2$ (Croot-Lev Problem 5.4, Tao)
Statement
For a prime $p$ and $A\subseteq\mathbb{F}_p\times\mathbb{F}_p$ with $|A|=p$, consider the number of ordered pairs $\big((x_1,y_1),(x_2,y_2)\big)\in A\times A$ with $(x_1-x_2)^2+(y_1-y_2)^2=1$ (unit distances in the finite plane, at the critical size $|A|=p=\sqrt{|\mathbb{F}_p^2|}$). How large can this count be as a function of $p$?
Acceptance. ADVANCES: exact maxima $f(p)$ for small primes $p$ (each certified by an optimal $p$-point set plus a matching ILP dual / exhaustive bound), tabulated across $p\equiv1$ and $p\equiv3\pmod4$, pinning whether $f(p)=\Theta(p)$ or grows like $p^{1+c}$; or an improved upper bound below $p^{3/2}$ (resp. a lower bound above $2p$) via a spectral/energy argument with a checkable certificate. FULLY RESOLVES: the exact asymptotic order of $f(p)$ (matching upper and lower bounds). Provide the extremal sets and the verification/solver scripts.
Background
Problem 5.4 of E. Croot & V. Lev, 'Open problems in additive combinatorics' (CRM Proc. Lecture Notes 43, AMS 2007, pp. 207-233), contributed by T. Tao. The unit-distance graph on $\mathbb{F}_p^2$ has been studied by Iosevich-Rudnev and others in the regime $|A|\gg p$ (Erdős-Falconer-type problems), but the exact extremal count at the CRITICAL size $|A|=p$ is neglected. Best-known bounds (elementary, from the survey): a coordinate line gives $\ge 2p$ unit-distance ordered pairs; a double-count gives $\le p^{3/2}$; the gap between $2p$ and $p^{3/2}$ is wide open. General finite-plane unit-distance upper bounds — Zahl ($O(n^{3/2})$ when $-1$ is a non-square), Rudnev ($O(n^{8/5})$ in general) — do not pin the critical case. The geometry differs for $p\equiv1$ vs $p\equiv3\pmod 4$ (whether $-1$ is a quadratic residue, i.e. whether the 'circle' $x^2+y^2=1$ splits). An attacker needs: (i) exact ILP / heuristic search over $p$-subsets of $\mathbb{F}_p^2$ to tabulate the maximum $f(p)$ for small $p$ of each residue class; (ii) the fact that the unit-distance graph is a Cayley graph on $\mathbb{F}_p^2$ with connection set $\{x^2+y^2=1\}$, whose eigenvalues are Kloosterman/Salié sums — combining the expander-mixing (spectral) bound with the extremal configurations to fix the exponent.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Croot & Lev, Open problems in additive combinatorics (Problem 5.4, contributed by Tao) | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.