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)}$ .

Using the notion of invariance introduced by Weiss in [Reference Weiss45], 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.

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.

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)$ [Reference Frankl26, Reference Pin and Berge38]. It thus suffices to observe, using equation (3), that $N \leq (6r)^d$ .

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.

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}$ .

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.

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*} $$

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).

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.

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.

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}$ .

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})$ .

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}}$ .

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*} $$