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$