Об одном алгоритме вычисления функций роста в конечных двупорождённых группах периода 5 | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/10

Об одном алгоритме вычисления функций роста в конечных двупорождённых группах периода 5

Пусть B0(2, 5) = (ai,a2) -наибольшая конечная двупорождённая бернсайдова группа периода 5, порядок которой равен 5. Для каждого элемента данной ai ao группы существует уникальное коммутаторное представление вида ai • a2 • • ... • aQ4, где ai e Z5, i = 1,2,..., 34. Здесь a1 и a2 - порождающие элементы Bo(2, 5); аз,..., аз4 - коммутаторы, которые вычисляются рекурсивно через а1 и а2. Определим фактор-группу группы B0(2, 5) следующего вида: Bk = = Bo (2, 5)/(afc+i ,...,a34). Очевидно, что |Bk | = 5. Предложен новый алгоритм, при помощи которого вычислены функции роста Bk относительно порождающих множеств {a1,a2} и {а1, а-, а2, а-} для k = 15, 16, 17. На основе полученных данных вычислены диаметр и средний диаметр соответствующих графов Кэли.

An algorithm for computation of the growth functions in finite two-generated groups of exponent 5.pdf Введение Одним из важных инструментов для определения строения группы является изучение её роста относительно фиксированного порождающего множества. Пусть G = (X). Шаром Ks радиуса s группы G будем называть множество всех её элементов, которые могут быть представлены в виде групповых слов в алфавите X длины не больше s. Для каждого целого неотрицательного s можно определить функцию F(s) роста группы, которая равна числу элементов группы G относительно X, представимых в виде несократимых групповых слов длины s. Таким образом, F(0) = |Ко| = 1, F(s) = |Ks| - |Ks-i| при s e N. Как правило, функцию роста конечной группы представляют в виде таблицы, в которую записывают ненулевые значения F(s). К сожалению, вычисление функции роста большой конечной группы является хотя и разрешимой, но весьма сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова элемента группы, как показали С. Ивен и О. Голдрейх [1], является NP-трудной. Таким образом, в наихудшем случае количество элементарных операций, которые необходимо выполнить для решения указанной задачи, представляет собой экспоненциальную функцию от |X |. Отметим также, что при вычислении функции роста группы мы параллельно выясняем характеристики соответствующего графа Кэли, например диаметр и средний диаметр [2]. Пусть F(s0) > 0, но F(s0 + 1) = 0, тогда s0 является диаметром графа Кэли группы G в алфавите порождающих X, который будем обозначать Dx(G). _1 so Соответственно средний диаметр DX (G) равен -- £ s • F(s). |G| s=0 Как известно, благодаря своим замечательным свойствам графы Кэли нашли применение при моделировании топологий многопроцессорных вычислительных систем (МВС)-суперкомпьютеров [3], а также дата-центров [4]. И вполне возможно, что в недалёком будущем понадобятся знания о сверхбольших графах, которые будут востребованы при проектировании распределённых систем, пиковая производительность которых будет достигать 1 экзафлопс и выше. Одной из широко применяемых топологий МВС является k-мерный гиперкуб, который задаётся группой B(k, 2) - k-порождённой бернсайдовой группой периода 2. Группа B(k, 2) имеет простую структуру и равна прямому произведению k экземпляров циклической группы порядка 2. Обобщением гиперкуба является n-мерный тор, который порождается прямым произведением n экземпляров циклических подгрупп, порядки которых могут не совпадать. В работе [5] исследованы графы Кэли групп B(k, 3), т. е. групп периода 3, а также проведён сравнительный анализ данных графов с гиперкубами. Анализ выявил, что графы B(k, 3) обладают более предпочтительными характеристиками, чем B(k, 2). Это означает, что при парном сравнении графов B(k1, 3) и B(k2, 2) с примерно одинаковым количеством вершин первые будут иметь меньшие диаметры, средние диаметры и степени. В связи с этим представляет интерес задача по исследованию графов Кэли конечных бернсайдовых групп другого периода. Пусть B0(2, 5) = (а1,а2) -максимальная конечная двупорождённая бернсайдова группа периода 5, порядок которой равен 534 [6]. Используя систему компьютерной алгебры GAP, нетрудно получить pc-представление (Power Commutator presentation) данной группы [3, 7]. В этом случае каждый элемент g e B0(2, 5) может быть однозначно записан в следующем виде: g = а?1 • а£2 • ... • «ОТ, а e Z5, i =1, 2,..., 34. Здесь а1 и а2 -порождающие элементы B0(2, 5); а3,...,а34 - коммутаторы, которые вычисляются рекурсивно через ai и а2 [6]. Обозначим через Bk фактор-группу B0 (2, 5) следующего вида: Bk = Bo(2,5)/(ак+1,... ,аэ4). Очевидно, что |Bk| = 5k и для всех д G Bk выполняется д = а?1 ■ а£2 ■ ... ■ аакк. Помимо прикладного интереса, существует и другая причина повышенного внимания исследователей к функциям роста Bk и особенно к B34 = B0(2, 5). Это объясняется тем, что полученная информация может оказаться полезной при решении открытой проблемы о конечности B(2, 5) - свободной двупорождённой бернсайдовой группы периода 5. Если B(2, 5) конечна, то B34 = B(2, 5). Однако в обозримом будущем вычислить функцию роста B34 едва ли возможно, поскольку количество её элементов очень велико: 534 = 582076609134674072265625 w 5 ■ 1023. К. А. Филипповым в работе [8] вычислена функция роста группы B14 в алфавите A2 = {а1, а2}. Аналогичная задача для симметричного порождающего множества A4 = = {а1 , а- , а2, а2 } решена Ч. Симсом [9]. В обоих случаях решение было получено при помощи длительных компьютерных вычислений. Отметим также, что Симс в своём алгоритме использовал элегантный трюк, основанный на применении к B14 группы автоморфизмов, сохраняющих длину группового слова. Это дало возможность свести задачу к рассмотрению только 1/16 части элементов группы. Подобный трюк для несимметричного порождающего множества менее эффективен, поскольку позволяет сократить количество элементов не более чем в 2 раза. Дальнейшее изучение функций роста групп Bk для k > 14 сталкивается с серьёзными вычислительными трудностями ввиду их больших порядков. В данной работе представлен эффективный алгоритм для вычисления функций роста указанных групп, который даёт возможность преодолеть существующий барьер. Компьютерная реализация алгоритма позволила вычислить функции роста групп Bk для k = 15, 16 и 17. В п. 1 рассматривается базовый алгоритм для вычисления функции роста конечной группы, а также исследуется его сложность. В п. 2 алгоритм модифицируется для исследования групп Bk. В п. 3 приведены результаты компьютерных вычислений по модифицированному алгоритму. 1. Описание базового алгоритма В качестве отправной точки далее представлен общий алгоритм A-I, вычисляющий функцию роста произвольной конечной группы G, заданной фиксированным порождающим множеством X. Лемма 1. Алгоритм A-I корректен, т.е. он за конечное число шагов вычислит функцию роста любой конечной группы G, заданной фиксированным порождающим множеством X. Доказательство. По построению A-I выражает каждый элемент группы G в виде группового слова наименьшей длины в алфавите X. После каждого прохода от п. 2 до п. 8 множество Ks представляет собой шар радиуса s группы G относительно X. Поскольку количество элементов группы конечно, через конечное число шагов, при некотором s = s0 + 1, все д G G будут записаны в виде слов, длины которых меньше Алгоритм 1. А-I Вход: X = {x1, x2,..., xm} -порождающее множество G Выход: функция роста F( s) группы G 1: s := 0, F( 0) := 1, K := {e}, P := K 2: s := s + 1 3: Ks := Ks-i 4: Для всех X E X и p E P 5: g = X ■ p (или g = p ■ x) 6: Если g E Ks, то Ks := Ks U {g} 7: P := Ks - Ks-i 8: F ( s) := |P| 9: Если F ( s) > 0, то переход в п. 2, 10: иначе 11: so := s - 1, переход в п. 12 _1 so 12: Dx( G) := so, Dx( G) := -- £ s ■ F ( s), выход |Kso 1 s=0 s0 + 1. Получим F ( s0 + 1) = 0 и |Kso | = |G|, что означает остановку алгоритма. При этом _1 so Dx( G) = so и Dx( G) = -- £ s ■ F ( s). ■ |Kso | s=0 Несмотря на то, что алгоритм A-I хорошо известен специалистам, автору не удалось найти публикаций, в которых были бы вычислены оценки его временной сложности. Например, в системе компьютерной алгебры GAP реализован указанный алгоритм, вычисляющий функцию роста группы подстановок. Однако в документации к системе отсутствуют сведения о его сложности. Для устранения указанного пробела воспользуемся машиной с произвольным доступом к памяти - RAM-машиной, а также асимптотическим анализом сложности [10]. Далее термины «временная сложность» и «сложность» будем считать равнозначными; кроме этого, введём обозначения: - T | G| ) - сложность алгоритма A-I; - O( f (|G|)) -верхняя асимптотическая оценка сложности; - П( f (|G|)) -нижняя асимптотическая оценка сложности; - в( f (|G|)) -одновременно верхняя и нижняя оценки сложности. Нам понадобятся следующие вспомогательные утверждения. Лемма 2. В процессе работы алгоритма A-I необходимо вычислить и проверить |X| ■ |G| групповых слов. Доказательство. При вычислении слов длины s ^ 1 следует обработать F ( s - 1)|X| элементов. В итоге получим Dx (G)+1 Dx (G)+1 £ F ( s - 1)|X| = |X| £ F (s - 1) = |X| ■ |G|. s=1 s=1 Лемма доказана. ■ Лемма 3. Пусть N(|G|) -суммарное количество проверок вида g G Ks алгоритма A-I. Тогда верно следующее неравенство: 2|G|2 + (JX| - 0 |G| + 1 ^ N(|G|) ^ (jX| - |G|2 + 2|G|. Доказательство. Рассмотрим сначала те групповые слова, которые войдут в Ks. Всего таких элементов, не считая единицы, (|G| - 1). Для первого из них необходимо осуществить одну проверку (с единицей группы), для второго - две и т. д. В итоге получим 1 + 2 + ... + (|G| - 1) = |G|(|G| - 1)/2 операций. Теперь рассмотрим те слова, которые не войдут в Ks. Согласно лемме 2, количество таких элементов равно |X| • |G| - (|G| - 1). В лучшем случае каждый из этих элементов будет проверен один раз и исключён, а в худшем - для каждого из них потребуется осуществить | G| сравнений. Таким образом, общее число проверок в худшем и лучшем случаях равно |G|(|G| - 1)/2 + |X| • |G| - (|G| - 1) и |G|(|G| - 1)/2 + (|X| • |G| - (|G| - 1))|G| соответственно. После элементарных преобразований получим нужное неравенство. ■ Теорема 1. T(|G|) G ft(|G|2) и T(|G|) G O(|X| • |G|2). Доказательство. При |G| ^ го сложностью операций всех пунктов алгоритма A-I, кроме четвертого, следует пренебречь. Поскольку количество элементарных операций, необходимое для вычисления произведения двух элементов группы, конечно и ограничено ©(1), то суммарная сложность M(|G|) п. 5 ограничена ©(|X| • |G|). Согласно лемме 3, получим |G|2/2 ^ N(|G|) ^ N(G) G ft(|G|2) и N(|G|) ^ |X| • |G|2 ^ ^ N(|G|) е O(|X| • |G|2). Так как T(|G|) = M(|G|) + N(|G|), получим T(|G|) е ft(|G|2) и T(|G|) е O(|X| • |G|2). ■ Следствие 1. Если |X| < |G|, то T(|G|) G ©(|G|2). Следствие 2. Если |X| ~ |G|, то T(|G|) G O(|G|3). Если порядок группы G достаточно большой, то наиболее критическими участками алгоритма A-I будут пп. 5 и 6, т.е. умножение элементов группы и проверка, позволяющая определить, встречался ранее такой элемент или нет. 2. Модификация алгоритма A-I для исследования групп Bk В данном случае X = A2 или A4. Рассмотрим п. 5 алгоритма. Существуют два способа умножения элементов в группах B&: собирательный процесс [3, 7] и метод полиномов Холла [11]. Вычислительные эксперименты показали, что второй способ позволяет значительно быстрее собирательного процесса (по крайней мере на порядок) умножать элементы в группах B& [12]. Следующий вопрос: как эффективнее умножать порождающие x е X на элементы группы p G Bk - слева (1 способ) или справа (2 способ), т. е. x• p или p• x? Кроме этого, была предложена идея при умножении слева использовать пять вариантов полиномов в зависимости от значения степени a i элемента p (3 способ). Для ответа на данный вопрос необходимо вычислить суммарное число операций t(k) в полиномах Холла, необходимое для выполнения одного произведения. В полиномах имеются три вида действий: сложение, умножение и остаток от деления числа на 5. На рис. 1 представлены графики t(k) для каждого из трёх способов (в предположении, что указанные действия имеют одинаковую сложность равную 1). Рис. 1. Графики сложности t(k) для одного произведения Рис. 1 наглядно показывает, что третий способ самый эффективный. Этот факт был учтён при реализации п. 5 алгоритма. Теперь обратимся к п. 6 алгоритма A-I. Для его оптимизации потребуется каждому ак элементу g е Bk присвоить уникальный порядковый номер. Пусть g = a^1 произвольный элемент Bk. Определим биективное отображение ф следующего вида: Ф g ng = a2... ak. Здесь ng представляет собой целое неотрицательное число, записанное в пятеричной системе счисления, которое возьмём в качестве порядкового номера g. Легко увидеть, что ng пробегает все значения от 0 до (5k - 1). Модифицируем A-I следующим образом. В п. 1 добавим булев вектор V размерности 5k, все элементы которого первоначально равны 0. Для удобства индексация элементов V начинается с 0, т.е. последний элемент вектора имеет индекс (5k - 1). Заменим п. 6 алгоритма A-I на следующий: 6: Если Vng = 0, то V„ff := 1 и Ks := K u {g}. Данная модификация позволяет избежать трудоёмкой процедуры поиска элемента g в множестве Ks. Будем считать, что для выполнения п. 6 алгоритма требуется не более t(g) элементарных операций. Несмотря на то, что порядки Bk ограничены сверху, имеет смысл рассмотреть асимптотическую оценку сложности модифицированной версии алгоритма, поскольку данные группы содержат достаточно большое число элементов при k > 8. Теорема 2. Пусть T(|Bk|) -вычислительная сложность модифицированного алгоритма A-I. Тогда верно, что T(|Bk|) е e(|Bk|). Доказательство. При вычислении асимптотической оценки следует учитывать сложность только наиболее трудоёмких фрагментов алгоритма, т. е. пп. 5 и 6. Поскольку T(|G|) = (t(k) + t(g))|X| • В|, |X|

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

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

Авторы

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

Ссылки

Even S. and Goldreich O. The Minimum Length Generator Sequence is NP-hard // J. Algorithms. 1981. No. 2. P. 311-313.
Кузнецов А. А., Кузнецова А. С. Параллельный алгоритм для исследования графов Кэли групп подстановок // Вестник СибГАУ. 2014. №1. C. 34-39.
Holt D., Eick B., and O'Brien E. Handbook of Computational Group Theory. Boca Raton: Chapman & Hall/CRC Press, 2005. 514 p.
Camelo M, Papadimitriou D., Fabrega L., and Vila P. Efficient routing in data center with underlying Cayley graph // Proc. 5th Workshop on Complex Networks CompleNet. 2014. P. 189-197.
Кузнецов А. А. Графы Кэли бернсайдовых групп периода 3 // Сибирские электронные математические известия. 2015. T. 12. C. 248-254.
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. Fast multiplication and growth in groups // Proc. 1998 Intern. Symp. Symbolic Algebraic Computation. 1998. P. 165-170.
Филиппов К.А. О диаметре Кэли одной подгруппы группы Bo(2, 5) // Вестник СибГАУ. 2012. №1. С. 234-236.
Sims C. Computation with Finitely Presented Groups. Cambridge: Cambridge University Press, 1994. 628 p.
Скиена C. Алгоритмы. Руководство по разработке. СПб.: БХВ-Петербург, 2014. 720 с.
Hall P. Nilpotent Groups: Notes of Lectures Given at the Canadian Mathematical Congress Summer Seminar, University of Alberta, 12-30 August, 1957. London: Queen Mary College, 1969.
Кузнецов А. А., Кузнецова А. С. Быстрое умножение элементов в конечных двупорождённых группах периода пять // Прикладная дискретная математика. 2013. № 1. C. 110-116
 Об одном алгоритме вычисления функций роста в конечных двупорождённых группах периода 5 | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/10

Об одном алгоритме вычисления функций роста в конечных двупорождённых группах периода 5 | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/10