Additive Combinatorics

(3 Credit Hours) · Undergraduate

Course description for C3.10 Additive Combinatorics: The aim of this course is to present classic results in additive and combinatorial number theory, showing how tools from a variety of mathematical areas may be used to solve number-theoretical problems. We will begin by looking at classical theorems about writing natural numbers as the sums of squares and primes. For instance, we will prove Lagrange's theorem that every number is the sum of four squares, and we will show that every large integer is the sum of a bounded number of primes. Next we will look at more general sets of integers, proving a famous theorem of Roth: every set of integers with positive density contains three distinct elements in arithmetic progression. We will also look at the structure of nite sets A of integers which are almost closed under addition in the sense that their sumset A + A := fa1+a2 : a1; a2 2 Ag 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. Finally, we will look at instances of the sum-product phenomenon, which says that it is impossible for a nite 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. Nonetheless, prerequisites will be minimal and we will develop what we need from scratch.