MAT6640: Additive Combinatorics, Winter Semester 2010

Prof: Andrew Granville
Bureau: 6153 André Aisenstadt, Tel: 343-6583; Courriel:

Course Book: Terence Tao and Van Vu's "Additive Combinatorics", Cambridge Studies in Advanced Mathematics 105, Cambridge University Press.

Classtimes: Monday 13h30-15h00; Tuesday 10h-11h00 or 9h30-11h30, in Andre-Aisenstadt 4186.
Class dates: From Jan 11 to Apr 13, 2010
Forthcoming times: 12/13 avril

2010 Course notes

I have just (16/04/2010) made substantial revisions to my notes, particularly with reference to Gowers' proof of four term arithmetic progressions. If you already have my notes you should simply print pages 31-33 and pages 43-58 from these new notes.
Revised Course notes from 2010.
I do hope to thoroughly revise the notes for the whole course in the next couple of weeks. I will make that available here as soon as it is completed.
En Francais, et page web complet

Course notes

I am not 100% certain what material we will cover in the course. A lot depends on the interests of the students. I am making available here my
Course notes from 2005.
(Please be aware that these are "first drafts", and not 100% reliable.) Also we have
Soundararajan's 2007 course notes from Stanford

Papers to read for background

You should begin by studying my
Introduction to additive combinatorics.

Terry Tao's blog contains an amazing amount of remarkable mathematics, usually well explained. He is one of the key people in the development of Additive Combinatorics and it is well worth finding his discussions of many of the key topics in this course.

WARNING! Wikipedia articles often contain misunderstandings and misleading statements. Do not use this as a primary source of information!

Course Contents/Syllabus

This will be a first course in additive combinatorics. This is a subject which incorporates ideas from an enormous number of areas: harmonic analysis, combinatorics, number theory, ergodic theory, discrete geometry, graph theory, theoretical computer science, even topology and algebra... The list is long, and no student can be expected to have all of the pre-requisites. We will attempt to explain the main ideas needed from the different subjects as they are needed. Our approach will be developed primarily from the point-of-view of harmonic analysis and analytic number theory.

There have been some spectacular results in this new area, including Green and Tao's proof that there are infinitely many k-term arithmetic progressions of primes, Bourgain's bounds on very short exponential sums, and the theory of prime values of the co-ordinates of orbits of matrix groups as developed by Bourgain-Gamburd-Sarnak and others. We will discuss these results, though fall far short of proving any of them! The main goal of our course will be to understand some of the key results and Gower's first proof of Szemeredi's Theorem for four term arithmetic progressions.

Topics may include
  • Adding sets and additive bases for the integers (including Dyson transformations).
  • Adding finite sets and covering lemmas.
  • Van der Waerden's theorem and the Hales-Jewett Theorem.
  • Discrete Fourier transformations and Weyl's equidistribution Theorem.
  • Vinogradov's three primes Theorem.
  • Roth's theorem.
  • The Freiman-Ruzsa Theorem.
  • Sum-Product Formulas. In the integers, in the reals, in finite fields, and in groups of matrices.
  • The Balog-Szemeredi-Gowers Theorem.
  • Gowers' norms and the inverse conjecture.
  • Szemeredi's regularity lemma.
  • Szemeredi's Theorem for four term arithmetic progressions.