ACO The ACO Seminar (2017–2018)

Feb. 22, 3:30pm, Wean 8220
Yufei Zhao, MIT
Tower-type bounds for Roth's theorem with popular differences


A famous theorem of Roth states that for any α > 0 and n sufficiently large in terms of α, any subset of {1, ..., n} with density α 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 α. That is, for every ε > 0, there is some n(ε) such that for all n > n(ε) and any subset A of {1, ..., n} with density α, there is some integer d > 0 for which the number of 3-term arithmetic progressions in A with common difference d is at least (α3-ε)n. We prove that n(ε) grows as an exponential tower of 2's of height on the order of log(1/ε). 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.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.

Back to the ACO home page