Pascal Millet

The term additive combinatorics refers to the study of the additive structure of a commutative group (sometimes the multiplicative structure of a ring) relying on combinatorial and elementary algebraic tools like graphs, counting methods and Fourier transform on finite group.

Let’s illustrate the type of question that arises in this field with two basic examples. Let A ⊂ \mathbb Z be a finite set. We denote by A+A the set of all integers of the form a+a′ where a,a′ ∈ A. We have the following elementary fact: |A + A| = 2|A| − 1 if and only if A is an arithmetic progression. In other words, there is a link between the cardinal of A + A and the additive structure of A. A generalized (and more robust) version of this fact is the Freiman-Ruzsa theorem, which asserts that if |A + A| is small, then A is a large subset of a generalized arithmetic progression.

Another interesting question concerning the additive structure is whether some arithmetic progressions of a given length exist in the set A. For example, by a pigeonhole argument, we have that every subset A of {1,...,N} of cardinal strictly greater than 2E(N/3)+1 contains an arithmetic progression with three terms. We deduce that for δ >2/3 nd for N large enough, every subset A of {1,...,N} of density δ contains an arithmetic progression with three terms. Roth’s theorem asserts that the same statement is true for every δ > 0.

In my presentation, I will begin by proving basic combinatorial facts about the sum of sets to provide familiarity with some important concepts. Then I will introduce the discrete Fourier transform, which is a key tool in additive combinatorics. Finally, I will present the proof of Roth’s theorem and some open related questions.