Periodicity and Dynamical Systems of Dickson Polynomials in Finite Fields

技术摘要：有限域中狄克森多项式的周期性与动力系统

问题陈述
本文研究了第一类狄克森多项式（记作 $D_n(x, \alpha)$）在有限域 $\mathbb{F}_q$ 上的动力学性质。虽然固定多项式映射（如 $x \mapsto x^n$ 或切比雪夫多项式）的函数图已被广泛研究，但本研究将重点转向了狄克森多项式族随指数 $n$ 变化的序列行为。具体而言，作者分析了在环 $\mathbb{F}_q[x]/(x^q - x)$ 内的多项式函数序列 $[D_n(x, \alpha) \pmod{x^q - x}]_{n \ge 1}$。主要目标是确定该序列的精确周期，描述这些多项式在复合运算下的生成群的代数结构（特别是在置换情形下），并推导出新的结构恒等式与对称性。

方法论
作者结合了代数数论、有限域理论和组合分析。核心方法论依赖于刻画狄克森多项式的经典泛函方程：
$$D_n(\phi_\alpha(u), \alpha) = \phi_\alpha(u^n)$$
其中 $\phi_\alpha(u) = u + \alpha u^{-1}$。该方程建立了一个交换图表，将 $D_n(x, \alpha)$ 在 $\mathbb{F}_q$ 上的动力学与特定子集 $\mathcal{T}_\alpha \subset \mathbb{F}_{q^2}^\times$ 上的幂映射 $u \mapsto u^n$ 联系起来（其中 $\mathcal{T}_\alpha$ 定义为 $\{u \in \mathbb{F}_{q^2} \mid u^{q+1} = \alpha \text{ 或 } u \in \mathbb{F}_q^\times\}$）。

关键方法步骤包括：

1. 周期性分析： 利用递推关系 $D_n = x D_{n-1} - \alpha D_{n-2}$ 和泛函方程，作者确定了使得 $D_n(x, \alpha) \equiv x \pmod{x^q - x}$ 且 $D_{n+1}(x, \alpha) \equiv 2 \pmod{x^q - x}$ 的最小 $n$。
2. 群论映射： 在置换情形下（即 $\gcd(n, q^2-1)=1$），作者构造了一个从 $(\mathbb{Z}/\pi_q(\alpha)\mathbb{Z})^\times$ 的一个子群到狄克森多项式函数在复合运算下的群的同态，并显式地刻画了其核。
3. 系数对称性： 作者利用卢卡斯定理（Lucas' Theorem）的推广版本以及涉及二项式系数的组合恒等式，证明了 $D_n(x, \alpha)$ 系数中非平凡的对称性。
4. 算法提取： 提出了一种通过分析给定多项式的系数比例来提取参数 $\alpha$ 的算法，利用了所得的对称性质。

主要贡献与结果

• 精确周期性（定理 1.1）： 本文确定了序列 $[D_n(x, \alpha) \pmod{x^q - x}]_{n \ge 1}$ 的精确周期。

  • 若 $q$ 为奇数且 $\alpha$ 是 $\mathbb{F}_q$ 中的平方元，则周期为 $\frac{q^2-1}{2}$。
  • 否则，周期为 $q^2 - 1$。
    该结果是通过分析 $\mathcal{T}_\alpha$ 中元素的阶，并证明 $D_n(x, \alpha) \equiv 2$ 蕴含了 $n$ 相对于 $q-1$ 和 $q+1$ 的特定整除条件而得出的。

• 置换狄克森多项式的群结构（定理 1.2）： 对于 $\alpha \in \mathbb{F}_q^\times$，集合 $\mathcal{D}_\alpha = \{D_{n, \alpha}(x) \pmod{x^q-x} \mid \alpha^n = \alpha, \gcd(n, q^2-1)=1\}$ 在复合运算下构成一个群。作者证明该群同构于 $(\mathbb{Z}/\pi_q(\alpha)\mathbb{Z})^\times$ 的一个子群的商群。具体而言：

  • 若 $\alpha = 1$，该群同构于 $(\mathbb{Z}/\pi_q(1)\mathbb{Z})^\times / H_1$，其中 $H_1 \cong \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z}/2\mathbb{Z}$。
  • 若 $\alpha \neq 1$，该群同构于 $U_\alpha / H_2$，其中 $H_2 \cong \mathbb{Z}/2\mathbb{Z}$。
    这为当指数 $n$ 与 $q^2-1$ 互素时的复合动力学提供了显式描述。

• 系数对称恒等式（定理 1.3）： 作者推导出了反映狄克森多项式系数“旋转”对称性的新恒等式。

  • 对于奇数 $q$：$x^{q^2+1}(D_{q^2-1}(x^{-1}, \alpha) - 2) = (-4\alpha)^{-1}(D_{q^2-1}(x, (16\alpha)^{-1}) - 2)$。
  • 若 $\alpha$ 是平方元：$x^{\frac{q^2+1}{2}} D_{\frac{q^2-1}{2}}(x^{-1}, \alpha) = 2 D_{\frac{q^2+1}{2}}(x, (16\alpha)^{-1})$。
    这些恒等式是利用系数显式公式的组合操作和广义卢卡斯定理证明的。

• 动力学结构与部分结果： 本文定义了序列的动力学结构 $(\ell, k)$（尾部长度与周期）。虽然尾部长度已完全确定，但当 $\gcd(n, q^2-1) \neq 1$ 时，精确周期仅得到了部分刻画。作者指出，当底层幂映射的周期 $k$ 为偶数时，狄克森序列的周期可能是 $k$ 或 $k/2$，这使得区分两者的精确判据仍是一个开放性问题。

• 算法应用： 文中提出了一个算法，用于识别给定多项式 $f(x)$ 是否为狄克森多项式 $D_n(x, \alpha)$ 并恢复 $\alpha$。该方法通过使用非零系数指数的最大公约数直接确定 $\alpha$，避免了暴力搜索，从而降低了搜索空间的复杂度。

意义
本文声称其意义在于提供了一个统一的代数框架来理解狄克森多项式的迭代，将切比雪夫多项式和幂映射已知的群论机制扩展到了更广泛的狄克森族。通过确定精确的周期性和复合狄克森多项式的群结构，这项工作为理解它们的函数图提供了更深的理论基础。所推导的对称恒等式和系数提取算法提供了分析这些多项式的新工具，可能有助于研究它们在密码学和伪随机数生成中的应用，尽管本文主要侧重于理论代数结构而非具体的应用实现。这些结果弥合了固定映射的动力学与多项式族序列行为之间的鸿沟。