Long arithmetic progressions in sumsets: Thresholds and bounds

By Endre Szemerédi, Van H. Vu. 2005

47 citations recorded by the source corpus.

l∗A = {a1 + · · ·+ al|ai ∈ Ai, ai = aj}. Among the most well-known results in all of mathematics are Vinogradov’s theorem, which says that 3P (P is the set of primes) contains all sufficiently large odd numbers, and Waring’s conjecture (proved by Hilbert, Hardy and Littlewood, Hua, and many others), which asserts that for any given r, there is a number l such that l∗Nr (N denotes the set of rth powers) contains all sufficiently large positive integers (see [29] for an excellent exposition concerning these results). In recent years, a considerable amount of attention has been paid to the study of finite sumsets. Given a finite set A and a positive integer l, the natural analogue of Vinogadov-Waring results is to show that under proper conditions, the sumset lA (l∗A) contains a long arithmetic progression. Let us assume that A is a subset of the interval [n] = {1, . . . , n}, where n is a large positive integer. The concrete problem we would like to address is to estimate the minimum length of the longest arithmetic progression in lA (l∗A) as a function of l, n, and |A|. We denote this function by f(|A|, l, n) (f∗(|A|, l, n)), following the notation in [13]. Many estimates for f(|A|, l, n) have been discovered by Bourgain, Freiman, Halberstam, Green, Ruzsa, and Sarkozy (see Section 3), but most of these results focus on sets with very high density, namely |A| is close to n. Estimating f∗(|A|, l, n) seems much harder, and not much was known prior to our study.

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

View Paper: https://www.semanticscholar.org/paper/97370c5916e32a7828e77b08b4823bb38d8e1fb0

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 Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

The structure theory of set addition revisited (2012, methodology): “For example, Gowers himself used it to spectacularly improve the bounds in Szemerédi’s theorem; Szemerédi and Vu used it to investigate long arithmetic progressions in [SV06]; Tao and Vu used it to investigate random matrices in [TV07]; Schoen records many shorter consequences at the end of his pape”
Finite and infinite arithmetic progressions in sumsets (2006, result): “In special cases sharp results have been obtained, thanks to the works of several researchers, including Bourgain, Freiman, Halberstam, Ruzsa and Sárközy [2, 7, 6, 17].”