GAPを介してグループ内の特定の長さの要素をカウントする

Question

たとえば、次のジェネレーターとリレーションを使用して、GAPに有限で提示されたグループGがあります。 $[ f1, f2, f3, f4 ]$ relators = $[ f1^2, f2^2, f3^2, f4^2, (f3*f2)^2, (f2*f1)^3, (f1*f4)^3, (f3*f1)^3, (f4*f3)^3, (f2*f4)^3 ]$

質問：長さが等しい要素Gの数を数えるにはどうすればよいですか？ $i$ （これは、要素が正確にGのゼロ以外の積であることを意味します $i$ 発電機 $f_i$ 最小限の方法で）？

Answer 1

決定不可能な文章題を持つグループがあるため、これは一般に有限表示グループに対しては実行できません。ただし、shortlex自動であるか、完全な書き換えシステムを備えている、無限に無限に提示される可能性のあるグループの場合は、KBMAGパッケージを使用してこれを行うことができます。

これは、無限のコクセター群を使用した簡単な例です。

gap> LoadPackage("kbmag");
true
gap> F := FreeGroup(3);;
gap> G := F/[F.1^2, F.2^2, F.3^2, (F.1*F.2)^2, (F.1*F.3)^3, (F.2*F.3)^7];;
gap> R := KBMAGRewritingSystem(G);;
gap> A := AutomaticStructure(R);;

あなたは機能を使うことができます $\mathsf{EnumerateReducedWords}$指定された長さのグループ要素のshortlex最小代表をリストします。だから、例えば、

gap> Length(EnumerateReducedWords(R,0,3));
16
gap> Length(EnumerateReducedWords(R,4,4));
9

長さ0から3の16個の要素と、正確に4個の長さの9個の要素があることを示しています。

グループの正確な成長関数を有理関数として計算することもできます。

gap> GrowthFunction(R);
(x_1^10+4*x_1^9+8*x_1^8+11*x_1^7+12*x_1^6+12*x_1^5+12*x_1^4+11*x_1^3+8*x_1^2+4\
*x_1+1)/(x_1^10+x_1^9-x_1^7-x_1^6-x_1^5-x_1^4-x_1^3+x_1+1)

係数 $a_n$ テイラー級数展開の $\sum_{n=0}^\infty a_nx^n$ これの長さの要素の数を与えるだろう $n$、しかし、GAPに級数展開を計算する機能があるかどうかはわかりません。

Answer 2

グループが十分に小さく（例のように）、順列グループに変換できる場合は、次を使用できますGrowthFunctionOfGroup。

gap> p:=Image(IsomorphismPermGroup(G));
Group([ (2,3)(4,5)(6,8), (1,2)(5,7)(8,9), (2,4)(3,5)(9,10), (4,6)(5,8)(7,9) ])
gap> GrowthFunctionOfGroup(p);
[ 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1 ]

したがって、長さ1の4つの要素、長さ2の9、というようになります。

グループがはるかに大きい場合（したがって、要素を格納するのが難しい場合）、または無限でさえある場合、これははるかに難しい問題です。