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

[B@R5uk]

Xaositect, Munin, как много всего! Спасибо!

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

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

B@R5uk, а что вы собственно хотите научиться делать?

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

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

Element     Inverse     Order  Multiplication Table
""          ""          1      0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47
"b"         "bb"        3      1   3   4   0   7   8   9   2  13  17  14  19  15   5  21  26  22   6  28  23  24  10  39  11  34  36  12  37  31  32  33  18  45  41  20  42  44  40  43  16  27  30  46  47  25  29  35  38
"c"         "cc"        3      2   5   6  10  11  12   0  16  17  18  19  20   1  25  26  27  28  29  30   3   4  33  34  35  36  37  38  39   7   8   9  40  41  42  43  44  45  13  14  15  46  47  21  22  23  24  31  32
"bb"        "b"         3      3   0   7   1   2  13  17   4   5   6  21  23  26   8  10  12  39   9  31  11  34  14  16  19  20  44  15  40  18  45  41  28  29  30  24  46  25  27  47  22  37  33  35  38  36  32  42  43
"bc"        "ccbb"      3      4   8   9  14  19  15   1  22   6  28  23  24   3  36  12  37  31  32  33   0   7  41  20  42  44  40  43  16   2  13  17  27  30  46  47  25  29   5  21  26  35  38  10  39  11  34  18  45
"cb"        "cbcb"      3      5  10  11   2  16  17  18   6  25  29  26   3  27  12  33  38  34   0   7  35  36  19  15  20  43  45   1  13  40  41  42  30  24  47   4  21  23  46  22  28  39   9  31  32  37   8  44  14
"cc"        "c"         3      6  12   0  19  20   1   2  28  29  30   3   4   5  37  38  39   7   8   9  10  11  42  43  44  45  13  14  15  16  17  18  46  47  21  22  23  24  25  26  27  31  32  33  34  35  36  40  41
"bbc"       "ccb"       4      7  13  17  21  23  26   3  39   9  31  11  34   0  44  15  40  18  45  41   1   2  30  24  46  25  27  47  22   4   5   6  37  33  35  38  36  32   8  10  12  42  43  14  16  19  20  28  29
"bcb"       "cbc"       4      8  14  19   4  22   6  28   9  36  32  12   0  37  15  41  43  20   1   2  42  44  23  26  24  47  29   3   5  27  30  46  33  34  38   7  10  11  35  39  31  16  17  18  45  40  13  25  21
"bcc"       "cbb"       4      9  15   1  23  24   3   4  31  32  33   0   7   8  40  43  16   2  13  17  14  19  46  47  25  29   5  21  26  22   6  28  35  38  10  39  11  34  36  12  37  18  45  41  20  42  44  27  30
"cbb"       "bcc"       4     10   2  16   5   6  25  29  11  12   0  33  35  38  17  19   1  15  18  40  20  43  26  28   3   4  23  27  46  30  24  47   7   8   9  36  31  37  39  32  34  13  42  44  14  45  41  21  22
"cbc"       "bcb"       4     11  17  18  26   3  27   5  34   0   7  35  36  10  45   1  13  40  41  42   2  16  47   4  21  23  46  22  28   6  25  29  39   9  31  32  37   8  12  33  38  44  14  19  15  20  43  30  24
"ccb"       "bbc"       4     12  19  20   6  28  29  30   0  37   8  38  10  39   1  42  14  43   2  16  44  45   3  27   4  22  24   5  25  46  47  21   9  36  32  11  33  35  31  34   7  15  18  40  41  13  17  23  26
"bbcb"      "cbcbb"     3     13  21  23   7  39   9  31  17  44  45  15   1  40  26  30  47  24   3   4  46  25  11  12  34  38  32   0   8  37  33  35  41  20  43   2  14  19  42  16  18  22   6  28  29  27   5  36  10
"bcbb"      "bccbb"     3     14   4  22   8   9  36  32  19  15   1  41  42  43   6  23   3  26  28  27  24  47  12  31   0   7  11  37  35  33  34  38   2  13  17  44  18  40  16  45  20   5  46  25  21  29  30  10  39
"bccb"      "bbcbb"     3     15  23  24   9  31  32  33   1  40  13  43  14  16   3  46  21  47   4  22  25  29   0  37   7  39  34   8  36  35  38  10  17  44  45  19  41  42  18  20   2  26  28  27  30   5   6  11  12
"cbbc"      "ccbcc"     3     16  25  29  33  35  38  10  15  18  40  20  43   2  23  27  46  30  24  47   5   6   9  36  31  37  39  32  34  11  12   0  13  42  44  14  45  41  17  19   1  21  22  26  28   3   4   7   8
"cbcb"      "cb"        3     17  26   3  11  34   0   7  18  45  41   1   2  13  27  47  22   4   5   6  21  23  35  38  36  32   8  10  12  39   9  31  42  43  14  16  19  20  44  15  40  28  29  30  24  46  25  37  33
"cbcc"      "ccbcb"     3     18  27   5  35  36  10  11  40  41  42   2  16  17  46  22  28   6  25  29  26   3  31  32  37   8  12  33  38  34   0   7  44  14  19  15  20  43  45   1  13  30  24  47   4  21  23  39   9
"ccbb"      "bc"        3     19   6  28  12   0  37   8  20   1   2  42  44  14  29   3   5  27  30  46   4  22  38   7  10  11  35  39  31   9  36  32  16  17  18  45  40  13  15  41  43  25  21  23  26  24  47  33  34
"ccbc"      "ccbbc"     3     20  29  30  38  10  39  12  43   2  16  44  45  19  24   5  25  46  47  21   6  28  32  11  33  35  31  34   7   0  37   8  15  18  40  41  13  17   1  42  14  23  26   3  27   4  22   9  36
"bbcbb"     "bccb"      3     21   7  39  13  17  44  45  23  26   3  30  46  47   9  11   0  12  31  37  34  38  15  18   1   2  19  40  42  41  20  43   4   5   6  25  28  27  22  29  24   8  35  36  10  32  33  14  16
"bcbbc"     "ccbccbb"   3     22  36  32  41  42  43  14  26  28  27  24  47   4  11  37  35  33  34  38   8   9  17  44  18  40  16  45  20  19  15   1   5  46  25  21  29  30   6  23   3  10  39  12  31   0   7   2  13
"bccbb"     "bcbb"      3     23   9  31  15   1  40  13  24   3   4  46  25  21  32   0   8  37  33  35   7  39  43   2  14  19  42  16  18  17  44  45  22   6  28  29  27   5  26  30  47  36  10  11  12  34  38  41  20
"bccbc"     "ccbbcbb"   3     24  32  33  43  14  16  15  47   4  22  25  29  23  34   8  36  35  38  10   9  31  45  19  41  42  18  20   2   1  40  13  26  28  27  30   5   6   3  46  21  11  12   0  37   7  39  17  44
"cbbcb"     "cbccbcb"   3     25  33  35  16  15  18  40  29  23  24  27   5  46  38   9  32  36  10  11  31  37  20   1  43  14  41   2  17  13  42  44  47   4  22   6  26   3  21  28  30  34   0   7   8  39  12  45  19
"cbcbb"     "bbcb"      3     26  11  34  17  18  45  41   3  27   5  47  21  22   0  35  10  38   7  39  36  32   1  40   2  16  20  13  44  42  43  14   6  25  29  23  30  46  28  24   4  12  31  37  33   8   9  19  15
"cbccb"     "ccbccbc"   3     27  35  36  18  40  41  42   5  46  25  22  26  28  10  31  33  32  11  34  37   8   2  13  16  15  43  17  45  44  14  19  29  23  24   3  47  21  30   4   6  38   7  39   9  12   0  20   1
"ccbbc"     "ccbc"      3     28  37   8  42  44  14  19  27  30  46   4  22   6  35  39  31   9  36  32  12   0  18  45  40  13  15  41  43  20   1   2  25  21  23  26  24  47  29   3   5  33  34  38   7  10  11  16  17
"ccbcb"     "cbcc"      3     29  38  10  20  43   2  16  30  24  47   5   6  25  39  32  34  11  12   0  33  35  44  14  45  41  17  19   1  15  18  40  21  22  26  28   3   4  23  27  46   7   8   9  36  31  37  13  42
"ccbcc"     "cbbc"      3     30  39  12  44  45  19  20  46  47  21   6  28  29  31  34   7   0  37   8  38  10  40  41  13  17   1  42  14  43   2  16  23  26   3  27   4  22  24   5  25   9  36  32  11  33  35  15  18
"bccbbc"    "ccbcbb"    4     31  40  13  46  25  21  23  37  33  35   7  39   9  42  16  18  17  44  45  15   1  28  29  27   5  26  30  47  24   3   4  36  10  11  12  34  38  32   0   8  41  20  43   2  14  19  22   6
"bccbcb"    "cbccbb"    4     32  43  14  24  47   4  22  33  34  38   8   9  36  16  45  20  19  15   1  41  42  25  21  29  30   6  23   3  26  28  27  10  39  12  31   0   7  11  37  35   2  13  17  44  18  40   5  46
"cbbcbb"    "cbbcbb"    2     33  16  15  25  29  23  24  35  38  10   9  31  32  18  20   2   1  40  13  43  14  27  30   5   6   3  46  21  47   4  22  11  12   0  37   7  39  34   8  36  17  44  45  19  41  42  26  28
"cbcbbc"    "ccbbcb"    4     34  45  41  47  21  22  26  38   7  39  36  32  11  20  13  44  42  43  14  17  18  29  23  30  46  28  24   4   3  27   5  12  31  37  33   8   9   0  35  10  19  15   1  40   2  16   6  25
"cbccbb"    "bccbcb"    4     35  18  40  27   5  46  25  36  10  11  31  37  33  41   2  17  13  42  44  16  15  22   6  26   3  21  28  30  29  23  24  34   0   7   8  39  12  38   9  32  45  19  20   1  43  14  47   4
"cbccbc"    "cbccbc"    2     36  41  42  22  26  28  27  32  11  34  37   8  35  43  17  45  44  14  19  18  40  24   3  47  21  30   4   6   5  46  25  38   7  39   9  12   0  10  31  33  20   1   2  13  16  15  29  23
"ccbbcb"    "cbcbbc"    4     37  42  44  28  27  30  46   8  35  36  39  12  31  14  18  41  45  19  20  40  13   4   5  22  26  47   6  29  25  21  23  32  11  34   0  38  10  33   7   9  43   2  16  17  15   1  24   3
"ccbcbb"    "bccbbc"    4     38  20  43  29  30  24  47  10  39  12  32  33  34   2  44  19  14  16  15  45  41   5  46   6  28   4  25  23  21  22  26   0  37   8  35   9  31   7  36  11   1  40  13  42  17  18   3  27
"ccbccb"    "ccbccb"    2     39  44  45  30  46  47  21  12  31  37  34  38   7  19  40  42  41  20  43  13  17   6  25  28  27  22  29  24  23  26   3   8  35  36  10  32  33   9  11   0  14  16  15  18   1   2   4   5
"bccbbcb"   "ccbccbcb"  3     40  46  25  31  37  33  35  13  42  44  16  15  18  21  28  30  29  23  24  27   5   7   8  39  12  38   9  32  36  10  11  45  19  20   1  43  14  41   2  17  47   4  22   6  26   3  34   0
"cbccbcb"   "cbbcb"     3     41  22  26  36  32  11  34  42  43  14  17  18  45  28  24   4   3  27   5  47  21  37  33   8   9   0  35  10  38   7  39  19  15   1  40   2  16  20  13  44   6  25  29  23  30  46  12  31
"ccbbcbb"   "bccbc"     3     42  28  27  37   8  35  36  44  14  19  18  40  41  30   4   6   5  46  25  22  26  39   9  12   0  10  31  33  32  11  34  20   1   2  13  16  15  43  17  45  29  23  24   3  47  21  38   7
"ccbcbbc"   "bccbbcbb"  3     43  24  47  32  33  34  38  14  16  15  45  41  20   4  25  23  21  22  26  29  30   8  35   9  31   7  36  11  10  39  12   1  40  13  42  17  18   2  44  19   3  27   5  46   6  28   0  37
"ccbccbb"   "bcbbc"     3     44  30  46  39  12  31  37  45  19  20  40  13  42  47   6  29  25  21  23  28  27  34   0  38  10  33   7   9   8  35  36  43   2  16  17  15   1  14  18  41  24   3   4   5  22  26  32  11
"ccbccbc"   "cbccb"     3     45  47  21  34  38   7  39  41  20  43  13  17  44  22  29  24  23  26   3  30  46  36  10  32  33   9  11   0  12  31  37  14  16  15  18   1   2  19  40  42   4   5   6  25  28  27   8  35
"bccbbcbb"  "ccbcbbc"   3     46  31  37  40  13  42  44  25  21  23  28  27  30  33   7   9   8  35  36  39  12  16  17  15   1  14  18  41  45  19  20  24   3   4   5  22  26  47   6  29  32  11  34   0  38  10  43   2
"ccbccbcb"  "bccbbcb"   3     47  34  38  45  41  20  43  21  22  26  29  30  24   7  36  11  10  39  12  32  33  13  42  17  18   2  44  19  14  16  15   3  27   5  46   6  28   4  25  23   0  37   8  35   9  31   1  40
 

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

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

Это я уже научился делать. Более того, я научился детектировать случаи, когда группа получается бесконечной. И в добавок ко всему, придумал способ, использующий методику научного тыка, для дополнения групповых соотношений для того, чтобы группа стала конечной. Но это всё проходняк: мне просто нужен был способ строить объекты для наглядного исследования. Осознавать всю эту абстрактную теорию без наглядных пособий (пусть даже неразумно громоздких) — это не для моего склада ума.

[Munin]

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

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

А вот это как-то не укладывается в голове :-) Куда же эта группа уходит?..

[mihaild]

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

Куда же эта группа уходит?

В каком смысле "уходит"? Просто если много раз повторять одно и то же то придем откуда начинали, а вот если брать разное - то в начальную точку не вернемся.
С помощью гугла удалось вспомнить название - задача Бёрнсайда. Википедия утверждает, что есть бесконечная конечно порожденная группа, в которой порядки всех элементов делят $665$, и что неизвестно, является ли бесконечной группа $B(2, 5)$ (группа, порожденная двумя элементами, с соотношениями $x^5 = e$ для всех возможных $x$).

[Munin]

Спасибо!

[B@R5uk]

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

[Munin]

Какие-то соотношения всё-таки надо знать.

[B@R5uk]

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

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

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



Она во многом похожа на группу тетраэдра $A_4$: не сложная, весьма красива и в то же время не представима в виде косого произведения. К сожалению, эта группа слишком "не сложная", поэтому в ней нет нетривиальных подгрупп, отличных от циклических (которые тут имеют порядки 2, 3 и 6). А ещё тут замечательный элемент $b^3$: он коммутирует со всеми остальными элементами группы.

[Munin]

"Простая группа" - это термин. Не произносите этих слов в описательном смысле, вас не поймут.

[B@R5uk]

Munin, спасибо, поправил. Термин слышал мимолётом, но поскольку я его не понимаю в полной степени, то даже и не вспомнил его, когда писал.

-- 25.02.2020, 11:06 --

А есть какой-нибудь быстрый и/или красивый способ найти все подгруппы в группе?

[Munin]

Мне показалось, вам будет интересна и поучительна популярная статья

О сложности вычислений в группах. Ольшанский А.Ю. // СОЖ, 2000, No 3, с. 118–123.

(pdf гуглится по названию).

[B@R5uk]

Munin, спасибо! Интересная статья. Журнал, правда, пришлось выкачивать с торрентов, потому что Гугль ничего качабельного не выдаёт. Понравилось то, как теорию групп используют в топологии: задача о стягиваемости кривой в точку на некой поверхности при правильном преформулировании эквивалентна проблеме слов в теории групп. Проблема слов — это решение вопроса, равно ли заданное слово единице группы или нет.

В конце-концов прояснилось, что же именно не является алгоритмически разрешимой задачей. Теорема Новикова-Буна (про которую в Гугле ни слуху ни духу) утверждает, что существует конечно-определённая группа (заданная конечным числом образующих и соотношений между ними), для которой проблема слов алгоритмически не разрешима в принципе. К сожалению, не уточнено, обязана ли такая группа быть бесконечной.

[mihaild]

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

К сожалению, не уточнено, обязана ли такая группа быть бесконечной

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

[Munin]

(Оффтоп)

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

Журнал, правда, пришлось выкачивать с торрентов, потому что Гугль ничего качабельного не выдаёт.

Мне сразу вышла ссылка http://www.pereplet.ru/nauka/Soros/pdf/0003_118.pdf
по запросу

О сложности вычислений в группах. Ольшанский А.Ю.

Большинство статей СОЖ можно достать по одной с двух-трёх сайтов, где они задержались в виде PDF. Но есть и одно-два места, где их можно скачать цельным архивом. Даже без торрентов. Ну и торренты - слава им.

[B@R5uk]

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

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

Не понятно тогда, почему на предыдущих страницах к моему желанию сделать это с помощью программы отнеслись столь критически.

Munin, у меня этот сайт не открывается ни в каком виде.

[mihaild]

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

почему на предыдущих страницах к моему желанию сделать это с помощью программы отнеслись столь критически

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