Arithmetic Regularity Lemmas

Szemeredi's regularity lemma is an indispensible tool in graph theory. It is often described as giving a "structure theorem for all graphs". I will describe a result, or rather a hierarchy of results, which does the same with "subsets of abelian groups" in place of "graphs". I will talk about applications of this result, such as (i) If a subset of {1,...,N} is almost sum-free (meaning that it has few solutions to x + y = z) then it may be expressed as a union of a genuinely sum-free set together with a small set; (ii) (Bergelson-Host-Kra conjecture) Fix alpha, epsilon. Let A be a subset of {1,...,N} with density alpha, where N is sufficiently large as a function of alpha and epsilon. Then there is some d such that A contains at least (alpha^3 - epsilon) N three-term progressions with common difference d, and some d' such that A contains at least (alpha^4 - epsilon) N four-term progressions with common difference d'. The analogue of this result fails for progressions of length five and longer. Some of this work is joint with T. Tao.

Ben Green, Clay Institute, University of Bristol, and M.I.T.

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube