GAP를 통해 그룹에서 주어진 길이의 요소 계산

Question

예를 들어 다음 생성자 및 관계와 함께 GAP에 유한하게 표시된 그룹 G가 있습니다. generators = $[ f1, f2, f3, f4 ]$ 관계자 = $[ 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에서 0이 아닌 곱임을 의미합니다. $i$ 발전기 $f_i$ 최소한으로)?

Answer 1

결정 불가능한 단어 문제가있는 그룹이 있기 때문에 유한하게 제시된 그룹에 대해서는 일반적으로 수행 할 수 없습니다. 그러나 shortlex 자동이거나 완전한 재 작성 시스템이있는 무한한 유한 제시 그룹의 경우 KBMAG 패키지를 사용하여이를 수행 할 수 있습니다.

다음은 무한한 Coxeter 그룹의 쉬운 예입니다.

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$ Taylor 시리즈 확장의 $\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 개 등이 있습니다.

그룹이 훨씬 크거나 (따라서 요소를 저장하는 것이 어렵습니다) 무한한 경우, 이것은 훨씬 더 어려운 문제입니다.