Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
Вторая из проблем Дэна — проблема сопряженности: определить для произвольных W1 и W2 из F, представляют они сопряженные элементы группы G или нет? Третья проблема — проблема изоморфизма: определить, задают два данных конечных представления изоморфные группы или нет? Для случая канонических представлений фундаментальных групп замкнутых 2-многообразий все эти три проблемы были решены самим Дэном [1912]; обобщения этих результатов будут рассмотрены нами в гл. V. Мы хотим отметить (см. предложение 5.4 настоящей главы), что в 1932 году Магнус показал разрешимость проблемы равенства слов в случае групп с одним определяющим соотношением, т. е. групп с представлением (X; R), в котором R состоит из одного элемента. Неизвестно, не будет ли разрешима проблема равенства слов для всякого представления, в котором R состоит из двух элементов. Неизвестно также, не будет ли разрешима проблема сопряженности для всякого представления с одним определяющим соотношением.
Ясно, что решение проблемы сопряженности содержит в себе решение проблемы равенства. Интуитивно легко поверить в то, что проблема сопряженности существенно труднее проблемы равенства, поскольку она содержит дополнительную переменную под квантором существования в том смысле, что речь идет о существовании элемента и в F, такого, что W11U11W2U лежит в JV. И действительно, существуют конечно представленные группы с разрешимой проблемой равенства слов, но неразрешимой проблемой сопряженности; см. Фридман [1960], Коллинз [1969], Миллер IH [1971].
2. Конечные представления
129
Проблема изоморфизма еще труднее. Возможно, наиболее поразительный из имеющихся в этой области результатов — результат С. И. Адяна [1955] и Рабина [1958], показывающий, что неразрешим \ даже очень частный случай проблемы изоморфизма, а именно проблема изоморфизма группы, заданной конечным представлением, тривиальной группе. Дальнейшую информацию по алгоритмическим проблемам в теории групп можно найти в работе Миллера III [1971]. В настоящей главе к алгоритмической неразрешимости мы уже больше не вернемся; напротив, будет доказано несколько результатов в положительном направлении.
2. Конечные представления
Основная теорема Тице [1908] связывает различные конечные представления одной и той же группы.
Пусть (X; R) — произвольное представление. Пусть г — произвольный элемент из N и R'=R\J {г}. Понятно, что (X; R) и (X; R') определяют изоморфные группы.
С другой стороны, предположим, что задано (X; R), и пусть X' = =Х[) {х}, где х^ X; если w — произвольный элемент из F и R' = =R\J {г}, где T=X-1UZ)1 то легко видеть, что (X; R) и (X'; R') определяют изоморфные группы.
Будем называть указанные выше переходы от данного представления к некоторому другому, а также обратные к ним преобразованиями Тице.
Предложение 2.1. Два конечных представления задают одну и ту же группу в том и только том случае, когда от одного из них к другому можно перейти конечной последовательностью преобразований Тице.
? Понятно, что два представления, конечные или бесконечные, связанные конечной последовательностью преобразований Тице, определяют изоморфные группы. Для доказательства обратного предположим, что два конечных представления (X1; ^1) и (X2; R1) определяют изоморфные группы. Для I = I1 2 обозначим через F1 свободную группу с базисом Хг, и пусть Af, — нормальное замыкание в F1 подмножества Ri^F1. Можно предполагать, что дана группа G и два отображения фг из F1 на G с ядрами ./V;. Можно предполагать, конечно, что X1flX2=0. Пусть F — свободная группа с базисом X=X1L)X2. Тогда (J)1 и ф2 вместе определяют отображение из X в G, продолжающееся до гомоморфизма ф из F в G. В самом деле, если рассматривать F1 и F2 как подгруппы в F, то ф — единственное общее Продолжение ГОМОМОрфИЗМОВ фі и ф2.
Для каждого XgX1 выберем wx?F2, такой, что хф=дожф, и обозначим через S1 конечное множество слов Sx=X-1Wx. Определим S2 аналогичным способом. От представления (X1; Ri) к представле-
№ 653
130 Гл. П. Порождающие и соотношения_
нию (X; P1LlS2) можно перейти конечной последовательностью преобразований Тице, каждое из которых вводит новый порождающий X? X2 и соотношение X-1Wx ? S2, выражающее х через X1. Ясно, что ядро N отображения ср из F на G является нормальным замыканием в F множества PiLlS2. Понятно также, что (P2USi)(p=l( поскольку R2 U S1SA7. Конечной последовательностью преобразований Тице можно присоединить элементы из P2LlSi по одному к Pi U S2, чтобы получить представление (X; R)=(X; Pi U Рг U S1 и S2) группы G.
Нами показано, что от (X1; R1) к (X; P) можно перейти конечной последовательностью преобразований Тице. Из соображений симметрии подобным же образом можно перейти от (X2; R2) к (X; R). Отсюда следует, что возможен и переход от (Xi; Pi) к (X2; R2). О
Следует подчеркнуть, что предложение 2.1 не дает решения проблемы изоморфизма даже в случае, когда проблема равенства слов разрешима для обоих данных представлений. Действительно, процедура выбора множеств S1 и S2 неэффективна. Преобразования Тице использовались для доказательства того, что разрешимость проблемы равенства или сопряженности — инвариант конечного представления группы; впрочем, даже более общее утверждение может быть доказано следующим несложным рассуждением.
