Элементы вычислительной теории групп
Покупка
Основная коллекция
Издательство:
Сибирский федеральный университет
Автор:
Шлепкин Алексей Анатольевич
Год издания: 2021
Кол-во страниц: 104
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Магистратура
ISBN: 978-5-7638-4496-2
Артикул: 814095.01.99
Учебное пособие «Элементы вычислительной теории групп» соответствует программе курса «Вычислительная теория групп» и подготовлено на основе преподавания автором дисциплины «Вычислительная теория групп». Рассмотрены вычислительные алгоритмы на группах подстановок, линейных группах, алгоритмы вычисления функции плотности групп. Методы, изложенные в учебном пособии, могут быть востребованы в алгебре, криптографии, прикладных вычислениях в науке и технике.
Предназначено для магистрантов, обучающихся по специальности 01.04.02 «Прикладная математика и информатика». Может быть полезно магистрантам, аспирантам, научным работникам в их научных исследованиях.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
Министерство науки и высшего образования Российской Федерации Сибирский федеральный университет ЭЛЕМЕНТЫ ВЫЧИСЛИТЕЛЬНОЙ ТЕОРИИ ГРУПП Учебное пособие Красноярск СФУ 2021
УДК 512.54(07) ББК 22.147.4я73 Ш687 Рецензенты: В. И. Сенашов, доктор физико-математических наук, профессор, ведущий научный сотрудник ИВМ КНЦ СО РАН; Н. Г. Сучкова, кандидат физико-математических наук, доцент кафедры прикладной математики и компьютерной безопасности СФУ Ш687 Элементы вычислительной теории групп : учеб. пособие / А. А. Шлепкин. – Красноярск : Сиб. федер. ун-т, 2021. – 104 с. ISBN 978-5-7638-4496-2 Учебное пособие «Элементы вычислительной теории групп» соответствует программе курса «Вычислительная теория групп» и подготовлено на основе преподавания автором дисциплины «Вычислительная теория групп». Рассмотрены вычислительные алгоритмы на группах подстановок, линейных группах, алгоритмы вычисления функции плотности групп. Методы, изложенные в учебном пособии, могут быть востребованы в алгебре, криптографии, прикладных вычислениях в науке и технике. Предназначено для магистрантов, обучающихся по специальности 01.04.02 «Прикладная математика и информатика». Может быть полезно магистрантам, аспирантам, научным работникам в их научных исследованиях. УДК 512.54(07) ББК 22.147.4я73 Электронный вариант издания см.: http://catalog.sfu-kras.ru ISBN 978-5-7638-4496-2 © Сибирский федеральный университет, 2021
ОГЛАВЛЕНИЕ Введение ............................................................................................................... 4 Глава 1. Вычислительные алгоритмы на группах подстановок ..................... 6 1.1. Вычисление симметрических групп малых степеней ........................... 6 1.2. Алгоритмы вычисления элементов симметрических и знакопеременных групп .................................................................................. 9 1.3. Алгоритмы вычисления регулярных подстановок .............................. 41 1.4. Алгоритмы вычисления регулярных подстановок заданного порядка ............................................................................................................ 49 Глава 2. Алгоритмы вычислений в линейных группах ................................. 55 2.1. Расширения полей ................................................................................... 55 2.2. Построение конечных полей простого порядка .................................. 55 2.3. Вычисление первообразных элементов мультипликативных групп конечных полей простого порядка ............................................................... 57 2.4. Вычисление элементов и автоморфизмов поля 𝐺𝐹(22𝑛) .................... 62 2.5. Примеры построения полей непростого порядка ................................ 65 2.6. Алгоритм вычисления 2-подгрупп группы 𝑈3(2𝑛) ............................. 67 2.7. Алгоритм вычисления силовской 2-подгруппы группы 𝑈3(2𝑛) ........ 68 2.8. Силовская 2-подгруппа группы 𝑈3(4) .................................................. 74 2.9. Вычисление элементов группы 𝐿2 (5) .................................................. 85 Глава 3. Вычисление функции плотности конечных групп .......................... 91 3.1. Основные понятия ................................................................................... 91 3.2. Изоморфизм групп с одной функцией плотности ............................... 95 Лабораторные работы ....................................................................................... 97 Библиографический список............................................................................ 102
ВВЕДЕНИЕ Вычислительная теория групп (ВТГ) является одним из важных и интересных направлений компьютерной алгебры. Возникли обширные пакеты компьютерных программ, позволяющие проводить вычисления в алгебраических системах, которые содержат большое число элементов (GAP, Cayley, Magma). Однако при всей мощи упомянутых пакетов они оказываются бессильными в исследовании систем, имеющих потенциально бесконечное число элементов, в связи с чем начали разрабатываться алгоритмы, которые годятся для произвольных типов алгебраических систем, в частности для конечнопорожденных групп. Это обусловлено в первую очередь тем, что в теории групп с начала прошлого века остается нерешенным ряд актуальных вопросов, связанных с такими группами, и один из таких вопросов, занимавших умы многих исследователей, остается вопрос о конечности двупорожденной группы периода 5 (группы В (2,5)), или, другими словами, вопрос о совпадении данной группы с наибольшей конечной двупорожденной группой периода 5 – группой 𝐵0(2, 5), порядок которой paвeн 534 – 582076609134674072265625. Известно (С. И. Адян, П. С. Новиков, И. Г. Лысенок и др.), что если число 5 заменить достаточно большим натуральным числом n, то ответ оказывается отрицательным. С другой стороны, ответ положительный при n, равном 4 или 6 (И. Н. Санов и М. Холл соответственно). Подробный анализ вычислений, проведенный для групп, порядки элементов которых исчерпываются числами 1, 2, 3, 4, 7, позволил ответить на вопрос о конечности таких гpyпп и тем самым решить известную проблему – о распознаваемости по спектру группы 𝐿2(7). Глава 1 посвящена изложению алгоритмов вычислений в группах подстановок. Рассматриваются примеры вычисления групп подстановок малых степеней (3, 4). Затем дается общий алгоритм вычисления 𝑆𝑛 (симметрическая группа) и 𝐴𝑛 (знакопеременная группа). Рассмотрены задачи вычисления таких групп в образующих специального вида. Особое внимание уделено вычислению групп регулярных подстановок, что обусловлено тем фактом, что любую конечную группу можно представить в виде подгруппы регулярных подстановок в подходящей 𝑆𝑛.
Глава 2 посвящена вычислениям в линейных группах над конечными полями. Поскольку поле обладает структурами, являющимися конечными абелевыми группами по сложению и умножению, то вначале рассматриваются вычисления в конечных полях (вычисления аддитивной группы поля, вычисление мультипликативной группы поля, вычисление первообразных элементов). Линейные группы представляют основной массив конечных простых неабелевых групп. В связи с этим рассмотрены вычисления в минимальной конечной простой линейной группе 𝐿2(5) (она же 𝐴5). Для данной группы рассмотрены задачи вычисления классов сопряженности, задачи нахождения порядков элементов группы, являющихся произведением заданных элементов. В главе 3 вводится понятие функции плотности группы. В теории групп арифметическими принято называть свойства группы, которые определяются ее числовыми параметрами: порядок группы и набор его простых делителей, порядки элементов, порядки подгрупп, степени неприводимых представлений, порядки классов сопряженности и т. д. В учебном пособии под этим углом зрения рассматривается понятие функции плотности группы, основанное на широко известном понятии функции роста группы. В качестве арифметического свойства, позволяющего с точностью до изоморфизма определить конечную группу, предлагается использовать понятия независимой системы образующих и функции плотности группы, введенные ниже. Вычисление функции плотности группы позволяет получить содержательную информацию о структуре группы. Рассмотрена задача об изоморфизме конечных простых групп с одной функцией плотности. Для практического закрепления теоретического материала приводятся лабораторные работы, а для дополнительного ознакомления с алгоритмами в ВТГ – библиографический список [1–15] Учебное пособие будет полезно студентам, аспирантам, научным работникам в области фундаментальной математики и информационных технологий.
ГЛАВА 1 ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ НА ГРУППАХ ПОДСТАНОВОК 1.1. Вычисление симметрических групп малых степеней Задача. Вычислить симметрическую группу степени 3- 𝑆3. Решение: Запишем все 6 подстановок степени 3: G= (1 2 3 1 2 3); G1=(1 2 3 1 3 2); G2=(1 2 3 2 1 3); G3=(1 2 3 2 3 1); G4=(1 2 3 3 1 2); G5=(1 2 3 3 2 1). Вычислим умножение этих подстановок: G*G=(1 2 3 1 2 3)=G G1*G1=(1 2 3 1 2 3)=G G*G1=(1 2 3 1 3 2)=G1 G1*G2=(1 2 3 2 3 1)=G3 G*G2=(1 2 3 2 1 3)=G2 G1*G3=(1 2 3 2 1 3)=G2 G*G3=(1 2 3 2 3 1)=G3 G1*G4=(1 2 3 3 2 1)=G5 G*G4=(1 2 3 3 1 2)=G4 G1*G5=(1 2 3 3 1 2)=G4 G*G5=(1 2 3 3 2 1)=G5 G2*G1=(1 2 3 3 1 2)=G4 G2*G2=(1 2 3 1 2 3)=G G5*G3=(1 2 3 1 3 2)=G1 G2*G3=(1 2 3 3 2 1)=G5 G5*G4=(1 2 3 2 1 3)=G2 G2*G4=(1 2 3 1 3 2)=G1 G5*G5=(1 2 3 1 2 3)=G G2*G5=(1 2 3 2 3 1)=G G3*G1=(1 2 3 3 2 1)=G5 G3*G2=(1 2 3 1 3 3)=G1 G3*G3=(1 2 3 3 1 2)=G4 G3*G4=(1 2 3 1 2 3)=G G3*G5=(1 2 3 2 1 3)=G2 G4*G1=(1 2 3 2 1 3)=G2
G4*G2=(1 2 3 3 2 1)=G5 G4*G3=(1 2 3 1 2 3)=G G4*G4=(1 2 3 2 3 1)=G3 G4*G5=(1 2 3 1 3 2)=G1 G5*G1=(1 2 3 2 3 1)=G3 G5*G2=(1 2 3 3 1 2)=G4 Составим таблицу умножения: G G1 G2 G3 G4 G5 G G G1 G2 G3 G4 G5 G1 G1 G G3 G2 G5 G4 G2 G2 G4 G G5 G1 G3 G3 G3 G5 G1 G4 G G2 G4 G4 G2 G5 G G3 G1 G5 G5 G3 G4 G1 G2 G Задача. Вычислить симметрическую группу степени 4- 𝑆4. Решение: Запишем все 24 подстановки степени 4: G=(1 2 3 1 2 3 4 4) ; G1=(1 2 3 1 2 4 4 3); G2=(1 2 3 1 4 2 4 3); G3=(1 2 3 4 1 2 4 3); G4=(1 2 3 2 1 3 4 4); G5=(1 2 3 2 1 4 4 3); G6=(1 2 3 2 4 1 4 3); G7=(1 2 3 4 2 1 4 3); G8=(1 2 3 1 3 2 4 4); G9=(1 2 3 1 3 4 4 2); G10=(1 2 3 1 4 3 4 2); G11=(1 2 3 4 1 3 4 2); G12=(1 2 3 3 1 2 4 4); G13=(1 2 3 3 1 4 4 2 ); G14=(1 2 3 3 4 1 4 2); G15=(1 2 3 4 3 1 4 2); G16=(1 2 3 2 3 1 4 4); G17=(1 2 3 2 3 4 4 1); G18=(1 2 3 2 4 3 4 1); G19=(1 2 3 4 2 3 4 1); G20=(1 2 3 3 2 1 4 4); G21=(1 2 3 3 2 4 4 1); G22=(1 2 3 3 4 2 4 1); G23=(1 2 3 4 3 2 4 1);
Операция умножения происходит следующим образом: G1*G2= (1 2 3 1 4 3 4 2)=G10; G4*G22=(1 2 3 4 3 2 4 1)=G23 G10*G5=(1 2 3 2 3 4 4 1)=G17 G23*G13=(1 2 3 2 4 1 4 3)=G6 Составим таблицу умножения: G G 1 G 2 G 3 G 4 G 5 G 6 G 7 G 8 G 9 G 10 G 11 G 12 G 13 G 14 G 15 G 16 G 17 G 18 G 19 G 20 G 21 G 22 G 23 G G G 1 G 2 G 3 G 4 G 5 G 6 G 7 G 8 G 9 G 10 G 11 G 12 G 13 G 14 G 15 G 16 G 17 G 18 G 19 G 20 G 21 G 22 G 23 G 1 G 1 G G 10 G 11 G 5 G 4 G 18 G 19 G 9 G 8 G 2 G 3 G 13 G 12 G 22 G 23 G 17 G 16 G 6 G 7 G 21 G 20 G 14 G 15 G 2 G 2 G 8 G 9 G 15 G 6 G 16 G 17 G 23 G 10 G G 1 G 7 G 14 G 20 G 21 G 19 G 18 G 4 G 5 G 3 G 22 G 12 G 13 G 14 G 3 G 3 G 12 G 13 G 14 G 7 G 20 G 21 G 22 G 11 G 4 G 5 G 6 G 15 G 16 G 17 G 18 G 19 G G 1 G 2 G 23 G 8 G 9 G 10 G 4 G 4 G 5 G 3 G 2 G G 1 G 7 G 6 G 12 G 13 G 11 G 10 G 8 G 9 G 15 G 14 G 20 G 21 G 19 G 18 G 16 G 17 G 23 G 22 G 5 G 5 G 4 G 11 G 10 G 1 G G 19 G 18 G 13 G 12 G 3 G 2 G 9 G 8 G 23 G 22 G 21 G 20 G 7 G 6 G 17 G 16 G 15 G 14 G 6 G 6 G 16 G 15 G 9 G 2 G 8 G 23 G 17 G 14 G 20 G 7 G 1 G 10 G G 19 G 21 G 22 G 12 G 3 G 5 G 18 G 4 G 11 G 13 G 7 G 7 G 20 G 14 G 13 G 3 G 12 G 22 G 21 G 15 G 16 G 6 G 5 G 11 G 4 G 18 G 17 G 23 G 8 G 2 G 1 G 19 G G 10 G 9 G 8 G 8 G 2 G 1 G 7 G 16 G 6 G 5 G 3 G G 10 G 9 G 15 G 20 G 14 G 13 G 11 G 4 G 18 G 17 G 23 G 12 G 22 G 21 G 19 G 9 G 9 G 10 G G 19 G 17 G 18 G 4 G 11 G 1 G 2 G 8 G 23 G 21 G 22 G 12 G 3 G 5 G 6 G 16 G 15 G 13 G 14 G 20 G 7 G 10 G 10 G 9 G 8 G 23 G 18 G 17 G 16 G 15 G 2 G 1 G G 19 G 22 G 21 G 20 G 7 G 6 G 5 G 4 G 11 G 14 G 13 G 12 G 3 G 11 G 11 G 13 G 12 G 22 G 19 G 21 G 20 G 14 G 3 G 5 G 4 G 18 G 23 G 17 G 16 G 6 G 7 G 1 G G 10 G 15 G 9 G 8 G 2 G 12 G 12 G 3 G 5 G 6 G 20 G 7 G 1 G 2 G 4 G 11 G 13 G 14 G 16 G 15 G 9 G 10 G G 19 G 21 G 22 G 8 G 23 G 17 G 18
Окончание таблицы умножения 1.2. Алгоритмы вычисления элементов симметрических и знакопеременных групп 1. Описание задачи. Через n будем обозначать ступень симметрической группы. В качестве порождающих элементов возьмем подстановки 𝑥1 = (1 2 3 2 1 3 4 … 𝑛 4 … 𝑛) = (1, 2) и 𝑦1 = (1 2 3 2 3 4 ⋯ 𝑛 − 1 𝑛 ⋯ 𝑛 1) = (1, 2, … , 𝑛) G 13 G 13 G 11 G 4 G 18 G 21 G 19 G G 10 G 5 G 3 G 12 G 22 G 17 G 23 G 8 G 2 G 1 G 7 G 20 G 14 G 9 G 15 G 16 G 6 G 14 G 14 G 15 G 16 G 17 G 22 G 23 G 8 G 9 G 6 G 7 G 20 G 21 G 18 G 19 G G 1 G 2 G 3 G 12 G 13 G 10 G 11 G 4 G 5 G 15 G 15 G 14 G 20 G 21 G 23 G 22 G 12 G 13 G 7 G 6 G 16 G 17 G 19 G 18 G 4 G 5 G 3 G 2 G 8 G 9 G 11 G 10 G G 1 G 16 G 16 G 6 G 7 G 1 G 8 G 2 G 3 G 5 G 10 G 14 G 15 G 9 G G 10 G 11 G 13 G 12 G 22 G 15 G 17 G 4 G 18 G 19 G 21 G 17 G 17 G 18 G 19 G G 9 G 10 G 11 G 4 G 21 G 22 G 23 G 8 G 1 G 2 G 3 G 12 G 13 G 14 G 15 G 16 G 5 G 6 G 7 G 20 G 18 G 18 G 17 G 23 G 8 G 10 G 9 G 15 G 16 G 22 G 21 G 19 G G 2 G 1 G 7 G 20 G 14 G 13 G 11 G 4 G 6 G 5 G 3 G 12 G 19 G 19 G 21 G 22 G 12 G 11 G 13 G 14 G 20 G 23 G 17 G 18 G 4 G 3 G 5 G 6 G 16 G 15 G 9 G 10 G G 7 G 1 G 2 G 8 G 20 G 20 G 7 G 6 G 5 G 12 G 3 G 2 G 1 G 16 G 15 G 14 G 13 G 4 G 11 G 10 G 9 G 8 G 23 G 12 G 21 G G 19 G 18 G 17 G 21 G 21 G 19 G 18 G 4 G 13 G 11 G 10 G G 17 G 23 G 22 G 12 G 5 G 3 G 2 G 8 G 9 G 15 G 14 G 20 G 1 G 7 G 6 G 16 G 22 G 22 G 23 G 17 G 16 G 14 G 15 G 9 G 8 G 18 G 19 G 21 G 20 G 6 G 7 G 1 G G 10 G 11 G 13 G 12 G 2 G 3 G 5 G 4 G 23 G 23 G 22 G 21 G 20 G 15 G 14 G 13 G 12 G 19 G 18 G 17 G 16 G 7 G 6 G 5 G 4 G 11 G 10 G 9 G 8 G 3 G 2 G 1 G
Нейтральным элементом Е является тождественная подстановка.
Легко проверить, А2 = Е и Е𝑛 = 𝐸. Требуется построить представление
группы Sn в виде слов на алфавите 𝑊 = {0, 1} . Пусть функция f
преобразует слово в подстановку. Тогда f определяется по правилам:
𝑓(0) = 𝑥1
𝑓(1) = 𝑥1
𝑓(𝑣𝑤) = 𝑓(𝑣) ∗ 𝑓(𝑤)
где 𝑣 ∈ 𝑊; 𝑤 = 𝑣1 … 𝑣𝑚, 𝑣𝑖 ∈ 𝑊; ∗ – композиция подстановок. Пустому
слову соответствует тождественная подстановка. Из данного слова w
длины m получается два слова длины m + 1: 0w и 1w. Получив новое слово,
мы проверяем его на наличие последовательности 00 или 1n в начале. Если
такая последовательность есть, то слово отбрасывается, так как оно
тождественно одному из слов, полученных ранее. По этой причине такие
последовательности не могут содержаться внутри уже построенных слов.
И, наконец, если подстановка нового слова уже находится в множестве
подстановок ранее полученных слов, то такое слово отбрасывается.
Так как |𝑆𝑛| = 𝑛!,то мы можем получить грубую оценку вычислительной
сложности задачи. Нужно построить n! слов, для каждого нового слова
получить подстановку и сравнить ее со всеми уже известными
подстановками, количество коих также будет приближаться к n! по мере
работы. Таким образом, если мы линейно просматриваем все ранее
полученные подстановки, время работы алгоритма будет близко
к 𝑂((𝑛!)2).
На множестве подстановок Р можно ввести отношение порядка, что
позволит хранить Р в виде бинарного дерева поиска и определять наличие
в нем новой подстановки за время порядка 𝑂(log2(|𝑃|)) вместо 𝑂(|𝑃|).
2. Представление данных. Программы писались под ОС Linux
и компилятор gcc версии не менее 4.7, процессор – любой х86_64.
Во всех версиях программы слова и подстановки хранятся в виде
данных типа беззнаковое целое число, элементы алфавита W представляют
собой биты такого числа.
Было написано две достаточно независимых версии программы. Первая версия может рассматриваться как прототип и на данный момент она не актуальна. Ни одна версия не использует параллелизм, вся работа выполняется в один поток. 1.2.1. Первая версия В первой версии программы будем сохранять слова в 64-битовом типе – от старшего бита к младшему. Пример: слово 10001 представляется в виде числа 17. В массивах 8-битовых чисел будем сохранять подстановки в одном сплошном массиве одна за другой. При этом все подстановки не обязательно хранить в памяти. Нам достаточно хранить только слова, необходимые для работы, а остальные можно выгружать в файлы на диск. 1.2.2. Вторая версия После запуска первой версии стало ясно, что 64 бита слишком мало для хранения слова. В группе S10 уже есть слова длины 58, а значит, длина слов S11 превысит 64. Также стало ясно, что линейный поиск в Р не позволит построить S11 за разумное время, поэтому были приняты следующие улучшения. Слова хранятся в 128-битном типе. Имеющийся процессор не поддерживает такой тип данных аппаратно, однако компилятор очень эффективно реализует его эмуляцию. В gcc такой тип называется unsigned_ _int128. Подстановки хранятся в 64-битовом типе, каждый элемент подстановки хранится в полубайте. Таким образом, каждый элемент может принимать 16 различных значений от 0 до 15, а во всем 64-битовом числе можно сохранить 16 элементов подстановки. Для больших значений n хранение получается достаточно эффективным, а операции сравнения и присваивания поддерживаются процессором аппаратно и выполняются за 1 такт. Более того, на таких представлениях подстановок вводится отношение порядка, операция сравнения «<», для которого также выполняется процессором аппаратно. Любая подстановка будет