Tower-type bounds for Roth's theorem with popular differences

DOI10.4171/JEMS/1271MaRDI QIDQ6056476zbMATH OpenOpenAlexWikidataFDO

Authors Jacob Fox, Huy-Tuan Pham, Yufei Zhao

Publication date 30 October 2023

Published in Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

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

zbMATH Keywords

arithmetic regularity lemmapopular differenceRoth's theorem

Mathematics Subject Classification ID

Ramsey theory (05D10) Arithmetic progressions (11B25) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: Green developed an arithmetic regularity lemma to prove a strengthening of Roth's theorem on arithmetic progressions in dense sets. It states that for every $epsilon>0$ there is some $N_0(epsilon)$ such that for every $Nge{N}_0(epsilon)$ and $Asubset[N]$ with $|A|=alphaN$, there is some nonzero $d$ such that $A$ contains at least $(alph{a}^3-epsilon)N$ three-term arithmetic progressions with common difference $d$. We prove that the minimum $N_0(epsilon)$ in Green's theorem is an exponential tower of 2s of height on the order of $log(1/epsilon)$. Both the lower and upper bounds are new. It shows that the tower-type bounds that arise from the use of a regularity lemma in this application are quantitatively necessary.

Review text

As a natural consequence of the findings in [\textit{V. Bergelson} et al., Invent. Math. 160, No. 2, 261--303 (2005; Zbl 1087.28007)], the following question was raised: Suppose that \( \alpha, \varepsilon > 0 \). Is it true that there is \( N_0(\alpha,\varepsilon ) \) such that if \( N \ge N_0(\alpha, \varepsilon ) \), and if \( A \subseteq \left\lbrace 1,\dots,N\right\rbrace \) has size \( \alpha N \), then there is some \( d \ne 0 \) such that \( A \) has at least \( (\alpha^3 - \varepsilon )N \) three-term arithmetic progressions with common difference \( d \)? \textit{B. Green} [Geom. Funct. Anal. 15, No. 2, 340--376 (2005; Zbl 1160.11314)] developed an arithmetic analogue of Szemerédi's regularity lemma and used it to give an affirmative answer to this question and it is known as Green's popular progression difference theorem. Green's proof uses the arithmetic regularity lemma and consequently shows that \( N_0 \) can be taken to be an exponential tower of twos of height \( \varepsilon^{-O(1)} \). In this paper, the main theorem determines the growth of the minimum \( N_0 \) for which Green's progression difference theorem holds, showing that it is an exponential tower of twos of height \( \Theta (\log (1/\varepsilon)). \) The authors prove that there exist absolute constants \( c, C > 0 \) such that for all \( 0 < \varepsilon < 1/2 \), \[ \text{tower}(c \log (1/\varepsilon)) \le N_0 (\varepsilon) \le \text{tower}(C \log (1/\varepsilon)), \] where \( \text{tower}(m) \) denotes an exponential tower of twos of height \( m. \)

Recommendations

• Popular progression differences in vector spaces
• Popular progression differences in vector spaces II
• On the structure of steps of three-term arithmetic progressions in a dense set of integers
• A note on maximal progression-free sets
• A new proof of Szemerédi's theorem
• On arithmetic structures in dense sets of integers
• A Hardy field extension of Szemerédi's theorem
• Arithmetic progressions of length three in subsets of a random set
• Szemerédi's theorem and problems on arithmetic progressions
• Improving Roth's theorem in the primes

Cites work

• A new proof of Szemerédi's theorem
• A note on Elkin's improvement of Behrend's construction
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
• A short proof of Gowers' lower bound for the regularity lemma
• A Szemerédi-type regularity lemma in abelian groups, with applications
• A tight lower bound for Szemerédi's regularity lemma
• A variant of the Corners theorem
• Additive combinatorics
• An arithmetic regularity lemma, an associated counting lemma, and applications
• An improved lower bound for arithmetic regularity
• Bounds for graph regularity and removal lemmas
• Dependent random choice
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• Integer sets containing no arithmetic progressions
• Integer Sets Containing No Arithmetic Progressions
• Logarithmic bounds for Roth's theorem via almost-periodicity
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Multiple recurrence and nilsequences (with an appendix by Imre Ruzsa)
• On certain other sets of integers
• On Certain Sets of Integers
• On Certain Sets of Positive Density
• On Roth's theorem on progressions
• On sets of integers containing k elements in arithmetic progression
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On triples in arithmetic progression
• Patterns without a popular difference
• Popular differences for corners in abelian groups
• Popular progression differences in vector spaces
• Popular progression differences in vector spaces II
• Roth's theorem on progressions revisited
• The difference between consecutive primes. II
• Triforce and corners

Cited in

(2)

• Triforce and corners
• Bounds in a popular multidimensional nonlinear Roth theorem

This page was built for publication: Tower-type bounds for Roth's theorem with popular differences

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