第三单元（续）：把随深度变化的非核心函数存成固定向量

本篇展开 D §6.5.1，原文 pp.54–55，式 (6.19)。近差分需要在同一个原区间内保留全部匹配索引。为将它送入固定函数的短块估计，原稿把各次需要的函数存入一个有限 Hilbert 直和，每次使用只选其中一个位置。

目标是两边不对称的平方能量界：

\sum_\nu\|\operatorname{stack}_{a,\nu}\|_2^2 \le P G_0|R|, \qquad \sum_\nu\|\operatorname{stack}_{b,\nu}\|_2^2 \le G_0|R|. \tag{Stack-energy}

差分指标只作为第一边向量的额外坐标，不在第二边重复复制。这项区别将在后面留下 $P^{-1/2}$ 的收益。

1. 哪些是函数族指标，哪些只是向量坐标

固定一个源投影转移步骤、近偏移 $\ell$ 和搜索分支。令

\nu=(G,b,\chi),

其中 $G$ 为组， $b$ 为分析块， $\chi$ 记录两侧的组成部分及二进长度选择。两侧的辅助选择先配成同一张有限列表，不使用的组合设为零。其大小在放大允许常数后至多为 $G_0$ 。

对一侧定义固定函数

\operatorname{stack}_{b,\nu}(y) =(W_{\nu,i}(y))_{i\in\mathcal I_\nu} \in\bigoplus_{i\in\mathcal I_\nu}\mathcal H.

具体的二进区间位置 $i$ 是向量坐标，不另放入 $\nu$ 。所以

\|\operatorname{stack}_{b,\nu}\|_2^2 =\sum_i\|W_{\nu,i}\|_2^2.

第一边另有合法差分指标 $p$ ，故坐标为 $(i,p)$ 。

每个完整坐标在形成时限制到选用它的使用区间之并。随后若切去原求和项，不再改变已经存好的函数。每次使用只选择一个二进位置，第一边同时保留固定 $\ell$ 下全部合法匹配差分。

式 (Stack-energy) 的 $\nu$ 求和已包括全部组与块； $G_0$ 的辅助列表大小并不再次替代组数或块数。

2. 一个固定向量上的嵌套投影积估计

这里展开所用 H Lemma 3.3（pp.8–9）。

设 $\mathcal X$ 为 Hilbert 空间，每个 $j=1,\ldots,m$ 有嵌套正交投影

P_0^j\le P_1^j\le\cdots\le P_T^j, \qquad Z_n=P_n^m\cdots P_n^1,

并令

L_T=1+\lceil\log_2(T+1)\rceil.

若有限行算子满足

\sum_\nu\|B_\nu x\|^2\le\|x\|^2,

则任意选择 $n(\nu)\in\{0,\ldots,T\}$ 都满足

\left(\sum_\nu\|B_\nu Z_{n(\nu)}x\|^2\right)^{1/2} \le L_T^m\|x\|. \tag{Prefixes}

令 $\Delta_0^j=P_0^j$ 、 $\Delta_n^j=P_n^j-P_{n-1}^j$ 。这里投影次序表示值域递增。同一 $j$ 的这些差分两两正交；对指标块 $A$ ，定义 $\Delta_A^j=\sum_{n\in A}\Delta_n^j$ 。每个前缀 $\{0,\ldots,n\}$ 可分成二进指标块，每个长度至多一块，长度种类至多 $L_T$ 。

将每个 $P_{n(\nu)}^j$ 按此分解。固定 $m$ 个长度，在一个固定长度元组下，把具有相同指标块元组的行分组。联合行界使其平方和不超过

\|\Delta^m_{A_m}\cdots\Delta^1_{A_1}x\|^2.

再对所有指标块元组求和，逐层使用该层的正交性，结果至多为 $\|x\|^2$ 。这里从未要求不同层的投影交换。

长度元组至多有 $L_T^m$ 个。在行的 Hilbert 直和中用三角不等式，证明式 (Prefixes)。

2.1 投影积跳跃的平方和

精确展开为

Z_n-Z_{n-1} =\sum_{j=1}^{m} P_n^m\cdots P_n^{j+1} \Delta_n^j P_{n-1}^{j-1}\cdots P_{n-1}^1.

先对这 $m$ 项使用 $\|\sum_j u_j\|^2\le m\sum_j\|u_j\|^2$ ，再逐项删去左边压缩。固定 $j$ 后，行 $B_n=\Delta_n^j$ 满足联合压缩界。将式 (Prefixes) 用于前面的 $j-1$ 层及前缀 $n-1$ ，得到

\sum_{n=1}^{T}\|(Z_n-Z_{n-1})x\|^2 \le m\sum_{j=1}^{m}L_T^{2(j-1)}\|x\|^2 \le m^2L_T^{2(m-1)}\|x\|^2. \tag{Product-jumps}

$m=0$ 时积为恒等，所有差为零。

对内部不相交的有序时间区间 $[r,t]$ ，将所有端点按顺序列出，限制每层投影到这一非递减端点列，再只保留 $r\to t$ 的跳跃，得到相同类型的界。对于一个长度为 $O(K)$ 的时间窗口，代价为

(C\log(K+2))^{O(m)}.

每次应用的 $x$ 必须是同一个固定向量。

3. 每个块内函数的二进前缀表示

对一个块内的函数列 $W_s$ ，写

W_s=W_b+\sum_{[r,t]\in\mathcal P(b,s)}(W_t-W_r),

其中 $\mathcal P(b,s)$ 是指标前缀 $[b,s]$ 的二进分解。在每个固定长度上，出现的区间互不相交，而且一次使用至多选择该长度的一个位置。

把基础函数 $W_b$ 和每个差分函数作为固定向量坐标存储。精确表达当前 $W_s$ 时，是对少数二进长度各取一个坐标并求和。长度选择归入 $\chi$ ，具体位置留作坐标。

需要三类非核心组成部分：基本 $U$ 输出、块内固定的模式非核心部分 $V_{G,b}$ ，以及滚动部分 $Z_{G,s}-Z_{G,u_b}$ 。

4. 基本 $U$ 组成部分

这种情形直接存储已经形成的各深度函数。D 式 (6.14) 已控制它们在全部实际使用上的平方能量。随后作用的辅助投影积在相应当前区间上局部压缩，限制到选择这些坐标的区间之并只降低范数。

因此不带额外差分指标的基本 $U$ 存储能量被 $G_0|R|$ 控制。若第一边带一个差分 $A_a^p$ ，可先写成两个正投影端点并逐个估计，再对至多 $P+1$ 个指标求和；允许成本为 $P G_0|R|$ 。

5. 块内固定的 $V_{G,b}$

记 $T_s$ 为后续辅助投影积，必要时包括一个差分端点。固定兼容的单独投影选择后，它由 $m=O(\log L)$ 套嵌套投影组成。此处被作用的

V_{G,b}

是在整个块内固定的同一个函数。

对每个固定二进长度，式 (Product-jumps) 给出

\|T_bV_{G,b}\|_2^2+ \sum_{\substack{[r,t]\text{ 为该长度}\\\text{的所需区间}}} \|(T_t-T_r)V_{G,b}\|_2^2 \le(C\log(K+2))^{O(m)}\|V_{G,b}\|_2^2.

再对二进长度求和，并用已证

\sum_{G,b}\|V_{G,b}\|_2^2\le G_0|R|,

得到所需存储能量。各坐标形成时的使用集合限制只会降低左侧。

这里可以对固定向量使用嵌套投影积引理，正是因为 $V_{G,b}$ 在块中没有随 $s$ 改变。不能把所有实际深度函数都直接代入同一次式 (Product-jumps)。

6. 滚动部分必须再拆一次差分

令

W_s=T_s(Z_{G,s}-Z_{G,u_b}).

其基础值 $W_b$ 使用区间 $[u_b,b]$ 的局部输出变化。不同块的这些区间只有固定次数重叠，故 D Lemma 6.1 控制全部基础值的能量。

对一个外层二进区间 $[r,t]$ ，精确地有

W_t-W_r =T_t(Z_{G,t}-Z_{G,r}) +(T_t-T_r)(Z_{G,r}-Z_{G,u_b}). \tag{Rolling-jump}

6.1 第一项直接使用已证变化界

固定外层长度时， $[r,t]$ 在每个块中内部不交。对于所需较细使用区间，先将其并扩大到包含它们的完整深度 $t$ 区间；这些区间都有后代实际使用。

$T_t$ 在深度 $t$ 区间上局部压缩，故第一项的限制输出范数由完整端点上的 $Z_{G,t}-Z_{G,r}$ 控制。对组与区间使用 D Lemma 6.1，得到 $G_0|R|$ 类型的平方和。这里没有在任意细子集上直接使用局部投影压缩性。

6.2 第二项先固定内层区间

每个块先在一个包含全部 $[u_b,r]$ 的 $O(K)$ 时间窗口内固定同一套二进网格，例如使用长度 $8K$ 、左端为 $u_b$ 的网格。全部 $[u_b,r]$ 都在这套网格中取前缀分解；对同一内层区间只定义一个固定输入 $X$ ，合并其全部用途；各外层位置的 $(T_t-T_r)X$ 仍分别作为输出坐标。因此不同的同长度区间互不相交。固定外层长度、内层长度及一个内层区间 $[a,v]$ 。所有选用这一内层区间的外层位置，都满足 $v\le r$ 。

令 $\Omega$ 为这些外层位置实际需要的完整深度 $r$ 区间之并，定义一个固定函数

X=\mathbf1_\Omega(Z_{G,v}-Z_{G,a}). \tag{Fixed-X}

虽然不同外层位置的 $r$ 不同，这个 $\Omega$ 先取它们的总并，随后保持固定。

$T_r,T_t$ 的局部性表明，在每个需要的深度 $r$ 区间上，用 $X$ 替代原来的 $Z_{G,v}-Z_{G,a}$ 不改变所需输出。因为该完整区间全部包含在 $\Omega$ 内，而两个算子只读取它及其后代。

因此可以对这一个固定 $X$ 使用式 (Product-jumps)，对全部外层位置求和，成本为

(C\log(K+2))^{O(m)}\|X\|_2^2.

6.3 再对这些固定函数求能量和

把 $\Omega$ 扩大到包含它的完整深度 $v$ 区间之并，范数只增加；每个这样的区间都有某个后来实际使用。D Lemma 6.1 因而可以估计这个完整端点上的 $Z_{G,v}-Z_{G,a}$ 。

固定内层长度时，各块的 $[u_b,r]$ 窗口长度为 $O(K)$ ，相邻块起点间隔为 $K$ ，故这些窗口只有固定次数重叠；每个窗口内同长度二进区间内部不交。于是对组、块与内层位置求和，不增加 $K$ 的固定幂，只得到 $G_0|R|$ 类型的平方和。

注意，式 (Fixed-X) 中两个端点可以分别使用 $F_v,F_a$ 。这不妨碍外层引理：在固定 $a,v,\Omega$ 后，它们的差是一个已经确定的函数，所有外层位置都作用于这个同一个 $X$ 。

7. 为什么二进长度与投影积只产生 $G_0$

恢复前面的所有二进长度选择时，只产生若干个 $\log(K+2)$ 的因子。嵌套投影积的代价为

(C\log(K+2))^{O(m)},\qquad m=O(\log L)=O(\log k).

源参数给出 $K\le\operatorname{poly}(P,k)$ ，并有 $P=\lceil\exp(\alpha k^\theta)\rceil$ 。因此

\log\log(K+2)\le C_q+C\log(2k),

这些代价的对数均受 $(1+\log(2k))$ 的固定幂控制，可以纳入

G_0=\exp\bigl(C_q(1+\log(2k))^C\bigr).

辅助组成部分及长度选择的配对列表也具有相同量级。

所有正投影平均先按兼容选择计算，再用 Jensen 不等式恢复；内部共享选择跨组保持一致，比较深度的选择也保持耦合。第一边的额外差分指标至多有 $P+1$ 个，所以它比未带差分的一边最多多一个 $P$ 因子。至此得到式 (Stack-energy)。

这一强能量界中没有 $K$ 的固定幂。此前路径大小与顶部数量可以支付 $P^C$ ，但若在这里也粗略支付 $K^C$ ，就可能消掉近差分的负幂收益。

8. 这些函数为什么适合后面的随机化

完成上述构造后，每个 $\operatorname{stack}_{a,\nu}$ 、 $\operatorname{stack}_{b,\nu}$ 都是一个固定的有限 Hilbert 向量函数。它们的定义已经包含了全部当时选用坐标的原使用集合。后来的停止只移走求和项，不重新裁剪存储函数。

具体二进位置和第一边的差分索引都保留为向量坐标。下一篇可用独立 Rademacher 符号选择当前位置，并用同一差分符号将第一边与冻结互补差分按固定 $\ell$ 配对。这样随机化之后的标量函数是跨求和区间固定的。

式 (Stack-energy) 本身只给 $L^2$ 能量，不自动说明每个随机化标量函数属于 $L^q$ 、 $q>2$ 。后面引用固定 $L^q$ 的局部常数时，必须通过源短块比较的明确步骤，不能直接跨过这项函数类别差别。

原文范围

D pp.54–55，式 (6.19)：固定函数族指标、位置和差分作为坐标、三个非核心组成部分的能量。
H Lemma 3.3，pp.8–9：嵌套前缀积与固定向量跳跃平方和，本篇给出完整有限证明。
D p.55：滚动函数的两层二进分解，固定内层区间后再使用外层固定向量估计，及 $G_0$ 成本核算。

下一篇 D §6.5.2 将精确陈述短块比较，证明匹配随机化与整个祖先区间最大值的组合怎样把式 (Stack-energy) 转为 $P^{-1/2}$ 的近差分界。