第二十章怎样证明已经是最好

祺乐问的“$K_4$ 会不会比正方形更大”，答案写在两个地方。一处是韵吉的本子，行列式那一页的最后一行写着 $\frac{2\times 3}{3+1}=\frac{3}{2}$。另一处是瀚林的电脑：一个四十二行的文件，每行是一个角，后面跟着电脑给它算出的最好值。

祺乐凑过去，要看最大的那一行。瀚林把屏幕往自己那边转了转。

“先别看最大的。”

“为什么？”

“这些数是求解器算出来的，都是小数。每一行都得先查过。”

韵吉问：“怎么查？”

给出一种安排，最多只能说明“这个倍数做得到”。可能还有一种我们没想到的安排，做得更好。怎样确认已经到头了？

第八章其实已经做过一次：一边交出“挑特殊顶点”的抽法，证明每条边不同的机会可以是 $\frac{1}{2}$；一边用“每张签至少两条边不同”的计数，证明不可能更低。两边落在同一个数上，最好的值就确定了。

瀚林要做的，是让电脑对很多组表都完成这样的“两边夹”，而且每一步都留下可以检查的凭据。

把每张签的机会都当成未知数

一组表上，所有可能的完整签有多少种？每个顶点有 $s$ 种回答，$n$ 个顶点，就有 $s^n$ 种。比如 $3$ 种回答、$4$ 个顶点，有 $3^4=81$ 种。

给每一种签设一个未知数，表示它出现的机会。这些未知数要满足：

• 都不小于零，加起来等于 $1$；
• 对每个顶点 $v$ 和每种回答 $a$，所有在 $v$ 那一栏写 $a$ 的签，机会加起来等于 $v$ 的表里 $a$ 的机会；
• 对每条边，两栏不同的签的机会加起来，不超过 $c$ 乘以这条边的距离。

在满足这些条件的前提下，让 $c$ 尽量小。

这种问题叫线性规划。“线性”的意思是，未知数只会被已知的数乘一下再加起来，不会互相相乘。解线性规划有成熟的方法，现成的程序叫“求解器”，我们用的是 Python 里 SciPy 软件包带的那一个。它会给出最小的 $c$，以及一张达到它的签表。签表本身就是“做得到”的凭据：任何人都可以把它代回去，逐条核对上面的条件。

对偶：一份“每张签都至少……”的证明

求解器给出最小的 $c$ 时，还会附上一句“这是最优的”。可这句话是求解器自己说的。李老师听我们讲到这里时问：“评委手里没有你们的电脑，凭什么信？”

“做不到更好”也得有一份能自己检查的凭据，它叫对偶证书。“对偶”是配成一对的意思：原来的问题是在所有签表里找最小的 $c$，和它配对的另一个问题，是在所有这类证明里找最大的下限。对偶证书的样子，其实就是第八章那个计数论证的推广。

在第八章，我们找到了一个对每一张允许的签都成立的不等式：“不同的边数至少是 $2$”。然后按签的机会加起来，得到“各边不同的机会之和至少是 $2$”，再推出倍数的下限。

对偶证书做的是同样的事，只是更一般：它给每个条件配一个“权重”，使得对每一张可能的签，某个加权的计数都满足一个不等式。把这些不等式按签的机会加起来，就得到 $c$ 的一个下限。

拿第八章的正方形来说，那份证书的核心就是一句话：“每张允许出现的签上，不同的边至少两条。”四个顶点、四种回答，可能的签一共 $4^4=256$ 种。这份证书相当于给四条边都配了同样大的权重；一般的证书里，不同的条件可以配不同的权重。检查证书，就是把这 $256$ 种签一张张代进去核对，有限个，一定查得完。一般的情形也一样，最多 $s^n$ 种。

如果“做得到”的签表给出的 $c$，和对偶证书给出的下限精确相等，最好的值就被两边夹住了。这样一对凭据，叫原始—对偶证书。有了它，就不需要相信求解器说“这是最优的”，任何人都能自己逐条验证。

用第九章出题游戏的话说，出题人已经把签盒摆好了。安排人交出答案单，算分的人核对一遍，知道这一局的分数做得到；安排人再交一份对偶证书，算分的人拿它把所有可能的签一张张核对完，就知道这一局换谁来安排，分数都不会更低。两份都核对过，这一局的最低分 $\rho$ 就定下来了。

小数点后十几位

麻烦出在求解器给出的数上。求解器用小数计算，小数点后十几位上常常有一点误差。

还是第八章那四张表。四个顶点、四种回答，$256$ 种签，瀚林把它交给求解器。结果最上面一行是最好的倍数：$1.5$。往下是四条边两端不同的机会，两条是 $0.5$，另外两条是 $0.49999999999999994$。

祺乐说：“就是二分之一嘛。”过了一会儿又说：“照这么算，四条边加起来比 $2$ 还少一点。它比我们证的还厉害？”

韵吉说：“不可能。正方形那组表，我们证过，加起来至少是 $2$。”

瀚林没接话，把再往下那几行抄了下来。那是求解器交出的签表，一共九种签，机会都是这样的数：

$$0.08333333333333333,0.16666666666666669,0.08333333333333331$$

瀚林在每个数旁边写上一个分数：$\frac{1}{12}$ 或 $\frac{1}{6}$。

这一回，小数离分数只差一点点，一眼看得出该是哪个分数。可我们要的是证明，差一点点也不行，何况照字面读，屏幕上这几个数和一个已经证明了的结论是矛盾的。浮点计算和严格证明之间怎样衔接，后来写进了论文的致谢，是我们碰到的主要困难之一。

瀚林拿这个问题去问过 AI：求解器的结果在小数点后第十五位上有误差，怎样才能做成证明用的精确证书？我们最后的做法是让电脑先用小数找候选，再用分数做检查。先把求解器给出的每个小数，还原成一个分母不超过一百万的分数；然后用 Python 的精确分数运算，把所有条件重新检查一遍：每个概率不是负数，总和是 $1$，每个顶点的边际分布，每条边的限制，零距离的边，对偶权重的正负号，每一种签上的对偶不等式，最后两边的数值是否精确相等。有一项不成立，这份证书就不接受。

“分母不超过一百万”只是找候选时用的办法，分母小不代表结果就对。

瀚林抄下来的那张签表，换成分数以后是下面这样。顶点的编号和第八章一样：顶点 $1$ 不写甲，顶点 $2$ 不写乙，顶点 $3$ 不写丙，顶点 $4$ 不写丁。

故意做坏几份证书

一个检查程序说“全部通过”，怎么知道它不是什么都放行？

瀚林写好程序，总要先故意喂它一份坏的输入，检查程序也是这样试的。我们故意做坏了三份证书，看它会不会拒绝：一份把联合分布的总量改掉，一份把一个对偶权重改成了正数（这种权重只许是零或负数），一份把一个集合的权重改错。三份坏证书都被拒绝了。

这只能说明检查程序能抓住这几种具体的错误，不能说明它没有任何缺陷。

四种工作，各管一段

一份原始—对偶证书，管的只是一组表。回头看瀚林这一路的计算，一共分成四部分：

• 精确证书，检查一组表的最好值；
• 完整枚举，检查角的清单有没有列全；
• 有限的清单为什么足以代表所有的输入，靠的是第十八章的有限极值归约，这是一般的数学证明；
• 另有一组检验例子，用来看圈和仙人掌图上的构造做得对不对。

$K_4$ 的清单上，一共有四十二组表。