| Sbornik: Mathematics |
|
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers) Self-affine T. I. Zaitsevaab, V. Yu. Protasovcb a Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia b Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia c University of L'Aquila, L'Aquila, Italy
Bibliographic databases:
     § 1. IntroductionA self-affine attractor in $\mathbb{R}^d$ (also known in the literature as an integer self-affine tile) is a compact set defined by an integer $d\times d$ matrix $M$ and by a finite set of integer vectors (‘digits’) $D = \{\boldsymbol{d}_0, \dots, \boldsymbol{d}_{m-1}\}\subset \mathbb{Z}^d$, where $m = |\operatorname{det} M|$. The matrix $M$ is assumed to be expanding, that is, the moduli of all of its eigenvalues are larger than $1$. The digits $\boldsymbol{d}_i \in D$ are taken from different cosets in $\mathbb{Z}^d/M\mathbb{Z}^d$, which means that $\boldsymbol{d}_{i} - \boldsymbol{d}_j \notin M\mathbb{Z}^d$ whenever $i\ne j$. Definition 1. The self-affine attractor corresponding to an expanding integer matrix $M$ and a set of digits $D$ is the following set: A self-affine attractor is a compact set with nonempty interior, and its Lebesgue measure $|G|$ is always a natural number. The integer shifts $\{G+k\}_{k \in \mathbb{Z}^d}$ cover the whole space $\mathbb{R}^d$ with $|G|$ layers, that is, every point $x\in \mathbb{R}^d$, apart from a null set, belongs to exactly $|G|$ shifts. In the case when $|G| = 1$ the attractor is called a tile and its shifts form a tiling of the space, that is, a one-layer partition of it (see [32] and [44]). Formula (1) means that in the $M$-adic system with digits in $D$ the attractor plays the role of a unit line segment in the space $\mathbb{R}^d$. However, even on the line $\mathbb{R}$, an attractor can be different from a line segment. For example, in the triadic system with digits $0$, $1$ and $2$ the set $G$ is a closed interval, but if the digit $2$ is replaced by $5$, then $G$ becomes a fractal-like set with an infinite number of connected components [60], [18]. Similarly to a line segment, any attractor is self-affine. For an arbitrary $\boldsymbol{a} \in \mathbb{Z}^d$ we denote by $M_{\boldsymbol{a}}$ the affine operator $M_{\boldsymbol{a}} \boldsymbol{x} = M\boldsymbol{x} - \boldsymbol{a}$, $\boldsymbol{x} \in \mathbb{R}^d$. It is easily shown that $G = \bigcup_{\boldsymbol{a}\in D} M_{\boldsymbol{a}}^{-1} G$, and since each set $M_{\boldsymbol{a}}^{-1} G$ has measure $m^{-1}|G|$ and the sum of these measures is equal to $|G|$, all these sets have intersections of zero measure. Therefore, up to a null set, $G$ is a disjoint union of shifts of the set $M^{-1}G$, that is, $G$ is indeed self-affine. That is why the characteristic function $\varphi = \chi_G$ of an arbitrary attractor is a refinable function, which satisfies the refinement equation
$$
\begin{equation}
\varphi(\boldsymbol x)=\sum_{\boldsymbol k \in D} \varphi (M\boldsymbol x -\boldsymbol k).
\end{equation}
\tag{2}
$$
If the attractor is a tile, then $\varphi$ possesses orthonormal integer shifts. Consequently, it generates a multiresolution analysis (MRA) of the space $L_2(\mathbb{R}^d)$. That is why tiles are applied to the construction of wavelets systems, in particular, of Haar bases in $L_2(\mathbb{R}^d)$ (see [11], [16], [31], [39], [42], [60] and [63], for example). An attractor is called isotropic if it is generated by an isotropic matrix $M$, which is a matrix with all eigenvalues of equal moduli but without nontrivial Jordan blocks. An isotropic matrix is similar to an orthogonal matrix multiplied by a scalar. Isotropic attractors are most popular in applications. An important class of attractors is two-digit attractors (2-attractors), for which $\operatorname{det} M = \pm 2$. In this case $m = |D| = 2$ and the $M$-adic system in $\mathbb{R}^d$ is similar to the dyadic system on the real line. In particular, each 2-attractor $G$ decomposes into two equal copies $M^{-1}(G+\boldsymbol{d}_0)$ and $M^{-1}(G+\boldsymbol{d}_1)$ and refinement equation (2) has only two terms. The Haar system has a unique generating function $\psi(\boldsymbol{x})=\varphi(M\boldsymbol{x}-\boldsymbol{d}_0) -\varphi(M\boldsymbol{x}-\boldsymbol{d}_1)$, unlike in the general case, when it has $m-1$ generating functions. For wavelet systems the situation is the same: in the two-digit case the system of wavelets is generated by one wavelet function and the corresponding MRA has a dyadic structure similarly to wavelets in $L_2(\mathbb{R})$. That is why wavelet systems generated by 2-attractors are natural and convenient in use. Two-digit attractors are extensively studied in the literature, a brief overview is given at the end of this section. It is known that for every $d$ there exist finitely many different 2-attractors in $\mathbb{R}^d$ up to affine similarity. In $\mathbb{R}^2$ there are precisely three 2-attractors: a square, a dragon, and a bear. All of them are isotropic. In $\mathbb{R}^3$ there exist seven 2-attractors, and there is only one isotropic attractor among them, namely, a cube. The main resultsWe derive a classification and find some geometric and topologic properties of 2-attractors. Some of our results, where possible, will be extended to an arbitrary number of digits. In the isotropic case the classification problem is solved completely (§ 5). This classification turns out to be rather simple, which is a bit surprising. Namely, in odd dimensions $d=2k+1$ all isotropic 2-attractors are parallelepipeds (Theorem 3), while in every even dimension $d=2k$ there exist precisely three 2-attractors up to affine similarity. These are a parallelepiped, the direct product of $k$ (two-dimensional) dragons and the direct product of $k$ (two-dimensional) bears (Theorem 4). The proofs are constructive, and the matrices $M$ of these 2-attractors are explicitly found. The classification obtained enables us to establish many properties of isotropic 2-attractors. In particular, we show that all isotropic 2-attractors in $\mathbb{R}^d$ are homeomorphic to the $d$-dimensional ball, but not $C^1$-diffeomorphic to one another. Moreover, all these three types of isotropic 2-attractors in an even-dimensional space are not pairwise metrically equivalent. This means that they cannot be mapped one to another by bi-Lipschitz maps (Theorem 5 in § 6). Properties of convex hulls of 2-attractors are analysed in § 7. It turns out that among all 2-attractors there are exactly two with polyhedral convex hulls, namely, a parallelepiped, whose convex hull has, of course, $2^d$ vertices, and a dragon, whose convex hull has $2^{3d/2}$ vertices. For all other 2-attractors the convex hull is a zonoid with infinitely many extreme points. In § 8 we consider applications. We show that every isotropic 2-attractor is a tile, hence it generates an MRA and a Haar system in $L_2(\mathbb{R}^d)$, provided the matrix $M$ and the set of digits $D$ are chosen in an appropriate way (Theorem 7 describes this choice explicitly). We emphasise that the Haar function generated by a direct product of the bivariate dragons is distinct from the product of bivariate Haar functions! For general (nonisotropic) 2-attractors the analogous statements are formulated as a conjecture, which is verified in small dimensions (Proposition 4). The basic auxiliary fact concerning 2-attractors is that they are uniquely defined, up to affine similarity, by the spectrum of the dilation matrix $M$ and do not actually depend on the digits $D$. This was first proved in [29]. In § 3 we give another proof, which makes it possible to extend this property to arbitrary attractors whose digits form an arithmetic progression (Theorem 2). Thus, the type of a 2-attractor depends entirely on the characteristic polynomial of the matrix $M$. Moreover, opposite polynomials (that is, the characteristic polynomials of matrices $M$ and $-M$) generate the same type. Theorem 8 in § 9 establishes the opposite: two attractors corresponding to distinct, but not opposite polynomials are not affinely similar to each other. This fact, whose proof is quite difficult, enables us to find the total number of different 2-attractors (up to affine similarity) in an arbitrary dimension $d$. This number is equal to the number of distinct expanding integer polynomials of degree $d$ with leading coefficient $1$ and free coefficient $\pm 2$ that are not opposite one to another. Expanding means that all roots of these polynomials are larger than $1$ in absolute value. In this way we obtain the number $N(d)$ of different 2-attractors in the space $\mathbb{R}^d$: $N(2)= 3$, $N(3) = 7$, $N(4) = 21$ and so on. In § 10 (Theorem 10) we show that $C_1d^2\leqslant N(d)\leqslant C_2 2^{d}$ (the constants are explicitly given in the statement of the theorem). The upper bound is derived from a result of Dubickas and Konyagin on the total number of integer polynomials with prescribed Mahler measure [22]. To obtain the lower bound we construct a series of integer expanding polynomials $p(z) = z^d + a_{d-1}z^{d-1}+ \dots + a_1 z \pm 2$ which contains a quadratic in $d$ number of polynomials. Only two series were previously known in the literature, both of which are linear in $d$ [34]. In § 12 we add five new series and a quadratic one among them. We see that the lower and upper bounds for $N(d)$ are far apart. Numerical results show that at least for $d\leqslant 8$, our upper bound seems to be tight: $N(d)$ grows as $2^d$. However, this is an open problem to give a proof of this fact or to come up with sharper bounds. Finally, in § 11 we analyse the regularity of 2-attractors and compute the Hölder exponents in $L_2(\mathbb{R}^d)$ for the corresponding Haar functions. We do this in the isotropic case for all $d$ and in the general case for small $d$. From the results obtained one can conclude that different 2-attractors always have different smoothness. A brief survey of the literature on 2-attractorsThe first examples of 2-attractors were presented in [27] and [8], where some properties were studied. The pioneering works [32], [31], [42] and [44] provided foundations of the theory of tiles and attractors and also paid much attention to the two-digit case. The topology of plane 2-attractors and combinatorial properties of the corresponding tilings of the plane were studied in [35], [37], [2] and [9] (see also § 6 for more references). In [29] it was shown that there are finitely many different, up to cyclic permutations, 2-attractors in $\mathbb{R}^d$; in [34] series of 2-attractors growing linearly in $d$ were presented. All types of 2-attractors in dimensions 2 and 3 (namely, three and seven types, respectively) were found in [9]. The monograph [26] and the papers [30], [33], [52] and [63] investigated various aspects of plane 2-attractors. In [42] six types of plane 2-attractors, up to integer affine similarity, were found. This classification was extended in [36] to attractors with three, four and five digits. In [61] the exponents of regularity of the plane 2-attractors were found. Some generalisations for noninteger matrices and related Pisot tilings, shift radix systems and so on were considered in [40] and [56]. Application to wavelets and related issues were addressed in many papers. Here we mention only the monographs [16], [60] and [51]. We also mention another approach to the construction of wavelets from tiles, not involving MRA (see [10], [11], [17], [24], [48] and [49]). More references can be found in the corresponding sections. NotationWe always assume a basis in $\mathbb{R}^d$ to be fixed and identify linear operators with the corresponding matrices. We denote the identity matrix by $I$ and the characteristic polynomial of a matrix $A$ by $p(\lambda) = \operatorname{det} (\lambda I - A)$. We use bold symbols for vectors and standard symbols for their components, that is, $\boldsymbol{x}=(x_1,\dots,x_d)$. We denote the Lebesgue measure of a set $X\subset\mathbb{R}^d$ by $|X|$. § 2. 2-attractors in $ {\mathbb{R}}^2$We begin with the case when $d=2$. On the two-dimensional plane there are exactly three 2-attractors up to affine similarity [9], [42], [61]. We call them a square, a dragon (some authors also use the term ‘twindragon’) and a bear (a ‘tame twindragon’). All of them are tiles and are homeomorphic to a disc [12], but not metrically equivalent to it [54]. Their partitions into two parts affinely similar to them are shown in Figure 1. The tilings by their integer shifts are shown in Figure 2. The construction of Haar functions and wavelet systems by means of plane 2-attractors was realized in [42], [60] and [31], and the smoothness of these Haar functions was analysed in [61]. The first systematic study of plane 2-attractors was presented in [27] and [8]. In [42] the matrices of plane 2-attractors were classified up to integer similarity. In this case two matrices $A$ and $B$ are considered to be equivalent if there exists an unimodular integer matrix $P \in \operatorname{GL}_2(\mathbb{Z})$ such that $P^{-1}AP = B$. There are six equivalence classes, which combine into three classes of affine isomorphic matrices. Also in [26] the case of noninteger digits was considered and in each of these six cases it was found out for which digits we obtain a tiling of the plane. In the case of three or more digits the classification problem is much more difficult because an attractor is not uniquely defined by the spectrum of the dilation matrix any longer. Nevertheless, for the small determinants $m=3,4,5$ all classes of integer affine similarity (but not of arbitrary affine similarity) of matrices were described in [36] for any possible characteristic polynomial. § 3. The spectrum of the matrix determines the 2-attractorOne of the remarkable properties of 2-attractors is that their geometry does not depend on the set of digits $D$. This was first observed in [29]. In Theorem 1 we show that a 2-attractor is uniquely (up to affine similarity) determined by the spectrum of the dilation matrix. Such uniqueness cannot be extended to a larger number of digits, for instance, to 3-attractors. Nevertheless, for some special digit sets, for example, progressions, a generalization is possible (§ 4). We begin with the observation that one digit in $D$ can be assumed to be zero. Indeed, $\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)$. Therefore, if we replace $\{\boldsymbol{d}_0, \boldsymbol{d}_1\}$ by $\{\boldsymbol{0}, \boldsymbol{d}_1 - \boldsymbol{d}_0\}$, then the attractor $G$ is translated by the vector $\bigl(\sum_{i=1}^{\infty} M^{-k}\bigr) \boldsymbol{d}_0$. Thus, in what follows we assume that $ \boldsymbol{d}_0 = 0$, and now everything depends on the choice of $\boldsymbol{d}_1$. We need the following simple auxiliary fact. Lemma 1. For an arbitrary $d\times d$ matrix $M$ and arbitrary points $\boldsymbol{a}, \boldsymbol{b} \in \mathbb{R}^d$ such that $\boldsymbol{a}$ does not lie in an eigenspace of $M$, there exists a matrix $C$ commuting with $M$ and taking $\boldsymbol{a}$ to $\boldsymbol{b}$. Proof. We pass to the Jordan basis of the matrix $M$ and consider a Jordan block $\Lambda$ of size $s$ corresponding to an eigenvalue $\lambda$. Let $\boldsymbol{a}'$ and $\boldsymbol{b}'$ be the $s$-dimensional components of the vectors $\boldsymbol{a}$ and $\boldsymbol{b}$ corresponding to this block. Denote by $\mathcal{H}$ the set of Hankel upper-triangular matrices of size $s$, that is, matrices of the form Note that $\mathcal{H}$ is a linear space and a multiplicative group. All elements of $\mathcal{H}$ commute with $\Lambda$. The set $U = \{X\boldsymbol{a}'\mid X \in \mathcal{H}\}$ is a linear subspace of $\mathbb{R}^s$ which is invariant with respect to every matrix in $\mathcal{H}$. We prove that $U=\mathbb{R}^s$. If this is not the case, then $U$ is an invariant subspace for each matrix in $\mathcal{H}$, in particular, for $\Lambda$. Therefore, $U$ coincides with one of the spaces $U_j= \bigl\{(x_1,\dots,x_j,0,\dots,0)^T\in \mathbb{R}^s\bigr\}$ (they form the complete set of invariant subspaces of $\Lambda$). Hence $\boldsymbol{a}' \in U_j$ for some $j\leqslant s-1$. Consequently, the vector $\boldsymbol{a}$ belongs to an eigenspace of the matrix $M$ spanned by all vectors of its Jordan basis except for the last $s-j$ vectors, which correspond to the block $\Lambda$. This contradicts the condition on $\boldsymbol{a}$. Thus, $U =\mathbb{R}^s$. Hence there exists a matrix $X \in \mathcal{H}$ for which $X\boldsymbol{a}' = \boldsymbol{b}'$. Recall that $X$ commutes with $\Lambda$. Having found such a matrix $X$ for each Jordan block of the matrix $M$, we form a block matrix $C$ for which $CM = MC$ and $C\boldsymbol{a} = \boldsymbol{b}$. The lemma is proved. Proof. Let $G$ be a 2-attractor, which is generated by a matrix $M$ and digits $\{\boldsymbol{0}, \boldsymbol{a}\}$, and $F$ be another 2-attractor, generated by the same matrix and digits $\{\boldsymbol{0}, \boldsymbol{b}\}$. By the definition of attractors $\boldsymbol{e}$ does not lie in an eigenspace of $M$. Therefore, Lemma 1 gives a matrix $C$ such that $CM = MC$ and $C\boldsymbol{a} = \boldsymbol{b}$. Every point of $F$ has the form Thus, $\boldsymbol{y} = C\boldsymbol{x}$, where $\boldsymbol{x}\in G$. Hence $F = CG$. The proposition is proved. Remark 1. According to Proposition 1, up to an affine similarity, a 2-attractor depends only on the expanding matrix $M$ and does not depend on the digit set $D$. As we have agreed, one of the digits in $D$ is equal to $\boldsymbol{0}$. The second digit can be an arbitrary integer point lying outside the eigenspaces of $M$. Moreover, this point can be noninteger (although this contradicts the definition of an attractor). Anyway, the attractor $G$ generated is affinely similar to a 2-attractor with integer digits. To see this, it suffices to take an arbitrary point $\boldsymbol{b} \in \mathbb{R}^d$ in the proof of Proposition 1; then nothing changes. That is why, in what follows we allow sometimes the digit $\boldsymbol{d}_1$ to be noninteger in proofs. Unless otherwise stated, we assume that $\boldsymbol{d}_1$ is the first basis vector $\boldsymbol{e} = \boldsymbol{e}_1 = (1,0,\dots,0)^T \in \mathbb{R}^d$. It is known (see [35], Proposition 2.5) that an expanding integer matrix with prime determinant cannot have multiple eigenvalues. Hence every such matrix is similar to a diagonal matrix. Therefore, two such matrices with the same spectrum are similar. Applying Proposition 1 we obtain the following. Theorem 1. A two-digit attractor is uniquely defined, up to an affine similarity, by the spectrum of the matrix $M$. Proof. Let $M= Q^{-1}\Delta Q$, where $\Delta$ is a diagonal matrix. Then for $\boldsymbol{x} \in G$ we have
$$
\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
$$
where $\boldsymbol{a}_k \in \{\boldsymbol{0}, \boldsymbol{e}\}$ for each $k$. We see that the attractor with matrix $M$ and digits $\{\boldsymbol{0}, \boldsymbol{e}\}$ is affinely similar to the attractor with matrix $\Delta$ and digits $\{\boldsymbol{0}, Q^{-1}\boldsymbol{e}\}$, and therefore, by Proposition 1 it is affinely similar to the attractor with matrix $\Delta$ and digits $\{\boldsymbol{0}, \boldsymbol{e}\}$. The theorem is proved. Thus, a 2-attractor depends on the characteristic polynomial of the matrix $M$ only. The converse is also true. Corollary 1. Every integer expanding polynomial with leading coefficient $1$ and free term $\pm 2$ generates a unique 2-attractor up to affine similarity. Proof. If $p(z) = z^d + a_{d-1}z^{d-1} + \dots + a_0$, where $a_0 = \pm 2$, is an expanding integer polynomial, then its companion matrix
$$
\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}
$$
has $p$ as the characteristic polynomial. Therefore, an attractor generated by the matrix $M$ and digits $\{\boldsymbol{0}, \boldsymbol{e}\}$ corresponds to the polynomial $p$. Applying Theorem 1 we prove uniqueness. The corollary is proved. § 4. Attractors generated by arithmetic progressionsTo what extent can the results in the previous sections be generalized to an arbitrary number of digits $m$? If the digit set $D$ is arbitrary, then no straightforward generalization is possible even in $\mathbb{R}^1$. For example, for $M=3$, when $m=3$, the attractor generated by the digits $\{0,1,2\}$ is a line segment while the one generated by $\{0,1,5\}$ is a disconnected fractal set (see [54]). So, attractors defined by the same matrix but different digit sets are not necessarily similar. The reason is that two-digit sets are always affinely similar to each other but three-digit sets are not. Nevertheless, generalizations are possible for special digit sets. For instance, when the digits form an arithmetic progression: $D = \{\boldsymbol{d}_0, \boldsymbol{d}_0+\boldsymbol{q}, \dots, \boldsymbol{d}_0+(m-1)\boldsymbol{q}\}$, where $\boldsymbol{d}_0, \boldsymbol{q} \in \mathbb{R}^d$, $\boldsymbol{q}\ne\boldsymbol{0}$. Since $D = \{\boldsymbol{0}, \boldsymbol{q}, \dots, (m-1)\boldsymbol{q}\}$ defines the same attractor shifted by $\sum_{k\in \mathbb{N}}M^{-k}\boldsymbol{d}_0$, we always assume that $\boldsymbol{d}_0=\boldsymbol{0}$. Theorem 2. All attractors generated by a fixed matrix $M$ are affinely similar, provided the digits form an arithmetic progression. Proof. We assume that $\boldsymbol{d}_0 = \boldsymbol{0}$. If a matrix $C$ commuting with $M$ (Lemma 1) maps the vector $\boldsymbol{q}_1$ to $\boldsymbol{q}_2$, then it maps the progression $D_1 = \{\boldsymbol{0}, \boldsymbol{q}_1, \dots, (m-1)\boldsymbol{q}_1\}$ to $D_2 = \{\boldsymbol{0}, \boldsymbol{q}_2, \dots, (m-1)\boldsymbol{q}_2\}$. Then we argue as in the proof of Proposition 1. The theorem is proved. Theorem 1, which states that a 2-attractor is uniquely determined by the spectrum of the dilation matrix, cannot be generalized to an arbitrary number of digits, nor even to progressions. This is because of multiple eigenvalues that can occur. The matrix $M$ can have nontrivial Jordan blocks and then it is not uniquely determined by its spectrum. One can claim that an expanding integer polynomial has no multiple roots only in the case when its free term is a prime number (see [35]). Thus, the following weaker version of Theorem 1 holds for and arbitrary prime $m$. Corollary 2. If $p$ is an integer expanding polynomial with a prime free term, then all attractors generated by matrices with characteristic polynomial $p$ and digits forming an arithmetic progression are affinely similar. Proof. Arguing as in the proof of Theorem 1 we establish an affine similarity of the attractors generated by the matrices $M$ and $\Delta$. We use the fact that the operator $Q^{-1}$ maps a progression to a progression. Then we use Theorem 1. The corollary is proved.
§ 5. Classification of isotropic 2-attractorsWe come to one of the main results of our paper: a complete list of isotropic 2-attractors. This list turns out to be surprisingly simple. Recall that a matrix is called isotropic if it is similar to an orthonormal matrix multiplied by a scalar. An attractor with an isotropic dilation matrix is also said to be isotropic. Isotropic attractors and tiles have a special place in wavelet theory and multivariate approximation theory. On the one hand, an isotropic dilation is most natural in most problems. In this case the space is expanded ‘equally in all directions’. On the other hand isotropic dilations are much simpler to study. It is for isotropic wavelets that univariate constructions have direct generalizations to the multivariate case. This concerns, for example, methods for the computation of the regularity exponents of scaling functions, methods for estimating the rate of wavelet approximation and so on. That is why in most literature on multivariate wavelets and subdivisions the authors deal with isotropic dilation matrices (see [60], [16], [39] and the detailed surveys in these works). In this section we find all isotropic 2-attractors. It turns out that their variety is not rich: in odd dimensions they are only parallelepipeds, in even dimensions direct products of dragons and direct products of bears are added. Conclusions from this classification will be drawn later. An algebraic polynomial is referred to as isotropic if all of its roots have the same absolute value. An integer polynomial that has the leading coefficient equal to $1$ and a prime free term cannot have multiple roots [35]. Therefore, an expanding integer matrix with prime determinant is isotropic if and only if its characteristic polynomial is isotropic. Proof. If $d$ is odd, then the matrix $M$ has at least one real eigenvalue, which is $2^{1/d}$ or $-2^{1/d}$ by isotropy. Substituting into the characteristic polynomial $p(z) = z^d + a_{d-1}z^{d-1} + \dots + a_1 z + a_0$ we obtain $- (z^d + a_0) = a_{d-1}z^{d-1} + \dots + a_1 z$. Observe that the number $z^d + a_0$ is an integer, hence $z = \pm 2^{1/d}$ is a root of an integer polynomial of degree $\leqslant d-1$. This is possible only if this polynomial is zero. Consequently, $p(z) = z^d + a_0$. Consider the case when $a_0 = - 2$; the case when $a_0 = 2$ is completely similar. Since the characteristic polynomial annihilates the matrix $M$, we have $p(M)= M^d - 2I = 0$. If $\{\boldsymbol{0}, \boldsymbol{e}\}$ are digits generating an attractor $G$, then $M^d\boldsymbol{e} = 2\boldsymbol{e}$. Let $\boldsymbol{a}_k = M^{k-1}\boldsymbol{e}$, $k = 1, \dots, d$, and let $P$ be the parallelepiped with vertex $\boldsymbol{0}$ and edges $\boldsymbol{a}_1, \dots, \boldsymbol{a}_d$. Then $P = M^{-1}P\sqcup M^{-1}(P+\boldsymbol{e})$. Hence the characteristic function of the set $P$ satisfies the same refinement equation as the characteristic function of $G$: $\varphi(\boldsymbol{x}) = \varphi(M\boldsymbol{x}) + \varphi(M\boldsymbol{x}-\boldsymbol{e})$. Since any refinement equation has a unique solution up to multiplication by a constant, we conclude that $\chi_{P} = \mu \chi_{G}$, where $\mu \in \mathbb{R}$ is a constant. Since both these functions take only the values $0$ and $1$, we obtain $\mu=1$ and $\chi_{P} = \chi_{G}$. The theorem is proved. Thus, in odd dimensions there are no isotropic 2-attractors except for parallelepipeds. In even dimensions we have a different situation. Even in $\mathbb{R}^2$ two new 2-attractors appear: the dragon and the bear. It turns out that the same three types exist in each even dimension. Theorem 4. If $d = 2k$ is even, then there exist exactly three isotropic 2-attractors in $\mathbb{R}^d$ up to affine similarity: a parallelepiped, a direct product of $k$ dragons, and a direct product of $k$ bears. This means that in a suitable basis in $\mathbb{R}^d$ an isotropic 2-attractor has the form $G = (K, \dots, K)$, where $K$ is either a rectangle, a dragon, or a bear, and the $i$th component $K$ corresponds to the coordinates $x_{2i}$, $x_{2i+1}$. The crucial point in the proof is as follows. Lemma 2. Every integer isotropic polynomial of degree $d = 2k$ with leading coefficient $1$ and prime free coefficient is equal to $q(z^k)$, where $q(t) = t^{2} + at + b$ is an isotropic integer quadratic polynomial. Proof. Let the polynomial have the form $z^{2k} + a_{2k - 1}z^{2k - 1} + \dots + a_1z \pm p = 0$, where $p$ is a prime number and $a_1, \dots, a_{2k -1} \in \mathbb{Z}$. Isotropy implies that all roots are equal to $p^{1/d}$ in absolute value. If there is at least one real root among them, then it is $\pm p^{1/d}$ and by repeating the proof of Theorem 3 we conclude that the polynomial is $z^{2k} \pm p$. The corresponding isotropic integer quadratic polynomial is $q(t) = t^2 \pm p$, which completes the proof. Now assume that there are no real roots. Then the roots are divided into pairs of conjugate ones $z_1 = \overline{z_2}$, $z_3 = \overline{z_4}$, …, $z_{2k-1} = \overline{z_{2k}}$. The product of the roots in one pair is $z_{2m-1}z_{2m} = |z_{2m - 1}|^2 = p^{1/k}$, $m = 1, \dots, k$. Let us show that $a_{2k - m} = a_{m} = 0$ for $m = 1, \dots, k - 1$. This will imply that the polynomial has the form $z^{2k} + a_k z^{k} \pm p$. After the change of variables $t = z^{k}$ the polynomial will become $q(t) = t^2 + a_k t \pm p$. It will remain isotropic since all roots of the $k$th degree will have the same modulus, so the proof will be complete.
To establish the equality $a_{2k - m} = a_{m} = 0$ for $m = 1, \dots, k-1$ we show first that $a_{m} = p^{(k - m) / k} a_{2k - m}$ for $m = 1, \dots, k-1$. Then both $a_{2k - m}$ and $ a_m$ are zero since they are integers, while $p^{(k - m) / k}$ is irrational for $m = 1, \dots, k-1$. By Vieta’s formulae we have
$$
\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}
$$
With each term $s = z_{j_1} \dotsb z_{j_{m}}$ in the second sum we associate a term $s_1$ in the first sum as follows. First we set $s_1$ to be the complement of $s$, which consists of those $z_i$ that are not present in $s$. Then for those $z_j$ that do not have their conjugates in $s$ we replace their conjugates in $s_1$ by $z_j$. For example, if $k = 4$ and $m = 3$, then the term $z_1z_2z_5$ is associated with $z_3 z_4 z_5 z_7 z_8$. We show that $s_1 = s p^{(k - m) / k}$. Then by (4) we have $a_{m} = p^{(k - m) / k} a_{2k - m}$, which completes the proof. The difference between the terms $s_1$ and $s$ is only in those pairs of conjugate roots that are either both present in $s$ or both absent from $s$. Let there be $a$ and $b$ such pairs, respectively. All products of conjugate roots are equal to $p^{1/k}$, hence ${s_1}/{s}=(p^{1/k})^{(b-a)}$. In total there are $m$ factors in $s$: these are $2a$ complete pairs and $k-a-b$ incomplete ones. Hence $m=k+a-b$ and $b-a=k-m$, so the required formula $s_1 = s p^{(k-m)/k}$ is proved. The proof is complete. Proof of Theorem 4. If $p$ is an integer isotropic polynomial of degree $d = 2k$, then by Lemma 2 we have $p(z) = q(z^k)$, where $q(t) = t^{2} + at + b$ is an isotropic integer quadratic polynomial. Let be the companion matrix of $q$. Since $|\operatorname{det}A|=|b|=2$ and the polynomial $q$ is isotropic, its roots have modulus $\sqrt{2}$. Hence the matrix $A$ is expanding. It was proved in [9] that every two-digit attractor in $\mathbb{R}^2$ is either a rectangle, a dragon, or a bear. Consequently, the matrix $A$ generates one of these attractors. Consider the matrix
$$
\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}
$$
formed by $2\times 2$ blocks: each zero denotes the zero $2\times 2$ matrix and $I$ is the identity $2\times 2$ matrix. Thus, $M$ is a $d\times d$ matrix and (5) is formed of $k^2$ blocks of size $2\times 2$. We represent an arbitrary vector $\boldsymbol{x} \in \mathbb{R}^d$ as a family of $k$ vectors of dimension 2, that is, $\boldsymbol{x} = (x_1, \dots, x_k)$, $x_i \in \mathbb{R}^2$. Then the equation for an eigenvector $M\boldsymbol{x} = \lambda \boldsymbol{x}$ becomes the system of equations $Ax_1 = \lambda x_k$, $x_{i+1} = \lambda x_{i}$, $i = 1, \dots, k-1$. Therefore, $Ax_k = \lambda^kx_k$, and so $\lambda^k$ is an eigenvalue of $A$. Thus, $q(\lambda^k) = 0$, which yields $p(\lambda) = 0$. Thus, the set of roots of the polynomial $p$ (there are exactly $d$ roots, all of which are simple!) coincides with the set of eigenvalues of $M$. Therefore, $M$ has a characteristic polynomial $p$. Now we use Theorem 1 and conclude that it is enough to prove that the attractor generated by the matrix $M$ is the product of $k$ attractors of the same type (rectangles, dragons, or bears). Then it will remain to observe that a product of several rectangles is a parallelepiped.
Let $L_i$ denote the two-dimensional subspace corresponding to the $i$th block of the matrix (5), $i=1, \dots, k$. Each vector $\boldsymbol{x} \in \mathbb{R}^d$ is represented as a sum $\boldsymbol{x} = \sum_{i=1}^k x_i$, $x_i \in L_i$, which will be denoted by $(x_1, \dots, x_k)$. We denote by $(X_1,\dots, X_k) = \sum_{i=1}^k X_i$ the direct sum of the sets $X_i \subset L_i$, $i = 1, \dots, k$; it consists of vectors $(x_1, \dots, x_k)$, $x_i \in X_i$, $i = 1, \dots, k$. Assume that a matrix $A$ and digits $\{0,a\}$ generate an attractor $K$ on the plane. Let us show that the matrix $M$ and the digits $\{\boldsymbol{0}, \boldsymbol{a}\}$, where $\boldsymbol{a} = (0, \dots, 0, a)$ ($k$ two-dimensional blocks), generate the attractor $G = (K, \dots, K)$. Since $K$ is a rectangle, a dragon, or a bear, the proof will be complete. We have
$$
\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}
$$
Consequently, $M^{-1}G = (A^{-1}K, K, \dots, K)$ and
$$
\begin{equation*}
M^{-1}(G+\boldsymbol a)=M^{-1}G+M^{-1}\boldsymbol a=(A^{-1}(K+a), K, \dots, K).
\end{equation*}
\notag
$$
Since $A^{-1}K \sqcup A^{-1}(K+a)= K$, we see that $M^{-1}G \sqcup M^{-1}(G+\boldsymbol{a}) = G$. Therefore, $G$ is an attractor generated by the matrix $M$ and the digits $\{\boldsymbol{0}, \boldsymbol{a}\}$. Replacing $\boldsymbol{a}$ by any other digit we obtain an affinely similar attractor, which completes the proof of Theorem 4. Remark 2. Thus, in an even dimension there are only three types of isotropic 2-attractors. Formally, we have not proved yet that these types are not affinely similar. This will follow from the results in § 6, where we show that they are not only merely affinely nonsimilar but also not $C^1$-diffeomorphic. The proofs of Theorems 3 and 4 are constructive. They do not only classify all isotropic 2-attractors, but also give a method for constructing them. If we choose arbitrary bases in the two-dimensional subspaces $L_1, \dots, L_k$, then we obtain a set $(G_1, \dots, G_k)$, where the $G_i$ are arbitrary dragons independent of one another. For any dragons $G_1, \dots, G_k$ their direct product is a $d$-dimensional isotropic attractor. The same is true for the product of $k$ arbitrary bears. We stress that we multiply either $k$ dragons or $k$ bears: there can be no mixed products. Since the choice of the dragons (or bears) is arbitrary, the set of $d$-dimensional isotropic 2-attractors possesses some diversity. However, it is achieved by the choice of an arbitrary basis. In each even dimension there are only three isotropic 2-attractors up to affine similarity. This suggests that it is necessary to study anisotropic attractors as well. As for today, the literature on their applications to wavelets and approximation algorithms is not very extensive; we can mention [13] and [15]–[19]. § 6. The topology of 2-attractorsEven the basic topological properties of self-affine attractors are quite difficult to analyse. Many authors [35], [37], [2], [9], [32], [34], [23] have studied the problem of connectedness of attractors. In [35], [37] and [2] it was shown that all attractors in dimensions $d = 2, 3, 4$, with digit sets forming an arithmetic progression are connected. The boundaries of attractors and the structure of their neighbours were studied in [20], [6], [7], [57], [3] and [4]. In [34] it was shown that the plane 2-attractors (the dragon and the bear) are connected. Moreover, it was proved in [12] that they are both homeomorphic to a disc. Since this is obvious for a rectangle, we obtain that each plane 2-attractor is homeomorphic to a disc. Using our classification of isotropic 2-attractors (Theorems 3 and 4) and bearing in mind that the product of $k$ compact sets homeomorphic to a disc is homeomorphic to a $2k$-dimensional ball we obtain the following. Corollary 3. For each $d\geqslant 2$, all $d$-dimensional isotropic 2-attractors are homeomorphic to a ball. For anisotropic 2-attractors this statement may fail even in the three-dimensional space [7]. A general (quite complicated) algorithm to verify if an attractor is homeomorphic to a ball was presented in [20]. Attractors with arbitrarily many digits need not be homeomorphic to a ball: the corresponding examples in $\mathbb{R}^3$ can be found in [20] (Propositions 8.7 and 8.11; the boundary of an attractor is a torus). However, in the isotropic case the question of a stronger topological equivalence arises. In particular, are isotropic 2-attractors diffeomorphic or at least metrically equivalent, that is, homeomorphic by a bi-Lipschitz mapping? In this section we give a negative answer by showing that the three plane 2-attractors (the rectangle, the dragon and the bear) are not bi-Lipschitz equivalent. Hence they are not $C^1$-diffeomorphic. Then Theorem 4 implies that the isotropic 2-attractors in $\mathbb{R}^{2k}$ are not pairwise bi-Lipschitz equivalent (in $\mathbb{R}^{2k+1}$ there are only parallelepipeds, which are obviously pairwise diffeomorphic). Definition 2. Two compact sets $G_1, G_2 \subset \mathbb{R}^d$ are called metrically equivalent or bi-Lipschitz equivalent if they are homeomorphic by means of a bi-Lipschitz map $f\colon \mathbb{R}^d \to \mathbb{R}^d$. The bi-Lipschitz property means that there exists a constant $C > 0$ such that $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|$ for all $\boldsymbol{x}_1, \boldsymbol{x}_2 \in \mathbb{R}^d$. Note that the bi-Lipschitz property implies bijectivity. If two sets are $C^1$-diffeomorphic, then they are bi-Lipschitz equivalent, but not vice versa, since bi-Lipschitz maps can be nondifferentiable. On the other hand, by Rademacher’s theorem [55] a bi-Lipschitz map is almost everywhere differentiable. We establish the nonequivalence of attractors by using a characteristic invariant with respect to bi-Lipschitz maps. Such an invariant is the surface dimension $\sigma(G)$. This is a supremum of numbers $r \geqslant 0$ such that $|G_{\varepsilon}|-|G|\leqslant C_{r}\varepsilon^{r}$ for all $\varepsilon > 0$, where $C_{r}$ does not depend on $\varepsilon$. Note that the surface dimension is different from the Hausdorff or box dimension. These latter do not distinguish sets of positive Lebesgue measure, while the surface dimension does. It measures the regularity of the boundary. However, it is different from the Hausdorff and box dimension of the boundary either. See [54] on the properties and computation of the surface dimension of attractors. Proof. Clearly, $|G_{\varepsilon}| - |G|= |G_{\varepsilon}\setminus G|$. Furthermore, $f(G)_{\varepsilon}\setminus f(G) \subset f(G_{C\varepsilon}\setminus G)$. The map $f$ increases the Lebesgue measure at most with coefficient $C^d$. Indeed, the Lebesgue measure is equal to the Hausdorff measure [50], and for the Hausdorff measure this property is obvious. Therefore, $|f(G_{C\varepsilon}\setminus G)| \leqslant C^d|G_{C\varepsilon}\setminus G|$. If ${\sigma(G) > r}$, then $|G_{C\varepsilon}\setminus G| \geqslant C_r |C\varepsilon|^{r}$. Thus, $|f(G)_{\varepsilon}\setminus f(G)| \leqslant C_r |C\varepsilon|^{r} \leqslant C_rC^{r+d} \varepsilon^r$. Since this is true for all $\varepsilon >0$, we have $\sigma(f(G)) > r$. Thus, the inequality $\sigma(G) > r$ yields $\sigma(f(G)) > r$. Hence $\sigma(f(G)) \geqslant \sigma(G)$. We have shown that a bi-Lipschitz map does not reduce the surface dimension. Applying this property to the inverse map we obtain $\sigma(f(G)) = f(G)$. The lemma is proved. Lemma 3 makes it possible to prove the nonequivalence of sets by a mere comparison of their surface dimensions. It was shown in [54] that the surface dimension of an isotropic attractor is equal to the Hölder exponent of its characteristic function in the space $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}
$$
where $\varphi = \chi_{G}$. The Hölder exponent of a parallelepiped, as well as that of any polyhedron, is equal to $1/2$. The Hölder exponents of a dragon and a bear were computed in [61] using methods from [18]. We arrive at the following result. Theorem 5. For every even $d$, all the three types of isotropic 2-attractors are homeomorphic but not bi-Lipschitz equivalent. Since for odd $d$ all isotropic 2-attractors are parallelepipeds, they are, of course, diffeomorphic. Hence Theorem 5 applies to even dimensions only. In the proof we need an auxiliary fact established in [54]. For a subspace $V \subset \mathbb{R}^d$, the $L_2$-Hölder exponent of $\varphi$ along $V$ is the quantity
$$
\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
$$
(all shifts are along the subspace $V$). Lemma A (see [18]). If $\varphi \in L_2(\mathbb{R}^d)$ is an arbitrary function and the space $\mathbb{R}^d$ is represented as the direct sum of subspaces $V_1, \dots, V_k$, then $\alpha(\varphi)\!=\!\min_{j=1, \dots, k}\alpha_{V_j}(\varphi)$. Proof of Theorem 5. For $d=2$, the Hölder exponents of the two-dimensional 2-attractors were computed in [61]. For the dragon this exponent is $0.2382\dots$ and for the bear it is $0.3446\dots$ (for the square, it is, of course, $0.5$). Since these exponents are equal to the corresponding surface dimensions, Lemma 3 implies that the sets in question are not bi-Lipschitz equivalent. For $d=2k$ each isotropic 2-attractor is equal to a direct product of either $k$ dragons or $k$ bears, or it is a parallelepiped. In the latter case $\alpha(G)=0.5$. In the case of dragons we denote the two-dimensional planes containing these dragons by $V_1, \dots, V_k$. Then for every $j$ $\alpha_{V_j}(G)$ is equal to the regularity of a dragon. By Lemma A, $\alpha_{V_j}(G)$ is $0.2382\dots$ . Similarly, the regularity of the direct product of $k$ bears is equal to the regularity of one bear, which is $0.3446\dots$ . Now, referring to Lemma 3 again we infer the nonequivalence of the sets under consideration. The theorem is proved. As for the non-isotropic 2-attractors, we can only formulate the following conjecture. § 7. Convex hulls of 2-attractorsPolyhedral attractors have been studied in the literature [31], [20], [62]. Apart from a theoretical interest, they are attractive for applications because they generate wavelets and subdivision schemes of simple structure. In [62] it was proved that any polygonal (but not necessarily convex) attractor in $\mathbb{R}^2$ is a parallelogram. A conjecture was made that this is true in any dimension: all polyhedral attractors are parallelepipeds. We are going to prove this conjecture for $2$-attractors. Actually, we establish a stronger fact and find all $2$-attractors whose convex hull is a polytope. We prove that a convex hull of an arbitrary $2$-attractor is an infinite zonotope, which is, in turn, a polytope precisely in two cases, of parallelepipeds and of products of dragons. Recall that a zonotope in $\mathbb{R}^d$ is the Minkowski sum of a finite number of line segments. Every zonotope is convex and is a projection of the $N$-dimensional cube onto the space $\mathbb{R}^d$, where $N$ is the number of segments. In particular, a zonotope always has a centre of symmetry. A zonoid is the limit of a sequence of zonotopes in the Hausdorff metric. We need a generalization of the notion of zonotope to an infinite number of line segments. Definition 3. An infinite zonotope in $\mathbb{R}^d$ is a Minkowski sum of a countable set of line segments whose sum of lengths is finite. An infinite zonotope is nondegenerate if it does not lie in a proper subspace. Every infinite zonotope is a zonoid but not vice versa. A nondegenerate infinite zonotope is a centrally symmetric convex body. Proposition 2. The convex hull of a 2-attractor generated by a matrix $M$ and digits $\{\boldsymbol{0}, \boldsymbol{a}\}$ is the nondegenerate infinite zonotope $\overline G= \sum_{k=1}^{\infty} M^{-k}\overline{\boldsymbol{a}}$, where $\overline{\boldsymbol{a}}$ is the line segment $[\boldsymbol{0}, \boldsymbol{a}]$. Proof. Since $\rho(M^{-1})< 1$, it follows that the sum of the lengths of the segments $M^{-k}\overline{\boldsymbol{a}}$ is finite. Hence $\overline G$ is a nondegenerate infinite zonotope. Clearly, $G \subset \overline G$, because $\{\boldsymbol{0}, \boldsymbol{a}\} \subset\overline{\boldsymbol{a}}$. Let us prove the opposite inclusion. Every point $\boldsymbol{x} \in \overline G$ is represented as a sum $\sum_{k=1}^{\infty} M^{-k} \boldsymbol{x}_k$, where each point $\boldsymbol{x}_k$ belongs to the line segment $M^{-k} \overline{\boldsymbol{a}}$. If for at least one $j$ the point $\boldsymbol{x}_j$ does not coincide with the endpoint of $M^{-j} \overline{\boldsymbol{a}}$, then it is the half-sum of some points $\boldsymbol{x}_j', \boldsymbol{x}_j'' \in M^{-j}\overline{\boldsymbol{a}}$. Therefore, $\boldsymbol{x}$ is the half-sum of the points $\boldsymbol{x}_j' + \sum_{k\ne j}^{\infty} M^{-k} \boldsymbol{x}_k$ and $\boldsymbol{x}_j'' + \sum_{k\ne j}^{\infty} M^{-k} \boldsymbol{x}_k$. Hence all extreme points of $\overline G$ are among points of the sum $\sum_{k=1}^{\infty} M^{-k} \{\boldsymbol{0}, \boldsymbol{a}\}$, that is, among points of $G$. By the Krein-Milman theorem every convex compact set is the closure of the convex hull of its extreme points. Then $\overline G$, as a closure of the convex hull of a subset of extreme points of the compact set $G$, is contained in $G$. The proposition is proved. As the first corollary we obtain the following curious fact on dragons. It is most likely known but we could not find a reference and therefore present its proof. Proof. The matrix $M$ of a dragon defines a rotation through $\pi/4$ with multiplication by $\sqrt{2}$. Hence all the line segments $M^{-k}\overline{\boldsymbol{e}}$ lie on four straight lines, which are the coordinate axes and the bisectors of the coordinate sectors. All segments lying on the same line make up one segment. So the sum $\sum_{k=1}^{\infty}M^{-k}\overline{\boldsymbol{e}}$ is a sum of four segments, which is an octagon. The proposition is proved. It turns out that among all 2-attractors, not necessarily isotropic, only the parallelepiped and the dragon, or a direct product of dragons, have simple convex hulls. A direct product of $k$ dragons (one of the three isotropic 2-attractors in $\mathbb{R}^{2k}$ by Theorem 4) is a polytope with $8^k$ vertices. All other 2-attractors have convex hulls which are not polytopes. Theorem 6. Among all 2-attractors in $\mathbb{R}^d$ there are precisely two types that have convex hulls which are polytopes, namely, a parallelepiped ($2^d$ vertices) and a direct product of $d/2$ dragons ($2^{3d/2}$ vertices). Every 2-attractor distinct from a parallelepiped and a product of dragons has a convex hull that is an infinite zonotope which has infinitely many extreme points. In the proof we need the following technical lemma. Lemma 4. If the set of line segments generating an infinite zonotope in $\mathbb{R}^d$ contains infinitely many nonparallel segments, then that zonotope is not a polytope. Proof. First we prove the statement in $\mathbb{R}^2$. Taking sums of all parallel segments in advance we can assume that all segments in the sequence $\{\overline{\boldsymbol{a}}_k\}_{k=1}^{\infty}$ have different directions. We choose an arbitrary index $j$ and consider the sequence of zonotopes $\overline G_s = \sum_{k=1}^{s} \overline{\boldsymbol{a}}_k$ for $s=j, j+1,\dots$ . Each of them is a $2s$-gon one side of which is parallel and equal to the segment $\overline{\boldsymbol{a}}_j$. Since $\overline G_s$ converges to an infinite zonotope $\overline G$ in the Hausdorff metric, the limit zonotope contains a boundary segment parallel to $\overline{\boldsymbol{a}}_j$ and of length at least $|\overline{\boldsymbol{a}}_j|$. Hence the boundary of $\overline G$ contains segments parallel to all the $\overline{\boldsymbol{a}}_j$, $j\in \mathbb{N}$. Therefore, $\overline G$ is not a polygon, which completes the proof in $\mathbb{R}^2$. To prove the theorem in $\mathbb{R}^d$ it suffices to project all the initial vectors onto some two-dimensional plane so that infinitely many nonparallel vectors remain after this projection. By what we proved above, the projection of $\overline G$ onto this plane is not a polygon, hence $\overline G$ is not a polytope. The lemma is proved. Proof of Theorem 6. First we show that a convex hull of the bear is not a polygon. In fact, in suitable coordinates the matrix of the bear defines a rotation through an angle of $\arctan\sqrt{7}$ with a dilation with coefficient $\sqrt{2}$. Since the angle is irrational, the set $M^{-k}\overline{\boldsymbol{e}}$, $k\in \mathbb{N}$, does not contain parallel segments. It remains to refer to Lemma 4. This completes the proof for $\mathbb{R}^2$. Consider now an arbitrary $\mathbb{R}^d$, $d\geqslant 3$. If the attractor $G$ is isotropic, then it is either a parallelepiped, a product of dragons, or a product of bears. The first two cases are mentioned in the statement of the theorem. In the last case the convex hull of the attractor is not a polytope, since the convex hull of the bear is not a polygon.
It remains to consider the case when the attractor $G$ is not isotropic. Let $V$ denote the linear span in $\mathbb{R}^d$ of the eigenvectors corresponding to the eigenvalues of $M^{-1}$ largest in modulus (recall that there are no multiple eigenvalues). If some eigenvalue is not real, we take the real and imaginary parts of the corresponding eigenvector. The vector $\boldsymbol{e}$ does not belong to $V$ because it does not belong to an invariant subspace of $M$. Hence the sequence $\{M^{-k}\boldsymbol{e}\}_{k=1}^{\infty}$ approaches $V$ as $k\to \infty$ but does not reach it since $M^{-1}$ is nonsingular. Therefore, the sequence of line segments $\{M^{-k}\overline{\boldsymbol{e}}\}_{k=1}^{\infty}$ contains infinitely many nonparallel segments. Now using Lemma 4 we complete the proof. The theorem is proved. Thus, according to Theorem 6 only parallelepipeds and products of dragons have simple convex hulls. Remark 3. It is interesting that the bear is a more regular attractor than the dragon: the regularity exponent of the bear in $L_2$ is $0.3446\dots$ while for the dragon it is $0.2382\dots$ . Nevertheless, the convex hull of the bear is an infinite zonotope while that of the dragon is an octagon. Now we are able to classify all simple 2-attractors and prove the conjecture in [62] in the case of 2-attractors. A polyhedral set is a union of a finite number of polyhedra. Proof. By Theorem 6, if a 2-attractor is a polyhedral set, then this is either a parallelepiped or a product of dragons. The dragon, however, is not a polyhedral set since its Hölder exponent in $L_2$ is strictly less than $0.5$. In the proof of Theorem 6 we have shown that the convex hull of a nonisotropic 2-attractor is never a polytope. This immediately implies the following. § 8. Tiles, Haar bases, and MRAThe Lebesgue measure of a self-affine attractor is a natural number. If this measure is equal to $1$, then the attractor is called a tile. The integer shifts of a tile cover the space $\mathbb{R}^d$ and have intersections of zero measure. The characteristic function $\varphi$ of a tile has orthonormal integer shifts. Among all attractors, tiles are most important in applications. In this case the function $\varphi$ generates an MRA and a system of wavelets. For 2-attractors (in this case, 2-tiles) $G(M, D)$, where $D=\{\boldsymbol{0}, \boldsymbol{a}\}$, the Haar basis is generated by $M$-contractions and integer shifts of one function: $\psi(\boldsymbol{x}) = \varphi(M\boldsymbol{x}) - \varphi(M\boldsymbol{x} - \boldsymbol{a})$. Wavelet systems are also generated by tiles in the frequency domain [24], [10], [11], [49], [48]. In approximation theory the case of tiles is also especially important since in this case the subdivision scheme converges in $L_p$. If an attractor is not a tile, then integer shifts of $\varphi$ are linearly dependent, and therefore $\varphi$ does not generate an MRA and the corresponding subdivision scheme can diverge [14], [39]. There are several criteria to verify that an attractor generated by a matrix $M$ and digits $D$ is a tile [44], [32]. This depends not only on the matrix but also on the digits. For example, if a matrix $M$ and digits $D=\{\boldsymbol{0}, \boldsymbol{a}\}$ generate a 2-tile $G(M,D)$, then the 2-attractor $G(M, D')$ generated by the same matrix and the digits $D'=\{0, 3\boldsymbol{a}\}$ is not a tile since it has Lebesgue measure $3^d|G(M,D)| \geqslant 3^d$. In dimensions $d=2, 3$, for every expanding integer matrix $M$ there exists a digit set $D$ for which $G(M, D)$ is a tile. However, even for $\mathbb{R}^4$ Potiopa presented in 1997 an example of a matrix $M$ for which such a digit set does not exist, so that this matrix does not generate a tile [43], [45]. In the case of two digits, the type of a 2-attractor depends neither on digits nor on the matrix $M$ but only on the characteristic polynomial of $M$. That is why it is natural to formulate the problem in a different way. Since a 2-attractor is determined by an expanding polynomial up to affine similarity, the problem can be formulated in a different way: can every expanding polynomial with $a_d = 1$ and $|a_0| = 2$ generate a tile? We conjecture that the answer is in the affirmative and, moreover, it is attained for the companion matrix (3) of the polynomial in question and for the digits $D=\{\boldsymbol{0}, \boldsymbol{e}\}$, where $\boldsymbol{e} = \boldsymbol{e}_1$ is the first basis vector. Conjecture 2. For an arbitrary expanding polynomial with leading coefficient $1$ and free term $\pm 2$ its companion matrix $M$ and the digits $D=\{\boldsymbol{0}, \boldsymbol{e}\}$ generate a tile. We observe immediately that this conjecture is true in two cases at least. The first is the case of small dimension. Proposition 4. Conjecture 2 is true for dimensions $d=2,3$. Proof. In dimension $d=2$ there are three polynomials generating 2-attractors (§ 2) up to equivalence; in dimension $d=3$ there are seven such polynomials (§ 11). Applying the software program checktile [46], which realizes the criterion from [32], to each of them we complete the proof. The second case is more important. Conjecture 2 is true for isotropic 2-attractors in all dimensions. Theorem 7. Conjecture 2 is true for isotropic polynomials. Proof. In an odd dimension every 2-attractor is a parallelepiped, which corresponds to the polynomial $p(z) = z^d \pm 2$ (Theorem 3). Then one verifies directly that the characteristic function of a cube $[0,1]^d$ satisfies the refinement equation $\varphi(\boldsymbol{x}) = \varphi(M\boldsymbol{x}) + \varphi(M\boldsymbol{x} - \boldsymbol{e})$, where $M$ is the companion matrix of the polynomial ${z^d - 2}$. Hence for this polynomial the 2-attractor is a tile $[0,1]^d$. For the polynomial ${z^d - 2}$ the same refinement equation has another solution, the characteristic function of the cube $[-1/3, 2/3] \times [0, 1]^{d-1}$. This cube is obviously a tile too.
In even dimension $d=2k$ Lemma 2 yields $p(z)= q(z^k)$, where $q(t) = {t^{2} + at \pm 2}$ is an isotropic quadratic polynomial. The permutation of the coordinates ${x_i \to x_{\sigma(i)}}$ by the formula $\sigma(i) = 2(k-i+1)$, $\sigma(i+k) = 2(k-i)+1$, ${i = 1, \dots, k}$, maps the companion matrix of the polynomial $p$ to the matrix $M$ defined by formula (5). Hence, if $M$ generates a tile, then the companion matrix also does. By Theorem 4 the matrix $M$ generates a 2-attractor, which is a direct product of equal two-dimensional attractors: dragons, bears, or rectangles. Since each of these two-dimensional attractors is a tile, their direct product is too. The theorem is proved. Remark 4. Theorem 7 guarantees the existence of a 2-tile affinely similar to an arbitrary isotropic 2-attractor. In Potiopa’s example [45] the matrix $M$ is also isotropic, and it does not generate a tile, that is, there is no suitable digit set $D$ such that $G(M,D)$ is a tile. However, Theorem 7 claims that for the companion matrix of the same characteristic polynomial $p(z) = z^4 + z^2 + 2$ such a digit set exists: this is $D= \{\boldsymbol{0}, \boldsymbol{e}\}$. We obtain a 2-tile $G(M,D)$. By Theorem 4 this tile is a product of two dragons. Thus, in Potiopa’s example it is only sufficient to go over to another integer basis in $\mathbb{R}^d$ to obtain a 2-tile. Remark 5. Despite the fact that an isotropic 2-tile is a direct product of identical bivariate tiles, it generates a Haar system which is distinct from a direct product of bivariate Haar functions. In fact, if $\varphi$ is a product of, say, $k$ dragons: $\varphi = \varphi_1 \otimes \dots \otimes \varphi_k$, where each function $\varphi_i$ is a characteristic function of a dragon in $\mathbb{R}^2$, then the Haar function in $\mathbb{R}^d$ is $\varphi(M\boldsymbol{x}) - \varphi(M\boldsymbol{x} - \boldsymbol{e})$: it is distinct from a direct product of $k$ bivariate Haar functions. Note also that the classification of isotropic 2-attractors in § 5 enables us to find the regularity exponents of the corresponding Haar functions. For odd $d$ there are only parallelepipeds; their Hölder exponent in $L_2(\mathbb{R}^d)$ is $0.5$. For even $d$ the list is supplemented by products of dragons and products of bears. Their regularity in $L_2(\mathbb{R}^2)$ is equal to the regularity of dragons and bears, respectively, which is $0.2382\dots$ and $0.3446\dots$, respectively [61]. § 9. Can one attractor correspond to different matrices?How many different 2-attractors up to affine similarity are there in $\mathbb{R}^d$? In the isotropic case there are either one or three types depending on the evenness of $d$. For nonisotropic matrices there are much more types, and their total number grows with dimension. In the next section we estimate this number. However, before we address this issue we have to answer one important question: is there a one-to-one correspondence between 2-attractors and the spectra of expanding matrices with determinant $\pm 2$? In § 3 this correspondence was established in one direction: by Theorem 1 each 2-attractor is uniquely determined by the spectrum of its matrix $M$, that is, by a polynomial with leading coefficient $1$ and free term $\pm 2$. Hence we can estimate the number of such polynomials of degree $d$. Each of them generates a unique attractor up to affine similarity. However, is the converse true? Is it true that each attractor is associated with a unique polynomial, that is, a unique matrix $M$ up to similarity? Is it possible that we find many appropriate polynomials, but all of them define the same type of attractors, for instance, parallelepipeds? This problem turns out to be nontrivial. First we show, which is simple, that two opposite matrices $M$ and $-M$ define the same 2-attractor. Then, which is more difficult, that different and nonopposite matrices define different (not affinely similar) attractors. We need the following known fact (see [35], Proposition 2.2). Proof. Let $D = \{\boldsymbol{0}, \boldsymbol{e}\}$. Set $\boldsymbol{c} = \frac12 \sum_{j=1}^{\infty} M^{-j} \boldsymbol{e}$. Then $G = \boldsymbol{c} + \sum_{j=1}^{\infty} \pm \frac12 M^{-j} \boldsymbol{e}$. The set $\sum_{j=1}^{\infty} \pm \frac12 M^{-j} \boldsymbol{e}$ is symmetric about the origin, hence $G$ is symmetric about the point $\boldsymbol{c}$. The proposition is proved. Definition 4. Algebraic polynomials $p = \sum_{k=0}^{d} p_k t^k$ and $q = \sum_{k=0}^{d} q_k t^k$ are called opposite is $q_k=(-1)^{d-k}p_k$, $k=0,\dots,d$. The leading coefficients of opposite polynomials are equal. Vieta’s formulae imply that the roots of the polynomial $q$ are roots of the polynomial $p$ taken with the opposite sign. Thus, the roots of $p$ and $q$ are opposite, which justifies our terminology. The matrices $M$ and $-M$ have opposite characteristic polynomials. Proof. The characteristic function $\varphi$ of an attractor $G$ satisfies the refinement equation $\varphi(\boldsymbol{x}) = \varphi(M\boldsymbol{x})+ \varphi(M\boldsymbol{x} -\boldsymbol{e})$. Since $G = 2\boldsymbol{c}-G$, it follows that $\varphi (2\boldsymbol{c}- \boldsymbol{x})= \varphi(\boldsymbol{x})$. Then $\varphi(\boldsymbol{x}) = \varphi(2M\boldsymbol{c} - M\boldsymbol{x}) + \varphi(2M\boldsymbol{c} - \boldsymbol{e} - M\boldsymbol{x})$. Therefore, the set $G$ is also an attractor with matrix $-M$ and digits $-2M\boldsymbol{c}$ and $\boldsymbol{e} - 2M\boldsymbol{c}$. The proposition is proved. It turns out that the converse is also true: if two polynomials generate identical 2-attractors, then they are either equal or opposite. This means that a 2-attractor defines the dilation matrix $M$ up to a sign and similarity. Theorem 8. If matrices $M_1$ and $M_2$ (with some sets of digits $D_1$ and $D_2$, respectively) generate the same 2-attractor up to affine similarity, then either $M_1 = M_2$ or $M_1 = - M_2$. The proof is based on the following lemma. For a matrix $M$ and a line segment $\overline{\boldsymbol{a}} = [- \boldsymbol{a}, \boldsymbol{a} ]\subset \mathbb{R}^d$, $\boldsymbol{a} \ne 0$, consider the set of segments $\mathcal T(M, \overline{\boldsymbol a})=\{ M^{-k}\overline{\boldsymbol a},\,k \in \mathbb N\}$, where coinciding segments are counted with multiplicity. Lemma 5 (the recovery of a dynamical system). Given two expanding $d\times d$ matrices $M_1$ and $M_2$ without multiple eigenvalues, if for some line segments $\overline{\boldsymbol{a}}_1$ and $\overline{\boldsymbol{a}}_2$ (where $\overline{\boldsymbol{a}}_i$ is not contained in an invariant subspace of $M_i$, $i = 1,2$) the equality $\mathcal{T}(M_1,\overline{\boldsymbol{a}}_1) = \mathcal{T}(M_2,\overline{\boldsymbol{a}}_2)$ holds, then either $M_1=M_2$ or ${M_1=-M_2}$. See § 13 for the proof. In fact, Lemma 5 guarantees that a linear dynamical system can be recovered from its trajectory even if the history is unknown, that is, the order of points is unknown. If we know the history, then the system can be identified by any $d+1$ successive points in the trajectory. The problem of the identification of a system with an unknown history is significantly more difficult. Now we are able to prove Theorem 8. To this end we use a known result from the theory of refinement equations and represent the Fourier transform $\widehat \varphi$ of the characteristic functions of an attractor $G$ as an infinite product of trigonometric polynomials. In this way we find the set of zeros of $\widehat \varphi$. This is a union of countably many hyperplanes in $\mathbb{R}^d$. To avoid dealing with hyperplanes we pass to their polars. The polar is taken with respect to the unit Euclidean sphere with centre $0$. The polar of a hyperplane is one point. Applying Lemma 5 we show that the set of zeros obtained determines the matrix $M$ in a unique way. Therefore, the attractor $G$ determines $M$ uniquely (up to $\pm$). Proof of Theorem 8. Assume that a 2-attractor $G$ is generated by a matrix $M$ and digits $\{\boldsymbol{0}, \boldsymbol{e}\}$; then its characteristic function satisfies the refinement equation $\varphi(\boldsymbol{x}) = \varphi(M\boldsymbol{x}) + \varphi(M\boldsymbol{x} -\boldsymbol{e})$ (see § 1, equation (2)). The solution of the refinement equation is expressed by the formula
$$
\begin{equation}
\widehat \varphi (\xi)= \widehat \varphi (0)\prod_{k=1}^{\infty} \boldsymbol m \bigl([M^{*}]^{-k}\boldsymbol \xi\bigr),
\end{equation}
\tag{8}
$$
where the trigonometric polynomial $\boldsymbol m(\boldsymbol \xi)=(1+e^{-2\pi i(\boldsymbol e, \boldsymbol \xi)})/2$ is called the mask of the equation (see, for example, [51]). If we show that the set of zeros of $\widehat\varphi(\boldsymbol{\xi})$ determines the matrix $M$ uniquely up to a sign, then everything is proved. Indeed, the function $\widehat\varphi$ is uniquely determined by the set $G$, and therefore the set of zeros of this function is also determined by $G$. Hence the matrix $M$ is also determined by the set $G$ up to a sign. Since $(\boldsymbol{e}, \boldsymbol{\xi}) = \xi_1$ (the first component of the vector $\boldsymbol{\xi}$), we see that the set of solutions of the equation $\boldsymbol{m}(\boldsymbol{\xi})= 0$ is the union of countably many parallel hyperplanes $\xi_1=1/2+n$, $n \in \mathbb{Z}$. The polars of these hyperplanes form a countable set of points $\mathcal R=\{2/(1+2n)\boldsymbol e_1\}_{n \in \mathbb Z}$, where $\boldsymbol{e}_1 = (1,0, \dots, 0)^T$ is the first basis vector. The set of zeros of the function $\boldsymbol m ([M^{*}]^{-k}\boldsymbol \xi)$ is the image of the set of zeros of the function $\boldsymbol m (\boldsymbol \xi)$ under the action of the operator $[M^*]^k$. Hence the polar of the set of zeros of $\boldsymbol{m}([M^{*}]^{-k}\boldsymbol{\xi})$ is $M^{-k}\mathcal{R}$. The set of zeros of the product (8) is the union of the sets of zeros of the functions $\boldsymbol{m}([M^{*}]^{-k}\boldsymbol{\xi})$ over all $k \in \mathbb{N}$ (all zeros are counted with multiplicities). Consequently, the set of zeros of $\widehat \varphi (\boldsymbol{\xi})$ is uniquely determined by $\bigcup_{k \in \mathbb{N}} M^{-k}\mathcal{R}$ (all points are taken with multiplicities). Every set $M^{-k}\mathcal{R}$ lies on the line segment $[-M^{-k}\boldsymbol{a}, M^{-k}\boldsymbol{a}]$, where $\boldsymbol{a} = 2\boldsymbol{e}_1$ is a point of the set $\mathcal{R}$ which is most distant from the origin; hence $M^{-k}\boldsymbol{a}$ is a point of $M^{-k}\mathcal{R}$ which is most distant from the origin. Let $\overline{\boldsymbol{a}} = [-\boldsymbol{a}, \boldsymbol{a}]$. We see that each set $\bigcup_{k \in \mathbb{N}} M^{-k}\mathcal{R}$ is uniquely determined by the set of segments $\bigcup_{k \in \mathbb{N}} M^{-k}\overline{\boldsymbol{a}} = \mathcal{T}(M, \overline{\boldsymbol{a}})$. Thus, the set of zeros of $\widehat \varphi $ determines the set of segments $\mathcal{T}(M,\overline{\boldsymbol{a}})$ in a unique way. If we show that this set of segments determines the matrix $M$ up to a sign, then everything is proved. If we assume the converse, that is, that there exist integer matrices $M_1$ and $M_2$ with determinants $\pm 2$ and there exist line segments $\overline{\boldsymbol{a}}_1$ and $\overline{\boldsymbol{a}}_2$ such that $\mathcal{T}(M_1, \overline{\boldsymbol{a}}_1) = \mathcal{T}(M_2, \overline{\boldsymbol{a}}_2)$, then by Lemma 5 we have either $M_1=\pm M_2$, as required, or one of these matrices has a multiple eigenvalue. The latter is impossible by Proposition 2.5 in [35]. The theorem is proved. Corollary 6. Two polynomials generate affinely similar 2-attractors if and only if they are either equal or opposite. In odd dimensions a polynomial with nonzero free coefficient cannot be opposite to itself and every polynomial with free coefficient $2$ is opposite to a polynomial which has the free coefficient $-2$, and vice versa. Thus, in odd dimensions the number of different (not affinely similar) 2-attractors is equal to the number of expanding integer polynomials with leading coefficient $1$ and free coefficient $2$. In even dimensions opposite polynomials have the same free coefficient. Polynomials opposite to themselves are precisely those having zero coefficients at all odd powers. They depend only on $x^2$ and the change $x_1= x^2$ respects the expanding property. Therefore, the total number of expanding polynomials opposite to themselves is equal to the number of expanding polynomials of half the degree with leading coefficient $1$ and free coefficient $\pm 2$. Thus, the number of different (not affinely similar) 2-attractors in $\mathbb{R}^{2d}$ is equal to half the sum of their number for expanding polynomials of degree $2d$ with leading coefficient $1$ and free coefficient $\pm 2$ and their number for similar polynomials of degree $d$. § 10. The number of 2-attractors in $ {\mathbb{R}}^d$In every dimension $d$ there are finitely many 2-attractors up to affine similarity [29]. In $\mathbb{R}^2$ there are exactly three 2-attractors; all of them are isotropic. In $\mathbb{R}^3$ there are exactly seven attractors (only one among them is isotropic, namely, a parallelepiped); see § 11 for more on the three-dimensional case. Numerical results in Table 1 show a lower bound for the number of 2-attractors in dimensions $d \leqslant 8$. Most likely, these estimates are quite sharp although we cannot prove this. Figure 3 presents the graph of the binary logarithm of this estimate for the number of 2-attractors in dimension $d$. We see that the graph is close to a linear function. Therefore, the lower bound for these $d$ is close to $2^d$. For higher dimensions $d$ we know only an approximate answer, as we have obtained lower and upper bounds quite distant from each other. Table 1.The lower bound for the number of 2-attractors
By Corollary 6 (§ 9) the question of the number of 2-attractors is reduced to the following problem on integer polynomials. Problem 2. How many expanding integer polynomials of degree $d$ with leading coefficient $1$ and free term $\pm 2$ do there exist? It was shown in [34] that the number of such polynomials grows at least linearly in $d$. On the other hand, this number is finite for every $d$. We are going to obtain the following estimates: a lower bound is $d^2/16+O(d)$, and an upper bound is $2^{ d+\varepsilon}$. Before giving a proof we observe that the asymptotic distribution of the number of expanding integer polynomials with a large free coefficient has been considered in the literature [1], [5], [41]. Polynomials with similar properties also appeared in [28]. In [58] a simplified Schur-Cohn criterion of the expanding property for integer polynomials was obtained. We start with a proof of the lower bound $d^2/16+O(d)$. We call a vector of natural numbers $(n_1, n_2, n_3)$ bad if it is proportional to a vector $(3x+s, 3y+s, 3z+s)$, where $s \in \{1, 2\}$ and $x,y,z \in \mathbb{Z}$. The corresponding partition of the integer $d=n_1+n_2+n_3$ into a sum of natural terms is said to be bad and all other partitions are said to be good. Partitions different only in the order of terms are identified. By $b_{+}(d)$ we denote the number of good partitions of the integer $d$. Theorem 9. Every polynomial of the form $P(z) = (1+z^m)(1+z^q)(1+z^k)+1$ is an expanding integer polynomial with leading coefficient $1$ and free term $2$, provided that $(m, q, k)$ is a good partition of $d = m + q + k$. If $d$ is not divisible by $3$, then the number of such polynomials $b_{+}(d)$ is equal to $d(d-1)/12+\omega_d$, where $\omega_d \in[-2/3,1/2]$. If $d$ is divisible by $3$, then it satisfies the equality Note that the principal terms of the upper bound and of the lower bound for $b_{+}(d)$ are quite close: $1/16=0.0625$ and $7/108 \approx 0.0648$. The proof of Theorem 9 is deferred to § 12. To derive the upper bound $2^{ d+\varepsilon}$ we apply a result due to Dubickas and Konyagin on the number of polynomials whose Mahler measure does not exceed a number $T$. The Mahler measure of an algebraic polynomial $p(t)= a_dt^d+\dots+a_1t+a_0$ is the quantity $\mu(p) = |a_d|\prod_{i=1}^d \max\{1,|\lambda_i|\}$, where $\lambda_1,\dots,\lambda_d$ are the roots of $p$ taken with multiplicities. The following theorem from [22] is cited in a slightly simplified form. We denote by $\theta = 1.32471\dots$ a root of the polynomial $x^3-x-1$. Theorem B (see [22]). If $T \geqslant \theta$, then the number of all integer polynomials with leading coefficient $1$ and Mahler measure at most $T$ does not exceed $T^{d (1+16 \ln \ln d/\ln d)}$. Now we are ready to formulate the main theorem in this section. Theorem 10. The total number $N(d)$ of not affinely similar 2-attractors in dimension $d$ satisfies the estimates ${d^2}/{16} - {43d}/{36}-5/6\leqslant N(d)\leqslant2^{d(1+{16 \ln \ln d}/{\ln d})}$. Proof. The lower bound follows from Theorem 9, which estimates the number of pairwise not opposite polynomials of the form $P(z) = (1 + z^m)(1 + z^q)(1 + z^k) + 1$. By Theorem 8, all of them define not affinely similar 2-attractors.
To establish the upper bound we observe that the Mahler measure of an expanding polynomial with coefficients $a_d = 1$ and $a_0 = \pm 2$ is $\prod_{i=1}^d |\lambda_i| = |a_0|= 2$. Hence $N(d)$ does not exceed the number of integer polynomials satisfying $\mu(p) \leqslant 2$. Applying Theorem B to $T=2$ we complete the proof. The large difference between the lower and upper bounds in Theorem 10 rises the question of the asymptotic behaviour of the value $N(d)$ as $d\to \infty$. At the first glance, $N(d)$ has to be significantly smaller than the number of polynomials with Mahler measure $\mu(p)\leqslant 2$. First, because in $N(d)$ we count only polynomials with leading coefficient $1$. Second, because roots with modulus smaller than $1$ are prohibited. Nevertheless, the numerical results in Table 1 suggest the opposite: for $d\leqslant 8$ the ratio $N(d)/2^d$ approaches $1$ as $d$ grows. Observe also that lower bounds for the number of polynomials with prescribed Mahler measure are often significantly smaller that upper bounds since examples of such polynomials ‘breed poorly’; see [25]. § 11. 2-attractors in $ {\mathbb{R}}^3$In the three-dimensional space there exist precisely seven types of non-affinely similar 2-attractors. They were constructed first in [9]. These 2-attractors have distinct characteristic polynomials which are not opposite to one another. Hence, by Corollary 6 they are not affinely similar. Their topological properties: homeomorphism to a ball, the structure of neighbours and so on were studied in [7]. In particular, the combinatorial structure of tilings of $\mathbb{R}^3$ by integer shifts of these attractors was also established in that work. In this section we compute the Hölder exponents of three-dimensional attractors and see that all of them are distinct. This explains not just their affine nonequivalence but also different approximation properties of the corresponding Haar wavelets. We will see that even drawing pictures of attractors depends significantly on their smoothness. Recall that every polynomial $\ p(z) = z^3 + a_{2}z^2 + a_1z + a_0$ is associated with its companion matrix
$$
\begin{equation*}
M=\begin{pmatrix} 0 & 0 & -a_0 \\ 1 & 0 & -a_{1} \\ 0 & 1 & -a_{2} \end{pmatrix}
\end{equation*}
\notag
$$
with characteristic polynomial $p$. For each of the seven polynomials written in Table 2 we build an attractor for the companion matrix and the digits $(0, 0, 0)^T$ and $(1, 0, 0)^T$. The Hölder exponent $\alpha (G)$ of a set $G$ is the Hölder exponent in $L_2$ of its characteristic function $\chi_G$ (see the definition (7)). Table 2.The regularity of three-dimensional 2-attractors
The Hölder exponent is evaluated using the method from [18]. First we consider auxiliary matrices $T_0$ and $T_1$, whose dimensions depend on the attractor (from $4$ to $23$ in our seven cases). Then we compute the $L_2$-spectral radius [53] of these matrices on a special subspace, which gives the Hölder exponent. The two-dimensional illustrations showing 2-attractors (a dragon, a rectangle and a bear) have been drawn using the software program from [38]. The three-dimensional illustrations have been made using two programs, Chaoscope [21] and IFStile [47]. Their algorithms are different: Chaoscope uses the probabilistic approach, its running time depends slightly on the type of attractor. The program IFStile produces more detailed pictures and uses apparently the iteration principle. Its running time depends significantly on the Hölder regularity of the attractor (see Remark 6 below). For example, the construction of a type 3 attractor (a parallelepiped), which has the highest regularity $\alpha = 0.5$, takes less than a minute, type 2 ($\alpha \approx 0.2315$) and type 4 ($\alpha\approx0.2328$) with the same parameters require several hours, and type 5 ($\alpha \approx 0.1173$) takes several days already, even for a worse image quality. These pictures also show the partition of each attractor into two affinely similar parts (dark green and light green). The images are presented in Figure 4; some attractors are shown from various angles. Remark 6. The quality of the attractors in Figure 4 depends significantly on their regularity. Let us try to explain this phenomenon using the example of the iteration method, which underlies perhaps all existing algorithms in one way or another. For the linear operator $T$ which acts in $L_2(\mathbb{R}^d)$ by the formula § 12. Series of expanding integer polynomials and 2-attractorsAs we know (Corollary 6), a 2-attractor is uniquely defined by an expanding integer polynomial $p(z)$ with leading coefficient $1$ and free term $\pm 2$. To construct an attractor we must take an integer matrix $M$ with characteristic polynomial $p$ (for example, its companion matrix (3) or any other matrix) and an arbitrary admissible pair of digits $D$. The 2-attractor obtained will be defined in a unique way, up to affine similarity, independently of $M$ and $D$. Hence, constructing 2-attractors is equivalent to finding the corresponding expanding polynomial. In this section we find several series of such polynomials. The number of polynomials of degree $d$ in each series grows linearly in $d$, only in series 4 the number of polynomials is quadratic in $d$. This is the series providing the lower bound for the number of 2-attractors in Theorem 10. First we present all series and then give the proofs. Series 1 and 2 are known in the literature, while series 3–7 are new to the best of our knowledge. Series of expanding integer polynomials with leading coefficient $1$ and free term $\pm 2$Series 1. a) Polynomials of the form $(z^m+z^q-2)/(z^{(m, q)}-1)$ with $m>q\geqslant1$, where $(m,q)$ is the greatest common divisor of $m$ and $q$. b) Polynomials of the form $(z^m+z^q+2)/(z^{(m, q)}+1)$, where $m_1=m/(m, q)$ and $m_2=q/(m, q)$ are odd, $m > q \geqslant 1$. Series 2. Polynomials in these series contain only three terms. a) Polynomials of the form $z^m - z^q + 2$ with $m > q \geqslant 1$ and odd $q_1=q/(m, q)$. b) The opposite series $z^q - z^m - 2$ with $q > m \geqslant 1$ and odd $q_1=q/(m, q)$. c) Polynomials of the form $z^m + z^q + 2$ with $m > q \geqslant 1$, where the integers $m_1=m/(m, q)$ and $q_1=q/(m, q)$ have distinct parity. Series 3. a) Polynomials of the form $(1 + z^m)(1 + z^q) + 1$ for all natural numbers $m$ and $q$. b) Polynomials of the form $(z^m - 1)(z^q - 1) + 1$ for all natural numbers $m$ and $q$. Recall that a vector with natural components $(n_1, n_2, n_3)$ is said to be bad if it is proportional to a vector of the form $(3x+s, 3y+s, 3z+s)$ with some $s \in \{1, 2\}$ and $x,y,z\in\mathbb{Z}$. All other vectors are said to be good. Series 4. a) Polynomials of the form $(1 + z^m)(1 + z^q)(1 + z^k) + 1$ for an arbitrary good vector $(m, q, k)$. b) Polynomials of the form $(1 - z^m)(1 - z^q)(1 + z^k) + 1$ apart from the case when $m\equiv q\pmod3$ and $k\equiv -m \pmod{3}$. Series 6. Polynomials of the form $(1 + z^m)(1 \pm z^r + z^{2r}) + 1$ with arbitrary natural numbers $m$ and $r$. Series 7. Polynomials of the form $(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$, where $a$, $b$ and $k$ are natural numbers. Remark 7. It is easy to see that the polynomials in series 1–7 are different (apart from the case when $k = q$ in 4, b), which reduces to 3, b), and from special cases of some series that are covered by 1). All polynomials in series 2, a), b), c), 3, a), b), 4, a), 5, 6 and 7 take different values at the point $z = 1$: $2$, $-2$, $4$, $5$, $1$, $9$, $10$, $3$ or $7$ and $2^{k+3}+1$ (where $k\leqslant1$), respectively. Now we prove that these polynomials are expanding, that is, all their roots lie outside the closed unit disc in the complex plane. Proof for series 1. a) Let $m = (m, q)m_1$ and $q = (m, q)q_1$. Then the polynomial can be rewritten as a sum of two geometric progressions Therefore, the free term is equal to $2$ and the leading coefficient is $1$. If the denominator vanishes: $z^{(m, q)} - 1 = 0$, then the value of the polynomial is $m_1 + q_1$, hence such $z$ are not roots of the polynomial. In what follows we assume that $z^{(m, q)} \ne 1$. Then $z^m + z^q - 2 = 0$, hence, the roots cannot be smaller than $1$ in modulus. If a root has modulus $1$, then the triangle inequality yields $z^m = z^q = 1$. Let $\gamma$ denote the argument of $z$ taken on the interval $[0,2\pi)$. Since $z^m = 1$, we have $\gamma={2\pi m_2}/{m}$, $m_2=0,\dots,m-1$. Moreover, $\gamma={2\pi q_2}/{q}$, $q_2=0,\dots,q-1$, so ${2\pi m_2}/{m}={2\pi q_2}/{q}$, which implies that $m_2q = q_2m$ and then $m_2q_1=q_2m_1$. Since $(m_1, q_1) = 1$, we see that $m_2$ is a multiple of $m_1$. However, in this case the argument of $z^{(m, q)}$ is equal to ${2\pi m_2 (m, q)}/{m_1 (m, q)}$, which is a multiple of $2\pi$. Therefore, the denominator $z^{(m, q)} - 1$ vanishes, which contradicts the assumption. So this polynomial does not have roots such that $|z|\leqslant1$.
b) This is a similar series, which can be obtained by changing signs. In this case the polynomial has the form
$$
\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
$$
We can assume again that $z^{(m, q)} + 1 \ne 0$, otherwise $z$ is not a root. Again there are no roots inside the unit circle, and on the unit circle we have $z^m = -1$ and $z^q= -1$. In this case the argument $\gamma \in [0, 2\pi)$ of $z$ satisfies ${\gamma=\pi/m+2\pi m_2/m=\pi/q+2\pi q_2/q}$. After multiplication by ${mq}/{\pi (m, q)}$ we obtain $q_1+2m_2q_1=m_1+2q_2m_1$. Since $(q_1,m_1)=1$, it follows that $(1+2m_2)$ is divisible by $m_1$. The argument of $z^{(m, q)}$ is ${\pi(m, q)}/{m}+{2\pi m_2(m, q)}/{m}=\pi ({1+2m_2})/{m_1}$, so this point corresponds to $-1$ because $(1+2m_2)/m_1$ is an odd integer. The denominator vanishes, which contradicts the assumption. The proof for series 1 is complete. Proof for series 2. In all the three cases the roots cannot lie inside the unit circle since in that case $|z^m \pm z^q| < 2$.
If $|z| = 1$, then in cases a) and b) we have $z^m = -1$, $z^q = 1$, and in case c) we have $z^m = -1$, $z^q = -1$. In cases a) and b) we obtain ${\pi}/{m}+{2\pi m_2}/{m}={2\pi q_2}/{q}$, where $m_2=0,\dots,m-1$, $q_2=0,\dots,q-1$. After multiplication by ${mq}/{\pi (m, q)}$ we obtain ${q_1(1\!+\!2m_2)\!=\!2q_2m_1}$. This is impossible since both $q_1$ and $1+2m_2$ are odd. In case c) we have ${\pi}/{m}+{2\pi m_2}/{m}={\pi}/{q}+{2\pi q_2}/{q}$, and therefore $q_1+ 2m_2 q_1 = m_1 + 2m_1q_2$. Hence $q_1 - m_1 = 2 (m_1q_2 - m_2q_1)$, which is impossible when $q_1$ and $m_1$ have distinct parity. Proof for series 3. a) Assume the converse: our polynomial $P(z)$ has a root $|z| \leqslant 1$.
Denote by $\overline{B}(1, 1)$ the disc in the complex plane with centre $1$ and radius $1$. Clearly, $|z^m| \leqslant 1$ and $|z^q| \leqslant 1$, so both points $z^m + 1$ and $z^q + 1$ lie in the disc $\overline{B}(1, 1)$. Observe that $z^m + 1 \ne 0$ and $z^q + 1 \ne 0$, for otherwise $P(z) = 1 \ne 0$. Every nonzero complex number in $\overline{B}(1, 1)$ has an argument strictly less than ${\pi}/{2}$ in modulus. Hence the product of two arbitrary nonzero numbers in this disc has an argument less than $\pi$ in modulus. Therefore, the product of $z^m + 1$ and $z^q + 1$ cannot have argument $\pi$ and be equal to $-1$, which is a contradiction. The proof for part b) is literally the same. Proof for series 4. a) Assume that our polynomial $P(z)$ has a root $|z| \leqslant 1$. Consider the points $z_1 = z^m + 1$, $z_2 = z^q + 1$ and $z_3 = z^k + 1$; they lie in the disc $\overline{B}(1, 1)$. Denote their arguments by $\alpha_1$, $\alpha_2$ and $\alpha_3$, respectively. Note that $z_i \ne 0$, ${i=1,2,3}$, for otherwise $P(z)=1\ne0$. Each interior point of the disc $\overline{B}(1, 1)$ has an argument smaller than ${\pi}/{2}$. Hence $|\alpha_i| < {\pi}/{2}$, $i=1,2,3$. Since $z_1z_2z_3 = -1$, it follows that $\alpha_1 + \alpha_2 + \alpha_3 = \pm \pi$. This implies that all numbers $\alpha_i$ have the same sign. We can assume that they are positive; otherwise we replace $z$ by the conjugate root. Thus, the $\alpha_i$ are the angles of an acute triangle. For an acute triangle the inequality $\cos(\alpha_1)\cos(\alpha_2)\cos(\alpha_3) \leqslant {1}/{8}$ holds, which becomes equality only for an equilateral triangle. We prove this assertion for the convenience of the reader. The function $f(x) = -\ln(\cos(x))$ is strictly convex on the interval ${x \in (0, {\pi}/{2})}$ because $f''(x)= {1}/{\cos^2(x)} > 0$. We need to find the maximum of the function $\cos(\alpha_1)\cos(\alpha_2)\cos(\alpha_3)$ or, which is equivalent, to minimize the function $f(\alpha_1, \alpha_2, \alpha_3) = -\ln(\cos(\alpha_1)) - \ln(\cos(\alpha_2)) - \ln(\cos(\alpha_3))$, which is coercive (convex, but perhaps taking the value $+\infty$) on the compact set $[0, {\pi}/{2}]^3$. Such a function possesses at most one minimum. On the intersection with the hyperplane $\alpha_1 + \alpha_2 + \alpha_3 = \pi$ the minimum is attained when all the arguments are equal.
Thus, $|\cos(\alpha_1)\cos(\alpha_2)\cos(\alpha_3)| \leqslant {1}/{8}$. Since $z_i \!\in\! \overline{B}(1, 1)$, we have ${|z_i| \!\leqslant\! 2 \cos(\alpha_i)}$. On the other hand $|z_1 z_2 z_3| = 1$; this implies that $|\cos(\alpha_1)\cos(\alpha_2)\cos(\alpha_3)| \geqslant {1}/{8}$. We come to the only possible case when the triangle is equilateral and $|z_1| = |z_2| = |z_3| = 1$. Then $z^m + 1$, $z^q + 1$ and $z^k + 1$ have the same argument ${\pi}/{3}$, and therefore $z^m$, $z^q$ and $z^k$ have the same argument ${2\pi}/{3}$. We denote the argument of $z$ by $\gamma\in[0,2\pi)$; then $\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$. Multiplying by ${3mq}/(2\pi)$ we obtain $q + 3m_2q = m + 3q_2m$. Hence $q$ and $m$ have the same remainders modulo $3$. The integer $k$ must have the same remainder. If these remainders are distinct from zero, then we have already obtained a bad vector $(q, m, k)$. If all integers $q$, $m$ and $k$ are divisible by $3$, then we divide them by the greatest common power of $3$. We obtain integers with the same nonzero remainder modulo $3$, that is, in this case $(q, m, k)$ is also a bad vector. Hence for good vectors the polynomial is expanding. b) The proof remains the same after the change of notation $z_1 = 1 - z^m$ and $z_2=1-z^q$, until we arrive at the equalities $|z_1| \!=\! |z_2| \!=\! |z_3| \!=\! 1$ and $\alpha_1 \!=\! \alpha_2 \!=\! \alpha_3 \!=\! {\pi}/{3}$ (without loss of generality we assume again that the arguments are positive). However, this time the argument of $z^m$ and $z^q$ is ${4\pi}/{3}$ and the argument of $z^k$ is again ${2\pi}/{3}$. We denote the argument of $z$ by $\gamma \in [0,2\pi)$; then $\gamma={4\pi}/(3m)+{2\pi m_2}/{m}={2\pi}/(3k)+{2\pi k_2}/{k}$, $m_2=1,\dots,m-1$ and $k_2=1,\dots,{k-1}$. Multiplying by ${3mk}/(2\pi)$ we obtain $2k + 3m_2k = m + 3q_2m$. Hence ${m\equiv -k\pmod{3}}$. Analogously, $q\equiv -k\pmod{3}$. If these conditions fail, then the polynomial is expanding. Proof for series 5. We denote our polynomial by $P(z) = (1 + z^m + z^{2m})(1 + z^q + z^{2q})+ 1$. We prove that if $(1 + z^m + z^{2m})(1 + z^q + z^{2q}) = - c$, where $c$ is a real positive number and $|z| \leqslant 1$, then $c < 1$. This is sufficient, since in this case $P(z)$ does not have roots such that $|z| \leqslant 1$. Since a polynomial is an analytic function, we can apply the open mapping principle: a nonconstant analytic function maps open sets to open sets. Hence the maximum of the real part of $P(z)$ on the unit disc is attained on its boundary. Thus, it suffices to prove the assertion for $|z| = 1$, that is, for $z = e^{i \alpha}$.
Let us investigate the properties of the polynomial $p(z) = 1 + z + z^2$ for $|z|= 1$. We spot a ‘white zone’ on the complex plane which consists of points on the unit circle with arguments in $[-{2\pi}/{3}, {2\pi}/{3}]$. Its complement on the circle will be called a ‘grey zone’ (see Figure 5). Observe that summing the vectors $z^2$ and $1$ gives a rhombus with diagonal parallel to $z$. If $z$ is in the white zone, then $p(z) = \lambda z$ for ${\lambda \geqslant 0}$, if $z$ is in the grey zone, then $p(z) = \lambda z$ for $\lambda < 0$. In both cases we obtain that $p(z)$ is in the white zone. Furthermore, we have $|p(z)|=|1+z+z^2|=|1+2\cos\alpha|$. We consider the question, for which positive real $c$ we can have $p(u)p(w)=-c$, where $u=z^m$, $w=z^q$ and $|u|=|w|=|z|=1$. If $u$ is in the grey zone, then the argument of $p(u)$ lies in $(-{\pi}/{3}, {\pi}/{3})$. The argument of $p(w)$ is in $[-{2\pi}/{3}, {2\pi}/{3}]$ since $p(w)$ is in the white zone. Hence the sum of the arguments of $p(u)$ and $p(w)$ cannot be equal to $\pi$ ($-\pi$), and therefore the equality $p(u)p(w)=-c$ is impossible. Hence both $u$ and $w$ are in the white zone. Let $u$ have argument $\beta$. Then
$$
\begin{equation*}
|p(u)p(w)|=(1+2\cos(\beta))(1+2\cos(\pi- \beta))=1-4 \cos^2 \beta.
\end{equation*}
\notag
$$
For $\beta$ such that $\cos \beta \ne 0$ this quantity is strictly less than $1$, as required. This condition can fail only if either $u = \pm i$ or $w = \pm i$. Let $u = i$. Then $p(u) = 1 + i - 1 = i$, and the product of $p(u)$ and $p(w)$ can have argument $\pi$ only for $p(w) = i$. Then $w = i$, and therefore $z^m = i$ and ${z^q=i}$. Now we prove that for $m \not \equiv q \pmod{4}$ this is impossible. Let $\gamma$ denote the argument of $z$ taken in the interval $[0,2\pi)$. Since $z^m=i$, we have $\gamma={\pi}/({2m})+{2\pi m_1}/{m}$, where $m_1=0,\dots,m-1$. Since $z^q=i$, we also have another formula: $\gamma= {\pi}/({2q})+{2 \pi q_1}/{q}$, where $q_1=0,\dots, q-1$. Thus, ${1}/({2m})+{2 m_1}/{m}={1}/({2q})+{2 q_1}/{q}$, and after multiplication by $2mq$ we obtain $q-m=4(q_1m-m_1q)$. This contradicts our assumption. The case $u = -i$ is considered similarly. In this case $w = -i$ and $q - m$ must again be a multiple of $4$. Proof for series 6. We begin with the following assertion.
Consider a polynomial $P(z) = (1+z^m)q(z^r) +1$, where $q(z) = z^n + a_{n-1}z^{n-1} + \dots + a_1z + 1$ is an integer polynomial. Then $P$ is expanding if
$$
\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
$$
Similarly to the previous series we apply the open mapping principle for analytic functions and reduce the proof to the following statement: if $z = e^{i\alpha}$ and $({1 + z^m})q(z) = - c$, where $c$ is real and strictly positive, then $c < 1$. Note that the point $1+z^m$ lies in the right-hand half-plane (if $1 + z^m = 0$, then $c = 0$ is nonpositive). Since the product of $1+z^m$ and $q(z^r)$ has argument $\pi$, $q(z^r)$ has a negative real part. Suppose $q(z^r)$ has argument $\gamma$. Then $(1+z^m)$ has argument $\pi-\gamma$ and $|1+z^m|=|2\cos(\pi-\gamma)|$. Therefore,
$$
\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
$$
Hence $c< 1$, which completes the proof.
In our case Proof for series 7. We apply the open mapping principle as for the previous two series. It suffices to prove that if $|z| = 1$ and $P(z) - 1 = -c$, where $c$ is a real positive number, then $c < 1$. We prove that the equality $P(z) - 1 = -c$ fails for any $c > 0$. Assume the converse. Let $s$ be the argument of $z$; then the arguments of $1 + z^a$, $1 + z^b$, $1 + z^{(a + b)}$, $1 + z^{2 (a + b)}$, $\dots$, $1 + z^{2^k (a + b)}$ are equal to ${as}/{2}$, ${bs}/{2}$, ${(a + b)s}/{2}$, $(a+b)s$, $\dots$, $2^{k-1}(a+b)s$ up to addition of $\pi$, respectively (see Figure 6).
Their sum is equal to $\pi$ up to addition of $2\pi$, hence for a suitable number $t \in \mathbb{Z}$ we have
$$
\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
$$
Hence $\pi t = (a+b)s (1 + 1 + 2 + 4 + \dots + 2^{k-1}) = (a+b)s 2^k$. Then the argument of the number $z^{2^k (a + b)}$ in the last pair of brackets is equal to $\pi t$ up to addition of $2\pi$. This means that either $1 + z^{2^k (a + b)} = 0$ (and so $P(z) - 1 = 0$ and $c = 0$, which is a contradiction) or $1 + z^{2^k (a + b)} = 2$. Hence we can now consider the inequality with fewer brackets:
$$
\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
$$
We repeat our argument reducing the number of brackets successively. In this way we arrive at the polynomial $(1 + z^a)(1 + z^b)$, which takes values only in the right-hand half-plane (see the proof for series 3) and hence cannot take a real negative value. Now we can give the promised proof of Theorem 9 in § 10. We denote the number of good partitions of an integer $d$ $b_{+}(d)$ and the number of bad partitions by $b_{-}(d)$ (see § 10 for the definitions). We denote the number of all partitions of $d$ into a sum of natural numbers by $b(d)$. Then we have $b(d) = b_{-}(d)+b_{+}(d)$. We use the following well-known estimate. Since the term $r(r-1)$ takes only the values $0$ and $2$ on the set of remainders modulo $3$, we obtain the following. Corollary 7. For every $d \in \mathbb{N}$ the equality $b(d)={d(d-1)}/{12}+\omega_d$ holds, where $\omega_d \in[-2/3,1/2]$. Proof of Theorem 9. The sum of the components of a bad vector is divisible by $3$, hence there are no bad partitions for $d \not \equiv 0 \pmod 3$. Therefore, $b_+(d)=b(d)$, and we apply Corollary 7 to this quantity. On the other hand, if $d\equiv0\pmod 3$, then $d=3^{\ell}d'$ and $d' \not \equiv 0 \pmod 3$. If $d=n_1+n_2+n_3$ is a bad partition, then there exists $j\leqslant \ell-1$ for which $(n_1, n_2, n_3) = 3^{j}(3x+s, 3y+s, 3z+s)$, where $s\in \{1,2\}$ and $x,y,z \in \mathbb{Z}$. Consequently, $x+y+z=3^{-j-1}d-s$. Thus, every bad partition of $d$ has the form $d = 3^{j}(3x+s) + 3^{j}(3y+s)+ 3^{j}(3z+s)$, where $j= 0,\dots,\ell-1$, $s\in\{1,2\}$ and $x+y+z$ is an arbitrary partition of $3^{-j-1}d-s$. Therefore, if $b\equiv 0\pmod 3$, then
$$
\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}
$$
Set $a_j = 3^{-j-1}d$. All the numbers $a_j$ but $a_{\ell-1}$ are multiples of $3$. Hence by Lemma 6, for $j = 0, \dots, \ell-1$ the $j$th term of the sum (9) is equal to where $v_j \in [-1,1]$. In the last term $a_{\ell -1}$ is not divisible by $3$, so the numerator of the first fraction can increase by $2$. Thus, where $v\in[-1/3,5/6]$ and $v_j\in[-1,1]$. To estimate this value from below we replace the sum of the ${a_j^2}/{6}$ by an infinite sum and the sum of the ${2a_j}/{3}$ by the first term. Taking the sum of a geometric progression and using the estimate $\sum_{j=0}^{l-1} (\frac{1}{2} + v_j) \leqslant \frac{1}{2} l \leqslant \frac{3}{2} d$ we obtain the required lower bound. Vice versa, for an upper bound we replace the sum of the ${a_j^2}/{6}$ by the first term and the sum of the ${2a_j}/{3}$ by an infinite geometric progression. Thus we obtain the upper bound. § 13. Appendix Proof of Lemma 5. Assume that $\mathcal{T}(M_1, \overline{\boldsymbol{a}}_1) = \mathcal{T}(M_2, \overline{\boldsymbol{a}}_2)$. First we show that $\rho(M_1^{-1}) = \rho(M_2^{-1})$, where $\rho$ is the spectral radius of the matrix. Since $M_1$ does not have multiple eigenvalues and since $\boldsymbol{a}_1$ does not belong to an invariant subspace of $M_1$, we obtain $\|M_1^{-k} \boldsymbol{a}_1\| \asymp [\rho(M_1^{-1})]^k$, where $\asymp$ denotes asymptotic equivalence. Then the number of segments in the set $\mathcal{T}(M_1, \overline{\boldsymbol{a}}_1)$ whose length exceeds a prescribed number $\varepsilon$ is equal to ${\ln \varepsilon }/{\ln \rho(M_1^{-1})}+o(1)$ as $\varepsilon \to 0$. Since $\mathcal{T}(M_1, \overline{\boldsymbol{a}}_1)=\mathcal{T}(M_2,\overline{\boldsymbol{a}}_2)$, we obtain $\rho(M_1^{-1})= \rho(M_2^{-1})$.
We can assume that $M_1^{-1}$ has a unique eigenvalue largest in modulus (or two complex conjugate ones), for otherwise the problem reduces to several problems of smaller dimensions. We call the eigenvalue largest in modulus the leading one and also call its eigenvector a leading eigenvector. Let $V_i$ be the subspace in $\mathbb{R}^d$ spanned by the leading eigenvectors of the matrix $M_i^{-1}$, $i = 1,2$. Then two cases are possible. 1) $\dim V_1 = 1$. In this case the leading eigenvalue $\lambda$ is real and $V_1$ is spanned by the leading eigenvector $\boldsymbol{v}_1$. Then the direction of the vector $M_1^{-k}\overline{\boldsymbol{a}}_1$ converges to the direction of $V_1$ as $k \to \infty$. Hence the ratio of the lengths of the successive line segments $M_1^{-k-1}\overline{\boldsymbol{a}}_1$ and $M_1^{-k}\overline{\boldsymbol{a}}_1$ tends to $\rho(M_1^{-1})$ as $k \to \infty$. Since $\rho(M_1^{-1}) < 1$, for sufficiently large $k$ we know the order of elements in the sequence $\{M_1^{-k}\overline{\boldsymbol{a}}_1\}_{k\geqslant N}$. This means that for small $\varepsilon > 0$ we know the order of elements of the set $\mathcal{T}(M_1,\overline{\boldsymbol{a}}_1)$ with length smaller than $\varepsilon$. We take $d+2$ segments in a row and denote the straight lines on which they lie by $\ell_1, \dots, \ell_{d+2}$. The operator $M_1^{-1}$ maps the line $\ell_i$ to $\ell_{i+1}$, $i = 1, \dots, d+1$. Regarding each line as a point in the projective space $\mathbb{P}^{d-1}$ we see that the operator $M_1^{-1}$ is uniquely defined up to a sign as an operator in $\mathbb{P}^{d-1}$ that maps prescribed $d+1$ points to prescribed points. Now consider the operator $M_2^{-1}$. It must have the same leading eigenvector $\boldsymbol{v}_2 = \boldsymbol{v}_1$ as the unique limit direction of vectors in $\mathcal{T}(M_2, \overline{\boldsymbol{a}}_2)$ (hence $\dim V_2 = 1$). The order of segments of length less than $\varepsilon$ for this operator must be the same, so we obtain the same lines $\ell_1,\dots,\ell_{d+2}$ in the same order. This implies that $M_1$ and $M_2$ define the same projective operator in $\mathbb{P}^{d-1}$, hence $M_1=\pm M_2$. 2) $\dim V_1 = 2$. In this case the leading eigenvalue of $M_1^{-1}$ has the form $re^{2\pi i \alpha_1}$, where $r=\rho(M_1^{-1})$. We need to consider two cases. a) $\alpha_1 = {p}/{q}$ is rational (${p}/{q}$ is an irreducible fraction). In a suitable basis in the two-dimensional plane $V_1$ the operator $M_1^{-1}|_{V_1}$ is a rotation through an angle of ${2\pi p}/{q}$ with multiplication by $r$. The line segments $M_1^{-k}\overline{\boldsymbol{a}}_1$ have exactly $q$ limit directions corresponding to the angles ${2\pi n}/{q}$, $n= 0, \dots, q-1$. There are at least three of these directions, because the case when $q=2$ corresponds to case 1) of real $\lambda$. Therefore, there exists a unique linear transform that maps the limit directions of vectors in the set $\mathcal{T}(M_1, \overline{\boldsymbol{a}}_1)$ to the directions at angles ${2\pi p}/{q}$, $p=0,\dots,q-1$. Consequently, the basis on the plane $V_1$ in which the operator $M_1^{-1}$ is a rotation with a contraction is uniquely determined by the set $\mathcal{T}(M_1, \overline{\boldsymbol{a}}_1)$. In this basis the ratio of the lengths of consecutive segments in $\{M_1^{-k}\overline{\boldsymbol{a}}_1\}_{k \geqslant N}$ tends to $r$, which gives us the order of elements of this sequence. The reasoning that follows is the same as in case 1): having found the order of the sequence we recover the operator $M_1^{-1}$ and thus prove that $M_1 = \pm M_2$. b) $ \alpha_1$ is irrational. In this case, in a suitable basis on the two-dimensional plane $V_1$ the operator $M_1^{-1}|_{V_1}$ is a rotation through an irrational angle of $2\pi \alpha_1$ with multiplication by $r$. To identify this basis we apply Weyl’s theorem on uniform distribution [59]: a trajectory of an irrational rotation of a unit vector converges to a uniform distribution on a circle. This means that for every arc of the unit circle the share of points on this arc in the sequence of points from the first to the $n$th tends to the ratio of the arc length to the length of the circle. The same is true for the projections of the segments $M_1^{-k}\overline{\boldsymbol{a}}_1$, since the angles between these segments and the subspace $V_1$ tend to zero at an exponential rate as $k\to \infty$. The number of line segments of length larger than $\varepsilon$ in the set $\mathcal{T}(M_1, \overline{\boldsymbol{a}}_1)$ is ${\ln \varepsilon }/{\ln r}+O(1)$ as $\varepsilon \to 0$. The number of projections of such segments occurring in a fixed angle of opening $\beta$ is ${\beta\ln \varepsilon }/{\pi \ln r}+o(1)$. If there exists another suitable basis in $V_1$, then it has to produce the same value of $\beta$. Thus, in the new basis the values of all angles are the same as in the old one. Hence this is the same basis up to an orthogonal transformation. We see that for an arbitrary set $\mathcal{T}(M_1, \overline{\boldsymbol{a}}_1)$ there exists a unique, up to an orthogonal transformation, basis in the two-dimensional plane $V_1$ in which the operator $M_1^{-1}$ is a rotation with multiplication by $r$. In this basis, the order of the segments in the sequence under consideration is uniquely defined, hence the operator $M_1^{-1}$ is also uniquely defined up to a sign. If we consider now the operator $M_2^{-1}$ with the same set $\mathcal{T}(M_2,\overline{\boldsymbol{a}}_2)= \mathcal{T}(M_1, \overline{\boldsymbol{a}}_1)$, then it has the same two-plane $V_2 = V_1$ as the limit plane of the directions of line segments in $\mathcal{T}(M_2,\overline{\boldsymbol{a}}_2)$ and the same basis in which $M_2^{-1}$ is a rotation with multiplication. Therefore, the elements of the sequence $M_2^{-k}\overline{\boldsymbol{a}}_2$ have the same ordering, provided that $k$ is large enough. In the same way as in part 1), having found the order of the elements we recover the operator $M_2^{-1}$ and thus prove that $M_1 = \pm M_2$. The lemma is proved. Proof of Lemma 6. Without loss of generality we assume that $n_1\leqslant n_2\leqslant n_3$. Let $d=3k+r$, $r\in\{0,1,2\}$. For $k=0$ the assertion is obvious, hence we suppose that $k\geqslant 1$. Then $n_1\leqslant k$, and $n_2 \in[n_1,[(d-n_1)/2]]$, where $[x]$ is an integer part of $x$. Consequently, The total number of odd integers in the sequence $d-n_1$, $n_1=1,\dots,k$, is at least $(k-1)/{2}$ and at most $(k+1)/{2}$. Hence Now we complete the proof by direct calculation. The lemma is proved. AcknowledgementsThe authors are grateful to S. Konyagin, A. Dubickas, I. Shkredov, N. Moshchevitin and S. Ivanov for useful discussions.
Citation in format AMSBIB
\Bibitem{ZaiPro22} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|