第二十一章四十二个角和一次超时

有限极值归约说，只要列出全部的角，算出每个角的最好值，就能得到图的耦合常数。瀚林对两个、三个、四个顶点，完整地列出了全部的角。

两个程序，一份清单

列角用了两个独立写的程序：一个检查所有可能用到的集合组合，看它们是否互不多余（也就是第十七章说的，没有“此消彼长”的余地）、方程是否有正的解；另一个从另一个方向枚举，再把重复得到的角去掉。

两个程序都跑完，瀚林在群里贴了一行：“42 个。两个程序都是 42 个。”

韵吉回：“只比了个数？”

过了一会儿，瀚林又贴了一行：“逐项对上了，连每个权重的分数。”

只比个数确实不够：两个程序可能碰巧数出同样多，却列错了不同的东西。逐项对上，才能排除这种情况。

四个顶点重新编号，有些角会互相变成对方。按这样的关系，$42$ 个角可以分成 $10$ 组。完全图怎样重新编号都不变，所以瀚林又写了一个每组只算一个代表的版本，和先前逐个算出的 $42$ 个结果一一对过，值都一样。

最后一行

$42$ 个角放到完全图 $K_4$ 上，每个角都有一份原始—对偶证书。这些证书全部用一个另外写的检查程序验证过。它直接从输入重新建立每一个条件，一共检查了 $6717$ 种完整签上的对偶不等式，以及两边数值的精确相等。

都查过了，瀚林才把四十二行按最好值从小到大排了一遍：一个 $0$，十四个 $1$，四个 $\frac{5}{4}$，二十二个 $\frac{4}{3}$。最后一行单独一个 $\frac{3}{2}$。

祺乐问：“就一个？”

“就一个。”

最大的正好是 $\frac{3}{2}$，和第十九章用行列式得到的结论一致。那个 $0$ 来自“所有顶点的表都相同”的角，这和“图常数至少是 $1$”的约定并不冲突。

最后一行的输入是四个集合，每个集合三个顶点，权重都是 $\frac{1}{3}$：$\{2,3,4\}$、$\{1,3,4\}$、$\{1,2,4\}$、$\{1,2,3\}$。每个顶点恰好在其中三个集合里，$3\times \frac{1}{3}=1$。把每个集合当成一种回答来看：$\{2,3,4\}$ 这种回答，顶点 $1$ 一点也没有，另外三个顶点各有 $\frac{1}{3}$。四种回答，四个顶点各缺一种，其余三种各 $\frac{1}{3}$。这就是第八章那四张表，只是去掉了名字。

瀚林又打开这一行的证书。做得到的那一半是十二种签，每种 $\frac{1}{12}$：每张签上三个顶点写同一个回答，第四个顶点正好不许写它，就写了别的。这正是第八章挑特殊顶点的抽法，和附录一列出的十二种签是同一种，只是回答的编号换了一下。六条边两端不同的机会都是 $\frac{1}{2}$，距离都是 $\frac{1}{3}$。做不到更好的那一半，给六条边配的权重里有两条是 $0$，另外四条一样大。这四条边连起来是一个正方形，两条权重为 $0$ 的边正好是它的对角线。第十九章证明 $K_4$ 至少是 $\frac{3}{2}$ 时，用的也是它里面的一个正方形。

第二十章那三份故意做坏的证书，都是拿这一行的证书改出来的，也都是被这个检查程序拒绝的。

十二个检验例子

列角是为了 $K_4$。另一组计算，检验的是圈和仙人掌图上的构造方法。我们准备了十二组人为设定的输入：八组是开发构造时边做边用的，另外四组是构造方法定下来以后才挑的，专门看方法在没见过的输入上表现如何。里面有一棵三个顶点的树、只有两种回答的正方形、三角形到五边形上的逐一缺失、带共同回答的圈、含零距离边的正方形、所有表都相同的情况、共用一个割点的两个三角形，等等。

对每一组输入，程序构造出的联合分布都用精确分数检查了：概率不为负、总和为 $1$、各顶点的边际分布、各边不同的机会、零距离边，以及图常数的上界。另外还用一个独立写的线性规划程序算了每组输入的最好值，又把回答的编号整个倒过来再算一遍。程序如果在哪里不小心依赖了回答排的先后，倒过来以后结果就可能变；两遍结果一致。

检验跑完以后，瀚林把输入文件一个个打开核对，发现最初挑的第四个检验例子，和开发用的那个三角形上的逐一缺失，边一样，三行权重也一样。瀚林把两个文件并排贴进群里，只写了一句：“这两个是同一个。”

重复的例子不能算一次新的检验。我们把它排除，另外选了一个带共同回答的三角形代替，构造方法本身没有改。新选的这个例子，先拿去和原来的那些输入逐一比过，连顶点和回答换了编号以后的样子也比了，确认不是哪个旧例子换了个样子。旧的输入、替代的输入和两轮结果都保留在随附材料里，“到底用了哪些例子”可以追查。

从这些比较里也能看到构造的不足。有一个检验例子是距离不均匀的正方形，构造给出的倍数是 $\frac{28214}{25629}$，约等于 $1.10$；而线性规划给出的数值结果是 $1$。构造只保证不超过统一的上界，对具体的某一组表不一定是最好的。

这些例子里的概率，都是我们为了检验数学而设定的分数，不来自真实的聊天产品。

一次超时

四十二份证书都通过以后，瀚林又试了五个顶点的完全图。顶点只多一个，非空的集合就从 $15$ 个变成 $31$ 个，要试的集合组合多了很多；一个角最多用五种回答，要代进去的完整签，也从最多 $4^4=256$ 种变成最多 $5^5=3125$ 种。程序在我们当时的设置下超时，没有算完。

瀚林在群里贴了最后一行输出，下面跟了一句：“这个写不写进论文？”

祺乐回：“写‘差一点就算完了’？”

韵吉回：“差多少？”

“不知道。”

瀚林也问了 AI。论文最后是这样写的：

• 完整的枚举和证书验证，只做到四个顶点；
• 表格里的五边形，只是在一组指定的输入上检验构造，算不上五个顶点的完整枚举；
• 五个顶点的完全图，探索没有完成，不作为结论的证据，也不放进随附的已验证结果。