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

[Munin]

B@R5uk
Ваши "слоистые" неабелевы группы - это, видимо, полупрямые произведения. Про которые вам говорили в теме выше.

[B@R5uk]

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

это, видимо, полупрямые произведения.

Они и есть. Даже больше: это полупрямые произведения циклических групп.

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

[B@R5uk]

Someone в сообщении #1440300 писал(а):

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

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

Забудьте.

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

Обратную решить можно. Прямую - нет.

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

[mihaild]

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

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

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

[B@R5uk]

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

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

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

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

Последнее упрощение, которое я делаю, заключается в том, что я рассматриваю группы только с двумя образующими. Хотя, на самом деле, оно не на столько серьёзно, как предыдущее. Работа со строками не зависит от алфавита вообще; он понадобится только на этапе построения списка элементов. Это упрощение для того, чтобы получить хоть что-то работающее.

Формальная абстрактная процедура построения группы заключается в том, что из образующих и их обратных строятся всевозможные комбинации, а затем, с помощью групповых соотношений, эти комбинации разбиваются на классы эквивалентности, которые и считаются элементами группы. Эта процедура на столько общая, что даже позволяет построить бесконечные группы. Разумеется, на практике она не применима. В связи с этим нужно разработать другой, более "приземлённый" алгоритм.

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

Итерация процедуры заключается в том, что мы достаём из очереди элемент g (очередь типа FIFO — первый вошёл, первый вышел) и проверяем, присутствует ли этот элемент в заполняемом множестве G. Если уже присутствует, то элемент отбрасывается. Если он отсутствует, то мы поступаем с ним так же, как с единичным элементом в инициализации: дописываем к g по одному символу из алфавита, все результаты добавляем в очередь, а сам элемент g добавляем во множество G. Итерации продолжаются до тех пор, пока очередь не опустеет.

Продемонстрирую это на примере недавно изученной мной группы $A_4$. Алфавитом является множество символов r, f.



0) Инициализация: множество G содержит пустую строку "", а очередь Q — строки "r", "f"
1) Достаём из очереди элемент "r", он в G отсутствует, поэтому добавляем в очередь элементы "rr", "rf", а элемент "r" — в G. Итого: G содержит "", "r", а очередь Q — "f", "rr", "rf"
2) Достаём из Q элемент "f", он так же в G отсутствует, добавляем его в G, а в очередь — элементы "fr", "ff". Итого: G содержит "", "r", "f", а очередь Q — "rr", "rf", "fr", "ff".
3) Достаём из Q строку "rr", она отсутствует в G, добавляем её. В очередь Q идут строки "rrr", "rrf". Итого: G содержит "", "r", "f", "rr", а очередь Q — "rf", "fr", "ff", "rrr", "rrf".
Шаги 4), 5) проходят аналогично. По окончанию этих итераций множество G будет содержать строки "", "r", "f", "rr", "rf", "fr", а очередь Q — "ff", "rrr", "rrf", "rfr", "rff", "frr", "frf".
6) Из Q достаётся строка "ff". Это строка эквивалентна пустой строке "", и поэтому она отбрасывается.
7) Из Q достаётся строка "rrr". Это строка так же эквивалентна пустой строке "", и она тоже отбрасывается. В результате этих двух шагов множество G не изменилось, а очередь Q потеряло первые два элемента, не получив новых, и теперь содержит только строки "rrf", "rfr", "rff", "frr", "frf".

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

8:  "rrf"            (6)
9:  "rfr"            (7)
10: "rff" = "r"
11: "frr"            (8)
12: "frf"            (9)
13: "rrfr"          (10)
14: "rrff" = "rr"
15: "rfrr"          (11)
16: "rfrf" = "frr"
17: "frrr" = "f"
18: "frrf" = "rfr"
19: "frfr" = "rrf"
20: "frff" = "fr"
21: "rrfrr" = "frf"
22: "rrfrf" = "rfrr"
23: "rfrrr" = "rf"
24: "rfrrf" = "rrfr"

В итоге получаем 12 элементов, как на картинке. Кроме всего прочего, этот алгоритм решает задачу о представлении каждого элемента в виде строки наименьшей длины.

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

"rrr"   -> ""
"ff"    -> ""
"rfrf"  -> "frr"
"frfr"  -> "rrf"
"rrfrr" -> "frf"
"frrf"  -> "rfr"

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

Тут, правда, есть тонкий момент. Редуцирующее соотношение может оказаться не укорачивающим (не и не удлиняющим!), так как заменяемая и заменяющая строки будут иметь одинаковое количество символов. Над этим мне пришлось знатно поломать голову. Решение оказалось до смешного простым: такое соотношение надо использовать как и любое другое, но только лишь в одну строну. Это можно объяснить следующим образом. Описанный выше алгоритм фактически является процедурой построения дерева элементов группы. Когда один элемент оказывается равным другому (в другом строковом представлении), соответствующие этим представлениям вершины дерева и вырастающие из них ветви сливаются воедино. Если эквивалентность связана с укорочением представляющей элемент строки, то он сливается с элементов на одном из предыдущих слоёв, более близких к корню дерева — единичному элементу I. Поскольку из того элемента уже выросла ветвь (дерево строится слой за слоем), то этот элемент надо отбросить. Если же укорочения строки не происходит, то это означает, что сливающиеся элементы находятся в одном слое, а ветвь должна расти только из одного из них.

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

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

Для примера, разобранного выше, результат будет иметь такой вид:

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

Correct table.

Пример программы на Java, реализующий описанный выше алгоритм вот:

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

import java.util.*;

public class Study_Group_Generation_3 {
        
        private static final char[] letters = {'r', 'f'};
        private static final String[] targetStrings = {"rrr", "ff", "rfrf", "frfr", "frrf", "rrfrr"};
        private static final String[] replacements =  {"",    "",   "frr",  "rrf",  "rfr",  "frf"};
//      private static final char[] letters = {'s', 't'};
//      private static final String[] targetStrings = {"sss", "tts", "stss", "sstt", "ssts", "ststt", "tstst", "tsttt", "stttt", "tttttt"};
//      private static final String[] replacements =  {"",    "st",  "tt",   "tss",  "tttt", "tsts",  "ss",    "s",     "ts",    "ststs"};
//      private static final char[] letters = {'q', 'p'};
//      private static final String[] targetStrings = {"qq", "ppqpp", "ppp", "pqpq", "qppqp", "qpqppq"};
//      private static final String[] replacements =  {"",   "q",     "qpq", "qpqp", "pqppq", "ppqp"};
//      private static final String[] targetStrings = {"qq", "ppqpp", "ppp", "pqpq", "qppqp", "qpqppq"};
//      private static final String[] replacements =  {"",   "q",     "qpq", "qpqp", "pqppq", "ppqp"};
        
        private static List<String> elementsNames = new ArrayList<>();
        private static Queue<String> queue = new ArrayDeque<>();
        private static int groupOrder;
        private static int[][] multiplicationTable;
        
        public static void main(String[] args) {
                int k, l, m, maxLength;
                String currentName, newName, whiteString;
                boolean flag;
                boolean[] checkFlags;
                currentName = "";
                k = 0;
                maxLength = 0;
                while (null != currentName && 100 > k) {
                        flag = true;
                        for (m = 0; targetStrings.length > m; ++m) {
                                if (currentName.endsWith(targetStrings[m])) {
                                        flag = false;
                                        break;
                                }
                        }
                        if (flag) {
                                System.out.println(String.format("%6d: \"%s\"", k, currentName));
                                elementsNames.add(currentName);
                                if (maxLength < currentName.length()) {
                                        maxLength = currentName.length();
                                }
                                ++k;
                                for (l = 0; letters.length > l; ++l) {
                                        newName = currentName + letters[l];
                                        queue.add(newName);
                                }
                        } else {
                                l = currentName.length() - targetStrings[m].length();
                                System.out.println(String.format("     -  \"%s\" = \"%s%s\"",
                                                currentName, currentName.substring(0, l), replacements[m]));
                        }
                        currentName = queue.poll();
                }
                System.out.println();
                whiteString = new String(new char[maxLength]).replace('\0', ' ');
                groupOrder = elementsNames.size();
                multiplicationTable = new int[groupOrder][groupOrder];
                for (k = 0; groupOrder > k; ++k) {
                        currentName = elementsNames.get(k);
                        System.out.print(String.format("\"%s\"%s",
                                        currentName, whiteString.substring(currentName.length())));
                        for (l = 0; groupOrder > l; ++l) {
                                newName = currentName + elementsNames.get(l);
                                flag = true;
                                while (flag) {
                                        flag = false;
                                        for (m = 0; targetStrings.length > m; ++m) {
                                                if (newName.contains(targetStrings[m])) {
                                                        newName = newName.replace(targetStrings[m], replacements[m]);
                                                        flag = true;
                                                        break;
                                                }
                                        }
                                }
                                flag = true;
                                for (m = 0; groupOrder > m; ++m) {
                                        if (0 == elementsNames.get(m).compareTo(newName)) {
                                                multiplicationTable[k][l] = m;
                                                flag = false;
                                                break;
                                        }
                                }
                                if (flag) {
                                        multiplicationTable[k][l] = -1;
                                }
                                System.out.print(String.format("%4d", multiplicationTable[k][l]));
                        }
                        System.out.println();
                }
                flag = true;
                for (k = 0; groupOrder > k; ++k) {
                        checkFlags = new boolean[groupOrder];
                        for (l = 0; groupOrder > l; ++l) {
                                m = multiplicationTable[k][l];
                                if (-1 == m) {
                                        flag = false;
                                } else {
                                        if (checkFlags[m]) {
                                                flag = false;
                                        }
                                        checkFlags[m] = true;
                                }
                        }
                }
                if (flag) {
                        System.out.println();
                        System.out.println("Correct table.");
                }
        }
}
 

Я погонял его для нескольких известных мне групп. Результаты работы удовлетворительные.

[Munin]

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

[B@R5uk]

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

[Munin]

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

Она имеет какое-то отношение к решаемой мной задаче?

Имеет.

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

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

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

[B@R5uk]

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

Имеет.

Спасибо. Это интересный взгляд на те же вещи под новым углом. Я правда не все термины понимаю, но тем не менее.

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

и все задачи кажутся вам лёгкими

Я бы так не сказал. С построением редуцирующих соотношений ещё есть проблемы.

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

и когда вас предупреждают, что что-то реально сложно, это на самом деле реально сложно.

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

[mihaild]

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

для этого используются следующие редуцирующие соотношения, являющиеся следствием групповых соотношений для группы $A_4$

Как вы выбираете, какие именно следствия брать?
Допустим у вас есть такое представление: $\langle \{a, b\} | \{a^2 = a, ab = a\}\rangle$ (задаваемая им группа известна как "тривиальная группа"). Если я правильно понимаю, то ваш алгоритм в какой-то момент возьмет в $G$ строки "", "a", и потом попробует добавить строку $b$. Какие конкретно построения покажут что $a = b$?

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

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

-- 20.02.2020, 12:49 --

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

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

Т.е. можно, но это займет много времени.

[B@R5uk]

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

Допустим у вас есть такое представление: $\langle \{a, b\} | \{a^2 = a, ab = a\}\rangle$

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

-- 20.02.2020, 13:40 --

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

...то мы смогли бы из этого изготовить алгоритм, распознающий тривиальную группу.

Тривиальная группа является конечной группой, поэтому не вижу проблем её опознать.

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

Т.е. можно, но это займет много времени.

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

-- 20.02.2020, 13:47 --

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

Как вы выбираете, какие именно следствия брать?

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

[mihaild]

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

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

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

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

Тривиальная группа является конечной группой, поэтому не вижу проблем её опознать

Точное утверждение такое: не существует алгоритма, который по представлению тривиальной группы говорит "да" за время $10^{10^\text{размер представления}}$, и не говорит "да" ни для какого представления, не задающего тривиальную группу.

[B@R5uk]

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

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

Потому что это другая половина кода, фактически другая программа, которую я ещё не опубликовал.

[Munin]

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

[mihaild]

$\mathbb Z_{2^n}$ можно задать $n + 1$ соотношениями размера $O(\log n)$: $x_0 + x_0 = x_1$, $x_1 + x_1 = x_2$, ..., $x_{n - 1} + x_{n - 1} = x_n$, $x_n + x_n = x_n$. Я сильно подозреваю что можно получить гораздо большую скорость роста порядка группы от размера порождающих соотношений, но ни найти ни придумать пример пока не могу.