Проблема тождества слов в конечной группе.

[dgwuqtj]

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

можно ли вообще редуцировать длинные соотношения как-то более эффективно?

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

[B@R5uk]

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

vpb, спасибо за литературу. Осилить бы это всё. В один присест книжку не прочитать, а без какого-то регулярного стимула типа математического кружка, или семинара, или лекции заставить себя читать понемногу, но регулярно и вдумчиво — тяжело. Но всё равно спасибо за интерес и желание помочь.

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

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

Это уже какая-то другая задача, отличная от проблемы равенства слов?

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

Если да, то это довольно жестокий факт. Я, конечно, понимаю, что групповые соотношения — штука довольно хитрая, но всё же. А что, если кроме того, что задаваемая соотношениями группа конечная, ещё известно, что её порядок не превышает фиксированного числа, например 30 (или 100, или 300, или 1000, в таком духе)? Ну и соотношения не какие-нибудь изощрённые безумной длины, а имеют практически интересную (во всяком случае для меня) длину О-большое от максимальной длины слова элемента в группе. Улучшат ли эти факты ситуацию с оценкой алгоритма? Бывает же так, что сложность алгоритма оценивается в том числе по заранее неизвестной величине, которая раскрывается только по результату работы.

[dgwuqtj]

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

известно, что её порядок не превышает фиксированного числа,

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

[mihaild]

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

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

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

[vpb]

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

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

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

-- 07.07.2024, 22:57 --

Вот это первоначальное. (И это, по-видимому, то и есть, что ТС интересовало).

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

Если же есть только порождающие соотношения, и promise проблема что группа конечная... То можно ли хотя бы за полином от $n$ проверить, что группа имеет размер не больше $n$?

-- 07.07.2024, 23:00 --

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

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

Совершенно правильно. Печально, не печально, но в общем имеем, что имеем ...

[mihaild]

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

Вот это первоначальное. (И это, по-видимому, то и есть, что ТС интересовало).

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

Если же есть только порождающие соотношения, и promise проблема что группа конечная... То можно ли хотя бы за полином от $n$ проверить, что группа имеет размер не больше $n$?

Вроде бы это ровно то, что я написал выше.

wikipedia писал(а):

Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt.

В данном случае yes - копредставления единичной группы, no - копредставления конечной неединичной группы.
И я думаю, что ТС интересует именно это.

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

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

[B@R5uk]

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

Но на бесконечных группах может говорить что угодно.

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

К вопросу о том, что групповые соотношения — хитрая штука. Решил тут совершенно случайно поиграться с соотношением

$$abaab\;=\;I$$

Кто бы мог подумать, что из него следует коммутируемость образующих? Домножим на суффикс, сделаем посдтановку и сократим:

$$abaabaab\;=\;aab$$

$$aba\;=\;aab$$

$$ba\;=\;ab$$

Разумеется, обратное не верно, потому что исходное соотношение имеет и другое следствие:

$$a^3b^2\;=\;I$$

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

А вот более сильный пример: соотношение

$$a^3bab\;=\;I$$

кроме очевидных тождественных соотношений, получаемых циклической ротацией слова

$$cW\;=\;I\quad\Leftrightarrow\quad W\;=\;c^{-1}\quad\Leftrightarrow\quad Wc\;=\;I$$

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

$$baaaba\;=\;I$$

$$baaabaaaba\;=\;baaa$$

$$aab\;=\;baa$$

Это первое следствие. Теперь возьмём другую ротацию, домножим на суффикс, сократим и сделаем подстановку:

$$aababa\;=\;I$$

$$aababaababa\;=\;ababa$$

$$ababaababa\;=\;baba$$

$$abab\;=\;baba$$

Это второе следствие. Теперь метод математической индукции. База уже есть, предположение и следствие следуют:

$$ab^nab\;=\;bab^na$$

$$baab^nab\;=\;babab^na$$

$$aabb^nab\;=\;ababb^na$$

$$ab^{n+1}ab\;=\;bab^{n+1}a$$

Предположение умножается спереди на вспомогательный множитель, затем в левой части применяется первое следствие, а во правой — второе. После сокращения и приведения получается следствие. ММИ даёт, что выражение верно для любого n, то есть систему соотношений, если "повезёт", можно наращивать следствиями бесконечно даже когда стартовое соотношение только одно.

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

[vpb]

Да, я был не совсем прав. Более точно, вполне возможно, что вот это утверждение

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

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

верно, но мое рассуждение по поводу него ошибочно.

[B@R5uk]

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

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

Хотелось бы всё-таки понять, откуда берётся эта неопределённость. Связано ли это с непредсказуемой последовательностью преобразований, которым придётся подвергнуть групповые соотношения, либо же это связано с непредсказуемым ростом размера группы?

Я вот, например, знаю такой класс групп:

$$\mathbb{G}_k^n\;=\;\mathbb{Z}_{k^n-1}\rtimes\mathbb{Z}_n\;=\;\left\langle\;a,\;b\;|\;ba=a^kb,\;b^n\;=\;I\;\right\rangle,\qquad\left|\mathbb{G}_k^n\right|\;=\;(k^n-1)n$$

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

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

[dgwuqtj]

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

Возможно ли ещё быстрее?

Конечно, группа перестановок $\mathrm S_n$ имеет $n - 1$ образующую и $O(n^2)$ соотношений ограниченной длины. А вообще если у вас есть группа $G$ с набором образующих и соотношений длины $m$, то $G \wr \math S_n$ имеет задание образующими и соотношениями типа $O(mn + n^2)$, а мощность $m^{n!} n!$.

[B@R5uk]

dgwuqtj в сообщении #1645876 писал(а):

$G \wr \math S_n$

Что этот значок обозначает? Не встречал ни разу.

dgwuqtj в сообщении #1645876 писал(а):

а мощность $m^{n!} n!$

Спасибо! Это интересный результат, особенно если понимать что откуда берётся и почему так получается. Пока я не совсем въехал в ваше утверждение.

[dgwuqtj]

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

Что этот значок обозначает? Не встречал ни разу.

Это сплетение групп (wreath product). Если даны две группы $G$ и $H$, причём $H$ действует на некотором множестве $X$, то $G \wr H$ - это полупрямое произведение $G^X \rtimes H$. Если $H = \mathrm S_n$ с обычным перестановочным действием, то сплетение порождается $G$ и $H$ с такими соотношениями: стабилизатор точки в $H$ (то есть $\mathrm S_{n - 1}$) коммутирует с $G$, а также $G$ коммутирует со своими нетривиальными сопряжениями перестановками. Там аж $n - 1$ такая сопряжённая группа, но так как они переставляются стабилизатором точки, то достаточно коммутируемости с одной из них. При стандартном задании $\mathrm S_n = \langle s_1, \ldots, s_{n - 1} \mid s_i^2, (s_i s_{i + 1})^3, s_i s_j = s_j s_i; |i - j| > 1\rangle$ речь идёт про объединение заданий образующими и соотношениями $G$ и этой группы перестановок с дополнительными соотношениями $s_i x = x s_i$ и $s_1 x s_1 y = y s_1 x s_1$ для всех образующих $x, y \in G$ и $i > 1$.

[mihaild]

dgwuqtj в сообщении #1645876 писал(а):

а мощность $m^{n!} n!$

А не $|G|^{n!} n!$?

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

[dgwuqtj]

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

А не $|G|^{n!} n!$?

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

Или даже похоже на поиск решений диофантовых уравнений над $\mathbb N$.

[mathematician123]

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

Я вот, например, знаю такой класс групп:

$$\mathbb{G}_k^n\;=\;\mathbb{Z}_{k^n-1}\rtimes\mathbb{Z}_n\;=\;\left\langle\;a,\;b\;|\;ba=a^kb,\;b^n\;=\;I\;\right\rangle,\qquad\left|\mathbb{G}_k^n\right|\;=\;(k^n-1)n$$

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

Появилась идея как обобщить эту конструкцию. Рассмотрим соотношения

$$s_1^n = I \quad s_1s_2s_1^{-1} = s_2^n \quad s_2s_3s_2^{-1} = s_3^n$$

Тогда $s_2^{n^n - 1} = I$, $s_3^{n^{n^n - 1} - 1} = I$. Хотелось бы доказать, что любой элемент группы представим в виде $s_3^as_2^bs_1^c$. Поменять местами $s_1, s_2$ и $s_2,s_3$ мы можем, но есть проблема — непонятно, что делать с $s_1s_3$. Что если добавить соотношение $s_1s_3 = s_3s_1$? Группа какого порядка получится? Если у этой группы порядок действительно растёт как двойная экспонента, то можно попробовать построить аналогичные группы с образующими $s_1, \ldots, s_k$.