一次共享的随机染色怎样留下小异常集合

本章精读 H 的 Lemma 6.3，位于 §6.2，第 41–43 页，为紧接着的 §6.3 历史球掩膜提供成功的固定颜色实现。原稿为 An $L^3$ bound for the trilinear Hilbert transform，固定 October 5, 2026 版本。

我们证明两件事。任意一次延迟数组的实现都只使每个顶点的颜色改变受控次数；而且可以选取同一次全局实现，使第一次标记失败的格具有任意小的固定相对总长度。后一句不是对每条空间路径各选一套随机数。

本章使用原始顶点列表固定、图距离随深度不增这两个输入。其后的主列、helper 列和线性化模式都不增加图顶点，这是原稿第 39 页的明确规定。

返回 H 导读

1. 先固定有限树、顶点和图，再抽随机数

固定根区间 $R$ 下的一棵有限二进树。每格 $I$ 的原始顶点列表记为 $\mathcal V(I)$ ，它包含全部相关槽位的原始列出现。子格继承父格列表，可以在末端增加新顶点；出生次序和同时出生时的排序已经固定。不同分支可以有不同的新顶点。即使两个顶点的曲率标签相同，它们仍是两次不同的原始列出现，延迟分别独立抽取。

假设每条从根向下的路径上，所有曾经出现的顶点总数不超过整数 $D\ge2$ 。并不要求整棵树的顶点总数不超过 $D$ 。整棵树有限，所以全局顶点数仍有限，但它不会进入最后的误差界。

图先定义在全部满足基本界的假想曲率标签上。绝对深度 $s$ 的距离记为 $d_s$ ，允许取 $+\infty$ ，等标签距离为零，并且

d_{s+1}(v,w)\le d_s(v,w). \tag{图的单调性}

这些距离由曲率标签与绝对深度决定，与空间位置、当前是否已出生、颜色和延迟数组无关。对尚未出生的标签，其距离也已经有定义。

这里的量词顺序是：先固定列表、出生记录和整个图族，再抽数组。相关结论对所有这样的固定图族统一成立；这不要求同一数组同时适用于所有可能的图族或所有边阈值。

2. 数量参数与两套共享数组

固定源文的整数尺度参数 $P\ge1$ ，并置

d_0=\lceil1000\log(2D)\rceil,\quad L=d_0^{30},\quad H_{\max}=100P(L+1),

b_2=100(H_{\max}+1),\quad b_1=d_0^{10}b_2(H_{\max}+1). \tag{参数}

没有底数标记的 $\log$ 是自然对数。概率论的最后界实际上不依赖 $b_1,b_2$ 的具体大小；它们的特殊比例将在历史球掩膜中使用。

对每个全局出生顶点 $z$ ，抽取两族延迟

D^{\mathrm{pri},q}_z,\quad D^{\mathrm{hi},q}_z,\quad 1\le q\le d_0.

所有出生顶点、轮次及两族之间的变量独立。每个延迟均由一个几何变量截断而成：

\mathbb P(X\ge n)=2^{-n}\quad(n=0,1,\ldots),\quad D_{\mathrm{one}}=\min(X,d_0).

上式的 $D_{\mathrm{one}}$ 只是在说明单个延迟的分布；下文用带标签的 $D_z^{\mathrm{pri},q},D_z^{\mathrm{hi},q}$ ，不与顶点数量预算 $D$ 混用。

一个出生顶点在某轮的延迟只抽一次，沿继承列表一直使用。高轮数组在所有冻结上下文之间共用。若每次换中心或换组就重抽，后面关于有限阶段和共同实现的证明都不再适用。

3. 主轮的分数、成功标记与固定前缀

在当前深度 $s$ 和当前已存在的顶点 $v$ ，第 $q$ 个主轮给竞争者 $z\in\mathcal V(I)$ 的分数为

S^{\mathrm{pri},q}_{s,v}(z) =D^{\mathrm{pri},q}_z-\left\lfloor d_s(z,v)/b_1\right\rfloor.

无限距离的分数取 $-\infty$ 。顶点 $v$ 自己是距离零的竞争者，故最高分总是一个位于 $\{0,\ldots,d_0\}$ 的整数。

一轮成功标记，指存在唯一赢家，其分数比每个其他竞争者至少高 $5$ 。选最早成功的主轮；其轮次、最高分和赢家分别记为 $q,g,z$ 。若没有成功轮，使用固定失败占位值。

设赢家的出生指标为 $i$ ，当前列表长度为 $j\ge i$ 。当 $j=i$ 时，使用等号分段和截至 $i$ 的前缀。否则，在正整数指标的固定二进分块中，取唯一最小块，使 $i$ 在下半部、 $j$ 在上半部；在这个上半部分段内，固定截至下半部末端的前缀 $W$ 。特别地， $z\in W$ ，而 $W$ 中的顶点当前已经存在。

对一个固定赢家，列表长度只增不减，因此它经历的等号分段和这些二进分段总共不超过

2+\lceil\log_2D\rceil\le d_0. \tag{前缀分段数}

每次离开一个上半块之后，包含同一个赢家指标的新块必须更大；不能反复回到已经离开的较小块。

4. 高轮用的是全深度冻结伪距离

固定一个主轮、赢家、最高分和前缀上下文。对每个假想标签 $a$ 及每个绝对深度 $s'\in\mathbb Z$ ，定义

f_a(s')=\max_{w\in W\setminus\{z\}} \bigl(b_1D_w^{\mathrm{pri},q}-d_{s'}(w,a)\bigr).

空最大值取 $-\infty$ 。剖面包括标签出生前后的所有深度，而且随深度非减。

令

T_l=(g-3)b_1+\frac{lb_1}{2d_0},\quad U=(g-2)b_1, \quad C_l(x)=\min(U,\max(T_l,x)),

其中 $1\le l\le d_0$ ，并规定 $C_l(-\infty)=T_l$ 。定义

d^{(l)}(a,b)= \sup_{s'\in\mathbb Z}|C_l(f_a(s'))-C_l(f_b(s'))|. \tag{冻结伪距离}

它总是有限的伪距离。由于 $C_{l+1}\circ C_l=C_{l+1}$ ，且截断映射为 $1$ -Lipschitz，

d^{(l+1)}(a,b)\le d^{(l)}(a,b).

固定上下文后，所有 $d^{(l)}$ 都不再随当前深度、当前顶点列表或高轮数组变化。它们可以依赖主数组；这会在概率证明中通过先条件化主数组处理。对于本章实际测试的有限出生顶点对，上确界只遍历整数深度，并只依赖有限个主延迟，因此没有额外的可测性选择问题；这不把全部假想曲率标签的集合当作有限集合。

5. 为什么总能找到两个同大小层的球

置

R_l=10l(d_0+1)b_2,\quad B_l(v;I)=\{a\in\mathcal V(I):d^{(l)}(a,v)\le R_l\},

并令

N_l(I)=\left\lfloor\log_{3/2}|B_l(v;I)|\right\rfloor.

每个球都包含当前中心 $v$ ，所以大小不为零。由伪距离随 $l$ 不增、半径随 $l$ 增大，

B_l(v;I)\subset B_{l+1}(v;I).

因此 $N_1\le\cdots\le N_{d_0}$ ，且所有值都在

0\le N_l\le m_D,\quad m_D=\lfloor\log_{3/2}D\rfloor<d_0-1

内。若每对相邻层都严格增加，就会有 $N_{d_0}-N_1\ge d_0-1$ ，矛盾。

故可以选最小的 $l<d_0$ ，使 $N_l=N_{l+1}$ ，把共同整数记为 $n$ 。高轮使用伪距离 $d^{(l+1)}$ ：第 $q'$ 轮的竞争者分数为

S^{\mathrm{hi},q'}_v(a) =D_a^{\mathrm{hi},q'}- \left\lfloor d^{(l+1)}(a,v)/b_2\right\rfloor.

选最早成功高轮，其轮次、最高分和赢家记为 $q',g_2,a$ ，失败时使用固定占位值。高轮中心仍是距离零的竞争者，所以 $0\le g_2\le d_0$ 。

6. 一个单调分数族只有有限个成功阶段

先抽象出实际要用的计数。固定一个目标顶点和一轮，竞争者逐渐增加，每个已经存在的竞争者分数非减，最高分始终属于 $\{0,\ldots,d_0\}$ 。

固定最高分值 $g$ 的连续时间段。如果在其中某个时刻成功标记，赢家为 $z$ ，那么在该段任何更早时刻已经有某个竞争者取得分数 $g$ 。该竞争者的分数不会下降，到成功时仍为 $g$ ，于是它只能是唯一赢家 $z$ 。其他竞争者更早时的分数也不大于成功时的分数，故都至多为 $g-5$ 。

这证明：在固定最高分段内，成功时刻形成一个初始连续段，赢家固定。一旦间隔被竞争者破坏，就不能在保持同一个最高分的情况下重新成功。每轮至多有 $d_0+1$ 个成功阶段。

把每轮的状态写成“失败”，或“成功、最高分、赢家”。一轮最多在 $2(d_0+1)$ 个边界处改变这项状态。对 $d_0$ 轮合并全部边界，最早成功轮及其最高分、赢家的阶段数不超过

2d_0(d_0+1)+1\le5d_0^2. \tag{轮选择阶段数}

不要求各轮的状态在时间上独立；这是对任意固定延迟实现的确定性计数。

主轮满足这些假设，因为图距离随深度不增，出生只增加竞争者。高轮在固定上下文、固定 $l$ 的区间中也满足：旧竞争者分数甚至完全不变，只有新的竞争者加入。

7. 球计数的阶段数不随深度总数增长

固定一个顶点 $v$ ，从它出生以后沿一条空间路径考察。主轮选中数据至多有 $5d_0^2$ 个阶段。每个成功阶段至多分成 $d_0$ 个前缀分段。

在一个前缀分段内，所有伪距离固定。每个球只因原始顶点加入列表而增长，因此

(N_1,\ldots,N_{d_0})

逐坐标非减，每个坐标的整数值范围至多为 $m_D+1\le d_0$ 。整个向量改变的次数至多为各坐标总增量之和，故其常值阶段数不超过

1+d_0m_D\le2d_0^2. \tag{球阶段数}

在每个阶段内，所选 $l,n$ 固定，高轮伪距离也固定。再用第 6 节，高轮选中数据至多有 $5d_0^2$ 个阶段。

相乘得到每个顶点的完整选中数据阶段数上界

(5d_0^2)\,d_0\,(2d_0^2)\,(5d_0^2)=50d_0^7. \tag{总阶段数}

主轮失败段不需要构造前缀或球；把它作为一个固定失败状态只会使实际计数更小。这个界与树的总深度无关。

8. 有限颜色与只下降的计数器

颜色记录七个坐标：

q,\quad g,\quad \text{等号情形或分段长度层},\quad l,\quad n,\quad q',\quad g_2.

各坐标包括失败占位值在内，都不超过 $d_0+2$ 种取值。成功组另外记录 $z,a,W$ 和精确二进分段块；赢家身份本身不塞进颜色坐标。

每个顶点出生时把变化计数器设为 $d_0^8$ 。只要七个颜色数据中任何一项改变，或任一赢家身份改变，就减 $1$ 。由上节及 $d_0\ge50$ ，总改变次数至多 $50d_0^7\le d_0^8$ ，所以计数器不会变成负数。

将“计数器、七个坐标”按计数器优先的字典序排列，并用一个对所有顶点共用的保序编码放入整数颜色集合。全部可能状态数至多为

(d_0^8+1)(d_0+2)^7 \le256d_0^{15}<d_0^{30}=L. \tag{颜色数}

每当状态或赢家改变，第一坐标严格减小，足以压过其他坐标的任意变化。因此每个顶点的颜色沿路径非增，且至多改变 $d_0^8$ 次。

同色意味着七项元数据完全相同，但不强迫不同顶点的赢家相同；赢家及固定前缀由组记录区分。这样得到的正是历史球掩膜所使用的颜色和组接口。

9. 一次固定情形为何以统一概率成功

所谓固定分数情形，是一个不超过 $D$ 个竞争者的有限集合，以及给每个竞争者的固定惩罚数 $c_z\in[0,\infty]$ 。至少一个惩罚为零。分数为 $X_z-c_z$ ，其中 $X_z$ 是独立未截断几何变量。在主轮和高轮中，惩罚分别是所列距离商的整数部分。

对每个几何变量结果，按固定顺序选一个最高分赢家 $z$ ，仅将 $X_z$ 增加 $5$ 。变换后该赢家唯一，并领先所有其他竞争者至少 $5$ 。

该映射单射：变换后的唯一赢家准确指出被增加的坐标，减去 $5$ 即恢复原结果。由于

\mathbb P(X_z=n)=2^{-n-1},\quad n=0,1,\ldots,

每个像结果的概率恰为原结果概率的 $2^{-5}$ 。对全部原结果求和，得到

\mathbb P(\text{这一轮成功，未截断})\ge2^{-5}=1/32. \tag{单轮成功}

惩罚为无穷的竞争者不会成为赢家；零惩罚的竞争者保证赢家存在。

将每个变量截断于 $d_0$ ，只有某个 $X_z>d_0$ 时结果才可能改变。因此

\mathbb P(\text{这一轮成功，截断后}) \ge\frac1{32}-D2^{-d_0}\ge\frac1{64}. \tag{截断成功}

最后一式由 $d_0=\lceil1000\log(2D)\rceil$ 、 $D\ge2$ 保证。现在固定这一个情形，轮次间独立，故全部 $d_0$ 轮失败的概率至多为

(1-1/64)^{d_0}\le e^{-d_0/64}. \tag{全轮失败}

不能直接把这一概率套在一个由同一族待揭示随机数选出的情形上。下面分别构造主轮的确定情形表和高轮的条件情形表。

10. 主轮只需枚举多项式个确定情形

固定一条空间路径，也就是固定除边界外的一个点 $x\in R$ 。沿这条路径，最多有 $D$ 个出生顶点。在抽取主数组以前，它们的出现次序与全部图距离都已经固定。

对这条路径的每个有序顶点对定义截断惩罚

c_s(z,v)=\min\left(d_0+5,\left\lfloor d_s(z,v)/b_1\right\rfloor\right),

无穷值也截成 $d_0+5$ 。它为非增整数序列，每对至多改变 $d_0+5$ 次。全部有序对加上列表的至多 $D$ 次变化，产生至多

E_{\mathrm{pri}}=1+D+D^2(d_0+5)

个阶段；阶段内列表与整个截断惩罚矩阵固定。

这个截断不改变成功与赢家判断。被截断的竞争者分数至多为 $d_0-(d_0+5)=-5$ ，而最高分至少为零；它既不可能获胜，也不可能破坏“至少领先 $5$ ”的条件。这里确实使用源文的非严格间隔“至少 $5$ ”。

每个阶段最多有 $D$ 个当前顶点需要测试，所以主轮固定情形数至多为

N_{\mathrm{pri}}\le D\bigl(1+D+D^2(d_0+5)\bigr). \tag{主轮情形数}

此表不依赖任何延迟。对各情形使用全轮失败界和并合界，得到

\mathbb P(\text{这条路径出现主轮失败}) \le N_{\mathrm{pri}}e^{-d_0/64}.

不同情形可以高度相关；并合界不要求它们独立。

11. 高轮先条件于全部主数组，再枚举

现在固定全部主数组的一次任意实现，但仍未揭示任何高轮延迟。对这条路径的每个顶点，主轮阶段、前缀分段和球计数阶段至多共有

(5d_0^2)\,d_0\,(2d_0^2)=10d_0^5

个。在每个成功主轮的这样的阶段中，主轮上下文、所选 $l,n$ 、整个伪距离 $d^{(l+1)}$ 均已固定。

高轮竞争者仍为当前前缀。阶段内前缀最多有 $D$ 种。因此，在全部至多 $D$ 个目标顶点上，高轮情形数至多为

N_{\mathrm{hi}}\le10D^2d_0^5. \tag{高轮情形数}

每个情形由一个目标顶点、固定冻结伪距离和固定当前前缀组成。它是主数组的函数，却不依赖高数组。即使后续碰到高轮失败就会停止，仍先把停止前所有可能需要的情形列入这张表。

条件于主数组后，高轮变量保持原来的独立分布。每个固定情形的全轮失败概率仍至多为 $e^{-d_0/64}$ ，所以

\mathbb P(\text{这条路径出现高轮失败}\mid \text{全部主数组}) \le10D^2d_0^5e^{-d_0/64}. \tag{条件高轮界}

这个条件上界对每个主数组实现都统一，取期望后依然成立。

我们使用同一高轮中各出生顶点之间的独立性，以及不同高轮之间的独立性。不同冻结上下文共享同一高数组，不必也不能把它们假定为独立。共享恰好保证了后来比较两个历史中心时，可以消去同一个高轮延迟。

12. 显式坏路径概率及“小固定比例”的含义

令坏路径事件表示沿固定路径，某个当前顶点的主轮或在成功主轮后的高轮没有标记。前两节合起来给出

\mathbb P(\text{固定路径坏})\le q(D),

其中

q(D)= \left[D\bigl(1+D+D^2(d_0+5)\bigr)+10D^2d_0^5\right]e^{-d_0/64}. \tag{坏路径概率}

这一界不含路径总深度，也不含整棵树的空间分支数。

因为 $d_0\ge1000\log(2D)$ ，

e^{-d_0/64}\le(2D)^{-125/8}.

又 $d_0=O(\log(2D))$ ，所以

q(D)\le C D^{-101/8}\bigl(\log(2D)\bigr)^5\longrightarrow0. \tag{衰减}

幂次没有必要最优化；它只用来把任何事先指定的小固定比例压住。

准确的选择顺序是：先给定要达到的 $\varepsilon_{\mathrm{bad}}\in(0,1)$ ，再把顶点数的允许上界 $D$ 或起始准确度 $k$ 选得足够大，使 $q(D)\le\varepsilon_{\mathrm{bad}}/2$ ，之后固定本章参数并抽数组。增加一个允许的上界 $D$ 不会增加真实顶点；原稿第 38 页 Proposition 5.8 的证明已使用 $D_{\mathrm{base}}\ge e^k$ ，第 39 页取 $D=D_{\mathrm{base}}$ 并允许扩大它。因此固定误差比例后，增大起始 $k$ 确实使这里的 $D$ 趋于无穷；同时仍保持 $\log D\le k^{O(1)}$ 。

这不是断言在一个已经固定且很小的 $D$ 上，只凭同样的 $d_0$ 就能达到任意给定的误差比例。

13. 对空间积分，选择一套全局实现

全局出生顶点数有限，截断延迟只有有限个取值，因此整个样本空间是有限的。所有颜色与失败事件可同时定义在每个原始格上；冻结剖面的整数深度上确界也是已定义的可测函数。

令 $\mathcal B(\omega)\subset R$ 表示在延迟实现 $\omega$ 下，某个祖先格发生上述失败的所有点。它是有限个二进格的并。用非负积分交换求期望与空间积分：

\mathbb E_\omega|\mathcal B(\omega)| =\int_R\mathbb P_\omega(x\in\mathcal B(\omega))\,\mathrm{d}x \le q(D)|R|. \tag{空间平均}

于是 Markov 不等式给出

\mathbb P\bigl(|\mathcal B(\omega)|> \varepsilon_{\mathrm{bad}}|R|\bigr) \le\frac{q(D)}{\varepsilon_{\mathrm{bad}}}\le\frac12.

所以至少存在一次全局实现 $\omega_*$ ，使

|\mathcal B(\omega_*)|\le\varepsilon_{\mathrm{bad}}|R|.

第 6–8 节的颜色次数结论对任意实现都成立，因此这同一次实现还具有颜色非增、至多 $L$ 色和每顶点至多 $d_0^8$ 次改变的性质。

这里从未要求“所有路径同时不失败”，也未对空间分支做一个随分支数增长的并合界。我们允许坏路径，控制的是它们的 Lebesgue 测度。

14. 为什么取第一次失败格

在 $\omega_*$ 下，把每条路径第一次需要标记却失败的格送到新的尝试。令这些首次失败格的集合为 $\mathcal F$ 。同一格只保留一次；如果一个格已有失败祖先，就不再作为首次失败格。

二进格相交时必有包含关系，而首次失败格之间不能有严格祖先关系。因此它们两两不交。并且每个这样的格都包含于 $\mathcal B(\omega_*)$ ，所以

\sum_{I\in\mathcal F}|I| =\left|\bigcup_{I\in\mathcal F}I\right| \le|\mathcal B(\omega_*)| \le\varepsilon_{\mathrm{bad}}|R|. \tag{异常根长度}

半开二进格约定可使“不交”成为字面成立；改用闭区间只差一个零测边界集。

如果实际构造只在部分格或部分顶点需要标记，第一次实际所需失败格只是我们已经计数的失败事件的子集合，仍满足同一界。保留路径上，每一次真正使用颜色和历史掩膜的位置都有成功主轮和高轮。

本章只控制这一种失败来源。把其他目录、大小和最大函数停止与它一起组织成 H 第 10 节的完整重启证明，仍需各自的误差和根长度预算。

15. 与历史掩膜的接口及仍保留的条件

现在可以把所选 $\omega_*$ 固定下来。每个出生顶点的主延迟沿继承列表不变；高数组在所有冻结上下文间共用；颜色非增；每个成功组有固定的主轮、分数、分段、球层、计数、高轮及赢家数据。除去首次失败根以后，历史球掩膜一章所假定的成功标记实现已经由本章构造。

这一结论依赖第 1 节的前置固定性。原始列表和图族不能在看过延迟以后任意改变；新的主列、helper 列和模式也不能作为新图顶点加入。若允许这种适应性改变，第 10 节的确定情形表和第 11 节“只依赖主数组”的条件情形表便不再成立。

尚未在本章展开的是同标签模板测试、变化投影历史的目录闭合，以及完整两侧估计。这些工作可以使用这里构造的颜色实现，但不由概率上的小异常集合自动推出。