Introduction to additive combinatorics (TCC)

In a nutshell


Starting: Tuesday, 15th October 2013
Dates: 15th, 22nd October, 5th, 12th, 19th, 26th November
Time slot: Tuesdays, 9am-11am
Level: graduate course (in the Taught Course Centre)
Prerequisites: some basic Fourier analysis, linear algebra and probability
Office hours: Friday, 2pm (on google hangout - please email me if you wish to participate!)

Synopsis |  Syllabus | Organisation | Assessment | Bibliography


This course serves as a first introduction to additive combinatorics, a subject that has a substantial history but has gained much attention in recent years as a result of numerous high-profile breakthroughs such as the Green-Tao theorem on arithmetic progressions in the primes.

Historically, additive combinatorics addresses problems regarding the additive structure of the integers. For example, what can we say about a finite set A of integers if we know that its sumset A+A={a+a': a, a' in A} is small? It turns out that such sets are highly structured, and we shall see various quantitative results to this effect in the 'toy setting' of F_p^n. We shall also study other additive structures such as 3-term arithmetic progressions in dense subsets of this vector space.

The aforementioned results about arithmetic structure are intimately related to structural results about large graphs, and in particular Szemerédi's celebrated regularity lemma. After proving it and deriving some graph-theoretic as well as arithmetical consequences, we shall give some examples of applications to theoretical computer science.

The methods employed throughout are a mix of analytic and algebraic techniques, together with some elementary probabilistic arguments and some hands-on combinatorics. For a precise list of topics please see the detailed syllabus below.

The prerequisites for this course are minimal. We shall need the fundamental notions of (discrete) Fourier analysis as well as basic concepts from linear algebra and discrete probability.

Feel free to contact me at julia.wolf at with any questions prior to the start of the course.

Return to top


Date ContentRecommended exercises
15/10/2013 Introduction to discrete Fourier analysis: Meshulam's theorem and an arithmetic removal lemma1.9, 1.11, 1.14, 1.24
22/10/2013 The structure of sets with small sumset: Plünnecke's inequality and the Freiman-Ruzsa theorem2.3, 2.14
05/11/2013 Sumsets contain large subspaces: Bogolyubov's lemma and Chang's theorem3.3, 3.9, 3.11, 3.14
12/11/2013 Additive energy and small sumset: the Balog-Szemerédi-Gowers theorem4.2, 4.5, 4.10
19/11/2013 Szemerédi's regularity lemma for graphs: triangle removal and other applications5.9, 5.19
26/11/2013 Selected applications of additive combinatorics to theoretical computer science6.2, 6.3, 6.10

Return to top


This course will not take place on Tuesday, 29th October 2013.

Return to top


At the end of the course, participants will choose from a list of original research articles and write up an exposition of the chosen result. This exposition should place the result in the context of what has been discussed in the course, and should be sufficiently detailed for other course participants to be able to follow the main steps of the argument. The completion of the short weekly problem sets is optional but strongly encouraged.

Return to top


The following reading material may be helpful to course participants. You may also wish to consult my personal roadmap for interesting surveys and original research articles in this general area.

[BTW] B. Barak, L. Trevisan, A. Wigderson (2007):
Lecture notes on Additive Combinatorics and Computer Science.
[G] B.J. Green (2005):
Finite fields models in additive combinatorics.
[N] M.B. Nathanson (1996):
Additive Number Theory: Inverse problems and the geometry of sumsets, Springer Graduate Texts in Mathematics.
google books
[TV] T. Tao and V. Vu (2006):
Additive Combinatorics, Cambridge Univ. Press.
google books

Return to top

This page was last updated 23rd October 2013.