选择一段文字或公式,即可在这里留下建议。保存后的建议仅作者可见,审核后才会公开。
多重遍历平均 / 原文精读
第三单元(扩展):稀疏尺度上的有限计数
本篇逐步展开 H Lemma 9.1,2026-10-05 版,pp.81–87。它在 D §6.6 中提供小于一次幂的计数收益;与前篇振幅插值之间的衔接见“核心元组的计数与振幅插值”§§5–6。
以下证明限于所列五项假设下的有限命题。原文版本与 D 的引用已经逐项对照;D 的实际应用仍须提供频率间隙、角色计数及标量核估计。
1. 有限命题及其五个条件
四个位置为 0,1,2,3,其中三或四个为核心位置,集合为 J。给定
M,L≥1,d≥0,B≥1,0<μ≤1≤ν,ζ∈Rd.
每个核心位置有一个有限实数标签集 Ai,同一位置的标签彼此不同,且 ∣Ai∣≤M。
固定 R0>0。对有限多个不同整数 s,给定
Rs=R02s,Es⊆i∈J∏Ai,Ns=∣Es∣.
这里 Rs 是倒尺度。一个元组在不同尺度出现时,按不同“出现”计数。
假设:
(1)两个不同核心位置的标签至多确定一个完整核心元组,并且该对标签至多在 L 个尺度出现。 (2)若有侧位置 l,存在 ws≥0、∑sws≤M,使在尺度 s 包含任一固定核心标签的元组数至多为 ws。 (3)同一核心位置的不同标签 a,a′ 分别在尺度 s,t 出现时,对所有整数向量 ∣n∣∞≤Q,
∣a−a′+n⋅ζ∣>Σmax(Rs,Rt).(Separated)
(4)对任一三核心子集,设 l′ 为被排除的位置,αi=i−l′。每个元组在尺度 s 都有一个整数向量 ∣n∣∞≤B,使
μRs≤i∑αiai+36n⋅ζ≤νRs.(Test-annulus)
其中各 αi 均属于 {±1,±2,±3}。 (5)在每个被占用的尺度,对所有 ∣n∣∞≤Q,
∣n⋅ζ∣∈/[μRs/1000,1000νRs].(Shift-gap)
另有固定的充分大绝对常数 Cres,使
Q≥Cres(d+1)2B,Σ≥Cres(d+1)2ν.(Reserves)
要证对 0<δ≤1,
s:Ns≤δM2∑Ns≤CℓL29δ1/2080M2,ℓ=1+log2(2+(d+1)2ν/μ).(Sparse-count)
常数不依赖维数、尺度数或标签数。
2. 先把实数数据放到共同细格
所有标签、尺度和 ∣n∣∞≤Q 的平移均为有限集合。可以用步长 h0>0 的共同格逼近全部实数,并使原坐标落在 h0 的一个固定整数倍上,保证稍后除以 1,2,3 仍落在共同细格内。
取 h0 时放在全部有限数据之后。使所有误差小于最小 Rs 的足够小倍数,就保留:
- 分离条件中的 Σ/2;
- 环带下界 μ/2 与上界 2ν;
- 原纯平移间隙内部更窄但仍有固定余量的间隙。
具体地,取工作参数 μ=μold/2、ν=2νold、Σ=Σold/2,并在原 Cres 中预留固定倍数余量。网格证明只要求
∣n⋅ζ∣∈/[μRs/50,50νRs].(Grid-gap)
这个区间严格位于原始宽禁区内部,有限数据的充分细逼近保留它。这里没有声称舍入后仍自动满足重新命名参数下的全部千倍禁区。
宽度向上取整至格点只增加 h0。这些固定倍数由式 (Reserves) 的绝对余量吸收。以下沿用原字母写格点情形,但纯平移反证只用式 (Grid-gap);第 10 节产生的区间严格包含在这一较窄禁区内。每个估计均与 h0 无关,因而最后适用于原实数数据。
3. 一个有许多四色路径的二部图
设二部图两侧顶点数至多为 M,边数至少为 ηM2,0<η≤1。边有至多 M 种颜色,同一顶点相接的边颜色互不相同。要找左侧一个大小至少 cηM 的集合,使其中任意两点之间有至少 cη5M3 条四步路径。
3.1 随机邻域与坏点对
把右侧补足到 m=⌈M⌉≤2M 个顶点。均匀选一个右侧顶点,令 Y 为其左侧邻域。则
E∣Y∣≥ηM/2,E∣Y∣2≥η2M2/4.
称一个有序左侧点对为坏点对,如果其共同邻点数小于 c0η2M。它同时落入 Y 的概率为共同邻点数除以 m。因此 Y2 中坏有序对数 BY 满足
EBY≤c0η2M2.
取 c0 充分小,便有
E(∣Y∣2−100BY)≥cη2M2.
所以存在一个 Y,满足 ∣Y∣≥cηM 且 BY<∣Y∣2/100。
3.2 删除少量顶点
删去在 Y 中有超过 ∣Y∣/4 个坏伙伴的顶点。被删数少于 ∣Y∣/25。令剩余集合为 B0,仍有
∣B0∣≥cηM.
对 a,a′∈B0,至少 ∣Y∣/2 个中点 z∈Y 同时是二者的好伙伴。每对 (a,z)、(z,a′) 各有至少 c0η2M 个右侧共同邻点,可独立选择。因此四步路径数至少为
c∣Y∣(η2M)2≥cη5M3.(Four-paths)
允许重复顶点。固定起点与四个有序边颜色,可按颜色唯一重建每一步,因此固定两端点时,不同路径对应不同的有序四色组。
4. 按计数质量分块,构造差集覆盖
以下先处理充分小的 δ>0,较大 δ 留到末节用总质量粗界处理。只保留 Ns≤δM2 的尺度。由任意一对核心位置的唯一性及尺度重数,
s∑Ns≤LM2.
取稍后确定的参数
0<α≤1,δ≤α/2,0<κ<1.
把保留尺度按 Rs 递减排列,贪心分成每块质量至多 αM2 的连续计数块。除最后一块外,各块质量大于 (α−δ)M2。块数满足
J0≤3L/α.(Block-number)
这些是按质量排列的计数块,与此前分析中的连续深度块不同。
4.1 每块的有限平移邻域
令 Rb+ 为块 b 的最大倒尺度,设
N0=⌈32B⌉,ϵb=h0⌈16νRb+/h0⌉.
格足够细时,ϵb≤17νRb+。对整数 t≥1,定义有限对称集合
Ub(t)={6n⋅ζ+u:n∈Zd, ∣n∣∞≤tN0, u∈h0Z, ∣u∣≤tϵb}.(Neighborhood)
它含零,并且
Ub(t)+Ub(t′)⊆Ub(t+t′).
4.2 从未覆盖出现构造图
固定一个核心位置 i 和一个块。只要其尚未覆盖标签涉及的出现质量超过 κM2,任选另两个核心位置 j,k。
将这些出现投影为 (i,j) 标签的简单二部图,每对标签只留一个本块尺度证书。每对至多出现 L 次,故边数大于
(κ/L)M2.
以第三位置的 k-标签给边着色。着色是正常的:若两条边在同一端点处有同一颜色,就共享两个核心标签,因而必须是同一个完整元组与同一条边。
令 η=κ/L。第 3 节给出
∣B0∣≥cηM
及式 (Four-paths)。
4.3 四条环带式消去中间标签
四步路径的左侧依次为 a,a1,a′,右侧为 b,b′,颜色为 c1,c2,c3,c4。将四个三位置环带式交替相加减,中间的 a1,b,b′ 消掉。除以 αi,得到
a−a′∈q(c1,c2,c3,c4)+Ub(1),(Color-difference)
其中 q 只依赖四色组。
具体地,颜色项为
−αiαk(c1−c2+c3−c4).
平移项系数 36/αi 是六的整数倍,四个平移相加后在 6ζ 格中的指标至多为 24B≤N0。 标量误差至多为 4νRb+,被 ϵb 容纳。
4.4 差集的最大分离子集
在 B0−B0 中取一个极大集合,使两个不同元素的差不属于 Ub(2)。为每个选中差值选一对端点。每对端点有至少 cη5M3 个四色组。
两个选中差值不能共享同一四色组,否则由式 (Color-difference),它们的差属于
Ub(1)−Ub(1)⊆Ub(2),
矛盾。全部四色组至多有 M4 个,因此选中差值数至多为
Cη−5M.
极大性说明这些差值为中心的 Ub(2) 平移覆盖整个 B0−B0。
删去这一批 B0 标签,重复上述步骤。每次删去至少 cηM 个标签,总次数至多为 Cη−1。因此每个核心位置在每块中,除质量至多 κM2 的未覆盖出现外,其标签被至多
K1=C(L/κ)6(Cover-number)
个集合 B 覆盖;每个 B−B 又被至多 K1M 个 Ub(2) 平移覆盖。
5. 排除缺少三个未来位置的出现
先删去任一核心位置在本块没有被覆盖的出现,总损失至多为
4J0κM2.
对剩余出现,若一个核心标签还属于某个更晚计数块的同位置覆盖集合,称该位置为未来位置。否则称为非未来位置。
固定一个位置,不同计数块中的非未来允许标签集互不相交:若某标签属于后块的覆盖集合,它在前块就属于未来位置。记每块非未来标签数为 mib,则
b∑mib≤M.
若存在侧位置 l,它一律视为非未来,定义
mlb=s∈b∑ws,b∑mlb≤M.
不足三个未来位置的出现至少有两个非未来位置,固定规则给它分配一对 i,j。在块 b,该类质量至多为
min(αM2,Lmibmjb).
若都是核心,这是标签对及尺度重数;若是一核心一侧,这是侧位置的关联数界,额外 L≥1 无妨。
利用 min(x,y)≤xy 和 Cauchy–Schwarz,
b∑min(αM2,Lmibmjb)≤LαMb∑mibmjb≤LαM2.(Nonfuture)
至多六种配对只增加绝对常数。
6. 固定三个未来覆盖集合并分成四段
剩余每个出现至少有三个未来核心位置。用固定规则选一个三元位置组,并给每个标签选一个后块覆盖集合。全部组合数至多为
4J0(J0K1)3=4J04K13.(Configurations)
固定一个组合,其质量为 ρM2>0。它包含当前计数块、三个核心位置及三个严格后块的覆盖集合 B1,B2,B3。下标 1,2,3 仅给这三个位置编号,原系数 αi 不变。
令
Γ=Cgap(d+1)2ν/μ.
若 ρ≤Cδℓ,已经有后面需要的小量界。以下设 ρ>Cδℓ,其中绝对常数充分大。
按倒尺度递减把这个组合的质量分成四个四分位段,并删去穿过三个分界的尺度格。每格质量至多为 δM2,所以四段各至少留下
的质量,并至少包含 ρ/(8δ) 个被占用的二进尺度。令 R# 为第二段最大的倒尺度。
6.1 第一段给出分离锚点
每个固定核心标签总共关联至多 LM 次出现。第一段因而在每个 Bi 中提供锚点集合 Bi0,满足
∣Bi0∣≥cρM/L.(Anchors)
锚点都有倒尺度至少为 R# 的出现证书,因此不同锚点按式 (Separated) 在允许平移下相隔超过 ΣR#。
6.2 最后一段给出很多实际三元组
完整三元组至多出现 L 次,因此最后一段可取不同实际三元组集合 F,每个选一个尺度证书,且
∣F∣≥cρM2/L.(Last-triples)
6.3 第二、三段留下尺度间隔
第三段有至少 ρ/(8δ) 个不同二进尺度。由于 ρ>Cδℓ,它保证任一第二段倒尺度比任一最后一段倒尺度至少大 Γ 倍。严格后块的倒尺度更小,同样满足这一间隔。
在第二段贪心保留相邻倒尺度比至少为 Γ 的尺度。一次选择至多去掉 1+⌈log2Γ⌉≤Cℓ 个尺度,因而保留数
q≥cρ/(δℓ).(Translators)
每个所选尺度 Rv 取一个实际三元组 tv。后面考察带指标的 q∣F∣ 个输出 tv+f,f∈F。
7. 只寻找一次小增长,避免维数指数成本
令 Ui,ϵi 为未来覆盖集合 Bi 所属计数块的邻域及宽度。
将每个整数系数区间和标量区间分段,可用至多
(2t+1)d+1
个 Ui(1) 平移覆盖 Ui(t)。因此存在一个奇数
1≤Hi≤100(d+1)2
使
∣Ui(Hi+2)∣≤2∣Ui(Hi)∣.(Small-growth)
否则每隔两个整数基数都翻倍,到 t≍(d+1)2 时,指数增长超过上述 t 的 d+1 次幂上界。
这里的维数指数只用于保证存在一个小增长位置;后面的估计使用固定因子二,不把 (2t+1)d+1 加入最终常数。
7.1 锚点邻域互不相交
集合
a+Ui(Hi),a∈Bi0
两两不交。若相交,两个锚点的差属于 Ui(2Hi),其平移指标至多为 C(d+1)2B,标量宽度至多为 C(d+1)2νR#,与式 (Reserves) 和锚点分离矛盾。
令
Zi=Bi0+Ui(Hi).
于是 ∣Zi∣=∣Bi0∣∣Ui(Hi)∣。由 Bi−Bi 的覆盖,
∣Zi−Bi∣≤K1M∣Ui(Hi+2)∣≤2K1M∣Ui(Hi)∣≤C(K1L/ρ)∣Zi∣.(Small-expansion)
8. 最小增长子集与二重、三重和集的覆盖
选非空 Xi⊆Zi,使
ri=∣Xi∣∣Xi−Bi∣
在所有非空子集中最小。由式 (Small-expansion),
ri≤CK1L/ρ.
8.1 迭代不等式的完整证明
暂写 X=Xi,B=Bi,r=ri。给定有限平移集 C0={c1,…,cq},令
Xj={x∈X:x+cj∈/∪v<j(X+cv)}.
则
∣X+C0∣=j∑∣Xj∣.
每个 (X∖Xj)−B+cj 中的点已经属于较早的 (X−B)+cv。因此第 j 步新增点数至多为
∣X−B∣−∣(X∖Xj)−B∣.
由 X 的最小增长性质,非空 X∖Xj 满足
∣(X∖Xj)−B∣≥r∣X∖Xj∣.
空集情况也成立。故新增点数至多为 r∣Xj∣,相加得到
∣X+C0−B∣≤r∣X+C0∣.
依次取 C0=−(m−1)B,归纳可得
∣Xi−mBi∣≤rim∣Xi∣,m≥1.(Iterated-growth)
8.2 和集中的分离集
Zi 由至多 M 个锚点邻域组成,所以某个邻域内的部分
Yi⊆Xi
满足 ∣Yi∣≥∣Xi∣/M,且
Yi−Yi⊆Ui(2Hi).
若 Pi⊆mBi 的任意两个不同元素之差不属于 Ui(2Hi),则 Yi−p、p∈Pi 两两不交,并包含于 Xi−mBi。由式 (Iterated-growth),
∣Pi∣M∣Xi∣≤rim∣Xi∣,∣Pi∣≤rimM.(Sumset-packing)
取极大分离集,就给出 mBi 的同样数目邻域平移覆盖。这里只需要 m=2,3。
9. 用锚点把第三个标签数因子消掉
置
r0=CK1L/ρ≥imaxri.
考虑 2B1×2B2×2B3 中满足
i=1∑3αixi+36n⋅ζ≤2νR#对某个 ∣n∣∞≤2B(Slab)
的输出。
前两坐标各可由至多 r02M 个 Ui(2Hi) 平移覆盖。固定其中一对覆盖盒,由式 (Slab) 解出第三坐标,它必须属于 2B3 与下列集合的交:
c+{n⋅ζ:∣n∣∞≤C(d+1)2B}+[−C(d+1)2νR#,C(d+1)2νR#].(Third-location)
除以 α3 不产生非整数平移指标:邻域的平移系数是六,环带平移系数是三十六,二者都可被 1,2,3 整除。
在这个局部第三坐标集合中取极大分离集 P,分离邻域为 U3(2H3)。集合
B30+P⊆3B3
仍是分离集。相同锚点时由 P 的定义保证;不同锚点若发生碰撞,由式 (Third-location) 会得到锚点差在允许平移后仅为 O((d+1)2νR#),与锚点分离矛盾。
因此式 (Sumset-packing) 对 m=3 给出
∣B30∣∣P∣≤r03M,∣P∣≤Cr03L/ρ.
这里利用了全部分离锚点,消去了第三个 M。
于是整个薄层可由至多
C(r02M)2r03L/ρ≤CK17(L/ρ)8M2(Slab-cover)
个 ∏iUi(2Hi) 的平移覆盖。
10. 每个覆盖盒至多容纳一个带指标输出
所有 tv+f 都满足式 (Slab):将第二段和最后一段的环带式相加即可。还需证明这些带指标输出在覆盖尺度上彼此分离。
10.1 同一平移中的两个不同三元组
若 f,f′∈F 不同,至少有一个坐标标签不同。它们最后一段的出现证书都早于全部未来块,即倒尺度都更大。因此式 (Separated) 的间隔大于对应 Ui(4Hi) 的平移与标量宽度。
同一覆盖盒内两点的坐标差必须在 Ui(4Hi) 中,故 tv+f 和 tv+f′ 不能在同一盒中。
10.2 不同平移之间的两个输出
考虑 tv+f 与 tv′+f′,设较大的第二段倒尺度为 Rbig。该三元组的环带剩余量绝对值在
[μRbig,νRbig]
中。另一第二段和两个最后一段的剩余量,总绝对值至多为 μRbig/10,这由 Γ 间隔保证。
因此输出差的线性形式加一个 O(B) 指标平移后,绝对值处于
[9μRbig/10,2νRbig].
若两输出在同一覆盖盒中,其坐标差属于 Ui(4Hi)。盒宽造成的额外标量误差至多为
C(d+1)2νimaxRfuture,i+≤μRbig/10.
所有平移指标合并后仍至多为 C(d+1)2B≤Q。这将产生一个纯平移,其绝对值处于
[4μRbig/5,3νRbig],
落在式 (Grid-gap) 禁止的较窄区间中,矛盾。
所以覆盖盒与带指标输出至多一一匹配,既排除了同一平移内部的重合,也排除了不同平移产生同一输出。
11. 比较输出数与覆盖数
由式 (Translators) 与式 (Last-triples),
q∣F∣≥cδℓLρ2M2.
与式 (Slab-cover) 比较并消去 M2,得到
cδℓLρ2≤CK17(L/ρ)8,ρ10≤CδℓK17L9.
由于 ℓ,K1,L≥1,可以稍放宽为
ρ≤CℓK1Lδ1/10.(Combination-mass)
先前省去的 ρ≤Cδℓ 情形也满足此式。
12. 最后选择两个辅助小参数
组合数由式 (Configurations) 控制。将组合质量、未覆盖质量以及式 (Nonfuture) 相加,得到
M−2s:Ns≤δM2∑Ns≤C(J0κ+Lα+ℓLJ04K14δ1/10)≤C(αLκ+Lα+ℓL29α−4κ−24δ1/10).(Before-choice)
最后一项的 L29 来自
L⋅L4⋅L24,
分别对应组合质量、四个计数块选择与四份差集覆盖成本。
当 δ 足够小时,取
α=δ1/1040,κ=α2.
此时 δ≤α/2。三个 δ 指数分别为
10401,20801,101−10404−104048=201.
因 0<δ≤1,最小指数 1/2080 给出统一上界,且 ℓ,L≥1,式 (Before-choice) 就成为式 (Sparse-count)。
对其余 δ,直接使用总质量 LM2,增大一个绝对常数便得到同一结果。舍入保持标签与元组的离散索引,也保持每个 Ns。工作参数的 ν/μ 为原比值的四倍,因此
ℓwork≤ℓold+2≤3ℓold.
于是网格估计给回原命题的同一 ℓ 因子,只有绝对常数改变。所有估计不依赖 h0,并且这里只需对给定的有限数据取一次充分细的格,无需任何无限尺度极限。
13. 这一收益怎样用于 D
令
c′=1/2080,p0=1−c′/2.
把尺度按 Ns 相对 M2 的二进大小分组,式 (Sparse-count) 中的 δc′ 抵消 p0<1 对小计数的放大,得到
s∑Nsp0≤C(明确参数成本)M2p0.
随后 D 的证明把它与一次幂配对计数插值,再使用跨组角色数界求振幅和。这一有限引理本身不证明标量核式、角色数界或纯平移间隙;那些适用前提仍须由各自章节提供。
本有限证明已完成单独审读。核对范围为上述有限组合命题及其与 D §6.6 引用的对应,不包括 H 的其他解析与几何证明,也不包括 A/B 使用的 R 多重混合命题。