ТЕОРИЯ ГРУПП



Группы Галуа, циклические группы, on-line алгоритмы

© Nickolay A. Balonin, 1.05.2015


Группа. Множество элементов с некоторой бинарной операцией × образует группу G, если операция отвечает привычному со школьной статьи закону арифметики, касающемуся как сложения, так и умножения. Складывать или умножать между собой три числа мы можем в любой последовательности. Это свойство именуется ассоциативностью. Множество должно включать в себя нейтральный элемент (единицу, при умножении) и все обратные элементы (умножение на которые ведет к 1).



Построение теории групп на опорах


Сложность группы – понятие размытое. Допустим, мы на тарелку укладываем остальные тарелки. Если растущая горка охватывает своими комбинациями все возможные конфигурации, которые можно сложить из тарелок, это повод охарактеризовать эту ситуацию как простую, а нижнюю тарелку объявить оселком, на котором проверяется простота. Такова нормальная подгруппа, перенимающая свойство тривиального элемента порождать всю группу.

В аналитической части теории групп принято рассматривать блоки (орбита элемента, фактор группа), образуемые умножениями некоторого элемента или совокупности элементов на элементы группы. Вокруг элементов или подмножеств возникает орбита или общность, рассматриваемая как конструктивный элемент группы. Что то вроде кочки с поросшей травой, основа и несомая ею часть. Сама по себе такая кочка смысла не имеет, но выделение нескольких позволяет говорить – найдена некая структура группы !

Мощность группы |G| обычно называется ее порядком (у конечного набора чисел, с операцией, это число элементов). Конечная группа содержит конечное число элементов, бинарная операция не выводит за пределы группы G×G→G. Древнейшая теорема Лагранжа отвечает представлению, возникшему еще до оформления теории групп: рассматривает размер конечной группы G как произведение размеров входящих в нее конечных подгрупп. Неполный вариант обратной теоремы к теореме Лагранжа (для некоторых делителей порядка группы G гарантируют существование подгрупп такого порядка) доказан норвежским математиком Силовом в 1872 г. Пусть |G|=pns, p – простое, s не делится на p. Тогда силовской p-подгруппой называется подгруппа G, имеющая порядок pn. Используется для вынесения суждения о простоте группы непосредственно по ее порядку.

Централизатор элемента. В группе, где не все элементы перестановочны между собой, иногда полезно рассмотреть множество всех элементов группы, перестановочных с некоторым заданным элементом a, т.е. множество всех элементов b, для которых ab совпадает с ba (ab=ba). Это множество называется централизатором элемента a. У матриц выделение коммутирующих матриц AB=BA – путь к выделению поля (из кольца).

Легко проверить, что централизаторы сами являются группами относительно операции в исходной группе, и, значит, они образуют подгруппы данной группы. Тривиальным примером служит централизатор нейтрального элемента 1; он всегда совпадает со всей исходной группой, так как одно из условий, определяющих группу, в том и состоит, что каждый элемент группы перестановочен с нейтральным элементом.

Самые простые группы: циклические, в них нет никаких инградиентов, кроме 1 и всей группы, нет подгрупп. Умножая 1 на элементы циклической группы, ее же и получим. Они образованы благодаря коммутативной, т.е. абелевой, операции. Элементы могут носить имена: a, aa, aaa ..., и, в самом деле, при умножении и слева, и справа на a элемент aa даст aaa.

Группа конечна, если операция группы приводит к тому, что некоторое достаточно большое aaa...a = 1. Близкая по смыслу дициклическая группа состоят из двух конгломератов: a, aa, aaa, ...; b, ab, aab, aaab, ... с взаимными переходами (совпадениями) элементов типа b2=av и т.п..

Помимо правила aaa...a = 1 уменьшению размера конечной группы способствуют иные сходные с ним правила (позволяющие производить сокращения), но стоит иметь в виду, что с 1861 года почти столетие теория выделяла всего пять относительно сложных конструкций Матье (-io), составляемых из пар элементов a, b.

Все четные перестановки пяти и более букв образуют некоммутативные простые группы. Эти группы – их называют знакопеременными группами на n буквах – составляют второе бесконечное семейство простых групп. Кстати, именно это принципиальное различие между знакопеременными группами степени меньшей или равной 4 и степени большей или равной 5 легло в основу исследований Галуа, посвященных алгебраическим уравнениям. С его помощью объясняется принципиальная разница в свойствах решений алгебраических уравнений степени меньшей или равной 4 и степени большей или равной 5.

Экспонента и порядок группы. Заметим, что наименьшее значение показателя m≥1 элемента am=1 называют экспонентой группы G (наименьшее общее кратное порядков элементов конечной группы).

Инволюции (корни квадратные). Элементы порядка 2 (aa=1) называются инволюциями. По содержанию, это корни (их взаимное произведение дает 1). Легко показать, что инволюции есть в каждой группе с четным числом элементов. Поэтому, согласно теореме Томпсона–Фейта (доказательство, как всегда, сложно), всякая некоммутативная простая группа содержит инволюции. Централизаторы инволюций в некоторых из 18 регулярных семейств имеют такое же внутреннее строение, как исходная группа, но в зачаточной форме.

Тривиальная группа – это группа, состоящая из одного элемента. Этот элемент обязан быть единицей группы; в зависимости от контекста его обозначают 0 (если групповая операция – сложение), 1 (в том случае, когда под групповой операцией подразумевается умножение) или e. Тривиальную группу нельзя путать с пустым множеством, поскольку аксиомы группы требуют наличия в ней единицы.

Граф Кэли. Наглядный граф переходов между элементами группы. Классификация графов по Стейнеру привела к выделению классических структур (проективные планы, аффинные планы и т.п.) и их параметров. Интерпретации групп строго регулярными графами описываются параметрами {ν, κ, λ, μ}. Спорадическая группа J2 представлена {100,36,14,12} графом.

Граф Кэли HJ.2:

Абелева группа. Если от арифметики берется закон коммутативности (ab=ba), то группа называется коммутативной или абелевой.

Матрицы, например, неподходящий материал для образования абелевых групп, если иметь в виду операцию умножения. А сложение, естественно, хлопот не вызывает.

Набор целых {0, 1, ..., n–1} это группа с операцией сложения по модулю n. Обычное обозначение ее Zn. Абелевы группы обычно записывают аддитивно (с плюсом): роль 1 играет 0, роль обратного элемента a–1 играет –a.

Основополагающая теорема о структуре конечной абелевой группы утверждает, что любая конечная абелева группа может быть разложена в прямую сумму своих циклических подгрупп, порядки которых являются степенями простых чисел. Множество всех чисел, сравнимых с a по модулю n, называется классом вычетов. На множестве целых чисел Z таких классов n, их обозначают Zn или Z/nZ. Например, Z/15Z (с модульной арифметикой) может быть разложено в прямую сумму двух циклических подгрупп порядков 3 и 5: Z15={0;5;10}+{0;3;6;9;12}. То же можно сказать про любую абелеву группу порядка пятнадцать, приходим к выводу, что все абелевы группы порядка 15 изоморфны.

Неабелевы группы. Если группа не абелева, то (ab)–1=b–1a–1, как у матриц. Порядок здесь имеет значение (перчатки, их все равно в каком порядке снимать, а вот пиджак снять раньше пальто – проблематично). Такая арифметика, она ничуть не затруднительна и привычна. Изучение не абелевых групп связано с формализацией понятия нейтрального элемента, роль которого начинают играть нормальные подгруппы. Если их несколько, то выясняют элементы, которыми нормальные подгруппы окружены (фактор группы).

Пример некоммутативной группы (не абелевой) – группы всех перестановок Sn, при n≥3; множество с n элементами порождает n! перестановок, как известно из школьной программы. Они названы симметрическими, поскольку впервые возникли в задачах с симметрическими многочленами типа x12+x22, симметрия которых состоит в специфичном вхождении аргументов. При n>4 симметрическая группа неразрешима, см. wiki.

Любая конечная группа изоморфна некоторой группе перестановок (теорема Кэли). Ее можно записать в виде двойной строки, где верхняя строка соответствует аргументу, а нижняя строка – значению перестановки (123/321). Перестановка называется четной, если число транспозиций (переносов) четно, такие перестановки образуют подгруппу An.

Подгруппа. Понятие группы связано с множеством и с операцией, над элементами множества. Если внутри множества G есть подмножество H, образующее группу с той же операцией, то выхода нет, его (с операцией) следует величать подгруппой. Для групп G, H не принято пользоваться обозначениями вложений (как у множеств), пишется более операционно H ≤ G. Что назвали надгруппой G ≥ H, дойдите до этого сами.

<X> – обозначение наименьшей подгруппы в G, содержащей порождающее ее множество X (пересечение всех подгрупп, содержащих X).

Нормальная подгруппа. Допустим, мы умножили элемент подгруппы на масштабный множитель слева и поделили на него же справа. Если элемент после этого остался в пределах подгруппы, его "увело", но не очень, то перед нами нормальная подгруппа.

Собственно, перед нами формализованное свойство 1 мультипликативной группы. Для не абелевых групп различать элементы, похожие на единицу (нормальные подгруппы), полезно. У нормальных подгрупп меньше проблем с операцией масштабирования (смещения, в аддитивном исполнении), например, левые и правые косеты совпадают.

Фактор группа. Масштабируем элементы нормальной подгруппы H умножением их на элементы группы G. Умножение на элементы из H не выводит произведение элементов нормальной группы за пределы H.

Эта "масштабированная" нормальная группа (играющая роль 1) и называется фактор группой. Фактор группа больше нормальной подгруппы. Иными словами, если H – нормальная подгруппа группы G, тогда сэт G/H = {xH | x∈G} формирует группу с операцией (xH)(yH)=xyH, называемую фактор группой ("умножаем множители", потом "применяем" для "масштабирования").

Коммутант группы. Подгруппа (производная группы) G(0) = [a,b]=a–1b–1ab, a и b – элементы группы G.

Коммутант группы – нормальная подгруппа. Всякая подгруппа, содержащая коммутант группы – нормальная. Цепочка производных стабилизируется на совершенной подгруппе, коммутант которой не меняется при "взятии" производной. Если эта группа тривиальна, исходная группа G называется разрешимой. Для абелевых групп коммутант совпадает с единичным элементом.

Отметим. В теории колец используется иное определение коммутанта, чьи элементы – коммутаторы – определены через разности abba.

Косеты. Когда мы масштабируем множителями показательные функции (циклические группы), построенные от чисел, мы не задумываемся, с какой стороны мы приписали множитель. Масштабирование (при мультипликативной операции группы), в аддитивном толковании, это смещение добавкой элемента. Когда мы начинаем задумываться, мы говорим о левых или правых косетах (cosets), буквально – со сэты, синхронизированные масштабированием или смещением сэты.

Циклическая группа. Группа называется циклической, если она порождена одним элементом. Т.е. степени этого образующегоо элемента g (взаимные произведения, степени) и есть элементы группы. Последовательные повышения степени приводят к нейтральному элементу gn=1, показатель степени совпадает с порядком группы n=o(g).

Группа порядка p, где p – простое число, циклична (поскольку порядок элемента, отличного от единицы, не может быть равен 1, все элементы, кроме единицы, имеют порядок p, и значит, каждый из них порождает группу).

Порядок произвольного элемента циклической группы gm равен n/gcd(m,n), где gcd(m,n) – наибольший общий делитель.

Группа G называется периодической (группой кручения), если все ее элементы имеют конечный порядок (образуют конечные циклические подгруппы). Всякая группа конечной экспоненты – периодическая. Произведение элементов конечной абелевой группы имеет порядок, не выше 2 (группа экспоненты 2 – абелева).

Простые группы. Группы, которые невозможно упростить менее, чем до нейтрального элемента, объединяя их элементы в субэлементы. Нельзя собрать гомоморфный образ, который вел бы себя как группа. Наименьшая некоммутативная простая группа состоит из 60 элементов. Ее можно описать как группу вращений правильного додекаэдра, переводящих его в себя. При этом каждая из 12 граней додекаэдра может занимать пять различных положений – этим и объясняется число 60.

Первый пример неабелевых простых групп был открыт Галуа. Это знакопеременная группа An – подгруппа индекса 2 в симметричной группе перестановок Sn, состоящая из всех четных перестановок. Простота An, n≥5 трактуется как неразрешимость алгебраических уравнений степени, большей 4 (теорема Галуа).

Спорадическая простая группа – это такая группа, для которой нет простого и ясного описания. Это не группа вычетов и не группа вращений, такая невнятная группа. Вместо слова "невнятная" используют термин "спорадическая". Пять примеров спорадических простых групп в 1861 году дал Эмиль Матье. В 1965 году, спустя век, Звонимир Янко (cross-section method) обнаруживает группу из 23×3×5×7×11×19=175560 элементов, обозначаемую J1.



Звонимир Янко


Группа J2=JH имеет 27×33×5×7 элементов, ее интерпретацию перестановками нашел Холл (есть геометрические интерпретации Холла и Жака Тита). Компьютеры позволили построить более крупные примеры с J3, J4 (таблица). Монструозная группа порядка, выражаемого 54-мя цифрами (большой монстр) обнаруживает удивительные связи monster moonshine с теорией чисел, теорией модулярных форм и т.п.

Внутри всякой простой группы содержатся некие меньшие конструкции, называемые централизаторами инволюций, которые помогают понять, как устроена исходная группа. В случае групп Ри централизаторы инволюций допускают представление в виде группы квадратных матриц размера 2×2, составленных из элементов конечной числовой системы, размер которой (т.е. число ее элементов) равен некоторой нечетной степени числа 3.

Например, если 3 возводится в степень 1, то соответствующая конечная числовая система состоит из трех элементов группы вычетов по модулю 3. Для доказательства одной из ранних частичных классификационных теорем требовалось показать, что группы Ри – это единственные простые группы, обладающие следующим свойством: их централизаторы инволюций допускают представление 2×2-матрицами, составленными из элементов конечной числовой системы размера pm, где p – простое, а m – нечетное число. Первым естественным шагом к достижению этой цели была попытка доказать следующую гипотезу: если некоторая простая группа обладает указанным свойством, то размер конечной числовой системы, из которой берутся элементы 2×2-матриц, равен нечетной степени простого числа 3. Со временем эта гипотеза была проверена для всех случаев, кроме одного: когда pm = 51.

Янко приступил к исследованию этого исключительного случая в полной уверенности, что простой группы нужного типа с числовой системой размера 51, т.е. 5, не существует. Однако, несмотря на все усилия, ему не удалось исключить такую возможность и тем самым завершить доказательство гипотезы. Наоборот, потратив немало труда, он сумел показать, что если простая группа такого вида существует, то она состоит в точности из 23×3×5×7×11×19 (т.е. 175 560) элементов. Вряд ли Янко удалось бы установить столь сильный результат, если бы одна подходящая группа не маячила на горизонте. С растущим нетерпением он двинулся дальше и показал, что если такая группа существует, то она порождается двумя 7×7-матрицами, в столбцах и строках которых стоят элементы группы вычетов по модулю 11 (см. нижний рисунок на с. 65). Если обозначить две эти матрицы через A и B, то группа состоит из всевозможных матричных произведений вида AA, BB, ABA, BBAABABBB и т.д.

Оставалось только узнать, действительно ли эта группа содержит в точности 175 560 элементов; если бы это было не так, то рассуждения Янко приводили бы к противоречию, которое он искал с самого начала. На первый взгляд кажется удивительным, что всевозможные матричные произведения, составленные из A и B, эквивалентны всего лишь 175 560 матрицам (именно это и означает существование группы требуемого типа). Ведь сюда входят и произведения, содержащие более миллиона A и B. Общее число матриц размера 7×7 с элементами из группы вычетов по модулю 11 равно, грубо говоря, 1149 или 1051, и, значит, произведения этих двух порождающих матриц составляют среди них лишь ничтожную долю. Тем не менее вычисления, проведенные к тому же полностью вручную, подтвердили существование шестой спорадической группы, которая в честь Янко (Janko) называется теперь J1.

ПОЛНЕЕ | С КАРТИНКАМИ


Гомоморфизм. Приведем еще пару мудреных слов, связанных со свойствами "умножения". Возьмем два множества, поставленные в соответствие, например, матриц и их определителей. Определитель произведения матриц равен произведению определителей. Операция "произведение" реализуется у матриц и определителей отлично друг от друга, но если установлен гомоморфизм реализаций (соответствие обоих типов произведений друг другу), мы можем судить об определителе произведения матриц, умножая определители, а не матрицы. В данном случае соответствие (гомоморфизм) несет полезную нагрузку (а не "прокукарекал, а там хоть не раcсветай").

Ядро гомоморфизма. Ядром у матриц называется совокупность линейно-независимых между собой векторов, которые матрица аннулирует Ax=0 (проецирует в 0), обозначается X=ker(A). Иными словами, это решение матричного уравнения AX=0, X=[x1, x2, ... ]. Ядро гомоморфизма – сходное понятие, при гомоморфном отображении нейтральный элемент переходит в нейтральный же. Если еще есть элементы, переводимые в нейтральный, то они образуют ядро гомоморфизма. Большое ядро свидетельствует о некоторой избыточности того, что отображается на "более узкое" множество (как сужение реки).

Пример ядра гомоморфизма – нормальная подгруппа, которая по ее определению конструируется как совокопность элементов, играющих роль нейтрального элемента. Те же операции порождают основанную на нормальной подгруппе фактор-группу, более широкое образование, перед нами "естественный" гомоморфизм с ядром в виде нормальной подгруппы.

Изоморфизм. Биективный гомоморфизм (в обе стороны) называется изоморфизмом. Любая группа G изоморфна подгруппе симметрической группы S(G) (теорема Кэли).

Возьмем тот же пример с матрицами и их определителями. Разложив определитель на сомножители, нам не узнать, какие именно матрицы умножались (так как разные матрицы могут иметь одинаковые определители). Значит, соответствие (гомоморфизм, позволявший судить об определителе произведения матриц, умножая их определители) не работает в противоположную сторону, не установлен изоморфизм операций.

Автоморфизм. Если в соответствие поставлены элементы одного и того же множества (а не столь различные между собой множества, как матрицы и их определители), то гомоморфизм величают автоморфизмом.

По сути, теория групп связана с симметриями, присущими какой-либо системе. Представьте себе снежинку, вершины которой отстоят друг от друга на 60°. Если снежинку повернуть вокруг оси, проходящей через ее центр перпендикулярно к ее плоскости, на 60° или на число градусов, кратное 60, то ее вид в целом останется неизменным, даже если какая-нибудь вершина и изменила свое положение.

Показательная функция ak представляет собой "спираль", которая разматывается внутри группы и рано или поздно возвращается к исходному элементу 1. Следом идет опять a. Вот и симметрия. Операция, которая оставляет общий вид фигуры неизменным в этом смысле, называется операцией симметрии (автоморфизмом). Сами автоморфизмы складываются в группу, исследование симметрии, это выделение группы автоморфизмов.

Группы Ли. Элементами групп могут быть параметрические зависимости (многообразия), являющиеся решениями дифференциальных уравнений. Классификация решений на основе их групповых свойств выдвинула работы Софуса Ли, изучавшего симметрии движений механических систем.

Кольцо, это расширенное толкование поля (а поле знакомо нам со школы по законам арифметики) при котором мы не требуем обратимости операции умножения. Таблица умножения ненулевых элементов кольца содержит 0.

Тело, это кольцо, тесно связанное с мультипликативной группой, которая образуется из него выбрасыванием ненужного группе 0.

Идеал, это более крупное, чем элементы или циклические подгруппы (показательные функции) объединение элементов кольца, характеризуемое идентификатором. Множество всех четных чисел образует идеал в кольце целых чисел, этот идеал порожден элементом 2 (умножением на 2). Как видно, идеал сопричастен и операции умножения (масштабирования элементов) и идентификатору 2 (на что именно масштабируем).

Определение и роль идеала кольца сходны с определением нормальной подгруппы в теории групп. Для подмножества четных чисел все немножечко проще, чем более общей ситуации, возникают свойства, на которые мы можем опираться. То же самое происходит с группой, в которой есть нормальная подгруппа.

Если мы забываем о существовании нейтрального и обратных элементов, то мы можем толковать о подполугруппе. Если нас волнует только существование обратных элементов, а все остальное, неважно, в том числе возможность выхода за пределы множества, то такой полуфабрикат называется симметричным подмножеством.

Поле. Множество элементов, на котором определены две операции сложения и умножения (правила взяты из арифметики), называют полем. Поля с конечным числом элементов p называют полями Галуа по имени их первого исследователя (Galois) и обозначают GF(p) или, в более общем виде, GF(pm).

Мультипликативную группу поля образует поле Галуа без нулевого элемента. Такую группу обозначают как GF(pm)*. Эта группа является циклической, то есть в ней есть порождающий элемент, а все остальные получаются возведением в степень порождающего.

Теория полей и теория групп смыкаются – важнейшим свойством конечных полей является то, что множество всех ненулевых элементов конечного поля образует группу по операции умножения, т. е. мультипликативную группу порядка p–1.

Квадратичные вычеты. Операция "умножения" не выводит целые числа поля Галуа GF(p) за пределы этого поля, по определению (это и есть основание, для построения группы). Она связана с "возвращением" квадратов чисел в пределы выбранного числового диапазона.


Те места, куда квадраты чисел "возвращаются", называются квадратичные вычеты (quadratic residues). Прочие числа числового поля называются квадратичные невычеты.

Возводить числа в степень можно, разумеется, и в более, чем во вторую, причем операции "возвращения" накроют, в таком случае, все числа. В том случае, когда для покрытия элементов "рикошетами" хватает степеней одного числа, поле, по сути дела, из них и образовано.

Такое число именуют порождающим (а минимальное число – порядком группы). Элементы поля, без нуля, – основа мультипликативной группы, циклической. Поскольку элементы – остатки, их называют вычеты или классами вычетов (не путать с квадратичными).

Примитивные элементы групп полей Галуа GF(p)


Поле GF(p), p – простое число, имеет p элементов, нумеруемых как 0, 1, 2,..., p–1. Арифметика в GF(p), это арифметика по модулю p. Поэтому, обозначив элементы целыми числами, несложно сгенерировать F=GF(p) таблицы сложения F[0] и умножения F[1], и к ним, весь корпус арифметических функций.

Возведение в степень обнаруживает различие между элементами поля Галуа. Как можно заметить, если возводить в степень числа 3 либо 5 в поле Галуа GF(7), мы получим все элементы поля, кроме 0.

Такие числа называются примитивными элементами. Примитивному элементу ставят в соответствие минимальный (по порядку) полином, корнем которого он является. Такой полином с коэффициентами из поля Галуа – задает связь, которая позволяет выражать старшие степени примитивного элемента через младшие. Заметим, что каждый ненулевой элемент конечного поля GF(p) – корень из 1, поскольку Ap–1=1 для любого ненулевого элемента GF(p).

В кольце R последовательные произведения некоторого элемента g (генератора) на элемент кольца x, образуют циклическое подкольцо gx0, gx1, gx2, ..., gxv–1 (в полиномиальной арифметике соответствует, например, циклическому сдвигу коэффициентов полинома g вправо).

Группы полей Галуа GF(p2) для нечетных p


Построение полей Галуа GF(p2) для нечетных p облегчается гарантированным наличием неприводимых многочленов вида X2 – r, с r из GF(p), случай GF(22) разобран тут.

Более точно, полином вида X2 – r неприводим в GF(p) тогда и только тогда, когда r – квадратичный невычет модуля p (что следует из их определения). Как известно, общее число квадратичных невычетов равно (p–1)/2. Например, 2 – квадратичный невычет для p = 3, 5, 11, 13, ..., и 3 – квадратичный невычет для p = 5, 7, 17, ....

Пусть p ≡ 3 mod 4, тогда p = 3, 7, 11, 19, ..., выбрав −1 ≡ p − 1 как квадратичный невычет, получим очень простой нередуцируемый многочлен X2 + 1. Следовательно, элементы вида a+jb, где j – квадратичный корень из 1 (или, в общем, из r) – элементы поля GF(p2), правила сложения и вычитания их наследуют правилам комплексной арифметики.

Вычисляя цепочки степеней элемента, получаем информацию о мультипликативной структуре группы GF(p2)*. Рассмотрим GF(32). Элемент x=[–1,–1]=[2,2] дает циклическую группу c x32–1=1, ему отвечает корень –1–j1 примитивного многочлена X2+2X+2.

Орбиты элементов, стабилизатор и фиксатор


Циклические подгруппы xk и подкольца, называемые орбитами, позволяют изучить состав и характер множеств элементов входящих в мультипликативную группу кольца Z*v. Мы говорим о кольце, поскольку в орбиту включают 0.


Орбиты. Орбитой элемента m кольца Z*v называется итог масштабирования подгруппы H (подкольцо): Orb(m)=mH. Умножение на m=0 дает частную орбиту {0} (орбиту элемента 0), умножение на m=1 дает саму подгруппу H в качестве тривиальной орбиты, на m=2 – следующую частную орбиту и т.п. Частные орбиты описывают циклические подкольца кольца.

Масштабирование на элементы Z*v подгруппы H называется также действием подгруппы на кольцо. Орбита подгруппы Orb(H) – обозначение совокупности элементов всех частных орбит, ее и называют для большей простоты, орбитой H.



Подгруппы в Z*v=13, т.е. орбиты m=1 и орбиты m=2



Мы видим, что умножение на разные множители меняет значения элементов mH (элементов строк рисунков). Как обычно, интересуются неподвижными точками mh=m, h – элемент H.

Равные между собой hm=m точки (инварианты действия) можно считать по разному, в подгруппе H (замораживая m) или на множестве Z*v (замораживая h): получая элементы стабилизатора и фиксатора.

Стабилизатор. Равные в результате действия hm=m между собой элементы H образуют подгруппу в H, называемую стабилизатор Stab(m).

Фиксатор. Равные в результате действия hm=m между собой элементы Z*v образуют фиксатор элемента подгруппы Fix(h).



Классы эквивалентности H={8k} в Zv=13


Если орбиты двух элементов Z*v пересекаются, то они тождественны между собой (орбиты разбивают H на классы эквивалентности). Число классов эквивалентности (на рисунке 4) равно сумме числа стабилизаторов (их 16, если посчитать) по всем элементам группы, делённой на размер этой группы (на рисунке 4), согласно лемме Бернсайда.

Дициклическая группа


Циклическая группа порождается показательной функцией элемента xk. Число таких элементов: 4n – порядок группы.

Дициклическая группа генерируется не одним, а парой элементов, удовлетворяющих следующим требованиям. Половина элементов группы, это ak (или [k,0]), другая половина akx (или [k,1]), причем

Dicn = < a, x | a2n=1, x2 = an, x a x–1 = a–1 >


В качестве таких элементом можно указать a=eiπ/n=sin(π/n)+icos(π/n), x=j (i, j – корни из мнимой единицы). Группа Dicn имеет порядок 4n и содержит пару циклических подгрупп порядков 2n. Каждый элемент ее однозначно представлен как akxl, где 0 ≤ k < 2n и l = 0,1.

От комплексной арифметики указанных кватернионов, можно перейти к арифметике степеней, причем akam=ak+m, akamx=ak+mx, akxam=ak–m, akxamx=ak–m+nx.

Как только появились у нас обозначения, для элементов, с правилами арифметики, т.е. с операцией умножения, так у нас появилась возможность производить операции в группе. Какие операции? У группы выбор небольшой.

Вычисляя цепочки степеней элемента, получаем информацию о мультипликативной структуре группы, видны циклические подгруппы порядков 2n и 2.


Пусть G = <a> – подгруппа Dicn, генерируемая элементом a (минимальная группа, включающая элемент). Тогда G – циклическая группа. Группа порядка 2n имеет индекс [Dicn:G] = 2 (индекс показывает соотношение элементов). Как любая подгруппа с индексом 2, G автоматически нормальная подгруппа. Группа Dicn/G – циклическая группа порядка 2.

Линейная комбинация элементов группы (групповое кольцо) может быть записано в форме R=R1+R2x, R1, R2 ⊆ <a>. Отметим, что сэт D группы G называется относительным дифференциальным набором (a relative difference set, RDS) с запрещенной подгруппой N, если соблюдены условия для образования RDS. Запрещенная подгруппа здесь <x2>, с нею R1, R2 образуют составные части для нахождения двух бинарных последовательностей, с помощью которых строится матрица Адамара.

ВИКИ | ДИЦИКЛИЧЕСКАЯ ГРУППА

Алгоритм Драгомира поиска последовательностей Ито


Японский математик Ито, занимаясь дициклическими группами, высказал предположение о соответствии их матрицам Адамара, рассматриваемых, в частности, в негациклической форме. Содержательная сторона алгоритма Драгомира состоит в том, что рассчитывается "шкала" U и положение пары "стрелок" – вращаемых возведением в степень пары "комплексных" чисел проекций trace1, trace2. Когда "стрелки" указывают деления "шкалы" U, ставим –1 в бинарных последовательностях (a, b), порождающих динегациклическую матрицу N2, сводимую к негациклической N1.

ПОРТРЕТЫ МАТРИЦ ИТО



Rambler's Top100