🔢 mathematics

The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048

本文通过分析所有布尔三次型的 GL(10,2)-轨道下的陪集权重枚举，计算了三阶 Reed-Muller 代码 RM(3,11) 的完整权重分布，这一过程同时为 RM(2,10) 的覆盖半径建立了一个 408 的新下界，并改进了 RM(6,10) 在 RM(7,10) 中相对覆盖半径的上界至 32。

原作者： Kirill Khoruzhii, Patrick Gelß, Sebastian Pokutta

发布于 2026-07-03

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Kirill Khoruzhii, Patrick Gelß, Sebastian Pokutta

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

想象一下，你正在试图组织一个庞大的秘密代码库。在数学和计算机科学的世界里，这些代码被称为 Reed–Muller 码。它们就像是一套特殊的指令集，用于清晰地传输信息，即使信息在传输过程中发生了一些混乱或损坏。

这篇论文旨在解决一个特定的、极其困难的谜题：计算一个长度为 2,048 的三阶码（third-order code）的精确“重量分布”（weight distribution）。

以下是作者的工作内容，使用了简单的类比进行说明：

1. 目标：统计“重”代码与“轻”代码

把每一组代码想象成一串由 2,048 个开关（开或关）组成的序列。

重量（Weight） 简单来说就是有多少个开关处于“开启”状态。
重量分布（Weight Distribution） 则是一个巨大的清单，它准确地告诉你：有多少个代码有 1 个开关开启，有多少个有 256 个开启，有多少个有 512 个开启，等等。

对于规模较小的库，数学家们已经有了答案。但对于这个特定的、巨大的库（长度为 2,048），这份清单一直缺失。作者们想要写下这份完整的目录。

2. 问题：过多的组合

为了解决这个问题，他们必须观察数十亿种代码的变化。这就像是在一家巨大的冰淇淋店里，尝试品尝每一种可能的口味组合，以看看哪一个是“最甜”或“最重”的。

这家店拥有 369 万 个不同的“口味家族”（数学家称之为“轨道”，即 orbits）。如果他们试图品尝每个家族中的每一个变化，这项任务将耗时比宇宙年龄还要长。这在计算上是不可能的。

3. 突破口：“捷径”规则

作者发现了一个聪明的捷径，他们称之为结构定理（structural theorem）。

想象一下，你正在试图从一个仓库里找到最重的行李箱。通常情况下，你必须打开每一个行李箱。但作者发现了一个规则：

“对于几乎每一种类型的行李箱，你只需要观察它的其中一个特定侧面（一个‘超平面限制’，即 hyperplane restriction），就能了解整个行李箱的情况。你只需要对一种非常奇怪、罕见的行李箱类型进行完整的、缓慢的检查。”

这个规则允许他们跳过了 99.9% 的繁重工作。他们不再需要检查数十亿个变化，而只需要检查一个可控的数量。这把一个不可能完成的任务变成了一个大约需要 65 年计算机运行时间的任务（虽然仍然巨大，但在现代超级计算机面前是可行的）。

4. 结果：新纪录

在对所有 369 万个家族运行完这个捷径后，他们终于组装出了完整的清单（重量分布）。

但在进行这项工作的过程中，他们发现了更令人兴奋的东西：

“最难”的代码： 他们在寻找一种远离简单代码的、最复杂的代码。用数学术语来说，他们是在寻找“二阶非线性度”（second-order nonlinearity）。
旧纪录： 已知的最佳“距离”是 400。
新纪录： 他们发现了 179 个特定的代码家族，其距离实际上达到了 408。

这是一件大事，因为这推高了这些代码能达到的“复杂性”已知极限。这就像是在奥运会上发现了一个新的跳高纪录。

5. 支线任务：一种更快的猜测方法

主要的计算过程耗时很长。因此，作者还构建了一个“智能猜测器”（启发式搜索，heuristic search）。

它不像是在品尝每一种冰淇淋口味那样，而是快速尝一口，看看是否接近目标，然后进行调整。
它找到了相同的答案（408），但速度快了 1,000 倍。
他们利用这个快速猜测器解决了另一个类似且更难的谜题（涉及 7 阶码），并同样提升了那个记录，将“距离”从 50 降低到了 32。

总结

简而言之，作者们：

绘制了一片巨大的、未知的数学领地（长度为 2,048 的代码）。
发现了一个捷径，使绘制地图成为可能。
发现了一个新纪录，即这些代码可以达到的复杂程度（将极限从 400 提高到了 408）。
创造了一个更快的工具，可以为未来的谜题快速寻找这些纪录。

他们并没有发明新的药物或引擎；他们解决了一个纯数学谜题，帮助我们理解纠错码的基本极限。

技术摘要：长度为 2048 的三阶 Reed–Muller 码的重量分布

问题陈述
Reed–Muller 码 $RM(r, m) $的重量分布是编码理论中的一个经典问题，但目前仅已知阶数$ r \leqslant 2 $及其对偶码$ r \geqslant m-3 $的闭合解。对于三阶码（$ r=3 $），完整的分布仅通过针对长度最高至 1024（$ RM(3, 10)$）的单独计算得以建立。本文旨在计算该链条中的下一步——长度为 2048 的三阶 Reed–Muller 码 $RM(3, 11) $的重量分布。第二个目标是确定所有十变量三次型的二阶非线性度$ d_2(f) $，从而确定$ RM(2, 10) $在$ RM(3, 10) $中的相对覆盖半径$ \rho_{2,3}(10)$。

方法论
计算依赖于 Sarwate 型递归，该递归将 $RM(3, m+1) $的重量枚举器表示为所有三次型$ f $对应的$ f + RM(2, m) $的陪集重量枚举器的平方和。由于陪集枚举器仅取决于$ f $的$ GL(m, 2)$-轨道，因此该求和可以简化为以轨道大小为权重的轨道代表元的求和。

对于 $m=10$ ，主要的瓶颈在于庞大的轨道数量（3,691,560 个非零轨道）以及评估单个陪集枚举器的成本。Brier 和 Langevin 的标准拆分公式要求对 $m=10$ 时 $2^{36}$ 个齐次二次型进行外层枚举，这对于完成全目录扫描在计算上是不可行的。

为了克服这一困难，作者采用了结构定理（定理 1）：除了在每个奇数维中存在的一个轨道外，每个非退化布尔三次型都允许一个非退化超平面限制。对于 $m=10$ （偶数维），该定理保证了每个非退化轨道都有一个同样是非退化的超平面限制。这使得陪集枚举器可以通过规模为 $2^{26}$ 的商空间而非 $2^{36}$ 来计算，从而使每个轨道的计算量节省了 $2^{10}$ 倍。

陪集重量枚举器的评估是使用快速 Walsh–Hadamard 变换在生成的仿射陪集上进行的。整个目录扫描过程大约耗费了 65 个 CPU 年。为了验证结果的紧密性并提高用于上界的效率，作者开发了一种局部搜索启发式算法（结合了贪婪下降、 $\tau$ -移动、迭代局部搜索和束搜索）。该启发式算法能够找到显式的二次修正项 $q$ ，以最小化 $wt(f+q)$，从而以极小的代价为覆盖半径提供证明。

核心贡献与结果

$RM(3, 11)$ 的重量分布：
本文给出了 $RM(3, 11) $的完整重量分布（表 1）。该结果是通过对十变量中所有 3,691,560 个非零$ GL(10, 2)$-轨道的三次型进行平方陪集重量枚举器求和，再加上零轨道的贡献而组成的。
二阶非线性度与相对覆盖半径：
每个陪集枚举器的最低非零指数对应于二阶非线性度 $d_2(f)$ 。计算表明，所有十变量三次型中 $d_2(f)$ 的最大值为 408。
- 定理 3： $RM(2, 10) $在$ RM(3, 10) $中的相对覆盖半径$ \rho_{2,3}(10)$ 正好是 408。
- 该最大值在 179 个不同的轨道上达到。这些轨道的代表元及其“接吻数”（实现最小重量的二次型计数）列于表 2 中。
- 所有 179 个极值形式均为非退化形式。
改进的覆盖半径下界：
该结果将 $RM(2, 10)$ 覆盖半径的最佳已知下界从 400 提高到了 408。这 179 个轨道作为该下界的显式见证者。
与交替秩（Alternating Rank）的联系：
论文建立了 $d_2(f)$ 与三次型交替秩（$arank $）之间的关系。利用导出的界限（定理 4），作者表明对于任何满足$ d_2(f) = 408 $的形式，其交替秩必须至少为 6。在$ m=10 $中，最大交替秩为 7。分析显示，179 个极值轨道中有 177 个具有$ arank = 7 $，另有 2 个具有$ arank = 6 $。这与较低维度（$ m \leqslant 9$）的情况形成对比，在低维度中，极值形式被迫具有该维度的最大可能交替秩。
启发式搜索与 Cocubic 上界：
局部搜索启发式算法成功地以大约全枚举一千分之一的成本重现了界限 $\rho_{2,3}(10) \leqslant 408$ 。将其应用于七阶形式时，该启发式算法将 $RM(6, 10) $在$ RM(7, 10)$ 中的相对覆盖半径的上界从 50 改进到了 32（引理 2）。

意义
本文声称其意义主要在于解决了 $RM(3, 11)$ 的重量分布问题，延续了已知的三阶码链条。关于非退化超平面限制的结构定理被视为关键的推动力，它使得全目录扫描在以往被认为“无法触及”的情况下变得可行。

确定 $\rho_{2,3}(10) = 408$ 对于覆盖半径文献具有重要意义，更新了 $RM(2, 10) $的最佳已知下界。此外，对极值轨道的分析提供了结构性的洞察：从单项式迹多项式（此前持有 400 纪录）向二项式迹多项式的转变，以及极值形式集中在最大交替秩处的现象，为在高维（$ m > 10$）中寻找高非线性度形式提供了新的方向。作者指出，枚举数据和参考代码已公开，以促进编码理论和布尔函数分析领域的进一步研究。

1. 目标：统计“重”代码与“轻”代码

2. 问题：过多的组合

3. 突破口：“捷径”规则

4. 结果：新纪录

5. 支线任务：一种更快的猜测方法

总结

类似论文