モーメント母関数とTaylor展開の項別微分

最近、統計学を勉強している。統計学における重要な概念の1つとしてモーメント母関数がある。モーメント母関数とは簡単な計算を施すことで次々と重要な統計量が取得できる便利関数であるが、これは指数関数 f(x) = e^xのTaylor展開と関係がある。本稿ではこれについて疑問に思ったことと、その回答について書いてみる。

なお、あらかじめ述べておくが、本稿は統計学の話と見せかけて、内容はほとんど解析学の話である。

モーメント母関数

定義

まず、モーメントの定義を以下に示す[1]。

モーメント
一般に
 \displaystyle{
\mu_r = E(X^r)
}
を, Xの (原点のまわりの) r次のモーメント moment, または積率といい,
 \displaystyle{
\mu'_r = E(X - \mu)^r
} (ただし、 \mu = E(X))
を, Xの期待値 (平均) のまわりのr次のモーメンという.

本[1]は記法が少々分かりづらいが、Xの期待値のまわりのモーメントの式は恐らく \mu'_r = E\{(X - \mu)^r\}を意図しているものと思われる。

続いてモーメント母関数の定義を以下に示す[1]。

モーメント母関数
すべての次数のモーメントを生成するモーメント母関数 moment generating function を
 \displaystyle{
M_X(t) = E(e^{tX})
}
と定義する. その計算は
 \displaystyle{
M_X(t) = \sum_x e^{tx} f(x)
} (離散型)
 \displaystyle{
M_X(t) = \int_{-\infty}^{\infty} e^{tx} f(x)dx
} (連続型)
による.

モーメント母関数からモーメントを取得する

モーメント母関数を使うと面倒な計算をすることなく任意の次数のモーメントを取得することができる。そのためにはモーメント母関数をr回微分して0を代入すれば良い。すなわち、以下の式が成立する。

 \displaystyle{
\mu_r = M^{(r)}_X(0)
}

なぜこうなるのか説明する。まず、 e^{x}のTaylor展開に x = tXを代入すると以下のようになる。

 \displaystyle{
e^{tX} = \sum_{n=0}^{\infty} \frac{(tX)^n}{n!}
}

さらに両辺の期待値を取ると以下のようになる。

 \displaystyle{
\begin{eqnarray}
M_X(t) &=& E \left(\sum_{n=0}^{\infty} \frac{(tX)^n}{n!} \right) \\
             &=& \sum_{n=0}^{\infty} E \left( \frac{(tX)^n}{n!} \right) \\
             &=& \sum_{n=0}^{\infty} \frac{t^n}{n!} E (X^n) \\
             &=& \sum_{n=0}^{\infty} \frac{\mu_n}{n!} t^n
\end{eqnarray}
}

2つ目の等号は期待値の加法性による*1。上式の両辺をr回微分してみる。

 \displaystyle{
\begin{eqnarray}
M^{(r)}_X(t) &=& \left(\sum_{n=0}^{\infty} \frac{\mu_n}{n!} t^n \right)^{(r)} \\
                      &=& \sum_{n=0}^{\infty} \left(\frac{\mu_n}{n!} t^n \right)^{(r)} \\
                      &=& \sum_{n=0}^{\infty} \frac{\mu_{n+r}}{n!} t^n
\end{eqnarray}
}

あとは t = 0を代入すれば求める式が得られる。

Taylor展開と項別微分

先程の説明の中で、さらりと項別微分を行っていたことにお気づきだろうか?よく知られているように、無限級数はいつでも気軽に項別微分出来るものではなく、常にそれが可能かどうかチェックする必要がある。

ここで私が疑問に思ったのは、Taylor展開によって得られた無限級数はいつでも項別微分可能か?ということである。以下でこれについて調べていこう。

級数

Taylor展開によって得られる無限級数は、いわゆる冪級数の形をしている。冪級数とは以下のような形をした級数である[2]。

 \displaystyle{
\sum_{n=0}^{\infty} a_n (x - \alpha)^n
}

ただし、 x - \alphaにxを代入してもこの後の議論はほとんど変わらないので、ここでは以下のような冪級数のみを考える。

 \displaystyle{
\sum_{n=0}^{\infty} a_n x^n
}

項別微分可能条件

一般の無限級数に対する項別微分可能条件を以下に示す[2]。

項別微分可能条件
 \sum a_n(x) = s(x)が収束し,  a_n(x)微分可能,  a_n'(x)が連続で,  \sum a_n'(x) = t(x)が一様に収束するならば,
 \displaystyle{
s'(x) = t(x)
}
すなわち s(x) = \sum a_n(x)が項別に微分される:
 \displaystyle{
\frac{d}{dx} \sum a_n(x) = \sum \frac{d}{dx} a_n(x)
}

Taylor展開によって得られる冪級数の場合、xが収束半径内に収まってさえいれば収束は保証される。また、各項は微分可能であり、各項の導関数も当然連続である。そのため、項別微分可能であるかどうかを知るためには、以下の2点について調べれば良い。

  • 各項の導関数の無限級数、すなわち \sum_{n=1}^{\infty} n a_n x^{n-1}の収束半径は、もとの級数 \sum_{n=0}^{\infty} a_n x^nの収束半径とどういう関係にあるか?
  •  \sum_{n=1}^{\infty} n a_n x^{n-1}は収束半径内において一様収束するか?

以下でそれぞれについて調べてみよう。

無限級数の収束半径

無限級数の収束半径は以下で与えられる[2]。

Cauchy-Hadamardの定理
級数 \sum a_n x^nの収束半径rは次の値を有する:
 \displaystyle{
\frac{1}{r} = \varlimsup_{n \to \infty} \sqrt[n]{a_n}
}

 n \to \inftyのとき \sqrt[n]{n} \to 1となるため、 \sum_{n=0}^{\infty} a_n x^n \sum_{n=1}^{\infty} n a_n x^{n-1}の収束半径は一致する。

級数の一様収束条件

級数の一様収束性を考える上では、次のAbelの定理が有効である。

Abelの定理
もしも巾級数 \sum a_n x^n x=x_0なるとき収束するならば,  |x| < |x_0|なるxのすべての値に関して絶対収束し, また領域 |x| < |x_0|に含まれる任意の閉区域において一様に収束する.

ここでちょっとした疑問が生じる。収束半径rに対して、xが収束する区間はよく |x| < rというように開区間として与えられる。一方、上の定理では閉区間での一様収束性を述べており、この定理をどのように適用すれば良いか分かりづらい。この点について少し説明してみる。

 \sum_{n=1}^{\infty} n a_n x^{n-1}の収束半径をrとする。また、 \epsilonをrより十分小さい正の数であるとする。一様収束とは、ざっくり言えばある区間において関数値があらゆるxに対して同じように収束していく様子を表す。そのため、ある1つの点において一様収束を考える意味はなく、必ず区間について考える必要がある。

一様収束を考える区間として、ここでは [-r + \epsilon,\ r - \epsilon]に着目してみよう。収束半径はrなので、 x = \frac{(r - \epsilon) + r}{2}の点において \sum_{n=1}^{\infty} n a_n x^{n-1}は収束する。よってAbelの定理により |x| < \frac{(r - \epsilon) + r}{2}に含まれる任意の閉区間において \sum_{n=1}^{\infty} n a_n x^{n-1}は一様収束する。特に、 [-r + \epsilon,\ r - \epsilon]において一様収束する。 \epsilon \to 0の極限をを考えれば、結局 \sum_{n=1}^{\infty} n a_n x^{n-1}は収束半径内において一様収束すると言える。

なお、 r = \inftyの場合は若干証明が異なるが、考え方はほとんど一緒である。

以上により、Taylor展開によって得られる冪級数は何回でも項別微分できる事が分かった。

まとめ

本稿ではモーメント母関数に端を発し、Taylor展開によって得られる無限級数の項別微分可能性について述べた。結論として、そのような級数は何回でも項別微分出来ることが分かった。

分かっている人からしてみれば実に当たり前のことかも知れないが、私にしてみればこういう疑問を抱けたこと自体を嬉しく思う。こういう初歩的な事実に対しても常に懐疑的に見る気持ちを忘れずに、これからも数学を学んでいけると良い。

参考

[1]

統計学入門 (基礎統計学?)

統計学入門 (基礎統計学?)

[2]
解析概論 改訂第3版 軽装版

解析概論 改訂第3版 軽装版

*1:無限級数に対しても加法性がそのまま成立するかどうかは厳密に考える必要があると思われるが、本[1]ではあまり細かいことは書いていなかった。

幾何平均の使いどころ

「平均」と言えば、算術平均 (=相加平均) の他に幾何平均 (=相乗平均) があるということをご存知の方は多いだろう。算術平均の方は意味が理解しやすく、使われる場面も多いと思われる。一方で、幾何平均はその意味するところが分かりづらく、一体どんな場面で使うべきものなのか、不勉強な私はこれまで知らなかった。せいぜい、高校数学で相加・相乗平均の関係を計算に使ったりする程度で、幾何平均ならではの使いどころというのは理解していなかった。

最近、統計学の本[1]を読み直して幾何平均の使いどころに気づいたので、本稿ではそれを紹介したいと思う。

定義

幾何平均の定義を[1]より引用する。

幾何平均
正数 x_1,\ x_2,\ \cdots,\ x_nの幾何平均 geometric mean  x_G
\displaystyle{
x_G = \sqrt[n]{x_1 \cdot x_2 \cdot \ \cdots \ \cdot x_n}
}
で定義され, (以下省略)

幾何平均の意味

幾何平均の定義式を少し変形してみよう。

\displaystyle{
x_G^n = x_1 \cdot x_2 \cdot \ \cdots \ \cdot x_n
}

この式の意味は、平均を計算するのに使用されたn個の数を全て掛け合わせたものは、幾何平均のn乗に等しいということである。つまり幾何平均とは、互いに掛け合わせることに意味があるようなデータに対して、平均的にはどのような数を掛け合わせることに相当するかを示す指標と言える。

例 : 前年度との売上比率

ここまでの話だけ聞くと何だか当たり前のことのような気がしてしまう訳だが、この事実を真に理解するために、1つ例を見て頂きたい。

ある会社の売上高が、2015年度から2016年度にかけて10%増加、2016年度から2017年度にかけて5%増加、2017年度から2018年度にかけて3%増加したとする。この時、2015年度から2018年度にかけて、平均で毎年どれくらい売上が伸びたと言えるだろうか?

ここで試しに算術平均を計算すると以下のようになる。

 \displaystyle{
\frac{1.1 + 1.05 + 1.03}{3} = 1.06
}

つまり、平均で毎年6%売上が伸びたと言えそうに見える。しかし、実はこれは正しくない。まず、2015年度の売上を1としたとき、2018年度の売上は以下のように計算される。

 \displaystyle{
1.1 \times 1.05 \times 1.03 = 1.18965
}

一方、毎年6%売上が伸びたとして計算すると以下のようになる。

 \displaystyle{
1.06^3 = 1.191016
}

このように、売上比率に対して算術平均を使ってしまうと、元のデータを用いた場合と計算が合わなくなってしまうのである。

この理由は、ある2つの年度の間の売上比率を計算するには、その間の各年度における前年度との売上比率を掛け合わせる必要があるからである。つまり、前年度との売上比率は掛け合わせることに意味があるデータだからである。

このようなケースこそ幾何平均の出番である。今回のデータに対して幾何平均を計算すると以下のようになる。

 \displaystyle{
\sqrt[3]{1.1 \times 1.05 \times 1.03} \simeq 1.059595
}

これを3乗すると、当然だが2015年度の売上を1としたときの2018年度の売上に一致する。すなわち、売上比率に対しては算術平均ではなく幾何平均を使うのが妥当であると言える。

まとめ

以上、幾何平均を使うべきケースについて例を交えて説明した。ポイントとしては、幾何平均は掛け合わせることに意味のあるデータに対して使用するということであった。これでもう、平均を計算する際にどちらを使うべきかで迷うことはないだろう。

参考

[1]

統計学入門 (基礎統計学?)

統計学入門 (基礎統計学?)

5次方程式の解を巡る旅 〜5次方程式の可解性判定編〜

前回の記事で3次・4次方程式のresolventについて説明した。本稿ではここまでの内容を総括し、5次方程式の可解性判定について述べる。

5次方程式の可解性判定

5次方程式のresolvent

 \mathbb{Q}上の5次多項式 f(x) = x^5 + a_3 x^3 + a_2 x^2 + a_1 x + a_0に対して、方程式 f(x)=0の可解性について考える。議論の流れに大きな影響はないので、f(x)はmonicとしている。

f(x)を良く見ると x^4の項がない。実は任意の多項式は適当な変数変換を施すことで、いつでも最高次より1つ次数の小さい項を消す事ができる[1]。そのため、ここでは最初から4次の項はその変換によって消されたものとして扱う。

まずは3次・4次方程式の場合と同じように、5次方程式にもresolventを考えるところからやってみよう。少々恣意的であるが、位数20のFrobenius群 F_{20}の作用に対して不変となる式について考えてみる。これを自力で思い付くのは難易度が高いが、幸い先人が以下の2つの式を見つけてくれている[2][3]。

 \displaystyle{
\begin{eqnarray}
P_1 &=& x_1^2 x_2 x_5 + x_1^2 x_3 x_4 + x_2^2 x_1 x_3 + x_2^2 x_4 x_5 + x_3^2 x_1 x_5 \\
&&  + x_3^2 x_2 x_4 + x_4^2 x_1 x_2 + x_4^2 x_3 x_5 + x_5^2 x_1 x_4 + x_5^2 x_2 x_3 \\
Q_1 &=& (x_1 x_2 + x_2 x_3 + x_3 x_4 + x_4 x_5 + x_5 x_1 \\
&&- x_1 x_3 - x_3 x_5 - x_5 x_2 - x_2 x_4 - x_4 x_1)^2
\end{eqnarray}
}

ここで、私自身が悩んだポイントについて補足しておく。上記2つの式は様々な文献で見かけるが、これらの間の関係についてはあまり触れられることがない。実はresolvent invariantに適当な対称式を足したり掛けたりしても、resolvent invariantが持つ対称性に変化はない。そのため、resolvent invariantは無数に存在し、 P_1,\ Q_1はどちらもその中の1つに過ぎない。実際、 4P_1 - Q_1は対称式になっているようだ[4]*1

どちらで考えても同じなので、以下では P_1を利用して議論を進める。 P_1 S_5の元を作用させると異なる6つの式が得られる。 P_1以外の式を以下に示す[2]。

 \displaystyle{
\begin{eqnarray}
P_2 &=& (1\ 2\ 3)P_1 \\
P_3 &=& (1\ 3\ 2)P_1 \\
P_4 &=& (1\ 2)P_1 \\
P_5 &=& (2\ 3)P_1 \\
P_6 &=& (1\ 3)P_1 \\
\end{eqnarray}
}

そのため、resolvent equationは以下のようになる。

 \displaystyle{
(z - P_1)(z - P_2)\ \cdots \ (z - P_6) = 0
}

以下、上記resolvent equationの左辺を f_{20}(z)とおく。 f_{20}(z)には P_1 S_5を作用させて得られる変化のパターンを全て根に持たせてあるので、 f_{20}(z)の係数は対称式となる。そのため、f(x)の係数を用いて表す事ができる。

Resolventを用いた可解性判定

ここで困ったことがある。3次・4次方程式ではresolvent equationの方が次数が小さかったため、resolvent equationを解くことで元の方程式の解が得られた。しかし、5次方程式から得られたresolvent equationは6次方程式であり、次元が上がってしまっている。こんな式を得たところで、一体どうしたら良いのだろうか?

実は、ここで以下の強力な定理が火を吹く (ただし、本稿の文脈に合わせて記号等を微修正してある) [2]。

5次方程式の可解性判定
The irreducible quintic  f(x) = x^5 +a_3 x^3 +a_2 x^2 +a_1 x + a_0 \in \mathbb{Q}[x] is solvable by radicals if and only if the polynomial  f_{20}(z) has a rational root. If this is the case, the sextic  f_{20}(z) factors into the product of a linear polynomial and an irreducible quintic.

要するに、 f_{20}(z)がただ1つの有理数根を持てば、f(x)は可解になる。これにより、resolvent equationの根を全て求めることが出来ずとも、元の多項式が可解かどうか判定できる。

Galois群とresolventの関係

しかし、この定理だけ見せられても何だか天下り的というか、どういう理屈でこんな事が成り立つのか分からない。そのため、もう少し掘り下げてみよう。

まず、f(x)が可解というのは、 \mathbb{Q}からf(x)の最小分解体への拡大に対応するGalois群が可解群である事を意味する。以下ではこのGalois群を \mathrm{Gal}(f)と書く。 \mathbb{Q}上既約な5次方程式のGalois群のうち、可解なものは共役を除いて3つしかなく、そのうち位数最大のものはFrobenius群 F_{20}であった。しかも、他の2つは共に F_{20}の部分群である。

そのため、f(x)が可解であるとは、 \mathrm{Gal}(f) \subset F_{20}を意味する。と言いたいところだが、実際には F_{20}には自身を含めて6つの共役な群が存在するので、 \mathrm{Gal}(f)はそのどれかに含まれることになる。

そうなると、 \mathrm{Gal}(f) F_{20}の共役に含まれる条件が知りたくなる。それを定理の形で述べたものが以下である[5]。

Galois群とresolventの関係
If  \mathrm{Gal}(f) is conjugate (in G) to a subgroup of  H = \mathrm{Stab}_G(F), then  \mathrm{Res}_G(F, f) has a root in  \mathbb{Z}. Furthermore, if  \mathrm{Res}_G(F, f) has a simple root in  \mathbb{Z} then  \mathrm{Gal}(f) is conjugate to a subgroup of  H = \mathrm{Stab}_G(F).

ただし、引用した論文では整数係数の多項式について論じているため、何かと \mathbb{Z}が登場していることに注意されたい。ここは \mathbb{Q}と読み替えても良いだろう。

ここで、Fはn変数の多項式であり、f(x)の根を代入することでresolvent invariantの役割を果たすものである。また、Gは対称群 S _nの部分群、 \mathrm{Res}_G(F, f)は以下の式で定義される。

 \displaystyle{
\mathrm{Res}_G(F, f) = \prod_{\sigma \in G/H} \left(z - F(x_{\sigma(1)}, \cdots  , x_{\sigma(n)}) \right)
}

 \mathrm{Res}_G(F, f) = 0という方程式はresolvent equationの一般形となっている。

この定理はGに選択の余地があるが、今は G = S_nのケースだけ考えれば十分である。簡易版の定理を以下に示す。

Galois群とresolventの関係 (簡易版)
If  \mathrm{Gal}(f) is conjugate to a subgroup of  H = \mathrm{Stab}_{S_n}(F), then  \mathrm{Res}_{S_n}(F, f) has a root in  \mathbb{Z}. Furthermore, if  \mathrm{Res}_{S_n}(F, f) has a simple root in  \mathbb{Z} then  \mathrm{Gal}(f) is conjugate to a subgroup of  H = \mathrm{Stab}_{S_n}(F).

上記定理のうち特に後半が重要で、これによってGalois群の可能性を絞り込む事ができる。すなわち、 S_nのある部分群Hに対するresolvent invariantを見つけられれば、まずresolvent equationが得られる。そして、それが有理数根を持つかどうかを調べることで、 \mathrm{Gal}(f)がH、もしくはその共役な部分群に含まれるかどうかが分かるのである。最初の定理が述べていたのはまさにこのGalois群の絞り込みの一例なのである。

可解性判定の例

実際に可解性判定をするためには f_{20}(z)の係数を求める必要があるが、幸い[2]に具体的な式が記載されている。いくつか計算してみよう。

例1:  f(x) = x^5 + 4x^2 - 2

このとき、resolvent equationは以下のようになる。

 \displaystyle{
f_{20}(z) = z^6 + 400 z^4 - 512 z^3 + 40000 z^2 + 68784 z + 65536
}

これは \mathbb{Q}上既約なので、f(x)は可解ではない。

例2:  f(x) = x^5 - 5x^3 + 5x + 3

この例は[6]を参考にさせて頂いた。このとき、resolvent equationは以下のようになる。

 \displaystyle{
f_{20}(z) = z^6 + 40 z^5 + 250 z^4 - 10625  z^3 - 146875 z^2 + 493750 z + 12875000
}

これは以下のように因数分解できる。

 \displaystyle{
f_{20}(z) = (z - 10)(z^5 + 50 z^4 + 750  z^3 - 3125 z^2 - 178125 z + 1287500)
}

有理数根をただ1つ持つので、f(x)は可解である。

おまけ

交代群と判別式

ここまでの議論で5次方程式の可解性を判定することができた。しかし、これだけではf(x)のGalois群が F_{20}に含まれるかどうかが分かるだけである。もっと問題を広げて、f(x)のGalois群を決定したいと思ったらどうすれば良いだろうか?

今の時点で分かっていることを少し言い換えると、Galois群が \{S_{5},\ A_{5}\}、または \{F_{20},\ D_{5},\ C_{5}\}のどちらに属するかを判定できたと言える。厳密にはGalois群はこれらと共役な部分群である可能性もあるが、共役というのは根への添字の付け方による変化に過ぎないので、ここでは共役は同一視する。

それぞれをさらに分解するために、 D_{5},\ C_{5} \subset A_{5}という事実に着目する。つまり、Galois群が A_{5}に含まれるかどうかが判定できれば、さらに可能性を絞り込めるのである。

そのためにはやはり上で紹介した定理を使うわけだが、定理を適用するには A_{5}の作用で不変となるresolvent invariantを見つける必要がある。実は判別式と呼ばれる非常に有名な式がこれに関係している。判別式の定義を以下に示す[7]。

差積と判別式
(1)  \delta(x) = \prod_{i < j} (x_i - x_j) x = (x_1, \cdots , x_n)の差積という.
(2)  \Delta(x) = \delta(x)^2 x = (x_1, \cdots , x_n)の判別式という.

ただし、これはmonicの場合の式のようだ。最高次の係数が1でない場合の式はWikipedia[8]などを参照されたい。

ここで、差積 \delta A_{5}のresolvent invariantになっている。 \delta S_{5}の元を作用させると \deltaまたは -\deltaのどちらかになるため、resolvent equationは以下のようになる。

 \displaystyle{
\begin{eqnarray}
(z - \delta)(z + \delta) &=& 0 \\
z^2 - \Delta &=& 0
\end{eqnarray}
}

上で述べた定理によると、これが有理数解を持てばGalois群が A_{5}に含まれることになる。言い換えると、 \sqrt{\Delta} \in \mathbb{Q}であればGalois群が A_{5}に含まれる。判別式自体は計算する手法が知られているため、これでGalois群が A_{5}に含まれるかどうかが分かる。あとは同様にして D_5,\ C_5を区別してやれば良い。

このように、上述の定理を繰り返し用いることで、多項式のGalois群を決定することができる。ただし、そのためには着目する群のresolvent invariantを求める必要があり、次元が大きくなるとそれが困難になると思われる。

超越的な解法について

ここまで、5次方程式の解を四則演算とべき根のみを使って表せる条件を考えてきた。しかし、これはかなり限定的な状況であるという点はハッキリと意識しておく必要があるだろう。実際、超越的な操作を許すことで、次元がどれだけ大きな方程式でも解を求められる事が知られている[3]。

まとめ

以上、5次方程式の可解性判定法について述べた。その中で、resolventとGalois群の間の関係を明らかにした。今回の調査を通して、Galois群がずっと身近に感じられるようになったのは大きな収穫であった。

本当は実際に5次方程式の解を求めるところまでやりたかったし、超越的な解法にも踏み込んでみたかった。しかし、残念ながら人生の時間は有限である。他の勉強との優先度を考え、5次方程式の解を巡る旅は一旦終えることにする。

もし今後この話題を再び取り上げる機会があれば、その時はまた良い旅ができることを願っている。

*1:これをWolframAlphaで愚直に計算してみたところ、めちゃくちゃ時間がかかった挙げ句にエラーになってしまった。[4]の著者がどうやって P_1,\ Q_1の間の関係を見出だしたのかが気になる。

5次方程式の解を巡る旅 〜3次・4次方程式のresolvent編〜

前回の記事 \mathbb{Q}上の5次既約多項式のGalois群について調べた。本稿では実際に方程式を解くために必要となるresolventについて説明する。

本当に知りたいのは5次方程式についてだが、前準備としてより低次元の方程式が解ける仕組みを理解しておくことは有用なので、本稿では話のスコープを3次・4次方程式に絞ることにする。

Resolventを用いた方程式の解法

次元の高い方程式を扱うための方法の1つとして、問題をより次元の低い方程式に帰着させることが挙げられる。例えば、nを3以上の自然数として、あるn次方程式を解きたいとする。もし自然数m  (m < n) に対してm次方程式の解から元の方程式の解が導き出せるのであれば、解くべき問題をずっと簡単にすることができる。

Resolventは3次・4次方程式に対して、そのような次元削減の方法を与えてくれる。

3次方程式の場合

Resolvent invariant

 \mathbb{Q}上の3次多項式 f(x) = x^3 + a_2 x^2 + a_1 x + a_0に対して、方程式 f(x)=0を解くことを考える。議論の流れに大きな影響はないので、f(x)はmonicとしている。

f(x)の根を x_1,\ x_2,\ x_3としたとき、一部の根の置換に対して不変となるような x_1,\ x_2,\ x_3多項式を考える。「一部の根の置換」として3次交代群 A_3を考えた場合、その作用に対して不変となる多項式を得るためには以下の式を利用する。

 \displaystyle{
U = x_1 + \omega x_2 + \omega^2 x_3
}

ここで、 \omegaは1の原始3乗根である。すると、 U^3 A_3の作用に対して不変となる。

このように、対称群の部分群に対して不変となるような式のことをresolvent invariantと呼ぶ[1]。しかし、実のところresolventという用語は使う人によって指すものが異なっている場合があり、resolvent invariantのことを単にresolventと呼ぶこともあるようである。

Resolvent equation

話を続けよう。さらに以下の式を考える。

 \displaystyle{
V = x_1 + \omega^2 x_2 + \omega x_3
}

 U^3 A_3の作用に対しては不変だが、奇置換を作用させると V^3に変化する。実は V^3も同様の性質を持っており、 A_3の作用に対しては不変、奇置換の作用に対しては U^3に変化する。

ここで、 U^3,\ V^3を解に持つ方程式を考えてみる。

 \displaystyle{
(t - U^3)(t - V^3) = 0
}

左辺をg(x)とおく。ここまでの議論により、g(x)の係数に S_3の元を作用させると、以下のどちらかになる。

 \displaystyle{
\begin{eqnarray}
(t - U^3)(t - V^3) \\
(t - V^3)(t - U^3)
\end{eqnarray}
}

結果はどちらも同じになっている。つまり、g(x)は S_3の作用に対して不変になる。そのため、g(x)の係数は x_1,\ x_2,\ x_3の対称式となる。対称式は基本対称式で表すことができるわけだが、解と係数の関係よりf(x)の係数が x_1,\ x_2,\ x_3の基本対称式になることを考えると、これはg(x)の係数をf(x)の係数で表せることを意味する。 ただし、計算は面倒なので割愛する。

このようして得られたg(x)を解けば U^3,\ V^3が分かる。あとはここから x_1,\ x_2,\ x_3を求めたいわけだが、これは以下のようして得られる。

 \displaystyle{
\begin{eqnarray}
x_1 &=& \frac{U + V - a_2}{3} \\
x_2 &=& \frac{\omega^2 U + \omega V - a_2}{3} \\
x_3 &=& \frac{\omega U + \omega^2 V - a_2}{3}
\end{eqnarray}
}

ただし、 a_2 = -(x_1 + x_2 + x_3)に注意されたい。

このように、3次方程式を解くにはまず g(x)=0という2次方程式を解き、その解を元に f(x)=0の解を求める。そして、元の方程式を解くために利用される方程式 g(x)=0のことをresolventと呼ぶ[1]。これに関しても用語の揺れがあって、resolvent equation、または日本語だと分解方程式とか分解式などと呼ばれることもある。

Resolvent invariantの条件

このようなことが成立するのは、こうなるようにresolvent invariantをうまく選んでいるからである。すなわち、resolvent invariantは以下の条件を満たすように選ばれていたのである。

  • 対称群の作用に対してn個未満のパターンにしか変化しない。
  • そこから元の方程式の解を導き出せる。

3次方程式についてはこのような都合の良い式が存在したので、解くことができたのである。

4次方程式の場合

4次方程式も基本的には同じ流れで解ける。 \mathbb{Q}上の4次多項式 f(x) = x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0に対して、方程式 f(x)=0を解くことを考える。やはりf(x)はmonicとしておく。

f(x)の根を x_1,\ x_2,\ x_3,\ x_4としたとき、resolvent invariantとして以下の式を考えてみる。

 \displaystyle{
\tau_1 = x_1 x_2 + x_3 x_4
}

 \tau_1は二面体群 D_4 = \langle (1\ 2),\ (1\ 3\ 2\ 4) \rangleの作用に対しては不変であるが、それ以外の置換を作用させると以下のどちらかの式に変化する。

 \displaystyle{
\begin{eqnarray}
\tau_2 &=& x_1 x_3 + x_2 x_4 \\ 
\tau_3 &=& x_1 x_4 + x_2 x_3
\end{eqnarray}
}

ここで1つ困ったことがある。3次方程式の場合は U^3,\ V^3がどちらも A_3の作用に対して不変となっていた。しかし、ここで得られた \tau_2,\ \tau_3 D_4に対して不変ではない。この違いをどう捉えたら良いだろうか?

実は、 \tau_2,\ \tau_3はそれぞれ D_4と共役な部分群 D_4' =  \langle(1\ 3),\ (1\ 2\ 3\ 4)  \rangle D_4'' =  \langle(1\ 4),\ (1\ 3\ 4\ 2)  \rangleの作用に対して不変なのである。3次方程式の場合は A_3がたまたま S_3正規部分群だったため、共役な部分群が A_3だけだったのである。

あとは \tau_2,\ \tau_3にそれぞれ D_4',\ D_4''以外の置換を作用させたときにどうなるかだが、 \tau_2 \tau_1,\ \tau_3のどちらかに、 \tau_3 \tau_1,\ \tau_2のどちらかに変化し、それ以外の変化のパターンはない。結局、 \tau_1,\ \tau_2,\ \tau_3 S_4の作用に対して変化しないか、互いに遷移し合うかのどちらかになる。

このとき、以下の方程式がresolvent equationとなる。

 \displaystyle{
(t - \tau_1)(t - \tau_2)(t - \tau_3) = 0
}

左辺をg(x)とおく。先ほどの議論により、g(x)の係数に S_4の元を作用させると根が互いに入れ替わるだけで、g(x)自体は不変となる。そのため、g(x)の係数は x_1,\ x_2,\ x_3,\ x_4の対称式となり、解と係数の関係によりg(x)の係数をf(x)の係数で表すことができる。

このようして得られたg(x)を解けば \tau_1,\ \tau_2,\ \tau_3が分かる。最後に、これらを用いて x_1,\ x_2,\ x_3,\ x_4を求める必要があるが、これは可能である。具体的な式は複雑なので割愛するが、気になる方は[2]などを参照されたい。

これで4次方程式も解くことが出来た。

おまけ:Lagrange resolventとは

本筋とはあまり関係ないが、最後にLagrange resolventの話をしておこうと思う。私は本件の調査を始めるまで、高次方程式を解くにはLagrange resolventというすごいやつを使えば良いのだと思っていたが、実はそうではない。ここで今の私の理解を整理しておく。

あるn次多項式f(x)の根を x_1,\ x_2,\ \cdots ,\ x_nとすると、Lagrange resolventとは以下のような式のことを言う。

 \displaystyle{
\sum_{i=1}^{n} \zeta_n^{i-1} x_i
}

ただし、 \zeta_nは1の原始n乗根である。

Lagrange resolventには面白い性質がある。すなわち、 \zeta_nで割ると根に巡回置換 (1\ 2\cdots n)を作用すさせるのと同じ効果が得られるのである。すると、 \frac{1}{\zeta_n}の作用により以下の異なるn個の式が得られる。

 \displaystyle{
\begin{eqnarray}
\sum_{i=1}^{n} \zeta_n^{i-1} x_i &=& x_1 + \zeta_n x_2 + \zeta_n^2 x_3 + \cdots + \zeta_n^{n-1} x_n \\
\frac{1}{\zeta_n} \sum_{i=1}^{n} \zeta_n^{i-1} x_i &=& x_2 + \zeta_n x_3 + \zeta_n^2 x_4 + \cdots + \zeta_n^{n-1} x_1 \\
\frac{1}{\zeta_n^2} \sum_{i=1}^{n} \zeta_n^{i-1} x_i &=& x_3 + \zeta_n x_4 + \zeta_n^2 x_5 + \cdots + \zeta_n^{n-1} x_2 \\
\vdots \\
\frac{1}{\zeta_n^{n-1}} \sum_{i=1}^{n} \zeta_n^{i-1} x_i &=& x_n + \zeta_n x_1 + \zeta_n^2 x_2 + \cdots + \zeta_n^{n-1} x_{n-1}
\end{eqnarray}
}

ここで、これらを全てn乗した式を考えると、全て一致することが分かる。つまり、n次多項式のLagrange resolventは、n乗することで巡回置換 (1\ 2\cdots n)に対して不変となるのである。

それ以外の置換に対する変化を考えると、結局Lagrange resolventのn乗は (n-1)!通りに変化することが分かる。

実は3次方程式を解く際に登場したU, VはLagrange resolventになっている。そのため、これらを3乗すると (3-1)!=2通りの式に変化したと言うわけである。

一方、4次方程式ではLagrange resolventを利用していない。それは、変化のパターンが (4-1)!=6通りとなってしまい、4次方程式を解くために6次方程式を解かなければならなくなるからである。

そんなわけで、Lagrange resolventは面白いが、方程式を解くのに使える万能薬ではないのである。

まとめ

以上、resolventとは何かということについて説明した。書き始めてみると毎度長くなってしまい、なかなか核心に迫れないでいるが、次回こそ5次方程式の可解性の議論に入りたいと思う。

参考

[1] Resolvent (Galois theory) - Wikipedia
[2]

代数学2 環と体とガロア理論

代数学2 環と体とガロア理論

5次方程式の解を巡る旅 〜既約多項式のGalois群編〜

前回の記事 \mathbb{Q}上の多項式の既約性を確実に判定できることが分かった。本稿からいよいよ本題である可解な5次方程式の話に入っていく。特に、本稿では既約な5次多項式のGalois群がどういう性質を持つのかについて記載しようと思う。

最小分解体とGalois群

f(x)を \mathbb{Q}上の既約多項式とする。 \mathbb{Q}上既約なので、f(x)は \mathbb{Q}上ではこれ以上因数分解できない。しかし、体を適切に拡大すれば因数分解できるようになる。例えば、思い切って \mathbb{C}まで拡大すれば因数分解可能となる。

しかし、多くの場合そこまで体を拡大せずとも、もっと小さい体で因数分解できるようになる。実際、因数分解ができるようになる最小の拡大体というものが存在し、これをf(x)の最小分解体という。以下、これをLと表すことにする。

Lを具体的に得るのは簡単で、単にf(x)の根を全て \mathbb{Q}に添加すればよい。すなわち、f(x)の根を  \alpha_1, \alpha_2, \cdots , \alpha_nとすれば、 L = \mathbb{Q}(\alpha_1, \alpha_2, \cdots , \alpha_n)となる。

 \mathbb{Q}からLへの拡大はGalois拡大である。これは自明ではなく証明が必要と思われるが、ここでは割愛する。Galois拡大とその中間体には、Galois群とその部分群が1対1で対応し、これをGalois対応と呼ぶ。Galois群とはLの \mathbb{Q}自己同型群のことであり、これはf(x)の根の置換と捉えることができる。そのため、Galois群は対称群やその部分群と同型になる[1]。

一般の5次多項式の場合では、最小分解体に対応するGaloisが5次対称群 S_5となる。これが可解群ではないために、根を代数的に表示することができないのであった。

推移的なGalois群

既約多項式のGalois群は1つ特徴的な性質を持っている。それは、作用が推移的になるということである。推移的な作用の定義を[2]より引用する。

推移的な作用
群Gが集合Xに作用するとする.
(中略)
 x \in Xがあり,  Gx = Xとなるとき, この作用は推移的であるという.

作用が推移的な群のことを可移群とかtransitive groupなどと呼ぶようである。

先ほど述べたように5次方程式のGalois群は5次対称群、もしくはその部分群と同型になるわけだが、そのうち作用が推移的なものはどれくらいあるのだろうか?実は、これは共役を除いて以下の5つしか存在しないことが知られている[3][4]。

名称 記号 位数 共役な部分群の数
対称群  S_5 120 1
交代群  A_5 60 1
Frobenius群  F_{20} 20 6
二面体群  D_{5} 10 6
巡回群  C_5 5 6

上に示した5つの群の性質を見てみよう。まず、以下の2つの正規列を作ることができる。

 \displaystyle{
\begin{eqnarray}
&& 1 \lhd A_5 \lhd S_5 \\
&& 1 \lhd C_{5} \lhd D_5 \lhd F_{20}
\end{eqnarray}
}

 S_5,\ A_5が可解群でないことは有名であるが、実は F_{20},\ D_{5},\ C_5は可解群となる。これより、5次の既約多項式f(x)について、 f(x)=0という方程式が代数的に解けるための必要十分条件は、Galois群が F_{20}に含まれることだと言える。これについては次回以降詳しく述べることにする。

Frobenius群とは

上で挙げた5つの群のうち、Frobenius群 F_{20}だけ馴染みがないという方は多いのではないだろうか?何を隠そう私自身も本件の調査をするまで知らなかった。そこで、本格的な可解性の議論に入る前に、Frobenius群の性質について調べてみたいと思う。

定義

まず、定義を[5]より引用する。

Frobenius群
Let G be a finite group acting transitively on a set X. We call G a Frobenius group if only the identity element fixes more than one point. In other words, if x,y are distinct elements, and if gx=x and gy=y then g=1. We assume that X has more than one element.

要するに、単位元以外の元はその作用によって高々1つの点しか固定しないということである。

重要な部分群

高々1つの点を固定するということは、点を1つ固定する元と1つも固定しない元があることを意味する。作用によって1つも点を固定しない元と単位元を合わせたものはFrobenius群の正規部分群となっており、これをFrobenius kernelと呼ぶ。また、作用によってある点 x_0 \in Xを固定する元と単位元を合わせたものは部分群となっており、これをFrobenius complementと呼ぶ。

一般にFrobenius群Gには常にFrobenius kernel KとFrobenius complement Hが存在し、 G = HKとなる。上で述べた事実と合わせると、結局GはKとHの半直積になる。すなわち、 G = K \rtimes Hである。

G, K, Hの成す短完全列

GとKは以下のような短完全列を成す。

 \displaystyle{
\{1\} \to K \xrightarrow{\nu} G \xrightarrow{\pi} G/K \to \{1\}
}

ここで、 \nuは入射、 \piは自然な全射を表す。

Frobenius群Gに対してKとG/Kは常に巡回群になることが知られている。このような性質を持つ群をメタ巡回群と呼ぶ[6]。すなわち、Frobenius群はメタ巡回群であると言える。

実はさらに G/K \cong Hとなる。G/KからHへの同型を \phiとすると、結局以下の短完全列が得られる。

 \displaystyle{
\{1\} \to K \xrightarrow{\nu} G \xrightarrow{\phi \circ \pi} H \to \{1\}
}

 F_{20}の全体像

Frobenius群の一般論はこれくらいにして、以下に F_{20}の構造を示す。

f:id:peng225:20180121162728p:plain

 F_{20}は2つの置換 \sigma = (1, 2, 3, 4, 5),\ \tau = (2, 3, 5, 4)によって生成されるので、全ての元を \sigma,\ \tauの積として表現している。エッジは生成元を左から掛ける操作を表しているが、一部省略している。各ノード下段の括弧で囲われた数字は、(1, 2, 3, 4, 5)という数字の列に対してその元を左作用させた結果を表している。その作用によって固定される点を赤で示している。

また、Frobenius kernelの元はノードに色を付けてある。具体的には K = \{1, \sigma, \sigma^2, \sigma^3, \sigma^4\}であり、これは正規部分群かつ巡回群になっている。なお、念のため明示的に述べておくが K = C_5となっている。

 F_{20}のFrobenius complementを得るために、例えば1を固定する元の集合を考えてみる。これは H = \{1, \tau, \tau^2, \tau^3 \}であり、確かに部分群かつ巡回群になっている。

まとめ

以上、既約多項式のGalois群の性質について述べ、続いてFrobenius群の紹介をした。後半はほとんど余談であったが、このようにある群の持つ性質をあれこれ調べてみるのは結構面白いし、Frobenius群を身近に感じるよい機会であったと思う。

次回はいよいよ可解な5次方程式の核心に迫っていこうと思う。

参考

[1]

代数学2 環と体とガロア理論

代数学2 環と体とガロア理論

[2]
代数学1 群論入門 (代数学シリーズ)

代数学1 群論入門 (代数学シリーズ)

[3] http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0848-01.pdf
[4] http://www.isc.meiji.ac.jp/~kurano/soturon/ronbun/08kurano.pdf
[5] Frobenius Groups
[6] Metacyclic group - Wikipedia

5次方程式の解を巡る旅 〜多項式の既約性判定編〜

Galois理論活用の難しさ

一般の5次方程式に代数的な解の公式が存在しないというのは有名な事実である。これはGalois理論に深く関連する話題であるが、これ自体はGaloisによって証明されたものではない[1]。Galois理論の面白さは、代数方程式が解けるための条件を与えてくれる点にある。すなわち、Kを体とし、f(x)をK上の多項式とする。f(x)の最小分解体をLとすれば、 f(x)=0という方程式が代数的に解けるための必要十分条件 \mathrm{Gal}(L/K)が可解群になることである。この事がGalois理論により導かれるのである[2]。

Galois理論はこのように興味深く重要な理論なのであるが、具体的な多項式を目の前にしてその可解性を論じようとすると、たちどころに手が止まってしまう。すなわち、理論としてGalois群と方程式の可解性の間に深い関係があることは分かったものの、それを具体的な問題にどう活用したら良いのかが自明でないのである。

そこで、本稿では考察の対象を \mathbb{Q}上5次の代数方程式に絞ってこの問題にアプローチしてみることにする。対象をこのように絞る理由は、あまり風呂敷を広げすぎても収集がつかなくなるのと、有理数体は素体であり、最も基本的かつ重要な体の1つと考えられるためである。

恐らく話が長くなるので、記事を何回かに分けることにする。今時点で頭に思い描いている全体のストーリーはあるが、深く考えていく中で書きたいことが変わる可能性があるので、目次は敢えて書かない。

Galois理論と多項式の既約性

ある具体的な多項式 f(x) \in \mathbb{Q}[x]の可解性について考えるとき、多くの文献では \mathbb{Q}上既約な多項式を扱うことが多いように思う。その理由は、可約多項式であれば因数分解された次元の低い多項式の可解性をそれぞれ考えればよいためだと思われる。

これは確かに一理あるのだが、ちょっと待って欲しい。実際にある具体的な多項式を目の前にして、それが既約であるかどうかというのは簡単に判定できるものなのだろうか?代数学を勉強したことがある人であれば、すぐに「Eisensteinの既約判定法を使えばよいのでは?」と思うことだろう。これは確かに一つの手である。しかし、Eisensteinの既約判定法に述べられている条件は、多項式が既約であるための十分条件であって必要十分条件ではないのである。つまり、本当は既約多項式なのに、Eisensteinの既約判定法ではそれが判定できないものが存在する。

これは困った。なぜなら、多項式の既約性とGalois群の構造の間には密接な関係があり、既約性が正確に判定できないとGalois群の決定が難しくなるからである。

既約性判定アルゴリズム

これについていろいろと調べてみたところ、 \mathbb{Q}上の多項式であれば既約性を判定するアルゴリズムが存在することが分かった。そもそもsageにis_irreducible関数が実装されているのだから、当然と言えば当然である[3]。

しかし、これがなかなかに難解なのである。その全容を説明することは今の私にはできないし、また紙面の都合もある。そのため、本稿ではアルゴリズムの概観を紹介し、多項式の既約性を決定的に判定する方法が存在するのだという点について、可能な限り納得感を得られるように努めてみる。

前処理

この後に述べる既約性判定アルゴリズムでは、入力として \mathbb{Z}上のmonicな多項式を与える必要がある。そのため、 f(x) \in \mathbb{Q}[x]に対して適切な前処理を施しておく必要がある。これについて f(x) = \frac{3}{4}x^2 + \frac{3}{2}x - \frac{6}{5}を例に説明する。

やることは3つある。1つ目は分母の最小公倍数を括り出すことである。先ほどの例の場合、 f(x) = \frac{1}{20}(15x^2 + 30x - 24)となる。2つ目は分子の最大公約数を括り出すことである。先ほどの例の場合、 f(x) = \frac{3}{20}(5x^2 + 10x - 8)となる。

ここまでの操作で f(x) = C g(x)\ (C \in \mathbb{Q},\ g(x) \in \mathbb{Z}[x])という形式に変換できた。あとはg(x)をmonicな多項式に変換できれば良い。そのためには、 g(x) = \sum_{i=0}^{n} a_i x^i\ (a_n \neq 0)に対して h(x) = a_n^{n-1} g\left(\frac{x}{a_n}\right)とすれば良い。先ほどの例の場合、 h(x) = 5\left(5\left(\frac{x}{5}\right)^2 + 10\frac{x}{5} - 8\right) = x^2 + 10x - 40となる。

このようにして得られたh(x)に対して後述のアルゴリズム適用すると、 \mathbb{Z}上既約かどうか判定できる。 \mathbb{Z}上既約であればGaussの補題により \mathbb{Q}上既約となる[4]。さらに、f(x)からh(x)を得た操作では既約性は不変であるため、h(x)が \mathbb{Q}上既約であればf(x)も \mathbb{Q}上既約となる。

アルゴリズムの流れ

 f(x) \in \mathbb{Z}[x]をmonicな多項式とする。f(x)の \mathbb{Z}上での既約性を判定するアルゴリズムの流れは以下のようになる[5][6][7]。

  1. f(x)がsquare freeであるかどうかを調べる。もしsquare freeでなければf(x)は可約なので処理を終える。
  2. pを素数とする。f(x)の各係数をmod pで写して得られる多項式 F_p上でもsquare freeになるようなpを見つける。
  3. f(x)を F_p上で因数分解する。つまり、 f(x) \equiv f_{1, 1}(x)f_{1, 2}(x) \cdots f_{1, m}(x) \pmod{p}を求める。もしf(x)が F_p上既約ならば \mathbb{Q}上既約なので処理を終える。
  4.  f_i(x)\ (i=1, 2, \cdots , m)にHensel liftingを繰り返し適用し、 2B_{lm} < p^a\ (a \in \mathbb{N})を満たすような p^aを法とした時の分解を求める。すなわち、 f(x) \equiv f_{a, 1}(x)f_{a, 2}(x) \cdots f_{a, m}(x) \pmod{p^a}を求める。ただし、 B_{lm}はLandau-Mignotte boundと呼ばれる値で、 B_{lm}=2^{\mathrm{deg}(f)}\|f\|_2である。 \|f\|_2はf(x)の係数の2乗和の平方根を表す。
  5.  f_{a, i}(x)\ (i=1, 2, \cdots , m)からいくつかを選んで掛け合わせる。そうして得られた関数の各係数を \bmod p^aで写す。このとき、もし値が p^a/2より大きければ p^aを引く。これが \mathbb{Z}[x]でf(x)を割り切ればf(x)は可約である。もし (全部選ぶというパターンは除いて) 全ての f_{a, i}(x)の組み合わせについてf(x)を割り切ることがなければf(x)は既約である。

ただし、これは多項式因数分解するためのアルゴリズムであるBerlekamp-Zassenhausアルゴリズムを、私が既約性判定用にアレンジしたものであるのでご注意願いたい。

以下でそれぞれのステップのポイントについて説明する。

Square free判定

f(x)がsquare freeであるとは、 f(x) = \{f_1(x)\}^{a_1}\{f_2(x)\}^{a_2} \cdots \{f_l(x)\}^{a_l}と既約多項式の積に分解したときに、 a_1 = a_2 = \cdots = a_l= 1となることである。 \mathbb{Q}上の多項式がsquare freeかどうかを判定するのは簡単である。すなわち、 \mathrm{GCD}(f(x), f'(x))が定数であればsquare freeである。

1つだけ例を上げよう。 f(x) = x^3 - x^2 - 5x - 3がsquare freeかどうかを判定してみる。GCDを求めるにはEuclidの互除法を使えば良い。 f'(x) = 3x^2 - 2x - 5なので、f(x)をf'(x)で割ると以下のようになる。

 \displaystyle{
x^3 - x^2 - 5x - 3 = (3x^2 - 2x - 5)\left(\frac{1}{3}x - \frac{1}{9} \right) - \frac{32}{9}(x + 1)
}

さらに 3x^2 - 2x - 5 x + 1で割ると以下のようになる。

 \displaystyle{
3x^2 - 2x - 5 = (x + 1)(3x + 5)
}

 \mathbb{Q}上の多項式における互除法では定数倍に意味はないので、 x + 1による割り算を行ったことに注意されたい[8]。以上により、 \mathrm{GCD}(f(x), f'(x)) = x + 1である。これは定数ではないため、f(x)はsquare freeではないことが分かった。実際、 f(x) = (x+1)^2(x-3)である。

なお、GCDの計算にさらっとEuclidの互除法を使ったが、これが可能なのは任意の体上の多項式環がEuclid整域となるからだという点を申し添えておく[9]。

既約性判定アルゴリズムでは F_p上でもsquare free判定をする必要があるが、これはちょっと工夫が要るようである。詳しくは[10]を参照されたい。

pの見つけ方

一般にf(x)がsquare freeであっても、それがmod pの世界でもsquare freeとは限らない。例えば、 f(x) = x^2 + 2x + 6はEisensteinの判定法により既約なので、square freeである。しかし、 f(x) \equiv x^2 + 2x + 1 \equiv (x+1)^2 \pmod{5}となり、これはsquare freeではない。

既約性判定アルゴリズムでは、f(x)がmod pの世界でもsquare freeになっていなければならないので、そのようなpを何とかして見つける必要がある。実は、これはそんなに悩む必要は無くて、有限個のpを除けばmod pの世界でもsquare freeとなるようである。証明はいまいち理解出来ていないが、[6]の命題6.36にヒントがある。

 F_pでの因数分解

これについては検索すると山のように論文なりブログなりが出てくる。特に[10]に分かりやすくまとまっているようなので、興味のある方はそちらを参照されたい。

 \mathbb{Q}上の既約性と F_p上の既約性の関係

一般に F_p上既約であれば \mathbb{Q}上既約となるが、逆は成り立たない。証明は[11]などを参照されたい。

Hensel lifting

Hensel liftingとは、Henselの補題を用いて \bmod p^kにおける多項式の根から \bmod p^{k+1}における根を帰納的に導出していく手続きである[12]。と、Wikipediaには記載されているが、実は多項式因数分解に関係する別バージョンが存在する[5][13][14]。Henselの補題 (別バージョン) の内容を[5]より引用する。

Henselの補題 (別バージョン)
Fを整係数一変数多項式、pは p \nmid lc(F)となる素数とし、 G_1 H_1はpを法とする有限体上の互いに素な多項式とするとき、

 \displaystyle{
F(x) \equiv G_1(x)H_1(x) \pmod{p}
}

であるならば、任意の正整数kに対して、

 \displaystyle{
\begin{eqnarray}
&& F(x) \equiv G_k(x)H_k(x) \pmod{p^k} \\
&& G_k \equiv G_1,\  H_k \equiv H_1 \pmod{p}
\end{eqnarray}
}

を満たす G_k H_kが存在する。

ここで、(定義が書かれていないので推測だが) lc(F)というのは多項式Fのleading coefficientを意味するのだと思われる。Leading coefficientというのは、要するに最高次の係数のことである。これがpで割りきれてしまうとmod pで写したときに次元が落ちてしまうので、そのようなケースを除外しているのである。もっとも、今考えているケースでは多項式はmonicであり、常に lc(F)=1となるのであまり気にする必要はない。

別バージョンを利用することで、Hensel liftingもそれに沿った形で行うことができる。具体的な G_k, H_kの求め方は[5]の証明や[15]が参考になる。この別バージョンのHensel liftingを無限に適用することで、 F_pにおける多項式因数分解をp進整数環 \mathbb{Z}_pにまで持ち上げる事ができる。

p進整数の近似

最終ステップでは本来 \mathbb{Z}_p上でのf(x)の分解が必要なのだが、実際のコンピュータで計算する際にはHensel liftingを無限に行うことはできないし、p進整数を誤差なく扱うことも困難である。すなわち、実際に扱うことができるのはp進整数の近似値だけである。

しかし、実はある程度の精度で近似値が得られれば、そこから多項式因数分解を厳密に行える事が知られている。この精度はLandau-Mignotte boundと呼ばれる値により規定されるようである。

組み合わせ計算複雑性

最終ステップでは f_{a, i}(x)\ (i=1, 2, \cdots , m)の組み合わせを全て計算して係数を調べる必要があるが、これは時間計算量が O(2^m)の処理であり、一般には極めて重いアルゴリズムである。しかし、これを多項式時間で行うことができるアルゴリズムも存在するようである[7]。私には難しくてとても理解出来なかったが、興味のある方はぜひチャレンジしてみて欲しい。

既約性判定の例

せっかくなので1つ例を見てみよう。ここでは以下の多項式 \mathbb{Z}上での既約性を判定してみる。

 \displaystyle{
f(x) = x^5 + 2x^4 - 7x^3 + 18x^2 + 2x - 4
}

以下でアルゴリズムのステップを順に実行してみよう。

Step 1

計算は省略するが、 \mathrm{GCD}(f(x), f'(x))が定数であることが簡単に確かめられる。よってf(x)はsquare freeである

Step 2

 p=5とすると、 f(x) \equiv x^5 + 2x^4 + 3x^3 + 3x^2 + 2x + 1 \pmod{5}となる。詳細は省くが、f(x)は F_5上でもsqure freeとなる。

Step 3

f(x)を F_5上で因数分解すると以下のようになる。

 \displaystyle{
f(x) \equiv (x+1)(x+2)(x+3)(x^2+x+1) \pmod{5}
}

Step 4

f(x)のLandau-Mignotte boundを計算すると以下のようになる。

 \displaystyle{
\begin{eqnarray}
B_{lm} &=& 2^5 \cdot \sqrt{1^2 + 2^2 + (-7)^2 + 18^2 + 2^2 + (-4)^2} \\
          &=& 32 \sqrt{398}
\end{eqnarray}
}

よってHensel liftingを行うべき回数は以下のようになる。

 \displaystyle{
\begin{eqnarray}
2 B_{lm} &<& 5^a \\
64 \sqrt{398} &<& 5^a \\
4 &<& a
\end{eqnarray}
}

よって \bmod 5^5の世界までHensel liftingで持ち上げれば十分である。詳細は割愛するが、Hensel liftingの結果は以下のようになる。

 \displaystyle{
\begin{eqnarray}
x+1 &\equiv& x+1361 \pmod{5} \\
x+2 &\equiv& x+1162 \pmod{5} \\
x+3 &\equiv& x+1768 \pmod{5} \\
x^2+x+1 &\equiv& x^2+1961x+2571 \pmod{5} \\
f(x) &\equiv& (x+1361)(x+1162)(x+1768)(x^2+1961x+2571) \pmod{5^5}
\end{eqnarray}
}

余談だが、Hensel liftingの計算はPARI/GPのAndroidアプリ版であるPariDroidを用いて行った[16]。スマホでこんな高度な計算ができるとは便利な世の中になったものだ。

Step 5

例えば以下の組み合わせについて考える。

 \displaystyle{
(x+1361)(x+1768) \equiv x^2+4x+3123 \pmod{5^5}
}

 \frac{5^5}{2}<3123であるため、 5^5 = 3125を引いて x^2+4x - 2とする。実はこれはf(x)を割り切るため、f(x)は可約である。

確認のために残りの因子についても計算してみる。

 \displaystyle{
(x+1162)(x^2+1961x+2571) \equiv x^3+3123x^2+3x+2 \pmod{5^5}
}

 \frac{5^5}{2}<3123であるため、 5^5 = 3125を引いて x^3-2x^2+3x+2とする。これもf(x)を割り切る。

結局、f(x)は以下のように因数分解出来ることが分かった。

 \displaystyle{
f(x) = (x^2 + 4x - 2)(x^3 - 2x^2 + 3x + 2)
}

まとめ

以上、5次方程式の解の様子を調べるための準備として、 \mathbb{Q}上の多項式の既約性を決定的に判定する方法が存在することについて述べた。今回はあまり深入りしなかったが、この辺りの話は数学とコンピュータが交差する世界であり、調べてみると非常に面白い。数学もコンピュータも好きな方にはぜひオススメしたい。

次回以降、本来の目的である5次方程式の調査を進めていきたいと思う。