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

On Sum-Free Functions

基本信息

论文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界的关键步骤

主要定理与结果

核心定理

Theorem 3.6：设 $n\ge 3$ 为奇数， $l$ 是 $n$ 的最小素因子。如果 $(l-1)(l+2)\le (n+1)/2$ ，则Conjecture 1.1对 $n$ 成立。

Theorem 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$ 。