线性化多项式与有限域算子代数

为什么这么稀疏的幂次仍足够 ​

普通多项式可以有很多项，线性化多项式只保留 $1,q,q^2,\dots$ 次幂。但每个系数 $a_i$ 有 $n$ 个底域坐标，$n$ 项恰好提供 $n^2$ 个 $K$-参数，与一个 $n\times n$ 矩阵相同。

参数数目相同还不够，必须证明没有两个系数表表示同一个算子。若次数小于 $q^n$ 的非零多项式在全部 $q^n$ 个域元素上为零，就违反根数界。因此次数至多 $q^{n-1}$ 的不同线性化多项式给不同函数。式(3)证明满射，根数界证明单射，两边合起来才得到(2)。

Moore矩阵检测的是底域独立性 ​

对 $r$ 个元素 $v_0,\dots ,v_{r-1}\in L$，$1\le r\le n$，定义

这个Moore矩阵在 $L$ 上可逆，当且仅当 $v_j$ 在 $K$ 上线性无关。若有底域线性关系，对其各次Frobenius作用，便得到同一个列关系。反之，矩阵奇异给非零行系数 $c_i\in L$，使 $\sum _i{c}_i{v}_j^{q^i}=0$。相应线性化多项式于是消去整个 $K$-张成空间。若 $v_j$ 独立，这个空间有 $q^r$ 个元素，但该非零多项式次数至多 $q^{r-1}$，矛盾。

要特别留意两个域：矩阵行列式在 $L$ 中算，所检测的向量关系却在 $K$ 中取系数。若把后者也换成 $L$-线性无关，那么 $L$ 作为自身的一维空间根本放不下两个独立元素。

Dickson矩阵与普通坐标矩阵怎样对齐 ​

固定基 $E$，令 $A$ 是 $\ell$ 的 $K$-坐标矩阵，列 $j$ 为 $[\ell (e_j){]}_E$。把缺少的系数补零至 $a_0,\dots ,a_{n-1}$，定义

系数下标 $j-i$ 模 $n$。对 $v(x)=(x,x^q,\dots ,x^{q^{n-1}}{)}^t$，逐行展开有

对每个基向量代入，左侧也等于 $B[\ell (e_j){]}_E$，所以

$B$ 由(5)可逆。于是 $\det D_{\ell }=\det A\in K$，且 ${\mathrm{rank}}_L{D}_{\ell }={\mathrm{rank}}_{K}A$。最后一个等式也需要说明扩域不会改变底域矩阵的秩：底域上的可逆消元理路行化简Row reduction用初等行变换把矩阵化为阶梯形以求解线性方程组和判定秩。已经把 $A$ 化成同一个单位块与零块，放到 $L$ 中这些消元仍可逆。

十六元域中一份双重可逆证书 ​

仍取 $a^4=a+1$，底域为 ${\mathbb{F}}_2$，幂基为 $(1,a,a^2,a^3)$。考虑

它的普通坐标矩阵与Dickson矩阵分别为

二者行列式均为一。式(7)说明它们认证同一个可逆算子，虽然一个在底域中、一个在扩域中。

复合逆为

把(9)代入 $\ell$，并使用 $x^{16}=x$，可以验得 $\ell (m(x))=x$；反向复合也为恒等。矩阵逆给出的基向量像，代入(4)，会恢复相同系数。这里只得到 $L$ 上的函数逆，形式多项式的复合不等于一阶多项式 $X$。

普通乘法与复合次序都不能混用 ​

在普通多项式环理路多项式环Polynomial ring系数来自给定环、以形式不定元构造的多项式集合。里，$X\cdot X=X^2$；但作为算子，恒等映射与自身复合仍是 $X$。更明显地，在特征二，$X$ 与 $X^2$ 都线性化，普通积 $X^3$ 却不一定保持加法。

复合通常不交换。设 $F(X)=X^q$、$M_a(X)=aX$，则

当 $a\notin K$ 时不同。一般地，若 $\ell =\sum _i{a}_i{X}^{q^i}$、$m=\sum _j{b}_j{X}^{q^j}$，则

在 $L$ 上作为函数使用时，把 $i+j$ 模 $n$ 汇总系数；作为形式多项式时则保留原次数。也正由(10)有 $D_{\ell \circ m}=D_{\ell }{D}_m$，次序与“先 $m$、后 $\ell$”一致。

非零形式多项式也可能是零算子 ​

$X^{q^n}-X$ 是非零形式多项式，却在 $L$ 上处处为零。式(2)的唯一性所以必须限定 $q$-次数小于 $n$。高次表达按 $x^{q^n}=x$ 约简以后才得到唯一系数表，不能从原表达“写了非零项”推断算子非零。

即使保留唯一低次代表，非零算子也未必可逆。下面的 $X^2+aX$ 有两个核元素，它与(8)仅差一个幂次，性质却不同。

迹伴随把“有没有解”变成可检查的障碍 ​

由迹配对非退化，对每个 $K$-线性 $\ell$，存在唯一 ${\ell }^{†}$ 满足

取 $j\equiv -i(\mathrm{mod}n)$、$0\le j<n$，利用 $T(u^{q^j})=T(u)$，得到

因此伴随的 $X^{q^j}$ 系数是 $a_i^{q^j}$。尤其 $i=0$ 留下 $a_{0}X$。这是相对于迹配对的伴随；一般基的坐标矩阵并不直接取转置，而应结合该基的Gram矩阵。

若 $z\in \ker {\ell }^{†}$，(11)给 $T(z\ell (x))=0$。故 $\mathrm{im}\ell \subseteq (\ker {\ell }^{†}{)}^{\perp }$。若 $G$ 为迹配对在同一基下的Gram矩阵，伴随矩阵为 $G^{-1}{A}^{t}G$，从而秩相同；右侧维数为 $n-\dim \ker {\ell }^{†}=\mathrm{rank}\ell$，所以包含实际为相等。于是

只需检查伴随核的一组 $K$-基。若找到一个解 $x_0$，全部解就是 $x_0+\ker \ell$；核维数为 $d$ 时恰有 $q^d$ 个解。

一份失败与一份完整解集 ​

在十六元域取 $s(X)=X^2+aX$。因 $s(X)=X(X+a)$，有 $\ker s=\{0,a\}$。伴随为

记非零伴随核元素为 $z_0$。$T(z_0)=1$，所以 $s(x)=1$ 无解；这是一份具体的迹障碍，不是求解器没找到候选。

另一方面，$s(1)=1+a$，故 $s(x)=1+a$ 的全部解为 $\{1,1+a\}$。核有两个元素，任何一个成功右端都必须有两个原像，不能因为先找到 $1$ 就宣布唯一。

实现与成本 ​

得到基和迹对偶后，(4)需要 $O(n^2)$ 次扩域乘加及相应Frobenius幂；(10)朴素复合也有 $n^2$ 对系数。构造坐标矩阵再做消元需 $O(n^3)$ 次底域算术，可给核、像及逆；这与在全部 $q^n$ 个域元素上试值是不同规模的算法。域元素的位表示、底域算术和Frobenius的实现成本另计。

子空间多项式理路子空间多项式的交、和与核计算Subspace polynomial calculus · Finite-field subspace annihilator polynomial以首一线性化根积唯一编码有限域子空间，逐基递推构造，再用普通gcd算交、复合算和，并提取线性算子的核与像。下一步将核和像本身编码为稀疏根积，给交、和及全解纤维的另一种精确证书。终点任务要求同时交出(8)、(9)、伴随核和不可解右端，避免只检验一种表示。