有限体の存在性に関するSoundararajanの記事

昨日、SoundararajanがarXivに記事をあげていて、さらっと読んだので部分的に紹介する*1。

定理とその証明

次の有名な基本的定理をRamanujanとErdősによるBertrandの仮説の証明を真似れば証明できるということが書かれている。

定理 $\mathbb{F}$ を有限体、 $n$ を正整数とする。このとき、monicな既約多項式 $f(x)\in \mathbb{F}[x]$ で $\deg f=n$ であるようなものが存在する。

多項式の世界での素数の存在性である。

証明. $\#\mathbb{F}=q$ とする。 $n=1$ のときは次数 $1$ のmonic多項式は $q$ 個あるが、それらは全て既約である。以下、 $n\geq 2$ とする。

$\mathcal{F}_n(x)\in \mathbb{F}[x]$ を $\mathbb{F}[x]$ の元であって次数が $n$ であるようなmonic多項式(このようなものは $q^n$ 個ある)全ての積とする。 $\deg\mathcal{F}_n(x)=nq^n$ である。

$d\leq n$ であるような正整数 $d$ と次数が $d$ のmonic既約多項式 $p(x)$ を好きに選んだときの $\mathrm{ord}_{p(x)}(\mathcal{F}_n(x) )$ を計算しよう。これは $\mathcal{F}_n(x)$ を既約多項式分解したときの $p(x)$ の指数であり、Legendreの公式*2の類似によって計算できる。つまり、

$\displaystyle \mathrm{ord}_{p(x)}(\mathcal{F}_n(x) )=\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}$ ( $p(x)^k$ で割り切れるような次数 $n$ のmonic多項式の個数)

が成り立つ。 $p(x)^k$ で割り切れるような次数 $n$ のmonic多項式を $f(x)$ とするとき、 $f(x)=p(x)^kg(x)$ の $g(x)$ は次数が $n-kd$ であるようなmonic多項式であるから、そのようなものの個数は $q^{n-kd}$ 個であることがわかる。よって、

$\displaystyle \mathrm{ord}_{p(x)}(\mathcal{F}_n(x) )=\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}q^{n-kd}$

と計算できた。ここで、Bertrandの仮説の証明では中央二項係数 $\binom{2N}{N}$ が重要な役割を果たすが、ここではその類似物として

$\displaystyle \frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}$

を扱う。用意した公式により

$\displaystyle \mathrm{ord}_{p(x)}\left(\frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}\right)=\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}q^{n-kd}-q\sum_{k=1}^{\left\lfloor \frac{n-1}{d}\right\rfloor}q^{n-1-kd}=\begin{cases} 1 & (d\mid n)\\ 0 & (d\nmid n) \end{cases}$

と計算できる。 $\mathbb{F}[x]$ の元であって次数が $d$ のmonic既約多項式全体のなす集合を $\mathcal{P}_d$ と表すと、上記計算は

$\displaystyle \frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}=\prod_{d\mid n}\prod_{p(x) \in \mathcal{P}_d}p(x) \in \mathbb{F}[x]\tag{1}$

の成立を意味する。次数は

$\displaystyle \deg\left(\frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}\right)=nq^n-q\bigl( (n-1)q^{n-1}\bigr)=q^n$

である。背理法で定理を証明するために、 $\mathcal{P}_n=\varnothing$ であったと仮定しよう。 $\mathbb{F}[x]$ の元であって次数が $d$ のmonic多項式全体のなす集合を $\mathbb{F}[x]_d$ と表すことにすると、整除関係

$\displaystyle \left.\frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}=\prod_{d\mid n, \ d\neq n}\prod_{p(x) \in \mathcal{P}_d}p(x) \ \right| \ \prod_{d=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\prod_{f(x) \in \mathbb{F}[x]_d}f(x)$

が成り立つ。次数を評価すると、 $\#\mathbb{F}[x]_d=q^d$ に注意して、

$\begin{align} \deg\left(\prod_{d=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\prod_{f(x) \in \mathbb{F}[x]_d}f(x)\right)&=\sum_{d=1}^{\left\lfloor \frac{n}{2}\right\rfloor}dq^d\leq \left\lfloor \frac{n}{2}\right\rfloor\sum_{d=1}^{\left\lfloor \frac{n}{2}\right\rfloor}q^d=\left\lfloor\frac{n}{2}\right\rfloor\cdot\frac{q(q^{\left\lfloor\frac{n}{2}\right\rfloor}-1)}{q-1}\\ &< \left\lfloor\frac{n}{2}\right\rfloor\cdot \frac{q}{q-1}\cdot q^{\left\lfloor\frac{n}{2}\right\rfloor}\leq 2\left\lfloor\frac{n}{2}\right\rfloor q^{\left\lfloor\frac{n}{2}\right\rfloor} \end{align}$

よって、先ほどの整除関係において次数の比較を行うと

$\displaystyle q^n < 2\left\lfloor\frac{n}{2}\right\rfloor q^{\left\lfloor\frac{n}{2}\right\rfloor}$

を得る。一方、

$q^n\geq (q^{\left\lfloor\frac{n}{2}\right\rfloor})^2\geq 2^{\left\lfloor\frac{n}{2}\right\rfloor}q^{\left\lfloor\frac{n}{2}\right\rfloor}\geq 2\left\lfloor\frac{n}{2}\right\rfloor q^{\left\lfloor\frac{n}{2}\right\rfloor}$

なので矛盾に到達した。 Q.E.D.

補足

素数 $p$ に対して位数 $p$ の有限体 $\mathbb{F}_p$ の存在性を示すのは容易いが、位数 $p^n$ の有限体 $\mathbb{F}_{p^n}$ の存在性の証明は比較的難しくなる。この記事で証明した定理(以下、「存在定理」)を用いると、次数 $n$ のmonicな $\mathbb{F}_p$ 係数既約多項式が存在するので、それが生成するイデアルによる $\mathbb{F}_p[x]$ の剰余環は位数が $p^n$ の有限体になっている。

このように存在定理を利用した有限体の存在性証明を採用する際、存在定理はゼータ関数を用いて証明されるのが標準的なようである。その証明を知りたい方には黒木先生の記事(PDF)

http://www.math.tohoku.ac.jp/~kuroki/LaTeX/20080424_finite_field.pdf

を参照していただきたい。

有限体の存在という極めて代数的な定理の証明にゼータ関数という解析(数論)的な対象を用いて見事に証明できるというのは面白い。

面白いし、その手法によるご利益もあるし、ゼータ関数について同時に学ぶことができて一石二鳥といいこと尽くめのようでもあるが、学生に厳密に理解させるためには無限和や無限積について別途説明する必要がある。

一方、今回Soundararajanが提案する方法では解析的な手法に頼らずに存在定理を証明することができるため、今後教育の現場で取り入れていってもよさそうだ。

なお、Soundararajanが指摘しているように、ゼータ関数を使った議論で得られるGaussの公式

$\displaystyle q^n=\sum_{d\mid n}d\#\mathcal{P}_d$

は $(1)$ 式の次数を比較することによっても得られる。それにMöbiusの反転公式を施せば $\#\mathcal{P}_n$ の明示公式が得られるが、 $\#\mathcal{P}_n\neq \varnothing$ だけだったら上述のようにRamanujan-Erdősの発想に基づく不等式評価で証明できるというわけだ。