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

[B@R5uk]

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

[dgwuqtj]

Она разрешима, вот обсуждение с подробностями: https://math.stackexchange.com/questions/15852/the-word-problem-for-finite-groups. Как я понимаю, оценить сложность наивного алгоритма легко, но она запросто может быть экспоненциальной как от размера входа (числа образующих и суммы длин соотношений), так и от порядка группы.

[dgwuqtj]

Хотя нет, очевидной оценки времени не видно.

[B@R5uk]

dgwuqtj, спасибо. Остаточно конечная группа — это что-то более сильное, чем просто конечная группа, но далеко ещё не полноценная бесконечная, я правильно понимаю?

[dgwuqtj]

Residually finite - это у которой пересечение всех нормальных подгрупп конечного индекса тривиально. То есть имеется достаточно много конечных факторгрупп, чтобы различать элементы. Свободные группы и группы типа $\mathrm{GL}(7, \mathbb Z)$ этим свойством обладают.

[mihaild]

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

Существует ли строгое доказательство того, что в конечной группе ситуация положительная?

А как задается эта группа?

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

так и от порядка группы

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

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

Остаточно конечная группа — это что-то более сильное, чем просто конечная группа, но далеко ещё не полноценная бесконечная, я правильно понимаю?

Да. Любая конечная группа остаточно конечна, но есть и куча бесконечных остаточно конечных групп.

[B@R5uk]

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

Пытаюсь пока въехать в доказательство, что на двух картинках дано. Оно явно не конструктивное, не смотря на то, что вроде-бы описывается последовательность действий, которым можно следовать, из-за непозволительной ресурсоёмкости этих действий.

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

-- 06.07.2024, 22:29 --

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

А как задается эта группа?

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

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

По таблице умножения легко решается за полином.

У меня совсем обратная проблема: восстановить таблицу умножения (или граф Кэли — они полностью эквивалентны, только первая быстрая, а второй компактный) по групповым соотношениям.

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

Да.

Спасибо!

[dgwuqtj]

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

из-за непозволительной ресурсоёмкости этих действий.

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

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

восстановить таблицу умножения (или граф Кэли — они полностью эквивалентны, только первая быстрая, а второй компактный) по групповым соотношениям

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

[B@R5uk]

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

А для более разумных классов групп...

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

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

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

...могут быть и более быстрые алгоритмы

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

[dgwuqtj]

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

[B@R5uk]

dgwuqtj, решётку по таблице я делал. Сначала строится список всех циклов в группе, в том числе вложенных, получаем множество циклов и затравочное множество подгрупп. Затем берём всевозможные пары цикл-подгруппа и строим замыкания относительно групповой операции, получаем новые подгруппы, включая исходную группу. Проверка тождественности двух подгрупп проста: берём образующие одной и смотрим, входят ли они в другую и наоборот. Для проверки включения действие "наоборот" не нужно. Когда нового ничего не получается и очередь подгрупп закончилась — задача решена. В результате имеем список всех подгрупп, их вложенность друг в друга (решётку надо будет ещё чуть-чуть довести до ума), их генераторы в группе, ранки, в том числе всей группы, все возможные множества образующих группы (из каждого цикла в порождающем комплекте взять по одному образующему элементу). Может ещё даже что-то, я уже забыл. Проблема здесь будет нарисовать граф красиво, чтобы одно на другое не налезало и связи не пересекали ноды. Даже если что-то подобное реализовано в yEd и Gephi, даже если получится осилить эти или подобные алгоритмы, без ручного довода человеком не обойтись.

Меня больше проблема перехода от соотношений к таблице/графу Кэли интересует. У меня пока на этом затык.

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

[B@R5uk]

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

То можно ли хотя бы за полином от $n$ проверить, что группа имеет размер не больше $n$?

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

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

1
a
b
aa
ab
ba
bb
aaa
aab
aba
abb
baa
bab
bba
... и так далее

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

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

(————————————————————————————————————————————————————————————————)

Я пытаюсь обойти эту проблему широкой свободы возможных действий над словом с помощью предварительной постройки некоторого минимального набора редуцирующих (в лексикографическом смысле) соотношений. Очевидно, что слова в самих этих соотношениях не могут быть дальше редуцированны с помощью них же. Например, для группы $\mathbb{Z}_7\rtimes\mathbb{Z}_3$ возможен такой набор (не уверен, что он единственный даже для фиксированного множества исходных групповых соотношений):

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

aab -> ba
bbb -> 1
babb -> aa
bbaa -> abb
bbab == aaaa
abaaa -> b
ababa -> bb
baaaa -> ab
babaa -> abab
aaaaaa -> babab

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

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

№№      Элем.   Наслед. a, b    Редуциров.
1       I       a       b       -
2       a       aa      ab      -
3       b       ba      bb      -
4       aa      aaa     aab     -
5       ab      aba     abb     -
6       ba      baa     bab     -
7       bb      bba     bbb     -
8       aaa     aaaa    aaab    -
-       aab     -       -       ba
9       aba     abaa    abab    -
10      abb     abba    abbb    -
11      baa     baaa    baab    -
12      bab     baba    babb    -
13      bba     bbaa    bbab    -
-       bbb     -       -       I
14      aaaa    aaaaa   aaaab   -
-       aaab    -       -       aba
15      abaa    abaaa   abaab   -
16      abab    ababa   ababb   -
17      abba    abbaa   abbab   -
-       abbb    -       -       a
18      baaa    baaaa   baaab   -
-       baab    -       -       bba
19      baba    babaa   babab   -
-       babb    -       -       aa
-       bbaa    -       -       abb
-       bbab    -       -       aaaa
20      aaaaa   aaaaaa  aaaaab  -
-       aaaab   -       -       baa     (= aaba)
-       abaaa   -       -       b
-       abaab   -       -       abba
-       ababa   -       -       bb
-       ababb   -       -       aaa
-       baaaa   -       -       ab
-       baaab   -       -       baba
-       babaa   -       -       abab
21      babab   bababa  bababb  -
-       aaaaaa  -       -       babab
-       aaaaab  -       -       abaa    (= aaaba)
-       bababa  -       -       I       (= bbb)
-       bababb  -       -       baaa
 

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

$$mN$$

где m — число образующих, N — порядок группы. Для каждого узла выполняется проверка на редуцируемость. Для этого надо проверить не является ли какой-нибудь суффикс текущего слова первым словом в каком-нибудь редуцирующем соотношении из списка выше. Тот факт, что префиксы несократимы гарантируется построением. Это перестаёт быть верным, после первой подстановки суффикса. Однако, эта подстановка гарантированно уменьшает лексикографический вес слова, поэтому, даже если оно сократимо далее, минимальное имя элемента уже имеется в наличии в частично (на данном этапе) построенном дереве. Чтобы получить конечный результат надо просто пройтись по нему от корня, перебирая буквы слова, полученного подстановкой суффикса. Надо также заметить, что лексикографическое упорядочивание у меня здесь не как в словаре, а наоборот: сначала смотрится длина слова, а потом уже его алфавитный порядок.

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

$$O\left(\log_mN\right)$$

когда большое число элементов группы не коммутирует, и в записи слов встречаются всевозможные комбинации образующих во всевозможных порядках. А в худшем случае (смотри группы $\mathbb{Z}_{32}$, $\mathbb{Z}_{16}\times\mathbb{Z}_2$, $\mathbb{Z}_{8}\times\mathbb{Z}_2^2$ и так далее для примера):

$$\frac N {2^{m-1}}+m-1$$

То есть, не хуже порядка группы.

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

Каждый элемент в пятом столбце встречается ровно m раз. Это будет нужно ниже.

(————————————————————————————————————————————————————————————————)

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

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

$$AB=C,\quad BD=F$$

Домножая и делая подстановку получаем:

$$AF=CD$$

Результирующее соотношение может дальше упроститься, если A и C имеют одинаковый префикс и/или F и D — суффикс. После сокращения соотношение дальше редуцируется всевозможным образом с помощью имеющегося набора соотношений. Несократимый результат, если он не является тривиальным "нейтральный элемент равен нейтральному" добавляется в список. Затем проверяться, можно ли имевшиеся ранее в списке соотношения сократить с помощью вновь найденных. Это гарантирует, что список будет минимальным не саморедуцируемым редуцирующим набором соотношений. Требования, необходимые для алгоритма выше.

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

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

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

$$\langle\;aab=baa,\;abb=bba\;\rangle$$

Для слова длиной 12 ниже они дают 18 синонимов (не уверен, что список полный, но для примера достаточно):

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

abbaaaaabbbb
bbabaaaabbba
bbabaaabbaba
bbabaabaabba
bbabaababbaa
bbabaabbaaba
bbabaabbbaaa
bbababaababa
bbababbaaaba
bbababbabaaa
bbabbaaaabba
bbabbaaabbaa
bbabbaabaaba
bbabbaabbaaa
bbabbabaabaa
bbabbabbaaaa
bbabbbaaaaba
bbabbbaabaaa
bbabbbbaaaaa

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

$$C_{19}^2=171$$

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

$$\left(a^3b\right)^5=I$$

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

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

(————————————————————————————————————————————————————————————————)

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

Всё. Клихэнгер. За три с половиной часа клаважмаканья устал. Опишу текущее состояние дел позже.

[vpb]

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

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

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

Хотя нет, очевидной оценки времени не видно.

Её и быть не может.

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

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

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

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

"Residually finite" по-русски "финитно аппроксимируемая".

[mihaild]

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

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

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

[vpb]

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

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

Совершенно очевидно. Берем вход, вычисляем для него оценку длины работы алгоритма, и пускаем алгоритм. Если за предполагаемое время работа не закончилась, значит, группа не единичная. Фсё.

-- 07.07.2024, 13:55 --

ТСу порекомендую книжку
D.F.Holt, B.Eick, E.A.O'Brien, Handbook of computational group theory.
И плюс книжки по общей теории групп, которые я на форуме писал раньше. Можно еще
Линдон, Шупп, Комбинаторная теория групп;
Каррас, Магнус, Солитэр, с тем же названием;
А.Ю.Ольшанский, Геометрия определяющих соотношений в группах.

-- 07.07.2024, 14:12 --

P.S.
mihaild
Или Вас что-то еще не устраивает насчет алгоритма ? Мне казалось, там всё прозрачно.