Tao–Vu · 加性组合学 · 第 7 章 Littlewood–Offord 问题

7.1　组合方法The combinatorial approach

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

本节目标我们手里有 \(n\) 个“步长” \(v_1,\dots,v_n\)（先当作实数）。每个 \(v_i\) 前面可以独立地放正号或负号，于是得到 \(2^n\) 个带符号和 \[\varepsilon_1 v_1+\varepsilon_2 v_2+\cdots+\varepsilon_n v_n,\qquad \varepsilon_i\in\{-1,+1\}.\] Littlewood–Offord 问题问的是：在所有这 \(2^n\) 个和里，最多能有多少个挤进一个长度固定的小区间（比如长度为 \(2\) 的开区间）？本节用纯组合的办法回答它，核心工具是“反链”（anti-chain）与 Sperner 定理。我们要把“一堆和挤在一起”这件事，翻译成“一堆子集互不包含”这件事，再用计数把上界卡死。

本章中我们介绍两种不同的方法。第一种是 Erdős 以及后来诸位作者的组合方法，它把问题改写为集合系（某个给定集合的子集的集族）的语言，从而可以调用极值集合系（extremal set systems）的理论。这种方法非常优美，并给出精确（sharp）的结果，但当人们对步长 \(v_j\) 施加更复杂的约束时，它就难以推广了。第二种、也是相当不同的方法，是 Halász 引入的傅里叶分析方法。用这种方法得到的界通常与最优结果相差一个绝对常数倍，但论证更为灵活。

一个贯穿全章的主题是：上述这些和的强集中（strong concentration）或大量重复，与步长 \(v_1,\dots,v_n\) 之间的强加性结构密切相关。在一个极端，若群 \(\mathbb Z\) 没有 \(2\)-挠（2-torsion），那么所有这些和两两不同，当且仅当 \(v_1,\dots,v_n\) 是非结合的（dissociated，见定义 4.32）。在另一个极端，若 \(v_1,\dots,v_n\) 落在一个秩与体积都很小的等差级数（arithmetic progression）之内，那么人们就预期这些和之间会有大量重复。于是情形与前几章研究过的和集估计（sum set estimates）以及逆和集定理（inverse sum set theorems）颇为相似——确实，我们对二者的处理也会有很强的相似之处（尤其是组合方法与傅里叶分析方法的平行使用）。

7.1.1　反链与 LYM 不等式

这种方法中的根本概念是反链（anti-chain）。

定义 7.1（反链）集族 \(\mathcal A\)（即一些集合组成的集合）称为反链，如果其中任何一个集合都不被另一个所包含；也就是说，对任意两个不同的 \(A,B\in\mathcal A\) 都有 \(A\not\subseteq B\)。

反链有时也被称作 Sperner 系（Sperner system），尤其是在较早的文献中。

例：什么是反链，什么不是取底集 \(X=\{1,2,3\}\)。把它的全部子集按“大小”分成 \(4\) 层：空集层、单点层、两点层、三点层。 直觉：反链就是“一条竖着的包含链都最多碰到它一次”的横向集族。下图把所有子集按层画成 Hasse 图，连线表示“下面被上面包含”。
{1,2,3} {1,2} {1,3} {2,3} {1} {2} {3} ∅ 反链
\(X=\{1,2,3\}\) 的全体子集（共 \(2^3=8\) 个）的包含关系。金色的中间一层 \(\{\{1,2\},\{1,3\},\{2,3\}\}\) 是一条反链；它恰好有 \(\binom{3}{1}=3\) 个元素（取最接近 \(|X|/2\) 的那一层）。
引理 7.2（LYM 不等式）设 \(\mathcal A\) 是有限集 \(X\) 的若干子集构成的一条反链。则 \[\sum_{A\in\mathcal A}\frac{1}{\binom{|X|}{|A|}}\le 1.\tag{7.1}\]

（LYM 取自 Lubell、Yamamoto、Meshalkin 三位独立得到此式者的姓氏首字母。）

证明. 我们给出 Bollobás 的概率证明，用的是 Katona 的随机映射法。设 \(\varphi:X\to[1,|X|]\) 是从 \(X\) 到 \(\{1,2,\dots,|X|\}\) 的一个随机双射，在全部 \(|X|!\) 个这样的双射中按均匀分布选取。一个简单的组合论证表明：对每个 \(A\in\mathcal A\) 有 \[\mathbb P\big(\varphi(A)=[1,|A|]\big)=\frac{1}{\binom{|X|}{|A|}}.\] 另一方面，由于没有哪个 \(A\) 被另一个所包含，事件 \(\big\{\varphi(A)=[1,|A|]\big\}\)（当 \(A\) 取遍 \(\mathcal A\) 时）两两互斥。因此它们概率之和不超过 \(1\)，这正给出所要的结论。♦
把证明拆开看：那个概率为什么是 \(1/\binom{|X|}{|A|}\)？事件 \(\varphi(A)=[1,|A|]\) 是说：随机排好的位置 \(1,2,\dots,|X|\) 中，最前面的 \(|A|\) 个位置恰好被 \(A\) 里的元素占满。一个均匀随机双射等价于把 \(X\) 的元素随机排成一行。所求即“\(A\) 的全体元素恰好排在最前 \(|A|\) 位”的概率。
  1. “哪些元素排在最前 \(|A|\) 位”这件事，等概率地落在 \(X\) 的任何一个 \(|A|\) 元子集上，共有 \(\binom{|X|}{|A|}\) 种可能。
  2. 其中“恰好是 \(A\)”只有 \(1\) 种。
  3. 所以概率 \(=\dfrac{1}{\binom{|X|}{|A|}}\)。（这里和具体怎么排前 \(|A|\) 位、后面怎么排都无关，所以无需更细致地数。）
随机把 X 排成一行（位置 1…|X|）： 123 4……|X| 前 |A| 位 = φ(A) = [1,|A|] 其余位置
事件 \(\varphi(A)=[1,|A|]\)：金色块（\(A\) 的元素）恰好占满最前 \(|A|\) 个位置。互不包含 \(\Rightarrow\) 不同的 \(A\) 不可能同时把“前若干位”占满，故这些事件互斥。

7.1.2　Sperner 定理与第一个 Littlewood–Offord 界

由显然的不等式 \(\binom{|X|}{|A|}\le\binom{|X|}{\lfloor |X|/2\rfloor}\)，我们立刻得到：

推论 7.3（Sperner 引理）设 \(\mathcal A\) 是有限集 \(X\) 的若干子集构成的反链。则 \[|\mathcal A|\le\binom{|X|}{\lfloor |X|/2\rfloor}.\]
从 LYM 到 Sperner，一步代数在 (7.1) 中，每一项的分母 \(\binom{|X|}{|A|}\) 都不超过最大的二项式系数 \(\binom{|X|}{\lfloor|X|/2\rfloor}\)（二项式系数在“正中间”取最大）。于是每一项 \(\ge\dfrac{1}{\binom{|X|}{\lfloor|X|/2\rfloor}}\)。把 \(|\mathcal A|\) 个这样的项加起来： \[1\ \ge\ \sum_{A\in\mathcal A}\frac{1}{\binom{|X|}{|A|}}\ \ge\ |\mathcal A|\cdot\frac{1}{\binom{|X|}{\lfloor|X|/2\rfloor}},\] 移项即得 \(|\mathcal A|\le\binom{|X|}{\lfloor|X|/2\rfloor}\)。

注意这个界显然是最优的：只要取 \(\mathcal A\) 为 \(X\) 的全部基数为 \(\lfloor |X|/2\rfloor\) 的子集所成的反链即可达到。

我们可以如下把 Sperner 引理应用于 Littlewood–Offord 问题。

推论 7.4设 \(v_1,\dots,v_n\) 为实数，且对所有 \(i\) 有 \(|v_i|\ge 1\)。设 \(I=\{x:x_0-1
证明. 必要时把某些 \(v_i\) 的符号反过来，我们可以假设对所有 \(i\) 有 \(v_i>1\)。现在令 \(\mathcal A\) 为 \([1,n]=\{1,\dots,n\}\) 的全体子集 \(A\) 组成的集族，其中 \(A\) 满足 \[\sum_{i\in A}v_i-\sum_{i\notin A}v_i\in I.\] 容易验证 \(\mathcal A\) 是一条反链，于是由 Sperner 引理 \(|\mathcal A|\le\binom{n}{\lfloor n/2\rfloor}\)。结论随之成立。♦
为什么可以“先把符号都翻成正”，又为什么 \(\mathcal A\) 是反链
  1. 符号归一化。把符号向量 \((\varepsilon_i)\) 对应到子集 \(A=\{i:\varepsilon_i=+1\}\)。则带符号和写成 \(\sum_{i\in A}v_i-\sum_{i\notin A}v_i\)。如果某个 \(v_i<-1\)，令 \(v_i'=-v_i>1\) 并同时翻转该坐标的正负规定，落入 \(I\) 的组数完全一一对应、个数不变。所以不妨设每个 \(v_i>1\)。
  2. 关键单调性。记 \(f(A)=\sum_{i\in A}v_i-\sum_{i\notin A}v_i\)。若往 \(A\) 里加入一个新元素 \(j\notin A\)，则 \(v_j\) 从“被减”变为“被加”，于是 \[f(A\cup\{j\})-f(A)=2v_j>2.\] 也就是说，集合一旦真包含另一个，它的 \(f\) 值就至少大 \(2\)。
  3. 互不包含。区间 \(I\) 的长度只有 \(2\)。若 \(A\subsetneq B\) 且二者都在 \(\mathcal A\) 中，则 \(f(B)-f(A)\ge 2\cdot|B\setminus A|\ge 2\)，两个值不可能同时落进同一个长度 \(2\) 的开区间。矛盾。所以 \(\mathcal A\) 里任何两个集合互不包含——这正是反链。
区间 I（长度 2） x₀−1 x₀+1 A⊂B ⇒ 差 ≥ 2
蓝点是落进区间 \(I\) 的带符号和。由于“真包含”会让 \(f\) 值至少跳 \(2\)，而 \(I\) 只有长度 \(2\)，两个有包含关系的子集不可能都落在 \(I\) 内——所以落进 \(I\) 的子集互不包含，构成反链，个数被 Sperner 卡住。

7.1.3　链与链分解：Sperner 定理的第二种证明

现在我们给出 Sperner 引理的另一种证明。为此需要用链（chain）的概念来与反链相对照。

定义 7.5（链）链是一列集合 \(A_1,\dots,A_m\)，满足对所有 \(1\le i长度。若对所有 \(1\le i连通的（connected）。有限集 \(X\) 中的一条连通链称为居中的（centered），如果 \(|A_1|+|A_m|=|X|\)，等价地，如果对所有 \(1\le i\le m\) 有 \[|A_i|=\frac{|X|-m-1}{2}+i.\] 注意，居中连通链的长度必须与 \(|X|\) 具有相反的奇偶性。
把定义 7.5 读懂
  • 链：一串越来越大的集合，像俄罗斯套娃，后一个包含前一个。
  • 连通：每往后一步，恰好多放进一个新元素（基数每次加 \(1\)），不许一次加两个。于是连通链的基数是连续整数 \(|A_1|,|A_1|+1,\dots,|A_1|+m-1\)。
  • 居中：这串连续的基数“以 \(|X|/2\) 为中心对称”。因为 \(|A_1|+|A_m|=|X|\)，最小的和最大的基数到 \(|X|/2\) 的距离相等。
  • 奇偶性：连续 \(m\) 个整数关于中心 \(|X|/2\) 对称，要求 \(m\) 与 \(|X|\) 奇偶相反（例如 \(|X|=3\) 时居中链长度只能是 \(2\) 或 \(4\)…，即偶数）。
引理 7.6（链分解引理）设 \(X\) 为有限集，记 \(2^X=\{A:A\subseteq X\}\) 为 \(X\) 的幂集。则 \(2^X\) 可被划分为若干条不相交、非空的居中连通链。
证明. 我们对 \(|X|\) 作归纳。\(|X|=0,1\) 的情形是平凡的。现设 \(|X|>1\)，且对所有更小的 \(X\) 命题已被证明。把 \(X=X'\cup\{x_0\}\)，其中 \(|X'|=|X|-1\)。由归纳假设，\(2^{X'}\) 可被划分为 \(X'\) 中若干条不相交、非空的居中连通链。对每一条这样的链 \(A_1,\dots,A_m\)，观察到两条链 \[A_1,\ \dots,\ A_m,\ A_m\cup\{x_0\}\] 以及 \[A_1\cup\{x_0\},\ \dots,\ A_{m-1}\cup\{x_0\}\] 都是 \(2^X\) 中的连通居中链，并且容易看出它们恰好划分了 \(2^X\)。注意第二类链可能为空，但当然可以毫无困难地把它从划分中略去。结论随之成立。♦
归纳一步在做什么：把每条旧链“裂成两条”设旧底集 \(X'\)，新底集 \(X=X'\cup\{x_0\}\)。\(2^X\) 里每个子集要么不含 \(x_0\)（就是 \(2^{X'}\) 的老子集），要么含 \(x_0\)（就是老子集再添上 \(x_0\)）。把一条老的居中连通链 \(A_1,\dots,A_m\) 处理成：
  1. 第一条新链：照抄整条老链，再在尾部接上 \(A_m\cup\{x_0\}\)。长度变成 \(m+1\)。它盖住了 \(A_1,\dots,A_m\)（不含 \(x_0\)）和 \(A_m\cup\{x_0\}\)（含 \(x_0\)）。
  2. 第二条新链：把老链前 \(m-1\) 个各添上 \(x_0\)：\(A_1\cup\{x_0\},\dots,A_{m-1}\cup\{x_0\}\)。长度 \(m-1\)。它盖住其余“含 \(x_0\)”的集合。
  3. 两条新链合起来，恰好把“老链的 \(m\) 个老集合”+“它们各添 \(x_0\) 得到的 \(m\) 个新集合”=\(2m\) 个 \(2^X\) 元素全部、且不重不漏地分掉。对所有老链都这样做，就分完了整个 \(2^X\)。
  4. 可以验证两条新链仍是居中连通链（基数仍连续、仍关于 \(|X|/2\) 对称）；若 \(m=1\)，第二条为空，丢掉即可。
{1,2,3} {1,2} {1,3} {2,3} {1} {2} {3} ∅ 3 条居中连通链：长度 4（蓝）+ 长度 2（绿）+ 长度 2（红），共 8 = 2³ 个子集
\(X=\{1,2,3\}\)（\(|X|\) 为奇数）的链分解：蓝链 \(\varnothing\subset\{1\}\subset\{1,2\}\subset\{1,2,3\}\)（长度 \(4\)，偶），绿链 \(\{2\}\subset\{2,3\}\)、红链 \(\{3\}\subset\{1,3\}\)（长度 \(2\)，偶）。链数 \(=3=\binom{3}{1}\)。每条链都恰好穿过最中间一层一次。

每条 \(X\) 中的居中连通链都必恰好包含一个基数为 \(\lfloor |X|/2\rfloor\) 的子集。因此引理 7.6 中链的总数恰好等于 \(\dbinom{|X|}{\lfloor |X|/2\rfloor}\)。更一般地，我们看出由该引理给出的、长度为 \(m\) 的居中连通链的数目，当 \(m\) 与 \(|X|\) 奇偶相反时恰为 \[\binom{|X|}{(|X|-m+1)/2}-\binom{|X|}{(|X|-m-1)/2},\] 若 \(m\) 与 \(|X|\) 奇偶相同则为 \(0\)。

由于一条反链与每条链至多相交于一个元素，我们就得到 Sperner 引理的一个新证明（亦可与 Menger 定理，即定理 6.31 相比较）。

第二种证明的一句话逻辑把整个幂集分成 \(\binom{|X|}{\lfloor|X|/2\rfloor}\) 条链（引理 7.6）。反链 \(\mathcal A\) 里任何两个元素互不包含，所以同一条链上最多坐着 \(\mathcal A\) 的一个成员。链一共就那么多条，于是 \(|\mathcal A|\le\) 链数 \(=\binom{|X|}{\lfloor|X|/2\rfloor}\)。这是“鸽巢”式的计数：把 \(\mathcal A\) 的成员塞进各条链，每条链最多装一个。

事实上，同样的论证给出如下推广。

命题 7.7设 \(\mathcal A_1,\dots,\mathcal A_k\) 是有限集 \(X\) 的子集构成的 \(k\) 条互不相交的反链。则 \[|\mathcal A_1|+\cdots+|\mathcal A_k|\le\sum_{i=-\lfloor k/2\rfloor}^{\lfloor (k-1)/2\rfloor}\binom{|X|}{\lfloor(|X|+i)/2\rfloor}.\]

我们把这个命题的证明留作练习（练习 7.1.3）。

命题 7.7 的直觉当只有一条反链（\(k=1\)）时，右端只剩 \(i=0\) 一项，就是 \(\binom{|X|}{\lfloor|X|/2\rfloor}\)，退回 Sperner。\(k\) 条互不相交反链合起来，等价于在每条链上最多取 \(\min(m,k)\) 个元素（\(m\) 为该链长度）。右端正是“取靠近中间的 \(k\) 层”所能容纳的元素总数——把 \(k\) 个最大的二项式系数加起来。

于是我们可以毫无困难地把推论 7.4 加以推广：

推论 7.8（Erdős 的 Littlewood–Offord 不等式）设 \(v_1,\dots,v_n\) 为实数，且对所有 \(i\) 有 \(|v_i|\ge 1\)。设 \(I=\{x:x_0-k
为什么区间变长 \(k\) 倍，就用 \(k\) 条反链仍记 \(f(A)=\sum_{i\in A}v_i-\sum_{i\notin A}v_i\)，真包含一步让 \(f\) 至少跳 \(2\)。现在区间长度是 \(2k\)，所以一条链上落进 \(I\) 的子集，其 \(f\) 值跨度 \(<2k\)，至多有 \(k\) 个。把落进 \(I\) 的全体子集按“在链分解里属于哪条链”分组，等于把它们写成 \(k\) 条反链之并，再套用命题 7.7。\(k=1\) 时退回推论 7.4。

7.1.4　推广到复数：乘积型 Sperner 定理

人们可以把实数 \(\mathbb R\) 换成更高维的空间，例如复数 \(\mathbb C\)。为此，我们需要 Sperner 引理的一个乘积形式，如下。

引理 7.9（乘积型 Sperner 引理）设 \(X\) 与 \(Y\) 为有限集，\(\mathcal A\) 为一些子集对 \((A,B)\)（其中 \(A\subseteq X,\ B\subseteq Y\)）组成的集族，并且 \(\mathcal A\) 是一条乘积反链，意思是：\(\mathcal A\) 中不存在两个不同的对 \((A,B),(A',B')\)，使得“\(A=A'\) 且 \(B\subsetneq B'\)”或“\(A\subsetneq A'\) 且 \(B=B'\)”。（换句话说，对每个固定的 \(B\)，使 \((A,B)\in\mathcal A\) 的那些 \(A\) 构成一条反链，反之亦然。）则 \[|\mathcal A|\le\binom{|X|+|Y|}{\lfloor(|X|+|Y|)/2\rfloor}.\]

我们把这个引理的证明留作练习（练习 7.1.4）。作为推论，我们得到推论 7.4 的复数版本。

A 在 X 中的层（|A|） B 在 Y 中的层（|B|） 固定 B，A 那一行 是反链 |A|+|B| 越靠近 (|X|+|Y|)/2，可放的越多
把每个对 \((A,B)\) 画在“\(A\) 的大小”ד\(B\) 的大小”网格上。乘积反链的约束是：横看每行、竖看每列都各自是普通反链。最终能放的对数被关于总大小 \(|A|+|B|\) 居中的那条对角带卡住，给出界 \(\binom{|X|+|Y|}{\lfloor(|X|+|Y|)/2\rfloor}\)。
推论 7.10设 \(v_1,\dots,v_n\) 为复数，且对所有 \(i\) 有 \(|v_i|\ge 1\)。设 \(B=\{z:|z-z_0|<1\}\) 是一个半径为 \(1\) 的球（圆盘）。则满足 \(\varepsilon_1 v_1+\cdots+\varepsilon_n v_n\in B\) 的 \(n\) 元组 \((\varepsilon_1,\dots,\varepsilon_n)\in\{-1,1\}^n\) 的总数至多为 \(\dbinom{n}{\lfloor n/2\rfloor}\)。
证明. 通过把复平面随机旋转一个角度，我们可以假设没有哪个 \(v_i\) 是纯实数或纯虚数。必要时反转某些 \(v_i\) 的符号，可以假设对所有 \(i\) 有 \(\operatorname{Im}v_i>0\)。令 \(X\) 为所有满足 \(\operatorname{Re}v_i>0\) 的 \(i\) 之集合，\(Y\) 为所有满足 \(\operatorname{Re}v_i<0\) 的 \(i\) 之集合；于是 \(X\cup Y=[1,n]\)。现在令 \(\mathcal A\) 为全体子集对 \((A,B)\)（其中 \(A\subseteq X,\ B\subseteq Y\)）组成的集族，使得 \[\sum_{i\in A\cup B}v_i-\sum_{i\notin A\cup B}v_i\in B.\] 容易验证 \(\mathcal A\) 是引理 7.9 意义下的乘积反链，结论随之成立。♦
把复数情形拆成两半看实数证明里我们用的是“加入一个元素让和增大 \(2v_j\)”这条单调性。复数没有大小顺序，但可以分坐标看：
  1. 先随机旋转，使每个 \(v_i\) 的实部、虚部都非零，再翻符号使虚部全正：\(\operatorname{Im}v_i>0\)。
  2. 把下标按实部正负分成 \(X\)（实部正）与 \(Y\)（实部负）两堆。
  3. 往 \(A\subseteq X\) 加一个元素，会把那一项 \(v_i\)（实部正、虚部正）从“被减”变“被加”，使实部明显增大；往 \(B\subseteq Y\) 加一个元素则使实部明显减小。无论哪一种，配合虚部全正的设置，都让带符号和移出半径 \(1\) 的圆盘。于是固定一边、另一边互不包含——正好是乘积反链。
  4. 套用引理 7.9，并注意 \(|X|+|Y|=n\)，即得界 \(\binom{n}{\lfloor n/2\rfloor}\)。

事实上，借助这一论证的更精巧的版本，在一般维数下也有类似的结论；见 [207]。

关于这类极值组合学结果，以上只是冰山一角；例如关于这些主题更详尽的处理，可见 [32]。这一方法的各种变体也已成功地应用于循环群（cyclic groups）；见 [163]。

练习

练习 7.1.1（集合对估计，set-pair estimate）设 \(A_1,\dots,A_m,B_1,\dots,B_m\) 是有限集，满足 \(A_i\cap B_j=\varnothing\) 当且仅当 \(i=j\)。证明 \[\sum_{i=1}^m\frac{1}{\binom{|A_i|+|B_i|}{|A_i|}}\le 1.\] 注意这把引理 7.3 包含为特例（取 \(B_i:=X\setminus A_i\)）。
练习 7.1.2（Erdős–Ko–Rado 定理）设 \(A_1,\dots,A_m\) 是 \(\mathbb Z_N\)（即 \(\{1,\dots,N\}\)）中的一条反链，使得任何两个 \(A_i,A_j\) 都相交（即对所有 \(i,j\) 有 \(A_i\cap A_j\ne\varnothing\)），并且对所有 \(i\) 及某个 \(k\le N/2\) 有 \(|A_i|\le k\)。证明 \(m\le\binom{N-1}{k-1}\)，并证明此界是精确的。（提示：先证明对任意双射 \(\varphi:\mathbb Z_N\to\mathbb Z_N\)，集合 \(\varphi(A_i)\) 中至多有 \(k\) 个能形如某个 \(a\in\mathbb Z_N\) 对应的区间 \([a+1,a+|A_i|]\)；这一优美的论证归功于 Katona [196]。）
练习 7.1.3证明命题 7.7。（提示：对任意长度为 \(m\) 的链，观察到该链中至多有 \(\min(m,k)\) 个元素能落在 \(\mathcal A_1\cup\cdots\cup\mathcal A_k\) 内。再数一数引理 7.6 中给定长度的链各有多少条。）
练习 7.1.4证明引理 7.9。（提示：若 \(A_1,\dots,A_m\) 是 \(X\) 中一条连通链、\(B_1,\dots,B_n\) 是 \(Y\) 中一条连通链，证明 \(\mathcal A\) 中形如 \((A_i,B_j)\) 的对至多有 \(\min(m,n)\) 个。或者，把 \(2^Y\) 分解为若干链 \(B_1,\dots,B_n\)，并对每条这样的链应用命题 7.7。）

返回 全书目录