动机
一个码可能需要含八个或十六个符号的字母表,同时又要求能对每个非零符号做除法。模八或模十六的整数算术无法提供这一性质:两个非零元素的乘积可能为零。有限域则在所需数量的符号上给出另一种算术。在把它用作求值字母表之前,我们应当弄清哪些大小是可能的,以及为什么所选大小的域确实存在。
我们将由多项式剩余类构造域,证明每个素数幂大小的域都存在,并确定扩域校验中所用到的子域。这些证明只需要多项式带余除法和初等向量空间知识。我们回顾所需的根数事实:域上的非零 次多项式至多有 个根,因为每个根都会分离出一个一次因式,再由归纳法控制余下的部分。
这里的唯一性指在保持加法与乘法的同构意义下唯一。它并不选定多项式基,也不为每个符号规定标准标记。编码器与解码器仍然需要约定一种表示方式;这种约定不同于抽象的域大小定理。
定义
定义 14.1.1
(域与特征)
域要求零与一不同,并且每个非零元素都可逆。其特征是满足 的最小正整数 (若存在)。有限域必定具有正特征。在特征为 时,一的倍数构成 的一个拷贝。
定义 14.1.2
(多项式商)
对于首一多项式 ,设其次数为 ,商 由多项式剩余类构成。由带余除法,每个剩余类都有唯一的次数小于 的代表元。 的剩余类记作 。此时商只是一个环;仅当 不可约时它才是域。
定义 14.1.3
(极小多项式)
对于有限域的一个元素,其在素域上的极小多项式是以该元素为根的次数最小的正次数首一多项式。它是不可约的,因为若它可分解,则在域中某个更低次的因式也会以该元素为根。多项式除法表明,它整除所有以该元素为根的其他多项式。
定义 14.1.4
(Frobenius 多项式、子域与 Frobenius 映射)
对于正整数 ,记 。在特征 下其导数为负一,所以它没有重复的不可约因式。子域与较大的域共享零和一,并对其运算封闭。在大小为 的域中,映射 称为 Frobenius 映射。
定理/命题
定理 14.1.5
(多项式商与可能的域大小)
每个有限域的大小都是 ,其中 为素数, 为整数。 上由首一 次多项式所作的商恰在该多项式不可约时是域;此时其大小为 。
定理 14.1.6
(存在性、唯一性与非零元的循环性)
对每个素数 和每个 ,大小为 的域存在,且在同构意义下唯一。每个有限域的乘法群都是循环群。
定理 14.1.7
(Frobenius 映射与子域)
在大小为 的域 上,Frobenius 映射是阶恰为 的自同构。对 的每个正因数 ,恰有一个含 个元素的子域,即 在 中的根所成的集合。不存在其他大小的子域。
证明思路或证明
构造算术并限定可能的大小
证明
(素特征与不可约判别)
若有限域的特征是合数,比如 ,其中 ,则非零元素 的乘积为零,与域的性质矛盾。因此其特征是素数。把该域看作其素子域上的有限维向量空间,则它含 个元素,每组 个系数对应一个元素。基的存在性可通过反复添加线性无关的元素直至有限集生成整个空间而得到。
若 不可约,则每个次数小于 的非零代表元 与 的最大公因式为一。多项式的 Euclid 算法给出 ,所以 的剩余类就是其逆元。反之,若 ,两个因式的次数都为正且小于 ,则它们的剩余类非零而乘积为零。因此商恰在不可约情形下是域。唯一代表元给出其基数 。
有限乘法子群有生成元
证明
(单位群的循环性与 Frobenius 的精确周期)
设 为有限域的非零元素集合。对于出现在某个元素阶中的每个素数,取整除这类阶的该素数的最大幂。对选定元素取适当的幂,便得到恰好具有该素数幂阶的元素。把这些元素相乘,便得到阶为 的元素, 是所有元素阶的最小公倍数:各因子可交换,且它们的阶两两互素。为验证阶的结论,把乘积提升到 除以某一素数幂因子所得的幂;其余各分量都化为单位元,这迫使该素数幂整除任何使乘积为单位元的指数。
的每个元素都满足 。根数上界给出 ,而一个阶为 的元素本身就在 中有 个不同的幂。因此 ,这些幂就是整个群。该证明用到了交换性和域的根数上界;并非每个有限群都是循环群。
由此可知,大小为 的域的每个元素都满足 。由特征 下的二项式恒等式,Frobenius 映射保持加法,也保持乘法,并且是单射,因为域中不存在满足 的非零元素。有限性使它成为满射。它的 次幂是恒等映射。若对某个 ,它的 次幂是恒等映射,则全部 个元素都是更低次多项式 的根,这不可能。因此其阶恰为 。
根数上界是真正需要域的一步,下面的环说明了这一点。
反例模式
有限交换环的单位群可以不是循环群
断言:每个有限交换环的单位群都是循环群。在 中,单位是 ,并且
每个单位的阶至多为二,所以没有阶为四的单位,该群不是循环群。上面的证明恰在一行失效: 在模八下有四个根 ,多于其次数,因为 表明存在零因子。此时各阶的最小公倍数 小于 。正确的命题就是已证明的那个:域的非零元素的有限子群是循环群。
通过计数不可约多项式证明存在性
证明
(每个次数都有不可约多项式)
设 为任一 次首一不可约多项式,并使用由它已构造的域商。其元素 在 上生成该域。因此 当且仅当 整除 :若 Frobenius 固定 ,则它固定 的每个多项式,从而固定整个域;再把 对其精确周期 取模即可。多项式除法现在表明
把 分解为 上的首一不可约因式之积。这种分解的存在性来自把可约多项式反复分解为更低次因式;Euclid 算法给出通常的唯一性。由于 没有重复因式,它恰好是所有次数整除 的首一不可约多项式之积。
令 为 次首一不可约多项式的个数。比较次数得到 ,特别地 。当 时,每个真正因数至多为 ,所以
最后一个不等式来自有限几何级数求和:对 ,该和小于 。一次的情形由 立即可得。因此每个正次数都存在不可约多项式,其商便构造出所需的域。为得到存在性,我们并未假设任何代数闭的外围域。
证明透视
计数论证在哪里用到哪个事实
整个计数由两个事实支撑。第一, 的导数为 ,所以它没有重复的不可约因式;这把整除关系变成精确的乘积,使次数恒等式 成为等式而非不等式。第二,等价关系 用到的是由 本身构造的域上 Frobenius 的精确周期。该域的大小为 ,其中 是手头已有多项式的次数,所以并没有预先假设关于大小 的任何事情,论证不是循环的。
不明显的一步是用 粗略地控制未知的因数项。 的每个真因数至多为 ,所以被减去的项至多构成一个止于 的几何级数,它小于 。 为正便完成论证:存在一个 次不可约多项式,而已证明的商判别把它变成大小为 的域。唯一性是另一步,接下来通过在域中分裂 来证明。
识别域及其子域
证明
(唯一性与子域的分类)
设 的大小都是 。 的乘法生成元 生成整个域,所以它在 上的极小多项式次数为 且整除 。多项式 在 中分裂为其 个不同的根,因为 的每个元素都是根。作为 的极小多项式的那个因式因此在 中有一个根 。求值把 映到 ,给出由 次商到 的单射域映射。有限大小相等使它成为同构。
对于 ,不可约因式的刻画表明 。因此 的全部 个不同的根都在 中。其根集由 Frobenius 恒等式对加法、减法与乘法封闭,对非零根的求逆也封闭。它是大小为 的子域。
反之,任何子域 的大小为 ,而 在 上的向量空间基给出 ,所以 。 的每个元素都是 的根。 中恰有 个这样的根,所以它们就是 的全部元素,这就证明了每个可能大小的子域唯一。
概念视角结构
子域就是 Frobenius 幂的不动点集
的每个自同构都是 的幂。取一个乘法生成元 ,其极小多项式 的次数为 。自同构 固定 ,所以 是 的根。元素 是 个互异的根,因为若有两者相同, 的某个较小正幂就会固定 ,从而固定 。因此 ,即 。自同构构成 阶循环群,而大小为 的子域就是 的不动点集:子域与子群 一一对应。
例题详解
例题 14.1.8
(用域算术处理四个符号)
在 上,多项式 没有根,因此不可约。其商含符号 ,满足 和 。因此 。平方运算交换 与 ,并固定零与一,所以 Frobenius 的阶为二。模四的整数算术中,二是非零的零因子,所以它不能替代这个字母表。
例题 14.1.9
(计数小次数的二元不可约多项式)
有两个首一一次不可约多项式,所以 。次数恒等式给出 ,故 ;以及 ,故 。在四次时,真因数是一和二,所以 ,从而 。这些计数针对的是首一不可约多项式,而不是带标记的域乘法表的数目,也不是域元素的个数。
例题 14.1.10
(十六个符号中可见的四元子域)
取 。该模多项式没有一次根,且不被唯一的二元不可约二次式 整除;除以它的余式为一。因此它不可约。令 。由 得 ,所以 是四元域的一个拷贝,并且等于 在 中的根集。
可能的子域大小为二、四和十六,对应因数一、二和四。相比之下,大小为八的域只有其二元素素子域和它自身,因为三除一以外没有真因数。八元域中一个含四个元素的子集,不能仅仅因为其基数看上去合理就成为子域。
常见错误
常见错误
(素数幂是大小,不是整数模数)
大小为 的域的符号是在 中取 个系数的多项式剩余类。其特征是 ,而不是 。当 时使用模 的整数会引入零因子,并使需要域的除法、根数上界与译码论证失效。
常见错误
(不可约模多项式不一定给出本原元)
把域作为代数来生成,不同于生成其非零乘法群。在 中,模多项式不可约,因为负一在 中不是平方。元素 与素域一起生成整个域,但 ,,所以它的乘法阶是四而不是八。因此,不可约的 次模多项式并不自动使其剩余变量成为本原乘法元素。要求具有指定阶的元素的 BCH 构造必须验证这一额外性质。上面的唯一性证明有意选择了乘法生成元(其存在性已经确立),而没有假设每个域生成元都具有该阶。
抽象分类与具体标记之间的同一区别,也出现在同构上。
常见错误
(在同构意义下唯一不等于同构唯一)
同构不一定唯一。在四元素的例子中,把 送到 或 给出两个保持素域的由该域到自身的同构。两者都保持算术。选定具体的基和比特表示,固定了实际计算所用的约定,而分类定理只提供抽象的可能性。
总结
有限域的大小恰为素数幂。不可约多项式的商构造出它们,因式计数论证证明每个次数下都存在不可约多项式,Frobenius 多项式的根则证明在同构意义下的唯一性。Frobenius 的周期与向量空间维数随即决定每个子域。这些结果为编码各章所用的字母表与子域检验提供了依据。
练习
快速检查
(为什么有限域的特征不可能为零?)
考虑一的倍数 。
解答 · 答案
在特征为零时,倍数 全都不同,会产生无穷多个元素。有限性迫使出现重复,从而特征为正。
快速检查
(为什么含 个元素的域恰有 个 的根?)
利用乘法群的阶与 的次数。
解答
每个非零元素的乘法阶整除循环群的大小 ,所以它满足 ;零也满足。共有 个元素,而多项式的次数正是 ,其导数为负一,所以这些就是它全部的不同根。
快速检查
(列出含 个元素的域的所有可能的子域大小。)
把 写成素数幂,并列出指数的因数。
解答 · 答案
这里 。因数一、二、三和六给出大小二、四、八和六十四,每种大小恰有一个子域。十六和三十二都不是子域的大小。
快速检查
(存在性证明是否提供了寻找 次不可约多项式的快速算法?请解释其中的区别。)
想一想 为正能告诉实现者什么,又不能告诉什么。
解答
没有。正的计数证明了某个不可约多项式存在。具体实现仍需要搜索策略和不可约性检验,并说明其代价。配套的算术单元证明了一个具体的检验;这个分类论证本身既没有提供优化的搜索,也没有选定表示方式。