元祖ワシ的日記

有限体の各次数における既約多項式の総数というのをここ暫く考えていました。まぁいろいろあるんですが、結論から言うと次の補題を証明した瞬間ほぼ終わりです。

例1)
$F_2$上の$X^{4} - X$の因数分解を考えます。$n=2$です。よって1次式と2次式の分解できます。実際計算してみると

$\begin{eqnarray*} X^{4} - X = X(X+1)(X^{2} + X + 1) \end{eqnarray*}$

となります。この式はこれ以上分解するのは不可能です。

例2)
$F_2$上の $X^{8} - X$の因数分解を考えます。$n=3$です。
この式は3の約数である1次と3次の既約多項式を因子に持ちます。実際計算してみると

$\begin{eqnarray*} X^{8} - X &=& X(X-1)(X^6 + X^5 + \cdots + 1)\\ &=& X(X-1)(X^3 + X + 1)(X^3 + X^2 + 1) \end{eqnarray*}$

例3)
$F_2$における$X^{16} - X$の因数分解を考えます。$n=4$です。
よって$n$の約数である既約4次式、2次式、1次式を因子にもちます。実際計算してみると、

$\begin{eqnarray*} X^{16} - X &=& X(X-1)(X^{2} + X + 1)(X^{12} + X^{11} + \cdots + 1)\\ &=& X(X-1)(X^{2} + X + 1)(X^4 +X +1)(X^4 +X^3 +1)(X^4 +X^3 +X^2 +X +1) \end{eqnarray*}$

以上なんとなく感覚がつかめていただいたでしょうか？２の冪以外の例はまた別の機会にここに書きます。

さて、ここから$F_q$における$n$次の既約多項式の個数を求めます。

$X^q-X$において$n$次の既約多項式の根を全て掛け合わせたものの次数を$\nu(n)$とします。先ほどの例で言えば

$\begin{eqnarray*} \nu(1)&=& 2\\ \nu(2) &=& 2\\ \nu(3) &=& 6\\ \nu(4) &=& 12\\ \end{eqnarray*}$
です。この先ですが

$\begin{eqnarray*} \nu(5) &=& 30\\ \nu(6)&=& 54\\ \end{eqnarray*}$

と続きます。

さて、$F_q$には$n$の約数である$d$次の既約多項式がすべて存在します。それらの次数を足し合わせれば当然$q$になります。よって、

$\begin{eqnarray*} \sum_{d|n}{\nu(d)} = q = p^n \end{eqnarray*}$

が成立します。ここからメビウスの反転公式を使って

$\begin{eqnarray*} \nu(d) = \sum_{d|n}{\mu\left(\frac{n}{d}\right)p^d} \end{eqnarray*}$

となります。$\nu(d) / n$が$n$次式の個数になるので

$\begin{eqnarray*} \frac{1}{n}\sum_{d|n}{\mu\left(\frac{n}{d}\right)p^d} \end{eqnarray*}$

が求める個数になります。