As part of the 18.099 discrete analysis reading group at MIT, I presented section 4.7 of Tao-Vu’s Additive Combinatorics textbook. Here were the notes I used for the first part of my presentation.
In the previous few lectures we’ve worked hard at developing the notion of characters, Bohr sets, spectrums. Today we put this all together to prove some Szemerédi-style results on arithmetic progressions of .
Recall that Szemerédi’s Theorem states that:
Theorem 1 (Szemerédi)
Let be an integer. Then for sufficiently large , any subset of with density at least
contains a length arithmetic progression.
Notice that the density approaches zero as but it does so extremely slowly.
Our goal is to show much better results for sets like , or . In this post we will prove:
Theorem 2 (Chang’s Theorem)
Let and let . Suppose , and let
Then there is a proper symmetric progression of rank at most and density
One can pick such that for example , i.e. if has small Ruzsa diameter. Or one can pick always, but then becomes quite large.
We also prove that
Let and let . Suppose and now let
Then there is a proper symmetric progression of rank at most and
2. Main steps
Our strategy will take the following form. Let be the set we want to study (for us, or ). Then our strategy will take the following four steps.
Step 1. Analyze the Fourier coefficients of . Note in particular the identities
Recall also from the first section of Chapter 4 that
- The support of is .
Step 2. Find a set of the form contained completely inside . Recall that by expanding definitions:
Step 3. Use the triangle inequality and the Fourier concentration lemma (covering). Recall that this says:
Lemma 4 (Fourier Concentration, or “Covering Lemma”, Tao-Vu 4.36)
Let , and let . Then one can pick , \dots, such that
and is contained in a -cube, i.e. it’s covered by where .
Using such a , we have by the triangle inequality
Step 4. We use the fact that Bohr sets contain long arithmetic progressions:
Theorem 5 (Bohr sets have long coset progressions, Tao-Vu 4.23)
Let . Then within one can select a proper symmetric progression such that
The third step is necessary because in the bound for the preceding theorem, the dependence on is much more severe than the dependence on . Therefore it is necessary to use the Fourier concentration lemma in order to reduce the size of before applying the result.
3. Proof of Chang’s theorem
First, we do the first two steps in the following proposition.
Let , . Assume , Then
Proof: To do this, as advertised consider
We want to show that any lies in the support of . Note that if does lie in this Bohr set, we have
We aim to show now . This follows by computing
Now we split the sum over :
Now we take the real part of both sides:
By definition of we can bound two of the ‘s via
Now the last sum is the square of the norm, hence
by the assumption .
Now, let , and let
Then by (1), we have
and then using the main result on Bohr sets, we can find a symmetric progression of density at least
and whose rank is at most . This completes the proof of Chang’s theorem.
4. Proof of the second theorem
This time, the Bohr set we want to use is:
Let . Then
Proof: Let . Note that we have , while . So by shifting , we may assume without loss of generality that
Now, consider in the Bohr set. Then we have
Bounding by the maximum for , and then using Cauchy-Schwarz,
Claim: if and then
Indeed one just considers two cases:
- If , then ( in Bohr set) and .
- If , then ( outside Spec) and .
So finally, we have
and this implies .
Once more by (1), we have
So there are the main theorem on Bohr sets again, there is a symmetric progression of density at least
and rank at most . This completes the proof of the second theorem.