12. 加性能量和 Balog–Szémeredi–Gowers 定理

到目前为止, 我们已经使用倍增常数测量了对集合添加加性结构后的数量. 这里, 我们介绍了加性能量, 这是一种对集合中加性结构的新测量方式.

定义 12.1. 令 $A$ 和 $B$ 是一个 Abel 群的有限子集. 它们的加性能量定义为$$E(A,B)=\left|\left\{\left(a_1,a_2,b_1,b_2\right)\in A\times A\times B\times B:a_1+a_2=b_1+b_2\right\}\right|.$$单个子集 $A$ 的加性能量为 $E(A):=$$E(A,A)$.

我们可以将加性能量视为在适当的 Cayley 图中计算长度为 4 的圈. 下面我们将看到加性能量在加性组合学中起到的重要作用.

定义 12.2. 对于 Abel 群的两个有限子集 $A$ 和 $B$, 定义$$r_{A,B}(x):=|\{(a,b)\in A\times B:x=a+b\}|,$$即 $x$ 可以表示为 $A+B$ 总和形式的数量.

我们可以用 $r_{A,B}(x)$ 计算加性能量:$$E(A,B)=\sum _x{r}_{A,B}(x{)}^2.$$

对于加性能量, 我们有命题 1.0.3 的类似命题如下.

命题 12.3. 如果 $A$ 是 $\mathbb{Z}$ 的有限子集, 则 $|A{|}^2\le E(A)\le |A{|}^3$.

证明. 回顾 $E(A)$ 定义我们可以直接得到下界. 上界是因为对于任何三元组 $\left(a_1,a_2,a_3\right)\in A^3$, 第四个坐标是固定的, 为 $a_1+a_2-a_3$.

$\square$

笔记 12.4. 命题 12.3 是紧的. 当 $A$ 没有加性结构时, 下界成立; 而当 $A=[n]$ 时, 上界渐近成立.

到目前为止, 我们已经比较了小倍增集合和大加性能量集合. 事实上, 前者蕴含了后者.

命题 12.5. 如果 $|A+A|\le K|A|$ , 则 $E(A)\ge |A{|}^3/K$.

证明. 根据 Cauchy-Schwarz 不等式我们有$$\begin{array}{rl}E(A)& =\sum _{x\in A+A}{r}_{A,A}(x{)}^2\ge \frac{1}{|A+A|}{\left(\sum _{x\in A+A}{r}_{A,A}(x)\right)}^2\\ & =\frac{|A{|}^4}{|A+A|}\ge \frac{|A{|}^3}{|K|}.\end{array}$$

$\square$

很自然地, 我们想要知道命题 12.5 的逆命题是否成立. 事实上, 具有大加性能量的集合也可能有大倍增, 如下面的示例所述.

例 12.6. 考虑集合 $A=[N/2]\cup \left\{-2,-4,-8,\dots ,-2^{N/2}\right\}$ . 注意 $A$ 是一小倍增集和一没有加性结构的集合的并集. 第一个分量导致了大加性能量 $E(A)=\Theta \left(N^3\right)$, 而第二个分量导致了大倍增 $|A+A|=\Theta \left(N^2\right)$.

然而, Balog 和 Szemerédi 表明, 每个具有大加性能量的集合都必须有一个高度结构化的小倍增子集, 即使该集合总体上具有相对较少的加性结构 (1994) . 他们的证明后来被 Gowers 改进, Gowers 给出了常数的多项式界限 (1998) , 这就是我们将在这里展示的版本.

定理 12.7 (Balog-Szemerédi-Gowers 定理). 令 $A$ 是一个 Abel 群的有限子集. 如果 $E(A)\ge |A{|}^3/K$ , 则存在子集 $A^{\prime }\subset$ $A$ , 并且 $\left|A^{\prime }\right|\ge K^{-O(1)}|A|$ , $\left|A^{\prime }+A^{\prime }\right|\le K^{O(1)}\left|A^{\prime }\right|$.

我们提出了一个定理的更强大版本, 它考虑了两个不同集合之间的加法结构.

定理 12.8. 令 $A$ 和 $B$ 是同一个 Abel 群的有限子集. 如果 $|A|,|B|\le n$ 且 $E(A,B)\ge n^3/K$ , 则存在子集 $A^{\prime }\subset A$ 和 $B^{\prime }\subset B$ , 并且 $\left|A^{\prime }\right|,\left|B^{\prime }\right|\ge K^{-O(1)}n$ , $\left|A^{\prime }+B^{\prime }\right|\le K^{O(1)}n$.

证明定理 12.8 蕴含定理 12.7. 假设 $E(A)\ge |A{|}^3/K$, 应用定理 12.8 , 取 $B=A$ 得到 $A^{\prime },B^{\prime }\subset A$ , 并且 $\left|A^{\prime }\right|,\left|B^{\prime }\right|\ge$ $K^{-O(1)}n$ , $\left|A^{\prime }+B^{\prime }\right|\le K^{O(1)}n$. 然后根据推论 2.0.7, 我们有$$\left|A^{\prime }+A^{\prime }\right|\le \frac{{\left|A^{\prime }+B^{\prime }\right|}^2}{\left|B^{\prime }\right|}\le K^{O(1)}n$$

$\square$

为了证明定理 12.8, 我们再次考虑从加法组合到图论的转换. 定理 12.8 的证明依赖下面的图论中结构.

定义 12.9. 令 $A$ 和 $B$ 是一个 Abel 群的子集, 令 $G$ 是一个顶点二分图 $A\cup B$. 定义限制和集 (restricted sumset) $A{+}_{G}B$ 为 $G$ 中边的和集$$A{+}_{G}B:=\{a+b:(a,b)\text{ 是 }G\text{ 中的一条边}\}.$$

定理 12.10. 令 $A$ 和 $B$ 是 Abel 群的有限子集, 令 $G$ 是顶点二分图 $A\cup B$ . 如果: $|A|,|B|\le n$ , $G$ 中至少有 $n^2/K$ 边, 且 $\left|A{+}_{G}B\right|\le Kn$; 则存在子集 $A^{\prime }\subset A$ 和 $B^{\prime }\subset B$ , 满足 $\left|A^{\prime }\right|,\left|B^{\prime }\right|\ge K^{-O(1)}n$ , $\left|A^{\prime }+B^{\prime }\right|\le K^{O(1)}n$.

证明定理 12.10 蕴含定理 12.8. 令 $S=\left\{x\in A+B:r_{A,B}(x)\ge n/2K\right\}$ 为 “流行和” 的集合. 建立顶点集为 $A\cup B$ 的二分图 $G$, $(a,b)\in A\times B$ 是一条边当且仅当 $a+b\in S$.

我们声称 $G$ 有很多边, 下面我们通过证明 “非流行和” 最多占 $E(A,B)$ 的一半来说明这一点. 注意到$$\frac{n^3}{K}\le E(A,B)=\sum _{x\in S}{r}_{A,B}(x{)}^2+\sum _{x\notin S}{r}_{A,B}(x{)}^2$$因为 $r_{A,B}(x)<n/2K$ , 当 $x\notin S$ 时, 我们可以将第二项约束为$$\sum _{x\notin S}{r}_{A,B}(x{)}^2\le \frac{n}{2K}\sum _{x\notin S}{r}_{A,B}(x)\le \frac{n}{2K}|A||B|\le \frac{n^3}{2K^{\prime }}$$带回上一不等式得到$$\sum _{x\in S}{r}_{A,B}(x{)}^2\ge \frac{n^3}{2K}$$此外, 因为对于所有 $x$ 满足 $r_{A,B}(x)\le |A|\le n$ , 因此$$e(G)=\sum _{x\in S}{r}_{A,B}(x)\ge \sum _{x\in S}\frac{r_{A,B}(x{)}^2}{n}\ge \frac{n^2}{2K}$$因此, 我们可以应用定理 12.10 来找到具有所需性质的集合 $A^{\prime }\subset A$ 和 $B^{\prime }\subset B$.

$\square$

本节的其余部分将重点证明定理 12.10, 我们从几个引理开始.

引理 12.11 (路径长为 2). 固定 $\delta ,ϵ>0$. 令 $G$ 是一个二分图, 顶点集为 $A\cup B$ , 至少 $\delta |A||B|$ 边. 则存在 $U\subset A$ 且 $|U|\ge \delta |A|/2$, 使得至少 $(1-ϵ)$ 占比的点对 $(x,y)\in U^2$ , 该点对至少有 $ϵ{\delta }^2|B|/2$ 个共同邻点.

(...) 路径长度为 2 引理示意图

证明. 我们随机均匀地选择 $v\in B$, 令 $U=N(v)\subset A$, 我们有 $\mathbb{E}[|U|]\ge \delta |A|$. 注意到, 有较少共同邻点的点对不太可能包含在 $U$ 中. 确实如此, 如果 $x,y\in A$ 的公共邻点小于 $ϵ{\delta }^2|B|/2$, 则 $\mathrm{Pr}[\{x,y\}\subset U]<ϵ{\delta }^2/2$.

如果两点的共同邻点数至少为 $ϵ{\delta }^2|B|/2$ , 我们称两点是友好的. 令 $X$ 为非友好点对 $(x,y)\in U^2$ 的数量, 那么$$\mathbb{E}[X]=\sum _{\genfrac{}{}{0ex}{}{(x,y)\in A^2}{\text{ unfriendly }}}\mathrm{Pr}[\{x,y\}\subset U]<\frac{ϵ{\delta }^2}{2}|A{|}^2$$因此, 我们有$$\mathbb{E}\left[|U{|}^2-\frac{X}{ϵ}\right]\ge (\mathbb{E}[|U|]{)}^2-\frac{\mathbb{E}[X]}{ϵ}>\frac{{\delta }^2}{2}|A{|}^2$$所以存在 $U$ 满足 $|U{|}^2-X/ϵ\ge {\delta }^2|A{|}^2/2$. 对于这个 $U$ , 我们有 $|U{|}^2\ge {\delta }^2|A{|}^2/2$, 即 $|U|\ge \delta |A|/2$. 此外, 我们有 $X\le ϵ|U{|}^2$, 所以最多有 $ϵ$ 占比的点对 $(x,y)\in U^2$, 该点对的共同邻点数少于 $ϵ{\delta }^2|B|/2$ .

$\square$

引理 12.12 (路径长为 3). 存在 $c,C>0$ 使以下结论成立. 固定任意取值的 $ϵ,\delta >0$, 令 $G$ 是任意顶点集为 $A\cup B$ 且至少有 $\delta |A||B|$ 条边的二分图. 则存在子集 $A^{\prime }\subset A$ 和 $B^{\prime }\subset B$ , 使得任何 $(a,b)\in A^{\prime }\times B^{\prime }$ 的两点之间至少有 $\eta |A||B|$ 条长度为 3 的路径, 其中 $\eta =c{\delta }^C$.

(...) 路径长度为 3 引理示意图

证明. 如果 $A$ 中的点对具有至少 $\frac{{\delta }^3|B|}{20}$ 个共同邻点, 则将它们称为友好点对. 定义$$A_1:=\left\{a\in A:\mathrm{deg}a\ge \frac{\delta }{2}|B|\right\}$$将 $A$ 限制为 $A_1$ 使其可以在 $A_1$ 和 $B$ 之间保证至少 $\delta$ 的边密度, $G$ 中删除的边少于 $\delta |A||B|/2$ 条. 因为我们至少剩下 $\delta |A||B|/2$ 条边, $a\in A_1$ 的最大度数是 $|B|$, 我们有 $\left|A_1\right|\ge \delta |A|/2$.

通过 $\left(A_1,B\right)$ 上的路径为 2 引理 (引理 12.11) , 构造 $A_2\subset A_1$, 其中 $ϵ=\delta /10$. 然后, $\left|A_2\right|\ge \delta \left|A_1\right|/2\ge {\delta }^2|A|/4$ , $A_2$ 中最多 $ϵ$ 占比的顶点对是不友好的.

令$$B^{\prime }=\left\{b\in B:\mathrm{deg}\left(b,A_2\right)\ge \frac{\delta }{4}\left|A_2\right|\right\}$$将 $\left(A_2,B\right)$ 限制为 $\left(A_2,B^{\prime }\right)$, 最多删除 $\delta \left|A_2\right||B|/4$ 条边. 因为 $A_2$ 中的最小度数至少是 $\delta /2$, 所以至少有 $\delta \left|A_2\right||B|/2$ 条 $A_2$ 和 $B$ 之间的边. 因此, 至少有 $\delta \left|A_2\right||B|/4$ 条 $A_2$ 和 $B^{\prime }$ 之间的边, 并且因为 $b\in B^{\prime }$ 的最大度数是 $\left|A_2\right|$ , 我们有 $\left|B^{\prime }\right|\ge \delta |B|/4$. 定义$$A^{\prime }=\left\{a\in A_2:a\text{ is friendly to at least }\left(1-\frac{\delta }{5}\right)\text{-fraction of }{A}_2\right\}$$我们有 $\left|A^{\prime }\right|\ge \left|A_2\right|/2\ge {\delta }^2|A|/8$.

我们现在固定 $(a,b)\in A^{\prime }\times B^{\prime }$ 并控制它们之间的路径长度为 3 的数量. 因为 $b$ 至少与 $A_2$ 中 $\delta \left|A_2\right|/4$ 个顶点相邻, $a$ 至少 $(1-\delta /5)\left|A_2\right|$ 个 $A_2$ 中的顶点是友好的, 所以 $A_2$ 中至少有 $\delta \left|A_2\right|/20$ 个顶点, 该顶点与 $a$ 友好且与 $b$ 相邻. 对于每一个这样的 $a_1\in A_2$, 至少有 ${\delta }^3|B|/20$ 个点 $b_1\in B$, 使得 $a{b}_1{a}_{1}b$ 是长度为 3 的路径. 因此从 $a$ 到 $b$ 的长度为 3 的路径数量至少是$$\frac{\delta }{20}\left|A_2\right|\cdot \frac{{\delta }^3}{20}|B|\ge \frac{\delta }{20}\cdot \frac{{\delta }^2}{4}|A|\cdot \frac{{\delta }^3}{20}|B|=\frac{{\delta }^6}{20\cdot 4\cdot 80}|A||B|$$取 $\eta$ 等于上述系数, 我们注意到 $\left|A^{\prime }\right|\ge {\delta }^2|A|/8\ge$ $\eta |A|$ 和 $\left|B^{\prime }\right|\ge \delta |B|/4\ge \eta |B|$. 证毕.

$\square$

我们可以使用引理 12.12 来证明 Balog-Szemerédi-Gowers 定理的图论版本 (定理 12.10) . (...)Balog-Szemerédi-Gowers 定理证明示意图

证明. 注意到 $|A|,|B|\ge \frac{n}{K}$. 通过引理 12.12, 我们可以找到 $A^{\prime }\subset A$ 和 $B^{\prime }\subset B$ 且大小满足 $\left|A^{\prime }\right|,\left|B^{\prime }\right|\ge K^{-O(1)}n$, 使得对于每个 $(a,b)\in A^{\prime }\times B^{\prime }$, 至少有 $K^{-O(1)}{n}^2$ 条路径 $a{b}_1{a}_{1}b$ , $\left(a_1,b_1\right)\in A\times B$. 因此, 对于每个 $(a,b)\in A^{\prime }\times B^{\prime }$, 方程 $x-y+z=a+b$ 至少有 $K^{-O(1)}{n}^2$ 个解, 令解为 $x,y,z\in A+{}_{G}B$ , $(x,y,z)=\left(a+b_1,a_1+b_1,a_1+b\right)$ 是沿每条路径 $a{b}_1{a}_{1}b$ 得到的. $$K^{-O(1)}{n}^2\left|A^{\prime }+B^{\prime }\right|\le {\left|A{+}_{G}B\right|}^3=e(G{)}^3\le K^3{n}^3$$所以 $\left|A^{\prime }+B^{\prime }\right|\le K^{O(1)}n$.

$\square$