- Lecturer: Ben Green
General Prerequisites:
Students should be familiar with elementary number theory such as modular arithmetic and prime factorisations. The first half of ASO Number Theory (not including the material on quadratic residues) will be quite sufficient. At one point we will state and use Euler's formula for planar graphs. This is covered in B8.5 Graph Theory, but the statement may be understood independently of that course. Early in the course we will use some simple facts about the distribution of prime numbers. This topic is explored in far greater detail in C3.8 Analytic Number Theory, but we will not assume attendance at that course.
Course Term: Hilary
Course Lecture Information: 16 lectures
Course Weight: 1
Course Level: M
Assessment Type: Written Examination
Course Overview:
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 finite sets A of integers which are almost closed under addition in the sense that their sumset \(A + A := \{a^1 +a^2 : a^1 + a^2 \varepsilon A\}\) 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 finite 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.
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 finite sets A of integers which are almost closed under addition in the sense that their sumset \(A + A := \{a^1 +a^2 : a^1 + a^2 \varepsilon A\}\) 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 finite 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.
Learning Outcomes:
Course Synopsis:
The classical bases.
Every prime congruent to 1 modulo 4 is a sum of two squares. Every natural number is the sum of four squares. *Discussion of sums of three squares*. Schnirelman density. Application of Selberg's sieve to show that every large number is the sum of at most \(C\) primes for some fixed \(C\).
Progressions of length 3.
Basic properties of Fourier transforms. Roth's theorem that every subset of \(\{1, \dots , N\}\) of size at least \(\delta N\) contains three elements in arithmetic progression, provided \(N\) is sufficiently large in terms of \(\delta\).
Sumsets and Freiman's theorem.
Basic sumset estimates. Additive energy and its relation to sumsets: statement (but not proof) of the Balog-Szemer\(\acute{e}\)di-Gowers theorem. Bohr sets and Bogolyubov's theorem. Minkowski's second theorem (statement only). Freiman's theorem on sets with small doubling constant.
Sum-product theorems.
The crossing number inequality for graphs. The Szemer\(\acute{e}\)di-Trotter theorem on point-line incidences, and application to prove that either \(|A + A|\) or \(|A \cdot A|\) has size at least \(c|A|^{5/4}\). The Pr\(\acute{e}\)kopa-Leindler inequality, quasicubes and sumsets. Proof of Bourgain and Chang's result that either the \(m\)-fold sumset \(A + A + \cdots + A\) or the \(m\)-fold product set \(A \cdot A \cdots \cdot A\) has size at least \(|A|^{f(m)}\), where \(f(m) \rightarrow \infty\).
If time allows the course will conclude with a brief non-examinable discussion of Gowers's work on Szemer\(\acute{e}\)di's theorem for progressions of length 4 and longer, which ties together several earlier strands in the course.
Every prime congruent to 1 modulo 4 is a sum of two squares. Every natural number is the sum of four squares. *Discussion of sums of three squares*. Schnirelman density. Application of Selberg's sieve to show that every large number is the sum of at most \(C\) primes for some fixed \(C\).
Progressions of length 3.
Basic properties of Fourier transforms. Roth's theorem that every subset of \(\{1, \dots , N\}\) of size at least \(\delta N\) contains three elements in arithmetic progression, provided \(N\) is sufficiently large in terms of \(\delta\).
Sumsets and Freiman's theorem.
Basic sumset estimates. Additive energy and its relation to sumsets: statement (but not proof) of the Balog-Szemer\(\acute{e}\)di-Gowers theorem. Bohr sets and Bogolyubov's theorem. Minkowski's second theorem (statement only). Freiman's theorem on sets with small doubling constant.
Sum-product theorems.
The crossing number inequality for graphs. The Szemer\(\acute{e}\)di-Trotter theorem on point-line incidences, and application to prove that either \(|A + A|\) or \(|A \cdot A|\) has size at least \(c|A|^{5/4}\). The Pr\(\acute{e}\)kopa-Leindler inequality, quasicubes and sumsets. Proof of Bourgain and Chang's result that either the \(m\)-fold sumset \(A + A + \cdots + A\) or the \(m\)-fold product set \(A \cdot A \cdots \cdot A\) has size at least \(|A|^{f(m)}\), where \(f(m) \rightarrow \infty\).
If time allows the course will conclude with a brief non-examinable discussion of Gowers's work on Szemer\(\acute{e}\)di's theorem for progressions of length 4 and longer, which ties together several earlier strands in the course.