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.

## 1. Synopsis

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

**Theorem 3**

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

and .

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.

**Proposition 6**

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:

**Proposition 7**

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

where

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.