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

• 1.    Введение

• 2.    Основная часть

Дана окружность единичной длинны. Пусть е — фиксированный иррациональный угол поворота. Цель данной работы — изучение количества слов длины n, порождаемых динамической системой поворота на е двух дуг, на которые разбита окружность. В работе [1] получена, кубическая оценка, для арифметической сложности слов Штурма, откуда, следует и кубическая оценка, для количества, слов, порождаемых поворотами двух дуг. Если угол поворота предполагается фиксированным, то оценка на количество слов длины n получается квадратичной от n.

Нас интересует динамическая система (ш, а, R_e, жо) — повороты окружности ш длины 1, разбитой на две дуги длины а и 1 — a на фиксированный иррациональный угол поворота е с начальной точкой жо. Ес ли RДжо) € а, то п-я буква слова w равна а, иначе Ь. Чтобы рассмотреть сразу все а, рассмотим тор Т 1 х 1, в котором каждое сечение прямой у = а, а € (0,1) является окружностью, разбитой на дуги а и 1 — а. Тогда поворот тора ж = ж + е преобразует все окружности как в (ш, а, R_e, жо). Прямые ж = 0 = 1, у = 0 = 1 и ж = у разбивают тор на две части, в которых пишутся разные буквы при попадании. Вместо того, чтобы рассматривать то, как проходит траектория R_e (жо) рассмотрим, как разбивают тор образы прямых ж = 0 = 1, у = 0 = 1 и ж = у при обратном преобразовании R_-e.

После п — 1 итер аций R_-e мы получим п вертикальных прямых (ж = 0, ж = — е, ж = {— 2 е } , ...), п наклонных прямых (ж = у, ж = у + е, ж = {у + 2 е } , ...) и одну горизонтальную у = 0. Чтобы подсчитать на сколько частей они разбивают тор, воспользуемся формулой Эйлера для графов на торе V — Е + F = 0. В нашем случае множество вершин графа V — это точки пересечения указанных прямых, множество рёбер графа Е — отрезки, на которые прямые разбиваются точками пересечения. Множество граней разбиения F — это множество областей, на которые прямые разбивают тор. Эти области соответствуют различным словам, порождённым символической динамикой (ш,a,R_e,Жо), где начальная точка жо лежит в соответствующей области. Каждая вертикальная прямая пересекает п наклонных, каждая наклонная пересекает п вертикальных, горизонтальная прямая также пересечена всеми наклонными и вертикальными, но только в п точках, являющимися итерациями точки (0, 0). Итого |V| = п², |Е| = 2п2 + п. Отсюда получаем, что искомое число частей разбиения F = Е — V = п² + п.

Работа поддержана Российским научным фондом, грант № 17-11-01377.