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:
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:
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
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:
Step 4. We use the fact that Bohr sets contain long arithmetic progressions:
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.
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:
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.