Proof. Notice that $[p]$ is the disjoint union of all $[q]$ , where $q \in \Sigma ^{S_2}$ and $[q] \subset [p]$ . It follows that for any $z \in \Sigma ^{{\mathbb {Z}^d}}$ , we have if and only if there is a unique $q \in \Sigma ^{S_2}$ such that $[q] \subset [p]$ and . Letting F be the difference set of $x,y$ , we obtain

Exchanging the order of the sums yields the result.

Proof. Let F be the difference set of $(x,y)$ . A straightforward computation shows that the difference set of $(\sigma ^u(x),\sigma ^u(y))$ is $F_1 = F-u$ and the difference set of $(x\circ A, x \circ A)$ is $F_2 = A^{-1}(F)$ .

Let $S \subset {\mathbb {Z}^d}$ be a finite set and $p \in \Sigma ^S$ . For the first claim, we have

Thus, $ (\sigma ^u(x),\sigma ^u(y))$ is an indistinguishable asymptotic pair.

For the second claim, let $q \in \Sigma ^{A(S)}$ be the pattern given by $q_{As}=p_s$ for every $s \in S$ . We note that for any $v \in {\mathbb {Z}^d}$ , $\sigma ^v(x)\in [q]$ if and only if $\sigma ^{A^{-1}v}(x \circ A) \in [p]$ . This means that $v \in \mathsf {occ}_q(x)$ if and only if $A^{-1}(v) \in \mathsf {occ}_p(x \circ A)$ .

As $(x,y)$ is an indistinguishable asymptotic pair, there is a finitely supported permutation $\pi $ of ${\mathbb {Z}^d}$ so that $\mathsf {occ}_q(x) = \pi (\mathsf {occ}_q(y))$ . Then $\pi ' = A \circ \pi \circ A^{-1}$ is a finitely supported permutation of ${\mathbb {Z}^d}$ so that $\mathsf {occ}_p(x\circ A)= \pi '(\mathsf {occ}_p(y\circ A))$ . We conclude that $\Delta _p(x\circ A,y\circ A)=0$ and thus they are indistinguishable.

Proof. Let F be the difference set of $x,y$ and $D \subset {\mathbb {Z}^d}$ , $\Phi \colon \Sigma _1^D \to \Sigma _2$ be respectively the set and block code which define $\phi $ . If $u \notin F-D$ , then $\sigma ^{u}(x)|_D = \sigma ^{u}(y)|_D$ and thus $\phi (x)_{u} = \phi (y)_{u}$ . As $F-D$ is finite, it follows that $\phi (x),\phi (y)$ are asymptotic.

Let $S\subset {\mathbb {Z}^d}$ be finite and $p\colon S\to \Sigma _2$ be a pattern. Let $\phi ^{-1}(p) \subset (\Sigma _1)^{D+S}$ be the set of patterns q with support $D+S$ so that for every $s \in S$ , $\Phi ((q_{d+s})_{d \in D}) = p_s$ . It follows that $\phi ^{-1}([p]) = \bigcup _{q \in \phi ^{-1}(p)}[q]$ .

Let $W \subset {\mathbb {Z}^d}$ be a finite set which is large enough such that $W \supseteq F\cup (D+F)$ . We have

$$ \begin{align*} \#\{u \in W-S \mid \sigma^u(\phi(x))\in[p]\} &= \sum_{q \in \phi^{-1}(p)}\#\{u\in W-S \mid \sigma^u(x)\in[q]\}\\ &= \sum_{q \in \phi^{-1}(p)}\#\{u\in W-S \mid \sigma^u(y)\in[q]\}\\ &= \#\{u\in W-S \mid \sigma^u(\phi(y))\in[p]\}. \end{align*} $$

As $W \supseteq F$ , we conclude that $\Delta _p(\phi (x), \phi (y))=0$ and therefore $(\phi (x), \phi (y))$ is an indistinguishable asymptotic pair.

Proof. Let $p \in \Sigma ^S$ be a pattern. As $(x_n,y_n)_{n \in \mathbb {N}}$ converges in the asymptotic relation to $(x,y)$ , there exists a finite set $F \subset {\mathbb {Z}^d}$ and $N_1 \in \mathbb {N}$ so that $x_n|_{{\mathbb {Z}^d} \setminus F} = y_n|_{{\mathbb {Z}^d} \setminus F}$ for every $n \geq N_1$ . In particular, we have that the difference sets of $(x,y)$ and $(x_n,y_n)$ for $n \geq N_1$ are contained in F. It suffices thus to show that

$$ \begin{align*} \# \{ \mathsf{occ}_p(x) \cap (F-S)\} = \#\{ \mathsf{occ}_p(y) \cap (F-S)\}. \end{align*} $$

As $(x_n)_{n\in \mathbb {N}}$ converges to x and $(y_n)_{n \in \mathbb {N}}$ converges to y, there exists $N_2 \in \mathbb {N}$ so that $x_n|_{F-S+S} = x|_{F-S+S}$ and $y_n|_{F-S+S} = y|_{F-S+S}$ for all $n \geq N_2$ . Thus, for $n \geq N_2$ and every $v\in F-S$ , we have that $\sigma ^{v}(x)|_S = \sigma ^{v}(x_n)|_S$ and $\sigma ^{v}(y)|_S = \sigma ^{v}(y_n)|_S$ . From this, we obtain that $\mathsf {occ}_p(x) \cap (F-S) = \mathsf {occ}_p(x_n) \cap (F-S)$ and $\mathsf {occ}_p(y) \cap (F-S) = \mathsf {occ}_p(y_n) \cap (F-S)$ for every $n \geq N_2$ .

Let $N = \max \{N_1,N_2\}$ and let $n \geq N$ . As $n \geq N_1$ , we have that $(x_n,y_n)$ is an indistinguishable asymptotic pair whose difference set is contained in F, it follows that $\# \{ \mathsf {occ}_p(x_n) \cap (F-S)\} = \#\{ \mathsf {occ}_p(y_n) \cap (F-S)\}.$ As $n \geq N_2$ , we obtain $\# \{ \mathsf {occ}_p(x) \cap (F-S)\} = \#\{ \mathsf {occ}_p(y) \cap (F-S)\}.$ As this argument holds for every pattern p, we conclude that $(x,y)$ is indistinguishable.

Proof. If x is not recurrent, there is a finite $S \subset {\mathbb {Z}^d}$ and $p \in \mathcal {L}_S(x)$ such that $\mathsf {occ}_p(x)$ is finite. As $\Delta _p(x,y)=0$ , it follows that $\mathsf {occ}_p(y)$ is also finite.

Let $(S_n)_{n \in \mathbb {N}}$ be an increasing sequence of finite subsets of ${\mathbb {Z}^d}$ such that $S_0 = S$ and $\bigcup _{n \in \mathbb {N}}S_n = {\mathbb {Z}^d}$ , and let $q_n = x|_{S_n}$ . As $x \in [q_n]$ and $\Delta _{q_n}(x,y)=0$ , there exists $u_n \in {\mathbb {Z}^d}$ so that $\sigma ^{u_n}(y) \in [q_n]$ . Furthermore, as $q_n|_S = p$ , it follows that $\sigma ^{u_n}(y) \in [p]$ and thus $u_n \in \mathsf {occ}_p(y)$ . As $\mathsf {occ}_p(y)$ is finite, there exists $v \in \mathsf {occ}_p(y)$ , and a subsequence such that $u_{n(k)} = v$ and thus $\sigma ^{v}(y) \in [q_{n(k)}]$ for every $k \in \mathbb {N}$ . As $\bigcap _{n \in \mathbb {N}}[q_n] = \bigcap _{k \in \mathbb {N}}[q_{n(k)}] = \{x\}$ , we deduce that $\sigma ^{v}(y) = x$ .

Proof. (1) Notice that

$$ \begin{align*} m^{\ell,r}(w) &= \#E^{\ell,r}(w) -\#E^\ell(w) -\#E^r(w) +1\\ &= \#\textrm{edges} -\#\textrm{vertices} +1. \end{align*} $$

In each connected component, we have that the number of edges is at least the number of vertices minus $1$ . (2) If $m^{\ell ,r}(w)=1-c$ , it implies that $\#\textrm {edges} -\#\textrm {vertices}=-1$ in each connected component. Therefore, each connected component is a tree and we deduce that the extension graph $E^{\ell ,r}(w)$ is acyclic. If $m^{\ell ,r}(w)>1-c$ , it implies there is a connected component in which $\#\textrm {edges} -\#\textrm {vertices}>-1$ . That connected component must contain a cycle. Thus, the extension graph $E^{\ell ,r}(w)$ is not acyclic. Part (3) is an immediate consequence of part (1). Part (4) is an immediate consequence of part (2).

Proof. For $\mathtt {i} \in \{\mathtt {0},\mathtt {1},\ldots ,d\}$ , let $g_{\mathtt {i}} = i_x - i_y$ , where $i_x,i_y$ are the unique positions in F so that $x_{i_x} = \mathtt {i}$ and $y_{i_y} = \mathtt {i}$ . Let $\mathcal {G}^{x-y} = \{g_{\mathtt {0}},\ldots ,g_d\}$ , $\mathcal {G}^{y-x} = - \mathcal {G}^{x-y}$ , and $\mathcal {G} = \mathcal {G}^{x-y} \cup \mathcal {G}^{y-x}$ .

We claim that the collection $\mathcal {G} = \mathcal {G}^{x-y} \cup \mathcal {G}^{y-x}$ generates $\mathbb {Z}^d$ as a monoid. Indeed, the flip condition ensures that every position in F occurs exactly once as an $i_x$ (and exactly once as an $i_y$ ). Moreover, for every $\mathtt {i} \in \{\mathtt {0},\mathtt {1},\ldots ,d\}$ , $g_{\mathtt {i}} = i_x - i_y \neq 0$ . As $\mathtt {0}_x = 0$ , using the previous properties, we can suitably add elements from $\mathcal {G}^{x-y}$ to produce all canonical vectors $\{e_1,\ldots ,e_d\}$ . Similarly, adding elements from $\mathcal {G}^{y-x}$ , we can produce $\{-e_1,\ldots ,-e_d\}$ . This provides a set which generates $\mathbb {Z}^d$ as a monoid.

For $m \in \mathbb {Z}^d$ , let $ \left \lVert {m} \right \rVert _{\mathcal {G}}$ be the word metric generated by $\mathcal {G}$ , that is, the least number $\ell $ so that m can be written as a sum of $\ell $ elements of $\mathcal {G}$ ( $0$ can be written as a sum of zero elements). Denote by $d_{\mathcal {G}}(m,m') = \left \lVert {m-m'} \right \rVert _{\mathcal {G}}$ and for a set $K \subset \mathbb {Z}^d$ , let $d_{\mathcal {G}}(m,K) = \min _{k \in K} d_{\mathcal {G}}(m,k)$ .

We just show that $\mathcal {L}_S(x)\subset \{\sigma ^{n}(x)|_{S}\colon n\in F-S\}$ , as the other case is analogous. Let $p \in \mathcal {L}_S(x)$ . There exists $n\in \mathbb {Z}^d$ such that $\sigma ^{n}(x)\in [p]$ . Choose n as above such that it minimizes $d_{\mathcal {G}}(n,F-S)$ . We claim that $d_{\mathcal {G}}(n,F-S) = 0$ . If this were not the case, there is ${f}\in F$ and ${s} \in S$ so that $d_{\mathcal {G}}(n,F-S) = d_{\mathcal {G}}(n,{f}-{s}) = \left \lVert {n - ({f}-{s})} \right \rVert _{\mathcal {G}} \geq 1$ .

By definition, we can write $n - ({f}-{s}) = \sum _{j = 1}^{d_{\mathcal {G}}(n,F-S)} {h}_j$ with each ${h}_j \in \mathcal {G}$ . Consider ${h}_1$ . There are two cases.

1. (1) If ${h}_1 \in \mathcal {G}^{x-y}$ , then ${h}_1 = g_i$ for some $0 \leq i \leq d$ . Consider the support $S' = \{ i_x \} \cup (n + S)$ and let $q = x|_{S'}$ . By definition, $x \in [q]$ and as $x,y$ are indistinguishable, there must exist $k \in F-S'$ so that $\sigma ^{k}(y) \in [q]$ and thus $\sigma ^{k+n}(y) \in [p]$ . There are again two cases.

   1. (a) If $k + n \in F-S$ , then as $x,y$ are indistinguishable, there must exist $n' \in F-S$ so that $\sigma ^{n'}(x) \in [p]$ . This contradicts the choice of n.

   2. (b) If $k + n \notin F-S$ , then necessarily $k \in F-\{i_x\}$ . We obtain that there is ${f}^* \in F$ so that $k = {f}^*-i_x$ . As $\sigma ^{k}(y)_{i_x} = y_{{f}^*-i_x + i_x} = \mathtt {i}$ , it follows by the flip condition that ${f}^* = i_y$ and so $k = i_y - i_x = -g_{i} = -{h}_1$ . We deduce that $\sigma ^{ n - {h}_1 }(y) \in [p]$ . As $k + n = n - {h}_1 \notin F-S$ and $x,y$ are asymptotic, we have that $\sigma ^{ n - {h}_1 }(x) \in [p]$ and that

      $$ \begin{align*} {d_{\mathcal{G}}(n-{h}_1,F-S)} &\leq \left\lVert { n - {h}_1 - {f}-{s} } \right\rVert _{\mathcal{G}}\\ &= \left\lVert { n - {f}-{s} } \right\rVert _{\mathcal{G}}-1 = {d_{\mathcal{G}}(n,F-S)}-1.\end{align*} $$
      Letting $n'\hspace{-1pt} =\hspace{-1pt} n\hspace{-1.5pt}-\hspace{-1.5pt}{h}_1$ , we have $\sigma ^{n'}(x)\hspace{-1pt}\in\hspace{-1pt} [p]$ and $d_{\mathcal {G}}(n',F\hspace{-1.5pt}-\hspace{-1.5pt}S)\hspace{-1pt} \leq\hspace{-1pt} d_{\mathcal {G}} (n,F\hspace{-1.5pt}-\hspace{-1.5pt}S)\hspace{-1pt}-\hspace{-1pt}1$ , contradicting the choice of n.

2. (2) If ${h}_1 \in \mathcal {G}^{y-x}$ , then ${h}_1 = -g_i$ for some $0 \leq i \leq d$ . The argument is analogous except that now, we consider $S' = \{ i_y \} \cup (n + S)$ and $q = y|_{S'}$ .

We conclude that $d_{\mathcal {G}}(n,F-S) = 0$ and thus $n \in F-S$ .

Proof. Let $P_1 = \{(a,f(a))\mid a\in A\}$ and $P_2 = \{(\pi (a),f(a))\mid a\in A\}$ . It is clear that $P_1$ and A have the same number of elements, it suffices thus to show that for every $b \in B$ , there is $a \in A$ such that $(\pi (a),f(a))\in P_2\setminus P_1$ and $f(a)=b$ .

Indeed, fix $b \in B$ and let $Q = \{ a \in A : f(a) = b\}$ . Clearly, $Q \neq \varnothing $ as f is surjective. Consider the directed graph $G = (Q,E)$ , where $(q,r)\in E$ if and only if $\pi (q) =r$ . Notice that Q does not contain a cycle due to $\pi $ being cyclic on U and $A \neq U$ ; therefore, there is $\bar {q} \in Q$ such that $\pi (\bar {q})\notin Q$ . Then we have $(\pi (\bar {q}),f(\bar {q}))\in P_2 \setminus P_1$ and $f(\bar {q})=b$ .

Proof. We do the proof of the inequality by induction on the cardinality of S. If $S=\{a\}$ is a singleton, the inequality holds since $\mathcal {L}_{\{a\}}(x) = \mathcal {L}_{\{a\}}(y) = \{\mathtt {0},\mathtt {1},\ldots ,d\}$ and thus

$$ \begin{align*} \#(\mathcal{L}_{\{a\}}(x) \cup \mathcal{L}_{\{a\}}(y)) = d+1 = \#F = \#(F-\{a\}). \end{align*} $$

Proceeding by induction, we assume that $\#\mathcal {L}_S(x,y)\geq \#(F-S)$ holds for some finite connected subset $S\subset {\mathbb {Z}^d}$ and we want to show it for $S\cup \{a\}$ for some $a\in {\mathbb {Z}^d}\setminus S$ such that $S\cup \{a\}$ is connected.

Let

$$ \begin{align*} G = (F-(S\cup\{a\})) \setminus (F-S) = (F-a) \setminus (F-S) \end{align*} $$

be the set of vectors $m \in {\mathbb {Z}^d}$ such that $m+(S\cup \{a\})$ intersects F without $m+S$ intersecting F. Since $S\cup \{a\}$ is connected, G is a strict subset of $F-a$ .

Let $f\colon G\to \mathcal {L}_{S}(x)$ be the map defined by $f(m) =\sigma ^{m}(x)|_{S}$ , and $g\colon G\to \{\mathtt {0},\mathtt {1},\ldots ,d\}$ be the map defined by $g(m) = (\sigma ^{m}(x))_{a} = x_{m +a}$ for every $m \in G$ . Notice that if $m\hspace{-0.75pt}\in\hspace{-0.75pt} G$ , then $f(m)\hspace{-0.75pt}=\hspace{-0.75pt}\sigma ^{m}(y)|_{S}$ and $f(G)\hspace{-0.75pt}=\hspace{-0.75pt}\{\sigma ^m(x)|_S\colon m\hspace{-0.75pt}\in\hspace{-0.75pt} G\}\hspace{-0.75pt} =\hspace{-0.75pt}\{\sigma ^m(y)|_S\colon m\hspace{-0.75pt}\in\hspace{-0.75pt} G\}$ .

Putting together the flip condition and that $G+a$ is a strict subset of F, it follows that g is injective and its image is a strict subset of the alphabet $\{\mathtt {0},\mathtt {1},\ldots ,d\}$ . Also notice that the flip condition implies that $y_{m+a}=(g(m)-1)\bmod (d+1)$ .

Since the asymptotic pair $(x,y)$ satisfies the flip condition, we have that $f(G)$ is a subset of patterns that are special at position a. This provides a lower bound for the pattern complexity. More precisely, because of the flip condition, for every $m\in G$ , we have that $\sigma ^{m}(x)|_{S\cup \{a\}}$ and $\sigma ^{m}(y)|_{S\cup \{a\}}$ are two distinct extensions to the support $S\cup \{a\}$ of the pattern $\sigma ^{m}(x)|_{S}=\sigma ^{m}(y)|_{S}$ . Therefore, we have the inclusion

$$ \begin{align*} & \bigcup_{w\in f(G)} \{u\in\mathcal{L}_{S\cup\{a\}}(x,y)\colon u|_{S}=w\}\\ &\qquad \supseteq \{\sigma^{m}(x)|_{S\cup\{a\}}\colon m\in G\} \cup \{\sigma^{m}(y)|_{S\cup\{a\}}\colon m\in G\}. \end{align*} $$

The union on the left is disjoint; therefore, taking the cardinality of both sides, we obtain

$$ \begin{align*} &\sum_{w\in f(G)} \#E^a(w)\\ &\qquad\geq \# (\{\sigma^{m}(x)|_{S\cup\{a\}}\colon m\in G\} \cup \{\sigma^{m}(y)|_{S\cup\{a\}}\colon m\in G\})\\ &\qquad= \#(\{(g(m),f(m))\colon m\in G\} \cup \{(g(m)-1 \bmod(d+1),f(m))\colon m\in G\})\\ &\qquad= \#(\{(s,fg^{-1}(s))\colon s \in g(G)\} \cup \{(s-1 \bmod(d+1),fg^{-1}(s))\colon s\in g(G)\})\\ &\qquad\geq \# g(G) + \# f(G) = \#G + \#f(G). \end{align*} $$

In the penultimate line, we use that g is injective and thus $g^{-1} \colon g(G)\to G$ is a bijection. In particular, this implies that $fg^{-1}\colon g(G) \to f(G)$ is surjective. As $g(G)$ is a strict subset of the alphabet $\{\mathtt {0},\mathtt {1},\ldots ,d\}$ , we obtain the last line using Lemma 3.3.

Since every pattern in $\mathcal {L}_{S}(x,y)$ can be extended in at least one way to position a, we have $\#E^a(w)\geq 1$ for every $w\in \mathcal {L}_{S}(x,y)$ . Also since $f(G) \subset \mathcal {L}_{S}(x,y)$ , we have

$$ \begin{align*} \#\mathcal{L}_{S\cup\{a\}}(x,y) -\#\mathcal{L}_{S}(x,y) &= \sum_{w\in\mathcal{L}_{S}(x,y)} (\#E^a(w)-1) \geq \sum_{w\in f(G)} (\#E^a(w)-1)\\ &= \sum_{w\in f(G)} \#E^a(w) - \#f(G)\\ &\geq (\#G + \#f(G)) - \#f(G) = \#G. \end{align*} $$

Therefore,

$$ \begin{align*} \#\mathcal{L}_{S\cup\{a\}}(x,y) \geq \#\mathcal{L}_{S}(x,y) + \# G \geq \#(F-S) + \#G = \#(F-(S\cup\{a\})).\\[-36pt] \end{align*} $$

Proof. Let us show item (1). Fix $(a,b) \in \Gamma _{\ell }(w)$ and let $w'$ be the pattern with support $S\cup \{\ell ,r\}$ such that $w'|_{S}=w$ , $w^{\prime }_{\ell }=a$ , and $w^{\prime }_{r}=b$ . As $(a,b) \in \Gamma _{\ell }(w)$ , there is $t \in {\mathbb {Z}^d}$ such that $t+\ell \in F$ , $(t+(S\cup \{r\})) \cap F =\varnothing $ , and $\sigma ^{t}(x)\in [w']$ . On the one hand, as $x,y$ are asymptotic with difference set F, we have $x|_{t+(S\cup \{r\})} = y|_{t+(S\cup \{r\})}$ and thus $y_{t+r} = x_{t+r}=b$ . On the other hand, by the flip condition, $y_{t+\ell } = x_{t+\ell }-1 \bmod { d+1} = a^*$ , which means we have both $(a,b)$ and $(a^*,b)$ in $E^{\ell ,r}(w)$ . Furthermore, if we let $w"$ be the pattern with support $S\cup \{\ell \}$ such that $w"|_{S}=w$ and $w^{\prime \prime }_{\ell }=a^*$ , condition (IND) implies that $w"$ must occur in x intersecting the difference set. It follows that there is $b'$ such that $(a^*,b') \in \Gamma _{\ell }(w)\cup \Gamma _{\star }(w)$ . The second claim is analogous to the first one.

Next we shall provide a bound on the number of edges of $\Gamma _{\ell }(w)$ and $\Gamma _{r}(w)$ . Indeed, notice that by condition (IND), we have that

$$ \begin{align*}\#\Gamma_{\ell}(w) \leq \#\{t\in {\mathbb{Z}^d} : t + \ell \in F \mbox{ and } (t + (S \cup \{r\})) \cap F = \varnothing)\}.\end{align*} $$

As $S\cup \{\ell ,r\}$ is connected, there is $u\in {\mathbb {Z}^d}$ with $ \left \lVert {u} \right \rVert _1 \leq 1$ such that $\ell +u \in S \cup \{r\}$ . In particular, there is at least one $t \in {\mathbb {Z}^d}$ such that $t+\ell \in F$ and $t+\ell +u \in F$ . As $\# F = d+1$ , we deduce that $\# \Gamma _{\ell }(w)\leq d$ . Analogously, we have $\# \Gamma _{r}(w)\leq d$ .

Let us finally prove item (3). Let $a \in E^{\ell }(w)$ and consider again the pattern $w'$ with support $S\cup \{\ell \}$ such that $w'|_{S}=w$ and $w^{\prime }_{\ell }=a$ . By condition (IND), it must occur intersecting F and thus we have that a must occur in some edge in $\Gamma _{\ell }(w)\cup \Gamma _{\star }(w)$ . If it occurs in an edge of $\Gamma _{\star }(w)$ , we are done, otherwise by item (1), we know it is connected to $a^*= a-1 \bmod {d+1}$ and that $a^*$ occurs in some edge in $\Gamma _{\ell }(w)\cup \Gamma _{\star }(w)$ . If said edge is in $\Gamma _{\star }(w)$ , we are done, otherwise we iterate the process, as $\# \Gamma _{\ell }(w) \leq d$ , it follows that we eventually end up in a vertex which belongs to an edge in $\Gamma _{\star }(w)$ . After an analogous argument for $b \in E^r(w)$ , we obtain that every connected component of $E^{\ell ,r}(w)$ must contain an edge of $\Gamma _{\star }(w)$ , and thus the number of connected components is bounded by $\#\Gamma _{\star }(w)$ .

Proof. In the case where $S = \varnothing $ , as $\ell \neq r$ , there is at most a unique $t \in {\mathbb {Z}^d}$ such that $t+\ell , t+r \in F$ , and thus $\# \Gamma _{\star }(w) \leq 1$ . If $S \neq \varnothing $ , condition (IND) implies that there is a unique $t \in {\mathbb {Z}^d}$ such that $(t+S)\cap F \neq \varnothing $ and $\sigma ^{t}(x)\in [w]$ . The second possibility, namely, that there is $t'$ such that $(t'+S)\cap F = \varnothing $ and $t'+\ell ,t'+r \in F$ can only occur if w is evil; therefore, we obtain that $\# \Gamma _{\star }(w) \leq 1$ if w is non-evil and $\# \Gamma _{\star }(w) \leq 2$ if w is evil.

By Lemma 3.6, we obtain that the number of connected components of $E^{\ell ,r}(w)$ is bounded by $1$ if w is non-evil, and by $2$ if it is evil. Using Lemma 3.1, we obtain that $m^{\ell ,r}(w) \geq 0$ whenever w is non-evil, and $m^{\ell ,r}(w)\geq -1$ if w is evil.

Proof. Let us first deal with the case $S\neq \varnothing $ . Summing each term in the definition of multiplicity, we obtain

$$ \begin{align*} &\sum_{w\in\mathcal{L}_S(x,y)} m^{\ell,r}(w)\\ &\qquad= \sum_{w\in\mathcal{L}_S(x,y)} \#E^{\ell,r}(w) -\sum_{w\in\mathcal{L}_S(x,y)} \#E^{\ell}(w) -\sum_{w\in\mathcal{L}_S(x,y)} \#E^{r}(w) +\sum_{w\in\mathcal{L}_S(x,y)} 1\\ &\qquad= \#\mathcal{L}_{S\cup\{\ell,r\}}(x,y) -\#\mathcal{L}_{S\cup\{\ell\}}(x,y) -\#\mathcal{L}_{S\cup\{r\}}(x,y) +\#\mathcal{L}_S(x,y). \end{align*} $$

On the one hand, we have the hypothesis that $\#\mathcal {L}_{S \cup \{\ell ,r\}}(x,y) = \#(F-(S \cup \{\ell ,r\}))$ . On the other hand, condition (IND) implies that $\# \mathcal {L}_{S'}(x,y)= \#(F-S')$ for every $S' \in \{S, S\cup \{\ell \}, S\cup \{r\}\}$ . We obtain

$$ \begin{align*} &\sum_{w\in\mathcal{L}_S(x,y)} m^{\ell,r}(w)\\ &\qquad= \#(F-(S\cup\{\ell,r\})) -\#(F-(S\cup\{r\})) -\#(F-(S\cup\{\ell\})) +\#(F-S)\\ &\qquad= \# ( {(F-(S\cup \{\ell,r\}) ) \setminus (F - (S \cup \{r\}))) }- \# {( (F-(S\cup \{\ell\}) ) \setminus (F - S))}\\ &\qquad= \# {((F-\{\ell\} ) \setminus (F - (S \cup \{r\}))) }- \# {(( F-\{\ell\} ) \setminus (F - S))}\\ &\qquad= -\# (( (F-\{r\})\setminus (F-S)) \cap (F-\{\ell\})). \end{align*} $$

Clearly, if $( (F-\{r\})\setminus (F-S)) \cap (F-\{\ell \}) = \varnothing $ , the value of the sum is $0$ . Otherwise, there is $t \in {\mathbb {Z}^d}$ such that $t+r \in F$ , $t+\ell \in F$ , but $t+s \notin F$ for every $s \in S$ , which is precisely the evil case. Notice that as $\ell \neq r$ , if such a t exists, then it is unique (because any non-trivial intersection $F \cap (t+F)$ has size at most $1$ ), and thus in this case, the sum has value $-1$ . We obtain thus that for $S \neq \varnothing $ , we have

$$ \begin{align*} \sum_{w \in \mathcal{L}_{S}(x,y)}m^{\ell,r}(w) = \begin{cases} -1 & \text{if } (S,\ell,r) \text{ is evil,}\\ 0 & \text{otherwise.} \end{cases} \end{align*} $$

Using Lemma 3.8 and the fact that there is exactly one evil pattern for an evil $(S,\ell ,r)$ , we obtain that $m^{\ell ,r}(w) = 1-c$ . By Lemma 3.1, this implies that the extension graph $E^{\ell ,r}(w)$ is acyclic.

Let us now deal with the case when $S = \varnothing $ . By assumption, $S\cup \{\ell ,r\}$ is connected and thus without loss of generality, we may write $r = \ell + e_i$ for some $i \in \{1,\ldots ,d\}$ . By definition, $m^{\ell ,r}(\varepsilon ) = \# E^{\ell ,r}(\varepsilon ) - \# E^{\ell }(\varepsilon ) - \# E^{r}(\varepsilon ) + 1$ . Clearly, $\# E^{\ell }(\varepsilon ) = \# E^{r}(\varepsilon ) = \mathcal {L}_{\{0\}}(x,y) = d+1$ and one can easily verify that for $U=\{\ell ,\ell +e_i\}$ , we have $\# E^{\ell ,r}(\varepsilon ) = \#(F-U) = 2d+1$ . It follows that $m^{\ell ,r}(\varepsilon )=0$ . As the number of connected components of $E^{\ell ,r}(\varepsilon )$ is bounded by $\#\Gamma _{\star }(\varepsilon )\leq 1$ , we conclude that $c = 1$ and thus $m^{\ell ,r}(\varepsilon )=1-c$ . By Lemma 3.1, this yields that the extension graph $E^{\ell ,r}(w)$ is acyclic.

Proof. Let $w\in \mathcal {L}_{S}(x,y)$ be a non-evil pattern. It follows that $\#\Gamma _{\star }(w) =1$ . Let $(\hat {a},\hat {b})$ be the sole element of $\Gamma _{\star }(w)$ .

Suppose that $\Gamma _{\ell }(w) \cap \Gamma _{r}(w)\neq \varnothing $ . Let $(a,b)\in \Gamma _{\ell }(w)\cap \Gamma _{r}(w)$ and p be the pattern with support $S\cup \{\ell ,r\}$ with $p|_{S}=w$ , $p_{\ell }=a$ , $p_{r}=b$ . It follows that there exists $t,t' \in {\mathbb {Z}^d}$ such that $\sigma ^{t}(x),\sigma ^{t'}(x)\in [p]$ with $t+\ell \in F$ , $(t+(S\cup \{r\}))\cap F = \varnothing $ , and $t'+r \in F$ , $(t'+(S\cup \{\ell \}))\cap F = \varnothing $ . It follows that the subpatterns $q_{\ell }$ and $q_{r}$ of p, with supports $S\cup \{\ell \}$ and $S\cup \{r\}$ , respectively, already intersect the support F in x (with vectors t and $t'$ , respectively), and thus if $t" \in {\mathbb {Z}^d}$ is such that $\sigma ^{t"}(x)\in [w]$ and $(t" +S) \cap F \neq \varnothing $ , then both $\hat {a} = x_{t"+\ell }\neq a$ and $\hat {b} = x_{t"+r}\neq b$ (otherwise the intersections of $q_{\ell }$ and $q_r$ with F on x would not be unique).

Iterating Lemma 3.6(1), we can construct a path $\pi _a$ in $E^{\ell ,r}(w)$ from a to $\hat {a}$ which begins by the edge $(a,b)$ . Similarly, using part (2), we can build a path $\pi _2$ from b to $\hat {b}$ which begins with the edge $(b,a)$ . Notice that in each path, either the edge $(\hat {a},\hat {b})$ does not appear, or it is the last edge on the path.

If $(\hat {a},\hat {b})$ does not appear in neither $\pi _a$ nor $\pi _b$ , we can put them together to construct a path from $\hat {a}$ to $\hat {b}$ which does not use the edge $(\hat {a},\hat {b})$ . Similarly, if $(\hat {a},\hat {b})$ appears in both of the paths, we can remove it from both paths and again we have a path from $\hat {a}$ to $\hat {b}$ which does not use the edge $(\hat {a},\hat {b})$ . In both cases, we obtain a cycle in $E^{\ell ,r}(w)$ .

Finally, let us suppose that the (undirected) edge $(\hat {a},\hat {b})$ appears at the end of just one path. As both cases are analogous, let us assume that it appears in $\pi _a$ . If we remove the first and last edge from $\pi _a$ , we obtain a path from b to $\hat {b}$ which does not use the edge $(a,b)$ and in which a does not appear. If we remove the first edge from $\pi _b$ , we obtain a path from a to $\hat {b}$ which does not use the edge $(b,a)$ and where b does not appear. Thus, a and b are connected through a path that does not use the edge $(a,b)$ and thus we obtain a cycle in $E^{\ell ,r}(w)$ .

Proof. The proof is done by induction on the cardinality of S. If $\# S=1$ , then it follows from the flip condition that equation (3) holds for all patterns $p\colon S\to \{\mathtt {0},\mathtt {1},\ldots ,d\}$ with support S of cardinality 1. Let us assume (by the induction hypothesis) that equation (3) holds for all supports $S\subset {\mathbb {Z}^d}$ with cardinality $\#S\leq k$ for some integer $k\geq 1$ . For the sake of contradiction, let us suppose that there exists a finite connected subset $U\subset {\mathbb {Z}^d}$ of cardinality $\#U=k+1$ such that equation (3) does not hold for some pattern $p \in \mathcal {L}_U(x,y)$ . As $\# \mathcal {L}_U(x) = \#\mathcal {L}_U(y) = \#(F-U)$ , we may assume without loss of generality that there exists a pattern $p \in \mathcal {L}_U(x,y)$ such that $\#(\mathsf {occ}_p(x)\setminus \mathsf {occ}_p(y))\geq 2$ . In other words, there are two distinct vectors $t,t' \in F-U$ such that both $\sigma ^t(x), \sigma ^{t'}(x)\in [p]$ . We claim that there exist $\ell ,r \in U$ which satisfy the following properties:

1. (A) $\ell \neq r$ ;

2. (B) U is a path in ${\mathbb {Z}^d}$ whose extreme elements are $\ell $ and r;

3. (C) $\ell $ is the unique element of U such that $t+\ell \in F$ ;

4. (D) r is the unique element of U such that $t'+r \in F$ .

Indeed, as $t,t' \in F-U$ , there are $\ell ,r \in U$ such that $t+\ell ,t'+r \in F$ . If $\ell = r$ , then as $t \neq t'$ , it follows that $t+\ell \neq t'+\ell $ are two distinct positions in F; however, as $\sigma ^t(x),\sigma ^{t'}(x)\in [p]$ , it follows that $x_{t+\ell } = x_{t'+\ell } = p_{\ell }$ which contradicts the flip condition. Therefore, we must have that $\ell \neq r$ . As U is connected, we may extract a path $U' \subseteq U$ in ${\mathbb {Z}^d}$ which connects $\ell $ and r. It follows that $p' = p|_{U'}$ also breaks equation (3) because $\sigma ^t(x),\sigma ^{t'}(x)\in [p']$ and $t,t' \in F-U'$ , and thus from the induction hypothesis, we must have $U' = U$ and thus U is a path in ${\mathbb {Z}^d}$ whose extreme elements are $\ell ,r$ . Using the same idea, suppose there is $\ell ' \in U$ such that $t+\ell ' \in F$ , then we could take the sub-path $U"\subset U$ which begins in $\ell '$ and ends in r and again $p" = p|_{U"}$ would violate the induction hypothesis. Thus, $\ell $ is unique. Similarly, r is unique.

Let $S = U \setminus \{\ell ,r\}$ , $w = p|_S$ , $a = p_{\ell }$ , and $b = p_{r}$ . Notice that the induction hypothesis implies that condition (IND) holds in $(x,y)$ for $(S,\ell ,r)$ .

As $t \neq t'$ , it follows that w is not an evil pattern. Furthermore, conditions (C) and (D) give that $(a,b)\in \Gamma _{\ell }(w)$ and $(a,b)\in \Gamma _{r}(w)$ , respectively. Therefore, we have $\Gamma _{\ell }(w) \cap \Gamma _{r}(w) \neq \varnothing $ and thus Lemma 3.10 yields that the extension graph $E^{\ell ,r}(w)$ contains a cycle. This is a contradiction with Lemma 3.9 that states that $E^{\ell ,r}(w)$ is acyclic.

We conclude that equation (3) holds for all patterns $p \in \mathcal {L}_U(x,y)$ for all finite connected subset $U\subset {\mathbb {Z}^d}$ of cardinality $\#U=k+1$ .

Proof of Theorem A

Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an asymptotic pair satisfying the flip condition with difference set $F = \{ 0, -e_1,\ldots ,-e_d\}$ . By Proposition 2.4, it follows that item (i) implies item (ii).

Assume item (ii) holds and let $S\subset {\mathbb {Z}^d}$ be a finite non-empty connected subset. As $(x,y)$ is indistinguishable, we have $\mathcal {L}_S(x)=\mathcal {L}_S(y)=\mathcal {L}_S(x,y)$ . Furthermore, from Lemma 3.4, we have $\#\mathcal {L}_S(x,y) \geq \#(F-S)$ . From Lemma 3.2, we have $\#\mathcal {L}_S(x,y) \leq \#(F-S)$ . We conclude that $\#\mathcal {L}_S(x)=\#\mathcal {L}_S(y) = \#(F-S)$ and thus item (iii) holds.

In Proposition 3.12, we proved that item (iii) implies item (i).

Proof. We proved $\mathcal {L}_S(x)\subset \{\sigma ^{n}(x)|_{S}\colon n\in F-S\}$ in Lemma 3.2. The equality

$$ \begin{align*} \mathcal{L}_S(x)=\{\sigma^{n}(x)|_{S}\colon n\in F-S\} \end{align*} $$

follows from Theorem A. From this equality, we deduce that the map $n\mapsto \sigma ^{n}(x)|_{S}$ is a bijection from $F-S$ to $\mathcal {L}_S(x)$ . As $\mathcal {L}_S(x)=\mathcal {L}_S(y)$ , we deduce that

$$ \begin{align*} \mathcal{L}_S(x)= \mathcal{L}_S(y) = \{\sigma^{n}(y)|_{S}\colon n\in F-S\}. \end{align*} $$

Thus, we conclude that the map $n\mapsto \sigma ^{n}(y)|_{S}$ is another bijection from $F-S$ to $\mathcal {L}_S(x)$ .

Proof of Corollary 1

Let $m=(m_1,\ldots ,m_d) \in \mathbb {N}^d$ be a positive integer vector. From Theorem A, we have that $\mathcal {L}_{m}(x) = \mathcal {L}_{m}(y) = \#(F-S(m))$ .

By a simple counting argument, we have that $\#(F-S(m))$ is equal to the volume of $S(m)$ plus the volume of each of its $d-1$ dimensional faces. We conclude that

$$ \begin{align*} \#\mathcal{L}_m(x) = \#\mathcal{L}_{m}(y) = m_1\cdots m_d \bigg(1+\frac{1}{m_1}+\cdots+\frac{1}{m_d}\bigg).\\[-43pt] \end{align*} $$

Proof. Let $n\in {\mathbb {Z}^d}$ and $j\in \{0,1,\ldots ,d\}$ be such that $n^\star +\rho \in W_j$ . Therefore, ${s_{\alpha ,\rho }(n)=j}$ . From equation (5), recall that we have $n^\star =n\cdot \alpha \bmod 1$ . Since the intervals $W_0$ , $W_1$ , $\ldots $ , $W_d$ are ordered from left to right on the interval $[0,1)$ , we must have

$$ \begin{align*} s_{\alpha,\rho}(n) = j &= \#\{ i\in\{1,\ldots,d\} : 1-\alpha_i \leq n\cdot\alpha+\rho-\lfloor n\cdot\alpha+\rho\rfloor \}\\ &= \#\{ i\in\{1,\ldots,d\} : 1 \leq \alpha_i + n\cdot\alpha+\rho-\lfloor n\cdot\alpha+\rho\rfloor \}\\ &= \#\{ i\in\{1,\ldots,d\} : \lfloor\alpha_i+n\cdot\alpha+\rho\rfloor -\lfloor n\cdot\alpha+\rho\rfloor = 1 \}\\ &= \sum\limits_{i=1}^d (\lfloor\alpha_i+n\cdot\alpha+\rho\rfloor -\lfloor n\cdot\alpha+\rho\rfloor). \end{align*} $$

The proof for $s^{\prime }_{\alpha ,\rho }$ follows the same argument after replacing inequalities ( $\leq $ ) by strict inequalities ( $<$ ) and floor functions ( $\lfloor \cdot \rfloor $ ) by ceil functions ( $\lceil \cdot \rceil $ ).

Proof. If all coordinates in $\alpha = (\alpha _1,\ldots ,\alpha _d)$ are rational, it is clear that $s_{\alpha ,\rho }$ and $s^{\prime }_{\alpha ,\rho }$ have finite orbits under the shift action and are thus uniformly recurrent.

Suppose there is $1 \leq i \leq d$ such that $\alpha _i$ is irrational and let $S \subset {\mathbb {Z}^d}$ be finite and $p \in \mathcal {L}_S(s_{\alpha ,\rho })$ . From the definition, we have that $\sigma ^n(s_{\alpha ,\rho }) \in [p]$ if and only if

$$ \begin{align*} n\cdot \alpha+\rho \in \bigcap_{k \in S} (W_{p_k} - \alpha \cdot k + \mathbb{Z}).\end{align*} $$

From the definition, it is easy to see that for each $\mathtt {j}\in \{\mathtt {0},\mathtt {1},\ldots ,d\}$ , the set $W_{\mathtt {j}}$ is either empty or has non-empty interior. As $p \in \mathcal {L}_S(s_{\alpha ,\rho })$ , it follows that $\bigcap _{k \in S} (\operatorname {Int} (W_{p_k} )- \alpha \cdot k + \mathbb {Z})$ is non-empty and thus contains an open interval $U \subseteq \mathbb {R}/\mathbb {Z}$ .

As $\alpha _i$ is irrational, it follows that there is $M \in \mathbb {N}$ such that for any $b \in \mathbb {R}/\mathbb {Z}$ , there is $0 \leq m \leq M$ such that $b+m\alpha _i \in U$ . It follows that for any $n \in {\mathbb {Z}^d}$ , there is $0 \leq m \leq M$ such that $(n + me_i)\cdot \alpha + \rho \in U$ and, therefore, $\sigma ^{n+me_i}(s_{\alpha ,\rho })\in [p]$ . This shows that $s_{\alpha ,\rho }$ is uniformly recurrent. The argument for $s^{\prime }_{\alpha ,\rho }$ is analogous.

Proof. Since $\alpha $ is totally irrational, we have that $\alpha _i+n\cdot \alpha $ is an integer if and only if $n=-e_i$ and $n\cdot \alpha $ is an integer if and only if $n=0$ . Therefore, we have that

$$ \begin{align*} \lfloor\alpha_i+n\cdot\alpha\rfloor-\lfloor n\cdot\alpha\rfloor = \lceil\alpha_i+n\cdot\alpha\rceil-\lceil n\cdot\alpha\rceil \end{align*} $$

for every $n\in \mathbb {Z}^d\setminus \{0,-e_i\}$ and $i\in \{1,\ldots ,d\}$ . Therefore,

$$ \begin{align*} c_{\alpha}(n)= c^{\prime}_{\alpha}(n) \end{align*} $$

for every $n\in \mathbb {Z}^d\setminus \{0,-e_0,\ldots ,-e_d\}$ . This shows that $(c_{\alpha },c^{\prime }_{\alpha })$ is an asymptotic pair whose difference set is $F=\{0,-e_0,\ldots ,-e_d\}$ .

Proof. From Lemma 4.6, if $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ is totally irrational, then $(c_{\alpha },c^{\prime }_{\alpha })$ is an asymptotic pair whose difference set is $F = \{0, -e_1, \ldots , -e_d \}$ .

From Lemma 4.3, we have that for $n \in \mathbb {Z}^d$ ,

$$ \begin{align*} (c_{\alpha})_n = \sum_{\mathtt{i}=1}^d (\lfloor\alpha_{\mathtt{i}}+ n \cdot \alpha \rfloor -\lfloor n \cdot \alpha \rfloor) \quad\mbox{and}\quad (c^{\prime}_{\alpha})_n = \sum_{\mathtt{i}=1}^d (\lceil\alpha_{\mathtt{i}}+ n \cdot \alpha \rceil -\lceil n \cdot \alpha \rceil). \end{align*} $$

From here, we obtain directly that $(c_{\alpha })_0 = \mathtt {0}$ and $(c^{\prime }_{\alpha })_0 = d$ . For $n = -e_{\mathtt {i}}$ , we get

(6) $$ \begin{align} (c_{\alpha})_{-e_{\mathtt{i}}} &= \sum_{\mathtt{j}=1}^d (\lfloor\alpha_{\mathtt{j}} -\alpha_{\mathtt{i}} \rfloor -\lfloor -\alpha_{\mathtt{i}} \rfloor) = d - \#\{ \mathtt{j} : \alpha_{\mathtt{j}} < \alpha_{\mathtt{i}} \} = \#\{ \mathtt{j} : \alpha_{\mathtt{j}} \geq \alpha_{\mathtt{i}} \}, \end{align} $$

(7) $$ \begin{align} (c^{\prime}_{\alpha})_{-e_{\mathtt{i}}} &= \sum_{\mathtt{j}=1}^d (\lceil\alpha_{\mathtt{j}} -\alpha_{\mathtt{i}} \rceil -\lceil -\alpha_{\mathtt{i}} \rceil) = \#\{ \mathtt{j} : \alpha_{\mathtt{j}}> \alpha_{\mathtt{i}} \}. \end{align} $$

As $\alpha $ is totally irrational, all $\alpha _{\mathtt {i}}$ are distinct non-zero values. From the above formula, we obtain that $(c_{\alpha })|_F$ and $(c^{\prime }_{\alpha })|_F$ are bijections onto $\{\mathtt {0},\mathtt {1},\ldots ,d\}$ and $(c_{\alpha })_{-e_{\mathtt {i}}}-(c^{\prime }_{\alpha })_{-e_{\mathtt {i}}} = \mathtt {1}$ , from where the second condition follows.