怀疑了22年之后：混合消息胜过分路传送

设想一个由线缆组成的网络，其中有几个发送者，各自想要把信息送达自己的接收者。经典的做法是路由（routing）：每条消息像包裹一样沿着一条或多条路径传送，流量甚至可以按任意比例分摊到许多路径上。网络编码（network coding）则增加了另一种自由：中间节点可以把收到的消息组合起来——例如把它们相加——而不仅仅是转发。

问题在于，这种自由是否真能让更多数据通过。论文关注的是无向网络，在这种网络中，一根线缆可以双向传输数据，但两个方向共享同一份容量。

一个在一个又一个情形中得到证实的猜想

2004年，Li和Li提出猜想：在这种情形下，编码相比分数路由没有任何优势；Harvey、Kleinberg和Rasala Lehman也独立提出了同样的猜想。在随后的二十年里，它在一类又一类网络中得到证实——两个会话的情形、某些平面网络、最多含六个编码节点的网络等等——但始终没有得到一般性的解决。复杂性理论中的其他一些结果，例如外部存储器中整数排序的下界以及乘法电路的下界，甚至是在假设它成立的前提下证明的。

已知理论早已限定了赌注的大小：编码胜过路由的幅度至多为一个对数因子。而Braverman、Garg和Schvartzman在2017年的一项结果表明，只要有一个网络具有严格的编码优势，就可以把它放大成一个大得多的差距。一切都归结为找到一个有限的例子。

相加就够了

附录给出了基本的构件，说明了为什么混合会有帮助。把几个源放在一个枢纽v周围，把它们的接收者放在另一个枢纽w周围，并用一根线缆连接v和w。每个源还有通往其他接收者的小侧路。在三轮之内，中间那根线缆传送的是所有消息的和；每个接收者收到这个和，再加上从侧路得到的其他消息，然后通过减法还原出自己的消息。如果没有中间那根线缆，每个源到它的接收者都要经过五跳。

这个构件来自Haeupler、Wajc和Zuzic的早期工作，它让编码变得更快，但单凭它本身还不能传送更多：一条长路径仍然可以运行高速率的流水线。

把电路变成网络

多伦多大学的Xindan Zhang和Baochun Li，以及清华大学的Zongpeng Li，找到了缺失的那一步。他们把一段短码变成一个可逆计算——一个由可逆整数加法构成的电路，它完成计算、复制结果，然后撤销中间步骤。接着，他们构建了一个新网络，其物理线缆就是该电路的导线，并为计算中的每一个寄存器（包括临时寄存器）都分配了各自的发送者-接收者需求。

剩下的工作由对沿导线“时间”的细致核算完成。对所有导线求和，长度恰好等于各项需求必须覆盖的最短距离之和。但指定的需求无法避开某些会多花两个单位的门。因此路由必然严格达不到满速率，而编码对每根线缆恰好只使用一次，并且在多个数据块上以流水线方式运行时，速率趋近于1。

证明了什么

• 一个有限的连通网络，其中每个节点最多与另外三个节点相连，每根线缆的容量都为1；在这个网络上，一种简单的二元线性码胜过了最好的分数路由。2004年的猜想是错误的。
• 同一个整数构造同时适用于每一个有限域和每一个非平凡的有限阿贝尔群。
• 通过反复组合副本，作者构造出无穷多族网络，在这些网络上编码趋近于满速率，而路由则按1/log n的某个幂次下降——这是一种多对数级的优势。

论文没有给出其反例中的节点数。仅它的基本构件就是一个持续13122轮的编码。

由机器检验

有限反例和网络族定理都在Lean证明助手中完成了形式化。作者表示，对2472个声明和1755条定理的审查显示，这些证明只使用了Lean的三条标准公理，没有任何未完成的证明；在一个全新环境中进行的独立复核也获得成功，不过使用的是同一个Lean内核。

尚待解决的问题

作者列出了三个问题：在他们的有限例子上优势的真实大小、已知的对数上限是否真的能达到，以及是否存在一个小的反例。论文最后一句话概括了目前的状况：“事实证明，编码在无向网络中确实有帮助；它能帮多大的忙，还有待观察。”

已声明使用人工智能。 一条脚注说明，OpenAI的GPT-6 Astra协助开发了证明和Lean代码。