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

7.6　二次 Littlewood–Offord 问题The quadratic Littlewood–Offord problem

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是全章较难的一节，请耐心跟着每一步的动机走。

本节目标前几节研究的是线性随机量 \(\eta_1v_1+\dots+\eta_nv_n\) 取某个固定值的概率（“集中性”）。本节把问题升一级：把每个 \(\eta_i\) 改成两两相乘的二次式 \(\sum c_{ij}\eta_i\eta_j\)，问它还能不能避免“挤在一个点上”。核心技巧是去耦（decoupling）——把一个二次问题拆成两次线性问题来做。最终回报是一个漂亮的应用：随机对称 \(\pm1\) 矩阵几乎必不奇异（行列式几乎从不为 \(0\)）。

从线性到二次

前面几节研究的是诸如 \(\eta_1v_1+\dots+\eta_nv_n\) 这类随机变量的线性组合的集中性。研究更一般的多项式组合同样很有意思。为简单起见，我们只限于讨论如下的二次表达式

\[Q(\eta_1,\dots,\eta_n)=\sum_{1\le i其中 \(c_{i,j},d_i\) 取值于一个加法群 \(Z\)，而 \(\eta_1,\dots,\eta_n\) 是相互独立、均匀分布的随机 \(\pm1\) 符号。

读懂记号
  • \(\eta_i\) 是“扔硬币”：各以 \(1/2\) 的概率取 \(+1\) 或 \(-1\)，彼此独立。
  • 系数 \(c_{i,j}\)（二次项）与 \(d_i\)（线性项）住在某个加法群 \(Z\) 里。最常见的 \(Z\) 就是整数 \(\mathbb{Z}\)。
  • “集中性差”指的是：无论目标值 \(x\) 取多少，\(Q=x\) 的概率都不大——也就是 \(Q\) 的取值很分散，不会扎堆在某一点。

我们可以问：在什么条件下能对随机变量 \(Q\) 的集中性建立上界？在 \(c_{ij}\) 全为零的特殊情形，\(Q\) 退化为纯线性式 \(\sum d_i\eta_i\)，此时由推论 7.13 我们已经知道：只要 \(d_i\) 中有许多非零，\(Q\) 就不会集中在单独一点。于是我们自然希望对二次部分建立类似的结果，即：只要 \(c_{ij}\) 中有许多非零，\(Q\) 同样不会集中在单独一点。我们给出这种形式的一个样例结果如下。

先回忆线性版（推论 7.13）对线性式 \(\sum_i a_i\eta_i\)，若其中有 \(m\) 个系数 \(a_i\neq0\)，则对任意 \(x\)， \[P\Big(\sum_i a_i\eta_i=x\Big)=O\!\left(\frac{1}{\sqrt m}\right).\] 直觉：非零项越多，结果分布在越多可能值上越“摊平”，落到任何单点的概率就越小（衰减速度 \(1/\sqrt m\)）。本节会两次调用这条线性结果，去拼出二次结果。
把 \(Q\) 看成一张“带权图”：顶点是下标 1…n，边 {i,j} 的权重是 c_{i,j} 1 2 3 4 5 6 7
每个非零系数 \(c_{i,j}\) 是一条边。命题 7.33 的条件“至少 \(k\) 个 \(i\)，每个都有至少 \(l\) 个 \(j\) 使 \(c_{i,j}\neq0\)”就是说：至少有 \(k\) 个顶点，其度数（连出的边数）至少是 \(l\)。这张图“边足够多”时，\(Q\) 就分散。

主命题

命题 7.33 [64]设 \(Z\) 或者是无挠的（torsion-free），或者是奇数阶有限群。记号同上，并假设：至少有 \(k\) 个下标 \(i\)，对每个这样的 \(i\)，都有至少 \(l\) 个下标 \(j\) 使 \(c_{i,j}\neq0\)。则对任意 \(x\in Z\)， \[P(Q=x)=O\big(\min(k,l)^{-1/8}\big).\]
“无挠”“奇数阶”是干什么用的证明里会出现形如 \(2c_{i,j}\) 的量，我们需要保证 \(c_{i,j}\neq0 \Rightarrow 2c_{i,j}\neq0\)。在无挠群（如 \(\mathbb{Z}\)）里，非零元乘 \(2\) 仍非零；在奇数阶有限群里，\(2\) 与群阶互素，乘 \(2\) 是可逆映射，也不会把非零变成零。若群里有 \(2\)-挠（例如 \(\mathbb{Z}/2\mathbb{Z}\)，那里 \(1+1=0\)），结论可能失效，所以要排除。
证明. 不失一般性，设 \(k\le l\)（这样 \(\min(k,l)=k\)）。

第一步：挑出一个“好的下标子集” \(A\)。一个贪心算法的论证表明：可以找到一个子集 \(A\subset[1,n]\)，其大小 \(|A|=\lceil(k+1)/2\rceil\)，使得对每个 \(i\in A\)，都有至少 \(\lceil(l+1)/2\rceil\) 个 \(j\in[1,n]\setminus A\) 满足 \(c_{i,j}\neq0\)。

基本想法。把二次对象 \(Q\) 看成一个线性表达式 \(\sum_j X_j\eta_j\)，其中系数 \(X_j\) 本身又是 \(\eta_1,\dots,\eta_n\) 的线性表达式；这样一来，二次的非集中结果就可望由两次线性非集中结果得到。然而这里有一个“耦合”问题：\(X_j\) 与 \(\eta_j\) 并不独立地变化。这个困难可以借助下面的去耦不等式来化解：

\[\begin{aligned} P\big(E(X,Y)\big)&\le P\big(E(X,Y)\wedge E(\tilde X,Y)\big)^{1/2}\\ &\le P\big(E(X,Y)\wedge E(\tilde X,Y)\wedge E(X,\tilde Y)\wedge E(\tilde X,\tilde Y)\big)^{1/4} \end{aligned}\tag{7.13}\]

这里 \(X,Y,\tilde X,\tilde Y\) 是取有限多个值的相互独立的随机变量，其中 \(X\) 与 \(\tilde X\) 同分布、\(Y\) 与 \(\tilde Y\) 同分布，而 \(E(X,Y)\) 是任意一个只依赖于 \(X\) 与 \(Y\) 的事件。此不等式的证明来自两次 Cauchy–Schwarz 不等式，留作习题。

我们对 \(X:=(\eta_i)_{i\in A}\) 与 \(Y:=(\eta_j)_{j\in[1,n]\setminus A}\) 应用此不等式，把 \(Q\) 写成 \(Q(X,Y)\)，得到

\[P\big(Q(X,Y)=x\big)\le P\big(Q(X,Y)=Q(\tilde X,Y)=Q(X,\tilde Y)=Q(\tilde X,\tilde Y)=x\big)^{1/4},\]

其中 \(\tilde X,\tilde Y\) 分别是 \(X,Y\) 的独立同分布副本。特别地，由“四个量都等于同一个 \(x\)”可推出它们的交错和为零，于是

\[P\big(Q(X,Y)=x\big)\le P\big(Q(X,Y)-Q(\tilde X,Y)-Q(X,\tilde Y)+Q(\tilde X,\tilde Y)=0\big)^{1/4}.\]

另一方面，我们有如下的因式分解

\[Q(X,Y)-Q(\tilde X,Y)-Q(X,\tilde Y)+Q(\tilde X,\tilde Y) =\sum_{i\in A}\sum_{j\in B}c_{ij}\,(\eta_i-\tilde\eta_i)(\eta_j-\tilde\eta_j) =\sum_{i\in A}v_i\,\eta_i^{(1/2)},\]

其中 \(B:=[1,n]\setminus A\)，并且

\[v_i:=\sum_{j\in B}4c_{ij}\,\eta_j^{(1/2)},\qquad \eta_i^{(1/2)}:=\frac{\eta_i-\tilde\eta_i}{2}.\]

注意 \(\eta_i^{(1/2)}\) 全都相互独立，且服从分布 \(\eta^{(1/2)}\)（即：以概率 \(1/2\) 取 \(0\)，各以概率 \(1/4\) 取 \(\pm1\)）。还有一个关键的观察：\((v_i)_{i\in A}\) 与 \((\eta_i^{(1/2)})_{i\in A}\) 是相互独立的（因为前者只依赖 \(Y\)-类变量、后者只依赖 \(X\)-类变量）。

现在只需证明

\[P\Big(\sum_{i\in A}v_i\,\eta_i^{(1/2)}=0\Big)=O\!\left(\frac{1}{k^{1/2}}\right).\]

第二步：先证“大多数 \(v_i\) 非零”。对每个 \(i\in A\)，我们有容易的界

\[\mathbb{E}\,\mathbb{I}(v_i=0)=P(v_i=0)\le\frac34,\]

这只要把除了某一个使 \(c_{i,j}\neq0\) 的下标 \(j\) 之外的所有 \(\eta_j\) 都条件固定下来即可看出（剩下那一个 \(\eta_j^{(1/2)}\) 一动，\(v_i\) 至多在一处取到 \(0\)）。由推论 7.13 我们还有更强的界

\[\mathbb{E}\,\mathbb{I}(v_i=0)=P(v_i=0)\le O\!\left(\frac{1}{\sqrt l}\right).\]

由期望的线性性，于是

\[\mathbb{E}\Big(\sum_{i\in A}\mathbb{I}(v_i=0)\Big)\le|A|\cdot\min\!\left(\tfrac34,\,O\!\left(\tfrac{1}{\sqrt l}\right)\right).\]

特别地，由 Markov 不等式，

\[P\Big(\sum_{i\in A}\mathbb{I}(v_i=0)\ge\tfrac67|A|\Big)\le\min\!\left(\tfrac78,\,O\!\left(\tfrac{1}{\sqrt l}\right)\right);\]

由于 \(|A|=\Omega(k)\)，我们得出（记“至少 \(\Omega(k)\) 个 \(v_i\) 非零”这一事件为 \(E\)）

\[P\Big(\big|\{1\le i\le n/2:\ v_i\neq0\}\big|=\Omega(k)\Big)\ge\max\!\left(\tfrac17,\,1-O\!\left(\tfrac{1}{\sqrt l}\right)\right).\]

第三步：在 \(E\) 上再用一次线性结果。现在，若我们对上述事件（记为 \(E\)）取条件，则 \(\eta_i^{(1/2)}\) 的分布与独立性不受影响（因为 \(E\) 只关乎 \(v_i\)，而 \(v_i\) 与 \(\eta_i^{(1/2)}\) 独立）。于是可以再次应用推论 7.13，得到

\[P\Big(\sum_{i\in A}v_i\,\eta_i^{(1/2)}=0\,\Big|\,E\Big)=O\!\left(\frac{1}{\sqrt k}\right);\]

当然也有与前面相同的粗糙上界 \(\tfrac34\)。于是

\[P\Big(\sum_{i\in A}v_i\,\eta_i^{(1/2)}=0\,\Big|\,E\Big)\le\min\!\left(\tfrac34,\,O\!\left(\tfrac{1}{\sqrt k}\right)\right).\]

把这一估计与对 \(P(E)\) 的估计、以及 Bayes 公式结合起来，便得到所要的结论（即 \(P(\sum v_i\eta_i^{(1/2)}=0)=O(k^{-1/2})\)，从而 \(P(Q=x)\le O(k^{-1/2})^{1/4}=O(k^{-1/8})=O(\min(k,l)^{-1/8})\)）。♦

讲解：把这条证明拆成看得见的几步

为什么要去耦我们想把 \(Q\) 写成对 \(i\in A\) 的线性式 \(\sum_i X_i\eta_i\)，再用线性结果。但 \(X_i=\sum_j c_{ij}\eta_j+d_i\) 里也含有别的 \(\eta_{i'}\)（\(i'\in A\)），而这些 \(\eta_{i'}\) 同时又是别的项的“乘子”。系数与乘子纠缠在一起，不独立，线性结果用不了。去耦不等式 (7.13) 的作用，就是用四个独立副本 \(X,\tilde X,Y,\tilde Y\) 做交错差，把纠缠的部分整体消掉，只留下 \(A\)–\(B\) 之间的“纯交叉项”，从而造出一对真正独立的 \((v_i)\) 与 \((\eta_i^{(1/2)})\)。代价是概率被开了 \(4\) 次方根（指数 \(1/4\)）。
去耦：四个独立副本做交错和 (+ − − +) Y（j∈B） Ỹ（j∈B 副本） X X̃ + Q(X,Y) − Q(X,Ỹ) − Q(X̃,Y) + Q(X̃,Ỹ) 纯 A、纯 B、线性项全部抵消，只剩 A–B 交叉项 \(c_{ij}(\eta_i-\tilde\eta_i)(\eta_j-\tilde\eta_j)\)
交错和的符号正好是 \((+,-,-,+)\)，等于差分 \((\eta_i-\tilde\eta_i)(\eta_j-\tilde\eta_j)\) 在两个方向上展开。这一步把二次型“掰直”成了一个系数与变量彼此独立的线性型。
例：差分变量 \(\eta^{(1/2)}\) 的分布取 \(\eta,\tilde\eta\) 各为独立的 \(\pm1\)，令 \(\eta^{(1/2)}=(\eta-\tilde\eta)/2\)。列出四种等概率（各 \(1/4\)）的组合：
  1. \(\eta=+1,\ \tilde\eta=+1\Rightarrow\eta^{(1/2)}=0\)。
  2. \(\eta=-1,\ \tilde\eta=-1\Rightarrow\eta^{(1/2)}=0\)。
  3. \(\eta=+1,\ \tilde\eta=-1\Rightarrow\eta^{(1/2)}=+1\)。
  4. \(\eta=-1,\ \tilde\eta=+1\Rightarrow\eta^{(1/2)}=-1\)。
合并：取 \(0\) 的概率 \(=1/4+1/4=1/2\)，取 \(+1\) 与 \(-1\) 各 \(1/4\)。这正是正文中所说的“\(\eta^{(1/2)}\) 的分布”。它仍是“居中对称”的随机量，对它照样能用线性 Littlewood–Offord。
概率 −11/4 01/2 +11/4
\(\eta^{(1/2)}\) 的取值分布：一半概率“静止”在 \(0\)，另一半对称地落在 \(\pm1\)。
两次线性、一次开方，凑出 1/8整条证明的“指数账本”是这样算的：
  1. 去耦把 \(P(Q=x)\) 换成一个新事件概率的 \(1/4\) 次方。
  2. 新事件 \(\sum_i v_i\eta_i^{(1/2)}=0\) 的概率，用两次线性结果控制：第一次保证“约 \(\Omega(k)\) 个 \(v_i\neq0\)”，第二次在这些非零系数上用线性 Littlewood–Offord，得到 \(O(k^{-1/2})\)。
  3. 合起来：\(P(Q=x)\le\big(O(k^{-1/2})\big)^{1/4}=O(k^{-1/8})\)。这就是 \(1/8\) 的来历：\(\tfrac12\times\tfrac14=\tfrac18\)。
习题 7.6.3 指出，更仔细些可以把 \(1/8\) 改进到 \(1/4\)；习题 7.6.1 又说明，再好的常数也逃不过 \(\min(k,l)^{-1/2}\) 这一极限，所以本质指数是 \(1/2\)。
A（≈ k/2 个“富”下标） B = [1,n] \ A（其余下标） 提供乘子 \(\eta_i^{(1/2)}\) 提供系数 \(v_i=\sum_{j\in B}4c_{ij}\eta_j^{(1/2)}\) A 与 B 不相交 ⇒ 乘子与系数独立，这正是能两次用线性结果的根基
贪心地把约 \(k/2\) 个“富”下标放进 \(A\)，使每个 \(i\in A\) 仍有约 \(l/2\) 个非零 \(c_{ij}\) 指向 \(B\)。系数 \(v_i\) 由 \(B\) 端的随机性决定，乘子 \(\eta_i^{(1/2)}\) 由 \(A\) 端决定，二者独立。

应用：随机对称符号矩阵几乎处处非奇异

在 [64] 中，这一估计与上一节的若干技巧结合，被用来得到：

定理 7.34 [64]设 \(M_n\) 是一个随机的对称 \(n\times n\) 矩阵，其元素是随机均匀分布的符号 \(\pm1\)，且上三角部分的元素相互独立。（严格下三角部分的元素当然由对称性从上半部分确定。）则对任意 \(\varepsilon>0\)， \[P\big(\det(M_n)=0\big)=O_\varepsilon\!\left(n^{-1/8+\varepsilon}\right).\]
为什么二次型会冒出来对称矩阵的对角线展开会把同一个随机符号 \(\eta_{ij}\)（\(i二次表达式上——这正是命题 7.33 处理的对象。于是“行列式 \(=0\)”被转化为“某个二次型集中于 \(0\)”，再用 \(P(Q=x)=O(\min(k,l)^{-1/8})\) 压下去，得到 \(n^{-1/8+\varepsilon}\) 的奇异概率上界。
和前几节的对照第 7.5 节处理的是元素全独立的 Bernoulli 矩阵，奇异概率是指数小的 \((1-\varepsilon)^n\) 级；而对称矩阵因为上下三角被强制相等，独立性减半、还引入了二次纠缠，所以这里只能（用本节方法）得到多项式小的 \(n^{-1/8+\varepsilon}\) 级界。结论虽弱些，但已足以说明：随机对称符号矩阵几乎必然可逆。

习题

习题 7.6
  1. 7.6.1　举例说明：对任意 \(k,l\ge1\)，存在满足命题 7.33 假设的 \(Q\)，使得 \(P(Q=0)=\Omega\big(\min(k,l)^{-1/2}\big)\)。因此，除了指数 \(1/8\) 与绝对常数之外，命题 7.33 的结论（在 \(1/2\) 这个本质指数意义下）已是最优的。
  2. 7.6.2　把命题 7.33 推广到 \(\eta_1,\dots,\eta_n\) 的 \(d\) 次多项式，其中 \(1/8\) 由一个依赖于 \(d\) 的指数代替。
  3. 7.6.3　把命题 7.33 中的常数 \(1/8\) 改进为 \(1/4\)。
  4. 7.6.4　（Meshulam，私人通信）找一个二次型 \(Q=\sum_{1\le i,j\le n}c_{ij}\xi_i\xi_j\)，其中对所有 \(i,j\) 都有 \(c_{ij}\neq0\)，而 \(\xi_i\) 是独立同分布的 Bernoulli 随机变量，使得 \[P(Q=0)\ge\big(2-o(1)\big)\frac{\binom{n}{n/2}}{2^{n}}.\] 将此与线性情形（推论 7.4）作比较。
小结本节的一句话：二次的非集中 = 去耦 + 两次线性非集中。去耦把纠缠的二次型“掰直”为系数与变量独立的线性型，代价是概率开四次方；两次调用线性 Littlewood–Offord 各贡献 \(1/2\) 的指数，最终凑成 \(\min(k,l)^{-1/8}\)。它的招牌应用，是证明随机对称 \(\pm1\) 矩阵的奇异概率小到 \(n^{-1/8+\varepsilon}\)。

返回 全书目录