今回は数学編です。
以前にMaximaで作成した、方程式のガロア群を求めるプログラムをSympyに移植しました。
-数学- はじめてSympyを使ってみた！ ーガロア群の計算を題材にしてー - Maxima で綴る数学の旅
まずその際に実装したアルゴリズムを簡単に復習します。
与えられた整係数モニック既約n次方程式をp(x)とします。 全ての係数が整数、最高次数はnでその係数が1、整数の範囲で因数分解ができない、ということです。
p(x)の数値解を全て求め、その適切な一次結合を作ります。解を並べ替えた一次結合も全て作り、それら全てを解とする別の方程式q(x)を計算します。q(x)の係数は浮動小数で求まりますが、それらは整数のはずなので、丸めて整数にします。q(x)を因数分解できるならすると、因数の１つが、p(x)の解の一次結合の満たす最小多項式になります。これをr(x)としましょう。r(x)の解は全て、p(x)の解の並べ替えの一次結合になっています。これらの並べ替えを置換群としてみたものがp(x)のガロア群です。
群論と体論の言葉を使うと、p(x)の分解体は係数体の単拡大なので、原始元があります。それを解の一次結合として作り、原始元を根とする最小多項式をr(x)として求めます。r(x)を求めるために、まず解の並びにn次対称群を作用させて得られる並び全ての一次結合を作り、それら全てを解とする方程式をq(x)として求めます。それが因数分解できるならして、その因数の１つをr(x)とします（因数分解できなければq(x)そのものがr(x)）。r(x)の解は全てp(x)の解の並べ替えの一次結合になっており、その並べ替えを置換群としてみたものがp(x)のガロア群です。
最後の１行を言い換えると、p(x)の解の並びにp(x)のガロア群を作用させた並びの一次結合がr(x)の解です。
従って、何かの手段でガロア群の候補（複数でも良い）が分かれば、p(x)の解の並びにその候補群を作用させた並べ替えの一次結合を全て数値計算し、それらを解としてもつr(x)の候補を計算できます。r(x)候補式の係数が全て整数になれば、ガロア群の候補として合格です。そのようなガロア群候補の中で最も位数が小さい候補群が、ガロア群というわけです。
ではp(x)のガロア群の候補に何があるか、というとそれがn次対称群の可移部分群なのです。p(x)は既約です。既約な方程式のガロア群は必ず可移群になります。従ってp(x)のガロア群は必ずn次対称群の可移部分群であることになります。
可移群とは、置換群の一種で、n文字の数字の並び1,...,nにその中の全ての置換を作用させたとき、全ての文字が移動する、という性質を持つ群です。大雑把に言えば既約方程式の解の対称性から、解の並びにガロア群を作用させると全ての解が他の解に移り得る、ということです。
というわけで、n次方程式p(x)に対してn次対称群\(S_n\)の全ての可移部分群を生成出来れば、１つづつ可移部分群がガロア群なのかどうかをチェックすることは高速に実行できることがわかります。
まとめるとアルゴリズムは以下のようになります。
事前計算で\(S_n\)の可移部分群を全て求めます。可移部分群を位数の小さい順に並べておきます。p(x)の全ての解の適切な一次結合及びその解の並びに、可移部分群を１つ作用させて得られる並び替え全てを解としてもつ方程式r(x)を数値計算で計算します。係数が全て整数に十分に近くなれば、その可移部分群がp(x)のガロア群であり、r(x)が分解体の原始元の最小多項式です。
n次既約方程式のガロア群がn次対称群の可移部分群であることは、様々な文献で述べられていますが、例えばアルティンの本：
では第3章の３「方程式のガロア群」 (p151-152)に、可遷群という言葉で説明されています。
次回はプログラム編です。
