# 有限体の構造：部分体・Frobenius 自己同型・既約多項式の個数 > 有限体の元が x^q − x の根全体であることから出発し、部分体の束、Frobenius 自己同型が生成する Galois 群、既約多項式の根と個数の公式、平方元、代数閉包を根の数え上げだけで証明する。 > https://rikai.mugen-giken.com/mathematics/finite-fields-coding/structure-of-finite-fields ## 0. この記事の要点 足し算・引き算・掛け算・割り算ができて、しかも元の個数が有限の数の体系があります。たとえば時計のように 7 で一周する数の体系では、0 以外の数でも割り算ができます。この記事は、そうした体系の「中身」を調べます。小さな体系は大きな体系の中にどう入っているのか、どんな多項式が因数分解できないのか、そのような多項式は何個あるのか、といった素朴な問いに、根の個数を数えるだけで答えます。読み終えると、元が 256 個や 16 個の体を自分の手で作って計算し、その構造を説明できるようになります。 - 元の個数が $q$ の有限体 $\mathbb{F}_q$ の元は、多項式 $x^q - x$ の根の全体です。この記事の定理は、すべてこの 1 つの事実と「$n$ 次多項式の根は $n$ 個以下」から出ます。 - $\mathbb{F}_{p^n}$ の部分体は $n$ の約数 $m$ ごとにちょうど 1 つあり、$p^m$ 個の元をもちます。部分体の包含関係は約数の整除関係と同じ形をしています。 - $\mathbb{F}_{q^n}$ の $\mathbb{F}_q$ 上の自己同型は、Frobenius 自己同型 $\sigma_q : x \mapsto x^q$ の冪 $n$ 個に限ります。中間体は $n$ の約数と 1 対 1 に対応します。 - $\mathbb{F}_q$ 上の $n$ 次既約多項式の根は $\alpha, \alpha^q, \ldots, \alpha^{q^{n-1}}$ の $n$ 個で、$x^{q^n} - x$ は次数が $n$ の約数であるモニック既約多項式すべての積です。 - ここから既約多項式の個数の公式 $N_q(n) = \frac1n \sum_{d \mid n} \mu(n/d)\, q^d$ が出ます。$N_q(n)$ は常に正で、ほぼ $q^n/n$ です。 - 奇数の $q$ では $0$ でない元のちょうど半分が平方元で、$\mathbb{F}_q$ のどの元も平方元 2 個の和で書けます。最後に $\mathbb{F}_q$ の代数閉包を有限体の合併として作ります。 ## 1. 動機 符号理論では、文字の集合に四則演算が欲しくなります。誤りを検出するための検査式は連立一次方程式で書くのが最も扱いやすく、連立一次方程式を解くには割り算が要るからです。文字が 2 種類なら $\mathbb{Z}/2\mathbb{Z}$、素数 $p$ 種類なら $\mathbb{Z}/p\mathbb{Z}$ が使えますが、計算機が扱う 1 バイトは $256 = 2^8$ 種類で、$\mathbb{Z}/256\mathbb{Z}$ は体ではありません（$2 \cdot 128 = 0$）。必要なのは元の個数が $2^8$ の体 $\mathbb{F}_{256}$ です。 元の個数が素数冪 $q = p^e$ の体がただ 1 つ存在すること、その乗法群が巡回群であることは [多項式環と体の拡大](/mathematics/algebra/polynomial-rings-field-extensions) で証明されています。この記事ではその先、つまり有限体の「中身」を調べます。部分体はいくつあるか、自己同型は何か、既約多項式はどう分解しどれだけあるか、という問いです。 無限体の拡大でこれらに答えるには Galois 理論の基本定理が必要ですが、有限体では事情がずっと簡単です。体の元がすべて 1 つの多項式 $x^q - x$ の根になっているので、「根の個数は次数以下」という数え上げだけで全部が決まります。この記事は Galois 理論の基本定理を使いません。 このテーマの後の章は、すべてこの章に乗っています。[第 2 章](/mathematics/finite-fields-coding/polynomials-trace-norm) は $x^n - 1$ の分解とトレースを扱い、後半の巡回符号・BCH 符号は原始元の冪を、有限幾何は $\mathbb{F}_q$ 上のベクトル空間を使います。 ## 2. 準備：根の個数・巡回群・有限体の元 この記事では体はすべて可換とします。$p$ は素数、$q$ は $p$ の冪を表します。 体 $F$ の部分体すべての共通部分を $F$ の**素体**という。$F$ の標数（）が素数 $p$ のとき、素体は $\{0, 1, 1+1, \ldots, (p-1)\cdot 1\}$ であり、$\mathbb{Z}/p\mathbb{Z}$ と同型である。これを $\mathbb{F}_p$ と書く。 実際、標数が $p$ なら $k \mapsto k \cdot 1$ は $\mathbb{Z}/p\mathbb{Z}$ から $F$ への単射な環準同型を定め、その像はどの部分体にも含まれ（部分体は $1$ を含み加法で閉じるので）、それ自身が体です。有限体の標数は必ず素数です（有限体は整域なので より標数は $0$ か素数で、標数 $0$ なら $k \cdot 1$ がすべて異なり無限個の元をもってしまいます）。 次の補題が、この記事のすべての数え上げの土台です。 $K$ を体、$f \in K[x]$ を次数 $n \ge 0$ の多項式とする。 1. $a \in K$ が $f(a) = 0$ を満たすなら、ある $g \in K[x]$ により $f = (x - a)\,g$ と書ける。 2. $a_1, \ldots, a_k \in K$ が $f$ の相異なる根なら、$f = (x - a_1)\cdots(x - a_k)\,g$ となる $g \in K[x]$ がある。 3. $f$ の $K$ における根は $n$ 個以下である。 (1) $f = \sum_{j=0}^{n} c_j x^j$ とします。$j \ge 1$ に対し $x^j - a^j = (x - a)(x^{j-1} + a x^{j-2} + \cdots + a^{j-1})$ です（右辺を展開すると中間の項が打ち消し合います）。したがって $$ f(x) = f(x) - f(a) = \sum_{j=1}^{n} c_j (x^j - a^j) = (x - a) \sum_{j=1}^{n} c_j \bigl(x^{j-1} + a x^{j-2} + \cdots + a^{j-1}\bigr) $$ となり、右辺の和を $g$ とすればよいです。 (2) $k$ についての帰納法で示します。$k = 1$ は (1) です。$f = (x - a_1)\cdots(x - a_{k-1})\,g_{k-1}$ と書けたとします。$x = a_k$ を代入すると $0 = (a_k - a_1)\cdots(a_k - a_{k-1})\,g_{k-1}(a_k)$ です。$a_k \ne a_i$ なので各 $a_k - a_i$ は $0$ でなく、体には零因子がないので $g_{k-1}(a_k) = 0$ です。(1) により $g_{k-1} = (x - a_k)\, g$ と書けます。 (3) 相異なる根が $k$ 個あれば、(2) の両辺の次数を比べて $n = k + \deg g \ge k$ です（$f \ne 0$ なので $g \ne 0$）。 乗法群の議論で使う巡回群の性質もまとめておきます。 $G$ を位数 $N$ の巡回群、$g$ をその生成元とする。 1. 整数 $j$ に対し、$g^j$ の位数は $N / \gcd(j, N)$ である。 2. $G$ の生成元はちょうど $\varphi(N)$ 個ある（$\varphi$ はオイラー関数）。 3. $N$ の正の約数 $d$ に対し、$G_d = \{x \in G : x^d = e\}$ は位数 $d$ の部分群で、$g^{N/d}$ が生成する。位数 $d$ の $G$ の部分群は $G_d$ だけである。 (1) $h = \gcd(j, N)$ とおきます。整数 $k$ について、 より $(g^j)^k = e \iff N \mid jk \iff (N/h) \mid (j/h)\,k$ です。$\gcd(N/h, j/h) = 1$ なので（）、 により最後の条件は $(N/h) \mid k$ と同値です。そのような最小の正の $k$ は $N/h$ です。 (2) より $G = \{g^j : 1 \le j \le N\}$ で、これら $N$ 個は相異なります。$g^j$ が生成元であることは位数が $N$ であることと同値で、(1) により $\gcd(j, N) = 1$ と同値です。そのような $j \in \{1, \ldots, N\}$ の個数が $\varphi(N)$ です（）。 (3) $x = g^j$ について $x^d = e \iff N \mid jd \iff (N/d) \mid j$ です。したがって $G_d = \{g^{(N/d) i} : 0 \le i \le d - 1\}$ で、これは $g^{N/d}$ が生成する部分群です。(1) より $g^{N/d}$ の位数は $N/\gcd(N/d, N) = d$ なので $|G_d| = d$ です。$H$ を位数 $d$ の部分群とすると、 より $H$ の元 $x$ はすべて $x^d = e$ を満たすので $H \subseteq G_d$ で、元の個数が等しいので $H = G_d$ です。 $F$ を有限体、$p$ をその標数とする。 1. $|F| = p^e$ となる $e \ge 1$ がある。以下 $q = p^e$ とおく。 2. すべての $a \in F$ が $a^q = a$ を満たし、$0$ でない $a$ は $a^{q-1} = 1$ を満たす。 3. $F[x]$ において $x^q - x = \prod_{a \in F} (x - a)$ である。 4. $K$ を $F$ を含む体とすると、$\{a \in K : a^q = a\} = F$ である。 (1) は の 1 です。 (2) $F^{\times} = F \setminus \{0\}$ は位数 $q - 1$ の群なので、 より $a \ne 0$ なら $a^{q-1} = 1$ です。両辺に $a$ を掛けて $a^q = a$ で、これは $a = 0$ でも成り立ちます。 (3) (2) より $F$ の $q$ 個の元はすべて $x^q - x$ の根です。 の 2 より $x^q - x = \prod_{a \in F}(x - a) \cdot g$ と書け、次数を比べて $\deg g = 0$、最高次の係数を比べて $g = 1$ です。 (4) (2) より $F$ は左辺に含まれます。$K[x]$ の多項式 $x^q - x$ の $K$ における根は の 3 より $q$ 個以下で、$F$ の $q$ 個の元がすでに根なので、ほかに根はありません。 (4) は「$K$ の中で $F$ の元かどうかは、$q$ 乗して元に戻るかどうかで判定できる」と読めます。以後、この判定を何度も使います。 $K$ を標数 $p$ の体、$k \ge 1$ とする。$E = \{a \in K : a^{p^k} = a\}$ は $K$ の部分体で、$|E| \le p^k$ である。 $E$ は $x^{p^k} - x$ の根の集合なので、 の 3 より $|E| \le p^k$ です。$0, 1 \in E$ です。$a, b \in E$ のとき、 より $(a + b)^{p^k} = a^{p^k} + b^{p^k} = a + b$、また $(ab)^{p^k} = a^{p^k} b^{p^k} = ab$ なので $a + b,\ ab \in E$ です。$-a = (p - 1) \cdot a$ は $a$ を $p - 1$ 個足したものなので $E$ に入ります。したがって $E$ は $K$ の部分環で、体の部分環なので整域です。有限な整域は体です（）。 有限体を具体的に作る方法も確認しておきます。 $K$ を元の個数が $q$ の有限体、$f \in K[x]$ を次数 $n \ge 1$ のモニックな既約多項式とする。剰余環 $L = K[x]/(f)$ は $q^n$ 個の元をもつ体である。$x$ の類を $\alpha$ と書くと $f(\alpha) = 0$ で、$(1, \alpha, \ldots, \alpha^{n-1})$ は $L$ の $K$ 上の基底であり、$f$ は $\alpha$ の $K$ 上の最小多項式である。 次の証明のねらいは、整数を素数で割った余りの体系と同じように、多項式を既約な多項式で割った余りの全体が体になることを確かめ、その元の個数と基底を読み取ることです。他の記事の命題は、この余りの体系が体になる理由と、$\alpha$ の最小多項式が $f$ になる理由を与えるために使います。 $K[x]$ は単項イデアル整域なので（）、既約元 $f$ の生成するイデアルは極大です（）。したがって $L$ は体です（）。定数多項式の類により $K$ を $L$ の部分体とみなします。 代入写像 $\mathrm{ev}_\alpha : K[x] \to L$, $g \mapsto g(\alpha)$ は自然な射影 $g \mapsto g + (f)$ そのものなので、核は $(f)$ で、$f(\alpha) = 0$ です。 により核を生成するモニックな既約多項式が $\alpha$ の最小多項式で、それは $f$ です。同じ命題から $L = K[\alpha]$ かつ $[L : K] = n$ です。 $L$ は $K$ 上 $n$ 次元なので、基底による座標表示で $K^n$ と 1 対 1 に対応し、$|L| = q^n$ です。$f(\alpha) = 0$ から $\alpha^n$ は $1, \alpha, \ldots, \alpha^{n-1}$ の $K$ 係数の一次結合で、これに $\alpha$ を掛けていけば $\alpha^{n+1}, \alpha^{n+2}, \ldots$ もそうだと分かります。$L = K[\alpha]$ なので $1, \ldots, \alpha^{n-1}$ は $L$ を張ります。これらが線形従属なら $L$ は $n - 1$ 個以下の元で張られ、次元が $n$ であることに反します。よって基底です。 $K$ を元の個数が $q$ の有限体、$n \ge 1$ とする。$K$ を部分体として含み $q^n$ 個の元をもつ体 $F$ が存在する。そのような体は $x^{q^n} - x$ の $K$ 上の分解体であり、$K$ の元を動かさない同型を除いて一意である。 $F$ が $K$ を含み $|F| = q^n$ なら、 の 3 より $x^{q^n} - x = \prod_{a \in F}(x - a)$ で、$F$ はこの多項式の根全体なので、$F$ は $x^{q^n} - x$ の $K$ 上の分解体です。一意性は分解体の一意性（）から従います。 存在を示します。$x^{q^n} - x \in K[x]$ の $K$ 上の分解体 $L$ を取ります（同じ定理）。$L$ は $K$ に有限個の代数的な元を付け加えた体なので、$K$ 上有限次元（ と ）で、有限体です。$F = \{a \in L : a^{q^n} = a\}$ とおくと、 より $F$ は部分体で、 の 2 より $K \subseteq F$ です（$a^q = a$ なら $a^{q^n} = a$）。$x^{q^n} - x$ は $L$ で 1 次式の積に分解し、その根はすべて $F$ に属します。あとは根が相異なることを示せば $|F| = q^n$ です。$a$ を根とすると、 より $$ x^{q^n} - x = (x^{q^n} - a^{q^n}) - (x - a) = (x - a)^{q^n} - (x - a) = (x - a)\bigl((x - a)^{q^n - 1} - 1\bigr) $$ で、右辺の第 2 因子は $x = a$ で $-1 \ne 0$ です。したがって $(x - a)^2$ は $x^{q^n} - x$ を割り切らず、根はすべて単根です。 以後、$\mathbb{F}_q$ を 1 つ固定したとき、$\mathbb{F}_{q^n}$ は $\mathbb{F}_q$ を部分体として含む $q^n$ 元の体を表すことにします。 により、これは $\mathbb{F}_q$ 上の同型を除いて 1 つに決まります。 **$\mathbb{F}_4$**。$x^2 + x + 1$ は $\mathbb{F}_2$ に根をもたない（$0, 1$ を代入するとどちらも $1$）2 次式なので既約です。$\mathbb{F}_4 = \mathbb{F}_2[x]/(x^2 + x + 1) = \{0, 1, \omega, \omega + 1\}$ で、$\omega^2 = \omega + 1$ です。 | $+$ | $0$ | $1$ | $\omega$ | $\omega+1$ | |---|---|---|---|---| | $0$ | $0$ | $1$ | $\omega$ | $\omega+1$ | | $1$ | $1$ | $0$ | $\omega+1$ | $\omega$ | | $\omega$ | $\omega$ | $\omega+1$ | $0$ | $1$ | | $\omega+1$ | $\omega+1$ | $\omega$ | $1$ | $0$ | | $\times$ | $1$ | $\omega$ | $\omega+1$ | |---|---|---|---| | $1$ | $1$ | $\omega$ | $\omega+1$ | | $\omega$ | $\omega$ | $\omega+1$ | $1$ | | $\omega+1$ | $\omega+1$ | $1$ | $\omega$ | $\omega \cdot \omega = \omega + 1$、$\omega(\omega + 1) = \omega^2 + \omega = 1$、$(\omega+1)^2 = \omega^2 + 1 = \omega$ です。$\mathbb{F}_4$ は $\mathbb{Z}/4\mathbb{Z}$ とは別物で、どの元も 2 回足すと $0$ になります。 **$\mathbb{F}_9$**。$x^2 + 1$ は $\mathbb{F}_3$ に根をもちません（$0^2 + 1 = 1$、$1^2 + 1 = 2$、$2^2 + 1 = 2$）。$\mathbb{F}_9 = \mathbb{F}_3[x]/(x^2 + 1) = \{a + b i : a, b \in \mathbb{F}_3\}$、$i^2 = -1$ です。$\mathbb{F}_3$ では $-1$ は平方元ではありませんが、$\mathbb{F}_9$ では $i$ と $-i = 2i$ が $-1$ の平方根です。乗法は複素数と同じ規則で、たとえば $(1 + i)^2 = 1 + 2i + i^2 = 2i$、$(1 + i)^4 = (2i)^2 = 4 i^2 = -1$ です。 ## 3. 原始元と離散対数 により、$\mathbb{F}_q^{\times}$ は位数 $q - 1$ の巡回群です。 1. 巡回群 $\mathbb{F}_q^{\times}$ の生成元を $\mathbb{F}_q$ の**原始元**という。 2. $\mathbb{F}_q$ 上の次数 $n$ のモニックな既約多項式 $f$ が**原始多項式**であるとは、$\mathbb{F}_{q^n}$ における $f$ の根が $\mathbb{F}_{q^n}$ の原始元であることをいう（$f$ が $\mathbb{F}_{q^n}$ に根をもち、根がすべて同じ位数をもつことは で示す）。 3. 原始元 $\gamma$ を固定する。$a \in \mathbb{F}_q^{\times}$ に対し、$a = \gamma^{j}$ となる $j \in \{0, 1, \ldots, q - 2\}$ がただ 1 つある。これを $a$ の（$\gamma$ を底とする）**離散対数**といい $\log_\gamma a$ と書く。 4. $j \in \{0, \ldots, q-2\}$ で $1 + \gamma^j \ne 0$ のとき、$1 + \gamma^j = \gamma^{Z(j)}$ で定まる $Z(j) \in \{0, \ldots, q - 2\}$ を **Zech 対数**という。$1 + \gamma^j = 0$ のときは $Z(j) = \infty$ と書く。 離散対数を使うと乗法が指数の足し算になります: $\gamma^i \gamma^j = \gamma^{i + j \bmod (q-1)}$。加法は Zech 対数の表で処理できます。$i \le j$ として $$ \gamma^i + \gamma^j = \gamma^i (1 + \gamma^{j - i}) = \gamma^{\,i + Z(j - i)} $$ です（$Z(j - i) = \infty$ なら和は $0$）。元を冪の指数で持てば、長さ $q - 1$ の表 1 枚で四則演算ができます。 $f = x^4 + x + 1 \in \mathbb{F}_2[x]$ は既約です。$f(0) = f(1) = 1$ なので 1 次の因子はなく、$\mathbb{F}_2$ 上の 2 次の既約多項式は $x^2 + x + 1$ だけ（ほかの 2 次式 $x^2$、$x^2 + 1 = (x+1)^2$、$x^2 + x = x(x+1)$ は可約）で、$(x^2 + x + 1)^2 = x^4 + x^2 + 1 \ne f$ だからです。$\mathbb{F}_{16} = \mathbb{F}_2[x]/(f)$ とし、$x$ の類を $\alpha$ とします。$\alpha^4 = \alpha + 1$ を使って冪を順に計算します（元 $c_3\alpha^3 + c_2\alpha^2 + c_1\alpha + c_0$ を $c_3c_2c_1c_0$ と書きます）。 | $j$ | $\alpha^j$ | $Z(j)$ | $j$ | $\alpha^j$ | $Z(j)$ | $j$ | $\alpha^j$ | $Z(j)$ | |---|---|---|---|---|---|---|---|---| | 0 | 0001 | $\infty$ | 5 | 0110 | 10 | 10 | 0111 | 5 | | 1 | 0010 | 4 | 6 | 1100 | 13 | 11 | 1110 | 12 | | 2 | 0100 | 8 | 7 | 1011 | 9 | 12 | 1111 | 11 | | 3 | 1000 | 14 | 8 | 0101 | 2 | 13 | 1101 | 6 | | 4 | 0011 | 1 | 9 | 1010 | 7 | 14 | 1001 | 3 | $\alpha^{15} = \alpha \cdot \alpha^{14} = \alpha^4 + \alpha = 1$ で、$15$ 個の冪がすべて異なるので $\alpha$ は原始元、$f$ は原始多項式です。表の使い方の例: $\alpha^3 + \alpha^{10} = \alpha^3(1 + \alpha^7) = \alpha^{3 + Z(7)} = \alpha^{12}$。直接確かめると $1000 + 0111 = 1111 = \alpha^{12}$ で一致します。 $\alpha$ を掛けるたびに 4 ビットが 1 つ左にずれ、$\alpha^4$ が溢れたときだけ $0011$（$= \alpha + 1$）を足す、という手順で表の各行ができます。溢れの有無と $j$ の進み方を見てください。
α の冪を 4 ビット列で順に計算する動画。各段階で 4 ビットを左へずらし、溢れたときだけ 0011 を足して次の冪を得る。右の輪の点が j = 0 から 14 まで進み、15 回で 1 に戻る。
## 4. 部分体と Frobenius 自己同型 ### 4.1. 部分体の束 $m, n$ を正の整数とする。 1. 整数 $a \ge 2$ について、$a^m - 1 \mid a^n - 1 \iff m \mid n$。 2. 体 $K$ 上の多項式環 $K[x]$ において、$x^m - 1 \mid x^n - 1 \iff m \mid n$。 3. 整数 $q \ge 2$ と体 $K$ について、$K[x]$ において $x^{q^m} - x \mid x^{q^n} - x \iff m \mid n$。 $n = sm + r$（$s \ge 0$、$0 \le r < m$）と書きます。$K[x]$ でも $\mathbb{Z}[x]$ でも $$ x^n - 1 = x^r (x^{sm} - 1) + (x^r - 1), \qquad x^{sm} - 1 = (x^m - 1)\bigl(x^{m(s-1)} + x^{m(s-2)} + \cdots + x^m + 1\bigr) $$ が成り立ちます（$s = 0$ のとき第 2 式の右辺の括弧は空の和 $0$ とします）。したがって $x^n - 1 = (x^m - 1)\,u(x) + (x^r - 1)$ となる多項式 $u$ があります。 (2) $r = 0$ なら $x^n - 1 = (x^m - 1)\,u$ で割り切れます。$r > 0$ のとき、$x^m - 1 \mid x^n - 1$ なら $x^m - 1 \mid x^r - 1$ ですが、$x^r - 1$ は $0$ でなく次数が $r < m$ なので、次数 $m$ の多項式の倍数にはなりません。 (1) 上の恒等式に $x = a$ を代入すると $a^n - 1 = (a^m - 1)\,u(a) + (a^r - 1)$ で、$u(a)$ は整数です。$0 \le a^r - 1 < a^m - 1$ なので、$a^m - 1 \mid a^n - 1$ は $a^r - 1 = 0$、つまり $r = 0$ と同値です。 (3) $x^{q^n} - x = x\,(x^{q^n - 1} - 1)$、$x^{q^m} - x = x\,(x^{q^m - 1} - 1)$ で、$K[x]$ は整域なので $x$ を約して、条件は $x^{q^m - 1} - 1 \mid x^{q^n - 1} - 1$ と同値です。(2) によりこれは $q^m - 1 \mid q^n - 1$ と同値で、(1) により $m \mid n$ と同値です。 $F$ を元の個数が $p^n$ の有限体とする。 1. $F$ の部分体の元の個数は $p^m$（$m$ は $n$ の正の約数）である。 2. $n$ の正の約数 $m$ ごとに、$p^m$ 個の元をもつ $F$ の部分体がただ 1 つ存在する。それは $F_{(m)} = \{a \in F : a^{p^m} = a\}$ で、$\mathbb{F}_{p^m}$ に同型である。 3. $n$ の約数 $m, m'$ について、$F_{(m)} \subseteq F_{(m')} \iff m \mid m'$。 (1) $E$ を部分体とします。$E$ は $1$ を含むので標数は $p$ で、 の 1 より $|E| = p^m$ と書けます。$F$ は $E$ 上のベクトル空間で、有限集合なので有限次元です。次元を $s$ とすると座標表示により $|F| = |E|^s$、つまり $p^n = p^{ms}$ で、$n = ms$ です。 (2) $m \mid n$ とします。 より $F_{(m)}$ は部分体で $|F_{(m)}| \le p^m$ です。逆向きの不等式を示します。 の 3 より $x^{p^n} - x = (x^{p^m} - x)\,h(x)$ となる $h \in F[x]$ があり、$\deg h = p^n - p^m$ です。 の 2 より $F$ の $p^n$ 個の元はすべて左辺の根なので、それぞれ $x^{p^m} - x$ か $h$ の根です。$h$ の根は $p^n - p^m$ 個以下（）なので、$x^{p^m} - x$ の根が $p^m$ 個以上あります。よって $|F_{(m)}| = p^m$ です。 一意性を示します。$E$ を $p^m$ 個の元をもつ部分体とすると、 の 2 を $E$ に使って $E$ の元はすべて $a^{p^m} = a$ を満たし、$E \subseteq F_{(m)}$ です。元の個数が等しいので $E = F_{(m)}$ です。$\mathbb{F}_{p^m}$ との同型は の 3 です。 (3) $F_{(m)} \subseteq F_{(m')}$ なら、(1) を体 $F_{(m')}$（元の個数 $p^{m'}$）とその部分体 $F_{(m)}$ に使って $m \mid m'$ です。逆に $m' = ms$ なら、$a^{p^m} = a$ を満たす $a$ について $p^m$ 乗を $s$ 回繰り返すと $a^{p^{ms}} = a$ となり、$a \in F_{(m')}$ です。
p 個（m = 1、素体） p² 個（m = 2） p³ 個（m = 3） p⁴ 個（m = 4） p⁶ 個（m = 6） p¹² 個（m = 12、全体）
図で $p^4$ 個の体と $p^6$ 個の体の共通部分は $p^2$ 個の体です（$\gcd(4, 6) = 2$）。$p^4$ 個の体は $p^3$ 個の体を含みません（$3 \nmid 4$）。「元の個数が小さい体は大きい体に入る」とは限らないことに注意してください。 ### 4.2. Frobenius 自己同型と Galois 群 $K \subseteq F$ を有限体の拡大、$|K| = q$ とする。写像 $\sigma_q : F \to F$, $\sigma_q(a) = a^q$ を（$K$ 上の）**Frobenius 自己同型**という。$a \in F$ に対し、$a, a^q, a^{q^2}, \ldots$ を $a$ の $K$ 上の**共役元**という。 $\sigma_q$ が実際に $K$ の元を動かさない体の自己同型であることは、次の定理の証明の最初に確かめます。$K$ 上の自己同型の群 $\mathrm{Aut}(F/K)$ と Galois 拡大の用語は のとおりとします。 $K \subseteq F$ を有限体の拡大とし、$|K| = q$、$|F| = q^n$ とする。$\sigma = \sigma_q$ とおく。 1. $\sigma \in \mathrm{Aut}(F/K)$ で、$\sigma$ の位数は $n$ である。 2. $\mathrm{Aut}(F/K) = \{\mathrm{id}, \sigma, \sigma^2, \ldots, \sigma^{n-1}\}$ である。$F/K$ は Galois 拡大で、Galois 群は $\sigma$ が生成する位数 $n$ の巡回群である。 3. $n$ の正の約数 $d$ ごとに、$K \subseteq M \subseteq F$ かつ $|M| = q^d$ を満たす体 $M$ がただ 1 つある。それは $M_d = \{a \in F : \sigma^d(a) = a\}$ で、中間体はこれらに限る。 4. $\mathrm{Aut}(F/K)$ の部分群は $\langle \sigma^d \rangle$（$d \mid n$）に限り、$\langle \sigma^d \rangle = \mathrm{Aut}(F/M_d)$、$|\langle \sigma^d\rangle| = n/d$ である。対応 $\langle \sigma^d \rangle \mapsto M_d$ は部分群と中間体の間の全単射で、$M_d \subseteq M_{d'} \iff d \mid d' \iff \langle \sigma^{d'} \rangle \subseteq \langle \sigma^d \rangle$ が成り立つ。 証明の方針です。(1) では $\sigma$ が確かに自己同型であることと位数を調べます。(2) の中心は、自己同型が 1 個の元（原始元 $\gamma$）の行き先だけで決まり、その行き先は $\gamma$ の最小多項式の根の中から選ぶしかないので、$n$ 個以下になる、という数え上げです。$\sigma$ の冪がすでに $n$ 個あるので、これで自己同型が全部だと分かります。(3)(4) は部分体の個数と巡回群の部分群の個数を比べる作業です。 (1) $q = p^e$ とします。 より $\sigma(a + b) = (a + b)^{p^e} = a^{p^e} + b^{p^e} = \sigma(a) + \sigma(b)$ です。また $\sigma(ab) = (ab)^q = a^q b^q = \sigma(a)\sigma(b)$、$\sigma(1) = 1^q = 1$ です。$\sigma$ は体からの環準同型なので単射で、$F$ は有限集合なので全単射です。$a \in K$ なら の 2 より $\sigma(a) = a^q = a$ です。よって $\sigma \in \mathrm{Aut}(F/K)$ です。 $\sigma^k(a) = a^{q^k}$ です。 の 2 を $F$ に使うと $\sigma^n = \mathrm{id}$ です。$1 \le k < n$ で $\sigma^k = \mathrm{id}$ なら、$F$ の $q^n$ 個の元がすべて次数 $q^k < q^n$ の多項式 $x^{q^k} - x$ の根になり、 に反します。よって $\sigma$ の位数は $n$ です。 (2) より $\mathrm{id}, \sigma, \ldots, \sigma^{n-1}$ は相異なる $n$ 個の元です。$|\mathrm{Aut}(F/K)| \le n$ を示せば十分です。$\gamma$ を $F$ の原始元とします（）。$F$ の $0$ でない元はすべて $\gamma$ の冪なので $F = K(\gamma)$ です。$g$ を $\gamma$ の $K$ 上の最小多項式とすると、 より $\deg g = [K(\gamma) : K] = [F : K]$ で、$|F| = q^{[F:K]}$ なので $\deg g = n$ です。$\tau \in \mathrm{Aut}(F/K)$ とすると、$g$ の係数は $K$ の元で $\tau$ に動かされないので $g(\tau(\gamma)) = \tau(g(\gamma)) = 0$ です。つまり $\tau(\gamma)$ は $g$ の根で、候補は $n$ 個以下です（）。$\tau(\gamma^j) = \tau(\gamma)^j$ なので $\tau$ は $\tau(\gamma)$ で決まります。したがって $|\mathrm{Aut}(F/K)| \le n$ です。 より $F$ は $x^{q^n} - x \in K[x]$ の $K$ 上の分解体なので、$F/K$ は Galois 拡大です。 (3) $q = p^e$ とすると $|F| = p^{en}$ です。 より、$F$ の部分体は $en$ の約数 $m$ に対する $F_{(m)}$ で尽くされ、$K = F_{(e)}$ です。同じ定理の 3 より $K \subseteq F_{(m)} \iff e \mid m$ なので、中間体は $m = ed$（$d \mid n$）に対する $F_{(ed)}$ です。$F_{(ed)} = \{a : a^{p^{ed}} = a\} = \{a : a^{q^d} = a\} = M_d$ で、元の個数は $p^{ed} = q^d$ です。$d$ が異なれば元の個数が異なるので、$q^d$ 個の元をもつ中間体は $M_d$ だけです。 (4) $\mathrm{Aut}(F/K) = \langle \sigma \rangle$ は位数 $n$ の巡回群なので、 の 3 より、部分群は $n$ の約数 $s$ ごとに位数 $s$ のものがただ 1 つあり、$\sigma^{n/s}$ が生成します。$d = n/s$ と書き直せば、部分群は $\langle \sigma^d \rangle$（$d \mid n$）で、位数は $n/d$ です。(1)(2) を拡大 $F/M_d$（$|M_d| = q^d$、$|F| = (q^d)^{n/d}$）に使うと、$\mathrm{Aut}(F/M_d)$ は $\sigma_{q^d} = \sigma^d$ が生成します。 $d \mapsto \langle \sigma^d \rangle$ と $d \mapsto M_d$ はどちらも $n$ の約数の集合からの全単射なので、$\langle \sigma^d \rangle \mapsto M_d$ は全単射です。$M_d \subseteq M_{d'} \iff d \mid d'$ は の 3（$ed \mid ed' \iff d \mid d'$）です。$d \mid d'$ なら $\sigma^{d'}$ は $\sigma^d$ の冪なので $\langle \sigma^{d'} \rangle \subseteq \langle \sigma^d \rangle$ です。逆にこの包含が成り立てば、$\sigma^{d'}$ は $\sigma^d$ の冪なので $\sigma^d$ で動かない元は $\sigma^{d'}$ でも動かず、$M_d \subseteq M_{d'}$、したがって $d \mid d'$ です。 (3)(4) は Galois 理論の基本定理が有限体の拡大で述べる内容そのものです。ここでは基本定理を使わず、部分体の個数と巡回群の部分群の個数を別々に数えて対応を作りました。 $q = p^e$ とする。$\mathbb{F}_q$ の体としての自己同型は $\sigma_p^{\,j} : a \mapsto a^{p^j}$（$0 \le j \le e - 1$）の $e$ 個で、自己同型群は $\sigma_p$ が生成する位数 $e$ の巡回群である。 $\tau$ を $\mathbb{F}_q$ の自己同型とします。$\tau(1) = 1$ で $\tau$ は加法を保つので、素体の元 $k \cdot 1$ を動かしません。したがって自己同型群は $\mathrm{Aut}(\mathbb{F}_q/\mathbb{F}_p)$ に等しく、 を $K = \mathbb{F}_p$、$n = e$ として使えば結論が出ます。 たとえば $\mathbb{F}_p$ の自己同型は恒等写像だけで、$\mathbb{F}_4$ の自己同型は恒等写像と $\omega \leftrightarrow \omega + 1$ の入れ替え（2 乗写像）の 2 つです。 ## 5. 既約多項式の根と個数 ### 5.1. 既約多項式の根は Frobenius の軌道 $K$ を元の個数が $q$ の有限体、$f \in K[x]$ を次数 $n$ のモニックな既約多項式とし、$F$ を $K$ を含む有限体、$|F| = q^N$ とする。 1. $f$ が $F$ に根をもつことと、$n \mid N$ であることは同値である。 2. $\alpha \in F$ が $f$ の根なら、$\alpha, \alpha^q, \alpha^{q^2}, \ldots, \alpha^{q^{n-1}}$ は相異なり、$\alpha^{q^n} = \alpha$ で、 $$ f(x) = (x - \alpha)(x - \alpha^q)\cdots(x - \alpha^{q^{n-1}}) $$ である。特に $f$ は $\mathbb{F}_{q^n}$ で相異なる 1 次式の積に分解する。$f \ne x$ なら、$f$ の根はすべて $F^{\times}$ の中で同じ位数をもつ。 (2) の証明の流れは次のとおりです。まず根 $\alpha$ を $q$ 乗しても根のままなので、$\alpha, \alpha^q, \alpha^{q^2}, \ldots$ はすべて $f$ の根です。次に、$q$ 乗を何回繰り返すと $\alpha$ に戻るか、その最小の回数を $r$ とおき、$\alpha$ を含む体の大きさを比べて $r = n$ と分かります。したがって $n$ 個の根が相異なり、$f$ の根はこれで全部です。(1) は、根をもつ条件を体の元の個数の言葉に直したものです。 (2) $\alpha \in F$ を $f$ の根とします。 より、代入写像 $K[x] \to F$ の核は $\alpha$ の最小多項式 $m_\alpha$（モニックで既約）が生成します。$f$ は核に属するので $m_\alpha \mid f$ で、$f$ は既約かつモニックなので $f = m_\alpha$ です。同じ命題から $[K(\alpha) : K] = n$ で、$|K(\alpha)| = q^n$ です。 の 2 を体 $K(\alpha)$ に使うと $\alpha^{q^n} = \alpha$ です。 $\sigma = \sigma_q$ とします。$f$ の係数は $K$ の元で $\sigma$ に動かされない（ の 1）ので、$f(\sigma(\alpha)) = \sigma(f(\alpha)) = 0$ です。繰り返して、$\alpha^{q^i} = \sigma^i(\alpha)$ はすべて $f$ の根です。 $r$ を $\alpha^{q^r} = \alpha$ となる最小の正の整数とします。$r \le n$ です。$E = \{a \in F : a^{q^r} = a\}$ は より $F$ の部分体で $|E| \le q^r$ です。$E$ は $K$ と $\alpha$ を含むので $K(\alpha) \subseteq E$、したがって $q^n \le q^r$ で、$r = n$ です。もし $0 \le i < j \le n - 1$ で $\alpha^{q^i} = \alpha^{q^j}$ なら、両辺に $\sigma^{n - j}$ を施して $\alpha^{q^{n - j + i}} = \alpha^{q^n} = \alpha$ となり、$0 < n - j + i < n$ なので $r = n$ に反します。よって $\alpha, \alpha^q, \ldots, \alpha^{q^{n-1}}$ は $f$ の相異なる $n$ 個の根です。 の 2 より $f = \prod_{i=0}^{n-1}(x - \alpha^{q^i}) \cdot g$ で、次数と最高次の係数を比べて $g = 1$ です。 $f \ne x$ なら $\alpha \ne 0$ です（$f(0) = 0$ なら の 1 より $x \mid f$ で、既約性から $f = x$）。$\sigma$ は体の自己同型なので、$\alpha^k = 1 \iff \sigma(\alpha)^k = 1$ で、$\alpha$ と $\sigma(\alpha)$ の位数は等しいです。 (1) $\alpha \in F$ が根なら、(2) の議論より $K(\alpha)$ は $q^n$ 個の元をもつ $F$ の部分体です。$F$ を $K(\alpha)$ 上のベクトル空間とみて次元を $s$ とすると $q^N = (q^n)^s$ で、$n \mid N$ です。 逆に $n \mid N$ とします。 より $L = K[x]/(f)$ は $q^n$ 個の元をもつ体で、$x$ の類 $\bar{x}$ の最小多項式は $f$ です。 の 2 より $\bar{x}^{q^n} = \bar{x}$、つまり $x^{q^n} - x$ は代入写像の核 $(f)$ に属し、$f \mid x^{q^n} - x$ です。 の 3 より $x^{q^n} - x \mid x^{q^N} - x$ なので、$x^{q^N} - x = f \cdot h$ となる $h \in K[x]$ があり、$\deg h = q^N - n < q^N$ です。$F$ の $q^N$ 個の元はすべて左辺の根（）ですが、$h$ の根は $q^N - n$ 個以下（）なので、$f$ の根になっている $F$ の元があります。 無限体では、既約多項式の根を 1 つ付け加えても残りの根が出てくるとは限りません（$\mathbb{Q}(\sqrt[3]{2})$ は $x^3 - 2$ の虚数の根を含みません）。有限体では根を 1 つ付け加えると、その $q$ 乗、$q^2$ 乗、… として全部の根が手に入ります。 $K$ を元の個数が $q$ の有限体、$n \ge 1$ とする。$K[x]$ において、$x^{q^n} - x$ は、次数が $n$ の約数であるモニックな既約多項式すべての積に等しい（各既約多項式はちょうど 1 回ずつ現れる）。 $F$ を $K$ を含む $q^n$ 元の体とします（）。$\mathcal{P}$ を、$F$ に根をもつ $K$ 上のモニックな既約多項式の全体とします。 の 1（$N = n$）より、$\mathcal{P}$ は次数が $n$ の約数であるモニックな既約多項式の全体です。 $g \in \mathcal{P}$ の $F$ における根の集合を $R_g$ とします。 の 2 より $g = \prod_{a \in R_g}(x - a)$ です。$F$ の各元 $a$ は、その最小多項式 $m_a$ の根なので $R_{m_a}$ に属します。また $a \in R_g$ なら、定理の証明で見たとおり $g = m_a$ です。したがって $F$ は $R_g$（$g \in \mathcal{P}$）の交わりのない合併です。 の 3 より $$ x^{q^n} - x = \prod_{a \in F}(x - a) = \prod_{g \in \mathcal{P}} \prod_{a \in R_g} (x - a) = \prod_{g \in \mathcal{P}} g $$ です。 $q = 2$、$n = 4$ では、次数 $1, 2, 4$ の既約多項式がすべて現れます。 $$ x^{16} - x = x\,(x + 1)\,(x^2 + x + 1)\,(x^4 + x + 1)\,(x^4 + x^3 + 1)\,(x^4 + x^3 + x^2 + x + 1). $$ 次数の合計は $1 + 1 + 2 + 4 + 4 + 4 = 16$ です。 の $\alpha$ で言えば、$x^2 + x + 1$ の根は $\alpha^5, \alpha^{10}$（部分体 $\mathbb{F}_4$ の $0, 1$ 以外の元）、$x^4 + x + 1$ の根は $\alpha, \alpha^2, \alpha^4, \alpha^8$ です。次数 3 の既約多項式が現れないのは $3 \nmid 4$ だからで、これは $\mathbb{F}_{16}$ が $\mathbb{F}_8$ を含まないこと（）の言い換えです。 ### 5.2. 既約多項式の個数 $\mathbb{F}_q[x]$ の次数 $n$ のモニックな既約多項式の個数を $N_q(n)$ と書く。 すべての $n \ge 1$ について $$ q^n = \sum_{d \mid n} d\, N_q(d), \qquad N_q(n) = \frac{1}{n} \sum_{d \mid n} \mu(n/d)\, q^d $$ が成り立つ。ここで和は $n$ の正の約数 $d$ をわたり、$\mu$ は数論の Möbius 関数（$m$ が相異なる $k$ 個の素数の積なら $\mu(m) = (-1)^k$、平方因子をもてば $\mu(m) = 0$、$\mu(1) = 1$）である。 証明のねらいは、各次数の既約多項式の個数を、$q^n$ という既知の数から逆算することです。前の定理から、$q^n$ は「次数 $d$ の既約多項式の個数 $\times\, d$」を $n$ の約数 $d$ について足した和に等しいと分かります。この形の関係式から個数を取り出す一般的な道具が、[半順序集合](/mathematics/combinatorics/posets-mobius#def-poset)の上の Möbius 反転です。ここでは [Möbius 関数](/mathematics/combinatorics/posets-mobius#def-mobius-function)の値を、約数の整除関係の場合に直した形で使います。小さい例では、$n = 2$ のとき $q^2 = N_q(1) + 2N_q(2)$ と $N_q(1) = q$ から $N_q(2) = (q^2 - q)/2$ と分かり、これは公式と一致します。 の両辺の次数を比べます。左辺の次数は $q^n$、右辺は次数 $d$ の既約多項式が $N_q(d)$ 個ずつなので $\sum_{d \mid n} d\,N_q(d)$ です。これで第 1 式が出ます。 第 1 式はすべての正の整数で成り立つので、$n$ の約数全体が整除関係でなす半順序集合 $D_n$ の上で、$f(d) = d\,N_q(d)$、$g(d) = q^d$ とおくと $g(x) = \sum_{y \mid x} f(y)$ がすべての $x \in D_n$ で成り立ちます。Möbius 反転公式（ の 1）より $f(n) = \sum_{d \mid n} \mu_{D_n}(d, n)\, g(d)$ で、$D_n$ の Möbius 関数は $\mu_{D_n}(d, n) = \mu(n/d)$ です（ の 2）。$n$ で割って第 2 式を得ます。 すべての素数冪 $q$ と $n \ge 1$ について $$ \frac{q^n}{n} - \frac{2\,q^{n/2}}{n} < N_q(n) \le \frac{q^n}{n} $$ が成り立つ。特に $N_q(n) \ge 1$ で、$n \to \infty$ のとき $N_q(n) \big/ (q^n/n) \to 1$ である。 上界は の第 1 式で $d = n$ の項だけを残した $q^n \ge n\,N_q(n)$ です。 下界を示します。$n$ の約数で $n$ より小さいものは $n/2$ 以下なので、第 2 式と $|\mu| \le 1$ から $$ n\,N_q(n) \ge q^n - \sum_{d=1}^{\lfloor n/2 \rfloor} q^d = q^n - \frac{q^{\lfloor n/2 \rfloor + 1} - q}{q - 1} $$ です。$q \ge 2$ より $q/(q - 1) \le 2$ なので、$\dfrac{q^{\lfloor n/2 \rfloor + 1} - q}{q - 1} < \dfrac{q}{q-1}\, q^{\lfloor n/2 \rfloor} \le 2\, q^{n/2}$ です。$n$ で割れば下界が出ます。 $N_q(n) \ge 1$ を示します。$n = 1$ では $N_q(1) = q$（1 次のモニック多項式 $x - a$ はすべて既約）です。$n \ge 2$ では $\lfloor n/2 \rfloor + 1 \le n$ なので、上の式から $n\,N_q(n) \ge q^n - \dfrac{q^{\lfloor n/2\rfloor + 1} - q}{q - 1} \ge q^n - (q^n - q) = q > 0$ です。最後に、不等式の各辺を $q^n/n$ で割ると $1 - 2\,q^{-n/2} < N_q(n)/(q^n/n) \le 1$ で、$n \to \infty$ で左辺は $1$ に近づきます。 は「$\mathbb{F}_p$ 上に任意の次数の既約多項式がある」ことを体の存在から導いていました。上の系はそれを $\mathbb{F}_q$ に広げ、個数まで与えます。無作為に選んだ $n$ 次のモニック多項式が既約である確率はおよそ $1/n$ です。大きな有限体を作るときに、乱数で多項式を選んで既約性を試す方法が実用になるのはこのためです。 $q = 2$ で公式を使います。 $$ \begin{aligned} N_2(1) &= 2, & N_2(2) &= \tfrac12(2^2 - 2) = 1, & N_2(3) &= \tfrac13(2^3 - 2) = 2,\\ N_2(4) &= \tfrac14(2^4 - 2^2) = 3, & N_2(5) &= \tfrac15(2^5 - 2) = 6, & N_2(6) &= \tfrac16(2^6 - 2^3 - 2^2 + 2) = 9. \end{aligned} $$ $n = 6$ では $\mu(1) = 1$、$\mu(2) = \mu(3) = -1$、$\mu(6) = 1$ を使いました。$n = 4$ では $\mu(4) = 0$ なので $d = 1$ の項は現れません。次数 4 の 3 個は に並んでいる $x^4 + x + 1$、$x^4 + x^3 + 1$、$x^4 + x^3 + x^2 + x + 1$ です。検算: $\sum_{d \mid 6} d\,N_2(d) = 1\cdot 2 + 2 \cdot 1 + 3 \cdot 2 + 6 \cdot 9 = 64 = 2^6$。 ### 5.3. 原始元と原始多項式の個数 1. $\mathbb{F}_q$ の原始元はちょうど $\varphi(q - 1)$ 個ある。 2. $\mathbb{F}_q$ 上の次数 $n$ の原始多項式はちょうど $\varphi(q^n - 1)/n$ 個ある。 (1) $\mathbb{F}_q^{\times}$ は位数 $q - 1$ の巡回群（）なので、 の 2 です。 (2) $F = \mathbb{F}_{q^n}$ とし、$P$ を $F$ の原始元の集合とします。(1) より $|P| = \varphi(q^n - 1)$ です。$\gamma \in P$ とすると、$F$ の $0$ でない元はすべて $\gamma$ の冪なので $\mathbb{F}_q(\gamma) = F$ で、$\gamma$ の $\mathbb{F}_q$ 上の最小多項式 $m_\gamma$ の次数は $[F : \mathbb{F}_q] = n$ です。 の 2 より、$m_\gamma$ は $F$ に相異なる $n$ 個の根をもち、それらは $\gamma$ と同じ位数 $q^n - 1$ をもつので、すべて $P$ に属します。したがって $m_\gamma$ は原始多項式です。逆に、原始多項式 $f$ は定義により根 $\gamma \in P$ をもち、$f = m_\gamma$ です。 以上から、原始多項式の全体は $\{m_\gamma : \gamma \in P\}$ で、$P$ は各原始多項式の根の集合（$n$ 個ずつ）の交わりのない合併です。よって原始多項式の個数は $|P|/n$ です。 特に $n \mid \varphi(q^n - 1)$ が分かります。これは整数論の主張としては自明ではありません。 $g = x^4 + x^3 + x^2 + x + 1 \in \mathbb{F}_2[x]$ は に現れる既約多項式です。$(x + 1)\,g = x^5 + 1$ なので、$g$ の根 $\beta$ は $\beta^5 = 1$ を満たし、$\beta \ne 1$（$g(1) = 1$）なので位数は $5$ です。$5 \ne 15$ なので $g$ は原始多項式ではありません。 の記号では $g$ の根は $\alpha^3, \alpha^6, \alpha^{12}, \alpha^{9}$ です。次数 4 の原始多項式は $\varphi(15)/4 = 8/4 = 2$ 個で、$x^4 + x + 1$ と $x^4 + x^3 + 1$ です。 $\mathbb{F}_3$ 上でも同じことが起きます。 の $\mathbb{F}_9 = \mathbb{F}_3[i]$ で、$x^2 + 1$ の根 $i$ の位数は $4$ なので $x^2 + 1$ は原始多項式ではありません。一方 $1 + i$ は $(1 + i)^4 = -1$ より位数 $8$ の原始元で、共役元は $(1 + i)^3 = 1 + i^3 = 1 - i$ なので、最小多項式は $(x - 1 - i)(x - 1 + i) = (x - 1)^2 + 1 = x^2 + x + 2$ です。次数 2 の原始多項式は $\varphi(8)/2 = 2$ 個で、もう 1 つは $x^2 + 2x + 2$（根は $-1 \pm i$）です。 次の例は、原始多項式が実用上なぜ大切かを示します。漸化式で作る 0 と 1 の列は、いつかは同じ並びを繰り返します。その周期が、多項式の根の位数にちょうど一致する、という話です。途中で線形写像 $\lambda$ を持ち出すのは、体の元 $\alpha^k$ を 0 か 1 の 1 つの値に読み替えて、列として取り出すためです。 $\mathbb{F}_2$ の元の列 $(s_k)_{k \ge 0}$ を漸化式 $s_{k+4} = s_{k+1} + s_k$ で作る回路を、線形帰還シフトレジスタといいます。この漸化式は $x^4 = x + 1$、つまり多項式 $x^4 + x + 1$ に対応します。 $\lambda : \mathbb{F}_{16} \to \mathbb{F}_2$ を $0$ でない $\mathbb{F}_2$ 線形写像とし、$s_k = \lambda(\alpha^k)$ とおきます。$\alpha^{k+4} = \alpha^{k+1} + \alpha^k$ に $\lambda$ を施すと漸化式が成り立ちます。$\lambda$ として「$\alpha^3$ の係数」を取ると、 の表の左端の桁を読んで $$ (s_k) = 0,0,0,1,0,0,1,1,0,1,0,1,1,1,1,\ 0,0,0,1,\ldots $$ です。この列の周期はちょうど $15$ です。$t$ が周期なら、すべての $k$ で $\lambda((\alpha^t - 1)\alpha^k) = 0$ です。$1, \alpha, \alpha^2, \alpha^3$ は $\mathbb{F}_{16}$ を張るので、すべての $y \in \mathbb{F}_{16}$ で $\lambda((\alpha^t - 1)\,y) = 0$ です。$\alpha^t \ne 1$ なら $(\alpha^t - 1)\,y$ は $\mathbb{F}_{16}$ 全体を動くので $\lambda = 0$ となり矛盾します。よって $\alpha^t = 1$、つまり $15 \mid t$ です。 同じ議論で、$n$ 次の既約多項式に対応する漸化式の周期は根の位数に等しく、原始多項式のとき最大値 $q^n - 1$ になります。 の $x^4 + x^3 + x^2 + x + 1$ に対応する $s_{k+4} = s_{k+3} + s_{k+2} + s_{k+1} + s_k$ では、初期値 $0,0,0,1$ から $0,0,0,1,1,\ 0,0,0,1,1,\ldots$ となり周期は $5$ です。 ## 6. 平方元 1. $q$ が偶数なら、$\mathbb{F}_q$ のすべての元は平方元（ある $b$ により $b^2$ と書ける元）である。 2. $q$ が奇数なら、$\mathbb{F}_q^{\times}$ の平方元はちょうど $(q - 1)/2$ 個で、$0$ を含めると平方元は $(q + 1)/2$ 個である。 3. $\mathbb{F}_q$ のすべての元 $c$ は、ある $a, b \in \mathbb{F}_q$ により $c = a^2 + b^2$ と書ける。 (1) $q = 2^e$ のとき、2 乗写像は Frobenius 写像 $\sigma_2$ で、 より有限体では全単射です。 (2) $s : \mathbb{F}_q^{\times} \to \mathbb{F}_q^{\times}$, $s(b) = b^2$ は群準同型です。$b^2 = 1$ は $(b - 1)(b + 1) = 0$ と同値なので核は $\{1, -1\}$ で、$q$ が奇数なので $1 \ne -1$（標数が $2$ でない）、核の位数は $2$ です。 より像の位数は $(q - 1)/2$ です。$0 = 0^2$ を加えて $(q + 1)/2$ 個です。 (3) $q$ が偶数なら (1) より $c = a^2 + 0^2$ と書けます。$q$ を奇数とし、$S$ を平方元の集合とします。(2) より $|S| = (q + 1)/2$ です。$c - S = \{c - b^2 : b \in \mathbb{F}_q\}$ も $(q+1)/2$ 個の元をもちます（$y \mapsto c - y$ は全単射）。$|S| + |c - S| = q + 1 > q$ なので $S$ と $c - S$ は共通の元をもちます（交わらなければ合併が $q + 1$ 個の元をもってしまいます）。その元を $a^2 = c - b^2$ と書けば $c = a^2 + b^2$ です。 (3) は有限体上の 2 次形式の理論の出発点で、「$\mathbb{F}_q$ 上の 3 変数の 2 次形式は必ず自明でない零点をもつ」ことの核心です。実数では $-1$ が平方和で書けないのと対照的です。 $q$ を奇数の素数冪、$a \in \mathbb{F}_q^{\times}$ とする。 1. $a^{(q-1)/2}$ は $1$ か $-1$ である。$a$ が平方元なら $1$、平方元でなければ $-1$ である。 2. $-1$ が $\mathbb{F}_q$ の平方元であることと、$q \equiv 1 \pmod 4$ であることは同値である。 (1) $\gamma$ を原始元とし、$a = \gamma^j$ と書きます。$(a^{(q-1)/2})^2 = a^{q-1} = 1$ なので、$a^{(q-1)/2}$ は $x^2 - 1 = (x - 1)(x + 1)$ の根、つまり $\pm 1$ です。 より $$ a^{(q-1)/2} = \gamma^{j(q-1)/2} = 1 \iff (q - 1) \mid \frac{j\,(q - 1)}{2} \iff j \text{ が偶数} $$ です。一方、$j = 2i$ なら $a = (\gamma^i)^2$ は平方元です。逆に $a = b^2$、$b = \gamma^i$ なら $\gamma^{j - 2i} = 1$ で $(q - 1) \mid j - 2i$、$q - 1$ は偶数なので $j$ は偶数です。したがって「$a$ が平方元 $\iff$ $j$ が偶数 $\iff$ $a^{(q-1)/2} = 1$」です。 (2) (1) を $a = -1$ に使います。$(-1)^{(q-1)/2}$ は $(q-1)/2$ が偶数なら $1$、奇数なら $-1$ で、$1 \ne -1$ なので、$-1$ が平方元 $\iff$ $(q - 1)/2$ が偶数 $\iff$ $q \equiv 1 \pmod 4$ です。 $q = p$ のとき、これは です。 で見たように $-1$ は $\mathbb{F}_3$ では平方元でなく $\mathbb{F}_9$ では平方元ですが、これは $3 \equiv 3$、$9 \equiv 1 \pmod 4$ と合っています。一般に、奇素数 $p$ について $p^2 \equiv 1 \pmod 4$ なので、$-1$ は $\mathbb{F}_{p^2}$ で必ず平方元になります。 ## 7. 代数閉包 $\mathbb{F}_q$ 上の多項式の根を全部まとめて扱える「大きな入れ物」を作ります。一般の体の代数閉包の存在には選択公理が必要ですが、有限体では有限体の列の合併として具体的に構成できます。 体 $K$ の**代数閉包**とは、$K$ を含む体 $\Omega$ であって、(i) $\Omega$ のすべての元が $K$ 上代数的であり、(ii) $\Omega[x]$ の次数 $1$ 以上の多項式がすべて $\Omega$ に根をもつ（$\Omega$ が**代数的閉体**である）ものをいう。 $K$ を元の個数が $q$ の有限体とする。 1. $K$ の代数閉包 $\Omega$ が存在する。 2. $\Omega$ を $K$ の代数閉包とする。各 $n \ge 1$ について、$\Omega_n = \{a \in \Omega : a^{q^n} = a\}$ は $K$ を含み $q^n$ 個の元をもつ $\Omega$ の部分体で、$q^n$ 個の元をもつ部分体はこれだけである。$m \mid n$ なら $\Omega_m \subseteq \Omega_n$ で、$\Omega = \bigcup_{n \ge 1} \Omega_n$ である。 3. $K$ の代数閉包は、$K$ の元を動かさない同型を除いて一意である。 証明の方針です。$K$ を含む体を、元の個数が $q^{1!}, q^{2!}, q^{3!}, \ldots$ となるように次々に大きくして、その合併を $\Omega$ とします。階乗にするのは、$K_j$ から $d$ 段進んだ体への拡大の次数 $(j+1)(j+2)\cdots(j+d)$ が必ず $d$ の倍数になり、$K_j$ 上の次数 $d$ の既約多項式が根をもつようにするためです。こうすると $\Omega$ の中の任意の多項式の根が、ある段階の体に入ります。 **(1) 構成。** 体の列 $K = K_1 \subseteq K_2 \subseteq K_3 \subseteq \cdots$ で $|K_j| = q^{j!}$ となるものを帰納的に作ります。$K_j$ が作れたら、 により $K_j$ を含み $|K_j|^{j+1} = q^{(j+1)!}$ 個の元をもつ体 $K_{j+1}$ を取ります。$\Omega = \bigcup_{j} K_j$ とし、$a, b \in \Omega$ の和と積は、$a, b$ をともに含む $K_j$ の中で計算します。$K_j$ は $K_{j'}$（$j \le j'$）の部分体なので、結果は $j$ の取り方によりません。体の公理は有限個の元についての等式と逆元の存在なので、関係する元をすべて含む $K_j$ の中で成り立ち、$\Omega$ は体です。 (i) $a \in \Omega$ はある $K_j$ に属し、$a^{q^{j!}} = a$ なので（）、$K$ 係数の多項式 $x^{q^{j!}} - x$ の根で、$K$ 上代数的です。 (ii) $g \in \Omega[x]$ を次数 $1$ 以上の多項式とします。係数は有限個なので、ある $j$ について $g \in K_j[x]$ です。$K_j[x]$ は一意分解整域（）なので、$g$ を割り切るモニックな既約多項式 $h \in K_j[x]$ があります。$d = \deg h$ とします。$i = j + d$ とすると $|K_i| = |K_j|^{N}$、$N = i!/j! = (j+1)(j+2)\cdots(j+d)$ です。連続する $d$ 個の整数の中には $d$ の倍数があるので $d \mid N$ で、 の 1 より $h$ は $K_i$ に根をもちます。それは $g$ の根でもあります。 **(2)** $\Omega$ を任意の代数閉包とします。 より $\Omega_n$ は部分体で $|\Omega_n| \le q^n$、 の 2 より $K \subseteq \Omega_1 \subseteq \Omega_n$ です。$u = x^{q^n} - x$ とします。(ii) と の 1 を繰り返し使うと、$u$ は $\Omega[x]$ で 1 次式の積に分解します。 の証明と同じ計算 $u = (x - a)\bigl((x - a)^{q^n - 1} - 1\bigr)$ により、$u$ の根はすべて単根です。よって $u$ は相異なる $q^n$ 個の根をもち、$|\Omega_n| = q^n$ です。$E$ を $q^n$ 個の元をもつ部分体とすると、 の 2 より $E \subseteq \Omega_n$ で、個数が等しいので $E = \Omega_n$ です。$m \mid n$ なら、$a^{q^m} = a$ を $n/m$ 回繰り返して $a^{q^n} = a$ なので $\Omega_m \subseteq \Omega_n$ です。 $a \in \Omega$ とします。(i) より $a$ は $K$ 上代数的なので、 より $K(a)$ は $K$ 上有限次元で、$d = [K(a) : K]$ とすると $|K(a)| = q^d$、したがって $a^{q^d} = a$、$a \in \Omega_d$ です。よって $\Omega = \bigcup_n \Omega_n$ です。 **(3)** $\Omega$ を (1) で作った体、$\Omega'$ を別の代数閉包とします。(2) を $\Omega'$ に使い、$\Omega'_n$ を同様に定めます。(2) を $\Omega$ に使うと、$q^{j!}$ 個の元をもつ部分体の一意性から $K_j = \Omega_{j!}$ です。 $K$ の元を動かさない体の同型 $\tau_j : K_j \to \Omega'_{j!}$ を、$\tau_{j+1}$ が $\tau_j$ の拡張になるように帰納的に作ります。$\tau_1$ は $K = K_1 = \Omega'_1$ の恒等写像です。$\tau_j$ が作れたとします。$u = x^{q^{(j+1)!}} - x$ とすると、$K_{j+1}$ は $u$ の $K_j$ 上の分解体、$\Omega'_{(j+1)!}$ は $u$ の $\Omega'_{j!}$ 上の分解体です（どちらも $u$ の根全体からなる体です。 の 3）。$u$ の係数は $1$ と $-1$ で $\tau_j$ に動かされないので、同型の拡張の補題（）により $\tau_j$ は同型 $\tau_{j+1} : K_{j+1} \to \Omega'_{(j+1)!}$ に拡張されます。 $a \in K_j$ に対し $\tau(a) = \tau_j(a)$ と定めると、拡張になっているので $j$ の取り方によらず、$\tau : \Omega \to \Omega'$ は体の準同型で、単射です。任意の $n$ について $n \mid n!$ なので $\Omega'_n \subseteq \Omega'_{n!} = \tau(K_n)$ で、(2) より $\Omega' = \bigcup_n \Omega'_n$ なので $\tau$ は全射です。任意の 2 つの代数閉包はどちらも $\Omega$ と $K$ 上同型なので、互いに $K$ 上同型です。 $K$ の代数閉包を $\overline{\mathbb{F}}_q$ と書きます。(2) により、$\overline{\mathbb{F}}_q$ の中では「$q^n$ 元の体」$\mathbb{F}_{q^n}$ が文字どおり 1 つに決まり、$\mathbb{F}_{q^m} \subseteq \mathbb{F}_{q^n} \iff m \mid n$ です。$\overline{\mathbb{F}}_q$ は無限体で、$\overline{\mathbb{F}}_q = \overline{\mathbb{F}}_p$ です（$q = p^e$ なら $\mathbb{F}_{p^n} \subseteq \mathbb{F}_{q^n}$）。Frobenius 写像 $\sigma_q$ は $\overline{\mathbb{F}}_q$ の自己同型で、位数は無限です。 ## 8. 演習 $\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3 + x + 1)$ とし、$x$ の類を $\alpha$ とする。(a) $\alpha^j$（$0 \le j \le 6$）を $1, \alpha, \alpha^2$ の一次結合で表せ。(b) $\mathbb{F}_8$ の $0, 1$ 以外の元がすべて原始元であることを示せ。(c) $\mathbb{F}_2$ 上の 3 次の原始多項式をすべて求めよ。 (a) $\alpha^3 = \alpha + 1$ を使って、$\alpha^4 = \alpha^2 + \alpha$、$\alpha^5 = \alpha^3 + \alpha^2 = \alpha^2 + \alpha + 1$、$\alpha^6 = \alpha^3 + \alpha^2 + \alpha = \alpha^2 + 1$、$\alpha^7 = \alpha^3 + \alpha = 1$ です。 (b) $\mathbb{F}_8^{\times}$ の位数は $7$ で素数なので、$1$ 以外の元の位数は $7$ の約数で $1$ でない、つまり $7$ です（）。 の $\varphi(7) = 6$ と合います。 (c) より $\varphi(7)/3 = 2$ 個で、(b) より 3 次の既約多項式はすべて原始多項式です。$N_2(3) = 2$ なので、3 次の既約多項式は $x^3 + x + 1$（根は $\alpha, \alpha^2, \alpha^4$）と $x^3 + x^2 + 1$（根は $\alpha^3, \alpha^6, \alpha^5$）の 2 つです。後者が既約であることは $0, 1$ を代入して根がないことから分かります（3 次式は可約なら 1 次の因子をもちます）。 $\mathbb{F}_{64}$ の元のうち、どの真の部分体にも属さないものの個数を、部分体の束から直接数えよ。それが $6\,N_2(6)$ に一致することを確かめ、理由を説明せよ。 $64 = 2^6$ なので、 より部分体は $\mathbb{F}_2, \mathbb{F}_4, \mathbb{F}_8, \mathbb{F}_{64}$ です。真の部分体のうち極大なものは $\mathbb{F}_4$ と $\mathbb{F}_8$ で、共通部分は $\mathbb{F}_2$（$\gcd(2, 3) = 1$）です。包除原理により、真の部分体に属する元は $4 + 8 - 2 = 10$ 個、属さない元は $64 - 10 = 54$ 個です。 $a$ がどの真の部分体にも属さないことは $\mathbb{F}_2(a) = \mathbb{F}_{64}$、つまり最小多項式の次数が $6$ であることと同値です。6 次の既約多項式はそれぞれ $\mathbb{F}_{64}$ に相異なる $6$ 個の根をもち（）、異なる既約多項式は根を共有しないので、そのような元は $6\,N_2(6) = 6 \cdot 9 = 54$ 個です。 $\mathbb{F}_q$ の $0$ でない元すべての積は $-1$ であることを示せ。$q = p$ の場合は何という定理か。 の 3 の両辺を $x$ で割ると $x^{q-1} - 1 = \prod_{a \ne 0}(x - a)$ です。定数項を比べると $-1 = (-1)^{q-1} \prod_{a \ne 0} a$ です。$q$ が奇数なら $(-1)^{q-1} = 1$ なので $\prod a = -1$ です。$q$ が偶数なら $(-1)^{q-1} = -1$ で $\prod a = 1$ ですが、標数 $2$ では $1 = -1$ です。$q = p$ の場合は $(p-1)! \equiv -1 \pmod p$、すなわちウィルソンの定理です。 $\mathbb{F}_9 = \mathbb{F}_3[i]$（$i^2 = -1$）について、(a) 平方元をすべて求めよ。(b) $1 + i$ を 2 個の平方元の和で表せ。(c) $1 + i$ が平方元でないことを Euler の規準で確かめよ。 (a) $b$ と $-b$ の平方は等しいので、$\pm$ を除いた代表 $1,\ i,\ 1 + i,\ 1 + 2i$ の平方を計算します。$1^2 = 1$、$i^2 = 2$、$(1 + i)^2 = 2i$、$(1 + 2i)^2 = 1 + 4i + 4i^2 = 1 + i - 1 = i$ です。$0$ でない平方元は $1, 2, i, 2i$ の $4 = (9 - 1)/2$ 個で、 と合います。 (b) $1 + i = 1^2 + (1 + 2i)^2$ です。 (c) $(1 + i)^{(9-1)/2} = (1 + i)^4 = (2i)^2 = 4 i^2 = -1$ なので、 より平方元ではありません。実際 (a) の一覧に入っていません。 ## 参考文献 - R. Lidl, H. Niederreiter, *Finite Fields*, 2nd ed., Encyclopedia of Mathematics and its Applications 20, Cambridge University Press, 1997 — 第 2 章（有限体の構造）、第 3 章（有限体上の多項式）。 - R. Lidl, H. Niederreiter, *Introduction to Finite Fields and Their Applications*, revised ed., Cambridge University Press, 1994 — 第 2 章・第 3 章、線形帰還シフトレジスタは第 6 章。 - K. Ireland, M. Rosen, *A Classical Introduction to Modern Number Theory*, 2nd ed., Graduate Texts in Mathematics 84, Springer, 1990 — 第 7 章（有限体）。 - 雪江明彦『代数学 2 環と体とガロア理論』日本評論社、2010 — 有限体と Galois 理論の章。 - S. W. Golomb, *Shift Register Sequences*, Holden-Day, 1967 — シフトレジスタ列の周期と原始多項式。