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

[B@R5uk]

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

А верно же, что имея элементы группы в виде произведения образующих можно восстановить всю таблицу умножения группы всего лишь по столбцам, соответствующим умножению на эти образующие?

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

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

int[][] restoreTable(int[][] arg) {
        int k, l, m, size, number;
        int[][] references, result;
        size = arg.length;
        number = arg[0].length;
        references = new int[size][number];
        result = new int[size][size];
        for (k = 0; size > k; ++k) {
                result[k][0] = k;
                for (l = 1; number >= l; ++l) {
                        m = arg[k][l - 1];
                        result[k][l] = m;
                        if (0 == references[m][1]) {
                                references[m][0] = k;
                                references[m][1] = l;
                        }
                }
        }
        for (k = number + 1; size > k; ++k) {
                for (l = 0; size > l; ++l) {
                        result[l][k] = result[result[l][references[k][0]]][references[k][1]];
                }
        }
        return result;
}
 

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

Каждый элемент $x$ группы можно представить как другой элемент $y$ группы, умноженный на одну из образующих $g$. Поэтому столбец умножения на элемент $x$ получается из столбца умножения на элемент $y$ перестановкой, задаваемой умножением на образующую $g$. Программа выше заполняет столбец умножения на единичный элемент (тривиальная перестановка), столбцы умножения на образующие, беря их из исходного массива arg, а затем — все остальные столбцы, применяя это правило.

[B@R5uk]

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

$\mathbb Z_{2^n}$ можно задать $n + 1$ соотношениями размера $O(\log n)$: $x_0 + x_0 = x_1$, $x_1 + x_1 = x_2$, ..., $x_{n - 1} + x_{n - 1} = x_n$, $x_n + x_n = x_n$.

Я правильно понимаю, что "плюс" здесь — это групповая операция, а в последнем групповом соотношении $x_n + x_n$ должно равняться единице группы?

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

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

На первой странице я решал задачу:

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

Покажите, что любая группа G с двумя образующими s и t, удовлетворяющими соотношениям

$$\begin{matrix}s^n=I,&sts^{-1}=t^k,\\ \end{matrix}$$

где n и k — целые числа, $n\ne 0, k>0$, будет группой конечного порядка. Покажите так же, что G не может содержать более чем $(k^n-1)n$ различных элементов.

Если ограничиться только этими двумя соотношениями, то их суммарная длина будет $n+k+8$ символов, включая знаки равенства, запятую и точку, а размер получающейся группы будет $(k^n-1)n$. Функция $n^n$ растёт чуть быстрее, чем экспонента, и, думаю, это тоже не предел.

[mihaild]

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

а в последнем групповом соотношении $x_n + x_n$ должно равняться единице группы?

Нейтральному элементу (раз уж группа аддитивная), и нет, это соотношение и утверждает что $x_n$ - нейтральный элемент (вообще при таком задании получаем $x_n = 2^n$).

[mihaild]

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

На первой странице я решал задачу

Да, и правда, вроде всё проходит.

[B@R5uk]

В группе тетраэдра $A_4$ оказывается есть нетривиальная подгруппа:

$$\left\{I,\;f,\;r^2fr,\;rfr^2\right\}$$

Если сделать замену $a=f,\;b=r^2fr$, то, поскольку $ab=ba=rfr^2$, получается как раз группа Клейна:

$$V_4=\left\{a^2=b^2=(ab)^2=I\right\}$$

Не то чтобы я сильно внимательно присматривался (если честно, совсем не присматривался), но пропустить этот важный момент — плохо.

[B@R5uk]

Я обнаружил что-то совершенно невероятное! Вот эта группа:



Содержит подгруппу:

$$\left\{I,\;c,\;b^3,\;cb^3,\;bcb^2,\;b^2cb,\;bcb^5,\;b^5cb\right\}$$

Её таблица умножения:

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

""         0   2   6  12  13  14  21  22
"c"        2   0  12   6  22  21  14  13
"bbb"      6  12   0   2  21  22  13  14
"bbbc"    12   6   2   0  14  13  22  21
"bbcb"    13  22  21  14   0  12   6   2
"bcbb"    14  21  22  13  12   0   2   6
"bcbbc"   21  14  13  22   6   2   0  12
"cbbcb"   22  13  14  21   2   6  12   0

Если присмотреться, то можно заметить, что это ни что иное, как $C_2\times C_2\times C_2$. То есть группа внутри себя содержит подгруппу более высокого ранга! Я точно нигде не ошибся? И если нет, то такое часто бывает?

[mihaild]

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

И если нет, то такое часто бывает?

Часто. Любая группа из $n$ элементов является подгруппой $S_n$, которая имеет ранг $2$.

[arseniiv]

B@R5uk
Я когда нашёл в свободной группе на двух элементах подгруппы, изоморфные свободным группам на любом другом конечном числе элементов, тоже долго не понимал, что это вообще было, но мне как раз тут вроде пояснили.

-- Пн мар 23, 2020 19:08:09 --

Хотя я всё забыл и снова удивляюсь.

[B@R5uk]

mihaild, спасибо.

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

Любая группа из $n$ элементов является подгруппой $S_n$

Я так понимаю, это теорема Кэли?

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

которая имеет ранг $2$.

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

-- 23.03.2020, 17:13 --

arseniiv в сообщении #1446538 писал(а):

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

Вот это вот очень сильно! И совсем не очевидно. Я понимаю, ещё квадрат на отрезок отобразить, но в группах же есть групповые аксиомы.

[mihaild]

arseniiv, это ИМХО примерно аналогично тому, что разница в длине между унарной и двоичной записями экспоненциальна, а между двоичной и с любым большим основанием - только в константу раз.

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

теорема Кэли?

Она самая.

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

Вот это не очевидно

Не очевидно, но несложно. Возьмите цикл $(12\ldots n)$ и транспозицию $(12)$.

[Munin]

https://en.wikipedia.org/wiki/Tetrahedral_symmetry
https://en.wikiversity.org/wiki/Symmetric_group_S4

https://en.wikipedia.org/wiki/Octahedral_symmetry
https://en.wikiversity.org/wiki/Full_octahedral_group

https://en.wikipedia.org/wiki/Icosahedral_symmetry

-- 23.03.2020 17:20:36 --

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

Вот это вот очень сильно! И совсем не очевидно.

Если подумать про свободную группу как про дерево, то можно понять, что внутри дерева с 3-кратным ветвлением можно найти вершины дерева с $n$-кратным ветвлением.

-- 23.03.2020 17:23:57 --

Munin в сообщении #1414290 писал(а):

Группы симметрии правильных многогранников - это:

полная группа тетраэдра $T_d$ - Wiki, Wikiversity, порядка 24;
полная группа октаэдра $O_h$ (она же группа симметрий куба) - Wiki, Wikiversity, порядка 48;
полная группа икосаэдра $I_h$ (она же группа симметрий додекаэдра) - Wiki, порядка 120.

Если запретить отражения - несобственные движения - то получаются "просто" (= хиральные) группы тетраэдра $T$ порядка 12, октаэдра $O$ порядка 24, икосаэдра $I$ порядка 60. (Эти обозначения - символы Шёнфлиса (Schönflies), придуманы в 19 веке для кристаллографии, и здесь уже не вполне удобны и логичны, но традиционны. Также есть нотация Коксетера и диаграммы Коксетера.) Эти полные группы порождаются отражениями, и они, и их подгруппы, называются группами Коксетера (Wiki), в комплексном случае - Shephard group (Wiki).

Кроме того, есть другие интересные родственные группы:

пиритоэдральная группа $T_h$ порядка 24, $T<T_h,$ $T_h\ncong T_d,$ Wikiversity;
бинарные группы $2T,2O,2I$ порядков 24, 48, 120, которые являются двойными накрытиями соответствующих хиральных групп, однако не содержат их в качестве подгрупп. $2T$ Wiki, $2O$ Wiki, $2I$ Wiki.

Все эти группы, кроме бинарных, могут быть реализованы как действительные матрицы $3\times 3,$ а бинарные - как комплексные матрицы $2\times 2.$ Таким образом, всё это конечные подгруппы в $\mathrm{O}(3),\mathrm{SO}(3),\mathrm{SU}(2).$ Кроме того, они изоморфны:

$T_d\cong O\cong S_4,$     $T\cong A_4=\mathrm{PSL}(2,3),$     $T_h\cong T\times\mathbb{Z}_2,$     $2T\cong Q\rtimes\mathbb{Z}_3,$
$O_h\cong S_2^3\rtimes S_3=S_4\times\mathbb{Z}_2,$     $O\cong S_4,$     $2O\cong?,$
$I_h\cong A_5\times\mathbb{Z}_2,$     $I\cong A_5=\mathrm{PSL}(2,4)=\mathrm{PSL}(2,5),$     $2I\cong\mathrm{SL}(2,5),$

где $S_n$ и $A_n$ - симметрическая и знакопеременная группы (группы перестановок и чётных перестановок), $Q$ - группа кватернионов (Wiki). $\mathrm{SL}(n,q)$ Wiki, $\mathrm{PSL}(n,q)=\mathrm{SL}(n,q)/Z(\mathrm{SL}(n,q))$ Wiki.

[arseniiv]

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

arseniiv, это ИМХО примерно аналогично тому, что разница в длине между унарной и двоичной записями экспоненциальна, а между двоичной и с любым большим основанием - только в константу раз.

О, это интересно!

[B@R5uk]

А есть какой-либо алгоритм, позволяющий перебрать все не изоморфные группы заданного размера?

[Xaositect]

Алгоритм-то точно есть (перебираем квадратные таблицы, выделяем из них таблицы Кэли групп, отсекаем изоморфные).
А вот насчет практических алгоритмов - это сложно. Можно посмотреть https://www.math.auckland.ac.nz/~obrien ... h/2000.pdf там есть общее описание, ссылки и данные о времени работы.
Данные доступны в GAP Small groups library (https://www.gap-system.org/Manuals/pkg/ ... chap0.html)

[B@R5uk]

Xaositect, спасибо.

-- 23.03.2020, 22:04 --

Не, статья имеет слишком высокий уровень, я не вкуриваю ни разу.

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

перебираем квадратные таблицы, выделяем из них таблицы Кэли групп, отсекаем изоморфные

Я так на бумажке пробовал ещё когда только заинтересовался группами. Гиблое дело, даже если отсекать таблицы, нарушающие свойства групп в процессе их построения. Будет слишком много изоморфных.

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

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