Свойства подгрупп группы

[B@R5uk]

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

Вот, например, абелевость. По определению группа/подгруппа абелева, когда любая пара её элементов коммутирует. То есть

$$\forall\,g_1,\,g_2\in G:\,g_1\cdot g_2=g_2\cdot g_1$$

Разумеется, вычислять в лоб по этому определению двумя вложенными циклами по всем элементам группы нерационально. Поэтому я придумал следующую оптимизацию: проверяем, что коммутирует любая пара образующих группы/подгруппы G. Корректность этой проверки следует из следующего утверждения:

Цитата:

Группа абелева тогда и только тогда, когда любая пара её образующих коммутирует.

В обратную сторону это утверждение очевидно. В прямую оно следует из того, что любой элемент группы представим в виде комбинации (слова) образующих (букв). Если записать два слова для двух элементов группы одно за другим, то за счёт того, что образующие коммутируют, можно первое слово по одной букве протащить за второе слово, что будет означать, что рассматриваемые элементы коммутируют. Разумеется, эта процедура работает только при условии конечности представления элементов группы, что верно для конечной группы. Что происходит в бесконечном случае — отдельный вопрос.

С нормальностью чуть-чуть интереснее. Подгруппа N группы G является нормальной, если любое сопряжение любого элемента $n\in N$ любым элементом $g\in G$ даёт элемент группы N:

$$\forall\,n\in N,\,g\in G\quad\exists n'\in N:n'=g^{-1}ng$$

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

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

Хотелось бы сократить и второй цикл: перебирать только образующие подгруппы N. Вопрос: можно ли?

[mihaild]

B@R5uk в сообщении #1559127 писал(а):

которая разбирает группу на подгруппы и вычисляет всевозможные свойства для последующего анализа

В первую очередь тут нужно спросить - как вы задаете группу и подгруппу.

B@R5uk в сообщении #1559127 писал(а):

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

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

B@R5uk в сообщении #1559127 писал(а):

Хотелось бы сократить и второй цикл: перебирать только образующие группы N. Вопрос: можно ли?

Ну вы посмотрите, как связано сопряжение данным элементом произведения с сопряжением им же сомножителей.

[B@R5uk]

mihaild в сообщении #1559128 писал(а):

...что любой элемент группы раскладывается в их конечное произведение

Действительно. Спасибо за уточнение.

mihaild в сообщении #1559128 писал(а):

В первую очередь тут нужно спросить - как вы задаете группу и подгруппу.

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

mihaild в сообщении #1559128 писал(а):

Ну вы посмотрите, как связано сопряжение данным элементом произведения с сопряжением им же сомножителей.

Ну, получается что-то в духе

$$(word)^{\sigma\lambda o\nu o}=\left(\left(\left(\left(w^{\sigma}\right)^{\lambda}\right)^o\right)^{\nu}\right)^o\left(\left(\left(\left(o^{\sigma}\right)^{\lambda}\right)^o\right)^{\nu}\right)^o\left(\left(\left(\left(r^{\sigma}\right)^{\lambda}\right)^o\right)^{\nu}\right)^o\left(\left(\left(\left(d^{\sigma}\right)^{\lambda}\right)^o\right)^{\nu}\right)^o$$

С последующим разложением каждой внутренней степени внутреннего сопряжения на образующие подгруппы с разделением сопряжений произведения на произведение сопряжений и повтором этого приёма до победного. То есть, получается всё-таки достаточно проверить только образующие как для всей группы, так и для подгруппы. Верно?

[mihaild]

B@R5uk в сообщении #1559131 писал(а):

Ну, получается что-то в духе

Зачем так сложно? Докажите, что
1) если $x^\alpha \in N$ и $y^\alpha \in N$ то и $(xy)^\alpha \in N$
2) из 1) следует, что множество элементов, все сопряженные к которым лежат в $N$, замкнуто относительно групповой операции
3) а если множество замкнуто относительно групповой операции, и содержит образующие подгруппы, то что можно про него сказать?

[B@R5uk]

mihaild в сообщении #1559132 писал(а):

Докажите, что

Ну, первое свойство очевидно из определения что такое сопряжение. Третье означает, что мы имеем дело подгруппой-прообразом N, но поскольку образующие те же, то это та же группа, причём она инвариантна относительно всех сопряжений группы G. Да, это последовательное и красивое доказательство. Спасибо.

Я тут подумал и придумал ещё одну оптимизацию. Мой процесс поиска подгрупп заключается в следующем. Сначала ищется список всех циклических подгрупп (они имеют ранг один). Все последующие подгруппы получаются замыканием относительно групповой операции объединения двух каких-либо подгрупп. Месить все подгруппы нерационально, поэтому я делаю следующее. Для очередной доставаемой из очереди подгруппы H перебираются все циклические подгруппы C, каждая циклическая $C\ne C\cap H$ (то есть, содержащая элементы, отсутствующие в H, или, что то же самое, не содержащаяся в H) строится замыкание объединения (обзовём это слияние для краткости). Такой подход хорош ещё тем, что ранг новой подгруппы (если она действительно новая, а не совпадает с одной из ранее найденных) на единицу больше ранга исходной подгруппы H.

Применительно к свойствам подгруппы этот процесс так же позволяет сделать оптимизацию (собственно, о чём и речь): теперь не надо по новой проверять нормальность и центральность вновь полученной подгруппы. Она будет нормальной или центральной, если, соответственно, обе сливаемые подгруппы были нормальными или центральными. То есть проверку надо будет делать только на первом этапе для циклических подгрупп. В дальнейшем проверка выполняется в одно действие — конъюнкцией.

С абелевостью чуть-чуть сложнее: сливаемые подгруппы должны быть абелевыми (автоматически выполнено для циклической подгруппы), а их образующие должны взаимно коммутировать. Получается, новая подгруппа будет абелевой, если исходная подгруппа H так же была абелевой, а ещё образующие коммутируют с образующей подгруппы C, с помощью которой порождается новая подгруппа. Куда более эффективно, чем проверять двумя вложенными циклами по всем элементам подгруппы!

[B@R5uk]

Подгруппа $H_1\subseteq G$ содержит подгруппу $H_2\subseteq G$ тогда и только тогда, когда она содержит образующие погруппы $H_2$. Следует из определения образующих, как и раньше. Я же нигде не ошибся?

Вообще, множество образующих — мощная штука, получается. Их количество в группе G как правило $O\left(1\right)$ и всего $O\left(\log\left|G\right|\right)$ в худшем случае.

[svv]

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

[B@R5uk]

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

Я как-то в старых программах пытался находить все порождающие множества группы (и делить их на классы эквивалентности относительно изоморфзимов для удобства), но это жутко медленно работает, так как для больших групп таких порождающих множеств бывает тьма тьмущая (224 для группы Паули и 9576 для $\operatorname{Aut}\left(\mathbb{Z}_2^3\right)$ с порядком всего 168, к примеру). И нужно это бывает только для построения всевозможных топологически различных графов Кэли группы. В новой программе множество образующих нужно для работы (в отличие от старой), но я ограничился одним-единственным для скорости. Перебор всех различных классов множеств можно будет сделать потом отдельной процедурой по запросу.

[svv]

Это здорово.

(Оффтоп)

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

[B@R5uk]

B@R5uk в сообщении #1559146 писал(а):

Она будет нормальной или центральной, если, соответственно, обе сливаемые подгруппы были нормальными или центральными.

Косяк, косяк. Слияние двух не нормальных подгрупп может дать нормальную. Простейший контрпример — $D_6$. В ней есть три подгруппы 2-го порядка, все они не являются нормальными, но их слияние даёт всю группу целиком, которая является нормальной подгруппой внутри себя. Да это тривиальная подгруппа, но можно привести примеры честной подгруппы с такими же свойствами ( $\operatorname{Z}(G)\times_G\mathbb{Z}_2=K_4\triangleleft D_8=G$ ). В чём дело?