子空间多项式的交、和与核计算

一组基用少量向量描述一个子空间，但同一子空间可以有许多不同的基。如果想要一种与基的选择无关、还能参与代数计算的表示，可以把子空间中的每个元素都当成根。看起来这会产生一个很长的多项式；有限域的线性结构却让绝大多数项自动消失。

形式陈述

根集本身就是完整编码

设 $K=\mathbb F_q$ 、 $L=\mathbb F_{q^n}$ ， $W\subseteq L$ 是维数 $r$ 的 $K$ -子空间，允许 $r=0$ 和 $r=n$ 。定义

P_W(X)=\prod_{w\in W}(X-w). \tag{1}

它是首一线性化多项式。当 $r\ge1$ 时，形状为

P_W(X)=X^{q^r}+c_{r-1}X^{q^{r-1}}+\cdots+c_1X^q+c_0X, \qquad c_0\ne0. \tag{2}

$r=0$ 时单独写为 $P_{\{0\}}(X)=X$ ，其一次项系数为一。所有情形的普通次数为 $q^r$ ， $q$ -次数为 $r$ ；不要把两个次数混写。根全部在 $L$ 内且无重根，根集恰好是 $W$ 。因此不同子空间有不同的 $P_W$ ，而不同基若张成同一空间，构造的最终多项式必须相同。

本页的交与和使用两种不同运算：

\boxed{P_{W\cap U}=\gcd(P_W,P_U),\qquad P_{W+U}=P_{P_W(U)}\circ P_W.} \tag{3}

第一式的gcd是 $L[X]$ 中的首一普通多项式最大公因子。第二式的 $P_W(U)$ 是把子空间 $U$ 的元素代入 $P_W$ 所得的像子空间，乘法是形式复合，不做函数次数约简。这两个选择是公式的一部分。

直觉

加入一个方向，只需加一层q次幂

零子空间 $\{0\}$ 的根积是 $P_0(X)=X$ ，不是常数一。假设已构造 $P_W$ ，现在选 $v\notin W$ ，令

c=P_W(v)\ne0.

$W+Kv$ 是 $q$ 个互不相交的陪集 $W+\lambda v$ 的并。线性化性质给 $P_W(X-\lambda v)=P_W(X)-\lambda c$ ，故

\begin{aligned} P_{W+Kv}(X) &=\prod_{\lambda\in K}\bigl(P_W(X)-\lambda c\bigr)\\ &=P_W(X)^q-c^{q-1}P_W(X). \end{aligned} \tag{4}

最后一步来自 $\prod_{\lambda\in K}(Y-\lambda)=Y^q-Y$ ，再作变量缩放。所有乘方都在形式多项式环中进行； $P_W(X)^q$ 会同时把系数与幂次取 $q$ 次幂。

从 $X$ 开始，沿任意一组基逐个使用(4)，就证明(2)并给出算法：每次保持首一、 $q$ -次数增加一。新的一次项系数是 $-c^{q-1}$ 乘旧的一次项系数，始终非零。因此导数是非零常数，根没有重复。

若传入的“基”出现冗余向量，则 $c=0$ 。此时不能把(4)当成增加一维的更新，否则会得到 $P_W^q$ ，给原根平白增加重数。程序可以拒绝这份独立基声明；若合同允许输入生成集，也可以跳过该向量，但必须明确报告没有增维。

为什么交可以用普通gcd

两份根积都首一且平方自由。共同根恰好是 $W\cap U$ ，所以普通gcd的根积就是 $P_{W\cap U}$ 。实现时可用域上多项式的Euclidean除法反复取余，最后首一化，不必先列出全部共同根。

这里并没有声称普通余式的每一步都仍为首一子空间多项式；需要保持的是普通多项式gcd的正确性，最终结果才重新具有(2)的形状。

为什么和要先取像，再复合

令 $V=P_W(U)$ 。因为 $P_W$ 是 $K$ -线性映射且核为 $W$ ，它在 $U$ 上的核为 $U\cap W$ 。秩—零度公式给

\dim V=\dim U-\dim(U\cap W).

对任意 $x\in L$ ， $P_W(x)\in V$ 当且仅当存在 $u\in U$ 使 $P_W(x)=P_W(u)$ ，即 $x-u\in W$ 。所以

(P_V\circ P_W)(x)=0\quad\Longleftrightarrow\quad x\in W+U.

复合多项式首一，普通次数为

q^{\dim V}q^{\dim W}=q^{\dim(W+U)}.

它已经拥有恰好这么多不同根，因此就是 $P_{W+U}$ ，证明(3)。特别地，若 $W\subseteq U$ ，得到

P_U=P_{P_W(U)}\circ P_W. \tag{5}

这是一份有方向的右复合因子证书。不能随意交换两个因子；线性化算子的复合一般不交换。

例子与边界

两个二维空间的交是一维，和是三维

取 $L=\mathbb F_2[a]$ 、 $a^4=a+1$ ，并令 $b=a^2+a$ ，于是 $b^2=b+1$ 。考察

W=\langle1,a\rangle_{\mathbb F_2},\qquad U=\langle1,a^2\rangle_{\mathbb F_2}.

先加入 $1$ ，(4)给 $P_{\langle1\rangle}=X^2+X$ 。再加入 $a$ 时， $c=a^2+a=b$ ，所以

P_W=(X^2+X)^2+b(X^2+X) =X^4+(b+1)X^2+bX. \tag{6}

加入 $a^2$ 时， $c=a^4+a^2=b+1$ ，故

P_U=X^4+bX^2+(b+1)X. \tag{7}

两空间的共同元素为 $0,1$ ，所以gcd应为 $X^2+X$ 。也可直接相加(6)、(7)，得到 $P_W+P_U=X^2+X$ ；这个多项式又整除二者，因此确实是首一gcd。

为了算和，注意 $P_W(1)=0$ 、 $P_W(a^2)=b+1$ ，所以 $P_W(U)=\langle b+1\rangle$ ，其根积为 $X^2+(b+1)X$ 。形式复合给

P_{W+U}=P_W^2+(b+1)P_W=X^8+X^4+X^2+X. \tag{8}

它的根是 $\langle1,a,a^2\rangle$ 的八个元素。式(8)也恰是绝对迹多项式；这个三维空间确实是迹的核。

两个四元素平面的普通gcd留下共同直线；先把第二个空间送入第一个根积，再复合得到八元素的和空间。

普通lcm只收集并集，没有补上线性组合

$W\cup U$ 在主例中有 $4+4-2=6$ 个元素。因此普通 $\operatorname{lcm}(P_W,P_U)$ 的次数是6，根集只是并集；它不是次数8的 $P_{W+U}$ 。例如 $a+a^2$ 在和空间中，却不在任何一个原平面中。

线性空间的和需要加入混合线性组合，集合的并不一定对加法封闭。这个差别解释了为何“gcd算交，所以lcm算和”在这里会误导。

整个域需要保留最后的高次项

零空间与全空间分别给

P_{\{0\}}=X,\qquad P_L=X^{q^n}-X. \tag{9}

后一式是非零形式多项式，但在 $L$ 上作为函数却恒零。若过早按函数关系将它约简成零，就丢掉了首一、次数和根重数这些用于表示空间的信息。因此本页所有根积、gcd和式(3)都先保留形式多项式；只有明确转成算子时才使用上一页的低次唯一代表。

$q>2$ 时还必须保留(4)中的减号。例如一维空间 $K v$ 的根积为 $X^q-v^{q-1}X$ 。不能把特征二算例中的加号原样搬到三元底域。

推论与应用

任意线性化算子的核都能变成首一根积

给定形式线性化多项式 $\ell$ ，允许它有重复根、很高次数，甚至为零多项式。由于 $X^{q^n}-X$ 在 $L$ 中恰有全部简单根，

\boxed{P_{\ker(\ell:L\to L)}= \gcd\bigl(\ell(X),X^{q^n}-X\bigr).} \tag{10}

gcd取首一；约定 $\gcd(0,X^{q^n}-X)=X^{q^n}-X$ ，因而零算子的核为整个 $L$ 。这里的gcd会移除 $\ell$ 中多余的重数，不会因为原多项式导数为零就遗漏核元素。

例如十六元域中的 $s(X)=X^2+aX$ 已经是首一、根为 $\{0,a\}$ ，所以它本身就是核多项式。改成 $s(X)^2$ ，函数核仍相同；与 $X^{16}-X$ 做gcd会恢复 $s$ ，而不是保留二重根。

像与方程的全部解也能被编码

从一组底域基 $e_j$ 出发，计算 $\ell(e_j)$ 并消元选出像的一组基，再使用(4)，就得到 $P_{\operatorname{im}\ell}$ 。于是

\ell(x)=y\text{ 有解}\quad\Longleftrightarrow\quad P_{\operatorname{im}\ell}(y)=0. \tag{11}

这与上一页的迹伴随障碍是同一个像空间的两份表示：一份用根多项式，一份用一组线性迹等式。两边应对每个右端给出相同判断。

若已有一个解 $x_0$ ，全部解为 $x_0+W$ ，其中 $W=\ker\ell$ 。这个仿射集的首一根积是

\prod_{w\in W}(X-x_0-w) =P_W(X-x_0)=P_W(X)-P_W(x_0). \tag{12}

最后一个多项式通常带非零常数项，所以不再是线性子空间的根积；它准确表达的是一整个解纤维。主例 $s(x)=1+a$ 的解为 $1,1+a$ ，根积即 $X^2+aX+(1+a)$ 。

稀疏表示省下什么，又没有省下什么

直接展开(1)有 $q^r$ 个根因子，根清单本身就可能很长。递推(4)只保存 $r+1$ 个 $q$ -幂系数；第 $i$ 步求 $P_W(v)$ 并更新至多 $i+2$ 项，累计 $O(r^2)$ 次扩域乘加及相应Frobenius/标量幂运算。输入生成集还需独立性处理，不能把这一项隐藏掉。

算交若调用普通稠密gcd，数组长度按普通次数 $q^r$ 收费，不能因为输入很稀疏就声称所有中间运算只按 $r$ 收费。算和可先对输入基求像、消元并用稀疏递推与复合，避免枚举全部空间元素。公开小域程序同时枚举根积来交叉检查，因此它有意保留指数规模的验证步骤，不代表最快实现。

终点任务要求对十六元域全部67个二元子空间检验交与和，同时迁移到三元和四元底域，明确每一份输出是形式根积还是约简算子。

用错误空间根积建立插值译码

Gabidulin插值译码把本页的首一根积用在未知错误值的底域张成空间 $E$ 上： $P_E$ 消去所有错误方向。若实际维数为 $r\le t$ ，再左复合 $X^{q^{t-r}}$ ，便得到首一且 $q$ 次数恰为预算 $t$ 的辅助多项式。这样低于预算的错误和零错误也不会破坏固定次数的线性系统。

最后恢复消息要求在形式多项式层验证 $N=\Lambda\circ f$ ，不能提前把 $X^{q^m}-X$ 约简成零。错误空间根积的存在保证系统相容，消息的唯一性则还来自求值码的距离与次数界；不应把消息唯一性误写成辅助插值解也唯一。

参考资料

Eli Ben-Sasson、Tuvi Etzion、Ariel Gabizon、Netanel Raviv，Subspace Polynomials and Cyclic Subspace Codes，2015年v3，§II Definitions1–2、Lemmas1–3：线性化根积、简单根系数及子空间的唯一多项式表示；Lemma4的证明使用普通gcd描述交集根。本文不采用其后编码构造或距离优化结论。
Baofeng Wu、Zhuojun Liu，Linearized polynomials over finite fields revisited，2013年v2，§§2–4的线性算子与复合接口。本文逐基递推、和空间复合恒等式及解纤维公式由陪集分解和核像证明直接展开。

形式陈述 ​

根集本身就是完整编码 ​

加入一个方向，只需加一层q次幂 ​

为什么交可以用普通gcd ​

为什么和要先取像，再复合 ​

两个二维空间的交是一维，和是三维 ​

普通lcm只收集并集，没有补上线性组合 ​

整个域需要保留最后的高次项 ​

任意线性化算子的核都能变成首一根积 ​

像与方程的全部解也能被编码 ​

稀疏表示省下什么，又没有省下什么 ​

用错误空间根积建立插值译码 ​

反向链接