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

[B@R5uk]

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

Сможете найти в ней нормальную подгруппу, фактор по которой не является подгруппой?

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

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

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

Первые два элемента — центр. Классы смежности по этой подгруппе образуют группу $K_4$ (ячейки 2x2 в таблице умножения), которая не является подгруппой $Q_8$.

Представить в виде произведения эту группу что-то не получается.

[ИСН]

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

Жизнь всегда сложнее, чем кажется на первый взгляд

Жизнь - не уверен, а теория групп - точно так. Вы коммутантами ещё не занимались?

[B@R5uk]

ИСН в сообщении #1468305 писал(а):

Вы коммутантами ещё не занимались?

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

[Roman_T]

Цитата:

три кольца 4-го порядка

Что это?

Цитата:

Представить в виде произведения эту группу что-то не получается.

И не получится. Почему?

[B@R5uk]

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

String[] seedLines = {"2 3 1 0 6 7 5 4", "4 5 7 6 1 0 2 3"};

Когда я был "в теме", то такое представление как-то напоминало мне, о какой группе идёт речь. Например, эта пара строк задаёт группу кватернионов с таблицей умножения парой постов выше. Но сейчас, когда прошло время, и я всё забыл, я смотрю на эти кипы чисел как на новые ворота. Благо, что программе всё равно, ей сунул, она прожевала и проглотила. Либо выплюнула, если исходные данные некорректны. Однако, мне нужна какое-то быстрое и человеческое представление того, что же за группа скрывается под каждым таким набором чисел.

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

И ещё вопрос по ходу. Рассматривая графы циклов групп малого порядка, заметил, что во многих группах на графе от единичного элемента выходят "лепестки": циклы длины 2, содержащие только один нетривиальных элемент. Такой элемент (2-го порядка), очевидно, невозможно представить в виде какой-либо степени какого-нибудь другого элемента. Это свойство является довольно отличительным, поскольку в группе чётного порядка довольно часто есть и другие элементы второго порядка, которые входят в циклы длины, большей, чем 2 (другими словами, представимы в виде степени). Для этих "лепестков" есть какое-нибудь специальное название?

[vpb]

Трагично, что пять месяцев ноутбук не могли починить.

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

Является ли граф циклов (его построение вроде как легко алгоритмизировать) однозначной характеристикой группы

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

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

Для этих "лепестков" есть какое-нибудь специальное название?

Нет, нету. Вообще элемент порядка 2 называется (часто) инволюцией. Или вообще никак не называется.

И, еще раз, настоятельно рекомендую читать учебники.

[B@R5uk]

vpb в сообщении #1491026 писал(а):

По-видимому, под "графом циклов" вы имеете в виду т.наз. граф Кэли.

Нет, не граф Кэли, а именно граф циклов. Например:

для группы $Z_4\times Z_2$.

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

[mihaild]

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

Другими словами, верно ли, что различные группы имеют различные графы циклов, или же одному и тому же графу циклов может соответствовать несколько групп?

Нет, неверно. Вроде бы самый простой контрпример (но не минимальный) - группа матриц вида $\begin{pmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix}$, где $a, b, c \in \mathbb Z_3$ - и некоторая абелева группа. Сможете найти циклический граф этой группы и абелеву группу с тем же циклическим графом?

[B@R5uk]

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

Нет, неверно.

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

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

Сможете найти циклический граф этой группы и абелеву группу с тем же циклическим графом?

Искать таблицу умножения 27 матриц 3 на 3? Это же 700 с хвостиком умножений этих матриц!

[mihaild]

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

Искать таблицу умножения 27 матриц 3 на 3?

Так вам не нужно строить эту таблицу. Порядки элементов этой группы найти сможете?

[B@R5uk]

А вообще, если подумать, то

$$\begin{pmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix} \times \begin{pmatrix} 1 & A & B \\ 0 & 1 & C \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & a+A & b+B+aC \\ 0 & 1 & c+C \\ 0 & 0 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix}^2 = \begin{pmatrix} 1 & 2a & 2b+ac \\ 0 & 1 & 2c \\ 0 & 0 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix}^3 = \begin{pmatrix} 1 & 3a & 3b+3ac \\ 0 & 1 & 3c \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} = I$$

Откуда получается, что все элементы группы этих матриц имеют порядок 3. Если учесть, что перемножение матриц — операция некоммутативная, то получается неабелева группа. Если верить списку групп малого порядка, то с указанными свойствами имеется только одна группа порядка 27: $Z_3^2\rtimes Z_3$. К сожалению, к ней не нарисовали графа циклов. Но, учитывая, что все элементы имеют порядок 3, то это будет $(27-1)/2=13$ двухэлементных лепестков, висящих на нейтральном элементе. По аналогии $Z_3^3$ должна иметь такой же граф циклов.

Забавный способ строить новые нетривиальные группы любого порядка. Ведь вместо $\mathbb{Z}_3$ можно было взять $\mathbb{Z}_n$. Надо поставить это на вооружение, написав программу, которая по заданному n будет строить таблицу умножения группы. Потом полученную группу можно будет разобрать на подгруппы и получить целый список всяких интересных групп, особенно, если n составное и достаточно большое.

[vpb]

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

Ведь вместо $\mathbb{Z}_3$ можно было взять $\mathbb{Z}_n$

Разумеется. Вообще, можно рассмотреть группу треугольных матриц с единицами на диагонали над любым кольцом (ассоциативным, не обязательно коммутативным). Например, над ${\mathbb Z}_n$, кольцом вычетов по модулю $n$ ; получается группа порядка $n^3$.

-- 07.11.2020, 21:03 --

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

Нет, не граф Кэли, а именно граф циклов. Например:

А, вот оно что. Мне это понятие как-то и не известно. В науке оно не используется (по моим сведениям).

[B@R5uk]

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

Вот, например, взять хотя бы группу $b^3 = c^3 = (bc)^3 = (b^2c)^6 = I$. В ней 108 элементов! По таблице умножения вообще ничего не поймёшь, а граф Кэли ещё попробуй красиво нарисуй. Не факт, что на плоскости выйдет что-то вразумительное. Графы Кэли больших групп на плоскости имеют тенденцию иметь кучу самопересечений, что сводит к нулю их читабельность. А вот для графа циклов я получил такую вот распечатку:

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

Cycles:
#0: [7, 31, 87, 42, 12, 0], L: 6
#1: [8, 32, 82, 39, 11, 0], L: 6
#2: [9, 35, 77, 36, 10, 0], L: 6
#3: [33, 106, 82, 107, 41, 0], L: 6
#4: [34, 107, 87, 106, 38, 0], L: 6
#5: [37, 107, 77, 106, 40, 0], L: 6
#6: [73, 32, 77, 39, 86, 0], L: 6
#7: [74, 31, 77, 42, 81, 0], L: 6
#8: [75, 39, 87, 32, 84, 0], L: 6
#9: [76, 42, 82, 31, 79, 0], L: 6
#10: [78, 36, 82, 35, 85, 0], L: 6
#11: [80, 35, 87, 36, 83, 0], L: 6
#12: [1, 3, 0], L: 3
#13: [2, 6, 0], L: 3
#14: [4, 19, 0], L: 3
#15: [5, 17, 0], L: 3
#16: [13, 26, 0], L: 3
#17: [14, 23, 0], L: 3
#18: [15, 21, 0], L: 3
#19: [16, 30, 0], L: 3
#20: [18, 29, 0], L: 3
#21: [20, 28, 0], L: 3
#22: [22, 55, 0], L: 3
#23: [24, 53, 0], L: 3
#24: [25, 51, 0], L: 3
#25: [27, 49, 0], L: 3
#26: [43, 66, 0], L: 3
#27: [44, 61, 0], L: 3
#28: [45, 64, 0], L: 3
#29: [46, 59, 0], L: 3
#30: [47, 57, 0], L: 3
#31: [48, 72, 0], L: 3
#32: [50, 71, 0], L: 3
#33: [52, 69, 0], L: 3
#34: [54, 70, 0], L: 3
#35: [56, 68, 0], L: 3
#36: [58, 98, 0], L: 3
#37: [60, 96, 0], L: 3
#38: [62, 95, 0], L: 3
#39: [63, 94, 0], L: 3
#40: [65, 92, 0], L: 3
#41: [67, 99, 0], L: 3
#42: [88, 101, 0], L: 3
#43: [89, 100, 0], L: 3
#44: [90, 105, 0], L: 3
#45: [91, 104, 0], L: 3
#46: [93, 103, 0], L: 3
#47: [97, 102, 0], L: 3


Special elements:
E 31 (order: 3), cycles (N: 3):
    #0 (L: 6)
    #7 (L: 6)
    #9 (L: 6)
E 32 (order: 3), cycles (N: 3):
    #1 (L: 6)
    #6 (L: 6)
    #8 (L: 6)
E 35 (order: 3), cycles (N: 3):
    #2 (L: 6)
    #10 (L: 6)
    #11 (L: 6)
E 36 (order: 3), cycles (N: 3):
    #2 (L: 6)
    #10 (L: 6)
    #11 (L: 6)
E 39 (order: 3), cycles (N: 3):
    #1 (L: 6)
    #6 (L: 6)
    #8 (L: 6)
E 42 (order: 3), cycles (N: 3):
    #0 (L: 6)
    #7 (L: 6)
    #9 (L: 6)
E 77 (order: 2), cycles (N: 4):
    #2 (L: 6)
    #5 (L: 6)
    #6 (L: 6)
    #7 (L: 6)
E 82 (order: 2), cycles (N: 4):
    #1 (L: 6)
    #3 (L: 6)
    #9 (L: 6)
    #10 (L: 6)
E 87 (order: 2), cycles (N: 4):
    #0 (L: 6)
    #4 (L: 6)
    #8 (L: 6)
    #11 (L: 6)
E 106 (order: 3), cycles (N: 3):
    #3 (L: 6)
    #4 (L: 6)
    #5 (L: 6)
E 107 (order: 3), cycles (N: 3):
    #3 (L: 6)
    #4 (L: 6)
    #5 (L: 6)
 

Сразу видно, что в группе есть 36 ничем не примечательных циклов порядка 3 и 12 циклов порядка 6, которые очень даже примечательны: в них куча общих элементов, которые имеют разный порядок, разное число общих циклов и разные позиции вхождения в эти циклы. Я не знаю, правда, какие дальнейшие выводы из этих наблюдений можно сделать, но это уже что-то интересное, плюс в плане трудоёмкости рассчитать это совсем не затратно.

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

[mihaild]

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

Если учесть, что перемножение матриц — операция некоммутативная, то получается неабелева группа

Вывод правильный, рассуждение - нет. У нас же подгруппа группы матриц, а в ней бывают и коммутативные подгруппы. Надо как-то убедиться, что наша подгруппа некоммутативная.

[mihaild]

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

найти в группе минимальное порождающее множество

Миниммальное (из которого нельзя ничего выкинуть) или наименьшее (содержащее минимально возможное число элементов)?
Впрочем ваш алгоритм даже минимальное не находит. Возьмем $S_3$ - ваш алгоритм возьмет сначала цикл длины $3$, потом еще цикл длины $3$, потом транспозицию. Хотя достаточно и одного цикла длины $3$ и транспозиции.