有限体上の多項式：最小多項式・円分剰余類・トレースとノルム

0. この記事の要点

「$x^n - 1$ という式は、有限個の数だけを使う世界でどんな因数に分かれるか」を調べます。整数 $0, 1, \ldots, n-1$ を「2 倍する」「3 倍する」といった操作で互いに移り合うもの同士にグループ分けすると、そのグループがそのまま因数に対応する、というのが前半の話です。後半では、大きな数の世界の元を小さな世界の元に「まとめて落とす」2 つの写像（和を取るトレース、積を取るノルム）を調べます。読み終えると、$x^n - 1$ の分解を手で計算でき、その計算が符号の設計にどう効くかが分かります。

• $\mathbb{F}_q$ 上の最小多項式の根は、$q$ 乗を繰り返して得られる共役元の全体です。次数は Frobenius 写像の軌道の長さに等しくなります。
• $\gcd(n, q) = 1$ のとき、$x^n - 1$ の $\mathbb{F}_q$ 上の既約因子は、$\mathbb{Z}/n\mathbb{Z}$ を「$q$ 倍」で分けた軌道（$q$-円分剰余類）と 1 対 1 に対応します。因子の次数は軌道の大きさです。
• 円分多項式 $\Phi_n$ は $\mathbb{F}_q$ 上で、次数 $\mathrm{ord}_n(q)$ の既約多項式 $\varphi(n)/\mathrm{ord}_n(q)$ 個の積に分解します。
• トレース $\mathrm{Tr}(a) = a + a^q + \cdots + a^{q^{n-1}}$ とノルム $\mathrm{N}(a) = a \cdot a^q \cdots a^{q^{n-1}}$ はどちらも全射です。$\mathrm{Tr}(a) = 0 \iff a = b^q - b$、$\mathrm{N}(a) = 1 \iff a = b^{q-1}$ が、元の個数を数えるだけで証明できます。
• $\mathbb{F}_{q^n}$ は $\mathbb{F}_q$ 上の正規基底 $(a, a^q, \ldots, a^{q^{n-1}})$ をもちます。
• 平方因子のない多項式 $f$ の既約因子の個数は、線形写像 $g \mapsto g^q - g$ の核の次元として求まります（Berlekamp）。最後に、有限斜体が可換であること（Wedderburn）を円分多項式で証明します。

この記事で使う事前知識

• Frobenius 自己同型: 有限体の元を $q$ 乗する写像で、足し算と掛け算を保ちます。→ Frobenius 自己同型
• 原始元: 0 でない元がすべてその冪で書ける元のこと。→ 原始元
• 元の位数: 何乗したときに初めて単位元に戻るか、その回数。→ 元の位数
• 体の拡大と最小多項式: 体を大きな体に含めたものが拡大で、ある元を根にもつ次数最小のモニックな多項式が最小多項式です。→ 体の拡大
• 線形写像: 足し算とスカラー倍を保つ写像。→ 線形写像
• 標数: 1 を何回足すと 0 になるかを表す素数（または 0）。→ 標数

1. 動機

符号理論で最もよく使う多項式は $x^n - 1$ です。長さ $n$ の巡回符号は $x^n - 1$ の約数と 1 対 1 に対応するので、$x^n - 1$ が $\mathbb{F}_q$ 上でどう分解するかが分かれば、長さ $n$ の巡回符号が何個あり、それぞれ何次元かがすべて分かります（第 4 章）。

複素数の上では $x^n - 1 = \prod_k (x - e^{2\pi i k/n})$ と 1 次式に分解します。$\mathbb{F}_q$ の上では 1 の $n$ 乗根が $\mathbb{F}_q$ に入っているとは限らず、拡大体 $\mathbb{F}_{q^m}$ まで行って初めて全部そろいます。$\mathbb{F}_q$ 係数の既約因子は、拡大体の根を「$\mathbb{F}_q$ から見て区別できない組」にまとめたものです。その組を作るのが 第 1 章 の Frobenius 自己同型 $\sigma_q : a \mapsto a^q$ です。根 $\beta^j$ に $\sigma_q$ を施すと $\beta^{jq}$ になるので、根の組分けは指数 $j$ を $q$ 倍する操作の軌道、つまり整数の計算に帰着します。

後半では、拡大体 $\mathbb{F}_{q^n}$ の元を $\mathbb{F}_q$ に落とす 2 つの写像、トレースとノルムを調べます。トレースは $\mathbb{F}_{q^n}$ から $\mathbb{F}_q$ への線形写像をすべて記述し、符号の重み分布を調べる指標の計算の土台になります。

この記事の定理は、第 1 章の 3 つの定理、すなわち 定理 4.4［有限体の構造］、定理 5.1［有限体の構造］、定理 5.2［有限体の構造］ に乗っています。記号は第 1 章のとおりで、$q$ は素数 $p$ の冪、$\mathbb{F}_{q^n}$ は $\mathbb{F}_q$ を含む $q^n$ 元の体です。

2. 最小多項式と円分剰余類

2.1. 最小多項式は共役元を根にもつ

定義 2.1（有限体上の最小多項式）↗

$F$ を $\mathbb{F}_q$ を含む有限体、$\alpha \in F$ とする。$g(\alpha) = 0$ を満たす $0$ でない $g \in \mathbb{F}_q[x]$ のうち、次数が最小でモニックなものを $\alpha$ の $\mathbb{F}_q$ 上の最小多項式といい、$m_\alpha$ と書く。

命題 6.2［多項式環と体の拡大］ により、$m_\alpha$ は既約で、$g(\alpha) = 0 \iff m_\alpha \mid g$ が成り立ち、$\deg m_\alpha = [\mathbb{F}_q(\alpha) : \mathbb{F}_q]$ です。

定理 2.2（最小多項式と共役元）✓

$F$ を $\mathbb{F}_q$ を含む有限体で $|F| = q^N$ とし、$\alpha \in F$ とする。$d$ を $\alpha^{q^d} = \alpha$ となる最小の正の整数とすると、

$$m_\alpha(x) = (x - \alpha)(x - \alpha^q)(x - \alpha^{q^2}) \cdots (x - \alpha^{q^{d-1}})$$

であり、これら $d$ 個の根は相異なる。さらに $d = \deg m_\alpha$ は $N$ の約数で、$\mathbb{F}_q(\alpha)$ は $q^d$ 個の元をもつ。

証明（定理 2.2）

$n = \deg m_\alpha$ とします。$m_\alpha$ は $\mathbb{F}_q$ 上のモニックな既約多項式で $\alpha \in F$ を根にもつので、定理 5.1［有限体の構造］ の 2 より、$\alpha, \alpha^q, \ldots, \alpha^{q^{n-1}}$ は相異なり、$\alpha^{q^n} = \alpha$ で、$m_\alpha = \prod_{i=0}^{n-1}(x - \alpha^{q^i})$ です。$\alpha^{q^n} = \alpha$ より $d \le n$ です。$1 \le i \le n - 1$ では $\alpha^{q^i} \ne \alpha$（相異なるので）ですから $d \ge n$ で、$d = n$ です。同じ定理の 1 より $n \mid N$ です。$[\mathbb{F}_q(\alpha) : \mathbb{F}_q] = n$ なので $|\mathbb{F}_q(\alpha)| = q^n$ です。

∎

「最小多項式の次数は、$q$ 乗を何回繰り返すと元に戻るか」という読み方が、この記事の計算の基本です。

2.2. 円分剰余類と x^n − 1 の分解

以下、$n$ は正の整数で $\gcd(n, q) = 1$ とします。$q$ は $n$ を法として可逆なので、$q$ の $n$ を法とする位数 $\mathrm{ord}_n(q)$ が定まります（定義 2.1［原始根と平方剰余の相互法則］）。

定義 2.3（q-円分剰余類）↗

$\gcd(n, q) = 1$ とする。$s \in \mathbb{Z}/n\mathbb{Z}$ に対し

$$C_s = \{\, s,\ sq,\ sq^2,\ sq^3,\ \ldots \,\} \subseteq \mathbb{Z}/n\mathbb{Z}$$

を、$s$ を含む（$n$ を法とする）$q$-円分剰余類という。

次の段落は、「$q$ 倍を繰り返すと元に戻る」ことから、$\mathbb{Z}/n\mathbb{Z}$ がきれいなグループ（円分剰余類）に分かれることを確かめています。たとえば $n = 15$、$q = 2$ なら $1 \to 2 \to 4 \to 8 \to 1$ と一周するので、$\{1, 2, 4, 8\}$ が 1 つのグループです（下の例を参照）。

$\pi : \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$, $\pi(j) = qj$ は全単射です（$q q' \equiv 1 \pmod n$ となる $q'$ を取れば $j \mapsto q' j$ が逆写像）。$m = \mathrm{ord}_n(q)$ とすると $\pi^m = \mathrm{id}$ なので、$\pi$ は位数 $m$ の巡回群 $\mathbb{Z}/m\mathbb{Z}$ の作用を定め（定義 2.1［群の作用と Sylow の定理］）、$C_s$ はその軌道です。したがって円分剰余類は $\mathbb{Z}/n\mathbb{Z}$ を交わりなく分割し、$|C_s|$ は $s q^d \equiv s \pmod n$ となる最小の正の整数 $d$ に等しく、$m$ の約数です（定理 2.4［群の作用と Sylow の定理］）。

定理 2.4（$x^n − 1$ の有限体上の分解）✓

$\gcd(n, q) = 1$、$m = \mathrm{ord}_n(q)$ とする。

1. $\mathbb{F}_{q^k}$ が位数 $n$ の元をもつことと、$m \mid k$ であることは同値である。
2. $\beta \in \mathbb{F}_{q^m}$ を位数 $n$ の元とする。$\mathbb{F}_{q^m}[x]$ において $x^n - 1 = \prod_{j=0}^{n-1} (x - \beta^j)$ で、$n$ 個の根は相異なる。
3. $s \in \mathbb{Z}/n\mathbb{Z}$ に対し、$\beta^s$ の $\mathbb{F}_q$ 上の最小多項式は

$$M_s(x) = \prod_{j \in C_s} (x - \beta^j)$$

で、次数は $|C_s|$ である。 4. $S$ を円分剰余類の代表元の集合とすると、$\mathbb{F}_q[x]$ において

$$x^n - 1 = \prod_{s \in S} M_s(x)$$

で、右辺の因子は相異なるモニックな既約多項式である。特に $x^n - 1$ は重根をもたず、既約因子の個数は $q$-円分剰余類の個数に等しい。

証明（定理 2.4）

(1) $\mathbb{F}_{q^k}^{\times}$ は位数 $q^k - 1$ の巡回群です（定理 7.3［多項式環と体の拡大］）。位数 $n$ の元があれば 系 7.1［部分群と剰余類］ より $n \mid q^k - 1$ です。逆に $n \mid q^k - 1$ なら、原始元 $\gamma$ に対し $\gamma^{(q^k - 1)/n}$ の位数は $n$ です（補題 2.3［有限体の構造］ の 3）。$n \mid q^k - 1$ は $q^k \equiv 1 \pmod n$ のことで、補題 2.2［原始根と平方剰余の相互法則］ の 1 より $m \mid k$ と同値です。

(2) $\beta^0, \beta^1, \ldots, \beta^{n-1}$ は相異なり（命題 6.5［群論入門］）、$(\beta^j)^n = (\beta^n)^j = 1$ なのですべて $x^n - 1$ の根です。補題 2.2［有限体の構造］ の 2 より $x^n - 1 = \prod_j (x - \beta^j) \cdot g$ で、次数と最高次の係数から $g = 1$ です。

(3) $\beta^s$ の共役元は $(\beta^s)^{q^i} = \beta^{s q^i}$ です。定理 6.3［群論入門］ より $\beta^{a} = \beta^{b} \iff a \equiv b \pmod n$ なので、$(\beta^s)^{q^d} = \beta^s$ となる最小の正の $d$ は $s q^d \equiv s \pmod n$ となる最小の正の $d$、つまり $|C_s|$ です。定理 2.2 より $\beta^s$ の最小多項式は $\prod_{i=0}^{d-1}(x - \beta^{sq^i})$ で、$\{s q^i \bmod n : 0 \le i \le d - 1\} = C_s$ なので、これは $M_s$ です。

(4) 円分剰余類は $\mathbb{Z}/n\mathbb{Z}$ の分割なので、(2) の積を類ごとにまとめて $x^n - 1 = \prod_{s \in S} \prod_{j \in C_s}(x - \beta^j) = \prod_{s \in S} M_s$ です。(3) より各 $M_s$ は $\mathbb{F}_q$ 係数のモニックな既約多項式です。異なる類の $M_s$ は根を共有しないので相異なります。

∎

ノート

$\gcd(n, q) \ne 1$ の場合は、$n = p^k n'$（$p \nmid n'$）と書くと、補題 7.1［多項式環と体の拡大］ より $x^n - 1 = (x^{n'} - 1)^{p^k}$ です。したがって分解は $n'$ の場合に帰着しますが、すべての因子が $p^k$ 重になります。符号理論で符号長と $q$ が互いに素であると仮定するのは、この重複を避けるためです。

例 2.5（x¹⁵ − 1 の F₂ 上の分解）

$n = 15$、$q = 2$ とします。$2^4 = 16 \equiv 1 \pmod{15}$ で、$2, 4, 8 \not\equiv 1$ なので $m = \mathrm{ord}_{15}(2) = 4$ です。$2$-円分剰余類は、各元を $2$ 倍していって

$$C_0 = \{0\},\quad C_1 = \{1, 2, 4, 8\},\quad C_3 = \{3, 6, 12, 9\},\quad C_5 = \{5, 10\},\quad C_7 = \{7, 14, 13, 11\}$$

の 5 個です。したがって $x^{15} - 1$ は $\mathbb{F}_2$ 上で次数 $1, 4, 4, 2, 4$ の 5 個の既約多項式の積です。$\mathbb{F}_{16} = \mathbb{F}_2[x]/(x^4 + x + 1)$ の原始元 $\alpha$（例 3.2［有限体の構造］）を $\beta$ に取ると、

$$\begin{aligned} M_0 &= x + 1, & M_1 &= x^4 + x + 1, & M_3 &= x^4 + x^3 + x^2 + x + 1,\\ M_5 &= x^2 + x + 1, & M_7 &= x^4 + x^3 + 1 && \end{aligned}$$

です。$M_1$ は $\alpha$ の最小多項式そのものです。$M_5$ は位数 $3$ の元 $\alpha^5, \alpha^{10}$ を根にもつ 2 次式で、$x^3 - 1 = (x - 1)(x^2 + x + 1)$ から決まります。$M_3$ は位数 $5$ の元を根にもち、$x^5 - 1 = (x - 1)(x^4 + x^3 + x^2 + x + 1)$ から決まります。$M_7$ は残りの因子で、$C_7 = -C_1$ なので根は $M_1$ の根の逆元、係数は $M_1$ の係数を逆順に並べたものです。

例 2.6（x²³ − 1（F₂ 上）と x¹¹ − 1（F₃ 上））

$n = 23$、$q = 2$。 $2$ の冪を $23$ で割った余りは $2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1$ で、$\mathrm{ord}_{23}(2) = 11$ です。円分剰余類は

$$C_0 = \{0\},\quad C_1 = \{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\},\quad C_5 = \{5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22\}$$

の 3 個なので、$x^{23} - 1$ は次数 $1, 11, 11$ の既約多項式の積です。具体的には

$$x^{23} - 1 = (x + 1)\,(x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1)\,(x^{11} + x^{10} + x^6 + x^5 + x^4 + x^2 + 1)$$

です。$2^{11} - 1 = 2047 = 23 \cdot 89$ なので、位数 $23$ の元は $\mathbb{F}_{2^{11}}$ にあります。11 次の因子が生成する長さ 23 の巡回符号が二元 Golay 符号です。

$n = 11$、$q = 3$。 $3$ の冪を $11$ で割った余りは $3, 9, 5, 4, 1$ で、$\mathrm{ord}_{11}(3) = 5$ です。円分剰余類は $\{0\}$、$\{1, 3, 4, 5, 9\}$、$\{2, 6, 7, 8, 10\}$ で、

$$x^{11} - 1 = (x - 1)\,(x^5 + x^4 + 2x^3 + x^2 + 2)\,(x^5 + 2x^3 + x^2 + 2x + 2)$$

です。5 次の因子は三元 Golay 符号を生成します。どちらの場合も $\{1, \ldots, n-1\}$ が 2 つの類に分かれ、一方は $n$ を法とする平方剰余の全体です（$23$ では $1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18$）。

3. 円分多項式と多項式の位数

3.1. 円分多項式

$x^n - 1$ の根を位数ごとにまとめた多項式が円分多項式です。まず整数係数の多項式として定義し、それから $\mathbb{F}_q$ に落とします。整数係数であることの証明に、次の補題を使います。

補題 3.1（モニック多項式による割り算）✓

$R$ を $1 \ne 0$ の可換環、$g \in R[x]$ を次数 $m$ のモニック多項式とする。任意の $f \in R[x]$ に対し、$f = g s + r$ かつ「$r = 0$ または $\deg r < m$」を満たす $s, r \in R[x]$ がただ 1 組存在する。

証明（補題 3.1）

存在を $\deg f$ についての帰納法で示します。$f = 0$ または $\deg f < m$ なら $s = 0$、$r = f$ とします。$\deg f = k \ge m$ とし、$f$ の最高次の項を $c x^k$ とすると、$g$ がモニックなので $f_1 = f - c x^{k-m} g$ は $0$ であるか次数が $k$ より小さいです。帰納法の仮定から $f_1 = g s_1 + r$ と書け、$f = g\,(s_1 + c x^{k-m}) + r$ です。

一意性を示します。$g s + r = g s' + r'$ とすると $g\,(s - s') = r' - r$ です。$s \ne s'$ なら、$g$ がモニックなので左辺の最高次の係数は $s - s'$ の最高次の係数に等しく $0$ でないので、左辺の次数は $m + \deg(s - s') \ge m$ です。右辺は $0$ か次数が $m$ より小さいので矛盾です。よって $s = s'$、したがって $r = r'$ です。

∎

定義 3.2（円分多項式）↗

正の整数 $n$ に対し、乗法についての位数がちょうど $n$ である複素数（1 の原始 $n$ 乗根）の全体を $P_n$ とする。

$$\Phi_n(x) = \prod_{\zeta \in P_n} (x - \zeta)$$

を $n$ 番目の円分多項式という。

$\zeta_n = e^{2\pi i/n}$ とすると、$x^n - 1$ の複素数の根は $\zeta_n^k$（$0 \le k \le n - 1$）の $n$ 個で、これらは $\zeta_n$ が生成する位数 $n$ の巡回群 $\mu_n$ をなします。位数 $n$ の複素数は $\mu_n$ の生成元なので、$P_n = \{\zeta_n^k : 1 \le k \le n,\ \gcd(k, n) = 1\}$ で、$\deg \Phi_n = \varphi(n)$ です（補題 2.3［有限体の構造］ の 2）。

補題 3.3（円分多項式は整数係数）✓

すべての $n \ge 1$ について、$x^n - 1 = \prod_{d \mid n} \Phi_d(x)$ が成り立ち、$\Phi_n$ は整数係数のモニック多項式である。

証明（補題 3.3）

$\mu_n$ の元 $z$ の位数は $n$ の約数です（系 7.1［部分群と剰余類］）。逆に $d \mid n$ のとき、位数 $d$ の複素数 $z$ は $z^d = 1$ より $z^n = 1$ を満たし $\mu_n$ に属します。したがって $\mu_n$ は $P_d$（$d \mid n$）の交わりのない合併で、

$$x^n - 1 = \prod_{z \in \mu_n}(x - z) = \prod_{d \mid n} \prod_{\zeta \in P_d} (x - \zeta) = \prod_{d \mid n}\Phi_d(x)$$

です（最初の等号は 補題 2.2［有限体の構造］ の 2 と次数の比較）。

$\Phi_n$ は 1 次のモニック多項式の積なのでモニックです。整数係数であることを $n$ についての帰納法で示します。$\Phi_1 = x - 1$ です。$n > 1$ とし、$d < n$ では $\Phi_d \in \mathbb{Z}[x]$ とします。$g = \prod_{d \mid n,\ d < n} \Phi_d$ は整数係数のモニック多項式です。補題 3.1 を $R = \mathbb{Z}$ に使って $x^n - 1 = g s + r$（$s, r \in \mathbb{Z}[x]$、$r = 0$ または $\deg r < \deg g$）と書きます。一方 $\mathbb{C}[x]$ では $x^n - 1 = g\,\Phi_n + 0$ です。補題 3.1 を $R = \mathbb{C}$ に使うと、割り算の一意性から $s = \Phi_n$、$r = 0$ です。よって $\Phi_n = s \in \mathbb{Z}[x]$ です。

∎

$\Phi_n$ の係数を $p$ を法として読んだ $\mathbb{F}_p[x]$ の多項式を $\overline{\Phi}_n$ と書きます。係数を $p$ を法として読む写像 $\mathbb{Z}[x] \to \mathbb{F}_p[x]$ は環準同型なので、$\mathbb{F}_p[x]$ でも $x^n - 1 = \prod_{d \mid n} \overline{\Phi}_d$ です。小さい例は $\Phi_1 = x - 1$、$\Phi_2 = x + 1$、$\Phi_3 = x^2 + x + 1$、$\Phi_4 = x^2 + 1$、$\Phi_5 = x^4 + x^3 + x^2 + x + 1$、$\Phi_6 = x^2 - x + 1$ です。

定理 3.4（円分多項式の有限体上の分解）✓

$n$ を正の整数とする。

1. $L$ を標数 $p$ の体、$\beta \in L$ を乗法についての位数が $n$ の元とすると、$L[x]$ において

$$\overline{\Phi}_n(x) = \prod_{\substack{0 \le j \le n - 1 \\ \gcd(j, n) = 1}} (x - \beta^j)$$

である。すなわち $\overline{\Phi}_n$ の根は、$\beta$ が生成する群の位数 $n$ の元の全体である。 2. $\gcd(n, q) = 1$、$m = \mathrm{ord}_n(q)$ とする。$\overline{\Phi}_n$ は $\mathbb{F}_q[x]$ において、相異なる $\varphi(n)/m$ 個のモニックな既約多項式の積に分解し、その次数はすべて $m$ である。

次の証明のねらいは、(1) で「$\overline{\Phi}_n$ の根は位数がちょうど $n$ の元だけ」と確かめ、(2) でそれらの根を 2.2 の円分剰余類（$n$ と互いに素な剰余だけを集めたもの）に振り分けることです。(1) の帰納法は、$n$ より小さい約数の分を先に片づけて、残りが $\overline{\Phi}_n$ だと見るためのものです。

証明（定理 3.4）

(1) $n$ についての帰納法で、すべての $L$ と $\beta$ について同時に示します。$G = \langle \beta \rangle$ とします。$G$ の $n$ 個の元 $\beta^j$ は相異なる $x^n - 1$ の根なので、補題 2.2［有限体の構造］ の 2 と次数の比較から $x^n - 1 = \prod_{j=0}^{n-1}(x - \beta^j)$ です。$G$ の元の位数は $n$ の約数なので、$d \mid n$ に対し $Q_d = \prod (x - z)$（積は $G$ の位数 $d$ の元 $z$ をわたる）とおくと

$$x^n - 1 = \prod_{d \mid n} Q_d(x)$$

です。$d \mid n$、$d < n$ とします。補題 2.3［有限体の構造］ の 3 より、$G$ の位数 $d$ の元は、位数 $d$ のただ 1 つの部分群 $\langle \beta^{n/d} \rangle$ の生成元、すなわち $(\beta^{n/d})^j$（$\gcd(j, d) = 1$）です。$\beta^{n/d}$ は位数 $d$ の元なので、帰納法の仮定から $\overline{\Phi}_d = Q_d$ です。したがって

$$\overline{\Phi}_n \cdot \prod_{d \mid n,\ d < n} Q_d = \prod_{d \mid n} \overline{\Phi}_d = x^n - 1 = Q_n \cdot \prod_{d \mid n,\ d < n} Q_d$$

で、$L[x]$ は整域なので $\overline{\Phi}_n = Q_n$ です（$n = 1$ のときは $\overline{\Phi}_1 = x - 1 = Q_1$ で、帰納法の出発点も含まれています）。$G$ の位数 $n$ の元は $\beta^j$（$\gcd(j, n) = 1$）です（同じ補題の 1）。

(2) 定理 2.4 の 1 より $\mathbb{F}_{q^m}$ に位数 $n$ の元 $\beta$ があります。$(\mathbb{Z}/n\mathbb{Z})^{\times}$ を $n$ と互いに素な剰余の集合とします。$\gcd(s, n) = 1$ なら $\gcd(sq^i, n) = 1$ なので、$C_s \subseteq (\mathbb{Z}/n\mathbb{Z})^{\times}$ で、$(\mathbb{Z}/n\mathbb{Z})^{\times}$ は円分剰余類の合併です。$s$ が $n$ を法として可逆なので、$s q^d \equiv s \pmod n$ は $q^d \equiv 1 \pmod n$ と同値で、$|C_s| = m$ です。したがって $(\mathbb{Z}/n\mathbb{Z})^{\times}$ は $\varphi(n)/m$ 個の類に分かれます。(1) の積を類ごとにまとめると、$\overline{\Phi}_n = \prod_s M_s$（$s$ は $(\mathbb{Z}/n\mathbb{Z})^{\times}$ に含まれる類の代表元）で、定理 2.4 の 3 と 4 より各 $M_s$ は次数 $m$ の相異なるモニックな既約多項式です。

∎

有理数体の上では $\Phi_n$ は常に既約ですが、有限体の上では $q$ が $n$ を法とする原始根であるとき（$m = \varphi(n)$）に限って既約です。たとえば $\mathrm{ord}_5(2) = 4 = \varphi(5)$ なので $\Phi_5$ は $\mathbb{F}_2$ 上既約で、$\mathrm{ord}_7(2) = 3$ なので $\Phi_7$ は $\mathbb{F}_2$ 上 2 個の 3 次式 $(x^3 + x + 1)(x^3 + x^2 + 1)$ に分解します。$\Phi_{15}$ は次数 $8$ で、例 2.5 の $M_1 M_7$ です。

3.2. 多項式の位数

定義 3.5（多項式の位数）↗

$f \in \mathbb{F}_q[x]$ を $f \ne x$ なるモニックな既約多項式とする。$f \mid x^e - 1$ となる最小の正の整数 $e$ を $f$ の位数（周期）といい、$\mathrm{ord}(f)$ と書く。

命題 3.6（既約多項式の位数）✓

$f \in \mathbb{F}_q[x]$ を次数 $n$ のモニックな既約多項式、$f \ne x$ とし、$\alpha \in \mathbb{F}_{q^n}$ を $f$ の根とする。

1. 正の整数 $e$ について $f \mid x^e - 1 \iff \alpha^e = 1$。したがって $\mathrm{ord}(f)$ は $\alpha$ の乗法についての位数に等しく、$q^n - 1$ の約数で、$q$ と互いに素である。
2. $e = \mathrm{ord}(f)$ とすると $n = \mathrm{ord}_e(q)$ である。
3. $f$ が原始多項式であることと、$\mathrm{ord}(f) = q^n - 1$ であることは同値である。
4. $\gcd(e, q) = 1$ とする。位数 $e$ のモニックな既約多項式は $\overline{\Phi}_e$ の既約因子の全体で、$\varphi(e)/\mathrm{ord}_e(q)$ 個あり、次数はすべて $\mathrm{ord}_e(q)$ である。

証明（命題 3.6）

$f$ は $\mathbb{F}_{q^n}$ に根をもちます（定理 5.1［有限体の構造］ の 1）。$f$ は $\alpha$ の最小多項式です（モニックな既約多項式で $\alpha$ を根にもつので $m_\alpha \mid f$ から $f = m_\alpha$）。$f \ne x$ なので $\alpha \ne 0$ です。

(1) $f \mid x^e - 1 \iff \alpha^e - 1 = 0$ は最小多項式の性質です。$\alpha \in \mathbb{F}_{q^n}^{\times}$ の位数は $q^n - 1$ の約数（系 7.1［部分群と剰余類］）で、$q^n - 1$ は $p$ で割り切れないので $q$ と互いに素です。

(2) 定理 2.2 より、$n$ は $\alpha^{q^d} = \alpha$ となる最小の正の $d$ です。$\alpha \ne 0$ なので $\alpha^{q^d} = \alpha \iff \alpha^{q^d - 1} = 1 \iff e \mid q^d - 1 \iff q^d \equiv 1 \pmod e$ です。そのような最小の $d$ は $\mathrm{ord}_e(q)$ です。

(3) 原始多項式の定義は「根 $\alpha$ が $\mathbb{F}_{q^n}$ の原始元」、つまり $\alpha$ の位数が $q^n - 1$ であることで、(1) より $\mathrm{ord}(f) = q^n - 1$ と同値です。

(4) $f$ の位数が $e$ なら、(1) より $\alpha$ の位数は $e$ で、定理 3.4 の 1（$L = \mathbb{F}_{q^n}$、$\beta = \alpha$）より $\overline{\Phi}_e(\alpha) = 0$、したがって $f \mid \overline{\Phi}_e$ です。逆に $f$ が $\overline{\Phi}_e$ の既約因子なら、定理 3.4 の 2 の証明で得た分解 $\overline{\Phi}_e = \prod_s M_s$ と既約分解の一意性（定理 2.5［多項式環と体の拡大］）より、$f$ はある $M_s$（$\gcd(s, e) = 1$）で、その根 $\beta^s$ の位数は $e$ なので、(1) より $\mathrm{ord}(f) = e$ です。個数と次数は 定理 3.4 の 2 です。

∎

たとえば $\mathbb{F}_2$ 上の 4 次の既約多項式 3 個の位数は、$x^4 + x + 1$ と $x^4 + x^3 + 1$ が $15$、$x^4 + x^3 + x^2 + x + 1$ が $5$ です。(2) より、位数が分かれば次数が決まります: $\mathrm{ord}_{15}(2) = \mathrm{ord}_5(2) = 4$。

4. トレースとノルム

この節では $K = \mathbb{F}_q$、$F = \mathbb{F}_{q^n}$、$\sigma = \sigma_q$ とします。$F$ は $K$ 上 $n$ 次元のベクトル空間です。

定義 4.1（トレースとノルム）↗

$a \in F$ に対し

$$\mathrm{Tr}_{F/K}(a) = \sum_{i=0}^{n-1} a^{q^i} = a + a^q + \cdots + a^{q^{n-1}}, \qquad \mathrm{N}_{F/K}(a) = \prod_{i=0}^{n-1} a^{q^i} = a^{(q^n - 1)/(q - 1)}$$

を $a$ の（$F$ から $K$ への）トレース、ノルムという。拡大を明示しなくてよいときは $\mathrm{Tr}$、$\mathrm{N}$ と書く。

ノルムの第 2 の表示は $1 + q + \cdots + q^{n-1} = (q^n - 1)/(q - 1)$ によります。トレースは $a$ の共役元（定理 4.4［有限体の構造］ の Galois 群による像）すべての和、ノルムは積です。

定理 4.2（トレースとノルムの基本性質）✓

$a, b \in F$、$c \in K$ とする。

1. $\mathrm{Tr}(a) \in K$、$\mathrm{N}(a) \in K$。
2. $\mathrm{Tr}(a + b) = \mathrm{Tr}(a) + \mathrm{Tr}(b)$、$\mathrm{Tr}(ca) = c\,\mathrm{Tr}(a)$、$\mathrm{Tr}(c) = nc$。また $\mathrm{N}(ab) = \mathrm{N}(a)\,\mathrm{N}(b)$、$\mathrm{N}(ca) = c^n\,\mathrm{N}(a)$、$\mathrm{N}(c) = c^n$。
3. $\mathrm{Tr}(a^q) = \mathrm{Tr}(a)$、$\mathrm{N}(a^q) = \mathrm{N}(a)$。
4. $\mathrm{Tr} : F \to K$ は全射で、各 $c \in K$ の逆像はちょうど $q^{n-1}$ 個の元からなる。$\mathrm{N}(a) = 0 \iff a = 0$ で、$\mathrm{N} : F^{\times} \to K^{\times}$ は全射な群準同型であり、各 $c \in K^{\times}$ の逆像はちょうど $(q^n - 1)/(q - 1)$ 個の元からなる。
5. （推移性）$M$ を $K \subseteq M \subseteq F$ なる中間体とすると、$\mathrm{Tr}_{F/K} = \mathrm{Tr}_{M/K} \circ \mathrm{Tr}_{F/M}$、$\mathrm{N}_{F/K} = \mathrm{N}_{M/K} \circ \mathrm{N}_{F/M}$。
6. $a$ の $K$ 上の最小多項式を $m_a = x^d + c_{d-1} x^{d-1} + \cdots + c_1 x + c_0$ とすると、$d \mid n$ で

$$\mathrm{Tr}(a) = -\frac{n}{d}\, c_{d-1}, \qquad \mathrm{N}(a) = \bigl((-1)^d c_0\bigr)^{n/d}.$$

次の証明のうち、つまずきやすい (4) の流れを先に述べます。トレースの核は多項式 $T(x)$ の根の集合なので、元の個数は高々 $q^{n-1}$ 個で、核の次元は $n - 1$ 以下です。すると像の次元は 1 以上になりますが、像は 1 次元空間 $K$ の部分空間なので $K$ 全体になる、という順です。(6) は、最小多項式の係数からトレースとノルムを読み取る式です。

証明（定理 4.2）

(1) $\sigma$ は体の自己同型で $a^{q^n} = a$ なので、$\sigma(\mathrm{Tr}(a)) = \sum_{i=0}^{n-1} a^{q^{i+1}} = \sum_{i=1}^{n-1} a^{q^i} + a = \mathrm{Tr}(a)$ です。つまり $\mathrm{Tr}(a)^q = \mathrm{Tr}(a)$ で、命題 2.4［有限体の構造］ の 4 より $\mathrm{Tr}(a) \in K$ です。和を積に替えた同じ計算で $\mathrm{N}(a)^q = \mathrm{N}(a)$、$\mathrm{N}(a) \in K$ です。

(2) 各 $\sigma^i$ は加法と乗法を保ち、$c \in K$ を動かさないので、$\mathrm{Tr}(a + b) = \sum_i (a^{q^i} + b^{q^i})$、$\mathrm{Tr}(ca) = \sum_i c\, a^{q^i}$、$\mathrm{Tr}(c) = \sum_i c = nc$ です。ノルムも $\mathrm{N}(ab) = \prod_i a^{q^i} b^{q^i}$、$\mathrm{N}(c) = \prod_i c = c^n$ で、$\mathrm{N}(ca) = \mathrm{N}(c)\,\mathrm{N}(a)$ です。

(3) $\mathrm{Tr}(a^q) = \mathrm{Tr}(\sigma(a)) = \sum_i \sigma^{i+1}(a) = \sigma(\mathrm{Tr}(a))$ で、(1) より $\mathrm{Tr}(a) \in K$ なので $\sigma(\mathrm{Tr}(a)) = \mathrm{Tr}(a)$ です。ノルムも同様です。

(4) (2) より $\mathrm{Tr}$ は $K$ 線形写像 $F \to K$ です。核は多項式 $T(x) = x + x^q + \cdots + x^{q^{n-1}}$ の $F$ における根の集合で、$\deg T = q^{n-1}$ なので核の元は $q^{n-1}$ 個以下です（補題 2.2［有限体の構造］）。核の次元を $k$ とすると $q^k \le q^{n-1}$ で $k \le n - 1$ です。次元定理（定理 7.3［ベクトル空間と線形変換］）より像の次元は $n - k \ge 1$ で、像は 1 次元空間 $K$ の部分空間なので $K$ 全体、したがって $k = n - 1$ です。$\mathrm{Tr}(a_0) = c$ となる $a_0$ を 1 つ取ると、$c$ の逆像は $a_0 + \mathrm{Ker}\,\mathrm{Tr}$ で、$q^{n-1}$ 個の元をもちます。

$\mathrm{N}(a) = a^{(q^n-1)/(q-1)}$ なので、体に零因子がないことから $\mathrm{N}(a) = 0 \iff a = 0$ です。(2) より $\mathrm{N} : F^{\times} \to K^{\times}$ は群準同型です。$\gamma$ を $F$ の原始元とします。補題 2.3［有限体の構造］ の 1 より、$\mathrm{N}(\gamma) = \gamma^{(q^n-1)/(q-1)}$ の位数は $(q^n - 1)\big/\gcd\bigl(\tfrac{q^n-1}{q-1},\, q^n - 1\bigr) = q - 1$ です。$K^{\times}$ の位数は $q - 1$ なので $\mathrm{N}(\gamma)$ は $K^{\times}$ を生成し、$\mathrm{N}$ は全射です。系 5.2［群の準同型定理］ より核の位数は $(q^n - 1)/(q - 1)$ で、各 $c$ の逆像は核の剰余類（補題 4.3［群の準同型定理］）なので同じ個数の元をもちます。

(5) 定理 4.4［有限体の構造］ の 3 より $|M| = q^d$（$d \mid n$）です。$n = dt$ とします。$M$ 上の Frobenius 写像は $a \mapsto a^{q^d}$ なので $\mathrm{Tr}_{F/M}(a) = \sum_{j=0}^{t-1} a^{q^{dj}}$ で、

$$\mathrm{Tr}_{M/K}\bigl(\mathrm{Tr}_{F/M}(a)\bigr) = \sum_{i=0}^{d-1} \Bigl(\sum_{j=0}^{t-1} a^{q^{dj}}\Bigr)^{q^i} = \sum_{i=0}^{d-1} \sum_{j=0}^{t-1} a^{q^{dj + i}} = \sum_{k=0}^{n-1} a^{q^k}$$

です。2 番目の等号は $\sigma^i$ が加法を保つこと、3 番目は $0 \le k \le n - 1$ が $k = dj + i$（$0 \le i < d$、$0 \le j < t$）とただ 1 通りに書けることによります。和を積に替えればノルムの推移性です。

(6) 定理 2.2 より $d \mid n$ で、$m_a = \prod_{i=0}^{d-1}(x - a^{q^i})$ です。展開して係数を比べると $c_{d-1} = -\sum_{i=0}^{d-1} a^{q^i}$、$c_0 = (-1)^d \prod_{i=0}^{d-1} a^{q^i}$ です。$M = K(a)$ は $q^d$ 個の元をもつ中間体なので、これは $c_{d-1} = -\mathrm{Tr}_{M/K}(a)$、$c_0 = (-1)^d\,\mathrm{N}_{M/K}(a)$ を意味します。$a \in M$ なので、(2) を拡大 $F/M$（次数 $n/d$）に使って $\mathrm{Tr}_{F/M}(a) = (n/d)\,a$、$\mathrm{N}_{F/M}(a) = a^{n/d}$ です。(5) より

$$\mathrm{Tr}_{F/K}(a) = \mathrm{Tr}_{M/K}\bigl(\tfrac{n}{d}\, a\bigr) = -\frac{n}{d}\, c_{d-1}, \qquad \mathrm{N}_{F/K}(a) = \mathrm{N}_{M/K}(a)^{n/d} = \bigl((-1)^d c_0\bigr)^{n/d}$$

です。

∎

$\mathrm{Tr}(a)$ は「$a$ を掛ける」という $K$ 線形写像 $F \to F$ の行列のトレースにも一致します。$K = \mathbb{F}_p$ の場合のこの事実は 補題 6.2［代数体の整数環と Dedekind 整域］ にあります。この記事では共役元の和という定義だけを使います。

(4) の全射性は無限体でも成り立つとは限りません。実数体から見た複素数体のノルム $z \mapsto |z|^2$ は負の数を値に取りません。有限体ではトレースもノルムも必ず全射で、しかも値が完全に均等に分布します。

定理 4.3（Hilbert の定理 90（有限体））✓

$a \in F = \mathbb{F}_{q^n}$ とする。

1. $\mathrm{Tr}_{F/K}(a) = 0$ であることと、ある $b \in F$ により $a = b^q - b$ と書けることは同値である。
2. $\mathrm{N}_{F/K}(a) = 1$ であることと、ある $b \in F^{\times}$ により $a = b^{q-1}$ と書けることは同値である。

証明（定理 4.3）

(1) $\wp : F \to F$, $\wp(b) = b^q - b$ は $K$ 線形です（$\sigma$ が $K$ 線形なので）。核は $\{b : b^q = b\} = K$ で（命題 2.4［有限体の構造］ の 4）、1 次元です。次元定理（定理 7.3［ベクトル空間と線形変換］）より像は $n - 1$ 次元で、$q^{n-1}$ 個の元をもちます。定理 4.2 の 2 と 3 より $\mathrm{Tr}(b^q - b) = \mathrm{Tr}(b^q) - \mathrm{Tr}(b) = 0$ なので、$\wp$ の像は $\mathrm{Ker}\,\mathrm{Tr}$ に含まれます。同じ定理の 4 より $\mathrm{Ker}\,\mathrm{Tr}$ も $q^{n-1}$ 個の元をもつので、両者は一致します。

(2) $\psi : F^{\times} \to F^{\times}$, $\psi(b) = b^{q-1}$ は群準同型で、核は $\{b : b^{q-1} = 1\} = K^{\times}$（位数 $q - 1$）です。系 5.2［群の準同型定理］ より像の位数は $(q^n - 1)/(q - 1)$ です。$\mathrm{N}(b^{q-1}) = \mathrm{N}(b^q)\,\mathrm{N}(b)^{-1} = 1$ なので像は $\mathrm{Ker}\,\mathrm{N}$ に含まれ、定理 4.2 の 4 より $\mathrm{Ker}\,\mathrm{N}$ の位数も $(q^n - 1)/(q - 1)$ なので、両者は一致します。

∎

一般の巡回拡大に対する Hilbert の定理 90 は 定理 4.1［S 単数と Kummer 理論］（乗法版）と 命題 8.2［群のコホモロジーと群の拡大］（加法版）にあります。有限体では、上のように「像と核の元の個数が一致する」ことを確かめるだけで証明が終わります。

系 4.4（標数 2 の 2 次方程式）✓

$q = 2^e$、$c \in \mathbb{F}_q$ とする。方程式 $x^2 + x + c = 0$ が $\mathbb{F}_q$ に解をもつことと、$\mathrm{Tr}_{\mathbb{F}_q/\mathbb{F}_2}(c) = 0$ であることは同値である。解 $b$ があるとき、解は $b$ と $b + 1$ の 2 つである。

証明（系 4.4）

標数 $2$ では $-1 = 1$ なので、$b^2 + b + c = 0 \iff c = b^2 - b$ です。定理 4.3 の 1 を拡大 $\mathbb{F}_q/\mathbb{F}_2$ に使うと（Frobenius 写像は 2 乗）、そのような $b \in \mathbb{F}_q$ があることは $\mathrm{Tr}_{\mathbb{F}_q/\mathbb{F}_2}(c) = 0$ と同値です。$b$ が解なら $(b + 1)^2 + (b + 1) + c = b^2 + b + c = 0$ で $b + 1$ も解で、2 次式の根は 2 個以下です。

∎

標数が $2$ でなければ 2 次方程式は平方完成して「判別式が平方元か」で判定できますが、標数 $2$ では $2$ で割れないので平方完成ができません。その代わりをするのがこの系です。一般の $a x^2 + b x + c = 0$（$a, b \ne 0$）は $x = (b/a)\,y$ とおくと $y^2 + y + ac/b^2 = 0$ になるので、$\mathrm{Tr}(ac/b^2) = 0$ が解をもつ条件です。

4.1. トレース形式と双対基底

命題 4.5（トレース形式の非退化性と双対基底）✓

1. $\langle a, b \rangle = \mathrm{Tr}_{F/K}(ab)$ は $F$ 上の対称な $K$ 双線形形式で、非退化である。すなわち、すべての $b \in F$ で $\mathrm{Tr}(ab) = 0$ なら $a = 0$ である。
2. $(e_1, \ldots, e_n)$ を $F$ の $K$ 上の基底とすると、$\mathrm{Tr}(e_i f_j) = \delta_{ij}$（$i = j$ のとき $1$、それ以外は $0$）を満たす基底 $(f_1, \ldots, f_n)$ がただ 1 つ存在する（双対基底）。このとき任意の $a \in F$ は $a = \sum_{i=1}^{n} \mathrm{Tr}(a f_i)\, e_i$ と表される。

証明（命題 4.5）

(1) 対称性は $ab = ba$ から、双線形性は 定理 4.2 の 2 から従います。$a \ne 0$ とします。$b \mapsto ab$ は $F$ の全単射なので、$\{\mathrm{Tr}(ab) : b \in F\} = \mathrm{Tr}(F) = K$（定理 4.2 の 4）で、$\mathrm{Tr}(ab) \ne 0$ となる $b$ があります。

(2) $F^{*}$ を $K$ 線形写像 $F \to K$ の全体とし、$\Lambda : F \to F^{*}$ を $\Lambda(a)(x) = \mathrm{Tr}(ax)$ で定めます。$\Lambda$ は $K$ 線形で、(1) より単射です。$\dim_K F^{*} = n = \dim_K F$（定理 2.3［双対空間と商空間］ の 1）なので、$\Lambda$ は全単射です（系 7.5［ベクトル空間と線形変換］）。$(e^1, \ldots, e^n)$ を $(e_i)$ の双対基底（$e^j(e_i) = \delta_{ij}$）とし、$f_j = \Lambda^{-1}(e^j)$ とおくと、$\mathrm{Tr}(f_j e_i) = e^j(e_i) = \delta_{ij}$ です。$\Lambda^{-1}$ は線形同型なので $(f_j)$ は $F$ の基底です。$f_j'$ も同じ条件を満たせば $\Lambda(f_j')$ と $\Lambda(f_j)$ は基底 $(e_i)$ の上で一致するので等しく、単射性から $f_j' = f_j$ です。最後に $a = \sum_i a_i e_i$（$a_i \in K$）と書くと $\mathrm{Tr}(a f_j) = \sum_i a_i\, \mathrm{Tr}(e_i f_j) = a_j$ です。

∎

系 4.6（線形汎関数はトレースで書ける）✓

$K$ 線形写像 $\lambda : F \to K$ はすべて、ただ 1 つの $a \in F$ により $\lambda(x) = \mathrm{Tr}_{F/K}(ax)$ と書ける。

証明（系 4.6）

命題 4.5 の証明の $\Lambda : F \to F^{*}$ が全単射であることの言い換えです。

∎

これは符号理論で繰り返し使われます。$\mathbb{F}_{q^n}$ 上の符号を $\mathbb{F}_q$ 上の符号に落とす操作や、$\mathbb{F}_q$ の加法指標 $x \mapsto e^{2\pi i\,\mathrm{Tr}(ax)/p}$ の分類は、どちらもこの系の応用です。

例 4.7（F₁₆ のトレースとノルム）

$\mathbb{F}_{16} = \mathbb{F}_2[x]/(x^4 + x + 1)$、$\alpha$ を $x$ の類とし、$\mathbb{F}_4 = \{0, 1, \alpha^5, \alpha^{10}\}$ とします（例 3.2［有限体の構造］）。

$\mathbb{F}_{16}/\mathbb{F}_2$。 定理 4.2 の 6 で読めます。$\alpha, \alpha^2, \alpha^4, \alpha^8$ の最小多項式 $x^4 + x + 1$ は $x^3$ の係数が $0$ なのでトレースは $0$、$\alpha^3, \alpha^6, \alpha^9, \alpha^{12}$ の最小多項式 $x^4 + x^3 + x^2 + x + 1$ と $\alpha^7, \alpha^{11}, \alpha^{13}, \alpha^{14}$ の最小多項式 $x^4 + x^3 + 1$ は $x^3$ の係数が $1$ なのでトレースは $1$ です。$\alpha^5, \alpha^{10}$ は最小多項式 $x^2 + x + 1$（$d = 2$）で、$\mathrm{Tr} = -(4/2) \cdot 1 = 0$、$\mathrm{Tr}(1) = 4 \cdot 1 = 0$ です。トレースが $0$ の元は $0, 1, \alpha, \alpha^2, \alpha^4, \alpha^5, \alpha^8, \alpha^{10}$ の $8 = 2^{4-1}$ 個、$1$ の元も $8$ 個です。

$\mathbb{F}_{16}/\mathbb{F}_4$。 $\mathrm{Tr}_{\mathbb{F}_{16}/\mathbb{F}_4}(a) = a + a^4$、$\mathrm{N}_{\mathbb{F}_{16}/\mathbb{F}_4}(a) = a^5$ です。冪の表から、たとえば $\mathrm{Tr}(\alpha) = \alpha + \alpha^4 = 1$、$\mathrm{Tr}(\alpha^3) = \alpha^3 + \alpha^{12} = \alpha^{10}$、$\mathrm{Tr}(\alpha^6) = \alpha^6 + \alpha^{9} = \alpha^5$ と計算できます。全体は次のとおりです。

値	トレースがその値になる元
$0$	$0,\ 1,\ \alpha^5,\ \alpha^{10}$
$1$	$\alpha,\ \alpha^2,\ \alpha^4,\ \alpha^8$
$\alpha^5$	$\alpha^6,\ \alpha^7,\ \alpha^9,\ \alpha^{13}$
$\alpha^{10}$	$\alpha^3,\ \alpha^{11},\ \alpha^{12},\ \alpha^{14}$

どの値も $4 = 4^{2-1}$ 回ずつ取られます。推移性の確認: $\mathrm{Tr}_{\mathbb{F}_4/\mathbb{F}_2}(\alpha^5) = \alpha^5 + \alpha^{10} = 1$、$\mathrm{Tr}_{\mathbb{F}_4/\mathbb{F}_2}(1) = 0$ なので、$\mathbb{F}_2$ へのトレースが $1$ になるのは表の下 2 行の 8 個で、上の計算と一致します。ノルムは $\mathrm{N}(\alpha^j) = \alpha^{5j}$ で、$j \bmod 3$ だけで決まり、$1, \alpha^5, \alpha^{10}$ をそれぞれ $5 = (16 - 1)/(4 - 1)$ 回ずつ取ります。

5. 正規基底

定義 5.1（正規基底・線形化多項式）↗

1. $a \in F = \mathbb{F}_{q^n}$ について、$(a, a^q, a^{q^2}, \ldots, a^{q^{n-1}})$ が $F$ の $K = \mathbb{F}_q$ 上の基底であるとき、これを正規基底という。
2. $c_0, \ldots, c_k \in F$ に対する $L(x) = \sum_{i=0}^{k} c_i\, x^{q^i}$ の形の多項式を（$q$ についての）線形化多項式という。

正規基底では、$q$ 乗写像が座標の巡回シフトになります: $b = \sum_i b_i a^{q^i}$ なら $b^q = \sum_i b_i a^{q^{i+1}}$ で、$a^{q^n} = a$ です。回路で $q$ 乗が配線の付け替えだけで済むので、有限体の演算回路の設計で好まれます。$\mathrm{Tr}(x)$ や $x^q - x$ は線形化多項式の例です。

補題 5.2（線形化多項式は線形写像を定める）✓

$L(x) = \sum_{i=0}^{k} c_i x^{q^i}$ を $F = \mathbb{F}_{q^n}$ 係数の線形化多項式とする。

1. 写像 $F \to F$, $a \mapsto L(a)$ は $K$ 線形で、$\sum_i c_i \sigma^i$ に等しい。
2. $k \le n - 1$ で、すべての $a \in F$ について $L(a) = 0$ なら、$c_0 = \cdots = c_k = 0$ である。

証明（補題 5.2）

(1) $L(a) = \sum_i c_i \sigma^i(a)$ で、各 $\sigma^i$ は $K$ 線形（定理 4.4［有限体の構造］ の 1）、$c_i$ を掛ける写像も $K$ 線形です。

(2) $L$ が $0$ でない多項式なら、その次数は $q^k \le q^{n-1} < q^n$ 以下なので、根は $q^n$ 個より少ないです（補題 2.2［有限体の構造］）。$F$ の $q^n$ 個の元がすべて根なら $L$ は零多項式で、$x^{q^0}, \ldots, x^{q^k}$ は次数の異なる単項式なので係数 $c_i$ はすべて $0$ です。

∎

(2) は「$\mathrm{id}, \sigma, \ldots, \sigma^{n-1}$ は $F$ 上一次独立である」という主張です。

定理 5.3（有限体の正規基底定理）✓

任意の有限体の拡大 $\mathbb{F}_{q^n}/\mathbb{F}_q$ は正規基底をもつ。

この定理の証明の方針は、$\sigma$（$q$ 乗写像）を $K$ 上の線形写像と見て、「ある 1 つの元 $a$ に $\sigma$ を繰り返し施すだけで、$F$ 全体が生成される」ことを示すことです。そのために、線形写像を巡回的なブロックに分ける有理標準形を使い、ブロックが 1 つしかないことを前の補題から導きます。

証明（定理 5.3）

$\sigma$ を $n$ 次元 $K$ ベクトル空間 $F$ の線形写像とみます。$g = \sum_{i=0}^{n-1} c_i x^i \in K[x]$ が $g(\sigma) = \sum_i c_i \sigma^i = 0$ を満たすなら、補題 5.2 の 2 より $g = 0$ です。つまり、$\sigma$ を代入して $0$ になる $0$ でない多項式の次数は $n$ 以上です。

有理標準形（定理 7.2［加群と PID 上の構造定理］）により、$x$ を $\sigma$ として作用させた $K[x]$ 加群として

$$F \cong K[x]/(d_1) \oplus \cdots \oplus K[x]/(d_s), \qquad d_1 \mid d_2 \mid \cdots \mid d_s$$

で、$d_s$ は $\sigma$ の最小多項式、$d_1 \cdots d_s$ は特性多項式（次数 $n$）です。$d_s(\sigma) = 0$ なので上で見たとおり $\deg d_s \ge n$ で、$\sum_i \deg d_i = n$、各 $d_i$ は定数でないので、$s = 1$ かつ $\deg d_1 = n$ です。

したがって $K[x]$ 加群の同型 $\theta : K[x]/(d_1) \to F$ があります。$a = \theta(1 + (d_1))$ とおくと、$\theta(x^i + (d_1)) = \sigma^i(a) = a^{q^i}$ です。$K[x]/(d_1)$ で $1, x, \ldots, x^{n-1}$ の類は $K$ 上一次独立です（一次関係があれば、次数 $n$ 未満の $0$ でない多項式が次数 $n$ の $d_1$ の倍数になってしまいます）。$\theta$ は $K$ 線形同型なので $a, a^q, \ldots, a^{q^{n-1}}$ も一次独立で、$n$ 次元空間の $n$ 個の一次独立なベクトルなので基底です（命題 5.7［ベクトル空間と線形変換］ の 3）。

∎

$\sigma^n = \mathrm{id}$ なので $d_1 \mid x^n - 1$ で、次数が等しくどちらもモニックなので、$\sigma$ の最小多項式も特性多項式も $x^n - 1$ です。証明の要点は、$F$ が $\sigma$ について「巡回ベクトル」$a$ をもつことでした。

例 5.4（F₈ の正規基底）

$\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3 + x + 1)$、$\alpha$ を $x$ の類とします。$\alpha^3 = \alpha + 1$、$\alpha^4 = \alpha^2 + \alpha$、$\alpha^5 = \alpha^2 + \alpha + 1$、$\alpha^6 = \alpha^2 + 1$ です。

$(\alpha, \alpha^2, \alpha^4)$ は正規基底ではありません。$\alpha + \alpha^2 + \alpha^4 = \mathrm{Tr}(\alpha) = 0$（最小多項式 $x^3 + x + 1$ の $x^2$ の係数が $0$）で、一次従属だからです。

$a = \alpha^3$ を取ると、共役元は $\alpha^3,\ \alpha^6,\ \alpha^{12} = \alpha^5$ です。基底 $(1, \alpha, \alpha^2)$ についての座標は $\alpha^3 = (1, 1, 0)$、$\alpha^6 = (1, 0, 1)$、$\alpha^5 = (1, 1, 1)$ です。$c_1(1,1,0) + c_2(1,0,1) + c_3(1,1,1) = 0$ とすると、第 3 成分から $c_2 + c_3 = 0$、第 2 成分から $c_1 + c_3 = 0$、第 1 成分から $c_1 + c_2 + c_3 = 0$ で、$c_1 = c_2 = c_3$ かつ $3c_1 = c_1 = 0$ となり一次独立です。よって $(\alpha^3, \alpha^6, \alpha^5)$ は正規基底です。正規基底を与える元のトレースは $0$ でない（基底の元の和が $0$ になれないので）ことに注意してください。ここでは $\mathrm{Tr}(\alpha^3) = \alpha^3 + \alpha^6 + \alpha^5 = 1$ です。

6. Berlekamp の分解法

$\mathbb{F}_q$ 上の多項式を既約因子に分解する古典的な方法を述べます。鍵は、$g^q - g = \prod_{c \in \mathbb{F}_q}(g - c)$ という恒等式です。

定義 6.1（Berlekamp 部分代数）↗

$f \in \mathbb{F}_q[x]$ を次数 $n \ge 1$ のモニック多項式、$R = \mathbb{F}_q[x]/(f)$ とする。

$$B(f) = \{\, g \in R : g^q = g \,\}$$

を $f$ の Berlekamp 部分代数という。

$R$ は標数 $p$ の可換環なので、補題 7.1［多項式環と体の拡大］ より $g \mapsto g^q$ は加法を保ち、$c \in \mathbb{F}_q$ に対し $(cg)^q = c\,g^q$ です。したがって $g \mapsto g^q - g$ は $R$ の $\mathbb{F}_q$ 線形写像で、$B(f)$ はその核、つまり $R$ の部分空間です。基底 $(1, x, \ldots, x^{n-1})$ について $g \mapsto g^q$ の行列 $Q$ を作れば（第 $i$ 列が $x^{qi} \bmod f$ の係数）、$B(f)$ は $Q - I$ の核として連立一次方程式で求まります。

以下、$f, h \in \mathbb{F}_q[x]$（$f \ne 0$）に対し、$f$ と $h$ が生成するイデアルのモニックな生成元（命題 7.2［イデアルと剰余環］）を $\gcd(f, h)$ と書きます。$d = \gcd(f, h)$ は $f$ と $h$ を割り切り、$d = uf + vh$ と書けるので、$f$ と $h$ の共通の約数はすべて $d$ を割り切ります。

定理 6.2（Berlekamp の定理）✓

$f \in \mathbb{F}_q[x]$ をモニック多項式とし、$f = f_1 f_2 \cdots f_r$ と相異なるモニックな既約多項式の積に書けるとする（$f$ は平方因子をもたない）。

1. $g \in \mathbb{F}_q[x]$ について、$g^q \equiv g \pmod f$ であることと、各 $i$ に対し $g \equiv c_i \pmod{f_i}$ となる $c_i \in \mathbb{F}_q$ が存在することは同値である。このとき $c_i$ は一意に定まる。
2. $B(f)$ の $\mathbb{F}_q$ 上の次元は、既約因子の個数 $r$ に等しい。特に、$f$ が既約であることと $\dim B(f) = 1$ は同値である。
3. $g^q \equiv g \pmod f$ のとき、(1) の $c_i$ を使って、各 $c \in \mathbb{F}_q$ について $\gcd(f, g - c) = \prod_{i\,:\,c_i = c} f_i$ であり、

$$f = \prod_{c \in \mathbb{F}_q} \gcd(f,\ g - c)$$

が成り立つ。$g$ が $f$ を法としてどの定数とも合同でなければ、右辺の因子のうち少なくとも 2 つは $1$ でなく、$f$ の自明でない分解が得られる。

証明の見通しは次のとおりです。(1) は、恒等式 $g^q - g = \prod_c (g - c)$ を使って、条件 $g^q \equiv g$ を「$f$ の既約因子ごとに $g$ が定数になる」と言い換えます。(2) では、その定数の組 $(c_1, \ldots, c_r)$ が $B(f)$ の元と 1 対 1 に対応することから、次元が因子の個数 $r$ になります。(3) では、定数 $c$ ごとに $\gcd(f, g - c)$ を取ることで、因子が実際に切り分けられます。

証明（定理 6.2）

(1) 命題 2.4［有限体の構造］ の 3 の恒等式 $x^q - x = \prod_{c \in \mathbb{F}_q}(x - c)$ に $x = g$ を代入すると

$$g^q - g = \prod_{c \in \mathbb{F}_q} (g - c)$$

です。$f_1, \ldots, f_r$ は相異なる既約元なので、既約分解の一意性（定理 2.5［多項式環と体の拡大］）より、$f \mid h$ は「すべての $i$ で $f_i \mid h$」と同値です。また $f_i$ は素元（補題 2.4［多項式環と体の拡大］）なので、$f_i \mid \prod_c (g - c)$ は「ある $c$ で $f_i \mid g - c$」と同値です。以上から $f \mid g^q - g$ は「各 $i$ に対し $f_i \mid g - c_i$ となる $c_i$ がある」と同値です。$f_i$ が $g - c$ と $g - c'$ をともに割り切れば定数 $c' - c$ を割り切り、$\deg f_i \ge 1$ なので $c = c'$ です。

(2) (1) により写像 $\Psi : B(f) \to \mathbb{F}_q^{\,r}$, $\Psi(g) = (c_1, \ldots, c_r)$ が定まります（$f$ を法とする類の代表の取り方によりません）。$g \equiv c_i$、$g' \equiv c_i' \pmod{f_i}$ なら $g + g' \equiv c_i + c_i'$、$ag \equiv a c_i$ なので $\Psi$ は $\mathbb{F}_q$ 線形です。$\Psi(g) = 0$ なら、すべての $i$ で $f_i \mid g$、したがって $f \mid g$ で、$g$ は $R$ の零元です。よって $\Psi$ は単射です。

全射性を示します。$h_i = \prod_{j \ne i} f_j$ とします。$f_i$ と $h_i$ が生成するイデアルを $(d)$ とすると、$d \mid f_i$ で $f_i$ は既約なので、$d$ は定数か $f_i$ の定数倍です。後者なら $f_i \mid h_i$ で、$f_i$ は素元なのである $j \ne i$ で $f_i \mid f_j$、どちらもモニックで既約なので $f_i = f_j$ となり矛盾します。よって $d$ は定数で、$u_i h_i + v_i f_i = 1$ となる $u_i, v_i \in \mathbb{F}_q[x]$ があります。$e_i = u_i h_i$ とおくと、$e_i \equiv 1 \pmod{f_i}$ で、$j \ne i$ なら $f_j \mid e_i$ です。$(c_1, \ldots, c_r) \in \mathbb{F}_q^{\,r}$ に対し $g = \sum_i c_i e_i$ とすると $g \equiv c_i \pmod{f_i}$ で、(1) より $g$ の類は $B(f)$ に属し、$\Psi(g) = (c_1, \ldots, c_r)$ です。したがって $\Psi$ は線形同型で、$\dim B(f) = r$ です。

(3) $d_c = \gcd(f, g - c)$ とします。$d_c$ は $f$ のモニックな約数で、$f$ の既約因子は相異なるので、$d_c$ は $f_1, \ldots, f_r$ のいくつかの積です。$f_i \mid d_c$ は「$f_i \mid f$ かつ $f_i \mid g - c$」、つまり $f_i \mid g - c$ と同値で、(1) の一意性より $c_i = c$ と同値です。よって $d_c = \prod_{i : c_i = c} f_i$ です。各 $i$ はちょうど 1 つの $c$（$= c_i$）に対して現れるので $\prod_c d_c = \prod_i f_i = f$ です。$c_i$ がすべて同じ値 $c$ なら $f \mid g - c$ で $g$ は定数 $c$ と合同です。そうでなければ $c_i$ は 2 つ以上の値を取り、対応する $d_c$ が $1$ でも $f$ でもありません。

∎

(2) の $\Psi$ は、環の同型 $R \cong \prod_i \mathbb{F}_q[x]/(f_i)$（中国剰余定理。2 個の因子の場合は 命題 2.4［加群と PID 上の構造定理］）のもとで、$B(f)$ が各成分の部分体 $\mathbb{F}_q$ の直積に対応することを言っています。各成分 $\mathbb{F}_q[x]/(f_i)$ は体で、その中で $g^q = g$ を満たす元は $\mathbb{F}_q$ の元だけだからです。

例 6.3（x⁸ + x⁶ + x⁴ + x³ + 1 を F₂ 上で分解する）

$f = x^8 + x^6 + x^4 + x^3 + 1 \in \mathbb{F}_2[x]$ とします。形式微分は $f' = 8x^7 + 6x^5 + 4x^3 + 3x^2 = x^2$ です。$f$ が平方因子 $h^2$ をもてば $h \mid f'$ ですが（$f = h^2 k$ なら $f' = 2hh'k + h^2k'$）、$f' = x^2$ の約数 $x$ は $f(0) = 1$ より $f$ を割り切らないので、$f$ は平方因子をもちません。

$q = 2$ なので、$g = \sum_{i=0}^{7} g_i x^i$ に対し $g^2 = \sum_i g_i x^{2i}$ です。$x^{2i} \bmod f$ を計算します。$x^8 \equiv x^6 + x^4 + x^3 + 1$ を使って順に、

$$\begin{aligned} x^{8} &\equiv x^6 + x^4 + x^3 + 1, & x^{10} &\equiv x^5 + x^4 + x^3 + x^2 + 1,\\ x^{12} &\equiv x^7 + x^6 + x^5 + x^4 + x^2, & x^{14} &\equiv x^5 + x^4 + x^3 + x + 1 \end{aligned}$$

です（$x^0, x^2, x^4, x^6$ はそのまま）。$g^2 = g$ を $x^j$ の係数ごとに書くと

$$\begin{aligned} x^0 &: g_0 + g_4 + g_5 + g_7 = g_0, & x^1 &: g_7 = g_1, & x^2 &: g_1 + g_5 + g_6 = g_2, & x^3 &: g_4 + g_5 + g_7 = g_3,\\ x^4 &: g_2 + g_4 + g_5 + g_6 + g_7 = g_4, & x^5 &: g_5 + g_6 + g_7 = g_5, & x^6 &: g_3 + g_4 + g_6 = g_6, & x^7 &: g_6 = g_7 \end{aligned}$$

です。$x^0$ と $x^3$ の式から $g_3 = 0$、$x^6$ の式から $g_4 = g_3 = 0$、$x^0$ の式から $g_5 = g_7$、さらに $g_1 = g_6 = g_7$、$g_2 = g_1 + g_5 + g_6 = g_7$ です（$x^4$ の式は $4 g_7 = 0$ で自動的に成り立ちます）。解は $g_0$ と $g_7$ を自由に選べる 2 次元空間で、

$$B(f) = \{\,0,\ 1,\ h,\ h + 1\,\}, \qquad h = x^7 + x^6 + x^5 + x^2 + x$$

です。定理 6.2 の 2 より $f$ の既約因子はちょうど 2 個です。互除法で $\gcd(f, h) = x^6 + x^5 + x^4 + x + 1$、$\gcd(f, h + 1) = x^2 + x + 1$ が得られ、

$$x^8 + x^6 + x^4 + x^3 + 1 = (x^2 + x + 1)\,(x^6 + x^5 + x^4 + x + 1)$$

です。既約因子が 2 個なので、右辺の 2 つの因子はどちらも既約です。右辺を展開して左辺に一致することも直接確かめられます。

7. Wedderburn の小定理

最後に、この記事で準備した円分多項式を使って、環と体 の 注意 5.4［環と体の基礎］ で予告されている定理を証明します。斜体とは、$1 \ne 0$ で、$0$ でない元がすべて（両側の）逆元をもつ環のことです。乗法の可換性は仮定しません。

定理 7.1（Wedderburn の小定理）✓

有限個の元からなる斜体は可換である。すなわち体である。

証明の方針は、有限斜体 $D$ の元の個数 $q^n$ を、類等式で「中心の分」と「それ以外の共役類の分」に分けて数えることです。$n > 1$ と仮定すると、円分多項式の値 $\Phi_n(q)$ が $q - 1$ を割り切ることが出ます。ところが $\Phi_n(q)$ の絶対値は $q - 1$ より大きいので、割り切ることはできず、矛盾から $n = 1$（可換）が従います。

証明（定理 7.1）

$D$ を有限斜体とし、$Z = \{z \in D : zx = xz\ (\forall x \in D)\}$ を中心とします。

個数の準備。 $Z$ は $0, 1$ を含み、和・積・加法の逆元で閉じています。$z \in Z$、$z \ne 0$ なら、$zx = xz$ の両辺に左右から $z^{-1}$ を掛けて $x z^{-1} = z^{-1} x$ なので $z^{-1} \in Z$ です。よって $Z$ は可換な斜体、つまり有限体で、$|Z| = q$ とおきます。$D$ は $Z$ 上のベクトル空間（スカラー倍は左からの積）で、有限次元です。次元を $n$ とすると $|D| = q^n$ です。$n = 1$ を示せば $D = Z$ で可換です。

$x \in D$ に対し $C(x) = \{y \in D : yx = xy\}$ とします。$Z$ と同じ計算で $C(x)$ は $Z$ を含む斜体で、$Z$ 上の部分空間でもあるので、$|C(x)| = q^{d(x)}$（$1 \le d(x) \le n$）と書けます。$D^{\times} = D \setminus \{0\}$ は位数 $q^n - 1$ の群で、$C(x) \setminus \{0\}$ は $x \ne 0$ の $D^{\times}$ における中心化群（位数 $q^{d(x)} - 1$）です。ラグランジュの定理（定理 6.1［部分群と剰余類］）より $q^{d(x)} - 1 \mid q^n - 1$ で、補題 4.1［有限体の構造］ の 1 より $d(x) \mid n$ です。

類等式。 群 $D^{\times}$ の中心は $Z \setminus \{0\}$（位数 $q - 1$）です。類等式（定理 3.1［群の作用と Sylow の定理］）より、元を 2 個以上含む共役類の代表元 $x_1, \ldots, x_r$ について

$$q^n - 1 = (q - 1) + \sum_{i=1}^{r} \frac{q^n - 1}{q^{d_i} - 1}, \qquad d_i = d(x_i)$$

です。$x_i$ は中心に属さないので $C(x_i) \ne D$、したがって $d_i \mid n$ かつ $d_i < n$ です。

円分多項式による評価。 $n > 1$ と仮定して矛盾を導きます。$d \mid n$、$d < n$ のとき、補題 3.3 より

$$x^n - 1 = \prod_{e \mid n} \Phi_e(x) = (x^d - 1) \cdot \Phi_n(x) \cdot \prod_{\substack{e \mid n,\ e \nmid d \\ e \ne n}} \Phi_e(x)$$

で、右辺の因子はすべて整数係数です（$x^d - 1 = \prod_{e \mid d}\Phi_e$ で、$d$ の約数は $n$ の約数であり $n$ とは異なります）。$x = q$ を代入すると、整数 $\Phi_n(q)$ は $q^n - 1$ と $(q^n - 1)/(q^d - 1)$ の両方を割り切ります。類等式の $q^n - 1$ と和の各項が $\Phi_n(q)$ で割り切れるので、

$$\Phi_n(q) \mid q - 1$$

です。一方 $\Phi_n(q) = \prod_{\zeta \in P_n}(q - \zeta)$ で、$n > 1$ なので $\zeta \in P_n$ は $1$ でない絶対値 $1$ の複素数です。$\zeta = \cos\theta + i \sin\theta$ と書くと $\cos\theta < 1$ で、

$$|q - \zeta|^2 = (q - \cos\theta)^2 + \sin^2\theta = q^2 - 2q\cos\theta + 1 > q^2 - 2q + 1 = (q - 1)^2$$

です。よって $|\Phi_n(q)| > (q - 1)^{\varphi(n)} \ge q - 1 \ge 1$ です。$0$ でない整数 $q - 1$ が、それより絶対値の大きい整数で割り切れることはないので矛盾です。したがって $n = 1$ で、$D = Z$ は可換です。

∎

この証明は E. Witt によるものです。定理 5.3［環と体の基礎］ と合わせると、有限の世界では「零因子がない環」「斜体」「体」の 3 つが一致します。有限射影平面で Desargues の定理から Pappus の定理が従うことは、この定理の幾何学的な言い換えです。

8. 演習

演習 8.1易

$21$ を法とする $2$-円分剰余類をすべて求め、$x^{21} - 1$ の $\mathbb{F}_2$ 上の既約因子の個数と次数を答えよ。そのうち $\overline{\Phi}_{21}$ の因子はどれか。

解答

$2$ の冪を $21$ で割った余りは $2, 4, 8, 16, 11, 1$ なので $\mathrm{ord}_{21}(2) = 6$ です。剰余類は

$$\{0\},\ \{1, 2, 4, 8, 16, 11\},\ \{3, 6, 12\},\ \{5, 10, 20, 19, 17, 13\},\ \{7, 14\},\ \{9, 18, 15\}$$

の 6 個で、定理 2.4 より既約因子は 6 個、次数は $1, 6, 3, 6, 2, 3$（合計 $21$）です。$21$ と互いに素な剰余からなる類は $C_1$ と $C_5$ なので、$\overline{\Phi}_{21}$（次数 $\varphi(21) = 12$）は 2 個の 6 次式の積です。これは 定理 3.4 の $\varphi(21)/\mathrm{ord}_{21}(2) = 12/6 = 2$ と合います。$C_3$ と $C_9$ は $\overline{\Phi}_7$ の 2 個の 3 次因子、$C_7$ は $\overline{\Phi}_3 = x^2 + x + 1$ に対応します。

演習 8.2標準

$\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3 + x + 1)$、$\alpha$ を $x$ の類とする。方程式 $y^2 + y + \alpha = 0$ と $y^2 + y + 1 = 0$ が $\mathbb{F}_8$ に解をもつかどうかを判定し、もつなら解を求めよ。

解答

系 4.4 を使います。$\mathrm{Tr}(\alpha) = \alpha + \alpha^2 + \alpha^4 = \alpha + \alpha^2 + (\alpha^2 + \alpha) = 0$ なので、1 つ目は解をもちます。$y = \alpha^2$ を試すと $\alpha^4 + \alpha^2 = (\alpha^2 + \alpha) + \alpha^2 = \alpha$ で、$y^2 + y = \alpha$ を満たします。解は $\alpha^2$ と $\alpha^2 + 1 = \alpha^6$ です。

$\mathrm{Tr}(1) = 3 \cdot 1 = 1 \ne 0$ なので、2 つ目は解をもちません。これは、$x^2 + x + 1$ の根が $\mathbb{F}_4$ の元で、$\mathbb{F}_8$ が $\mathbb{F}_4$ を含まない（$2 \nmid 3$。定理 4.2［有限体の構造］）ことと合っています。

演習 8.3標準

$q \equiv 3 \pmod 4$ とする。(a) $x^2 + 1$ が $\mathbb{F}_q$ 上既約であることを示し、$\mathbb{F}_{q^2} = \mathbb{F}_q[i]$（$i^2 = -1$）と書けることを確かめよ。(b) $a, b \in \mathbb{F}_q$ に対し $\mathrm{N}_{\mathbb{F}_{q^2}/\mathbb{F}_q}(a + bi) = a^2 + b^2$ を示せ。(c) $c \in \mathbb{F}_q^{\times}$ に対し、$a^2 + b^2 = c$ の解 $(a, b) \in \mathbb{F}_q^2$ の個数を求めよ。

解答

(a) 命題 6.2［有限体の構造］ の 2 より、$q \equiv 3 \pmod 4$ では $-1$ は平方元でないので $x^2 + 1$ は $\mathbb{F}_q$ に根をもたず、2 次式なので既約です。命題 2.6［有限体の構造］ より $\mathbb{F}_q[x]/(x^2 + 1)$ は $q^2$ 元の体で、基底は $(1, i)$ です。

(b) $i^q = i \cdot (i^2)^{(q-1)/2} = i \cdot (-1)^{(q-1)/2} = -i$（$(q-1)/2$ は奇数）なので、$(a + bi)^q = a^q + b^q i^q = a - bi$ です。したがって $\mathrm{N}(a + bi) = (a + bi)(a + bi)^q = (a + bi)(a - bi) = a^2 + b^2$ です。

(c) 定理 4.2 の 4 より、ノルムが $c$ になる $\mathbb{F}_{q^2}$ の元は $(q^2 - 1)/(q - 1) = q + 1$ 個です。$(a, b) \mapsto a + bi$ は全単射なので、解は $q + 1$ 個です。特にどの $c \ne 0$ も 2 個の平方元の和で書けます。

演習 8.4難

$f \in \mathbb{F}_q[x]$ を次数 $n \ge 1$ のモニック多項式とする。次の 2 条件がともに成り立つことが、$f$ が既約であるための必要十分条件であることを示せ（Rabin の判定法）。

(i) $f \mid x^{q^n} - x$。 (ii) $n$ の各素因数 $\ell$ について $\gcd(f,\ x^{q^{n/\ell}} - x) = 1$。

解答

必要性。 $f$ が既約なら、定理 5.2［有限体の構造］ より $f$ は $x^{q^n} - x$ の因子で (i) が成り立ちます。同じ定理より $x^{q^{n/\ell}} - x$ の既約因子の次数は $n/\ell$ の約数で $n$ より小さいので、$f$ はその因子ではありません。$f$ は既約なので、$\gcd(f, x^{q^{n/\ell}} - x)$ は $1$ か $f$ で、$f$ ではないので $1$ です。

十分性。 (i) と 定理 5.2［有限体の構造］ より、$f$ は次数が $n$ の約数である相異なるモニックな既約多項式の積です。その因子 $g$ の次数 $d$ が $n$ より小さいとします。$n/d > 1$ の素因数 $\ell$ を取ると $d \mid n/\ell$ なので、$g \mid x^{q^{n/\ell}} - x$ です。すると $g$ は $f$ と $x^{q^{n/\ell}} - x$ の共通の約数で、(ii) に反します。よって $f$ の既約因子の次数はすべて $n$ で、$\deg f = n$ なので $f$ は既約です。

$x^{q^k} \bmod f$ は 2 乗を繰り返す方法で速く計算できるので、この判定法は実用になります。

参考文献

• R. Lidl, H. Niederreiter, Finite Fields, 2nd ed., Encyclopedia of Mathematics and its Applications 20, Cambridge University Press, 1997 — 第 2 章（トレース・ノルム・基底）、第 3 章（多項式の位数、線形化多項式）、第 4 章（多項式の分解）。
• F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977 — 第 4 章（有限体）、第 7 章（円分剰余類と巡回符号）。
• E. R. Berlekamp, “Factoring polynomials over finite fields”, Bell System Technical Journal 46 (1967), 1853–1859。
• M. O. Rabin, “Probabilistic algorithms in finite fields”, SIAM Journal on Computing 9 (1980), 273–280。
• E. Witt, “Über die Kommutativität endlicher Schiefkörper”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 8 (1931), 413。
• M. Aigner, G. M. Ziegler, Proofs from THE BOOK, Springer — 「有限斜体は体である」の章（Witt の証明）。