去掉对数：一般证明与研究记录¶
一般三次方上界已经证明。建议先读独立的一般证明；较早的乘积界证明解释原有对数来源，本文保留走到新证明之前的子类、归约和失败路线。
1. 当前准确结论¶
对道路格数为 \(N\le n^2\) 的诱导四邻接森林，候选列表算法已证明
当 \(m\ge n-1\) 时，水平道路条带给出匹配下界，因而
一般的对数缺口已闭合。 新证明使用全部历史的逐行最早星心、共同切口、分量内参考类，以及按一个标签轴长分组的容量二分配，得到
关键改进是固定同早端的原查询轴像，把参考晚轴当作第二条轴。两份实际有限轴段已足以迫使副本间距超过标签轴长，不需要高幂、直轴或无限物理延长。方向 A 的连通并不交命题虽然被反例否定，常数容量仍然成立。参见反例与初稿及完整一般证明。
下文的“容量”指把标记分配给允许使用的道路格并限制每格接收次数；“支付”指用已有总量上界的计数覆盖标记。这些是证明工具，不是程序新增步骤。第 2—5 节保留历史推导及原方向；它们的局部限制和反例仍有意义，但不再表示算法的一般复杂度尚未解决。
本文把结果分成三类：
- 已证： 有一般推导，写明适用条件。
- 已否定： 有满足相关条件的具体反例或参数族。
- 未证： 只是充分条件、猜想或可继续检验的思路。
有限搜索没有找到反例，不等于已证；辅助计数有反例，也不等于算法有反例。
2. 在一般证明之前得到的输入子类¶
下表各项都是独立的充分条件，不要求同时满足。查询树始终指最后一次仍有候选存活的完整位移树；最后清空候选的失败新点不放入这棵树。
| 条件 | 已证扫描界或结论 | 证明思路与入口 |
|---|---|---|
| 查询树或每个道路分量的叶子数有统一常数上界 | $W\le N+3(n-1)\sum_C | C |
| 道路分量都是路径；或有效查询是一条可从两端交错增长的路径 | \(W\le(6n-5)N\) | 上一行的直接推论。旧方向字符串论证保留在路径证明。 |
| 每个道路分量到某条主路径的树距离至多为固定常数 \(r\) | \(W\le(2r^2+2r+1)(6n-5)N\) | 将枝杈命中投影到主路径，控制短连接的可能性。根叶链证明后半部分 |
| 每个道路分量只有 \(O(n)\) 个分叉点，枝长任意 | $W\le(6n-5)N+\sum_C | C |
| 先完成查询直径及查询根到它的连接，再增长删除直径后剩余的路径挂枝 | \(W\le(10n-7)N\) | 已完成子模板给挂枝的两侧提供平衡约束。访问顺序是必要前提，尚不能删去。分枝证明 |
| 查询的每个非空水平平移交集都连通 | \(W\le2nN\) | 对固定水平标签，同一查询势能类型的标记注入道路交集。包含任意根、任意访问顺序的直主干直齿梳形查询。标签证明第 7 节 |
| 每对相邻行的竖边列位置，每个非零差值的重数都至多为固定常数 \(b\) | \(W\le[(b+2)n-b]N\) | 用局部竖边限制重复早端，再分配完整早前缀。这允许稠密道路和超过线性数量的分叉。标签证明第 15 节 |
| 相关标签平移词的幂次数有统一常数上界 | \(W=O(nN)\) | 按树轴最短周期和资源投影分组；幂次数控制资源重复使用。无非平凡幂时可取 \(W\le(4n-2)N\)。标签证明第 20、27 节 |
其中 \(L_T\) 是有根查询叶数，\(\ell_C\) 是道路分量的无根叶数，\(B_C\) 是道路分叉点数；单点树的叶数取一。两棵树的叶数可以同时很大，所以第一行不解决一般情形。
还有一个直观的限定族：同一张图内，不同高度梳层的总成本可按总齿高共同支付。关键是按一个候选能存活多久收费，而不是在每个前缀上重新领取整幅道路的预算。它解释了为什么“混合很多高度”未必产生对数下界，完整计算见混合层高证明。
关于单棵梳形树为何在线性次筛选后仍有平方个候选，以及按所述顺序访问后任意继续查询为何仍不超过三次方，见梳形树问答与图示。该文补充固定常数倍模板的精确计数，并区分单前缀候选数与全部筛选费用。
3. 保留完整前缀的标签路线：历史归约及其闭合¶
3.1 从成功检查到一对早、晚查询点¶
每个候选至多失败一次，所以全部失败检查至多为道路数。对成功检查，固定道路目标格和查询行，把最早成功点记作早端 \(e\)，同组后来的成功点记作晚端 \(f\)。初始零位移不参与选星心。
定义
两次成功给出的条件是
定义标签交集
由于早前缀包含在晚前缀里，整份早资源都在交集中：
这比“根到早端的路径存在”更强。过去多次失败的计费，恰恰丢掉了完整前缀中的其他分支。
记这种只按行分组的标记数为 \(M_h\)，则
这里 \(k_r\) 是第 \(r\) 行的道路数。原充分目标 \(M_h\le C|G_h|\) 现已由一般证明实现，常数可取四。以下保留取得这一结论之前的逐步归约。
3.2 为什么完整早资源是有用的¶
已证：早端互异的标记子族有单位容量。 对任意标记子集，选早端最晚的一笔。它的完整早前缀已经包含这个子集的所有不同查询早端，因此这一份资源本身就有不少于子集标记数的点。Hall 条件成立。
这里仅要求查询早端互异，源可以不同。反之，同一早端可能对应许多源，不能不加处理地使用此论证。
还有若干已证的局部容量：源共线时可单位分配；全部完整资源位于一条简单路径内时容量至多四；轴投影很短或早端种类很少时也有常数容量。标签证明第 13、17、21、24、27 节给出准确条件。
3.3 共同切口与树轴筛选¶
不同查询交集分量的标记具有真实时间反序：若一个早端更早，其晚端反而更晚。利用最晚早端确定共同切口，可把已完成或两份前缀相交的标记一次支付；留下的两份相关查询子树不相交，所有晚源仍匹配同一个完整前缀。
标签交域上的平移还对应一条树轴。将沿轴的方向词写成最短词的幂，记最短周期长度为 \(p\)、幂次数为 \(q\)，则标签沿轴的长度是
这里是树路径的边长，不应与格点中水平坐标差一概混同。不同“查询轴类”记录查询侧不同的平移轴；“实际参考轴像”还包含它在宿主树中落在哪里的信息。
已有容量规则支付了低幂、路径交域、单点轴交、少早端，以及短轴跨度的部分。对其他分量还可支付四个长早轴类。剩余标记因而必须同时处于高幂、分叉交域、多长轴类的困难部分，每份资源含有至少两个周期的轴跨度。
3.4 参考类与每源点块：最终已证的归约¶
在所选同周期共轭类中，以最晚早端所在类作为参考。参考类的全部标记，包括离轴早端，都可以支付。
每个非参考源都匹配参考晚前缀，以及所有非参考晚端中最早者的完整前缀。两条不同查询轴同时存在，迫使共享同一参考轴像的不同源，沿轴相距超过一个标签长度。因此每源可以领取 \(\ell+1\) 个互不冲突的轴点。
同一参考轴像内，完整共同早树的副本也互不相交。 但不同轴像的资源会重叠，不能跨像直接相加资源大小。
最短周期为一时，参考轴像的道路交集互不相交，点块成本可跨标签合并。为了避免依赖历史轮数，记最终未付量为
其中 \(E_{\rm curved}\) 是上述筛选后最短周期大于一的标记数；\(r_{h,a}\) 只统计同一筛选余项内、最短周期为一的非参考源标记。参考类必须在该余项里重新选择。则已有
当时未受控的余项 \(E=O(nN)\) 现已得到。 它只计实际标记的一个子集，一般标签容量界可直接控制它；不必再对弯曲周期和每源超额分别收费。此前仅有轴类数、交域数或每源点块，并不足以推出这一结论。历史归约见标签证明第 29—38 节。
3.5 另一个可用限制：标签平移源的死亡位置¶
每个非参考源匹配参考晚前缀，但其标签平移源在参考早端之前或同一时刻已经失败。否则它的参考早前缀整体落在原交域里，统一的平移关系将迫使它也属于参考轴类。
第一次失败的查询父边，映到宿主后是一条从交域内到交域外的边；未平移的晚源在该边两端仍成功。这保留了完整历史条件，但不同源可能复用同一条边，尚未获得常数重数的费用界。见标签证明第 40 节。
4. 已否定的路线：具体错在哪里¶
下表否定的是相应辅助命题。列出的构造都不能被直接当作一般算法的超三次方反例。
| 已否定的加强 | 反例说明了什么 | 保留的有效部分与入口 |
|---|---|---|
| 任意道路森林都能保持原位置补点成为一棵诱导树 | 线性数量、每棵线性大小的路径可以任意两棵都无法连接；扩大网格也无效 | 否定这一补点归约；这些路径森林本身仍属于三次方上界已证子类。反例、图示与证明 |
| 模板超过线性大小后，候选必降至线性个 | 合法梳族中，模板和候选都可远大于边长，乘积仍达到一般界同阶 | 单前缀乘积界仍正确。多尺度梳形构造 |
| 对全部历史成功位移直接使用静态平行四边形禁形 | 历史成功来自不同完整前缀，其并可含非退化平行四边形 | 主证明必须固定同一完整模板。局部计费反例 |
| 每次成功一定增加包围盒或副本并集 | 两者都可连续不增长，仍有合法成功检查 | 不能逐次向“新占用空间”收费。前缀重叠证明 |
| 一般查询前沿总数是道路数的常数倍 | 同根诱导网格树的前沿数可达 \(\,\Theta(nN)\,\) | 前沿事件存在完整前缀冲突；直接实际匹配量没有同样反例。前沿反例 |
| 只用历史第三长臂容量支付重复收费 | 容量可恒为九，收费随参数无界增长；候选转移也未增加该容量 | 候选死亡切口与短早臂窗口仍有效。分枝证明末节 |
| 每笔标记只用自己的根到早端路径，就有统一常数容量 | 二次方个真实标记可以拥挤在线性大小的路径并里 | 必须允许使用路径外的完整早前缀。标签证明第 9 节 |
| 关联图无环；或资源连通就能分开类型与重复早端 | 关联图可以成环；实际资源连通分量可同时有多类型和重复早端 | 宿主道路无环不能自动传给辅助图。标签证明第 5、8、18 节 |
| 直接相加各势能类或各轴像的资源并 | 复用会导致无界高估；横竖取较小预算也无法普遍修复 | 单类注入、同像内不交仍正确。标签证明第 10、22、39 节 |
| 整个标签交域可按标签无限平移并保持森林 | 不同离轴枝在远副本对齐后可以成环 | 单份严格切口资源满足更强前提，仍可无限延长为森林。标签证明第 34—35 节 |
| 每源点块已支付全部标记，可以删去超额 | 深钩和二维梳状族留下真实超额 | 这些超额仍有显式单位分配，说明规则不够强，并非算法失败。标签证明第 38—39 节 |
| 每条失效出边只需承担常数个剩余源或常数超额 | 现有四类、参考类和点块付款之后，同一条边仍可承载线性多个源及无界超额 | 只排除直接按边常数收费，仍可研究共享边之后的资源分配。十轮研究第 1 节 |
例如，最新的二维嵌套梳族可同时满足
它严格否定道路数级别的粗资源大小预算，但实际扫描仍未超过目标三次界。参数证明保留了森林诱导性、真实最早星心、单位分配和移动数的逐项核对。
5. 原探索方向及最终去向¶
以下保留当时提出的方向。现有一般证明已完成算法的三次方目标；其中更强的辅助命题并不因此自动成立。
当时合并后的安排与现在的结果（2026-10-12）¶
新建议与原有 A—E 并不互斥：跨尺度摊还是宏观目标，候选寿命提供计数方式，完整前缀、参考轴类和失效边提供可能使用的结构。下表列出当时的目标及现在的结果。
| 主线 | 与已有路线的关系 | 当前结果 |
|---|---|---|
| 跨尺度摊还与接近饱和时的结构 | 加强 D，用 F 的寿命计数串联全部历史 | 已用全历史标签收费控制总和，排除无界多个尺度都花满预算；没有使用接近饱和的结构分类 |
| 完整早资源与候选死亡 | A 的不交命题已否定，转向标签长度分组；B、C、E 是可组合的工具，F 统一解释费用 | 已证明容量二；有限第二轴引理统一处理全部幂次，再加共同切口及参考类得到容量四 |
| 直接争取三次方并搜索反例 | 新增 G、H，防止把更强的道路数界当成唯一目标 | 已证明更强的道路数乘边长上界；原三次方下界与之匹配 |
最终采用容量二分组完成了一般证明。 对 A 的验证先后经历初次检查、十轮研究，最终由左右早横枝否定一般不交性。新证明保留“同早端副本间距大于标签轴长”，不要求整个连通资源并不交。
A. 移除参考轴类后的连通资源不交性：已否定¶
固定真实共同切口、一个高幂共轭类和所选标记子族；移除最晚早端所在的参考轴类。取剩余完整早资源并的任一连通分量 \(U\)，连通性包括不同资源之间的单位格邻接。原猜想是
为什么值得检验： 若同一个查询早端在此分量内重复出现，对应两源在自身宿主轴上相距超过一个标签长度，因为两源还必须匹配另一条参考晚轴。连接它们的树路径属于该资源分量，于是会包含两个相差标签的点，与猜想矛盾。早端便互异，可使用单位容量。
现在的结论： 两份合法早资源可分别从共同轴点向左、向右伸展，每份短于标签，连通并却跨过整个标签长度。边长 71、171 个道路点的完整历史反例已独立复核；七层版本还能穿过四类付款和参考重选。它没有重复早端，也没有最终点块超额，故只否定该不交命题。
十轮研究的原顺序嵌套梳列带证明及轴投影等价引理仍成立。替代路线按标签轴长对资源左端点分组，已经得到容量二：组内早端互异，每个道路点至多参与两个组。有限第二轴引理与全部计费见一般证明。
B. 沿失效边支付每源超额¶
非参考源已带有一条离开交域的真实边。可以尝试证明：许多源若通过同一边产生大量超额，完整晚前缀就迫使宿主额外占用道路，或形成不允许的第二条连接。
现在已证明：即使经过现有付款，单条边的源重数和未付超额也可无界增长。直接按边常数收费已被排除；仍可研究共享这条边的源能否联合使用其他道路预算。证明见十轮研究第 1 节。单纯把每源全部早资源大小加起来，也已被二维嵌套梳否定。
C. 跨周期合并弯曲轴的预算：新证明已绕开¶
对共同最短周期，长轴长度有线性预算；对最短周期一，不同实际轴交不重叠。不同增长周期之间如何共享道路空间，仍没有足够的合并界。
已经有“相关交域只有线性多个”和“周期重复次数总和有界”等结论。但需要的是实际标记数；不能把次数预算误写成所有轴长度或所有资源大小之和的预算。
D. 直接证明多尺度不能同时饱和：已由全历史界解决¶
旧一般上界的对数来自不同前缀尺度分别收费。历史高重叠的非平行平移受到几何限制，同方向段的最大重复倍率也已有线性总预算。这说明可以保留已删除候选的历史约束。
仍缺把所有实际成功检查映射到这份预算的方法；仅靠固定参考方向的预算已有反例。见跨前缀重叠证明。
可以先分析静态乘积界接近饱和时，候选是否必须聚集在少数方向、长重复段或共同分枝结构上，再研究查询增长如何破坏这些结构。目标是让每份结构只领取一次预算。静态梳族已能达到乘积界同阶，因此不能只把单个前缀的不等式改紧；必须用同一候选的存活历史连接不同尺度。
E. 从高度记录继续缩小剩余收费：局部问题保留¶
任意查询顺序的若干分叉费用已经支付，剩余可归约为直径或根高度增长时的真实成功量。重复记录有根投影次序、死亡切口和短臂窗口。
尚未控制候选转移的累计重数。记录本身能达到三次方，且可能需要任意多条根叶链；不能改用已否定的一般线性前沿或历史第三长臂容量。
F. 用候选寿命统一成功检查的摊还：计数方式保留¶
令 \(s(a)\) 为初始道路候选 \(a\) 在新位置全量筛选中的成功次数，不计初始零位移与重复访问。候选一旦失败就不再出现，所以严格有
这只是换一个顺序统计同一批检查，尚未改进上界。它允许少数候选存活很久；不能额外假设每个候选的寿命都是线性的。可按寿命分层，也可把长寿命候选的完整匹配前缀、首次死亡边和分枝记录一起保留，尝试证明不同寿命层共享一份总预算。B 的平移源失效边和 E 的转移重数，都是这一框架中的具体问题。
G. 直接争取三次方：更强目标已完成¶
证明 \(W=O(nN)\) 足够，但比原目标更强。当时带对数上界立即给出的推论是
因此，若只追求原目标，稀疏道路情形已无需新论证，可以集中研究超过这个阈值的情形。可尝试同时给道路、障碍格和边界分配预算，允许使用整个网格的面积。这里没有证明新的稠密图结构，也没有声称每次成功必新增面积；后一个说法已有反例。
H. 用真实总费用检验反例：改作证明复核¶
对递归分叉、嵌套重复块、混合周期和不同发现顺序，直接记录 \(W/n^3\)、实际移动数，以及各倍增前缀区间的费用。需要在同一张图、同一条行走上使许多尺度一起积累大费用；分别为每个尺度另造最坏图没有作用。
有限实验用于挑选值得证明的参数族。只有证明比值随参数无界增长，并控制移动项，才能否定目标总时间；单个大比值、资源大小和过大或多尺度候选很多都不够。本次 A 的实验也保存真实费用与移动数，但不是对这一反例方向的穷尽搜索。
6. 怎样判断一个新证明或反例是否真正推进了问题¶
这份核对顺序也适用于审查现有证明或进一步改进常数：
- 先确认计数对象。 是真实候选检查，还是一个可能高估很多的辅助量？
- 保留完整前缀。 候选在某点成功，要求此前全部已访问点都匹配。
- 核对星心最早性。 任意成功配对未必是当前定义中的标记。
- 核对诱导森林。 坐标相邻就自动有边，不能只检查构造者想画出的边。
- 计入真实移动数。 树上回走不增加筛选，却仍计入时间中的移动项。
- 区分证明与实验。 有限搜索、超过正式边长的数学族检查、原程序核验各说明不同的事。
- 逐项检查量词。 同一轴像内不交，不推出不同轴像间不交；固定周期的预算，不允许不加控制地对所有周期重复领取。
研究目录提供独立构造证明、代表性输入、输入指纹和验证脚本。