Kotlinでも代数学(2)

はじめに

この記事はSwiftで代数学入門シリーズに影響を受けて書かれました。

元記事のその4-その5くらいの内容相当、つまり有限体を構成するまで、になっております。

今回予告

前回の次回予告で

  • 有理数体くんの q に\(0\)を食わせるフトドキモノが現れてもいいように、\(p \in \mathbb{Z}\)、\(q \in \mathbb{Z}^{+}\)とかしよう!
  • 有理数体くん、ちょっと頭弱いみたいになってるので約分してほしい!
  • それが終わったらいよいよ有限体、そして多項式環、代数拡大までいこう

と書きました。が、有理数体くんの q に関しては今回はというか永久にやりません。もう出てきませんし……というわけなので、うしろ2つをやっていきましょう。

ではまずは約分しましょう!

約分

有理数\(\frac{p}{q}\)がある数\(c\)をもって\(\frac{cp’}{cq’}\)と表せるとき\(\frac{p}{q} = \frac{p’}{q’}\)とみなすことができて、また、この操作を約分というのでした。

2つの数\(a\)、\(b\)の最大公約数を\(\mathrm{gcd}\left(a, b\right)\)と表すことにすると、\(\mathrm{gcd}\left(p’, q’\right)=1\)となる(もうこれ以上約分できない)とき、これを既約であると言います。

つまり、約分するためには2数の最大公約数を求める必要がありますね(ちなみにgcdとはgreatest common divisor: 最大公約数の略です)。

ユークリッドの互除法

大変な天下りで申し訳ないのですが、最大公約数を求めるアルゴリズムといえば……そう!ユークリッドの互除法ですよね。

解説は他の文献を参照してもらうことにして、コードはこうです。

これでわたしたちの有理数もわかりやすい形で表示できるようになります!有理数体クラスQはこのようなコードになるでしょうか。

いまのところは表示するとき以外に約分してもらう必要はまったくありませんが……

 

さて。ここからが今回のメインの話題です。

 

剰余類環

自然数\(n \ge 2 \)について、\(n\)で割った余りが等しい整数を集めたものを\(n\)を法とする剰余類というのでした。

この剰余類について、\(\mathbb{Z}/n\mathbb{Z} = \{ \left[0\right], \left[1\right], \ldots, \left[n-1\right]\}\)とする(ただし\(\left[k\right]\)は剰余が\(k\)に等しい剰余類)とき、ある\(a \in \mathbb{Z} \)が属する剰余類を\(\left[a\right]\)とするとき、\(\left[a\right], \left[b\right] \in \mathbb{Z}/n\mathbb{Z}\)について

  • \(\left[a\right] + \left[b\right] = \left[a+b\right]\)
  • \(\left[a\right] \times \left[b\right] = \left[a\times b\right]\)

という演算\(+\)と\(\times\)を定義すれば、これは環をなし、このように構成されたものを剰余類環といいます。

これらの演算の意味するところは、剰余類どうしの演算を「それぞれの剰余類から元を1つずつ選び、それらの演算の結果の数が属する剰余類に対応させる」ということです。このときに選ばれる元を代表元といいます。本来は演算が代表元の取りかたによらずに定まることはそれは別に確認しないといけないのですが、ここでは例によって割愛します。

\(\mathbb{Z}/n\mathbb{Z}\)の各元は数ではなく数の集まりなのですが、\(\left[a\right]\)の代表元としていつも\(a\)を取ることにすれば、実質的には\(\mathbb{Z}/n\mathbb{Z} = \{0, 1, \ldots, n-1\}\)であると考えて差し支えないでしょう(少なくともこのシリーズでは)。

というわけで、ではさっそくコードにしていきましょう!

……と言いたいのですが……

悲しいお知らせ

剰余類環の実装にあたって、Swift版をそのままマネて

TPInt を構成し、

と書きたくなりますが……

残念ながらこれはうまくいきません。

まず型パラメータ n はなので n.modulo のようなアクセスはできません。というかそもそもKotlinにはstatic memberなどという概念は存在していないのです

つまり、インスタンスを介さなければメンバにはアクセスできないのですが……

じゃあインスタンス化すればいいじゃない……と言いたくなりますが、これもやはりNGです。Kotlinでは型パラメータからインスタンスを生成することも許されていません。インライン関数に限って言えば、 inline fun <reified n>... としてnを具象化することもできるのですがここではムリなようです……

要するに、型パラメータ n が渡されたとしても、その n から modulo の値を取得する方法がない!さらにインスタンスを生成することもできないので演算の結果とかを返却できない!ということです(少なくともわたしの調査した限りでは。もしあるならばご教授ください)。

じゃあどうしましょうか……

いろいろ考えてみたのですが、ここは潔くこの方法を諦めましょう。

代わりにこういうのはどうでしょうか。

T のコンストラクタを呼ぶのではなく、(サブクラスでoverrideされる前提の)ファクトリメソッドによりインスタンスを作ります。プロパティ modulo については abstract としておくことでクラス内で参照でき、しかもサブクラスでのoverrideを強要できます。

これで Z_<T> の中で modulo にアクセスすることができますし、コンストラクタの代わりに generator を使って

のように書くことができるようになりました!( Z__ という雑な型はここで other: T に対して other.value と書けるようにするために必要です。 T はなんでもよいのではなくて value というメンバを持っていてほしいですからね。)

全体のコードは

です。各メソッド、プロパティにデフォルト実装を与えることで抽象化もたぶんバッチリです。

(ちなみにこの方法、 interface ではできません。というのは Any から継承した equals() と toString() の2つのメソッドを interface で実装することは許されていないからです。)

遠回りしてしまいましたが、これで剰余類環が構成できるようになりました。

としておいて

よさそうですね。\(a = 3 \in \mathbb{Z}_5\)と\(d = 1 \in \mathbb{Z}_{11}\)との間の演算は、これらの型が異なるためコンパイルタイムで弾かれます。型安全!無敵!

identity の取得が非常にダサいですがしかたありません。必要であればパッケージレベルのメソッドなどで対応しましょう。

有限体

さて、この剰余類環\(\mathbb{Z}/n\mathbb{Z}\)ですが、\(n\)が素数のときこれは体となるのでした。こうしてできた体を位数\(n\)の有限体などといい、\(\mathbb{F}_n\)と表します。素数であることがわかりやすいように、これからは\(\mathbb{F}_n\)の代わりに\(\mathbb{F}_p\)と書くことにしましょう(primeのp)。

体をなす、ということは積\(\times\)についての逆元が存在する、ということです。つまり0でない任意の元\(a \in \mathbb{F}_p\)について\(ax \equiv 1 \bmod p\)となる\(x\)が存在します。

\(\mathrm{gcd}\left(a, p\right) = 1\)である(\(p\)は素数なので)ことから\(ax \equiv 1 \bmod p \Leftrightarrow ax + py \equiv 1 \bmod p\)となりますが、この形の式\(ax + by = \mathrm{gcd}(a,b)\)をベズー(Bézout)の等式と呼び、その解\((x,y)\)は拡張ユークリッドの互除法というアルゴリズムで得られることが知られています。

詳しいことはやはり別の文献をあたっていただくことにして、\(a, b\)が与えられたときにべズーの等式\(ax + by = \mathrm{gcd}\left(a, b\right) = 1\)を解くアルゴリズムはこうです。

さて、ここまでくれば有限体くん\(\mathbb{F}_p\)を実装できますね。

有限体クラス class F_ は、その実装は Z_ とおなじ感じでできます。違うのは逆元を表すプロパティ val inverse を持つことです。最終的なコードはこうです!!

使い方も剰余類環のときとおなじです。

としておいて

こうです。よさそうですね(相変わらず identity が……)

次回予告

  • 多項式環を構成しよう!
  • 代数拡大しよう!
  • 遊ぼう

実際のところ長くなりそう、くらいの見通ししかたっておりませんので大雑把な予告に留めておきます。多項式環が構成できればそこからの拡大体の構成は簡単に、とは言わないまでもあっさりできそうな気はしています。余裕があればそこまでいってしまいましょう。

では次回!