Задача со словом для групп - Word problem for groups

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

Связанная, но отличающаяся друг от друга проблема единообразных слов для класса K рекурсивно представленных групп - это алгоритмическая проблема решения, заданного в качестве входных данных представления P для группы G в классе K и двух слов в генераторах G , представляют ли слова же элемент G . Некоторые авторы требуют, чтобы класс K был определен рекурсивно перечислимым набором представлений.

История

На протяжении всей истории предмета вычисления в группах проводились с использованием различных нормальных форм . Обычно они неявно решают проблему слов для рассматриваемых групп. В 1911 году Макс Дена предложил, чтобы слово проблема является важной областью исследования в своем собственном праве, наряду с проблемой сопряженности и задачей группы изоморфизма . В 1912 году он дал алгоритм, который решает как проблему слова, так и проблему сопряженности для фундаментальных групп замкнутых ориентируемых двумерных многообразий рода больше или равного 2. Последующие авторы значительно расширили алгоритм Дена и применили его к широкому кругу групп. теоретические проблемы решения .

Как было показано Петр Новиков в 1955 году , что существует конечно определенная группа G такая , что задача слово G является неразрешимой . Отсюда сразу следует, что проблема единообразного слова также неразрешима. Другое доказательство было получено Уильямом Бун в 1958 году.

Слово «проблема» было одним из первых примеров неразрешимой проблемы, которую можно было найти не в математической логике или теории алгоритмов , а в одном из центральных разделов классической математики - алгебре . Из-за своей неразрешимости некоторые другие проблемы комбинаторной теории групп также оказались неразрешимыми.

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

Более конкретное описание

В более конкретных терминах проблема единообразия слов может быть выражена как вопрос переписывания буквальных строк . Для представления P группового G , P будет указывать определенное количество генераторов

х , у , z , ...

для G . Нам нужно ввести одну букву для x и другую (для удобства) для элемента группы, представленного x ⁻¹ . Назовите эти буквы (вдвое больше, чем образующих) алфавитом нашей задачи. Тогда каждый элемент в G представлен в некотором роде произведение ${\ displaystyle \ Sigma}$

abc ... pqr

символов из , некоторой длины, умноженной на G . Строка длиной 0 ( пустая строка ) обозначает единичного элемента е из G . Суть всей проблемы состоит в том, чтобы уметь распознать все способы представления e при определенных отношениях. ${\ displaystyle \ Sigma}$

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

В качестве простого примера возьмем презентацию { a | а ³ }. Запись А для обратного , мы имеем возможные ниточки , сочетающие любое количество символов и A . Каждый раз, когда мы видим aaa , aA или Aa, мы можем вычеркнуть их. Мы также должны не забыть вычеркнуть AAA ; это говорит о том, что, поскольку куб a является единичным элементом G , то же самое можно сказать и о кубе, обратном к a . В этих условиях проблема слов становится легкой. Сначала сократите строки до пустой строки, a , aa , A или AA . Затем обратите внимание, что мы также можем умножить на aaa , чтобы мы могли преобразовать A в aa и преобразовать AA в a . В результате проблема слов для циклической группы третьего порядка разрешима.

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

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

Примеры

Следующие группы имеют решаемую проблему со словами:

• Автоматические группы , в том числе:
  • Конечные группы
  • Отрицательно изогнутые (также известные как гиперболические) группы
  • Евклидовы группы
  • Группы Кокстера
  • Группы кос
  • Геометрически конечные группы
• Конечно порожденные свободные группы
• Конечно порожденные свободные абелевы группы
• Полициклические группы
• Конечно порожденные рекурсивно абсолютно представленные группы , в том числе:
  • Конечно определенные простые группы.
• Конечно определенные финитно аппроксимируемые группы
• Группы одного отношения (это теорема Магнуса), в том числе:
  • Фундаментальные группы замкнутых ориентируемых двумерных многообразий.
• Комбинированные группы
• Группы с возможностью автоматического суммирования

Известны также примеры неразрешимых словесных проблем:

• Для рекурсивно перечислимого множества A натуральных чисел, имеющего неразрешимую проблему принадлежности, ⟨a , b, c, d | ^п ба ^п = с ^п постоянного ток ^п  : п ∈ ⟩ является конечно порожденной группой с перечислимой презентацией , чье слово проблема неразрешима
• Каждая конечно порожденная группа с рекурсивно перечислимым представлением и неразрешимой проблемой слов является подгруппой конечно определенной группы с неразрешимой проблемой слов
• Число соотносителей в конечно представленной группе с неразрешимой проблемой слов может быть всего 14 или даже 12.
• Явный пример разумной короткой презентации с неразрешимой проблемой слов дан в Collins 1986:

${\ displaystyle {\ begin {array} {lllll} \ langle & a, b, c, d, e, p, q, r, t, k & | && \\ & p ^ {10} a = ap, & pacqr = rpcaq, & ra = ar, & \\ & p ^ {10} b = bp, & p ^ {2} adq ^ {2} r = rp ^ {2} daq ^ {2}, & rb = br, & \\ & p ^ {10 } c = cp, & p ^ {3} bcq ^ {3} r = rp ^ {3} cbq ^ {3}, & rc = cr, & \\ & p ^ {10} d = dp, & p ^ {4} bdq ^ {4} r = rp ^ {4} dbq ^ {4}, & rd = dr, & \\ & p ^ {10} e = ep, & p ^ {5} ceq ^ {5} r = rp ^ {5} ecaq ^ {5}, & re = er, & \\ & aq ^ {10} = qa, & p ^ {6} deq ^ {6} r = rp ^ {6} edbq ^ {6}, & pt = tp, & \ \ & bq ^ {10} = qb, & p ^ {7} cdcq ^ {7} r = rp ^ {7} cdceq ^ {7}, & qt = tq, & \\ & cq ^ {10} = qc, & p ^ { 8} ca ^ {3} q ^ {8} r = rp ^ {8} a ^ {3} q ^ {8}, && \\ & dq ^ {10} = qd, & p ^ {9} da ^ {3 } q ^ {9} r = rp ^ {9} a ^ {3} q ^ {9}, && \\ & eq ^ {10} = qe, & a ^ {- 3} ta ^ {3} k = ka ^ {-3} ta ^ {3} && \ rangle \ end {array}}}$

Частичное решение проблемы со словом

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

Учитывая рекурсивное представление P = ⟨ X | R ⟩ для группы G , определим:

${\ displaystyle S = \ {\ langle u, v \ rangle: u {\ text {и}} v {\ text {- слова в}} X {\ text {и}} u = v {\ text {in} }ГРАММ\ \}}$

тогда существует частично рекурсивная функция f _P такая, что:

${\ displaystyle f_ {P} (\ langle u, v \ rangle) = {\ begin {cases} 0 & {\ text {if}} \ \ langle u, v \ rangle \ in S \\ {\ text {undefined / не останавливается}} \ & {\ text {if}} \ \ langle u, v \ rangle \ notin S \ end {case}}}$

Более неформально, существует алгоритм, который останавливается, если u = v , но не останавливается в противном случае.

Отсюда следует, что для решения проблемы слов для P достаточно построить рекурсивную функцию g такую, что:

${\ displaystyle g (\ langle u, v \ rangle) = {\ begin {cases} 0 & {\ text {if}} \ \ langle u, v \ rangle \ notin S \\ {\ text {undefined / не останавливается }} \ & {\ text {if}} \ \ langle u, v \ rangle \ in S \ end {case}}}$

Однако у = V в G тогда и только тогда , когда увы ^-1 = 1 в G . Отсюда следует, что для решения проблемы слов для P достаточно построить рекурсивную функцию h такую, что:

${\ displaystyle h (x) = {\ begin {cases} 0 & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ G \\ {\ text {undefined / не останавливается}} \ & {\ text {if}} \ x = 1 \ {\ text {in}} \ G \ end {case}}}$

Пример

На примере использования этой техники будет доказано следующее:

Теорема: конечно представимая финитно аппроксимируемая группа имеет разрешимую проблему слов.

Доказательство: Пусть G = ⟨ X | R ⟩ является конечно, остаточно конечной группой.

Пусть S будет группой всех перестановок N , натуральных чисел, которая фиксирует все числа, кроме конечного, тогда:

1. S является локально конечным и содержит копию любой конечной группы.
2. Проблема слов в S разрешима путем вычисления произведений перестановок.
3. Существует рекурсивное перечисление всех отображений конечного множества X в S .
4. Так как G аппроксимируется конечными, если ш есть слово в образующих X из G , то W ≠ 1 в G тогда и только некоторого отображения X в S индуцирует гомоморфизм такой , что ш ≠ 1 в S .

Учитывая эти факты, алгоритм определяется следующим псевдокодом:

For every mapping of X into S
    If every relator in R is satisfied in S
        If w ≠ 1 in S
            return 0
        End if
    End if
End for

определяет рекурсивную функцию h такую, что:

${\ displaystyle h (x) = {\ begin {cases} 0 & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ G \\ {\ text {undefined / не останавливается}} \ & {\ text {if}} \ x = 1 \ {\ text {in}} \ G \ end {case}}}$

Это показывает, что у G есть разрешимая проблема слов.

Неразрешимость проблемы единого слова

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

Чтобы решить проблему равномерного слова для класса K групп, достаточно найти рекурсивную функцию, которая принимает конечное представление P для группы G и слово в образующих G , такую, что всякий раз, когда G ∈ K : ${\ displaystyle f (P, w)}$${\ displaystyle w}$

${\ displaystyle f (P, w) = {\ begin {cases} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ G \\ {\ text {undefined / не останавливается }} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ G \ end {case}}}$

Теорема Буна-Роджерса: не существует единого частичного алгоритма, который решает проблему слов во всех конечно определенных группах с разрешимой проблемой слов.

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

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

Замечание: Пусть G = ⟨ X | R ⟩ является конечно определенной группой с решаемой проблемой тождества и Н конечное подмножество G . Пусть Н ^* = ⟨ Н ⟩, быть группой , порожденной H . Тогда задача слово в Н ^* разрешима: дано два слова ч, к в генераторах Н из Н ^* , записать их в виде слов X и сравнить их с помощью решения проблемы равенства в G . Легко думать , что это демонстрирует единообразное решение проблемы тождества для класса К (скажем) конечно порожденных групп , которые могут быть встроены в G . Если бы это было так, то несуществование универсальной разрешимой группы проблем со словами легко вытекало бы из высказывания Буна-Роджерса. Однако только что предложенное решение проблемы слов для групп из K не является однородным. Чтобы убедиться в этом, рассмотрим группу J = ⟨ Y | Т ⟩ ∈ K ; для того , чтобы использовать вышеупомянутый аргумент , чтобы решить эту проблему слов в J , в первую очередь необходимо выставить отображение е: Y → G , которая простирается до вложения е ^* : J → G . Если бы существовала рекурсивная функция, которая отображала (конечно порожденные) представления групп в K во вложения в G , то действительно можно было бы построить равномерное решение проблемы слов в K. Но в целом нет оснований предполагать, что такая рекурсивная функция существует. Тем не менее, оказывается, что, используя более сложный аргумент, проблема слова в J может быть решена без использования вложения е : J → G . Вместо этого используется перечисление гомоморфизмов используются, и поскольку такое перечисление может быть построено равномерно, что приводит к равномерному решению проблемы тождества в K .

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

Предположим, что G - универсальная разрешимая группа словесных задач. Учитывая конечное представление P = ⟨ X | R⟩ из группы Н , можно рекурсивно перечислить все гомоморфизмы часа : H → G сначала перечисление всех отображений часа ^† : X → G . Не все из этих отображений распространяются на гомоморфизмы, но, так как ч ^† ( R ) конечно, можно различать гомоморфизмы и не -гомоморфизмы, используя решение проблемы равенства в G . «Отсев» негомоморфизмов дает требуемое рекурсивное перечисление: h ₁ , h ₂ , ..., h _n , ....

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

${\ displaystyle {\ text {If}} \ w \ neq 1 \ {\ text {in}} \ H, \ h_ {n} (w) \ neq 1 \ {\ text {in}} \ G \ {\ текст {для некоторых}} \ h_ {n}}$

${\ displaystyle {\ text {If}} \ w = 1 \ {\ text {in}} \ H, \ h_ {n} (w) = 1 \ {\ text {in}} \ G \ {\ text { для всех}} \ h_ {n}}$

Рассмотрим алгоритм, описываемый псевдокодом:

Let n = 0
    Let repeatable = TRUE
        while (repeatable)
            increase n by 1
            if (solution to word problem in G reveals hn(w) ≠ 1 in G)
                Let repeatable = FALSE
output 0.

Это описывает рекурсивную функцию:

${\ displaystyle f (w) = {\ begin {cases} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ H \\ {\ text {undefined / не останавливается}} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ H. \ end {case}}}$

Функция F явно зависит от представления P . Считая его функцией двух переменных, была построена рекурсивная функция , которая принимает конечное представление P для группы H и слово w в образующих группы G , так что всякий раз, когда G имеет разрешимую проблему со словами: ${\ displaystyle f (P, w)}$

${\ displaystyle f (P, w) = {\ begin {cases} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ H \\ {\ text {undefined / не останавливается }} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ H. \ end {cases}}}$

Но это равномерно решает проблему слов для класса всех конечно определенных групп с разрешимой проблемой слов, что противоречит Бун-Роджерсу. Это противоречие доказывает, что G не может существовать.

Алгебраическая структура и проблема слова

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

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

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

Следующее было доказано Бернхардом Нойманом и Ангусом Макинтайром :

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

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

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

Рекурсивно представленная простая группа S имеет разрешимую проблему слов.

Чтобы доказать это Пусть ⟨ X | R ⟩ рекурсивное представление для S . Выберите ∈ S такой , что ≠ 1 в S .

Если ж это слово на генераторах X из S , то пусть:

${\ displaystyle S_ {w} = \ langle X | R \ cup \ {w \} \ rangle.}$

Существует такая рекурсивная функция , что: ${\ displaystyle f _ {\ langle X | R \ cup \ {w \} \ rangle}}$

${\ displaystyle f _ {\ langle X | R \ cup \ {w \} \ rangle} (x) = {\ begin {cases} 0 & {\ text {if}} \ x = 1 \ {\ text {in}} \ S_ {w} \\ {\ text {undefined / не останавливается}} \ & {\ text {if}} \ x \ neq 1 \ {\ text {in}} \ S_ {w}. \ End {case }}}$

Напишите:

${\ displaystyle g (w, x) = f _ {\ langle X | R \ cup \ {w \} \ rangle} (x).}$

Тогда, поскольку конструкция f была равномерной, это рекурсивная функция двух переменных.

Отсюда следует, что: рекурсивно. По конструкции: ${\ Displaystyle ч (ш) = г (ш, а)}$

${\ displaystyle h (w) = {\ begin {cases} 0 & {\ text {if}} \ a = 1 \ {\ text {in}} \ S_ {w} \\ {\ text {undefined / не останавливается }} \ & {\ text {if}} \ a \ neq 1 \ {\ text {in}} \ S_ {w}. \ end {cases}}}$

Поскольку S - простая группа, ее единственными фактор-группами являются она сама и тривиальная группа. Так как ≠ 1 в S , мы видим , а = 1 в S _ш , если и только если S _ш тривиально тогда и только тогда , когда W ≠ 1 в S . Следовательно:

${\ displaystyle h (w) = {\ begin {cases} 0 & {\ text {if}} \ w \ neq 1 \ {\ text {in}} \ S \\ {\ text {undefined / не останавливается}} \ & {\ text {if}} \ w = 1 \ {\ text {in}} \ S. \ end {case}}}$

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

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

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

Смотрите также

• Комбинаторика слов
• SQ-универсальная группа
• Проблема со словом (математика)
• Проблема достижимости
• Вложенные стековые автоматы (использовались для решения проблемы слов для групп)

Примечания

использованная литература

• У. В. Бун, Ф. Б. Каннонито и Р. К. Линдон . Проблемы со словами: проблема решения в теории групп. Нидерланды: Северная Голландия. 1973 г.
• Бун, WW; Хигман, Г. (1974). «Алгебраическая характеристика разрешимости проблемы слова» . J. Austral. Математика. Soc . 18 : 41–53. DOI : 10.1017 / s1446788700019108 .
• Бун, WW; Роджерс-младший, Х. (1966). «О проблеме Дж. Х. К. Уайтхеда и проблеме Алонзо Черча» . Математика. Сканд . 19 : 185–192. DOI : 10,7146 / math.scand.a-10808 .
• Борисов В.В. (1969) "Простые примеры групп с неразрешимой проблемой слов", Академия Наук СССР. Математические заметки , 6 : 521–532, ISSN  0025-567X , MR  0260851
• Коллинз, Дональд Дж. (1969), «Проблемы слова и сопряжения в группах с несколькими определяющими отношениями», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 15 (20–22): 305–324, doi : 10.1002 / malq. 19690152001 , Руководство по ремонту  0263903
• Коллинз, Дональд Дж (1972), "Об одной теореме вложения группы В. В. Борисов", Бюллетень Лондонского математического общества , 4 (2): 145-147, DOI : 10,1112 / БОГО / 4.2.145 , ISSN  0024-6093 , MR  0314998
• Коллинз, Дональд Дж (1986), "Простая презентация группы с неразрешимой проблемой слово", штат Иллинойс Журнал математики , 30 (2): 230-234, DOI : 10,1215 / IJM / 1256044631 , ISSN  0019-2082 , М.Р.  0840121
• Коллинз, Дональд Дж .; Цишанг Х. (1990), Комбинаторная теория групп и фундаментальные группы , Берлин, Нью-Йорк: Springer-Verlag , с. 166, Руководство по ремонту  1099152
• Деновский, Макс (1911), "Убер unendliche diskontinuierliche Gruppen" , Mathematische Annalen , 71 (1): 116-144, DOI : 10.1007 / BF01456932 , ISSN  0025-5831 , МР  1511645 , S2CID  123478582
• Деновский, Макс (1912), "Преобразование дер Kurven Ауф zweiseitigen Flächen" , Mathematische Annalen , 72 (3): 413-421, DOI : 10.1007 / BF01456725 , ISSN  0025-5831 , МР  1511705 , S2CID  122988176
• А. В. Кузнецов, "Алгоритмы как операции в алгебраических системах", Известия Акад. Сер мат АН СССР (1958)
• CF Миллер. "Решение проблемы для группы - обзор и размышления". В « Алгоритмах и классификации в комбинаторной теории групп» , страницы 1–60. Спрингер, 1991.
• Ротман, Джозеф (1994), Введение в теорию групп , Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-94285-8
• Стиллвелл, Дж. (1982). «Проблема слова и проблема изоморфизма групп» . Вестник АПП . 6 : 33–56. DOI : 10,1090 / s0273-0979-1982-14963-1 .
• Ниберг-Бродда, Карл-Фредрик (2021), «Проблема слов для моноидов с одним отношением: обзор», Semigroup Forum , 103 (2): 297–355, arXiv : 2105.02853 , doi : 10.1007 / s00233-021-10216 -8