MathLabs

解法：格拉德科夫–帕克–齐明给出的上下铺猜想显式反例(2024年)

第 7/8 步：违反是真实存在的,但小到天文数字级别
上一步下一步
通俗地说

在证明不等式确实反转之后,作者们还大致估算了它反转的程度——答案令人震惊:在他们那张 7,2227{,}222 个顶点的图上,两个概率之间的差距小于 10−433110^{-4331},这个数字微小到没有任何有意义的十进制表示,也完全超出了任何计算机模拟所能探测的范围。这正是为什么前面各步那条谨慎、纯粹解析性的引理链是必不可少的——无论投入多少计算能力,都不可能通过在这种规模的图上直接实验来探测到如此微小的差距。

为了在计算机确实能够探测的规模上感受这一效应,作者们还尝试了同一构造小得多的版本:一个 8282 个顶点的图就已经显示出约 10−4710^{-47} 的差距,而另一个采用不同权重的 2828 个顶点的版本则显示出约 10−7810^{-78} 的差距——两者仍然远小到无法通过模拟单个随机结果来观察,但已经小到足以用精确的计算机计算来确认。

Pr⁡[u1↔u10]−Pr⁡[u1↔u10′]<−10−4331\Pr[u_1 \leftrightarrow u_{10}] - \Pr[u_1 \leftrightarrow u_{10}'] < -10^{-4331}
详细分析

格拉德科夫、帕克与齐明(2024年,注记4.2)指出,由于把小零件 G1204G_{1204} 的六份副本代入霍勒姆超图涉及多层条件化,他们那张 7,2227{,}222 个顶点的反例上真实的差距 Pr⁡[u1↔u10′]−Pr⁡[u1↔u10]\Pr[u_1 \leftrightarrow u_{10}'] - \Pr[u_1 \leftrightarrow u_{10}] 小于 10−433110^{-4331}——小到根本无法通过计算探测,这生动地说明了为什么这个反驳必须是、也确实是纯粹解析性的,而非实验性的。

为了让这一现象在实验上可以观察到,作者们另外计算(论文第7节)表明:使用更小的小零件参数 n=14n = 14,得到一个只有 8282 个顶点的图,其差距在计算上可以探测到,数量级约为 10−4710^{-47};使用与之密切相关的加权上下铺猜想(一种允许边概率各不相同的等价表述),配合进一步优化的小型小零件(n=5n = 5,p≈0.0349p \approx 0.0349),可以得到一个 2828 个顶点的图,差距数量级约为 10−7810^{-78}。这些实验由计算机运行并交叉核对,并不能替代定理1.2的解析证明,但它们在人类可以理解的规模上确认了这一定性机制,并被用来寻找和验证这一现象更小的实例。

这种结合——对大型显式反例给出无条件的解析证明,再辅以针对更小近亲图形的、有目标的计算机实验来建立直觉、探索反例究竟能小到什么程度——反映了现代组合数学中日益常见的一种证明风格,尽管(与四色定理或非周期单块瓷砖的结果不同)这里核心证明的任何一步实际上都不依赖计算机验证。

本步骤用到的知识
事件与概率