On the size of k-fold sum and product sets of integers

By Jean Bourgain, Mei-Chu Chang. 2003

67 citations recorded by the source corpus.

We prove the following theorem: for all positive integers $b$ there exists a positive integer $k$, such that for every finite set $A$ of integers with cardinality $|A| > 1$, we have either $$ |A + ... + A| \geq |A|^b$$ or $$ |A \cdot ... \cdot A| \geq |A|^b$$ where $A + ... + A$ and $A \cdot ... \cdot A$ are the collections of $k$-fold sums and products of elements of $A$ respectively. This is progress towards a conjecture of Erdos and Szemeredi on sum and product sets.

Subfields: Computer Vision and Pattern Recognition, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/12fe69829c5512c84ee6425c7c0a705b90a17ce6

How researchers see this paper

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

In Computer Vision and Pattern Recognition

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

COMPRESSIONS, CONVEX GEOMETRY AND THE FREIMAN–BILU THEOREM (2005, background): “…a remarkable result of Freiman and Bilu [1, 2, 6], which shows that given any finite subset A of a torsion-free abelian group with σ [A] = K and given any ε > 0, one can find a progression P ′ with dimension at most log2 K + ε and size at most |A| such that |A ∩ P ′| exp(− exp(CεKCε ))|A|, where…”
New sum-product type estimates over finite fields (2014, background): “et us write this statement in shorthand as (11) |AA| . |A| ⇒ |A +A| & |A|2. The question is open for any ﬁeld but rationals, for it has been resolved in the integer setting by Bourgain and Chang, [2]. This furthered an earlier paper by Chang, [6], which showed that |A+A| & |A|2, given that |”
NEW RESULTS ON SUM‐PRODUCT TYPE GROWTH OVER FIELDS (2017, background): “Changing the notation Sj to S and noting that 2 i+jηj ≥ 2 12 i+j concludes the proof of Lemma 41.”
On a conjecture of Marton (2023, result): “This generalizes a well-known result of Bourgain and Chang [ 2], who established this when A is a set of integers.”