7.4 逆 Littlewood–Offord 结果Inverse Littlewood–Offord results
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 定理 / 证明 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
- 本章里 \(X_v^{(\mu)}=\eta_1 v_1+\cdots+\eta_n v_n\)，其中 \(\eta_1,\dots,\eta_n\) 独立同分布，取 \(0\) 的概率为 \(1-\mu\)，取 \(+1\) 和 \(-1\) 的概率各为 \(\mu/2\)。当 \(\mu=1\) 时，\(\eta_i\) 就是纯随机的 \(\pm1\)（随机符号）。
- 集中概率记 \(P_\mu(v):=\max_x P\big(X_v^{(\mu)}=x\big)\)——随机和最爱待的那一点的命中概率。
- 一个秩为 \(d\) 的广义等差级数 \(P=\{a_0+m_1 w_1+\cdots+m_d w_d\}\)（各 \(m_i\) 跑一段整数区间）。它的体积 \(V\) 是这些系数组合的总个数；若所有组合给出的元素互不相同（映射单射），就称它是正常的（proper），此时 \(|P|=V\)。对称的（symmetric）指各系数区间形如 \([-N_i,N_i]\)、以原点为中心。
从正向到逆向：先看两个“取逆否”的例子
在前几节我们考虑的是正向 Littlewood–Offord 结果：对步长 \(v=(v_1,\dots,v_n)\) 作某些假设，作为结论得到集中概率 \(P\big(X_v^{(\mu)}=x\big)\) 的某种上界。在许多应用中，更有意思的是建立逆向 Littlewood–Offord 结果：假设集中概率有一个下界，并由此推出 \(v\) 的某种结构性质。当然，每个正向结果都可以通过取逆否命题变成一个逆向结果。
例如，由推论 7.13 我们知道：若 \(v_1,\dots,v_n\) 落在一个无挠群 \(Z\) 中，且对某个 \(0<\mu\le1\) 与某个 \(x\in Z\) 有 \[P\big(X_v^{(\mu)}=x\big)\ \ge\ \frac{1}{\sqrt{\mu k}},\] 则 \(v_1,\dots,v_n\) 中至多有 \(O(k)\) 个是非零的。
类似地，由推论 7.16 可见：若 \(v_1,\dots,v_n\) 是正整数，且对某个 \(0<\mu\le1\) 与 \(x\in\mathbb Z\)，集中概率 \(P\big(X_v^{(\mu)}=x\big)\) 远大于 \(\mu^{-1/2}n^{-3/2}\)，则其中至少有两个 \(v_j\) 相等（事实上容易证明：必有大量的对 \((v_i,v_j)\) 彼此相等）。
- 第一个：和如果非常爱往某一点跑，那么真正在“搅动”这个和的非零步必然不多（最多 \(O(k)\) 个），其余都是 \(0\)——这是最朴素的“结构”。
- 第二个：若全是正整数还能高度集中，那一定出现了重复值。直觉是：互不相同的正整数会让 \(\pm\) 求和散得很开（取值很多），难以集中；要想集中，就得靠重复的值“对消”出同一个数。
现在我们考虑能给出步长 \(v_1,\dots,v_n\) 更多结构的逆向 Littlewood–Offord 定理。本节的结果可与逆和集估计（inverse sum set estimates）类比：在后者中，我们假设某集合 \(A\) 有较小的倍增常数，并由此推出 \(A\) 的某种结构信息，例如 \(A\) 被包含在一个等差级数之内。为简单起见，我们将聚焦于 \(\mu=1\) 的情形（不过可以借助推论 7.12 或引理 7.14 之类的结果，把它推广到更一般的 \(\mu\)）。
动机：广义等差级数让集中概率变大（例 7.19）
让我们从一个 \(\max_x P(X_v^{(1)}=x)\) 很大的例子开始。正是这个例子构成了我们这些结果的主要动机。
上面的例子表明：若 \(v\) 的元素属于一个秩小、体积小的广义等差级数，则 \(P_\mu(v)\) 就大。我们自然希望它的逆命题也成立，即：
下面我们给出几个支持这一论断的结果。先给一个简单但相当弱的结果。
第一步结果：装进一个 \(d\) 维立方体（命题 7.20）
- 反证起手。假设 \(v\) 装不进任何 \(d\) 维立方体。引理 4.35 翻译成人话：装不进 \(d\) 维立方体，就一定能找出 \(d+1\) 个步长 \(w_1,\dots,w_{d+1}\)，它们“互相独立”到极致——任何系数取自 \(\{-1,0,1\}\) 的组合 \(\sum m_i w_i\) 都给出不同的值（这就是“非相关 dissociated”）。
- 条件化（conditioning）。把和拆成“和 \(w\) 有关的部分”\(+\)“其余部分”。固定其余部分后，要让总和等于 \(x\)，只剩下 \(w\) 那部分要等于某个 \(y\)。所以命中 \(x\) 的概率不超过 \(w\) 那部分命中最热门点 \(y\) 的概率。
- 非相关 ⇒ 分得很开。\(w\) 有 \(d+1\) 个元，符号选择共 \(2^{d+1}\) 种。非相关保证这 \(2^{d+1}\) 个和全不相同（这里要用 \(Z\) 无 \(2\)-挠，否则 \(w_i\) 与 \(-w_i\) 可能相等而撞车）。既然 \(2^{d+1}\) 个等可能的结果互不相同，单点概率最多 \(2^{-(d+1)}\)。
- 撞出矛盾。于是 \(P(X_v^{(1)}=x)\le 2^{-d-1}\)，与假设 \(>2^{-d-1}\) 冲突。所以最初的反设不成立，\(v\) 必能装进 \(d\) 维立方体。♦
在实践中，这个命题用处不大，因为立方体的维数 \(d\) 可能相当大（典型情形约为 \(\log n\)）。然而，可以通过增大边长来降低维数，并允许少量例外的步长 \(v_j\) 落在所得级数之外。
第二步结果：降维、放长、容许少量例外（命题 7.21）
注意，推论 7.13（取 \(\mu=1\)）可看作本命题 \(d=1\) 的情形，而命题 7.20 可看作 \(k=1\) 的极限情形。当然，应取 \(k<\sqrt n\)，以免结论变得空洞。
- “或者…或者…”是一个二选一：要么集中概率小到 \(\le\delta_d k^{-d}\)（没结构，但概率被压住了）；要么概率大，那就必有结构——几乎所有步长都被一个 \((d-1)\) 维、边长 \(2k\) 的级数 \(P\) 捕获。
- “边长换维数”。命题 7.20 用边长 \(2\)（系数 \(\{-1,0,1\}\)）但维数高达 \(\sim\log n\)；这里把边长放大到 \(2k\)（系数 \([-k,k]\)），维数就降到了 \(d-1\)。盒子从“瘦高”变“矮胖”。
- \(a_0 v_j\in P\) 里的 \(a_0\)。不是 \(v_j\) 本身在 \(P\) 里，而是它的某个 \(1\) 到 \(k\) 倍在 \(P\) 里。这个 \(a_0\) 因子有点碍眼，定理 7.22 会去掉它（代价是把级数放大一些）。
- \(k^2\) 个例外。允许少数“捣乱分子”逃到 \(P\) 外面，只要求其余的都被框住。
- 第 0 步. 初始化 \(r=0\)。此时 \((w_1,\dots,w_r)\) 平凡地是 \(k\)-非相关的，且由推论 7.12 有 \[P\Big(X^{(1/4d)}_{\,v^{(d-r)k^2}\,w_1^{k^2}\cdots w_r^{k^2}}=0\Big)\ \ge\ P\big(X_v^{(1)}=x\big).\tag{7.7}\]
- 第 1 步. 数一数有多少个 \(1\le j\le n\) 使得 \((w_1,\dots,w_r,v_j)\) 仍是 \(k\)-非相关的。若这个数目小于 \(k^2\)，则终止算法；否则进入第 2 步。
- 第 2 步. 应用推论 7.12，可找到一个 \(v_j\)，使得 \((w_1,\dots,w_r,v_j)\) 是 \(k\)-非相关的，且 \[P\Big(X^{(1/4d)}_{\,v^{(d-r)k^2}\,w_1^{k^2}\cdots w_r^{k^2}}=0\Big)\ \le\ P\Big(X^{(1/4d)}_{\,v^{(d-r-1)k^2}\,w_1^{k^2}\cdots w_r^{k^2}\,v_j^{k^2}}=0\Big).\] 然后令 \(w_{r+1}:=v_j\)，并把 \(r\) 增加到 \(r+1\)。返回第 1 步。注意这样做时 \((w_1,\dots,w_r)\) 仍保持 \(k\)-非相关，且 (7.7) 仍然成立。
假设我们在某步 \(r\le d-1\) 终止。那么我们得到一个 \(k\)-非相关的 \(r\)-元组 \((w_1,\dots,w_r)\)，但使 \((w_1,\dots,w_r,v_j)\) 为 \(k\)-非相关的 \(v_j\) 至多只有 \(k^2\) 个。展开定义，这表明：除至多 \(k^2\) 个 \(v_j\) 之外，都存在 \(a_0\in[1,k]\) 使得 \(a_0 v_j\in Q-Q\)，其中 \(Q:=[0,k]^r\cdot(w_1,\dots,w_r)\) 且 \(r\le d-1\)。把若干个“占位”向量添加到 \(w_j\) 中，即得结论。
现在证明：我们确实必定在某步 \(r\le d-1\) 终止。（反证）假设我们到达了第 \(d\) 步。那么我们有一个 \(k\)-非相关元组 \((w_1,\dots,w_d)\)，使得 \[P\big(X_v^{(1)}=x\big)\ \le\ P\Big(X^{(1/4d)}_{\,w_1^{k^2}\cdots w_d^{k^2}}=0\Big).\] 令 \(\Gamma\subset\mathbb Z^d\) 为格 \[\Gamma:=\{(m_1,\dots,m_d)\in\mathbb Z^d:\ m_1w_1+\cdots+m_dw_d=0\},\] 则利用独立性可写出 \[P\big(X_v^{(1)}=x\big)\ \le\ P\Big(X^{(1/4d)}_{\,w_1^{k^2}\cdots w_d^{k^2}}=0\Big)\ =\ \sum_{(m_1,\dots,m_d)\in\Gamma}\ \prod_{j=1}^d P\big(X^{(1/4d)}_{1^{k^2}}=m_j\big),\tag{7.8}\] 其中 \(X^{(1/4d)}_{1^{k^2}}=\eta_1+\cdots+\eta_{k^2}\)。
现在使用一个体积装填（volume-packing）论证。一个涉及二项式公式的简单计算（或对参数 \(k^2\) 作归纳）表明：表达式 \(P\big(X^{(1/4d)}_{1^{k^2}}=m\big)\) 关于 \(m\) 是偶函数，且对正的 \(m\) 递减。当 \(|m|\le k\) 时它还是 \(\Theta_d(1/k)\)（这可由斯特林公式 (1.52)，或由推论 7.13 及方差、单调性的考量看出）。于是我们有 \[P\big(X^{(1/4d)}_{1^{k^2}}=m\big)\ =\ O_d\!\Big(\frac1k\sum_{m'\in m+(-k/2,\,k/2)}P\big(X^{(1/4d)}_{1^{k^2}}=m'\big)\Big),\] 从而由 (7.8) 得 \[P\big(X_v^{(1)}=x\big)\ \le\ O_d\!\Big(k^{-d}\!\!\sum_{(m_1,\dots,m_d)\in\Gamma}\ \sum_{(m_1',\dots,m_d')\in(m_1,\dots,m_d)+(-k/2,\,k/2)^d}\ \prod_{j=1}^d P\big(X^{(1/4d)}_{1^{k^2}}=m_j'\big)\Big).\] 由于 \((w_1,\dots,w_d)\) 是 \(k\)-非相关的，落在 \(\Gamma\) 中的所有 \((m_1,\dots,m_d)\) 都互不相同，因而它们各自加上 \((-k/2,k/2)^d\) 后所得的小盒子互不重叠。于是我们断定 \[P\big(X_v^{(1)}=x\big)\ \le\ O_d\!\Big(k^{-d}\!\!\sum_{(m_1,\dots,m_d)\in\mathbb Z^d}\ \prod_{j=1}^d P\big(X^{(1/4d)}_{1^{k^2}}=m_j\big)\Big).\] 但由并集界（union bound）有 \[\sum_{(m_1,\dots,m_d)\in\mathbb Z^d}\ \prod_{j=1}^d P\big(X^{(1/4d)}_{1^{k^2}}=m_j\big)\ =\ 1.\] 为完成证明，把命题中的常数 \(\delta_d\) 取为大于 \(O_d(k^{-d})\) 中隐藏常数即可。♦
- 算法在干嘛？每一步都试图找一个新方向 \(v_j\)，让加进来后仍保持 \(k\)-非相关（即新的级数仍“正常”、不塌缩）。只要还能找到 \(\ge k^2\) 个这样的 \(v_j\)，就挑一个“最优”的（让目标概率不降）加进去。
- 算法停下时（\(r\le d-1\)）= 好情形。停下意味着“能扩张方向的 \(v_j\) 不到 \(k^2\) 个”。剩下的绝大多数 \(v_j\) 都不能扩张，这恰恰说明它们（的某个 \(\le k\) 倍）被已有的 \(w_1,\dots,w_r\) 张成的小级数 \(Q-Q\) 捕获——这正是命题要的结构。维数 \(r\le d-1\)，正好。
- 算法停不下来（跑满 \(d\) 步）= 坏情形，要排除。若真凑齐了 \(d\) 个 \(k\)-非相关方向 \(w_1,\dots,w_d\)，把概率展开成在格 \(\Gamma\) 上的求和 (7.8)。
- 体积装填的核心一招。单个一维分布 \(P(X^{(1/4d)}_{1^{k^2}}=m)\) 在 \(|m|\le k\) 这段内大小约 \(1/k\)，所以一个点的概率 \(\approx\) 把它周围 \(k\) 宽的小区间概率摊平平均。乘到 \(d\) 维，就是把 \(\Gamma\) 上每个点替换成它周围 \(k\times\cdots\times k\) 的小盒。
- 不重叠 ⇒ 求和 \(\le1\)。\(k\)-非相关保证 \(\Gamma\) 里的点彼此隔得够远，小盒互不重叠，于是把它们并起来不会超过整个 \(\mathbb Z^d\) 上的总和，而后者由并集界恰等于 \(1\)。多出来的 \(k^{-d}\) 因子就是结论里的 \(\delta_d k^{-d}\)。这与“到达第 \(d\) 步”所隐含的概率大相矛盾，故算法必在 \(r\le d-1\) 处终止。♦
去掉 \(a_0\)：完整的逆 Littlewood–Offord 定理（定理 7.22）
上述命题中的 \(a_0\) 因子有些不尽如人意。多花一些力气，可以去掉这个因子，但代价是把级数稍微放大一些。
定理 7.22 的证明颇为冗长，但它是命题 7.21 证明的一个改良。详情见 [366]。
- 去掉了 \(a_0\)。命题 7.21 只保证 \(a_0 v_j\in P\)（某个倍数在里面）；定理 7.22 保证 \(v_j\) 本身就在 \(P\) 里。
- 量化更干净。只要集中概率 \(\ge n^{-A}\)（多项式级别的下界，相当弱的假设），就能得到秩 \(\le B\)、体积 \(\le n^B\) 的级数，只漏掉 \(\le Bn^\alpha\) 个元素（\(\alpha\) 可任意小）。这正是“概率大 ⇒ 结构（小 GAP）”这一猜想的强形式。
相对 Halász 不等式的逆定理（定理 7.23）
对相对 Halász 不等式（引理 7.14），在 [365] 中也得到了一个精神类似的逆定理：
事实上，还得到了一些额外的结构信息，即：\(v_1,\dots,v_n\) 大部分被包含在级数 \(P\) 的“核”（core）之中，并且……
- 第一个条件 \(P(X_v^{(1)}=0)\ge\varepsilon_1\,P(X_v^{(1/4-\varepsilon_0/100)}=0)\)：把 \(\mu=1\)（纯随机符号）下的集中度与一个更“懒惰”（\(\mu\approx1/4\)，常取 \(0\)）的版本作比较，保证集中不是靠大量 \(\eta_i=0\) 偷来的。
- 第二个条件 \(P(X_v^{(1)}=0)\ge(\tfrac34+2\varepsilon_0)^n\)：直接给集中概率一个指数级下界，即“集中得相当厉害”。
- 结论里体积约为 \(1/P(X_v^{(1)}=0)\)：集中概率越大，能框住所有步长的级数就越小——与例 7.19 给出的下界 (7.6) 的方向完全吻合，互为正逆。
返回 全书目录