Double Toeplitz codes and their average weight enumerators

这篇论文《Double Toeplitz codes and their average weight enumerators》（双重 Toeplitz 码及其平均重量枚举器）由 Masaaki Harada 和 Keito Yamaguchi 撰写，主要研究了**双重 Toeplitz 码（Double Toeplitz codes）**的平均重量枚举器，并以此为基础对有限域 $\mathbb{F}_q$（其中 $q \in \{2, 3, 4\}$）上的此类码的存在性、最优性分类进行了详细分析。

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

1. 研究背景与问题定义

• 背景：双重循环码（Double Circulant Codes）是一类重要的等自对偶（isodual）码。近年来，双重 Toeplitz 码被引入作为双重循环码的推广，旨在构造具有更大最小距离的等自对偶或形式自对偶码。
• 核心问题：
  1. 如何计算双重 Toeplitz 码的平均重量枚举器（Average Weight Enumerator），而不需要显式地枚举所有码字集合？
  2. 利用平均重量枚举器确定在给定长度 $n$ 和最小距离 $d$ 下，是否存在具有特定参数的双重 Toeplitz 码。
  3. 对 $\mathbb{F}_q$ 上的**DT-最优（DT-optimal）**双重 Toeplitz 码（即具有最大可能最小距离的码）进行分类，特别是找出那些不等价于双重循环码或双重负循环码的新码。

2. 方法论

论文采用了理论推导与计算机穷举搜索相结合的方法：

A. 理论推导：平均重量枚举器

• 定义：设 $\Omega_{q,n}$ 为 $\mathbb{F}_q$ 上所有不同双重 Toeplitz $[n, n/2]$ 码的集合。平均重量枚举器定义为 $\Psi_{q,n}(y) = \sum_{C \in \Omega_{q,n}} W_C(y)$。
• 关键引理（Lemma 3.2）：作者推导了包含特定向量 $(u, v)$ 的双重 Toeplitz 码的数量 $|\Omega_{(u,v)}^{q,n}|$。该数量取决于向量 $u$ 和 $v$ 的权重（weight）：
  • 若 $wt(u)=0, wt(v)=0$，数量为$q^{n-1}$。
  • 若 $wt(u)=0, wt(v)\neq 0$，数量为 $0$。
  • 若 $wt(u)\neq 0$，数量为 $q^{n/2-1}$。
• 主要定理（Theorem 3.3）：基于上述引理，作者给出了 $\Psi_{q,n}(y)$ 的显式表达式。该公式仅依赖于 $n$ 和 $q$，无需遍历所有码。
  $$\Psi_{q,n}(y) = q^{n-1} + q^{n/2-1} \left( \sum_{j=1}^{n/2} \left[ \binom{n}{j} - \binom{n/2}{j} \right] (q-1)^j y^j + \sum_{j=n/2+1}^{n} \binom{n}{j} (q-1)^j y^j \right)$$
• 存在性判据（Proposition 3.4）：利用平均重量枚举器的系数，如果低权重码字的平均数量小于总码数乘以 $(q-1)$，则必然存在最小距离至少为 $d$ 的码。

B. 计算机搜索与分类

• 工具：使用 Magma 软件进行计算。
• 等价性简化：为了减少搜索空间，利用双重 Toeplitz 码的对称性（如 $DT(t, a, b) \cong DT(t, b, a)$ 和标量乘法等价性）对候选码进行剪枝（见 Lemma 5.1, 5.2, 5.3）。
• 搜索范围：针对 $q \in \{2, 3, 4\}$ 和 modest 长度（二进制 $n \le 40$，三进制 $n \le 26$，四进制 $n \le 20$ 等）进行了穷举搜索。

3. 主要贡献与结果

A. 平均重量枚举器的显式公式

论文首次给出了双重 Toeplitz 码平均重量枚举器的通用解析表达式（Theorem 3.3）。这使得研究者可以在不生成具体码的情况下，理论上预测特定长度和域上存在高最小距离码的可能性。

B. 最小距离存在性的确定

利用理论公式和计算机验证，论文确定了 $q \in \{2, 3, 4\}$ 时，不同最小距离 $d$ 所需的最小长度 $n$：

• 二进制 ($q=2$)：
  • $d \ge 5$ 存在当且仅当 $n \ge 16$。
  • $d \ge 6$ 存在当且仅当 $n \ge 18$。
  • $d \ge 8$ 存在当且仅当 $n=24$ 或 $n \ge 28$（排除了 $n=26$）。
  • 详细列出了 $d \le 10$ 时的存在性界限（Proposition 4.2）。
• 三进制 ($q=3$)：
  • 修正了文献 [20] 中关于 $n=28$ 时最大最小距离的错误（原报道为 8，实际为 9）。
  • 确定了 $d \le 10$ 时的存在性界限（Proposition 4.3）。
• 四进制 ($q=4$)：
  • 确定了 $d \le 10$ 时的存在性界限（Proposition 4.4）。
  • 特别指出，虽然存在四进制 $[26, 13, 10]$ 码，但 exhaustive search 表明不存在双重循环 $[26, 13, 10]$ 码，并提出了是否存在双重 Toeplitz $[26, 13, 10]$ 码的问题。

C. DT-最优码的分类

论文对 $d_{q,DT}(n)$（最大最小距离）下的所有不等价码进行了分类，并统计了非双重循环/非双重负循环的码的数量：

• 二进制 ($n \le 40$)：
  • 在 $n=38$ 时，发现了 118,328 个不等价的 DT-最优双重 Toeplitz 码，其中绝大多数不等价于双重循环码。
  • 列出了 $n=4, 6, \dots, 40$ 的具体数量（Table 3）。
• 三进制 ($n \le 26$)：
  • 修正了 $n=28$ 的 $d_{3,DT}$ 值为 9。
  • 在 $n=18$ 时发现了 156,189 个不等价的 DT-最优双重 Toeplitz 码（Table 6）。
• 四进制 ($n \le 20$)：
  • 确定了 $n=16, 18, 20, 22, 24$ 时的最大最小距离（Proposition 5.5）。
  • 由于计算量过大，未能完成 $n=16$ 时的完整分类，但给出了 $n=18, 20$ 的结果（Table 10）。

D. 具体构造

论文提供了大量具体的构造实例，包括：

• 具体的生成向量 $r$（用于双重循环码）。
• 具体的参数三元组 $(t, a, b)$（用于双重 Toeplitz 码），例如 $n=14$ 的二进制码、$n=20$ 的三进制码等（见 Tables 4, 5, 7, 9, 11）。

4. 意义与结论

1. 理论突破：建立了双重 Toeplitz 码平均重量枚举器的理论框架，为证明此类码的存在性提供了强有力的工具，类似于自对偶码的研究方法。
2. 新码的发现：分类结果表明，存在大量不等价于传统双重循环码或双重负循环码的 DT-最优双重 Toeplitz 码。这极大地扩展了已知最优码的家族。
3. 修正与完善：修正了先前文献中关于三进制码 $n=28$ 的最小距离的错误数据，并填补了 $q \in \{2, 3, 4\}$ 在中等长度下的参数表空白。
4. 开放问题：论文提出了一个关键问题：是否存在 $(q, n)$ 使得双重 Toeplitz 码的最大最小距离 $d_{q,DT}(n)$ 严格大于双重循环码 $d_{q,DC}(n)$ 或双重负循环码 $d_{q,DN}(n)$？目前的分类显示虽然有很多新码，但在某些参数下，DT-最优码的最小距离并未超过循环码的最优值，但在其他情况下（如 $n=38$ 二进制）数量巨大，暗示了结构上的丰富性。

综上所述，该论文通过结合组合数学理论与计算机代数系统，系统地研究了双重 Toeplitz 码的性质，不仅提供了理论工具，还通过大规模计算丰富了编码理论中的最优码库。