选择一段文字或公式，即可在这里留下建议。保存后的建议仅作者可见，审核后才会公开。
多重遍历平均 / 原文精读 / 局部调和分析依赖
变化的投影历史怎样仍能使列目录有限终止
本章精读 H §6.4 的 Lemma 6.7，第 47–49 页 ，并完整展开它需要的 Lemma 3.3，第 8–9 页 。固定原稿为 An L 3 L^3 L 3 。
前一章的同标签测试说明：每次四线性小量测试失败，都能找到一个与残差有大矩的新模板。本章要证明这种插入只能发生有限多次，而且总数的对数仍是原参数的固定幂。困难在于被测状态也在变化；一次插入可以改变若干个投影，进而改变以后所有被测状态。
原文 Lemma 6.7 引用的是 Lemma 3.4 中的二进前缀论证。本章在一个固定格内以“插入时刻”为指标，直接证明并使用 Lemma 3.3 的行形式。这里不需要先证明 Lemma 3.4 对任意空间深度的完整压缩结论。
返回 H 导读
1. 哪些资料固定，哪些仍可变化
固定一棵有限二进树和其中的活跃格。每条从根向下的空间路径至多遇到 M M M M ≥ 1 M\ge1 M ≥ 1
补充阅读：上述原始出处仍为 H 第 38 页 Proposition 5.8；它在给定基本数据下所需的活跃格路径数论证现见 H10 第 9 节 ，第 1 节 另行说明仍作为来源输入的原始目录预算。后续实际历史列表与 Section 7 整个 helper 基仍须另行提供。
原始预算的配套证明：H 第 35–36 页 Proposition 5.6 的基本列构造及其整条路径预算现见 H11 第 16 节 ；检测附录 明列外部离散二次逆定理。这补充本章的原始预算输入，不代替后续实际历史列表或 Section 7 整个 helper 基的构造。
原始图顶点、出生记录、颜色、球掩膜与累积掩膜均已固定。新列仍附着在某个原始顶点上，不增加图顶点，不改变颜色或掩膜。目录的改变只是在已有标签允许的列空间中加入新列。
记颜色数为 L \mathcal L L
R = L + 5.
R=\mathcal L+5.
R = L + 5. 原始列为秩零。固定整数 n 0 ≥ 1 n_0\ge1 n 0 ≥ 1 1 , … , L + 4 1,\ldots,\mathcal L+4 1 , … , L + 4 R R R D ≥ 2 D\ge2 D ≥ 2 H 0 H_0 H 0
τ 3 = D − C τ ,
\tau_3=D^{-C_\tau},
τ 3 = D − C τ , 其中 C τ C_\tau C τ
对每个格及每个槽位，预先列出所需的目标掩膜和投影历史的名字。一个名字指定目标秩、目标掩膜、槽位、基本向量、各历史因子所用的掩膜和秩、正投影或其补算子，以及具体 pad 选择。它不指定后来插入哪些列。
主目录的目标投影和历史因子只使用主秩 0 , … , L + 4 0,\ldots,\mathcal L+4 0 , … , L + 4 R R R L − m + 1 \mathcal L-m+1 L − m + 1 L + j \mathcal L+j L + j 1 ≤ j ≤ 4 1\le j\le4 1 ≤ j ≤ 4 L + 5 \mathcal L+5 L + 5
历史长度至多为
m ∗ ≤ C log ( 2 L ) .
m_*\le C\log(2\mathcal L).
m ∗ ≤ C log ( 2 L ) . 设每个格、每个秩的这种名字总数至多为 S ≥ 1 S\ge1 S ≥ 1
log D + log H 0 + log n 0 + log ( M + 1 ) + log ( S + 1 ) ≤ k C 0 , R ≤ k C 0 . (固定资料预算)
\log D+\log H_0+\log n_0+\log(M+1)+\log(S+1)
\le k^{C_0},\quad
R\le k^{C_0}.
\tag{固定资料预算}
log D + log H 0 + log n 0 + log ( M + 1 ) + log ( S + 1 ) ≤ k C 0 , R ≤ k C 0 . ( 固定资料预算 ) 这里及下文都允许增大固定指数，并从充分大的起始 k k k
这一计数只使用原始顶点上下文、秩、颜色、pad 及有限长因子的名字。它不计图距离的数值，也不计后来实际出现的纯源列。若每个因子的名字数至多为 exp ( k C 1 ) \exp(k^{C_1}) exp ( k C 1 ) O ( log ( 2 L ) ) O(\log(2\mathcal L)) O ( log ( 2 L ))
( 2 exp ( k C 1 ) ) m ∗ + 1 ,
\bigl(2\exp(k^{C_1})\bigr)^{m_*+1},
( 2 exp ( k C 1 ) ) m ∗ + 1 , 仍满足上述预算。原文主目录的名字来自后续定位与转移所需的历史；helper 基的数量另按第 12 节的来源条件给定。
2. 私有坐标与格内的普通正交投影
固定一个活跃格 I I I
X I = L 2 ( I ; H ) , ⟨ F , G ⟩ I = 1 ∣ I ∣ ∫ I ⟨ F ( y ) , G ( y ) ⟩ H d y , H = C ⊕ ℓ 2 ( V ) .
\mathscr X_I=L^2(I;\mathcal H),\quad
\langle F,G\rangle_I=\frac1{|I|}\int_I
\langle F(y),G(y)\rangle_{\mathcal H}\,\mathrm{d}y,
\quad
\mathcal H=\mathbb C\oplus\ell^2(\mathcal V).
X I = L 2 ( I ; H ) , ⟨ F , G ⟩ I = ∣ I ∣ 1 ∫ I ⟨ F ( y ) , G ( y ) ⟩ H d y , H = C ⊕ ℓ 2 ( V ) . 第一坐标是物理函数；其余是各列的私有坐标。一个列为
Φ v ( y ) = ( ϕ v ( y ) , ϵ v e v ) , ϵ v ≥ D − 2 .
\Phi_v(y)=\bigl(\phi_v(y),\sqrt{\epsilon_v}\,e_v\bigr),
\quad \epsilon_v\ge D^{-2}.
Φ v ( y ) = ( ϕ v ( y ) , ϵ v e v ) , ϵ v ≥ D − 2 . 不同私有标签使用不同的正交单位向量 e v e_v e v ∣ ϕ v ∣ ≤ 1 |\phi_v|\le1 ∣ ϕ v ∣ ≤ 1 ϵ v = 1 \epsilon_v=1 ϵ v = 1
∥ Φ v ∥ 2 , I ≤ 2 . (新列范数)
\|\Phi_v\|_{2,I}\le\sqrt2.
\tag{新列范数}
∥ Φ v ∥ 2 , I ≤ 2 . ( 新列范数 ) 重复曲率标签仍可有不同的私有标签。
给定目标秩 r r r A \mathcal A A r r r A \mathcal A A I I I
在同一格依次插入列。时刻 t t t t t t Q t Q_t Q t
ran Q t − 1 ⊆ ran Q t .
\operatorname{ran}Q_{t-1}\subseteq\operatorname{ran}Q_t.
ran Q t − 1 ⊆ ran Q t . 故
Δ Q t = Q t − Q t − 1
\Delta Q_t=Q_t-Q_{t-1}
Δ Q t = Q t − Q t − 1 是正交投影，并且不同 t t t
每个被测历史的基本向量 g ∈ X I g\in\mathscr X_I g ∈ X I B B B U U U
X t − 1 = T t − 1 m ⋯ T t − 1 1 g , m ≤ m ∗ , (旧历史状态)
X_{t-1}=T_{t-1}^{m}\cdots T_{t-1}^{1}g,\quad m\le m_*,
\tag{旧历史状态}
X t − 1 = T t − 1 m ⋯ T t − 1 1 g , m ≤ m ∗ , ( 旧历史状态 ) 其中每个 T t a T_t^a T t a P t a P_t^a P t a 1 − P t a 1-P_t^a 1 − P t a
3. 一次失败准确地产生多大的增量
预先给定整数预算 n r n_r n r r r r
在秩 r r r
F t = ( ( 1 − Q t − 1 ) X t − 1 ) p h y s .
F_t=\bigl((1-Q_{t-1})X_{t-1}\bigr)_{\mathrm{phys}}.
F t = ( ( 1 − Q t − 1 ) X t − 1 ) phys . 它要对掩膜内的每一个可用的较低秩纯源列，及两个任意归一化 L 2 ( I ) L^2(I) L 2 ( I )
τ 3 D n r − 1 ∥ g ∥ 2 , I . (原式 13)
\frac{\tau_3}{D\sqrt{n_{r-1}}}\,\|g\|_{2,I}.
\tag{原式 13}
D n r − 1 τ 3 ∥ g ∥ 2 , I . ( 原式 13 ) 分母是 D n r − 1 D\sqrt{n_{r-1}} D n r − 1 D n r − 1 \sqrt{Dn_{r-1}} D n r − 1
若某个测试失败，同标签 Lemma 6.6 产生目标槽位的一个有界模板 ϕ \phi ϕ F t F_t F t
τ 3 D n r − 1 H 0 ∥ g ∥ 2 , I . (失败矩)
\frac{\tau_3}{D\sqrt{n_{r-1}}H_0}\,\|g\|_{2,I}.
\tag{失败矩}
D n r − 1 H 0 τ 3 ∥ g ∥ 2 , I . ( 失败矩 ) 把它附着在触发源的原始顶点上，以目标秩 r r r
Φ = ( ϕ , e n e w ) .
\Phi=(\phi,e_{\mathrm{new}}).
Φ = ( ϕ , e new ) . 这个私有坐标在旧基本向量、旧历史状态和旧投影空间中都为零。因此
⟨ ( 1 − Q t − 1 ) X t − 1 , Φ ⟩ I = 1 ∣ I ∣ ∫ I F t ( y ) ϕ ( y ) ‾ d y . (物理矩等于向量矩)
\left\langle(1-Q_{t-1})X_{t-1},\Phi\right\rangle_I
=
\frac1{|I|}\int_I F_t(y)\overline{\phi(y)}\,\mathrm{d}y.
\tag{物理矩等于向量矩}
⟨ ( 1 − Q t − 1 ) X t − 1 , Φ ⟩ I = ∣ I ∣ 1 ∫ I F t ( y ) ϕ ( y ) d y . ( 物理矩等于向量矩 ) 设 u = ( 1 − Q t − 1 ) Φ u=(1-Q_{t-1})\Phi u = ( 1 − Q t − 1 ) Φ u ≠ 0 u\ne0 u = 0 ∥ u ∥ 2 , I ≤ ∥ Φ ∥ 2 , I ≤ 2 \|u\|_{2,I}\le\|\Phi\|_{2,I}\le\sqrt2 ∥ u ∥ 2 , I ≤ ∥Φ ∥ 2 , I ≤ 2 Φ \Phi Φ
∥ ( Δ Q t ) X t − 1 ∥ 2 , I ≥ ∣ ⟨ X t − 1 , u ⟩ I ∣ ∥ u ∥ 2 , I > τ 3 2 D n r − 1 H 0 ∥ g ∥ 2 , I . (单次增量)
\begin{aligned}
\|(\Delta Q_t)X_{t-1}\|_{2,I}
&\ge \frac{|\langle X_{t-1},u\rangle_I|}{\|u\|_{2,I}}\\
&>\frac{\tau_3}{\sqrt2D\sqrt{n_{r-1}}H_0}\,\|g\|_{2,I}.
\end{aligned}
\tag{单次增量}
∥ ( Δ Q t ) X t − 1 ∥ 2 , I ≥ ∥ u ∥ 2 , I ∣ ⟨ X t − 1 , u ⟩ I ∣ > 2 D n r − 1 H 0 τ 3 ∥ g ∥ 2 , I . ( 单次增量 ) 若这一步只加入这一列，则首行实际等于右边的投影大小；下界已经足够。
若 g = 0 g=0 g = 0 ∥ g ∥ 2 , I > 0 \|g\|_{2,I}>0 ∥ g ∥ 2 , I > 0
4. 固定向量的正交能量为何还不够
对于一个固定向量 h h h
∑ t ∥ ( Δ Q t ) h ∥ 2 , I 2 ≤ ∥ h ∥ 2 , I 2 .
\sum_t\|(\Delta Q_t)h\|_{2,I}^2\le\|h\|_{2,I}^2.
t ∑ ∥ ( Δ Q t ) h ∥ 2 , I 2 ≤ ∥ h ∥ 2 , I 2 . 但第 3 节作用的是 X t − 1 X_{t-1} X t − 1 h h h
这种区别不能略去。在 C T \mathbb C^T C T Q t Q_t Q t t t t X t − 1 = e t X_{t-1}=e_t X t − 1 = e t 1 1 1
∑ t = 1 T ∥ ( Δ Q t ) X t − 1 ∥ 2 = T .
\sum_{t=1}^T\|(\Delta Q_t)X_{t-1}\|^2=T.
t = 1 ∑ T ∥ ( Δ Q t ) X t − 1 ∥ 2 = T . 所以仅有各状态的范数界，不可能得到与 T T T
本章额外知道：每个 X t − 1 X_{t-1} X t − 1 g g g
5. 二进前缀的行估计
先暂时在任意 Hilbert 空间 X \mathscr X X a = 1 , … , m a=1,\ldots,m a = 1 , … , m
P 0 a , … , P T a , Z t = P t m ⋯ P t 1 .
P_0^a,\ldots,P_T^a,\quad
Z_t=P_t^m\cdots P_t^1.
P 0 a , … , P T a , Z t = P t m ⋯ P t 1 . 另有有限个有界线性行算子
B ν : X ⟶ Y ν , ∑ ν ∥ B ν h ∥ 2 ≤ ∥ h ∥ 2 ( h ∈ X ) . (行压缩条件)
B_\nu:\mathscr X\longrightarrow\mathscr Y_\nu,\quad
\sum_\nu\|B_\nu h\|^2\le\|h\|^2
\quad(h\in\mathscr X).
\tag{行压缩条件}
B ν : X ⟶ Y ν , ν ∑ ∥ B ν h ∥ 2 ≤ ∥ h ∥ 2 ( h ∈ X ) . ( 行压缩条件 ) 每一行可独立选择一个前缀时刻 t ( ν ) ∈ { 0 , … , T } t(\nu)\in\{0,\ldots,T\} t ( ν ) ∈ { 0 , … , T }
L T = 1 + ⌈ log 2 ( T + 1 ) ⌉ .
L_T=1+\lceil\log_2(T+1)\rceil.
L T = 1 + ⌈ log 2 ( T + 1 )⌉ . Lemma 3.3 的所需结论为
( ∑ ν ∥ B ν Z t ( ν ) g ∥ 2 ) 1 / 2 ≤ L T m ∥ g ∥ . (前缀行界)
\left(\sum_\nu\|B_\nu Z_{t(\nu)}g\|^2\right)^{1/2}
\le L_T^m\|g\|.
\tag{前缀行界}
( ν ∑ ∥ B ν Z t ( ν ) g ∥ 2 ) 1/2 ≤ L T m ∥ g ∥. ( 前缀行界 ) 当 m = 0 m=0 m = 0
对每层定义
Δ 0 a = P 0 a , Δ t a = P t a − P t − 1 a ( 1 ≤ t ≤ T ) .
\Delta_0^a=P_0^a,\quad
\Delta_t^a=P_t^a-P_{t-1}^a\quad(1\le t\le T).
Δ 0 a = P 0 a , Δ t a = P t a − P t − 1 a ( 1 ≤ t ≤ T ) . 同层的这些算子是相互正交的投影。对整数指标的二进块 A ⊆ { 0 , … , T } A\subseteq\{0,\ldots,T\} A ⊆ { 0 , … , T }
Δ A a = ∑ t ∈ A Δ t a .
\Delta_A^a=\sum_{t\in A}\Delta_t^a.
Δ A a = t ∈ A ∑ Δ t a . 固定块长时，各块互不相交，因此其块投影仍相互正交。
每个整数前缀 { 0 , … , t } \{0,\ldots,t\} { 0 , … , t } L T L_T L T
P t a = ∑ A 为该前缀的二进块 Δ A a .
P_t^a=\sum_{A\text{ 为该前缀的二进块}}\Delta_A^a.
P t a = A 为该前缀的二进块 ∑ Δ A a . 现在展开每一行的全部 m m m ( ℓ 1 , … , ℓ m ) (\ell_1,\ldots,\ell_m) ( ℓ 1 , … , ℓ m )
B ν Δ A m ( ν ) m ⋯ Δ A 1 ( ν ) 1 g .
B_\nu\Delta_{A_m(\nu)}^m\cdots
\Delta_{A_1(\nu)}^1g.
B ν Δ A m ( ν ) m ⋯ Δ A 1 ( ν ) 1 g . 将具有同一个实际块元组 ( A 1 , … , A m ) (A_1,\ldots,A_m) ( A 1 , … , A m )
∥ Δ A m m ⋯ Δ A 1 1 g ∥ 2 .
\|\Delta_{A_m}^m\cdots\Delta_{A_1}^1g\|^2.
∥ Δ A m m ⋯ Δ A 1 1 g ∥ 2 . 再对实际出现的块元组求和，可扩大到全部指定长度的块元组。逐层使用同层正交性，
∑ A 1 , … , A m ∥ Δ A m m ⋯ Δ A 1 1 g ∥ 2 ≤ ∥ g ∥ 2 . (固定块长平方界)
\sum_{A_1,\ldots,A_m}
\|\Delta_{A_m}^m\cdots\Delta_{A_1}^1g\|^2
\le\|g\|^2.
\tag{固定块长平方界}
A 1 , … , A m ∑ ∥ Δ A m m ⋯ Δ A 1 1 g ∥ 2 ≤ ∥ g ∥ 2 . ( 固定块长平方界 ) 具体说，先固定前 m − 1 m-1 m − 1 m − 1 m-1 m − 1
最后在 Hilbert 直和 ⨁ ν Y ν \bigoplus_\nu\mathscr Y_\nu ⨁ ν Y ν L T m L_T^m L T m ∥ g ∥ \|g\| ∥ g ∥
6. 补算子及旧时刻怎样进入行界
若每一层可为 P t a P_t^a P t a 1 − P t a 1-P_t^a 1 − P t a 2 m 2^m 2 m m m m
( ∑ ν ∥ B ν T t ( ν ) m ⋯ T t ( ν ) 1 g ∥ 2 ) 1 / 2 ≤ ( 2 L T ) m ∥ g ∥ . (含补算子的行界)
\left(
\sum_\nu\|B_\nu T_{t(\nu)}^m\cdots T_{t(\nu)}^1g\|^2
\right)^{1/2}
\le(2L_T)^m\|g\|.
\tag{含补算子的行界}
( ν ∑ ∥ B ν T t ( ν ) m ⋯ T t ( ν ) 1 g ∥ 2 ) 1/2 ≤ ( 2 L T ) m ∥ g ∥. ( 含补算子的行界 ) 这个界不需要任何不同层间的交换性。
回到固定格 I I I
B t = Δ Q t , t ( ν ) = t − 1.
B_t=\Delta Q_t,\quad t(\nu)=t-1.
B t = Δ Q t , t ( ν ) = t − 1. 因为目标增量的像空间相互正交，
∑ t = 1 T ∥ B t h ∥ 2 , I 2 ≤ ∥ h ∥ 2 , I 2 .
\sum_{t=1}^T\|B_t h\|_{2,I}^2\le\|h\|_{2,I}^2.
t = 1 ∑ T ∥ B t h ∥ 2 , I 2 ≤ ∥ h ∥ 2 , I 2 . 所以
∑ t = 1 T ∥ ( Δ Q t ) T t − 1 m ⋯ T t − 1 1 g ∥ 2 , I 2 ≤ ( 2 L T ) 2 m ∥ g ∥ 2 , I 2 . (变化历史的总能量)
\sum_{t=1}^T
\|(\Delta Q_t)T_{t-1}^m\cdots T_{t-1}^1g\|_{2,I}^2
\le(2L_T)^{2m}\|g\|_{2,I}^2.
\tag{变化历史的总能量}
t = 1 ∑ T ∥ ( Δ Q t ) T t − 1 m ⋯ T t − 1 1 g ∥ 2 , I 2 ≤ ( 2 L T ) 2 m ∥ g ∥ 2 , I 2 . ( 变化历史的总能量 ) 在全部时刻中只保留真正向这个名字收费的时刻，只会减小左端。
这里所有秩的插入步骤统一计数。其他秩的插入可以改变历史，也可以改变目标投影；这些变化都已包含在相应递增投影家族里。某一步不改变目标空间时，其行增量为零。无需先假定其他秩的目录停止变化。
选择哪一个失败测试可以依赖输入和此前的插入。应用行估计时，先固定实际得到的有限试验序列及其中全部投影家族，再使用对任意这些家族都成立的确定性不等式。这里不要求投影、行算子与基本向量之间具有概率独立性。
7. 为什么无需再乘触发源列的数量
每次插入只选定一个失败测试作为凭证，把这次插入归给它的目标掩膜及历史名字。不同的较低秩纯源列可以触发同一个名字；它们均使用第 3 节同样的增量下界。
若某个名字在一段至多 T T T N N N
N τ 3 2 2 D 2 n r − 1 H 0 2 ∥ g ∥ 2 , I 2 ≤ ( 2 L T ) 2 m ∗ ∥ g ∥ 2 , I 2 .
N\,
\frac{\tau_3^2}{2D^2n_{r-1}H_0^2}\,
\|g\|_{2,I}^2
\le
(2L_T)^{2m_*}\|g\|_{2,I}^2.
N 2 D 2 n r − 1 H 0 2 τ 3 2 ∥ g ∥ 2 , I 2 ≤ ( 2 L T ) 2 m ∗ ∥ g ∥ 2 , I 2 . 除掉非零的基本范数，得到
N ≤ 2 D 2 n r − 1 H 0 2 τ 3 − 2 ( 2 L T ) 2 m ∗ .
N\le
2D^2n_{r-1}H_0^2\tau_3^{-2}
(2L_T)^{2m_*}.
N ≤ 2 D 2 n r − 1 H 0 2 τ 3 − 2 ( 2 L T ) 2 m ∗ . 每个秩至多 S S S r r r
2 S D 2 H 0 2 τ 3 − 2 n r − 1 ( 2 L T ) 2 m ∗ . (单格插入数)
2S D^2H_0^2\tau_3^{-2}\,
n_{r-1}(2L_T)^{2m_*}.
\tag{单格插入数}
2 S D 2 H 0 2 τ 3 − 2 n r − 1 ( 2 L T ) 2 m ∗ . ( 单格插入数 ) 这个计算只按目标名字分组，没有按触发源的身份分组。对每个目标名字，所有触发源造成的增量都落在同一列正交行中，已经一起计入。若再乘当前源列数，就会引入原证明不需要的损失，也会破坏随后简单的秩预算。
8. 从一个格到一条路径
一条空间路径至多有 M M M
令
A ( k ) = 2 M S D 2 H 0 2 τ 3 − 2 .
A(k)=2MSD^2H_0^2\tau_3^{-2}.
A ( k ) = 2 M S D 2 H 0 2 τ 3 − 2 . 则沿路径新生的秩 r r r
A ( k ) n r − 1 ( 2 L T ) 2 m ∗ . (路径新生数)
A(k)\,n_{r-1}(2L_T)^{2m_*}.
\tag{路径新生数}
A ( k ) n r − 1 ( 2 L T ) 2 m ∗ . ( 路径新生数 ) 这里只用到活跃格的路径数，不使用整棵树的总格数。不同分支可以各自拥有不同的新列，结论不把它们合并成一个全局列数预算。
固定资料预算允许我们选一个固定整数 a ≥ 2 a\ge2 a ≥ 2 k k k
log A ( k ) ≤ k a , R ≤ k a , log n 0 ≤ k a , m ∗ ≤ a log ( 2 k ) . (统一参数界)
\log A(k)\le k^a,\quad
R\le k^a,\quad
\log n_0\le k^a,\quad
m_*\le a\log(2k).
\tag{统一参数界}
log A ( k ) ≤ k a , R ≤ k a , log n 0 ≤ k a , m ∗ ≤ a log ( 2 k ) . ( 统一参数界 ) 这里使用第 1 节已给定的原始列路径预算 n 0 n_0 n 0 n 0 = 1 n_0=1 n 0 = 1
接下来选择各秩预算，并证明算法在达到预算之前已经停止。这一步必须同时覆盖全部秩，不能把后面会变化的历史预先冻结成不变状态。
9. 预先选择所有预算，再排除第一次超限
取整数
Q = ⌈ exp ( k a + 3 ) ⌉ , n r = n 0 Q r ( 0 ≤ r ≤ R ) , T ∗ = n R + 1. (预算选择)
Q=\left\lceil\exp(k^{a+3})\right\rceil,\quad
n_r=n_0Q^r\quad(0\le r\le R),
\quad
T_*=n_R+1.
\tag{预算选择}
Q = ⌈ exp ( k a + 3 ) ⌉ , n r = n 0 Q r ( 0 ≤ r ≤ R ) , T ∗ = n R + 1. ( 预算选择 ) 于是
log ( 2 T ∗ ) ≤ C a k 2 a + 3 , L T ∗ ≤ C a k 2 a + 3 .
\log(2T_*)\le C_a k^{2a+3},\quad
L_{T_*}\le C_a k^{2a+3}.
log ( 2 T ∗ ) ≤ C a k 2 a + 3 , L T ∗ ≤ C a k 2 a + 3 . 结合 m ∗ ≤ a log ( 2 k ) m_*\le a\log(2k) m ∗ ≤ a log ( 2 k )
log ( ( 2 L T ∗ ) 2 m ∗ ) ≤ C a ( log ( 2 k ) ) 2 .
\log\bigl((2L_{T_*})^{2m_*}\bigr)
\le C_a(\log(2k))^2.
log ( ( 2 L T ∗ ) 2 m ∗ ) ≤ C a ( log ( 2 k ) ) 2 . 因此对充分大的起始 k k k
A ( k ) ( 2 L T ∗ ) 2 m ∗ ≤ Q / 4 , Q ≥ 4. (预算余量)
A(k)(2L_{T_*})^{2m_*}\le Q/4,
\quad Q\ge4.
\tag{预算余量}
A ( k ) ( 2 L T ∗ ) 2 m ∗ ≤ Q /4 , Q ≥ 4. ( 预算余量 ) 这就是原文把 n r / n r − 1 n_r/n_{r-1} n r / n r − 1
为准确处理原始列在不同深度的出生，试验计数固定在整棵有限树的每一条完整根叶路径 π \pi π n 0 n_0 n 0 s s s
a s ( π ) = # { 目前已生成、出生格属于 π 、秩恰为 s 的新列 } ,
a_s(\pi)=\#\{\text{目前已生成、出生格属于 }\pi
\text{、秩恰为 }s\text{ 的新列}\},
a s ( π ) = # { 目前已生成、出生格属于 π 、秩恰为 s 的新列 } , 并定义各累计计数
N ~ ≤ r ( π ) = n 0 + ∑ s = 1 r a s ( π ) ( 0 ≤ r ≤ R ) . (完整路径试验计数)
\widetilde N_{\le r}(\pi)
=n_0+\sum_{s=1}^{r}a_s(\pi)
\quad(0\le r\le R).
\tag{完整路径试验计数}
N ≤ r ( π ) = n 0 + s = 1 ∑ r a s ( π ) ( 0 ≤ r ≤ R ) . ( 完整路径试验计数 ) 它界定这条完整路径上目前已经生成的实际列数。以后遍历到一个原始列的出生格，不再增加这份计数，因为原始预算已经预留。只有生成新列才会改变它；每次对相关路径的每个受影响累计秩增加恰好一。
这些预留仅用于证明次数上界。任何格的实际可用列、被测状态和正交投影仍只包含已经在该格出生或从祖先继承的列；未来出生不提前进入投影。此定义是对原文“路径先验界和 trial cap”的具体实现，不声称原文逐字定义了这个计数对象。
先从根向下构造主目录。在一个活跃格内，只要还有要求的测试失败，就任选一个失败凭证并插入相应新列。为证明过程有限，暂时规定：若某条完整路径的任一累计试验计数第一次超过 n r n_r n r n 0 n_0 n 0
假设第一次超限由格 I I I π \pi π R R R n R n_R n R
N ~ ≤ R ( π ) ≤ n R + 1 = T ∗ . (试验长度上界)
\widetilde N_{\le R}(\pi)\le n_R+1=T_*.
\tag{试验长度上界}
N ≤ R ( π ) ≤ n R + 1 = T ∗ . ( 试验长度上界 ) 这条路径上每个格的局部插入序列长度都不超过这个数。其他分支的插入不进入该路径计数。于是第 8 节对每个主秩的界可用，预算余量给出
a s ( π ) ≤ ( Q / 4 ) n s − 1 ( 1 ≤ s < R ) .
a_s(\pi)\le (Q/4)n_{s-1}\quad(1\le s<R).
a s ( π ) ≤ ( Q /4 ) n s − 1 ( 1 ≤ s < R ) . 主阶段尚无 helper 列，故 a R ( π ) = 0 a_R(\pi)=0 a R ( π ) = 0 s = R s=R s = R r ≥ 1 r\ge1 r ≥ 1
N ~ ≤ r ( π ) = n 0 + ∑ s = 1 r a s ( π ) ≤ n 0 + Q 4 ∑ s = 1 r n s − 1 = n 0 + Q 4 ( Q − 1 ) ( n r − n 0 ) ≤ n r + 2 n 0 3 ≤ n r 2 < n r . (超限矛盾)
\begin{aligned}
\widetilde N_{\le r}(\pi)
&=n_0+\sum_{s=1}^{r}a_s(\pi)\\
&\le n_0+\frac Q4\sum_{s=1}^{r}n_{s-1}\\
&=n_0+\frac{Q}{4(Q-1)}(n_r-n_0)\\
&\le\frac{n_r+2n_0}{3}
\le\frac{n_r}{2}<n_r.
\end{aligned}
\tag{超限矛盾}
N ≤ r ( π ) = n 0 + s = 1 ∑ r a s ( π ) ≤ n 0 + 4 Q s = 1 ∑ r n s − 1 = n 0 + 4 ( Q − 1 ) Q ( n r − n 0 ) ≤ 3 n r + 2 n 0 ≤ 2 n r < n r . ( 超限矛盾 ) 末两步使用 Q ≥ 4 Q\ge4 Q ≥ 4 n r ≥ 4 n 0 n_r\ge4n_0 n r ≥ 4 n 0 n 0 n_0 n 0
每次失败都加入一个新私有标签。因为临时停止条件不可达到，一个格不能无限插入而始终保持完整路径计数不超过 n R n_R n R a s ( π ) a_s(\pi) a s ( π ) s < R s<R s < R
主目录全部完成以后，才固定整个 helper 基并启动 helper 阶段。沿用已经记入全部主列的完整路径计数，原始出生及已建主列的逐格读取均不再改变它。随后只有新 helper 列使 a R ( π ) a_R(\pi) a R ( π )
a R ( π ) ≤ ( Q / 4 ) n R − 1 .
a_R(\pi)\le (Q/4)n_{R-1}.
a R ( π ) ≤ ( Q /4 ) n R − 1 . 把这个新界与主阶段已经证明的 a s ( π ) a_s(\pi) a s ( π ) N ~ ≤ R ( π ) ≤ n R / 2 \widetilde N_{\le R}(\pi)\le n_R/2 N ≤ R ( π ) ≤ n R /2
新列只向后代继承，不反向加入祖先的可用列；所以后代构造不改变祖先已完成的格内测试。主历史的全部因子及目标都只用秩小于 R R R
所得路径总预算满足
log n R = log n 0 + R log Q ≤ C a k 2 a + 3 . (最终路径预算)
\log n_R
=\log n_0+R\log Q
\le C_a k^{2a+3}.
\tag{最终路径预算}
log n R = log n 0 + R log Q ≤ C a k 2 a + 3 . ( 最终路径预算 ) 指数是固定的，不依赖空间深度、整棵树的分支数或后来线性化的精度。
10. 平滑平均不会增加一个 pad 数量因子
源文的正平滑滤子是同秩、不同 pad 的 P P P
P ‾ = 1 P ∑ p = 1 P P ( p ) .
\overline P=\frac1P\sum_{p=1}^P P^{(p)}.
P = P 1 p = 1 ∑ P P ( p ) . 相应补算子也可写为
1 − P ‾ = 1 P ∑ p = 1 P ( 1 − P ( p ) ) .
1-\overline P=\frac1P\sum_{p=1}^P(1-P^{(p)}).
1 − P = P 1 p = 1 ∑ P ( 1 − P ( p ) ) . 所以一个长度 m m m 1 1 1
目录构造已经把每种具体 pad 选择列为一个名字。对每一项，形式测试都满足原式 13 的同一上界。四线性形式对目标残差线性，故三角不等式把同一上界传给平均历史，不额外产生 P m P^m P m
具体 pad 的数量已经进入第 1 节的名字计数 S S S
同一理由适用于目标补滤子的平均：先对每个具体目标掩膜证明测试，再对归一化权重求平均。
11. 私有坐标为什么正好解释阈值的归一化
设秩不超过 r r r
Y = ∑ v ∈ A c v Φ v , ∣ A ∣ ≤ n r .
Y=\sum_{v\in\mathcal A}c_v\Phi_v,\quad
|\mathcal A|\le n_r.
Y = v ∈ A ∑ c v Φ v , ∣ A ∣ ≤ n r . 每个系数在格内为常数。私有坐标正交，且 ϵ v ≥ D − 2 \epsilon_v\ge D^{-2} ϵ v ≥ D − 2
D − 2 ∑ v ∣ c v ∣ 2 ≤ ∥ Y ∥ 2 , I 2 .
D^{-2}\sum_v|c_v|^2
\le\|Y\|_{2,I}^2.
D − 2 v ∑ ∣ c v ∣ 2 ≤ ∥ Y ∥ 2 , I 2 . 若 Y Y Y z z z
∑ v ∣ c v ∣ ≤ n r ( ∑ v ∣ c v ∣ 2 ) 1 / 2 ≤ D n r ∥ z ∥ 2 , I . (原始投影的系数和)
\sum_v|c_v|
\le\sqrt{n_r}\left(\sum_v|c_v|^2\right)^{1/2}
\le D\sqrt{n_r}\,\|z\|_{2,I}.
\tag{原始投影的系数和}
v ∑ ∣ c v ∣ ≤ n r ( v ∑ ∣ c v ∣ 2 ) 1/2 ≤ D n r ∥ z ∥ 2 , I . ( 原始投影的系数和 ) 这里不需要物理列之间正交，甚至允许它们完全相同。私有坐标负责保持系数可控。
现在把一个较低秩的源投影展开，系数和至多 D n r − 1 ∥ z ∥ 2 , I D\sqrt{n_{r-1}}\|z\|_{2,I} D n r − 1 ∥ z ∥ 2 , I
∣ H I ( 目标残差 , 较低秩源投影 , A , B ) ∣ ≤ τ 3 ∥ g ∥ 2 , I ∥ z ∥ 2 , I , ∥ A ∥ 2 , I , ∥ B ∥ 2 , I ≤ 1. (源系数相消)
|H_I(\text{目标残差},\text{较低秩源投影},A,B)|
\le
\tau_3\|g\|_{2,I}\|z\|_{2,I},
\quad
\|A\|_{2,I},\|B\|_{2,I}\le1.
\tag{源系数相消}
∣ H I ( 目标残差 , 较低秩源投影 , A , B ) ∣ ≤ τ 3 ∥ g ∥ 2 , I ∥ z ∥ 2 , I , ∥ A ∥ 2 , I , ∥ B ∥ 2 , I ≤ 1. ( 源系数相消 ) 四个槽位按实际用途放置，不改变这个系数估计。这正是分母 D n r − 1 D\sqrt{n_{r-1}} D n r − 1
12. 后加 helper 目录的固定性条件
主目录完成以后，先构造并固定 Section 7 所需的整个 side states，然后才启动 helper 插入。原文要求每个活跃格的这些额外基本向量至多有
exp ( k C 2 )
\exp(k^{C_2})
exp ( k C 2 ) 个，计入槽位、组和模式等名字。它们不是各个频率展开项。
helper 测试只用主目录中的纯源列。其基本向量在 helper 阶段开始时固定；后续 helper 插入只改变投影历史。若这些基本向量有额外私有坐标，所有新 helper 坐标都从与它们不相交的坐标集合中选择。于是第 3 节“物理矩等于向量矩”的理由仍成立。
把这些固定基本向量的数量计入 S S S R = L + 5 R=\mathcal L+5 R = L + 5
这一结论依赖上述 side states 的数量及其先固定后插入的次序。本章证明在这些输入下目录可闭合；Section 7 怎样构造这些整个状态仍是另外的证明任务。若每插入一次 helper 就重新任意选择基本向量，第 4 节的反例已经说明现有能量论证不再适用。
13. 目录预算与图阈值的参数次序
图的边阈值 H e d H_{\mathrm{ed}} H ed
因此可以依次选择：
固定基本模板复杂度、颜色和历史长度等预算，按第 9 节固定全部 n r n_r n r
按这些路径计数、私有权重和系数预算，把 τ 2 \tau_2 τ 2
最后按 Lemma 6.1 选择 H e d H_{\mathrm{ed}} H ed τ 2 \tau_2 τ 2
对最终选定的图，才固定一份适用的颜色实现和实际掩膜，随后执行上述目录构造。计数估计对这些具体数值一致。这里不要求同一份随机颜色数组同时适用于所有可能的 H e d H_{\mathrm{ed}} H ed
若模板复杂度每次插入都会增加，第一步中的 H 0 H_0 H 0
14. 本章闭合的结论及其边界
在固定的原始图资料、有限名字历史、基本向量和活跃格路径预算下，主目录及随后以固定整个 side states 为基的 helper 目录都能有限终止。所有要求的纯源残差测试成立，路径列数的对数为 k k k
证明中实际展开了三个环节：新私有坐标把物理大矩变成正交增量；二进前缀行界处理同一个固定基本向量的变化投影历史；一次全秩预算排除第一次路径超限。没有把变化状态当成固定向量，也没有为每个触发源重新付一次能量预算。
尚作为来源输入保留的，是 Proposition 5.8 的活跃格路径数、后续定位与转移要求哪些有限名字历史，以及 Section 7 整个 helper 基的构造与数量。这里没有证明任意空间深度的完整 Lemma 3.4 压缩，也没有把这一局部目录闭合升级成完整 H 主定理。
后续实际历史现已在 H12 第 6 节 和历史附录 中逐项列出。H12 由此展开当前组局部化与两个远带方向；完整侧基的构造与数量、线性侧能量和近带全局估计仍作为后续输入。这一补充不改变本章的条件式目录终止结论。
返回 D 的证明次序 H Lemma 9.1：有限计数证明