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.

## 1. Synopsis

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

**Definition 2**

Let and . The ** constant** of , denoted , is defined as

**Definition 3**

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

such that

- 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)**

We have

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.

## 3. Periodicity

**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.