A Delsarte Linear Programming Approach to the Erdős–Falconer Distance Problem over Finite Fields

Tao Zhang · 2026

Read A Delsarte Linear Programming Approach to the Erdős–Falconer Distance Problem over Finite Fields by Tao Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29965.txt.

Introduction

Tao Zhang attacks the Erdős–Falconer distance problem over finite fields. Finite fields are number systems with finitely many elements. The problem asks how large a point set must be. Beyond some size, its pairwise distances should cover many field values. Earlier work by Iosevich and Rudnev set such a threshold for general sets. Zhang lowers that threshold in even dimensions, for every even dimension at least four.

His tool is the Delsarte linear programming method from combinatorics. He builds it on the level sets of a quadratic form, which plays the role of squared distance in this setting. He analyzes the needed eigenvalues through Gauss sums and Kloosterman sums. Then he constructs a valid solution to the linear program. The result holds uniformly for every non-degenerate quadratic form. Sets above the new bound yield a positive proportion of all possible distances.

Catalog record

CREATORTao Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.29965

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Delsarte Linear Programming Approach to the Erdős–Falconer Distance Problem over Finite Fields Tao Zhang Abstract We introduce a Delsarte linear programming approach to the finite field Erdős–Falconer distance problem. Let q q be an odd prime power, let n n be even, and let Q Q be a non-degenerate quadratic form on 𝔽 q n \mathbb{F}_{q}^{n} . For E ⊂ 𝔽 q n E\subset\mathbb{F}_{q}^{n} , define Δ Q ( E ) = { Q ( x − y ) : x , y ∈ E } . \Delta_{Q}(E)=\{Q(x-y):\ x,y\in E\}. We prove that, for every fixed 0 < α < 1 2 0<\alpha<\frac{1}{2} , there exist constants C α > 0 C_{\alpha}>0 and q α q_{\alpha} such that if q ≥ q α q\geq q_{\alpha} and | E | ≥ C α ​ q n 2 + 1 3 , |E|\geq C_{\alpha}q^{\frac{n}{2}+\frac{1}{3}}, then | Δ Q ​ ( E ) | > 1 + α ⁡ ( q − 1 ) . |\Delta_{Q}(E)|>1+\alpha(q-1). In particular, Δ Q ​ ( E ) \Delta_{Q}(E) contains a positive proportion of the elements of 𝔽 q \mathbb{F}_{q} , and hence | Δ Q ​ ( E ) | ≫ q |\Delta_{Q}(E)|\gg q . Our result applies uniformly to all non-degenerate quadratic forms in even-dimensional finite field vector spaces. In the Euclidean case Q ⁡ ( x ) = x 1 2 + ⋯ + x n 2 , Q(x)=x_{1}^{2}+\cdots+x_{n}^{2}, it improves, for every even n ≥ 4 n\geq 4 over arbitrary finite fields, the general exponent n + 1 2 \frac{n+1}{2} obtained by Iosevich and Rudnev to n 2 + 1 3 . \frac{n}{2}+\frac{1}{3}. The proof is based on the association scheme arising from the level sets of Q Q . By analyzing the corresponding eigenvalues through Gauss sums and Kloosterman sums, we construct a suitable feasible solution to the Delsarte linear program. This provides a new algebraic-combinatorial method for obtaining distance set estimates over finite fields. Keywords : Erdős–Falconer Distance Problem, Delsarte linear programming, Kloosterman sum. AMS subject classifications : 52C10, 11L40. † † footnotetext: E-mail addresses: [email protected] (T. Zhang). 1 Introduction For a finite set E\subset\mathbb{R}^{n} , the classical Erdős distance problem asks how small the number of distinct distances determined by E can be in terms of |E| . A natural continuous analogue is the Falconer distance problem. For a compact set E\subset\mathbb{R}^{n} , define its Euclidean distance set by \Delta_{\mathbb{R}^{n}}(E)=\left\{\sum_{i=1}^{n}(x_{i}-y_{i})^{2}:\ x,y\in E\right\}. The Falconer conjecture asserts that if \dim_{H}(E)>\frac{n}{2}, then \Delta_{\mathbb{R}^{n}}(E) has positive Lebesgue measure. This threshold is expected to be sharp. Substantial progress has been made on this problem. In the plane, Guth, Iosevich, Ou and Wang [ 9 ] proved that |\Delta_{\mathbb{R}^{2}}(E)|>0 whenever \dim_{H}(E)>\frac{5}{4}. In higher dimensions, Du, Ou, Ren and Zhang [ 7 ] showed that for n\geq 3 , the distance set has positive Lebesgue measure provided \dim_{H}(E)>\frac{n}{2}+\frac{1}{4}-\frac{1}{8n+4}. These results illustrate the depth of the distance problem and its close connection with harmonic analysis, geometric measure theory, and incidence geometry. Finite field analogues of classical problems in harmonic analysis, geometric measure theory, and combinatorics have attracted considerable attention in recent years. On the one hand, the discrete setting often makes the underlying mechanisms more transparent; on the other hand, finite fields introduce new arithmetic phenomena that have no direct analogue over the real numbers. We refer the reader to [ 2 , 11 , 16 , 22 ] and the references therein for related developments. In this paper, we study the finite field analogue of the Erdős–Falconer distance problem. Let \mathbb{F}_{q} be a finite field with q elements, where q is an odd prime power, and let \mathbb{F}_{q}^{n} denote the n -dimensional vector space over \mathbb{F}_{q} . For x=(x_{1},\dots,x_{n})\in\mathbb{F}_{q}^{n} , define d(x)=\sum_{i=1}^{n}x_{i}^{2}. For a set E\subset\mathbb{F}_{q}^{n} , its distance set is \Delta_{d}(E)=\{d(x-y):\ x,y\in E\}. The finite field Erdős–Falconer distance problem asks for the smallest exponent \alpha_{n} such that if |E|\gg q^{\alpha_{n}} , then |\Delta_{d}(E)|\gg q. A foundational result of Iosevich and Rudnev [ 11 ] , proved via Fourier analytic methods, gives \alpha_{n}\leq\frac{n+1}{2}. This bound is sharp in odd dimensions [ 10 ] . In even dimensions, however, the situation is much more delicate. The known examples only imply the lower bound \alpha_{n}\geq\frac{n}{2}, and it has been conjectured that this lower bound is the correct threshold for all even n . Despite considerable effort [ 4 , 5 , 8 , 15 , 13 , 14 , 12 , 17 , 18 , 19 ] , the conjecture in even dimensions remains open. In dimension 2 , the best known exponent over arbitrary finite fields is \frac{4}{3} [ 1 , 4 ] , while over prime fields the exponent has been improved to \frac{5}{4} [ 17 ] . In dimension 4 , Pham and Xue [ 20 ] recently improved the exponent over prime fields from \frac{5}{2} to \frac{77}{31} . These developments show that any improvement over the general exponent \frac{n+1}{2} , especially uniformly in all even dimensions and over arbitrary finite fields, is highly nontrivial. The main purpose of this paper is to establish such a uniform improvement. Moreover, instead of restricting ourselves to the standard Euclidean quadratic form d(x) , we work in a more general setting. Let Q(x)=x^{T}Ax be a non-degenerate quadratic form on \mathbb{F}_{q}^{2m} , where A is symmetric and invertible. For E\subset\mathbb{F}_{q}^{2m} , define \Delta_{Q}(E)=\{Q(x-y):\ x,y\in E\}. Our main theorem shows that, for every non-degenerate quadratic form in even dimension, a set of size q^{m+\frac{1}{3}} already determines a positive proportion of all possible distances. Theorem 1.1 . Fix 0<\alpha<\frac{1}{2} . There exist constants C_{\alpha}>0 and q_{\alpha} such that, for every odd prime power q\geq q_{\alpha} , every integer m\geq 1 , every non-degenerate quadratic form Q on \mathbb{F}_{q}^{2m} , and every set E\subset\mathbb{F}_{q}^{2m} with |E|\geq C_{\alpha}q^{m+\frac{1}{3}}, we have |\Delta_{Q}(E)|>1+\alpha(q-1). Thus the distance set contains more than an arbitrary fixed proportion \alpha<\frac{1}{2} of the nonzero field elements, up to the additional possible value 0 . In particular, Theorem 1.1 immediately implies the following consequence. Corollary 1.2 . Let E\subset\mathbb{F}_{q}^{2m} . If |E|\geq Cq^{m+\frac{1}{3}} for a sufficiently large constant C , then |\Delta_{Q}(E)|\gg q. In particular, for the standard quadratic form d(x)=\sum_{i=1}^{2m}x_{i}^{2}, if E\subset\mathbb{F}_{q}^{2m} satisfies |E|\geq Cq^{m+\frac{1}{3}}, then |\Delta_{d}(E)|\gg q. In terms of the ambient dimension n=2m , our result gives the exponent \frac{n}{2}+\frac{1}{3} for all even dimensions. This improves the general exponent \frac{n+1}{2} of Iosevich and Rudnev [ 11 ] by \frac{1}{6} in the exponent. In dimension 2 , it recovers the best known exponent \frac{4}{3} over arbitrary finite fields. In every even dimension n\geq 4 , it gives a genuine improvement over the previously available general bound. In particular, in dimension 4 , our exponent is \frac{7}{3} , improving upon the exponent \frac{5}{2} over arbitrary finite fields and also strengthening the recent prime-field exponent \frac{77}{31} of [ 20 ] . The proof is based on the Delsarte linear programming method, originally introduced in Delsarte’s algebraic approach to association schemes in coding theory [ 6 ] . This approach brings tools from algebraic combinatorics into the finite field distance problem and differs from the Fourier analytic and incidence-geometric methods that have traditionally been used in this area. More precisely, we analyze the association scheme naturally induced by the level sets of

Read the complete text