Kotlinでも代数学(3)

Posted on by まろまろ

はじめに

この記事は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つの要素で決定されます。

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

class Polynomial<K: Field>(val coeffs: List<K>) {}

クラス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*}\]

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

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

class Polynomial<K: Field<K>>(val coeffs: List<K>): Ring<Polynomial<K>> {
  constructor(degree: Int, generator: (Int)->K): this((0 .. degree).map{ generator(it) })

  override val zero: Polynomial<K>
    get() = Polynomial(0){_ -> coeffs[0].zero}
  override val identity: Polynomial<K>
    get() = Polynomial(0){_ -> coeffs[0].identity}
  val degree: Int
    get() {
      (coeffs.size - 1 downTo 0).forEach { if(coeffs[it] != coeffs[0].zero) { return it } }
      return 0
    }

  override operator fun times(other: Polynomial<K>): Polynomial<K> = Polynomial(this.degree + other.degree) {
    (0 .. it).fold(coeffs[0].zero) {
      res, j ->
      res + this[j] * other[it-j]
    }
  }

  override operator fun times(other: Int): Polynomial<K> = Polynomial(this.degree) { this[it] * other }

  override operator fun plus(other: Polynomial<K>): Polynomial<K> {
    val d = if(this.degree > other.degree) { this.degree } else { other.degree }
    return Polynomial(d){this[it] + other[it]}
  }

  override operator fun unaryMinus(): Polynomial<K> = Polynomial(this.degree){ -this[it] }

  override fun equals(other: Any?): Boolean = when(other) {
    is Polynomial<*> -> if(this.degree == other.degree) {
      this.coeffs.zip(other.coeffs).all{ (t, o) -> t == o }
    } else {
      false
    }
    else -> false
  }

  operator fun get(i: Int): K = if(i <= this.degree) { coeffs[i] } else { coeffs[0].zero }

  fun apply(x: K): K = (0..this.degree).fold(coeffs[0].zero) { sum, i -> sum + this[i] * (x pow i)}

  fun map(acc: (K)->K): Polynomial<K> = Polynomial(coeffs.map(acc))
}

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

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

infix fun <K> Field<K>.pow(n: Int): K = if(n == 0) { this.identity } else { this * this.pow(n - 1) }

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

確認してみましょう。

fun constructPolynomialQ(vararg coeffs: Int): Polynomial<Q> = Polynomial(coeffs.map{ Q(it) })

fun main(args: Array<String>) {
  val f = constructPolynomialQ(1, -2, 1)
  val g = constructPolynomialQ(-4, 3)

  println(f) //#=> x^2 + -2x + 1
  println(g) //#=> 3x + -4

  println(f+g) //#=> x^2 + x + -3
  println(f*g) //#=> 3x^3 + -10x^2 + 11x + -4
}

いいですね。

これで多項式環\(\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 はこんな感じです。

  infix fun <K: Field<K>> Polynomial<K>.eucDiv(other: Polynomial<K>): Pair<Polynomial<K>, Polynomial<K>> {
    fun eucDivMonomial(f: Polynomial<K>, g: Polynomial<K>): Pair<Polynomial<K>, Polynomial<K>> {
      val n = f.degree - g.degree
      if(n < 0) {
        return Pair(Polynomial(0){ _ -> f[0].zero }, f)
      } else {
        val a = f.leadCoeff / g.leadCoeff
        val q = Polynomial(n){ if(it == n) { a } else { f[0].zero } }
        val r = f - q * g
        return Pair(q, r)
      }
    }

    val d = if(this.degree > other.degree) { this.degree - other.degree } else { 0 }

    return (d downTo 0).fold(Pair(this.zero, this)) {
      (q, r), _ ->
        val (mq, mr) = eucDivMonomial(r, other)
        Pair(q + mq, mr)
    }
  }

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

試してみましょう。

fun constructPolynomialQ(vararg coeffs: Int): Polynomial<Q> = Polynomial(coeffs.map{ Q(it) })

fun main(args: Array<String>) {
  val f = constructPolynomialQ(2, -3, 1, 2)
  val g = constructPolynomialQ(1, 0, 1)

  println(f) //#=> 2x^3 + x^2 + -3x + 2
  println(g) //#=> x^2 + 1

  val (q, r) = f eucDiv g

  println(q) //#=> 2x + 1
  println(r) //#=> -5x + 1

  println(f == g * q + r) //#=> true
}

はい。バッチリですね！

多項式の剰余類環

整数の場合、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>> を実装し、コンストラクタの代わりに生成子を使うようにして各演算を定義するのみです。

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

interface P__<K: Field<K>> {
  val poly: Polynomial<K>
}

abstract class PolynomialQuotientRing<P: P__<K>, K: Field<K>> (override val poly: Polynomial<K>): Ring<P>, P__<K> {
  abstract val generator: (Polynomial<K>) -> P
  abstract val monomialGen: (K) -> P
  abstract val value: Polynomial<K>

  override val identity
    get() = monomialGen(poly.coeffs[0].identity)
  override val zero
    get() = monomialGen(poly.coeffs[0].zero)

  override operator fun times(other: P): P = generator(this.poly * other.poly)
  override operator fun times(other: Int): P = generator(this.poly * other)
  override operator fun plus(other: P): P = generator(this.poly + other.poly)
  override operator fun unaryMinus(): P = generator(-this.poly)

  override fun toString(): String = "$poly mod $value"
}

これを

class g(override val poly: Polynomial<Q>): PolynomialQuotientRing<g, Q>(poly) {
  constructor(vararg coeffs: Int): this(Polynomial(coeffs.map{ Q(it) }))
  constructor(vararg coeffs: Q): this(Polynomial(coeffs.toList()))

  override val generator: (Polynomial<Q>) -> g = ::g
  override val monomialGen: (Q) -> g = { g(it) }

  override val modulo: Polynomial<Q> = constructPolynomialQ(1, 0, 1)

  override fun equals(other: Any?): Boolean = when(other) {
    is g -> (this.poly - other.poly) % this.modulo == constructPolynomialQ(0)
    else -> false
  }
}

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

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

fun main(args: Array<String>) {
  val f = g(2, -3, 1, 2)
  val r = g(1, -5)

  println(f) //#=> 2x^3 + x^2 + -3x + 2 mod x^2 + 1
  println(r) //#=> -5x + 1 mod x^2 + 1

  println(f == r) //#=> true
}

よさそうですね。

多項式の最大公約数

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

\[ \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 を演算として持つ環としてこれを定義してみましょう。

interface EuclideanRing<T>: Ring<T> {
  infix fun eucDiv(other: T): Pair<T, T>
  operator fun rem(other: T): T
}

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

fun <R: EuclideanRing<R>> gcd(lhs: R, rhs: R): R = when(rhs) {
  lhs.zero -> lhs
  else -> gcd(rhs, lhs % rhs)
}

inline fun <reified R: EuclideanRing<R>> euclid(lhs: R, rhs: R): Pair<Array<R>, R> {
  var a = lhs
  var b = rhs
  var qsp: Array<R> = arrayOf()

  while(b != a.zero) {
    val (q, r) = a eucDiv b
    a = b
    b = r
    qsp = arrayOf(q) + qsp
  }

  return Pair(qsp, a)
}

inline fun <reified R: EuclideanRing<R>> bezout(a: R, b: R): Triple<R, R, R> {
  val (qs, d) = euclid(a, b)
  val m: Matrix<R> = qs.fold(Matrix(2, 2, arrayOf(a.identity)).identity) {
    ret, value ->
    ret * Matrix(2, 2, arrayOf(a.zero, a.identity, a.identity, -value))
  }

  return Triple(m[0, 0], m[0, 1], d)
}

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

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

fun main(args: Array<String>) {
  val f = constructPolynomialQ(0, 2, -3, 1) //#=> x^3 + -3x^2 + 2x
  val g = constructPolynomialQ(6, -5, 1) //#=> x^2 + -5x + 6

  println(gcd(f, g)) //#=> 6x + -12

  val (p, q, r) = bezout(f, g)

  println(p) //#=> 1
  println(q) //#=> 6x + -12
  println(r) //#=> true

  println(f*p + g*q == r)
}

おっけーのようです。

さて、体

整数の場合、\(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)\)は体になります！

実装！！

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

abstract class PolynomialQuotientField<P: P__<F>, F: Field<F>>(override val poly: Polynomial<F>): Field<P>, P__<F> {
  abstract val generator: (Polynomial<F>) -> P
  abstract val monomialGen: (F) -> P
  abstract val polyGen: (F) -> Polynomial<F>

  abstract val modulo: Polynomial<F>

  override val inverse: P
    get() {
      val (p, _, r) = bezout(poly, modulo)
      return generator(p * polyGen(r.coeffs[0].inverse))
    }

  // ...省略
}

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

これを使って

class g(override val poly: Polynomial<Q>): PolynomialQuotientField<g, Q>(poly) {
  constructor(vararg coeffs: Int): this(Polynomial(coeffs.map{ Q(it) }))
  constructor(vararg coeffs: Q): this(Polynomial(coeffs.toList()))

  override val generator: (Polynomial<Q>) -> g = ::g
  override val monomialGen: (Q) -> g = { g(it) }
  override val polyGen: (Q) -> Polynomial<Q> = { Polynomial(it) }

  override val modulo: Polynomial<Q> = constructPolynomialQ(-2, 0, 1)

  override fun equals(other: Any?): Boolean = when(other) {
    is g -> (this.poly - other.poly) % this.modulo == constructPolynomialQ(0)
    else -> false
  }
}

として……

fun main(args: Array<String>) {
  val f = g(1, 1)

  println(f) //#=> x + 1 mod x^2 + -2
  println(f.inverse) //#=> x + -1 mod x^2 + -2

  println(f * f.inverse) //#=> 1 mod x^2 + -2
}

できました！！

拡大……！！

実はさきほどの体\(\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}\)ですよね。

確認です。

fun main(args: Array<String>) {
  val a = g(0, 1)
  println(a) //#=> x mod x^2 + -2
  println(a*a) //#=> 2 mod x^2 + -2
  println(a * a == g(2)) //#=> true

  val aa = g(1) + a //#=> 1 + \sqrt{2}のつもり
  val asq = aa * aa
  val rhs = a * 2 + g(3)

  println(asq) //#=> (1 + \sqrt(2)) * (1 + \sqrt{2})
  println(rhs) //#=> 2\sqrt{2} + 3
  println(asq == rhs) //#=> true

  val b1 = g(1) / aa //#=> 1 / (1 + \sqrt{2})のつもり
  val b2 = g(-1) + a //#=> \sqrt{2} - 1のつもり

  println(b1)
  println(b2)
  println(b1 == b2) //#=> true
}

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)\)を作ってみましょう。

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

class Qi(override val poly: Polynomial<Q>): PolynomialQuotientField<Qi, Q>(poly) {
  constructor(vararg coeffs: Int): this(Polynomial(coeffs.map{ Q(it) }))
  constructor(vararg coeffs: Q): this(Polynomial(coeffs.toList()))

  override val generator: (Polynomial<Q>) -> Qi = ::Qi
  override val monomialGen: (Q) -> Qi = { Qi(it) }
  override val polyGen: (Q) -> Polynomial<Q> = { Polynomial(it) }

  override val modulo: Polynomial<Q> = constructPolynomialQ(1, 0, 1)

  // ...省略
}

としておいて

fun main(args: Array<String>) {
  val i = Qi(0, 1) // これが虚数単位i
  println(i * i == Qi(-1)) //#=> true

  val z = Qi(3) + i * 2
  println(z * z == Qi(5) + i * 12) //#=> true
}

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

また、

class W /* 省略 */ {
  constructor(vararg coeffs: Int): this(Polynomial(coeffs.map{ Q(it) }))
  constructor(vararg coeffs: Q): this(Polynomial(coeffs.toList()))
  override val modulo: Polynomial<Q> = constructPolynomialQ(1, 1, 1)

  // ...省略
}

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

fun main(args: Array<String>) {
  val w3 = W(0, 1) //#=> 1の3乗根
  println(w3 * w3 * w3 == W(1)) #=> true
}

ね？

おわりに

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

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

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

では！