ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ


当ブログは3月31日をもって更新終了します。

有限体の勉強まとめ (後編)

記事「有限体の勉強まとめ (前編)」の続きです。
これは長くなりますなあ…。
まあ、最後なので気合い入れて執筆していきましょう。

Yahoo!知恵袋でヒントをもらったりしていますが、細かなところは自分で考えた理論展開です。
全体的な理論展開の方針は、私が読んでいた本にならっています。


まず、有限体の話に入る前に、あとで使う定理として、環同型の話をします。
環Q, Rの間に同型写像φ:Q→Rが定義できるとします。

定理1: 単元c∈Qについてφ(c)∈Rは単元である。
証明
すべてのa∈Qについてa = ca'が成り立ちます。
両辺をφに入れてφ(a) = φ(c)*φ(a')が成り立ちます。
任意のx∈Rについてx = φ(a)となるaが存在し、x = φ(c)*φ(a')です。
よってφ(c)は任意のx∈Rを割り切るため、単元です。

定理2: 単元でないa∈Qについてφ(a)∈Rは単元でない。
証明
φの逆写像φ'を利用して、定理1のように
「単元c∈Rについてφ'(c)∈Qは単元である」と言えます。
対偶をとり「単元でないφ'(c)∈Qについてc∈Rは単元でない」と言えます。
これはφ'が全射なのでφ'(c) = aと置けますが、そのときc = φ(a)と表せます。

定理3: 素元p∈Qについてφ(p)∈Rは素元である。
証明
φ(p) = abとなる任意のa,bを置いたとき、φ'(φ(p)) = p = φ'(a)*φ'(b)が成り立ちます。
pは素元なのでφ'(a)とφ'(b)のどちらかは単元です。
定理1よりφ(φ'(a)) = aとφ(φ'(b)) = bのどちらかは必ず単元です。
pは単元でないので定理2よりφ(p)は単元でなく、0でもないのでφ(p)は素元です。


それでは、有限体の話を始めましょう。




「任意の有限体Kは、ある有限体Z_p[x]/(f(x))と同型である」が証明のゴールです。


まず有限体Kの位数をq、標数をpと置きます。
続いてK_p⊆Kを定義します。

定義: K_p = { 0, [1],..., [p-1] }
[n]は前編と同じく1をn回だけ足した元ですが、1とはKにおける乗法の単位元です。

すぐに判明しますが、K_pにKの乗法と加法を導入すると、Z_pと同じ構造をしており、Z_pが体であることを確認するのと同じ要領でK_pが体であることが分かります。

定理4: K_pは体(特にKの部分体)である。

定理5: K_pとZ_pは同型である。
想像してみたら当たり前ですが、証明は難しいですね。

証明
φ([n]) = [n]というK_pからZ_pへの写像φを定義します。
任意の標数pの有限体における[m] = [n]とm mod p = n mod pは同値であり、[m] = [n]ならばφ([m]) = [m] = [n] = φ([n])ですのでφは写像になりえます。
定義: φ([n]) = [n]

φ([m]) + φ([n]) = ([m]) + ([n]) = [m+n]
φ(([m]) + ([n])) = φ([m+n]) = [m+n]
φ([m])*φ([n]) = ([m])*([n]) = [mn]
φ(([m])*([n])) = φ([mn]) = [mn]
なので、これは準同型写像です。

任意の[n]についてφ([n]) = [n]となる[n]が存在し、φ([m]) = [m] = [n] = φ([n])ならば[m] = [n]なので、φは全単射でもあり、同型写像になります。



上記の定理5は後で使いますが、ちょっと違う話をします。

Kの原始根のひとつをα∈Kとします。
K_p[α]つまり、K_p[α] = { f(α) | f(x) ∈ K_p[x] } を考えます。
f(x)にαを代入するときの計算の枠組みはKを使うことにします。

定理6: K_p[α] = Kである。
証明
すべての f(α) ∈ K_p[α] は閉じているKの枠組みで計算されるので f(α) ∈ Kです。
よってK_p[α] ⊆ Kです。
一方、K_p[α] ⊇ { 0, α^1, α^2,..., α^(q-2), α^(q-1) } で、これはαが原始根であることからKを表す集合なので、K_p[α] ⊇ Kです。
以上の2つからK_p[α] = Kです。


続いて今回の話の中核となる定理を述べます。

定理7: Kは、ある有限体K_p[x]/(f(x))と同型である。
証明
K_pを係数とする多項式 x^(q-1) - 1 に、Kを計算の枠組みとしてαを代入すると、α^(q-1) - 1 = 1 - 1 = 0となります。
実はこれはαに限ったことではなく、Kの0でない任意の要素はα^rと表せますが、
(α^r)^(q-1) - 1 = α^(r(q-1)) - 1 = (α^(q-1))^r - 1 = 1^r - 1 = 1 - 1 = 0となります。

定理8: Kの任意の0でない元はK_pを係数とする多項式 x^(q-1) - 1に代入するとK内で0になる。

ここでq >= 2から多項式 x^(q-1) - 1 は定数(単元)でないので、既約多項式の積に分解できます。
x^(q-1) - 1 = g_1(x)*...*g_n(x)とすると、左辺はαを代入して0になるということで、Kは体であり整域の性質を持つので、g_j(α) = 0となるg_j(x)が存在します。
この既約多項式g_j(x)をf(x)と置きます。
記事「多項式の商環による体の拡大」で述べた定理から、既約多項式f(x) ∈ K_p[x]はf(α) = 0を満たすので、K_p[x]/(f(x))はK_p[α]と同型です。
定理6よりK_p[α] = Kなので、Kは有限体K_p[x]/(f(x))と同型です。


定理9: f(x)の位数をmとすると、Kの位数はp^mである。
証明
上記リンクの記事でZ_p[x]/(f(x))の位数がp^mであると指摘したのと同様に、K_p[x]/(f(x))の位数も係数体が変わっただけなのでp^mです。
定理7よりKとK_p[x]/(f(x))の間に全単射が定義できるということなので、Kの位数はK_p[x]/(f(x))の位数と等しく、p^mです。

これは重要なイメージですね。
任意の有限体の位数は、ある素数の冪乗にしかなりえません。


さて、ここからは多種多様な有限体Kから定義されたK_pを、統一的にZ_pに変換する地味だけど面倒くさい証明です。

定理10: K_p[x]とZ_p[x]は同型である。
証明
任意のn次多項式f(x)∈K_p[x]はf(x) = a_n*x^n + ... + a_1*x + a_0と表せます。
a_n,...,a_1,a_0はK_pの要素なので、係数を定理5のφでZ_pの要素に変換する写像ψを定義します。
2つの多項式が等しい、つまり a_n*x^n + ... + a_1*x + a_0 = b_n*x^n + ... + b_1*x + b_0 ならば係数がすべて等しいということなので、これは写像になりえます。
定義: ψ(a_n*x^n + ... + a_1*x + a_0) = φ(a_n)*x^n + ... + φ(a_1)*x + φ(a_0)

Z_p[x]に属する任意のn次多項式も a_n*x^n + ... + a_1*x + a_0 と表せますが、これはφの逆写像φ'を使用してψ(φ'(a_n)*x^n + ... φ'(a_1)*x + φ'(a_0))と等しいのでψは全射です。
また、K_p[x]に属する2つの多項式f(x),g(x)が異なるなら、ある次数について係数が異なるということですが、φが単射であることからψ(f(x)),ψ(g(x))は、その次数について係数が異なり、つまり異なる多項式となるためψは単射です。

続いて、K_p[x]内の多項式f(x) = a_m*x^m + ... a_1*x + a_0, g(x) = b_n*x^n + ... + b_1*x + b_0において加算や乗算を行ったとき、f(x) + g(x)やf(x)*g(x)の各々の次数の係数は、f(x)とg(x)の係数に加算や乗算を行ったものです。
j次の項の係数は多項式v_jを使用してv_j(a_m,...,a_1,a_0,b_n,...,b_1,b_0)で表せます。
Z_p[x]内の多項式ψ(f(x)),ψ(g(x))におけるψ(f(x)) + ψ(g(x))やψ(f(x))*ψ(g(x))も、ψの定義から多項式の構造はf(x),g(x)と同じであり、計算に使う係数がある項や、係数の計算の手順は同じです。
よって、こちらのj次の項の係数も同じくv_j(φ(a_m),...,φ(a_1),φ(a_0),φ(b_n),...,φ(b_1),φ(b_0))で表せます。

ここで、φが準同型写像の性質を持つことから数学的帰納法で比較的に楽に示せると思いますが、
v_j(φ(a_m),...,φ(a_1),φ(a_0),φ(b_n),...,φ(b_1),φ(b_0)) = φ(v_j(a_m,...,a_1,a_0,b_n,...,b_1,b_0))が成り立ちます。
これは任意の項の係数で成り立つということですので、
ψ(f(x)) + ψ(g(x))とψ(f(x) + g(x))は全ての係数が等しいため等しい多項式です。
同様にψ(f(x))*ψ(g(x)) = ψ(f(x)*g(x))です。
よってψは準同型写像の定義を満たします。

以上の議論からψは準同型写像であり全単射なので同型写像となります。


定理10のψを利用して、さっそく次の定理を証明できます。

定理11: 有限体K_p[x]/(f(x))に対して、Z_p[x]/(ψ(f(x)))は有限体である。
証明
既約多項式f(x)から有限体K_p[x]/(f(x))を構成しているわけですが、定理3よりψ(f(x))も素元、すなわち既約多項式です。
よって前編で指摘したとおり、Z_p[x]/(ψ(f(x)))は有限体です。

定理12: 有限体K_p[x]/(f(x))と有限体Z_p[x]/(ψ(f(x)))は同型である。
証明
((f(x)) + v(x))から((ψ(f(x))) + ψ(v(x)))への対応を考えると、
((f(x)) + v(x)) = ((f(x)) + w(x))ならばv(x)~w(x)つまり、あるq(x)においてw(x) - v(x) = f(x)*q(x)ですが、
両辺をψに入れるとψ(w(x)) - ψ(v(x)) = ψ(f(x))*ψ(q(x))、つまりψ(v(x))~ψ(w(x))で、((ψ(f(x))) + ψ(v(x))) = ((ψ(f(x))) + ψ(w(x)))なので、これは写像になりえます。

任意の((ψ(f(x))) + v(x))∈Z_p[x]/(ψ(f(x)))について、ψの逆写像ψ'を使用して((f(x)) + ψ'(v(x)))∈K_p[x]/(f(x))が対応しているので全射です。
また、((ψ(f(x))) + ψ(v(x))) = ((ψ(f(x))) + ψ(w(x)))ならば、ψ(v(x))~ψ(w(x))つまり、あるq(x)においてψ(w(x)) - ψ(v(x)) = ψ(f(x))*q(x)ですが、
両辺をψ'に入れるとψ'(ψ(w(x))) - ψ'(ψ(v(x))) = ψ'(ψ(f(x)))*ψ'(q(x))、つまりw(x) - v(x) = f(x)*ψ'(q(x))、よってv(x)~w(x)、((f(x)) + v(x)) = ((f(x)) + w(x))なので単射です。

そして単純に商環の加法の定義から
"((f(x)) + v(x))の像" + "((f(x)) + w(x))の像" = ((ψ(f(x))) + ψ(v(x))) + ((ψ(f(x))) + ψ(w(x))) = ((ψ(f(x))) + ψ(v(x)) + ψ(w(x)))であり、ψが準同型写像であるため、これは((ψ(f(x))) + ψ(v(x) + w(x)))と等しくなります。
一方で、"((f(x)) + v(x)) + ((f(x)) + w(x))の像" = "((f(x)) + v(x) + w(x))の像" = ((ψ(f(x))) + ψ(v(x) + w(x)))なので前者と等しくなります。
乗法についても同じことが言えるため、この写像は準同型写像の定義を満たします。

よって、この写像は全単射であり準同型写像であるので同型写像となります。


定理12: Kは、ある有限体Z_p[x]/(f(x))と同型である。
証明
Kは定理7より、ある有限体K_p[x]/(g(x))と同型であり、これは定理12よりZ_p[x]/(ψ(g(x)))と同型です。
f(x) = ψ(g(x))と置いて、Kは、ある有限体Z_p[x]/(f(x))と同型です。



さて、これで本題は済みました。

私が読んでいた群・環・体の本では、さらに「位数の等しい有限体は同型である」という定理が証明を省いて紹介されており、
証明が気になったので考えていたのですが、自力では解決できずにYahoo!知恵袋の力を借りて理解したので、述べていこうと思います。

任意の2つの有限体K, Lについて位数が等しいなら同型であることを証明します。
K, Lの等しい位数をqとします。

定理13: KとLの標数は等しい。
証明
Kの標数をp_K、Lの標数をp_Lとします。
定理9より、q = p_K^m, q = p_L^nです。
素因数分解の一意性によりp_K = p_Lです。
(ついでに m = n でもあります。)


等しい標数をpと置いて、本題と同じような理論を組み立てます。

定義: K_p = { 0, [1],..., [p-1] }
定義: L_p = { 0, [1],..., [p-1] }


これらはZ_pと同型であるので、それを介して同型であることが言えますし、
もしくは、そもそもZ_pと同型であることを証明したときに、Z_p特有の性質は使っていないので、同じ証明で直接的に同型であることを言えます。

定理14: K_pとL_pは同型である。

同様にして、これらの定理も言えます。

定理15: K_p[x]とL_p[x]は同型である。
定義: K_p[x]からL_p[x]への同型写像をψとする。


定理16: 既約多項式f(x)∈K_p[x]について、L_p[x]/(ψ(f(x)))は有限体である。

定理17: 既約多項式f(x)∈K_p[x]について、K_p[x]/(f(x))とL_p[x]/(ψ(f(x)))は同型である。


ここで、定理7と同じ話を繰り返しますが、K_p[x]内の多項式 x^(q-1) - 1 を既約多項式の積に分解できます。
同じ話で、x^(q-1) - 1 = g_1(x)*...*g_n(x)とすると、Kの原始根αについてg_j(α) = 0となるg_j(x)が存在します。
f(x) = g_j(x)と置きます。

定義: 既約多項式f(x)∈K_p[x]は、原始根α∈Kについてf(α) = 0とする。

ところで、ψ(x^(q-1) - 1) = ψ(g_1(x)*...*g_n(x)) = ψ(g_1(x))*...*ψ(g_n(x))ですが、定理3によりg_1(x),...,g_n(x)が既約多項式(素元)であるため、ψ(g_1(x)),...,ψ(g_n(x))は既約多項式となります。

定理18: ψ(f(x))(β) = 0となるβ∈Lが存在する。
証明
ψ(x^(q-1) - 1)は、ψの定義からL_pが係数の x^(q-1) - 1 なので、q-1次式です。
定理8よりLの0でないq-1個の元は、この多項式に代入するとL内で0になります。
Lは整域の性質を持つので、Lの0でないq-1個の元はψ(g_1(x)),...,ψ(g_n(x))のどれかに代入するとL内で0になります。

しかし、n次の多項式は最大でもn個までしか、代入して0になる元を持たないので、
ψ(g_1(x)),...,ψ(g_n(x))の次数の和がq-1であることから、これら全てにおいて代入して0になるLの元が、それぞれの次数と同じ個数だけ存在している必要があります。
(そうでないと仮定すれば矛盾を導けます。)

一例としてf(x) = g_j(x)にも代入して0になるLの元が、これの次数と同じ個数だけ存在しているので、これは1次以上の多項式ですから、ψ(f(x))(β) = 0となるβ∈Lが存在します。


定理19: L_p[β]とL_p[x]/(ψ(f(x)))は同型である。
証明
定理18によって既約多項式ψ(f(x))はψ(f(x))(β) = 0を満たすので、記事「多項式の商環による体の拡大」で述べた定理からL_p[β]とL_p[x]/(ψ(f(x)))は同型です。

定理20: KとL_p[β]は同型である。
証明
まず定理6からK = K_p[α]です。
これは定理7と同様に、K_p[x]/(f(x))と同型です。
定理17からL_p[x]/(ψ(f(x)))と同型です。
定理19からL_p[β]と同型です。
よってKとL_p[β]は同型です。

定理21: L_p[β] = Lである。
証明
L_p[β]は閉じているLの枠組みで計算されるのでL_p[β] ⊆ Lです。
定理20からKとL_p[β]は同型で、全単射が導入できるので、L_p[β]の要素数はKと同じくqです。
Lの要素数もqであるので、実はL_p[β] ⊆ LどころかL_p[β] = Lです。


定理22: KとLは同型である。
証明
定理20からKとL_p[β]が同型で、定理21からL_p[β] = Lなので、KとLは同型です。



以上です。

この後編は、だいぶ長い執筆になるだろうと思っていましたが、3回の執筆で書き終えられました。
F#の記事に比べると、めちゃめちゃ短いですね。

まあ、前編でも言いましたが私が書くのが遅いってだけで、今回は扱う内容自体は狭いですからね。


記事冒頭で書きましたが、証明の発想は本やYahoo!知恵袋で授かってあれど、書き下したのは自力です。
また、ちまちま同型であることを証明していく面倒くさいやつは、完全オリジナルです。

しかし、どこか非論理的というか、数学の証明の書き方に適合できていない感じはありますね~。
イメージはあるんだけど、うまく言葉に出来ないというか…。

数学は恋と同じですね(名言)

この命題と推論を自然演繹で書き下すとしたら、一体これはどう書けばいいんだろうかという局面は、今回も証明していて多々ありました。
一階述語言語で表せない命題は除きますが、基本的に自然演繹での証明を日本語に直訳したような証明が、理想的な証明だと思っています。


まあ、久しぶりに数学の記事で体系的な、そして(いつもと比べれば)大規模な内容のものを書けたんで、多分これが最後になりますから、最後はマトモなクオリティのものを書けて良かったなと感じますね。

今年度は数学の記事を結構、書きましたが、いかがでしたかね。

tag: 数学 群環体 証明 論理学 多項式 有限 集合 同値 勉強 終活

コメント

2018/03/31以降はコメント、トラックバック不可です。

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/536-e6bfdfd6
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。