はじめに
この記事は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: 最大公約数の略です）。
ユークリッドの互除法
大変な天下りで申し訳ないのですが、最大公約数を求めるアルゴリズムといえば……そう！ユークリッドの互除法ですよね。
解説は他の文献を参照してもらうことにして、コードはこうです。
fun gcd(a: Z, b: Z): Z = when(b) {
0 -> a
else -> gcd(b, a%b)
}
これでわたしたちの有理数もわかりやすい形で表示できるようになります！有理数体クラスQはこのようなコードになるでしょうか。
class Q(val p: Z, val q: Z = 1): Field<Q> {
//...省略
val reduced: Q
get() {
val d = gcd(this.p, this.q)
return Q(p/d, q/d)
}
override fun toString(): String {
val r = this.reduced
return when(r.q) {
1 -> "${r.p}"
else -> "${r.p} / ${r.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版をそのままマネて
interface TPInt {
val modulo: Int
}
class TPInt_5: TPInt {
override val modulo: Int = 5
}
...とTPInt を構成し、
class Z_<n: TPInt>(val value: Z) {
override val modulo
get() = n.modulo
}と書きたくなりますが……
残念ながらこれはうまくいきません。
まず型パラメータn は型なのでn.modulo のようなアクセスはできません。というかそもそもKotlinにはstatic memberなどという概念は存在していないのです。
つまり、インスタンスを介さなければメンバにはアクセスできないのですが……
class Z_<n: TPInt> (val value: Z) {
val t:n = n()
}じゃあインスタンス化すればいいじゃない……と言いたくなりますが、これもやはりNGです。Kotlinでは型パラメータからインスタンスを生成することも許されていません。インライン関数に限って言えば、inline fun <reified n>… としてnを具象化することもできるのですがここではムリなようです……
要するに、型パラメータn が渡されたとしても、そのn からmodulo の値を取得する方法がない！さらにインスタンスを生成することもできないので演算の結果とかを返却できない！ということです（少なくともわたしの調査した限りでは。もしあるならばご教授ください）。
じゃあどうしましょうか……
いろいろ考えてみたのですが、ここは潔くこの方法を諦めましょう。
代わりにこういうのはどうでしょうか。
interface Z__ {
val value: Z
}
abstract class Z_<T: Z__>(override val value: Z): Ring<T>, Z__ {
abstract val generator: (Z)->T
abstract val modulo: Int
//...
}
class Z_5(override val value: Z): Z_<Z_5>(value) {
override val generator: (Z)->Z_5 = { Z_5(it) }
override val modulo: Int = 5
}
T のコンストラクタを呼ぶのではなく、（サブクラスでoverrideされる前提の）ファクトリメソッドによりインスタンスを作ります。プロパティmodulo についてはabstract としておくことでクラス内で参照でき、しかもサブクラスでのoverrideを強要できます。
これでZ_<T> の中でmodulo にアクセスすることができますし、コンストラクタの代わりにgenerator を使って
abstract class Z_/* 省略 */ {
//...省略
override operator fun times(other: T) = generator(this.value * other.value)
}のように書くことができるようになりました！（Z__ という雑な型はここでother: T に対してother.value と書けるようにするために必要です。T はなんでもよいのではなくてvalue というメンバを持っていてほしいですからね。）
全体のコードは
abstract class Z_<T: Z__>(override val value: Z): Ring<T>, Z__ {
abstract val generator:(Z)->T
abstract val modulo: Int
override val identity
get() = generator(1)
override val zero
get() = generator(0)
override operator fun times(other: T) = generator(this.value * other.value)
override operator fun plus(other: T) = generator(this.value + other.value)
override operator fun unaryMinus() = generator(-this.value)
override fun equals(other: Any?): Boolean = when(other) {
is Z_<*> -> (((this.value - other.value) % this.modulo) == 0)
else -> false
}
override fun toString() = "${this.value % this.modulo} mod ${this.modulo}"
}
です。各メソッド、プロパティにデフォルト実装を与えることで抽象化もたぶんバッチリです。
（ちなみにこの方法、interface ではできません。というのはAny から継承したequals() とtoString() の2つのメソッドをinterface で実装することは許されていないからです。）
遠回りしてしまいましたが、これで剰余類環が構成できるようになりました。
class Z_5(override val value: Z): Z_<Z_5>(value) {
override val generator: (Z)->Z_5 = {Z_5(it)}
override val modulo = 5
}
class Z_11(override val value: Z): Z_<Z_11>(value) {
override val generator: (Z)->Z_11 = {Z_11(it)}
override val modulo = 11
}
としておいて
fun main(args: Array<String>) {
val a = Z_5(3)
val b = Z_5(0).identity
val c = Z_5(13)
val d = Z_11(0).identity
println(a) #=> 3 mod 5
println(b) #=> 1 mod 5
println(c) #=> 3 mod 5
println(d) #=> 1 mod 11
println(a+c) #=> 1 mod 5
println(a-c) #=> 0 mod 5
println(a*c) #=> 4 mod 5
// println(a*d) #=> コンパイルエラー!!
println(a==c) #=> true
// println(b==d) #=> コンパイルエラー!!
}よさそうですね。\(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\)を解くアルゴリズムはこうです。
fun bezout(a: Z, b: Z): Triple<Z, Z, Z> {
fun euclid(a: Z, b: Z, qs: Array<Z>): Pair<Array<Z>, Z> = when(b) {
0 -> Pair(qs, a)
else -> {
val q = a / b
val r = a % b
euclid(b, r, arrayOf(q) + qs)
}
}
val (qs, d) = euclid(a, b, arrayOf())
val m = qs.fold(identity(2, 2)){ret, value -> ret * Matrix(2, 2, arrayOf(0, 1, 1, -value))}
return Triple(m[0, 0], m[0, 1], d)
}
さて、ここまでくれば有限体くん\(\mathbb{F}_p\)を実装できますね。
有限体クラスclass F_ は、その実装はZ_ とおなじ感じでできます。違うのは逆元を表すプロパティval inverse を持つことです。最終的なコードはこうです！！
abstract class F_<T: Z__>(override val value: Z): Field<T>, Z__ {
//...省略
override val inverse: T
get() {
val (x, _, _) = bezout(value, modulo)
return generator(x)
}
}使い方も剰余類環のときとおなじです。
class F_5(override val value: Z): F_<F_5>(value) {
override val generator: (Z)->F_5 = {F_5(it)}
override val modulo = 5
}
としておいて
val a = F_5(0)
val b = F_5(1)
val c = F_5(2)
val d = F_5(3)
val e = F_5(4)
val f = F_5(5)
println(a) //#=> 0 mod 5
println(b) //#=> 1 mod 5
println(c) //#=> 2 mod 5
println(d) //#=> 3 mod 5
println(e) //#=> 4 mod 5
println(f) //#=> 0 mod 5
println(b+c) //#=> 3 mod 5
println(c-d) //#=> 4 mod 5
println(d*e) //#=> 2 mod 5
println(e/c) //#=> 2 mod 5
println(a==f) //#=> true
println(b.inverse) //#=> 1 mod 5
println(c.inverse) //#=> 3 mod 5
println(d.inverse) //#=> 2 mod 5
println(e.inverse) //#=> 4 mod 5
println(d*d.inverse==d.identity) //#=> true
こうです。よさそうですね（相変わらずidentity が……）。
次回予告
- 多項式環を構成しよう！
- 代数拡大しよう！
- 遊ぼう
実際のところ長くなりそう、くらいの見通ししかたっておりませんので大雑把な予告に留めておきます。多項式環が構成できればそこからの拡大体の構成は簡単に、とは言わないまでもあっさりできそうな気はしています。余裕があればそこまでいってしまいましょう。
では次回！