時計の世界の環

up:: 代数学

Swiftで代数学入門〜 4. 時計の世界の「環」 - Qiita

ちょっと別へ。整数や有理数体より小さい、けれど環を満たす数の集合を考える。曜日数とか時計。

整数全体を一周分の目盛りの降られた輪に巻き付け、同じところに来る数を同じとする。一周が5なら1,6,11…が同じ扱いになる。

どの点であっても、同じ扱いの数の差は「一周分」の何倍かになる。1と6の差は5の一倍、1と11の差は5の二倍。

この一周分をn、二つの同じ扱いの数a,bの差がnの倍数の時、a,bはnを法として合同といい、 $a \equiv b (mod n)$ と書く。

整数環Zを、「nを法とする合同」関係で分類して出来るのが、n時間時計の世界Zn。この世界では合同な数は全て最小のものになるため、数はn種類しかない。

この合同な数の最小整数、あるいはn種類の中にある数は合同類の中の整数と呼ぶ。

このZnに演算を突っ込めば数になる。

「法」を型に持つ

法になる数値nをパラメータとしてZnを表すstruct Z_<n>を作る。

……が、struct型を構成するパラメータ＝必須要素としてn、つまりInt値を追加することはswiftだと出来ない。型パラメータに入るのは型のみ。

なので「「Int型の値」を表す型」を作る。
つまり値ごとに型を作るということ。

まずはプロトコル。

protocol TPInt {
    static var value: Int { get }
}

そしてこれを実装して型を作る。

struct TPInt_5 : TPInt {
    static let value = 5
}

一応、0とその足し算(型を受け、その中のvalue読んで1足す)を定義する型を用意し、任意の数になるまで型を作るという手もある。

struct TPInt_0 : TPInt {
    static let value = 0
}
 
struct TPInt_Succ<n: TPInt> : TPInt {
    static var value: Int {
        return n.value + 1
    }
}
 
typealias TPInt_1 = TPInt_Succ<TPInt_0>
typealias TPInt_2 = TPInt_Succ<TPInt_1>
...
typealias TPInt_5 = TPInt_Succ<TPInt_4>

これで struct Z_<n: TPInt> に対して typealias Z_5 = Z_<TPInt_5> とすれば、それがZ5。
今更だがtypealiasはtypeに別名を付ける機能。C++でのtypedefみたいなの。

ちなみに型パラメータで型状態を固定するこの方法は、幽霊型と呼ばれるデザインパターンの一つ。状態チェックをコンパイル時で行えるらしい。

剰余類環の実装

Znの中身を作る。

struct Z_<n: TPInt> {
    var mod: Int {
        return n.value
    }
 
    let value: Z
 
    init(_ value: Int) {
        self.value = value
    }
}

法を出力するmod、合同類の中の整数を入れるvalue、インスタンスを作る際に入れた引数を合同類の中の整数にしてvalueに放り込むイニシャライザ。

ついでIntegerLiteralConvertible と CustomStringConvertibleに準拠させる。

extension Z_ : IntegerLiteralConvertible {
    init(integerLiteral value: IntegerLiteralType) {
        self.init(value)
    }
}
 
extension Z_ : CustomStringConvertible {
    var description: String {
        return "\value mod \(mod)"
    }
}

結果はこんな感じ。

typealias Z_5 = Z_<TPInt_5>
let a: Z_5 = 1               // 1 mod 5

イコールの定義

ようやく計算を突っ込み始める。まずはイコールから。

Znでのイコールとは合同のこと。そのままでは実装できないので変形。

a \equiv b (mod n) \Leftrightarrow a - b \in n Z

もともと合同の定義が「a,bの差がnの倍数である」ということなので、元に戻しただけ。というわけで右のを実装。差に対して剰余演算%を使い、余りが0になるかどうか調べる。

ではEquatableを実装しメソッド追加。

struct Z_<n: TPInt> : Equatable {
    ...
    func ==<n: TPInt>(a: Z_<n>, b: Z_<n>) -> Bool {
        return (a.value - b.value) % n.value == 0
    }
}

オペレーターのオーバーライドには引数ラベルは最初から必要ない。また、型と同じ、もしくは型から読める(プロトコルの方として呼んだりすること)型引数を付ける。
当然ながら、同じ法同士の数でないと比較できないようにしていることには注意。

実際動かすとこう。

typealias Z_5 = Z_<TPInt_5>
let a: Z_5 = 2   // 2  mod 5
let b: Z_5 = 37  // 37 mod 5
a == b           // true

四則演算の定義

よーしじゃあRingを実装すればもう四則演算だな、とはならない。確認しなきゃいけないことがある。

struct Z_<n: TPInt> : Ring {
   ...
   func +<n: TPInt>(a: Z_<n>, b: Z_<n>) -> Z_<n> {
    return Z_<n>(a.value + b.value)
}
}

valueに入ってるのは合同類の整数。元の数はZn型の中にはないが、はたして「元の整数を合同類の整数にしたものの足し算結果」は「元の整数の足し算結果を合同類の整数にしたもの」と常に等しくなるのか。

これの確認は $a \equiv b, c \equiv d$ のとき $a + c \equiv b + d$ であることを調べればいい。合同類の整数の中で適当にスライドさせた値二つは、どこで足しても合同になる。

この時、 $a - b, c - d$ は合同の定義よりnの倍数なので、それぞれ $kn, l n (k, l \in Z)$ と書ける。

{\begin{eqnarray} (a + c) - (b + d) &=& (a - b) + (c - d) \\ &=& kn + ln \\ &=& (k + l)n \end{eqnarray} }

よってこのように変換できる。これは $(a + c) - (b + d)$ がnの倍数であるということになる。ならば $a + c \equiv b + d$ ということになる。これは1+2と321+47は整数としては別のものだが、5を法とした合同類では同じ1+2になってるということ。

もう一つ確認する必要がある。+が加法群を成すかどうか。
群の定義は300、交換則逆元単位元。単位元0はZ_<n>(0)になる。交換則はRingのデフォルト実装。なので逆元としてーの演算を追加。

prefix func -<n: TPInt>(a: Z_<n>) -> Z_<n> {
    return Z_<n>(-a.value)
}

続いて掛け算を追加。

func *<n: TPInt>(a: Z_<n>, b: Z_<n>) -> Z_<n> {
    return Z_<n>(a.value * b.value)
}

＊がモノイド、つまり交換則と単位元を成すことは確認。
1は0と同じく定義され、交換則はデフォルト実装。

この後はprintAddOpTableなどを使って演算表を見る。
演算表を見ると、＋は対角線上で表が対称になるので、可換ということが分かる。さらに、Z5なら全ての掛け算にかけて単位元1になる値があることが分かる。つまりZ5は体。

一方、Z6は1になる値もしくは0になる値があるだけなので、体ではない。この違いは次回、有限体で。

Sonolart

エクスプローラー

時計の世界の環

目次

「法」を型に持つ

剰余類環の実装

イコールの定義

四則演算の定義

グラフビュー

目次

バックリンク