Additive Combinatorics

4.0 credits

This course introduces additive combinatorics, a field at the intersection of combinatorics, number theory, and theoretical computer science. We will study the structure of sets under addition, with emphasis on tools and results that have found striking applications in computer science and mathematics. Topics include sumset estimates and the Plünnecke-Ruzsa inequalities, the necessary Fourier analytic tools, Freiman's theorem on sets with small doubling, the Balog-Szemerédi-Gowers theorem, arithmetic progressions and Roth's theorem, the sum-product phenomenon, and Gowers uniformity norms. Applications in algorithms, complexity, and number theory will be discussed.