Вычислительные эксперименты в конечных двупорождённых бернсайдовых группах периода 5 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/60

Вычислительные эксперименты в конечных двупорождённых бернсайдовых группах периода 5

Пусть B0(2, 5) = (a1,a2) - наибольшая конечная двупорождённая бернсайдова группа периода 5, порядок которой равен 534. Для каждого элемента данной группы существует единственное представление вида a^1 • a^2 • ... • a044, где од G Z5, i = 1, 2,..., 34. Здесь a1 и a2 - порождающие элементы B0(2, 5), a3,..., a34 - коммутаторы, которые вычисляются рекурсивно через ai и a2. Определим факторгруппу группы B0(2, 5) следующего вида: B = B0(2, 5)/(afc+1,..., a34). Очевидно, что |Bfc | = 5k. На основе проведённых вычислительных экспериментов сформулирована гипотеза о диаметре группы B для симметричного порождающего множества {a1, a-1, a2, a-1}.

Computational experiments in finite two generator burnside groups of exponent five.pdf Настоящая работа продолжает исследования, начатые в [1, 2], которые посвящены разработке алгоритмов для исследования роста в конечных двупорождённых группах периода 5. В [1] основной упор сделан на создании алгоритмов минимальной вычислительной сложности, а в [2] разработан ресурсно-эффективный алгоритм, который имеет низкую пространственную сложность и сохраняет вычислительную сложность на приемлемом уровне. Напомним основные определения [1]. Пусть G = (X). Шаром Ks радиуса s группы G будем называть множество всех её элементов, которые могут быть представлены в алфавите X в виде несократимых групповых слов длины не больше s. Все элементы одинаковой длины i образуют сферу Pj радиуса i. Единица группы e является пустым s словом, длина которого равна нулю. Согласно данным определениям, Ks = (J Pj. j=0 Для каждого целого неотрицательного i можно определить (сферическую) функцию роста группы F(G), которую будем записывать в виде вектора F(G) = = (F0, F1,... , Fj,...), где Fj = |Pj|. Пусть Fs0 > 0, но Fs0+1 = 0, тогда s0 является диаметром графа Кэли группы G в алфавите порождающих X, который будем обо_1 so значать (G). Средний диаметр (G) равен -- £ sFs. | G| s=0 Заметим, что решение некоторых задач теории кодирования и криптографии сводится к исследованию соответствующих графов Кэли. Например, открытая проблема эффективного восстановления вершин в графе Хэмминга является одной из таких задач [3]. Кратко опишем алгоритмы из [1, 2]. Алгоритм 1 вычисляет шар Ks фиксированного радиуса s произвольной конечной группы G, заданной порождающим множеством X. Данный алгоритм имеет низкую вычислительную сложность, однако при его реализации каждый элемент группы необходимо хранить в памяти компьютера, и если группа имеет большой порядок, то применение алгоритма 1 становится невозможным. Пусть p - гомоморфизм G на группу Q и N - ядро p, т.е. Q = G/N. По аналогии с группой, для каждого смежного класса qN определим сферу Pi(q), шар Ks(q) и функцию роста Fi(q): Pi(q) = {g : g e Pi и p(g) = q}, Ks(q) = J Pl(q)) F,(q) = |Pi(q)|. i=0 Пусть Fd(q) > 0, но Fd+i(q) = 0, тогда d будем называть диаметром смежного класса qN и обозначать DX (qN). Если Q - сравнительно большая группа, то множество K2s(q) будет значительно меньше, чем K2s(G). Данный факт взят за основу построения алгоритма 2, который, получив на входе шар Ks группы G радиуса s, фактор-группу Q = G/N и некоторый элемент q е Q, возвращает функцию роста F(q) = (F0 (q),... , F2s(q)) для шара K2s(q) смежного класса qN радиуса 2s. Объединив алгоритмы 1 и 2, получим алгоритм 3, который вычисляет функцию роста F(G) = F(q) шара K2s фиксированного радиуса 2s произвольной конечной qeQ группы G, заданной порождающим множеством X. Пусть B0(2, 5) = (a1,a2) -максимальная конечная двупорождённая бернсайдова группа периода 5, порядок которой равен 534 [4]. При помощи системы компьютерной алгебры GAP легко получить коммутаторное представление данной группы [5]. В этом случае каждый элемент g е B0(2, 5) может быть однозначно записан в виде a^1 ■ a^2 ■ ■... ■ aO,^, где ai е Z5 и i =1, 2,..., 34. Здесь a1 и a2 - порождающие элементы B0(2, 5); a3,... , a34 - коммутаторы, которые вычисляются рекурсивно через a1 и a2 [4]. Определим фактор-группу Bk = B0(2,5)/(ak+1,... ,a34). Очевидно, что |Bk| = 5k и g = a^1 ■ a^2 ■ ... ■ ac^k для всех g е Bk. Пусть A4 = {a1, a-1, a2, a-1} - симметричное порождающее множество групп Bk. Отметим, что на сегодняшний день при помощи компьютерных вычислений удалось получить функции роста групп Bk при k ^ 19 [1, 2]. В настоящее время ведутся расчёты функции роста группы B20 = (A4) по алгоритму 3, при этом s = 20, Q = B10 и N = (an,... ,a20). При суммировании получаемых функций роста F(q) смежных классов qN отмечено, что, начиная с некоторого шага (не более 10% от порядка группы), промежуточные функции роста группы F(B20) сохраняют области возрастания и убывания. Рис. 1 наглядно отражает данный факт. Вычислительные эксперименты в группах Bk при k ^ 19 показали, что и в них промежуточные функции роста ведут себя аналогично. Кроме того, выяснилось, что при k ^ 19 смежный класс eNk всегда включает слова максимальной длины группы, на основании чего можно сформулировать гипотезу для всех 2 ^ k ^ 34: Гипотеза 1. DAi(eNk) = DAi(Bk), где |Nk| - |Qk| - B|1/2. 1 II _(1_1_ ' 1 1 1 1 1 /Н ! h l \\ 1 > 11 ' ■■/ 14 i .с1! U 1 ! Ч 1 , ч] 4 ji ' 0--Ч ll ' ' \\ l" /V/ /А ф а I !, -0- 4- е -d - .0-1.-04 L „--б- 1 1 li 0 t-B-i 0 2 4 6 8 10 12 14 16 18 20 22 24 26 2Э 30 32 34 36 38 40 Длина Рис. 1. Промежуточные функции роста F(B20) Результаты вычислительных экспериментов в группах Bk при 20 ^ k ^ 25 представлены в таблице. k 20 21 22 23 24 25 Da4 (eNk) 38 39 41 44 44 46 Если гипотеза верна, то значения диаметров смежных классов eNk в таблице равны диаметрам соответствующих групп Bk относительно порождающего множества A4.

Ключевые слова

функция роста группы, группа Бернсайда, Burnside group, the growth function

Авторы

ФИООрганизацияДополнительноE-mail
Кузнецов Александр АлексеевичСибирский государственный университет науки и технологий им. акад. М.Ф. Решетнёвадоктор физико-математических наук, профессор, директор институтаalex_kuznetsov80@mail.ru
Всего: 1

Ссылки

Кузнецов А. А. Об одном алгоритме вычисления функций роста в конечных двупорождён-ных группах периода 5 // Прикладная дискретная математика. 2016. №3(33). C. 116-125.
Кузнецов А. А., Кузнецова А. С. Ресурсно-эффективный алгоритм для исследования роста в конечных двупорождённых группах периода 5 // Прикладная дискретная математика. 2018. №42. C. 94-103.
Константинова Е. В. Комбинаторные задачи на графах Кэли. Новосибирск: НГУ, 2010. 110 с.
Havas G., Wall G., and Wamsley J. The two generator restricted Burnside group of exponent five // Bull. Austral. Math. Soc. 1974. No. 10. P. 459-470.
Sims C. Computation with Finitely Presented Groups. Cambridge: Cambridge University Press, 1994. 628 p.
 Вычислительные эксперименты в конечных двупорождённых бернсайдовых группах периода 5 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/60

Вычислительные эксперименты в конечных двупорождённых бернсайдовых группах периода 5 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/60