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

[mihaild]

arseniiv в сообщении #1437078 писал(а):

Не уверен, что нет теоремы, что для общего случая не существует алгоритма

Из теоремы Адяна-Рабина следует что проверка, является ли заданная порождающими соотношениями группа циклической, алгоритмически неразрешима. Об этом речь?

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

Я правильно понимаю, что может быть и меньше элементов?

Да - например в тривиальной (одноэлементной) группе все эти соотношения тоже выполнены.

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

То есть исходные уравнения определять группу неоднозначно?

Чтобы получить однозначность нужно потребовать максимальности этой группы.
Формально, пусть у нас есть набор генераторов и соотношений вида $x_1 x_2 \ldots x_n = e$. Возьмем свободную группу, порожденную нашими генераторами. Можно доказать, что в ней есть наименьшая по включению нормальная подгруппа, содержащая все левые части порождающих соотношений. Тогда группой, заданной данными соотношениями, называется фактор нашей свободной группы по этой наименьшей по включению.

[Munin]

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

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

Пока начните с того, что полупрямое произведение - обобщение прямого произведения.
В прямом произведении вы берёте по элементу из каждой группы $g,\in G,h\in H,$ и строите "прямоугольную табличку умножения". У вас получаются элементы $(g,h),$ которые можно понимать как $gh=hg.$ По сути, в новой группе все элементы старых групп - это образующие, а соотношения - это что любой $g$ коммутирует с любым $h.$
В полупрямом произведении начинается всё так же, но только нет коммутативности. И в "прямоугольной табличке умножения" каждая строка остаётся хорошим смежным классом, а вот столбцы "переплетаются".
В частности, ваша исходная группа есть $\mathbb{Z}_7\rtimes\mathbb{Z}_3$ или $\mathbb{Z}_3\rtimes\mathbb{Z}_7$ (разберитесь, какая именно).

Ещё гляньте объяснение в хорошем учебнике, типа Кострикина.

-- 27.01.2020 13:50:46 --

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

То есть исходные уравнения определять группу неоднозначно?

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

-- 27.01.2020 13:54:16 --

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

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

[mihaild]

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

Но так не принято: принято подразумевать, что других уравнений нет.

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

[B@R5uk]

Спасибо. Мне ещё читать и изучать как до Камчатки.

Пока на основе уравнений:

$$\begin{matrix}p^h=q^n=I,&qp=p^kq,&h>k,&h|k^n-1\\ \end{matrix}$$

$$\begin{matrix}\left(p^a q^b\right)\left(p^c q^d\right)=p^f q^g,&f=a+c k^b\left(\bmod\,h\right),&g=b+d\left(\bmod\,n\right)\\ \end{matrix}$$

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

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

class calc {
        static int modPower(int arg, int pow, int mod) {
                long a = arg, res = 1;
                a %= mod;
                while (0 < pow) {
                        if (0 != (pow & 1)) {
                                res = (res * a) % mod;
                        }
                        pow >>= 1;
                        a = (a * a) % mod;
                }
                return (int) res;
        }
}

public class Group_Check {
        public static void main(String[] args) {
                int k, pow1, pow2, pow3, size, ord, a, b, c, d;
                pow1 = 8;
                pow2 = 2;
                pow3 = 5;
                if (pow1 <= pow3) {
                        System.out.println("ERROR");
                        return;
                }
                if (1 != calc.modPower(pow3, pow2, pow1)) {
                        System.out.println("ERROR");
                        return;
                }
                System.out.println(String.format("Equations: p^%d = q^%d = I, qp = p^%d q", pow1, pow2, pow3));
                size = pow1 * pow2;
                System.out.println("Group size = " + size);
                for (k = 0; size > k; ++k) {
                        a = 0;
                        b = 0;
                        c = k % pow1;
                        d = k / pow1;
                        ord = 0;
                        do {
                                a = (c * calc.modPower(pow3, b, pow1) + a) % pow1;
                                b = (b + d) % pow2;
                                ++ord;
                                //System.out.println(String.format("%d -> {%d, %d}", ord, a, b));
                        } while (0 != a || 0 != b);
                        System.out.print(String.format("Order {%d, %d} = %d", c, d, ord));
                        if (size != ord) {
                                System.out.println();
                        } else {
                                System.out.println(" = size");
                        }
                }
        }
}
 

Группы всех приведённых графов, кроме абелевой группы порядка 10, проверку прошли.

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

В частности, ваша исходная группа есть $\mathbb{Z}_7\rtimes\mathbb{Z}_3$ или $\mathbb{Z}_3\rtimes\mathbb{Z}_7$ (разберитесь, какая именно).

Судя по формулам умножения элементов должно быть $\mathbb{Z}_7\rtimes\mathbb{Z}_3$, так как степени второй образующей просто суммируются по модулю 3.

[Munin]

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

Ещё гляньте объяснение в хорошем учебнике, типа Кострикина.

3-й том.

-- 27.01.2020 14:40:57 --

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

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

Но так не принято: принято подразумевать, что других уравнений нет.

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

Ну я в этих нюансах не разбираюсь, так что как скажете.

[arseniiv]

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

Из теоремы Адяна-Рабина следует что проверка, является ли заданная порождающими соотношениями группа циклической, алгоритмически неразрешима. Об этом речь?

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

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

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

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

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

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

Тут в каком-то смысле один множитель действует на другом, но при этом мы ещё и запоминаем, чем мы там надействовали, и потому берутся пары. Впрочем, нет, лучше почитайте свойства полупрямого произведения. Munin уже написал, но недостаточно: мало некоммутативности, важны ещё детали про действие. Кроме того свойство представимости элементов в виде произведений делает конструкцию прозрачной примерно как свойство представимости комплексного числа в виде $(a,0) + (0,1)(b,0)$, если его изначально задавали в виде тоже непонятных пар.

[vpb]

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

диэдрических групп.

Извиняюсь, диэдральных.

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

что есть более простое доказательство

Нет, нету.

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

без использования ММИ.

А что это такое ?

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

то мы всё так же получим группу?

Совершенно верно.

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

какое-нибудь специальное название?

Возможно (не уверен), что это называется квазидиэдральная.

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

не вырождаются в обычную циклическую 16-го порядка

Тогда бы $p$ и $q$ коммутировали.

-- 27.01.2020, 20:32 --

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

Мне ещё читать и изучать как до Камчатки.

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

-- 27.01.2020, 20:34 --

Я как-то постил список учебников по теории групп, сейчас попробую разыскать.

-- 27.01.2020, 20:45 --

Вот здесь.

[Munin]

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

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

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

За список учебников от меня большое спасибо!

[B@R5uk]

Ради полноты картины построил графы двух оставшихся групп порядка 16, получаемых косым произведением циклических групп $\mathbb{Z}_8\rtimes\mathbb{Z}_2$. И проверил их неприводимость к циклической группе $\mathbb{Z}_{16}$.



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

В связи с этим у меня есть подозрение, что прямое произведение двух циклических групп не вырождается в циклическую, если НОД порядков сомножителей больше единицы. И наоборот, если НОД порядков умножаемых циклических групп равен 1, то произведение вырождается в циклическую группу. Причём в последнем случае в качестве образующей новой группы можно взять произведение образующих умножаемых групп. Доказательство последнего факта довольно просто. Надо показать, что пара чисел $\{a\,\bmod\,b,\,a\,\bmod\,c\}$ пробегает все возможные комбинации остатков при $a=0,\,1,\,...\,bc-1$, если $\gcd(b,\,c)=1$. Это, кстати, имеет связь с китайской теоремой об остатках.

А вот с первым утверждением я без понятия что делать. Хотя численные эксперименты показывают его верность. Доказательство наверняка использует метод "от противного".

-- 28.01.2020, 01:51 --

vpb, спасибо. ММИ — метод математической индукции.

arseniiv в сообщении #1437160 писал(а):

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

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

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

$$\begin{matrix}p^h=q^n=I,&qp=p^kq,&h>k,&k^n=1\left(\bmod\,h\right)\\ \end{matrix}$$

$$\begin{matrix}\left(p^a q^b\right)\left(p^c q^d\right)=p^f q^g,&f=\left(a+c k^b\right)\bmod\,h,&g=\left(b+d\right)\bmod\,n\\ \end{matrix}$$

[mihaild]

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

А вот с первым утверждением я без понятия что делать.

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

[B@R5uk]

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

-- 28.01.2020, 02:21 --

Тут, однако, встаёт другой интересный вопрос. Численные эксперименты показывают, всегда найдётся элемент, порядок которого равен НОК образующих, причём, как правило, не один. И элемент, равный произведению образующих как раз таким является. Это, видимо, связано с периодом последовательности пар чисел $\{n\,\bmod\,b,\,n\,\bmod\,c\}$, который как раз равен $\operatorname{lcm}\left(b,\,c\right)$.

[mihaild]

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

найдётся элемент, порядок которого равен НОК образующих

Ну собственно пусть $a$ и $b$ - образующие, их порядки $x$ и $y$. Пусть $z$ - порядок $ab$. Тогда $a^z b^z = e$, т.е. $a^z = e$ и $b^z = e$.

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

причём как правило не один

А у циклической группы (кроме $\mathbb{Z}_2$) уже не один образующий.
Еще можете подумать, все ли элементы, порядок которых равен НОК, являются произведениями образующих.

[Munin]

B@R5uk
Обычно люди идут в другом порядке: сначала проходят случай абелевых групп конечного порядка - он полностью изучен и довольно прост. А потом уже занимаются неабелевыми группами. Соответственно, абелевы группы при прямом произведении дают абелеву группу, и сначала люди изучают прямое произведение, а потом полупрямое.

А вы как-то наоборот знакомитесь с этой областью.

[B@R5uk]

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

[B@R5uk]

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

В связи с этим я как раз нашёл на что надо умножить $\mathbb{Z}_5$, чтобы получился красивый граф. Это группа $\mathbb{Z}_4$. К сожалению, из-за её высокого 4-го порядка на картинке вместо пятиконечных звёздочек получается месиво из направленных отрезков. В этом плане $\mathbb{Z}_7\rtimes\mathbb{Z}_3$ из первого поста вне конкурентов. Но тем не менее:



Эта группа забавна тем, что она в каком-то смысле является "расщеплением" диэдральной группы $D_5$: образующая группы второго порядка f расщепляется в квадрат $f=q^2$ и появляется два новых уровня со своей арифметикой. Другими словами, диэдральная группа $D_5$ является подгруппой произведения $\mathbb{Z}_5\rtimes\mathbb{Z}_4$. Возможно даже, можно так умножить $D_5$ на $\mathbb{Z}_2$, чтобы в результате получилась эта группа 20-го порядка.

-- 28.01.2020, 05:28 --

arseniiv в сообщении #1437160 писал(а):

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

По-моему, если есть возможность построить таблицу умножения группы или хотя бы выписать все элементы группы, то можно двигаться не снизу вверх, а сверху вниз.

То есть, вот, например, есть группа G. Все её элементы известны, и мы знаем, как их друг на друга умножать. Тогда действуем по следующему плану.
1) Выбираем элемент группы с наибольшим рангом. Пусть это будет $q_0$. Этот элемент порождает в группе G некоторую циклическую подгруппу $C^0=H_1$ (Здесь верхний индекс у символа "C" означает порядковый номер, а не ранг группы). Если $C^0=G$, то наша задача выполнена. В противном случае полагаем $k=1$ и переходим к пункту 2).
2) Поскольку $H_k\ne G$, то в множестве $G\backslash H_k$ есть элементы. Опять возьмём элемент $q_k$ с наибольшим рангом.
3) Этот элемент опять порождает в группе G некоторую циклическую подгруппу $C^k$. Будем рассматривать все элементы $c^k_l$ этой подгруппы и все правые смежные классы $H_k\,c^k_l$. Эти классы не пересекаются, а их объединение даёт новую подгруппу $H_{k+1}$ в группе G.
4) Если $H_{k+1}=G$, то наша задача закончена. В противном случае полагаем $k\leftarrow k+1$ и переходим к пункту 2).

Поскольку после каждой итерации в множестве $G\backslash H_k$ остаётся всё меньше и меньше элементов, а G конечна, то алгоритм рано или поздно закончится. А выбор на каждом шаге элемента с наибольшим рангом гарантирует, что полученное построение будет с наименьшим возможным числом образующих. Ну, или, во всяком случае, таков план.