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]。

f(x)がsquare freeであるかどうかを調べる。もしsquare freeでなければf(x)は可約なので処理を終える。
pを素数とする。f(x)の各係数をmod pで写して得られる多項式が $F_p$ 上でもsquare freeになるようなpを見つける。
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}$ 上既約なので処理を終える。
$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乗和の平方根を表す。
$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次方程式の調査を進めていきたいと思う。