# 18.099 Transcript: Chang’s Theorem

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 ${\mathbb Z_N}$.

Recall that Szemerédi’s Theorem states that:

Theorem 1 (Szemerédi)

Let ${k \ge 3}$ be an integer. Then for sufficiently large ${N}$, any subset of ${\{1, \dots, N\}}$ with density at least

$\displaystyle \frac{1}{(\log \log N)^{2^{-2^k+9}}}$

contains a length ${k}$ arithmetic progression.

Notice that the density approaches zero as ${N \rightarrow \infty}$ but it does so extremely slowly.

Our goal is to show much better results for sets like ${2A-2A}$, ${A+B+C}$ or ${A+B}$. In this post we will prove:

Theorem 2 (Chang’s Theorem)

Let ${K,N \ge 1}$ and let ${A \subseteq Z = \mathbb Z_N}$. Suppose ${E(A,A) \ge |A|^3 / K}$, and let

$\displaystyle d \ll K\left( 1+\log \frac{1}{\mathbf P_Z A} \right).$

Then there is a proper symmetric progression ${P \subseteq 2A-2A}$ of rank at most ${d}$ and density

$\displaystyle \mathbf P_Z P \ge d^{-d}.$

One can pick ${K}$ such that for example ${|A \pm A| \le k|A|}$, i.e. if ${A}$ has small Ruzsa diameter. Or one can pick ${K = 1/\mathbf P_Z A}$ always, but then ${d}$ becomes quite large.

We also prove that

Theorem 3

Let ${K,N \ge 1}$ and let ${A, B, C \subseteq Z = \mathbb Z_N}$. Suppose ${|A|=|B|=|C| \ge \frac{1}{K}|A+B+C|}$ and now let

$\displaystyle d \ll K^2\left( 1+\log \frac{1}{\mathbf P_Z A} \right).$

Then there is a proper symmetric progression ${P \subseteq A+B+C}$ of rank at most ${d}$ and

$\displaystyle \mathbf P_Z P \ge d^{-d}.$

## 2. Main steps

Our strategy will take the following form. Let ${S}$ be the set we want to study (for us, ${S=2A-2A}$ or ${S=A+B+C}$). Then our strategy will take the following four steps.

Step 1. Analyze the Fourier coefficients of ${\widehat 1_S}$. Note in particular the identities

\displaystyle \begin{aligned} \left\lVert \widehat 1_A \right\rVert_{\ell^\infty(Z)} &= \mathbf P_Z A \\ \left\lVert \widehat 1_A \right\rVert_{\ell^2(Z)} &= \sqrt{\mathbf P_Z A} \\ \left\lVert \widehat 1_A \right\rVert_{\ell^4(Z)} &= \frac{E(A,A)}{|Z|^3}. \end{aligned}

Recall also from the first section of Chapter 4 that

• The support of ${1_A \ast 1_B}$ is ${A+B}$.
• ${\widehat{f \ast g} = \widehat f \cdot \widehat g}$.
• ${f(x) = \sum_\xi \widehat f(\xi) e(\xi \cdot x)}$.

Step 2. Find a set of the form ${\text{Bohr }(\text{Spec }_\alpha A, \rho)}$ contained completely inside ${S}$. Recall that by expanding definitions:

$\displaystyle \text{Bohr }(\text{Spec }_\alpha A, \rho) = \left\{ x \in Z \mid \sup_{\xi \; : \; \widehat 1_A(\xi) \ge \alpha \mathbf P_ZA} \left\lVert \xi \cdot x \right\rVert_{\mathbb R/\mathbb Z} < \rho \right\}.$

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 ${A \subseteq Z}$, and let ${0 < \alpha \le 1}$. Then one can pick ${\eta_1}$, \dots, ${\eta_d}$ such that

$\displaystyle d \ll \frac{1 + \log \frac{1}{\mathbf P_ZA}}{\alpha^2}$

and ${\text{Spec }_\alpha A}$ is contained in a ${d}$-cube, i.e. it’s covered by ${c_1\eta_1 + \dots + c_d\eta_d}$ where ${c_i \in \{-1,0,1\}}$.

Using such a ${d}$, we have by the triangle inequality

$\displaystyle \text{Bohr }\left(\{\eta_1, \dots, \eta_d\}, \frac{\rho}{d} \right) \subseteq \text{Bohr }\left( \text{Spec }_\alpha A, \rho \right). \ \ \ \ \ (1)$

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 ${Z = \mathbb Z_N}$. Then within ${\text{Bohr }(S, r)}$ one can select a proper symmetric progression ${P}$ such that

$\displaystyle \mathbf P_Z P \ge \left( \frac{r}{|S|} \right)^{|S|}$

and ${\text{rank } P \le |S|}$.

The third step is necessary because in the bound for the preceding theorem, the dependence on ${|S|}$ is much more severe than the dependence on ${r}$. Therefore it is necessary to use the Fourier concentration lemma in order to reduce the size of ${|S|}$ before applying the result.

## 3. Proof of Chang’s theorem

First, we do the first two steps in the following proposition.

Proposition 6

Let ${A \subseteq Z}$, ${0 < \alpha \le 1}$. Assume ${E(A,A) \ge 4\alpha^2 |A|^3}$, Then

$\displaystyle \text{Bohr }\left(\text{Spec }_\alpha A, \frac 16\right) \subseteq 2A-2A.$

Proof: To do this, as advertised consider

$\displaystyle f = 1_A \ast 1_A \ast 1_{-A} \ast 1_{-A}(x).$

We want to show that any ${x \in \text{Bohr }(\text{Spec }_\alpha A, \frac 16)}$ lies in the support of ${f}$. Note that if ${x}$ does lie in this Bohr set, we have

$\displaystyle \text{Re } e(\xi \cdot x) \ge \frac{1}{2} \qquad \forall \xi \in \text{Spec }_\alpha A.$

We aim to show now ${f(x) > 0}$. This follows by computing

\displaystyle \begin{aligned} f(x) &= 1_A \ast 1_A \ast 1_{-A} \ast 1_{-A}(x) \\ &= \sum_\xi \widehat 1_A(\xi)^2 \widehat 1_{-A}(\xi)^2 e(\xi \cdot x) \\ &= \sum_\xi |\widehat 1_A(\xi)|^4 e(\xi \cdot x) \end{aligned}

Now we split the sum over ${\text{Spec }_\alpha A}$:

\displaystyle \begin{aligned} f(x) &= \sum_{\xi \in \text{Spec }_\alpha(A)} |\widehat 1_A(\xi)|^4 e(\xi \cdot x) + \sum_{\xi \notin \text{Spec }_\alpha(A)} |\widehat 1_A(\xi)|^4 e(\xi \cdot x). \end{aligned}

Now we take the real part of both sides:

\displaystyle \begin{aligned} \text{Re } f(x) &\ge \sum_{\xi \in \text{Spec }_\alpha(A)} |\widehat 1_A(\xi)|^4 \cdot \frac{1}{2} - \sum_{\xi \notin \text{Spec }_\alpha(A)} |\widehat 1_A(\xi)|^4 \\ &= \frac{1}{2} \sum_{\xi} |\widehat 1_A(\xi)|^4 - \frac32 \sum_{\xi \notin \text{Spec }_\alpha(A)} |\widehat 1_A(\xi)|^4 \\ &= \frac{1}{2} \frac{E(A,A)}{|Z|^3} - \frac32 \sum_{\xi \notin \text{Spec }_\alpha(A)} |\widehat 1_A(\xi)|^4. \end{aligned}

By definition of ${\text{Spec }_\alpha A}$ we can bound two of the ${\left\lvert \widehat 1_A(\xi) \right\rvert}$‘s via

\displaystyle \begin{aligned} \text{Re } f(x) &\ge \frac{1}{2} \frac{E(A,A)}{|Z|^3} - \frac32 (\alpha\mathbf P_Z A)^2 \sum_{\xi \notin \text{Spec }_\alpha(A)} |\widehat 1_A(\xi)|^2 \end{aligned}

Now the last sum is the square of the ${\ell^2}$ norm, hence

\displaystyle \begin{aligned} \text{Re } f(x) &\ge \frac{1}{2} \frac{E(A,A)}{|Z|^3} - \frac32 (\alpha\mathbf P_Z A)^2 \cdot \mathbf P_ZA \\ &\ge \frac{1}{2} \frac{E(A,A)}{|Z|^3} - \frac32 \alpha^2 \frac{|A|^3}{|Z|^3} > 0 \end{aligned}

by the assumption ${E(A,A) \ge 4\alpha^2 |A|^3}$. $\Box$

Now, let ${\alpha = \frac{1}{2\sqrt K}}$, and let

$\displaystyle d \ll \frac{1 + \log \frac{1}{\mathbf P_Z A}}{\alpha^2} \ll K\left( 1 + \log \frac{1}{\mathbf P_Z A} \right).$

Then by (1), we have

$\displaystyle \text{Bohr }\left(\{\eta_1, \dots, \eta_d\}, \frac{1}{6d} \right) \subseteq \text{Bohr }\left( \text{Spec }_\alpha A, \frac16 \right) 2A-2A.$

and then using the main result on Bohr sets, we can find a symmetric progression of density at least

$\displaystyle \left( \frac{1/6d}{d} \right)^d = d^{-d}$

and whose rank is at most ${d}$. 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 ${\alpha = \frac{1}{2\pi K}}$. Then

$\displaystyle \text{Bohr }\left(\text{Spec }_\alpha A, \frac{1}{2\pi K}\right) \subseteq A+B+C.$

Proof: Let ${f = 1_A \ast 1_B \ast 1_C}$. Note that we have ${\mathbf P_Z(A+B+C) \le K\mathbf P_Z A}$, while ${\mathbf E_ZA = (\mathbf P_ZA)^3}$. So by shifting ${C}$, we may assume without loss of generality that

$\displaystyle f(0) \ge \frac{(\mathbf P_ZA)^3}{K\mathbf P_ZA} \ge \frac{1}{K} (\mathbf P_ZA)^2.$

Now, consider ${x}$ in the Bohr set. Then we have

\displaystyle \begin{aligned} \left\lvert f(x)-f(0) \right\rvert &= \left\lvert \sum_\xi \widehat1_A(\xi) \widehat1_B(\xi) \widehat1_C(\xi) \left( e(\xi \cdot x) - 1 \right) \right\rvert \\ &\le \sum_\xi \left\lvert \widehat 1_A(\xi) \right\rvert \left\lvert \widehat 1_B(\xi) \right\rvert \left\lvert \widehat 1_C(\xi) \right\rvert \left\lvert e(\xi \cdot x) - 1 \right\rvert \\ &\le 2\pi \sum_\xi \left\lvert \widehat 1_A(\xi) \right\rvert \left\lvert \widehat 1_B(\xi) \right\rvert \left\lvert \widehat 1_C(\xi) \right\rvert \left\lVert \xi \cdot x \right\rVert_{\mathbb R/\mathbb Z}. \end{aligned}

Bounding by the maximum for ${A}$, and then using Cauchy-Schwarz,

\displaystyle \begin{aligned} \left\lvert f(x)-f(0) \right\rvert &\le 2\pi \sup_\xi \left( \left\lvert \widehat 1_A(\xi) \right\rvert \left\lVert \xi \cdot x \right\rVert_{\mathbb R/\mathbb Z} \right) \sum_\xi \left\lvert \widehat 1_B(\xi) \right\rvert \left\lvert \widehat 1_C(\xi) \right\rvert \\ &\le 2\pi \sup_\xi \left( \left\lvert \widehat 1_A(\xi) \right\rvert \left\lVert \xi \cdot x \right\rVert_{\mathbb R/\mathbb Z} \right) \sqrt{ \sum_\xi \left\lvert \widehat 1_B(\xi) \right\rvert^2 \sum_\xi \left\lvert \widehat 1_C(\xi) \right\rvert^2} \\ &\le 2\pi \mathbf P_Z A \cdot \sup_\xi \left( \left\lvert \widehat 1_A(\xi) \right\rvert \left\lVert \xi \cdot x \right\rVert_{\mathbb R/\mathbb Z} \right) \end{aligned}

Claim: if ${x \in \text{Bohr }(\text{Spec }_\alpha A, \frac{1}{2\pi K})}$ and ${\xi \in Z}$ then

$\displaystyle \left\lvert \widehat 1_A(\xi) \right\rvert \left\lVert \xi \cdot x \right\rVert_{\mathbb R/\mathbb Z} < \frac{1}{2\pi K} \mathbf P_ZA$

Indeed one just considers two cases:

• If ${\xi \in \text{Spec }_\alpha A}$, then ${\left\lVert \xi \cdot x \right\rVert_{\mathbb R/\mathbb Z} < \alpha}$ (${x}$ in Bohr set) and ${\left\lvert \widehat1_A(\xi) \right\rvert \le \mathbf P_ZA}$.
• If ${\xi \notin \text{Spec }_\alpha A}$, then ${\left\lvert \widehat 1_A(\xi) \right\rvert < \alpha \mathbf P_ZA}$ (${\xi}$ outside Spec) and ${\left\lVert \xi \cdot x \right\rVert_{\mathbb R/\mathbb Z} \le 1}$.

So finally, we have

$\displaystyle \left\lvert f(x)-f(0) \right\rvert < 2\pi \mathbf P_Z A \cdot \sup_\xi \left( \left\lvert \widehat 1_A(\xi) \right\rvert \right) < \frac{(\mathbf P_ZA)^2}{K} \le f(0)$

and this implies ${f(x) \neq 0}$. $\Box$

Once more by (1), we have

$\displaystyle \text{Bohr }\left(\{\eta_1, \dots, \eta_d\}, \frac{1}{2\pi Kd} \right) \subseteq \text{Bohr }\left( \text{Spec }_\alpha A, \frac{1}{2\pi K} \right) \subseteq A+B+C$

where

$\displaystyle d \ll \frac{1+\log \frac{1}{\mathbf P_ZA}}{\alpha^2} \ll K^2\left( 1 + \log \frac{1}{\mathbf P_Z A} \right).$

So there are the main theorem on Bohr sets again, there is a symmetric progression of density at least

$\displaystyle \left( \frac{\frac{1}{2\pi Kd}}{d} \right)^d \ll d^{-d}$

and rank at most ${d}$. This completes the proof of the second theorem.