选择一段文字或公式,即可在这里留下建议。保存后的建议仅作者可见,审核后才会公开。
多重遍历平均 / 原文精读
第三单元(续):坏层数怎样控制模式行的平方和
本篇讨论 D §6.4 的前半部分,原文 pp.49–50,特别是式 (6.12)。前篇冻结行定理要求每组模式投影已有普通联合 Bessel 界。这里说明原稿实际选择的非核心模式行为什么满足这一前提,再从正交投影过渡到模式系数的精确部分和。
D 沿用 H §§8.4–8.6 的图、好坏分类及其几何结论。本篇明确保留两项源前提:每个主列的异常块与坏高度数界,以及不相邻模式的振荡内积小量。相应的有理高度稳定证明与 Fourier 振荡估计尚未在这里全部重新证明。计数链、从小内积到 Bessel 界,以及精确部分和的后续推导则在下文展开。
1. 在同一个冻结列表上定义两个图
固定位置、组、偏移及一个分析块。模式列表在 ub=b−4K 冻结,在深度 vb=b−2K 的保留区间 J 上比较,当前块末为 tb=b+K。包括系数为零的所有已可用模式,列表在相关后代上保留。统一常数 D∗≥ek 同时控制一条路径上全部相关组的永久模式数、冻结系数绝对值之和及私有权重倒数;水平参数维数满足 dmax≤CqkC,见 D 式 (6.9) 及其后说明。
模式的标量二次频率斜率为
ωm(x)=2λmx+γm.
H 用同一个水平频率向量 ϑ,以及层数参数
Δ=10,Lh=6h,Eh=A0h+1(0≤h≤J∗),
其中 A0≥6 足够大。Lh 是允许平移的分母,Eh 是整数平移范围,不是正交投影。分离阈值记为 Ξ,源选择为 Ξ=D∗1000。
在高度 h,若存在整数向量 n、∥n∥∞≤Eh,使
x∈Jsup∣ωm(x)−ωm′(x)+n⋅ϑ/Lh∣≤Ξ/rvb,
则在 PRE 图中连接 m,m′。将右侧换成 Ξ/rtb,就定义 CURRENT 图。这里 rs=2−s∣Joriginal∣。
因为 rtb<rvb,PRE 图包含的边也是 CURRENT 图的边。记相应连通分量为
Eh(m),Fh(m).
把旧见证 n 换成 6n,表明两图随 h 增加只加边不删边。后代区间缩小且比较阈值增大,也使既有边在原文规定的后续列表上保留。
“最小分量”在本节指高度零的连通分量。对模式集合 D,π(D) 表示其主列标签集合,不是概率因子映射。
2. 好高度、核心模式与非核心模式
原文有一个主列是否在当前块异常的判断,以及非异常主列在高度 h 是否满足高度稳定条件的判断。它们来自 H Lemmas 8.2–8.3(pp.67–69)。本节使用的准确数量结论是:
- 一个固定主列沿路径至多在 Bbad≤Cdmax 个块异常;
- 在一个固定块,非异常主列至多在 Abad≤CdmaxRht 个高度不满足稳定条件。
其中 dmax 控制相关水平参数维数,Rht 是源有理高度论证的辅助整数。它可能依赖较大的模式常数。所选总高度 J∗ 将先吸收这种依赖。
对 h≥Δ,一个模式 m 在高度 h 为好,要求
⌊log1.1∣π(Eh−Δ(m))∣⌋=⌊log1.1∣π(Fh(m))∣⌋,
且 π(Fh(m)) 中至少九成主列在该块非异常并在该高度稳定。低于 Δ 的高度一律为坏。
固定一个足够小的绝对常数 δ∗>0。若模式的坏高度数至多为 δ∗(J∗+1),称为核心模式;否则为非核心模式,原文称 linear-side mode。
同一个最小 PRE 分量中的模式,在所有更高 PRE 图和 CURRENT 图中具有相同连通分量。因此它们的好坏判断完全相同,整个最小 PRE 分量要么全为核心,要么全为非核心。这一简单继承事实足以用于本篇的非核心事件选择。
3. 非核心事件如何排成链
固定一个位置与组。一个事件为
(b,J,E),
其中 J 是保留的深度 vb 区间,E 是其冻结列表中的一个非核心最小 PRE 分量。
将分析块编号分成模十的十类。在同一类中,若后事件位于前事件的后代路径上,且两者某些模式相同或在后事件最小 PRE 图中相邻,就从前事件连到后事件。
同类相邻块至少相隔 10K,故后块的 PRE 比较深度不小于前块末深度。前块的每条 CURRENT 边在后块 PRE 图中仍成立:较后区间更小,阈值更宽,模式与整数平移见证保留。最小 PRE 的连线在所有高度仍保留。
于是对一条事件链,任取每个事件的一个模式,并记其在高度 h 的主列集合为 Pi,h,Ci,h,有
Pi,h⊆Ci,h⊆Pi+1,h.(Chain-nesting)
两列也各自随 h 增加。每个集合非空,大小至多为主列数上界 Dm。这里使用主列数,而非可能大得多的模式数 D∗。
4. 一个进入次序的有限求和引理
对应 H Lemma 8.5,pp.69–70。
设非空有限集合
S1⊆⋯⊆ST,∣ST∣≤M,
并有 Xt⊆St,每个元素最多属于 A 个 Xt。则
t=1∑T∣St∣∣Xt∣≤AHM,HM=r=1∑⌊M⌋r1≤1+logM.(Entry-rank)
按元素首次进入 St 的次序编号,同一步进入者任意排序。排名为 r 的元素所处的任何集合至少有 r 个元素,因此每次贡献至多 1/r,总共最多贡献 A/r。对所有排名求和即可。
这个引理不要求知道元素何时离开 Xt;只有每个元素的总出现次数受控。
5. 坏高度链的计数证明
下面展开 H Lemma 8.6(p.70)在当前证明中的形式。
设一条链有 N 个事件,高度为 0,…,J。集合满足式 (Chain-nesting),大小至多 M。每个主列至多在 B 个事件异常;对固定事件,每个非异常主列至多在 A 个高度不稳定。
设异常集为 Xi,高度不稳定集为 Yi,h。对 h≥Δ,坏高度由以下任一条件触发:两个基数的底数 1.1 对数取整不同,或
∣Ci,h∣∣(Xi∪Yi,h)∩Ci,h∣>β.
每个事件有超过 δ(J+1) 个坏高度。定义
L0=⌊log1.1M⌋,Q=Δ(L0+1)+β−1AHM.
5.1 基数变化产生的坏高度数
记
pi,h=⌊log1.1∣Pi,h∣⌋,ci,h=⌊log1.1∣Ci,h∣⌋.
其值在 0,…,L0 中。若两个取整不同,因集合包含,差至少为一,故其指示函数不超过
ci,h−pi,h−Δ=(pi,h−pi,h−Δ)+(ci,h−pi,h).
固定 i,对第一项在 h 上求和至多为 ΔL0:每次单步增长只在至多 Δ 个窗口中出现。
固定 h,由 Ci,h⊆Pi+1,h,第二项在 i 上的和至多为 L0。加上每个事件最初 Δ 个坏高度,这一类坏事件总数至多为
NΔ(L0+1)+(J+1)L0.
5.2 异常与高度不稳定的贡献
坏比例条件的指示函数不超过 β−1 乘异常比例与不稳定比例之和。
固定事件 i,集合 Ci,h 随 h 增加,每个非异常主列最多在 A 个 Yi,h 出现。式 (Entry-rank) 给出不稳定比例总和至多 AHM。
固定高度 h,集合 Ci,h 随 i 增加,每个主列最多在 B 个异常集出现,故异常比例总和至多 BHM。
合并两类,坏高度总数不超过
NQ+(J+1)(L0+β−1BHM).
另一方面它严格大于 δN(J+1)。若
J+1≥δ2Q,
则 NQ 可吸收到左侧的一半,得到
N<δ2(L0+β−1BHM).(Chain-length)
5.3 较大的高度参数在哪里消失
代入
M=⌈Dm⌉,β=1/10,δ=δ∗,A≤CdmaxRht,B≤Cdmax.
H 先将 J∗ 选得足够大,以满足上面的吸收条件。最终链长界因而为
N≤Cδ∗dmaxlog(2Dm).(Short-chain)
Rht 只影响需要取多大的 J∗,不再出现在最终链长中。这是不能把粗略的全部模式高度数直接作为行数成本的原因。
6. 同一链层的模式行具有普通 Bessel 界
给每个事件赋予以它为终点的最长链长度。存在连线的两个事件具有不同层数,所以同一层中两个重叠事件没有相同或相邻的模式。同一块同一区间上的不同事件本来就是不同最小 PRE 分量,也没有跨分量的边。
因此沿一条路径,同层事件的模式标签集两两不交,其总大小至多 D∗。H Lemma 8.7 的振荡部分进一步给出:两个重叠事件间任意模式对,在较小区间上的归一化内积绝对值至多
D∗−200.(Mode-pair)
这一分析小量来自源 PRE 不相邻性、允许的整数平移和截断 Fourier 尾部,是此处明确使用的第二项几何前提。
6.1 从小内积直接证明投影的联合界
令 Pe 为事件 e 的模式张成上的局部正交投影。用对偶性,只需估计这些值域中任意函数 fe 的合成和。写
fe=1Jem∈Ee∑βe,mψm,be=(m∑∣βe,m∣2)1/2.
私有权重下界给出
∣Je∣be2≤D∗2∥fe∥22.
若两个区间不交,内积为零;若相交,由式 (Mode-pair) 及每组至多 D∗ 个模式,
∣⟨fe,ff⟩∣≤D∗−199∣Je∩Jf∣bebf.
沿路径最多有 D∗ 个同层非空事件。故
e=f∑∣⟨fe,ff⟩∣≤D∗−199∫Re:y∈Je∑be2dy≤D∗−198e∑∣Je∣be2≤D∗−196e∑∥fe∥22.
加上对角项,得到一个绝对的合成界;由对偶性,这些局部模式投影具有绝对的普通联合 Bessel 常数。
6.2 加回块余数与链层
共有十个块余数类,每类链层数满足式 (Short-chain)。将各层的平方和相加,固定组的全部事件行具有平方 Bessel 常数
Cdmaxlog(2Dm)≤G0.
这是前篇 D Lemma 6.3 所需的联合行前提,确实由所选事件结构得到,而不只是每行单独为正交投影。
7. 冻结行定理处理随块变化的函数
事件行的模式输出区间为 Je,主端点是包含它的深度 ub 区间。模式列表在该端点已可用,保留区间又在本块后续步骤中实际使用,因此前篇冻结行定理的条件成立。
于是
G,b,J,E∑∥PE,JZG,b∥22≤G0∣R∣.(Projection-energy)
这里跨组求和保持同一个位置、搜索分支与颜色。各块的冻结函数来自各自的 Fub。这个求和已由变化函数行定理处理,不要求不同块的模式系数彼此相同。固定不变的是模式标签、展开资料与相关算子结构。
8. 正交投影与精确系数部分和的区别
令
TE,J=1Jm∈E∑αmψm
为冻结模式展开在 E 中的精确系数部分和。一般情况下,它不等于 PE,JZG,b,因为不同模式只近似正交。
补集中的每个模式与 E 中每个模式满足式 (Mode-pair)。若 v 为 E 张成内归一化 L2(J) 范数为一的函数,私有方向给出其系数 ℓ1 范数至多 D∗3/2。冻结函数的外部系数绝对值之和至多 D∗,所以
∣⟨ZG,b−TE,J,v⟩2,J∣≤D∗−200D∗D∗3/2≤D∗−190.
这里 ⟨⋅,⋅⟩2,J 用归一化测度。因此
∥PE,JZG,b−TE,J∥2,J≤D∗−190.(Subtotal-error)
把链层数上界记为
Nlev≤Cdmaxlog(2Dm).
固定一个模十余数类、一层及路径点 y,每个包含该点的事件至少占用一个永久模式标签。同组同层的这些标签不交,不同组的永久标签又已区分;统一预算包含所有相关组。因此事件数至多为 D∗,从而
e∑∣Je∣≤10NlevD∗∣R∣.
式 (Subtotal-error) 的普通 L2 平方误差至多为 ∣Je∣D∗−380,所以全部误差平方和至多
10NlevD∗−379∣R∣.
由 dmax≤CqkC、logDm≤CqkC 和 D∗≥ek,提高起始精度后,这项至多为 ∣R∣。最后逐项使用
∥TE,J∥22≤2∥PE,JZG,b∥22+2∥TE,J−PE,JZG,b∥22,
与式 (Projection-energy) 合并,得到全部精确 TE,J 的平方范数和界。
9. 非核心部分的平方能量
同一 J 上,不同最小 PRE 分量的标签互不相交,并满足同样的跨模式小内积。第 6.1 节的系数计算因此也适用于这些精确部分和,得到其合成和的平方范数由各自平方范数和控制。
定义 Vl,G,b 为 Zl,G,b 的全部非核心模式精确部分和,包括私有坐标;在无所需输出或使用依据的分支设为零。对同层 J 的不交区间及全部 G,b 求和,得到 D 式 (6.12):
G,b∑∥Vl,G,b∥22≤G0∣R∣.(Side-energy)
整个证明对固定但任意的备选偏移成立。后续可先平均物理逼近误差,再选择一个合适偏移;这个统一平方能量界仍然保留。证明也没有要求同一个模式在不同块中的冻结系数相等。
原文范围与下一步
- D pp.49–50:冻结列表、PRE/CURRENT 分类、事件行及非核心精确部分和,式 (6.12)。
- H §§8.4–8.5,pp.67–70:两个图、好坏高度、核心分类、进入次序求和与坏高度链。
- H Lemma 8.7、Proposition 8.9,pp.70–73:振荡小内积、事件分层、联合 Bessel 与精确系数部分和。
本篇只将源异常块/高度计数及振荡小内积作为前提,不把它们归因于普通正交性。下一段 D pp.50–52 要选择偏移、同时控制滚动变化与非核心部分的路径平方和,再取得核心代表的数量与大小条件。那些后续步骤仍需要分别核对。