3. 有限域 Roth 定理的多项式方法的证明

目前, $F_{3}^{n}$ 中 Roth 定理最好的上界如下:

定理 3.1 (Ellenberg 与 Gijswijt (2017)). $r_{3} (F_{3}^{n}) = O (2.7 6^{n})$

这个上界改进了之前由 Bateman 和 Katz 于 2012 年给出的上界 $O (3^{n} / n^{1 + ϵ})$ ( $ϵ > 0$ ) . Bateman 和 Katz 使用 Fourier 分析的方法来证明他们的上界, 并且直到 17 年 Ellenberg 和 Gijswijt 给出新的上界以来, 上界是否可以改进至 $O (c^{n})$ ( $c < 3$ ) 一直是开放的. 新给出的上界更接近 Edel 于 2004 年给出的下界 $2.2 1^{n}$ .

Croot-Lev-Pach (2017 ) 给出了在 $(Z /4 Z)^{n}$ 上与 3-AP 上界类似的上界, 他们证明了 $(Z /4 Z)^{n}$ 4-AP-free 的集合的大小最大为 $O (3.6 1^{n})$ . 他们使用了多项式方法的一种变体, 并且由于元素阶为 2, 这使他们的证明变得更容易. 正如文献中经常提到的那样, Ellenberg 和 Gijswijt 使用 Croot-Lev-Pach 方法证明了 $F_{3}^{n}$ 上新的上界.

令 $A \subseteq F_{3}^{n}$ 是 3-AP-free 集 (在文献中有时也被称为上限集 cap set) . 我们有等式 $δ_{0} (x + y + z) = a \in A \sum δ_{a} (x) δ_{a} (y) δ_{a} (z)$ (3.1) $x, y, z \in A$ , 其中 $δ_{a}$ 是 Dirac delta 函数, 定义为: $δ_{a} (x) := {10 if x = a if x \neq = a$ 因为 $F_{3}^{n}$ 中 $x + y + z = 0$ 当且仅当 $z - y = y - x$ , 这意味着只有 $x = y = z = a$ 时 $x, y, z$ 才构成等差数列, $a \in F_{3}^{n}$ . 所以 (3.1) 成立.

我们将证明 (3.1) 的左侧是 “低秩” 的, 右侧是我们在下面意义下的 “高秩” 的.

回想一下线性代数中矩阵秩的概念: 给定一个函数 $F : A \times A \to F$ , 对于域 $F$ , 如果我们有 $F (x, y) = f (x) g (y)$ , 函数 $f, g : A \to F$ , 我们称 $F$ 的秩为 1, 简称秩 1. 我们定义 rank $F$ 是将 $F$ 写为秩 1 函数的线性组合所需的秩 1 函数数量的最小值.

我们应该如何定义函数 $F$ : $A \times A \times A \to F$ 的秩? 函数 $A \times A \to F$ 对应于矩阵, 函数 $A \times A \times A \to F$ 对应于 3 阶张量. 类似的, 我们有张量秩的概念, 其中秩 1 函数形如 $F (x, y, z) = f (x) g (y) h (z)$ . 张量秩是一个很重要的概念, 有很多的性质, 但我们不会用到它. 我们需要的是切片秩 (slice-rank) 的概念. 具体的,

定义 3.2 (Slice rank). 函数 $F : A \times A \times A \to F$ 的切片秩为 1 如果它可以写做如下形式之一 $f (x) g (y, z), f (y) g (x, z), or f (z) g (x, y),$ 其中, $f : A \to F$ 和 $g : A \times A \to F$ 是非零函数. 函数 $F : A \times A \times A \to F$ 的切片秩是将 $F$ 可以写成秩 1 函数的线性组合所需的秩 1 函数数量的最小值.

对角函数的切片秩是多少? 回忆线性代数的知识, 对角矩阵的秩是非零项的数量. 该结论同样适用于切片秩.

引理 3.3. 如果 $F : A \times A \times A \to F$ 定义为 $F (x, y, z) = a \in A \sum c_{a} δ_{a} (x) δ_{a} (y) δ_{a} (z)$ 则 $slice-rank F = ∣ {a \in A : c_{a} \neq = 0} ∣$ 这里的系数 $c_{a}$ 对应于对角线元素.

证明. 很明显, slice-rank $F \leq ∣ {a \in A : c_{a} \neq = 0} ∣$ . 这是因为我们可以将 $F$ 秩 1 函数的线性组合 $F (x, y, z) = c _{a} \neq = 0 a \in A \sum c_{a} δ_{a} (x) (δ_{a} (y) δ_{a} (z))$ 对于另一个方向, 我们假设所有对角线元素都不为零; 如果对于某些 $a$ , $c_{a} = 0$ , 那么我们可以在不增加切片秩的情况下从 $A$ 中删除 $a$ . 采用反证法, 假设 slice-rank $F < ∣ A ∣$ . 我们有 $F (x, y, z) = f_{1} (x) g_{1} (y, z) + \dots + f_{ℓ} (x) g_{ℓ} (y, z) + f_{ℓ + 1} (y) g_{ℓ + 1} (x, z) + \dots + f_{m} (y) g_{m} (x, z) + f_{m + 1} (z) g_{m + 1} (x, y) + \dots + f_{∣ A ∣ - 1} (z) g_{∣ A ∣ - 1} (x, y)$

命题 3.4. 存在 $h : A \to F_{3}$ , $∣ supp h ∣ > m$ 使得 $z \in A \sum h (z) f_{i} (z) = 0$ (3.2)对于所有的 $i = m + 1, \dots, ∣ A ∣ - 1$ 成立. 这里 supp $h$ 是集合 ${z \in A : h (z) \neq = 0}$ .

证明.

显然, 满足条件的 $h$ 一定是一个维数大于 $m$ 的子空间. 我们声称: 任何 $m + 1$ 维子空间的支撑集的大小至少为 $m + 1$ (这里的支撑集定义与命题中保持一致) . 理由如下:

对于任意 $m + 1$ 维子空间 $X$ , 我们将其 $m + 1$ 个线性无关的向量按列摆放构成一个 $∣ A ∣ \times (m + 1)$ 的矩阵, 不妨记为 $Y$ . $Y$ 的秩为 $m + 1$ . 我们可以在 $Y$ 中删去一些行得到一个 $(m + 1) \times (m + 1)$ 且行列式非零的矩阵. 新得到的矩阵的列向量我们记作 $v_{1}, v_{2}, \dots, v_{m + 1} \in F_{3}^{m + 1}$ . 因为行列式非零, 所以 $v_{1}, v_{2}, \dots, v_{m + 1}$ 是 $F_{3}^{m + 1}$ 的一组基. 因此一定存在 $v_{1}, v_{2}, \dots, v_{m + 1}$ 的线性组合是全 1 向量, 全 1 向量的支撑集大小为 $m + 1$ . 所以未删除行之前的列向量 (即 $Y$ 的列向量) 也能给出一个支撑集大小至少为 $m + 1$ 的线性组合.

$□$

选择上述命题中的

h

, 考虑

z \in A \sum F (x, y, z) h (z) = a \in A \sum z \in A \sum c_{a} δ_{a} (x) δ_{a} (y) δ_{a} (z) h (z) = a \in A \sum c_{a} h (a) δ_{a} (x) δ_{a} (y)

还注意到

z \in A \sum F (x, y, z) h (z) = f_{1} (x) g_{1} (y) + \dots + f_{ℓ} (x) g_{ℓ} (y) + f_{ℓ + 1} (y) g_{ℓ + 1} (x) + \dots + f_{m} (y) g_{m} (x)

其中

g_{i} (y) = \sum_{z \in A} g_{i} (y, z) h (z)

,

1 \leq i \leq ℓ

.

g_{i} (x) = \sum_{z \in A} g_{i} (x, z) h (z)

,

ℓ + 1 \leq i \leq m

. 因此

a \in A \sum c_{a} h (a) δ_{a} (x) δ_{a} (y) = f_{1} (x) g_{1} (y) + \dots + f_{ℓ} (x) g_{ℓ} (y) + f_{ℓ + 1} (y) g_{ℓ + 1} (x) + \dots + f_{m} (y) g_{m} (x)

注意等号左边有超过

m

个对角线元素 (记作

a

,

h (a) \neq = 0

) , 但等号右边切片秩最多为

m

, 矛盾.

$□$

使用归纳法, 我们可以轻松地将 3 个变量的情形推广到任何有限数量的变量, 我们省略其证明.

我们已经证明了 ( 3.1) 右边的切片秩为 $∣ A ∣$ , 因此是 “高秩”. 现在我们来证明左侧是 “低秩”.

引理 3.5. 定义 $F : A \times A \times A \to F_{3}$ 如下: $F (x + y + z) := δ_{0} (x + y + z)$ 则 slice-rank $F \leq 3 M$ , 其中 $M := a, b, c \geq 0 a + b + c = n b + 2 c \leq 2 n /3 \sum \frac{n !}{a ! b ! c !}$

证明. 在 $F_{3}$ 中, 有 $δ_{0} (x) = 1 - x^{2}$ . 因此 $δ_{0} (x + y + z) = i = 1 \prod n (1 - (x_{i} + y_{i} + z_{i})^{2})$ (3.3)其中 $x_{i}$ 是 $x \in F_{3}^{n}$ 的坐标, 依此类推. 如果我们展开右侧, 我们会得到一个变量数目为 $3 n$ 的多项式, 阶数为 $2 n$ . 每个单项式形如 $x_{1}^{i_{1}} \dots x_{n}^{i_{n}} y_{1}^{j_{1}} \dots y_{n}^{j_{n}} z_{1}^{k_{1}} \dots z_{n}^{k_{n}}$ 其中 $i_{1}, i_{2}, \dots, i_{n}, j_{1}, \dots, j_{n}, k_{1}, \dots, k_{n} \in {0, 1, 2}$ . 下面我们对这些单项式分组. 对于每一项, 根据鸽巢原理, $i_{1} + \dots + i_{n}, j_{1} + \dots + j_{n}, k_{1} + \dots + k_{n}$ 三项中至少有一项最多为 $2 n /3$ . 我们可以将 (3.3) 写为单项式的和. 具体的, 我们将其写为 $i = 1 \prod n (1 - (x_{i} + y_{i} + z_{i})^{2}) = i_{1}, i_{1}, \dots, i_{n} j_{1}, j_{2}, \dots, j_{n} k_{1}, k_{2}, \dots, k_{n} \sum c_{i_{1}, \dots, i_{n}, j_{1}, \dots, j_{n}, k_{1}, \dots, k_{n}} x_{1}^{i_{1}} \dots x_{n}^{i_{n}} y_{1}^{j_{1}} \dots y_{n}^{j_{n}} z_{1}^{k_{1}} \dots z_{n}^{k_{n}}$ (3.4)其中系数 $c_{i_{1}, \dots, i_{n}, j_{1}, \dots, j_{n}, k_{1}, \dots, k_{n}} \in F_{3}$ . 然后, 我们可以按以下方式进行分组以将 (3.4) 写为切片秩为 1 的函数的和: $i = 1 \prod n (1 - (x_{i} + y_{i} + z_{i})^{2}) = + i_{1} + \dots + i_{n} \leq \frac{2 n}{3} \sum x_{1}^{i_{1}} \dots x_{n}^{i_{n}} f_{i_{1}, \dots, i_{n}} (y, z) + j_{1} + \dots + j_{n} \leq \frac{2 n}{3} \sum y_{1}^{j_{1}} \dots y_{n}^{j_{n}} g_{j_{1}, \dots, j_{n}} (x, z) k_{1} + \dots + k_{n} \leq \frac{2 n}{3} \sum z_{1}^{k_{1}} \dots z_{n}^{k_{n}} h_{k_{1}, \dots, k_{n}} (x, y)$ 其中 $f_{i_{1}, \dots, i_{n}} (y, z) = k _{1} , k _{2} , \dots , k _{n} j _{1} , j _{2} , \dots , j _{n} \sum c_{i_{1}, \dots, i_{n}, j_{1}, \dots, j_{n}, k_{1}, \dots, k_{n}} y_{1}^{j_{1}} \dots y_{n}^{j_{n}} z_{1}^{k_{1}} \dots z_{n}^{k_{n}}$ $g_{j_{1}, \dots, j_{n}} (x, z)$ 和 $h_{k_{1}, \dots, k_{n}} (x, y)$ 是完全类似的.

因此, 每个阶数最多为 $2 n /3$ 的单项式对 slice-rank 有 3 次贡献, 并且此类单项式的数量最多为 $M$ . 因此 slice-rank 最多为 $3 M$ .

$□$

现在我们来估计 $M$ . 将 $(1 + x + x^{2})^{n}$ 展开我们得到 $(1 + x + x^{2})^{n} = a, b, c \geq 0 a + b + c = n \sum x^{b + 2 c} \frac{n !}{a ! b ! c !}$ 上述等式对任意 $x$ 均成立. 令 $x$ 的取值为 $0 \leq x \leq 1$ , 两边除以 $x^{2 n /3}$ , 我们有 $f (x) = (x^{- 2/3} + x^{1/3} + x^{4/3})^{n} > a, b, c \geq 0 a + b + c = d b + 2 c \leq 2 n /3 \sum \frac{n !}{a ! b ! c !} x^{b + 2 c - \frac{2}{3} n} > a, b, c \geq 0 a + b + c = d b + 2 c \leq 2 n /3 \sum \frac{n !}{a ! b ! c !}$ 第一个不等号是因为 $x > 0$ 且增加了约束条件 $b + 2 c \leq 2 n /3$ ; 第二个不等号是因为 $0 < x < 1$ . 为了得到最优上界, 我们最小化 $f (x) = x^{- 2/3} + x^{1/3} + x^{4/3}$ , $x \in (0, 1)$ . 求导得到 $f^{'} (x) =$ $(4 x^{2} + x - 2) /3 x^{5/3}$ . 令 $f^{'} (x) = 0$ 我们得到 $4 x^{2} + x - 2 = 0$ , 即 $x = - 1/8 \pm 33 /8$ . 又因为 $0 < x < 1$ , 所以极值点为 $x = (33 - 1) /8$ , 极值为 $f ((33 - 1) /8) \approx 2.755 < 2.76$ .

当这个证明出来时, 人们震惊了; 这基本上只有四页纸, 但展示了代数方法的巨大力量. 然而, 与我们上次使用的 Fourier 分析方法相比, 这些方法似乎更 “脆弱”. 扩展此技术得到 $F_{5}^{n}$ 的 4-AP-free 子集大小的上界仍是一个悬而未决的问题 (在上述参数中, 我们可以用任何其他有限域替换 $F_{3}$ , 所以域的选择并不重要) . 我们也可以将多项式方法扩展到 $F_{2}^{n} \times F_{2}^{n}$ 中的无角 (corner-free) 集.

名字空间

视图

3. 有限域 Roth 定理的多项式方法的证明