Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Yufei Zhao MIT Title: Tower-type bounds for Roth's theorem with popular differences Abstract: 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. |