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

7.2　傅里叶分析方法The Fourier-analytic approach

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 引理 / 推论 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是全书较硬的一节，凡有公式都先给出最小的具体例子（常取所有 \(v_j=1\) 的“掷硬币随机游走”）再讲一般情形。

本节目标 我们要研究这样一个随机量：给定 \(n\) 个数（或群里的元素）\(v_1,\dots,v_n\)，给每个数随机配一个正负号 \(\varepsilon_j=\pm1\)，看带号和 \[X_v=\varepsilon_1 v_1+\cdots+\varepsilon_n v_n\] 落在某一点的概率有多大。Littlewood–Offord 问题问的是：这个概率最大能有多大（即随机和最多能“挤”在一个点上多少）？上一节用纯组合方法处理，本节改用傅里叶分析——核心一招是把“\(X_v\) 等于某个点的概率”这种计数式的离散量，改写成一个积分／期望，然后用三角函数、求和集增长（柯西–达文波特不等式）等连续工具去估计它。本节最终目标是 Halász 的两条强有力的集中不等式（引理 7.14、7.15），它们给出比组合方法更精细的上界。

现在我们来介绍 Halász 的傅里叶分析方法。用概率论的语言会比较方便。对加法群 \(Z\) 中任意一个步长 \(n\)-元组 \(v=(v_1,\dots,v_n)\)，我们用记号 \(X_v\) 表示随机变量 \[X_v:=\varepsilon_1 v_1+\cdots+\varepsilon_n v_n,\] 其中 \(\varepsilon_1,\dots,\varepsilon_n\) 是相互独立的随机变量，各以概率 \(1/2\) 取值 \(-1\) 或 \(+1\)。显然，\(\mathbb P(X_v=x)\) 等于把 \(x\) 写成 \(\varepsilon_1 v_1+\cdots+\varepsilon_n v_n\)（其中 \(\varepsilon_1,\dots,\varepsilon_n\in\{-1,1\}\)）的表示法个数除以 \(2^n\)。注意 \(X_v\) 在对 \(n\)-元组 \(v\) 作置换下是不变的。我们用 \(vw\) 表示 \(v\) 与 \(w\) 的拼接。于是 Littlewood–Offord 问题就是要控制给定 \(v\) 时 \(X_v\) 的分布；而逆 Littlewood–Offord 问题则是：在已知 \(X_v\) 具有某种“反常”的分布性质时，反推 \(v\) 必须具有的某种结构信息。

例：最小的具体例子 取 \(v=(1,1,1)\)（即 \(n=3\)，三个步长都是 \(1\)）。那么 \(X_v=\varepsilon_1+\varepsilon_2+\varepsilon_3\)，每个 \(\varepsilon_j\) 独立地等可能取 \(\pm1\)。一共有 \(2^3=8\) 种符号选法，对应的和及其出现次数为： \[+3:\,1\ \text{种};\quad +1:\,3\ \text{种};\quad -1:\,3\ \text{种};\quad -3:\,1\ \text{种}.\] 所以 \(\mathbb P(X_v=1)=3/8\)，这是最大的单点概率。换句话说，把三枚 \(\pm1\) 加起来，“最挤”的那一点也只占 \(3/8\)。Littlewood–Offord 问题正是要把这种“最挤”程度估计清楚。
−3−1 +1+3 13 33 最高的一根：\(\tfrac38\) \(X_v=\varepsilon_1+\varepsilon_2+\varepsilon_3\) 的取值与表示法个数（共 8 种）
把符号和按取值分组：\(\pm3\) 各 \(1\) 种、\(\pm1\) 各 \(3\) 种。最高的一根（\(=+1\)）占 \(3/8\)，这就是 \(n=3\) 时的最大单点概率。一般地，\(v=(1,\dots,1)\) 时分布就是二项分布，最高峰约为 \(\binom{n}{n/2}/2^n\approx \sqrt{2/(\pi n)}\)，随 \(n\) 增大像 \(1/\sqrt n\) 那样变矮。

引入更一般的随机变量 \(X_v^{(\mu)}\)（对任意 \(0\le\mu\le1\)）会很有用，它定义为 \[X_v^{(\mu)}:=\varepsilon_1^{(\mu)}v_1+\cdots+\varepsilon_n^{(\mu)}v_n,\] 其中 \(\varepsilon_1^{(\mu)},\dots,\varepsilon_n^{(\mu)}\) 是相互独立的随机变量，各以概率 \(\mu/2\) 取 \(+1\) 和 \(-1\)，以概率 \(1-\mu\) 取 \(0\)。于是当 \(\mu=1\) 时 \(X_v^{(\mu)}\) 就回到 \(X_v\)；另一个极端 \(\mu=0\) 时它退化为常数 \(0\)。中间的情形对应于步长为 \(v_1,\dots,v_n\) 的“懒惰随机游走”（lazy random walks）。由于 \(\varepsilon_i\) 有相当大的概率取 \(0\)，可以预期 \(X_v^{(\mu)}\) 会比 \(X_v\) 更集中；事实也确实如此。在实际操作中，\(\mu\le1/2\) 的情形比 \(\mu=1\) 的情形更便于做傅里叶分析，这是因为我们马上会用到的某种“正性”（positivity）性质。

为什么叫“懒惰”，以及“正性”是什么 参数 \(\mu\) 是“迈步的概率”：每一步以概率 \(\mu\) 真的走一步（\(\pm v_j\)），以概率 \(1-\mu\) 原地不动（取 \(0\)）。\(\mu\) 越小越“懒”，走得越少，越容易停在原点附近，所以更集中。
“正性”指的是：本节核心公式里会出现因子 \(1-\mu+\mu\cos(2\pi\theta)\)。由于 \(\cos\ge-1\)，这个因子 \(\ge 1-2\mu\)；只要 \(\mu\le1/2\)，它就恒为非负。非负的量好处大——可以两边取对数、可以当成“权重”来比较大小，傅里叶分析里许多放缩都依赖它。\(\mu=1\) 时这个因子 \(1-1+\cos=\cos\) 可正可负，处理起来麻烦得多，这就是偏爱 \(\mu\le1/2\) 的原因。

本节我们考虑离散问题：理解随机变量 \(X_v^{(\mu)}\) 集中在单个点的概率 \(\mathbb P(X_v^{(\mu)}=x)\)。下一节将简要讨论类似的、集中在一个立方体中的概率 \(\mathbb P(X_v^{(\mu)}\in Q)\)。

两步技术化简：把背景群换成“有限且阶为奇数”

我们先对问题做一些技术性的化简。

第一，可以化归到背景群 \(Z\) 为有限的情形。这只要对步长 \(v_1,\dots,v_n\) 施加一个合适的 \(n\) 阶 Freiman 同构（见习题 5.3.3）即可达到，同时注意这不改变 \(X_v\) 的分布。

第二，还可以进一步化归到 \(Z\) 的阶为奇数的情形。要看清这一点，由推论 3.8，任何有限加法群都能写成一个 2-挠群（2-torsion group）与一个奇数阶群的乘积。随机变量 \(X_v\) 投影到 2-挠群分量上时表现是平凡的（因为在这个群里 \(+v_j=-v_j\)），所以不失一般性，我们可以投影到另一个因子上。注意，如果原来的元素 \(v_1,\dots,v_n\) 处在某个无挠群（如 \(\mathbb Z^d\)）中，那么由引理 5.25，我们现在可以把这些向量放进一个奇素数阶的循环群里。（这样做时可能暂时遮蔽掉 \(v_1,\dots,v_d\) 的某些“维数”结构，所以在论证的某些阶段，有时回到原来的背景群会更方便。）

为什么要排除偶数阶（2-挠） 2-挠群里每个元素满足 \(x+x=0\)，即 \(-x=x\)。于是符号 \(\varepsilon_j\) 取 \(+1\) 还是 \(-1\) 毫无区别（\(+v_j=-v_j\)），随机性消失，问题变得平凡。把这种“没信息”的分量丢掉，只留奇数阶的部分，问题才有意思。奇数阶还有一个技术好处：映射 \(\xi\mapsto 2\xi\) 是可逆的（因为 \(2\) 与群的阶互素），下面证明里会反复用到“换元 \(\xi\to2\xi\)”这一招。

把分布写成傅里叶变换：核心引理 7.11

做了这些化简后，我们现在可以用傅里叶变换来表达 \(X_v\) 的分布。和往常一样，我们在 \(Z\) 上固定一个对称的、非退化的双线性型 \(\xi\cdot x\)（取值在 \(\mathbb R/\mathbb Z\) 中）。以下记 \(e(t):=e^{2\pi i t}\)。

引理 7.11（\(X_v\) 的傅里叶表示） 设 \(Z\) 是奇数阶有限群。若 \(v=(v_1,\dots,v_n)\) 是 \(Z\) 中元素的 \(n\)-元组，则对任意 \(0\le\mu\le1\) 与 \(x\in Z\)，有 \[\mathbb P\!\left(X_v^{(\mu)}=x\right)=\mathbb E_{\xi\in Z}\,\cos(2\pi\,\xi\cdot x)\prod_{j=1}^n\bigl(1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\bigr).\]
证明. 由于量 \(\prod_{j=1}^n(1-\mu+\mu\cos(2\pi\,\xi\cdot v_j))\) 是 \(\xi\) 的偶函数，我们可以把右端写成 \[\mathbb E_{\xi\in Z}\,e(-\xi\cdot x)\prod_{j=1}^n\bigl(1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\bigr).\] 注意到 \(1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)=\mathbb E\bigl(e(\xi\cdot\varepsilon_j^{(\mu)}v_j)\bigr)\)，并利用 \(\varepsilon_j^{(\mu)}\) 的相互独立性，可把上式重写为 \[\mathbb E\,\mathbb E_{\xi\in Z}\,e\!\left(\xi\cdot\bigl(X_v^{(\mu)}-x\bigr)\right).\] 现在结论就由引理 4.5（特征的正交性 / 傅里叶反演）得到。♦
  1. 为什么 \(1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\) 正好是某个期望。 对单个步长 \(\varepsilon_j^{(\mu)}v_j\) 算期望 \(\mathbb E\,e(\xi\cdot\varepsilon_j^{(\mu)}v_j)\)：以概率 \(\mu/2\) 取 \(+v_j\)，贡献 \(\tfrac{\mu}{2}e(\xi\cdot v_j)\)；以概率 \(\mu/2\) 取 \(-v_j\)，贡献 \(\tfrac{\mu}{2}e(-\xi\cdot v_j)\)；以概率 \(1-\mu\) 取 \(0\)，贡献 \(1-\mu\)。相加并用 \(\tfrac12(e(\theta)+e(-\theta))=\cos(2\pi\theta)\)，恰得 \(1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\)。
  2. 为什么连乘 \(\prod_j\) 出现。 因为各步 \(\varepsilon_j^{(\mu)}\) 相互独立，整段游走的指数期望 \(\mathbb E\,e(\xi\cdot X_v^{(\mu)})=\mathbb E\,e\!\bigl(\xi\cdot\sum_j\varepsilon_j^{(\mu)}v_j\bigr)=\prod_j\mathbb E\,e(\xi\cdot\varepsilon_j^{(\mu)}v_j)\)——独立随机变量之和的指数期望等于各自期望之积。
  3. 为什么对 \(\xi\) 取期望就抓出了概率。 这正是傅里叶反演（引理 4.5）：对群里所有“频率” \(\xi\) 求平均 \(\mathbb E_{\xi\in Z}\,e(\xi\cdot y)\)，当 \(y=0\) 时等于 \(1\)，否则等于 \(0\)。所以 \(\mathbb E_{\xi}\,e(\xi\cdot(X_v^{(\mu)}-x))\) 恰好挑出“\(X_v^{(\mu)}=x\)”这一事件，对它再取概率期望就得到 \(\mathbb P(X_v^{(\mu)}=x)\)。
用 \(v=(1,1,1)\) 验证引理 7.11 取 \(Z=\mathbb Z_N\)（\(N\) 大的奇数），\(\xi\cdot x=\xi x/N\)，\(\mu=1\)，验证 \(\mathbb P(X_v=1)=3/8\)。此时连乘是 \(\cos^3(2\pi\xi/N)\)，公式给出 \[\mathbb P(X_v=1)=\mathbb E_{\xi}\cos(2\pi\xi/N)\cos^3(2\pi\xi/N)=\mathbb E_\xi\cos^4(2\pi\xi/N).\] 当 \(N\to\infty\) 时 \(\mathbb E_\xi\cos^4(2\pi\xi/N)\to\int_0^1\cos^4(2\pi t)\,dt=\tfrac38\)。和我们前面手数的 \(3/8\) 完全一致——这说明傅里叶公式确实在算同一个概率，只是换了一种“积分”的算法。

这条引理已经突出了 \(0\le\mu\le\tfrac12\) 这一情形的特殊地位：此时 \(1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\) 变成非负的。在更进一步的情形 \(0\le\mu\le\tfrac14\) 下，我们有下面这条初等却极有用的估计： \[1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)=\exp\!\Bigl(-\Theta\bigl(\mu\,\|\xi\cdot v_j\|_{\mathbb R/\mathbb Z}^2\bigr)\Bigr),\tag{7.1}\] 这里 \(\|x\|_{\mathbb R/\mathbb Z}\) 表示 \(x\) 到最近整数的距离。

读懂 (7.1) 把因子写成指数形式有什么好处？因为连乘 \(\prod_j\) 取对数后变成求和 \(-\Theta(\mu\sum_j\|\xi\cdot v_j\|^2)\)，求和远比连乘好估计。这个等式的依据是：当 \(\theta\) 小时 \(1-\cos(2\pi\theta)\approx 2\pi^2\theta^2\)，而 \(\|\cdot\|_{\mathbb R/\mathbb Z}\) 量的就是 \(\theta\) 离整数的距离；于是 \(1-\mu+\mu\cos=1-\mu(1-\cos)\approx\exp(-\mu(1-\cos))\)，再把 \(1-\cos\) 换成同阶的 \(\|\cdot\|^2\)。符号 \(\Theta(\cdot)\) 表示“上下都被常数倍夹住”，即两边只差一个绝对常数因子。直观上：\(\xi\cdot v_j\) 离整数越远，这一项越小，对概率的贡献越被压制。

由引理 7.11 立刻得到的比较型界：推论 7.12

由引理 7.11，我们能立即建立若干关于“一个分布 \(X_v^{(\mu)}\) 如何控制另一个分布”的有用界限。

推论 7.12 设 \(v=(v_1,\dots,v_n)\)、\(w=(w_1,\dots,w_m)\) 是加法群 \(Z\)（无挠，或有限且阶为奇数）中的元组，\(x\in Z\)。
证明. 如前所述，可设 \(Z\) 为奇数阶有限群。各情形都用引理 7.11 把概率改写。Hölder 公式是显然的；当 \(\mu\le1/2\) 时控制公式也显然（因为各因子非负，去掉 \(w\) 那些非负因子只会让乘积变大，而 \(\cos(2\pi\,\xi\cdot x)\le1\)）。在 \(\mu\le\mu'/4\) 的情形，注意到初等不等式 \[|\cos(\pi\theta)|\le\frac34+\frac14\cos(2\pi\theta),\] 从而（由三角不等式） \[\bigl|(1-\mu')+\mu'\cos(\pi\theta)\bigr|\le\Bigl(1-\frac{\mu'}{4}\Bigr)+\frac{\mu'}{4}\cos(2\pi\theta).\] 于是结论由换元 \(\xi\to2\xi\)（当 \(Z\) 为奇数阶时可逆）得到。
重复公式同理由初等不等式 \[(1-\mu)+\mu\cos(2\pi\theta)\le\Bigl(1-\frac{\mu}{k}+\frac{\mu}{k}\cos(2\pi\theta)\Bigr)^k\] 推出，这只要两边取对数并利用 \(\log(1-t)\) 在区间 \(0凹性即可看出。♦
  1. “控制”在直觉上说什么。 它说：把 \(\mu'\) 调小成 \(\mu\)、并把多余的步长 \(w\) 删掉，得到的随机和在原点处的概率，必定不小于原来那个和落在任意点 \(x\) 的概率。两件事都让分布更集中（更懒、步更少），所以单点概率只升不降。最后一句“原点最集中”是因为公式里只有 \(x=0\) 时 \(\cos(2\pi\,\xi\cdot x)\equiv1\) 取到最大，其它 \(x\) 的 \(\cos\) 会有正有负地相消。
  2. 为什么 \(\mu\le\mu'/4\) 这一支需要 \(\xi\to2\xi\)。 当 \(\mu'\) 可能大于 \(1/2\) 时，因子未必非负，不能直接放缩。这时用倍角技巧：\(|\cos(\pi\theta)|\) 被一个非负的、关于 \(\cos(2\pi\theta)\) 的线性式压住，再把变量 \(\xi\) 换成 \(2\xi\) 就把 \(\pi\) 变回 \(2\pi\)。换元可逆正是靠群的阶为奇数。代价是把系数从 \(\mu'\) 缩到 \(\mu'/4\)，这就是条件里那个 \(4\) 的来源。
  3. “重复”为何把 \(\mu\) 除以 \(k\)。 把每个步长复制 \(k\) 份，同时把迈步概率从 \(\mu\) 降到 \(\mu/k\)，总的“有效迈步量”大致守恒，但分布更集中。凹性不等式保证复制后原点概率只增不减。

上述推论表明，当 \(\mu\le1/2\) 时，量 \(\mathbb P(X_v^{(\mu)}=0)\) 在对元组 \(v\)（例如增删重复元素）和参数 \(\mu\) 做“小修小补”时是相当稳定的。作为一个应用，我们给出推论 7.4 的一个傅里叶分析版本。

推论 7.13 设 \(v=(v_1,\dots,v_n)\) 是无挠群 \(Z\) 中的 \(n\)-元组，使得 \(v_j\) 中至少有 \(k\) 个非零。则对所有 \(0<\mu\le1\) 与 \(x\in Z\)，有 \[\mathbb P\!\left(X_v^{(\mu)}=x\right)=O\!\left(\frac{1}{\sqrt{\mu k}}\right).\]
证明. 用控制性质可设 \(\mu\le1/2\)。不失一般性设 \(v_1,\dots,v_k\) 非零。反复运用推论 7.12 得 \[\mathbb P\!\left(X_v^{(\mu)}=x\right)\le\mathbb P\!\left(X_{vv}^{(\mu/2)}=0\right)\le\mathbb P\!\left(X_{vv_j^k}^{(\mu/2)}=0\right)\le\mathbb P\!\left(X_{v_j^k}^{(\mu/2)}=0\right)\] 对某个 \(1\le j\le k\) 成立。后面这个量是随机游走理论中的标准量1，可以用斯特林公式 (1.52) 组合地算出来，但我们这里给出一个傅里叶分析的算法。把 \(v_j^k\) 经 Freiman 同构映到某个大循环群 \(Z_N\) 中的单位元 \(1\)，用引理 7.11 得 \[\mathbb P\!\left(X_{v_j^k}^{(\mu/2)}=0\right)=\mathbb E_{\xi\in Z_N}\Bigl(1-\frac{\mu}{2}+\frac{\mu}{2}\cos(2\pi\xi/N)\Bigr)^k,\] 从而令 \(N\to\infty\) 取极限： \[\mathbb P\!\left(X_{v_j^k}^{(\mu/2)}=0\right)=\int_0^1\Bigl(1-\frac{\mu}{2}+\frac{\mu}{2}\cos(2\pi\xi)\Bigr)^k d\xi.\] 用 (7.1)，只需对积分 \(\int_0^1\exp\bigl(-\Theta(k\mu\,\xi^2)\bigr)\,d\xi\) 作界。容易证明这个积分的大部分权重落在区间 \((0,\,C/\sqrt{\mu k})\) 中（\(C\) 为某个大常数）。结论得证。♦
  1. 把链条看清楚。 第一步用“重复”把 \(v\) 复制成 \(vv\) 并把 \(\mu\) 减半；第二步插入 \(v_j^k\)（某个非零步长复制 \(k\) 份）；第三步用控制把多余部分删掉，只留 \(v_j^k\)。于是问题归结为“同一个非零步长走 \(k\) 步”的最简单游走。
  2. 为什么最后是高斯积分。 \(\bigl(1-\tfrac\mu2+\tfrac\mu2\cos\bigr)^k\) 经 (7.1) 变成 \(\exp(-\Theta(k\mu\|\xi\|^2))\)，这是个钟形（高斯型）曲线，宽度约 \(1/\sqrt{\mu k}\)。整条曲线下的面积就约为它的高度 \(O(1)\) 乘宽度，即 \(O(1/\sqrt{\mu k})\)。这就是 \(1/\sqrt{\mu k}\) 这个量级的来源——它本质上是中心极限定理“\(n\) 步随机游走的典型范围约 \(\sqrt n\)、单点概率约 \(1/\sqrt n\)”的精确版本。

我们指出，在 \(\mu=1\) 的情形，推论 7.4 给出尖锐的界 \[\mathbb P\!\left(X_v^{(1)}=x\right)\le\binom{k}{\lfloor k/2\rfloor}\Big/2^k=\Theta\!\left(\frac{1}{\sqrt k}\right),\] 这要归功于斯特林公式 (1.52)。这表明傅里叶分析方法能给出差一个绝对常数即尖锐的界。如果步长 \(v_1,\dots,v_n\) 足够“高维”，还能做得比这个 \(O(1/\sqrt k)\) 型的界更好；见习题 7.2.3。

回到 \(v=(1,1,1)\)：核对 \(1/\sqrt k\) 取 \(k=3\)，\(\mu=1\)。上式右端 \(\binom{3}{1}/2^3=3/8\)，正是我们一开始数出来的最大单点概率。再取大一点，\(k=4\)：\(\binom{4}{2}/2^4=6/16=3/8\)；\(k=100\) 时约为 \(\sqrt{2/(100\pi)}\approx0.08\)。可见峰值确实像 \(1/\sqrt k\) 那样缓慢变矮——步数翻到四倍，峰只降一半。
取值（带号和，居中对齐） \(k\) 小：窄而高，峰 \(\sim1/\sqrt k\) \(k\) 大：宽而矮
步数 \(k\) 越大，带号和的分布越宽（典型范围约 \(\sqrt k\)）也越矮（峰值约 \(1/\sqrt k\)）。推论 7.13 把这条直觉对任意非零步长都证明了出来。

更深的分布不等式：Halász 相对集中不等式

现在我们给出一条更深刻的分布不等式，它特别地依赖于柯西–达文波特不等式（定理 5.4）。

引理 7.14（Halász 相对集中不等式）[195] 设 \(Z\) 或为无挠群，或为奇素数阶的循环群。设 \(v\) 是 \(Z\) 中的元组。则对任意满足 \(\mu\le1/4\) 的 \(0<\mu\le\mu'\le1\)，对所有 \(x\in Z\) 有 \[\mathbb P\!\left(X_v^{(\mu')}=x\right)\le O\!\left(\sqrt{\frac{\mu}{\mu'}}\right)\mathbb P\!\left(X_v^{(\mu)}=0\right)+O\!\left(\mathbb P\!\left(X_v^{(\mu)}=0\right)^{\mu'/\mu}\right).\]

注意，控制不等式只给出 \(\mathbb P(X_v^{(\mu')}=x)\le\mathbb P(X_v^{(\mu)}=0)\)。因此当 \(\mu\) 显著小于 \(\mu'\) 时，Halász 不等式更优——此时它断言 \(X_v^{(\mu)}\) 在原点处的集中频率远高于 \(X_v^{(\mu')}\)（因为第一项前面的系数 \(\sqrt{\mu/\mu'}\) 很小，要让不等式成立，\(\mathbb P(X_v^{(\mu)}=0)\) 必须相对很大）。关于这条不等式的更多讨论及更定量的版本，见 [195]、[364]、[365]。

证明. 用控制不等式可设 \(\mu'\le1/2\) 且 \(x=0\)。也可设 \(\mu'/\mu\) 很大。由推论 5.25 可设 \(Z=Z_p\)（\(p\) 为奇素数）。引入函数 \(F,G:Z\to\mathbb R^+\)： \[F(\xi):=\prod_{j=1}^n\bigl(1-\mu'+\mu'\cos(2\pi\,\xi\cdot v_j)\bigr);\qquad G(\xi):=\prod_{j=1}^n\bigl(1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\bigr);\] 于是由引理 7.11，我们的任务是证明 \[\mathbb E_{Z_p}(F)=O\!\left(\sqrt{\frac{\mu}{\mu'}}\right)\mathbb E_{Z_p}(G)+O\!\left(\mathbb E_{Z_p}(G)^{\mu'/\mu}\right).\] 现设 \(0<\alpha\le1\) 任意。由 (7.1) 可见，若 \(\xi\in Z_p\) 满足 \(F(\xi)>\alpha\)，则 \[\Bigl(\sum_{j=1}^n\|\xi\cdot v_j\|_{\mathbb R/\mathbb Z}^2\Bigr)^{1/2}=O\!\left(\sqrt{\frac{\log\frac1\alpha}{\mu'}}\right).\] 由三角不等式，于是得到：若 \(\xi_1,\dots,\xi_m\) 是集合 \(\{\xi\in Z_p:F(\xi)\ge\alpha\}\) 中任意元素，则 \[\Bigl(\sum_{j=1}^n\|(\xi_1+\cdots+\xi_m)\cdot v_j\|_{\mathbb R/\mathbb Z}^2\Bigr)^{1/2}=O\!\left(m\sqrt{\frac{\log\frac1\alpha}{\mu'}}\right).\] 若取 \(m=c\sqrt{\mu'/\mu}\)（\(c>0\) 为某个小的绝对常数），再用一次 (7.1) 便得 \[G(\xi_1+\cdots+\xi_m)>\alpha.\] 换句话说，我们建立了如下求和集包含关系： \[m\{\xi\in Z_p:F(\xi)>\alpha\}\subseteq\{\xi\in Z_p:G(\xi)>\alpha\}.\] 反复运用柯西–达文波特不等式2，得 \[\mathbb P_{Z_p}\bigl(m\{\xi\in Z_p:G(\xi)>\alpha\}\bigr)\ge\max\bigl(m\,\mathbb P_{Z_p}(\{\xi\in Z_p:F(\xi)>\alpha\}),\,1\bigr).\] 若 \(\alpha\ge\mathbb E_{Z_p}(G)\)，则由马尔可夫不等式 \(\mathbb P_{Z_p}(\{\xi:G(\xi)>\alpha\})<1\)，从而 \[\mathbb P_{Z_p}(\{\xi:F(\xi)>\alpha\})\le\frac1m\,\mathbb P_{Z_p}(\{\xi:G(\xi)>\alpha\}).\] 对 \(\alpha\) 积分，得 \[\mathbb E_{Z_p}\bigl(F\cdot\mathbf 1(F\ge\mathbb E_{Z_p}(G))\bigr)\le\frac1m\,\mathbb E_{Z_p}(G)=O\!\left(\sqrt{\frac{\mu}{\mu'}}\,\mathbb E_{Z_p}(G)\right).\] 另一方面，由 (7.1) 有逐点界 \(F(\xi)\le G^{(\mu'/\mu)}(\xi)\)，从而 \[\mathbb E_{Z_p}\bigl(F\cdot\mathbf 1(F<\mathbb E_{Z_p}(G))\bigr)\le\mathbb E_{Z_p}(G)^{\mu'/\mu}.\] 把这两式相加，即得结论。♦
这条证明的灵魂：把“概率大的频率”当集合做加法 整条证明的关键是把抽象的概率估计，翻译成集合求和集变大的几何问题。
  1. 定义两族函数 \(F\)（用大参数 \(\mu'\)）、\(G\)（用小参数 \(\mu\)）。由引理 7.11，要比的两个概率分别是 \(F,G\) 的平均值。
  2. 看“水平集” \(\{F>\alpha\}\)（\(F\) 比阈值 \(\alpha\) 还大的那些频率 \(\xi\)）。由 (7.1)，\(F(\xi)>\alpha\) 等价于 \(\sum_j\|\xi\cdot v_j\|^2\) 很小，即 \(\xi\) 在“好集合”里。
  3. 把好集合里的 \(m\) 个频率相加 \(\xi_1+\cdots+\xi_m\)，由三角不等式它的 \(\sum\|\cdot\|^2\) 至多放大 \(m^2\) 倍。只要 \(m=c\sqrt{\mu'/\mu}\)，放大量恰好被 \(\mu'/\mu\) 的差距吸收，使得这个和仍落在 \(\{G>\alpha\}\) 里。于是 \(m\{F>\alpha\}\subseteq\{G>\alpha\}\)。
  4. 柯西–达文波特登场：在 \(Z_p\) 里，把一个集合自加 \(m\) 次，大小至少变成原来的 \(m\) 倍（直到填满整个群）。所以 \(\{G>\alpha\}\) 至少是 \(\{F>\alpha\}\) 的 \(m\) 倍大，即 \(\mathbb P(\{F>\alpha\})\le\frac1m\mathbb P(\{G>\alpha\})\)。
  5. 对所有阈值 \(\alpha\) 积分，就把“\(F\) 的平均 \(\le\frac1m\,G\) 的平均”兑现出来。\(\frac1m=\sqrt{\mu/\mu'}\) 正是不等式里那个小系数。
习题 7.2.5 表明：若把 \(Z\) 换成非循环有限群（如 \(\mathbb F_3^d\)），柯西–达文波特失效，这条不等式就会崩——这恰好说明了 Cauchy–Davenport 在 Halász 论证中的关键作用。
\(Z_p\)（频率全体） \(\{F>\alpha\}\) → 自加 \(m\) 次 \(m\{F>\alpha\}\subseteq\{G>\alpha\}\) 大小 \(\ge m\) 倍
柯西–达文波特不等式：在 \(Z_p\) 里把集合 \(\{F>\alpha\}\) 自加 \(m\) 次，大小至少放大 \(m\) 倍。它把“求和集包含关系”翻译成概率上的 \(1/m\) 因子，这正是 Halász 不等式比朴素控制更强的根源。

更直接的单点界：Halász 集中不等式

对上述论证稍作修改，可得到关于 \(\mathbb P(X_v^{(\mu)}=x)\) 的一个更直接的界。

引理 7.15（Halász 集中不等式）[167] 设 \(Z\) 是奇素数阶的循环群，\(v=(v_1,\dots,v_n)\) 是 \(Z\) 中的元组且所有 \(v_j\) 均非零。则对任意 \(0<\mu\le1\) 与 \(x\in Z\)，有 \[\mathbb P\!\left(X_v^{(\mu)}=x\right)\le O\!\left(\frac{1}{\sqrt{\mu n}}\,\mathbb P_{\xi\in Z}\Bigl(\sum_{j=1}^n\cos(2\pi\,\xi\cdot v_j)\ge\frac n2\Bigr)\right)+\exp\bigl(-\Theta(\mu n)\bigr).\tag{7.2}\]
证明. 用控制性质可设 \(\mu\le1/2\)。由引理 7.11 与 (7.1)， \[\mathbb P\!\left(X_v^{(\mu)}=x\right)\le\mathbb E_Z F\le\mathbb E_{\xi\in Z}\exp\!\Bigl(-\Theta\bigl(\mu\sum_{j=1}^n\|\xi\cdot v_j\|_{\mathbb R/\mathbb Z}^2\bigr)\Bigr).\] 我们可以按 \(\bigl(\sum_{j=1}^n\|\xi\cdot v_j\|_{\mathbb R/\mathbb Z}^2\bigr)^{1/2}\) 的大小把右端分段，从而把上式界为 \[O\!\left(\sum_{1\le m\le c\mu n}\exp(-\Theta(m))\,\mathbb P_{\xi\in Z}\Bigl(\bigl(\sum_{j=1}^n\|\xi\cdot v_j\|_{\mathbb R/\mathbb Z}^2\bigr)^{1/2}\le\sqrt{m/\mu}\Bigr)\right)+\exp(-\Theta(c\mu n)),\] 其中 \(c>0\) 是小的绝对常数。现注意到 \[\|\xi\cdot v_j\|_{\mathbb R/\mathbb Z}^2=\Theta\bigl(1-\cos(2\pi\,\xi\cdot v_j)\bigr),\tag{7.3}\] 它与引理 4.5 结合给出 \(\mathbb E_{\xi\in Z}\|\xi\cdot v_j\|_{\mathbb R/\mathbb Z}^2=\Theta(1)\)。由期望的线性性，于是有 \[\mathbb E_{\xi\in Z}\sum_{j=1}^n\|\xi\cdot v_j\|_{\mathbb R/\mathbb Z}^2=\Theta(n);\] 特别地可见，若 \(c\) 足够小，则 \(\mathbb P_{\xi\in Z}\bigl((\sum_{j=1}^n\|\xi\cdot v_j\|^2)^{1/2}\le c\sqrt n\bigr)\) 严格小于 \(1\)。像前一证明那样运用柯西–达文波特不等式，得到 \[\mathbb P_{\xi\in Z}\Bigl(\bigl(\sum_{j=1}^n\|\xi\cdot v_j\|^2\bigr)^{1/2}\le\sqrt{m/\mu}\Bigr)\le O\!\left(\sqrt{\frac{m}{\mu n}}\right)\mathbb P_{\xi\in Z}\Bigl(\bigl(\sum_{j=1}^n\|\xi\cdot v_j\|^2\bigr)^{1/2}\le c\sqrt n\Bigr).\] 再次用 (7.3)，便得 \[\mathbb P_{\xi\in Z}\Bigl(\bigl(\sum_{j=1}^n\|\xi\cdot v_j\|^2\bigr)^{1/2}\le\sqrt{m/\mu}\Bigr)\le O\!\left(\sqrt{\frac{m}{\mu n}}\right)\mathbb P_{\xi\in Z}\Bigl(\sum_{j=1}^n\cos(2\pi\,\xi\cdot v_j)\ge\frac n2\Bigr)\] （只要 \(c\) 足够小）。结论随即由如下观察得到： \[\sum_{1\le m\le\sqrt{\mu n}}\exp(-\Theta(m))\sqrt{\frac{m}{\mu n}}=O\!\left(\frac{1}{\sqrt{\mu n}}\right)\] （\(\exp(-\Theta(m))\) 的几何级数衰减足以压过 \(\sqrt m\) 的多项式增长）。♦
  1. (7.3) 在说什么。 \(\|\xi\cdot v_j\|^2\)（到最近整数距离的平方）与 \(1-\cos(2\pi\,\xi\cdot v_j)\) 是同阶的——两者都在 \(\xi\cdot v_j\) 为整数时为 \(0\)、离整数越远越大。于是“\(\sum\cos\ge n/2\)”就等价于“\(\sum\|\cdot\|^2\) 较小”，即 \(\xi\) 让多数 \(\xi\cdot v_j\) 都接近整数。
  2. 分段求和的好处。 直接对 \(\mathbb E\exp(-\Theta(\mu\sum\|\cdot\|^2))\) 估计不好下手，于是按指数的大小（用整数 \(m\) 标记“\(\sum\|\cdot\|^2\approx m/\mu\)”这一层）切片，每片的权重是 \(\exp(-\Theta(m))\)，再乘上落在该片的频率比例。柯西–达文波特把每片比例都压到 \(\sqrt{m/(\mu n)}\) 乘“最集中那层”的比例。
  3. 结论的形状。 把各片求和，几何衰减的 \(\exp(-\Theta(m))\) 把 \(\sqrt m\) 压住，留下总系数 \(1/\sqrt{\mu n}\)。所以最终单点概率 \(\lesssim\frac{1}{\sqrt{\mu n}}\times(\text{“多数 }\xi\cdot v_j\text{ 接近整数”的频率比例})\)。后一个比例越小，说明 \(v\) 越“分散”，随机和越不集中。

这个界很容易就蕴含推论 7.13，而且事实上要强得多。例如，我们有：

推论 7.16 [167] 设 \(0<\mu\le1\)，\(n\) 充分大（依赖于 \(\mu\)）。设 \(v=(v_1,\dots,v_n)\) 是正整数的元组。对每个整数 \(j>0\)，记 \(m_j\) 为 \(j\) 在 \(v\) 中出现的次数，即 \(m_j:=\bigl|\{1\le i\le n:v_i=j\}\bigr|\)。则对任意 \(x\in Z\) 有 \[\mathbb P\!\left(X_v^{(\mu)}=x\right)\le O\!\left(\mu^{-1/2}n^{-5/2}\sum_{j>0}m_j^2\right).\] 特别地，若所有 \(v_i\) 互不相同，则 \[\mathbb P\!\left(X_v^{(\mu)}=x\right)\le O\!\left(\mu^{-1/2}n^{-3/2}\right).\]

我们指出，在 \(\mu=1\) 的情形，本推论的后半句最早是在 [310] 中用组合方法建立的（精确的阈值见 [330]）。

证明. 我们可以用 Freiman 同构把 \(v_1,\dots,v_n\) 放进某个很大的素数阶群 \(Z_p\) 中。直接应用帕塞瓦尔定理 4.2 得 \[\mathbb E_{\xi\in Z_p}\Bigl|\sum_{j=1}^n\cos(2\pi\,\xi\cdot v_j)\Bigr|^2=O\!\left(\sum_{j>0}m_j^2\right),\] 从而由马尔可夫不等式， \[\mathbb P_{\xi\in Z_p}\Bigl(\sum_{j=1}^n\cos(2\pi\,\xi\cdot v_j)\ge\frac n2\Bigr)=O\!\left(\frac{1}{n^2}\sum_{j>0}m_j^2\right).\] 结论随即由引理 7.15 得到（注意当 \(n\) 大时 \(\exp(-\Theta(\mu n))=O(\mu^{-1/2}n^{-5/2})\)）。♦
为什么“互不相同”给出 \(n^{-3/2}\) 量 \(\sum_{j>0}m_j^2\) 度量 \(v\) 里有多少“重复”。
  1. 若所有 \(v_i\) 互不相同，则每个 \(m_j\) 要么是 \(0\) 要么是 \(1\)，于是 \(\sum_j m_j^2=\sum_j m_j=n\)。代入主界 \(\mu^{-1/2}n^{-5/2}\cdot n=\mu^{-1/2}n^{-3/2}\)，得后半句。
  2. 另一极端：若 \(v=(1,1,\dots,1)\)（全相同），则 \(m_1=n\)，\(\sum m_j^2=n^2\)，主界给出 \(\mu^{-1/2}n^{-1/2}\)——正是推论 7.13 那个较弱的 \(1/\sqrt{\mu n}\)。
  3. 所以“元素越分散（重复越少），随机和越不集中”被定量化为：单点概率 \(\propto\sum m_j^2\)。习题 7.2.6 表明在 \(m_j\) 递减时这个界已无法改进（除常数外）。
这就是傅里叶方法的威力：组合方法只看“有多少非零步长”，而它能看到“步长的重复结构 \(\sum m_j^2\)”，从而给出更细的界。
全相同 \(v=(1,\dots,1)\) \(\sum m_j^2=n^2\)，最集中 互不相同 \(v=(1,2,3,\dots)\) \(\sum m_j^2=n\)，最分散
柱高表示各值出现的次数 \(m_j\)。左：全挤在一个值上，\(\sum m_j^2=n^2\)，随机和最集中；右：均匀分散，\(\sum m_j^2=n\)，随机和最不集中。推论 7.16 把单点概率精确地系于 \(\sum m_j^2\)。

习题

习题
  1. 7.2.1　证明：在推论 7.12 控制不等式的条件 \(\mu\le\mu'/4\) 中，常数 \(4\) 不能换成任何更小的常数，即使在最重要的 \(\mu'=1\) 情形也如此。
  2. 7.2.2　若 \(v=(v_1,\dots,v_n)\) 是整数元组，证明对所有整数 \(m\)， \[\mathbb P\!\left(X_v^{(\mu)}=m\right)=\int_0^1\cos(2\pi m\xi)\prod_{j=1}^n\bigl(1-\mu+\mu\cos(2\pi v_j\xi)\bigr)\,d\xi.\]
  3. 7.2.3　[167] 设 \(1\le k\le n\) 且 \(d\ge1\)，设 \(v=(v_1,\dots,v_n)\) 是 \(\mathbb R^d\) 中向量的元组，且是“非退化”的，即 \(\mathbb R^d\) 的每个真子空间至多包含 \(v_1,\dots,v_n\) 中的 \(n-k\) 个。证明对每个 \(0<\mu\le1\) 与 \(x\in\mathbb R^d\)， \[\mathbb P\!\left(X_v^{(\mu)}=x\right)=O_d\bigl((\mu k)^{-d/2}\bigr).\] （提示：仿照推论 7.13，从形如 \(\mathbb P(X_{v^d}^{(\mu/d)}=0)\) 的表达式出发，适当地运用 Hölder 不等式以得到形如 \(\mathbb P(X_{w_1^k w_2^k\cdots w_d^k}^{(\mu/d)})\) 的量，其中 \(w_1,\dots,w_d\in\mathbb R^d\) 线性无关。）给出例子说明这个界在 \(O_d(\cdot)\) 记号中的隐含常数意义下是最优的。
  4. 7.2.4　[364] 在引理 7.14 的记号与假设下，建立 Halász 不等式的如下定量特例： \[\mathbb P\!\left(X_v^{(1)}=x\right)\le\frac12\mathbb P\!\left(X_v^{(1/16)}=0\right)+\mathbb P\!\left(X_v^{(1/16)}=0\right)^4.\]
  5. 7.2.5　证明：当 \(Z\) 是非循环有限群时，引理 7.14 可以失效。特别地，若 \(Z=\mathbb F_3^d\)，证明在适当选取元组 \(v\) 时，对很大一段 \(\mu\) 的范围，\(\mathbb P(X_v^{(\mu)}=0)\) 可以与 \(1/3^d\) 同阶。这说明柯西–达文波特不等式在 Halász 论证中起到的关键作用。
  6. 7.2.6　证明：若 \(m_j\) 关于 \(j\) 递减，则推论 7.16 的右端除隐含常数外不可改进。（提示：计算 \(X_v^{(\mu)}\) 的方差。）
  7. 7.2.7　设 \(0<\mu\le1\)，并设 \(n\) 充分大（依赖于 \(\mu\)）。设 \(v=(v_1,\dots,v_n)\) 取值于某奇素数 \(p\) 的 \(Z_p\) 中的一个加性集合 \(S\) 内。证明对任意偶整数 \(k\ge2\) 与 \(x\in Z\)， \[\mathbb P\!\left(X_v^{(\mu)}=x\right)\le O_k\!\left(\mu^{-1/2}n^{-2k-\frac12}\|S\|_{2k}^{(2k)}\sum_{j\in S}m_j^2\right),\] 其中 \(m_j\) 为 \(j\) 在 \(v\) 中出现的次数，\(\|\cdot\|_{2k}^{(2k)}\) 常数由定义 4.26 给出。特别地，若 \(v_j\) 互不相同，则 \[\mathbb P\!\left(X_v^{(\mu)}=x\right)\le O_k\!\left(\mu^{-1/2}n^{-(2k+1)/2}\|S\|_{2k}^{(2k)}\right).\] 于是 \(X_v^{(\mu)}\) 只有在 \(v\) 的支撑集的 \(\Lambda(p)\) 常数很大时才能显著集中。
  8. 7.2.8　[167] 设 \(0<\mu\le1\)，\(n\) 充分大（依赖于 \(\mu\)）。设 \(v_1,\dots,v_n\) 是非零整数，\(k\ge2\) 为偶整数。推广推论 7.16，证明对任意 \(x\in Z\)， \[\mathbb P\!\left(X_v^{(\mu)}=x\right)\le O_k\!\left(\mu^{-1/2}n^{-2k-\frac12}R_k\right),\] 其中 \(R_k\) 是方程 \[\varepsilon_1 v_{i_1}+\cdots+\varepsilon_{2k}v_{i_{2k}}=0\] 的解的个数。

1. 事实上，一个有用的启发式是把 \(X_{v^k}^{(\mu)}\) 想成（差常数倍意义下）类似于等差数列 \([-\sqrt{\mu k},\,\sqrt{\mu k}]\cdot v\) 上的均匀分布；注意这一启发式有切尔诺夫（Chernoff）不等式支撑。

2. 严格说来，这里应写成 \[\mathbb P_{Z_p}\bigl(m\{\xi:G(\xi)>\alpha\}\bigr)\ge\max\bigl(m\,\mathbb P_{Z_p}(\{\xi:F(\xi)>\alpha\})-(m-1)/p,\,1\bigr),\] 因为柯西–达文波特不等式只蕴含 \(|A+B|\ge\min\{|A|+|B|-1,\,p\}\)（对 \(Z_p\) 的任意子集 \(A,B\)）。然而由于可以取 \(p\) 任意大，\((m-1)/p\) 这一项可以忽略。

返回 全书目录