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

[dgwuqtj]

Если вы хотите в каком-то виде хранить все подгруппы вообще, то почему бы не хранить их как абстрактную решётку? То есть сразу поддерживая операции "пересечь две подгруппы" и "взять подгруппу, порождённую двумя данными", ну и с возможностью проверять на включения. Я сходу не могу сказать, какая структура данных тут лучше подходит, но явно что-то графовое (для начала — ориентированный граф из подгрупп, где рёбра соответствуют включению подгрупп, между которыми нет промежуточных). Заодно у каждой подгруппы можно посчитать нормализатор $\mathrm N_G(H) = \{g \in G \mid H^g = H\}$, это позволит быстро проверять нормальность включения одной подгруппы в другую.

Кстати, какое-то описание подгрупп $A \times B$ в общем случае тоже есть, прочитайте про лемму Гурса. Причём эта лемма применима и к бесконечным группам, например, с её помощью можно за разумное время руками классифицировать конечные подгруппы $\mathrm{SO}(4)$ с точностью до сопряжения.

[B@R5uk]

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

почему бы не хранить их как абстрактную решётку?

Это как?

[dgwuqtj]

Ладно, насчёт структуры данных я не уверен. Зато нашёл ссылку, там указана книжка (Butler, Fundamental algorithms for permutation groups) с описанием нормального алгоритма для поиска всех подгрупп.

[B@R5uk]

Алгоритм по ссылке не очень: он требует предварительного знания идеальных групп и не позволяет находить ранк группы и её подгрупп. Необходимость предварительного знания лишает его универсальности, когда можно её добиться с нуля. Хотя сам по себе интересный подход.

Книжку скачал, читаю, вникаю. Спасибо.

[dgwuqtj]

Perfect groups — это совершенные группы, и таких среди групп маленького порядка немного: у них должен быть неабелевый композиционный фактор, так что наименьший порядок такой группы — это $60$, за исключением тривиальной группы. А для больших порядков уже самих подгрупп слишком много. Совершенные группы малых порядков $60$, $120$, $168$ (вторая неабелева простая группа), $180$ можно легко описать руками с точностью до изоморфизма, ну и такие подгруппы по идее как-то легко ищутся для каждого порядка по отдельности.

Например, совершенные подгруппы порядка $60$ (изоморфные $\mathrm A_5$) порождаются парами нетривиальных элементов $a$, $b$ с соотношениями $a^2 = b^3 = (a b)^5 = 1$, а совершенные подгруппы порядка $120$ (изоморфные бинарной группе икосаэдра) порождаются тройками элементов $a$, $b$, $c$ с соотношениями $a^2 = b^3 = c^5 = a b c$ при $a b c \neq 1$ (тут любая из образующих выражается через другие, так что перебирать достаточно пару элементов). Это гуглится по ключевым словам "группа фон Дика" и "универсальные центральные расширения симметрических групп". Совершенные группы порядка $168$ тоже все изоморфны $\mathrm{PSL}(2, 7) \cong \langle S, T \mid S^7 = T^2 = (S T)^3 = (S^4 T)^4 = 1 \rangle$, представление взято отсюда.

Вас вообще группы какого порядка интересуют?

[B@R5uk]

Ну, группа $\mathrm{PSL}(2,7)$ — это мой старый знакомый. Я как только построение группы автоморфизмов запрограммировал, так сразу опробовал его на $\mathrm C_2^3$ с очевидным результатом. У меня даже три различные представления запасено:

$$\begin{array}{l} \mathrm{PSL}(2,7)=\bigl\langle\;a,\;b\;|\;a^7=b^3=(ab)^4=(a^2b)^2=I\;\bigr\rangle\\ \mathrm{PSL}(2,7)=\bigl\langle\;a,\;b\;|\;a^7=b^4=(ab)^3=(ab^3)^2=I\;\bigr\rangle\\ \mathrm{PSL}(2,7)=\bigl\langle\;a,\;b\;|\;a^2=b^3=(ab)^7=(abab^2)^4=I\;\bigr\rangle\\ \end{array}$$

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

Используется синтаксис Text

Reduction set (4 relations):
    bbb -> 1
    aabaab -> 1
    aaaaaaa -> 1
    abababab -> 1

...

Iteration: 33
...

Nodes created/traversed total: 5826 / 2421367

Reduction set (43 relations):
    bbb -> 1
    aaaaa -> baab
    aabaa -> bb
    ababb -> baba
    baaba == abaab
    babab -> aba
    bbaba -> abab
    aabbaab -> bbaaa
    abaaaba -> bab
    baabbaa -> aaabb
    bbaaabb -> aabbaa
    aaabbaaa -> baaaab
    aababaab -> bbaaaa
    abaaaaba -> babbab
    abaabbab -> baaaba
    baaabbab == abbabbaa
    baabbabb == aaaababa
    babbaaab == aabbabba
    bbaaaabb -> aababaa
    bbabbaab == ababaaaa
    aaabbabba -> babaaaab
    aabbaaaab -> bbabbaaa
    aabbabbab -> baaabbaa
    abbabbaaa -> baaaabab
    baaaabbaa -> aaabbabb
    babaaaabb == abaaabbaa
    babbabbaa -> aabbaaab
    babbabbab -> abbaabba
    bbaaaabab == aabbaaaba
    aaababaaab -> bbabbabba
    aababaaaab -> baaabba
    aabbaaabab -> bbaaababa
    ababaaabba -> babbaaaab
    abbaaababa -> baaaabbab
    baaaababaa -> abbaaab
    baaaabbabb -> abbaaaaba
    baaababaaa -> abbabbabb
    babaaabbaa -> ababaaabb
    babbaaaaba == aababaaabb
    babbaabbab -> aaababaaa
    bbaaababaa == abaaaabbab
    bbabbaaaab -> abaaaabba
    aaaababaaaa -> bbabbabb

================================================
Generator multiplication table:
   0           1           a           b
   1           b          ba          bb
   2          bb         bba           1
   3           a          aa          ab
   4          aa         aaa         aab
   5         aaa        aaaa        aaab
   6        aaaa        baab       aaaab
   7          ba         baa         bab
   8         baa        baaa        baab
   9        baab       abaab       baabb
  10         aab        aaba        aabb
  11        aaba          bb       aabab
  12          ab         aba         abb
  13         aba        abaa        abab
  14        abab       ababa        baba
  15         bab        baba        babb
  16        baba       babaa         aba
  17        abaa       abaaa       abaab
  18       abaab           1      abaabb
  19         bba        bbaa        bbab
  20        bbab        abab       bbabb
  21        aabb       aabba          aa
  22       aabba      aabbaa      aabbab
  23      aabbaa     aabbaaa       bbaaa
  24        bbaa       bbaaa       bbaab
  25       bbaaa      bbaaaa      bbaaab
  26       abaaa      abaaaa      abaaab
  27      abaaab         bab     abaaabb
  28       baabb      baabba         baa
  29      baabba       aaabb     baabbab
  30        aaab       aaaba       aaabb
  31       aaabb      aaabba         aaa
  32      bbaaab     bbaaaba      aabbaa
  33      aaabba     aaabbaa     aaabbab
  34     aaabbaa      baaaab      abbaaa
  35        baaa       baaaa       baaab
  36       baaaa       bbaab      baaaab
  37      baaaab     baaaaba     baaaabb
  38       aabab      aababa       ababa
  39      aababa     aababaa       aaaba
  40     aababaa    aababaaa      bbaaaa
  41      bbaaaa         aab     bbaaaab
  42      abaaaa      abbaab     abaaaab
  43     abaaaab      babbab    abaaaabb
  44        babb       babba          ba
  45       babba      babbaa      babbab
  46      babbab      abaabb     babbabb
  47      abaabb     abaabba        abaa
  48     abaabba      aaaabb      baaaba
  49       baaab      baaaba      baaabb
  50      baaaba        babb     baaabab
  51      baaabb     baaabba        baaa
  52     baaabba    baaabbaa    abbabbaa
  53         abb        abba           a
  54        abba       abbaa       abbab
  55       abbab       aabab      abbabb
  56      abbabb     abbabba        abba
  57     abbabba    abbabbaa    abbabbab
  58    abbabbaa    baaaabab   aababaaaa
  59     baabbab     baaabab    aaaababa
  60       aaaab      aaaaba      aaaabb
  61      aaaaba        aabb     aaaabab
  62     aaaabab    aaaababa     aaababa
  63    aaaababa   aaaababaa      baabba
  64      babbaa     babbaaa     babbaab
  65     babbaaa    babbaaaa    aabbabba
  66      aabbab      aaabab     aabbabb
  67     aabbabb    aabbabba       aabba
  68    aabbabba   aabbabbaa    baaabbaa
  69     bbaaaab    bbaaaaba     aababaa
  70       bbabb      bbabba         bba
  71      bbabba     bbabbaa     bbabbab
  72     bbabbaa    bbabbaaa    ababaaaa
  73       ababa      ababaa        aaba
  74      ababaa     ababaaa     ababaab
  75     ababaaa    ababaaaa    ababaaab
  76    ababaaaa     babaaab   ababaaaab
  77     aaabbab     aaaabab    aaabbabb
  78    aaabbabb    babaaaab      aaabba
  79       babaa      babaaa      babaab
  80      babaaa     babaaaa     babaaab
  81     babaaaa     babbaab    babaaaab
  82    babaaaab     bbabbab   abaaabbaa
  83     aabbaaa    aabbaaaa    aabbaaab
  84    aabbaaaa       aaaab    bbabbaaa
  85    bbabbaaa   bbabbaaaa   aaaababaa
  86    baaabbaa     bbaaaab     babbaaa
  87     baaaaba       baabb    baaaabab
  88    baaaabab   baaaababa    baaababa
  89     baaaabb    baaaabba       baaaa
  90    baaaabba    aaabbabb   baaaabbab
  91     abaaabb    abaaabba       abaaa
  92    abaaabba   abaaabbaa   aabbabbaa
  93   abaaabbaa    abbaaaab     babaaaa
  94     babbabb    babbabba       babba
  95    babbabba    aabbaaab    abbaabba
  96    aabbaaab   aabbaaaba    aaaabbaa
  97       abbaa      abbaaa      abbaab
  98      abbaab     ababaab     abbaabb
  99     abbaabb    abbaabba       abbaa
 100    abbaabba     abaaabb   abbaabbab
 101    bbaaaaba      bbaabb   aabbaaaba
 102   aabbaaaba     aabbabb   bbaaababa
 103       aaaba         abb      aaabab
 104      aaabab     aaababa      aababa
 105     aaababa    aaababaa      aaaaba
 106    aaababaa   aaababaaa     abbaaaa
 107   aaababaaa  aaababaaaa   bbabbabba
 108     bbabbab     babaabb    bbabbabb
 109    bbabbabb   bbabbabba      bbabba
 110   bbabbabba     aaabbab   babbaabba
 111    aababaaa   aababaaaa   aababaaab
 112   aababaaaa    ababaaab     baaabba
 113     bbaaaba       bbabb    bbaaabab
 114    bbaaabab   bbaaababa    babaabba
 115   bbaaababa  abaaaabbab    bbaaaaba
 116    ababaaab       abbab   ababaaabb
 117   ababaaabb   babbaaaab     ababaaa
 118    babbaaaa       baaab   babbaaaab
 119   babbaaaab  aababaaabb   baaababaa
 120      abbaaa     abbaaaa     abbaaab
 121     abbaaab    abbaaaba     aaabbaa
 122    abbaaaba      abbabb   abbaaabab
 123   abbaaabab   baaaabbab   ababaabba
 124   baaaabbab    bbaabbab   abbaaaaba
 125   baaaababa     abbaaab     bbaabba
 126     abbaaaa        aaab    abbaaaab
 127    abbaaaab   abbaaaaba    aaababaa
 128   abbaaaaba     abbaabb    baaaabba
 129     baaabab    baaababa     abaabba
 130    baaababa   baaababaa     baaaaba
 131   baaababaa   abbabbabb    babbaaaa
 132    abbabbab    ababaabb   abbabbabb
 133   abbabbabb  abbabbabba     abbabba
 134     babaaab        bbab    babaaabb
 135    babaaabb   babaaabba      babaaa
 136   babaaabba   ababaaabb  aaaababaaa
 137   aababaaab      aabbab  aababaaabb
 138  aababaaabb    babbaabb    aababaaa
 139     babbaab      abaaab    babbaabb
 140    babbaabb   babbaabba      babbaa
 141   babbaabba    babaaabb   aaababaaa
 142    abaaaabb   abaaaabba      abaaaa
 143   abaaaabba   aaaabbabb  abaaaabbab
 144  abaaaabbab   abbaabbab   bbabbaaaa
 145   bbabbaaaa      bbaaab   abaaaabba
 146   aaaababaa  aaaababaaa    aabbaaaa
 147  aaaababaaa    bbabbabb  abbabbabba
 148       bbaab      babaab      bbaabb
 149      aaaabb     aaaabba        aaaa
 150      babaab           b     babaabb
 151      bbaabb     bbaabba        bbaa
 152     aaaabba    aaaabbaa    aaaabbab
 153     ababaab          ab    ababaabb
 154     babaabb    babaabba       babaa
 155     bbaabba      baaabb    bbaabbab
 156    aaaabbaa     abaaaab     aabbaaa
 157    aaaabbab     baabbab   aaaabbabb
 158    ababaabb   ababaabba      ababaa
 159    babaabba     baaaabb     bbaaaba
 160    bbaabbab    bbaaabab   baaaababa
 161   aaaabbabb   ababaaaab     aaaabba
 162   aabbabbaa     babbabb  aaababaaaa
 163   ababaaaab    abbabbab     bbabbaa
 164   ababaabba    abaaaabb    abbaaaba
 165   abbaabbab   abbaaabab    babbabba
 166  aaababaaaa   aababaaab    abaaabba
 167  abbabbabba    aaaabbab   babaaabba
Order: 168
================================================
 

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

Вас вообще группы какого порядка интересуют?

Чем больше, тем лучше. Группы автоморфизмов большими бывают, а смотреть на них самый смак. Так то у меня порой и полторы тыщи порядок группы с текущим алгоритмом комп тянет. Как повезёт с числом автоморфизмов и с произведением числа циклов на число подгрупп. Превышение первого порога приводит к вылету с ошибкой о нехвате памяти, а второго — к практическому зависанию из-за долгого времени расчёта. У меня результаты никуда не сохраняются, а после построения списка подгрупп, я часто хочу глянуть как некоторые из них устроены. Для этого я должен отредактировать код, вбив в него номер соответствующей подгруппы для изучения, и запустить работу программы по-новой. Если время ожидания больше 10-15 секунд, то для меня это можно считать превышение лимита времени. Пока жду, отвлекусь и/или забуду что хотел.

-- 12.02.2025, 20:23 --

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

Perfect groups — это совершенные группы

Совершенными у нас называют ещё и те, у которых все автоморфизмы внутренние. Вернее, если вики верить, то их и называют совершенными (complete group). А "perfect" группы вроде как правильно звать Каиновыми группами. Без понятия, как правильно, и почему нормально как "полная" и "идеальная" перевести не могли.

[dgwuqtj]

Я тут подумал, по идее совершенных групп довольно мало, можно просто взять их список с порядками до нескольких тысяч и руками доказать, что других нет. Правда, это упирается в CFSG, точнее — что в похожем списке из конечных простых групп других нет. Насчёт терминологии — я привык переводить perfect как совершенная, у специалистов по конечным группам и по комбинаторной теории групп могут быть свои традиции.

[B@R5uk]

Пусть H — некоторая собственная подгруппа группы G и g — элемент, этой подгруппе не принадлежащий. Пусть он порождает циклическую подгруппу C:

$$H\le G,\qquad g\in G\setminus H,\qquad C=\bigl\langle\;g\;\bigr\rangle$$

Я пытаюсь понять, какие тут возможны варианты в общем случае для замыкания подгруппы H с элементом g.

Выше рассмотрен случай, когда для некоторого простого числа p выполняется:

$$\bigl|H\bigr|\cdot p=\bigl|G\bigr|\quad\Longrightarrow\quad\bigl\langle\;H,\;g\;\bigr\rangle=G$$

Мне кажется это можно обобщить:

$$f=\frac{\bigl|C\bigr|}{\bigl|H\cap C\bigr|},\quad|H|\cdot f=\bigl|G\bigr|\quad\Longrightarrow\quad\bigl\langle\;H,\;g\;\bigr\rangle=G$$

Смысл в том, что если положительное число f — минимальная степень элемента g, которая отправляет его в подгруппу H (эта степень может равняться нейтральному элементу, тогда f является порядком элемента g), то подгруппа H будет иметь f различных смежных классов, порождёнными степенями элемента g от 1 до f включительно (или от 0 до f не включая). Поскольку их количество равно отношению порядков группы G и подгруппы H, то они покрывают всю группу целиком. Я же правильно рассуждаю?

[dgwuqtj]

Да, всё так.

[B@R5uk]

dgwuqtj, спасибо.

То есть в плане моих искомых всевозможных вариантов получается такая трихотомия:

$$\begin{array}{l|cccc} &\qquad&\bigl\langle\;H,\;C\;\bigr\rangle<G&\qquad&\bigl\langle\;H,\;C\;\bigr\rangle=G\\ \hline\\ \bigl|H\bigr|\bigl|C\bigr|<\bigl|G\bigr|\bigl|H\cap C\bigr|&&\text{1) возможно}&&\text{2) возможно}\\ \\ \bigl|H\bigr|\bigl|C\bigr|=\bigl|G\bigr|\bigl|H\cap C\bigr|&&\text{невозможно}&&\text{3) возможно} \end{array}$$

Для меня практический смысл в том, что если G и H — это вложенные подгруппы какой-то другой более общей группы, то обнаружив этот факт вложения, можно пройтись по элементам g и сразу отметить случай 3) для всех пар подгруппа-цикл. Это позволит в дальнейшем избежать повторных вычислений. К сожалению, различить случаи 1) и 2) без непосредственно вычисления замыкания не получится. Но, поскольку в результате может получиться третья новая подгруппа, то это сразу делать и не надо, потому что если делать это вне очереди, то ранк новой подгруппы может быть определён ошибочно.

Ещё забавно, что эти три случая никак не связаны с тем, является ли подгруппа H (и/или даже цикл C) нормальными в группе G. (Ну, может, кроме того, что случай 2, вроде бы, невозможен?). В качестве примера мне вспоминается группа $\mathrm A_5$ порядка 60, которая простая (и поэтому не имеет нормальных подгрупп), но содержит подгруппы $\mathrm A_4$ и $\mathrm C_5$, произведение порядков которых (12 и 5, соответственно) даёт порядок исходной группы. Разумеется, пересечение пары таких подгрупп содержит только нейтральный элемент.