C3.10 Additive Combinatorics (2024-25)
Main content blocks
- Lecturer: Profile: Ben Green
Course information
General Prerequisites:
There are very few prerequisites for this course. At one point we will state and use Euler's formula for planar graphs. This is covered in B8.5 Graph Theory, but the statement may be understood independently of that course. We will be discussing the notion of entropy, which is introduced in B8.4 Information Theory. However, we will develop what we need from first principles.
Course Term: Hilary
Course Lecture Information: 16 lectures
Course Weight: 1
Course Level: M
Assessment Type: Written Examination
Course Overview:
Additive combinatorics is the study of additive questions about finite sets of integers.
We will begin by proving a famous theorem of Roth: every set of integers with positive density contains three distinct elements in arithmetic progression. This proof uses some basic ideas from Fourier analysis, which we will develop from scratch. Then, we will turn to the corresponding question in the group $(\mathbf{Z}/3\mathbf{Z})^n$, where much stronger bounds are known using algebraic methods.
Next we will look at the structure of finite sets $A$ of integers which are almost closed under addition in the sense that their sumset $A + A := \{ a_1 + a_2 : a_1, a_2 \in A \}$ is relatively small. The highlight here is Freiman's theorem, which states that any such set has a precise combinatorial structure known as a generalised progression. The proof once again uses some Fourier analysis as well as a host of other ingredients such as the geometry of numbers, which we will develop from first principles.
After that, we will turn to the corresponding question in vector spaces over finite fields. We will introduce entropy methods and describe how they may be used to prove a rather precise description of sets with small sumset in this setting.
Finally, we will look at instances of the sum-product phenomenon, which says that it is impossible for a finite set of integers to be simultaneously additively- and multiplicatively structured. This section draws from a particularly rich set of other mathematical areas, including graph theory, geometry and analysis, as well as previous sections of the course. Nonetheless, prerequisites will be minimal and we will develop what we need from scratch.
A particular aim of the course will be to give a taster of the very large number of different methods which have been brought to bear on these topics: Fourier analysis, algebraic methods, methods from information theory, graph theory and geometric combinatorics.
We will begin by proving a famous theorem of Roth: every set of integers with positive density contains three distinct elements in arithmetic progression. This proof uses some basic ideas from Fourier analysis, which we will develop from scratch. Then, we will turn to the corresponding question in the group $(\mathbf{Z}/3\mathbf{Z})^n$, where much stronger bounds are known using algebraic methods.
Next we will look at the structure of finite sets $A$ of integers which are almost closed under addition in the sense that their sumset $A + A := \{ a_1 + a_2 : a_1, a_2 \in A \}$ is relatively small. The highlight here is Freiman's theorem, which states that any such set has a precise combinatorial structure known as a generalised progression. The proof once again uses some Fourier analysis as well as a host of other ingredients such as the geometry of numbers, which we will develop from first principles.
After that, we will turn to the corresponding question in vector spaces over finite fields. We will introduce entropy methods and describe how they may be used to prove a rather precise description of sets with small sumset in this setting.
Finally, we will look at instances of the sum-product phenomenon, which says that it is impossible for a finite set of integers to be simultaneously additively- and multiplicatively structured. This section draws from a particularly rich set of other mathematical areas, including graph theory, geometry and analysis, as well as previous sections of the course. Nonetheless, prerequisites will be minimal and we will develop what we need from scratch.
A particular aim of the course will be to give a taster of the very large number of different methods which have been brought to bear on these topics: Fourier analysis, algebraic methods, methods from information theory, graph theory and geometric combinatorics.
Course Synopsis:
Arithmetic progressions.<\b> Basic properties of Fourier transforms. Roth's theorem that every subset of \(\{1,\dots, N\}\) of size at least \(\delta N\) contains three elements in arithmetic progression, provided \(N\) is sufficiently large in terms of \(\delta\). The Croot-Lev-Pach method and strong bounds for arithmetic progressions in \((\mathbf{Z}/3\mathbf{Z})^n\).
Sumsets and Freiman's theorem.<\b> Basic sumset estimates. Additive energy and its relation to sumsets: statement (but not proof) of the Balog-Szemerédi-Gowers theorem. Bohr sets and Bogolyubov's theorem. Minkowski's second theorem (statement only). Freiman's theorem on sets with small doubling constant. Freiman's lemma on the dimension of sets with small doubling.
Entropy methods and polynomial Freiman-Ruzsa.<\b> Basic notions of entropy and entropy analogues of sumset inequalities. The fibring inequality for entropy doubling. Marton's conjecture in characteristic 2. Deduction of the weak polynomial Freiman-Ruzsa conjecture over \(\mathbf{Z}\).
{Sum-product theorems.<\b> The crossing number inequality for graphs. The Szemerédi-Trotter theorem on point-line incidences, and application to prove that either <span class="nolink">\(|A + A|\)</span> or <span class="nolink">\(|A \cdot A|\)</span> has size at least <span class="nolink">\(c|A|^{5/4}\). Proof of Bourgain and Chang's result that either the \(m\)-fold sumset \(A + A + \cdots + A\) or the \(m\)-fold product set \(A \cdot A \cdots \cdot A\) has size at least \(|A|^{f(m)}\), where \(f(m) \rightarrow \infty\).
If time allows the course will conclude with a brief non-examinable discussion of Gowers's work on Szemerédi's theorem for progressions of length 4 and longer, which ties together several earlier strands in the course.
Sumsets and Freiman's theorem.<\b> Basic sumset estimates. Additive energy and its relation to sumsets: statement (but not proof) of the Balog-Szemerédi-Gowers theorem. Bohr sets and Bogolyubov's theorem. Minkowski's second theorem (statement only). Freiman's theorem on sets with small doubling constant. Freiman's lemma on the dimension of sets with small doubling.
Entropy methods and polynomial Freiman-Ruzsa.<\b> Basic notions of entropy and entropy analogues of sumset inequalities. The fibring inequality for entropy doubling. Marton's conjecture in characteristic 2. Deduction of the weak polynomial Freiman-Ruzsa conjecture over \(\mathbf{Z}\).
{Sum-product theorems.<\b> The crossing number inequality for graphs. The Szemerédi-Trotter theorem on point-line incidences, and application to prove that either <span class="nolink">\(|A + A|\)</span> or <span class="nolink">\(|A \cdot A|\)</span> has size at least <span class="nolink">\(c|A|^{5/4}\). Proof of Bourgain and Chang's result that either the \(m\)-fold sumset \(A + A + \cdots + A\) or the \(m\)-fold product set \(A \cdot A \cdots \cdot A\) has size at least \(|A|^{f(m)}\), where \(f(m) \rightarrow \infty\).
If time allows the course will conclude with a brief non-examinable discussion of Gowers's work on Szemerédi's theorem for progressions of length 4 and longer, which ties together several earlier strands in the course.
Section outline
-
-
Full lecture notes for the course. Please note that, since much of the second half of the course is new, what is covered in lectures may be a subset of what is in the notes.
Please let me know of any comments or corrections.
-
Covers material from Chapters 1 and 2 of the notes.
The sheet is available in two formats: with no solutions, and with solutions to Section A and C questions. -
Covers material from Section 3 and some of Section 4 of the notes.
The sheet is available in two formats: with no solutions, and with solutions to Section A and C questions.
-
This sheet covers the second half of Chapter 4 and Chapter 5 of the notes.
It is available in two forms: without solutions and with solutions to Sections A and C.
-
Covers Section 6 to 9 of the notes. As usual, it is available either with no solutions, or with solutions to Sections A and C.
-
-
-
Registration start: Monday, 13 January 2025, 12:00 PMRegistration end: Friday, 14 February 2025, 12:00 PM
-
Class Tutor's Comments Assignment
Class tutors will use this activity to provide overall feedback to students at the end of the course.
-