A sum-product estimate in finite fields, and applications

By Jean Bourgain, Nets Hawk Katz, Terence Tao. 2003

548 citations recorded by the source corpus.

AbstractLet A be a subset of a finite field $$ F := \mathbf{Z}/q\mathbf{Z} $$ for some prime q. If $$ |F|^{\delta} < |A| < |F|^{1-\delta} $$ for some δ > 0, then we prove the estimate $$ |A + A| + |A \cdot A| \geq c(\delta)|A|^{1+\varepsilon} $$ for some ε = ε(δ) > 0. This is a finite field analogue of a result of [ErS]. We then use this estimate to prove a Szemerédi-Trotter type theorem in finite fields, and obtain a new estimate for the Erdös distance problem in finite fields, as well as the three-dimensional Kakeya problem in finite fields.

Subfields: Algebra and Number Theory, Applied Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/f856b0efcb223daa4789d039d3ef4e5d7174e197

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Applied Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Growth Estimates in Positive Characteristic via Collisions (2015, methodology): “They yield a considerable improvement to the state of the art, that arose from a series of questions and estimates by Bourgain, Katz, and Tao [6] and further work, e.”
On the singularity probability of discrete random matrices (2009, result): “1, for example proving a sum-product result for the complex numbers and proving a SzemerédiTrotter-type result for the complex numbers, where the applications follow from the analogous results for Z/Q where Q is a prime (see [3]).”
Sum–product estimates for rational functions (2010, methodology): “Lemma 11 (Szemerédi–Trotter theorem for Fp [4]).”
Linear degree extractors and the inapproximability of max clique and chromatic number (2006, unknown): “P= Our constructions rely on recent results in additive number theory and extractors by Bourgain-Katz-Tao [11], BarakImpagliazzo-Wigderson [5], Barak-Kindler-Shaltiel-Sudakov-Wigderson [6], and Raz [36].”
Affine linear sieve, expanders, and sum-product (2010, methodology): “(3.54) According to (3.53) and the analysis leading to (3.33) which uses the expander property, we have that ∑ y∈O w(y,x)≤L y∈W(Z/pZ) 1 ∑ y∈W(Z/pZ) ( X |Op| + X τ ) X p + pdimG−1Xτ .”
On the spectral gap for finitely-generated subgroups of SU(2) (2007, methodology): “Whereas Helfgott used the sum-product theorem in F p, due to Bourgain, Katz, and Tao [ 4 ], our proof builds crucially on the metrical counterpart, given by the “discretized ring conjecture” (due to Katz and Tao [18]), proved by Bourgain [2].”
Stable group theory and approximate subgroups (2009, unknown): “1 of [5] in the sum-product setting, as well as the theorem of [20] for subsets of SL2(Fp), can be put in the framework of Proposition 5.”
Estimates for the Number of Sums and Products and for Exponential Sums in Fields of Prime Order (2006, methodology): “For the proof, following [10] and [5], we associate with a set A ⊂ F the set I(A) := {a1(a2 − a3) + a4(a5 − a6) : a1, .”