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.
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
For such sets we have the Rudin’s inequality (yes, Walter) which states that
Disassociated sets come up via the so-called “cube covering lemma”:
Finally, we remind the reader that
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 .
Proof: Apply the pigeonhole principle to find an such that
Then the claim follows.
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.
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.