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

ТЕОРЕМА. Цуоть Q- - Т-1/4-группа, й и два элемента из б , а - целее положительное число так о е, что (ХпФ 1 .Т о гд а , если а п& = 6 а п , т о СХ и В лежат в одной и той жв циклической подгруппе & . ДОКАЗАТЕЛЬСТВО, Предположим, что утверждение теоремы ложно.Тогда рассмотрим множество М сло в W , удовле­ творяющих следующим условиям; ( 1 ) I V з (Й 6 )п Р С 1- 4 , где м - положитель­ ное целое 4исло и М б ) я + 4 . ( 2 ) /?в и С в не лежат в одной циклической подгруппе ( ( 3 ) К-минимально для ( I ) и ( 2 ) условий. Пусть М<НИЛ W е /М и I Йв>\ - минимальна].Для дока- • за т е л ь ст в а теоремы достаточно п оказать, что - 0 , Пусть . I ((Вс1/, 1 ДС|) , если 1Д1 -* /в/ » ,,W| , если lflf< 1в» . Т о гд а, используя лексикографичеокий порядок, рассмотрим олово W из Mi , для которого ИWit минимальна, и соо твет­ ствующую приведённую связную односвязную диаграмму Д' , гра­ ничный цикл Q ' c /' t р которой имеет метки ^ t Щ * ) * С t ( p ( t ) ш ( / Г * # * ) * , ( р ( & * ( Г * . ф и этом допустим, что количество областей в Л минималь­ но, ^ Пути о< и р> в Д не пересекаются.Действительно, если ъ ! П р > 4 0 , то,полагая < ^ - о , / Ь ~ р , А г с мэтками Щ ьУ ) * f s- Ci , ip ( ы 2 ) $ ( < p (fa jy i * & , } * * М (&й)У4 “ , где 2 s C ,P tG & , в силу ip ( 0 ) 4 4 и V ( * C ) 4 i , имеем, что о 4 и ^ z не являются пустыми Путями. Поэтоцу, разрезал диаграмму Л . в точке пересечения и р с последующи зашиванием границы и склеивая полученные две диа­ граммы по путям о () и / г , получим связную односвязкую диаг­ рамму 2 о граничным циклом <о <4Л 'Г0 , , меткой которого является слово tv — 0< P i 0 ? ~ * в ~ О л Рд ’ P i* из М* .Количество областей в 2 и А одинаково, однако не­ равен ство HWtt < 11W Ц противоречит условию выбора IV . Склеивая пути V и р , из диаграммы 2 получим кольцевую диаграмму А с внешним граничным циклом <5 и внутренним граничным циклом Z , на которых выделим две вершины О и О' соответственно так ,ч то наименьшим путём, соединяющим юс, явля­ е т с я е/ ,