Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
Теорема 4.1. Пусть P — произвольное марковское свойство конечно представленных групп. Тогда не существует алгоритма, позволяющего определять, обладают или нет конечно представленные группы свойством Р.
? Пусть Gi и G2— соответствующие свойству P конечно представленные группы из определения марковского свойства. Пусть, далее, H — конечно представленная группа с неразрешимой проблемой равенства слов. Рассмотрим произвольное слово w от порождающих группы Н. Исходя из группы G2#H и слова w, построим группу Ew, используя уже введенную конструкцию Рабина. Напомним, что при HNN-вложении, исходя из данного представления для G2*H*(x), можно эффективно выписать представление для 2-порожденной группы U, в которую вкладывается G2*H*(x). Как и выше, положим
J = <U, ух, у2; г/Г1"^! = "?. УҐа2у2 = и\->, K = <J, г; Z-^yxZ = у\, г-гу2г = у\>, Q = <r, s, t; S-Vs = T2, Z-1SZ = S2), DW = <K*Q; r = z, t = [w, x]>.
аконец,
EW = DW* G1.
Пусть Лц,— указанное представление для группы Ew, соответ-твующее этой конструкции. Исходя из слова w от порождающих руппы H можно эффективно описать процедуру выписывания коечного представления nw. При рассмотрении конструкции Рабина * предыдущем разделе мы видели, что если тф\ в Н, то G2 вкладывается в Ew. Таким образом, E10 не обладает свойством Р. Если ^=I в Н, то Dw = {\), так что Ew изоморфна Gi и, значит, обладает свойством Р. Следовательно, группа Ew с представлением nw обла-
264 Гл. IV. Свободные произведения и И^Ы-расширения
дает свойством P тогда и только тогда, когда W=I в Я. Таким образом, с помощью алгоритма, решающего вопрос о наличии у конечн представленных групп свойства Р, можно решать проблему равен ства слов в Я. Поскольку в Я проблема равенства слов неразрешима1 такой алгоритм невозможен. ?
На самом деле доказательство теоремы показывает, чторекур сивно нераспознаваемы и многие свойства, не являющиеся мар ковскими. Назовем свойство P конечно представленных групп несовместимым со свободными произведениями, если:
(1) существует конечно представленная группа Gi, обладающая свойством P и такая, что
(2) если А — произвольная нетривиальная конечно представленная группа, то AxG1 не обладает Р.
Например, пусть г — произвольное натуральное число. Свойство иметь ранг г несовместимо со свободными произведениями, так как по теореме Грушко — Неймана если Gi имеет ранг г и Аф{\), то ранг группы G1^A строго больше г. Пусть G1— произвольная конечно представленная группа. Снова по теореме Грушко — Неймана свойство быть изоморфной группе Gt несовместимо со свободными произведениями.
При совершении последнего шага конструкции теоремы 4.1 было видно, что если w=l в Я, то Ew изоморфна группе G1. Если wф\ в Я, то Ew является свободным произведением группы Gi и некоторой нетривиальной группы. Таким образом, доказательство показывает, что если P несовместимо со свободными произведениями, то не существует алгоритма, определяющего, задает ли конечное представление группу со свойством Р. В частности, если дана некоторая конечно представленная группа G1, то нельзя сказать, какие конечные представления — представления группы G1.
Укажем теперь конструкцию К. А. Михайловой [1958], с по^ мощью которой автор показала, что прямое произведение двух свое бодных групп может обладать конечно порожденной подгруппой с неразрешимой проблемой вхождения. Пусть 1
H = Kx1.....хп; T1.....rmy I
— некоторая конечно представленная группа. Обозначим через fn свободную группу с базисом {хи . . ., Xn}. Будем обозначать элементы прямого произведения fnxfn упорядоченными парами (и, v). Пусть Lj1 — подгруппа в fnxfn, порожденная парами
(X1, Xi), i=\, п,
(1, г/), j = l, т.
Лемма 4.2. Пара (и, v) лежит в Ln тогда и только тогда, когда u=v в Н.
4. Некоторые алгоритмические проблемы
265
P Понятно, что если (и, V)ZLf1, то u = v в Н, так как каждый из порождающих обладает этим свойством. Предположим, что U = V в Н. Пара (и, и) лежит в LH, поскольку все диагональные пары (*,, X1) лежат в LH. Из равенства u = v в H следует, что
откуда (и, V)ZLf1. ?
Согласно этой лемме, проблема вхождения в Ln в группе FnX X Fn эквивалентна проблеме равенства слов в Н. Взяв в качестве H группу с неразрешимой проблемой равенства слов, получаем, что верна
Теорема 4.3. Пусть п^2. Тогда существует конечно порожденная подгруппа L11 группы FnXFn, такая, что проблема вхождения элементов из Fn X Fn в L11 неразрешима. ?
Пусть G — некоторая конечно порожденная группа. Проблема порождения в G разрешима, если существует алгоритм, который по любому данному конечному подмножеству элементов этой группы определяет, совпадает или нет подгруппа, порожденная этим подмножеством, со всей группой G.
Снова рассмотрим конструкцию Михайловой, начиная с неко-.торой конечно представленной группы Н. Заметим, что #={1} тогда и только тогда, когда u=v для всех пар (и, v) слов от порождающих группы Н. По лемме 4.2 это бывает в точности тогда, когда
Конструкция Рабина дает класс представлений с шестью порождающими, следовательно, проблема тривиальности для представлений с шестью порождающими неразрешима. Поскольку конечно представленная группа H равна {1} тогда и только тогда, когда L11=FnXFn, проблема порождения для F6XF6 неразрешима. Тот же результат для любого п>6 может быть получен простым добавлением новых порождающих символов к представлению и, кроме того, добавлением этих новых порождающих в качестве определяющих соотношений. Таким образом, мы получаем такой результат Миллера III [1971].
