参考类之后：不交性反例与容量二证明稿¶

日期：2026-10-12。接续十轮研究。

后续审计更新： 核心分组推导成立，第二轴间距已改写为只涉及实际有限轴段的证明，因而不再需要无限物理轴延长和高幂限制。独立的一般三次方证明进一步把固定标签费用降为四份交域预算。后续已完成独立完整收费复核与中英题解同步，详见新证明第 9 节。下文保留原始证明稿；其中条件式结论、五份预算和“待审计”文字均属于历史状态。

原始证明稿的状态。 本文的反例已经从完整历史独立复核，方向 A 的连通资源不交猜想被否定。第 3—5 节给出一个可能闭合一般复杂度缺口的完整推导稿：改用一个标签长度分组，而非要求整个资源并不交。推导依赖既有的物理周期轴延长及第二轴分离引理；当时计划专门审计这些依赖、量词及常数。在该审计完成前，主题解暂保留原已确认上界，不把有限程序检查当作一般证明。

1. 左右相反的早横枝给出真实反例¶

取标签和三个查询高度、早横枝末端为

\[ h=(0,6),\qquad (r_1,r_2,r_3)=(10,23,40),\qquad (c_1,c_2,c_3)=(4,-4,2). \]

查询从原点沿第零列依次下降到三个高度。在每层走到早端，再原路返回主干。访问完第三层早横枝后，逆序回到各层，分别向右走到晚端，再返回主干：

\[ e_i=(r_i,c_i),\qquad f_i=e_i+h. \]

令候选源及宿主道路恰为

\[ a_i=(-r_i,0),\qquad F=\bigcup_{i=1}^{3}\left((a_i+P_{t(f_i)})\cup(a_i+h+P_{t(e_i)})\right). \]

这是完整前缀的并，不是仅放入六个指定端点。它共有 171 个道路点，是一棵诱导树；查询有 65 个不同位置。平移装入边长 71 的棋盘后，实现该发现顺序需要 116 步，原程序与两个独立答案算法均给出 1418 次候选检查。正式输入见反例输入。

道路为什么无环，星心为什么真实¶

道路仅有两根竖干：第零列从行负四十到三十，第六列从行负四十到零。零行的水平段从列负四到十，连接两根竖干。其余横枝所在行分别为负三十、负十七、负十三、十三、十七、三十；它们互相不邻接。

负行上的左右两组横枝之间至少空一个格点；正行处第六列竖干已经结束。因此除了零行的唯一连接外，所有横枝都是挂在一根竖干上的路径，不会产生第二条连接。

查询第一步向下。第一次成功筛选后，候选只能在第零或第六列，因为只有这两列有竖边。固定晚源在第零列、目标和查询行后，更早成功点的列只能是晚端列，或晚端列减六。前者就是尚未访问的晚端自己，后者唯一确定上述早端；构造又显式保留了它的完整成功前缀。因此指定配对确实使用最早星心。

删除参考类仍然自平移相交¶

最大早下标为 50，严格切口截止为 51。参考标记来自第三层，早晚下标为 50 和 56。删除该类后，上层源的最大资源在宿主零行覆盖右区间，第二层源的最大资源覆盖左区间：

\[ S_{a_1,e_1}\cap\{r=0\}=\{(0,c):0\le c\le4\},\qquad S_{a_2,e_2}\cap\{r=0\}=\{(0,c):-4\le c\le0\}. \]

两份资源共用竖干及原点，其并是连通的。该分量沿宿主轴的投影区间为

\[ [-4,4],\qquad \operatorname{diam}\pi_L(U)=8>6=\ell. \]

所以

\[ U\cap(U+h)\supseteq\{(0,2),(0,3),(0,4)\}. \]

直观看，单份区间分别是“从零向左四步”和“从零向右四步”；每份都比标签短，连接后却跨过了整个标签长度。十轮研究的跨度等价引理仍然正确，被否定的是期望它满足的严格短跨度界。

这一分量的六笔剩余标记早端仍互异，因此仍有完整资源单位分配。它不是算法复杂度反例，也没有否定“删除参考类后有常数容量”。

2. 四个长轴类的付款不能修复该不交命题¶

使用七层，参数取

\[ r_i=3\cdot2^{i-1}\ (1\le i\le7),\qquad h=(0,8),\qquad c_i=6(-1)^{i+1}. \]

早访问顺序仍由上到下，晚访问顺序由下到上。负向早臂的晚访问延长到第八列；正向早臂延长到第十四列。每个源匹配自己的完整晚前缀，其平移源匹配自己的最大早前缀。

所有非零层差互异且为三的倍数，所以不同层的横枝不会新增邻接。与小例相同，两根竖干只在零行连接一次，宿主仍为诱导树。脚本从实际标记筛出七个长早轴类，每类恰有五笔标记。付款相同时先选较晚类，支付四类后再在余项重选参考，仍留下前两层：十笔标记、两个源，连通轴区间从负六到六，大于标签长度八。

这已经穿过“四个长轴类付款再删除参考类”的筛选。不过每源五笔仍小于九点的点块容量，最终超额为零。不能把它说成第 38 节最终超额的反例。

3. 替代不交性的关键：同早端副本间距大于标签轴长¶

以下给出待审计的证明稿。固定一个标签交域分量，以及其高幂严格标记子族。使用标签证明第 23、25—30 节的记号：宿主平移为自由群左乘，轴、最短周期与标签轴长为

\[ g,\qquad L,\qquad p,\qquad \ell=qp,\qquad q\ge4,\qquad \delta=h/q. \]

每笔标记的查询平移词及查询轴为

\[ g_e=w_f w_e^{-1}=a^{-1}ga,\qquad I_e=a^{-1}L. \]

在这个分量的所选子族内，选早下标最大的标记作为参考，其轴记为

\[ J=I_{e_*}. \]

删除参考轴类。不同查询轴对应不同查询交集分量，真实时间反序保证每个剩余源完整匹配参考晚前缀。该前缀含有一段参考轴路径

\[ A\subseteq J,\qquad |E(A)|\ge\ell. \]

现在取具有同一个查询早端的两个不同剩余源。它们的晚端也相同，故查询轴相同；同时

\[ aI_e=bI_e=L,\qquad I_e\ne J, \qquad aA\subseteq F,\quad bA\subseteq F. \]

两份轴段在同一道路树中，因为两个源都属于当前宿主交域分量。按第 30 节“第二条轴”引理，它们不相交。两源之比保持宿主轴，其轴向位移为最短周期的非零整数倍；另一条参考轴有相同周期与水平位移。因此

\[ \boxed{|\Delta_{\rm axis}(a,b)|>|E(A)|\ge\ell.} \]

这里必须固定相同早端的原查询轴像，再把参考轴用作第二条轴；不是固定参考轴像。这与第 37 节的使用方向相反。

展开第二轴论证，避免隐藏前提¶

相对左乘保持第一条轴，网格位移为某个非零整数倍的共同水平周期。参考轴的两份无限物理像因而重合。若两段实际道路相交，在该宿主点沿周期方向唯一续接，会迫使两条抽象参考轴像相同。

同一个非恒等自由群左乘于是同时保持两条不同的轴；但自由群的自由树作用中，非恒等元只有一条平移轴。这是不可能的。因此两个有限轴段只能沿共同物理轴错开，且偏移量严格大于该段边长。

这个步骤使用已证明的无限物理周期轴性质。仅在抽象自由树里说“共轭所以间距大”是不够的；两份完整参考晚前缀、相同物理周期及同一道路树都不可省略。

4. 按一个标签长度分组，得到容量二¶

每笔标记仍使用自己的完整早资源，记投影左端点为

\[ S_{a,e}=a+P_{t(e)},\qquad \lambda_{a,e}=\min\pi_L(S_{a,e}). \]

严格切口保证单份资源与其标签平移不交，因而

\[ \operatorname{diam}\pi_L(S_{a,e})\le\ell-1. \]

同早端两份资源互为保持宿主轴的左乘像，投影左端点之差就是上一节的轴位移，所以

\[ e=e',\quad a\ne b\quad\Longrightarrow\quad |\lambda_{a,e}-\lambda_{b,e}|>\ell. \]

将资源按以下半开区间分组：

\[ \lambda_{a,e}\in[j\ell,(j+1)\ell),\qquad j\in\mathbb Z. \]

每组早端互异。 因此第 13 节的完整前缀 Hall 论证给每组单位分配。也可以直接按早下标递增贪心分配：第几笔的完整前缀至少包含此前所有不同早端及根，故总能找到尚未使用的资源点。

一个道路点至多参与两个组。 若它的轴投影坐标为

\[ x=\pi_L(z), \]

所有含有它的资源左端点必在

\[ \lambda_{a,e}\in[x-\ell+1,x]. \]

该整数区间至多遇到两个长度为标签轴长的分组。叠加各组单位分配，便得到

\[ \boxed{C_{\rm nonref}\le2.} \]

这不限制整个连通并的跨度，也不按不同参考轴像重复领取整幅道路的预算。左、右早横枝反例可以跨越分组边界，却不会使一个道路点参与无界多个组。

5. 若上述依赖审计通过，如何合并成一般上界¶

参考轴类本身有单位容量：同一类、同一宿主分量内的源之差沿公共周期方向，故源同行；若两笔标记的资源早端像相同，则其晚目标也相同，查询早端也同行。真实最早星心唯一，因而这两笔标记相同。将该类标记分配到资源早端像即可。

于是高幂分量的严格部分容量至多三。低幂分量沿用第 27 节的既有界：

\[ q\le3\quad\Longrightarrow\quad C\le q+1\le4. \]

在每个宿主交域分量内分别选参考，再对不交的分量求和；不需要跨共轭类型重复付费。共同切口已付部分另占一次交域预算，故拟得到

\[ \widetilde M_h\le5|G_h|. \]

逐行星心至多为棋盘边长乘道路数，每个候选最多失败一次，再使用全标签同行有序点对恒等式，即

\[ \begin{aligned} W&\le(n+1)N+\sum_h\widetilde M_h\\ &\le(n+1)N+5(n-1)N=(6n-4)N. \end{aligned} \]

因此本证明稿的结论是

\[ T=O(n^2+m+nN)\subseteq O(n^3+m). \]

这里没有使用方向 A 的错误不交猜想，也不需要先支付四个长轴类、每源点块或分别处理直轴超额。待审计的是这条完整依赖链，不能仅因为最后的代数求和正确就跳过第 3 节。

6. 本次已完成的核验与后续审计¶

验证脚本与结果记录了 16 个输入、72 个参考场景，其中 10 个弯曲轴场景；共检查 5667 对同早端相邻副本间距，并在 10988 笔带场景重数的标记上实际构造了分组分配。最大逐点使用量为二。

小反例的全部星心还从完整前缀定义独立枚举，全部答案与位集算法、逐前缀枚举及原标准程序一致。七层例由实际标记重新执行长跨度筛选、四类付款和参考类重选。上述计数含重复场景，不能视为独立随机样本。

下一次优先从头审计第 3 节：同早端两源是否确实共用原轴像，参考晚轴段是否完整匹配，物理周期位移与抽象轴长度是否对应，分量级选择是否保留反序；然后复查容量分组与全标签常数。若发现缺口，应直接记录并撤回相应推导，不能用这些有限实验替代它。

python topics/simulation/grid-forest-matching/research/verify_reference_capacity.py --output topics/simulation/grid-forest-matching/research/reference-capacity-results.json --program build/grid-forest-matching.exe