🔢 mathematics

Perfect codes in weakly metric association schemes

本文引入了多项式弱度量结合方案的概念，并将 Lloyd 定理与 Schwartz-Zippel 引理相结合，以推导出包括 Lee 距离、NRT 距离、混合 Hamming 距离以及和秩距离在内的多种度量下完美码的非存在性结果。

原作者： Minjia Shi, Jing Wang, Patrick Solé

发布于 2026-06-02

📖 1 分钟阅读🧠 深度阅读

原作者： Minjia Shi, Jing Wang, Patrick Solé

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一个巨大的、多维度的仓库里堆放完全相同的圆形盒子。你的目标是这样排列这些盒子，使得仓库地板上的每一平方英寸都被恰好一个盒子覆盖，既没有缝隙，也没有重叠。在数学和编码理论的世界中，这被称为寻找一个**“完美码”（perfect code）**。

这篇由 Shi、Wang 和 Solé 撰写的论文本质上是一个侦探故事。作者们试图弄清楚：“在哪些特定类型的仓库中，完美地堆放这些盒子在数学上是不可能的？”

以下是他们如何破解这个谜题的，通过简单的概念进行拆解：

1. 仓库与规则（设定）

在编码理论中，数据被发送为一组数字（比如一串由 0 和 1 组成的序列，或者使用另一种语言的数字）。

空间： 将“仓库”想象成一个巨大的网格，其中的每个点都代表一条可能的消息。
距离： 通常，我们通过计算有多少个字母不同来测量距离（比如将“cat”与“bat”对比，距离为 1）。但在本文中，他们研究了更复杂的距离测量方式，例如 Lee 度量（数字像时钟一样循环）或 NRT 度量（位置的重要性超过了数字本身）。
完美码： 完美码是一组“中心点”（消息），使得如果你在每个中心周围画一个一定大小的圆（或球体），这些圆能完美覆盖整个仓库，且互不重叠。

2. 旧的线索：Lloyd 定理

几十年来，数学家们一直使用一种叫做 Lloyd 定理 的工具。你可以把它看作是一个“神奇清单”。

如果一个完美码可能存在，该定理指出一个特定的数学配方（一个多项式方程）必须拥有一定数量的“根”（即解），且这些解必须是整数。
如果这个配方没有足够的整数解，那么完美码就不存在。

然而，这个旧的清单是有限制的。它在处理简单的、标准的仓库（如 Hamming 度量）时效果很好，但对于上述更复杂的、“奇特”的仓库（如 Lee 或 NRT 度量），它会失效或给出模糊的答案。

3. 新工具：Schwartz-Zippel 引理

作者决定将旧的清单与来自计算机科学的一个强大新工具——Schwartz-Zippel 引理结合起来。

类比： 想象你有一个巨大的、多颜色的蛋糕（一个多变量多项式）。你想知道这个蛋糕上是否存在任何“零点”（即空缺处）。
Schwartz-Zlyppel 引理就像一条规则，它说：“如果你有一个具有一定数量成分（变量）和一定复杂度（次数）的蛋糕，那么你可能拥有的空缺点数量是有严格限制的。”
转折点： 作者意识到，对于这些复杂的仓库，那个“神奇清单”（Lloyd 定理）所要求的空缺点数量，超过了 Schwartz-Zippel 规则所规定的物理极限。

4. “弥散”问题

为了实现这一点，他们引入了一个新概念，称为弥散函数（Dispersion Function）。

可以将其想象为一个“人群计数器”。它统计在距离中心一定范围内，存在多少种不同类型的“邻里”。
在一个简单的仓库中，人群增长缓慢（线性增长）。而在这些复杂的仓库中，人群的增长是爆发式的（指数级增长）。
作者证明了，由于在这些特定度量下人群增长得如此之快，导致“神奇清单”所要求的解的数量，根本无法在 Schwartz-Zippel 规则设定的限度内容纳得下。

5. 判决：“这里没有完美码”

通过结合这两个想法，作者们推导出了一个“主定理”。他们将其应用于四种特定类型的复杂仓库：

Lee 度量： 用于处理像数字时钟或模运算之类的场景。
NRT 度量： 用于生成随机数和处理数据块。
Sum-Rank 度量： 用于网络编码（在互联网上传输数据）。
混合字母表码（Mixed Alphabet Codes）： 其中消息的不同部分使用不同的“语言”（例如，有些部分是二进制，有些是三进制）。

结果： 对于这四种情况，在某些条件下（通常是当仓库非常大或盒子尺寸特定时），数学证明了完美堆放是不可能的。因为“人群”太庞大了，而“规则”不允许这种完美的契合。

6. 他们没有做的事情

需要注意的是，这篇论文并没有做以下事情：

他们并没有发明一种新的堆放盒子的方法。
他们并没有说这些编码是没用的；他们只是证明了在这些特定设定下，其“完美版本”并不存在。
他们没有解决关于所有 Lee 码的 50 年之久的猜想（这仍然是一个开放性问题），但他们提供了强有力的证据，表明对于大规模尺寸，完美码很可能并不存在。

总结

作者们构建了一个新的数学“陷阱”。他们展示了对于几种重要的类型的数据传输系统，空间的几何结构是如此扭曲，以至于你永远无法完美地排列你的纠错码。如果你试图强行进行完美排列，数学会说：“不行，数字对不上。”这有助于工程师们知道，在这些特定领域，他们应该停止寻找“完美”的方案，转而专注于寻找“足够好”的方案。

技术摘要：弱度量结合方案中的完美码

问题陈述
本文探讨了分类能够容纳 $e$ -完美码（即空间被半径为 $e$ 的不相交球体划分的码）的有限度量参数的基本问题。虽然 Lloyd 定理为标准度量结合方案（特别是针对存在此类码的场景）提供了必要条件（即 Lloyd 多项式在整数点处消失），但许多感兴趣的编码场景——如 Lee 度量、NRT 度量、混合字母表和和秩距离（sum-rank distance）——并不严格满足度量结合方案的定义。之前的推广研究，例如 Solé (1989) 引入的“弱度量结合方案”（WMAS）概念，虽然建立了广义的 Lloyd 定理，但在过去三十多年中并未产生任何关于不存在性的结果。核心挑战在于如何为这些更广泛的、非度量背景下的完美码推导出有效的非存在性判据。

方法论
作者结合两种不同的数学框架来推导新的非存在性结果：

WMAS 中的广义 Lloyd 定理： 他们利用弱度量结合方案的框架，在该框架下，如果一个 $e$ -完美码存在，则 Lloyd 多项式 $\Psi^{(e)}(j)$ 必须至少消失 $\Pi(e) - 1$ 次。这里 $\Pi(e)$ 是“弥散函数”（dispersion function），用于计算产生距离至多为 $e$ 的元素的类数。
Schwartz-Zippel 引理： 他们应用了理论计算机科学中的 Schwartz-Zippel 引理，该引理提供了有限定义域上非零多元多项式零点个数的上界。具体而言，一个在集合 $S$ 上总度数为 $e$ 的 $r$ 元多项式，其零点个数最多为 $e \cdot |S|^{r-1}$ 。

为了桥接这些概念，作者引入了 $r$ -多项式结合方案 的概念。如果一个 WMAS 的第一特征值是 $r$ 元多项式在特定点处的取值，则称其为 $r$ -多项式的。通过将 Lloyd 多项式视为一个最多为 $e$ 次的多元多项式，作者将所需的零点数量 ( $\Pi(e) - 1$ ) 与 Schwartz-Zippel 界限允许的最大零点数量 ( $e \cdot |S|^{r-1}$ ) 进行比较。如果 $\Pi(e) - 1 > e \cdot |S|^{r-1}$ ，则会产生矛盾，从而证明不存在这样的完美码。

主要贡献与结果
本文建立了一个主定理（定理 2），指出如果弥散函数的增长相对于索引集的大小和变量的数量足够快，则在 $r$ -多项式 WMAS 中不存在 $e$ -完美码。该一般性结果被应用于四个特定的编码场景：

Lee 度量：
- 固定字母表 ( $q$ )： 对于较大的码长 $n$ 和与 $n$ 成比例的覆盖半径 $e$ ，作者证明了其不存在性。
- 固定 $e$ ： 对于固定的字母表大小 $q$ 和足够大的 $n$ ，若 $e > (s+1) \cdot (s!)^2 / (s-1)$ （其中 $s = \lfloor q/2 \rfloor$ ），则不存在完美码。这为存在了 50 年之久的猜想提供了渐近支持，即当 $e > 1$ 且 $n > 2$ 时，不存在完美 $e$ -码。
和秩度量 (Sum-Rank Metric)： 用于网络编码，论文推导出了当块数 $t \to \infty$ 时不存在性的条件。如果覆盖半径与块数的比值 $e/t \to a$ ，且维度 $d$ 满足 $d < (1+a)^{1+a}/a^a - 1$ （近似为 $d < e^a$ ），则不存在完美码。
混合字母表码： 对于 Hamming 方案的直积，论文证明了如果覆盖半径 $e$ 随 $n$ 按 $an $的比例缩放，且$ a > 1/k $（其中$ k$ 是不同字母表组的数量），则不存在完美码。
NRT 度量（有序 Hamming 空间）： 与 Lee 度量的情况类似，对于较大的 $n$ ，当 $e$ 超过依赖于块长度 $r$ 的特定阈值时，证明了不存在性。

作者还提供了数值表以说明这些界限，表明所推导的理论阈值是充分条件，尽管实际的非存在性临界点通常出现得更早。

局限性与反例
论文明确指出该方法并非普适的。它对于弥散函数 $\Pi(e)$ 增长过慢或变量数量过多的方案失效。具体包括：

齐次度量 (Homogeneous Metric)： 当 $n$ 很大时，条件 $\Pi(e) - 1 > e \cdot |S|^{r-1}$ 不成立，因此该定理无法证明其不存在性。
$q$ -ary Johnson 方案： 弥散函数的增长不足以满足该不等式，因此该定理不适用于此方案。

意义
本文的主要意义在于通过将经典代数编码理论（Lloyd 定理）与计算机科学中的组合界限（Schwartz-Zippel 引理）相结合，振兴了非度量背景下完美码的研究。通过引入多项式弱度量结合方案的概念，作者建立了一个统一的框架，为四种主要的编码度量提供了渐近非存在性结果。这项工作将多元 $P$ -多项式方案和 $m$ -距离正则图的最新发展与经典的编码问题联系了起来，为在传统度量假设失效的情况下分析完美码的极限提供了一种新的工具。