代数学の問題

難易度 3期末試験の応用レベル証明問題大学数学代数学

$q$ を素数のべきとし、 $F_{q}$ を $q$ 個の元からなる有限体とする。 $F_{q} [x]$ の多項式が既約であるとは、次数が $1$ 以上で、次数 $1$ 以上の 2 つの多項式の積に表せないことをいう。このとき、 $F_{q}$ 上のモニックな $3$ 次既約多項式の個数は
$\frac{q ^{3} - q}{3}$
であることを証明せよ。

ただし、 $F_{q} [x]$ において、次数 $1$ 以上のモニック多項式はモニックな既約多項式の積に（並べ方を除いて）ただ 1 通りに分解されること（素因数分解の一意性）は用いてよい。

この問題で使うもの

有限体上の既約多項式の個数（説明と入口の問題）
組合せ（説明と入口の問題）

この問題を解けるようになるまで（61 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

モニックな $3$ 次多項式は全部で $q^{3}$ 個あります。そこから既約でないものの個数を引く方針で考えよう。

ヒント 2

既約でないモニック $3$ 次多項式は、既約因子の次数の組が $(1, 1, 1)$ か $(1, 2)$ のどちらかです。そのためには、まずモニックな $2$ 次既約多項式の個数を求めておく必要があります。

ヒント 3

モニック $2$ 次で既約でないものは $(x - a) (x - b)$ の形で、分解の一意性から個数は重複を許して $F_{q}$ から 2 つ選ぶ選び方の数 $\frac{q ( q + 1 )}{2}$ に等しくなります。これを $q^{2}$ から引いて $2$ 次既約多項式の個数を出し、 $3$ 次の場合も同様に型ごとに数えよう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

モニックな $d$ 次多項式が $q^{d}$ 個あることを述べ、既約でないものを引いて数える方針を立てている（1 点）
既約でないモニック $2$ 次多項式が $(x - a) (x - b)$ の形であり、分解の一意性から重複組合せで $\frac{q ( q + 1 )}{2}$ 個と数え、 $2$ 次既約多項式の個数 $\frac{q ^{2} - q}{2}$ を導いている（3 点）
既約でないモニック $3$ 次多項式を既約因子の次数で $(1, 1, 1)$ 型と $(1, 2)$ 型に分け、分解の一意性から重複なく数えられることを述べている（2 点）
$(1, 1, 1)$ 型を $\frac{q ^{3} + 3 q ^{2} + 2 q}{6}$ 個、 $(1, 2)$ 型を $q \cdot \frac{q ^{2} - q}{2}$ 個と正しく数えている（3 点）
$q^{3}$ から引いて整理し、 $\frac{q ^{3} - q}{3}$ を結論している（1 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

モニックな $d$ 次多項式は $x^{d} + c_{d - 1} x^{d - 1} + \dots + c_{0}$ （ $c_{i} \in F_{q}$ ）と書け、係数 $c_{0}, \dots, c_{d - 1}$ の選び方は $q^{d}$ 通りなので、モニックな $d$ 次多項式は全部で $q^{d}$ 個ある。また、モニックな $1$ 次多項式 $x - a$ （ $a \in F_{q}$ ）は次数の関係から積に分解できないので既約であり、ちょうど $q$ 個ある。

以下、 $N_{d}$ でモニックな $d$ 次既約多項式の個数を表す。モニック多項式の積に分解するとき、各因子の最高次係数の積が $1$ になるので、因子はすべてモニックにとり直せる（定数倍を因子間でやりとりする）。したがって、モニック多項式の既約分解はモニックな既約多項式の積として考えてよい。

ステップ 1（補題）: $N_{2} = \frac{q ^{2} - q}{2}$ 。
モニックな $2$ 次多項式 $f$ が既約でないとすると、 $f$ は次数 $1$ 以上の 2 つの多項式の積で、次数の和が $2$ なのでどちらも $1$ 次である。モニックにとり直すと $f = (x - a) (x - b)$ （ $a, b \in F_{q}$ ）となる。逆にこの形の多項式は既約でない。
分解の一意性より、 $(x - a) (x - b) = (x - a^{'}) (x - b^{'})$ となるのは ${a, b}$ と ${a^{'}, b^{'}}$ が重複を込めて同じ組のときに限る。よって既約でないモニック $2$ 次多項式の個数は、 $F_{q}$ から重複を許して 2 つ選ぶ選び方の数に等しい。 $a = b$ の場合が $q$ 通り、 $a \neq = b$ の場合が $(2 q) = \frac{q ( q - 1 )}{2}$ 通りなので、合計 $q + \frac{q ( q - 1 )}{2} = \frac{q ( q + 1 )}{2}$ 個である。したがって
$N_{2} = q^{2} - \frac{q ( q + 1 )}{2} = \frac{q ^{2} - q}{2} .$

ステップ 2: 既約でないモニック $3$ 次多項式の分類。
モニックな $3$ 次多項式 $f$ が既約でないとき、 $f$ のモニックな既約多項式への分解で、因子の次数は正の整数でその和が $3$ 、かつ因子は 2 個以上ある。よって次数の組は $(1, 1, 1)$ または $(1, 2)$ のどちらかである。
- 型 A: $f = (x - a) (x - b) (x - c)$ （ $a, b, c \in F_{q}$ ）
- 型 B: $f = (x - a) g (x)$ （ $a \in F_{q}$ , $g$ はモニックな $2$ 次既約多項式）
逆に、これらの形の多項式は既約でないモニック $3$ 次多項式である。分解の一意性より、型 A と型 B の両方に当てはまる多項式はなく（既約因子の次数の組が異なる）、また同じ型の中では、既約因子の組（重複を込めた組）が違えば多項式も違う。

ステップ 3: 型 A と型 B の個数。
型 A の個数は、 $F_{q}$ から重複を許して 3 つ選ぶ選び方の数である。3 つとも等しい場合が $q$ 通り、ちょうど 2 つが等しい場合が（重なる値 $q$ 通り） $\times$ （残りの値 $q - 1$ 通り） $= q (q - 1)$ 通り、3 つとも異なる場合が $(3 q) = \frac{q ( q - 1 ) ( q - 2 )}{6}$ 通りなので、
$q + q (q - 1) + \frac{q ( q - 1 ) ( q - 2 )}{6} = q^{2} + \frac{q ^{3} - 3 q ^{2} + 2 q}{6} = \frac{q ^{3} + 3 q ^{2} + 2 q}{6} .$
型 B の個数は、 $a$ の選び方 $q$ 通りと $g$ の選び方 $N_{2}$ 通りの積で、ステップ 1 より
$q \cdot \frac{q ^{2} - q}{2} = \frac{q ^{3} - q ^{2}}{2} .$

ステップ 4: 結論。
モニックな $3$ 次多項式 $q^{3}$ 個から、既約でないもの（型 A と型 B）を除くと
$N_{3} = q^{3} - \frac{q ^{3} + 3 q ^{2} + 2 q}{6} - \frac{q ^{3} - q ^{2}}{2} = \frac{6 q ^{3} - ( q ^{3} + 3 q ^{2} + 2 q ) - ( 3 q ^{3} - 3 q ^{2} )}{6} = \frac{2 q ^{3} - 2 q}{6} = \frac{q ^{3} - q}{3} .$
（確認: $q = 2$ のとき $N_{3} = 2$ で、 $x^{3} + x + 1$ , $x^{3} + x^{2} + 1$ の 2 個に一致する。）

以上により、 $F_{q}$ 上のモニックな $3$ 次既約多項式の個数は $\frac{q ^{3} - q}{3}$ である。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる