ИССЛЕДОВАНИЕ ФУНКЦИЙ РОСТА В КОНЕЧНЫХ ДВУПОРОЖДЕННЫХ ГРУППАХ ПЕРИОДА 5

Полный текст

Пусть B0(2,5, k) - максимальная конечная двупо-рожденная бернсайдова группа периода 5 ступени нильпотентности k. В данном классе групп наибольшей является группа B0 (2,5,12), порядок которой равен 534 [1]. Положим {a1, a2} - порождающие элементы B0 (2,5, k). В [2] было начато исследование функций роста в группах B0 (2,5, k). Относительно порождающего множества {a1, a-1a2, a-1} вычислены указанные характеристики групп для k < 5 . Настоящая работа является логичным продолжением [2]. В ней будут представлены результаты вычислений функций роста указанных групп для порождающего множества А = {a1, a2} при k < 5 . Функция роста группы B0(2,5,6) относительно А получена К. А. Филипповым в работе [3]. Для вычисления функции роста и диаметра графа Кэли относительно А необходимо перечислить все элементы группы в формате минимальных слов [4]. Вычислив количество слов на каждой длине, можно будет получить функцию роста группы, а максимально возможная длина минимальных слов будет являться диаметром Кэли группы. Отметим, что для случаев k = 2, 3, 4, 5 были использованы компьютерные вычисления, основанные на алгоритме из разд. 1. Рассматриваемая задача помимо фундаментально -го значения, имеет также и приложения, например, при проектировании компьютерных вычислительных сетей [5]. Сеть процессоров может быть представлена как неориентированный граф, в котором процессоры являются вершинами, а две вершины графа соединены ребром, если имеется прямое соединение между соответствующими процессорами. С одной стороны, желательно, чтобы между процессорами было как можно меньше соединений, а с другой, обмен данными между процессорами предпочтительно производить с наименьшим числом посредников. Очевидно, эти два критерия противоречат друг другу. На теоретико-групповом языке диаметр графа вычислительной сети будет равен максимальной длине минимальных слов соответствующей графу группы. Описание алгоритма вычисления функции роста группы. Пусть p - простое число, а G - конечная группа экспоненты p. Это значит, что gp = 1 для всех g є G. Положим А = {a1, a2} - порождающие элементы G. На множестве А введем отношение порядка «-С» (меньше): ах<а2. Пусть g элемент из G. Тогда его можно представить в виде конечного произведения из порождающих, т. е. , g = a1 -a2 •...-as, где ai єА, правую часть данного равенства мы будем называть словом и записывать v = a1a2...as. Натуральное число s будем называть длиной слова v. 58 Математика, механика, информатика Функция L(v) определена на множестве всех слов и равна длине слова v, т. е. L(v) = s для слова v, указанного выше. Единица группы e будет представлена пустым словом, которое мы будем обозначать є. По определению, длина пустого слова равна 0. Определение отношения порядка на множестве слов. Будем говорить, что слово v меньше слова w и записывать это как v X w , если имеет место одно из следующих утверждений: 1. L(v) < L(w); 2. Если L(w) = L(v), тогда пусть v = aja2...as и w = P1P2...PS, a1 = P1, a2 = P2, ak-1 = Pk-1, ak < Pk для некоторого 1 < k < s. Определение минимально2о слова. Слово v будем называть минимальным в G относительно введенного порядка, если для любого другого слова w, удовлетворяющего условию gv = gw, будет выполняться v X w. Так как G нильпотентна, то мы можем найти цепочку подгрупп Gi (1 < i < n), обладающих следующими свойствами: G = G1 ^ G2 ^ ^ Gn ^ Gn+1 = e, Gi нормальны в G, а факторы Gi / Gi+1 имеют порядок p и лежат в центре G / Gi+1. Пусть для 1 < i < n элемент ai є Gi, но ai £ Gi+1, тогда каждый элемент группы g є G может однозначным образом записан в виде g = aj71 a]2 - a'ln ,0 <y< p. (1.1) Такое представление элементов группы (pc-представление), можно получить при помощи алгоритма известного как p-quotient algorithm [6]. Он реализован в системах компьютерной алгебры GAP и Magma. Если А - порождающее множество группы G, то любой ее элемент, записанный в виде слова aa as, где ai єА, можно преобразовать к виду (1): aja2 — as ^ a^1 a^2 — a, 'In ( 2) 4. Если 5. Если pq 3. Для vi є V vi ^ w. Если w £ Qs, то Ks = Ks u v , Qs = Qs U w, T = T u v . fi < |V|, то i = i +1, переход в 3; [i = |V|, то переход в 5. [T ^0, то переход в пункт 2; [T = 0, то переход в пункт 6. 6. Диаметр G равен s -1, Ks-1(G) - множество всех минимальных слов группы. Функция роста задается формулой f (j) =| K}- (G) | -1 K^ (G) | (1 < j < s -1). 7. Завершение работы алгоритма. Группа В0 (2,5,1). Данная группа представляет собой элементарную абелеву группу, порядок которой равен 52. Нетрудно вычислить функцию роста данной группы и диаметр Кэли (см. табл. 1). Справедлива следующая Теорема 1. Относительно порождающего множества А группа В0 (2,5,1) имеет диаметр Кэли, равный 8, а функция роста задана табл. 1. Доказательство. Очевидно. Таблица 1 Функция роста группы B0(2,5,1) Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов 0 1 3 4 6 3 1 2 4 5 7 2 2 3 5 4 8 1 |В0(2,5,1)| = 52 = 25 Процедура (2) дает возможность решить проблему равенства слов в G. На ее основе мы можем перечислить элементы G в формате минимальных слов. Обозначим через Ks (G) множество всех минимальных слов группы G, не превосходящих по длине s. Множество Qs (G) - элементы Ks (G), записанные в виде правой части (2). Пустое слово - единицу группы обозначим e. Пусть s0 є N - минимальное число, для которого выполняется Ks0(G) = Kso+j(G). В этом случае s0 будет являться диаметром Кэли группы G. Опишем алгоритм, вычисляющий Ks : 1. s = 0, K0 = {є}, Q0 = {e}, T = K0. 2. s = s +1, Ks = Ks-!, Qs = Qs-1, V = a{T U a2T , T = 0 , i = 1. Группа B0 (2,5,2). Любой элемент группы B0 (2,5,2) представим в виде нормального коммутаторного слова [1]: g = a?1 a\2 aY3, у,- є Z5. Для умножения элементов, будем использовать полиномы Холла, полученные в [7]. Пусть aX1 aX2 a3X3 и a/1 aУ2 ap - два произвольных элемента в группе В0 (2,5,2), записанных в коммутаторном виде. Тогда их произведение равно aX1 a^2 a^3 ■ a/1 ap ap = af1 a^2 a33, где zi є Z5 и: z1 = X + Уи Z2 = X2 + У2, z3 = X3 + У3 + X2 У1. Применив алгоритм из разд. 1, получим функцию роста рассматриваемой группы (табл. 2). Имеет место Теорема 2. Относительно порождающе2о множества А 2руппа В0 (2,5,2) имеет диаметр Кэли, равный 10, а функция роста задана табл. 2. Доказательство. Следует из вычислений функции роста группы В0(2,5,2) по алгоритму из разд. 1. 59 Вестник СибГАУ. № 3(49). 2013 Таблица 2 Функция роста группы B0(2,5,2) Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов 0 1 3 8 6 23 9 10 1 2 4 15 7 21 10 4 2 4 5 20 8 17 ^(2,5,2) =53 =125 Таблица 3 Функция роста группы B0(2,5,3) Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов 0 1 6 56 12 487 18 12 1 2 7 100 13 438 19 4 2 4 8 166 14 343 20 2 3 8 9 262 15 222 4 16 10 370 16 112 5 30 11 455 17 34 B0(2,5,3)| = 55 = 3125 Группа B0(2,5,3). Каждый элемент группы B0 (2,5,3) представим в виде нормального коммутаторного слова g = a^ a]2 a|3 a{4 a|5, yi є Z5. Пусть ap1 ap2ap ap4a5:5 и a? apap a?4a|5 - два произвольных элемента в группе B0 (2,5,3) , записанных в коммутаторном виде. Тогда их произведение равно ap1 ap ap ap4 a5:5 ■ a?1 a?? ap a?4 ap = a^ a22 ap ap ap , где zi є Z5 и: z1 = X + ^, z2 = X2 + y2 , z3 = X3 + y3 + x2 УJ, f У ) z4 = x4 + ?4 + X2 I 2 1+ X3 , z5 = x5 + У5 + x2У У2 +| 2 IУ + X3У2 . Здесь и далее n! биномиальный коr !(n - r)! эффициент. Применив алгоритм из разд. 1, вычислим функцию роста группы B0(2,5,3) (табл. 3). Справедлива следующая Теорема 3. Относительно порождающего множества А группа B0(2,5,3) имеет диаметр Кэли, равный 20, а функция роста задана таблицей 3. Доказательство. Следует из вычислений функции роста группы B0(2,5,3) по алгоритму из разд. 1. Группа B0 (2, 5, 4). Каждый элемент группы B0 (2,5,4) представим в виде нормального коммутаторного слова Ї1 У? Y3 Y 4 Y5 Y6 Y7 Y' g = a1 a2 a-3 a44 a^5 a6 a7 a^' Yi :Z5. Пусть X1 X2 X3 X4 X5 X6 X7 X8 a11 a22 a35 a44 a55 a6 a77 a§ ap1 a? ap a?4 ap ap ap a8^8 - два произвольных элемента в группе B0 (2, 5, 4) , записанных в коммутаторном виде. Тогда их произведение равно ap1 ap2 ap ap4 ap ap ap ap8 ■ a?1 ap ap a?4 ap ap ap ap = a1ZJ a22 ap ap ap ap ap ap, где zt є Z5 и: z1 = X + ^, z2 = x2 + У2 , z3 = X3 + У3 + X2 ^, z4 = X4 + У4 + X2 I 2 1 + X3 ^, z5 = X5 + У5 + X2 УУ2 +| 2 | У + X3 У2 = z6 = X6 + У6 + X2 | 3 I + x У1 z7 = x7 + y7 + У1 + xn У1 y2 + + X3 У У2 + X4 У2 + X5 УJ, z8 = X8 + У8 +I 3 ІУ +I 2 IУУ2 + + x2 P У2 + X, У2 + X5 У2. и 60 Математика, механика, информатика Применив алгоритм из разд. 1, найдем функцию роста группы B0(2,5,4) (табл. 4). Теорема 4. Относительно порождающего множества А группа B0 (2,5,4) имеет диаметр Кэли, равный 30, а функция роста задана таблицей 4. Доказательство. Следует из вычислений функции роста группы B0(2,5,4) по алгоритму из разд. 1. Группа В0 (2,5,5). Аналогичным образом вычислим функцию роста группы B0 (2,5,5) (табл. 5). Справедлива следующая Теорема 5. В алфавите А группа B0(2,5,5) имеет диаметр Кэли, равный 32, а функция роста задана таблицей 5. Доказательство. Следует из вычислений функции роста группы B0(2,5,5) по алгоритму из разд. 1. Группа В0(2,5,6). К. А. Филиппов в работе [3] вычислил функцию роста группы B0 (2,5,6) (табл. 6). Таблица 4 Функция роста группы В0(2,5,4) Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов 0 1 8 214 16 21923 24 18448 1 2 9 410 17 31600 25 8706 2 4 10 784 18 41954 26 3256 3 8 11 1487 19 50670 27 812 4 16 12 2735 20 54460 28 152 5 30 13 4905 21 51399 29 52 6 58 14 8529 22 42862 30 26 7 112 15 14118 23 30892 |B0(2,5,4)| = 58 = 390 625 Таблица 5 Функция роста группы В0(2,5,5) Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов 0 1 9 410 18 126828 27 887095 1 2 10 784 19 229180 28 487974 2 4 11 1495 20 399742 29 179463 3 8 12 2845 21 658283 30 36089 4 16 13 5409 22 994274 31 3332 5 30 14 10271 23 1332692 32 116 6 58 15 19476 24 1533785 7 112 16 36732 25 1497003 8 214 17 68679 26 1253223 B0(2,5,5) = 510 = 9765625 Таблица 6 Функция роста группы В0(2,5,6) Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов Длина Кол-во слов 0 1 12 2847 24 6055431 36 831332170 1 2 13 5417 25 11319139 37 618248452 2 4 14 10303 26 21039700 38 367604796 3 8 15 19602 27 38795471 39 151894200 4 16 16 37254 28 70686385 40 34898104 5 30 17 70751 29 126432849 41 3181218 6 58 18 134224 30 219647100 42 69158 7 112 19 254321 31 364201879 43 800 8 214 20 481252 32 561801464 44 316 9 410 21 909349 33 779044350 45 158 10 784 22 1714866 34 936055279 11 1495 23 3226931 35 954336955 |B0(2,5,6)| = 514 = 6103515625

Об авторах

А. С. Кузнецова

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: alexakulch@rambler.ru
Россия, Красноярск, просп. им. газ. «Красноярский рабочий», 31

Список литературы

Дополнительные файлы