Подсчет элементов заданной длины в группе через GAP
У меня есть конечно представленная группа G в GAP, например, со следующими генераторами и отношениями: генераторы = $[ 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$ минимально)?
Ответы
Это невозможно сделать для конечно определенных групп вообще, потому что есть группы с неразрешимыми проблемами слов. Но для возможно бесконечных конечно представленных групп, которые являются короткими автоматическими или имеют полную систему перезаписи, вы можете использовать пакет 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}$для составления краткого списка наименьших представителей групповых элементов заданной длины. Так, например,
gap> Length(EnumerateReducedWords(R,0,3));
16
gap> Length(EnumerateReducedWords(R,4,4));
9
сообщает нам, что существует 16 элементов длиной от 0 до 3 и 9 элементов длиной ровно 4.
Вы также можете вычислить точную функцию роста группы как рациональную функцию.
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 функция для вычисления расширений рядов.
Если ваша группа достаточно мала (как ваш пример), и вы можете преобразовать в группу перестановок, вы можете использовать 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 ]
Итак, есть 4 элемента длиной 1, 9 - длиной 2 и так далее.
Если группа намного больше (поэтому хранить элементы сложно) или даже бесконечна, это гораздо более сложная проблема.