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 second half of my presentation.
We aim to prove the following result.
Theorem 1 (Bourgain)
Assume is prime and . Assume that
is such that . Then contains a proper arithmetic progression of length at least
for some absolute constant .
The methods that we used with Bohr sets fail here, because in the previous half of yesterday’s lecture we took advantage of Parseval’s identity in order to handle large convolutions, always keeping two term’s inside the sign. When we work with this causes us to be stuck. So, we instead use the technology of constants and dissociated sets.
2. Previous results
As usual, let denote a finite abelian group. Recall that
Let and . The constant of , denoted , is defined as
If , we say is a dissociated set if all subset sums of are distinct.
For such sets we have the Rudin’s inequality (yes, Walter) which states that
Lemma 4 (Rudin’s inequality)
If is dissociated then
Disassociated sets come up via the so-called “cube covering lemma”:
Lemma 5 (Cube covering lemma)
Let and . Then we can partition
- Each is dissociated of size ,
- There exists , , such that is contained in a -cube, i.e. it’s covered by , where .
Finally, we remind the reader that
Lemma 6 (Parseval)
Since we don’t have Bohr sets anymore, the way we detect progressions is to use the pigeonhole principle. In what follows, let be the shift of by , id est .
Proposition 7 (Pigeonhole gives arithmetic progressions)
Let , and suppose is such that
Then contains an arithmetic of length and spacing .
Proof: Apply the pigeonhole principle to find an such that
Then the claim follows.
Proposition 8 (Estimate for for dissociated)
Let , with dissociated. Then for any set with we have
Proof: Let be large and note
Then by Parseval and Rudin,
We may then take .
We combine these two propositions into the following lemma which applies if has nonzero values of “uniform” size.
Lemma 9 (Uniformity estimate for shifts)
Let and . Suppose that is “uniform in size” across its support, in the sense that
Then one can find such that and for all ,
Proof: Use the cube covering lemma to put where is contained in the cube of and for . Accordingly, we decompose over its Fourier transform as
by letting be supported on and supported on .
First, we can bound the “leftover” bits in :
Since the are covered by a cube of , we get
Let’s then bound the contribution over each dissociated set. We’ll need both the assumption of uniformity and the proposition we proved for dissociated sets.
where the last step is by uniformity of . Now combine everything with triangle inequality.
4. Proof of main theorem
Without loss of generality . Of course, we let so . We will have parameters , , and which we will select at the end.
Our goal is to show there exists some integer such that
Now we cannot apply the uniformity estimate directly since is probably not uniform, and therefore we impose a dyadic decomposition on the base group ; let
Then as before we can decompose via Fourier transform to obtain
so that is supported on .
Now we can apply the previous lemma to get for each :
for some ; hence by summing and using the fact that
we obtain that
As for the “error” term, we bound
Thus, putting these altogether we need to find such that
Now set and , so the first and third terms are less than , since by hypothesis
from which we deduce
Thus it suffices that
where . Note . Now we recall the result that
and so it suffices for us that
for constants and . Then works now.