Dept Banner
Dept Banner

Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Tower-type bounds for Roth's theorem with popular differences

Yufei Zhao, MIT

Location:  Hill 705
Date & time: Monday, 16 April 2018 at 2:00PM - 3:00PM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530