Задача со словом для групп

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

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

История [ править ]

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

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

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

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

Более конкретное описание [ править ]

В более конкретных терминах проблема единообразия слов может быть выражена как вопрос переписывания буквальных строк . ^[10] Для представления 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 ,аа , А или АА . Затем обратите внимание, что мы также можем умножить на aaa , чтобы мы могли преобразовать A в aa и преобразовать AA в a . В результате проблема слов для циклической группы третьего порядка разрешима.

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

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

Примеры [ править ]

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

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

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

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

${\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{ and }}v{\text{ are words in }}X{\text{ and }}u=v{\text{ in }}G\ \}}$

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

${\displaystyle f_{P}(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \in S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \notin S\end{cases}}}$

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

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

${\displaystyle g(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \notin S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \in S\end{cases}}}$

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

${\displaystyle h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}}$

Пример [ править ]

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

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

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

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

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

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

Для каждого отображения X в S Если каждый относитель в R удовлетворяется в S Если w ≠ 1 в S, верните 0 Конец, если  Конец, если Конец для

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

${\displaystyle h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}}$

Это показывает, что у 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/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ G\end{cases}}}$

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

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

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

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

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

Предположим, что G - универсальная разрешимая группа задач со словами. Учитывая конечное представление P = ⟨ X | R⟩ из группы Н , можно рекурсивно перечислить все гомоморфизмы часа : H → G сначала перечисление всех отображений часа ^† : X → G . Не все эти отображения продолжаются до гомоморфизмов, но, поскольку h ^† ( 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\ {\text{for some}}\ h_{n}}$

${\displaystyle {\text{If}}\ w=1\ {\text{in}}\ H,\ h_{n}(w)=1\ {\text{in}}\ G\ {\text{for all}}\ h_{n}}$

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

Пусть  n = 0 Пусть  repeatable = TRUE while ( повторяемый ) увеличьте n на 1, если (решение проблемы слов в G показывает, что h n ( w ) 1 в G ) Пусть  repeatable = FALSEвыход 0.

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

${\displaystyle f(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}}$

Функция 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/does not halt}}\ &{\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/does not halt}}\ &{\text{if}}\ x\neq 1\ {\text{in}}\ S_{w}.\end{cases}}}$

Написать:

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

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

Отсюда следует, что: рекурсивно. По конструкции:${\displaystyle h(w)=g(w,a)}$

${\displaystyle h(w)={\begin{cases}0&{\text{if}}\ a=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\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/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ S.\end{cases}}}$

Существование такой функции достаточно , чтобы доказать , что проблема разрешима слово для 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, Руководство MR  1099152
• Деновский, Макс (1911), "Убер unendliche diskontinuierliche Gruppen" , Mathematische Annalen , 71 (1): 116-144, DOI : 10.1007 / BF01456932 , ISSN  0025-5831 , МР  1511645
• Деновский, Макс (1912), "Преобразование дер Kurven Ауф zweiseitigen Flächen" , Mathematische Annalen , 72 (3): 413-421, DOI : 10.1007 / BF01456725 , ISSN  0025-5831 , МР  1511705
• А. В. Кузнецов, "Алгоритмы как операции в алгебраических системах", Известия Акад. Сер мат АН СССР (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 .