Число подгрупп группы

[B@R5uk]

Как быстро может расти число подгрупп группы G с ростом её порядка n? Как вообще подходить к этой задаче?

Единственный подход к оценке мне видится через рассмотрение наихудшего случая. Единственное, что приходит в голову — это группа

$$G=\mathbb{Z}_2^r$$

У неё каждый элемент образует группу (с нейтральным), каждая пара элементов образует группу (после замыкания) и так далее. В результате число подгрупп:

$$s=\sum\limits_{k=0}^{r}C_n^{\min(k,\;r-k)}\simeq O\left(n^{r/2}\right)=O\left(\exp\frac{\ln^2n}{2\ln 2}\right)$$

Но является ли этот пример наихудшим, и правильно ли я прикинул число подгрупп?

[dgwuqtj]

Вот тут есть обсуждение, в качестве верхней оценки на число подгрупп упоминается $O(n^{(1/4 + o(1)) \log_2 n})$

[B@R5uk]

dgwuqtj, спасибо. Оценка похоже чем-то на мою в общих чертах, хотя я и не правильно число подгрупп у $\mathbb{Z}_2^r$ почитал. Не говоря про то, что вместо n надо было взять n-1, многие подгруппы в моей формуле выше повторяются из-за того, что одну и ту же подгруппу можно задать несколькими способами. Контр-пример: у группы $\mathbb{Z}_2^4$ подгрупп вида $\mathbb{Z}_2^2$ имеется 35 штук, а не $C_{15}^2=105$.

[B@R5uk]

А какие вообще существуют методы поиска подгрупп?

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

Сложность операции замыкания (при правильной реализации), дающей подгруппу H группы G

$$O(mr)=O(nr),\quad m=|H|,\quad n=|G|$$

где r — это наибольший возможный ранк подгруппы, его можно оценить как логарифм порядка n группы. Для каждой подгруппы и каждого элемента пробуется эта операция, то есть сложность всего алгоритма будет

$$O(sn^2r)$$

где s — это количество подгрупп в группе. Казалось бы, хороший полиномиальный алгоритм, жить и радоваться. Вот только третья степень по n (если считать величины s и n одного порядка) радоваться мешает. Уже для групп порядка тысячи величина куба сравнима с частотой процессора, и это не учитывая константу времени. В результате поиск подгрупп для групп размера от тысячи делается значительно дольше, чем несколько секунд. И чем дальше в лес, тем страшнее ночь.

Самое обидное, что большинство подгрупп находится почти сразу, а львиная доля работы алгоритма заключается в том, что он проверяет, что действительно можно получить группу целиком (взяв несколько образующих) тьмой тьмущей способов. И это не удивительно; во многих группах ранка 2 почти любая пара элементов (за редкими исключениями) может быть взята как образующие группы. Тут так и напрашивается оптимизация: каким-то способом быстро проверять (без построения замыкания), что текущий набор образующих (одна новая и остальные из обрабатываемой подгруппы) порождает уже найденную подгруппу (как правило группу целиком).

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

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

[dgwuqtj]

Есть такой обзор. Вам лучше правда изучать эту тему систематически.

[B@R5uk]

dgwuqtj, спасибо. Выше моей квалификации, но всё равно спасибо за помощь и интерес в вопросе.

[B@R5uk]

В продолжение темы. Справедливо ли следующее утверждение?

Пусть G — конечная группа и H — её собственная подгруппа. Пусть так же выполнено:

$$g\in G/H,\qquad|G|=p|H|$$

где p — простое число. Тогда замыкание подгруппы H и элемента g относительно групповой операции равняется группе G целиком:

$$\bigl\langle\;H,\;g\;\bigr\rangle=G$$

Конец леммы.

В случае когда простое число p является двойкой утверждение очевидно. Подгруппа H даже является нормальной и умножение её на элемент g (с любой стороны) даёт её смежный класс, который дополняет её до все группы G. В случае произвольного простого числа это не очевидно и с какой стороны подходить к доказательству я не представляю. Может от противного? Допустить, что равенство для замыкания не верно, но тогда должна существовать подгруппа, порядок которой больше H (так как элемент g лежит вне её и замыкание должно даль больший результат), но меньше G (так любая подгруппа отличная от неё будет меньше), что в принципе возможно, если порядок G является составным числом с кучей простых множителей (в степенях).

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

[dgwuqtj]

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

Допустить, что равенство для замыкания не верно, но тогда должна существовать подгруппа, порядок которой больше H (так как элемент g лежит вне её и замыкание должно даль больший результат), но меньше G (так любая подгруппа отличная от неё будет меньше)

Порядок этой промежуточной группы делит $|G|$ и делится на $|H|$, а $|G| / |H|$ у вас простое.

Разве что разность множеств обозначается как $G \setminus H$, а то у вас написано, что $g$ — это произвольный смежный класс...

[B@R5uk]

dgwuqtj в сообщении #1674310 писал(а):

Порядок этой промежуточной группы делит $|G|$ и делится на $|H|$, а $|G| / |H|$ у вас простое.

То есть лемма всё-таки работает. Спасибо! И это здорово. Теперь всякий раз, когда для подгруппы A расширенная подгруппа

$$B=\bigl\langle\;A,\;g\;\bigr\rangle,\qquad g\in B\setminus A$$

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

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

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

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

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

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

[dgwuqtj]

А вы не думали одну из образующих перебирать не из всей $G$, а из множества представителей классов сопряжения? Например, у $\mathrm S_6$ всего $11$ классов сопряжённости, а элементов $720$.

[B@R5uk]

В смысле 720 элементов распадаются на 11 орбит относительно внутренних автоморфизмов? Не совсем представляю как это можно использовать для построения списка подгрупп или хотя бы для распознавания, когда получается которая из найденных. Потому что, когда часть генераторов фиксируется, для остальных орбиты расщепляются и становятся меньше (как правило). Другими словами, если элементы a и b группы принадлежат одному классу сопряжённости, то это не значит что в паре с элементом d они дадут одну и ту же подгруппу. Если они дают разные, то фиксация элемента d расщепляет исходную орбиту и элементы a и b попадают в разные части. Это происходит потому, что набор автоморфизмов, оставляющих элемент d неподвижным значительно меньше набора всех автоморфизмов (пусть даже и внутренних). Ну, за исключением случаев, когда элемент d — какой-то особенный (нейтральный или единственный центральный, например).

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

[dgwuqtj]

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

Внутренних автоморфизмов мало у абелевых групп и чего-то похожего на них, но нильпотентные группы (и абелевы в том числе) всё равно надо сначала раскладывать в произведение $p$-подгрупп, которые в общем случае будут меньше.

[B@R5uk]

То есть, если группа G представима в виде

$$G=A\times B,\qquad A\cap B=\bigl\{I\bigr\}$$

то любая подгруппа группы G представима в виде двух множителей, где один берётся из A, другой — из B и других подгрупп не существует? С полупрямым произведение тоже самое? Фактически, если это верно и найти быстрый метод факторизации группы, то получается реализовать подход "Разделяй и властвуй".

[dgwuqtj]

Нет, но это будет верно, если $|A|$ и $|B|$ взаимно просты. Контрпример: возьмите диагонально вложенную $\mathrm C_2 \leq \mathrm C_2 \times \mathrm C_2$. Про полупрямые произведения не скажу.

[B@R5uk]

Да, это я ерунду написал, пока был афк, сам понял. С полупрямыми вообще всё запущено. В группе

$$\mathrm C_7\rtimes\mathrm C_3$$

Кроме двух тривиальных подгрупп и нормального цикла 7-го порядка целых семь циклов 3-го порядка. В сумме 21 элемент:

$$7\times(3-1)+7=21$$

Случаи, когда имеется прямое произведения и порядки сомножителей взаимно просты, слишком редки, к сожалению.

-- 12.02.2025, 14:39 --

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