Tusnády 问题导读

导言

这份导读回答三个问题

论文的主结论只有一行：平面上轴平行矩形的组合差异度是 $\Theta(\log^{3/2} n)$ 。围绕它有三个问题，全文按这个顺序展开。

之前为什么不行

旧的下界方法都停在 $\log n$ 。第二部分逐个说明它们是怎么工作的，天花板在哪里。

这次为什么可以

论文换了问法：点随机撒；先固定一种染色，证明它“染得好”的概率小到 $e^{-cn}$ ，再把 $2^n$ 种染色一并排除。第三部分讲这个转换。

有什么新技术

一个叫“局部振荡”的量。在好层上，横向细分一级、纵向合并一级，会带来正的条件期望增益。固定已经揭示的信息，只改变一个点的下一位横坐标数字，新势函数只变一点点。第四部分给出完整推导。

需要的预备知识

全文只假设大二水平：求和与不等式，指数和对数，概率、期望与独立性。条件期望、Cauchy–Schwarz 不等式这样的工具，第一次出现时都有一个标着“工具”的方框把它讲清楚，并给出证明。标着“推导”的折叠块是完整证明，默认展开；标着“选读”的块可以跳过，不影响主线。每节标题上方标了难度：入门、进阶、核心推导。

全景：五句话的证明

第 8 节在单位正方形里随机撒

n

个点。固定一种染色

\chi

，记

F_\chi(x,y)

为锚定矩形

[0,x]\times[0,y]

里的颜色和。只要“

F_\chi

处处都小”的概率比

2^{-n}

小得多，就能用并集界一次排除全部

2^n

种染色。

第 11–12 节把正方形按

b

进制切开。第

j

阶段，横向区间宽

b^{-j}

，纵向的块高

b^{j-h}

。对每个横向区间取两个端点处的平均

a_I(y)

，量它在每个块里的最大值减最小值，再对所有区间和块取平均，得到

Z_j

。有

Z_j\ge0

和

Z_j\le2\max|F_\chi|

2 max ∣ F_{χ} ∣

。

第 13–15 节横向细分一级、纵向合并一级，叫过一层，一共

h

层。在每个“比较矩形”里，细分之后的振荡之和平均不降，而且多出一截，至少是

\frac14\sqrt{m_R}

，

m_R

是比较矩形的内部区域里的点数。另一方面，改动一个点的下一位数字，

Z

至多变

\frac1M

，其中

M

是每层比较矩形的个数。

第 16–17 节把

Z

的总涨幅拆成各层的“条件增益”和一个“波动项”。只要点摊得开，一层的条件增益至少是

\sqrt{n/M}

的常数倍，

\frac nM

是一个比较矩形里的平均点数；

h

层上点都摊得开，这件事以极高的概率成立，而且与染色无关。波动项是大的负数的概率，由有界差分不等式控制，小到乘上

2^n

之后仍然很小。

第 18 节取层数

h

为

\log n

的量级、

\frac nM

为

h

的量级。于是除了概率至多

e^{-An}

的例外，每种染色都有

\max|F_\chi|>\frac h{64b^{3/2}}\sqrt{n/M}

\frac{h}{64 b ^{3/2}} n / M

，这是

h^{3/2}

也就是

\log^{3/2}n

的量级。

这些记号后面都会定义，第一遍只需要看个大意。

这份导读依据作者提供的论文 r65 版撰写。第四部分逐节对应论文第 2 节的证明：式 (1)–(18)、引理 2.1 和 2.3–2.6、Fact 2.2、命题 2.7，以及附录的 Fact A.1，编号都与 r65 版一致。论文的证明写得很紧凑，这里补上了省略的步骤，并加了例子和交互图；第 20 节有论文的四步概括和各节的对应。导读里补充的推导、例子和交互演示不能代替形式化验证，也不能代替独立的审阅。所有结论以论文为准；标明“背景”的内容来自相关文献，不在论文正文里。

Part I · 第 1–3 节

问题

先把问题本身弄清楚：染色游戏怎么玩，一维为什么容易，二维难在哪里，以及“ $\log^{3/2} n$ ”这样的记号到底在说什么。

§ 1 · 入门一个染色游戏

平面上有 $n$ 个点。你的任务是把每个点染成红色或蓝色。染完之后，对手可以任选一个边与坐标轴平行的矩形，数一数矩形里红点比蓝点多几个，或者少几个。这个差的绝对值就是你的损失。

你想让损失尽量小，而且颜色必须在对手挑矩形之前定好。所以一种染色的好坏，要看它在最坏的那个矩形上的表现。

多试几组点会发现两件事。第一，点数很少时，最优值通常只有 1 或 2。第二，随手染的颜色往往离最优差得不少。整篇论文关心的问题是：点数 $n$ 很大时，这个最优值最坏会有多大。

为了方便计算，以后把红色记作 $+1$ ，蓝色记作 $-1$ 。矩形里“红点数减蓝点数”就是矩形内所有点的颜色之和。

§ 2 · 入门从一维到二维

一维：交替染色就够了

先看简单的情形。如果所有点都在一条直线上，“矩形”就退化成区间。把点从左到右排好，红蓝交替地染。

一个区间里的点在排序中是连续的一段。连续一段交替的

\pm1

相加，结果只能是

-1

、

0

或

+1

。

一维的答案热身

直线上任意 $n\ge1$ 个点，按顺序交替染色后，每个区间里的颜色之和的绝对值不超过 $1$ 。所以一维情形的差异度恒为 $1$ ，与 $n$ 无关。

二维：只按一个坐标交替不够

二维的点有两个顺序：按 $x$ 坐标排一次，按 $y$ 坐标排一次。如果只按 $x$ 坐标交替染色，那么每个竖直的条带都很平衡，但水平条带可能很糟。上面的游乐场里有一个“特制点集”按钮：它把 $x$ 顺序中排奇数位的点都放在下半部分，偶数位的都放在上半部分。这时按 $x$ 交替染色，下半个正方形里就全是红点。

更麻烦的是，矩形同时对 $x$ 和 $y$ 提要求。落在一个矩形里的点，在 $x$ 顺序里不一定连续，在 $y$ 顺序里也不一定连续。一维那个“连续一段”的论证完全用不上。

Tusnády 当年问的就是：二维能不能也做到某个与 $n$ 无关的常数。Beck 在 1981 年给出了否定的回答，同时证明差异度至多是 $\log^4 n$ 量级。从那以后，问题变成了确定它的准确增长速度。

只看“锚定矩形”就够了

先把点集平移到第一象限，让所有坐标都是正的。左下角固定在原点的矩形 $A(x,y)=[0,x]\times[0,y]$ 叫锚定矩形。它只有两个参数，比一般矩形好处理得多。而且只看锚定矩形最多损失 4 倍。

左下角那块被减了两次，所以要加回一次。这就是容斥原理。

用式子写出来：对矩形 $R=(x_1,x_2]\times(y_1,y_2]$ 和任意染色 $\chi$ ，

\begin{aligned}\chi(P\cap R)={}&\chi\bigl(P\cap A(x_2,y_2)\bigr)-\chi\bigl(P\cap A(x_1,y_2)\bigr)\\&-\chi\bigl(P\cap A(x_2,y_1)\bigr)+\chi\bigl(P\cap A(x_1,y_1)\bigr).\end{aligned}

右边四项每一项的绝对值都不超过“锚定矩形上的最大差”，所以一般矩形上的差至多是它的 4 倍。反过来，锚定矩形本身就是矩形。因此两种定义下的差异度只差一个不超过 4 的常数因子，研究增长速度时可以只看锚定矩形。论文的下界甚至直接对锚定矩形成立。

§ 3 · 入门记号与增长速度

三层的 min 和 max

设 $P$ 是平面上的有限点集。一个染色是函数 $\chi:P\to\{+1,-1\}$ ${+ 1, - 1}$ 。对平面上的集合 $R$ ，记

\chi(P\cap R)=\sum_{p\in P\cap R}\chi(p).

点集 $P$ 的差异度，和 $n$ 个点的最坏差异度，定义为

\disc(P)=\min_{\chi}\ \max_{R}\ \bigl|\chi(P\cap R)\bigr|,\qquad \Delta_2(n)=\max_{|P|=n}\disc(P),

其中 $R$ 取遍所有轴平行矩形。下标 2 表示平面。这三层可以读成一场三步的博弈：

max对手先选

n

个点的位置，想让你难办。

min你看到点之后选染色

\chi

，想让最坏的矩形也平衡。

max对手看到染色之后选矩形

R

，挑差最大的那个。

易错

证明上界和证明下界是两种完全不同的任务，后面会反复用到这个区别。

上界 $\Delta_2(n)\le K$ $K$ ：对每一个 $n$ 点集，都要找出一种染色，使所有矩形的差不超过 $K$ 。

下界 $\Delta_2(n)> K$ $K$ ：要找出一个 $n$ 点集，使每一种染色都有某个矩形的差超过 $K$ 。染色有 $2^n$ 种，要一个不漏地全部排除。

渐近记号

我们关心的是 $n\to\infty$ 时的增长速度，不关心常数倍。三个记号的意思是：

$f(n)=O(g(n))$ $O (g (n))$ ：存在常数 $C$ ，使 $n$ 足够大时 $f(n)\le C\,g(n)$ $C g (n)$ 。读作“至多是 $g$ 的量级”。
$f(n)=\Omega(g(n))$ $Ω (g (n))$ ：存在常数 $c>0$ $0$ ，使 $n$ 足够大时 $f(n)\ge c\,g(n)$ $c g (n)$ 。读作“至少是 $g$ 的量级”。
$f(n)=\Theta(g(n))$ $Θ (g (n))$ ：以上两条同时成立，量级完全确定。

另外， $\log^{3/2}n$ 是 $(\log n)^{3/2}$ 的简写。对数取什么底不影响量级，因为换底只差常数倍。需要具体数值的地方，会写明用的是以 2 为底的 $\log_2$ 还是自然对数 $\ln$ 。

从数值上看，两者只差 $\sqrt{\log_2 n}$ 倍：一百万个点时大约是 4.5 倍。和随机染色能保证的 $\sqrt{n\log n}$ 相比，两者都小得可怜。但数学上要问的是真实的增长速度到底是哪一个，这不能靠“差不多”来回答。

本文的结论论文 Corollary 1.2，由 Theorem 1.1 和 Nikolov 的上界推出

存在常数 $c>0$ $0$ ，使得对每个 $n\ge1$ 有 $\Delta_2(n)\ge c\log^{3/2}n$ $c lo g^{3/2} n$ 。结合已知的上界， $\Delta_2(n)=\Theta(\log^{3/2}n)$ $Θ (lo g^{3/2} n)$ 。

论文实际证明的是一个更强的说法：随机撒的点集几乎总是这么难染。准确的表述在第 8 节。

Part II · 第 4–7 节

之前知道什么，为什么卡住

上界一路从 $\log^4 n$ 降到 $\log^{3/2}n$ ，下界却一直停在 $\log n$ 。这一部分把两边的方法都过一遍，重点看下界的几种工具各自停在哪里，为什么。

§ 4 · 入门上下界的历史

这一部分是背景材料。论文只在引言和第 3 节里各用一段话概括了这些工作；这里的推导取自标准文献，个别地方是这份导读补充的，会在出现的地方注明。

上界和下界是用两套完全不同的工具分别推进的。把已知结果画在一张图上，纵轴是 $\log n$ 的指数。

表格视图（论文 Table 1）

界	出处	年份	备注
$O(\log^4 n)$	Beck	1981
$O(\log^{3.5+\varepsilon} n)$	Beck	1989	对每个固定的 $\varepsilon>0$
$O(\log^3 n)$	Bohus	1990
$O(\log^{2.5} n)$	Srinivasan	1997
$O(\log^2 n)$	Bansal–Garg	2017	构造性的，能给出算法
$O(\log^{3/2} n)$	Nikolov	2017
$\Omega(\log n)$	Schmidt	1972	经转移原理得到
$\Omega(\log n)$	Matoušek–Nikolov	2015	分解范数； $d$ 维是 $\Omega(\log^{d-1}n)$
$\Omega(\log^{3/2} n)$	本文		随机点即可达到

图里能读出三件事。

上界那条线一级一级往下降，最后在 2017 年到达 $\log^{3/2}n$ 。
下界那条线一直是平的。Schmidt 1972 年的定理说的是连续差异度，要经过第 6 节的转移原理才变成染色问题的下界。2015 年换了一种全新的方法，得到的仍然是 $\log n$ 。
于是剩下一个 $\sqrt{\log n}$ 的缺口。哪一边是对的，事先并不清楚：论文提到，Bansal 在 2022 年国际数学家大会的报告里猜想下界 $\log n$ 才是对的。论文的结论是另一边：上界 $\log^{3/2}n$ 是对的。Bansal 和 Nikolov 2026 年的综述也讨论了平面上剩下的这个缺口。

缺口两头都有道理。 $\log n$ 是另一个经典问题（连续差异度，见第 6 节）的正确答案。 $\log^{3/2}n$ 则是最好的染色方法做到的。到底是染色方法还能改进，还是下界的证明不够强，一直没有定论。

§ 5 · 进阶上界从哪来

本文证明的是下界。但上界的想法里有一个结构，下界的证明里会再遇到：把问题拆成 $\log n$ 层尺度，每一层付一份代价。所以值得先看一眼。

最朴素的办法：随机染色

每个点独立地抛硬币决定颜色。这样能做到什么程度？需要三个概率工具，其中 Markov 不等式和并集界后面还会再用。

工具 · Markov 不等式

设随机变量 $X\ge0$ $0$ ， $a>0$ $0$ 。则 $\Pr[X\ge a]\le \EE[X]/a$ $E [X] / a$ 。

证明只有一行： $\EE[X]\ge \EE\bigl[X\cdot\one_{\{X\ge a\}}\bigr]\ge a\cdot\Pr[X\ge a]$ $a]$ 。意思是，一个非负的量如果平均值很小，它就不太可能很大。

工具 · 并集界

对任意事件 $E_1,\dots,E_N$ ，有 $\Pr[E_1\cup\dots\cup E_N]\le\sum_i\Pr[E_i]$ $\sum_{i} Pr [E_{i}]$ 。“至少发生一件坏事”的概率，不超过各件坏事概率之和。证明：并集的示性变量不超过各事件示性变量之和，两边取期望。

工具 ·

\pm1

之和的尾概率

设 $S=\eps_1+\dots+\eps_s$ $ϵ_{s}$ ，各 $\eps_i$ 独立，等概率取 $\pm1$ 。则对任意 $a>0$ $0$ ， $\Pr[\,|S|\ge a\,]\le 2e^{-a^2/(2s)}$ $2 e^{- a^{2} / (2 s)}$ 。

推导尾概率的证明

对任意 $t>0$ $0$ ，由独立性， $\EE[e^{tS}]=\prod_i\EE[e^{t\eps_i}]=(\cosh t)^s$ $(cosh t)^{s}$ ，其中 $\cosh t=\tfrac12(e^t+e^{-t})$ $e^{- t})$ 。
逐项比较幂级数： $\cosh t=\sum_{k\ge0}\dfrac{t^{2k}}{(2k)!}$ $\sum_{k \geq 0} \frac{t ^{2 k}}{( 2 k )!}$ ， $e^{t^2/2}=\sum_{k\ge0}\dfrac{t^{2k}}{2^k\,k!}$ $\sum_{k \geq 0} \frac{t ^{2 k}}{2 ^{k} k !}$ 。因为 $(2k)!=k!\cdot(k+1)(k+2)\cdots(2k)\ge k!\cdot2^k$ $2^{k}$ ，所以 $\cosh t\le e^{t^2/2}$ $e^{t^{2} /2}$ 。
对非负随机变量 $e^{tS}$ 用 Markov 不等式： $\Pr[S\ge a]=\Pr[e^{tS}\ge e^{ta}]\le e^{-ta}\,\EE[e^{tS}]\le e^{st^2/2-ta}$ $e^{s t^{2} /2 - t a}$ 。
取 $t=a/s$ $a / s$ ，指数变成 $-a^2/(2s)$ 。由对称性 $\Pr[S\le -a]$ 有同样的界，两者相加得结论。

现在固定一个 $n$ 点集和一个矩形 $R$ 。 $R$ 里有 $s\le n$ 个点，随机染色下 $\chi(P\cap R)$ 正是 $s$ 个独立 $\pm1$ 之和。取 $a=\sqrt{10\,n\ln n}$ $10 n ln n$ ，

\Pr\bigl[\,|\chi(P\cap R)|\ge a\,\bigr]\le 2e^{-a^2/(2n)}=2n^{-5}.

矩形虽然有无穷多个，但它们截出的点子集是有限的：子集由“ $x$ 顺序中的哪一段”和“ $y$ 顺序中的哪一段”决定，至多 $\bigl(\tfrac{n(n+1)}2\bigr)^2\le n^4$ 种。由并集界，存在某个矩形超标的概率至多 $n^4\cdot2n^{-5}=2/n$ $2/ n$ ，当 $n\ge3$ 时小于 1。所以一定有一种染色让所有矩形都不超标：

\Delta_2(n)\le\sqrt{10\,n\ln n}\qquad(n\ge3).

这个界离真相差得很远，真相是 $\log n$ 的幂次。但这段推导展示了一种基本手法：用概率证明存在性。第三部分会把同样的手法反过来用。

把前缀拆成二进区间

要做到 $\log n$ 的幂次，需要利用矩形的结构。把 $x$ 方向分成 $m=2^h$ 列。长度为 $2$ 的幂、位置对齐的区间叫二进区间：第 0 层是整个 $[1,m]$ ，第 1 层是左右两半，一直到第 $h$ 层的单独一列。

有两个事实，后面都会用到：

每一列恰好属于 $h+1$ 个二进区间，每层一个。
每个前缀 $[1,v]$ 都能写成至多 $h+1$ 个互不相交的二进区间的并，每层至多一个。这其实就是 $v$ 的二进制展开。

于是一个锚定矩形（宽度是前缀 $[1,v]$ ，高度到某处为止）可以拆成至多 $h+1$ 个“二进条带”。如果一种染色能让每个二进条带内部的误差都不超过 $E$ ，那么锚定矩形的误差就不超过 $(h+1)E$ $1) E$ 。每个条带单独看是个一维问题，容易。困难在于同一种染色要同时照顾全部 $h+1$ 层。

历史上的上界大多沿着“分层”的思路走。早期的证明用的是部分染色的想法：每一轮只给一部分点定色，同时控制一族标准矩形上的误差，剩下的点留到下一轮。每一轮、每一层尺度都有损失，所以得到的是 $\log n$ 的高次幂。后来的改进主要是在减少这些损失。

目前最好的上界

Nikolov 在 2017 年证明了 $\Delta_2(n)=O(\log^{3/2}n)$ $O (lo g^{3/2} n)$ 。证明依赖 Banaszczyk 的一个深刻定理，定理本身远超大二水平，这里把它当作黑箱，只看它怎么和二进分解搭配。

选读从 Banaszczyk 定理到

O(\log^{3/2}n)

的骨架

Banaszczyk 定理（前缀和版本）背景 · 2012

设 $v_1,\dots,v_n\in\R^d$ 的长度都不超过 1， $\mathcal K\subset\R^d$ 是关于原点对称的凸体，并且一个标准高斯随机向量落在 $\mathcal K$ 里的概率至少是 $1-\frac1{2n}$ $\frac{1}{2 n}$ 。则存在符号 $\eps_i\in\{\pm1\}$ ${\pm 1}$ ，使所有前缀和 $\sum_{i\le u}\eps_iv_i$ （ $u=1,\dots,n$ $1, \dots, n$ ）都落在 $5\mathcal K$ 里。

把点按高度排成 $p_1,\dots,p_n$ ，记 $r_i$ 为 $p_i$ 在 $x$ 方向的名次。锚定矩形上的颜色和是 $A(u,v)=\sum_{i\le u,\ r_i\le v}\eps_i$ $\sum_{i \leq u, r_{i} \leq v} ϵ_{i}$ 。
取 $h=\lceil\log_2n\rceil$ $⌈ lo g_{2} n ⌉$ ，把名次 $1,\dots,2^h$ 当作列。给每个点一个向量 $v_i$ ，坐标用二进区间 $I$ 编号：若 $r_i\in I$ $I$ ，该坐标是 $1/\sqrt{h+1}$ ，否则是 0。每个点恰在 $h+1$ 个二进区间里，所以 $\norm{v_i}=1$ $1$ 。
对每个 $v$ ，令 $b_v$ 为前缀 $[1,v]$ 的二进分解的示性向量，它至多有 $h+1$ 个 1。分解是不相交的，所以 $\ip{b_v}{v_i}=\one_{\{r_i\le v\}}/\sqrt{h+1}$ $1_{{r_{i} \leq v}} / h + 1$ 。
取 $\mathcal K=\{y:\ |\ip{b_v}{y}|\le t\ \text{对}\ v=1,\dots,n\}$ $1, \dots, n}$ ，它是关于原点对称的凸集（严格地说要限制在这些 $b_v$ 张成的子空间里才有界，这不影响论证）。对高斯向量 $g$ ， $\ip{b_v}{g}$ 服从方差不超过 $h+1$ 的正态分布，所以 $\Pr[|\ip{b_v}{g}|>t]\le2e^{-t^2/(2(h+1))}$ $2 e^{- t^{2} / (2 (h + 1))}$ 。对这 $n$ 个 $v$ 用并集界，取 $t=\sqrt{2(h+1)\ln(4n^2)}$ 就满足定理的条件。
定理给出的符号满足 $\bigl|\sum_{i\le u}\eps_i\ip{b_v}{v_i}\bigr|\le5t$ $5 t$ ，也就是 $|A(u,v)|\le5t\sqrt{h+1}=5(h+1)\sqrt{2\ln(4n^2)}=O(\log^{3/2}n).$

两个因子的来源很清楚： $h+1\approx\log n$ 来自二进分解的层数， $\sqrt{\log n}$ 来自要求 $n$ 个约束同时成立。原文处理的是一般维数，用的是分解范数的语言，细节以原文为准。

上界的故事到这里停住了。它留下一个印象：有 $\log n$ 层，每层要多付 $\sqrt{\log n}$ 。本文证明的是，这个代价一分也省不掉。

§ 6 · 进阶下界从哪来：连续差异度与转移原理

一个更老的问题：点放得均不均匀

不染色，只问：在单位正方形 $[0,1]^2$ 里放 $n$ 个点，怎样才算均匀。如果点是均匀的，面积为 $a$ 的矩形里应该有大约 $an$ 个点。点集 $P$ 的连续差异度定义为最坏的偏差

D(P)=\sup_{R}\ \Bigl|\,|P\cap R|-n\cdot\mathrm{area}(R)\Bigr|,\qquad D(n)=\min_{|P|=n}D(P),

其中 $R$ 取遍 $[0,1]^2$ 里的轴平行矩形。注意这里是你自己放点，所以取 $\min$ 。

网格和随机点的偏差都在 $\sqrt n$ 量级。第三种点集叫二进网，它的偏差只有 $\log n$ 量级。下面把这个结论推出来，因为推导里又出现了“ $\log n$ 层，每层贡献常数”的结构。

二进网：每层误差不超过 1

设 $N=2^s$ $2^{s}$ 。把整数 $i\in\{0,\dots,N-1\}$ 写成 $s$ 位二进制，再把这 $s$ 位倒过来读成一个二进制小数，记作 $\varphi(i)$ 。例如 $s=3$ 时 $i=6=(110)_2$ $(110)_{2}$ ， $\varphi(6)=(0.011)_2=3/8$ $3/8$ 。点集取为

P=\bigl\{\,(i/N,\ \varphi(i))\ :\ i=0,1,\dots,N-1\,\bigr\}.

网性质背景 · Hammersley 点集

设 $p+q=s$ $s$ 。每个形如 $\bigl[\frac a{2^p},\frac{a+1}{2^p}\bigr)\times\bigl[\frac b{2^q},\frac{b+1}{2^q}\bigr)$ 的盒子（面积恰为 $1/N$ ）里恰好有 $P$ 的一个点。

推导网性质，以及

D(P)\le 4(\log_2N+1)

网性质。 $i/N$ 落在第一个区间里，等价于 $i$ 的最高 $p$ 位是 $a$ 的二进制。 $\varphi(i)$ 落在第二个区间里，等价于 $\varphi(i)$ 的前 $q$ 位小数是 $b$ 的二进制，也就是 $i$ 的最低 $q$ 位被确定。 $p+q=s$ $s$ ，所以 $i$ 的全部 $s$ 位都被确定，恰有一个 $i$ 。
拆分。考虑锚定矩形 $[0,X)\times[0,Y)$ $[0, Y)$ 。由二进制展开， $[0,X)$ 可以拆成至多 $s$ 个互不相交的二进区间（长度是互不相同的 $2^{-p}$ ， $1\le p\le s$ $s$ ），外加一段长度小于 $1/N$ 的零头。 $X=1$ 时它就是 $[0,1)$ 这一个区间。
每个二进条带。设 $I$ 是长度 $2^{-p}$ 的二进区间。横坐标在 $I$ 里的点有 $2^{s-p}$ 个。由网性质（取 $q=s-p$ $p$ ），它们的纵坐标在每个 $\bigl[\frac b{2^q},\frac{b+1}{2^q}\bigr)$ 里恰有一个。所以 $I\times[0,Y)$ 里的点数在 $\lfloor Y2^q\rfloor$ 和 $\lceil Y2^q\rceil$ 之间，而“应有的点数”是 $N\cdot2^{-p}\cdot Y=Y2^q$ $Y 2^{q}$ 。误差不超过 1。
零头。横坐标都是 $1/N$ 的倍数，长度小于 $1/N$ 的区间里至多一个点，应有点数小于 1。误差不超过 1。
合计。锚定矩形的偏差至多 $s+1=\log_2N+1$ $1$ 。一般矩形是四个锚定矩形的加减，所以 $D(P)\le4(\log_2N+1)$ $1)$ 。

任意点数。对任意 $n\ge2$ ，取点 $(i/n,\varphi(i))$ ，其中 $0\le i<n$ ， $\varphi$ 把 $i$ 的二进制数字倒序写成小数（前导零不影响结果）。锚定矩形选中的横坐标构成前 $k$ 个指标，且 $|k-nX|\le1$ 。把这段指标分成长度为 2 的幂、起点与长度对齐的块，至多需要 $\lfloor\log_2 n\rfloor+1$ 块。每一块的倒序数字在等长二进纵区间里各放一个点，所以计数误差至多为 1。把各块误差与 $|k-nX|Y\le1$ 相加，就对任意 $n$ 得到 $O(\log n)$ ；一般矩形再付至多四倍。

反方向是 Schmidt 在 1972 年证明的定理：无论怎么放点， $D(n)\ge c\log n$ $c lo g n$ 。它的证明这里不展开。两者合起来，连续差异度的答案完全确定：

D(n)=\Theta(\log n).

只看锚定矩形的版本是 $\sup_{x,y}\bigl|\,|P\cap([0,x]\times[0,y])|-nxy\,\bigr|$ $n x y$ ，它的最小值同样是 $\Theta(\log n)$ 。把它除以 $n$ ，就是常说的星差异度，最优量级是 $(\log n)/n$ 。

转移原理：好染色能造出均匀点集

连续差异度和组合差异度之间有一座桥，叫转移原理。它的证明是初等的，而且很有意思：反复染色、只留红点。

转移原理（简化形式）背景 · 标准论证的简化版，常数由本导读给出

对所有 $n\ge2$ $2$ ，有 $D(n)\le2\,\Delta_2(2n^2)+5$ $5$ 。也就是说，如果任何点集都能染得很平衡，就一定存在很均匀的点集。

旧的偏差每步减半，新引入的偏差就是那一步染色的差异度。

推导转移原理的证明

减半。设 $P$ 有 $N$ 个点（ $N$ 为偶数）， $\chi$ 是一种染色，所有矩形上 $|\chi(P\cap R)|\le f$ $f$ 。令 $P^+$ 为红点的集合。对每个矩形 $R$ ，红点数是 $|P^+\cap R|=\frac12\bigl(|P\cap R|+\chi(P\cap R)\bigr)$ $R))$ ，所以 $\Bigl|\,|P^+\cap R|-\tfrac12|P\cap R|\,\Bigr|\le\tfrac f2.$ 取 $R$ 为整个正方形，得 $\bigl||P^+|-\frac N2\bigr|\le\frac f2$ $\frac{f}{2}$ 。
修正点数。 $P^+$ 的点数可能不恰好是 $N/2$ ，但只差至多 $f/2$ 个。删掉或补上这么多点，得到恰有 $N/2$ 个点的 $P'$ 。每动一个点，任何矩形里的点数至多变 1，所以 $\bigl||P'\cap R|-\frac12|P\cap R|\bigr|\le f$ $f$ 。
连续差异度的递推。由三角不等式， $\begin{aligned}\Bigl|\,|P'\cap R|-\tfrac N2\,\mathrm{area}(R)\Bigr|&\le\Bigl|\,|P'\cap R|-\tfrac12|P\cap R|\,\Bigr|+\tfrac12\Bigl|\,|P\cap R|-N\,\mathrm{area}(R)\Bigr|\\&\le f+\tfrac12D(P).\end{aligned}$ 对 $R$ 取上确界： $D(P')\le\frac12D(P)+f$ $f$ 。
$\Delta_2$ 关于点数单调不减。在一个点集的远处再添一个点，原来的每个矩形都可以缩小一点避开新点，所以差异度不会变小。
迭代。取 $k=\lceil\log_2n\rceil$ $⌈ lo g_{2} n ⌉$ ，从 $N_0=2^kn$ 个点的 $P_0$ 出发做 $k$ 次减半， $P_j$ 有 $2^{k-j}n$ 个点。因为 $2^k<2n$ $2 n$ ，每个 $P_j$ 的点数都小于 $2n^2$ ，所以每一步都能找到差异度不超过 $f=\Delta_2(2n^2)$ 的染色。把递推展开， $D(P_k)\le\frac{D(P_0)}{2^k}+f\cdot\Bigl(1+\frac12+\frac14+\dots\Bigr)\le\frac{D(P_0)}{2^k}+2\,\Delta_2(2n^2).$
起点。取 $P_0$ 为一个 $\lceil\sqrt{N_0}\rceil\times\lceil\sqrt{N_0}\rceil$ 的网格去掉多余的点。直接数格点可得 $D(P_0)\le5\sqrt{N_0}$ $5 N_{0}$ 。于是 $D(P_0)/2^k\le5\sqrt{n/2^k}\le5$ $5$ ，因为 $2^k\ge n$ $n$ 。
结论。 $P_k$ 恰有 $n$ 个点，所以 $D(n)\le D(P_k)\le2\,\Delta_2(2n^2)+5$ $5$ 。

把它和 Schmidt 定理 $D(n)\ge c\log n$ 放在一起，得到 $\Delta_2(2n^2)\ge\frac12(c\log n-5)$ $5)$ 。再用一次单调性，对所有 $N$ 都有 $\Delta_2(N)=\Omega(\log N)$ $Ω (lo g N)$ 。这就是经典下界的来源。

天花板

这条路线的逻辑是“组合差异度不会比连续差异度小”。可是连续差异度恰好就是 $\Theta(\log n)$ ，二进网已经做到了。所以单靠这条路线，证不出比 $\log n$ 更大的下界。

转移原理是单向的：好染色能造出均匀点集，但均匀点集的存在不保证有好染色。本文的结论正说明两者确实不同：平面上组合差异度比连续差异度大一个 $\sqrt{\log n}$ 因子。

§ 7 · 进阶其他下界工具，和它们停下的地方

除了转移原理，还有两类方法给出过 $\Omega(\log n)$ 。它们的思路相近：对每一种染色，用同一套办法给出“存在坏矩形”的证据。

正交函数法

这是 Roth 在 1954 年引入的方法。把偏差写成正方形上的函数 $D(x,y)$ ，再找一个检验函数 $F$ ，使内积 $\ip{D}{F}=\iint DF$ 很大而 $F$ 本身不大。由 Cauchy–Schwarz 不等式， $D$ 的平方平均就不可能小。检验函数用 Haar 函数拼成：每个二进盒子上放一个取值 $\pm1$ 的小波，不同形状的盒子给出互相正交的函数。

选读Roth 定理的完整推导：

D(N)\ge\frac1{128}\sqrt{\log_2N}

设 $P\subset[0,1)^2$ 有 $N$ 个点， $D(x,y)=\#\bigl(P\cap[0,x)\times[0,y)\bigr)-Nxy$ $N x y$ 。

尺度。取整数 $n$ 使 $2N\le2^n<4N$ $4 N$ 。对每个 $r=(r_1,r_2)$ $(r_{1}, r_{2})$ ， $r_1+r_2=n$ $n$ ，把正方形切成 $2^n$ 个大小为 $2^{-r_1}\times2^{-r_2}$ 的二进盒子，每个面积 $2^{-n}$ 。这样的 $r$ 共有 $n+1$ 个。
Haar 函数。对区间 $I$ ，令 $h_I$ 在左半取 $+1$ ，右半取 $-1$ ，区间外为 0。对盒子 $R=I\times J$ $J$ ，令 $h_R(x,y)=h_I(x)h_J(y)$ $h_{I} (x) h_{J} (y)$ 。
空盒子上的内积。直接积分， $\int_I x\,h_I(x)\,dx=-|I|^2/4$ $- ∣ I ∣^{2} /4$ ，所以 $\iint Nxy\,h_R=N|R|^2/16$ $N ∣ R ∣^{2} /16$ 。另一方面，如果 $R$ 里没有 $P$ 的点，那么每个点 $p$ 的计数函数 $\one_{\{p_x<x\}}\one_{\{p_y<y\}}$ 在 $R$ 上至少对一个变量是常数，而 $h_I$ 、 $h_J$ 的积分都是 0，所以计数部分与 $h_R$ 的内积为 0。于是空盒子满足 $\ip{D}{h_R}=-N|R|^2/16$ $- N ∣ R ∣^{2} /16$ 。
一层的检验函数。令 $f_r=-\sum h_R$ $- \sum h_{R}$ ，对所有类型为 $r$ 的空盒子求和。因为 $N\le2^{n-1}$ $2^{n - 1}$ ，空盒子至少有 $2^{n-1}$ 个，所以 $\ip{D}{f_r}\ge2^{n-1}\cdot\frac{N\,4^{-n}}{16}=\frac{N2^{-n}}{32}>\frac1{128},\qquad\norm{f_r}^2\le2^n\cdot2^{-n}=1.$
正交。若 $r\ne r'$ $r^{'}$ ，不妨设 $r_1<r_1'$ $r_{1}^{'}$ 。类型 $r'$ 的盒子在 $x$ 方向更窄，它的 $x$ 区间要么与 $I$ 不相交，要么整个落在 $I$ 的某一半里，此时 $h_I$ 在其上是常数，积分为 0。所以 $\ip{f_r}{f_{r'}}=0$ $0$ 。
合起来。令 $F=\sum_rf_r$ $\sum_{r} f_{r}$ 。则 $\ip{D}{F}>\frac{n+1}{128}$ $\frac{n + 1}{128}$ ， $\norm{F}^2=\sum_r\norm{f_r}^2\le n+1$ $1$ 。由 Cauchy–Schwarz， $\sup|D|\ \ge\ \norm{D}_2\ \ge\ \frac{\ip{D}{F}}{\norm{F}}>\frac{\sqrt{n+1}}{128}\ge\frac{\sqrt{\log_2N}}{128}.$

每一层 $r$ 贡献一个常数，共有 $n+1\approx\log N$ 层。在平方平均的意义下，这些贡献按“平方和开根号”合并，得到 $\sqrt{\log N}$ 。Schmidt 1972 年的定理把它提高到了 $\log N$ 。后来 Halász 在 Roth 的框架里用更精巧的检验函数重新证明了这个结果，让各层的贡献直接相加。

把同样的想法用到染色上，Wei 和 Yi 证明了二进网的组合差异度是 $\Omega(\log n)$ 。这类证明的收益是按尺度一层一层累加的：共 $\log n$ 层，每层贡献一个常数。

在第 6 节那个二进网上，这已经是能证明的极限了，因为它本身就能染得这么好。下面的验证是这份导读补充的，不在论文里，只用到第 6 节的工具。

推导第 6 节的二进网可以染到差异度

4(\log_2N+1)

染色。第 $i$ 个点 $(i/N,\varphi(i))$ 的颜色取为 $(-1)^{b(i)}$ ，其中 $b(i)$ 是 $i$ 的二进制里 1 的个数。
一个二进条带里的颜色。设 $I$ 是长度 $2^{-p}$ 的二进区间， $q=s-p$ $p$ 。横坐标在 $I$ 里的点是 $i=a\cdot2^q+j$ $j$ ， $j=0,\dots,2^q-1$ $1$ 。它们按纵坐标排序，就是按 $j$ 的 $q$ 位倒序 $r$ 排序。倒序不改变 1 的个数，所以排在第 $r$ 位的点的颜色是 $\pm(-1)^{b(r)}$ ，正负号对整个条带是同一个。
前缀和不超过 1。序列 $(-1)^{b(r)}$ ， $r=0,1,2,\dots$ $0, 1, 2, \dots$ ，是 $+,-,-,+,-,+,+,-,\dots$ 。 $b(2r+1)=b(2r)+1$ $1$ ，所以它每两项一组，每组是 $(+,-)$ 或 $(-,+)$ 。任何前缀和只能是 $-1$ 、 $0$ 或 $1$ 。
合计。条带 $I\times[0,Y)$ 里的点是这个排序的一段前缀，颜色和的绝对值不超过 1。像第 6 节那样把锚定矩形拆成至多 $s$ 个条带加一段零头，颜色和的绝对值不超过 $s+1$ $1$ 。一般矩形再乘 4。

所以，只要证明针对的是这样的点集，结论就不可能超过 $\log n$ 。要突破它，必须换一类点集。

分解范数 $\gamma_2$

第二类方法来自线性代数。把“哪个点在哪个矩形里”写成 0–1 矩阵 $A$ 。把 $A$ 分解成两个矩阵的乘积 $A=BC$ $BC$ ，定义

\gamma_2(A)=\min_{A=BC}\ \bigl(B\ \text{的最长行向量的长度}\bigr)\times\bigl(C\ \text{的最长列向量的长度}\bigr).

Matoušek、Nikolov 和 Talwar 证明，这个量从两边夹住了差异度（准确地说是“遗传差异度”：在所有子点集上取最坏的差异度。Tusnády 问题可以化成网格上的这个量）：

\frac{\gamma_2(A)}{C\log M}\le\operatorname{herdisc}(A)\le C\sqrt{\log M}\,\gamma_2(A).

其中 $M$ 是矩阵行数， $C$ 是常数。第 5 节的二进分解给出一维前缀矩阵的一个分解：最大行范数与最大列范数都至多为 $\sqrt{h+1}$ ，所以它们的乘积至多为 $h+1$ 。在含 $n$ 个点的各坐标方向等长的完整 $d$ 维乘积网格上，锚定盒子的关联矩阵满足 $\gamma_2=\Theta_d(\log^d n)$ 。下面的下界通过遗传差异度选取网格的子集，并不声称每个点集都有这个 $\gamma_2$ 值。对任意 $n$ 点集，把各坐标的秩嵌入网格，则得到所需的 $\gamma_2$ 上界。因此，固定 $d$ 时，这两个通用不等式给出

\Omega(\log^{d-1}n)\ \le\ \Delta_d(n)\ \le\ O(\log^{d+1/2}n).

天花板

左右两个不等式各带一个对数因子的损失，而且已经知道这两个损失对一般的矩阵都无法改进。对平面乘积网格， $\gamma_2\approx\log^2n$ $lo g^{2} n$ ，下界一侧除以 $\log n$ 之后正好又是 $\log n$ 。真实值 $\log^{3/2}n$ 严格落在两个界之间，这把通用的尺子量不出来。

小结：三种方法，同一个数

方法	给出的下界	停在这里的原因
连续差异度 + 转移原理	$\Omega(\log n)$	连续差异度本身就是 $\Theta(\log n)$
正交函数法	$\Omega(\log n)$	已有的论证每层只挣到常数；第 6 节的二进网本身就能染到 $O(\log n)$
分解范数 $\gamma_2$	$\Omega(\log^{d-1}n)$ ，平面即 $\log n$	通用不等式自带对数因子的损失
本文：随机点集，逐个染色估计概率	$\Omega(\log^{3/2}n)$	与上界吻合

这里回顾的具体论证有两个特点。第一，这些论证没有给出本文对随机点集的统一下界：转移原理和分解范数路线给出的坏点集藏在某个网格的子集里；前面介绍的正交函数法在组合差异度上的应用针对二进网，但该方法本身并不限于这类点集。第二，这里介绍的几种按尺度分层计算收益的论证，每层挣到的都是常数， $\log n$ 层合计 $\log n$ 。本文两点都换掉了：点是随机的，每层尺度挣到的是 $\sqrt{\log n}$ 的量级。证明的骨架仍然是一层一层地挣，这一点和正交函数法一脉相承。不同的是每一层挣多少，以及怎样保证对全部 $2^n$ 种染色同时成立。

Part III · 第 8–10 节

换一个问法

不去构造坏点集，而是随机撒点，再证明每一种染色都几乎不可能染好。这一部分讲这个转换、它对概率估计提出的要求，以及后面一直要用的一个小工具：把随机数一位一位地揭示出来。

§ 8 · 入门随机撒点，一次对付一种染色

第 3 节强调过，下界要排除全部 $2^n$ 种染色。上面介绍的经典论证没有给出本文这种对随机点集、同时适用于全部染色的下界。论文换了一种安排：

点集不构造。在单位正方形

[0,1]^2

里独立、均匀地撒

n

个点

P_1,\dots,P_n

，记

P_i=(U_i,V_i)

(U_{i}, V_{i})

。

染色给第

i

个点指定颜色

\chi_i\in\{+1,-1\}

{+ 1, - 1}

。一种染色就是一个向量

\chi=(\chi_1,\dots,\chi_n)

(χ_{1}, \dots, χ_{n})

，一共

2^n

个。颜色是按点的编号指定的，撒点之前就定好了。

目标对每一个固定的

\chi

，证明“这种染色在所有锚定矩形上都很平衡”的概率小得出奇。

把锚定矩形 $[0,x]\times[0,y]$ 里的颜色和写成一个二元函数：

F_\chi(x,y)=\sum_{i=1}^n\chi_i\,\one_{\{U_i\le x,\ V_i\le y\}}.

这里 $\one_{\{\cdots\}}$ 是示性函数：条件成立时取 1，否则取 0。再记 $\norm{F_\chi}_\infty=\max_{0\le x,y\le1}\abs{F_\chi(x,y)}$ $max_{0 \leq x, y \leq 1} ∣ F_{χ} (x, y)∣$ ，它就是这种染色在锚定矩形上的最大差。论文的主定理是下面这句话。

定理 1.1（随机点）论文 Theorem 1.1

对每个 $A>0$ $0$ ，存在常数 $c_A>0$ $0$ ，使下面的结论对每个整数 $n\ge1$ 成立。设 $P_1,\dots,P_n$ 是 $[0,1]^2$ 中独立均匀的随机点，则

\Pr\Bigl[\ \text{对每一个}\ \chi\in\{\pm1\}^n\ \text{都有}\ \norm{F_\chi}_\infty\ge c_A(\log_2n)^{3/2}\ \Bigr]\ \ge\ 1-e^{-An}.

方括号里的事件说的是点集，不是某一种染色：这组点不管怎么染，都有一个锚定矩形的差至少是 $c_A(\log_2n)^{3/2}$ 。所以染色完全可以在看到所有点之后再挑。你挑出来的那一种也是 $2^n$ 个向量之一，结论对它照样成立。

从这个定理马上得到三件事。

坏点集存在。一个概率为正的事件不是空的，而随机撒的点以概率 1 互不相同，所以至少有一个 $n$ 点集，任何染色的差都至少是 $c_A(\log_2n)^{3/2}$ 。锚定矩形也是矩形，于是 $\Delta_2(n)\ge c\log^{3/2}n$ $c lo g^{3/2} n$ 。加上 Nikolov 的上界， $\Delta_2(n)=\Theta(\log^{3/2}n)$ $Θ (lo g^{3/2} n)$ 。
随机点集就是最坏的。不需要任何巧妙的构造，随手撒的点以极接近 1 的概率达到最坏的量级。
$A$ 可以任意大。想让失败概率是 $e^{-100n}$ 也行，只是常数 $c_A$ 会跟着变小。论文没有去优化 $c_A$ ，它非常小，所以这个界只对很大的 $n$ 有意义；第 18 节末尾给出了具体的数。

证明的两步

记 $t=c_A(\log_2n)^{3/2}$ $c_{A} (lo g_{2} n)^{3/2}$ 。证明分成两步，第一步是全文的主体。

固定染色对每一个固定的

\chi

，证明

\Pr\bigl[\norm{F_\chi}_\infty\le t\bigr]\le e^{-(A+\ln2)n}

e^{- (A + l n 2) n}

。

并集界“存在某个

\chi

染得好”是

2^n

个事件的并，所以它的概率至多是

2^n\cdot e^{-(A+\ln2)n}=e^{-An}

e^{- A n}

。

第二步只用到第 5 节的并集界，不需要这 $2^n$ 个事件之间有任何独立性。但它对第一步提了一个很高的要求：每一种染色“染得好”的概率都必须比 $2^{-n}$ 还小。如果只证到 $0.9^n$ ，乘上 $2^n$ 之后是 $1.8^n$ ，什么也说明不了。换句话说，平均每多一个点，“染得好”的概率就得不止减半。

第四部分的证明比这两步稍微精细一点。“染得好”会被拆成两个事件：一个只和点的位置有关，对所有染色是同一个事件，排除一次就够了；另一个才需要逐个染色估计，再乘 $2^n$ 。但要求没有变：逐个染色估计的那一部分，概率必须比 $2^{-n}$ 小得多。

	第 5 节的随机染色（上界）	这里（下界）
随机的是什么	染色	点的位置
固定的是什么	点集，和一个矩形	一种染色
并集界对什么用	至多 $n^4$ 个矩形	$2^n$ 种染色
每个事件的概率要多小	$n^{-5}$ 就够	必须小于 $2^{-n}$
结论	存在一种好染色	以极高的概率没有好染色

固定 $\chi$ 之后，随机性全在点的位置上：每个点带着事先指定的颜色，独立地落在正方形里均匀的一处。另外，同一个点的横坐标 $U_i$ 和纵坐标 $V_i$ 也是独立的。第 10 节会利用这一点：先把全部纵坐标看作已知，只让横坐标随机。

§ 9 · 进阶该瞄准多大： $\frac32$ 是怎么猜出来的

动手证明之前，先估一下 $t$ 最大能取到多少。这一节是启发式的计算，对应论文第 3 节里“The Brownian sheet and Talagrand's proof”那一段的前半。它不是证明的一部分，但能解释 $\frac32$ 这个指数的来历。

固定 $\chi$ ，记 $S=\sum_i\chi_i$ $\sum_{i} χ_{i}$ 。 $F_\chi(x,y)$ 是 $n$ 个独立项之和，每一项以概率 $xy$ 贡献 $\pm1$ ，否则贡献 0。它的均值是 $S\,xy$ ，围绕均值的起伏是 $\sqrt n$ 的量级。减去均值，再除以 $\sqrt n$ ，得到的过程协方差是 $\min(x,x')\min(y,y')-xy\,x'y'$ $x y x^{'} y^{'}$ 。概率论里有一张随机曲面和它很像，叫布朗单，记作 $W(x,y)$ 。它是布朗运动的二维版本： $W(x,y)$ 服从均值 0、方差 $xy$ 的正态分布，协方差是 $\min(x,x')\min(y,y')$ ，不相交的矩形上的增量相互独立。两者差的那一项 $xy\,x'y'$ ，相当于把布朗单在右上角钉住，换成 $W(x,y)-xy\,W(1,1)$ $x y W (1, 1)$ 。下面只借布朗单来猜尺度，不区分这两个过程，也不管均值那一项。

小球估计背景 · Bass 1988，Talagrand 1994

布朗单在整个正方形上都留在 $[-\varepsilon,\varepsilon]$ 里的概率满足

-\log\Pr\bigl[\norm{W}_\infty\le\varepsilon\bigr]\ \asymp\ \varepsilon^{-2}\log^3(1/\varepsilon)\qquad(\varepsilon\to0),

其中 $\asymp$ 表示两边相差不超过常数倍。左边的上界是 Bass 证明的，与之匹配的下界是 Talagrand 证明的。后面还会用到 $\gtrsim$ 和 $\lesssim$ ：不计常数倍的“至少”和“至多”。

一维的对照更容易理解。布朗运动 $B(s)$ 在 $[0,1]$ 上始终留在 $[-\varepsilon,\varepsilon]$ 里的概率大约是 $e^{-c/\varepsilon^2}$ 。理由是：把时间切成长度 $\varepsilon^2$ 的小段，每一小段里它走出 $\pm\varepsilon$ 的概率是个常数，而要连续 $1/\varepsilon^2$ 段都不出界。二维多出来的 $\log^3(1/\varepsilon)$ 没有这么简单的解释，这正是 Talagrand 定理的内容。

现在把它代进第 8 节的要求里。“ $\norm{F_\chi}_\infty\le t$ $t$ ”相当于“ $\norm{W}_\infty\le\varepsilon$ $ε$ ”，其中 $\varepsilon=t/\sqrt n$ $t / n$ 。于是猜测

\Pr\bigl[\norm{F_\chi}_\infty\le t\bigr]\ \approx\ \exp\Bigl(-c\,\frac{n}{t^2}\,\log^3\frac{\sqrt n}{t}\Bigr).

要让它小于 $2^{-n}$ ，指数必须至少是 $n$ 的量级：

\frac{n}{t^2}\,\log^3\frac{\sqrt n}{t}\ \gtrsim\ n\qquad\Longleftrightarrow\qquad t\ \lesssim\ \log^{3/2}\frac{\sqrt n}{t}.

当 $t$ 只是 $\log n$ 的幂次时， $\log\frac{\sqrt n}t\approx\frac12\log n$ $\frac{1}{2} lo g n$ 。所以门槛正好在 $t\asymp\log^{3/2}n$ $lo g^{3/2} n$ ：比它小的 $t$ ，并集界够用；比它大的，就不够了。 $\frac32$ 就是 3 的一半：小球估计里对数的三次方，开平方之后变成 $\frac32$ 次方。

问题	对应的随机过程	小球概率的指数	解出的 $t$	实际答案
直线上的区间	布朗运动	$\varepsilon^{-2}$	常数	1（第 2 节）
平面上的矩形	布朗单	$\varepsilon^{-2}\log^3(1/\varepsilon)$	$\log^{3/2}n$	$\Theta(\log^{3/2}n)$ （本文）

第一行是个验算：一维时指数里没有对数，解出来 $t$ 是常数，和第 2 节“交替染色，差恒为 1”对得上。

这只是猜测

“像布朗单”说的是分布的极限，它描述的是典型的起伏。这里要估计的概率是 $e^{-n}$ 这么小的数，弱收敛本身控制不了指数小的概率。论文的说法是：这个计算只预言了尺度； $F_\chi$ 不是高斯过程，高斯极限控制不了这么小的概率。所以第四部分要直接对有限个点证明。

另外，上面的类比略去了两样东西：极限过程在右上角是钉住的；颜色不平衡时 $F_\chi$ 还有均值 $S\,xy$ ，全染成红色时 $F_\chi(1,1)=n$ $n$ ，根本不是 $\sqrt n$ 的量级。猜尺度时可以先不管它们，证明里不能。

第四部分的证明完全不用高斯分布。但它最后得到的参数关系，和上面这个计算一模一样，第 19 节会回来对一下账。

§ 10 · 进阶逐位揭示：把一个随机数拆成一串骰子

证明里的随机性是一点一点放出来的。先看一个随机数怎么拆。取整数 $b\ge2$ 作为底数。把 $[0,1]$ 等分成 $b$ 段， $U$ 落在第几段，就把这个编号记作它的第 1 位数字 $d_1\in\{1,\dots,b\}$ ${1, \dots, b}$ 。再把那一段等分成 $b$ 小段， $U$ 落在第几小段记作 $d_2$ 。这样一直做下去。这就是 $U$ 的 $b$ 进制小数，只是数字从 1 数起，为的是和后面“第 $r$ 个子区间”对上号。

每往下一行，就把上一行高亮的那一段放大成整行，再四等分。

工具 · 均匀随机数的各位数字

如果 $U$ 在 $[0,1]$ 上均匀分布，那么它的各位数字 $d_1,d_2,\dots$ 相互独立，而且每一位都在 $\{1,\dots,b\}$ 上均匀分布。

证明：“前 $j$ 位数字依次是 $r_1,\dots,r_j$ ”等价于“ $U$ 落在某一个长度为 $b^{-j}$ 的区间里”，概率是 $b^{-j}=\frac1b\cdot\frac1b\cdots\frac1b$ $\frac{1}{b} \dots \frac{1}{b}$ 。联合概率等于各自概率的乘积，这正是独立且均匀的定义。

所以一个均匀随机数可以看成一串独立的 $b$ 面骰子。已经掷出前 $j$ 个，只知道 $U$ 在哪一个长 $b^{-j}$ 的区间里；下一个骰子决定它落在这个区间的哪一个子区间，而且与前面掷出的结果无关。

已知信息和条件期望

证明分阶段进行，阶段从 0 编到 $h$ （ $h$ 是层数，第 11 节取定）。记 $\mathcal F_j$ 为第 $j$ 阶段的已知信息：全部 $n$ 个点的纵坐标 $V_1,\dots,V_n$ ，加上每个横坐标 $U_i$ 的前 $j$ 位数字。 $\mathcal F_0$ 只知道纵坐标。每往下走一个阶段，就多揭示每个点的一位数字。

因为各点相互独立， $U_i$ 又与 $V_i$ 独立，所以在 $\mathcal F_j$ 已知的条件下， $n$ 个点的下一位数字是 $n$ 个独立的、均匀的 $b$ 面骰子。从第 $j$ 阶段到第 $j+1$ 阶段，新增的随机性只有这些。

工具 · 条件期望

$\EE[X\mid\mathcal F_j]$ 的意思是：把已知信息当成常数，只对还没揭示的数字求平均。结果是一个由已知信息决定的量。后面用到它的四条性质。

线性。 $\EE[X+Y\mid\mathcal F_j]=\EE[X\mid\mathcal F_j]+\EE[Y\mid\mathcal F_j]$ $F_{j}]$ ，不需要独立性。

已知的量可以提出来。如果 $Y$ 由 $\mathcal F_j$ 决定，那么 $\EE[YX\mid\mathcal F_j]=Y\cdot\EE[X\mid\mathcal F_j]$ $F_{j}]$ 。求平均时 $Y$ 是常数。

逐层平均。先对后揭示的数字求平均，再对先揭示的求平均，等于一次对全部求平均： $\EE\bigl[\EE[X\mid\mathcal F_{j+1}]\bigm|\mathcal F_j\bigr]=\EE[X\mid\mathcal F_j]$ $F_{j}]$ ，特别地 $\EE\bigl[\EE[X\mid\mathcal F_j]\bigr]=\EE[X]$ $E [X]$ 。

绝对值。 $\bigl|\EE[X\mid\mathcal F_j]\bigr|\le\EE\bigl[\,|X|\bigm|\mathcal F_j\bigr]$ $F_{j}]$ 。平均值的绝对值不超过绝对值的平均值，这是三角不等式。

如果只有有限种可能的结果，条件期望就是一个加权平均，这四条都可以直接验证。本文的情形正是如此：每一步只涉及 $n$ 个骰子，一共 $b^n$ 种结果，每种的概率都是 $b^{-n}$ 。只有第 13 节有一处要对连续的位置求平均，那里会说明。

Part IV · 第 11–18 节

局部振荡

这一部分是证明本身，依据论文的 r65 稿。主角是一个叫局部振荡的量 $Z_j$ 。证明的骨架是三件事：过一层， $Z$ 平均涨一截（引理 2.1、2.3、2.4 和 Fact 2.2）；点摊得开的时候，这一截足够大，而点几乎总是摊得开（引理 2.5）；实际的涨幅很难比平均值低太多（引理 2.6）。命题 2.7 把它们合起来，对全部染色用并集界。

路线是：先把正方形按阶段切成小矩形，定义 $Z_j$ （第 11、12 节）。在一个矩形里证明，细分之后振荡的期望只增不减，而且多出一截（第 13、14 节）；一位数字对 $Z$ 的影响很小（第 15 节）。然后把 $h$ 层接起来（第 16 节），说明在 $M\le n$ 时，各层以高概率同时是好层（第 17 节），最后选参数收尾（第 18 节）。公式编号 (1)–(18)、引理 2.1、2.3–2.6、Fact 2.2、命题 2.7 和附录的 Fact A.1 都和论文一致。个别地方为了讲解调了先后，会在当处说明。

§ 11 · 入门 $h+1$ 个阶段，一族等面积的矩形

从这里到第 17 节，染色 $\chi$ 是固定的，把 $F_\chi$ 简写成 $F$ 。以概率 1，各点的纵坐标互不相同，也没有哪个点的坐标形如 $k/b^r$ （ $k$ 、 $r\ge0$ 是整数）。下面只在这个事件上讨论。后面所有区间的端点都是 $k/b^r$ 的形式，所以没有点落在分割线上。

取三个参数：

底数 $b\ge3$ $3$ ，是整数；
层数 $h\ge1$ $1$ ，是整数；
$M=b^{h-1}$ $b^{h - 1}$ 。

它们的具体取值到第 18 节才定： $b$ 是一个只依赖 $A$ 的大常数， $h$ 大约是 $\log n$ 除以 $\log b$ 。

阶段。对 $j=0,1,\dots,h$ $0, 1, \dots, h$ ，第 $j$ 阶段把正方形这样切开：

横向切成 $b^j$ 个长度为 $b^{-j}$ 的区间 $I$ 。前 $j$ 位数字相同的横坐标正好落在同一个区间里。
纵向切成 $b^{h-j}$ 个高度为 $b^{j-h}$ 的块 $B$ 。块含下端、不含上端。

于是第 $j$ 阶段共有 $b^j\cdot b^{h-j}=b^h=bM$ 个小矩形 $I\times B$ $B$ ，每个的面积都是 $b^{-j}\cdot b^{j-h}=b^{-h}$ $b^{- h}$ 。个数和面积都与 $j$ 无关，变的只是形状：第 0 阶段是 $b^h$ 根横放的细条，第 $h$ 阶段是 $b^h$ 根竖放的细条。

阶段 $j=0,1,\dots,h$ 一共 $h+1$ 个。从第 $j$ 阶段到第 $j+1$ 阶段的过渡，叫做第 $j$ 层， $j=0,\dots,h-1$ $1$ ，一共 $h$ 层。论文把它叫做 transition $j\to j+1$ $1$ ，把小矩形叫做 cell，把子区间叫做 child，把纵向的区间按场合叫做 vertical interval 或 block。

过一层，同时发生两件事：

每个区间 $I$ 被切成 $b$ 个子区间 $C_1,\dots,C_b$ ，从左到右编号。一个点落在哪个子区间，由它的下一位数字决定。
每 $b$ 个相邻的旧块 $B_1,\dots,B_b$ （从下到上）并成一个新块 $J$ 。

一次过渡发生在一个矩形

R=I\times J

里（对应论文的 Figure 2 和 Figure 3 左）。左边的

b

个旧矩形

I\times B_\ell

和右边的

b

个新矩形

C_k\times J

铺满的是同一块地方。

这样的 $R=I\times J$ 叫比较矩形： $I$ 是第 $j$ 阶段的区间， $J$ 是第 $j+1$ 阶段的块。它一共有 $b^j\cdot b^{h-j-1}=M$ 个，每个面积是 $\frac1M$ 。所以

\frac nM=\text{一个比较矩形里的平均点数}.

这个比值后面会反复出现。到第 18 节会看到，它应该取成 $h$ 的量级。

“面积相同、形状各异的一族矩形”并不新鲜：第 7 节 Roth 的方法用的就是面积固定的二进盒子。新的地方在于，下面要在这族矩形上量一个不同的东西。

§ 12 · 进阶端点平均与振荡

端点平均

对一个横向区间 $I=[s,t]$ $[s, t]$ ，把 $F$ 在两个端点处的值取平均：

a_I(y)=\frac{F(s,y)+F(t,y)}2.\tag{2}

论文把端点记作 $I^-$ 、 $I^+$ ，把这个函数记作 $a^{(I)}$ ，在 $I$ 固定的时候简写成 $a$ 。式 (1) 是下面 $Z_j$ 的定义，论文在引言里就给出了。

它是 $y$ 的函数，叫做 $I$ 的端点平均。看看每个点在里面占多大份量。在纵坐标不超过 $y$ 的点里， $F(s,y)$ 把 $I$ 左边的点按颜色加起来， $F(t,y)$ 加的是这些点再加上 $I$ 里面的点。所以：

一个点在

a_I

里的系数只取决于它在

I

的左边、里面还是右边。

a_I(y)=\sum_{i=1}^n\chi_i\,w_I(U_i)\,\one_{\{V_i\le y\}},\qquad w_I(u)=\begin{cases}1,&u\ \text{在}\ I\ \text{的左边},\\[2pt]\tfrac12,&u\ \text{在}\ I\ \text{里},\\[2pt]0,&u\ \text{在}\ I\ \text{的右边}.\end{cases}

所以 $a_I(y)$ 是一个阶梯函数： $y$ 每往上越过一个点，它就跳 $\chi_iw_I(U_i)$ ，也就是 $\pm1$ 、 $\pm\frac12$ 或者不动。那个 $\frac12$ 看起来有点怪，第 13、14 节会看到它是整个证明的支点。论文把这个系数叫做点的权重（weight）。

例

取 $b=4$ $4$ 、 $h=1$ $1$ 。看区间 $I=[\frac14,\frac12]$ $[\frac{1}{4}, \frac{1}{2}]$ ，放三个点： $I$ 的左边有一个红点，高度 0.3； $I$ 里有一个蓝点，高度 0.55，还有一个红点，高度 0.8。它们的系数依次是 $1$ 、 $\frac12$ 、 $\frac12$ 。让 $y$ 从下往上走：

a_I(y)=\begin{cases}0,&y<0.3,\\1,&0.3\le y<0.55,\\1-\frac12=\frac12,&0.55\le y<0.8,\\\frac12+\frac12=1,&y\ge0.8.\end{cases}

0.3 以下没有点；越过左边的红点，加 1；越过蓝点，减 $\frac12$ ；越过最后一个红点，加 $\frac12$ 。

几件事值得动手试一下。把阶段调到 0，这时 $I=[0,1]$ $[0, 1]$ ，左端点的矩形是空的， $a_I(y)=\frac12F(1,y)$ $\frac{1}{2} F (1, y)$ ，每个点的系数都是 $\frac12$ 。把区间移到最右边，几乎所有点的系数都是 1， $a_I$ 接近 $F(1,y)$ 本身。翻转 $I$ 里面一个点的颜色， $a_I$ 在它上方的部分整体挪 1；翻转 $I$ 左边的一个点，挪 2；翻转右边的点，什么也不变。

振荡

$a_I(y)$ 是阶梯函数，只跳有限次，所以在任何一个块上它都有最大值和最小值。对一个关于高度的函数 $f$ 和一个纵向的块 $B$ ，记

\operatorname{osc}_B\,f=\max_Bf-\min_Bf,\qquad\operatorname{mid}_B\,f=\frac{\max_Bf+\min_Bf}2,\tag{3}

分别叫做 $f$ 在 $B$ 上的振荡和中点。振荡量的是 $f$ 在 $B$ 上取值的范围有多宽，中点量的是这个范围在哪里。最大值和最小值就是 $\operatorname{mid}_B\,f\pm\frac12\operatorname{osc}_B\,f$ $\frac{1}{2} osc_{B} f$ 。块含下端、不含上端。

工具 · 振荡的三条性质

不怕加常数。整个块上同时加一个数 $c$ ，最大值和最小值一起动，振荡不变；中点跟着加 $c$ 。

三角不等式。 $\operatorname{osc}_B(f+g)\le\operatorname{osc}_B\,f+\operatorname{osc}_B\,g$ $osc_{B} g$ 。理由： $\max(f+g)\le\max f+\max g$ $max g$ ， $\min(f+g)\ge\min f+\min g$ $min g$ ，两式相减。反复用它，对有限个函数的和同样成立。另外，乘一个常数 $c$ ，振荡变成 $|c|$ 倍： $\operatorname{osc}_B(cf)=|c|\operatorname{osc}_B\,f$ $∣ c ∣ osc_{B} f$ 。

反向三角不等式。 $\bigl|\operatorname{osc}_B(f+g)-\operatorname{osc}_B\,f\bigr|\le\operatorname{osc}_B\,g$ $osc_{B} g$ 。理由：把 $f$ 写成 $(f+g)+(-g)$ $(- g)$ ，再用一次三角不等式和 $\operatorname{osc}_B(-g)=\operatorname{osc}_B\,g$ $osc_{B} g$ ，得到 $\operatorname{osc}_B\,f\le\operatorname{osc}_B(f+g)+\operatorname{osc}_B\,g$ $osc_{B} g$ 。另一个方向就是三角不等式本身。

第一条是选振荡的原因：挪动一个高度不在 $B$ 里的点， $B$ 上的函数只是整体加了一个常数。第二条在第 13 节用，第三条在第 15 节用。

势函数 $Z_j$

把第 $j$ 阶段所有小矩形上的振荡取平均：

Z_j=\frac1{bM}\sum_{I\times B}\operatorname{osc}_B\,a_I,\tag{1}

求和遍历第 $j$ 阶段的 $bM$ 个小矩形 $I\times B$ （论文叫 cell）。论文把 $Z_j$ 叫做势函数（potential）。在上面的例子里， $I$ 是第 1 阶段的区间，唯一的块是整个 $[0,1)$ ， $a_I$ 在它上面取到 $0$ 、 $\frac12$ 、 $1$ 三个值，振荡是 $1-0=1$ $1$ 。

Z_j

的两条基本性质论文式 (9) 和它后面一段

0\le Z_j\le2\norm F_\infty,\tag{9}

并且 $Z_j$ 由 $\mathcal F_j$ 决定。

式 (9) 在论文里到 2.4 小节才出现，这里提前用了它的编号。

推导两条性质

下界。每一项都是最大值减最小值，不会是负的。
上界。由 (3)，一个振荡是 $a_I$ 的两个值之差；由 (2)， $a_I$ 的每个值是 $F$ 的两个值的平均，绝对值不超过 $\norm F_\infty$ 。所以每一项振荡都不超过 $2\norm F_\infty$ ，平均值也一样。
由 $\mathcal F_j$ 决定。第 $j$ 阶段的区间端点是 $b^{-j}$ 的整数倍。一个点在某个端点的左边还是右边，看它的前 $j$ 位数字就知道了。所以每个系数 $w_I(U_i)$ 都由 $\mathcal F_j$ 决定，纵坐标本来就已知。

注意 $Z_0$ 不一定是 0：第 0 阶段的块虽然很矮，里面仍然可能有点。后面只用到 $Z_0\ge0$ $0$ 。

式 (9) 的上界是 $Z$ 和差异度之间唯一的联系，但已经够用了：

\norm{F_\chi}_\infty\ \ge\ \tfrac12Z_h.

所以只要证明 $Z_h$ 很大，这种染色就有一个差很大的锚定矩形。而 $Z_0\ge0$ $0$ ，之后一共走 $h$ 步。接下来的计划就是证明：它每一步平均都在涨，而且实际值很难比平均值低太多。

把阶段从 0 调到 3，可以看到三件事。第 0 阶段的块很矮，一个块里通常只有零到两三个点，振荡多半是 0、 $\frac12$ 或 1，所以 $Z_0$ 很小。在这组点上，往后小矩形越来越瘦高，每个块越来越高，里面的点越来越多，颜色整体变浓， $Z_j$ 跟着变大。但不管怎么变，横条都不会越过虚线，这就是式 (9)。再换成“按 $y$ 顺序交替”染色： $F(1,y)$ 被压得很小，可是在这个样本上 $Z_j$ 仍然涨得起来，因为窄区间上的 $a_I$ 只看得见一部分点，交替的规律在那里被打乱了。

这些都是一组样本上的现象。单次实现里 $Z_j$ 完全可以下降，两个点就够：取 $b=3$ $3$ 、 $h=1$ $1$ ，点 $(\frac45,\frac15)$ 染红、 $(\frac9{10},\frac45)$ 染蓝，按定义算出 $Z_0=\frac13$ $\frac{1}{3}$ ， $Z_1=\frac16$ $\frac{1}{6}$ 。后面证明的是条件期望在涨，再另外控制实际值对条件期望的偏离。

为什么是端点平均，为什么是振荡

端点平均让“细分”变得干净：把 $I$ 切成 $b$ 个子区间，再让每个点随机落进其中一个，子区间的端点平均再取平均，期望恰好等于原来的 $a_I$ （第 14 节的式 (7)）。只取右端点就没有这个性质。

振荡不怕加常数：整个块上同时加一个数，最大值和最小值一起动，差不变。所以一个点横向移动时，对每个固定的横向区间 I，只有包含该点高度的纵向块的振荡可能改变（第 15 节）。直接用 $|a_I|$ 的最大值就做不到这一点。

§ 13 · 核心推导一个矩形里的比较（上）：不含概率的部分

这两节的目标

固定一个比较矩形 $R=I\times J$ $J$ 。细分之前， $R$ 被切成 $b$ 个横条 $I\times B_\ell$ $B_{ℓ}$ ；细分之后，被切成 $b$ 个竖条 $C_k\times J$ $J$ 。把 $R$ 最低和最高的两个横条去掉，剩下的部分叫做 $R$ 的内部区域，里面的点数记作 $m_R$ ：

R^{\mathrm{in}}=I\times(B_2\cup\dots\cup B_{b-1}),\qquad m_R=|P\cap R^{\mathrm{in}}|.

因为 $b\ge3$ $3$ ，内部区域不是空的。这两节要证明的是引理 2.3：竖条上的振荡之和，期望至少是横条上的振荡之和再加一笔，

\EE\Bigl[\,\sum_{k=1}^b\operatorname{osc}_J\,a_{C_k}\Bigr]\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,a_I\ +\ \frac14\sqrt{m_R}.

这一节先做不含概率的部分，得到式 (5) 和 (6)。它们对骰子的任何结果都成立。下一节再取期望。

为了少写下标，这两节把 $a_I$ 简写成 $a$ ，叫旧函数；把 $a_{C_k}$ 简写成 $a_k$ ，叫子函数。论文也是这样写的。

第一步：一个关于阶梯函数的不等式

先不管点和骰子，只看一个定义在 $J$ 上、只取有限个值的函数 $f$ 。 $J$ 上的振荡和 $b$ 个旧块上的振荡有什么关系？最容易想到的是： $J$ 包含每一个旧块，所以 $\operatorname{osc}_J\,f\ge\operatorname{osc}_{B_\ell}\,f$ $osc_{B_{ℓ}} f$ ， $b$ 个不等式加起来就是 $b\operatorname{osc}_J\,f\ge\sum_\ell\operatorname{osc}_{B_\ell}\,f$ $\sum_{ℓ} osc_{B_{ℓ}} f$ 。引理 2.1 说，其实还能多出一项。

引理 2.1（纵向比较）论文 Lemma 2.1

对 $J$ 上每一个只取有限个值的函数 $f$ ，

b\,\operatorname{osc}_J\,f\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,f+2\,\bigl|\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f\bigr|.\tag{4}

$\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f$ 叫做最高的块相对最低的块的偏移（论文叫 offset）： $f$ 在最高的块里取值的范围，和在最低的块里取值的范围，中心差了多少。

推导引理 2.1

首尾两个块合起来看。 $B_1$ 和 $B_b$ 都在 $J$ 里，而 $f$ 在一个块 $B$ 上的最大、最小值是 $\operatorname{mid}_B\,f\pm\frac12\operatorname{osc}_B\,f$ $\frac{1}{2} osc_{B} f$ 。拿最高的块的最大值减最低的块的最小值，再反过来减一次： $\begin{aligned}\operatorname{osc}_J\,f&\ \ge\ \max_{B_b}f-\min_{B_1}f=\frac{\operatorname{osc}_{B_1}f+\operatorname{osc}_{B_b}f}2+\bigl(\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f\bigr),\\[4pt]\operatorname{osc}_J\,f&\ \ge\ \max_{B_1}f-\min_{B_b}f=\frac{\operatorname{osc}_{B_1}f+\operatorname{osc}_{B_b}f}2-\bigl(\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f\bigr).\end{aligned}$
取较大的一个。两个右边只差在偏移前面的符号上，所以 $\operatorname{osc}_J\,f\ \ge\ \frac{\operatorname{osc}_{B_1}f+\operatorname{osc}_{B_b}f}2+\bigl|\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f\bigr|.$
中间的块。对中间 $b-2$ 个块，各用一次 $\operatorname{osc}_J\,f\ge\operatorname{osc}_{B_\ell}\,f$ $osc_{B_{ℓ}} f$ 。把这 $b-2$ 个不等式和第 2 步的两倍加起来，左边一共是 $b$ 个 $\operatorname{osc}_J\,f$ 。

灰色的是最低和最高两个块。这个例子里四个块上的振荡是

1,\ 2,\ 1,\ 1.5

，偏移是

0.75

，式 (4) 的右边是

5.5+2\times0.75=7

7

，左边是

4\times2.5=10

10

。

偏移就是后面增益的来源。给 $f$ 在最高的块上整体加一个常数：偏移变了，而每个块上的振荡都不变。所以式 (4) 里只有左边 $J$ 上的振荡看得见它。

第二步：细分之后，对子函数取平均

现在把 $I$ 切成 $b$ 个子区间 $C_1,\dots,C_b$ ，每个子区间有自己的端点平均 $a_k=a_{C_k}$ $a_{C_{k}}$ 。不去逐个研究它们，而是先把它们平均起来：

\bar a(y)=\frac1b\sum_{k=1}^ba_k(y).

由振荡的三角不等式（第 12 节）， $b$ 个函数各自的振荡加起来，不小于它们的和的振荡；而它们的和是 $b\,\bar a$ ：

\sum_{k=1}^b\operatorname{osc}_J\,a_k\ \ge\ \operatorname{osc}_J\Bigl(\sum_{k=1}^ba_k\Bigr)=b\,\operatorname{osc}_J\,\bar a.

右边正好是引理 2.1 左边的形状。对 $f=\bar a$ 用引理 2.1：

先平均，再比较论文式 (5)

\sum_{k=1}^b\operatorname{osc}_J\,a_k\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,\bar a+2\,\bigl|\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a\bigr|.\tag{5}

左边是细分之后 $b$ 个竖条上的振荡之和，正是我们要的量。右边只剩一个函数 $\bar a$ ：它在 $b$ 个旧块上的振荡，加上它在首尾两个块之间的偏移的两倍。 $b$ 个子区间各自的细节都不见了。

到这里为止没有用到任何概率。不管点落在哪个子区间，式 (5) 都成立。

第三步：一个点在 $\bar a$ 里的权重

要比较 $\bar a$ 和原来的 $a$ ，先算每个点在 $\bar a$ 里的权重。由式 (2)， $\bar a$ 数每个点时用的权重，是它在 $b$ 个子区间里的系数的平均；而 $a$ 用的是它在 $I$ 里的系数，论文叫它的旧权重。 $I$ 左边的点，在每个 $a_k$ 里的系数都是 1，平均还是 1； $I$ 右边的点都是 0。这两类点在 $\bar a$ 里和在 $a$ 里一模一样。

$I$ 里面的点旧权重是 $\frac12$ ，新的权重要看它落在哪个子区间。设它落在 $C_r$ 里：它右边的 $b-r$ 个子区间都把它算作“在左边”，各给系数 1；它自己所在的子区间给 $\frac12$ ；它左边的子区间给 0。所以它在 $\bar a$ 里的权重是

\frac{(b-r)+\frac12}b=\frac12+\frac{b+1-2r}{2b}\qquad(r=1,\dots,b).

这里的 $r$ 是子区间的编号，也就是骰子的结果。

$b=4$ 时，把每个子区间给它的系数排成一张表，行是子区间 $k$ ，列是骰子的结果 $r$ ；每一列的平均就是它在 $\bar a$ 里的权重：

	$r=1$	$r=2$	$r=3$	$r=4$
$a_1$ 里的系数	$\frac12$	0	0	0
$a_2$ 里的系数	1	$\frac12$	0	0
$a_3$ 里的系数	1	1	$\frac12$	0
$a_4$ 里的系数	1	1	1	$\frac12$
$\bar a$ 里的权重	$\frac78$	$\frac58$	$\frac38$	$\frac18$
比 $\frac12$ 多出的部分	$+\frac38$	$+\frac18$	$-\frac18$	$-\frac38$

上面的式子把权重拆成了两部分。前一部分 $\frac12$ 正是旧权重。后一部分是多出来的偏差，可正可负。把颜色也乘进去，对落在 $C_r$ 里的第 $i$ 个点记

X_i=\chi_i\cdot\frac{b+1-2r}{2b},

叫做它的增量（论文叫 jump： $\bar a$ 在这个点的高度比 $a$ 多跳的那一下）。于是 $\bar a$ 就是 $a$ 加上 $I$ 里面各点的增量：

\bar a

等于

a

加上增量论文式 (6)

\bar a(y)=a(y)+\sum_{i:\ U_i\in I,\ V_i\le y}X_i.\tag{6}

求和遍历 $I$ 里面、高度不超过 $y$ 的点。用话说： $\bar a$ 跟着旧函数走，只是在 $I$ 里每个点的高度处多跳一下 $X_i$ 。这仍然是一个恒等式，没有概率。

取 $b=4$ $4$ ，画一个比较矩形 $R$ ，并且只考虑 $R$ 里的点。先看“ $a$ ”：右图是阶梯函数 $a(y)$ ，每个旧块旁边的粗线从块里的最小值画到最大值，长度就是这个块上的振荡。再看“ $\bar a$ ”：实线是掷完骰子之后的 $\bar a$ ，虚线是原来的 $a$ ；最低和最高两个块的粗线上各有一个圆点，标的是中点。图下面那条粗线从一个中点画到另一个中点，长度就是偏移的绝对值。点 $C_1,\dots,C_4$ 可以看每个子区间各自的函数和它在整个 $J$ 上的振荡。

多掷几次骰子。 $\bar a$ 每次都不一样，在虚线 $a$ 的两侧摆动。而读数里的那串不等式每一次都成立：四个竖条上的振荡之和，不小于 $4\operatorname{osc}_J\bar a$ ，后者又不小于式 (5) 的右边。

易错

$\bar a(y)$ 本身是随机的，它依赖骰子。下一节会说它的期望是 $a(y)$ ，但掷一次骰子，一个点的权重可以是 $\frac78$ ，也可以是 $\frac18$ ； $b=4$ 时没有哪个结果恰好给出 $\frac12$ （ $b$ 是奇数时，只有正中间的子区间给出 $\frac12$ ）。

那个 $\frac12$ 也不能换。如果不取端点平均，只用区间右端点处的 $F$ 值，点在自己所在的子区间里系数就是 1，权重变成 $\frac{b-r+1}b$ ，对 $r$ 平均是 $\frac{b+1}{2b}$ ，而它在 $I$ 里的系数是 1，两边对不上。

另一种看法：条件期望

在区间 $I$ 里均匀地随机取一个横坐标 $x$ ，与所有的点无关。那么 $a_I(y)$ 是 $F(x,y)$ 在 $\mathcal F_j$ 下的条件期望： $I$ 里面的点和 $x$ 都在 $I$ 里均匀分布，谁在左边各占一半。论文第 3 节把它写成 $a_I(y)=\EE\bigl[\frac1{|I|}\int_IF(x,y)\,dx\bigm|\mathcal F_j\bigr]$ $F_{j}]$ ，并指出这是 Talagrand 证明里“横向取平均”的条件期望版本。同样的道理， $\bar a(y)$ 是同一个量在 $\mathcal F_{j+1}$ 下的条件期望，只不过多知道了一位数字。（这里的平均包括各点在区间里的具体位置，不再是有限个结果的加权平均，但第 10 节的四条性质照样成立。）

§ 14 · 核心推导一个矩形里的比较（下）：取期望，基准和增益

上一节得到了式 (5)，它对骰子的任何结果都成立：

\sum_{k=1}^b\operatorname{osc}_J\,a_k\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,\bar a+2\,\bigl|\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a\bigr|.

这一节对右边取期望，分两件事做。第一件： $\bar a$ 在各旧块上的振荡，期望不小于 $a$ 的振荡，这是基准。第二件：偏移的绝对值，期望至少是 $\frac18\sqrt{m_R}$ ，乘以 2 就是增益。合起来就是引理 2.3。

随机的是什么

先说清楚什么是已知的，什么是随机的。各点的颜色和高度固定；每个点相对 $I$ 的位置（在 $I$ 的左边、在 $I$ 里、在 $I$ 的右边）也固定。 $I$ 里面的每个点独立地、等可能地落进 $b$ 个子区间之一，也就是各掷一个 $b$ 面的骰子。论文把这叫做局部实验（local experiment）。在局部实验里，旧函数 $a$ 是固定的，子函数 $a_1,\dots,a_b$ 是随机的。下面的 $\EE$ 都是对这些骰子取的。

别的都不需要指定： $I$ 外面的点在每个子区间的同一侧，所以子函数依赖横坐标的方式只有两样：每个点相对 $I$ 的位置，和 $I$ 里的点各自落进哪个子区间。第 16 节会说明，在 $\mathcal F_j$ 已知的条件下，过一层时每个比较矩形里发生的正是这个实验。

第一步：增量是对称的，所以 $\EE\,\bar a=a$

看一个 $I$ 里面的点的增量 $X_i=\chi_i\cdot\frac{b+1-2r}{2b}$ $\frac{b + 1 - 2 r}{2 b}$ ，其中 $r$ 在 $1,\dots,b$ 上等可能。 $r$ 从 1 走到 $b$ 时， $b+1-2r$ 依次取 $b-1,\ b-3,\ \dots,\ -(b-1)$ $1)$ ，这组数关于 0 对称。所以不管颜色是什么， $X_i$ 取每个值和取它的相反数的概率一样大：它是对称的（和 $-X_i$ 同分布），特别地 $\EE X_i=0$ $0$ 。不同的点用不同的骰子，各个增量相互独立。

由式 (6)， $\bar a(y)$ 等于 $a(y)$ 加上若干个增量，每个增量的期望是 0。所以

平均函数的期望是旧函数论文式 (7)

\EE\,\bar a(y)=a(y)\qquad\text{对每个高度 }y.\tag{7}

细分一步之后再取平均，期望意义下回到原来的函数。这就是第 12 节说的“端点平均让细分变得干净”。

第二步：基准

工具 · 最大值的期望不小于期望的最大值

设 $\phi(y)$ 是一个随机的函数（每个 $y$ 处的值都是随机变量）， $B$ 是一个集合。对 $B$ 里任意一个固定的 $y_0$ ，总有 $\max_{y\in B}\phi(y)\ge\phi(y_0)$ $ϕ (y_{0})$ 。两边取期望： $\EE\max_{y\in B}\phi(y)\ge\EE\,\phi(y_0)$ $E ϕ (y_{0})$ 。这对每个 $y_0$ 都成立，所以

\EE\max_{y\in B}\phi(y)\ \ge\ \max_{y_0\in B}\EE\,\phi(y_0).

同样的道理， $\EE\min_{y\in B}\phi(y)\le\min_{y_0\in B}\EE\,\phi(y_0)$ $min_{y_{0} \in B} E ϕ (y_{0})$ 。

直观地说：先看骰子再挑最好的高度，平均起来不会比事先挑定一个高度差。把工具用在 $\bar a$ 和每个旧块 $B_\ell$ 上，再用式 (7)：

\EE\operatorname{osc}_{B_\ell}\bar a=\EE\max_{B_\ell}\bar a-\EE\min_{B_\ell}\bar a\ \ge\ \max_{B_\ell}a-\min_{B_\ell}a=\operatorname{osc}_{B_\ell}a.

旧的振荡保得住。对 $\ell=1,\dots,b$ 求和，再对式 (5) 两边取期望：

基准，加上偏移的期望论文式 (8)

\EE\Bigl[\,\sum_{k=1}^b\operatorname{osc}_J\,a_k\Bigr]\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,a+2\,\EE\,\bigl|\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a\bigr|.\tag{8}

右边第一项是细分之前横条上的振荡之和，这一步说的是“不亏”。第二项是增益，下面三步给它一个下界。

第三步：把内部点的贡献单独拿出来

内部区域 $R^{\mathrm{in}}=I\times(B_2\cup\dots\cup B_{b-1})$ 里的点有一个特别的性质：它们都在 $B_1$ 的上方、 $B_b$ 的下方。记

D=\sum_{i:\ P_i\in R^{\mathrm{in}}}X_i

为这 $m_R$ 个内部点的增量之和，再记 $g$ 为式 (6) 里去掉这些增量之后的函数：

g(y)=a(y)+\sum_{i:\ U_i\in I,\ P_i\notin R^{\mathrm{in}},\ V_i\le y}X_i.

那么：

在 $B_1$ 上，内部点都还没被数到，所以 $\bar a=g$ $g$ ；
在 $B_b$ 上，内部点全都被数到了，所以 $\bar a=g+D$ $D$ ，比 $g$ 整体高出一个常数 $D$ 。

对应论文的 Figure 3（左、中）。内部区域里的 10 个点决定

D

。上下两个灰色块里的 4 个淡色的点只进入

g

：它们的高度在

B_1

或

B_8

里，增量只影响块的一部分，不能当成常数提出来。

整个块上加一个常数 $D$ ，最大值和最小值都跟着加 $D$ ，中点也加 $D$ 。所以

偏移里有一个

D

论文引理 2.3 的证明，Step 4

\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a=\theta+D,\qquad\text{其中}\ \ \theta=\operatorname{mid}_{B_b}g-\operatorname{mid}_{B_1}g.

$\theta$ 是 $g$ 自己的偏移：没有内部点的增量时，首尾两个块本来就差多少。

例

取 $b=4$ $4$ 。为了简单，设一共只有两个点，都在 $R$ 里：一个红点在 $B_2$ 里，一个蓝点在 $B_3$ 里，都是内部点。细分之前， $a$ 在红点处从 0 升到 $\frac12$ ，在蓝点处又降回 0。四个旧块上的振荡是 $0,\frac12,\frac12,0$ ，和是 1。注意 $a$ 在最低和最高的块上都恒等于 0：两个颜色抵消了，首尾没有偏移。

细分之后，设红点落进 $C_r$ ，蓝点落进 $C_{r'}$ 。没有别的点，所以 $g=a$ $a$ ， $\theta=0$ $0$ ，而 $D=\frac{5-2r}8-\frac{5-2r'}8=\frac{r'-r}4$ $\frac{r ^{'} - r}{4}$ 。 $\bar a$ 在 $B_1$ 上是 0，在 $B_4$ 上是常数 $D$ ，偏移就是 $D$ 。十六种等可能的结果里：

$\|D\|$	0	$\frac14$	$\frac12$	$\frac34$
有几种结果	4	6	4	2

所以 $\EE|D|=\frac1{16}\bigl(6\cdot\frac14+4\cdot\frac12+2\cdot\frac34\bigr)=\frac5{16}$ $\frac{5}{16}$ 。细分之前首尾恰好持平，细分之后只有四分之一的机会仍然持平。式 (8) 右边的第二项是 $2\cdot\frac5{16}=\frac58$ $\frac{5}{8}$ ；引理 2.3 保证的是 $\frac14\sqrt2\approx0.35$ $0.35$ 。

偏移是“一个固定的数 $\theta$ ，加上一个随机的和 $D$ ”。对某一次骰子， $D$ 可能恰好把原来的偏移 $\theta$ 抵消掉。但 $D$ 是若干个独立的对称增量之和，这样的和不会总挤在某个数附近，所以平均起来抵消不掉。下一步把这句话变成不等式。

第四步：对称随机变量的和离任何定点都不近

先算增量的两个矩。 $X_i^2$ 不依赖颜色， $r$ 在 $1,\dots,b$ 上等可能：

\EE X_i^2=\frac1b\sum_{r=1}^b\Bigl(\frac{b+1-2r}{2b}\Bigr)^2=\frac{b^2-1}{12b^2}=:\sigma^2.

另外 $|X_i|\le\frac{b-1}{2b}$ （ $r=1$ $1$ 或 $b$ 时取到），所以 $X_i^4\le\bigl(\frac{b-1}{2b}\bigr)^2X_i^2$ $(\frac{b - 1}{2 b})^{2} X_{i}^{2}$ ，于是

\EE X_i^4\le\Bigl(\frac{b-1}{2b}\Bigr)^2\sigma^2\le\frac{b^2-1}{4b^2}\,\sigma^2=3\sigma^4.

推导这两个矩

二阶矩。 $b+1-2r$ 取 $b-1,\ b-3,\ \dots,\ -(b-1)$ $1)$ ，它们的平方和是 $\frac{b(b^2-1)}3$ （比如 $b=4$ $4$ ： $9+1+1+9=20=\frac{4\cdot15}3$ $\frac{4 \cdot 15}{3}$ ）。所以 $\EE X_i^2=\frac1b\cdot\frac{b(b^2-1)}{3\cdot4b^2}=\frac{b^2-1}{12b^2}$ $\frac{b ^{2} - 1}{12 b ^{2}}$ 。论文换了一种算法： $X_i^2=\bigl(r-\frac{b+1}2\bigr)^2/b^2$ $\frac{b + 1}{2})^{2} / b^{2}$ ，而 $r$ 的方差是 $\frac{(b+1)(2b+1)}6-\frac{(b+1)^2}4=\frac{b^2-1}{12}$ $\frac{b ^{2} - 1}{12}$ 。
四阶矩。中间那个不等号是 $(b-1)^2\le b^2-1$ $1$ ，也就是 $b\ge1$ $1$ 。最后的等号是 $\frac{b^2-1}{4b^2}=3\sigma^2$ $3 σ^{2}$ 。

$b$ 很大时 $\sigma^2$ 接近 $\frac1{12}$ ，这是 $[-\frac12,\frac12]$ 上均匀分布的方差。

工具 · Cauchy–Schwarz 不等式（期望形式）

对任意随机变量 $X,Y$ ，有 $\EE|XY|\le\sqrt{\EE[X^2]\cdot\EE[Y^2]}$ $E [X^{2}] \cdot E [Y^{2}]$ 。

证明：对任意 $s>0$ $0$ ，由 $(\sqrt s\,|X|-|Y|/\sqrt s)^2\ge0$ 得 $|XY|\le\frac12\bigl(sX^2+Y^2/s\bigr)$ $Y^{2} / s)$ 。取期望，再取 $s=\sqrt{\EE[Y^2]/\EE[X^2]}$ $E [Y^{2}] / E [X^{2}]$ 。有一个二阶矩是 0 时结论显然。

Fact 2.2（对称随机变量的和）论文 Fact 2.2，证明在附录 A.1

设 $X_1,\dots,X_m$ 相互独立，每个都是对称的，并且 $\EE X_i^2=\sigma^2$ $σ^{2}$ ， $\EE X_i^4\le3\sigma^4$ $3 σ^{4}$ ，其中 $\sigma>0$ $0$ 。则对任意实数 $\theta$ ，

\EE\,\bigl|\theta+X_1+\dots+X_m\bigr|\ \ge\ \sigma\sqrt{\frac m3}.

对均匀的 $\pm1$ 符号，这是 Khintchine 不等式（常数差一些）；四阶矩的条件对它们成立，对这里的增量上面刚验证过。

推导Fact 2.2

记 $Y=X_1+\dots+X_m$ $X_{m}$ 。 $m=0$ 时右边是 0，结论显然；下面设 $m\ge1$ $1$ 。

平移不帮忙。每个 $X_i$ 对称，它们又独立，所以 $Y$ 和 $-Y$ 同分布， $\EE|\theta+Y|=\EE|\theta-Y|$ $Y ∣$ 。两者取平均，再用 $|\theta+y|+|\theta-y|\ge2|y|$ $2∣ y ∣$ ，得到 $\EE|\theta+Y|\ge\EE|Y|$ $E ∣ Y ∣$ 。
二阶矩。 $\EE Y^2=\sum_{i,j}\EE[X_iX_j]=\sum_i\EE X_i^2=m\sigma^2$ $m σ^{2}$ ，因为 $i\ne j$ 时 $\EE[X_iX_j]=\EE X_i\cdot\EE X_j=0$ $0$ 。
四阶矩。展开 $Y^4$ 。一项里如果有某个下标出现奇数次，由独立性和对称性，它的期望是 0。剩下两类：四个下标全相同的 $X_i^4$ ；两两配对的 $X_i^2X_j^2$ （ $i<j$ $j$ ），每一对出现 $\binom42=6$ 次。所以 $\EE Y^4=\sum_i\EE X_i^4+6\sum_{i<j}\EE X_i^2\,\EE X_j^2\le3m\sigma^4+3m(m-1)\sigma^4=3m^2\sigma^4.$
两次 Cauchy–Schwarz。把 $Y^2$ 拆成 $|Y|^{1/2}\cdot|Y|^{3/2}$ $∣ Y ∣^{3/2}$ ，再把 $|Y|^3$ 拆成 $|Y|\cdot Y^2$ $Y^{2}$ ： $\EE Y^2\le\bigl(\EE|Y|\bigr)^{1/2}\bigl(\EE|Y|^3\bigr)^{1/2},\qquad\EE|Y|^3\le\bigl(\EE Y^2\bigr)^{1/2}\bigl(\EE Y^4\bigr)^{1/2}.$ 第一式两边平方，再代入第二式： $(\EE Y^2)^2\le\EE|Y|\cdot(\EE Y^2)^{1/2}(\EE Y^4)^{1/2}$ $(E Y^{2})^{1/2} (E Y^{4})^{1/2}$ ，也就是 $\EE|Y|\ge(\EE Y^2)^{3/2}/(\EE Y^4)^{1/2}$ $(E Y^{2})^{3/2} / (E Y^{4})^{1/2}$ 。论文在这里用一次 Hölder 不等式（指数 $\frac32$ 和 3），结果相同。
代入。 $\EE|Y|\ge\dfrac{m^{3/2}\sigma^3}{\sqrt3\,m\sigma^2}=\sigma\sqrt{\dfrac m3}$ $σ \frac{m}{3}$ 。

拖动平移量：曲线在 $\theta=0$ 处最低，这是推导的第 1 步。三条横线自上而下排列，这是第 4、5 步。把项数从 1 调到 12，三条线一起按 $\sqrt m$ 的速度上升：项越多，和摊得越开，离任何一个点的平均距离就越大。 $m$ 个内部点给出 $\sqrt m$ 量级的增益，来源就在这里。

第五步：合起来，得到引理 2.3

把骰子分成两批：内部区域里的点的骰子，和 $I$ 里其余的点的骰子（高度在 $B_1$ 里、在 $B_b$ 里、或者在 $J$ 之外的点）。先把第二批看成已知的，只对第一批求平均。这时 $g$ 是一个固定的函数， $\theta$ 是一个固定的数。而 $D$ 是 $m_R$ 个独立的对称增量之和，它们和第二批骰子无关。

对 $\theta+D$ 用 Fact 2.2，取 $m=m_R$ $m_{R}$ 。偏移的绝对值的条件期望至少是

\sigma\sqrt{\frac{m_R}3}=\frac{\sqrt{b^2-1}}{6b}\,\sqrt{m_R}\ \ge\ \frac18\sqrt{m_R}.

后一个不等号是 $16(b^2-1)\ge9b^2$ $9 b^{2}$ ， $b\ge2$ 时成立。这个下界对任何 $\theta$ 都一样，所以第二批骰子怎么掷都压不低它；再对第二批求平均（第 10 节的“逐层平均”），它仍然成立：

\EE\,\bigl|\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a\bigr|\ \ge\ \frac18\sqrt{m_R}.

代进式 (8)：

引理 2.3（局部增益）论文 Lemma 2.3

在局部实验里，

\EE\Bigl[\,\sum_{k=1}^b\operatorname{osc}_J\,a_k\Bigr]\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,a\ +\ \frac14\sqrt{m_R}.

左边是细分之后 $R$ 里 $b$ 个竖条上的振荡之和，右边第一项是细分之前 $b$ 个横条上的振荡之和。把 $R$ 从横着切改成竖着切，振荡之和平均至少多出 $\frac14\sqrt{m_R}$ 。论文说这是整个证明的核心。

这一笔有多大？一个比较矩形里平均有 $\frac nM$ 个点，其中 $1-\frac2b$ 的比例在内部区域里。所以典型情况下，每个比较矩形每细分一次，振荡之和多出 $\sqrt{n/M}$ 的量级。这就是第 5 节末尾说的那个代价：每一层多付一个平方根。

还有一点后面要用：增益的大小 $m_R$ 只数点，不看颜色。染色会改变 $\theta$ ，也会改变各个 $X_i$ 的符号；但 $X_i$ 是对称的，变号之后分布不变，而 Fact 2.2 对任何 $\theta$ 都成立。

多掷几次，再按“掷 2 万次取平均”。三件事应该能看出来。 $\bar a$ 的振荡之和，长期平均不小于旧的和，这是基准。偏移的两倍的长期平均明显大于 $\frac14\sqrt{m_R}$ ，后者只是一个保守的下界。新的和的长期平均又比“基准加增益”大不少：振荡的三角不等式和引理 2.1 都丢掉了一些东西。把点数调大，偏移大致按点数的平方根增长。

一个矩形能给出什么，还缺什么

引理 2.3 直接用在整个正方形上，会得到什么？取 $I=[0,1]$ $[0, 1]$ ， $J=[0,1)$ $[0, 1)$ ， $R$ 就是单位正方形（去掉上边）。每个子函数的振荡是 $a_k$ 的两个值之差，每个值又是 $F$ 的两个值的平均，所以不超过 $2\norm F_\infty$ ；引理左边至多是 $2b\,\EE\norm F_\infty$ 。固定各点的高度，横坐标独立均匀，第一位数字做的就是局部实验，于是

\EE\,\norm F_\infty\ \ge\ \frac{\sqrt{m_R}}{8b}.

典型情况下内部区域里有大约 $(1-\frac2b)n$ 个点，所以这是 $\sqrt n$ 的量级，比要证的 $\log^{3/2}n$ 大得多。

易错

这不是差异的下界。上面的染色是在抽横坐标之前定好的；看过点再染色，可以做到 $O(\log^{3/2}n)$ （Nikolov）。我们要的是对全部 $2^n$ 种染色同时成立的结论，所以每一种固定的染色失败的概率要远小于 $2^{-n}$ 。一个矩形上比较一次，只给出一个期望，离这个要求很远。

所以后面四节不用一个大矩形，而是用 $M$ 个小矩形，并且在 $h$ 个逐渐变细的横向尺度上重复这个比较。引理 2.3 是为此设计的：它的输出（竖条上的振荡之和）和输入（横条上的振荡之和）是同一种量，上一层的输出可以直接当下一层的输入。这样做之后还缺两样东西：

点数增益取决于每个内部区域分到多少点。点会不会太挤？第 17 节，引理 2.5。

期望引理 2.3 只说期望。实际值会不会比期望低很多？第 15、16 节，引理 2.6。

§ 15 · 进阶改一位数字，影响有多大

引理 2.3 说的是平均。要把平均变成“几乎总是”，需要知道细分之后的振荡对每一个骰子有多敏感。答案是：很不敏感。这一节不含概率，只用第 12 节的两条性质：振荡不怕加常数，以及反向三角不等式 $\bigl|\operatorname{osc}_B(f+g)-\operatorname{osc}_B\,f\bigr|\le\operatorname{osc}_B\,g$ $osc_{B} g$ 。论文把这件事放在引理 2.6 的证明里，是它的 Step 1。

一位数字的影响论文引理 2.6 的证明，Step 1

在第 $j$ 层，只改变一个点 $P_i$ 的下一位数字，也就是把它在所在的旧区间 $I$ 里挪到另一个子区间，其余的点不动。那么在第 $j+1$ 阶段的 $bM$ 个小矩形里，只有 $b$ 个的振荡可能变，每个至多变 1。所以

Z_{j+1}\ \text{至多变}\ \frac b{bM}=\frac1M.

推导为什么只有

b

个小矩形受影响

哪些函数会变。设 $P_i$ 从 $C_r$ 挪到 $C_{r'}$ 。它的系数只在 $I$ 的 $b$ 个子区间里变：在别的区间看来，它仍然在同一侧。它在 $a_k$ 里的系数是 $1$ 、 $\frac12$ 或 $0$ ，挪了之后还是这三个数之一，所以 $a_k(y)\ \text{的变化}=e_k\,\one_{\{V_i\le y\}},\qquad|e_k|\le1,$ 其中 $e_k$ 是 $\chi_i$ 乘以新旧系数之差。这是一个只在高度 $V_i$ 处跳一次的阶梯函数。
高度不在块里。看第 $j+1$ 阶段的一个小矩形 $C_k\times B$ $B$ ， $B$ 是一个新块。如果 $V_i\notin B$ $B$ ，那么 $B$ 要么整个在 $V_i$ 下面，要么整个在它上面，上面那个变化在 $B$ 上是常数。振荡不怕加常数， $\operatorname{osc}_B\,a_k$ 不变。
高度在块里。变化在 $B$ 上只取 0 和 $e_k$ 两个值，它自己的振荡是 $|e_k|\le1$ $1$ 。由反向三角不等式， $\operatorname{osc}_B\,a_k$ 的变化不超过 1。
合计。含 $V_i$ 的新块只有一个，记作 $J$ 。受影响的小矩形就是 $C_1\times J,\dots,C_b\times J$ 这 $b$ 个，它们合起来是比较矩形 $I\times J$ $J$ 。 $Z_{j+1}$ 是 $bM$ 个振荡之和除以 $bM$ ，所以至多变 $\frac b{bM}$ 。

这里看得出为什么要量振荡。固定已揭示信息，改变一个点的下一位横坐标数字，会改变它上方所有高度上的 $a_k$ 都变了，受影响的块可能有很多。但其中只有一个块的振荡会变，其余的块只是整体平移了一下。如果量的是 $|a_k|$ 的最大值，这些块就都得算进去。

不管怎么挪，标出来的格子都在同一行，也就是那个点所在的块；变化量的绝对值之和不超过 $b=4$ $4$ 。到这里，关于“细分一步”的两件事都齐了：

平均引理 2.3：每个比较矩形里的振荡之和，平均至少多出

\frac14\sqrt{m_R}

。

影响改一个点的下一位数字，只有它所在的那个比较矩形里的振荡之和会变，至多变

b

；

Z_{j+1}

至多变

\frac1M

。

§ 16 · 核心推导把 $h$ 层接起来：计划、条件增益和波动

前三节只看一个比较矩形、一次细分。现在回到第 12 节的 $Z_0,Z_1,\dots,Z_h$ ，把 $h$ 层接起来。这一节先列出剩下的计划，然后完成其中两步：引理 2.4 说每一层平均涨多少，引理 2.6 说实际的涨幅很难比平均值低太多。

第一步：把涨幅拆成“条件增益”和“波动”

$Z_j$ 由 $\mathcal F_j$ 决定。所以每一层的实际涨幅可以写成两段：

Z_{j+1}-Z_j=\underbrace{\EE\bigl[Z_{j+1}-Z_j\bigm|\mathcal F_j\bigr]}_{\text{条件增益：这一层平均涨多少}}+\underbrace{\bigl(Z_{j+1}-\EE[Z_{j+1}\mid\mathcal F_j]\bigr)}_{\text{波动：实际值减去平均值}}.

对 $j=0,\dots,h-1$ 求和：

初值、条件增益和波动项论文式 (10)

Z_h=Z_0+\sum_{j<h}\EE\bigl[Z_{j+1}-Z_j\bigm|\mathcal F_j\bigr]+T,\qquad T=\sum_{j<h}\bigl(Z_{j+1}-\EE[Z_{j+1}\mid\mathcal F_j]\bigr).\tag{10}

$\EE[Z_{j+1}-Z_j\mid\mathcal F_j]$ 叫做第 $j$ 层的条件增益（conditional gain）， $T$ 叫做波动项（fluctuation term）。由式 (9)， $Z_0\ge0$ $0$ ， $Z_h\le2\norm F_\infty$ $2 ∥ F ∥_{\infty}$ 。所以只要右边后两项合起来很大， $\norm F_\infty$ 就很大。剩下的证明分三步：

(a)每一层的条件增益至少是一个数

\delta_j

，它只依赖点的位置，不依赖染色。引理 2.4，本节。

(b)

M\le n

且

b

很大时，除了一个指数小的概率，每个

\delta_j

都很大。引理 2.5，第 17 节。

(c)对一种固定的染色，波动项

T

很难是一个很大的负数。引理 2.6，本节。

命题 2.7（第 18 节）把三步合起来，再对所有染色用并集界。

第二步：每一层平均涨多少

第 $j$ 层有 $M$ 个比较矩形，面积都是 $\frac1M$ 。和第 13 节一样，比较矩形 $R$ 的内部区域是 $R$ 去掉最低和最高的旧小矩形， $m_R$ 是里面的点数。

引理 2.4（条件增益）论文 Lemma 2.4

对 $0\le j<h$ $h$ ，以概率 1，

\EE\bigl[\,Z_{j+1}-Z_j\bigm|\mathcal F_j\bigr]\ \ge\ \delta_j:=\frac1{4bM}\sum_R\sqrt{m_R},\tag{11}

求和遍历第 $j$ 层的 $M$ 个比较矩形。

推导引理 2.4

按比较矩形分组。每个旧的小矩形是恰好一个比较矩形的横条，每个新的小矩形是恰好一个比较矩形的竖条： $R=I\times J$ 里有 $b$ 个旧的 $I\times B_\ell$ 和 $b$ 个新的 $C_k\times J$ $J$ 。所以 $bM\,(Z_{j+1}-Z_j)=\sum_R\Bigl(\sum_k\operatorname{osc}_J\,a_{C_k}-\sum_\ell\operatorname{osc}_{B_\ell}\,a_I\Bigr).$
每个比较矩形里是一次局部实验。在 $\mathcal F_j$ 已知的条件下：各点的高度已知；每个点相对每个旧区间 $I$ 的位置已知； $I$ 里面的点，下一位数字是独立、均匀的骰子，决定它落进哪个子区间。这正是第 14 节的局部实验，而且在所有的 $R$ 里同时进行。 $a_I$ 是旧函数， $a_{C_1},\dots,a_{C_b}$ 是子函数。
求和。对每个 $R$ 用引理 2.3，括号里的量的条件期望至少是 $\frac14\sqrt{m_R}$ 。全部加起来，除以 $bM$ ，得到 (11)。

$\delta_j$ 不是负的，所以每一层平均都不降。它有多大？如果每个内部区域里都有 $\frac nM$ 个左右的点， $M$ 个 $\sqrt{n/M}$ 加起来再除以 $4bM$ ， $\delta_j$ 大约是 $\frac1{4b}\sqrt{n/M}$ 。 $h$ 层累积起来是 $h\sqrt{n/M}$ 的量级。但“如果”不是保证，第 17 节处理它。

$\delta_j$ 还有一个特点： $m_R$ 只数点，不看颜色。所以 $\delta_j$ 对 $2^n$ 种染色都是同一个数。

式 (10) 中间那个和里的每一项至少是 $\delta_j\ge0$ $0$ 。 $T$ 里的每一项，在 $\mathcal F_j$ 已知时均值是 0，可正可负。要证 $Z_h$ 很大，只怕一件事： $T$ 是一个很大的负数，把增益吃掉了。下面证明这件事的概率极小。

第三步：有界差分

工具 · 有界的零均值随机变量

设 $c>0$ 、 $\mathbb E Y=0$ 且 $|Y|\le c$ 。则对任意实数 $t$ ， $\mathbb E e^{tY}\le\cosh(tc)\le e^{t^2c^2/2}$ 。若 $c=0$ ，则 $Y=0$ 几乎处处成立，结论直接成立。

证明：函数 $y\mapsto e^{ty}$ 是凸的，在区间 $[-c,c]$ 上它位于连接两个端点的弦的下方：

e^{tY}\le\frac{c+Y}{2c}\,e^{tc}+\frac{c-Y}{2c}\,e^{-tc}.

取期望， $\EE\,Y=0$ $0$ ，右边变成 $\frac12(e^{tc}+e^{-tc})=\cosh(tc)$ $cosh (t c)$ 。第二个不等号 $\cosh x\le e^{x^2/2}$ 在第 5 节证过。

条件期望的版本同样成立：如果在某些已知信息下 $Y$ 的条件期望是 0，并且 $|Y|\le c$ $c$ ，那么 $e^{tY}$ 的条件期望不超过 $e^{t^2c^2/2}$ 。证明一字不改，只是把 $\EE$ 都换成条件期望。

圆圈都在弦的下方，所以重心也在弦的下方，而弦在 0 处的高度正是 $\cosh(tc)$ 。只取两个端点时，重心恰好落在弦上，这是最坏的情形。再往上一点是 $e^{t^2c^2/2}$ 。把 $tc$ 调成负数，图左右翻转，结论不变。

Fact A.1（有界差分）论文附录 A.2

设 $\xi_1,\dots,\xi_n$ 相互独立，随机元素 $\Gamma$ 与向量 $(\xi_1,\dots,\xi_n)$ 独立。设 $\varphi$ 可测， $f=\varphi(\Gamma,\xi_1,\dots,\xi_n)$ 可积，且 $c>0$ 。固定 $\Gamma$ 的任意取值，只改变一个 $\xi_i$ 时， $\varphi$ 的值至多变化 $c$ 。则对任意实数 $t$ ，以概率 1，

\EE\Bigl[\exp\bigl(t\,(f-\EE[f\mid\Gamma])\bigr)\Bigm|\Gamma\Bigr]\ \le\ \exp\Bigl(\frac{n\,t^2c^2}2\Bigr).

推导Fact A.1

$\Gamma$ 和各个 $\xi_i$ 独立，所以“给定 $\Gamma$ ”就是把 $\varphi$ 的第一个变量固定成一个值 $\gamma$ 。于是只要对每个固定的 $\gamma$ ，证明不带条件的 $\EE\exp\bigl(t(f-\EE f)\bigr)\le\exp\bigl(\frac{nt^2c^2}2\bigr)$ $exp (\frac{n t ^{2} c ^{2}}{2})$ ，其中 $f=\varphi(\gamma,\xi_1,\dots,\xi_n)$ $φ (γ, ξ_{1}, \dots, ξ_{n})$ 。下面固定 $\gamma$ 。

一个一个地揭示。令 $f_i=\EE[f\mid\xi_1,\dots,\xi_i]$ $ξ_{1}, \dots, ξ_{i}]$ ，即知道前 $i$ 个变量之后对 $f$ 的最佳猜测； $f_0=\EE f$ $E f$ ， $f_n=f$ $f$ 。记 $Y_i=f_i-f_{i-1}$ $f_{i - 1}$ ，则 $f-\EE f=\sum_{i=1}^nY_i$ $\sum_{i = 1}^{n} Y_{i}$ 。
每一步的均值是 0。由“逐层平均”， $\EE[f_i\mid\xi_1,\dots,\xi_{i-1}]=f_{i-1}$ $f_{i - 1}$ ，所以 $\EE[Y_i\mid\xi_1,\dots,\xi_{i-1}]=0$ $0$ 。
每一步有界。因为变量相互独立， $f_i$ 是这样算出来的：把前 $i$ 个变量固定在揭示出的值上，对后面的变量求平均。把它看成第 $i$ 个变量的函数：第 $i$ 个变量换一个值，被平均的每一项至多变 $c$ ，所以平均值也至多变 $c$ 。而 $f_{i-1}$ 是这个函数再对第 $i$ 个变量求平均。一个取值范围不超过 $c$ 的函数，离它自己的平均值不会超过 $c$ 。所以 $|Y_i|\le c$ $c$ 。
从最后一个往前剥。 $Y_1,\dots,Y_{n-1}$ 由 $\xi_1,\dots,\xi_{n-1}$ 决定，可以提出来；对 $Y_n$ 用上面工具的条件期望版本： $\begin{aligned}\EE\,e^{t\sum_{i\le n}Y_i}&=\EE\Bigl[e^{t\sum_{i<n}Y_i}\cdot\EE\bigl[e^{tY_n}\bigm|\xi_1,\dots,\xi_{n-1}\bigr]\Bigr]\\[4pt]&\le e^{t^2c^2/2}\cdot\EE\,e^{t\sum_{i<n}Y_i}.\end{aligned}$ 重复 $n$ 次，得到 $\exp\bigl(\frac{nt^2c^2}2\bigr)$ 。

这是有界差分不等式（McDiarmid）的矩母函数形式，证明用的是 Azuma 的鞅论证；标准版本的常数更好，这里用不着。像 $Y_1,Y_2,\dots$ 这样“在此前揭示的一切都已知时均值为 0”的一串量，叫做鞅差。

这个例子里 $f_i$ 有现成的公式。前 $i$ 个骰子出现过 $s$ 种点数时，剩下 $8-s$ 种里的每一种，在后面 $10-i$ 个骰子里都不出现的概率是 $\bigl(\frac78\bigr)^{10-i}$ ，所以 $f_i=(8-s)\bigl(\frac78\bigr)^{10-i}$ $s) (\frac{7}{8})^{10 - i}$ 。

图和推导对得上两处。每一步有正有负：出了新点数就往下跳，点数重复就往上挪一点，两者按概率加权平均是 0，这是第 2 步。（第一个骰子例外：它一定是新点数，这一步恰好是 0。）每一步都落在浅色竖条里，这是第 3 步。再做 30 轮，终点散在 $\EE f$ 两侧一个不大的范围里。

第四步：波动项很难是大的负数

引理 2.6（波动）论文 Lemma 2.6

固定一种染色， $T$ 是式 (10) 里的波动项。则对任意 $\lambda>0$ $0$ ，

\Pr[\,T\le-\lambda\,]\ \le\ \exp\Bigl(-\frac{\lambda^2M^2}{2hn}\Bigr).\tag{13}

推导引理 2.6

把第 $j$ 层的波动记作 $T_j=Z_{j+1}-\EE[Z_{j+1}\mid\mathcal F_j]$ $F_{j}]$ ，于是 $T=T_0+\dots+T_{h-1}$ $T_{h - 1}$ 。

一位数字。改变一个点的下一位数字， $Z_{j+1}$ 至多变 $\frac1M$ 。这是第 15 节。
一层。 $Z_{j+1}$ 是 $n$ 个下一位数字的函数，另外还依赖 $\mathcal F_j$ 里的信息（各点的高度和前 $j$ 位数字）。这 $n$ 个数字相互独立，也和 $\mathcal F_j$ 独立。用 Fact A.1： $\Gamma$ 取 $\mathcal F_j$ 里的信息， $\xi_1,\dots,\xi_n$ 取下一位数字， $c=\frac1M$ $\frac{1}{M}$ ，再把 $t$ 换成 $-t$ 。对任意 $t>0$ $0$ ， $\EE\bigl[e^{-tT_j}\bigm|\mathcal F_j\bigr]\ \le\ \exp\Bigl(\frac{n\,t^2}{2M^2}\Bigr).$
$h$ 层连乘。 $T_0,\dots,T_{h-2}$ 在 $\mathcal F_{h-1}$ 已知时都已经定了，可以提出来： $\EE\,e^{-tT}=\EE\Bigl[e^{-t(T_0+\dots+T_{h-2})}\cdot\EE\bigl[e^{-tT_{h-1}}\bigm|\mathcal F_{h-1}\bigr]\Bigr]\le\exp\Bigl(\frac{n\,t^2}{2M^2}\Bigr)\cdot\EE\,e^{-t(T_0+\dots+T_{h-2})}.$ 再对 $\mathcal F_{h-2}$ 、 $\mathcal F_{h-3}$ 一直到 $\mathcal F_0$ 这样做，得到 $\EE\,e^{-tT}\le\exp\bigl(\frac{hn\,t^2}{2M^2}\bigr)$ $exp (\frac{hn t ^{2}}{2 M ^{2}})$ 。
Markov 不等式，再选 $t$ 。和第 5 节一样，“ $T\le-\lambda$ $- λ$ ”就是“ $e^{-tT}\ge e^{t\lambda}$ $e^{t λ}$ ”，所以 $\Pr[T\le-\lambda]\le e^{-t\lambda}\cdot\EE\,e^{-tT}\le\exp\Bigl(-t\lambda+\frac{hn\,t^2}{2M^2}\Bigr).$ 指数是 $t$ 的二次函数，在 $t=\frac{\lambda M^2}{hn}$ 处最小，最小值是 $-\frac{\lambda^2M^2}{2hn}$ 。

这一步不需要各层之间独立。给定每一层的已知信息，下一位数字是相互独立的骰子，改变其中一位， $Z_{j+1}$ 至多变 $\frac1M$ 。先对这一层用条件期望形式的指数矩界，再逐层取条件期望， $h$ 层各贡献一个因子 $\exp\bigl(\frac{n\,t^2}{2M^2}\bigr)$ ，式 (13) 的指数里的 $hn$ 和 $M^2$ 就是这么累积出来的。

易错

不能把这个论证简化成“ $T$ 是 $hn$ 位数字的函数，每一位的影响至多 $\frac1M$ ”。改变较早的一位数字，会连带改变后面各层的 $Z$ 和条件期望，对 $T$ 的影响可以超过 $\frac1M$ 。一个小例子： $b=3$ $3$ 、 $h=2$ $2$ 、 $n=3$ $3$ ，所以 $M=3$ $3$ ；颜色 $(+1,-1,+1)$ ，纵坐标 $(\frac1{10},\frac34,\frac{19}{20})$ ，横坐标 $(\frac{11}{18},\frac1{18},\frac12)$ 。把第二个点的横坐标改成 $\frac{13}{18}$ ，也就是把它的第一位数字从 1 改成 3，其余不动。直接按定义算， $T$ 从 $\frac{14}{81}$ 变成 $-\frac{22}{81}$ ，变了 $\frac49>\frac13$ $\frac{1}{3}$ 。

所以界是逐层用的：每一层只让当前这一位数字变动，此前的数字都算作已知。

式 (13) 是对一种固定的染色说的： $Z_j$ 依赖染色，换一种染色， $T$ 就是另一个随机变量。要对付全部 $2^n$ 种染色，右边得乘上 $2^n$ ，所以 $\lambda$ 要取得让指数 $\frac{\lambda^2M^2}{2hn}$ 比 $n\ln2$ 大。第 18 节做这件事。

后面两节的走向。

\delta_*

是第 17 节定义的一个数，量级是

\sqrt{n/M}

。用于下界各层条件增益的好事件只依赖点的位置，对所有染色统一处理；条件增益本身仍可依赖染色。右边的波动项逐个染色处理，再做并集界。

取 $b=8$ $8$ 、 $h=3$ $3$ ，所以 $M=64$ $64$ 。随机撒 $n$ 个点，选一种染色方式，算出 $Z_0,\dots,Z_3$ 。折线从 $Z_0$ 出发，把各层的 $\delta_j$ 逐层加上去；折线每一段升高的量，是这一层条件增益的下界。表里后两列是第 17 节的内容：这一层有多大比例的点落在不重的内部区域里（至少一半就是好层），以及好层保证的下界 $\delta_*$ 。“多撒几十组”会重复实验，看 $Z_h$ 最小能到多少。

图里有三件事可以留意，说的都是眼前这组样本。第一， $Z_j$ 逐层上升，每一层的涨幅都远高于 $\delta_j$ ，表里可以直接对比。要记住 $\delta_j$ 是条件期望的下界：单次实现的涨幅没有这样的保证，甚至可以是负的。第二，换成沿 Z 形曲线交替的染色， $\max|F|$ 小了很多， $Z_h$ 也跟着变小，但在这组样本上各层仍然在涨。第三，重复几十组，这些样本里 $Z_h$ 的最小值和平均值在同一个量级，没有哪一组掉到接近 0。这只是有限次实验的观察，说明不了尾概率； $e^{-cn}$ 这么小的概率要靠式 (13)。

§ 17 · 进阶点不会太挤：重的区域和好层

式 (11) 里的 $\delta_j=\frac1{4bM}\sum_R\sqrt{m_R}$ $\frac{1}{4 b M} \sum_{R} m_{R}$ ，在每个内部区域里都有 $\frac nM$ 个左右的点时，大约是 $\frac1{4b}\sqrt{n/M}$ 。但这不是保证。如果点扎堆挤在少数几个内部区域里，或者大量落在各个比较矩形最低、最高的旧小矩形里，这个和就会很小；极端情况下所有点都不在内部区域里， $\delta_j=0$ $0$ 。这一节证明： $M\le n$ 时，除了一个指数小的概率，每一层都能留住这个数的一个只依赖 $b$ 的比例。这是第 16 节计划里的 (b)。

重的区域，好层

一个比较矩形里平均有 $\frac nM$ 个点。固定第 $j$ 层，对它的 $M$ 个比较矩形定义：

重内部区域里的点数

m_R

超过

\dfrac{bn}M

，即超过一个比较矩形的平均点数的

b

倍，就说这个内部区域是重的（heavy）。

好层如果至少有

\dfrac n2

个点落在不重的内部区域里，就说这一层是好层（论文：the transition is good）。

好层说的是：至少一半的点摊得足够开。记 $G_j$ 为“第 $j$ 层是好层”这个事件， $G=G_0\cap\dots\cap G_{h-1}$ 为“ $h$ 层都是好层”。它们只看点的位置，与染色无关。再记

好层保证的下界论文式 (12)

\delta_*=\frac1{8\,b^{3/2}}\sqrt{\frac nM}.\tag{12}

它是“理想值” $\frac1{4b}\sqrt{n/M}$ 的 $\frac1{2\sqrt b}$ 倍。

引理 2.5（好层）论文 Lemma 2.5

设 $0\le j<h$ $h$ 。

(i) 在 $G_j$ 上， $\delta_j\ge\delta_*$ $δ_{*}$ 。

(ii) 如果 $M\le n$ $n$ ，那么 $\Pr[\,G_j\ \text{不发生}\,]\le\bigl(\frac{48}b\bigr)^{n/2}$ $(\frac{48}{b})^{n /2}$ ，于是 $\Pr[\,G\ \text{不发生}\,]\le h\bigl(\frac{48}b\bigr)^{n/2}$ $h (\frac{48}{b})^{n /2}$ 。

推导(i)：好层上

\delta_j\ge\delta_*

不重的区域里，平方根不比点数小太多。当 $0<m_R\le bn/M$ 时， $\sqrt{m_R}=m_R/\sqrt{m_R}\ge m_R/\sqrt{bn/M}$ 。当 $m_R=0$ 时，直接验证最后的不等式即可：两边都是 0。
求和。只留下不重的区域。好层上它们里面的点数之和至少是 $\frac n2$ ： $\sum_R\sqrt{m_R}\ \ge\ \frac1{\sqrt{bn/M}}\sum_{R\ \text{不重}}m_R\ \ge\ \frac n2\sqrt{\frac M{bn}}.$
除以 $4bM$ 。 $\delta_j\ge\dfrac1{4bM}\cdot\dfrac n2\sqrt{\dfrac M{bn}}=\dfrac1{8\,b^{3/2}}\sqrt{\dfrac nM}=\delta_*$ $δ_{*}$ 。

为什么要把重的区域扔掉？平方根是凹的：同样多的点，摊在很多个区域里，平方根之和大；挤在一个区域里，平方根之和小。一个区域里的点数超过平均水平的 $b$ 倍之后，多出来的点对 $\sum\sqrt{m_R}$ 几乎没有贡献，干脆不算。

一层不是好层的概率

把每个比较矩形最低和最高的旧小矩形叫做边界带（boundary strips）。每个点要么在某个内部区域里，要么在边界带里。

推导(ii)：

M\le n

时，

\Pr[\,G_j\ \text{不发生}\,]\le\bigl(\frac{48}b\bigr)^{n/2}

不是好层意味着什么。这时落在不重的内部区域里的点不到 $\frac n2$ 个。其余的点要么在重的内部区域里，要么在边界带里。所以有超过 $\frac n2$ 个点落在集合 $W$ 里， $W$ 是边界带和全部重区域的并。
重的区域不多。没有哪个点同时在两个内部区域里，而每个重区域里有超过 $\frac{bn}M$ 个点，一共只有 $n$ 个点。所以重区域少于 $n\big/\frac{bn}M=\frac Mb$ 个。
$W$ 不是固定的集合。哪些区域是重的，取决于点落在哪里。所以不能直接算“一个点落进 $W$ 的概率”。办法是把所有可能的情况都列出来：考虑每一组 $\mathcal S$ ，它由少于 $\frac Mb$ 个内部区域组成，不管里面的区域重不重。记 $W_{\mathcal S}$ 为边界带和 $\mathcal S$ 里的区域的并， $E_{\mathcal S}$ 为“至少 $\frac n2$ 个点落在 $W_{\mathcal S}$ 里”这个事件。第 1、2 步说：如果第 $j$ 层不是好层，那么取 $\mathcal S$ 为重区域的全体， $E_{\mathcal S}$ 就发生了。所以“不是好层”包含在这些 $E_{\mathcal S}$ 的并里。
$W_{\mathcal S}$ 很小。固定 $\mathcal S$ 。边界带是每个比较矩形的 $b$ 个旧小矩形里的两个，合起来面积是 $\frac2b$ 。 $\mathcal S$ 里的区域少于 $\frac Mb$ 个，每个面积不到 $\frac1M$ ，合起来不到 $\frac1b$ 。所以 $W_{\mathcal S}$ 是一个固定的集合，面积至多 $\frac3b$ 。
一组固定的点全落进去。如果 $E_{\mathcal S}$ 发生，就有 $\lceil\frac n2\rceil$ 个下标，它们对应的点全在 $W_{\mathcal S}$ 里。 $n$ 个点独立、均匀，所以指定的一组点全落进固定的 $W_{\mathcal S}$ 的概率至多是 $\bigl(\frac3b\bigr)^{\lceil n/2\rceil}\le\bigl(\frac3b\bigr)^{n/2}$ （因为 $\frac3b\le1$ $1$ ）。下标集合至多 $2^n$ 个，由并集界， $\Pr[E_{\mathcal S}]\le2^n\bigl(\frac3b\bigr)^{n/2}$ $2^{n} (\frac{3}{b})^{n /2}$ 。
对 $\mathcal S$ 用并集界。内部区域一共 $M$ 个，所以 $\mathcal S$ 至多有 $2^M$ 种选法： $\Pr[\,G_j\ \text{不发生}\,]\ \le\ 2^{M+n}\Bigl(\frac3b\Bigr)^{n/2}\ \le\ 4^n\Bigl(\frac3b\Bigr)^{n/2}=\Bigl(\frac{48}b\Bigr)^{n/2}.$ 中间用了 $M\le n$ $n$ 。再对 $h$ 层用一次并集界，就是 $\Pr[\,G\ \text{不发生}\,]$ 的界。

推导的第 1 到 4 步。灰色和红色两部分合起来面积至多

\frac3b

；不是好层，就要求一半以上的点落在这两部分里。哪些区域是红的事先不知道，所以第 6 步要对所有可能的选法用并集界。

取 $b=64$ $64$ ，一层有 $M=4096$ 个比较矩形。左图的每个小方格代表一个内部区域，颜色越深点越多，红色是重的。右边的横条把 $n$ 个点分成三份：在不重的内部区域里、在重的内部区域里、在边界带里。青色那一段过半就是好层。均匀撒点时，默认的这组样本是好层；一般情形下，引理 2.5 保证的是以极高的概率是好层。用滑块把一部分点硬挤进 16 个区域，或者硬塞进边界带，看要挤到什么程度才不再是好层。

试一下三个预设。均匀撒点的这组样本里没有重的区域， $97\%$ 左右的点在不重的内部区域里。挤 40% 的点进 16 个区域：这 16 个区域都变红了，但剩下的点仍然过半，还是好层， $\delta_j$ 仍然不小于 $\delta_*$ 。挤进去的比例过了一半左右就不再是好层，第三个预设取的是 60%。要让随机撒的点自己变成这样，概率不超过最后一个读数， $b=64$ $64$ 、 $n=M$ 时是 $2^{-850}$ 左右。

有三点值得停一下。第一，这里随机的是点的位置，而“好层”只和位置有关。所以 $G$ 对 $2^n$ 种染色是同一个事件，只需要排除一次。第二， $M\le n$ 这个条件用在第 6 步： $\mathcal S$ 的选法有 $2^M$ 种，要让 $\bigl(\frac3b\bigr)^{n/2}$ 压得住， $M$ 不能比 $n$ 大。第三，各层的内部区域形状不同，各层是不是好层并不独立；证明只对 $h$ 层用了并集界，用不着独立性。

§ 18 · 核心推导收尾：定理 1.1

定理 1.1 的陈述在第 8 节。

三步合起来：命题 2.7

第 16 节计划里的 (a)(b)(c) 都有了。对一种染色 $\chi$ ，考虑两个事件：

事件一

G

不发生：有某一层不是好层。这件事只和点的位置有关，与染色无关。

M\le n

时概率至多

h\bigl(\frac{48}b\bigr)^{n/2}

（引理 2.5）。

事件二染色

\chi

的波动项

T\le-\lambda

- λ

，其中

\lambda=\frac14h\delta_*

\frac{1}{4} h δ_{*}

。这件事和染色有关。概率由引理 2.6 控制。

命题 2.7（对所有染色同时成立的概率界）论文 Proposition 2.7

设 $M\le n$ $n$ 。则

\Pr\Bigl[\,\text{存在}\ \chi\ \text{使}\ \norm{F_\chi}_\infty\le\frac h{64\,b^{3/2}}\sqrt{\frac nM}\,\Bigr]\ \le\ h\Bigl(\frac{48}b\Bigr)^{n/2}+2^n\exp\Bigl(-\frac{hM}{2048\,b^3}\Bigr).\tag{14}

推导命题 2.7

左边的门槛就是 $\frac18h\delta_*$ 。先固定一种染色，并设 $G$ 发生，而 $\norm F_\infty\le\frac18h\delta_*$ $\frac{1}{8} h δ_{*}$ 。

条件增益之和。在 $G$ 上，每一层的条件增益至少是 $\delta_j$ （引理 2.4），而 $\delta_j\ge\delta_*$ （引理 2.5 (i)）。由式 (10) 和 $Z_0\ge0$ $0$ ， $Z_h\ \ge\ h\,\delta_*+T.$
$F$ 很小就逼出事件二。由式 (9)， $Z_h\le2\norm F_\infty\le\frac14h\delta_*$ $\frac{1}{4} h δ_{*}$ 。和第 1 步合起来， $T\le-\frac34h\delta_*$ $- \frac{3}{4} h δ_{*}$ ，更有 $T\le-\lambda$ $- λ$ ， $\lambda=\frac14h\delta_*$ $\frac{1}{4} h δ_{*}$ 。论文只用后者，常数没有优化。
事件二的概率。由 (12)， $\delta_*^2=\frac n{64\,b^3M}$ $\frac{n}{64 b ^{3} M}$ 。在 (13) 里代入这个 $\lambda$ ： $\frac{\lambda^2M^2}{2hn}=\frac{h\,\delta_*^2M^2}{32\,n}=\frac{hM}{2048\,b^3}.$ 所以 $\Pr\bigl[\,G\ \text{发生且}\ \norm F_\infty\le\frac18h\delta_*\,\bigr]\le\exp\bigl(-\frac{hM}{2048b^3}\bigr)$ $exp (- \frac{h M}{2048 b ^{3}})$ 。
并集界。如果存在一种染色使 $\norm{F_\chi}_\infty\le\frac18h\delta_*$ $\frac{1}{8} h δ_{*}$ ，那么要么 $G$ 不发生，要么 $G$ 发生而这种染色的 $F_\chi$ 很小。前一个事件只有一个；后一类事件每种染色有一个，共 $2^n$ 个： $\Pr\bigl[\exists\chi:\ \norm{F_\chi}_\infty\le\tfrac18h\delta_*\bigr]\le\Pr[\,G\ \text{不发生}\,]+\sum_\chi\Pr\bigl[\,G\ \text{发生且}\ \norm{F_\chi}_\infty\le\tfrac18h\delta_*\bigr].$ 代入引理 2.5 (ii) 和第 3 步。

右边的两项，只有第二项乘了 $2^n$ 。事件一是所有染色共用的，排除一次就够了。

选参数

现在把 $b$ 、 $h$ 定下来，目标是让 (14) 的右边不超过 $e^{-An}$ ，同时让左边的门槛至少是 $c_A(\log_2n)^{3/2}$ 。给定 $A>0$ $0$ ，取整数 $b$ 大到满足两个条件（ $\ln$ 是自然对数，论文写作 $\log$ ）：

\frac12\ln\frac b{48}\ \ge\ A+2,\qquad\frac b{4096}\ \ge\ A+2+\ln2.\tag{15}

这样的 $b$ 只依赖 $A$ ，而且 $b>48$ $48$ ，所以 $64\le b^4$ $b^{4}$ 。再取

c_A=\frac{b^{-8}}{(1+\log_2b)^{3/2}}.

对每个 $n\ge1$ $1$ ，取 $h$ 为满足 $b^{-5}h\,b^{h-1}\le n$ 的最大正整数，并令 $M=b^{h-1}$ $b^{h - 1}$ 。 $h=1$ 时左边是 $b^{-5}\le1$ $1$ ，而左边随 $h$ 增大趋于无穷，所以这样的 $h$ 存在。

参数之间的关系论文式 (16)、(17)、(18)

b^{-5}hM\ \le\ n\ <\ 2\,b^{-4}hM,\tag{16}

\log_2n\ <\ (1+\log_2b)\,h,\tag{17}

c_A(\log_2n)^{3/2}\ <\ b^{-8}h^{3/2}.\tag{18}

推导式 (16)、(17) 和 (18)

(16) 左边的不等式是 $h$ 的定义。 $h$ 是最大的，所以 $h+1$ 不满足条件： $n<b^{-5}(h+1)b^h$ $1) b^{h}$ 。用 $h+1\le2h$ 和 $b^h=bM$ $b M$ ，得到 $n<2h\,b^{-4}M$ $2 h b^{- 4} M$ ，这是 (16) 的右边。对同一个不等式用 $h+1\le2^h$ 和 $b^{-5}\le1$ $1$ ： $n<(2b)^h$ $(2 b)^{h}$ ，取以 2 为底的对数就是 (17)。把 (17) 两边取 $\frac32$ 次方，再乘上 $c_A$ ，就是 (18)。

式 (16) 说，一个比较矩形里的平均点数 $\frac nM$ 在 $b^{-5}h$ 和 $2b^{-4}h$ 之间，是 $h$ 的量级。式 (17) 说 $h>\frac{\log_2n}{1+\log_2b}$ $\frac{l o g _{2} n}{1 + l o g _{2} b}$ ，至少是 $\log n$ 的量级；反过来 $h$ 也不会更大，因为它的定义要求 $b^{-5}h\,b^{h-1}\le n$ $n$ 。

为什么是 $b^{-5}$ ？(16) 的下界让 (14) 的门槛至少是 $\frac{h^{3/2}}{64b^4}$ 。上界让 (14) 最后那个指数超过 $\frac{bn}{4096}$ ， $b$ 够大时压得住 $2^n$ 。如果换成 $b^{-4}$ ，这个指数只能保证超过 $\frac n{4096}$ ，对付不了 $2^n$ 种染色。

为什么密度 $\frac nM$ 取 $h$ 的量级？密度再大一些，每个 $\delta_j$ 会更大。但取 $\lambda$ 为总增益的量级时，(13) 的指数是 $hM$ 的量级（ $b$ 固定），和密度无关；它必须超过 $n\ln2$ 。所以 $n$ 至多是 $hM$ 的量级，密度至多是 $h$ 的量级。

定理 1.1 的证明

推导分两种情形

情形一： $M>n$ $n$ 。命题 2.7 需要 $M\le n$ $n$ ，这种情形要另外处理。由 (16)， $b^{-5}hM\le n<M$ $M$ ，所以 $h<b^5$ $b^{5}$ ；由 (18)， $c_A(\log_2n)^{3/2}<b^{-8}\cdot b^{15/2}<1$ $1$ 。于是只要找一个锚定矩形，在任何染色下差都是 1。以概率 1 各点的高度互不相同，最低的点只有一个，锚定矩形 $[0,1]\times[0,\min_iV_i]$ 里只有它，颜色和是 $\pm1$ 。定理在这种情形下以概率 1 成立。
情形二： $M\le n$ $n$ 。式 (14) 右边的第一项。这时 $h\le2^{h-1}\le M\le n$ $n$ 。由 (15) 的第一个条件， $\bigl(\frac{48}b\bigr)^{n/2}=\exp\bigl(-\frac n2\ln\frac b{48}\bigr)\le e^{-(A+2)n}$ $e^{- (A + 2) n}$ ，所以第一项至多是 $n\,e^{-(A+2)n}$ 。
第二项。由 (16)， $hM>\frac12nb^4$ $\frac{1}{2} n b^{4}$ ，所以 $\frac{hM}{2048\,b^3}>\frac{bn}{4096}\ge(A+2+\ln2)\,n$ $ln 2) n$ ，用的是 (15) 的第二个条件。于是 $2^n\exp\bigl(-\frac{hM}{2048b^3}\bigr)\le e^{n\ln2}\cdot e^{-(A+2+\ln2)n}=e^{-(A+2)n}$ $e^{- (A + 2) n}$ 。
相加。(14) 的右边不超过 $(n+1)\,e^{-(A+2)n}=(n+1)e^{-2n}\cdot e^{-An}\le e^{-An}$ $e^{- A n}$ ，因为 $n+1\le e^{2n}$ $e^{2 n}$ 。
换算成 $\log n$ 。在这个例外事件之外，每一种染色都满足 $\norm{F_\chi}_\infty>\frac h{64\,b^{3/2}}\sqrt{\frac nM}\ \ge\ \frac h{64\,b^{3/2}}\sqrt{\frac h{b^5}}=\frac{h^{3/2}}{64\,b^4}\ \ge\ b^{-8}h^{3/2}\ >\ c_A(\log_2n)^{3/2}.$ 依次用到 (16) 的 $\frac nM\ge\frac h{b^5}$ $\frac{h}{b ^{5}}$ 、 $64\le b^4$ $b^{4}$ 、以及 (18)。

第 5 步是指数 $\frac32$ 最后出现的地方：门槛是 $h\cdot\sqrt{n/M}$ $n / M$ ，而 $\frac nM$ 至少是 $h$ 的一个常数倍，所以门槛是 $h^{3/2}$ 的量级。第 4 步解释了 (15) 里为什么是 $A+2$ 而不是 $A$ ：多出来的 $e^{-2n}$ 用来吃掉因子 $n+1$ $1$ ，它来自第一项前面的 $h\le n$ 和第二项。

把式 (14) 右边出现的每个因子都写成 $e^{(\,\cdot\,)n}$ 的形式，只看括号里的数。两个事件各记一本账。事件一的两行代价来自引理 2.5 的证明： $\mathcal S$ 的 $2^M\le2^n$ 种选法，和下标集合的 $2^n$ 种选法。事件二要对 $2^n$ 种染色用并集界，所以有一行 $\ln2$ 。两个小计都不超过 $-(A+2)$ 时，证明的第 2 到 4 步就走得通。第一项前面的因子 $h$ 不是指数级的，没有记进账里。为了方便拖动，这里取 $b=2^L$ $2^{L}$ ；论文只要求 $b$ 是整数。

两本账各有代价和收益。事件一的收益是 $\frac12\ln\frac b3$ ，随 $b$ 只按对数增长；事件二的收益是 $\frac b{4096}$ ，随 $b$ 线性增长，但起步晚。 $A$ 小的时候，卡住的是事件二： $A=0.5$ 时它要求 $b\ge13080$ $13080$ ，而事件一只要 $b\ge7124$ $7124$ 。 $A$ 大的时候反过来，卡住的是事件一，因为对数增长得慢。两个小计都能随 $b$ 增大而变得任意地负，这就是定理里的 $A$ 可以任意大的原因：想要多小的失败概率，就把底数 $b$ 取多大。

拖动点数可以看到： $h$ 大约是 $\frac{\log_2n}{\log_2b}$ ，随 $n$ 增长得很慢。 $\frac nM$ 本身是锯齿状的： $n$ 增大时它跟着涨， $h$ 每加 1 它就掉到原来的 $\frac1b$ ；但它始终夹在带子里，而带子随 $h$ 缓慢上移。带子越过 1，需要 $h$ 达到 $\frac12b^4$ 到 $b^5$ 的量级。最后一个读数展示表达式 $b^{-8}h^{3/2}$ ，它超过 1 还要更晚。图中 b = 16,…,256 不满足式 (15)，这里只演示尺度变化，不给出定理的概率保证。定理要求的 $b$ 上万，图的形状和这里一样，只是横轴要拉长很多，下面“关于常数”给出了具体的数。

这就证完了定理 1.1。随机点集以正概率满足结论，而且以概率 1 各点互不相同，所以存在 $n$ 点集使任何染色在某个锚定矩形上的差至少是 $c_A(\log_2n)^{3/2}$ 。和 Nikolov 的上界合起来：

\Delta_2(n)=\Theta(\log^{3/2}n).

关于常数

证明给出的常数很小。以失败概率 $2^{-n/2}$ 为例，即 $A=\frac12\ln2$ $\frac{1}{2} ln 2$ ：满足 (15) 的最小的整数是 $b=12451$ $12451$ ，这时 $c_A\approx2^{-114.6}$ $2^{- 114.6}$ 。下界 $c_A(\log_2n)^{3/2}$ 要超过 1，需要 $\log_2n$ 大于 $c_A^{-2/3}\approx2^{76.4}$ $2^{76.4}$ 。在此之前，定理给出的界还不到 1，不如“差至少是 1”这件平凡的事。

这在渐近结果里很常见：定理确定的是增长的量级，不是具体数值。论文在定理后面直接说了：没有去优化 $c_A$ ，它非常小，所以这个界只对很大的 $n$ 有意义。

Part V · 第 19–22 节

回顾

证明走完了。这一部分先把 $\frac32$ 这个指数的账重新对一遍，再回答开头的三个问题，然后看还有什么没解决。最后附上依赖图、记号表和文献。

§ 19 · 进阶 $\frac32$ 的账

证明里有三个数在起作用：

h

层数，也就是从一个阶段到下一个阶段的过渡次数。由 (17)，它是

\log n

的量级。

\delta_*\asymp\sqrt{n/M}

每过一个好层，

Z

的条件增益至少是

\delta_*=\frac1{8b^{3/2}}\sqrt{n/M}

\frac{1}{8 b ^{3/2}} n / M

。

\frac nM

是一个比较矩形里的平均点数。

\frac nM\asymp h

参数的选择，式 (16)。于是每个好层涨

\sqrt h

的量级，

h

层都是好层，合计

h\cdot\sqrt h=h^{3/2}

h^{3/2}

。

\norm{F_\chi}_\infty\ >\ \frac{h\,\delta_*}8=\frac h{64\,b^{3/2}}\sqrt{\frac nM}\ \asymp\ h^{3/2}\ \asymp\ (\log n)^{3/2}.

$\frac{h\delta_*}8$ 里的 8 是这样来的：如果 $\norm{F_\chi}_\infty$ 不超过它，那么 $Z_h\le2\norm{F_\chi}_\infty\le\frac{h\delta_*}4$ $\frac{h δ _{*}}{4}$ ，离条件增益之和 $h\delta_*$ 还差 $\frac34h\delta_*$ ，这个差只能由波动项来补。论文只用了其中的 $\frac14h\delta_*$ ，常数没有优化。

为什么 $\frac nM$ 不能取得更大

每层的涨幅是 $\sqrt{n/M}$ ，看起来 $\frac nM$ 越大越好。限制来自并集界。式 (13) 里取 $\lambda=\frac{h\delta_*}4$ $\frac{h δ _{*}}{4}$ ，指数是 $\frac{hM}{2048b^3}$ ；要压住 $2^n$ 种染色，它必须比 $n\ln2$ 大。所以 $hM$ 至少要是 $n$ 的 $b^3$ 的若干倍，也就是

\frac nM\ \lesssim\ \frac h{b^3}.

第 18 节的取法 $\frac nM<\frac{2h}{b^4}$ 在这个范围里，还留了一个因子 $b$ 的余量，用来把失败概率压到 $e^{-An}$ 。论文在引言里是这样说的：密度再大，每层的增益会更大；但对总增益量级的偏离，波动的估计给出的指数是 $hM$ 的量级，不管密度是多少，而它必须超过 $n\ln2$ 。所以密度 $\frac nM$ 取 $h$ 的量级，已经是这个论证允许的最大值。

一句话的直观

每一层有 $M$ 个比较矩形， $h$ 层共 $hM$ 个。对一种固定的染色， $Z_h$ 要异常地小，大多数比较矩形里的随机和都得碰巧抵消掉。如果把这 $hM$ 个矩形当成各自独立、每个碰巧的概率是个常数，合起来大约是 $e^{-c\,hM}$ 。染色有 $2^n$ 种可挑，并集界要求 $2^n\cdot e^{-c\,hM}$ 很小，所以要 $hM\gtrsim n$ $n$ ，即 $\frac nM\lesssim h$ $h$ 。

这只是关于尺度的启发式说法：各个比较矩形、各层之间并不独立。证明用的是第 16 节逐层迭代的条件指数矩界，也就是式 (13)：取 $\lambda$ 为总增益的量级时，它右边的指数正好是 $hM$ 的常数倍。

和连续差异度对比一下。第 6 节的二进网，每个二进条带的误差不超过 1， $\log n$ 层合计 $\log n$ 。这里每一层的涨幅是 $\sqrt{\log n}$ 的量级，合计 $\log^{3/2}n$ 。两个问题相差的 $\sqrt{\log n}$ ，就是每层多出来的这个平方根。

和第 9 节的猜测对账

第 9 节用布朗单的小球估计猜出了尺度。现在把证明里的参数翻译成那边的语言。差异度的尺度是 $t\asymp h\sqrt{n/M}$ $h n / M$ ，对应的小球半径是 $\varepsilon=t/\sqrt n\asymp h/\sqrt M$ $h / M$ 。

布朗单的小球估计	这里的证明
半径 $\varepsilon$	$h/\sqrt M$
$\log(1/\varepsilon)$	$\frac12\log M-\log h$ $lo g h$ ，是 $h$ 的量级（ $b$ 是常数）
指数 $\varepsilon^{-2}\log^3(1/\varepsilon)$	$\frac M{h^2}\cdot h^3=hM\asymp n$

最后一行说，在这组参数下小球概率的指数正好是 $n$ 的量级，也就是刚好够付 $2^n$ 的并集界。两边用的是同一个“三次方”： $n\asymp\varepsilon^{-2}h^3$ $ε^{- 2} h^{3}$ 。证明没有用到布朗单，但落在了它预言的尺度上。论文第 3 节做的是第 9 节那个计算；把证明里的参数代回去对账，是这份导读加的。

§ 20 · 入门之前为什么不行，这次为什么可以

之前为什么不行

借连续差异度。转移原理只能把连续差异度的下界搬过来，而连续差异度恰好是 $\Theta(\log n)$ 。单靠这条路，到 $\log n$ 为止。
正交函数法。在第 7 节介绍的经典论证里，检验函数的收益按尺度逐层相加， $\log n$ 层各贡献一个常数。
分解范数。 $\gamma_2$ 与差异度之间的两个通用不等式各带对数因子的损失，平面上的下界一侧正好落在 $\log n$ 。

这些具体论证没有给出本文对随机点集的统一下界。这里介绍的正交函数法在组合差异度上的应用针对二进网，另外两条路线给出的坏点集藏在某个网格的子集里。二进网本身就能染到 $O(\log n)$ （见第 7 节），在它上面不可能证出更多。

这次为什么可以

换点集点随机撒。二进网这样的点集可以让各层尺度的误差同时很小；随机点的每一位数字都是新掷的骰子，每一层都带来新的起伏。

换问法一次固定一种染色，估计它“染得好”的概率，再对

2^n

种染色用并集界。这要求概率小到

e^{-cn}

，而且

c

要足够大。

换一个量不直接盯着

F

的最大值，改看局部振荡

Z_j

。在好层上，它的条件期望增益至少为

\delta_*=(8b^{3/2})^{-1}\sqrt{n/M}

。固定已揭示的信息，只改变一个点新揭示的下一位横坐标数字，

Z_{j+1}

至多变化

1/M

。

初等的概率Cauchy–Schwarz（论文用 Hölder）、有界差分不等式、Markov 不等式和并集界。全程只用到阶梯函数的最大最小值和条件平均。论文摘要里说，这个证明“出人意料地简单和初等”。

	旧方法	本文
点集	二进网，或者某个网格的子集	随机撒点
怎样对付全部 $2^n$ 种染色	对每种染色给出证据（检验函数、分解范数）	对每种染色估计“染得好”的概率，再用并集界
需要的关键估计	检验函数的内积、矩阵的分解范数	局部振荡的平均涨幅和单点影响
各层尺度的贡献	常数，合计 $\log n$	$\sqrt{\log n}$ ，合计 $\log^{3/2}n$

和旧方法的联系也值得一提。“横向变细、纵向变粗、面积不变”的矩形族，正是 Roth 和 Halász 的正交函数法里用的那一族。论文在相关工作里还指出了和 Talagrand 证明布朗单小球估计的联系：Talagrand 的证明里有一个确定性的递推，在一个坐标方向上取平均，在另一个方向上挑代表点；论文的局部比较用的是同样的一对相反的尺度。对子函数取平均，在期望意义下保住了旧函数；内部区域里的点带来的独立对称增量提供了增益。端点平均 $a_I$ 则是 Talagrand 那里“横向取平均”的条件期望版本（第 13 节末尾）。

论文的四步，和这份导读的对应

论文引言把证明概括成四步。第四部分讲的就是这四步，只是顺序稍有不同：这里把“一位数字的影响”提前到了第 15 节，把好层放在了波动之后。

论文的四步	内容	论文里的位置	这份导读
(1) Potential	逐位揭示横坐标；端点平均、振荡、 $Z_j$ ； $Z_j\le2\norm F_\infty$	式 (1)–(3)、(9)	§ 10–§ 12
(2) Local gain	一个比较矩形里，竖条上的振荡之和平均比横条上多 $\frac14\sqrt{m_R}$ ；对所有比较矩形求和	引理 2.1、Fact 2.2、引理 2.3、引理 2.4	§ 13、§ 14、§ 16
(3) Good transitions	重的区域、好层； $M\le n$ 时每一层都是好层，例外的概率指数小，而且与染色无关	引理 2.5	§ 17
(4) All colorings	一位数字只让 $Z_{j+1}$ 变 $\frac1M$ ；有界差分控制波动项；对 $2^n$ 种染色用并集界；选参数	引理 2.6、Fact A.1、命题 2.7、2.5 小节（Parameters）	§ 15、§ 16、§ 18

技术清单

技术	作用	位置
随机点，逐个染色的并集界	把“每种染色都不好”化成一个固定染色的概率估计	§ 8
逐位揭示横坐标	每一层只放出 $n$ 个独立的骰子	§ 10
端点平均 $a_I$ （式 (2)）	细分之后，子函数的平均在期望意义下回到旧函数	§ 12、§ 14
局部振荡 $Z_j$ （式 (1)）	不怕加常数：对每个受影响的横向区间，只有包含该点高度的块可能改变振荡	§ 12、§ 15
纵向比较（引理 2.1，式 (4)）	$J$ 上的振荡看得见首尾两个块之间的偏移，单个块上的振荡看不见	§ 13
先平均，再比较（式 (5)、(6)）	把 $b$ 个子函数并成一个 $\bar a$ ，它等于旧函数加上各点的增量	§ 13
对称增量之和不会扎堆（Fact 2.2）	内部点的增量之和 $D$ 加上任何固定的偏移，绝对值的期望至少是 $\frac18\sqrt{m_R}$	§ 14
条件增益加波动项（式 (10)、引理 2.4）	把 $Z_h$ 写成初值、各层条件增益之和与均值为 0 的波动项；条件增益有一个与染色无关的共同下界	§ 16
有界差分（Fact A.1、引理 2.6）	波动项很难是大的负数，不需要各层独立	§ 15、§ 16
重的区域与好层（引理 2.5）	M ≤ n 时，各层以高概率同时是好层；这个事件与染色无关	§ 17

§ 21 · 入门常数、形式化验证与开放问题

显式的坏点集

证明是概率性的：它说明随机点集几乎都是坏的，却指不出一个具体的。能不能明确写出一族点集，差异度是 $\Omega(\log^{3/2}n)$ ？论文指出，主要的困难是：把独立的随机数字换成确定的选择之后，怎样保住在许多层尺度上累积起来的振荡。

高维

对 $d\ge3$ 维的盒子，已知 $\Omega_d(\log^{d-1}n)\le\Delta_d(n)\le O_d(\log^{d-1/2}n)$ $O_{d} (lo g^{d - 1/2} n)$ ，缺口同样是 $\sqrt{\log n}$ 。（第 7 节里的 $\log^{d+1/2}n$ 是分解范数方法给出的较弱的上界，Nikolov 后来把它改进到了 $\log^{d-1/2}n$ 。）Bansal 猜想 $d$ 维的答案是 $O(\log^{d-1}n)$ ；论文的定理说明这在 $d=2$ 时不对。

高维该是哪一边？把第 9 节的计算搬到 $d$ 维：布朗单的小球猜想预言指数是 $\varepsilon^{-2}\log^{2d-1}(1/\varepsilon)$ ，和 $n\ln2$ 平衡之后得到 $\log^{d-1/2}n$ ，与已知的上界吻合。论文同时强调，这个启发式的计算并不能把结论转移到有限点集上。证明方面，论文的论证用到了横向和纵向两个相反的分辨率：细分一个坐标时，一个点的影响被限制在一个纵向块里（第 15 节）。要推广到高维，需要在几个坐标同时细分或合并时找到相应的局部比较。

常数

第 18 节末尾算过，证明给出的 $c_A$ 极小： $A=\frac12\ln2$ 时 $b=12451$ $12451$ ， $c_A\approx2^{-114.6}$ $2^{- 114.6}$ ，结论要到天文数字般的 $n$ 才有实质内容。论文明确说没有优化 $c_A$ 。

形式化验证与 AI

论文末尾有一段“AI methodology statement”，大意是：作者从 2013 年起就在考虑这个问题；2026 年 7 月开始，作者与 GPT 和 Claude 交互式地研究它，先得到一个基于“killed suffix walk”的证明，后来简化成论文第 2 节和附录里的局部振荡证明；同样的工具加上 Xean 被用来检查证明和准备稿件；主要的下界定理有一份 Lean 形式化，按论文的说法由 GPT 完成；作者核实了全部内容的正确性和原创性。形式化的代码在 github.com/wzskytop/tusnady-lean，所用工具和核查记录以仓库当前的说明为准；论文在 arXiv:2610.08130。

形式化的范围要分清。它覆盖的是论文的新下界：随机点的定理 1.1，以及由它得到的确定性下界。引用的上界、由此合成的 $\Theta(\log^{3/2}n)$ 、历史叙述，以及这份导读补充的解释和交互演示，都不在形式化的范围里。

定理、引理与 Lean 声明的对应关系见仓库的论文与代码对应表。

这份导读补充了推导、例子和交互演示。它们不能代替形式化验证，也不能代替独立的审阅。

其他方向

论文在相关工作里提到两个方向。一是在线差异问题：点随机到达时，已有工作研究了区间、条带和 Tusnády 问题的在线算法。对 $[0,1]^d$ 里均匀随机到达的点，已知任何在线算法在前 $T$ 个点里以常数概率出现 $\Omega_d(\log^{d/2}T)$ 的差（Bansal–Jiang–Singla–Sinha）。定理 1.1 对任何染色都成立，在线、离线都算，所以在平面上把这个界从 $\log T$ 抬到了 $\log^{3/2}T$ 。二是数据结构：差异度和范围搜索、近似范围计数的下界有关，而本文的难例是随机的，或许能用来得到平均情形的下界。

§ 22 · 附录依赖图、记号表与文献

证明的依赖关系

记号表

记号	含义	首次出现
$P,\ n$	点集和点数	§ 1
$\chi$	染色，取值 $\pm1$ ； $\chi(P\cap R)$ 是 $R$ 内颜色之和	§ 3
$\disc(P),\ \Delta_2(n)$	点集的差异度； $n$ 个点的最坏差异度	§ 3
$D(P),\ D(n)$	连续差异度	§ 6
$P_i=(U_i,V_i)$	第 $i$ 个随机点的横坐标和纵坐标	§ 8
$F_\chi(x,y),\ \norm{F_\chi}_\infty$	锚定矩形 $[0,x]\times[0,y]$ 里的颜色和；它的最大绝对值。第 11 节起简写为 $F$	§ 8
$A,\ c_A$	失败概率 $e^{-An}$ 里的指数；定理 1.1 里的常数	§ 8
$W,\ \varepsilon$	布朗单；小球的半径	§ 9
$b,\ L$	底数，整数， $b\ge3$ $3$ ；定理的证明里取得很大（式 (15)）。第 18 节的交互里取成 2 的幂 $b=2^L$	§ 10、§ 18
$\mathcal F_j$	第 $j$ 阶段的已知信息：全部纵坐标和每个横坐标的前 $j$ 位数字	§ 10
$h,\ M$	层数：阶段编号 $j=0,\dots,h$ $0, \dots, h$ ，过渡共 $h$ 次，从阶段 $j$ 到 $j+1$ 叫第 $j$ 层（论文：transition $j\to j+1$ $1$ ）； $M=b^{h-1}$ 是每层比较矩形的个数	§ 11
$I,\ B$	第 $j$ 阶段的横向区间（宽 $b^{-j}$ ）和纵向块（高 $b^{j-h}$ ）； $I\times B$ 是小矩形（论文：cell）	§ 11
$C_k,\ J,\ R$	$I$ 的第 $k$ 个子区间（论文：child）；由 $b$ 个旧块 $B_1,\dots,B_b$ 并成的新块；比较矩形 $I\times J$	§ 11
$a_I(y),\ w_I(u)$	端点平均， $F$ 在 $I=[s,t]$ 的两个端点处的值的平均，式 (2)；论文写作 $a^{(I)}$ 。横坐标是 $u$ 的点在其中的系数（权重） $w_I(u)$ 是 $1,\frac12,0$	§ 12
$\operatorname{osc}_B\,f,\ \operatorname{mid}_B\,f$	振荡： $f$ 在 $B$ 上的最大值减最小值；中点：最大值和最小值的平均。式 (3)	§ 12
$Z_j$	局部振荡（论文：potential）：第 $j$ 阶段各小矩形上 $a_I$ 的振荡的平均，式 (1)	§ 12
$R^{\mathrm{in}},\ m_R$	$R$ 的内部区域 $I\times(B_2\cup\dots\cup B_{b-1})$ $B_{b - 1})$ ；里面的点数	§ 13
$a,\ a_k,\ \bar a$	固定 $I$ 时的简写：旧函数 $a=a_I$ $a_{I}$ ；子函数 $a_k=a_{C_k}$ $a_{C_{k}}$ ；它们的平均 $\bar a=\frac1b\sum_ka_k$	§ 13
偏移	$\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f$ $mid_{B_{1}} f$ ：最高的块相对最低的块（论文：offset）	§ 13
$r,\ X_i$	骰子的结果（点落进 $C_r$ ）；这个点的增量 $\chi_i\frac{b+1-2r}{2b}$ （论文：jump）	§ 13
$D,\ g,\ \theta$	内部点的增量之和； $\bar a$ 去掉这些增量之后的函数； $g$ 自己的偏移	§ 14
$\sigma^2$	一个增量的二阶矩 $\frac{b^2-1}{12b^2}$	§ 14
条件增益	$\EE[Z_{j+1}-Z_j\mid\mathcal F_j]$ $F_{j}]$ ：第 $j$ 层平均涨多少	§ 16
$T,\ T_j$	波动项 $\sum_j\bigl(Z_{j+1}-\EE[Z_{j+1}\mid\mathcal F_j]\bigr)$ $F_{j}])$ ，式 (10)；其中第 $j$ 层的那一项	§ 16
$\delta_j$	第 $j$ 层条件增益的下界 $\frac1{4bM}\sum_R\sqrt{m_R}$ ，式 (11)	§ 16
$\Gamma,\ \xi_i,\ \varphi,\ c,\ t$	Fact A.1 里的已知信息、独立变量、函数、单个变量的影响的上界、指数里的参数	§ 16
$\lambda$	引理 2.6 里偏离的大小；命题 2.7 里取 $\frac14h\delta_*$	§ 16、§ 18
重、好层	$m_R>\frac{bn}M$ 的内部区域是重的；至少 $\frac n2$ 个点在不重的内部区域里的层是好层	§ 17
$G_j,\ G$	第 $j$ 层是好层； $h$ 层都是好层	§ 17
$\delta_*$	好层保证的下界 $\frac1{8b^{3/2}}\sqrt{n/M}$ ，式 (12)	§ 17
边界带， $\mathcal S,\ W_{\mathcal S},\ E_{\mathcal S}$	各比较矩形最低、最高的旧小矩形；少于 $\frac Mb$ 个内部区域的一组；这一组和边界带的并；“至少一半的点在 $W_{\mathcal S}$ 里”这个事件。第 17 节里不带下标的 $W$ 是边界带和全部重区域的并，和第 9 节的布朗单无关	§ 17

文献

以下书目信息取自论文 r65 版的参考文献表；标“背景”的两条是这份导读补充的。

Z. Wei. Tight Bounds for Tusnády's Problem in the Plane. arXiv:2610.08130. 本导读讲解的论文；导读依据的是 r65 版稿件，2026-10-07 已确认其 TeX 源文件与 arXiv v1 逐字节相同。
C. Aistleitner, D. Bilyk, and A. Nikolov. Tusnády's problem, the transference principle, and non-uniform QMC sampling. MCQMC 2016（Springer，2018）.
K. Azuma. Weighted sums of certain dependent random variables. Tôhoku Mathematical Journal 19(3), 1967.
W. Banaszczyk. On series of signed vectors and their rearrangements. Random Structures & Algorithms 40(3), 2012.
N. Bansal. Discrepancy theory and related algorithms. Proceedings of the International Congress of Mathematicians 2022, Vol. 7. EMS Press, 2023.
N. Bansal and S. Garg. Algorithmic discrepancy beyond partial coloring. STOC 2017.
N. Bansal, H. Jiang, R. Meka, S. Singla, and M. Sinha. Online discrepancy minimization for stochastic arrivals. SODA 2021.
N. Bansal, H. Jiang, S. Singla, and M. Sinha. Online vector balancing and geometric discrepancy. STOC 2020.
N. Bansal and A. Nikolov. Discrepancy theory: an algorithmic and geometric perspective. arXiv:2608.00140, 2026.
R. F. Bass. Probability estimates for multiparameter Brownian processes. The Annals of Probability 16, 1988.
J. Beck. Balanced two-colorings of finite sets in the square I. Combinatorica 1(4), 1981.
J. Beck. Balanced two-colorings of finite sets in the cube. Discrete Mathematics 73, 1989.
D. Bilyk and M. Lacey. The supremum norm of the discrepancy function: recent results and connections. MCQMC 2012（Springer，2013）.
G. Bohus. On the discrepancy of 3 permutations. Random Structures & Algorithms 1(2), 1990.
G. Halász. On Roth's method in the theory of irregularities of point distributions. Recent Progress in Analytic Number Theory, Vol. 2, 1981.
H. Jiang, J. Kulkarni, and S. Singla. Online geometric discrepancy for stochastic arrivals with applications to envy minimization. arXiv:1910.01073, 2019.
K. G. Larsen. On range searching in the group model and combinatorial discrepancy. SIAM Journal on Computing 43(2), 2014.
J. Matoušek. Geometric Discrepancy: An Illustrated Guide. Springer, 1999.
J. Matoušek and A. Nikolov. Combinatorial discrepancy for boxes via the $\gamma_2$ norm. SoCG 2015.
J. Matoušek, A. Nikolov, and K. Talwar. Factorization norms and hereditary discrepancy. IMRN, 2020.
C. McDiarmid. On the method of bounded differences. Surveys in Combinatorics, 1989. Cambridge University Press, 1989.
A. Nikolov. Tighter bounds for the discrepancy of boxes and polytopes. Mathematika 63(3), 2017.
W. M. Schmidt. Irregularities of distribution. VII. Acta Arithmetica 21, 1972.
A. Srinivasan. Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems. SODA 1997.
M. Talagrand. The small ball problem for the Brownian sheet. The Annals of Probability 22(3), 1994.
Z. Wei and K. Yi. The space complexity of 2-dimensional approximate range counting. SODA 2013. 期刊版：Tight space bounds for two-dimensional approximate range counting, ACM Transactions on Algorithms, 2018.
C. Xu. Xean. GitHub 仓库，2026，github.com/chaoxu/xean.
背景：K. F. Roth. On irregularities of distribution. Mathematika 1, 1954.
背景：第 6、7 节关于二进网、转移原理和 $\gamma_2$ 范数的叙述，依据上面 Matoušek 的专著以及 Matoušek–Nikolov–Talwar、Nikolov 的论文。

这份导读回答三个问题

之前为什么不行

这次为什么可以

有什么新技术

需要的预备知识

全景：五句话的证明

问题

§ 1 · 入门一个染色游戏

§ 2 · 入门从一维到二维

一维：交替染色就够了

二维：只按一个坐标交替不够

只看“锚定矩形”就够了

§ 3 · 入门记号与增长速度

三层的 min 和 max

渐近记号

之前知道什么，为什么卡住

§ 4 · 入门上下界的历史

§ 5 · 进阶上界从哪来

最朴素的办法：随机染色

把前缀拆成二进区间

目前最好的上界

§ 6 · 进阶下界从哪来：连续差异度与转移原理

一个更老的问题：点放得均不均匀

二进网：每层误差不超过 1

转移原理：好染色能造出均匀点集

§ 7 · 进阶其他下界工具，和它们停下的地方

正交函数法

分解范数 γ2\gamma_2γ2​

小结：三种方法，同一个数

换一个问法

§ 8 · 入门随机撒点，一次对付一种染色

证明的两步

§ 9 · 进阶该瞄准多大：32\frac3223​ 是怎么猜出来的

§ 10 · 进阶逐位揭示：把一个随机数拆成一串骰子

已知信息和条件期望

局部振荡

§ 11 · 入门h+1h+1h+1 个阶段，一族等面积的矩形

§ 12 · 进阶端点平均与振荡

端点平均

振荡

势函数 ZjZ_jZj​

§ 13 · 核心推导一个矩形里的比较（上）：不含概率的部分

第一步：一个关于阶梯函数的不等式

第二步：细分之后，对子函数取平均

第三步：一个点在 aˉ\bar aaˉ 里的权重

§ 14 · 核心推导一个矩形里的比较（下）：取期望，基准和增益

随机的是什么

第一步：增量是对称的，所以 E aˉ=a\EE\,\bar a=aEaˉ=a

第二步：基准

第三步：把内部点的贡献单独拿出来

第四步：对称随机变量的和离任何定点都不近

第五步：合起来，得到引理 2.3

一个矩形能给出什么，还缺什么

§ 15 · 进阶改一位数字，影响有多大

§ 16 · 核心推导把 hhh 层接起来：计划、条件增益和波动

第一步：把涨幅拆成“条件增益”和“波动”

第二步：每一层平均涨多少

第三步：有界差分

第四步：波动项很难是大的负数

§ 17 · 进阶点不会太挤：重的区域和好层

重的区域，好层

一层不是好层的概率

§ 18 · 核心推导收尾：定理 1.1

三步合起来：命题 2.7

选参数

定理 1.1 的证明

回顾

§ 19 · 进阶32\frac3223​ 的账

为什么 nM\frac nMMn​ 不能取得更大

和第 9 节的猜测对账

§ 20 · 入门之前为什么不行，这次为什么可以

之前为什么不行

这次为什么可以

论文的四步，和这份导读的对应

技术清单

§ 21 · 入门常数、形式化验证与开放问题

显式的坏点集

高维

常数

形式化验证与 AI

分解范数 $\gamma_2$

§ 9 · 进阶该瞄准多大： $\frac32$ 是怎么猜出来的

§ 11 · 入门 $h+1$ 个阶段，一族等面积的矩形

势函数 $Z_j$

第三步：一个点在 $\bar a$ 里的权重

第一步：增量是对称的，所以 $\EE\,\bar a=a$

§ 16 · 核心推导把 $h$ 层接起来：计划、条件增益和波动

§ 19 · 进阶 $\frac32$ 的账

为什么 $\frac nM$ 不能取得更大