Нормальные базисы и символическая динамика

Актуальность темы

.

Комбинаторика ело? находит свое применение в самых разных разделах математики. Например, в алгебре при изучении базисов и нормальных форм, в алгебраической топологии, в символической динамике. Ряд проблем, относящихся к комбинаторике слов находится на стыке алгебры и теории динамических систем. Многие проблемы комбинаторики слов представляют самостоятельный интерес.

Комбинаторика слов широко используется в задачах комбинаторной теории групп, в теории алгебр Ли, в вопросах бернсайдовского типа и в задачах, связанных с мономиальными алгебрами. Комбинаторная техника, относящаяся к теории групп, развивалась в работах М. Дэна, Е. С. Голода и И. Р. Шафаревича, П. С. Новикова, С. И. Адяна, А. И. Костри-кина, Е. И. Зельманова, И. Рипса, М. Громова, А. Ю. Ольшанского, М. В. Сапира и др.

Е. С. Голод и И. Р. Шафаревич [11], [12] построили конечно порожденную бесконечную периодическую группу (с неограниченной экспонен-той) на основе рассмотрения нормальных форм алгебр и оценки функий роста. П. С. Новиков и С. И. Адян [1] провели детальное исследование свойств периодичности, находящее свое применение в самых разных разделах математики. Ими были впервые построены примеры бесконечных конечно порожденных периодических групп ограниченой экспоненты (т.е. решена проблема Бернсайда), получены наилучшие из известных оценок на экспоненту для таких групп (см. обзор [2]). В дальнейшем был исследован случай четной экспоненты (см. [24], [58]).

В основе замечательных работ М. Громова и А. Ю. Ольшанского также лежит техника диаграмм Ван-Кампена, возникшая в комбинаторной топологии. Подробнее (а также литературу по этой теме) см. в монографии [27].

Комбинаторные соображения, возникшие в символической динамике (автоматные группы), нашли свое применение в работах С. В. Алешина [3, 4, 5] и и Р. И. Григорчука [13], [14], [15] при решении проблемы Мил-нора — посторении групп промежуточного роста (при этом группы Гри-горчука периодичны). Впервые автоматные полугруппы были построены в работах С. В. Алешина. (Изложение примера С. В. Алешина — см. в книге [16]) Автоматные конструкции активно используются в самых разных ситуациях (см. [9], [31], [29], [21]). Возникают они и в данной работе графы Рози).

Комбинаторика слов активно используется в алгебрах Ли, особенно в проблемах бернсайдовского типа [20]. В теории алгебр Ли описание базиса дается в терминах так называемых «правильных слов» (базис Холла-Ширшова). Слово называется правильным если оно лексикографически больше любого его циклически сопряженного (слова циклически сопряо/сены, если г) — щщ, = ЩЩ для некоторых щ и ^2). (А запись слова по циклу используется в теории групп, тесно связанной с теорией алгебр Ли.) Только в правильном слове (причем существуют алгоритмы, делающие это однозначно) можно расставить лиевы скобки так, чтобы при их раскрытии исходное слово оказалось старшим членом получившегося полинома. Тем самым правильные слова задают базис свободной алгебры Ли (базис Линдона-Ширшова) [7]. Применив методы символической динамики (равномерно рекуррентные слова и соображения компактности) Д. Бэкелин установил, что любое сверхслово содержит подслово вида иуи, где и и V — правильные слова, получив, тем самым, короткое доказательство локальной нильпотентности подалгебры алгебры Ли, порожденной сэндвичами, упростив соответствующие работы А. И. Кострикина [31], такое же доказательство независимо было получено А. Д. Чанышевым.

Применив комбинаторное соображение, связанное с невозможностью зацепления правильного слова за самого себя, А. И. Ширшов показал алгоритмическую разрешимость проблемы равенства в алгебрах Ли с одним определяющим соотношением. С помощью комбинаторики слов А. И. Ширшов [35] доказал теорему о свободе подалгебры свободной алгебры Ли. Для супералгебр это обобщили А. А. Михалев [25] и А. С. Штерн [36]. Он показал алгоритмическую разрешимость проблемы равенства для алгебр Ли с одним определяющим соотношением.

Комбинаторика слов активно используется в проблемах бернсайдовского типа, в теории Р/-алгебр, достаточно упомянуть знаменитую теорему Ширшова о высоте [32], [33] утверждающую возможность приведения слов к кусочно периодическому виду.

Теорема А. И. Ширшова о высоте. Пусть, А — конечно порожденная Р1 -алгебра степени т. Тогда существует конечный набор элельен-тов У и число /г € N такие, что, А линейно представима (то есть порождается линейными комбинациями) множеством элементов вида: т = щк1и2к2 — • ¦ игкт, где щ &euro-У и г < к.

При этом в основе оригинальных доказательств А. И. Ширшова (как теоремы о свободе так и теоремы о высоте) лежала техника, связанная с преобразованием алфавита путем подстановок. Эта же техника используется при работе с равномерно-рекуррентными словами и в символической динамике.

Последующие доказательства теоремы о высоте [44] и ее обобщение для алгебр Ли [26] использовали анализ свойств периодичности.

Понятие роста в алгебре является важным комбинаторным инвариантом, ему посвящена монография [59] (см. также [31], [9]). Если размерность пространства, порожденного словами степени не выше п от образующих, А растет как пх, то величина, А называется размерностью Гельфанда-Кириллова алгебры А. Размерность Гельфанда-Кириллова может быть равной 0, 1, а также любому числу > 2, оо или не существовать. То обстоятельство, что она не может принимать промежуточные значения на интервале (1,2) составляет содержание известной теоремы Бергмана. Ассоциативная алгебра размерности Гельфанда-Кириллова О конечномерна. Л. Смолл показал, что ассоциативная алгебра размерности Гельфанда-Кириллова 1 является РТ-алгеброй. Базисы ассоциативных алгебр размерности Гельфанда-Кириллова больше 1 с минимальной функцией роста исследовались в работах А. Т. Колотова [18], [19]. Их описание дается в терминах так называемых последовательностей Штурма находящейся в центре внимания данной работы.

Обобщение понятия роста на бесконечномерный случай является понятие ряда коразмерностей, введенное А. Регевым. Первоначальное доказательство А. Регева об экспоненциальной оценке ряда коразмерности относительно свободных алгебр было улучшено В. Н. Латышевым с помощью оценки числа полилинейных п-разбиваемых слов на основе теоремы Дилуорса [22]. Само же понятие п-разбиваемого слова возникло у А. И. Ширшова в его теореме о высоте. Ряды коразмерности исследовались также в работах В. Н. Латышева, С. П. Мищенко, М. В. Зайцева, А. С1атЬпто. Понятию роста посвящена монография [59].

Комбинаторика слов успешно работает в теории полугрупп. Следует отметить работы Екатеринбургской школы Л. Н. Шеврина, в часности, работы М. В. Сапира, О. Г. Харлампович. Они активно применяли методы символической динамики в теории полугрупп.

В теории мономиальных алгебр комбинаторика слов имеет основополагающее значение и находится в центре внимания работы [9], технику мономиальных алгебр и символической динамики к построению комбинаторной геометрической теории колец активно развивали А. Смоктуно-вич и Е. И. Зельманов.

Структурная теория позволила получить элегантные, но, как правило, неконструктивные доказательства в теории колец. Вместе с тем она оказала несколько тормозящее влияние на развитие непосредственно комбинаторных методов, пусть более трудоемких, но зато позволяющих получать конструктивные оценки и дающих лучшее понимание комбинаторной сути.

Вопросы, связанные с базисами алгебр, приводят изучению бесконечных (в одну или обе стороны) слов или сверхслов. Фундаментальным понятием в теории сверхслов является понятие равномерно-рекуррентного слова, введенное X. Фгорстенбергом [51]. Слово V/ называется равномерно-реккурентнъш, если для каждого подслова V С IV существует натуральное N (v), такое, что для любого подслова и С IV длины не менее, чем.

V является подсловом и. Имеет место следующая Теорема. Пусть IV — бесконечное сверхслово. Тогда существует такое равномерно-рекуррентное слово V/, все подслова которого являются подсловами сверхслова V/.

Эта теорема исключительно важна в комбинаторике слов, поскольку очень часто позволяет свести изучение произвольных слов к изучению равномерно-реккурентных слов.

В терминах равномерно-рекуррентных слов строится теория радикалов мономиальных алгебр ([9]). Мономиальная алгебра называется моно-миально почти простой, если фактор-алгебра, по идеалу, порожденному по любому моному, нильпотентна.

Множество ненулевых слов в почти простой мономиальной алгебре совпадает с множеством всех подслов некоторого равномероно-рекуррентного слова. Пересечение же идеалов с почти простым фактором совпадает с нильрадикалом мономиальной алгебры, а также ее радикалом Джекоб-сона (см. [43]).

В терминах равномерно-рекуррентных слов также получается описание слабо нетеровых мономиальных алгебр. Каждое ненулевое слово слабо нетеровой мономиальной алгебры есть подслово из набора (сверх)слов, удовлетворяющего следующему условию: каждое слово из этого набора либо конечное, либо является бесконечным (односторонними или двухсторонними) словом, которое при выбрасывании некоторого конечного куска распадается на равномерно-рекуррентные части.

Существуют разные подходы к изучению сверхслов:

1. непосредственно комбинаторные свойства слов;

2. графы подслов, или графы Рози].

3. топологическая динамика.

Классическими работами по теории комбинаторики слов являются монографии [62, 63], [68].

Другим инструментом изучения сверхслов является понятие графов подслов или графов Рози. Если? — бесконечное сверхслово над алфавитом А, то к-графом Рози называется граф, вершины которого соответствуют различным подсловам IV длины к. Из вершины в вершинушг ведег стрелка, если максимальный суффикс г<-1 совпадает с максимальным префиксом 1П2, то есть — аи, г^ = гш2, где а, а, 2 € А.

Общий подход, связанный с описанием слов с помощью динамических систем, следующий. Пусть ]? = {и)п} - бесконечное слово. т ({гип}) = {ИЛ1+1} оператор сдвига. Рассмотрим замыкание траектории слова относительно метрики Хэмминга X € А*. Прямые задачи символической динамики связаны с получением информации о динамической системе (.X, т) по информации о слове ИЛ.

Известно, что если слово? равиомерно-рекуррептно, то полученная динамическая система минимальна, то есть не содержит нетривиальных замкнутых инвариантных траекторий.

Также стоит отметить работу [10], изучающую слова, получаемые из взятия дробных частей многочленов со старшим иррациональным коэффициентом в целых точках.

Обратно, пусть имеется дискретная топологическая динамическая система, то есть задано компактное топологическое пространство М, гомеоморфизм /: М -" М и несколько открытых подмножеств.

С/1, С/2,., ип-.

Положим также ип = ми1ищи. иип-1.

Рассмотрим начальную точку х Е М и последовательность итераций х,/(ж),. По этой последовательности можно построить слово ]? = {шп) над алфавитом, А = {а1, аг, • • •, ап} следующим образом: ииг = ак, если /^(ж) е С4. По свойствам динамической системы (размерность множества М, эргодичность) можно получить информацию о слове ?.

Важным примером в изучении сверхслов на основе динамического подхода являются слова с предельной функцией роста.

Хорошо известно, что если функция роста слова V (n) (то есть размерность пространства, порожденного словами степени не выше п) при некотором п удовлетворяет неравенству V (n) < п (п + 3)/2, то алгебра имеет линейный рост.

В работе А. Т. Колотова [18] построены алгебры с «предельной» функцией роста (то есть когда V (ii) = п{п + 3)/2), которые описаны в терминах поворота окружности. А именно, все такие алгебры, кроме счетного множества, строятся как алгебры Ацг, где W = {wi — слово над алфавитом {0,1}, задаваемая иррациональными a, j3 &euro-Е (0,1)): W{ = д (г + 1) — g (i), где д (г) = [а / + ?3]. В комбинаторике слов чаще используется функция сложности Т (гг), равная количеству различных подслов длины п. И, таким образом, V (n) = ^к• Для алгебр функцию сложности корректно будет определить следующим образом: Тд (п) = Va{h) — Уд (п — 1), поскольку алгебра может быть неоднородна.

Известно, что lim^oo Та (п) — п всегда существует. Он может быть равен —оо, С, +оо. Если lim"oo Та (п) — п = —оо, то алгебра, А либо конечномерна, либо имеет медленный рост. JI. Смолл и Д. Бергман исследовали алгебры медленного роста в ряде своих рабог. Суммируя их результаты, получаем описание нормальных базисов таких алгебр.

Назовем алгебру граничной, если lim">00TJ4(n) — п — С. Описание нормальных базисов граничных алгебр следует из теоремы 4.9 и результатов [9].

Слова с предельной функцией роста Т (п) = 77 + 1 образуют класс так называемых слов Штурма (Sturmian words), другое название — слова Бетти, которые впервые были приведены в работе [64] Hedlund, Morse «Symbolic dynamics II. Sturmian trajectories» .

Классическая теория слов Штурма описана в обзорах [47], [60].

К наиболее важным результатам в теории слов Штурма относится так называемая теорема эквивалентности, в которой утверждается эквивалентность трех классов сверхслов над двубуквенным алфавитом:

Теорема эквивалентности. [[64, 47]] Следующие условия на слово W эквивалентны:

1. с./1ово W имеет фунцию сложности Twin) — п + 1/.

2. слово W сбалансированно и иепериодично;

3. слово W порождается системой (S1, С/, Та) с иррациональным углом вращения а.

Последние продвижения в теории слов Штурма описаны в обзоре [48] J. Berstel «Recent results in Sturmian words» .

Естественными обобщениями слов Штурма являются слова с минимальным ростом, то есть слова с функцией роста Т (п) = п + К, начиная с некоторого п. Для двубуквенных алфавитов они носят название квазиштурмовых слов. Слова с функцией роста, удовлетворяющей соотношению Ншп"00 T (ii)/п = 1 изучены в работе [37] A. Aberkane «Words whose complexity satisfies lim p (n)/n = 1» .

Другим обобщением слов Штурма является обобщение, связанное с понятием сбалансированности, а также т-сбалансированности. Сбалансированные непериодические слова над 77-буквенным алфавитом изучены в работе [52] R. L. Graham «Covering the Positive Integers by disjoints sets of the form {na + ?3}: n = 1- 2-.». Построение порождающей динамической системы для сбалансированных непериодических слов является одним из результатов данной работы. Исследование сбалансированных слов тесно связано с построением ненильпотпентных ниль-алгебр (см. 3.9).

Описание периодических сбалансированных слов связано с гипотезой Френкеля (Fraenkel's conjecture), утверждающей, что все сбалансированные периодические слова над алфавитом, А = {ai,., ап} из п символов имеют вид w = (ад00, где Un задается рекуррентно:

Un = (Un-ianUn-i), U3 = aia2aia3aia2ai.

Для 3-х буквенного алфавита гипотеза была доказана Р. Тайдеманом ([71, 72]). В настоящий момент гипотеза доказана для алфавитов, состоящих не более чем из 7 символов.

Продвижение в задачах символической динамики для слов с линейной функцией роста получено в работе [39] P. Arnoux, G. Rauzy «Representation geometrique des suites the complexite 2n +1». В этой работе построена динамическая система для слов с функцией роста Т (п) — 2п + 1, обладающих дополнительным комбинаторным свойством. В работе [69] G. Rote, «Sequences with snbword complexity 2n» в терминах эволюции графов Ро-зи описаны слова с функцией роста 2п.

Одним из основных результатов данной работы является обобщение этих результатов на слова с линейной функцией роста, то есть с функцией роста Т (п) — кп + I, для п > N.

Перекладывания отрезков естественным образом служат обобщением вращения круга. Эти преобразования были введены В. И. Оселедецем [28], следовавшим идее В. И. Арнольда [6], (см. также [17]). Рози [67] впервые показал, что связь между вращениями круга и последовательностями Штурма обобщается, если рассматривать иерекладывания отрезков. В связи с этим (в той же работе) он задал вопрос об описании последовательностей, связанных с перекладываниями отрезков.

Такие последовательности являются еще одним естественным обобщением слов Штурма. В частном случае, для к = 3 отрезков, описание таких последовательностей было получено в работе [54], а в работе [56] были изучены частные случаи последовательностей, порождаемых перекладыванием 4-х отрезков. Стоит также отметить работы [38, 40, 41, 42].

В случае произвольного числа отрезков также получен ряд интересных результатов. В работе [55] получен комбинаторный критерий порождаемое&tradeслов, получаемых симметричным перекладыванием отрезков, то есть перекладыванием, связанным с перестановкой (1 —> к, 2 —> к — 1,., к 1).

В работе [57]независимо от нас получен критерий порождаемости слов преобразованием перекладывания отрезков, удовлетворяющих следующему условию: траектория каждой концевой точки отрезка перекладывания не попадает на концевую отрезка перекладывания, в том числе сама на себя. В этом случае, как не сложно видеть, слова будут иметь функцию сложности Т (п) = (к — 1) п + 1. В данной работе получено полное описание критерия порождаемости слова перекладыванием отрезков, в частности, не требующее выполнения этого условия.

Отметим также, что в приведенных выше работах изучаются перекладывания, не меняющие ориентацию отрезков, а характеристические множества совпадают с отрезками перекладывания. В данной работе с помощью языка графов Рози сначала изучаются слова, порождаемые кусочно-непрерывным преобразованием отрезка, а затем показывается эквивалентность множества таких слов и слов, порождаемых перекладываниями. Этот метод дает возможность описать p.p. слова, связанные с произвольным перекладыванием отрезка, более того, мы не требуем, чтобы характеристические множества, соответсвующие символам алфавита, совпадали с перекладываемыми отрезками.

Цель работы.

Диссертация посвящена исследованию нормальных базисов алгебр медленного роста, а также исследованию взаимосвязи между комбинаторными свойствами слов, цепочками порождающих их автоматов (графов Рози) и порождающими их динамическими системами. Свойства периодичности такаже находятся в центре внимания настоящей работы.

Научная новизна.

Все основные результаты являются новыми и состоят в следующем:

1. Описание нормальных базисов граничных алгебр, то есть алгебр с функцией сложности, асимптотически равной ?? + С.

2. Построение общего критерия порождаемости слова преобразованием перекладывания отрезков в автоматных терминах (решение вопроса, поставленного Рози).

3. Описание множества сбалансированных непериодических слов над произвольным алфавитом в терминах порождающей динамической системы.

Основные методы исследования.

Основными инструментами исследования в работе являются исследование цепочки автоматов (графов Рози), порождающих сверхслово, а также техника подстановок, восходящая к А. И. Ширшову. Мы пользуемся различными результатами теории равномерно-рекуррентных слов и слов Штурма. Также используются результаты эргодической теории (существование инвариантной меры, равномерность иррациональных сдвигов тора).

Практическая и теоретическая ценность.

Работа носит теоретический характер. Результаты диссертации могут быть полезны в комбинаторной теории колец и полугрупп, в частности, при изучении мономиальных алгебр, а также в символической динамике.

Апробация результатов.

Основные результаты диссертации докладывались на следующих семинарах:

1. «Кольца и модули» кафедры высшей алгебры МГУ в 2000;2006 гг.

2. «Арифметика и геометрия» кафедры теории чисел МГУ в 2004;2005г.

3. Dynamics seminar, Einstein Institute of Mathematics, 2004r.

4. Seminar of Weizman Institute of Science, 2004r.

5. «Динамические системы «кафедры дифференциальных уравнений МГУ, 2008 г.

Публикации.

Результаты диссертации опубликованы в следующих работах:

1. Белов А. Я. Чернятьев A. JL, Слова медленного роста и перекладывания отрезков /7 Успехи Л4ат. Наук, 2008, 63:1(379), 159−160.

Чернятьеву А.Л. принадлежат доказательства основных теорем 1 и 2).

2. Чернятьев А. Л., Сбалансированные слова и символическая динамика, Фундаментальная и прикладная математика, Том 13, выпуск 5, 2007 г., стр. 213−224.

3. Чернятьев А. Л., Белов А. Я., Описание слов Штурма над алфавитом из п символов. Математические методы и приложения, 6-й мат. Симп. МГСУ, — Москва, МГСУ, 1999 г., стр. 122−128.

Чернятьеву А.Л. принадлежит построение конструкции динамической системы и доказательство основной теоремы.).

4. Белов А. Я, Чернятьев А. Л., Описание множества слов, порождаемых перекладыванием отрезков // Депонировано в ВИНИТИ, N1048-В2007, 18 стр.

Чернятьеву А.Л. принадлежат доказательства основных теорем 1 и 2.).

5. Чернятьев А. Л. Слова с минимальной функцией роста // Вестник МГУ, том 6, стр. 42−44, 2008 г.

Структура и объем работы.

Диссертация состоит из оглавления, введения, четырех глав и списка литературы, который включает 75 наименований. Объем диссертации составляет 82 страницы.

Благодарности.

Автор глубоко благодарен своим научным руководителям — доктору физико-математических наук Алексею Яковлевичу Белову и доктору физико-матема-тических наук, профессору Александру Васильевичу Михалеву за постановку задач, обсуждение результатов и постоянное внимание к работе.

Автор благодарен за внимание и обсуждение работы доктору физико-математических наук, профессору Виктору Николаевичу Латышеву, доктору физико-математических наук Николаю Германовичу Могцевитину, доктору физико-математических наук Андрею Михайловичу Райгород-скому, доктору физико-математических наук, профессору Юлию Сергеевичу Ильяшенко.

Автор выражает свою отдельную благодарность профессору университета Вайсмана А. Френкелю (А. Ггеапке1) за обсуждение 2-ой главы работы, а также профессору Л. Замбони (Ьиса %атЬош) за обсуждение 4-ой главы работы.

Краткое содержание работы.

Первая глава посвящена обзору и доказательству базовых результатов комбинаторики слов.

Отдельно рассматриваются результаты теории слов Штурма, представлено доказательство теоремы эквивалентности, которое используется в следующих главах. Также доказываются основные результаты из теории графов Рози.

Вторая глава посвящена изучению сбалансированных слов над произвольным алфавитом. Изучаются свойства слов, порождаемых иррациональными сдвигами тора.

Пусть Ш — слово над бинарным алфавитом, порождаемое сдвигом одномерного тора, то есть динамикой (В1,1/, Та, хо).

Обозначим (3 = а/д + т/д, ия = {хдх € С/}, уо = х0/д, где д, г — целые. Несложно показать, что динамика (81, Тр, С/д, у0) порождает то же слово ?. Переход от первой динамики ко второй мы назовем размножением.

Доказана следующая теорема об эквивалентности динамик:

Теорема 1.1 Пусть два слова И7! и порожденные динамиками (В1, Та, II, Х (и (В1,Тр, V, уо) совпадают. Тогда существуютр ид такие, что множества и и V при соответствующих размножениях совпадают с точностью до поворота, т. е. 11р — Т^(Т^) для некоторого 6 > 0.

Далее проводим редукцию от сбалансированного слова Цг над ?7-буквенным алфавитом к п бинарным словам Штурма:

Построим слова И^, • • •, №п над бинарными алфавитами.

М = {оь а!}, А2 = {а2, а2}, • • •, Ап = {а&bdquo-, ап} следующим образом:

Каждому слову Wi соответствует одномерная динамика (S1, Tai, А/, Xi), ее порождающая, следовательно слово W порождается свигом на п-мерном торе с вектором сдвига 7 = (ai,., ап).

Обозначим через М замыкание траектории начальной точки х = (a-i, х2, ¦ ¦ ¦, при действии Т7.

Доказано следующее предложение:

Предложение 1.2 М гомеоморфно множеству S1 х {1,2,., N}.

Теперь видно, что динамика реализуется на множестве М — S1 х {1,2,., VV}, а отображение имеет вид: /: (х, к) (х + а, к + 1 mod N).

Будем понимать под Ui характеристическое множество для символа Oj, которое лежит в замыкании траектории. Пусть также C/f обозначает часть характеристического множества, которое лежит на к-он компоненте связности (окружности) М. Далее изучаются соответствующие характеристические множества.

Основным результатом данной главы является.

Теорема 1.3 Пусть W — сбалансированное непериодическое слово над алфавитом А. Тогда для W существует динамическая cucme.ua (М, f), удовлетворяющая следующим условиям:

1. М = й1 х Ът как топологическое пространство;

2. /: М —> М есть композиция поворота на, а в в1 и сдвига на 1 в.

Длина В1 равна т;

3. Каждая компонента § х {к} к = 1,., п разбита па 2 т дуг: т, красных и т синихвсе красные имеют длину а, все синие 1 — а. красные и синие дуги чередуются;

4. Синий цвет ¦имеет I оттенков, красный — к оттенков, к+1 — А-число букв в алфавите. Все середины дуг даного оттенка образуют вершины правильного многоугольника («правильный 1-угольник» -это точка на окружности," правильный 2-угольник" - пара диаметрально противоположных точек);

5. При переходе от компоненты 8 х {к} к компоненте § х {к + 1} (Б х {т+ 1} = § х {1}^ порядок расположения оттенков внутри красных и синих компонент сохраняется, а сами красные и синие дуги («рулетки») проворачиваются относительно друг друга на 1. Так что преобразование / приводит к смещению на, а относительно красных компонент и на 1 — а (в обратную сторону) относительно синих.

Третья глава посвящена описанию нормальных базисов граничных алгебр, т. е. алгебр, которые связаны с другим обобщенем слов Штурма — словам медленного роста.

Слово? называется ааовом медленного роста, если Ру (п) = п + К, для всех п > N. В словах Штурма Руу{п) = п+1 и Р]у (п + 1) — Р (п) = 1. Естественным обобщением будут слова, для которыхР (п) = п + К, т. е. + 1) — Р (п) = 1 для достаточно больших п.

Показывается, что для каждого такого слова существует граф Рози, соответствующий некоторому слову Штурма. Действительно, если начиная с некоторого п > N выполняется Т (п) — п + К, то это означает, что для каждого п > N в слове Ш существует только одно правое и одно левое специальное слово длины п. То есть в графах Рози таких слов есть одна входящая и одна выходящая развилка, а значит, существует слово Штурма с такой же эволюцией /с-графов, что и данное. Дальше просходит редукция к теореме эквивалентности. Доказана следующая.

Теорема 1.4 Пусть — рекуррентное слово над произволггным конечным алфавитом А. Тогда следующие условия на слово IV эквивалентны:

1. Существует такое натуральное N, что функция рост, а слова W равна 2V (n) = п + К, для п> N и некоторого постоянного натурального К.

2. Существуют такое иррациональное, а и целые щ, по,. пт, что слово W порождается динамической системой (S1,^, I (ll,., IUn, х), где Та — сдвиг окружности на иррациональную величину a, IUiобъединение дуг вида (nja, nj+a).

Для произвольной алгебры, А через Va (ti) обозначается размерность векторного пространства, порожденного мономами длины не больше п, Уа{п) называется функцией роста алгебры А. Пусть Тд (п) = —.

Уа{п— 1). Если алгебра однородна, то Та (п) есть размерность векторного пространства, порожденного мономами длины ровно п, Та (п) называется функцией сложности алгберы А.

Известно (см. [9]) что-либо Нт^-юо (2~л (п) — п) = —оо (в этом случае есть альтернатива: либо limV^(n) = С < оо и тогда dim, А < оо, либо Ул{п>) = 0(п) и алгебра имеет медленный рост)] либо Та{п)—п < Constлибо, наконец, lim,^^ (2л (п) — п) = оо.

В последнем случае рост может быть хаотичным, поэтому для изучения интересны первые два случая. Случай, когда 2л (п) — п < Const (т.е. случай алгебр медленного роста) исследовался Дж. Бергманом и JI. Смоллом. Нормальные базисы для таких алгебр исследованы в работе [9]. Назовем алгебру граничной, если Хл (п) — п < Const.

Описание нормальных базисов граничных алгебр следует из теоремы 1.4 и результатов [9].

Четвертая глава посвящена описанию слов, связанных с перекладыванием отрезков. Рассматриваются случаи, когда ориентация отрезков сохраняется и когда нет. В терминах графов Рози дается комбинаторное описание сверхслов порождающихся перекладыванием отрезков. В центре внимания слова, имеющие функцию роста Тцг{п) — kn +1. Если слово обладает такой функцией роста, то Тцг{п + 1) — Ту{п) = к.

Известно, что если перекладывание к отрезков регулярно, то есть траектория любого из концов отрезков перекладывания не попадает на другой конец любого отрезка, то эволюция любой точки является словом с ростом Tw (n) — кп + I.

Мы ищем условия на слово W, при которых оно порождалось бы преобразованием перекладываний отрезка, не обязательно являющегося регулярным. Отметим, что сдвиг окружности, по сути, является перекладыванием двух отрезков с сохранением ориентации.

Рассмотрим соответствие между подсловами и подмножествами М. Легко видеть, что если начальная точка принадлежит множеству 17 г, то ее эволюция начинается с символа щ. Рассмотрим образы множеств 11 г при отображениях • • •• Ясно, что если точка принадлежит множеству т{~пигп) п т-^Хи^) П. П т^1ик) п и^ то эволюция начинается со слова а^а^ Соответственно, количество различных существенных эволюций длины п + 1 равно количеству разбиений множества М на непустые подмножества границами иод-множств <9С/ги их образами при отображениях f~l, /~2,., /гг+1. Обозначим через 1и множество разбиения, которое соответствует слову и. Ясно, что специальным под словам соответствуют те интервалы, которые делятся образами концов перекладываемых интервалов. Для данного слова и назовем слово V левым (соответственно, правъш) потомком, если и — суффикс (соответственно, префикс) слова V, в соответствии с этим будем называть вершину в (?п левым (соотв. правым) потомком вершины в С?*-, п > к. Прообраз конца интервала может являться граничной точкой только для двух интервалов, соответственно, специальные под-слова могут иметь валентность только равную 2.

Правило 1. Для того, чтобы бесконечное слово? порождалось системой (1,Т, 1/1,., IIк) необходимо, чтобы любое специальное слово имело валентность 2.

Таким образом, мы можем наложить условие на эволюцию графов Рози: начиная с некоторого к все /г-графы Рози имеют входящие и исходящие развилки степени 2. Предположим, что некоторому под слову ги соответствует характеристический интервал, полностью лежащий внутри интервала перекладывания. Пусть точка, А & [0,1] делит на два интервала, образы которых лежат в 1(1к и 1Щ соответственно, а точка В е [0,1] - делит на интервалы, прообразы которых лежат в /йг и 1а соответственно.

Выбор минимального невстречающегося слова, а, значит, удаляемого ребра, определяется взаиморасположением точек, А и В, а также сохранением или сменой ориентации отображения на этих множествах. Итого, имеется 8 вариантов, которые разбиваются на четыре пары, соответствующие одинаковым наборам слов. Например, слову щиюк соответствует ситуация.

В < A, T-[xw, B]) С Iai, T ([xw, А] с Iak).

Введем понятие размеченного графа Рози. Граф Рози называется размеченным, если.

1. Ребра каждой развилки помечены символами I («left») и г («right»).

2. Некоторые вершины помечены символом.

Последователем размеченного графа Рози назовем ориентированный граф, являющийся его последователем как графа Рози, разметка ребер которого определяется по правилу:

1. Ребра, входящие в развилку должны быть помечены теми же символами, как и ребра, входящие в любого левого потомка этой вершины;

2. Ребра, выходящие из развилки должны быть помечены теми же символами, как и ребра, выходящие из любого правого потомка этой вершины;

3. Если вершина помечена знаком «-'», то все ее правые потомки также должны быть помечены знаком «-» .

Замечание. Поясним смысл разметки графа. Пусть ребра входящей развилки соответствуют аги а^, символы /иг соответствуют левому и правому множеству в паре (T (Iai), T (Iaj)). Если символы и а/ соответствуют ребрам исходящей развилки, то символы I и г ставятся в соответствии с порядком «лево-право» в паре (Iak, Iai). Знак «-» ставится в вершине, если характеристическое множество, ей соответствующее, принадлежит интервалу перекладывания, на котором меняется ориентация.

Условие для перехода от графа Gn к Gn+i;

Правило 2.

1. Если в графе нет двойных развилок, соответствующих биспециаль-ным подсловам, то при переходе от Gn к Gn+1 имеем Gn+i = D{Gn).

2. Если вершина, соответствующая бисиециальному слову не помечена знаком то ребра, соответствующие запрещенным словам выбираются из пар 1 г и rl.

3. Если вершина помечена знаком «-», то удаляемые ребра должны выбираться из пары И или гг.

Назовем эволюцию размеченных графов Рози правильной, если правила 1 и 2 выполняются для всей цепочки эволюции графов, начиная с Сг1, назовем эволюцию асимптотически правильной, если правила 1 и 2 выполняются, начиная с некоторого С? п. Будем говорить, что эволюция размеченных графов Рози ориентирована, если в /с-графах нет вершин, помеченных знаком «-» .

Теорема 1.5 Равномерно-рекуррентное с. аовоЛ?

1. Порождается перекладыванием отрезков, тогда и только тогда, когда слово обеспечивается асимптотически правильной эволюцией размеченных графов Рози.

2. Порождается перекладыванием отрезков с сохранением ориентации тогда и только тогда, когда слово обеспечивается асимптотически правильной ориентированной эволюцией размеченных графов Рози.

1. С. И. Адян. Проблема Бернсайда и тождества в группах // М., Наука, 1975.

2. С. И. Адян, А. А. Разборов Периодические группы и алгебры Ли. Успехи мат. наук, 1987, т. 42, по 2, стр. 2−68.

3. С. В. Алешин, О свободной группе конечного автомата.//Вестник Моск. Унив. Сер 1. Мат. и Мех.1983, № 4, 12−14.

4. С. В. Алешин, О суперпозициях автоматных отображений // Кибернетика, Киев, 1975, № 1, 29−34.

5. С. В. Алешин, Конечные автоматы и проблема Бернсайда для периодических групп // Мат. Заметки 11 (1972), 319−328.

6. В. И. Арнольд, Малые знаменатели и проблемы устойчивости движения в классической и небесной механике// Успехи Мат. Наук, 1963, 18:6(114), стр. 91−192.

7. Ю. А. Бахтурин, Тождества в алгебрах Ли // Москва, Наука, 1985, 448 стр.

8. А. Я. Белов, Классификация слабо нетеровых мономиальных ал-геб // Фунд. и прикл. мат. 1995.-1., т1,№ 4, -С. 1085−1089.

9. А. Я. Белов, В. В. Борисеико, В. Н. Латышев, Мономиальные алгебры // Итоги науки и техники. Совр. Мат. Прил. Тем. Обзоры т. 26 (алг. 4), М. 2002. 35−214.

10. А. Я. Белов, Г. В. Кондаков, Обратные задачи символической динамики // Фундаментальная и прикладная математика, Т1, № 1, 1995, Т. 1, № 1. 71−79.

11. Е. С. Голод, И. Р. Шафаревич О башне полей классов. Изв. АН СССР. Сер. мат., 964, т. 28, по 2, стр. 261−272.

12. Е. С. Голод, О нильалгебрах и финитно-аппроксимируемых р-группах. Изв. АН СССР. Сер. мат., 1964, т. 28, по 2, стр. 273−276.

13. Р. И. Григорчук, К проблеме Милнора о групповом росте. Докл. АН СССР, 1983, т. 271, № 1, стр. 53−54.

14. Р. И. Григорчук, Степени роста конечно порожденных групп и теория инвариантных средних. Изв. АН СССР. Сер. мат., 1984, т. 48, по 5, стр. 939−985.

15. Р. И. Григорчук, О рядах Гильберта-Пуанкаре градуированных алгебр, ассоциированных с группами. Мат. сб., 1989, т. 180, по 2, стр. 207−225.1G. М. И. Каргаполов, Ю. И. Мерзляков, Основы теории групп, (Зе изд., Наука, 1982) 288стр.

16. А. Б. Каток, А. М. Степин, Аппроксимации в эргодической теории // Успехи Мат. Наук, 1967, 22:5(137), 81−106.

17. А. Т. Колотов, Апериодические последовательности и функции роста в алгебрах // Алгебра и логика, 20 (1981), 138−154, 250.

18. А. Т. Колотов, Алгебры и группы с периодической функцией роста // Алгебра и логика, 19 (1980), 659−668, 745.

19. А. И. Косгрикин Вокруг Бернсайда. — М.: Наука, 1986, 232 стр.

20. В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин, Введение в теорию автоматов // Москва, «Наука», 1985. 320 стр.

21. В. Н. Латышев, К теореме Регева о тождествах тензороного произведения Р/-алгебр // Успехи матем. наук, 1972, т. 27, № 4, стр. 213−214.

22. Р. Линдон, П. Шупп, Комбинаторная теория групп // М., Мир, 1980.

23. И. Г. Лысёнок, Бесконечность бернсайдовых групп периода 2к при к > 13 // УМН, 1992, 47:2(284), 201−202.

24. А. А. Михалёв Подалгебры свободных цветных супералгебр Ли // Мат. заметки.- 1985.-Т. 37, № 5.-С. 653−661.

25. С. П. Мищенко, Вариант теоремы о высоте для алгебр Ли. Мат. заметки, 1990, -7, по 4, стр. 83−89.

26. А. Ю. Ольшанский Геометрия определяющих соотношений в группах, сер. Соврем.алгебра. М.: Наука, 1989, 447 стр.

27. В. И. Оселедец, О спектре эргодических автоморфизмов // ДАН СССР, 1966, 168, 1009−1011.

28. А. Саломаа, Жемчужины формальных языков. — М.: Мир, 1986, 159 стр.

29. Я. Г. Синай, Введение в эргодическую теорию // М.: ФАЗИС, 1996. 144 с.

30. В. А. Уфнаровский Комбинаторные и асимптические методы в алгебре // Итоги науки и тех. Серия Совр. Пробл. Мат. Фунд. направл. М. ВИНИТИ. 1990; 57, стр 5−177. (РЖМат, 1990).

31. А. И. Ширшов, О некоторых неассоциативных ниль-кольцах и алгебраических алгебрах. Мат. сб., 1957, т. 41, по 3, 381−394.

32. А. И. Ширшов, О кольцах с тождественными соотношениями. Мат. сб., 1957, т. 43, по 2, стр. 277−283.

33. А. И. Ширшов О свободных кольцах Ли. Мат. сб., 1958, т. 45, по 2, стр. 113−122.

34. А. И. Ширшов, О базах свободной алгебры Ли. Алгебра и логика, 1962, т. 1, н. 1, стр. 14−19.

35. А. С. Штерн, Свободные супералгебры Ли // Сиб. мат. журн.—1986.—Т. 27, стр. 170—174.

36. A. Aberkane, Words whose complexity satisfies lim p (n)/n = 1 // Theor. Сотр. Sci., 307, (2003), 31−46.

37. P. Ambro z, L. Hakov E. Pelantov&, Properties of 3iet preserving morphisms and their matrices / / Proceedings WORDS 2007, Eds. P. Arnoux, N. Bedaride, J. Cassaigne, (2007), 18−24.

38. P. Arnoux and G. Rauzy 1991], Representation geometrique des suites the complcxite 2n + 1 // Bull. Soc. Math. France 119, 199 215.

39. P. Balazi, Infnite Words Coding Three-Interval Exchange // diploma work CTU (2003).

40. M. Morse, G. A. Hedlund 1940], Symbolic dynamics II. Sturmian trajectories, // Amer. J. Math. 62, 1−42.

41. G. Rauzy, Suites a ternies dans un alphabet fini //In Semin. Theorie des Nombres, p. 25−01−25−16, 1982;1983, Expose No 25.

42. G. Rauzy, Echanges d’intervalles et transformations induites, (in French), Acta Arith. 34 (1979), p. 315−328.

43. G. Rozenberg and A. Salomaa // The Mathematical Theory of L Systems, Academic Press, New York etc., 1980.

44. G. Rote, Sequences with subword complexity 2n // J. Number Theory 46 (1994) 196−213.

45. A. Salomaa. Jewels of Formal Language Theory // Computer Science Press, 1981.

46. R. Tijdeman, Decomposition of the integers as a direct sum of two subsets // in: Number Theory, ed. by S. David, Number Theory Seminar Paris 1992;93, Cambridge University Press, (1995), 261−276.

47. R. Tijdeman, Fraenkel’s conjecture for six sequences // Discrete Mathematics, Volume 222, Issue 1−3, 223 234, 2000.

48. L. Vuillon, Balanced words // Bull. Belg. Math. Soc. Simon Stevin 10 (2003), no. 5, 787−805.

49. L. Vuillon, A characterization of Sturmian word by return words // European Journal of Combinatorics (2001) 22, 263−275.

50. H. Weyl, Uber der gleichverteilung von zahlen mod 1, // Math. Ann., v. 77, 313−352, 1916.