Conteggio di elementi di una data lunghezza in un gruppo tramite GAP
Ho un gruppo G finitamente presentato in GAP, ad esempio con i seguenti generatori e relazioni: generatori = $[ f1, f2, f3, f4 ]$ relatori = $[ 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 ]$
Domanda: come posso contare il numero di elementi G che hanno lunghezza uguale a $i$ (il che significa che l'elemento è un prodotto diverso da zero in G di esattamente $i$ generatori $f_i$ in modo minimale)?
Risposte
Questo non può essere fatto per gruppi finitamente presentati in generale, perché ci sono gruppi con problemi di parole indecidibili. Ma per possibilmente infiniti gruppi finitamente presentati che sono automatici shortlex o hanno sistemi di riscrittura completi, puoi usare il pacchetto KBMAG per farlo.
Ecco un semplice esempio con un infinito gruppo di 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);;
Puoi usare la funzione $\mathsf{EnumerateReducedWords}$per elencare shortlex meno rappresentanti degli elementi del gruppo di lunghezza specificata. Quindi, ad esempio,
gap> Length(EnumerateReducedWords(R,0,3));
16
gap> Length(EnumerateReducedWords(R,4,4));
9
ci dice che ci sono 16 elementi di lunghezza da 0 a 3 e 9 elementi di lunghezza esattamente 4.
Puoi anche calcolare l'esatta funzione di crescita del gruppo come funzione razionale.
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)
I coefficienti $a_n$ dell'espansione della serie Taylor $\sum_{n=0}^\infty a_nx^n$ di questo darebbe il numero di elementi di lunghezza $n$, ma non so se GAP abbia una funzione per calcolare espansioni in serie.
Se il tuo gruppo è sufficientemente piccolo (come è il tuo esempio), e puoi convertirlo in un gruppo di permutazione, puoi usare 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 ]
Quindi ci sono 4 elementi di lunghezza 1, 9 di lunghezza 2 e così via.
Se il gruppo è molto più grande (quindi memorizzare gli elemnts è difficile) o addirittura infinito, questo è un problema molto più difficile.