New lower bounds for constant-weight codes via seeded bit-swap tabu search

想象一下你正试图为一个旅行打包行李，但有一个非常奇怪的规则：你打包的每一件物品的大小必须完全相同，而且没有两件物品可以过于相似。如果它们太像了，在黑暗中可能会混淆在一起，导致混乱。在数字通信的世界里，这个“行李箱”是一个消息，而“物品”是零和一的模式（比特），“大小”则是模式中“1”的数量。这就是**等重码（constant-weight codes）**的谜题。科学家们使用这些编码在有噪声的信道（如 Wi-Fi 或深空无线电）上可靠地发送数据，确保即使有几个比特被扰乱，接收方也能弄清楚发送了什么。目标很简单，但也极其困难：如何在保持差异的前提下，尽可能多地将独特的物品装进这个行李箱。行李箱越大（即能容纳的编码越多），我们就能同时发送更多的信息。

威廉·埃科尔斯（William Echols）决定通过一个聪明的转折点来解决这个打包问题。他并没有从一个空的行李箱开始，然后随机扔东西进去并祈祷它们能放得下，而是使用了一种“种子化”的方法。你可以这样理解：如果你想建造一座更好的乐高城堡，你不会从零开始；你会拿出一座现有的优秀城堡，拆掉一些砖块，然后通过交换它们来尝试让城堡变得更大或更坚固。埃科尔斯使用了一种叫做**禁忌搜索（tabu search）**的计算机方法，这就像是一个非常固执的探险家，拒绝重复走过的路（以避免陷入循环），并不断尝试新的路径。通过用现有的高质量代码设计来“播种”这个探险家，他引导其找到了 124 个全新的、更大的打包排列方式。这些新排列提高了我们发送消息数量的下限，甚至帮助我们理解在高维空间中，多少个球体可以同时接触到一个中心球体——这个概念被称为“切向数（kissing numbers）”。

打包谜题与神奇的种子

在数字世界中，数据仅仅是一串长长的零和一。有时，为了增强鲁棒性，我们只允许具有特定数量“1”的字符串。例如，如果我们规定“重量”为 5，那么每个字符串必须恰好包含五个“1”，其余部分为“0”。现在，假设你有一组这样的字符串。为了防止错误，你的集合中每一个字符串都必须与其他任何字符串都有足够的差异。如果两个字符串太相似，一点点噪声就可能把一个变成另一个，从而让接收方产生困惑。它们之间的“距离”是通过有多少个位置不同来衡量的。

这个领域的核心问题是：在你的集合中，你最多可以放入多少个字符串？ 这个最大值被称为 $A(n, d, w)$，其中 $n$ 是字符串的长度，$d$ 是要求的最小距离，$w$ 是“1”的数量。几十年来，数学家和计算机科学家一直试图为各种设定找到这些最大的集合。他们发现了一些很棒的集合，但通常不知道自己是否已经找到了绝对最大的那一个。他们只知道自己无法做得比目前的数值更好。

“种子化”策略

以往使用计算机搜索寻找这些最大值的尝试往往感觉像是在黑暗的森林中徘徊。计算机从随机猜测开始，虽然有时能找到好的路径，但经常会卡在一些局部的小高地，这些地方看起来像是山顶，但其实并不是。它们会停在那里，认为自己已经找到了最好的代码，而实际上，更高的山峰就在下一座小丘之后。

埃科尔斯意识到，关键在于停止从零开始。他使用了一种**种子初始化（seeded initialization）**技术。他不是生成一个随机的起点，而是取一个已知的、高质量的代码（一个“种子”），并利用它来启动搜索。

他通过两种有趣的方式实现了这一点：

1. 直接播种： 他取一个现有的代码，并小心地添加一个额外的单词，这个单词经过精心选择，以造成最少的“麻烦”（距离赤字）。这创造了一个稍微大一点、稍微有点混乱的起点。
2. 邻域播种： 他观察了针对略微不同问题的代码。例如，如果他想要一个长度为 30 的代码，他可能会取一个长度为 29 的优秀代码，在每个单词后面加一个“0”使其长度变为 30，然后将其作为起点。或者，他可能会取一个长度为 31 的代码，去掉一个“0”，然后使用它。

一旦有了这些“种子化”的起点，他就运行了他的位交换禁忌搜索（bit-swap tabu search）。想象一下，这种搜索就像一场“抢椅子”的游戏，椅子就是字符串中“1”的位置。算法会交换比特的位置，试图让字符串变得更加不同。所谓的“禁忌”部分意味着算法会记录它刚刚做过的移动，并拒绝立即撤销这些移动，从而迫使它探索新的领域，而不是在原地打转。

结果：124 项新发现

通过使用这种聪明的种子化策略，埃科尔斯发现了 124 个新的构造，打破了之前的最佳已知记录。这些不仅仅是微小的改进，有些甚至是巨大的飞跃。

例如：

• 对于一个特定约束下的长度为 39 的代码，之前的最佳记录是 1,014 个单词。新方法找到了 1,118 个单词。这增加了 104 个！
• 对于长度 40，记录从 1,170 跳升至 1,230。
• 对于长度 56，数量从 2,414 增加到了 2,477。

这些数字代表了在这些特定设定下，我们现在可以保证发送而不产生混淆的独特消息的最大数量。该论文并不声称这些是绝对的最大值（即真正的数学极限），但它证明了我们确实可以做得比之前想象的更好。它提高了“下限”，这意味着我们确定至少可以装入这么多项物品。

切向数：令人惊喜的副作用

故事在这里变得更有趣了。论文还涉及到了一个概念，叫做切向数（kissing numbers）。想象一下，房间中央有一个巨大的球体。多少个同样大小的球体可以围绕着中心球体排列，使得它们彼此之间互不重叠，且都与中心球体接触？在三维空间中，答案是 12。但在更高维度的空间中（比如 32 或 33 维），答案很难找到。

这些切向数的数学与埃科尔斯发现的等重码有着深刻的联系。因为他改进了特定参数下的代码（特别是 $A(n, 8, 8)$），他自动提高了 32、33、34 和 37 维切向数的下限。

例如，对于维度 32 ($\tau_{32}$)，之前的估计是至少有 345,408 个球体可以接触中心球体。有了新的代码，这个数字跳升至 346,432。虽然百分比增幅很小，但在高维几何的世界里，能找到哪怕多出一个能放下的球体也是一次显著的胜利。

总结

威廉·埃科尔斯不仅仅是找到了几个更好的代码；他展示了通过聪明地处理搜索起点——即利用现有知识中的“种子”而非盲目开始——你可以找到更好的解决方案。论文证明了 124 项特定的改进是可能的，并且它为我们能够可靠地打包进这些数字字符串中的数据量提供了一个新的、更高的底线。这提醒我们，有时最好的前进方式是站在已有的知识肩膀之上，而不是试图从头开始构建一切。