正規部分群の構成

今回のオリジナルプログラムでは各元の一点集合の conjugate closure から極大正規部分群を選んでいますが,それが必ずしも正しい結果を与えないことも,例えば

G:[[1,2,3,4,5,6],[1,2,3,4,6,5],[1,2,4,3,5,6],[1,2,4,3,6,5],
     [2,1,3,4,5,6],[2,1,3,4,6,5],[2,1,4,3,5,6],[2,1,4,3,6,5]];

正規部分群

[[1,2,3,4,5,6],[1,2,3,4,6,5],[1,2,4,3,5,6],[1,2,4,3,6,5]]

のように指摘されています.

一方,共役類に分割された群  G=\bigcup_{i\in A}C_i とその部分群 S について,次の2つは等価でした.
(1)SG正規部分群である.
(2) S=\bigcup_{i\in B}C_i となる空でない B \subseteq A がある.

従って,有限群 G を共役類に分割すれば,G の位数 d正規部分群の全体は,元の個数の合計が d,かつ,和が積閉である共役類の和の全体に一致します.

以下,この性質による組成列計算のコードを記します.なお,mnsg では powerset を用いましたが,入力の群のサイズが程々(笑)なら共役類も多くはないので,爆発しないと思われます(母関数を用いると,元の個数の合計が d になる組のみを抽出できますが,…).

/* 置換の積,逆元 */
mul(A,B):=map(lambda([s],A[s]),B)$
inv(A):=map(second,sort(map("[",A,sort(A)),lambda([s,t],s[1]<t[1])))$
/* 共役類分割 */
CC(GG):=block([g,C:[],G:setify(GG),H],
unless G={} do (g:listify(G)[1],
H:setify(map(lambda([s],mul(s,mul(g,inv(s)))),GG)),
G:setdifference(G,H),push(H,C)),map(listify,C))$
/* 積閉判定 */
isG(GG):=is(setify(apply('append,makelist(makelist(mul(i,j),i,GG),j,GG)))=setify(GG))$
/* 極大正規部分群 */
mnsg(GG):=block([S:[],PS:map(lambda([s],apply('append,listify(s))),listify(powerset(setify(CC(GG)))))],
for d in rest(reverse(listify(divisors(length(GG))))) while S=[] do
S:sublist(PS,lambda([s],length(s)=d and isG(s))),S[1])$
/* Galois 群の組成列 */
cs(GG):=block([S:[GG],m:GG],unless length(m)=1 do push(m:mnsg(m),S),
[S:reverse(S),S:map(length,S),makelist(S[i-1]/S[i],i,2,length(S))])$

例えば,冒頭のGに対して,cs(G); と入力すれば

[[[[1,2,3,4,5,6],[1,2,3,4,6,5],[1,2,4,3,5,6],[1,2,4,3,6,5],
          [2,1,3,4,5,6],[2,1,3,4,6,5],[2,1,4,3,5,6],[2,1,4,3,6,5]],
         [[1,2,3,4,5,6],[1,2,3,4,6,5],[1,2,4,3,5,6],[1,2,4,3,6,5]],
         [[1,2,3,4,5,6],[1,2,3,4,6,5]],[[1,2,3,4,5,6]]],[8,4,2,1],[2,2,2]]

と出力(最後の2つは各部分群の位数,隣接するそれらの比の値)されます.

次の位数9の部分群は,冒頭の例と同じく,singleton の conjugate closure にはならないものです.

[x^6+x^5+x^4+x^3-4*x^2+5,
 [[[[1,2,3,4,5,6],[1,3,2,5,4,6],[3,4,1,6,2,5],[3,1,4,2,6,5],[2,4,1,3,6,5],
    [2,1,4,6,3,5],[4,2,3,5,1,6],[4,3,2,1,5,6],[3,5,1,2,6,4],[3,1,5,6,2,4],
    [2,5,1,6,3,4],[2,1,5,3,6,4],[5,2,3,1,4,6],[5,3,2,4,1,6],[3,5,4,6,2,1],
    [3,4,5,2,6,1],[2,5,4,3,6,1],[2,4,5,6,3,1],[1,6,3,5,4,2],[1,3,6,4,5,2],
    [1,6,2,4,5,3],[1,2,6,5,4,3],[6,4,1,2,3,5],[6,1,4,3,2,5],[4,6,3,1,5,2],
    [4,3,6,5,1,2],[4,6,2,5,1,3],[4,2,6,1,5,3],[6,5,1,3,2,4],[6,1,5,2,3,4],
    [5,6,3,4,1,2],[5,3,6,1,4,2],[5,6,2,1,4,3],[5,2,6,4,1,3],[6,5,4,2,3,1],
    [6,4,5,3,2,1]],
   [[1,2,3,4,5,6],[1,2,6,5,4,3],[1,3,2,5,4,6],[1,6,3,5,4,2],[4,2,6,1,5,3],
    [4,3,2,1,5,6],[4,6,3,1,5,2],[5,2,6,4,1,3],[5,3,2,4,1,6],[5,6,3,4,1,2],
    [1,3,6,4,5,2],[1,6,2,4,5,3],[4,2,3,5,1,6],[5,2,3,1,4,6],[4,3,6,5,1,2],
    [4,6,2,5,1,3],[5,3,6,1,4,2],[5,6,2,1,4,3]],
   [[1,2,3,4,5,6],[1,3,6,4,5,2],[1,6,2,4,5,3],[4,2,3,5,1,6],[5,2,3,1,4,6],
    [4,3,6,5,1,2],[5,6,2,1,4,3],[4,6,2,5,1,3],[5,3,6,1,4,2]],
   [[1,2,3,4,5,6],[1,3,6,4,5,2],[1,6,2,4,5,3]],[[1,2,3,4,5,6]]],[36,18,9,3,1],
  [2,2,3,3]]]