On Permutation Trinomials and Complete Permutation Polynomials via Fiber Criteria over Finite Fields

本文利用 Zieve 纤维判据将置换多项式的验证简化为三元乘法子群上的显式计算，并在此基础上结合 AGW 判据构建了基于三次单位根纤维分解的完全置换多项式通用构造框架。

要点

这篇论文听起来充满了高深的数学符号，但我们可以把它想象成一场**“数字世界的交通规划”**。

想象一下，你有一个巨大的城市，城市里只有有限数量的居民（比如 $q$ 个人）。在这个城市里，有一条特殊的规则：每个人都要根据一个特定的公式（多项式）移动到另一个位置。

• 置换多项式 (Permutation Polynomials)：就像是一个完美的交通调度员。如果这个调度员能让每一个居民都移动到不同的新位置，且没有两个人撞在一起（没有重复），也没有人掉队（覆盖所有人），那他就是个优秀的调度员。
• 完全置换多项式 (Complete Permutation Polynomials, CPPs)：这是更高级的调度员。他不仅要自己调度得好，还要保证：如果他在原来的规则上再加一步（比如每个人都再往前走一步），大家依然能完美地重新排队，不撞车、不掉队。 这就像是一个不仅擅长指挥交通，还能在突发状况下（比如加塞）依然维持秩序的大师。

这篇论文的作者（Bouyacoub, El-Baz, Kihel）主要做了三件大事：

1. 给旧地图画了更简单的导航图（简化证明）

以前，其他数学家（Bousalmi 等人）发现了一些特定的“完美调度公式”，但他们的证明过程非常繁琐，就像是用显微镜去数每一粒沙子，需要分很多种情况讨论。

作者的新方法：
他们发现了一个神奇的“捷径”（叫 Zieve 准则）。

• 比喻：想象你要检查一条繁忙的街道是否堵车。以前，你要检查整条街上的每一辆车。现在，Zieve 准则告诉你：你只需要检查这条街上最核心的三个路口（数学上叫“三次单位根”）是否通畅。如果这三个路口没问题，整条街就肯定没问题。
• 成果：作者用这个“只看三个路口”的方法，非常简短、清晰地重新证明了之前的旧成果。就像是用 GPS 一键导航，代替了以前手画地图的麻烦。

2. 发明了一套“万能交通构建法”（构建新公式）

这是论文的核心贡献。他们不仅想验证别人发现的公式，还想创造新的“完全调度员”（CPP）。

• 挑战：构建“完全调度员”比构建普通调度员难得多，因为要同时满足两个条件（原规则和新规则都要完美）。
• 新方法（纤维分解法）：
  作者把城市分成了三个大区（对应那三个核心路口）。
  1. 第一步：确保每个大区内部的人能乱序排好队（纤维内的单射）。
  2. 第二步：确保这三个大区之间的人能完美交换位置（大区间的置换）。
  3. 第三步：把这两步结合起来，就得到了一个完美的“完全调度员”。
• 特别技巧：他们发现，如果城市的总人数 $q$ 满足一个特定的条件（$q$ 除以 9 余 1），这个构建过程会变得超级简单，就像给每个大区发一个固定的“通行证”（标量乘法），大家只要按顺序走就行。

3. 发现了“规则失效”的陷阱（反例）

在数学中，知道什么行不通和知道什么行得通一样重要。

• 发现：作者发现，如果城市人数 $q$ 只是满足“除以 3 余 1"，但不满足“除以 9 余 1"，他们刚才那套简单的构建方法就会失效。
• 比喻：就像你发明了一种完美的停车技巧，在 9 个车位的小停车场（$q \equiv 1 \pmod 9$）里百试百灵。但你试着把它用到 7 个车位（$q=7$）或 31 个车位（$q=31$）的停车场时，车子就会撞在一起。
• 意义：通过举出这些具体的“撞车”例子（反例），作者证明了他们的理论是有严格边界的，不是随便什么数字都能用。这就像给未来的研究者画了一张“危险区域”地图，告诉大家：“嘿，在这个区域别用那个简单公式，会出事的！”

总结

这就好比：

1. 以前：大家用笨办法证明某些交通路线是通的。
2. 现在：作者用“只看三个关键点”的聪明办法，轻松证明了旧路线。
3. 创新：作者设计了一套新的“交通建设蓝图”，只要城市规模符合特定条件（$q \equiv 1 \pmod 9$），就能轻松造出完美的交通系统。
4. 警示：作者还特意警告大家，如果城市规模不符合那个特定条件，这套蓝图就会失效，导致交通瘫痪。

这篇论文的价值在于它让复杂的数学证明变得更短、更清晰，并提供了一套容易操作的工具来创造新的数学结构，同时划清了这些工具的使用边界。这对于密码学（保护数据安全）和编码理论（防止信息传输错误）来说，是非常实用的工具。

技术摘要

1. 研究背景与问题 (Problem)

• 核心对象：有限域 $\mathbb{F}_q$ 上的置换多项式 (Permutation Polynomials, PP) 和 完全置换多项式 (Complete Permutation Polynomials, CPP)。
  • PP：多项式 $f \in \mathbb{F}_q[X]$ 诱导 $\mathbb{F}_q$ 上的双射。
  • CPP：不仅 $f$ 是置换多项式，且 $f(X) + X$ 也是置换多项式。CPP 的构造条件更为严格，在编码理论、密码学和伪随机序列设计中具有重要应用，但构造难度更大。
• 具体挑战：
  • 近年来，Bousalmi, Bayad 和 Derbal (2021) 提出了一些特定形式的置换三项式（形如 $X^r(X^{2s} + \alpha X^s + \beta)$，其中 $s=(q-1)/3$）的构造结果，但其原始证明依赖于繁琐的直接计算和分情况讨论。
  • 对于 CPP 的构造，特别是针对 $q \equiv 1 \pmod 9$ 的情况，缺乏一个统一且易于验证的通用框架。
  • 现有的构造方法往往缺乏对参数条件（如 $q$ 的模性质）必要性的深入分析。

2. 方法论 (Methodology)

本文主要结合了两种现代代数工具来简化证明并构建新结果：

1. Zieve 判据 (Zieve's Criterion)：

   • 用于处理形如 $f(X) = X^r h(X^{(q-1)/d})$ 的多项式。
   • 该判据将 $\mathbb{F}_q$ 上的置换性验证简化为两个条件：
     1. $\gcd(r, (q-1)/d) = 1$。
     2. 诱导映射在小的乘法子群 $\mu_d$（$d$ 次单位根）上是置换。
   • 本文主要取 $d=3$，将验证简化为在 3 元群 $\mu_3 = \{1, \omega, \omega^2\}$ 上的显式计算。

2. AGW 判据 (AGW Criterion)：

   • 由 Akbary, Ghioca 和 Wang 提出，提供了一种基于“纤维分解” (fiber decomposition) 的通用框架。
   • 它将有限集上的双射分解为：纤维上的单射性 + 纤维诱导映射在商集上的双射性。
   • 本文利用 AGW 判据处理 $F(X) = f(X) + X$ 的形式，通过投影 $\pi(x) = x^s$ 将 $\mathbb{F}_q^*$ 分解为三个纤维（对应 $\mu_3$ 的三个元素），分别验证纤维内的单射性和纤维间的置换性。

3. 主要贡献 (Key Contributions)

3.1 对已有结果的简化证明

• 贡献：为 Bousalmi, Bayad 和 Derbal 提出的两类置换三项式定理（Theorems 3 & 4 in [4]）提供了简短且透明的新证明。
• 方法：系统应用 Zieve 判据（$d=3$）。
• 效果：将原本复杂的直接求值转化为在 $\mu_3$ 上的简单显式计算，证明了在特定参数条件下，诱导映射 $u \mapsto u^r h(u)^s$ 确实是 $\mu_3$ 的置换。

3.2 构建完全置换多项式 (CPP) 的通用框架

• 贡献：建立了一个针对 $q \equiv 1 \pmod 9$ 的通用 CPP 构造准则。
• 形式：针对 $f(X) = X^r c(X^s)$ 形式，其中 $s=(q-1)/3$。
• 核心定理 (Theorem 4.1)：提出了四个可验证条件 (G1-G4)：
  1. 互素与非零：$\gcd(r, s)=1, \gcd(r, 3)=1$，且 $c(u)^s=1$。
  2. 纤维单射性：在纤维 $K$ 上定义的映射 $\phi_u(z) = z(1 + \beta_u z^{r-1})$ 是单射。
  3. 良定义性：诱导值 $v(u) = (1 + \beta_u z^{r-1})^s$ 与纤维代表元 $z$ 的选择无关，且落在 $\mu_3$ 中。
  4. 纤维置换性：诱导映射 $\bar{\psi}(u) = u \cdot v(u)$ 是 $\mu_3$ 的置换。
• 特化结果 (Theorem 5.1)：当 $r \equiv 1 \pmod s$（即 $r = 1 + ks$）时，纤维映射退化为标量乘法。此时四个条件简化为两个极易验证的条件：
  • 非零条件：$\tau(u) = 1 + c(u)u^k \neq 0$。
  • 置换条件：$\bar{\psi}(u) = u \cdot \tau(u)^s$ 是 $\mu_3$ 的置换。

3.3 参数条件的尖锐性分析

• 贡献：通过具体的反例证明了 $q \equiv 1 \pmod 9$ 这一条件对于该构造方法的必要性。
• 发现：如果仅假设 $q \equiv 1 \pmod 3$ 而不满足 $q \equiv 1 \pmod 9$，即使参数满足互素条件，构造出的多项式也可能不是置换多项式（即 $F(X)$ 会失效）。

4. 主要结果 (Results)

1. 置换三项式的统一视角：

   • 证明了 Bousalmi 等人的结果本质上是 Zieve 判据在 $d=3$ 时的直接推论，无需复杂的分情况讨论。

2. 新的 CPP 族：

   • 在 $q \equiv 1 \pmod 9$ 且 $r = 1 + ks$ 的条件下，给出了构造 CPP 的显式族。
   • 示例：
     • $q=109, r=73$：构造出 $f(X) = X^{73}(X^{36} + \delta X^{36} + \dots)$ 形式的 CPP。
     • $q=163, r=163$ 和 $q=199, r=199$：验证了不同参数下的有效性。
   • 这些例子展示了如何通过选择特定的 $\delta$（满足 $\delta^2+\delta+1=0$）和 $k$ 值来生成满足条件的 CPP。

3. 反例验证：

   • $q=7$ ($7 \equiv 1 \pmod 3$但$7 \not\equiv 1 \pmod 9$)：构造的$F(X)$ 将三个不同元素映射到 0，不是置换。
   • $q=31$ ($31 \equiv 4 \pmod 9$)：构造的$F(X)$在$x=5$和$x=8$ 处取值相同，不是单射。
   • 这些反例证实了 $q \equiv 1 \pmod 9$ 是该特定构造方法成立的关键算术条件。

5. 意义与影响 (Significance)

• 理论简化：将复杂的置换多项式验证问题转化为小群（$\mu_3$）上的计算，极大地降低了验证难度，使得新结果的证明更加清晰和标准化。
• 构造工具：提出的“标量纤维特化” (Scalar Fiber Specialization) 为构造完全置换多项式提供了一套易于操作的算法。研究者只需检查简单的非零条件和置换条件即可生成新的 CPP 族。
• 边界明确：通过反例明确了构造方法的适用范围，指出了 $q \equiv 1 \pmod 9$ 这一条件的数学本质（保证了 $3|s$，进而保证$\gcd(r,3)=1$ 等关键性质），避免了在无效参数范围内进行徒劳的尝试。
• 应用潜力：由于 CPP 在密码学（如 S 盒设计）和编码理论中的重要性，本文提供的易于验证的构造族为设计具有优良非线性性质的加密组件提供了新的数学资源。

总结：本文通过巧妙结合 Zieve 判据和 AGW 判据，不仅简化了现有置换三项式的证明，还建立了一个强大的通用框架来构造有限域上的完全置换多项式，并严格界定了该方法的算术边界。