Decidability of the isomorphism problem between multidimensional substitutive subshifts

Abstract

An important question in dynamical systems is the classification problem, that is, the ability to distinguish between two isomorphic systems. In this work, we study the topological factors between a family of multidimensional substitutive subshifts generated by morphisms with uniform support. We prove that it is decidable to check whether two minimal aperiodic substitutive subshifts are isomorphic. The strategy followed in this work consists of giving a complete description of the factor maps between these subshifts. Then, we deduce some interesting consequences on coalescence, automorphism groups, and the number of aperiodic symbolic factors of substitutive subshifts. We also prove other combinatorial results on these substitutions, such as the decidability of defining a subshift, the computability of the constant of recognizability, and the conjugacy between substitutions with different supports.

1. Introduction

Isomorphic systems are indistinguishable in terms of their dynamical properties, making classification an important problem in dynamical systems. Nevertheless, finding an isomorphism (or conjugation) between two dynamical systems has proven to be highly challenging. We recall that an isomorphism between two symbolic systems $(X,S,\mathbb {Z}^{d})$ and $(Y,S,\mathbb {Z}^{d})$ is a continuous and bijective map $\phi :(X,S,\mathbb {Z}^{d})\to (Y,S,\mathbb {Z}^{d})$ commuting with the action, that is, for any $\boldsymbol {n}\in \mathbb {Z}^{d}$ , $\phi \circ S^{\boldsymbol {n}}=S^{\boldsymbol {n}}\circ \phi $ . If the map $\phi $ is only surjective, it is called a factor map.

One classic approach to address the classification problem involves identifying invariants, which are properties shared by isomorphic systems and are easily determinable. However, in some cases, the existing invariants may not suffice for this purpose. Additionally, the topological factors of a topological dynamical system are rarely used explicitly to unravel the structure of a particular dynamical system. Nonetheless, they contain valuable information for certain aspects and can be employed for concrete computations or the study of specific structures, such as in spectral theory.

We are also concerned with the decidability of certain properties. A property is said to be decidable if an algorithm exists that allows one to verify whether the property is satisfied or not. In this article, our focus lies on the decidability of the classification problem within the family of multidimensional substitutive subshifts.

One-dimensional substitutive subshifts have been extensively studied for several decades, ever since they were introduced by Gottschalk in [27]. They represent the simplest non-trivial zero-entropy symbolic systems and are generated in a highly deterministic manner. This simplicity has led to their presence in various fields of mathematics, computer science, and physics, such as combinatorics of words, number theory, dynamics of aperiodic tilings, quasi-crystals, and more (see, for example, [1, 2, 35, 36]). However, their deep understanding took several decades, with significant contributions made by Cobham [10] (who identified them as so-called automatic sequences from a computational perspective), Queffélec and others [14, 39, 42] (in terms of their spectral properties), Mossé [34] (focused on recognizability, which is a sort of invertibility of substitutions), Durand, Host, and Skau [18] (who classified their topological factor systems), and Host and Parreau among several others [12, 13, 15, 30, 33, 41] (classification of their automorphism groups). We refer to [23, 39] for extensive bibliographies on the (earlier developments of the) subject. Many of the aspects mentioned above remain largely unexplored in the context of multidimensional substitutive systems.

In the multidimensional setting, substitutive subshifts find their motivation in physical phenomena, particularly through the discovery of the aperiodic structure of quasi-crystals, modeled by the Penrose tiling [37]. In these models, symmetries play a fundamental role and are described using finite data. Numerous articles have been dedicated to the study of these tilings (see [3] for an extensive bibliography on aperiodic order). Substitutive systems have then emerged as valuable mathematical models within this research direction. Our focus in this article is on substitutions with uniform support, where the shape of any pattern defined by the substitution remains the same (see [8] for basic properties on this topic, where we follow the same notation). Within this class of substitutive subshifts, we prove that assuming they have the same combinatorial structure, it is decidable whether a factor map exists between two aperiodic substitutive subshifts.

Theorem A. Let $\zeta _{1},\zeta _{2}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L. It is decidable to know whether there exists a factor map $\phi :(X_{\zeta _{1}},S,\mathbb {Z}^{d})\to (X_{\zeta _{2}},S,\mathbb {Z}^{d})$ .

The strategy followed in this article involves providing a complete description of the factor maps between substitutive subshifts. This approach draws inspiration from a series of works on automorphism groups of symbolic systems, which we proceed to describe. The study of factors and conjugacies between dynamical systems is a classical problem, primarily concerning their algebraic and dynamical properties in relation to those of the system $(X, T, \mathbb {Z}^{d})$ . Automorphisms, which are self-conjugacies of a particular system, can be algebraically defined as elements of the centralizer of the action group $\langle T\rangle $ , considered as a subgroup of all homeomorphisms $ {\mathrm {Homeo}}(X)$ from X to itself. Symbolic systems already exhibit significant rigidity properties regarding factor maps and automorphisms. For instance, the famous Curtis–Hedlund–Lyndon theorem [29] establishes that any factor map between subshifts is a sliding block code, implying that the automorphism group is countable and discrete. Initially studied for subshifts of finite type [29], these automorphism groups were shown to be infinitely generated and containing various groups, including all finite groups, the free group on two generators, the direct sum of a countable number of copies of $\mathbb {Z}$ , and any countable collection of finite groups. The existence of a conjugacy between two subshifts of finite type is known to be equivalent to the notion of strong shift equivalence for matrices over $\mathbb {Z}^{+}$ [47], which is not known to be decidable [31].

However, within the rich family of substitutive subshifts, factor maps exhibit strong rigidity properties, as proven by Host and Parreau in [30]. They provided a complete description of factor maps between subshifts arising from certain constant-length substitutions, proving that any measurable factor map induces a continuous one. As a consequence, the automorphism group is virtually generated by the shift action, meaning that there exists a finite set of automorphisms such that any automorphism can be expressed as the composition of an element from this finite set and a power of the shift. Moreover, any finite group can be realized as a quotient group $ {\mathrm {Aut}}(X,S,\mathbb {Z})/\langle S\rangle $ for these subshifts, as proven by Lemańczyk and Mentzen in [33]. The proof by Host and Parreau is based on the following fact: there exists a bound (in this case, $r=2$ ) such that any factor map between these substitutive subshifts is the composition of a sliding block code with a radius less than r and a power of the shift map. Using the self-induced properties of substitutive subshifts, Salo and Törmä provided in [41] a renormalization process for factor maps between two minimal substitutive subshifts of constant length and for Pisot substitutions, extending the description obtained in [30] within a topological framework. More recently, Durand and Leroy [20] showed the decidability of the factorization problem between two minimal substitutive subshifts, extending the results of Salo and Törmä, giving a computable upper bound R such that every factor map between minimal substitutive subshifts is the composition of a power of the shift map with a factor map having a radius less than R. The decidability of the factorization problem in the constant-length case had previously been proved by Fagnot in [22] using the first-order logic framework of Presburger arithmetic, without assuming minimality. In [8], an analogous result to that of Host and Parreau for the multidimensional framework was established. In this article, we further extend the findings in [8] to the whole class of aperiodic minimal multidimensional constant-shape substitutive subshifts.

Theorem B. Let $\zeta _{1},\zeta _{2}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix. Then, there exists a computable constant R such that every factor map between $(X_{\zeta _{1}},S,\mathbb {Z}^{d})$ and $(X_{\zeta _{2}},S,\mathbb {Z}^{d})$ is the composition of a shift map with a factor map of radius less than R.

The constant R of the previous theorem depends on the constant of recognizability of the image substitution $\zeta _{2}$ . In [8], it was already established that aperiodic primitive constant-shape substitutions are recognizable. In this article, we prove that this constant is computable.

Theorem C. Let $\zeta $ be an aperiodic primitive constant-shape substitution with expansion matrix L and support F. There is a computable upper bound for the constant of recognizability of $\zeta $ . This bound can be expressed only by the cardinality of the alphabet $|\mathcal {A}|$ , the expansion matrix L, the support F, and the dimension d.

This result is an analog of the one proved by Durand and Leroy in [19] for the one-dimensional case.

This article is organized as follows. The basic definitions and background are introduced in §2. Section 3 is devoted to the study of the supports of a constant-shape substitution. We prove the decidability of whether this sequence is Følner (Theorem 3.2), useful to define the substitutive subshift. Then, we use this proof to get a bound on their complexity function (Proposition 3.6). In §4, we deal with the conjugacy problem between two aperiodic primitive constant-shape substitutions with the same expansion matrix but different support. We prove that for any pair of different supports $F_{1}, G_{1}$ of an expansion matrix and any constant-shape substitution with support $F_{1}$ , there exists a constant-shape substitution with support $G_{1}$ such that the two substitutive subshifts are topologically conjugate (Theorem 4.1). This answers a question raised in [24], where a similar result was shown for the one-dimensional case. Section 5 is devoted to the computability of the constant of recognizability of constant-shape substitutions. To do this, we study the computability of the repetitivity function for substitutive subshifts (Lemma 5.4). Finally, in §6, we characterize the factor maps between aperiodic primitive substitutive subshifts sharing the expansion matrix (Theorem 6.2). Then, we deduce the coalescence of substitutive subshifts (Proposition 6.4), meaning any endomorphism between the substitutive subshift and itself is invertible. We also prove that the automorphism group of substitutive subshifts is virtually generated by the shift action (Proposition 6.5). Additionally, we use Theorem 6.2 to conclude the decidability of the factorization problem between substitutive subshifts having the same expansion matrix (Theorem 6.6). Thanks to the coalescence of substitutive subshifts, we also deduce the decidability of the isomorphism problem (Corollary 6.9). We finish this section proving that substitutive subshifts have finitely many aperiodic symbolic factors, up to conjugacy (Lemma 6.12). Thanks to Theorem 6.2, we can provide a list containing these factors.

2. Definitions and basic properties

2.1. Basic definitions and notation

2.1.1. Notation

Throughout this article, we will denote by $\boldsymbol {n}=(n_{1},\ldots ,n_{d})$ the elements of $\mathbb {Z}^{d}$ and by $\boldsymbol {x}=(x_{1},\ldots ,x_{d})$ the elements of $\mathbb {R}^{d}$ . If $F\subseteq \mathbb {Z}^{d}$ is a finite set, it will be denoted by $F\Subset \mathbb {Z}^{d}$ , and we use the notation $\Vert F\Vert =\max \nolimits _{\boldsymbol {n}\in F}\Vert \boldsymbol {n}\Vert $ , where $\Vert \cdot \Vert $ is the standard Euclidean norm of $\mathbb {R}^{d}$ . If $L\in \mathcal {M}(d,\mathbb {R})$ is a $d\times d$ -matrix, we denote $\Vert L\Vert =\max \nolimits _{\boldsymbol {x}\in \mathbb {R}\setminus \{\boldsymbol {0}\}} \Vert L(\boldsymbol { x})\Vert /\Vert \boldsymbol {x}\Vert $ as the matrix norm of L.

A sequence of finite sets $(F_{n})_{n>0}\subseteq \mathbb {Z}^{d}$ is said to be Følner if for any $\boldsymbol {n}\in \mathbb {Z}^{d}$

$$ \begin{align*} \lim\limits_{n\to \infty}\dfrac{|F_{n}\Delta (\boldsymbol{n}+F_{n})|}{|F_{n}|}=0, \end{align*} $$

where $|X|$ stands for the cardinality of the set X. (In the literature, especially in group theory, it is common to also ask that the union of the sequence of sets $(F_{n})_{n>0}$ is equal to $\mathbb {Z}^{d}$ for a sequence to be Følner, but we will not use it in this article.) For any pair of subsets $E, F\subseteq \mathbb {Z}^{d}$ , we denote $F^{\circ E}$ as the set of all elements $\boldsymbol {f}\in F$ such that $\boldsymbol {f}+E\subseteq F$ , that is,

$$ \begin{align*} F^{\circ E}=\{\boldsymbol{f}\in F\colon \boldsymbol{f}+E\subseteq F\}. \end{align*} $$

In the case where E is a discrete ball centered at the origin, meaning $E\hspace{-1pt}=\hspace{-1pt}[B(\boldsymbol {0},r)\hspace{-1pt}\cap\hspace{-1pt} \mathbb {Z}^{d}]$ for some $r>0$ , we will denote $F^{\circ [B(\boldsymbol {0}, r) \cap \mathbb {Z}^{d}]}$ simply by $F^{\circ r}$ . Note that the Følner assumption implies that for any $E\Subset \mathbb {Z}^{d}$ ,

(1) $$ \begin{align} \lim\limits_{n\to \infty}\dfrac{|F_{n}^{\circ E}\Delta F_{n}|}{|F_{n}|}=1. \end{align} $$

2.2. Symbolic dynamics

Let $\mathcal {A}$ be a finite alphabet and let $d\geq 1$ be an integer. We define a topology on $\mathcal {A}^{\mathbb {Z}^{d}}$ by endowing $\mathcal {A}$ with the discrete topology and considering on $\mathcal {A}^{\mathbb {Z}^{d}}$ the product topology, generated by cylinders. Since $\mathcal {A}$ is finite, $\mathcal {A}^{\mathbb {Z}^{d}}$ is a metrizable compact space. The additive group $\mathbb {Z}^{d}$ acts on this space by translations (or shifts), defined for every $\boldsymbol {n}\in \mathbb {Z}^{d}$ by

$$ \begin{align*} S^{\boldsymbol{n}}(x)_{\boldsymbol{k}}=x_{\boldsymbol{n}+\boldsymbol{k}}, x\in \mathcal{A}^{\mathbb{Z}^{d}}, \boldsymbol{k}\in \mathbb{Z}^{d}. \end{align*} $$

The $\mathbb {Z}^{d}$ -action $(\mathcal {A}^{\mathbb {Z}^{d}},S,\mathbb {Z}^{d})$ is called the full-shift.

Let $P\subseteq \mathbb {Z}^{d}$ be a finite set. A pattern is an element $\texttt {p}\in \mathcal {A}^{P}$ . We say that P is the support of $\texttt {p}$ , denoted $P= {\mathrm {supp}}(\texttt {p})$ . We say that a pattern $\texttt {p}$ occurs in $x\in \mathcal {A}^{\mathbb {Z}^{d}}$ if there exists $\boldsymbol {n}\in \mathbb {Z}^{d}$ such that $\texttt {p}=x|_{\boldsymbol {n}+P}$ (identifying P with $\boldsymbol {n}+P$ by translation). In this case, we denote it as $\texttt {p}\sqsubseteq x$ , and we call such $\boldsymbol {n}$ an occurrence in x of $\texttt {p}$ .

A subshift $(X,S,\mathbb {Z}^{d})$ is given by a closed subset $X\subseteq \mathcal {A}^{\mathbb {Z}^{d}}$ that is invariant under the $\mathbb {Z}^{d}$ -action. In this article, even if the alphabet changes, S will always denote the shift map, and we usually say that X itself is a subshift. A subshift can also be defined by its language. For $P\Subset \mathbb {Z}^{d}$ , we denote

$$ \begin{align*}\mathcal{L}_{P}(X)=\{\texttt{p}\in \mathcal{A}^{P}: \text{ there exists } x \in X,\ \texttt{p}\sqsubseteq x\}.\end{align*} $$

We define the language of a subshift X by

$$ \begin{align*} \mathcal{L}(X)=\bigcup\limits_{P\Subset \mathbb{Z}^{d}}\mathcal{L}_{P}(X). \end{align*} $$

We say that the subshift $(X,S,\mathbb {Z}^{d})$ is minimal if it does not contain proper non-empty subshifts. The subshift is aperiodic if there are no non-trivial periods; that is, if $S^{\boldsymbol {p}}x=x$ for some $\boldsymbol {p}\in \mathbb {Z}^{d}$ and $x\in X$ , then $\boldsymbol {p}=0$ .

Let $\mathcal {B}$ be a finite alphabet and consider a subshift $Y\subseteq \mathcal {B}^{\mathbb {Z}^{d}}$ . A map $\phi :(X,S,\mathbb {Z}^{d}) \to (Y,S,\mathbb {Z}^{d})$ is a factor map if it is continuous, surjective, and commutes with the actions, that is, $\phi \circ S^{\boldsymbol {n}} = S^{\boldsymbol {n}} \circ \phi $ for all $\boldsymbol {n} \in \mathbb {Z}^d$ . In this case, we say that $(Y,S,\mathbb {Z}^{d})$ is a factor of $(X,S,\mathbb {Z}^{d})$ . If $\phi $ is also injective, we say it is a conjugacy (or an isomorphism). When $\phi :(X,S,\mathbb {Z}^{d})\to (Y,S,\mathbb {Z}^{d})$ is a factor map, there exists a finite subset $P\Subset \mathbb {Z}^{d}$ and a P-block map $\Phi : \mathcal {L}_{P}(X)\to \mathcal {B}$ such that for any $\boldsymbol { n}\in \mathbb {Z}^{d}$ and $x\in X$ , $\phi (x)_{\boldsymbol {n}}= \Phi (x|_{\boldsymbol {n}+ P})$ . This is known as the Curtis–Hedlund–Lyndon theorem [29]. We call such P the support of $\Phi $ and a support of $\phi $ . Observe that if $\phi $ is induced by $\Phi $ , we can define another block map $\Phi '$ also inducing $\phi $ and whose support is a discrete ball of the form $[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]$ for $r\in \mathbb {N}$ . We define the radius of $\phi $ (and denote it by $r(\phi )$ ) as the infimum of $r\in \mathbb {N}$ such that $\phi $ is induced by a block map with support $[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]$ .

2.3. Multidimensional constant-shape substitutions

We recall some basic definitions and results about multidimensional substitutive subshifts of constant shape that will be used throughout this article. We refer to [8] for basic properties on this topic, where we follow the same notation (see also [25] for spectral properties of these subshifts). Let $L\in \mathcal {M}(d,\mathbb {Z})$ be an expansion integer matrix, that is, there exists $\unicode{x3bb}>1$ such that for every $\boldsymbol {x}\in \mathbb {R}^{d}\setminus \{0\}$ , we have that $\Vert L(\boldsymbol {x}) \Vert>\unicode{x3bb} \Vert \boldsymbol {x}\Vert $ . Let F be a fundamental domain of $L(\mathbb {Z}^{d})$ in $\mathbb {Z}^{d}$ , meaning a set of representative classes of $\mathbb {Z}^{d}/L(\mathbb {Z}^{d})$ (with $\boldsymbol {0}\in F$ ), and let $\mathcal {A}$ be a finite alphabet. A multidimensional constant-shape substitution is a map $\zeta :\mathcal {A}\to \mathcal {A}^{F}$ . The set F is called the support of the substitution. The following shows an example of a constant-shape substitution.

Example 2.1. (Triangular Thue–Morse substitution)

The triangular Thue–Morse substitution is defined with $L=2 {\mathrm {id}}_{\mathbb {R}^{2}}$ , $F=\{(0,0),(1,0),(0,1),(-1,-1)\}$ , and $\mathcal {A}=\{a,b\}$ as

$$ \begin{align*}\begin{array}{cccccccccccc} & & & & b & & & & & & a & \\ \sigma_{\Delta TM}: & a & \mapsto & & a & b, & & b & \mapsto & & b & a. \\ & & & a & & & & & & b & & \\ \end{array}\end{align*} $$

In the literature, constant-shape substitutions with a positive diagonal expansion matrix $L= {\mathrm {diag}}(l_{i})_{i=1,\ldots ,d}$ and support equal to the standard d-dimensional parallelepiped are called block substitutions. These substitutions have a characteristic block structure defined by the shape of $F_{1}$ . Moreover, when $L=p {\mathrm {id}}_{\mathbb {R}^{2}}$ is equal to some positive multiple of the identity and the support is equal to , we use the term square substitution to describe such cases.

Given a substitution $\zeta $ , we let $L_{\zeta }$ denote its expansion matrix and $F_{1}^{\zeta }$ its support. For any $n>0$ , we define the nth iteration of the substitution $\zeta ^{n}:\mathcal {A}\to \mathcal {A}^{F_{n}^{\zeta }}$ by induction: $\zeta ^{n+1}=\zeta \circ \zeta ^{n}$ , where the supports of these substitutions satisfy the recurrence

(2) $$ \begin{align} F_{n+1}^{\zeta}=L_\zeta(F_{n}^{\zeta})+F_{1}^{\zeta}\quad \text{for all } n\geq 1. \end{align} $$

Observe that we trivially have $L_{\zeta ^n} = L_\zeta ^n$ .

The language of a substitution is the set of all patterns that appear in $\zeta ^{n}(a)$ for some $n>0$ , $a\in \mathcal {A}$ , that is,

$$ \begin{align*}\mathcal{L}_{\zeta}=\{\texttt{p}\colon \texttt{p}\sqsubseteq \zeta^{n}(a)\ \text{for some }n>0,\ a\in \mathcal{A}\}.\end{align*} $$

For such a language to define a subshift, we need that the sets $F_n^\zeta $ contain arbitrarily large balls for n large enough, that is, for any $r>0$ , there exists $n>0$ such that $(F_{n}^{\zeta })^{\circ r}\neq \emptyset $ . This condition is ensured by the Følner property. Moreover, the Følner assumption on the sequence of fundamental domains $(F_{n})_{n>0}$ is necessary to ensure that the subshift is uniquely ergodic, following the proof given in [32] for substitutive Delone sets. We prove in the next section that the Følner property is actually equivalent to the existence of arbitrarily large balls in the sequence of supports. We also show that whether a sequence $(F_n)_{n>0}$ satisfies this property is decidable (see Theorem 3.2).

Example 2.2. (Iterations of a constant-shape substitution)

The first three iterations of the substitution $\sigma _{\Delta TM}$ illustrated in Example 2.1.

We define the subshift $X_{\zeta }$ associated with the substitution $\zeta $ as the set of all sequences $x\in \mathcal {A}^{\mathbb {Z}^{d}}$ such that every pattern occurring in x is in $\mathcal {L}_{\zeta }$ . We call this subshift a substitutive subshift.

A substitution $\zeta $ is called primitive if there exists a positive integer $n>0$ , such that, for every $a,b\in \mathcal {A}$ , b occurs in $\zeta ^{n}(a)$ . Each substitution $\zeta $ can be naturally associated with an incidence matrix denoted as $M_{\zeta }$ . For any $a,b\in \mathcal {A}$ , as $(M_{\zeta })_{a,b}$ is defined as ${|\{\boldsymbol {f}\in F_{1}^{\zeta }\colon \zeta (a)_{\boldsymbol {f}} =b\}|}$ , that is, it is equal to the number of occurrences of b in the pattern $\zeta (a)$ , the substitution $\zeta $ is primitive if and only if its incidence matrix is primitive. A matrix is primitive when it has a power with strictly positive coefficients.

If $\zeta $ is a primitive constant-shape substitution, the existence of periodic points is well known, that is, there exists at least one point $x_{0}\in X_{\zeta }$ such that $\zeta ^{p}(x_{0})=x_{0}$ for some $p>0$ . In the primitive case, the subshift is preserved by replacing the substitution with a power of it, meaning $X_{\zeta ^{n}}$ is equal to $X_{\zeta }$ for any $n>0$ . Thus, we may assume that the substitution possesses at least one fixed point. To avoid some problems, we only keep in the alphabet the letters that appear in the fixed points. We recall that in this case, the substitutive subshift is minimal if and only if the substitution is primitive (see [39]).

As in the one-dimensional case, the supports do not need to cover all the space. Nevertheless, up to adding a finite set and taking its images under powers of the expansion map L, they cover the space. This property is explained in the following proposition. It is similar to the notion of remainder in numeration theory and will be technically useful.

Proposition 2.3. [8, Proposition 2.10]

Let $L\in \mathcal {M}(d,\mathbb {Z})$ be an expansion matrix and $F_{1}$ be a fundamental domain of $L(\mathbb {Z}^{d})$ in $\mathbb {Z}^{d}$ (containing $\boldsymbol {0}$ ). Then, the set $K_{L,F_{1}}=\bigcup \nolimits _{m>0}(( {\mathrm {id}} -L^{m})^{-1}(F_{m})\cap \mathbb {Z}^{d})$ is finite and satisfies

$$ \begin{align*}\bigcup\limits_{n\geq 0} L^{n}(K_{L,F_{1}})+F_{n}=\mathbb{Z}^{d},\end{align*} $$

where $F_{0}^{\zeta }=\{\boldsymbol {0}\}$ .

It is straightforward to check that for any block substitution, the set $K_{L,F_{1}}$ is equal to . If $\zeta $ is a constant-shape substitution, we denote $K_{\zeta }=K_{L_{\zeta },F_{1}^{\zeta }}$ . The set $K_{\zeta }$ controls, in some way, the number of periodic points that a constant-shape substitution has. More specifically, it can be proved that a primitive constant-shape substitution has at most $|\mathcal {L}_{K_{\zeta }}(K_{\zeta })| \zeta $ -periodic points.

Remark 2.4. Observing that the sets $\bigcup \nolimits _{m =1}^n(( {\mathrm {id}} -L^{m})^{-1}(F_{m})\cap \mathbb {Z}^{d})$ , $n \geq 1$ , are nested, Proposition 2.3 implies that $K_{L,F_{1}}$ is equal to $\bigcup \nolimits _{m=1}^j(( {\mathrm {id}} -L^{m})^{-1}(F_{m})\cap \mathbb {Z}^{d})$ for some $j>0$ . Therefore, whenever $\zeta $ is primitive, up to replacing $\zeta $ by a power of itself, we may assume that $K_\zeta $ is equal to $( {\mathrm {id}} -L_{\zeta })^{-1}(F_{1}) \cap \mathbb {Z}^d$ . In the latter case, it is straightforward to prove that $\Vert K_{L,F_{1}}\Vert \leq \Vert L^{-1}(F_{1})\Vert /(1-\Vert L^{-1}\Vert )$ .

For the triangular Thue–Morse substitution, the set $K_{\Delta TM}$ is equal to $\{(-1,0),(0,0), (0,-1),(1,1)\}$ .

The proof of Proposition 2.3 is inspired by the Euclidean division algorithm, which was used to obtain finite sets satisfying particular properties as shown in the following result that we will use in the rest of this article.

Proposition 2.5. [8, Proposition 2.12]

Set $A\Subset \mathbb {Z}^{d}$ containing $\boldsymbol {0}\in \mathbb {Z}^{d}$ and let $F\Subset \mathbb {Z}^{d}$ containing a fundamental domain $F_{1}$ of an integer expansion matrix L. Then, there exists a (computable) finite subset $C \subseteq \mathbb {Z}^{d}$ containing $\mathbf {0}$ and such that we have the following.

1. (1) $A+F \subseteq C+A+F\subseteq L(C)+F_{1}$ .

2. (2) More generally, for any $n\geq 0$ :

   • • $L^{n}(C+A+F)+F_{n}\subseteq L^{n+1}(C)+F_{n+1}$ ;

   • • $C+\sum \nolimits _{i=0}^{n}L^{i}(A+F)\subseteq L^{n+1}(C)+F_{n+1}$ .

3. (3) The sequence of sets $(L^{n}(C)+F_{n})_{n\geq 0}$ is nested.

4. (4) $\Vert C\Vert \leq (\Vert L^{-1}(A+F)\Vert +\Vert L^{-1}(F_{1})\Vert )/(1-\Vert L^{-1}\Vert )$ .

Proof. We define the sequence $(C_n)_{n \geq 0}$ of finite sets by $C_0 = \{\mathbf {0}\}$ and, for every $n \geq 0$ ,

$$ \begin{align*} C_{n+1} = [L^{-1}(C_n+A+F-F_1)\cap \mathbb{Z}^{d}]. \end{align*} $$

One easily checks by induction that $C_n \subseteq C_{n+1}$ for all $n\geq 0$ and a quick computation shows that

$$ \begin{align*} \| C_n\| \leq \frac{\Vert L^{-1}(A+F)\Vert+\Vert L^{-1}(F_{1}) \Vert}{1-\Vert L^{-1}\Vert }. \end{align*} $$

As a consequence, the sequence $(C_n)_{n \geq 0}$ stabilizes and we set $C = C_N$ , where N is such that $C_n = C_N$ for every $n \geq N$ . This set C is obviously computable.

Let us now check that the set C satisfies all items. The set C contains $\mathbf {0}$ by construction, which directly implies that $A+F \subseteq C+A+F$ . If $\boldsymbol {n} \in C+A+F$ , then $\boldsymbol {n}$ belongs to $C_n +A + F$ for some $n\in \mathbb {N}$ . We can thus write $\boldsymbol {n} = \boldsymbol {n}' = \boldsymbol {a} + \boldsymbol {f}$ as well as $\boldsymbol {n} = L(\boldsymbol {m}) + \boldsymbol {f}'$ , for some $\boldsymbol {n}' \in B_n, \boldsymbol {a} \in A, \boldsymbol {f} \in F$ , and $\boldsymbol {f}' \in F_1$ . We deduce that $L(\boldsymbol {m}) \in C_n + A + F - F_1$ , and hence $\boldsymbol {m} \in C$ . Item (2) follows by induction and implies item (3), as $\mathbf {0} \in A \cap F$ .

Remark 2.6. Note that if we change the pair $(L,F_{1})$ by $(L^{n},F_{n})$ for any $n\geq 1$ , then the set C given by Proposition 2.5 is the same for fixed A and F. Using the notion of digit tile defined in [8, §2.7], we note that $\Vert L^{-n}(F_{n})\Vert \xrightarrow [n\to \infty ]\ \Vert T_{(L,F_{1})}\Vert $ . Hence, the sequence $(\Vert L^{-n}(F_{n})\Vert /(1-\Vert L^{-n}\Vert ))_{n\geq 1}$ is uniformly bounded. Note that, in the block case, these quantities are bounded by $\sqrt {d}$ , where d is the dimension of the substitution.

From now on, we denote $C_{L,F_{1}}$ to the set given by Remark 2.6 using $A=\{\boldsymbol {0}\}$ and $F=F_{1}+F_{1}$ . By [8, Remark 2.13(2)], we have that for any $n\in \mathbb {N}$ , $C_{L,F_{1}}+F_{n}+F_{n}\subseteq L^{n}(C_{L,F_{1}})+F_{n}$ . Note that, in the block case, the set $C_{L,F_{1}}$ is equal to .

Every element of $\mathbb {Z}^{d}$ can be expressed in a unique way as $\boldsymbol {p}= L(\boldsymbol {j})+\boldsymbol {f}$ , with $\boldsymbol {j} \in \mathbb {Z}^{d}$ and $\boldsymbol {f}\in F_{1}$ , so we can consider the substitution $\zeta $ as a map from $X_{\zeta }$ to itself given by

$$ \begin{align*}\zeta(x)_{L(\boldsymbol{j})+\boldsymbol{f}}=\zeta(x(\boldsymbol{j}))_{\boldsymbol{f}}.\end{align*} $$

This map is continuous. Moreover, when the substitution is aperiodic and primitive, Proposition 5.7 below ensures that this map is actually a homeomorphism. This property is satisfied, even in the case where the substitution is not injective on letters, that is, when there exist distinct letters $a,b\in \mathcal {A}$ such that $\zeta (a)=\zeta (b)$ . This comes from the notion of recognizability of a substitution (see §5).

Definition 2.7. Let $\zeta $ be a substitution and $x\in X_{\zeta }$ be a fixed point. We say that $\zeta $ is recognizable on x if there exists some constant $R>0$ such that for all $\boldsymbol {i}, \boldsymbol {j}\in \mathbb {Z}^{d}$ ,

$$ \begin{align*}x|_{[B(L_{\zeta}(\boldsymbol{i}),R)\cap \mathbb{Z}^{d}]}=x|_{[B(\boldsymbol{j},R)\cap \mathbb{Z}^{d}]}\, \!{\implies}\!\, (\text{there exists } \boldsymbol{k}\in \mathbb{Z}^{d}) ((\boldsymbol{j}=L_{\zeta}(\boldsymbol{k}))\wedge (x_{\boldsymbol{i}}=x_{\boldsymbol{k}})).\end{align*} $$

The recognizability of a substitution $\zeta $ implies that for every $x\in X_{\zeta }$ , there exist a unique $x'\in X_{\zeta }$ and a unique $\boldsymbol {j} \in F_{1}^{\zeta }$ such that $x=S^{\boldsymbol {j}}\zeta (x')$ . This implies that the set $\zeta (X_{\zeta })$ is a clopen subset of $X_{\zeta }$ , and $\{S^{\boldsymbol {j}}\zeta (X_{\zeta })\colon \ \boldsymbol {j} \in F_{1}^{\zeta }\}$ forms a clopen partition of $X_{\zeta }$ (the proof is classical and similar to the one-dimensional case [39, §5.6]). Any power of a recognizable substitution is also recognizable, so these properties extend to $\zeta ^{n}$ for all $n>0$ . The recognizability property was first proved for any aperiodic primitive substitution by B. Mossé in the one-dimensional case [34], and in the multidimensional case by Solomyak [43] for aperiodic self-affine tilings with an $\mathbb {R}^{d}$ -action. Later, in [8], it was established that the aperiodic symbolic factors of primitive substitutive subshifts also satisfy a recognizability property.

3. Decidability of the Følner property for fundamental domains of an expansion matrix and computability of the language of constant-shape substitutions

Let $L\in \mathcal {M}(d,\mathbb {Z})$ be an expansion matrix and $F_{1}\Subset \mathbb {Z}^{d}$ be a fundamental domain of $L(\mathbb {Z}^{d})$ in $\mathbb {Z}^{d}$ containing $\boldsymbol {0}$ . Define the sequence of fundamental domains of $L^{n}(\mathbb {Z}^{d})$ as in equation (2):

$$ \begin{align*}F_{n+1}=L(F_{n})+F_{1}\quad \text{for all } n\geq 1.\end{align*} $$

We recall that the sequence $(F_{n})_{n\in \mathbb {N}}$ is said to be Følner if for any $\boldsymbol {n}\in \mathbb {Z}^{d}$ ,

$$ \begin{align*}\lim\limits_{n\to\infty}\dfrac{|F_{n}\Delta (\boldsymbol{n}+F_{n})|}{|F_{n}|}=0. \end{align*} $$

As mentioned in the previous section, the Følner property ensures that the sets $F_n$ eventually contain balls of arbitrarily large radius, which then allows us to define a subshift. However, the converse is not true in general, that is, having balls of arbitrarily large radius is not enough to guarantee that the sequence is Følner, since the sets can be sparse at the same time, as the following example shows.

Example 3.1. Consider the sequence of finite sets given by for any $n\in \mathbb {N}$ . Set $r>2$ . Let $n\in \mathbb {N}$ be large enough. We note that

which lets us conclude that $|(A_{n}+r)\Delta A_{n}|/|A_{n}|\to 1/2$ as $n\to \infty $ . Hence, the sequence $(A_{n})_{n\in \mathbb {N}}$ is not Følner.

In this section, we prove Theorem 3.2, stating that, when the sets $F_n$ are built as in equation (2), the Følner property is equivalent to the existence of arbitrarily large balls in the sets $F_n$ for large enough n. Moreover, we show that we have some control over the index of the sequence to check an equivalent property, which implies that being Følner is decidable.

Theorem 3.2. Let $L\in \mathcal {M}(d,\mathbb {Z})$ be an expansion matrix and $F_{1}\Subset \mathbb {Z}^{d}$ be a fundamental domain of $L(\mathbb {Z}^{d})$ in $\mathbb {Z}^{d}$ containing $\boldsymbol {0}$ . Set $\bar {r} = \|L^{-1}(F_1)\|/(1-\|L^{-1}\|)$ . The sequence $(F_{n})_{n\in \mathbb {N}}$ defined as equation (2) is Følner if and only if there exists $n \leq ({(6\bar {r})^{3d}-(6\bar {r})^d})/{6}$ such that $F_n$ contains a translation of $C_{L,F_1}+[B(\boldsymbol {0},\bar {r})\cap \mathbb {Z}^{d}]$ . In particular, it is decidable to check whether $(F_{n})_{n\in \mathbb {N}}$ is a Følner sequence.

In the block case, that is, $L= {\mathrm {diag}}(\ell _{i})_{i=1}^{d}$ and , we note that $C_{L,F_{1}}+[B(\boldsymbol {0},\bar {r})\cap \mathbb {Z}^{d}]\subseteq [B(\boldsymbol { 0},2\sqrt {d})\cap \mathbb {Z}^{d}]$ , and hence for any $n\in \mathbb {N}$ such that $n\geq \log (4\sqrt {d})/\log (\min \ell _{i})$ contains a translation of $C_{L,F_{1}}+[B(\boldsymbol {0},\bar {r})\cap \mathbb {Z}^{d}]$ .

Roughly speaking, the idea of the proof of Theorem 3.2 is twofold. First, we show that if some $F_N$ contains a large enough ball B, then the ‘extended image’ $L^m(B)+F_m$ inside $F_{N+m}$ will contain a ball larger than B and this will enforce the Følner property. The statement of Proposition 3.3 below is actually more precise about the ball B, which allows us get a characterization of the Følner property. Figure 1 illustrates this idea. In the second step (Proposition 3.4), we define a finite graph and translate the condition of Proposition 3.3 into the existence of a path in this graph. This leads to the decidability of the Følner property and to a bound on the index N. Figure 3 is an example of the graphs for the triangular Thue–Morse substitution.

Figure 1 A visual representation of Claim 1 with the triangular Thue–Morse substitution (Example 2.1). The black points on the left represent the points in $F_{4}$ , and $F_{5}$ on the right. The blue points (triangles) represent the points $(-2,5)$ in $F_{4}$ (left) and $(-4,10)=2\cdot (-2,5)+(0,0)$ in $F_{5}$ (right). Finally, the red points (squares) on the left represent the set $(-2,5)+C_{L,F_{1}}+K$ and $(-4,10)+C_{L,F_{1}}+L(K)+F_{1}$ on the right.

Consider the set $K\Subset \mathbb {Z}^{d}$ given by Proposition 2.3, and the set $C_{L,F_{1}}\Subset \mathbb {Z}^{d}$ given by Proposition 2.5 with $A=\{\boldsymbol {0}\}$ and $F=F_{1}+F_{1}$ . We recall that, by item (2), for any $n\geq 1, C_{L,F_{1}}+F_{n}+F_{n}\subseteq L^n(C_{L,F_{1}})+F_n$ . We also deduce from item (4) that

(3) $$ \begin{align} \|C_{L,F_1}\| \leq 2\bar{r}. \end{align} $$

Assume, up to replacing L by an appropriate power of it, that $K=( {\mathrm {id}}-L)^{-1}(F_{1})\cap \mathbb {Z}^{d}$ . The following result shows a characterization for the sequence of fundamental domains $(F_{n})_{n\in \mathbb {N}}$ to be Følner.

Proposition 3.3. Let $L\in \mathcal {M}(d,\mathbb {Z})$ be an expansion matrix, $F_{1}\Subset \mathbb {Z}^{d}$ a fundamental domain of $L(\mathbb {Z}^{d})$ in $\mathbb {Z}^{d}$ containing $\boldsymbol {0}$ , and $(F_{n})_{n\in \mathbb {N}}$ be the sequence of fundamental domains defined as equation (2). The following conditions are equivalent:

1. (1) the sequence $(F_{n})_{n\in \mathbb {N}}$ is Følner;

2. (2) there exists $n \in \mathbb {N}$ and $\boldsymbol {f}\in F_{n}$ such that

   $$ \begin{align*} \boldsymbol{f}+C_{L,F_{1}}+K\subseteq F_{n}; \end{align*} $$

3. (3) for every finite set $B \supseteq K$ , there exists $m \in \mathbb {N}$ , $\boldsymbol {f}\in F_{m}$ such that

   $$ \begin{align*} \boldsymbol{f}+C_{L,F_{1}}+B\subseteq F_{m}. \end{align*} $$

Note that item (3) implies that it is equivalent for a substitution $\zeta $ to define that the substitutive subshift $X_{\zeta }$ to the sequence $(F_{n})_{n>0}$ is Følner.

Proof. The implications $(1) \Rightarrow (2)$ , $(1) \Rightarrow (3)$ , and $(3) \Rightarrow (2)$ are direct. Let us thus assume item (2). We recall that, by Proposition 2.3, $\bigcup \nolimits _{p\in \mathbb {N}}L^{p}(K)+F_{p}=\mathbb {Z}^{d}$ and the sequence of finite sets $(L^{p}(K)+F_{p})_{p\in \mathbb {N}}$ is nested. To check that $(F_{n})_{n\in \mathbb {N}}$ is Følner, it is enough to prove that

$$ \begin{align*} (\text{for all } p\in \mathbb{N})\ \lim\limits_{n\to\infty}\dfrac{|F_{n}\Delta (F_{n}+C_{L,F_{1}}+L^{p}(K)+F_{p})|}{|F_{n}|}=0, \end{align*} $$

or, equivalently, that

(4) $$ \begin{align} (\text{for all } p\in \mathbb{N})\ \lim\limits_{n\to\infty} \frac{|\{\boldsymbol{f}\in F_{n}\colon \boldsymbol{f}+C_{L,F_1}+L^{p}(K)+F_{p} \subseteq F_n\}|}{|F_n|} = 1. \end{align} $$

For any $n\in \mathbb {N}$ and $p\in \mathbb {N}$ , we set

$$ \begin{align*} J_{n,p}=\{\boldsymbol{f}\in F_{n}\colon \boldsymbol{f}+C_{L,F_1}+L^{p}(K)+F_{p} \subseteq F_n\}, \end{align*} $$

$a_{n,p}=|J_{n,p}|$ , and $b_{n,p}=a_{n,p}/|F_{n}|$ . By assumption, there exists $N \in \mathbb {N}$ and $\boldsymbol {f} \in F_N$ such that $\boldsymbol {f}+C_{L,F_{1}}+K\subseteq F_{N}$ . In other words, we have $a_{N,0} \geq 1$ . Claim 1 below shows a form of stability of elements of $J_{n,p}$ under the application of L. In particular, it implies that $a_{N+p,p} \geq 1$ for all $p \in \mathbb {N}$ . Since $\bigcup \nolimits _{p\in \mathbb {N}}L^{p}(K)+F_{p}=\mathbb {Z}^{d}$ and the sequence of finite sets $(L^{p}(K)+F_{p})_{p\in \mathbb {N}}$ is nested, it also implies item (3).

Claim 1. For all $n,p \in \mathbb {N}$ and all $\boldsymbol {f} \in F_n$ , if $\boldsymbol {f}+C_{L,F_{1}}+L^p(K)+F_p\subseteq F_{n}$ , then all elements $\boldsymbol {g} \in L(\boldsymbol {f})+F_1 \subseteq F_{n+1}$ are such that $\boldsymbol {g}+C_{L,F_{1}}+L^{p+1}(K)+F_{p+1}\subseteq F_{n+1}$ . In particular, we have

$$ \begin{align*} a_{n+1,p} \geq a_{n+1,p+1} \geq a_{n,p} \lvert \det(L)\rvert. \end{align*} $$

Proof of Claim 1

Indeed, since $C_{L,F_{1}}+F_1+F_1\subseteq L(C_{L,F_{1}})+F_1$ , we have

$$ \begin{align*} \boldsymbol{f}+C_{L,F_{1}}+L^p(K)+F_p\subseteq F_{n}& \!\implies\! L(\boldsymbol{f})+(L(C_{L,F_{1}})+F_{1})+L^{p+1}(K)+L(F_p)\subseteq F_{n+1} \\ & \!\implies\! (L(\boldsymbol{f})+F_{1})+C_{L,F_{1}}+L^{p+1}(K)+F_{p+1}\subseteq F_{n+1}. \end{align*} $$

This implies that $a_{n+1,p+1} \geq a_{n,p} \lvert \det (L)\rvert $ . The other inequality follows from the fact that $L^p(K)+F_p \subseteq L^{p+1}(K)+F_{p+1}$ .

Figure 1 illustrates Claim 1. Note that Claim 1 proves that item (2) implies item (3).

Since $|F_{n+1}| = |F_n|\lvert \det (L)\rvert $ , we deduce from Claim 1 that the sequence $(b_{n,p})_n$ is non-decreasing for all p. Furthermore, it is also bounded from above by 1, and the limit in equation (4) exists.

For every $p \in \mathbb {N}$ , we set $m(p)=\inf \{n \mid a_{n,p}>0\}$ . By hypothesis and Claim 1, we note that $m(p)\leq N+p$ . Recall that for any $k\geq 1$ , any element in $F_{k\cdot m(p)}$ can be written as $\sum \nolimits _{i=0}^{k-1}L^{i\cdot m(p)}(\boldsymbol {f}_{i})$ , with $\boldsymbol {f}_{i}\in F_{m(p)}$ .

Claim 2. If there exists $0\leq i\leq k-1$ such that $\boldsymbol {f}_{i}\in J_{m(p),p}$ , then $(\sum \nolimits _{i=0}^{k-1}L^{i \cdot m(p)}(\boldsymbol {f}_{i}))\in J_{k\cdot m(p),p}$ .

Using the notion of invariance introduced by Weiss in [45], Claim 2 proves that if $F_{n}$ is $(C+L^{p}(K)+F_{p},\varepsilon )$ -invariant, then for any $k>0$ , the set $F_{kn}$ is $(C+L^{p}(K)+F_{p},\varepsilon ^{k})$ -invariant, which will let us conclude that the sequence $(F_{n})_{n>0}$ is Følner.

Proof of Claim 2

First, we note that $m(p)\geq p$ . For any $\boldsymbol {c}\in C_{L,F_{1}}$ and $\boldsymbol {n}\in L^{p}(K)+F_{p}$ , we need to find $(\boldsymbol {g}_{i})_{i=0}^{k-1}\subseteq F_{m(p)}$ such that

$$ \begin{align*}\bigg(\sum\limits_{i=0}^{k-1}L^{i\cdot m(p)}(\boldsymbol{f}_{i})\bigg)+\boldsymbol{c}+\boldsymbol{n}=\bigg(\sum\limits_{i=0}^{k-1}L^{i\cdot m(p)}(\boldsymbol{g}_{i})\bigg).\end{align*} $$

Let $0\leq j\leq k-1$ be the minimal such that $\boldsymbol {f}_{j}\in J_{m(p),p}$ . If $j=0$ , then the result follows from Claim 2. Assume that $j>0$ . Since $L^p(K)+F_p \subseteq L^{j \cdot m(p)}(K)+F_{j \cdot m(p)}$ , there exist $\boldsymbol {k}\in K$ and $(\boldsymbol {h}_{i})_{i=0}^{j-1}\subseteq F_{m(p)}$ such that

$$ \begin{align*} \boldsymbol{n}=L^{j\cdot m(p)}(\boldsymbol{k})+\bigg(\sum\limits_{i=0}^{j-1}L^{i\cdot m(p)}(\boldsymbol{h}_{i})\bigg). \end{align*} $$

Then, using items (2) and (3) of Proposition 2.5, there exists $\boldsymbol {c}_{1}\in C_{L,F_{1}}$ and $(\boldsymbol {g}_{i})_{i=0}^{j-1}\subseteq F_{m(p)}$ such that

$$ \begin{align*}\boldsymbol{c}+\bigg(\sum\limits_{i=0}^{j-1}L^{i\cdot m(p)}(\boldsymbol{f}_{i})\bigg)+\bigg(\sum\limits_{i=0}^{j-1}L^{i\cdot m(p)}(\boldsymbol{h}_{i})\bigg)=L^{j\cdot m(p)}(\boldsymbol{ c}_{1})+\sum\limits_{i=0}^{j-1}L^{i\cdot m(p)}(\boldsymbol{g}_{i}).\end{align*} $$

Hence,

$$ \begin{align*}\bigg(\sum\limits_{i=0}^{k-1}L^{i\cdot m(p)}(\boldsymbol{f}_{i})\bigg)+\boldsymbol{c}+\boldsymbol{n}&=\bigg(\sum\limits_{i=0}^{j-1}L^{i\cdot m(p)}(\boldsymbol{ g}_{i})\bigg)+\bigg(\sum\limits_{i=j+1}^{k-1}L^{i\cdot m(p)}(\boldsymbol{f}_{i})\bigg)\\&\quad+L^{j\cdot m(p)}(\boldsymbol{f}_{j}+\boldsymbol{c}_{1}+\boldsymbol{k}).\end{align*} $$

We conclude by noting that $\boldsymbol {f}_j+\boldsymbol {c}_{1}+\boldsymbol {k}\in F_{m(p)}$ .

Now, Claim 2 implies that

$$ \begin{align*}&|F_{k\cdot m(p)}\Delta (F_{k\cdot m(p)}+C+L^{p}(K)+F_{p})|\\&\quad\subseteq \bigg\{\sum\limits_{i=0}^{k-1}L^{i \cdot m(p)}(\boldsymbol{f}_{i})\in F_{k\cdot m(p)}\colon (\text{for all } i)\ \boldsymbol{ f}_{i}\notin J_{m(p),p}\bigg\}.\end{align*} $$

Hence, for any $p\in \mathbb {N}$ ,

$$ \begin{align*} \lim\limits_{k\to\infty}b_{k,p} &\geq \lim\limits_{k\to\infty}b_{k\cdot m(p),p} \\ & \geq 1-\lim\limits_{k\to\infty}\dfrac{\bigg|\bigg\{\sum\limits_{i=0}^{k-1}L^{i}(\boldsymbol{f}_{i})\in F_{k\cdot m(p)}\colon (\text{for all }\ 0\leq i\leq k-1)\boldsymbol{f}_{i}\notin J_{m(p),p}\bigg\}\bigg|}{|F_{k\cdot m(p)}|}\\ & =1-\lim\limits_{k\to\infty}\dfrac{(\lvert \det(L)\rvert^{m(p)}-|J_{m(p),p}|)^{k}}{\lvert \det(L)\rvert^{k\cdot m(p)}}\\ & = 1-\lim\limits_{k\to\infty}\bigg(1-\dfrac{|J_{m(p),p}|}{\lvert \det(L)\rvert^{m(p)}}\bigg)^{k}\\ & = 1. \end{align*} $$

We conclude that the sequence $(F_{n})_{n>0}$ is Følner.

We now aim to show that satisfying item (2) of Proposition 3.3 is decidable. The next result shows that this condition is equivalent to the existence of a synchronizing word in some particular finite graph, a condition which is known to be decidable [44].

Assume that $B \Subset \mathbb {Z}^d$ satisfies $K \subseteq B \subseteq L(B)+F_1$ . Let us consider a labeled directed graph $\mathcal {G}(L,F_{1},B)$ , where the vertex set is $C_{L,F_{1}}+B$ and there is an edge from $\boldsymbol {a}\in C_{L,F_{1}}+B$ to $\boldsymbol {b}\in C_{L,F_{1}}+B$ labeled with $\boldsymbol {f}\in F_{1}$ if and only if there exists $\boldsymbol {g}\in F_{1}$ such that $\boldsymbol {f}+\boldsymbol {a}=L(\boldsymbol {b})+\boldsymbol {g}$ . Figure 2 shows the graph $\mathcal {G}(L,F_{1},B)$ in the classical one-dimensional case, where $L=\ell \geq 2$ and .

Figure 2 The graph for the classical one-dimensional case.

Figure 3 The graph $\mathcal {G}(L,F_{1},K)$ for the triangular Thue–Morse. Outgoing edges from vertex $(0,0)$ are not represented as they are self-loops.

Figure 3 represents the graph $\mathcal {G}(L,F_{1},K)$ for the triangular Thue–Morse (Example 2.1).

Note that $\boldsymbol {0}\in C_{L,F_{1}}+B$ has out-degree $|F_{1}|=\lvert \det (L)\rvert $ and any edge from $\boldsymbol {0}$ is a self-loop. Furthermore, if $\boldsymbol {a}\in C_{L,F_{1}}+B$ is an in-neighbor of $\boldsymbol {0}$ with an edge labeled by $\boldsymbol {f}\in F_{1}$ , then $\boldsymbol {f}+\boldsymbol {a}\in F_{1}$ . Let $P=\boldsymbol {a}_{0}\xrightarrow []{\boldsymbol {f}_{0}} \boldsymbol {a}_{1} \xrightarrow []{\boldsymbol { f}_{1}} \boldsymbol {a}_{2}$ be a path in $\mathcal {G}(L,F_{1},B)$ . By definition, we have that $\boldsymbol {f}_{0}+\boldsymbol {a}_{0}=L(\boldsymbol {a}_{1})+\boldsymbol {g}_{0}$ and $\boldsymbol { f}_{1}+\boldsymbol {a}_{1}=L(\boldsymbol {a}_{2})+\boldsymbol {g}_{1}$ for some $\boldsymbol {g}_{0}, \boldsymbol {g}_{1}\in F_{1}$ . This implies that $L(\boldsymbol {f}_{1})+\boldsymbol {f}_{0}+\boldsymbol { a}_{0}=L^{2}(\boldsymbol {a}_{2})+L(\boldsymbol {g}_{1})+\boldsymbol {g}_{0}$ .

Proposition 3.4. Let $n \geq 1$ and $\boldsymbol {f} = \sum \nolimits _{i=0}^{n-1}L^{i}(\boldsymbol {f}_{i}) \in F_{n}$ , with $\boldsymbol {f}_{i} \in F_1$ for every i. We have that $\boldsymbol {f}+C_{L,F_{1}}+B\subseteq F_{n}$ if and only if $\boldsymbol {f}_{0}\boldsymbol {f}_{1} \cdots \boldsymbol {f}_{n-1}$ labels a path from every vertex in $\mathcal {G}(L,F_{1},B)$ to $\boldsymbol {0}$ .

Proof. Assume that $\boldsymbol {f}+C_{L,F_{1}}+B\subseteq F_{n}$ . Set $\boldsymbol {a}\in C_{L,F_{1}}+B$ . Then, there exists $\boldsymbol {g}(\boldsymbol {a})=\sum \nolimits _{i=0}^{n-1}L^{i}(\boldsymbol {g}_{i}(\boldsymbol {a}))\in F_{n}$ such that $\boldsymbol {f}+\boldsymbol {a}=\boldsymbol {g}(\boldsymbol {a})$ . Note that there exists $\boldsymbol { a}_{1}\in C_{L,F_{1}}+B$ such that $\boldsymbol {f}_{0}+\boldsymbol {a}=L(\boldsymbol {a}_{1})+\boldsymbol {g}_{0}(\boldsymbol {a})$ , and a straightforward induction shows that there exists a sequence $(\boldsymbol { a}_{i})_{i=1}^{n-1}$ such that for any $1\leq i\leq n-1$ , $\boldsymbol {f}_{i}+\boldsymbol {a}_{i}=L(\boldsymbol {a}_{i+1})+\boldsymbol {g}_{i}(\boldsymbol {a})$ and $\boldsymbol {f}_{n-1}+\boldsymbol {a}_{n-1}=\boldsymbol {g}_{n-1}(\boldsymbol {a})$ . This implies that there is a path $P_{\boldsymbol {a}}=\boldsymbol {a}\xrightarrow []{\boldsymbol {f}_{0}} \boldsymbol {a}_{1} \xrightarrow []{\boldsymbol {f}_{1}} \cdots \xrightarrow []{\boldsymbol {f}_{n-2}} \boldsymbol {a}_{n-1} \xrightarrow []{\boldsymbol {f}_{n-1}} \boldsymbol {0}$ . All of these paths have the same label. The other direction is direct.

The next result is a direct consequence of Propositions 3.3 and 3.4.

Corollary 3.5. Let $L\in \mathcal {M}(d,\mathbb {Z})$ be an expansion matrix, $F_{1}\Subset \mathbb {Z}^{d}$ a fundamental domain of $L(\mathbb {Z}^{d})$ in $\mathbb {Z}^{d}$ containing $\boldsymbol {0}$ , and $(F_{n})_{n\in \mathbb {N}}$ be the sequence of fundamental domains defined as equation (2). Let also $B \Subset \mathbb {Z}^d$ satisfying $K \subseteq B \subseteq L(B)+F_1$ . The sequence $(F_{n})_{n\in \mathbb {N}}$ is Følner if and only if there exists $n \geq 1$ and a word $\boldsymbol {f}_{0}\boldsymbol {f}_{1} \cdots \boldsymbol {f}_{n-1} \in F_1^*$ that labels a path from any vertex to $\boldsymbol {0}$ in $\mathcal {G}(L,F_{1},B)$ .

Note that in Figure 2, if $\ell \geq 3$ , the letter $\texttt {1}$ labels paths from every vertex in $\{-1,0,1\}$ to $0$ . If $\ell =2$ , the word $\texttt {01}$ labels paths from every vertex in $\{-1,0,1\}$ to $0$ . Observe that in Figure 3, the word $(0,1)(1,0)(-1,-1)(0,1)$ labels paths from every vertex to $(0,0)$ , which implies by Corollary 3.5 that the corresponding sequence $(F_n)_{n>0}$ of fundamental domains is Følner. In particular, we have

$$ \begin{align*} \binom{-2}{5} = \binom{0}{1} + L \binom{1}{0} + L^2 \binom{-1}{-1} +L^3\binom{0}{1}, \end{align*} $$

so Proposition 3.4 implies that $(-2,5) \in F_4$ satisfies $(-2,5)+C_{L,F_1}+K \subseteq F_4$ . This inclusion is illustrated on the left part of Figure 1.

Proof of Theorem 3.2

Set $B = [B(\boldsymbol {0},\bar {r}) \cap \mathbb {Z}^d]$ . Since $\|K\| \leq \bar {r}$ (see Remark 2.4), we have that $K \subseteq B$ . Assuming that some $F_n$ contains a translation of $C_{L,F_1}+B$ , we directly deduce from Proposition 3.3 that the sequence $(F_n)_{n>0}$ is Følner.

Let us now assume that the sequence $(F_n)_{n>0}$ is Følner. We first prove that we also have that $B \subseteq L(B)+F_1$ . Indeed, if $\boldsymbol {n}, \boldsymbol {n}_{1}\in \mathbb {Z}^{d}$ and $\boldsymbol {f}_{1}\in F_{1}$ are such that $\boldsymbol {n}=L(\boldsymbol {n}_{1})+\boldsymbol {f}_{1}$ , then

$$ \begin{align*}\Vert \boldsymbol{n}_{1}\Vert \leq \Vert L^{-1}\Vert\cdot \Vert\boldsymbol{n}\Vert+\Vert L^{-1}(\boldsymbol{f}_{1})\Vert.\end{align*} $$

In particular, we have that

(5) $$ \begin{align} B \subseteq L([B(\boldsymbol{0}, \Vert L^{-1}\Vert \cdot \bar{r}+\Vert L^{-1}(F_{1})\Vert )\cap \mathbb{Z}^{d}])+F_{1} = L(B)+F_{1}. \end{align} $$

By Corollary 3.5, there exists $n \geq 1$ and a word $\boldsymbol {f}_{0}\boldsymbol {f}_{1} \cdots \boldsymbol {f}_{n-1}$ labeling a path $\mathcal {G}(L,F_{1},B)$ from every vertex to $\boldsymbol {0}$ . When such a word exists, it is known that the length of the shortest one is at most $(N^{3}-N)/6$ , where N is the number of vertices of $\mathcal {G}(L,F_{1},B)$ [26, 38]. It thus suffices to observe, using equation (3), that $N \leq (6r)^d$ .

Thanks to Proposition 3.3, from now on, we always assume that the sequence of supports of a substitution is Følner.

The techniques used in the proof of Theorem 3.2 are also useful to understand the pattern complexity of a multidimensional substitutive subshift. The pattern complexity function (or just the complexity function), denoted by $p_{\zeta }(r)$ , is the number of patterns in $\mathcal {L}_{[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}(X_{\zeta })$ . The next result shows that the pattern complexity of a multidimensional substitutive subshift is polynomial. This result was already known in the case of aperiodic tillings [40, Theorem 7.17], which follows the proof in the dissertation of Hansen [28].

Proposition 3.6. Let $\zeta $ be an aperiodic and primitive constant-shape substitution with expansion matrix $L_{\zeta }$ and support $F_{1}^{\zeta }$ . Then, there exists a constant $c>0$ such that

$$ \begin{align*}p_{\zeta}(r)\leq c\cdot r^{-\log(\lvert \det(L_\zeta)\rvert)/\log(\Vert L_\zeta^{-1}\Vert)}.\end{align*} $$

Proof. To alleviate notation in the proof, we omit the indices and exponents $\zeta $ to denote the fundamental domains $F_n$ and the expansion matrix L. Set $B=[B(\boldsymbol {0},\bar {r})\cap \mathbb {Z}^{d}]$ , where $\bar {r} = \|L^{-1}(F_1)\|/(1-\|L^{-1}\|)$ . The idea of the proof is to show that, for all $r>0$ , every pattern in $\mathcal {L}_{[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}(X_{\zeta })$ will appear in the image under some power of $\zeta $ of a pattern in $\mathcal {L}_{C_{L,F_1}+B}(X_{\zeta })$ and that we can control the needed power. The polynomial bound then appears using some counting argument.

First, observe that the inclusion given in equation (5) holds if we replace $\bar {r}$ by any positive radius r, that is,

$$ \begin{align*} [B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}] \subseteq L([B(\boldsymbol{0}, \Vert L^{-1}\Vert \cdot r+\Vert L^{-1}(F_{1})\Vert )\cap \mathbb{Z}^{d}])+F_{1}. \end{align*} $$

This implies that for all $r>0$ ,

(6) $$ \begin{align} [B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]\subseteq L^{n(r)}(B)+F_{n(r)}, \end{align} $$

where $n(r)= \lceil \log (r-\Vert L^{-1}(F_{1}))\Vert /\log (\Vert L^{-1}\Vert )\rceil $ . Recall that the set $C_{L,F_1}$ satisfies $C_{L,F_1} + F_n + F_n \subseteq L^n(C_{L,F_1})+F_n$ for all $n \geq 0$ . Thus, using equation (6), we get that

$$ \begin{align*}F_{n(r)}+[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]\subseteq L^{n(r)}(C_{L,F_{1}}+B)+F_{n(r)}.\end{align*} $$

Let $x\in X_{\zeta }$ be a fixed point of $\zeta $ . Since $x=\zeta (x)$ , for every pattern $\texttt {u}\in \mathcal {L}_{[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}(X_{\zeta })$ , there exists $\texttt {v}\in \mathcal {L}_{C_{L,F_{1}}+B}(X_{\zeta })$ and $\boldsymbol {f}\in F_{n(r)}$ such that $\texttt {u}=\zeta ^{n(r)} (\texttt {v})_{\boldsymbol {f}+[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}$ . Indeed, if $\boldsymbol {n}\in \mathbb {Z}^{d}$ is such that $\texttt {u}=x_{\boldsymbol {n}+[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}$ , write $\boldsymbol {n}=L^{n(r)}(\boldsymbol {n}_{1})+\boldsymbol {f}$ for some $\boldsymbol {n}_{1}\in \mathbb {Z}^{d}$ and $\boldsymbol {f}\in F_{n(r)}$ . Consider $\texttt {v}=x|_{\boldsymbol {n}_{1}+C_{L,F_{1}}+B}$ . Since x is a fixed point of $\zeta $ , we have that $\zeta ^{n(r)}(\texttt {v})=x|_{\boldsymbol { n}+L^{n(r)}(C_{L,F_{1}}+B)+F_{n(r)}}$ . In particular, $\texttt {u}=\zeta ^{n(r)}(\texttt {v})_{\boldsymbol {f}+[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}$ . Now, since $|\mathcal {L}_{C_{L,F_{1}}+B}(X_{\zeta })|$ is at most $|\mathcal {A}|^{|C_{L,F_{1}}+B|}$ , we have that

$$ \begin{align*} p_{\zeta}(r) & \leq |\mathcal{A}|^{|C_{L,F_{1}}+B|}\lvert \det(L)\rvert^{n(r)} \\ & \leq |\mathcal{A}|^{|C_{L,F_{1}}+B|}\cdot r^{-\log(\lvert \det(L)\rvert)/\log(\Vert L^{-1}\Vert)}, \end{align*} $$

which ends the proof.

4. Conjugacy between constant-shape substitutions sharing the expansion matrix

Constant-shape substitutions in dimension 1 were defined in [24] under the name of pattern substitutions. This notion slightly differs from the one-dimensional constant-shape substitutions by allowing the support associated with each letter to vary. The author proved that every biinfinite sequence which is a fixed point of a pattern substitution is, in fact, substitutive. As a consequence, pattern substitutions do not generate new aperiodic sequences beyond those produced by regular substitutions. This raised the question of whether this fact holds in higher dimensions. In this section, we prove an analog of this result (Theorem 4.1). For a fixed expansion matrix, the conjugacy class of substitutive subshifts is invariant by changing the supports of the substitution.

Let us start with an example. The triangular Thue–Morse substitution has exactly eight $\sigma _{\Delta TM}$ -periodic points of order 2 (or $\sigma _{\Delta TM}^{2}$ has exactly eight fixed points), which are generated by the eight patterns in $\mathcal {L}_{K_{\Delta TM}}(X_{\sigma _{\Delta TM}})$ shown in Figure 4.

Now, consider the substitution $\sigma _{1 }$ shown in Figure 5, with $L=2\cdot {\mathrm {id}}_{\mathbb {R}^{2}}$ and , over the alphabet $\mathcal {A}=\{0,1,\ldots ,15\}$ defined as follows.

This square substitution is conjugated to the triangular Thue–Morse substitution via the following coding:

$$ \begin{align*}\begin{array}{cccccccccccccccc} \Phi: & 0 & \mapsto & a & & 1 & \mapsto & b & & 2 & \mapsto & b & & 3 & \mapsto & a \\ & & & & & & & & & & & & & & & \\ & 4 & \mapsto & a & & 5 & \mapsto & a & & 6 & \mapsto & a & & 7 & \mapsto & b \\ & & & & & & & & & & & & & & & \\ & 8 & \mapsto & b & & 9 & \mapsto & b & & 10 & \mapsto & b & & 11 & \mapsto & b \\ & & & & & & & & & & & & & & & \\ & 12 & \mapsto & a & & 13 & \mapsto & a & & 14 & \mapsto & a & & 15 & \mapsto & b. \\ \end{array}\end{align*} $$

To see this, we note that $\sigma _{1 }$ also has exactly eight $\sigma _{1}$ -periodic points of order 2 generated by the patterns in shown in Figure 6.

Figure 4 The eight patterns in $\mathcal {L}_{K_{\Delta TM}}(X_{\sigma _{\Delta TM}})$ .

Figure 5 A square substitution conjugate to the triangular Thue–Morse substitution.

Figure 6 The patterns that generate the eight fixed points of $\sigma _{1 }^{2}$ .

A standard computation shows that if we define $\phi :X_{\sigma _{\Delta TM}}\to \phi (X_{\sigma _{1 }})$ by the coding $\phi (x)_{\boldsymbol {n}}=\Phi (x_{\boldsymbol {n}})$ for any $\boldsymbol {n}\in \mathbb {Z}^{2}$ , then any fixed point of $\sigma _{1 }^{2}$ is mapped, via $\phi $ , to a fixed point of $\sigma _{\Delta TM}^{2}$ . The minimality of $(X_{\sigma _{\Delta TM}},S,\mathbb {Z}^{2})$ lets us conclude that $\phi (X_{\sigma _{\Delta TM}})=X_{\sigma _{1 }}$ . It can be shown that the map $\psi :X_{\sigma _{\Delta TM}}\to X_{\sigma _{1 }}$ induced by the local map

$$ \begin{align*}\begin{array}{llllllllllllllllllll} \Psi: & b & a & & & & a & a & & & & b & a & & & & a & a & & \\ & a & b & \mapsto & 0 & & b & b & \mapsto & 1 & & b & a & \mapsto & 2 & & a & a & \mapsto & 3 \\ & & & & & & & & & & & & & & & & & & & \\ & a & a & & & & a & b & & & & b & a & & & & a & a & & \\ & a & b & \mapsto & 4 & & a & a & \mapsto & 5 & & a & a & \mapsto & 6 & & b & a & \mapsto & 7 \\ & & & & & & & & & & & & & & & & & & & \\ & a & b & & & & b & b & & & & a & b & & & & b & b & & \\ & b & a & \mapsto & 8 & & b & a & \mapsto & 9 & & b & b & \mapsto & 10 & & b & b & \mapsto & 11 \\ & & & & & & & & & & & & & & & & & & & \\ & b & b & & & & b & b & & & & a & b & & & & b & a & & \\ & a & b & \mapsto & 12 & & a & a & \mapsto & 13 & & a & b & \mapsto & 14 & & b & b & \mapsto & 15, \\ \end{array}\end{align*} $$

satisfies $\psi \circ \phi = {\mathrm {id}}_{X_{\sigma _{1 }}}$ , so $(X_{\sigma _{1}},S,\mathbb {Z}^{2}), (X_{\sigma _{TM}},S,\mathbb {Z}^{2})$ are topologically conjugate. The example above generalizes as follows.

Theorem 4.1. Let $\zeta $ be an aperiodic primitive constant-shape substitution with an expansion matrix L and support $F_{1}$ . Now, consider another fundamental domain $G_1\Subset \mathbb {Z}^{d}$ of $\mathbb {Z}^d/L(\mathbb {Z}^d)$ , with $\mathbf {0} \in G_1$ , and such that the associated sequences $(F_{n})_{n>0}$ , $(G_{n})_{n>0}$ are Følner. There exists an aperiodic computable primitive constant-shape substitution $\tilde {\zeta }$ with support $G_{1}$ such that $(X_{\zeta },S,\mathbb {Z}^{d})$ and $(X_{\tilde {\zeta }},S,\mathbb {Z}^{d})$ are topologically conjugate.

The proof of Theorem 4.1 is an adaptation of the construction of substitution of length n from the one-dimensional case that we now recall. We refer to [39] for more details. Assume that $\zeta : \mathcal {A}^* \to \mathcal {A}^*$ is a primitive one-dimensional substitution. For every $n \geq 1$ , we consider the set $\mathcal {L}_n(X_\zeta )$ as an alphabet $\mathcal {B}_n$ and define the substitution $\zeta _n:\mathcal {B}_n^* \to \mathcal {B}_n^*$ as follows. If $w = w_1 \cdots w_n \in \mathcal {B}_n$ and $\zeta (w) = v = v_1 \cdots v_\ell $ , where all $w_i$ and $v_j$ are letters, then $\ell \geq |\zeta (w_1)|+n-1$ and we set

$$ \begin{align*} \zeta_n(w) = (v_1 \cdots v_n)(v_2 \cdots v_{n+1}) \cdots (v_{|\zeta(w_1)|} \cdots v_{|\zeta(w_1)|+n-1}). \end{align*} $$

It turns out that $\zeta _n$ is a primitive substitution and that the subshifts $X_\zeta $ and $X_{\zeta _n}$ are conjugate, an isomorphism being given by the sliding block

$$ \begin{align*} \Phi : \mathcal{L}_{n}(X_\zeta) \to \mathcal{B}_n, w \mapsto (w). \end{align*} $$

In the proof of Theorem 4.1, we find a set B whose $F_1$ -image $L(B)+F_1$ can be cut into blocks with support B along $G_1$ . This allows us define the substitution $\tilde {\zeta }$ and we prove that the associated subshifts are conjugate. Note that, the local map $\psi $ in the above example that defines a conjugacy between the triangular Thue–Morse substitution and a square substitution is a coding of the patterns in .

Proof. Using Remark 2.4, we may assume that $\zeta $ has a fixed point $\bar {x}\in X_{\zeta }$ . Assume $K_{1}=( {\mathrm {id}}-L)^{-1}(F_{1})\cap \mathbb {Z}^{d}$ and $K_{2}=( {\mathrm {id}}-L)^{-1}(G_{1})\cap \mathbb {Z}^{d}$ are the sets given by Proposition 2.3 for $F_{1}$ and $G_{1}$ , respectively.

First, we adapt the proof of Proposition 2.5 to obtain a finite set $A\Subset \mathbb {Z}^{d}$ such that for any $n\geq 0, K_{2}+A+G_{n}\subseteq L^{n}(K_{2}+A)+F_{n}$ . Consider the sequence $(A_n)_{n \geq 0}$ of finite sets in $\mathbb {Z}^d$ as follows: set $A_0 = \{\mathbf {0}\}$ , and for $n\geq 0$ ,

$$ \begin{align*} A_{n+1} &= \{ \boldsymbol{p} \in \mathbb{Z}^d \mid \text{there exists } \boldsymbol{f} \in F_1, \boldsymbol{g}_{1}, \boldsymbol{g}_{2} \in G_1, \boldsymbol{q} \in A_n: L(\boldsymbol{p})+\boldsymbol{f} = \boldsymbol{q} + \boldsymbol{ g}_{1} + \boldsymbol{g}_{2}\}\\ &= L^{-1}(A_n + G_1 + G_1 - F_1) \cap \mathbb{Z}^d. \end{align*} $$

We will prove that this sequence is eventually stationary, that is, there exists $N>0$ such that for all $m\geq N$ , $A_{m}=A_{N}$ .

Claim 1. For every $n\geq 0$ and every $k>0$ , we have the following inclusions: $A_{n}\subseteq A_{n+1}$ and $K_{2}+A_{n}+G_{k}\subseteq L^{k}(K_{2}+A_{n+k})+F_{k}$ .

This claim shows that if we choose $N>0$ such that for all $m\geq N$ , $A_{m}=A_{N}$ , then for all $k>0$ , we have that $K_{2}+A_{N}+G_{k}\subseteq L^{k}(K_{2}+A_{N})+F_{k}$ . Now, if we consider a pattern $\texttt {w}\in \mathcal {L}_{K_{2}+A_{N}}(X_{\zeta })$ , the support of $\zeta ^{k}(\texttt {w})$ is large enough to be split into $(K_{2}+A_{N})$ -blocks along $G_k$ . This will allow us to consider $\mathcal {L}_{K_{2}+A_{N}}(X_{\zeta })$ as an alphabet and to define the substitution $\tilde {\zeta }$ with support $G_1$ .

Proof of Claim 1

We first prove that $A_{n}\subseteq A_{n+1}$ for every $n \geq 0$ . Since $\boldsymbol {0}\in G_1 \cap F_1$ , we trivially have that $A_{0} \subseteq A_{1}$ . It is then a direct consequence of the definition of the sets $A_n$ that if $A_n \subseteq A_{n+1}$ , then $A_{n+1} \subseteq A_{n+2}$ .

Now, let us prove the other sequence of inclusions. The inclusion $K_{2}+A_{n}+G_{1}\subseteq L(K_{2}+A_{n+1})+F_{1}$ is direct for any $n\geq 0$ . Suppose that $K_{2}+A_{n}+G_{k}\subseteq L^{k}(K_{2}+A_{n+k})+F_{k}$ for some $n \geq 0$ and some $k>0$ . Since $G_{k+1} = G_k + L^k(G_{1})$ , we get that

$$ \begin{align*} K_{2}+A_{n}+G_{k+1} = K_{2}+A_{n}+G_k + L^k(G_{1}) \subseteq L^{k}(K_{2}+A_{n+k}+G_1)+F_{k}. \end{align*} $$

By the initial case, we have that $K_{2}+A_{n+k}+G_1 \subseteq L(K_{2}+A_{n+k+1})+F_{1}$ . Using the equality $F_{k+1}=F_k + L^k(F_1)$ ,

$$ \begin{align*} L^{k}(K_{2}+A_{n+k}+G_1)+F_{k} & \subseteq L^{k+1}(K_{2}+A_{n+k+1})+L^k(F_1) +F_{k}\\ & =L^{k+1}(K_{2}+A_{n+k+1})+ F_{k+1}. \end{align*} $$

This completes the proof of the claim.

Now, we prove that the sequence of finite sets $(A_{n})_{n>0}$ is eventually stationary. Define the sequence $a_{n}=\Vert A_{n}\Vert $ . This sequence satisfies

$$ \begin{align*}a_{n+1}\leq \Vert L^{-1}\Vert a_{n} +\Vert L^{-1}(G_{1}+G_{1}-F_1)\Vert,\end{align*} $$

which implies that

$$ \begin{align*} a_{n} \leq a_{0}\cdot \Vert L^{-1}\Vert^{n} + \Vert L^{-1}(G_{1}+G_{1}-F_1)\Vert\dfrac{1-\Vert L^{-1}\Vert^{n}}{1-\Vert L^{-1}\Vert}.\end{align*} $$

Since $\Vert L^{-1}\Vert <1$ , the sequence $(a_{n})_{n\geq 0}$ is bounded. Therefore, the nested sequence $(A_n)_{n \geq 0}$ is eventually constant. Let $n \geq 0$ such that $A_n = A_m$ for all $m \geq n$ and set $A = A_n$ . By Claim 1, we have

(7) $$ \begin{align} \text{for all } k> 0, K_{2}+A+G_{k}\subseteq L^{k}(K_{2}+A)+F_{k}. \end{align} $$

To define a substitution $\tilde {\zeta }$ with support $G_{1}$ , we consider the set $\mathcal {B}=\mathcal {L}_{K_{2}+A}(X_{\zeta })$ as a new alphabet and we define the substitution $\tilde {\zeta }$ with support $G_{1}$ on the alphabet $\mathcal {B}$ as follows:

$$ \begin{align*}\text{for all } \boldsymbol{g}\in G_{1}, (\tilde{\zeta}(\texttt{w}))_{\boldsymbol{g}}=\zeta(\texttt{w})_{\boldsymbol{g}+K_{2}+A}.\end{align*} $$

Note that by equation (7), the substitution $\tilde {\zeta }$ is well defined. Using Claim 1 and the primitivity of $\zeta $ , it is straightforward to check that $\tilde {\zeta }$ is primitive. Let us now prove that $(X_{\zeta },S,\mathbb {Z}^{d})$ and $(X_{\tilde {\zeta }},S,\mathbb {Z}^{d})$ are topologically conjugate. Indeed, consider the factor map $\phi :X_{\zeta }\to \mathcal {B}^{\mathbb {Z}^d}$ induced by

$$ \begin{align*}\begin{array}{lll} \Phi: & \!\!\!\mathcal{L}_{K_{2}+A}(X_{\zeta})\!\!\!\! &\to \mathcal{B}\\ &\quad\, \texttt{w} &\mapsto \texttt{w}. \end{array}\end{align*} $$

Thus, for all $x\in X_{\zeta }$ and $\boldsymbol {n}\in \mathbb {Z}^{d}$ , we have that $\phi (x)_{\boldsymbol {n}}=\Phi (x|_{\boldsymbol {n}+K_{2}+A})$ . We prove that $\phi (\bar {x})$ is a fixed point of $\tilde {\zeta }$ . Set $\boldsymbol {n}\in \mathbb {Z}^{d}$ . There exists a unique $\boldsymbol {n}_{1}\in \mathbb {Z}^{d}$ and $\boldsymbol {g}\in G_{1}$ such that $\boldsymbol {n}=L(\boldsymbol {n}_{1})+\boldsymbol {g}$ . Note that

$$ \begin{align*} (\tilde{\zeta}(\phi(\bar{x})))_{\boldsymbol{n}} & = (\tilde{\zeta}(\phi(\bar{x})))_{L(\boldsymbol{n}_{1})+\boldsymbol{g}}\\ & = (\tilde{\zeta}(\phi(\bar{x}))_{\boldsymbol{n}_{1}})_{\boldsymbol{g}}\\ & = (\tilde{\zeta}(\Phi(\bar{x}|_{\boldsymbol{n}_{1}+K_{2}+A})))_{\boldsymbol{g}}\\ & = (\zeta(\bar{x}|_{\boldsymbol{n}_{1}+K_{2}+A}))_{\boldsymbol{g}+K_{2}+A}\\ & = (\zeta(\bar{x}))_{L(\boldsymbol{n}_{1})+\boldsymbol{g}+K_{2}+A}\\ & = (\zeta(\bar{x}))_{\boldsymbol{n}+K_{2}+A}\\ & = \bar{x}_{\boldsymbol{n}+K_{2}+A}\\ & = \Phi(\bar{x}|_{\boldsymbol{n}+K_{2}+A})\\ & = (\phi(\bar{x}))_{\boldsymbol{n}}, \end{align*} $$

so $\phi (\bar {x})\in X_{\tilde {\zeta }}$ is a fixed point of $\tilde {\zeta }$ . By the minimality of $\phi (X_\zeta )$ and $X_{\tilde {\zeta }}$ , we conclude that $\phi (X_\zeta ) = X_{\tilde {\zeta }}$ . Therefore, $\phi $ is a factor map from $X_\zeta $ to $X_{\tilde {\zeta }}$ . To prove that it is a conjugacy, we check that the factor map $\psi :X_{\tilde {\zeta }}\to \mathcal {A}^{\mathbb {Z}^d}$ induced by

$$ \begin{align*}\begin{array}{lll} \Psi: & \!\!\!\mathcal{L}_{K_{2}+A}(X_{\zeta}) \!\!\!\!& \to \mathcal{A}\\ &\quad\, \texttt{w} & \mapsto \texttt{w}_{\boldsymbol{0}} \end{array}\end{align*} $$

is its inverse map. Indeed, for any $\boldsymbol {n}\in \mathbb {Z}^{d}$ , we get that $\psi (\phi (\bar {x}))_{\boldsymbol {n}}=\Psi (\phi (\bar {x})_{\boldsymbol {n}})=\Psi (\bar {x}_{\boldsymbol {n}+K_{2}+A})=\bar {x}_{\boldsymbol {n}}$ , that is, $\psi (\phi (\bar {x}))=\bar {x}$ . The minimality of $(X_{\zeta },S,\mathbb {Z}^{d})$ implies that $\psi \circ \phi = {\mathrm {id}}_{X_{\zeta }}$ . Hence, $\phi $ , $\psi $ are invertible and $\phi ^{-1}=\psi $ . We conclude that $(X_{\zeta },S,\mathbb {Z}^{d})$ and $(X_{\tilde {\zeta }},S,\mathbb {Z}^{d})$ are topologically conjugate.

Observe that, by construction, the set $B=K_{2}+A$ only depends on $L,F_1$ , and $G_1$ , not on the combinatorial properties of $\zeta $ . For example, the set is enough to obtain a square substitution conjugate to a substitution defined with $L=2\cdot {\mathrm {id}}_{\mathbb {R}^{2}}$ and $F_{1}=\{(0,0),(1,0),(0,1),(-1,-1)\}$ .

5. Computability of the constant of recognizability

The recognizability property of substitutions is a combinatorial one that offers a form of invertibility, allowing the unique decomposition of points within the substitutive subshift. Recall that if $\zeta $ is a substitution with a fixed point $x\in X_{\zeta }$ , then $\zeta $ is recognizable on x if there exists some constant $R>0$ such that for all $\boldsymbol {i}, \boldsymbol {j}\in \mathbb {Z}^{d}$ ,

(8) $$ \begin{align} x|_{[B(L_{\zeta}(\boldsymbol{i}),R)\cap \mathbb{Z}^{d}]}=x|_{[B(\boldsymbol{j},R)\cap \mathbb{Z}^{d}]} \!\implies\! (\text{there exists } \boldsymbol{k}\in \mathbb{Z}^{d}) ((\boldsymbol{j}=L_{\zeta}(\boldsymbol{k}))\wedge (x_{\boldsymbol{i}}=x_{\boldsymbol{k}})). \end{align} $$

This property was initially established for aperiodic primitive substitutions by Mossé in [34]. This proof implies the existence of a natural sequence of refining (Kakutani–Rokhlin) partitions, which is a key tool when studying substitutive systems and more general $\mathcal {S}$ -adic systems. Subsequently, in [5], it was extended to cover non-primitive substitutions. Later, Durand and Leroy proved the computability of the recognizability length for one-dimensional primitive substitutions [19], which was then generalized by Beal, Perrin, and Restivo in [4] for the most general class of morphisms, including ones with erasable letters. In the multidimensional setting, Solomyak showed in [43] that aperiodic translationally finite self-affine tilings of $\mathbb {R}^{d}$ satisfy a recognizability property, referred to as the unique composition property. Furthermore, in [8], it was demonstrated that aperiodic symbolic factors of constant-shape substitutive subshifts also exhibit a recognizability property. In this section, we provide a computable upper bound for the constant of recognizability of aperiodic primitive constant-shape substitutions (Theorem 5.1). This upper bound can be expressed solely in terms of $|\mathcal {A}|,L_{\zeta }, \Vert F_{1}^{\zeta }\Vert $ and d. This result will be instrumental in the subsequent section, where we establish the decidability of the factorization problem between minimal substitutive subshifts. To achieve this, we will adapt some of the proofs presented in [8] to obtain computable bounds. We prove the following.

Theorem 5.1. Let $\zeta $ be an aperiodic primitive constant-shape substitution on an alphabet $\mathcal {A}$ , with expansion matrix $L_{\zeta }$ and support $F_{1}^{\zeta }$ admitting a fixed point $x\in X_{\zeta }$ . Define:

• • $t=-\log (\Vert L_{\zeta }\Vert )/\log (\Vert L_{\zeta }^{-1}\Vert )$ ;

• • $\bar {r}=\Vert L_{\zeta }^{-1}(F_{1}^{\zeta })\Vert /(1-\Vert L_{\zeta }^{-1}\Vert )$ ;

• • $a=\lceil (2\Vert F_{1}^{\zeta }\Vert +d)(2\Vert F_{1}\Vert + \Vert L_{\zeta }\Vert ^{|\mathcal {A}|^{2}+(|\mathcal {A}|+1)^{(6\bar {r})^{d}}})\rceil $ ;

• • $\bar {R}=\lceil \Vert L_{\zeta }^{-1}\Vert ^{|\mathcal {A}|-1}\cdot a\cdot 9^{t}\Vert L_{\zeta }\Vert ^{|t(|\mathcal {A}|-1)}\bar {r}^{t})+4\bar {r}\rceil $ ;

• • $\bar {n}=\lceil |\mathcal {A}|^{(2\bar {R}+6\bar {r})^{d}}\rceil $ .

Then, $\zeta $ is recognizable on x and the constant of recognizability is at most

$$ \begin{align*}2\Vert L_{\zeta}\Vert^{|\mathcal{A}|}[2\Vert F_{1}^{\zeta}\Vert + \Vert L_{\zeta}\Vert^{{\bar n}+|\mathcal{A}|}(2\Vert F_{1}^{\zeta}\Vert+7\bar{r}+\Vert L_{\zeta}^{-1}\Vert^{|\mathcal{A}|-1}\cdot a\cdot 9^{t}\Vert L_{\zeta}\Vert^{t(|\mathcal{A}|-1)})\bar{r}^{t}].\end{align*} $$

In B. Mossé’s original proof, a key argument for the proof of the recognizability property is the existence of an integer $p>0$ with the following property: for all $a,b\in \mathcal {A}$ , if $\zeta ^{n}(a)=\zeta ^{n}(b)$ for some $n\geq 0$ , then $\zeta ^{p}(a)=\zeta ^{p}(b)$ . This result was proved in [21]. Notably, this property holds true for $p=1$ when the substitution is injective on letters. The original proof concerns only one-dimensional morphisms. Nevertheless, it is possible to adapt the proof to the multidimensional context. The proof is left to the reader.

Theorem 5.2. [21, Theorem 3]

Let $\zeta $ be a constant-shape substitution. Then for any patterns $\texttt {u},\texttt {v}\in \mathcal {A}^{P}$ , for some $P\Subset \mathbb {Z}^{d}$ , we have that

$$ \begin{align*}\zeta^{|\mathcal{A}|-1}(\texttt{u})\neq \zeta^{|\mathcal{A}|-1}(\texttt{v}) \!\implies\! \text{for all } n,\ \zeta^{n}(\texttt{u})\neq \zeta^{n}(\texttt{v}).\end{align*} $$

We recall that $\zeta $ is primitive if and only if its incidence matrix $M_{\zeta }$ defined for all $a,b\in \mathcal {A}$ as $(M_{\zeta })_{a,b}=|\{\boldsymbol {f}\in F_{1}^{\zeta }\colon \zeta (a)_{\boldsymbol {f}}=b\}|$ is primitive, that is, there exists $k>0$ such that $M_{\zeta }^{k}$ only contains positive integer entries. The following is a well-known bound for this k.

Lemma 5.3. [46]

A non-negative $d\times d$ matrix M is primitive if, and only if, there is an integer $k\leq d^{2}-2d+2$ such that $M^{k}$ only contains positive entries.

Following the proof of the recognizability property of multidimensional substitutive subshifts in [8], we first study the computability of the growth of the repetitivity function. We recall that the repetitivity function of a minimal subshift is the map $R_{X}:\mathbb {R}_{+}\to \mathbb {R}_{+}$ defined for $r>0$ as the smallest radius such that every discrete ball $[B(\boldsymbol { n},R_{X}(r))\cap \mathbb {Z}^{d}]$ contains an occurrence of every pattern whose support has a diameter less than r.

Like in several proofs of §3, we will consider the set K of Proposition 2.3, the set $C_{L_{\zeta },F_{1}^{\zeta }}$ given by Proposition 2.5 with $A=\{\boldsymbol {0}\}$ and $F=F_{1}^{\zeta }+F_{1}^{\zeta }$ , and the set $B=[B(\boldsymbol {0},\bar {r})\cap \mathbb {Z}^{d}]$ , where $\bar {r} = \|L_{\zeta }^{-1}(F_1^{\zeta })\|/(1-\|L_{\zeta }^{-1}\|)$ . Recall that $B \subseteq L_{\zeta }(B)+F_1^{\zeta }$ (see equation (5)) and that K satisfies $\|K\| \leq \bar {r}$ (see Remark 2.6), and so is included in B.

Lemma 5.4. Let $\zeta $ be an aperiodic primitive constant-shape substitution. Define $t=-\log (\Vert L_{\zeta }\Vert )/\log (\Vert L_{\zeta }^{-1}\Vert )$ . Then,

$$ \begin{align*} R_{X_{\zeta}}(r) \leq (2 \|F_1^{\zeta}\|+ \|L_{\zeta}\|^{|\mathcal{A}|^{2}+(|\mathcal{A}|+1)^{(6\bar{r})^d}} (2 \|F_1^{\zeta}\|+d)) r^t. \end{align*} $$

Proof. Set $r>0$ . We will show that every pattern $\texttt {u} \in \mathcal {L}_{[B(\boldsymbol {0},r) \cap \mathbb {Z}^d]}(X_\zeta )$ occurs in every image $\zeta ^{m(r)}(a)$ , $a \in \mathcal {A}$ , for some $m(r)\in \mathbb {N}$ and then we give an upper bound on $m(r)$ , from which we deduce a bound on the repetitivity function.

Following the proof of Proposition 3.6, we know that for every pattern $\texttt {u}\in \mathcal {L}_{[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}(X_{\zeta })$ , there exists $\texttt {v}\in \mathcal {L}_{C_{L_{\zeta },F_{1}^{\zeta }}+B}(X_{\zeta })$ and $\boldsymbol {f}\in F_{n(r)}^{\zeta }$ such that $\texttt {u}=\zeta ^{n(r)}(\texttt {v})_{\boldsymbol {f}+[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}$ , where $n(r)=\lceil \log (r-\Vert L_{\zeta }^{-1}(F_{1}^{\zeta }))\Vert /\log (\Vert L_{\zeta }^{-1}\Vert )\rceil $ . Thus, consider $\texttt {v}\in \mathcal {L}_{C_{L_{\zeta },F_1^{\zeta }}+B}(X_{\zeta })$ and let $n\in \mathbb {N}$ denote the smallest positive integer such that $\texttt {v}\sqsubseteq \zeta ^{n}(a)$ for some $a\in \mathcal {A}$ (such an n exists by primitivity of the substitution).

Let us first prove that $n\leq (|\mathcal {A}|+1)^{|C_{L_{\zeta },F_{1}^{\zeta }}+B|}$ . Indeed, as $\texttt {v}_1 := \texttt {v}$ occurs in $\zeta ^{n}(a)$ , there exists $\boldsymbol {f}_{n} \in F_n$ such that $\zeta ^{n}(a)_{\boldsymbol {f}_{n}+C_{L,F_{1}}+B}=\texttt {v}_1$ . Writing $\boldsymbol {f}_{n}=L_{\zeta }(\boldsymbol {f}_{n-1})+\boldsymbol {f}_{1}$ , there exists a pattern $\texttt {v}_2$ with minimal support $S_2$ such that $\zeta ^{n-1}(a)_{\boldsymbol {f}_{n-1}+S_2} = \texttt {v}_2$ and $\texttt {v}_{1} = \zeta (\texttt {v}_{2})_{\boldsymbol {f}_{1}+C_{L_{\zeta },F_{1}^{\zeta }}+B}$ . Note that we have

$$ \begin{align*} C_{L_{\zeta},F_1^{\zeta}}+B+\boldsymbol{f}_1 \subseteq C_{L_{\zeta},F_1^{\zeta}}+L_{\zeta}(B)+F_1^{\zeta}+F_1^{\zeta} \subseteq L_{\zeta}(B+C_{L_{\zeta},F_1^{\zeta}})+F_1^{\zeta}, \end{align*} $$

so the support $S_2$ of $\texttt {v}_{2}$ satisfies $S_2 \subseteq B+C_{L,F_1}$ . Observe that since $\texttt {v}_1$ does not occur in $\zeta ^{n-1}(a)$ , we have that $\texttt {v}_2 \neq \texttt {v}_1$ . Using the same argument, we can find a pattern $\texttt {v}_3$ with minimal support $S_3$ in $\zeta ^{n-2}(a)$ such that $\texttt {v}_3$ occurs in $\zeta (v_2)$ , $S_3 \subseteq B+C_{L_{\zeta },F_1^{\zeta }}$ and $\texttt {v}_3 \notin \{\texttt {v}_1,\texttt {v}_2\}$ . Continuing this way, we inductively construct a sequence of pairwise distinct patterns $\texttt {v}_{1},\texttt {v}_{2},\ldots $ in $\bigcup _{S \subseteq C_{L_{\zeta },F_{1}^{\zeta }}+B}\mathcal {L}_{S}(X_{\zeta })$ , such that for any $j\geq 1$ , $\texttt {v}_{j}\sqsubseteq \zeta (\texttt {v}_{j+1})$ , and $\texttt {v}_{j}$ occurs in $\zeta ^{n-j+1}(a)$ but does not occur in $\zeta ^{n-j}(a)$ . Considering that there are at most $|\mathcal {A}|^{|S|}$ patterns in $\mathcal {L}_{S}(X_{\zeta })$ , we conclude that $n\leq (|\mathcal {A}|+1)^{|C_{L_{\zeta },F_{1}^{\zeta }}+B|}$ .

Now, by Lemma 5.3, for any pair of letters $a,b\in \mathcal {A}$ , we have that $a\sqsubseteq \zeta ^{|\mathcal {A}|^{2}}(b)$ . Hence, for any letter $a\in \mathcal {A}$ , any pattern $\texttt {v}\in \mathcal {L}_{C_{L_{\zeta },F_{1}^{\zeta }}+B}(X_{\zeta })$ occurs in $\zeta ^{|\mathcal {A}|^{2}+(|\mathcal {A}|+1)^{|C_{L_{\zeta },F_{1}^{\zeta }}+B|}}(a)$ .

Since for any $n>0$ , $L_{\zeta }^{n}(\mathbb {Z}^{d})$ is $d\Vert L_{\zeta }\Vert ^{n}$ -relatively dense, any ball of radius $d\Vert L_{\zeta }\Vert ^{n}+2\Vert F_{1}^{\zeta }\Vert \cdot \Vert L_{\zeta }\Vert ^{n}$ contains a set of the form $L_{\zeta }^{n}(\boldsymbol {m})+F_{n}^{\zeta }$ for some $\boldsymbol {m}\in \mathbb {Z}^{d}$ . This implies that any pattern of the form $\zeta ^{n}(a)$ , for some $a\in \mathcal {A}$ , occurs in any pattern in $\mathcal {L}_{[B(\boldsymbol {0}, \Vert L_{\zeta }\Vert ^{n}(d+2\Vert F_{1}^{\zeta }\Vert )\cap \mathbb {Z}^{d}]}(X_{\zeta })$ . In particular, for $N=|\mathcal {A}|^{2}+(|\mathcal {A}|+1)^{|C_{L_{\zeta },F_{1}^{\zeta }}+B|}$ , we conclude that any ball of radius $\|L_{\zeta }\|^N (2 \|F_1^{\zeta }\|+d)$ contains an occurrence of any pattern $\texttt {v}\in \mathcal {L}_{C_{L_{\zeta },F_1^{\zeta }}+B}(X_{\zeta })$ . Hence, by the first part of the proof, any ball of radius $\|L_{\zeta }\|^{n(r)} (2 \|F_1^{\zeta }\|+ \|L_{\zeta }\|^N (2 \|F_1^{\zeta }\|+d))$ contains an occurrence of any pattern $\texttt {u}\in \mathcal {L}_{[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}(X_{\zeta })$ .

To finish the proof, we deduce from equation (3) that $\|C_{L_{\zeta },F_1^{\zeta }}+B\| \leq 3 \bar {r}$ . Using classical upper bounds for the cardinality of the discrete balls $[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]$ , we have that $|C_{L_{\zeta },F_1^{\zeta }}+B|\leq (6 \bar {r})^{d}$ . With this new bound, we get that for any $r>0$ ,

$$ \begin{align*} R_{X_{\zeta}}(r) & \leq (2 \|F_1^{\zeta}\|+ \|L_{\zeta}\|^N (2 \|F_1^{\zeta}\|+d)) \Vert L\Vert^{\log(r)/\log(\Vert L^{-1}\Vert)}\\ & \leq (2 \|F_1^{\zeta}\|+ \|L_{\zeta}\|^{|\mathcal{A}|^{2}+(|\mathcal{A}|+1)^{(6\bar{r})^{d}}} (2 \|F_1^{\zeta}\|+d)) r^t.\\[-2.9pc] \end{align*} $$

As pointed out in [8], the growth of the repetitivity function has a direct consequence on the distance between two occurrences of a pattern in a point $x\in X_{\zeta }$ , called repulsion property. This is an analog to the k-power-free property of one-dimensional primitive substitutions. We add the proof for completeness.

Proposition 5.5. (Repulsion property)

Let $\zeta $ be an aperiodic primitive constant-shape substitution, $x\in X_{\zeta }$ , and set $t=-\log (\Vert L_{\zeta }\Vert )/\log (\Vert L_{\zeta }^{-1}\Vert )$ . Then, if a pattern $\texttt {p}\sqsubseteq x$ with $[B(\boldsymbol {s},r)\cap \mathbb {Z}^{d}]\subseteq {\mathrm {supp}}(\texttt {p})$ , for some $\boldsymbol {s}\in \mathbb {Z}^{d}$ and $r>0$ , has two occurrences $\boldsymbol {j}_{1}, \boldsymbol { j}_{2}\in \mathbb {Z}^{d}$ in x such that $r\geq R_{X_{\zeta }}(\Vert \boldsymbol {j}_{1}-\boldsymbol {j}_{2}\Vert )$ , then $\boldsymbol {j}_{1}$ is equal to $\boldsymbol {j}_{2}$ .

Proof. For any $\boldsymbol {k}\in \mathbb {Z}^{d}$ , we consider the pattern $\texttt {w}_{\boldsymbol {k}}=x|_{\boldsymbol {k}\cup (\boldsymbol {k}+\boldsymbol {j}_{2}-\boldsymbol {j}_{1})}$ . Note that $ {\mathrm {diam}}( {\mathrm {supp}}(\texttt {w}_{\boldsymbol { k}}))=\Vert \boldsymbol {j}_{2}-\boldsymbol {j}_{1}\Vert $ . Since $r\geq R_{X_{\zeta }}(\Vert \boldsymbol {j}_{2}-\boldsymbol {j}_{1}\Vert )$ , then the support of the pattern $\texttt {p}$ contains an occurrence in x of any pattern $\texttt {w}_{\boldsymbol {k}}$ . Since $\boldsymbol {j}_{1}$ is an occurrence of $\texttt {p}$ in x, we get that for any $\boldsymbol {k}\in \mathbb {Z}^{d}$ , there exists $\boldsymbol {n}_{\boldsymbol { k}}\in \mathbb {Z}^{d}$ such that $x_{\boldsymbol {j}_{1}+\boldsymbol {n}_{\boldsymbol {k}}+\boldsymbol {k}}=x_{\boldsymbol {k}}$ and $x_{\boldsymbol {j}_{1}+\boldsymbol {n}_{\boldsymbol {k}}+(\boldsymbol { j}_{2}-\boldsymbol {j}_{1}+\boldsymbol {k})}=x_{\boldsymbol {j}_{2}-\boldsymbol {j}_{1}+\boldsymbol {k}}$ , which implies that $x_{\boldsymbol {j}_{2}+\boldsymbol {n}_{\boldsymbol {k}}+\boldsymbol {k}}=x_{\boldsymbol {j}_{2}-\boldsymbol { j}_{1}+\boldsymbol {k}}$ . The fact that $\boldsymbol {j}_{2}$ is an occurrence of $\texttt {p}$ in x lets us conclude that for any $\boldsymbol {k}\in \mathbb {Z}^{d}$ , $x_{\boldsymbol {j}_{2}-\boldsymbol {j}_{1}+\boldsymbol {k}}$ is equal to $x_{\boldsymbol {k}}$ , that is, $\boldsymbol {j}_{2}-\boldsymbol {j}_{1}$ is a period of x. Since $\zeta $ is aperiodic, we conclude that $\boldsymbol {j}_{1}=\boldsymbol {j}_{2}$ (see Figure 7).

Figure 7 Illustration of a forbidden situation given by the repulsion property (Proposition 5.5).

Now, we proceed to give a computable upper bound for the constant of recognizability of constant-shape substitutions. As mentioned in [19], the proof of the recognizability property has two steps. Using the notation of equation 8, the first step is to show that $\boldsymbol {j}$ belongs to $L_{\zeta }(\mathbb {Z}^d)$ and the second one is to show that $x_{\boldsymbol {i}} = x_{\boldsymbol { k}}$ . Here, we adapt the proofs in [8].

Proposition 5.6. (First step of recognizability: positions of ‘cutting bars’)

Let $\zeta $ be an aperiodic primitive constant-shape substitution from an alphabet $\mathcal {A}$ with expansion matrix $L_{\zeta }$ and support $F_{1}^{\zeta }$ . Let $x\in X_{\zeta }$ be a fixed point of $\zeta $ . Consider the constants:

• • $t=-\log (\Vert L_{\zeta }\Vert )/\log (\Vert L_{\zeta }^{-1}\Vert )$ ;

• • $\bar {r}=\Vert L_{\zeta }^{-1}(F_{1}^{\zeta })\Vert /(1-\Vert L_{\zeta }^{-1}\Vert )$ ;

• • $\bar {R}=\lceil \Vert L_{\zeta }^{-1}\Vert ^{|\mathcal {A}|-1}\cdot R_{X_{\zeta }}(9\Vert L_{\zeta }\Vert ^{|\mathcal {A}|-1}\bar {r})+4\bar {r}\rceil $ ;

• • $\bar {n}=\lceil |\mathcal {A}|^{(2\bar {R}+6\bar {r})^{d}}\rceil $ .

Then, $R=\Vert L_{\zeta }\Vert ^{\bar {n}+|\mathcal {A}|}(\bar {R}+3\bar {r})+2\Vert L_{\zeta }\Vert ^{\bar {n}+|\mathcal {A}|}\cdot \Vert F_{1}^{\zeta }\Vert $ is such that for all $\boldsymbol {i}, \boldsymbol {j}\in \mathbb {Z}^{d}$ ,

$$ \begin{align*}x|_{L_{\zeta}(\boldsymbol{i})+[B(\boldsymbol{0},R)\cap \mathbb{Z}^{d}]}=x|_{\boldsymbol{j}+[B(\boldsymbol{0},R)\cap \mathbb{Z}^{d}]} \!\implies\! \boldsymbol{j}\in L_{\zeta}(\mathbb{Z}^{d}).\end{align*} $$

The proof of Proposition 5.6 is an adaptation of the proof of [8, Proposition 3.7], using some ideas in [19]. This bound is far from being sharp, but does not depend on the combinatorics of the substitution. The idea of the proof is to construct sequences of patterns $\zeta ^{n}(\texttt {w}_{n})$ , $\zeta ^{n}(\texttt {u}_{n})$ and $\zeta ^{n}(\texttt {v}_{n})$ around two points $\boldsymbol {i}_{n}\in L_{\zeta }(\mathbb {Z}^{d})$ and $\boldsymbol {j}_{n}\notin L_{\zeta }(\mathbb {Z}^{d})$ such that $\zeta ^{n}(\texttt {w}_{n})\sqsubseteq \zeta ^{n}(\texttt {u}_{n})\sqsubseteq \zeta ^{n}(\texttt {v}_{n})$ , where $ {\mathrm {supp}}(\texttt {w}_{n})$ , $ {\mathrm {supp}}(\texttt {u}_{n})$ , and $ {\mathrm {supp}}(\texttt {v}_{n})$ are fixed for every $n>0$ and big enough to ensure that if two occurrences of $\texttt {w}_{n}$ occur in $\texttt {u}_{n}$ , they must be the same. The constants given in Proposition 5.6 ensure that the arguments are true.

Proof. Using Proposition 2.5 with $A = \{\boldsymbol {0}\}$ and $F = F_1^{\zeta } - F_1^{\zeta }$ , there exists a finite set $D\subseteq \mathbb {Z}^{d}$ such that for every $n>0$ , $F_{n}^{\zeta }-F_{n}^{\zeta }\subseteq L_{\zeta }^{n}(D)+F_{n}^{\zeta }$ . Observe that, by item (4) of Proposition 2.5, we have that $\Vert D\Vert \leq 3\bar {r}$ . We prove the statement by contradiction. Assume the contrary. Then, for every $|\mathcal {A}|\leq n\leq \bar {n}+|\mathcal {A}|$ , there exist $\boldsymbol {i}_{n}\in L_{\zeta }(\mathbb {Z}^{d})$ and $\boldsymbol {j}_{n}\notin L_{\zeta }(\mathbb {Z}^{d})$ such that

$$ \begin{align*}x|_{\boldsymbol{i}_{n}+L_{\zeta}^{n}(D+[B(\boldsymbol{0},\bar{R})\cap \mathbb{Z}^{d}])+F_{n}^{\zeta}]}=x|_{\boldsymbol{j}_{n}+L_{\zeta}^{n}(D+[B(\boldsymbol{0},\bar{R})\cap \mathbb{Z}^{d}])+F_{n}^{\zeta}}.\end{align*} $$

For any $|\mathcal {A}|\leq n\leq |\mathcal {A}|+\bar {n}$ , we consider $\boldsymbol {a}_{n}\in \mathbb {Z}^{d}$ and $\boldsymbol {f}_{n}\in F_{n}^{\zeta }$ such that $\boldsymbol {i}_{n}=L_{\zeta }^{n}(\boldsymbol {a}_{n})+\boldsymbol { f}_{n}$ (see Figure 8). Note that, by definition of the set $D\Subset \mathbb {Z}^{d}$ , we have that

$$ \begin{align*}L_{\zeta}^{n}(\boldsymbol{a}_{n})+L_{\zeta}^{n}([B(\boldsymbol{0},\bar{R})\cap \mathbb{Z}^{d}])+F_{n}^{\zeta}\subseteq \boldsymbol{i}_{n}+L_{\zeta}^{n}(D+[B(\boldsymbol{0},\bar{R})\cap \mathbb{Z}^{d}])+F_{n}^{\zeta}.\end{align*} $$

Figure 8 Illustration of the pattern $\zeta ^{n}(\texttt {u}_{n})$ around the coordinates $L_{\zeta }^{n}(\boldsymbol {a}_{n})$ (black, left) and $\boldsymbol {j}_{n}-\boldsymbol {f}_{n}$ (blue, right).

Figure 9 Illustration of the patterns $\zeta ^{n}(\texttt {w}_{n})$ , $\zeta ^{n}(\texttt {u}_{n})$ , and $\zeta ^{n}(\texttt {v}_{n})$ around $\boldsymbol {j}_{n}-\boldsymbol {f}_{n}$ .

Let $\texttt {u}_{n}\in \mathcal {L}_{[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}(X_{\zeta })$ be such that (see Figure 8)

$$ \begin{align*}x|_{L_{\zeta}^{n}(\boldsymbol{a}_{n})+L_{\zeta}^{n}([B(\boldsymbol{0},\bar{R})\cap \mathbb{Z}^{d}])+F_{n}^{\zeta}}=\zeta^{n}(\texttt{u}_{n})=x|_{(\boldsymbol{j}_{n}-\boldsymbol{f}_{n})+L_{\zeta}^{n}([B(\boldsymbol{0},\bar{R})\cap \mathbb{Z}^{d}])+F_{n}^{\zeta}}.\end{align*} $$

Observe that $\boldsymbol {j}_{n}-\boldsymbol {f}_{n}$ is not necessarily in $L_{\zeta }^{n}(\mathbb {Z}^{d})$ , so we set $\boldsymbol {b}_{n}\in \mathbb {Z}^{d}$ and $\boldsymbol {g}_{n}\in F_{n}^{\zeta }$ such that $\boldsymbol { j}_{n}-\boldsymbol {f}_{n}=L_{\zeta }^{n}(\boldsymbol {b}_{n})+\boldsymbol {g}_{n}$ . Now, for any $n>0$ and $E\subseteq \mathbb {Z}^{d}$ , we define the following sets:

$$ \begin{align*} G_{n,E} & =\{\boldsymbol{n}\in \mathbb{Z}^{d}\colon (L_{\zeta}^{n}(\boldsymbol{n})+F_{n}^{\zeta})\cap (\boldsymbol{j}_{n}-\boldsymbol{f}_{n})+L_{\zeta}^{n}(E)+F_{n}^{\zeta}\neq \emptyset\};\\ H_{n,E} & = \{\boldsymbol{n}\in \mathbb{Z}^{d}\colon (L_{\zeta}^{n}(\boldsymbol{n})+F_{n}^{\zeta})\subseteq (\boldsymbol{j}_{n}-\boldsymbol{f}_{n})+L_{\zeta}^{n}(E)+F_{n}^{\zeta}\}. \end{align*} $$

By definition, we have for any $n>0$ and any $E\subseteq \mathbb {Z}^{d}$ that $H_{n,E}$ is included in $G_{n,E}$ . Since $x=\zeta (x)$ , there exist patterns $\texttt {v}_{n}\in \mathcal {L}_{G_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}-\boldsymbol {b}_{n}}(X_{\zeta })$ , $\texttt {w}_{n}\in \mathcal {L}_{H_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}-\boldsymbol {b}_{n}}(X_{\zeta })$ , with $L_{\zeta }^{n}(\boldsymbol {b}_{n})$ being an occurrence of $\zeta ^{n}(\texttt {v}_{n})$ and $\zeta ^{n}(\texttt {w}_{n})$ in x, such that $\zeta ^{n}(\texttt {w}_{n})$ occurs in $\zeta ^{n}(\texttt {u}_{n})$ and $\zeta ^{n}(\texttt {u}_{n})$ occurs in $\zeta ^{n}(\texttt {v}_{n})$ , as illustrated in Figure 9.

Claim 1. For any $n>0$ , $\boldsymbol {b}_{n}$ belongs to $H_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}$ , and $(G_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}-\boldsymbol {b}_{n})$ is a bounded set.

Proof of Claim 1

Note that $\boldsymbol {b}_{n}\in H_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}$ if and only if

$$ \begin{align*}F_{n}^{\zeta}-\boldsymbol{g}_{n}\subseteq L_{\zeta}^{n}([B(\boldsymbol{0},\bar{R})\cap \mathbb{Z}^{d}])+F_{n}^{\zeta},\end{align*} $$

which is true since $\bar {R}\geq \Vert D\Vert $ . Now, set $\boldsymbol {m}\in (G_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}-\boldsymbol {b}_{n})$ , that is, there exists $\boldsymbol {h}_{n}\in F_{n}^{\zeta }$ , $\boldsymbol {r}_{n}\in [B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]$ , and $\boldsymbol {l}_{n}\in F_{n}^{\zeta }$ such that

$$ \begin{align*}L_{\zeta}^{n}(\boldsymbol{m})+\boldsymbol{h}_{n}=L_{\zeta}^{n}(\boldsymbol{b}_{n})+\boldsymbol{g}_{n}+L_{\zeta}^{n}(\boldsymbol{r}_{n})+\boldsymbol{l}_{n},\end{align*} $$

that is, $\boldsymbol {m}-\boldsymbol {b}_{n}=\boldsymbol {r}_{n}+L_{\zeta }^{-n}(\boldsymbol {g}_{n}+\boldsymbol {l}_{n}-\boldsymbol {h}_{n})$ , which implies that $\Vert \boldsymbol {m}-\boldsymbol {b}_{n}\Vert \leq \bar {R}+\Vert L_{\zeta }^{-n}(\boldsymbol {g}_{n}+\boldsymbol {l}_{n}-\boldsymbol {h}_{n})\Vert $ . Since $\Vert L_{\zeta }^{-n}(\boldsymbol {g}_{n}+\boldsymbol {l}_{n}-\boldsymbol {h}_{n})\Vert \leq 3\bar {r}$ , we conclude that $\Vert \boldsymbol {m}-\boldsymbol {b}_{n}\Vert \leq \bar {R}+3\bar {r}$ .

Since $\Vert G_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}-\boldsymbol {b}_{n}\Vert \leq \bar {R}+3\bar {r}$ , as in the proof of Proposition 3.6, we have that $|\mathcal {L}_{G_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]-\boldsymbol {b}_{n}}}(X_{\zeta })|\leq |\mathcal {A}|^{(2\bar {R}+6\bar {r})^{d}}$ . Since $\bar {n}\geq |\mathcal {L}_{G_{n,[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]-\boldsymbol {b}_{n}}}(X_{\zeta })|$ , there are two indices $|\mathcal {A}|<n<m\leq \bar {n}+|\mathcal {A}|$ , some finite sets $G,H \Subset \mathbb {Z}^{d}$ such that

$$ \begin{align*} G=(G_{n,[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]}-\boldsymbol{b}_{n})=(G_{m,[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]}-\boldsymbol{b}_{m}),\\ H=(H_{n,[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]}-\boldsymbol{b}_{n})=(H_{m,[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]}-\boldsymbol{b}_{m}), \end{align*} $$

and some patterns $\texttt {u}\in \mathcal {L}_{[B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}]}(X_{\zeta }),\texttt {v}\in \mathcal {L}_{G}(X_{\zeta })$ and $\texttt {w}\in \mathcal {L}_{H}(X_{\zeta })$ such that $\texttt {u}=\texttt {u}_{n}=\texttt {u}_{m}$ , $\texttt {v}=\texttt {v}_{n}=\texttt {v}_{m}$ , and $\texttt {w}=\texttt {w}_{n}=\texttt {w}_{m}$ . Set

$$ \begin{align*}\texttt{a}_{n}=x|_{(\boldsymbol{j}_{n}-\boldsymbol{ f}_{n})+L_{\zeta}^{n}([B(\boldsymbol{0},\bar{R})\cap \mathbb{Z}^{d}])+F_{n}^{\zeta}\setminus(L_{\zeta}^{n}(\boldsymbol{b}_{n})+L_{\zeta}^{n}(H)+F_{n}^{\zeta})},\end{align*} $$

that is, $\texttt {a}_{n}$ is the pattern whose support is equal to $ {\mathrm {supp}}(\zeta ^{n}(\texttt {u}))\setminus {\mathrm {supp}}(\zeta ^{n}(\texttt {w}))$ , as illustrated in Figure 10.

Figure 10 Illustration of the patterns $\zeta ^{n}(\texttt {w})$ and $\texttt {a}_{n}$ around $(\boldsymbol {j}_{n}-\boldsymbol {f}_{n})$ .

Applying $\zeta ^{m-n}$ to $\zeta ^{n}(\texttt {u})$ , we obtain the patterns $\zeta ^{m}(\texttt {a}_{n})$ and $\zeta ^{m-n}(\zeta ^{n}(\texttt {w}))=\zeta ^{m}(\texttt {w})$ . Note that

If $\zeta ^{m-n}(\texttt {a}_{n})$ and $\texttt {a}_{m}$ are different, then the pattern $\zeta ^m(\texttt {u})$ contains two occurrences of $\zeta ^{m}(\texttt {w})$ . We will use the repulsion property (Proposition 5.5) to get the contradiction, that is, these two occurrences are the same. To do this, we need the following result.

Claim 2. For any $n>0$ and any $E\subseteq \mathbb {Z}^{d}$ , the set $G_{n,E}$ is included in $H_{n,E}+C_{L_{\zeta },F_{1}^{\zeta }}+C_{L_{\zeta }+F_{1}^{\zeta }}+D$ .

Proof of Claim 2

First, we prove that for any $n>0$ and $E\Subset \mathbb {Z}^{d}$ , we have that $G_{n,E}\subseteq H_{n,(E+C_{L_{\zeta },F_{1}^{\zeta }}+C_{L_{\zeta },F_{1}^{\zeta }})}+D$ . Indeed, set $\boldsymbol {m}\in G_{n,E}$ . Then, there exists $\boldsymbol {h}_{n}\in F_{n}^{\zeta }$ , $\boldsymbol {e}_{n}\in E$ , $\boldsymbol {l}_{n}\in F_{n}^{\zeta }$ such that $L_{\zeta }^{n}(\boldsymbol {m})+\boldsymbol {h}_{n}=L_{\zeta }^{n}(\boldsymbol {b}_{n})+\boldsymbol { g}_{n}+L_{\zeta }^{n}(\boldsymbol {e}_{n})+\boldsymbol {l}_{n}$ . Set $\boldsymbol {d}_{n}\in D$ such that $\boldsymbol {l}_{n}-\boldsymbol {h}_{n}+\boldsymbol {g}_{n}=L_{\zeta }^{n}(\boldsymbol {d}_{n})$ . Hence, $\boldsymbol {m}=\boldsymbol { b}_{n}+\boldsymbol {e}_{n}+\boldsymbol {d}_{n}$ . We prove that $\boldsymbol {m}-\boldsymbol {d}_{n}\in H_{n,E+C_{L_{\zeta },F_{1}^{\zeta }}+C_{L_{\zeta },F_{1}^{\zeta }}}$ .

Now, set $\boldsymbol {o}_{n}\in F_{n}^{\zeta }$ . Then,

$$ \begin{align*} L_{\zeta}^{n}(\boldsymbol{m}-\boldsymbol{d}_{n})+\boldsymbol{o}_{n} & =L_{\zeta}^{n}(\boldsymbol{m})+\boldsymbol{h}_{n}-L_{\zeta}^{n}(\boldsymbol{d}_{n})-\boldsymbol{h}_{n}+\boldsymbol{o}_{n}\\ & = L_{\zeta}^{n}(\boldsymbol{b}_{n})+\boldsymbol{g}_{n}+L_{\zeta}^{n}(\boldsymbol{e}_{n})+\boldsymbol{l}_{n}-L_{\zeta}^{n}(\boldsymbol{d}_{n})-\boldsymbol{h}_{n}+\boldsymbol{o}_{n}\\ & = L_{\zeta}^{n}(\boldsymbol{b}_{n})+L_{\zeta}^{n}(\boldsymbol{e}_{n})+\boldsymbol{o}_{n}. \end{align*} $$

Let $\boldsymbol {q}_{n}\in F_{n}^{\zeta }$ and $\boldsymbol {c}_{n}\in C_{L_{\zeta },F_{1}^{\zeta }}$ be such that $\boldsymbol {g}_{n}+\boldsymbol {q}_{n}=L_{\zeta }^{n}(\boldsymbol {c}_{n})$ . We get that $L_{\zeta }^{n}(\boldsymbol { m}-\boldsymbol {d}_{n})+\boldsymbol {o}_{n}=L_{\zeta }^{n}(\boldsymbol {b}_{n})+\boldsymbol {g}_{n}+L_{\zeta }^{n}(\boldsymbol {e}_{n}+\boldsymbol {c}_{n})+(\boldsymbol {o}_{n}+\boldsymbol {q}_{n})$ . Since $F_{n}^{\zeta }+\boldsymbol {q}_{n}\subseteq L_{\zeta }^{n}(C_{L_{\zeta },F_{1}^{\zeta }})+F_{n}^{\zeta }$ , we conclude that $\boldsymbol {m}\in H_{n,E+C_{L_{\zeta },F_{1}^{\zeta }}+C_{L_{\zeta },F_{1}^{\zeta }}}+D$ .

To finish the proof, we note that a straightforward computation shows that for any $n>0$ and $A,B\Subset \mathbb {Z}^{d}$ , we have that $H_{n,A+B}\subseteq H_{n,A}+B$ . We then conclude that $G_{n,E}\subseteq H_{n,E}+C_{L_{\zeta },F_{1}^{\zeta }}+C_{L_{\zeta },F_{1}^{\zeta }}+D$ .

By Theorem 5.2, these patterns come from two patterns $\texttt {w}_{1},\texttt {w}_{2}\in \mathcal {L}_{H}(X_{\zeta })$ such that $\zeta ^{|\mathcal {A}|-1}(\texttt {w}_{1})=\zeta ^{|\mathcal {A}|-1}(\texttt {w}_{2})=\zeta ^{|\mathcal {A}|-1}(\texttt {w})$ , occurring in $\zeta ^{|\mathcal {A}|-1}(\texttt {v})$ . Thanks to Claim 2 and the fact that $\Vert C_{L_{\zeta },F_{1}^{\zeta }}+C_{L_{\zeta },F_{1}^{\zeta }}+D\Vert \leq 9\bar {r}$ , the difference between these two occurrences is included in $L_{\zeta }^{|\mathcal {A}|-1}([B(\boldsymbol {0},9\bar {r})\cap \mathbb {Z}^{d}])$ , so the distance is smaller than $9\Vert L_{\zeta }\Vert ^{|\mathcal {A}|-1}\bar {r}$ .

Claim 3. For any $r>0$ and any $n>0$ , we have that $[B(\boldsymbol {0},r-3\bar {r})\cap \mathbb {Z}^{d}]\subseteq H_{n,[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}$ and $[L_{\zeta }^{n}(B(\boldsymbol {0},r))\cap \mathbb {Z}^{d}]\subseteq L_{\zeta }^{n}([B(\boldsymbol {0},r+\bar {r})\cap \mathbb {Z}^{d}])+F_{n}^{\zeta }$ .

Proof of Claim 3

Set $\boldsymbol {n}\in [B(\boldsymbol {0},r-3\bar {r})\cap \mathbb {Z}^{d}]$ and $\boldsymbol {h}_{n}, \boldsymbol {l}_{n}\in F_{n}^{\zeta }$ . Then, we write

$$ \begin{align*} L_{\zeta}^{n}(\boldsymbol{n})+\boldsymbol{h}_{n} & =(\boldsymbol{j}_{n}-\boldsymbol{f}_{n})+L_{\zeta}^{n}(\boldsymbol{r}_{n}-\boldsymbol{b}_{n})+\boldsymbol{l}_{n}\\ & = L_{\zeta}^{n}(\boldsymbol{r}_{n})+\boldsymbol{g}_{n}+\boldsymbol{l}_{n} \end{align*} $$

for some $\boldsymbol {r}_{n}\in \mathbb {Z}^{d}$ . We note that there exists $\boldsymbol {c}\in C_{L_{\zeta },F_{1}^{\zeta }}$ such that $L_{\zeta }^{n}(\boldsymbol {c})+\boldsymbol {h}_{n}=\boldsymbol {g}_{n}+\boldsymbol { l}_{n}$ and we conclude that $\boldsymbol {m}=\boldsymbol {r}_{n}+\boldsymbol {c}$ . Since $\Vert \boldsymbol {m}\Vert \leq r-3\bar {r}$ and $\Vert \boldsymbol {c}\Vert \leq 3\bar {r}$ , we conclude that $\boldsymbol {r}_{n}\leq r$ . Now we prove the second inclusion.

Set $\boldsymbol {n}\in L_{\zeta }^{n}(B(\boldsymbol {0},r))\cap \mathbb {Z}^{d}$ . Then, there exists $\boldsymbol {m}_{1}\in \mathbb {Z}^{d}$ and $\boldsymbol {f}\in F_{n}^{\zeta }$ such that $\boldsymbol {m}=L_{\zeta }^{n}(\boldsymbol { m}_{1})+\boldsymbol {f}$ , which implies that $\Vert \boldsymbol {m}_{1}+L_{\zeta }^{-n}(\boldsymbol {f})\Vert \leq r$ . We then get that

$$ \begin{align*}\Vert \boldsymbol{m}_{1}\Vert\leq r+\Vert L_{\zeta}^{-n}(\boldsymbol{f})\Vert \leq r+\bar{r}.\\[-34pt]\end{align*} $$

By Claim 3, we have that

$$ \begin{align*}&[L_{\zeta}^{|\mathcal{A}|-1}(B(\boldsymbol{0},\bar{R}-4{\bar{r}}))\cap \mathbb{Z}^{d}] \\&\quad\subseteq L_{\zeta}^{|\mathcal{A}|-1}([B(\boldsymbol{0},\bar{R}-3{\bar{r}})\cap \mathbb{Z}^{d}])+F_{|\mathcal{A}|-1}^{\zeta}\subseteq {\mathrm{supp}}(\zeta^{|\mathcal{A}|-1}(\texttt{w})),\end{align*} $$

so $ {\mathrm {supp}}(\zeta ^{|\mathcal {A}|-1}(\texttt {w}))$ contains a discrete ball of radius $(\bar {R}-4\bar {r})/\Vert L_{\zeta }^{-1}\Vert ^{|\mathcal {A}|-1}$ . By the repulsion property (Proposition 5.5), this is a contradiction. Indeed, by the choice of $\bar {R}$ , we note that

$$ \begin{align*} \dfrac{1}{\Vert L^{-1}\Vert^{|\mathcal{A}|-1}}(\bar{R}-4{\bar r})\geq \dfrac{1}{\Vert L^{-1}\Vert^{|\mathcal{A}|-1}}9^{t}(\Vert L_{\zeta}\Vert\cdot R_{X_{\zeta}}(9\Vert L_{\zeta}\Vert^{|\mathcal{A}|-1}\bar{r})), \end{align*} $$

so $\zeta ^{m-n}(\texttt {a}_{n})=\texttt {a}_{m}$ as illustrated in Figure 11.

Figure 11 Illustration of the patterns $\zeta ^{m-n}(\texttt {a}_{n})$ in $L_{\zeta }^{m-n}(\boldsymbol {j}_{n})$ .

To finish the proof, we note that since $\zeta ^{n}(\texttt {u})\sqsubseteq \zeta ^{n}(\texttt {v})$ , there exists $\boldsymbol {p}_{m}\in L_{\zeta }^{n}(\boldsymbol {b}_{m})+L_{\zeta }^{n}(G)+F_{n}^{\zeta }$ such that $x|_{\boldsymbol { p}_{m}+L_{\zeta }^{n}([B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}])+F_{n}^{\zeta }}=\zeta ^{n}(\texttt {u})$ , which implies that $x|_{L_{\zeta }^{m-n}(\boldsymbol {p}_{m})+L_{\zeta }^{m}([B(\boldsymbol { 0},\bar {R})\cap \mathbb {Z}^{d}])+F_{m}^{\zeta }}=\zeta ^{m}(\texttt {u})$ . Using the fact that $\zeta ^{m-n}(\texttt {a}_{n})=\texttt {a}_{m}$ , we get that $L_{\zeta }^{m-n}(\boldsymbol {p}_{m})+L_{\zeta }^{m}([B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}])+F_{m}^{\zeta }=(\boldsymbol {j}_{m}-\boldsymbol {f}_{m})+L_{\zeta }^{m}([B(\boldsymbol {0},\bar {R})\cap \mathbb {Z}^{d}])+F_{m}^{\zeta }$ , that is, $\boldsymbol {j}_{m}-\boldsymbol {f}_{m}=L_{\zeta }^{m-n}(\boldsymbol {p}_{m})\in L_{\zeta }^{m}(\mathbb {Z}^{d})$ . Since $\boldsymbol {i}_{m}, \boldsymbol {f}_{m}\in L_{\zeta }(\mathbb {Z}^{d})$ , we conclude that $\boldsymbol {j}_{m}\in L_{\zeta }(\mathbb {Z}^{d})$ .

In Proposition 5.6, we compute a constant such that we can recognize patterns of the form $\zeta (a)$ for $a\in \mathcal {A}$ . However, it does not give information on the letter from which the pattern $\zeta (a)$ arises. If the substitution is injective in letters, this result is enough to get a complete recognizability property. To finish the proof of Theorem 5.1, we need to deal with the case where the substitution is not injective. For this case, we prove the second step of the recognizability property.

Proposition 5.7. (Second step of recognizability: uniqueness of pre-images)

Let $\zeta $ be an aperiodic primitive substitution and $x\in X_{\zeta }$ be a fixed point of $\zeta $ . Consider $R_{|\mathcal {A}|}>0$ the constant of Proposition 5.6 associated with $\zeta ^{|\mathcal {A}|}$ , that is,

$$ \begin{align*}x|_{L^{|\mathcal{A}|}_{\zeta}(\boldsymbol{i})+[B(\boldsymbol{0},R_{|\mathcal{A}|})\cap \mathbb{Z}^{d}]}=x|_{\boldsymbol{j}+[B(\boldsymbol{0},R_{|\mathcal{A}|})\cap \mathbb{Z}^{d}]} \!\implies\! \boldsymbol{ j}\in L^{|\mathcal{A}|}_{\zeta}(\mathbb{Z}^{d}).\end{align*} $$

Consider also $R=R_{|\mathcal {A}|}+2\Vert F_{1}^{\zeta }\Vert \cdot \Vert L_{\zeta }\Vert ^{|\mathcal {A}|}$ . Then, for any $\boldsymbol {i},\boldsymbol {j}\in \mathbb {Z}^{d}$ ,

$$ \begin{align*}x|_{[B(L_{\zeta}(\boldsymbol{i}),R)\cap \mathbb{Z}^{d}]}=x|_{[B(L_{\zeta}(\boldsymbol{j}),R)\cap \mathbb{Z}^{d}]} \!\implies\! x_{\boldsymbol{i}}=x_{\boldsymbol{j}}.\end{align*} $$

Proof. Let $\boldsymbol {k}\in \mathbb {Z}^{d}$ and $\boldsymbol {f}=\sum \nolimits _{i=1}^{|\mathcal {A}|-1}L_{\zeta }^{i}(\boldsymbol {f}_{i})\in F_{|\mathcal {A}|}^{\zeta }$ be such that $L_{\zeta }^{|\mathcal {A}|}(\boldsymbol {k})+\boldsymbol { f}=L_{\zeta }(\boldsymbol {i})$ . Hence, we have that $L_{\zeta }^{|\mathcal {A}|-1}(\boldsymbol {k})+\sum \nolimits _{i=1}^{|\mathcal {A}|-1}L_{\zeta }^{i-1}(\boldsymbol {f}_{i})=\boldsymbol {i}$ . By the definition of $R_{|\mathcal {A}|}>0$ , we have the existence of $\boldsymbol {m}\in \mathbb {Z}^{d}$ such that $L_{\zeta }^{|\mathcal {A}|}(\boldsymbol {m})+\boldsymbol {f}=L_{\zeta }(\boldsymbol {j})$ , which implies that $\boldsymbol {j}= L_{\zeta }^{|\mathcal {A}|-1}(\boldsymbol { m})+\sum \nolimits _{i=1}^{|\mathcal {A}|-1}L_{\zeta }^{i-1}(\boldsymbol {f}_{i})$ . Note that, by the definition of $R>0$ , we get that $x|_{L_{\zeta }^{|\mathcal {A}|}(\boldsymbol { k})+F_{|\mathcal {A}|}^{\zeta }}=x|_{L_{\zeta }^{|\mathcal {A}|}(\boldsymbol {m})+F_{|\mathcal {A}|}^{\zeta }}$ . Hence, $\zeta ^{|\mathcal {A}|}(x_{\boldsymbol {k}})=\zeta ^{|\mathcal {A}|}(x_{\boldsymbol {m}})$ and by Theorem 5.2, we also have that $\zeta ^{|\mathcal {A}|-1}(x_{\boldsymbol {k}})=\zeta ^{|\mathcal {A}|-1}(x_{\boldsymbol {m}})$ . This implies that $x|_{L_{\zeta }^{|\mathcal {A}|-1}(\boldsymbol { k})+F_{|\mathcal {A}|-1}^{\zeta }}=x|_{L_{\zeta }^{|\mathcal {A}|-1}(\boldsymbol {m})+F_{|\mathcal {A}|-1}^{\zeta }}$ , which lets us conclude that $x_{\boldsymbol {i}}=x_{\boldsymbol {j}}$ .

Remark 5.8. We recall that if $R_{\zeta }$ is a constant of recognizability for the first step for $\zeta $ , then $2\Vert L_{\zeta }\Vert R_{\zeta }$ is a constant of recognizability for the first step for $\zeta ^{2}$ . Indeed, note that if

$$ \begin{align*}x|_{L_{\zeta}^{2}(\boldsymbol{i})+L_{\zeta}([B(\boldsymbol{0}),R_{\zeta}]\cap \mathbb{Z}^{d})+[B(\boldsymbol{0}),R_{\zeta}]\cap \mathbb{Z}^{d}}=x|_{\boldsymbol{m}+L_{\zeta}([B(\boldsymbol{0}),R_{\zeta}]\cap \mathbb{Z}^{d})+[B(\boldsymbol{0}),R_{\zeta}]\cap \mathbb{Z}^{d}},\end{align*} $$

then $\boldsymbol {m}\in L_{\zeta }^{2}(\mathbb {Z}^{d})$ . A straightforward induction shows that for any $n>0$ , $2\Vert L_{\zeta }\Vert ^{n}R_{\zeta }$ is a constant of recognizability for the first step for $\zeta ^{n}$ .

Proof of Theorem 5.1

Finally, to get an upper bound, we just need to make the computation. By Remark 5.8, we have that if $R_{\zeta }$ is given by Proposition 5.6 for $\zeta $ , then $2\Vert L_{\zeta }\Vert ^{|\mathcal {A}|}(R_{\zeta }+\Vert F_{1}^{\zeta }\Vert )$ is a constant of recognizability, for the second step, for $\zeta $ . By Proposition 5.6, we then get that $\zeta $ is recognizable on x and the constant of recognizability is at most

$$ \begin{align*}2\Vert L_{\zeta}\Vert^{|\mathcal{A}|}[2\Vert F_{1}^{\zeta}\Vert + \Vert L_{\zeta}\Vert^{{\bar n}+|\mathcal{A}|}(2\Vert F_{1}^{\zeta}\Vert+7\bar{r}+\Vert L_{\zeta}^{-1}\Vert^{|\mathcal{A}|-1}\cdot a\cdot 9^{t}\Vert L_{\zeta}\Vert^{t(|\mathcal{A}|-1)})\bar{r}^{t}].\end{align*} $$

6. Rigidity properties of topological factors between aperiodic minimal substitutive subshifts

In this section, we study factor maps between multidimensional substitutive subshifts. The main theorem (Theorem 6.2) shows that if $\zeta _{1},\zeta _{2}$ are two aperiodic substitutions with the same expansion map L and there exists a factor map $\pi :(X_{\zeta _{1}},S,\mathbb {Z}^{d})\to (X_{\zeta _{2}},S,\mathbb {Z}^{d})$ between two substitutive subshifts, then there exists another factor map $\phi :(X_{\zeta _{1}},S,\mathbb {Z}^{d})\to (X_{\zeta _{2}},S,\mathbb {Z}^{d})$ given by a local map of a computable bounded radius that only depends on the support and the constant of recognizability. We recall that, by Theorem 4.1, if two substitutions are defined with the same expansion matrix, we can assume, up to conjugacy, that they also share the same support. We then deduce the following consequences: every aperiodic minimal substitutive subshift is coalescent (Proposition 6.4) and the quotient group $ {\mathrm {Aut}}(X_{\zeta },S,\mathbb {Z}^{d})/\langle S\rangle $ is finite, extending the results in [8] for the whole class of aperiodic minimal substitutive subshifts given by constant-shape substitutions. Next, we prove the decidability of the factorization and the isomorphism problem between aperiodic minimal substitutive subshifts (Theorem 6.6 and Corollary 6.9). We finish this section proving that aperiodic minimal substitutive subshifts have finitely many aperiodic symbolic factors, up to conjugacy (Lemma 6.12) and providing an algorithm to obtain a list of the possible injective substitution factors of an aperiodic substitutive subshift.

6.1. Factor maps between substitutive subshifts

We prove a multidimensional analog of [20, Theorem 8.1] as follows. There exists a computable upper bound R such that any factor map between two aperiodic minimal substitutive subshifts is equal to a shift map composed with a sliding block code of radius less than R. This was first done in the measurable setting under some extra combinatorial assumptions for the substitutions (in particular, for bijective substitutions) in the one-dimensional case in [30] and in the multidimensional case in [8]. A similar result was also proved for factor maps between two minimal substitutive subshifts of constant-length and Pisot substitutions in [41]. This last result was extended in [20] for the whole class of aperiodic minimal substitutive subshifts. They also gave a computable bound for the radius of a factor map between two minimal substitutive subshifts. We prove a similar result of [20] for the multidimensional constant-shape case, where the expansion matrices of the constant-shape substitutions are the same. We start with the following property about factor maps between substitutive subshifts.

Proposition 6.1. Let $\zeta _{1},\zeta _{2}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L and the same support $F_{1}$ , and $\phi :(X_{\zeta _{1}},S,\mathbb {Z}^{d})\to (X_{\zeta _{2}},S,\mathbb {Z}^{d})$ be a factor map. Then, for any $n>0$ , there exists a unique $\boldsymbol {f}_n\in F_{n}$ such that if $x\in \zeta _{1}^n(X_{\zeta _{1}})$ , then $\phi (x)\in S^{-\boldsymbol {f}_{n}} \zeta _{2}^{n}(X_{\zeta _{2}})$ .

Proof. Set $x\in \zeta _{1}^{n}(X_{\zeta _{1}})$ . Then, there exists $\boldsymbol {f}_{n}(x)$ such that $\phi (x)\in S^{-\boldsymbol {f}_{n}} \zeta _{2}^{n}(X_{\zeta _{2}})$ . We prove that $\boldsymbol {f}_{n}(x)$ is constant on $\zeta _{1}^{n}(X_{\zeta _{1}})$ . Note that $S^{\boldsymbol {n}}x\in \zeta _{1}^{n}(X_{\zeta _{1}})$ if and only if $\boldsymbol {n}=L_{\zeta }^{n}(\boldsymbol {m})$ for some $\boldsymbol {m}\in \mathbb {Z}^{d}$ . Hence, $\phi (S^{L_{\zeta }^{n}(\boldsymbol {m})}(x))=S^{L_{\zeta }^{n}(\boldsymbol {m})}\phi (x)\in S^{-\boldsymbol {f}_{n}}\zeta _{2}^{n}(X_{\zeta _{2}})$ . Now, if $y\in \zeta _{1}^{n}(X_{\zeta _{1}})$ , we use the minimality of $(X_{\zeta },S,\mathbb {Z}^{d})$ to obtain a sequence $(S^{L_{\zeta }^{n}(\boldsymbol {m}_{p})}(x))_{p>0}$ converging to y. By continuity of $\phi $ , we conclude that $\phi (y)\in S^{-\boldsymbol {f}_{n}(x)}\phi (x)$ .

The following theorem states the rigidity properties that factor maps between substitutive subshifts with the same expansion map satisfy. As in the previous sections, we define ${\bar r}=\Vert L^{-1}(F_{1})\Vert /(1-\Vert L^{-1}\Vert )$ . Observe that in the proofs of the next results, we sometimes need to replace a substitution $\zeta $ by a power $\zeta ^n$ of itself. However, in the computations, this modification does not impact the bound $\bar {r}$ , that is, we do not have to replace $\bar {r}$ by $\Vert L^{-n}(F_{n})\Vert /(1-\Vert L^{-n}\Vert )$ .

Theorem 6.2. Let $\zeta _{1},\zeta _{2}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L and support $F_{1}$ . Suppose there exists a factor map $\phi :(X_{\zeta _{1}},S,\mathbb {Z}^{d})\to (X_{\zeta _{2}},S,\mathbb {Z}^{d})$ with radius r. Then, there exists $\boldsymbol {j}\in \mathbb {Z}^{d}$ and a factor map $\psi :(X_{\zeta _{1}},S,\mathbb {Z}^{d})\to (X_{\zeta _{2}},S,\mathbb {Z}^{d})$ such that $S^{\boldsymbol {j}}\phi =\psi $ , satisfying the following two properties.

1. (1) The factor map $\psi $ is a sliding block code of radius at most $2\bar {r}+R_{\zeta _{2}}+1$ , where $R_{\zeta _{2}}$ is a constant of recognizability for $\zeta _{2}$ .

2. (2) There exists an integer $n>0$ and $\boldsymbol {f}\in F_{n}$ such that $S^{\boldsymbol {f}}\psi \zeta _{1}^{n}=\zeta _{2}^{n}\psi $ .

The proof is inspired by [41], but contains more details, as in the works in [8, 20], allowing to express a bound on the radius of factor maps, that it is invariant under iteration of the substitutions. While V. Salo and I. T $\ddot {o}$ rm $\ddot {a}$ state explicit formulas on how the invariants of the substitution behave under iteration, as well as the lemma that gives the ultimate bound obtained in the case of a contracting affine map, they do not explicitly state a bound on the radius of factor maps. The key contribution of Durand and Leroy in [20] was to extend these results to the whole class of primitive substitutions. In particular, for the constant-length case, the arguments remain similar. We then use Theorem 6.2 to deduce some topological and combinatorial properties of aperiodic primitive constant-shape substitutions.

Proof. For any $n>0$ , we denote $\boldsymbol {f}_{n}(\phi )$ as the element of $F_n$ given by Proposition 6.1. We recall that the recognizability property implies that the substitution maps $\zeta _{1}^{n},\zeta _{2}^{n}$ are homeomorphisms from $X_{\zeta _{1}}$ to $\zeta _{1}^n(X_{\zeta _{1}})$ and from $X_{\zeta _{2}}$ to $\zeta _{2}^n(X_{\zeta _{2}})$ , respectively. Hence, for any $x\in X_{\zeta _{1}}$ , there exists a unique point $\phi _{n}(x)\in X_{\zeta _{2}}$ such that

(9) $$ \begin{align} S^{\boldsymbol{f}_{n}(\phi)}\phi \zeta_{1}^{n}(x)=\zeta_{2}^{n}(\phi_{n}(x)). \end{align} $$

Let us show that $\phi _n$ is also a factor map and that, for large enough n, it has a ‘small’ radius. The map $\phi _{n}$ is obviously continuous, so let us prove that it commutes with the shift. Take $\boldsymbol {m}\in \mathbb {Z}^{d}$ . We note that

$$ \begin{align*} \zeta_{2}^{n}(\phi_{n}(S^{\boldsymbol{m}}x)) & = S^{\boldsymbol{f}_{n}(\phi)}\phi\zeta_{1}^{n}(S^{\boldsymbol{m}}x)\\ & = S^{\boldsymbol{f}_{n}(\phi)}\phi S^{L^{n}(\boldsymbol{m})}\zeta_{1}^{n}(x)\\ & = S^{L^{n}(\boldsymbol{m})+\boldsymbol{f}_{n}(\phi)}\phi \zeta_{1}^{n}(x)\\ & = S^{L^{n}(\boldsymbol{m})}\zeta_{2}^{n}(\phi_{n}(x))\\ & = \zeta_{2}^{n}(S^{\boldsymbol{m}}\phi_{n}(x)). \end{align*} $$

The map $\zeta _2^n:X_{\zeta _2} \to \zeta _2^n(X_{\zeta _2})$ , being injective, proves that $\phi _{n}(S^{\boldsymbol {m}}x) = S^{\boldsymbol {m}}\phi _{n}(x)$ , so the map $\phi _{n}$ is a factor map between $(X_{\zeta _{1}},S,\mathbb {Z}^{d})$ and $(X_{\zeta _{2}},S,\mathbb {Z}^{d})$ .

Let us now show that equation (9) allows to bound the radius of $\phi _n$ for large enough n. Roughly, given $x|_{[B(\boldsymbol {0},R)\cap \mathbb {Z}^{d}]}$ , we first apply $\zeta _1^n$ to compute $\zeta _1^n(x)$ on some big support. Then we lose some information using $\phi $ and the shift $S^{\boldsymbol {f}_n}$ . Our aim is thus to find R such that, for large enough n, the remaining information is large enough to be ‘desubstituted’ by $\zeta _2^n$ .

Let $P_{n}\Subset \mathbb {Z}^{d}$ be such that if $x,y\in X_{\zeta _1}$ , then

(10) $$ \begin{align} x|_{P_{n}}=y|_{P_{n}} \!\implies\! \phi_{n}(x)_{\boldsymbol{0}}=\phi_{n}(y)_{\boldsymbol{0}}. \end{align} $$

By definition, we have that $\zeta _{1}^{n}(x)|_{L^{n}(P_{n})+F_{n}}$ is equal to $\zeta _{1}^{n}(y)|_{L^{n}(P_{n})+F_{n}}$ . We then obtain that

(11) $$ \begin{align} (S^{\boldsymbol{f}_{n}(\phi)}\phi\zeta_{1}^{n}(x))|_{(L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi)}=(S^{\boldsymbol{f}_{n}(\phi)}\phi\zeta_{1}^{n}(y))|_{(L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi)}, \end{align} $$

which implies that

$$ \begin{align*} \zeta_{2}^{n}(\phi_{n}(x))|_{(L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi)}=\zeta_{2}^{n}(\phi_{n}(y))|_{(L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi)}. \end{align*} $$

Let $R_{\zeta _{2}}$ be a constant of recognizability for $\zeta _{2}$ . By Proposition 5.7 and Remark 5.8, we get that $\phi _n(x)$ and $\phi _n(y)$ coincide on the support

$$ \begin{align*} [L^{-n}(((L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi))^{\circ \mathcal{R}_{n}})]\cap \mathbb{Z}^{d}, \end{align*} $$

where $\mathcal {R}_{n}=\sum \nolimits _{i=0}^{n-1}L^{i}([B(\boldsymbol {0},R_{\zeta _{2}})\cap \mathbb {Z}^{d}])$ . By equation (10), for $\phi _{n}$ to be a sliding block code induced by a $P_{n}$ -block map, we need that

$$ \begin{align*} \boldsymbol{0}\in [L^{-n}(((L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi))^{\circ \mathcal{R}_{n}})]\cap \mathbb{Z}^{d}. \end{align*} $$

We have that

(12) $$ \begin{align} \boldsymbol{0}\in [L^{-n}(((L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi))^{\circ \mathcal{R}_{n}})]\cap \mathbb{Z}^{d} & \Leftrightarrow \boldsymbol{0}\in ((L^{n}(P_{n})+F_{n})^{\circ r }-\boldsymbol{ f}_{n}(\phi))^{\circ \mathcal{R}_{n}}\notag\\ & \Leftrightarrow \mathcal{R}_{n} \subseteq (L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi)\notag\\ & \Leftrightarrow \boldsymbol{f}_{n}(\phi)+\mathcal{R}_{n} \subseteq (L^{n}(P_{n})+F_{n})^{\circ r}. \end{align} $$

Consider $R = 2\bar {r}+R_{\zeta _{2}}+1$ and let us prove that $P_n = [B(\boldsymbol {0},R)\cap \mathbb {Z}^{d}]$ satisfies equation (12) for large enough n. Indeed, for all $\boldsymbol {r}_n \in \mathcal {R}_n$ and all $\boldsymbol {r} \in [B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]$ , we can write $\boldsymbol {f}_n(\phi )+\boldsymbol {r}_n+\boldsymbol {r} = L^n(\boldsymbol {a})+\boldsymbol { g}_n$ for some $\boldsymbol {a} \in \mathbb {Z}^d$ and $\boldsymbol {g}_n \in F_n$ . We then get

(13) $$ \begin{align} \nonumber \|\boldsymbol{a}\| &\leq \|L^{-n}(\boldsymbol{f}_n(\phi)-\boldsymbol{g}_n+\boldsymbol{r}_n+\boldsymbol{r})\| \\ &\leq \|L^{-n}(\boldsymbol{f}_n(\phi))\|+\|L^{-n}(\boldsymbol{g}_n)\|+\|L^{-n}(\boldsymbol{r}_n)\|+\|L^{-n}(\boldsymbol{r})\|, \end{align} $$

and the fact that for n large enough, $\Vert L^{-1}\Vert ^{n+1}r\leq 1$ , we conclude that for any n large enough, $\Vert P_{n}\Vert \leq 2\bar {r}+R_{\zeta _{2}}+1$ .

As in [8, 30], we note that for any $n\geq 1$ , $\boldsymbol {f}_{n+1}(\phi )=\boldsymbol {f}_{n}(\phi )\ (\text {mod}\ L^{n}(\mathbb {Z}^{d}))$ . Hence, there exists $\boldsymbol {g}\in F_{1}$ such that $\boldsymbol {f}_{n+1}(\phi )=\boldsymbol {f}_{n}(\phi )+L^{n}(\boldsymbol {g})\ (\text {mod}\ L^{n+1}(\mathbb {Z}^{d}))$ . We note that $\boldsymbol {g}=\boldsymbol {f}_{1}(\phi _{n})$ . Indeed,

(14) $$ \begin{align} \nonumber S^{\boldsymbol{f}_{n+1}(\phi)}\phi \zeta_{1}^{n+1} & = \zeta_{2}^{n+1}(\phi_{n+1}), \\ \nonumber S^{\boldsymbol{f}_{n+1}(\phi)-\boldsymbol{f}_{n}}S^{\boldsymbol{f}_{n}(\phi)}\phi \zeta_{1}^{n}\zeta & = \zeta_{2}^{n+1}(\phi_{n+1}),\\ \nonumber S^{L^{n}(\boldsymbol{g})}\zeta_{2}^{n}\phi_{n}\zeta_{1} & = \zeta_{2}^{n+1}(\phi_{n+1}),\\ S^{\boldsymbol{g}}\phi_{n}\zeta_{1} & =\zeta_{2}(\phi_{n+1}). \end{align} $$

By definition of $\boldsymbol {g}$ , $\boldsymbol {f}_{1}(\phi _{n})$ , $\phi _{n+1}$ , and $(\phi _{n})_{1}$ , we conclude that $\boldsymbol {g}=\boldsymbol {f}_{1}(\phi _{n})$ and $(\phi _{n})_{1}=\phi _{n+1}$ . By recurrence, we conclude that for any $n,k\geq 0$ , $(\phi _{n})_{k}=\phi _{n+k}$ .

To finish the proof, observe that for fixed alphabets $\mathcal {A}$ and $\mathcal {B}$ , there exists a finite number of sliding block codes of radius $2\bar {r}+R_{\zeta _{2}}+1$ . Thus, there exist two different integers $m, k\geq 0$ such that $\phi _{m}=\phi _{m+k}$ .

Let $n\geq m$ be a multiple of k. Note that $(\phi _{n})_{k}=\phi _{n+k}=(\phi _{m+k})_{n-m}=(\phi _{m})_{n-m}=\phi _{n}$ . This implies that for all $r\in \mathbb {N}$ , $\phi _{n}$ is equal to $(\phi _{n})_{rk}$ . Since $\phi _{n}$ is equal to $\phi _{2n}$ , we denote $\psi =\phi _{n}$ and $\boldsymbol {f}=\boldsymbol {f}_{n}(\psi )$ . By definition of $\boldsymbol {f}$ , we have that $S^{\boldsymbol {f}}\psi \zeta _{1}^{n}=\zeta _{2}^{n}\psi $ .

Set $\boldsymbol {j}=\boldsymbol {f}_{n}(\phi )-\boldsymbol {f}$ , then

$$ \begin{align*}S^{\boldsymbol{j}}\phi\zeta_{1}^{n}=S^{\boldsymbol{f}_{n}(\phi)-\boldsymbol{f}}\phi\zeta_{1}^{n}=S^{-\boldsymbol{f}}\zeta_{2}^{n}\psi=\psi\zeta_{1}^{n},\end{align*} $$

which implies that $S^{\boldsymbol {j}}\phi $ and $\psi $ coincides on $\zeta _{1}^{n}(X_{\zeta _{1}})$ , and hence on the whole set $X_{\zeta _{1}}$ by minimality.

6.2. Consequences of Theorem 6.2

As a consequence of Theorem 6.2, we extend the results on the coalescence and the automorphism group of substitutive subshifts proved in [8]. Specifically, we get rid of the reducibility condition for constant-shape substitutions. We recall that a system is coalescent if any factor map between X and itself is invertible. This was first proved in [16] for one-dimensional linearly recurrent subshifts (in particular, aperiodic primitive substitutive subshifts). Multidimensional linearly recurrent substitutive subshifts (such as the self-similar ones) are also coalescent as a consequence of a result in [11]. For an aperiodic primitive constant-shape substitution, we denote $R_{\zeta }$ to be a constant of recognizability for $\zeta $ .

Since the set of sliding block codes $2\bar {r}+R_{\zeta }+1$ is finite, we will assume here (up to considering a power of $\zeta $ ) that if a factor map $\psi $ satisfies property (2) in Theorem 6.2, then it does so for $n=1$ , that is, there exists $\boldsymbol {p}\in F_{1}^{\zeta }$ such that $S^{\boldsymbol {p}}\psi \zeta =\zeta \psi $ .

6.2.1. Coalescence of substitutive subshifts

The coalescence of aperiodic substitutive subshifts was proved in [8] for reduced aperiodic primitive constant-shape substitutions. Here, we proved it for the whole class of aperiodic primitive constant-shape substitutions. As in [8], we use the notion of $\zeta $ -invariant orbits. An orbit $\mathcal {O}(x,\mathbb {Z}^{d})$ is called $\zeta $ -invariant if there exists $\boldsymbol {j}\in \mathbb {Z}^{d}$ such that $\zeta (x)=S^{\boldsymbol {j}}x$ , that is, the orbit is invariant under the action of $\zeta $ in $X_{\zeta }$ . Since for every $\boldsymbol {n}\in \mathbb {Z}^{d}$ we have that $\zeta \circ S^{\boldsymbol {n}}=S^{L_{\zeta }\boldsymbol {n}}\circ \zeta $ , the definition is independent of the choice of the point in the $\mathbb {Z}^{d}$ -orbit of x. As an example, the orbit of a fixed point of the substitution map is an example of an invariant orbit. We recall that in [8], it was proved that there exist finitely many invariant orbits.

Proposition 6.3. [8, Proposition 3.9]

Let $\zeta $ be an aperiodic primitive constant-shape substitution. Then, there exist finitely many $\zeta $ -invariant orbits in the substitutive subshift $X_{\zeta }$ . The bound is explicit and depends only on d, $|\mathcal {A}|$ , $\Vert L_{\zeta }^{-1}\Vert $ , $\Vert F_{1}^{\zeta }\Vert $ , and $\det (L_{\zeta }- {\mathrm {id}})$ .

We now prove that substitutive subshifts are coalescent.

Proposition 6.4. Let $\zeta $ be an aperiodic primitive constant-shape substitution. Then, the substitutive subshift $(X_{\zeta },S,\mathbb {Z}^{d})$ is coalescent.

Proof. Set $\phi \in {\mathrm {End}}(X_{\zeta },S,\mathbb {Z}^{d})$ . Theorem 6.2 ensures that there exists $\boldsymbol {j}\in \mathbb {Z}^{d}$ such that $S^{\boldsymbol {j}}\phi $ is equal to a sliding block code $\psi $ of a fixed radius satisfying $S^{\boldsymbol {p}}\psi \zeta =\zeta \psi $ for some $\boldsymbol {p}\in F_{1}^{\zeta }$ . Let $\bar {x}\in X_{\zeta }$ be in a $\zeta $ -invariant orbit, that is, there exists $\boldsymbol {j}\in \mathbb {Z}^{d}$ such that $\zeta (\bar {x})=S^{\boldsymbol {j}}\bar {x}$ . Note that

$$ \begin{align*}\zeta \psi(\bar{x}) = S^{\boldsymbol{p}}\psi\zeta(\bar{x})=S^{\boldsymbol{p}+\boldsymbol{j}}\psi(\bar{x}),\end{align*} $$

so, if the orbit of x is in a $\zeta $ -invariant orbit, then $\psi (x)$ is also in a $\zeta $ -invariant orbit. By Proposition 6.3, there exist finitely many $\zeta $ -invariant orbits, and hence for n large enough, we can find $x\in X_{\zeta }$ with x and $\psi ^{n}(x)$ being in the same orbit, that is, there exists $\boldsymbol {m}\in \mathbb {Z}^{d}$ such that $S^{\boldsymbol {m}}\psi ^{n}(x)=x$ . The minimality of $(X_{\zeta },S,\mathbb {Z}^{d})$ allows us to conclude that $\psi ^{n}=S^{-\boldsymbol {m}}$ . Hence, $\psi $ is invertible, which implies that $\phi $ is invertible.

6.2.2. The automorphism group of substitutive subshifts

The rigidity properties of the topological factors between substitutive subshifts also allow us to conclude that the group $ {\mathrm {Aut}}(X_{\zeta },S,\mathbb {Z}^{d})/\langle S\rangle $ is finite, since any element in $ {\mathrm {Aut}}(X_{\zeta },S,\mathbb {Z}^{d})$ can be represented as an automorphism with radius $2\bar {r}+R_{\zeta }+1$ .

Proposition 6.5. Let $(X_{\zeta },S,\mathbb {Z}^{d})$ be a substitutive subshift from an aperiodic primitive reduced constant-shape substitution $\zeta $ . Then, the quotient group $ {\mathrm {Aut}}(X_{\zeta },S,\mathbb {Z}^{d})/\langle S\rangle $ is finite. A bound for $| {\mathrm {Aut}}(X_{\zeta },S,\mathbb {Z}^{d})/\langle S \rangle |$ is given by an explicit formula depending only on d, $|\mathcal {A}|$ , $\Vert L_{\zeta }^{-1}\Vert $ , $\Vert F_{1}^{\zeta }\Vert $ .

We recall that this was proved in the one-dimensional case as a consequence of the works [12, 13, 15], where they proved that the automorphism group of a minimal subshift with non-superlinear complexity is virtually generated by the shift action.

6.2.3. Decidability of the factorization problem between aperiodic substitutive subshifts

In this section, we prove that the factorization problem is decidable for aperiodic substitutive subshifts, given by substitutions sharing the same expansion matrix (Theorem 6.6). This extends the one proved by Fagnot [22] and Durand and Leroy [20] in the one-dimensional constant-length case as follows.

Theorem 6.6. Let $\zeta _{1},\zeta _{2}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L. It is decidable to know whether there exists a factor map between $(X_{\zeta _{1}},S,\mathbb {Z}^{d})$ and $(X_{\zeta _{2}},S,\mathbb {Z}^{d})$ .

First, we note that, by Theorem 4.1, we may assume that the substitutions share the same support. Let $\zeta _{1}, \zeta _{2}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L and support $F_{1}$ .

Proposition 6.7. Let $\zeta _{1}:\mathcal {A} \to \mathcal {A}^{F_1},\zeta _{2}:\mathcal {B} \to \mathcal {B}^{F_1}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L and the same support $F_{1}$ . Let $\Phi :\mathcal {A}^{[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]} \to \mathcal {B}$ be a block map of radius r and let $\phi $ be the associated factor map from $\mathcal {A}^{\mathbb {Z}^d}$ to $\phi (\mathcal {A}^{\mathbb {Z}^d})$ . If there exists $\boldsymbol {f} \in \mathbb {Z}^d$ such that $S^{\boldsymbol {f}} \phi \zeta _1(x) = \zeta _2 \phi (x)$ for all $x \in X_{\zeta _1}$ , then $\phi $ is a factor map from $X_{\zeta _1}$ to $X_{\zeta _2}$ .

Proof. A straightforward induction shows that for all $n>0$ , there exists $\boldsymbol {f_n} \in \mathbb {Z}^d$ such that $S^{\boldsymbol {f}_n} \phi \zeta _1^n(x) = \zeta _2^n \phi (x)$ for all $x \in X_{\zeta _1}$ . Let $x \in X_{\zeta _1}$ be a fixed point of $\zeta _1$ . By minimality and using the Følner property, it suffices to show that any pattern of the form $\phi (x)_{\boldsymbol {f}_n+F_n}$ belongs to $\mathcal {L}(X_{\zeta _2})$ . Since x is a fixed point of $\zeta _1$ , we have that $\phi (x)_{F_n+\boldsymbol {f}_n} = (\zeta _2^n(\phi (x)))_{F_n} = \zeta _2^n(\phi (x)_{\boldsymbol {0}})$ , which concludes the proof.

Corollary 6.8. Let $\zeta _{1}:\mathcal {A} \to \mathcal {A}^{F_1},\zeta _{2}:\mathcal {B} \to \mathcal {B}^{F_1}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L and the same support $F_{1}$ . Let $r>0$ and $\Phi :\mathcal {A}^{[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]} \to \mathcal {B}$ be a block map of radius r and let $\phi $ be the associated factor map from $\mathcal {A}^{\mathbb {Z}^d}$ to $\phi (\mathcal {A}^{\mathbb {Z}^d})$ . For any $\boldsymbol {f} \in \mathbb {Z}^d$ , it is decidable whether $S^{\boldsymbol {f}} \phi \zeta _1(x) = \zeta _2 \phi (x)$ for all $x \in X_{\zeta _1}$ .

Proof. Note that

(15) $$ \begin{align} &S^{\boldsymbol{f}}\phi\zeta_{1}(x)=\zeta_{2}(\phi(x))\nonumber\\ &\quad \Leftrightarrow (\text{for all } \boldsymbol{n}\in \mathbb{Z}^{d})(\text{for all } \boldsymbol{g}\in F_{1}), \phi\zeta_{1}(x)_{L(\boldsymbol{n})+\boldsymbol{g}+\boldsymbol{f}} =\zeta_{2}(\phi(x))_{L(\boldsymbol{n})+\boldsymbol{g}}\notag\\ &\quad \Leftrightarrow (\text{for all } \boldsymbol{n}\in \mathbb{Z}^{d})(\text{for all } \boldsymbol{g}\in F_{1}), \phi\zeta_{1}(x)_{L(\boldsymbol{n})+\boldsymbol{g}+\boldsymbol{f}} =\zeta_{2}(\phi(x)_{\boldsymbol{n}})_{\boldsymbol{g}}\notag\\ &\quad \Leftrightarrow (\text{for all } \boldsymbol{n}\in \mathbb{Z}^{d})(\text{for all } \boldsymbol{g}\in F_{1}), \phi\zeta_{1}(x)_{L(\boldsymbol{n})+\boldsymbol{g}+\boldsymbol{f}} =\zeta_{2}(\Phi(x|_{\boldsymbol{n}+[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]}))_{\boldsymbol{g}}. \end{align} $$

Let $\boldsymbol {c}_{\boldsymbol {g}}\in C$ and $\boldsymbol {h}_{\boldsymbol {g}}\in F_{1}$ be such that $\boldsymbol {g}+\boldsymbol {f}=L(\boldsymbol {c}_{\boldsymbol {g}})+\boldsymbol {h}_{\boldsymbol {g}}$ , then equation (15) is equivalent to

(16) $$ \begin{align}&(\text{for all } \boldsymbol{n}\in \mathbb{Z}^{d})(\text{for all } \boldsymbol{g}\in F_{1}), \Phi(\zeta_{1}(x)|_{L(\boldsymbol{n})+L(\boldsymbol{c}_{\boldsymbol{g}})+\boldsymbol{h}_{\boldsymbol{g}}+[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]})\nonumber\\ &\quad=\zeta_{2}(\Phi(x|_{\boldsymbol{n}+[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]}))_{\boldsymbol{g}}. \end{align} $$

Using Proposition 2.5 with $A = [B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]$ and $F = F_1$ , we find a set $E \Subset \mathbb {Z}^{d}$ such that $\Vert E\Vert \leq \Vert L^{-1}\Vert r/(1-\Vert L^{-1}\Vert )+3\bar {r}$ and

$$ \begin{align*}F_1 + [B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]\subseteq L(E)+F_{1},\end{align*} $$

so we can rewrite equation (16) as

(17) $$ \begin{align}(\text{for all } \boldsymbol{n}\in \mathbb{Z}^{d})(\text{for all } \boldsymbol{g}\in F_{1})& , \Phi(\zeta_{1}(x)|_{L(\boldsymbol{n})+L(\boldsymbol{c}_{\boldsymbol{g}})+L(E)+F_{1}}) =\zeta_{2}(\Phi(x|_{\boldsymbol{n}+[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]}))_{\boldsymbol{g}}\notag\\ (\text{for all } \boldsymbol{n}\in \mathbb{Z}^{d})(\text{for all } \boldsymbol{g}\in F_{1})& , \Phi(\zeta_{1}(x|_{\boldsymbol{n}+\boldsymbol{c}_{\boldsymbol{g}}+E})) =\zeta_{2}(\Phi(x|_{\boldsymbol{n}+[B(\boldsymbol{0},r)\cap \mathbb{Z}^{d}]}))_{\boldsymbol{g}}. \end{align} $$

We note that $ {\mathrm {diam}}( {\mathrm {supp}}(x|_{\boldsymbol {n}+\boldsymbol {c}_{g}+E}))\leq 2 \Vert E\Vert \leq 2\Vert L^{-1}\Vert r/(1-\Vert L^{-1}\Vert )+6\bar {r}$ and $ {\mathrm {diam}}( {\mathrm {supp}}(x|_{\boldsymbol {n}+[B(\boldsymbol {0},R)\cap \mathbb {Z}^{d}]}))\leq 2r$ . Consider $\mathfrak {R}=\max \{2r,2\Vert L^{-1}\Vert r/(1-\Vert L^{-1}\Vert )+6\bar {r}\}$ . To test if a sliding block code satisfies equation (17), we consider any pattern $\texttt {w}\in \mathcal {L}(X_{\zeta _1})$ with support $[B(\boldsymbol {0},R_{X_{\zeta _1}}(\mathfrak {R}))\cap \mathbb {Z}^{d}]$ , where $R_{X_{\zeta _{1}}}(\cdot )$ denotes the repetitivity function of the substitutive subshift $X_{\zeta _{1}}$ . By Lemma 5.4, we note that this discrete ball contains an occurrence of any pattern of the form $x|_{\boldsymbol {n}+\boldsymbol {c}_{\boldsymbol {g}}+E}$ and $x|_{\boldsymbol {n}+[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]}$ for any $\boldsymbol {n}\in \mathbb {Z}^{d}$ and $\boldsymbol {g}\in F_{1}$ .

Proof of Theorem 6.6

Let $R_{\zeta _{2}}$ be a constant of recognizability for $\zeta _{2}$ . Using Theorem 6.2 and Proposition 6.7, there is a factor map from $X_{\zeta _1}$ to $X_{\zeta _2}$ if and only if there exist $n>0$ , $\boldsymbol {f} \in F_n$ and a factor map $\phi $ with radius $R=2\bar {r}+R_{\zeta _{2}}+1$ that satisfies $S^{\boldsymbol {f}}\phi \zeta _{1}^{n}(x)=\zeta _{2}^{n}\phi (x)$ for all $x \in X_{\zeta _1}$ .

We first show that if such a factor map exists, we can find another factor map $\psi $ with the same radius such that $S^{\boldsymbol {f}}\phi \zeta _{1}^{n}(x)=\zeta _{2}^{n}\phi (x)$ for all $x \in X_{\zeta _1}$ and for some $n \leq |\mathcal {B}|^{|\mathcal {A}|^{R}}$ . Indeed, equation (9) defines other factor maps $\phi _n$ that, by equation (13) for $n\geq \lfloor \log _{2}(R)\rfloor $ , also have radius R. We can thus find two indices such that $\phi _{n}=\phi _{m} = \psi $ and $m<n$ . By equation (14), the factor maps $\phi _n$ satisfy $S^{\boldsymbol {g}}\phi _{n}\zeta _{1} =\zeta _{2}(\phi _{n+1})$ for some $\boldsymbol {g} \in F_1$ . Hence, there exists $\boldsymbol {f} \in F_{n-m}$ such that $S^{\boldsymbol {f}}\psi \zeta _{1}^{n-m}(x)=\zeta _{2}^{n-m}\psi (x)$ for all $x \in X_{\zeta _1}$ .

Finally, for every $n \kern1.5pt{\leq}\kern1.5pt |\mathcal {B}|^{|\mathcal {A}|^{R}}$ , every $\boldsymbol {f} \kern1.5pt{\in}\kern1.5pt F_n$ , and every block map ${\Phi :\mathcal {A}^{[B(\mathbf {0},R)\cap \mathbb {Z}^{d}]} \kern1.5pt{\to}\kern1.5pt \mathcal {B}}$ , Corollary 6.8 allows us to decide whether that block map defines a factor map from $X_{\zeta _1}$ to $X_{\zeta _2}$ . Since there is only a finite number of possibilities, this completes the proof.

Using the fact that minimal substitutive subshifts from aperiodic primitive constant- shape substitutions are coalescent (Proposition 6.4), we can decide if two aperiodic primitive constant-shape substitutions with the same expansion matrix are conjugate.

Corollary 6.9. Let $\zeta _{1},\zeta _{2}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L. It is decidable to know whether $(X_{\zeta _{1}},S,\mathbb {Z}^{d})$ and $(X_{\zeta _{2}},S,\mathbb {Z}^{d})$ are topologically conjugate.

6.2.4. Aperiodic symbolic factors of substitutive subshifts

The radius of the sliding block codes given by Theorem 6.2 can be improved when the substitutions involved are injective on letters. Indeed, under the assumption of injectivity, we can deduce from equation (11) that, by injectivity of the substitution $\zeta _{2}$ , $\phi _{n}(x)$ and $\phi _{n}(y)$ coincide on the set $\{\boldsymbol {m}\in \mathbb {Z}^{d}\colon L^{n}(\boldsymbol { m})+F_{n}\subseteq (L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol {f}_{n}(\phi )\}$ . Moreover, if $\phi _{n}$ is given by a $P_{n}$ -local map, we need that

$$ \begin{align*} F_{n}\subseteq (L^{n}(P_{n})+F_{n})^{\circ r}-\boldsymbol{f}_{n}(\phi), \end{align*} $$

which is true if $F_{n}+F_{n}+[B(\boldsymbol {0},r)\cap \mathbb {Z}^{d}]\subseteq L^{n}(P_{n})+F_{n}$ . Proceeding as in the proof of Theorem 6.2, we get that $\phi _{n}$ has radius at most $3\bar {r}+1$ . As mentioned in Remark 2.6, this bound is independent of the choices of the powers $\zeta _{1}$ and $\zeta _{2}$ . We thus have the following result.

Corollary 6.10. Let $\zeta _{1},\zeta _{2}$ be two aperiodic primitive constant-shape substitutions with the same expansion matrix L and support $F_{1}$ , such that $\zeta _2$ is injective. If $\phi : X_{\zeta _1} \to X_{\zeta _2}$ is a factor map, then there is a factor map $\psi :X_{\zeta _1} \to X_{\zeta _2}$ with radius at most $3\bar {r}+1$ such that $\phi = S^{\boldsymbol {j}} \psi $ for some $\boldsymbol {j} \in \mathbb {Z}^d$ .

Now, as in [20], we prove that we can always assume that the aperiodic substitutions are injective on letters. Indeed, let $\zeta :\mathcal {A}\to \mathcal {A}^{F}$ be an aperiodic primitive constant-shape substitution and consider $\mathcal {B}\subseteq \mathcal {A}$ such that for any $a\in \mathcal {A}$ , there exists a unique $b\in \mathcal {B}$ satisfying $\zeta (a)=\zeta (b)$ . We define the map $\Phi :\mathcal {A}\to \mathcal {B}$ such that $\Phi (a)=b$ if and only if $\zeta (a)=\zeta (b)$ . Then, there exists a unique constant-shape substitution $\tilde {\zeta }:\mathcal {B}\to \mathcal {B}^{F}$ defined by $\tilde {\zeta }\circ \phi =\phi \circ \zeta $ . It is clear that $\tilde {\zeta }$ is primitive and $\Phi $ induces a topological factor from $(X_{\zeta },S,\mathbb {Z}^{d})$ to $(X_{\tilde {\zeta }},S,\mathbb {Z}^{d})$ denoted by $\phi $ . The substitution $\tilde {\zeta }$ defined this way is called the injectivization of $\zeta $ .

Proposition 6.11. [6]

Let $\zeta $ be an aperiodic primitive constant-shape substitution and $\tilde {\zeta }$ be its injectivization. Then, $(X_{\zeta },S,\mathbb {Z}^{d})$ and $(X_{\tilde {\zeta }},S,\mathbb {Z}^{d})$ are topologically conjugate.

Proof. Since $\phi $ is a factor map, we prove that it is one-to-one. Let $x,y\in X_{\zeta }$ be such that $\phi (x)=\phi (y)$ . Note that $\zeta (x)=\zeta (\phi (x))=\zeta (\phi (y))=\zeta (y)$ . The fact that $\zeta :X_{\zeta }\to \zeta (X_{\zeta })$ is a homeomorphism lets us conclude that $x=y$ .

By construction, $\tilde {\zeta }$ may not be injective on letters, so we proceed in the same way to obtain an injectivization of $\tilde {\zeta }$ (and of $\zeta $ ). Since in each step the cardinality of the alphabet is decreasing, we will obtain, in finite steps, an injective substitution $\overline {\zeta }$ such that $(X_{\zeta },S,\mathbb {Z}^{d})$ and $(X_{\overline {\zeta }},S,\mathbb {Z}^{d})$ are topologically conjugate.

Now, let $\zeta $ be an aperiodic primitive constant-shape substitution. From [8, Theorem 3.26], we know that any aperiodic symbolic factor of $(X_{\zeta },S,\mathbb {Z}^{d})$ is conjugate to an aperiodic primitive constant-shape substitution with the same expansion matrix and support of some power of $\zeta $ . This substitution may not be injective, but using Proposition 6.11, we can find an injective substitution which is conjugate to the symbolic factor. Then, thanks to Corollary 6.10, we only need to test finitely many sliding block codes, which are the ones of radius $3\bar {r}+1$ . In particular, we prove the following result, extending what is known [18] for linearly recurrent shifts (in particular, aperiodic primitive substitutions).

Lemma 6.12. Let $\zeta $ be an aperiodic primitive constant-shape substitution. The substitutive subshift $(X_{\zeta },S,\mathbb {Z}^{d})$ has finitely many aperiodic symbolic factors, up to conjugacy.

7. Future works and discussions

7.1. Listing the factors and decidability of the aperiodicity of multidimensional substitutive subshifts

Since substitutions are defined by finite objects, it is natural to ask about the decidability of some properties about them. Lemma 6.12 states that any aperiodic substitutive subshift $X_\zeta $ has finitely many aperiodic symbolic factors. Furthermore, from [8, Theorem 3.26] and Proposition 6.11, any such factor is conjugate to a substitutive subshift defined by an injective constant-shape substitution with the same support as $\zeta $ . Thus, we would like to give a list $\zeta _1,\ldots ,\zeta _k$ of injective constant-shape substitutions that define all aperiodic symbolic factors of $X_\zeta $ .

Corollary 6.10 allows to give a bound on the size of the alphabet of any injective constant-shape substitution that would define an aperiodic symbolic factor of $X_\zeta $ . Hence, we can produce a finite list of candidates. Furthermore, if we know that two substitutions from that list are aperiodic, then Theorem 6.2 allows us to decide whether they are conjugate. Therefore, positively answering the following question would allow us to list all possible aperiodic symbolic factors of $X_\zeta $ .

Question 7.1. Is it decidable whether a primitive constant-shape substitution is aperiodic?

7.2. Toward a Cobham’s theorem for constant-shape substitutions

In [22], it was proved that if $\zeta _{1}, \zeta _{2}$ are two one-dimensional aperiodic primitive constant-length substitutions and $(X_{\zeta _{2}},S,\mathbb {Z})$ is a symbolic factor of $(X_{\zeta _{1}},S,\mathbb {Z})$ , then their lengths have a common power (greater than 1), generalizing a well-known result proved by Cobham [9]. In the multidimensional framework, Theorem 4.1 and [17] imply that this still remains true when the expansion matrix is equal to a multiple of the identity, but there is no generalized version for all constant-shape substitutions, which raises the following question.

Question 7.2. Is there a version of Cobham’s theorem for constant-shape substitutions?

7.3. Connections with first-order logic theory

In the one-dimensional case, the decidability of the factorization problem between two constant-length substitutions was proved in [20] using automata theory and its connection with first-order logic. We describe the proof in the following. Let $k\geq 2$ . An infinite sequence is called k-automatic if there is a finite state automaton with output (we refer to [2] for definitions) that, reading the base-k representation of a natural number n, outputs the letter $x(n)$ .

Now, consider the first-order logical structure $\langle \mathbb {N},+,V_{k},=\rangle $ , where $V_{k}$ corresponds to k-valuation function $V_{k}:\mathbb {N}\to \mathbb {N}$ by $V_{k}(0)=1$ and

$$ \begin{align*}V_{k}(n)=\max\{p\colon q^{r}\ \text{divides}\ n\}.\end{align*} $$

A subset $E\subseteq \mathbb {N}$ is called k-definable if there exists a first-order formula $\phi $ in $\langle \mathbb {N},+,V_{k},=\rangle $ such that $E=\{n\in \mathbb {N}\colon \phi (n)\}$ . An infinite sequence $x\in \mathcal {A}^{\mathbb {N}}$ is called k-definable if for all $a\in \mathcal {A}$ , the set $\{n\colon x_{n}=a\}$ is k-definable.

Theorem 7.3. [7, 10] Let $\mathcal {A}$ be a finite alphabet and $k\geq 2$ . An infinite sequence $x\in \mathcal {A}^{\mathbb {N}}$ is k-automatic if and only if it is k-definable and if and only if it is the image under a letter-to-letter substitution of a fixed point of a substitution of constant length k.

Theorem 7.4. The theory $\langle \mathbb {N},+,V_{k},=\rangle $ is decidable, that is, for each closed formula expressed in this first-order logical structure, there is an algorithm deciding whether it is true or not.

Theorem 7.3 extends to multidimensionnal constant-shape substitutions for which the expansion matrix is proportional to the identity. Hence, in that case, the decidability of the factorization problem can be deduced by the Büchi–Bruyère theorem. In the general case, it is not clear that these tools can be applied. For an integer expansion matrix $L\in \mathcal {M}(d,\mathbb {Z})$ , we do not have the analogous notions of L-automaticity and of L-definability. This raises the following questions.

Question 7.5.

1. (1) Can we extend the notion of k-automaticity to the general case of integer expansion matrices? More precisely, can we define L-automatic sequences so that these sequences are exactly the image under a letter-to-letter substitution of a constant-shape substitution with expansion matrix L?

2. (2) Can we define a logical structure depending on L and a notion of L-definability to obtain an analog of the Büchi–Bruyère theorem for constant-shape substitutions?

3. (3) Assuming that the logical structure exists, is this theory decidable?

7.4. Topological Cantor factors of substitutive subshifts

In the one-dimensional case, the topological Cantor factors of aperiodic primitive substitutions are either expansive or equicontinuous [18]. This classification result is no longer true in the multidimensional framework ([8, Example 4.3] is an example of an aperiodic primitive constant-shape substitution with a Cantor factor which is neither expansive neither equicontinuous). Moreover, we only study the aperiodic topological factors of substitutive subshifts, leaving open the study of the topological factors with non-trivial periods. The following are open questions.

Question 7.6.

1. (1) Are the expansive factors of aperiodic substitutive subshifts also substitutive?

2. (2) Is there a classification theorem for topological Cantor factors of constant-shape substitutions?

3. (3) Do aperiodic primitive constant-shape substitutions have a finite number of aperiodic topological Cantor factors, up to conjugacy?