Kotlinでも代数学(3)

はじめに

この記事はSwiftで代数学入門シリーズに影響を受けて書かれました。
元記事のその6-その7くらいの内容相当、つまり多項式環から代数拡大するまで、になっております。

今回予告

実は今回で最終回です!

前回の次回予告で

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

と書きました。こんかいはその通り進めましょう。

まずは多項式についてです。

多項式

\[ f\left(x\right) = a_nx^n + a_{n-1}x^{n-1} + \ldots a_1x^1 + a_0\]
という形の式のことを多項式というのでした。
この式において\(a_0, \ldots, a_n \in \mathbb{K}\)(\(\mathbb{K}\)は体)のことを係数いい、また、\(n\)のことを次数というのでしたよね。多項式はこの2つの要素で決定されます。

さっそくこの多項式を表す型を作りましょう。

クラス Polynomial<K> は係数のリストとしてプロパティ coeffs を持ちます。このリストは\(a\left[0\right] = a_0, a\left[1\right] = a_1, \ldots, a\left[n\right] = a_n \)のように\(n+1\)この値を昇順に格納することにします。

さて、この多項式ですが、以下のように演算を定義することで環をなします。

\[ f\left(x\right) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 = \sum_{i=0}^{n} a_i x^i \\ g\left(x\right) = b_n x^n + b_{n-1} x^{n-1} + \cdots + b_1 x + b_0 = \sum_{i=0}^{n} b_i x^i \]

であるとすると、

  • \(f\left(x\right) + g\left(x\right) = \left(\displaystyle \sum_{i=0}^{n} a_i x^i\right) + \left(\displaystyle \sum_{i=0}^{n} b_i x^i\right) = \displaystyle \sum_{i=0}^{n} \left(a_i + b_i \right) x^i \)
  • \(f\left(x\right) \times g\left(x\right) = \left(\displaystyle \sum_{i=0}^{n} a_i x^i\right) \times \left( \displaystyle \sum_{j=0}^{m} b_j x^j \right) = \displaystyle \sum_{i=0}^{m+n}\left( \displaystyle \sum_{i+j=k} a_i b_j \right)x^k \)

です。数式で書かれるとなにがなにやら……となってしまうかもしれません。中学の数学を思い出してみてください。たとえば\(f\left(x\right) = x^2 -2x + 1\)、\(g\left(x\right) = 3x -4\)とすると、

\[ \begin{eqnarray*}f\left(x\right) + g\left(x\right) &=& x^2 + (-2 + 3)x +(1-4) = x^2 + x -3 \\ f\left(x\right) \times g\left(x\right) &=& 3x^3 + \left(-4x^2 – 6x^2\right) + \left(8x + 3x\right) -4 = 3x^3 -10x^2 +11x -4\end{eqnarray*}\]

ですよね。そういう感じです。

ではこれをコードにしていきます。あらかじめコードにしておいたものがこちらです。

先に説明した2つの演算と必要なプロパティを定義し(相変わらずプロパティはひどいですが)環を作りました!元記事に倣い、次数と生成子をとるコンストラクタ constructor(degree:Int, generator: (Int)->K) と、いろいろな便利メソッドも持たせています。

こっそり登場している pow ですが、これは

という Field のメソッドです。 infix として定義することで中置記法が使え、まるで演算子のように利用できます。

確認してみましょう。

いいですね。

これで多項式環\(\mathbb{K}\left[x\right]\)ができました!

多項式でも除算したい

さて、ようやく多項式環\(\mathbb{K}\left[x\right]\)が構成できたわけですが、これからなんとか体を作りたいのです。

以前、整数環\(\mathbb{Z}\)から有限体\(\mathbb{F}_p\)を構成したことを思い出してください。このときは、ある整数\(n \in \mathbb{Z}\)で割ったあまりが等しいものを集めた剰余類環\(\mathbb{Z}/n\mathbb{Z}\)からスタートしたのでした。

多項式でも似たような方法が使えます。

そのためにはまず多項式の除算を考えましょう。

整数の場合

2つの整数\(n, m \in \mathbb{Z}\)(ただし\(n > m\))が、ある数\(q, r \in \mathbb{Z}\)をもって\(n = qm + r\)(ただし\(m > r\))と表せるとき、\(q\)を商、\(r\)を余りといい、この計算を余りつき除算などというのでした。

多項式の場合

いっぽう多項式の場合はどうでしょうか。

次数がそれぞれ\(n\)と\(m\)(ただし\(n > m\))である2つの多項式\(f\left(x\right), g\left(x\right) \in \mathbb{K}\left[x\right]\)について、ある多項式\(h\left(x\right), r\left(x\right) \in \mathbb{K}\left[x\right]\)をもって\[f\left(x\right) = h\left(x\right) \cdot g\left(x\right) + r\left(x\right)\](ただし\(r\left(x\right)\)の次数を\(l\)としたとき\(m > l\))と表せるとき、\(h\left(x\right)\)を商、\(r\left(x\right)\)を余りといいます。

たとえば、\(f\left(x\right) = 2x^3 +x^2 -3x +2\)、\(g\left(x\right) = x^2 + 2\)とすると、\[ f\left(x\right) = \left(2x + 1\right) g\left(x\right) + \left(-5x + 1\right) \]ですから、\(2x+1\)が商、\(-5x+1\)が余り、ということになりますね。

整数の場合とだいたい同じですね。整数では数自体の大小を見ていましたが、多項式の場合、代わりに次数に注目していることに注意してください。

さて、このような「余りつき除算」のことをユークリッド除法といいます。詳しい話は例によって他の文献を参照していただくとして、\(f\left(x\right)\)と\(g\left(x\right)\)とでユークリッド除法の計算をするメソッド eucDiv はこんな感じです。

Pair の最初の要素に商、2番目の要素に余りが返されます。

試してみましょう。

はい。バッチリですね!

多項式の剰余類環

整数の場合、2数\(a, b \in \mathbb{Z}\)について、ある数\(n \in \mathbb{Z}\)で割った余りが等しいとき、これを\(n\)を法として合同といい、\(a \equiv b \bmod n\)と表すのでしたよね。

多項式の場合も同様にして、2つの多項式\(f_1\left(x\right), f_2\left(x\right) \in \mathbb{K}\left[x\right]\)について、ある多項式\(g\left(x\right) \in \mathbb{K}\left[x\right]\)で割った余りが等しいとき、これを\(g\left(x\right)\)を法として合同といい、\(f_1\left(x\right) \equiv f_2\left(x\right) \bmod g\left(x\right) \)と表すことができます。

先の例でいえば、\(f\left(x\right) = 2x^3 + x^2 -3x + 2\)を\(g\left(x\right) = x^2 + 1\)で割ったときの余りは\(-5x + 1\)でした。したがって\(f\left(x\right) \equiv -5x + 1 \bmod g\left(x\right) \)である、ということです。

というわけで、(除数\(n\)を固定して剰余類環\(\mathbb{Z}/n\mathbb{Z}\)を構成したように)\(g\left(x\right)\)を固定して、余りによって多項式環\(\mathbb{K}\left[x\right]\)を分類することで多項式の剰余類環\(\mathbb{K}\left[x\right]/g\left(x\right)\)が構成できることになります!

実装

さて、その「多項式の剰余類環」ですが、整数の剰余類環の(悲しみの)実装とほぼ同じです。

値のプレースホルダとなるインターフェイス P__<K: Field<K>> を実装し、コンストラクタの代わりに生成子を使うようにして各演算を定義するのみです。

といって出来上がったものがこちら。

これを

のように実装して使います。抽象化具合が残念なことになってますが……

先ほどの例で試してみましょう。

よさそうですね。

多項式の最大公約数

さて、ようやく、ようやく準備が整いました。これで多項式の体を作ることができます。

\[ \begin{eqnarray} f\left(x\right) &=& x^3 -3x +2x \\ g\left(x\right) &=& x^2 -5x + 6\end{eqnarray} \]

という多項式について考えてみましょう。

それぞれ因数分解すると

\[ \begin{eqnarray} f\left(x\right) &=& x^3 -3x +2x = x\left(x-1\right)\left(x-2\right) \\ g\left(x\right) &=& x^2 -5x + 6 = \left(x-2\right)\left(x-3\right)\end{eqnarray} \]

であることから\(x-2\)が(最大)公約数だと考えることができますね。すなわち\(\textrm{gcd}\left(f\left(x\right), g\left(x\right)\right) = x-2 \)ということです。

整数の場合と同様にして、これらの多項式にもユークリッドの互除法を適用することができます。ということはやはり同様にしてべズーの等式を得ることもできるでしょう。

つまり、ある多項式\(p\left(x\right), q\left(x\right) \in \mathbb{K}\left[x\right]\)が存在して\(f\left(x\right)p\left(x\right) + g\left(x\right)q\left(x\right) = \mathrm{gcd}\left(f\left(x\right), g\left(x\right)\right)\)となるはずですよね。

さきほどユークリッド除法というのが出てきましたが、このユークリッド除法が可能な環をユークリッド環などというのでした。 eucDiv を演算として持つ環としてこれを定義してみましょう。

これを使って、以前整数\(\mathbb{Z}\)専用に定義した gcd() や bezout() をユークリッド環であれば計算可能なように拡張できます。

ジェネリクスのためinlineかつreifiedになっていることを除けば整数版のものと同じ計算です。なお、関数 euclid() はinlineである制約から再帰呼び出しできないのでループを使った実装になっています。

やはり先の例で確認してみます。

おっけーのようです。

さて、体

整数の場合、\(n\)が素数のとき\(\mathbb{Z}/n\mathbb{Z}\)は体となるのでした。

ある多項式\(g\left(x\right) \in \mathbb{K}\left[x\right]\)が\(g\left(x\right) = g_1\left(x\right)g_2\left(x\right)\)のように因数分解できないとき、これを既約な多項式といい、整数でいうところの素数にあたります。

ということはこのような既約多項式\(g\left(x\right)\)を持ってくれば任意の多項式について\(\mathrm{gcd}\left(f\left(x\right), g\left(x\right)\right) = 1\)となります(因数分解できないのだから自身以外の多項式について公約数を持ちませんよね)。したがって、べズーの等式\(f\left(x\right)p\left(x\right) + g\left(x\right)q\left(x\right) = \mathrm{gcd}\left(f\left(x\right), g\left(x\right)\right) \Leftrightarrow f\left(x\right)p\left(x\right) \equiv 1 \bmod g\left(x\right)\)となり、\(p\left(x\right)\)が\(f\left(x\right)\)の(\(g\left(x\right)\)上の)逆元です。

まとめると、多項式の場合、\(g\left(x\right)\)が既約であるとき、\(\mathbb{K}\left[x\right]/g\left(x\right)\)は体になります!

実装!!

さっそくですがコードです。ドン!

Field を実装し、必要なパラメータ inverse を持たせるだけです。

これを使って

として……

できました!!

拡大……!!

実はさきほどの体\(\mathbb{K}\left[x\right]/\left(x^2 – 2\right)\)は有理数体に\(\sqrt{2}\)をつけて拡大したものに他ならないのです。

どういうことかというと、\(g\left(x\right)\)において\(x^2 -2 \equiv 0 \bmod g\left(x\right) \Leftrightarrow x^2 \equiv 2 \bmod g\left(x\right)\)なので\(x \equiv \sqrt{2}\)ですよね。

確認です。

2乗して\(2\)になる\(a\)は明らかに\(\sqrt{2}\)です。その他の計算も\(a=\sqrt{2}\)として正しい結果になっていますね。

これでKotlinでも代数拡大できました!!!

おまけ

ここからは代数拡大で遊んでみます。

複素数体\(\mathbb{C}\)といえば実数体\(\mathbb{R}\)に\(i^2 = -1\)なる数を追加して拡大して作られる体です。これを実装……といきたいところですが、みなさんご存知の通りコンピュータで\(\mathbb{R}\)を作ることはできませんから、代わりに\(\mathbb{Q}\)を使ってガウス数体\(\mathbb{Q}\left(i\right)\)を作ってみましょう。

とはいえこれまでとぜんぜん変わりませんけどね。

としておいて

さきほどと同じく、2乗して\(-1\)になる\(i\)は虚数単位です!

また、

とすればこれは1の3乗根\(\zeta_3\)を持つ体になります。

ね?

おわりに

Kotlinでも代数拡大できました!!

読み返してみて、長すぎなので分割してもよかったなと思いました。でもせっかくの最終回ですしまぁいいのではないでしょうか。

ちょっと遊び足りない気もしますが……

では!