Tao–Vu · 加性组合学 · 第 1 章 概率方法

1.8　高阶薄基Thin bases of higher order

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节目标 先把名词说清楚。一个正整数集合 \(B\subset\mathbb{Z}^+\) 称为\(k\) 阶基（basis of order \(k\)），意思是每个（足够大的）正整数 \(n\) 都能写成 \(B\) 中 \(k\) 个元素之和 \(n=x_1+\dots+x_k\)。记 \(r_{k,B}(n)\) 为 \(n\) 写成这种和的方法数（表示数）。
越“省料”的基越好：我们希望 \(B\) 很稀疏，使得每个 \(n\) 的表示方法不太多，即 \(r_{k,B}(n)\) 增长尽量慢。可以证明任何 \(k\) 阶基都满足 \(r_{k,B}(n)\) 至少是 \(\log n\) 量级，所以 \(r_{k,B}(n)=O(\log n)\) 已是最薄的可能——满足它的基就叫薄基（thin basis）。
本节要做的事：用上一节的多项式集中不等式（定理 1.37）证明定理 1.15——对每个 \(k\ge 1\) 都存在 \(k\) 阶薄基。\(k=2\) 的情形（定理 1.13）此前已用 Chernoff 不等式解决，但那条路在 \(k\ge 3\) 失效，因为 \(r_{k,B}(n)\) 无法简单写成独立随机变量之和。

我们现在回到 1.3 节开启的薄基 \(B\) 及其计数函数 \(r_{k,B}(n)\) 的研究。不过在本节，我们可以借助定理 1.37，给出定理 1.15 的一个证明——该定理断言：对每个 \(k\ge 1\)，都存在一个 \(k\) 阶基 \(B\)，使得对所有大的 \(n\) 有 \(r_{k,B}(n)=O_k(\log n)\)。在 \(k=2\) 的情形（见定理 1.13），这是用 Chernoff 不等式证明的，但该方法无法直接搬到更高的 \(k\)，因为 \(r_{k,B}(n)\) 不能轻易地表示成独立随机变量之和。

数轴上的某个大整数 n（这里 k=3, n=62） B={1,4,9,16,25,36,49,...}（完全平方数，一个稀疏集合） 表示 1：62 = 1 + 25 + 36 表示 2：62 = 4 + 9 + 49 ……（如还有其它拆法，一并计入） 这种和式的总条数 = rk,B(n)
把每个大整数 \(n\) 拆成 \(B\) 中 \(k\) 个数之和，至少要有一种拆法（这就是“\(k\) 阶基”）；拆法的条数就是 \(r_{k,B}(n)\)。薄基要求这个条数随 \(n\) 缓慢增长（\(\le C\log n\)）。
为什么 \(k\ge 3\) 时 Chernoff 失效 当 \(k=2\) 时，固定 \(n\)，把 \(n=x+(n-x)\) 的各种拆法看成一串互不重叠的“元件”：对每个 \(x独立项之和，Chernoff 直接适用。
而 \(k=3\) 时，\(n=x_1+x_2+x_3\) 的不同拆法会共用同一个 \(x_i\)（例如 \(30=1+4+25\) 与 \(30=1+13+16\) 都用到 \(1\)），各项不再独立，不能简单求和。正是这种“项与项纠缠在一起”的困难，迫使我们改用多项式集中不等式（定理 1.37），并先建立下面几条引理来控制“到底有多少条互不重叠的拆法”。

1.8.1　布尔多项式中“互不相交项”的控制

我们从一条关于布尔多项式的简单引理开始：它表明，若 \(E(X)\) 不太大，则在样本空间的大多数点 \((t_1,\dots,t_n)\) 处，多项式 \(X\) 不会包含太多互不相交的项（参见习题 1.3.12）。

引理 1.40 设 \(X=\sum_{A\in\mathcal{A}}\prod_{j\in A}t_j\) 是 \(n\) 个独立布尔变量 \(t_1,\dots,t_n\) 的布尔多项式；令随机集合 \(B\subseteq[1,n]\) 为 \(B:=\{j\in[1,n]:t_j=1\}\)；再令随机变量 \(D\in\mathbb{N}\) 定义为：包含在 \(B\) 中的、属于 \(\mathcal{A}\) 的那些集合里，能找到的两两不相交集合的最大个数。则对任意整数 \(K\ge 1\)，有 \[\tag{}P(D\ge K)\le\frac{E(X)^K}{K!}.\]
先把记号读懂
证明. 注意，对任意两两不相交的 \(A_1,\dots,A_K\)，有 \[\tag{}\mathbf{1}(D\ge K)\le\frac{1}{K!}\sum_{\substack{A_1,\dots,A_K\in\mathcal{A}\\ \text{两两不相交}}}\Big(\prod_{j\in A_1}t_j\Big)\cdots\Big(\prod_{j\in A_K}t_j\Big).\] 对两边取期望，先用期望的线性性 (1.3)、再用独立性，得到 \[P(D\ge K)\le\frac{1}{K!}\sum_{A_1,\dots,A_K\in\mathcal{A}}E\Big(\prod_{j\in A_1}t_j\Big)\cdots E\Big(\prod_{j\in A_K}t_j\Big).\] 而再次利用期望的线性性，右端恰好就是 \(E(X)^K/K!\)，命题得证。♦
  1. 左边的指示函数为什么成立。若 \(D\ge K\)，说明 \(B\) 里至少能找到 \(K\) 个两两不相交、且都在 \(\mathcal{A}\) 中的集合 \(A_1,\dots,A_K\)。对这一组，乘积 \(\big(\prod_{j\in A_1}t_j\big)\cdots\big(\prod_{j\in A_K}t_j\big)=1\)（因为每个 \(A_i\subseteq B\)）。这 \(K\) 个集合可以按 \(K!\) 种顺序排列都被这个对称求和数到，故除以 \(K!\)。于是右边的和 \(\ge 1=\mathbf{1}(D\ge K)\)。若 \(D
  2. 取期望、用独立性。由于 \(A_1,\dots,A_K\) 两两不相交，乘积 \(\prod_{j\in A_1}t_j,\dots,\prod_{j\in A_K}t_j\) 用到的是互不重叠的硬币，彼此独立，故“积的期望 = 期望的积”。
  3. 把求和拆开。放宽到所有（不必互不相交的）\(A_1,\dots,A_K\) 求和只会变大，而 \(\sum_{A_1,\dots,A_K}\prod_iE\big(\prod_{j\in A_i}t_j\big)=\Big(\sum_{A}E\big(\prod_{j\in A}t_j\big)\Big)^K=E(X)^K.\) 于是右端 \(=E(X)^K/K!\)。
随机集合 B = { j : t_j = 1 }（被选中的整数） A₁ A₂ A₃ 这三个 A 两两不相交且都落在 B 内 ⇒ 此处 D ≥ 3
\(D\) 数的是：完全落在 \(B\) 里、又彼此不共用元素的 \(\mathcal{A}\)-集合最多能有几个。引理 1.40 保证：只要平均值 \(E(X)\) 小，\(D\) 跑得很大的概率就被 \(E(X)^K/K!\) 死死压住。

1.8.2　向日葵引理

当这条引理与 Erdős 和 Rado 的向日葵引理（sunflower lemma，[95]）结合时，威力尤其大。称一组集合 \(A_1,\dots,A_l\) 构成一朵向日葵，如果所有两两交集 \(A_i\cap A_j\)（\(i\ne j\)）都相同（这些 \(A_i\) 称为这朵花的花瓣）。我们允许这个公共的两两交集为空集。

引理 1.41（向日葵引理） 若 \(\mathcal{A}\) 是一族集合，每个的大小至多为 \(k\)，且 \(|\mathcal{A}|>(l-1)^k\,k!\)，则 \(\mathcal{A}\) 中存在 \(l\) 个集合，它们构成一朵向日葵。

该引理可用初等组合方法证明，留作习题。它对计数函数 \(r_{k,B}(n)\) 有如下推论。

公共核心 Y 花瓣花瓣花瓣 花瓣花瓣花瓣
一朵向日葵：每片花瓣 \(A_i\) 都恰好与其它花瓣交在同一个核心上（\(A_i\cap A_j\) 对所有 \(i\ne j\) 都等于同一集合），核心之外的部分互不重叠。向日葵引理说：集合多到一定程度（\(>(l-1)^k k!\)），就一定逼出一朵有 \(l\) 片花瓣的向日葵。
推论 1.42 设 \(B\subset\mathbb{Z}^+\)，\(k\ge 2\)。对每个 \(n\in\mathbb{Z}^+\)，令 \(D_{k,n}\) 为：在 \(B\) 的元素构成、和为 \(n\) 的那些重集2 \(\{x_1,\dots,x_k\}\) 当中，能找到的两两不相交者的最大个数。则 \[r_{k,B}(n)\le k!\,k^k\,\max\!\Big(D_{k,n},\ \sup_{m

2 重集（multiset）是允许元素重复的集合。

证明. 固定 \(n\)。考虑这样得到的集合族 \(\mathcal{A}\)：取 \(B\) 中元素、和为 \(n\) 的重集 \(\{x_1,\dots,x_k\}\)，再去掉重复元素。显然 \(r_{k,B}(n)\le k^k|\mathcal{A}|\)。再观察：\(\mathcal{A}\) 中任何一朵向日葵的花瓣数至多为 \(D_{k,n}\)（当花瓣两两不相交时）或至多为 \(\sup_{m♦
  1. 从“重集表示”到“集合族”。每条表示 \(n=x_1+\dots+x_k\) 是一个重集；删去重复后得到一个普通集合 \(A\)（大小 \(\le k\)）。一个 \(A\) 最多对应 \(k^k\) 条原表示（把每个位置填成 \(A\) 中哪个元素），故 \(r_{k,B}(n)\le k^k|\mathcal{A}|\)。
  2. 向日葵花瓣数的两种上界。若一朵向日葵的花瓣两两不相交，则对应的重集也两两不相交，个数 \(\le D_{k,n}\)。若花瓣共享一个非空核心，挑核心里一个公共元素 \(c\)，从每片花瓣对应的重集里删掉一个 \(c\)，得到的是和为 \(n-c
  3. 套向日葵引理。记 \(M=\max\big(D_{k,n},\sup_{m
这条推论在说什么 计数函数 \(r_{k,B}(n)\) 被两样东西控制住：（一）互不相交的表示能有多少（\(D_{k,n}\)）；（二）低一阶的计数函数 \(r_{k-1,B}\) 有多大。前者用引理 1.40 + 概率压住，后者用对 \(k\) 归纳处理。这正是下面命题 1.43 的策略。

1.8.3　低阶计数函数几乎必然有界

利用上述方法，我们现在能给出通往定理 1.15 的一个初步结果。

命题 1.43 设 \(k\ge 2\)，并令 \(B\subset\mathbb{Z}^+\) 是 \(\mathbb{Z}^+\) 的一个随机子集：让每个 \(x\) 独立地以概率 \[P(x\in B)=\min\!\big(C\,x^{1/k-1}\log^{1/k}x,\ 1\big)\] 属于 \(B\)，其中 \(C>1\) 为某个正常数。则以概率 \(1\)，对所有 \(1\le k'
读懂记号
  • \(P(x\in B)=\min(Cx^{1/k-1}\log^{1/k}x,1)\)：每个整数 \(x\) 像抛一枚偏心硬币那样独立决定要不要进 \(B\)，越大的 \(x\) 入选概率越小（因为 \(1/k-1<0\)，\(x^{1/k-1}\) 随 \(x\) 递减）。这种概率挑出来的 \(B\) 平均而言恰好稀疏到能当 \(k\) 阶基。
  • \(O_{C,k,k',B}(1)\)：一个有界的量（上界只依赖于下标里的常数，与 \(n\) 无关）。
  • “以概率 \(1\)”：随机选出的 \(B\) 几乎总是满足该性质（例外情形的概率为 \(0\)）。
  • 结论的含义：所有比 \(k\) 低的阶 \(k'\)，其计数函数 \(\sup_n r_{k',B}(n)\) 都是有限常数——即用 \(B\) 中 \(k'
证明. 我们对 \(k'\) 归纳。\(k'=1\) 的情形是显然的。现设 \(1♦
  1. 归纳的骨架。要证“所有 \(k'
  2. 把 \(D_{k',n}\) 压住。引理 1.40 给出 \(P(D_{k',n}\ge K)\le E(\cdots)^K/K!\)。只要平均值 \(E(\cdots)\) 随 \(n\) 衰减，把 \(K\) 取大就能让这个概率小于 \(1/n^2\)。
  3. 为什么平均值会衰减。关键是那条不等式链最后给出 \(E(\cdots)=O(n^{k'/k-1}\log n)\)。指数 \(k'/k-1<0\)（因 \(k'
  4. Borel–Cantelli 收尾。各 \(n\) 的“坏事概率” \(\sum_n 1/n^2<\infty\)，故几乎必然只有有限多个 \(n\) 出坏事，即 \(D_{k',n}\) 终将一直 \(♦

1.8.4　定理 1.15 的证明

现在我们来证明定理 1.15。只需证明下述命题即可。

命题 1.44 设 \(k\ge 2\)，并令 \(B\subset\mathbb{Z}^+\) 是 \(\mathbb{Z}^+\) 的随机子集：让每个 \(x\) 独立地以概率 \[P(x\in B)=\min\!\big(C\,x^{1/k-1}\log^{1/k}x,\ 1\big)\] 属于 \(B\)，其中 \(C>1\) 为某正常数。若 \(C\) 取得依赖于 \(k\) 而足够大，则以概率 \(1\)，除有限多个 \(n\) 外都有 \(r_{k,B}(n)=\Theta_{C,k}(\log n)\)。特别地，\(B\) 以概率 \(1\) 是一个 \(k\) 阶薄基。
读懂记号 \(\Theta\) \(r_{k,B}(n)=\Theta_{C,k}(\log n)\) 表示 \(r_{k,B}(n)\) 被 \(\log n\) 上下双向夹住：存在只依赖 \(C,k\) 的常数 \(c_1,c_2>0\)，使 \(c_1\log n\le r_{k,B}(n)\le c_2\log n\)。上界保证“薄”（表示不多），下界保证“是基”（每个 \(n\) 至少有一种、其实约 \(\log n\) 种表示，绝不会无表示）。
证明. 我们将用两个相关的量来估计 \(r_{k,B}(n)\)： \[\tag{1.40}R(n):=\big|\{(x_1,\dots,x_k)\in B:x_1+\dots+x_k=n;\ n^{0.1}主项，\(E(n)\) 看作误差项；这反映了一个直观事实：对大多数表示 \(n=x_1+\dots+x_k\)，诸 \(x_i\) 互不相同、且量级都与 \(n\) 相当。因此，只需证明以概率 \(1\)，除有限多个 \(n\) 外都有 \[E(n)=O_{C,k,B}(1);\qquad R(n)=\Theta_{C,k,B}(\log n).\]
n = x₁+x₂+…+x_k 的所有表示 主项 R(n)： 各 xᵢ 互不相同且都 > n^0.1 误差 E(n)： 有重复或 有 xᵢ ≤ n^0.1
把 \(n\) 的全部表示分成两堆：主项 \(R(n)\)（“典型”表示，各项互异且都不太小）与误差项 \(E(n)\)（“退化”表示）。证明的策略是：误差项几乎必然有界（可忽略），主项则集中在 \(\Theta(\log n)\) 附近。

我们先处理误差项 \(E(n)\)。论证与命题 1.43 的证明相同。令 \(\mathcal{A}_n\) 为由满足 \(x_1+\dots+x_k=n\) 且“\(x_1=x_2\) 或 \(x_1\le n^{0.1}\)”的重集 \(\{x_1,\dots,x_k\}\) 产生的集合。仿照推论 1.42 的论证，有 \[E(n)\le k!\,k^k\,\max\!\Big(D_n,\ \sup_{m

误差项为什么衰减得更快 注意上面误差项里 \(E(\sum\cdots)\) 多出一个因子 \(n^{-0.9/k}\)：这是因为 \(E(n)\) 里强行要求某个变量很小（\(x_1\le n^{0.1}\)）或两个变量相等。被钉死一个小变量，相当于少了约 \(n^{0.9}\) 的“自由度”，于是平均值比主项小一个 \(n^{-0.9/k}\) 量级，衰减到 \(n^{-1/k-0.9/k}\log n\)。衰减越快，\(D_n\) 越难变大，最终 \(E(n)\) 几乎必然被一个常数封顶——退化表示只有有限多条，对总数无关紧要。

现在我们估计主项 \(R(n)\)。注意到可以把 \(R(n)\) 写成一个 \(k\) 次齐次布尔多项式 \(Y=Y(t_1,\dots,t_n)\)；更明确地， \[Y(t_1,\dots,t_n)=\sum_{A\in\mathcal{A}_n}\prod_{j\in A}t_j,\] 其中 \(\mathcal{A}_n\) 是所有满足 \(x_1+\dots+x_k=n\) 且 \(n^{0.1}\tfrac12 E(Y)\Big)=O_{C,k}\!\Big(\frac{1}{n^2}\Big)\] 对所有大的 \(n\) 成立。应用定理 1.37（并取 \(C\) 足够大），我们看到只需证明导数估计 \[E_1(Y),\dots,E_{k-1}(Y)\le n^{-\gamma}\] 对所有大的 \(n\) 与某个 \(\gamma>0\) 成立。换言之，我们需要建立 \[E\Big(\frac{\partial^{\alpha_1}}{\partial t_1}\cdots\frac{\partial^{\alpha_n}}{\partial t_n}\,Y(t_1,\dots,t_n)\Big)\le n^{-\gamma}\] ♦

（原文 PDF 摘录至此页结束。其后的内容验证上述偏导数估计：对每个 \(1\le j\le k-1\)、每个阶数之和为 \(j\) 的多重指标 \((\alpha_1,\dots,\alpha_n)\)，把 \(Y\) 对这些变量求偏导相当于固定 \(j\) 个被选中的元素、再数剩下 \(k-j\) 个元素的表示个数；同命题 1.43 的求和估计可得其期望 \(\le n^{-\gamma}\)。这便满足定理 1.37 的条件，给出 \(Y\) 在 \(E(Y)\) 附近的集中，从而 \(R(n)=\Theta(\log n)\)，命题 1.44 与定理 1.15 证毕。）

整节证明结构回顾
  1. 目标：构造一个 \(k\) 阶薄基，即随机集合 \(B\) 几乎必然满足 \(r_{k,B}(n)=\Theta(\log n)\)。
  2. 引理 1.40：用矩方法把“互不相交项个数 \(D\) 过大”的概率压成 \(E(X)^K/K!\)。
  3. 引理 1.41（向日葵）+ 推论 1.42：把计数函数 \(r_{k,B}(n)\) 控制在 \(D_{k,n}\) 与低一阶 \(r_{k-1,B}\) 之上。
  4. 命题 1.43：对 \(k\) 归纳，证明所有低阶 \(r_{k',B}\)（\(k'
  5. 命题 1.44：把 \(r_{k,B}(n)\) 拆成主项 \(R(n)\) 与误差项 \(E(n)\)；误差项几乎必然有界，主项写成布尔多项式 \(Y\)，用多项式集中不等式（定理 1.37）让它集中在 \(E(Y)=\Theta(C\log n)\) 附近。
  6. 结论：每个 \(k\) 都存在 \(k\) 阶薄基，定理 1.15 得证。

返回 全书目录