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

どうも、佐野です。これまで整数環 `Z: Ring` や有理数体 `Q: Field` を作ってきましたが、環や体になるのは $\mathbb{Z}$ や $\mathbb{Q}$ のような大きなものばかりではありません。今回は「時計の世界」に住む可愛い数たちを紹介します。

## 目次：

1. [数とは何か？](bd356c59dc0559ee9a0b)
2. [群・環・体の定義](733e0ecf12da359db729)
3. [有理数を作ってみよう](222a6a418fb29a0684f8)
4. [時計の世界の「環」](91fbc70136b0e5706c09) _← イマココ_ 
5. [小さな「体」を作ろう](f5cd40bf669fa8511f9b)
6. [多項式は整数によく似てる](83be0ad7d2f2e4f3f44d)
7. [代数拡大で数を作ろう！](ccf7ece3dfeb98b38946)

# 時計の世界の整数

今回の内容は [@tsujimotter](https://twitter.com/tsujimotter) さん『[時計の世界の整数論](http://www.slideshare.net/junpeitsuji/maths4pg)』の発表スライドを引用しながら説明させて頂きます:pray:

小学校の算数で $5 + 8 = [\ \ \ ]$ のような問題があったとして、$[\ 13\ ]$ 以外を入れたら間違いなくバツを食らうでしょう。でも時計の中で考えると「$5$時の$8$時間後は$1$時」なので $[\ 1\ ]$ でも良さそうです。あるいは曜日だと「金曜日($5$)の$8$日後は土曜日($6$)」なので $[\ 6\ ]$ でも良さそうです。

時計や曜日のような「ループする数の世界」を考えてみましょう。整数全体を「一周分の目盛りのふられた輪」にグルグルと巻きつけて、同じところに来る数を同じと見なします。「$5$ 時間時計」なら「$1, 6, 5, 16, \cdots$」は全部同じ「$1$ 時」です。

![](https://qiita-image-store.s3.amazonaws.com/0/8146/2bfbe92e-0e91-50c5-fdeb-ffe6872ae5ca.png)

このことをより数学的に（そしてプログラム的に）扱いやすくするには、同じところに来る数の差に注目します。どの点においても、その点に来る数の差は「一周分」の何倍かになっています。「$1, 6, 5, 16, \cdots$」は全て $5$ の倍数間隔になってますよね。

この「一周分」を $n$ として、二つの数 $a, b$ の差が $n$ の倍数のとき $a, b$ は「$n$ を法として合同」といい、$a \equiv b \pmod{n}$ と書きます。整数環 $\mathbb{Z}$ を $n$ を法とする合同関係で分類したときにできるのが「$n$ 時間時計の世界」$\mathbb{Z}_n$ です。ここには「数」が $n$ 個しかありません。

（前回も有理数を作るときの「あるルールでまとめたグループを一つのものと見なす」という考え方をしました）

![](https://qiita-image-store.s3.amazonaws.com/0/8146/3e7161fc-4226-b83b-561c-523191855c56.png)

この「時計」に演算を入れることで「数」としての生命を帯びるようになります。
実装しながら見ていきましょう！

## 「法」を型に持てるようにするには？

まず `n` をパラメータとして $\mathbb{Z}_ n$ を表す `struct Z_<n>` を作りたいのですが、ここで `n: Int` だったら型パラメータとして渡すことはできません。Swift で型パラメータに渡せるのは「型」だけです。

「型」しか渡せないというのなら、「「`Int`型の値」を表す型」を大胆に作ってしまいましょう。これがその型の `protocol` です：

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

そして例えば `5` を表す `TPInt_5` を作る場合は、こうすればいいのです：

```swift
struct TPInt_5 : TPInt {
    static let value = 5
}
```

あるいはペアノ式に：

```swift
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>` とすれば、それが $\mathbb{Z}_ 5$ です！

型レベルで `n` を固定することができれば演算は `Z_<n>` の中だけで定義できるので、別の法を持つ合同類と間違って足したりということが（コンパイラレベルで）できなくなります。まさに型安全 :muscle: 

（「[Swift で Phantom Type（幽霊型）](http://qiita.com/taketo1024/items/71e3272211f08d7e0cde)」でやってることと本質的に同じです）

## 剰余類環の実装

では $\mathbb{Z}_n$ を作っていきましょう：

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

`Z_<n>` の `n.value` を簡単に取り出せるように `mod` プロパティを入れておきます。`value: Z` として、その合同類の中の整数を持てるようにしましょう。先にデバッグしやすいように `IntegerLiteralConvertible` と `CustomStringConvertible` を適合しておきます：

```swift
extension Z_ : IntegerLiteralConvertible {
    init(integerLiteral value: IntegerLiteralType) {
        self.init(value)
    }
}

extension Z_ : CustomStringConvertible {
    var description: String {
        return "\value mod \(mod)"
    }
}
```

そしたらこうできます：

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

いいですね、早くもそれっぽくなってる感じがします。

## イコールの定義

`Z_<n>` でのイコールを定義するには、「中の数」の合同を実装すれば良いことになります。「整数の合同」の定義はなんだったか思い出すと：

```math
a \equiv b \pmod{n}\ \Leftrightarrow \ a - b \in n \mathbb{Z}
```

$n \mathbb{Z}$ は「$n$ の倍数全体」です（$\mathbb{Z}$を丸ごと $n$ 倍したイメージ）。「$a$ と $b$ の差は $n$ の倍数」ということです。これをプログラムで実装するのは簡単です、剰余演算 `%` を使って差の余りが `0` かどうかを調べればいいのです。

`Z_<n> : Equatable` として `==` 演算を定義しましょう。

```swift
struct Z_<n: TPInt> : Equatable {
   ...
}
```

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

できました。`==` はジェネリック型 `<n: TPInt>` を一つだけ取っていて、引数の型はどちらも `Z_<n>` で固定されている点に注目してください。

確認してみましょう：

```swift
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
```

問題なさそうです！

## 四則演算の定義

次に `Z_<n> : Ring` として足りない演算を入れて行きましょう。

```swift
struct Z_<n: TPInt> : Ring {
   ...
}
```

まずは足し算：

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

…あれ、これでいいのでしょうか？ 例えば $1 \bmod 5$ は $\lbrace \cdots, 1, 6 ,11, 16, \cdots \rbrace$ を同じと見なしたもので、 `value` として持っているのは $1$ かもしれませんし $16$ かもしれませんし $198234191$ かもしれません。

「同じもの」ってことにしてるものを足した結果が「違うもの」になることはないのか？これを確認するには、$a \equiv b, c \equiv d$ のとき $a + c \equiv b + d$ かどうかを調べなければいけません。$a - b, c - d$ は合同の定義により $n$ の倍数なので、それぞれ $kn, ln \ (k, l \in \mathbb{Z})$ と書けるはずです。すると：

```math
\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$ になってるということです。

正直この手の確認作業は全く楽しくないですが（楽しい人いたらごめんなさい）、同値類の代表元を使って演算や写像を定義する場合、それが代表元の取り方によらず定まるということは確認しなければなりません。グループの代表者として誰を選ぶかで、全然違う結論になったら困るというです（現実世界では割と起こりがちですが）。

この `+` がちゃんと加法群を成すかも確認しなければなりません。まずゼロ元は `Z_<n>(0)` で、これは `Ring` のデフォルト実装によって入るものです。これがゼロだということは、時計の世界では「$1$周, $2$周, $3$周, ...」は全てゼロだということです。

`prefix -` はこうです：

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

以上でちゃんと加法群の公理が満たされることを「[群の定義](http://qiita.com/taketo1024/items/733e0ecf12da359db729)」を振り返りながら確認してみてください（演習）。

次に掛け算です：

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

まずこれが代表元の取り方によらないことは確認する必要があります。単位元は `Ring` のデフォルト実装で定まる `Z_<n>(1)` で、`Z_<n>` が `*` に関してモノイドを成すことも確認してください（演習）。

こうして `Z_<n>` に足し算と掛け算を入れ、環構造を定めることができました！

![](https://qiita-image-store.s3.amazonaws.com/0/8146/6bd7e4b0-2174-5943-5245-fa379a95a120.png)


## 遊んでみよう！
`Z_<n>` ができたので、いろいろな `n` を入れて遊んでみましょう。

演算の様子を一望するには「演算表」を作るのが一番です。 `printAddOpTable` という関数を作って、 `Z_5` の加法の演算表を見てみましょう：

```swift
let values: [Z_5] = [0, 1, 2, 3, 4]
printAddOpTable(values)
```

```
+	|	0	1	2	3	4
--------------------------
0	|	0	1	2	3	4
1	|	1	2	3	4	0
2	|	2	3	4	0	1
3	|	3	4	0	1	2
4	|	4	0	1	2	3
```

例えば `(4, 3)` 成分には `2` があり、これは $4 + 3 \equiv 2 \pmod{5}$ ということです。各行に一つだけ $0$ となる列があります。例えば `4` 行を見ると、`1` 列と交わるところが `0` になってます。これは $-4 \equiv 1 \pmod{5}$ ということです。表が対角線に沿って対称なので、加法が可換だということも分かります。

次に乗法の演算表です：

```swift
printMulOpTable(values)
```

```
*	|	0	1	2	3	4
--------------------------
0	|	0	0	0	0	0
1	|	0	1	2	3	4
2	|	0	2	4	1	3
3	|	0	3	1	4	2
4	|	0	4	3	2	1
```

`0` との積は常に `0` で、`1` との積は不変です。加法の場合と同じく、各行に一つだけ $1$ となる列があります。例えば `(3, 2)` 成分が `1` になってます。これは $3 \cdot 2 \equiv 1 \pmod{5}$ というで、$3$ の逆数は $2$ だということです。 

$0$ でない全ての元が掛けて $1$ になる元を持つということは…つまり $\mathbb{Z}_5$ は「体」だということです！$\mathbb{Z}_5 = \lbrace 0, 1, 2, 3, 4 \rbrace$ と数が $5$ つしかない世界が「体」になっていて、有理数や実数みたいに $+, -, \times, \div$ ができるなんて驚きませんか？

今度は `n = 6` の場合を見てみましょう：

```swift
typealias Z_6 = Z_<TPInt_6>
let values: [Z_6] = [0, 1, 2, 3, 4, 5]
printAddOpTable(values)
printMulOpTable(values)
```

```
+	|	0	1	2	3	4	5
------------------------------
0	|	0	1	2	3	4	5
1	|	1	2	3	4	5	0
2	|	2	3	4	5	0	1
3	|	3	4	5	0	1	2
4	|	4	5	0	1	2	3
5	|	5	0	1	2	3	4
```

```
*	|	0	1	2	3	4	5
------------------------------
0	|	0	0	0	0	0	0
1	|	0	1	2	3	4	5
2	|	0	2	4	0	2	4
3	|	0	3	0	3	0	3
4	|	0	4	2	0	4	2
5	|	0	5	4	3	2	1
```

加法の演算表は `Z_5` の場合とそんなに変わりませんが、乗法はかなり違います。まず各行に対して掛けて `1` になる列が必ずしもありません。また `(2, 3)`成分など `0` でない数同士をかけて `0` になるところがいくつかあります。`1` が出てくる行と `0` が出てくる行の違いはなんでしょう…？

次回は「有限体」で、この秘密に迫ります！

（サンプルコードは追って公開するので、ぜひ手元で遊んでみてください）

## 参考
> ![](https://qiita-image-store.s3.amazonaws.com/0/8146/a8a8e234-231a-1a17-dea4-56e55817e507.png)
> 
> **「時計の世界の整数論」** [発表動画](https://www.youtube.com/watch?v=9yq4r_Zapx4) / [資料](http://www.slideshare.net/junpeitsuji/maths4pg) by [@tsujimotter](https://twitter.com/tsujimotter)

「[第2回 プログラマのための数学勉強会](http://taketo1024.hateblo.jp/entry/report/20150327)」での @tsujimotter さんの発表スライドを引用させて頂きました。「フェルマーの小定理」から「平方剰余の相互法則」まで分かりやすく説明してくれます。今回の記事で「時計の世界の整数」に興味を持たれた方は是非ご覧ください:+1:

## ソースコード

GitHub: [SwiftyAlgebra](https://github.com/taketo1024/SwiftyAlgebra/blob/master/README.md)

* [QuotientRing](https://github.com/taketo1024/SwiftyAlgebra/blob/master/Algebra.playground/Sources/Quotient/QuotientRing.swift)
* [IntQuotientRing](https://github.com/taketo1024/SwiftyAlgebra/blob/master/Algebra.playground/Sources/Quotient/IntQuotientRing.swift)

## 宣伝
* 3/19(土) 「[第6回 プログラマのための数学勉強会](http://eventdots.jp/event/582339)」
* プログラマのための数学勉強会 [Facebook ページ](https://www.facebook.com/プログラマのための数学勉強会-1566085336971723/?ref=bookmarks)
* 個人ブログ [Imaginary & Imaginative](http://taketo1024.hateblo.jp)