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

концевые вершины полосы П, должны быть первичными, в противном случае, в силу замечания 3, приходим к противоречию с условием Т(4). Таким образом, на некотором шаге либо уже не сможем накрыть без противоречий с условием ч ; е < V Т(4), либо придем к новому слову с меньшим числом кусков. В случаях 2 и 3 для полосы, скажем, П,- и области D\ полосы П проводятся те же рассуждения, что и для неизолированных деновских областей. Таким образом, доказана лемма .> • Лемма 7. Если в диаграмме М, с граничной меткой <р{дМ) =w" есть толь­ ко короткие полосы, то выполняя конечное число ^-преобразований, придем к слову w 0 ~ w и для wo имеет место утверждение теоремы 1 . Этой леммой заканчивается доказательство теоремы 1. Данное утверждение было доказано ранее Баглеем и Прайдом другими методами [4]. Методы, разработанные при доказательстве теоремы I позволяют доказать теорему 2 , необходимую при решении основного результата статьи. Следствие 1. Если w" =1 в группе G=(X; R) с условием С(4)&Т(4), то су­ ществует слово г eR: г s s', / ~ w или w2, где p< t. Следствие 2. Существует алгоритм, позволяющий по слову w определить конечен ли его порядок в группе G. §3. Доказательство теоремы 2 В этом параграфе речь пойдет об элементах бесконечного порядка в группе G = (X; R) с условием С(4)&Т(4). Будет доказана следующая теорема Теорема 2. Существует алгоритм, строящий по любому циклически несо­ кратимому слову w, представляющему в группе G = (X; R) с условием С(4)&Т(4) элемент бесконечного порядка, сопряженное с w*. к < 2 в группе G слово w0, любая степень которого Л, R - несократима. Нам понадобятся следующие леммы. Лемма 8. Существует алгоритм, строящий по любому циклически несо­ кратимому в свободной группе и не равному 1 в группе G слову w циклически Л, R - несократимое слово wo, сопряженное с w в группе G. 111