АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 2001 г.

л и п ? Доказательство очевидно. Лемма 9. Существует алгоритм, строящий по любому несократимому в свободной группе и не равному 1 в группе G слову w R, R - несократимое слово w0, равное ему в группе G. Доказательство очевидно. Лемма 10. Пусть слово и' представляющее в группе G элемент бесконеч­ ного порядка циклически R, R - несократимо и в слове w 2 есть длинное R или R -сокращение. Существует алгоритм, строящий по слову w сопряженное с ним или с его квадратом в группе G слово н>0, любая степень которого R, R - несо­ кратима. Доказательство. Допустим, что в w 2 есть длинное R - сокращение опре­ деленное деновской областью D. Рассмотрим окружность С с меткой w”, п> 1. Пусть tp(8DnC ) —wwi, w = ичп, qtdD\C) а и. Если wi не является куском, то winwiu = W|UWin из леммы 1 , получаем, что w = / , и w имеет конечный поря­ док, так как <p(dD ) a s'. Следовательно, ||wij| = 1. Сделаем разрез вдоль W| и на­ клеим на окружность С п экземпляров области D по границе с меткой w'". На внутренней границе полученной диаграммы записано слово U|", где и,~ w, || «|||=2. Теперь можно показать, что и” е R, т.е. слово щ - искомое. Пусть в w2 есть длинная полоса. Из доказательства леммы 6 следует, что возможны следующие ситуации: к 1. Полоса П = У Dj - полоса первого типа. Из определения полосы перво- /=1 го типа следует, что из областей Du . . . , Д н можно склеить кольцевую диа­ грамму S\: dS\ = Со и С|. При этом может получиться, что 1) все области имеют на внутренней границе по куску и в этом случае, очевидно, любая степень слова ч>\ R, R - несократима; 2) область D, имеет с С) только общую вершину. Пусть <P(C q ) = w'1, ip(C]) я W|, где W| = tpiidDyjdDi'U...udDk.t)n.dU)\CQ. Предположим, что к - 1 > 1. Слово и, циклически R, R - несократимо. Действительно, если приклеить деновскую область или полосу к диаграмме S| по границе С|, то по- 112