On Reed-Muller subcodes, Grassmannian partitions and sum-free functions

技術的概要：リード・ムラー部分符号、グラスマン多様体の分割、および和自由関数について

問題の定義
本論文は、符号理論と有限幾何学における 3 つの相互に関連する問題を取り扱います：

1. リード・ムラー部分符号：リード・ムラー符号 $RM(r, n)$ の線形部分符号を構成し、すべての最小重み符号語を回避することで、親符号の最小距離よりも厳密に大きい最小距離を達成すること。
2. 和自由関数の存在：$k$ 次和自由関数 $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ の存在条件と必要な下限を決定すること。関数が $k$ 次和自由であるとは、任意の $k$ 次元アフィン部分空間におけるその関数値の和が非ゼロであることを意味します。Carlet が最近この概念を導入し、そのような関数の無限族（$m=n$ の場合）を提供しましたが、$m < n$ の場合および特定の次数 $k \ge 3$ に対するそのような関数の存在は、依然としてほとんど未解決です。
3. グラスマン多様体の分割：$\mathbb{F}_2^n$ のすべての $k$ 次元線形部分空間の集合（グラスマン多様体）を、定次元部分空間符号に分割する問題。これは、頂点が $k$ 次元部分空間であり、辺が次元 $k-1$ で交わる部分空間同士を結ぶグラスマングラフの彩色数 $\chi(J_2(n, k))$ を決定することと同等です。

手法
著者らは、符号理論と和自由関数の性質の間に厳密な対応関係を確立しました。

• 対応関係の構築：非退化な $(n-r)$ 次和自由関数 $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ の存在が、符号次数 $m$ で最小距離 $3 \cdot 2^{n-r-1}$ を持つ $RM(r, n)$の線形部分符号の存在と同等であることを証明しました。これは、関数$F$ の評価ベクトルを用いて部分符号のパリティチェック行列を構成することによって達成されました。
• 代数的解析：著者らは、ブール関数の代数的次数、高次微分の性質、およびリード・ムラー符号の構造（特に、フラットとその対称差を介した最小重みおよび次最小重みの符号語の特性付け）を利用し、和自由関数の存在に対する必要条件を導出しました。
• 関数によるグラフ彩色：本論文は、「証人関数」$\omega_F(A) = \sum_{x \in A} F(x)$ を用いてグラスマングラフ上の彩色を定義します。隣接する頂点（次元 $k-1$ で交わる部分空間）が異なる非ゼロ値に写像されるようにすることで、著者らは有効な彩色を構成しました。
• 計算検証：小さな次元（$n=5, 6, 7$）において、著者らは既知のほぼ完全非線形（APN）関数の間で、複数の次数 $k$ に対して和自由となる多次数和自由関数の存在を検証するために計算探索を行いました。

主要な貢献と結果

1. 同値定理（定理 1.1）：
   本論文は、双射的対応関係を確立しました：非退化な $(n-r)$ 次和自由 $(n, m)$-関数が存在するならば、かつその逆も成り立つのは、最小距離 $3 \cdot 2^{n-r-1}$ を持つ $RM(r, n)$の符号次数$m$ の線形部分符号が存在する場合です。

   • 意義：これにより、$RM(r, n)$のすべての最小重み符号語を回避する新しいリード・ムラー部分符号の族が得られます。これらの部分符号は、元の符号の最小距離の 1.5 倍の最小距離を持ち、符号次数は$n$のみです。範囲$2 < r < n-2$ において、これらの符号は新規であると考えられます。

2. $m$ に関する新しい下限（定理 3.5）：
   著者らは、$k$ 次和自由関数の存在に対する出力次元 $m$ の最初の非自明な下限を導出しました。$2 \le k \le n-2$ に対して、$(n, m)$-関数が $k$ 次和自由であるならば、次が成り立ちます：
   $$m \ge \max\{n - k + 2, k + 2\}$$
   この結果は、$m < n$ の場合、$k$ の特定の範囲に対してそのような関数は存在し得ないことを意味し、これまでは $m=n$ の場合に限定されていた既存の知見を精緻化します。

3. 既知の族の非退化性（定理 3.6）：
   本論文は、Carlet によって導入された無限族の冪関数 $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$ が $k < n$ に対して非退化であることを証明しました。これにより、これらの関数が真に出力空間の次元 $n$ を必要とし、和自由性を維持しながら低次元の関数に縮小できないことが確認されました。

4. 改良されたグラスマングラフ彩色（定理 5.1）：
   著者らは、以前の彩色結果を一般化しました。代数的次数 $k$ の関数 $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ が、$(k-1)$ 次および $k$ 次和自由の両方である場合、グラスマングラフ $J_2(n+1, k)$ は $\binom{m}{1}_2 = 2^m - 1$ 色の有効な彩色を許容することを示しました。

   • 応用：奇数次元における逆関数（$\{1, 2, n-2, n-1\}$-次和自由）を用いて、著者らは $J_2(n+1, n-1)$ に対する彩色を導出しました。
   • 具体的な結果：$n=5$ の場合、立方 $\{2, 3\}$-次和自由関数（$x^7$ および $x^{21}$）の存在は、$\chi(J_2(6, 3)) \le 31$ という限界をもたらし、以前に知られていた上限を改善しました。

5. 多次数関数に関する計算的知見：
   本論文は、$n=6$ に対して、既知の APN 関数のうち、3 次または 4 次和自由となるものは存在しないことを報告しています。$n=7$ に対しては、ゴールド APN 関数（$x^{15}, x^{77}, x^{85}$）に同値な関数のみが 4 次和自由であることが見つかりました。これは、多次数和自由関数が希少であり、構成が困難であることを示唆しています。

意義と主張
本論文は、$k$ 次和自由関数と、強化された最小距離を持つリード・ムラー部分符号の構成との間の直接的なリンクを確立した最初の研究であると主張しています。この関連性は、最小重み符号語を回避する部分符号を生成するための新しい代数的ツールを提供します。

さらに、この研究は、$m < n$ である和自由関数の存在に対する最初の非自明な必要条件を提供し、Carlet が提起した特定の未解決問題に対処しています。これらの関数をグラスマングラフの彩色数と関連付けることで、本論文は、特に $k > 2$ の場合における $\chi(J_2(n, k))$ の上限を改善する方法を提供します。

著者らは、新しい 和自由関数の構成に関しては慎重であり、既知の冪関数を超えて真に新しい例を構築することは依然として困難であると指摘しています。彼らは、$k \ge 3$ に対する多次数和自由関数の存在を、符号理論（非線形符号）およびグラフ理論の両方への含意を有する重要な未解決問題として位置付けています。