On the growth functions of finite two generator burnside groups of exponent five.pdf Одним из важных инструментов для определения строения группы является изучение её роста относительно фиксированного порождающего множества. Пусть G = {X}. Шаром Ks радиуса s группы G будем называть множество всех её элементов, которые могут быть представлены в виде групповых слов в алфавите X длиной не больше s. Для каждого целого неотрицательного s можно определить функцию роста группы F(s), которая равна числу элементов группы G относительно X, представимых в виде несократимых групповых слов длиной s. Таким образом, F(0) = |Ko| = 1, F(s) = |Ks| - |Ks_1| при s Е N. Как правило, функцию роста конечной группы представляют в виде таблицы, в которую записывают ненулевые значения F(s). Пусть F(s0) > 0, но F(s0 + 1) = 0, тогда s0 является диаметром графа Кэли группы G в алфавите порождающих X, который будем обозначать Dx (G). Вычисление функции роста произвольной конечной группы является хотя и разрешимой, но весьма сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова элемента группы, как показали С. Ивен и О. Голдрейх [1], является NP-трудной. Пусть B0(2, 5) = (a1,a2) -максимальная конечная двупорождённая бернсайдова группа периода 5, порядок которой равен 534 [2]. Используя систему компьютерной алгебры GAP, нетрудно получить pc-представление (power commutator presentation) данной группы [3, 4]. В этом случае каждый элемент g G B0(2, 5) записывается в виде уникального упорядоченного произведения базисных коммутаторов в определённых степенях: Vg G Bo(2, 5) (g = a?1 ■ a^2 ■ ... ■ a^34, ai G Z5, i = 1, 2,..., 34). Здесь коммутаторы a1 и a2 являются порождающими элементами группы, а последующие- a3,..., a34 -определяются рекурсивно через a1 и a2 [2]. Обозначим через Bk фактор-группу группы B0(2, 5) следующего вида: Bk = Bo(2,5)/(ak+1,.. .,a34). Очевидно, что \Bk\ = 5k и Vg G Bk (g = a?1 ■ aO,2 ■ ... ■ aakk). К. А. Филипповым в [5] вычислена функция роста группы B14 в алфавите A2 = = {a\_,a2}. Аналогичная задача для симметричного порождающего множества A4 = = {a1, a-1, a2, a-1} решена Ч. Симсом [6]. В обоих случаях решение было получено при помощи длительных компьютерных вычислений. Одной из причин интереса исследователей к функциям роста Bk является то, что получаемая информация может оказаться полезной при решении открытой проблемы о конечности B(2, 5) - свободной двупорождённой бернсайдовой группы периода 5. Дальнейшее изучение функций роста групп Bk для k > 14 сталкивается с серьёзными вычислительными трудностями ввиду их больших порядков. Настоящая работа посвящена разработке эффективного алгоритма для вычисления функций роста указанных групп, который бы дал возможность преодолеть существующий барьер. За основу взят алгоритм, описанный в [7]. Для быстрого умножения элементов группы использовались полиномы Холла, полученные в [8]. Введён новый метод упорядочивания элементов, который позволил значительно повысить быстродействие. Модифицированный алгоритм реализован на 4-процессорном компьютере (на каждом по 16 ядер) с общей памятью объемом 256 Гб. В результате вычислены функции роста групп Bk для k = 15, 16 и 17. В таблице приведены значения диаметров графов Кэли групп Bk, полученные в настоящей работе, а также уже известные; на рис. 1 и 2 приведены графики роста функций Bk. k 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 DA2 (Bk) 8 10 13 20 20 25 30 31 32 35 40 40 45 46 50 55 Da^ (Bk) 4 6 9 10 13 15 19 20 20 24 26 28 30 30 33 34 Рис. 1. Графики функций роста групп Вд в алфавите A2 Рис. 2. Графики функций роста групп Вд в алфавите A4

Скачать электронную версию публикации