Probabilistic Tools - Introduction to Additive Combinatorics

3 Probabilistic Tools

All probability spaces in this course will be finite.

Theorem 3.1 (Khintchine’s inequality). Assuming that:

$p \in [2, \infty)$
$X_{1}, X_{2}, \dots, X_{n}$ independent random variables
$ℙ (X_{i} = x_{i}) = \frac{1}{2} = ℙ (X_{i} = - x_{i})$

Then

{∥ \sum_{i = 1}^{n} X_{i} ∥}_{L^{p} (ℙ)} = O (p^{\frac{1}{2}} {(\sum_{i = 1}^{n} ∥ X_{i} ∥_{L^{2} (ℙ)}^{2})}^{\frac{1}{2}}) .

Proof. By nesting of norms, it suffices to prove the case $p = 2 k$ for some $k \in ℕ$ . Write $X = \sum_{i = 1}^{n} X_{i}$ , and assume $\sum_{i = 1}^{n} ∥ X_{i} ∥_{L^{\infty} (ℙ)}^{2} = 1$ . Note that in fact $\sum_{i = 1}^{n} ∥ X_{i} ∥_{L^{2} (ℙ)}^{2} = \sum_{i = 1}^{n} ∥ X_{i} ∥_{L^{\infty} (ℙ)}^{2}$ , hence $\sum_{i = 1}^{n} ∥ X_{i} ∥_{L^{2} (ℙ)}^{2} = 1$ .

By Chernoff’s inequality (Example 2.5), for all $𝜃 > 0$ we have

ℙ (| X | \geq 𝜃) \leq 4 \exp (- \frac{𝜃^{2}}{4}),

and so using the fact that $ℙ (| X | \leq t) = \int_{0}^{t} ρ_{X} (s) d s$ we have

\begin{array}{l} ∥ X ∥_{L^{2 k} (ℙ)}^{2 k} & = \int_{0}^{\infty} t^{2 k} ρ_{X} (t) d t \\ = \int_{0}^{\infty} 2 k t^{2 k - 1} ℙ (| X | \geq t) d t & integration by parts \\ \leq \underset{= : I (K)}{\underset{⏟}{\int_{0}^{\infty} 8 k t^{2 k - 1} \exp (- \frac{t^{2}}{4}) d t}} \end{array}

We shall show by induction on $k$ that $I (K) \leq 2^{2 k} \frac{{(2 k)}^{k}}{4 k}$ . Indeed, when $k = 1$ ,

\int_{0}^{\infty} t \exp (- \frac{t^{2}}{4}) d t = {[- 2 \exp (- \frac{t^{2}}{4})]}_{0}^{\infty} = 2 \leq 2 .

For $k > 1$ , integrate by parts to find that

\begin{array}{l} I (K) & = \int_{0}^{\infty} \underset{u}{\underset{⏟}{t^{2 k - 2}}} \cdot \underset{v}{\underset{⏟}{t \exp (- \frac{t^{2}}{4})}} d t \\ = {[t^{2 k - 2} \cdot (- 2 \exp (- \frac{t^{2}}{4}))]}_{0}^{\infty} - \int_{0}^{\infty} (2 k - 2) t^{2 k - 3} (- 2 \exp (- \frac{t^{2}}{4})) d t \\ = 4 (k - 1) \int_{0}^{\infty} t^{2 (k - 1) - 1} \exp (- \frac{t^{2}}{4}) d t \\ = 4 (k - 1) I (K - 1) \\ \leq 4 (k - 1) 2^{2 (k - 1)} \frac{{(2 (k - 1))}^{k - 1}}{4 (k - 1)} \\ \leq 2^{2 k} \frac{{(2 k)}^{k}}{4 k} □ \end{array}

Corollary 3.2 (Rudin’s Inequality). Let $Γ \subseteq \hat{𝔽_{2}^{n}}$ be a linearly independent set and let $p \in [2, \infty)$ . Then for any $\hat{f} \in l^{2} (Γ)$ ,

{∥ \sum_{γ \in Γ} \hat{f} (γ) γ ∥}_{L^{P} (𝔽_{2}^{n})} = O (\sqrt{p} ∥ \hat{f} ∥_{l^{2} (Γ)}) .

Corollary 3.3. Let $Γ \subseteq \hat{𝔽_{2}^{n}}$ be a linearly independent set and let $p \in (1, 2]$ . Then for all $f \in L^{p} (𝔽_{2}^{n})$ ,

∥ \hat{f} ∥_{l^{2} (Γ)} = O (\sqrt{\frac{p}{p - 1}} ∥ f ∥_{L^{p} (𝔽_{2}^{n})}) .

Proof. Let $f \in L^{p} (𝔽_{2}^{n})$ and write $g = \sum_{γ \in Γ} \hat{f} (γ) γ$ . Then

\begin{array}{l} ∥ \hat{f} ∥_{l^{2} (Γ)}^{2} & = \sum_{γ \in Γ} | \hat{f} (γ) |^{2} \\ = {⟨ \hat{f}, \hat{g} ⟩}_{l^{2} (\hat{𝔽_{2}^{n}})} \\ = {⟨ f, g ⟩}_{L^{2} (𝔽_{2}^{n})} & by Plancherel’s identity \end{array}

which is bounded above by $∥ f ∥_{L^{p} (𝔽_{2}^{n})} ∥ g ∥_{L^{p^{'}} (𝔽_{2}^{n})}$ where $\frac{1}{p} + \frac{1}{p^{'}} = 1$ , using Hölder’s inequality.

By Rudin’s Inequality,

∥ g ∥_{L^{p^{'}} (𝔽_{2}^{n})} = O (\sqrt{p^{'}} ∥ \hat{g} ∥_{l^{2} (Γ)}) = O (\sqrt{\frac{p}{p - 1}} ∥ \hat{f} ∥_{l^{2} (Γ)}) . □

Recall that given $A \subseteq 𝔽_{2}^{n}$ of density $α > 0$ , we had $| {Spec}_{ρ} (𝟙_{A}) \leq ρ^{- 2} α^{- 1}$ . This is best possible as the example of a subspace shows. However, in this case the large spectrum is highly structured.

Theorem 3.4 (Special case of Chang’s Theorem). Assuming that:

$A \subseteq 𝔽_{2}^{n}$ of density $α > 0$
$ρ > 0$

Then there exists

H \leq \hat{𝔽_{2}^{n}}

of dimension

O (ρ^{- 2} \log α^{- 1})

such that

H \supseteq {Spec}_{ρ} (𝟙_{A})

Proof. Let $Γ \subseteq {Spec}_{ρ} (𝟙_{A})$ be a maximal linearly independent set. Let $H = ⟨ {Spec}_{ρ} (𝟙_{A}) ⟩$ . Clearly $\dim (H) = | Γ |$ . By Corollary 3.3, for all $p \in (1, 2]$ ,

{(ρ α)}^{2} | Γ | \leq \sum_{γ \in Γ} | \hat{𝟙_{A}} (γ) |^{2} = ∥ \hat{𝟙_{A}} ∥_{l^{2} (Γ)}^{2} = O (\frac{p}{p - 1} ∥ 𝟙_{A} ∥_{L^{p} (𝔽_{2}^{n})}^{2}),

| Γ | = O (ρ^{- 2} α^{- 2} α^{2 ∕ p} \frac{p}{p - 1}) .

Set $p = 1 + {(\log α^{- 1})}^{- 1}$ to get $| Γ | = O (ρ^{- 2} α^{- 2} (α^{2} \cdot e^{2}) (\log α^{- 1} + 1))$ . □

Definition 3.5 (Dissociated). Let $G$ be a finite abelian group. We say $S \subseteq G$ is dissociated if $\sum_{s \in S} 𝜀_{s} s = 0$ for $𝜀 \in {- 1, 0, 1}^{| S |}$ , then $𝜀 \equiv 0$ .

Clearly, if $G = 𝔽_{2}^{n}$ , then $S \subseteq G$ is dissociated if and only if it is linearly independent.

Theorem 3.6 (Chang’s Theorem). Assuming that:

$G$ a finite abelian group
$A \subseteq G$ be of density $α > 0$
$Λ \supseteq {Spec}_{ρ} (𝟙_{A})$ is dissociated

Then

| Λ | = O (ρ^{- 2} \log α^{- 1}

We may bootstrap Khintchine’s inequality to obtain the following:

Theorem 3.7 (Marcinkiewicz-Zygmund). Assuming that:

$p \in [2, \infty)$
$X_{1}, X_{2}, \dots, X_{n} \in Ł^{p} (ℙ)$ independent random variables
$𝔼 \sum_{i = 1}^{n} X_{i} = 0$

Then

{∥ \sum_{i = 1}^{n} X_{i} ∥}_{L^{p} (ℙ)} = O (p^{\frac{1}{2}} {∥ \sum_{i = 1}^{n} | X_{i} |^{2} ∥}_{L^{p ∕ 2} (ℙ)}^{\frac{1}{2}}) .

Proof. First assume the distribution of the $X_{i}$ ’s is symmetric, i.e. $ℙ (X_{i} = a) = ℙ (X_{i} = - a)$ for all $a \in ℝ$ . Partition the probability space $Ω$ into sets $Ω_{1}, Ω_{2}, \dots, Ω_{M}$ , write $ℙ_{j}$ for the induced measure on $Ω_{j}$ such that all $X_{i}$ ’s are symmetric and take at most 2 values. By Khintchine’s inequality, for each $j \in [M]$ ,

\begin{array}{l} {∥ \sum_{i = 1}^{n} X_{i} ∥}_{L^{p} (ℙ_{j})}^{p} & = O (p^{p ∕ 2} {(\sum_{i = 1}^{n} ∥ X_{i} ∥_{L^{2} (ℙ_{j})}^{2})}^{p ∕ 2}) \\ = O (p^{p ∕ 2} {∥ \sum_{i = 1}^{n} | X_{i} |^{2} ∥}_{L^{p ∕ 2} (ℙ_{j})}^{p ∕ 2}) \end{array}

so summing over all $j$ and taking $p$ -th roots gives the symmetric case. Now suppose the $X_{i}$ ’s are arbitrary, and let $Y_{1}, \dots, Y_{n}$ be such that $Y_{i} \sim X_{i}$ and $X_{1}, X_{2}, \dots, X_{n}, Y_{1}, Y_{2}, \dots, Y_{n}$ are all independent. Applying the symmetric case to $X_{i} - Y_{i}$ ,

\begin{array}{l} {∥ \sum_{i = 1}^{n} (X_{i} - Y_{i}) ∥}_{L^{p} (ℙ \times ℙ)} & = O (p^{\frac{1}{2}} {∥ \sum_{i = 1}^{n} | X_{i} - Y_{i} |^{2} ∥}_{L^{p ∕ 2} (ℙ \times ℙ)}^{\frac{1}{2}}) \\ = O (p^{\frac{1}{2}} {∥ \sum_{i = 1}^{n} | X_{i} - Y_{i} |^{2} ∥}_{L^{p ∕ 2} (ℙ)}^{\frac{1}{2}}) \end{array}

But then

\begin{array}{l} {∥ \sum_{i = 1}^{n} X_{i} ∥}_{L^{p} (ℙ)} = {∥ \sum_{i = 1}^{n} X_{i} - \underset{= 0}{\underset{⏟}{𝔼^{Y} \sum_{i = 1}^{n} Y_{i}}} ∥}_{L^{p} (ℙ)}^{p} \\ = 𝔼^{X} {| \sum X_{i} - 𝔼^{Y} \sum Y_{i} |}^{p} \\ = 𝔼^{X} {| 𝔼^{Y} \sum (X_{i} - Y_{i}) |}^{p} \\ \leq 𝔼^{X} 𝔼^{Y} {| \sum (X_{i} - Y_{i}) |}^{p} & by Jensen say \\ = {∥ \sum (X_{i} - Y_{i}) ∥}_{L^{p} (ℙ \times ℙ)}^{p} \end{array}

concluding the proof. □

Theorem 3.8 (Croot-Sisask almost periodicity). Assuming that:

$G$ a finite abelian group
$𝜀 > 0$
$p \in [2, \infty)$
$A, B \subseteq G$ are such that $| A + B | \leq K | A |$
$f : G \to ℂ$

Then there exists

b \in B

and a set

X \subseteq B - b

such that

| X | \geq 2^{- 1} K^{- O (𝜀^{- 2} p)} | B |

and

∥ τ_{x} f * μ_{A} - f * μ_{A} ∥_{L^{p} (G)} \leq 𝜀 ∥ f ∥_{L^{p} (G)} \forall x \in X,

where $τ_{x} g (y) = g (y + x)$ for all $y \in G$ , and as a reminder, $μ_{A}$ is the characteristic measure of $A$ .

Proof. The main idea is to approximate

f * μ_{A} (y) = 𝔼_{x} f (y - x) μ_{A} (x) = 𝔼_{x \in A} f (y - x)

by $\frac{1}{m} \sum_{i = 1}^{m} f (y - z_{i})$ , where $z_{i}$ are sampled independently and uniformly from $A$ , and $m$ is to be chosen later.

For each $y \in G$ , define $Z_{i} (y) = τ_{- z i} f (y) - f * μ_{A} (y)$ . For each $y \in G$ , these are independent random variables with mean $0$ , so by Marcinkiewicz-Zygmund,

\begin{array}{l} {∥ \sum_{i = 1}^{m} Z_{i} (y) ∥}_{L^{p} (ℙ)}^{p} & = O (p^{p ∕ 2} {∥ \sum_{i = 1}^{m} | Z_{i} (y) |^{2} ∥}_{L^{p ∕ 2} (ℙ)}^{p ∕ 2}) \\ = O (p^{p ∕ 2} 𝔼_{(z_{1}, \dots, z_{m}) \in A^{m}} {| \sum_{i = 1}^{m} | Z_{i} (y) |^{2} |}^{p ∕ 2}) \end{array}

By Hölder with $\frac{1}{p^{'}} + \frac{2}{p} = 1$ , we get

\begin{array}{l} {| \sum_{i = 1}^{m} | Z_{i} (y) |^{2} |}^{p ∕ 2} & \leq {(\sum_{i = 1}^{m} 1^{p^{'}})}^{\frac{1}{p^{'}} \cdot \frac{p}{2}} {(\sum_{i = 1}^{m} | Z_{i} (y) |^{2 \cdot p ∕ 2})}^{\frac{2}{p} \cdot \frac{p}{2}} \\ \leq {(\sum_{i = 1}^{m} 1^{p^{'}})}^{\frac{p}{2} - 1} {(\sum_{i = 1}^{m} | Z_{i} (y) |^{2 \cdot p ∕ 2})}^{\frac{2}{p} \cdot \frac{p}{2}} \\ = m^{p ∕ 2 - 1} \sum_{i = 1}^{m} | Z_{i} (y) |^{p} \end{array}

{∥ \sum_{i = 1}^{m} Z_{i} (y) ∥}_{L^{p} (ℙ)}^{p} = O (p^{p ∕ 2} m^{p ∕ 2 - 1} 𝔼_{(z_{1}, \dots, z_{m}) \in A^{m}} \sum_{i = 1}^{m} | Z_{i} (y) |^{p}) .

Summing over all $y \in G$ , we have

𝔼_{y \in G} {∥ \sum_{i = 1}^{m} Z_{i} (y) ∥}_{L^{p} (ℙ)}^{p} = O (p^{p ∕ 2} m^{p ∕ 2 - 1} 𝔼_{(z_{1}, \dots, z_{m}) \in A^{m}} \sum_{i = 1}^{m} 𝔼_{y \in G} | Z_{i} (y) |^{p})

with

\begin{array}{l} {(𝔼_{y \in G} | Z_{i} (y) |^{p})}^{\frac{1}{p}} & = ∥ Z_{i} ∥_{L^{p} (G)} \\ = ∥ τ_{- z_{i}} f - f * μ_{A} ∥_{L^{p} (G)} \\ \leq, ∥ τ_{- z_{i}} f ∥_{L^{p} (G)} + ∥ f * μ_{A} ∥_{L^{p} (G)} \\ \leq ∥ f ∥_{L^{p} (G)} + ∥ f ∥_{L^{q} (G)} ∥ μ_{A} ∥_{L^{1} (G)} \\ \leq 2 ∥ f ∥_{L^{p} (G)} \end{array}

by Young / Hölder ( $∥ f * g ∥_{L^{r} (G)} \leq ∥ f ∥_{L^{p} (G)} ∥ g ∥_{L^{q} (G)}$ where $1 + \frac{1}{r} = \frac{1}{p} + \frac{1}{q}$ ).

So we have

𝔼_{(z_{1}, \dots, z_{m}) \in A^{m}} 𝔼_{y \in G} {| \sum_{i = 1}^{m} Z_{i} (y) |}^{p} = O (p^{p ∕ 2} m^{p ∕ 2 - 1} \sum_{i = 1}^{m} {(2 ∥ f ∥_{L^{p} (G)})}^{p}) = O ({(4 p)}^{p ∕ 2} m^{p ∕ 2} ∥ f ∥_{L^{p} (G)}^{p}) .

Choose $m = O (𝜀^{- 2} p)$ so that the RHS is at most ${(\frac{𝜀}{4} ∥ f ∥_{L^{p} (G)})}^{p}$ . whence

𝔼_{(z_{1}, \dots, z_{m}) \in A^{m}} \underset{= (*)}{\underset{⏟}{𝔼_{y \in G} {| \frac{1}{m} \sum_{i = 1}^{m} τ_{- z i} f (y) - f * μ_{A} (y) |}^{p}}} = O ({(4 p)}^{p ∕ 2} m^{p ∕ 2} ∥ f ∥_{L^{p} (G)}^{p}) = {(\frac{𝜀}{4} ∥ f ∥_{L^{p} (G)})}^{p} .

Write

L = {z = (z_{1}, \dots, z_{m}) \in A^{m} : (*) \leq {(\frac{𝜀}{2} ∥ f ∥_{L^{p} (G)})}^{p}} .

By Markov inequality, since

𝔼 (*) \leq {(\frac{𝜀}{4} ∥ f ∥_{L^{p} (G)})}^{p} = 2^{- p} {(\frac{𝜀}{2} ∥ f ∥_{L^{p} (G)})}^{p},

we have

\frac{| A^{m} ∖ L |}{| A^{m} |} = ℙ ((*) \geq {(\frac{𝜀}{2} ∥ f ∥_{L^{p} (G)})}^{p}) \leq ℙ ((*) \geq 2^{p} 𝔼 (*)) \leq 2^{- p}

so $| L | \geq (1 - \frac{1}{2^{p}}) | A |^{m} \geq \frac{1}{2} | A |^{m}$ . Let

D = {\underset{m}{\underset{⏟}{(b, b, \dots, b)}} : b \in B} .

Now $L + D \subseteq {(A + B)}^{m}$ , whence

| L + D | \leq | A + B |^{m} \leq K^{m} | A |^{m} \leq 2 K^{m} | L | .

By Lemma 1.17,

E (L, D) \geq \frac{| L |^{2} | D |^{2}}{| L + D |} \geq \frac{1}{2} K^{- m} | D |^{2} | L |

so there are at least $\frac{| D |^{2}}{2 K^{m}}$ pairs $(d_{1}, d_{2}) \in D \times D$ such that $r_{L - L} (d_{2} - d_{1}) > 0$ . In particular, there exists $b \in u b$ and $X \subseteq B - b$ of size $| X | \geq \frac{| D |}{2 K^{m}} = \frac{| B |}{2 K^{m}}$ such that for all $x \in X$ , there exists $l_{2} (x) \in L$ such that for all $i \in [m]$ , $l_{1} {(x)}_{i} - l_{2} {(x)}_{i} = x$ . But then for each $x \in X$ , by the triangle inequality,

\begin{array}{l} ∥ τ_{- x} f * μ_{A} - f * μ_{A} ∥_{L^{p} (G)} & \leq {∥ τ_{- x} f * μ_{A} - τ_{- x} (\frac{1}{m} \sum_{i = 1}^{m} τ_{- l_{2} {(x)}_{i}} f) ∥}_{L^{p} (G)} \\ + {∥ τ_{- x} (\frac{1}{m} \sum_{i = 1}^{m} τ_{- l_{2} (x_{i})} f) - f * μ_{A} ∥}_{L^{p} (G)} \\ = {∥ f * μ_{A} - \frac{1}{m} \sum_{i = 1}^{m} τ_{- l_{2} {(x)}_{i}} f ∥}_{L^{p} (G)} \\ + {∥ \frac{1}{m} \sum_{i = 1}^{m} τ_{- x - l_{2} {(x)}_{i}} f - f * μ_{A} ∥}_{L^{p} (G)} \\ \leq 2 \cdot \frac{𝜀}{2} ∥ f ∥_{L^{p} (G)} \end{array}

by definion of $L$ . □

Theorem 3.9 (Bogolyubov again, after Sanders). Assuming that:

$A \subseteq 𝔽_{p}^{n}$ of density $α > 0$

Then there exists a subspace

V \leq 𝔽_{p}^{n}

of codimension

O (\log^{4} α^{- 1})

such tht

V \subseteq A + A - A - A

Almost periodicity is also a key ingredient in recent work of Kelley and Meka, showing that any $A \subseteq [N]$ containing no non-trivial 3 term arithmetic progressions has size $| A | \leq \exp (- C \log^{\frac{1}{11}} N) N$ .