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

1.9　薄华林基Thin Waring bases

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 注记）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是全章的高潮，把前面发展的概率工具（尤其是 1.7 节的多项式集中不等式）用来回答一个非常具体的数论问题，建议先把下面的“本节目标”读懂。

本节目标 一个数论里的经典对象是“华林基”——所有 \(r\) 次方数 \(\{0^r,1^r,2^r,\dots\}\)。已知当 \(k\) 足够大时，每个自然数都能写成 \(k\) 个 \(r\) 次方数之和。本节要问：能不能从这一堆 \(r\) 次方数里挑出极少的一部分，使得“每个数仍能写成 \(k\) 个之和”，而且表示方法的数目被压到最小（约 \(O(\log n)\) 个）？这样的稀疏子集叫“薄基”。本节用概率方法证明：这样的薄子基确实存在。

从“存在薄基”到“经典基里藏着薄基”

回忆：\(k\) 阶薄基（thin basis of order \(k\)）是指一个集合 \(B\subset\mathbb N\)，使得对所有充分大的 \(n\) 都有 \(r_{k,B}(n)=O(\log n)\)。上面已经证明的定理 1.15 断言：\(\mathbb N\) 含有任意阶的薄基。鉴于像平方数、素数这样的经典基（classical bases）如此丰富，自然要提出如下问题：

符号回顾 \(r_{k,B}(n)\) 表示把 \(n\) 写成 \(B\) 中 \(k\) 个元素之和的表示个数（即满足 \(b_1+\dots+b_k=n\)、各 \(b_i\in B\) 的方式数）。称 \(B\) 是 \(k\) 阶基，意思是对所有充分大的 \(n\) 都有 \(r_{k,B}(n)\ge 1\)，也就是每个大数都能写成 \(k\) 个 \(B\)-元素之和。"薄"指在保证 \(r_{k,B}(n)\ge1\)（基的资格）的前提下，把表示数压到尽可能小，\(r_{k,B}(n)=O(\log n)\)。
问题 1.46 设 \(A\) 是任意固定的 \(k\) 阶基。\(A\) 是否含有一个薄子基（thin subbasis）\(B\)？

注意，西顿（Sidon）最初的问题可以看成本问题在 \(k=2\)、\(A=\mathbb N\) 时的特例。由 (1.21) 我们知道，一个薄基 \(B\) 享有如下的上下界：

\[|B\cap[0,N]|=\Omega_k\!\left(N^{1/k}\right);\qquad |B\cap[0,N]|=O_k\!\left(N^{1/k}\log^{1/k}N\right)\]

对一切充分大的 \(N\) 成立。于是我们可以考虑问题 1.46 的如下较弱版本：

问题 1.47 设 \(A\) 是任意固定的 \(k\) 阶基。\(A\) 是否含有一个子基 \(B\)，使得对一切充分大的 \(N\) 都有 \(|B\cap[0,N]|=O_k\!\left(N^{1/k}\log^{1/k}N\right)\)？
为什么 \(N^{1/k}\) 是绕不过去的下界 这一步是理解全节的钥匙。假设 \(B\) 是 \(k\) 阶基，看区间 \([0,N]\)。每个 \(n\le N\) 至少有一种 \(k\)-元素表示，而这些表示用到的元素都不超过 \(N\)，即都落在 \(B\cap[0,N]\) 里。设 \(M=|B\cap[0,N]|\)。
  1. 从 \(M\) 个元素里取 \(k\) 个（可重复）来求和，最多产生 \(\binom{M+k-1}{k}=O_k(M^k)\) 个不同的和。
  2. 这些和必须覆盖 \(0,1,\dots,N\) 共约 \(N\) 个目标值（基的资格要求），所以 \(O_k(M^k)\ge N\)。
  3. 反解得 \(M\ge \Omega_k(N^{1/k})\)。这就是下界 \(|B\cap[0,N]|=\Omega_k(N^{1/k})\) 的直觉来源——太稀疏就当不了基。
另一方向：若 \(r_{k,B}(n)=O(\log n)\)，把 \(n\) 从 \(0\) 加到 \(N\)，总表示数 \(\sum_{n\le N}r_{k,B}(n)=O(N\log N)\)；而这个总和又约等于 \(M^k\)（每组 \(k\)-元组贡献一个和）。于是 \(M^k=O(N\log N)\)，给出 \(M=O_k(N^{1/k}\log^{1/k}N)\)。这正是上界。所以薄基的密度被夹在 \(N^{1/k}\) 附近，只差一个 \(\log\) 因子。
全华林基 \(\mathbb N^{\wedge r}\)（很稠密） 薄子基 \(B\)（极稀疏） 每个数有非常多表示 每个数仍能表示，但只有 \(O(\log n)\) 种 挑选目标：去掉绝大多数点，仍保住"基"的资格
把稠密的华林基"瘦身"成薄子基：保留的点要少到接近 \(N^{1/k}\) 的密度极限，又不能少到漏掉某个大数。

华林基上的已知结果

问题 1.47 已经针对华林基 \(\mathbb N^{\wedge r}=\{0^r,1^r,2^r,\dots\}\) 被深入研究，尤其是在 \(r=2\) 的情形 [90, 56, 387, 388, 384, 331]。对这些基，已知：若 \(k\) 充分大（依赖于 \(r\)），则 \(\mathbb N^{\wedge r}\) 是 \(k\) 阶基，并且进一步有

\[\tag{1.42} r_{k,\mathbb N^{\wedge r}}(n)=\Theta_{k,r}\!\left(n^{\frac{k}{r}-1}\right);\]

注意这与 (1.21) 是相容的。

指数 \(\tfrac{k}{r}-1\) 是怎么来的 这是把 \(n\) 写成 \(x_1^r+\dots+x_k^r=n\) 的解数的几何估计，用"体积近似计数"即可看懂。
  1. 每个 \(x_j\) 的取值范围是 \(0\le x_j\le n^{1/r}\)（因为单个 \(x_j^r\le n\)）。
  2. 不加约束时 \((x_1,\dots,x_k)\) 是一个边长约 \(n^{1/r}\) 的 \(k\) 维方块里的格点，共约 \((n^{1/r})^k=n^{k/r}\) 个。
  3. 约束 \(x_1^r+\dots+x_k^r=n\) 是一个方程，把维数从 \(k\) 降到 \(k-1\)，相当于在解数上"除以"一个量级 \(n^{1/r}\cdot n^{-1/r}\cdots\)；精确算下来，落在这张曲面附近的格点约为 \(n^{k/r}\big/ n=n^{\frac{k}{r}-1}\)。
  4. 于是表示数 \(r_{k,\mathbb N^{\wedge r}}(n)=\Theta_{k,r}(n^{k/r-1})\)。当 \(k\) 增大，这个数随 \(n\) 增长得越来越快——表示极其富余，正好留出"删点瘦身"的空间。

Choi、Erdős 与 Nathanson 在 [56] 中证明：\(\mathbb N^{\wedge 2}\)（即平方数集）含有一个 \(4\) 阶子基 \(B\)，使得对一切 \(N>1\) 与一切 \(\varepsilon>0\) 都有 \(|B\cap[0,N]|=O_\varepsilon(N^{1/3+\varepsilon})\)。这被 Zöllner [387, 388] 推广：他证明对任意 \(k\ge 4\)，都存在一个 \(k\) 阶子基 \(B\subset\mathbb N^{\wedge 2}\)，使得对任意 \(\varepsilon>0\) 与 \(N>1\) 都有 \(|B\cap[0,N]|=O_{k,\varepsilon}(N^{1/k+\varepsilon})\)。这个界后来被进一步加强为 \(|B\cap[0,N]|=O_k(N^{1/k}\log^{1/k}N)\)；由 (1.21) 我们知道，除了那个对数因子之外，这个界是最优的。Spencer 在 [331] 中给出了 Wirsing 关于 \(k=4\) 情形结果的一个简短证明。

对 \(r\ge 3\)，已知的结果要少得多。1980 年，Nathanson [259] 证明 \(\mathbb N^{\wedge r}\) 含有某个阶的子基，其密度为 \(o(N^{1/r})\)。在同一篇论文里，他提出了问题 1.47 在 \(A=\mathbb N^{\wedge r}\) 时的一个特例。

在 [379] 中，Vu 对 \(A=\mathbb N^{\wedge r}\)（任意 \(r\ge 1\)）肯定地回答了问题 1.46（从而也回答了问题 1.47）：

定理 1.48 对任意固定的 \(r\)，存在一个整数 \(k_0\)，使得下述成立：对任意 \(k\ge k_0\)，所有 \(r\) 次方数构成的集合 \(\mathbb N^{\wedge r}\) 含有一个 \(k\) 阶薄基 \(B\)。特别地，由 (1.21) 我们有 \(|B\cap[0,n)|=O_k\!\left(N^{1/k}\log^{1/k}N\right)\) 对一切充分大的 \(N\) 成立。
注记 1.49 定理 1.37 中那个尖锐的集中（concentration）结果，最初正是为了证明定理 1.48 而发展出来的。
把定理 1.48 翻成大白话 取 \(r=2\)（平方数）。所有平方数 \(0,1,4,9,16,25,\dots\) 太多了。定理说：只要 \(k\) 足够大（比如 \(k\ge k_0\)），就能从平方数里抠掉绝大多数，只留下一个稀薄子集 \(B\)，使得
  1. 每个充分大的 \(n\) 仍能写成 \(B\) 里 \(k\) 个平方数之和（\(B\) 还是 \(k\) 阶基）；
  2. 这样的写法数目 \(r_{k,B}(n)=O(\log n)\)（薄）；
  3. 留下的元素在 \([0,N]\) 里只有约 \(N^{1/k}\log^{1/k}N\) 个——已逼近理论下限 \(N^{1/k}\)。
关键证明思想：随机地保留每个 \(r\) 次方数，保留概率随数的大小精心调节，然后证明这个随机集合以概率 1 同时满足以上三条。

核心命题：随机子集几乎必然是薄基

正如定理 1.15 是命题 1.44 的推论一样，定理 1.48 是下述命题的直接推论。

命题 1.50 设 \(k,r\ge 2\)，并设 \(B\) 是 \((\mathbb Z^+)^{\wedge r}\) 的一个随机子集，定义方式为：让各个 \(x^r\in B\) 相互独立地以概率 \[P(x^r\in B)=\min\!\left(C\,x^{\frac{r}{k}-1}\log^{1/k}x,\;1\right)\] 被选入，其中 \(C>1\) 为某个正常数。若 \(k\) 充分大（依赖于 \(r\)），且 \(C\) 充分大（依赖于 \(k,r\)），则以概率 1，对除有限多个 \(n\) 之外的所有 \(n\) 都有 \(r_{k,B}(n)=\Theta_{C,k,r,B}(\log n)\)。特别地，\(B\) 以概率 1 是 \(k\) 阶薄基。
为什么保留概率取成 \(C\,x^{r/k-1}\log^{1/k}x\) 这个概率不是随便定的——它被"反推"出来，使得每个 \(n\) 的期望表示数恰好是 \(\log n\) 量级。
  1. 要使 \(n\) 能表示，需要 \(x_1^r+\dots+x_k^r=n\) 这样的 \(k\)-元组中，至少有一组的 \(k\) 个元素全部被保留。
  2. 一组被全部保留的概率约为 \(\prod_{j=1}^k P(x_j^r\in B)\approx \prod_j C x_j^{r/k-1}\log^{1/k}x_j\)。
  3. 把这个乘积对所有 \(\Theta(n^{k/r-1})\) 个 \(k\)-元组求和，得到期望表示数 \(E(Y_n)\)。代入概率后量纲恰好抵消掉那个 \(n^{k/r-1}\)，只剩下 \(C^k\log n\) 量级（见下文 (1.43)）。
  4. 所以期望 \(\approx C^k\log n\)：取 \(C\) 大可保证 \(\ge1\)（基的资格），而 \(\log n\) 的增长正是"薄"所要求的上界。指数 \(\tfrac{r}{k}-1\) 是负的，意味着越大的数被保留的概率越小——大数本来表示就多，要删得更狠。
证明（概要）. 与命题 1.44 的证明一样，只需证明：以概率 1，对除有限多个 \(n\) 之外的所有 \(n\) 都有 \[E(n)=O_{C,k,r,B}(1);\qquad R(n)=\Theta_{C,k,r,B}(\log n),\] 其中 \(R(n)\) 与 \(E(n)\) 在 (1.40)、(1.41) 中已定义。\(E(n)\) 的贡献可用与上一节相似的论证处理，留作习题，故我们集中于 \(R(n)\)。 如前，我们可以把 \(R(n)\) 写成一个布尔多项式 \(Y_n=Y_n(t_1,\dots,t_m)\)，其中 \(m=\lfloor n^{1/r}\rfloor\)，\(t_x=\mathbb I(x^r\in B)\)，且 \[Y_n=\sum_{A\in\mathcal A_n}\ \prod_{x\in A}t_x,\] 这里 \(\mathcal A_n\) 是所有正整数集 \(\{x_1,\dots,x_k\}\) 的全体，满足 \(x_1^r+\dots+x_k^r=n\) 且 \(n^{0.1}期望。下面我们集中于 \(Y_n\) 的期望，特别要确立 \[E(Y_n)=\Theta_{k,r}\!\left(C^{k}\log n\right).\] 这是主估计，论证的其余部分照命题 1.44 进行。注意到 \[E(Y_n)=C^{k}\sum_{\substack{x_1<\dots♦
关于证明结构的说明 上面的概要把整个证明压缩成一句话："把表示数写成随机变量 \(Y_n\)，证明它的期望约为 \(\log n\)，再用集中不等式让随机实例几乎必然贴住期望。" 其中：
随机保留 \(x^r\) 概率 \(Cx^{r/k-1}\log^{1/k}x\) 表示数 \(R(n)=Y_n\) \(=\sum_A\prod_{x\in A}t_x\) 期望 \(E(Y_n)\) \(=\Theta(C^k\log n)\) 集中不等式 \(Y_n\) 贴住期望 几乎必然 \(r_{k,B}(n)=\Theta(\log n)\)
命题 1.50 的证明骨架：随机保留 → 表示数化为随机多项式 \(Y_n\) → 算期望约 \(\log n\) → 用集中不等式（1.7 节）锁住随机实例 → 几乎必然得到薄基。
为什么 (1.43) 是"略强于"(1.42) 的 标准界 (1.42) 给的是整个表示数 \(r_{k,\mathbb N^{\wedge r}}(n)=\Theta(n^{k/r-1})\)，即对所有 \(k\)-元组求和带权重 \(1\)。而 (1.43) 给的是带负幂权重 \(\prod x_j^{r/k-1}\) 的加权和等于 \(\Theta_{r,k}(1)\)。把这个加权和"去掉权重"就回到 (1.42) 的数量级，所以 (1.43) 蕴含 (1.42)；但 (1.43) 还额外控制了权重的分布（即表示中各 \(x_j\) 大小的均衡程度），因此信息更丰富——这正是构造薄基时需要的精细控制。
即时自测
  1. 取 \(r=2,k=4\)。把 \(\mathbb N^{\wedge 2}\) 中第 \(x\) 个平方数以概率 \(\min(Cx^{2/4-1}\log^{1/4}x,1)=\min(Cx^{-1/2}\log^{1/4}x,1)\) 保留。随着 \(x\) 增大，这个概率是增大还是减小？这与"大数表示太多、要删得更狠"是否一致？
  2. 说明：为什么薄基在 \([0,N]\) 中的元素个数不可能少于常数倍 \(N^{1/k}\)？（提示：用上文"\(M\) 个元素最多产生 \(O_k(M^k)\) 个和"。）
  3. 在命题 1.50 的期望式中，把每个 \(x_j\) 都近似看成 \(n^{1/r}\)，元组数近似看成 \(n^{k/r-1}\)，验证 \(C^k\cdot n^{k/r-1}\cdot (n^{1/r})^{k(r/k-1)}\cdot(\log n)\) 化简后确实约为 \(C^k\log n\)。

返回 全书目录