Additive Combinatorics and Applications Autumn 2023

The course has little prerequisites beyond basic analysis and linear algebra. Some knowledge of integration theory, probability, and of the theory of finite fields, can be useful.

Forum

A DMATH forum is available for discussion and to ask/answer questions about the course, see here.

Lecture notes

I will prepare lecture notes during the course of the semester. The various drafts will appear here, with a date indicating which version it is.
Version of 20.12.2023.

Exercises

The lecture will be accompanied by roughly biweekly exercise classes, usually during the Thursday class. We will announce the precise dates in the lecture as well as here. You should submit your exercise sheets either in person in the Tuesday lecture before the next exercise class or in PDF form to the coordinator: cynthia.bortolotto [at] math.ethz.ch.

Dates of exercise classes
September 28
October 12
October 26
November 9
November 23
December 7

Exercise sheet	Due by	Solutions
Exercise sheet 1	October 3	Exercise sheet 1
Exercise sheet 2	October 10	Exercise sheet 2
Exercise sheet 3	October 26	Exercise sheet 3
Exercise sheet 4	November 9	Exercise sheet 4
Exercise sheet 5	November 23	Exercise sheet 5
Exercise sheet 6	December 7	Exercise sheet 6>

Summary of the lectures

We indicate here the topics discussed in each lecture, with references to the literature where applicable.

Day	Content
19.9.2023	Introduction: what is additive combinatorics? Some basic statements, and some applications. Outline of the contents of the course. Review of some basic facts.
21.9.2023	Survey of Fourier analysis on finite abelian groups.
26.9.2022	Definition and basic properties and examples of product sets and Freiman morphisms. Definition of Sidon sets, application to the fourth moment; the Erdös-Turán example.
3.10.2023	The Eberhard--Manners classification of "classical" dense Sidon sets. Statements of basic results concerning Sidon sets (finite and infinte) in positive integers.
5.10.2023	Proof of upper bound for the "density" of infinite Sidon sets in positive integers. Definition of approximate subgroups and first quick discussion.
10.10.2023	Approximate subgroups: the Ruzsa distance, covering lemma, and control of higher product sets from the triple product set. Link between approximate subgroups and neutral symmetric sets with small tripling. Definition of multiplicative energy and statement of the link between sets with large normalized energy and approximate subgroups.
17.10.2023	A sample application of the idea of approximate subgroups: the Bourgain-Gamburd on expander graphs associated to SL₂(F_p); definition of expanders, and sketch of the key steps.
19.10.2023	Proof of a version of the Balog-Szemerédi-Gowers Theorem (following Schoen). Short discussion of the general version.
24.10.2023	Beginning of Chapter 3 (the sum-product phenomenon). Discussion of simple examples, including the Erdös "multiplication table problem". First proof of the sum-product theorem for integers (Erdös-Szemerédi). The argument of Elekes using the Szemerédi-Trotter Theorem.
31.10.2023	Sketch of the proof of the Szemerédi-Trotter inequality using the crossing inequality for planar graphs. Solymosi's proof of the sum-product inequality. Statement of the Bourgain-Katz-Tao Theorem.
2.11.2023	Proof of the Bourgain-Katz-Tao Theorem, following the original argument. Remarks on applications.
7.11.2023	Second proof of the Bourgain-Katz-Tao Theorem, using Breuillard's approach.
14.11.2023	Discussion of applications of the sum-product theorem: incidence bounds, Dvir's Theorem on Kakeya sets, exponential sums over multiplicative subgroups.
16.11.2023 One hour lecture only	Rough outline of the proof of the theorem of Bourgain, Glibichuk and Konyagin.
21.11.2023	General discussion of arithmetic progressions in subsets of abelian groups. Behrend's example of large sets without three term progressions. Presentation of the strategy of Roth's Theorem.
28.11.2023	Start of the proof of Roth's Theorem; comparison with the sumfree set situation.
30.11.2023	End of the proof of Roth's Theorem. Start of discussion of longer progressions.
5.12.2023	No lecture
12.12.2023	Definition of Gowers norms. Relation of the second Gowers norm with the Fourier transform. Proof that the Gowers norms are (semi)norms.
14.12.2023	Gowers norms control the behavior of functions along arithmetic progressions. Trichotomy for the existence of k-term progressions in terms of the size of a Gowers norm of the balanced characteristic function. Example of functions with large and small Gowers norms.
14.12.2023	Quick survey of the inverse theorem for Gowers norms. Going back to sumsets: discussion of the Freiman-Ruzsa Theorem, and outline of Ruzsa's proof.
21.12.2023	No lecture!

Literature

Additive Combinatorics by T. Tao and V. Vu (Cambridge University Press, 2010)
Additive combinatorics, lecture notes by K. Soundararajan, Stanford, 2007.
Additive combinatorics, lecture notes by B. Green, Oxford, 2023.
Graph Theory and Additive Combinatorics by Y. Zhao, Cambridge University Press, 2023 (PDF version available from the webpage).
For the discussion of expander graphs and the Bourgain--Gamburd Theorem, one can look at my book An introduction to expander graphs (also available from the SMF website).