CMU Campus
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
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.

Date: Thursday, February 22, 2018
Time: 3:30 pm
Location: Wean Hall 8220
Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.