Предельные кривые для класса самоподобных адических автоморфизмов тема диссертации и автореферата по ВАК РФ 01.01.01, кандидат наук Минабутдинов, Алексей Рафаилович

• Минабутдинов, Алексей Рафаилович
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Минабутдинов, Алексей Рафаилович

Введение ................................................. 4

Глава 1. Индивидуальные непрерывные мосты и когомологич-ные константе функции.....................................13

1.1. Основные определения и обозначения...................13

1.2. Необходимое условие существования предельных функций ... 17

Глава 2. Существование предельных кривых для полиномиальных адических систем......................................20

2.1. Полиномиальные адические системы.....................20

2.2. Некоторые тождества для обобщенных биномиальных коэффициентов..............................................25

2.3. Комбинаторика конечных путей полиномиальных адических

систем ............................................. 27

2.4. Обобщенная т-щадическая система счисления на интервале [0,1]. 31

2.5. Сходимость при % w отношений dim(% — /,Ад,)/dim(%,A^)

размерностей вершин..................................35

2.6. Теорема существования непрерывных предельных кривых для

полиномиальных систем................................37

2.7. Примеры предельных кривых для полиномиальных систем. . . 45

2.8. Вид предельных кривых в симметричном случае при d w. . 52

Глава 3. Предельные кривые для автоморфизма Паскаля. . . 55

3.1. Система базисных функций Уолша.......................56

3.2. Полиномы Кравчука как эргодические суммы для цилиндрических функций ..................................... 60

3.3. Вид предельных кривых в транзитных режимах...........70

3

3.4. Свойства самоподобия функций 7^, 1..................73

3.5. Некоторые приложения полученных результатов к теории бу-

левых функций, комбинаторике и теории чисел............76

Заключение..................................................80

Приложение А. Список основных обозначений......................81

Список публикаций ..........................................81

Цитированная литература.....................................82

4

Введение диссертации (часть автореферата) на тему «Предельные кривые для класса самоподобных адических автоморфизмов»

Введение

Основная цель данной работы — исследование уточнений к индивидуальной эргодической теореме Биркгофа для специального класса адических автоморфизмов.

Индивидуальная эргодическая теорема является центральным результатом в эргодической теории. Рассмотрим автоморфизм Т, заданный на пространстве с инвариантной мерой ц. Пусть - суммируемая функция, ж G , (ф))=0 - числовая последовательность, элементы которой определены значениями функции вдоль траектории точки ж, ф = Ч). Тогда для

ц-п.в. ж существует предел 1 и—1 lim - /з- !=0

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

вательность случайных величин и для последовательности частичных сумм

1

S*(%) = (%) : S*(%) = Y2 ФМ, 1 < +w, исследуют вопрос о существова-

ло

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

Тогда иногда рассматривают вопрос о существовании последовательности на-

туральных чисел и нормирующих коэффициентов , таких, чтобы суще

ствовал предел распределений

(щ)

Д'

Анализируя автоморфизм Паскаля, введенный в эргодическую теорию

А. М. Вершиком в работе [7] и активно изучавшийся впоследствии многими

5

авторами (см. [8-11] и др.), К. Мела, Т. де ла Рю, Э. Жанврес и И. Веленик нашли замечательную новую сторону этой проблемы. Она заключается в возможности стабилизации поведения специальным образом нормированных конечных последовательностей растущей длины частичных сумм суммируемых функций вдоль индивидуальных (односторонних) траекторий автоморфизма. Такой взгляд на эту проблему позволил на примере автоморфизма Паскаля проиллюстрировать новый подход, который отличается от рассматриваемых ранее тем, что возникающий предельный объект, получивший название предельной функции, имеет не стохастическую, а детерминистическую природу.

Предложенный Т. де ла Рю, Э. Жанврес и И. Веленик в работе [12] объект может быть определен, вообще говоря, для произвольной числовой последовательности (ф)°=0. Для этого рассмотрим последовательность ее частичных сумм S*(п) и, полагая S*(0) = 0, доопределим ее с помощью линейной интерполяции на нецелые неотрицательные значения аргумента. Доопределенную таким образом непрерывную функцию обозначим через F. Рассмотрим последовательность непрерывных функций : [0,1] [—1,1], получа-

емых следующей перенормировкой функции F:

, . FО - п) — t -уЛ) = ——

где нормирующие коэффициенты канонически выбраны равными

max ]F(On)—OF(n)] (при условии, что F(On)—OF(n) 0, иначе = 1). По ^[0,1]

определению, р^(0) = р^(1) = 0, поэтому функцию естественно назвать мостом. Нас интересует множество предельных точек последовательности в равномерной метрике на [0,1].

Вернемся к последовательности ф, заданной равенством ф = у(Т^ж) при фиксированной точке ж. Соответствующую последовательность мостов будем обозначать через р^.

Определение 1. Если для выбранных функции у и точки ж G суще-

6

ствует такая последовательность Д) р N, что последовательность непрерывных функций сходится к (непрерывной) функции р^ в равномер-

ной метрике на [0,1], то функцию р = р^ называют предельной функцией, ее график предельной кривой, последовательность «моментов времени» О = (^) — стабилизирующей последовательностью, а последовательность

R^ = R^^g — нормирующей последовательностью. Непрерывным предельным мостом автоморфизма (И, R) для функции у в точке ж называется четверка (щ (R^^p).

Отметим, что сходимость по Чезаро последовательности (Д,Д влечет для нормирующего коэффициента R^ соотношение R^ = о(/^). Определение 2. Непрерывный предельный мост (/^^=1,(R^^=1,p^

для функции у в точке ж назовем существенным, если для любого е > 0 выполнено соотношение (О)1 = о(НД.

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

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

7

Теорема. (А. М. Вершик [7]). Всякий эргоДический автоморфизм, заданный на пространстве Лебега-Рохлина, изоморфен некоторому аДическому автоморфизму. Более того, изоморфизм может быть построен таким образом, что всякая счетная плотная инвариантная поДалгебра измеримых множеств перейДет в алгебру цилинДрических множеств.

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

В работах [7, 15-18] началось исследование комбинаторики марковских компактов (множеств путей на диаграммах Браттели). В этой работе мы изучим комбинаторную динамику конечных путей и определяемых ими цилиндров.

Чтобы получить интересные результаты, необходимо ограничиться некоторым классом адических автоморфизмов. Мы опишем диаграммы Браттели специального вида и зададим адический порядок на путях. Рассматриваемые нами диаграммы могут быть заданы производящим полиномом р(х) = а0 + Я1Х - - - + а^х^ степени Д G N U {0} c натуральными коэффициентами 0 < 2 < ф которые задают число ребер, соединяющих произвольную вершину (пД) с (н + 1Д + Д-ой вершиной следующего уровня. Данные диаграммы являются самоподобными, т.е. изоморфны (как упорядоченные градуированные графы, определение дано ниже) диаграммам, получаемым при

8

сдвиге корневой вершины в любую из нижележащих. Множество путей в графе Браттели В обозначим через Ху. На классах кофинитных путей можно задать естественный (ко)лексикографический порядок ^, который определяет адический автоморфизм При р(х) = а0,а0 > 1, получаемый таким образом автоморфизм является реализацией стационарного одометра. При Д = degр > 1 получаемые автоморфизмы являются нестационарными, они получили название полиномиальных аДических автоморфизмов и изучались в работах К. Мела [19] и C. Бейли [20]. Наш подход к определению полиномиальных адических автоморфизмов является менее ограничительным: мы не ограничиваемся рассмотрением единственного «канонического» порядка, рассматривавшегося в работах [19] и [20]. Класс полиномиальных адических автоморфизмов включает в себя (при р(х) = 1 + ж) знаменитый автоморфизм Паскаля (7,П),7 = {0,1}^. Из теоремы де Финетти следует, что множеством инвариантных эргодических мер автоморфизма является семейство мер Бернулли р^ = Ң(щ 1 — д). Важно отметить, что попытки исследовать и

1

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

Сформулируем основные результаты из работы [12].

Теорема. ([12], теорема 2.4.) Пусть (7,П, р^),у G (0,1), - автоморфизм Паскаля, а у - цилиндрическая функция. ТогДа Для р^-п.в. ж преДельная функция G С[0,1] существует тогДа и только тогДа, когДа функция у не когомологична константе.

Также для функций, коррелирующих с простейшими цилиндрически-

ми функциями г, (ж) = 1щ,=о}, где ж =

(^ )^1

G 4, авторы [12] показали,

что почти всюду предельной кривой является обобщенная кривая Такаги 7^.

9

(Определенная в работе [13] функция Такаги совпадает с функцией 2Д/2.) Теорема. ([12], теорема 2.5.) Для цилиндрических функций у, уДовлетворяющих условие Ү2к=1 cov^^(у,*п) > 0, среДи преДельных функций содержится функция Т^1.

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

Изучение предельных кривых является нетривиальной задачей и представляет интерес в том числе из-за возникновения так называемых транзитных режимов - наборов катастроф, которые происходят с (до)предельной функцией при вариации пути х. Некоторые примеры цилиндрических функций у и точек х G /, приводящих к таким режимам, были описаны в работе [12].

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

Основная цель данной диссертации — изучить индивидуальные непрерывные мосты для цилиндрических функций в полиномиальных адиче-ских системах.

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

10

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

Во второй главе исследуются непрерывные предельные мосты для полиномиальных автоморфизмов. В разделе 2.1 приводится конструкция таких автоморфизмов, структура инвариантных эргодических мер, а также основные свойства этих автоморфизмов. Семейство инвариантных эргодических мер, как и в случае автоморфизма Паскаля, представляет собой однопараметрическое семейство бернуллиевких мер. Важную роль в комбинаторной динамике полиномиальных автоморфизмов играют обобщенные биномиальные коэффициенты - размерности вершин соответствующих диаграмм Браттели. В разделе 2.2 исследуются некоторые свойства обобщенных биномиальных коэффициентов, на основе которых в разделе 2.3 строится явная формула для номера конечного пути в лексикографическом порядке, определяющем данный автоморфизм. В разделе 2.4 вводится в рассмотрение обобщенная т-^-адическая система счисления на интервале [0,1]. При г = 2,^ = 1/2 она сводится к стандартному диадическому представлению числа. Самоподобная структура диаграммы Браттели полиномиального автоморфизма обеспечивает сходимость отношений размерностей пар вершин, разности соответствующих координат которых фиксированы, к точкам отрезка, имеющим стационарное (т.е. стабилизирующееся, начиная с некоторого номера) разложение в т-^-адической системе. В разделе 2.6 доказана теорема существования непрерывных предельных кривых - основной результат данной главы. Она устанавливает, что условие некогомологичности цилиндрической функции константе является необходимым и достаточным условием существования непре

11

рывного предельного моста для полиномиальных адических автоморфизмов. В разделе 2.7 исследуются примеры предельных кривых полиномиальных автоморфизмов для «канонического» лексикографического порядка. Все построенные примеры предельных кривых можно рассматривать как обобщенные (т-^-адические) кривые Такаги. При этом соответствующие непрерывные предельные мосты оказываются существенными. Также в этой части исследованы свойства самоподобия и непрерывности данных кривых. Результаты этой части позволяют в разделе 2.8 получить аналитические доказательства некоторых предположений, сделанных в работе [12] на основе ряда компьютерных экспериментов.

Третья глава диссертации посвящена доказательству гипотезы Т. де ла Рю, Э. Жанврес и И. Веленик о том, что для всякой (неко-гомологичной константе) цилиндрической функции можно построить такую стабилизирующую последовательность /^, что графиком предельной функции будет являться обобщенная кривая Такаги. Эту задачу можно свести к описанию транзитных режимов (в которых могут возникнуть другие функции) и доказательству того, что множество путей, для которых они возникают, имеет меру ноль. Технически, изучение транзитных режимов требует глубокого анализа асимптотик частичных сумм цилиндрических функций. Частичные суммы для автоморфизма Паскаля могут быть выражены через полиномы Кравчука, а исследование предельных кривых в транзитных режимах можно свести к рассмотрению специальных асимптотик (разностей) полиномов Кравчука.

Доказательство теоремы проводится в несколько этапов. На первом этапе, в разделе 3.1, построен ортогональный базис {%^}W=0 пространства цилиндрических функций. В терминах ряда (суммы) Фурье по этой системе дано полное описание когомологичных константе цилиндрических функций для автоморфизма Паскаля. На втором этапе, в разделе 3.2, найдены формулы

12

для частичных сумм базисных функций t 0, представляющие собой (с точностью до нормировки) ортогональные полиномы Кравчука. На третьем этапе исследованы асимптотики полиномов Кравчука, на основе которых в разделе 3.3 проведен анализ транзитных режимов.

Упорядоченные в лексикографическом порядке множества вершин единичного куба {0,1}"*, сумма координат которых равна ^, составляют башни (см. ниже), участвующие в аппроксимации автоморфизма Паскаля, и являются замечательными комбинаторными объектами. Они связаны с теоремами Маколея и Крускала-Катоны, линиями уровня функции s2(%) (число единиц в двоичном представлении целого неотрицательного числа %), а также теорией булевых функций. В разделе 3.5 устанавливается эта связь и приводятся приложения полученных результатов к некоторым задачам теории булевых функций, комбинаторики и теории чисел. Показано, что каждому транзитному режиму соответствует корень некоторого полинома Эрмита, а также аналитически описаны предельные кривые, наблюдаемые в транзитный режимах.

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

Основные результаты, представленные в диссертации, изложены в работах [1-6] и докладывались на Санкт-Петербургском семинаре по теории представлений и динамическим системам, на международной конференции «Dynamics, Combinatorics, Representations» в Санкт-Петербурге в 2015 году и на конференции «New Advances in Symbolic Dynamics» в Марселе (Люмини) в 2017 году.

13

Глава 1

Индивидуальные непрерывные мосты и когомологичные константе функции

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

1.1. Основные определения и обозначения

Определение 3. Диаграммой Браттели В = (^, f) называется бесконечный градуированный неотрицательными целыми числами граф, множества вершин и ребер f которого обладают следующими свойствами:

1. Множества вершин и ребер f являются градуированными множества-

ми, т.е. являются счетным объединением попарно непересекающихся конечных множеств: = UW=0^^, f = UW=0f^, а множества и f^

конечны для всех уровней %.

2. Множество % состоит из единственной вершины с непустым множеством исходящих ребер, называемой корневой вершиной.

3. Ребра являются ориентированными и всегда исходят из вершины в вер-

шины следующего уровня; всякая некорневая вершина имеет непустое

14

множество входящих и исходящих ребер. При этом две вершины могут быть связаны более чем одним ребром.

Для удобства обозначений, мы считаем, что на каждом уровне % множество 4^. состоит из L(%) + 1 вершины, которые занумерованны слева направо индексами от нуля до Ъ(%). Определим отображение : f задающее

по ребру его конец, а также отображение : f , задающее его начало. Последовательности ребер (^,)^, такие, что конец %-го ребра является началом (% + 1)-го, составляют пространство (^, f) путей диаграммы В.

Пусть 0 - такие числа, что + 1 равно входящей степени вершины

(%,^). Мы будем считать, что ребра, входящие в вершину (%,^), помечены индексами 0,1,..., .

Согласно классическому определению А. М. Вершика, введенному в основополагающей работе [15], мы предполагаем, что на множестве ребер (^), входящих в вершину с координатами (^, ^), 0 < < L(^), ^ > 1,

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

Определение 4. Адический автоморфизм Т на пространстве \ (^max U ^min) задан переходом от точки этого пространства (пути в графе) к следующему пути относительно порядка ^.

Замечание 1. Преобразование Т определено всюду кроме (не более чем) счетного множества максимальных путей ^max, а обратное преобразование Т-1 определено всюду кроме (не более чем) счетного множества минимальных

15

путей ^min. Адический автоморфизм Р : \ ^max \ ^min является го

меоморфизмом в естественной канторовской топологии. Мы будем считать, что адический автоморфизм задан на множестве \ (^max U ^min).

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

Для пути обозначим через ^Ц<^) номер вершины уровня %, через которую проходит данный путь. Для конечного пути с = (с1,...,с^), ведущего из начальной вершины (0,0) в вершину (%,^), число А^(с) будем коротко обозначать через ^(с). Цилиндрическое множество ранга % вида С = [с1с2 ---сЦ = {^ G ]^1 = с1,^2 = с2,---,^^ = с^} определяется

конечным путем с = (с1,с2,---,с^), ведущим из вершины (0,0) в вершину (%,^) = (%,^(с))- Число таких путей (размерность вершины) (%,^) мы будем обозначать через dim(%,^) или, короче, - Множеству конеч-

ных путей с = (с1,с2,---,с^), ^(с) = ^, упорядоченных в лексикографическом порядке, соответствует упорядоченное множество цилиндров , составленное из соответствующих цилиндров, которые удобно обозначать через Ц), 1 j dim(^, ^). Множество образует башню автоморфизма, множество башен {т^}^=0^ фиксированного уровня % определяет аппроксимацию автоморфизма Р, см. [14], [16], [21]. Номера этажей башни — это номера путей в лексикографическом порядке. Номер пути обозначим через

Num(^). Очевидно, что номер Num(^) пути лежит в пределах от

единицы до dim(%, ^).

Пусть G G — цилиндрическое множество, ж G и G N. Размерностью dim(C, (^, ^^(ж))) цилинДра С при фиксированной вершине (%,^,(ж)) называется число путей, принадлежащих С, которые совпадают с путем ж начиная с уровня %. Для всякой (неатомической) эргодической инвариантной

16

меры д выполнено соотношение д(С) = lim

^—^ОО

для д-п.в. ж G F.

dim((^,^^(^)))

Зафиксируем вершину (^, ^) диаграммы Браттели В. Ее можно рассмат

ривать как исходную в новой диаграмме В^ = (У, f). Множество вершин У, ребер f^ и путей F(В^) определяются естественным образом. Как и выше, частичный порядок В на путях диаграммы В' индуцируется с линейных

порядков <ң/^', В > %, на множествах входящих ребер.

Диаграммы Браттели В = (У, f) и В' = (У^, f^) назовем изоморфными, если найдутся такие биекции б : У У и к : f f, что б о о к и

б о о к. Упорядоченные диаграммы (В, ^) и (В', ^^) изоморфны, если

при изоморфизме диаграмм В и В' порядок переходит в порядок В.

Определение 5. Упорядоченная диаграмма Браттели (В, ^) называется самопоДобной, если упорядоченные диаграммы (В, ^) и (В^_ ) изоморфны

для % G N, 0 В(^).

Пусть F — множество всех функций / : F R. Пространство цилиндрических функций ранга N (т.е. функций, постоянных на элементах разбиения на цилиндры ранга N) обозначим через F^.

Линейно-интерполированные частичные суммы , ж G (1), цилиндрической функции из пространства F^, Ғ < ^, будем кратко обозначать через . Пусть на этаже Ғ < % диаграммы Браттели находится В + 1 вершина. Пусть G , 0 В(^), — путь конечной длины, такой,

что его начальный отрезок В = (^1 ,^2,...,^w) является максимальным, т.е. Num(^') = dim(F, ^(В)). Разобьем множество путей, ведущих из начальной вершины (0,0) в вершину (%, ^) и не превосходящих пути ^, на классы В^(^), в зависимости от того, через какую из вершин (Җ /), 0 < / < L, уровня Ғ проходят данные пути (некоторые из множеств В^(^) могут оказаться пустыми). Так как путь В является максимальным, размерность dim(F, /) делит число путей (<^), лежащих в классе В^(^), для всякого 0 < / < L(F).

17

Обозначим через Д) отношение е^(^) к dim(N,/), а через сумму (Нҗ/), 0 Е(н). Сумма значений функции у по путям, лежащим в

классе Е^(^), равна (^). Группируя слагаемые, для частичной сум-

мы в точке у = Num(^) приходим к следующему выражению:

щ (j ) = X ("). (1.1)

/=0

1.2. Необходимое условие существования предельных

функций

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

Пусть (ДЕ, р) - эргодический автоморфизм. Пусть для суммируемой функции у, точки ж G и последовательности (ф) = (ф(ж)) функции р(( / заданы соотношением

г., ,

R^

где R^, выбраны равными максимуму модуля числителя (функция в числителе предполагается не равной нулевой функции на [0,1]). Не теряя общности, будем считать, что предел у* (ж) = lim 1в точке ж существует. Следующее утверждение обобщает лемму 2.1 работы [12] на случай произвольной суммируемой функции.

Теорема 1. Если непрерывные предельные кривые р(( = lim^ р(( / , существуют Для п.в. ж, то соответствующие нормирующие коэффициенты R(( / неограничены по н.

Доказательство. Пусть, напротив, ]R^ / ] R. Положим, для краткости, Е = , pi = р^ , = R^ , и р = р^. Так как р = 0, найдется у G N,

18

для которого IF (j) = ц*. Тогда liminf]^^( )] = liminf]F (j) —

]F(j) — *] = 1F(2) — ц*] > 0, что противоречит непрерывности функции

в нуле.

Определение 6. Функция ц G ТДДд), удовлетворяющая тождеству ц = с + / о Ғ — / для некоторой постоянной с и функции / G F^(Jf, д), называется когомологичной константе.

Теорема 2. Последовательность нормирующих коэффициентов д-п.в. ограничена тогда и только тогда, когда функция ц когомологична константе.

^—1

Доказательство. Суммы Y2 (з — 3*) о когомологичной константе функ-

J =0

ции ограничены, следовательно д-п.в. ограничены нормирующие коэффициенты .

Доказательство обратного утверждения использует результат А. Г. Ка-чуровского из работы [22]. Пусть нормирующие коэффициенты п.в.

ограничены. Тогда для п.в. ж G для всякого j G N выполнено неравенство ]F^(j) — р(/^)] Ғ. Переходя к пределу по %, получаем, что

] Y2 / о П(Д] Ғ, где / = ц — ц*. Согласно теореме 19 работы [22], нера-

!=1

венство ]^^] G, эквивалентно существованию функции / G Ғ^, такой, что

F — /к (Следовательно, ц = / о F — / + ц*.

Замечание 2. В силу эргодичности, когомологичность константе функции ц следует уже из ограниченности нормирующей последовательности на множестве положительной меры.

В силу теорем 1 и 2 во всех теоремах существования предельной кривой предполагается некогомологичность константе рассматриваемой функции.

Определение 7. Пусть диаграмма Браттели П имеет на каждом уровне единственную вершину, а порядок входящих ребер возрастает слева напра

19

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

Рис. 1.1. Пример диаграммы Браттели классического одометра.

Теорема 3. Пусть (ДТ, ^.) - классический оДометр. ТогДа всякая цилинДрическая функция ц G когомологична константе. СлеДовательно, преДельной кривой Для такой функции не существует.

Доказательство. На каждом уровне % > N диаграммы Браттели находится

(1.1), определяется единственным коэффициентом ^0, а значит, пропорциональна размерности П^ = dim(F, 0) вершины (F, 0). Можно вычесть из функции ц такую константу С, чтобы выполнялось равенство ^д—0^ = 0. Это эквивалентно тому, что функция ц — G принадлежит линейному простран-

ству, натянутому на функции этажа башни тҗ0.

20

Глава 2

Существование предельных кривых для полиномиальных адических систем.

Список литературы диссертационного исследования кандидат наук Минабутдинов, Алексей Рафаилович, 2017 год

ция -

Доказательстзо. Пусть выбран типичный путь ж G Ну. Можно считать, что последовательность (п(ж),Ау) удовлетворяет свойствам Д < < Дб

для некоторого Д > 0. Пусть, для начала, такие н и фиксированы. Также мы рассматриваем множество путей длины rn, входящих в вершину ДД) Д < < б(н — 1), н >> rn, диаграммы Ву. Самоподобие диаграммы Ву позволяет рассматривать эти пути как пути, идущие из основания в вершину (rn,j),0 < тф обратной диаграммы, см. рис. 2.6. Как показано в части 2.4, каждому конечному пути длины m на обратной диаграмме Браттели Ну, ведущему в вершину (ш, j), соответствует стационарное число ранга m из множества СД которому, в свою очередь, соответствует щт-адический интервал ранга rn. Длину этого интервала обозначим через , а приращение на этом интервале функции фД, определенной в части 2.6, через , 0 ф j ф тб. Значения (ж^д ,й^у) могут быть определены индуктивно: начальные значе-

47

ния при rn = 0 Жо,о = 1,^0,0 = 0; при m > 0 и индексах 7, таких, что,

(rn - 1)7 < 7 ш7, _7), (ж^), а при прочих

7, определим их рекурсивно: ж^-щ ^Z^=0 ^7', 7^-щ ^Z^=0 ^7'7m,.-7 -Таким образом, функция полностью определяется в точках вида , 1 m М, (rn — 1)7 < 7 rn7. Переходя к пределу, мы получаем требуемое

утверждение.

Пусть параметры щ и ^2 принадлежат интервалу (0,1). Определим

функцию S*^2 : [0,1] [0,1], отображающую число ж, представленное в

—

щ-адической записи 2.9 в виде ж = X) Е (^7)^1 7=1

^1'^7+2^2 '.7 +-

в чис-

ло

X—\ ^1'^7 +2^2'^7Ч -^7

м 1.2 (^7 )92( Т)

7=1

(2.15)

Для всякой щ-рациональной точки ж0 = произвольного ж G [0,1], функция ДД2

Е (%- )^1

7=1

&1'^7 +2&2'^7 Ч-

удовлетворяет следующему уравне-

П

и

нию самоподобия:

^2(^0 + ^?1 = 5^2 (^о) + S*^,^2 (Е, (2.16)

/\ a1'S^+2a2'Sm4--

где = фД-у) , ^ = 1,2. В частном случае щ = 1/г

функция является функцией распределения меры /Д.

Формула (2.16) означает, что график ДД2 на обобщенном щадическом интервале [ж0, ж0 + ] является миниатюрной версией ^2, сжатой в г^2 раз по вертикали и в по горизонтали.

Семейство функций ^2 (-) позволяет определить новый класс функций

,7 G N.

?2=?1

'^1 :=

При 7 = 0 удобно считать, что 7)0?(Е = При р2(ж) = 1 + ж, = 1/2 и 7 = 1

функция 27^11/2 является знаменитой кривой Такаги, см. [13]. Данная связь

48

Рис. 2.8. График функции 7^, при р(ж) = 2 + ж + ж^ и параметре равном

впервые установлена в работе [25]. Такие функции в диадическом случае d = 1 изучались в ряде работ, см, например, [26], [27] и исторический обзор в [28]. При > 2 также некоторые частные случаи в работе [29].

Теорема 7. Фрмкрмм 7^,7 Е (0, l/<pj),A: > 1, мелрермемм ма ммтереале [0,1].

у^оказатпельстпбо. Идея доказательства использует то, что для точек тир, лежащих в одном элементе ранга m щг-адического разбиения, первые m координат (ад, - - -, совпадают. Это позволяет напрямую оценить модуль разности [7^ (ж) - 7^(р)].

Определим равным отношению ^/7. Как было показано в ча-

сти 2.4 выше, всякое число ж Е [0,1] может быть естественным образом закодировано путем ц? = Е Л, в (совершенно сбалансированном)

дереве Пусть, для начала, А; = 1. Функция 7^<?(т) = 7*(т) отображает число ж = Е [0,1], кодируемое последовательностью (цц,Ш2,...), щ ЕЛ, следующим образом:

где 5/ - s? - число координат, равных / Е Л, среди (сщ, ц?2,..., %), в р =

49

Обозначим через ф- сумму О - + 2&2 * Т,- + - - - + .

Производная (ф) равна ф-1,0^-1[(j — /)^ + ], где / = ф- — + 2.

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

/

1 + &1(^ — 1)^ + ' ' ' + ^-1^ 1 — (^ — 1)^ 2

&1^^-1 + 2&2^^—2^^ + ... &^-1^

(2.17)

Пусть &max является максимальным из коэффициентов полинома р(д). Ясно, что ] < &тахцу-. (Обозначим через р^^ж G (0,1) максимум из

/2

, ,..., ^з-т }.

Пусть принадлежит границе некоторого ^-г-адического интервала ранга rn, содержащего ж. Тогда справедлива оценка

W ^7'-1

Д (у) -т IЩТ +=)

^'=т !=0

Пользуясь оценкой, ]^^'+^] < (p^^^)^', приходим к выводу, что абсолютное значение производной (ф) при j > 2 оценивается выражением вида Р(2,9)(РтажР'-2, где Р(j,^) - некоторый полином. Положим е равным 0.99. Тогда при достаточно больших m выполнено:

w Щ — 1

IT(y) - Т(ж)] X )(Р^.^)'-2 < Г(р^^)"', (2.18)

^'=т^=0

где О -некоторая константа.

В общем случае, не умаляя общности, можно считать, что точки ж и ж + принадлежат некоторому -т-адическому интервалу ранга m = тф), причем lim rn(d) = +w, а щ как и выше, - граничная точка этого интервала. Выполнена оценка

да + <5) - Щ)! < ]Т(у) - Т(ж)] + ДО) - Т(ж + < 2СрЩ.

50

При > 1, с учетом оценки ^-ой производной ] у' ] < Р^(2,й)(Р^аж)'-^-1, где у > Д а Р^(у, у) - некоторый полином, структура

доказательства и результат полностью сохраняются.

Покажем, что для некоторых цилиндрических функций в качестве предельных кривых возникают графики функций 7)Д. (В случае автоморфизма Паскаля это утверждение было доказано в работе [12], лемма 3.2.)

Предложение 4. Для цилиндрических функции у виДа - Хр=0ДД{^1 G F предельной кривой является график функ-

ции 7^^.

Доказательство. Для краткости докажем теорему для многочлена р3Д) = 1 + ж + ж2. В силу леммы 4, достаточно доказать, что предельная кривая рД) совпадает с функцией 7^ в точках вида ж = ф и ж = у'-1 (у +Д), где у G N.

Функция 7^ отображает точку ж = ф в точку у' = уу'-1, а точку

ж = ф 1(у + Д) в точку Д' 2 (уф + (у - 1)Д + р). В силу 2.17,

Согласно тождеству 4 из таблицы 2.1, мы имеем: . Обозначим

для краткости частичные суммы РД через Р. Нужно вычислить следующие пределы при 2 G N, н w, (в предположении Е^^^1 = 2у + Д):

Полагая Р^ = (2 - Е^^^1), после некоторых вычислений видим, что пер-

вый предел равен Д-а второй предел равен ф-2(Д + (2 - 1)t^ + у)

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

Отметим, что построенный мост является существенным, см. определение 2. В общем случае доказательство проводится аналогично. П

51

Численные эксперименты показывают, что функции 7)^, А; 1, и их линейные комбинации возникают в качестве пределвнвж функций lim уР , 72^00 '

для любв1х некогомологичнв1х константе функций G Тцу для автоморфизма 7],. Доказателвству этого резулвтата для случая автоморфизма Паскаля посвящена третвя глава диссертации. Выражение (2.4) показывает, что для цилиндрической функции частичнвю суммв1 определенв1 коэф-

фициентами О < А; < N7. Поэтому удобно вв1братв такой ортогональный базис, для которого коэффициента: задаются производящей функцией

= (^о + ^1^ + -' - + Например, для автоморфизма Паскаля

функция (1 — ат)^(1 + где а = является производящей функцией

полиномов Кравчука, а - элемент базиса Уолша. Изучение предельных кривых для автоморфизма Паскаля сводится к изучению тонких асимптотик полиномов Кравчука. Однако прямой перенос этих результатов на общий случай представляется достаточно сложным и громоздким.

Рис. 2.9. Пример предельной кривой для автоморфизма ТД, ст = (0, 2,1).

Рассмотрение автоморфизмов при естественно приводит к от-

личной (от возникающей для случая канонического порядка) т-щадической системе счисления и, как следствие, другим предельным кривым. Любопытно, что некоторые из возникающих кривых также возникали в работе японских математиков Т. Окада, Т. Секигучи и Я. Шиота в работе [29], в которой они обобщали работу [25] на мультиномиальный случай. Пример одной из

52

/ О 1 2 \

кривых, отвечающих подстановке , приведен на рис. 2.9.

о

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

2.8. Вид предельных кривых в симметричном случае

при d сю.

В этой части мы отвечаем на вопрос И. Веленика, Т. де ла Рю и Э. Жан-врес из работы [12], стр. 20, часть 4.3.1. Мы предполагаем, что полином имеет вид 1 + ж + + - - - +

Рис. 2.10. Вид предельных кривых для полиномиальной адической системы при параметре d + 1 = 2,3,8,32.

Пусть <Е (0,1), at<? 6 (0,1) является (единственным) решением на (0,1) уравнения

^ + ^-^ + -.- + ^ = /-1.

Как и выше, положим /5 = /5^ равным отношению Как показано в части 2.4, всякий ж из интервала [0,1] может быть записан в (^+1)-адическом представлении в виде

ж

СЮ —1

= Е (Е

1=1 3=0

(2.19)

где д? = G {0,1..., d} = Л, является путем в (d + 1)-адическом

53

(совершенно сбалансированном) дереве ^^+1, а s'; равно числу появлений символа G Л среди ^1,^2,... ,^7-.

Обозначим через (ж) (аналитическую по параметру ) функцию, определенную (равномерно суммируемым по ж) рядом (2.19). Мы положим

мер, если 7 = 1, то представление (2.19) при = 1/2 является стандартным

диадическим представлением числа ж G [0,1].

Авторы работы [12] провели ряд компьютерных экспериментов с целью численно проверить, переносятся ли их результаты, полученные для автоморфизма Паскаля, на системы, заданные полиномами р^(ж),7 > 1. Результаты их экспериментов (но в большей общности: для полиномов с произвольными натуральными коэффициентами) были (аналитически) получены автором диссертации в работе [6] и изложены в разделе 2.6 выше. В частности, авторов [12] заинтересовало поведение предельных мостов при больших значениях параметра 7: численные эксперименты показывали, что предельные кривые должны сходиться при 7 ^ — к гладкой кривой.

На основе теоремы 4 вопрос авторов [12] можно сформулировать как вопрос о поведении функций

1 дП (ж)

<?=<?*

(2.20)

при больших значениях параметра 7 (мы дополнительно должны ввести вертикальную нормализацию делением на 7 + 1; если 7 = 1, то график функции 27^ является кривой Такаги). Ниже мы покажем, что при 7 ^ — предельная кривая является параболой, см рис. 2.10.

Предложение 5. Пусть полиномы р^(ж) имеют виД 1 + ж + ж2 + - - - + рф функции 7^ : [0,1] R определены равенством (2.20), а функция ф определена равенством ф(^) = t(1 — t),t G [0,1]. ТогДа 7^ равномерно схоДятся к ф при 7 ^ —.

54

Доказательство. Разделим единичный интервал на 7 +1 подинтервалов 7, = (7+1; 77+1), 0 < < ^, одинаковой длины и вычислим функцию 77 в (левой) граничной точке каждого из интервалов. Нам также нужно показать, что приращения функций 77 являются равномерно по 7 стремящимися к нулю на этих интервалах. После этого остается перейти к пределу по 7.

В силу того, что мы исследуем симметричный случай = t- =

теорема о неявной функции (см. формулу (2.17)) показывает, что произ-

- -

водную t- можно выразить следующим образом: = -2-7. Отсюда Д- =

= -. Последнее позволяет заключить, что у-(^')]-=-* = -=-* -

J?'-1^' + г^^-1?'^- = (9.)'-1(9 + n?.(-)) = (^,)'-1(j - 2r)).

-=-*

Отметим, что левые граничные точки с. интервалов /с.,с G [0,1],с7 =

[с7], ([ - ] - целая часть числа) задаются отношением с7 = 7+1 и кодируется

стационарной последовательностью = (^)°=1, где ^1 = с7 и = 0,7 > 2.

Это позволяет вычислить значения функции 77(с.) явным образом:

77М =

1 7с-1

л+j 1 -

/=0

2('^(' - 1) + '7 = С.(1 - С.)

-----> с.(1 - с.).

7—^00

7 +1

7

Мы можем заключить, что, если предельная гладкая кривая существует, то

она является параболой.

Остается проверить, что приращения функций 77 равномерно стремятся к нулю по параметру 7 на интервалах /с.. Аналогично оценке (2.18), мы

получаем, что для ж G /с7 справедливо w . -1/

]77M - 77М] = с+гЕ7* 1 12 U -

'=2 /=0

2(s'+2s' +--+75^-^' +/)

7

<

W ' 1

^^2. Последнее неравенетво позволяет заkлючuть, что Рае-стояние Хаусдорфа между графиками стремится к нулю.

П

55

Глава 3

Предельные кривые для автоморфизма

Паскаля.

В этой главе предельные кривые подробно исследуются на примере конкретного автоморфизма - адического автоморфизма Паскаля (7, И). Как и в общем случае, мы будем считать, что выбрана инвариантная эргодическая мера , у G (0,1). Целью данной главы является доказательство следующей теоремы единственности предельной кривой:

Теорема 8. Пусть П - автоморфизм Паскаля, заданный на пространстве

с мерой (Ц Д ),у G (0,1), П G N и у G F^ - некогомологичная константе

цилинДрическая функция. ТогДа Для -п.в. ж стабилизирующая последова

тельность ф = ф(ж) может быть выбрана так, что преДельной функцией

является обобщенная функция Такаги 7^

гДе G {-1,1}.

Задача доказать данную теорему была поставлена в работе [12] и была мотивирована численными экспериментами, демонстрирующими изменения вида предельной кривой и асимптотик нормирующих коэффициентов при вариации вида (Д + Д,п),Д = о(н), пути (^^,н), lim — = у, в графе Паскаля. Данные бифуркации авторы работы [12] назвали транзитными режимами и поставили задачу их исследовать (см. работу [12], часть 4 «Открытые вопросы»).

Наш подход будет заключаться в следующем: мы выберем в пространстве F^ удобный ортогональный базис, что позволит явно описать некогомо-логичные константе цилиндрические функции для автоморфизма Паскаля (теорема 9), а также установить вид предельных кривых в общем случае (теорема 8) и в транзитных режимах (см. часть 3.3).

56

3.1. Система базисных функций Уолша

Систему функций РаДемахера {р^(у)})Д1 на пространстве 7 = {0,1}^ можно коротко определить следующим образом1:

тДй) := (-1)^", й = ) G

Определим систему функций Уолша {*щ}Д0 (в нумерации Пэли).

Определение 9. Полагаем -ид(у) = 1. Число t G No представим в виде t = р2° + t121 + - - - + -12^-1, где С G {0,1}. Положим

w-1

Wt(y) П 6=+1(^^*' = ^1°(у) ' Тз (^) ' " ' ' У'(^)

(3.1)

где щ - 2-ая функция Радемахера.

Функции Уолша-Пэли образуют группу характеров диадической группы Z2 и образуют ортонормированный базис в Е^1/2 (1). Для функции ф G Е))1/2 (7) обозначим через Уф(ф, у) частичные суммы ряда Фурье по системе Уолша-

1

Пэли: Е^(ф,у) ^2/^=0 (й)i где ф(у)щ^(У)^У'

o

Система Уолша {*щ}Д0 является полной ортонормированной системой в ^Л1/2 (^), а значит, и полной системой в Д). В нумерации Пэли первые 2^ функций Уолша образуют также базис в F^.

Предложение 6. Если ф G F^ и Д 2^, то (ф) = ф.

Определим систему функции *иф, t > 0, следующим равенством:

(3.2)

1 Наше определение задает функции Радемахера на группе Z2, при отображении оно естественно соответствует классическому определению тДу) = sign(sin (2"лу)), у G [0,1), % Д 1 на [0,1).

57

где через s2(t) обозначено число еДиниц 6 двоичном разложении натурального числа б (в англоязычной литературе - «sum of binary digits function»). В случае у = 1/2 имеем тождество ш^/2 = *щ.

Предложение 7. Пусть П G N. При 0 < з < t справедливы тожДества:

cov^, (^? = 0, Ел, = °,

что позволяет заключить, что система {ш/}/=0 образует ортогональный базис в пространстве цилинДрических функций (УУ, ), причем ]]ш/]]2 = 1 - (2у - 1)2m.

Доказательство. Положим о равным 2у — 1. Среднее функции Уолша по мере может быть найдено следующим образом:

/

= У(—1Л—'

/=0

(1 - y)m-

(2у - 1)m =

где rn = S2(t). (3.3)

Определим операцию О на парах натуральных чисел в двоичной записи как сложение без переноса: для 2 = X) и у (^2^, где G {0,1},

Л=0 л=0

по определению,

О / = (^л + ^л) mod 2.

Л=0

Очевидно, что (более того, функции Уолша-Пэли образуют

группу характеров диадической группы Z2). Поэтому можно записать:

cov^ (ш^, ш^) = Ел- Е^,Ш; Е^,ш^.

Пользуясь этим выражением, при 0 < s < б, ковариацию cov^,(ш/,^g) можно выразить следующим образом:

coET, (^Д,^s) ^2(-1)S2('-'

'=0

mod 2 )

58

Для того, чтобы показать, что правая часть приведенного выше равен/ 10 \

ства равна нулю, рассмотрим матрицу А(ж) = . Обозначим через

\ 0

В^(ж) ^-кратное кронекеровское произведение (Җж)) , G N. Записывая

^-кратное кронекеровское произведение последовательно и пользуясь свой-

ством (Л 0 В)(С 0 В) = (N0) 0 (BD), по индукции легко проверить, что

В^ (ж)В^ (^) = В^ (ж + ^).

(3.4)

Строки и столбцы матрицы В^ нам удобно нумеровать начиная с нуля. По индукции проверим, что при G N и 0 < 2,2* < 2^ (^,j)-ый элемент матрицы В^(ж) имеет вид

7), если 2 > 7 и (2 — 77 = С

(3.5) 0 иначе.

База индукции: при = 1 равенство очевидно. Пусть равенство (3.5) доказано при некотором В Положим г = 2^. Функция s2(-) удовлетворяет уравнениям

s2(J + г) = s2(J) + 1, J = ° 1,... /г - 1, (3.6)

(3.7)

s2(J + Г) = s2(J), 2 = Г/Т + ^..., - 1.

/ В^ O \

Так как B^+i = ) ) , то нужно проверить формулу (3.5) для каждо-

\ жВ^ В^ /

го из четырех блоков матрицы B^+i. Пусть, например, г < 2 < 2т и 0 < j < г.

Запишем (3.6) как s2(^ — г — j) + 1 = s2(^ — г — j + г) = s2(^ — j). Тогда по

59

индуктивному предположению получаем

Ф+Ъ'))=

0 иначе

Ж - Ж^(/ т '), если (2 - г - J) ф J = 2,

0 иначе

^S2(/ '), если (2 - j) ф j = 2,

(3.8)

Аналогичная проверка для остальных блоков может быть проведена с использованием (3.7) вместо (3.6).

По классической теореме Куммера [30] для натуральных чисел t и s выполнено равенство t ф s = t + s тогда и только тогда, когда биномиальный коэффициент является нечетным, отсюда

^s2(,^7'), если Q) = 1 mod 2,

0 , иначе

(в первом случае мы воспользовались тем, что 2 - j = ((2 - j) ф j) ф j = 2 ф j).

Это объясняет структуру «треугольника Серпинского», образуемую ненулевыми коэффициентами матрицы (ж),ж = 0, например,

/ 1 0 0 0 0 0 0 0

ж 1 0 0 0 0 0 0

ж 0 1 0 0 0 0 0

В4(ж) = 2 ж2 ж ж 1 0 0 0 0

ж 0 0 0 1 0 0 0

2 ж2 ж 0 0 ж 1 0 0

ж2 0 ж 0 ж 0 1 0

\ ж3 2 ^2 2 ^2 ж 2 ж2 ж ж 1

60

Из (3.4) следует, что В^(ж)В^(-ж) = В^(0) - единичная (^ х ^-матрица.

Пусть t > s > 1. Имеем

Е(-1)'2<*-''[( 7=0 mod 2] )+S2<'^"') = = (в,(-.)),,^(В,М),„ = (в,(0)),,, = 0 (3.9) 7=0

Равенство Е^ш/ = 0,^ = 1/2, проверяется аналогично:

Ей, = Е [(р

7=0

mod 2] • (-a)S2<'-^''E^,(B,(-.)),,^as2<^'' = 0.

7=0

Вычислим 2-норму:

))2 = Елд(^?)2 = с°Ею(^/ ) = c°v

(^t,^t) = Е^ - Е2^ = 1 - а2В

П

3.2. Полиномы Кравчука как эргодические суммы для

цилиндрических функций

Найдем явную формулу для частичных сумм В^ функции ш/, t G N.

Для пути = (<^i,..., ^^), ^^ G {0,1}, в графе Паскаля обозначим через В натуральное число, равное числу s2(^) = X^=i ^7' единиц в нем, а через 1 В В < В - - - < координаты единиц в пути ^. Графически, путь соединяет вершины (0, 0) и (н, ^) = (н, н-^1) графа Паскаля. В части 2.3 было показано (см. формулу (2.4)), что номер в лексикографическом порядке2 num(^) пути равен Y2 (^-+1.

j=1

2

т.е.

номер этажа в башне

61

В случае графа Паскаля верно и обратное: для любого ж G N существуют и единственны целые числа > а;-' > - - - > а;-g 0, такие, что ж = (^) + (^1) + ''' + (^g). В существовании легко убедиться, используя

«жадный алгоритм»: возьмем а; максимальным натуральным, таким, что ж Q); на следующем шаге заменим ж на ж - Q), а на - 1 и будем продолжать, пока не получим ноль (в силу того, что =1, что, вообще говоря, неверно для обобщенных биномиальных коэффициентов). Единственность проверяется по индукции. Такое представление натурального числа ж называют биномиальным разложением, или ^-каскаДом (см., например, [31], главу 10.4). Нам удобно записывать наименьшее слагаемое Qtg) как Д-S , Д-S-1

Y2 Cg----') = Y2 СдГ---') + 1, что позволяет установить путь = (^)", '=0 g ' '=0 g '

по его номеру ж = Num(^), записанному в виде ^1 -каскада следующим обра-Д1-1

зом: если ж = Y2 ("-g') + 1, то путь (^/)[=1 имеет координаты

'=0 1 '

j 1, / = % - 2' + 1, 0 < J < ^1 - 1, = <

) 0, иначе.

Отметим, что при j =0 имеем ("J0) = = ж^0,;,", что соответствует

пути (0,0 ... 0,1,1, ..., 1,0, 0 ..., 0). Отметим также, что используя биноми-

Д-! "-Д=Д1 !

альное разложение сумм num(^) и num(^) + г можно задать т-ую итерацию

автоморфизма Паскаля ^,r G N.

В силу существования ^'-каскаДа, мы можем определить функцию , изначально заданную равенством (2.6) на путях из , на натуральных числах ж = Num(^):

Пусть т,ж,^ - целые неотрицательные числа, удовлетворяющие неравенствам 0 < m < ^, 0 < ж < ^. Обозначим через ^т(ж,^,^) ненормированные

62

полиномы Кравчука дискретной переменной ж, определенные с помощью сле-

дующего равенства:

КДщщп) = 2F1

—ж, —m 1

—н у

(3.11)

где 2Ki - гипергеометрическая функция Гаусса. Нормированные полиномы

Кравчука рДД = р^ДД = Q) 2F1

—ж, —^ 1 —% '

могут быть заданы с помощью

производящей функции

1 — 3

3

ФДжщ ) = (1 + ь )^—^(1 — ж )^

где а =

(3.12)

Предложение 8. Для функции Д, 0 < t < 2^, сумма КД(ж^,^,^), гДе =

Q—)), 0 < 2 < min{^,n — ^} > К, выражается следующей формулой:

ДщД = (—2у)^К^(^ — 2, у, н — 2) - (3.13)

гДе т = s2(t).

Доказательство. Будем считать, что функция Уолша является произведением rn = s2(t), 1 < rn < К, различных функций Радемахера ф[ . В силу

:=1

цилиндричности, функция : Г {—1,1} определена уже на конечных пу-

тях из множества л^у, н > К, путей длины н в графе Паскаля, ведущих из вершины (0,0) в вершину (н, Д. Положим Д равным н — ^. Пусть натуральное число ж = Q) + (^Д) +----+ (^Д) задает конечный путь (^^))Д G л^,^,

такой, что = 0 для 1 < у < К. Тогда биномиальное разложение числа ж удовлетворяет свойству (ж) > К. По определению, число КД (ж) рав-

но сумме значений на всех путях из множества л^у, не превосходящих в лексикографическом порядке пути ж.

Разобьем все пути из множества л^д на два класса, в соответствии с тем, какое значение (1 или —1) принимает на них функция *щ. Каждый путь щ в свою очередь, разобьем на 2 части: начало Д длины К и хвост Д длины

63

Q) - N, так, что = (<х^,^^^). Путь <х' заканчивается в одной из вершин (Җу), 0 у N, и полностью определяет значение функции на всем пути <х. Количество путей из первого класса, ведущих из вершины (0,0) в фиксированную вершину (Җу), дает следующая комбинаторная лемма.

Лемма 5. Пусть Для натурального П заДаны 1 < т < П различных натуральных чисел {%,}/=!, таких, что 1 < н, < П. Число 4%^ өектороө (r1,...,rJ), состоящих из П еДиниц и минус еДиниц, уДозлетзоряющих Двум условиям:

1. П/=1 = 1, 1 7V, 1 2 т;

2. число еДиниц среДи г,, при 1 2 П, разно у,

разно

биномиальные коэффициенты ДоопреДелены нулем.

Первое условие гарантирует то, что функция ш^(^^) (^^) равна

/=1

единице (и, тем самым, путь действительно из первого класса), а второе условие — то, что путь ведет в вершину (Җу).

Пути из второго класса, ведущие в вершину (Җу), - это все оставши-

Количество хвостовых путей <х" считается по приведенной выше формуле

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

64

Частичная сумма Т/Д(ж), согласно формуле (1.1), задается равенством

сп м = Х . Ғ (^)

^'=0

С)

(3.14)

где 0 $1 ж $

и а^,-,(ж) > W,

в котором правая часть зависит лишь только от N и rn, но не от индек

са Т (Очевидно, что му G F^ влечет, что G ҒД при F > TV. Поло

жим индекс равным 2^ — 1. В силу зависимости (ж) только лишь от m и F, для натуральных аргументов ж, удовлетворяющих соотношению

а^—з(ж) > — s > Ғ^, мы получим тождество фф(ж) = (ж). Поэтому

ниже мы будем полагать, что Т = Ғ. Тогда

ю = Х(-1)'"-Ч

J=0

а^1—^(ж) > rn.

(3.15)

Для функции ш/, ^ = 1/2, (напомним, что, согласно равенству (3.2), эти функции линейно выражаются через функции , 0 < j < Т следующим образом: ш/ X) , где коэффициенты ф = (ф (1 — 2^ф—фц G N) коэффици-

^=0

енты

виде

X) в аналогичном выражении суммы Т/ / выражаются в

^=0

m—j

= (—29)Д7) (Уф ' = (—29)Д7)

Первое равенство следует из элементарного тождества ф) (—1)^'= ^=0

(—2^)^(—а)^—,а = .

Записывая тождество (1+ с)"*—(1 — от) = (1+ т)^— (1 — а^)^' (1+ т)"*—и приравнивая коэффициенты при F, получаем следующее представление для полиномов Кравчука:

Pt,^.(m) = ф (mj (_J) .

Пользуясь тождеством (rn,^,F), запишем полученное ра-

65

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

Е К,.(Г 9, ) (^^ —(() = 9, Л Q).

Полагая N = rn, мы приходим к следующему выражению для функции q m q .

j=0

Х(-29)Д";) Xm.(9,9, ЮЦ'.Д) = (-29 )m^m.(&', 9-"') (,

J =0

в котором необходимо положить н' = % — ц Ц = — 2.

в

/

Замечание 9. Для ж = Y2 Q—?*-), где (^0,21,... ,^/—i) - возрастающая последо-j =о 1 J

вательность, такая, что G N и — у > 0 при 0 у / — 1, / < ^1 — F,

сумма (ж) равна

/

(^) ^2(—2^)m^m(^ — й — J- 9- — й) -

J=0

/н — зА ^i — J.

(3.16)

Следующий результат показывает, что для автоморфизма Паскаля ко-гомологичные константе функции у G F^ могут быть описаны в терминах проекций:

Теорема 9. Цилиндрическая функция у, принадлежащая пространству F^ - когомологична константе тогДа и только тогДа, когДа Для всякого т, 1 т ,

cov-щ (^, Ү2 ) = 0,

t:s2(t)=m

гДе через s2(t) обозначено число еДиниц в Двоичном разложении номера t.

Доказательство. Можно считать, что E^qу = 0. Разложим функцию у в сумму Фурье S*2w (у) ^12 . Для ж удовлетворяющих условиям равенства

t=0

66

(3.14) имеем:

где = ( '=с Y2 = 0, 0 < j < N. Из этого представления следует

t:s2(t)=w

ограниченность частичных сумм функции (ж) на 0 ж Q) и, в силу