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

7.5　随机伯努利矩阵Random Bernoulli matrices

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

本节目标研究一个看似简单、实则极难的问题：把一个 \(n\times n\) 的方阵随机填上 \(+1\) 或 \(-1\)（每格独立、等概率），它的行列式恰好等于 \(0\) 的概率有多大？等价地：从立方体顶点集 \(\{-1,1\}^n\) 里随机取 \(n\) 个向量，它们线性相关的概率有多大？本节会给出一系列越来越强的上界，最终给出 Kahn–Komlós–Szemerédi 的指数型界 \(P(\det(M_n)=0)\le(1-\varepsilon)^n\)，并讲清前面各节的工具是如何被一一调用进来的。

设 \(M_n\) 为随机的 \(n\times n\) 矩阵，其元素是相互独立、均匀分布的符号 \(\pm1\)（\(M_n\) 常被称为随机伯努利矩阵，random Bernoulli matrix）。与 \(M_n\) 有关的若干量的分布，例如它的行列式与奇异值，是许多领域所关心的对象，包括理论物理、组合学与理论计算机科学。事实证明，前面各节发展出的工具非常适合用于研究 \(M_n\)。

本节我们聚焦于一个特定的问题，即理解奇异概率（singularity probability）\(P(\det(M_n)=0)\)。一个等价的表述是：给定 \(n\) 个向量 \(X_1,\dots,X_n\)，它们独立、均匀地取自单位立方体的顶点集 \(\{-1,1\}^n\subset\mathbb{R}^n\)，问这些向量线性无关的概率是多少？

一个 \(M_5\) 的样例（每格独立 ±1）： +−++− ++−++ −++−+ +−−+− −−+++ 每个格子 \(=+1\) 或 \(-1\)， 独立、各占概率 \(\tfrac12\)。 问：\(\det(M_n)=0\) 的概率？ 即 5 个行向量是否落入某个 过原点的超平面里。
“行列式为零”\(\Longleftrightarrow\)“这些 \(\pm1\) 向量线性相关”\(\Longleftrightarrow\)“它们全部落进 \(\mathbb{R}^n\) 中某个过原点的超平面”。

这个听起来简单的问题，结果却出人意料地不平凡。容易证明

\[\tag{7.9}P\big(X_i=\pm X_j\text{ 对某对 }1\le i一个类似的论证（同时考虑 \(M_n\) 的行与列）给出

\[\tag{7.10}P(\det(M_n)=0)\ge(2+o(1))\,n^2\,2^{-n}.\]

人们猜想这个下界是精确的；于是有：

猜想 7.24 \(\displaystyle P(\det(M_n)=0)=(2+o(1))\,n^2\,2^{-n}\)。特别地，\(\displaystyle P(\det(M_n)=0)=\Big(\tfrac12+o(1)\Big)^n\)。
例：为什么会出现 \(n^2 2^{-n}\) 让行列式为零的最常见原因，是矩阵里有两行恰好相等或恰好相反。
  1. 固定两行 \(i完全相同，每个坐标都得猜对，概率 \(2^{-n}\)；要完全相反，也是 \(2^{-n}\)。两种情形共 \(2\cdot2^{-n}\)。
  2. 这样的行对有 \(\binom{n}{2}=\tfrac{n(n-1)}{2}\approx\tfrac{n^2}{2}\) 对。
  3. 用联合界把它们加起来：\(\approx\tfrac{n^2}{2}\cdot2\cdot2^{-n}=n^2 2^{-n}\)，这正是 (7.9) 的量级。再把“列”也算上，下界就翻倍成 (7.10) 的 \(2n^2 2^{-n}\)。
猜想 7.24 断言：除了这种“两行/两列重合”的简单原因，没有别的来源会显著贡献——这就是它难证之处。注意 \(n^2 2^{-n}\) 和 \((\tfrac12+o(1))^n\) 是同一个量，因为多项式因子 \(n^2\) 会被指数的底数吸收进 \(o(1)\)。

这个猜想至今仍然悬而未决，不过本节将讨论在这个问题上取得的一些进展。注意到 \(M_n\) 奇异，当且仅当存在非零向量 \(v\in\mathbb{R}^n\) 使得 \(M_nv=0\)。通过把 \(v\) 限制在某些特殊的向量集合上，我们可以得到所猜测的界 \((1/2+o(1))^n\)。下面这个结果归功于 Komlós。

定理 7.25（Komlós） 设 \(n\ge3\)，并设 \(\Omega_1\) 为 \(\mathbb{R}^n\) 中至少有 \(3n/\log_2 n\) 个坐标为零的向量构成的集合。则“存在非零 \(v\in\Omega_1\) 使得 \(M_nv=0\)”的概率为 \((1+o(1))\,n^2\,2^{-n}\)。

通过考虑 \(M_n\) 的转置，可以看出这条定理等价于下面的引理。

引理 7.26 设 \(n\ge3\)，并以 \(E\) 记事件“存在非零 \((a_1,\dots,a_n)\in\Omega_1\) 使得 \(a_1X_1+\dots+a_nX_n=0\)”。则 \(P(E)=(1+o(1))\,n^2\,2^{-n}\)。
证明. 为建立上界，我们用联合界给出 \[P(E)=\sum_{2\le k\le n-3n/\log_2 n}P(E_k\setminus E_{k-1}),\] 其中 \(E_k\) 是事件“存在恰有 \(k\) 个分量非零的 \((a_1,\dots,a_n)\in\mathbb{R}^n\) 使得 \(a_1X_1+\dots+a_nX_n=0\)”。（注意事件 \(E_1\) 是空的——单个非零向量永远张不出零。）由 (7.9) 容易看出 \(P(E_2)=(1+o(1))\,n^2\,2^{-n}\)，因此只需证明 \[\sum_{3\le k\le n-3n/\log_2 n}P(E_k\setminus E_{k-1})=o(n^2\,2^{-n}).\] 由对称性我们有 \(\displaystyle P(E_k)\le\binom{n}{k}P(F_k\setminus E_{k-1})\)，其中 \(F_k\) 是事件“存在非零 \(a_1,\dots,a_k\) 使得 \(a_1X_1+\dots+a_kX_k=0\)”。若 \(F_k\setminus E_{k-1}\) 发生，则以 \(X_1,\dots,X_k\) 为列的 \(n\times k\) 矩阵的秩恰为 \(k-1\)，于是 \((a_1,\dots,a_k)\) 本质上是该矩阵中 \(k-1\) 行的楔积（wedge product）。选取这 \(k-1\) 行有 \(\binom{n}{k-1}\) 种方式；固定这些行的全部元素后（从而也固定了 \(a_1,\dots,a_k\)），由推论 7.4 可知，其余 \(n-k+1\) 行中的每一行与方程 \(a_1X_1+\dots+a_kX_k=0\) 相容的概率为 \(\binom{k}{k/2}/2^k\)。于是我们得到 \[P(E_k\setminus E_{k-1})\le\binom{n}{k}\binom{n}{k-1}\left(\frac{\binom{k}{k/2}}{2^k}\right)^{n-k+1}.\] 当 \(k=\Theta(n)\) 时，把 \(\binom{k}{k/2}/2^k\) 估计为 \(O(1/\sqrt n)\)，则该结论由直接计算得出。♦
为什么把 \(v\) 限制在“稀疏”集合上会简单
  1. \(\Omega_1\) 里的向量大部分坐标都是 0（至少 \(3n/\log_2 n\) 个零）。坐标越稀疏，能让 \(\sum a_jX_j=0\) 成立的“随机巧合”就越少。
  2. 关键估计是 \(\dfrac{\binom{k}{k/2}}{2^k}=O\!\Big(\dfrac{1}{\sqrt k}\Big)\)：一个长度 \(k\) 的随机 \(\pm1\) 向量与一个固定向量内积为某特定值的概率，正是中心二项系数除以 \(2^k\)，约 \(\dfrac{1}{\sqrt k}\)。这就是 Erdős–Littlewood–Offord 那条“最大反链/中心系数”界在此处的化身。
  3. 把它对“其余 \(n-k+1\) 行”各自独立地相乘，得到一个非常小的乘方 \((1/\sqrt n)^{\,n-k+1}\)，足以压过两个二项式系数 \(\binom{n}{k}\binom{n}{k-1}\) 的组合爆炸——于是除了 \(k=2\)（两行重合）那一项，其余都是高阶小量。

让我们再考虑另一类受限的向量。设 \(\Omega_2\) 为 \(\mathbb{R}^n\) 中所有坐标绝对值至多为 \(n^C\) 的整数向量构成的集合，其中 \(C\) 是某个正常数。

定理 7.27 “存在非零 \(v\in\Omega_2\) 使得 \(M_nv=0\)”的概率为 \((1/2+o(1))^n\)。（误差项 \(o(1)\) 当然依赖于 \(C\)。）
证明. 下界是平凡的，故我们集中精力于上界。对每个非零向量 \(v\)，记 \(p(v)\) 为“随机伯努利向量 \(X\) 满足 \(X\cdot v=0\)”的概率。显然 \(P(M_nv=0)=p(v)^n\)。由于一个超平面至多包含 \(2^{n-1}\) 个 \(\pm1\) 向量，故 \(p(v)\le 1/2\)。对 \(j=1,2,\dots\)，令 \(S_j\) 为 \(\Omega_2\) 中满足 \(2^{-j-1}2^{-j}\ge n^{-(d+1/3)}.\] （\(d\) 的值依赖于 \(j\)，但被一个常数从上方控制。）置 \(k=n^{\varepsilon}\)。于是 \(2^{-j}\approx k^{-d}\)，我们便可用命题 7.21 来估计 \(S_j\)。事实上，调用该命题可知，选取 \(v\) 的例外坐标的位置与取值至多有 \(\binom{n}{k^2}(2n^C+1)^{k^2}=n^{O(k^2)}=n^{o(n)}\) 种方式。固定广义级数 \(P\) 只有 \((2n^C+1)^{d-1}=n^{O(1)}\) 种方式。一旦 \(P\) 固定，设置 \(v\) 其余坐标的方式至多有 \(|P|^n=(2k+1)^{(d-1)n}\) 种。把这些合在一起， \[S_j\le O(1)^n\,n^{O(k^2)}\,k^{(d-1)n}.\] 由于 \(k=n^{\varepsilon}\) 且 \(2^{-j}\le n^{-(d-1+1/3)}\)，可得 \[2^{-jn}\,S_j\le O(1)^n\,n^{o(n)}\,n^{-n/3}.\] 由于 \(j\) 的个数只有 \(O(\log n)\)，而 \(n^{-\Theta(n)}\log n=o((1/2)^n)\)，证毕。♦
这一步在做什么（直觉） 我们把所有“整数小坐标”向量 \(v\) 按它们的“危险程度” \(p(v)\)（一个随机行恰好垂直于 \(v\) 的概率）分桶：第 \(j\) 桶里 \(p(v)\approx 2^{-j}\)。
  1. 桶里每个 \(v\) 贡献 \((2^{-j})^n\)（要 \(n\) 行同时垂直），所以 \(p(v)\) 越小越无害。
  2. 但小 \(p(v)\) 的桶里向量可能很多（\(S_j\) 大）。胜负取决于 \(S_j\) 增长得快还是 \((2^{-j})^n\) 衰减得快。
  3. 逆 Littlewood–Offord 型结果（命题 7.21）说：要让 \(p(v)\) 不太小，\(v\) 的坐标必须高度结构化——挤进一个广义算术级数 \(P\) 里。结构化意味着“能选的 \(v\) 不多”，于是 \(S_j\) 被严格压住，衰减最终获胜。
这就是“加性组合学反过来帮概率论”的典型套路：从“概率不小”反推“必有算术结构”，再用结构稀少性回收概率。

将定理 7.25 与推论 7.13 结合，我们得到下面的推论。

推论 7.28 [215] 设 \(n\ge3\)。则对任意 \(1\le i\le n\) 有 \[P\big(X_i\text{ 是 }X_1,\dots,X_{i-1}\text{ 的线性组合}\big)\le\min\left(2^{\,i-n-1},\;O\!\Big(\frac{1}{\sqrt n}\Big)\right).\]
证明. 先证明上界 \(2^{i-n-1}\)。注意 \(X_1,\dots,X_{i-1}\) 张成一个维数至多为 \(i-1\) 的空间，因此存在 \(i-1\) 个坐标，它们决定了该空间中所有其余坐标。但若固定了 \(X_i\) 的这 \(i-1\) 个坐标，则 \(X_i\) 仍在剩下的 \(2^{n-i+1}\) 个点中均匀分布，结论随之得出。现在证明界 \(O(1/\sqrt n)\)。我们可以假设 \(n\) 很大且 \(i\) 接近 \(n\)（譬如 \(i>.9n\)）。向量 \(X_1,\dots,X_{i-1}\) 至少包含于一个超平面 \(\{(x_1,\dots,x_n)\in\mathbb{R}^n:a_1x_1+\dots+a_nx_n=0\}\) 中；任意选取一个这样的超平面。由定理 7.25，我们必有 \(\Theta(n)\) 个坐标 \(a\) 非零的概率为 \(1-O(1/\sqrt n)\)（事实上这里可以有高得多的概率）。由推论 7.13，\(X_i\cdot(a_1,\dots,a_n)=0\) 的概率至多为 \(O(1/\sqrt n)\)。由于此事件是 \(X_i\) 成为 \(X_1,\dots,X_{i-1}\) 线性组合的必要条件，结论得证。♦

由这条推论、贝叶斯恒等式与独立性，容易验证当 \(n\) 较大时

\[P(\det(M_n)=0)\le\sum_{i=2}^{n}P\big(X_i\text{ 是 }X_1,\dots,X_{i-1}\text{ 的线性组合}\big)=O\!\left(\frac{\log n}{\sqrt n}\right).\]

在 [215]、[216] 中，通过此方法的一个变体，这个界被略微改进为 \(O(1/\sqrt n)\)。

逐项相乘 vs. 逐项相加（直觉） 要让 \(n\) 个向量线性无关，可以一行一行地添加：第 \(i\) 行只要不落进前 \(i-1\) 行张成的空间即可。
  1. 第 \(i\) 行“掉进去”的概率被推论 7.28 控制为 \(O(1/\sqrt n)\)。
  2. “某一行掉进去”的概率，用联合界 \(\le\sum_{i=2}^n O(1/\sqrt n)=O(\sqrt n)\)——太弱，超过 1，没用。
  3. 真正有用的是把它接到行列式上：\(P(\det=0)\le\sum_i P(\text{第 }i\text{ 行掉进去})\)，而真正接近 \(n\) 的 \(i\) 才贡献 \(O(1/\sqrt n)\)，加起来约 \(O(\log n/\sqrt n)\)。这给出了一个多项式衰减的界——但不是指数级的，离猜想 \((\tfrac12)^n\) 还很远。
要拿到指数界，需要 Kahn–Komlós–Szemerédi 的全新想法（见定理 7.29）。

利用这一论证的一个精细化版本，事实上可以得到关于行列式的如下估计 [364]：

\[P\Big(\,|\det(M_n)|=\sqrt{n!}\,\exp\big(O(n^{1/2}\log^{1/2}n)\big)\Big)=1-o(1).\]

右端几乎是最优的（见习题 7.5.3 与 7.5.4）。借助 [366] 中近期的结果，可以使 \(o(1)=1/n^{C}\) 对任意固定的 \(C\) 成立，代价是改变左端 \(O\) 中隐藏的常数。然而，是否能取到 \(o(1)=\exp(-\Theta(n))\) 仍不清楚。

现在我们来介绍 Kahn、Komlós 与 Szemerédi 的一项突破性结果 [195]，它在没有任何限制的情况下建立了一个指数型的界。

定理 7.29 [195] 存在一个正常数 \(\varepsilon\) 使得 \(P(\det(M_n)=0)\le(1-\varepsilon)^n\)。

事实上，[195] 中得到的显式值为 \(\varepsilon=0.001\)。这在 [364] 中被改进到大约 \(\varepsilon=0.042\)，随后在 [365] 中被改进到 \(\varepsilon=\tfrac14+o(1)\)。猜想 7.24 断言可以取 \(\varepsilon=\tfrac12+o(1)\)，那将是最优可能的结果。

我们现在勾勒定理 7.29 的证明。用下面这条引理重新表述问题会很方便：

引理 7.30 [195],[374],[364] 我们有 \[P(\det(M_n)=0)=2^{o(n)}\,P\big(X_1,\dots,X_n\text{ 张成一个超平面}\big).\]
证明. 我们已经知道 \[P(\det(M_n)=0)=P\big(X_1,\dots,X_n\text{ 线性相关}\big).\] 因此下界是显然的，我们只需建立上界。若 \(X_1,\dots,X_n\) 线性相关，则必存在某个 \(0\le d\le n-1\) 使得 \(X_1,\dots,X_{d+1}\) 张成一个 \(d\) 维子空间。固定 \(d\) 并以此事件为条件，反复应用推论 7.28 可见，\(X_1,\dots,X_n\) 张成一个超平面的概率为 \(2^{-o(n)}\)。结论得证。♦
“线性相关”\(\approx\)“恰好张成一张超平面”
  1. 线性相关只说“张成的维数 \(\le n-1\)”，可能是任意维 \(d\)。
  2. 引理 7.30 说：维数偏小（\(d
  3. 所以在指数尺度上，几乎所有“相关”都是“恰好差一维”，即所有点落在同一张超平面 \(V\) 上。于是问题归结为：对每张超平面 \(V\)，估计“\(n\) 个点全落在 \(V\) 上”的概率，再对所有 \(V\) 求和。

用这条引理再配合联合界，于是只需证明 \[\sum_V P\big(X_1,\dots,X_n\text{ 张成 }V\big)\le(1-\varepsilon+o(1))^n,\] 其中 \(V\) 取遍所有超平面。注意我们可以把注意力限制在那些由其与 \(\{-1,1\}^n\) 的交张成的超平面 \(V\)；容易看出这是一个有限集合。我们称这样的超平面为非平凡的（non-trivial）。与一张非平凡超平面相关联的一个重要的量是它的密度 \[P(X\in V)=\frac{|V\cap\{-1,1\}^n|}{|\{-1,1\}|^n},\] 这里我们把 \(X\) 看成 \(\{-1,1\}^n\) 中的一个随机元素。注意只要 \(v\) 是 \(V\) 的法向量，就有 \(P(X\in V)=P(X\cdot v=0)\)。我们可以用下面的引理排除掉所有低密度超平面的贡献：

引理 7.31 [195] 对任意 \(0<\alpha<1\)，我们有 \[\sum_{V:\,P(X\in V)\le\alpha}P\big(X_1,\dots,X_n\text{ 张成 }V\big)\le n\alpha.\]
证明. 若 \(X_1,\dots,X_n\) 张成超平面 \(V\)，则存在某个 \(1\le i\le n\)，使得从 \(X_1,\dots,X_n\) 中去掉 \(X_i\) 后所成的 \(n-1\) 个向量仍然张成 \(V\)。固定 \(i\) 并以此事件为条件，可见 \(V\) 由除 \(X_i\) 之外的所有向量所决定，而此时 \(X_i\) 也落在 \(V\) 中的概率至多为 \(\alpha\)。结论得证。♦
超平面 \(V\)（过原点） 红点：落在 \(V\) 内的 ±1 顶点 灰点：不在 \(V\) 内的顶点 密度 \(=\dfrac{\#\text{红点}}{2^n}=P(X\in V)\)
每张非平凡超平面 \(V\) 抓住一部分 \(\pm1\) 顶点；抓得越多，密度 \(P(X\in V)\) 越高，\(n\) 个随机点全落进去的概率 \(\approx P(X\in V)^n\) 也越大。低密度超平面由引理 7.31 一次性清扫掉。

这样，为建立断言，只需考虑那些满足 \(P(X\in V)\ge(1-\varepsilon)^n\) 的高密度超平面。另一方面，由引理 7.26 与推论 7.13，我们可以控制那些满足 \(P(X\in V)\gg\tfrac1{\sqrt n}\) 的极高密度超平面。所以实际上我们只需处理 \[(1-\varepsilon)^n\le P(X\in V)\le O\!\Big(\tfrac1{\sqrt n}\Big)\] 这一段范围。

现在我们关键性地用到相对 Halász 不等式，即引理 7.14。令 \(0<\mu\ll1\) 为一个小参数（与 \(n\) 无关），并令 \(Y\in\{-1,0,1\}^n\) 为随机变量 \(Y=(\eta_1^{(\mu)},\dots,\eta_n^{(\mu)})\)。引理 7.14 蕴含（当 \(n\) 足够大时）：若 \(\mu\) 足够小，则 \(Y\) 比 \(X\) 更强地集中在上述超平面 \(V\) 上：

\[\tag{7.11}P(Y\in V)=O(\sqrt\mu)\,P(X\in V).\]

若我们使用非正式的启发式 \[P\big(X_1,\dots,X_n\text{ 张成 }V\big)\approx P(X\in V)^n,\] 那么我们就期望 \[P\big(X_1,\dots,X_n\text{ 张成 }V\big)\le O(\sqrt\mu)^n\,P\big(Y_1,\dots,Y_n\text{ 张成 }V\big),\] 其中 \(Y_1,\dots,Y_n\) 是 \(Y\) 的相互独立的同分布副本。对此式在 \(V\) 上求和，并利用一个平凡事实——每一组 \(Y_1,\dots,Y_n\) 至多张成一张超平面 \(V\)——我们于是期望 \[P(M_n=0)\le O(\sqrt\mu)^n,\] 取 \(\mu\) 足够小，这当然就给出了定理 7.29。

核心想法：把 \(X\) 换成更“尖”的 \(Y\)
  1. \(X\) 的每个坐标是 \(\pm1\)；而 \(Y\) 的每个坐标以大概率取 \(0\)、小概率（由 \(\mu\) 控制）取 \(\pm1\)。\(Y\) 更稀疏。
  2. 相对 Halász 不等式 (7.11) 说：对同一张超平面，\(Y\) 落入的概率只是 \(X\) 的 \(O(\sqrt\mu)\) 倍——一个可以任意调小的固定折扣。
  3. 把“\(n\) 个点全落进 \(V\)”看成 \(n\) 次独立事件相乘，\(X\) 版与 \(Y\) 版相差因子 \(O(\sqrt\mu)^n\)。
  4. 而 \(Y\) 版求和后总量 \(\le1\)（每组 \(Y\) 至多定一张 \(V\)）。于是 \(X\) 版总量 \(\le O(\sqrt\mu)^n\)，取 \(\mu\) 小到使 \(\sqrt\mu<1-\varepsilon\)，就压出了指数界。这正是把加性组合学的集中不等式当作“概率折扣券”来用。

上述策略几乎奏效，唯有一个小问题：\(Y_1,\dots,Y_n\) 可能彼此过于线性相关，以至于它们只张成 \(V\) 的一个真子空间，而非 \(V\) 本身。解决这个问题最简单的办法，是只使用少量的 \(Y\)，譬如取 \(Y_1,\dots,Y_{\delta n}\)，其中 \(\delta\) 很小1。若 \(V\) 的密度足够高且 \(\delta\) 足够小，我们就能保证 \(Y_1,\dots,Y_{\delta n}\) 在 \(V\) 中保持线性无关。这把本论证中潜在的收益从 \(O(\sqrt\mu)^n\) 削减到了仅 \(O(\sqrt\mu)^{\delta n}\)，但这仍足以建立定理 7.29。

更严格地，我们引入独立于 \(X_1,\dots,X_n\) 的 \(Y_1,\dots,Y_{\delta n}\)。固定一个密度 \((1-\varepsilon)^n\le\sigma\le O(1/\sqrt n)\)，并令 \(V\) 满足 \(P(X\in V)=(1+O(\tfrac1n))\sigma\)： \[P\big(Y_1,\dots,Y_{\delta n}\in V\big)\ge\Omega\!\Big(\tfrac{1}{\sqrt\mu}\Big)^{\delta n}\sigma^{\delta n}.\] 若 \(\delta\) 充分小（依赖于 \(\mu\)），且 \(\varepsilon\) 充分小（依赖于 \(\delta\) 与 \(\mu\)），则可以修改推论 7.28，把上式精细化为 \[\tag{7.12}P\big(Y_1,\dots,Y_{\delta n}\text{ 在 }V\text{ 中线性相关}\big)\ge\Omega\!\Big(\tfrac{1}{\sqrt\mu}\Big)^{\delta n}\sigma^{\delta n};\] 我们把它留作习题。由独立性，我们于是有 \[P\big(X_1,\dots,X_n\text{ 张成 }V\big)\le O(\sqrt\mu)^{\delta n}\,\sigma^{-\delta n}\,P(E_V),\] 其中 \(E_V\) 是事件“\(X_1,\dots,X_n\) 张成 \(V\) 且 \(Y_1,\dots,Y_{\delta n}\) 在 \(V\) 中线性无关”。但若此事件发生，则在 \(X_1,\dots,X_n\) 中存在 \(n-\delta n\) 个向量，它们与 \(Y_1,\dots,Y_{\delta n}\) 一起张成 \(V\)。若固定所有这些向量，则 \(V\) 也被固定，而 \(X_1,\dots,X_n\) 中剩下的 \(\delta n\) 个向量落在 \(V\) 中的概率为 \(O(\sigma^{\delta n})\)。我们于是断定 \[\sum_{V:\,P(X\in V)=(1+O(\frac1n))\sigma}P(E_V)\le\binom{n}{\delta n}\,O(\sigma^{\delta n}),\] 将其与前面诸估计结合，给出 \[\sum_{V:\,P(X\in V)=(1+O(\frac1n))\sigma}P\big(X_1,\dots,X_n\text{ 张成 }V\big)\le O(\sqrt\mu)^{\delta n}\binom{n}{\delta n}.\] 若我们选取 \(\delta\) 充分小（依赖于 \(\mu\)）、\(\varepsilon\) 充分小（依赖于 \(\delta,\mu\)），就能使右端为 \((1-\varepsilon+o(1))^n\)。再对所有相关的 \(\sigma\) 求和（这样的 \(\sigma\) 只有大约 \(O(n^2)\) 个），即如所愿地得到定理 7.29。

1 严格来说，我们应当用 \(\lfloor\delta n\rfloor\) 代替 \(\delta n\)，但为叙述方便，我们将略去这个无关紧要的细节。

为什么只用 \(\delta n\) 个 \(Y\) 仍然够（直觉）
  1. 理想方案“用满 \(n\) 个 \(Y\)”会因 \(Y\) 太稀疏而张不满 \(V\)，论证失效。
  2. 折中：只用 \(\delta n\) 个 \(Y\)（一小批），再借 \(n-\delta n\) 个 \(X\) 凑齐 \(V\) 的其余维度。这样 \(Y\) 这一小批仍能保持线性无关。
  3. 代价是折扣券只剩 \(O(\sqrt\mu)^{\delta n}\)（指数变小了），但底数仍 \(<1\)，乘上组合因子 \(\binom{n}{\delta n}\) 后整体仍为 \((1-\varepsilon)^n\) 量级。指数界因此保住。

利用定理 7.23，可以把 \(\varepsilon\) 提升到大至 \(\tfrac14+o(1)\)。其基本要点在于：定理 7.23 允许人们显著地改进 (7.11)，除非超平面 \(V\) 具有某种例外的形态（特别是，其法向量的坐标……）。

（本节摘录至此结束；正文在此处转入对例外超平面之法向量结构的进一步讨论，超出本 PDF 节选范围。）

本节回顾 一条主线串起全章工具：
  1. 问题：\(P(\det M_n=0)\)，猜想 \((\tfrac12+o(1))^n\)，主因是“两行/两列重合”（定理 7.24，量级 \(n^2 2^{-n}\)）。
  2. 受限情形：把法向量 \(v\) 限制在稀疏向量集 \(\Omega_1\)（定理 7.25/引理 7.26）或小整数向量集 \(\Omega_2\)（定理 7.27），用中心二项系数界 \(\binom{k}{k/2}/2^k=O(1/\sqrt k)\) 和逆 Littlewood–Offord（命题 7.21）即可拿到 \((\tfrac12+o(1))^n\)。
  3. 逐行添加：推论 7.28 给出每行“掉进旧空间”的概率 \(O(1/\sqrt n)\)，但只得多项式界 \(O(\log n/\sqrt n)\)。
  4. 指数界：Kahn–Komlós–Szemerédi（定理 7.29）把问题化为“点全落进高密度超平面 \(V\)”（引理 7.30、7.31），再用相对 Halász 不等式 (7.11) 把 \(X\) 换成更稀疏的 \(Y\)，赚到折扣因子 \(O(\sqrt\mu)^{\delta n}\)，得到 \((1-\varepsilon)^n\)。后续工作把 \(\varepsilon\) 推到 \(\tfrac14+o(1)\)。

返回 全书目录