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

[B@R5uk]

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

Хотел просто оставить его здесь и дожидаться помощи (так как не знаю другого способа найти ответ, кроме как брать различные группы и проверять в лоб), но открыл листинг программы, представленной ранее, и наткнулся на искомый пример. В листинге есть редуцирующие соотношения, которые являются исходными данными этой программы для построения группы $C_8\rtimes C_2$ с задающими соотношениями $p^8=q^2=I,\;qp=p^3q$. Эти редуцирующие соотношения имеют вид:

$$\begin{align*}qq&\to I\\ppqpp&\to q\\ppp&\to qpq\\pqpq&\to qpqp\\qppqp&\to pqppq\\qpqppq&\to ppqp\\ \end{align*}$$

Из них видно, что $pqpq=qpqp=pppp$, то есть ответ на мой вопрос положительный. Однако, из-за наличия соотношения $ppp=qpq$ на этапе построения дерева элементов группы не дойдёт до того, чтобы три или более элементов одного яруса дерева редуцировались в пользу только одного элемента. То есть мой вопрос нуждается в уточнении.

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

[mihaild]

Не очень понятен вопрос. Может ли оказаться так, что три слова $a$, $b$, $c$ различны и их нельзя привести к более коротким, при этом $ax = by = cz$ и их тоже нельзя привести к более коротким? Да, даже в абелевом случае.

[B@R5uk]

Может ли оказаться так, что слова $A_k,\;k=\overline{1,N},\;N\ge 3$ не приводимы к более коротким, имеют одну и ту же длину, различны в смысле равенства строк при этом $A_k=A_l,\;k\ne l$ в смысле равенства элементов, но для этих $A_k$ и $A_l$ не существует таких разбиений на подстроки $A_k=B_kC_k$ и $A_l=D_lE_l$ (в смысле равенства строк), что $B_k=D_l$ (в смысле равенства элементов), но $B_k\ne D_l$ (в смысле равенства строк). При этом длина строк $B_k$ и $D_l$ может быть различна.

Поскольку у меня всего две образующие, то абелевы группы отпадают сразу. Среди всего набора строк $A_k$ можно указать только две строки, отличающиеся последним символом. Те же пары строк, что имеют общий последний символ, после его отбрасывания сразу дают строки $B_k$ и $D_l$, которых не должно существовать. Эти стоки различны смысле равенства строк, но равны в смысле равенства элементов, так как группа абелева. Впрочем, даже абелевость не нужна, строки $B_k$ и $D_l$ будут равны, так как получены тождественным преобразованием из равных строк $A_k$ и $A_l$.

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

[B@R5uk]

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

[mihaild]

Вы про условия вида $xy = z$ в задании группы представлением? Так и называются - relations (https://en.wikipedia.org/wiki/Presentation_of_a_group).

[vpb]

B@R5uk
1) Поинтересуйтесь тем, что такое алгоритм Тодда-Кокстера перечисления смежных классов. См. книжку Каргаполова-Мерзлякова, глава 5, параграф 14.

2) Слова над данным алфавитом, при одной длине, упорядочиваются, внезапно, лексикографически. Это упорядочение обладает свойством, что если $x\prec y$, то $xz\prec yz$ и $zx\prec zy$.

3) Рекомендуется скачать с либгену В.Н.Латышев, Комбинаторная теория колец. Стандартные базисы. Там есть параграф 3, "Схема слияния и канонический вид символьных выражений".

[B@R5uk]

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

Так и называются - relations

Спасибо.

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

См. книжку Каргаполова-Мерзлякова, глава 5, параграф 14.

Вы имеете в виду "Основы теории групп"? Посмотрел начало главы: там всё очень сухо и малопонятно (кроме описания свободной группы). Либо надо читать сначала, либо нужно больше предварительных знаний. Упоминаний алгоритма не нашёл. У меня 3-е издание, если что.

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

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

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

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

Остался только пункт 1), с которым куча проблем. Но у меня, вроде, что-то более-менее хорошее получилось. О чём я сейчас и попытаюсь рассказать.

[B@R5uk]

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

...ну и еще хорошо бы сказать, какие свойства от них нужны.

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

Если некоторый элемент $g\in G$, представимый строкой из символов $S_g$ допускает представление в виде другой, более короткой строки $S'_g$, то должно существовать соотношение $T=R$, где строки $T$ и $R$ различны, несократимы (начинаются разными символами и заканчиваются разными), имеют разную длину ($R$ короче, чем $T$) и строка $T$ является подстрокой строки $S_g$, позволяя, таким образом, эту строку $S_g$ укоротить (редуцировать). При этом подстановка строки $R$ вместо $T$ в строке $S_g$ не обязательно должно давать строку $S'_g$. Эта поблажка нужна чтобы не плодить редуцирующие правила до бесконечности, а обходиться некоторым компактным (но полным!) множеством. При этом, разумеется, тождество $T=R$ является следствием групповых соотношений.

Все возможные соотношения $T_k=R_k$ должны удовлетворять условию полноты. Чтобы определиться что это значит сначала надо договориться как именно эти соотношения будут применяться. Договорённость такая. Соотношения применяются лишь одним способом: в строке $S$ ищется подстрока $T_k$ и заменяется на $R_k$. Эту договорённость можно символически обозначать стрелкой: $T_k\to R_k$. Полнота множества редуцирующих соотношений означает, что с последовательным применением этих правил (не важно в каком порядке) любую строку $S_g$ элемента $g$ можно привести к строке $\Sigma_g$ минимально возможной для элемента $g$ длины.

Так же можно потребовать минимальности самих соотношений $T_k=R_k$. То есть чтобы ни $T_k$, ни $R_k$ нельзя было сократить с помощью какого-либо другого правила $T_l\to R_l$. В принципе, это будет следовать из требования минимальности множества $\left\{T_k\to R_k\right\}$. В самом деле, если мы можем редуцировать тождество $T_k=R_k$, то мы получим правило $T'_k\to R'_k$ (возможно, поменяв местами правую и левую часть — в зависимости от того, какая строка короче), в которой длина строки $T'_k$ будет короче, чем $T_k$. По этой причине вновь полученное правило будет более общо, и, возможно, упразднит одно или несколько правил в множестве редуцирующих соотношений.

Редуцирующие правила, удовлетворяющие требованиям выше, позволяют с легкостью строить множество элементов группы в виде дерева элементов. Если мы строим дерево ярус за ярусом, то встречая строку, суффикс которой (или она сама целиком) является левой частью какого-либо редуцирующего соотношения $T_k\to R_k$, то, очевидно, этот элемент уже был представлен в виде более короткой строки на одном из предыдущих ярусов дерева. Поэтому текущую строку и соответствующую ей вершину дерева надо отбросить вместе со всеми ветвями, что из неё растут.

Проблемы возникают, когда редуцирующее правило $T_k\to R_k$ оказывается не совсем редуцирующим: длина строк $T_k$ и $R_k$ одинакова. Такие "ущербные" правила тем не менее нужны в силу требования полноты множества редуцирующих соотношений. Так же необходимость в них можно проследить из способа построения группы с помощью дерева элементов. Если элемент $g$ допускает представление в виде нескольких различных минимальных строк $\Sigma^l_g$, то вершины дерева, соответствующие этим строкам, встретятся на одном ярусе; при этом их все надо отбросить в пользу только одной их них. С этими равновеликими парами строк связаны ещё тонкости, но пока не будет о грустном.

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

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

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

3) Комбинация двух тождеств. Если имеется два тождества $AB=C$ и $BD=E$, то к первому можно дописать в конец строку $D$, ко второму — спереди $A$. В результате получится $ABD=CD=AE$ или просто $AE=CD$, то есть новое тождество. Тут важно заметить, что это действие не является коммутативным, то есть если удастся скомбинировать первую пару со второй, а так же вторую с первой, то результаты будут, как правило, разные. Исключение — когда тождество комбинируется само с собой. Ещё одно важное замечание — комбинацию тождеств иногда можно провести несколькими способами (для оного и того же порядка "слагаемых"), а иногда — ни одним. В любом случае, в моём алгоритме это действие — ключевой способ порождения новых редуцирующих соотношений.

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

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

Итак, сам алгоритм. В качестве затравки используются групповые соотношения, так как они сами являются редуцирующими правилами, пускай, возможно, и не оптимальными. Мы их помещаем в очередь. Каждая итерация алгоритма достаёт из очереди (типа FIFO) элемент и упрощает его с помощью действий 1) и 2) до победного (для данной итерации) конца. Тут возможно два варианта: либо мы получили тривиальное соотношение, что означает, что надо перейти к следующей итерации, либо результатом стало новое редуцирующее правило. В последнем случае это правило добавляется в множество редуцирующих соотношений. Затем с помощью действия 3) вновь найденное тождество комбинируется во всех порядках со всеми соотношениями множества (в том числе с самим собой). Результаты комбинации (коих может быть несколько для каждой пары или вообще ни одного) добавляются в очередь. Итерации продолжаются пока очередь не опустеет, либо пока не будет превышен один из пределов по размеру множества соотношений или по длине строк в редуцирующих правилах.

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

Рассмотрим наглядный пример. Группа диэдра $D_4$ имеет следующие соотношения: $rrrr\to I,\;ff\to I,\;rfrf\to I$. Комбинация первого и второго ничего не даст, а вот комбинация третьего с первым и вторым дают, соответственно, $rrr\to frf,\;rfr\to f$. Эти две пары упраздняют первое и третье соотношения. В результате имеем: $ff\to I,\;rrr\to frf,\;rfr\to f$. Комбинируя последние два получаем: $frffr\to rrf$, а после редукции с помощью первого соотношения — $frr\to rrf$. Результирующее множество редуцирующих правил — $\left\{ff\to I,\;rfr\to f,\;rrr\to frf,\;frr\to rrf\right\}$ — является полным.

Код программы, который реализует все вышеописанные операции со строками и даже иногда выдаёт что-то вразумительное:
... а вот не влез он в лимит 20000 символов на сообщение. Опубликую позже.

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

(Оффтоп)

Что-то сильно я мыслию по древу растёкся, да серым волком по земле...

[B@R5uk]

Код программы, который реализует все вышеописанные операции со строками и даже иногда выдаёт что-то вразумительное:

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

import java.util.*;

public class Study_Group_Generation_4 {
        
        private static final boolean displayFlag = true;
//      private static final boolean displayFlag = false;
        
        private static final int lengthLimit = 100;
        private static final int numberLimit = 20;
        
//      private static final String[] stringPairs = {"sss", "", "tts", "st"};
//      private static final String[] stringPairs = {"rrr", "", "ff", "", "rfrf", ""};
        private static final String[] stringPairs = {"rrrr", "", "ff", "", "rfrf", ""};
//      private static final String[] stringPairs = {"rrrr", "", "ff", "", "rfr", "f"};
//      private static final String[] stringPairs = {"rrr", "", "ff", "", "rfrfrf", ""};
//      private static final String[] stringPairs = {"pppppppp", "", "qq", "", "pppq", "qp"};
//      private static final String[] stringPairs = {"pppppppp", "", "qq", "", "pppqp", "q"};
//      private static final String[] stringPairs = {"pppppppp", "", "qq", "", "pppppq", "qp"};
//      private static final String[] stringPairs = {"ppppp", "", "qqqq", "", "ppq", "qp"};
//      private static final String[] stringPairs = {"bbbb", "", "cc", "", "bcbcbc", ""};
//      private static final String[] stringPairs = {"bbbbb", "", "ccc", "", "bcbcbc", ""};
        
        private static StringReductionSet reductionTool = new StringReductionSet();
        private static Queue<StringPair> queue = new LinkedList<>();
        private static Set<StringPair> queueSet = new TreeSet<>();
        
        public static void main(String[] args) {
                int k;
                StringPair currentPair, tempPair;
                Set<StringPair> newPairs;
                Iterator<StringPair> iterator;
                
                System.out.println("========================");
                System.out.println("Starting relations:");
                System.out.println("------------------------");
                for (k = 0; stringPairs.length - 1 > k; k += 2) {
                        System.out.println(String.format("\"%s\" = \"%s\"", stringPairs[k], stringPairs[k + 1]));
                }
                System.out.println("========================");
                System.out.println();
                
                for (k = 0; stringPairs.length - 1 > k; k += 2) {
                        currentPair = new StringPair(stringPairs[k], stringPairs[k + 1]);
                        reductionTool.add(currentPair);
                        if (displayFlag) {
                                System.out.println(currentPair.toString());
                        }
                        newPairs = reductionTool.combine(currentPair);
                        iterator = newPairs.iterator();
                        while (iterator.hasNext()) {
                                tempPair = iterator.next();
                                if (queueSet.add(tempPair)) {
                                        queue.add(tempPair);
                                        if (displayFlag) {
                                                System.out.println("    ... " + tempPair.toString());
                                        }
                                }
                        }
                }
                if (displayFlag) {
                        System.out.println();
                }
                
                while (!queue.isEmpty()) {
                        currentPair = queue.poll();
                        queueSet.remove(currentPair);
                        if (displayFlag) {
                                System.out.println(currentPair.toString());
                        }
                        if (currentPair.getLeft().equals("rrrf")) {
                                System.out.println();
                        }
                        reductionTool.reduce(currentPair);
                        if (displayFlag) {
                                System.out.println(currentPair.toString());
                        }
                        if (!currentPair.isTrivial()) {
                                if (lengthLimit < currentPair.getLeft().length()) {
                                        System.out.println("String length limit exceeded.");
                                        break;
                                }
                                if (numberLimit < reductionTool.getPairsNumber()) {
                                        System.out.println("String length limit exceeded.");
                                        break;
                                }
                                //reductionTool.add(tempPair);
                                newPairs = reductionTool.combine(currentPair);
                                newPairs.addAll(currentPair.combineWith(currentPair));
                                iterator = newPairs.iterator();
                                while (iterator.hasNext()) {
                                        tempPair = iterator.next();
                                        if (queueSet.add(tempPair)) {
                                                queue.add(tempPair);
                                                if (displayFlag) {
                                                        System.out.println("    ... " + tempPair.toString());
                                                }
                                        }
                                }
                                newPairs = reductionTool.addExclusionary(currentPair);
                                iterator = newPairs.iterator();
                                while (iterator.hasNext()) {
                                        tempPair = iterator.next();
                                        if (queueSet.add(tempPair)) {
                                                queue.add(tempPair);
                                                if (displayFlag) {
                                                        System.out.println("    === " + tempPair.toString());
                                                }
                                        }
                                }
                        }
                        if (displayFlag) {
                                System.out.println();
                        }
                }
                
                System.out.println("================================");
                System.out.println("Reduction laws:");
                System.out.println("--------------------------------");
                reductionTool.display();
                System.out.println("--------------------------------");
                reductionTool.displayAsArray();
                System.out.println("================================");
        }
}

class StringReductionSet {
        
        private List<StringPair> reductionPairs, equivalencePairs;
        
        public StringReductionSet() {
                reductionPairs = new LinkedList<>();
                equivalencePairs = new LinkedList<>();
        }
        
        public int getPairsNumber() {
                return reductionPairs.size() + equivalencePairs.size();
        }

        public void add(StringPair arg) {
                if (!arg.isTrivial()) {
                        if (arg.isReciprocal()) {
                                equivalencePairs.add(arg);
                        } else {
                                reductionPairs.add(arg);
                        }
                }
        }
        
        public Set<StringPair> addExclusionary(StringPair arg) {
                Iterator<StringPair> iterator;
                StringPair tempPair;
                Set<StringPair> result = new TreeSet<>();
                if (!arg.isTrivial()) {
                        iterator = reductionPairs.iterator();
                        while (iterator.hasNext()) {
                                tempPair = iterator.next();
                                if (tempPair.isIncluded(arg)) {
                                        iterator.remove();
                                        result.add(tempPair);
                                }
                        }
                        iterator = equivalencePairs.iterator();
                        while (iterator.hasNext()) {
                                tempPair = iterator.next();
                                if (tempPair.isIncluded(arg)) {
                                        iterator.remove();
                                        result.add(tempPair);
                                }
                        }
                        if (arg.isReciprocal()) {
                                equivalencePairs.add(arg);
                        } else {
                                reductionPairs.add(arg);
                        }
                }
                return result;
        }
        
        public void reduce(StringPair arg) {
                Iterator<StringPair> iterator1, iterator2;
                StringPair equivalencePair;
                boolean breakFlag, loopFlag;
                iterator1 = equivalencePairs.iterator();
                if (iterator1.hasNext()) {
                        equivalencePair = iterator1.next();
                } else {
                        equivalencePair = null;
                }
                breakFlag = false;
                outerloop:
                while (true) {
                        loopFlag = true;
                        while (loopFlag) {
                                loopFlag = false;
                                iterator2 = reductionPairs.iterator();
                                while (iterator2.hasNext()) {
                                        if (arg.reduceWith(iterator2.next())) {
                                                loopFlag = true;
                                                breakFlag = false;
                                        }
                                }
                        }
                        if (null == equivalencePair) {
                                break;
                        }
                        while (true) {
                                if (arg.reduceWith(equivalencePair)) {
                                        break;
                                }
                                if (iterator1.hasNext()) {
                                        equivalencePair = iterator1.next();
                                } else {
                                        if (breakFlag) {
                                                break outerloop;
                                        } else {
                                                breakFlag = true;
                                                iterator1 = equivalencePairs.iterator();
                                        }
                                }
                        }
                }
        }
        
        public Set<StringPair> combine(StringPair arg) {
                Iterator<StringPair> iterator;
                Set<StringPair> result = new TreeSet<>();
                iterator = reductionPairs.iterator();
                while (iterator.hasNext()) {
                        result.addAll(arg.combineWith(iterator.next()));
                }
                iterator = equivalencePairs.iterator();
                while (iterator.hasNext()) {
                        result.addAll(arg.combineWith(iterator.next()));
                }
                return result;
        }
        
        public void display() {
                reductionPairs.forEach((w) -> System.out.println(w.toString()));
                equivalencePairs.forEach((w) -> System.out.println(w.toString()));
        }
        
        public void displayAsArray() {
                StringBuilder result = new StringBuilder();
                reductionPairs.forEach((w) -> {
                        result.append(", ");
                        result.append(w.toArrayString());
                });
                equivalencePairs.forEach((w) -> {
                        result.append(", ");
                        result.append(w.toArrayString());
                });
                result.delete(0, 1);
                result.setCharAt(0, '{');
                result.append("};");
                System.out.println(result);
        }
}

class StringPair implements Comparable<StringPair> {
        
        private String left, right;
        
        public StringPair(String arg1, String arg2) {
                if (arg1.length() < arg2.length()) {
                        left = arg2;
                        right = arg1;
                } else {
                        left = arg1;
                        right = arg2;
                }
                reduce();
        }
        
        public StringPair(StringPair arg) {
                left = arg.left;
                right = arg.right;
        }
        
        public String getLeft() {
                return left;
        }
        
        public String getRight() {
                return right;
        }
        
        public boolean isTrivial() {
                return 0 == left.length() && 0 == right.length();
        }
        
        public boolean isReciprocal() {
                return left.length() == right.length();
        }
        
        public boolean isIncluded(StringPair arg) {
                return left.contains(arg.left) || right.contains(arg.left);
        }
        
        public boolean equals(StringPair arg) {
                return left.equals(arg.left) && right.equals(arg.right);
        }
        
        public int compareTo(StringPair arg) {
                int result = left.compareTo(arg.left);
                if (0 != result) {
                        return result;
                }
                return right.compareTo(arg.right);
        }
        
        public String toString() {
                return String.format("\"%s\" -> \"%s\"", left, right);
        }
        
        public String toArrayString() {
                return String.format("{\"%s\", \"%s\"}", left, right);
        }
        
        public void reduce() {
                int k, l;
                k = 0;
                while (left.length() > k && right.length() > k) {
                        if (left.charAt(k) != right.charAt(k)) {
                                break;
                        }
                        ++k;
                }
                if (0 < k) {
                        left = left.substring(k);
                        right = right.substring(k);
                }
                k = left.length();
                l = right.length();
                while (0 < l) {
                        --k;
                        --l;
                        if (left.charAt(k) != right.charAt(l)) {
                                ++k;
                                ++l;
                                break;
                        }
                }
                if (left.length() > k) {
                        left = left.substring(0, k);
                        right = right.substring(0, l);
                }
        }
        
        public boolean reduceWith(StringPair arg) {
                String tempString;
                boolean flag = false;
                while (left.contains(arg.left)) {
                        left = left.replace(arg.left, arg.right);
                        flag = true;
                }
                while (right.contains(arg.left)) {
                        right = right.replace(arg.left, arg.right);
                        flag = true;
                }
                if (flag) {
                        if (left.length() < right.length()) {
                                tempString = left;
                                left = right;
                                right = tempString;
                        }
                        reduce();
                }
                return flag;
        }
        
        public Set<StringPair> combineWith(StringPair arg) {
                int k, limit, start;
                String A, B1, B2, C;
                StringPair newPair;
                Set<StringPair> result = new TreeSet<>();
                limit = Math.min(this.left.length(), arg.left.length());
                for (k = 1; limit > k; ++k) {
                        /*
                         *  arg: AB1 -> D
                         * this: B2C -> E
                         *   if B1 = B2 = B
                         * then  ABC -> DC
                         *       ABC -> AE
                         *  and  AE <-> DC
                         */
                        start = arg.left.length() - k;
                        B1 =  arg.left.substring(start);
                        B2 = this.left.substring(0, k);
                        if (B1.equals(B2)) {
                                A =  arg.left.substring(0, start);
                                C = this.left.substring(k);
                                newPair = new StringPair(A + this.right, arg.right + C);
                                if (!newPair.isTrivial()) {
                                        result.add(newPair);
                                }
                        }
                }
                if (!this.equals(arg)) {
                        for (k = 1; limit > k; ++k) {
                                /*
                                 * this: AB1 -> D
                                 *  arg: B2C -> E
                                 *   if B1 = B2 = B
                                 * then  ABC -> DC
                                 *       ABC -> AE
                                 *  and  AE <-> DC
                                 */
                                start = this.left.length() - k;
                                B1 = this.left.substring(start);
                                B2 =  arg.left.substring(0, k);
                                if (B1.equals(B2)) {
                                        A = this.left.substring(0, start);
                                        C =  arg.left.substring(k);
                                        newPair = new StringPair(A + arg.right, this.right + C);
                                        if (!newPair.isTrivial()) {
                                                result.add(newPair);
                                        }
                                }
                        }
                }
                return result;
        }
}
 

[B@R5uk]

Я правильно понимаю, что конечный порядок элементов группы ещё не гарантирует конечность самой группы? Например, в группе, задаваемой соотношениями $b^3=c^3=\left(bc\right)^3=I$, элемент $bcc$ будет иметь бесконечный порядок, поэтому и сама группа тоже будет бесконечной.

[Munin]

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

Я правильно понимаю, что конечный порядок элементов группы ещё не гарантирует конечность самой группы?

Порождающих элементов. Да.

-- 22.02.2020 16:33:08 --

Тьфу, образующих.

[B@R5uk]

А что можно сделать с табличкой умножения группы, чтобы найти какие-нибудь характерные её свойства? А то я вот я получил какую-то группу 60-го порядка, смотрю на эти 3600 чисел от 0 до 59, чешу репу и думаю: "А что же дальше?" Проверить корректность таблицы — это, разумеется, первое что я делаю. Так же не представляет труда для каждого элемента найти его порядок и обратный ему элемент. Но этого как-то мало.

[Xaositect]

Какие свойства Вам нужны? Можно найти максимальные подгруппы, нормальные подгруппы, композиционный ряд. Или классы сопряженности, неприводимые представления и их характеры.

[Munin]

Ищите смежные классы и классы сопряжённости, потом подгруппы.

[mihaild]

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

Я правильно понимаю, что конечный порядок элементов группы ещё не гарантирует конечность самой группы?

В таком виде это очевидно: группа функций $\mathbb N \to \mathbb Z_2$ со сложением в качестве групповой операции. Надо еще потребовать конечной порожденности.

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

Порождающих элементов

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

А вот вопрос о том, существует ли бесконечная конечно порожденная конечно представленная группа, в которой все элементы имеют конечный порядок, открыт.

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