1. 有限域 Roth 定理

我们首先来查看有限域版本的 Roth 定理. 在应用于一般整数情况之前, 有限域版本是一个很好的尝试思路, 因为在有限域中许多令人头疼的技术问题都消失了.

令 $r_{3} (F_{3}^{n})$ 表示 $F_{3}^{n}$ 的 3-AP-free 子集大小的最大值. 注意, 给定 $F_{3}^{n}$ 中的 $x, y, z$ , 以下是等价的:

•	$x, y, z$ 构成长度为 3 的等差数列
•	$x - 2 y + z = 0$
•	$x + y + z = 0$
•	$x, y, z$ 构成一条直线
•	对于所有的 $i$ , $x, y, z$ 的第 $i$ 个坐标都不同或都相等.

我们将陈述并证明 Roth 定理的有限域版本. 有限域版本的证明与 Roth 定理的原理相同, 但稍微容易一些.

定理 1.1. $r_{3} (F_{3}^{n}) = O (\frac{3 ^{n}}{n})$

回顾三角形删除引理的证明, 我们可以直接得到 $r_{3} (F_{3}^{n}) = o (3^{n})$ , 但上述定理给出更好的上界. 不久之后我们就会证明定理 1.1.

我们先简要回顾一下这个问题的历史. 2004 年, Edel 发现 $r_{3} (F_{3}^{n}) \geq 2.2 1^{n}$ . 很久以来, 命题 $r_{3} (F_{3}^{n}) = (3 - o (1))^{n}$ 是否正确一直是开放的. 最近, 一个令人惊讶的突破表明 $r_{3} (F_{3}^{n}) \leq 2.7 6^{n}$ (2016, Ellenberg 和 Gijswijt) .

回顾 Szemerédi 正则性引理的证明过程, 我们有一个能量增量的论证. 有趣的是, Roth 定理的策略也是能量增量的一种变体. 我们将关注于密度增量, 给定 $A \subset F_{3}^{n}$ , 我们采取如下步骤:

1.	如果 $A$ 是伪随机的 (我们将看到它等价于 Fourier uniform, 粗略地说, 它的所有 Fourier 系数都很小) , 那么有一个计数引理将表明 $A$ 有很多的 3-AP.
2.	如果 $A$ 不是伪随机的, 那么我们将证明 $A$ 具有很大的 Fourier 系数. 然后我们可以找到一个维数为 1 的仿射子空间 (即超平面) , 该子空间 $A$ 的密度会增大. 现在我们将 $A$ 限制在这个超平面上, 并重复前面的步骤.
3.	每次我们重复时, 我们都会获得一个密度增量. 由于密度的上界为 1, 所以步数是有限的.

接下来, 我们回顾一些对我们的证明很重要的 Fourier 分析思想. 在 $F_{3}^{n}$ 中, 我们定义 $F_{3}^{n} \to C$ 的映射 $γ_{r} (x) = ω^{r \cdot x}$ , 下标 $r \in F_{3}^{n}$ , $ω = e^{2 πi /3}$ , $r \cdot x = r_{1} x_{1} + \dots + r_{n} x_{n}$ . 接下来我们定义 Fourier 变换. 对于 $f : F_{3}^{n} \to C$ , Fourier 变换由 $f : F_{3}^{n} \to C$ 给出, 其中 $f (r) = x \in F_{3}^{n} E f (x) ω^{- r \cdot x} = ⟨ f, γ_{r} ⟩$ Fourier 变换是 $f$ 和 $γ_{r}$ 的内积.

更一般的, 我们有

定义 1.2 ( $F_{p}^{n}$ 上的 Fourier 变换). $f : F_{p}^{n} \to C$ 的 Fourier 变换由 $f : F_{p}^{n} \to C$ 给出, 对于每个 $r \in F_{p}^{n}$ , $f (r) := E_{x \in F_{p}^{n}} f (x) ω^{- r \cdot x} = \frac{1}{p ^{n}} x \in F_{p}^{n} \sum f (x) ω^{- r \cdot x}$ 其中 $r \cdot x = r_{1} x_{1} + \dots + r_{n} x_{n}$ .

笔记 1.3. 为了方便我们作以下约定: 平均或求和的变量在 $F_{p}^{n}$ 上均匀变化.

我们注意到 Fourier 变换的一些关键性质如下.

命题 1.4.

•	$\hat{f} (0) = E f$
•	(Parseval) $E_{x \in F_{p}^{n}} f (x) \overline{g (x)} = \sum_{r \in F_{p}^{n}} f (r) \overline{g (r)}$
•	(反演) $f (x) = \sum_{r \in F_{p}^{n}} f (r) ω^{r \cdot x}$
•	(卷积) 定义 $(f * g) (x) = E_{y} f (y) g (x - y)$ , 我们有 $f * g (x) = f (x) g (x)$

下面我们证明这些性质. 第一条是显然的, 我们来证明第二到四条. 首先我们注意到 ${γ_{r} : r \in F_{p}^{n}}$ 构成一组正交基, 我们称其为 Fourier 基, 可以验证 $⟨ γ_{r}, γ_{s} ⟩ = x E [γ_{r} (x) \overline{γ_{s} (x)}] = x E [ω^{- (r - s) \cdot x}] = {1 if r = s 0 otherwise$ 我们可以将 Fourier 变换看作从 $F_{p}^{n}$ 到 Fourier 基构成的空间的酉变换, 立即得到 Fourier 反演和 Parseval 等式. 最后, 我们检查卷积公式的正确性, $x E [(f * g) ω^{r \cdot x}] = x, y E [f (y) g (x - y) ω^{- r (y + (x - y))}] = r E [f (x) ω^{- r \cdot x}] s E [g (x) ω^{- s \cdot x}]$

下面的引理将 Fourier 变换与 3-AP 联系在一起.

命题 1.5.

如果 $f, g, h : F_{3}^{n} \to C$ , 则 $x, y E [f (x) g (x + y) h (x + 2 y)] = r \sum f (r) g (- 2 r) h (r)$

我们将给出这个命题的两个证明, 其中第二个证明更具概念性.

版本 1.

我们用 Fourier 反演公式对等式左边处理.

L H S = x, y E (r_{1} \sum f (r_{1}) ω^{r_{1} \cdot x}) (r_{2} \sum g (r_{2}) ω^{r_{2} \cdot (x + y)}) (r_{3} \sum h (r_{3}) ω^{r_{3} \cdot (x + 2 y)}) = r_{1}, r_{2}, r_{3} \sum f (r_{1}) g (r_{2}) h (r_{3}) x E ω^{x \cdot (r_{1} + r_{2} + r_{3})} y E ω^{y \cdot (r_{2} + 2 r_{3})} = r \sum f (r) g (- 2 r) h (r)

最后的等号成立是因为

x E ω^{x \cdot (r_{1} + r_{2} + r_{3})} = {10 if r_{1} + r_{2} + r_{3} = 0 otherwise

和

y E ω^{y \cdot (r_{2} + 2 r_{3})} = {10 if r_{2} + 2 r_{3} = 0 otherwise

$□$

版本 2.

在这个证明中, 我们将等式左边视为卷积. 令 $g_{1} (y) = g (- y /2)$ , 所以 $g_{1} (r) = g (- 2 r)$ . $E_{x, y} f (x) g (x + y) h (x + 2 y) = E_{x, y, z : x - 2 y + z = 0} f (x) g (y) h (z) = E_{x, y, z : x + y + z = 0} f (x) g_{1} (y) h (z) = (f * g_{1} * h) (0) = r \sum f * g_{1} * h (r) = r \sum f (r) g_{1} (r) h (r) = r \sum f (r) g (- 2 r) h (r)$

$□$

需要注意的是, 在 $F_{3}$ 中 $- 2 = 1$ . 因此, 如果我们取 $f, g, h = 1_{A}$ , 其中 $A \subset F_{3}^{n}$ , 则 $3^{- 2 n} # {(x, y, z) \in A^{3} : x + y + z = 0} = r \sum 1_{A} (r)^{3}$

笔记 1.6. 如果 $A = - A$ , 那么得到的式子与计算 Cayley 图中长度为 3 的闭圈的公式相同.

引理 1.7 (计数引理).

如果 $A \subset F_{3}^{n}$ 且 $∣ A ∣ = α 3^{n}$ , 令 $Λ_{3} (A) = E_{x, y} [1_{A} (x) 1_{A} (x + y) 1_{A} (x + 2 y)]$ . 则 $∣ ∣ Λ_{3} (A) - α^{3} ∣ ∣ \leq α r \neq = 0 max ∣ ∣ 1_{A} (r) ∣ ∣$

证明. 根据命题 1.5

Λ_{3} (A) = r \sum 1_{A} (r)^{3} = α^{3} + r \neq = 0 \sum 1_{A} (r)^{3}

因此,

∣ ∣ Λ_{3} (A) - α^{3} ∣ ∣ = ∣ ∣ r \neq = 0 \sum 1_{A} (r)^{3} ∣ ∣ \leq r \neq = 0 \sum ∣ ∣ 1_{A} (r) ∣ ∣^{3} \leq r \neq = 0 max ∣ ∣ 1_{A} (r) ∣ ∣ \cdot r \sum ∣ ∣ 1_{A} (r) ∣ ∣^{2} = r \neq = 0 max ∣ ∣ 1_{A} (r) ∣ ∣ \cdot E 1_{A}^{2} = α r \neq = 0 max ∣ ∣ 1_{A} (r) ∣ ∣

$□$

d 下面我们开始证明定理 1.1.

设 $N = 3^{n}$ 为 $F_{3}^{n}$ 中的元素个数.

第 1 步, 如果集合是 3-AP-free 的, 则有一项大的 Fourier 系数.

引理 1.8. $A \subset F_{3}^{n}$ 且 $∣ A ∣ = α 3^{n}$ . 如果 $A$ 是 3-AP-free 的且 $N \geq 2 α^{- 2}$ , 则存在 $r \neq = 0$ 使得 $∣ ∣ 1_{A} (r) ∣ ∣ \geq α^{2} /2$ .

证明. 注意到 $Λ_{3} (A) = N^{- 2} # {(x, y, z) \in A^{3} : x + y + z = 0} = \frac{∣ A ∣}{N ^{2}} = \frac{α}{N}$ 其中第二个等号成立是因为 3-AP-free 中只有 $x = y = z$ 时满足 $x + y + z = 0$ . 根据计数引理, 我们有 $α r \neq = 0 max ∣ ∣ 1_{A} (r) ∣ ∣ \geq α^{3} - \frac{α}{N} \geq \frac{α ^{3}}{2}$

$□$

第 2 步. 大的 Fourier 系数意味着超平面上的密度增量.

引理 1.9. $A \subset F_{3}^{n}$ 且 $∣ A ∣ = α 3^{n}$ . 如果 $∣ ∣ 1_{A} (r) ∣ ∣ \geq δ$ 对于某 $r \neq = 0$ 成立, 则当 $A$ 限制在某个超平面上时, $A$ 的密度至少为 $α + \frac{δ}{2}$ .

证明. 我们有

1_{A} (r) = x \in F_{3}^{n} E 1_{A} (x) w^{- r \cdot x} = \frac{1}{3} (α_{0} + α_{1} w + α_{2} w^{2})

其中

α_{0}, α_{1}, α_{2}

是

A

在

r^{⊥}

的陪集上的密度. 我们想要证明

α_{0}, α_{1}, α_{2}

中有一个是显著大于

α

的. 注意到

α = \frac{α _{0} + α _{1} + α _{2}}{3}

. 由三角不等式,

3 δ \leq ∣ ∣ α_{0} + α_{1} w + α_{2} w^{2} ∣ ∣ = ∣ ∣ (α_{0} - α) + (α_{1} - α) w + (α_{2} - α) w^{2} ∣ ∣ \leq j = 0 \sum 2 ∣ α_{j} - α ∣ = j = 0 \sum 2 (∣ α_{j} - α ∣ + (α_{j} - α))

(最后一步的技巧也将在下一节中用到) 请注意, 最后一个求和中的每一项

∣ α_{j} - α ∣ + (α_{j} - α)

都是非负的. 因此, 存在

j

使得

δ \leq ∣ α_{j} - α ∣ + (α_{j} - α)

, 所以有

α_{j} \geq α + \frac{δ}{2}

.

$□$

第 3 步, 迭代密度增量.

到目前为止, 如果 $A$ 是 3-AP-free 的且 $N \geq 2 α^{- 2}$ , 那么在某个超平面上 $A$ 的密度至少为 $α + α^{2} /4$ . 我们令初始密度为 $α_{0} = α$ . 在第 $i$ 步, 我们将 $A$ 限制在某个超平面上, 使得子空间内 $A$ 的密度为 $α_{i} \geq α_{i - 1} + α_{i - 1}^{2} /4$ 令 $N_{i} = 3^{n - i}$ , 只要 $N_{i} \geq 2 α_{i}^{- 2}$ 我们就可以继续做第 $i$ 步. 因为 $α_{i}$ 最大为 1, 因此迭代过程一定在有限次数后终止. 我们关心的问题是, 多少次迭代后会终止? 显然 $\frac{4}{α ^{2}}$ 次后一定会终止, 但这个上界还不够好, 它仅能告诉我们 $∣ A ∣ = O (\frac{3 ^{n}}{n})$ . 下面我们将去找一个更好的上界.

考虑从 $α_{0}$ 开始到第一次翻倍的迭代次数 $i_{1}$ , $α_{i_{1}} > 2 α_{0}$ . 显然 $i_{1} \leq \frac{4}{α}$ . 接着我们考虑从 $α_{i_{1}}$ 到下一次翻倍的迭代次数 $i_{2}$ , $α_{i_{2}} > 2^{2} α_{0}$ , 整理得到 $i_{2} \leq \frac{2}{α}$ . 依次类推, 第 $k$ 次翻倍需要的迭代次数 $i_{k} \leq \frac{4}{α 2 ^{k - 1}}$ . 对于任意的 $k$ , 有 $\frac{4}{α} + \frac{2}{α} + \dots + \frac{4}{2 ^{k - 1} α} \leq \frac{8}{α}$ 所以在 $\frac{8}{α}$ 次迭代后一定终止. 假设该过程在 $m$ 步后终止, 密度为 $α_{m}$ . 那么最后一步中子空间的大小为 $3^{n - m} < 2 α_{m}^{- 2} \leq 2 α^{- 2}$ . 对不等式两边取对数有 $n \leq \frac{8}{α} + lo g_{3} (\frac{2}{α ^{2}}) = O (\frac{1}{α})$ 因此, $\frac{∣ A ∣}{N} = α = O (1/ n)$ . 等价的, $∣ A ∣ = α N = O (\frac{3 ^{n}}{n})$ , 这正是我们想要的.

笔记 1.10. 该证明在整数中会变得困难得多, 因为整数时子空间不能向下传递.

一个自然的问题是这种技术是否可以推广到 4-AP 的计数. 在基于正则性引理的 Roth 定理证明中, 我们看到图删除引理是不够的, 实际上我们还需要超图正则性和超图删除引理来实现 4-AP 计数. 类似地, 虽然这里介绍的计数引理表明 Fourier 系数控制着 3-AP 的计数, 但它们并不控制着 4-AP 的计数. 例如, 考虑集合 $A = {x \in F_{5}^{n} : x \cdot x = 0}$ , 可以证明 $A$ 对应的非零 Fourier 系数都是小的. 然而, 我们也可以证明 $A$ 的 4-AP 数量是错误的, 这意味着 Fourier 系数无法控制 4-AP 的数量. Gowers 为了扩展 Roth 定理的证明, 专门开发了高阶 Fourier 分析 (二次 Fourier 分析) , 他证明了 Szemeredi 定理适用于更大的 AP. 下面的定理给出了一个二次 Fourier 分析的例子.

定理 1.11 (Inverse theorem for quadratic Fourier analysis). 对于任意的 $δ > 0$ , 存在一个常数 $c (δ) > 0$ 使得如果 $A \subset F_{5}^{n}$ 具有密度 $α$ 并且 $∣ ∣ Λ_{4} (A) - α^{4} ∣ ∣ > δ$ , 则存在 $F_{5}$ 上的二次非零多项式 $f (x_{1}, \dots, x_{n})$ 满足 $∣ ∣ E_{x \in F_{5}^{n}} 1_{A} (x) ω^{f (x)} ∣ ∣ \geq c (δ)$

名字空间

视图

1. 有限域 Roth 定理