Menghitung elemen dengan panjang tertentu dalam grup melalui GAP

Question

Saya memiliki grup G yang disajikan dengan baik di GAP, misalnya dengan generator dan relasi berikut: generator = $[ f1, f2, f3, f4 ]$ relator = $[ 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 ]$

Pertanyaan: Bagaimana cara menghitung jumlah elemen G yang memiliki panjang yang sama $i$ (yang berarti bahwa elemen tersebut adalah hasil perkalian bukan nol di G tepatnya $i$ generator $f_i$ dengan cara minimal)?

Answer 1

Hal ini tidak dapat dilakukan untuk kelompok yang disajikan dengan sempurna secara umum, karena ada kelompok dengan masalah kata yang tidak dapat diputuskan. Tetapi untuk grup yang disajikan tanpa batas dan mungkin shortlex otomatis atau memiliki sistem penulisan ulang lengkap, Anda dapat menggunakan paket KBMAG untuk melakukan ini.

Berikut adalah contoh mudah dengan grup Coxeter tak terbatas.

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);;

Anda bisa menggunakan fungsinya $\mathsf{EnumerateReducedWords}$untuk membuat daftar perwakilan terkecil dari elemen kelompok dengan panjang tertentu. Misalnya,

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

memberitahu kita bahwa ada 16 elemen dengan panjang 0 sampai 3, dan 9 elemen dengan panjang tepat 4.

Anda juga dapat menghitung fungsi pertumbuhan yang tepat dari grup sebagai fungsi rasional.

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)

Koefisien $a_n$ dari ekspansi seri Taylor $\sum_{n=0}^\infty a_nx^n$ dari ini akan memberikan jumlah elemen panjang $n$, tapi saya tidak tahu apakah GAP memiliki fungsi untuk menghitung ekspansi seri.

Answer 2

Jika grup Anda cukup kecil (seperti contoh Anda), dan Anda dapat mengubahnya menjadi grup permutasi, Anda dapat menggunakan 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 ]

Jadi ada 4 elemen dengan panjang 1, 9 dengan panjang 2, dan seterusnya.

Jika grupnya jauh lebih besar (jadi sulit menyimpan elemen) atau bahkan tidak terbatas, ini adalah masalah yang jauh lebih sulit.