有限体上の既約多項式の数 - 日々の暮らしと時々の数学

いろいろあって有限体を見ていたら、
Wikipediaの既約多項式のページを見ていたら、
その有限体上の既約多項式の数についての項目があった。

それは

◆定理◆
有限体 $\mathbb{F}_q$ 上の $n$ 次のモニックな既約多項式の数は、
$\displaystyle \frac{1}{n}\sum_{d|n}\mu \left( \frac{n}{d}\right) q^d$
で与えられる。ただし、 $\mu (n)$ はメビウス関数である。

というものである。

これの証明が、arXiv:1001.0409にある。
（Sunil K. Chebolu, Jan Minac,Counting irreducible polynomials
over finite fields using the inclusion-exclusion principle）

今回はこの証明を紹介する。

使う議論は有限体に関する基本的な知識のみで、
この証明について著者は
「驚くべきことに、今回の記事のシンプルな議論はいくらかの
専門家は知っているかもしれないが、教科書には載っていない」
と書いている。

確かにシンプルな議論だった。

証明に入る前に（これも上記の記事に書いてあることだが）
この定理は $q=p$ の場合（つまり素数のとき）には
ガウス(1777-1855)が証明したことらしい。

さらに、メビウスの反転公式を用いたクラシカルな証明は
あの、アイルランド・ローゼンの有名な教科書に書いてあるそうだ。
（恥ずかしながらきちんと読んだことはない）

添え字が極めて読みにくいことが判明したため、
$\mathbb{F}_{q^n}$ のことを $\mathbb{F}\langle q^n\rangle$ と書くことにする。

証明するに当たり、以下の基本的な有限体の知識と
メビウス関数の定義を確認する。

有限体の元の数は素べきである。
有限体 $\mathbb{F}\langle q^n\rangle$ は、ある $\mathbb{F}_q$ 上の $n$ 次の既約多項式 $p(x)$ の最小分解体である。
$\mathbb{F}_q$ 上の既約多項式は重根をもたない。
異なる $\mathbb{F}_q$ 上のモニックな既約多項式は共通根をもたない。
$\mathbb{F}\langle q^a\rangle\subset \mathbb{F}\langle q^b\rangle\Leftrightarrow a|b$ である。
有限体はその元の数により、同型を除き一意に定まる。

という6つである。

1.と5.は拡大次数から簡単にわかる。
2.は有限体同士の拡大はガロア拡大であり、単拡大である。
その最小多項式をとれば、共役な根はフロベニウスで与えられるから、
すべての根を含む。よって最小分解体になる。
3.は先のガロアなので分離拡大であることによる。
（ガロアと分離がどっちを先に示すかは定義や議論次第）
4.は一般に最小多項式がただ一つに決まるということに他ならない。
（もとの論文には"monic"という言葉が抜けているが、必要だろう）
6.は $x^q-x$ の最小分解体でなければならないことから従う事実である。

また、メビウス関数とは

◆定義◆
メビウス関数 $\mu :\mathbb{Z}_{>0}\to \{ 0,\pm 1\}$ を
$\displaystyle \mu (n)=\left\{ \begin{array} {}0 &(n \mbox{ has a squared prime factor}) \\ (-1)^k & (\mbox{otherwise})\end{array}\right.$
で、ここで $k$ は素因数の数を表す。

という定義である。

証明

これらを認めれば証明ができる。
＜証明＞
代数閉包 $\overline{\mathbb{F}}_q$ を固定した下で考える。
$n=1$ のときは明らかなので、 $n>1$ としよう。
${\cal P}_n$ を $\mathbb{F}_q$ 上の $n$ 次のモニック既約多項式全体とする。
${\cal R}_n\subset \mathbb{F}\langle q^n\rangle$ を ${\cal P}_n$ の元の根全体とする。
根が全て $\mathbb{F}\langle q^n\rangle$ に含まれるのは2.と6.による。

3.と4.によれば、
$n|{\cal P}_n|=|{\cal R}_n|$
であるから後者を考えることにする。
ここで、 ${\cal R}_n$ について、
${\cal R}_n=\{ \alpha \in \mathbb{F}\langle q^n\rangle|[ \mathbb{F}_q(\alpha ):\mathbb{F}_q] =n\}$
であり、 $[ \mathbb{F}_q(\alpha ):\mathbb{F}_q] =n$ は、
$\alpha$ が $\mathbb{F}\langle q^n\rangle$ に含まれ、同時に真部分集合に含まれないことと同値である。
さらに、それは $\mathbb{F}\langle q^n\rangle$ に含まれ、極大な真部分集合に含まれないことと言える。

いま、 $n$ の素因数分解が $n=u^av^bw^c\cdots$ という形だとする。
すると、極大な真部分集合たちは
$F_u=\mathbb{F}\langle q^{n/u}\rangle ,F_v=\mathbb{F}\langle q^{n/v}\rangle ,F_w=\mathbb{F}\langle q^{n/w}\rangle ,\dots$
である。

これらのことから、 $|{\cal R}_n|=|(F_u\cup F_v\cup F_w\cup\cdots )^c|$ である。
このとき、4.から $F_u\cap F_v=\mathbb{F}\langle q^{n/uv}\rangle ,F_u\cap F_v\cap F_w=\mathbb{F}\langle q^{n/uvw}\rangle$ などとなるから、
和集合の元の数に関する法則(inclusion-exclusion principle)*1によって
$|{\cal R}_n|=q^n$
$-q^{n/u}-q^{n/v}-q^{n/w}-\cdots$
$+q^{n/uv}+q^{n/vw}+q^{n/wu}+\cdots$
$\cdots$
$(-1)^kq^{n/uvw\cdots}$
が得られる。

これをメビウス関数を用いて表示すれば定理が得られる。
（となっているが、この最後のところをもう少しコメントすると、
約数 $d|n$ について $q$ のべきに $d=\frac{n}{n/d}$ が
現われていて、 $\frac{n}{d}$ が素因数の1乗の積になっているもの
だけを考えたいので、確かに平方因子を持つものは消えてくれるし、
また、そうでない場合、符号は $\frac{n}{d}$ の素因子の数の
奇偶によって決まっているから、確かに合っている。）