Additive combinatorics (Spring 2017)

Lecturer: Wojciech Samotij
e-mail: samotij(at)
Course #: 0366-5063-01
Monday, 16:10–19:00
Ornstein 110

Office hours:
Wednesday, 15:00–16:00
Schreiber 002

Course description

Among topics that will be covered in the class are the following: discrete Fourier analysis over finite abelian groups; arithmetic progressions in the integers and finite abelian groups (Szemerédi's theorem); Sidon sets; sum-free sets in the integers and finite abelian groups; sum-product estimates (the Erdős–Szemerédi conjecture); the Littlewood–Offord problem; the structure of sets with a small sumset

There will be no final exam. Instead, the grade will be given based on solutions to homework assignments/exercises.

The course will be taught in English.

Further reading

T. Gowers, Generalizations of Fourier analysis, and how to apply them, preprint, arXiv:1608.04127

Course outline

March 13
Van der Waerden's theorem; the Erdős–Turán conjecture / Szemerédi's theorem (without proof); characters of a finite abelian group and the Pontryagin dual; Fourier transform over finite abelian groups; Parseval's identity / Plancherel's formula
March 20
Fourier transforms of subsets of finite abelian groups; Roth's theorem in ℤ3m (Meshulam's theorem) with proof; proof of Roth's theorem in {1, ..., n}
March 27
Progression of upper bounds in Roth's theorem; Freiman isomorphisms; Behrend's construction of large subsets of {1, ..., n} with no 3-term APs; the triangle removal lemma; derivation of Roth's theorem from the triangle removal lemma; the "corners" theorem in [n]2 and derivation of Roth's theorem from it; the Kr+1(r) removal lemma; the "corners" theorem in [n]d
April 3
The notion of ε-regularity; Szemerédi's regularity lemma; the triangle counting lemma; proof of the triangle removal lemma; proof of Szemerédi's regularity lemma
April 24
Proof of Szmerédi's regularity lemma (continued); the upper bound on the size of 3AP-free sets in (ℤq)m due to Ellenberg–Gijswijt, after Croot–Lev–Pach; a proof of Hoeffding's inequality (large deviations of sums of independent bounded random variables)
May 8
Cauchy–Davenport theorem; Kneser's theorem; sum-free sets; largest sum-free subsets of {1, ..., n}; every n-element set of integers contains a sum-free subset with (n+1)/3 elements; the theorem of Eberhard, Green, and Manners (without proof)
May 15
Infinite sum-free sets either contain only odd numbers or have upper density at most 2/5 (Łuczak); Sidon sets in {1, ..., n}: the upper bound of Erdős and Turán and the construction of Singer / Ruzsa; Bh-sets in {1, ..., n}: the trivial upper bound and the construction of Bose and Chowla; the sum-product conjecture of Erdős and Szemerédi; the upper bound of Erdős and Szemerédi
May 22
Progression of lower bounds in the sum-product conjecture; the argument of Elekes; the Szemerédi–Trotter incidence theorem; the crossing lemma of Ajtai–Chvátal–Newborn–Szemerédi; Solymosi's bound; the Littlewood–Offord problem; Sperner's theorem and Erdős' bound
May 29
Halász' theorem; singularity of random Bernoulli matrices
June 5
An analogue of the Cauchy–Davenport theorem in ℝ/ℤ; Frieman's 3k-4 theorem; Plünnecke graphs
June 12
Plünnecke graphs: addition graphs, independent addition graphs, product graphs, inverse graphs; magnification ratios; multiplicativity of magnification ratios; Plünnecke's theorem; estimates for the growth of iterated sumsets in abelian groups
June 19
Geometry of numbers: lattices, fundamental parallelepipeds, determinants; Blichfeldt's lemma; Minkowski's first and second theorem
June 26
Generalised arithmetic progressions (GAPs); Bohr neighbourhoods contain large GAPs; Bogolyubov's theorem; Freiman's inverse theorem


Assignment #1 (due on April 24)
Assignment #2 (due on May 29)
Assignment #3 (due on June 26)