A sum-product estimate in finite fields, and applications

DOI10.1007/S00039-004-0451-1MaRDI QIDQ1889817zbMATH OpenOpenAlexWikidataFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(only showing first 100 items - show all)

• The sum-product theorem in Z_q with q arbitrary
• On the exponential sum-product problem
• A quantified version of Bourgain's sum-product estimate in \(\mathbb F_{p}\) for subsets of incomparable sizes
• On additive properties of product sets in an arbitrary finite field
• Generalized incidence theorems, homogeneous forms and sum-product estimates in finite fields
• On character sums with distances on the upper half plane over a finite field
• On the singularity probability of discrete random matrices
• Fourier methods and non degenerate polynomials
• Distinct spreads in vector spaces over finite fields
• Conditional expanding bounds for two-variable functions over arbitrary fields
• Group actions and geometric combinatorics in \(\mathbb{F}_{q}^{d}\)
• Cayley digraphs associated to arithmetic groups
• On the number of incidences between points and planes in three dimensions
• A modular Szemerédi-Trotter theorem for hyperbolas
• Algebraic methods in sum-product phenomena
• Sums and products along sparse graphs
• Quasi-periodic decompositions and the Kemperman structure theorem
• New bounds on exponential sums related to the Diffie-Hellman distributions
• A sum--product theorem in semi-simple commutative Banach algebras
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• On the Gowers norms of certain functions
• On incidences of lines in regular complexes
• Some multiplicative equations in finite fields
• New bounds for distance-type problems over prime fields
• The finite Littlewood problem in \(\mathbb{F}_p\)
• Improved estimates for polynomial Roth type theorems in finite fields
• Sparse affine-invariant linear codes are locally testable
• Distribution of the determinants of sums of matrices
• Extension theorems and a connection to the Erdős-Falconer distance problem over finite fields
• Discretized sum-product and Fourier decay in \(\mathbb{R}^n\)
• An isoperimetric inequality for Hamming balls and local expansion in hypercubes
• A point-conic incidence bound and applications over \(\mathbb{F}_p\)
• Incidences between Euclidean spaces over finite fields
• Dot-product sets and simplices over finite rings
• On the energy variant of the sum-product conjecture
• Extending Erdős-Beck's theorem to higher dimensions
• Bisectors and pinned distances
• On popular sums and differences for sets with small multiplicative doubling
• Some sum-product type estimates for two-variables over prime fields
• On the balanced upper chromatic number of finite projective planes
• Distribution of distances in positive characteristic
• Sum-product phenomena: \(\mathfrak{P}\)-adic case
• Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory
• Results on the Erdős-Falconer distance problem in \(\mathbb{Z}_q^d\) for odd \(q\)
• Finite field restriction estimates based on Kakeya maximal operator estimates
• Decomposition of subsets of finite fields
• Discretized sum-product estimates in matrix algebras
• Distance sets over arbitrary finite fields
• Differencing methods for Korobov-type exponential sums
• Bounds of trilinear and quadrilinear exponential sums
• A sum-product theorem in matrix rings over finite fields
• Three-point configurations determined by subsets of \({\mathbb{F}_q}^2\) via the Elekes-Sharir paradigm
• Product set estimates for non-commutative groups
• A sum-product estimate in algebraic division algebras
• The k-resultant modulus set problem on algebraic varieties over finite fields
• The generalized \(k\)-resultant modulus set problem in finite fields
• Some remarks on the asymmetric sum-product phenomenon
• On the quotient set of the distance set
• Embeddings of weighted graphs in Erdős-type settings
• Analogues of the Balog-Wooley decomposition for subsets of finite fields and character sums with convolutions
• Growth in \(\mathrm{SL}_3(\mathbb Z/p\mathbb Z)\).
• On distance sets and product sets in vector spaces over finite rings
• A product theorem in free groups.
• Another sum-product estimate in finite fields
• Exponential sum estimates over subgroups of \(\mathbb Z^*_q\), \(q\) arbitrary
• On the spectral gap for finitely-generated subgroups of \(\text{SU}(2)\)
• Exponential sum estimates in finite commutative rings and applications
• New results on expanders
• A Gauss sum estimate in arbitrary finite fields
• Sieving and expanders
• Conditional expanding bounds for two-variable functions over prime fields
• Additive patterns in multiplicative subgroups
• New sum-product type estimates over finite fields
• The number of occurrences of a fixed spread among \(n\) directions in vector spaces over finite fields
• Sum-product theorems in algebraic number fields
• Frames over finite fields: basic theory and equiangular lines in unitary geometry
• Some sum-product estimates in matrix rings over finite fields
• Working session: Thin groups and super-approximation. Abstracts from the working session held October 10--15, 2021 (hybrid meeting)
• On the number of dot product chains in finite fields and rings
• On two-variable expanders over finite rings
• On the sums of any k points in finite fields
• Unions of lines in F^n
• Incidence bounds for block designs
• Multiparameter projection theorems with applications to sums-products and finite point configurations in the Euclidean setting
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Probabilistic and asymptotic aspects of finite simple groups.
• Approximate groups and doubling metrics
• Sum-product estimates and multiplicative orders of \(\gamma \) and \(\gamma +\gamma ^{ - 1}\) in finite fields
• A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one
• Elementary methods for incidence problems in finite fields
• ALMOST ALL PRIMES HAVE A MULTIPLE OF SMALL HAMMING WEIGHT
• Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős-Falconer distance conjecture
• Growth in SL2 over finite fields
• An introduction to randomness extractors
• On sum of products and the Erdős distance problem over finite fields
• On the size of Kakeya sets in finite fields
• An explicit incidence theorem in F_p
• Expander graphs in pure and applied mathematics
• Stable group theory and approximate subgroups
• Areas of triangles and Beck's theorem in planes over 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)