動機
一個碼可能需要含八個或十六個符號的字母表,同時又要求能對每個非零符號做除法。模八或模十六的整數算術無法提供這個性質:兩個非零元素的乘積可能為零。有限域則在所需數量的符號上給出另一種算術。在把它用作求值字母表之前,我們應當弄清楚哪些大小是可能的,以及為甚麼所選大小的域確實存在。
我們會由多項式剩餘類構造域,證明每個質數冪大小的域都存在,並確定擴域校驗中所用到的子域。這些證明只需要多項式帶餘除法和初等向量空間知識。我們回顧所需的根數事實:域上的非零 次多項式至多有 個根,因為每個根都會分離出一個一次因式,再由歸納法控制餘下的部分。
這裏的唯一性指在保持加法與乘法的同構意義下唯一。它並不選定多項式基,也不為每個符號規定標準標記。編碼器與解碼器仍然需要約定一種表示方式;這種約定不同於抽象的域大小定理。
定義
定義 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 的週期與向量空間維數隨即決定每個子域。這些結果為編碼各章所用的字母表與子域檢驗提供了依據。
練習
快速檢查
(為甚麼有限域的特徵不可能為零?)
考慮一的倍數 。
解答 · 答案
在特徵為零時,倍數 全都不同,會產生無窮多個元素。有限性迫使出現重複,從而特徵為正。
快速檢查
(為甚麼含 個元素的域恰有 個 的根?)
利用乘法群的階與 的次數。
解答
每個非零元素的乘法階整除循環群的大小 ,所以它滿足 ;零也滿足。共有 個元素,而多項式的次數正是 ,其導數為負一,所以這些就是它全部的不同根。
快速檢查
(列出含 個元素的域的所有可能的子域大小。)
把 寫成質數冪,並列出指數的因數。
解答 · 答案
這裏 。因數一、二、三和六給出大小二、四、八和六十四,每種大小恰有一個子域。十六和三十二都不是子域的大小。
快速檢查
(存在性證明是否提供了尋找 次不可約多項式的快速算法?請解釋其中的分別。)
想一想 為正能告訴實現者甚麼,又不能告訴甚麼。
解答
沒有。正的計數證明了某個不可約多項式存在。具體實現仍需要搜尋策略和不可約性檢驗,並說明其代價。配套的算術單元證明了一個具體的檢驗;這個分類論證本身既沒有提供優化的搜尋,也沒有選定表示方式。