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

ЛЕММА 7 . Если уравнение^ Х п- А имеет решение, то для минимального решения (лгУХ ,п ) одного из соответствующих ему уравнений ( 3 ' ) можно эффективно установить верхнюю грани­ цу длины представления слова X 6Gr+ , ДОКАЗАТЕЛЬСТВО. Случай I . Пусть X - не дельта сопря­ женно периодическое олово. Тогда имеем две возможности: а) , Приведем WL _ н нормальной_форме. Пусть A2rn‘Wt = А а< W( , где W/t £ СХ я W; не со­ держит Л. В соотношенйи № Х Т = А ° Щ (7) левая часть является элементом __£* . По теореме Гарсайда d i ^ O . Если представление W , = Н Х ’ .. Н ^ , где д а ' 9 , ~2г% т° +2та ддд некоторого фиксированного М , то длина . редставления X меньше + 2т0 . Действительно , ИВ леммы (6) сл едует, что, если длина представления основы X не иеиъше_2тоМ<1)т°+2т0 , то V n tM . длина представления основы Хп будет больше о (М+0то- > ,„4 , 2 т 0 > 9 , - , что противоречит ( 7 ) . ■ в) У '10 . Тогда ( л Ч Х ) п = й гп>1Х , перепишем в виде Х П= й г ¥ п ^ т , w . ___ Приведем Щ к нормальной форме №\ - &pL И/* . Тогда Х гп - /ХЫ^п+3rnSPi Wi ■ ( 8 ) Так как Х п с С + , то по теореме Гароайда 2luln+2m, +pt >о. Если длина представления WL не больше 2 Ш о ‘ +2та для некоторого М . то даьша представления основы X не боль­ ше 2 т $ Мт°*,К 2 т 0 . Случай 2. X ' - дельта сопряженно периодическое слово. Тогда длина представления основг X не превосходит + 2 гп0 . Займемся изучением решений уравнений вида ( 3 ' ) . ЛШ.5А 8 . Пусть (дгУ Х ,п ,) , ( Л ^ л г ) - два решения оддаого,из уравнений ( 3 ' ) . Тогда, если X неприводимо, то - 7G