Задача по теории групп

[Munin]

Xaositect в сообщении #1446626 писал(а):

Данные доступны в GAP Small groups library

Ещё (для групп, обозримых глазом) советую GroupProps Wiki https://groupprops.subwiki.org/wiki/Main_Page
Ну и совсем для маленьких: https://en.wikipedia.org/wiki/List_of_small_groups

И убиться талмудом (формата A4):
Conway J.H. et al. Atlas of finite groups. Maximal Subgroups and Ordinary Characters for Simple Groups. 1985.

[B@R5uk]

Теорема Лагранжа утверждает, что порядок любой подгруппы делит порядок группы, а верно ли обратное? Найдётся ли в группе такая подгруппа, что её порядок равен заданному делителю порядка группы?

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

[Xaositect]

$A_4$ (порядок 12) не содержит подгрупп порядка 6.

Если порядок раскладывается на простые множители как $|G| = p_1^{m_1} \dots p_n^{m_n}$, то всегда есть подгруппы порядков $p_k^{m_k}$ - силовские подгруппы. Следовательно, есть и подгруппы с меньшими показателями.

[B@R5uk]

Xaositect в сообщении #1446853 писал(а):

$A_4$ (порядок 12) не содержит подгрупп порядка 6.

Точно! Это я должен был это заметить, когда игрался с ней. Xaositect, спасибо.

Xaositect в сообщении #1446853 писал(а):

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

То есть простые делители ранга группы всегда имеют подгруппу соответствующего порядка. Это может немного упростить перебор групп заданного порядка.

[Munin]

Xaositect в сообщении #1446853 писал(а):

Если порядок раскладывается на простые множители как $|G| = p_1^{m_1} \dots p_n^{m_n}$, то всегда есть подгруппы порядков $p_k^{m_k}$ - силовские подгруппы. Следовательно, есть и подгруппы с меньшими показателями.

Простите, я не понял, как второе из первого следует.

[Xaositect]

Это известный факт из теории $p$-групп. Если $p$-простое, то группа порядка $p^n$ содержит нормальную подгруппу порядка $p^m$ для любого $m \leq n$.
Это доказывается из того, что центр такой группы нетривиален, это уже даст подгруппы до некоторого $p^{k_1}$ (для абелевых групп утверждение доказывается просто), а дальше мы берем фактор-группу по центру и поднимаем ее подгруппы в прообразы в исходной группе, и по индукции все получается.

[Munin]

А, то есть "из этого и ещё кое-каких неозвученных фактов следует". Спасибо за подробности!

[B@R5uk]

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

Есть тут один интересный приём — заполнять таблицу по скелету нейтральных элементов...

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

На самом деле всё просто: каждая вновь заполненная ячейка таблицы (с помощью очередной гипотезы) ведёт за собой ещё пять заполненный ячеек (всего шесть):

$$\begin{align*} ab&=c\\ b^{-1}a^{-1}&=c^{-1}\\ a^{-1}c&=b\\ c^{-1}a&=b^{-1}\\ cb^{-1}&=a\\ bc^{-1}&=a^{-1}\end{align*}$$

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

[Munin]

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

[B@R5uk]

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

[Munin]

А, это не элементы группы, это элементы таблицы Кэли. Тогда пусть его...

[B@R5uk]

Решил пока отложить скелет в дальний ящик и отклониться в сторону комбинаторики. А именно: решать задачу в лоб. Ясное дело, никаких новых интересных для себя групп я не найду, так как они начинаются с размера 12, 18 и более (что компьютеру не под силу перебрать), но посмотреть что получится всегда интересно.

Идея заключается в следующем. Первые строка и столбец таблицы умножения группы заполняются по умолчанию последовательно числами от 1 до n, где n — порядок группы. Дальше встаёт вопрос, как заполнить вторую строчку и что из этого можно получить. Я выше уже писал, что таблица умножения группы сильно избыточна, в частности, в случае циклической группы (ранг 1) достаточно всего одной строки, чтобы восстановить всю таблицу умножения. В общем же случае, из любой k-ой строки таблицы

$$\left(\begin{matrix}r_1=k\times 1=k,&r_2=k\times 2&r_3=k\times 3&\ldots&r_n=k\times n\\ \end{matrix}\right)$$

можно извлечь информацию, чтобы заполнить по крайней мере ещё одну строчку. Всё потому, что в этой строке всегда есть элемент $r_{\bar{k}}=k\times \bar{k}=1$ и элемент $r_k=k\times k=k^2$. Проще работать с последним равенством. С помощью него можно найти строку, соответствующую умножению на $k^2=r_k$ слева. Она будет равна

$$\left(\begin{matrix}r_{r_1}&r_{r_2}&r_{r_3}&\ldots&r_{r_n}\\ \end{matrix}\right)$$

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

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

0  1  2  3  4  5  6  7
1  5  4  6  3  7  2  0
2  -  -  -  -  -  -  -
3  -  -  -  -  -  -  -
4  -  -  -  -  -  -  -
5  7  3  2  6  0  4  1
6  -  -  -  -  -  -  -
7  0  6  4  2  1  3  5


1x0=1
1x1=5
1x2=4
1x3=6
1x4=3
1x5=7
1x6=2
1x7=0

5x0=1x1x0=1x1=5
5x1=1x1x1=1x5=7
5x2=1x1x2=1x4=3
5x3=1x1x3=1x6=2
5x4=1x1x4=1x3=6
5x5=1x1x5=1x7=0
5x6=1x1x6=1x2=4
5x7=1x1x7=1x0=1

7x0=1x5x0=1x5=7
7x1=1x5x1=1x7=0
7x2=1x5x2=1x3=6
7x3=1x5x3=1x2=4
7x4=1x5x4=1x6=2
7x5=1x5x5=1x0=1
7x6=1x5x6=1x4=3
7x7=1x5x7=1x1=5

1x7x0=1x7=0
1x7x1=1x0=1
1x7x2=1x6=2
1x7x3=1x4=3
1x7x4=1x2=4
1x7x5=1x1=5
1x7x6=1x3=6
1x7x7=1x5=7
 

Поскольку строки таблицы (кроме первой) одна не хуже другой, то я решил заполнять вторую строчку. Сначала мне показалось, что будет $(n-1)!$ вариантов заполнения, потому что второй элемент во второй строчке будет стоять на первом месте. Но потом я сообразил, что, поскольку первая строка уже заполнена, то не все перестановки элементов, начинающиеся со 2-го, будут удовлетворять групповым аксиомам. Из них надо отсеять те перестановки, в которых номер элемента совпадает с его позицией. Вычислительный эксперимент даёт такие результаты:

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

===============
     #   1  2
---------------
     1:  2  1
===============

==================
     #   1  2  3
------------------
     1:  2  3  1
==================

=====================
     #   1  2  3  4
---------------------
     1:  2  1  4  3
     2:  2  3  4  1
     3:  2  4  1  3
=====================


========================
     #   1  2  3  4  5
------------------------
     1:  2  1  4  5  3
     2:  2  1  5  3  4
     3:  2  3  1  5  4
     4:  2  3  4  5  1
     5:  2  3  5  1  4
     6:  2  4  1  5  3
     7:  2  4  5  1  3
     8:  2  4  5  3  1
     9:  2  5  1  3  4
    10:  2  5  4  1  3
    11:  2  5  4  3  1
========================

===========================
     #   1  2  3  4  5  6
---------------------------
     1:  2  1  4  3  6  5
     2:  2  1  4  5  6  3
     3:  2  1  4  6  3  5
     4:  2  1  5  3  6  4
     5:  2  1  5  6  3  4
     6:  2  1  5  6  4  3
     7:  2  1  6  3  4  5
     8:  2  1  6  5  3  4
     9:  2  1  6  5  4  3
    10:  2  3  1  5  6  4
    11:  2  3  1  6  4  5
    12:  2  3  4  1  6  5
    13:  2  3  4  5  6  1
    14:  2  3  4  6  1  5
    15:  2  3  5  1  6  4
    16:  2  3  5  6  1  4
    17:  2  3  5  6  4  1
    18:  2  3  6  1  4  5
    19:  2  3  6  5  1  4
    20:  2  3  6  5  4  1
    21:  2  4  1  3  6  5
    22:  2  4  1  5  6  3
    23:  2  4  1  6  3  5
    24:  2  4  5  1  6  3
    25:  2  4  5  3  6  1
    26:  2  4  5  6  1  3
    27:  2  4  5  6  3  1
    28:  2  4  6  1  3  5
    29:  2  4  6  3  1  5
    30:  2  4  6  5  1  3
    31:  2  4  6  5  3  1
    32:  2  5  1  3  6  4
    33:  2  5  1  6  3  4
    34:  2  5  1  6  4  3
    35:  2  5  4  1  6  3
    36:  2  5  4  3  6  1
    37:  2  5  4  6  1  3
    38:  2  5  4  6  3  1
    39:  2  5  6  1  3  4
    40:  2  5  6  1  4  3
    41:  2  5  6  3  1  4
    42:  2  5  6  3  4  1
    43:  2  6  1  3  4  5
    44:  2  6  1  5  3  4
    45:  2  6  1  5  4  3
    46:  2  6  4  1  3  5
    47:  2  6  4  3  1  5
    48:  2  6  4  5  1  3
    49:  2  6  4  5  3  1
    50:  2  6  5  1  3  4
    51:  2  6  5  1  4  3
    52:  2  6  5  3  1  4
    53:  2  6  5  3  4  1
===========================
 

Если внимательно присмотреться, то можно заметить, что функция $b(n)$ числа допустимых перестановок для второй строчки, табличка которой:

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

n       (n-1)!          b(n)
1       1               0
2       1               1
3       2               1
4       6               3
5       24              11
6       120             53
7       720             309
8       5040            2119
9       40320           16687
10      362880          148329
11      3628800         1468457
 

удовлетворяет формуле

$$b\left( n \right)=\left( n-3 \right)b\left( n-2 \right)+\left( n-2 \right)b\left( n-1 \right)$$

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

[B@R5uk]

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

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

n       b(n)            bad             2       3       4       5       6       7       8       9       10      11      12
1       0               0               -       -       -       -       -       -       -       -       -       -       -
2       1               0               1       -       -       -       -       -       -       -       -       -       -
3       1               0               -       1       -       -       -       -       -       -       -       -       -
4       3               0               1       -       2       -       -       -       -       -       -       -       -
5       11              5               -       -       -       6       -       -       -       -       -       -       -
6       53              18              3       8       -       -       24      -       -       -       -       -       -
7       309             189             -       -       -       -       -       120     -       -       -       -       -
8       2119            1204            15      -       180     -       -       -       720     -       -       -       -
9       16687           11367           -       280     -       -       -       -       -       5040    -       -       -
10      148329          99840           105     -       -       8064    -       -       -       -       40320   -       -
11      1468457         1105577         -       -       -       -       -       -       -       -       -       362880  -
12      16019531        11649186        945     22400   113400  -       604800  -       -       -       -       -       3628800
 

Первый столбец — порядок группы, второй — количество не конфликтующих перестановок второй строки, третий — количество некорректных перестановок из числа не конфликтующих. В столбцах, озаглавленных числами — количество перестановок, для которых элемент 2 имеет соответствующий порядок (он делит прядок группы в первом столбце). Для каждой строки сумма чисел третьего и последующих столбцов равна числу во втором столбце. Забавно, что число перестановок, которым соответствует циклическая группа равно $(n-2)!$.

-- 01.04.2020, 21:09 --

Последовательность $b(n)$ — это сдвинутая последовательность A000255. Код программы поиграться:

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

public class Study_Group_Table_Permut_2 {
        
        public static void main(String[] args) {
                int k, l, size, count;
                int[] secondLine, tempLine, ord;
                boolean flag;
                boolean[][] tableFlags;
                size = 12;
                secondLine = new int[size];
                ord = new int[size];
                secondLine[0] = 1;
                secondLine[1] = 0;
                for (k = 2; size > k; ++k) {
                        secondLine[k] = k;
                }
                count = 0;
                while (true) {
                        getNextPermutation(secondLine);
                        if (1 != secondLine[0]) {
                                break;
                        }
                        flag = true;
                        for (k = 1; size > k; ++k) {
                                if (k == secondLine[k]) {
                                        flag = false;
                                        break;
                                }
                        }
                        if (flag) {
                                ++count;
                                //System.out.print(String.format("%6d:", count));
                                //display(secondLine);
                                tempLine = getFirstLine(size);
                                tableFlags = new boolean[size][size];
                                l = 0;
                                do {
                                        ++l;
                                        tempLine = getProduct(secondLine, tempLine);
                                        for (k = 1; size > k; ++k) {
                                                if (tableFlags[k][tempLine[k]]) {
                                                        flag = false;
                                                }
                                                tableFlags[k][tempLine[k]] = true;
                                        }
                                } while (0 != tempLine[0]);
                                for (k = 1; size > k; ++k) {
                                        if (k != tempLine[k]) {
                                                flag = false;
                                                break;
                                        }
                                }
                                if (flag) {
                                        ++ord[l - 1];
                                        //System.out.println(String.format(",%5d", l));
                                } else {
                                        ++ord[0];
                                        //System.out.println(",  bad");
                                }
                        }
                }
                System.out.println();
                System.out.println(String.format("bad:%8d", ord[0]));
                for (k = 1; size > k; ++k) {
                        if (0 != ord[k]) {
                                System.out.println(String.format("%3d:%8d", k + 1, ord[k]));
                        }
                }
        }
        
        private static void display(int[] arg) {
                int k;
                for (k = 0; arg.length > k; ++k) {
                        System.out.print(String.format("%3d", arg[k] + 1));
                }
        }
        
        private static boolean getNextPermutation(int[] arg) {
                int k, l, temp;
                k = arg.length;
                do {
                        --k;
                        if (0 == k) {
                                return false;
                        }
                } while (arg[k - 1] > arg[k]);
                temp = arg[k - 1];
                l = arg.length;
                do {
                        --l;
                } while (temp > arg[l]);
                arg[k - 1] = arg[l];
                arg[l] = temp;
                l = arg.length - 1;
                while (k < l) {
                        temp = arg[k];
                        arg[k] = arg[l];
                        arg[l] = temp;
                        ++k;
                        --l;
                }
                return true;
        }
        
        private static int[] getFirstLine(int arg) {
                int k;
                int[] result = new int[arg];
                for (k = 0; arg > k; ++k) {
                        result[k] = k;
                }
                return result;
        }
        
        private static int[] getProduct(int[] arg1, int[] arg2) {
                int k, size;
                size = arg1.length;
                int[] result = new int[size];
                for (k = 0; size > k; ++k) {
                        result[k] = arg1[arg2[k]];
                }
                return result;
        }
}
 

[B@R5uk]

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

$$\left(\begin{matrix}1&2&3&4&5&6&7&8&9&10\\2&3&4&5&6&7&8&9&10&1\\ \end{matrix}\right)$$

$$\left(\begin{matrix}1&2&3&4&5&6&7&8&9&10\\2&3&4&5&1&7&8&9&10&6\\ \end{matrix}\right)$$

Первая сразу даёт таблицу умножения циклической группы:

$$\left[\begin{matrix}1&2&3&4&5&6&7&8&9&10\\2&3&4&5&6&7&8&9&10&1\\3&4&5&6&7&8&9&10&1&2\\4&5&6&7&8&9&10&1&2&3\\5&6&7&8&9&10&1&2&3&4\\6&7&8&9&10&1&2&3&4&5\\7&8&9&10&1&2&3&4&5&6\\8&9&10&1&2&3&4&5&6&7\\9&10&1&2&3&4&5&6&7&8\\10&1&2&3&4&5&6&7&8&9\\ \end{matrix}\right]$$

Вторая даёт только часть таблицы умножения:

$$\left[\begin{matrix}1&2&3&4&5&6&7&8&9&10\\2&3&4&5&1&7&8&9&10&6\\3&4&5&1&2&8&9&10&6&7\\4&5&1&2&3&9&10&6&7&8\\5&1&2&3&4&10&6&7&8&9\\6&-&-&-&-&-&-&-&-&-\\7&-&-&-&-&-&-&-&-&-\\8&-&-&-&-&-&-&-&-&-\\9&-&-&-&-&-&-&-&-&-\\10&-&-&-&-&-&-&-&-&-\\ \end{matrix}\right]$$

Тут встаёт вопрос как быстро генерировать в лексикографическом порядке перестановки для следующей пустой строки так, чтобы не было повторений в столбцах. Перебор (n-1)! вариантов с отсеиванием — очень медленно.

[B@R5uk]

Обнаружил забавную вещь: группу диэдра $Dih_n$ можно задать в симметричном виде с помощью двух образующих второго порядка: $Dih_n=\langle a,\;b\;|\;a^2=b^2=\left(ab\right)^n=I\rangle$. Граф Кэли для такого задания представляет собой просто 2n-многоугольник с чередующимися рёбрами-образующими. Чтобы это представление свести к обычному заданию $Dih_n=\langle r,\;f\;|\;r^n=f^2=\left(ab\right)^2=I\rangle$, можно, например, сделать замену $a=rf,\;b=f,\;ab=r$. Поясняющие картинки для случая $n=4$: