2025-11-10T02:46:09.476031

On Sum-Free Functions

Ebeling, Hou, Rydell et al.

A function from $\Bbb F_{2^n}$ to $\Bbb F_{2^n}$ is said to be {\em $k$th order sum-free} if the sum of its values over each $k$-dimensional $\Bbb F_2$-affine subspace of $\Bbb F_{2^n}$ is nonzero. This notion was recently introduced by C. Carlet as, among other things, a generalization of APN functions. At the center of this new topic is a conjecture about the sum-freedom of the multiplicative inverse function $f_{\text{\rm inv}}(x)=x^{-1}$ (with $0^{-1}$ defined to be $0$). It is known that $f_{\text{\rm inv}}$ is 2nd order (equivalently, $(n-2)$th order) sum-free if and only if $n$ is odd, and it is conjectured that for $3\le k\le n-3$, $f_{\text{\rm inv}}$ is never $k$th order sum-free. The conjecture has been confirmed for even $n$ but remains open for odd $n$. In the present paper, we show that the conjecture holds under each of the following conditions: (1) $n=13$; (2) $3\mid n$; (3) $5\mid n$; (4) the smallest prime divisor $l$ of $n$ satisfies $(l-1)(l+2)\le (n+1)/2$. We also determine the ``right'' $q$-ary generalization of the binary multiplicative inverse function $f_{\text{\rm inv}}$ in the context of sum-freedom. This $q$-ary generalization not only maintains most results for its binary version, but also exhibits some extraordinary phenomena that are not observed in the binary case.

academic

Sum-Free関数について

基本情報

論文ID: 2410.10426
タイトル: On Sum-Free Functions
著者: Alyssa Ebeling, Xiang-Dong Hou, Ashley Rydell, Shujun Zhao
分類: math.NT（数論）、cs.IT（情報理論）、math.IT（数学情報理論）
発表時期: 2024年10月（arXivプレプリント）
論文リンク: https://arxiv.org/abs/2410.10426

要約

本論文は有限体上のsum-free関数の概念を研究している。 $\mathbb{F}_{2^n}$ から $\mathbb{F}_{2^n}$ への関数が $k$ 次sum-freeであるとは、すべての $k$ 次元 $\mathbb{F}_2$ -アフィン部分空間上での関数値の和がゼロでないことを意味する。この概念はC. Carletによって最近導入され、APN関数の一般化として機能する。研究の中心は乗法逆関数 $f_{\text{inv}}(x)=x^{-1}$ のsum-free性に関する予想である。 $n$ が奇数の場合に限り $f_{\text{inv}}$ が2次（同値的に $(n-2)$ 次）sum-freeであることが知られており、 $3\le k\le n-3$ に対して $f_{\text{inv}}$ は決して $k$ 次sum-freeではないという予想が立てられている。この予想は偶数 $n$ について証明されているが、奇数 $n$ については未解決である。

研究背景と動機

問題定義：本論文はsum-free関数の性質、特に乗法逆関数のsum-free性を研究する。Sum-free関数とは、すべての $k$ 次元アフィン部分空間上での関数値の和がゼロでない関数である。
重要性：
- Sum-free関数はほぼ完全非線形（APN）関数の自然な一般化であり、APN関数は差分攻撃への耐性により暗号学で広く研究されている
- ブロック暗号の積分攻撃への脆弱性を解決する。この攻撃はS-ボックスのアフィン部分空間上での値の和の予測可能性を利用する
- 理論的観点から、sum-freedom概念は豊かな数学的内容を有する
既存の制限：
- 奇数 $n$ の場合、乗法逆関数のsum-free性に関する中心的予想（Conjecture 1.1）は完全には解決されていない
- $q$ 元の場合の適切な一般化に関する研究が不足している
研究動機：sum-free関数理論の理解を進め、特に乗法逆関数に関連する重要な予想を解決し、より一般的な有限体上への拡張を探索する。

中核的貢献

複数の条件下でConjecture 1.1を証明：
- $n=13$ の場合
- $3|n$ の場合
- $5|n$ の場合
- 最小素因子 $l$ が $(l-1)(l+2)\le (n+1)/2$ を満たす場合
二元乗法逆関数の「正しい」 $q$ 元一般化を決定：関数 $g_{q-1}(x)=1/x^{q-1}$ が二元の場合の $f_{\text{inv}}$ の適切な $q$ 元一般化であることを証明
新しい証明方法を提供：Lang-Weil界を用いて $4\in K_n$ （すべての $n\ge 6$ ）の新しい証明を与えた
$q$ 元の場合の異常現象を発見：コンピュータ探索により、 $q=3,5$ かつ $n=7$ に対して、 $g_{q-1}$ が $\mathbb{F}_{q^7}$ 上のすべての $1\le k\le 6$ で $k$ 次sum-freeであることを発見

方法の詳細説明

問題設定

有限体 $\mathbb{F}_{q^n}$ 上の関数 $f: \mathbb{F}_{q^n} \to \mathbb{F}_{q^n}$ が与えられたとき、その $k$ 次sum-free性を研究する。すなわち、すべての $k$ 次元 $\mathbb{F}_q$ -アフィン部分空間 $A$ に対して $\sum_{x\in A} f(x) \neq 0$ が成り立つことを研究する。

中核的方法の構造

Moore行列式法：
- Moore行列式 $\Delta(X_1,\ldots,X_k)$ を用いて線形独立性を特徴付ける
- sum-free性とMoore行列式の零点の関連性を確立
対称多項式法：
- Carletの判別基準を対称多項式形式に再表現
- $\Theta_k(X_1,\ldots,X_k)$ 多項式を導入
Lang-Weil界法：
- 代数幾何のLang-Weil界を利用して有限体上の代数多様体の点数を推定
- $\Theta_4$ の絶対既約性を証明

技術的革新点

統一的理論枠組み：
- 二元から $q$ 元の場合への統一的理論枠組みを確立
- ほとんどの二元結果が $q$ 元の場合に推広可能であることを証明
新しい構成技法：
- Theorem 3.3は既知のsum-free違反例から新しい違反例を構成する体系的方法を提供
- 部分体構造を利用した再帰的構成
絶対既約性証明：
- 付録で $\Theta_4$ 多項式の絶対既約性の技術的証明を提供
- これはLang-Weil界の応用における重要なステップ

主要定理と結果

中核定理

定理3.6： $n\ge 3$ を奇数、 $l$ を $n$ の最小素因子とする。 $(l-1)(l+2)\le (n+1)/2$ ならば、Conjecture 1.1は $n$ に対して成立する。

定理4.6（ $q$ 元版判別基準）：関数 $g_{q-1}$ が $k$ 次sum-freeでない当且つ只当、 $v_1,\ldots,v_k\in \mathbb{F}_{q^n}$ が存在して $\Delta(v_1,\ldots,v_k)\neq 0$ かつ $\Delta_1(v_1,\ldots,v_k)=0$ を満たす。