# Second Order Ergodic Theorem for Self-Similar Tiling Systems

Konstantin Medynets  Konstantin Medynets, Department of Mathematics, U.S.
Naval Academy, Annapolis, MA 21402, USA<EMAIL_ADDRESS>and  Boris Solomyak
Boris Solomyak, Department of Mathematics, University of Washington, Seattle,
WA 98195-4350, USA<EMAIL_ADDRESS>
###### Abstract.

We consider infinite measure-preserving non-primitive self-similar tiling
systems in Euclidean space $\mathbb{R}^{d}$. We establish the second-order
ergodic theorem for such systems, with exponent equal to the Hausdorff
dimension of a graph-directed self-similar set associated with the
substitution rule.

B. S. is supported in part by NSF grant DMS-0968879.

##  1\. Introduction

Let $\mathbb{X}=(X,\mu,\mathbb{T})$ be a conservative, ergodic, measure
preserving dynamical system on a $\sigma$-finite measure space. If $f\in
L^{1}(X,\mu)$, then Hopf’s ratio ergodic theorem says that the growth of
$S_{n}f(x)=f(x)+\cdots+f(T^{n-1}x)$ is independent of $f$ in the sense that if
$g\in L^{1}(X,\mu)$ with $\int g\,d\mu\neq 0$, then

$\frac{S_{n}f(x)}{S_{n}g(x)}\to\frac{\int f\,d\mu}{\int g\,d\mu}\mbox{ for
}\mu\mbox{-a.e. }x\in X.$

It turns out that due to the measure $\mu$ being infinite, it is impossible to
replace functions $S_{n}g(x)$ by constants $\\{a_{n}\\}$ [A, Theorem 2.4.2].
However, it was observed earlier [Fi1, ADF, LS] that for some systems, the
ratios $S_{n}f(x)/a_{n}$ (for some choice of $a_{n}$) still converge to $\int
f\,d\mu$, though in a weaker sense (second-order averages). The asymptotic
behavior of the sequence $\\{a_{n}\\}$ is an invariant of the dynamical
system.

The main result of the present paper is the following ergodic theorem showing
that for self-similar tilings the sequence $\\{a_{n}\\}$ can be chosen as
$\\{n^{\alpha+1}\\}$ where $\alpha$ is an intrinsic parameter of the system
reflecting self-similarity (the precise statements, with all technical
assumptions, are Theorem 5.5 and Theorem 6.11).

######  Theorem 1.1.

(i) Let $\mathbb{X}=(\Omega,\mu,{{\mathbb{R}}}^{d})$ be a non-primitive self-
similar substitution tiling system preserving an infinite ergodic measure
$\mu$. Assume that the measure $\mu$ is non-zero and finite on some open
subset of $\Omega$. Then there exist positive parameters $\alpha$ and $c$ such
that for every function $f\in L^{1}(\Omega,\mu)$ and $\mu$-almost every tiling
$\mathcal{T}\in\Omega$, we have

(1.1)
$\lim\limits_{t\to\infty}\frac{1}{\log(t)}\int_{1}^{t}\frac{\int_{B_{R}}f(\mathcal{T}-u)\,du}{c(2R)^{\alpha}}\,\frac{dR}{R}=\int_{\Omega}fd\mu.$

Here $B_{R}$ is the ball of radius $R$ centered at the origin.

(ii) The parameters $\alpha$ and $c$ are invariants of the measure-theoretic
isomorphism of the system $\mathbb{X}$.

(iii) This result is also valid for a large class of one-dimensional symbolic
substitution systems with integrals in the left-hand side replaced by the
corresponding sums.

Our work was originally inspired by A. Fisher’s paper [Fi1], where he obtained
a similar ergodic theorem for a single substitution system $(X_{\sigma},S)$
generated by the map $\sigma(0)=000$ and $\sigma(1)=101$. Iterating the map
$\sigma^{n}(1)$, $n\geq 1$, we get a sequence where the appearances of 1’s and
0’s resemble the process of constructing the middle-thirds Cantor set. Fisher
used this analogy to show that for any function $f\in L^{1}(X_{\sigma},\mu)$
and $\mu$-a.e point $x\in X_{\sigma}$,

$\lim_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{\sum_{i=0}^{k-1}f(S^{i}x)}{ck^{\alpha}}\cdot\frac{1}{k}=\int_{X_{\sigma}}fd\mu,$

where $\mu$ is the unique $S$-invariant measure $\mu$ on $X_{\sigma}$ with
$\mu([1])=1$. Here $\alpha=\log(2)/\log(3)$ is the Hausdorff dimension and $c$
is the average density of the Hausdorff measure on the middle-thirds Cantor
set. Average densities were introduced by Bedford and Fisher [BF] (see
Definition 5.4). The middle-thirds Cantor set arising in the study of the
substitution $\sigma$ is a special case of the self-similar set (in general,
for a graph-directed iterated function system) that one can associate to every
self-similar tiling substitution (Section 3.1). In the proof of Theorem 1.1,
we show the parameters $\alpha$ and $c$ always arise as the Hausdorff
dimension and the appropriate average density of the Hausdorff measure of the
associated graph-directed sets.

It is well-known that primitive substitution dynamical systems (both symbolic
and tiling versions) are uniquely ergodic. Non-primitive substitutions and
their invariant measures have been recently studied in [Y, BKM, BKMS, HY],
where it was shown, in particular, that for a large class of non-primitive
symbolic substitutions infinite ($\sigma$-finite) invariant measures appear
naturally. This has also been extended to the tiling setting in [CS]. The
present work continues this line of research.

We observe that the second-order ergodic theorem is not a universal result.
Its validity depends on intrinsic properties of the dynamical system in
question. We refer the reader to the paper [ADF] of Aaronson-Denker-Fisher for
the discussion of second order ergodic theorems for Markov shifts. We also
mention the paper [LS] of Ledrappier and Sarig establishing the second order
ergodic theorem for certain horocycle flows.

The basic idea of the proof of Theorem 1.1 has roots in the work of Bedford
and Fisher [BF]. In a nutshell, it follows from the Birkhoff ergodic theorem
for the renormalization, or “scaling” map, associated with the substitution,
restricted to a certain fractal subset of the tiling space. The negative part
(going into the past) of this renormalization map turns out to be essentially
the time-1 map of the scenery flow arising from “zooming in” into the fractal.

The structure of the paper is the following. In Section 2 we give the
definition of the substitution tiling system $(\Omega,{{\mathbb{R}}}^{d})$
generated by a tile substitution $\mathcal{G}$. We then recall the
classification of infinite ergodic invariant measures established in [CS]. In
subsection 2.3 we explicitly state technical assumptions on the tiling system
needed for Theorem 1.1.

In Section 3 we show how to associate a graph-directed set to the substitution
rule $\mathcal{G}$. In the following sections we use this fractal to count
frequencies of prototiles in tilings of $\Omega$.

In Section 4, we show that the transverse dynamical system (generated by
iterations of the substitution rule) is measure-theoretically isomorphic to a
Markov chain.

Sections 5 and 6 are devoted to the proof of Theorem 1.1. As a corollary, we
establish that almost every sequence from a substitution space admits a non-
zero “$\alpha$-dimensional frequency,” where the parameter $\alpha$ comes from
Theorem 1.1. Section 7 contains a few examples and open questions.

##  2\. Tiling Dynamical Systems

In this section we fix our notation and present necessary definitions from
tiling dynamics. We mostly follow conventions of [CS], see also [Ro].

###  2.1. Tiling Space

Fix a finite alphabet $\mathcal{W}$ and an integer $d\geq 1$. By a tile in
$\mathbb{R}^{d}$ we mean a pair $T=(F,i)$ of a compact set $F$ that is the
closure of its interior, and a letter (label) $i\in\mathcal{W}$. Two
geometrically identical sets labeled by different letters are treated as
distinct tiles. The set $F$ will be called the support of the tile $T$, in
symbols, $\textrm{supp}(T)=F$. A tiling is a family of tiles $\mathcal{T}$
such that $\mathbb{R}^{d}=\cup\\{\textrm{supp}(T):T\in\mathcal{T}\\}$ and
distinct tiles have disjoint interiors. A patch is a finite set of tiles with
disjoint interiors. The support of a patch $P$ is the set
$\textrm{supp}(P)=\cup\\{\textrm{supp}(T):T\in P\\}$. If $\mathcal{T}$ is a
tiling, its finite subsets are called $\mathcal{T}$-patches.

The translate of a tile $T=(F,i)$ by a vector $u\in\mathbb{R}^{d}$ is the tile
$T+u=(F+u,i)$. Similarly, a translate of a patch $P$ by $u\in\mathbb{R}^{d}$
is the patch $P+u=\\{T+u:T\in P\\}$. We say that two patches $P_{1}$ and
$P_{2}$ are translationally equivalent if $P_{1}=P_{2}+u$ for some vector
$u\in\mathbb{R}^{d}$.

######  Definition 2.1.

Let $\mathcal{A}$ be a finite set of tiles in $\mathbb{R}^{d}$ such that
distinct tiles from $\mathcal{A}$ are not translationally equivalent. Tiles
from the set $\mathcal{A}$ are called prototiles. We will call translations of
prototiles $\mathcal{A}$-tiles.

Denote by $\mathcal{A}^{+}$ the set of patches made of translates of tiles
from $\mathcal{A}$. We assume that every prototile $T\in\mathcal{A}$ is
centered at the origin, in the sense that $\textbf{0}\in{\rm
int}(\textrm{supp}(T))$.

Let $\varphi$ be an expanding linear transformation in ${{\mathbb{R}}}^{d}$. A
map $\mathcal{G}:\mathcal{A}\rightarrow\mathcal{A}^{+}$ is called a tile
substitution with expansion $\varphi$ if

(2.1) $\textrm{supp}(\mathcal{G}(T))=\varphi(\textrm{supp}(T))\mbox{ for every
tile }T\in\mathcal{A}.$

In other words, the substitution $\mathcal{G}$ shows how to subdivide the
inflated tile $\varphi(\textrm{supp}(T))$ into translates of prototiles. The
tile substitution can be written explicitly as follows:

(2.2) ${\mathcal{G}}(T)=\bigcup_{T^{\prime}\in{\mathcal{A}}}\\{T^{\prime}+u:\
u\in{\mathcal{D}}_{T,T^{\prime}}\\}\ \ \mbox{for all}\ \ T\in{\mathcal{A}},$

where ${\mathcal{D}}_{T,T^{\prime}}$ is a finite (possibly empty) subset of
${{\mathbb{R}}}^{d}$, the tiles in the right-hand side have disjoint
interiors, and

(2.3) $\varphi({\rm
supp}(T))=\bigcup_{T^{\prime}\in{\mathcal{A}}}\bigcup_{u\in{\mathcal{D}}_{T,T^{\prime}}}({\rm
supp}(T^{\prime})+u).$

The substitution $\mathcal{G}$ is extended to translates of prototiles by
$\mathcal{G}(T+u)=\mathcal{G}(T)+\varphi(u)$; and to patches by
$\mathcal{G}(P)=\cup\\{\mathcal{G}(T):T\in P\\}$. The linearity of $\varphi$
and the equation (2.1) imply that the patch $\mathcal{G}(P)$ is well-defined.

######  Remark 2.2.

In this paper we restrict ourselves to the self-similar case, i.e.
$\varphi=\lambda\cdot O$, where $O$ is an orthogonal matrix and $\lambda>1$.
We refer to the corresponding ${\mathcal{G}}$ as self-similar tiling
substitution. The more general case of an arbitrary expansion map $\varphi$,
referred to as self-affine, is not covered by our main results.

######  Definition 2.3.

For a given tiling substitution
$\mathcal{G}:\mathcal{A}\rightarrow\mathcal{A}^{+}$, let
$M_{\mathcal{G}}=(m_{A,B})_{A,B\in\mathcal{A}}$ be the matrix with $m_{A,B}$
being the number of translates of the prototile $A$ in the patch
$\mathcal{G}(B)$ (i.e. $m_{A,B}=\\#{\mathcal{D}}_{A,B}$). The matrix
$M_{\mathcal{G}}$ is called the substitution matrix of $\mathcal{G}$.

The substitution is called primitive if some power of the substitution matrix
has only positive entries. We emphasize that our focus is on the non-primitive
case.

The following example will help illustrate the concepts as we go along. We
call it the integer Sierpiński carpet tiling substitution, by analogy with A.
Fisher’s integer Cantor set substitution [Fi1].

######  Example 2.4.

Suppose that the prototile set $\mathcal{A}$ consists of two $1\times 1$
squares on the plane labeled by $0$ and $1$ (we will call them the “0-tile”
and “1-tile”). Consider the following tile substitution ${\mathcal{G}}$:

$\begin{array}[]{|c|}\hline\cr 0\\\
\hline\cr\end{array}\mapsto\begin{array}[]{|c|c|c|}\hline\cr 0&0&0\\\
\hline\cr 0&0&0\\\ \hline\cr 0&0&0\\\ \hline\cr\end{array}\qquad\mbox{ and
}\qquad\begin{array}[]{|c|}\hline\cr 1\\\
\hline\cr\end{array}\mapsto\begin{array}[]{|c|c|c|}\hline\cr 1&1&1\\\
\hline\cr 1&0&1\\\ \hline\cr 1&1&1\\\ \hline\cr\end{array}$

The expansion map is a dilation: $\varphi=3I$. The substitution matrix
$M_{\mathcal{G}}=\left(\begin{array}[]{cc}9&1\\\ 0&8\end{array}\right)$ is
non-primitive.

######  Definition 2.5.

Let $\mathcal{G}:\mathcal{A}\rightarrow\mathcal{A}^{+}$ be a tile
substitution. Denote by $\Omega_{\mathcal{G}}$ the set of all tilings of
$\mathbb{R}^{d}$ by tiles from $\mathcal{A}$ such that
$\mathcal{T}\in\Omega_{\mathcal{G}}$ if every $\mathcal{T}$-patch is a
subpatch of $\mathcal{G}^{n}(T)+u$ for some $T\in\mathcal{A}$,
$u\in\mathbb{R}^{d}$, and $n\geq 1$. The set $\Omega_{\mathcal{G}}$ is called
the tiling space corresponding to the substitution $\mathcal{G}$. The group
$\mathbb{R}^{d}$ has a natural translation action on $\Omega_{\mathcal{G}}$
given by $u:\mathcal{T}\mapsto\mathcal{T}-u$ for every $u\in\mathbb{R}^{d}$
and $\mathcal{T}\in\Omega_{\mathcal{G}}$. The pair
$(\Omega_{\mathcal{G}},\mathbb{R}^{d})$ is called a substitution tiling
system.

Let $\|\cdot\|$ be the Euclidean norm on $\mathbb{R}^{d}$. For
$x\in\mathbb{R}^{d}$ and $R>0$, set
$B_{R}(x)=\\{u\in\mathbb{R}^{d}:\,\|u-x\|\leq R\\}$. We will write $B_{R}$ for
$B_{R}(\textbf{0})$. For a compact set $K$ and a tiling $\mathcal{T}$, denote
by $\mathcal{T}[[K]]$ the set of all $\mathcal{T}$-patches $P$ with
$K\subset\textrm{supp}(P)$. Define a metric $\rho$ on the space
$\Omega_{\mathcal{G}}$ as follows. Given tilings
$\mathcal{T}^{\prime},\mathcal{T}^{\prime\prime}\in\Omega_{\mathcal{G}}$, let
$\rho(\mathcal{T}^{\prime},\mathcal{T}^{\prime\prime})$ be the minimum of
$2^{-1/2}$ and

$\inf\limits\\{r>0:\exists g\in
B_{r},P^{\prime}\in\mathcal{T}^{\prime}[[B_{1/r}]],P^{\prime\prime}\in\mathcal{T}^{\prime\prime}[[B_{1/r}]]\mbox{
such that }P^{\prime}-g=P^{\prime\prime}\\}.$

With respect to the topology generated by $\rho$, two tilings are close to
each other if they agree on a large ball around the origin after a small
translation. The cut-off parameter $2^{-1/2}$ is needed to fulfill the
triangle inequality.

######  Definition 2.6.

(1) We say that the tiling system $\Omega_{\mathcal{G}}$ has finite local
complexity (FLC) if for every tiling $\mathcal{T}\in\Omega_{\mathcal{G}}$ and
$R>0$, there are only finitely many $\mathcal{T}$-patches of diameter less
than $R$ up to translation equivalence. (Note that finite pattern condition
and translational finiteness are sometimes used in the literature synonymously
with FLC).

(2) The tiling substitution $\mathcal{G}$ is called admissible if for every
prototile $T\in\mathcal{A}$ there exists a tile
$\mathcal{T}\in\Omega_{\mathcal{G}}$ such that $T\in\mathcal{T}$.

It is not always trivial to verify these conditions. Of course,
$\Omega_{\mathcal{G}}$ in Example 2.4 has FLC. Less obvious examples of FLC
tile substitutions (with tiles having fractal boundary) are considered e.g. in
[K2, So1], and two of them are discussed in Section 7. There exist primitive
tile substitution systems that do not have the FLC property, see [K1, p.244]
and [D, FR] (the latter ones have polygonal tiles).

Next let us verify that the tiling substitution in Example 2.4 is admissible.
If we put a 1-tile on the plane so that one of its corners is at the origin
and start iterating the substitution, we will obtain an increasing sequence of
patches which agree with each other and tend to a tiling of a quarter-plane.
Since the second iterate
${\mathcal{G}}^{2}\left(\,\begin{array}[]{|c|}\hline\cr 1\\\
\hline\cr\end{array}\,\right)$ contains a patch of the form
$\begin{array}[]{|c|c|}\hline\cr 1&1\\\ \hline\cr 1&1\\\ \hline\cr\end{array}$
, we can start with this “seed” centered at the origin and obtain a tiling of
the entire plane, which is the union of the four quarter-plane tilings. This
tiling is then in $\Omega_{\mathcal{G}}$, which confirms admissibility.

The FLC assumption implies the following result. The proof can be found, for
example, in [RW, Lemma 2].

######  Proposition 2.7.

If the tiling system has the FLC property, then the set $\Omega_{\mathcal{G}}$
is compact with respect to the topology generated by the metric $\rho$. The
action of the group $\mathbb{R}^{d}$ by translations on $\Omega_{\mathcal{G}}$
is continuous.

Along with the translation ${{\mathbb{R}}}^{d}$-action, we have the
substitution action on $\Omega_{\mathcal{G}}$, which is denoted by the same
letter ${\mathcal{G}}:\,\Omega_{\mathcal{G}}\to\Omega_{\mathcal{G}}$. These
two dynamical systems are intertwined by the relation

(2.4)
${\mathcal{G}}({\mathcal{T}}-y)={\mathcal{G}}({\mathcal{T}})-\varphi(y),\
{\mathcal{T}}\in\Omega_{\mathcal{G}},\ y\in{{\mathbb{R}}}^{d}.$

The following result shows that any tiling in $\Omega_{\mathcal{G}}$ has a
preimage under the map $\mathcal{G}$, see [CS, Lemma 2.8].

######  Proposition 2.8.

If $\mathcal{G}$ is admissible, then the map
$\mathcal{G}:\Omega_{\mathcal{G}}\rightarrow\Omega_{\mathcal{G}}$ is a
continuous surjection.

In fact, this is almost immediate. To find a pre-image of
${\mathcal{T}}\in\Omega_{\mathcal{G}}$ under ${\mathcal{G}}$ one needs to
“compose” or “combine” its tiles into patches that are translates of
substituted prototiles (i.e. ${\mathcal{G}}(T),\ T\in{\mathcal{A}}$), so that
the resulting tiling, after rescaling by $\varphi^{-1}$, belongs to
$\Omega_{\mathcal{G}}$. This is always possible locally, by the definition of
$\Omega_{\mathcal{G}}$ (Definition 2.5), and one only has take a subsequential
limit.

One of the important issues in the theory of substitutions is to understand
when the map $\mathcal{G}$ is invertible. This property is sometimes referred
to as recognizability or unique composition. In fact,
${\mathcal{T}}\in\Omega_{\mathcal{G}}$ has a unique pre-image under
${\mathcal{G}}$ whenever the “composition” described above is unique. Global
invertibility of ${\mathcal{G}}$ is equivalent to non-periodicity of the
tiling space for primitive tile substitutions [So2], but the extension to the
non-primitive case is by no means trivial.

######  Definition 2.9.

A tiling $\mathcal{T}\in\Omega_{\mathcal{G}}$ is periodic if there is a non-
zero vector $u\in\mathbb{R}^{d}$ such that $\mathcal{T}=\mathcal{T}+u$. Such a
vector $u$ is called a period of ${\mathcal{T}}$. A tile substitution
$\mathcal{G}$ is called non-periodic if the set $\Omega_{\mathcal{G}}$ has no
periodic tilings.

The set of periods of a tiling in ${{\mathbb{R}}}^{d}$ is a subgroup of
${{\mathbb{R}}}^{d}$. Periodic tilings can be further classified according to
the rank of the group of periods, but this will not concern us in this paper.
A classical argument shows that ${\mathcal{G}}$ cannot be invertible if the
tiling space contains a periodic tiling. Indeed, if
${\mathcal{G}}({\mathcal{S}})={\mathcal{T}}$ and
${\mathcal{T}}={\mathcal{T}}+u$, then
${\mathcal{G}}({\mathcal{S}})={\mathcal{G}}({\mathcal{S}}+\varphi^{-1}u)={\mathcal{T}}$
by (2.4). If ${\mathcal{S}}={\mathcal{S}}+\varphi^{-1}u$, we can repeat this,
obtaining shorter and shorter periods. However, this cannot go on
indefinitely, since the period of a tiling cannot be shorter than the diameter
of the largest ball which is contained in the interior of all the prototiles.

Next we discuss minimal components of our tiling dynamical systems. Recall
that a dynamical system is minimal if it has no proper closed invariant
subsets. It is well-known that tiling dynamical systems arising from primitive
substitutions are minimal (see e.g. [Ro]).

######  Definition 2.10.

A minimal component of the system $(\Omega_{\mathcal{G}},\mathbb{R}^{d})$ is a
closed $\mathbb{R}^{d}$-invariant set that contains no proper closed invariant
subsets. We note that if a minimal component $\Omega$ contains a tiling with
period $u\in\mathbb{R}^{d}$, then every tiling of $\Omega$ has the period $u$.

An easy consequence of Proposition 2.8 is that
$\Omega_{{\mathcal{G}}}=\Omega_{{\mathcal{G}}^{k}}$ for any $k\in{\mathbb{N}}$
(see [CS, Lemma 2.9]), hence one can replace the tiling substitution with its
power, whenever convenient. Reordering the letters in the alphabet
$\mathcal{A}$ and replacing $\mathcal{G}$ with its higher power
$\mathcal{G}^{k}$ if needed, the substitution matrix can be reduced to the
following form:

(2.5)
$M_{\mathcal{G}}=\left(\begin{array}[]{ccccccc}F_{1}&0&\cdots&0&X_{1,s+1}&\cdots&X_{1,m}\\\
0&F_{2}&\cdots&0&X_{2,s+1}&\cdots&X_{2,m}\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\cdots&\vdots\\\
0&0&\cdots&F_{s}&X_{s,s+1}&\cdots&X_{s,m}\\\
0&0&\cdots&0&F_{s+1}&\cdots&X_{s+1,m}\\\
\vdots&\vdots&\cdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&0&0&\cdots&F_{m}\end{array}\right)$

The square matrices $F_{i}$ on the main diagonal are either zero matrices or
contain only strictly positive entries. For any fixed $j=s+1,...,m$, at least
one of the matrices $X_{k,j}$ is non-zero. The block-triangular form (2.5)
allows us to give an effective description of minimal components of the
system.

For each $i=1,\ldots,m$, denote by $\mathcal{A}_{i}$ the set of prototiles
corresponding to the block $F_{i}$. Denote by $\Omega_{i}$ the set of tilings
$\mathcal{T}\in\Omega_{\mathcal{G}}$ whose patches are subpatches of
$\mathcal{G}^{n}(T)$, $n\geq 0$, with $T\in\mathcal{A}_{i}$. For $i\leq s$ it
follows from the structure of $M_{\mathcal{G}}$ that
${\mathcal{G}}({\mathcal{A}}_{i})\subset{\mathcal{A}}_{i}^{+}$, and then
$\Omega_{i}$ is just the substitution tiling system for the restriction of
${\mathcal{G}}$ to ${\mathcal{A}}_{i}$. Since $F_{i}$ is strictly positive for
$i\leq s$, we see that $(\Omega_{i},{{\mathbb{R}}}^{d})$ is minimal. It is not
hard to show ([CS, Lemma 2.10]) that the sets
$\\{\Omega_{1},\ldots,\Omega_{s}\\}$ are the only minimal components of the
tiling system.

In Example 2.4, the unique minimal component consists of the tilings with
0-tiles only. It is, of course, periodic, with the lattice ${\mathbb{Z}}^{2}$
being the group of periods, so it is topologically conjugate to the
translation action on the 2-torus ${{\mathbb{R}}}^{2}/{\mathbb{Z}}^{2}$.

Next we state a sufficient condition for the invertibility of the map
$\mathcal{G}$, following [CS], for which we need another definition.

######  Definition 2.11.

(1) Denote by $\mathcal{A}_{\textrm{per}}$ the set of all tiles
$T\in\mathcal{A}$ that occur in periodic tilings from minimal components. Set
$\mathcal{A}_{\textrm{nonp}}=\mathcal{A}\setminus\mathcal{A}_{\textrm{per}}$.
We emphasize that prototiles which do not appear in minimal components belong
to $\mathcal{A}_{\textrm{nonp}}$ by default.

(2) A substitution $\mathcal{G}$ is said to satisfy the non-periodic border
condition (NBC) if for every tile $T\in\mathcal{A}_{\textrm{nonp}}$, the
$\mathbb{R}^{d}$-boundary of the patch $\mathcal{G}(T)$ is contained in the
union of $\mathcal{A}_{\textrm{nonp}}$-tiles of $\mathcal{G}(T)$ (or rather,
their boundaries).

For the proof of the following result see [CS, Theorem 4.1 and 4.4].

######  Theorem 2.12.

(1) If the dynamical system $(\Omega_{\mathcal{G}},\mathbb{R}^{d})$ has no
periodic tilings, then the substitution
$\mathcal{G}:\Omega_{\mathcal{G}}\rightarrow\Omega_{\mathcal{G}}$ is a
homeomorphism.

(2) Assume that a substitution $\mathcal{G}$ satisfies the non-periodic border
condition. Then for every tiling $\mathcal{T}\in\Omega_{\mathcal{G}}$ that
contains a tile from $\mathcal{A}_{\textrm{nonp}}$ there exists a unique
tiling $\mathcal{T}^{\prime}$ such that
$\mathcal{G}(\mathcal{T}^{\prime})={\mathcal{T}}$.

######  Remark 2.13.

It is conjectured in [CS, Section 4] that the NBC condition may be dropped in
part (2) of the theorem, that is, ${\mathcal{G}}$ is always invertible on the
set of non-periodic tilings. It is clear that NBC is satisfied in Example 2.4.
For specific examples, even those which fail the NBC, invertibility of
${\mathcal{G}}$ on non-periodic tilings can sometimes be verified by
inspection, by observing that the “composition,” discussed after Proposition
2.8, is unique. In view of Theorem 2.12, for tiling systems with NBC, periodic
tilings can only exist in minimal components. [CS, Example 4.6] shows that the
latter property may fail without the NBC.

###  2.2. Invariant Measures

######  Definition 2.14.

(1) A measure $\mu$ on $\Omega_{\mathcal{G}}$ is called invariant if
$\mu(U-u)=\mu(U)$ for every $u\in\mathbb{R}^{d}$ and every Borel set
$U\subset\Omega_{\mathcal{G}}$. An invariant measure $\mu$ is called ergodic
if whenever a Borel set $X$ is translation-invariant, i.e. $X-u=X$ for every
$u\in\mathbb{R}^{d}$, either $\mu(X)=0$ or $\mu(\Omega_{\mathcal{G}}\setminus
X)=0$.

(2) By the transversal of $\Omega_{\mathcal{G}}$ we mean the family of all
tilings $\mathcal{T}\in\Omega_{\mathcal{G}}$ such that one of the
$\mathcal{T}$-tiles is exactly a prototile from $\mathcal{A}$. Recall that
each prototile contains the origin in the interior of its support. Throughout
the paper, the transversal will be denoted by
$\Gamma\subset\Omega_{\mathcal{G}}$.

(3) A transverse measure is a Borel measure $\nu$ on $\Gamma$ such that
$\nu(U)=\nu(U-u)$ for every Borel subset $U\subset\Gamma$ and
$u\in\mathbb{R}^{d}$ for which $U-u\subset\Gamma$.

######  Proposition 2.15.

There is a one-to-one correspondence between finite (resp. $\sigma$-finite)
transverse measures and finite (resp. $\sigma$-finite) invariant measures [CS,
Section 7].

Consider the transversal $\Gamma$. For a prototile $T\in\mathcal{A}$, set

$\Gamma_{T}=\\{\mathcal{T}\in\Gamma:\,T\in\mathcal{T}\\}.$

Then $\Gamma=\coprod_{T\in\mathcal{A}}\Gamma_{T}$ is a disjoint union. The
following result provides a description of “natural” $\sigma$-finite ergodic
measures, for the proof see Theorems 3.1 and 5.22 in [CS].

######  Theorem 2.16.

(i) Each finite ergodic measure is supported by one of the minimal components
$\\{\Omega_{1},\ldots,\Omega_{s}\\}$.

(ii) Let $i\in\\{s+1,\ldots,m\\}$ be such that the matrix $F_{i}$ is nonzero
and there exist $A\in\mathcal{A}_{i}$ and $n>0$ such that a translate of $A$
appears in the interior of $\mathcal{G}^{n}(A)$. Then there exists a unique
(up to scaling) invariant ergodic $\sigma$-finite measure $\mu$ supported by
$\Omega_{i}$ such that $0<\mu^{\rm tr}(\Gamma_{C})<\infty$ for some (and, in
fact, for all) prototile $C\in\mathcal{A}_{i}$, where $\mu^{\rm tr}$ is the
transverse measure corresponding to $\mu$. Moreover, the vector $(\mu^{\rm
tr}(\Gamma_{C}))_{C\in{\mathcal{A}}_{i}}$ is a right Perron-Frobenius
eigenvector of $F_{i}$.

######  Remark 2.17.

Denote by ${\mathcal{L}}^{d}$ the Lebesgue measure on ${{\mathbb{R}}}^{d}$.
Observe that the substitution matrix $M_{\mathcal{G}}$ has a strictly positive
left eigenvector $({\mathcal{L}}^{d}({\rm supp}(T)))_{T\in{\mathcal{A}}}$,
corresponding to the eigenvalue $\lambda=\rho(A)$. This follows from (2.1) and
the fact that the tile boundaries have zero $d$-dimensional Lebesgue measure.
(The latter is proved e.g. in [P, Prop. 1.2] by B. Praggastis; she does not
assume primitivity there.) Note also that $\rho(A_{i})=\lambda$ for $i\leq s$
and $\rho(A_{i})<\lambda$ for $i=s+1,\ldots,m$. The latter inequality follows
from the existence of strictly positive left eigenvector, see [G, Theorem
III.6].

In view of Theorem 2.16, the study of ergodic measures can be reduced to the
study of the dynamics on one of the sets $\Omega_{i}$. In fact, we can simply
restrict the substitution to the subset of prototiles
$\bigcup_{j=1}^{i}{\mathcal{A}}_{j}$; the substitution matrix will then be
obtained by truncating the matrix in (2.5) so that the diagonal block $F_{i}$
will be in the lower-right corner. This implies that it is enough to consider
substitution tiling systems whose incidence matrices have the following form:

(2.6) $M_{\mathcal{G}}=\left(\begin{array}[]{cc}A&C\\\ 0&B\end{array}\right),$

where $A$ and $B$ are square matrices; $B$ is a primitive matrix; $C$ and $A$
are non-zero matrices. Note that $B$ is uniquely determined (it will be
$F_{i}$ when we consider $\Omega_{i}$); the matrix $A$ does not have to be
primitive and may contain zero diagonal blocks. In view of the discussion
above, we will always have $\rho(B)<\rho(A)$. Note that $B=[8]$, a $1\times 1$
matrix, in Example 2.4.

###  2.3. Technical Assumptions

Here we summarize the assumptions we will be implicitly imposing on the tiling
systems in question. Throughout the paper, the symbols $\mathcal{G}$ and
$\varphi(x)=\lambda\cdot O(x)$, $\Omega_{\mathcal{G}}$ will be reserved for a
self-similar tile substitution, the associated expansion map, and the tiling
space, respectively. The set of prototiles corresponding to the matrix $B$
will be denoted by $\mathcal{B}$. Furthermore, we will always assume that the
tiling substitution $\mathcal{G}:\mathcal{A}\rightarrow\mathcal{A}^{+}$
satisfies the following conditions:

  1. (1)

Every prototile is a compact subset of $\mathbb{R}^{d}$ that is the closure of
its interior. Note that this implies that the Hausdorff dimension of the
boundary of every prototile is at least $d-1$, see, for example, Corollary
IV.2 and Theorem VII.3 in [HuW].

  2. (2)

The tiling system $\Omega_{\mathcal{G}}$ has finite local complexity.

  3. (3)

The tile substitution $\mathcal{G}$ is admissible.

  4. (4)

The substitution $\mathcal{G}$ satisfies NBC: the non-periodic border
condition (see Definition 2.11).

  5. (5)

The substitution matrix $M_{\mathcal{G}}$ has the form (2.6), with $C$ non-
zero, $B$ primitive, $\rho(B)>1$.

  6. (6)

We have $\alpha:=\log(\rho(B))/\log(\lambda)>d-1$. The meaning of $\alpha$
will be clarified in Section 3.1.

######  Remark 2.18.

1\. The admissibility assumption implies that for every prototile
$T\in\mathcal{B}$ there is $n>0$ such that a translate of $T$ occurs in the
interior of $\mathcal{G}^{n}(T)$.

2\. One can show that if the ${{\mathbb{R}}}^{d}$-boundary of the patches
${\mathcal{G}}(T)$, for $T\in\mathcal{B}$, is contained in the union of
$\mathcal{B}$-tiles of ${\mathcal{G}}(T)$ (this implies NBC), then condition
(6) above also holds. We leave this as an exercise.

We summarize dynamical properties of tiling systems, which follow from our
assumptions.

######  Proposition 2.19.

The space $\Omega_{\mathcal{G}}$ is compact. The map
$\mathcal{G}:\Omega_{\mathcal{G}}\rightarrow\Omega_{\mathcal{G}}$ is a
continuous surjection that is invertible on non-periodic tilings. The
dynamical system $(\Omega_{\mathcal{G}},\mathbb{R}^{d})$ has a unique (up to
scaling) infinite $\sigma$-finite measure $\mu$ such that the corresponding
transverse measure is positive and finite on one (equivalently on all) of the
sets $\Gamma_{T}$, $T\in\mathcal{B}$.

###  2.4.  Hierarchical Structure

For each $k\in{\mathbb{Z}}$, define prototiles of order $k$ as
$\varphi^{k}(T)=((\varphi^{k}({\rm supp}(T)),i)$, where $T\in{\mathcal{A}}$
and $i$ is the label of $T$. Tiles of order $k$ are defined as translates of
the prototiles of order $k$. We say that they have “type $\mathcal{B}$” if $T$
has type $\mathcal{B}$.

Given a tiling ${\mathcal{T}}\in\Omega_{\mathcal{G}}$, using the surjectivity
of the substitution map $\mathcal{G}$, find a sequence of tilings
$\\{{\mathcal{T}}_{k}\\}_{k\in\mathbb{Z}}$ such that
${\mathcal{T}}_{0}={\mathcal{T}}$ and
$\mathcal{G}({\mathcal{T}}_{k})={\mathcal{T}}_{k+1}$ for every
$k\in\mathbb{Z}$. Denote by ${\mathcal{T}}^{(k)}$ the tiling obtained from
${\mathcal{T}}_{k}$ by replacing each tile with the corresponding tile of
order $k$, i.e. ${\mathcal{T}}^{(k)}=\varphi^{k}({\mathcal{T}}_{k})$. Note
that the tiles of ${\mathcal{T}}^{(k+1)}$ are obtained from tiles of
${\mathcal{T}}^{(k)}$ by “composition,” roughly speaking, by taking
appropriate unions, and the inverse operation is “subdivision,” determined by
the substitution rule. Observe that if ${\mathcal{T}}$ contains a tile of type
$\mathcal{B}$, then these tilings are uniquely defined; in fact,

(2.7) ${\mathcal{T}}^{(k)}=\varphi^{k}{\mathcal{G}}^{-k}({\mathcal{T}})\ \
\mbox{for all}\ k\in{\mathbb{Z}}.$

The tiles of ${\mathcal{T}}^{(k)}$ will be called tiles of order $k$ obtained
from ${\mathcal{T}}$. The tiles of ${\mathcal{T}}^{(k)}$ for $k>0$ will
sometimes be referred to as “supertiles of ${\mathcal{T}}$”.

##  3\. Transverse Dynamics

One of the main technical ingredients in our proof will be the dynamical
system $(\Omega_{\mathcal{G}},\mathcal{G})$, restricted to a certain fractal
subset defined below. Recall that $\varphi=\lambda\cdot O$, $\lambda>1$, and
$O$ is an orthogonal matrix.

###  3.1. Graph-Directed Iterated Function Systems

Consider the directed graph $G=(V,E)$ such that the set of vertices $V$
coincides with the alphabet $\mathcal{B}$ and the multiplicity of the set of
edges from $T$ to $T^{\prime}$ is exactly the number of occurrences of the
(translate of) prototile $T^{\prime}$ in the patch $\mathcal{G}(T)$. It
follows that the transpose matrix $B^{t}$ is exactly the incidence matrix of
the graph $G$. We will denote by $\mathcal{E}_{T,T^{\prime}}$ the set of edges
connecting a vertex $T$ to a vertex $T^{\prime}$. We will use the symbols
$s(e),r(e)$ respectively, to denote the source and range of a directed edge.

For each vertex (prototile) $T\in V$, consider the set $S_{T}={\rm supp}(T)$.
Notice that there is a one-to-one correspondence between edges in
$\mathcal{E}_{T_{1},T_{2}}$ and the set of translates of (the order $(-1)$
tile) $\varphi^{-1}(T_{2})$ in $\varphi^{-1}(\mathcal{G}(T_{1}))$. We shall
fix such a correspondence.

This can be made precise using formula (2.2) for the tile substitution: the
set of edges ${\mathcal{E}}_{T,T^{\prime}}$ corresponds to
${\mathcal{D}}_{T,T^{\prime}}$, for $T,T^{\prime}\in\mathcal{B}$. Given
$e\in{\mathcal{E}}_{T,T^{\prime}}$, we denote the corresponding vector in
${\mathcal{D}}_{T,T^{\prime}}$ by $u_{e}$. Then the similitude

(3.1) $f_{e}:\,x\mapsto\varphi^{-1}(x+u_{e})$

maps the set $S_{T^{\prime}}$ onto the translate of
$\varphi^{-1}(S_{T^{\prime}})$ corresponding to the edge $e$ in the patch
$\varphi^{-1}(\mathcal{G}(T))$ according to (2.3). Observe that distinct edges
define different maps. Then $G=(V,E)$, $\\{f_{e}\\}_{e\in E}$, is a graph-
directed system, and it uniquely defines a family of non-empty compact sets
$\\{K_{T}\\}_{T\in\mathcal{B}}$ of $\mathbb{R}^{d}$ such that

(3.2)
$K_{T}=\bigcup_{T^{\prime}\in\mathcal{B}}\bigcup_{e\in\mathcal{E}_{T,T^{\prime}}}f_{e}(K_{T^{\prime}}),$

see [MW] or [Fa, p.48]. Note that $K_{T}\subset S_{T}$ for every
$T\in\mathcal{B}$. The set $K_{T}$ is obtained from $S_{T}$ by consecutively
removing all “$\varphi$-preimages” of tiles from
$\mathcal{A}\setminus\mathcal{B}$. We note that the union (3.2) need not be
disjoint.

Observe that the contraction coefficient of every map $f_{e}$, $e\in E$, is
exactly $1/\lambda$. Thus, to find the Hausdorff dimension of the sets
$\\{K_{T}\\}_{T\in\mathcal{B}}$, one needs to consider the matrix $D^{(s)}$
with the entries

$D_{T_{1},T_{2}}^{(s)}=\sum_{e\in\mathcal{E}_{T_{1},T_{2}}}\frac{1}{\lambda^{s}}=\frac{1}{\lambda^{s}}m_{T_{2},T_{1}}.$

It follows from [MW], see also [Fa, Corollary 3.5]111This requires the open
set condition which can be verified by setting $U_{T}=\textrm{int}(S_{T})$ and
noting that
$U_{T}\supset\bigcup_{T^{\prime}\in\mathcal{B}}\bigcup_{e\in\mathcal{E}_{T,T^{\prime}}}f_{e}(U_{T^{\prime}})$,
the union being disjoint., that the Hausdorff dimension of each set $K_{T}$,
$T\in\mathcal{B}$, is the unique positive number $\alpha$ satisfying

$1=\rho(D^{(\alpha)})=\frac{1}{\lambda^{\alpha}}\rho(B^{t})=\frac{\rho(B)}{\lambda^{\alpha}}.$

Therefore, the Hausdorff dimension of every set $K_{T}$, $T\in\mathcal{B}$, is
equal to

(3.3) $\alpha=\log(\rho(B))/\log(\lambda).$

######  Remark 3.1.

It is proved in [MW], see also [Fa, Corollary 3.5], that the
$\alpha$-dimensional Hausdorff measure of $K_{T}$, denoted
${\mathcal{H}}^{\alpha}(K_{T})$, is positive and finite. This, together with
(3.2), implies that

(3.4) ${\mathcal{H}}^{\alpha}(K_{T}\cap K_{T^{\prime}})=0\ \ \mbox{for}\ T\neq
T^{\prime},$

and $({\mathcal{H}}^{\alpha}(K_{T}))_{T\in\mathcal{B}}$ is a left Perron-
Frobenius eigenvector of $B$.

We will also need the fact that
$\\{{\mathcal{H}}^{\alpha}|_{K_{T}}\\}_{T\in\mathcal{B}}$ is the list of
natural self-similar graph-directed measures on the attractors. This means
that $\\{{\mathcal{H}}^{\alpha}|_{K_{T}}\\}_{T\in\mathcal{B}}$ is, up to
scaling, the unique list of finite and positive Borel measures $\eta_{{}_{T}}$
on $K_{T}$, $T\in\mathcal{B}$, such that

(3.5)
$\eta_{{}_{T}}=\sum_{T^{\prime}\in\mathcal{B}}\sum_{e\in{\mathcal{E}}_{T,T^{\prime}}}\frac{1}{\rho(B)}(\eta_{{}_{T^{\prime}}}\circ
f_{e}^{-1}),$

see [E, 3.5]. Moreover, these natural measures may be obtained as projections
of appropriate Markov measures on the sequence space, as we are now going to
explain.

Let $T\in\mathcal{B}$. By the definition of graph-directed sets, $x\in K_{T}$
if and only if there is an infinite path $(e_{0},e_{1},\ldots)$ in the graph
$G$ such that $T=s(e_{0})$ and

(3.6) $\\{x\\}=\bigcap\limits_{k=0}^{\infty}K_{(e_{0},\ldots,e_{k})},$

where

(3.7) $K_{(e_{0},\ldots,e_{k})}=f_{e_{0}}\circ f_{e_{1}}\circ\cdots\circ
f_{e_{k}}(K_{r(e_{k})}).$

######  Definition 3.2.

(1) Let $X_{G}$ be the two-sided edge shift space associated with the graph
$G=(V,E)$, i.e.

$X_{G}=\\{(e_{n})\in E^{\mathbb{Z}}:e_{n+1}\mbox{ follows }e_{n}\mbox{ in the
graph }G\mbox{ for every }n\in\mathbb{Z}\\}.$

Formally, “$e_{n+1}\mbox{ follows }e_{n}\mbox{ in the graph }G$” means
$r(e_{n+1})=s(e_{n})$. The left shift on $X_{G}$ is denoted by $S$.

(2) We will refer to $X_{G}$ as the set of infinite two-sided paths
$(e_{n})_{n\in{\mathbb{Z}}}$ in the graph $G$. We will need it in the next
section; for now, let $X_{G}^{+}$ be the set of one-sided infinite paths
$(e_{n})_{n\geq 0}$ in the graph $G$. The natural projection
$\pi_{+}:\,X_{G}^{+}\to{{\mathbb{R}}}^{d}$ is defined by

$\pi_{+}\left((e_{n})_{n\geq 0}\right)=\lim_{k\to\infty}f_{e_{0}}\circ
f_{e_{1}}\circ\cdots\circ f_{e_{k}}(x_{0}),$

which is independent of $x_{0}\in{{\mathbb{R}}}^{d}$. For $T\in\mathcal{B}$
let

(3.8) $X^{+}_{G}(T)=\\{(e_{n})_{n\geq 0}\in X_{G}^{+}:\ s(e_{0})=T\\}$

be the set of infinite paths in $G$ starting at the vertex $T$. Clearly,
$X_{G}^{+}=\coprod_{T\in{\mathcal{B}}}X^{+}_{G}(T)$ is a disjoint union. It
follows from (3.6) that

$K_{T}=\pi_{+}(X^{+}_{G}(T)).$

Using (3.1), the natural projection $\pi_{+}$ can be written explicitly as
follows:

(3.9) $\pi_{+}\left((e_{n})_{n\geq
0}\right)=\sum_{n=0}^{\infty}\varphi^{-n-1}u_{e_{n}}.$

(3) Let $w=(w_{T})_{T\in\mathcal{B}}$ be the right Perron-Frobenius
eigenvector for the matrix $B^{t}$, such that $\sum_{T\in\mathcal{B}}w_{T}=1$.
We consider the Markov measure $\overline{\eta}$ on $X_{G}^{+}$, with initial
probabilities (i.e. probabilities of starting at $T\in\mathcal{B}$) equal to
$w_{T}$ and the probability of moving along an edge $e$ equal to
$\frac{w_{r(e)}}{\rho(B)w_{s(e)}}$. Consistency follows from the fact that $w$
is the right eigenvector of the transition matrix for the graph, with
eigenvalue $\rho(B)$. In view of Remark 3.1, we have

$w_{T}=c_{0}^{-1}{\mathcal{H}}^{\alpha}(T)\ \ \mbox{where}\ \
c_{0}=\sum_{T^{\prime}\in{\mathcal{B}}}{\mathcal{H}}^{\alpha}(T^{\prime}),$

and hence for a cylinder set $[e_{0},\ldots,e_{n}]\subset X_{G}^{+}$ we obtain

(3.10)
$\overline{\eta}([e_{0},\ldots,e_{n}])=\frac{w_{r(e_{n})}}{\rho(B)^{n+1}}=\frac{{\mathcal{H}}^{\alpha}(r(e_{n}))}{c_{0}\rho(B)^{n+1}},.$

The next lemma follows from the theory of graph-directed IFS (see e.g. the
proof of [MW, Theorem 3]).

######  Lemma 3.3.

For $T\in\mathcal{B}$ consider

$\eta_{{}_{T}}:=\overline{\eta}|_{X^{+}_{G}(T)}\circ\pi_{+}^{-1},$

that is, the natural projection of the measure $\overline{\eta}$ restricted to
$X^{+}_{G}(T)$. Then $\\{\eta_{{}_{T}}\\}_{T\in\mathcal{B}}$ is the list of
graph-directed self-similar measures satisfying (3.5), and

$\eta_{{}_{T}}=c_{0}^{-1}{\mathcal{H}}^{\alpha}|_{K_{T}}\ \ \mbox{for}\
T\in\mathcal{B},$

where
$c_{0}=\sum_{T^{\prime}\in{\mathcal{B}}}{\mathcal{H}}^{\alpha}(T^{\prime})$.

###  3.2. “Cantorization” of tilings

Recall that the graph-directed set $K_{T}$ is defined for every prototile
$T\in\mathcal{B}$. If $T^{\prime}=T+x$ is a translate of a prototile
$T\in\mathcal{B}$, then we write $K_{T^{\prime}}$ for the set $K_{T}+x$.

######  Definition 3.4.

(1) The “cantorization” of a tiling $\mathcal{T}\in\Omega_{\mathcal{G}}$ is
the set

${\mathcal{C}}({\mathcal{T}})=\bigcup\\{K_{T}:\ T\in{\mathcal{T}}\ \mbox{and
$T$ is type ${\mathcal{B}}$}\\}.$

(2) Denote

$\Omega_{0}=\\{\mathcal{T}\in\Omega_{\mathcal{G}}:\textbf{0}\in\mathcal{C}(\mathcal{T})\\},$

where 0 stands for the zero vector.

Next we present some equivalent conditions for the property
${\mathcal{T}}\in\Omega_{0}$, which are immediate from the definitions.

######  Remark 3.5.

(1) We have ${\mathcal{T}}\in\Omega_{0}$ if and only if there exist
$T_{0}\in\mathcal{B}$ and $x\in K_{T_{0}}$ such that
$T_{0}-x\in{\mathcal{T}}$.

(2) We have ${\mathcal{T}}\in\Omega_{0}$ if and only if there is a nested
sequence of type ${\mathcal{B}}$ tiles of order $-k$ obtained from
${\mathcal{T}}$, such that the intersection of their supports is the origin
${\bf 0}$. More formally (compare (2.7)), we have that
${\mathcal{T}}\in\Omega_{0}$ if and only if there is a sequence of type
$\mathcal{B}$ tiles $T_{-k}\in\varphi^{-k}{\mathcal{G}}^{k}({\mathcal{T}})$,
$k\geq 1$, such that

${\rm supp}(T_{-k-1})\subset{\rm supp}(T_{-k}),\ k\geq 0,\ \ \mbox{and}\ \
\bigcap_{k=0}^{\infty}{\rm supp}(T_{-k})=\\{{\bf 0}\\}.$

######  Proposition 3.6.

(i) The set $\Omega_{0}$ is compact in the tiling metric.

(ii) The map $\mathcal{G}:\Omega_{0}\rightarrow\Omega_{0}$ is a homeomorphism.

(iii) For every tiling $\mathcal{T}\in\Omega_{0}$, we have that
$\mathcal{C}(\mathcal{G}^{-1}(\mathcal{T}))=\varphi^{-1}(\mathcal{C}(\mathcal{T}))$
and $\mathcal{C}(\mathcal{G}(\mathcal{T}))=\varphi(\mathcal{C}(\mathcal{T}))$.

###### Proof.

(i) We only need to show that the set $\Omega_{0}$ is closed in
$\Omega_{\mathcal{G}}$. Consider a tiling $\mathcal{T}\notin\Omega_{0}$. Then
$\textbf{0}\notin\mathcal{C}({\mathcal{T}})$. Then ${\bf 0}$ does not belong
to $K_{T}$ for any tile of type ${\mathcal{B}}$ containing the origin, which
is an open condition, since $K_{T}$ is compact.

(ii) The continuity of the map
$\mathcal{G}:\Omega_{\mathcal{G}}\rightarrow\Omega_{\mathcal{G}}$ is well-
known and easily follows from the definition of the tiling metric. Note that
tiles of type ${\mathcal{B}}$ belong to ${\mathcal{A}}_{\rm nonp}$, since they
do not appear in minimal components, see Definition 2.11(1). So
${\mathcal{G}}$ is one-to-one on $\Omega_{0}$. Hence, in view of Theorem 2.12,
we only need to show that $\mathcal{G}(\Omega_{0})=\Omega_{0}$.

Remark 3.5(2) implies that if ${\mathcal{T}}\in\Omega_{0}$ then
${\mathcal{G}}({\mathcal{T}})\in\Omega_{0}$. Indeed, using the notation of the
remark, we have $\varphi
T_{-k}\in\varphi^{-(k-1)}{\mathcal{G}}^{k-1}({\mathcal{G}}({\mathcal{T}}))$,
so $\\{\varphi T_{-k}\\}_{k\geq 1}$ is a nested sequence of tiles of order
$-(k-1)$ obtained from ${\mathcal{G}}({\mathcal{T}})$, all of type
$\mathcal{B}$, and clearly the intersection of their supports is $\\{{\bf
0}\\}$.

Since the map $\mathcal{G}$ is invertible on $\Omega_{0}$ by Theorem 2.12, we
can find a (unique) tiling $\mathcal{T}_{-1}$ with
$\mathcal{G}(\mathcal{T}_{-1})=\mathcal{T}$. We claim that
${\mathcal{T}}_{-1}\in\Omega_{0}$. If not, then for some $k>0$ all the tiles
of order $-k$ obtained from ${\mathcal{T}}_{-1}$ containing the origin are of
type ${\mathcal{A}}\setminus{\mathcal{B}}$. But the substitution of
${\mathcal{A}}\setminus{\mathcal{B}}$ tiles contains only
${\mathcal{A}}\setminus{\mathcal{B}}$ tiles, so we get a contradiction with
the assumption that the origin lies in a ${\mathcal{B}}$ tile of
${\mathcal{T}}$. We have proved that $\mathcal{G}|_{\Omega_{0}}$ is a
homeomorphism.

(iii) It follows from Equation (3.2) that
$\varphi^{-1}({\mathcal{C}}({\mathcal{G}}(T)))=K_{T}$ for every prototile
$T\in\mathcal{B}$. Therefore,

$\varphi^{-1}({\mathcal{C}}({\mathcal{G}}({\mathcal{T}})))={\mathcal{C}}({\mathcal{T}})\
\ \mbox{for every tiling}\ {\mathcal{T}}\in\Omega_{0}.$

Ths implies the last statement of the proposition. ∎

##  4\. Transverse Measures

In this section we show that the dynamical system $(\Omega_{0},\mathcal{G})$
is measure-theoretically isomorphic to a mixing Markov chain, namely, the edge
shift on the graph $G$ with the incidence matrix $B^{t}$, equipped with the
measure of maximal entropy. We note that properties of
$(\Omega_{\mathcal{G}},\mathcal{G})$ as a topological dynamical system were
earlier considered in [AP].

Let $\mu$ be the $\mathbb{R}^{d}$-ergodic measure on $\Omega_{\mathcal{G}}$ as
described in Proposition 2.19. It is unique up to scaling; we will normalize
it later. There exists a unique Borel $\sigma$-finite transverse measure
$\mu^{{\rm tr}}$ on the transversal $\Gamma$ such that

(4.1) $\mu(U-\Theta)=\mu^{{\rm tr}}(U)\cdot{\mathcal{L}}^{d}(\Theta),$

where $\mathcal{L}^{d}$ is the $d$-dimensional Lebesgue measure and

$U-\Theta=\\{{\mathcal{T}}-x:\ {\mathcal{T}}\in U,\ x\in\Theta\\},$

for all Borel sets $U\subset\Gamma_{Q}$ and $\Theta\subset{\rm supp}(Q),\
Q\in\mathcal{B}$, see Section 7 in [CS] for the details. (Actually, in [CS]
this is only proved for $U$ contained in a small ball centered at the origin,
but the formula in stated generality follows from shift invariance of the
measure $\mu$.) This means that “locally” the measure $\mu$ behaves as a
product measure.

Following [CS], we give the following definition. Recall that
$\Gamma_{T}=\\{\mathcal{T}\in\Gamma:\,T\in\mathcal{T}\\}$.

######  Definition 4.1.

For every $Q\in\mathcal{B}$ and $n\geq 0$, define

$\mu^{{\rm tr}}_{n,Q}=\mu^{{\rm tr}}(\mathcal{G}^{n}(\Gamma_{Q})-x),$

where $x$ is a vector such that $\mathcal{G}^{n}(\Gamma_{Q})-x\subset\Gamma$.
Since $\mu^{{\rm tr}}$ is a transverse measure, the definition of $\mu^{{\rm
tr}}_{n,Q}$ does not depend on the choice of $x$.

The next result follows from Lemma 5.11 in [CS] and the Perron-Frobenius
theorem for primitive matrices.

######  Lemma 4.2.

There exists a (unique) right Perron-Frobenius eigenvector $\xi$ for the
matrix $B$ such that

(4.2) $\mu^{{\rm tr}}_{n,{Q}}=\frac{\xi_{Q}}{\rho(B)^{n}}\mbox{ for every
}Q\in\mathcal{B}\mbox{ and }n\geq 0.$

Let $G=(V,E)$ be the graph of the iterated function system constructed in
Section 3.1.

######  Definition 4.3.

(1) The itinerary of ${\mathcal{T}}\in\Omega_{0}$ for the
${\mathcal{G}}$-dynamics is a two-sided infinite path
$\beta({\mathcal{T}})=(e_{n})_{n\in{\mathbb{Z}}}\in X_{G}$ (see Definition
3.2), defined as follows: $\beta({\mathcal{T}})=(e_{n})_{n\in{\mathbb{Z}}}$ if
for all $n\in{\mathbb{Z}}$ the tiling ${\mathcal{G}}^{n}({\mathcal{T}})$ has a
tile $T_{n}$ of type $s(e_{n})=r(e_{n-1})\in\mathcal{B}$ containing the origin
and $T_{n+1}$ occurs in ${\mathcal{G}}(T_{n})$ in the position corresponding
to $e_{n}$.

(2) Observe that $\varphi^{n}T_{-n}$ for $n>0$ forms an increasing sequence of
supertiles of the tiling ${\mathcal{T}}$. We will call it the compatible
sequence of supertiles of ${\mathcal{T}}$ containing the origin.

(3) Note that the itinerary need not be unique. Denote by $\Omega_{0}^{*}$ the
set of all tilings $\mathcal{T}\in\Omega_{0}$ for which the itinerary is
unique. The itinerary is non-unique if and only if for some
$n\in{\mathbb{Z}}$, the origin ${\bf 0}$ lies on the common boundary of two
tiles of ${\mathcal{B}}$ type
$T_{n},T_{n}^{\prime}\in{\mathcal{G}}^{n}({\mathcal{T}})$ and, moreover, ${\bf
0}\in K_{T_{n}}\cap K_{T_{n}^{\prime}}$. Note that just being on the boundary
of a tile may not lead to non-uniqueness.

Thus $\beta:\,\Omega_{0}^{*}\to X_{G}$ is a well-defined function, whereas
$\beta$ may be considered as a multi-valued function on all of $\Omega_{0}$.
Observe that $\Omega_{0}^{*}$ is a ${\mathcal{G}}$-invariant Borel subset of
$\Omega_{0}$.

(4) By definition, $\beta\circ{\mathcal{G}}=S\circ\beta$, where $S$ is the
left shift on $X_{G}$. This holds, in an appropriate sense, even when the
itinerary is non-unique.

######  Remark 4.4.

(1) Many properties of the tiling dynamical system can be expressed using the
symbolic dynamics provided by the itinerary $\beta$. In particular, if we fix
the left one-sided sequence $(e_{n})_{n<0}$, this corresponds to the set of
translates of ${\mathcal{T}}\in\Omega_{0}^{*}$, such that the origin stays in
the interior of its original tile of type $r(e_{-1})$. This is a “piece” of
the translation orbit of ${\mathcal{T}}$. On the other hand, fixing the right
half of the symbolic orbit $(e_{n})_{n\geq 0}$ corresponds to the transversal;
more precisely, for all ${\mathcal{T}}\in(\Gamma_{T}+x)\cap\Omega^{*}_{0}$ for
a fixed vector $x$, the sequences $\beta({\mathcal{T}})$ agree in $n\geq 0$.

(2) There are, however, some complications. First, $\beta$ is not well-defined
on $\Omega_{0}\setminus\Omega_{0}^{*}$. Second, $\beta$ need not be one-to-one
and need not be onto (even if extended to $\Omega_{0}$ as a multi-valued
function). The reason is that the sequence $(e_{n})_{n<0}$ determines a
sequence of compatible supertiles whose union need not be the entire space
${{\mathbb{R}}}^{d}$. We will deal with such sequences by showing that they
have zero measure of maximal entropy for $S$. To get an example of such a
sequence, let ${\mathcal{G}}$ be the substitution from Example 2.4. Then the
graph $G$ has a single vertex and eight loops, corresponding to the eight
1-tiles in the substitution of a 1-tile. Taking a constant sequence
$(e_{n})_{n<0}$, corresponding to the lower-left 1-tile, for instance, will
yield the tiling of the 1st quadrant of the plane; see the discussion
following Definition 2.6. More generally, if the sequence $(e_{n})_{n<0}$
eventually consists of edges corresponding to the 1-tiles on one of the sides
of the substituted 1-tile, then the union of compatible supertiles will only
cover a half-plane or a quarter-plane.

######  Definition 4.5.

(1) Define $X^{*}_{G}$ as the set of $(e_{n})\in X_{G}$ such that the
compatible increasing sequence of supertiles, corresponding to
$(e_{n})_{n<0}$, has all of ${{\mathbb{R}}}^{d}$ as the limit (i.e. the union)
of the supports. It is clear that $X^{*}_{G}$ is $S$-invariant.

(2) We define the natural projection map $\pi:\,X^{*}_{G}\to\Omega_{0}$ so
that $(e_{n})$ is an itinerary of ${\mathcal{T}}:=\pi(\overline{e})$. It is
possible to describe ${\mathcal{T}}$ explicitly, as a limit of an increasing
compatible sequence of patches (whose supports are the supports of supertiles
of ${\mathcal{T}}$). The condition $\overline{e}=(e_{n})_{n\in{\mathbb{Z}}}\in
X_{G}$ means, by definition, that

(4.3) $r(e_{n})+u_{e_{n}}\in{\mathcal{G}}(s(e_{n}))\ \ \ \mbox{for all}\
n\in{\mathbb{Z}}$

(recall that the vertices of $G$ are identified with the prototiles in
${\mathcal{B}}$). A tile of ${\mathcal{T}}=\pi(\overline{e})$ containing the
origin (possibly non-unique) must be

(4.4)
$T_{0}-\sum_{n=0}^{\infty}\varphi^{-n-1}u_{e_{n}}=T_{0}-\pi_{+}(\overline{e}_{+}),$

where $T_{0}=s(e_{0})$ and $\overline{e}_{+}=(e_{n})_{n\geq 0}$ (recall that
$\pi_{+}$ was defined in Definition 3.2(2)). Note that this already guarantees
${\mathcal{T}}\in\Omega_{0}$, in view of Remark 3.5(1) and (3.9). Now we let

(4.5)
$\pi(\overline{e})=\lim_{k\to\infty}\left[{\mathcal{G}}^{k}(s(e_{-k}))-\sum_{n=-k}^{\infty}\varphi^{-n-1}u_{e_{n}}\right].$

We claim that these patches are increasing and compatible. Indeed,

${\mathcal{G}}^{k}(s(e_{-k}))-\sum_{n=-k}^{\infty}\varphi^{-n-1}u_{e_{n}}\subset{\mathcal{G}}^{k+1}(s(e_{-k-1}))-\sum_{n=-k-1}^{\infty}\varphi^{-n-1}u_{e_{n}}$

reduces to

$u_{e_{-k-1}}+s(e_{-k})\in{\mathcal{G}}(s(e_{-k-1})),$

which follows from (4.3), keeping in mind that $s(e_{-k})=r(e_{-k-1})$. Thus,
the right-hand side of (4.5) is well-defined, and it is a tiling of the entire
${{\mathbb{R}}}^{d}$ if $\overline{e}\in X_{G}^{*}$.

######  Lemma 4.6.

We have $\pi\circ S={\mathcal{G}}\circ\pi$ on $X^{*}_{G}$ and
$\pi\circ\beta={\textit{I}d}$ on $\beta(\Omega_{0}^{*})$.

###### Proof.

This is an immediate consequence of the definitions. ∎

Next we consider the measure of maximal entropy (the Parry measure)
$\overline{\nu}$ for the shift $S$ on $X_{G}$. Recall that the incidence
matrix for the graph $G$ is $B^{t}$. The Parry measure (of the edge shift) is
a Markov measure, given by

(4.6)
$\overline{\nu}([e_{1},\ldots,e_{n}]_{k})=u_{s(e_{1})}v_{s(e_{1})}\prod_{j=1}^{n}\frac{v_{r(e_{j})}}{\rho(B)v_{s(e_{j})}}=\frac{u_{s(e_{1})}v_{r(e_{n})}}{\rho(B)^{n}},$

where $[e_{1},\ldots,e_{n}]_{k}$ is a cylinder set in $X_{G}$ starting at the
index $k\in{\mathbb{Z}}$, $n\geq 0$, $u=(u_{Q})_{Q\in\mathcal{B}}$ is the left
Perron-Frobenius eigenvector of $B^{t}$, and $v=(v_{Q})_{Q\in\mathcal{B}}$ is
the right Perron-Frobenius eigenvector of $B^{t}$, normalized so that
$\sum_{Q\in\mathcal{B}}u_{Q}v_{Q}=1$. The measure is clearly shift-invariant.
We have

$\overline{\nu}(\\{\overline{e}\in X_{G}:\
s(e_{0})=Q\\})=\sum_{Q^{\prime}\in\mathcal{B}}\sum_{e\in{\mathcal{E}}_{Q,Q^{\prime}}}u_{Q}v_{Q^{\prime}}\cdot\rho(B)^{-1}=u_{Q}v_{Q},$

which implies that $\overline{\nu}$ is a probability measure. For the vector
$u$ we can take the vector $\xi$ from Lemma 4.2, which is a right Perron-
Frobenius eigenvector for $B$, and for the vector $v$ we can take
$({\mathcal{H}}^{\alpha}(K_{Q}))_{Q\in\mathcal{B}}$, which is a left Perron-
Frobenius eigenvector for $B$, see Remark 3.1. Since the measure $\mu$ was
defined up to scaling, we can normalize it (this will also affect the
transverse measure) so that

(4.7)
$\sum_{Q\in\mathcal{B}}\xi_{Q}{\mathcal{H}}^{\alpha}(K_{Q})=\sum_{Q\in\mathcal{B}}\mu^{{\rm
tr}}(\Gamma_{Q}){\mathcal{H}}^{\alpha}(K_{Q})=1.$

Then we have

(4.8)
$\overline{\nu}([e_{1},\ldots,e_{n}]_{k})=\frac{\xi_{s(e_{1})}}{\rho(B)^{n}}\,{\mathcal{H}}^{\alpha}(K_{r(e_{n})})\
\ \mbox{for}\ k\in{\mathbb{Z}},\ n\geq 0.$

It is well-known that the measure-preserving transformation
$(X_{G},S,\overline{\nu})$ is ergodic, where $S$ is the left shift.

######  Lemma 4.7.

We have $\overline{\nu}(X_{G}\setminus X^{*}_{G})=0$.

###### Proof.

Recall that there is an integer $k>0$ such that for each prototile
$T\in\mathcal{B}$ the interior of the patch ${\mathcal{G}}^{k}(T)$ contains a
translate of $T$. We can assume without loss of generality, passing from
${\mathcal{G}}$ to ${\mathcal{G}}^{k}$, that $k=1$. Then for any vertex of the
graph $G$ (i.e. $Q\in\mathcal{B}$) there is an edge $e$, with $s(e)=Q$, which
corresponds to the choice of an interior tile in the patch ${\mathcal{G}}(Q)$.
A one-sided path $(e_{n})_{n<0}$, which includes infinitely many of these
“interior” edges, will necessarily belong to $X_{G}^{*}$. Indeed, choosing an
interior supertile of order $n$ inside the supertile of order $n+1$, for
$n>0$, implies that the union of the compatible sequence of supertiles
contains the ball of radius $\delta\lambda^{n}$ centered at the origin, for
some $\delta>0$. A standard argument shows that this is a full measure set. To
verify this, note that the set of paths, which avoid the selected edges, has a
growth rate equal to the spectral radius of a matrix $B^{\prime}$ having at
least one entry in each row smaller than that of $B$, whence
$\rho(B^{\prime})<\rho(B)$. ∎

######  Definition 4.8.

Define the measure $\nu$ on $\Omega_{0}$ as the “push-forward” of
$\overline{\nu}$ on $X_{G}^{*}$ via the map $\pi$, that is,

$\nu(U)=\overline{\nu}(\pi^{-1}(U))\ \ \ \mbox{for Borel}\
U\subset\Omega_{0}.$

Since $\overline{\nu}$ is $S$-invariant, we obtain from Lemma 4.6 that the
measure $\nu$ is ${\mathcal{G}}$-invariant on $\Omega_{0}$.

######  Lemma 4.9.

We have $\nu(\Omega_{0}\setminus\Omega_{0}^{*})=0$.

###### Proof.

The argument is almost the same as in the proof of Lemma 4.7. It is enough to
prove that the set of tilings ${\mathcal{T}}\in\Omega_{0}$, for which there
exists $n\in{\mathbb{Z}}$ such that ${\bf 0}$ is on the boundary of a tile of
type ${\mathcal{B}}$ in ${\mathcal{G}}^{n}({\mathcal{T}})$, has $\nu$ measure
zero. Considering the itineraries of such tilings, we see that they must
contain only finitely many edges $e_{i}$ corresponding to the tile of type
$r(e_{i})$ in the interior of ${\mathcal{G}}(s(e_{i}))$, for $i\geq 0$. But
the growh rate of such sequences is strictly less than $\rho(B)$, hence their
$\overline{\nu}$ measure equals zero, as desired. ∎

######  Theorem 4.10.

Suppose that the Markov measure $\overline{\nu}$ is defined by (4.8), using
the normalization (4.7), and $\nu=\overline{\nu}\circ\pi^{-1}$. Then the
following hold:

(i) The probability-preserving system $(\Omega_{0},{\mathcal{G}},\nu)$ is
measure-theoretically isomorphic to $(X_{G},S,\overline{\nu})$, hence ergodic.

(ii) For any $Q\in\mathcal{B}$ and all Borel sets $\Theta\subset\Gamma_{Q},\
W\subset K_{Q}$ we have

(4.9) $\nu(\Theta-W)=\mu^{{\rm tr}}(\Theta)\cdot{\mathcal{H}}^{\alpha}(W).$

###### Proof.

(i) This follows from Lemmas 4.6, 4.7, and 4.9.

(ii) The left-hand side of (4.9) is well-defined, since
$\Gamma_{Q}-K_{Q}\subset\Omega_{0}$ by Remark 3.5(1). First let us prove the
equality for $\Theta=\Gamma_{Q}$. Recall that $X_{G}^{+}(Q)$ denotes the set
of one-sided paths in $G$ starting at $Q$. We have

$\nu(\Gamma_{Q}-W)=\overline{\nu}\left(\\{\overline{e}\in X_{G}:\
\overline{e}_{+}\in X^{+}_{G}(Q)\ \mbox{and}\ \pi_{+}(\overline{e}_{+})\in
W\\}\right),$

using the fact that ${\mathcal{T}}\in\Gamma_{Q}-W$, with $W\subset K_{Q}$, has
an itinerary with $s(e_{0})=Q$, and $\nu$ almost every tiling has a unique
itinerary by Lemma 4.9. The measure $\overline{\nu}$ on $X_{G}$ induces a
measure $\overline{\nu}_{+}$ on $X_{G}^{+}$ via the projection
$\overline{e}\mapsto\overline{e}_{+}$. Comparing (4.6) with (3.10) we see that

$\overline{\nu}_{+}|_{X^{+}_{G}(Q)}=c_{0}^{-1}\xi_{Q}\cdot\overline{\eta}|_{X^{+}_{G}(Q)}.$

Thus,

$\displaystyle\nu(\Gamma_{Q}-W)$ $\displaystyle=$
$\displaystyle\overline{\nu}_{+}|_{X^{+}_{G}(Q)}(\pi_{+}^{-1}W)$
$\displaystyle=$ $\displaystyle
c_{0}^{-1}\xi_{Q}\cdot\overline{\eta}|_{X^{+}_{G}(Q)}(\pi_{+}^{-1}W)$
$\displaystyle=$ $\displaystyle c_{0}^{-1}\xi_{Q}\cdot\eta_{Q}(W)$
$\displaystyle=$ $\displaystyle\xi_{Q}{\mathcal{H}}^{\alpha}(W),$

where we used Lemma 3.3 in the last step.

Now let us verify (4.9) for an arbitrary Borel $\Theta\subset\Gamma_{Q}$. The
transversal $\Gamma_{Q}$ is topologically a Cantor set, in which the Borel
$\sigma$-algebra is generated by the sets of the form
${\mathcal{G}}^{n}(\Gamma_{Q^{\prime}}-x)$, $Q^{\prime}\in{\mathcal{A}}$,
where $x$ is such that $Q+x\in{\mathcal{G}}^{n}(Q^{\prime})$. We have

$\nu({\mathcal{G}}^{n}(\Gamma_{Q^{\prime}}-x-W)=\nu({\mathcal{G}}^{n}(\Gamma_{Q^{\prime}}-\varphi^{-n}(x+W)))=\nu(\Gamma_{Q^{\prime}}-\varphi^{-n}(x+W)),$

using the fact that $\nu$ is ${\mathcal{G}}$-invariant. Note that $W\subset
K_{Q}$ and $Q+x\in{\mathcal{G}}^{n}(Q^{\prime})$ imply
$W+x\subset{\mathcal{C}}({\mathcal{G}}^{n}(Q^{\prime}))=\varphi^{n}K_{Q^{\prime}}$,
hence $\varphi^{-n}(x+W)\subset K_{Q^{\prime}}$, and by the case of (4.9)
already proved,

$\displaystyle\nu(\Gamma_{Q^{\prime}}-\varphi^{-n}(x+W))$ $\displaystyle=$
$\displaystyle\xi_{Q^{\prime}}\cdot{\mathcal{H}}^{\alpha}(\varphi^{-n}W)$
$\displaystyle=$
$\displaystyle\frac{\xi_{Q^{\prime}}\cdot{\mathcal{H}}^{\alpha}(W)}{\lambda^{nd}}$
$\displaystyle=$
$\displaystyle\frac{\xi_{Q^{\prime}}\cdot{\mathcal{H}}^{\alpha}(W)}{\rho(B)^{n+1}}$
$\displaystyle=$ $\displaystyle\mu^{{\rm
tr}}(\Gamma_{Q^{\prime}}-x)\cdot{\mathcal{H}}^{\alpha}(W),$

by Lemma 4.2 and Definition 4.1. The proof is complete.

∎

##  5\. Second Order Ergodic Theorem

In this section we establish the second order theorem for tiling substitution
systems. We begin with Lemma 5.3 saying that the second order ergodic theorem
can be established by checking the convergence of second order averages for
one (any) function only. This lemma was originally proved in [Fi1, Theorem 4]
for the discrete case. We include the proof for the reader’s convenience. The
proof is based on the following generalization of Hopf’s ratio ergodic
theorem. Recall that a group action is free if the identity is the only group
element for which there exists a fixed point. Our tiling translation action is
free in the measure-theoretic sense, since tilings containing at least one
tile of type ${\mathcal{B}}$ are non-periodic [CS, Corollary 4.5], and these
tilings form an invariant set of full $\mu$ measure. Recall that $B_{R}$
denotes the closed Euclidean ball. We note that the dynamical system in the
following theorem need not be conservative as the ergodic sums get averaged
over symmetric balls versus $[0,n]^{d}$.

######  Theorem 5.1 (M. Hochman [H]).

Let $\\{T^{u}\\}_{u\in\mathbb{R}^{d}}$ be a free ergodic measure preserving
action on a standard $\sigma$-finite measure space $X$. Then for $\mu$-a.e.
$x\in X$ and every $f,g\in L^{1}(X,\mu)$ with $\int_{X}gd\mu\neq 0$, we have

$\frac{\int_{B_{R}}f(T^{u}(x))du}{\int_{B_{R}}g(T^{u}(x))du}\to\frac{\int_{X}fd\mu}{\int_{X}gd\mu}\
\ \mbox{as }R\to\infty.$

######  Remark 5.2.

In fact, [H] considers non-singular free ergodic actions of ${\mathbb{Z}}^{d}$
or ${{\mathbb{R}}}^{d}$, which includes measure-preserving actions, and
averaging is over balls in any norm. We note that for our purposes it would
suffice to use an older ratio ergodic theorem of M. Becker [Beck], but it
would require a little additional argument, so we chose to quote the recent
more general result of M. Hochman.

######  Lemma 5.3.

Let $\\{T^{u}\\}_{u\in\mathbb{R}^{d}}$ be a free ergodic measure preserving
action on a standard $\sigma$-finite measure space $(X,\mu)$. Assume that
there exists $\alpha>d-1$ such that for some function $g\in
L^{\infty}(X,\mu)\cap L^{1}(X,\mu)$ with $\int_{X}g\,d\mu\neq 0$, the limit

$\lim\limits_{t\to\infty}\frac{1}{\log(t)}\int_{1}^{t}\frac{\int_{B_{R}}g(T^{u}(x))\,du}{(2R)^{\alpha}}\,\frac{dR}{R}$

exists and is finite for $\mu$ a.e. $x\in X$. Then

(i) this limit is constant almost everywhere;

(ii) writing this limit as $c\cdot\int_{X}gd\mu$ for some constant $c$, we get
that for every function $f\in L^{1}(X,\mu)$,

$\lim\limits_{t\to\infty}\frac{1}{\log(t)}\int_{1}^{t}\frac{\int_{B_{R}}f(T^{u}(x))\,du}{c(2R)^{\alpha}}\,\frac{dR}{R}=\int_{X}f\,d\mu$

for $\mu$-a.e. $x\in X$.

###### Proof.

(i) Set

$S_{R}^{g}(x)=\int_{B_{R}}g(T^{u}(x))\,du\ \ \mbox{and}\ \
\overline{g}(x)=\lim\limits_{t\to\infty}\frac{1}{\log(t)}\int_{1}^{t}\frac{S_{R}^{g}(x)}{(2R)^{\alpha}}\,\frac{dR}{R}.$

By assumption, the function $\overline{g}(x)$ is finite for $\mu$-a.e. $x\in
X$, and it is straightforward to check that $\overline{g}$ is measurable. We
claim that $\overline{g}(T^{v}(x))=\overline{g}(x)$ for every
$v\in\mathbb{R}^{d}$ and $\mu$-a.e. $x\in X$. Indeed,

$\int_{B_{R}}g(T^{u}(x))\,du-\int_{B_{R}}g(T^{u+v}(x))\,du=O(R^{d-1}\|g\|_{\infty})\
\ \mbox{as}\ R\to\infty,$

and the assumption $\alpha>d-1$ yields the claim. Since the measure $\mu$ is
ergodic, we get that the function $\overline{g}$ is constant almost
everywhere.

(ii) Applying Theorem 5.1, we obtain that

$\frac{S_{R}^{f}(x)}{S_{R}^{g}(x)}\to\frac{\int f\,d\mu}{\int g\,d\mu}\ \mbox{
as }R\to\infty.$

Assume for definiteness that $\int g\,d\mu>0$ and $\int f\,d\mu\geq 0$. It
follows that for any $\varepsilon>0$ there is $R_{0}>0$ such that for all
$R>R_{0}$,

$S_{R}^{g}(x)\frac{\int f\,d\mu}{\int g\,d\mu}\,(1-\varepsilon)\leq
S_{R}^{f}(x)\leq S_{R}^{g}(x)\frac{\int fd\mu}{\int
g\,d\mu}\,(1+\varepsilon).$

Dividing the inequalities by $2^{\alpha}R^{\alpha+1}$ and integrating with
respect to $R$ yields

$(1-\varepsilon)\int g\,d\mu\,\frac{\int f\,d\mu}{\int
g\,d\mu}\leq\lim\limits_{t\to\infty}\frac{1}{\log(t)}\int_{1}^{t}\frac{S_{R}^{f}(x)}{(2R)^{\alpha}}\,\frac{dR}{R}\leq(1+\varepsilon)\int
g\,d\mu\,\frac{\int f\,d\mu}{\int g\,d\mu}.$

Taking the limit as $\varepsilon\to 0$, we obtain the result. ∎

Now we are ready to prove the main result of the paper, but first we give the
definition of the average (or second-order) density, which was introduced by
Bedford and Fisher [BF].

######  Definition 5.4.

Let $\alpha>0$ and $\eta$ a positive finite Borel measure on
${{\mathbb{R}}}^{d}$. The average $\alpha$-dimensional density of $\eta$ at
$x$ is

$A^{\alpha}(\eta,x)=\lim_{k\to\infty}\frac{1}{k}\int_{0}^{k}\frac{\eta(B_{e^{-t}}(x))}{(2e^{-t})^{\alpha}}\,dt,$

if the limit exists. Note that we can replace $e^{-t}$ by $\lambda^{-t}$ for
$\lambda>1$, without changing the value of $A^{\alpha}(\eta,x)$. For $d=1$,
the right average density is defined as above, replacing
$\eta(B_{e^{-t}}(x))/(2e^{-t})^{\alpha}$ by $\eta([x,x+e^{-t}))/e^{-\alpha
t}$.

It is known that for a graph-directed self-similar set $K$ satisfying the Open
Set Condition, the $\alpha$-dimensional average density of the Hausdorff
measure ${\mathcal{H}}^{\alpha}$ (where $\alpha$ is the dimension of the set)
restricted to $K$, exists and is constant ${\mathcal{H}}^{\alpha}$-a.e. This
is proved in [BF] for srtandard IFS, and the extension to the graph-directed
sets is straightforward (as we essentially show below).

######  Theorem 5.5.

Let $\mathbb{X}=(\Omega_{\mathcal{G}},\mu,{{\mathbb{R}}}^{d})$ be the tiling
dynamical system corresponding to a tile substitution $\mathcal{G}$. Suppose
that the tiling system satisfies the assumptions of Section 2.3. Assume that
$\mu$ is an infinite ($\sigma$-finite) invariant measure, positive and finite
on $\Omega_{\mathcal{B}}$, where $\Omega_{\mathcal{B}}$ is the set of tilings
which have a type ${\mathcal{B}}$ tile containing the origin.

Then there exist positive parameters $\alpha$ and $c$ such that for
$\mu$-almost every tiling $\mathcal{T}\in\Omega$ and for every function $f\in
L^{1}(\Omega,\mu)$, we have

(5.1)
$\lim\limits_{t\to\infty}\frac{1}{\log(t)}\int_{0}^{t}\frac{\int_{B_{R}}f({\mathcal{T}}-u)\,du}{c(2R)^{\alpha}}\,\frac{dR}{R}=\int_{\Omega_{\mathcal{G}}}fd\mu.$

Here $\alpha=\log(\rho(B))/\log(\lambda)$ is the Hausdorff dimension of the
graph-directed self-similar sets from Section 3.1 and

$c=\gamma\cdot\lim\limits_{k\to\infty}\frac{1}{k}\int_{0}^{k}\frac{\mathcal{H}^{\alpha}(B_{\lambda^{-t}}(u)\cap
K_{Q})}{(2\lambda^{-t})^{\alpha}}\,dt$

for $\mathcal{H}^{\alpha}$-a.e. $u\in K_{Q}$ and for every $Q\in\mathcal{B}$,
where ${\mathcal{H}}^{\alpha}$ is the $\alpha$-dimensional Hausdorff measure
on $K_{Q}$ . The parameter $c$ is the average $\alpha$-dimensional density of
${\mathcal{H}}^{\alpha}$ restricted to $K_{Q}$, up to the normalizing constant
$\gamma$:

$\gamma^{-1}=\sum_{Q\in{\mathcal{B}}}\xi_{Q}{\mathcal{H}}^{\alpha}(Q),\ \
\mbox{where}\ \
\sum_{Q\in{\mathcal{B}}}\xi_{Q}{\mathcal{L}}^{d}(Q)=\mu(\Omega_{\mathcal{B}}),$

and $(\xi_{Q})_{Q\in{\mathcal{B}}}$ is a right Perron-Frobenius eigenvector of
the matrix $B$.

###### Proof.

(1) First note that, without loss of generality, we can normalize $\mu$ in
such a way that (4.7) holds, so that $\gamma=1$. We then define $\nu$ as in
Theorem 4.10 and consider the ergodic probability-preserving transformation
$(\Omega_{0},\nu,\mathcal{G}^{-1})$. We follow, in part, the argument of [BF,
Theorem 3.1] (see also [Fa, Theorem 6.6]). Recall that $B_{R}$ denotes the
closed ball of radius $R$ centered at the origin. Define a function
$\psi:\Omega_{0}\rightarrow\mathbb{R}$ by

$\psi(\mathcal{T})=\int\limits_{0}^{1}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap{B}_{\lambda^{t}})}{(2\lambda^{t})^{\alpha}}\,dt.$

Since the Hausdorff measure $\mathcal{H}^{\alpha}$ is finite on sets
$\mathcal{K}_{T}$, $T\in\mathcal{B}$, and the ball ${B}_{\lambda}$ contains
only a finite number of tiles, the function $\psi$ is bounded. It is
straightforward to check that the function $\psi$ is measurable.

(2) Recall that $\varphi=\lambda\cdot O$, where $O$ is an orthogonal matrix,
hence
${\mathcal{H}}^{\alpha}(\varphi^{-1}E)=\lambda^{-\alpha}{\mathcal{H}}^{\alpha}(E)$
for any Borel set $E$. Note also that
$\varphi(B_{\lambda^{t}})=B_{\lambda^{t+1}}$. Applying Proposition 3.6, we
obtain that

$\displaystyle\psi(\mathcal{G}^{-1}(\mathcal{T}))$ $\displaystyle=$
$\displaystyle\int\limits_{0}^{1}\frac{\mathcal{H}^{\alpha}(\varphi^{-1}\mathcal{(}C(\mathcal{T}))\cap{B}_{\lambda^{t}})}{2^{\alpha}\lambda^{t\alpha}}\,dt$
$\displaystyle=$
$\displaystyle\int\limits_{0}^{1}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap{B}_{\lambda^{t+1}})}{2^{\alpha}\lambda^{(t+1)\alpha}}\,dt$
$\displaystyle=$
$\displaystyle\int\limits_{1}^{2}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap{B}_{\lambda^{t}})}{2^{\alpha}\lambda^{t\alpha}}\,dt.$

It follows that

$\sum_{i=0}^{k-1}\psi(\mathcal{G}^{-i}\mathcal{T})=\int\limits_{0}^{k}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap{B}_{\lambda^{t}})}{2^{\alpha}\lambda^{t\alpha}}\,dt.$

Thus, applying the Birkhoff Ergodic Theorem to the system
$(\Omega_{0},\nu,\mathcal{G}^{-1})$ and the function $\psi$, we get that

(5.2)
$\lim\limits_{k\to\infty}\frac{1}{k}\int\limits_{0}^{k}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap{B}_{\lambda^{t}})}{2^{\alpha}\lambda^{t\alpha}}\,dt=\int_{\Omega_{0}}\psi(\mathcal{S})\,d\nu(\mathcal{S})$

for $\nu$-a.e. tiling $\mathcal{T}\in\Omega_{0}$. Substituting $\lambda^{t}=R$
into (5.2), we obtain that

(5.3)
$\int_{\Omega_{0}}\psi(\mathcal{S})\,d\nu(\mathcal{S})=\lim\limits_{z\to\infty}\frac{1}{\log(z)}\int\limits_{1}^{z}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap{B}_{R})}{2^{\alpha}R^{\alpha}}\,\frac{dR}{R}$

for $\nu$-a.e. $\mathcal{T}\in\Omega_{0}$. (Passing from $z=\lambda^{k}$ for
$k\in{\mathbb{N}}$ to an arbitrary $z>0$, $z\to\infty$, in the limit above is
justified, since $\psi$ is a bounded function.)

(3) We have

$\Omega_{\mathcal{G}}=\bigcup_{Q\in{\mathcal{A}}}(\Gamma_{Q}-{\rm supp}(Q)).$

The sets in the right-hand side have intersections of zero $\mu$ measure in
view of (4.1), since ${\mathcal{L}}^{d}(\partial({\rm supp}(Q)))=0$. Consider
the function

$g:=\sum_{Q\in{\mathcal{B}}}\frac{{\mathcal{H}}^{\alpha}(Q)}{{\mathcal{L}}^{d}(Q)}\cdot\chi_{{}_{\Gamma_{Q}-{\rm
supp}(Q)}}\in L^{\infty}(\Omega_{\mathcal{G}},\mu).$

That is, $g({\mathcal{T}})$ is nonzero if and only if the origin lies in a
${\mathcal{T}}$-tile $Q-x$ of type ${\mathcal{B}}$, and then the value of the
function is $\frac{{\mathcal{H}}^{\alpha}(Q)}{{\mathcal{L}}^{d}(Q)}$ (this is
well-defined on a set of full $\mu$ measure). Then (4.1) implies

$\int_{\Omega_{\mathcal{G}}}g({\mathcal{T}})\,d\mu({\mathcal{T}})=\sum_{Q\in{\mathcal{B}}}\mu^{{\rm
tr}}(\Gamma_{Q}){\mathcal{H}}^{\alpha}(Q)=1.$

In view of Lemma 5.3, it suffices to establish the second order ergodic
theorem just for the function $g$.

Given a tiling $\mathcal{T}\in\Omega_{\mathcal{G}}$, denote

$V_{R}({\mathcal{T}})=\int_{{B}_{R}}g({\mathcal{T}}-u)\,du.$

Observe that for every tile $T=Q-x\in{\mathcal{T}}$, with $Q\in{\mathcal{B}}$,
such that ${\rm supp}(T)\subset B_{R}$, integrating $g({\mathcal{T}}-u)$ over
${\rm supp}(T)$ contributes ${\mathcal{H}}^{\alpha}(K_{T})$ to
$V_{R}({\mathcal{T}})$. Exactly the same contribution from $T$ comes to
${\mathcal{H}}^{\alpha}({\mathcal{C}}({\mathcal{T}})\cap B_{R})$. Therefore,
the difference between
${\mathcal{H}}^{\alpha}({\mathcal{C}}({\mathcal{T}})\cap B_{R})$ and
$V_{R}({\mathcal{T}})$ is bounded (in modulus) by the sum of
${\mathcal{H}}^{\alpha}(K_{T})$ over those $T\in{\mathcal{T}}$ of type
${\mathcal{B}}$ whose supports intersect $\partial B_{R}$. Thus, denoting by
$d_{M}$ the maximal diameter of a prototile, we obtain

$\left|\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap
B_{R})-V_{R}(\mathcal{T})\right|\leq{\mathcal{L}}^{d}(B_{R}\setminus
B_{R-d_{M}})\cdot\max_{Q\in{\mathcal{B}}}\frac{{\mathcal{H}}^{\alpha}(Q)}{{\mathcal{L}}^{d}(Q)}=O(R^{d-1}),$

with the implied constant in $O(\cdot)$ depending only on the tiling
${\mathcal{T}}$.

Since $\alpha>d-1$ (one of our standing assumptions), we obtain that

$\lim\limits_{z\to\infty}\frac{1}{\log(z)}\int\limits_{1}^{z}\frac{|\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap
B_{R})-V_{R}(\mathcal{T})|}{2^{\alpha}R^{\alpha+1}}\,dR=0.$

Using Equation (5.3), we conclude that

(5.4)
$\lim\limits_{z\to\infty}\frac{1}{\log(z)}\int\limits_{1}^{z}\frac{\int_{B_{R}}g(\mathcal{T}-u)du}{2^{\alpha}R^{\alpha+1}}\,dR=\int_{\Omega_{0}}\psi(\mathcal{S})\,d\nu(\mathcal{S})$

for $\nu$-a.e. tiling $\mathcal{T}\in\Omega_{0}$. Denote by $Y$ the set of all
tilings in $\Omega_{\mathcal{G}}$ for which Equation (5.4) holds. Observe that
if $\mathcal{T}\in Y$, then $\mathcal{T}-v\in Y$ for any $v\in\mathbb{R}^{d}$
(here we use $\alpha>d-1$ again), i.e. $Y$ is translation-invariant.
Translation invariance of $Y$ implies that
$Y\cap(\Gamma_{Q}-K_{Q})=(Y\cap\Gamma_{Q})-K_{Q}$ for each prototile
$Q\in\mathcal{B}$. Since $\nu(Y\cap\Omega_{0})>0$, there is a prototile
$Q\in\mathcal{B}$ with $\nu(Y\cap(\Gamma_{Q}-K_{Q}))>0$. Then Theorem 4.10(ii)
implies that

$0<\nu(Y\cap(\Gamma_{Q}-K_{Q}))=\nu((Y\cap\Gamma_{Q})-K_{Q})=\mu^{{\rm
tr}}(Y\cap\Gamma_{Q})\cdot{\mathcal{H}}^{\alpha}(K_{Q}),$

hence $\mu^{{\rm tr}}(Y\cap\Gamma_{Q})>0$. Again using translation-invariance
of $Y$ and (4.1) we obtain

$\mu(Y)\geq\mu((Y\cap\Gamma_{Q})-{\rm supp}(Q))=\mu^{{\rm
tr}}(Y\cap\Gamma_{Q})\cdot{\mathcal{L}}^{d}({\rm supp}(Q))>0,$

and ergodicity of the tiling dynamical system
$\Omega_{\mathcal{G}},\mu,{{\mathbb{R}}}^{d})$ implies that (5.4) holds for
$\mu$-a.e. $\mathcal{T}\in\Omega_{\mathcal{G}}$. Setting

$c=\int_{\Omega_{0}}\psi(\mathcal{S})\,d\nu(\mathcal{S}),$

we get the result.

(4) It remains to show that the parameter $c$ can be interpreted as the
average density of the Hausdorff measure on the graph-directed set. Using the
same arguments as in (2) above, we obtain that

$\displaystyle\psi(\mathcal{G}^{k}(\mathcal{T}))$ $\displaystyle=$
$\displaystyle\int\limits_{0}^{1}\frac{\mathcal{H}^{\alpha}(\varphi^{k}(\mathcal{C}(\mathcal{T}))\cap
B_{\lambda^{t}})}{2^{\alpha}\lambda^{t\alpha}}\,dt$ $\displaystyle=$
$\displaystyle\int\limits_{0}^{1}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap
B_{\lambda^{t-k}})}{2^{\alpha}\lambda^{(t-k)\alpha}}\,dt$ $\displaystyle=$
$\displaystyle\int\limits_{-k}^{-k+1}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap
B_{\lambda^{t}})}{2^{\alpha}\lambda^{t\alpha}}\,dt.$

Applying the Birkhoff Ergodic Theorem to the system
$(\Omega_{0},\nu,\mathcal{G})$ and the function $\psi$, we see that for
$\nu$-a.e. $\mathcal{T}\in\Omega_{0}$,

(5.5)
$\lim\limits_{k\to\infty}\frac{1}{k}\int_{-k}^{0}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap
B_{\lambda^{t}})}{2^{\alpha}\lambda^{t\alpha}}\,dt=\lim\limits_{k\to\infty}\frac{1}{k}\int_{0}^{k}\frac{\mathcal{H}^{\alpha}(\mathcal{C}(\mathcal{T})\cap
B_{\lambda^{-t}})}{2^{\alpha}\lambda^{-t\alpha}}\,dt=c.$

We have

$\Omega_{0}=\bigcup_{Q\in{\mathcal{B}}}(\Gamma_{Q}-K_{Q}),$

and the sets in the right-hand side have intersections of zero $\nu$ measure,
in view of Theorem 4.10(ii) and (3.4). Then the set of tilings
${\mathcal{T}}\in\Omega_{0}$, such that (5.5) holds and ${\mathcal{T}}$
belongs to $\Gamma_{Q}-{\mathcal{K}}_{Q}$ for a unique $Q\in{\mathcal{B}}$,
has full $\nu$ measure. Denote this set of tilings by $Z$. Observe that the
behavior of the limit in (5.5) depends only on the small neighborhood of the
origin (because the limit doesn’t change if we replace $\int_{0}^{k}$ by
$\int_{i}^{k}$ for any fixed $i\in{\mathbb{N}}$), hence ${\mathcal{T}}-u\in Z$
for $T\in\Gamma_{Q}$ and $u\in K_{Q}$ implies ${\mathcal{T}}^{\prime}-u\in Z$
for any ${\mathcal{T}}^{\prime}\in\Gamma_{Q}$. Thus, for every
$Q\in{\mathcal{B}}$,

$Z\cap(\Gamma_{Q}-K_{Q})=\Gamma_{Q}-K_{Q}^{\prime}$

for some $K_{Q}^{\prime}\subset K_{Q}$. We have

$\displaystyle\mu^{{\rm tr}}(\Gamma_{Q})\cdot{\mathcal{H}}^{\alpha}(K_{Q})$
$\displaystyle=$ $\displaystyle\nu(\Gamma_{Q}-K_{Q})$ $\displaystyle=$
$\displaystyle\nu(Z\cap(\Gamma_{Q}-K_{Q}))$ $\displaystyle=$
$\displaystyle\nu(\Gamma_{Q}-K_{Q}^{\prime})$ $\displaystyle=$
$\displaystyle\mu^{{\rm
tr}}(\Gamma_{Q})\cdot{\mathcal{H}}^{\alpha}(K_{Q}^{\prime}).$

It follows that ${\mathcal{H}}^{\alpha}$-a.e. $u\in K_{Q}$ is such that
${\mathcal{T}}-u\in Z$ for $T\in\Gamma_{Q}$, which means, rewriting (5.5),
that

$c=\lim\limits_{k\to\infty}\frac{1}{k}\int_{0}^{k}\frac{\mathcal{H}^{\alpha}(K_{Q}\cap
B_{\lambda^{-t}}(u))}{2^{\alpha}\lambda^{-t\alpha}}\,dt\ \ \mbox{for\
${\mathcal{H}}^{\alpha}$-a.e.\ $u\in K_{Q}$,\ for all\ $Q\in\mathcal{B}$},$

as desired. The proof is complete. ∎

######  Remark 5.6.

1\. Since there exists $f\in L^{1}(\Omega_{\mathcal{G}},\mu)$ such that
$0<\int_{\Omega_{\mathcal{G}}}f\,d\mu<\infty$, it is immediate that the
paramaters $\alpha$ and $c$ in Theorem 5.5 are invariants of measure-theoretic
isomorphism.

2\. We considered averaging over Euclidean balls in Theorem 5.5. This was
needed in the equality $\varphi(B_{R})=B_{\lambda R}$. If we restrict
ourselves to the case when $\varphi$ is a pure dilation, i.e.
$\varphi(x)=\lambda x$ for $\lambda>1$, then we can use averaging over balls
in any norm.

##  6\. Substitution Dynamical Systems

In this section, we derive the second order ergodic theorem for a class of
one-dimensional substitution systems. We begin with a brief review of the
background. This will be reminiscent of our discussion of the structure of
tiling substitutions, however, there are certain fundamental differences. One
of the principal differences between symbolic substitution systems and their
tiling counterparts is that symbolic substitutions may have finite ergodic
invariant measures supported off the minimal components.

Now $\mathcal{A}$ is a finite alphabet (usually
${\mathcal{A}}=\\{1,\ldots,N\\}$) and $\mathcal{A}^{+}$ is the set of all
finite non-empty words over $\mathcal{A}$. A map
$\sigma:\mathcal{A}\rightarrow\mathcal{A}^{+}$ is called a substitution; it is
extended to $\mathcal{A}^{+}$ by concatenation. Given two words
$v,w\in\mathcal{A}^{+}$, we will write $v\prec w$ if $v$ is a subword of $w$.
Denote by $L(\sigma)$ the set of all words $w\in\mathcal{A}^{+}$ such that
$w\prec\sigma^{n}(a)$ for some $a\in\mathcal{A}$ and $n\geq 1$. The family
$L(\sigma)$ is called the language of the substitution. For a word $w$, its
length will be denoted by $|w|$.

######  Definition 6.1.

The substitution dynamical system determined by a substitution $\sigma$ is a
pair $(X_{\sigma},S)$, where

$X_{\sigma}=\\{x\in\mathcal{A}^{\mathbb{Z}}:\ x[-n,n]\in L(\sigma)\mbox{ for
all }n\geq 1\\}$

and $S:\mathcal{A}^{\mathbb{Z}}\rightarrow\mathcal{A}^{\mathbb{Z}}$ is the
left shift. The set $X_{\sigma}$ is $S$-invariant and closed in
$\mathcal{A}^{\mathbb{Z}}$ with respect to the product topology.

Given $a,b\in{\mathcal{A}}$, denote by $m_{a,b}$ the number of occurrences of
$a$ in the word $\sigma(b)$. The matrix
$M_{\sigma}=(m_{a,b})_{a,b\in\mathcal{A}}$ is the substitution matrix of
$\sigma$. Reordering the letters in the alphabet $\mathcal{A}$, the matrix
$M_{\sigma}$ can be transformed to have an upper block-triangular form as in
(2.5). The diagonal matrices $F_{i}$ determine the structure of invariant
subsets and the spectral properties of $F_{i}$ determine the structure of
invariant measures. We will not discuss these results here and refer the
reader to [BKMS] for details.

Our approach to the second order ergodic theorem of substitution systems is
based on Theorem 5.5, which we apply to the self-similar substitution system
on the line ${{\mathbb{R}}}$, arising from the symbolic substitution system
$(X_{\sigma},S)$ as a suspension flow. For this to exist, however, it is
necessary and sufficient that the substitution matrix $M_{\sigma}$ should have
a strictly positive left eigenvector, whose components will serve as the
lengths of the prototiles. This is a significant restriction: it is known that
a strictly positive left eigenvector for the matrix $M_{\sigma}$ in the form
(2.5) exists if and only if all the matrices $F_{1},\ldots,F_{s}$,
corresponding to the minimal components, have the same spectral radius, which
is strictly greater than the spectral radii of all the remaining diagonal
blocks $F_{s+1},\ldots,F_{m}$, see [G, Th.III.6, p.92].

Standing assumption. We will assume for simplicity that

(6.1) $M_{\sigma}=\left(\begin{array}[]{cc}A&C\\\ 0&B\end{array}\right),$

where $A$ and $B$ are primitive, with $\rho(A)>\rho(B)>1$, and $C$ is non-
zero. We expect that our method works in the more general case, when
$M_{\sigma}$ has a strictly positive left eigenvector, but we have not
verified the details.

Under our standing assumption, plus a technical condition stated below, the
system $(X_{\sigma},S)$ has a unique, up to scaling, invariant measure that is
positive and finite on at least one open set, and this measure is infinite
$\sigma$-finite. This follows from Corollary 5.6 in [BKMS] in the case when
the substitution system is non-periodic. The non-periodicity was needed to
ensure the recognizability property [BKM, Theorem 5.17], however, it is
possible to extend the proof of Theorem 5.17 from [BKM] to the needed
generality.

First we need a technical lemma. Given two sequences $\\{x_{n}\\}$ and
$\\{y_{n}\\}$ of reals, the notation $x_{n}\approx y_{n}$ means that
$x_{n}/y_{n}\to 1$ as $n\to\infty$.

######  Lemma 6.2.

Let $\mathcal{A}=\\{1,2,\ldots,N\\}$ be a finite alphabet and
$\sigma:\mathcal{A}\rightarrow\mathcal{A}^{+}$ a substitution with the
substitution matrix of the form (6.1). Assume that the matrices $A$ and $B$
are primitive and $\rho(A)>\rho(B)>1$. Then

(6.2) $|\sigma^{k}(i)|\approx\xi_{i}\rho(A)^{k},\ \ i=1,\ldots,N,$

where $\overline{\xi}=(\xi_{i})_{i=1}^{N}$ is a left Perron-Frobenius
eigenvector for $M=M_{\sigma}$, i.e.

$[\xi_{1}\ldots\xi_{N}]M=\rho(A)[\xi_{1}\ldots\xi_{N}].$

###### Proof.

We have $|\sigma^{k}(i)|=\langle M^{k}{\bf e}_{i},\overline{1}\rangle$ where
${\bf e}_{i}$ is the $i$-th unit vector and $\overline{1}=[1\ldots 1]^{t}$.
Asymptotics of the entries of powers of a non-negative (not necessarily
irreducible) matrix are known. It follows e.g. from Theorem (9.4) in [S] that
there exist $\xi_{i}>0$ such that $|\sigma^{k}(i)|\approx\xi_{i}\rho(A)^{k}$,
$i\leq N$. It remains to show that $\overline{\xi}=\\{\xi_{i}\\}$ is a left
eigenvector.

Notice that

$M^{k+1}{\bf e}_{j}=\sum_{i=1}^{N}M(i,j)M^{k}{\bf e}_{i}.$

Hence

$\langle M^{k+1}{\bf e}_{j},\overline{1}\rangle=\sum_{i=1}^{N}\langle
M^{k}{\bf e}_{i},\overline{1}\rangle M(i,j),$

which implies

$\xi_{j}\rho(A)^{k+1}\approx\sum_{i=1}^{N}\xi_{i}\rho(A)^{k}M(i,j)\mbox{ as
}k\to\infty.$

This implies that $\overline{\xi}$ is a left eigenvector for $M$, as desired.
∎

######  Definition 6.3.

Set $\lambda=\rho(A)$. Let $\overline{\xi}$ be the left eigenvector for the
matrix $M_{\sigma}$ in the lemma above, satisfying (6.2). For each letter
$a\in\mathcal{A}$, denote by $I_{a}$ the interval of length $\xi_{a}$ centered
at the origin. We will consider these intervals as tiles in $\mathbb{R}$,
labeled by their letters. Set $\varphi(x)=\lambda x$. Define the tile
substitution $\mathcal{G}$ on the tiles $\\{I_{a}\\}_{a\in{\mathcal{A}}}$ as
follows. Consider the inflated tile $\varphi(I_{v})=\lambda I_{v}$. Since

$\textrm{length}(\lambda
I_{v})=\lambda\xi_{v}=\sum_{w\in\mathcal{A}}M(w,v)\xi_{w},$

we can subdivide the interval $\lambda I_{v}$ into the intervals $\\{I_{w}\\}$
according to the sequence of all the letters of $\sigma(v)$. Define
$\mathcal{G}(I_{v})$ as the collection of the corresponding translates of the
intervals $\\{I_{w}\\}_{w\in\sigma(v)}$. We will call $\mathcal{G}$ the tile
substitution associated with $\sigma$ and denote by $\Omega_{\mathcal{G}}$ the
corresponding tiling space.

Denote by ${\mathcal{B}}$ the set of letters corresponding to the matrix $B$.

######  Lemma 6.4.

(i) The tiling substitution ${{\mathbb{R}}}$-action
$(\Omega_{\mathcal{G}},{{\mathbb{R}}})$ is isomorphic (canonically
topologically conjugate) to the suspension flow over the symbolic substitution
${\mathbb{Z}}$-action $(X_{\sigma},S)$, with the “roof function” equal to the
constant $\xi_{j}>0$ on the cylinder sets $[j]$ for $j\in{\mathcal{A}}$.

(ii) Assume that the substitution ${\mathcal{G}}$ satisfies the conditions of
Section 2.3. Then there is a unique infinite ($\sigma$-finite) invariant
measure $\nu$ for the system $(X_{\sigma},S)$, normalized so that

$\sum_{b\in{\mathcal{B}}}\xi_{b}\nu([b])=1.$

This measure may be identified with the transverse measure $\mu^{{\rm tr}}$ of
the invariant measure $\mu$ for the system
$(\Omega_{\mathcal{G}},{{\mathbb{R}}})$, normalized so that
$\mu(\Omega_{\mathcal{B}})=1$, where $\Omega_{\mathcal{B}}$ is the set of
tilings from $\Omega_{\mathcal{G}}$ having a tile of type ${\mathcal{B}}$
containing the origin.

###### Proof.

This follows from definitions and the results of [CS]. We just observe that
the transversal of $\Omega_{\mathcal{G}}$ may be naturally identified with
$X_{\sigma}$, and transversal measures correspond to invariant measures for
$(X_{\sigma},S)$. ∎

For the technical assumptions from Section 2.3 to hold, it is enough that

(6.3) $\forall\,b\in{\mathcal{B}},\ \sigma(b)\ \mbox{starts and ends with a
letter from}\ {\mathcal{B}},$

and

(6.4) $\forall\,b\in{\mathcal{B}},\ \exists\,k\in{\mathbb{N}}\ \mbox{such
that}\ \sigma^{k}(b)\ \mbox{has at least one ``interior'' letter from}\
{\mathcal{B}}.$

######  Definition 6.5.

We will call a substitution $\sigma$ admissible if it has the form (6.1), with
$\rho(A)>\rho(B)>1$, and both (6.3) and (6.4) are satisfied.

######  Remark 6.6.

Actually, condition (6.3) may be omitted: it implies the “non-periodic border
condition”, see Definition 2.11, which was needed for recognizability of non-
periodic tilings. In fact, in the setting of one-dimensional self-similar
tiling substutions, the proof of recognizability from [CS] works without it.

Let $(X,T,\nu)$ be an infinite ergodic measure-preserving transformation. The
system is called conservative if it has no wandering sets of positive measure,
i.e. there is no set $W\subset X$ with $\nu(W)>0$ and $W\cap
T^{-n}W=\emptyset$ for every $n\geq 1$. We need conservativity of our systems,
since we will consider one-sided averages for the substitution
${\mathbb{Z}}$-action.

######  Lemma 6.7.

The substitution dynamical system with an infinite invariant measure
$(X_{\sigma},\nu,S)$ , corresponding to an admissible substitution $\sigma$,
is conservative.

###### Proof.

We will use Maharam’s recurrence theorem (see [A, 1.1.7]), which says that if
there exists a subset $Y$ of finite measure, such that
$X_{\sigma}=\bigcup_{n=0}^{\infty}S^{-n}Y$ mod $\nu$, then $S$ is
conservative. Let $Y$ be the set of sequences $(y_{n})_{n\in{\mathbb{Z}}}\in
X_{\sigma}$ such that $y_{1}\in{\mathcal{B}}$. Then $\nu(Y)<\infty$ by Lemma
6.4. We have $y\not\in\bigcup_{n=0}^{\infty}S^{-n}Y$ if and only if there
exists $k\in{\mathbb{Z}}$ such that
$y_{n}\in{\mathcal{A}}\setminus{\mathcal{B}}$ for all $n>k$. Since $\nu$ is
supported on the set of sequences which contain at least one
${\mathcal{B}}$-symbol, it suffices to show that

$\nu(Y_{0})=0,\ \ \mbox{where}\ \ Y_{0}=\\{x\in X_{\sigma}:\
x_{n}\in{\mathcal{A}}\setminus{\mathcal{B}}\ \mbox{for all}\ n>0\ \mbox{and}\
x_{0}\in{\mathcal{B}}\\}.$

For every $y\in Y_{0}$ and $n>0$ there exist $b\in\mathcal{B}$ and
$i=0,\ldots,|\sigma^{n}(b)|-1$ such that $y\in S^{i}[\sigma^{n}(b)]$, where
$[\sigma^{n}(b)]=\\{x\in X_{\sigma}:x[0,|\sigma^{n}(b)|-1]=\sigma^{n}(b)\\}$.
Since every word $\sigma^{n}(b)$, $b\in\mathcal{B}$, ends with a letter from
$\mathcal{B}$, we immediately get that $i=|\sigma^{n}(b)|-1$. It follows that
$Y_{0}\subset\bigcup_{b\in{\mathcal{B}}}\bigcap_{n\geq
1}S^{|\sigma^{n}(b)|-1}[\sigma^{n}(b)]$.

Since the measure $\nu$ is non-atomic, we have that

$\nu(S^{|\sigma^{n}(b)|-1}[\sigma^{n}(b)])=\nu([\sigma^{n}(b)])\to 0\mbox{ as
}n\to\infty.$

This yields the result. ∎

The following simple “folklore” lemma gives the so-called “accordion”
representation of words from $X_{\sigma}$.

######  Lemma 6.8.

Let $x\in X_{\sigma}$ and $n\geq 1$. Then

(6.5)
$x[1,n]=u_{0}\sigma(u_{1})\sigma^{2}(u_{2})\ldots\sigma^{m}(u_{m})\sigma^{m}(v_{m})\sigma^{m-1}(v_{m-1})\ldots\sigma(v_{1})v_{0},$

where $m\geq 1$ and $u_{i},v_{j},\ i,j=1,\ldots,m$, are subwords (possibly
empty) of $\sigma(a)$, $a\in\mathcal{A}$. Moreover, at least one of
$u_{m},v_{m}$ is nonempty.

###### Proof.

Set $w=x[1,n]$. By the definition of $X_{\sigma}$, we can choose
$a\in{\mathcal{A}}$ and the minimal $k\in{\mathcal{N}}$ such that
$w\prec\sigma^{k}(a)$. Writing $\sigma^{k-1}(a)=a_{1}\ldots a_{m}$ we obtain
that $w\prec\sigma(a_{1})\ldots\sigma(a_{m})$, hence

$w=u_{0}\sigma(w^{(1)})v_{0},$

where $w^{(1)}$ is a subword $\sigma^{k-1}(a)$ (possibly empty), $u_{0}$ is a
suffix of some $\sigma(a_{i})$ (possibly empty), and $v_{0}$ is a prefix of
some $\sigma(a_{j})$ (possibly empty). Repeating this process with $w^{(1)}$,
etc., by induction, we obtain the desired representation (6.5). ∎

For a word $w\in{\mathcal{A}}^{+}$ we define its “population vector” by
$\overline{\ell}(w)=(\ell_{i}(w))_{i=1}^{N}$ where $\ell_{i}(w)$ is the number
of symbols $i$ in the word $w$. For $w\in{\mathcal{A}}^{+}$ denote

(6.6) $|w|_{\mathcal{T}}:=\langle\overline{\ell}(w),\overline{\xi}\rangle$

and call this quantity the tiling length of the word $w$. Note that
$\overline{\ell}(\sigma(w))=M_{\sigma}\overline{\ell}(w)$ by definition of the
substitution matrix.

######  Lemma 6.9.

Let $\sigma$ be an admissible substitution. Then for any $x\in X_{\sigma}$ we
have

$\lim_{n\to\infty}\frac{|x[1,n]|_{\mathcal{T}}}{n}=1.\ $

###### Proof.

Given $x\in X_{\sigma}$ and $n\geq 1$, consider the accordion representation
(6.5). Note that for all $i$,

$|u_{i}|,|v_{i}|\leq\max_{a}|\sigma(a)|=:L_{\max}.$

Recall that for each letter $a\in{\mathcal{A}}$ we have
$|\sigma^{k}(a)|\approx\xi_{a}\lambda^{k}=\lambda^{k}|a|_{\mathcal{T}}$ by
Lemma 6.2. Hence

(6.7) $|\sigma^{k}(u)|\approx\lambda^{k}|u|_{\mathcal{T}},\ \ k\to\infty,$

uniformly for all $u$ with $|u|\leq L_{\max}$. Note also

$\langle\overline{\ell}(\sigma^{k}(j)),\overline{\xi}\rangle=\langle
M_{\sigma}^{k}{\bf e}_{j},\overline{\xi}\rangle=\langle{\bf
e}_{j},(M_{\sigma}^{t})^{k}\overline{\xi}\rangle=\langle{\bf
e}_{j},\lambda^{k}\overline{\xi}\rangle=\lambda^{k}\xi_{j},$

which yields $|\sigma^{k}(u)|_{\mathcal{T}}=\lambda^{k}|u|_{\mathcal{T}}$.
Using the accordion representation of $x[1,n]$, we obtain

$\frac{|x[1,n]|_{\mathcal{T}}}{n}=\frac{\sum_{i=0}^{m}\lambda^{i}|u_{i}|_{\mathcal{T}}+\sum_{i=0}^{m}\lambda^{i}|v_{i}|_{\mathcal{T}}}{\sum_{i=0}^{m}|\sigma^{i}(u_{i})|+\sum_{i=0}^{m}|\sigma^{i}(v_{i})|}\,.$

Now the desired statement follows from (6.7) and the fact that $m\to\infty$ as
$n\to\infty$ and at least one of $u_{m},v_{m}$ is nonempty. ∎

The next lemma gives an upper bound for the number of $\mathcal{B}$-tiles in
the interval $[0,t]$. Recall that $\Omega_{\mathcal{G}}$ is the tiling space
of $\mathcal{G}$, the tile substitution associated with $\sigma$. Given
$\mathcal{T}\in\Omega_{\mathcal{G}}$, denote by
$N_{\mathcal{T}}({\mathcal{B}},t)$ the total number of ${\mathcal{B}}$-tiles
of ${\mathcal{T}}$, contained (completely) in the interval $[0,t]$.

######  Lemma 6.10.

There exists a constant $K>0$ such that for every
$\mathcal{T}\in\Omega_{\mathcal{G}}$ and $t>0$, we have
$N_{\mathcal{T}}({\mathcal{B}},t)\leq Kt^{\alpha}$, where
$\alpha=\log(\rho(B))/\log(\rho(A))$.

###### Proof.

Since the inequality will persist (with a slightly larger constant $K$) if we
shift ${\mathcal{T}}$ by a fixed vector, we can assume that ${\mathcal{T}}$
belongs to the transversal of $\Omega_{\mathcal{G}}$. For every integer $s>0$,
find a tiling $\mathcal{T}_{s}$ such that
$\mathcal{G}^{s}(\mathcal{T}_{s})=\mathcal{T}$, see Proposition 2.8. Choose an
integer $k>0$ such that $\rho(A)^{k}\xi_{i}>2$ for every $i\in\mathcal{A}$.
Let $T_{s}$ be the tile of ${\mathcal{T}}_{s}$ containing the origin; it is
centered at the origin for all $s$: since ${\mathcal{T}}$ is in the
transversal, all $T_{s}$ are actual prototiles, see Definition 6.3. Then the
interval $[0,\rho(A)^{s}]$ is covered by the patch $\mathcal{G}^{s+k}(T_{s})$
by our choice of $k$. Thus, $N_{\mathcal{T}}({\mathcal{B}},\rho(A)^{s})$ does
not exceed the number of occurrences of $\mathcal{B}$-tiles in the patch
$\mathcal{G}^{s+k}(T_{s})$. By the Perron-Frobenius theorem applied to the
primitive matrix $B$, the number of $\mathcal{B}$-tiles in
$\mathcal{G}^{s+k}(T_{s})$ asymptotically grows not faster than $K\rho(B)^{s}$
for some constant $K$ independent of $s$. The constant $K$ can be adjusted so
that $N_{\mathcal{T}}({\mathcal{B}},\rho(A)^{s})\leq K\rho(B)^{s}$ for every
tiling $\mathcal{T}$ and every positive real number $s$. Setting
$t=\rho(A)^{s}$, noting that $\rho(A)^{\alpha}=\rho(B)$ and adjusting the
constant again, we obtain the desired inequality for all $t>0$. ∎

Now we are ready to prove the main result on substitutions. It will be
convenient to write elements of $X_{\sigma}$ as $(x(n))_{n\in{\mathbb{Z}}}$.

######  Theorem 6.11.

Let $\sigma:\mathcal{A}\rightarrow\mathcal{A}^{+}$ be an admissible
substitution, see Definition 6.5. Let $\nu$ be the infinite invariant measure
on $X_{\sigma}$ from Lemma 6.4.

Then for every function $f\in L^{1}(X_{\sigma},\nu)$ and $\nu$-a.e. $x\in
X_{\sigma}$, we have that

$\int_{X_{\sigma}}f(y)d\nu(y)=\lim\limits_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{\sum_{i=0}^{k-1}f(S^{i}x)}{ck^{\alpha}}\,\frac{1}{k}\,,$

where $\alpha=\log(\rho(B))/\log(\rho(A))$ and $c>0$ is the right average
$\alpha$-dimensional density of ${\mathcal{H}}^{\alpha}$ restricted to any of
the graph-directed sets associated with $\mathcal{G}$.

###### Proof.

(1) Consider the one-dimensional tile substitution system
$(\Omega_{\mathcal{G}},\mathbb{R})$ associated with $\mathcal{G}$, see
Definition 6.3 and Lemma 6.4. Denote by $\mu$ the (unique) translation-
invariant measure on $\Omega_{\mathcal{G}}$ corresponding to $\nu$. Recall
that $X_{\sigma}$ can be identified with the transversal of
$\Omega_{\mathcal{G}}$. More precisely, for $x\in X_{\sigma}$, let
${\mathcal{T}}(x)\in\Omega_{\mathcal{G}}$ be the tiling, which has the
prototile $I_{x(0)}$ as its tile, and the other tiles are $I_{x(n)}+y_{n}$, so
that the left endpoint of $I_{x(n+1)}+y_{n+1}$ is the right endpoint of
$I_{x(n)}+y_{n}$ for all $n\in{\mathbb{Z}}$.

(2) In view of Theorem 4 in [Fi1], which is a one-sided version of Lemma 5.3,
it is enough to establish the result for a single function $f\in
L^{1}(X_{\sigma},\nu)$ with $\int fd\nu\neq 0$. Theorem 4 from [Fi1] was
established under the assumption that the system is conservative, so we use
Lemma 6.7 here. Consider the function $f$ on $X_{\sigma}$ given by: $f(x)=1$
if $x(1)\in\mathcal{B}$ and $f(x)=0$ otherwise.

Let $F$ be the function on $\Omega_{\mathcal{G}}$ such that
$F(\mathcal{T})=1/\xi_{i}$ if the tile of $\mathcal{T}$ containing the origin
is a translate of $I_{i}$ for some $i\in\mathcal{B}$, and $F(\mathcal{T})=0$
otherwise. This is well-defined $\mu$-a.e. Repeating the arguments of Theorem
5.5, we obtain that for $\mu$-a.e. tiling
$\mathcal{T}\in\Omega_{\mathcal{G}}$,

(6.8)
$\lim\limits_{t\to\infty}\frac{1}{\log(t)}\int_{1}^{t}\frac{\int_{0}^{R}F(\mathcal{T}-u)\,du}{R^{\alpha+1}}\,dR=c\int_{\Omega_{\mathcal{G}}}F(\mathcal{S})\,d\mu(\mathcal{S}):=\theta>0,$

where $\alpha=\log(\rho(B))/\log(\rho(A))$ and $c>0$ is the right average
$\alpha$-dimensional density of ${\mathcal{H}}^{\alpha}$ restricted to any of
the graph-directed sets associated with $\mathcal{G}$

Recall that $N_{\mathcal{T}}({\mathcal{B}},R)$ is the number of
${\mathcal{B}}$-tiles contained in $[0,R]$. Thus,

$N_{\mathcal{T}}({\mathcal{B}},R)\leq\int_{0}^{R}F(\mathcal{T}-u)\,du\leq
N_{\mathcal{T}}({\mathcal{B}},R)+1.$

Since $\mu$ is (locally) a product of the transverse measure $\nu$ and the
Lebesgue measure on $\mathbb{R}$, it follows from Equation (6.8) that for
$\nu$-a.e. $x\in X_{\sigma}$,

(6.9)
$\lim\limits_{t\to\infty}\frac{1}{\log(t)}\int_{0}^{t}\frac{N_{{\mathcal{T}}(x)}({\mathcal{B}},R)}{R^{\alpha+1}}\,dR=\theta.$

(3) We want to show that

$\theta=\lim_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{\sum_{i=0}^{k-1}f(S^{i}x)}{k^{\alpha+1}}$

for all $x\in X_{\sigma}$ satisfying Equation (6.9). Denote by
$\ell_{\mathcal{B}}(w)$ the number of ${\mathcal{B}}$-letters in a word
$w\in{\mathcal{A}}^{+}$, and observe that

$\sum_{i=0}^{k-1}f(S^{i}x)=\ell_{\mathcal{B}}(x[1,k]).$

Note that (6.9) is equivalent to

$\lim_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{N_{{\mathcal{T}}(x)}({\mathcal{B}},k)}{k^{\alpha+1}}=\theta,$

so we just need to estimate
$|N_{{\mathcal{T}}(x)}({\mathcal{B}},k)-\ell_{\mathcal{B}}(x[1,k])|$. We claim
that

(6.10) $\ell_{\mathcal{B}}(x[1,k])=N_{\mathcal{B}}({\mathcal{T}}(x),R_{k}),\ \
\ \mbox{where}\ \ R_{k}=|x[1,k]|_{\mathcal{T}}+(1/2)\xi_{x(0)}.$

Indeed, the left-hand side represents the number of ${\mathcal{B}}$-letters in
$x[1,k]$ and the right-hand side equals the number of ${\mathcal{B}}$-tiles,
(completely) contained in the interval $[0,R_{k}]$. According to the
definition of ${\mathcal{T}}(x)$ at the beginning of the proof, it has the
prototile $I_{x(0)}$ centered at the origin, so that half of its length
$(1/2)\xi_{x(0)}$ is in $[0,R_{k}]$. After that the sequence of tiles which
fits in $[0,R_{k}]$ exactly corresponds to $x[1,k]$, by the definition of the
tile length. Thus, both sides of (6.10) count the same quantity.

Now, by Lemma 6.9 we have $R_{k}\approx k$, hence $R_{k}=k+o(k)$, as
$k\to\infty$, using the standard $o(\cdot)$ notation. In view of (6.10) and
Lemma 6.10, we have

$\displaystyle|N_{{\mathcal{T}}(x)}({\mathcal{B}},k)-\ell_{\mathcal{B}}(x[1,k])|$
$\displaystyle=$
$\displaystyle|N_{{\mathcal{T}}(x)}({\mathcal{B}},k)-N_{{\mathcal{T}}(x)}({\mathcal{B}},R_{k})|$
$\displaystyle\leq$ $\displaystyle K|R_{k}-k|^{\alpha}+1=o(k^{\alpha}).$

Indeed,
$N_{{\mathcal{T}}(x)}({\mathcal{B}},R_{k})-N_{{\mathcal{T}}(x)}({\mathcal{B}},k)$
equals the number of ${\mathcal{B}}$-tiles of ${\mathcal{T}}(x)$ in the
interval $[k,R_{k}]$ (assume that $k\leq R_{k}$ for definiteness) plus one, if
a ${\mathcal{B}}$-tile contains $k\in{{\mathbb{R}}}$ in its interior, and the
number of ${\mathcal{B}}$-tiles of ${\mathcal{T}}(x)$ in the interval
$[k,R_{k}]$ equals $N_{\mathcal{B}}({\mathcal{T}}(x)-k,R_{k}-k)$, to which we
can apply Lemma 6.10. Thus,

$\displaystyle\lim_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{\sum_{i=0}^{k-1}f(S^{i}x)}{k^{\alpha+1}}$
$\displaystyle=$
$\displaystyle\lim_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{\ell_{\mathcal{B}}(x[1,k])}{k^{\alpha+1}}$
$\displaystyle=$
$\displaystyle\lim_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{N_{{\mathcal{T}}(x)}({\mathcal{B}},k)}{k^{\alpha+1}}$
$\displaystyle+$
$\displaystyle\lim_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{o(k^{\alpha})}{k^{\alpha+1}}=\theta+0,$

as desired. Noticing that

$\theta=c\int_{\Omega_{\mathcal{G}}}F\,d\mu=c\sum_{b\in\mathcal{B}}\nu([b])=c\int_{X_{\sigma}}f\,d\nu$

by Lemma 6.4, we get the result. ∎

######  Remark 6.12.

(1) We note that the parameters $\alpha$ and $c$ appearing in the second order
ergodic theorem are invariants of the measure-theoretical isomorphism between
infinite measure preserving systems. This is immediate, since there exists
$f\in L^{1}(X_{\sigma},\nu)$ such that $\int_{X_{\sigma}}fd\nu$ is positive
and finite.

As an example, consider two symbolic substitution systems on the alphabet
$\mathcal{A}=\\{0,1\\}$ given by $\sigma_{1}(0)=0^{3}$ (three zeros),
$\sigma_{1}(1)=101$; and $\sigma_{2}(0)=0^{9}$, $\sigma_{2}(1)=1^{4}01^{4}$.
Then, $\alpha_{1}=\log(2)/\log(3)$, whereas $\alpha_{2}=\log(8)/\log(9)$.
Since $\alpha_{1}\neq\alpha_{2}$, these systems cannot be measure-
theoretically isomorphic with respect to the invariant infinite measures, and
hence, cannot be topologically conjugate.

The parameter $c$ can also be used to distinguish substitution systems,
although the computation is more involved. For example, consider for
$k=0,\ldots,3$ the substitutions $\sigma_{k}(0)=0^{9}$ and
$\sigma_{k}(1)=10^{k}10^{6-k}1$. For all of them we have $\alpha=1/2$, but the
average densities of the corresponding graph-directed sets are likely to be
different, which would imply that the substitution dynamical systems
associated with $\sigma_{k}$ are pairwise non-isomorphic.

(2) In general, symmetric and one-sided average densities need not be equal,
except in symmetric cases, such as the middle-thirds Cantor set.

As a corollary of Theorem 6.11, we establish that almost every sequence in
$X_{\sigma}$ admits an “$\alpha$-dimensional frequency”.

######  Corollary 6.13.

Let $(X_{\sigma},\nu,S)$ be a substitution system satisfying the assumptions
of Theorem 6.11. Then for every letter $b\in\mathcal{B}$, the limit

$\lim\limits_{n\to\infty}\frac{1}{\log(n)}\sum_{1\leq k\leq
n,\;x_{k}=b}\frac{1}{k^{\alpha}}$

exists and equals to $\alpha\cdot c\cdot\nu([b])$ for $\nu$-a.e. $x=(x_{k})\in
X_{\sigma}$.

###### Proof.

We will use the same notation as in the proof of Theorem 6.11. Fix a letter
$b\in\mathcal{B}$. Consider the function $f:X_{\sigma}\rightarrow\mathbb{R}$
such that $f(x)=1$ if $x_{0}=b$ and $f(x)=0$ otherwise. Given a sequence $x\in
X_{\sigma}$, denote by $\ell_{b}(x,k)=\ell_{b}(x[1,k])$ the number of
occurrences of the symbol $b$ in the word $x[1,k]$. Theorem 6.11 implies that

(6.11)
$\lim_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{\infty}\frac{\ell_{b}(x,k)}{k^{\alpha+1}}=c\nu([b])$

for $\nu$-a.e. $x\in X_{\sigma}$. Fix a sequence $x\in X_{\sigma}$ satisfying
Equation (6.11). Using summation by parts, we get

$\sum_{k=1}^{n}\frac{f(S^{k}x)}{k^{\alpha}}=\sum_{k=1}^{n-1}\ell_{b}(x,k)\left(\frac{1}{k^{\alpha}}-\frac{1}{(k+1)^{\alpha}}\right)+\frac{\ell_{b}(x,n)}{n^{\alpha}}.$

Lemmas 6.9 and 6.10 imply that $\ell_{b}(x,n)/\alpha^{d}$ is uniformly bounded
in $n$. Notice that
$\left(\frac{1}{k^{\alpha}}-\frac{1}{(k+1)^{\alpha}}\right)\approx\frac{\alpha}{k^{\alpha+1}}.$
Thus, (6.11) yields

$\displaystyle\lim\limits_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\frac{f(S^{k}x)}{k^{\alpha}}$
$\displaystyle=$
$\displaystyle\lim\limits_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1}^{n}\ell_{b}(x,k)\frac{d}{k^{\alpha+1}}$
$\displaystyle=$ $\displaystyle\alpha\int fd\nu=\alpha\cdot c\cdot\nu([b])$

for $\nu$-a.e. $x\in X_{\sigma}$. ∎

This may be compared with a result of [Be], which implies that all “morphic”
sequences $x$ have the logarithmic frequency of letters. This means that for
$a\in\mathcal{A}$ the following limit exists:

$\lim\limits_{n\to\infty}\frac{1}{\log(n)}\sum_{k=1,\;x_{k}=a}^{n}\frac{1}{k}\,.$

For our substitutions it is immediate that the logarithmic frequency of
$b\in{\mathcal{B}}$ is zero for all $x\in X_{\sigma}$, since already the
ordinary frequency $\lim_{n\to\infty}\frac{1}{n}\\#\\{k\leq n:\ x_{k}=b\\}$
equals zero.

##  7\. Examples and open questions

In this section we consider a few examples of tiling and substitution systems
and determine the parameter $\alpha$ appearing in the second order ergodic
theorem.

######  Example 7.1.

(“Cantor” substitution). Let $\mathcal{A}=\\{0,1\\}$ and $\sigma(0)=000$,
$\sigma(1)=101$. Consider the substitution system $(X_{\sigma},S)$ associated
to $\sigma$. Observe that the graph-directed set of $\sigma$ is the middle-
thirds Cantor set. The dynamical system $(X_{\sigma},S)$ admits a unique
ergodic measure $\mu$ on $X_{\sigma}$ with the property $\mu([1])=1$. Then
Theorem 6.11 holds for the system $(X_{\sigma},S)$ with parameters
$\alpha=\log(2)/\log(3)$ and $c>0$, where $c$ is the right average density of
the Hausdorff measure on the middle-thirds Cantor set. Actually, in this case
the right and left average densities are equal to the symmetric average
density; its numerical value has been computed in [PZ]. The second order
ergodic theorem for the system $(X_{\sigma},S)$ was originally established by
A. Fisher [Fi1].

######  Example 7.2.

Returning to Example 2.4, we see that the associated graph-directed set is the
classical Sierpiński carpet. So Theorem 5.5 with parameter
$\alpha=\log(8)/\log(3)$ applies to this tiling system.

######  Example 7.3.

Here we consider a tiling dynamical systems with prototiles having fractal
boundaries. Our example is a modification of the system described in [So1,
Section 7.2], belonging to the family of tilings constructed in [K2, Section
6].

Let $r\approx.34115+1.1616i$ be a root of the equation $x^{3}+x+1=0$. Let
$T_{a}$, $T_{b}$, and $T_{c}$ be sets (prototiles) as described in Lemma 7.7
of [So1]. We use the same notation as in [So1].

We note that $T_{a}$, $T_{b}$, and $T_{c}$ are compact subsets of
$\mathbb{C}$. Set $\theta(z)=rz$. Then $\theta(T_{a})=T_{b}$; $\theta(T_{b})$
is the union of a translation of $T_{b}$ and of $T_{c}$; and $\theta(T_{c})$
is a translation of $T_{a}$. This subdivision rule uniquely determines a tile
substitution $\Theta$.

Set $\mathcal{G}=\Theta^{2}$. Thus, $\mathcal{G}(T_{a})$ is the union of a
translation of $T_{b}$ and of $T_{c}$; $\mathcal{G}(T_{b})$ is the union of a
translation of $T_{b}$, of $T_{c}$, and of $T_{a}$; and $\mathcal{G}(T_{c})$
is a copy of $T_{b}$. Set $\varphi(z)=r^{2}z$. Then after the “realification”
of $\mathbb{C}$, the map $\varphi$ can be represented as
$\varphi((x,y)^{T})=\lambda\cdot O\cdot(x,y)^{T}$, where $\lambda=|r^{2}|$ and

$O=\left(\begin{array}[]{cc}\beta&-\gamma\\\ \gamma&\beta\\\
\end{array}\right)$

with $\beta+\gamma i=r^{2}/|r^{2}|$. Then $\lambda$ is the expansion constant
of $\varphi$.

Assuming that the tiles $T_{a}$, $T_{b}$, and $T_{c}$ are colored white,
denote by $S_{a}$, $S_{b}$, and $S_{c}$ their respective copies colored black.
Extend the tile substitution $\mathcal{G}$ on $\\{S_{a},S_{b},S_{c}\\}$ as
follows: $S_{a}$ is mapped into a union of $S_{b}$ and $S_{c}$ in the same way
as $T_{a}$; $S_{c}$ is mapped into a copy of $S_{b}$ as $T_{c}$; and the tile
$S_{b}$ is mapped into a union of $S_{a}$, $S_{b}$, and $S_{c}$ exactly as
$T_{b}$, but with the tile $S_{b}$ being replaced by the tile $T_{b}$ (of the
same shape but of a different color).

Denote by $\mathcal{A}$ the set of prototiles
$\\{T_{a},T_{b},T_{c},S_{a},S_{b},S_{c}\\}$. Consider the tiling dynamical
system $(\Omega_{\mathcal{G}},\mathbb{R}^{2})$ associated to
$\mathcal{G}:\mathcal{A}\rightarrow\mathcal{A}^{+}$. This system has a unique
minimal component determined by white tiles, see [CS, Lemma 2.10]. The minimal
component is non-periodic, see [So1, Section 7.2]. Hence, the substitution
$\mathcal{G}$ satisfies all the conditions of Theorem 2.16 yielding that this
system admits a unique “natural” infinite invariant measure $\mu$ up to
scaling. The substitution matrix $M_{\mathcal{G}}$ is given by

$\left(\begin{array}[]{cccccc}0&1&0&0&0&0\\\ 1&1&1&0&1&0\\\ 1&1&0&0&0&0\\\
0&0&0&0&1&0\\\ 0&0&0&1&0&1\\\ 0&0&0&1&1&0\\\ \end{array}\right)$

It follows that the matrix $B$ is equal to $\left(\begin{array}[]{ccc}0&1&0\\\
1&0&1\\\ 1&1&0\\\ \end{array}\right).$ Since $\rho(B)\approx 1.618$ and the
expansion constant of $\mathcal{G}$ is $\lambda\approx 1.466$, we get that
$\alpha=\log(\rho(B))/\log(\lambda)>1$. Hence, the second order theorem
(Theorem 5.5) with parameter $\alpha\approx 1.258$ applies to the system
$(\Omega_{\mathcal{G}},\mathbb{R}^{2})$.

######  Example 7.4.

This example is a non-minimal extension of the well-known Rauzy tiling [R]. We
start with the Rauzy tiling itself. Let $r\approx-0.7771845+1.11514i$ be the
complex root of the equation $1-r-r^{2}-r^{3}=0$. The tiles may be described
using digit expansions in the base of $r$. There are three prototiles $T_{a}$,
$T_{b}$, and $T_{c}$, which may be represented as follows:

$T:=\Bigl{\\{}\sum_{n=0}^{\infty}a_{n}r^{-n}:\ a_{n}\in\\{0,1\\},\
a_{n}a_{n+1}a_{n+2}\neq 111\ \mbox{for all}\ n\Bigr{\\}}.$

Then

$T_{a}:=r^{-1}T,\ T_{b}:=1+r^{-2}T,\ T_{c}:=1+r^{-1}+r^{-3}T.$

Clearly, $rT_{a}=T_{a}\cup T_{b}\cup T_{c}$, $rT_{b}=r+T_{a}$, and
$rT_{c}=r+T_{b}$. This determines the substitution rule. (Strictly speaking,
these prototiles do not satisfy our definition, since $T_{b}$ and $T_{c}$ do
not contain the origin in the interior of their support, but this can be
easily rectified, translating the tiles. However, the given form of the tiles
is more convenient.) All the tiles of the Rauzy tiling can also be described
using base $r$ expansions: for any finite sum $z=\sum_{n=-N}^{-1}a_{n}r^{-n}$
with the property that $a_{n}\in\\{0,1\\},\ a_{n}a_{n+1}a_{n+2}\neq 111$ for
all $n$, we have $z+T_{a}\in{\mathcal{T}}$ in all cases,
$z+T_{b}\in{\mathcal{T}}$ iff $a_{-2}a_{-1}\neq 11$, and
$z+T_{c}\in{\mathcal{T}}$ iff $a_{-1}\neq 1$.

Now consider the “extended” tiling system, with the prototiles
$T_{a},T_{b},T_{c}$ and $S_{a}$, $S_{b}$, which have the same support as
$T_{a},T_{b}$ respectively, but have a different color (label). The
substitution acts as before on $T_{a},T_{b},T_{c}$, and

$rS_{a}=S_{a}\cup S_{b}\cup T_{c},\ \ rS_{b}=1+S_{a}.$

The matrix of the substitution is
$M_{\mathcal{G}}=\left(\begin{array}[]{cc}A&C\\\ 0&B\end{array}\right)$, where

$A=\left(\begin{array}[]{ccc}1&1&0\\\ 1&0&1\\\ 1&0&0\end{array}\right),\ \ \
B=\left(\begin{array}[]{cc}1&1\\\ 1&0\end{array}\right),\ \ \
C=\left(\begin{array}[]{cc}0&0\\\ 0&0\\\ 1&0\end{array}\right).$

The expansion $\lambda=|r|\approx 1.3562$ is the same as for the Rauzy tiling,
and $\rho(B)\approx 1.618$ is the golden ratio. All the assumptions from
Section SectionAssumptions are easily verified. We get
$\alpha=\log(\rho(B))/\log(\lambda)\approx 1.57935>1$, so Theorem 5.5 applies.
Figure 1 shows the “cantorization” of the tiling, so it gives an idea of both
“large-scale” structure of the tiling and the “small-scale” structure of the
graph-directed sets.

It is interesting to note that the “cantorization” of the tiling has a simple
description using base $r$ expansions: instead of all expansions using the
digits $(a_{n})$ with $111$ forbidden, one should consider all expansion with
the sequence of digits from the “golden mean” shift, that is, $11$ is
forbidden.

###  7.1. Open questions

1\. We had to impose some technical conditions on the substitution to prove
the second order ergodic theorem. For example, we do not know if it holds for
the following substitution on $\\{0,1,2\\}$:

$0\mapsto 00000,\ \ 1\mapsto 1111,\ \ 2\mapsto 20212.$

The matrix of the substitution is
$M_{\sigma}=\left(\begin{array}[]{ccc}5&0&1\\\ 0&4&1\\\
0&0&3\end{array}\right)$. Thus, there is an infinite ($\sigma$-finite)
invariant measure positive and finite on cylinder sets containing $2$,
however, there is no positive left eigenvector, so our methods do not work.

2\. We proved that (in appropriate contexts) converge the logarithmic averages
of the expressions

$R^{-\alpha}\int_{B_{R}}f({\mathcal{T}}-u)\,du\ \ \mbox{and}\ \ \
k^{-\alpha}\sum_{i=0}^{k-1}f(S^{i}x).$

But one can also view them as random variables (with ${\mathcal{T}}$ or $x$
taken randomly from the substitution space, according to the invariant measure
normalized on the appropriate cylinder set), and inquire whether they converge
in distribution as $R$ (resp. $k$) tend to infinity along a subsequence? For
instance, it appears that for the “integer Cantor” substitution from Example
1, we get that $2^{-n}\sum_{i=0}^{3^{n}-1}f(S^{i}x)$ tends to the uniform
distribution on $[0,1]$ as $n\to\infty$, for $f$ the characteristic function
of $[1]$ (and then for all $f\in L^{1}(X_{\sigma},\mu)$ with $\int
f\,d\mu=1$).

Acknowledgment. We are grateful to Karl Petersen, who asked whether the
second-order ergodic theorem holds for the Sierpiński gasket tiling system and
who told us about A. Fisher’s paper [Fi1]. We would also like to thank the
referee for his/her valuable comments.

## References

  * [A] J. Aaronson, _An introduction to infinite ergodic theory_. Mathematical Surveys and Monographs, 50. American Mathematical Society, Providence, RI, 1997.
  * [ADF] J. Aaronson, M. Denker, and A. Fisher, _Second order ergodic theorems for ergodic transformations of infinite measure spaces_. Proc. Amer. Math. Soc. 114 (1992), no. 1, 115–127.
  * [AP] J. Anderson and I. Putnam, _Topological invariants for substitution tilings and their associated $C^{*}$-algebras_. Ergodic Theory Dynam. Systems 18 (1998), no. 3, 509–537.
  * [Beck] M. Becker, A ratio ergodic theorem for groups of measure-preserving transformations. Illinois J. Math. 27 (1983), 562–570.
  * [BF] T. Bedford and A. Fisher, Analogues of the Lebesgue density theorem for fractal sets of reals and integers. Proc. London Math. Soc. (3) 64 (1992), 95–124.
  * [Be] J. Bell, Logarithmic frequency in morphic sequences. J. Theor. Nombres Bordeaux 20 (2008), no. 2, 227–241.
  * [BKM] S. Bezuglyi, J. Kwiatkowski, K. Medynets, _Aperiodic substitution systems and their Bratteli diagrams_. Ergodic Theory Dynam. Systems 29 (2009), no. 1, 37–72.
  * [BKMS] S. Bezuglyi, J. Kwiatkowski, K. Medynets, B. Solomyak, _Invariant measures on stationary Bratteli diagrams_. Ergodic Theory Dynam. Systems 30 (2010), no. 4, 973–1007.
  * [CS] M.I. Cortez and B. Solomyak, _Invariant measures for non-primitive tiling substitutions_. J. Anal. Math. 115 (2011), 293–342.
  * [D] L. Danzer, Inflation species of planar tilings which are not of locally finite complexity. Proc. Steklov Inst. Math. 239 (2002), 108–116.
  * [E] G. Edgar, Integral, Probability, and Fractal Measures. Springer, 1997.
  * [Fa] K. Falconer, _Techniques in fractal geometry_. John Wiley & Sons, Ltd., Chichester, 1997.
  * [Fi1] A. Fisher, _Integer Cantor sets and an order-two ergodic theorem_. Ergodic Theory Dynam. Systems 13 (1993), no. 1, 45–64.
  * [FR] N. P. Frank and E. A. Robinson, Jr., Generalized $\beta$-expansions, substitution tilings, and local finiteness. Trans. Amer. Math. Soc. 360 (2008), 1163–1177.
  * [G] F. R. Gantmacher, Applications of the theory of martrices. Interscience Publishers, Inc., New York, 1959.
  * [HY] M. Hama and H. Yuasa, Invariant measures for subshifts arising from substitutions of some primitive components. Hokkaido Math. J. 40 (2011), no. 2, 279–312.
  * [H] M. Hochman, _A ratio ergodic theorem for multiparameter non-singular actions_. J. Eur. Math. Soc. 12 (2010), no. 2, 365–383.
  * [HuW] W. Hurewicz, and H. Wallman, _Dimension Theory_. Princeton Mathematical Series, v. 4. Princeton University Press, Princeton, N. J., 1941.
  * [K1] R. Kenyon, _Self-replicating tilings. Symbolic dynamics and its applications_ (New Haven, CT, 1991), 239-263, Contemp. Math., 135, Amer. Math. Soc., Providence, RI, 1992.
  * [K2] R. Kenyon, _The construction of self-similar tilings_. Geom. Funct. Anal. 6 (1996), no. 3, 471–488.
  * [LS] F. Ledrappier and O. Sarig, _Fluctuations of ergodic sums for horocycle flows on $\mathbb{Z}^{d}$-covers of finite volume surfaces_. Discrete Contin. Dyn. Syst. 22 (2008), no. 1-2, 247–325.
  * [MW] R.D. Mauldin, S.C. Williams, _Hausdorff dimension in graph directed constructions_. Trans. Amer. Math. Soc. 309 (1988), no. 2, 811–829.
  * [PZ] N. Patzschke and M. Zähle, M. Fractional differentiation in the self-affine case. III. The density of the Cantor set. Proc. Amer. Math. Soc. 117 (1993), no. 1, 137–144.
  * [P] B. Praggastis, Numeration systems and Markov partitions from self similar tilings. Trans. Amer. Math. Soc. 351 (1999), no. 8, 3315–3349.
  * [RW] C. Radin, M. Wolff, _Space tilings and local isomorphism_. Geom. Dedicata 42 (1992), no. 3, 355–360.
  * [R] G. Rauzy, Nombres algébriques et substitutions. Bull. Soc. Math. France 110(2) (1982), 147–178.
  * [Ro] E. A. Robinson, Jr., Symbolic dynamics and tilings of ${{\mathbb{R}}}^{d}$. Symbolic dynamics and its applications, Proc. Sympos. Appl. Math., Vol. 60, Amer. Math. Soc., Providence, RI, 2004, pp. 81–119.
  * [S] H. Schneider, The influence of the marked reduced graph of a nonnegative matrix on the Jordan form and on related properties: a survey. Proceedings of the symposium on operator theory (Athens, 1985). Linear Algebra Appl. 84 (1986), 161–189.
  * [So1] B. Solomyak, _Dynamics of self-similar tilings_. Ergodic Theory Dynam. Systems 17 (1997), no. 3, 695–738.
  * [So2] B. Solomyak, Nonperiodicity implies unique composition for self-similar translationally finite tilings. Discrete Comput. Geom. 20 (1998), 265–279.
  * [Y] H. Yuasa, Invariant measures for the subshifts arising from non-primitive substitutions. J. D’Analyse Math. 102 (2007), 143–180.