Однозначная идентификация конечной группы

B@R5uk · 26/05/12 1694 приходит весна?

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

Порядок
Ранг
Абелевость (является и группа абелевой: да/нет)
Список количества элементов каждого порядка (не знаю как это одним словом или словосочетанием назвать)

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

код: [ скачать ] [ спрятать ]

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

----------------------------------------------------------------------------------------

Name            O   R   A   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15

----------------------------------------------------------------------------------------

Z1              1   0   +   1   -   -   -   -   -   -   -   -   -   -   -   -   -   -

Z2              2   1   +   1   1   -   -   -   -   -   -   -   -   -   -   -   -   -

Z3              3   1   +   1   -   2   -   -   -   -   -   -   -   -   -   -   -   -

Z4              4   1   +   1   1   -   2   -   -   -   -   -   -   -   -   -   -   -

K4              4   2   +   1   3   -   0   -   -   -   -   -   -   -   -   -   -   -

Z5              5   1   +   1   -   -   -   4   -   -   -   -   -   -   -   -   -   -

D6              6   2   -   1   3   2   -   -   0   -   -   -   -   -   -   -   -   -

Z6              6   1   +   1   1   2   -   -   2   -   -   -   -   -   -   -   -   -

Z7              7   1   +   1   -   -   -   -   -   6   -   -   -   -   -   -   -   -

Z8              8   1   +   1   1   -   2   -   -   -   4   -   -   -   -   -   -   -

Z4 x Z2         8   2   +   1   3   -   4   -   -   -   0   -   -   -   -   -   -   -

D8              8   2   -   1   5   -   2   -   -   -   0   -   -   -   -   -   -   -

Q8              8   2   -   1   1   -   6   -   -   -   0   -   -   -   -   -   -   -

Z3^3            8   3   +   1   7   -   0   -   -   -   0   -   -   -   -   -   -   -

Z9              9   1   +   1   -   2   -   -   -   -   -   6   -   -   -   -   -   -

Z3^2            9   2   +   1   -   8   -   -   -   -   -   0   -   -   -   -   -   -

D10             10  2   -   1   5   -   -   4   -   -   -   -   0   -   -   -   -   -

Z10             10  1   +   1   1   -   -   4   -   -   -   -   4   -   -   -   -   -

Z11             11  1   +   1   -   -   -   -   -   -   -   -   -   10  -   -   -   -

Q12             12  2   -   1   1   2   6   -   2   -   -   -   -   -   0   -   -   -

Z12             12  1   +   1   1   2   2   -   2   -   -   -   -   -   4   -   -   -

A4              12  2   -   1   3   8   0   -   0   -   -   -   -   -   0   -   -   -

D12             12  2   -   1   7   2   0   -   2   -   -   -   -   -   0   -   -   -

Z6 x Z2         12  2   +   1   3   2   0   -   6   -   -   -   -   -   0   -   -   -

Z13             13  1   +   1   -   -   -   -   -   -   -   -   -   -   -   12  -   -

D14             14  2   -   1   7   -   -   -   -   6   -   -   -   -   -   -   0   -

Z14             14  1   +   1   1   -   -   -   -   6   -   -   -   -   -   -   6   -

Z15             15  1   +   1   -   2   -   4   -   -   -   -   -   -   -   -   -   8

----------------------------------------------------------------------------------------

Name            O   R   A   1   2   4   8   16

Z16             16  1   +   1   1   2   4   8

Z4^2            16  2   +   1   3   12  -   -

K4 # Z4         16  2   -   1   7   8   -   -

Z4 # Z4         16  2   -   1   3   12  -   -

Z8 x Z2         16  2   +   1   3   4   8   -

Z8 #5 Z2        16  2   -   1   3   4   8   -

D16             16  2   -   1   9   2   4   -

Z8 #3 Z2        16  2   -   1   5   6   4   -

Q16             16  2   -   1   1   10  4   -

Z4 x K4         16  3   +   1   7   8   -   -

D8 x Z2         16  3   -   1   11  4   -   -

Q8 x Z2         16  3   -   1   3   12  -   -

Pauli           16  3   -   1   7   8   -   -

Z2^4            16  4   +   1   15  -   -   -

------------------------------------------------

Name            O   R   A   1   17

Z17             17  1   +   1   16

----------------------------------------------------

Name            O   R   A   1   2   3   6   9   18

D18             18  2   -   1   9   2   -   6   -

Z18             18  1   +   1   1   2   2   6   6

D6 x Z3         18  2   -   1   3   8   6   -   -

Z3 # D6         18  3   -   1   9   8   -   -   -

Z6 x Z3         18  2   +   1   1   8   8   -   -

----------------------------------------------------

Name            O   R   A   1   19

Z19             19  1   +   1   18

----------------------------------------------------

Name            O   R   A   1   2   3   4   9   20

Q20             20  2   -   1   1   10  4   4   -

Z20             20  1   +   1   1   2   4   4   8

Z5 # Z4         20  2   -   1   5   10  4   -   -

D20             20  2   -   1   11  -   4   4   -

Z10 x Z2        20  2   +   1   3   -   4   12  -

----------------------------------------------------

Name            O   R   A   1   3   7   21

Z7 # Z3         21  2   -   1   14  6   -

Z21             21  1   +   1   2   6   12

----------------------------------------------------

Name            O   R   A   1   2   11  22

D22             22  2   -   1   11  10  -

Z22             22  1   +   1   1   10  10

----------------------------------------------------

Name            O   R   A   1   23

Z23             23  1   +   1   22

------------------------------------------------------------

Name            O   R   A   1   2   3   4   6   8   12  24

Z3 # Z8         24  2   -   1   1   2   2   2   12  4   -

Z24             24  1   +   1   1   2   2   2   4   4   8

2T              24  2   -   1   1   8   6   8   -   -   -

Q24             24  2   -   1   1   2   14  2   -   4   -

D6 x Z4         24  2   -   1   7   2   8   2   -   4   -

D24             24  2   -   1   13  2   2   2   -   4   -

Q12 x Z2        24  2   -   1   3   2   12  6   -   -   -

8G24            24  2   -   1   9   2   6   6   -   -   -

Z12 x Z2        24  2   +   1   3   2   4   6   -   8   -

D8 x Z3         24  2   -   1   5   2   2   10  -   4   -

Q8 x Z3         24  2   -   1   1   2   6   2   -   12  -

S4              24  2   -   1   9   8   6   -   -   -   -

A4 x Z2         24  2   -   1   7   8   -   8   -   -   -

D12 x Z2        24  3   -   1   15  2   -   6   -   -   -

Z6 x K4         24  3   +   1   7   2   -   14  -   -   -

------------------------------------------------------------

Name            O   R   A   1   5   25

Z25             25  1   +   1   4   20

Z5^2            25  2   +   1   24  -

--------------------------------------------

Name            O   R   A   1   2   13  26

D26             26  2   -   1   13  12  -

Z26             26  1   +   1   1   12  12

--------------------------------------------

Name            O   R   A   1   3   9   27

Z27             27  1   +   1   2   6   18

Z9 x Z3         27  2   +   1   8   18  -

Z3^2 # Z3       27  2   -   1   26  -   -

Z9 # Z3         27  2   -   1   8   18  -

Z3^3            27  3   +   1   26  -   -

------------------------------------------------------------

Name            O   R   A   1   2   3   6   13  28

Q28             28  2   -   1   1   14  6   6   -

Z28             28  1   +   1   1   2   6   6   12

D28             28  2   -   1   15  -   6   6   -

Z14 x Z2        28  2   +   1   3   -   6   18  -

------------------------------------------------------------

Name            O   R   A   1   29

Z29             29  1   +   1   28

------------------------------------------------------------

Name            O   R   A   1   2   3   5   6   10  15  30

D6 x Z5         30  2   -   1   3   2   4   12  -   8   -

D10 x Z3        30  2   -   1   5   2   4   10  -   8   -

D30             30  2   -   1   15  2   4   -   -   8   -

Z30             30  1   +   1   1   2   4   2   4   8   8

------------------------------------------------------------

Name            O   R   A   1   31

Z31             31  1   +   1   30

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Name            O   R   A   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

----------------------------------------------------------------

Name            O   R   A   1   2   3   4   6   9   12  18  36

Q36             36  2   -   1   1   2   18  2   6   -   6   -

Z36             36  1   +   1   1   2   2   2   6   4   -   12

K4 # Z9         36  2   -   1   3   2   0   6   24  -   -   -

D36             36  2   -   1   19  2   0   2   6   -   6   -

Z18 x Z2        36  2   +   1   3   2   0   6   6   -   18  -

Q12 x Z3        36  2   -   1   1   8   6   8   -   12  -   -

Z3 # Q12        36  3   -   1   1   8   18  8   -   -   -   -

Z12 x Z3        36  2   +   1   1   8   2   8   -   16  -   -

Z3^2 # Z4       36  2   -   1   9   8   18  0   -   -   -   -

D6^2            36  2   -   1   15  8   0   12  -   -   -   -

A4 x Z3         36  2   -   1   3   26  0   6   -   -   -   -

D6 x Z6         36  2   -   1   7   8   0   20  -   -   -   -

Z6 # D6         36  3   -   1   19  8   0   8   -   -   -   -

Z6^2            36  2   +   1   3   8   0   24  -   -   -   -

----------------------------------------------------------------

Name            O   R   A   1   2   4   5   8   10  20  40

Z5 #4 Z8        40  2   -   1   1   2   4   20  4   8   -

Z40             40  1   +   1   1   2   4   4   4   8   16

Z5 #2 Z8        40  2   -   1   1   10  4   20  4   -   -

Q40             40  2   -   1   1   22  4   -   4   8   -

D10 x Z4        40  2   -   1   11  12  4   -   4   8   -

D40             40  2   -   1   21  2   4   -   4   8   -

Q20 x Z2        40  2   -   1   3   20  4   -   12  -   -

K4 # D10        40  2   -   1   13  10  4   -   12  -   -

Z20 x Z2        40  2   +   1   3   4   4   -   10  16  -

D8 x Z5         40  2   -   1   5   2   4   -   20  8   -

Q8 x Z5         40  2   -   1   1   6   4   -   4   24  -

D10 # Z4        40  2   -   1   11  20  4   -   4   -   -

D20 x Z2        40  3   -   1   23  -   4   -   12  -   -

Z10 x K4        40  3   +   1   7   -   4   -   28  -   -

------------------------------------------------------------

Name            O   R   A   1   41

Z41             41  1   +   1   40

------------------------------------------------------------

Name            O   R   A   1   2   3   6   7   14  21  42

Z7 #3 Z6        42  2   -   1   7   14  14  6   -   -   -

Z7 #4 Z6        42  2   -   1   1   14  14  6   6   -   -

D6 x Z7         42  2   -   1   3   2   -   6   18  12  -

D14 x Z3        42  2   -   1   7   2   14  6   -   12  -

D42             42  2   -   1   21  2   -   6   -   12  -

Z42             42  1   +   1   1   2   2   6   6   12  12

------------------------------------------------------------

Name            O   R   A   1   2   5   10  25  50

D50             50  2   -   1   25  4   -   20  -

Z50             50  1   +   1   1   4   4   20  20

D10 x Z5        50  2   -   1   5   24  20  -   -

Z5^2 # Z2       50  3   -   1   25  24  -   -   -

Z10 x Z5        50  2   +   1   1   24  24  -   -

----------------------------------------------------

Name            O   R   A   1   2   4   13  26  52

Q52             52  2   -   1   1   26  12  12  -

Z52             52  1   +   1   1   2   12  12  24

Z13 # Z4        52  2   -   1   13  26  12  -   -

D52             52  2   -   1   27  -   12  12  -

Z26 x Z2        52  2   +   1   3   -   12  36  -

------------------------------------------------------------

Name            O   R   A   1   2   3   6   9   18  27  54

D54             54  2   -   1   27  2   -   6   -   18  -

Z54             54  1   +   1   1   2   2   6   6   18  18

D18 x Z3        54  2   -   1   9   8   18  18  -   -   -

D6 x Z18        54  2   -   1   3   8   6   18  18  -   -

5G54            54  2   -   1   9   26  18  -   -   -   -

Z9 #2 Z6        54  2   -   1   9   8   18  18  -   -   -

7G54            54  3   -   1   27  8   -   18  -   -   -

8G54            54  3   -   1   9   26  18  -   -   -   -

Z9 x Z6         54  2   +   1   1   8   8   18  18  -   -

10G54           54  2   -   1   1   26  26  -   -   -   -

Z18 # Z3        54  2   -   1   1   8   8   18  18  -   -

D6 x Z3^2       54  2   -   1   3   26  24  -   -   -   -

13G54           54  3   -   1   9   26  18  -   -   -   -

14G54           54  4   -   1   27  26  -   -   -   -   -

Z6 x Z3^2       54  3   -   1   1   26  26  -   -   -   -

------------------------------------------------------------

Name            O   R   A   1   3   7   9   21  63

Z7 # Z9         63  2   -   1   2   6   42  12  -

Z63             63  1   +   1   2   6   6   12  36

Z7 # Z3^2       63  2   -   1   44  6   -   12  -

Z21 x Z3        63  2   +   1   8   6   -   21  -

----------------------------------------------------

Name            O   R   A   1   3   5   15  25  75

Z75             75  1   +   1   2   4   8   20  40

Z5^2 # Z3       75  2   -   1   50  24  -   -   -

Z15 x Z5        75  2   +   1   2   24  48  -   -

----------------------------------------------------

Удобство этого метода в том, что порядок элементов, и, как следствие, количество элементов каждого порядка очень легко считается. Для этого даже не надо структуру группы знать. Однако, проблемы с этим подходом маячили на горизонте уже для групп порядка 16. Группа $\mathbb{Z}_8\times\mathbb{Z}_2$ и группа $\mathbb{Z}_8\overset{5}{\rtimes}\mathbb{Z}_2=\left\langle\;a,\;b\;|\;a^8=b^2=I,\;ab=ba^5\;\right\rangle$ имеют одинаковый "вектор порядков элементов": 1-3-4-8-0 (для порядков 1-2-4-8-16). Так же они имеют одинаковый ранк, и единственным их глобальным отличием является то, что одна из них абелева, а другая — нет. Аналогичная ситуация с группами 27-го порядка $\mathbb{Z}_9\times\mathbb{Z}_3$ и $\mathbb{Z}_9\rtimes\mathbb{Z}_3$ , они имеют одинаковый вектор 1-8-18-0 (для порядков 1-3-9-27), одинаковый ранк и отличаются только абелевостью.

Наконец, для групп 54-го порядка (возможно, что это же случается и для групп порядка 32 или 48, но я их не "осваивал") я наткнулся таки на полные "группы-двойники": ${}^8\mathrm{G}_{54}=\mathbb{Z}_3^2\rtimes\mathrm{D}_6=\left(\mathbb{Z}_3^2\rtimes\mathbb{Z}_3\right)\rtimes\mathbb{Z}_2=\left\langle\;a,\;b\;|\;a^3=b^3=(ab)^3=(a^2b)^3=d^2=(ad)^2=(bd)^2=I\;\right\rangle$ ${}^{13}\mathrm{G}_{54}=\mathbb{Z}_3^2\rtimes\mathrm{D}_6=\mathbb{Z}_3^2\rtimes\mathbb{Z}_6=\mathbb{Z}_3^3\rtimes\mathbb{Z}_2=\left(\mathbb{Z}_3\rtimes\mathrm{D}_6\right)\times\mathbb{Z}_3=$ $=\left\langle\;a,\;b\;|\;a^3=b^3=c^3=d^2=[a,\;b]=[a,\;c]=[b,\;c]=[c,\;d]=(ad)^2=(bd)^2=I\;\right\rangle$ Обе они имеют ранк 3, их "вектор порядков" 1-9-26-18-0-0-0-0 (для порядков 1-2-3-6-9-18-27-54), и обе они не абелевы. Единственное отличие сразу бросающееся в глаза (и легко считающееся, что не мало важно), — вторая имеет нетривиальный центр.

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

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

dgwuqtj · 07/08/23 1099

А как быстро вы умеете считать ранг? Говорят, изоморфность проверяется за время $O(n^{\log_2 n + C})$ .

B@R5uk · 26/05/12 1694 приходит весна?

Он задан размером таблицы умножения. (Откуда она берётся — это отдельный вопрос, не имеющий отношения к теме). Изоморфность я делал. У меня она считается за $O(r\cdot n^{r+1})$ где r — ранк, а n — порядок группы. На входе нужно две таблицы умножения и список образующих группы. Но мне нужна идентификация группы, а не брутфорс изоморфности со списком. Не самая быстрая операция, особенно для групп большого ранга и порядка.

dgwuqtj · 07/08/23 1099

Порядок группы - это её мощность, $n$ . А ранг - это наименьшая мощность порождающего множества. Мне в голову приходит только перебор всех подмножеств порядка $O(\log n)$ .

B@R5uk · 26/05/12 1694 приходит весна?

dgwuqtj, не совсем понимаю, с чем именно вы мне пытаетесь помочь.

dgwuqtj · 07/08/23 1099

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

B@R5uk · 26/05/12 1694 приходит весна?

То есть, существует некоторая минимальная величина порядка, для которой существуют две группы, у которых совпадают все величины из списка:

Ранк группы
Порядок группы
Порядок центра
Количество элементов каждого порядка

Верно?

Интересно, какова эта величина? Если порядок центра заменить абелевостью, то я нашёл, что она либо 32, либо 48, но точно не больше 54.

dgwuqtj · 07/08/23 1099

Без понятия, но не доказано, что такой величины нет. Можете поискать среди групп порядка 64 или 128, вдруг повезёт.

-- 11.08.2024, 14:15 --

Хотя вот тут предлагают смотретт на $p$ -группы класса 2 и экспоненты $p$ при $p > 2$ . Там все нетривиальные элементы порядка $p$ , что сразу делает самый большой инвариант бессмысленным. Это группы порядка 81, 243, и так далее.

B@R5uk · 26/05/12 1694 приходит весна?

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

Но я такой не знаю.

-- 11.08.2024, 14:19 --

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

Там все нетривиальные элементы порядка $p$ , что сразу делает самый большой инвариант бессмысленным.

О!..

Да, заставляет задуматься.

То есть я всё-такие откладываю проблему как минимум до порядка 81.

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

... $p$ -группы класса 2...

Что значит "класс" у p-групп? Который раз уже натыкаюсь.

dgwuqtj · 07/08/23 1099

На 81 не смотрите, там групп экспоненты 3 и класса 2 вроде мало. Класс у нильпотентной группы - это длина нижнего центрального ряда, класс 1 у абелевых групп, класс 2 у групп с $[G, G] \leq \mathrm C(G)$ , и так далее.

B@R5uk · 26/05/12 1694 приходит весна?

dgwuqtj, я тут вспомнил вопрос, давно мучаюший меня: а разве решётка подгрупп не является однозначным идентификатором группы? Другими словами, существуют ли две не изоморфные конечные группы с одинаковыми решётками?

dgwuqtj · 07/08/23 1099

Существуют, $\mathrm C_2$ и $\mathrm C_3$ .

B@R5uk · 26/05/12 1694 приходит весна?

В смысле циклические группы 2-го и 3-го порядка? Ну, у них разные решётки на мой взгляд, отличаются порядком групп в одной из вершин графа.

dgwuqtj · 07/08/23 1099

Решётки подгрупп изоморфны, это решётки из двух элементов всё-таки. Если что, решётка — это частично упорядоченное множество с дополнительными свойствами, там никакой другой информации не содержится. Или вы хотите рассматривать решётки с дополнительной структурой типа порядков элементов? Тогда понятия не имею, может, группа и восстановится однозначно.

B@R5uk · 26/05/12 1694 приходит весна?

С дополнительной, разумеется. Как минимум ранк и порядки должны включаться в структуру данных. Нормальные, центральные, характеристические, абелевы подгруппы тоже должны как-то выделяться. Орбиты подгрупп относительно группы автоморфизмов тоже, но это уже высший пилотаж, хотя порой бывают изоморфные подгруппы, которые не принадлежат центру, но не входят в один класс эквивалентности (не принадлежат одной орбите) Как правило это нормальные подгруппы и фактор-группы по ним отличаются (не изомфорфны). В любом случае, решётка у простых циклических групп — это вырожденное явление и может оказаться исключением из правила. Хотя нет, у $\mathbb{Z}_{pq}$ получается решётка с векторами:

$\mathbb{Z}_{1}\to\mathbb{Z}_{p}$
$\mathbb{Z}_{1}\to\mathbb{Z}_{q}$
$\mathbb{Z}_{p}\to\mathbb{Z}_{pq}$
$\mathbb{Z}_{q}\to\mathbb{Z}_{pq}$

Мда, без допинформации не интересно.

Научный форум dxdy

Правила форума

Однозначная идентификация конечной группы

Кто сейчас на конференции