Additive Combinatorics
Course information
Mastermath course Additive Combinatorics Spring 2024
Lectures: Tuesdays 14:00 - 15:45
Tutorials: Tuesdays 16:00 - 16:45
Location: Week 6-13 SP D1.116 (UvA)
Week 14 no lecture
Week 15-17 SP D1.116
Week 18 L016 (CWI, Science Park 123)
Week 19-21 SP D1.116
Exam: Tuesday, June 18, 14:00 - 17:00 room SP L1.01
Retake: Tuesday, July 9, 14:00 - 17:00 room SP L0.12
Lecturer: Jop Briët
Schedule: See below under the lecture notes
For assignments 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 most fundamental 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 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.
Lecture notes
Below are drafts of lectures notes accompanying the first few lectures. Notes will be updated as the course progresses. Comments are welcome!
February 6
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.
February 13
We will see a powerful generalization of van der Waerden's theorem involving colorings of discrete hypercubes.
February 20
Fourier analysis over finite abelian groups is used to prove Szemerédi's theorem for 3-APs in finite vector spaces.
February 27
The Fourier-analytic density-increment strategy is applied to the integer setting of Roth.
March 5
A key lemma giving regular decompositions of graphs underlies a combinatorial proof of Roth's theorem.
March 19
A Fourier-analytic regularity lemma gives a refined version of Meshulam's theorem with 'popular difference'.
March 26
Quadratic hypersurfaces play a role in constructions of 3-AP-free sets in both the integer and finite-field settings.
April 9
The polynomial method is used to vastly improve Meshulam's theorem on 3-AP-free sets in finite vector spaces.
April 16
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.
With non-trivial modifications, the Fourier-analytic density-increment strategy can be used to prove Szemerédi's theorem.
