Additive Combinatorics

Course information

Mastermath course Additive Combinatorics Spring 2026

Lectures: Mondays 10:00 - 11:45
Tutorials: Mondays 12:00 - 12:45

Exceptions: April 6 no lecture

April 27 no lecture

May 4 L016 @ CWI

Location: Week 6-13 SP D1.113

Mid term Monday, March 23 10:00 - 13:00 SP D1.113

Exam: Monday, June 8, 10:00 - 13:00 SP L1.01
Retake: Monday, June 29, 10:00 - 13:00 SP D1.113

Lecturer: Jop Briët (j.briet@cwi.nl)
Teaching assistant: Philippe van Dordrecht (Philippe.Dordrecht@cwi.nl)

Schedule: See below under the lecture notes

For exercises and discussion forum, please visit the ELO website.

Description

Additive combinatorics is a relatively new area of mathematics that brings together areas such as combinatorial and analytic number theory, Ramsey theory, harmonic analysis, graph theory, extremal combinatorics, algebraic methods, ergodic theory and probability theory. The area may be summarized as the theory of counting additive structures in subsets of integers or other abelian groups.

A general question that drives much of the area asks what can be said about additive patterns in a set when the set is big. One of the central results in the area is Szemerédi's theorem, which says that arithmetic progressions of any finite length appear in any big-enough subset of the integers. Another is the Freiman-Ruzsa theorem, which says that if A is a set in some finite abelian group such that the set of pair-sums A+A has roughly the same size as A, then A is approximately a coset of a subgroup.

Major impetus was given to the field by a Fourier-analytic proof of Szemerédi's theorem due to Gowers. This proof ingeniously expanded basic techniques used to prove the case of three-term arithmetic progressions and led to the development of a higher-order Fourier analysis. Building yet further this result and its proofs, Green and Tao later proved their now celebrated result that the prime numbers contain arbitrarily long arithmetic progressions.

Additive combinatorics enjoys close connections with theoretical computer science, in particular with property testing algorithms and error correcting codes. In recent years, intriguing connections with quantum information theory have also emerged.

Lecture notes

Below are drafts of lectures notes accompanying the first few lectures. Notes will be updated as the course progresses. Comments are welcome!

van der Waerden

February 2

In this lecture, we give a brief introduction and discuss a classic result of van der Waerden which is often quoted as marking the origin of additive combinatorics.

Hales-Jewett

February 9

We will see a powerful generalization of van der Waerden's theorem involving colorings of discrete hypercubes.

Meshulam

February 16

Fourier analysis over finite abelian groups is used to prove Szemerédi's theorem for 3-APs in finite vector spaces.

Roth

February 23

The Fourier-analytic density-increment strategy is applied to the integer setting of Roth.

Regularity lemma

March 2

A key lemma giving regular decompositions of graphs underlies a combinatorial proof of Roth's theorem.

Triangle removal lemma

March 9

The regularity lemma is used to prove Roth's theorem.

Arithmetic regularity

March 16

A Fourier-analytic regularity lemma gives a refined version of Meshulam's theorem with 'popular difference'.

Lower bounds

March 23

Quadratic hypersurfaces play a role in constructions of 3-AP-free sets in both the integer and finite-field settings.

Cap set

April 30

The polynomial method is used to vastly improve Meshulam's theorem on 3-AP-free sets in finite vector spaces.

Sum sets I: Freiman-Ruzsa

April 20

A finite subset A of an abelian group is a coset of a subgroup if and only if |A+A| = |A|. The Freiman-Ruzsa theorem gives an approximate equivalence.