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

[Munin]

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

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

Ваша

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

- это ровно абелева и есть ($\mathbb{Z}_8\times\mathbb{Z}_2$). Неужели некрасивая? Ну ладно, что ж. Зато просто устроенная.

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

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

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

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

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

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

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

Хотя это уже не теория групп :-)

И вообще, то, чем вы занимаетесь (графы групп) - это уже геометрическая теория групп.
См.

Геометрическая теория групп | Андрей Малютин (СПбГУ, 2018, 15 лекций)
https://www.lektorium.tv/node/32971
https://www.youtube.com/playlist?list=PL-_cKNuVAYAWJ1jC1JmdqWBBKFe0AeWQ0

хотя это для вашего текущего уровня, может быть, сложновато.

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

Эта группа забавна тем, что она в каком-то смысле является "расщеплением" диэдральной группы $D_5$

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

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

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

И тот и другой вариант в теории групп есть и используется, если я правильно понимаю.

[mihaild]

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

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

Не гарантирует. Возьмем $S_4$ - в ней ваш алгоритм выберет например цикл $(1234)$, потом цикл $(1324)$, потом еще что-то (т.к. пока были только четные элементы) - итого минимум 3 элемента. При этом $S_4$ порождается двумя (циклом длины $4$ и транспозицией).
Насколько я помню (сейчас найти не могу), лучший (на какой-то момент) из известных алгоритмов для поиска минимального порождающего множества по таблице умножения работал за что-то вроде $O(n^{\log n})$. И оно просто перебирал все кандидаты в порождающие подмножества, пользуясь тем, что минимальное порождающее множество не может быть слишком большим.

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

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

Чуть сильнее: все конечнопорожденные.

[B@R5uk]

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

Возможно даже, можно так умножить $D_5$ на $\mathbb{Z}_2$, чтобы в результате получилась эта группа 20-го порядка.

Нельзя такого сделать. Потому что НОД порядков групп не равен единице. Тот случай, когда группу нельзя получить из её подгруппы групповым произведением.

[B@R5uk]

Есть такая простая на вид задача, которая ставит меня в тупик:

Цитата:

Пусть G — группа и f — отображение, ставящее в соответствие каждому элементу группы его квадрат. Таким образом, $f:\,\,x\to x^2$. Будет ли это отображение изоморфизмом?

Требования изоморфизма заключаются в двух пунктах:
1) $\forall a,b:\,\,f\left(ab\right)=f\left(a\right)f\left(b\right)$;
2) $f\left(a\right)=f\left(b\right)\Leftrightarrow a=b$.
И, вообще говоря, определённое в задаче отображение нарушает оба пункта: первый — для не абелевых групп, когда $ab\ne ba$ и, следовательно, $f\left(ab\right)=abab\ne aabb=f\left(a\right)f\left(b\right)$, а второй — для групп, в которых $\exists a\ne I:\,\,a^2=I$. Тем не менее, существуют группы, в которых это отображение будет изоморфизмом. Например, $C_3$ и вообще любая абелева группа, в которой $a^2=I\Leftrightarrow a=I$.

Так как правильно ответить на вопрос задачи: да или нет?

[Munin]

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

[B@R5uk]

То есть ответ "нет", а в качестве доказательства — пример любой группы, где нарушается хотя бы одно требование? Нарушение первого требования в не абелевой группе показать проще всего. Хотя, первое, что мне пришло на ум, это именно $a^2=I$.

-- 10.02.2020, 13:35 --

Не, всё-таки контрпример, $C_2$ будет проще.

-- 10.02.2020, 13:37 --

Munin, спасибо. Думаю, у меня в голове прояснилось. Можно читать дальше.

[mihaild]

Я бы ответил "в общем случае не будет" с любым примером. Но формулировка мне кажется сильно неудачной (ничего не стоило написать "для всех ли групп будет изоморфизмом").

[B@R5uk]

Прочитал про группу тетраэдра $A_4$. Понял, что группы могут быть устроены значительно сложнее, чем мне показалось поначалу. Граф группы:



Видно, что как ни крути и в какие степени не возводи, поменять местами элементы $r$ и $f$ в произведении $fr$ не получится. Всё из-за соотношения $frfrfr=I$. Это приводит к тому, что элементы группы нельзя представить в универсальном виде $r^nf^m$, как это можно сделать, например, в любой диэдральной группе. Или в группе, получаемой косым произведением любого количества циклических групп.

Теперь я для себя имею такую классификацию групп по степени "запущенности":
1) абелевы группы, где любые два элемента коммутируют: $ab=ba$
2) неабелевы "слоистые" группы, где любые две образующие коммутируют со степенью: $ab=ba^k$ (что происходит с произвольными двумя элементами ещё не проверял). В таких группах любой элемент можно представить как упорядоченное произведение образующих в нужных степенях:

$$b=\prod\limits_{k}{g_k^{\alpha\left(b,k\right)}}$$

Слоистыми такие группы являются потому, что их можно разбить на слои, соответствующие одной или нескольким образующим. Умножение на эти внутренние образующие не выводит из слоя. А умножение на другие образующие переводит весь слой в какой-нибудь другой слой, так как они все одинакового размера. В группе тетраэдра $A_4$ такого нет.
3) все остальные группы.

-- 18.02.2020, 14:32 --

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

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

То есть, вот, например, есть группа 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).

Теперь я понимаю, почему при построении группы по системе образующих с определяющими соотношениями используется такой, на первый взгляд, мутный алгоритм:
1) строим все возможные произведения (строки произвольной длины) из образующих и их обратных (в случае конечных групп можно не брать обратные, но заранее не угадаешь);
2) с помощью соотношений между образующими строим классы эквивалентности строк (путём замены/удаления подстрок), которые и называем элементами группы.
Всё из-за отсутствия "слабой" коммутативности образующих со степенью: $ab=ba^k$.

В связи с этим в моём алгоритме пункт 3), цель которого построить по заданному элементу $q_k$ и подгруппе $H_k$ новую расширенную подгруппу, надо поправить следующим образом. Надо рассматривать последовательность множеств $H_k,\;H_kC^k,\;H_kC^kH_k,\;H_kC^kH_kC^k$ и так далее до тех пор, пока элементы этих множеств будут давать какие-нибудь новые, ещё не рассмотренные элементы. Объединение всех этих элементов и будет новой, расширенной подгруппой $H_{k+1}$.

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

[Someone]

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

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

Ситуация ещё хуже: это вообще не алгоритм. http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tm&paperid=1180&option_lang=rus.

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

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

Забудьте.

[B@R5uk]

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

Ситуация ещё хуже: это вообще не алгоритм.

Вот те раз! Если есть готовая таблица умножения, то чем же не алгоритм?

[Someone]

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

Если есть готовая таблица умножения

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

[B@R5uk]

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

Если задана с самого начала для всех элементов группы, то задачи никакой нет.

Ну, если есть решение, то есть и вопрос, на который оно отвечает.

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

[mihaild]

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

И да, для упрощения себе жизни я потребовал задание группы в виде таблицы умножения

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

Если группа задана таблицей умножения, то можно найти минимальное по размеру порождающее множество перебором - оно не может быть больше чем $O(\log n)$ по размеру (хотя это конечно не полиномиальное время; я не знаю, известны ли полиномиальные алгоритмы для этой задачи).

[B@R5uk]

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

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

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

[ИСН]

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