Classification of Boolean Cubic Forms in Ten Variables

技術要約：10変数におけるブール3次形式の分類

問題提起
本論文は、体 $\mathbb{F}_2$ 上の10変数におけるブール3次形式を $GL(10, 2)$-同値の観点から分類する問題に取り組んでいる。ブール3次形式とは、$x_j^2 = x_j$を満たす変数を持つ多項式$f(x) = \sum T_{ijk} x_i x_j x_k$（係数は$\mathbb{F}_2$）のことである。2つの形式は、定数項、線形項、および2次の項を無視した場合、変数に対する可逆な線形変換によって互いに変換可能であれば同値であるとされる。この分類は、$GL(10, 2)$の作用下における$RM^*(3, 10)$（リード・マラー符号の第3層）の非ゼロ軌道の列挙に対応する。$m \leq 9$の各体においては完全な分類が存在するが、$m=10$ のケースは、本研究以前にはどの体においても扱われていなかった。

手法
著者らは、ランク層別列挙戦略と、軌道識別のための新しい完全不変量を組み合わせた手法を採用している。

1. ランク層別列挙 (BFS):
   列挙は「交互ランク（alternating rank）」に基づいて進行する。ここで、交互ランクとは、形式 $f$ が $r$ 個の分解可能な3次形式 $u(x)v(x)w(x)$ の和として分解できる最小の数 $r$ と定義される。プロセスはゼロ形式から始まり、現在のレイヤーの代表元に対してランク1の形式（分解可能な3次形式）を逐次的に加算していく。これにより、次のランクレイヤーの候補が生成される。探索空間は、すべての $2^{\binom{10}{3}}$ 個の形式を列挙するのではなく、各ステップで $GL(10, 2)$-軌道を特定することによって大幅に削減される。

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$ から得られる特定の右次数・余次数カウント。
  • $\rho(f)$: 残された唯一の衝突ペア（$f_{381}, f_{382}$）のためのマーキングされた3つ組（marked triples）に基づくリゾルバ。
    これら $(\mu_5, \theta, \rho)$ は単一の64ビットワードに圧縮される。この不変量は、すべての代表元にわたって衝突がないことが検証されている。

3. 検証:
   完全性は、以下の2つの独立した方法によって検証される：

• バーンサイドの補題: 軌道の総数が、群の作用から導かれる理論的な和と一致する。
• 軌道・スタビライザー恒等式: すべてのカタログ代表元に対する $|GL(10, 2)| / |St(f)|$の総和が、全非ゼロ形式の数（$2^{\binom{10}{3}} - 1$）に等しい。

主要な貢献と結果

• カタログ: 本論文は、10変数におけるすべての非ゼロ $GL(10, 2)$-軌道の具体的なカタログである 3,691,560 個の軌道を提示している。
• 代表元: 各軌道に対し、最小化された単項式数（最大観測値は17）、$GL(10, 2)$ におけるスタビライザーの位数、および明示的な交互ランク分解が提供される。
• 構造データ:
  • 交互ランク: 次元10における最大交互ランクは7である。分布は、ランク6の形式が非退化な形式の中で支配的なレイヤーであることを示している。
  • スタビライザー: 143個の異なるスタビライザーの位数が存在する。次元10におけるほとんどの形式は自明なスタビライザーを持つ。
  • 次元性: 全軌道のうち、348個は非自明な根基（lower effective dimensionsから継承）を持ち、3,691,212個は次元10において非退化である。
• 不変量の性能: 64ビット不変量の評価は、1形式あたり平均0.20 msであり、直接的な標準的ラベル付け（衝突クラスに対して最大8.9 sを要した）よりも大幅に高速である。

意義と応用
著者らは、本研究を以下の領域における基礎的なリソースとして位置づけている：

• 符号理論: このカタログは、第3次リード・マラー符号 $RM(3, 10)$および関連する構造$RM^*(7, 10)$の余集合重み列挙および被覆半径を計算するための必要な入力を提供する。また、$RM(3, 11)$ のためのSarwate型再帰に必要な軌道インデックス層も提供する。
• 量子コンピューティング: この分類は、量子回路を最適化するためのルックアップテーブルを提供する。位相多項式の3次の部分の交互ランクはToffoliゲート数に影響を与えるため、このカタログを用いることで、ANDカウント最小化のためのサブ回路置換と同様に、3次の断片（最大10変数まで）を最適な分解へと置き換えることが可能になる。
• 数学的分類: これは、任意の体における次元10の交互三線形形式の最初の完全な分類である。極化により、その結果はトリベクターの幾何学および結合子形式によるコードループの分類に直接適用される。

論文は、$m=10$ において分類は完了しているものの、$m=11$ への拡張には（軌道の数が $\approx 6 \times 10^{13}$ と推定される指数関数的な増加のため）より効率的な不変量が必要になるだろうと結論づけている。データとコードはZenodoおよびGitHubを通じて公開されている。