Yufei Zhao, Massachusetts Institute of Technology

Abstract

A famous theorem of Roth states that for any $alpha > 0$ and $n$ sufficiently large in terms of $alpha$, any subset of ${1, dots, n}$ with density $alpha$ contains a 3-term arithmetic progression. Green developed an arithmetic regularity lemma and used it to prove that not only is there one arithmetic progression, but in fact there is some integer $d > 0$ for which the density of 3-term arithmetic progressions with common difference $d$ is at least roughly what is expected in a random set with density $alpha$. That is, for every $epsilon > 0$, there is some $n(epsilon)$ such that for all $n > n(epsilon)$ and any subset $A$ of ${1, dots, n}$ with density $alpha$, there is some integer $d > 0$ for which the number of 3-term arithmetic progressions in $A$ with common difference $d$ is at least $(alpha^3-epsilon)n$. We prove that $n(epsilon)$ grows as an exponential tower of 2's of height on the order of $log(1/epsilon)$. We show that the same is true in any abelian group of odd order $n$. These results are the first applications of regularity lemmas for which the tower-type bounds are shown to be necessary.

Joint work with Jacob Fox and Huy Tuan Pham.