Pグループ生成アルゴリズム

数学、特に群論においては、固定された素数と変化する整数指数に対する素数冪順序の有限群は、簡単に言えば有限p群と呼ばれます。 ${\displaystyle p^{n}}$${\displaystyle p}$${\displaystyle n\geq 0}$

MF Newman ^[1] とEA O'Brien ^[2] [ ^3]によるp群生成アルゴリズムは、木の根として取られる 割り当てられた有限p群の子孫木を 構築するための再帰的なプロセスである。

有限p群に対して、の下指数p中心級数（簡単に言うと下p中心級数）はの特性部分群の 降順級数であり、次のように再帰的に定義されます。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle (P_{j}(G))_{j\geq 0}}$${\displaystyle G}$

${\displaystyle (1)\qquad P_{0}(G):=G}$そして、 については。 ${\displaystyle P_{j}(G):=\lbrack P_{j-1}(G),G\rbrack \cdot P_{j-1}(G)^{p}}$${\displaystyle j\geq 1}$

任意の非自明な有限p群は冪零であるため、となる整数が存在し 、は の指数pクラス(簡単にpクラス)と呼ばれます。 自明な群のみがを持ちます。一般に、任意の有限p群に対して、そのpクラスは と定義できます。 ${\displaystyle G>1}$${\displaystyle c\geq 1}$${\displaystyle P_{c-1}(G)>P_{c}(G)=1}$${\displaystyle \mathrm {cl} _{p}(G):=c}$${\displaystyle G}$${\displaystyle 1}$${\displaystyle \mathrm {cl} _{p}(1)=0}$${\displaystyle G}$${\displaystyle \mathrm {cl} _{p}(G):=\min \lbrace c\geq 0\mid P_{c}(G)=1\rbrace }$

したがって、の完全な下p中心級数は次のように与えられる。 ${\displaystyle G}$

${\displaystyle (2)\qquad G=P_{0}(G)>\Phi (G)=P_{1}(G)>P_{2}(G)>\cdots >P_{c-1}(G)>P_{c}(G)=1}$、

は のFrattini 部分群であるためです。 ${\displaystyle P_{1}(G)=\lbrack P_{0}(G),G\rbrack \cdot P_{0}(G)^{p}=\lbrack G,G\rbrack \cdot G^{p}=\Phi (G)}$${\displaystyle G}$

読者の便宜と番号のシフトを指摘するために、（通常の）下中心級数は、の特性部分群の下降級数でもあり、次のように再帰的に定義されること を思い出す。${\displaystyle G}$${\displaystyle (\gamma _{j}(G))_{j\geq 1}}$${\displaystyle G}$

${\displaystyle (3)\qquad \gamma _{1}(G):=G}$そして、 については。 ${\displaystyle \gamma _{j}(G):=\lbrack \gamma _{j-1}(G),G\rbrack }$${\displaystyle j\geq 2}$

上で述べたように、任意の非自明な有限p群に対して、となるような整数が存在し 、は の冪零類と呼ばれ、 はの冪零性の指数と呼ばれます。 は自明な群のみに存在します。 ${\displaystyle G>1}$${\displaystyle c\geq 1}$${\displaystyle \gamma _{c}(G)>\gamma _{c+1}(G)=1}$${\displaystyle \mathrm {cl} (G):=c}$${\displaystyle G}$${\displaystyle c+1}$${\displaystyle G}$${\displaystyle 1}$${\displaystyle \mathrm {cl} (1)=0}$

の完全な下中心級数は次のように与えられる。 ${\displaystyle G}$

${\displaystyle (4)\qquad G=\gamma _{1}(G)>G^{\prime }=\gamma _{2}(G)>\gamma _{3}(G)>\cdots > \ガンマ _{c}(G)>\ガンマ _{c+1}(G)=1}$、

は の交換子部分群または導来部分群であるためです。 ${\displaystyle \gamma _{2}(G)=\lbrack \gamma _{1}(G),G\rbrack =\lbrack G,G\rbrack =G^{\prime }}$${\displaystyle G}$

指数pクラスについては、次のルールを覚えておく必要があります。

を有限のp群とします。 ${\displaystyle G}$

R

1. 規則:は よりも速く下降するためです。${\displaystyle \mathrm {cl} (G)\leq \mathrm {cl} _{p}(G)}$${\displaystyle \gamma _{j}(G)}$${\displaystyle P_{j}(G)}$
2. 規則:あるグループ に対して が成り立つ場合、任意の に対して が成り立ちます。${\displaystyle \vartheta \in \mathrm {Hom} (G,{\チルダ {G}})}$${\displaystyle {\tilde {G}}}$${\displaystyle \vartheta (P_{j}(G))=P_{j}(\vartheta (G))}$${\displaystyle j\geq 0}$
3. 規則: 任意の について、条件および はを意味します。${\displaystyle c\geq 0}$${\displaystyle N\triangleleft G}$${\displaystyle \mathrm {cl} _{p}(G/N)=c}$${\displaystyle P_{c}(G)\leq N}$
4. 規則: とします。 の場合、すべての に対して が成り立ち、特に、すべての に対して が成り立ちます。${\displaystyle c\geq 0}$${\displaystyle \mathrm {cl} _{p}(G)=c}$${\displaystyle \mathrm {cl} _{p}(G/P_{k}(G))=\min(k,c)}$${\displaystyle k\geq 0}$${\displaystyle \mathrm {cl} _{p}(G/P_{k}(G))=k}$${\displaystyle 0\leq k\leq c}$

指数p類の有限非自明p群の親は 、 を の下指数p中心級数の最後の非自明項で割っ た商として定義されます。逆に、この場合、は の直接の子孫と呼ばれます。親と直接の子孫のp類は によって接続されます。 ${\displaystyle \pi (G)}$${\displaystyle G>1}$${\displaystyle \mathrm {cl} _{p}(G)=c\geq 1}$${\displaystyle \pi (G):=G/P_{c-1}(G)}$${\displaystyle G}$${\displaystyle P_{c-1}(G)>1}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \pi (G)}$${\displaystyle \mathrm {cl} _{p}(G)=\mathrm {cl} _{p}(\pi (G))+1}$

子孫ツリーは、有限p群の同型類 間の親子孫関係を視覚化するための階層構造です。子孫ツリーの頂点は、有限p群の同型類です。ただし、頂点は常に、対応する同型類の代表を選択することによってラベル付けされます。頂点が頂点の親である場合は常に、子孫ツリーの有向辺は 、商 への標準射影 の方向でによって定義されます。 ${\displaystyle \pi (G)}$${\displaystyle G}$${\displaystyle G\to \pi (G)}$ ${\displaystyle \pi :G\to \pi (G)}$${\displaystyle \pi (G)=G/P_{c-1}(G)}$

子孫ツリーでは、親と直下の子孫の概念を一般化できます。頂点は頂点の子孫であり、がと等しいかパス が存在する場合、は の祖先です。${\displaystyle R}$${\displaystyle P}$${\displaystyle P}$${\displaystyle R}$${\displaystyle R}$${\displaystyle P}$

${\displaystyle (5)\qquad R=Q_{0}\to Q_{1}\to \cdots \to Q_{m-1}\to Q_{m}=P}$、 どこ、 ${\displaystyle m\geq 1}$

からへの有向辺。パスを形成する頂点は、の反復親と必ず一致します。 ${\displaystyle R}$${\displaystyle P}$ ${\displaystyle Q_{j}=\pi ^{j}(R)}$${\displaystyle R}$${\displaystyle 0\leq j\leq m}$

${\displaystyle (6)\qquad R=\pi ^{0}(R)\to \pi ^{1}(R)\to \cdots \to \pi ^{m-1}(R)\to \pi ^{m}(R)=P}$、 どこ。 ${\displaystyle m\geq 1}$

これらは、のpクラスが次のように与えられる 場合ののp クラスの連続した商 として見ることもできます。 ${\displaystyle Q_{j}=R/P_{c-j}(R)}$ ${\displaystyle c-j}$${\displaystyle R}$${\displaystyle R}$${\displaystyle \mathrm {cl} _{p}(R)=c\geq m}$

${\displaystyle (7)\qquad R\simeq R/P_{c}(R)\to R/P_{c-1}(R)\to \cdots \to R/P_{c+1-m}(R)\to R/P_{c-m}(R)\simeq P}$、 どこ。 ${\displaystyle c\geq m\geq 1}$

特に、すべての非自明な有限p群は、 （辺 からなる）最大パスを定義する。${\displaystyle G>1}$${\displaystyle c=\mathrm {cl} _{p}(G)}$

${\displaystyle (8)\qquad G\simeq G/1=G/P_{c}(G)\to \pi (G)=G/P_{c-1}(G)\to \pi ^{2}(G)=G/P_{c-2}(G)\to \cdots }$

${\displaystyle \cdots \to \pi ^{c-1}(G)=G/P_{1}(G)\to \pi ^{c}(G)=G/P_{0}(G)=G/G\simeq 1}$

は自明な群 で終わります。 の最大経路の最後から 2 番目の商は、階数 の基本アーベルp群です。ここで、は の生成元階数を表します。 ${\displaystyle \pi ^{c}(G)=1}$${\displaystyle G}$${\displaystyle \pi ^{c-1}(G)=G/P_{1}(G)\simeq C_{p}^{d}}$${\displaystyle d=d(G)}$${\displaystyle d(G)=\dim _{\mathbb {F} _{p}}(H^{1}(G,\mathbb {F} _{p}))}$${\displaystyle G}$

一般に、頂点の子孫木は、 ルートから始まる のすべての子孫の部分木です。自明群の最大可能子孫木には、すべての有限p群が含まれ、例外的です。これは、自明群が、その直接の子孫として、さまざまな生成子階数を持つ無限個の基本アーベルp群すべてを持つためです。ただし、任意の非自明な有限p群 ( で割り切れる位数) は、直接の子孫を有限個しか持ちません。 ${\displaystyle {\mathcal {T}}(G)}$ ${\displaystyle G}$${\displaystyle G}$ ${\displaystyle G}$${\displaystyle {\mathcal {T}}(1)}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle d\geq 1}$${\displaystyle p}$

を生成元 を持つ有限p群とします。私たちの目標は、 の非同型な直系の子孫の完全なリストをコンパイルすることです。すべての直系の子孫は、のp被覆群と 呼ばれる特定の拡張の商として取得でき、次のように構築できること がわかります。${\displaystyle G}$${\displaystyle d}$ ${\displaystyle G}$${\displaystyle G^{\ast }}$${\displaystyle G}$${\displaystyle G}$

正確なシーケンスの形でのプレゼンテーションを確かに見つけることができます${\displaystyle G}$

${\displaystyle (9)\qquad 1\longrightarrow R\longrightarrow F\longrightarrow G\longrightarrow 1}$、

ここで、 は生成元を持つ自由群を表し、 は核 を持つエピモーフィズムです。すると、 はの定義関係からなるの正規部分群になります。元とについては、共役、したがって交換子もに含まれます。したがって、は の特性部分群であり、のp乗法子は、以下の理由から、基本アーベルp群です。 ${\displaystyle F}$${\displaystyle d}$${\displaystyle \vartheta :\ F\longrightarrow G}$${\displaystyle R:=\ker(\vartheta )}$${\displaystyle R\triangleleft F}$${\displaystyle F}$${\displaystyle G\simeq F/R}$${\displaystyle r\in R}$${\displaystyle f\in F}$${\displaystyle f^{-1}rf\in R}$${\displaystyle \lbrack r,f\rbrack =r^{-1}f^{-1}rf\in R}$${\displaystyle R}$${\displaystyle R^{\ast }:=\lbrack R,F\rbrack \cdot R^{p}}$${\displaystyle R}$ ${\displaystyle R/R^{\ast }}$${\displaystyle G}$

${\displaystyle (10)\qquad \lbrack R,R\rbrack \cdot R^{p}\leq \lbrack R,F\rbrack \cdot R^{p}=R^{\ast }}$。

ここで、のp被覆群を次のように 定義できる。${\displaystyle G}$

${\displaystyle (11)\qquad G^{\ast }:=F/R^{\ast }}$、

そして正確な順序

${\displaystyle (12)\qquad 1\longrightarrow R/R^{\ast }\longrightarrow F/R^{\ast }\longrightarrow F/R\longrightarrow 1}$

は、基本的なアーベルp乗法子による拡張であることを示す。 ${\displaystyle G^{\ast }}$${\displaystyle G}$

${\displaystyle (13)\qquad \mu (G):=\dim _{\mathbb {F} _{p}}(R/R^{\ast })}$

のp乗数ランク。 ${\displaystyle G}$

ここで、割り当てられた有限p群がpクラスであると仮定しましょう。すると、条件とから、規則(R3)に従って、が成立し、の核を次のように 定義できます。${\displaystyle G\simeq F/R}$${\displaystyle \mathrm {cl} _{p}(G)=c}$${\displaystyle R\triangleleft F}$${\displaystyle \mathrm {cl} _{p}(F/R)=c}$${\displaystyle P_{c}(F)\leq R}$${\displaystyle G}$

${\displaystyle (14)\qquad P_{c}(G^{\ast })=P_{c}(F)\cdot R^{\ast }/R^{\ast }\leq R/R^{\ast }}$

p乗数の部分群として。その結果、核ランク

${\displaystyle (15)\qquad \nu (G):=\dim _{\mathbb {F} _{p}}(P_{c}(G^{\ast }))\leq \mu (G)}$

はp乗数ランクによって上から制限されます。 ${\displaystyle G}$

前と同様に、 を生成元を持つ有限p群とします。 ${\displaystyle G}$${\displaystyle d}$

命題。 任意のp元アーベル中心拡大

${\displaystyle (16)\qquad 1\to Z\to H\to G\to 1}$

のp基本アーベル部分群 で、がのp被覆群 の商となるもの。 ${\displaystyle G}$${\displaystyle Z\leq \zeta _{1}(H)}$${\displaystyle d(H)=d(G)=d}$${\displaystyle G^{\ast }}$${\displaystyle G}$

証拠については、右側の 「表示」をクリックしてください。

特に、の直系の子孫はp元アーベル中心拡大 である。${\displaystyle H}$${\displaystyle G}$

${\displaystyle (17)\qquad 1\to P_{c-1}(H)\to H\to G\to 1}$

の、以来 ${\displaystyle G}$

${\displaystyle 1=P_{c}(H)=\lbrack P_{c-1}(H),H\rbrack \cdot P_{c-1}(H)^{p}}$を意味し 、${\displaystyle P_{c-1}(H)^{p}=1}$${\displaystyle P_{c-1}(H)\leq \zeta _{1}(H)}$

どこ。 ${\displaystyle c=\mathrm {cl} _{p}(H)}$

定義。のp乗法子の 部分群は、の 直接の子孫へのエピモーフィズムの 核によって与えられる場合、許容されると呼ばれます。 ${\displaystyle M/R^{\ast }\leq R/R^{\ast }}$${\displaystyle G}$${\displaystyle M/R^{\ast }=\ker(\psi ^{\ast })}$${\displaystyle \psi ^{\ast }:\ G^{\ast }\to H}$${\displaystyle H}$${\displaystyle G}$

同等の特徴付けは、核を補う適切な部分群である。${\displaystyle 1<M/R^{\ast }<R/R^{\ast }}$

${\displaystyle (18)\qquad (M/R^{\ast })\cdot (P_{c}(F)\cdot R^{\ast }/R^{\ast })=R/R^{\ast }}$。

したがって、 のすべての直接の子孫のリストをコンパイルするという私たちの目標の最初の部分は、の核を補うのすべての許容される部分群を構築したときに完了します。ただし、一般に、リスト ${\displaystyle G}$${\displaystyle R/R^{\ast }}$${\displaystyle P_{c}(G^{\ast })=P_{c}(F)\cdot R^{\ast }/R^{\ast }}$${\displaystyle c=\mathrm {cl} _{p}(G)}$

${\displaystyle (19)\qquad \lbrace F/M\quad \mid \quad M/R^{\ast }\leq R/R^{\ast }{\text{ is allowable }}\rbrace }$、

ここで、 は、直下の子孫間の 同型性により冗長になります。${\displaystyle G^{\ast }/(M/R^{\ast })=(F/R^{\ast })/(M/R^{\ast })\simeq F/M}$${\displaystyle F/M_{1}\simeq F/M_{2}}$

2 つの許容される部分群と は、の対応する直接の子孫である商 が同型である場合に、同値であると呼ばれます。 ${\displaystyle M_{1}/R^{\ast }}$${\displaystyle M_{2}/R^{\ast }}$${\displaystyle F/M_{1}\simeq F/M_{2}}$${\displaystyle G}$

の直接の子孫間の同型性は、 という性質を持ち 、したがって の自己同型を誘導し、これは のp -被覆群の自己同型に拡張できます。 のp -乗法子 へのこの拡張された自己同型性の制限は 、 によって一意に決定されます。 ${\displaystyle \varphi :\ F/M_{1}\to F/M_{2}}$${\displaystyle G=F/R}$${\displaystyle c=\mathrm {cl} _{p}(G)}$${\displaystyle \varphi (R/M_{1})=\varphi (P_{c}(F/M_{1}))=P_{c}(\varphi (F/M_{1}))=P_{c}(F/M_{2})=R/M_{2}}$${\displaystyle \alpha \in \mathrm {Aut} (G)}$${\displaystyle G}$${\displaystyle \alpha ^{\ast }\in \mathrm {Aut} (G^{\ast })}$${\displaystyle G^{\ast }=F/R^{\ast }}$${\displaystyle G}$ ${\displaystyle \alpha ^{\ast }}$${\displaystyle R/R^{\ast }}$${\displaystyle G}$${\displaystyle \alpha }$

なので、各拡張自己同型は、許容される部分群の置換を誘導します。を、の自己同型によって誘導されるすべての置換によって生成される置換群と定義します。すると、写像 はエピモフィズムとなり、許容される部分群の同値類は、置換群の作用下での許容される部分群の軌道とまったく同じになります。 ${\displaystyle \alpha ^{\ast }(M/R^{\ast })\cdot P_{c}(F/R^{\ast })=\alpha ^{\ast }\lbrack M/R^{\ast }\cdot P_{c}(F/R^{\ast })\rbrack =\alpha ^{\ast }(R/R^{\ast })=R/R^{\ast }}$${\displaystyle \alpha ^{\ast }\in \mathrm {Aut} (G^{\ast })}$${\displaystyle \alpha ^{\prime }}$${\displaystyle M/R^{\ast }\leq R/R^{\ast }}$${\displaystyle P:=\langle \alpha ^{\prime }\mid \alpha \in \mathrm {Aut} (G)\rangle }$${\displaystyle G}$${\displaystyle \mathrm {Aut} (G)\to P}$${\displaystyle \alpha \mapsto \alpha ^{\prime }}$${\displaystyle M/R^{\ast }\leq R/R^{\ast }}$${\displaystyle P}$

最終的に、の作用下での の許容されるサブグループの各軌道の代表を選択すれば、のすべての直接の子孫のリストをコンパイルするという目標は達成されます。これはまさに、割り当てられたルートの子孫ツリーを構築するための再帰手順の 1 つのステップでpグループ生成アルゴリズムが行うことです。 ${\displaystyle \lbrace F/M_{i}\mid 1\leq i\leq N\rbrace }$${\displaystyle G}$${\displaystyle M_{i}/R^{\ast }}$${\displaystyle N}$${\displaystyle R/R^{\ast }}$${\displaystyle P}$

有限p群は、少なくとも 1 つの直接の子孫を持つ場合は可能(または拡張可能)と呼ばれ、そうでない場合は終端(または葉) と呼ばれます。の核ランクは、の能力に関する決定を許可します。 ${\displaystyle G}$${\displaystyle \nu (G)}$${\displaystyle G}$${\displaystyle G}$

• ${\displaystyle G}$が終端であるのは、 の場合のみです。${\displaystyle \nu (G)=0}$
• ${\displaystyle G}$は、 の場合に限り可能です。${\displaystyle \nu (G)\geq 1}$

能力の場合、には、 p乗数内の対応する許容サブグループのインデックスに応じて、異なるステップ サイズの直接の子孫があります。が の位数である場合、ステップ サイズ の直接の子孫は の位数になります。 ${\displaystyle G=F/R}$${\displaystyle \nu =\nu (G)}$ ${\displaystyle 1\leq s\leq \nu }$${\displaystyle (R/R^{\ast }:M/R^{\ast })=p^{s}}$${\displaystyle M/R^{\ast }}$${\displaystyle R/R^{\ast }}$${\displaystyle G}$${\displaystyle \vert G\vert =p^{n}}$${\displaystyle s}$${\displaystyle \#(F/M)=(F/R^{\ast }:M/R^{\ast })=(F/R^{\ast }:R/R^{\ast })\cdot (R/R^{\ast }:M/R^{\ast })}$ ${\displaystyle =\#(F/R)\cdot p^{s}=\vert G\vert \cdot p^{s}=p^{n}\cdot p^{s}=p^{n+s}}$

核ランクを持つ頂点における子孫ツリーの多重分岐の関連現象については、子孫ツリーに関する記事を参照してください。 ${\displaystyle G}$${\displaystyle \nu (G)\geq 2}$

pグループ生成アルゴリズムは、直接の子孫の構築を単一の固定ステップ サイズのものに制限する柔軟性を提供します。これは、子孫の数が非常に多い場合に非常に便利です (次のセクションを参照)。 ${\displaystyle 1\leq s\leq \nu }$

のすべての直接の子孫、ステップ サイズ の直接の子孫 の数をそれぞれ、で表します。すると が得られます。具体的な例として、 SmallGroups識別子を使用して、直接の子孫の広範なセットを持つ興味深い有限メタベルp群をいくつか示し、さらに、コンピュータ代数システム GAP および MAGMA のp群生成アルゴリズムの実際の実装で与えられる通常の形式で、可能な直接の子孫の数を示します。 ${\displaystyle s}$${\displaystyle G}$${\displaystyle N}$${\displaystyle N_{s}}$${\displaystyle N=\sum _{s=1}^{\nu }\,N_{s}}$${\displaystyle 0\leq C_{s}\leq N_{s}}$${\displaystyle (N_{1}/C_{1};\ldots ;N_{\nu }/C_{\nu })}$

まず、 とします。 ${\displaystyle p=3}$

まず、 型のアーベル化を持つ群から始めます。子孫ツリーに関する記事の図 4 を参照してください。 ${\displaystyle (3,3)}$

• 同クラスのグループには、ランク、および子孫数、があります。${\displaystyle \langle 27,3\rangle }$${\displaystyle 1}$${\displaystyle \nu =2}$${\displaystyle \mu =4}$${\displaystyle (4/1;7/5)}$${\displaystyle N=11}$
• 同クラスのグループには、ランク、および子孫数、があります。${\displaystyle \langle 243,3\rangle =\langle 27,3\rangle -\#2;1}$${\displaystyle 2}$${\displaystyle \nu =2}$${\displaystyle \mu =4}$${\displaystyle (10/6;15/15)}$${\displaystyle N=25}$
• その直接の子孫の 1 つであるグループ には、ランク、および子孫番号、があります。${\displaystyle \langle 729,40\rangle =\langle 243,3\rangle -\#1;7}$${\displaystyle \nu =2}$${\displaystyle \mu =5}$${\displaystyle (16/2;27/4)}$${\displaystyle N=43}$

対照的に、型のアーベル化を持つ群は、部分的に計算可能性の限界を超えて配置されます。 ${\displaystyle (3,3,3)}$

• 同クラスのグループには、ランク、および子孫数、があります。${\displaystyle \langle 81,12\rangle }$${\displaystyle 2}$${\displaystyle \nu =2}$${\displaystyle \mu =7}$${\displaystyle (10/2;100/50)}$${\displaystyle N=110}$
• 同クラスのグループにはランクがあり、子孫の数は不明です。${\displaystyle \langle 243,37\rangle }$${\displaystyle 3}$${\displaystyle \nu =5}$${\displaystyle \mu =9}$${\displaystyle (35/3;2783/186;81711/10202;350652/202266;\ldots )}$${\displaystyle N>4\cdot 10^{5}}$
• 同クラスのグループにはランクがあり、子孫の数は不明です。${\displaystyle \langle 729,122\rangle }$${\displaystyle 4}$${\displaystyle \nu =8}$${\displaystyle \mu =11}$${\displaystyle (45/3;117919/1377;\ldots )}$${\displaystyle N>10^{5}}$