Erdős–Szemerédi theorem

The Erdős–Szemerédi theorem states that every finite set of integers has either a large sumset or a large product set: at least a constant multiple of its size raised to a fixed power greater than one.

Connect

Sumset: For sets A and B in an additive group, their sumset is the set of all sums a + b with a in A and b in B. The theorem measures how many distinct sums arise when the set is added to itself.
Paul Erdős: A Hungarian mathematician known for prolific collaboration and major contributions to combinatorics and number theory. He posed the sum-product problem with Szemerédi.
Arithmetic progression: A sequence of numbers with a constant difference between consecutive terms. Arithmetic progressions have small sumsets, illustrating how additive structure can suppress expansion.
Incidence bounds for sum-product problems: Estimates on point-line incidences used to bound the size of sumsets and product sets. Geometric incidence estimates yield quantitative versions of sum-product growth.
Product set: For sets A and B in a multiplicative structure, their product set contains all products ab with a in A and b in B. The theorem compares multiplicative growth with the sumset's growth.
Endre Szemerédi: A Hungarian mathematician whose work includes major results in combinatorics and number theory. He co-authored the problem that led to the theorem.
Geometric progression: A sequence of numbers with a constant ratio between consecutive terms. Geometric progressions have small product sets, the multiplicative counterpart to additive structure.
Expander graphs: Sparse graphs with strong connectivity properties, measured by rapid spreading of sets or spectral gaps. Sum-product growth can support expansion arguments in arithmetic and graph constructions.
Additive energy: The number of quadruples satisfying a₁ + a₂ = a₃ + a₄, often used to measure additive structure. Many repeated sums signal structure that can be traded against product-set growth.
Additive combinatorics: The study of additive structure in sets, using tools from combinatorics, number theory, and harmonic analysis. The theorem helped motivate a broader framework for comparing additive and multiplicative structure.