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

技术摘要：关于 Reed-Muller 子码、格拉斯曼流形划分与和自由函数

问题陈述
本文探讨了编码理论与有限几何中三个相互关联的问题：

1. Reed-Muller 子码：构造 Reed-Muller 码 $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$ 维线性子空间的集合（即格拉斯曼流形）划分为常维子空间码的问题。这等价于确定格拉斯曼图 $J_2(n, k)$ 的色数 $\chi(J_2(n, k))$，其中顶点为 $k$ 维子空间，若两子空间交集维数为 $k-1$ 则连边。

方法论
作者建立了编码理论与和自由函数性质之间的严格对应关系。

• 对应构造：本文证明，非退化的 $(n-r)$ 阶和自由函数 $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ 等价于 $RM(r, n)$中存在一个余维数为$m$且最小距离为$3 \cdot 2^{n-r-1}$的线性子码。这是通过利用函数$F$ 的求值向量构造该子码的校验矩阵来实现的。
• 代数分析：作者利用布尔函数的代数次数、高阶导数的性质以及 Reed-Muller 码的结构（特别是通过平坦子空间及其对称差来刻画最小重量和次小重量码字），推导出了和自由函数存在的必要条件。
• 基于函数的图着色：本文利用“见证函数”$\omega_F(A) = \sum_{x \in A} F(x)$ 来定义格拉斯曼图上的着色。通过确保相邻顶点（交集维数为 $k-1$ 的子空间）映射到不同的非零值，作者构建了有效的着色方案。
• 计算验证：对于小维度（$n=5, 6, 7$），作者在已知的几乎完美非线性（APN）函数中进行了计算搜索，以验证多阶和自由函数（即对多个阶数 $k$ 均为和自由的函数）的存在性。

主要贡献与结果

1. 等价定理（定理 1.1）：
   本文建立了一一对应关系：存在非退化的 $(n-r)$ 阶和自由 $(n, m)$-函数，当且仅当存在一个余维数为 $m$ 且最小距离为 $3 \cdot 2^{n-r-1}$ 的 $RM(r, n)$ 线性子码。

   • 意义：这产生了一类新的 Reed-Muller 子码，它们避开了 $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$ 且同时是 $(k-1)$ 阶和 $k$ 阶和自由的函数 $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$，则格拉斯曼图 $J_2(n+1, k)$ admits 一种使用 $\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 函数中无一为三阶或四阶和自由。对于 $n=7$，仅发现等价于 Gold APN 函数（$x^{15}, x^{77}, x^{85}$）的函数是四阶和自由的。这表明多阶和自由函数极为罕见且难以构造。

意义与主张
本文声称首次建立了 $k$ 阶和自由函数与构造具有增强最小距离的 Reed-Muller 子码之间的直接联系。这一关联为生成避开最小重量码字的子码提供了一种新的代数工具。

此外，该工作提供了 $m < n$ 时和自由函数存在的第一个非平凡必要条件，解决了 Carlet 提出的一个具体开放问题。通过将这类函数与格拉斯曼图的色数联系起来，本文提供了一种改进 $\chi(J_2(n, k))$ 上界的方法，特别是针对 $k > 2$ 的情形。

作者在构造新的和自由函数方面保持谦逊，指出在已知幂函数之外构造真正新的实例仍然困难。他们将 $k \ge 3$ 时多阶和自由函数的存在性框架化为一个重要的开放问题，这对编码理论（非线性码）和图论均具有深远影响。