代数体上の多項式の因数分解

本稿では次の問題を考える。

” $f\in \mathbb{Q} [x]$ を代数体 $\mathbb{Q} (\alpha)$ 上で因数分解するにはどうしたらよいか？”

これに対する答えとなるアルゴリズムがhttp://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0722-02.pdfの始めに載っている。ここではそれの証明および計算の実例を示してみよう*1。

追記:このアルゴリズムはCohenの有名な"A course in computational algebraic number theory"の3章の6.2に載っていた。

まずそこで与えられているアルゴリズムは以下の通りである（一部記号など変えている）

1. $s$ を有理数とし, $f(x+sy)$ と $f_\alpha(y)$ の $y$ に関する終結式 $r(x)={\rm Res} (f(x+sy),f_\alpha(y),y)$ を求める.このとき $r(x)$ が無平方（即ち重根を持たない）となるように $s$ をうまく定める（このような $s$ は存在し、またそれは整数に選べる）.

2. $r(x)$ を $\mathbb{Q}$ 上で因数分解する
$r(x)=r_1(x)\cdots r_l(x)(各 r_iは \mathbb{Q} 上既約)$

3. 各 $i(i=1,\cdots ,l)$ に対し, $\mathbb{Q} (\alpha)[x]$ の元としてgcdをとる (ただしモニックになるように選ぶ)
$f_i(x)=\gcd (r_i(x),f(x+s\alpha))$

4. すると以下が成り立ち,これが $f\in \mathbb{Q} [x]$ の $\mathbb{Q} (\alpha)$ 上で因数分解を与える(ただし1になる因子も許すことにする)
$f(x)=f_1(x-s\alpha)\cdots f_l(x-s\alpha)$

この記事では主にそのPDFの内容をなぞる形になっている。ここで扱いきれなかったガロア理論の話についてはhttps://period-mathematics.hatenablog.com/entry/2019/05/03/181220で詳しく解説している。ただしそこの後半は本稿の内容を把握していないと読めない。

アルゴリズムの証明
アルゴリズムの計算の実例
PARI/GPを使ってアルゴリズムに頼らずに一気に計算する方法
アルゴリズム通りに計算
まとめ

アルゴリズムの証明

これは以下のPDFを参照してほしい。ただしここでは $f(x)=f_1(x-s\alpha)\cdots f_l(x-s\alpha)$ となるところまでしか解決できておらず、各 $f_i(x)$ が $\mathbb{Q} (\alpha)$ 上既約であることが示されていない。もしお分かりになった方がおられましたら是非ご一報ください

追記（2019/10/29）:コメントでの情報提供で解決しました、ありがとうございます。

drive.google.com

アルゴリズムの計算の実例

まずはそこで与えられている例を計算してみよう。使用する計算機は代数や数論の計算に強いPARI/GPというものである。これを選んだのは単純に使いやすく、わかりやすく、またなんといってもスマホ（ただしAndroid限定）に対応しているからである（Androidでは「PariDroid」というアプリ名でGoogle Playストアを探せば出てくる、現在では）。PCの場合はhttp://pari.math.u-bordeaux.fr/download.htmlからダウンロード出来る。

これを使ったことのない読者も以下の手順を踏んでいくうちにすぐになれると思う。参考までに、https://sehermitage.web.fc2.com/etc/parigp_func.htmlには基本的なコマンド等が載っている。もっと詳しいコマンドなどについては英語で検索すればPDFなどがヒットするのでそれを参考にするとよいだろう。

さて、PDFにて扱われている例は、既約五次多項式

x^5+x^4-4*x^3-3*x^2+3*x+1

の根を $\alpha$ としたとき $\mathbb{Q}(\alpha)$ 上でこれを因数分解するというものである（つまり $f_{\alpha}=f$ というケースである）。これを以下やっていこう。以下の計算機を使う場面では $\alpha$ を $a$ で代用している。

PARI/GPを使ってアルゴリズムに頼らずに一気に計算する方法

アルゴリズム通りに行く前に、PARI/GPの動作確認も兼ねてこれを一気にやってしまおうと思う。実はPARI/GPには既に代数体上の因数分解のコマンド「factornf*2」が実装されているので手始めにそれを使ってみよう。

PARI/GPについて何も知らない読者はここを読まないと次の節は読めない。以下「gp >」と書いてある横にあるものが、その上にある説明を実現するコマンドである。

1. まず上の多項式に名前を付ける

gp > f(x)=x^5+x^4-4*x^3-3*x^2+3*x+1

2.factornfコマンドで $\mathbb{Q}(a)$ 上で因数分解する

gp > factornf(f(x),f(a))

こうすると以下のように出力される

%3 =
[ x + Mod(-a, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1) 1]
[ x + Mod(-a^2 + 2, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1) 1]
[ x + Mod(-a^3 + 3*a, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1) 1]
[ x + Mod(-a^4 + 4*a^2 - 2, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1) 1]
[x + Mod(a^4 + a^3 - 3*a^2 - 2*a + 1, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1) 1] 　

とりあえず流れはこれだけである。出力結果を解読しよう。

まず右に出ている「1」は指数である。またModの「, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1」はただのmodなのでこれは無視してその前の文字を読んでいくと結局以下のような分解が得られたことを意味している

(x - a)(x + (-a^2 + 2))(x + (-a^3 + 3*a))(x + (-a^4 + 4*a^2 - 2))(x + (a^4 + a^3 - 3*a^2 - 2*a + 1))

これはPDFの分解とも一致しており、PARI/GPの信用も上がったと思う。

計算画面はこのようになる

f:id:period_mathematics:20190504011557p:plain

とりあえずこの通りにやってみて分解が得られているかを確認してほしい。

無事できているようならこのコマンドの解説を読み進めていこう。

二番目の手順で「factornf(f(x),f(a))」と打ったわけだがこれは一体何をしたのかということだが、これは次の例を見れば一発だと思う

gp > factornf(x^4-2,y^2-2)
%1 =
[x^2 + Mod(-y, y^2 - 2) 1]

[ x^2 + Mod(y, y^2 - 2) 1]

>gpが入力、%1=以下が出力である。例によってmodの部分「, y^2 - 2」を無視すれば、見ての通りこれは $x^4-2$ を $\mathbb{Q}$ に $y^2-2$ の根を添加して出来る体 $\mathbb{Q}(\sqrt{2})$ 上で因数分解していることがわかるであろう。

このようにfactornf(f(x),g(y))は $g(y)$ の根から作られる体上で $f(x)$ を因数分解するコマンドなのである。そうすれば「factornf(f(x),f(a))」はまさに今懸案としている問題の解を与えるコマンドであることがわかるであろう。

補足（ここの内容も以下で出てくるので読まれたい）

-「modの部分を無視すれば」というようなことを書いてきたがやはりmodの部分があっては見づらい。これを解消するのがコマンド「 lift」で、以下のように打つことでmodの部分がきれいに消えて出力される

コマンド

gp > lift(factornf(f(x),f(a)))

出力
%3 =
[ x - a 1]

[ x + (-a^2 + 2) 1]

[ x + (-a^3 + 3*a) 1]

[ x + (-a^4 + 4*a^2 - 2) 1]

[x + (a^4 + a^3 - 3*a^2 - 2*a + 1) 1]

この考察からもliftは係数がmodタイプのとき、元に戻す（係数をその代表元に置き換える）操作をするコマンドであることがわかる。

アルゴリズム通りに計算

さて、それでは本題に入る。

1. 多項式に名前を付ける

gp > f(x)=x^5+x^4-4*x^3-3*x^2+3*x+1
%1 = (x)->x^5+x^4-4*x^3-3*x^2+3*x+1

2. $a$ を mod $f(a)$ で還元する

gp > a=Mod(a,f(a))
%2 = Mod(a, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1)

3. $f$ を自明な因子 $x-a$ で割る

gp > lift(f(x)/(x-a))
%3 = x^4 + (a + 1)*x^3 + (a^2 + a - 4)*x^2 + (a^3 + a^2 - 4*a - 3)*x + (a^4 + a^3 - 4*a^2 - 3*a + 3)
（これは $f$ を $\mathbb{Q}(a)$ 係数多項式と認識させることが出来るという効果もある）

4.今の結果を新しく $h(x,a)$ と名前を付ける

gp > h(x,a)=x^4 + (a + 1)*x^3 + (a^2 + a - 4)*x^2 + (a^3 + a^2 - 4*a - 3)*x + (a^4 + a^3 - 4*a^2 - 3*a + 3)

%4 = (x,a)->x^4+(a+1)*x^3+(a^2+a-4)*x^2+(a^3+a^2-4*a-3)*x+(a^4+a^3-4*a^2-3*a+3)

5.終結式を計算する

gp > polresultant(h(x+b,b),f(b),b)

%5 =x^20 - 44*x^18 + 792*x^16 - 7623*x^14 + 43076*x^12 - 147983*x^10 + 310123*x^8 - 388652*x^6 + 278179*x^4 - 102487*x^2 + 14641
（文字を $a$ から $b$ に変えているのは、今は $a$ は手順2の影響でmodで還元されてしまっているから通常の変数の役割を果たせないからである（エラーが出る））

6.これを因数分解する

gp > factor(%5)

%6 =
[x^5 - 11*x^3 - 11*x^2 + 11*x + 11 1]
[ x^5 - 11*x^3 + 22*x - 11 1]
[ x^5 - 11*x^3 + 22*x + 11 1]
[x^5 - 11*x^3 + 11*x^2 + 11*x - 11 1]

7.その中の因子と「 $\mathbb{Q}(a)$ 内で」gcdをとる*3が使えはする。))

gp > gcd(h(x+a,a),x^5-11*x^3+22*x+11)
%7 =Mod(5*a^4 - 16*a^3 - 13*a^2 + 29*a + 9, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1)*x + Mod(-30*a^4 + 9*a^3 + 61*a^2 - 8*a - 7, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1)

8.モニックにする

gp > (%7)/(5*a^4-16*a^3-13*a^2+29*a+9)
%8 = Mod(1, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1)*x + Mod(-a^4 + 4*a^2 + a - 2, a^5 + a^4 - 4*a^3 - 3*a^2 + 3*a + 1)（ただし「%7」はここでは直前の結果を表している）*4

よって-a^4+4*a^2+a-2が因子の一つ。他の因子も同様。

これを実際に行なった様子は

f:id:period_mathematics:20190504085243p:plain

まとめ

PARI/GPの計算においては既にコマンドが実装されているため実用上はこのアルゴリズムに頼る必要がないのはお察しの通りだと思う。

ただ代数体上の因数分解というのは基本的で重要な話題に思うので、このような理論的側面を追うのはいつか重要になってくるのではないかと思う。

とりあえずPARI/GPの扱いに慣れることも目的の一つなので是非手順を追って計算してみてほしい。

*1:以下の議論において $\mathbb{Q}$ を全て標数0の体 $F$ で置き換えることで $F$ 上の多項式に対しても全く同様の結果が成り立つ.

*2:Tragerの方法によっているらしい

*3:もともと筆者は例えばここならgcd(h(x+a,a),x^5-11*x^3+22*x+11+0*a)というように「+0*a」という項を付け加えて $\mathbb{Q}(a)$ 係数だと認識させていたのだがどうやら手順3の時点でそれは達成されていたようだったのでその必要はなかった。この考えでfactornfの代わりにlift( factor (f(x)+0*a

*4:この記法は関数を扱う場合少し注意が必要で、例えば手順4で「 h(x,a)=%3」とやっても、関数として機能してくれない。例えばh(1,2)などの具体値を計算しようとすればわかる