-数学- SympyとGAPで可移部分群の条件から5次方程式のガロア群を高速に求める(3)

今回はプログラム編です。いきなりSympyで実装した、可移部分群を使った実装をお見せします。

TransitiveGroups5とかTransitiveGroup4という変数に、大量のPermutationGroupのインスタンスのリストが設定されています。これらはそれぞれ、全て\(S_5\), \(S_4\)の可移部分群のリストになっています。またそれぞれのリストの中の可移部分群は位数の小さい順に並んでいます。

from sympy import *
from sympy.abc import a, b, c, d, e, f, x, y, z, V, k
from sympy.combinatorics import *

SOLVARLIST=[a,b,c,d,e,f]

# order sorted list of transitive subgroups of S5
# generated using GAP with the following commands
# gap> genIsTransitive := function (n) return (function(g) return IsTransitive(g,[1..n]); end); end;
# gap> Filtered(AllSubgroups(SymmetricGroup(5)),genIsTransitive(5));
# and a copule of syntax adjustments from GAP to Sympy
TransitiveGroups5=[
    PermutationGroup([ Permutation(0,2,4,1,3) ]), 
    PermutationGroup([ Permutation(0,3,4,2,1) ]), 
    PermutationGroup([ Permutation(0,1,3,4,2) ]), 
    PermutationGroup([ Permutation(0,3,4,1,2) ]), 
    PermutationGroup([ Permutation(0,3,1,2,4) ]), 
    PermutationGroup([ Permutation(0,1,4,2,3) ]), 
    PermutationGroup([ Permutation(0,2)(1,4), Permutation(0,3,2,1,4) ]), 
    PermutationGroup([ Permutation(0,2)(1,3), Permutation(0,1,4,3,2) ]), 
    PermutationGroup([ Permutation(1,3)(2,4), Permutation(0,4,3,1,2) ]), 
    PermutationGroup([ Permutation(0,3)(1,4), Permutation(0,3,4,2,1) ]), 
    PermutationGroup([ Permutation(0,3)(2,4), Permutation(0,4,2,3,1) ]), 
    PermutationGroup([ Permutation(0,3)(1,2), Permutation(0,4,3,2,1) ]), 
    PermutationGroup([ Permutation(0,1)(2,3), Permutation(0,4,2,1) ]), 
    PermutationGroup([ Permutation(1,2)(3,4), Permutation(0,3,2,1) ]), 
    PermutationGroup([ Permutation(0,4)(2,3), Permutation(1,4,3,2) ]), 
    PermutationGroup([ Permutation(0,4)(1,2), Permutation(0,4,3,1) ]), 
    PermutationGroup([ Permutation(0,1)(3,4), Permutation(0,4,3,2) ]), 
    PermutationGroup([ Permutation(0,2)(3,4), Permutation(0,1,3,2) ]), 
    PermutationGroup([ Permutation(0,3)(1,2), Permutation(1,4,3) ]), 
    PermutationGroup([ Permutation(3,4), Permutation(0,1,3,2) ])]

# order sorted list of transitive subgroups of S4
# gap> Filtered(AllSubgroups(SymmetricGroup(4)),genIsTransitive(4));
TransitiveGroups4=[
    PermutationGroup([ Permutation(0,3)(1,2), Permutation(0,2)(1,3) ]), 
    PermutationGroup([ Permutation(0,2,1,3), Permutation(0,1)(2,3) ]), 
    PermutationGroup([ Permutation(0,3,2,1), Permutation(0,2)(1,3) ]), 
    PermutationGroup([ Permutation(0,1,3,2), Permutation(0,3)(1,2) ]), 
    PermutationGroup([ Permutation(0,3)(1,2), Permutation(0,2)(1,3), Permutation(2,3) ]), 
    PermutationGroup([ Permutation(0,1)(2,3), Permutation(0,2)(1,3), Permutation(0,3) ]), 
    PermutationGroup([ Permutation(0,1)(2,3), Permutation(0,3)(1,2), Permutation(1,3) ]), 
    PermutationGroup([ Permutation(0,3)(1,2), Permutation(0,2)(1,3), Permutation(1,3,2) ]), 
    PermutationGroup([ Permutation(0,3)(1,2), Permutation(0,2)(1,3), Permutation(1,3,2), Permutation(2,3)])]

def phi(args): return Sum(Array([1,-1,2,-5,0])[k]*Array(args)[k],(k,0,len(args)-1)).doit()

def GaloisGroupMinumalPolynomial(p):
    varList=SOLVARLIST[:p.degree()]
    numsollist=list(zip(varList,p.nroots(n=310)))
    if p.degree()==4:
        transitivesubg=TransitiveGroups4
    elif p.degree()==5:
        transitivesubg=TransitiveGroups5
    else:
        return("Degree of p must be 4 or 5")
    
    for gal in transitivesubg:
        res=1
        for g in gal._elements:
            res=expand(res*(V-phi(g(varList)).subs(numsollist)))
        all_coeff_list=list(map(lambda x:((x*1000).round())/1000,Poly(res).all_coeffs()))
        if all(list(map(lambda x:x.is_Integer and not x.has(I),all_coeff_list))):
            return((Poly(all_coeff_list,gens=V)),gal)
    return(False)

def displayG(mp,gg):
    display(mp.expr, gg, gg.order())

phi()という関数が、引数に解の並びのリストを取り、適当な一次結合による単拡大の原始元を作ります。

GaloisGroupMinumalPolynomial(p)という関数はpとして指定された多項式を引数として、pのガロア群を計算します。この際に前回説明したアルゴリズムが使われています。pは最大次係数が1、整数係数の既約な多項式でなければなりません。

プログラム中の変数numsollistには解を表すSympy変数と数値解の組が設定されます。また変数galには可移部分群が設定され、変数gにはgalの中の置換が設定されます。変数resには最小多項式の候補が設定されます。係数が全て整数かどうか確認して、そうであれば、resは最小多項式であることがわかるので、resと対応する可移群を返します。

displayG()という関数は多項式と群のペアを受け取り、それらをlatex表示します。

このデータとして抱え込んでいる可移群のリストは別の群論専用数学ソフトであるGAPを利用しました。GAPをインストールして起動します。そして上記プログラム中のコメントにあるコマンド：

gap> genIsTransitive := function (n) return (function(g) return IsTransitive(g,[1..n]); end); end;
gap> Filtered(AllSubgroups(SymmetricGroup(5)),genIsTransitive(5));

を走らせると、可移群のリストがGAPのシンタックスで得られます。このリストを適当なエディタ （VSCodeなど）に読み込んでSympyのシンタックスに直したものがこのプログラムに組み込まれています。

過去にMaximaで実装してきたプログラムでは群論の知識はほとんど使わず、ガロア理論の知識だけでガロア群を計算していました。今回のプログラムではガロア群が可移群になる、という群論の知識を使うことで大幅な高速化を達成できました。