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

Лемма 6. Пусть в диаграмме М, с граничной меткой (ДдМ) a w" есть длинная полоса П, тогда существует соотношение, удовлетворяющее заключе­ нию теоремы 1 . к Доказательство. Пусть П = ( J Dt . Рассмотрим циклическую перестанов- Ы ку слова w -w * такую, что её начало совпадает с началом полосы П. Здесь воз­ никает необходимость в рассмотрении двух случаев. I. Начало слова w* не является первичной вершиной. 1.1. Пусть w* г <p((dD\ и D2 и . . . < j D„) n dM)v, где 2 <т< к- 2 и <p(dDm+lr\ дМ) ш 1 ч>'и v '- начало слова w*. Пусть для определенности т = к-2. Подклеив экземпляр полосы П к границе дМ диаграммы М , начиная с куска v ' dDm+ 1 , получим либо противоречие с условием Т(4), либо слова из R сократи­ мы. 1.2. Пусть и>* a <p((3D]иЗДги . . . u3D*./) n 8M)v, где qtdDkr^ дМ) a w ', причем w* = v'w". Пусть <р(д П \ дМ)л = и. Рассмотрим диаграмму М\ с гранич­ ной меткой cfidMi) в (и 'и )'", где ил и '~ (w*)2. Рассуждая как при доказательст­ ве леммы 3, получим, что | Mi\ = 1 и ( и [иУт е R. 1.3. Пусть w* = <p((dD{<udD 2 <J . . . u3Dt) п дМ) и пусть /ДдП \ ЗА /)'1 а и. Перейдем к слову (и)" = 1, где и ~ w в группе G. В силу специфики расположе­ ния полосы П в диаграмме М, ясно, что ||и|| < ||и>|| и, следовательно, по индук­ тивному предположению имеет место утверждение теоремы. II. Начало слова w* - первичная вершина. 11.1. Пусть w* = <o((3D| kj D j U . . . u£>m) гл ЗА/), где 2< т <к-2. Пусть т=к-2. Здесь проводим рассуждения, как и в п. 1.1. 11.2. Пусть и1* = ( o ((3D|U3D2 u . . . иЭДи) п дМ). 11.2.1. \<p(dDkr\ дМ) | < \<p(dD, n дМ)\. В этом случае получаем либо М Я Ь П ЭЛ/)|| = 1, что противоречит условию С(4), либо <p(dDk) = (fidD\) — сло­ ва с общим началом <p(dDk п дМ), но тогда полосу П можно подклеить на гра­ ницу диаграммы А/, что противоречит условиям, наложенным на полосы. 107