Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
Существует нормальная подгруппа MbD, являющаяся максимальной относительно свойства Mf)S = (I}. Поскольку S вкладывается в DIM, вследствие упомянутой максимальности и доказанного выше свойства DIM — простая группа. Число порождающих группы D равно 6, так как порождающие г и t могут быть удалены. ?
Из теоремы 3.2 непосредственно следует, что существует 2К» простых групп с шестью порождающими. Интересное свойство теоремы Холла — ее доказуемая неконструктивность. Напомним, что группа называется рекурсивно представленной, если она обладает представлением с конечным числом порождающих и рекурсивно перечислимым множеством определяющих соотношений. Кузнецов [1958] отметил, что верна
Теорема 3.6. Для рекурсивно представленной простой группы разрешима проблема равенства слов.
? Пусть G = Ot1, хп; гх, ...>. Если G=(I}; то результат, понятно, верен, так что предположим, что вф \ \\. Пусть Хф 1 — фиксированный элемент из G.
Если w — произвольное слово из G, то пусть Gw— группа, получающаяся из G добавлением ш к определяющим соотношениям. Тогда
Gw = <xt.....хп; w, гх, гг, ...у.
Если w=l, то, конечно, Gw изоморфна G. Если wфl в G, то из простоты группы G следует, что Gw — тривиальная группа. В частности, X= 1 в Gw тогда и только тогда, когда шф\ в G. Таким образом, Gw также рекурсивно представлена.
Хорошо известным способом легко показать, что в рекурсивно представленной группе множество слов, равных единице, рекурсивно перечислимо. Поэтому алгоритм, решающий проблему равенства слов в G, таков. При заданном w перечисляем слова, равные единице в G, и одновременно перечисляем слова, равные единице в Gn,. Если w=l в G, то w появляется в первом списке, если мфі в G,
262
Гл. IV. Свободные произведения и HNN-расширекия
то во втором списке появляется х. Остается дождаться, пока осуществится одна из этих возможностей. ?
Предположим, что конечно представленная группа H с неразрешимой проблемой равенства существует. (Это будет доказано в-разд. 7.) По теореме Холла H может быть вложена в простую группу G с 6 порождающими. Таким образом, проблема равенства слов ц G неразрешима: Поскольку G проста, из теоремы Кузнецова следует, что G не может быть рекурсивно представленной.
Мы еще не сказали ничего о конечно представленных бесконеч ных простых группах. Первый пример такой группы найден Р. Томпсоном в 1969 г. Г. Хигман [1974] указал Но неизоморфных конечн представленных бесконечных простых групп. Открытым остаетс интересный вопрос: каждая ли конечно представленная группа разрешимой проблемой равенства слов вкладывается в конечно пред ставленную простую группу? Теорема Кузнецова показывает, чт разрешимость проблемы равенства слов — необходимое услови существования такого вложения. В разд. 7 мы докажем следующу теорему Буна и Хигмана [1974]: проблема равенства слов разрешим в некоторой конечно порожденной группе тогда и только тогда, когд эта группа может быть вложена в простую подгруппу в конечі представленной группе.
4. Некоторые алгоритмические проблемы
В настоящем разделе будет предполагаться, что конечно пред ставленные группы с неразрешимой проблемой равенства существуют. (Это будет доказано в разд. 7.) Обратимся вначале к теореї С. И. Адяна [1955] и Рабина [1958], согласно которой большинст теоретико-групповых свойств алгоритмически нераспознаваемо. Z ответствующая теорема для полугрупп была доказана ран А. А. Марковым [1947]. В его работе возникло понятие марковско свойства, определение которого мы приводим ниже.
Пусть P — свойство конечно представленных групп, кото сохраняется при изоморфизме. Свойство P называется марковск если
(1) существует конечно представленная группа Gi со свойством Р;
(2) существует конечно представленная группа G2, которая не может быть вложена ни в какую конечно представленную группу со свойством Р.
Среди известных примеров марковских свойств — свойство быть тривиальной (в качестве G2 можно взять любую конечно представленную нетривиальную группу), конечной, абелевой, свободной и группой без кручения. Свойство P называется наследственным, если из того, что G обладает этим свойством, следует, что и все ее подгруппы им обладают. Любое наследственное свойство конечно
4. Некоторые алгоритмические проблемы
263
представленных групп является марковским, если только существуют конечно представленные группы без этого свойства. Чтобы указать примеры ненаследственных марковских свойств, заметим, что если P — произвольное свойство, такое, что для всех конечно представленных групп, обладающих этим свойством, разрешима проблема равенства слов, то это марковское свойство. Действительно, пусть H — конечно представленная группа с неразрешимой проблемой равенства слов. В каждой конечно представленной группе, в которую вкладывается Н, неразрешима проблема равенства слов, и, следовательно, эта группа не обладает свойством Р. Таким образом, по теореме 3.6 простота является марковским свойством. Иметь ранг 2 — это не марковское свойство, поскольку каждая конечно представленная группа может быть вложена в конечно представленную группу ранга 2 методом Хигмана— Нейман — Неймана.
