The Green–Tao Theorem - Higher-order Uniformity and Applications

3 The Green–Tao Theorem

Theorem 3.1. For all $k \geq 3$ , the primes contain an arithmetic progression of length $k$ .

Theorem 3.2 (Weighted Szemerédi). For all $k \geq 3$ and $α > 0$ , there exists $c = c (k, α) > 0$ such that for any function $f : ℤ ∕ N ℤ \to [0, 1]$ satisfying $𝔼 f = α$ ,

𝔼_{x, d} f (x) f (x + d) \dots f (x + (k - 1) d) > c (k, α) - o_{k, α} (1),

where $o_{k, α} (1)$ is a quantity that goes to $0$ as $n \to \infty$ at a rate that depending on $k$ and $α$ .

There is a standard method that allows converting between a statement like the above about $ℤ ∕ N ℤ$ into a statement about $[N]$ : given a subset of $[N]$ , just view it as a subset of $ℤ ∕ 3 N ℤ$ (arithmetic progressions in $ℤ ∕ 3 N ℤ$ that lie in $[N]$ correspond to genuine arithmetic progressions in $[N]$ ).

Insight of Green and Tao: the primes are dense in a certain subset of the naturals.

We will use some results of Conlon–Fox–Zhao which are sparse versions of the hypergraph regularity results we saw earlier. We will only prove one of these results in lectures, which is the sparse counting lemma.

Definition 3.3. A function $ν = ν^{(N)} : ℤ ∕ N ℤ \to [0, \infty)$ is said to satisfy the $k$ -linear forms condition ( $k$ -LFC) if

𝔼_{\begin{array}{c} x_{1}^{(0)}, x_{1}^{(1)} \\ ⋮ \\ x_{k}^{(0)}, x_{k}^{(1)} \end{array}} \prod_{j = 1}^{k} \prod_{ω \in {0, 1}^{[k] ∖ {j}}} ν {(\sum_{i = 1}^{k} (i - j) x_{i}^{(ω_{i})})}^{n_{j, ω}} = 1 + o (1)

for any choice of exponents $n_{j, ω} \in {0, 1}$ .

Example 3.4. We will omit writing out the $n_{j, ω}$ in this example.

$ν$ satisfies the $2$ -LFC if

𝔼_{\begin{array}{c} x, x^{'} \\ y, y^{'} \end{array}} ν (y) ν (y^{'}) ν (- x) ν (x^{'}) = 1 + o (1) .

$ν$ satisfies the $3$ -LFC if

𝔼_{\begin{array}{c} x, x^{'} \\ y, y^{'} \\ z, z^{'} \end{array}} ν (y + 2 z) ν (y^{'} + 2 z) ν (y + 2 z^{'}) ν (y^{'} + 2 z^{'}) ν (- x + z) ν (- x^{'} + z) ν (- x + z^{'}) ν (- x^{'} + z^{'}) ν (- 2 x - y) ν (- 2 x^{'} - y) ν (- 2 x - y^{'}) ν (- 2 x - y^{'}) = 1 + o (1) .

$ν (y + 2 z) ν (- x + z) ν (- 2 x - y)$ relates to three term progressions: it is the arithmetic progression $y + 2 z + n (- x - y - z)$ for $n = 0, 1, 2$ .

Theorem 3.5 (Relative Szemerédi). Let $k \geq 3$ and $α > 0$ and suppose $ν = ν^{(N)} : ℤ ∕ N ℤ \to [0, 1]$ satisfies the $k$ -LFC. Suppose $N$ is sufficiently large and coprime to $(k - 1)!$ . Let $f : ℤ ∕ N ℤ \to [0, \infty)$ satisfies $0 \leq f (x) \leq ν (x)$ for all $x \in ℤ ∕ N ℤ$ and suppose $𝔼 f \geq α$ . Then

𝔼_{x, d} f (x) f (x + d) \dots f (x + (k - 1) d) \geq c (k, α) - o_{k, α, \underset{rate of convergence in k -LFC}{\underset{⏟}{ν}}} (1)

where $c (k, α)$ is as in Theorem 3.2. Often refer to $ν$ as a pseudorandom majorant for $f$ .

Note: taking $f$ here to be the indicator of the primes won’t satisfy the conditions above, because we need $𝔼 f \geq α$ . Instead, we’ll use the fact that $f$ is not bounded (takes values in $[0, \infty)$ ).

Think of “ $f (n) = 𝟙_{primes} (n) \cdot \log n$ .”

In the original Green–Tao proof, they needed an additional condition as well as the $k$ -LFC, and this additional requires a lot of analytic number theory to prove. One of the great contributions of the proof by Conlon–Fox–Zhao was to remove this additional condition, and in particular greatly reducing the amount of analytic number theory needed to prove the result.

Consider the van Mangoldt function

Λ (n) = {\begin{matrix} \log p & if n = p^{k} for some prime p \\ 0 & otherwise \end{matrix}

By the Prime Number Theorem,

𝔼_{n \in [N]} Λ (n) = 1 + o (1) .

(Remark: we won’t need the Prime Number Theorem to prove Green–Tao)

Problem: $Λ$ is biased with respect to small residue classes. Use $W$ -trick: let $w = w (N)$ be a function $\to \infty$ with $N$ e.g. $\sim \log \log N$ . Let $W = \prod_{p \leq w} p$ , and consider only primes $\equiv 1 (m o d W)$ , by defining

\tilde{Λ (n)} = {\begin{matrix} \frac{φ (W)}{W} \log (W n + 1) & if W n + 1 is prime \\ 0 & otherwise \end{matrix}

where $φ$ is the Euler totient function. Can show $𝔼_{n \in [N]} \tilde{Λ} (n) = 1 + o (1)$ , provided $w$ grows sufficiently slowly.

Reminder: instead of $Λ$ , want to consider

\tilde{Λ} (n) = {\begin{matrix} \frac{φ (W)}{W} \log (W n + 1) & if W n + 1 prime \\ 0 & otherwise \end{matrix}

Proposition 3.6 (Pseudorandom majorant for the primes). For all $k \geq 3$ , there exists $δ > 0$ such that for all sufficiently large $N$ , there exists $ν^{(N)} : ℤ ∕ N ℤ \to [0, \infty)$ satisfying the $k$ -LFC and $ν (n) \geq δ_{k} \tilde{Λ} (n)$ for all $n \in [N ∕ 2, N)$ . $ν$ is given by

ν (n) = {\begin{matrix} \frac{φ (W)}{W} \frac{Λ_{χ, R} {(W n + 1)}^{2}}{c_{χ} \log R} & n \in [N ∕ 2, N) \\ 1 & otherwise \end{matrix}

where

$χ : ℝ \to [0, 1]$ is a smooth function supported on $[- 1, 1]$ with $χ (0) = 1$
$c_{χ} = \int_{0}^{\infty} | χ^{'} (x) |^{2} d x$
$R = N^{k^{- 1} 2^{- k - 3}}$ .
$Λ_{χ, R} (n) = \log R \sum_{d | n} μ (d) χ (\frac{\log d}{\log R})$ .
Compare with $Λ (n) = \sum_{d | n} μ (d) \log (\frac{n}{d})$ and $\sum_{\begin{array}{c} d | n \\ d \leq R \end{array}} \log \frac{R}{d}$ .

Proof. Omitted. □

Next goal: “Approximate” $0 \leq f \leq ν$ by $0 \leq \tilde{f} \leq 1$ with $𝔼 f = 𝔼 \tilde{f}$ (transference principle).

Definition 3.7. Let $G$ be an abelian group (which you can think of as being $ℤ ∕ N ℤ$ ), let $r \in ℕ$ , and let $ψ : G^{r} \to G$ a surjective homomorphism, $f, \tilde{f} : G \to [0, \infty)$ . We say $(f, \tilde{f})$ is an $(r, 𝜀)$ -discrepancy pair (DP) with respect to $ψ$ if

| 𝔼_{x = (x_{1}, \dots, x_{r}) \in G^{r}} (f (ψ (x)) - \tilde{f} (ψ (x))) \prod_{i = 1}^{r} u_{i} (\underset{= (x_{1}, \dots, x_{i - 1}, x_{i + 1}, \dots, x_{r})}{\underset{⏟}{x_{[r] ∖ {i}}}}) | \leq 𝜀

for all functions $u_{1}, \dots, u_{r} : G^{r - 1} \to [0, 1]$ .

In words: no function in fewer variables can distinguish $f$ from $\tilde{f}$ .

Can think of $ψ (x) = x_{1} + x_{2} + \dots + x_{r}$ .

Theorem 3.8 (Dense Model Theorem). For all $𝜀 > 0$ , there exists $k = 𝜀^{- O (1)}$ and $𝜀^{'} = \exp (- 𝜀^{- O (1)})$ such that the following holds: Let $X$ be a finite set, let $F$ be a collection of functions $φ : X \to [- 1, 1]$ . Suppose $ν : X \to [0, \infty)$ satisfying

| ⟨ ν - 1, φ ⟩ | \leq 𝜀^{'} \forall φ \in F^{k} = {\prod_{i = 1}^{k} φ_{i} : φ_{i} \in F, k^{'} \leq k}

and $f : X \to [0, \infty)$ satisfies $f \leq ν$ and $𝔼 f \leq 1$ . Then there exists $\tilde{f} : X \to [0, 1]$ such that $𝔼 \tilde{f} = 𝔼 f$ and $| ⟨ f - \tilde{f}, φ ⟩ | \leq 𝜀$ for all $φ \in F$ .

Corollary 3.9. For all $𝜀 > 0$ , there exists $𝜀^{'} = \exp (- 𝜀^{- O (1)})$ such that the following holds: Let $G$ be an abelian group, $r \in ℕ$ , $ψ : G^{r} \to G$ a surjective homomorphism. Let $f, ν : G \to [0, \infty)$ be such that $0 \leq f \leq ν$ , $𝔼 f \leq 1$ and $(ν, 1)$ is an $(r, 𝜀^{'})$ -discrepancy pair with respect to $ψ$ . Then there exists $\tilde{f} : G \to [0, 1]$ such that $𝔼 \tilde{f} = 𝔼 f$ and $(f, \tilde{f})$ is an $(r, 𝜀)$ -discrepancy pair with respect to $ψ$ .

Deduction from Theorem 3.8. For any collection of functions $u_{1}, \dots, u_{r} : G^{r - 1} \to [0, 1]$ , define a generalized convolution with respect to $ψ$

\begin{array}{l} {(u_{1}, \dots, u_{r})}_{ψ}^{*} : G & \to [0, 1] \\ {(u_{1}, \dots, u_{r})}_{ψ}^{*} (x) & = 𝔼_{\begin{array}{c} y \in G^{r} \\ ψ (y) = x \end{array}} \prod_{i = 1}^{r} u_{i} (y_{[r] ∖ {i}}) \end{array}

$r = 2$ :

u_{1} * u_{2} (x) = 𝔼_{\begin{array}{c} y \in G^{2} \\ y_{1} + y_{2} = x \end{array}} u_{1} (y_{1}) u_{2} (y_{2})

So indeed the earlier expression looks like a reasonable definition for a generalised convolution.

Notice that the LHS in ?? 30 is just $⟨ f - \tilde{f}, {(u_{1} \dots u_{r})}_{ψ}^{*} ⟩$ .

Let $F$ be the set of functions which can be written as convex combinations of generalised convolutions with respect to $ψ$ . Then by the hypotheses, $(ν, 1)$ is an $(r, 𝜀^{'})$ -discrepancy pair with respect to $ψ$ , which is equivalent to $⟨ ν - 1, φ ⟩ \leq 𝜀^{'}$ for all $φ \in F$ .

Want: $| ⟨ f - \tilde{f}, φ ⟩ | \leq 𝜀$ for all $φ \in F$ .

So it suffices to show that $F$ is closed under multiplication. Indeed,

\begin{array}{l} {(u_{1}, \dots, u_{r})}_{ψ}^{*} (x) {(u_{1}^{'}, \dots, u_{r}^{'})}_{ψ}^{*} (x) & = 𝔼_{\begin{array}{c} y \in G^{r} \\ ψ (y) = x \end{array}} 𝔼_{\begin{array}{c} y^{'} \in G^{r} \\ ψ (y) = x \end{array}} \prod_{i = 1}^{r} u_{i} (y_{[r] ∖ {i}}) \prod_{i = 1}^{r} u_{i}^{'} (\underset{= y_{[r] ∖ {i}} + z_{[r] ∖ {i}}}{\underset{⏟}{y_{[r] ∖ {i}}^{'}}}) \\ = 𝔼_{\begin{array}{c} z \in G^{r} \\ ψ (z) = 0 \end{array}} [\underset{generalised convolution wrt ψ}{\underset{⏟}{𝔼_{\begin{array}{c} y \in G^{r} \\ ψ (y) = x \end{array}} \prod_{i = 1}^{r} u_{i} (y_{[r] ∖ {i}}) u_{i}^{″} (y_{[r] ∖ {i}})}}] □ \end{array}

Define a norm on functions $f : G^{r} \to ℝ$ by

∥ f ∥ = (∥ f ∥_{□, r}) = \sup_{φ \in F} | ⟨ f, φ ⟩ | = \sup_{φ \in F \cup (- F)} ⟨ f, φ ⟩

This has a dual:

∥ φ ∥^{*} = \sup_{∥ f ∥ \leq 1} ⟨ f, φ ⟩ .

By definition, $| ⟨ f, φ ⟩ | \leq ∥ f ∥ ∥ φ ∥^{*}$ . Note

∥ f ∥ = \sup_{φ \in F} | ⟨ f, φ ⟩ | = \sup_{φ \in F} | 𝔼_{x} f (x) φ (x) | \leq ∥ f ∥_{1},

and by duality

∥ φ ∥^{*} \geq ∥ φ ∥_{\infty} .

Lemma 3.10. The unit ball of $∥ ∙ ∥^{*}$ is just $conv (F \cup (- F))$ .

We will use Hahn–Banach to prove this.

Theorem 3.11 (Hahn–Banach). Let $K$ be a closed convex body in $ℝ^{n}$ , and suppose $𝜃 \in ℝ^{n} ∖ K$ . Then there exists $f \in ℝ^{n}$ such that $⟨ f, 𝜃 ⟩ > 1$ while $⟨ f, η ⟩ \leq 1 \forall η \in K$ .

Proof. Suppose $φ \in F \cup (- F)$ . Then

∥ φ ∥^{*} = \sup_{∥ f ∥ \leq 1} ⟨ f, φ ⟩ \leq 1 .

So $φ$ is in the unit ball of $∥ ∙ ∥^{*}$ . Convex combinations of elements in $F \cup (- F)$ are also in the unit ball by the triangle inequality.

For the converse, we need Hahn–Banach. Suppose $φ \notin conv (F \cup (- F))$ . By Theorem 3.11, there exists $f$ such that $⟨ f, φ ⟩ > 1$ but $⟨ f, η ⟩ \leq 1 \forall η \in conv (F \cup (- F))$ . The latter implies $∥ f ∥ \leq 1$ . But

1 < ⟨ f, φ ⟩ \leq ∥ f ∥ ∥ φ ∥^{*} \leq ∥ φ ∥^{*} .

Hence $φ$ does not lie in the unit ball of $∥ ∙ ∥^{*}$ . □

This implies that the unit ball of $∥ ∙ ∥^{*}$ is closed under multiplication. Hence, $\forall φ, ψ : G \to ℝ$ , then

{∥ \frac{φ}{∥ φ ∥^{*}} \frac{ψ}{∥ ψ ∥^{*}} ∥}^{*} \leq 1 ⟹ ∥ φ ψ ∥^{*} \leq ∥ φ ∥^{*} ∥ ψ ∥^{*} .

(dual norm is submultiplicative).

Theorem 3.12 (Dense Model (Theorem 3.7’)). For all $𝜀 > 0$ , if $ν : X \to [0, \infty)$ satisfying $∥ ν - 1 ∥ \leq \exp (- 𝜀^{- O (1)})$ and $f : X \to [0, \infty)$ satisfies $0 \leq f \leq ν$ , then there exists $\tilde{f} : X \to [0, 1]$ such that $∥ f - \tilde{f} ∥ \leq 𝜀$ .

Proof. Given $f : X \to [0, \infty)$ , $0 \leq f \leq ν$ , it suffices to show that there exists $\tilde{f} : X \to [0, 1 + \frac{𝜀}{2}]$ with $∥ f - \tilde{f} ∥ \leq \frac{𝜀}{2}$ , assuming that $∥ ν - 1 ∥ \leq 𝜀^{'}$ for some sufficiently small $𝜀^{'}$ .

Suppose that there is no such $\tilde{f}$ , i.e. $f$ cannot be written as $f = f_{1} + f_{2}$ , with

f_{1} \in K_{1} = {g : X \to [0, 1 + 𝜀 ∕ 2]} and f_{2} \in K_{2} = {h : X \to ℝ : ∥ h ∥ \leq 𝜀 ∕ 2} .

In other words: we are supposing that $f \notin K_{1} + K_{2}$ . Note that $K_{1}$ and $K_{2}$ are both convex bodies, and both contain $0$ . Thus $K_{1} + K_{2}$ is convex and contains $K_{1}$ and $K_{2}$ .

By Hahn–Banach, there exists $ψ : X \to ℝ$ such that $⟨ f, ψ ⟩ > 1$ and $⟨ g, ψ ⟩ \leq 1 \forall g \in K_{1} + K_{2}$ . Taking $g = (1 + \frac{𝜀}{2}) 𝟙_{ψ > 0} \in K_{1}$ , we note that

⟨ (1 + 𝜀 ∕ 2) 𝟙_{ψ > 0}, ψ ⟩ = ⟨ (1 + 𝜀 ∕ 2), ψ_{+} ⟩ \leq 1

where $ψ_{+} (x) = \max {0, ψ (x)}$ . Thus $⟨ 1, ψ_{+} ⟩ \leq {(1 + 𝜀 ∕ 2)}^{- 1}$ .

On the other hand, if $⟨ g, ψ ⟩ \leq 1 \forall g \in K_{2}$ , so $⟨ g^{'}, ψ ⟩ \leq \frac{2}{𝜀}$ for all $g^{'} : X \to ℝ$ with $∥ g^{'} ∥ \leq 1$ . So $∥ ψ ∥^{*} \leq \frac{2}{𝜀}$ .

So far, we have

1 < ⟨ f, ψ ⟩ \leq ⟨ f, ψ_{+} ⟩ \leq ⟨ ν, ψ_{+} ⟩ = ⟨ ν - 1, ψ_{+} ⟩ + \underset{\leq {(1 + 𝜀 ∕ 2)}^{- 1}}{\underset{⏟}{⟨ 1, ψ_{+} ⟩}} .

So if we had $∥ ψ_{+} ∥^{*}$ bounded above, we would be done. Indeed, by Weierstrass approximation, there exists a polynomial $P$ such that

| P (x) - \max {0, x} | \leq \frac{𝜀}{8} \forall x \in [- \frac{2}{𝜀}, \frac{2}{𝜀}] .

Recall that earlier we used duality to show $∥ ψ ∥_{\infty} \leq ∥ ψ ∥^{*} \leq \frac{2}{𝜀}$ , which is why we only need the polynomial approximation to hold in the interval $[- \frac{2}{𝜀}, \frac{2}{𝜀}]$ .

Let $P (x) = a_{d} x^{d} + \dots + a_{1} x + a_{0}$ . We can do this with $R : = \sum_{i = 0}^{d} | a_{i} | {(\frac{2}{𝜀})}^{i} = \exp (- 𝜀^{- O (1)})$ . Now

∥ P ψ ∥^{*} \leq \sum_{i = 1}^{d} | a_{i} | ∥ ψ^{i} ∥^{*} \leq \sum_{i = 1}^{d} | a_{i} | {(∥ ψ ∥^{*})}^{i} \leq R

and

⟨ ν - 1, ψ_{+} ⟩ = ⟨ ν - 1, P ψ ⟩ + ⟨ ν - 1, ψ_{+} - P ψ ⟩ \leq \underset{\leq 𝜀^{'} \cdot R}{\underset{⏟}{∥ ν - 1 ∥ ∥ P ψ ∥^{*}}} + \underset{\leq 1}{\underset{⏟}{∥ ν - 1 ∥_{1}}} \underset{\leq \frac{𝜀}{8}}{\underset{⏟}{∥ ψ_{+} - P ψ ∥_{\infty}}} .

Choosing $𝜀^{'}$ such that $𝜀^{'} \cdot R \leq \frac{𝜀}{8}$ , we arrive at a contradiction. □

$X = X_{1} \cup X_{2} \cup X_{3} \cup X_{4}$ .

$X_{- i}$ means $X_{1} \cup \dots \cup X_{i - 1} \cup X_{i + 1} \cup \dots \cup X_{4}$ . $x_{- i} = (x_{1}, \dots, x_{i - 1}, x_{i + 1}, x_{4}) \in X_{- i}$ . (for all $i \in [4]$ )

Work with $4$ -partite $3$ -uniform weighted hypergraphs.

g = {(g_{- i})}_{i \in [4]}

with each $g_{- i} : X_{- i} \to ℝ$ . For two such hypergraphs, $g$ and $ν$ , write $g \leq ν$ whenever $g_{- i} (x_{- i}) \leq ν_{- i} (x_{- i})$ for all $i \in [4]$ and all $x_{- i} \in X_{- i}$ .

Given a weighted $3$ -uniform hypergraph $h$ on $X_{- i}$ , define

∥ h ∥_{□, i} = \sup_{A_{j} \subseteq X_{- j}} | 𝔼_{x_{- i} \in X_{- i}} h (x_{- i}) \prod_{j \in [4] ∖ {i}} 𝟙_{A_{j}} (x_{- i, - j}) | .

Given a weighted $4$ -partite $3$ -uniform hypergraph on $X$ , define

∥ g ∥_{□} = \max_{i \in [4]} {∥ g_{- i} ∥_{□, i}} .

Definition 3.13. Say that a $4$ -partite $3$ -uniform weighted hypergraph $ν$ satisfies the $3$ -LFC if

𝔼_{\begin{array}{c} x_{1}^{(0)}, x_{1}^{(1)} \in X_{1} \\ ⋮ x_{4}^{(0)}, x_{4}^{(1)} \in X_{4} \end{array}} \prod_{j = 1}^{4} \prod_{ω \in {0, 1}^{[4] ∖ {j}}} ν {(x_{- j}^{(ω)})}^{n_{j, w}} = 1 + o (1) .

Our definition can be recovered by making the substitution

{(x^{(ω)})}_{- j} = \sum_{i = 1}^{4} (j - i) x_{i}^{(ω_{i})} .

Theorem 3.14 (Sparse counting lemma). Let $ν, g, \tilde{g}$ be weighted hypergraphs on $X_{1} \cup X_{2} \cup X_{3} \cup X_{4}$ . Suppose that $ν$ satisfies the $3$ -LFC (as in Definition 3.13), $0 \leq g \leq ν$ , $0 \leq \tilde{g} \leq 1$ , and $∥ g - \tilde{g} ∥_{□} = o (1)$ . Then

| 𝔼_{x_{1}, \dots, x_{4}} \prod_{j = 1}^{4} g_{- j} (x_{- j}) - 𝔼_{x_{1}, \dots, x_{4}} \prod_{j = 1}^{4} {\tilde{g}}_{- j} (x_{- j}) | = o (1) .

The proof consists of the following steps:

(1)

Lemma 3.15 (Telescoping argument). Let $0 \leq \tilde{g} \leq 1$ , and $g_{- j} \leq 1 \forall j \in [3]$ , $g_{- 4} \leq ν_{- 4}$ . If $∥ g - \tilde{g} ∥_{□} \leq 𝜀$ , then

| 𝔼_{x_{1}, \dots, x_{4}} \prod_{j = 1}^{4} g_{- j} (x_{- j}) - \prod_{j = 1}^{4} {\tilde{g}}_{- j} (x_{-} j) | \leq 4 𝜀 .

Sketch proof.

\begin{array}{l} 𝔼 \prod_{j = 1}^{4} g (x_{- j}) & = \underset{small}{\underset{⏟}{𝔼 \prod_{j = 1}^{3} g (x_{- j}) (g (x_{- 4}) - \tilde{g} (x_{- 4}))}} + 𝔼 \prod_{j = 1}^{3} g (x_{- j}) \tilde{g} (x_{- 4}) \end{array}

Now we no longer have to worry about $g_{- 4}$ . Then repeat. □

(2)

Lemma 3.16 (Strong linear forms). Suppose $ν$ satisfies the $3$ -LFC as defined in Definition 3.13 and suppose $0 \leq g \leq ν$ , $0 \leq \tilde{g} \leq 1$ . Then

| 𝔼_{x_{1}, x_{2}, x_{3}, x_{4}^{(0)}, x_{4}^{(1)}} (ν (x_{- 4}) - 1) \prod_{j = 1}^{3} \prod_{ω \in {0, 1}} h_{j, ω} (x_{- j}^{(ω)}) |,

where $x^{(ω)} = (x_{1}, x_{2}, x_{3}, x_{4}^{(ω)})$ and $h_{j, ω}$ is either $g_{- j}$ or ${\tilde{g}}_{- j}$ .

Sketch proof. Use LFC and Cauchy-Schwarz. □

(3) Next (final) lecture: densification strategy

At each step, if $g_{- j} \leq ν_{- j}$ and $∥ g_{- j} - {\tilde{g}}_{- j} ∥_{□, j} \leq 𝜀$ , find $0 \leq g_{- j}^{'} \leq 1$ such that $∥ g_{- j}^{'} - {\tilde{g}}_{- j} ∥_{□, j} \leq 𝜀$ .

Sketch proof of Theorem 3.5. Given $f : ℤ ∕ N ℤ \to [0, \infty)$ and $ν : ℤ ∕ N ℤ \to [0, \infty)$ , $0 \leq f \leq ν$ , satisfying the $3$ -LFC:

\begin{array}{l} ψ : G^{4} \to G {\begin{matrix} ψ_{1} (x_{1}, \dots, x_{4}) = x_{2} + 2 x_{3} + 3 x_{4} \\ ψ_{2} (x_{1}, \dots, x_{4}) = - x_{1} + x_{3} + 2 x_{4} \\ ψ_{3} (x_{1}, \dots, x_{4}) = - 2 x_{1} - x_{2} + x_{4} \\ ψ_{4} (x_{1}, \dots, x_{4}) = - 3 x_{1} - 2 x_{2} - x_{3} \end{matrix} \end{array}

Define the weighted hypergraphs $g, ν$ on ${(ℤ ∕ N ℤ)}^{4}$ :

\begin{array}{l} g_{- j} (x_{- j}) & = f (ψ_{j} (x_{1}, \dots, x_{4})) \\ ν_{- j} (x_{- j}) & = ν (ψ_{j} (x_{1}, \dots, x_{4})) \end{array}

and from the Dense Model Theorem, obtain $\tilde{f} : ℤ ∕ N ℤ \to [0, 1]$ such that $∥ f - \tilde{f} ∥_{□} \leq 𝜀$ , with corresponding weighted hypergraph

{\tilde{g}}_{- j} (x_{- j}) = \tilde{f} (ψ_{j} (x_{1}, \dots, x_{4})) .

By the sparse counting lemma, we have

Corollary 3.17. For all $γ > 0$ , there exists $𝜀 > 0$ such that the following holds: Let $ν, f, \tilde{f} : ℤ ∕ N ℤ \to [0, \infty)$ with $0 \leq f \leq ν$ , $0 \leq \tilde{f} \leq 1$ and $∥ f - \tilde{f} ∥_{□} \leq 𝜀$ . Then

| 𝔼_{x, d} \prod_{j = 0}^{3} f (x + j d) - 𝔼 \prod_{j = 0}^{3} \tilde{f} (x + j d) | \leq γ .

But also, by Corollary 3.9, $𝔼 \tilde{f} = 𝔼 f \geq δ$ , so by the weighted Szemerédi Theorem we get the result. □

Proof of Theorem 3.14. By inductionon $m = number of ν_{- 1}, \dots, ν_{- 4} that are not identically 1$ . $m = 0$ and $m = 1$ straightforward.

Suppose true for $m = M \geq 1$ , and consider $M + 1$ . Without loss of generality $ν_{- 1}$ is not identically $1$ . Define auxiliary weighted hypergraphs $ν^{'}, g^{'}, {\tilde{g}}^{'} : X_{- 1} \to [0, \infty)$ by

\begin{array}{l} ν^{'} (x_{- 1}) & = 𝔼_{x_{1} \in X_{1}} ν_{- 2} (x_{- 2}) ν - 3 (x_{- 3}) ν_{- 4} (x_{- 4}) \\ g^{'} (x_{- 1}) & = 𝔼_{x_{1} \in X_{1}} g_{- 2} (x_{- 2}) g_{- 3} (x_{- 3}) g_{- 4} (x_{- 4}) \\ {\tilde{g}}^{'} (x_{- 1}) & = 𝔼_{x_{1} \in X_{1}} {\tilde{g}}_{- 2} (x_{- 2}) {\tilde{g}}_{- 3} (x_{- 3}) {\tilde{g}}_{- 4} (x_{- 4}) \end{array}

Note that these do not depend on $ν_{- 1}$ , $g_{- 1}$ , ${\tilde{g}}_{- 1}$ . Also define $g^{'} \land 1 = \max {g^{'}, 1}$ and $ν^{'} \land 1 = \max {ν^{'}, 1}$ .

Observe that by the LFC, $𝔼 ν^{'}, 𝔼 {ν^{'}}^{2} = 1 + o (1)$ and by Cauchy–Schwarz, ${(𝔼 | ν^{'} - 1 |)}^{2} \leq 𝔼 | ν^{'} - 1 |^{2} = o (1)$ (i).

Claim: $∥ g^{'} \land 1 - {\tilde{g}}^{'} ∥_{□} = o (1)$ .

Proof of claim: Since $0 \leq g^{'} - g^{'} \land 1 = \max {g^{'} - 1, 0} \leq \max {ν^{'} - 1, 0} \leq | ν^{'} - 1 |$ (ii). For any $A_{2} \subseteq X_{3} \times X_{4}$ , $A_{3} \subseteq X_{2} \times X_{4}$ , $A_{4} \subseteq X_{2} \times X_{3}$ ,

\begin{array}{l} 𝔼 ((g^{'} \land 1) - {\tilde{g}}^{'} (x_{- 1})) \underset{= \prod_{j = 2}^{4} 𝟙_{A_{j}}}{\underset{⏟}{𝟙_{A_{2}} (x_{3}, x_{4}) 𝟙_{A_{3}} (x_{2}, x_{4}) 𝟙_{A_{4}} (x_{2}, x_{3})}} \\ = \underset{in absolute value = o (1) because of (i) and (ii)}{\underset{⏟}{𝔼 (g^{'} \land 1 - g^{'}) (x_{- 1})}} \prod_{j = 2}^{4} 𝟙_{A_{j}} + 𝔼 (g^{'} - {\tilde{g}}^{'}) (x_{- 1}) \prod_{j = 2}^{4} 𝟙_{A_{j}} \end{array}

Note that $g^{'}$ involves at most $M$ unbounded functions, so the second term is $o (1)$ by the inductive hypothesis. □

Consider

\begin{array}{l} | 𝔼 \prod_{j = 1}^{4} g_{- j} (x_{- j}) - \prod_{j = 1}^{4} {\tilde{g}}_{- j} (x_{- j}) | & = | 𝔼_{x_{2}, x_{3}, x_{4}} g_{- 1} (x_{- 1}) g^{'} (x_{- 1}) - {\tilde{g}}_{- 1} (x_{- 1}) {\tilde{g}}^{'} (x_{- 1}) | \\ = 𝔼 g_{- 1} g^{'} - {\tilde{g}}_{- 1} {\tilde{g}}^{'} \\ = 𝔼 g (g^{'} - {\tilde{g}}^{'}) + 𝔼 (g - \tilde{g}) {\tilde{g}}^{'} \end{array}

Since $0 \leq \tilde{g} \leq 1$ , the second term is at most $∥ g - \tilde{g} ∥_{□} = o (1)$ . The first term, by Cauchy–Schwarz, is bounded above by

(𝔼 g) (𝔼 g {(g^{'} - {\tilde{g}}^{'})}^{2}) \leq \underset{= 1 + o (1)}{\underset{⏟}{𝔼 ν}} \cdot 𝔼 ν {(g^{'} - {\tilde{g}}^{'})}^{2}

By the strong linear forms condition, may replace $ν$ by $1$ . So $| 𝔼 g (g^{'} - {\tilde{g}}^{'}) |^{2} \leq (1 + o (1)) (o (1) + 𝔼 {(g^{'} - {\tilde{g}}^{'})}^{2})$ . Expand

𝔼 {(g^{'} - {\tilde{g}}^{'})}^{2} = 𝔼 (\underset{\leq ν^{'}}{\underset{⏟}{g^{'}}} - \underset{\leq 1}{\underset{⏟}{{\tilde{g}}^{'}}}) \underset{\leq | ν^{'} - 1 |}{\underset{⏟}{(g^{'} - g^{'} \land 1)}} + \underset{= (iii)}{\underset{⏟}{𝔼 (g^{'} - {\tilde{g}}^{'}) (g^{'} \land 1 - {\tilde{g}}^{'})}}

So the first term is bounded above by $𝔼 (ν^{'} + 1) | ν^{'} + 1 | = o (1)$ by LFC.

Notice that

𝔼 (g^{'} - {\tilde{g}}^{'}) (g^{'} \land 1 - {\tilde{g}}^{'}) = 𝔼 g^{'} \cdot g^{'} \land 1 + 𝔼 {\tilde{g}^{'}}^{2} - 𝔼 g^{'} {\tilde{g}}^{'} - 𝔼 {\tilde{g}}^{'} \cdot g^{'} \land 1,

and each term is, up to $o (1)$ , equal to $𝔼 {\tilde{g}^{'}}^{2}$ . Indeed (let’s do the hardest term),

𝔼 g^{'} \cdot g^{'} \land 1 - 𝔼 {\tilde{g}^{'}}^{2} = 𝔼_{x_{1}, x_{2}, x_{3}, x_{4}} [g^{'} \land 1 (x_{- 1}) \prod_{j = 2}^{4} g_{- j} (x_{- j}) - {\tilde{g}}^{'} (x_{- 1}) \prod_{j = 2}^{4} {\tilde{g}}_{- j} (x_{- j})]

but $∥ g^{'} \land 1 - {\tilde{g}}^{'} ∥_{□} = o (1)$ by the claim, so done by inductive hypothesis. □

[next] [prev] [prev-tail] [front] [up]