Indistinguishable asymptotic pairs and multidimensional Sturmian configurations

Abstract

Two asymptotic configurations on a full $\mathbb {Z}^d$-shift are indistinguishable if, for every finite pattern, the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of $\mathbb {Z}^d$. We prove that indistinguishable asymptotic pairs satisfying a ‘flip condition’ are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together, the two results provide a generalization to $\mathbb {Z}^d$ of the characterization of Sturmian sequences by their factor complexity $n+1$. Many open questions are raised by the current work and are listed in the introduction.

1. Introduction

Asymptotic pairs, also known as homoclinic pairs, are pairs of points in a dynamical system whose orbits coalesce. These were first studied by Poincaré [2] in the context of the three body problem and used to model chaotic behavior. Namely, two orbits which remain arbitrarily close outside a finite window of time may be used to represent pairs of trajectories that, despite having similar behavior for an arbitrarily long time, present abrupt local differences.

In this work, we consider asymptotic pairs of zero-dimensional expansive actions of ${\mathbb {Z}^d}$ . Concretely, given a finite set $\Sigma $ , we consider the space of configurations ${\Sigma ^{{\mathbb {Z}^d}} = \{ x \colon {\mathbb {Z}^d} \to \Sigma \}}$ endowed with the prodiscrete topology and the shift action ${\mathbb {Z}^d} \overset {\sigma }{\curvearrowright } \Sigma ^{{\mathbb {Z}^d}}$ . In this setting, two configurations $x,y \in \Sigma ^{{\mathbb {Z}^d}}$ are asymptotic if x and y differ in finitely many sites of ${\mathbb {Z}^d}$ . The finite set $F = \{ v \in {\mathbb {Z}^d} : x_v \neq y_v\}$ is called the difference set of $(x,y)$ . An example of an asymptotic pair when $d=2$ is shown in Figure 1.

Given two asymptotic configurations $x,y \in \Sigma ^{{\mathbb {Z}^d}}$ , we want to compare the number of occurrences of patterns. A pattern is a function $p \colon S \to \Sigma $ , where S, called the support of p, is a finite subset of ${\mathbb {Z}^d}$ . The occurrences of a pattern $p\in \Sigma ^S$ in a configuration ${x\in \Sigma ^{\mathbb {Z}^d}}$ is the set . The language of a configuration ${x\in \Sigma ^{\mathbb {Z}^d}}$ over a finite support $S\subset {\mathbb {Z}^d}$ is $\mathcal {L}_S(x)=\{p\in \Sigma ^S\colon \mathsf {occ}_p(x)\neq \varnothing \}$ . When ${x,y \in \Sigma ^{{\mathbb {Z}^d}}}$ are asymptotic configurations, the difference $\mathsf {occ}_p(x)\setminus \mathsf {occ}_p(y)$ is finite because the occurrences of p are the same far from the difference set of x and y. We say that $(x,y)$ is an indistinguishable asymptotic pair if $(x,y)$ is asymptotic and the following equality holds:

(1) $$ \begin{align} \#(\mathsf{occ}_p(x)\setminus \mathsf{occ}_p(y)) = \#(\mathsf{occ}_p(y)\setminus \mathsf{occ}_p(x)) \end{align} $$

for every pattern p of finite support.

In other words, an asymptotic pair $(x,y)$ is indistinguishable if every pattern appears the same number of times in x and in y while overlapping the difference set. The pair of configurations x and y shown in Figure 1 is an example of an indistinguishable asymptotic pair: we may check by hand that equation (1) holds for patterns with small supports such as symbols (patterns of shape $\{0\}$ ), dominoes (patterns of shape $\{0,e_1\}$ and $\{0,e_2\}$ ), etc. For instance, the configurations x and y in Figure 1 contain eight different patterns with support $\{0,e_1,2e_1,e_2\}$ , each occurring exactly once while overlapping the difference set, see Figure 2.

The notion of indistinguishable asymptotic pairs appears naturally in Gibbs theory. This theory studies measures on symbolic dynamical systems which are at equilibrium in the sense that the conditional pressure for every finite region of the lattice is maximized, so that every finite region is in equilibrium with its surrounding. See [8, 19, 27, 34] for further background. An important component of Gibbs measures, the specification, can be formalized by means of a shift-invariant cocycle in the equivalence relation of asymptotic pairs, see [7, 15]. With an appropriate norm, the space of continuous shift invariant cocycles on the asymptotic relation becomes a Banach space, and every asymptotic pair induces a continuous linear functional through the canonical evaluation map.

The set of indistinguishable asymptotic pairs are precisely those which induce the trivial linear functional and, thus, a natural question is if there is an underlying dynamical structure behind this property. We shall not speak any further of Gibbs theory in this work and study indistinguishable asymptotic pairs without further reference to their origin in Gibbs theory. An interested reader can find out more about the role of indistinguishable asymptotic pairs in the aforementioned setting by reading [7, §§2 and 3].

Figure 1 The indistinguishable asymptotic configurations $x,y\in \{\mathtt {0},\mathtt {1},\mathtt {2}\}^{\mathbb {Z}^2}$ are shown on the support . The two configurations are equal except on their difference set $F=\{0,-e_1,-e_2\}$ shown in darker hue.

Figure 2 The eight patterns of shape $\{0,e_1,2e_1,e_2\}$ appearing in the configurations x and y. All of them appear intersecting the difference set in x and y.

In the case of dimension $d=1$ , it was shown that for the difference set $F= \{-1,0\}\subset \mathbb {Z}$ , indistinguishable asymptotic pairs are precisely the étale limits of characteristic bi-infinite Sturmian sequences [9, Theorem B]. In the case where one of the configurations in the indistinguishable pair is recurrent, the asymptotic pair can only be a pair of characteristic bi-infinite Sturmian sequences associated to a fixed irrational value [9, Theorem A]. Furthermore, it was shown that any indistinguishable asymptotic pair in $\Sigma ^{\mathbb {Z}}$ can be obtained from these base cases through the use of a substitution and the shift map [9, Theorem C], thus providing a full characterization of indistinguishable asymptotic pairs in $\mathbb {Z}$ .

1.1. Main results

In this article, we extend [9, Theorem A] to the multidimensional setting. It is based on the following additional condition made on the difference set. Let $\{e_1,\ldots , e_d\}$ denote the canonical basis of ${\mathbb {Z}^d}$ . We say that two indistinguishable asymptotic configurations $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ satisfy the flip condition if their difference set is $F = \{ 0, -e_1,\ldots ,-e_d \}$ , every symbol in $\{\mathtt {0},\mathtt {1},\ldots ,d\}$ occurs in x and y at the support F, and the map defined by $x_n\mapsto y_n$ for every $n\in F$ is a cyclic permutation on the alphabet $\{\mathtt {0},\mathtt {1},\ldots ,d\}$ . Without lost of generality, we assume that $x_{0} = \mathtt {0}$ and $y_n = x_n - \mathtt {1} \bmod (d+\mathtt {1})$ for every $n\in F$ . For example, the indistinguishable asymptotic pair $(x,y)$ illustrated in Figure 1 satisfies the flip condition with $(x_0,x_{-e_1},x_{-e_2})=(\mathtt {0},\mathtt {1},\mathtt {2})$ and $(y_0,y_{-e_1},y_{-e_2})=(\mathtt {2},\mathtt {0},\mathtt {1})$ .

It is a well-known fact that Sturmian configurations in dimension one can be characterized by their complexity [16, 31], that is, they are exactly the bi-infinite recurrent words in which exactly $n+1$ subwords of length n occur for every $n \in \mathbb {N}$ . We first prove the following result providing a similar characterization of indistinguishable asymptotic pairs satisfying the flip condition by their pattern complexity which does not require uniform recurrence, or even recurrence, as an hypothesis.

Theorem A. Let $d\geq 1$ and $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\}$ . The following are equivalent.

1. (i) For every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ and $p \in \mathcal {L}_S(x)\cup \mathcal {L}_S(y)$ , we have

   $$ \begin{align*} \#(\mathsf{occ}_p(x)\setminus \mathsf{occ}_p(y)) = 1 = \#(\mathsf{occ}_p(y)\setminus \mathsf{occ}_p(x)). \end{align*} $$

2. (ii) The asymptotic pair $(x,y)$ is indistinguishable.

3. (iii) For every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ , the pattern complexity of x and y is

   $$ \begin{align*}\#\mathcal{L}_S(x)=\#\mathcal{L}_S(y) = \#(F-S).\end{align*} $$

The proof of Theorem A relies on an extension of the notion of bispecial factor to the setting of multidimensional configurations. Given a language, a bispecial factor is a word that can be extended in more than one way to the left and to the right. The bilateral multiplicity of bispecial factors in a one-dimensional language is closely related to the complexity of that language, see [14]. Here, for a connected support $S\subset {\mathbb {Z}^d}$ and two distinct positions $a,b\in {\mathbb {Z}^d}\setminus S$ such that $S\cup \{a\}$ , $S\cup \{b\}$ , and $S \cup \{a,b\}$ are connected, we say that a pattern $w\colon S\to \mathcal {A}$ is bispecial if it can be extended in more than one way at position a and at position b. The description of the bispecial patterns of indistinguishable asymptotic pairs and their multiplicities provides us a tool for bounding their pattern complexity. Reciprocally, the rigid pattern complexity given in Theorem A forces the extension graphs associated to the bispecial patterns to have no cycle, which in turn provides us with a way to show that the configurations are indistinguishable. In one dimension, sequences, such as when the extension graphs of bispecial factors are trees, are known as dendric words [11] and thus, we may think of our construction as multidimensional analogues of those.

When S is a d-dimensional rectangular block, the number $\#(F-S)$ from Theorem A admits a nice form. When $d=1$ , we compute $\#(F-S)=\#(\{0,-1\}-\{0,1,\ldots , n-1\})=n+1$ which is the factor complexity function for one-dimensional Sturmian words. When $d=2$ , $\#(F-S)=\#(\{(0,0),(-1,0),(0,-1)\}-\{(i,j)\colon 0\leq i<n, 0\leq j<m\})=mn+m+n$ is the rectangular pattern complexity of a discrete plane with totally irrational (irrational and rationally independent) slope, see [12] for further references. With our result above, we can provide an explicit formula for every dimension.

Corollary 1. Let $d\hspace{-0.5pt}\geq\hspace{-0.5pt} 1$ and $(m_1,\ldots ,m_d)\in \mathbb {N}^d$ . The rectangular pattern complexity of an indistinguishable asymptotic pair $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ satisfying the flip condition is

$$ \begin{align*} \#\mathcal{L}_{(m_1,\ldots,m_d)}(x) =\#\mathcal{L}_{(m_1,\ldots,m_d)}(y)= m_1\cdots m_d \bigg(1+\frac{1}{m_1}+\cdots+\frac{1}{m_d}\bigg). \end{align*} $$

Our main result provides a beautiful connection between indistinguishable asymptotic pairs satisfying the flip condition and codimension-one (dimension of the internal space) cut and project schemes, see [20] for further background, and more precisely with multidimensional Sturmian configurations. The definition of multidimensional Sturmian configurations from codimension-one cut and project schemes is fully described in §4.1. A quick and easy definition of multidimensional Sturmian configurations can be given with the following formulas. Given a totally irrational vector $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ , the lower and upper characteristic d-dimensional Sturmian configurations with slope $\alpha $ are given by

(2) $$ \begin{align} \begin{array}{llll} c_{\alpha}:&{\mathbb{Z}^d} \to \{\mathtt{0},\mathtt{1},\ldots,d\}\\ &n \mapsto \sum\limits_{i=1}^d (\lfloor\alpha_i+n\cdot\alpha\rfloor -\lfloor n\cdot\alpha\rfloor) \end{array} \text{ and } \begin{array}{llll} c^{\prime}_{\alpha}:&{\mathbb{Z}^d} \to \{\mathtt{0},\mathtt{1},\ldots,d\}\\ &n \mapsto \sum\limits_{i=1}^d (\lceil\alpha_i+n\cdot\alpha\rceil -\lceil n\cdot\alpha\rceil). \end{array} \end{align} $$

It turns out that these configurations are examples of indistinguishable asymptotic pairs which satisfy the flip condition. In fact, we show that a pair of uniformly recurrent asymptotic configurations is indistinguishable and satisfies the flip condition if and only if it is a pair of characteristic d-dimensional Sturmian configurations for some totally irrational slope.

Theorem B. Let $d\geq 1$ and $x,y\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{\mathbb {Z}^d}$ such that x is uniformly recurrent. The pair $(x,y)$ is an indistinguishable asymptotic pair satisfying the flip condition if and only if there exists a totally irrational vector $\alpha \in [0,1)^d$ such that $x=c_{\alpha }$ and $y=c^{\prime }_{\alpha }$ are the lower and upper characteristic d-dimensional Sturmian configurations with slope $\alpha $ .

The indistinguishable asymptotic pair shown in Figure 1 is an example as such, where $x=c_{\alpha }$ and $y=c^{\prime }_{\alpha }$ with $\alpha =(\alpha _1,\alpha _2)=(\sqrt {2}/2,\sqrt {19}-4)$ . Notice that $c_\alpha $ and $c^{\prime }_\alpha $ are uniformly recurrent when $\alpha $ contains at least an irrational coordinate (see Lemma 4.5), so that the hypothesis is really only used in one direction of the theorem. Note that a version of Theorem B for rational vector $\alpha \in \mathbb {Q}^d$ was considered in [26] with an infinite difference set of the form $F+K$ , where $K\subset {\mathbb {Z}^d}$ is some lattice.

The link with codimension-one cut and project schemes can be illustrated as follows. The configurations $x=c_{\alpha }$ and $y=c^{\prime }_{\alpha }$ encode the rhombi obtained as the projection of the cube faces in a discrete plane of normal vector $(1-\alpha _1,\alpha _1-\alpha _2,\alpha _2)$ , see Figure 3. This three symbol coding of a discrete plane was proposed in [22], see also [10].

Figure 3 Configurations x and y from Figure 1 are encoding a tiling of the plane [5] by three types of pointed rhombus drawn using Jolivet’s notation [23, p. 112]. The tilings shown above correspond to the projection of the surface of a discrete plane of normal vector $(1-\alpha _1,\alpha _1-\alpha _2,\alpha _2) \approx (0.293, 0.348, 0.359)$ , with $\alpha =(\alpha _1,\alpha _2)=(\sqrt {2}/2,\sqrt {19}-4)$ , in three-dimensional space, and their difference can be interpreted as the flip of a unit cube shown in white.

We also prove a slightly more general version of Theorem B. We say that two indistinguishable asymptotic configurations $x,y \in \Sigma ^{{\mathbb {Z}^d}}$ satisfy the affine flip condition if their difference set F has cardinality $\#F = d+1$ , there is $m \in F$ such that $(F-m)\setminus \{0\}$ is a base of ${\mathbb {Z}^d}$ , the restriction $x|_F$ is a bijection $F\to \Sigma $ , and the map defined by $x_n\mapsto y_n$ for every $n\in F$ is a cyclic permutation on $\Sigma $ .

Corollary 2. Let $d\geq 1$ and $x,y\in \Sigma ^{\mathbb {Z}^d}$ such that x is uniformly recurrent. The pair $(x,y)$ is an indistinguishable asymptotic pair satisfying the affine flip condition if and only if there exist a bijection $\tau \colon \{\mathtt {0},\mathtt {1},\ldots ,d\}\to \Sigma $ , an invertible affine transformation $A\in \operatorname {Aff}({\mathbb {Z}^d})$ , and a totally irrational vector $\alpha \in [0,1)^d$ such that $x=\tau \circ c_{\alpha }\circ A$ and $y=\tau \circ c^{\prime }_{\alpha }\circ A$ .

If we further assume that the configurations in the asymptotic pair are uniformly recurrent, we can put together Theorems A and B, and obtain the following characterization of uniformly recurrent multidimensional Sturmian configurations in terms of their pattern complexity. This generalizes the well-known theorem of Morse, Hedlund, and Coven to higher dimensions [16, 31].

Corollary 3. Let $d\geq 1$ and $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an asymptotic pair such that x is uniformly recurrent and which satisfies the flip condition with difference set $F = \{ 0, -e_1,\ldots ,-e_d\}$ . The following are equivalent.

1. (i) For every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ and $p \in \mathcal {L}_S(x,y)$ , we have

   $$ \begin{align*} \#(\mathrm{\sf occ}_p(x)\setminus \mathrm{\sf occ}_p(y)) = 1 = \#(\mathrm{\sf occ}_p(y)\setminus \mathrm{\sf occ}_p(x)). \end{align*} $$

2. (ii) The asymptotic pair $(x,y)$ is indistinguishable.

3. (iii) For every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ , we have

   $$ \begin{align*}\#\mathcal{L}_S(x)=\#\mathcal{L}_S(y) = \#(F-S).\end{align*} $$

4. (iv) There exists a totally irrational vector $\alpha \in [0,1)^d$ such that $x = c_{\alpha }$ and $y=c^{\prime }_{\alpha }$ .

1.2. Open questions

To fully generalize the theorem of Morse, Hedlund, and Coven, we would hope the equivalence holds for single configurations and not only for pairs of asymptotic configurations satisfying the flip condition. More precisely, in the case of uniformly recurrent configurations, we believe that the pattern complexity characterizes multidimensional Sturmian configurations. The formula defining $s_{\alpha ,\rho }$ and $s^{\prime }_{\alpha ,\rho }$ slightly extends equation (2) and can be found in Lemma 4.3.

Question 1. Let $d\geq 1$ and $x \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be a uniformly recurrent configuration. Let $F = \{ 0, -e_1,\ldots ,-e_d\}$ . Consider the following two statements:

1. (i) for every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ , we have $\#\mathcal {L}_S(x)= \#(F-S)$ ;

2. (ii) there exists a totally irrational vector $\alpha \in [0,1)^d$ and a intercept $\rho \in [0,1)$ such that $x = s_{\alpha ,\rho }$ or $x=s^{\prime }_{\alpha ,\rho }$ .

Since $s_{\alpha ,\rho }$ , $s^{\prime }_{\alpha ,\rho }$ , and $c_\alpha $ have the same language when $\alpha $ is totally irrational, we can deduce from Corollary 3 that statement (ii) implies statement (i). Is it true that statements (i) and (ii) are equivalent?

Consider a sequence of totally irrational slopes $(\alpha _n)_{n \in \mathbb {N}}$ for which both $c_{\alpha _n}$ and $c^{\prime }_{\alpha _n}$ converge in the prodiscrete topology. Then $(c_{\alpha _n},c^{\prime }_{\alpha _n})_{n \in \mathbb {N}}$ converges in the asymptotic relation to an étale limit $(c,c')$ , see Definition 2.8. It turns out that étale limits preserve both the flip condition and indistinguishability, and will thus satisfy all of the equivalences stated in Theorem A. An example of such a limit is illustrated in Figure 4.

Figure 4 An indistinguishable asymptotic pair $(c,c')$ which satisfies the flip condition obtained by taking the limit of the Sturmian configurations given by $\alpha _n = ({1}/{n}(\sqrt {2}-1),{1}/{n}(\sqrt {3}-1))$ .

We believe that, in fact, every indistinguishable asymptotic pair on ${\mathbb {Z}^d}$ which satisfies the flip condition can be obtained through an étale limit as above.

Conjecture 1. Let $d\geq 1$ and $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair which satisfies the flip condition. Then there exists a sequence of totally irrational vectors $(\alpha _n)_{n \in \mathbb {N}}$ such that $(x,y)$ is the étale limit of the sequence of asymptotic pairs $(c_{\alpha _n},c^{\prime }_{\alpha _n})_{n \in \mathbb {N}}$ .

It was proved that Conjecture 1 holds when $d=1$ , see [9, Theorem B]. Proving it for $d>1$ is harder due to the various ways a sequence $(\alpha _n)_{n\in \mathbb {N}}$ can converge to some vector $\alpha \in [0,1)^d$ leading to infinitely many étale limits associated to a single vector. When $d=1$ , there are only two such ways: from above or from below. Describing combinatorially what happens in these two cases was sufficient in [9] to prove the result. An analogue combinatorial description of all different behaviors when $d>1$ is still open.

In [9, Theorem C], indistinguishable asymptotic pairs were totally described when $d=1$ by the image under substitutions of characteristic Sturmian sequences. Describing indistinguishable asymptotic pairs in general when $d>1$ (other than those satisfying the flip condition or some affine version of it) remains an open question.

Question 2. Let $d\geq 1$ and $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair. Does there exists a sequence of totally irrational vectors $(\alpha _n)_{n \in \mathbb {N}}$ such that $(x,y)$ can be derived from the étale limit of the sequence of asymptotic pairs $(c_{\alpha _n},c^{\prime }_{\alpha _n})_{n \in \mathbb {N}}$ ?

Our current work also leads to another interesting question. In dimension 1, it is known at least since [30] that a sequence of factor complexity less than or equal to n is eventually periodic. In two dimensions, it is still an open problem [17, 24] known as Nivat’s conjecture [32] whether a configuration x for which there are $n,m \in \mathbb {N}$ with $\#\mathcal {L}_{(n,m)}(x)\leq nm$ is periodic or not. Another question which seems to have been overlooked due to the difficulty of settling Nivat’s conjecture is to describe the minimal complexity of an aperiodic configuration (trivial stabilizer under the shift map, that is, $\sigma ^n(x)=x$ only holds for $n =0$ ) which admits a totally irrational vector of symbols frequencies. When $d=1$ , we know that such sequences have complexity at least $n+1$ and are realized by Sturmian configurations. However, when $d=2$ , configurations with rectangular pattern complexity $mn+1$ are not uniformly recurrent and do not have a totally irrational vector of symbol frequencies [13]. As the symbol frequencies of the multidimensional Sturmian configurations $c_\alpha $ and $c^{\prime }_\alpha $ is $\alpha $ , it follows by Theorems B and A that they provide an upper bound for this problem, namely, that these sequences can be realized with complexity $\#(F-S)$ for every pattern of connected support S. According to Cassaigne and Moutot (personal communication, January 2023), there exist two-dimensional configurations with totally irrational vector of symbol frequencies with pattern complexity strictly less than $\#(F-S)$ for infinitely many connected supports S. Therefore, we ask the following question.

Question 3. Let $d\geq 1$ . Let $x\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be a configuration with trivial stabilizer, and assume that the frequencies of symbols in x exist and form a totally irrational vector. Let $S\subset {\mathbb {Z}^d}$ be a non-empty connected finite support. What is the greatest lower bound for the pattern complexity $\#\mathcal {L}_S(x)$ ?

It is known that bispecial factors within the language of a Sturmian sequence of slope $\alpha \in [0,1)$ are related to the convergents of the continued fraction expansion of $\alpha $ [18]. Since our work extends the notion of bispecial factors to the setup of multidimensional Sturmian configurations (see Figure 5), it is natural to ask the following question about simultaneous Diophantine approximation [35].

Figure 5 On the left, an L-shape pattern of support $\{(1,0),(2,0),(3,0),(4,0),(4,1),(4,2),(4,3), (4,4)\}$ is shown. It is bispecial at positions $a=(0,0)$ and $b=(4,5)$ because it can be extended in more than one way at these positions within the language of the configurations x and y shown in Figure 1. Thus, $b-a=(4,5)\in V_\alpha $ when $\alpha =(\sqrt {2}/2,\sqrt {19}-4)$ .

Question 4. Let $d\geq 1$ and $\alpha \in [0,1)^d$ be a totally irrational vector. What is the relation between the set

$$ \begin{align*} V_\alpha=\{b-a\colon \text{ there exists } w\in\mathcal{L}_S(c_\alpha) \text{ which is bispecial at positions } a,b\in{\mathbb{Z}^d}\} \end{align*} $$

and simultaneous Diophantine approximations of the vector $\alpha $ ?

1.3. Structure of the article

Preliminary properties of indistinguishable asymptotic pairs are presented in §2. In §3, we study the pattern complexity of multidimensional indistinguishable asymptotic pairs satisfying the flip condition and we prove Theorem A. In §4, we define characteristic Sturmian configurations in ${\mathbb {Z}^d}$ from codimension-one cut and project schemes. We prove that they are indistinguishable asymptotic pairs satisfying the flip condition. In §5, we complete the proof of Theorem B, more precisely that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are multidimensional Sturmian configurations. In the Appendix A, we provide an analogous notion of indistinguishable pairs for pairs of asymptotic configurations on a countable group and provide proofs of their basic properties for further reference.

2. Preliminaries

We denote by $\mathbb {N}$ the set of non-negative integers. Intervals consisting of integers are written using the notation for $n,m \in \mathbb {Z}$ with $n \leq m$ . A finite subset $S\subset {\mathbb {Z}^d}$ is connected if the subgraph induced by the vertices S within the graph with vertices $V = {\mathbb {Z}^d}$ and edges $E=\{(u,u+e_i)\colon u\in {\mathbb {Z}^d},1\leq i\leq d\}$ is connected, where $e_i$ is the canonical vector with $1$ on position i and $0$ elsewhere.

Let $\Sigma $ be a finite set which we call an alphabet and d a positive integer. An element $x \in \Sigma ^{{\mathbb {Z}^d}} = \{x \colon {\mathbb {Z}^d} \to \Sigma \}$ is called a configuration. For $u \in {\mathbb {Z}^d}$ , we denote the value $x(u)$ by $x_u$ . We endow a set of all configurations $\Sigma ^{{\mathbb {Z}^d}}$ with the prodiscrete topology. The shift action ${\mathbb {Z}^d} \overset {\sigma }{\curvearrowright } \Sigma ^{{\mathbb {Z}^d}}$ is given by the map $\sigma \colon {\mathbb {Z}^d} \times \Sigma ^{{\mathbb {Z}^d}}\to \Sigma ^{{\mathbb {Z}^d}}$ , where

The orbit of $x \in \Sigma ^{{\mathbb {Z}^d}}$ is the set $\mathrm {Orb}(x) = \{\sigma ^{v}(x) : v \in {\mathbb {Z}^d} \}$ . For a finite subset $S \subset {\mathbb {Z}^d}$ , a function $p \colon S \to \Sigma $ is called a pattern and the set S is its support. We denote it as $p \in \Sigma ^S$ . Given a pattern $p \in \Sigma ^S$ , the cylinder centered at p is $[p] = \{ x \in \Sigma ^{{\mathbb {Z}^d}} \colon x|_S = p \}$ . For finite subset $S \subset {\mathbb {Z}^d}$ , the language with support S of a configuration x is the set of patterns

$$ \begin{align*}\mathcal{L}_{S}(x) = \{ p \in \Sigma^S : \mbox{ there is } u \in {\mathbb{Z}^d} \mbox{ such that } \sigma^u(x) \in [p]\}. \end{align*} $$

The language of x is the union $\mathcal {L}(x)$ of the sets $\mathcal {L}_S(x)$ for every finite $S \subset {\mathbb {Z}^d}$ . We say a pattern p appears in $x \in \Sigma ^{{\mathbb {Z}^d}}$ if there exists $u \in {\mathbb {Z}^d}$ such that $\sigma ^u(x) \in [p]$ . Let us also denote by $\mathsf {occ}_p(x) = \{u \in {\mathbb {Z}^d} \colon \sigma ^u(x) \in [p]\}$ the set of occurrences of a pattern p in the configuration $x \in \Sigma ^{{\mathbb {Z}^d}}$ .

Definition 2.1. We say that two configurations $x,y$ are asymptotic, or that $(x,y)$ is an asymptotic pair, if the set $F = \{ u \in {\mathbb {Z}^d} \colon x_u \neq y_u\}$ is finite. The set F is called the difference set of $(x,y)$ . If $x=y$ , we say that the asymptotic pair is trivial.

Observe that when $x,y \in \Sigma ^{{\mathbb {Z}^d}}$ are asymptotic sequences, the difference $\mathsf {occ}_p(x)\setminus \mathsf {occ}_p(y)$ is finite because the occurrences of p are the same far from the difference set. More precisely, let F denote the difference set of an asymptotic pair $x,y$ . Let S denote the support of a pattern p, then for every $u \in {\mathbb {Z}^d} \setminus (F-S)$ and every $s \in S$ , we have $s+u \notin F$ and thus

$$ \begin{align*}\sigma^u(x)_s = x_{u+s} = y_{u+s} = \sigma^u(y)_s,\end{align*} $$

which implies in turn that $u\in \mathsf {occ}_p(x)$ if and only if $u\in \mathsf {occ}_p(y)$ for all $u\in {\mathbb {Z}^d}\setminus (F-S)$ . Therefore,

$$ \begin{align*} \mathsf{occ}_p(x)\setminus \mathsf{occ}_p(y) \subseteq F-S = \{ g-s \colon g \in F, s \in S \}. \end{align*} $$

In particular, the set $\mathsf {occ}_p(x)\setminus \mathsf {occ}_p(y)$ is finite. Moreover, since F is the difference set of x and y, we have

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

Definition 2.2. We say that two asymptotic configurations $x,y \in \Sigma ^{{\mathbb {Z}^d}}$ are indistinguishable if for every pattern p of finite support, we have

$$ \begin{align*} \#(\mathsf{occ}_p(x)\setminus \mathsf{occ}_p(y)) = \#(\mathsf{occ}_p(y)\setminus \mathsf{occ}_p(x)). \end{align*} $$

Notice that Definition 2.2 holds only for asymptotic pairs. A more general notion, known as local indistinguishability exists in the context of tilings of $\mathbb {R}^d$ , see [6, §5.1.1]. In terms of subshifts, two configurations $x,y\in \Sigma ^{\mathbb {Z}^d}$ are locally indistinguishable, or LI for short, if they have the same language, that is, $\mathcal {L}(x)=\mathcal {L}(y)$ . In this work, we always write ‘indistinguishable asymptotic pair’ to emphasize the context in which Definition 2.2 holds.

An example of an indistinguishable asymptotic pair over $\mathbb {Z}^2$ is shown in Figure 6, see also Figure 1.

Figure 6 A non-trivial indistinguishable asymptotic pair for $\Sigma = \{\mathtt {0},\mathtt {1}\}$ and $d=2$ , where $y = \sigma ^{(3,1)}(x)$ . The difference set is highlighted in darker hue and the portions of the configurations which are not shown consist only of the symbol $\mathtt {0}$ .

Next we state equivalent conditions for indistinguishability which we will use interchangeably in the proofs that follow. We use the symbol to indicate the characteristic function of a set A.

Remark 2.3. The following conditions are equivalent:

1. (1) x and y are indistinguishable asymptotic configurations with difference set F;

2. (2) for every pattern p with finite support $S \subset {\mathbb {Z}^d}$ , we have

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

3. (3) for every pattern p with finite support $S \subset {\mathbb {Z}^d}$ , we have

   

2.1. Properties of indistinguishable asymptotic pairs

Proposition 2.4. Let $S_1 \subset S_2$ be finite subsets of ${\mathbb {Z}^d}$ and let $p \in \Sigma ^{S_1}$ . We have

$$ \begin{align*} \Delta_p(x,y) = \sum_{q \in \Sigma^{S_2}, [q] \subset [p] } \Delta_q(x,y).\end{align*} $$

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.

In particular, to prove that two asymptotic configurations are indistinguishable, it suffices to verify the condition $\Delta _p(x,y)=0$ on patterns p whose supports form a collection of finite subsets of ${\mathbb {Z}^d}$ with the property that every finite subset of ${\mathbb {Z}^d}$ is contained in some set in the collection. In particular, we may consider the collection of all rectangles (products of bounded integer intervals) or the collection of all connected finite subsets of ${\mathbb {Z}^d}$ .

The affine group $\operatorname {Aff}({\mathbb {Z}^d})$ of ${\mathbb {Z}^d}$ is the group of all invertible affine transformations from ${\mathbb {Z}^d}$ into itself. We can represent it as the semidirect product $\operatorname {Aff}({\mathbb {Z}^d}) = {\mathbb {Z}^d} \rtimes \operatorname {GL}_d(\mathbb {Z})$ , where $\operatorname {GL}_d(\mathbb {Z})$ is the group of all invertible $d \times d$ matrices with integer entries, which represents the automorphisms of ${\mathbb {Z}^d}$ , and the factor ${\mathbb {Z}^d}$ on the left represents translations.

Proposition 2.5. Let $(x,y)$ be an indistinguishable asymptotic pair, then:

1. (1) $(\sigma ^u(x),\sigma ^u(y))$ is an indistinguishable asymptotic pair for every $u \in {\mathbb {Z}^d}$ ;

2. (2) $(x\circ A, y \circ A)$ is an indistinguishable asymptotic pair for every $A \in \operatorname {GL}_d(\mathbb {Z})$ .

In particular, the set of indistinguishable asymptotic pairs is invariant under the action of $\operatorname {Aff}({\mathbb {Z}^d})$ .

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.

Let $\Sigma _1,\Sigma _2$ be alphabets. A map $\phi \colon \Sigma _1^{{\mathbb {Z}^d}} \to \Sigma _2^{{\mathbb {Z}^d}}$ is a sliding block code if there exists a finite set $D \subset {\mathbb {Z}^d}$ and map $\Phi \colon \Sigma _1^D \to \Sigma _2$ called the block code such that

$$ \begin{align*} \phi(x)_{u} = \Phi( \sigma^{u}(x)|_{D}) \mbox{ for every } u \in {\mathbb{Z}^d}, x \in \Sigma_1^{{\mathbb{Z}^d}}.\end{align*} $$

Notice that sliding block codes are continuous maps which commute with the shift action, that is, $\sigma ^{u}(\phi (x)) = \phi (\sigma ^{u}(x))$ for every $u \in {\mathbb {Z}^d}$ and $x \in \Sigma _1^{{\mathbb {Z}^d}}$ .

Proposition 2.6. Let $x,y \in \Sigma _1^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair and $\phi \colon \Sigma _1^{{\mathbb {Z}^d}} \to \Sigma _2^{{\mathbb {Z}^d}}$ a sliding block code. The pair $\phi (x),\phi (y) \in \Sigma _2^{{\mathbb {Z}^d}}$ is an indistinguishable asymptotic pair.

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.

Remark 2.7. The property of being an indistinguishable asymptotic pair is also preserved by d-dimensional substitutions and the proof is essentially the same as [9, Lemma 5.2]. We will not make use of this fact anywhere in the article. However, we remark that substitutions might be helpful to answer Question 2, since they were the tool that provides the characterization of indistinguishable asymptotic pairs for $d=1$ , see [9, Theorem C].

Let us recall that a sequence $(x_n)_{n \in \mathbb {N}}$ of configurations in $\Sigma ^{{\mathbb {Z}^d}}$ converges to $x \in \Sigma ^{{\mathbb {Z}^d}}$ if for every $u \in {\mathbb {Z}^d}$ , we have that $(x_n)_{u} = x_{u}$ for all large enough $n \in \mathbb {N}$ . In what follows, we use a notion of convergence for asymptotic pairs which is stronger than the convergence in the prodiscrete topology to ensure that limits of asymptotic pairs are themselves asymptotic. This notion comes from interpreting the equivalence relation of asymptotic pairs as an ‘étale equivalence relation’. For more information on étale equivalence relations and their role in the theory of topological orbit equivalence of Cantor minimal systems, the reader can refer to [33].

Definition 2.8. Let $(x_n,y_n)_{n \in \mathbb {N}}$ be a sequence of asymptotic pairs. We say that $(x_n,y_n)_{n \in \mathbb {N}}$ converges in the asymptotic relation to a pair $(x,y)$ if $(x_n)_{n \in \mathbb {N}}$ converges to x, $(y_n)_{n \in \mathbb {N}}$ converges to y, and there exists a finite set $F \subset {\mathbb {Z}^d}$ so that $x_n|_{{\mathbb {Z}^d} \setminus F} = y_n|_{{\mathbb {Z}^d} \setminus F}$ for all large enough $n \in \mathbb {N}$ .

If $(x_n,y_n)_{n \in \mathbb {N}}$ converges in the asymptotic relation to a pair $(x,y)$ , then the pair $(x,y)$ is necessarily asymptotic. We call $(x,y)$ the étale limit of $(x_n,y_n)_{n \in \mathbb {N}}$ . In the next proposition, we see that indistinguishability is preserved by étale limits.

Proposition 2.9. Let $(x_n,y_n)_{n \in \mathbb {N}}$ be a sequence of asymptotic pairs in $\Sigma ^{{\mathbb {Z}^d}}$ , which converges in the asymptotic relation to $(x,y)$ . If for every $n \in \mathbb {N}$ we have that $(x_n,y_n)$ is indistinguishable, then $(x,y)$ is indistinguishable.

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.

Definition 2.10. Let $x \in \Sigma ^{{\mathbb {Z}^d}}$ be a configuration.

1. (1) x is recurrent if for every $p \in \mathcal {L}(x)$ , the set $\mathsf {occ}_p(x)$ is infinite.

2. (2) x is uniformly recurrent if every $p \in \mathcal {L}(x)$ appears with bounded gaps, that is, for every $p \in \mathcal {L}(x)$ , there exists a finite $K \subset {\mathbb {Z}^d}$ such that for every $u \in {\mathbb {Z}^d}$ , there is $k \in K$ such that $\sigma ^{u+k}(x) \in [p]$ .

Clearly, both recurrence and uniform recurrence are properties that are satisfied either by both configurations in an indistinguishable asymptotic pair simultaneously, or by none of them. Furthermore, it can be easily verified that both of these properties are preserved under the action of $\operatorname {Aff}({\mathbb {Z}^d})$ , just as in Proposition 2.5.

Proposition 2.11. Let $x,y \in \Sigma ^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair. If x is not recurrent, then $x,y$ lie in the same orbit.

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

Remark 2.12. All of the definitions and results stated so far in this section are valid in the more general context where ${\mathbb {Z}^d}$ is replaced by a countable group $\Gamma $ . In Appendix A, we provide definitions and proofs in this more general setting with the hope that it might be useful for further research.

2.2. Known results on dimension $1$

When considering $d=1$ , two phenomena, stated in the lemmas below, simplify the study of indistinguishable asymptotic pairs: every word in the language can be read from the difference set, and recurrent configurations which are part of an indistinguishable asymptotic pair are in fact uniformly recurrent.

Lemma 2.13. [9, Lemma 2.8]

Let $x,y \in \Sigma ^{\mathbb {Z}}$ be a non-trivial indistinguishable asymptotic pair with difference set F. For every finite $S \subset \mathbb {Z}$ and $w \in \mathcal {L}_S(x)$ , there is $u \in F-S$ such that $\sigma ^u(x) \in [w]$ .

Lemma 2.14. [9, Lemma 2.12]

Let $x,y\in \Sigma ^{\mathbb {Z}}$ be a non-trivial indistinguishable asymptotic pair. If x is recurrent, then x is uniformly recurrent.

Gathering Proposition 2.11 and Lemma 2.14, we obtain the following beautiful dichotomy.

Corollary 2.15. [9, Corollary 2.13]

Let $x,y\in \Sigma ^{\mathbb {Z}}$ be a non-trivial asymptotic indistinguishable pair. Then exactly one of the following statements holds:

1. (1) $x = \sigma ^n(y)$ for some non-zero $n \in \mathbb {Z}$ ;

2. (2) x and y are uniformly recurrent.

This dichotomy was the starting point which lead to our characterization of Sturmian configurations through indistinguishable asymptotic pairs in $\mathbb {Z}$ .

Theorem 2.16. [9, Theorem A]

Let $x,y\in \{\mathtt {0},\mathtt {1}\}^{\mathbb {Z}}$ and assume that x is recurrent. The pair $(x,y)$ is an indistinguishable asymptotic pair with difference set $F=\{-1,0\}$ such that $x_{-1}x_{0}=\mathtt {10}$ and $y_{-1}y_{0}=\mathtt {01}$ if and only if there exists $\alpha \in [0,1]\setminus \mathbb {Q}$ such that $x={c}_{\alpha }$ and $y={c}^{\prime }_{\alpha }$ are the lower and upper characteristic Sturmian sequences of slope $\alpha $ .

When $d\geq 2$ , there exist non-trivial indistinguishable asymptotic pairs where both of the above lemmas fail.

Example 2.17. Let $u,v \in \{\mathtt {0},\mathtt {1}\}^{\mathbb {Z}}$ be any indistinguishable asymptotic pair. Consider the configurations $x,y \in \{\mathtt {0},\mathtt {1},\mathtt {2}\}^{\mathbb {Z}^2}$ given by

$$ \begin{align*} x(i,j) = \begin{cases} u(i) & \mbox{if } j = 0,\\ \mathtt{2} & \mbox{if } j \neq 0,\\ \end{cases} \quad \mbox{and} \quad y(i,j) = \begin{cases} v(i) & \mbox{if } j = 0\\ \mathtt{2} & \mbox{if } j \neq 0\\ \end{cases} \quad\mbox{for every } i,j \in \mathbb{Z}. \end{align*} $$

The words $x,y$ form an indistinguishable asymptotic pair which does not satisfy Lemma 2.13 (the symbol $2$ does not occur in the difference set) nor Lemma 2.14 (it is recurrent but not uniformly recurrent). See Figure 7.

Figure 7 An indistinguishable, recurrent, but not uniformly recurrent asymptotic pair $(x,y)$ given by the two characteristic Fibonacci words ( $\alpha = ({\sqrt {5}-1})/{2}$ ) in the central row.

In particular, a convenient consequence of Lemma 2.13 in $d=1$ is that the complexity of any pair of indistinguishable configurations is linear and the bound is given by the size of the difference set. More precisely, if $x,y \in \Sigma ^{\mathbb {Z}}$ is a non-trivial indistinguishable asymptotic pair whose difference set F is contained in an interval I, then for every $n \geq 1$ ,

See [9, Proposition 3.4]. This consequence also fails in the multidimensional setting as shown in the following example.

Example 2.18. Fix $\mathtt {k} \geq 1$ . Let $u,v$ as in Example 2.17 and let $x,y \in \{\mathtt {0},\ldots , \mathtt {k}-1\}^{\mathbb {Z}^2}$ be given by

$$ \begin{align*} x(i,j) = \begin{cases} u(i) & \mbox{if } j = 0,\\ \mathtt{j} \,\mod \mathtt{k} & \mbox{if } j \neq 0, \end{cases} \quad\mbox{and}\quad y(i,j) = \begin{cases} v(i) & \mbox{if } j = 0,\\ \mathtt{j} \,\mod \mathtt{k} & \mbox{if } j \neq 0.\\ \end{cases} \end{align*} $$

We obtain an indistinguishable asymptotic pair whose difference set has size $2$ , but such that the alphabet can be as large as required by taking larger values of $\mathtt {k}$ .

This shows that a na’́ive analogue of the complexity upper-bound given by Lemma 2.13 also fails in the multidimensional setting. However, under special conditions, which we introduce in §2.3, we show that an analogue of Lemma 2.13 holds, which gives us a way to extend Theorem 2.16 to ${\mathbb {Z}^d}$ .

2.3. The flip condition

As shown in the examples of §2.2, indistinguishable asymptotic pairs in ${\mathbb {Z}^d}$ in general are not related to Sturmian configurations as strongly as in dimension $1$ . Despite these discouraging examples, we show that if we consider indistinguishable asymptotic pairs satisfying an additional hypothesis, then many of the good properties from dimension $1$ are still valid and we will be able to obtain a characterization of multidimensional Sturmian configurations in terms of indistinguishable asymptotic pairs.

Definition 2.19. Let $x,y\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an asymptotic pair. We say it satisfies the flip condition if:

1. (1) the difference set of x and y is $F=\{0, -e_1,\ldots ,-e_d\}$ ;

2. (2) the restriction $x|_F$ is a bijection $F \to \{\mathtt {0},\mathtt {1},\ldots ,d\}$ ;

3. (3) the map defined by $x_n\mapsto y_n$ for every $n\in F$ is a cyclic permutation on the alphabet $\{\mathtt {0},\mathtt {1},\ldots ,d\}$ .

Without lost of generality, we assume that $x_{0} = \mathtt {0}$ and $y_n = x_n - \mathtt {1} \bmod (d+\mathtt {1})$ for every $n\in F$ .

The flip condition may be interpreted as a symbolic coding of the act of geometrically flipping the faces of a hypercube at the origin of a discrete hyperplane as in Figure 3.

3. Multidimensional indistinguishable asymptotic pairs and their complexity

The goal of this section is to prove Theorem A, which characterizes indistinguishable asymptotic pairs that satisfy the flip condition through their complexity.

3.1. Special factors in higher dimensions

In one dimension, the factor complexity is related to the valence of left and right special factors [14]. Similarly, in higher dimensions, the pattern complexity is related to the valence of special patterns with connected support. In this section, we shall generalize the notion of special factors to higher dimensions, which will be the fundamental tool in the proof of Theorem A.

Since we will often consider all patterns which appear in configurations $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ , it is practical to introduce the notation and for every finite support $S\subset {\mathbb {Z}^d}$ . For a pattern $w\in \mathcal {L}_S(x,y)$ and a position $\ell \in {\mathbb {Z}^d}\setminus S$ , let the extensions at position $\ell \in {\mathbb {Z}^d}$ of the pattern w within the language $\mathcal {L}(x,y)$ be

Observe that the extensions $E^\ell (w)$ always depend on the language $\mathcal {L}(x,y)$ , but we do not write $E_{x,y}^\ell (w)$ to lighten the notation. Following the terminology for $d=1$ , we say that a pattern $w\in \mathcal {L}_{S}(x,y)$ such that $\#E^{\ell }(w)\geq 2$ is special at position $\ell \in {\mathbb {Z}^d}$ . Notice that we have the equality

$$ \begin{align*} \#\mathcal{L}_{S\cup\{\ell\}}(x,y) = \sum_{w\in\mathcal{L}_{S}(x,y)} \#E^{\ell}(w). \end{align*} $$

Let $\ell ,r \in {\mathbb {Z}^d}\setminus S$ be positions such that $\ell \neq r$ . We say that a pattern $w\in \mathcal {L}_{S}(x,y)$ is bispecial at positions $\ell ,r$ if $\#E^{\ell }(w)\geq 2$ and $\#E^r(w)\geq 2$ . Moreover, for a pattern $w\in \mathcal {L}_S(x,y)$ , let the bilateral extensions at positions $\ell ,r \in {\mathbb {Z}^d}\setminus S$ of the pattern w within the language $\mathcal {L}(x,y)$ be

$$ \begin{align*} E^{\ell,r}(w)=\{(u_{\ell},u_r) \colon u\in\mathcal{L}_{S\cup\{\ell,r\}}(x,y)\text{ and } u|_{S}=w \}. \end{align*} $$

The bilateral multiplicity $m^{\ell ,r}(w)$ of the pattern w at the positions $\ell ,r\in {\mathbb {Z}^d}\setminus S$ within the language $\mathcal {L}(x,y)$ is given by the expression

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

We use the same terminology as when $d=1$ [14] to describe bispecial factors: we say that a pattern $w\in \mathcal {L}_{S}(x,y)$ is strong (respectively weak, neutral) at the positions $\ell ,r\in {\mathbb {Z}^d}\setminus S$ if $m^{\ell ,r}(w)>0$ (respectively $m^{\ell ,r}(w)<0$ , $m^{\ell ,r}(w)=0$ ).

Notice that we may interpret $E^{\ell ,r}(w)$ as an undirected bipartite graph called extension graph, see [11]. The vertices are given by the disjoint union $V = E^{\ell }(w) \sqcup E^{r}(w)$ and we have an edge $(a,b)\in E^{\ell }(w) \times E^{r}(w)$ if there is $u \in \mathcal {L}_{S \cup \{\ell ,r\}}(x,y)$ such that $u_{\ell } = a$ , $u_{r} = b$ and $u|_S = w$ . In this manner, $\# E^{\ell ,r}(w)$ corresponds to the number of edges of the graph and $\# E^{\ell }(w)+\# E^{r}(w)$ corresponds to the number of vertices.

In the next lemma, we show that combinatorial properties of the extension graph $E^{\ell ,r}(w)$ impose lower bounds on the bilateral multiplicity of the pattern w.

Lemma 3.1. Let $w\in \mathcal {L}_S(x,y)$ be a pattern and c be the number of connected components of $E^{\ell ,r}(w)$ .

1. (1) $m^{\ell ,r}(w)\geq 1-c$ .

2. (2) The extension graph $E^{\ell ,r}(w)$ is acyclic if and only if $m^{\ell ,r}(w)=1-c$ .

3. (3) If $E^{\ell ,r}(w)$ is connected, then $m^{\ell ,r}(w)\geq 0$ .

4. (4) If $E^{\ell ,r}(w)$ is connected and contains a cycle, then $m^{\ell ,r}(w)>0$ .

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

3.2. Complexity of indistinguishable asymptotic pairs with the flip condition

Here we shall show that the flip condition along with indistinguishability impose that every pattern in the language must occur in a position which intersects the difference set. This property implies an upper bound for the pattern complexity.

Lemma 3.2. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair satisfying the flip condition. For every finite non-empty subset $S \subset {\mathbb {Z}^d}$ , we have $\mathcal {L}_S(x,y)\subset \{\sigma ^{n}(x)|_{S}\colon n\in F-S\}$ . In particular, $\#\mathcal {L}_S(x,y)\leq \#(F-S)$ .

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

Lemma 3.2 generalizes Lemma 2.13 which is valid in $\mathbb {Z}$ without resorting to the flip condition. We say that a permutation is cyclic if it consists of a single cycle and has no fixed points. To obtain a lower bound and thus the equality, we will use the following technical result.

Lemma 3.3. Let $\pi \colon U\to U$ be a cyclic permutation on a finite set U. Let $A\subset U$ and $f\colon A\to B$ be a surjective map for some finite set B. If $A\neq U$ , then

$$ \begin{align*} \#\{(a,f(a))\mid a\in A\} \cup \{(\pi(a),f(a))\mid a\in A\} \geq \# A + \#B. \end{align*} $$

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

We will now use Lemma 3.3 to prove a lower bound for the pattern complexity of asymptotic pairs satisfying the flip condition. Notice that we do not use indistinguishability in what follows.

Lemma 3.4. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an asymptotic pair satisfying the flip condition. Then for every finite non-empty connected subset $S\subset {\mathbb {Z}^d}$ , we have

$$ \begin{align*} \#\mathcal{L}_S(x,y)\geq \#(F-S). \end{align*} $$

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

3.3. Properties of asymptotic pairs with the flip condition and complexity $\#(F-S)$

In this subsection, we fix an asymptotic pair $(x,y)$ which satisfies the flip condition and study the properties that we can obtain from the assumption that $\mathcal {L}_S(x,y)= \#(F-S)$ for every non-empty connected finite $S\subset {\mathbb {Z}^d}$ . For the remainder of the subsection, we fix a (possibly empty) connected set $S\subset {\mathbb {Z}^d}$ and $\ell ,r \in {\mathbb {Z}^d}\setminus S$ such that $S\cup \{\ell \}, S\cup \{r\}$ and $S\cup \{\ell ,r\}$ are connected. We also convene that $\mathcal {L}_{\varnothing }(x,y) = \{\varepsilon \}$ , where $\varepsilon $ is the empty pattern. As our proof will be by induction, we shall often make use of the following condition which will correspond to the inductive hypothesis.

Definition 3.5. We say that $(x,y)$ satisfies condition (IND) if for every $S' \in \{S, S\cup \{\ell \}, S\cup \{r\}\}$ , any pattern $p' \in \mathcal {L}_{S'}(x,y)$ occurs intersecting F in x, that is, for every $p' \in \mathcal {L}_{S'}(x,y)$ , there is $t'\in F-S'$ such that we have $\sigma ^{t'}(x)\in [p']$ .

It is clear that condition (IND) implies that $\# \mathcal {L}_{S'}(x,y)\leq \#(F-S')$ . By Lemma 3.4, we have the other inequality and thus condition (IND) in fact states two things: that $\# \mathcal {L}_{S'}(x,y)= \#(F-S')$ and that the position $t'\in F-S'$ such that $\sigma ^{t'}(x)\in [p']$ is unique.

Our general strategy will be similar to the proof of Lemma 3.4, that is, we will look at the positions in $F-(S\cup \{\ell ,r\})$ for which only one of $\{\ell ,r\}$ intersects the difference set and nothing else does, which will provide us with the means to describe $E^{\ell ,r}(w)$ for words $w \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^S$ and ultimately to prove Theorem A.

Let $w \in \mathcal {L}_S(x,y)$ . We are going to define three special subsets of $E^{\ell ,r}(w)$ :

$$ \begin{align*} \Gamma_{\ell}(w) &= \{ (x_{t+\ell},x_{t+r})\in E^{\ell,r}(w) : \mbox{ there is }\\ &t \in {\mathbb{Z}^d} \mbox{ such that } \sigma^t(x) \in [w], t+\ell \in F, (t+(S \cup \{r\})) \cap F = \varnothing \}; \end{align*} $$

$$ \begin{align*} \Gamma_{r}(w) &= \{ (x_{t+\ell},x_{t+r})\in E^{\ell,r}(w) : \mbox{ there is }\\ & t \in {\mathbb{Z}^d} \mbox{ such that } \sigma^t(x) \in [w], t+r \in F, (t+(S \cup \{\ell\})) \cap F = \varnothing \}; \end{align*} $$

$$ \begin{align*} \Gamma_{\star}(w) &= \{ (x_{t+\ell},x_{t+r})\in E^{\ell,r}(w) : \mbox{ there is }\\ & t \in {\mathbb{Z}^d} \mbox{ with } \sigma^t(x) \in [w] \mbox{ such that either } (t+S) \cap F \neq \varnothing \\ &\quad \mbox{or } t+\ell,t+r \in F \mbox{ and } (t+S) \cap F = \varnothing \}. \end{align*} $$

The set $\Gamma _{\ell }(w)$ consists of all edges in $E^{\ell ,r}(w)$ that can be obtained by a pattern (with support $S \cup \{\ell ,r\}$ and whose restriction to S is w) which intersects F solely on position $\ell $ . Similarly, $\Gamma _{r}(w)$ consists of all edges in $E^{\ell ,r}(w)$ that can be obtained by a pattern which intersects F solely on position r. Finally, $\Gamma _{\star }(w)$ represents the edges in $E^{\ell ,r}(w)$ that occur in some pattern which intersects F, but does so either having S intersect F, or having both $\ell $ and r do so at the same time. Notice that these three sets cover all possible ways that $S\cup \{\ell ,r\}$ can intersect the difference set F.

In particular, if we want to show that no pattern appears twice on x intersecting the difference set, we would need to show that $\Gamma _{\ell }(w) \cap \Gamma _{r}(w) = \varnothing $ . This will be the main goal of this section.

We shall first show that under condition (IND), we can use the set $\Gamma _{\star }(w)$ to bound the number of connected components of $E^{\ell ,r}(w)$ .

Lemma 3.6. For a symbol $\kappa \in \{\mathtt {0},\mathtt {1},\ldots ,d\}$ , let us denote $\kappa ^* = (\kappa -1) \bmod {(d+1)}$ . Assume condition (IND) and consider the bipartite graph $E^{\ell ,r}(w)$ .

1. (1) If $(a,b) \in \Gamma _{\ell }(w)$ , then $(a^*,b)\in E^{\ell ,r}(w)$ and there is $b'$ such that $(a^*,b') \in \Gamma _{\ell }(w)\cup \Gamma _{\star }(w)$ .

2. (2) If $(a,b) \in \Gamma _{r}(w)$ , then $(a,b^*)\in E^{\ell ,r}(w)$ and there is $a'$ such that $(a',b^*) \in \Gamma _{r}(w)\cup \Gamma _{\star }(w)$ .

3. (3) The number of connected components of $E^{\ell ,r}(w)$ is bounded above by $\#\Gamma _{\star }(w)$ .

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

Next we will have to estimate the size of $\Gamma _{\star }(w)$ to have a lower bound on the multiplicities $m^{\ell ,r}(w)$ . It turns out that one particular case is harder to deal with and thus we shall give it a special name to simplify the upcoming statements.

Definition 3.7. Let $S\subset {\mathbb {Z}^d}$ be a connected non-empty finite support and $\ell ,r\in {\mathbb {Z}^d}\setminus S$ with $\ell \neq r$ . We say that $(S,\ell ,r)$ is evil if there exists $t\in {\mathbb {Z}^d}$ such that $\{t+\ell ,t+r\}\subset F$ and $(t+S)\cap F=\varnothing $ .

We also say that $w \in \mathcal {L}_S(x)$ is an evil pattern if for $t\in {\mathbb {Z}^d}$ such that $\{t+\ell ,t+r\}\subset F$ and $(t+S)\cap F=\varnothing $ , we have $x_{t+s} = w_s$ for every $s \in S$ .

We remark that by definition, the empty pattern $\varepsilon $ with support $S = \varnothing $ is not evil. Definition 3.7 is illustrated in Figure 8 when $d=2$ .

Figure 8 $(S_1,\ell _1,r_1)$ is evil, as both $\ell _1$ and $r_1$ can simultaneously overlap F without $S_1$ doing so. Notice that $(S_2,\ell _2,r_2)$ is not evil since $\ell _2-r_2\notin F-F$ . $(S_3,\ell _3,r_3)$ is also not evil since the unique $t\in \mathbb {Z}^2$ with $t+\{\ell _3,r_3\}\subset F$ is such that $(t+S_3)\cap F\neq \varnothing $ .

Lemma 3.8. Let $w \in \mathcal {L}_{S}(x,y)$ and assume condition (IND). If w is an evil pattern, then $m^{\ell ,r}(w) \geq -1$ . If w is non-evil, then $m^{\ell ,r}(w) \geq 0$ .

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.

Next we shall show that the bound in Lemma 3.8 is tight. To do so, we will produce a formula for the sum of a bilateral multiplicities.

Lemma 3.9. Suppose that $\#\mathcal {L}_{S \cup \{\ell ,r\}}(x,y) = \#(F-(S \cup \{\ell ,r\}))$ and that condition (IND) holds. For every $w \in \mathcal {L}_{S}(x,y)$ , let c be the number of connected components of $E^{\ell ,r}(w)$ . We have

$$ \begin{align*} m^{\ell,r}(w) = 1-c = \begin{cases} -1 & \text{if } w \text{ is evil,}\\ 0 & \text{otherwise.} \end{cases} \end{align*} $$

In particular, the extension graph $E^{\ell ,r}(w)$ contains no cycle.

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.

Lemma 3.10. Suppose that $\#\mathcal {L}_{S \cup \{\ell ,r\}}(x,y) = \#(F-(S \cup \{\ell ,r\}))$ and that condition (IND) holds. For every non-evil $w \in \mathcal {L}_{S}(x,y)$ , if $\Gamma _{\ell }(w) \cap \Gamma _{r}(w)\neq \varnothing $ , then the extension graph $E^{\ell ,r}(w)$ contains a cycle.

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

Remark 3.11. Using a variation of the previous argument, it is also possible to show for evil patterns that if $\Gamma _{\ell }(w) \cap \Gamma _{r}(w)\neq \varnothing $ , then $E^{\ell ,r}(w)$ contains a cycle. However, we shall not need that statement for the proof of Theorem A.

Proposition 3.12. Let $d\geq 1$ and $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\}$ . Assume that for every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ , the pattern complexity of x and y is $\#\mathcal {L}_S(x)=\#\mathcal {L}_S(y) = \#(F-S)$ . Then for every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ and $p \in \mathcal {L}_S(x)\cup \mathcal {L}_S(y)$ , we have

(3) $$ \begin{align} \#(\mathrm{\sf occ}_p(x)\setminus \mathrm{\sf occ}_p(y)) = 1 = \#(\mathrm{\sf occ}_p(y)\setminus \mathrm{\sf occ}_p(x)). \end{align} $$

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

3.4. Proof of Theorem A

We shall now prove our characterization of indistinguishable asymptotic pairs with the flip condition through complexity. For the convenience of the reader, we recall the statement.

Theorem A. Let $d\geq 1$ and $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\}$ . The following are equivalent.

1. (i) For every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ and $p \in \mathcal {L}_S(x)\cup \mathcal {L}_S(y)$ , we have

   $$ \begin{align*} \#(\mathrm{\sf occ}_p(x)\setminus \mathrm{\sf occ}_p(y)) = 1 = \#(\mathrm{\sf occ}_p(y)\setminus \mathrm{\sf occ}_p(x)). \end{align*} $$

2. (ii) The asymptotic pair $(x,y)$ is indistinguishable.

3. (iii) For every non-empty finite connected subset $S\subset {\mathbb {Z}^d}$ , the pattern complexity of x and y is

   $$ \begin{align*}\#\mathcal{L}_S(x)=\#\mathcal{L}_S(y) = \#(F-S).\end{align*} $$

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

Theorem A gives us two descriptions of the language of x and y for any connected support.

Corollary 3.13. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair satisfying the flip condition. For every finite non-empty connected subset $S \subset {\mathbb {Z}^d}$ , we have that the maps given by $n\mapsto \sigma ^{n}(x)|_{S}$ and $n\mapsto \sigma ^{n}(y)|_{S}$ are two distinct bijections from $F-S$ to $\mathcal {L}_S(x)$ .

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

3.5. Rectangular pattern complexity

We have so far shown that for any indistinguishable pair $(x,y)\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ which satisfies the flip condition and any finite non-empty connected subset $S \subset {\mathbb {Z}^d}$ , we have $\# \mathcal {L}_S(x) = \# \mathcal {L}_S(y) = \#(F-S).$ This equation takes a beautiful form when S is a d-dimensional box.

For a positive integer vector $m = (m_1,\ldots ,m_d)\in \mathbb {N}^d$ , let $S(m) \subset {\mathbb {Z}^d}$ denote the support

which represents the d-dimensional box whose sides have lengths $m_1,\ldots ,m_d$ . Also, for $x \in \Sigma ^{{\mathbb {Z}^d}}$ , we write $\mathcal {L}_{m}(x) = \mathcal {L}_{S(m)}(x)$ to denote the set of patterns with support $S(m)$ occurring in x. We refer to the function which maps m to $\# \mathcal {L}_{m}(x)$ as the rectangular pattern complexity of 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*} $$

The geometrical interpretation of the rectangular complexity of an indistinguishable pair $(x,y)\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ which satisfies the flip condition provides meaning to a curious relation that one can find perhaps by boredom or accident. Let us express the rectangular complexity as a real map $f \colon \mathbb {R}^{d} \to \mathbb {R}$ given by

$$ \begin{align*}f(x_1,\ldots,x_d) = x_1\cdots x_d \bigg( 1+ \frac{1}{x_1} + \cdots + \frac{1}{x_d} \bigg). \end{align*} $$

If we consider the derivative of f with respect to some $x_i$ , we obtain

$$ \begin{align*} \frac{\partial }{\partial x_i}f(x_1\cdots x_d) & = \frac{x_1\cdots x_d}{x_i} \bigg( 1+ \frac{1}{x_1} + \cdots + \frac{1}{x_d} \bigg) + x_1\cdots x_d \bigg( \frac{-1}{x_i^2}\bigg)\\ & = \frac{x_1\cdots x_d}{x_i}\bigg( 1+ \frac{1}{x_1} + \cdots + \frac{1}{x_d} - \frac{1}{x_i} \bigg). \end{align*} $$

In other words, the derivative of the complexity function of a d-dimensional indistinguishable pair $(x,y)\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ which satisfies the flip condition with respect to any variable yields the rectangular complexity function of a $(d-1)$ -dimensional indistinguishable pair $(x',y')\in \{\mathtt {0},\mathtt {1},\ldots ,d-1\}^{{\mathbb {Z}^d}}$ which satisfies the flip condition. The geometrical interpretation is that as this complexity corresponds to the volume of a d-dimensional box of size $(m_1\cdots m_d)$ plus the sum of the volume of the $(d-1)$ -dimensional faces, then taking the derivative with respect to a canonical direction $e_i$ yields from the box the volume ${m_1\cdots m_d}/{m_i}$ of the corresponding $(d-1)$ -dimensional face orthogonal to $e_i$ , and for each of the $(d-1)$ -dimensional faces, we either obtain the $(d-2)$ -dimensional face orthogonal to $e_i$ , or $0$ if the $(d-1)$ -dimensional face is orthogonal to $e_i$ .

4. Characteristic Sturmian configurations in ${\mathbb {Z}^d}$

In this section, we introduce characteristic multidimensional Sturmian configurations from codimension-one cut and project schemes. We show that they are examples of indistinguishable asymptotic pairs satisfying the flip condition.

4.1. Codimension-one cut and project schemes for symbolic configurations

Cut and project schemes of codimension-one (dimension of the internal space) can be defined in several ways (for a different definition, see [20]). In what follows, we follow the formalism of [6, §7], but note that we need to adapt it to describe symbolic configurations over a lattice ${\mathbb {Z}^d}$ . Let $d\geq 1$ be an integer and

$$ \begin{align*} \begin{array}{llll} \pi:&\!\!\mathbb{R}^{d+1} &\to& \mathbb{R}^d\\ &\!\!(x_0,x_1,\ldots,x_d) &\mapsto& (x_1,\ldots,x_d) \end{array} \end{align*} $$

be the projection of $\mathbb {R}^{d+1}$ in the physical space $\mathbb {R}^d$ . Let $\alpha _0=1$ , $\alpha _{d+1}=0$ , and $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ be a totally irrational vector, that is, such that $\{1,\alpha _1, \ldots , \alpha _d\}$ is linearly independent over $\mathbb {Q}$ . Let

$$ \begin{align*} \begin{array}{llll} \pi_{\mathrm{int}}:&\!\!\mathbb{R}^{d+1} &\to& \mathbb{R}/\mathbb{Z} \\ &\!\!(x_0,x_1,\ldots,x_d) &\mapsto& \sum_{i=0}^d x_i \alpha_i \end{array} \end{align*} $$

be the projection of $\mathbb {R}^{d+1}$ in the internal space $\mathbb {R}/\mathbb {Z}$ . Consider the lattice $\mathcal {L}=\mathbb {Z}^{d+1}\subset \mathbb {R}^{d+1}$ whose image is $\pi (\mathcal {L})=\mathbb {Z}^d$ . This is the setting of a codimension-one cut and project scheme summarized in the following diagram adapted from [6, §7.2]:

Remark 4.1. The usual condition imposed in cut and project schemes is that $\pi |_{\mathcal {L}}$ is injective, see [6, §7.2], which does not hold in our case. Here, it is more convenient to relax this condition to

(4) $$ \begin{align} \operatorname{\mathrm{Ker}}\pi\cap\mathcal{L} \subseteq \operatorname{\mathrm{Ker}}\pi_{\mathrm{int}}. \end{align} $$

Of course, if $\pi |_{\mathcal {L}}$ is injective, then equation (4) is satisfied since $\operatorname {\mathrm {Ker}}\pi \cap \mathcal {L} = \{0\} \subset \operatorname {\mathrm {Ker}}\pi _{\mathrm {int}}$ . Also, we may observe that if equation (4) holds, then the star map $\pi (\mathcal {L})\to \pi _{\mathrm {int}}(\mathcal {L})$ is still well defined:

With the definition of $\pi $ and $\pi _{\mathrm {int}}$ above, we have that equation (4) holds since $\operatorname {\mathrm {Ker}}\pi \cap \mathcal {L}=\mathbb {Z}\times \{0\}^d \subseteq \operatorname {\mathrm {Ker}}\pi _{\mathrm {int}}$ . Moreover,

(5) $$ \begin{align} n^\star=\alpha\cdot n \bmod 1 \end{align} $$

for every $n\in \pi (\mathcal {L})={\mathbb {Z}^d}$ . For a given window $W\subset \mathbb {R}/\mathbb {Z}$ in the internal space,

is the projection set within the cut and project scheme, where $L=\pi (\mathcal {L})$ . If $W\subset \mathbb {R}/\mathbb {Z}$ is a relatively compact set with non-empty interior, any translate $t+\curlywedge (W)$ of the projection set, $t\in \mathbb {R}^d$ , is called a model set.

If $W=[0,1)$ , then $\curlywedge (W)={\mathbb {Z}^d}$ . Thus, if $W\subset [0,1)$ , then $\curlywedge (W)\subset {\mathbb {Z}^d}$ . Moreover, if $\{W_i\}_{i\in \{0,\ldots ,d\}}$ is a partition of $[0,1)$ , then $\{\curlywedge (W_i)\}_{i\in \{0,\ldots ,d\}}$ is a partition of ${\mathbb {Z}^d}$ . Using this idea, we now build configurations $\mathbb {Z}^d\to \{\mathtt {0},\mathtt {1},\ldots ,d\}$ according to a partition of $\mathbb {R}/\mathbb {Z}$ , or equivalently of the interval $[0,1)$ , into consecutive intervals.

Definition 4.2. Let $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ be a totally irrational vector and $\tau $ be the permutation of $\{\mathtt {1},\ldots ,d\}\cup \{\mathtt {0},d+1\}$ which fixes $\{\mathtt {0},d+1\}$ and such that $0=\alpha _{\tau (d+1)}<\alpha _{\tau (d)}<\cdots <\alpha _{\tau (\mathtt {1})}<\alpha _{\tau (\mathtt {0})}=1$ . For every $i\in \{0,1,\ldots ,d\}$ , let

$$ \begin{align*} W_i &= [1-\alpha_{\tau(i)},1-\alpha_{\tau(i+1)}), \quad W^{\prime}_i = (1-\alpha_{\tau(i)},1-\alpha_{\tau(i+1)}] \end{align*} $$

be such that $\{W_i\}_{i\in \{0,\ldots ,d\}}$ and $\{W^{\prime }_i\}_{i\in \{0,\ldots ,d\}}$ are two partitions of the interval $[0,1)$ . The configurations

$$ \begin{align*} \begin{array}{llll} c_{\alpha}:&\!\!{\mathbb{Z}^d} &\to& \{\mathtt{0},\mathtt{1},\ldots,d\}\\ &\!\!n &\mapsto& i \text{ if } n^\star\in W_i \end{array} \quad \text{and} \quad \begin{array}{llll} c^{\prime}_{\alpha}:&\!\!{\mathbb{Z}^d} &\to& \{\mathtt{0},\mathtt{1},\ldots,d\}\\ &\!\!n &\mapsto & i \text{ if } n^\star\in W^{\prime}_i \end{array} \end{align*} $$

are respectively the lower and upper characteristic d-dimensional Sturmian configurations with slope $\alpha \in [0,1)^d$ . Moreover, if $\rho \in \mathbb {R}/\mathbb {Z}$ , the configurations

$$ \begin{align*} \begin{array}{llll} s_{\alpha,\rho}:&\!\!{\mathbb{Z}^d} &\to& \{\mathtt{0},\mathtt{1},\ldots,d\}\\ &\!\!n &\mapsto& i \text{ if } n^\star+\rho\in W_i \end{array} \quad \text{and} \quad \begin{array}{llll} s^{\prime}_{\alpha,\rho}:&\!\!{\mathbb{Z}^d} &\to& \{\mathtt{0},\mathtt{1},\ldots,d\}\\ &\!\!n &\mapsto& i \text{ if } n^\star+\rho\in W^{\prime}_i \end{array} \end{align*} $$

are respectively the lower and upper d-dimensional Sturmian configurations with slope $\alpha \in [0,1)^d$ and intercept $\rho \in \mathbb {R}/\mathbb {Z}$ .

It turns out that configurations $s_{\alpha ,\rho }$ and $s^{\prime }_{\alpha ,\rho }$ can be expressed by a formula involving a sum of differences of floor functions thus extending the definition of Sturmian sequences by mechanical sequences [31]. It also reminds of recent progresses on Nivat’s conjecture where configurations with low pattern complexity are proved to be sums of periodic configurations [24, 36], although here it involves a sum of non-periodic configurations.

Lemma 4.3. Let $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ be a totally irrational vector and $\rho \in \mathbb {R}/\mathbb {Z}$ . The lower and upper d-dimensional Sturmian configurations with slope $\alpha $ and intercept $\rho $ are given by the following rules:

$$ \begin{align*} \begin{array}{llll} s_{\alpha,\rho}:&\!\!{\mathbb{Z}^d} &\to& \{\mathtt{0},\mathtt{1},\ldots,d\}\\ &\!\!n &\mapsto& \sum\limits_{i=1}^d (\lfloor\alpha_i+n\cdot\alpha+\rho\rfloor -\lfloor n\cdot\alpha+\rho\rfloor) \end{array} \end{align*} $$

and

$$ \begin{align*} \begin{array}{llll} s^{\prime}_{\alpha,\rho}:&\!\!{\mathbb{Z}^d} &\to & \{\mathtt{0},\mathtt{1},\ldots,d\}\\ &\!\!n &\mapsto& \sum\limits_{i=1}^d (\lceil\alpha_i+n\cdot\alpha+\rho\rceil -\lceil n\cdot\alpha+\rho\rceil). \end{array} \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 $ ).

When $d=1$ , $s_{\alpha ,\rho }$ and $s^{\prime }_{\alpha ,\rho }$ correspond to lower and upper mechanical words defined in [31], see also [1, 3, 29]. When $d=2$ , they are in direct correspondence to discrete planes as defined in [4, 5, 12]. See also Jolivet’s PhD thesis [23]. In general, we say that a configuration in $\{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ is Sturmian if it coincides either with $s_{\alpha ,\rho }$ or $s^{\prime }_{\alpha ,\rho }$ for some $\rho \in \mathbb {R}$ and totally irrational $\alpha \in [0,1)^d$ .

When $\rho =0$ , we have $s_{\alpha ,0}=c_{\alpha }$ and $s^{\prime }_{\alpha ,0}=c^{\prime }_{\alpha }$ . Thus, equation (2) in §1 follows from Lemma 4.3.

The fact that the configurations $c_\alpha $ and $c^{\prime }_\alpha $ are encodings of codimension-one cut and project schemes is illustrated with $\alpha =(\alpha _1,\alpha _2)=(\sqrt {2}/2,\sqrt {19}-4)$ in Figure 3, in which we see a discrete plane in dimension 3 of normal vector $(1-\alpha _1,\alpha _1-\alpha _2,\alpha _2) \approx (0.293, 0.348, 0.359)$ . Below, we provide another example and compute its language for small rectangular supports.

Example 4.4. Let $\alpha ={{(\sqrt{3}-1,\sqrt{2}-1)}} $ . The two-dimensional characteristic Sturmian configurations $c_{\alpha }$ and $c^{\prime }_{\alpha }$ are shown in Figure 9. To motivate the main ideas of the proofs in the next section, we explicitly compute the language of these configurations for some rectangular supports of small size.

Figure 9 Two-dimensional configurations $c_{\alpha }$ and $c^{\prime }_{\alpha }$ when $\alpha ={{(\sqrt{3}-1,\sqrt{2}-1)}} $ are shown on the support . The two configurations are equal except on the difference set $F=\{(0,0),(-1,0), (0,-1)\}$ shown in darker hue.

The patterns of shape $(1,3)$ that we see in $c_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ and $c^{\prime }_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ are

The patterns of shape $(3,1)$ that we see in $c_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ and $c^{\prime }_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ are

The patterns of shape $(2,2)$ that we see in $c_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ and $c^{\prime }_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ are

The patterns of shape $(2,3)$ that we see in $c_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ and $c^{\prime }_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ are

The patterns of shape $(3,2)$ that we see in $c_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ and $c^{\prime }_{{(\sqrt{3}-1,\sqrt{2}-1)}} $ are

We may check in Figure 9 that each of these patterns has exactly one occurrence intersecting the difference set. This is the main tool that allows us to show that d-dimensional characteristic Sturmian configurations are indistinguishable.

4.2. Characteristic d-dimensional Sturmian configurations and the flip condition

Lemma 4.5. For any $\alpha \in [0,1)^d$ and $\rho \in \mathbb {R}$ , the configurations $s_{\alpha ,\rho }$ and $s^{\prime }_{\alpha ,\rho }$ are uniformly recurrent.

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.

Lemma 4.6. If $\alpha $ is totally irrational, then $\big (c_{\alpha },c^{\prime }_{\alpha }\big )$ is an asymptotic pair whose difference set is $F = \{0, -e_1, \ldots , -e_d \}$ .

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

Proposition 4.7. Let $\alpha \in [0,1)^d$ be totally irrational. The characteristic d-dimensional Sturmian configurations $c_{\alpha }$ and $c^{\prime }_{\alpha }$ satisfy the flip condition.

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.

4.3. Characteristic d-dimensional Sturmian configurations are indistinguishable

For every $\mathtt {i}$ with $\mathtt {0}\leq \mathtt {i}\leq d$ , the set $W_{\mathtt {i}}$ is a left-closed right-open interval sharing the same end-points as $W^{\prime }_{\mathtt {i}}$ which is a right-closed left-open interval. We have that $\mathcal {P}=\{W_{\mathtt {i}}\}_{\mathtt {0}\leq \mathtt {i}\leq d}$ and $\mathcal {P}'=\{W^{\prime }_{\mathtt {i}}\}_{\mathtt {0}\leq \mathtt {i}\leq d}$ are two partitions of the circle $\mathbb {R}/\mathbb {Z}$ illustrated in Figure 10.

Figure 10 Define $\alpha _{\mathtt {0}} = 1$ and $\alpha _{d+\mathtt {1}}=0$ , and let $\tau $ be the permutation of $\{\mathtt {1},\ldots ,d\}\cup \{\mathtt {0},d+1\}$ which fixes $\{\mathtt {0},d+1\}$ and such that $0<\alpha _{\tau (d)}<\cdots <\alpha _{\tau (\mathtt {1})}<1$ . The intervals $W_i=[1-\alpha _{\tau (\mathtt {i})}, 1-\alpha _{\tau (\mathtt {i+1})})$ form a partition of the circle $\mathbb {R}/\mathbb {Z}$ and similarly for the intervals $W^{\prime }_i=(1-\alpha _{\tau (\mathtt {i})}, 1-\alpha _{\tau (\mathtt {i+1})}]$ .

Let $S\subset {\mathbb {Z}^d}$ be finite and $p\colon S\to \{\mathtt {0},\mathtt {1},\ldots ,d\}$ be a pattern with support S. Let

(8) $$ \begin{align} I_p = \bigcap_{n\in S} (W_{p(n)} - \alpha\cdot n) \quad \text{and} \quad I^{\prime}_p = \bigcap_{n\in S} (W^{\prime}_{p(n)} - \alpha\cdot n). \end{align} $$

Additionally, let $\mathcal {P}^S = \{ I_p\}_{p \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^S}$ and $(\mathcal {P}')^S = \{ I^{\prime }_p\}_{p \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^S}$ be the partitions of $\mathbb {R}/\mathbb {Z}$ determined by the support S. Notice that the sets $I_p$ and $I^{\prime }_p$ have the same interior (which is non-empty if and only if these sets are non-empty) and thus differ only on their boundary points.

The pattern p appears in $c_{\alpha }$ if and only if $\operatorname {Int}(I_p)\neq \varnothing $ . Similarly, the pattern p appears in $c^{\prime }_{\alpha }$ if and only if $\operatorname {Int}(I^{\prime }_p)\neq \varnothing $ . As $\operatorname {Int}(I_p) = \operatorname {Int}(I^{\prime }_{p})$ , we obtain that p appears in $c_{\alpha }$ if and only if p appears in $c^{\prime }_{\alpha }$ . Therefore, the configurations $c_{\alpha }$ and $c^{\prime }_{\alpha }$ share the same language, that is, $\mathcal {L}_S(c_{\alpha }) = \mathcal {L}_S(c^{\prime }_{\alpha })$ for every finite $S \subset {\mathbb {Z}^d}$ . Also, $\#\mathcal {L}_S(c_{\alpha })$ is equal to the number of non-empty sets $I_p$ for $p \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^S$ .

Lemma 4.8. For every non-empty connected finite set $S\subset {\mathbb {Z}^d}$ and pattern $p \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{S}$ , the sets $I_{p},I^{\prime }_{p}$ are either empty or intervals in $\mathbb {R}/\mathbb {Z}$ .

Proof. We only prove this for $I_{p}$ , the argument for $I^{\prime }_{p}$ follows from the considerations stated above. Let us notice that the intersection of two left-closed, right-open intervals on the circle is either empty, a left-closed and right-open interval, or a disconnected union of them. This third case can only occur when the sum of the lengths of both intervals exceeds $1$ .

Let us now prove the lemma by induction. If $S =\{n\}$ is a singleton, then the result is direct: if $p(n)=\mathtt {i}$ , we have that $I_{p} = I_{\mathtt {i}}-\alpha \cdot n$ , which is clearly a non-empty interval on the circle.

Now let S be a non-empty connected finite set, $p \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{S}$ , and suppose the result holds for every strict non-empty connected subset of S. As S is finite, we can find $n \in S$ such that $S' = S \setminus \{n\}$ is also connected by removing a leaf in some spanning tree of S. Let $p'$ be the restriction of p to $S'$ , then we have

$$ \begin{align*} I_p = I_{p'} \cap (I_{p(n)}-\alpha \cdot n). \end{align*} $$

By the inductive hypothesis, $I_{p'}$ is an interval. We also have that $(I_{p(n)}-\alpha \cdot n)$ is an interval. Therefore, the only case where $I_p$ might not be an interval is when the sum of the lengths of $I_{p'}$ and $I_{p(n)}$ is strictly larger than $1$ .

As S is connected, there is $1 \leq j \leq d$ such that $n - e_j \in S'$ or $n+e_j \in S'$ . Let us proceed in the case where $n - e_j \in S'$ , the other case is analogous. We have that $I_{p'} \subset I_{p(n-e_j)} - \alpha \cdot (n-e_j)$ . Notice that if $p(n-e_j)\neq p(n)$ , then the sum of the lengths of $I_{p'}$ and $I_{p(n)}$ is at most $1$ , and hence the only issue can arise when $p(n-e_j)= p(n)$ (and $I_{p(n)}$ has length larger than $\tfrac 12$ ).

Suppose it is the case and let $\mathtt {i} = p(n-e_j)= p(n)$ . Let $\pi $ be the permutation of $\{\mathtt {1},\ldots ,d\} \cup \{\mathtt {0},d+1\}$ which fixes $\mathtt {0}$ and $d+1$ , and such that

$$ \begin{align*}0= \alpha_{\pi(d+\mathtt{1})}< \alpha_{\pi(d)} < \cdots < \alpha_{\pi(\mathtt{1})} < \alpha_{\pi(\mathtt{0})}=1.\end{align*} $$

With this, $I_{\mathtt {i}} = [1-\alpha _{\pi (\mathtt {i})}, 1-\alpha _{\pi (\mathtt {i+1})})$ , and hence we have

$$ \begin{align*} I_{p'} \subset I_{\mathtt{i}} - \alpha \cdot (n-e_j) = [1-\alpha_{\pi(\mathtt{i})}+\alpha_{\mathtt{j}}, 1-\alpha_{\pi(\mathtt{i+1})}+\alpha_{\mathtt{j}}) - \alpha \cdot n,\end{align*} $$

$$ \begin{align*} I_{p(n)} - \alpha \cdot n = [1-\alpha_{\pi(\mathtt{i})}, 1-\alpha_{\pi(\mathtt{i+1})}) - \alpha \cdot n. \end{align*} $$

There are two cases to consider.

1. (1) If $\alpha _j \leq \alpha _{\pi (\mathtt {i+1})}$ , we have that $I_{p'} + \alpha \cdot n \subset (I_{\mathtt {i}}+\alpha _j) \subset [0,1)$ . It follows that $I_p + \alpha \cdot n = (I_{p'} + \alpha \cdot n) \cap I_{p(n)}$ is either empty or an interval in $\mathbb {R}/\mathbb {Z}$ and therefore so is $I_{p}$ .

2. (2) If $\alpha _j \geq \alpha _{\pi (\mathtt {i})}$ , we have $I_{p'} + \alpha \cdot n \subset (I_{p}+\alpha _j) \subset [1,2)$ . It follows that $I_p + \alpha \cdot n = (I_{p'} + \alpha \cdot n) \cap I_{p(n)}$ is either empty or an interval in $\mathbb {R}/\mathbb {Z}$ and therefore so is $I_{p}$ .

We conclude that in both of the problematic cases, $I_{p}$ is either empty or an interval in $\mathbb {R}/\mathbb {Z}$ .

Lemma 4.9. Let $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ be totally irrational and S be a non-empty finite connected subset of ${\mathbb {Z}^d}$ . For every $p \in \mathcal {L}_S(c_{\alpha })=\mathcal {L}_S(c^{\prime }_{\alpha })$ , the sets $\mathsf {occ}_p(c_{\alpha })\cap (F-S)$ and $\mathsf {occ}_p(c^{\prime }_{\alpha })\cap (F-S)$ are singletons.

Proof. The partition $\mathcal {P}=\{I_{\mathtt {i}}\}_{\mathtt {0}\leq \mathtt {i} \leq d}$ of $\mathbb {R}/\mathbb {Z}$ is a partition into $d+1$ intervals corresponding to the $d+1$ symbols in the alphabet. The boundary points of the intervals $I_{\mathtt {i}} \in \mathcal {P}$ are

$$ \begin{align*} F\cdot\alpha = \{0, 1-\alpha_1, \ldots, 1-\alpha_d\}. \end{align*} $$

Notice that $\mathcal {P}^S = \{I_p : p\in \mathcal {L}_S(c_{\alpha })\} = \{I_p : p\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^S \text { and } I_p\neq \varnothing \}$ . Using Lemma 4.8, we obtain that $\mathcal {P}^S$ is a partition of $\mathbb {R}/\mathbb {Z}$ into non-empty (left-closed, right-open) intervals. It is therefore clear from the definition of the intervals $I_p$ that their unique boundary points are described by the set $F\cdot \alpha -S\cdot \alpha = (F-S)\cdot \alpha $ .

For each p, there exists a unique boundary point $\xi \in (F-S)\cdot \alpha $ which belongs to $I_p$ (the left-end point of $I_p$ ). Since $\alpha $ is totally irrational, the map $n\mapsto n\cdot \alpha +\mathbb {Z}$ is injective, and thus there is a unique vector $n\in F-S$ such that $n\cdot \alpha =\xi $ . We have that ${\sigma ^{n}(c_{\alpha }) = s_{\alpha ,\xi } \in [p]}$ and so $n \in \mathsf {occ}_p(c_{\alpha })$ .

The argument for $c^{\prime }_{\alpha }$ is identical, the only difference being that the unique boundary point is now the right-end point of $I^{\prime }_p$ .

Theorem 4.10. If $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ is totally irrational, then $(c_{\alpha },c^{\prime }_{\alpha })$ is a non-trivial indistinguishable asymptotic pair which satisfies the flip condition.

Proof. By Lemma 4.6, we have that $(c_{\alpha },c^{\prime }_{\alpha })$ is a non-trivial asymptotic pair whose difference set is $F=\{0,-e_1,\ldots ,-e_d\}$ . Furthermore, by Proposition 4.7, it satisfies the flip condition. Let S be a non-empty connected finite subset of ${\mathbb {Z}^d}$ and $p \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^S$ . From Lemma 4.9, we obtain that the set of occurrences of p intersects $F-S$ exactly once for both $c_{\alpha }$ and $c^{\prime }_{\alpha }$ , that is,

$$ \begin{align*} \#( \mathsf{occ}_p(c_{\alpha}) \cap (F-S) ) = 1 = \#( \mathsf{occ}_p(c^{\prime}_{\alpha}) \cap (F-S) ). \end{align*} $$

By Proposition 2.4, it suffices to check the above condition for patterns whose support is a non-empty finite connected subset of ${\mathbb {Z}^d}$ . We conclude that $(c_{\alpha },c^{\prime }_{\alpha })$ is indistinguishable.

Remark 4.11. If we take a sequence of totally irrational vectors $(\alpha _n)_{n \in \mathbb {N}}$ , it follows that each associated pair $(c_{\alpha _n},c^{\prime }_{\alpha _n})$ satisfies the flip condition. It follows that if both $(c_{\alpha _n})_{n \in \mathbb {N}}$ and $(c^{\prime }_{\alpha _n})_{n \in \mathbb {N}}$ converge to c and $c'$ in the prodiscrete topology, then $(c_{\alpha _n},c^{\prime }_{\alpha _n})$ converges in the asymptotic relation to the étale limit $(c,c')$ , which thus also satisfies the flip condition. By Proposition 2.9, we get that $(c,c')$ is therefore an indistinguishable asymptotic pair. This can be used to provide examples of indistinguishable asymptotic pairs which satisfy the flip condition, but that are not uniformly recurrent. See Figure 4.

5. Uniformly recurrent indistinguishable asymptotic pairs are Sturmian

The goal of this section is to prove Theorem B. We already proved in Theorem 4.10 that if $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ is totally irrational, then $(c_{\alpha },c^{\prime }_{\alpha })$ is a non-trivial indistinguishable asymptotic pair which satisfies the flip condition. Thus, it remains to show the existence of a totally irrational vector $\alpha =(\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ describing an indistinguishable asymptotic pair which satisfies the flip condition whenever the configurations are uniformly recurrent. The proof relies on an induction argument on the dimension of ${\mathbb {Z}^d}$ and on the existence of a factor map between the symbolic dynamical system generated by a multidimensional Sturmian configuration and rotations on the circle $\mathbb {R}/\mathbb {Z}$ .

5.1. Symbolic representations

Consider ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ a continuous ${\mathbb {Z}^d}$ -action on $\mathbb {R}/\mathbb {Z}$ , where $R\colon {\mathbb {Z}^d}\times \mathbb {R}/\mathbb {Z}\to \mathbb {R}/\mathbb {Z}$ . For some finite set $\mathcal {A}$ , a topological partition of $\mathbb {R}/\mathbb {Z}$ (in the sense of [28, Definition 6.5.3]) is a collection $\{P_a\}_{a\in \mathcal {A}}$ of disjoint open sets $P_a\subset \mathbb {R}/\mathbb {Z}$ such that $\mathbb {R}/\mathbb {Z} = \bigcup _{a\in \mathcal {A}} \overline {P_a}$ . If $S\subset {\mathbb {Z}^d}$ is a finite set, we say that a pattern $w\in \mathcal {A}^S$ is allowed for $\mathcal {P},R$ if

(9) $$ \begin{align} \bigcap_{k\in S} R^{-k}(P_{w_k}) \neq \varnothing. \end{align} $$

The intersection in equation (9) is related to the definition of $I^{\prime }_w$ and $I_w$ done in equation (8) except here, the sets $P_{w_k}$ are open.

Let us recall that a ${\mathbb {Z}^d}$ -subshift is a set of the form $X \subset \mathcal {A}^{{\mathbb {Z}^d}}$ which is closed in the prodiscrete topology and invariant under the shift action; and its language is the union of $\mathcal {L}(x)$ for every $x \in X$ . Let $\mathcal {L}_{\mathcal {P},R}$ be the collection of all allowed patterns for $\mathcal {P},R$ . The set $\mathcal {L}_{\mathcal {P},R}$ is the language of a subshift $\mathcal {X}_{\mathcal {P},R}\subseteq \mathcal {A}^{{\mathbb {Z}^d}}$ defined as follows, see [21, Proposition 9.2.4]:

$$ \begin{align*} \mathcal{X}_{\mathcal{P},R} = \{x\in\mathcal{A}^{{\mathbb{Z}^d}} \mid \sigma^n(x)|_S \in\mathcal{L}_{\mathcal{P},R} \text{ for every } n\in{\mathbb{Z}^d} \text{ and finite subset } S\subset{\mathbb{Z}^d}\}. \end{align*} $$

We call $\mathcal {X}_{\mathcal {P},R}$ the symbolic extension of ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ determined by $\mathcal {P}$ .

For each $x\in \mathcal {X}_{\mathcal {P},R}$ and $m\geq 0$ , there is a corresponding non-empty open set

$$ \begin{align*} D_m(x) = \bigcap_{\Vert k\Vert_{\infty} \leq m} R^{-k}(P_{x_k}) \subset \mathbb{R}/\mathbb{Z}. \end{align*} $$

The sequence of compact closures $(\overline {D}_m(x))_{m \in \mathbb {N}}$ of these sets is nested and thus it follows that their intersection is non-empty. Notice that there is no reason why $\operatorname {diam}(\overline {D}_m(x))$ should converge to zero, and thus the intersection could contain more than one point. For $\mathcal {X}_{\mathcal {P},R}$ to capture the dynamics of ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ , this intersection should contain only one point. This leads to the following definition.

Definition 5.1. A topological partition $\mathcal {P}$ of $\mathbb {R}/\mathbb {Z}$ gives a symbolic representation $\mathcal {X}_{\mathcal {P},R}$ of ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ if for every $x\in \mathcal {X}_{\mathcal {P},R}$ , the intersection $\bigcap _{m=0}^{\infty }\overline {D}_m(x)$ consists of exactly one point $\rho \in \mathbb {R}/\mathbb {Z}$ . We call x a symbolic representation of $\rho $ .

If $\mathcal {P}$ gives a symbolic representation of the dynamical system ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ , then there is a well-defined map $f\colon \mathcal {X}_{\mathcal {P},R} \to \mathbb {R}/\mathbb {Z}$ which maps a configuration $x\in \mathcal {X}_{\mathcal {P},R}\subset \mathcal {A}^{{\mathbb {Z}^d}}$ to the unique point $f(x)\in \mathbb {R}/\mathbb {Z}$ in the intersection $\bigcap _{n=0}^{\infty }\overline {D}_n(w)$ . It is not hard to prove that f is in fact a factor map, that is, such that f is continuous, surjective, and ${\mathbb {Z}^d}$ -equivariant ( $f(\sigma ^k(x)) = R^k(f(x))$ for every $k \in {\mathbb {Z}^d}$ ). A proof of this fact for the case $d=1$ can be found in [28, Proposition 6.5.8]. A proof for $\mathbb {Z}^2$ -actions can be found in [25, Proposition 5.1] and a proof for general group actions follows the same arguments.

Now let us turn back to circle rotations. Let $\alpha \in [0,1)^d$ and consider the dynamical system ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ , where $R\colon {\mathbb {Z}^d}\times \mathbb {R}/\mathbb {Z}\to \mathbb {R}/\mathbb {Z}$ is the continuous ${\mathbb {Z}^d}$ -action on $\mathbb {R}/\mathbb {Z}$ defined by

for every $n\in {\mathbb {Z}^d}$ .

Recall that an action is minimal if every orbit is dense. The following lemma is well known; we write it down for future reference and we give a quick proof sketch.

Lemma 5.2. Let $\alpha \in [0,1)^d$ be totally irrational and consider the topological partition of the circle

$$ \begin{align*} \mathcal{P}=\{\operatorname{Int}(W_{\mathtt{i}})\}_{\mathtt{i}\in\{\mathtt{0},\mathtt{1},\ldots,d\}}. \end{align*} $$

1. (1) The partition $\mathcal {P}$ gives a symbolic representation of the dynamical system ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ .

2. (2) The symbolic dynamical system $\mathcal {X}_{\mathcal {P},R}$ is minimal and satisfies $\mathcal {X}_{\mathcal {P},R}= \overline {\{\sigma ^k c_\alpha \colon k\in {\mathbb {Z}^d}\}}$ .

3. (3) $f\colon \mathcal {X}_{\mathcal {P},R}\to \mathbb {R}/\mathbb {Z}$ , where $f(x) \in \bigcap _{n=0}^{\infty }\overline {D}_n(w)$ is a factor map.

Proof. As $\alpha $ is totally irrational, then every component $\alpha _i$ is irrational and hence it follows that the action ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ is minimal. From here, it follows by standard arguments that $\mathcal {P}$ gives a symbolic representation $\mathcal {X}_{\mathcal {P},R}$ of the ${\mathbb {Z}^d}\overset {R}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ , as every $\operatorname {Int}(W_{\mathtt {i}})$ is invariant only under the trivial rotation (e.g., see [25, Lemma 3.4]). The second statement follows easily from the definitions of $\mathcal {X}_{\mathcal {P},R}$ and $c_{\alpha }$ , and the third statement follows from the discussion below Definition 5.1.

5.2. Ordered flip condition

To simplify the proofs in this section, we consider a particular case of the flip condition in which the values of $x|_F$ and $y|_F$ are fixed.

Definition 5.3. Let $d\geq 1$ be an integer. An indistinguishable asymptotic pair $x, y\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ satisfies the ordered flip condition if:

1. (1) the difference set of x and y is $F=\{0, -e_1,\ldots ,-e_d\}$ ;

2. (2) $x_0 = \mathtt {0}$ and $x_{-e_i} = \mathtt {i}$ for all $\mathtt {1} \leq \mathtt {i} \leq d$ ;

3. (3) $y_0 = d$ and $y_{-e_{i}} = \mathtt {i}-\mathtt {1}$ for all $\mathtt {1} \leq \mathtt {i} \leq d$ .

Observe that if two configurations satisfy the ordered flip condition, they also satisfy the flip condition. Moreover, notice that the ordered flip condition corresponds to the permutation of F given by

$$ \begin{align*} 0 \mapsto -e_{\mathtt{1}} \mapsto -e_{\mathtt{2}} \mapsto \cdots \mapsto -e_{d} \mapsto 0. \end{align*} $$

Lemma 5.4. Let $d\geq 1$ be an integer. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ form an indistinguishable asymptotic pair satisfying the flip condition. Then there exists a matrix $A\in \operatorname {GL}_d(\mathbb {Z})$ which permutes the canonical base $\{e_1,\ldots ,e_d\}$ such that $(x\circ A,y\circ A)$ is an indistinguishable asymptotic pair satisfying the ordered flip condition.

Proof. As $x,y$ satisfy the flip condition, then the restrictions of x and y to F are bijections $F\to \{\mathtt {0},\mathtt {1},\ldots ,d\}$ , $x_0 = 0$ , and $y_n = x_n - \mathtt {1} \bmod (d+\mathtt {1})$ for every $n\in F$ . Let $A \in \operatorname {GL}_d(\mathbb {Z})$ be the permutation matrix which sends $-e_i$ to $x|_F^{-1}(\mathtt {i})$ for all i with $1\leq i\leq d$ . Thus, it satisfies $x(-Ae_i)=\mathtt {i}$ .

By Proposition 2.5, $x\circ A,y\circ A$ is an indistinguishable asymptotic pair. It is clear by definition of A that their difference set is F, that $(x \circ A)_0 = x_0 = \mathtt {0}$ , and $(x \circ A)_{-e_i} = x(-Ae_i) = \mathtt {i}$ for all $\mathtt {1} \leq \mathtt {i} \leq d$ .

Finally, $(y\circ A)_0 = y_0 = x_0-\mathtt {1} = 0-\mathtt {1} = d\bmod (d+\mathtt {1})$ and for $\mathtt {1} \leq \mathtt {i} \leq d$ , we have $(y\circ A)_{-e_i}= y(-Ae_i) = x(-Ae_i)-\mathtt {1} = \mathtt {i-1}\bmod (d+\mathtt {1})$ . Thus, $(x\circ A, y\circ A)$ satisfy the ordered flip condition.

It follows that if we show that every pair $x,y\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ which satisfies the ordered flip condition is equal to $c_{\alpha },c^{\prime }_{\alpha }$ for some totally irrational $\alpha $ , we immediately obtain that every non-trivial indistinguishable asymptotic pair which satisfies the flip condition also coincides with $c_{\alpha '},c^{\prime }_{\alpha '}$ for some totally irrational slope $\alpha '$ , where $\alpha '$ is a permutation of $\alpha $ .

Proposition 5.5. Let $d\geq 1$ be an integer. Let $\alpha \in [0,1)^d$ be totally irrational such that $1>\alpha _{\mathtt {1}}> \alpha _{\mathtt {2}} > \cdots > \alpha _{d}>0$ . The characteristic d-dimensional Sturmian configurations $c_{\alpha }$ and $c^{\prime }_{\alpha }$ satisfy the ordered flip condition.

Proof. From Proposition 4.7, $(c_{\alpha },c^{\prime }_{\alpha })$ satisfy the flip condition. Following equations (6) and (7), we get

$$ \begin{align*} (c_{\alpha})_{-e_{\mathtt{i}}} &= \#\{ \mathtt{j} : \alpha_{\mathtt{j}} \geq \alpha_{\mathtt{i}} \} = \mathtt{i}, \\ (c^{\prime}_{\alpha})_{-e_{\mathtt{i}}} &= \#\{ \mathtt{j} : \alpha_{\mathtt{j}}> \alpha_{\mathtt{i}} \} = \mathtt{i}-1. \end{align*} $$

Thus, $(c_{\alpha },c^{\prime }_{\alpha })$ satisfy the ordered flip condition.

5.3. Indistinguishable asymptotic pairs restricted to a $(d-1)$ -dimensional submodule

In what follows, we show that indistinguishable asymptotic pairs which satisfy the ordered flip condition are Sturmian. Our strategy is to reduce the dimension of the underlying group by restricting the values of the configurations to the $(d-1)$ -dimensional submodule orthogonal to $e_1$ and then to apply a suitable projection which fuses two symbols into a single one. We show that the resulting configurations in $\mathbb {Z}^{d-1}$ also satisfy the ordered flip condition and thus gives us the means to prove our result inductively.

To develop this strategy, we introduce the following notation. Let $B\hspace{-1pt}=\hspace{-1pt}\{b_1,\ldots ,b_k\}\hspace{-1pt}\subset\hspace{-1pt} {\mathbb {Z}^d}$ . For each starting point $v\in {\mathbb {Z}^d}$ , let

$$ \begin{align*} \begin{array}{llll} \ell_{v,B}\colon&\!\!\mathbb{Z}^k & \to & {\mathbb{Z}^d}\\ &\!\!n & \mapsto & v+ n_1b_1 +\cdots+n_k b_k. \end{array} \end{align*} $$

If $x\in \Sigma ^{{\mathbb {Z}^d}}$ is a configuration, then $x\circ \ell _{v,B}\in \Sigma ^{\mathbb {Z}^k}$ is the k-dimensional configuration which occurs in x starting at position $v\in {\mathbb {Z}^d}$ and following the directions $b_i\in B$ . Below, we use the shorter notation to denote the canonical basis without the vector $e_1$ .

Let us consider the projection

$$ \begin{align*} \begin{array}{llll} \pi:&\!\!\{\mathtt{0},\mathtt{1},\ldots,d\} & \to & \{\mathtt{0},\ldots,d-1\}\\ &\mathtt{j} & \mapsto & \begin{cases} \mathtt{0} & \text{if } \mathtt{j} = \mathtt{0},\\ \mathtt{j}-\mathtt{1} & \text{if } \mathtt{j}\neq\mathtt{0}, \end{cases} \end{array} \end{align*} $$

which extends to configurations $x\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ by letting

$$ \begin{align*} \pi(x)&=(\pi(x_{n}))_{n\in{\mathbb{Z}^d}}\in\{\mathtt{0},\ldots,d-1\}^{{\mathbb{Z}^d}}. \end{align*} $$

Proposition 5.6. Let $d\geq 2$ be an integer. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair satisfying the ordered flip condition. Then $\pi \circ x\circ \ell _{0,e_1^\perp }$ and $\pi \circ y\circ \ell _{0,e_1^\perp }$ are indistinguishable asymptotic configurations in $\{\mathtt {0},\mathtt {1},\ldots ,d-1\}^{\mathbb {Z}^{d-1}}$ which satisfy the ordered flip condition in dimension $d-1$ .

Proof. By Proposition 2.6, we have that $(\pi (x), \pi (y))$ is an indistinguishable asymptotic pair. Under the ordered flip condition, the difference set of $(\pi (x), \pi (y))$ is ${F\setminus \{-e_1\}= \{ 0, -e_{\mathtt {2}}, -e_{\mathtt {3}}, \ldots , -e_{d}\}}$ and thus it follows that for any pattern p with support $S \subset \langle e_1^{\perp }\rangle $ , we have

It follows that the pair $(\pi \circ x\circ \ell _{0,e_1^\perp }, \pi \circ y\circ \ell _{0,e_1^\perp })$ is also indistinguishable. It can be checked directly that it also satisfies the ordered flip condition.

If we were also able to show that $\pi \circ x\circ \ell _{0,e_1^\perp }$ is uniformly recurrent, then Proposition 5.6 provides a way to prove Theorem B by induction on the dimension. Namely, if we were to proceed by induction, we would obtain that $\pi \circ x\circ \ell _{0,e_1^\perp }$ and $\pi \circ y\circ \ell _{0,e_1^\perp }$ are $(d-1)$ -dimensional characteristic Sturmian configurations associated to a totally irrational slope $(\alpha ^{(2)},\ldots ,\alpha ^{(d)})\in [0,1)^{d-1}$ , that is,

$$ \begin{align*} \pi\circ x\circ\ell_{0,e_1^\perp}=c_{(\alpha^{(2)},\ldots,\alpha^{(d)})} \quad \mbox{and}\quad \pi\circ y\circ\ell_{0,e_1^\perp}=c^{\prime}_{(\alpha^{(2)},\ldots,\alpha^{(d)})}. \end{align*} $$

We could proceed from there to obtain our desired result.

The next two lemmas show that, for all $v\in {\mathbb {Z}^d}$ , the parallel $(d-1)$ -dimensional configurations $\pi \circ x\circ \ell _{v,e_1^\perp }$ and $\pi \circ y\circ \ell _{v,e_1^\perp }$ belong to $\overline {\mathrm {Orb}(\pi \circ x\circ \ell _{0,e_1^\perp })} =\overline {\mathrm {Orb}(\pi \circ y\circ \ell _{0,e_1^\perp })}$ , that is, the $(d-1)$ -dimensional subshift whose language is $\mathcal {L}(c_{(\alpha ^{(2)},\ldots ,\alpha ^{(d)})}) = \mathcal {L}(c^{\prime }_{(\alpha ^{(2)},\ldots ,\alpha ^{(d)})})$ .

Lemma 5.7. Let $d\geq 2$ be an integer. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair satisfying the ordered flip condition. For each finite non-empty connected subset $S \subset \{0\}\times \mathbb {Z}^{d-1}$ , let

$$ \begin{align*} A_S &=\mathcal{L}_S(x\circ\ell_{0,e_1^\perp})\cup \mathcal{L}_S(y\circ\ell_{0,e_1^\perp}),\\ B_S &=\mathcal{L}_S(x\circ\ell_{-e_1,e_1^\perp})\cup \mathcal{L}_S(y\circ\ell_{-e_1,e_1^\perp}). \end{align*} $$

We have $A_S\cap B_S\neq \varnothing $ .

Proof. Let $S \subset \{0\}\times \mathbb {Z}^{d-1}$ be a finite non-empty connected subset. Since $(\pi \circ x\circ \ell _{0,e_1^\perp }, \pi \circ y\circ \ell _{0,e_1^\perp })$ satisfies the $(d-1)$ -dimensional ordered flip condition with difference set $F\setminus \{-e_1\}$ , from Theorem A, we have

$$ \begin{align*} &\#A_S \geq \#\pi(A_S)\\ &\quad= \mathcal{L}_S(\pi \circ x\circ\ell_{0,e_1^\perp})\cup \mathcal{L}_S(\pi \circ y\circ\ell_{0,e_1^\perp}) = \# (F\setminus\{-e_1\}-S) = \# (F-S) - \#S. \end{align*} $$

By contradiction, assume that $A_S\cap B_S=\varnothing $ . From Corollary 3.13, we have that $\#\mathcal {L}_S(x\circ \ell _{-e_1,e_1^\perp })\geq \#S$ and $\#\mathcal {L}_S(y\circ \ell _{-e_1,e_1^\perp })\geq \#S$ so that $\#B_S\geq \#S$ . The case $\#B_S=\#S$ is impossible. Indeed, $\#B_S=\#S$ implies that $B_S=\mathcal {L}_S(x\circ \ell _{-e_1,e_1^\perp })= \mathcal {L}_S(y\circ \ell _{-e_1,e_1^\perp })$ . Observe that $x(-e_1)=\mathtt {1}$ and $y(-e_1)=\mathtt {0}$ . Let $w\in B_S$ be a pattern with the most occurrences of the symbol $\mathtt {0}$ . Since $x,y$ is an indistinguishable asymptotic pair satisfying the flip condition, Corollary 3.13 implies that the pattern w must appear in x intersecting the difference set F. Since $A_S \cap B_S = \varnothing $ , then necessarily the pattern w appears in x intersecting the position $-e_1$ . Over the same support, there is a pattern in y with one more occurrence of the symbol $\mathtt {0}$ . This pattern also belongs to $B_S$ , and thus it contradicts the maximality of the number of occurrences of the symbol $\mathtt {0}$ in w among all patterns in $B_S$ . Therefore, $\#B_S\geq \#S+1$ .

From Theorem A, we have $\#(A_S\cup B_S)\leq \#\mathcal {L}_S(x)=\#(F-S)$ . Thus,

$$ \begin{align*} \#(A_S\cap B_S) &= \#A_S + \#B_S - \#(A_S\cup B_S)\\ &\geq (\#(F-S) - \#S) +(\#S+1) -\#(F-S) = 1. \end{align*} $$

This contradicts the assumption $A_S\cap B_S=\varnothing $ . Thus, $A_S\cap B_S\neq \varnothing $ .

Lemma 5.8. Let $d\geq 2$ be an integer. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair satisfying the ordered flip condition. For every $v\in {\mathbb {Z}^d}$ , we have

$$ \begin{align*} \mathcal{L}(\pi\circ x\circ\ell_{v,e_1^\perp}) \subset \mathcal{L}(\pi\circ x\circ\ell_{0,e_1^\perp}) \quad\text{and}\quad \mathcal{L}(\pi\circ y\circ\ell_{v,e_1^\perp}) \subset \mathcal{L}(\pi\circ y\circ\ell_{0,e_1^\perp}). \end{align*} $$

Proof. As $\pi (x),\pi (y)$ is an indistinguishable asymptotic pair whose difference set is contained in $e_1^{\perp }$ , it follows that $\pi \circ x\circ \ell _{v,e_1^\perp } = \pi \circ y\circ \ell _{v,e_1^\perp }$ for every $v \notin \langle e_1^\perp \rangle $ and that $\mathcal {L}(\pi \circ x\circ \ell _{0,e_1^\perp }) =\mathcal {L}(\pi \circ y\circ \ell _{0,e_1^\perp })$ . Therefore, it is sufficient to prove the inclusion $\mathcal {L}(\pi \circ x\circ \ell _{v,e_1^\perp }) \subset \mathcal {L}(\pi \circ x\circ \ell _{0,e_1^\perp })$ . By contradiction, suppose that there is $v\in \mathbb {Z}e_1$ such that $w\in \mathcal {L}(\pi \circ x\circ \ell _{v,e_1^\perp }) \setminus \mathcal {L}(\pi \circ x\circ \ell _{0,e_1^\perp })\neq \varnothing $ . Let $w' \in \pi ^{-1}(w)$ , it follows that $w' \in \mathcal {L}(x\circ \ell _{v,e_1^\perp })\setminus \mathcal {L}(x\circ \ell _{0,e_1^\perp })$ . Using that $x,y$ are indistinguishable and satisfy the flip condition, we conclude using Lemma 3.2 that $w' \in \mathcal {L}(x\circ \ell _{-e_1,e_1^\perp })\setminus \mathcal {L}(x\circ \ell _{0,e_1^\perp })$ and thus that $w\in \mathcal {L}(\pi \circ x\circ \ell _{-e_1,e_1^\perp }) \setminus \mathcal {L}(\pi \circ x\circ \ell _{0,e_1^\perp })$ . In other words, without loss of generality, we may assume that $v=-e_1$ .

For every sufficiently large $n \in \mathbb {N}$ , if we let , then the pattern $p = (\pi (x))|_{S_n}$ contains w and thus does not occur in $\pi (x)\circ \ell _{0,e_1^\perp }$ . Define $e_0 = 0$ and let $j \in \{0,\ldots ,d\}\setminus \{1\}$ , $S_n^j = S_n \cup \{-e_j \}$ , and $p^j = \pi (x)|_{S_n^j}$ . As $\pi (x), \pi (y)$ is indistinguishable, there must exist ${u_j} \in (F\setminus \{-e_1\})-S_n^j$ so that $\sigma ^{{u_j}}(\pi (y)) \in [p^j]$ . As $p = p^j|_{S_n}$ does not occur in $\pi (x)\circ \ell _{0,e_1^\perp }$ , we have that ${u_j} \notin (F\setminus \{-e_1\})-S_n$ , from where we obtain that $u_j\in e_j+(F\setminus \{-e_1\})$ . By the ordered flip condition, we have the following.

1. (1) If $j = 0$ , then $(\pi (x))_{0} = \mathtt {0}$ and $(\pi (y))_{-e_2}=0$ , and hence we have ${u_j = e_0-e_2 = -e_2}$ .

2. (2) If $2 \leq j < d$ , then $(\pi (x))_{-e_j} = \mathtt {j}-\mathtt {1}$ and $(\pi (y))_{-e_{j+1}}=\mathtt {j}-\mathtt {1}$ , and hence we have $u_j = e_j - e_{j+1}$ .

3. (3) If $j = d$ , then $(\pi (x))_{-e_d} = d-\mathtt {1}$ and $(\pi (y))_{0}=d-\mathtt {1}$ , and hence we have $u_j = -e_d+e_0 = e_d$ .

Notice that in any case, we have $u_j \in \langle e_1^{\perp }\rangle $ . As $\pi (x), \pi (y)$ is asymptotic outside of $F\setminus \{-e_1\}$ , we conclude that

$$ \begin{align*} \sigma^{u_j}(\pi(x))|_{S_{n}} = \sigma^{u_j}(\pi(y))|_{S_{n}} = (\pi(x))|_{S_{n}}\end{align*} $$

for every large enough n. Noting that the set $\mathcal {G} = \{ u_j : j \in \{0,\ldots ,d\}\setminus \{1\} \}$ generates (as a group) $\{0\}\times \mathbb {Z}^{d-1}$ , it follows that the configuration $\pi \circ x\circ \ell _{-e_1,e_1^\perp }$ is constant and thus $\mathcal {L}_S(\pi \circ x\circ \ell _{-e_1,e_1^\perp })$ is a singleton for every finite support $S\subset \{0\}\times \mathbb {Z}^{d-1}$ .

Assuming $S\hspace{-1pt}\subset\hspace{-1pt} \{0\}\hspace{-1pt}\times\hspace{-1pt} \mathbb {Z}^{d-1}$ is the shape of the pattern w, we have $\mathcal {L}_S(\pi\hspace{-1pt} \circ\hspace{-1pt} x\hspace{-1pt}\circ\hspace{-1pt} \ell _{-e_1,e_1^\perp })\hspace{-1pt}=\hspace{-1pt}\{w\}$ . From Lemma 5.7, for all finite non-empty connected subset $S\subset \{0\}\times \mathbb {Z}^{d-1}$ , we have $A_S\cap B_S\neq \varnothing $ , where

$$ \begin{align*} A_S &=\mathcal{L}_S(x\circ\ell_{0,e_1^\perp})\cup \mathcal{L}_S(y\circ\ell_{0,e_1^\perp}) =\mathcal{L}_S(x\circ\ell_{0,e_1^\perp}),\\ B_S &=\mathcal{L}_S(x\circ\ell_{-e_1,e_1^\perp})\cup \mathcal{L}_S(y\circ\ell_{-e_1,e_1^\perp}) =\mathcal{L}_S(x\circ\ell_{-e_1,e_1^\perp}), \end{align*} $$

which also holds under the projection by $\pi $ . Therefore, if S is the shape of the pattern w, we have

$$ \begin{align*} \varnothing &\neq \pi(A_S) \cap \pi(B_S)\\ &= \mathcal{L}_S(\pi\circ x\circ\ell_{0,e_1^\perp}) \cap \mathcal{L}_S(\pi\circ x\circ\ell_{-e_1,e_1^\perp})\\ &= \mathcal{L}_S(\pi\circ x\circ\ell_{0,e_1^\perp}) \cap \{w\}. \end{align*} $$

This implies that $w\in \mathcal {L}_S(\pi \circ x\circ \ell _{0,e_1^\perp })$ which contradicts the definition of w. Thus, we conclude that $\mathcal {L}(\pi \circ x\circ \ell _{v,e_1^\perp }) \subset \mathcal {L}(\pi \circ x\circ \ell _{0,e_1^\perp })$ for all $v\in {\mathbb {Z}^d}$ .

Given a configuration $x \in A^{{\mathbb {Z}^d}}$ , we say a pattern $p\in A^S$ occurs with bounded gaps if there exists $n\hspace{-0.5pt} \in\hspace{-0.5pt} \mathbb {N}$ such that for any $v\hspace{-0.5pt} \in\hspace{-0.5pt} {\mathbb {Z}^d}$ , there is such that $\sigma ^{v+u}(x)|_S\hspace{-0.5pt} =\hspace{-0.5pt} p$ . If a pattern does not occur with bounded gaps, this means that there is a sequence $(v_i)_{i \in \mathbb {N}}$ with $v_i \in {\mathbb {Z}^d}$ such that p does not occur in any accumulation point of the sequence $(\sigma ^{v_i}(x))_{i \in \mathbb {N}}$ .

Lemma 5.9. Let $d\geq 1$ be an integer. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair satisfying the ordered flip condition. If x is uniformly recurrent, then $\pi \circ x\circ \ell _{0,e_1^\perp }$ is uniformly recurrent.

Proof. Suppose that $\pi \circ x\circ \ell _{0,e_1^\perp }$ is not uniformly recurrent and let $p \in \mathcal {L}(\pi \circ x\circ \ell _{0,e_1^\perp })$ be a pattern in its language which does not occur with bounded gaps. Let S be the support of p. Let be the sliding-block code such that for any $z \in \{\mathtt {0},\mathtt {1},\ldots ,d-1\}^{{\mathbb {Z}^d}}$ and $v \in {\mathbb {Z}^d}$ ,

As x is uniformly recurrent, the topological closure of its orbit $X=\overline {\mathrm {Orb}(x)}$ is a minimal subshift, and it follows that both $\pi (X)$ and $\psi (\pi (X))$ are also minimal subshifts. Let us denote $w = \psi (\pi (x))$ .

For $n \in \mathbb {N}$ , let and let $h_n$ denote the pattern with support $B_n$ which is identically . For every $t \in \mathbb {Z} e_1$ , we define

$$ \begin{align*} N(t) = \sup\{n\in\mathbb{N} \mid h_n \text{ occurs in } w\circ\ell_{t,e_1^\perp} \text{ with bounded gaps}\}. \end{align*} $$

Notice that the values of $N(t)$ do not change if we replace w by an accumulation point of a sequence of shifts of w by vectors in $\{0\}\times \mathbb {Z}^{d-1}$ . Let $(t_i)_{i \geq 1}$ be an enumeration of $\mathbb {Z} e_1$ . We construct a sequence $(w_i)_{i \geq 0}$ of configurations in $\psi (\pi (X))$ as follows. Let $w_{0} =w$ . For every $i \geq 1$ , we construct the configuration $w_i$ from $w_{i-1}$ according to one of the following three cases.

Case 1: $N(t_i) = -\infty $ . In this case, the symbol does not occur in $w\circ \ell _{t,e_1^\perp }$ with bounded gaps and thus, there is a sequence $(u_n)_{n \in \mathbb {N}}$ with $u_n \in \{0\}\times \mathbb {Z}^{d-1}$ for which does not appear in $(\sigma ^{u_n}(w_{i-1}) \circ \ell _{t_i,e_1^\perp })|_{B_n}$ . We let $w_i$ be any accumulation point of this sequence.

Case 2: $N(t_i) \in \mathbb {N}$ . This means that there is a largest $n \in \mathbb {N}$ for which $h_{n}$ occurs in $w_{i-1}\circ \ell _{t_i,e_1^\perp }$ with bounded gaps. In this case, there is a sequence $(u_n)_{n \in \mathbb {N}}$ with $u_n \in \{0\}\times \mathbb {Z}^{d-1}$ for which $h_{n+1}$ does not appear in $(\sigma ^{u_n}(w_{i-1}) \circ \ell _{t_i,e_1^\perp })|_{B_n}$ . We let $w_i$ be any accumulation point of this sequence.

Case 3: $N(t_i) = \infty $ . Here for every $n \in \mathbb {N}$ , the pattern $h_n$ occurs in $w_{i-1}\circ \ell _{t_i,e_1^\perp }$ with bounded gaps. In this case, there is a sequence $(u_n)_{n \in \mathbb {N}}$ with $u_n \in \{0\}\times \mathbb {Z}^{d-1}$ such that $(\sigma ^{u_n}(w_{i-1}) \circ \ell _{t_i,e_1^\perp })|_{B_n}$ is identically . We let $w_i$ be any accumulation point of this sequence.

By construction, $w_i \in \psi (\pi (X))$ for every $i \in \mathbb {N}$ . Let $\bar {w}$ be an accumulation point of the sequence $(w_i)_{i \in \mathbb {N}}$ . It follows that $\bar {w} \in \psi (\pi (X))$ . This sequence has the following properties:

1. (1) $N(t)=-\infty $ if and only if $\bar {w}\circ \ell _{t,e_1^\perp }$ is identically ;

2. (2) $N(t)= n \in \mathbb {N}$ if and only if $h_n$ occurs with bounded gaps in $\bar {w}\circ \ell _{t,e_1^\perp }$ and $h_{n+1}$ does not occur;

3. (3) $N(t) = \infty $ if and only if $\bar {w}\circ \ell _{t,e_1^\perp }$ is identically .

Let

$$ \begin{align*}\mathcal{N}= \{ N(t): t \in \mathbb{Z} e_1\}\cap \mathbb{N}. \end{align*} $$

Suppose that the collection $\mathcal {N}$ is finite. This contradicts the minimality of $\psi (\pi (X))$ . Indeed, by the assumption on p, we have that both the symbol and the patterns $h_n$ for every $n \in \mathbb {N}$ occur in $w \circ \ell _{0,e_1^\perp }$ . In particular, for every $n \in \mathbb {N}$ , there is a pattern $q_n$ with support $B_{n+1}$ which occurs in $w \circ \ell _{0,e_1^\perp }$ , such that $q_n|_{B_n} = h_n$ and $q_{n}|_{B_{n+1} \setminus B_n}$ is not identically . For any $n> \max (\mathcal {N})$ , it follows that $q_n$ does not occur in $\bar {w}$ , and thus ${w \notin \overline {\mathrm {Orb}(\bar {w})}}$ , which contradicts minimality.

Suppose now that the collection $\mathcal {N}$ is infinite. For any $\kappa \in \mathbb {N}$ , we can then find $(k_i)_{i=1,\ldots ,\kappa }$ with $k_i \in \mathbb {Z} e_1$ such that

$$ \begin{align*} 0 \leq N(k_1) < N(k_2) < \cdots < N(k_{\kappa}). \end{align*} $$

For every $i \in \{1,\ldots , \kappa \}$ , let $G(k_i)$ be the smallest integer such that every pattern in $\bar {w}_{k_i}$ with support a translate of $B_{G(k_i)}$ contains $h_{N(k_i)}$ as a subpattern. This value exists due to the fact that $h_{N(k_i)}$ occurs in $\bar {w}_{k_i}$ with bounded gaps.

Let $\ell \in \mathbb {N}$ be such that the support of p is contained in $B_{\ell }$ , let $g = 1+2\max _{i=1,\ldots ,\kappa } G(k_i)$ , and let $m \in \mathbb {N}$ be an arbitrary number which we shall later take sufficiently large to find a contradiction. Let us consider any pattern $r_i$ with support $B_{g+m}$ in $\mathcal {L}(\bar {w}_{k_i})$ . By definition of $\psi $ , there is a pattern $r^{\prime }_i$ with support $B_{g+m+\ell }$ in $\mathcal {L}(\pi \circ x \circ \ell _{k_i,e_1^\perp })$ whose image under $\psi $ contains $r_i$ as a subpattern.

By Lemma 5.8, it follows that $\mathcal {L}(\pi \circ x\circ \ell _{k_i,e_1^\perp }) \subset \mathcal {L}(\pi \circ x\circ \ell _{0,e_1^\perp })$ . Also, by Proposition 5.6, the configurations $\pi \circ x\circ \ell _{0,e_1^\perp }, \pi \circ y\circ \ell _{0,e_1^\perp }$ are indistinguishable with the ordered flip condition and thus by Lemma 3.2, every pattern $r^{\prime }_i$ must occur in $\pi \circ x\circ \ell _{0,e_1^\perp }$ intersecting its difference set. Applying the map $\psi $ , a simple estimate shows that an occurrence of $r_i$ must appear in $w \circ \ell _{0,e_1^\perp } $ such that its support $B_{g+m}$ is contained in the set $B_{2(g+m+{\ell })+1}$ .

Now let $i,j\in \{1,\ldots ,\kappa \}$ be distinct. By construction, the patterns $r_i$ and $r_{j}$ can overlap at most in their borders. More explicitly, if $r_i$ were to occur at position $v_i \in \mathbb {Z}^{d-1}$ and $r_{j}$ at position $v_{j}\in \mathbb {Z}^{d-1}$ , then $v_i + B_m \cap v_{j}+ B_m= \varnothing $ . This is due to the definition of g, because if the intersection were to contain a block $B_{g}$ , then it would contain a block of larger than the maximum allowed size for one of both patterns, see Figure 11.

Figure 11 Structure of the patterns $r_i$ .

We conclude that within the support $B_{2(g+m+{\ell })+1}$ , we must be able to fit $\kappa $ blocks of size $B_m$ with no intersection. In particular, we must have that

$$ \begin{align*} (4(g+m+{\ell})+3)^d= |B_{2(g+m+{\ell})+1}| \geq \kappa|B_m| = \kappa(2m+1)^d. \end{align*} $$

Let us fix $\kappa = 4^{d}$ . This fixes in turn the constant g, and thus let $K = g+\ell +1$ . Using the previous inequality, we obtain

$$ \begin{align*} 4^d(K+m)^d \geq (4(g+m+{\ell})+3)^d \geq \kappa(2m+1)^d \geq 4^{d}(2m)^d. \end{align*} $$

From here, we deduce that

$$ \begin{align*} (K+m)^d \geq (2m)^d \mbox{ for every } m \in \mathbb{N}. \end{align*} $$

The previous inequality is clearly false for large enough m, and thus we have that $\mathcal {N}$ cannot be infinite either. We conclude that $\pi \circ x\circ \ell _{0,e_1^\perp }$ is uniformly recurrent.

The next proposition shows, under some hypothesis, the existence of a factor map $g\colon \overline {\mathrm {Orb}(x)}\to \mathbb {R}/\mathbb {Z}$ .

Proposition 5.10. Let $d\geq 2$ be an integer. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair satisfying the ordered flip condition and assume x is uniformly recurrent. Assume there exists a factor map $f\colon \overline {\mathrm {Orb}(\pi \circ x\circ \ell _{0,e_1^\perp })}\to \mathbb {R}/\mathbb {Z}$ commuting the actions $\mathbb {Z}^{d-1}\overset {\sigma }{\curvearrowright }\overline {\mathrm {Orb}(\pi \circ x\circ \ell _{0,e_1^\perp })}$ and $\mathbb {Z}^{d-1}\overset {T}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ . Then there is $\rho \in [0,1)$ such that the map $g\colon \overline {\mathrm {Orb}(x)}\to \mathbb {R}/\mathbb {Z}$ defined by $g(z)=f(\pi \circ z\circ \ell _{0,e_1^\perp })$ is a factor map between the actions $\mathbb {Z}^{d}\overset {\sigma }{\curvearrowright }\overline {\mathrm {Orb}(x)}$ and $\mathbb {Z}^{d}\overset {R_{\rho }\times T}{\curvearrowright }\mathbb {R}/\mathbb {Z}$ , where $R_{\rho }$ is the rotation by $\rho $ .

Proof. The map g is continuous and onto since f is continuous and onto. Also since f is a factor map commuting the $\mathbb {Z}^{d-1}$ -actions, for every $z\in \overline {\mathrm {Orb}(x)}$ and $(0,r)\in \{0\}\times \mathbb {Z}^{d-1}$ , we have

$$ \begin{align*} g(\sigma^{(0,r)}z) &=f(\pi\circ \sigma^{(0,r)}z\circ\ell_{0,e_1^\perp})\\ &=f(\sigma^{r}(\pi\circ z\circ\ell_{0,e_1^\perp})) =T^r(f(\pi\circ z\circ\ell_{0,e_1^\perp})) =T^r(g(z)). \end{align*} $$

Thus, it remains to show that for every $z\in \overline {\mathrm {Orb}(x)}$ and $k\in \mathbb {Z}$ , we have $g(\sigma ^{ke_1}z)=R_\rho ^{k}(g(z))$ for some $\rho \in \mathbb {R}/\mathbb {Z}$ . Since $\overline {\mathrm {Orb}(x)}$ is minimal and g is continuous, it is sufficient to prove it for $z=x$ or $z=y$ .

From Proposition 5.6, the configurations $\pi \circ x\circ \ell _{0,e_1^\perp }$ and $\pi \circ y\circ \ell _{0,e_1^\perp }\in \{\mathtt {0},\mathtt {1},\ldots , d-1\}^{\mathbb {Z}^{d-1}}$ are asymptotic with difference set $F\setminus \{-e_1\}$ . Therefore, $\pi \circ x\circ \ell _{k,e_1^\perp }=\pi \circ y\circ \ell _{k,e_1^\perp }$ for every $k\in \mathbb {Z}\setminus \{0\}$ . So we have

$$ \begin{align*} g(\sigma^{ke_1}x) &=f(\pi\circ \sigma^{ke_1}x\circ\ell_{0,e_1^\perp}) =f(\pi\circ x\circ\ell_{k,e_1^\perp})\\ &=f(\pi\circ y\circ\ell_{k,e_1^\perp}) =f(\pi\circ \sigma^{ke_1}y\circ\ell_{0,e_1^\perp}) =g(\sigma^{ke_1}y) \end{align*} $$

for every $k\in \mathbb {Z}\setminus \{0\}$ . Moreover, for every $r\in \mathbb {Z}^{d-1}$ , we have

$$ \begin{align*} f(\pi\kern1.4pt{\circ}\kern1.4pt x\kern1.4pt{\circ}\kern1.4pt\ell_{0,e_1^\perp}) \kern1.2pt{-}\kern1.2ptf(\pi\kern1.4pt{\circ}\kern1.4pt y\kern1.4pt{\circ}\kern1.4pt\ell_{0,e_1^\perp}) &=f(\pi\kern1.4pt{\circ}\kern1.4pt x\kern1.4pt{\circ}\kern1.4pt\ell_{0,e_1^\perp})\kern1.4pt{+}\kern1.4ptT^r(0) \kern1.4pt{-}\kern1.4ptf(\pi\kern1.4pt{\circ}\kern1.4pt y\kern1.4pt{\circ}\kern1.4pt\ell_{0,e_1^\perp})\kern1.4pt{-}\kern1.4ptT^r(0)\\ &=f(\sigma^r\pi\circ x\circ\ell_{0,e_1^\perp}) -f(\sigma^r\pi\circ y\circ\ell_{0,e_1^\perp}), \end{align*} $$

which goes to 0 when $\Vert r\Vert \to \infty $ since $\pi \circ x\circ \ell _{0,e_1^\perp }$ and $\pi \circ y\circ \ell _{0,e_1^\perp }$ are asymptotic. We conclude that

(10) $$ \begin{align} g(\sigma^{ke_1}x)=g(\sigma^{ke_1}y) \end{align} $$

for every $k\in \mathbb {Z}$ .

The remainder of the proof is based on the following observation which we use several times.

Observation 5.11. Let $d\geq 2$ be an integer. Let $z,z'\in \overline {\mathrm {Orb}(x)}$ . If for all $m\in \mathbb {N}$ there exist two patterns u and v of support and a vector $t\in \{0\}\times \mathbb {Z}^{d-1}$ such that

$$ \begin{align*} \pi(z),\pi(z') \in[u]\cap\sigma^{t+e_1}[v], \end{align*} $$

then

$$ \begin{align*} g(z) -g(\sigma^{-e_1}z) = g(z') -g(\sigma^{-e_1}z'). \end{align*} $$

Proof. The domain of the factor map f is compact so f is uniformly continuous. Therefore, for all $\varepsilon>0$ , there exists $m\in \mathbb {N}$ such that for all patterns w of shape , the Lebesgue measure of the interval $f([w])$ is less than $\varepsilon /2$ . Since the Lebesgue measure of the interval $f(\sigma ^k[w])=T^k(f([w]))$ is equal to the Lebesgue measure of $f([w])$ for every $k\in \mathbb {Z}^{d-1}$ , we also have that for all patterns w of shape , the Lebesgue measure of the interval $f([w])$ is less than $\varepsilon /2$ . From the hypothesis, let u and v be two patterns of support , and ${t\in \{0\}\times \mathbb {Z}^{d-1}}$ be a vector such that $\pi (z),\pi (z') \in [u]\cap \sigma ^{t+e_1}[v]$ . We obtain

$$ \begin{align*} g(z) - g(\sigma^{-e_1}z) &= f(\pi\circ z\circ\ell_{0,e_1^\perp}) - f(\pi\circ\sigma^{-e_1}z\circ\ell_{0,e_1^\perp}) \\ &= f(\pi(z)\circ\ell_{0,e_1^\perp}) - f(\sigma^{-e_1}\pi(z)\circ\ell_{0,e_1^\perp}) \\ &\in f([u]\circ\ell_{0,e_1^\perp}) - f(\sigma^{t} [v]\circ\ell_{0,e_1^\perp}), \end{align*} $$

which is an interval in $\mathbb {R}/\mathbb {Z}$ of size at most ${\varepsilon }/{2} +{\varepsilon }/{2}=\varepsilon $ . Similarly,

$$ \begin{align*} g(z') - g(\sigma^{-e_1}z') \in f([u]\circ\ell_{0,e_1^\perp}) - f(\sigma^{t} [v]\circ\ell_{0,e_1^\perp}). \end{align*} $$

Thus, we have

$$ \begin{align*} \vert ( g(z) - g(\sigma^{-e_1}z) ) - ( g(z') - g(\sigma^{-e_1}z') ) \vert \leq \varepsilon. \end{align*} $$

Since this holds for all $\varepsilon>0$ , it concludes the proof of the observation.

Our first goal is to show using Observation 5.11 that for all $k\in \mathbb {Z}$ , we have

(11) $$ \begin{align} g(\sigma^{ke_1}x) - g(\sigma^{(k-1)e_1}x) \in\{ g(\sigma^{e_1}x) -g(x), g(x) -g(\sigma^{-e_1}x), g(\sigma^{-e_1}x) -g(\sigma^{-2e_1}x)\}. \end{align} $$

Let $m\in \mathbb {N}$ . Let be a d-dimensional box in $\mathbb {Z}^d$ of size m in all directions except the direction $e_1$ . Let u and v be two patterns of support appearing in the configuration x such that $\sigma ^{ke_1}x \in [u]\cap \sigma ^{e_1}[v]$ . Thus,

$$ \begin{align*} \pi(\sigma^{ke_1}x) \in[\pi(u)]\cap\sigma^{e_1}[\pi(v)]. \end{align*} $$

The fact that the pair $(x,y)$ is indistinguishable implies that the pattern $[u]\cap \sigma ^{e_1}[v]$ of support $B\cup (B-e_1)$ must appear in x (and y) intersecting the difference set. Therefore, there exists $r\in \{0\}\times \mathbb {Z}^{d-1}$ and $j\in \{-1,0,1\}$ such that $\sigma ^{je_1+r}x \in [u]\cap \sigma ^{e_1}[v]$ . Thus,

$$ \begin{align*} \pi(\sigma^{je_1+r}x) \in[\pi(u)]\cap\sigma^{e_1}[\pi(v)]. \end{align*} $$

From Observation 5.11 (here $t=0$ ), we obtain

$$ \begin{align*} g(\sigma^{ke_1}x) -g(\sigma^{-e_1}\sigma^{ke_1}x) &= g(\sigma^{je_1+r}x) -g(\sigma^{-e_1}\sigma^{je_1+r}x)\\ &= g(\sigma^{je_1}x) + T^r(0) -g(\sigma^{(j-1)e_1}x) - T^r(0)\\ &= g(\sigma^{je_1}x) -g(\sigma^{(j-1)e_1}x), \end{align*} $$

which shows that equation (11) holds.

Our next goal is to show the existence of some $\rho \in \mathbb {R}/\mathbb {Z}$ such that

(12) $$ \begin{align} g(\sigma^{e_1}x) - g(x) = g(x) - g(\sigma^{-e_1}x) = g(\sigma^{-e_1}x) -g(\sigma^{-2e_1}x) = \rho. \end{align} $$

The strategy is to find patterns satisfying Observation 5.11. Let $m\in \mathbb {N}$ . Let be a d-dimensional box in $\mathbb {Z}^d$ of size m in all directions except the direction $e_1$ . Let $S\subset \{0\}\times \mathbb {Z}^{d-1}\subset {\mathbb {Z}^d}$ be the union of all translates of B that intersect the difference set $F\setminus \{-e_1\}$ of the pair $(\pi (x), \pi (y))$ , that is,

$$ \begin{align*} S = \bigcup_{k\in K} B+k, \quad \text{where} \quad K = \{k\in{\mathbb{Z}^d} \colon (B+k)\cap (F\setminus \{-e_1\})\neq\varnothing \}. \end{align*} $$

The restrictions of the configurations $\pi (x)$ and $\pi (y)$ to the support S have the nice property of containing their language of patterns of shape B in the most optimal way, that is, they contain exactly one occurrence of each pattern of shape B. Indeed, from Proposition 5.6, the configurations $\pi \circ x\circ \ell _{0,e_1^\perp }$ and $\pi \circ y\circ \ell _{0,e_1^\perp }\in \{\mathtt {0},\mathtt {1},\ldots ,d-1\}^{\mathbb {Z}^{d-1}}$ satisfy the $(d-1)$ -dimensional ordered flip condition. Therefore, from Corollary 3.13, it follows that the patterns $H_x=\pi (x)|_S$ and $H_y=\pi (y)|_S$ contain exactly one occurrence of every pattern of shape B that are in $\mathcal {L}_B(\pi (x))=\mathcal {L}_B(\pi (y))$ .

We write $\pi (x)\in [H_x]$ and $\pi (y)\in [H_y]$ , where the cylinders are within $\overline {\mathrm {Orb}(\pi (x))}$ . Since $\pi (x)_0\neq \pi (y)_0$ , we have $[H_x]\cap [H_y]=\varnothing $ . Observe also that, from Corollary 3.13, the pattern $H_x$ has only one occurrence in $\pi (x)$ whose support intersects the difference set $F\setminus \{-e_1\}$ . More formally, if $v\in F\setminus \{-e_1\}-S$ and $[H_x]\cap \sigma ^v[H_x]\neq \varnothing $ , then $v=0$ .

From Proposition 5.6, we also have $\mathcal {L}(\pi \circ x\circ \ell _{0,e_1^\perp }) = \mathcal {L}(\pi \circ y\circ \ell _{0,e_1^\perp })$ . From Lemma 5.8, for every $v\in {\mathbb {Z}^d}$ , we have

$$ \begin{align*} \mathcal{L}(\pi\circ x\circ\ell_{v,e_1^\perp}) \subseteq \mathcal{L}(\pi\circ x\circ\ell_{0,e_1^\perp}) = \mathcal{L}(\pi\circ y\circ\ell_{0,e_1^\perp}) \supseteq \mathcal{L}(\pi\circ y\circ\ell_{v,e_1^\perp}). \end{align*} $$

Since x is uniformly recurrent, we have that $\pi \circ x\circ \ell _{0,e_1^\perp }$ and $\pi \circ y\circ \ell _{0,e_1^\perp }$ are uniformly recurrent by Lemma 5.9. Thus, $\overline {\mathrm {Orb}(\pi \circ x\circ \ell _{0,e_1^\perp })} =\overline {\mathrm {Orb}(\pi \circ y\circ \ell _{0,e_1^\perp })}$ is a minimal subshift. We deduce $\pi \circ x\circ \ell _{v,e_1^\perp }\in \overline {\mathrm {Orb}(\pi \circ x\circ \ell _{0,e_1^\perp })}$ , $\pi \circ y\circ \ell _{v,e_1^\perp }\in \overline {\mathrm {Orb}(\pi \circ y\circ \ell _{0,e_1^\perp })}$ , and the equality of the languages:

$$ \begin{align*} \mathcal{L}(\pi\circ x\circ\ell_{v,e_1^\perp}) = \mathcal{L}(\pi\circ x\circ\ell_{0,e_1^\perp}) = \mathcal{L}(\pi\circ y\circ\ell_{0,e_1^\perp}) = \mathcal{L}(\pi\circ y\circ\ell_{v,e_1^\perp}) \end{align*} $$

for every $v\in {\mathbb {Z}^d}$ .

Therefore, the pattern $H_x$ must occur in $\pi \circ y\circ \ell _{e_1,e_1^\perp }$ . Let $t\in \{0\}\times \mathbb {Z}^{d-1}$ be such that $\pi (y)\in [\sigma ^{-e_1-t}H_x]$ . Since $\pi \circ x\circ \ell _{e_1,e_1^\perp } =\pi \circ y\circ \ell _{e_1,e_1^\perp }$ , we also have $\pi (x)\in [\sigma ^{-e_1-t}H_x]$ . Recall that by Proposition 2.6, we have that $(\pi (x), \pi (y))$ is an indistinguishable asymptotic pair. Since the pattern $\pi (x)|_{S\cup (S-t-e_1)}$ appears in $\pi (x)$ intersecting the difference set $F\setminus \{-e_1\}$ , it must appear in $\pi (y)$ intersecting the difference set $F\setminus \{-e_1\}$ . Formally, there exists $v\in F\setminus \{-e_1\}-(S\cup (S-t-e_1))$ such that $\sigma ^{-v}(\pi (x))\in [\sigma ^{-e_1-t}H_x]\cap [H_y]$ . There are two cases to consider.

• • If $v\in F\setminus \{-e_1\}-S$ , then $\sigma ^{e_1+t}(\pi (x))\in [H_x]\cap \sigma ^v[H_x]$ . Therefore, $v=0$ and $\pi (x)=\sigma ^{-v}(\pi (x))\in [H_y]$ . However, $\pi (x)\in [H_x]$ , which contradicts ${[H_x]\cap [H_y]=\varnothing }$ .

• • If $v\in F\setminus \{-e_1\}-(S-e_1-t)$ , then $\pi (x)\in [H_x]\cap \sigma ^{v-e_1-t}[H_x]$ . Also $v-e_1-t\in F\setminus \{-e_1\}-S$ , and thus we must have $v-e_1-t=0$ . Therefore, $\pi (x)\in [\sigma ^{v}H_y]=[\sigma ^{e_1+t}H_y]$ .

Let $Q=(\sigma ^{-2e_1-2t}\pi (x))|_S$ . We have that

$$ \begin{align*} \pi(x)&\in [\sigma^{-e_1-t}H_x] \cap [H_x] \cap [\sigma^{e_1+t}H_y] \cap [\sigma^{2e_1+2t}Q],\\ \pi(y)&\in [\sigma^{-e_1-t}H_x] \cap [H_y] \cap [\sigma^{e_1+t}H_y] \cap [\sigma^{2e_1+2t}Q]. \end{align*} $$

The current situation is depicted in Figure 12.

Figure 12 The patterns $H_x$ and $H_y$ appearing in configurations $\pi (x)$ and $\pi (y)$ . The pattern $\pi (x)|_{S\cup (S-t-e_1)\cup (S-2t-2e_1)}$ is shown in gray background. Since it appears in $\pi (x)$ intersecting the difference set $F\setminus \{-e_1\}$ , it must appear in $\pi (y)$ intersecting the difference set $F\setminus \{-e_1\}$ .

Figure 13 The pattern $\pi (x)|_{S\cup (S-t-e_1)\cup (S-2t-2e_1)}$ , shown in gray, appears in $\pi (y)$ intersecting the difference set $F\setminus \{-e_1\}$ in one of three ways. To lighten the figure, we omit the shifts $\sigma ^{e_1+t}$ in the ellipses. In the first case, the non-trivial overlap of $H_y$ with itself is impossible, which implies $H_x=H_y$ , which is a contradiction. In the second case, the non-trivial overlap of $H_y$ with itself is impossible, which implies that $H_y=Q$ . In the third case, the proof uses the existence of patterns $u_x$ and $u_y$ .

Since the pattern $\pi (x)|_{S\cup (S-t-e_1)\cup (S-2t-2e_1)}$ appears in $\pi (x)$ intersecting the difference set $F\setminus \{-e_1\}$ , it must appear in $\pi (y)$ intersecting the difference set $F\setminus \{-e_1\}$ . Formally, there exists $v\in F\setminus \{-e_1\}-(S\cup (S-t-e_1)\cup (S-2t-2e_1))$ such that $\sigma ^{-v}(\pi (x))\in [\sigma ^{-e_1-t}H_x]\cap [H_y]\cap [\sigma ^{e_1+t}H_y]$ . We consider three cases, see Figure 13.

• • If $v\in F\setminus \{-e_1\}-S$ , then $\sigma ^{e_1+t}(\pi (x))\in [H_x]\cap \sigma ^v[H_x]$ . Therefore, $v=0$ and $\pi (x)=\sigma ^{-v}(\pi (x))\in [H_y]$ . However, $\pi (x)\in [H_x]$ , which contradicts ${[H_x]\ \cap} $ ${[H_y]=\varnothing} $ .

• • If $v\in F\setminus \{-e_1\}-(S-t-e_1)$ , then $\sigma ^{-e_1-t}(\pi (x))\in [H_y]\cap \sigma ^{v-e_1-t}[H_y]$ . Also $v-e_1-t\in F\setminus \{-e_1\}-S$ , and thus we must have $v-e_1-t=0$ . On the one hand, we have $\sigma ^{-v}\pi (x)\in [\sigma ^{e_1+t}H_y]$ . On the other hand, we have $\sigma ^{-v}\pi (x)=\sigma ^{-e_1-t}\pi (x)\in [\sigma ^{e_1+t}Q]$ . We deduce the equality $Q=H_y$ . We may now use Observation 5.11. Let $u=\pi (y)|_B$ be the pattern of support B within $H_y$ . We have

  $$ \begin{align*} \pi(y)\in[H_y]\subset[u] \quad \text{and} \quad \pi(y)\in[\sigma^{e_1+t}H_y]\subset[\sigma^{e_1+t}u]. \end{align*} $$
  Also,
  $$ \begin{align*} \sigma^{-e_1-t}\pi(y)\in[H_y]\subset[u] \quad \text{and} \quad \sigma^{-e_1-t}\pi(y)\in[\sigma^{e_1+t}Q]=[\sigma^{e_1+t}H_y]\subset[\sigma^{e_1+t}u]. \end{align*} $$
  The pattern u also appears in $H_x$ Let $r\in F\setminus \{-e_1\}-B$ such that $[\sigma ^rH_x]\subset [u]$ . We have
  $$ \begin{align*} \sigma^{e_1+t+r}\pi(x)\in[\sigma^rH_x]\subset[u] \quad \text{and} \quad \sigma^{e_1+t+r}\pi(x)\in[\sigma^{e_1+t+r}H_x]\subset[\sigma^{e_1+t}u]. \end{align*} $$
  Since the above holds for pattern u of arbitrarily large size, from Observation 5.11, we conclude that
  $$ \begin{align*} g(\sigma^{e_1}x) - g(x) = g(y) - g(\sigma^{-e_1}y) = g(\sigma^{-e_1}y) -g(\sigma^{-2e_1}y) = \rho \end{align*} $$
  for some $\rho \in \mathbb {R}/\mathbb {Z}$ .

• • If $v\in F\setminus \{-e_1\}-(S-2t-2e_1)$ , then $\sigma ^{-v+e_1+t}(\pi (x))\in [H_x]\cap \sigma ^{-v+2e_1+2t}[H_y]$ . Since $v-2e_1-2t\in F\setminus \{-e_1\}-S$ , the support $S+v-2e_1-2t$ of the translated pattern $\sigma ^{-v+2e_1+2t}[H_y]$ intersects the difference set $F\setminus \{-e_1\}$ . Let $\gamma \in \{0\}\times \mathbb {Z}^{d-1}$ be such that $B+\gamma \subset S+v-2e_1-2t$ and $B+\gamma \cap F\setminus \{-e_1\}\neq \varnothing $ . By definition of S, we also have $B+\gamma \subset S$ . In other words, $u_x=\pi (x)|_{B+\gamma }$ is a subpattern of $H_x$ and of $\sigma ^{-v+2e_1+2t}H_y$ , and thus satisfies

  $$ \begin{align*} [H_x]\cap\sigma^{-v+2e_1+2t}[H_y]\subset[u_x]. \end{align*} $$
  Similarly, we have $\sigma ^{-v}(\pi (x))\kern1.7pt{\in}\kern1.7pt [H_y]\kern1.7pt{\cap}\kern1.7pt \sigma ^{-v+2e_1+2t}[Q]$ . We obtain that ${u_y\kern1.7pt{=}\kern1.7pt\pi (y)|_{B+\gamma }}$ is a subpattern of $H_y$ and of $\sigma ^{-v+2e_1+2t}Q$ , and thus satisfies
  $$ \begin{align*} [H_y]\cap\sigma^{-v+2e_1+2t}[Q]\subset[u_y]. \end{align*} $$
  In summary, we have
  $$ \begin{align*} \sigma^{e_1+t}\pi(y)\in[H_x]\subset[u_x] \quad \text{and} \quad \sigma^{e_1+t}\pi(y)\in[\sigma^{e_1+t}H_y]\subset[\sigma^{e_1+t}u_y]. \end{align*} $$
  Also
  $$ \begin{align*} \pi(x)\in[H_x]\subset[u_x] \quad \text{and} \quad \pi(x)\in[\sigma^{e_1+t}H_y]\subset[\sigma^{e_1+t}u_y]. \end{align*} $$
  Moreover,
  $$ \begin{align*} &\sigma^{-v+e_1+t}\pi(x)\in\sigma^{-v+e_1+t}[\sigma^{e_1+t}H_y] \subset[u_x]\\ &\sigma^{-v+e_1+t}\pi(x)\in\sigma^{-v+e_1+t}[\sigma^{2e_1+2t}Q] =\sigma^{e_1+t}[\sigma^{-v+2e_1+2t}Q] \subset[\sigma^{e_1+t}u_y]. \end{align*} $$
  Since the above holds for patterns $u_x$ and $u_y$ of arbitrarily large size, from Observation 5.11, we conclude that
  $$ \begin{align*} g(\sigma^{e_1}y) - g(y) = g(x) - g(\sigma^{-e_1}x) = g(\sigma^{-e_1}x) -g(\sigma^{-2e_1}x) = \rho \end{align*} $$
  for some $\rho \in \mathbb {R}/\mathbb {Z}$ .

Using equation (10), we obtain that equation (12) holds. From equations (11) and (12), we conclude that there exists $\rho \in \mathbb {R}/\mathbb {Z}$ such that for all $k\in \mathbb {Z}$ , we have

$$ \begin{align*} g(\sigma^{ke_1}x) = g(x) + k\rho = R_\rho^{k}(g(x)). \end{align*} $$

Since $\overline {\mathrm {Orb}(x)}$ is minimal and g is continuous, we conclude that for every $z\in \overline {\mathrm {Orb}(x)}$ and $k\in \mathbb {Z}$ , we have $g(\sigma ^{ke_1}z)=R_\rho ^{k}(g(z))$ .

5.4. Proof of Theorem B

In this subsection, we prove Theorem B. The proof is essentially done in Proposition 5.13 which assumes the ordered flip condition. The proof is done by induction on the dimension using results proved in the previous subsection. First, we need the next lemma which is used thereafter.

Lemma 5.12. Let $A,B\subset \mathbb {R}$ be two closed sets such that $A\cup B$ is a compact interval I. If $A\cap B$ is a singleton, then A and B are intervals.

Proof. Let x be the element in $A \cap B$ and let $A' = \operatorname {Int}(I) \setminus A$ and $B' = \operatorname {Int}(I) \setminus B$ . Then $A' \cup B' = \operatorname {Int}(I) \setminus \{x\}$ .

If x is in the boundary of I, we conclude that either $A'$ or $B'$ is empty, as both are open disjoint sets and $\operatorname {Int}(I)$ is connected. Therefore, one of $A,B$ is equal to I and the other is equal to the singleton $\{x\}$ .

If x is in the interior of I, we may write $\operatorname {Int}(I) \setminus \{x\}$ as the union of two open intervals. Again, as they are connected, it follows that one must be $A'$ and the other $B'$ , from where it follows that A and B are intervals.

Proposition 5.13. Let $d\geq 1$ be an integer. Let $x,y \in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{{\mathbb {Z}^d}}$ be an indistinguishable asymptotic pair satisfying the ordered flip condition and assume x is uniformly recurrent. There exists a totally irrational vector $\alpha = (\alpha _1,\ldots ,\alpha _d)\in [0,1)^d$ such that $ 1>\alpha _1 >\alpha _2 >\cdots >\alpha _d >0$ , and $x=c_{\alpha }$ , $y=c^{\prime }_{\alpha }$ are the d-dimensional characteristic Sturmian configurations with slope $\alpha $ .

Proof. Our proof proceeds by induction on the dimension d. The base case $d=1$ is given in Theorem 2.16. Let $d>1$ and assume that Proposition 5.13 holds for $d-1$ . As the configurations $\pi \circ x\circ \ell _{0,e_1^\perp }$ and $\pi \circ y\circ \ell _{0,e_1^\perp }\in \{\mathtt {0},\mathtt {1},\ldots ,d-1\}^{\mathbb {Z}^{d-1}}$ satisfy the ${(d-1)}$ -dimensional ordered flip condition and $\pi \circ x\circ \ell _{0,e_1^\perp }$ is uniformly recurrent (Lemma 5.9 and Proposition 5.6), it follows by the induction hypothesis that $\pi \circ x\circ \ell _{0,e_1^\perp }$ and $\pi \circ y\circ \ell _{0,e_1^\perp }$ are $(d-1)$ -dimensional characteristic Sturmian configurations associated to a totally irrational slope $(\alpha _2,\ldots ,\alpha _d)\in [0,1)^{d-1}$ , satisfying $ 1>\alpha _2 >\cdots >\alpha _d >0$ , that is,

$$ \begin{align*} \pi\circ x\circ\ell_{0,e_1^\perp}=c_{(\alpha_2,\ldots,\alpha_d)} \quad \mbox{and}\quad \pi\circ y\circ\ell_{0,e_1^\perp}=c^{\prime}_{(\alpha_2,\ldots,\alpha_d)}. \end{align*} $$

Let f be the factor map $f\colon \overline {\mathrm {Orb}(\pi \circ x\circ \ell _{0,e_1^\perp })}\to \mathbb {R}/\mathbb {Z}$ obtained in Lemma 5.2 which commutes the $(d-1)$ -dimensional shift on $\overline {\mathrm {Orb}(\pi \circ x\circ \ell _{0,e_1^\perp })}$ with the $(d-1)$ -dimensional rotation by $(\alpha _2,\ldots ,\alpha _d)$ on the circle $\mathbb {R}/\mathbb {Z}$ . From Proposition 5.10, there exist $\rho _1\in \mathbb {R}/\mathbb {Z}$ and a topological factor map $g\colon \overline {\mathrm {Orb}(x)}\to \mathbb {R}/\mathbb {Z}$ that commutes the d-dimensional shift with the d-dimensional rotation by $(\rho _1,\alpha _2,\ldots ,\alpha _d)$ on the circle $\mathbb {R}/\mathbb {Z}$ .

The map g is explicitly given by $g(w)=f(\pi \circ w\circ \ell _{0,e_1^\perp })$ . In particular, $g([\mathtt {0}]\cup [\mathtt {1}])$ , $g([\mathtt {2}])$ , $\ldots $ , $g([d])$ are consecutive intervals from left to right on the unit interval.

Next we show that $g([\mathtt {0}])$ and $g([\mathtt {1}])$ are also intervals using Lemma 5.12. As both $[0]\cap \overline {\mathrm {Orb}(x)}$ and $[1]\cap \overline {\mathrm {Orb}(x)}$ are compact and g is continuous, it follows that their images are closed, and thus it suffices to show that their intersection is a singleton.

We have $g(x)=g(y)=0$ . Thus, $g(\sigma ^{-e_1}x)=g(\sigma ^{-e_1}y)=-\rho _1$ . Also, $\sigma ^{-e_1}x\in [\mathtt {1}]$ and $\sigma ^{-e_1}y\in [\mathtt {0}]$ . Therefore, $-\rho _1\in g([\mathtt {0}])\cap g([\mathtt {1}])$ . By contradiction, suppose that $g([\mathtt {0}])\cap g([\mathtt {1}])$ contains another element $\gamma \neq -\rho _1$ . Therefore, there exist ${w,z\in \overline {\mathrm {Orb}(x)}}$ with $w\in [\mathtt {0}]$ and $z\in [\mathtt {1}]$ such that $g(w)=g(z)=\gamma $ . Since $g(w)=g(z)$ , the configurations w and z are equal on many positions. More precisely, if $v\in {\mathbb {Z}^d}$ is such that $g(\sigma ^v(w))=\gamma + v\cdot (\rho _1,\alpha _2,\ldots ,\alpha _d)=g(\sigma ^v(z))$ is in the interior of the interval $g([\mathtt {i}])$ for some $\mathtt {i}\in \{\mathtt {2},\ldots ,\mathtt {d}\}$ , then $w_v=\mathtt {i}=z_v$ . In other words, the set

$$ \begin{align*} V=\{v\in{\mathbb{Z}^d}\colon \gamma + v\cdot (\rho_1,\alpha_2,\ldots,\alpha_d) \in\operatorname{Int}(g([\mathtt{i}])) \text{ for some }\mathtt{i}\in\{\mathtt{2},\ldots,\mathtt{d}\}\} \end{align*} $$

satisfies $w|_V=z|_V$ .

Let $\varepsilon>0$ be such that $\varepsilon <|\gamma -(-\rho _1)|$ and $\varepsilon <|\alpha _d|$ . Let $m\in \mathbb {N}$ be such that the Lebesgue measure of $f([q])$ is less than $\varepsilon $ for every allowed pattern appearing in the configuration $\pi \circ x\circ \ell _{0,e_1^\perp }$ . Let and $p' \in \mathcal {L}_{B_m}(x)$ be a pattern such that the number of sites ${S = \{ u \in B_m : p'(u) \in \{\mathtt {2},\ldots ,d\}\}}$ is maximized. Let $p\colon S\to \{\mathtt {2},\ldots ,d\}$ be the restriction of $p'$ to S. From the maximality of the set $S\subset B_m$ , we know that for every $u\in {\mathbb {Z}^d}$ such that $\sigma ^u(x)\in [p]$ , we have $\sigma ^u(x)|_{B_m\setminus S}$ is a pattern over symbols $\mathtt {0}$ and $\mathtt {1}$ only. Thus, the pattern p occurs at position $u\in {\mathbb {Z}^d}$ in x if and only if $\pi (p')$ occurs at position u in $\pi (x)$ . Also, the pattern $p\circ \ell _{0,e_1^\perp }$ occurs at position $u\in \mathbb {Z}^{d-1}$ in $x\circ \ell _{0,e_1^\perp }$ if and only if $\pi (p')\circ \ell _{0,e_1^\perp }$ occurs at position u in $\pi (x)\circ \ell _{0,e_1^\perp }$ . From Theorem A, the pattern $\pi (p')\circ \ell _{0,e_1^\perp }$ of connected support occurs in $\pi (x)\circ \ell _{0,e_1^\perp }$ with support intersecting the difference set of the asymptotic pair $(\pi (x)\circ \ell _{0,e_1^\perp }, \pi (y)\circ \ell _{0,e_1^\perp })$ in a unique position. Therefore, the pattern p occurs in x in a unique position with support intersecting the set $F\setminus \{-e_1\}$ . We use this property multiple times below.

From the maximality of S, we also have that $[\pi (p)]=[\pi (p')]$ , where the cylinders are taken within $\pi (\overline {\mathrm {Orb}(x)})$ . On the one hand, it is clear that $[\pi (p')]\subseteq [\pi (p')|_S]=[\pi (p)]$ . On the other hand, suppose $c\in \overline {\mathrm {Orb}(x)}$ such that $\pi (c)\in [\pi (p)]$ . If $\pi (c_k)\neq \mathtt {0}$ for some $k\in B_m\setminus S$ , then $c_n=\pi (c_k)+1\in \{\mathtt {2},\ldots ,d\}$ . Thus, the pattern $c|_{S\cup \{k\}}$ is strictly larger than the pattern p and this contradicts the maximality of the set S. Thus, $\pi (c)\in [\pi (p')]$ and hence $[\pi (p)]\subseteq [\pi (p')]$ . Since the support of $[\pi (p')]$ is connected, we deduce from Lemma 4.8 that $g([p]) =f([\pi (p)]\circ \ell _{0,e_1^\perp }) =f([\pi (p')]\circ \ell _{0,e_1^\perp })$ is a non-empty interval whose length is at most $\varepsilon $ .

As $(\alpha _2,\ldots ,\alpha _d)$ is totally irrational, the interval $g([p])$ has non-empty interior and there exists $u\in (\{0\}\times \mathbb {Z}^{d-1})\setminus S$ such that $g(\sigma ^{-u}(z))=g(\sigma ^{-u}(w))=\gamma - u\cdot (0,\alpha _2,\ldots ,\alpha _d) \in \operatorname {Int}(g([p]))$ . Thus, $\sigma ^{-u}(w)\in [p]$ and $\sigma ^{-u}(z)\in [p]$ . Equivalently, ${w\in \sigma ^u([p])}$ and $z\in \sigma ^u([p])$ . For each $\mathtt {i}\in \{\mathtt {0},\mathtt {1},d\}$ , let $q_{\mathtt {i}}\colon \{0\}\cup (S-u)\to \{\mathtt {0},\mathtt {1},\ldots ,d\}$ be the pattern defined by

$$ \begin{align*} q_{\mathtt{i}}(n)= \begin{cases} p(n+u) & \mbox{if } n \in S-u,\\ \mathtt{i} & \mbox{if } n = 0. \end{cases} \end{align*} $$

We have $w\in [\mathtt {0}]\cap \sigma ^{u}([p])=[q_{\mathtt {0}}]$ and $z\in [\mathtt {1}]\cap \sigma ^{u}([p])=[q_{\mathtt {1}}]$ . Also, $[d]\cap \sigma ^{u}([p])=[q_d]$ .

By Lemma 3.2, the pattern $q_{\mathtt {1}}$ must occur in x intersecting the difference set. Recall that $x_{-e_1}=\mathtt {1}$ . However, $\sigma ^{-e_1}x\notin [q_{\mathtt {1}}]$ since the opposite implies that ${-\rho _1=}$ ${g(\sigma ^{-e_1}x)\in g([q_{\mathtt {1}}])\subset g(\sigma ^{u}([p]))}$ . Since $\gamma =g(w) \in g(\sigma ^{u}([p]))$ and $g(\sigma ^{u}([p]))= g([p])+ u\cdot (\rho _1,\alpha _2,\ldots ,\alpha _d)\subset \mathbb {R}/\mathbb {Z}$ is an interval of length at most $\varepsilon $ , we have $|\gamma -(-\rho _1)|<\varepsilon $ , which is a contradiction. Therefore, the pattern $q_{\mathtt {1}}$ must occur in x intersecting the difference set in such a way that the subpattern p intersects the difference set. Since the symbol $\mathtt {1}=x_{-e_1}$ is not in the pattern p, the pattern $q_{\mathtt {1}}$ must occur in x in such a way that the subpattern p intersects the set $F\setminus \{-e_1\}$ .

The pattern $q_{\mathtt {0}}$ must also occur in x intersecting the difference set. Since the pattern $q_{\mathtt {0}}$ does not contain the symbol $\mathtt {1}=x_{-e_1}$ , the pattern $q_{\mathtt {0}}$ must occur in x intersecting the set $F\setminus \{-e_1\}$ . As there is exactly one occurrence of the subpattern p occurring in x intersecting the set $F\setminus \{-e_1\}$ , we must have $x\in [q_{\mathtt {0}}]\subset \sigma ^{u}([p])$ . This implies that ${y\in [q_d]}$ . Thus, the pattern $q_d$ is in the language of x and must also appear in x intersecting the difference set. Since the pattern $q_d$ does not contain the symbol $\mathtt {1}=x_{-e_1}$ , the pattern $q_d$ must occur in x intersecting the set $F\setminus \{-e_1\}$ . Again, we recall that there is exactly one occurrence of the subpattern p occurring in x intersecting the set $F\setminus \{-e_1\}$ . Therefore, we must have $\sigma ^{-e_d}x\in [q_d]\subset \sigma ^{u}([p])$ . In summary, we have $0=g(x)\in g(\sigma ^{u}([p]))$ and $-\alpha _d=g(\sigma ^{-e_d}x)\in g(\sigma ^{u}([p]))$ . Since $g(\sigma ^{u}([p]))$ is an interval of length at most $\varepsilon $ , we have $|0-(-\alpha _d)|<\varepsilon $ , which is a contradiction. Thus, we conclude that $g([\mathtt {0}])\cap g([\mathtt {1}])$ is a singleton and thus from Lemma 5.12, we deduce that $g([\mathtt {0}])$ and $g([\mathtt {1}])$ are intervals. More precisely, from the facts that $g(x)=0$ , $g(\sigma ^{-e_2}y)=1$ , and $-\rho _1 \in g([0])\cap g([1])$ , we conclude that $g([0]) = [0,-\rho _1]$ and $g([1]) = [-\rho _1,-\alpha _2]$ .

We now claim that the vector $\widetilde {\alpha } = (\rho _1,\alpha _2,\ldots ,\alpha _d)$ is totally irrational. Indeed, were it not the case, there would exist a non-zero $n \in {\mathbb {Z}^d}$ for which $n \cdot \widetilde {\alpha } =0 \bmod {1}$ . Let $\beta \in \mathbb {R}/\mathbb {Z}$ be rationally independent with $\widetilde {\alpha }$ . It follows that for any $m \in {\mathbb {Z}^d}$ , the value $\beta +m\cdot \widetilde {\alpha } \in \mathbb {R}/\mathbb {Z}$ does not lie in the boundary of the intervals $g([\mathtt {i}])$ . In particular, $g^{-1}(\beta )$ is a singleton. Indeed, let $\widetilde {w},\widetilde {z}\in g^{-1}(\beta )$ . Then for every $m\in {\mathbb {Z}^d}$ , we have $g(\sigma ^m(\widetilde {w}))=g(\sigma ^m(\widetilde {z}))=\beta +m\cdot \widetilde {\alpha }\in \operatorname {Int}(g([\mathtt {i}]))$ for some $\mathtt {i}\in \{\mathtt {0},\ldots ,d\}$ . Thus, $\widetilde {w}_m=\mathtt {i}=\widetilde {z}_m$ and globally we have the equality $\widetilde {w}=\widetilde {z}$ . Since $n \cdot \widetilde {\alpha } =0 \bmod {1}$ , then it follows that ${\sigma ^n(\widetilde {w}) = \widetilde {w}}$ . By minimality of $\overline {\mathrm {Orb}(x)}$ , it follows that every configuration $\widetilde {z}$ in $\overline {\mathrm {Orb}(x)}$ satisfies $\sigma ^n(\widetilde {z}) = \widetilde {z}$ . This is incompatible with x and y having a finite difference set as we would have

$$ \begin{align*} x|_F = \sigma^{kn}(x)|_F = \sigma^{kn}(y)|_F = y|_F \mbox{ for arbitrarily large } k \in \mathbb{N}. \end{align*} $$

Hence, as $\widetilde {\alpha }$ is totally irrational, it follows that the orbit ${\mathbb {Z}^d} \cdot \widetilde {\alpha }$ lies in the boundary of the intervals exactly for values in $F\cdot \widetilde {\alpha }$ . An inspection of the values on the difference set shows that

$$ \begin{align*} x=c_{\widetilde{\alpha}} \quad \mbox{and}\quad y=c^{\prime}_{\widetilde{\alpha}}.\\[-36pt] \end{align*} $$

Remark 5.14. Proposition 5.13 is proven by induction starting with the base case ${d=1}$ which is dealt with in Theorem 2.16. Technically, it might be possible to perform the induction using as base the case of dimension $d=0$ . In this way, Proposition 5.13 would contain an independent proof of the case $d=1$ about Sturmian configurations in $\mathbb {Z}$ . In the current state of our proof, this would demand significant changes to the previous lemmas so we do not do it here.

We now present the proof of Theorem B.

Proof of Theorem B

Let $\alpha \in [0,1)^d$ be totally irrational. From Lemma 4.5, the characteristic d-dimensional Sturmian configurations $c_{\alpha }$ and $c^{\prime }_{\alpha }$ are uniformly recurrent. From Theorem 4.10, $(c_{\alpha },c^{\prime }_{\alpha })$ is a non-trivial indistinguishable asymptotic pair. From Proposition 4.7, the pair $(c_{\alpha },c^{\prime }_{\alpha })$ satisfies the flip condition.

Let $x,y\in \{\mathtt {0},\mathtt {1},\ldots ,d\}^{\mathbb {Z}^d}$ be an indistinguishable asymptotic pair satisfying the flip condition and assume x is uniformly recurrent. Using Lemma 5.4, we obtain a permutation matrix $A \in \operatorname {GL}_d(\mathbb {Z})$ such that $(x\circ A,y\circ A)$ is an indistinguishable asymptotic pair which satisfies the ordered flip condition. A straightforward computation shows that $x\circ A$ is uniformly recurrent. From Proposition 5.13, there exists a totally irrational vector ${\alpha = (\alpha _1,\ldots ,\alpha _d)\in [0,1)^d}$ such that $ 1>\alpha _1 >\alpha _2 >\cdots >\alpha _d >0$ , and $x \circ A =c_{\alpha }$ , $y \circ A=c^{\prime }_{\alpha }$ are the d-dimensional characteristic Sturmian configurations with slope $\alpha $ . Then $x = c_{\alpha }\circ A^{-1}$ and $y=c^{\prime }_{\alpha }\circ A^{-1}$ .

Let us compute these configurations explicitly. Recall that the adjoint of a permutation matrix is its inverse, that is, $A^T=A^{-1}$ . It follows, using equation (2), that for every $m \in {\mathbb {Z}^d}$ , we have

$$ \begin{align*} x(m) = c_{\alpha}\circ (A^{-1}m) & = \sum\limits_{i=1}^d (\lfloor\alpha_i+(A^{-1}m)\cdot\alpha\rfloor -\lfloor (A^{-1}m)\cdot\alpha\rfloor)\\ & = \sum\limits_{i=1}^d (\lfloor\alpha_i+m\cdot (A\alpha)\rfloor -\lfloor m\cdot (A\alpha)\rfloor) = c_{A\alpha }(m). \end{align*} $$

Similarly, we get that $y(m) = c^{\prime }_{\alpha }\circ A^{-1}(m) = c^{\prime }_{A \alpha }(m)$ for every $m \in {\mathbb {Z}^d}$ . Thus, we obtain that $x = c_{A \alpha }$ and $y = c^{\prime }_{A \alpha }$ , as required.

We finish this section by extending our result to Corollary 2. Let us briefly recall the definition of the affine flip condition.

Definition 5.15. We say that an indistinguishable asymptotic pair $x,y \in \Sigma ^{{\mathbb {Z}^d}}$ with difference set $\underline {F}$ satisfies the affine flip condition if:

1. (1) there is $m \in \underline {F}$ such that $(\underline {F}-m)\setminus \{0\}$ is a base of ${\mathbb {Z}^d}$ ;

2. (2) the restriction $x|_{\underline {F}}$ is a bijection $\underline {F}\to \Sigma $ ;

3. (3) the map $x_n \mapsto y_n$ for all $n\in \underline {F}$ induces a cyclic permutation on $\Sigma $ .

Notice that the first condition of Definition 5.15 implies that $\#\underline {F} = d+1$ .

Let us also recall that Corollary 2 states if $x,y\in \Sigma ^{\mathbb {Z}^d}$ is such that x is uniformly recurrent, then the pair $(x,y)$ is an indistinguishable asymptotic pair satisfying the affine flip condition if and only if there exists a bijection $\tau \colon \{\mathtt {0},\mathtt {1},\ldots ,d\}\to \Sigma $ , there exists an invertible affine transformation $A\in \operatorname {Aff}({\mathbb {Z}^d})$ , and there exists a totally irrational vector $\alpha \in [0,1)^d$ such that $x=\tau \circ c_{\alpha }\circ A$ and $y=\tau \circ c^{\prime }_{\alpha }\circ A$ .

Proof of Corollary 2

Recall first that the property that a configuration is uniformly recurrent is invariant under affine transformations of ${\mathbb {Z}^d}$ and sliding-block codes. We shall use this fact implicitly in this proof.

Suppose first that $x=\tau \circ c_{\alpha } \circ A$ and $y=\tau \circ c_{\alpha } \circ A$ for some $A \in \operatorname {Aff}({\mathbb {Z}^d})$ and $\tau \colon \{\mathtt {0},\mathtt {1},\ldots ,d\}\to \Sigma $ . By Theorem B, $c_{\alpha },c^{\prime }_{\alpha }$ form an indistinguishable asymptotic pair which satisfies the flip condition. By Propositions 2.5 and 2.6, we obtain that ${x = \tau \circ c_{\alpha } \circ A, y = \tau \circ c^{\prime }_{\alpha } \circ A}$ is an indistinguishable asymptotic pair. Let us show that they satisfy the affine flip condition. As $\tau ,A$ are bijections, it is clear that if F is the difference set of $x,y$ , then $\underline {F} = A^{-1}(F)$ . It follows that $\#\underline {F} = d+1$ , that $\{ A^{-1}(n) - A^{-1}(0) : n \in \{-e_1,\ldots ,-e_d\}\}$ is a base of ${\mathbb {Z}^d}$ , that the restriction $x|_{\overline {F}}$ is a bijection, and that the map $x_n \mapsto y_n$ induces a cyclic permutation on $\Sigma $ . That is, $x,y$ satisfy the affine flip condition.

Conversely, if $x,y$ satisfy the affine flip condition, there is $m \in \underline {F}$ such that ${B= (\underline {F}-m)\setminus \{0\}}$ is a base of ${\mathbb {Z}^d}$ . Construct an integer matrix $\textbf {B} \in \operatorname {GL}_d(\mathbb {Z})$ by putting elements of $B = \{b_1,\ldots ,b_d\}$ in its columns. Let $A^{-1}\in \operatorname {Aff}({\mathbb {Z}^d})$ be the affine transformation such that $n \mapsto m + \textbf {B}n$ and notice that it maps F onto $\underline {F}$ sending $0$ to m. By the second and third conditions of the affine flip condition, there is a unique bijection $\tau ^{-1} \colon \Sigma \to \{\mathtt {0},\mathtt {1},\ldots ,d\}$ such that $\tau ^{-1}(x_m) = 0$ and $\tau ^{-1}(x_n) = \tau ^{-1}(y_n)-1 \bmod {d+1}$ for every $n \in \underline {F}$ . It follows directly from the choices of $A^{-1}$ and $\tau ^{-1}$ that $\tau ^{-1} \circ x \circ A^{-1},\tau ^{-1} \circ y \circ A^{-1}$ satisfy the flip condition. Furthermore, by Propositions 2.5 and 2.6, they form an indistinguishable asymptotic pair. Hence, by Theorem B, it follows that there is a totally irrational vector $\alpha \in [0,1]^d$ such that $\tau ^{-1} \circ x \circ A^{-1}= c_{\alpha }$ and $\tau ^{-1} \circ y \circ A^{-1}= c^{\prime }_{\alpha }$ . Thus, $x = \tau \circ c_{\alpha }\circ A$ and $y = \tau \circ c^{\prime }_{\alpha }\circ A.$

Proof of Corollary 3

It follows directly from Theorems A and B.