Seminars & Colloquia Calendar

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.