| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) Самоподобные 2-аттракторы и тайлы Т. И. Зайцеваab, В. Ю. Протасовcb a Московский центр фундаментальной и прикладной математики b Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова c University of L'Aquila, Italy
Англоязычная версия:
Sbornik: Mathematics, 2022, Volume 213, Issue 6, Pages 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$, определяется как Самоподобный аттрактор является компактом с непустой внутренностью, а его мера Лебега $|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$) порождают один и тот же тип. В теореме 8 (§ 9) мы устанавливаем обратное: аттракторы, соответствующие различным и не противоположным полиномам, не аффинно подобны друг другу. Этот факт, доказательство которого довольно сложно, позволяет находить число различных (с точностью до аффинного подобия) 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$, т.е. матриц вида Заметим, что $\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$. Лемма доказана. Доказательство. Пусть 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$ имеет вид Таким образом, $\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]. Поэтому растягивающая целая матрица с простым определителем является изотропной тогда и только тогда, когда ее полином изотропный. Доказательство. Если $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$ – квадратичный целый изотропный полином. Положим – сопровождающая матрица полинома $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$-мерному шару, получаем Из работы [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] о свойствах и вычислении поверхностной размерности для аттракторов. Доказательство. Ясно, что $|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-аттракторов, то мы лишь можем сформулировать следующее предположение. § 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$. Предложение доказано. В качестве первого следствия получим следующий любопытный факт о драконах. Он наверняка известен, но мы не смогли найти ссылки, поэтому включаем его доказательство. Доказательство. Матрица дракона $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-аттракторов. Многогранным множеством называется объединение конечного числа многогранников. Доказательство. Согласно теореме 6 многогранным множеством среди 2-аттракторов может быть либо параллелепипед, либо произведение драконов. Дракон, однако, не является многогранным множеством, поскольку его показатель Гёльдера в $L_2$ меньше $0.5$. При доказательстве теоремы 6 мы установили, что выпуклая оболочка неизотропного 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$. Поэтому, естественно сформулировать проблему по-другому. Поскольку 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]) факт. Доказательство. Пусть $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$ имеют противоположные характеристические полиномы. Доказательство. Характеристическая функция $\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-аттракторов
В силу следствия 6 (§ 9) вопрос о числе 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, то оно удовлетворяет неравенству Заметим, что главные члены верхней и нижней оценок на $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-аттракторов
Для каждого из возможных семи многочленов, указанных в табл. 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)$ по формуле § 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 встречались в литературе, серии 3–7, насколько нам известно, новые. Серии целых растягивающих многочленов со старшим коэффициентом $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}$. Серия 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. Несложно убедиться в том, что все многочлены серий 1–7 различны (кроме случая $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$. Многочлен можно переписать в виде суммы двух прогрессий Отсюда следует, что у этого многочлена свободный член $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$, что завершает доказательство утверждения. В нашем случае Доказательство для серии 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, всегда лежит в правой полуплоскости и не может быть отрицательным действительным числом. Теперь мы можем дать обещанное доказательство теоремы 9 (§ 10). Через $b_{+}(d)$ обозначим количество хороших разбиений числа $d$, через $b_{-}(d)$ – количество плохих разбиений (определения см. § 10), а через $b(d)$ – количество всех разбиений числа $d$ в сумму натуральных слагаемых. Таким образом, $b(d)=b_{-}(d)+b_{+}(d)$. Мы используем следующую известную оценку. Поскольку слагаемое $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 где $v_j \in [-1,1]$. В последнем слагаемом $a_{\ell -1}$ не делится на 3, поэтому числитель в первой дроби может увеличиться на $2$. Таким образом, где $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$. Следовательно, Количество нечетных среди чисел $d-n_1$, $n_1=1, \dots, k$, не меньше $(k-1)/{2}$ и не больше $(k+1)/{2}$. Поэтому Откуда простым вычислением получаем результат. Лемма доказана. БлагодарностиАвторы признательны за полезные обсуждения С. Конягину, А. Дубицкасу, И. Шкредову, Н. Мощевитину и С. Иванову.
Цитирование в формате AMSBIB
\RBibitem{ZaiPro22} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|