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

где к « Z , Ik l * п . - / . Д о к а з а т е л ь с т в о . Проведен индукцию по числу п. При п_~ { утвер;;н(онио леммы очевидно. O ciiobhjto трудность представляет случай n.~z . Действительно, при п>2 имеем: е f/7>J = е({£ k j * u n) = e ( f ' u j + е{и/ь)+3к; * ( & * < ) /к , 1 * 1 , / k J * n - 2 . Отсюда ^ 6 ( £ u‘) +**i к ~к,+к± - \кЫ пч . Итак, необходимо доказать формулу: . t ( a v ) ~ e ( u )+ e ( v - )+ i k , lkl=f. ( I ) Пусть слово U является нормально!! формой элемента и. , а слово V - нормальной формой эломопта V~ . Возможны случаи: 1. Слово U V /шляется нормально!! формой. Тогда очевидно, что £ ( tr tv ~ ) - е ( и ) + е ( v ) t формула (I) верна при к =о. 2. U s L U , V , где V - нормальная форма элемента v / . Тогда e ( u v ) =е ( ( / , ) щ По е (и )= e ( V ,) + е (V )= е ( и .г ~ ) - е (гг). Следовательно, &(и гг) =е (и ) +e(ir), Формула (I) верна при к~0 . ■3. V si U V{ , где V / - нормальная форма элемента и v . Этот случай разбирается полностью аналогично случаю 2. 4, Предположим, что с л у ч а и !, 2 и 3 но имоют моста. Тогда и ° и , у 6Т , V r T i f ^ V n ( 2 ) где £ е {±1 } , SI Т - нормальная форма элемента Т ' . Действительно* пусть Т - максимальное по длине слово такое, что имеют место равенства U i l U ' T - , V к T V ' , Т - нормальная форма элемента Т~* . То 1 ’да слова С!' ц V ' не пусты. Это вытекает из того, что случаи 2 и 3 не имоют места. Слово V но мокот оканчиваться буквой х . Докажем это. Если слово V ока 1 гч!шается букво!! х , а слово Т пусто, то в ciury того, что не имеет моста случай I , слово V должно начинаться с буквы х . Это противоречит максимольнос- ти слова Т по длине. Если :::е слово U ‘ оканчивается буквой , а слово Т не пусто, то слово Т должно начинаться с буквы у в некоторой степени ? £ i - l \ . Тогда слово I - ; i % -