1. Introduction and statement of results

We recall that an iterated function system acting on $\mathbb {R}^{d}$ is a tuple $(T_1,\,\ldots,\,T_N)$ of contractions of $\mathbb {R}^{d}$ with respect to some norm on $\mathbb {R}^{d}$, which in this article will always be the Euclidean norm. It is classical (see [Reference Hutchinson15]) that for every such iterated function system, there exists a unique non-empty compact set $X\subset \mathbb {R}^{d}$ with the property $X=\bigcup _{j=1}^{N} T_jX$ and this set is conventionally called the attractor or limit set of the iterated function system. The iterated function system $(T_1,\,\ldots,\,T_N)$ is said to satisfy the open set condition if there exists a non-empty open set $U\subset \mathbb {R}^{d}$ such that $T_jU\subseteq U$ for every $j=1,\,\ldots,\,N$ and such that the distinct images $T_j U$, $T_kU$ have empty pairwise intersection. If the open set condition holds and every $T_j$ is given by a similarity transformation $T_jx=r_j O_jx+v_j$ with $r_j \in (0,\,1)$, $O_j \in O(d)$ and $v_j \in \mathbb {R}^{d}$, then it is well known that the Hausdorff dimension and upper and lower box dimensions of $X$ coincide and are all equal to the unique $s \in (0,\,d]$ such that $\sum \nolimits _{j=1}^{N} r_j^{s}=1$, a value which is conventionally called the similarity dimension of the iterated function system. Since the classic work of J.E. Hutchinson in [Reference Hutchinson15], there has been substantial interest in extending this result by weakening either the hypothesis of the open set condition, the hypothesis that the transformations $T_j$ should be similitudes, or both.

An iterated function system $(T_1,\,\ldots,\,T_N)$ acting on $\mathbb {R}^{d}$ is said to have exact overlaps if for some pair of distinct words $j_1j_2 \cdots j_n \in \{1,\,\ldots,\,N\}^{n}$ and $k_1k_2\cdots k_m \in \{1,\,\ldots,\,N\}^{m}$ one has $T_{j_1}T_{j_2}\cdots T_{j_n}=T_{k_1}T_{k_2}\cdots T_{k_m}$. By considering the words $j_1\cdots j_n k_1\cdots k_m$ and $k_1\cdots k_mj_1\cdots j_n$ in place of $j_1\cdots j_n$ and $k_1\cdots k_m$, it may be assumed without loss of generality that $n=m$, and we will always make this reduction in the sequel. When $(T_1,\,\ldots,\,T_N)$ consists of similitudes and admits exact overlaps, it is well known as folklore (and is explicitly articulated in [Reference Simon and Solomyak26]) that the Hausdorff and box dimensions of the attractor are strictly smaller than the similarity dimension. In this work, we will call an iterated function system for which the Hausdorff dimension of the attractor is smaller than the similarity dimension exceptional. It is conjectured (see e.g. [Reference Hochman13]) that for an iterated function system of similitudes the only situations in which the system is exceptional are those in which either an exact overlap exists, or the similarity dimension exceeds the dimension of the smallest affine subspace of $\mathbb {R}^{d}$ which is preserved by every $T_j$. Both of the latter two circumstances are precluded a priori when the open set condition is satisfied.

More generally, an affine iterated function system is usually understood to be a tuple $(T_1,\,\ldots,\,T_N)$ of invertible affine transformations of $\mathbb {R}^{d}$ all of which are contracting with respect to some norm on $\mathbb {R}^{d}$. In this context, a suitable analogue of the similarity dimension, now often called the affinity dimension, was articulated by Falconer in [Reference Falconer8]. The affinity dimension is always an upper bound for the upper box dimension of the attractor. According to one of the principal results of [Reference Falconer8], if a tuple of linear maps $A_1,\,\ldots,\,A_N \in \operatorname {GL}_d(\mathbb {R})$ is specified and those maps are all sufficiently strongly contracting, then for Lebesgue almost every choice of $(u_1,\,\ldots,\,u_N) \in (\mathbb {R}^{d})^{N}$, the attractor of the iterated function system $(T_1,\,\ldots,\,T_N)$ defined by $T_jx:=A_jx+u_j$ has Hausdorff dimension and upper and lower box dimension equal to its affinity dimension. On the other hand, affine iterated function systems for which these dimensions are not equal to the affinity dimension (which we again describe as “exceptional”) are much easier to construct than in the self-similar case, as follows.

In the affine case, the open set condition does not suffice to guarantee that the dimension of the attractor is non-zero (an observation which dates back to [Reference Edgar6]). In the case of affine iterated function systems, the existence of exact overlaps again guarantees exceptionality, although the required arguments are much more delicate than in the self-similar case and are correspondingly much more recent (see the introduction to [Reference Morris23]). As before, if an affine iterated function system preserves an affine subspace with dimension smaller than the affinity dimension then the affine subspace necessarily contains the attractor, so the dimension of the subspace bounds the dimension of the attractor and the iterated function system is necessarily exceptional. In the affine case, a further possibility exists that the iterated function system may lack an invariant affine subspace but preserve a low-dimensional variety or manifold, a phenomenon which is investigated in [Reference Bandt and Kravchenko2, Reference Feng and Käenmäki10]. For example, if $T_1,\,\ldots,\,T_N \colon \mathbb {R}^{3}\to \mathbb {R}^{3}$ are contractions of the form

\[ T\begin{pmatrix} x\\y\\z\end{pmatrix}:=\begin{pmatrix} \lambda_1\lambda_2 & \lambda_1 v & \lambda_2 u \\ 0 & \lambda_1 & 0\\ 0 & 0 & \lambda_2 \end{pmatrix}\begin{pmatrix} x\\y\\z\end{pmatrix} + \begin{pmatrix} uv\\u\\v\end{pmatrix} \]

then the two-dimensional variety $\{(x,\,y,\,z) \in \mathbb {R}^{3} \colon x=yz\}$ is preserved by the iterated function system $(T_1,\,\ldots,\,T_N)$, hence this variety contains the attractor and the dimension of the attractor cannot be higher than two. On the other hand, as long as the parameters $\lambda _1$, $\lambda _2$, $u$, $v$ are chosen such that the fixed points of $T_1,\,\ldots,\,T_N$ do not belong to a common one- or two-dimensional affine subspace of $\mathbb {R}^{3}$ then no invariant affine subspace can exist, since any invariant subspace must contain these fixed points. Lastly, it may happen that the open set condition holds, no proper submanifold of $\mathbb {R}^{d}$ is preserved by the iterated function system, no exact overlaps exist, and yet the iterated function system is nonetheless exceptional (see e.g. [Reference Bedford4, Reference Das and Simmons5, Reference Feng and Wang11, Reference Fraser12, Reference McMullen22]). A feature common to most such systems is the existence of a linear projection map $P\colon \mathbb {R}^{d} \to \mathbb {R}^{d}$ such that $PT_jP=PT_j$ for every $j=1,\,\ldots,\,N$ and such that the kernel of the projection $P$ is more strongly contracted by the transformations $T_j$ than is the image subspace of $P$. Remarkably, at least three of these four sources of exceptionality may hold robustly with respect to changes in the translation parameters $v_1,\,\ldots,\,v_N$ of the affine transformations $T_ix=A_ix+v_i$; see the introduction to [Reference Morris23] for further examples and discussion.

This note is concerned with the way in which three of the properties described above — the open set condition, the existence of exact overlaps, and the property of being exceptional — depend on the translation parameters of an affine iterated function system. More formally, given linear maps $A_1,\,\ldots,\,A_N \in \operatorname {GL}_d(\mathbb {R})$ all of which are contracting with respect to some norm on $\mathbb {R}^{d}$, we ask about the structure of the set of tuples $(u_1,\,\ldots,\,u_N) \in (\mathbb {R}^{d})^{N}$ such that the iterated function system $(T_1,\,\ldots,\,T_N)$ defined by $T_jx:=A_j+u_j$ is exceptional (or otherwise), or satisfies the open set condition, or admits exact overlaps. In this note, we exhibit examples with the property that all of these phenomena are at once dense in the space of translation parameters. This family of examples may be constructed for every value of $d$, and in two dimensions includes strongly irreducible examples for which the linear maps $A_1,\,\ldots,\,A_N$ do not preserve any finite union of lines through theorigin in $\mathbb {R}^{d}$.

The purpose of this note is to prove the following theorem:

If $\|A^{-1}\|<\frac {1}{2}$ then the theorem of Falconer from [Reference Falconer8] (in its modified form which was introduced by Solomyak in [Reference Solomyak27]) may be applied to the above system to show that for Lebesgue almost every $(u_1,\,\ldots,\,u_N) \in (\mathbb {R}^{d})^{N}$ the attractor of $(T_1,\,\ldots,\,T_N)$ has Hausdorff dimension precisely $d$. Likewise a theorem of Jordan, Pollicott and Simon in [Reference Jordan, Pollicott and Simon16] applies to show that the dimension of the uniform self-affine measure $\nu$ defined by $(T_1,\,\ldots,\,T_N)$ is equal to $d$ for almost all translation parameters. A recent result of D.-J. Feng [Reference Feng9] also implies that the set of non-exceptional parameters $(u_1,\,\ldots,\,u_N)$ in both of these theorems contains a dense $G_\delta$ set as well as having full Lebesgue measure. Theorem 1 thus illustrates on the other hand that the set of exceptional translation parameters in these two theorems is in some cases dense in the parameter space, a possibility which does not seem to have been explicitly noted before. We remark that the special case of Theorem 1 in which $d=1$ and in which $A$ is equal to the $1\times 1$ matrix with $3$ as its sole entry was previously obtained by R. Kenyon in [Reference Kenyon17, §2], but its connection with Falconer's theorem was not remarked on in that work. In certain special cases, the division into the two possible outcomes (i) and (ii) in the case $u_1,\,\ldots,\,u_N \in \bigcup _{m \geq 0} A^{-m}\mathbb {Z}^{d}$ can be related to earlier work of Ngai and Wang in [Reference Ngai and Wang24], and this is discussed further in the next section.

In the case $N<|\det A|$ it is not possible to obtain conclusions similar to those of Theorem 1 (with a Hausdorff measure of appropriate dimension substituted for Lebesgue measure) since the open set condition may be satisfied while the Hausdorff measure of the attractor is zero (see [Reference Bedford4, Reference McMullen22]). In the excluded case where $N=2$, taking $d=2$ and

\[ A=\begin{pmatrix}1 & 1\\-1 & 1\end{pmatrix}, \]

one may show that the attractor is independent of the choice of the translation vectors up to changing the co-ordinates by a similarity transformation, as long as the translation vectors $u_1,\,u_2 \in \mathbb {R}^{d}$ are always taken to be distinct. In this case, the attractor is in fact the twindragon fractal studied by Davis and Knuth (see e.g. [Reference Knuth18, §4.1]). Consequently when $N=2$, it is not always possible for the two cases (i), (ii) to be densely intermixed in the parameter space.

An iterated function system $(T_1,\,\ldots,\,T_N)$ of the form $T_jx=A_ix+v_i$ is often called reducible if the matrices $A_i$ all preserve a common subspace $V$ of $\mathbb {R}^{d}$ such that ${0<\dim V< d}$ and irreducible otherwise; the system is called strongly irreducible if the matrices $A_i$ do not preserve any finite union of such subspaces. Strong irreducibility is a requirement of several known sufficient conditions for the Hausdorff dimension of the attractor to equal the affinity dimension (most notably [Reference Bárány, Hochman and Rapaport3, Reference Hochman and Rapaport14] as well as a number of now-subsumed earlier results) and examples where the Hausdorff dimension does not equal the affinity dimension are frequently reducible (see for example [Reference Bedford4, Reference Das and Simmons5, Reference Feng and Wang11, Reference McMullen22, Reference Przytycki and Urbański25]) or at least fail to be strongly irreducible [Reference Fraser12]. When $d>2$ the matrix $A$ in Theorem 1 necessarily admits a real invariant subspace and in those cases, the iterated function system $(T_1,\,\ldots,\,T_N)$ is consequently reducible. On the other hand when $d=2$ strong irreducibility occurs whenever $A$ has non-real eigenvalues which are not proportional to roots of unity. A strongly irreducible example with $d=2$ and $\|A^{-1}\|=1/\sqrt {N}=1/\sqrt {5}$ is illustrated in Figure 1.

Figure 1.

Attractors of two iterated function systems of the type described in Theorem 1. (i). A strongly irreducible planar system satisfying the open set condition, (ii). The same system with different translation parameters and with exact overlaps.

The method of proof of Theorem 1 is as follows. Firstly, by an affine change of co-ordinates every iterated function system of the form $T_jx \equiv A^{-1}x+u_j$ with translation vectors in $\bigcup _{m \geq 0}A^{-m}\mathbb {Z}^{d}$ is equivalent to such a system with every $u_j$ belonging to $\mathbb {Z}^{d}$ and with one of the vectors $u_j$ being zero. In this context it is classical that positive Lebesgue measure of the attractor is equivalent to the absence of exact overlaps (see [Reference Lagarias and Wang20]) and the remaining details of the dichotomy into (i) versus (ii) may also be completed using existing results on iterated function systems. Classical results on self-affine tilings such as [Reference Bandt1] also provide a sufficient condition for the open set condition which can be shown to hold densely on $(\bigcup _{m \geq 0}A^{-m}\mathbb {Z}^{d})^{N}$ and this establishes (i). To show that (ii) is satisfied densely in $(\bigcup _{m \geq 0}A^{-m}\mathbb {Z}^{d})^{N}$ we modify a classical Fourier-analytic argument of Erdős from [Reference Erdős7] to show that for a dense set of translation parameters, the measure $\nu$ is singular.

We lastly remark that the literature on self-affine tilings includes general sufficient conditions for the attractor to have zero Lebesgue measure (and hence for the case (ii) to hold) which could in principle be used to give an alternative, more constructive proof that (ii) holds densely in certain cases, but these results require additional hypotheses on $A$ and $N$ which would significantly narrow the scope of the result. Such sufficient conditions are part of the subject of the article [Reference Lagarias and Wang19].

2. Proof of Theorem 1

Throughout the proof, we fix $A$ and $N$ satisfying the hypotheses of Theorem 1. We begin by establishing the dichotomy described in Theorem 1:

Proof. The existence and uniqueness of $\nu$ follow from the classical results of J.E. Hutchinson [Reference Hutchinson15]. Since there exists $m\geq 0$ such that $u_1,\,\ldots,\,u_N \in A^{-m}\mathbb {Z}^{d}$, by a linear change of co-ordinates of the form $x \mapsto A^{m}x$ we may without loss of generality suppose that $u_1,\,\ldots,\,u_N \in \mathbb {Z}^{d}$; by a further translation of the co-ordinates we also assume without loss of generality that $u_1=0$. It is straightforward to check that the two outcomes (i) and (ii) are unaffected by these co-ordinate transformations. We, therefore, make this reduction for the remainder of the proof.

We first show that if exact overlaps are present then the other properties described in (ii) above must follow. We recall that the affinity dimension defined by Falconer in [Reference Falconer8] is a real number associated with each invertible affine iterated function system $(\hat {T}_1,\,\ldots,\,\hat {T}_{\hat {N}})$ on $\mathbb {R}^{d}$ whose properties include the following. Let each $\hat {T}_j$ have the form $\hat {T}_jx=B_jx+v_j$ for some invertible linear map $B_j$ and vector $v_j$. Then the upper box dimension of the attractor of $(\hat {T}_1,\,\ldots,\,\hat {T}_{\hat {N}})$ is bounded above by the affinity dimension of $(\hat {T}_1,\,\ldots,\,\hat {T}_{\hat {N}})$, and its affinity dimension is strictly less than $d$ if and only if $\sum \nolimits _{j=1}^{\hat {N}} |\det B_j|<1$. Suppose now that $(T_1,\,\ldots,\,T_N)$ admits an exact overlap corresponding to two words of length $n$, say, and let $X=\bigcup _{j=1}^{N} T_jX$ be its attractor. Let $\hat {T}_1,\,\ldots,\,\hat {T}_{N^{n}}$ denote the $N^{n}$ maps of the form $T_{j_1}\cdots T_{j_n}$ where $j_1,\,\ldots,\,j_n \in \{1,\,\ldots,\,N\}$. Since $(T_1,\,\ldots,\,T_N)$ is assumed to have an exact overlap of length $n$, at least two of the maps $\hat {T}_j$ fail to be distinct, so by relabelling if necessary we assume without loss of generality that $\hat {T}_{N^{n}}=\hat {T}_{N^{n}-1}$. By iterating the functional equation $X=\bigcup _{j=1}^{N} T_jX$ we have

\[ X=\bigcup_{j=1}^{N} T_jX= \bigcup_{j_1,\ldots,j_n=1}^{N} T_{j_1}\cdots T_{j_n}X = \bigcup_{j=1}^{N^{n}} \hat{T}_jX=\bigcup_{n=1}^{N^{n}-1}\hat{T}_jX \]

where we have used the fact that the sets $\hat {T}_{N^{n}}X$ and $\hat {T}_{N^{n}-1}X$ are identical. Thus $X$ is the attractor of the iterated function system $(\hat {T}_1,\,\ldots,\,\hat {T}_{N^{n}-1})$ as well as of $(T_1,\,\ldots,\,T_N)$. But each $\hat {T}_j$ has the form $\hat {T}_jx=A^{-n}x + v_j$ for some $v_j \in \mathbb {R}^{d}$, and since $\sum \nolimits _{j=1}^{N^{n}-1}|\det A^{-n}|=(N^{n}-1)|\det A|^{-n} = 1-N^{-n}<1$ the affinity dimension of $(\hat {T}_1,\,\ldots,\,\hat {T}_{N^{n}-1})$ is strictly less than $d$. It follows that the upper box dimension of $X$ is strictly smaller than $d$ and in particular $X$ has zero Lebesgue measure. The support $Z$ of $\nu$ is easily seen to satisfy $Z=\bigcup _{j=1}^{N} T_jZ$ and is therefore precisely equal to the attractor $X$, so the support of $\nu$ has zero Lebesgue measure and $\nu$ is necessarily singular. This completes the verification of (ii).

We now suppose for the remainder of the proof that exact overlaps are not present and demonstrate that in this case (i) holds. For this, we will apply a result of Lagarias and Wang from the literature on self-affine tilings [Reference Lagarias and Wang20]. A simple induction shows that for every $n \geq 1$, for every word $j_1j_2\cdots j_n$ and every $x \in \mathbb {R}^{d}$ we have

\[ T_{j_1}\cdots T_{j_n} x =A^{{-}n}x + \sum_{r=1}^{n} A^{1-r} u_{j_r}. \]

It follows that if $j_1j_2\cdots j_n$ and $k_1k_2\cdots k_n$ are distinct words, then since by hypothesis $T_{j_1}\cdots T_{j_n} \neq T_{k_1}\cdots T_{k_n}$ we necessarily have

\[ \sum_{r=1}^{n} A^{1-r} u_{j_r} \neq \sum_{r=1}^{n} A^{1-r} u_{k_r}. \]

Multiplying on the left by $A^{n-1}$ and rearranging we find that

\[ \sum_{t=0}^{n-1} A^{t} u_{j_{n-t}} \neq \sum_{t=0}^{n-1}A^{t} u_{k_{n-t}}. \]

Since both expressions belong to $\mathbb {Z}^{d}$ they are necessarily separated by a Euclidean distance of at least $1$. For every $n \geq 1$ define

\[ \mathcal{D}_n:=\left\{\sum_{t=0}^{n-1} A^{t} u_{j_{t+1}} \colon j_1,j_2,\ldots,j_n \in \{1,\ldots,N\} \right\}. \]

It follows from the preceding arguments that each $\mathcal {D}_n$ contains exactly $N^{n}$ distinct points. The fact that $u_1=0$ implies that $\mathcal {D}_n \subseteq \mathcal {D}_{n+1}$ for every $n \geq 1$ since every element of $\mathcal {D}_n$ may be realized as an element of $\mathcal {D}_{n+1}$ with $u_{j_{n+1}}=u_1=0$. The union $\bigcup _{n=1}^{\infty } \mathcal {D}_n$ consists of points separated by a Euclidean distance of at least $1$ and is thus uniformly discrete in the sense of [Reference Lagarias and Wang20, §2]. We may now apply the implication (iv)$\implies$(iii) of [Reference Lagarias and Wang20, Theorem 1.1] to deduce that the attractor of $(T_1,\,\ldots,\,T_N)$ is equal to the closure of its interior and that the topological boundary of the attractor has zero Lebesgue measure. Let $U$ denote the interior of the attractor: clearly, $U$ has a positive Lebesgue measure and $U=\bigcup _{j=1}^{N} T_j U$ up to Lebesgue measure zero. The latter is only possible if both $T_jU \subseteq U$ for every $j=1,\,\ldots,\,N$ and if distinct sets $T_jU$ do not intersect, which is precisely the open set condition. It is straightforward to deduce that if $\lambda$ denotes the normalized restriction of Lebesgue measure to $U$ then $\frac {1}{N}\sum \nolimits _{j=1}^{N} (T_j)_*\lambda =\lambda$ and this implies that $\lambda =\nu$ since this functional equation has a unique solution. The proof is complete.

Remark. The proof of Proposition 2.1 in effect makes use of the fact that under that proposition's hypotheses, for every two distinct words $j_1j_2\cdots j_n$ and $k_1k_2\cdots k_n$ we have either

\[ T_{j_1}\cdots T_{j_n}=T_{k_1}\cdots T_{k_n} \]

or

\[ \|T_{j_1}\cdots T_{j_n}(0)-T_{k_1}\cdots T_{k_n}(0)\|\geq \|A^{{-}n}\|\geq C\kappa^{n}, \]

where $C>0$ and $\kappa \in (0,\,1)$ are suitable constants depending only on $A$. This results in $T_1,\,\ldots,\,T_N$ satisfying the weak separation condition introduced in K.-S. Lau and S.-M. Ngai's article [Reference Lau and Ngai21] and investigated further in [Reference Ngai and Wang24, Reference Zerner28]. Indeed, in the special case, where $A$ is proportional to an orthogonal matrix the conclusions of Proposition 2.1 may be obtained directly from certain results of [Reference Ngai and Wang24].

Returning to the proof of Theorem 1, it remains for us to establish that the two outcomes (i) and (ii) each hold for a dense set of parameters $(u_1,\,\ldots,\,u_N) \in (\bigcup _{m\geq 0}A^{-m}\mathbb {Z}^{d})^{N}$. In view of the above proposition, it will suffice to establish the following two facts: there exists a dense set of $(u_1,\,\ldots,\,u_N) \in (\bigcup _{m\geq 0}A^{-m}\mathbb {Z}^{d})^{N}$ such that the associated iterated function system does not have exact overlaps; and there exists a dense set of $(u_1,\,\ldots,\,u_N) \in (\bigcup _{m\geq 0}A^{-m}\mathbb {Z}^{d})^{N}$ such that the associated measure $\nu$ is singular. We begin with the former, for which we modify a criterion established by C. Bandt [Reference Bandt1].

Proof. Let $(u_1,\,\ldots,\,u_N) \in (\bigcup _{m\geq 0} A^{-m}\mathbb {Z}^{d})^{N}$ and suppose that $A^{m_0}u_j \in \mathbb {Z}^{d}$ for every $j=1,\,\ldots,\,N$ and that the $N$ sets $A^{m_0}u_j+A\mathbb {Z}^{d}$ are all pairwise distinct. Suppose for a contradiction that $T_{j_1}\cdots T_{j_n}=T_{k_1}\cdots T_{k_n}$ for two distinct words $j_1j_2\cdots j_n$ and $k_1k_2\cdots k_n,$ which without loss of generality we assume to have equal length. Since for all $x \in \mathbb {R}^{d}$

\[ T_{j_1}\cdots T_{j_n}x = A^{{-}n}x + \sum_{r=1}^{n} A^{1-r}u_{j_r},\quad T_{k_1}\cdots T_{k_n}x = A^{{-}n}x + \sum_{r=1}^{n} A^{1-r}u_{k_r} \]

it follows that

\[ \sum_{r=1}^{n} A^{1-r}u_{j_r} = \sum_{r=1}^{n} A^{1-r}u_{k_r}. \]

Let $t \in \{1,\,\ldots,\,n\}$ be the largest integer such that $u_{j_t} \neq u_{k_t}$. Clearly, this implies

\[ \sum_{r=1}^{t} A^{1-r}u_{j_r} = \sum_{r=1}^{t} A^{1-r}u_{k_r} \]

and therefore

\[ \sum_{r=0}^{t-1} A^{r} u_{j_{t-r}} = \sum_{r=0}^{t-1} A^{r} u_{k_{t-r}} \]

so that

\[ A^{m_0}u_{j_t} - A^{m_0} u_{k_t} = \sum_{r=1}^{t-1} A^{r} \left(A^{m_0}u_{k_r}-A^{m_0}u_{j_r}\right) \in A\mathbb{Z}^{d}. \]

Hence $A^{m_0}u_{j_t}+A\mathbb {Z}^{d} = A^{m_0} u_{k_t}+A\mathbb {Z}^{d}$, a contradiction. The proof is complete.

Proof. Let $(v_1,\,\ldots,\,v_N) \in (\bigcup _{m\geq 0} A^{-m}\mathbb {Z}^{d})^{N}$ be arbitrary and choose $m_0 \geq 0$ such that $A^{m_0}v_j \in \mathbb {Z}^{d}$ for every $j=1,\,\ldots,\,N$. Let $n \geq 1$ be arbitrary. Since $\mathbb {Z}^{d}$ is $(1/\sqrt {2})$-dense in $\mathbb {R}^{d}$, the lattice $A\mathbb {Z}^{d}$ is $(\|A\|/\sqrt {2})$-dense in $\mathbb {R}^{d}$, so the $N$ distinct sets of the form $v+A\mathbb {Z}^{d}$ are each $(\|A\|/\sqrt {2})$-dense in $\mathbb {R}^{d}$. It follows that we may choose $(w_1,\,\ldots,\,w_N) \in \mathbb {Z}^{d}$ such that $\max _j \|A^{m_0+n}v_j-w_j\| \leq \|A\|/\sqrt {2}$ and such that the sets $w_j+A\mathbb {Z}^{d}$ are all distinct. Now define $u_j:=A^{-m_0-n}w_j$ for every $j=1,\,\ldots,\,N$. Clearly, we have $(u_1,\,\ldots,\,u_N) \in \mathcal {U}$ and

\[ \max_j \|u_j-v_j\|\leq \left\|A^{{-}m_0-n}\right\| \cdot \max_j \left\|A^{m_0+n}v_j-w_j\right\| \leq \bigg(\frac{\|A\|}{\sqrt{2}}\bigg) \left\|A^{{-}m_0-n}\right\|. \]

In particular by choosing $n$ sufficiently large the tuple $(u_1,\,\ldots,\,u_N)$ may be chosen as close to $(v_1,\,\ldots,\,v_N)$ as desired. The lemma is proved.

This completes the proof that the set of parameters corresponding to the outcome (i) of Theorem 1 is dense in $(\bigcup _{m \geq 0} A^{-m}\mathbb {Z}^{d})^{N}$. To show that the second outcome (ii) is also dense, we require two further lemmas. The first of these shows that a certain Fourier-analytic condition holds densely in $(\bigcup _{m \geq 0} A^{-m}\mathbb {Z}^{d})^{N}$, and the second demonstrates that the Fourier-analytic condition implies the singularity of the measure $\nu$.

Proof. Fix a non-zero vector $w \in \mathbb {Z}^{d}$ throughout the proof, and also choose vectors $u_1,\,\ldots,\,u_{N-1} \in \bigcup _{m \geq 0}A^{-m}\mathbb {Z}^{d}$ arbitrarily. We will show that the set of all $u_N \in \bigcup _{m \geq 0}A^{-m}\mathbb {Z}^{d}$ satisfying $(u_1,\,\ldots,\,u_N) \in \mathcal {V}_w$ is a dense set, and this clearly suffices to prove the lemma.

Since $\bigcup _{m \geq 0}A^{-m}\mathbb {Z}^{d}$ is dense in $\mathbb {R}^{d}$, it is sufficient for us to show that the set

\[ \mathcal{G}:=\bigg\{v \in \mathbb{R}^{d} \colon e^{2\pi i \langle A^{n}v,w\rangle} + \sum_{j=1}^{N-1} e^{2\pi i \langle A^{n}u_j,w\rangle } \neq 0 \text{ for all }n \in \mathbb{Z}\bigg\} \]

is open and dense in $\mathbb {R}^{d}$. For every $n \in \mathbb {Z}$ define

\[ \mathcal{G}_n:=\bigg\{v \in \mathbb{R}^{d} \colon e^{2\pi i \langle A^{n}v,w\rangle} + \sum_{j=1}^{N-1} e^{2\pi i \langle A^{n}u_j,w\rangle}\neq 0\bigg\} \]

so that $\mathcal {G}=\bigcap _{n \in \mathbb {Z}} \mathcal {G}_n$. If $|\!\sum \nolimits _{j=1}^{N-1} e^{2\pi i \langle A^{n}u_j,w\rangle }|\neq 1$ then $\mathcal {G}_n$ is equal to $\mathbb {R}^{d}$; otherwise, the complement of $\mathcal {G}_n$ in $\mathbb {R}^{d}$ is the union of countably infinitely many evenly spaced, parallel hyperplanes in $\mathbb {R}^{d}$, each being a translated copy of the orthogonal complement of $(A^{\top })^{n}w$. In either case, $\mathcal {G}_n$ is easily seen to be open and dense in $\mathbb {R}^{d}$. Moreover, if the second case occurs only for finitely many $n \in \mathbb {Z}$ then $\mathcal {G}$ is equal to the intersection of finitely many open and dense subsets of $\mathbb {R}^{d}$ and hence will be open and dense. But, it is indeed the case that $|\sum \nolimits _{j=1}^{N-1} e^{2\pi i \langle A^{n}u_j,w\rangle }|= 1$ for at most finitely many $n$. To see this, we observe that on the one hand, for all sufficiently large positive $n$, we have $A^{n}u_j \in \mathbb {Z}^{d}$ for every ${j=1,\,\ldots,\,N-1}$. For all such $n$ we clearly have $e^{2\pi i \langle A^{n}u_j,w\rangle }=1$ for every $j=1,\,\ldots,\,N-1$ so that $|\sum \nolimits _{j=1}^{N-1} e^{2\pi i \langle A^{n}u_j,w\rangle }|=N-1>1$. On the other hand, since $\lim _{k\to -\infty } A^{-k}u_j=0$ for every $j=1,\,\ldots,\,N-1$ we also have $\lim _{n \to -\infty } |\sum \nolimits _{j=1}^{N-1} e^{2\pi i \langle A^{n}u_j,w\rangle }|=N-1>1$. We conclude that $|\sum \nolimits _{j=1}^{N-1} e^{2\pi i \langle A^{n}u_j,w\rangle }|$ can equal $1$ for at most finitely many $n$, so $\mathcal {G}$ is indeed equal to the intersection of a finite collection of open, dense subsets of $\mathbb {R}^{d}$ and is therefore open and dense as needed. The result follows.

The following result now completes the proof of Theorem 1.

Proof. Fix a non-zero vector $w \in \mathbb {Z}^{d}$ and a tuple $(u_1,\,\ldots,\,u_N) \in \mathcal {V}_w$ throughout the proof, and let $(T_1,\,\ldots,\,T_N)$ be the associated iterated function system and $\nu$ the associated measure. We define the Fourier transform of $\nu$ by $\hat \nu (\xi ):=\int _{\mathbb {R}^{d}} e^{i \langle x,\xi \rangle } d\nu (x)$ for every $\xi \in \mathbb {R}^{d}$. We will show that the limit $\lim _{r \to \infty } \hat \nu (2\pi (A^{\top })^{r})$ exists and is non-zero, which by the Riemann–Lebesgue lemma implies that $\nu$ is not absolutely continuous with respect to Lebesgue measure. By Proposition 2.1, it will then follow that $\nu$ issingular.

We first claim that the infinite product

\[ \prod_{n={-}\infty}^{\infty} \bigg(\frac{1}{N}\sum_{j=1}^{N} e^{2\pi i \langle A^{{-}n} u_j,w\rangle}\bigg) \]

is absolutely convergent and non-zero. Since $(u_1,\,\ldots,\,u_N) \in \mathcal {V}_w$, it is true by definition that every term in the product is non-zero. Since $A^{m} u_j \in \mathbb {Z}^{d}$ for all sufficiently large positive integers $m$, the terms in the product are also identically equal to $1$ for all large enough negative integers $n$. On the other hand, we clearly have $\max _j |e^{2\pi i \langle A^{-n} u_j,\,w\rangle }-1|=O(\|A^{-n}\|)$ as $n \to +\infty$ by Lipschitz continuity. By Gelfand's formula, the latter expression converges exponentially to zero as $n \to +\infty$ and this suffices to demonstrate the absolute convergence of the product. The claim isproved.

We next derive a formula for $\hat \nu (2\pi (A^{\top })^{r}w)$ for each $r \geq 1$. If $\xi \in \mathbb {R}^{d}$ is arbitrary then using the self-similarity relation for $\nu$,

\begin{align*} \hat\nu(\xi) & = \displaystyle\int_{\mathbb{R}^{d}} e^{i \langle x,\xi \rangle} d\nu(x) \\ & =\displaystyle\int_{\mathbb{R}^{d}}e^{i\langle x,\xi\rangle } d\bigg(\displaystyle\frac{1}{N}\displaystyle\sum_{j=1}^{N} (T_j)_*\nu\bigg)(x)\\ & =\frac{1}{N}\sum_{j=1}^{N} \int_{\mathbb{R}^{d}} e^{i\langle T_j x,\xi\rangle} d\nu(x)\\ & =\frac{1}{N}\sum_{j=1}^{N} \int_{\mathbb{R}^{d}}e^{i \langle A^{{-}1}x+u_j,\xi\rangle} d\nu(x)\\ & =\frac{1}{N}\sum_{j=1}^{N} e^{i \langle u_j, \xi\rangle}\int_{\mathbb{R}^{d}} e^{i\langle x,(A^{\top})^{{-}1}\xi\rangle} d\nu(x)=\frac{1}{N}\sum_{j=1}^{N} e^{i \langle u_j, \xi\rangle} \hat\nu((A^{\top})^{{-}1}\xi). \end{align*}

Iterating this relation $m$ times yields the formula

\[ \hat\nu(\xi)= \prod_{n=0}^{m-1} \bigg(\frac{1}{N} \sum_{j=1}^{N} e^{i \langle A^{{-}n}u_j,\xi\rangle} \bigg)\hat\nu\left((A^{\top})^{{-}m}\xi\right) \]

valid for all $m\in \mathbb {N}$ and $\xi \in \mathbb {R}^{d}$. Since $\hat \nu$ is continuous and satisfies $\hat \nu (0)=1$, we deduce that for every integer $r \geq 0$

\begin{align*} \hat\nu(2\pi (A^{\top})^{r}w)& = \lim_{m \to \infty} \prod_{n=0}^{m-1} \bigg(\displaystyle\frac{1}{N} \displaystyle\sum_{j=1}^{N} e^{2\pi i \langle A^{r-n}u_j,w\rangle}\bigg)\hat\nu(2\pi (A^{\top})^{r-m}w)\\ & = \prod_{n=0}^{\infty}\bigg(\frac{1}{N} \sum_{j=1}^{N} e^{2\pi i \langle A^{r-n}u_j,w\rangle}\bigg)= \prod_{n={-}r}^{\infty}\bigg(\frac{1}{N} \sum_{j=1}^{N} e^{2\pi i \langle A^{{-}n}u_j,w\rangle}\bigg) \end{align*}

and therefore

\[ \lim_{r \to \infty}\hat\nu\left(2\pi \left(A^{\top}\right)^{r}w\right) = \prod_{n={-}\infty}^{\infty}\bigg(\frac{1}{N} \sum_{j=1}^{N} e^{2\pi i \langle A^{{-}n}u_j,w\rangle} \bigg) \]

which is well defined and non-zero by our previous claim. Since $\|(A^{\top })^{r}w\| \to \infty$ as $r \to \infty$ it follows by the Riemann–Lebesgue lemma that $\nu$ is not absolutely continuous and the proof of the lemma is complete.