# Catalan numbers as discrepancies for a family of substitutions on infinite
alphabets

Dirk Frettlöh  Technische Fakultät, Bielefeld University,
Postfach 100131, 33501 Bielefeld, Germany<EMAIL_ADDRESS>,  Alexey
Garber  School of Mathematical & Statistical Sciences,
The University of Texas Rio Grande Valley,
1 West University Blvd., Brownsville, TX 78520, USA<EMAIL_ADDRESS>and  Neil Mañibo  Fakultät für Mathematik, Bielefeld University,
Postfach 100131, 33501 Bielefeld, Germany  School of Mathematics and
Statistics,
Open University, Walton Hall, Kents Hill,
Milton Keynes, United Kingdom MK7 6AA<EMAIL_ADDRESS><EMAIL_ADDRESS>
(Date: August 27, 2024)

###### Abstract.

In this work, we consider a class of substitutions on infinite alphabets and
show that they exhibit a growth behaviour which is impossible for
substitutions on finite alphabets. While for both settings the leading term of
the tile counting function is exponential (and guided by the inflation
factor), the behaviour of the second-order term is strikingly different. For
the finite setting, it is known that the second term is also exponential or
exponential times a polynomial. We exhibit a large family of examples where
the second term is at least exponential in $n$ divided by half-integer powers
of $n$, where $n$ is the number of substitution steps. In particular, we
provide an identity for this discrepancy in terms of linear combinations of
Catalan numbers.

###### Key words and phrases:

Substitutions, Delone set, infinite alphabets, discrepancy, Catalan numbers,
aperiodic tilings

###### 1991 Mathematics Subject Classification:

05B45, 37B10, 52C23

_Dedicated to our dear colleague and good friend, Uwe._

##  1\. Introduction

Exponential growth or decay appears in many discrete or continuous dynamical
systems. A perfect example of such a behaviour is the famous Fibonacci
sequence that can be used to describe a (very simplified) growth of a
population of bunnies. The Fibonacci sequence grows like $\Theta(\varphi^{n})$
where $\varphi=\frac{\sqrt{5}+1}{2}$ is the golden mean; see Section 1.1 for
the notations we use for asymptotic behaviour.

In the sequel, we assume that the reader is familiar with basic terms and
concepts of aperiodic order. Rather than explaining those basic terms here we
will refer to the monograph [2] when necessary.

For (classical) primitive substitution tilings [2], the asymptotic growth of
many quantities scales like $\lambda^{n}$, where $\lambda$ is the associated
inflation factor — respectively its $d$-th power, if the tiling lives in
$\mathbb{R}^{d}$, for $d\geq 2$. For example, the number of tiles of all types
(or of any single tile type) in the $n$-th iteration of the substitution
applied to one prototile grows like $\Theta(\lambda^{n})$. Both these
phenomena originate from the uniqueness of the Perron–Frobenius eigenvalue
$\lambda$ of the substitution matrix $M$ and from the Jordan form of $M$ and
its powers $M^{n}$.

In the context of primitive substitutions, the discrepancy is the difference
between the tracked quantity $q(n)$ and the expected value $c\cdot\lambda^{n}$
for the appropriate constant $c>0$. Its asymptotics are determined by the
second largest (in absolute value) eigenvalue $\lambda^{\prime}$. Again by
using the Jordan form of $M^{n}$, this discrepancy can be written as
$P(n)|\lambda^{\prime}|^{n}$ for some polynomial $P$ if $\lambda^{\prime}$ is
real, and with some additional trigonometric factor if $\lambda^{\prime}$ is
complex.

The discrepancy plays a crucial role in the study of bounded-distance
equivalence relations for point sets. Two Delone sets are bounded-distance
equivalent to each other, if there is a bijection $f$ between them such that
$|f(x)-x|<C$ for some $C>0$; see [6, 21, 22] and references therein. A similar
notion of discrepancy lies in the core of the study of bounded remainder sets;
see [4, 9] and references therein.

This paper studies discrepancies for a certain class of substitutions on
infinite alphabets, which belongs to a generalisation of primitive
substitutions introduced in [14, 15]. This particular class was studied in
[5], where it was shown that in the most general setting it allows any real
number greater than $2$ to be the inflation factor of such a substitution.

More precisely, given a bounded sequence of non-negative integers
${\boldsymbol{a}}=(a_{i})_{i\geqslant 0}$ satisfying certain assumptions,
${\boldsymbol{a}}$ defines a “pre-substitution” on the countable alphabet
$\mathbb{N}_{0}\simeq\\{[i]\\}$; see Eq. (1). This pre-substitution can be
extended to a substitution $\varrho_{{\boldsymbol{a}}}$ on a compact alphabet
$\mathcal{A}$ via a suitable embedding of $\mathbb{N}_{0}$ into a shift space;
see [5] for the complete construction. This substitution
$\varrho_{{\boldsymbol{a}}}$ on a now compact alphabet $\mathcal{A}$ satisfies
several properties that hold for primitive substitutions, including existence
of letter frequencies and of an associated geometric substitution with
inflation factor $\lambda$. We refer to [5] and [14, 15] for more details. We
briefly remark that the tilings generated by these substitutions have infinite
local complexity (ILC), both combinatorially and geometrically. One primary
motivation for the series of works of the authors in the infinite alphabet
regime is the development of an infinite-dimensional renormalisation scheme
which would cover such objects, including the pinwheel tilings of the plane,
which have since resisted a complete spectral characterisation; see [3, 7] for
some statistical and spectral properties of pinwheel tilings.

The question that inspired this paper was whether the Delone sets arising from
these substitutions are bounded-distance equivalent to $\alpha\mathbb{Z}$ for
some appropriate $\alpha$. Hence, our main focus is the discrepancy function
$d_{\boldsymbol{a}}(n)$, which we define as follows. First, we count the
number of letters in $\varrho^{n}_{\boldsymbol{a}}([0])$. Due to existence of
frequencies and associated tile lengths, this quantity is
$\nicefrac{{1}}{{c_{\boldsymbol{a}}}}\cdot\lambda^{n}+d_{\boldsymbol{a}}(n)$,
where $d_{\boldsymbol{a}}(n)\in o(\lambda^{n})$. Here

  * •

$\lambda$ is the inflation factor, and

  * •

$c_{\boldsymbol{a}}$ is the average tile length, assuming the length of $[0]$
is 1 (hence $\nicefrac{{1}}{{c_{\boldsymbol{a}}}}$ equals the density of the
corresponding Delone set in $\mathbb{R}$, see [2]).

The paper is organised as follows. In Section 2, we provide necessary
definitions and some background on substitutions on infinite alphabets,
together with specific results for the class of substitutions we will be
considering. In Section 3, we prove that, if $a_{i}=1$ for all $i$, the
discrepancy $d_{\boldsymbol{a}}$ is (a multiple of) the tail of the power
series

$\frac{1-\sqrt{1-4x}}{2x}=\sum_{i=0}^{\infty}C_{i}x^{i}$

evaluated at $x=\nicefrac{{4}}{{25}}$. Here $C_{k}$ is the $k$-th Catalan
number; see for instance [17, 23, 24] or OEIS sequence A000108 [16]. In
particular, in Theorem 3.2, we show for this specific choice of
${\boldsymbol{a}}$ that $d_{\boldsymbol{a}}(n)$ belongs to
$\Theta\left(\frac{2^{n}}{n^{\nicefrac{{3}}{{2}}}}\right)$.

In Section 4, we tackle the more general case of eventually constant sequences
${\boldsymbol{a}}$. We show that, in that case, the discrepancy
$d_{\boldsymbol{a}}(n)$ is also related to Catalan numbers through a non-
homogeneous linear recurrence relation from Lemma 4.7. In Theorem 4.10, we
show that there exists a non-negative integer $q$ such that some subsequence
of $d_{\boldsymbol{a}}(n)$ grows at least as fast as
$\Omega\left(\frac{2^{n}}{n^{q+\nicefrac{{3}}{{2}}}}\right)$. This implies
that none of the Delone sets arising from the substitutions in this class is
bounded distance equivalent to $\alpha\mathbb{Z}$, for any $\alpha>0$. This is
Corollary 4.12. By the results in [21] (see also [6]), this in turn implies
that each substitution $\varrho_{\boldsymbol{a}}$ gives rise to uncountably
many equivalence classes of Delone sets with respect to bounded distance
equivalence.

We want to emphasise that both asymptotics are completely different from the
case of substitutions on finite alphabets where (for some subsequence) the
similarly defined discrepancy is of order
$\Theta\left(n^{q}|\lambda^{\prime}|^{n}\right)$ for some non-negative integer
$q$ and for some (possibly complex) number $\lambda^{\prime}$. In Section 5,
we apply the general framework from Section 4 to two concrete examples.
Working through these examples, we show how the results from Section 4 are
used to get a recurrence relation for the discrepancy function. Notably, we
are able to get explicit formulas for the discrepancies in these two examples.

Section 6 complements the above results by numerical computations of
discrepancies of further examples, exploring the different phenomena that may
occur for substitutions on infinite alphabets. Our examples study possible
cases for some auxiliary parameter $\mu$ and discuss how the corresponding
values of $\lambda$ change (or do not change) the growth rate of the
discrepancy function.

###  1.1. Notations for asymptotic behaviour

We use the following families for asymptotic behaviour [12]. Here, we assume
that $f$ and $g$ are functions of a non-negative integer parameter $n$ and
that $g(n)>0$ for sufficiently large $n$.

  * •

$f\in o(g)$ if $\lim\limits_{n\rightarrow\infty}\frac{|f(n)|}{g(n)}=0$;

  * •

$f\in O(g)$ if $\limsup\limits_{n\rightarrow\infty}\frac{|f(n)|}{g(n)}$ is
finite;

  * •

$f\in\Omega(g)$ if $\liminf\limits_{n\rightarrow\infty}\frac{|f(n)|}{g(n)}>0$
or infinite;

  * •

$f\in\Theta(g)$ if both
$\limsup\limits_{n\rightarrow\infty}\frac{|f(n)|}{g(n)}$ and
$\liminf\limits_{n\rightarrow\infty}\frac{|f(n)|}{g(n)}$ are positive numbers.

##  2\. Preliminaries

###  2.1. A class of substitutions over a compact alphabet

Let $\mathcal{A}=\mathbb{N}_{0}\cup\left\\{\infty\right\\}$ be the one-point
compactification of the set $\mathbb{N}_{0}$ of non-negative integers. We
consider a class of substitutions on the alphabet $\mathcal{A}$ that maps
letters in $\mathcal{A}$ to finite words over $\mathcal{A}$. The class is
parameterised by a bounded sequence $\boldsymbol{a}=(a_{i})_{i}$ of non-
negative integers. We restrict to sequences $\boldsymbol{a}=(a_{i})_{i}$ which
are _eventually constant_ , i.e., there exists $k\in\mathbb{N}$ for which
$a_{i}=a$ for some $a>0$ and for all $i\geqslant k$. We additionally require
that $a_{0}>0$. The substitution associated to $\boldsymbol{a}$ is constructed
as follows. We define the following “pre-substitution” on letters $[i]$ with
$i\in\mathbb{N}_{0}$, see [5, Def. 3.1], via

$\displaystyle\varrho_{\boldsymbol{a}}([0])$
$\displaystyle=[0]^{a_{0}}[1],\text{ and}$ (1)
$\displaystyle\varrho_{\boldsymbol{a}}([i])$
$\displaystyle=[0]^{a_{i}}[i-1][i+1]\;\text{ for }i>0.$

Since both $i-1$ and $i+1$ go to $\infty$ as $i\to\infty$, and since $a_{i}$
is eventually constant and is equal to $a$ for $i\geqslant k$, we then set

$\varrho_{\boldsymbol{a}}([\infty])=[0]^{a}[\infty][\infty].$

This makes the rule
$\varrho_{\boldsymbol{a}}\colon\mathcal{A}\to\mathcal{A}^{+}$ a continuous
map, where the topology on the set $\mathcal{A}^{+}$ of finite words over
$\mathcal{A}$ is the topology of a disjoint union; see [15]. Moreover, the
restrictions we impose on ${\boldsymbol{a}}$ imply that
$\varrho_{\boldsymbol{a}}$ is a _primitive_ substitution. In the compact
alphabet setting, $\varrho_{\boldsymbol{a}}$ being primitive means that, for
any non-empty open set $U\subset\mathcal{A}$, there exists a power $n:=n(U)$
such that $\varrho_{\boldsymbol{a}}^{n}(b)$ contains a letter in $U$, for all
$b\in\mathcal{A}$; see [5, Thm. 3.5]. Note that such a rule results in a well-
defined shift space $(X_{\varrho},S)$ that has many nice properties of
primitive substitutions on finite alphabets (e.g., minimality, unique
ergodicity); see [5, Thm. 1.4]. For more details on dynamical properties of
substitutions on compact alphabets, we refer the reader to [15].

Since we are interested in discrepancies for tile counting functions, we will
focus on _supertiles_ , i.e., words of the form
$\varrho^{n}_{\boldsymbol{a}}([i])$ and the associated substitution operator
$M$, which is the generalisation of the substitution matrix for infinite
alphabets. More specifically, we will be looking at the number of words in the
$n$-th order supertile $\varrho^{n}_{\boldsymbol{a}}([0])$ of type $[0]$ as
$n$ grows.

###  2.2. Substitution operator, natural length function, and frequencies

Let $M$ be a bounded linear operator on a Banach space $E$. The _spectrum_ of
$M$, which we denote by $\sigma(M)$, is the set of all complex numbers
$\lambda$ for which $(\lambda\boldsymbol{I}-M)$ is not invertible, where
$\boldsymbol{I}$ denotes the identity operator. The _spectral radius_ of $M$
is defined as $r(M)=\sup\left\\{|\lambda|\colon\lambda\in\sigma(M)\right\\}$.
Let $B_{1}(0)$ be the unit ball in $E$. The operator $M$ is called _compact_
if the image of $B_{1}(0)$ under $M$ is relatively compact. This is a rather
strong condition. In fact, for the substitutions we treat in this work, the
corresponding substitution operator is never compact; see [15, Prop. 6.2]. A
weaker condition is _quasi-compactness_. An operator $M$ with spectral radius
$1$ is called quasi-compact, if there exists a compact operator $N$ and
$n\in\mathbb{N}$ such that $|M^{n}-N|_{\text{op}}<1$, where
$|\cdot|_{\text{op}}$ is the operator norm. We refer to [8, 15] and references
therein for details on such operators and their properties.

Most asymptotics for abelian quantities (i.e., quantities which solely depend
on the number of certain tiles within a supertile and not their location) for
substitutions on finite alphabets are encoded by the corresponding
substitution matrix. In the compact alphabet setting, one can associate a
_substitution operator_ $M$ to the substitution $\varrho_{\boldsymbol{a}}$ as
follows. Consider the Banach space $E=C(\mathcal{A})$ of continuous functions
on $\mathcal{A}$ (with the sup norm). Define $M\colon E\to E$ to be

$(Mf)(b)=\sum_{c\in\varrho_{\boldsymbol{a}}(b)}f(c),$

where $\varrho_{\boldsymbol{a}}(b)$ is to be understood as a multiset. $M$ is
a positive and bounded linear operator on $E$.

Let $K$ be the positive cone in $E$ consisting of all non-negative continuous
functions. A natural length function $\ell$ for $\varrho_{\boldsymbol{a}}$ is
a function in $K$ for which $M\ell=\lambda\ell$ for some $\lambda\neq 0$. In
other words, it corresponds to a non-negative eigenvector of $M$ in $K$ with
non-zero eigenvalue $\lambda$. If further $\lambda>1$ and $\ell$ is _strictly
positive_ , i.e., $\ell(b)>0$ for all $b\in\mathcal{A}$, one can associate a
geometric inflation rule to $\varrho_{\boldsymbol{a}}$ which generates
substitution tilings on $\mathbb{R}$ with (possibly) infinitely many prototile
lengths. The following result is proved in [15].

######  Theorem 2.1.

Let $\varrho$ be a substitution on a compact alphabet. Suppose that $\varrho$
is primitive and that the associated scaled substitution operator
$\frac{1}{r(M)}M$ is quasi-compact. Then, $\varrho$ admits a unique (up to
scalar multiplication) natural length function which is strictly positive with
$\lambda=r(M)>1$.

######  Remark 2.2.

Quasi-compactness has strong implications to the spectral properties of $M$.
In particular, this is equivalent to the _essential spectral radius_
$r_{\text{ess}}(M)$ being strictly less than $r(M)$. Since it is not central
to our arguments, we do not define $r_{\text{ess}}(M)$ here and refer the
reader to [1, 15, 18] instead. This observation also implies that outside the
essential spectral radius, there are at most finitely many other elements of
$\sigma(M)$, each being an eigenvalue with finite-dimensional (generalised)
eigenspace; see [8, Ch. XIV.1].

It was shown in [5, Sect. 4] that the substitutions considered in Section 2
satisfy the conditions in Theorem 2.1. Moreover, we know closed forms for
$\lambda$ and $\ell$ in terms of the defining sequence $\boldsymbol{a}$.

######  Proposition 2.3 ([5]).

Let $\varrho_{\boldsymbol{a}}$ be a substitution on
$\mathcal{A}=\mathbb{N}_{0}\cup\left\\{\infty\right\\}$ as defined in Eq. (1).
Let $\mu$ be the unique real number in $(0,1)$ that satisfies

$\frac{1}{\mu}=\sum_{i=0}^{\infty}a_{i}\mu^{i}.$

One then has

$\lambda=\mu+\frac{1}{\mu}\quad\text{ and
}\quad\ell([k])=\mu^{k}+\sum_{j=1}^{k}\sum_{i=j}^{\infty}a_{i}\mu^{i+k+1-2j},\text{
for }k>0,$ (2)

with the normalization $\ell([0])=1$.

It is easy to see that the substitution defined in Eq. (1) admits a bi-
infinite tiling fixed point $\mathcal{T}$ with seed $\infty|0$. From this
substitution tiling, one can derive a Delone set $\varLambda_{\mathcal{T}}$ by
collapsing each tile to the location of its left endpoint. Unique ergodicity
implies that the points in $\varLambda_{\mathcal{T}}$ admit a well-defined
frequency. This leads us to the following result; compare [5, Prop. 4.5].

######  Proposition 2.4.

Let $\varLambda_{\mathcal{T}}$ be the Delone set derived from the tiling fixed
point of $\varrho_{\boldsymbol{a}}$. Then, the frequency of the point of type
$[k]$ in $\varLambda_{\mathcal{T}}$ is given by $\nu([k])=(1-\mu)\mu^{k}$.
Moreover, the density of $\varLambda_{\mathcal{T}}$ exists and is given by
$\operatorname{dens}(\varLambda_{\mathcal{T}})=\big{(}\sum_{k=0}^{\infty}\nu([k])\ell([k])\big{)}^{-1}$.

Figure 1. The $\varrho_{\boldsymbol{a}}$ of Example 2.5 applied to the tile
$[0]$ (a unit interval): $[0]$ is inflated by $\lambda=\frac{5}{2}$ and
subdivided into tiles $[0]$ and $[1]$. This is the first order supertile
$\varrho_{\boldsymbol{a}}([0])$. In the next step $\varrho_{\boldsymbol{a}}$
is applied to the two tiles of the first order supertile. This yields the
second order supertile $\varrho^{2}_{\boldsymbol{a}}([0])$ consisting of five
tiles.

######  Example 2.5.

Consider the sequence $\boldsymbol{a}$ with $a_{i}=1$ for all $i$. The
corresponding substitution $\varrho_{\boldsymbol{a}}$ has
$\mu=\nicefrac{{1}}{{2}}$ and hence $\lambda=\nicefrac{{5}}{{2}}$,
$\ell([k])=2-\nicefrac{{1}}{{2^{k}}}$ and
$\nu([k])=\nicefrac{{1}}{{2^{k+1}}}$; compare Figure 1. The average distance
between two points in $\varLambda_{\mathcal{T}}$ is given by
$(\operatorname{dens}(\varLambda_{\mathcal{T}}))^{-1}=\nicefrac{{4}}{{3}}$.

###  2.3. Spectral gap, discrepancies, and bounded distance equivalence

Apart from the existence of a strictly positive length function and unique
ergodicity, quasi-compactness (together with primitivity) has direct
implications to studying discrepancies. It also implies that the operator $M$
has a _spectral gap_ , i.e., it admits a “second largest” element (in terms of
modulus). More formally, the quantity

$r_{2}=:\sup\left\\{|\lambda^{\prime}|\colon\lambda^{\prime}\in\sigma(M)\setminus\left\\{\lambda\right\\}\right\\}$

exists and is strictly less than the inflation factor $\lambda$; see [14, Sec.
7].

######  Remark 2.6.

Not all primitive substitutions over a compact alphabet admit a spectral gap;
see [14, Ex. 6.18] for an example for which $M$ is not quasi-compact.

Let $f\in C(\mathcal{A})$ with $\|f\|\leqslant 1$. We define
$\text{Act}(f,b,n):=M^{n}f(b)=\sum_{c\in\varrho^{n}(b)}f(c)$ and
$\text{Exp}(f,b,n)=\lambda^{n}\cdot\ell(b)\operatorname{dens}(\varLambda)$.
(Later we will consider $f(b)=1$ for all $b\in\mathcal{A}$. Then
$\text{Act}(f,b,n)$ is the actual number of tiles in
$\varrho^{n}_{\boldsymbol{a}}(b)$, and $\text{Exp}(f,b,n)$ is the expected
number of tiles in $\varrho^{n}_{\boldsymbol{a}}(b)$.) The following
discrepancy estimate follows from [14, Thm. 7.3].

######  Theorem 2.7.

Let $\varrho$ be a primitive substitution on a compact alphabet with quasi-
compact substitution operator $M$. Then for any $f\in C(\mathcal{A})$ with
$\|f\|\leqslant 1$, there exists a function
$\theta\colon\mathbb{N}\to\mathbb{R}_{+}$ with
$\lim_{n\to\infty}\sqrt[n]{\theta(n)}=1$ such that

$|\textnormal{Exp}(f,b,n)-\textnormal{Act}(f,b,n)|\leqslant\theta(n)(r_{2})^{n}.$

######  Remark 2.8.

Quasi-compact operators are ubiquitous in the study of dynamical systems (both
in the discrete and continuous regimes). In particular, the quasi-compactness
of the Ruelle–Perron–Frobenius transfer operator allows one to estimate rates
of mixing and decay of correlations; see the seminal works by Ruelle and
Pollicott [18, 20]. The (isolated) eigenvalues lying strictly between the
peripheral spectrum (i.e., the intersection of $\sigma(M)$ with the circle of
radius $r(M)$) and the essential spectrum figure in expansions similar to that
in Theorem 2.7. These eigenvalues are also known as _Ruelle–Pollicott
resonances_ , which find a variety of applications including fractal geometry
and stochastic differential equations; see [10] for instance. In our setting,
the peripheral spectrum consists solely of $\lambda$, and the other isolated
eigenvalues of Ruelle–Pollicott-type are the ones which show up in our
discrepancy estimates; see Example 6.2 below.

In this work, we will focus on the tile counting function $f$ with $f(b)=1$
for all $b\in\mathcal{A}$. Note that $(M^{n}f)(b)$ counts the number of tiles
in $\varrho_{\boldsymbol{a}}^{n}(b)$. We will restrict ourselves to $n$-th
order supertiles of type $[0]$, hence we fix $b=[0]$. For eventually constant
sequences, we give certain bounds for $r_{2}$ and the function $\theta(n)$,
which are related to Catalan numbers.

##  3\. Catalan numbers as discrepancies

In this section, we completely describe the tile counting function and
discrepancies for the substitution in Example 2.5 where $a_{i}=1$ for all
$i\geqslant 0$. The sequence serves as a model example since it is the first
and probably one of the simplest examples where the discrepancy function shows
Catalan-like growth.

For this sequence, recall from [14] that we have the following pre-
substitution on letters $[i],i\in\mathbb{N}$.

$\displaystyle\varrho_{\boldsymbol{a}}([0])$ $\displaystyle=[0][1],\text{
and}$ $\displaystyle\varrho_{\boldsymbol{a}}([i])$
$\displaystyle=[0][i-1][i+1]\text{ for }i>0.$

To this pre-substitution we associate the corresponding infinite substitution
matrix

${\boldsymbol{A}}=\left(\begin{array}[]{cccccc}1&2&1&1&1&\dots\\\
1&0&1&0&0&\ldots\\\ 0&1&0&1&0&\ldots\\\ 0&0&1&0&1&\ldots\\\
0&0&0&1&0&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right).$

One can view $\boldsymbol{A}$ as the transpose of the substitution operator
$M$ restricted on the subspace associated to the isolated points in
$\mathcal{A}$.

We will estimate the tile counting function

$\\#_{\boldsymbol{a}}(n):=(1,1,1,\ldots)\boldsymbol{A}^{n}(1,0,0,\ldots)^{t}=(M^{n}f)([0]),$

which returns the total number of letters in
$\varrho^{n}_{{\boldsymbol{a}}}([0])$. (Recall that we consider
$\varrho_{\boldsymbol{a}}(b)$ as a multiset.) Note that despite using infinite
vectors and an infinite matrix $\boldsymbol{A}$, the product is well defined
because the product of the left vector with any power of $\boldsymbol{A}$ will
give a vector with finitely many non-zero entries (since each column of
$\boldsymbol{A}^{n}$ has only finitely many non-zero entries). In order to
make formulas shorter we denote by $[\boldsymbol{v}]_{i}$ the $i$-th term of a
vector $\boldsymbol{v}$. We are interested in
$[(1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}$ (we will start indexing from $0$,
since the initial entry corresponds to $[0]$).

The coefficient of $\lambda^{n}$ in the formula for
$[(1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}$ can be estimated from the lengths of
tiles and their frequencies, see [14] or [5]; compare also [2] for the finite
alphabet case. In the particular case of this substitution, the average tile
length is $\nicefrac{{4}}{{3}}$ from Example 2.5.

Since the inflation factor for this substitution is $\nicefrac{{5}}{{2}}$, the
length of $\varrho^{n}_{\boldsymbol{a}}([0])$ is $(\nicefrac{{5}}{{2}})^{n}$,
and this iteration is expected to have
$\nicefrac{{3}}{{4}}\cdot(\nicefrac{{5}}{{2}})^{n}$ tiles. Thus we write

$[(1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}=\frac{3}{4}\cdot\left(\frac{5}{2}\right)^{n}+d_{\boldsymbol{a}}(n)$

and estimate the discrepancy term $d_{\boldsymbol{a}}(n)$ for all $n\geqslant
0$.

Let $\boldsymbol{I}$ be the infinite identity matrix. Then, by elementary
calculation,
$(-1,1,1,\ldots)=(1,1,1,\ldots)(2\boldsymbol{A}-5\boldsymbol{I})$. We define a
new function $D(n)$ as

$D(n):=[(-1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}=2d_{\boldsymbol{a}}(n+1)-5d_{\boldsymbol{a}}(n).$
(3)

######  Lemma 3.1.

Let $C_{k}$ be the $k$-th Catalan number, $C_{k}={2k\choose k}-{2k\choose
k+1}=\frac{{2k\choose k}}{k+1}$. Then,

$D(n)=\left\\{\begin{array}[]{rl}-C_{k}&\text{ if }n=2k,\\\ 0&\text{ if
}n=2k+1.\end{array}\right.$

###### Proof.

Let $\mathcal{V}$ be the space of all stabilising sequences
${\boldsymbol{x}}=(x_{0},x_{1},x_{2},\ldots)$ of real numbers such that
${\displaystyle\sum_{i=0}^{\infty}\frac{x_{i}}{2^{i}}={\boldsymbol{x}}\cdot\left(1,\frac{1}{2},\frac{1}{4},\ldots\right)^{t}=0}$.
The space $\mathcal{V}$ is invariant under the operator $\boldsymbol{B}$
defined by the right multiplication by $\boldsymbol{A}$. Indeed,
$\boldsymbol{A}\left(1,\frac{1}{2},\frac{1}{4},\ldots\right)^{t}=\frac{5}{2}\left(1,\frac{1}{2},\frac{1}{4},\ldots\right)^{t}$
and therefore if
${\boldsymbol{x}}\cdot\left(1,\frac{1}{2},\frac{1}{4},\ldots\right)^{t}=0$,
then

$({\boldsymbol{x}}\boldsymbol{A})\cdot\left(1,\frac{1}{2},\frac{1}{4},\ldots\right)^{t}=\frac{5}{2}\,{\boldsymbol{x}}\cdot\left(1,\frac{1}{2},\frac{1}{4},\ldots\right)^{t}=0.$

Let ${\boldsymbol{e}}_{0}=(-1,1,1,\ldots)$ and for every $i>0$ we define
${\boldsymbol{e}}_{i}$ as follows

$\begin{array}[]{r}{\boldsymbol{e}}_{1}=(1,-2,0,0,0,0,\ldots),\\\
{\boldsymbol{e}}_{2}=(0,1,-2,0,0,0,\ldots),\\\
{\boldsymbol{e}}_{3}=(0,0,1,-2,0,0,\ldots),\end{array}$

and so on. Then $\mathcal{E}=\\{{\boldsymbol{e}}_{i}\\}_{i}$ is a basis for
$\mathcal{V}$: every vector in $\mathcal{V}$ is stabilising and it can be
written as a multiple of ${\boldsymbol{e}}_{0}$ plus a finite linear
combination of vectors from $\mathcal{E}$.

Simple computations show that
$\boldsymbol{B}({\boldsymbol{e}}_{0})={\boldsymbol{e}}_{0}+{\boldsymbol{e}}_{1}$
and
$\boldsymbol{B}({\boldsymbol{e}}_{i})={\boldsymbol{e}}_{i-1}+{\boldsymbol{e}}_{i+1}$
for $i>0$. In other words, the matrix of the restriction of $\boldsymbol{B}$
on $\mathcal{V}$ in $\mathcal{E}$ is

${\boldsymbol{B}^{\prime}}=\left(\begin{array}[]{cccccc}1&1&0&0&0&\dots\\\
1&0&1&0&0&\ldots\\\ 0&1&0&1&0&\ldots\\\ 0&0&1&0&1&\ldots\\\
0&0&0&1&0&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right).$

We claim that
$\boldsymbol{B}^{n}({\boldsymbol{e}}_{0})=c_{0,n}{\boldsymbol{e}}_{0}+\cdots+c_{n,n}{\boldsymbol{e}}_{n}$,
where the list $(c_{0,n},\ldots,c_{n,n})$ is the list of binomial coefficients
$\binom{n}{i}$, sorted from the largest one to the smallest one. That is, for
$n$ even the list goes
$\binom{n}{\nicefrac{{n}}{{2}}},\binom{n}{\nicefrac{{n}}{{2}}-1},\binom{n}{\nicefrac{{n}}{{2}}+1},\binom{n}{\nicefrac{{n}}{{2}}-2},\ldots,{n\choose
0},{n\choose n}$; and for $n$ odd analogously.

This can be shown by in induction. The basis $n=0$ is trivial because
${\boldsymbol{B}}({\boldsymbol{e}}_{0})={\boldsymbol{e}_{0}}=c_{0,0}{\boldsymbol{e}_{0}}$.
For the induction step we write

${\boldsymbol{B}}^{n+1}({\boldsymbol{e}_{0}})={\boldsymbol{B}}(c_{0,n}{\boldsymbol{e}}_{0}+\cdots+c_{n,n}{\boldsymbol{e}}_{n})=\\\
=(c_{0,n}+c_{1,n}){\boldsymbol{e}_{0}}+(c_{0,n}+c_{2,n}){\boldsymbol{e}_{1}}+(c_{1,n}+c_{3,n}){\boldsymbol{e}_{2}}+\cdots+(c_{n-2,n}+c_{n,n}){\boldsymbol{e}_{n-1}}+\\\
+c_{n-1,n}{\boldsymbol{e}_{n}}+c_{n,n}{\boldsymbol{e}_{n+1}}.$

Note that the coefficients of ${\boldsymbol{e}}_{n}$ and
${\boldsymbol{e}_{n+1}}$ are $c_{n-1}=c_{n,n}=1=c_{n,n+1}=c_{n+1,n+1}$ as
claimed. The remaining coefficients are sums of two binomial coefficients and
we use the identity ${n\choose i}+{n\choose i+1}={n+1\choose i+1}$ in each
case. Note that $c_{i,n}$ is equal to $c_{i-1,n}$ or $c_{i+1,n}$ depending on
the parities of $i$ and $n$ so the identity can be used for each coefficient.

Since only ${\boldsymbol{e}}_{0}$ and ${\boldsymbol{e}}_{1}$ have non-zero
starting entry,

$[(-1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}=[\boldsymbol{B}^{n}({\boldsymbol{e}}_{0})]_{0}=-c_{0,n}+c_{1,n}.$

The right-hand side is the difference between the second-to-the-largest and
largest binomial coefficients which is either 0 if $n$ is odd, or $-C_{k}$ if
$n$ is even. ∎

Since $d_{\boldsymbol{a}}(0)=\frac{1}{4}$ and
$d_{\boldsymbol{a}}(n+1)=\frac{5}{2}d_{\boldsymbol{a}}(n)+\frac{1}{2}D(n)$
from Eq. (3), we derive the following explicit formula for
$d_{\boldsymbol{a}}(n)$ for $n>0$:

$d_{\boldsymbol{a}}(n)=\left\\{\begin{array}[]{rl}\frac{1}{2}\left(\frac{5}{2}\right)^{2k}\left(\frac{5}{4}-C_{0}-\left(\frac{2}{5}\right)^{2}C_{1}-\ldots-\left(\frac{2}{5}\right)^{2k}C_{k}\right),&\text{
if }n=2k+1,\\\ \frac{5}{2}d_{\boldsymbol{a}}(n-1),&\text{ if
}n=2k.\end{array}\right.$

Next, we use the power series for the Catalan numbers to obtain precise
asymptotics for $d_{\boldsymbol{a}}(n)$. In particular,

$C(x)=\frac{1-\sqrt{1-4x}}{2x}=\sum_{i=0}^{\infty}C_{i}x^{i},$

whose radius of convergence is $\nicefrac{{1}}{{4}}$. Plugging
$x=\frac{4}{25}$ into this series yields
$C(\nicefrac{{4}}{{25}})=\nicefrac{{5}}{{4}}$, from which we get the
representation of $d_{\boldsymbol{a}}(2k+1)$ as the tail of this series:

$d_{\boldsymbol{a}}(2k+1)=\frac{1}{2}\left(\frac{5}{2}\right)^{2k}\sum_{i=k+1}^{\infty}\left(\frac{2}{5}\right)^{2i}C_{i}=\frac{2}{25}\left(C_{k+1}+\frac{4}{25}C_{k+2}+\left(\frac{4}{25}\right)^{2}C_{k+3}+\cdots\right).$

Since $C_{i+1}<4C_{i}$, the right-hand side is bounded from above by a
geometric series with factor $\nicefrac{{16}}{{25}}$ and we have the following
estimates

$\frac{2}{25}C_{k+1}\leqslant
d_{\boldsymbol{a}}(2k+1)\leqslant\frac{2}{9}C_{k+1}\qquad\qquad\text{and}\qquad\qquad\frac{1}{5}C_{k+1}\leqslant
d_{\boldsymbol{a}}(2k+2)\leqslant\frac{5}{9}C_{k+1}.$

Overall, both $d_{\boldsymbol{a}}(2k-1)$ and $d_{\boldsymbol{a}}(2k)$ are in
$\Theta(C_{k})=\Theta\left(\frac{4^{k}}{k^{\nicefrac{{3}}{{2}}}}\right)$.
Summarising, we get the following result.

######  Theorem 3.2.

For the substitution $\varrho_{\boldsymbol{a}}$ with $a_{i}=1$ for all $i$,
the number $\\#_{\boldsymbol{a}}(n)$ of tiles in
$\varrho_{\boldsymbol{a}}^{n}([0])$ has asymptotic expansion

$\\#_{\boldsymbol{a}}(n)\,\in\,\frac{3}{4}\left(\frac{5}{2}\right)^{n}+\Theta\left(\frac{2^{n}}{n^{\nicefrac{{3}}{{2}}}}\right).$

In particular, $r_{2}=2$ and $\theta(n)=n^{-3/2}$ in Theorem 2.7.

######  Remark 3.3.

Note that in the proof of quasi-compactness in [5, Thm. 3.5] the authors have
implicitly provided a bound for $r_{\text{ess}}(M)$, namely
$r_{\text{ess}}(M)\leqslant 2$ for all substitutions treated in this paper,
which we conjecture to be an equality. This suggests that, in the exact
expansion of $\\#_{\boldsymbol{a}}(n)$ of Theorem 3.2, the error term
completely comes from the essential spectrum. This is not true in general, as
there are (at most finitely many) Ruelle–Pollicott-type eigenvalues which may
show up; see Example 6.2.

##  4\. Stabilising sequences

In this section, we consider sequences ${\boldsymbol{a}}=(a_{i})_{i}$ with
$a_{0}>0$ that stabilise to a non-zero integer. So there is a $k$ such that
$a_{i}=a>0$ for every $i\geqslant k$. We mostly employ the same approach as in
Section 3, but it requires more linear algebra to deal with technicalities.

From Proposition 2.3, the inflation factor for the corresponding substitution

$\displaystyle\varrho_{\boldsymbol{a}}([0])$
$\displaystyle=[0]^{a_{0}}[1],\text{ and}$
$\displaystyle\varrho_{\boldsymbol{a}}([i])$
$\displaystyle=[0]^{a_{i}}[i-1][i+1]\text{ for }i>0$

is equal to $\lambda=\mu+\dfrac{1}{\mu}$ where $\mu\in(0,1)$ is the solution
of

$\displaystyle\frac{1}{\mu}=\sum_{i=0}^{\infty}a_{i}\mu^{i}$
$\displaystyle=a_{0}+a_{1}\mu+\cdots+a_{k-1}\mu^{k-1}+a\mu^{k}+a\mu^{k+1}+a\mu^{k+2}+\cdots$
$\displaystyle=a_{0}+a_{1}\mu+\cdots+a_{k-1}\mu^{k-1}+\frac{a\mu^{k}}{1-\mu}.$
(4)

From this, we can see that $\mu$ is an algebraic number, and so is $\lambda$.
More specifically, $\mu$ is a root of the following polynomial with integer
coefficients

$P(x)=1+(-1-a_{0})x+(a_{0}-a_{1})x^{2}+\cdots+(a_{k-2}-a_{k-1})x^{k}+(a_{k-1}-a)x^{k+1}.$

As before, we define the substitution matrix as

$\boldsymbol{A}=\left(\begin{array}[]{cccccc}a_{0}&a_{1}+1&a_{2}&a_{3}&a_{4}&\dots\\\
1&0&1&0&0&\ldots\\\ 0&1&0&1&0&\ldots\\\ 0&0&1&0&1&\ldots\\\
0&0&0&1&0&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right)$

and note that the elements in the first row stabilise to $a$ at some point. On
the right, $\boldsymbol{A}$ can be multiplied by row-vectors from $\ell^{1}$,
while on the left it can be multiplied by column-vectors from $\ell^{\infty}$.
These spaces roughly correspond to tile lengths and frequencies in the finite
alphabet setting.

We will estimate the number of letters in $\varrho_{\boldsymbol{a}}^{n}([0])$,
that is, $\\#_{\boldsymbol{a}}(n)=[(1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}$. The
results of [5] imply that the tiles have well defined frequencies $\nu([k])$,
as well as the natural tile lengths $\ell([k])$, see Propositions 2.3 and 2.4.
As before, the leading term is
$\nicefrac{{1}}{{c_{\boldsymbol{a}}}}\lambda^{n}$. Since we are only
interested in the discrepancy, we write

$\\#_{\boldsymbol{a}}(n):=[(1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}=\frac{1}{c_{\boldsymbol{a}}}\lambda^{n}+d_{\boldsymbol{a}}(n),$

where $c_{\boldsymbol{a}}$ is the expected tile length assuming $\ell([0])=1$.
Note that $\nicefrac{{1}}{{c_{\boldsymbol{a}}}}$ is exactly the density given
in Proposition 2.4.

Let $Q(x)=b_{0}+b_{1}x+\cdots+b_{m}x^{m}$ be the minimal polynomial of
$\lambda$. Define
${\boldsymbol{x}}_{\boldsymbol{a}}:=(1,1,1,\ldots)Q(\boldsymbol{A})$. For this
vector, one has

$[{\boldsymbol{x}}_{\boldsymbol{a}}\boldsymbol{A}^{n}]_{0}=[(1,1,1,\ldots)Q(\boldsymbol{A})\boldsymbol{A}^{n}]_{0}=b_{0}d_{\boldsymbol{a}}(n)+b_{1}d_{\boldsymbol{a}}(n+1)+\cdots+b_{m}d_{\boldsymbol{a}}(n+m),$
(5)

as the exponential term $\lambda^{n}$ vanishes. For example, in Section 3, we
had $Q(x)=2x-5$ and ${\boldsymbol{x}}_{\boldsymbol{a}}=(-1,1,1,\ldots)$.

Below, we determine the growth rate of the left-hand side in order to estimate
the growth rate of the right-hand side. In order to justify that, we need to
establish that the right-hand side is non-zero.

######  Lemma 4.1.

Suppose $\varrho_{\boldsymbol{a}}$ is a non-constant length substitution.
Then, for every non-zero polynomial $f(x)$ with integer coefficients, one has
$(1,1,1,\ldots)f(\boldsymbol{A})\neq 0$.

###### Proof.

Let $x_{i}$ be the largest index such that in
$(1,1,1,\ldots)\boldsymbol{A}^{i}$, the entries on places $x_{i}$ and
$x_{i}+1$ are different. If all entries are equal, we set $x_{i}=-1$. Since
$(1,1,1,\ldots)\boldsymbol{A}^{i}$ stabilises, the values $x_{i}$ are well
defined for every $i\geqslant 0$ and $x_{0}=-1$.

We claim that the sequence $x_{i}$ is increasing. Indeed, $x_{0}=-1$ and
$(1,1,1,\ldots)\boldsymbol{A}$ is not a vector with all equal entries because
$\varrho_{\boldsymbol{a}}$ is not a constant-length substitution. We consider
several cases. Recall that $k$ is the index when sequence $\boldsymbol{a}$
stabilises to the value $a$.

Case 1: $k>1$. Then
$(1,1,1,\ldots)\boldsymbol{A}=(a_{0}+1,a_{1}+2,\ldots,a_{k-1}+2,a+2,a+2,\ldots)$
and $x_{1}=k-1$. Using induction, let
$(1,1,1,\ldots)\boldsymbol{A}^{i}=(c_{0},\ldots,c_{x_{i}},c,c,c,\ldots)$ with
$x_{i}\geqslant k-1$ with $c_{x_{i}}\neq c$. Then,
$[(1,1,1,\ldots)\boldsymbol{A}^{i+1}]_{x_{i}+1}=c_{0}a+c_{x_{i}}+c$, while
$[(1,1,1,\ldots)\boldsymbol{A}^{i+1}]_{x_{i}+2}=c_{0}a+2c$ and these two
entries are different. Therefore, $x_{i+1}>x_{i}$ which settles the case.

Here, we have used $x_{i}\geqslant k-1$. Thus $x_{i}+1\geqslant k$ and $c_{0}$
is multiplied by $a$ as the initial entry of the corresponding column of the
matrix $\boldsymbol{A}$.

Case 2: $k=0$. Then $a_{i}=a\geqslant 1$ and
$(1,1,1,\ldots)\boldsymbol{A}=(a+1,a+2,a+2,\ldots)$ so $x_{1}=0>x_{0}$. After
that,

$(1,1,1,\ldots)\boldsymbol{A}^{2}=(a^{2}+2a+2,a^{2}+3a+3,a^{2}+3a+4,a^{2}+3a+4,a^{2}+3a+4,\ldots)$

and $x_{2}=1>x_{1}$. Now we can proceed as in the previous case.

Case 3: $k=1$. Then $(a_{i})_{i}=(b,a,a,a,\ldots)$ and $b\neq a+1$ since
otherwise $\varrho_{{\boldsymbol{a}}}$ would be a constant-length
substitution. In this case,
$(1,1,1,\ldots)\boldsymbol{A}=(b+1,a+2,a+2,\ldots)$ and $x_{1}=0>x_{0}$. After
that,

$(1,1,1,\ldots)\boldsymbol{A}^{2}=(b^{2}+a+b+2,ab+2a+b+3,ab+3a+4,ab+3a+4,ab+3a+4,\ldots)$

and $x_{2}=1>x_{1}$. Again, the rest follows similarly to the first case.

Since $x_{i}$ is increasing, the vectors $(1,1,1,\ldots)\boldsymbol{A}^{i}$
are linearly independent, and this completes the proof. ∎

Let $\mathcal{V}$ be the space of all stabilising sequences
${\boldsymbol{x}}=(x_{0},x_{1},x_{2},\ldots)$ of real numbers such that
${\displaystyle\sum_{i=0}^{\infty}x_{i}\mu^{i}=0}$. The space $\mathcal{V}$ is
an invariant subspace of the operator $\boldsymbol{B}$ defined by the right
multiplication by $\boldsymbol{A}$. Moreover, since
$\boldsymbol{A}(1,\mu,\mu^{2},\mu^{3},\ldots)^{t}=\lambda(1,\mu,\mu^{2},\mu^{3},\ldots)^{t}$,
we get that

${\boldsymbol{x}}_{\boldsymbol{a}}\cdot(1,\mu,\mu^{2},\mu^{3},\ldots)^{t}=(1,1,1,\ldots)Q(\boldsymbol{A})(1,\mu,\mu^{2},\mu^{3},\ldots)^{t}=0$

and so ${\boldsymbol{x}}_{\boldsymbol{a}}\in\mathcal{V}$.

While $\mathcal{V}$ has a countable basis, it should be related to the minimal
polynomial for $\mu$, which can be different from $P(x)$. Thus, we will work
with a certain subspace of $\mathcal{V}$. In what follows, we define
${\boldsymbol{e}}_{0}=(-1,a_{0},a_{1},\ldots,a_{k-1},a,a,a,\ldots)$, and

$\begin{array}[]{r}{\boldsymbol{e}}_{1}=(1,-1-a_{0},a_{0}-a_{1},a_{1}-a_{2},\ldots,a_{k-2}-a_{k-1},a_{k-1}-a,0,0,0,0,\ldots),\\\
{\boldsymbol{e}}_{2}=(0,1,-1-a_{0},a_{0}-a_{1},a_{1}-a_{2},\ldots,a_{k-2}-a_{k-1},a_{k-1}-a,0,0,0,\ldots),\\\
{\boldsymbol{e}}_{3}=(0,0,1,-1-a_{0},a_{0}-a_{1},a_{1}-a_{2},\ldots,a_{k-2}-a_{k-1},a_{k-1}-a,0,0,\ldots),\end{array}$
(6)

and so on. More specifically, the entries of ${\boldsymbol{e}}_{0}$ are taken
from Eq. (4) defining $\mu$, and for all other ${\boldsymbol{e}}_{i}$, the
entries are the coefficients of the polynomial $P(x)$ originating from Eq. (4)
that has $\mu$ as a root. This implies that each ${\boldsymbol{e}}_{i}$ is in
$\mathcal{V}$. Moreover, the span $\langle\mathcal{E}\rangle$ of
$\mathcal{E}:=\mathcal{\\{}{\boldsymbol{e}}_{i}\\}_{i\in\mathbb{N}_{0}}$ is a
subspace of finite codimension in $\mathcal{V}$.

Again, straightforward computations show that
$\boldsymbol{B}({\boldsymbol{e}}_{0})={\boldsymbol{e}}_{0}+{\boldsymbol{e}}_{1}$
and
$\boldsymbol{B}({\boldsymbol{e}}_{i})={\boldsymbol{e}}_{i-1}+{\boldsymbol{e}}_{i+1}$
for $i>0$. In other words, $\langle\mathcal{E}\rangle$ is an invariant
subspace for $\boldsymbol{B}$ and the matrix of the restriction of
$\boldsymbol{B}$ on $\langle\mathcal{E}\rangle$ in $\mathcal{E}$ is

${\boldsymbol{B}^{\prime}}=\left(\begin{array}[]{cccccc}1&1&0&0&0&\dots\\\
1&0&1&0&0&\ldots\\\ 0&1&0&1&0&\ldots\\\ 0&0&1&0&1&\ldots\\\
0&0&0&1&0&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right).$

######  Lemma 4.2.

There exists a non-zero polynomial $R(x)$ with integer coefficients such that
${\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})$ is a (finite) linear
combination of vectors from $\mathcal{E}$.

###### Proof.

The vector ${\boldsymbol{x}}_{\boldsymbol{a}}$ is in $\mathcal{V}$ and
$\mathcal{V}$ is an invariant subspace of $\boldsymbol{B}$. Since
$\langle\mathcal{E}\rangle$ has a finite codimension in $\mathcal{V}$, the
(cosets of) vectors
${\boldsymbol{x}}_{\boldsymbol{a}},\boldsymbol{B}({\boldsymbol{x}}_{\boldsymbol{a}}),\boldsymbol{B}^{2}({\boldsymbol{x}}_{\boldsymbol{a}}),\ldots$
are linearly dependent in the factor space
$\mathcal{V}/\langle\mathcal{E}\rangle$. Since all entries are integers, there
exists a non-trivial integer linear combination of these vectors that lies in
$\langle\mathcal{E}\rangle$. ∎

It is worth noting that Section 3 gives the simplest example and $R(x)=1$
because $\langle\mathcal{E}\rangle=\mathcal{V}$ in that section and
${\boldsymbol{x}}_{\mathbf{a}}\in\mathcal{V}$ right away.

######  Lemma 4.3.

For the polynomial $R(x)$ from Lemma 4.2, there exists a non-zero polynomial
$g(x)$ with integer coefficients such that
${\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})=g(\boldsymbol{B})({\boldsymbol{e}}_{0})$.

###### Proof.

The proof of existence follows from the fact that, for each $i$,
$\boldsymbol{B}^{i}({\boldsymbol{e}}_{0})-{\boldsymbol{e}}_{i}$ belongs to the
$\mathbb{Z}$-span of
$\\{{\boldsymbol{e}}_{0},\ldots,{\boldsymbol{e}}_{i-1}\\}$. By Lemma 4.1, the
left-hand side is non-zero and therefore $g(x)$ is nonzero as well. ∎

######  Definition 4.4.

For a polynomial
$\alpha(x)=\alpha_{0}+\alpha_{1}x+\cdots+\alpha_{m}x^{m}\in\mathbb{R}[x]$ we
define the $\alpha$-twist of $d_{\boldsymbol{a}}$ as

$\alpha*d_{\boldsymbol{a}}(n):=\alpha_{0}d_{\boldsymbol{a}}(n)+\alpha_{1}d_{\boldsymbol{a}}(n+1)+\cdots+\alpha_{m}d_{\boldsymbol{a}}(n+m).$

With this convention, the right-hand side in Eq. (5) for
$[{\boldsymbol{x}}_{\boldsymbol{a}}\boldsymbol{A}^{n}]_{0}$ can be written as
$Q*d_{\boldsymbol{a}}$.

The following lemma is straightforward.

######  Lemma 4.5.

For every polynomial $\alpha(x)$, if
$\boldsymbol{y}={\boldsymbol{x}}_{\boldsymbol{a}}\alpha(\boldsymbol{A})$, then
$[\boldsymbol{y}\boldsymbol{A}^{n}]_{0}=(\alpha Q)*d_{\boldsymbol{a}}$.

######  Corollary 4.6.

In the notations used above,

$[{\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})\boldsymbol{A}^{n}]_{0}=(RQ)*d_{\boldsymbol{a}}.$

Now we are ready to formulate an analogue of Lemma 3.1 for the general case of
stabilising sequences.

######  Lemma 4.7.

There exists an integer $p\geqslant 0$ and integers $\alpha_{i},\beta_{i}$
such that

$[{\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})\boldsymbol{A}^{n}]_{0}=\left\\{\begin{array}[]{rl}\alpha_{0}C_{k}+\cdots+\alpha_{p}C_{k+p}&\text{
if }n=2k,\\\ \beta_{0}C_{k}+\cdots+\beta_{p}C_{k+p}&\text{ if
}n=2k+1.\end{array}\right.$

Furthermore, if $g(x)=\gamma_{0}+\gamma_{1}x+\cdots+\gamma_{m}x^{m}$ is the
polynomial from Lemma 4.3, then $\alpha_{i}=-\gamma_{2i}$, and
$\beta_{i+1}=-\gamma_{2i+1}$ for $i\geqslant 0$ while $\beta_{0}=0$. Thus, not
all $\alpha_{i},\beta_{i}$ are zero.

###### Proof.

From Lemma 4.3,
${\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})\boldsymbol{A}^{n}=\boldsymbol{B}^{n}(g(\boldsymbol{B})({\boldsymbol{e}}_{0})).$
Suppose $g(x)=\gamma_{0}+\gamma_{1}x+\cdots+\gamma_{m}x^{m}$, then

${\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})\boldsymbol{A}^{n}=\boldsymbol{B}^{n}(g(\boldsymbol{B})({\boldsymbol{e}}_{0}))=\gamma_{0}\boldsymbol{B}^{n}({\boldsymbol{e}}_{0}))+\gamma_{1}\boldsymbol{B}^{n+1}({\boldsymbol{e}}_{0}))+\cdots+\gamma_{m}\boldsymbol{B}^{n+m}({\boldsymbol{e}}_{0})).$

Since only ${\boldsymbol{e}}_{0}$ and ${\boldsymbol{e}}_{1}$ have non-zero
first entry, we can use the approach of Lemma 3.1 to show that the first entry
of $\boldsymbol{B}^{i}({\boldsymbol{e}}_{0})$ is either $0$ or the negative of
a Catalan number depending on the parity of $i$.

More precisely, this approach implies that if $n=2k$, then

$\alpha_{0}=-\gamma_{0},\qquad\alpha_{1}=-\gamma_{2},\qquad\alpha_{2}=-\gamma_{4},$

and so on, and if $n=2k+1$, then $\beta_{0}=0$ and

$\beta_{1}=-\gamma_{1},\qquad\beta_{2}=-\gamma_{3},\qquad\beta_{3}=-\gamma_{5},$

and so on. These equalities give the claimed values for $\alpha_{i}$ and
$\beta_{i}$ and also immediately show that not all $\alpha_{i}$ and
$\beta_{i}$ are zero since $g(x)$ is a non-zero polynomial. ∎

######  Proposition 4.8.

Let $p\geqslant 0$ and let $F(k)=\alpha_{0}C_{k}+\cdots+\alpha_{p}C_{k+p}$ for
some integers $\alpha_{i}$ at least one of which is not $0$. Then, there
exists an integer $0\leqslant q\leqslant p$ such that ${\displaystyle
F(k)\in\Theta\left(\frac{4^{k}}{k^{q+\nicefrac{{3}}{{2}}}}\right)}$.

###### Proof.

First of all, note that the coefficients of the power series
$\sum_{k}F(k)x^{k+p}$ for large $k$ coincide with the coefficients of the
series for

$\frac{1-\sqrt{1-4x}}{2x}(\alpha_{0}x^{p}+\cdots+\alpha_{p}).$

Since $\sqrt{1-4x}$ is not a rational function, the values $F(k)$ cannot all
be zero starting for some $k$.

Recall that $C_{k+1}=\frac{2(2k+1)}{k+2}C_{k}$. Therefore

$C_{k+i}=C_{k}\cdot\frac{2^{i}(2k+1)\cdots(2k+i)}{(k+2)\cdots(k+i+1)}=C_{k}\frac{P_{i}(k)}{Q_{i}(k)}$

for some polynomials $P_{i},Q_{i}$ of degree $i$. This implies that

$F(k)=C_{k}\cdot\mathcal{R}(k),$

where $\mathcal{R}(k)$ is a rational function with integer coefficients and
the numerator and denominator of $\mathcal{R}$ are polynomials of degree at
most $p$. The numerator of $\mathcal{R}$ cannot be 0 because $F(k)$ does not
stabilise to $0$. Thus, $\mathcal{R}(k)\in\Theta(\nicefrac{{1}}{{k^{q}}})$ for
some integer $q$ between $0$ and $p$. Taking into account the asymptotics for
$C_{k}$ completes the proof. ∎

######  Remark 4.9.

A similar result without the specific power of $k$ in the denominator can be
obtained using algebraic generating functions. We refer to [23, Ch. 6] for
more details.

######  Theorem 4.10.

There is an integer $q$ such that a subsequence of $d_{\boldsymbol{a}}(n)$
belongs to $\Omega\left(\dfrac{2^{n}}{n^{q+\nicefrac{{3}}{{2}}}}\right)$.

###### Proof.

Assume to the contrary that $d_{\boldsymbol{a}}(n)\in
o\left(\frac{2^{n}}{n^{q+\nicefrac{{3}}{{2}}}}\right)$ for every integer $q$.
Using Lemma 4.7 and Proposition 4.8 we get that either for odd $n$ or for even
$n$, the subsequence
$[{\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})\boldsymbol{A}^{n}]_{0}$
is in $\Theta\left(\frac{2^{n}}{n^{q+\nicefrac{{3}}{{2}}}}\right)$ for some
non-negative integer $q$.

From Corollary 4.6,
$[{\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})\boldsymbol{A}^{n}]_{0}=(RQ)*d_{\boldsymbol{a}}$.
By our assumption, for every fixed $i\geqslant 0$, $d_{\boldsymbol{a}}(n+i)$
is in $o\left(\frac{2^{n}}{n^{q+\nicefrac{{3}}{{2}}}}\right)$ and so is the
$RQ$-twist $(RQ)*d_{\boldsymbol{a}}$, which contradicts the previous estimate.
∎

It is clear that
$\Omega\left(\dfrac{2^{n}}{n^{q_{0}+\nicefrac{{3}}{{2}}}}\right)\subset\Omega\left(\dfrac{2^{n}}{n^{q+\nicefrac{{3}}{{2}}}}\right)$,
for all $q\geqslant q_{0}$, and so one can assume without loss of generality
that $q$ is non-negative in the theorem above. This formulation is closer to
_lower bounds_ for asymptotic behaviours exhibited by substitutions on finite
alphabets. We emphasise, however, that examples for which
$d_{\boldsymbol{a}}(n)$ exhibits _precise_ asymptotics (as in Theorem 3.2)
with non-negative $q$ can only occur in the infinite alphabet setting. On the
other hand, there also exist examples for which $q=-1$ in the actual
asymptotics along a subsequence; see Example 6.4.

######  Remark 4.11.

It is worth mentioning that there is an alternative way to prove Theorem 4.10
without using Catalan numbers at all. First, one observes that the matrix
$\frac{1}{2}B$ is the transition matrix of a random walk on the non-negative
integers. The central limit theorem implies that this random walk tends to a
Gaussian standard distribution for large $n$, and can thus be described by
$f(x)=\frac{1}{\sqrt{2\pi n}}e^{\nicefrac{{-x^{2}}}{{2n}}}$.

The $p$-th derivative $f^{(p)}$ can be related to the linear combinations of
Catalan numbers in Lemma 4.7. It turns out that $f^{(k)}(0)=0$ for $k$ odd,
and $f^{(k)}=c\cdot\frac{1}{n^{(2p+1)/2}}$ for $p$ even. Multiplying again
with $2^{n}$ yields exactly the growth rate in Theorem 4.10.

However, using the approach with Catalan numbers does not only yield Theorem
4.10 but gives us exact values for the results in Sections 3 and 5.

######  Corollary 4.12.

Suppose $\varrho_{\boldsymbol{a}}$ is a non-constant length substitution. Then
no Delone set $\Lambda$ arising from $\varrho_{\boldsymbol{a}}$ is bounded
distance equivalent to $\alpha\mathbb{Z}$, for any $\alpha>0$.

This is just a consequence of Theorem 4.10 together with an infinite version
of Hall’s marriage theorem [19].

##  5\. Two further examples — precise values

In this section, we apply the general framework from the last section to two
particular examples having the same values $\mu$ and $\lambda$. This yields
exact expressions for the respective discrepancies and illustrates to what
extent equal values for $\mu$ and $\lambda$ may still allow for different
discrepancy functions; namely here: equal asymptotics, but with different
constants.

######  Example 5.1.

For this example, we consider ${\boldsymbol{a}}=(1,2,2,2,\ldots)$. The
associated substitution matrix is

$\boldsymbol{A}=\left(\begin{array}[]{cccccc}1&3&2&2&2&\dots\\\
1&0&1&0&0&\ldots\\\ 0&1&0&1&0&\ldots\\\ 0&0&1&0&1&\ldots\\\
0&0&0&1&0&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right).$

The equation that defines $\mu$ is

$\frac{1}{\mu}=1+2\mu+2\mu^{2}+2\mu^{3}+\cdots=-1+\frac{2}{1-\mu}.$

It transforms into $1-2\mu-\mu^{2}=0$ so $\mu=\sqrt{2}-1$ and
$\lambda=\mu+\nicefrac{{1}}{{\mu}}=2\sqrt{2}$, with the minimal polynomial for
$\lambda$ being $Q(x)=x^{2}-8$.

Thus,
${\boldsymbol{x}}_{\boldsymbol{a}}=(1,1,1,\ldots)(\boldsymbol{A}^{2}-8\boldsymbol{I})=(-2,2,4,4,4,\ldots)$
and

$[{\boldsymbol{x}}_{\boldsymbol{a}}\boldsymbol{A}^{n}]_{0}=(x^{2}-8)*d_{\boldsymbol{a}}=d_{\boldsymbol{a}}(n+2)-8d_{\boldsymbol{a}}(n).$

Now we turn our attention to the space $\mathcal{V}$ of all stabilizing
sequences that satisfy ${\displaystyle\sum x_{i}\mu^{i}=0}$ and to the
subspace spanned by the vectors ${\boldsymbol{e}}_{i}$ where

$\begin{array}[]{l}{\boldsymbol{e}}_{0}=(-1,1,2,2,2,2,\ldots),\\\
{\boldsymbol{e}}_{1}=(1,-2,-1,0,0,0,\ldots),\\\
{\boldsymbol{e}}_{2}=(0,1,-2,-1,0,0,\ldots),\\\
{\boldsymbol{e}}_{3}=(0,0,1,-2,-1,0,\ldots),\end{array}$

and so on. These are the vectors from Eq. (6).

The vector ${\boldsymbol{x}}_{a}$ lies already in this subspace because
${\boldsymbol{x}}_{\boldsymbol{a}}=2{\boldsymbol{e}}_{0}$. So we can use
$R(x)=1$ in Lemma 4.2. Actually, in this particular example,
$\mathcal{V}=\left\langle\mathcal{E}\right\rangle$, as it was in Section 3.

Also, in Lemma 4.3, we can use $g(x)=2$. Plugging this data into Corollary 4.6
and Lemma 4.7, we get
${\boldsymbol{x}}_{a}\boldsymbol{A}^{n}=2\boldsymbol{B}^{n}({\boldsymbol{e}}_{0})$
and therefore

$d_{\boldsymbol{a}}(n+2)-8d_{\boldsymbol{a}}(n)=[{\boldsymbol{x}}_{a}\boldsymbol{A}^{n}]_{0}=\left\\{\begin{array}[]{rl}-2C_{k}&\text{
if }n=2k,\\\ 0&\text{ if }n=2k+1.\end{array}\right.$

At this point we can see that
$d_{\boldsymbol{a}}(2k+1)=8^{k}d_{\boldsymbol{a}}(1)$ so this subsequence
appears to be in $\Theta((2\sqrt{2})^{n})$. Such a term must be a leading term
in $\\#_{\boldsymbol{a}}(n)=[(1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}$ and should
not appear in $d_{\boldsymbol{a}}(n)$. However, once we track the expected
length $c_{\boldsymbol{a}}$, this will not be an issue.

More specifically, the frequency of the tile $[i]$ is
$(1-\mu)\mu^{i}=(2-\sqrt{2})(\sqrt{2}-1)^{i}$ and the length of the tile $[i]$
is $\sqrt{2}+1-\sqrt{2}(\sqrt{2}-1)^{i}$. This gives the expected tile length
to be

$c_{\boldsymbol{a}}=\sum_{i=0}^{\infty}(2-\sqrt{2})(\sqrt{2}-1)^{i}\Bigl{(}\sqrt{2}+1-\sqrt{2}(\sqrt{2}-1)^{i}\Bigr{)}=\sqrt{2}.$

One then has

$\\#_{\boldsymbol{a}}(n)=[(1,1,1,\ldots)\boldsymbol{A}^{n}]_{0}=\frac{1}{c_{\boldsymbol{a}}}\lambda^{n}+d_{\boldsymbol{a}}(n)=\frac{1}{\sqrt{2}}(2\sqrt{2})^{n}+d_{\boldsymbol{a}}(n).$

This gives $d_{\boldsymbol{a}}(0)=1-\nicefrac{{1}}{{\sqrt{2}}}$ and
$d_{\boldsymbol{a}}(1)=0$ because
$(1,1,1,...)\boldsymbol{A}=(2,4,4,4,\ldots)$. Therefore,
$d_{\boldsymbol{a}}(2k+1)=0$ for every integer $k\geqslant 0$ due to the
recurrence relation above.

If $n$ is even, a similar approach as in Section 3 using tails of the power
series from Catalan numbers gives the growth rate
$d_{\boldsymbol{a}}(n)\in\Theta\left(\frac{2^{n}}{n^{\nicefrac{{3}}{{2}}}}\right)$.

The next example shares the same $\mu$ and $\lambda$ with Example 5.1, but one
has $\mathcal{V}\neq\left\langle\mathcal{E}\right\rangle$. Hence, we will need
to apply all steps for the general case in Section 4.

######  Example 5.2.

Consider ${\boldsymbol{a}}=(1,1,3,4,4,4,4,\ldots)$. The associated
substitution matrix is

$\boldsymbol{A}=\left(\begin{array}[]{ccccccc}1&2&3&4&4&4&\dots\\\
1&0&1&0&0&0&\ldots\\\ 0&1&0&1&0&0&\ldots\\\ 0&0&1&0&1&0&\ldots\\\
0&0&0&1&0&1&\ldots\\\ 0&0&0&0&1&0&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right).$

The equation that defines $\mu$ is

$\frac{1}{\mu}=1+\mu+3\mu^{2}+4\mu^{3}+4\mu^{4}+4\mu^{5}+\cdots=-3-3\mu-\mu^{2}+\frac{4}{1-\mu}.$

It transforms into $1-2\mu-2\mu^{3}-\mu^{4}=0$ or
$(1-2\mu-\mu^{2})(1+\mu^{2})=0$ so $\mu=\sqrt{2}-1$ and
$\lambda=\mu+\nicefrac{{1}}{{\mu}}=2\sqrt{2}$, with minimal polynomial
$Q(x)=x^{2}-8$ as before.

However,
${\boldsymbol{x}}_{\boldsymbol{a}}=(1,1,1,\ldots)(\boldsymbol{A}^{2}-8\boldsymbol{I})=(-3,1,7,11,12,12,12,12,\ldots)$.

Since $\mu$ and $\lambda$ are the same as in the previous example,
$\mathcal{V}$ is still the space of all stabilizing sequences that satisfy
${\displaystyle\sum x_{i}\mu^{i}=0}$. But the vectors ${\boldsymbol{e}}_{i}$
and the subspace they span are different now. In particular,
$\mathcal{E}=\\{{\boldsymbol{e}}_{i}\\}_{i\geqslant 0}$ where

$\begin{array}[]{l}{\boldsymbol{e}}_{0}=(-1,1,1,3,4,4,4,\ldots),\\\
{\boldsymbol{e}}_{1}=(1,-2,0,-2,-1,0,0,0,\ldots),\\\
{\boldsymbol{e}}_{2}=(0,1,-2,0,-2,-1,0,0,\ldots),\\\
{\boldsymbol{e}}_{3}=(0,0,1,-2,0,-2,-1,0,\ldots),\end{array}$

and so on. In this case, the span $\langle\mathcal{E}\rangle$ is of
codimension $2$ in $\mathcal{V}$ and ${\boldsymbol{x}}_{\boldsymbol{a}}$ is
not in the span.

Observing that
${\boldsymbol{x}}_{\boldsymbol{a}}=3{\boldsymbol{e}}_{0}+(0,-2,4,2,0,0,0,\ldots)$,
we write

$\begin{array}[]{rl}{\boldsymbol{x}}_{\boldsymbol{a}}+\langle\mathcal{E}\rangle=&(0,-2,4,2,0,0,0,\ldots)+\langle\mathcal{E}\rangle,\text{
and}\\\
{\boldsymbol{x}}_{\boldsymbol{a}}\boldsymbol{A}+\langle\mathcal{E}\rangle=&(-2,4,0,4,2,0,0,\ldots)+\langle\mathcal{E}\rangle=-2{\boldsymbol{e}}_{1}+\langle\mathcal{E}\rangle=\langle\mathcal{E}\rangle.\\\
\end{array}$

Thus, we can take $R(x)=x$ in Lemma 4.2 and write

${\boldsymbol{x}}_{{\boldsymbol{a}}}\boldsymbol{A}=(3{\boldsymbol{e}}_{0}+(0,-2,4,2,0,0,0,\ldots))\boldsymbol{A}=3({\boldsymbol{e}}_{0}+{\boldsymbol{e}}_{1})-2{\boldsymbol{e}}_{1}=3{\boldsymbol{e}}_{0}+{\boldsymbol{e}}_{1}.$

For Lemma 4.3, we take $g(x)=x+2$ because

$(\boldsymbol{B}+2\boldsymbol{I})({\boldsymbol{e}}_{0})=({\boldsymbol{e}}_{0}+{\boldsymbol{e}}_{1})+2{\boldsymbol{e}}_{0}={\boldsymbol{x}}_{{\boldsymbol{a}}}\boldsymbol{A}={\boldsymbol{x}}_{{\boldsymbol{a}}}R(\boldsymbol{A}).$

Then,
${\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})\boldsymbol{A}^{n}=\boldsymbol{B}^{n}((\boldsymbol{B}+2\boldsymbol{I})({\boldsymbol{e}}_{0}))=\boldsymbol{B}^{n+1}({\boldsymbol{e}}_{0})+2\boldsymbol{B}^{n}({\boldsymbol{e}}_{0})$.
We use $RQ=x(x^{2}-8)$ in Corollary 4.6 and Lemma 4.7 and write

$d_{\boldsymbol{a}}(n+3)-8d_{\boldsymbol{a}}(n+1)=(x(x^{2}-8))*d_{\boldsymbol{a}}=[{\boldsymbol{x}}_{\boldsymbol{a}}R(\boldsymbol{A})\boldsymbol{A}^{n}]_{0}=\left\\{\begin{array}[]{rl}-2C_{k},&\text{
if }n=2k,\\\ -C_{k+1},&\text{ if }n=2k+1.\end{array}\right.$

Here, we can see that the two expressions for even and odd $n$ can be
different linear combinations of (different) Catalan numbers. Nevertheless, we
still have
$d_{\boldsymbol{a}}(n)\in\Theta\left(\frac{2^{n}}{n^{\nicefrac{{3}}{{2}}}}\right)$
as the subsequences of odd and even $n$ can be written using tails of the
Catalan series as in Section 3 and as in the previous example. However, the
constants in the inequalities defining the order of growth are different for
odd and even $n$.

##  6\. Even more examples — numerical evidence

In this section, we give more examples of eventually constant sequences
${\boldsymbol{a}}$ that lead to various behaviours of the tile counting
function that have not appeared in this paper so far. We provide examples of
sequences which (i) give rise to eigenvalues different from $\lambda$ which
show up in the asymptotics, (ii) admit “fake” eigenvalues that appear in
finding the general solution of the equation in Lemma 4.7 treated as a linear
recurrence relation, but do not appear in the actual numerical solution, and
(iii) illustrate the fact that, in Theorem 4.10, the parameter $q$ for actual
asymptotics may have negative values as well.

For each example described below, our computational experiments in Wolfram
Mathematica [25] are organised as follows.

Given the sequence ${\boldsymbol{a}}$, we generate the matrix
$\boldsymbol{A}_{1}$ obtained from $\boldsymbol{A}$ by taking its upper-left
corner of size $201\times 201$. For the vector
${\boldsymbol{t}}=(1,0,0,\ldots,0)^{t}$ of size 201 and for every
$n=1,\ldots,200$, the sum of entries of $\boldsymbol{A}_{1}^{n}\boldsymbol{t}$
counts the number $\\#_{\boldsymbol{a}}(n)$ of tiles in the supertile
$\varrho_{\boldsymbol{a}}^{n}([0])$ because none of these supertiles contain
tiles outside of $\\{[0],[1],\ldots,[200]\\}$.

Using Proposition 2.3, we can find precise values of the respective $\mu$ and
$\lambda$, and the density of the resulting Delone set. This allows us to find
the discrepancy function $d_{\boldsymbol{a}}(n)$ for $n=1,\ldots,200$ and, in
the cases below, infer its correct asymptotics.

######  Remark 6.1.

Whereas the values in our computations are exact for $n$ up to 200, they are
pretty accurate for much larger $n$: as outlined in Remark 4.11 we can
describe the discrepancy as a random walk on the non-negative integers. By the
law of the iterated logarithm [11, 13], our random walk stays below position
$n$ after essentially $n^{2}$ steps almost surely (more precisely, after
$\sqrt{2\log\log n^{2}}n^{2}$ steps or less). So we might alternatively have
carried out the computations up to $n=10^{4}$ or so, without losing much
precision. As before, we decided to restrict ourselves to exact values.

The frequencies and density can be obtained from Proposition 2.4. An
alternative, and for most cases described below more useful, method to get the
length function $\ell$ is to treat it as a left eigenvector of
$\boldsymbol{A}$ with eigenvalue $\lambda$. The structure of $\boldsymbol{A}$
ensures that, starting from some $k$, $\ell$ satisfies the equation

$a+\ell([k-1])+\ell([k+1])=\lambda\ell([k]),$

where $a$ is the value to which ${\boldsymbol{a}}$ stabilises. This equation
can be treated as non-homogeneous linear recurrence which can be solved
explicitly knowing several starting terms (in this case, we have $k+1$ initial
conditions). We can also simplify the process a bit by using that $\ell$ must
be continuous, and hence bounded on the alphabet $\mathcal{A}$.

For all examples described below, we have $k=1$ or $k=2$, so the initial
values of the corresponding recurrence as well as the density can be computed
manually. We illustrate how this approach works in the example below.

######  Example 6.2.

Consider the sequence ${\boldsymbol{a}}=(1,9,9,9,\ldots)$. As we will see, the
bound from Theorem 4.10 is a lower bound in this case, but the actual growth
of the discrepancy is exponential with base greater than $2$. Nevertheless, we
can guess the leading term of the discrepancy by finding additional
eigenvectors of the infinite matrix $\boldsymbol{A}$, and by isolating the
corresponding exponential term; the remaining part of discrepancy still
exhibits Catalan-like growth.

Using Eq. (4), $\mu$ can be computed from the equation

$\frac{1}{\mu}=\sum
a_{i}\mu^{i}=1+9(\mu+\mu^{2}+\mu^{3}+\cdots)=1+\frac{9\mu}{1-\mu}.$

This transforms into the quadratic equation $8\mu^{2}+2\mu-1=0$ with two
solutions $\mu=\nicefrac{{1}}{{4}}$ and $\mu_{*}=\nicefrac{{-1}}{{2}}$, where
the former defines the inflation factor $\lambda=\nicefrac{{17}}{{4}}$.

In order to find the lengths, we recall that the vector
$(1,\ell([1]),\ell([2]),\ell([3]),\ldots)$ is a left $\lambda$-eigenvector of
the matrix

$\boldsymbol{A}=\left(\begin{array}[]{cccccc}1&10&9&9&9&\dots\\\
1&0&1&0&0&\ldots\\\ 0&1&0&1&0&\ldots\\\ 0&0&1&0&1&\ldots\\\
0&0&0&1&0&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right).$

Therefore, $1+\ell([1])=\nicefrac{{17}}{{4}}$ and
$\ell([1])=\nicefrac{{13}}{{4}}$. Additionally, for $k\geqslant 1$,

$9+\ell([k-1])+\ell([k+1])=\frac{17}{4}\ell([k]).$

Rewriting the above equation into

$\ell([k+1])-\frac{17}{4}\ell([k])+\ell([k-1])=-9,$

we can treat it as a non-homogeneous linear recurrence with solution
$\ell([k])=\alpha\cdot\left(\nicefrac{{1}}{{4}}\right)^{k}+\beta\cdot
4^{k}+4$, with initial terms $\ell([0])=1$ and
$\ell([1])=\nicefrac{{13}}{{4}}$.

The initial values allow us to find $\alpha=-3$ and $\beta=0$. Note that the
latter guarantees that $\ell([\cdot])$ is bounded, as it is required for left
eigenvectors of $\boldsymbol{A}$. Overall,
$\ell([k])=4-\nicefrac{{3}}{{4^{k}}}$.

Recalling that the frequency of the letter $[k]$ is $\nu([k])=(1-\mu)\mu^{k}$,
we get the average tile length to be

$c_{\boldsymbol{a}}=\sum_{k=0}^{\infty}\ell([k])\nu([k])=\sum_{k=0}^{\infty}\left(4-\frac{3}{4^{k}}\right)\cdot\left(1-\frac{1}{4}\right)\frac{1}{4^{k}}=\frac{8}{5}.$

Hence the corresponding density is $\nicefrac{{5}}{{8}}$.

As before, the density gives the coefficient for the leading term. That is,

$\\#_{\boldsymbol{a}}(n)\;\in\;\frac{5}{8}\left(\frac{17}{4}\right)^{n}+o\left(\left(\frac{17}{4}\right)^{n}\right).$

For the discrepancy, we want to estimate
$\\#_{\boldsymbol{a}}(n)-\frac{5}{8}\left(\frac{17}{4}\right)^{n}$.

Initally, we expected that this difference will grow as
$\dfrac{2^{n}}{n^{\nicefrac{{3}}{{2}}}}$ as in Theorem 3.2, but it turns out
that it actually grows faster. The numerical computations suggest that the
growth rate comes from the second solution $\mu_{*}=\nicefrac{{-1}}{{2}}$ of
the quadratic equation for $\mu$ discussed above.

More precisely, $\mu_{*}$ gives rise to
$\lambda_{*}=\mu_{*}+\nicefrac{{1}}{{\mu_{*}}}=\nicefrac{{-5}}{{2}}$ which is
an eigenvalue of $\boldsymbol{A}$ with left eigenvector $\ell_{*}$ given by

$\ell_{*}([k])=\mu_{*}^{k}+\sum_{j=1}^{k}\sum_{i=j}^{\infty}a_{i}\mu_{*}^{i+k+1-2j};$

compare with Eq. (2). For every $k\geqslant 0$, the corresponding series are
convergent because ${\boldsymbol{a}}$ is bounded and $|\mu_{*}|<1$.

In the finite-dimensional case, every eigenvalue of an operator
${\boldsymbol{A}}$ may trigger corresponding exponential growth in the image
of ${\boldsymbol{A}}^{n}$. A similar effect can be observed here. Since all of
our operators here are quasi-compact, they all admit finitely many eigenvalues
outside the essential spectrum, which means the expansion
$\\#_{\boldsymbol{a}}(n)$ contains finitely many (exponential) terms before
the Catalan-like term; see Remarks 2.2 and 3.3.

In particular, our computations show that

$\\#_{\boldsymbol{a}}(n)-\frac{5}{8}\left(\frac{17}{4}\right)^{n}\;\in\;\frac{1}{4}\left(-\frac{5}{2}\right)^{n}+o\left(\left(\frac{5}{2}\right)^{n}\right)$

and the difference shows Catalan-like growth rate of
$\dfrac{2^{n}}{n^{\nicefrac{{3}}{{2}}}}$, see Figure 2.

Figure 2. For the sequence ${\boldsymbol{a}}=(1,9,9,9,\ldots)$, the plot shows
the ratio
$\frac{\\#_{\boldsymbol{a}}(n)-\frac{5}{8}\left(\frac{17}{4}\right)^{n}-\frac{1}{4}\left(-\frac{5}{2}\right)^{n}}{\nicefrac{{2^{n}}}{{n^{\nicefrac{{3}}{{2}}}}}}.$
.

Overall, we conjecture that, for ${\boldsymbol{a}}=(1,9,9,9,\ldots)$, we have

$\\#_{\boldsymbol{a}}(n)\;\in\;\frac{5}{8}\left(\frac{17}{4}\right)^{n}+\frac{1}{4}\left(-\frac{5}{2}\right)^{n}+\Theta\left(\frac{2^{n}}{n^{\nicefrac{{3}}{{2}}}}\right).$
(7)

######  Example 6.3.

For the next example, we consider the sequence
${\boldsymbol{a}}=(3,1,1,1,\ldots)$. This sequence was studied by Mañibo,
Rust, and Walton in [15, Ex. 6.14]. This sequence gives rise to alternative
values $\mu_{*}$ and $\lambda_{*}$ as well, but $\lambda_{*}$ is not an
eigenvalue of $\boldsymbol{A}$ and does not appear in the counting function
$\\#_{\boldsymbol{a}}(n)$.

As before, we use Eq. (4) to write

$\frac{1}{\mu}=3+\mu+\mu^{2}+\mu^{3}+\cdots=3+\frac{\mu}{1-\mu}.$

This transforms into the quadratic equation $2\mu^{2}-4\mu+1=0$ with two
solutions $\mu=1-\nicefrac{{1}}{{\sqrt{2}}}$ and
$\mu_{*}=1+\nicefrac{{1}}{{\sqrt{2}}}$. The former defines
$\lambda=3+\nicefrac{{1}}{{\sqrt{2}}}$, the inflation factor also obtained in
[15, Ex. 6.14].

Using a similar approach to the lengths, we find that the average length of
tiles is $\frac{12-4\sqrt{2}}{7}$. Thus,

$\\#_{\boldsymbol{a}}(n)\;\in\;\frac{7}{12-4\sqrt{2}}\left(3+\frac{1}{\sqrt{2}}\right)^{n}+o\left(\left(3+\frac{1}{\sqrt{2}}\right)^{n}\right).$

More precisely, our experiments show that, for the sequence
${\boldsymbol{a}}=(3,1,1,1,\ldots)$,

$\\#_{\boldsymbol{a}}(n)\;\in\;\frac{7}{12-4\sqrt{2}}\left(3+\frac{1}{\sqrt{2}}\right)^{n}+\Theta\left(\frac{2^{n}}{n^{\nicefrac{{3}}{{2}}}}\right),$
(8)

see Figure 3.

Figure 3. For the sequence ${\boldsymbol{a}}=(3,1,1,1,\ldots)$, the plot shows
the ratio
$\frac{\\#_{\boldsymbol{a}}(n)-\frac{7}{12-4\sqrt{2}}\left(3+\frac{1}{\sqrt{2}}\right)^{n}}{\nicefrac{{2^{n}}}{{n^{\nicefrac{{3}}{{2}}}}}}.$
.

Note that
$\lambda_{*}=\mu_{*}+\nicefrac{{1}}{{\mu_{*}}}=3-\nicefrac{{1}}{{\sqrt{2}}}>2$
does not show up in the asymptotics of $\\#_{\boldsymbol{a}}(n)$ because it is
not an eigenvalue for $\boldsymbol{A}$. From Remark 3.3, if $\lambda_{\ast}$
is in the spectrum of the substitution operator, and $|\lambda_{\ast}|>2$,
then $\lambda_{\ast}$ must be an eigenvalue, with eigenvector of the form
given in Proposition 2.3. However, if $|\mu_{\ast}|>1$, the corresponding
eigenvector $\ell_{\ast}([k])$ is unbounded, which means $\lambda_{\ast}$
cannot be an eigenvalue. Since $\mu_{*}$ does not yield an eigenvector, we
call $\lambda_{*}$ a fake eigenvalue.

The fake eigenvalue $\lambda_{*}$ will appear in the general solution of the
equation in Lemma 4.7 treated as a linear recurrence. Indeed, the polynomial
$R(\boldsymbol{A})$ there contains the minimal polynomial of $\lambda$ as a
multiple. Since $\lambda$ and $\lambda_{*}$ are algebraically conjugate, they
both will be roots of the corresponding characteristic polynomial. However,
the initial conditions will eliminate the term $\lambda_{*}^{n}$ from the
general solution, consistent with $\lambda_{\ast}$ not being in the spectrum
of $M$.

We also experimented with a slightly modified sequence
${\boldsymbol{a}}=(a_{0},1,1,1,\ldots)$ with $a_{0}=4,5,6$ with the same
results. For each $a_{0}$, there is a fake $\lambda_{*}$ which does not
contribute to $\\#_{\boldsymbol{a}}(n)$.

We briefly remark that both examples from Section 5 exhibit similar
properties, namely, both of them additionally have $\mu_{*}=-1-\sqrt{2}$ and
$\lambda_{*}=-2\sqrt{2}$ (which has the same absolute value as
$\lambda=2\sqrt{2}$), but this $\lambda_{*}$ is again fake as it does not give
rise to an eigenvector and does not appear in the corresponding tile counting
function.

######  Example 6.4.

Next, we consider ${\boldsymbol{a}}=(2,4,2,2,2,\ldots)$. The equation for
$\mu$ is

$\frac{1}{\mu}=2+4\mu+2\mu^{2}+2\mu^{3}+\cdots=2\mu+\frac{2}{1-\mu}.$

It transforms into the cubic equation $2\mu^{3}-2\mu^{2}-3\mu+1=0$ or
$(\mu+1)(2\mu^{2}-4\mu+1)=0$. So in addition to
$\mu=1-\nicefrac{{1}}{{\sqrt{2}}}$ and $\mu_{*}=1+\nicefrac{{1}}{{\sqrt{2}}}$
from the previous example, we also have $\mu_{**}=-1$.

Thus, $\lambda=3+\nicefrac{{1}}{{\sqrt{2}}}$ is the same as in the previous
example. The average length of tiles is $4-2\sqrt{2}$. We note that, as
before, $\lambda_{*}=3-\nicefrac{{1}}{{\sqrt{2}}}$ does not contribute to the
counting function $\\#_{\boldsymbol{a}}(n)$.

Additionally, $\lambda_{**}=\mu_{**}+\nicefrac{{1}}{{\mu_{**}}}=-2$ is not an
eigenvalue of $\boldsymbol{A}$, but it affects the behaviour of
$\\#_{{\boldsymbol{a}}}(n)$. In particular, our experiments show that it
alters the power of $n$ in the denominator of the discrepancy and

$\\#_{\boldsymbol{a}}(n)\in\frac{1}{4-2\sqrt{2}}\left(3+\frac{1}{\sqrt{2}}\right)^{n}+\Theta\left(\frac{2^{n}}{n^{\nicefrac{{1}}{{2}}}}\right),$
(9)

see Figure 4.

Note that this is still consistent with Theorem 2.7, with $r_{2}=2$ but now
$\theta(n)=n^{-1/2}$. We conjecture that it is possible to tie this behaviour
to the recurrence from Lemma 4.7 and to the spectral nature of $\lambda$. The
right-hand side there grows at least as
$\nicefrac{{2^{n}}}{{n^{q+\nicefrac{{3}}{{2}}}}}$ with some alternating
behaviour for odd/even $n$, so it is possible that having $-2$ as a root of
characteristic polynomial adds a linear factor to the growth of some
particular solution.

Moreover, $\lambda=-2$ is an _approximate eigenvalue_ of $\boldsymbol{A}$,
i.e., there exists a sequence $\left\\{\boldsymbol{v}^{(n)}\right\\}$ of unit
vectors in $\ell^{1}$ for which
$|\boldsymbol{A}\boldsymbol{v}^{(n)}+2\boldsymbol{v}^{(n)}|\to 0$ as
$n\to\infty$. In this case, one can choose $\boldsymbol{v}^{(n)}$ to be

$\boldsymbol{v}^{(n)}=\frac{1}{n}\left((-1)^{n}n,(-1)^{n-1}(n-1),\ldots,-1,0,0,\ldots\right).$

It is easy to see that every $\boldsymbol{v}^{(n)}$ has unit sup-norm in
$\ell^{1}$. Moreover, one can check that

$\boldsymbol{A}\boldsymbol{v}^{(n)}+2\boldsymbol{v}^{(n)}=\begin{cases}(\frac{3}{n},0,0,\ldots),&n\text{
even},\\\ (-\frac{4}{n},0,0,\ldots),&n\text{ odd},\end{cases}$

from which the required convergence follows. Since $-2$ is an approximate
eigenvalue which is not an eigenvalue, it is part of the _continuous spectrum_
of $\boldsymbol{A}$. A more detailed analysis of these approximate
eigenvectors might yield a better description of the asymptotics.

Figure 4. For the sequence ${\boldsymbol{a}}=(2,4,2,2,\ldots)$, the plot shows
the ratio
$\frac{\\#_{\boldsymbol{a}}(n)-\frac{1}{4-2\sqrt{2}}\left(3+\frac{1}{\sqrt{2}}\right)^{n}}{\nicefrac{{2^{n}}}{{n^{\nicefrac{{3}}{{2}}}}}}.$
Unlike the previous plots this one indicates linear growth, hence an
additional factor $n$. Figure 5. For the sequence
${\boldsymbol{a}}=(1,8,12,12,\ldots)$, the plot shows the expression
$\left(\frac{\\#_{\boldsymbol{a}}(n)-\frac{3}{5}\left(\frac{17}{4}\right)^{n}-\frac{1}{5}(-2)^{n}}{2^{n}}\right)^{-2}.$

######  Example 6.5.

Here, we consider ${\boldsymbol{a}}=(1,8,12,12,12,\ldots)$. The equation
satisfied by $\mu$ reads $4\mu^{3}+7\mu^{2}+2\mu-1=(\mu+1)^{2}(4\mu-1)=0$. So
it has $\mu=\nicefrac{{1}}{{4}}$ as the solution that gives
$\lambda=\nicefrac{{17}}{{4}}$ and $\mu_{*}=-1$ as root of multiplicity $2$.

However, the discrepancy between $\\#_{\boldsymbol{a}}(n)$ and the leading
term grows not as $2^{n}\sqrt{n}$ as one may guess from the previous example
if every repetition of $\mu_{*}=-1$ (or $\lambda_{*}=-2$) brings a factor of
$n$ to the discrepancy.

What is also different from previous examples is that $\lambda_{*}=-2$ is an
eigenvalue with the eigenvector $(1,-3,-3,-3,\ldots)$. Moreover, this
eigenvalue contributes to the tile counting function.

Our computations (see Figure 5) suggest that

$\\#_{\boldsymbol{a}}(n)\in\frac{3}{5}\left(\frac{17}{4}\right)^{n}+\frac{1}{5}(-2)^{n}+\Theta\left(\frac{2^{n}}{n^{\nicefrac{{1}}{{2}}}}\right).$
(10)

We note that the asymptotics of the tile counting function for this example is
considerably more subtle than the rest, and we needed to check the 2000th
iteration of the substitution instead of just the 200th.

######  Example 6.6.

Our last example shows that complex values for $\mu$ may lead to relatively
standard behaviour as well.

For the sequence ${\boldsymbol{a}}=(1,7,15,15,15,\ldots)$, the equation for
$\mu$ has solutions $\mu=\nicefrac{{1}}{{4}}$ and $\mu_{*}=\frac{-1\pm
i\sqrt{5}}{6}$. The inflation factor $\lambda=\nicefrac{{17}}{{4}}$ defines
the leading term of $\\#_{{\boldsymbol{a}}}(n)$ and $\lambda_{*}=\frac{-7\pm
i\cdot 5\sqrt{5}}{6}$ are eigenvalues as well, since $|\mu_{*}|<1$ for both
choices of the sign.

Again, treating the equation in Lemma 4.7 as a linear recurrence, these
$\lambda_{*}$’s should contribute an exponential-times-trigonometric function
to the tile counting function $\\#_{{\boldsymbol{a}}}(n)$; and this is exactly
what our computations show, see Figure 6. A refined expected formula for
$\\#_{{\boldsymbol{a}}}(n)$ with the exact trigonometric factor remains to be
found.

Figure 6. For the sequence ${\boldsymbol{a}}=(1,7,15,15,\ldots)$, the plot
shows the ratio
$\frac{\\#_{\boldsymbol{a}}(n)-\frac{1}{2}\left(\frac{17}{4}\right)^{n}}{\left(\sqrt{\frac{29}{6}}\right)^{n}}.$

## Acknowledgments

The authors want to thank Igor Pak for discussions related to the asymptotics
of Catalan-related sequences and corresponding references. We also would like
to thank Lorenzo Sadun for numerous discussions on discrepancies of
substitutions and Michael Baake for helpful comments on the manuscript. We
also thank two anonymous reviewers for their valuable comments and
suggestions; in particular, one for pointing the connection to one-dimensional
random walks. Finally, we thank Fernando Cordero for discussions on random
walks. A.G. is partially supported by the Alexander von Humboldt Foundation.
N.M. is supported by the German Academic Exchange Service (DAAD) through a
PRIME Fellowship.

## References

  * [1] A.G. Aksoy: The radius of the essential spectrum, J. Math. Anal. Appl. 128 (1987) 101–107.
  * [2] M. Baake, U. Grimm: Aperiodic Order. Vol. 1: A Mathematical Invitation, Cambridge University Press, Cambridge, 2013.
  * [3] M. Baake, U. Grimm, D. Frettlöh, Pinwheel patterns and powder diffraction, Philos. Mag. 87 (2007) 2831–2838, https://arxiv.org/abs/math-ph/0610012.
  * [4] D. Frettlöh, A. Garber: Pisot substitution sequences, one dimensional cut-and-project sets and bounded remainder sets with fractal boundary, _Indag. Math._ 29 (2018), 1114–1130, https://arxiv.org/abs/1711.01498.
  * [5] D. Frettlöh, A. Garber, N. Mañibo: Substitution tilings with transcendental inflation factor, preprint (2022) https://arxiv.org/abs/2208.01327.
  * [6] D. Frettlöh, A. Garber, L. Sadun: Number of bounded distance equivalence classes in hulls of repetitive Delone sets. _Discr. Contin. Dynam. Syst._ 42 (2022) 1403–1414, https://arxiv.org/abs/2101.02514.
  * [7] U. Grimm, X. Deng, Some comments of pinwheel tilings and their diffraction, J. Phys. Conf. Ser. 284 (2011) 012032 (9pp), https://arxiv.org/abs/1102.1750.
  * [8] H. Hennion, L. Hervé:Limit Theorems for Markov Chains and Stochastic Properties of Dynamical Systems by Quasi-compactness, Springer Berlin (2001).
  * [9] A. Haynes, M. Kelly, H. Koivusalo: Constructing bounded remainder sets and cut-and-project sets which are bounded distance to lattices II, _Indag. Math._ 28 (2017) 138-144, https://arxiv.org/abs/1602.00529.
  * [10] M. Kesseböhmer, S. Kombrink: A complex Ruelle–Perron–Frobenius theorem for infinite Markov shifts with applications to renewal theory, Discr. Contin. Dynam. Syst. S 10 (2017) 335–352, https://arxiv.org/abs/1604.08252.
  * [11] A. Khinchin: Über einen Satz der Wahrscheinlichkeitsrechnung, _Fundam. Math._ 6 (1924) 9–-20.
  * [12] D.E. Knuth: _The Art of Computer Programming, Vol. 1: Fundamental Algorithms_ , 3rd ed., Addison Wesley, 1997.
  * [13] A. Kolmogoroff: Über das Gesetz des iterierten Logarithmus, _Mathematische Annalen_ 101 (1929) 126-–135.
  * [14] N. Mañibo, D. Rust, J.J. Walton: Spectral properties of substitutions on compact alphabets, preprint (2021), https://arxiv.org/abs/2108.01762.
  * [15] N. Mañibo, D. Rust, J.J. Walton: Substitutions on compact alphabets, preprint (2022), https://arxiv.org/abs/2204.07516.
  * [16] OEIS Foundation Inc. (2022), The Catalan numbers, Entry A000108 in The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A000108.
  * [17] I. Pak: History of Catalan numbers. Appendix to R. Stanley, “Catalan Numbers”, Cambridge Univ. Press, 2015, 177-189, https://arxiv.org/abs/1408.5711.
  * [18] M. Pollicott: Meromorphic extensions of generalized zeta functions, Invent. Math. 85 (1986) 147–164.
  * [19] R. Rado: Factorization of even graphs, _Quart. J. Math. Oxford_ 20 (1949) 95–104.
  * [20] D. Ruelle: Locating resonances for Axiom A dynamical systems, J. Stat. Phys. 44 (1986) 281–292.
  * [21] Y. Smilansky, Y. Solomon: A dichotomy for bounded displacement equivalence of Delone sets, _Ergodic Th. Dynam. Syst._ 42 (2022) 2693-–2710, https://arxiv.org/abs/2011.00106.
  * [22] Y. Solomon: A simple condition for bounded displacement, _J. Math. Anal. Appl._ 414 (2014) 134–148, https://arxiv.org/abs/1111.1690.
  * [23] R.P. Stanley, S. Fomin: _Enumerative Combinatorics, Vol. 2_ , Cambridge University Press, Cambridge, 1999.
  * [24] R.P. Stanley: _Catalan Numbers_ , Cambridge University Press, New York, 2015.
  * [25] Wolfram Research, Inc., Mathematica, Version 13.1, Champaign, IL (2022).