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

Содержание к диссертации

Введение

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

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

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

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

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

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

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

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

2.5. Сходимость при — оо отношений dim( — ,n)/dim(,n) размерностей вершин 35

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

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

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

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

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

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

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

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

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

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

Заключение

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

Введение к работе

Актуальность работы.

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

Индивидуальная эргодическая теорема является центральным результатом в эргодической теории. Рассмотрим автоморфизм Т, заданный на пространстве X с инвариантной мерой /і. Пусть д - суммируемая функция, х Є X, {fiJiLo - числовая последовательность, элементы которой определены значениями функции д вдоль траектории точки ж, fi = д(Т^гх). Тогда для /і-п.в. х существует предел

_, п—1

1 ^—V

lim — > ji.

n-^oo fi ²-—' г=0

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

п

S(n) = S^(n) : S(n) = ^2 fi{^x)i 1 — ⁿ < +₅ исследуют вопрос о существовало нии нормирующей последовательности коэффициентов г_п, такой, чтобы рас-

S(n)

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

Ті

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

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

нашли замечательную новую сторону этой проблемы. Она заключается в возможности стабилизации поведения специальным образом нормированных конечных последовательностей растущей длины частичных сумм ограниченных функций вдоль индивидуальных (односторонних) траекторий автоморфизма. Такой взгляд на эту проблему позволил на примере автоморфизма Паскаля проиллюстрировать новый подход, который отличается от рассматриваемых ранее тем, что возникающий предельный объект, получивший название предельной функции, имеет не стохастическую, а детерминистическую природу. Предложенный Т. де ла Рю, Э. Жанврес и И. Веленик в работе [] объект может быть определен, вообще говоря, для произвольной числовой последовательности (i)^₀. Для этого рассмотрим последовательность ее частичных сумм () и, считая (0) = О, доопределим ее с помощью линейной интерполяции на нецелые неотрицательные значения аргумента. Доопределенную таким образом непрерывную функцию обозначим через . Рассмотрим последовательность непрерывных функций _п : [0,1] —> [—1,1], получаемых следующей перенормировкой функции :

i ) — ()
_n() = ,

где нормирующие коэффициенты _n канонически выбраны равными max \( ) — ()\. Поскольку _п(0) = _п(1) = 0, функцию _п есте-

ІЄ[0,1]'

ственно назвать мостом. Нас интересует множество предельных точек последовательности _п в равномерной метрике на [0,1].

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

обозначать через

Определение 1. Если для выбранных функции и точки Є существует такая последовательность ^{) Є N, что последовательность непре-рывных функций _]9( s сходится к (непрерывной) функции ^y в равномер-

x^iji ух J

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

l_n = l⁹_n(x) — стабилизирующей последовательностью, а последовательность H_n = К ,g, ч — нормирующей последовательностью. Непрерывным предель-

X₁l_n уХ j

ным мостом автоморфизма (X, Т) для функции g в точке х называется четверка (х, (/_п) ,, (R_n) _₁₅ty?).

Отметим, что сходимость по Чезаро последовательности (f_n)_n влечет для нормирующего коэффициента R_n соотношение R_n = o(l_n).

Определение 2. Непрерывный предельный мост [х,[1_п) ,, [Н_п) __v(p для функции g в точке х назовем существенным, если для любого є > 0 выполнено соотношение (/_п) = o(R_n).

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

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

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

Пространством, на котором задано адическое преобразование, является (под)множество путей (последовательностей ребер) бесконечного градуиро-

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

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

Чтобы получить интересные результаты, необходимо ограничиться некоторым классом адических автоморфизмов. Мы опишем диаграммы Браттели специального вида и зададим адический порядок на путях. Рассматриваемые нами диаграммы могут быть заданы производящим полиномом р{х) = <2о + сых + a,d%^d степени d Є N U {0} c натуральными коэффициентами а,і,0 < і < d, которые задают число ребер, соединяющих произвольную вершину (п,к) с (п + 1, к + г)-ой вершиной следующего уровня. Данные диаграммы являются самоподобными, т.е. изоморфны (как упорядоченные градуированные графы, определение дано ниже) диаграммам, получаемым при сдвиге корневой вершины в любую из нижележащих. Множество путей в графе Браттели В обозначим через Х_р. На классах кофинитных путей можно задать естественный (ко)лексикографический порядок ^, который определяет адический автоморфизм Т_р. При р(х) = ао,йо > 1, получаемый таким образом автоморфизм Т_р является реализацией стационарного одометра. При d = degp > 1 получаемые автоморфизмы являются нестационарными, они получили название полиномиальных адических автоморфизмов и изучались в работах К. Мела [] и C. Бейли []. Наш подход к определению полиномиальных адических автоморфизмов является менее ограничительным: мы не ограничиваемся рассмотрением единственного «канонического» порядка, рассматривавшегося в работах [] и []. Класс полиномиальных адических

автоморфизмов включает в себя (при() = 1 + ) знаменитый автоморфизм Паскаля (, ), = {0, 1}⁰⁰. Согласно теореме де Финетти, множеством инвариантных эргодических мер автоморфизма является семейство мер Бернулли

_q = Y[(, 1 ~). Важно отметить, что попытки исследовать и обобщить свой-

1 ства автоморфизма Паскаля являлись мотивацией для определения понятия

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

рассматриваются в данной работе, включает в себя класс полиномиальных

адических автоморфизмов и стационарных одометров.

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

Теорема. ([], теорема 2.4.) Пусть (,,_q), Є (0,1), - автоморфизм Паскаля, а- цилиндрическая функция. Тогда для q-п.в. предельная функция ⁹_x Є [0,1] существует тогда и только тогда, когда функция не когомологична константе.

Также для функций, коррелирующих с простейшими цилиндрическими функциями і() = 1{_ж.₌₀}, где = (j)^L₁ Є , авторы [] показали, что почти всюду предельной кривой является обобщенная кривая Такаги Т¹. (Определенная в работе [13] функция Такаги совпадает с функцией ¹₂Ту₂.)

Теорема. ([, теорема 2.5.) Для цилиндрических функций , удовлетворяющих условию Ylt^1 covM_g(,*) > 0, среди предельных функций содержится

функция Тд¹.

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

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

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

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

Научная новизна. Все основные результаты диссертации являются новыми. Теорема 6 обобщает основной результат работы [].

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

Методы исследований.

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

Основные положения и результаты, выносимые на защиту:

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

2. Доказано, что для полиномиальных адических систем данное условие является необходимым и достаточным.

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

4. Для автоморфизма Паскаля исследована комбинаторика цилиндрических функций и получено выражение частичных сумм через полиномы Кравчука.

5. Исследовано асимптотическое поведение полиномов Кравчука.

6. Доказана гипотеза Т. де ла Рю, Э. Жанврес и И. Веленик о появлении в качестве предельной кривой обобщенной кривой Такаги для цилиндрических функций.

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

Публикации. Основные результаты диссертации опубликованы в шести печатных работах в рецензируемых журналах [–] из Перечня ведущих рецензируемых журналов и изданий ВАК.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, библиографии и приложения. Общий объем диссертации 86 страниц. Библиография включает 39 наименований на 4 страницах.

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

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

1. Множества вершин V и ребер Е являются градуированными множествами, т.е. являются счетным объединением попарно непересекающихся конечных множеств: V = U L0Vn, Е = U L0n, а множества Vn и Еп конечны для всех уровней п.

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

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

Для удобства обозначений, мы считаем, что на каждом уровне множество Vn состоит из () + 1 вершины, которые занумерованны слева направо индексами от нуля до (). Определим отображение : 8 — V задающее по ребру его конец, а также отображение 8 — V, задающее его начало. Последовательности ребер {п)( =1, такие, что конец -го ребра является началом ( + 1)-го, составляют пространство = (V,8) путей диаграммы . Пусть Vjik 0 такие числа, что п + 1 равно входящей степени вершины (,). Мы будем считать, что ребра, входящие в вершину (,), помечены индексами 0,1,..., п .

Согласно классическому определению А. М. Вершика, введенному в основополагающей работе [15], мы предполагаем, что на множестве ребер l (), входящих в вершину Є V с координатами (, ), 0 (), 1, определен линейный порядок щк. Данные линейные порядки щк задают частичный порядок - на множестве ребер V. Порядок - индуцирует (ко)лексикографический порядок на классах кофинитных путей (т.е. путей, лежащих в одном классе хвостового разбиения) и, тем самым, частичный порядок на всем пространстве путей . Несколько перегружая обозначения, полученный частичный порядок на мы также обозначаем через - . Упорядоченной диаграммой называется пара (, ).

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

Замечание 1. Преобразование определено всюду кроме (не более чем) счетного множества максимальных путей тах, а обратное преобразование 1 определено всюду кроме (не более чем) счетного множества минимальных путей Хт[п. Адический автоморфизм Т : X \ Хтах — X \ Хт[п является гомеоморфизмом в естественной канторовской топологии. Мы будем считать, что адический автоморфизм задан на множестве X \ (Xmax U Xmin).

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

Для пути со обозначим через кп(со) номер вершины уровня п, через которую проходит данный путь. Для конечного пути с = (ci,...,cn), ведущего из начальной вершины (0,0) в вершину (п,к), число кп(с) будем коротко обозначать через к(с). Цилиндрическое множество ранга п вида С = [с\С2... сп] = {со Є X\coi = Сі, о;2 = C2,...,o;n = cn} определяется конечным путем с = (сі, С2 , сп), ведущим из вершины (0,0) в вершину (п,к) = (п,к(с)). Число таких путей (размерность вершины) (п,к) мы будем обозначать через dim(n,&) или, короче, Нп . Множеству тгп конечных путей с = (сі, С2, сп), к (с) = п, упорядоченных в лексикографическом порядке, соответствует упорядоченное множество цилиндров тП;й, составленное из соответствующих цилиндров, которые удобно обозначать через Tnyk(j), 1 J dim(n, к). Множество тп образует башню автоморфизма, множество башен {тп,к\к=о фиксированного уровня п определяет аппроксимацию автоморфизма Т, см. [14], [16], [21]. Номера этажей башни — это номера путей в лексикографическом порядке. Номер пути со Є тіщк обозначим через Num((x ). Очевидно, что номер Num( x ) пути со Є тіщк лежит в пределах от единицы до dim(n, к).

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

Представление (2.8) числа Є [0,1] будем называть обобщенным -адическим -представлением (или, короче, -представлением), а в случае, если компоненты вектора имеют вид i = -,1 — симметричным -представлением. Для симметричного -представления функция () = , 0 . В частном случае = 2, симметричное -представление является обычным диадическим представлением числа на отрезке [0,1].

Как отмечено выше, точки из пространства = Vi(J можно рассматривать также как пути в дереве Л4Г. Обозначим через Q объединение т&х,а U тіП;СГ множеств максимальных и минимальных путей, а через — множество всех -стационарных точек на интервале [0,1] в симметричном представлении. Формула (2.8) задает каноническую биекцию : \ Q — [0,1] \ , переводящую путь = (і, 2, . . ., п ...) Є в точку интервала [0,1]. Отображение переносит меру q, Є (0,1), заданную на пространстве , в меру q на [0,1], семейство башен {п к} =о переводит в набор \n,k}Vk=o семейств дизъюнктных интервалов, концы которых являются стационарными точками ранга в симметричном -разложении. Это позволяет задать (изоморфную) реализацию Vi(J полиномиального автоморфизма Vi(J на множестве [0,1] \ . Отметим, что интервалы, составляющие башни п , кодируются конечными путями из множеств П;й.

Подобное представление может быть получено для любого адического автоморфизма (хотя возможность получения явного регулярного выражения, аналогичного выражению (2.8), является, конечно, следствием самоподобия диаграммы Браттели полиномиальной системы). В англоязычной литературе такое представление автоморфизма часто называют «cutting and stacking» конструкцией.

Положим в определении выше вектор р = (pj(q) ) _0 равным вектору tl tl t td (т q,. .., q,tq,. .. ,tq, —,...,—,... , J1 ,..., J1, заданному согласно след Ьо Ьі ч v Ч v ствию 1 теоремы 4 производящим полиномом р(ж) = ао+аїх Ь а , 6г = ttd-ijO і (і. Данную запись числа ж Є [0,1] назовем обобщенной g-r-адической записью, заданной полиномом р(х) и подстановкой а (или же, короче, g-r-адической записью). Обозначим через Gq множество стационарных чисел в такой записи.

Приведем пример g-r-адической записи для случая канонического порядка (т.е. тождественной подстановки а = id). Через &j,0 i r — 1, обозначим r-мерный вектор (0, 0,..., 0,1,1,..., 1,0,0,..., 0), а через е , 0 і г — 1, 5=о bj bi T,dj=i+ibj обозначим r-мерный стандартный орт. Через и v обозначим скалярное произведение векторов. Для данного выбора р = (pj(q) ) -_0 представление (2.8) запишется следующим образом: 00 , bvs-+2bo-s--\ \-db,i-s х=} I„{(jjj)qH — \ , (2.9) где Iq(w) = 6о4тг + &і йт + hf + s при w; = 6, + s,0 s bh+h0 h d

Замечание 5. Множество Gq можно получить и несколько иным способом: напрямую из множества стационарных чисел G\/r в симметричной системе счисления. Пусть Fj2 — функция распределения меры jiq на интервале [0,1]. Тогда Gq = {у\у = Fp{x),x Є Gl/r}. 2.5. Сходимость при п —оо отношений dim(n — I, кп)/ dim(n, кп) размерностей вершин. В этой части будет показано, что при фиксированном / Є N точки г -элементного вектора Кп_і п после нормировки делением на размерность Hn,kn = Ср(п,кп) вершины сходятся при п -л оо к компонентам вектора G1, содержащего g-r-рациональные числа ранга / интервала [0,1].

Пусть х Є X — некоторый случайный бесконечный путь, выбираемый согласно мере \iqiq Є (0,1/а ). Всюду ниже, для краткости, последовательности вершин (п,кп(х)), выбираемые согласно пути ж, мы записываем просто как (п,кп) или даже (п,к). Не умаляя общности, мы можем считать, что дп кп (d — д)п для некоторого 5 0.

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

Найдем явную формулу для частичных сумм n\ функции , Є N. Для пути = (і,..., п), і Є {0,1}, в графе Паскаля обозначим через \ натуральное число, равное числу i{) = X =i з единиц в нем, а через 1 \ kx координаты единиц в пути . Графически, путь соединяет вершины (0, 0) и (, ) = (, —\) графа Паскаля. В части 2.3 было показано (см. формулу (2.4)), что номер в лексикографическом порядке2 num() пути п—к равен 2 (j ) + 1. J=I J 2 т.е. номер этажа в башне тп & В случае графа Паскаля верно и обратное: для любого ж Є N существуют и единственны целые числа а a-k-i a-k-s 0, такие, что х = (Т) ilk-i) + + (T-s) . В существовании легко убедиться, используя «жадный алгоритм»: возьмем а,к максимальным натуральным, таким, что х ( ) ; на следующем шаге заменим х на х — ( ) , а к на & — 1 и будем продолжать, пока не получим ноль (в силу того, что (Q) =1, что, вообще говоря, неверно для обобщенных биномиальных коэффициентов). Единственность проверяется по индукции. Такое представление натурального числа х называют биномиальным разложением, или к-каскадом (см., например, [31], главу 10.4). Нам удобно записывать наименьшее слагаемое (кк ) как V /afc_s-l-7 v /afc_s-l-7\ ,1 / \n Z { k-s- ) = Z- { k-s- ) что позволяет установить путь UJ = {0Jj){, по его номеру x = Num(w), записанному в виде &і-каскада следующим обра ki-l зом: если х = 2 (к -) + 1, то путь (ui)f=1 имеет координаты з=о 1 3 ! lj = n-ij + l,0 j ki-l, 0, иначе. Отметим, что при j = 0 имеем (П ) = ( 1 ) = хг0,к,т что соответствует пути (0,0 ... 0,1,1,..., 1,0, 0 ... , 0). Отметим также, что используя биноми к-г п-к=кх і альное разложение сумм num( x ) и num( x ) + г можно задать r-ую итерацию автоморфизма Паскаля Ргш, г Є N.

В силу существования к\-каскада, мы можем определить функцию dk J, изначально заданную равенством (2.6) на путях си из 7гП;й, на натуральных числах х = Num( x ): aNj, ч akl-N , akl-i-N akl-s-N {x] = U - з U -1 - J U - в -з- (3.10) Пусть ,, – целые неотрицательные числа, удовлетворяющие неравенствам 0 , 0 . Обозначим через (,,) ненормированные полиномы Кравчука дискретной переменной , определенные с помощью следующего равенства: m(,,) = 21\-, -;-j, (3.11) где 21 - гипергеометрическая функция Гаусса. Нормированные полиномы Кравчука () = ,() = 21 производящей функции -ж, -т. 1 -п q могут быть заданы с помощью S n(,) = (l + )n-x(l-)x, где =- . (3.12) Я. Предложение 8. Для функции l, 0 2N, сумма k{i ,n), где к,п = (k--i) , 0 — ,min{, - } , выражается следующей формулой: k{hk:n) = {-2)mm( -,,-)- гАп, (3.13) где = S2(). Доказательство. Будем считать, что функция Уолша t является произве т дением = S2(), 1 , различных функций Радемахера YI щ. В силу г=1 цилиндричности, функция : — {-1,1} определена уже на конечных путях из множества П;й, , путей длины в графе Паскаля, ведущих из вершины (0,0) в вершину (, ). Положим 1 равным - . Пусть натуральное число = (,fc1) + (tf1 11 ) + {Т1 -8) задает конечный путь {j)v-=1 Є П;й, такой, что j = 0 для 1 . Тогда биномиальное разложение числа удовлетворяет свойству -i) . По определению, число k() равно сумме значений t на всех путях из множества П;й, не превосходящих в лексикографическом порядке пути .

Разобьем все пути из множества П;й на два класса, в соответствии с тем, какое значение (1 или -1) принимает на них функция f. Каждый путь , в свою очередь, разобьем на 2 части: начало длины и хвост " длины 2 — N, так, что со = (u/,и/ ). Путь со заканчивается в одной из вершин (N,j), 0 j N, и полностью определяет значение функции Wt на всем пути со. Количество путей со из первого класса, ведущих из вершины (0,0) в фиксированную вершину (N,j), дает следующая комбинаторная лемма.

Лемма 5. Пусть для натурального N заданы 1 т N различных натуральных чисел {nj}1; таких, что 1 ГІІ N. Число Jff векторов (гі,... ,гдг); состоящих из N единиц и минус единиц, удовлетворяющих двум условиям: 1. YULi гщ = 1, 1 N, 1 і ш; 2. число единиц среди г І, при 1 і 7V, равно j, равно Е Ґт\ ( N — т \ 2Z АГ — 7 — 2Z , /:0 2/ га J биномиальные коэффициенты доопределены нулем. т Первое условие гарантирует то, что функция Wt(co ) = Y[ гщ{ш ) равна г=1 единице (и, тем самым, путь со действительно из первого класса), а второе условие — то, что путь со ведет в вершину (N,j).

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

Теоретико-числовая интерпретация. В теории чисел известной задачей является поиск явной формулы для суммы 1 Sg(N) = J2g(s2(n)) n=0 при заданной функции д : N — Ш. В классическом случае, когда д(у) = у, ответ представляется формулой Троллопа-Деланжа, см. работу [34]. В современных работах [27] и [35] рассмотрены случаи о (у) = (у) ,т 0, о (у) = ут и даже g(y,t) = exp(ty). Оказывается, что Sg(N) в каждом из этих случаев имеет явное выражение, ключевой частью которого являются линейные комбинации функций Т?, к 1, 0 q 1.

Графики линейной комбинации Т} и Т? возникают как предельные кривые автоморфизма Паскаля. Отметим, что так как башню тп автоморфизма Паскаля можно рассматривать как набор натуральных чисел {j : S2(j) = к} (см., например, [1]), упорядоченных по возрастанию, то изучаемые нами частичные суммы F k равны «условным суммам»: J2 9(Э), (Kj 2, s2(j)=k где функция д зависит от конечного числа младших разрядов в диадической записи натурального j.

Функции Уолша используют в качестве удобного ортогонального базиса в теории булевых функций. Через 1п обозначим множество вершин единичного куба {0,1}п. Пусть Вп - множество булевых функций / : 1п — {0,1}, а Sn - множество симметричных булевых функций от п переменных, т.е. таких функций /(ж), х = (xi, Х2 хп) Є Іп, которые принимают одно и то же значение на всех векторах х постоянного веса \\х\\ = S2{x). Спектром Уолша4 функции / Є Вп называется вектор (q)t=Q коэффициентов Фурье по системе Уолша {wt}t=Q в пространстве Ь2({0,1}п, /І1/2) с равномерной мерой Ml/2: cf =J2f(x)wt(x). хЄІ„ Симметричная функция / Є Sn полностью определяется двоичным вектором / = (/o,/i,...,/n), где fk = f(x) при ж = k,к = 0,1,...п. Спектр Уолша симметричной функции, лежащей в пространстве L2({0,l}-,/i1/2), может быть выражен через симметричные многочлены Кравчука: lb lb cf = J2fk Yl wJ = J2(-1)mlKni(kA/l2 i)-fk, (3.28) где т = S2(t).

Если вместо пространства L2({0,l}-,/i1/2) рассмотреть пространства L2({0} 1}п} fiq)}q Є (0,1), с метрикой, заданной мерой Бернулли fiq, то аналогом базиса Уолша окажется ортонормированный базис {wf/wf І2}г=о , заданный выражением (3.2). Из соотношения (3.13) следует, что спектр Уолша (q)t=Q симметричной функции / Є Sn по системе { /Н ЦЫ о может быть выражен через многочлены Кравчука Km(k,q,n) следующим образом: Cl = J2 \ 2q \2т{1)К к П) Л Ш = S2 ) (3.29)

Лексикографический порядок, на котором основан автоморфизм Паскаля, напрямую связан с комбинаторными теоремами Маколея и Кру-скала-Катона. Обозначим через U множество {1,2...,п}; подмножества

На практике для функций Уолша часто используют нумерацию Адамара, вместо нумерации Уо-лша-Пэли, используемой в этой работе. множества U удобно отождествлять с векторами из {0,1}п. Пусть А С {0,1}п - некоторое семейство векторов (подмножеств U). Тенью дА семейства А называется множество всех векторов, получаемых из векторов множества А заменой одной из единиц на ноль. Предположим, что семейство векторов А является / -регулярным, что значит, что каждый вектор семейства состоит в точности из к\ единиц и, соответственно, к = п — к\ нулей.

Естественным вопросом является вопрос об устройстве т-элементного семейства А с наименьшей тенью.

Теорема Маколея [36] утверждает, что m-элементное семейство А векторов с наименьшей тенью представляет собой первые т векторов сечения куба {0,1}п по векторам с к\ единицами, упорядоченного в лексикографическом5 порядке, а в теореме Крускала-Катона [37, 38] найдена формула для вычисления мощности тени семейства А . Другими словами, семейством А являются первые т путей длины п из башни тп автоморфизма Паскаля. Используя введенные выше обозначения, теорему Крускала-Катона можно записать как неравенство (которое достигается на множестве А ) \дА\ дк А, где через обозначена мощность множества, а функция дк ,J() была задана выше соотношением (3.10).