Title: Daniel's Flashcards / Year 4 / Term 1 / Additive Combinatorics

html: Definition 1.1 (Sumset). Let G be an abelian group. Given A , B ⊆ G, define the sumset A + B to be
A + B : = { a + b : a ∈ A , b ∈ B }
and the difference set A − B to be
A − B : = { a + b : a ∈ A , b ∈ B } .
nothing: True

html: Lemma 1.3. Assuming that:
- A ⊆ ℤ is finite.
Then | A + A | ≥ 2 | A | − 1, with equality if and only if A is an arithmetic progression.
proof: Proof. Let A = { a 1 , a 2 , … , a n } with a 1 < a 2 < ⋯ < a n. Then
a 1 + a 1 < a 1 + a 2 < a 1 + a 2 < ⋯ < a 1 + a n < a 2 + a n < ⋯ < a n + a n ,
so | A + A | ≥ 2 | A | − 1. But we could also have written
a 1 + a 1 < a 1 + a 2 < a 2 + a 2 < a 2 + a 3 < a 2 + a 4 < ⋯ < a 2 + a n < a 3 + a n < ⋯ < a n + a n .
When | A + A | = 2 | A | − 1, these two orderings must be the same. So a 2 + a i = a 1 + a i + 1 for all i = 2 , … , n − 1. □
cloze1: True

html: Theorem 1.5 (Cauchy-Davenport). Assuming that:
- p is a prime
- A , B ⊆ ℤ ∕ p ℤ nonempty
Then
| A + B | ≥ min ⁡ { p , | A | + | B | − 1 } .
proof: Proof. Assume | A | + | B | ≤ p + 1. Without loss of generality assume that 1 ≤ | A | ≤ | B | and that 0 ∈ A. Apply induction on | A |. The case | A | = 1 is trivial. Suppose | A | ≥ 2, and let 0 ≠ a ∈ A.
Since { a , 2 a , 3 a , … , ( p − 1 ) a , p a } = ℤ ∕ p ℤ and | A | + | B | ≤ p + 1, there must exist m ≥ 0 such that m a ∈ B but ( m + 1 ) a ∉ B. Let B ′ = B − m a, so 0 ∈ B ′, a ∉ B ′, | B ′ | = | B |.
But 1 ≤ | A ∩ B ′ | < | A |, so the inductive hypothesis applies to A ∩ B ′ and A ∪ B ′. Since
( A ∩ B ′ ) + ( A ∪ B ′ ) ⊆ A + B ′ ,
we have
| A + B | = | A + B ′ | ≥ | ( A ∩ B ′ ) + ( A ∪ B ′ ) | ≥ | A ∩ B ′ | + | A ∪ B ′ | + 1 = | A | + | B | + 1 . □
nothing: True

html: Definition 1.8 (Ruzsa distance). Given finite sets A , B ⊆ G, we define the Ruzsa distance d ( A , B ) between A and B by
d ( A , B ) = log ⁡ | A − B | | A | | B |
nothing: True

html: Lemma 1.9 (Ruzsa’s triangle inequality). Assuming that:
- A , B , C ⊆ G finite
Then
d ( A , C ) ≤ d ( A , B ) + d ( B , C ) .
proof: Proof. Observe that
| B | ⋅ | A − C | ≤ | A − B | ⋅ | B − C | .
Indeed, writing each d ∈ A − C as d = a d − c d with a d ∈ A, c d ∈ C, the map
ϕ : B × ( A − C ) → ( A − B ) × ( B − C ) ( b , d ) ↦ ( a d − b , b − c d )
is injective. The triangle inequality now follows from the definition. □
nothing: True

html: Definition 1.10 (Doubling / difference constant). Given a finite A ⊆ G, we write
σ ( A ) : = | A + A | | A |
for the doubling constant of A and
δ ( A ) : = | A − A | | A |
for the difference constant of A.
nothing: True

html: Theorem 1.11 (Plunnecke’s Inequality). Assuming that:
- A , B ⊆ G are finite sets
- | A + B | ≤ K | A | for some K ≥ 1
Then ∀ ⁡ l , m ∈ ℕ 0,
| l B − m B | ≤ K l + m | A | .
proof: Proof. Choose a non-empty subset A ′ ⊆ A such that the ratio | A ′ + B | | A ′ | is minimised, and call this ratio K ′. Then | A ′ + B | = K ′ | A ′ |, K ′ ≤ K, and ∀ ⁡ A ″ ⊆ A, | A ″ + B | ≥ K ′ | A ″ |.
Claim: For every finite C ⊆ G, | A ′ + B + C | ≤ K ′ | A ′ + C |.
Let’s complete the proof of the theorem assuming the claim. We first show that ∀ ⁡ m ∈ ℕ 0, | A ′ + m B | ≤ K ′ m | A ′ |. Indeed, the case m = 0 is trivial, and m = 1 is true by assumption. Suppose m > 1 and the inequality holds for m − 1. By the claim with C = ( m − 1 ) B, we get
| A ′ + m B | = | A ′ + B + ( m − 1 ) B | ≤ K ′ | A ′ + ( m − 1 ) B | ≤ K ′ m | A ′ | .
But as in the proof of Ruzsa’s triangle inequality, ∀ ⁡ l , m ∈ ℕ 0, we can show
| A ′ | | l B − m B | ≤ | A ′ + l B | | A ′ + m B | ≤ K ′ l | A ′ | K ′ m | A ′ | = K ′ l + m | A ′ | 2 .
Hence | l B − m B | ≤ K ′ l + m | A ′ | ≤ K ′ l + m | A |, which completes the proof (assuming the claim).
We now prove the claim by induction on | C |. When | C | = 1 the statement follows from the assumptions. Suppose the claim is true for C, and consider C ′ = C ∪ { x } for some x ∉ C. Observe that
A ′ + B + C ′ = ( A ′ + B + C ) + ( ( A ′ + B + x ) ∖ ( D + B + x ) )
with D = { a ∈ A ′ : a + B + x ⊆ A ′ + B + X }.
By definition of K ′, | D + B | ≥ K ′ | D |, so
| A ′ + B + C ′ | ≤ | A ′ + B + C | + | A ′ + B + x | − | D + B + x | ≤ IH K ′ | A ′ + C | + K ′ | A ′ | − K ′ | D | = K ′ ( | A ′ + C | + | A ′ | − | D | )
We apply this argument a second time, writing
A ′ + C ′ = ( A ′ + C ) ⊔ ( ( A ′ + x ) ∖ ( E + x ) )
where E = { a ∈ A ′ : a + x ∈ A ′ + C } ⊆ D. We conclude that
| A ′ + C ′ | = | A ′ + C | + | A ′ + x | − | E + x | ≥ | A ′ + C | + | A ′ | − | D |
so
| A ′ + B + C ′ | ≤ K ′ ( | A ′ + C | + | A ′ | − | D | ) ≤ K ′ | A ′ + C ′ | ,
proving the claim. □
nothing: True

html: Theorem 1.12 (Freiman-Ruzsa). Assuming that:
- A ⊆ 𝔽 p n
- | A + A | ≤ K | A | (i.e. σ ( A ) ≤ K)
Then A is contained in a subspace H ≤ 𝔽 p n of size | H | ≤ K 2 p K 4 | A |.
proof: Proof. Choose X ⊆ 2 A − A maximal such that the translates x + A with x ∈ X are disjoint. Such a set X cannot be too large: ∀ ⁡ x ∈ X, x + A ⊆ 3 A − A, so by Plunnecke’s Inequality, since | 3 A − A | ≤ K 4 | A |,
| X | | A | = | ⋃ x ∈ X ( x + A ) | ≤ | 3 A − A | .
So | X | ≤ K 4. We next show
2 A − A ⊆ X + A − A . (∗)
Indeed, if y ∈ 2 A − A and y ∉ X, then by maximality of X, y + A ∩ x + A ≠ ∅ for some x ∈ X (and if y ∈ X, then clearly y ∈ X + A − A).
It follows from (∗) by induction that ∀ ⁡ l ≥ 2,
l A − A ⊆ ( l − 1 ) X + A − A , (∗∗)
since
l A − A = A + ( l − 1 ) A − A ⏟ ⊆ ( l − 2 ) X + A − A ⊆ ( l − 2 ) X + 2 A − A ⏟ ⊆ X + A − A ⊆ ( l − 1 ) X + A − A .
Now let H ≤ 𝔽 p n be the subgroup generated by A, which we can write as
H = ⋃ l ≥ 1 ( l A − A ) ⊆ ( ∗ ∗ ) Y + A − A
where Y ≤ 𝔽 p n is the subgroup generated by X.
But every element of Y can be written as a sum of | X | elements of X with coefficients amongst 0 , 1 , … , p − 1, hence | Y | ≤ p | X | ≤ p K 4. To conclude, note that
| U | ≤ | Y | | A − A | ≤ p K 4 ≤ p K 4 K 2 | A | ,
where we use Plunnecke’s Inequality or even Ruzsa’s triangle inequality. □
nothing: True

html: Theorem 1.14 (Polynomial Freiman-Ruzsa, due to Gowers–Green–Manners–Tao 2024). Assuming that:
- A ⊆ 𝔽 p n
- | A + A | ≤ K | A |
Then there exists a subspace K ≤ 𝔽 p n of size at most C 1 ( K ) | A | such that for some x ∈ 𝔽 p n,
| A ∩ ( x + K ) | ≥ | A | C 2 ( K ) ,
where C 1 ( K ) and C 2 ( K ) are polynomial in K.
proof: Proof. Omitted, because the techniques are not relevant to other parts of the course. See Entropy Methods in Combinatorics next term. □
nothing: True

html: Lemma 1.17. Assuming that:
- A , B ⊆ G
- both non-empty
Then
E ( A , B ) ≥ | A | 2 | B | 2 | A + B | .
proof: Proof. Define r A + B ( x ) = | { ( a , b ) ∈ A × B : a + b = x } | (and notice that this is the same as | A ∩ ( x − B ) |). Observe that
E ( A , B ) = | { ( a , a ′ , b , b ′ ) ∈ A 2 × B 2 : a + b = a ′ + b ′ } = ∑ x ∈ G r A + B ( x ) 2 = ∑ x ∈ A + B r A + B ( x ) 2 ≥ ( ∑ x ∈ A + B r A + B ( x ) ) 2 | A + B | by Cauchy-Schwarz
but
𝟙 𝟙 𝟙 𝟙 ∑ x ∈ G | A ∪ ( x − B ) | = ∑ x ∈ G ∑ y ∈ G 𝟙 A ( y ) 𝟙 x − B ( y ) = ∑ x ∈ G ∑ y ∈ G 𝟙 A ( y ) 𝟙 B ( x − y ) = | A | | B |
(As usual, 𝟙 𝟙 A here means the indicator function). □
cloze1: True

html: Theorem 1.19 (Balog–Szemeredi–Gowers, Schoen). Assuming that:
- A ⊆ G is finite
- E ( A ) ≥ η | A | 3 for some η > 0
Then there exists A ′ ⊆ A of size at least c 1 ( η ) | A | such that | A ′ + A ′ | ≤ | A ′ | c 2 ( η ), where c 1 ( η ) and c 2 ( η ) are polynomial in η.
proof: Proof. Let U = { x ∈ G : | A ∩ ( x + A ) | ≤ 1 2 η | A | }. Then
∑ x ∈ U | A ∩ ( x + A ) | 2 = 1 2 η | A | ∑ x | A ∩ ( x + A ) | = 1 2 η | A | 3 = 1 2 E ( A )
For 0 ≤ i ≤ ⌈ log ⁡ 2 η − 1 ⌉, let
Q i = { x ∈ G : | A | 2 i + 1 < | A ∩ ( x + A ) | ≤ | A | 2 i } ,
and set δ i = η − 1 2 − 2 i. Then
𝟙 ∑ i δ i | Q i | = ∑ i | Q i | η 2 2 i = 1 η | A | 2 ∑ i | A | 2 2 2 i | Q i | = 1 η | A | 2 ∑ i | A | 2 2 2 i ∑ x ∉ U 𝟙 { | A | 2 i + 1 < | A ∩ ( x + A ) | ≤ | A | 2 i } ≥ 1 η | A | 2 ∑ x ∉ U | A ∩ ( x + A ) | 2 ≥ 1 η | A | 2 ⋅ 1 2 E ( A ) ( ∑ x ∈ U | A ∩ ( x + A ) | 2 ≤ 1 2 E ( A ) ) = 1 2 | A | ( ∗ )
Let S = { ( a , b ) ∈ A 2 : a − b ∉ P c η }. Then
∑ i ∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) ∩ Q i | ≤ ∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) | ⏟ = | A ∩ ( a − b + A ) | ≤ c η | A | ⏟ by definition of S ≤ | S | ⋅ c η | A | ≤ c η | A | 3 ≤ 2 c η | A | 2 ⋅ 1 2 | A | ≤ ( ∗ ) 2 c η | A | 2 ∑ i δ i | Q i |
Hence there exists i 0 such that
∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) ∩ Q i 0 | ≤ 2 c η | A | 2 δ i 0 | Q i 0 | .
Let Q = Q i 0, δ = δ i 0, λ = 2 − i 0. So
∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) ∩ Q | ≤ 2 c η δ | A | 2 | Q | . (∗∗)
Find x such that X = | A ∩ ( A + x ) | is large.
Given x ∈ G, let X ( x ) = A ∩ ( x + A ). Then
𝔼 x ∈ Q | X ( x ) | = 1 | Q | ∑ x ∈ Q | A ∩ ( x + A ) | ≥ 1 2 λ | A | .
Let T ( x ) = { ( a , b ) ∈ X ( x ) 2 : a − b ∉ P c η }. Then
𝔼 X ∈ Q | T ( x ) | = 𝔼 x ∈ Q | { ( a , b ) ∈ ( A ∩ ( x ⏟ x ∈ A − a ∩ A − b + A ) ) 2 : a − b ∉ P c η } | = 1 | Q | ∑ x ∈ Q | { ( a , b ) ∈ S : x ∈ A − a ∩ A − b } | = 1 | Q | ∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) ∩ Q | ≤ 1 | Q | 2 c η | A | 2 δ | Q | = 2 c η δ | A | 2 = 2 c λ 2 | A | 2
Therefore,
𝔼 x ∈ Q | X ( x ) | 2 − ( 1 6 c ) − 1 | T ( x ) | ≤ C-S ( 𝔼 x ∈ Q | X ( x ) | ) 2 − ( 1 6 c ) − 1 𝔼 x ∈ Q | T ( x ) | ≤ ( λ 2 ) 2 | A | 2 − ( 1 6 c ) − 1 2 c λ 2 | A | 2 = ( λ 2 4 − λ 2 8 ) | A | 2 = λ 2 8 | A |
So there exists x ∈ Q such that | X ( x ) | 2 ≥ λ 2 8 | A | 2, in which case we have
| X | ≥ λ 8 | A | ≥ η 3 | A |
and | T ( x ) | ≤ 1 6 c | X | 2. □
nothing: True

html: Definition 1.20 (gamma-popular differences). Given A ⊆ G and γ > 0, let
P γ = { x ∈ G : | A ∩ ( x + A ) | ≥ γ | A | }
be the set of γ-popular differences of A.
nothing: True

html: Lemma 1.21. Assuming that:
- A ⊆ G is finite
- E ( A ) ≥ η | A | 3
- c > 0
Then there is a subset X ⊆ A of size | X | ≥ η | A | ∕ 3 such that for all but a ( 1 6 c )-proportion of pairs ( a , b ) ∈ X 2, a − b ∈ P c η.
proof: Proof. Let U = { x ∈ G : | A ∩ ( x + A ) | ≤ 1 2 η | A | }. Then
∑ x ∈ U | A ∩ ( x + A ) | 2 = 1 2 η | A | ∑ x | A ∩ ( x + A ) | = 1 2 η | A | 3 = 1 2 E ( A )
For 0 ≤ i ≤ ⌈ log ⁡ 2 η − 1 ⌉, let
Q i = { x ∈ G : | A | 2 i + 1 < | A ∩ ( x + A ) | ≤ | A | 2 i } ,
and set δ i = η − 1 2 − 2 i. Then
𝟙 ∑ i δ i | Q i | = ∑ i | Q i | η 2 2 i = 1 η | A | 2 ∑ i | A | 2 2 2 i | Q i | = 1 η | A | 2 ∑ i | A | 2 2 2 i ∑ x ∉ U 𝟙 { | A | 2 i + 1 < | A ∩ ( x + A ) | ≤ | A | 2 i } ≥ 1 η | A | 2 ∑ x ∉ U | A ∩ ( x + A ) | 2 ≥ 1 η | A | 2 ⋅ 1 2 E ( A ) ( ∑ x ∈ U | A ∩ ( x + A ) | 2 ≤ 1 2 E ( A ) ) = 1 2 | A | ( ∗ )
Let S = { ( a , b ) ∈ A 2 : a − b ∉ P c η }. Then
∑ i ∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) ∩ Q i | ≤ ∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) | ⏟ = | A ∩ ( a − b + A ) | ≤ c η | A | ⏟ by definition of S ≤ | S | ⋅ c η | A | ≤ c η | A | 3 ≤ 2 c η | A | 2 ⋅ 1 2 | A | ≤ ( ∗ ) 2 c η | A | 2 ∑ i δ i | Q i |
Hence there exists i 0 such that
∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) ∩ Q i 0 | ≤ 2 c η | A | 2 δ i 0 | Q i 0 | .
Let Q = Q i 0, δ = δ i 0, λ = 2 − i 0. So
∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) ∩ Q | ≤ 2 c η δ | A | 2 | Q | . (∗∗)
Find x such that X = | A ∩ ( A + x ) | is large.
Given x ∈ G, let X ( x ) = A ∩ ( x + A ). Then
𝔼 x ∈ Q | X ( x ) | = 1 | Q | ∑ x ∈ Q | A ∩ ( x + A ) | ≥ 1 2 λ | A | .
Let T ( x ) = { ( a , b ) ∈ X ( x ) 2 : a − b ∉ P c η }. Then
𝔼 X ∈ Q | T ( x ) | = 𝔼 x ∈ Q | { ( a , b ) ∈ ( A ∩ ( x ⏟ x ∈ A − a ∩ A − b + A ) ) 2 : a − b ∉ P c η } | = 1 | Q | ∑ x ∈ Q | { ( a , b ) ∈ S : x ∈ A − a ∩ A − b } | = 1 | Q | ∑ ( a , b ) ∈ S | ( A − a ) ∩ ( A − b ) ∩ Q | ≤ 1 | Q | 2 c η | A | 2 δ | Q | = 2 c η δ | A | 2 = 2 c λ 2 | A | 2
Therefore,
𝔼 x ∈ Q | X ( x ) | 2 − ( 1 6 c ) − 1 | T ( x ) | ≤ C-S ( 𝔼 x ∈ Q | X ( x ) | ) 2 − ( 1 6 c ) − 1 𝔼 x ∈ Q | T ( x ) | ≤ ( λ 2 ) 2 | A | 2 − ( 1 6 c ) − 1 2 c λ 2 | A | 2 = ( λ 2 4 − λ 2 8 ) | A | 2 = λ 2 8 | A |
So there exists x ∈ Q such that | X ( x ) | 2 ≥ λ 2 8 | A | 2, in which case we have
| X | ≥ λ 8 | A | ≥ η 3 | A |
and | T ( x ) | ≤ 1 6 c | X | 2. □
cloze1: True

html: Lemma 2.2. Assuming that:
- γ ∈ G ^
Then
𝔼 x ∈ G γ ( x ) = { 1 if γ = 1 0 otherwise ,
and for all x ∈ G,
∑ γ ∈ G ^ γ ( x ) = { | G ^ | if x = 0 0 otherwise .
proof: Proof. The first equality in eqch case is trivial. Suppose γ ≠ 1. Then there exists y ∈ G with γ ( y ) ≠ 1. Then
γ ( y ) 𝔼 z ∈ G γ ( z ) = 𝔼 z ∈ G γ ( y + z ) = 𝔼 z ′ ∈ G γ ( z ′ )
So 𝔼 z ∈ G γ ( z ) = 0.
For the second part, note that given x ≠ 0, there must by γ ∈ G ^ such that γ ( x ) ≠ 1, for otherwise G ^ would act trivially on ⟨ x ⟩, hence would also be the dual group for G ∕ ⟨ x ⟩, a contradiction. □
cloze1: True

html: Definition 2.3 (Fourier transform). Given f : G → ℂ, define its Fourier transform f ^ : G ^ → ℂ by
f ^ ( γ ) = 𝔼 x ∈ G f ( x ) γ ( x ) ¯ .
nothing: True

html: Lemma 2.7. Assuming that:
- f , g : G → ℂ
Then
- (i) ∥ f ∥ L 2 ( G ) 2 = ∥ f ^ ∥ l 2 ( G ^ ) 2 (Parseval’s identity)
- (ii) ⟨ f , g ⟩ = ⟨ f ^ , g ^ ⟩ (Plancherel’s identity)
proof: Proof. Exercise (hopefully easy). □
cloze1: True

html: Definition 2.8 (Spectrum). Let 1 ≥ ρ > 0 and f : G → ℂ. Define the ρ-large spectrum of f to be
Spec ⁡ ρ ( f ) = { γ ∈ G ^ : | f ^ ( γ ) | ≥ ρ ∥ f ∥ 1 } .
nothing: True

html: Lemma 2.10. Assuming that:
- ρ > 0
Then
| Spec ⁡ ρ ( f ) | ≤ ρ − 2 ∥ f ∥ 2 2 ∥ f ∥ 1 2 .
proof: Proof. By Parseval’s identity,
∥ f ∥ 2 2 = ∥ f ^ ∥ 2 2 = ∑ γ ∈ G ^ | f ^ ( γ ) | 2 ≥ ∑ γ ∈ Spec ⁡ ρ ( f ) | f ^ ( γ ) | 2 ≥ | Spec ⁡ ρ ( f ) | ( ρ ∥ f ∥ 1 ) 2 □
cloze1: True

html: Definition 2.11 (Convolution). Given f , g : G → ℂ, we define their convolution f ∗ g : G → ℂ by
f ∗ g ( x ) = 𝔼 y ∈ G f ( y ) g ( x − y ) ∀ ⁡ x ∈ G .
nothing: True

html: Lemma 2.13. Assuming that:
- f , g : G → ℂ
Then
f ∗ g ^ ( γ ) = f ^ ( γ ) g ^ ( γ ) ∀ ⁡ γ ∈ G ^ .
proof: Proof.
f ∗ g ^ ( γ ) = 𝔼 x ∈ G f ∗ g ( x ) γ ( x ) ¯ = 𝔼 x ∈ G 𝔼 [ ∈ y ] G f ( y ) g ( x − y ⏟ u ) γ ( x ) ¯ = 𝔼 u ∈ G 𝔼 [ ∈ y ] G f ( y ) g ( u ) γ ( u + y ) ¯ = f ^ ( γ ) g ^ ( γ ) □
cloze1: True

html: Theorem 2.15 (Bogolyubov’s lemma). Assuming that:
- A ⊆ 𝔽 p n be a set of density α
Then there exists V ≤ 𝔽 p n of codimension ≤ 2 α − 2 such that V ⊆ A + A − A − A.
proof: Proof. Observe
𝟙 𝟙 𝟙 𝟙 2 A − 2 A = supp ⁡ ( 𝟙 A ∗ 𝟙 A ∗ 𝟙 − A ∗ 𝟙 − A ⏟ = : g ) ,
so wish to find V ≤ 𝔽 p n such that g ( x ) > 0 for all x ∈ V. Let 𝟙 S = Spec ⁡ ρ ( 𝟙 A ) with ρ = α 2 and let V = ⟨ S ⟩ ⊥. By Lemma 2.10, codim ⁡ ( V ) ≤ | S | ≤ ρ − 2 α − 1. Fix x ∈ V.
𝟙 𝟙 𝟙 𝟙 g ( x ) = ∑ t ∈ 𝔽 p n ^ g ^ ( t ) e ( x ⋅ t ∕ p ) = ∑ t ∈ 𝔽 p n ^ | 𝟙 A ^ ( t ) | 4 e ( x ⋅ t ∕ p ) by Lemma 2.13 = α 4 + ∑ t ≠ 0 | 𝟙 A ^ ( t ) | 4 e ( x ⋅ t ∕ p ) = α 4 + ∑ t ∈ S ∖ { 0 } | 𝟙 A ^ ( t ) | 4 e ( x ⋅ t ∕ p ) ⏟ ( 1 ) + ∑ t ∉ S | 𝟙 A ^ ( t ) | 4 e ( x ⋅ t ∕ p ) ⏟ ( 2 )
Note ( 1 ) ≥ ( ρ α ) 4 since x ⋅ t = 0 for all t ∈ S and
𝟙 𝟙 𝟙 𝟙 𝟙 | ( 2 ) | ≤ sup ⁡ t ∉ S | 𝟙 A ^ ( t ) | 2 ∑ t ∉ S | 𝟙 A ^ | 2 ≤ sup ⁡ t ∈ S | 𝟙 A ^ ( t ) | 2 ∑ t ∉ S | 𝟙 A ^ | 2 ≤ ( ρ α ) 2 ∥ 𝟙 A ∥ 2 2 by Parseval’s identity = ρ 2 α 3
hence g ( x ) > 0 (in fact, ≥ α 4 2) for all x ∈ V and codim ⁡ ( V ) ≤ 2 α − 2. □
nothing: True

html: Lemma 2.17. Assuming that:
- A ⊆ 𝔽 p n of density α
- ρ > 0
- 𝟙 sup ⁡ t ≠ 0 | 𝟙 A ^ ( t ) | ≥ ρ α
Then there exists V ≤ 𝔽 p n of codimension 1 and x ∈ 𝔽 p n such that
| A ∩ ( x + V ) | ≥ α ( 1 + ρ 2 ) | V | .
proof: Proof. Let t ≠ 0 be such that 𝟙 | 𝟙 A ^ ( t ) | ≥ ρ α, and let V = ⟨ t ⟩ ⊥. Write v j + V for j ∈ [ p ] = { 1 , 2 , … , p } for the p distinct cosets v j + V = { x ∈ 𝔽 p n : x ⋅ t = j } of V. Then
𝟙 𝟙 𝟙 𝟙 A ^ ( t ) = f A ^ ( t ) = 𝔼 x ∈ 𝔽 p n ( 𝟙 A ( x ) − α ) e ( − x ⋅ t ∕ p ) = 𝔼 j ∈ [ p ] 𝔼 x ∈ v j + V ( 𝟙 A ( x ) − α ) e ( − j ∕ p ) = 𝔼 j ∈ [ p ] ( | A ∩ ( v j + V ) | | v j + V | − α ⏟ = a j ) e ( − j ∕ p )
By triangle inequality, 𝔼 j ∈ [ p ] | a j | ≥ ρ α. But note that 𝔼 j ∈ [ p ] a j = 0 so 𝔼 j ∈ [ p ] a j + | a j | ≥ ρ α, hence there exists j ∈ [ p ] such that a j + | a j | ≥ ρ α. Then a j ≥ ρ α 2. □
cloze1: True

html: Lemma 2.18. Assuming that:
- p ≥ 3 prime
- A ⊆ 𝔽 p n of density α > 0
- 𝟙 sup ⁡ t ≠ 0 | 𝟙 A ^ ( t ) | ≤ 𝜀
Then the number of 3-term arithmetic progressions in A differs from α 3 ( p n ) 2 by at most 𝜀 ( p n ) 2.
proof: Proof. The number of 3-term arithmetic progressions in A is ( p n ) 2 times
𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 T 3 ( 𝟙 A , 𝟙 A , 𝟙 A ) = 𝔼 x , d ∈ 𝔽 p n 𝟙 A ( x ) 𝟙 ( x + d ) 𝟙 A ( x + 2 d ) = 𝔼 x , y ∈ 𝔽 p n 𝟙 A ( x ) 𝟙 A ( y ) 𝟙 A ( 2 y − x ) = 𝔼 y ∈ G 𝟙 A ( y ) 𝔼 x ∈ G 𝟙 A ( x ) 𝟙 A ( 2 y − x ) = 𝔼 y ∈ G 𝟙 A ( y ) 𝟙 A ∗ 𝟙 A ( 2 y ) = ⟨ 𝟙 2 ⋅ A , 𝟙 A ∗ 𝟙 A ⟩
By Plancherel’s identity and Lemma 2.13, we have
𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 = ⟨ 𝟙 2 ⋅ A ^ , 𝟙 A ^ 2 ⟩ = ∑ t 𝟙 2 ⋅ A ^ ( t ) 𝟙 A ^ ( t ) 2 ¯ = α 3 + ∑ t ≠ 0 𝟙 2 ⋅ A ^ ( t ) 𝟙 A ^ ( t ) 2 ¯
but
𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 | ∑ t ≠ 0 𝟙 2 ⋅ A ^ ( t ) 𝟙 A ^ ( t ) 2 | ≤ sup ⁡ t ≠ 0 | 𝟙 A ^ ( t ) | ∑ t ≠ 0 | 𝟙 2 ⋅ A ^ ( t ) | | 𝟙 A ^ ( t ) | ≤ CS sup ⁡ t ≠ 0 | 𝟙 A ^ ( t ) | ( ∑ t | 𝟙 2 ⋅ A ^ ( t ) | 2 ∑ t | 𝟙 A ^ ( t ) | 2 ) 1 2 ≤ 𝜀 ∥ 𝟙 2 ⋅ A ^ ∥ 2 ∥ 𝟙 A ^ ∥ 2 = 𝜀 ⋅ α
by Parseval’s identity. □
cloze1: True

html: Theorem 2.19 (Meshulam’s Theorem). Assuming that:
- A ⊆ 𝔽 p n a set containing no non-trivial 3 term arithmetic progressions
Then | A | = O ( p n log ⁡ p n ).
proof: Proof. By assumption,
𝟙 𝟙 𝟙 T 3 ( 𝟙 A , 𝟙 A , 𝟙 A ) = | A | ( p n ) 2 = α p n .
But as in (the proof of) Lemma 2.18,
𝟙 𝟙 𝟙 𝟙 | T 3 ( 𝟙 A , 𝟙 A , 𝟙 A ) − α 3 | ≤ sup ⁡ t ≠ 0 | 𝟙 A ^ ( t ) | ⋅ α ,
so provided p n ≥ 2 α − 2, i.e. 𝟙 𝟙 𝟙 T 3 ( 𝟙 A , 𝟙 A , 𝟙 A ) ≤ α 3 2 we have 𝟙 sup ⁡ t ≠ 0 | 𝟙 A ^ ( t ) | ≥ α 2 2.
So by Lemma 2.17 with ρ = α 2, there exists V ≤ 𝔽 p n of codimension 1 and x ∈ 𝔽 p n such that | A ∩ ( x + V ) | ≥ ( α + α 2 4 ) | V |.
We iterate this observation: let A 0 = A, V 0 = 𝔽 p n, α 0 = | A 0 | | V 0 |. At the i-th step, we are given a set A i − 1 ⊆ V i − 1 of density α i − 1 with no non-trivial 3 term arithmetic progressions. Provided that p dim ⁡ ( V i − 1 ) ≥ 2 α i − 1 − 2, there exists V i ≤ V i − 1 of codimension 1, x i ∈ V i − 1 such that
| ( A − x i ) ∩ V i | ≥ ( α i − 1 + ( α i − 1 ) 2 4 ) | V i | .
Set A i = ( A − x i ) ∩ V i ⊆ V i, has density ≥ α i − 1 + ( α i − 1 ) 2 4, and is free of non-trivial 3 term arithmetic progressions.
Through this iteration, the density increases from α to 2 α in at most α ( α 2 4 ) = 4 ⋅ α − 1 steps.
2 α to 4 α in at most 2 α ( ( 2 α ) 2 4 ) = 2 α − 1 steps and so on.
So reaches 1 in at most
4 α − 1 ( 1 + 1 2 + 1 4 + 1 8 + ⋯ ) ≤ 8 α − 1
steps. The argument must end with dim ⁡ ( V i ) ≥ n − 8 α − 1, at which point we must have had p dim ⁡ ( V i ) < 2 α i − 1 2 ≤ 2 α − 2, or else we could have continued.
But we may assume that α ≥ 2 p − n 4 (or α − 2 < 2 p n 2) whence p n − 8 α − 1 ≤ p n 2, or n 2 ≤ 2 α − 1. □
nothing: True

html: Theorem 2.20 (Roth’s theorem). Assuming that:
- A ⊆ [ N ] = { 1 , … , N }
- A contains no non-trivial 3 term arithmetic progressions
Then | A | = O ( N log ⁡ log ⁡ N ).
proof: Proof. We may assume that | A ′ | = | A ∩ [ p ] | ≥ α ( 1 − α 2 0 0 ) p since otherwise
| A ∩ [ p + 1 , N ] | ≥ α N − ( α ( 1 − α 2 0 0 ) p ) = α ( N − p ) + α 2 2 0 0 p ≥ ( α + α 2 4 0 0 ) ( N − p )
so we would be in Case (ii) with J = [ p + 1 , N ]. Let A ″ = A ′ ∩ [ p 3 , 2 p 3 ]. Note that all 3 term arithmetic progressions of the form ( x , x + d , x + 2 d ) ∈ A ′ × A ″ × A ″ are in fact arithmetic progressions in [ N ].
If | A ′ ∩ [ p 3 ] | or | A ′ ∩ [ 2 p 3 , p ] | were at least 2 5 | A ′ |, we would again be in case (ii). So we may assume that | A ″ | ≥ | A ′ | 5.
Now as in Lemma 2.18 and Theorem 2.19,
𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 α ″ p = | A ″ | p 2 T 3 ( 𝟙 A ′ , 𝟙 A ″ , 𝟙 A ″ ) = α ′ ( α ″ ) 2 + ∑ t 𝟙 A ′ ^ ( t ) 𝟙 A ″ ^ ( t ) ¯ 𝟙 2 ⋅ A ″ ^ ( t )
where α ′ = | A ′ | p and α ″ = | A ″ | p. So as before,
𝟙 α ′ α ″ 2 ≤ sup ⁡ t ≠ 0 | 𝟙 A ′ ( t ) | ⋅ α ″ ⁡ ,
provided that α ″ p ≤ 1 2 α ′ ( α ″ ) 2, i.e. 2 p ≤ α ′ α ″. (Check this is satisfied).
Hence
𝟙 sup ⁡ t ≠ 0 | 𝟙 A ′ ^ ( t ) | ≥ α ′ α ″ ⁡ 2 ≥ 1 2 ( α ( 1 − α 2 0 0 ) ) 2 ⋅ 2 5 ≥ α 2 1 0 . □
nothing: True

html: Lemma 2.22. Assuming that:
- A ⊆ [ N ] of density α > 0
- N > 5 0 α − 2
- A contains no non-trivial 3 term arithmetic progressions
- p a prime in [ N 3 , 2 N 3 ]
- let A ′ = A ∩ [ p ] ⊆ ℤ ∕ p ℤ
Then one of the following holds:
- (i) 𝟙 sup ⁡ t ≠ 0 | 𝟙 A ′ ^ ( t ) | ≥ α 2 1 0 (where the Fourier coefficient is computed in ℤ ∕ p ℤ)
- (ii) There exists an interval J ⊆ [ N ] of length ≥ N 3 such that | A ∩ J | ≥ α ( 1 + α 4 0 0 ) | J |
proof: Proof. We may assume that | A ′ | = | A ∩ [ p ] | ≥ α ( 1 − α 2 0 0 ) p since otherwise
| A ∩ [ p + 1 , N ] | ≥ α N − ( α ( 1 − α 2 0 0 ) p ) = α ( N − p ) + α 2 2 0 0 p ≥ ( α + α 2 4 0 0 ) ( N − p )
so we would be in Case (ii) with J = [ p + 1 , N ]. Let A ″ = A ′ ∩ [ p 3 , 2 p 3 ]. Note that all 3 term arithmetic progressions of the form ( x , x + d , x + 2 d ) ∈ A ′ × A ″ × A ″ are in fact arithmetic progressions in [ N ].
If | A ′ ∩ [ p 3 ] | or | A ′ ∩ [ 2 p 3 , p ] | were at least 2 5 | A ′ |, we would again be in case (ii). So we may assume that | A ″ | ≥ | A ′ | 5.
Now as in Lemma 2.18 and Theorem 2.19,
𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 α ″ p = | A ″ | p 2 T 3 ( 𝟙 A ′ , 𝟙 A ″ , 𝟙 A ″ ) = α ′ ( α ″ ) 2 + ∑ t 𝟙 A ′ ^ ( t ) 𝟙 A ″ ^ ( t ) ¯ 𝟙 2 ⋅ A ″ ^ ( t )
where α ′ = | A ′ | p and α ″ = | A ″ | p. So as before,
𝟙 α ′ α ″ 2 ≤ sup ⁡ t ≠ 0 | 𝟙 A ′ ( t ) | ⋅ α ″ ⁡ ,
provided that α ″ p ≤ 1 2 α ′ ( α ″ ) 2, i.e. 2 p ≤ α ′ α ″. (Check this is satisfied).
Hence
𝟙 sup ⁡ t ≠ 0 | 𝟙 A ′ ^ ( t ) | ≥ α ′ α ″ ⁡ 2 ≥ 1 2 ( α ( 1 − α 2 0 0 ) ) 2 ⋅ 2 5 ≥ α 2 1 0 . □
cloze1: True

html: Lemma 2.23. Assuming that:
- m ∈ ℕ
- φ : [ m ] → ℤ ∕ p ℤ be given by x ↦ t x for some t ≠ 0
- 𝜀 > 0
Then there exists a partition of [ m ] into progressions P i of length l i ∈ [ 𝜀 m 2 , 𝜀 m ] such that
diam ⁡ ( φ ( P i ) ) = max ⁡ x , y ∈ P i | φ ( x ) − φ ( y ) | ≤ 𝜀 p
for all i.
proof: Proof. Let u = ⌊ m ⌋ and consider 0 , t , 2 t , … , u t. By Pigeonhole, there exists 0 ≤ v < w ≤ usuch that | w t − v t | = | ( w − v ) t | ≤ p u. Set s = w − v, so | s t | ≤ p u. Divide [ m ] into residue classes modulo s, each of which has size at least m s ≥ m 4. But each residue class can be divided into arithmetic progressions of the form a , a + s , … , a + d s with 𝜀 u 2 < d ≤ 𝜀 u. The diameter of the image of each progression under φ is | d s t | ≤ d p u ≤ 𝜀 u p u = 𝜀 p. □
cloze1: True

html: Lemma 2.24. Assuming that:
- A ⊆ [ N ] of density α > 0
- p a prime in [ N 3 , 2 N 3 ]
- let A ′ = A ∩ [ p ] ⊆ ℤ ∕ p ℤ
- 𝟙 | 𝟙 A ′ ^ ( t ) | ≥ α 2 2 0 for some t ≠ 0
Then there exists a progression P ⊆ [ N ] of length at least α 2 N 5 0 0 such that | A ∩ P | ≥ α ( 1 + α 8 0 ) | P |.
proof: Proof. Let 𝜀 = α 2 4 0 π, and use Lemma 2.23 to partition [ p ] into progressions P i of length
≥ 𝜀 p 2 ≥ α 2 4 0 π N 3 2 ≥ α 2 N 5 0 0
and diam ⁡ ( φ ( P i ) ) ≤ 𝜀 p. Fix one x i from each of the P i. Then
α 2 2 0 ≤ | f A ′ ^ ( t ) | = | 1 p ∑ i ∑ x ∈ P i f A ′ ( x ) e ( − x t ∕ p ) | = 1 p | ∑ i ∑ x ∈ P i f A ′ ( x ) e ( − x i t ∕ p ) + ∑ i ∑ x ∈ P i f A ′ ( x ) ( e ( − x t ∕ p ) − e ( − x i t ∕ p ) ) | ≤ 1 p ∑ i | ∑ x ∈ P i f A ′ ( x ) | + 1 p ∑ i ∑ x ∈ P i | f A ′ ( x ) | | e ( − x t ∕ p ) − e ( − x i t ∕ p ) ⏟ ≤ 2 π 𝜀 since | t ( x − x i ) | ≤ 𝜀 p |
So
∑ i | ∑ x ∈ P i f A ′ ( x ) | ≥ α 2 4 0 p .
Since f A ′ has mean zero,
∑ i ( | ∑ x ∈ P i f A ′ ( x ) | + ∑ x ∈ P i f A ′ ( x ) ) ≥ α 2 4 0 p ,
hence there exists i such that
| ∑ x ∈ P i f A ′ ( x ) | + ∑ x ∈ P i f A ′ ( x ) ≥ α 2 8 0 | P i |
and so
∑ x ∈ P i f A ′ ( x ) ≥ α 2 1 6 0 | P i | . □
cloze1: True

html: Definition 2.25 (Bohr set). Let Γ ⊆ G ^ and ρ > 0. By the Bohr set B ( Γ , ρ ) we mean the set
B ( Γ , ρ ) = { x ∈ G : | γ ( x ) − 1 | < ρ ∀ ⁡ γ ∈ Γ } .
We call | Γ | the rank of B ( Γ , ρ ), and ρ its width or radius.
nothing: True

html: Lemma 2.27. Assuming that:
- Γ ⊆ G ^ of size d
- ρ > 0
Then
| B ( Γ , ρ ) | ≥ ( ρ 8 ) d | G | .
proof: Proof. Recall 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 A ∗ 𝟙 A ∗ 𝟙 − A ∗ 𝟙 − A ( x ) = ∑ ⁡ γ ∈ G ^ | 𝟙 A ^ ( γ ) | 4 γ ( x ).
Let 𝟙 Γ ∈ Spec ⁡ α 2 ( 𝟙 A ), and note that, for x ∈ B ( Γ , 1 2 ) and γ ∈ Γ, Re ⁡ ( γ ( x ) ) > 0. Hence, for x ∈ B ( Γ , 1 2 ),
𝟙 𝟙 𝟙 Re ⁡ ∑ γ ∈ G ^ | 𝟙 A ^ ( γ ) | 4 γ ( x ) = Re ⁡ ∑ γ ∈ Γ | 𝟙 A ^ ( γ ) | 4 γ ( x ) ⏟ ≥ α 4 + Re ⁡ ∑ γ ∉ Γ | 𝟙 A ^ ( γ ) | 4 γ ( x )
and
𝟙 𝟙 𝟙 | Re ⁡ ∑ γ ∉ Γ | 𝟙 A ^ ( γ ) | 4 γ ( x ) | ≤ sup ⁡ γ ∉ Γ | 𝟙 A ^ ( γ ) | 2 ∑ γ ∉ Γ | 𝟙 A ^ ( γ ) | 2 ≤ ( α 2 ⋅ α ) 2 ⋅ α = α 4 2 . □
cloze1: True

html: Proposition 2.28 (Bogolyubov in a general finite abelian group). Assuming that:
- A ⊆ G of density α > 0
Then there exists Γ ⊆ G ^ of size at most 2 α − 2 such that A + A − A − A ⊇ B ( Γ , ρ ).
proof: Proof. Recall 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 A ∗ 𝟙 A ∗ 𝟙 − A ∗ 𝟙 − A ( x ) = ∑ ⁡ γ ∈ G ^ | 𝟙 A ^ ( γ ) | 4 γ ( x ).
Let 𝟙 Γ ∈ Spec ⁡ α 2 ( 𝟙 A ), and note that, for x ∈ B ( Γ , 1 2 ) and γ ∈ Γ, Re ⁡ ( γ ( x ) ) > 0. Hence, for x ∈ B ( Γ , 1 2 ),
𝟙 𝟙 𝟙 Re ⁡ ∑ γ ∈ G ^ | 𝟙 A ^ ( γ ) | 4 γ ( x ) = Re ⁡ ∑ γ ∈ Γ | 𝟙 A ^ ( γ ) | 4 γ ( x ) ⏟ ≥ α 4 + Re ⁡ ∑ γ ∉ Γ | 𝟙 A ^ ( γ ) | 4 γ ( x )
and
𝟙 𝟙 𝟙 | Re ⁡ ∑ γ ∉ Γ | 𝟙 A ^ ( γ ) | 4 γ ( x ) | ≤ sup ⁡ γ ∉ Γ | 𝟙 A ^ ( γ ) | 2 ∑ γ ∉ Γ | 𝟙 A ^ ( γ ) | 2 ≤ ( α 2 ⋅ α ) 2 ⋅ α = α 4 2 . □
nothing: True

html: Theorem 3.1 (Khintchine’s inequality). Assuming that:
- p ∈ [ 2 , ∞ )
- X 1 , X 2 , … , X n independent random variables
- ℙ ( X i = x i ) = 1 2 = ℙ ( X i = − x i )
Then
∥ ∑ i = 1 n X i ∥ L p ( ℙ ) = O ( p 1 2 ( ∑ i = 1 n ∥ X i ∥ L 2 ( ℙ ) 2 ) 1 2 ) .
proof: Proof. By nesting of norms, it suffices to prove the case p = 2 k for some k ∈ ℕ. Write X = ∑ ⁡ i = 1 n X i, and assume ∑ ⁡ i = 1 n ∥ X i ∥ L ∞ ( ℙ ) 2 = 1. Note that in fact ∑ ⁡ i = 1 n ∥ X i ∥ L 2 ( ℙ ) 2 = ∑ i = 1 n ∥ X i ∥ L ∞ ( ℙ ) 2, hence ∑ ⁡ i = 1 n ∥ X i ∥ L 2 ( ℙ ) 2 = 1.
By Chernoff’s inequality (Example 2.5), for all 𝜃 > 0 we have
ℙ ( | X | ≥ 𝜃 ) ≤ 4 exp ⁡ ( − 𝜃 2 4 ) ,
and so using the fact that ℙ ( | X | ≤ t ) = ∫ 0 t ρ X ( s ) d s we have
∥ X ∥ L 2 k ( ℙ ) 2 k = ∫ 0 ∞ t 2 k ρ X ( t ) d t = ∫ 0 ∞ 2 k t 2 k − 1 ℙ ( | X | ≥ t ) d t integration by parts ≤ ∫ 0 ∞ 8 k t 2 k − 1 exp ⁡ ( − t 2 4 ) d t ⏟ = : I ( K )
We shall show by induction on k that I ( K ) ≤ 2 2 k ( 2 k ) k 4 k. Indeed, when k = 1,
∫ 0 ∞ t exp ⁡ ( − t 2 4 ) d t = [ − 2 exp ⁡ ( − t 2 4 ) ] 0 ∞ = 2 ≤ 2 .
For k > 1, integrate by parts to find that
I ( K ) = ∫ 0 ∞ t 2 k − 2 ⏟ u ⋅ t exp ⁡ ( − t 2 4 ) ⏟ v d t = [ t 2 k − 2 ⋅ ( − 2 exp ⁡ ( − t 2 4 ) ) ] 0 ∞ − ∫ 0 ∞ ( 2 k − 2 ) t 2 k − 3 ( − 2 exp ⁡ ( − t 2 4 ) ) d t = 4 ( k − 1 ) ∫ 0 ∞ t 2 ( k − 1 ) − 1 exp ⁡ ( − t 2 4 ) d t = 4 ( k − 1 ) I ( K − 1 ) ≤ 4 ( k − 1 ) 2 2 ( k − 1 ) ( 2 ( k − 1 ) ) k − 1 4 ( k − 1 ) ≤ 2 2 k ( 2 k ) k 4 k □
nothing: True

html: Theorem 3.4 (Special case of Chang’s Theorem). Assuming that:
- A ⊆ 𝔽 2 n of density α > 0
- ρ > 0
Then there exists H ≤ 𝔽 2 n ^ of dimension O ( ρ − 2 log ⁡ α − 1 ) such that 𝟙 H ⊇ Spec ⁡ ρ ( 𝟙 A ).
proof: Proof. Let 𝟙 Γ ⊆ Spec ⁡ ρ ( 𝟙 A ) be a maximal linearly independent set. Let 𝟙 H = ⟨ Spec ⁡ ρ ( 𝟙 A ) ⟩. Clearly dim ⁡ ( H ) = | Γ |. By Corollary 3.3, for all p ∈ ( 1 , 2 ],
𝟙 𝟙 𝟙 ( ρ α ) 2 | Γ | ≤ ∑ γ ∈ Γ | 𝟙 A ^ ( γ ) | 2 = ∥ 𝟙 A ^ ∥ l 2 ( Γ ) 2 = O ( p p − 1 ∥ 𝟙 A ∥ L p ( 𝔽 2 n ) 2 ) ,
so
| Γ | = O ( ρ − 2 α − 2 α 2 ∕ p p p − 1 ) .
Set p = 1 + ( log ⁡ α − 1 ) − 1 to get | Γ | = O ( ρ − 2 α − 2 ( α 2 ⋅ e 2 ) ( log ⁡ α − 1 + 1 ) ). □
nothing: True

html: Definition 3.5 (Dissociated). Let G be a finite abelian group. We say S ⊆ G is dissociated if ∑ ⁡ s ∈ S 𝜀 s s = 0 for 𝜀 ∈ { − 1 , 0 , 1 } | S |, then 𝜀 ≡ 0.
nothing: True

html: Theorem 3.6 (Chang’s Theorem). Assuming that:
- G a finite abelian group
- A ⊆ G be of density α > 0
- 𝟙 Λ ⊇ Spec ⁡ ρ ( 𝟙 A ) is dissociated
Then | Λ | = O ( ρ − 2 log ⁡ α − 1.
proof: Proof. First assume the distribution of the X i’s is symmetric, i.e. ℙ ( X i = a ) = ℙ ( X i = − a ) for all a ∈ ℝ. Partition the probability space Ω into sets Ω 1 , Ω 2 , … , Ω 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 ∈ [ M ],
∥ ∑ i = 1 n X i ∥ L p ( ℙ j ) p = O ( p p ∕ 2 ( ∑ i = 1 n ∥ X i ∥ L 2 ( ℙ j ) 2 ) p ∕ 2 ) = O ( p p ∕ 2 ∥ ∑ i = 1 n | X i | 2 ∥ L p ∕ 2 ( ℙ j ) p ∕ 2 )
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 , … , Y n be such that Y i ∼ X i and X 1 , X 2 , … , X n , Y 1 , Y 2 , … , Y n are all independent. Applying the symmetric case to X i − Y i,
∥ ∑ i = 1 n ( X i − Y i ) ∥ L p ( ℙ × ℙ ) = O ( p 1 2 ∥ ∑ i = 1 n | X i − Y i | 2 ∥ L p ∕ 2 ( ℙ × ℙ ) 1 2 ) = O ( p 1 2 ∥ ∑ i = 1 n | X i − Y i | 2 ∥ L p ∕ 2 ( ℙ ) 1 2 )
But then
∥ ∑ i = 1 n X i ∥ L p ( ℙ ) = ∥ ∑ i = 1 n X i − 𝔼 Y ∑ i = 1 n Y i ⏟ = 0 ∥ L p ( ℙ ) p = 𝔼 X | ∑ X i − 𝔼 Y ∑ Y i | p = 𝔼 X | 𝔼 Y ∑ ( X i − Y i ) | p ≤ 𝔼 X 𝔼 Y | ∑ ( X i − Y i ) | p by Jensen say = ∥ ∑ ( X i − Y i ) ∥ L p ( ℙ × ℙ ) p
concluding the proof. □
nothing: True

html: Theorem 3.7 (Marcinkiewicz-Zygmund). Assuming that:
- p ∈ [ 2 , ∞ )
- Ł X 1 , X 2 , … , X n ∈ Ł p ( ℙ ) independent random variables
- 𝔼 ∑ ⁡ i = 1 n X i = 0
Then
∥ ∑ i = 1 n X i ∥ L p ( ℙ ) = O ( p 1 2 ∥ ∑ i = 1 n | X i | 2 ∥ L p ∕ 2 ( ℙ ) 1 2 ) .
proof: Proof. First assume the distribution of the X i’s is symmetric, i.e. ℙ ( X i = a ) = ℙ ( X i = − a ) for all a ∈ ℝ. Partition the probability space Ω into sets Ω 1 , Ω 2 , … , Ω 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 ∈ [ M ],
∥ ∑ i = 1 n X i ∥ L p ( ℙ j ) p = O ( p p ∕ 2 ( ∑ i = 1 n ∥ X i ∥ L 2 ( ℙ j ) 2 ) p ∕ 2 ) = O ( p p ∕ 2 ∥ ∑ i = 1 n | X i | 2 ∥ L p ∕ 2 ( ℙ j ) p ∕ 2 )
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 , … , Y n be such that Y i ∼ X i and X 1 , X 2 , … , X n , Y 1 , Y 2 , … , Y n are all independent. Applying the symmetric case to X i − Y i,
∥ ∑ i = 1 n ( X i − Y i ) ∥ L p ( ℙ × ℙ ) = O ( p 1 2 ∥ ∑ i = 1 n | X i − Y i | 2 ∥ L p ∕ 2 ( ℙ × ℙ ) 1 2 ) = O ( p 1 2 ∥ ∑ i = 1 n | X i − Y i | 2 ∥ L p ∕ 2 ( ℙ ) 1 2 )
But then
∥ ∑ i = 1 n X i ∥ L p ( ℙ ) = ∥ ∑ i = 1 n X i − 𝔼 Y ∑ i = 1 n Y i ⏟ = 0 ∥ L p ( ℙ ) p = 𝔼 X | ∑ X i − 𝔼 Y ∑ Y i | p = 𝔼 X | 𝔼 Y ∑ ( X i − Y i ) | p ≤ 𝔼 X 𝔼 Y | ∑ ( X i − Y i ) | p by Jensen say = ∥ ∑ ( X i − Y i ) ∥ L p ( ℙ × ℙ ) p
concluding the proof. □
nothing: True

html: Theorem 3.8 (Croot-Sisask almost periodicity). Assuming that:
- G a finite abelian group
- 𝜀 > 0
- p ∈ [ 2 , ∞ )
- A , B ⊆ G are such that | A + B | ≤ K | A |
- f : G → ℂ
Then there exists b ∈ B and a set X ⊆ B − b such that | X | ≥ 2 − 1 K − O ( 𝜀 − 2 p ) | B | and
∥ τ x f ∗ μ A − f ∗ μ A ∥ L p ( G ) ≤ 𝜀 ∥ f ∥ L p ( G ) ∀ ⁡ x ∈ X ,
where τ x g ( y ) = g ( y + x ) for all y ∈ G, and as a reminder, μ A is the characteristic measure of A.
proof: Proof. The main idea is to approximate
f ∗ μ A ( y ) = 𝔼 x f ( y − x ) μ A ( x ) = 𝔼 x ∈ A f ( y − x )
by 1 m ∑ ⁡ 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 ∈ G, define Z i ( y ) = τ − z i f ( y ) − f ∗ μ A ( y ). For each y ∈ G, these are independent random variables with mean 0, so by Marcinkiewicz-Zygmund,
∥ ∑ i = 1 m Z i ( y ) ∥ L p ( ℙ ) p = O ( p p ∕ 2 ∥ ∑ i = 1 m | Z i ( y ) | 2 ∥ L p ∕ 2 ( ℙ ) p ∕ 2 ) = O ( p p ∕ 2 𝔼 ( z 1 , … , z m ) ∈ A m | ∑ i = 1 m | Z i ( y ) | 2 | p ∕ 2 )
By Hölder with 1 p ′ + 2 p = 1, we get
| ∑ i = 1 m | Z i ( y ) | 2 | p ∕ 2 ≤ ( ∑ i = 1 m 1 p ′ ) 1 p ′ ⋅ p 2 ( ∑ i = 1 m | Z i ( y ) | 2 ⋅ p ∕ 2 ) 2 p ⋅ p 2 ≤ ( ∑ i = 1 m 1 p ′ ) p 2 − 1 ( ∑ i = 1 m | Z i ( y ) | 2 ⋅ p ∕ 2 ) 2 p ⋅ p 2 = m p ∕ 2 − 1 ∑ i = 1 m | Z i ( y ) | p
so
∥ ∑ i = 1 m Z i ( y ) ∥ L p ( ℙ ) p = O ( p p ∕ 2 m p ∕ 2 − 1 𝔼 ( z 1 , … , z m ) ∈ A m ∑ i = 1 m | Z i ( y ) | p ) .
Summing over all y ∈ G, we have
𝔼 y ∈ G ∥ ∑ i = 1 m Z i ( y ) ∥ L p ( ℙ ) p = O ( p p ∕ 2 m p ∕ 2 − 1 𝔼 ( z 1 , … , z m ) ∈ A m ∑ i = 1 m 𝔼 y ∈ G | Z i ( y ) | p )
with
( 𝔼 y ∈ G | Z i ( y ) | p ) 1 p = ∥ Z i ∥ L p ( G ) = ∥ τ − z i f − f ∗ μ A ∥ L p ( G ) ≤ , ∥ τ − z i f ∥ L p ( G ) + ∥ f ∗ μ A ∥ L p ( G ) ≤ ∥ f ∥ L p ( G ) + ∥ f ∥ L q ( G ) ∥ μ A ∥ L 1 ( G ) ≤ 2 ∥ f ∥ L p ( G )
by Young / Hölder (∥ f ∗ g ∥ L r ( G ) ≤ ∥ f ∥ L p ( G ) ∥ g ∥ L q ( G ) where 1 + 1 r = 1 p + 1 q).
So we have
𝔼 ( z 1 , … , z m ) ∈ A m 𝔼 y ∈ G | ∑ i = 1 m Z i ( y ) | p = O ( p p ∕ 2 m p ∕ 2 − 1 ∑ 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 ( 𝜀 4 ∥ f ∥ L p ( G ) ) p. whence
𝔼 ( z 1 , … , z m ) ∈ A m 𝔼 y ∈ G | 1 m ∑ i = 1 m τ − z i f ( y ) − f ∗ μ A ( y ) | p ⏟ = ( ∗ ) = O ( ( 4 p ) p ∕ 2 m p ∕ 2 ∥ f ∥ L p ( G ) p ) = ( 𝜀 4 ∥ f ∥ L p ( G ) ) p .
Write
L = { z = ( z 1 , … , z m ) ∈ A m : ( ∗ ) ≤ ( 𝜀 2 ∥ f ∥ L p ( G ) ) p } .
By Markov inequality, since
𝔼 ( ∗ ) ≤ ( 𝜀 4 ∥ f ∥ L p ( G ) ) p = 2 − p ( 𝜀 2 ∥ f ∥ L p ( G ) ) p ,
we have
| A m ∖ L | | A m | = ℙ ( ( ∗ ) ≥ ( 𝜀 2 ∥ f ∥ L p ( G ) ) p ) ≤ ℙ ( ( ∗ ) ≥ 2 p 𝔼 ( ∗ ) ) ≤ 2 − p
so | L | ≥ ( 1 − 1 2 p ) | A | m ≥ 1 2 | A | m. Let
D = { ( b , b , … ⁡ , b ) ⏟ m : b ∈ B } .
Now L + D ⊆ ( A + B ) m, whence
| L + D | ≤ | A + B | m ≤ K m | A | m ≤ 2 K m | L | .
By Lemma 1.17,
E ( L , D ) ≥ | L | 2 | D | 2 | L + D | ≥ 1 2 K − m | D | 2 | L |
so there are at least | D | 2 2 K m pairs ( d 1 , d 2 ) ∈ D × D such that r L − L ( d 2 − d 1 ) > 0. In particular, there exists b ∈ u b and X ⊆ B − b of size | X | ≥ | D | 2 K m = | B | 2 K m such that for all x ∈ X, there exists l 2 ( x ) ∈ L such that for all i ∈ [ m ], l 1 ( x ) i − l 2 ( x ) i = x. But then for each x ∈ X, by the triangle inequality,
∥ τ − x f ∗ μ A − f ∗ μ A ∥ L p ( G ) ≤ ∥ τ − x f ∗ μ A − τ − x ( 1 m ∑ i = 1 m τ − l 2 ( x ) i f ) ∥ L p ( G ) + ∥ τ − x ( 1 m ∑ i = 1 m τ − l 2 ( x i ) f ) − f ∗ μ A ∥ L p ( G ) = ∥ f ∗ μ A − 1 m ∑ i = 1 m τ − l 2 ( x ) i f ∥ L p ( G ) + ∥ 1 m ∑ i = 1 m τ − x − l 2 ( x ) i f − f ∗ μ A ∥ L p ( G ) ≤ 2 ⋅ 𝜀 2 ∥ f ∥ L p ( G )
by definion of L. □
nothing: True

html: Theorem 3.9 (Bogolyubov again, after Sanders). Assuming that:
- A ⊆ 𝔽 p n of density α > 0
Then there exists a subspace V ≤ 𝔽 p n of codimension O ( log ⁡ 4 α − 1 ) such tht V ⊆ A + A − A − A.
proof: Proof. Every P ∈ V n d can be written as a linear combination of monomials in M n d, so
P ( x + y ) = ∑ m , m ′ ∈ M n d deg ⁡ ( m m ′ ) ≤ d c m , m ′ m ( x ) m ′ ( y )
for some coefficients c m , m ′. Clearly at least one of m , m ′ must have degree ≤ d 2, whence
P ( x + y ) = ∑ m ∈ M n d ∕ 2 m ( x ) F m ( y ) + ∑ m ′ ∈ M n d ∕ 2 m ′ ( y ) G m ′ ( x ) ,
for some families of polynomials ( F m ) m ∈ M n d ∕ 2, ( G m ′ ) m ′ ∈ M n d ∕ 2.
Viewing ( P ( x + y ) ) x , y ∈ A as a | A | × | A |-matrix C, we see that C can be written as the sum of at most 2 m d ∕ 2 matrices, each of which has rank 1. Thus rank ⁡ ( C ) ≤ 2 m d ∕ 2. But by assumption, C is a diagonal matrix whose rank equals | { a ∈ A : P ( a + a ) ≠ 0 } |. □
nothing: True

html: Theorem 4.1 (Ellenberg-Gijswijt, following Croot-Lev-Pach). Assuming that:
- A ⊆ 𝔽 3 n contains no non-trivial 3 term arithmetic progressions
Then | A | = o ( 2 . 7 5 6 ) n.
proof: Proof. Every P ∈ V n d can be written as a linear combination of monomials in M n d, so
P ( x + y ) = ∑ m , m ′ ∈ M n d deg ⁡ ( m m ′ ) ≤ d c m , m ′ m ( x ) m ′ ( y )
for some coefficients c m , m ′. Clearly at least one of m , m ′ must have degree ≤ d 2, whence
P ( x + y ) = ∑ m ∈ M n d ∕ 2 m ( x ) F m ( y ) + ∑ m ′ ∈ M n d ∕ 2 m ′ ( y ) G m ′ ( x ) ,
for some families of polynomials ( F m ) m ∈ M n d ∕ 2, ( G m ′ ) m ′ ∈ M n d ∕ 2.
Viewing ( P ( x + y ) ) x , y ∈ A as a | A | × | A |-matrix C, we see that C can be written as the sum of at most 2 m d ∕ 2 matrices, each of which has rank 1. Thus rank ⁡ ( C ) ≤ 2 m d ∕ 2. But by assumption, C is a diagonal matrix whose rank equals | { a ∈ A : P ( a + a ) ≠ 0 } |. □
nothing: True

html: Lemma 4.2. Assuming that:
- A ⊆ 𝔽 3 n
- P ∈ V n d is a polynomial
- P ( a + a ′ ) = 0 for all a ≠ a ′ ∈ A
Then
| { a ∈ A : P ( 2 a ) ≠ 0 } | ≤ 2 m d ∕ 2 .
proof: Proof. Every P ∈ V n d can be written as a linear combination of monomials in M n d, so
P ( x + y ) = ∑ m , m ′ ∈ M n d deg ⁡ ( m m ′ ) ≤ d c m , m ′ m ( x ) m ′ ( y )
for some coefficients c m , m ′. Clearly at least one of m , m ′ must have degree ≤ d 2, whence
P ( x + y ) = ∑ m ∈ M n d ∕ 2 m ( x ) F m ( y ) + ∑ m ′ ∈ M n d ∕ 2 m ′ ( y ) G m ′ ( x ) ,
for some families of polynomials ( F m ) m ∈ M n d ∕ 2, ( G m ′ ) m ′ ∈ M n d ∕ 2.
Viewing ( P ( x + y ) ) x , y ∈ A as a | A | × | A |-matrix C, we see that C can be written as the sum of at most 2 m d ∕ 2 matrices, each of which has rank 1. Thus rank ⁡ ( C ) ≤ 2 m d ∕ 2. But by assumption, C is a diagonal matrix whose rank equals | { a ∈ A : P ( a + a ) ≠ 0 } |. □
cloze1: True

html: Proposition 4.3. Assuming that:
- A ⊆ 𝔽 3 n a set containing no non-trivial 3 term arithmetic progressions
Then | A | ≤ 3 m 2 n ∕ 3.
proof: Proof. Let d ∈ [ 0 , 2 n ] be an integer to be determined later. Let W be the space of polynomials in V n d that vanish on ( 2 ⋅ A ) c. We have
dim ⁡ ( W ) ≥ dim ⁡ ( V n d ) − | ( 2 ⋅ A ) c | = m d − ( 3 n − | A | ) .
We claim that there exists P ∈ W such that | supp ⁡ ( P ) | ≥ dim ⁡ ( W ). Indeed, pick P ∈ W with maximal support. If | supp ⁡ ( P ) | < dim ⁡ ( W ), then there would be a non-zero polynomial Q ∈ W vanishing on supp ⁡ ( P ), in which case supp ⁡ ( P + Q ) ⊋ supp ⁡ ( P ), contradicting the choice of P.
Now by assumption,
{ a + a ′ : a ≠ a ′ ∈ A } ∩ 2 ⋅ A = ∅ .
So any polynomial that vanishes on ( 2 ⋅ A ) c vanishes on { a + a ′ : a ≠ a ′ ∈ A }. By Lemma 4.2 we now have that,
| A | − ( 3 n − m d ) = m d − ( 3 n − | A | ) ≤ dim ⁡ ( W ) ≤ | supp ⁡ ( P ) | = | { x ∈ 𝔽 3 n : P ( x ) ≠ 0 } | = | { a ∈ A : P ( 2 a ) ≠ 0 } | ≤ 2 m d ∕ 2
Hence | A | ≥ 3 n − m d + 2 m d ∕ 2. But the monomials in M n ∖ M n d are in bijection with the ones in M 2 n − d via x 1 α 1 ⋯ x n α n ↦ x 1 2 − α 1 ⋯ x n 2 − α n, whence 3 n − m d = m 2 n − d. Thus setting d = 4 n 3, we have | A | ≤ m 2 n ∕ 3 + 2 m 2 n ∕ 3 = 3 m 2 n ∕ 3. □
cloze1: True

html: Definition 4.5 (U 2-norm). Given f : G → ℂ, define its U 2-norm by the formula
∥ f ∥ U 2 ( G ) 4 = 𝔼 x , a , b ∈ G f ( x ) f ( x + a ) f ( x + b ) ¯ f ( x + a + b ) .
nothing: True

html: Lemma 4.6. Assuming that:
- f 1 , f 2 , f 3 : G → ℂ
Then
| T 3 ( f 1 , f 2 , f 3 ) | ≤ min ⁡ i ∈ [ 3 ] ∥ f i ∥ U 2 ( G ) ⋅ ∏ j ≠ i ∥ f j ∥ L ∞ ( G ) .
proof: Proof. We have seen that
∥ f ∥ U 2 ( 𝔽 p n ) 2 ≤ ∥ f ^ ∥ l ∞ ( 𝔽 p n ^ ) ∥ f ∥ L 2 ( 𝔽 p n ) ≤ ∥ f ^ ∥ l ∞ ( 𝔽 p n ^ ) ,
so
δ 2 ≤ ∥ f ^ ∥ l ∞ ( 𝔽 p n ^ ) = sup ⁡ t ∈ 𝔽 p n ^ | 𝔼 x f ( x ) e ( − x ⋅ t ∕ p ) | . □
cloze1: True

html: Theorem 4.7 (U 2 Inverse Theorem). Assuming that:
- f : 𝔽 p n → ℂ
- ∥ f ∥ L ∞ ( 𝔽 p n ) ≤ 1
- δ > 1
- ∥ f ∥ U 2 ( 𝔽 p n ) ≥ δ
Then there exists b ∈ 𝔽 p n such that
| 𝔼 x ∈ 𝔽 p n f ( x ) e ( − x ⋅ b ∕ p ) | ≥ δ 2 .
In other words, | ⟨ f , ϕ ⟩ | ≥ δ 2 for ϕ ( x ) = e ( − x ⋅ b ∕ p ) and we say “f correlates with a linear phase function”.
proof: Proof. We have seen that
∥ f ∥ U 2 ( 𝔽 p n ) 2 ≤ ∥ f ^ ∥ l ∞ ( 𝔽 p n ^ ) ∥ f ∥ L 2 ( 𝔽 p n ) ≤ ∥ f ^ ∥ l ∞ ( 𝔽 p n ^ ) ,
so
δ 2 ≤ ∥ f ^ ∥ l ∞ ( 𝔽 p n ^ ) = sup ⁡ t ∈ 𝔽 p n ^ | 𝔼 x f ( x ) e ( − x ⋅ t ∕ p ) | . □
nothing: True

html: Definition 4.8 (U 3 norm). Given f : G → ℂ, define its U 3 norm by
∥ f ∥ U 3 ( G ) 8 : = 𝔼 ∈ x , a , b , c f ( x ) f ( x + a ) f ( x + b ) f ( x + c ) ¯ f ( x + a + b ) f ( x + b + c ) f ( x + a + c ) f ( x + a + b + c ) ¯ = 𝔼 x , h 1 , h 2 , h 3 ∈ G ∏ 𝜀 ∈ { 0 , 1 } 3 C | 𝜀 | f ( x + 𝜀 ⋅ h )
where C g ( x ) = g ( x ) ¯ and | 𝜀 | denotes the number of ones in 𝜀.
nothing: True

html: Definition 4.9 (U 3 inner product). Given functions f 𝜀 : G → ℂ for 𝜀 ∈ { 0 , 1 } 3, define their U 3 inner product by
⟨ ( f 𝜀 ) 𝜀 ∈ { 0 , 1 } 3 ⟩ U 3 ( G ) = 𝔼 x , h 1 , h 2 , h 3 ∈ G ∏ 𝜀 ∈ { 0 , 1 } 3 C | 𝜀 | f 𝜀 ( x + 𝜀 ⋅ h ) .
nothing: True

html: Lemma 4.10 (Gowers–Cauchy–Schwarz Inequality). Assuming that:
- f 𝜀 : G → ℂ, 𝜀 ∈ { 0 , 1 } 3
Then
| ⟨ ( f 𝜀 ) 𝜀 ∈ { 0 , 1 } 3 ⟩ U 3 ( G ) ≤ ∏ 𝜀 ∈ { 0 , 1 } 3 ∥ f 𝜀 ∥ U 3 ( G ) .
proof: Proof. We additionally assume f = f 1 = f 2 = f 3 = f 4 to make the proof easier to follow, but the same ideas are used for the general case. We additionally assume ∥ f ∥ L ∞ ( 𝔽 5 n ) ≤ 1, by rescaling, since the inequality is homogeneous.
Reparametrising, we have
T 4 ( f , f , f , f ) = 𝔼 a , b , c , d ∈ 𝔽 5 n f ( 3 a + 2 b + c ) f ( 2 a + b − d ) f ( a − c − 2 d ) f ( − b − 2 c − 3 d ) | T 4 ( f , f , f , f ) | 8 ≤ ( 𝔼 a , b , c | 𝔼 d f ( 2 a + b − d ) f ( a − c − 2 d ) f ( − b − 2 c − 3 d ) | 2 ) 4 = ( 𝔼 d , d ′ 𝔼 a , b f ( 2 a + b + d ) f ( 2 a + b − d ′ ) ¯ 𝔼 c f ( a − c − 2 d ) f ( a − c − 2 d ′ ) ¯ f ( − b − 2 c − 3 d ) f ( − b − 2 c − 3 d ′ ) ¯ ) 4 ≤ ( 𝔼 d , d ′ 𝔼 a , b | 𝔼 c f ( a − c − 2 d ) f ( a − c − 2 d ′ ) ¯ f ( − b − 2 c − 3 d ) f ( − b − 2 c − 3 d ′ ) ¯ | 2 ) 2 = ( 𝔼 c , c ′ , d , d ′ 𝔼 a f ( a − c − 2 d ) f ( a − c ′ − 2 d ) ¯ f ( a − c − 2 d ′ ) ¯ f ( a − c ′ − 2 d ′ ) 𝔼 b f ( − b − 2 c − 3 d ) f ( − b − 2 c ′ − 3 d ) ¯ f ( − b − 2 c − 3 d ′ ) ¯ f ( − b − 2 c ′ − 3 d ′ ) ) 2 ≤ 𝔼 c , c ′ , d , d ′ , a | 𝔼 b f ( − b − 2 c − 3 d ) f ( − b − 2 c ′ − 3 d ) ¯ f ( − b − 2 c − 3 d ′ ) ¯ f ( − b − 2 c ′ − 3 d ′ ) | 2 = 𝔼 b , b ′ , c , c ′ , d , d ′ f ( − b − 2 c − 3 d ) f ( − b ′ − 2 c − 3 d ) ¯ f ( − b − 2 c ′ − 3 d ) ¯ f ( − b ′ − 2 c ′ − 3 d ) f ( − b − 2 c − 3 d ′ ) ¯ f ( − b ′ − 2 c − 3 d ′ ) f ( − b − 2 c ′ − 3 d ′ ) f ( − b ′ − 2 c ′ − 3 d ′ ) ¯ □
nothing: True

html: Proposition 4.11. Assuming that:
- f 1 , f 2 , f 3 , f 4 : 𝔽 5 n → ℂ
Then
T 4 ( f 1 , f 2 , f 3 , f 4 ) ≤ min ⁡ i ∈ [ 4 ] ∥ f i ∥ U 3 ( G ) ∏ j ≠ i ∥ f j ∥ L ∞ ( 𝔽 5 n ) .
proof: Proof. We additionally assume f = f 1 = f 2 = f 3 = f 4 to make the proof easier to follow, but the same ideas are used for the general case. We additionally assume ∥ f ∥ L ∞ ( 𝔽 5 n ) ≤ 1, by rescaling, since the inequality is homogeneous.
Reparametrising, we have
T 4 ( f , f , f , f ) = 𝔼 a , b , c , d ∈ 𝔽 5 n f ( 3 a + 2 b + c ) f ( 2 a + b − d ) f ( a − c − 2 d ) f ( − b − 2 c − 3 d ) | T 4 ( f , f , f , f ) | 8 ≤ ( 𝔼 a , b , c | 𝔼 d f ( 2 a + b − d ) f ( a − c − 2 d ) f ( − b − 2 c − 3 d ) | 2 ) 4 = ( 𝔼 d , d ′ 𝔼 a , b f ( 2 a + b + d ) f ( 2 a + b − d ′ ) ¯ 𝔼 c f ( a − c − 2 d ) f ( a − c − 2 d ′ ) ¯ f ( − b − 2 c − 3 d ) f ( − b − 2 c − 3 d ′ ) ¯ ) 4 ≤ ( 𝔼 d , d ′ 𝔼 a , b | 𝔼 c f ( a − c − 2 d ) f ( a − c − 2 d ′ ) ¯ f ( − b − 2 c − 3 d ) f ( − b − 2 c − 3 d ′ ) ¯ | 2 ) 2 = ( 𝔼 c , c ′ , d , d ′ 𝔼 a f ( a − c − 2 d ) f ( a − c ′ − 2 d ) ¯ f ( a − c − 2 d ′ ) ¯ f ( a − c ′ − 2 d ′ ) 𝔼 b f ( − b − 2 c − 3 d ) f ( − b − 2 c ′ − 3 d ) ¯ f ( − b − 2 c − 3 d ′ ) ¯ f ( − b − 2 c ′ − 3 d ′ ) ) 2 ≤ 𝔼 c , c ′ , d , d ′ , a | 𝔼 b f ( − b − 2 c − 3 d ) f ( − b − 2 c ′ − 3 d ) ¯ f ( − b − 2 c − 3 d ′ ) ¯ f ( − b − 2 c ′ − 3 d ′ ) | 2 = 𝔼 b , b ′ , c , c ′ , d , d ′ f ( − b − 2 c − 3 d ) f ( − b ′ − 2 c − 3 d ) ¯ f ( − b − 2 c ′ − 3 d ) ¯ f ( − b ′ − 2 c ′ − 3 d ) f ( − b − 2 c − 3 d ′ ) ¯ f ( − b ′ − 2 c − 3 d ′ ) f ( − b − 2 c ′ − 3 d ′ ) f ( − b ′ − 2 c ′ − 3 d ′ ) ¯ □
cloze1: True

html: Theorem 4.12 (Szemeredi’s Theorem for 4-APs). Assuming that:
- A ⊆ 𝔽 5 n a set containing no non-trivial 4 term arithmetic progressions
Then | A | = o ( 5 n ).
proof: Proof (sketch). Let Δ h f ( x ) denote f ( x ) f ( x + h ) ¯.
∥ f ∥ U 3 ( G ) = ( 𝔼 h ∥ Δ h f ∥ U 2 4 ) 1 8.
- STEP 1: Weak linearity. See reference.
- STEP 2: Strong linearity. We will spend the rest of the lecture discussing this in detail.
- STEP 3: Symmetry argument. Problem 8 on Sheet 3.
- STEP 4: Integration step. Problem 9 on Sheet 3.
STEP 1: If ∥ f ∥ U 3 ( G ) 8 = 𝔼 h ∥ Δ h ∥ U 2 4 ≥ δ 8, then for at least a δ 8 2-proportion of h ∈ 𝔽 5 n, δ 8 2 ≤ ∥ Δ h f ∥ U 2 4 ≤ ∥ Δ h f ^ ∥ l ∞ 2. So for each such h ∈ 𝔽 5 n, there exists t h such that | Δ h f ^ ( t h ) | 2 ≥ δ 8 2.
Proposition 4.15. Assuming that:
- f : 𝔽 5 n → ℂ
- ∥ f ∥ ∞ ≤ 1
- ∥ f ∥ U 3 ( G ) ≥ δ
- | 𝔽 5 n | = Ω δ ( 1 )
Then there exists S ⊆ 𝔽 5 n with | S | = Ω δ ( | 𝔽 5 n | ) and a function ϕ : S → 𝔽 5 n ^ such that
- (i) | Δ h f ^ ( ϕ ( h ) ) | = Ω δ ( 1 );
- (ii) There are at least Ω δ ( | 𝔽 5 n | 3 ) quadruples ( s 1 , s 2 , s 3 , s 4 ) ∈ S 4 such that s 1 + s 2 = s 3 + s 4 and ϕ ( s 1 ) + ϕ ( s 2 ) + ϕ ( s 4 ).
STEP 2: If S and ϕ are as above, then there is a linear function ψ : 𝔽 5 n → 𝔽 5 n ^ which coincides with ϕ for many elements of S.
Proposition 4.16. Assuming that:
- S and ϕ given as in Proposition 4.15
Then there exists n × n matrix M with entries in 𝔽 5 and b ∈ 𝔽 5 n such that ψ ( x ) = M x + b (ψ : 𝔽 5 n → 𝔽 5 n ^) satisfies ψ ( x ) = ϕ ( x ) for Ω δ ( | 𝔽 5 n | ) elements x ∈ S.
Proof. Consider the graph of ϕ, Γ = { ( h , ϕ ( h ) ) : h ∈ S } ⊆ 𝔽 5 n × 𝔽 5 n ^. By Proposition 4.15, Γ has Ω δ ( | 𝔽 5 n | 3 ) additive quadruples.
By Balog–Szemeredi–Gowers, Schoen, there exists Γ ′ ⊆ Γ with | Γ ′ | = Ω δ ( | Γ | ) = Ω δ ( | 𝔽 5 n | ) and | Γ ′ + Γ ′ | = O δ ( | Γ ′ | ). udefine S ′ ⊆ S by Γ ′ = { ( h , ϕ ( h ) ) : h ∈ S ′ } and note | S ′ | = Ω δ ( | 𝔽 5 n | ).
By Freiman-Ruzsa applied to Γ ′ ⊆ 𝔽 5 n × 𝔽 5 n ^, there exists a subspace H ≤ 𝔽 5 n × 𝔽 5 n ^ with | H | = O δ ( | Γ ′ | ) = O δ ( | 𝔽 5 n | ) such that Γ ′ ⊆ H.
Denote by π : 𝔽 5 n × 𝔽 5 n ^ → 𝔽 5 n the projection onto the first n coordinates. By construction, π ( H ) ⊇ S ′. Moreover, since | S ′ | = Ω δ ( | 𝔽 5 n | ),
| ker ⁡ ( π | H ) | = | H | | Im ⁡ ( π | H ) | = O δ ( | 𝔽 5 n | ) | S ′ | = O δ ( 1 ) .
We may thus partition H into O δ ( 1 ) cosets of some subspace H ∗ such that π | H is injective on each coset. By averaging, there exists a coset x + H ∗ such that
| Γ ′ ∩ ( x + H ∗ ) | = Ω δ ( | Γ ′ | ) = Ω δ ( | 𝔽 5 n | ) .
Set Γ ″ = Γ ′ ∩ ( x + H ∗ ), and define S ″ accordingly.
Now π | x + ∗ is injective and surjective onto V : = Im ⁡ ( π | x + H ∗ ). This means there is an affine linear map ψ : V → 𝔽 5 n ^ such that ( h , ψ ( h ) ) ∈ Γ ″ for all h ∈ S ″. □
Then do steps 3 and 4. □
nothing: True

html: Theorem 4.14 (U 3 inverse theorem). Assuming that:
- f : 𝔽 5 n → ℂ
- ∥ f ∥ L ∞ ( 𝔽 5 n ) ≤ 1
- ∥ f ∥ U 3 ( G ) ≥ δ for some δ > 0
Then there exists a symmetric n × n matrix M with entries in 𝔽 5 and b ∈ 𝔽 5 n such that
| 𝔼 x f ( x ) e ( ( x ⊤ ⁡ M x + b ⊤ ⁡ x ) ∕ p ) | ≥ c ( δ )
where c ( δ ) is a polynomial in δ. In other words, | ⟨ f , ϕ ⟩ | ≥ c ( δ ) for ϕ ( x ) = e ( ( x ⊤ ⁡ M x + b ⊤ ⁡ x ) ∕ p ) and we say “f correlates with a quadratic phase function”.
proof: Proof (sketch). Let Δ h f ( x ) denote f ( x ) f ( x + h ) ¯.
∥ f ∥ U 3 ( G ) = ( 𝔼 h ∥ Δ h f ∥ U 2 4 ) 1 8.
- STEP 1: Weak linearity. See reference.
- STEP 2: Strong linearity. We will spend the rest of the lecture discussing this in detail.
- STEP 3: Symmetry argument. Problem 8 on Sheet 3.
- STEP 4: Integration step. Problem 9 on Sheet 3.
STEP 1: If ∥ f ∥ U 3 ( G ) 8 = 𝔼 h ∥ Δ h ∥ U 2 4 ≥ δ 8, then for at least a δ 8 2-proportion of h ∈ 𝔽 5 n, δ 8 2 ≤ ∥ Δ h f ∥ U 2 4 ≤ ∥ Δ h f ^ ∥ l ∞ 2. So for each such h ∈ 𝔽 5 n, there exists t h such that | Δ h f ^ ( t h ) | 2 ≥ δ 8 2.
Proposition 4.15. Assuming that:
- f : 𝔽 5 n → ℂ
- ∥ f ∥ ∞ ≤ 1
- ∥ f ∥ U 3 ( G ) ≥ δ
- | 𝔽 5 n | = Ω δ ( 1 )
Then there exists S ⊆ 𝔽 5 n with | S | = Ω δ ( | 𝔽 5 n | ) and a function ϕ : S → 𝔽 5 n ^ such that
- (i) | Δ h f ^ ( ϕ ( h ) ) | = Ω δ ( 1 );
- (ii) There are at least Ω δ ( | 𝔽 5 n | 3 ) quadruples ( s 1 , s 2 , s 3 , s 4 ) ∈ S 4 such that s 1 + s 2 = s 3 + s 4 and ϕ ( s 1 ) + ϕ ( s 2 ) + ϕ ( s 4 ).
STEP 2: If S and ϕ are as above, then there is a linear function ψ : 𝔽 5 n → 𝔽 5 n ^ which coincides with ϕ for many elements of S.
Proposition 4.16. Assuming that:
- S and ϕ given as in Proposition 4.15
Then there exists n × n matrix M with entries in 𝔽 5 and b ∈ 𝔽 5 n such that ψ ( x ) = M x + b (ψ : 𝔽 5 n → 𝔽 5 n ^) satisfies ψ ( x ) = ϕ ( x ) for Ω δ ( | 𝔽 5 n | ) elements x ∈ S.
Proof. Consider the graph of ϕ, Γ = { ( h , ϕ ( h ) ) : h ∈ S } ⊆ 𝔽 5 n × 𝔽 5 n ^. By Proposition 4.15, Γ has Ω δ ( | 𝔽 5 n | 3 ) additive quadruples.
By Balog–Szemeredi–Gowers, Schoen, there exists Γ ′ ⊆ Γ with | Γ ′ | = Ω δ ( | Γ | ) = Ω δ ( | 𝔽 5 n | ) and | Γ ′ + Γ ′ | = O δ ( | Γ ′ | ). udefine S ′ ⊆ S by Γ ′ = { ( h , ϕ ( h ) ) : h ∈ S ′ } and note | S ′ | = Ω δ ( | 𝔽 5 n | ).
By Freiman-Ruzsa applied to Γ ′ ⊆ 𝔽 5 n × 𝔽 5 n ^, there exists a subspace H ≤ 𝔽 5 n × 𝔽 5 n ^ with | H | = O δ ( | Γ ′ | ) = O δ ( | 𝔽 5 n | ) such that Γ ′ ⊆ H.
Denote by π : 𝔽 5 n × 𝔽 5 n ^ → 𝔽 5 n the projection onto the first n coordinates. By construction, π ( H ) ⊇ S ′. Moreover, since | S ′ | = Ω δ ( | 𝔽 5 n | ),
| ker ⁡ ( π | H ) | = | H | | Im ⁡ ( π | H ) | = O δ ( | 𝔽 5 n | ) | S ′ | = O δ ( 1 ) .
We may thus partition H into O δ ( 1 ) cosets of some subspace H ∗ such that π | H is injective on each coset. By averaging, there exists a coset x + H ∗ such that
| Γ ′ ∩ ( x + H ∗ ) | = Ω δ ( | Γ ′ | ) = Ω δ ( | 𝔽 5 n | ) .
Set Γ ″ = Γ ′ ∩ ( x + H ∗ ), and define S ″ accordingly.
Now π | x + ∗ is injective and surjective onto V : = Im ⁡ ( π | x + H ∗ ). This means there is an affine linear map ψ : V → 𝔽 5 n ^ such that ( h , ψ ( h ) ) ∈ Γ ″ for all h ∈ S ″. □
Then do steps 3 and 4. □
nothing: True

html: Proposition 4.15. Assuming that:
- f : 𝔽 5 n → ℂ
- ∥ f ∥ ∞ ≤ 1
- ∥ f ∥ U 3 ( G ) ≥ δ
- | 𝔽 5 n | = Ω δ ( 1 )
Then there exists S ⊆ 𝔽 5 n with | S | = Ω δ ( | 𝔽 5 n | ) and a function ϕ : S → 𝔽 5 n ^ such that
- (i) | Δ h f ^ ( ϕ ( h ) ) | = Ω δ ( 1 );
- (ii) There are at least Ω δ ( | 𝔽 5 n | 3 ) quadruples ( s 1 , s 2 , s 3 , s 4 ) ∈ S 4 such that s 1 + s 2 = s 3 + s 4 and ϕ ( s 1 ) + ϕ ( s 2 ) + ϕ ( s 4 ).
proof: Proof. Consider the graph of ϕ, Γ = { ( h , ϕ ( h ) ) : h ∈ S } ⊆ 𝔽 5 n × 𝔽 5 n ^. By Proposition 4.15, Γ has Ω δ ( | 𝔽 5 n | 3 ) additive quadruples.
By Balog–Szemeredi–Gowers, Schoen, there exists Γ ′ ⊆ Γ with | Γ ′ | = Ω δ ( | Γ | ) = Ω δ ( | 𝔽 5 n | ) and | Γ ′ + Γ ′ | = O δ ( | Γ ′ | ). udefine S ′ ⊆ S by Γ ′ = { ( h , ϕ ( h ) ) : h ∈ S ′ } and note | S ′ | = Ω δ ( | 𝔽 5 n | ).
By Freiman-Ruzsa applied to Γ ′ ⊆ 𝔽 5 n × 𝔽 5 n ^, there exists a subspace H ≤ 𝔽 5 n × 𝔽 5 n ^ with | H | = O δ ( | Γ ′ | ) = O δ ( | 𝔽 5 n | ) such that Γ ′ ⊆ H.
Denote by π : 𝔽 5 n × 𝔽 5 n ^ → 𝔽 5 n the projection onto the first n coordinates. By construction, π ( H ) ⊇ S ′. Moreover, since | S ′ | = Ω δ ( | 𝔽 5 n | ),
| ker ⁡ ( π | H ) | = | H | | Im ⁡ ( π | H ) | = O δ ( | 𝔽 5 n | ) | S ′ | = O δ ( 1 ) .
We may thus partition H into O δ ( 1 ) cosets of some subspace H ∗ such that π | H is injective on each coset. By averaging, there exists a coset x + H ∗ such that
| Γ ′ ∩ ( x + H ∗ ) | = Ω δ ( | Γ ′ | ) = Ω δ ( | 𝔽 5 n | ) .
Set Γ ″ = Γ ′ ∩ ( x + H ∗ ), and define S ″ accordingly.
Now π | x + ∗ is injective and surjective onto V : = Im ⁡ ( π | x + H ∗ ). This means there is an affine linear map ψ : V → 𝔽 5 n ^ such that ( h , ψ ( h ) ) ∈ Γ ″ for all h ∈ S ″. □
cloze1: True

html: Proposition 4.16. Assuming that:
- S and ϕ given as in Proposition 4.15
Then there exists n × n matrix M with entries in 𝔽 5 and b ∈ 𝔽 5 n such that ψ ( x ) = M x + b (ψ : 𝔽 5 n → 𝔽 5 n ^) satisfies ψ ( x ) = ϕ ( x ) for Ω δ ( | 𝔽 5 n | ) elements x ∈ S.
proof: Proof. Consider the graph of ϕ, Γ = { ( h , ϕ ( h ) ) : h ∈ S } ⊆ 𝔽 5 n × 𝔽 5 n ^. By Proposition 4.15, Γ has Ω δ ( | 𝔽 5 n | 3 ) additive quadruples.
By Balog–Szemeredi–Gowers, Schoen, there exists Γ ′ ⊆ Γ with | Γ ′ | = Ω δ ( | Γ | ) = Ω δ ( | 𝔽 5 n | ) and | Γ ′ + Γ ′ | = O δ ( | Γ ′ | ). udefine S ′ ⊆ S by Γ ′ = { ( h , ϕ ( h ) ) : h ∈ S ′ } and note | S ′ | = Ω δ ( | 𝔽 5 n | ).
By Freiman-Ruzsa applied to Γ ′ ⊆ 𝔽 5 n × 𝔽 5 n ^, there exists a subspace H ≤ 𝔽 5 n × 𝔽 5 n ^ with | H | = O δ ( | Γ ′ | ) = O δ ( | 𝔽 5 n | ) such that Γ ′ ⊆ H.
Denote by π : 𝔽 5 n × 𝔽 5 n ^ → 𝔽 5 n the projection onto the first n coordinates. By construction, π ( H ) ⊇ S ′. Moreover, since | S ′ | = Ω δ ( | 𝔽 5 n | ),
| ker ⁡ ( π | H ) | = | H | | Im ⁡ ( π | H ) | = O δ ( | 𝔽 5 n | ) | S ′ | = O δ ( 1 ) .
We may thus partition H into O δ ( 1 ) cosets of some subspace H ∗ such that π | H is injective on each coset. By averaging, there exists a coset x + H ∗ such that
| Γ ′ ∩ ( x + H ∗ ) | = Ω δ ( | Γ ′ | ) = Ω δ ( | 𝔽 5 n | ) .
Set Γ ″ = Γ ′ ∩ ( x + H ∗ ), and define S ″ accordingly.
Now π | x + ∗ is injective and surjective onto V : = Im ⁡ ( π | x + H ∗ ). This means there is an affine linear map ψ : V → 𝔽 5 n ^ such that ( h , ψ ( h ) ) ∈ Γ ″ for all h ∈ S ″. □
cloze1: True