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

[arseniiv]

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

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

Так можно, хотя это может быть не самый эффективный способ рано отвергнуть. (UPD: Конечно лишь если таблицу предлагается физически переставлять, на что каждый раз будет тратиться время.) Например можно сразу не рассматривать перестановки, переводящие нейтральный элемент в не-нейтральный, но это как раз скучно. Может быть есть смысл, если элементов много, выбрать два и проверить для них $f(ab) = f(a)f(b)$, и может ещё несколько раз так сделать?

-- Вт май 19, 2020 00:13:24 --

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

-- Вт май 19, 2020 00:15:37 --

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

[B@R5uk]

Ну, неизменность нейтрального элемента при автоморфизме — это тривия. Тут более серьёзные ограничения есть. Например, при автоморфизме образ и прообраз обязаны иметь один и тот же порядок, принадлежать к классам эквивалентности одного размера, входить в одинаковые типы подгрупп. Это накладывает весьма серьёзные ограничения и значительно суживает число возможных вариантов.

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

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

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

[B@R5uk]

Моя самая последняя программа, с помощью которой я изучаю свойства групп и подгрупп. Состоит из пяти файлов. В Study_Groups_2.java находится функция main, в которой происходит вызов вычислительных и отображающих функций. Ключевые вычислительные функции находятся в GroupClass.java, который не влез в сообщение, и я его по-позже отправлю. В GroupsCollection.java находятся затравки таблиц умножения групп, по которым восстанавливаются полные таблицы, по которым, в свою очередь, изучается группа. Файлы SubgroupClass.java и SubgroupsRecordClass.java — это вспомогательные классы с искомой информацией о группе и подгруппах с функциями вывода. Последний файл тоже не влез в пост и будет отправлен позже.

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

public class Study_Groups_2 {
        
        public static void main(String[] args) {
                GroupClass group;
                SubgroupsRecordClass sgRecord;
                group = new GroupClass(GroupsCollection.getTableSeed(3));
                if (21 >= group.getOrder()) {
                        group.displayMultiplicationTable();
                        group.displayConjugacyTable();
                }
                group.displayElementsProperties();
                group.displayConjugacyClasses();
                sgRecord = group.educeSubgroups();
                //sgRecord.displayCycles();
                sgRecord.displaySubgroups();
                //sgRecord.displayInclusionTable();
                sgRecord.subgroupsList[sgRecord.subgroupsList.length - 1].displayGenerators();
        }
}
 

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

public class GroupsCollection {
        
        private static int[][][] tableSeeds = new int[100][][];
        
        static {
                //              Z_2 x Z_2 x Z_2
                //              Order 8
                tableSeeds[0] = new int[][] {
                        {1, 0, 4, 5, 2, 3, 7, 6},
                        {2, 4, 0, 6, 1, 7, 3, 5},
                        {3, 5, 6, 0, 7, 1, 2, 4}
                };
                //              Tetrahredal group A_4
                //              Order 12
                tableSeeds[1] = new int[][] {
                        {1, 0, 3, 2, 6, 7, 4, 5, 9, 8, 11, 10},
                        {2, 4, 5, 8, 9, 0, 7, 10, 11, 1, 6, 3}
                };
                //              Z_7 # Z_3
                //              Order 21
                tableSeeds[2] = new int[][] {
                        {1, 3, 4, 0, 7, 8, 9, 2, 18, 10, 6, 13, 14, 20, 15, 12, 19, 16, 5, 17, 11},
                        {2, 5, 6, 10, 11, 4, 12, 15, 16, 17, 8, 9, 18, 3, 1, 13, 7, 14, 20, 0, 19}
                };
                //              Dihedral group Dih_3
                //              Order 6
                tableSeeds[3] = new int[][] {
                        {1, 0, 3, 2, 5, 4},
                        {2, 4, 5, 1, 3, 0}
                };
                //              Dihedral group Dih_4
                //              Order 8
                tableSeeds[4] = new int[][] {
                        {1, 0, 3, 2, 6, 7, 4, 5},
                        {2, 4, 5, 1, 7, 6, 0, 3}
                };
                //              Dihedral group Dih_5
                //              Order 10
                tableSeeds[5] = new int[][] {
                        {1, 0, 3, 2, 6, 7, 4, 5, 9, 8},
                        {2, 4, 5, 1, 8, 9, 0, 3, 7, 6}
                };
                //              Dihedral group Dih_6
                //              Order 12
                tableSeeds[6] = new int[][] {
                        {1, 0, 3, 2, 6, 7, 4, 5, 11, 10, 9, 8},
                        {2, 4, 5, 1, 8, 9, 0, 3, 10, 11, 7, 6}
                };
                //              Dihedral group Dih_7
                //              Order 14
                tableSeeds[7] = new int[][] {
                        {1, 0, 3, 2, 6, 7, 4, 5, 10, 11, 8, 9, 13, 12},
                        {2, 4, 5, 1, 8, 9, 0, 3, 12, 13, 6, 7, 11, 10}
                };
                //              Dihedral group Dih_8
                //              Order 16
                tableSeeds[8] = new int[][] {
                        {1, 0, 3, 2, 6, 7, 4, 5, 10, 11, 8, 9, 15, 14, 13, 12},
                        {2, 4, 5, 1, 8, 9, 0, 3, 12, 13, 6, 7, 14, 15, 11, 10}
                };
                //              Dihedral group Dih_9
                //              Order 18
                tableSeeds[9] = new int[][] {
                        {1, 0, 3, 2, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13, 17, 16},
                        {2, 4, 5, 1, 8, 9, 0, 3, 12, 13, 6, 7, 16, 17, 10, 11, 15, 14}
                };
                //              Z_3 x Z_3 x Z_3
                //              Order 27
                tableSeeds[10] = new int[][] {
                        {1, 4, 5, 6, 0, 10, 11, 12, 13, 14, 2, 3, 17, 18, 19, 20, 21, 7, 8, 9, 23, 24, 25, 15, 16, 26, 22},
                        {2, 5, 7, 8, 10, 12, 13, 0, 15, 16, 17, 18, 1, 20, 21, 3, 22, 4, 23, 24, 6, 25, 9, 11, 26, 14, 19},
                        {3, 6, 8, 9, 11, 13, 14, 15, 16, 0, 18, 19, 20, 21, 1, 22, 2, 23, 24, 4, 25, 5, 7, 26, 10, 12, 17}
                };
                //              Klein group K_4
                //              Z_2 x Z_2
                //              Order 4
                tableSeeds[12] = new int[][] {
                        {1, 0, 3, 2},
                        {2, 3, 0, 1}
                };
                //              Z_3 x Z_3
                //              Order 9
                tableSeeds[13] = new int[][] {
                        {1, 3, 4, 0, 6, 7, 2, 8, 5},
                        {2, 4, 5, 6, 7, 0, 8, 1, 3}
                };
                //              Z_4 x Z_4
                //              Order 16
                tableSeeds[14] = new int[][] {
                        {1, 3, 4, 6, 7, 8, 0, 10, 11, 12, 2, 13, 14, 5, 15, 9},
                        {2, 4, 5, 7, 8, 9, 10, 11, 12, 0, 13, 14, 1, 15, 3, 6}
                };
                //              Z_5 x Z_5
                //              Order 25
                tableSeeds[15] = new int[][] {
                        {1, 3, 4, 6, 7, 8, 10, 11, 12, 13, 0, 15, 16, 17, 18, 2, 19, 20, 21, 5, 22, 23, 9, 24, 14},
                        {2, 4, 5, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 0, 19, 20, 21, 1, 22, 23, 3, 24, 6, 10}
                };
                //              Z_6 x Z_6
                //              Order 36
                tableSeeds[16] = new int[][] {
                        {1, 3, 4, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 19, 0, 21, 22, 23, 24, 25, 2, 26, 27, 28, 29, 5, 30, 31, 32, 9, 33, 34, 14, 35, 20},
                        {2, 4, 5, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 0, 26, 27, 28, 29, 1, 30, 31, 32, 3, 33, 34, 6, 35, 10, 15}
                };
                //              Z_7 x Z_7
                //              Order 49
                tableSeeds[17] = new int[][] {
                        {1, 3, 4, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 0, 28, 29, 30, 31, 32, 33, 2, 34, 35, 36, 37, 38, 5, 39, 40, 41, 42, 9, 43, 44, 45, 14, 46, 47, 20, 48, 27},
                        {2, 4, 5, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 0, 34, 35, 36, 37, 38, 1, 39, 40, 41, 42, 3, 43, 44, 45, 6, 46, 47, 10, 48, 15, 21}
                };
                //              Z_8 x Z_8
                //              Order 64
                tableSeeds[18] = new int[][] {
                        {1, 3, 4, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 0, 36, 37, 38, 39, 40, 41, 42, 2, 43, 44, 45, 46, 47, 48, 5, 49, 50, 51, 52, 53, 9, 54, 55, 56, 57, 14, 58, 59, 60, 20, 61, 62, 27, 63, 35},
                        {2, 4, 5, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 0, 43, 44, 45, 46, 47, 48, 1, 49, 50, 51, 52, 53, 3, 54, 55, 56, 57, 6, 58, 59, 60, 10, 61, 62, 15, 63, 21, 28}
                };
                //              Z_9 x Z_9
                //              Order 81
                tableSeeds[19] = new int[][] {
                        {1, 3, 4, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, 43, 0, 45, 46, 47, 48, 49, 50, 51, 52, 2, 53, 54, 55, 56, 57, 58, 59, 5, 60, 61, 62, 63, 64, 65, 9, 66, 67, 68, 69, 70, 14, 71, 72, 73, 74, 20, 75, 76, 77, 27, 78, 79, 35, 80, 44},
                        {2, 4, 5, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 0, 53, 54, 55, 56, 57, 58, 59, 1, 60, 61, 62, 63, 64, 65, 3, 66, 67, 68, 69, 70, 6, 71, 72, 73, 74, 10, 75, 76, 77, 15, 78, 79, 21, 80, 28, 36}
                };
                //              Z_8 x Z_2
                //              Order 16
                //              p^8 = q^2 = I;  qp = pq
                tableSeeds[20] = new int[][] {
                        {1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 15, 2},
                        {2, 4, 0, 6, 1, 8, 3, 10, 5, 12, 7, 14, 9, 15, 11, 13}
                };
                //              Z_8 # Z_2
                //              Order 16
                //              p^8 = q^2 = I;  qp = p^3q
                tableSeeds[21] = new int[][] {
                        {1, 3, 4, 9, 6, 7, 5, 10, 11, 13, 8, 2, 14, 15, 0, 12},
                        {2, 5, 0, 8, 9, 1, 12, 13, 3, 4, 14, 15, 6, 7, 10, 11}
                };
                //              Z_8 # Z_2
                //              Order 16
                //              p^8 = q^2 = I;  qp = p^5q
                tableSeeds[22] = new int[][] {
                        {1, 3, 4, 6, 8, 7, 10, 12, 11, 13, 9, 14, 2, 15, 5, 0},
                        {2, 5, 0, 8, 9, 1, 12, 13, 3, 4, 14, 15, 6, 7, 10, 11}
                };
                //              Pauli group
                //              Order 16
                tableSeeds[23] = new int[][] {
                        {1, 0, 4, 5, 2, 3, 14, 12, 10, 11, 8, 9, 7, 15, 6, 13},
                        {2, 6, 0, 7, 13, 11, 1, 3, 12, 10, 9, 5, 8, 4, 15, 14},
                        {3, 8, 9, 0, 12, 13, 11, 14, 1, 2, 15, 6, 4, 5, 7, 10}
                };
                //              Z_4 # Z_4
                //              Order 16
                //              p^4 = q^4 = I;  qp = p^3q
                tableSeeds[24] = new int[][] {
                        {1, 3, 4, 7, 8, 2, 10, 0, 5, 6, 12, 13, 9, 15, 11, 14},
                        {2, 5, 6, 8, 9, 10, 11, 4, 12, 13, 14, 0, 15, 7, 1, 3}
                };
                //              Binary tetrahedral group 2T = SL(2,3)
                //              Order 24
                tableSeeds[30] = new int[][] {
                        {1, 3, 4, 11, 7, 6, 8, 17, 12, 10, 13, 16, 23, 18, 9, 19, 22, 15, 20, 2, 14, 5, 0, 21},
                        {2, 5, 6, 9, 3, 10, 11, 14, 7, 15, 16, 17, 20, 8, 21, 22, 12, 23, 4, 13, 1, 19, 18, 0}
                };
                //              Symmetric group S_4
                //              Order 24
                //              r^4 = s^2 = (sr)^3 = I
                tableSeeds[31] = new int[][] {
                        {1, 3, 4, 6, 7, 8, 0, 15, 11, 12, 13, 20, 16, 17, 18, 2, 22, 23, 21, 14, 5, 19, 9, 10},
                        {2, 5, 0, 9, 10, 1, 13, 14, 15, 3, 4, 19, 20, 6, 7, 8, 21, 22, 23, 11, 12, 16, 17, 18}
                };
                //              Quaternion group Q_8 = Dic_2
                //              Order 8
                tableSeeds[32] = new int[][] {
                        {1, 3, 4, 6, 7, 2, 0, 5},
                        {2, 5, 3, 7, 1, 6, 4, 0}
                };
                //              Dicyclic group Dic_3
                //              Order 12
                tableSeeds[33] = new int[][] {
                        {1, 3, 4, 6, 7, 2, 9, 10, 5, 11, 8, 0},
                        {2, 5, 6, 8, 3, 9, 10, 1, 11, 7, 0, 4}
                };
                //              Dicyclic group Dic_4
                //              Order 16
                tableSeeds[34] = new int[][] {
                        {1, 3, 4, 7, 8, 2, 10, 6, 14, 5, 13, 12, 9, 15, 11, 0},
                        {2, 5, 6, 9, 7, 10, 11, 12, 3, 13, 14, 0, 15, 8, 1, 4}
                };
                //              Dicyclic group Dic_5
                //              Order 20
                tableSeeds[35] = new int[][] {
                        {1, 3, 4, 7, 8, 2, 11, 10, 13, 5, 6, 15, 16, 17, 9, 18, 14, 12, 19, 0},
                        {2, 5, 6, 9, 10, 11, 12, 14, 7, 15, 16, 17, 0, 3, 18, 13, 19, 1, 8, 4}
                };
                //              Dicyclic group Dic_6
                //              Order 24
                tableSeeds[36] = new int[][] {
                        {1, 3, 4, 7, 8, 2, 11, 13, 14, 5, 6, 16, 17, 10, 21, 9, 20, 19, 12, 15, 23, 18, 0, 22},
                        {2, 5, 6, 9, 10, 11, 12, 15, 13, 16, 17, 18, 0, 19, 7, 20, 21, 22, 1, 23, 14, 3, 4, 8}
                };
                //              Dicyclic group Dic_7
                //              Order 28
                tableSeeds[37] = new int[][] {
                        {1, 3, 4, 7, 8, 2, 11, 13, 14, 5, 6, 17, 18, 16, 20, 9, 10, 22, 23, 12, 24, 15, 26, 21, 19, 0, 27, 25},
                        {2, 5, 6, 9, 10, 11, 12, 15, 16, 17, 18, 19, 0, 21, 13, 22, 23, 24, 25, 1, 7, 26, 20, 27, 3, 4, 14, 8}
                };
                //              Dicyclic group Dic_8
                //              Order 32
                tableSeeds[38] = new int[][] {
                        {1, 3, 4, 7, 8, 2, 11, 13, 14, 5, 6, 17, 18, 22, 20, 9, 10, 23, 24, 12, 29, 15, 16, 27, 28, 19, 0, 31, 21, 25, 26, 30},
                        {2, 5, 6, 9, 10, 11, 12, 15, 16, 17, 18, 19, 0, 21, 22, 23, 24, 25, 26, 1, 13, 27, 28, 29, 30, 3, 4, 20, 31, 7, 8, 14}
                };
                //              Dicyclic group Dic_9
                //              Order 36
                tableSeeds[39] = new int[][] {
                        {1, 3, 4, 7, 8, 2, 11, 13, 14, 5, 6, 17, 18, 20, 21, 9, 10, 24, 25, 12, 23, 28, 15, 16, 30, 31, 19, 0, 32, 22, 34, 29, 26, 27, 35, 33},
                        {2, 5, 6, 9, 10, 11, 12, 15, 16, 17, 18, 19, 0, 22, 23, 24, 25, 26, 27, 1, 29, 20, 30, 31, 32, 33, 3, 4, 13, 34, 28, 35, 7, 8, 21, 14}
                };
                //              A_4 x Z_2
                //              Order 24
                //              a^6 = (ad)^2 = I;  a^3 = d^3
                tableSeeds[50] = new int[][] {
                        {1, 3, 4, 7, 8, 9, 10, 14, 15, 16, 5, 17, 0, 18, 12, 21, 22, 23, 11, 2, 13, 19, 6, 20},
                        {2, 5, 6, 11, 12, 13, 7, 15, 18, 0, 19, 4, 20, 14, 22, 9, 8, 1, 10, 23, 21, 3, 17, 16}
                };
                //              (Z_3 x Z_3) # Z_3
                //              Order 27
                //              b^3 = c^3 = (bc)^3 = (b^2c)^3 = I
                tableSeeds[53] = new int[][] {
                        {1, 3, 4, 0, 7, 8, 9, 2, 13, 16, 14, 18, 15, 5, 24, 21, 6, 22, 20, 23, 11, 12, 25, 26, 10, 17, 19},
                        {2, 5, 6, 10, 11, 12, 0, 15, 16, 17, 18, 19, 1, 20, 21, 22, 23, 24, 3, 4, 25, 26, 7, 8, 9, 13, 14}
                };
                //              Order 48
                //              b^3 = c^3 = (bc)^3 = (b^2c)^4 = I
                tableSeeds[54] = new int[][] {
                        {1, 3, 4, 0, 7, 8, 9, 2, 13, 17, 14, 19, 15, 5, 21, 26, 22, 6, 28, 23, 24, 10, 39, 11, 35, 31, 12, 37, 32, 33, 34, 45, 18, 42, 40, 20, 43, 41, 44, 16, 30, 27, 29, 46, 47, 25, 36, 38},
                        {2, 5, 6, 10, 11, 12, 0, 16, 17, 18, 19, 20, 1, 25, 26, 27, 28, 29, 30, 3, 4, 34, 35, 36, 31, 37, 38, 39, 7, 8, 9, 42, 41, 40, 43, 44, 45, 13, 14, 15, 47, 46, 24, 21, 22, 23, 32, 33}
                };
                //              Order 75
                //              b^3 = c^3 = (bc)^3 = (b^2c)^5 = I
                tableSeeds[55] = new int[][] {
                        {1, 3, 4, 0, 7, 8, 9, 2, 13, 17, 14, 19, 15, 5, 21, 26, 22, 6, 28, 23, 24, 10, 31, 11, 37, 32, 12, 40, 33, 34, 35, 16, 43, 18, 48, 50, 44, 20, 52, 54, 45, 46, 47, 25, 56, 27, 61, 63, 29, 64, 30, 65, 57, 58, 59, 60, 36, 38, 72, 39, 69, 41, 70, 42, 71, 67, 68, 51, 74, 55, 73, 49, 53, 62, 66},
                        {2, 5, 6, 10, 11, 12, 0, 16, 17, 18, 19, 20, 1, 25, 26, 27, 28, 29, 30, 3, 4, 36, 37, 38, 39, 40, 41, 42, 7, 8, 9, 47, 48, 49, 50, 51, 52, 53, 54, 55, 13, 14, 15, 59, 61, 62, 63, 64, 60, 65, 66, 56, 21, 22, 23, 24, 35, 67, 69, 70, 32, 68, 71, 72, 31, 33, 34, 73, 44, 74, 43, 45, 46, 57, 58}
                };
                //              Order 108
                //              b^3 = c^3 = (bc)^3 = (b^2c)^6 = I
                tableSeeds[56] = new int[][] {
                        {1, 3, 4, 0, 7, 8, 9, 2, 13, 17, 14, 19, 15, 5, 21, 26, 22, 6, 28, 23, 24, 10, 31, 11, 37, 32, 12, 40, 33, 34, 35, 16, 43, 18, 49, 51, 44, 20, 53, 55, 45, 46, 47, 25, 57, 27, 64, 66, 58, 29, 68, 30, 70, 59, 60, 61, 62, 36, 87, 38, 78, 39, 80, 82, 41, 83, 42, 85, 73, 74, 75, 76, 77, 50, 99, 52, 92, 94, 54, 95, 56, 96, 98, 88, 89, 90, 91, 48, 65, 105, 67, 101, 71, 102, 72, 104, 100, 103, 63, 69, 81, 86, 106, 107, 79, 84, 93, 97},
                        {2, 5, 6, 10, 11, 12, 0, 16, 17, 18, 19, 20, 1, 25, 26, 27, 28, 29, 30, 3, 4, 36, 37, 38, 39, 40, 41, 42, 7, 8, 9, 48, 49, 50, 51, 52, 53, 54, 55, 56, 13, 14, 15, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 21, 22, 23, 24, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 31, 32, 33, 34, 35, 90, 92, 93, 94, 95, 91, 96, 97, 98, 99, 43, 44, 45, 46, 47, 100, 101, 102, 58, 103, 104, 105, 57, 59, 60, 61, 62, 106, 107, 73, 74, 75, 76, 88, 89}
                };
                //              Symmetric group S_5
                //              Order 120
                //              r^5 = s^2 = (sr)^4 = (sr^2sr^3)^2 = I
                tableSeeds[60] = new int[][] {
                        {1, 3, 4, 6, 7, 8, 11, 12, 13, 14, 15, 0, 19, 20, 21, 22, 23, 24, 25, 2, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 26, 5, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 9, 10, 66, 67, 68, 69, 70, 71, 72, 73, 87, 74, 75, 76, 77, 78, 79, 80, 81, 82, 16, 17, 18, 30, 88, 89, 90, 91, 92, 93, 94, 83, 65, 95, 96, 97, 98, 99, 100, 101, 102, 103, 27, 28, 29, 107, 108, 109, 110, 111, 112, 85, 61, 104, 86, 64, 113, 114, 60, 117, 115, 41, 43, 44, 45, 118, 119, 84, 42, 116, 105, 106, 62, 63},
                        {2, 5, 0, 9, 10, 1, 16, 17, 18, 3, 4, 26, 27, 28, 29, 30, 6, 7, 8, 25, 41, 42, 43, 44, 45, 19, 11, 12, 13, 14, 15, 40, 49, 60, 52, 61, 62, 63, 64, 65, 31, 20, 21, 22, 23, 24, 58, 59, 71, 32, 83, 73, 34, 84, 76, 85, 86, 87, 46, 47, 33, 35, 36, 37, 38, 39, 80, 81, 82, 103, 92, 48, 104, 51, 105, 98, 54, 93, 106, 88, 66, 67, 68, 50, 53, 55, 56, 57, 79, 101, 102, 111, 70, 77, 107, 116, 113, 114, 75, 112, 117, 89, 90, 69, 72, 74, 78, 94, 109, 108, 115, 91, 99, 96, 97, 110, 95, 100, 119, 118}
                };
        }
        
        public static int[][] getTableSeed(int arg) {
                return tableSeeds[arg];
        }
}
 

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

public class SubgroupClass implements Comparable<SubgroupClass> {
        
        public int[] elements;
        public int rank, index;
        public String id;
        public int[][] generators, generatorsTypes, generatorsByType;
        public SubgroupClass[] conjugates, parents;
        
        public SubgroupClass(int[] arg1) {
                elements = arg1;
        }
        
        public int getOrder() {
                return elements.length;
        }
        
        public boolean include(SubgroupClass arg) {
                int k, l, element, anotherElement;
                k = 1;
                l = 1;
                while (elements.length > k && arg.elements.length > l) {
                        element = elements[k];
                        anotherElement = arg.elements[l];
                        if (element > anotherElement) {
                                return false;
                        }
                        if (element == anotherElement) {
                                ++l;
                        }
                        ++k;
                }
                if (arg.elements.length == l) {
                        return true;
                }
                return false;
        }
        
        public int compareTo(SubgroupClass arg) {
                int k;
                if (elements.length > arg.elements.length) {
                        return 1;
                }
                if (elements.length < arg.elements.length) {
                        return -1;
                }
                for (k = 0; elements.length > k; ++k) {
                        if (elements[k] > arg.elements[k]) {
                                return 1;
                        }
                        if (elements[k] < arg.elements[k]) {
                                return -1;
                        }
                }
                return 0;
        }
        
        public void display() {
                int k, l, m;
                if (null == id) {
                        System.out.print("id: none");
                } else {
                        System.out.print("id: \"" + id + "\"");
                }
                System.out.print("; order: ");
                System.out.print(elements.length);
                System.out.print("; rank: ");
                System.out.print(rank);
                System.out.print("; index: ");
                System.out.println(index);
                System.out.print("        elements: ");
                System.out.print(elements[0]);
                for (k = 1; elements.length > k; ++k) {
                        System.out.print(", ");
                        System.out.print(elements[k]);
                }
                System.out.println();
                System.out.print("        generators");
                if (null != generators) {
                        System.out.print(" (");
                        System.out.print(generators.length);
                        System.out.print("): ");
                        if (1 == rank) {
                                System.out.print(generators[0][0]);
                                for (k = 1; generators.length > k; ++k) {
                                        System.out.print(", ");
                                        System.out.print(generators[k][0]);
                                }
                        } else {
                                System.out.print("{");
                                System.out.print(generators[0][0]);
                                for (l = 1; rank > l; ++l) {
                                        System.out.print("; ");
                                        System.out.print(generators[0][l]);
                                }
                                m = 1;
                                for (k = 1; generators.length > k; ++k) {
                                        System.out.print("},  {");
                                        System.out.print(generators[k][0]);
                                        for (l = 1; rank > l; ++l) {
                                                System.out.print("; ");
                                                System.out.print(generators[k][l]);
                                        }
                                        ++m;
                                        if (42 == m && 50 < generators.length) {
                                                break;
                                        }
                                }
                                System.out.print("}");
                                if (42 == m && 50 < generators.length) {
                                        System.out.print(", ... (");
                                        System.out.print(generators.length - m);
                                        System.out.print(" more)");
                                }
                        }
                        System.out.println();
                } else {
                        System.out.println(": none");
                }
                System.out.print("        conjugates (");
                System.out.print(conjugates.length);
                System.out.print("): \"");
                System.out.print(conjugates[0].id);
                if (this == conjugates[0]) {
                        for (k = 1; conjugates.length > k; ++k) {
                                System.out.print("\", \"");
                                System.out.print(conjugates[k].id);
                        }
                }
                System.out.println("\"");
                System.out.print("        parents: ");
                if (0 == parents.length) {
                        System.out.println("none");
                } else {
                        System.out.print("\"");
                        System.out.print(parents[0].id);
                        for (k = 1; parents.length > k; ++k) {
                                System.out.print("\", \"");
                                System.out.print(parents[k].id);
                        }
                        System.out.println("\"");
                }
                System.out.println();
        }
        
        public void displayGenerators() {
                int k, l, m;
                if (1 < rank) {
                        System.out.println();
                        System.out.print("Subgroup \"");
                        System.out.print(id);
                        System.out.println("\" generators by type:");
                        for (k = 0; generatorsTypes.length > k; ++k) {
                                System.out.print("    Type ");
                                System.out.print(generatorsTypes[k][0]);
                                for (l = 1; rank > l; ++l) {
                                        System.out.print("-");
                                        System.out.print(generatorsTypes[k][l]);
                                }
                                System.out.print(" (");
                                System.out.print(generatorsByType[k].length);
                                System.out.print("):");
                                for (l = 0; generatorsByType[k].length > l; ++l) {
                                        if (0 == l % 8) {
                                                if (0 == l) {
                                                        System.out.print("\n        {");
                                                } else {
                                                        System.out.print("},\n        {");
                                                }
                                        } else {
                                                System.out.print("}, {");
                                        }
                                        System.out.print(generators[generatorsByType[k][l]][0]);
                                        for (m = 1; rank > m; ++m) {
                                                System.out.print("; ");
                                                System.out.print(generators[generatorsByType[k][l]][m]);
                                        }
                                }
                                System.out.println("}");
                        }
                        System.out.println();
                }
        }
}
 

[B@R5uk]

Остальные части программы. Было б здорово, если бы кто-нибудь постестил, а то вдруг я забыл или потёр лишнее, чтобы влезло в пост. Что-то вроде ничего особого программа не делает, а графоманства вышло на пол сотни килобайт.

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

import java.util.*;

public class GroupClass {
        
        private int groupOrder;
        private int[][] multiplicationTable, conjugacyTable, conjugacyClasses;
        private int[] inverseElements, elementsOrders, conjugacyNumber, conjugacyClassIndex;
        
        public GroupClass(int[][] arg) {
                restoreMultiplicationTable(arg);
                computeConjugacyTable();
        }
        
        public int getOrder() {
                return groupOrder;
        }
        
        private void restoreMultiplicationTable(int[][] tableSeed) {
                int k, l, m, generatorNumber;
                int[][] references;
                boolean[] rowFlags, clmFlags;
                generatorNumber = tableSeed.length;
                groupOrder = tableSeed[0].length;
                multiplicationTable = new int[groupOrder][];
                multiplicationTable[0] = new int[groupOrder];
                for (k = 0; groupOrder > k; ++k) {
                        multiplicationTable[0][k] = k;
                }
                for (k = 0; generatorNumber > k; ++k) {
                        multiplicationTable[k + 1] = tableSeed[k];
                }
                references = new int[groupOrder][3];
                for (k = 0; groupOrder > k; ++k) {
                        for (l = 1; generatorNumber >= l; ++l) {
                                m = multiplicationTable[l][k];
                                if (0 == references[m][2]) {
                                        references[m][0] = l;
                                        references[m][1] = k;
                                        references[m][2] = 1;
                                }
                        }
                }
                for (k = 0; groupOrder > k; ++k) {
                        if (1 != references[k][2]) {
                                throw new IllegalArgumentException("\n\nTable seed is not complete.\n\n");
                        }
                }
                for (k = generatorNumber + 1; groupOrder > k; ++k) {
                        multiplicationTable[k] = new int[groupOrder];
                        for (l = 0; groupOrder > l; ++l) {
                                m = multiplicationTable[references[k][1]][l];
                                m = multiplicationTable[references[k][0]][m];
                                multiplicationTable[k][l] = m;
                        }
                }
                for (k = 0; groupOrder > k; ++k) {
                        rowFlags = new boolean[groupOrder];
                        clmFlags = new boolean[groupOrder];
                        for (l = 0; groupOrder > l; ++l) {
                                if (rowFlags[multiplicationTable[k][l]] || clmFlags[multiplicationTable[l][k]]) {
                                        throw new IllegalArgumentException("\n\nTable seed is not self-consistent.\n\n");
                                }
                                rowFlags[multiplicationTable[k][l]] = true;
                                clmFlags[multiplicationTable[l][k]] = true;
                        }
                }
                inverseElements = new int[groupOrder];
                for (k = 0; groupOrder > k; ++k) {
                        for (l = 0; groupOrder > l; ++l) {
                                if (0 == multiplicationTable[k][l]) {
                                        inverseElements[k] = l;
                                        break;
                                }
                        }
                }
                elementsOrders = new int[groupOrder];
                for (k = 0; groupOrder > k; ++k) {
                        l = 0;
                        m = 0;
                        while (true) {
                                l = multiplicationTable[k][l];
                                ++m;
                                if (0 == l) {
                                        break;
                                }
                        }
                        elementsOrders[k] = m;
                }
        }
        
        private void computeConjugacyTable() {
                int k, l, m, n;
                boolean flag;
                int[] conjugatesList;
                boolean[] conjugacyFlags;
                List<int[]> classesList = new ArrayList<>();
                Iterator<int[]> iterator;
                conjugacyTable = new int[groupOrder][groupOrder];
                conjugacyClassIndex = new int[groupOrder];
                conjugacyNumber = new int[groupOrder];
                for (k = 0; groupOrder > k; ++k) {
                        conjugacyFlags = new boolean[groupOrder];
                        n = 0;
                        for (l = 0; groupOrder > l; ++l) {
                                m = inverseElements[l];
                                m = multiplicationTable[k][m];
                                m = multiplicationTable[l][m];
                                conjugacyTable[k][l] = m;
                                if (!conjugacyFlags[m]) {
                                        conjugacyFlags[m] = true;
                                        ++n;
                                }
                        }
                        conjugacyNumber[k] = n;
                        conjugatesList = new int[n];
                        m = 0;
                        for (l = 0; groupOrder > l; ++l) {
                                if (conjugacyFlags[l]) {
                                        conjugatesList[m] = l;
                                        ++m;
                                }
                        }
                        flag = true;
                        iterator = classesList.iterator();
                        m = 0;
                        while (iterator.hasNext()) {
                                if (Arrays.equals(iterator.next(), conjugatesList)) {
                                        conjugacyClassIndex[k] = m;
                                        flag = false;
                                        break;
                                }
                                ++m;
                        }
                        if (flag) {
                                conjugacyClassIndex[k] = classesList.size();
                                classesList.add(conjugatesList);
                        }
                }
                conjugacyClasses = classesList.toArray(new int[classesList.size()][]);
        }
        
        public void displayMultiplicationTable() {
                int k, l;
                System.out.println();
                System.out.println("Multiplication Table:");
                for (k = 0; groupOrder > k; ++k) {
                        for (l = 0; groupOrder > l; ++l) {
                                System.out.print(String.format("%4d", multiplicationTable[k][l]));
                        }
                        System.out.println();
                }
                System.out.println();
        }
        
        public void displayConjugacyTable() {
                int k, l;
                System.out.println();
                System.out.println("Conjugacy Table:");
                for (k = 0; groupOrder > k; ++k) {
                        System.out.print(String.format("%4d", k));
                }
                System.out.println();
                for (k = 0; groupOrder > k; ++k) {
                        for (l = 0; groupOrder > l; ++l) {
                                System.out.print(String.format("%4d", conjugacyTable[k][l]));
                        }
                        System.out.println();
                }
                System.out.println();
        }
        
        public void displayElementsProperties() {
                int k;
                System.out.println();
                System.out.println("Elements Properties:");
                System.out.println("  Elem   Invs   Ordr   Conj   Indx");
                for (k = 0; groupOrder > k; ++k) {
                        System.out.println(String.format("%6d %6d %6d %6d %6d", k, inverseElements[k],
                                        elementsOrders[k], conjugacyNumber[k], conjugacyClassIndex[k]));
                }
                System.out.println();
        }
        
        public void displayConjugacyClasses() {
                int k, l, limit;
                System.out.println();
                System.out.println("Conjugacy Classes:");
                System.out.println("Index Size    List of elements");
                for (k = 0; conjugacyClasses.length > k; ++k) {
                        limit = conjugacyClasses[k].length;
                        System.out.print(String.format("%5d %4d    %d", k, limit, conjugacyClasses[k][0]));
                        for (l = 1; limit > l; ++l) {
                                System.out.print(String.format(", %d", conjugacyClasses[k][l]));
                        }
                        System.out.println();
                }
                System.out.println();
        }
        
        public SubgroupsRecordClass educeSubgroups() {
                final String rankLetters = "-ABDEFHJKLMNPQRSTUVWXYZ";
                int k, l, m, n, rank, limit;
                int[] tmpArray1, orderCount;
                int[][] tmpArray2;
                boolean[] flags;
                SubgroupClass currentSubgroup, newSubgroup;
                Queue<SubgroupClass> currentQueue, nextQueue;
                TreeMap<SubgroupClass, TreeSet<int[]>> generatorsMap;
                TreeSet<int[]> generatorSets;
                Iterator<int[]> intArrIterator;
                Iterator<SubgroupClass> subgroupsIterator;
                TreeSet<SubgroupClass> subgroupsList, subgroupsBatch;
                SubgroupsRecordClass result;
                //==========================================================
                Comparator<int[]> intArrComp = (int[] arg1, int[] arg2) -> {
                        int i;
                        if (arg1.length != arg2.length) {
                                throw new IllegalArgumentException("\n\nArrays being comparing must be the same length.\n\n");
                        }
                        for (i = 0; arg1.length > i; ++i) {
                                if (arg1[i] > arg2[i]) {
                                        return 1;
                                }
                                if (arg1[i] < arg2[i]) {
                                        return -1;
                                }
                        }
                        return 0;
                };
                //==========================================================
                subgroupsList = new TreeSet<>();
                result = new SubgroupsRecordClass();
                result.elementCycles = new SubgroupClass[groupOrder];
                orderCount = new int[groupOrder + 1];
                generatorsMap = new TreeMap<>();
                for (k = 1; groupOrder > k; ++k) {
                        currentSubgroup = generateCycle(k);
                        if (subgroupsList.add(currentSubgroup)) {
                                currentSubgroup.rank = 1;
                                generatorSets = new TreeSet<>(intArrComp);
                                generatorsMap.put(currentSubgroup, generatorSets);
                                ++orderCount[currentSubgroup.getOrder()];
                        } else {
                                currentSubgroup = subgroupsList.floor(currentSubgroup);
                                generatorSets = generatorsMap.get(currentSubgroup);
                        }
                        generatorSets.add(new int[] {k});
                        result.elementCycles[k] = currentSubgroup;
                }
                result.cyclesList = new SubgroupClass[subgroupsList.size()];
                subgroupsIterator = subgroupsList.iterator();
                k = 0;
                m = 0;
                n = 0;
                while (subgroupsIterator.hasNext()) {
                        currentSubgroup = subgroupsIterator.next();
                        if (m != currentSubgroup.getOrder()) {
                                m = currentSubgroup.getOrder();
                                n = 1;
                        }
                        if (groupOrder == m) {
                                currentSubgroup.id = "G";
                        } else {
                                if (1 == orderCount[m]) {
                                        currentSubgroup.id = "C" + m;
                                } else {
                                        currentSubgroup.id = "C" + m + "-" + n;
                                }
                        }
                        ++n;
                        generatorSets = generatorsMap.get(currentSubgroup);
                        tmpArray2 = new int[generatorSets.size()][];
                        intArrIterator = generatorSets.iterator();
                        l = 0;
                        while (intArrIterator.hasNext()) {
                                tmpArray2[l] = intArrIterator.next();
                                ++l;
                        }
                        currentSubgroup.generators = tmpArray2;
                        result.cyclesList[k] = currentSubgroup;
                        ++k;
                }
                //==========================================================
                currentQueue = new ArrayDeque<>(subgroupsList);
                rank = 2;
                while (!currentQueue.isEmpty()) {
                        nextQueue = new ArrayDeque<>();
                        generatorsMap = new TreeMap<>();
                        subgroupsBatch = new TreeSet<>();
                        orderCount = new int[groupOrder + 1];
                        while (!currentQueue.isEmpty()) {
                                currentSubgroup = currentQueue.poll();
                                for (k = 0; result.cyclesList.length > k; ++k) {
                                        newSubgroup = computeSubgroupsProduct(currentSubgroup, result.cyclesList[k]);
                                        if (subgroupsList.add(newSubgroup)) {
                                                newSubgroup.rank = rank;
                                                subgroupsBatch.add(newSubgroup);
                                                generatorSets = new TreeSet<>(intArrComp);
                                                generatorsMap.put(newSubgroup, generatorSets);
                                                ++orderCount[newSubgroup.getOrder()];
                                        } else {
                                                newSubgroup = subgroupsList.floor(newSubgroup);
                                                generatorSets = generatorsMap.get(newSubgroup);
                                        }
                                        if (rank == newSubgroup.rank) {
                                                for (l = 0; currentSubgroup.generators.length > l; ++l) {
                                                        for (m = 0; result.cyclesList[k].generators.length > m; ++m) {
                                                                tmpArray1 = Arrays.copyOf(currentSubgroup.generators[l], rank);
                                                                tmpArray1[rank - 1] = result.cyclesList[k].generators[m][0];
                                                                Arrays.sort(tmpArray1);
                                                                generatorSets.add(tmpArray1);
                                                        }
                                                }
                                        }
                                }
                        }
                        subgroupsIterator = subgroupsBatch.iterator();
                        m = 0;
                        n = 0;
                        while (subgroupsIterator.hasNext()) {
                                currentSubgroup = subgroupsIterator.next();
                                nextQueue.add(currentSubgroup);
                                if (m != currentSubgroup.getOrder()) {
                                        m = currentSubgroup.getOrder();
                                        n = 1;
                                }
                                if (groupOrder == m) {
                                        currentSubgroup.id = "G";
                                } else {
                                        if (1 == orderCount[m]) {
                                                currentSubgroup.id = rankLetters.substring(rank - 1, rank) + m;
                                        } else {
                                                currentSubgroup.id = rankLetters.substring(rank - 1, rank) + m + "-" + n;
                                        }
                                }
                                ++n;
                                generatorSets = generatorsMap.get(currentSubgroup);
                                tmpArray2 = new int[generatorSets.size()][];
                                intArrIterator = generatorSets.iterator();
                                l = 0;
                                while (intArrIterator.hasNext()) {
                                        tmpArray2[l] = intArrIterator.next();
                                        ++l;
                                }
                                currentSubgroup.generators = tmpArray2;
                        }
                        currentQueue = nextQueue;
                        ++rank;
                }
                //==========================================================
                newSubgroup = new SubgroupClass(new int[] {0});
                newSubgroup.id = "I";
                subgroupsList.add(newSubgroup);
                limit = subgroupsList.size();
                result.inclusionTable = new int[limit][limit];
                result.subgroupsList = new SubgroupClass[limit];
                subgroupsIterator = subgroupsList.iterator();
                k = 0;
                while (subgroupsIterator.hasNext()) {
                        currentSubgroup = subgroupsIterator.next();
                        result.subgroupsList[k] = currentSubgroup;
                        currentSubgroup.index = k;
                        l = 0;
                        limit = currentSubgroup.getOrder();
                        while (true) {
                                newSubgroup = result.subgroupsList[l];
                                if (limit <= newSubgroup.getOrder()) {
                                        break;
                                }
                                if (currentSubgroup.include(newSubgroup)) {
                                        result.inclusionTable[l][k] = 1;
                                }
                                ++l;
                        }
                        ++k;
                }
                limit = subgroupsList.size();
                for (k = 0; limit > k; ++k) {
                        for (l = 0; limit > l; ++l) {
                                if (0 != result.inclusionTable[k][l]) {
                                        for (m = 0; limit > m; ++m) {
                                                if (0 != result.inclusionTable[l][m]) {
                                                        result.inclusionTable[k][m] = 2;
                                                }
                                        }
                                }
                        }
                }
                for (k = 0; limit > k; ++k) {
                        subgroupsBatch = new TreeSet<>();
                        for (l = 0; limit > l; ++l) {
                                if (1 == result.inclusionTable[k][l]) {
                                        subgroupsBatch.add(result.subgroupsList[l]);
                                }
                        }
                        result.subgroupsList[k].parents = new SubgroupClass[subgroupsBatch.size()];
                        result.subgroupsList[k].parents = subgroupsBatch.toArray(result.subgroupsList[k].parents);
                }
                //==========================================================
                for (k = 1; limit > k; ++k) {
                        if (1 < result.subgroupsList[k].rank) {
                                generatorSets = new TreeSet<>(intArrComp);
                                tmpArray2 = new int[result.subgroupsList[k].generators.length][result.subgroupsList[k].rank];
                                for (l = 0; result.subgroupsList[k].generators.length > l; ++l) {
                                        tmpArray1 = new int[result.subgroupsList[k].rank];
                                        for (m = 0; result.subgroupsList[k].rank > m; ++m) {
                                                tmpArray1[m] = elementsOrders[result.subgroupsList[k].generators[l][m]];
                                        }
                                        Arrays.sort(tmpArray1);
                                        generatorSets.add(tmpArray1);
                                        tmpArray2[l] = tmpArray1;
                                }
                                intArrIterator = generatorSets.iterator();
                                result.subgroupsList[k].generatorsTypes = new int[generatorSets.size()][];
                                result.subgroupsList[k].generatorsByType = new int[generatorSets.size()][];
                                l = 0;
                                while (intArrIterator.hasNext()) {
                                        tmpArray1 = intArrIterator.next();
                                        result.subgroupsList[k].generatorsTypes[l] = tmpArray1;
                                        result.subgroupsList[k].generatorsByType[l] = new int[result.subgroupsList[k].generators.length];
                                        n = 0;
                                        for (m = 0; result.subgroupsList[k].generators.length > m; ++m) {
                                                if (Arrays.equals(tmpArray1, tmpArray2[m])) {
                                                        result.subgroupsList[k].generatorsByType[l][n] = m;
                                                        ++n;
                                                }
                                        }
                                        result.subgroupsList[k].generatorsByType[l] = Arrays.copyOf(result.subgroupsList[k].generatorsByType[l], n);
                                        ++l;
                                }
                        }
                }
                //==========================================================
                flags = new boolean[limit];
                for (k = 0; limit > k; ++k) {
                        if (!flags[k]) {
                                subgroupsBatch = new TreeSet<>();
                                for (l = 0; groupOrder > l; ++l) {
                                        tmpArray1 = result.subgroupsList[k].elements;
                                        tmpArray1 = Arrays.copyOf(tmpArray1, tmpArray1.length);
                                        for (m = 0; tmpArray1.length > m; ++m) {
                                                tmpArray1[m] = conjugacyTable[tmpArray1[m]][l];
                                        }
                                        Arrays.sort(tmpArray1);
                                        subgroupsBatch.add(new SubgroupClass(tmpArray1));
                                }
                                result.subgroupsList[k].conjugates = new SubgroupClass[subgroupsBatch.size()];
                                subgroupsIterator = subgroupsBatch.iterator();
                                l = 0;
                                while (subgroupsIterator.hasNext()) {
                                        currentSubgroup = subgroupsList.floor(subgroupsIterator.next());
                                        flags[currentSubgroup.index] = true;
                                        result.subgroupsList[k].conjugates[l] = currentSubgroup;
                                        currentSubgroup.conjugates = result.subgroupsList[k].conjugates;
                                        ++l;
                                }
                        }
                }
                return result;
        }
        
        private SubgroupClass generateCycle(int arg) {
                int k;
                int[] result;
                ArrayList<Integer> list = new ArrayList<>();
                Integer tmp = new Integer(arg);
                while (true) {
                        list.add(tmp);
                        if (0 == tmp) {
                                break;
                        }
                        tmp = new Integer(multiplicationTable[arg][tmp]);
                }
                result = new int[list.size()];
                for (k = 0; list.size() > k; ++k) {
                        result[k] = list.get(k);
                }
                Arrays.sort(result);
                return new SubgroupClass(result);
        }
        
        private SubgroupClass computeSubgroupsProduct(SubgroupClass arg1, SubgroupClass arg2) {
                int k;
                int[] result;
                Integer element, newElement;
                Iterator<Integer> iterator;
                Set<Integer> collector, currentSet, nextSet, tmpSet;
                Queue<Integer> currentQueue, nextQueue;
                collector = new TreeSet<>();
                currentSet = new TreeSet<>();
                nextSet = new TreeSet<>();
                for (k = 0; arg1.elements.length > k; ++k) {
                        element = new Integer(arg1.elements[k]);
                        collector.add(element);
                        currentSet.add(element);
                }
                for (k = 0; arg2.elements.length > k; ++k) {
                        element = new Integer(arg2.elements[k]);
                        if (collector.add(element)) {
                                nextSet.add(element);
                        } else {
                                currentSet.remove(element);
                        }
                }
                currentQueue = new ArrayDeque<>(nextSet);
                while (!currentQueue.isEmpty()) {
                        nextQueue = new ArrayDeque<>();
                        while (!currentQueue.isEmpty()) {
                                element = currentQueue.poll();
                                iterator = currentSet.iterator();
                                while (iterator.hasNext()) {
                                        newElement = new Integer(multiplicationTable[element][iterator.next()]);
                                        if (collector.add(newElement)) {
                                                nextQueue.add(newElement);
                                        }
                                }
                        }
                        currentQueue = nextQueue;
                        tmpSet = currentSet;
                        currentSet = nextSet;
                        nextSet = tmpSet;
                }
                result = new int[collector.size()];
                iterator = collector.iterator();
                k = 0;
                while (iterator.hasNext()) {
                        result[k] = iterator.next();
                        ++k;
                }
                return new SubgroupClass(result);
        }
}
 

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

public class SubgroupsRecordClass {
        
        public SubgroupClass[] elementCycles;
        public SubgroupClass[] cyclesList;
        public SubgroupClass[] subgroupsList;
        public int[][] inclusionTable;
        
        public void displayCycles() {
                int k;
                for (k = 0; cyclesList.length > k; ++k) {
                        cyclesList[k].display();
                }
        }
        
        public void displaySubgroups() {
                int k;
                System.out.println();
                System.out.println("Subgroups List:");
                System.out.println();
                for (k = 0; subgroupsList.length > k; ++k) {
                        subgroupsList[k].display();
                }
        }
        
        public void displayInclusionTable() {
                int k, l;
                System.out.println();
                System.out.println("Subgroups Inclusion Table:");
                System.out.print("   ");
                for (l = 0; subgroupsList.length > l; ++l) {
                        System.out.print(String.format("%3d", l));
                }
                System.out.println();
                for (k = 0; subgroupsList.length > k; ++k) {
                        System.out.print(String.format("%3d", k));
                        for (l = 0; subgroupsList.length > l; ++l) {
                                System.out.print(String.format("%3d", inclusionTable[k][l]));
                        }
                        System.out.println();
                }
                System.out.println();
        }
}
 

[arseniiv]

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

Остальные части программы. Было б здорово, если бы кто-нибудь постестил, а то вдруг я забыл или потёр лишнее, чтобы влезло в пост.

Ну есть же многофайловые pastebin’ы (типа github gist). Там ничего укорачивать не придётся. Хотя когда по весу тянет на проект, можно и репозиторий где-нибудь хостить.

[B@R5uk]

arseniiv, а вам не интересно потестить? Или нет джавы под рукой?

Вот, например, результат для диэдральной группы $\operatorname{Dih}_3$:

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

Multiplication Table:
   0   1   2   3   4   5
   1   0   3   2   5   4
   2   4   5   1   3   0
   3   5   4   0   2   1
   4   2   1   5   0   3
   5   3   0   4   1   2


Conjugacy Table:
   0   1   2   3   4   5
   0   0   0   0   0   0
   1   1   3   4   3   4
   2   5   2   5   5   2
   3   4   4   3   1   1
   4   3   1   1   4   3
   5   2   5   2   2   5


Elements Properties:
  Elem   Invs   Ordr   Conj   Indx
     0      0      1      1      0
     1      1      2      3      1
     2      5      3      2      2
     3      3      2      3      1
     4      4      2      3      1
     5      2      3      2      2


Conjugacy Classes:
Index Size    List of elements
    0    1    0
    1    3    1, 3, 4
    2    2    2, 5


Subgroups List:

id: "I"; order: 1; rank: 0; index: 0
        elements: 0
        generators: none
        conjugates (1): "I"
        parents: "C2-1", "C2-2", "C2-3", "C3"

id: "C2-1"; order: 2; rank: 1; index: 1
        elements: 0, 1
        generators (1): 1
        conjugates (3): "C2-1", "C2-2", "C2-3"
        parents: "G"

id: "C2-2"; order: 2; rank: 1; index: 2
        elements: 0, 3
        generators (1): 3
        conjugates (3): "C2-1"
        parents: "G"

id: "C2-3"; order: 2; rank: 1; index: 3
        elements: 0, 4
        generators (1): 4
        conjugates (3): "C2-1"
        parents: "G"

id: "C3"; order: 3; rank: 1; index: 4
        elements: 0, 2, 5
        generators (2): 2, 5
        conjugates (1): "C3"
        parents: "G"

id: "G"; order: 6; rank: 2; index: 5
        elements: 0, 1, 2, 3, 4, 5
        generators (9): {1; 2},  {1; 3},  {1; 4},  {1; 5},  {2; 3},  {2; 4},  {3; 4},  {3; 5},  {4; 5}
        conjugates (1): "G"
        parents: none


Subgroup "G" generators by type:
    Type 2-2 (3):
        {1; 3}, {1; 4}, {3; 4}
    Type 2-3 (6):
        {1; 2}, {1; 5}, {2; 3}, {2; 4}, {3; 5}, {4; 5}
 

Видно, что группу можно породить парой элементов 2-го порядка оба и парой элементов 2-го и 3-го порядка. В первом случае есть 3 таких пары, но, поскольку их можно взять в любом порядке, то получается 6 комбинаций для автоморфизма группы. Во втором случае есть сразу 6 пар для 6 автоморфизмов. Конкретно в случае этой группы автоморфизмы даже проверять не надо: достаточно посмотреть на таблицу сопряжения. Видно, что сопряжение с помощью каждого элемента группы порождает перестановку группы. Композиция двух сопряжений — это умножение элемента первого сопряжения слева на элемент второго сопряжения. Все автоморфизмы внутренние, и группа автоморфизмов получается равна исходной группе. (Единственное, с порядком умножения не очень понятно).

[arseniiv]

(Оффтоп)

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

Или нет джавы под рукой?

Какая-то есть, и старый уже к этому времени Єclipse, но выглядит как морока… (так как я на джаве почти не писал и в итоге придётся возиться, чтобы всё устроить как следует).

Но тема мне очень нравится!

[B@R5uk]

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

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

"I"      0   1   2   3   4   5   6   7   8   9  10  11
"f"      1   0   3   2   5   4   7   6   9   8  11  10
"rrfr"   2   3   0   1   6   7   4   5  10  11   8   9
"rfrr"   3   2   1   0   7   6   5   4  11  10   9   8
"r"      4   7   5   6   8  11   9  10   0   3   1   2
"fr"     5   6   4   7   9  10   8  11   1   2   0   3
"frf"    6   5   7   4  10   9  11   8   2   1   3   0
"rf"     7   4   6   5  11   8  10   9   3   0   2   1
"rr"     8  10  11   9   0   2   3   1   4   6   7   5
"frr"    9  11  10   8   1   3   2   0   5   7   6   4
"rrf"   10   8   9  11   2   0   1   3   6   4   5   7
"rfr"   11   9   8  10   3   1   0   2   7   5   4   6
 

И графом Кэли:



У этой группы 3 элемента 2-го порядка и 8 элементов 3-го порядка. Все элементы 2-го порядка входят в один класс сопряжённости, то есть эквивалентны. Аналогичная ситуация с элементами 3-го порядка. В качестве порождающего множества можно взять один любой элемент 2-го порядка (голубые вершины графа) и один любой элемент 3-го порядка (розовые). Любыми они могут быть, потому что эквивалентны. Всего получается $8\times3=24$ комбинации, что даёт 24 автоморфизма группы тетраэдра $A_4$. Как ни банально, группой автоморфизмов является симметрическая группа $S_4$.

Дальше, моя программа подсказывает мне, что группу тетраэдра можно породить не только образующими 2-го и 3-го порядка, но и двумя образующими только 3-го порядка. Всего таких элементов в группе 8. Но каждый из них имеет обратный, который входит с прямым в одну и ту же подгруппу. В качестве образующих нельзя брать такие элементы, равно как в алгебре нельзя брать в качестве базиса пространства линейнозависимые вектора. Поэтому комбинаций будет не $8\times 7/2=28$, а всего $8\times 6/2=24$. Казалось бы получили те же самые 24 автоморфизма. Ан нет!

Поскольку каждая образующая 3-го порядка в паре порождающего множества друг другу эквивалентна, то их можно поменять местами. То есть всего получается 48 автоморфизмов, что не сходится с расчётом выше. Ответ на этот парадокс оказывается прост: пара паре — рознь. Произведение некоторых образующих 3-го порядка даёт элемент 2-го порядка (например, $r\times r^2f=f$), а некоторых — 3-го (например, $rf\times fr=r^2$). Поэтому эти 24 порождающих множества дальше распадаются на два класса по 12 множеств. Внутри каждого этого класса теперь пары можно не только переставлять, но и заменять друг на друга. Получается как раз 24 автоморфизма.

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



Таблица соответствия элементов:

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

0   I     I     I
1   f     rb    rdd
2   rrfr  br    rrd
3   rfrr  rbbr  rdr
4   r     r     r
5   fr    bb    d
6   frf   brr   ddrr
7   rf    rrb   rrdd
8   rr    rr    rr
9   frr   bbr   dr
10  rrf   b     dd
11  rfr   rbb   rd
 

[B@R5uk]

А верно ли, что если абелева группа содержит только один элемент 2-го порядка, то она циклическая?

-- 08.06.2020, 14:34 --

Ответ: нет. А контрпример: $\mathbb{Z}_6\times\mathbb{Z}_3$. Распознавание групп по таблице умножения — та ещё проблема.

[B@R5uk]

Составил табличку автоморфизмов циклических групп (надеюсь, нигде не ошибся).

$$\begin{tabular}{l|ccccccccccccccc} G&$Z_1$&$Z_2$&$Z_3$&$Z_4$&$Z_5$&$Z_6$&$Z_7$&$Z_8$&$Z_9$&$Z_{10}$&$Z_{11}$&$Z_{12}$&$Z_{13}$&$Z_{14}$&$Z_{15}$\\ \hline Aut(G)&$Z_1$&$Z_1$&$Z_2$&$Z_2$&$Z_4$&$Z_2$&$Z_6$&$Z_2^2$&$Z_6$&$Z_4$&$Z_{10}$&$Z_2^2$&$Z_{12}$&$Z_6$&$Z_4\times Z_2$ \end{tabular}$$

$$\begin{tabular}{l|cccccccccccc} G&$Z_{16}$&$Z_{17}$&$Z_{18}$&$Z_{19}$&$Z_{20}$&$Z_{21}$&$Z_{22}$&$Z_{23}$&$Z_{24}$&$Z_{25}$&$Z_{26}$&$Z_{27}$\\ \hline Aut(G)&$Z_4\times Z_2$&$Z_{16}$&$Z_6$&$Z_{18}$&$Z_4\times Z_2$&$Z_6\times Z_2$&$Z_{10}$&$Z_{22}$&$Z_2^3$&$Z_{20}$&$Z_{12}$&$Z_{18}$ \end{tabular}$$

$$\begin{tabular}{l|cccccccccc} G&$Z_{28}$&$Z_{29}$&$Z_{30}$&$Z_{31}$&$Z_{32}$&$Z_{33}$&$Z_{34}$&$Z_{35}$&$Z_{36}$&$Z_{37}$\\ \hline Aut(G)&$Z_6\times Z_2$&$Z_{28}$&$Z_4\times Z_2$&$Z_{30}$&$Z_8\times Z_2$&$Z_{10}\times Z_2$&$Z_{16}$&$Z_{12}\times Z_2$&$Z_6\times Z_2$&$Z_{36}$ \end{tabular}$$

$$\begin{tabular}{l|cccccccccc} G&$Z_{38}$&$Z_{39}$&$Z_{40}$&$Z_{41}$&$Z_{42}$&$Z_{43}$&$Z_{44}$&$Z_{45}$&$Z_{46}$&$Z_{47}$\\ \hline Aut(G)&$Z_{18}$&$Z_{12}\times Z_2$&$Z_4\times Z_2^2$&$Z_{40}$&$Z_6\times Z_2$&$Z_{42}$&$Z_{10}\times Z_2$&$Z_{12}\times Z_2$&$Z_{22}$&$Z_{46}$ \end{tabular}$$

$$\begin{tabular}{l|cccccccccc} G&$Z_{48}$&$Z_{49}$&$Z_{50}$&$Z_{51}$&$Z_{52}$&$Z_{53}$&$Z_{54}$&$Z_{55}$&$Z_{56}$&$Z_{57}$\\ \hline Aut(G)&$Z_4\times Z_2^2$&$Z_{42}$&$Z_{20}$&$Z_{16}\times Z_2$&$Z_{12}\times Z_2$&$Z_{52}$&$Z_{18}$&$Z_{20}\times Z_2$&$Z_6\times Z_2^2$&$Z_{18}\times Z_2$ \end{tabular}$$

$$\begin{tabular}{l|ccccccccccc} G&$Z_{58}$&$Z_{59}$&$Z_{60}$&$Z_{61}$&$Z_{62}$&$Z_{63}$&$Z_{64}$&$Z_{65}$&$Z_{66}$&$Z_{67}$&$Z_{68}$\\ \hline Aut(G)&$Z_{28}$&$Z_{58}$&$Z_8\times Z_2$&$Z_{60}$&$Z_{30}$&$Z_6^2$&$Z_{16}\times Z_2$&$Z_{12}\times Z_4$&$Z_{10}\times Z_2$&$Z_{66}$&$Z_{16}\times Z_2$ \end{tabular}$$

$$\begin{tabular}{l|ccccccccc} G&$Z_{69}$&$Z_{70}$&$Z_{71}$&$Z_{72}$&$Z_{73}$&$Z_{74}$&$Z_{75}$&$Z_{76}$&$Z_{77}$\\ \hline Aut(G)&$Z_{22}\times Z_2$&$Z_{12}\times Z_2$&$Z_{70}$&$Z_6\times Z_2^2$&$Z_{72}$&$Z_{36}$&$Z_{20}\times Z_2$&$Z_{18}\times Z_2$&$Z_{30}\times Z_2$ \end{tabular}$$

$$\begin{tabular}{l|cccccccccc} G&$Z_{78}$&$Z_{79}$&$Z_{80}$&$Z_{81}$&$Z_{82}$&$Z_{83}$&$Z_{84}$&$Z_{85}$&$Z_{86}$&$Z_{87}$\\ \hline Aut(G)&$Z_{12}\times Z_2$&$Z_{78}$&$Z_4^2\times Z_2$&$Z_{54}$&$Z_{40}$&$Z_{82}$&$Z_6\times Z_2^2$&$Z_{16}\times Z_4$&$Z_{42}$&$Z_{28}\times Z_2$ \end{tabular}$$

Проглядывается некоторая закономерность: ранг результирующей группы определяется фи-функцией Эйлера от ранга исходной группы, а так же автоморфизм группы с составным рангом $n\times m$ можно выразить в виде произведения автоморфизмов: $\operatorname{Aut}(Z_{nm})=\operatorname{Aut}(Z_{n})\times\operatorname{Aut}(Z_{m})$, если числа n и m являются взаимно простыми. Сейчас пытаюсь понять, откуда все эти закономерности берутся.

В целом автоморфизмы циклических групп немного разочаровывают. Все они абелевы, и многие сами являются циклическими группами. Вот не сравнить с $\operatorname{Aut}(Z_2^3)$, порядок которой 168 не смотря на то, что порядок исходной группы всего 8!

-- 08.06.2020, 19:22 --

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

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

import java.util.*;

class ArrayComparator implements Comparator<int[]> {
        public int compare(int[] arg1, int[] arg2) {
                int k;
                if (arg1.length != arg2.length) {
                        throw new IllegalArgumentException("\n\nArrays being comparing must be the same length.\n\n");
                }
                for (k = 0; arg1.length > k; ++k) {
                        if (arg1[k] > arg2[k]) {
                                return 1;
                        }
                        if (arg1[k] < arg2[k]) {
                                return -1;
                        }
                }
                return 0;
        }
}

public class Study_Group_Automorphism {
        
//      static final String[] seedLines = {"1 2 0"};
//      static final String[] seedLines = {"1 2 3 0"};
//      static final String[] seedLines = {"1 2 3 4 0"};
//      static final String[] seedLines = {"1 3 0 5 2 4"};
//      static final String[] seedLines = {"1 2 3 4 5 6 0"};
//      static final String[] seedLines = {"1 3 0 5 2 6 4"};
//      static final String[] seedLines = {"1 2 3 4 5 6 7 0"};
//      static final String[] seedLines = {"1 2 3 4 5 6 7 8 9 10 11 12 13 14 0"};
        /*
        static final String[] seedLines = {""};
        static {
                int k, limit = 87;
                StringBuilder result = new StringBuilder("1");
                for (k = 2; limit > k; ++k) {
                        result.append(" ").append(k);
                }
                result.append(" 0");
                seedLines[0] = result.toString();
        }
        //*/
//      static final int[] genSet = {1};
        
//      static final String[] seedLines = {"1 0 3 2", "2 3 0 1"};
//      static final String[] seedLines = {"1 2 0 4 5 3", "3 5 4 0 2 1"};
//      static final String[] seedLines = {"1 0 3 2 5 4", "2 4 0 5 1 3"};
//      static final String[] seedLines = {"1 0 5 4 3 2", "2 4 0 5 1 3"};
//      static final String[] seedLines = {"1 0 3 2 6 7 4 5 9 8", "2 4 5 1 8 9 0 3 7 6"};
//      static final String[] seedLines = {"1 0 3 2 6 7 4 5 9 8 11 10", "2 4 5 8 9 0 7 10 11 1 6 3"};
//      static final String[] seedLines = {"1 0 3 2 5 4 7 6 9 8 11 10", "4 7 5 6 8 11 9 10 0 3 1 2"};
//      static final String[] seedLines = {"1 2 0 4 5 3 7 8 6 10 11 9", "3 10 8 0 7 11 9 4 2 6 1 5"};
//      static final String[] seedLines = {"4 5 6 7 8 9 10 11 0 1 2 3", "10 11 8 9 1 0 3 2 7 6 5 4"};
//      static final String[] seedLines = {"4 5 6 7 8 9 10 11 0 1 2 3", "5 4 7 6 11 10 9 8 2 3 0 1"};
//      static final String[] seedLines = {"1 3 4 9 6 7 5 10 11 13 8 2 14 15 0 12", "2 5 0 8 9 1 12 13 3 4 14 15 6 7 10 11"};
//      static final String[] seedLines = {"1 2 4 5 8 11 12 15 18 19 21 22 25 26 28 29 32 35 0 3 6 7 9 10 13 14 16 17 20 23 24 27 30 31  33  34", "3 5 11 14 22 28 31 1 9 12 18 20 27 29 35 2 10 16 19 25 33 0 6 8 15 17 23 26 34 4 7 13 21 24 30 32"};
//      static final int[] genSet = {1, 3};
        
        static final String[] seedLines = {"1 0 4 5 2 3 7 6", "2 4 0 6 1 7 3 5", "3 5 6 0 7 1 2 4"};
        static final int[] genSet = {1, 2, 3};
        
        public static void main(String[] args) {
                int k, l, limit, value;
                int[] permutation, substitution;
                int[][] decomposition;
                GroupClass group, autGroup;
                Map<int[], Integer> map;
                //==================================================================
                group = new GroupClass(seedLines);
                decomposition = group.decomposeBy(genSet);
                group.displayTable();
                System.out.println();
                //System.out.println(Arrays.deepToString(decomposition));
                //==================================================================
                limit = group.getOrder();
                map = new TreeMap<>(new ArrayComparator());
                permutation = new int[limit];
                for (k = 1; limit > k; ++k) {
                        permutation[k] = k;
                }
                map.put(permutation, 0);
                System.out.println("Elements permutations:");
                System.out.print("   0: ");
                System.out.println(Arrays.toString(permutation));
                substitution = new int[genSet.length];
                l = 1;
                outerLoop:
                while (true) {
                        permutation = group.compilePermutation(decomposition, substitution);
                        if (null != permutation) {
                                if (group.checkPermutation(permutation)) {
                                        if (!map.containsKey(permutation)) {
                                                map.put(permutation, l);
                                                System.out.print(String.format("%4d: ", l));
                                                System.out.println(Arrays.toString(permutation));
                                                ++l;
                                        }
                                }
                        }
                        k = 0;
                        while (true) {
                                value = substitution[k];
                                ++value;
                                if (limit == value) {
                                        substitution[k] = 0;
                                        ++k;
                                        if (genSet.length == k) {
                                                break outerLoop;
                                        }
                                } else {
                                        substitution[k] = value;
                                        break;
                                }
                        }
                }
                System.out.println();
                //==================================================================
                autGroup = new GroupClass(map);
                //autGroup.displayTable();
                autGroup.displayElementsOrders();
                //autGroup.displayTableSeed(new int[] {1, 8, 9});
        }
}
 

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

import java.util.*;

public class GroupClass {
        
        private int groupOrder;
        private int[][] table;
        private int[] elementsOrders;
        
        public GroupClass(int[][] arg) {
                int k, l, value;
                int[] currentLine, newLine;
                boolean[] flags;
                Queue<int[]> queue = new ArrayDeque<>();
                groupOrder = arg[0].length;
                for (k = 0; arg.length > k; ++k) {
                        if (groupOrder != arg[k].length) {
                                throw new IllegalArgumentException("\n\nIncorrect seed lines: lengths mismatch.\n\n");
                        }
                        flags = new boolean[groupOrder];
                        for (l = 0; groupOrder > l; ++l) {
                                value = arg[k][l];
                                if (0 > value || groupOrder <= value) {
                                        throw new IllegalArgumentException("\n\nIncorrect seed lines: wrong element number.\n\n");
                                }
                                if (flags[value]) {
                                        throw new IllegalArgumentException("\n\nIncorrect seed lines: duplicate elements.\n\n");
                                } else {
                                        flags[value] = true;
                                }
                        }
                }
                flags = new boolean[groupOrder];
                table = new int[groupOrder][];
                table[0] = new int[groupOrder];
                for (k = 0; groupOrder > k; ++k) {
                        table[0][k] = k;
                }
                flags[0] = true;
                for (k = 0; arg.length > k; ++k) {
                        value = arg[k][0];
                        if (flags[value]) {
                                throw new IllegalArgumentException("\n\nIncorrect seed lines: duplicate lines.\n\n");
                        } else {
                                newLine = Arrays.copyOf(arg[k], groupOrder);
                                table[value] = newLine;
                                flags[value] = true;
                                queue.add(newLine);
                        }
                }
                while (!queue.isEmpty()) {
                        currentLine = queue.poll();
                        for (k = 0; arg.length > k; ++k) {
                                newLine = linesPermutation(currentLine, arg[k]);
                                value = newLine[0];
                                if (!flags[value]) {
                                        table[value] = newLine;
                                        flags[value] = true;
                                        queue.add(newLine);
                                }
                        }
                }
                for (k = 0; groupOrder > k; ++k) {
                        if (null == table[k]) {
                                throw new IllegalArgumentException("\n\nIncorrect seed lines: incomplete table.\n\n");
                        }
                }
                for (k = 0; groupOrder > k; ++k) {
                        flags = new boolean[groupOrder];
                        for (l = 0; groupOrder > l; ++l) {
                                value = table[l][k];
                                if (flags[value]) {
                                        throw new IllegalArgumentException("\n\nIncorrect seed lines: erroneous table.\n\n");
                                } else {
                                        flags[value] = true;
                                }
                        }
                }
                computeElementsOrders();
        }
        
        public GroupClass(String[] arg) {
                this(newArg(arg));
        }
        
        public GroupClass(Map<int[], Integer> arg) {
                int[] x, y;
                Iterator<int[]> k, l;
                Set<int[]> permutSet = arg.keySet();
                groupOrder = arg.size();
                table = new int[groupOrder][groupOrder];
                k = permutSet.iterator();
                while (k.hasNext()) {
                        x = k.next();
                        l = permutSet.iterator();
                        while (l.hasNext()) {
                                y = l.next();
                                table[arg.get(x)][arg.get(y)] = arg.get(linesPermutation(x, y));
                        }
                }
                computeElementsOrders();
        }
        
        public int getOrder() {
                return groupOrder;
        }
        
        private static int[][] newArg(String[] arg) {
                int k;
                int[][] result = new int[arg.length][];
                for (k = 0; arg.length > k; ++k) {
                        result[k] = decodeString(arg[k]);
                }
                return result;
        }
        
        private static int[] decodeString(String arg) {
                int k, value, digit;
                int[] result;
                boolean flag;
                ArrayList<Integer> collector = new ArrayList<>();
                k = 0;
                value = 0;
                flag = false;
                while (arg.length() > k) {
                        digit = arg.charAt(k) - '0';
                        ++k;
                        if (0 <= digit && digit <= 9) {
                                value = value * 10 + digit;
                                flag = true;
                        } else {
                                if (flag) {
                                        collector.add(new Integer(value));
                                        value = 0;
                                        flag = false;
                                }
                        }
                }
                if (flag) {
                        collector.add(new Integer(value));
                }
                value = collector.size();
                result = new int[value];
                for (k = 0; value > k; ++k) {
                        result[k] = collector.get(k);
                }
                return result;
        }
        
        private void computeElementsOrders() {
                int k, element, order;
                elementsOrders = new int[groupOrder];
                for (k = 0; groupOrder > k; ++k) {
                        element = 0;
                        order = 0;
                        do {
                                element = table[element][k];
                                ++order;
                        } while (0 != element);
                        elementsOrders[k] = order;
                }
        }
        
        private static int[] linesPermutation(int[] arg1, int[] arg2) {
                int k;
                int[] result = new int[arg1.length];
                for (k = 0; arg1.length > k; ++k) {
                        result[k] = arg1[arg2[k]];
                }
                return result;
        }
        
        public void displayTable() {
                int k, l;
                System.out.println();
                System.out.println("Multiplication Table:");
                for (k = 0; groupOrder > k; ++k) {
                        for (l = 0; groupOrder > l; ++l) {
                                System.out.print(String.format("%4d", table[k][l]));
                        }
                        System.out.println();
                }
                System.out.println();
        }
        
        public int[][] decomposeBy(int[] arg) {
                int k, l, currentElement, newElement;
                int[][] result = new int[groupOrder][3];
                boolean[] flags = new boolean[groupOrder];
                Queue<Integer> queue = new ArrayDeque<>();
                queue.add(new Integer(0));
                result[0] = new int[0];
                flags[0] = true;
                l = 1;
                while (!queue.isEmpty()) {
                        currentElement = queue.poll();
                        for (k = 0; arg.length > k; ++k) {
                                newElement = table[arg[k]][currentElement];
                                if (!flags[newElement]) {
                                        queue.add(new Integer(newElement));
                                        result[l][0] = newElement;
                                        result[l][1] = k;
                                        result[l][2] = currentElement;
                                        flags[newElement] = true;
                                        ++l;
                                }
                        }
                }
                if (groupOrder != l) {
                        throw new IllegalArgumentException("\n\nIncorrect generating set.\n\n");
                }
                return result;
        }
        
        public int[] compilePermutation(int[][] arg1, int[] arg2) {
                int k, element;
                int[] result = new int[groupOrder];
                boolean[] flags = new boolean[groupOrder];
                for (k = 1; groupOrder > k; ++k) {
                        element = table[arg2[arg1[k][1]]][result[arg1[k][2]]];
                        if (flags[element]) {
                                return null;
                        }
                        result[arg1[k][0]] = element;
                        flags[element] = true;
                }
                return result;
        }
        
        public boolean checkPermutation(int[] arg) {
                int k, l;
                for (k = 0; groupOrder > k; ++k) {
                        for (l = 0; groupOrder > l; ++l) {
                                if (arg[table[k][l]] != table[arg[k]][arg[l]]) {
                                        return false;
                                }
                        }
                }
                return true;
        }
        
        public void displayTableSeed(int[] arg) {
                int k, l;
                boolean flag1, flag2;
                flag1 = false;
                System.out.println();
                System.out.print("{");
                for (k = 0; arg.length > k; ++k) {
                        if (flag1) {
                                System.out.println(",");
                        } else {
                                flag1 = true;
                        }
                        System.out.print("{");
                        flag2 = false;
                        for (l = 0; groupOrder > l; ++l) {
                                if (flag2) {
                                        System.out.print(", " + table[arg[k]][l]);
                                } else {
                                        flag2 = true;
                                        System.out.print(table[arg[k]][l]);
                                }
                        }
                        System.out.print("}");
                }
                System.out.println("}");
                System.out.println();
        }
        
        public void displayElementsOrders() {
                int k, l;
                ArrayList<Integer> collector;
                Iterator<Integer> iterator;
                System.out.println();
                System.out.println("Elements by order:");
                for (k = 1; groupOrder >= k; ++k) {
                        if (0 == groupOrder % k) {
                                collector = new ArrayList<>();
                                for (l = 0; groupOrder > l; ++l) {
                                        if (k == elementsOrders[l]) {
                                                collector.add(new Integer(l));
                                        }
                                }
                                if (!collector.isEmpty()) {
                                        System.out.print(String.format("%4d (%d): ", k, collector.size()));
                                        iterator = collector.iterator();
                                        l = 0;
                                        while (iterator.hasNext()) {
                                                if (0 == l) {
                                                        l = 1;
                                                } else {
                                                        System.out.print(", ");
                                                }
                                                System.out.print(String.format("%d", iterator.next()));
                                        }
                                        System.out.println();
                                }
                        }
                }
                System.out.println();
        }
}
 

[mihaild]

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

ранг результирующей группы определяется фи-функцией Эйлера от ранга исходной группы

Автоморфизм $\mathbb Z_n$ однозначно задается образом единицы. А в какие элементы может перейти $1$, чтобы получился автоморфизм?

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

автоморфизм группы с составным рангом $n\times m$ можно выразить в виде произведения автоморфизмов: $\operatorname{Aut}(Z_{nm})=\operatorname{Aut}(Z_{n})\times\operatorname{Aut}(Z_{m})$, если числа n и m являются взаимно простыми

Это правда. Хороший способ понять, почему - попробовать из пары автоморфизмов $\mathbb Z_n$ и $\mathb Z_m$ собрать автоморфизм $\mathbb Z_{nm}$, а потом его разобрать обратно на пару.
Если сходу не получается - то как хотя бы из афтоморфизма $\mathbb Z_n$ сделать автоморфизм $\mathbb Z_{nm}$?

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

Все они абелевы

Это следует из того, что автоморфизм циклической группы - это по сути умножение на число (пофакторизованное, но от факторизации абелевость не пропадает).

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

и многие сами являются циклическими группами

Это только в начале так, дальше реже будут. Точный результат известен (есть например в английской википедии). Закономерность тут может быть увидеть сможете, но доказывается он не совсем тривиально.

[B@R5uk]

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

Автоморфизм $\mathbb Z_n$ однозначно задается образом единицы. А в какие элементы может перейти $1$, чтобы получился автоморфизм?

Это как раз просто. Только мне нравится больше групповое толкование, а не теоретико-числовое. Циклическая группа по определению имеет ранг 1, то есть имеет одну образующую, порядок которой совпадает с порядком группы. В качестве образующей можно взять любой элемент, имеющий тот же порядок. Оказывается, что такие элементы выражаются через степень образующей, которая взаимно проста с порядком группы. Отсюда функция Эйлера. Я понимаю, что это не строгое доказательство, а всего лишь отсылка к таковому, но всё же.

С остальным думать надо.

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

Это только в начале так, дальше реже будут. Точный результат известен

Я натыкался на что-то такое в вики про "мультипликативную группу кольца вычетов". Там пишут, что цикл получается для любой нечётной степени простого числа, удвоенной степени и для 4. Понятно, что с ростом порядка такие числа встречаются реже.

Ещё забавно, что иногда произведение $\mathbb Z_n\times\mathbb Z_m$ имеет ранг 2 и может быть представлено в виде произведения $\mathbb Z_k\times\mathbb Z_l$, где $n\times m=k\times l$, но $\{n,\;m\}\ne\{k,\;l\}$. Если потребовать, чтобы число l было минимально возможным, то такое представление единственно для любой пары $\{n,\;m\}$, но весьма хитро выражается. Я замечал некоторые закономерности, но пока не нашёл общей формулы.

[mihaild]

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

Я замечал некоторые закономерности, но пока не нашёл общей формулы

А какие-то закономерности, когда $\mathbb Z_n \times \mathbb Z_n$ имеет ранг 1, а когда 2, заметили? Это будет подсказкой, как посчитать $l$ (в частности, $l = 1$ если ранг 1).
Если надоест думать - посмотрите теорему о классификации конечнопорожденных абелевых групп, из неё это всё получается с закрытыми глазами.

[B@R5uk]

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

А какие-то закономерности, когда $\mathbb Z_n \times \mathbb Z_m$ имеет ранг 1, а когда 2, заметили?

Это мы ещё здесь давно уже обсуждали. Да, пожалуй l — это наибольший общий делитель n и m. Меня смутило то, что множители перераспределяются так, что бы в произведении $\mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}\times\mathbb{Z}_{n_3}\times...$ каждый следующий порядок должен делить предыдущий.

[mihaild]

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

Меня смутило то, что множители перераспределяются так, что бы в произведении $\mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}\times\mathbb{Z}_{n_3}\times...$

Вот это непонятно. Мы начали с произведения двух циклических групп, дальше вы его как-то раскладываете в произведение циклических групп - как?