有限群全形的計算

王積社

（韓山師范學院數(shù)學與統(tǒng)計學系，廣東潮州 521041）

一般地說，群G的自同構不一定都是內(nèi)自同構.因此提出問題：是否存在一個群G*≥G，且GG*，使得G的每個自同構都可由G*的內(nèi)自同構限制在G上得到？答案是肯定的，所謂的群的全形就是滿足上述條件的擴群[1]34.然而，確定群G的全形僅人工計算并非易事，因此本文試研究有限群全形的算法及程序.

1 理論基礎

本文中，模n的剩余類加群簡記為Z={0 ,1,…,n-1}，n階置換

n簡記為[k1,k2,…kn]（稱之為置換的簡約形），群G上所有的一一變換組成的群記為SG.

設G={a1=e,a2,…,an}是n階群，取定ai∈G，作映射

亦可表為

令R(G)={R (a1),R(a2),…,R(an)}，則R(G )≤Sn且G?R(G)[2]35-37，因此稱R(G)為G的右正則表示.

設G為群，a，g∈G，規(guī)定ag=g-1ag，稱之為a在g下的共軛變形.同樣對于G的子群或子集H，規(guī)定Hg=g-1Hg叫做H在g下的共軛變形.

定義1 設G是群，H是G的子群，g∈G.若Hg=H，則稱g正規(guī)化H，并稱G中所有正規(guī)化H的元素的集合

為H在G中的正規(guī)化子.

定義2 稱Hol(G)=NSG(R(G))為G的全形.

定理1 用Aut(G)表示G的自同構群，則Hol(G)=R(G)Aut(G)且R(G)?Aut(G)=1.[1]35

因此，如果把G與R(G)同等看待，那么Hol(G)就可作為開始問題中要找的G*.[1]35

定理2 Hol(G)=Aut(G)·R(G)且Hol(G)/R(G)?Aut(G).[3]92

定理3 n階循環(huán)群的自同構群是一個φ(n)階的群，其中φ(n)是歐拉函數(shù).

證明 因為同構映射下生成元與生成元相對應，且生成元的對應關系完全決定了群中其它元素的對應關系，所以循環(huán)群的自同構數(shù)等于其生成元數(shù).于是設G=＜a＞是由a生成的n階循環(huán)群，則當k是小于n且與n互素的正整數(shù)時，ak也是G的生成元(參見文獻[4]之P61習題結果)，因此G=＜ak＞.令

可證σk是G的自同構映射，由于G有且僅有φ(n)個生成元，所以G的自同構群必為φ(n)階的群.

定理4 設G是n階群，則|Hol(G)|=n|Aot(G)|（這里 ||A表示集合A的基數(shù)），進而當G是循環(huán)群時|Hol(G)|=nφ(n).

證明因為Hol(G)=Aut(G)·R(G)且R(G)?Aut(G)=1，所以|Hol(G)|=|A u t(G)||R(G)|(參見文獻[3]之P21習題結果).又G?R(G)?|R(G)|=|G|=n，所以|Hol(G)|=n|Aut(G)|.而當G是循環(huán)群時|Aut(G)|=φ(n)，所以當G是循環(huán)群時|Hol(G)|=nφ(n).

2 Hol(G)的一般算法

于是，要求Hol(G)需作三步處理：（1）求 R(G)；（2）求SG；（3）在SG中找出所以符合條件g-1R(SG)g=R(SG)的元素.具體如下：

2.1 算法設計

step1 輸入或生成群G的元素.需要酌情處理，例如：對于Zn，只要輸入n，由程序生成數(shù)組Zn={0，1，…，n-1}即可；而對于置換群，可直接輸入全部元素的簡約式，也可輸入其生成元而由程序生成其所有元素（置換群的生成算法可參見文獻[5]）.

step2 計算R(G).因為R(ai)=[a1aia2ai… anai]，所以需要根據(jù)G的乘法具體計算，例如對于Zn，R(Zn)={R(0)， R(1)， …，R(n-1)}，R(i)=[0+i 1+i… n-1+i]，所以如果用二維數(shù)組RZn存儲R(Zn)的元素，那么求R(Zn)的算法如下：

step3計算SG.因為

所以需要先計算SG.而SG是G上所有的一一變換組成的群，所以SG的計算需要全排列的生成算法.例如，對于Zn，如果用g={g[1]g[2]…g[n]}表示Zn元素的全排列，那么使用全排列的生成算法（如文獻[6]中的換位法）計算SZn的算法如下：

因為群G的全形為

step4 計算Hol(G).因為Hol(G)={g∈SG|g-1R(G)g=R(G)}，所以需要在SG中找出所有滿足g-1R(G)g=R(G)的元素g，亦即是需要對G中的每個元素g，判定集合g-1R(Zn)g是否與R(Zn)相等，為此采取以下措施：

①因為當n較大時， ||SG非常大，所以若存儲SG元素勢必需要很大的存儲空間，這是不可行的，但是注意到判定是否g-1R(G)g=R(G)，只需要對每個g∈SG進行一次即可，所以可不存儲SG的元素，而在SG元素的生成過程中，生成一個判定一個即可，這樣即可節(jié)省大量的存儲空間.

②因為g-1R(G)g=R(G)?g-1R(G)g?R(G)且R(G)?g-1R(G)g，而顯然R(G)?g-1R(G)g，所以只要在SG找出滿足g-1R(G)g?R(G)的所有元素g即可.

③關于共軛變形，需要進行置換的乘法運算，而置換的運算使用置換的簡約式非常方便，因為?x∈R(Zn)，如用一維數(shù)組a、b、c、e分別存儲g、g-1、x、g-1xg的簡約式，那么：

求g-1的算法為：for(k=1;k＜=n;k++)b[a[i]]=i;

求g-1xg的算法為：for(k=1;k＜=n;k++)e[i]=a[c[b[i]]];

2.2 參考程序

根據(jù)算法，使用C語言設計了求Hol(Zn)的參考程序，程序中用一維數(shù)組Zn[n+1]存儲模n的剩余類，二維數(shù)組RZn存儲Zn的右正則表示.程序代碼如下：

2.3 算法分析

首先，因為必須遍歷SG中所有元素，所以算法的時間復雜度不可避免地是O(n!)，于是隨著n增大計算會愈加困難，如在筆者的電腦(CPU：AMD Athlon IIX2 240，內(nèi)存：2G)上計算Hol(Z12)僅需173 s，而計算Hol(Z13)用了41 min，但計算Hol(Z14)則用了10 h.不過如若需要的話可用并行計算處理較大的Hol(G)——這是可以的，因為存在全排列生成的并行算法[7,8]，并且“邊生成邊判斷”的算法也恰好支持并行處理.其次，使用“邊生成邊判斷”的算法不僅有益于提高計算速度，而且使空間復雜度降低至O(n2)，這是非常有利的.

3 Hol(Z n)特殊算法

3.1 算法設計

首先根據(jù)定理2，Hol(Zn)=Aut(Zn·)R(Zn)；其次根據(jù)定理3，Hol(Zn)是一個φ(n)階的群，其同構映射σk為σk(a)=ak，其中的k滿足(n,k)=1；再次根據(jù)定理4可知，Aut(Zn·)R(Zn)沒有重復元素.因此可特別設計計算Hol(Zn)的算法如下：

step1 求所有小于n且與n互素的k，這需要判定兩個正整數(shù)是否互素的算法，實質(zhì)上即是求兩個正整數(shù)的最大公因數(shù)算法.

step2 求 R(Zn)={R(0)，R(1)，…，R(n-1)}， R(i)=[0+i 1+i…n-1+i].

step3 求 Aut(Zn)={σ1,σ2,…,σφ(n)} ， 其 中

step3計算Hol(Zn)=Aut(Zn)·R(Zn).

3.2 參考程序

根據(jù)算法，使用C語言設計了求Hol(Zn)的特別程序，程序中用一維數(shù)組Zn[n+1]存儲模n的剩余類，二維數(shù)組RZn與Aut分別存儲Zn的右正則表示及Zn的自同構群.程序代碼如下：

3.3 算法分析

此算法的時間與空間復雜度都是n2級的，效率較高，在筆者的電腦上，計算Hol(Z1000)且輸出400 000個元素到文件中，僅用96 s；計算Hol(Z5000)輸出10 000 000個元素到文件中，約用3.5 h.

4 計算示例

例1 Hol(Z4)的計算結果如下.

亦即是：

例2 Hol(Z10)的計算結果如下.

5 結論

本文給出了有限群G的全形Hol(G)的算法及程序以及剩余類加群Zn之全形的特殊算法及程序，算法及程序都只是參考的，有待于進一步優(yōu)化.比如設計高效的全排列生成算法是提高算法計算速度的關鍵；再如判定是否g-1R(G)g?R(G)時需要遍歷R(G)的元素，工作量較大，但如果先將R(G)共軛分類，判定時根據(jù)g-1xg(x∈R(G))的“型”在相應的共軛類中判定，也許能提高計算速度.另外本應給出前n個Hol(Zn)的計算結果（每個Hol(Zn)的生成元），但是限于篇幅，另文再續(xù).

[1]徐明曜.有限群導引[M].北京：科學出版社，1999.

[2]王萼芳.有限群論基礎[M].北京：清華大學出版社，2012.

[3]張遠達.有限群構造：上冊[M].北京：科學出版社，1982.

[4]張禾瑞.近世代數(shù)基礎[M].修訂本.北京：高等教育出版社，1978.

[5]王積社.置換群的生成算法[J].科教文匯，2009，（3，中旬刊）：269.

[6]王曉玲.換位法實現(xiàn)全排列[J].滄州師范專科學校學報，2004，20（4）：56.

[7]吳素萍.全排列遞歸算法的并行化[J].寧夏大學學報：自然科學版，2007，28（4）：337-339.

[8]鐘珞.最佳并行排列組合算法[J].微機發(fā)展，1991（1）：24-26.