🔢 mathematics

$2$-quasi-perfect Lee codes and abelian Ramanujan graphs: a new construction and relationship

本文提出了一种基于有限域 $\mathbb{F}_{q^2}$ 中集合 $H_q = \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$ 生成元的新显式无限族 2-拟完美 Lee 码构造，并建立了该码与梅萨格等人构造的码以及李图和有限欧几里得图等阿贝尔拉马努金图之间的统一理论框架。

原作者： Shohei Satake

发布于 2026-04-22

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Shohei Satake

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

这篇论文就像是在设计一种极其高效的“防错快递系统”，同时发现这个系统和一种**神奇的“社交网络”**有着惊人的联系。

为了让你轻松理解，我们把论文里的专业术语换成生活中的比喻：

1. 核心任务：给快递包上“防错锁” (Lee 码)

想象你正在给成千上万个包裹贴标签（这就是编码）。在传输过程中，标签可能会因为颠簸而磨损，导致数字看错（这就是错误）。

Lee 距离：就像是在一个圆形的钟面上，数字"1"和"2"离得很近，但"1"和"12"虽然数值差大，但在圆上其实也很近。这种“圆周距离”就是 Lee 距离。
准完美码 (Quasi-perfect Code)：这是一种“超级防错锁”。它不仅能纠正少量的错误（比如把"1"看成"2"），而且保证在覆盖所有可能的错误情况时，几乎没有浪费空间。这就好比你的锁既结实又轻便，没有多余的金属。

论文的贡献：作者发现了一种新的、通用的方法，可以制造出这种“超级防错锁”，而且这种锁可以做得非常大（长度任意长），适用于各种复杂的场景。

2. 新发明的“魔法配方” (Hq 集合)

以前的科学家（如 Mesnager 等人）已经找到了一些制造这种锁的配方，但作者发现了一个全新的配方。

旧配方：像是用特定的积木块拼出来的，虽然好用，但看起来有点孤立。
新配方 (Hq)：作者利用了一个叫 $y = x^3$ $y = x^{3}$ 的数学曲线上的点作为“积木”。
- 比喻：想象你在一个巨大的棋盘上，只挑选那些符合“立方体规律”的格子作为关键节点。作者证明，只要棋盘够大（ $q \ge 14$ ），用这些特定的格子拼出来的锁，就是完美的“准完美锁”。
- 惊喜：这个新配方做出来的锁，和以前大家知道的那些锁，虽然看起来参数一样（大小、纠错能力相同），但内部结构完全不同。就像两辆外观一样的跑车，引擎内部的设计却截然不同。

3. 意外的“跨界”发现：锁与社交网络 (拉马努金图)

这是论文最精彩的部分。作者发现，制造这些“防错锁”的过程，竟然和一种叫**“阿贝尔拉马努金图” (Abelian Ramanujan Graphs)** 的东西是一回事。

什么是拉马努金图？
- 比喻：想象一个巨大的社交网络（比如微信好友圈）。如果这个网络设计得极其高效，每个人只需要认识很少的人，就能在很短的时间内联系到网络里的任何人（直径小），而且这个网络看起来非常“随机”、没有规律（伪随机性强），这就是拉马努金图。它是网络设计的“黄金标准”。
- 这种图在数学界非常著名，被认为是“最完美的社交网络”。
两者的联系：
- 作者发现，他造出的“新防错锁”，其背后的数学结构，正好对应着一种新的拉马努金图（由 Forey 等人最近发现的）。
- 更重要的是，作者把以前那些著名的“防错锁”（Mesnager 等人的成果）和另外两种著名的“完美社交网络”（Li 的图和有限欧几里得图）联系在了一起。
- 统一框架：以前大家觉得这些锁是零散发明的，现在作者发现，它们其实都是同一种“完美社交网络”的不同表现形式。就像发现苹果、梨和橘子虽然长得不一样，但都属于“蔷薇科”这个大家族。

4. 为什么这很重要？(哲学层面的思考)

论文最后提出了一个有趣的观点：

看似矛盾：拉马努金图的特点是“看起来像随机的”（伪随机），这通常意味着没有固定的规律。但是，要造出完美的“防错锁”，却需要非常严格、死板的结构（不能有任何多余的错误空间）。
结论：作者发现，“看起来随机”和“结构严谨”竟然可以共存。这就像是一个看起来杂乱无章的森林，其实每一棵树的生长都遵循着极其精密的数学法则。这种“宏观随机、微观有序”的特性，正是这些代码和图形如此强大的原因。

总结

这篇论文就像是一位建筑大师：

他设计了一种新的、超坚固的防盗门（新构造的 Lee 码）。
他惊讶地发现，这扇门的结构图纸，竟然和一种传说中的“完美城市交通网”（拉马努金图）完全吻合。
他还把以前大家造的各种防盗门，都归类到了这个“完美交通网”的家族里，解释了为什么它们都那么好用。

这不仅解决了“如何造出更好的防盗门”的问题，还揭示了数学中**“编码理论”（保护信息）和“图论”**（网络连接）之间深层的、美丽的统一性。

这篇论文由 Shohei Satake 撰写，题为《2-准完美 Lee 码与阿贝尔拉马努金图：一种新构造及其关系》。文章主要解决了构造任意长度的 2-准完美 Lee 码的问题，并建立了 Lee 码构造与阿贝尔拉马努金图（Abelian Ramanujan Graphs）之间的理论联系。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

Lee 码与准完美性：Lee 码是在 Lee 距离下定义的纠错码。寻找“完美”Lee 码（即同时具有最大纠错能力和最小覆盖半径）是一个经典难题（受 Golomb-Welch 猜想限制，仅在特定参数下存在）。因此，研究重点转向构造“准完美”Lee 码（t-准完美码指能纠正 t 个错误且覆盖半径为 t+1）。
现有挑战：
- 构造任意大长度的准完美 Lee 码仍然是一个开放难题。
- 现有的构造（如 Camarero-Martínez 和 Mesnager-Tang-Qi 的构造）往往基于特定的多项式方程解集，缺乏统一的理论框架来解释为何某些代数结构能产生此类码。
- 虽然已知某些阿贝尔拉马努金图（具有最优谱间隙的图）的小直径有利于 Lee 码的覆盖半径，但具体哪些拉马努金图能产生准完美码尚不明确。
核心目标：
1. 构造一种新的、显式的、任意长度的 2-准完美 p 进制 Lee 码族。
2. 建立 Lee 码构造与阿贝尔拉马努金图（特别是 Li 图和有限欧几里得图）之间的统一理论框架。

2. 方法论 (Methodology)

文章采用了代数几何、有限域理论和谱图理论相结合的方法：

码的构造框架：
- 基于 Mesnager, Tang 和 Qi 提出的通用构造框架 $C(\Gamma, H)$ 。其中 $\Gamma$ 是 $\mathbb{F}_p$ 上的向量空间， $H$ 是生成集。
- 判定条件（引理 2）：码 $C(\Gamma, H)$ 是 2-准完美的充要条件涉及集合 $H$ 的迭代和（ $H^{(i)}$ ）的大小和覆盖性质。具体而言，要求 $\bigcup_{i=0}^2 H^{(i)}$ 的大小满足特定等式，且 $\bigcup_{i=0}^3 H^{(i)} = \Gamma$ 。这对应于 Cayley 图 $\text{Cay}(\Gamma, H)$ 的直径为 3。
新构造策略：
- 利用有限域 $\mathbb{F}_{q^2}$ （其中 $q=p^k$ ）的加法群 $\mathbb{F}_q^2$ 作为向量空间。
- 定义生成集 $H_q = \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$ 。这对应于三次曲线 $y=x^3$ 上的点。
- 利用代数几何工具（Hasse-Weil 界、绝对不可约性）来验证 $H_q$ 是否满足 2-准完美的判定条件。
图论联系：
- 分析由 $H_q$ 生成的 Cayley 图的谱性质，确认其为“几乎拉马努金图”（Almost Ramanujan Graph）。
- 将 Mesnager-Tang-Qi 构造中的生成集与Li 图（Li's graphs）和有限欧几里得图（Finite Euclidean graphs）进行对比和统一。

3. 主要贡献与结果 (Key Contributions & Results)

A. 新的 2-准完美 Lee 码构造 (Theorem 4)

构造：对于素数 $p \ge 5$ 和 $q=p^k \ge 14$ ，定义码 $C(\mathbb{F}_q^2, H_q)$ ，其中 $H_q = \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$ 。
参数：
- 长度： $n = \frac{q-1}{2}$
- 维数： $k_{code} = \frac{q-1}{2} - 2k$
- 性质：这是一个 2-准完美的 p 进制 Lee 码。
证明核心：
- 引理 11：证明了 $\#(\bigcup_{i=0}^2 H_q^{(i)}) = 2n^2 + 2n + 1$ ，满足计数条件。
- 引理 12 & 13：利用代数曲线 $F_{a,b}(x,y)=0$ 的绝对不可约性和 Hasse-Weil 界，证明了当 $q \ge 14$ 时， $\bigcup_{i=0}^3 H_q^{(i)} = \mathbb{F}_q^2$ ，即直径条件满足。
独特性：
- 该构造源自 Forey 等人关于几乎拉马努金图的近期工作。
- 与 Mesnager-Tang-Qi 的构造不同（即使参数相同，生成集结构也不同，见示例 7-9）。
- 扩展了适用范围，特别是对于 $p \equiv 1, 7 \pmod{12}$ 的素数，提供了新的参数族。

B. 与阿贝尔拉马努金图的统一关系 (Section 5)

Li 图与 Mesnager-Tang-Qi 码：
- 证明了 Mesnager-Tang-Qi 构造中的生成集 $H_+$ 实际上对应于 Li 图（定义为 $\text{Cay}(\mathbb{F}_{q^2}^+, N_2)$ ，其中 $N_2$ 是范数为 1 的元素集合）。
- 利用 Deligne 对 Kloosterman 和的界限，确认 Li 图是拉马努金图。
有限欧几里得图的统一：
- 引入有限欧几里得图的概念，定义为 $\text{Cay}(\mathbb{F}_{q^2}^+, E_Q)$ ，其中 $E_Q = \{(x,y) \mid Q(x,y)=1\}$ ， $Q$ 为非退化二次型。
- 命题 18：证明了 Mesnager-Tang-Qi 构造中的两类码（基于 $H_+$ 和 $H_-$ ）分别对应于两种不等价的二次型 $Q_+$ 和 $Q_-$ 生成的欧几里得图。
- 结论：任何非退化二次型 $Q$ 生成的码，在坐标置换和符号变化下，都等价于 Mesnager-Tang-Qi 构造中的某一种。这为这些码族提供了统一的几何描述。

4. 意义与结论 (Significance & Conclusion)

理论突破：
- 提供了一类新的、显式的 2-准完美 Lee 码，解决了任意大长度构造的难题。
- 揭示了 Lee 码构造与谱图理论（特别是拉马努金图）之间的深层联系。
谱与结构的辩证关系：
- 文章指出，虽然这些码对应的 Cayley 图在谱上表现为“伪随机”（特征值分布收敛于半圆律，与随机图不可区分），但 2-准完美性要求图具有极其严格的局部结构（直径为 3 且满足特定的覆盖计数）。
- 这揭示了一个有趣的现象：谱不可区分性（Spectral indistinguishability）并不保证局部伪随机性。即，一个图可以是谱意义上的拉马努金图，但仍需满足额外的确定性代数条件才能生成准完美码。
未来方向：
- 探索其他阿贝尔（几乎）拉马努金图是否能生成新的准完美 Lee 码族。
- 进一步研究谱性质与局部覆盖性质之间的结构性差距。

总结：Satake 的工作不仅通过代数几何方法构造了新的 Lee 码，更重要的是建立了一个统一的框架，将分散的 Lee 码构造与数论和组合数学中著名的拉马努金图（Li 图和有限欧几里得图）联系起来，深化了对纠错码与谱图理论之间相互作用的理解。