有限域正规基与 Frobenius 循环坐标

一个元素的所有共轭彼此不同，只说明它没有过早回到起点；这些共轭作为向量，仍可能线性相关。正规基要求再多一步：同一个元素的共轭，恰好能无重复地表示整个扩域。 找到这样的元素后，Frobenius运算就变成坐标的循环移动。

形式陈述

设 $q$ 为素数幂， $n\ge1$ ， $K=\mathbb F_q$ ， $L=\mathbb F_{q^n}$ 。记相对Frobenius为 $\sigma(x)=x^q$ 。若有序表

N_\alpha=(\alpha,\alpha^q,\ldots,\alpha^{q^{n-1}})

是 $L$ 的 $K$ -基，就称它为正规基， $\alpha$ 为关于 $K$ 的正规元素。这里的“正规”描述一组向量怎样相连，不是说矩阵与转置交换，也不是给向量加上长度或直角条件。

有限域正规基定理：对每个 $q,n$ ，这样的 $\alpha$ 都存在。无需假设特征不整除 $n$ 。

更精确地，固定一个正规元素 $\alpha$ ，令

m(T)=T^n-1\in K[T],\qquad \theta=g(\sigma)\alpha,\quad \deg g<n.

每个 $\theta\in L$ 都有唯一这样的表示，并且

\theta\text{ 正规}\quad\Longleftrightarrow\quad \gcd(g,m)=1. \tag{1}

若 $m=\prod_{P}P^{e_P}$ 是不同首一不可约因子的分解，正规元素的总数为

\boxed{q^n\prod_{P\mid T^n-1}\left(1-q^{-\deg P}\right).} \tag{2}

乘积中的每个不同因子只出现一次；即使 $T^n-1$ 有重因子，公式也照常有效。

直觉

一个算子，能否只靠一个起始向量跑完整个空间

通常选基可以自由挑 $n$ 个向量。正规基只允许挑第一个，后面都由 $\sigma$ 生成。因此问题转成： $\sigma$ 是否有一个循环向量，其前 $n$ 个轨道向量线性无关？

若已经找到它，写

x=c_0\alpha+c_1\sigma\alpha+\cdots+c_{n-1}\sigma^{n-1}\alpha, \qquad c_i\in K.

因为 $\sigma$ 固定全部 $c_i$ ，且 $\sigma^n\alpha=\alpha$ ，所以

[\sigma x]_{N_\alpha}=(c_{n-1},c_0,\ldots,c_{n-2})^t. \tag{3}

这里省下的是Frobenius的算术；一般域乘法并没有因此变成逐坐标相乘。换基本身也要计算，不能只看式(3)就宣称全部扩域运算都是常数代价。

存在性：先证明算子没有更短的关系

显然 $\sigma^n=I$ ，所以算子极小多项式 $m_\sigma$ 整除 $T^n-1$ 。反设存在一个次数小于 $n$ 的非零关系

c_0I+c_1\sigma+\cdots+c_d\sigma^d=0, \qquad d<n.

它表示普通多项式

Q(X)=c_0X+c_1X^q+\cdots+c_dX^{q^d}

在 $L$ 的全部 $q^n$ 个元素上为零。不同的 $q$ 次幂有不同次数，所以 $Q$ 不是零多项式；它的次数至多 $q^{n-1}$ ，却有 $q^n$ 个根，违背域上非零多项式的根数界。因此

m_\sigma(T)=T^n-1. \tag{4}

现在实际使用有理标准形： $n$ 维算子的各不变因子次数之和为 $n$ ，最大不变因子就是极小多项式。式(4)的次数已经是 $n$ ，所以只能有一个伴随块。该块的首个循环向量便给所求正规元素。论证没有对 $T^n-1$ 求不同特征值，更没有对 $n$ 做除法；特征整除次数时也不会失效。

全部正规元素为什么恰好对应单位

映射

K[T]/(m)\longrightarrow L,\qquad [g]\longmapsto g(\sigma)\alpha

是 $K[T]$ -模同构：正规基保证它在次数小于 $n$ 的代表元上是一一对应， $T$ 的作用正是 $\sigma$ 。从 $\theta=g(\sigma)\alpha$ 出发能生成整个模，当且仅当 $[g]$ 生成整个商环作为自身的模，也就是 $[g]$ 为单位。多项式Bézout恒等式又把可逆性变成 $\gcd(g,m)=1$ ，证明(1)。

用环的中国剩余分解，商环分成各个 $K[T]/(P^{e_P})$ 。若 $d=\deg P$ ，这一分量有 $q^{e_Pd}$ 个元素；非单位恰是可被 $P$ 整除的类，共 $q^{(e_P-1)d}$ 个。各分量的单位数相乘，便得到(2)。重因子影响分量大小，却不需要把同一个比例因子重复乘 $e_P$ 次。

例子与边界

同一个十六元域中的三个不同问题

取 $L=\mathbb F_2[a]$ ， $a^4=a+1$ 。 $a$ 的Frobenius轨道为

a,\quad a^2,\quad a+1,\quad a^2+1.

四项互异，但总和为零，故不是正规基。另一方面， $a$ 的乘法阶为15，是 $L^\times$ 的生成元，所以它既生成整个域，又生成乘法群。这两种“生成”都没有保证共轭向量独立。

改取 $\alpha=a^3$ 。四个共轭是

a^3,\quad a^3+a^2,\quad1+a+a^2+a^3,\quad a+a^3.

把它们作为列写在幂基 $(1,a,a^2,a^3)$ 下，得到

C=\begin{pmatrix} 0&0&1&0\\ 0&0&1&1\\ 0&1&1&0\\ 1&1&1&1 \end{pmatrix},\qquad \det C=1\in\mathbb F_2. \tag{5}

所以 $\alpha$ 正规。但它的乘法阶只有5，因为 $a$ 的阶为15， $a^3$ 的阶为 $15/\gcd(15,3)=5$ 。正规不保证乘法本原，乘法本原也不保证正规。 正规元素确实生成整个域：其共轭必须有 $n$ 项互异，因而域生成次数为 $n$ ；反向蕴含被 $a$ 否定。

四个共轭互异的a只有三维张成；a三次方的共轭构成四维基，Frobenius在正规坐标中只作循环移动。

非零迹何时足够

若 $\theta$ 正规，则

\operatorname{Tr}_{L/K}(\theta)=\sum_{i=0}^{n-1}\sigma^i\theta\ne0, \tag{6}

否则就是一份所有系数为一的非平凡基向量关系。即使 $n=0$ 于底域，系数表 $(1,\ldots,1)$ 仍不是零表，不能把两件事混为一谈。

通常(6)只是必要条件。例如 $\mathbb F_8/\mathbb F_2$ 中， $\operatorname{Tr}(1)=1+1+1=1$ ，但 $1$ 的三个共轭全部相同，不正规。此时 $T^3-1=(T-1)(T^2+T+1)$ ，正规元素总数为 $8(1-1/2)(1-1/4)=3$ 。

若特征为 $p$ 且 $n=p^s$ ，则有更强的充要判据：

\theta\text{ 正规}\quad\Longleftrightarrow\quad\operatorname{Tr}_{L/K}(\theta)\ne0. \tag{7}

因为 $T^n-1=(T-1)^n$ ，(1)只要求 $g(1)\ne0$ 。又因迹对Frobenius不变， $\operatorname{Tr}(g(\sigma)\alpha)=g(1)\operatorname{Tr}(\alpha)$ ，而后一个固定迹非零，所以得到(7)。这包括 $n=1$ 。

十六元域的绝对次数是4，因此恰有 $16(1-1/2)=8$ 个正规元素；它们正是幂基中 $a^3$ 系数为一的八个元素。迹为零的 $a$ 被排除，迹为一的 $a^3$ 被接受。

改底域，答案也会变

在同一个 $L$ 中取 $b=a^2+a$ ，则 $b^2=b+1$ ， $K'=\{0,1,b,b+1\}\cong\mathbb F_4$ 。现在相对Frobenius是 $x\mapsto x^4$ ，扩张次数为二。

原来绝对不正规的 $a$ 现在满足 $a+a^4=1\ne0$ ，所以 $(a,a^4)$ 是 $K'$ -正规基。这里次数二仍为特征的幂；正规元素恰为相对迹非零者，也恰为 $L\setminus K'$ 的12个元素。底域不写清，“这个元素正规吗”就没有确定答案。

推论与应用

正规基的迹对偶也按同一个方向循环

设 $N_\alpha^*=(\beta_0,\ldots,\beta_{n-1})$ 是迹对偶基。迹的Frobenius不变性给

\operatorname{Tr}\bigl((\sigma^i\alpha)(\sigma\beta_j)\bigr) =\operatorname{Tr}\bigl((\sigma^{i-1}\alpha)\beta_j\bigr) =\delta_{i-1,j},

下标均模 $n$ 。对偶向量的唯一性因此给 $\sigma\beta_j=\beta_{j+1}$ 。整张对偶表也由一个元素 $\beta_0$ 生成，是正规基。这里证明的是“对偶仍正规”，并没有证明 $\beta_0=\alpha$ ；自对偶性是额外条件。

正规基使Frobenius结构简单，迹对偶则把任意输入读成这组坐标。下一页的线性化多项式把这两种表示进一步接成任意线性算子的系数与矩阵。

如何交付一份可复查的正规基

给出域的不可约定义多项式、底域、候选 $\alpha$ 、全部共轭的幂基坐标及非零行列式，便足以认证这一个正规基。对全部正规元素计数时，再提交 $T^n-1$ 的不同不可约因子，不能只试几个随机元素后猜总数。

朴素构造 $n$ 个共轭并消元，每个候选需要 $n$ 次相对Frobenius求值及 $O(n^3)$ 次底域算术；全部枚举有 $q^n$ 个候选，是指数规模。存在性证明不把这种枚举伪装成关于 $n\log q$ 的高效算法。若已经使用正规坐标，式(3)只需重新排列 $n$ 个坐标；是否能用循环存储省去实际搬动，则是表示层的另一个选择。

终点任务要求核对(5)、八个绝对正规元素与十二个相对正规元素，并将同一批数据接入算子和子空间证书。

参考资料

Keith Conrad，Linear Independence of Characters，§3，尤其Theorem3.7的循环扩张正规基证明。本文在有限域情形用普通多项式根数界证明算子独立，再调用已有有理标准形；计数及正特征迹判据由商环单位直接推导。
Baofeng Wu、Zhuojun Liu，Linearized polynomials over finite fields revisited，2013年v2，§1的正规/对偶基记号及§§2–4的算子表示背景。本文不声称构造最优正规基或提供一般快速乘法复杂度。

形式陈述 ​

一个算子，能否只靠一个起始向量跑完整个空间 ​

存在性：先证明算子没有更短的关系 ​

全部正规元素为什么恰好对应单位 ​

同一个十六元域中的三个不同问题 ​

非零迹何时足够 ​

改底域，答案也会变 ​

正规基的迹对偶也按同一个方向循环 ​

如何交付一份可复查的正规基 ​

反向链接