Additive combinatorics (Spring 2020)

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

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

Further reading

T. Gowers, Generalizations of Fourier analysis, and how to apply them, Bull. Amer. Math. Soc. (N.S.) 54 (2017), 1–44, arXiv:1608.04127
T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), 143–184, preprint

Course outline

March 11
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 18
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 25
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 1
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 22
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
May 6
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); 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
May 13
Bh-sets in {1, ..., n}: the trivial upper bound and the construction of Bose and Chowla; the Cauchy–Davenport theorem; Kneser's theorem (without proof); the sum-product conjecture of Erdős and Szemerédi; the upper bound of Erdős and Szemerédi; progression of lower bounds; the argument of Elekes; the Szemerédi–Trotter incidence theorem
May 20
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 27
singularity of random Bernoulli matrices; Halász' theorem
June 3
Frieman's 3k-4 theorem (without proof); the Plünnecke–Ruzsa inequality (estimates for the growth of iterated sumsets); geometry of numbers: lattices, fundamental parallelepipeds, determinants; Blichfeldt's lemma
June 10
Minkowski's first theorem; Minkowski's second theorem (without proof); Bohr neighbourhoods contain large generalised APs; Bogolyubov's theorem
June 17
Ruzsa's representation lemma; Freiman's inverse theorem (with proof)


Assignment #1
Assignment #2
Assignment #3