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

[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, спасибо. Выше моей квалификации, но всё равно спасибо за помощь и интерес в вопросе.