九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

Lee 度量完美码的分类

《组合设计中的 50 个公开问题》 · 问题 35 专题综述

题面除平凡与少数已知外,是否存在其他 Lee 度量完美码?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

Lee 度量:ℤ 上 «循环距离» —— |a|L = min(|a|, n−|a|) 在 ℤn 中,ℤn 上取坐标和。完美码:半径 r 的 Lee 球恰好铺满整个空间(无重叠无缝隙)。汉明度量的完美码已完全分类(Tietäväinen–van Lint 1970s:Hamming 码与二元/三元 Golay 码之外无,且都是线性的);Lee 度量的对应分类残缺:已知零星族(Golay 的 Lee 版、Golomb–Welch 的负例区间)之外,«非线性的 Lee 完美码» 是否存在是码论的持久缺口。它也是 «晶格铺球» 问题的码论投影——与几何数论(«Lee 球 = 交叉多面体»)相连。

主要概念

Lee 球的体积与铺满条件

ℤn 中半径 r 的 Lee 球体积 = Σj=0min(r,n) 2jC(n,j)C(r,j)(«先选 j 个 «双动» 坐标» 的组合公式)。完美 ⟺ 码字数 × 球体积 = 空间大小——对 ℤn(无限空间)化为 «晶格铺满»:码的 «Voronoi 域» 恰是 Lee 球 ⟺ 晶格的 «覆盖半径 = r 且球无重叠»。Golomb–Welch 猜想(1970):半径 r ≥ 2 的 Lee 球不能铺满 ℤn(n 大时)——已对大 n(Kim 等)证明,小 n 残留。

有限字母表的情形

ℤqn 的 Lee 完美码:「线性」情形有 Tietäväinen 型部分分类;「非线性」情形的 «零星» 完美码(如 q=5 的某些族)使分类复杂化——汉明度量下 «线性 ⟹ 完美 ⟹ 已知族» 的链条在 Lee 度量下断裂。

主要命题与证明

命题 1(汉明完美码分类,Tietäväinen–van Lint;陈述) 汉明度量下,ℤqn(或 𝔽qn)的非平凡完美纠错码只有 Hamming 码族与 Golay 码(二元、三元)。证明走 « Lloyd 定理 »(完美码的 «均匀分布» 强制)+ 参数方程的数论分析。

说明 Lloyd 定理是 «完美 ⟹ 谱约束» 的原型:完美码的 «距离分布» 使某多项式在特定点上取 «整数» ——数论约束直接排除绝大多数参数。□

命题 2(Golomb–Welch 负例,1970 起的攻坚;陈述) ℤn 中半径 r ≥ 2 的 Lee 球不可铺满,对 «n 充分大»(相对 r)已证(Kim–Post等人 2010s 的系列:用 «模算术» 与 «体积-表面积» 论证);小 n(如 n=2,3,4 的若干 r)的残留情形是当前战场。

说明 n=2 时 Lee 球是 «钻石»(旋转 45° 的正方形),钻石铺平面 = 对角晶格铺满 ✓(r 任意)—— «小维反例» 真实存在,这正是分类 «残缺» 的几何原因:n=2 的完美码族(对角晶格)不在 «线性 Golay 型» 模板里。□

命题 3(有限域 Lee 完美码的零星谱;陈述) ℤqn 的 Lee 完美码已知零星族:Golay 码的 Lee 版(q=11 的 «三元 Golay 的 Lee 对应»)、若干 «r=1 的 Hamming-Lee 族» 与零星非线性例。完整分类(含 «非线性» 的排除)未完成——Lloyd 型谱约束在 Lee 度量下的对应版只覆盖部分情形。

说明 本问题的 «设计» 接口:完美码 = «完美覆盖设计» 的度量版,与 06 号覆盖数同族——«完美» 概念在设计理论的三个度量(汉明/Lee/覆盖)上的命运各异,是 «度量几何决定组合命运» 的标本。□

进展与文献

Golomb–Welch《Perfect codes in the Lee metric》(1970);Tietäväinen 与 van Lint 的汉明分类;Kim–Post 的 Lee 铺满负例系列;Horak 的模算术方法。开放核心:Golomb–Welch 猜想的小维残留;非线性 Lee 完美码的排除;Lee 度量下的 «Lloyd 定理» 完整版。

← 返回问题 35