Recent trends III: Subsets of the integers without three term arithmetic progressions

22 Apr 2024

Let $A\subset \lbrace 1,\ldots, N\rbrace $ be a subset without non-trivial 3-term arithmetic progressions (APs), i.e., such that the equation $a+b=2c$ only has solutions for $a,b,c\in A$ if $a=b=c$. What is the maximum size $r_3(N):=\max_{A\subset \lbrace 1,\ldots,N\rbrace \text{ without 3 APs}}(|A|)$ that we can have? This question and many similar ones have driven the development of an important part of additive combinatorics during the last century. In this post, we will review the key milestones regarding these developments. In the end, we will present the breakthrough result of 2023 that finally settles (of course, up to some constants) the correct order of magnitude of such maximum size.

In 1921 Baudet asked whether for any integers $r,k\ge 2$ there exists $N=N(r,k)$ such that if the numbers $\lbrace 1,\ldots, N\rbrace $ are colored with $r$ colors, then there is a monochromatic arithmetic progression of length $k$. Van der Waerden [14] answered affirmatively this question in 1927 by providing a result that is now considered a foundational result of Ramsey theory. Note that any non-trivial bound on $r_3(N)$ translates to a bound for $N(r,3)$ as any partition of $\lbrace 1,\ldots, N \rbrace $ into $r$ colors forces at least one such partition to have a density at least $N/r$.

Ten years later, in 1936, Erdős and Turán proved that $r_3(N)/N\le 3/8+\epsilon$ for sufficiently large $N$ depending on $\epsilon$, see [7]. They also conjectured that $r_3(N)=o(N)$. In 1946 Behrend [2] proved the lower bound

\[%\label{eq:be} r_3(N)/N \ge e^{-O(\log N)^{1/2}} \tag{1}\]

by explicitly building a large set lacking 3 APs. This function tends quite fast to 0. It wasn’t until 1953 when Roth [11] proved Erdős and Turán’s conjecture. Moreover, he proved the estimate

\[%\label{eq:roth} r_3(N)/N \le O\left(\frac{1}{\log\log N}\right) = e^{-O(\log\log\log N)}.\tag{2}\]

The work of Roth is especially important because he successfully introduced a technique known as the density increment argument for counting arithmetic progressions. This technique consists of 2 steps:

1. If a set $A\subset \lbrace 1,\ldots,N\rbrace $ does not contain 3 APs, then the value of

   \[\Lambda_3(A):=\mathbb{E}_{x,r\in \lbrace 1,\ldots,N\rbrace } 1_A(x)1_A(x+r)1_A(x+2r),\]

   where $1_A$ is the characteristic function of $A$, differs significantly from the random expected value, $(|A|/N)^3$. This implies that (after embedding $A$ into some $\mathbb{Z}/p\mathbb{Z}$ for some appropriately chosen prime $p$) $1_A(x)-|A|/N$ correlates non-trivially with a character defined on $\mathbb{Z}/p\mathbb{Z}$.

2. From the correlation proved in the previous point, it follows that inside $\mathbb{Z}/p\mathbb{Z}$ there exists a large arithmetic progression $P\subset \mathbb{Z}/p\mathbb{Z}$ such that $\frac{|A\cap P|}{|P|}\ge \frac{|A|}{N}+\epsilon\left(\frac{|A|}{N}\right)$ for some positive function $\epsilon(\cdot)$.

Thus, if the density of $A$ is larger than the right-hand side of (2) (for $N$ large enough) we could iterate the previous process until we get the contradiction that $\frac{|A\cap P|}{|P|}>1$.

This fantastic result settles Erdős and Turán’s conjecture, but note that there is still a large gap between the upper (2) and lower (1) bounds for $r_3(N)$. In 1977, Erdős [6] posed the question of whether any subset $A\subset \mathbb{N}$ such that

\[\sum_{a\in A} \frac{1}{a} = \infty\]

must contain arithmetic progressions of any fixed length $k$ (and offered a reward of 3000 USD for its solution). The first non-trivial case is $k=3,$ and not even for that case a solution was known. Observe that the set of prime numbers, whose asymptotic density is 0, does satisfy that the sum of its inverses diverges. Thus, a positive answer to Erdős’s question implies that there are progressions of arbitrary length in the primes.

In the years following 1977, there were many advances in improving the bound of Roth (2). These were due to Heath-Brown [9] (1987), Szemerédi [13] (1990), and Bourgain [5] (1999). One of the main ideas behind these results consists in improving step 1 described above: Instead of using a correlation with a single character to prove a density increment, they use correlations with many characters at once. These advancements kept improving the bound of Roth and were getting closer to the solution of the case $k=3$ of Erdős’s question. In 2011, Sanders [12] proved that

\[r_3(N)/N \le O\left(\frac{(\log\log N )^5}{\log N}\right).\]

Note that if the logarithm in the denominator of the previous formula were instead $\log(N)^{1 + \epsilon}$ it would settle the case $k=3$ of Erdős’s question. We remark that the case of $A$ being the prime numbers had been known since 2004 due to the work of Green and Tao [8]. However, their proof relied heavily on number theoretic properties of the prime numbers. Thus, it did not generalize to arbitrary subsets.

The general solution for the case $k=3$ of Erdős’s question was finally given in 2020 by Bloom and Sisask [4], who proved that

\[r_3(N)/N\le O\left(\frac{1}{(\log N)^{1+c}} \right)\]

for some positive constant $c>0$. The techniques used in their proof are heirs of those of Roth, i.e., making density increment arguments via Fourier analysis. They managed to adapt the arguments of Bateman and Kats [1] to the setting of intervals and developed new ideas to translate the information from frequency space to physical space.

Once Erdős’s question for $k=3$ is settled, we turn to our original question: what is the correct order of magnitude of $r_3(N)$? Note that Bloom and Sisask’s bound together with Behrend’s construction yield

\[%\label{eq:be+bs} e^{-O(\log N)^{1/2}} \ll \frac{r_3(N)}{N} \ll e^{-O(\log\log N)}.\tag{3}\]

Hence, it remains unclear whether the correct order of magnitude of $r_3(N)$ is closer to the left-hand side or the right-hand side of (3).

The answer appeared in 2023 thanks to Kelley and Meka [10], who proved that the correct bound is (in a sense) the one of Behrend. More precisely, from their arguments Bloom and Sisask deduced that

\[\frac{r_3(N)}{N} \ll e^{-O(\log N)^{1/11}}\]

as shown in their exposition of the work of Kelley and Meka [3]. This exposition is written in a language familiar to additive combinatorialists. The key idea that we want to mention to conclude this post is that while previous works have focused on pushing the methods in the frequency space, i.e., working with the Fourier transform, the work of Kelley and Meka is much more focused on the physical space. Nevertheless, they prove a density increment statement much stronger than the ones we knew until their work appeared.

---

References

[1] M. Bateman, N. H. Katz, New bounds on cap sets, J. Amer. Math. Soc. 25, 2 (2012), 585–613.

[2] F. A. Behrend On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. U. S. A. 32 (1946): 331–332.

[3] T. F. Bloom, O. Sisask, The Kelley–Meka bounds for sets free of three-term arithmetic progressions, submitted arXiv:2302.07211

[4] T. F. Bloom, O. Sisask, Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions, submitted arXiv:2007.03528

[5] J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal. 9 (1999),968–984. MR 1726234. Zbl 0959.11004. doi: 10.1007/s000390050105.

[6] P. Erdős, Problems in number theory and combinatorics, Proceedings of the Sixth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1976), Congress. Numer. XVIII , pp. 35–58, Utilitas Math., Winnipeg, Man., 1977 MR80e:10005; Zentralblatt 471.10002. Available here.

[7] P. Erdős, P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264; Zentralblatt 15,152. Available here.

[8] B. Green, T. Tao, The primes contain arbitrarily long arithmetic progressions, (2004) Annals of Mathematics. 167 (2): 481–547.

[9] D. R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. 35 (1987), 385–394. MR 0889362. Zbl 0589.10062.doi: 10.1112/jlms/s2-35.3.385.

[10] Z. Kelley, R. Meka, Strong bounds for 3-progressions, arXiv:2302.05537

[11] K. Roth, On certain sets of integers, Journal of the London Mathematical Society. 28 (1): 104–109. doi:10.1112/jlms/s1-28.1.104

[12] T. Sanders, On Roth’s theorem on progressions, Ann. of Math. (2) 174, 1 (2011), 619–636.

[13] E. Szemerédi, Integer sets containing no arithmetic progressions, Acta Math. Hungar. 56 (1990), 155–158. MR 1100788. Zbl 0721.11007. doi:10.1007/BF01903717.

[14] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, (1927), Nieuw. Arch. Wisk. 15: 212–216. Available here.

---

The author of this post, Diego González-Sánchez, is a research fellow at the Alfréd Rényi Institute of Mathematics.