Математический сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Математический сборник, 2022, том 213, номер 6, страницы 71–110
DOI: https://doi.org/10.4213/sm9682
(Mi sm9682)
 

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Самоподобные 2-аттракторы и тайлы

Т. И. Зайцеваab, В. Ю. Протасовcb

a Московский центр фундаментальной и прикладной математики
b Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова
c University of L'Aquila, Italy
Список литературы:
Аннотация: Исследуются 2-аттракторы в пространстве $\mathbb R^d$ – самоподобные компакты, заданные двумя сжимающими аффинными операторами с одинаковой линейной частью. Они широко изучались в литературе под разными названиями (двухциферные тайлы, двойные драконы, 2-рептайлы и т.д.) в связи с приложениями в дискретной геометрии, теории чисел и теории приближений, для построения базисов Хаара и всплесков (вейвлетов) многих переменных. В работе получена полная классификация изотропных 2-аттракторов в $\mathbb R^d$ и показано, что все они гомеоморфны друг другу, но не диффеоморфны. В общем неизотропном случае доказано, что 2-аттрактор однозначно с точностью до аффинного подобия определяется спектром матрицы сжатия. Приведены оценки на число различных 2-аттракторов в $\mathbb R^d$, для чего исследованы целые унитарные растягивающие полиномы со свободным коэффициентом $\pm 2$. Их количество оценивается с помощью меры Малера. Построено несколько серий таких полиномов. Для некоторых 2-аттракторов вычислены показатели их регулярности по Гёльдеру. Часть результатов обобщена на аттракторы с произвольным количеством цифр.
Библиография: 63 названия.
Ключевые слова: самоподобные аттракторы, тайлы, система Хаара, целочисленные полиномы, устойчивые полиномы.
Финансовая поддержка Номер гранта
Фонд развития теоретической физики и математики "БАЗИС"
Российский фонд фундаментальных исследований 20-01-00469-а
Исследование Т. И. Зайцевой выполнено при поддержке Фонда развития теоретической физики и математики “БАЗИС”. Исследование В. Ю. Протасова выполнено при поддержке Российского фонда фундаментальных исследований (грант № 20-01-00469-а).
Поступила в редакцию: 26.10.2021
Англоязычная версия:
Sbornik: Mathematics, 2022, Volume 213, Issue 6, Pages 794–830
DOI: https://doi.org/10.1070/SM9682
Реферативные базы данных:
Тип публикации: Статья

§ 1. Введение

Самоподобные аттракторы в $\mathbb R^d$ – компактные множества, определенные целочисленной $(d\times d)$-матрицей $M$ и множеством целых векторов (“цифр”) $D=\{\boldsymbol d_0, \dots, \boldsymbol d_{m-1}\}\subset \mathbb Z^d$, где $m=|\operatorname{det} M|$. При этом матрица $M$ предполагается растягивающей, т.е. модули всех ее собственных значений больше $1$, а цифры $\boldsymbol d_i \in D$ взяты из разных классов смежности $\mathbb Z^d/M\mathbb Z^d$, т.е. $\boldsymbol d_{i}-\boldsymbol d_j \notin M\mathbb Z^d$ при $i\ne j$.

Определение 1. Самоподобный аттрактор, соответствующий целой растягивающей матрице $M$ и множеству цифр $D$, определяется как

$$ \begin{equation} G=G(M, D)= \biggl\{0.\boldsymbol a_1 \boldsymbol a_2 \ldots =\sum_{k=1}^{\infty} M^{-k}\boldsymbol a_k \colon\boldsymbol a_k \in D\biggr\}. \end{equation} \tag{1} $$

Самоподобный аттрактор является компактом с непустой внутренностью, а его мера Лебега $|G|$ – натуральное число. Целые сдвиги $\{G+k\}_{k \in \mathbb Z^d}$ покрывают пространство $\mathbb R^d$ в $|G|$ слоев, т.е. каждая точка $x\in \mathbb R^d$, за исключением множества меры нуль, принадлежит ровно $|G|$ сдвигам. В случае $|G|=1$ аттрактор называется тайлом, а его сдвиги образуют разбиение пространства в один слой (тайлинг), см. [32], [44].

Из формулы (1) следует, что аттрактор является аналогом единичного отрезка в $\mathbb R^d$ в $M$-ичной системе счисления с цифрами из $D$. Однако даже на прямой $\mathbb R$ аттрактор может быть отличен от отрезка. Скажем, в троичной системе счисления с цифрами $0,1$ и $2$ множество $G$ – отрезок, но если заменить цифру $2$ на $5$, то $G$ превращается во фрактальное множество с бесконечным числом компонент связности [60], [18]. Аналогично отрезку, аттрактор обладает самоподобием. Для любого $\boldsymbol a \in \mathbb Z^d$ обозначаем через $M_{\boldsymbol a}$ аффинный оператор $M_{\boldsymbol a} \boldsymbol x=M\boldsymbol x-\boldsymbol a, \boldsymbol x \in \mathbb R^d$. Легко показать, что $G=\bigcup_{\boldsymbol a \in D} M_{\boldsymbol a}^{ -1} G$, а поскольку мера каждого из множеств $M_{\boldsymbol a}^{ -1} G$ равна $m^{-1} |G|$, а вместе они составляют меру $|G|$, все эти множества пересекаются по мере нуль. Поэтому $G$ есть дизъюнктное (с точностью до меры нуль) объединение сдвигов множества $M^{-1}G$, т.е. $G$ действительно самоподобно. Поэтому характеристическая функция $\varphi=\chi_G$ произвольного аттрактора является масштабирующей, т.е. удовлетворяет масштабирующему уравнению

$$ \begin{equation} \varphi(\boldsymbol x)=\sum_{\boldsymbol k \in D} \varphi (M\boldsymbol x -\boldsymbol k). \end{equation} \tag{2} $$
Если аттрактор является тайлом, то функция $\varphi$ обладает ортонормированными целыми сдвигами. Следовательно, она порождает кратномасштабный анализ (КМА) пространства $L_2(\mathbb R^d)$. Поэтому тайлы применяются при построении систем всплесков, в частности базисов Хаара в $L_2(\mathbb R^d)$, см., например, [11], [16], [31], [39], [42], [60], [63].

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

Важный класс аттракторов составляют двухциферные (2-аттракторы), для которых $\operatorname{det} M=\pm 2$. В этом случае $m=|D|=2$, и $M$-ичная система в $\mathbb R^d$ аналогична двоичной системе на прямой. В частности, каждый аттрактор $G$ распадается на две подобные ему копии $M^{-1}(G+\boldsymbol d_0)$ и $M^{-1}(G+\boldsymbol d_1)$, а масштабирующее уравнение (2) содержит всего два слагаемых. Система Хаара имеет единственную порождающую функцию $\psi(\boldsymbol x)=\varphi(M\boldsymbol x-\boldsymbol d_0)-\varphi(M\boldsymbol x-\boldsymbol d_1)$ (напомним, что в общем случае система Хаара имеет $m-1$ порождающих функций). Аналогично с системами всплесков: в двухциферном случае они порождены единственной всплеск-функцией, а соответствующий КМА имеет двоичную структуру подобно всплескам в $L_2(\mathbb R)$. Поэтому системы всплесков, порожденные 2-аттракторами, наиболее естественны и просты в использовании.

2-аттракторам посвящена обширная литература (мы дадим краткий обзор в конце параграфа). Известно, что при каждом $d$ в $\mathbb R^d$ существует конечное число различных, с точностью до аффинного подобия, 2-аттракторов. Так, в $\mathbb R^2$ есть ровно три 2-аттрактора – квадрат, дракон и медведь, все они изотропные. В $\mathbb R^3$ существует семь 2-аттракторов, среди них только один изотропный – куб.

Основные результаты

Мы исследуем 2-аттракторы – их классификацию, геометрические и топологические свойства. Когда это возможно, мы распространяем некоторые результаты на аттракторы с произвольным числом цифр. В изотропном случае вопрос классификации удается решить полностью (§ 5). Эта классификация оказывается простой, что довольно неожиданно. В нечетной размерности $d=2k+1$ все изотропные 2-аттракторы суть параллелепипеды (теорема 3). В четной размерности $d=2k$ существует ровно три, с точностью до аффинного подобия, изотропных 2-аттрактора. Это параллелепипед, а также прямое произведение $k$ (двумерных) драконов и прямое произведение $k$ (двумерных) медведей (теорема 4). Доказательство теорем конструктивно: матрицы $M$ соответствующих 2-аттракторов находятся в явном виде.

Полученная классификация позволяет установить множество свойств изотропных 2-аттракторов. Так, мы показываем, что все изотропные 2-аттракторы в $\mathbb R^d$ гомеоморфны $d$-мерному шару, но не $C^1$-диффеоморфны друг другу. Более того, все три типа изотропных аттракторов в четной размерности не являются метрически эквивалентными, т.е. не переводятся один в другой липшицевым в обе стороны отображением (теорема 5 в § 6). Свойства выпуклых оболочек аттракторов исследуются в § 7. Оказывается, что среди всех 2-аттракторов выпуклая оболочка является многогранником только у параллелепипеда ($2^d$ вершин) и у произведения драконов ($2^{3d/2}$ вершин). У остальных 2-аттракторов выпуклая оболочка – зоноид с бесконечным множеством крайних точек.

В § 8 мы обращаемся к приложениям и показываем, что каждый изотропный 2-аттрактор является тайлом, а значит, порождает КМА и базис Хаара, при условии, что матрица $M$ и цифры $D$ выбраны подходящим образом (теорема 7 явно указывает, каким). При этом функция Хаара, порожденная произведением двумерных драконов, не совпадает с произведением двумерных функций Хаара! Аналогичные утверждения для общих (неизотропных) 2-аттракторов формулируются в виде гипотезы, которая проверяется для малых размерностей (предложение 4).

Основной вспомогательный факт о 2-аттракторах состоит в том, что они определяются однозначно с точностью до аффинного подобия спектром матрицы $M$ и не зависят от выбора цифр $D$. Это было установлено в [29]. В § 3 мы даем другое доказательство, которое позволяет распространить данное свойство на произвольные аттракторы с цифрами, составляющими арифметическую прогрессию (теорема 2). Итак, тип 2-аттрактора зависит только от характеристического полинома матрицы $M$. Более того, противоположные полиномы (т.е. характеристические полиномы матриц $M$ и $-M$) порождают один и тот же тип. В теореме 89) мы устанавливаем обратное: аттракторы, соответствующие различным и не противоположным полиномам, не аффинно подобны друг другу. Этот факт, доказательство которого довольно сложно, позволяет находить число различных (с точностью до аффинного подобия) 2-аттракторов в любой размерности $d$. Оно равно количеству различных и не противоположных друг другу целочисленных растягивающих полиномов степени $d$ со старшим коэффициентом $1$ и свободным коэффициентом $\pm 2$. Растягивающий означает, что все корни полинома по модулю больше $1$. Так мы получаем количество $N(d)$ различных 2-аттракторов в пространстве $\mathbb R^d$: $N(2)=3$, $N(3)=7$, $N(4)=21$ и т.д. В § 10 (теорема 10) мы показываем, что $C_1d^2 \leqslant N(d) \leqslant C_2 2^{d}$ (значения констант приведены в формулировке теоремы). Оценка сверху получена с помощью результата Дубицкаса–Конягина о числе целых полиномов с заданной мерой Малера [22]. Для оценки снизу мы строим серию целых растягивающих полиномов вида $p(z)=z^d+a_{d-1}z^{d-1}+\dots+a_1 z \pm 2$, содержащую квадратичное по $d$ число полиномов. До этого в литературе были известны только две серии, в обеих число полиномов линейно по $d$ [34]. В § 12 мы добавляем еще пять новых серий, среди которых одна – квадратическая. Как мы видим, нижняя и верхняя оценки на $N(d)$ далеки друг от друга. Численные результаты показывают, что по крайней мере для $d\leqslant 8$ верхняя оценка практически точна: $N(d)$ растет как $2^d$. Однако доказательство этого факта или получение более точных оценок остается открытой проблемой.

Наконец, в § 11 мы исследуем гладкость 2-аттракторов, вычисляя показатель Гёльдера в $L_2(\mathbb R^d)$ для соответствующих функций Хаара. Мы делаем это в изотропном случае при любых $d$ и в общем случае для малых $d$. Согласно полученным результатам, различные 2-аттракторы всегда имеют разную гладкость.

Краткий обзор литературы по 2-аттракторам

В работах [27], [8] были построены первые примеры и исследованы свойства 2-аттракторов. Работы [32], [31], [42], [44], заложившие основы теории аттракторов и тайлов, также уделили много внимания двухциферному случаю. Топологические свойства 2-аттракторов и комбинаторика замощений плоскости их целыми сдвигами исследовались [35], [37], [2], [9] (другие ссылки по этой теме – в § 6). В [29] было показано, что в $\mathbb R^d$ существует конечное число 2-аттракторов, с точностью до аффинного подобия, а в [34] были построены серии 2-аттракторов, число которых растет линейно по $d$. В [9] были найдены все типы в двухмерном и трехмерном случае (три и семь типов соответственно). Различным аспектам плоских 2-аттракторов посвящена монография [26] и статьи [30], [33], [52], [63]. В [42] найдены шесть типов плоских 2-аттракторов с точностью до целочисленного аффинного подобия, а в [36] эта классификация продолжена на случаи трех, четырех и пяти цифр. В [61] вычислены показатели гладкости плоских 2-аттракторов. Обобщения на нецелые матрицы и связанные с ними замощения Пизо, shift radix systems и т.д. исследовались в [40], [56].

Приложения к всплескам и смежные вопросы исследовались в большом количестве работ, упомянем здесь лишь монографии [16], [60], [51]. Также отметим другой подход к построению всплесков, не использующий кратномасштабный анализ – например, статьи [10], [11], [17], [24], [48], [49].

Больше ссылок указано нами в конкретных параграфах.

Обозначения

Мы всегда будем предполагать, что базис в $\mathbb R^d$ фиксирован, и будем отождествлять линейный оператор с соответствующей матрицей. Через $I$ обозначена единичная матрица, $p(\lambda)=\operatorname{det} (\lambda I-A)$ – характеристический полином матрицы $A$. Мы пользуемся жирными буквами для обозначения векторов и простыми буквами для обозначения их компонент, т.е. $\boldsymbol x=(x_1, \dots, x_d)$. Через $|X|$ обозначена мера Лебега множества $X \subset \mathbb R^d$.

§ 2. 2-аттракторы в $\mathbb R^2$

Мы начнем со случая $d=2$. На двумерной плоскости существует ровно три, с точностью до аффинного подобия, 2-аттрактора [9], [42], [61]. Мы будем называть их квадрат, дракон (в литературе употребляется также термин twindragon) и медведь (tame twindragon). Все они являются тайлами и все три гомеоморфны кругу [12], но не метрически эквивалентны [54]. Их разбиение на две подобные им части показано на рис. 1, а замощение плоскости их целочисленными сдвигами на рис. 2. Построение функций Хаара и систем всплесков по плоским 2-аттракторам осуществлялось в [42], [60], [31], исследование гладкости полученных функций Хаара – в [61].

Первое систематическое исследование плоских 2-аттракторов осуществлялось в [27], [8]. В [42] матрицы плоских 2-аттракторов классифицируются с точностью до целочисленного подобия. В этом случае матрицы $A$ и $B$ считаются эквивалентными, если существует унимодулярная матрица $P \in \operatorname{GL}_2(\mathbb Z)$ такая, что $P^{-1}AP=B$. Получается шесть таких классов, которые склеиваются в три класса аффинной изоморфности. В [26] также рассмотрен случай нецелых цифр и показано, при каких цифрах в каждом из шести случаев мы будем получать замощение плоскости в один слой (как у тайла).

В случае трех и более цифр задача классификации гораздо более сложная, поскольку аттрактор уже не определяется характеристическим многочленом матрицы. Однако при малых определителях $m=3, 4, 5$ в работе [36] для каждого из возможных характеристических полиномов описаны все классы целочисленного подобия матриц (но не произвольного аффинного подобия!).

§ 3. Cпектр матрицы определяет 2-аттрактор

Одно из замечательных свойств двухциферных аттракторов состоит в том, что его геометрия не зависит от множества цифр $D$. Впервые это было замечено в работе [29]. Как мы покажем в теореме 1, двухциферный аттрактор однозначно, с точностью до аффинного подобия, определяется спектром матрицы растяжения. Подобная единственность не распространяется на большее число цифр, скажем, на 3-аттракторы. Однако для некоторых специальных множеств цифр, скажем, на прогрессии, обобщение возможно (§ 4).

Начнем с того, что одну из цифр $D$ можно всегда считать нулевой. В самом деле, $\sum_{i=1}^{\infty} M^{-k}\boldsymbol d_k=\bigl( \sum_{i=1}^{\infty} M^{-k}\bigr) \boldsymbol d_0+ \sum_{i=1}^{\infty} M^{-k}(\boldsymbol d_k-\boldsymbol d_0)$. Поэтому если заменить множество цифр $\{\boldsymbol d_0, \boldsymbol d_1\}$ на $\{\boldsymbol 0, \boldsymbol d_1-\boldsymbol d_0\}$, то аттрактор $G$ сдвинется на вектор $\bigl( \sum_{i=1}^{\infty} M^{-k}\bigr) \boldsymbol d_0$. Везде далее считаем, что $ \boldsymbol d_0=0$, и теперь все зависит только от выбора $\boldsymbol d_1$.

Нам понадобится несложный вспомогательный факт.

Лемма 1. Для произвольной $d\times d$ матрицы $M$ и для произвольных точек $\boldsymbol a, \boldsymbol b \in \mathbb R^d$ таких, что $\boldsymbol a$ не принадлежит собственному подпространству $M$, существует матрица $C$, которая коммутирует с $M$ и переводит $\boldsymbol a$ в $\boldsymbol b$.

Доказательство. Перейдем к жорданову базису матрицы $M$ и рассмотрим одну жорданову клетку $\Lambda$ размера $s$, соответствующую собственному значению $\lambda$. Обозначим через $\boldsymbol a'$ и $\boldsymbol b'$ $s$-мерные компоненты векторов $\boldsymbol a$ в $\boldsymbol b$, соответствующие данной клетке. Обозначим через $\mathcal H$ множество Ханкелевых верхнетреугольных матриц размера $s$, т.е. матриц вида
$$ \begin{equation*} \begin{pmatrix} \alpha_1 & \alpha_2 & \dots & \alpha_{s-1} & \alpha_{s} \\ 0 & \alpha_1 & \alpha_2 & \dots & \alpha_{s-1} \\ 0 & 0 & \alpha_1 & \alpha_2 & \dots \\ \vdots & \vdots & \ddots & \ddots& \vdots \\ 0 & 0 & \dots & 0 & \alpha_1 \end{pmatrix}. \end{equation*} \notag $$
Заметим, что $\mathcal H$ – линейное пространство, являющееся мультипликативной полугруппой. Все элементы $\mathcal H$ коммутируют с $\Lambda$. Множество $U=\{X\boldsymbol a' \mid X \in \mathcal H\}$ является линейным подпространством $\mathbb R^s$, инвариантным относительно каждой матрицы из $\mathcal H$. Докажем, что $U=\mathbb R^s$. Если это не так, то $U$ является собственным подпространством каждой матрицы из $\mathcal H$, в частности – матрицы $\Lambda$. Поэтому $U$ совпадает с одним из пространств $U_j=\bigl\{(x_1, \dots, x_j, 0, \dots, 0)^T \in \mathbb R^s\bigr\}$ (ими исчерпываются все собственные подпространства $\Lambda$). Значит, $\boldsymbol a' \in U_j$ при некотором $j\leqslant s-1$. Следовательно, вектор $\boldsymbol a$ лежит в собственном подпространстве матрицы $M$, порожденном всеми векторами ее жорданова базиса, кроме $s-j$ последних векторов, соответствующих клетке $\Lambda$. Это противоречит условию на $\boldsymbol a$. Итак, $U=\mathbb R^s$. Значит, существует матрица $X \in \mathcal H$, для которой $X\boldsymbol a'=\boldsymbol b'$. Напомним, что $X$ коммутирует с $\Lambda$. Найдя такую матрицу $X$ для каждой жордановой клетки матрицы $M$, составим из них блочную матрицу $C$, для которой $CM=MC$ и $C\boldsymbol a=\boldsymbol b$. Лемма доказана.

Предложение 1. Все 2-аттракторы, порожденные заданной матрицей $M$, аффинно подобны.

Доказательство. Пусть 2-аттрактор $G$ порожден матрицей $M$ и цифрами $\{\boldsymbol 0, \boldsymbol a\}$, а 2-аттрактор $F$ – той же матрицей и цифрами $\{\boldsymbol 0, \boldsymbol b\}$. По определению аттрактора $\boldsymbol e$ не лежит в собственном подпространстве $M$. Поэтому лемма 1 дает матрицу $C$, для которой $CM=MC$ и $C\boldsymbol a=\boldsymbol b$. Каждая точка $F$ имеет вид
$$ \begin{equation*} \boldsymbol y=\sum_{j}M^{-k_j}\boldsymbol b=\sum_{j}M^{-k_j}C\boldsymbol a= \sum_{j}CM^{-k_j}\boldsymbol a=C\sum_{j}M^{-k_j}\boldsymbol a. \end{equation*} \notag $$
Таким образом, $\boldsymbol y=C\boldsymbol x$, где $\boldsymbol x\in G$. Следовательно, $F=CG$. Предложение доказано.

Замечание 1. Согласно предложению 1, с точностью до аффинного подобия, 2-аттрактор зависит только от растягивающей матрицы $M$ и не зависит от цифр $D$. Одна из двух цифр в $D$, как мы договорились, равна $\boldsymbol 0$, а в качестве второй может выступать любая целая точка, не лежащая в собственном подпространстве $M$. Более того, эта точка может быть не целой (хотя это противоречит определению аттрактора), все равно получившееся множество $G$ будет аффинно подобно 2-аттрактору с целыми цифрами. Чтобы в этом убедиться, достаточно в доказательстве предложения 1 взять произвольную точку $\boldsymbol b \in \mathbb R^d$, ничего не изменится. Поэтому в дальнейшем в доказательствах мы будем позволять цифре $\boldsymbol d_1$ быть нецелой.

По умолчанию будем всегда брать в качестве $\boldsymbol d_1$ первый базисный вектор $\boldsymbol e=\boldsymbol e_1=(1,0, \dots,0)^T \in \mathbb R^d$.

Известно ([35; предложение 2.5]), что целая растягивающая матрица с простым определителем не может иметь кратных собственных значений. Поэтому каждая такая матрица подобна диагональной матрице, а значит, две матрицы с одинаковым спектром подобны. Применив предложение 1, получаем следующую теорему.

Теорема 1. Двухциферный аттрактор однозначно определяется, с точностью до аффинного подобия, спектром матрицы $M$.

Доказательство. Пусть $M=Q^{-1}\Delta Q$, где $\Delta$ – диагональная матрица. Тогда для $\boldsymbol x \in G$ имеем
$$ \begin{equation*} \boldsymbol x=\sum_{k\in \mathbb N}M^{-k}\boldsymbol a_k=\sum_{k\in \mathbb N}Q\Delta^{-k}Q^{-1}\boldsymbol a_k=Q \sum_{k\in \mathbb N}\Delta^{-k} (Q^{-1}\boldsymbol a_k), \end{equation*} \notag $$
где $\boldsymbol a_k \in \{\boldsymbol 0, \boldsymbol e \}$ для каждого $k$. Получается, что аттрактор с матрицей $M$ и цифрами $\{\boldsymbol 0, \boldsymbol e\}$ аффинно подобен аттрактору с матрицей $\Delta$ и цифрами $\{\boldsymbol 0, Q^{-1}\boldsymbol e\}$, а значит, в силу предложения 1 – аттрактору с матрицей $\Delta$ и цифрами $\{\boldsymbol 0, \boldsymbol e\}$. Теорема доказана.

Итак, 2-аттрактор зависит только от характеристического полинома матрицы $M$. Верно и обратное.

Следствие 1. Каждому целому растягивающему полиному со старшим коэффициентом $1$ и свободным коэффициентом $\pm 2$ соответствует единственный с точностью до аффинного подобия 2-аттрактор.

Доказательство. Если $p(z)=z^d+a_{d-1}z^{d-1}+\dots+a_0$, где $a_0=\pm 2$, является целым растягивающим полиномом, то его сопровождающая матрица
$$ \begin{equation} M=\begin{pmatrix} 0 & 0 & \dots & 0 &-a_0 \\ 1 & 0 & \dots & 0 & -a_{1} \\ 0 & 1 & \dots & 0 & -a_{2} \\ \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & \dots & 1 & -a_{d-1} \end{pmatrix} \end{equation} \tag{3} $$
имеет полином $p$ в качестве характеристического. Следовательно, аттрактор, порожденный матрицей $M$ с цифрами $\{\boldsymbol 0, \boldsymbol e\}$, соответствует полиному $p$. Применив теорему 1, получаем единственность. Следствие доказано.

§ 4. Аттракторы, порожденные арифметическими прогрессиями

В какой степени результаты предыдущих параграфов обобщаются на любое число цифр $m$? Если множество цифр $D$ произвольно, то прямых обобщений быть не может уже в $\mathbb R^1$. Например, при $M=3$ (в этом случае $m=3$), аттрактор, заданный цифрами $\{0,1,2\}$ – отрезок, а цифрами $\{0,1,5\}$ – несвязное фрактальное множество [54]. Поэтому аттракторы, определенные одной матрицей, но разными множествами цифр, могут не быть аффинно подобны. Причина в том, что все множества из двух цифр аффинно подобны друг другу, а из трех цифр – нет. Однако для специальных множеств цифр обобщения возможны. Например, если цифры составляют арифметическую прогрессию: $D=\{\boldsymbol d_0, \boldsymbol d_0+\boldsymbol q, \dots, \boldsymbol d_0+(m-1)\boldsymbol q\}$, где $\boldsymbol d_0, \boldsymbol q \in \mathbb R^d, \boldsymbol q \ne \boldsymbol 0$. Поскольку для прогрессии $D=\{\boldsymbol 0, \boldsymbol q, \dots, (m-1)\boldsymbol q\}$ будет тот же аттрактор, сдвинутый на вектор $\sum_{k\in \mathbb N}M^{-k}\boldsymbol d_0$, мы всегда будем считать, что $\boldsymbol d_0=\boldsymbol 0$.

Теорема 2. Все аттракторы, порожденные заданной матрицей $M$, аффинно подобны при условии, что цифры составляют арифметическую прогрессию.

Доказательство. Считаем, что $\boldsymbol d_0=\boldsymbol 0$. Если матрица $C$, коммутирующая с $M$ (лемма 1), переводит вектор $\boldsymbol q_1$ в $\boldsymbol q_2$, то она переводит прогрессию $D_1=\{\boldsymbol 0, \boldsymbol q_1, \dots (m-1)\boldsymbol q_1\}$ в прогрессию $D_2=\{\boldsymbol 0, \boldsymbol q_2, \dots (m-1)\boldsymbol q_2\}$. Далее действуем так же, как при доказательстве предложения 1. Теорема доказана.

Теорема 1 о том, что 2-аттракторы определяются спектром матрицы, не обобщается на произвольное число цифр, даже на прогрессии. Виной тому возможное наличие кратных собственных значений. В этом случае матрица $M$ может иметь нетривиальные жордановы клетки и, соответственно, неоднозначно определяться своим спектром. Утверждать отсутствие кратных корней у целого растягивающего полинома можно лишь в случае, когда его свободный коэффициент – простое число, см. [35]. Поэтому верна следующая ослабленная версия теоремы 1 для произвольного простого числа $m$.

Следствие 2. Если задан целый растягивающий полином $p$ с простым свободным коэффициентом, то все аттракторы, порожденные матрицей с характеристическим полиномом $p$ и цифрами, составляющими арифметическую прогрессию, аффинно подобны.

Доказательство. Так же, как при доказательстве теоремы 1, доказываем аффинное подобие аттракторов, порожденных матрицами $M$ и $\Delta$, при этом пользуемся тем, что оператор $Q^{-1}$ переводит прогрессию в прогрессию. Далее пользуемся теоремой 1. Следствие доказано.

§ 5. Классификация изотропных 2-аттракторов

Мы подошли к одному из главных результатов настоящей работы – полному списку изотропных 2-аттракторов. Список этот окажется на удивление простым. Напомним, что матрица изотропна, если она подобна ортогональной матрице, умноженной на число. Аттрактор, порожденный изотропной матрицей, также называется изотропным.

Изотропные аттракторы и тайлы занимают особое место в теории всплесков и многомерной теории приближений. С одной стороны, для большинства задач изотропное растяжение является наиболее естественным. В этом случае пространство “растягивается одинаково во все стороны”. C другой стороны, изотропные матрицы наиболее просты для анализа. Именно для изотропных всплесков существуют прямые обобщения одномерных конструкций и методов на многомерные. Например, методы вычисления гладкости масштабирующей функции, методы оценивания скорости приближения всплесками и т.д. Поэтому бо́льшая часть литературы по многомерным всплескам и уточняющим алгоритмам имеет дело именно с изотропными матрицами растяжения, см. [60], [16], [39] и подробные обзоры в этих работах.

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

Мы будем называть изотропным полиномом алгебраический полином, все корни которого равны по модулю. У целого полинома со старшим коэффициентом $1$ и простым свободным коэффициентом нет кратных корней [35]. Поэтому растягивающая целая матрица с простым определителем является изотропной тогда и только тогда, когда ее полином изотропный.

Теорема 3. Если $d$ нечетно, то все изотропные 2-аттракторы в $\mathbb R^d$ – параллелепипеды.

Доказательство. Если $d$ нечетно, то матрица $M$ имеет хотя бы одно действительное собственное значение, которое в силу изотропности равно $2^{1/d}$ или $-2^{1/d}$. Подставляя этот корень в характеристический полином $p(z)=z^d+a_{d-1}z^{d-1}+\dots+a_1 z+a_0 $, получаем $- (z^d+a_0)=a_{d-1}z^{d-1}+\dots+a_1 z$. Заметим, что $z^d+a_0$ – целое число, поэтому число $z=\pm 2^{1/d}$ является корнем целого полинома степени $\leqslant d-1$. Последнее возможно, только если этот полином тождественно равен нулю. Следовательно, $p(z)=z^d+a_0$. Рассмотрим случай $a_0=- 2$, случай $a_0=2$ полностью аналогичен. Поскольку характеристический полином обнуляет матрицу $M$, имеем $p(M)=M^d-2I=0$. Если $\{\boldsymbol 0, \boldsymbol e\}$ – цифры, порождающие аттрактор $G$, то $M^d\boldsymbol e=2\boldsymbol e$. Положим $\boldsymbol a_k=M^{k-1}\boldsymbol e$, $k=1, \dots, d$, и назовем $P$ параллелепипед с вершиной $\boldsymbol 0$, натянутый на ребра $\boldsymbol a_1, \dots, \boldsymbol a_d$. Тогда $P=M^{-1}P\sqcup M^{-1}(P+\boldsymbol e)$. Следовательно, характеристическая функция $P$ удовлетворяет тому же масштабирующему уравнению: $\varphi(\boldsymbol x)=\varphi(M\boldsymbol x)+\varphi(M\boldsymbol x-\boldsymbol e)$, что и характеристическая функция $G$. В силу единственности с точностью до умножения на константу решения масштабирующего уравнения получаем $\chi_{P}=\mu \chi_{G}$, где $\mu \in \mathbb R$ – константа. Поскольку обе функции принимают значения $0$ или $1$, получаем $\mu=1$ и $\chi_{P}=\chi_{G}$. Теорема доказана.

Таким образом, в нечетных размерностях не существует изотропных 2-аттракторов, кроме параллелепипедов. В четных ситуация иная: уже в $\mathbb R^2$ появляются два новых аттрактора – дракон и медведь. Оказывается, в любой четной размерности будут только те же три типа.

Теорема 4. Если $d=2k$ – четно, то в $\mathbb R^d$ существуют, с точностью до аффинного подобия, ровно три изотропных 2-аттрактора: параллелепипед, прямое произведение $k$ драконов и прямое произведение $k$ медведей.

Это означает, что в подходящих координатах в $\mathbb R^d$ изотропный 2-аттрактор имеет вид $G=(K, \dots, K)$, где $K$ – либо прямоугольник, либо дракон, либо медведь; при этом $i$-й компонент $K$ занимает координаты $x_{2i}$, $x_{2i+1}$. Ключевую роль в доказательстве играет следующая лемма.

Лемма 2. Каждый целый изотропный полином степени $d=2k$ со старшим коэффициентом $1$ и с простым свободным коэффициентом имеет вид $q(z^k)$, где $q(t)=t^{2}+at+b$ – квадратичный целый изотропный полином.

Доказательство. Пусть полином имеет вид $z^{2k}+a_{2k-1}z^{2k-1}+\dots+a_1z \pm p= 0$, где $p$ – простое число, $a_1, \dots, a_{2k -1} \in \mathbb Z$. Поскольку он изотропный, все его корни равны по модулю $p^{1/d}$. Если у него есть вещественный корень, он равен $\pm p^{1/d}$, и, повторяя доказательство теоремы 3, получаем, что многочлен равен $z^{2k} \pm p$. Cоответствующим квадратичным целым изотропным полиномом будет $q(t)=t^2 \pm p$, т.е. в этом случае теорема доказана. Далее считаем, что все корни не вещественные и разделяются на сопряженные пары $z_1=\overline{z_2}, z_3=\overline{z_4}, \dots, z_{2k-1}=\overline{z_{2k}}$. Произведения корней внутри пар $z_{2m-1}z_{2m}=|z_{2m-1}|^2=p^{1/k}$, $m=1, \dots, k$. Мы докажем, что $a_{2k-m}=a_{m}=0$ при $m=1, \dots,k-1$, отсюда будет следовать, что многочлен имеет вид $z^{2k}+a_k z^{k} \pm p$. После замены переменных $t=z^{k}$ многочлен примет вид $q(t)=t^2+a_k t \pm p$. Он останется изотропным, так как все корни $k$-й степени имеют одинаковый модуль. Таким образом, теорема будет доказана.

Для доказательства равенства $a_{2k-m}=a_{m}=0$ при $m=1, \dots, k-1$ убедимся в том, что $a_{m}=p^{(k-m) / k} a_{2k-m}$ при $m=1, \dots, k-1$. Тогда оба числа $a_{2k-m}$, $a_m$ будут равны нулю, поскольку они целые, а число $p^{(k-m) / k}$ при $m=1, \dots, k-1$ иррационально.

По теореме Виета

$$ \begin{equation} \begin{aligned} \, (-1)^m a_m&=\sum_{i_1 < i_2 < \dots < i_{2k-m}} z_{i_1} \dotsb z_{i_{2k- m}}, \\ (-1)^m a_{2k-m}&=\sum_{j_1 < j_2 < \dots < j_{m}} z_{j_1} \dotsb z_{j_{m}}. \end{aligned} \end{equation} \tag{4} $$
Сопоставим биективно каждому слагаемому $s=z_{j_1} \dotsb z_{j_{m}}$ из второй суммы слагаемое $s_1$ из первой суммы. Вначале возьмем в качестве $s_1$ слагаемое-дополнение, состоящее из тех $z_i$, которых нет в $s$. Потом для тех $z_j$, у которых в $s$ нет их сопряженной пары, заменим в $s_1$ их сопряженные пары обратно на $z_j$. Например, если $k=4, m=3$, слагаемому $z_1z_2z_5$ будет соответствовать $z_3 z_4 z_5 z_7 z_8$. Докажем, что при таком соответствии $s_1=s p^{(k-m) / k}$, тогда в силу формул (4) $a_{m}=p^{(k-m) / k} a_{2k-m}$ и все доказано. Разница слагаемых $s_1$ и $s$ только в тех парах сопряженных корней, которые полностью входят или не входят в $s$ (пусть таких пар будет $a$ и $b$ соответственно). Все произведения сопряженных корней равны $p^{1/k}$, поэтому ${s_1}/{s}=(p^{1/k})^{(b-a)}$. Всего в $s$ входит $m$ множителей, это $2a$ полных пар и $k-a-b$ неполных. Отсюда $m=k+a-b$, $b-a=k-m$ и необходимая формула $s_1=s p^{(k- m) / k}$ доказана. Лемма доказана.

Доказательство теоремы 4. Пусть $p$ – целый изотропный полином степени $d=2k$. По лемме 2 $p(z)=q(z^k)$, где $q(t)=t^{2}+at+b$ – квадратичный целый изотропный полином. Положим
$$ \begin{equation*} A=\begin{pmatrix} 0 & -b \\ 1 & -a \end{pmatrix} \end{equation*} \notag $$
– сопровождающая матрица полинома $q$. Поскольку $|\operatorname{det} A |=|b|=2$ и полином $q$ изотропный, модули его корней равны $\sqrt{2}$, т.е. матрица $A$ растягивающая. Согласно [9] каждый двухциферный аттрактор в $\mathbb R^2$ является либо прямоугольником, либо драконом, либо медведем. Соответственно, матрица $A$ порождает один из этих аттракторов. Рассмотрим следующую матрицу:
$$ \begin{equation} M =\begin{pmatrix} 0 & I & 0 & \dots & 0 \\ 0 & 0 & I & \dots & 0 \\ \vdots & \vdots & \ddots & \ddots& \vdots \\ 0 & 0 & \dots & 0 & I \\ A & 0 & \dots & 0 & 0 \end{pmatrix}, \end{equation} \tag{5} $$
заданную $(2\times 2)$-блоками: каждый нуль обозначает нулевую $(2\times 2)$-матрицу, $I$ – единичная $(2\times 2)$-матрица. Таким образом, $M$ – это $(d\times d)$-матрица, а формула (5) задана $k^2$ блоками размера $2\times 2$. Представим произвольный вектор $\boldsymbol x \in \mathbb R^d$ составленным из $k$ векторов размерности 2, т.е. $\boldsymbol x=(x_1, \dots, x_k)$, $x_i \in \mathbb R^2$. Тогда уравнение на собственный вектор $M\boldsymbol x=\lambda \boldsymbol x$ принимает вид системы: $Ax_1=\lambda x_k$, $x_{i+1}=\lambda x_{i}$, $i=1, \dots, k-1$. Следовательно, $Ax_k=\lambda^kx_k$, откуда $\lambda^k$ – собственное значение $A$. Значит, $q(\lambda^k)=0$, откуда $p(\lambda)=0$. Итак, множество корней полинома $p$ (их ровно $d$ штук и среди них нет кратных!) совпадает с множеством собственных значений матрицы $M$. Следовательно, $M$ имеет характеристический полином $p$. Теперь в силу теоремы 1 достаточно доказать, что аттрактор, порождаемый матрицей $M$, есть произведение $k$ двумерных аттракторов одного типа (прямоугольник, дракон, или медведь). Далее останется сделать замечание, что произведение нескольких прямоугольников – параллелепипед.

Обозначим через $L_i$ двумерное пространство, соответствующее $i$-му блоку матрицы (5), $i=1, \dots, k$. Каждый вектор $\boldsymbol x \in \mathbb R^d$ разлагается в сумму $\boldsymbol x=\sum_{i=1}^k x_i$, $x_i \in L_i$, которую будем обозначать $(x_1, \dots, x_k)$. Через $(X_1, \dots, X_k)=\sum_{i=1}^k X_i$ будем обозначать прямую сумму множеств $X_i \subset L_i$, $i=1, \dots, k$, которая состоит из векторов $(x_1, \dots, x_k)$, $x_i \in X_i$, $i=1, \dots, k$.

Пусть матрица $A$ и цифры $\{0,a\}$ порождают на плоскости аттрактор $K$. Докажем, что матрица $M$ и цифры $\{\boldsymbol 0, \boldsymbol a\}$, где $\boldsymbol a=(0, \dots, 0, a)$ ($k$ двумерных блоков), порождает аттрактор $G=(K, \dots, K)$. Поскольку $K$ – либо прямоугольник, либо дракон, либо медведь, все будет доказано. Имеем:

$$ \begin{equation} M^{-1}= \begin{pmatrix} 0 & 0 & 0 & \dots & A^{-1} \\ I & 0 & 0 & \dots & 0 \\ 0 & I & \ddots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & \dots & I & 0 \end{pmatrix} . \end{equation} \tag{6} $$
Следовательно, $M^{-1}G=(A^{-1}K, K, \dots, K)$ и
$$ \begin{equation*} M^{-1}(G+\boldsymbol a)=M^{-1}G+M^{-1}\boldsymbol a=(A^{-1}(K+a), K, \dots, K). \end{equation*} \notag $$
Так как $ A^{-1}K \sqcup A^{-1}(K+a)=K$, получаем $M^{-1}G \sqcup M^{-1}(G+\boldsymbol a)=G$. Мы приходим к выводу, что $G$ – аттрактор, порожденный матрицей $M$ и цифрами $\{\boldsymbol 0, \boldsymbol a\}$. C любой другой цифрой вместо $\boldsymbol a$ получится аффинно подобный аттрактор, что завершает доказательство теоремы 4.

Замечание 2. Итак, в нечетной размерности есть ровно три типа изотропных 2-аттракторов. Формально мы не доказали то, что эти типы не аффинно подобны. Это будет следовать из результатов § 6, где мы установим, что они не только не подобны, но и не $C^1$-диффеоморфны.

Доказательства теорем 3 и 4 конструктивны: они не только классифицируют все изотропные 2-аттракторы, но и дают метод их построения. Если ввести произвольные базисы в двумерных пространствах $L_1, \dots, L_k$, то получаем множество $(G_1, \dots, G_k)$, где все $G_i$ – произвольные драконы, не зависящие друг от друга. Для любых драконов $G_1, \dots, G_k$ их прямое произведение – $d$-мерный изотропный аттрактор. То же верно для произведения $k$ произвольных медведей. Заметим, что перемножаются либо $k$ драконов, либо $k$ медведей. Никакого смешанного произведения не бывает.

В силу произвольности выбора драконов (или медведей), множество $d$-мерных изотропных 2-аттракторов обладает некоторым разнообразием. Однако оно достигается за счет выбора произвольного базиса. С точностью до аффинного подобия есть всего три изотропных 2-аттрактора в каждой размерности. Это обстоятельство приводит к выводу о необходимости изучения неизотропных аттракторов. До сих пор литература по их приложениям к всплескам и аппроксимационным алгоритмам достаточно скудна (можно упомянуть [13], [15]–[19]).

§ 6. Топология 2-аттракторов

Даже простые топологические свойства самоподобных аттракторов весьма трудны для исследования. Множество работ [35], [37], [2], [9], [32], [34], [23] было посвящено связности аттракторов. Так, в [35], [37], [2] было доказано, что все аттракторы в размерностях $d=2, 3, 4$, у которых цифры составляют арифметическую прогрессию, связны. Границы аттракторов и структура их соседей изучались в [20], [6], [7], [57], [3], [4].

В работе [34] было показано, что плоские 2-аттракторы – медведь и дракон – связны. Более того, как установлено в [12], они оба гомеоморфны кругу. Поскольку для прямоугольника это очевидно, получаем, что каждый плоский 2-аттрактор гомеоморфен кругу. Воспользовавшись нашей классификацией изотропных 2-аттракторов (теоремы 3 и 4) и тем простым фактом, что прямое произведение $k$ компактов, гомеоморфных кругу, гомеоморфно $2k$-мерному шару, получаем

Следствие 3. При любом $d\geqslant 2$ все $d$-мерные изотропные 2-аттракторы гомеоморфны шару.

Из работы [7] следует, что это утверждение может не выполняться для неизотропных 2-аттракторов даже в трехмерном случае. Общий довольно сложный алгоритм проверки гомеоморфности аттракторов шару приведен в статье [20]. Аттракторы с произвольным числом цифр не обязательно гомеоморфны шару – пример в трехмерном случае можно найти там же в [20] (предложение 8.7, также предложение 8.11 – граница является тором). Однако для изотропного случая возникает вопрос о более сильной топологической эквивалентности. В частности, будут ли изотропные 2-аттракторы диффеоморфны или хотя бы метрически эквивалентны, т.е. гомеоморфны путем билипшицевого отображения? В этом параграфе будет получен отрицательный ответ: мы покажем, что все три плоских 2-аттрактора – прямоугольник, дракон и медведь – не являются билишшицево эквивалентными, а следовательно, они и не $C^1$-диффеоморфны. Далее из теоремы 4 будет следовать, что все изотропные 2-аттракторы в $\mathbb R^{2k}$ не билипшицево эквивалентны друг другу (в $\mathbb R^{2k+1}$ есть только параллелепипеды, которые, естественно, все диффеоморфны).

Определение 2. Два компакта $G_1, G_2 \subset \mathbb R^d$ называются метрически эквивалентными, или билипшицево эквивалентными, если они гомеоморфны с помощью билипшицевого отображения $f\colon \mathbb R^d \to \mathbb R^d$. Билипшицевость означает, что существует константа $C > 0$, для которой $C^{-1}|\boldsymbol x_1-\boldsymbol x_2| \leqslant |f(\boldsymbol x_1)-f(\boldsymbol x_2)| \leqslant C |\boldsymbol x_1-\boldsymbol x_2|$ при любых $\boldsymbol x_1, \boldsymbol x_2 \in \mathbb R^d$.

Заметим, что билипшицевость отображения влечет его взаимную однозначность. Если множества $C^1$-диффеоморфны, то они билипшицево эквивалентны, но не наоборот, поскольку билипшицево отображение может быть не дифференцируемым. Хотя согласно теореме Радемахера (см. [55]) оно дифференцируемо почти всюду. Мы установим неэквивалентность аттракторов с помощью характеристики, не меняющейся при билипшицевых отображениях. Таким инвариантом является поверхностная размерность $\sigma(G)$: супремум чисел $r \geqslant 0$, для которых $|G_{\varepsilon}| - |G| \leqslant C_{r} \varepsilon^{ r}$ при всех $\varepsilon > 0$, где $C_{r}$ не зависит от $\varepsilon$. Заметим, что поверхностная размерность не совпадает ни с размерностью хаусдорфа, ни с бокс-размерностью. В самом деле, в отличие от последних, поверхностная размерность различает множества положительной лебеговой меры. В некотором смысле поверхностная размерность характеризует регулярность границы множества. Она, однако, не совпадает также ни с хаусдорфовой размерностью границы, ни с ее бокс-размерностью. См. [54] о свойствах и вычислении поверхностной размерности для аттракторов.

Лемма 3. Показатель $\sigma(G)$ сохраняется при билипшицевых отображениях $\mathbb R^d$.

Доказательство. Ясно, что $|G_{\varepsilon}| - |G|=|G_{\varepsilon}\setminus G|$. Кроме того, $f(G)_{\varepsilon}\setminus f(G) \subset f(G_{C\varepsilon}\setminus G)$. Отображение $f$ увеличивает меру Лебега множества не более, чем в $C^d$ раз. В самом деле, мера Лебега равна мере Хаусдорфа (см. [50]), а для меры Хаусдорфа данное свойство очевидно. Поэтому $|f(G_{C\varepsilon}\setminus G)| \leqslant C^d|G_{C\varepsilon}\setminus G|$. Если $\sigma(G) > r$, то $|G_{C\varepsilon}\setminus G| \geqslant C_r |C\varepsilon|^{r}$. Таким образом, $|f(G)_{\varepsilon}\setminus f(G)|\leqslant C_r |C\varepsilon|^{r} \leqslant C_rC^{r+d} \varepsilon^r$. Так как это верно для всех $\varepsilon\,{>}\,0$, мы получаем $\sigma(f(G))\,{>}\,r$. Итак, неравенство $\sigma(G)\,{>}\,r$ влечет $\sigma(f(G))\,{>}\,r$. Следовательно, $\sigma(f(G))\,{\geqslant}\, \sigma(G)$. Таким образом, билипшицево отображение не уменьшает поверхностной размерности. Применив это утверждение к обратному отображению, получаем, что $\sigma(f(G))=f(G)$. Лемма доказана.

Лемма 3 позволяет доказывать неэквивалентность множеств простым сравнением их поверхностных размерностей. В работе [54] было доказано, что поверхностная размерность изотропных аттракторов равна половине показателя Гёльдера их характеристических функций в пространстве $L_2$:

$$ \begin{equation} \alpha(G)=\alpha(\varphi)=\sup_{\alpha \geqslant 0} \bigl\{ \| \varphi(\boldsymbol x+\boldsymbol h)- \varphi(\boldsymbol x)\|_1 \leqslant C |\boldsymbol h|^{ \alpha}, \boldsymbol h \in \mathbb R^d \bigr\}, \end{equation} \tag{7} $$
где $\varphi=\chi_{G}$. Показатель Гёльдера параллелепипеда, как и любого многогранника, равен $1/2$. Показатели Гёльдера дракона и медведя были вычислены в [61] с помощью [18]. Отсюда мы приходим к следующему результату.

Теорема 5. При четных $d$ все три типа изотропных 2-аттракторов гомеоморфны, но не билипшицево эквивалентны.

Поскольку при нечетных $d$ все изотропные 2-аттракторы являются параллелепипедами, они, естественно, диффеоморфны. Поэтому теорема 5 применяется только для четных размерностей. Для ее доказательства нам понадобится следующее вспомогательное утверждение, установленное в [54]. Для произвольного подпространства $V \subset \mathbb R^d$, назовем $L_2$-показателем Гёльдера функции $\varphi$ вдоль $V$ величину

$$ \begin{equation*} \alpha_{V}(\varphi)=\sup_{\alpha \geqslant 0} \bigl\{\| \varphi(\,\cdot\,+\boldsymbol h)- \varphi(\,\cdot\,)\|_1 \leqslant C |\boldsymbol h|^{ \alpha},\, \boldsymbol h \in V \bigr\} \end{equation*} \notag $$
(сдвиги осуществляются только вдоль подпространства $V$).

Лемма A (см. [18]). Если $\varphi \in L_2(\mathbb R^d)$ – произвольная функция, а пространство $\mathbb R^d$ представлено в виде прямой суммы подпространств $V_1, \dots, V_k$, то $\alpha(\varphi)=\min_{j=1, \dots, k}\alpha_{V_j}(\varphi)$.

Доказательство теоремы 5. При $d=2$ показатели Гёльдера двумерных 2-аттракторов вычислены в [61]. Для дракона этот показатель равен $0.2382\dots$, для медведя равен $0.3446\dots$ (для квадрата, естественно, $0.5$). Поскольку эти показатели равны поверхностным размерностям, лемма 3 означает, что эти множества не билипшицево эквивалентны. При $d=2k$ каждый 2-аттрактор аффинно подобен либо прямому произведению $k$ драконов, либо $k$ медведей, либо является параллелепипедом. В последнем случае $\alpha(G)=0.5$. В случае драконов обозначим через $V_1, \dots, V_k$ двумерные плоскости, содержащие данных драконов. Тогда $\alpha_{V_j}(G)$ равно гладкости дракона для любого $j$. В силу леммы A $\alpha_{ V_j}(G)$ равно гладкости дракона $0.2382\dots$ . Аналогично, гладкость прямого произведения $k$ медведей равна гладкости одного медведя, т.е. $0.3446\dots$ . Теперь вновь ссылаемся на лемму 3 и заключаем неэквивалентность данных множеств. Теорема доказана.

Что касается неизотропных 2-аттракторов, то мы лишь можем сформулировать следующее предположение.

Гипотеза 1. Если 2-аттракторы не аффинно подобны, они не билипшицево эквивалентны.

§ 7. Выпуклые оболочки 2-аттракторов

Аттракторы-многогранники изучались в литературе [31], [20], [62]. Кроме теоретического интереса, они привлекательны для приложений, поскольку порождают всплески и уточняющие алгоритмы с простой структурой. В [62] было показано, что каждый аттрактор-многоугольник в $\mathbb R^2$ (не обязательно выпуклый) является параллелограммом, и была выдвинута гипотеза о том, что этот факт верен в любой размерности: все аттракторы-многогранники являются параллелепипедами. Сейчас мы покажем, что по крайней мере для $2$-аттракторов эта гипотеза верна. Фактически, мы установим более сильный факт и найдем все $2$-аттракторы, выпуклая оболочка которых является многогранником. Мы докажем, что выпуклая оболочка любого $2$-аттрактора является бесконечным зонотопом, который, в свою очередь, является многогранником только в двух случаях: для параллелепипеда и для произведения драконов.

Напомним, что зонотопом в $\mathbb R^d$ называется сумма по Минковскому конечного числа отрезков. Каждый зонотоп выпуклый и является проекцией $N$-мерного куба на пространство $\mathbb R^d$, где $N$ – число отрезков. В частности, зонотоп имеет центр симметрии. Зоноид – предел последовательности зонотопов в метрике Хаусдорфа. Нам понадобится обобщение понятия зонотопа на бесконечное множество отрезков.

Определение 3. Бесконечным зонотопом в $\mathbb R^d$ называется сумма по Минковскому счетной последовательности отрезков с конечной суммой длин. Бесконечный зонотоп невырожден, если он не лежит в подпространстве меньшей размерности.

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

Предложение 2. Выпуклая оболочка $2$-аттрактора, порожденного матрицей $M$ и цифрами $\{\boldsymbol 0, \boldsymbol a\}$ является невырожденным бесконечным зонотопом $\overline G=\sum_{k=1}^{\infty} M^{-k}\overline{\boldsymbol a}$, где $\overline{\boldsymbol a}$ – отрезок $[\boldsymbol 0, \boldsymbol a]$.

Доказательство. Поскольку $\rho(M^{-1})< 1$, сумма длин отрезков $M^{-k}\overline{\boldsymbol a}$ конечна, следовательно, $\overline G$ – невырожденный бесконечный зонотоп. Ясно, что $G \subset \overline G$, так как $\{\boldsymbol 0, \boldsymbol a\} \subset \overline{\boldsymbol a}$. Установим обратное включение. Каждая точка $\boldsymbol x \in \overline G$ разлагается в сумму $\sum_{k=1}^{\infty} M^{-k} \boldsymbol x_k$, где каждая точка $\boldsymbol x_k$ принадлежит отрезку $M^{-k} \overline{\boldsymbol a}$. Если хотя бы для одного $ j$ точка $\boldsymbol x_j$ не совпадает с концом отрезка $M^{-j} \overline{\boldsymbol a}$, то она является полусуммой некоторых точек $\boldsymbol x_j', \boldsymbol x_j'' \in M^{-j} \overline{\boldsymbol a} $. Следовательно, $\boldsymbol x$ является полусуммой точек $\boldsymbol x_j'+\sum_{k\ne j}^{\infty} M^{-k} \boldsymbol x_k$ и $\boldsymbol x_j''+\sum_{k\ne j}^{\infty} M^{-k} \boldsymbol x_k$. Поэтому все крайние точки множества $\overline G$ находятся среди точек суммы $\sum_{k=1}^{\infty} M^{-k} \{\boldsymbol 0, \boldsymbol a\}$, т.е. среди точек множества $G$. По теореме Крейна–Мильмана каждое выпуклое компактное множество есть замыкание выпуклой оболочки своих крайних точек. Тогда $\overline G$, как замыкание выпуклой оболочки крайних точек компакта $G$, лежит в $G$. Предложение доказано.

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

Предложение 3. Выпуклая оболочка дракона является восьмиугольником.

Доказательство. Матрица дракона $M$ является поворотом на $\pi/4$ с умножением на $\sqrt{2}$, поэтому все отрезки $M^{-k}\overline{\boldsymbol e}$ расположены на четырех прямых – координатных осях и биссектрисах координатных углов. Все отрезки на одной прямой складываются в один отрезок. Отсюда следует, что сумма $\sum_{k=1}^{\infty}M^{-k}\overline{\boldsymbol e}$ есть сумма четырех отрезков, т.е. восьмиугольник. Предложение доказано.

Оказывается, что среди всех 2-аттракторов, не обязательно изотропных, только параллелепипед и дракон либо прямые произведения драконов имеют простые выпуклые оболочки. Прямое произведение $k$ драконов (один из трех возможных изотропных 2-аттракторов в $\mathbb R^{2k}$ – теорема 4) является многогранником с $8^k$ вершинами. Все остальные 2-аттракторы имеют выпуклые оболочки, не являющиеся многогранниками.

Теорема 6. Среди всех 2-аттракторов в $\mathbb R^d$ есть только два типа с выпуклой оболочкой, являющейся многогранником. Это параллелепипед ($2^d$ вершин) и прямое произведение $d/2$ драконов ($2^{3d/2}$ вершин).

У любого 2-аттрактора, не являющегося параллелепипедом или произведением драконов, выпуклая оболочка является бесконечным зонотопом и имеет бесконечно много крайних точек.

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

Лемма 4. Если среди отрезков, порождающих бесконечный зонотоп в $\mathbb R^d$, есть бесконечно много непараллельных, то зонотоп не является многогранником.

Доказательство. Докажем сначала утверждение в $\mathbb R^2$. Сложив заранее все параллельные отрезки, будем предполагать, что все отрезки в последовательности $\{\overline{\boldsymbol a}_k\}_{k=1}^{\infty}$ имеют разные направления. Фиксируем произвольный индекс $j$ и рассмотрим последовательность зонотопов $\overline G_s=\sum_{k=1}^{s} \overline{\boldsymbol a}_k$ при $s=j, j+1, \dots $ . Каждый из них является $2s$-угольником, у которого одна из сторон параллельна и равна отрезку $\overline{\boldsymbol a}_j$. Поскольку $\overline G_s$ сходится в метрике Хаусдорфа к бесконечному зонотопу $\overline G$, предельный зонотоп имеет на границе отрезок, параллельный отрезку $\overline{\boldsymbol a}_j$ и не меньший $|\overline{\boldsymbol a}_j|$ по длине. Следовательно, $\overline G$ имеет на границе отрезки, параллельные всем отрезкам $\overline{\boldsymbol a}_j$, $j\in \mathbb N$. Значит, $\overline G$ не является многоугольником, что завершает доказательство в $\mathbb R^2$. Для доказательства в $\mathbb R^d$ достаточно спроецировать все векторы на подходящую двумерную плоскость так, чтобы в проекции было по-прежнему бесконечно много непараллельных векторов. По доказанному выше проекция бесконечного зонотопа $\overline G$ на эту плоскость не будет многоугольником, поэтому $\overline G$ не будет многогранником. Лемма доказана.
Доказательство теоремы 6. Сначала покажем, что выпуклая оболочка медведя – не многоугольник. В самом деле, матрица медведя в подходящих координатах определяет поворот на угол $\operatorname{arctg} (\sqrt{7})$ с растяжением в $\sqrt{2}$ раз. Поскольку угол поворота иррациональный, среди отрезков $M^{-k}\overline{\boldsymbol e}$, $k \in \mathbb N$, нет параллельных. Остается сослаться на лемму 4. Таким образом, в $\mathbb R^2$ теорема доказана. Рассмотрим произвольное $\mathbb R^d$, $d\geqslant 3$. Если аттрактор $G$ изотропный, то это либо параллелепипед, либо произведение драконов, либо произведение медведей. Первые два случая оговорены в условии теоремы, в последнем случае аттрактор не является многогранником, поскольку выпуклая оболочка медведя не многоугольник. Остается рассмотреть случай, когда аттрактор $G$ неизотропный. Обозначим через $V$ линейное подпространство в $\mathbb R^d$, содержащее собственные векторы всех наибольших по модулю собственных значений матрицы $M^{-1}$ (напомним, что среди собственных значений нет кратных). Если какое-то собственное значение не является действительным, берем действительную и мнимую части соответствующего собственного вектора. Вектор $\boldsymbol e$ не принадлежит $V$, поскольку он не принадлежит никакому инвариантному подпространству матрицы $M$. Поэтому последовательность $\{M^{-k}\boldsymbol e\}_{k=1}^{\infty}$ приближается к подпространству $V$ при $k \to \infty$, не достигая его, поскольку $M^{-1}$ невырождена. Поэтому, последовательность отрезков $\{M^{-k}\overline{\boldsymbol e}\}_{k=1}^{\infty}$ содержит бесконечно много непараллельных. Применив лемму 4, завершаем доказательство. Теорема доказана.

Итак, согласно теореме 6 только параллелепипеды и произведения драконов имеют простую выпуклую оболочку.

Замечание 3. Интересно, что медведь является более регулярным аттрактором, чем дракон: гладкость в $L_2$ медведя равна $0.3446\dots$ против $0.2382\dots$ у дракона. Тем не менее выпуклая оболочка медведя – бесконечный зонотоп, в то время как у дракона – восьмиугольник.

Теперь мы в состоянии классифицировать простые 2-аттракторы и подтвердить гипотезу из [62] для 2-аттракторов.

Многогранным множеством называется объединение конечного числа многогранников.

Следствие 4. Если 2-аттрактор является многогранным множеством, то это параллелепипед.

Доказательство. Согласно теореме 6 многогранным множеством среди 2-аттракторов может быть либо параллелепипед, либо произведение драконов. Дракон, однако, не является многогранным множеством, поскольку его показатель Гёльдера в $L_2$ меньше $0.5$.

При доказательстве теоремы 6 мы установили, что выпуклая оболочка неизотропного 2-аттрактора не может быть многогранником. Отсюда сразу же получаем

Следствие 5. Если 2-аттрактор является параллелепипедом, то он изотропный.

§ 8. Тайлы, базисы Хаара и КМА

Мера Лебега самоподобного аттрактора всегда является натуральным числом. Если она равна 1, то аттрактор называется тайлом. Целые сдвиги тайла покрывают $\mathbb R^d$ в один слой с пересечениями нулевой меры, а его характеристическая функция $\varphi$ имеет ортонормированные целые сдвиги. Именно тайлы наиболее важны в приложениях. В этом случае функция $\varphi$ порождает КМА и систему всплесков. Для 2-аттрактора (в данном случае – 2-тайла) $G(M, D)$, где $D=\{\boldsymbol 0, \boldsymbol a\}$, базис Хаара порождается $M$-сжатиями и целыми сдвигами одной функции $\psi(\boldsymbol x)=\varphi(M\boldsymbol x) - \varphi(M\boldsymbol x-\boldsymbol a)$. Системы всплесков также могут порождаться тайлами в частотной области [24], [10], [11], [49], [48]. В теории приближений случай тайлов также имеет особую важность, поскольку именно в этом случае уточняющая схема (subdivision scheme) сходится в $L_p$. Если аттрактор не является тайлом, то целые сдвиги функции $\varphi$ линейно зависимы, поэтому функция $\varphi$ не образует КМА, а соответствующая уточняющая схема может расходиться [14], [39]. Существуют различные условия для алгоритмической проверки, является ли аттрактор, порожденный матрицей $M$ и цифрами $D$, тайлом [44], [32]. При этом все зависит не только от матрицы, но и от цифр. Например, если матрица $M$ и множество цифр $D=\{\boldsymbol 0, \boldsymbol a\}$ порождает 2-тайл $G(M,D)$, то для множества цифр $D'=\{0, 3\boldsymbol a\}$ 2-аттрактор $G(M, D')$ уже не является тайлом, поскольку его мера Лебега равна $3^d|G(M,D)| \geqslant 3^d$. В размерностях $d=2, 3$ для каждой растягивающей матрицы $M$ существует множество цифр $D$, для которого $G(M, D)$ – тайл. Но уже в $\mathbb R^4$ А. Потиопа в 1997 г. построил пример матрицы $M$, для которой такого множества цифр не существует, т.е. эта матрица не порождает тайла [43], [45].

В случае двух цифр тип 2-аттрактора не зависит ни от цифр, ни от матрицы $M$, а зависит только от характеристического полинома $M$. Поэтому, естественно сформулировать проблему по-другому.

Проблема 1. Всегда ли существует тайл, аффинно подобный данному 2-аттрактору?

Поскольку 2-аттрактор с точностью до аффинного подобия определяется растягивающим полиномом, проблема может быть сформулирована так: каждый ли растягивающий целый полином, у которого $a_d=1$, $|a_0|=2$ порождает тайл?

Мы предполагаем, что ответ утвердительный и, более того, достигается для сопровождающей матрицы (3) данного полинома и цифр $D=\{\boldsymbol 0, \boldsymbol e\}$, где $\boldsymbol e=\boldsymbol e_1$ – первый базисный вектор.

Гипотеза 2. Для произвольного растягивающего целого полинома со старшим коэффициентом $1$ и свободным коэффициентом $\pm 2$ его сопровождающая матрица $M$ и цифры $D=\{\boldsymbol 0, \boldsymbol e\}$ порождают тайл.

Отметим сразу два случая, в которых эта гипотеза верна. Первый – случай малых размерностей.

Предложение 4. Гипотеза 2 верна в размерностях $d=2,3$.

Доказательство. В размерности $d=2$ существуют, с точностью до эквивалентности, три полинома, порождающие 2-аттрактор (§ 2), в размерности $d=3$ таких полиномов семь (§ 11). Применив к каждому программу checktile (см. [46]), реализующую критерий из [32], завершаем доказательство.

Второй случай более важен. Гипотеза 2 верна для изотропных 2-аттракторов в любой размерности.

Теорема 7. Гипотеза 2 верна для изотропных полиномов.

Доказательство. В нечетной размерности каждый 2-аттрактор является параллелепипедом, соответствующим полиному $p(z)=z^d \pm 2$ (теорема 3). Тогда непосредственно проверяется, что характеристическая функция куба $[0,1]^d$ удовлетворяет масштабирующему уравнению $\varphi(\boldsymbol x)=\varphi(M\boldsymbol x)+\varphi(M\boldsymbol x-\boldsymbol e)$, где $M$ – сопровождающая матрица полинома $z^d -2$. Следовательно, для данного полинома 2-аттрактор является тайлом $[0,1]^d$. Для полинома $z^d -2$ то же масштабирующее уравнение имеет решение – характеристическую функцию куба $[-1/3, 2/3] \times [0, 1]^{d-1}$. Данный куб, естественно, также является тайлом.

В четной размерности $d=2k$ согласно лемме 2 имеем $p(z)=q(z^k)$, где $q(t)=t^{2}+at \pm 2$ – квадратичный изотропный полином. После перестановки координат $x_i \to x_{\sigma(i)}$ по формуле $ \sigma(i)=2(k-i+1)$; $\sigma(i+k)=2(k-i)+1$, $i=1, \dots, k$, сопровождающая матрица полинома $p$ переходит в матрицу $M$, определенную формулой (5). Поэтому если $M$ порождает тайл, то и сопровождающая матрица также порождает тайл. Согласно теореме 4 матрица $M$ порождает 2-аттрактор, являющийся прямым произведением равных двумерных 2-аттракторов – драконов, медведей и прямоугольников. Так как каждый из этих двумерных аттракторов является тайлом, прямое произведение также является тайлом. Теорема доказана.

Замечание 4. Теорема 7 гарантирует существование 2-тайла, аффинно подобного произвольному изотропному 2-аттрактору. В примере Потиопа (см. [45]) матрица $M$ также изотропная, и она не порождает тайла, т.е. для нее не существует цифр $D$ таких, что $G(M,D)$ – тайл. Однако согласно теореме 7 для сопровождающей матрицы того же самого характеристического полиномома $p(z)=z^4+z^2+2$ такое множество цифр существует – это $D=\{\boldsymbol 0, \boldsymbol e \}$. Мы получим 2-тайл $G(M,D)$. Согласно теореме 4 этот тайл – произведение двух драконов. Таким образом, в примере Потиопа достаточно просто перейти к другому целочисленному базису в $\mathbb R^d$, чтобы получить 2-тайл.

Замечание 5. Несмотря на то что изотропный 2-тайл является прямым произведением одинаковых двумерных тайлов, порожденная им система Хаара не является прямым произведением двумерных функций Хаара. Так, если $\varphi$ – прямое произведение, скажем, $k$ драконов: $\varphi=\varphi_1 \otimes \dots \otimes \varphi_k$, где каждая функция $\varphi_i$ – характеристическая функция дракона в $\mathbb R^2$, то функция Хаара в $\mathbb R^d$ – это $\varphi(M\boldsymbol x)-\varphi(M\boldsymbol x- \boldsymbol e)$, она не совпадает с прямым произведением $k$ двумерных функций Хаара.

Заметим также, что классификация изотропных 2-аттракторов, полученная в § 5, позволяет находить гладкость порожденных ими функций Хаара. При нечетных $d$ есть только параллелепипеды, их показатель Гёльдера в $L_2(\mathbb R^d)$ равен $0.5$. При четных $d$ добавляются произведения драконов и произведения медведей. Их гладкость равна показателям Гёльдера драконов и медведей в $L_2(\mathbb R^2)$ – соответственно $0.2382\dots$ и $0.3446\dots$ [61].

§ 9. Может ли один аттрактор соответствовать разным матрицам?

Сколько существует различных, с точностью до аффинного подобия, 2-аттракторов в $\mathbb R^d$? В изотропном случае существует либо один, либо три типа, в зависимости от четности $d$. Для неизотропных таких типов гораздо больше, и их число растет с ростом размерности. В следующем параграфе мы получим оценки на это число. Для этого, однако, необходимо ответить на один важный вопрос: находятся ли типы 2-аттракторов во взаимно однозначном соответствии со спектрами растягивающих матриц с определителем $\pm 2$? В § 3 мы установили это соответствие в одну сторону: в силу теоремы 1 каждый аттрактор однозначно определяется спектром своей матрицы $M$, т.е. целым растягивающим полиномом со старшим коэффициентом $1$ и свободным коэффициентом $\pm 2$. Значит, мы можем оценить число таких полиномов степени $d$. Каждый такой полином порождает единственный, с точностью до аффинного подобия, аттрактор. Но верно ли обратное, что каждому аттрактору соответствует только один полином, т.е. только одна (с точностью до аффинного подобия) матрица $M$? Не получится ли так, что мы найдем много подходящих полиномов, но они все будут определять один и тот же тип аттрактора, скажем, параллелепипед? Решение этого вопроса оказывается нетривиальным. Мы покажем (это легко), что матрицы $M$ и $-M$ порождают один и тот же 2-аттрактор. И что (это сложнее) разные и не противоположные друг другу матрицы порождают разные (т.е. не аффинно подобные) аттракторы.

Нам понадобится следующий известный (см. [35; предложение 2.2]) факт.

Предложение 5. Каждый 2-аттрактор центрально-симметричен.

Доказательство. Пусть $D=\{\boldsymbol 0, \boldsymbol e\}$. Обозначим $\boldsymbol c=\frac12 \sum_{j=1}^{\infty} M^{-j} \boldsymbol e$. Тогда $G=\boldsymbol c+\sum_{j=1}^{\infty} \pm \frac12 M^{-j} \boldsymbol e$. Множество $\sum_{j=1}^{\infty} \pm \frac12 M^{-j} \boldsymbol e$ симметрично относительно нуля, поэтому $G$ симметрично относительно точки $\boldsymbol c$. Предложение доказано.

Определение 4. Алгебраические полиномы $p=\sum_{k=0}^{d} p_k t^k$ и $q=\sum_{k=0}^{d} q_k t^k$ называются противоположными, если $q_k=(-1)^{d-k}p_k$, $k=0, \dots, d$.

Старшие коэффициенты противоположных полиномов равны. Из теоремы Виета следует, что корни полинома $q$ – это корни полинома $p$, взятые с обратным знаком. Таким образом, корни $p$ и $q$ противоположны, что оправдывает терминологию. Матрицы $M$ и $-M$ имеют противоположные характеристические полиномы.

Предложение 6. Противоположные полиномы порождают один и тот же 2-аттрактор.

Доказательство. Характеристическая функция $\varphi$ аттрактора $G$ удовлетворяет масштабирующему уравнению $\varphi(\boldsymbol x)=\varphi(M\boldsymbol x)+\varphi(M\boldsymbol x-\boldsymbol e)$. Так как $G=2\boldsymbol c-G$, то $\varphi (2\boldsymbol c-\boldsymbol x)=\varphi(\boldsymbol x)$. Тогда $\varphi(\boldsymbol x)=\varphi(2M\boldsymbol c-M\boldsymbol x)+\varphi(2M\boldsymbol c- \boldsymbol e-M\boldsymbol x)$. Следовательно, множество $G$ является также аттрактором с матрицей $-M$ и цифрами $-2M\boldsymbol c$, $\boldsymbol e- 2M\boldsymbol c$. Предложение доказано.

Оказывается, что верно и обратное: если полиномы порождают один и тот же 2-аттрактор, то они либо равны, либо противоположны. Таким образом, 2-аттрактор определяет матрицу $M$ с точностью до знака и до подобия.

Теорема 8. Если матрицы $M_1$ и $M_2$ (с некоторыми множествами цифр $D_1$, $D_2$) порождают один и тот же, с точностью до аффинного подобия, 2-аттрактор, то либо $M_1=M_2$, либо $M_1=- M_2$.

Доказательство основано на следующей лемме. Для данной матрицы $M$ и заданного отрезка $\overline{\boldsymbol a}=[- \boldsymbol a, \boldsymbol a ]\subset \mathbb R^d$, $\boldsymbol a \ne 0$, рассмотрим следующее множество отрезков $\mathcal T(M, \overline{\boldsymbol a})=\{ M^{-k}\overline{\boldsymbol a},\,k \in \mathbb N\}$, где совпадающие отрезки считаются с кратностью.

Лемма 5 (о восстановлении линейной системы). Даны растягивающие $(d\times d)$-матрицы $M_1$, $M_2$, у которых нет кратных собственных значений. Тогда если для некоторых отрезков $\overline{\boldsymbol a}_1$ и $\overline{\boldsymbol a}_2$ ($\overline{\boldsymbol a}_i$ не лежит в собственном подпространстве $M_i$, $i=1,2$) выполнено $\mathcal T(M_1, \overline{\boldsymbol a}_1)=\mathcal T(M_2, \overline{\boldsymbol a}_2)$, то либо $M_1=M_2$, либо $M_1=-M_2$.

Доказательство см. в § 13. Лемма 5 фактически устанавливает возможность идентификации линейной динамической системы по ее траектории, даже если история неизвестна, т.е. не известны номера точек. Если номера известны, то матрица однозначно определяется любыми $d+1$ идущими подряд точками траектории. Задача идентификации с неизвестной историей значительно более сложная.

Теперь мы можем доказать теорему 8. Для этого мы воспользуемся известным результатом теории масштабирующих функций и представим преобразование Фурье $\widehat \varphi$ характеристической функции аттрактора $G$ в виде бесконечного произведения тригонометрических полиномов. C помощью этого представления мы найдем множество нулей функции $\widehat \varphi$. Оно является объединением счетного числа гиперплоскостей в $\mathbb R^d$. Чтобы не иметь дело с гиперплоскостями, перейдем к их полярам. Поляра берется относительно единичной евклидовой сферы с центром в $0$, поляра гиперплоскости – одна точка. Со ссылкой на лемму 5 мы покажем, что получившееся множество точек однозначно определяет матрицу $M$. Из этого следует, что аттрактор $G$ однозначно (с точностью до $\pm$) определяет $M$.

Доказательство теоремы 8. Пусть 2-аттрактор $G$ порождается матрицей $M$ и цифрами $\{\boldsymbol 0, \boldsymbol e\}$. Тогда его характеристическая функция удовлетворяет масштабирующему уравнению $\varphi( \boldsymbol x)=\varphi(M\boldsymbol x)+\varphi(M\boldsymbol x -\boldsymbol e)$ (см. § 1, уравнение 2). Решение масштабирующего уравнения выражается формулой
$$ \begin{equation} \widehat \varphi (\xi)= \widehat \varphi (0)\prod_{k=1}^{\infty} \boldsymbol m \bigl( [M^{*}]^{-k}\boldsymbol \xi\bigr), \end{equation} \tag{8} $$
где тригонометрический полином $\boldsymbol m(\boldsymbol \xi)=(1+e^{-2\pi i (\boldsymbol e, \boldsymbol \xi) })/2$ называется маской уравнения (см., например, [51]). Если мы покажем, что множество нулей функции $\widehat \varphi (\boldsymbol \xi)$ однозначно, с точностью до знака, определяет матрицу $M$, все будет доказано. В самом деле, функция $\widehat \varphi $ однозначно определяется множеством $G$, следовательно, и множество нулей этой функции также определяется множеством $G$. Значит, и матрица $M$, с точностью до знака, будет определяться множеством $G$. Так как $(\boldsymbol e, \boldsymbol \xi)=\xi_1$ (первая компонента вектора $\boldsymbol \xi$), множество решений уравнения $\boldsymbol m(\boldsymbol \xi)=0$ – это объединение счетного числа параллельных гиперплоскостей $\xi_1=1/2+n$, $n \in \mathbb Z$. Поляры этих гиперплоскостей – счетное множество точек $\mathcal R=\{2/(1+2n)\boldsymbol e_1\}_{n \in \mathbb Z}$, где $\boldsymbol e_1=(1,0, \dots, 0)^T$ – первый базисный вектор. Множество нулей функции $\boldsymbol m ([M^{*}]^{-k}\boldsymbol \xi)$ – это образ множества нулей функции $\boldsymbol m (\boldsymbol \xi)$ под действием оператора $[M^*]^k$. Значит, поляра множества нулей функции $\boldsymbol m([M^{*}]^{-k}\boldsymbol \xi)$ – это $M^{-k}\mathcal R$. Множество нулей произведения (8) является объединением множеств нулей функций $\boldsymbol m ([M^{*}]^{-k}\boldsymbol \xi)$ по всем $k \in \mathbb N$ (все нули считаются с кратностями). Следовательно, множество нулей функции $\widehat \varphi (\boldsymbol \xi)$ однозначно определяется множеством $\bigcup_{k \in \mathbb N} M^{-k}\mathcal R$ (все точки считаются с учетом кратностей). Каждое множество $M^{-k}\mathcal R$ лежит на отрезке $[-M^{-k}\boldsymbol a, M^{-k}\boldsymbol a]$, где $\boldsymbol a=2\boldsymbol e_1$ – точка множества $\mathcal R$, наиболее отстоящая от нуля, а значит, $M^{-k}\boldsymbol a$ – точка множества $M^{-k}\mathcal R$, наиболее отстоящая от нуля. Положим $\overline{\boldsymbol a}=[-\boldsymbol a, \boldsymbol a]$. Мы видим, что каждое множество $\bigcup_{k \in \mathbb N} M^{-k}\mathcal R$ однозначно определяется множеством отрезков $\bigcup_{k \in \mathbb N} M^{-k}\overline{\boldsymbol a}=\mathcal T(M, \overline{\boldsymbol a})$. Итак, множество нулей функции $\widehat \varphi $ однозначно определяет множество отрезков $\mathcal T( M,\overline{\boldsymbol a})$. Если мы установим, что это множество отрезков однозначно, с точностью до знака, определяет матрицу $M$, все будет доказано. Если предположить обратное, что существуют целые матрицы $M_1$, $M_2$ с определителем $\pm 2$ и отрезки $\overline{\boldsymbol a}_1$ и $\overline{\boldsymbol a}_2$, для которых $\mathcal T(M_1, \overline{\boldsymbol a}_1)=\mathcal T(M_2, \overline{\boldsymbol a}_2)$, то согласно лемме 5 либо $M_1=\pm M_2$, что и требовалось, либо одна из матриц имеет кратное собственное значение. Последнее невозможно в силу [35; предложение 2.5]. Теорема доказана.

Следствие 6. Два полинома порождают аффинно подобные 2-аттракторы тогда и только тогда, когда они либо равны, либо противоположны.

В нечетных размерностях полином не может быть противоположен себе, а каждый полином со свободным коэффициентом $2$ противоположен ровно одному полиному со свободным коэффициентом $-2$ и наоборот. Таким образом, в нечетных размерностях количество различных (не аффинно подобных) 2-аттракторов равно количеству растягивающих полиномов со старшим коэффициентом $1$ и свободным коэффициентом $2$.

В четных размерностях противоположные полиномы имеют одинаковый свободный коэффициент. Противоположны себе будут в точности те полиномы, у которых нулевые коэффициенты перед нечетными степенями. Они зависят от $x^2$ и при замене $x_1=x^2$ свойство растягиваемости не поменяется. Поэтому полиномов, противоположных себе, столько же, сколько растягивающих полиномов вдвое меньшей степени со старшим коэффициентом $1$ и свободным коэффициентом $\pm 2$. Итак, количество различных (не аффинно подобных) 2-аттракторов в $\mathbb R^{2d}$ равно полусумме количества растягивающих полиномов степени $2d$ со старшим коэффициентом $1$ и свободным коэффициентом $\pm 2$ и такого же количества для степени $d$.

§ 10. Количество 2-аттракторов в $\mathbb R^d$

В каждой размерности $d$ существует конечное число различных (не аффинно подобных) 2-аттракторов [29]. В $\mathbb R^2$ есть ровно три 2-аттрактора (все – изотропные), в $\mathbb R^3$ их ровно семь (изотропный только один – параллелепипед), см. также § 11 про трехмерный случай. Численные результаты, представленные в табл. 1, дают нам оценку снизу на число аттракторов в размерностях $d \leqslant 8$ (по-видимому, эти оценки точны, хотя мы не можем этого доказать). На рис. 3 – график двоичного логарифма этой оценки на число аттракторов размерности $d$, видно, что он близок к линейному. Следовательно, нижняя оценка при этих $d$ близка к $2^d$. Для бо́льших размерностей $d$ мы знаем ответ лишь приблизительно, получив достаточно далекие друг от друга оценки сверху и снизу.

Таблица 1.Оценка снизу на число 2-аттракторов

d Число полиномов Число 2-аттракторов
263
3147
43621
55829
612871
719095
8362199

В силу следствия 69) вопрос о числе 2-аттракторов сводится к следующей задаче о целых полиномах.

Проблема 2. Сколько существует растягивающих целых полиномов степени $d$ со старшим коэффициентом $1$ и свободным коэффициентом $ \pm 2$ ?

В [34] было показано, что число таких полиномов растет по крайней мере линейно по $d$. С другой стороны, для каждого $d$ это число конечно. Мы получим нижнюю оценку $d^2/16+O(d)$, и верхнюю $ 2^{ d+\varepsilon}$. Перед доказательством отметим, что в литературе изучалось асимптотическое распределение количества целых растягивающих многочленов (при большом свободном коэффициенте) [1], [5], [41]. Многочлены с похожими условиями возникали также в работе [28]. В [58] получено упрощение критерия “растягиваемости” Шура–Кона для целочисленных многочленов.

Мы начнем с доказательства нижней оценки $d^2/16+O(d)$. Назовем плохим вектор $(n_1, n_2, n_3)$ из натуральных чисел, если он пропорционален вектору $(3x+s, 3y+s, 3z+s)$, где $s \in \{1, 2\}$, и $ x, y, z \in \mathbb Z$. Соответствующее разбиение числа $d=n_1+n_2+n_3$ на сумму натуральных слагаемых будем также называть плохим, а все другие разбиения называем хорошими. Мы отождествляем разбиения, отличающиеся только порядком слагаемых. Через $b_{+}(d)$ обозначим количество хороших разбиений числа $d$.

Теорема 9. Любой многочлен вида $P(z)=(1+z^m)(1+z^q)(1+z^k)+1$ является растягивающим целым полиномом со старшим коэффициентом $1$ и свободным коэффициентом $2$, если $(m, q, k)$ является хорошим разбиением $d=m+q+k$. Если $d$ не делится на $3$, то их количество $b_{+}(d)$ равно $d(d-1)/12+\omega_d$, где $\omega_d \in[-2/3,1/2]$. Если $d$ делится на 3, то оно удовлетворяет неравенству

$$ \begin{equation*} \frac{d^2}{16} - \frac{43d}{36}-\frac56 \leqslant b_{+}(d)\leqslant \frac{7d^2}{108}+\frac{5d}{12}+\frac23. \end{equation*} \notag $$

Заметим, что главные члены верхней и нижней оценок на $b_{+}(d)$ близки: $1/16=0.0625, 7/108 \approx 0.0648$ . Доказательство теоремы 9 отложим до § 12.

Для вывода оценки сверху $2^{ d+\varepsilon}$ мы воспользуемся результатом А. Дубицкаса и С. Конягина о числе полиномов, мера Малера которых не превосходит числа $T$.

Мерой Малера алгебраического полинома $p(t)=a_dt^d+\dots+a_1t+a_0$ называется число $\mu(p)=|a_d| \prod_{i=1}^d \max \{1, |\lambda_i|\}$, где $\lambda_1, \dots, \lambda_d$ – корни полинома $p$ с учетом кратности. Следующую теорему из [22] мы приводим в несколько упрощенной формулировке. Обозначим $\theta=1.32471\dots$ – корень полинома $x^3-x-1$.

Теорема B (см. [22]). Если $T \geqslant \theta$, то количество целых полиномов со старшим коэффициентом $1$, мера Малера которых не больше $T$, не превосходит $T^{d (1+16 \ln \ln d/\ln d)}$.

Теперь мы готовы сформулировать главную теорему этого параграфа.

Теорема 10. Количество $N(d)$ не аффинно подобных 2-аттракторов размерности $d$ удовлетворяет неравенствам ${d^2}/{16} - {43d}/{36}-5/6\leqslant N(d)\leqslant2^{d(1+{16 \ln \ln d}/{\ln d})}$.

Доказательство. Оценка снизу следует из теоремы 9, где оценивается количество не противоположных друг другу полиномов серии $P(z)=(1+z^m)(1+z^q)(1+z^k)+1$. Согласно теореме 8 все они дают не аффинно подобные 2-аттракторы.

Для оценки сверху заметим, что у растягивающего полинома с коэффициентами $a_d=1$, $a_0=\pm 2$ мера Малера равна $\prod_{i=1}^d |\lambda_i|=|a_0|=2$. Поэтому $N(d)$ не превосходит числа целых полиномов, у которых $\mu(p) \leqslant 2$. Применяя теорему B для $T=2$, завершаем доказательство.

Из-за большой разницы между верхней и нижней оценками в теореме 10 встает вопрос об асимптотическом поведении величины $N(d)$ при $d\to \infty$. На первый взгляд, $N(d)$ должно быть значительно меньше количества полиномов с мерой Малера $\mu(p) \leqslant 2$. Во-первых, потому что для $N(d)$ учитываются только полиномы со старшим коэффициентом $1$, во-вторых, потому что запрещены корни меньше $1$. Однако численные результаты, приведенные в табл. 1, говорят скорее об обратном: для $d\leqslant 8$ отношение $N(d)/2^d$ приближается к $1$ с ростом $d$. Отметим также, что нижние оценки на количество полиномов с заданной мерой Малера часто получаются сильно меньше верхних, поскольку примеры подобных полиномов “плохо размножаются”, см. [25].

§ 11. 2-аттракторы в $\mathbb R^3$

В трехмерном пространстве существует семь типов аффинно-неизоморфных 2-аттракторов. Они были впервые построены в работе [9]. У этих 2-аттракторов характеристические многочлены различны и не противоположны друг другу, поэтому, по следствию 6, они не аффинно подобны. В [7] изучались их топологические свойства – гомеоморфность шару, структура соседей и так далее. В частности, была установлена комбинаторная структура покрытий пространства $\mathbb R^3$ целочисленными сдвигами данных аттракторов. В этом параграфе мы вычислим показатели гладкости по Гёльдеру трехмерных 2-аттракторов и увидим, что они различны. Это объясняет не только их аффинную неэквивалентность, но и различные аппроксимационные свойства соответствующих систем всплесков Хаара. Как мы увидим, даже построение картинок существенно зависит от гладкости аттракторов.

Напомним, что по полиному $p(z)=z^3+a_{2}z^2+a_1z+a_0$ можно построить сопровождающую матрицу

$$ \begin{equation*} M=\begin{pmatrix} 0 & 0 & -a_0 \\ 1 & 0 & -a_{1} \\ 0 & 1 & -a_{2} \end{pmatrix} \end{equation*} \notag $$
с характеристическим полиномом $p$.

Таблица 2.Гладкость трехмерных 2-аттракторов

Многочлен$L_2$ -cпектральный радиус Показатель Гёльдера в $L_2$
$z^3+2z^2+2z+2$0.970820.06822
$z^3+z^2+z+2$0.932380.23148
$z^3+2$0.89090.5
$z^3-z^2-z+2$0.942780.23282
$z^3 -z+2$0.951970.1173
$z^3-2z+2$0.985480.02563
$z^3+z^2+2$0.975420.04713

Для каждого из возможных семи многочленов, указанных в табл. 2, мы строим аттрактор по сопровождающей матрице и цифрам $(0, 0, 0)^T$ и $(1, 0, 0)^T$. Показателем гладкости по Гёльдеру $\alpha (G)$ множества $G$ называется показатель гладкости по Гёльдеру в $L_2$ его характеристической функции $\chi_G$ (см. определение (7)).

Показатель Гёльдера можно найти, используя метод из [18]. Сначала мы строим вспомогательные матрицы $T_0$, $T_1$, их размерности зависят от аттрактора (от $4$ до $23$ в наших семи случаях). Далее мы вычисляем $L_2$-спектральный радиус [53] этих матриц на специальном подпространстве и по нему находим показатель гладкости по Гёльдеру.

Двумерные иллюстрации с 2-аттракторами (с драконом, прямоугольником и медведем) получены с помощью программы [38]. Для построения трехмерных картинок мы использовали две программы, Chaoscope [21] и IFStile [47]. Алгоритмы построения у них различны. Chaoscope использует вероятностный подход, и время работы мало зависит от типа аттрактора. Другая программа, IFStile, в которой получаются более детальные рисунки, по-видимому использует итерационный алгоритм, скорость сходимости которого существенно зависит как раз от значений гладкости по Гёльдеру (замечание 6 ниже). Так, построение типа 3 (параллелепипеда) с максимальной гладкостью $\alpha=0.5$ занимает меньше минуты, типы 2 ($\alpha \approx 0.2315$) и 4 ($\alpha\approx0.2328$) при тех же параметрах строятся несколько часов, а типу 5 ($\alpha \approx 0.1173$) требуется уже несколько дней даже для худшего качества изображения. На этих рисунках также показано разбиение аттрактора на две аффинно подобные ему части (более темную и более светлую). Получившиеся изображения – на рис. 4 некоторые типы показаны в нескольких ракурсах.

Замечание 6. Качество рис. 4 находится в прямой зависимости от гладкости соответствующих аттракторов. Попробуем объяснить этот феномен на примере итерационного алгоритма, который, видимо, в той или иной форме, лежит в основе большинства программ построения аттракторов. Для линейного оператора $T$, действующего в $L_2(\mathbb R^d)$ по формуле

$$ \begin{equation*} [Tf](\boldsymbol x)=\sum_{\boldsymbol k \in D} f(M\boldsymbol x-\boldsymbol k), \end{equation*} \notag $$
характеристическая функция $\varphi=\chi_{ G}$ является неподвижной точкой. Если аттрактор $G$ является тайлом, то для начальной функции $f_0=\chi_{[0,1]^d}$ (характеристической функции единичного куба), итерационный алгоритм $f_{k+1}=Tf_{k}$, $k \geqslant 0$, сходится к $\varphi$ в $L_2$. При этом $\|f_k-\varphi\|_{L_2}=O(2^{- k \alpha})$, где $\alpha$ – показатель Гёльдера $\varphi$ (этот факт известен для любой масштабирующей функции [14], [16], [39]). Следовательно $k\approx \log_2(1/\varepsilon)/\alpha$. Скажем, для приближения $\varphi$ с точностью $0.03$ нужно порядка $k={5}/{\alpha}$ итераций. Для аттрактора типа 3 нужно 10 итераций (меньше минуты компьютерного времени). Для типов 2 и 4 нужно уже 22 итерации, что требует уже несколько часов, поскольку сложность каждой итерации увеличивается. На тип 5 нужно уже $45$ итераций, что исключает возможность его построения за разумное время без существенной потери качества. На типы 6 и 7 нужно 195 (!) и 106 итераций соответственно.

§ 12. Серии целых растягивающих многочленов и 2-аттракторов

Как мы знаем (следствие 6), 2-аттрактор полностью определяется соответствующим целым растягивающим полиномом $p(z)$ со старшим коэффициентом $1$ и свободным коэффициентом $\pm 2$. Для построения аттрактора нужно взять целую матрицу $M$ с характеристическим полиномом $p$ (например, его сопровождающую матрицу (3) или любую другую) и произвольную допустимую пару цифр $D$. Полученный 2-аттрактор будет, с точностью до аффинного подобия, однозначно определен, независимо от $M$ и $D$. Поэтому задача построения 2-аттракторов равносильна задаче нахождения растягивающих полиномов. В этом параграфе мы построим несколько серий таких полиномов. Количество полиномов степени $d$ в каждой серии растет линейно по $d$, и только серия 4 содержит квадратическое по $d$ число полиномов (именно она обеспечивает оценку снизу на число 2-аттракторов в теореме 10. Сначала мы выпишем все серии, а затем приведем соответствующие доказательства. Серии 1 и 2 встречались в литературе, серии 37, насколько нам известно, новые.

Серии целых растягивающих многочленов со старшим коэффициентом $1$ и свободным коэффициентом $\pm 2$

Серия 1. a) Многочлены вида $(z^m+z^q-2)/(z^{(m, q)}-1)$ при условии $m > q \geqslant 1$, где $(m, q)$ обозначает наибольший общий делитель чисел $m$ и $q$.

b) Многочлены вида $(z^m+z^q+2)/(z^{(m, q)}+1)$ при условиях $m_1=m/(m, q)$, $m_2=q/(m, q)$ нечетны, $m > q\geqslant 1$.

Серия 2. В этих сериях всего три слагаемых.

a) Многочлены вида$z^m-z^q+2$ при $m > q \geqslant 1$ и нечетном $q_1=q/(m, q)$.

b) Противоположная ей серия $z^q-z^m-2$ при $q > m \geqslant 1$ и нечетном $q_1=q/(m, q)$.

c) Многочлены вида $z^m+z^q+2$ при $m > q \geqslant 1$, при условии, что числа $m_1=m/(m, q)$, $q_1=q/(m, q)$ разной четности.

Серия 3. a) Многочлены вида $(1+z^m)(1+z^q)+1$ при любых натуральных $m$, $q$.

b) Многочлены вида $(z^m-1)(z^q-1)+1$ при любых натуральных $m$, $q$.

Напомним, что вектор из натуральных чисел $(n_1, n_2, n_3)$ называется плохим, если он пропорционален некоторому вектору $(3x+s, 3y+s, 3z+s)$, где $s \in \{1, 2\}$, и $ x, y, z \in \mathbb Z$. Остальные векторы называются хорошими.

Серия 4. a) Многочлены вида $(1+z^m)(1+z^q)(1+z^k)+1$ при любом хорошем векторе $(m, q, k)$.

b) Многочлены вида $(1-z^m)(1-z^q)(1+z^k)+1$, если неверно, что остатки при делении на $3$ у чисел $m$ и $q$ равны, а $k \equiv -m \pmod{3}$.

Серия 5. Многочлены вида $(1+z^m+z^{2m})(1+z^q+z^{2q})+1$, если $m \not \equiv q \pmod{4}$.

Серия 6. Многочлены вида $(1+z^m)(1 \pm z^r+z^{2r})+1$, где $m$, $r$ – произвольные натуральные числа.

Серия 7. Многочлены вида $(1+z^a)(1+z^b)(1+z^{(a+b)}) (1+z^{2(a+b)}) (1+ z^{4(a+b)}) (1+z^{8 (a+b))}) \dotsb (1+z^{2^k (a+b)})+1$, где $a$, $b$, $k$ – натуральные.

Замечание 7. Несложно убедиться в том, что все многочлены серий 17 различны (кроме случая $k=q$ в 4, b), который сводится к 3, b) и отдельных частных случаев некоторых серий, которые также содержатся в серии 1). У всех многочленов серий 2, a), b), c), 3, a), b), 4, a), 5, 6, 7 разные значения в точке $z=1$: $2$, $-2$, $4$, $5$, $1$, $9$, $10$, $3$ или $7$, $2^{k+3}+1$ (где $k \leqslant 1$) соответственно.

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

Доказательство для серии 1. a) Пусть $m=(m, q)m_1$, $q=(m, q)q_1$. Многочлен можно переписать в виде суммы двух прогрессий
$$ \begin{equation*} \begin{aligned} \, \frac{z^m-1}{z^{(m, q)}-1}+\frac{z^q-1}{z^{(m, q)}-1} &=1+{z^{(m, q)}}+{(z^{(m,q)})}^2+\dots+{(z^{(m,q)})}^{m_1-1} \\ &\qquad+1+{z^{(m, q)}}+\dots+{(z^{(m,q)})}^{q_1-1}. \end{aligned} \end{equation*} \notag $$
Отсюда следует, что у этого многочлена свободный член $2$, а старший коэффициент $1$. Если знаменатель $z^{(m, q)}-1=0$, то значение многочлена равно $m_1+q_1$, и такие $z$ не являются корнями многочлена. Далее считаем, что $z^{(m, q)} \ne 1$. Тогда корни многочлена удовлетворяют условию $z^m+z^q-2=0$, поэтому они не могут быть по модулю меньше $1$. Если корень равен по модулю $1$, то по неравенству треугольника $z^m=z^q=1$. Обозначим через $\gamma$ аргумент $z$, выбранный в диапазоне $[0, 2\pi)$. Поскольку $z^m=1$, то $\gamma={2\pi m_2}/{m}$, $m_2=0, \dots, m-1$. Кроме того, $\gamma={2\pi q_2}/{q}$, $q_2=0, \dots, q-1$. Значит, ${2\pi m_2}/{m}={2\pi q_2}/{q}$, откуда $m_2 q=q_2 m$, тогда $m_2 q_1=q_2 m_1$. Так как $(m_1, q_1)=1$, то $m_2$ делится на $m_1$. Но тогда у $z^{(m, q)}$ полярный угол будет ${2\pi m_2 (m, q)}/{m_1 (m, q)}$ и это число кратно $2\pi$, значит, знаменатель $z^{(m, q)}-1$ равен нулю, что противоречит предположению. Таким образом, этот многочлен не может иметь корней $|z| \leqslant 1$.

b) Аналогичная серия может быть получена изменением знаков. В этом случае многочлен имеет вид

$$ \begin{equation*} \begin{aligned} \, \frac{z^m+1}{z^{(m, q)}+1}+\frac{z^q+1}{z^{(m, q)}+1} &=1-{z^{(m, q)}}+{(z^{(m,q)})}^2+\dots+{(z^{(m,q)})}^{m_1-1} \\ &\qquad+1-{z^{(m, q)}}+\dots+{(z^{(m,q)})}^{q_1-1}. \end{aligned} \end{equation*} \notag $$
Опять можно считать $z^{(m, q)}+1 \ne 0$, иначе $z$ не будет являться корнем многочлена. Точки внутри единичного круга снова не подходят, а на границе должны выполняться условия $z^m=-1$, $z^q=-1$. Тогда аргумент числа $z$, равный $\gamma \in [0, 2\pi)$, удовлетворяет равенствам $\gamma={\pi}/{m}+{2\pi m_2}/{m}={\pi}/{q}+{2\pi q_2}/{q}$. После домножения на ${mq}/{\pi (m, q)}$ получаем $q_1+2m_2q_1=m_1+2q_2m_1$. Поскольку $(q_1, m_1)=1$, $(1+2m_2)$ делится на $m_1$. Найдем полярный угол у $z^{(m, q)}$. Это ${\pi(m, q)}/{m}+{2\pi m_2(m, q)}/{m}=\pi ({1+2m_2})/{m_1}$. Эта точка соответствует числу $-1$, поскольку $(1+2m_2)/m_1$ – нечетное целое число. Снова получаем, что знаменатель занулился, что противоречит предположению. Доказательство для серии 1 завершено.

Доказательство для серии 2. Во всех трех случаях корни не могут лежать внутри единичного круга, поскольку тогда $|z^m \pm z^q| < 2$.

Если $|z|=1$, то в случаях a) и b) должно выполняться $z^m=-1$, $z^q=1$, в случае c) выполняется $z^m=-1$, $z^q=-1$.

В случаях a) и b) получаем ${\pi}/{m}+{2\pi m_2}/{m}={2\pi q_2}/{q}$, где $m_2=0, \dots, m-1$, $q_2=0, \dots, q-1$. После домножения на ${mq}/{\pi (m, q)}$ будет $q_1 (1+2m_2)=2q_2 m_1$. Поскольку и $q_1$, и $1+2m_2$ нечетны, это невозможно.

В случае c) ${\pi}/{m}+{2\pi m_2}/{m}={\pi}/{q}+{2\pi q_2}/{q}$, тогда $q_1+2m_2 q_1=m_1+2m_1q_2$. Значит, $q_1-m_1=2 (m_1q_2-m_2q_1)$, что невозможно, если $q_1$, $m_1$ разной четности.

Доказательство для серии 3. a) Докажем от противного. Предположим, что у нашего многочлена $P(z)$ есть корень $|z| \leqslant 1$.

Пусть $\overline{B}(1, 1)$ – замкнутый круг на комплексной плоскости с центром $1$ и радиусом $1$. Ясно, что $|z^m| \leqslant 1$ и $|z^q| \leqslant 1$, поэтому обе точки $z^m+1$ и $z^q+1$ лежат в круге $\overline{B}(1, 1)$. Заметим, что $z^m+1 \ne 0$, $z^q+1 \ne 0$, иначе $P(z)=1 \ne 0$. У каждого ненулевого комплексного числа, лежащего в круге $\overline{B}(1, 1)$, аргумент по модулю строго меньше ${\pi}/{2}$. Поэтому у произведения двух любых ненулевых чисел из этого круга аргумент меньше по модулю $\pi$. Значит, произведение чисел $z^m+1$ и $z^q+1$ не может иметь аргумент $\pi$ и быть равным $-1$, противоречие.

Доказательство п. b) аналогично.

Доказательство для серии 4. а) Предположим, что у нашего многочлена $P(z)$ есть корень $|z| \leqslant 1$. Обозначим точки $z_1=z^m+1$, $z_2=z^q+1$, $z_3=z^k+1$, они лежат в круге $\overline{B}(1, 1)$. Пусть их аргументы $\alpha_1$, $\alpha_2$, $\alpha_3$ соответственно. Заметим, что $z_i \ne 0$, $i=1, 2, 3$, иначе $P(z)=1 \ne 0$. У каждого ненулевого комплексного числа, лежащего в круге $\overline{B}(1, 1)$, аргумент по модулю строго меньше ${\pi}/{2}$. Поэтому $|\alpha_i| < {\pi}/{2}$, $i=1, 2, 3$. Поскольку $z_1z_2z_3=-1$, $\alpha_1+\alpha_2+\alpha_3=\pm \pi$. Из этих двух условий следует, что числа $\alpha_i$ одного знака. Можно считать, что они положительны (иначе заменим $z$ на сопряженный корень). Таким образом, числа $\alpha_i$ являются углами остроугольного треугольника. Известно, что для остроугольного треугольника выполнено неравенство $\cos(\alpha_1)\cos(\alpha_2)\cos(\alpha_3) \leqslant {1}/{8}$, а равенство достигается только на равностороннем треугольнике. Для удобства читателей приведем соответствующее рассуждение. Функция $f(x)=-\ln(\cos(x))$ при $x \in (0, {\pi}/{2})$ является строго выпуклой, поскольку $f''(x)= {1}/{\cos^2(x)} > 0$. Нам нужно максимизировать функцию $\cos(\alpha_1)\cos(\alpha_2)\cos(\alpha_3)$, т.е. минимизировать функцию $f(\alpha_1, \alpha_2, \alpha_3)=-\ln(\cos(\alpha_1))-\ln( \cos(\alpha_2))-\ln(\cos(\alpha_3))$, которая будет являться коэрцитивной на компакте $[0,{\pi}/{2}]^3$ (выпуклой с возможными значениями $+\infty$). У такой функции не более одного минимума, который на пересечении с гиперплоскостью $\alpha_1+\alpha_2+\alpha_3=\pi$ будет достигаться при равенстве аргументов.

Таким образом, $|\cos(\alpha_1)\cos(\alpha_2)\cos(\alpha_3)| \leqslant {1}/{8}$. Так как $z_i \in \overline{B}(1, 1)$, $|z_i| \leqslant 2 \cos(\alpha_i)$. Поскольку $|z_1 z_2 z_3|=1$, отсюда следует, что $|\cos(\alpha_1)\cos(\alpha_2)\cos(\alpha_3)| \geqslant {1}/{8}$. Получаем единственный возможный случай, когда треугольник равносторонний и $|z_1|=|z_2|=|z_3|=1$. Тогда $z^m+1$, $z^q+1$, $z^k+1$ имеют одинаковые аргументы ${\pi}/{3}$, значит, $z^m$, $z^q$, $z^k$ имеют одинаковые аргументы ${2\pi}/{3}$. Обозначим аргумент числа $z$ через $\gamma \in [0, 2\pi)$, тогда $\gamma={2\pi}/({3m})+{2\pi m_2}/{m}=2\pi/(3q)+2\pi q_2/{q}$, $m_2=1, \dots, m- 1$, $q_2=1, \dots, q-1$. Домножим на ${3mq}/(2\pi)$, тогда $q+3m_2q=m+3q_2m$. Значит, у $q$ и $m$ должны быть одинаковые остатки при делении на $3$. Такой же остаток должен быть у $k$. Если эти остатки не равны $0$, то мы уже получили плохой вектор $(q, m, k)$. Если все числа $(q, m, k)$ делятся на $3$, поделим их на максимальную общую степень $3$. У получившихся чисел также должен быть одинаковый ненулевой остаток при делении на $3$, т.е. и в этом случае $(q, m, k)$ образуют плохой вектор. Значит, для хороших векторов многочлен является растягивающим.

b) Доказательство сохраняется с точностью до замены определений на $z_1=1-z^m$, $z_2=1-z^q$ до момента, когда мы получаем, что $|z_1|=|z_2|=|z_3|=1$ и $\alpha_1=\alpha_2=\alpha_3={\pi}/{3}$ (снова, не теряя общности, считаем углы положительными). Но теперь аргументы $z^m$, $z^q$ получаются ${4\pi}/{3}$, у $z^k$ он снова ${2\pi}/{3}$. Обозначим аргумент числа $z$ через $\gamma \in [0, 2\pi)$, тогда $\gamma={4\pi}/(3m)+{2\pi m_2}/{m}={2\pi}/(3k)+{2\pi k_2}/{k}$, $m_2=1, \dots, m-1$, $k_2=1, \dots, k-1$. Домножим на ${3mk}/(2\pi)$, тогда $2k+3m_2k=m+3q_2m$. Значит, $m \equiv -k \pmod{3}$. Аналогично $q \equiv -k \pmod{3}$. Если эти условия не выполняются, мы можем быть уверены, что многочлен растягивающий.

Доказательство для серии 5. Обозначим наш многочлен $P(z)=(1+z^m+z^{2m})(1+z^q+z^{2q})+1$. Докажем, что если $(1+z^m+z^{2m})(1+z^q+z^{2q})=- c$, где $c$ – вещественное положительное число и $|z| \leqslant 1$, то $c < 1$. Этого достаточно, так как тогда при $|z| \leqslant 1$ у многочлена $P(z)$ не будет корней. Мы применим к $P(z)$ принцип открытости: аналитическая функция, отличная от константы, переводит открытое множество комплексной плоскости в открытое множество. Поэтому, максимум действительной части функции $P(z)$ на единичном круге достигается на его границе. Следовательно, нам достаточно доказать утверждение для случая $|z|=1$, т.е. $z=e^{i \alpha}$.

Исследуем свойства многочлена $p(z)=1+z+z^2$ для $|z|=1$. Выделим на комплексной плоскости “белую зону” – точки единичной окружности с углами из $[-{2\pi}/{3},{2\pi}/{3}]$, ее дополнение назовем “серой зоной” (рис. 5). Заметим, что при сложении векторов $z^2$ и $1$ получается ромб с диагональю, параллельной $z$. При этом если точка $z$ в белой зоне, то $p(z)=\lambda z$ для $\lambda \geqslant 0$, если $z$ в серой, то $p(z)=\lambda z$ для $\lambda < 0$. В обоих случаях получаем, что $p(z)$ будет лежать в белой зоне. Кроме того, справедливо равенство $|p(z)|=|1+z+z^2|=|1+2\cos \alpha|$.

Мы рассматриваем вопрос, при каких положительных вещественных $c$ возможно $p(u)p(w)=-c$, где $u=z^m$, $w=z^q$, $|u|=|w|=|z|=1$. Если $u$ лежит в серой зоне, то аргумент $p(u)$ лежит в $(-{\pi}/{3}, {\pi}/{3})$. Аргумент $p(w)$ лежит в $[-{2\pi}/{3}, {2\pi}/{3}]$, так как $p(w)$ в белой зоне. При таких условиях сумма аргументов $p(u)$ и $p(w)$ не может быть равна $\pi$ ($-\pi$), а значит, равенство $p(u)p(w)=-c$ невозможно. Тогда и $u$, и $w$ должны лежать в белой зоне. Пусть у $u$ аргумент $\beta$. Значит,

$$ \begin{equation*} |p(u)p(w)|=(1+2\cos(\beta))(1+2\cos(\pi- \beta))=1-4 \cos^2 \beta. \end{equation*} \notag $$

При $\beta$ с $\cos \beta \ne 0$ эта величина строго меньше $1$ и все доказано. Это может нарушаться только при $u=\pm i$ или $w=\pm i$. Пусть $u=i$. Тогда $p(u)=1+i-1= i$, и чтобы $p(u)$, $p(w)$ в произведении давали число с аргументом $\pi$, $p(w)=i$. Тогда $w=i$, т.е. выполняется $z^m=i$, $z^q=i$.

Докажем, что если $m \not \equiv q \pmod{4}$, то такое невозможно. Обозначим через $\gamma$ аргумент $z$, выбранный в диапазоне $[0, 2\pi)$. Поскольку $z^m=i$, $\gamma={\pi}/({2m})+{2 \pi m_1}/{m}$, где $m_1=0, \dots, m-1$. Поскольку $z^q=i$, верна и другая формула $\gamma= {\pi}/({2q})+{2 \pi q_1}/{q}$, где $q_1=0, \dots, q-1$. Значит, ${1}/({2m})+{2 m_1}/{m}={1}/({2q})+{2 q_1}/{q}$, откуда после домножения на $2mq$ получаем $q-m=4 (q_1m- m_1q)$, что невозможно при нашем условии.

Аналогично разбирается случай, когда $u=-i$, тогда верно $w=-i$, и $q-m$ должно снова делиться на $4$.

Доказательство для серии 6. Докажем такое утверждение.

Полином $P(z)=(1+z^m)q(z^r)+1$, где $q(z)=z^n+a_{n-1}z^{n-1}+\dots+a_1z+1$ – целый полином, является растягивающим, если

$$ \begin{equation*} \min_{t \in \mathbb R} (\cos nt+a_{n-1} \cos (n-1)t+\dots+a_1 \cos t+1) >-\frac{1}{2}. \end{equation*} \notag $$

По принципу открытости аналитического отображения, аналогично предыдущей серии, будем доказывать, что если $z=e^{i\alpha}$, $(1+z^m)q(z)=- c$, где $c$ – вещественное положительное число, то $c < 1$. Заметим, что $1+z^m$ лежит в правой полуплоскости (если $1+z^m=0$, то $c=0$ неположительно). Так как произведение $1+z^m$ и $q(z^r)$ имеет аргумент $\pi$, то $q(z^r)$ имеет отрицательную вещественную часть. Пусть $q(z^r)$ имеет аргумент $\gamma$. Тогда $(1+z^m)$ имеет аргумент $\pi- \gamma$, и $|1+z^m|=|2\cos (\pi-\gamma)|$. Тогда

$$ \begin{equation*} \begin{aligned} \, &|(1+z^m)q(z^r)| =2|\cos (\pi-\alpha) q(z^r)|=2|\cos (\alpha) q(z^r)| =2 |\operatorname{Re}(q(z^r))| \\ &\qquad=-2 \operatorname{Re}(q(z^r))=2 (\cos nrs+a_{n-1} \cos (n-1)rs+\dots+a_1 \cos rs+1) \\ &\qquad< 2\cdot \frac{1}{2}=1. \end{aligned} \end{equation*} \notag $$
Значит, $c< 1$, что завершает доказательство утверждения.

В нашем случае

$$ \begin{equation*} q(z)=z^2 \pm z+1, \qquad \min_{t \in \mathbb R}(\cos 2t \pm \cos t+1)=\min_{x\in [-1, 1]} 2x^2 \pm x=- \frac{1}{8}. \end{equation*} \notag $$

Доказательство для серии 7. Применяем принцип открытости аналитического отображения, как в предыдущих двух сериях. Будет достаточно доказать, что если при $|z|=1$ верно $P(z)-1=-c$, где $c$ – вещественное положительное число, то $c < 1$. Мы докажем, что равенство $P(z)-1=-c$ не выполняется ни для какого вещественного $c > 0$. Предположим противное. Пусть $s$ – аргумент числа $z$, тогда аргументы $1+z^a$, $1+z^b$, $1+z^{(a+b)}$, $1+z^{2 (a+b)}$, $\dots$, $1+z^{2^k (a+b)}$ с точностью до прибавления $\pi$, будут $as/{2}$, ${bs}/{2}$, $(a+b)s/{2}$, $(a+b)s$, $\dots$, $2^{k-1} (a+b)s$ (рис. 6).

Их сумма c точностью до прибавления $2\pi$ равна $\pi$, поэтому для некоторого $t \in \mathbb Z$

$$ \begin{equation*} \frac{as}{2}+\frac{bs}{2}+\frac{(a+b)s}{2}+(a+b)s+\dots+2^{k-1}(a+b)s=\pi t. \end{equation*} \notag $$

Значит, $\pi t=(a+b)s (1+1+2+4+\dots+2^{k-1})=(a+b)s 2^k$. Тогда в последней скобке аргумент числа $z^{2^k (a+b)}$ будет с точностью до $2\pi$ равен $\pi t$. То есть либо $1+z^{2^k (a+b)}=0$ (и тогда $P(z)-1=0$, $c=0$, противоречие), либо $1+z^{2^k (a+b)}=2$. Значит, теперь мы можем рассматривать равенство с меньшим числом скобок:

$$ \begin{equation*} \begin{aligned} \, &(1+z^a)(1+z^b)(1+z^{(a+b)}) (1+z^{2(a+b)}) (1+z^{4(a+b)}) \\ &\qquad\times (1+z^{8 (a+b)}) \dotsb (1+z^{2^{k-1} (a+b)})=-\frac{c}{2}. \end{aligned} \end{equation*} \notag $$
Повторяем рассуждение, постепенно уменьшая число скобок. Так дойдем до многочлена $(1+z^a)(1+z^b)$, любое значение которого, как показано в доказательстве серии 3, всегда лежит в правой полуплоскости и не может быть отрицательным действительным числом.

Теперь мы можем дать обещанное доказательство теоремы 910). Через $b_{+}(d)$ обозначим количество хороших разбиений числа $d$, через $b_{-}(d)$ – количество плохих разбиений (определения см. § 10), а через $b(d)$ – количество всех разбиений числа $d$ в сумму натуральных слагаемых. Таким образом, $b(d)=b_{-}(d)+b_{+}(d)$. Мы используем следующую известную оценку.

Лемма 6. Для любого $d \in \mathbb N$ имеем

$$ \begin{equation*} \frac{d(d-1)-r(r-1)}{12}-\frac{1}{2}\leqslant b(d) \leqslant \frac{d(d-1)-r(r-1)}{12}+\frac{1}{2}, \end{equation*} \notag $$
где $r$ – остаток от деления $d$ на $3$.

Поскольку слагаемое $r(r-1)$ на множестве остатков от деления на $3$ принимает только значения $0$ и $2$, получаем

Следствие 7. Для любого $d \in \mathbb N$ имеем: $b(d)={d(d-1)}/{12}+\omega_d,$ где $\omega_d \in[-2/3,1/2].$

Доказательство теоремы 9. Сумма координат плохого вектора делится на $3$, поэтому при $d \not \equiv 0 \pmod 3$ плохих разбиений нет, значит, $b_+(d)=b(d)$, и для этой величины мы применяем следствие 7. Если же $d \equiv 0 \pmod 3$, то $ d=3^{\ell} d'$, $d' \not \equiv 0 \pmod 3$. Если $d=n_1+n_2+n_3$ – плохое разбиение, то существует $j\leqslant \ell-1$, при котором $(n_1, n_2, n_3)=3^{j}(3x+s, 3y+s, 3z+s)$, где $s\in \{1,2\}$ и $x,y,z \in \mathbb Z$. Следовательно, $x+y+z=3^{-j-1}d- s$. Итак, каждое плохое разбиение числа $d$ имеет вид $d=3^{j}(3x+s)+3^{j}(3y+s)+3^{j}(3z+s)$, где $j=0, \dots, \ell-1$, $s \in \{1, 2\}$ и $x+y+z$ – произвольное разбиение числа $3^{-j-1}d- s$. Следовательно, если $b\equiv 0\pmod 3$, то
$$ \begin{equation} b_{+}(d)=b(d)-\sum_{j=0}^{\ell-1}\bigl(b(3^{-j-1}d- 1)+b(3^{-j-1}d-2)\bigr). \end{equation} \tag{9} $$
Обозначим $a_j=3^{-j-1}d$. Все числа $a_j$, кроме последнего $a_{\ell-1}$, делятся на $3$. Поэтому $j$-е слагаемое в сумме (9) при $j=0, \dots, \ell-1$ равно по лемме 6
$$ \begin{equation*} \frac{(a_j-1)(a_j-2)-2\cdot 1}{12}+\frac{(a_j-2)(a_j-3)}{12}+v_j = \frac{(a_j- 1)(a_j-3)}{6}+v_j, \end{equation*} \notag $$
где $v_j \in [-1,1]$. В последнем слагаемом $a_{\ell -1}$ не делится на 3, поэтому числитель в первой дроби может увеличиться на $2$. Таким образом,
$$ \begin{equation*} b_+(d)=\frac{d(d-1)}{12}-v -\sum_{j=0}^{\ell-1}\biggl(\frac{(a_j-1)(a_j-3)}{6}+v_j\biggr), \end{equation*} \notag $$
где $v \in[-1/3,5/6], $ и $v_j \in [-1, 1]$. Для оценки полученного выражения снизу мы заменим сумму слагаемых ${a_j^2}/{6}$ на бесконечную, а сумму ${2a_j}/{3}$ на первое слагаемое. Сложив полученную геометрическую прогрессию и оценив $\sum_{j=0}^{l-1} (0.5+v_j) \leqslant 1.5 l \leqslant 1.5 d$, получим требуемую оценку снизу. Для оценки сверху мы наоборот заменяем сумму ${a_j^2}/{6}$ на первое слагаемое, а сумму ${2a_j}/{3}$ на бесконечную геометрическую прогрессию. Таким образом, получаем верхнюю оценку, что завершает доказательство.

§ 13. Приложение

Доказательство леммы 5. Предположим $\mathcal T(M_1, \overline{\boldsymbol a}_1)=\mathcal T(M_2, \overline{\boldsymbol a}_2)$. Докажем сначала, что $\rho(M_1^{-1})=\rho(M_2^{-1})$, где $\rho$ – спектральный радиус матрицы. Поскольку $M_1$ не имеет кратных собственных значений и поскольку $\boldsymbol a_1$ не лежит в собственном подпространстве $M_1$, получаем $\|M_1^{-k} \boldsymbol a_1\| \asymp [\rho(M_1^{-1})]^k$, где $\asymp$ обозначает асимптотическую эквивалентность. Тогда количество отрезков в множестве $\mathcal T(M_1, \overline{\boldsymbol a}_1)$, длина которых больше заданного числа $\varepsilon$, равно ${\ln \varepsilon }/{\ln \rho(M_1^{-1})}+o(1)$ при $\varepsilon \to 0$. Поскольку $\mathcal T(M_1, \overline{\boldsymbol a}_1)=\mathcal T(M_2, \overline{\boldsymbol a}_2)$, получаем $\rho(M_1^{-1})=\rho(M_2^{-1})$.

Считаем, что $M_1^{-1}$ имеет единственное максимальное по модулю собственное значение (либо два комплексно сопряженных). Иначе задача распадается на несколько задач меньших размерностей. Назовем максимальное по модулю собственное значение старшим, и его собственный вектор также назовем старшим собственным вектором. Пусть $V_i$ – подпространство в $\mathbb R^d$, порожденное старшими собственными векторами матрицы $M_i^{-1}$, $i=1,2$. Возможны два случая.

1) $\dim V_1=1$. В этом случае старшее собственное значение $\lambda$ действительное, и $V_1$ порождено старшим собственным вектором $\boldsymbol v_1$. Тогда направление отрезка $M_1^{-k}\overline{\boldsymbol a}_1$ стремится к направлению $V_1$ при $k \to \infty$. Следовательно, отношение длин последовательных отрезков $M_1^{-k-1}\overline{\boldsymbol a}_1$ и $M_1^{-k}\overline{\boldsymbol a}_1$ стремится к $\rho(M_1^{-1})$ при $k \to \infty$. Поскольку $\rho(M_1^{-1}) < 1$, при достаточно больших $k$ нам известен порядок элементов в последовательности $\{M_1^{-k}\overline{\boldsymbol a}_1\}_{k\geqslant N}$. Это значит, что при достаточно малом $\varepsilon > 0$ нам известен порядок отрезков длины меньше $\varepsilon$ в множестве $\mathcal T(M_1, \overline{\boldsymbol a}_1)$. Взяв последовательно $d+2$ отрезка, обозначим через $\ell_1, \dots \ell_{d+2}$ прямые линии, на которых они лежат. Оператор $M_1^{-1}$ переводит прямую $\ell_i$ в $\ell_{i+1}$, $i=1, \dots, d+1$. Интерпретируя каждую прямую как точку в проективном пространстве $\mathbb{P}^{d-1}$, мы видим, что оператор $M_1^{-1}$ определяется однозначно, с точностью до знака, как оператор в $\mathbb{P}^{d-1}$, переводящий заданные $d+1$ точки в заданные точки. Если теперь рассмотреть оператор $M_2^{-1}$, то он обязан иметь тот же старший собственный вектор $\boldsymbol v_2=\boldsymbol v_1$, как единственное предельное направление отрезков множества $\mathcal T(M_2, \overline{\boldsymbol a}_2)$ (следовательно, ${\dim V_2}=1$), тот же порядок отрезков длины меньше $\varepsilon$, а значит, и те же прямые $\ell_1, \dots, \ell_{d+2}$ в том же порядке. Следовательно, $M_1$ и $M_2$ образуют один и тот же проективный оператор в $\mathbb{P}^{d-1}$, поэтому $M_1=\pm M_2$.

2) $\dim V_1=2$. В этом случае старшее собственное значение $M_1^{-1}$ имеет вид $r e^{ 2\pi i \alpha_1}$, где $r=\rho(M_1^{-1})$. Нам необходимо рассмотреть два случая.

a) $\alpha_1={p}/{q}$ – рационально (${p}/{q}$ – несократимая дробь). B подходящем базисе на двумерной плоскости $V_1$ оператор $M_1^{-1}|_{V_1}$ – поворот на угол ${2\pi p}/{q} $ с умножением на $r$. Отрезки $M_1^{-k}\overline{\boldsymbol a}_1$ будут иметь ровно $q$ предельных направлений, соответствующих углам ${2\pi n}/{q}$, $n=0, \dots, q-1$. Этих направлений минимум три, поскольку случай $q=2$ соответствует случаю 1) действительного $\lambda$. Поэтому существует единственное линейное преобразование, переводящее предельные направления множества $\mathcal T(M_1, \overline{\boldsymbol a}_1)$ в направления углов ${2\pi p}/{q}$, $p=0, \dots, q-1$. Следовательно, базис на плоскости $V_1$, в котором оператор $M_1^{-1}$ – поворот со сжатием, определяется по множеству $\mathcal T(M_1, \overline{\boldsymbol a}_1)$ однозначно. В этом базисе отношение длин последовательных отрезков во множестве $\{M_1^{-k}\overline{\boldsymbol a}_1\}_{k \geqslant N} $ стремится к $r$, откуда мы узнаем порядок элементов этой последовательности. Далее рассуждение такое же, как и в п. 1): зная порядок последовательности, мы однозначно восстанавливаем оператор $M_1^{-1}$ и тем самым доказываем, что $M_1=\pm M_2$.

b) $ \alpha_1$ иррационально. В этом случае в подходящем базисе на двумерной плоскости $V_1$ оператор $M_1^{-1}|_{V_1}$ – поворот на иррациональный угол $2\pi \alpha_1$ с умножением на $r$. Чтобы идентифицировать этот базис, воспользуемся теоремой Вейля о равномерном распределении [59]: траектория иррационального поворота единичного вектора стремится к равномерному распределению на окружности. Это значит, что для каждой дуги единичной окружности доля точек, попавших в эту дугу, к доле всех точек последовательности от первой до $n$-й стремится к отношению длины дуги к длине окружности. Количество отрезков в множестве $\mathcal T(M_1, \overline{\boldsymbol a}_1)$, длина которых больше $\varepsilon$, равно ${\ln \varepsilon }/{\ln r}+O(1)$ при $\varepsilon \to 0$. Число этих отрезков, попавших в заданный угол величины $\beta$, равно ${\beta\ln \varepsilon }/{\pi \ln r}+o(1)$, $\varepsilon \to 0$. Если есть другой подходящий базис в $V_1$, то в нем должно быть такое же значение угла $\beta$. Таким образом, в новом базисе значения всех углов такие же, как и в старом. Следовательно, это тот же базис, с точностью до ортогонального преобразования. Итак, для данного множества $\mathcal T(M_1, \overline{\boldsymbol a}_1)$ существует единственный, с точностью до ортогонального преобразования, базис на двумерной плоскости $V_1$, в котором оператор $M_1^{-1}$ является поворотом с умножением на $r$. В этом базисе определяется порядок отрезков в данной последовательности, а значит, определяется и сам оператор $M_1^{-1}$ с точностью до знака. Если теперь взять оператор $M_2^{-1}$ с тем же множеством $\mathcal T(M_2, \overline{\boldsymbol a}_2)=\mathcal T(M_1, \overline{\boldsymbol a}_1)$, то он будет иметь ту же плоскость $V_2=V_1$, как предельную плоскость направлений отрезков из $\mathcal T(M_2, \overline{\boldsymbol a}_2)$, с тем же базисом, в котором $M_2^{-1}$ будет задавать поворот с умножением. Следовательно, последовательность $M_2^{-k}\overline{\boldsymbol a}_2$ при больших $k$ будет иметь тот же порядок элементов. Так же, как в п. 1), зная порядок последовательности, мы однозначно восстанавливаем оператор $M_2^{-1}$ и тем самым доказываем, что $M_1=\pm M_2$. Лемма доказана.

Доказательство леммы 6. Не ограничивая общности, считаем, что $n_1 \leqslant n_2 \leqslant n_3$. Пусть $d=3k+r$, $r \in \{0, 1, 2\}$. При $k=0$ утверждение очевидно, поэтому считаем $k \geqslant 1$. Тогда $n_1 \leqslant k$, а $n_2 \in[n_1,[(d-n_1)/2]]$, где $[x]$ – целая часть числа $x$. Следовательно,
$$ \begin{equation*} b(d)=\sum_{n_1=1}^{k}\biggl(\biggl[\frac{d-n_1}{2}\biggr]- n_1+1\biggr). \end{equation*} \notag $$
Количество нечетных среди чисел $d-n_1$, $n_1=1, \dots, k$, не меньше $(k-1)/{2}$ и не больше $(k+1)/{2}$. Поэтому
$$ \begin{equation*} - \frac{k+1}{2}+\sum_{n_1=1}^{k}\biggl(\frac{d-n_1}{2}- n_1+1\biggr) \leqslant b(d)\leqslant-\frac{k-1}{2}+\sum_{n_1=1}^{k}\biggl(\frac{d-n_1}{2}- n_1+1\biggr). \end{equation*} \notag $$
Откуда простым вычислением получаем результат. Лемма доказана.

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

Авторы признательны за полезные обсуждения С. Конягину, А. Дубицкасу, И. Шкредову, Н. Мощевитину и С. Иванову.

Список литературы

1. S. Akiyama, H. Brunotte, A. Pethő, J. M. Thuswaldner, “Generalized radix representations and dynamical systems. III”, Osaka J. Math., 45:2 (2008), 347–374  mathscinet  zmath
2. S. Akiyama, N. Gjini, “On the connectedness of self-affine attractors”, Arch. Math. (Basel), 82:2 (2004), 153–163  crossref  mathscinet  zmath
3. S. Akiyama, B. Loridant, “Boundary parametrization of planar self-affine tiles with collinear digit set”, Sci. China Math., 53:9 (2010), 2173–2194  crossref  mathscinet  zmath  adsnasa
4. S. Akiyama, B. Loridant, J. M. Thuswaldner, “Topology of planar self-affine tiles with collinear digit set”, J. Fractal Geom., 8:1 (2021), 53–93  crossref  mathscinet  zmath; arXiv: 1801.02957
5. S. Akiyama, A. Pethő, “On the distribution of polynomials with bounded roots. II. Polynomials with integer coefficients”, Unif. Distrib. Theory, 9:1 (2014), 5–19  mathscinet  zmath
6. S. Akiyama, J. M. Thuswaldner, “A survey on topological properties of tiles related to number systems”, Geom. Dedicata, 109:1 (2004), 89–105  crossref  mathscinet  zmath
7. C. Bandt, Combinatorial topology of three-dimensional self-affine tiles, arXiv: 1002.0710
8. C. Bandt, “Self-similar sets. V. Integer matrices and fractal tilings of $\mathbb R^n$”, Proc. Amer. Math. Soc., 112:2 (1991), 549–562  crossref  mathscinet  zmath
9. C. Bandt, G. Gelbrich, “Classification of self-affine lattice tilings”, J. London Math. Soc. (2), 50:3 (1994), 581–593  crossref  mathscinet  zmath
10. J. J. Benedetto, M. T. Leon, “The construction of multiple dyadic minimally supported frequency wavelets on $\mathbb R^d$”, The functional and harmonic analysis of wavelets and frames (San Antonio, TX, 1999), Contemp. Math., 247, Amer. Math. Soc., Providence, RI, 1999, 43–74  crossref  mathscinet  zmath
11. J. J. Benedetto, S. Sumetkijakan, “Tight frames and geometric properties of wavelet sets”, Adv. Comput. Math., 24:1-4 (2006), 35–56  crossref  mathscinet  zmath
12. C. Bandt, Y. Wang, “Disk-like self-affine tiles in $\mathbb R^2$”, Discrete Comput. Geom., 26:4 (2001), 591–601  crossref  mathscinet  zmath
13. M. Bownik, Anisotropic Hardy spaces and wavelets, Mem. Amer. Math. Soc., 164, no. 781, Amer. Math. Soc., Providence, RI, 2003, vi+122 pp.  crossref  mathscinet  zmath
14. A. S. Cavaretta, W. Dahmen, C. A. Micchelli, Stationary subdivision, Mem. Amer. Math. Soc., 93, no. 453, Amer. Math. Soc., Providence, RI, 1991, vi+186 pp.  crossref  mathscinet  zmath
15. M. Cotronei, D. Ghisi, M. Rossini, T. Sauer, “An anisotropic directional subdivision and multiresolution scheme”, Adv. Comput. Math., 41 (2015), 709–726  crossref  mathscinet  zmath
16. C. A. Cabrelli, C. Heil, U. M. Molter, Self-similarity and multiwavelets in higher dimensions, Mem. Amer. Math. Soc., 170, no. 807, Amer. Math. Soc., Providence, RI, 2004, viii+82 pp.  crossref  mathscinet  zmath
17. M. Charina, T. Mejstrik, “Multiple multivariate subdivision schemes: matrix and operator approaches”, J. Comput. Appl. Math., 349 (2019), 279–291  crossref  mathscinet  zmath
18. M. Charina, V. Yu. Protasov, “Regularity of anisotropic refinable functions”, Appl. Comput. Harmon. Anal., 47:3 (2019), 795–821  crossref  mathscinet  zmath
19. A. Cohen, K. Gröchenig, L. F. Villemoes, “Regularity of multivariate refinable functions”, Constr. Approx., 15:2 (1999), 241–255  crossref  mathscinet  zmath
20. G. R. Conner, J. M. Thuswaldner, “Self-affine manifolds”, Adv. Math., 289 (2016), 725–783  crossref  mathscinet  zmath
21. N. Desprez, Chaoscope, Software http://www.chaoscope.org/
22. A. Dubickas, S. V. Konyagin, “On the number of polynomials of bounded measure”, Acta Arith., 86:4 (1998), 325–342  crossref  mathscinet  zmath
23. Qi-Rong Deng, Ka-sing Lau, “Connectedness of a class of planar self-affine tiles”, J. Math. Anal. Appl., 380:2 (2011), 493–500  crossref  mathscinet  zmath
24. Xingde Dai, D. R. Larson, D. M. Speegle, “Wavelet sets in $\mathbb R^n$”, J. Fourier Anal. Appl., 3:4 (1997), 451–456  crossref  mathscinet  zmath
25. A. Dubickas, “Counting integer reducible polynomials with bounded measure”, Appl. Anal. Discrete Math., 10:2 (2016), 308–324  crossref  mathscinet  zmath
26. Xiaoye Fu, J.-P. Gabardo, Self-affine scaling sets in $\mathbb R^2$, Mem. Amer. Math. Soc., 233, no. 1097, Amer. Math. Soc., Providence, RI, 2015, vi+85 pp.  crossref  mathscinet  zmath
27. W. J. Gilbert, “Radix representations of quadratic fields”, J. Math. Anal. Appl., 83:1 (1981), 264–274  crossref  mathscinet  zmath
28. A. M. Garsia, “Arithmetic properties of Bernoulli convolutions”, Trans. Amer. Math. Soc., 102:3 (1962), 409–432  crossref  mathscinet  zmath
29. G. Gelbrich, “Self-affine lattice reptiles with two pieces in $\mathbb R^n$”, Math. Nachr., 178:1 (1996), 129–134  crossref  mathscinet  zmath
30. R. F. Gundy, A. L. Jonsson, “Scaling functions on $\mathbb R^2$ for dilations of determinant $\pm 2$”, Appl. Comput. Harmon. Anal., 29:1 (2010), 49–62  crossref  mathscinet  zmath
31. C. Gröchenig, W. R. Madych, “Multiresolution analysis, Haar bases, and self-similar tilings of $\mathbf R^n$”, IEEE Trans. Inform. Theory, 38:2, Part 2 (1992), 556–568  crossref  mathscinet  zmath
32. K. Gröchenig, A. Haas, “Self-similar lattice tilings”, J. Fourier Anal. Appl., 1:2 (1994), 131–170  crossref  mathscinet  zmath
33. Xing-Gang He, Ka-Sing Lau, “Characterization of tile digit sets with prime determinants”, Appl. Comput. Harmon. Anal., 16:3 (2004), 159–173  crossref  mathscinet  zmath
34. D. Hacon, N. C. Saldanha, J. J. P. Veerman, “Remarks on self-affine tilings”, Exp. Math., 3:4 (1994), 317–327  crossref  mathscinet  zmath
35. I. Kirat, Ka-Sing Lau, “On the connectedness of self-affine tiles”, J. London Math. Soc. (2), 62:1 (2000), 291–304  crossref  mathscinet  zmath
36. I. Kirat, Ka-Sing Lau, “Classification of integral expanding matrices and self-affine tiles”, Discrete Comput. Geom., 28:1 (2002), 49–73  crossref  mathscinet  zmath
37. I. Kirat, Ka-Sing Lau, Hui Rao, “Expanding polynomials and connectedness of self-affine tiles”, Discrete Comput. Geom., 31:2 (2004), 275–286  crossref  mathscinet  zmath
38. A. Kravchenko, D. Mekhontsev, IFS Builder 3d, Software http://fractals.nsu.ru/builder3d_en.htm
39. A. Krivoshein, V. Protasov, M. Skopina, Multivariate wavelets frames, Ind. Appl. Math., Springer, Singapore, 2016, xiii+248 pp.  crossref  mathscinet  zmath
40. P. Kirschenhofer, J. M. Thuswaldner, “Shift radix systems–a survey”, Numeration and substitution 2012, RIMS Kôkyûroku Bessatsu, B46, Res. Inst. Math. Sci. (RIMS), Kyoto, 2014, 1–59  mathscinet  zmath
41. P. Kirschenhofer, A. Thuswaldner, “Distribution results on polynomials with bounded roots”, Monatsh. Math., 185:4 (2018), 689–715  crossref  mathscinet  zmath
42. J. C. Lagarias, Yang Wang, “Haar type orthonormal wavelet bases in $\mathbf R^2$”, J. Fourier Anal. Appl., 2:1 (1995), 1–14  crossref  mathscinet  zmath
43. J. C. Lagarias, Yang Wang, “Haar bases for $L^2(\mathbb R^n)$ and algebraic number theory”, J. Number Theory, 57:1 (1996), 181–197  crossref  mathscinet  zmath
44. J. C. Lagarias, Yang Wang, “Integral self-affine tiles in $\mathbb R^n$. II. Lattice tilings”, J. Fourier Anal. Appl., 3:1 (1997), 83–102  crossref  mathscinet  zmath
45. J. Lagarias, Yang Wang, “Corrigendum/addendum: "Haar bases for $L_2(\mathbb R^n)$ and algebraic number theory"”, J. Number Theory, 76:2 (1999), 330–336  crossref  mathscinet  zmath
46. T. Mejstrik, “Algorithm 1011: improved invariant polytope algorithm and applications”, ACM Trans. Math. Software, 46:3 (2020), 29, 26 pp.  crossref  mathscinet  zmath
47. D. Mekhontsev, IFStile, Software http://ifstile.com/
48. K. D. Merrill, “Simple wavelet sets in $\mathbb R^n$”, J. Geom. Anal., 25:2 (2015), 1295–1305  crossref  mathscinet  zmath
49. K. D. Merrill, Generalized multiresolution analyses, Lect. Notes Appl. Numer. Harmon. Anal., Birkhäuser/Springer, Cham, 2018, x+113 pp.  crossref  mathscinet  zmath
50. F. Morgan, Geometric measure theory. A beginner's guide, Academic Press, Inc., Boston, MA, 1988, viii+145 pp.  mathscinet  zmath
51. И. Я. Новиков, В. Ю. Протасов, М. А. Скопина, Теория всплесков, Физматлит, М., 2005, 613 с.  mathscinet  zmath; англ. пер.: I. Ya. Novikov, V. Yu. Protasov, M. A. Skopina, Wavelet theory, Transl. Math. Monogr., 239, Amer. Math. Soc., Providence, RI, 2011, xiv+506 с.  crossref  mathscinet  zmath
52. Sze-Man Ngai, V. F. Sirvent, J. J. P. Veerman, Yang Wang, “On 2-reptiles in the plane”, Geom. Dedicata, 82:1-3 (2000), 325–344  crossref  mathscinet  zmath
53. В. Ю. Протасов, “Обобщенный совместный спектральный радиус. Геометрический подход”, Изв. РАН. Сер. матем., 61:5 (1997), 99–136  mathnet  crossref  mathscinet  zmath; англ. пер.: V. Yu. Protasov, “The generalized joint spectral radius. A geometric approach”, Izv. Math., 61:5 (1997), 995–1030  crossref  adsnasa
54. V. Yu. Protasov, “Surface dimension, tiles, and synchronizing automata”, SIAM J. Math. Anal., 52:4 (2020), 3463–3486  crossref  mathscinet  zmath
55. H. Rademacher, “Über partielle und totale Differenzierbarkeit von Funktionen mehrerer Variablen und über die Transformation der Doppelintegrale”, Math. Ann., 79:4 (1919), 340–359  crossref  mathscinet  zmath
56. W. Steiner, J. M. Thuswaldner, “Rational self-affine tiles”, Trans. Amer. Math. Soc., 367:11 (2015), 7863–7894  crossref  mathscinet  zmath
57. J. M. Thuswaldner, Shu-qin Zhang, “On self-affine tiles whose boundary is a sphere”, Trans. Amer. Math. Soc., 373:1 (2020), 491–527  crossref  mathscinet  zmath
58. M. Uray, On the expansivity gap of integer polynomials, arXiv: 1905.06976
59. H. Weyl, “Über die Gleichverteilung von Zahlen mod. Eins”, Math. Ann., 77:3 (1916), 313–352  crossref  mathscinet  zmath
60. P. Wojtaszczyk, A mathematical introduction to wavelets, London Math. Soc. Stud. Texts, 37, Cambridge Univ. Press, Cambridge, 1997, xii+261 pp.  crossref  mathscinet  zmath
61. T. Zaitseva, “Haar wavelets and subdivision algorithms on the plane”, Adv. Syst. Sci. Appl., 17:3 (2017), 49–57  crossref
62. Т. И. Зайцева, “Простые тайлы и аттракторы”, Матем. сб., 211:9 (2020), 24–59  mathnet  crossref  mathscinet  zmath; англ. пер.: T. I. Zaitseva, “Simple tiles and attractors”, Sb. Math., 211:9 (2020), 1233–1266  crossref  adsnasa
63. V. G. Zakharov, “Rotation properties of 2D isotropic dilation matrices”, Int. J. Wavelets Multiresolut. Inf. Process., 16:1 (2018), 1850001, 14 pp.  crossref  mathscinet  zmath

Образец цитирования: Т. И. Зайцева, В. Ю. Протасов, “Самоподобные 2-аттракторы и тайлы”, Матем. сб., 213:6 (2022), 71–110; T. I. Zaitseva, V. Yu. Protasov, “Self-affine $2$-attractors and tiles”, Sb. Math., 213:6 (2022), 794–830
Цитирование в формате AMSBIB
\RBibitem{ZaiPro22}
\by Т.~И.~Зайцева, В.~Ю.~Протасов
\paper Самоподобные 2-аттракторы и тайлы
\jour Матем. сб.
\yr 2022
\vol 213
\issue 6
\pages 71--110
\mathnet{http://mi.mathnet.ru/sm9682}
\crossref{https://doi.org/10.4213/sm9682}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4461454}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2022SbMat.213..794Z}
\transl
\by T.~I.~Zaitseva, V.~Yu.~Protasov
\paper Self-affine $2$-attractors and tiles
\jour Sb. Math.
\yr 2022
\vol 213
\issue 6
\pages 794--830
\crossref{https://doi.org/10.1070/SM9682}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000992264800004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85137695252}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sm9682
  • https://doi.org/10.4213/sm9682
  • https://www.mathnet.ru/rus/sm/v213/i6/p71
  • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Статистика просмотров:
    Страница аннотации:529
    PDF русской версии:51
    PDF английской версии:63
    HTML русской версии:279
    HTML английской версии:102
    Список литературы:74
    Первая страница:18
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024