Additive and Analytic Combinatorics

Additive combinatorics is the theory of counting additive structures in sets. This theory has seen exciting developments and dramatic changes in direction in recent years thanks to its connections with areas such as harmonic analysis, ergodic theory, and representation theory. As it turns out, many combinatorial ideas that have existed in the combinatorics community for quite some time can be used to attack notorious problems in other areas of mathematics. A typical example is the Green-Tao theorem on the existence of long arithmetic progressions in primes, which uses a famous theorem of Szemerédi on arithmetic progressions in dense sets as a key component. A more recent breakthrough in this field is the work of Breuillard, Green, and Tao, which established an analogue of the Freiman inverse theorem for non-commutative groups. Freiman’s theorem is a cornerstone of combinatorial number theory. It was first stated and proved for integers by Freiman (Ruzsa later came up with a different proof). It is not too hard to extend Ruzsa’s proof to abelian groups and this was done by Green and Ruzsa a few years ago. However, the extension to non-commutative groups is much harder and requires sophisticated tools, in particular, several tools from the proof of Hilbert’s fifth problem. The result has many consequences, most notably a new proof of Gromov’s polynomial growth theorem. The field is also of great interest to computer scientists; a number of the techniques and theorems have seen application in, for example, communication complexity, property testing, and the design of randomness extractors.