A sum-product estimate in finite fields, and applications

DOI10.1007/S00039-004-0451-1zbMATH Open1145.11306arXivmath/0301343OpenAlexW1990524943WikidataQ57311539 ScholiaQ57311539MaRDI QIDQ1889817FDOQ1889817

Authors: Nets Hawk Katz, Jean Bourgain, Terence Tao 

Publication date: 13 December 2004

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Abstract: Let $A$ be a subset of a finite field $$ for some prime $q$. If $|F{|}^{d}elta<|A|<|F{|}^{1-delta}$ for some $delta>0$, then we prove the estimate $|A+A|+|A.A|geqc(delta)|A{|}^{1+eps}$ for some $eps=eps(delta)>0$. This is a finite field analogue of a result of Erdos and Szemeredi. We then use this estimate to prove a Szemeredi-Trotter type theorem in finite fields, and obtain a new estimate for the Erdos distance problem in finite fields, as well as the three-dimensional Kakeya problem in finite fields.

Full work available at URL: https://arxiv.org/abs/math/0301343

Recommendations

• Another sum-product estimate in finite fields
• Sum-product Estimates in Finite Fields via Kloosterman Sums
• On sum of products and the Erdős distance problem over finite fields
• An improved sum-product estimate for general finite fields
• The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30)

Cited In (only showing first 100 items - show all)

• Distinct distances with \(\ell_p\) metrics
• Extension theorems and a connection to the Erdős-Falconer distance problem over finite fields
• Bounds of trilinear and quadrilinear exponential sums
• The number of occurrences of a fixed spread among \(n\) directions in vector spaces over finite fields
• A sum-product theorem in matrix rings over finite fields
• New results on expanders
• On the generalized Erdős-Falconer distance problems over finite fields
• Distinct distances in the complex plane
• The sum-product theorem in \(\mathbb Z_q\) with \(q\) arbitrary
• Probabilistic and asymptotic aspects of finite simple groups.
• On the sum product estimates and two variables expanders
• Sum-product theorem and exponential sum estimates in residue classes with modulus involving few prime factors
• Products of differences over arbitrary finite fields
• The solvability of norm, bilinear and quadratic equations over finite fields via spectra of graphs
• On sum-product representation in \(\mathbb Z_q\)
• Distinct distances between points and lines in \(\mathbb{F}_q^2\)
• Distinct distances on regular varieties over finite fields
• An improved bound on the Hausdorff dimension of Besicovitch sets in \(\mathbb {R}^3\)
• On sum-sets and product-sets of complex numbers
• Discretized sum-product estimates in matrix algebras
• On the structure of distance sets over prime fields
• Additive patterns in multiplicative subgroups
• Incidence bounds for block designs
• New bounds on exponential sums related to the Diffie-Hellman distributions
• Sum-product theorems and exponential sum bounds in residue classes for general modulus
• Four-variable expanders over the prime fields
• Elementary methods for incidence problems in finite fields
• ON THE TWO-PARAMETER ERDŐS–FALCONER DISTANCE PROBLEM IN FINITE FIELDS
• Exponential sum estimates over subgroups of \(\mathbb Z^*_q\), \(q\) arbitrary
• Quasi-periodic decompositions and the Kemperman structure theorem
• Distinct distances on hyperbolic surfaces
• Stronger sum-product inequalities for small sets
• Sets with many pairs of orthogonal vectors over finite fields
• Cayley digraphs associated to arithmetic groups
• Fourier methods and non degenerate polynomials
• An appreciation of Jean Bourgain’s work
• Multiplicative energy of shifted subgroups and bounds on exponential sums with trinomials in finite fields
• From Apollonius to Zaremba: local-global phenomena in thin orbits
• A two-parameter finite field Erdős-Falconer distance problem
• A note on conditional expanders over prime fields
• New results for the growth of sets of real numbers
• A sum-product estimate in algebraic division algebras
• On the number of incidences between points and planes in three dimensions
• Sum-product theorems in algebraic number fields
• A new bound for the Erdős distinct distances problem in the plane over prime fields
• Expanders on matrices over a finite chain ring, I
• Expanders on Matrices over a Finite Chain Ring, II
• On rich lines in grids
• On the exponential sum-product problem
• On the sums of any \(k\) points in finite fields
• Conditional expanding bounds for two-variable functions over arbitrary fields
• On the energy variant of the sum-product conjecture
• Sieving and expanders
• Some multiplicative equations in finite fields
• Algebraic methods in sum-product phenomena
• Incidences between points and generalized spheres over finite fields and related problems
• Distinct spreads in vector spaces over finite fields
• On a Furstenberg-Katznelson-Weiss type theorem over finite fields
• The finite Littlewood problem in \(\mathbb{F}_p\)
• On asymptotic formulae in some sum-product questions
• A Gauss sum estimate in arbitrary finite fields
• Approximate groups and doubling metrics
• Growth in SL2 over finite fields
• A modular Szemerédi-Trotter theorem for hyperbolas
• New sum-product type estimates over finite fields
• Sums and products in finite fields: an integral geometric viewpoint
• A NEW SUM–PRODUCT ESTIMATE IN PRIME FIELDS
• Finite field restriction estimates based on Kakeya maximal operator estimates
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Conditional expanding bounds for two-variable functions over prime fields
• On three-variable expanders over finite fields
• Sum-product Estimates in Finite Fields via Kloosterman Sums
• Expansion and random walks in \(\text{SL}_d(\mathbb{Z}/p^n\mathbb{Z})\). II.
• On point-line incidences in vector spaces over finite fields
• Expansion and random walks in \(\text{SL}_d(\mathbb{Z}/p^n\mathbb{Z})\). I.
• Areas of triangles and Beck's theorem in planes over finite fields
• On configurations where the Loomis-Whitney inequality is nearly sharp and applications to the Furstenberg set problem
• On the elliptic curve analogue of the sum-product problem
• Pinned distance sets, \(k\)-simplices, Wolff's exponent in finite fields and sum-product estimates
• Sums and products along sparse graphs
• Heegaard genus and property τ for hyperbolic 3-manifolds
• Stable group theory and approximate subgroups
• Sets with integral distances in finite fields
• The equation \(x_1x_2=x_3x_4+\lambda \) in fields of prime order and applications
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• On sums and products in \(\mathbb C[x]\)
• Averages in vector spaces over finite fields
• Growth in solvable subgroups of \(\mathrm{GL}_r(\mathbb Z/p\mathbb Z)\).
• Growth in finite simple groups of Lie type
• A slight improvement to Garaev's sum product estimate
• Ubiquity of simplices in subsets of vector spaces over finite fields
• On distance sets and product sets in vector spaces over finite rings
• On self-similar sets with overlaps and inverse theorems for entropy
• The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields
• Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős-Falconer distance conjecture
• Sum-product phenomena: \(\mathfrak{P}\)-adic case
• New results on sum-product type growth over fields
• Group actions and geometric combinatorics in \(\mathbb{F}_{q}^{d}\)
• Distance sets of two subsets of vector spaces over finite fields
• Fourier analysis and expanding phenomena in finite fields

This page was built for publication: A sum-product estimate in finite fields, and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1889817)