ブログ「サイバー少年」

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

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

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

tag:

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

できれば昨年中に書いておきたかった有限体の勉強まとめです。
内容が広いので文量はともかく、執筆時間が相当なものになるだろうということで、前編、後編でお送りします。

今のところ予定している配分では、特に後編がかなりヘビーになると思っています。
内容が広いって言っても、広くないんですけどね。
私が書くのが遅いという…。

前編は導入部分の話だけで証明といった証明も特になく、準備運動のようなものです。
いや、前編もかなり時間かけて書いたんですけど。


さて、まず体についてはご存知のものとします。
有限体とは、体を構成している集合が有限集合であるものです。

有限集合ですから要素数を自然数で表すことができます。
この要素数を体の位数と呼びます。

後述する体の要素についての位数というのもあって、両方とも位数という名前ですが別概念です。
同じ名前やめろよと言いたいですが、余談として、たぶん位数がnの体の要素が構成する乗法群が集合の要素数として位数nになるから、なんでしょうね。


なお、ここで体の位数が1、体の要素が1 = 0のひとつだけということは、ありえません。
(このような代数系である場合、零環という名前の環になります。)

この話題は記事「体の準同型写像に必要な定義」でもしましたが、どうやら体の公理系に零環は矛盾しないのだけれど、
零環でない体が充足してくれる魅力的な性質が零環だけ充足してくれないことがあって、テンションだだ下がりだから排除しておきたい、
しかし零環というたったひとつのケースを除外するための公理を設定するのもなんだかなぁって感覚で、暗黙的に体から除外しているみたいですね。

厳密にやるなら体の公理に零環を除外することを加えるべきだと思います。
ただ証明でいちいち「ここで1 = 0ではないので…」と言及するのも面倒ですからねぇ。

数学はフィーリングで考えている部分も大きいので、零環でない体に共通するイメージの論理的妥当性を主張するために零環ではないという条件を持ち出さなければならないのは邪魔です。




続いて体の要素の位数の話ですが、そもそも有限体は体ですから、乗法について閉じています。
つまり体Kについて、a∈Kならば、aa∈K, aaa∈K,...となりますが、ある元aをn回だけ乗算した元を、よくある冪乗の記号でa^nと書くことにします。
ただし、a^0 = 1とします。

ここでa != 0とします。
有限体は要素数が有限ですから、a^0, a^1, a^2...と続けていったときに(この列を系列と呼びます。)元が出尽くして、
最大でもKの位数qにおいて、a^(q-1)で以前に出てきた元と同じ元が現れます。

なぜ要素数はq個あるのに最大でa^(q-1)の段階で再び同じ元が現れるのかというと、体は整域の性質を持つので、0でない元aをいくら乗算しても0になることはないですから、この系列には0以外のq-1個の元のみ現れるためです。

もちろん、q-1より小さい自然数で冪乗したときに以前と同じ元が現れることもあります。

一般的には0 <= r < s <= q-1となる自然数r,sにおいて、a^r = a^sとなるということです。
この等式をa^rで割ると、1 = a^(s-r)となります。

0 < s-r <= q-1が導けますから、q-1以下で0より大きいs-rについてa^(s-r) = 1 = a^0となります。
このような条件下で一番小さいs-r、要するにm > 0でa^m = a^0となる最小のmを、a(a != 0)の位数と呼びます。

いま議論したように位数qの有限体の0でない要素の位数がq-1より大きくなることはありません。


ところで位数が最大のq-1となる元のことを有限体の原始根と呼びます。
原始根αについて、0 <= r < s < q-1となる自然数r,sでα^r = α^sであると仮定すると、
先程と同様の議論で0 < s-r < q-1でα^(s-r) = α^0でαは原始根ではなくなってしまうので、この仮定は否定されます。

これが何を言っているかというと、α^(q-1)に到達するまでの系列α^0, α^1, α^2,..., α^(q-2)は全て異なる元であるということです。

この系列のq-1個の元は前述のように有限体が整域であるため0ではないので、有限体の0以外のq-1個の元のどれかであり、すべて異なるということでしたから、この系列は有限体の0以外の元すべてを表しています。

つまり原始根をずっと掛け合わせていくと有限体の0以外の全ての元が得られるということです。
原始根でない元aをずっと掛け合わせても、0以外の元がすべて出尽くす前にa^m = a^0となってしまい、また同じ系列を繰り返すだけなので、全ての元は得られません。


原始根が有限体に含まれていれば上述のように便利なのですが、実は任意の有限体は原始根を持ちます
この証明は面白いのですが、微妙に長く、しかも私が解読に戸惑ったわけでもないので省略します。

まあ具体例だけ示しておきましょう。

例えば、ユークリッド整域である整数環Zを素数p∈Zの単項イデアル(p)で類別したZ/(p)が体であること、および要素数が有限であることは、記事「イデアルと商環とユークリッド整域の商環」を読めば分かります。

ただ、商環は面倒くさいので、これと同型な代表系Z_p = {0,1,2,...,p-1}を考えます。
加法と乗法はZ内で計算したあとのpで割った余りとして定義されます。

たとえば、Z_7は有限体です。
これは3,5∈Z_7が原始根となります。

有限体Z_5は2,3∈Z_5が原始根です。




続いて、体の標数の話をします。
体について標数という自然数があり、とりあえず、有限体でない体の標数は0と定義されます。

任意の有限体について
1, 1+1, 1+1+1,...という系列を考えます。

これも要素の位数と同じ話で、有限体ですから、どこかで同じものが再び現れます。
1+1+1+1+1 = 1+1+1だとしたら、両辺から1+1+1を引いて1+1 = 0となります。

表記法が面倒くさいので乗法の単位元1をn回だけ足した有限体の元を[n]と書くことにします。
[5] = [3]なら、両辺から[3]を引いて[2] = 0となります。

このように[n] = 0となる最小の自然数n > 0を有限体の標数と呼びます。

標数が1の有限体は、1 = 0ということで、零環であり前述のとおり体ではないので、ありえません。
もし標数1の有限体を認めてしまうと、実は今後の理論展開に不都合があるので、そういう意味でも零環は体でないとしたんでしょうね。


位数qの有限体の標数がq以下であることはもちろんのこと、実は有限体の標数は必ず素数となります

分配法則により
(1+1+1)*(1+1) = (1+1)+(1+1)+(1+1)みたいに、
([m])*([n])は[m]の1を[n]に置き換えることになるので、
([m])*([n]) = [mn]が成り立ちます。

ここで、有限体の標数nが素数でないと仮定すると、nは2つ以上の素因数p_1,p_2,...,p_mに分解できます。
[n] = 0ですが、[n] = [p_1*p_2*...*p_m] = ([p_1])*([p_2])*...*([p_m])なので、
([p_1])*([p_2])*...*([p_m]) = 0となり、有限体は整域なので、この中に[p_j] = 0となるp_jが存在します。

p_j < nなので、nの最小性、すなわちnが標数であることに矛盾します。
よって有限体の標数は素数です。

たしかに先ほど挙げた例のZ_7やZ_5の標数は素数ですね。
そもそも標数が素数になるように作った有限体ですからね。


なお、有限体の任意の0でない要素aについて、
たとえば1+1+1 = 0なら両辺にaを掛けてa+a+a = 0、
逆にa+a+a = 0ならば両辺をaで割って1+1+1 = 0、
(後者は体でなければ除算できませんが、整域であるなら、その性質から同じことが言えます。)

つまり、aをn回足して0になるnと、1をn回足して0になるnは一致します。
このnで最小のものは、定義から標数ですね。


Z_5やZ_7のようにZの商環から作った有限体は、詳しくは知らないのですが、これの真部分集合が同じ演算で体を成すことがありえないそうで、そういう体を素体というそうです。
有限体であるような素体は、Z_5やZ_7を考えれば分かりますが、位数と標数が一致するみたいですね。



では、他にはどういう種類の有限体があるでしょうか。

上述の有限体Z_pを係数とする多項式環Z_p[x]は、係数が体なのでユークリッド整域です。
これをZ_p[x]内での既約多項式f(x)∈Z_p[x]の単項イデアルで類別した商環Z_p[x]/(f(x))は、やはり体になります。

さらに、f(x)の次数をmとすると、m次以上の任意の多項式a(x)をf(x)で割って、
a(x) = b(x)*f(x) + q(x)となりますから、a(x)~q(x)、((f(x)) + a(x)) = ((f(x)) + q(x))であり、q(x)はm-1次以下の多項式ですから、
すべてのZ_p[x]/(f(x))の要素は、なんらかのm-1次以下の多項式を含む同値類として表せます。

よって、m-1次以下の多項式をすべて網羅して、それぞれ、それを含む同値類を考えれば、Z_p[x]/(f(x))の要素をすべて網羅したことになります。

Z_p[x]/(f(x)) = { ((f(x)) + q(x)) | q(x) ∈ {v(x) | v(x)はm-1次以下} }です。


m-1次以下の多項式の組み合わせは、0次の項からm-1次の項までのm個の係数をどうするかという問題ですから、ここで係数体は有限個の要素数pしかないので、p^m通りとなります。

よって、Z_p[x]/(f(x))の要素数はp^m個以下であるはずなので、これは有限体です。

ちなみに、異なるm-1次以下の多項式v(x),w(x)について、v(x) - w(x)はm-1次以下であり、0でもないからf(x)で割り切れないので、((f(x)) + v(x)) != ((f(x)) + w(x))です。
つまり、m-1次以下の多項式q(x)と((f(x)) + q(x))は一対一対応であり、実はZ_p[x]/(f(x))の要素数はちょうどp^m個です。

そのため全てのm-1次以下の多項式からなる代表系を作ることができます。
加法と乗法はZ_p[x]内で計算して、加法はこの代表系について閉じているからいいのですが、乗法はZ_p[x]内で計算したあとf(x)で割った余りとして定義されます。


ところでZ_p[x]/(f(x))の標数は、((f(x)) + 1)を足し合わせて、いつ((f(x)) + 0)になるかという、定数項だけ、Z_p内で計算しているだけの話ですから、係数体の標数と同じくpです。

なお、f(x)が1次式である場合、すべての0次以下の多項式からなる代表系を作れば、体Z_pと同一の体になります。


さて、それでは具体例を見てみましょう。
係数体の標数は一番単純な2でやってみます。
(標数2の例しか本に載っていないのでパクれない…)

係数がZの多項式環や係数がQやR、Qなどのとき既約多項式であるものも、係数を有限体と見なすと既約多項式でなかったり、逆に既約多項式でないものが既約多項式になったりするので注意が必要です。

たとえば、x^2 + 1は係数体をQまで大きくしない限り既約多項式なので、既約多項式だろうと思ってしまいますが、Z_2上では(x+1)^2 = x^2 + (1+1)x + 1*1 = x^2 + 1です。
Z_p上での既約多項式を探したいなら、エラトステネスの篩を使ったりしなければなりません。

そうすると、x, x + 1, x^2 + x + 1, x^3 + x + 1なんかが既約多項式であると判明します。

面倒くさいので全部、すべてのm-1次以下の多項式からなる代表系に置き換えて書きますが、
Z_2[x]/(x) : {0, 1}
Z_2[x]/(x + 1) : {0, 1}
Z_2[x]/(x^2 + x + 1) : {0, 1, x, x + 1}
Z_2[x]/(x^3 + x + 1) : {0, 1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1}
が代表系となります。

m >= 2のとき、xは必ず原始根になるんじゃないかと予想して、たしかに上記の例では下の2つは全てxが原始根になるのですが、証明を頑張って考えていました。
Yahoo!知恵袋で聞いてみたら、反例があるみたいですね。


このZ_pが係数体の多項式から構成する有限体Z_p/(f(x))は、今後の理論展開において非常に重要となります。

実は、あらゆる有限体は、この類の有限体と同型になるのです。



その証明は後編にて書きます。
後編で書く予定の内容は、本に書いておらず自力で補完した部分が多く、あんまり自分でも理解していないので、執筆にめちゃくちゃ時間が掛かりそうです。

また、細かいところの証明が面白くないくせに長くなるので、文量も増えると思います。
まあ、後編の内容は上の定理の証明だけ、あとプラスアルファ、を予定しているんですけどね。

それでも長くなる。
ただ、去年に書いていたF#についての解説記事ほどの大規模プロジェクトにはならないと思います。

わりとお待たせすると思いますが、当ブログで数学について勉強したことを書く記事としては最後になるはずです。

乞うご期待!

tag: 数学 群環体 集合 有限 同値 素数 ユークリッド 勉強 多項式 終活

コメント

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

コメントの投稿

トラックバック

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

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

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。