实际历史清单与误差量词

本附录配合主文《从实际搜索历史到当前组局部化，再把远带移向侧参数》。符号、固定 H 原稿版本及前提均与正文相同。以下把正文的清单生成写成可以逐项枚举的有限规则，并说明哪些测试在目录插入之前就能够命名。

A. 一个历史名称的组成

H 原稿第 47 页 · H 原稿第 48 页 · H 原稿第 49 页 · 主文中的四类历史

在固定格上，历史名称由以下有限数据组成：基本模式、槽位、基的名称、目标掩膜的上下文与 pad、目标秩、内历史因子的有序列表。主基的名称只能是所选模式在这一槽位的固定 $B_e$ 或 $U_e$。辅助基则是随后固定的完整侧状态名称。

一个因子由四项数据确定：掩膜上下文、秩、单独 pad、正投影或其补算子。掩膜上下文有两种：累积切分点 $m$，或历史球组 $G$ 及插入序号。历史词是从右向左作用的算子乘积，等价地，可保存从早到晚的左乘列表。两种记法不能在一处混用。

只有当前可用的列进入投影。未来可能插入的列不属于当前投影像空间；名称只是指定未来每次增大目录时如何重算该投影。同一名称在整个列的插入次序上对应递增的正投影族；补算子不递增，但可由正投影族处理。这是 Lemma 6.7 所需的单调性。

目标残差不算入内历史长度。对于球目标，所有四个槽位的内历史都是原搜索累积词。对于转移目标，内历史是在实际删除顺序中露出的剩余正词。辅助目标的内历史是以前已转移到 $a$ 槽的辅助平均的乘积。

B. 搜索生成规则与不变量

H 原稿第 49 页 · H 原稿第 50 页 · 返回二进搜索

令一个节点的记录为

其中 $v=\varnothing$ 表示没有下保留槽位。初始化 $(1,L,u_0,\varnothing;1,1,1,1)$，$u_0$ 从基本 $B$ 槽中固定选择。每个非叶节点选择最小的非保留槽位 $t$，并取中点 $m=\lfloor(\ell+h)/2\rfloor$。

两个孩子的更新为

未列出的词保持不变。因此在每个节点都有如下不变量。

1. 上保留槽位要么为未被改动的初始基本 $B$，此时 $h=L$；要么其最外层为切分点 $h$ 的正累积滤子。
2. 当 $\ell>1$ 时，下保留槽位的最外层为切分点 $\ell-1$ 的补累积滤子。当 $\ell=1$ 时没有下保留槽位。
3. 两个保留槽位互异；每次新左乘都发生在非保留槽位，故仍被保留的槽位外层不会被覆盖。
4. 沿同一路径，每个切分点只出现一次。所有已插入正因子的秩名称互异，尽管它们的数值未必按插入次序单调。
5. 四槽累积因子的总数等于路径长度，至多 $\lceil\log_2 L\rceil$。

这些不变量由更新公式直接归纳。叶 $\ell=h=j$ 时，它们立即成为正文中的秩 $L-j+1,L-j+2$ 及 pad 差公式。使用另一种预先固定的非保留槽位选择规则也得到相同不变量；为使选择完全确定，这里采用编号最小的槽位。

C. 主目录的完整清单

H 原稿第 48 页 · H 原稿第 49 页 · H 原稿第 50 页 · H 原稿第 51 页

以下每条记录都另对其所有内因子 pad 和目标 pad 枚举。记录目标 pad $t$ 时，$1\le t\le P$。不把恒等端点当成需要检测的新目标。

C1. 旧源残差

H 原稿第 48 页 · H 原稿第 49 页 · H 原稿第 50 页 · 第一球恒等式

对每个叶 $j>1$，把下保留槽位写为

记录目标 $(v,L-j+2,U_{j-1,h(j-1)+t})$，内历史为 $W_v^{\mathrm{in}}z_v$。其他槽位在局部化中变成什么并不形成新的目标基：H 原式 (13) 已对任意两个 $L^2$ 观察参数成立。

逐纯源证明第一球恒等式时，旧源可能出现在等式左右两边，但仍使用这一记录。特别地，右边的球输出只作为观察参数；不能反过来展开高秩球源去触发低秩下保留槽位测试。

C2. 球插入

H 原稿第 47 页 · H 原稿第 49 页 · H 原稿第 50 页 · 四球局部化

对每个叶和每个实际组上下文 $G$，固定第一个球所在的非保留槽位，再给其余槽位固定顺序 $e_1,e_2,e_3,e_4$。对 $j=1,2,3,4$ 记录

第一球由上保留槽位的纯源触发，另外三球由第一球的纯源触发。源标签均为允许原始顶点，源秩分别不超过 $L$、$L+1$，严格低于其对应目标。

C3. 主滤子的逐次移除

H 原稿第 50 页 · H 原稿第 51 页 · 滤子的删除顺序

对每个叶、每个 $c,d$ 的基本输入都为 $B$ 的角色排列，生成两个槽位的所有补因子展开。每个补因子可选恒等项或负的正平均项，故每个分支带一个确定总符号。所保留正因子的次序不变；最外面再保留该槽已有的球平均。

在每个正词分支中，只比较两槽当前最外层的秩，删去较大者。若待移除滤子是 $c$ 的 $Q_c$，记删除后的词为 $V_c$。对待移除滤子的每个个别投影 $Q_{c,t}$ 记录

下一步继续比较剩余两槽。最终两词都为空。在枚举个别 pad 选择之前，每个正词分支的删除位置数不超过删除前的因子总数。

为什么这覆盖高带的两端？若高带指标 $q\le P$，它需要目标 $Q_{c,q-1}$ 和 $Q_{c,q}$。在第二远带方向 $q>p+2$ 中，$q\ge4$，故这两个下标都在 $1,\ldots,P$ 内。若 $q=P+1$，只需 $Q_{c,P}$。因此上述遍历恰好包含所有实际测试，未要求一个不存在的 pad $P+1$ 目录。

主清单在辅助插入之前即可生成：C3 的内词只由主搜索和删除顺序决定。后来辅助带是测试允许的任意观察参数，无须把它列进主历史。

D. 固定侧基之后的辅助清单

H 原稿第 48 页 · H 原稿第 49 页 · H 原稿第 51 页 · H 原稿第 52 页 · 第一远带方向 · 固定完整侧基的条件

记某个正词分支的实际待移除顺序为

把每个待移除滤子的掩膜、pad 不变地复制到槽位 $a$，秩全部改成 $R_*=L+5$，记得到的正平均为 $\widehat Q^{(j)}$。第 $j$ 次转移以前的侧历史为

这里下标 $j$ 是转移次序，不是辅助的新秩。每个辅助投影的秩都相同。

对第 $j$ 个待移除掩膜的所有 $1\le t\le P$ 记录辅助残差目标，内历史为 $D_a^{(j-1)}S_a$。把其中所有平均按 pad 列成个别词。第一远带方向 $p>q+2$ 需要 pad $p-1,p$ 或终端 pad $P$，全部已经列入。

虽然所有辅助因子的秩相同，它们一般来自不同掩膜，不必交换。目录终止只要求同一个正投影名称在列的插入次序上递增，不要求不同名称之间有包含关系。目标残差可以作用于同秩历史，这不违反“触发纯源必须较低秩”的条件。实际触发源始终来自主槽位 $c$，秩至多 $L+4<R_*$。

完整侧基 $S_a$ 的向量在这一阶段前固定，新的私有辅助坐标在该基中为零。若允许它随着辅助插入而重新选取，目录增量不能再归给一个固定基，Lemma 6.7 的前提就失效。主目录与辅助目录清单允许多个固定完整侧基，但不能把无限多频率分量临时提升为新基。

E. 计数的准确用途

H 原稿第 48 页 · H 原稿第 49 页 · 恢复平均

对于一个固定叶，四槽一共至多 $m_*$ 个累积因子，因此 $c,d$ 的所有补展开至多为 $2^{m_*}$，所有删除位置至多为 $m_*+2$。每个历史因子及目标各有 $P$ 个个别 pad；涉及端点时至多再多一个固定的二因子。角色排列不超过 $4!$，球插入位置恰为四个。

原始上下文名称的先验总数由成功颜色和历史掩膜的构造给出，它独立于图距离的数值。若用 $D^{C_{\mathrm{ctx}}}$ 控制这些名称，正文式 (10) 是所有以上选项相乘的一个宽松上界。它不宣称每个枚举名称都在某格非零，也不要求把全树不同空间分支上的组并成一条路径的组数。

把这份清单交给 Lemma 6.7 时，个别 pad 历史数进入插入总数的预算。这份目录构造完成以后，分析估计使用总权重为一的平均，故不再乘清单中 pad 组合的数目。两处计数的用途不同，不能混同。

所有主清单记录在实际运行中都是主秩投影或补投影作用于固定基本输入。所有辅助记录是辅助正投影作用于固定完整侧基。任意两观察参数不需要枚举；它们已在测试范数的上确界里。

F. 四类误差的量词

H 原稿第 49 页 · H 原稿第 50 页 · H 原稿第 51 页 · H 原稿第 52 页 · 远带总误差

固定有限树、一个模式及一套先验预算。下面列出的常数不依赖树深度、实际个别 pad、具体触发源或线性调制。

1. 旧源与同组球残差：对每个目标及个别历史，先用原式 (13)，再把一个较低秩外层支持的 $D\sqrt{n_{r-1}}$ 系数和消掉。只留下 $\tau_3$ 乘固定基和观察参数的局部范数。
2. 不同组错配：展开上源和第一球的两份支持；代价允许是先验主目录预算的固定幂。纯源距离大于一使 Lemma 6.1 给出 $\tau_2$。此项不依赖旧源残差的精度。
3. 第一远带方向：源为主带，目标为辅助残差。主带系数预算至多 $D\sqrt{n_{R_*-1}}$，由辅助目标的分母消掉。观察参数是另一主历史和第二侧状态。
4. 第二远带方向：近源来自另一槽位的较低秩主外层，目标为待移除的主残差；辅助整带是观察参数。远源则展开主源与辅助支持使用 $\tau_2$。只有远源子项需要辅助系数预算。

对给定 $C_3$，令 $A_{\mathrm{tr}}(k)$ 控制转移位置与正词分支数。它是 $k$ 的固定多项式。因此可以选择固定 $C_\tau$，使

在先验 $D_{\mathrm{tot}}$ 固定后，再要求

两式均可与局部化的

同时满足。因为所有量的对数有 $k^{O(1)}$ 的先验界，仍有 $\log(1/\tau_2)\le k^{O(1)}$，符合 Lemma 6.1 的输入。

先验 $D_{\mathrm{tot}}$ 的获取依赖“完整侧基数有 $\exp(k^{O(1)})$ 上界”这项输入，而不依赖这些基的某次频率分解。主目录误差不需要乘未来线性化模式的总数。若以后的一项估计实际要求新增指数个侧基，就必须重新核验其先验数量与参数次序，不能默认为已被这里的有限清单覆盖。

G. 低阶边界

H 原稿第 39 页 · H 原稿第 47 页 · H 原稿第 49 页 · H 原稿第 50 页 · H 原稿第 51 页 · 带恒等式与两个终端

当 $L=1$ 时，搜索没有切分，初始基本上源的颜色就是一，没有下保留槽位；四球插入及后面的转移仍有意义。累积秩一不一定被任何实际切分用到，不影响“秩不超过某值”的目录预算。

当 $P=1$ 时，正平均就是单个投影，仍有两个带：$Q_1$ 与 $1-Q_1$。H 原式 (15) 仍必须求到 $P+1=2$。此时没有 $|p-q|>2$ 的远带，所有非零差项保留为近带。

当某目标掩膜为空时，其正投影为零。若第一球没有当前组，组和为空；旧源论证说明相应叶只有数值误差。若转移的低辅助掩膜为空，相应正带为零，无需寻找一个不存在的邻居。

当两个原始顶点有相同曲率标签时，图距离为零，但私有列标签仍不同。累积/历史掩膜以标签条件判定成员，纯源的系数唯一性却依赖各自的私有坐标。不能把这两个层面的“相同”混淆。

H. 本附录不替代的后续定理

H 原稿第 48 页 · H 原稿第 50 页 · H 原稿第 51 页 · H 原稿第 52 页 · 主文结论的范围

这里不构造H 第 7–8 节的完整侧状态，不证明它们的线性平方预算，也不证明近带和带来 $P^{-1/2}$ 增益。它只核实：给定这些固定基及其先验数目，本章的每一次实际测试均属于此前列定的有限清单，且远带消去不会迫使主目录在辅助插入之后再改变。