Нормальные базисы и символическая динамика тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Чернятьев, Александр Леонидович
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2008
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М В ЛОМОНОСОВА
Механико-математический факультет
На правах рукописи УДК 512+519 17
Чернятьев Александр Леонидович Нормальные базисы и символическая динамика
01 01 06 — математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
/
003449 1Б9
Москва —
2008
003449169
Работа выполнена на кафедре высшей алгебры Механико-математического факультета Московского государственного университета имени М В Ломоносова
Научные руководители: доктор физико-математических наук
А Я Белов
доктор физико-математических наук, профессор А В Михалев
Официальные оппоненты- доктор физико-математических наук,
профессор И Б Кожухов,
(Московский институт электронной техники),
доктор физико-математических наук, профессор А А Михалев,
(Московский государственный университет
имени М В Ломоносова)
Ведущая организация: Тульский государственный
педагогический университет имени Л Н Толстого
Защита диссертации состоится 31 октября 2008 г в 16 ч 40 мин на заседании диссертационного совета Д 501 001 84 при Московском государственном университете имени М В Ломоносова по адресу Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д 1, Московский Государственный Университет имени М В Ломоносова, Механико-математический факультет, аудитория 14-08
С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж)
Автореферат разослан 30 сентября 2008 г
Ученый секретарь диссертационного совета Д 501 001 84 в МГУ доктор физико-математических наук, профессор
А О Иванов
Общая характеристика работы Актуальность темы
Комбинаторика слов находит свое применение в самых разных разделах математики Например, в алгебре при изучении базисов и нормальных форм, в алгебраической топологии, в символической динамике Ряд проблем, относящихся к комбинаторике слов находится на стыке алгебры и теории динамических систем Многие проблемы комбинаторики слов представляют самостоятельный интерес
Комбинаторика слов широко используется в задачах комбинаторной теории групп, в теории алгебр Ли, в вопросах бернсайдовского типа и в задачах, связанных с мономиальными алгебрами Комбинаторная техника, относящаяся к теории групп, развивалась в работах М Дэна, Е С Голода и И Р Шафаревича, П С Новикова, С И Адяна, А И Кострикина, Е И Зельманова, И Рипса, М Громова, А Ю Ольшанского, М В Сапира и др
Е С Голод и И Р Шафаревич3 построили конечно порожденную бесконечную периодическую группу (с неограниченной экспонентой) на основе рассмотрения нормальных форм алгебр и оценки функий роста П С Новиков и С И Адян2 провели детальное исследование свойств периодичности, находящее свое применение в самых разных разделах математики Ими были впервые построены примеры бесконечных конечно порожденных периодических групп ограниченой экспоненты (те решена проблема Бернсайда), получены наилучшие из известных оценок на экспоненту для таких групп В дальнейшем был исследован случай четной экспоненты
В основе замечательных работ М Громова и А Ю Ольшанского3 также лежит техника диаграмм Ван-Кампена, возникшая в комбинаторной топологии
Комбинаторные соображения, возникшие в символической динамике (автоматные группы), нашли свое применение в работах С В Алешина4 и Р И Григорчука5 при решении проблемы Милнора - построении групп промежуточного роста (при этом группы Григорчука периодичны) Впервые автоматные полугруппы были построены в работах С В Алешина (
1 Голод Е С , Шафаревич И Р О башне полей классов Иэв АН СССР Сер мат, 964, т 28, по 2, стр 261-272
2 Адян С И , Проблема Бернсайда и тождества в группах // М , Наука, 1975
3 Ольшанский А Ю Геометрия определяющих соотношений в группах сер Соврем алгебра. М Наука, 1989, 447 стр
4 Алешин С В , О суперпозициях автоматных отображений // Кибернетика, Киев, 1975, N1, 29-34
Алешин СВ, О свободной группе конечного автомата.//Вестник Моек У нив Сер 1 Мат и
Мех 1983, N4, 12-14
5Григорчук Р И К проблеме Милнора о групповом росте Докл АН СССР, 1983, т 271, N1, стр 53-54
Г\
изложение примера С В Алешина - см в книге6) Автоматные конструкции активно используются в самых разных ситуациях Возникают они и в данной работе (графы Рози)
Комбинаторика слов активно используется в алгебрах Ли, особенно в проблемах бернсайдовского типа7 В теории алгебр Ли описание базиса дается в терминах так называемых "правильных слов" (базис Линдона-Ширшова) Слово называется правильным если оно лексикографически больше любого его циклически сопряженного (слова VI, циклически сопряжены, если Ух = 1411/2, = ЩЩ для некоторых щ и иг) (А запись слова по циклу используется в теории групп, тесно связанной с теорией алгебр Ли ) Только в правильном слове (причем однозначно) можно расставить лиевы скобки так, чтобы при их раскрытии исходное слово оказалось старшим членом получившегося полинома Тем самым правильные слова задают базис свободной алгебры Ли (базис Холла-Ширшова8) Применив методы символической динамики (равномерно рекуррентные слова и соображения компактности) Д Бэкелин установил, что любое сверхслово содержит подслово вида иуи, где и и и - правильные слова, получив, тем самым, короткое доказательство локальной нильпотентности подалгебры алгебры Ли, порожденной сэндвичами, упростив соответствующие работы В А Уфнаровского9
Применив комбинаторное соображение, связанное с невозможностью зацепления правильного слова с самим собой, А И Ширшов показал алгоритмическую разрешимость проблемы равенства в алгебрах Ли с одним определяющим соотношением
С помощью комбинаторики слов А И Ширшов10 доказал теорему о свободе подалгебры свободной алгебры Ли Для супералгебр это обобщили А А Михалев11 и А С Штерн 12
Комбинаторика слов активно используется в проблемах бернсайдовского типа, в теории Р1-алгебр, достаточно упомянуть знаменитую теорему Ширшова о высоте13, утверждающую возможность приведения слов к кусочно периодическому виду
Теорема А И.Ширшова о высоте. Пусть А - конечно порожденная Р1-алгебра степени т Тогда существует конечный набор элементов У и
6 Каргаполов М И , Мерзляков Ю И Основы теории групп, (Зе изд, Наука, 1982) 288стр
7 Кострикин А И Вокруг Бернсайда — М Наука, 1986, 232 стр
8 Бахтурин Ю А , Тождества в алгебрах Чи // Москва, Наука, 1985, 448 стр
9 Уфнаровский В А Комбинаторные и асимптотические методы в алгебре // Итоги науки и тех Сер Совр Пробл Матем Фунд направл М ВИНИТИ 1990, т 57, стр 5-177 (РЖМат, 1990)
10 Ширшов А И О базах свободной алгебры Ли Алгебра и логика, 1962, т 1, по 1, стр 14-19
11 Михалев А А Подалгебры свободных цветных супералгебр Ли // Мат заметки, 1985, т 37, N 5 стр 653-661
12 Штерн А С Свободные супералгебры Ли // Сиб мат журн 1986, т 27, стр 170-174
13 Ширшов А И О некоторых неассоциативных ниль-кольцах и алгебраических алгебрах Мат сб , 1957, т 41, по 3, 381-394
число h € N такие, что А линейно представима (то есть порождается линейными комбинациями) множеством элементов вида
W — uikíu2k2 uTkr, где иг eY иг < h
При этом в основе оригинальных доказательств А И Ширшова (как теоремы о свободе так и теоремы о высоте) лежала техника, связанная с преобразованием алфавита путем подстановок Эта же техника используется при работе с равномерно-рекуррентными словами и в символической динамике
Последующие доказательства14 теоремы о высоте и ее обобщение15 для алгебр Ли использовали анализ свойств периодичности
Понятие роста в алгебре является важным комбинаторным инвариантом, ему посвящена монография Краузе и Ленагана16 Если размерность пространства, порожденного словами степени не выше п от образующих А растет как пх, то величина Л называется размерностью Гельфанда-Кириллова алгебры А Размерность Гельфанда-Кириллова может быть равной 0, 1, а также любому числу > 2, оо или не существовать То обстоятельство, что она не может принимать промежуточные значения на интервале (1,2) составляет содержание известной теоремы Берглшна Ассоциативная алгебра размерности Гельфанда-Кириллова 0 конечномерна Л Смолл показал, что ассоциативная алгебра размерности Гельфанда-Кириллова 1 является -Р/-алгеброй Базисы ассоциативных алгебр размерности Гельфанда-Кириллова больше 1 с минимальной функцией роста исследовались в работах А Т Колотова17 Их описание дается в терминах так называемых последовательностей Штурма, находящихся в центре внимания данной работы
Обобщение понятия роста на бесконечномерный случай является понятие ряда коразмерностей, введенное А Регевым Первоначальное доказательство А Регева об экспоненциальной оценке ряда коразмерности относительно свободных алгебр было улучшено В Н Латышевым18 с помощью оценки числа полилинейных n-разбиваемых слов на основе теоремы Дилу-орса Само же понятие п-разбиваемого слова возникло у А И. Ширшова в его теореме о высоте Ряды коразмерности исследовались также в работах В Н Латышева, С П Мищенко, М В Зайцева, А Джамбруно
14 Belov, A Some estimations for nilpotence of mi-algebras over a field of an arbitrar} characteristic and height theorem // Communications m algebra, 20 (10) 2919-2922, 1992
15 Мищенко С П , Вариант теоремы о высоте для алгебр Ли Мат заметки, 1990, ,7, по 4, стр 83-89
16 Krause, G , Lenagan, Т Н Growth of algebra and Gelfand-Kinllov dimension // Research Notes m Math , Pitman, London, 1985
17 Колотое AT, Апериодические последовательности и функции роста в алгебрах // Алгебра и логика, 20 (1981), 138-154, 250 ,
Колотое А Т, Алгебры и группы с периодической функцией роста // Алгебра и логика, 19 (1980), 659-668, 745
18 Латышев В Н , К теореме Регева о тождествах тензороного произведения PI-алгебр // Успехи матем наук, 1972, т 27, N4, стр 213-214
Комбинаторика слов успешно работает в теории полугрупп Следует отметить работы Екатеринбургской школы JI H Шеврина, в часности, работы M В Сапира, О Г Харлампович Они активно применяли методы символической динамики в теории полугрупп
В теории мономиальных алгебр комбинаторика слов имеет основополагающее значение и находится в центре внимания работы19
Структурная теория позволила получить элегантные, но, как правило, неконструктивные доказательства в теории колец Вместе с тем она оказала несколько тормозящее влияние на развитие непосредственно комбинаторных методов, пусть более трудоемких, но зато позволяющих получать конструктивные оценки и дающих лучшее понимание комбинаторной сути Вопросы, связанные с базисами алгебр, приводят изучению бесконечных (в одну или обе стороны) слов или сверхслов Фундаментальным понятием в теории сверхслов является понятие равномерно-рекуррентного слова, введенное X Фюрстенбергом20 Слово W называется равномерно-реккурентным, если для каждого поделова v С W существует натуральное N(v), такое, что для любого поделова и <z W длины не менее, чем N(v), v является подсловом и Имеет место следующая
Теорема Пусть W - бесконечное сверхслово Тогда существует такое равномерно-рекуррентное слово W, все поделова которого являются под-словами сверхслова W
Эта теорема исключительно важна в комбинаторике слов, поскольку часто позволяет свести изучение произвольных слов к изучению равномерно-реккурентных слов
В терминах равномерно-рекуррентных слов строится теория радикалов мономиальных алгебр Мономиальная алгебра называется мономиально почти простой, если фактор-алгебра по идеалу, порожденному по любому моному, нильпотентна
Множество ненулевых слов в почти простой мономиальной алгебре совпадает с множеством всех подслов некоторого равномероно-рекуррентного слова
Пересечение же идеалов с почти простым фактором совпадает21 с нильрадикалом мономиальной алгебры, а также с ее радикалом Джекобсона
В терминах равномерно-рекуррентных слов также получается описание слабо нетеровых мономиальных алгебр Каждое ненулевое слово слабо нетеровой мономиальной алгебры есть подслово из набора (сверх)слов, удовлетворяющего следующему условию каждое слово из этого набора либо конечное, либо является бесконечным (односторонними или двухсторонни-
19 Белов А Я , Борисенко В В , Патышев В H , Мономиальные алгебры // Итоги на>ки и техники Совр Мат Прил Тем Обзоры т 26 (алг 4), M 2002 35-214
20 Furstenberg H , Poincaré reccurence and number theory // Bull Amer Math Soc , 5 211-234, 1981
21 Belov, A, Gateva-Ivanova, T , Radicals of monomial algebras // Proceedings of Taiwan-Moscow Algebra Workshop, С 159-169, 1994
ми) словом, которое при выбрасывании некоторого конечного куска распадается на равномерно-рекуррентные части
Существует разные подходы к изучению сверхслов
1 непосредственно комбинаторные свойства слов,
2 графы подслов, или графы Рози,
3 топологическая динамика
Классическими работами по теории комбинаторики слов являются монографии Лотер22, а также Розенберга и Саломаа23
Другим инструментом изучения сверхслов является понятие графов подслов или графов Рози Если W - бесконечное сверхслово над алфавитом А, то к-графом Рози называется граф, вершины которого соответствуют различным подсловам W длины к Из вершины u>i в вершину w2 ведет стрелка, если максимальный суффикс wi совпадает с максимальным префиксом w2, то есть w 1 = a\u, w2 = ua2, где ai, а2 S А
Общий подход, связанный с описанием слов с помощью динамических систем, следующий Пусть W = {wn} - бесконечное слово т({гип}) = {k;,1+i} - оператор сдвига Рассмотрим замыкание траектории слова относительно метрики Хэмминга X £ А* Прямые задачи символической динамики связаны с получением информации о динамической системе (X, т) по информации о слове W
Известно, что если слово W равномерно-рекуррентно, то полученная динамическая система минимальна, то есть не содержит нетривиальных замкнутых инвариантных траекторий
Также стоит отметить работу Белова и Кондакова24, изучающую слова, получаемые из взятия дробных частей многочленов со старшим иррациональным коэффициентом в целых точках
Обратно, пусть имеется дискретная топологическая динамическая система, то есть задано компактное топологическое пространство М, гомеоморфизм / М->Ми несколько открытых подмножеств
Ui,U2, ,Un-i
Положим также
Un = M\Uil>U2\J U [/„_!
22 М Lothaire, Combinatorics on Words // Encyclopedia of Mathematics and its Applications, Addison-Wesley, Reading, MA, 1983, Vol 17
13 Rosenberg, G , Salomaa, A // The Mathematical Theory of L Sjstems, Academic Press, New York etc, 1980
24 Белов А Я , Кондаков Г В , Обратные задачи символической динамики // Фундаментальная и прикладная математика, Т 1, N1 71-79
Рассмотрим начальную точку х € M и последовательность итераций х, f(x), По этой последовательности можно построить слово W = {wn} над алфавитом А = {ai,a2, ,ап} следующим образом wt = а^, если f^\x) € f/jt По свойствам динамической системы (размерность множества М, эргодичность) можно получить информацию о слове W
Важным примером в изучении сверхслов на основе динамического подхода являются слова с предельной функцией роста
Хорошо известно, что если функция роста слова V(n) (то есть размерность пространства, порожденного словами степени не выше п) при некотором п удовлетворяет неравенству V(n) < n(n + 3)/2, то алгебра имеет линейный рост
В работе Колотова25 построены алгебры с "предельной" функцией роста (то есть когда V(n) = п(п + 3)/2), которые описаны в терминах поворота окружности А именно, все такие алгебры, кроме счетного множества, строятся как алгебры Aw, где W = {wt} - слово над алфавитом {0,1}, задаваемая иррациональными a,ß G (0,1)) wt = д(г+1)—д(г), где р(г) = [аг+/3] В комбинаторике слов чаще используется функция сложности Т(п), равная количеству различных подслов длины п И, таким образом, V(n) = Т). Для алгебр функцию сложности корректно будет определить следующим образом Тдп = VA{n) — Va{ti — 1), поскольку алгебра может быть неоднородна
Известно, что lim^go Тд(п) — п всегда существует Он может быть равен —оо, С, +00 Если lim^oo Тд(п) — п = —со, то алгебра А либо конечномерна, либо имеет медленный рост JI Смолл и Д Бергман исследовали алгебры медленного роста в ряде своих работ Суммируя их результаты, получаем описание нормальных базисов таких алгебр
Назовем алгебру граничной, если lim„_с» Тд(п) — п = С Описание нормальных базисов граничных алгебр является одной из целей данной работы
Слова с предельной функцией роста Т{п) = п + 1 образуют класс так называемых слов Штурма (Sturmian words), другое название - слова Бетти , которые были приведены в работе Морса и Хедлунда26 Классическая теория слов Штурма описана в обзоре Берстей и Сэбол27
К наиболее важным результатам в теории слов Штурма относится так называемая теорема эквивалентности, в которой утверждается эквивалентность трех классов сверхслов над двубуквенным алфавитом
25 А Т Колотое, Апериодические последовательности и функции роста в алгебрах // Алгебра и логика, 20 (1981), 138-154, 250
26 Morse,M , Hedlund G A [1940J, Symbolic dynamics II Sturmian trajectories, // Amer J Math 62, 1-42
27 Berstel.J , Séébold, P, Sturmian words, in M Lothaire (Ed ) // Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, Vol 90, Cambridge University Press, Cambridge, 2002 (Chap 2)
Теорема эквивалентности Следующие условия на слово W эквивалентны
1 слово W имеет фунцию сложности Тцг(п) = n 4- 1,
2 слово W сбалансированно и непериодично,
3 слово W порождается системой (S1, U,Ta) с иррациональным углом вращения а
Последние продвижения в теории слов Штурма описаны в обзоре Бер-стей28 Естественными обобщениями слов Штурма являются слова с минимальным ростом, то есть слова с функцией роста Т(п) = п + К, начиная с некоторого п Для двубуквенных алфавитов они носят название квазиштурмовых слов Слова с функцией роста, удовлетворяющей соотношению lim^oo Т(п)/п = 1 изучены в работе Аберкейн29
Другим обобщением слов Штурма является обобщение, связанное с понятием сбалансированности, а также тп-сбалансированности Сбалансированные непериодические слова над n-буквенным алфавитом изучены в работе Грехема30 Построение порождающей динамической системы для сбалансированных непериодических слов является одним из результатов данной работы Исследование сбалансированных слов тесно связано с построением ненильпотнентных ниль-алгебр
Описание периодических сбалансированных слов связано с гипотезой Френкеля (Fraenkel's conjecture), утверждающей, что все сбалансированные периодические слова над алфавитом А = {aj, ,a„} из п символов с попарно различными плотностями символов имеют вид
W = (Un)°°,
где Un задается рекуррентно
Un = (Un-ianUn-i), U3 = aia2aia3aia2ai
Для 3-х буквенного алфавита гипотеза была доказана Р Тайдеманом31 В настоящий момент гипотеза доказана для алфавитов, состоящих не более чем из 7 символов
Продвижение в задачах символической динамики для слов с линейной функцией роста получено в работе П Арно и Г Рози32 В этой работе по-
28 Berstel.J , Resent results on Sturmian words // Developments m language theory II, 13-24, World Scientific, 1996
29 Aberkane.A , Words whose complexity satisfies Ътр[п)/п = 1 // Theor Comp Sei, 307, (2003), 31-46
30 Graham, R L , Covering the Positive Integers by disjoints sets of the form {[no + P\ n = 1,2, } // J Combm Theory Ser A15 (1973) 354-358
31 Tijdeman.R , 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, (1395), 261-276
32Arnoux,P , Rau2y,G , [1991], Representation geometnque des suites the complexite 2n + 1 // Bull Soc Math FVance 119, 199-215
строена динамическая система для слов с функцией роста Т(п) = 2п+1, обладающих дополнительным комбинаторным свойством В работе Г Роте33, в терминах эволюции графов Рози описаны слова с функцией роста 2п
Одним из основных результатов данной работы является обобщение этих результатов на слова с линейной функцией роста, то есть с функцией роста Т{п) = кп + I, для п> N
Перекладывания отрезков естественным образом служат обобщением вращения круга Эти преобразования были введены Оселедецем34, следовавшим идее Арнольда35 Рози36 впервые показал, что связь между вращениями круга и последовательностями Штурма обобщается, если рассматривать перекладывания отрезков В связи с этим (в той же работе) он задал вопрос об описании последовательностей, связанных с перекладываниями отрезков
Такие последовательности являются еще одним естественным обобщением слов Штурма В частном случае, для к = 3 отрезков, описание таких последовательностей было получено в работе Ференци, Холтон, Замбони37, а в работе38 были изучены частные случаи последовательностей, порождаемых перекладыванием 4-х отрезков
В случае произвольного числа отрезков также получен ряд интересных результатов В работе39 получен комбинаторный критерий порождаемое™ слов, получаемых симметричным перекладыванием отрезков, то есть перекладыванием, связанным с перестановкой (1 —> к, 2 —» к — 1, ,к —> 1)
В работе40 независимо от нас получен критерий порождаемое™ слов преобразованием перекладывания отрезков, удовлетворяющих следующему условию траектория каждой концевой точки отрезка перекладывания не попадает на какую-либо концевую точку отрезка перекладывания, в том числе сама на себя В этом случае, как не сложно видеть, слова будут иметь функцию сложности Т(п) = (к — l)n + 1 В данной работе получен более общий результат, не требующий выполнения этого условия
Отметим также, что во всех этих работах изучаются перекладывания, не меняющие ориентацию отрезков, а характеристические множества совпа-
33 Rote,G , Sequences with subword complexity 2n // J Number Theory 46 (1994) 196-213
34 Оселедец В И , О спектре эргодических автоморфизмов // ДАН СССР, 1966,168, стр 1009-1011
35 Арнольд В И , Малые знаменатели и проблемы устойчивости движения в классической и небесной механике// Успехи Мат Наук, 1963,18 6(114), стр 91-192
36 Rauzy,G , Echanges d'intervalles et transformations induites, (m French), Acta Anth 34 (1979), p 315-328
37 Ferenczi,S , Holton,C , Zamboni,L, The structure of three-mterval exchange transformations II a combinatorial description of the trajectories// J Anal Math 89 (2003), p 239-276
38 Ferenczi, S , Zamboni, L, Examples of 4-interval exchange transformations, preprint (2006), http //im! umv-mrs fr/ ferenczi/fz2 pdf
39 Ferenczi, S , Zamboni, L, A new induction for symmetric k-interval exchange transformations and distances theorem, submitted, http //iml univ-mrs fr/ ferenczi/fzl pdf
40 Ferenczi, S ,Zamboni, L , Languages of k-interval exchange transformations, submitted, http //iml univ-mrs fr/ ferenc2i/fz3 pdf
дают с отрезками перекладывания В нашей работе с помощью языка графов Рози мы сначала изучаем слова, порождаемые кусочно-непрерывным преобразованием отрезка, а затем показываем эквивалентность множества таких слов и слов, порождаемых перекладываниями Этот метод дает возможность описать р р слова, связанные с произвольным перекладыванием отрезка, более того, мы не требуем, чтобы характеристические множества, соответсвующие символам алфавита, совпадали с перекладываемыми отрезками
Цель Работы
Диссертация посвящена исследованию нормальных базисов алгебр медленного роста, а также исследованию взаимосвязи между комбинаторными свойствами слов, цепочками порождающих их автоматов (графов Рози) и порождающими их динамическими системами Свойства периодичности такаже находятся в центре внимания настоящей работы
Научная новизна
Все основные результаты являются новыми и состоят в следующем
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г
Публикации
Основные результаты опубликованы в 5 работах, список которых приведен в конце автореферата [1-5]
Структура диссертации
Диссертация состоит из оглавления, введения, четырех глав и списка литературы, который включает 75 наименований Объем диссертации составляет 82 страницы
Краткое содержание работы
Первая глава посвящена обзору и доказательству базовых результатов комбинаторики слов
Отдельно рассматриваются результаты теории слов Штурма, представлено доказательство теоремы эквивалентности, которое используется в следующих главах Также доказываются основные результаты из теории графов Рози
Вторая глава посвящена изучению сбалансированных слов над произвольным алфавитом Изучаются свойства слов, порождаемых иррациональными сдвигами тора
Пусть W - слово над бинарным алфавитом, порождаемое сдвигом одномерного тора, то есть динамикой (S1, U, Та, ж0) Обозначим /3 = a/q + r/q,
ид = \x\qx € С/}, у0 = х0/д, где ц, г — целые Несложно показать, что динамика (81, Тр, уо) порождает то же слово У/ Переход от первой динамики ко второй мы назовем ц -размножением Доказана следующая теорема об эквивалентности динамик
Теорема 1. Пусть два слова ЪУ^ и порожденные динамиками (§*, Та, II, хо) и (51, V, уо) совпадают Тогда существуют р и д такие, что множества 11 и V при соответствующих размножениях совпадают с точностью до поворота,т е 17р = Т^(Уд) для некоторого 5 > О
Далее проводим редукцию от сбалансированного слова \¥ над п-буквенным алфавитом к п бинарным словам Штурма Построим слова И^, , №п над бинарными алфавитами
Ах = {аьа1},Л2 = {а2,а2}, ,Ап = {а„, а„} следующим образом Ж = «)П62
п п \ а„ ю„ ф а,
Каждому слову 1¥г соответствует одномерная динамика (й1,!1^, Д^х,), ее порождающая, следовательно слово И7 порождается свигом на п-мерном торе с вектором сдвига 7 = (с*1, ,ап) Обозначим через М замыкание траектории начальной точки х = (Х1,Х2, ,хп) при действии Т7 Доказано следующее предложение
Предложение 1. М гомеоморфно множеству Б1 х {1,2, , Лг}
Теперь видно, что динамика реализуется на множестве М = В1 х {1,2, , ./V}, а отображение имеет вид / (х, к) —{х + а, к + 1 тос1 ./V) Будем теперь понимать под £/г характеристическое множество для символа аг, которое лежит на замыкании траектории, и пусть также I/* обозначает часть характеристического множества, которое лежит на к-ой компоненте связности (окружности) М Далее изучаются соответствующие характеристические множества Основным результатом данной главы является
Теорема 2. Пусть IV - сбалансированное непериодическое слово над алфавитом А Тогда для VV существует динамическая система (М, /), удовлетворяющая следующим условиям
1 М = Б>1 х Ът как топологическое пространство
2 / М —> М есть композиция поворота на а в В1 и сдвига на 1 в 2т Длина В1 равна т,
3 Каждая компонента S х {к} к = 1, ,п разбита на 2тп дуг т красных и т синих, все красные имеют длину а, все синие 1 — а,красные и синие дуги чередуются,
4 Синий цвет имеет I оттенков, красный - к оттенков, k + I = |Л|-число букв в алфавите Все середины дуг даного оттенка образуют вершины правильного многоугольника ("правильный 1 -угольник" - это точка на окружности, "правильный 2-угольник" - пара диаметрально противоположных точек),
5 При переходе от компоненты § х {&} к компоненте S х {к + 1}
х {то + 1} = § х {l}/' порядок расположения оттенков внутри красных и синих компонент сохраняется, а сами красные и синие дуги ("рулетки") проворачиваются относительно друг друга на 1 ( так что преобразование / приводит к смещению на а относительно красных компонент и на 1 — а (в обратную сторону) относительно синих)
Третья глава посвящена описанию нормальных базисов граничных алгебр, те алгебр, которые связаны с другим обобщенем слов Штурма -словам медленного роста Слово W называется словом медленного роста, если F\\r(n) = п + К, для всех п > N ( в словах Штурма F\y(n) = п + 1 и Fw{n + 1) — F{n) = 1 для всех тг > 1) Естественным обобщением будут слова, для которых F(n) = п + К, то есть F(n + 1) — F(n) = 1 для достаточно больших п
Показывается, что для каждого такого слова существует граф Рози, соответствующий некоторому слову Штурма Действительно, если начиная с некоторого п > N выполняется Т(п) = п + К, то это означает, что для каждого п > N в слове W существует только одно правое и одно левое специальное слово длины п То есть в графах Рози таких слов есть одна входящая и одна выходящая развилка, а значит, существует слово Штурма с такой же эволюцией fc-графов, что и данное Дальше просходит редукция к теореме эквивалентности Доказана
Теорема 3 Пусть W - рекуррентное слово над произвольным конечным алфавитом А Тогда следующие условия на слово W эквивалентны
1 существует такое натуральное N, что функция роста слова W равна Тцг(п) = п + К, для п> N и некоторого постоянного натурального К,
2 существуют такое иррациональное а и целые П\,П2, пт, что слово W порождается динамической системой (S1, Та, 7ai, ,Ian,x), где
Та - сдвиг окружности на иррациональную величину а, /0> - объединение дуг вида (nja,nj+ia)
Для произвольной алгебры А через Уа(п) обозначается размерность вектрного пространства, порожденного мономами длины не больше п, V^(rx) называется функцией роста алгебры А Пусть Хд(п) = Уд (га) — — 1) Если алгебра однородна, то 7д(п) есть размерность векторного пространства, порожденного мономами длины ровно п, 7д(п) называется функцией сложности алгберы А
Известно, что либо lim„_oo (7л (n) — п) = -оо (в этом случае есть альтернатива) либо 1нпУд(п) = С < оо и тогда dim А < оо, либо Уд(п) = 0(п) и алгебра имеет медленный рост), либо 7л (га) — п < Const, либо, наконец, lim,,—,» (7л(п) — п) — оо
В последнем случае рост может быть хаотичным, поэтому для изучения интересны первые два случая Случай, когда Тл(га) — п < Const (те случай алгебр медленного роста) исследовался Дж Бергманом и JI Смол-лом Нормальные базисы для таких алгебр исследованы в монографии (19) Назовем алгебру граничной, если 7л(п) — тг < Const Описание нормальных базисов граничных алгебр следует из теоремы 3 и результатов монографии19
Четвертая глава посвящена описанию слов, связанных с перекладыванием отрезков Рассматриваются случаи, когда ориентация отрезков сохраняется и когда нет В терминах графов Рози дается комбинаторное описание сверхслов порождающихся перекладыванием отрезков В центре внимания слова, имеющие функцию роста Twin) = kn + l Если слово обладает такой функцией роста, то 7V(n + 1) — 7\у(тг) — k
Известно, что если перекладывание к отрезков регулярно, то есть траектория любого из концов отрезков перекладывания не попадает на другой конец любого отрезка, то эволюция любой точки является словом с ростом Tw{n) = kn + l
Мы ищем условия на слово W, при которых оно порождалось бы преобразованием перекладываний отрезка, не обязательно являющегося регулярным Отметим, что сдвиг окружности, по сути, является перекладыванием двух отрезков с сохранением ориентации
Рассмотрим соответствие между подсловами и подмножествами М Легко видеть, что если начальная точка принадлежит множеству С,, то ее эволюция начинается с символа а, Рассмотрим образы множеств 11г при отображениях Ясно, что если точка принадлежит множе-
ству
T^iUJ л T-^\uln_x) п п T^iUJ п и10,
то эволюция начинается со слова а!оаг] atn Соответственно, количество различных существенных эволюций длины п + 1 равно количеству разби-
ений множества М на непустые подмножества границами подмножств dUt и их образами при отображениях /-1,/-2, ,f~n+1 Обозначим через 1и множество разбиения, которое соответствует слову и Ясно, что специальным подсловам соответствуют те интервалы, которые делятся образами концов перекладываемых интервалов Для данного слова и назовем слово v левым (соотв правым) потомком, если и - суффикс (соотв префикс) слова v, в соответствии с этим будем называть вершину в Gn левым (соотв правым) потомком вершины в Gk, п > к Прообраз конца интервала может являться граничной точкой только для двух интервалов, соответственно, специальные подслова могут иметь валентность только равную 2 Сформулируем следующее условие
Правило 1 Для того, чтобы бесконечное слово W порождалось системой
{I,T,U\, ,Uk) необходимо, чтобы любое специальное слово имело валентность 2
Таким образом, мы можем наложить условие на эволюцию графов Рози начиная с некоторого к все fc-графы Рози имеют входящие и исходящие развилки степени 2 Предположим, что некоторому подслову w соответствует характеристический интервал, полностью лежащий внутри интервала перекладывания Пусть точка А 6 [0,1] делит Iw на два интервала, образы которых лежат в 1йк и 1т соответственно, а точка В € [0,1] - делит на интервалы, прообразы которых лежат в 1а, и 1Л} соответственно
Выбор минимального невстречающегося слова, а, значит, удаляемого ребра, определяется взаиморасположением точек Л и -В, а также сохранением или сменой ориентации отображения на этих множествах Итого, имеется 8 вариантов, которые разбиваются на четыре пары, соответствующие одинаковым наборам слов Например, слову агта^ соответствует ситуация
В < A,T~\[xw,B]) С Ia„T([xw,A] С IaJ
Введем понятие размеченного графа Рози Граф Рози называется размеченным, если
1 ребра каждой развилки помечены символами I ("left") и г ("right"),
2 Некоторые вершины помечены символом "-"
Последователем размеченного графа Рози назовем ориентированный граф, являющийся его последователем как графа Рози, разметка ребер которого определяется по правилу
1 ребра, входящие в развилку должны быть помечены теми же символами, как и ребра, входящие в любого левого потомка этой вершины,
2 ребра, выходящие из развилки должны быть помечены теми же символами, как и ребра, выходящие из любого правого потомка этой вершины,
3 если вершина помечена знаком "-", то все ее правые потомки также должны быть помечены знаком "-"
Замечание. Поясним смысл разметки графа Пусть ребра входящей развилки соответствуют а, и символы I и г соответствуют левому и правому множеству в паре (Т(1а1),Т(1а])) Если символы а^ и а; соответствуют ребрам исходящей развилки, то символы I и г ставятся в соответствии с порядком "лево-право" в паре /а,) Знак "-" ставится в вершине, если характеристическое множество, ей соответствующее, принадлежит интервалу перекладывания, на котором меняется ориентация Условие для перехода от графа Сп к Сп-н
Правило 2.
1 Если в графе нет двойных развилок, соответствующих биспециаль-ным подсловам, то при переходе от йп к Сп+1 имеем (?„+! = /?((?„),
2 Если вершина, соответствующая биспециальному слову не помечена знаком "-", то ребра, соответствующие запрещенным словам выбираются из пар 1г и г1
3 Если вершина помечена знаком то удаляемые ребра должны выбираться из пары И или гг
Назовем эволюцию размеченных графов Рози правильной, если правила 1 и 2 выполняются для всей цепочки эволюции графов, начиная с назовем эволюцию асимптотически правильной, если правила 1 и 2 выполняются, начиная с некоторого Будем говорить, что эволюция размеченных графов Рози ориентированна, если в /с-графах нет вершин, помеченных знаком "-"
Теорема 4 Равномерно-рекуррентное слово
1 Порождается перекладыванием отрезков, тогда и только тогда, когда слово обеспечивается асимптотически правильной эволюцией размеченных графов Рози
2 Порождается перекладыванием отрезков с сохранением ориентации тогда и только тогда, когда слово обеспечивается асимптотически правильной ориентированной эволюцией размеченных графов Рози
Благодарности
Автор глубоко благодарен своим научным руководителям — доктору физико-математических наук Алексею Яковлевичу Белову и доктору физико-математических наук, профессору Александру Васильевичу Михалеву за постановку задач, обсуждение результатов и постоянное внимание к работе
Автор благодарен за внимание и обсуждение работы доктору физико-математических наук, профессору Виктору Николаевичу Латышеву, доктору физико-математических наук Николаю Германовичу Мощевитину, доктору физико-математических наук Андрею Михайловичу Райгородскому, доктору физико-математических наук, профессору Юлию Сергеевичу Илья-шенко
Автор выражает свою отдельную благодарность профессору университета Вайсмана А Френкелю (А Ргеапке1) за обсуждение 2-ой главы работы, а также профессору Л Замбони ( Ьиса Zamboш) за обсуждение 4-ой главы работы
Работы автора по теме диссертации
1 Белов А Я Чернятьев А Л , Слова медленного роста и перекладывания отрезков // Успехи Мат Наук, 2008, 63 1(379), 159-160
(Чернятьеву А Л принадлежат доказательства основных теорем 1 и 2)
2 Чернятьев А Л ,Сбалансированные слова и символическая динамика, Фундаментальная и прикладная математика, Том 13, выпуск 5, 2007 г, стр 213-224
3 Чернятьев А Л , Белов А Я , Описание слов Штурма над алфавитом из п символов, Математические методы и приложения, 6-й мат Симп МГСУ, - Москва, МГСУ, 1999г, стр 122-128
(Чернятьеву А Л принадлежит построение конструкции динамической системы и доказательство основной теоремы )
4 Белов А Я, Чернятьев А Л , Описание множества слов, порождаемых перекладыванием отрезков // Депонировано в ВИНИТИ, 1Ч1048-В2007, 18 стр
(Чернятьеву А Л принадлежат доказательства основных теорем 1 и 2)
5 Чернятьев А Л Слова с минимальной функцией роста // Вестник МГУ, том 6, стр 42-44, 2008 г
Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова
Подписано в печать 09. 0$ Формат 60x90 1/16 Уел печ л 10 Тираж №0 экз Заказ ¿/9
Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета
1 Введение.
2 Пространство слов и символическая динамика.
2.1 Пространство слов.
2.2 Рекуррентность и равномерная рекуррентность
2.3 Специальные подслова.
2.4 Морфизмы
2.5 Вопросы периодичности.
2.6 Графы Рози подслов.
2.7 Слова, порождаемые динамическими системами.
2.8 Функция рассогласования.
2.9 Соответствие между словами и разбиениями множества.
2.10 Перекладывания отрезков.
2.11 Слова Штурма.
2.12 Структура слов Штурма.
2.13 Слова Арно-Рози.
3 Сбалансированные слова и динамические системы
3.1 Введение и постановка проблемы.
3.2 Основные конструкции и определения.
3.3 Конечные сбалансированные слова.
3.4 Расширение сбалансированных слов.
3.5 Слова, порождаемые повороотом окружности.
3.6 Сбалансированные слова над алфавитом из п символов.
3.7 Основная теорема о непериодических сбалансированных словах над произвольным алфавитом.
3.8 Замечания о периодических сбалансированных словах над произвольным алфавитом.
3.9 Сбалансированные слова и теорема Голода-Шафаревича.
4 Слова с минимальной функцией роста.
4.1 Постановка задачи.
4.2 Свойства слов с минимальной функцией роста.
4.3 Частоты подслов в словах медленного роста.
4.4 Конструкция динамической системы.
4.5 Нормальные базисы граничных аллгебр.
5 Перекладывания отрезков и символическая динамика.
5.1 Введение и постановка задачи.
5.2 Необходимые условия для порождаемое™ слова перекладыванием отрезков.
5.3 Построение динамической системы.
5.4 Эквивалентность множества р.р слов, порождаемых кусочно-непрерывным преобразованием, множеству слов, порождаемых перекладыванием отрезков.
Актуальность темы.
Комбинаторика ело? находит свое применение в самых разных разделах математики. Например, в алгебре при изучении базисов и нормальных форм, в алгебраической топологии, в символической динамике. Ряд проблем, относящихся к комбинаторике слов находится на стыке алгебры и теории динамических систем. Многие проблемы комбинаторики слов представляют самостоятельный интерес.
Комбинаторика слов широко используется в задачах комбинаторной теории групп, в теории алгебр Ли, в вопросах бернсайдовского типа и в задачах, связанных с мономиальными алгебрами. Комбинаторная техника, относящаяся к теории групп, развивалась в работах М. Дэна, Е. С. Голода и И. Р. Шафаревича, П. С. Новикова, С. И. Адяна, А. И. Костри-кина, Е. И. Зельманова, И. Рипса, М. Громова, А. Ю. Ольшанского, М. В. Сапира и др.
Е. С. Голод и И. Р. Шафаревич [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 - • ■ игкт, где щ €У и г < к.
При этом в основе оригинальных доказательств А. И. Ширшова (как теоремы о свободе так и теоремы о высоте) лежала техника, связанная с преобразованием алфавита путем подстановок. Эта же техника используется при работе с равномерно-рекуррентными словами и в символической динамике.
Последующие доказательства теоремы о высоте [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 €Е (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 "Représentation geometrique des suites the complexité 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] получен комбинаторный критерий порождаемое™ слов, получаемых симметричным перекладыванием отрезков, то есть перекладыванием, связанным с перестановкой (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}, • • •, Ап = {а„, ап} следующим образом:
Каждому слову 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, 199215.
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 Sémin. Théorie des Nombres, p. 25-01-25-16, 1982-1983, Exposé No 25.
42. G. Rauzy, Échanges 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.
