Classification of Boolean Cubic Forms in Ten Variables

技术摘要：十变量布尔三次型的分类

问题陈述
本文研究了在域 $\mathbb{F}_2$ 上，十个变量的布尔三次型在 $GL(10, 2)$-等价下的分类问题。布尔三次型是一个多项式$f(x) = \sum T_{ijk} x_i x_j x_k$，其中系数属于$\mathbb{F}_2$，且变量满足$x_j^2 = x_j$。两个形式是等价的，如果可以通过变量的正则可逆线性变换将一个转换为另一个（忽略常数项、线性项和二次项）。该分类对应于在$GL(10, 2)$作用下对空间$RM^*(3, 10)$（第三层 Reed–Muller 码）中非零轨道的枚举。虽然在不同域下对于维度 $m \leq 9$ 的情形已存在完整的分类，但在本文之前，维度 $m=10$ 的情况在任何域下都尚未被处理。

方法论
作者采用了基于秩分层的枚举策略，并结合了一种用于识别轨道的创新完备不变量。

1. 秩分层枚举 (BFS)：
   枚举过程通过“交替秩”（alternating rank）进行，该秩定义为使形式 $f$ 能分解为 $r$ 个可分解三次项之和 $u(x)v(x)w(x)$ 的最小数量 $r$。该过程从零形式开始，通过迭代地将秩为 1 的形式（可分解三次项）添加到当前层的代表元中，从而生成下一秩层的候选对象。通过在每一步识别 $GL(10, 2)$-轨道而非枚举所有$2^{\binom{10}{3}}$ 个形式，显著缩小了搜索空间。

2. 完备不变量构建：
   为了高效区分轨道，作者构建了一个 $GL(10, 2)$-不变量。

   • 正交图 ($G_f$)： 基于关系 $u \perp_f v \iff \Delta_u \Delta_v f(x) = 0$。虽然 $G_f$ 的同构类是 $m < 10$ 时的完备不变量，但在 $m=10$ 时失效，留下了 51 个未解决的碰撞。
   • 关联图 ($B_f$)： 一个由极化双线性形式导出的二部图，其中的边表示映射关系（$u \to_f v$）。
   • 局部统计量： 为了避免使用计算成本极高的全图同构测试，作者提取了局部统计量：
     • $\mu_5(f)$：$G_f$ 中长度为 5 的闭路径的多重集。
     • $\theta(f)$：来自 $B_f$ 的一组特定的右度-共度（right degree-codegree）计数。
     • $\rho(f)$：针对唯一剩余碰撞对（$f_{381}, f_{382}$）的基于标记三元组的解析器。
       上述三元组 $(\mu_5, \theta, \rho)$ 被压缩为一个 64 位字。该不变量经验证在所有代表元之间是无碰撞的。

3. 验证：
   通过两种独立的方法验证完备性：

   • 伯恩赛德引理 (Burnside's Lemma)： 轨道总数与根据群作用得出的理论和一致。
   • 轨道-稳定子恒等式 (Orbit-Stabilizer Identity)： 所有代表元的 $|GL(10, 2)| / |St(f)|$之和等于非零形式的总数（$2^{\binom{10}{3}} - 1$）。

主要贡献与结果

• 目录： 本文提供了一个包含所有 3,691,560 个非零 $GL(10, 2)$-轨道（十变量布尔三次型）的显式目录。
• 代表元： 对于每个轨道，目录都提供了一个最小化单项式数量的代表元（最大观察值为 17）、其在 $GL(10, 2)$ 中的稳定子阶数以及显式的交替秩分解。
• 结构数据：
  • 交替秩： 维度 10 的最大交替秩为 7。分布显示，秩为 6 的形式在非退化形式中构成主导层。
  • 稳定子： 共有 143 种不同的稳定子阶数。大多数 $m=10$ 的形式具有平凡稳定子。
  • 维度： 在总轨道数中，348 个具有非平凡根基（继承自较低的有效维度），而 3,691,212 个在维度 10 下是非退化的。
• 不变量性能： 该 64 位不变量对每个形式的评估平均耗时 0.20 ms，显著快于直接进行规范标记（后者在处理碰撞类时最高耗时 8.9 s）。

意义与应用
作者将这项工作定位为以下几个领域的基石资源：

• 编码理论： 该目录为计算第三阶 Reed–Muller 码 $RM(3, 10)$及其相关结构（如$RM^*(7, 10)$）的陪集权重枚举器和覆盖半径提供了必要的输入。它还为$RM(3, 11)$ 的 Sarwate 型递归提供了所需的轨道索引层。
• 量子计算： 该分类为优化量子电路提供了查找表。由于相位多项式中三次部分的交替秩控制着 Toffoli 门的计数，该目录允许用最优分解替换三次片段（最高达 10 个变量），类似于通过子电路替换来最小化 AND 计数。
• 数学分类： 这构成了第一个对维度 10 上任何域的交替三线性形式的完整分类。通过极化，研究结果直接适用于三向量的几何学以及通过结合子形式（associator forms）进行的码环（code loops）分类。

论文总结指出，虽然 $m=10$ 的分类已经完成，但若要扩展到 $m=11$，由于轨道数量呈指数级增长（估计约为 $\approx 6 \times 10^{13}$），则需要更高效的不变量。相关数据和代码已通过 Zenodo 和 GitHub 公布。