#9 有限体

今回は、有限体の基礎的な事項を確認する。 いくつかの定理の証明を省略しているが、気になる方は代数学の教科書（書名に「ガロア理論」が含まれるものを読むと良いだろう）を参照されたい。

有限体ことはじめ

体(たい)

体(たい) (field) は、ざっくり言うと四則演算ができる数の体系である。 より具体的に言うと、加法 \(+\) と乗法 \(\times\) が定まった集合 \(K\) が体であるとは、

1. 加法 \(+\) について、 \(K\) が可換群となる。つまり、
   1. 結合法則：任意の \(a,b,c\in K\) について \((a+b)+c=a+(b+c)\).
   2. 交換法則：任意の \(a,b\in K\) について \(a+b=b+a\).
   3. 単位元：加法の単位元 \(0\in K\) があって、任意の \(a\in K\) について \(a+0=0+a=a\).
   4. 逆元：任意の \(a\in K\) に対してある \(b\in K\) が存在し、 \(a+b=b+a=0\). この \(b\) は通常 \(-a\) と表記される。
2. 乗法 \(\times\) について、 \(K\) が可換モノイドとなる。つまり、
   1. 結合法則：任意の \(a,b,c\) について \((a b) c=a (b c)\).
   2. 交換法則：任意の \(a,b\in K\) について \(a b=b a\).
   3. 単位元：乗法の単位元 \(1\in K\) があって、任意の \(a\in K\) について \(a\cdot 1=1\cdot a=a\).
3. 乗法 \(\times\) について、 \(0\) 以外の元が逆元（逆数）を持つ。\(a\) の逆元は \(a^{-1}\) や \(1/a\) と表記される。
4. \(1\ne 0\).
5. 分配法則：任意の \(a,b,c\in K\) に対して、 \(a(b+c)=ab+ac\), \((a+b)c=ac+bc\).

が成り立つことを言う。

体について標数 (characteristic) と呼ばれる整数が定まる。 さっき紹介した \(\mathbb{F}_2\) や \(\mathbb{F}_3\) は、 1 を何回か足すと 0 になってしまう。 \(\mathbb{F}_2\) においては \(1+1=0\) だし、 \(\mathbb{F}_3\) においては \(1+1+1=0\) となる。 体 \(K\) において 1 を \(n\) 回足した時にはじめて \(0\) となった場合、体 \(K\) の標数は \(n\) であるという。 1 を何回足しても 0 とならない場合（そのような正の自然数 \(n\) が存在しない場合）は、その体の標数は 0 であるという。

例えば、\(\mathbb{F}_2\) の標数は 2 で、\(\mathbb{F}_3\) の標数は 3 である。 \(\mathbb{F}_5\) と \(\mathbb{F}_5(\sqrt{2})\) の標数はいずれも 5 である。 \(\mathbb{Q}\) や \(\mathbb{R}\) の標数は 0 である。

体の基礎となる集合が有限個の場合、特に有限体という。 有限体でない体を無限体という。 先の例では、 \(\mathbb{F}_2\), \(\mathbb{F}_3\), \(\mathbb{F}_5\), \(\mathbb{F}_5(\sqrt{2})\) が有限体である。

有限体ならば標数は正だが、標数が正だからといって有限体とは限らない。 有限体上の有理関数体 \(\mathbb{F}_p(x)\) や、有限体の代数閉包 \(\overline{\mathbb{F}_p}\) は無限体である。

群(ぐん)

群(ぐん)は、二項演算（ここでは中点 \(\cdot\) で書く）が定義された集合であって、次の性質を満たすもののことである。

1. 結合則：任意の \(x,y,z\) に対して、 \((x\cdot y)\cdot z=x\cdot(y\cdot z)\).
2. 単位元の存在：ある元 \(e\) が存在して、任意の \(x\) に対して \(e\cdot x=x\cdot e=x\) を満たす。 このような元 \(e\) は存在すればただ一つであり、単位元と呼ばれる。
3. 逆元の存在：各 \(x\) に対して、ある \(y\) が存在して、 \(x\cdot y=y\cdot x=e\) となる。 それぞれの \(x\) に対して、このような \(y\) は存在すればただ一つであり、 \(x^{-1}\) と表記される。

群の例は色々ある。

集合として有限集合な群は、有限群と呼ばれる。 \(\mathbb{Z}/m\mathbb{Z}\) は有限群であるし、有限体 \(K\) を加法について見るとこれは有限群である。 有限体 \(K\) の乗法群も有限群である。

群 \(G\) の元の個数を位数といい、集合の元の個数と同じ \(\#G\) で表記する。 群が無限個の元からなる場合は位数が無限であるという。 \(\mathbb{Z}/m\mathbb{Z}\) は位数 \(m\) の有限群である。

演算が可換な群は可換群と呼ばれる。 \(\mathbb{Z}\) や \(\mathbb{Z}/m\mathbb{Z}\) は可換群である。 体の加法と乗法は可換なので、 \(K\) と \(K^\times\) はそれぞれ可換群である。 あみだくじの例では \(n\le 2\) の場合は可換群だが、 \(n\ge 3\) の場合は非可換群となる。

群 \(G\) の部分集合 \(H\) が、 \(G\) と同じ演算について群をなす場合、 \(H\) は \(G\) の部分群であるという。 「同じ演算について」という部分がポイントである。 体 \(K\) について、 \(K\) と \(K^\times\) はどちらも群となり、 \(K^\times=K\setminus\{0\}\) は \(K\) の部分集合だが、 \(K\) と \(K^\times\) では考えている演算が違うため、 \(K^\times\) は \(K\) の部分群ではない。

群 \(G\) について、適当な \(a\in G\) を使うと \(G\) の任意の元が \(a\) の冪(べき) \(a^i\) として書けてしまう、つまり \(G=\{\ldots,a^{-2},a^{-1},e,a,a^2,\ldots\}\) が成り立つ、という状況がある。 このような \(a\) は \(G\) の生成元であるといい、一個の元で生成される群を巡回群と呼ぶ。 群の結合法則より、巡回群は可換群である。

群 \(G\) の元 \(a\) について、 \(\{a^i\mid i\in\mathbb{Z}\}=\{\ldots,a^{-2},a^{-1},e,a,a^2,\ldots\}\) という集合を考えると、これは \(G\) の部分群となる。 これを \(a\) の生成する巡回群と呼び、 \(\langle a\rangle\) と表記する。 \(\langle a\rangle\) の位数を、元 \(a\) の位数と呼ぶ。

素体

いくつかの体に関しては、 \(\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}\) という包含関係が成り立つ（この際、加法、乗法は同じものを使う）。 このような包含関係の中で最小のものを素体 (prime field) と呼ぶ。

有理数体 \(\mathbb{Q}\) は、素体である。 なぜなら、任意の有理数は 1 と四則演算を使って作り出すことができる（例：\(3/4=(1+1+1)/(1+1+1+1)\))）。 よって、 \(\mathbb{Q}\) からいくつか元を取り除いて \(\mathbb{Q}\) よりも小さい体を作ることはできない。

素数 \(p\) について、 \(p\) 個の元 \(\{0,1,\ldots,p-1\}\) からなる有限体 \(\mathbb{F}_p\) も、素体である。 標数 \(p\) の体は必ず \(\mathbb{F}_p\) を素体として含む。

素体は、標数ごとにただ1つ存在する。 \(\mathbb{Q}\) は標数 0 の素体であり、標数 0 の体は必ず \(\mathbb{Q}\) を部分体として含む。

代数拡大

体 \(K\) を固定して考えると、 \(K\) 上のある種の代数方程式は \(K\) 上に根を持たない。

例えば、 \(\mathbb{R}\) 上の方程式 \(x^2+1=0\) は実根を持たないし、 \(\mathbb{Q}\) 上の代数方程式 \(x^2-2=0\) は有理数根を持たない。 \(\mathbb{F}_2\) 上の多項式 \(x^2+x+1=0\) は \(\mathbb{F}_2\) に根を持たないし、 \(\mathbb{F}_3\) 上の多項式 \(x^2+1=0\) は \(\mathbb{F}_3\) 上に根を持たない。

そういう時、もとの体にその方程式の根となるような元 \(\alpha\) を付け加えてやることができる。

その付け加えた体を、 \(K\) の代数拡大体と呼び、 \(K(\alpha)\) と書く。

数学的に真面目にやるには、 \(K\) の多項式環 \(K[x]\) をその既約多項式 \(f(x)\) の生成するイデアル \((f)\) で割る、という操作をする。 そうして得られたもの \(K[x]/(f)\) は再び体となる。

有限体

元の個数が有限である体を有限体 (finite field) という。

有限体の標数は正である。 なぜなら、標数 0 の体は素体として有理数体 \(\mathbb{Q}\) を含み、これは無限体であるからである。

有限体の例としては、標数 \(p\) の素体 \(\mathbb{F}_p\) がある。

他の例は、 \(\mathbb{F}_p\) を代数拡大することによって得られる。 体の例として最初の方に挙げた \(\mathbb{F}_5(\sqrt{2})\) は有限体である。

例えば、 \(\mathbb{F}_3\) には 2 の平方根がない（対比：\(\mathbb{R}\) には \(-1\) の平方根がない）。 2の平方根を付け足したものは \(\mathbb{F}_3(\sqrt{2})=\{a+b\sqrt{2}\mid a,b\in\mathbb{F}_3\}\) となり、これは 9 個の元からなるので有限体である。

逆に、有限体は必ず \(\mathbb{F}_p\) の代数拡大として書ける。

この連載では、一般の有限体の場合についての定理を単に「フェルマーの小定理」と呼ぶことにする。

この定理はここでは証明しない。代わりに、いくつか例を見てみる。

標数 \(p\) (\(p>0\)) の体において、 \(p\) 乗する写像 \(x\mapsto x^p\) は体の準同型写像となる。 つまり、 \(\varphi\colon x\mapsto x^p\) について、

1. \(\varphi(1)=1\),
2. \(\varphi(x+y)=\varphi(x)+\varphi(y)\),
3. \(\varphi(xy)=\varphi(x)\varphi(y)\)

が成り立つ。 1. と 3. は明らかだろう。 2. は、つまり \[(x+y)^p=x^p+y^p\] だが、これは mod \(p\) で \[\binom{p}{k}\equiv\begin{cases} 1 & (k=0 \text{ または } p) \\ 0 & (\text{それ以外}) \end{cases}\] から従う。 この「\(p\) 乗する」写像を、フロベニウス写像という。 有限体の場合は、この写像は同型写像となる。

この定理も証明は省略する。 この定理により、位数 \(q\) の有限体は同型を除いて一意なので、それを \(\mathbb{F}_q\) と書く。

Haskell における有限体の実装

これまでは、具体的な環や体などの数学的対象に、 Haskell の型を対応させてきた。 しかし、有限体 \(\mathbb{F}_q\) という対象は \(q\) という整数に依存する。

個々の有限体に対して、 \(\mathbb{F}_2\) には型 F2 を, \(\mathbb{F}_3\) には型 F3 を、というに個別の型を作ることはもちろんできる。 実行時に与えられる素数 \(p\) に対して \(\mathbb{F}_p\) に対応する型を作るにはどうすればいいか。

項に依存した型は依存型 (dependent types) と呼ばれるが、（古典的には） Haskell には依存型はない。 しかし、自然数を型でエンコードすることはできて、あとはランク2多相 (rank-2 polymorphism) があれば、実行時に与えられた自然数を型レベルに持ち上げることができる。 型レベルに持ち上げた自然数から実行時に使える値を取り出すのには型クラスを使えば良い、というのが以下の論文で述べられている：

• Oleg Kiselyov and Chung-chien Shan, Functional Pearl: Implicit Configurations – or, Type Classes Reflect the Values of Types

これを Haskell のライブラリーとして実装したのが reflection パッケージである。 ただし、型レベル自然数としては通常の型ではなくて Nat カインドの型を使うし、実行時に与えられた自然数を型レベルに持ち上げる操作には多相再帰ではなく GHC の実装を悪用したものになっている。

さて、この連載は一変数多項式から始まり、（多倍長演算を除けば）なるべく自前で各種アルゴリズムを実装するようにしてきた。 しかし、有限体に関しては、（和、差、積に関しては）誰が実装しても同じような実装になると考えられ、自前で実装する意義は薄いと考えられる。 よって、ここでは有限体を再発明することはせず、既存の実装である finite-field パッケージをそのまま利用することにする。

finite-field パッケージの使い方を簡単に確認しておく。 finite-field パッケージが提供する型や関数は、 Data.FiniteField モジュールを import することによって使えるようになる。

Data.FiniteField モジュールは、有限体を表す型クラス FiniteField と、有限素体を表すデータ型 PrimeField, それに有限素体の元を整数に変換する関数 toInteger を提供している：

class Fractional k => FiniteField k where
  order :: k -> Integer
  char :: k -> Integer
  pthRoot :: k -> k
  allValues :: [k]

data PrimeField (p :: Nat) = ...

toInteger :: PrimeField p -> Integer

FiniteField のメソッドを一応説明しておく。 order は有限体の位数、つまり元の個数だ。 char は有限体の標数、 pthRoot は p 乗根を返す。allValues は有限体の元をリストとして返す。

【2018年3月6日 追加】PrimeField 型も IntegralDomain と GCDDomain のインスタンスにしておこう：

module Numeric.AlgebraicReal.Class where
import Data.Ratio
import qualified Data.Vector as V
import Data.FiniteField
import GHC.TypeLits (KnownNat)

-- 略

instance (KnownNat p) => IntegralDomain (PrimeField p) where
  divide = (/)

instance (KnownNat p) => GCDDomain (PrimeField p) where
  gcdD = fieldGcd
  contentV = fieldContentV

finite-field パッケージを使うために、algebraic-real.cabal の build-depends: に次のように書き加える：

  build-depends:       base >= 4.7 && < 5
                     , vector
                     , finite-field

stack.yaml の extra-deps: にも追加する：　

# Dependency packages to be pulled from upstream that are not in the resolver
# (e.g., acme-missiles-0.3)
extra-deps:
- finite-field-0.9.0

それができたら stack repl で ghci を起動する。 プロンプトに :m Data.FiniteField と打ち込んでコンテクストを切り替え、:set -XDataKinds で DataKinds 拡張を有効にする。 DataKinds拡張は、型レベルの自然数を普通に記述するために必要となる。

*Numeric.AlgebraicReal.UniPoly Numeric.AlgebraicReal.AlgReal Numeric.AlgebraicReal.CReal Numeric.AlgebraicReal.Class Numeric.AlgebraicReal.Factor.Kronecker Numeric.AlgebraicReal.Factor.SquareFree Numeric.AlgebraicReal.Interval Numeric.AlgebraicReal.Resultant Numeric.AlgebraicReal.UniPoly> :m Data.FiniteField
Prelude Data.FiniteField> :set -XDataKinds

計算例として、 \(\mathbb{F}_{11}\) において \(x^{11}=x\) となることを確かめてみよう。

Prelude Data.FiniteField> 2^11 :: PrimeField 11
2
Prelude Data.FiniteField> 3^11 :: PrimeField 11
3
Prelude Data.FiniteField> 4^11 :: PrimeField 11
4

有限体上の多項式の計算もしてみよう。 まず :m + Numeric.AlgebraicReal.UniPoly で UniPoly モジュールを使えるようにする。

Prelude Data.FiniteField> :m + Numeric.AlgebraicReal.UniPoly
Prelude Data.FiniteField Numeric.AlgebraicReal.UniPoly>

\((x+1)^{11}=x^{11}+1\) となることを確認してみよう。

Prelude Data.FiniteField Numeric.AlgebraicReal.UniPoly> (ind + 1)^11 :: UniPoly (PrimeField 11)
UniPoly [1,0,0,0,0,0,0,0,0,0,0,1]
Prelude Data.FiniteField Numeric.AlgebraicReal.UniPoly> ((ind + 1)^11 :: UniPoly (PrimeField 11)) == ind^11 + 1
True

これで有限体についての準備が整ったので、次回からは有限体上の多項式の因数分解アルゴリズムを取り上げて行く。

• 前：#8 多項式の因数分解 その1 Kronecker の方法と無平方分解
• 目次
• 次：#10 多項式の因数分解 その2 Cantor-Zassenhaus の方法