Proof Take two distinct elements in $\Sigma $ , say $0$ and $1$ , respectively. Define the following sequence $\{\alpha _n\}_{n\in \mathbb Z}$ of infinite strings from $\Sigma ^{\omega }$ :

$$ \begin{align*} \alpha_n = \begin{cases} (01)^{2^n}(011)^{2^n}...(01^{2^k})^{2^n}... & (n\geqslant0), \\ (01)(01^{2^{2^{-n}}})...(01^{(2^k)^{2^{-n}}})... & (n<0). \end{cases} \end{align*} $$

The idea behind this definition is the following. The string $\alpha _0$ is of the form:

$$ \begin{align*}(01) (011) (01111)\ldots (01^{2^k}) (01^{2^{k+1}})\ldots \end{align*} $$

Let us call the substrings $(01^{2^k})$ blocks of $\alpha _0$ . The above definition tells us that $\alpha _1$ is obtained from $\alpha _0$ by doubling each block of $\alpha _0$ . Similarly, $\alpha _{-1}$ is obtained from $\alpha _0$ by removing every other block. This process is propagated to all $\alpha _n$ 's.

We show that $\alpha _n \leqslant _{QI} \alpha _{n+1}$ for all $n\geqslant 0$ . For negative n, the proof is similar. In $\alpha _n$ consider the segment of the form

$$ \begin{align*}\underbrace{(01^{2^{k+1}})(01^{2^{k+1}})\ldots (01^{2^{k+1}})}_{2^n \text{ times}}. \end{align*} $$

We map this segment of $\alpha _n$ into the following segment of the string $\alpha _{n+1}$ :

$$ \begin{align*}\underbrace{(01^{2^{k}})(01^{2^{k}})(01^{2^{k}})(01^{2^{k}})\ldots (01^{2^{k}})(01^{2^{k}})}_{2^{n+1} \text{ times}}. \end{align*} $$

The mapping sends the block $(01^{2^{k+1}})$ in $\alpha _n$ into $(01^{2^{k}})^2$ in $\alpha _{n+1}$ in an obvious injective way. This mapping can easily be seen to be a quasi-isometry from $\alpha _n$ into $\alpha _{n+1}$ . We refer the reader to Figure 2.

Figure 2

The mapping from $(01^{2^{k+1}})$ -block in $\alpha _n$ into $(01^{2^{k}})(01^{2^{k}})$ -block in $\alpha _{n+1}$ .

Now we need to prove that there is no quasi-isometric mapping from $\alpha _{n+1}$ into  $\alpha _n$ . For the sake of contradiction assume that g is an $(A,B,C)$ -quasi-isometry from $\alpha _{n+1}$ into $\alpha _n$ . Then using Lemma 2.3 and Lemma 2.1, one sees that g needs to be strictly monotone on all but finitely many positions of $\alpha _{n+1}$ with color $0$ ; that is, we need to have $M \in \omega $ such that for all $m,m^{\prime }>M$ and $m>m^{\prime }$ we have if $\alpha _{n+1}(m) = \alpha _{n+1}(m^{\prime }) = 0$ then $g(m)> g(m^{\prime })$ .

We now show that we have a contradiction. Let $m_{i,n}$ and $m_{j, n+1}$ be the positions of the ith $0$ in $\alpha _n$ and jth $0$ in $\alpha _{n+1}$ , respectively. Now assume that $m_{i,n+1}> M$ and $g(m_{i,n+1}) = m_{j,n}$ . Then from monotonicity and injectivity of g on all positions colored $0$ in $\alpha _{n+1}$ , we should have

$$ \begin{align*}d_{\alpha_n} (g(m_{i,n+1}),g(m_{i+k,n+1})) \geqslant m_{j+k,n} - m_{j,n}. \end{align*} $$

Together with the $(A,B,C)$ -quasi-isometry condition, this implies $m_{j+k,n} - m_{j,n} \leqslant A(m_{i+k,n+1} - m_{i,n+1}) + B$ and hence

$$ \begin{align*} r(k) = \frac{m_{j+k,n} - m_{j,n}}{m_{i+k,n+1} - m_{i,n+1}} \leqslant A + \frac{B}{m_{i+1,n+1} - m_{i,n+1}} \quad (k \geqslant 1), \end{align*} $$

which in particular says the value $r(k)$ is uniformly bounded with respect to k. On the other hand, from the construction of $\alpha _n$ and $\alpha _{n+1}$ one can observe that the growth rate of $m_{k,n}$ with respect to k is much faster than that of $m_{k,n+1}$ ; more precisely, one can verify that $m_{2^n \cdot k , n} = \mathcal O(2^k)$ holds for each $n \in \omega $ , and thus $m_{2^n \cdot k , n+1} = m_{2^{n+1} \cdot \frac {k}{2} , n+1} = \mathcal O(2^{\frac {k}{2}})$ holds when k is even. This implies $r(k)$ is unbounded, which is a contradiction.⊣

Proof As above we assume that $0,1\in \Sigma $ . Consider the following sequence of strings $\beta _n$ , $n\in \omega $ :

$$ \begin{align*} \beta_n = 010^{2^n}1^{2^n}0^{3^{n}}1^{3^{n}}...0^{k^{n}}1^{k^{n}}... \end{align*} $$

We claim that this sequence forms an antichain in $\Sigma _{QI}^{\omega }$ . Take any $n,m \in \omega $ and suppose $\beta _n \leqslant _{QI} \beta _m$ via an $(A,B,C)$ -quasi-isometry f. We will show that $n=m$ .

Let $A_{s,t}$ be the “tth block” of zeros in $\beta _{s}$ . We can represent $A_{s,t}$ as the interval

$$ \begin{align*} A_{s,t} = [2\sum_{i=0}^{t-1}i^{s},2\sum_{i=0}^{t-1}i^{s}+(t)^{s}-1]. \end{align*} $$

Since f is a quasi-isometry, an easy argument shows that there exists $k,l \in \omega $ such that (1) $\,f(A_{n,k}) \subseteq A_{m,l}$ , and (2) for every $k^{\prime } \in \omega $ , we have $\,f(A_{n,k^{\prime }+k}) \subseteq A_{m,k^{\prime }+l}$ . Intuitively, these say that from some point the quasi-isometry f maps $\beta _n$ in the “block by block” manner without vacancy—one can easily verify that, without this property f generates unbounded distortions (and thus is not a quasi-isometry). Now note that we have:

$$ \begin{align*}(1/A)|A_{n,k^{\prime}+k}|-B \leqslant |A_{m, k^{\prime}+l}| \leqslant A|A_{n,k^{\prime}+k}|+B. \end{align*} $$

Therefore, we should have a positive upper and lower bounds on the ratio

$$ \begin{align*} \frac{|A_{n,k^{\prime}+k}|}{|A_{m,k^{\prime}+l}|} = \frac{(k^{\prime}+k)^n}{(k^{\prime}+l)^m} \end{align*} $$

with respect to $k^{\prime }$ . The only case that satisfies this condition is $n=m$ .⊣

Proof Suppose that $\beta \leqslant _{QI} \alpha $ via an $(A,B,C)$ -quasi-isometry f. Our goal is to show that $\alpha \sim _{QI} \beta $ . It suffices to show that there exists a constant D such that for every sufficiently large $y \in \alpha $ (i.e., for every $y \geqslant Y$ with some fixed constant Y) there exists an $x \in \beta $ with $|y-f(x)| \leqslant D$ and $Cl(x) = Cl(y)$ . Indeed, assuming such a condition we can construct a quasi-isometry $g:\alpha \to \beta $ as follows; for each $y \in \alpha $ ,

1. 1. if there exists $y'\in \alpha $ such that $|y'-y|\leqslant D$ for which there is $x'\in \beta $ with $\,f(x')=y'$ , then let $g(y)=x'$ ;

2. 2. otherwise, let $x\in \beta $ be any position such that $Cl(x) = Cl(y)$ , and let $g(y) = x$ .

Here $g(y)$ is well-defined in case 2, as $\beta $ clearly contains both of $0$ and $1$ as its color. It is easy to verify that g is a quasi-isometry—recall the argument in Remark 1.5, and observe that the case 2 happens only for finitely many y’s.

Now we prove existence of the constant D. Enumerate all elements of the image of f as $\{y_n\}_{n\in \omega }$ , where $y_n < y_{n+1}$ for all n. Then by definition of $(A,B,C)$ -quasi-isometry, we have $y_{n+1} - y_n \leqslant 2C+1$ (as otherwise there is y between $y_n$ and $y_{n+1}$ that violates the density property). On the other hand, it is clear from the construction of $\alpha $ that every sufficiently large $y \in \alpha $ is a member of a single-colored interval I in $\alpha $ with the size greater than $2C+1$ . Thus for such a y, one can find $x \in \beta $ such that $|y-f(x)| \leqslant 2C+1$ and $Cl(x) = Cl(y)$ .⊣

Proof Let $\,f:\alpha \to \beta $ be an $(A,B, C)$ -quasi-isometry. The constant C tells us that there is $n_0 \in \omega $ such that $\,f(n_0) \in [0,C]$ . Thus, by the Small Cross Over Lemma there is a bound D (which is independent of the choice of f) such that $\,f(0) \leqslant D$ . Since f is an $(A,B, C)$ -quasi-isometry, we have

$$ \begin{align*} f(n)\leqslant An+B+f(0) \leqslant An+(B+D). \end{align*} $$

So, we let $D'=B+D$ .⊣

Proof Let $\,f:\alpha \to \beta $ be an $(A,B,C)$ -quasi-isometry and let $\,f_n = f\hspace {-.4em}\upharpoonright _n$ . We show that $\,f_n$ satisfies the last condition of possibly-extendable function (i.e., the condition 3 in Definition 3.6); Conditions 1 and 2 of Definition 3.6 clearly hold. Assume the contrary, letting $y < M_n - (C-D)$ be an element such that no $x \in \{0,\ldots , n\}$ satisfies $\,f_n(x) \in \{y-C,\ldots , y+C\}$ . As f is an $(A,B,C)$ -quasi-isometry, there should be an $x'> n $ that satisfies $\,f(x') \in \{y-C,\ldots , y+C\}$ . But then, for $x'' \in f_n^{-1}(M_n)$ , we have $\,f(x') - f(x'') \leqslant (y+C) - M_n < D$ . This contradicts the Small Cross Over Lemma.

If $x_1, x_2, \ldots $ is an infinite path through the tree $T(\alpha , \beta , A,B)$ then the mapping f defined as the limit of the sequence $\,f_{x_1}, f_{x_2}, \ldots $ is an $(A,B, C)$ -quasi-isometry from $\alpha $ to $\beta $ .⊣

Proof If $\alpha \leqslant _{QI}\beta $ via $\,f:\alpha \to \beta $ , then take $n'\geqslant n$ such that for any $i\geqslant n'$ we have $\,f(i) \geqslant m$ . Define $\,f':\alpha '\to \beta '$ as follows. For all $j\leqslant n'$ , make $\,f'$ color preserving. For all $i> n$ set $\,f'(i)=f(i)$ . This is a quasi-isometry. The converse can be shown in a similar way.⊣

Proof Note that the assumption of the theorem (that letters that occur in $\alpha $ or $\beta $ must occur in both of these strings infinitely often) is important. For instance, no $\gamma $ exists such that $0^\omega <_{QI} \gamma <_{QI} 10^\omega $ .

Let $\alpha <_{QI} \beta $ via f. We can assume (if necessary, by taking $QI$ -equivalent strings $\alpha '\sim _{QI} \alpha $ and $\beta '\sim _{QI} \beta $ ) that f is injective and monotonic. The reader can verify this (or the reader can refer to Theorem 4.11). So, $\beta $ is of the form

$$ \begin{align*}\beta = \alpha(0) w_0 \alpha(1) w_1 \ldots, \end{align*} $$

where the length of finite strings $w_k$ are all uniformly bounded by a constant. By $p(n)$ we denote the position of $\alpha (n)$ in $\beta $ , that is, $p(n) = n+\sum _{i=0}^{n-1} |w_i|$ .

An informal idea of constructing $\gamma $ is the following. Initially $\gamma $ starts copying $\alpha $ until an initial segment of $\alpha $ such that no mapping from $\beta $ can possibly be extended to a $(1,1,1)$ -quasi-isometry into $\gamma $ built. From that point on, $\gamma $ switches to $\beta $ and copies $\beta $ until an initial segment of $\gamma $ is built such that no mapping from $\gamma $ can possibly be extended to a $(2,2,2)$ -quasi-isometry into $\alpha $ built. Then $\gamma $ switches to $\alpha $ and continues on copying $\alpha $ . Below is a formal description.

In what follows we inductively define the sequence $\gamma _k$ of infinite strings, where $k\in \omega $ . The strings $\gamma _k$ will always be of the form $\gamma _k = \alpha (0) u_0^{(k)} \alpha (1) u_1^{(k)} \ldots $ , where for each i and k, the string $u_i^{(k)}$ is either $w_i$ or an empty string.

Let $p_k(n)$ be the position of $\alpha (n)$ in the string $\gamma _k$ , that is, $p_k(n) = n+\sum _{i=0}^{n-1} |w_i^{(k)}|$ . Call a string $\delta $ an extension of a finite string w if it has w as its prefix (i.e., $\delta = w\delta '$ for some $\delta '$ ). Now we define the sequence $\{\gamma _k\}_{k\in \omega }$ as follows:

• • Set $\gamma _0 :=\alpha $ .

• • For given $k \geqslant 1$ we proceed as follows.

  • – Assume $k-1$ is even. Find $n_k \in \omega $ such that no mapping $\,f: \beta \hspace {-.4em}\upharpoonright _{n_k} \to \gamma _{k-1}$ exists that can possibly be extendable to $(k,k,k)$ -quasi-isometry. Such $n_k$ exists because $\beta \not \leqslant _{QI}\gamma _{k-1}$ (by inductive hypothesis). Take a sufficiently large s, say $s = kn_k + D_k$ , where $D_k$ is a constant in Lemma 3.5 for $(k,k,k)$ -quasi-isometry constant, and set

    $$ \begin{align*}\gamma_k = \gamma_{k-1}\hspace{-.4em}\upharpoonright_s\beta(s+1)\beta(s+2)\ldots. \end{align*} $$
    Note that any map from $\beta \hspace {-.4em}\upharpoonright _{n_k}$ to any extension of $\gamma _{k-1}\hspace {-.4em}\upharpoonright _s$ is not possibly extendable to a $(k,k,k)$ -quasi-isometry. Note that, by Lemma 3.9, we also have $\gamma _k \not \leqslant _{QI}\alpha $ .

  • – Assume that $k-1$ is odd. Find $n_k \in \text {range} (p_{k-1})$ such that no map $\,f: \gamma _{k-1} \hspace {-.4em}\upharpoonright _{n_k} \to \alpha $ is possibly extendable to $(k,k,k)$ -quasi-isometry; this is possible because $\gamma _{k-1} \not \leqslant _{QI}\alpha $ . Let $s = p_{k-1}^{-1}(n_k)$ (thus we have $\gamma _{k-1} \hspace {-.4em}\upharpoonright _{n_k} = \alpha (0) u_0^{(k-1)} \alpha (1) u_1^{(k-1)} \ldots \alpha (s)$ ), and just as above, set

    $$ \begin{align*} \gamma_k = \gamma_{k-1} \hspace{-.4em}\upharpoonright_{n_k} \alpha (s+1)\alpha (s+2) \ldots. \end{align*} $$
    Note that, by Lemma 3.9, we have $\beta \not \leqslant _{QI}\gamma _k$ .

Let $\gamma = \lim _{k\to \infty } \gamma _k$ . Now we show that $\gamma \not \leqslant _{QI} \alpha $ . Assume that $\gamma \leqslant _{QI} \alpha $ via a quasi-isometry. Select the smallest even k such that $\gamma \leqslant _{QI} \alpha $ via a $(k,k,k)$ -quasi-isometry g. Consider the construction of $\gamma _k$ . The string $\gamma _k$ has the prefix $\gamma _{k-1} \hspace {-.4em}\upharpoonright _{n_k}$ such that no map $\,f: \gamma _{k-1} \hspace {-.4em}\upharpoonright _{n_k} \to \alpha $ is possibly extendable to $(k,k,k)$ -quasi-isometry. By construction, $\gamma _{k-1} \hspace {-.4em}\upharpoonright _{n_k}$ is a prefix of $\gamma $ , that is, $\gamma \hspace {-.4em}\upharpoonright _{n_k}= \gamma _{k-1} \hspace {-.4em}\upharpoonright _{n_k}$ . Hence, g restricted to $ \gamma _{k-1} \hspace {-.4em}\upharpoonright _{n_k}$ is possibly extendable to a $(k,k,k)$ -quasi-isometry. Contradiction. Similarly, one can show that $\gamma \not \geqslant _{QI} \beta $ . Finally note that $\gamma $ is of the form $\alpha (0) u_0 \alpha (1) u_1 \ldots $ , where $u_i$ is either $w_i$ or an empty string for each i. This implies that $\alpha \leqslant _{QI} \gamma \leqslant _{QI} \beta $ .⊣

Proof Assume we have constructed $\gamma ^{(0)},\ldots ,\gamma ^{(n)}$ such that $\alpha <_{QI} \gamma ^{(i)} <_{QI} \beta $ for each $i\leqslant n$ . Then construct $\gamma ^{(n+1)}$ via the same construction of $\gamma $ in the proof of Theorem 3.10, but $n_k$ is a number such that

1. 1. no map $\,f: \beta \hspace {-.4em}\upharpoonright _{n_k} \to \gamma _{k-1}$ or $\,f: \gamma ^{(i)} \hspace {-.4em}\upharpoonright _{n_k} \to \gamma _{k-1} (i\leqslant n)$ is possibly extendable to $(k,k,k)$ -quasi-isometry; and

2. 2. if $k-1$ is odd, then the finite string $\beta (n_{k-1}+1)\ldots \beta (n_k)$ contains every color in $Cl(\beta )$ .

Notice that the condition 2 is imposed to assure that any color in $\gamma ^{(n)}$ occurs in it infinitely often. This property of $\gamma ^{(n)}$ is required to apply Lemma 3.9 when we compare $\gamma _k$ and $\gamma ^{(n)}$ in the construction of $\gamma ^{(m)}$ , $m>n$ .⊣

Proof We prove that $\mathcal F(0)$ is a filter. Let $\alpha \in \mathcal F(0)$ and $\alpha \leqslant _{QI} \beta $ through an $(A, B, C)$ -quasi-isometry f. We need to show that $\beta \in \mathcal F(0)$ . Assume, for the sake of contradiction, that the lengths of $0$ -blocks in $\beta $ are unbounded. Let B be the length of the largest $0$ -block in $\alpha $ . Now, take a $0$ -block $\beta (i)\ldots \beta (i+n_0)$ in $\beta $ , where $n_0$ is sufficiently large. We give bound on the value of $n_0$ below. Since f is a quasi-isometry, there exists a $\beta (i_0)$ that belongs to the block $\beta (i)\ldots \beta (i+n_0)$ such that $\beta (i_0)$ has a preimage $\alpha (j_0)$ and $\beta (i_0)$ is within distance C from the center of the $0$ -block $\beta (i)\ldots \beta (i+n_0)$ . The length of the block in $\alpha $ that contains $\alpha (j_0)$ is bounded by B. We conclude that the string

$$ \begin{align*}\alpha(j_0-B-1)\ldots \alpha(j_0)\ldots \alpha(j_0+B+1) \end{align*} $$

must contain $1$ . The length of this string is $2B+2$ . There exists a constant D such that f-image of all intervals of length $2B+2$ is contained in the intervals in $\beta $ of length at most D. So, if $n_0=2D$ then the f-image of the interval

$$ \begin{align*}\alpha(j_0-B-1)\ldots \alpha(j_0)\ldots \alpha(j_0+B+1) \end{align*} $$

must be inside of $\beta (i)\ldots \beta (i+n_0)$ . This implies that the original $0$ -block $\beta (i)\ldots \beta {(i+n_0)}$ contains $1$ since f preserves colors. It must be the case that $n_0\leqslant 2D$ . Hence, $\beta \in \mathcal F(0)$ . Finally, it is clear that $[1^{\omega }]$ is the least element in $\mathcal F(0)$ . Hence, $\mathcal F(0)$ is a principal filter. The same proof shows that the set $\mathcal F(1)$ is a principal filter.⊣

Proof Let $\alpha \in \mathcal I(u)$ and $\beta \leqslant _{QI} \alpha $ . If there is a universal bound on the lengths of all $0$ -blocks in $\beta $ then from the theorem above we would have a universal bound on the lengths of $0$ -blocks in $\alpha $ . This is a contradiction. Similarly, there could not be a universal bound on the lengths of $1$ -blocks in $\beta $ .⊣

Proof Assume that $\alpha =0^{n_0}1^{m_0} 0^{n_1}1^{m_1}\ldots $ and there is a constant B such that $1\leqslant n_i, m_i\leqslant B$ for all i. Consider a mapping $\,f: (01)^\omega \to \alpha $ that maps the ith occurrence of $0$ and $1$ in $(01)^\omega $ to any position of the blocks $0^{n_i}$ and $1^{m_i}$ in $\alpha $ , respectively. Then f witnesses $(01)^\omega \leqslant _{QI} \alpha $ . Also the string $(01)^\omega $ is the greatest element of $\{0,1\}_{QI}^{\omega }$ , as shown in the proof of Proposition 1.6. Thus we have $\alpha \leqslant _{QI} (01)^\omega $ .⊣

Proof The chain constructed in Theorem 3.1 is in $\mathcal F(0)$ . Hence, both $\mathcal F(0)$ and $\mathcal F(1)$ have countable chains. Let $\beta _n$ , $n \in \omega $ , be the sequence from the proof of Theorem 3.2:

$$ \begin{align*}\beta_n = 010^{2^n}1^{2^n}0^{3^{n}}1^{3^{n}}...0^{k^{n}}1^{k^{n}} \ldots. \end{align*} $$

Using this sequence, construct the following new sequence $\{\beta _n \oplus 1^\omega \}_{n \in \omega }$ . Each string $\beta _n \oplus 1^\omega $ belongs to the filter $\mathcal F(0)$ . In the same manner as in the proof of Theorem 3.2 one can show that $\{\beta _n \oplus 1^\omega \}_{n \in \omega } \subset \mathcal {F}(1)$ is an antichain. Similarly $\{\beta _n \oplus 0^\omega \}_{n \in \omega } \subset \mathcal {F}(0)$ is an antichain.⊣

Proof The minimal elements constructed in Theorem 3.3 are clearly in the ideal $\mathcal I(u)$ . For the second part we adapt the proof of the Density Theorem. Assume that $\alpha $ is a maximal element. We can represent $\alpha $ as follows:

$$ \begin{align*}\alpha=0^{n_0} u_0 1^{n_1} u_1 0^{n_2} u_2 1^{n_3} u_3 0^{n_4} u_4 1^{n_4}\ldots, \end{align*} $$

where $n_0< n_1< n_2< \dotsb $ . Note that $\alpha <_{QI} (01)^{\omega }$ . If we apply the proof of the Density Theorem directly, then we might produce $\gamma $ such that $\alpha <_{QI} \gamma <_{QI} (01)^{\omega }$ with $\gamma \not \in \mathcal I(u)$ . To guarantee that $\gamma \in \mathcal I(u)$ we need to slightly change the proof of the Density Theorem. Namely, every time when $\gamma $ copies a part of $\alpha $ , it should include a $0$ -block and also a $1$ -block whose lengths are greater that the lengths of all $0$ -blocks and $1$ -blocks in $\gamma $ that has been built so far. It is clear that this condition can be satisfied. This puts $\gamma $ into the ideal $\mathcal I (u)$ .⊣

Proof If $\alpha \leqslant _{QI} \beta $ then it is easy to select finite strings $x,y, u, v$ that satisfy the statement of the theorem.

Assume that there are $x,y, u, v \in \Sigma ^{\star }$ such that $\alpha =xu^{\omega }$ , $\beta =yv^{\omega }$ , $Cl(x)\subseteq Cl(y)$ and $Cl(u) \subseteq Cl(v)$ . Construct a quasi-isometry f from $\alpha $ to $\beta $ as follows. First, map the prefix x into the prefix y so that colors are preserved. Secondly, we consider the set $X=\{x_1,\ldots , x_k\}$ of all distinct colors that appear in u. Now map every $x_i$ -colored position in the kth copy of u in the string $\alpha $ into an $x_i$ colored position in the kth copy of v in the string $\beta $ . Set $A=\max \{|x|, |y|, |u|, |v|\}$ and $A=B=C$ . It is clear that f preserves colors and the quasi-isometry inequality between the distances $d(x,y)$ and $d(f(x), f(y))$ with quasi-isometry constants $A, B, C$ as required.⊣

Proof Let $A=\{a_1,\ldots , a_k\}$ and $B=\{b_1, \ldots , b_n\}$ be elements of $\mathcal X(\Sigma )$ . Associate with the pair $(A,B)$ the infinite string $a_1\ldots a_k (b_1\ldots b_n)^{\omega }$ . This establishes the mapping from $\mathcal X \times \mathcal X$ into $\mathcal E_P$ . By Theorem 3.20 this is an isomorphism from $\mathcal X \times \mathcal X$ onto $\mathcal E_P$ . The second part is proved similarly.⊣

Proof Let $\alpha =xuuu\ldots $ and $ \beta =yvvv\ldots $ . Assume that $Cl(x)\subseteq Cl(y)$ and $Cl(u) \subseteq Cl(v)$ . Our desired mapping $\,f_{\alpha }$ maps x into y by preserving colors. This is where $\,f_{\alpha }$ need not be order preserving embedding. So, it suffices to construct a computable quasi-isometric embedding from $\alpha _1=u^{\omega }$ to $\beta _1=v^{\omega }$ . Let $X=\{x_1,\ldots , x_k\}$ be the set of all colors that appear in u, and hence in v. Let $a_i$ be the number of times that color $x_i$ appears in u. Clearly $a_i\geqslant 1$ . Consider the new string $v_1$ obtained by writing v exactly $a_1+\ldots +a_n$ times, that is, $v_1=(v)^{a_1+a_2+\ldots + a_n}$ . now it is easy to see that there exists an embedding $\,f'$ from u into $v_1$ that preserves colors and the order. We now easily propagate this mapping $\,f'$ to a color preserving embedding $\,f_{\alpha }$ from $\alpha _1$ into  $\beta _1$ . The map $\,f_{\alpha }:\alpha \rightarrow \beta $ thus built is a desired quasi-isometry.⊣

Proof We define $\gamma $ using $\beta $ and the quasi-isometry f. For each position i in string $\beta $ consider $\,f^{-1}(i)$ . If $\,f^{-1}(i)=\emptyset $ then replace i with the position $(i, \emptyset )$ and color this position with $\beta (i)$ . Otherwise, let $j_{i,1}< \cdots < j_{i,k}$ be all f-preimages of i in the string $\alpha $ listed in their natural order. Replace the position i in $\beta $ with positions

$$ \begin{align*}(i,1)< (i,2)<\cdots < (i,k), \end{align*} $$

and color positions in this interval by color $\beta (i)$ . Thus, we have defined the new string $\gamma $ . Let us map elements $(i,1)$ , $(i,2)$ , $\ldots $ , $(i,k)$ in $\gamma $ into the position i of $\beta $ . If i has no f-preimage then map $(i,\emptyset )$ on i. This determines the function $\,f_2$ stated in the lemma. Clearly, $\,f_2$ is a surjective quasi-isometry. The function $\,f_1$ is obtained from f as follows. For every $i\in \beta $ if $\,f^{-1}(i)\neq \emptyset $ , then map elements $j_{i,1}, \ldots , j_{i, k}$ on the elements $(i,1)$ , $(i,2)$ , $\ldots $ , $(i,k)$ , respectively. The mapping is an injective quasi-isometry from $\alpha $ into $\gamma $ . Finally, it is also easy to see that $\beta \leqslant _{QI} \gamma $ through the map $i\rightarrow (i, \emptyset )$ if $\,f^{-1}(i)=\emptyset $ , and $i\rightarrow (i,1)$ if $\,f^{-1}(i)\neq \emptyset $ .⊣

Proof Let $\gamma $ be a string that is obtained by eliminating each position of $\beta $ that is not in the image of f, and construct $\,f_1$ and $\,f_2$ in an obvious way. It is clear that $\beta \leqslant _{QI} \gamma $ .⊣

Proof let us list all pairs $(a_0, b_0), (a_1, b_1), \ldots $ that constitute maximal crossings via f, that is, $a_i<b_i$ and $\,f(a_i) -f(b_i) = D_f$ . We list these pairs in the way that $b_i < a_{i+1}$ holds for each i, which is possible as we prove below. Without loss of generality let $a_i \leqslant a_{i+1}$ for each i. First we have $a_i \neq a_j$ for every $i \neq j$ , as otherwise we have $\,f(b_i) = f(b_j) = f(a_i) - D_f$ , which contradicts injectivity of f; in a similar way we can show $b_i \neq b_j$ for every $i \neq j$ . Next we have $\,f(a_i) < f(a_j)$ for each $i < j$ , as otherwise $\,f(a_i) - f(b_j)> f(a_j) - f(b_j) = D_f$ while $a_i < a_j < b_j$ , which contradicts the fact that $D_f$ is the cross-over constant of f; in a similar way we can show $\,f(b_i) < f(b_j)$ for each $i < j$ . Lastly we have $b_i < a_{i+1}$ for every i, as otherwise we have $\,f(a_{i+1})- f(b_i)> f(a_i)- f(b_i) = D_f$ while $a_{i+1} < b_i$ , again which contradicts the fact that $D_f$ is the cross-over constant of f.

Now we construct $\,f_1$ by “undoing” each maximal crossing in f. It is done by a function g that swaps the positions $\,f(a_i)$ and $\,f(b_i)$ in $\gamma $ for each i. Formally, we define g as the following function:

$$ \begin{align*} g(a) = \left\{ \begin{array}{lll} f(b_i) & \text{if }a = f(a_i), \\ f(a_i) & \text{if }a = f(b_i), \\ a & \text{otherwise.} \end{array} \right. \end{align*} $$

Notice that g satisfies all conditions of atomic crossing maps except that the sequence that defines g, namely $(f(b_0), f(a_0)),(f(b_1), f(a_1)),\ldots \hspace {-.04em},$ may not satisfy $\,f(a_i) < f(b_{i+1})$ for some i. In what follows we decompose g into a finite composition of atomic crossing maps.

If the sequence $(f(a_0), f(b_0)),(f(a_1), f(b_1)),\ldots $ is finite, then an aforementioned decomposition of g is clearly possible. If it is infinite, then for each $k = 0,1, \ldots , D_f -1$ define a sequence $(a_0^{(k)}, b_0^{(k)}), (a_1^{(k)}, b_1^{(k)}), \ldots $ by

$$ \begin{align*} (a_i^{(k)}, b_i^{(k)}) = (f(b_{i D_f +k}),f(a_{i D_f +k})). \end{align*} $$

As we have $\,f(b_{i+1})> f(b_i)$ for each i, we have $a_{i+1}^{(k)} \geqslant a_i^{(k)}+D_f = b_i^{(k)}$ ; we also have $a_{i+1}^{(k)} \neq b_i^{(k)}$ because f is injective. Thus we have $a_{i+1}^{(k)}> b_i^{(k)}$ for each i, and the sequence $(a_0^{(k)}, b_0^{(k)}), (a_1^{(k)}, b_1^{(k)}), \ldots $ defines an atomic crossing map, say $g_k$ . Clearly, we have $g = g_{D_f-1} \circ \cdots \circ g_0$ .

Now let $\gamma _1$ be a string that is obtained by swapping each color of $\gamma $ at the positions $\,f(a_i)$ and $f(b_i)$ , and let $f_1 {{\kern-2.3pt}={\kern-2.3pt}} g {{\kern-2.3pt}\circ{\kern-2.3pt}} f$ and $f_2 {{\kern-2.3pt}={\kern-2.3pt}} g^{-1} {{\kern-2.3pt}={\kern-2.3pt}} g$ . Below we prove $D_{f_1} {{\kern-2.3pt}<{\kern-2.3pt}} D_f$ holds; all other desired properties of $f_1, f_2$ and $\gamma _1$ are easy to derive from their construction.

Below we prove $\,f_1(a) -f_1(b) < D_f$ for each pair $(a,b)$ of positions such that $a<b$ . The inequality holds if $(a,b) = (a_i,b_i)$ for some i, as every maximal crossing in f is undone by g. Otherwise we have $\,f(a) -f(b) < D_f$ , so it suffices to show $\,f_1(a) -f_1(b) < D_f$ for each $(a,b)$ such that $a<b$ and $\,f_1(a) -f_1(b)> f(a) -f(b)$ . Notice that we have $\,f_1(a) = f(b_i) < f(a)$ if $a = a_i$ , $\,f_1(a) = f(a_i)> f(a)$ if $a = b_i$ , or $\,f_1(a) = f(a)$ otherwise. From this observation, it suffices to verify the cases in which $b = a_j$ holds for some j, or $a = b_i$ holds for some i. We verify the former case as follows; the latter can be checked in a similar way.

• • If $a {{\kern-2.3pt}={\kern-2.3pt}} a_i$ for some i, then we have $i{{\kern-2.3pt}<{\kern-2.3pt}}j$ and hence $f_1(a) {{\kern-2.3pt}-{\kern-2.3pt}} f_1(b) {{\kern-2.3pt}={\kern-2.3pt}} f(b_i) {{\kern-2.3pt}-{\kern-2.3pt}} f(b_j) {{\kern-2.3pt}<{\kern-2.3pt}}0$ .

• • If $a {{\kern-2pt}={\kern-2pt}} b_i$ for some i, then $f_1(a) {{\kern-2pt}-{\kern-2pt}} f_1(b) {{\kern-2pt}={\kern-2pt}} f(a_i) {{\kern-2pt}-{\kern-2pt}} f(b_j) {{\kern-2pt}<{\kern-2pt}} f(a_i) {{\kern-2pt}-{\kern-2pt}} f(b_i) {{\kern-2pt}={\kern-2pt}} D_f$ .

• • Otherwise, we have $\,f_1(a) -f_1(b) = f(a) - f(b_j)$ . Notice that $a<b = a_j<b_j$ , and hence $\,f(a) - f(b_j) \leqslant D_f$ holds; we also have $\,f(a) - f(b_j) \neq D_f$ , as the equality holds only if $(a,b_j) = (a_i,b_i)$ for some i. Thus we have $\,f_1(a) -f_1(b) < D_f$ .⊣

Proof Use a construction similar to the one from the proof of Lemma 4.6, but swapping colors of $\alpha $ rather than $\gamma $ .⊣

Proof First, compute an upper bound $\hat D_f$ of the cross-over constant $D_f$ . It can be computed from the quasi-isometry constants $(A,B, C)$ via Lemma 2.1. Then let $\gamma = \gamma _{\hat D_f}$ , $\,f = f_{\hat D_f}$ , and for each $k = \hat D_f, \ldots , 1$ , decompose $\,f_k$ into a sequence $\alpha \xrightarrow {f_{k-1}} \gamma _{k-1} \xrightarrow {g_{k-1}} \gamma _k$ as in the proof of Lemma 4.6 that is modified in the following way: at the beginning of the procedure, we list all pairs $(a_0, b_0), (a_1, b_1), \ldots $ such that $a_i < b_i$ and $\,f(a_i) - f(b_i) = k$ rather than $\,f(a_i) - f(b_i) = D_f$ . As $k \geqslant D_{f_k}$ holds for each k, the resulting list is either empty, or the same as the one via the original procedure. Notice that in the former case the modified procedure returns $\gamma _{k-1} = \gamma _k$ , $\,f_{k-1} = f_k$ and $g_{k-1} = \mathrm {id}$ . Through this we obtain the sequence $\alpha \xrightarrow {f_{0}} \gamma _{0} \xrightarrow {g} \gamma $ , where $g = g_{\hat D_f-1} \circ \cdots \circ g_0$ ; this is a decomposition with the desired properties.⊣

Proof The case $1$ and $2$ are derived from Corollary 4.2, 4.8 and 4.7. To show the case $3$ , first apply Lemma 4.3 and then Corollary 4.2 to the surjection; notice, from the construction, that Lemma 4.1 decomposes a surjection into a bijection and a monotonic surjection.⊣

Proof Recall that the second decomposition in Theorem 4.11 is derived from Corollary 4.2 and 4.8. As a property given from these corollaries, we have $\gamma _1 \sim _{QI} \gamma _2$ and $\gamma _2 \sim _{QI}\beta $ . Now let $\beta ' = \gamma _1$ .⊣

Proof Let $\beta = v_1v_2\ldots $ and $\gamma = w_1w_2\ldots $ be witnessing partitions for $\beta \leqslant _{CR} \gamma $ . We initially partition $\alpha $ in the following way:

$$ \begin{align*}\alpha = u_1u_2\ldots, \end{align*} $$

where $|u_n| = |v_n|$ for all n. In what follows we show that if we merge some $u_n$ ’s and $v_n$ ’s in a careful way, then we obtain witnessing partitions of $\alpha $ and $\beta $ . From these partitions we can then derive witnessing partitions of $\alpha $ and $\gamma $ .

Let $(a_1, b_1), (a_2, b_2), \ldots $ be the sequence of crossing pairs that define the quasi-isometric atomic crossing map $\,f: \alpha \rightarrow \beta $ . We can assume that no interval $u_i$ contains one of these crossing pairs. Indeed, if $u_i$ contains a crossing pair $(a, b)$ then we can simply change $\alpha $ by interchanging colors at positions a and b. Similarly, if $(a,b)$ is a crossing pair and $\alpha (a)=\alpha (b)$ we can change the map f be sending a to a and b to b. The output of the process described is a new atomic crossing map $\,f':\alpha ' \to \beta $ , where $\alpha ' \sim _{QI} \alpha $ is obtained from $\alpha $ by switching colors, and $\,f'$ is obtained from f by switching images in every crossing pair $(a,b)$ that belongs to some $u_i$ .

Assume that $(a,b)$ is a crossing pair such that $a\in u_i$ and $b\in u_{i+j}$ . In this case we say that $u_i$ contains the left-end of the crossing pair $(a,b)$ and $u_{i+j}$ contains the right-end of the crossing pair. If $j>1$ , we can replace $u_i$ with the segment $u_i u_{i+1}\ldots u_{i+j-1}$ and $v_i$ with $v_iv_{i+1}\ldots v_{i+j-1}$ . This changes the partition of $\alpha $ and $\beta $ but does not change the quasi-isometry map f. Also, the sizes of the new partitioning intervals are uniformly bounded. Thus, we can always assume that the partition $\alpha =u_1 u_2u_2\ldots $ is such that $|u_i|=|v_i|$ for all i, all crossing pairs occur between neighboring intervals only, and $\alpha (a)\neq \alpha (b)$ for all crossing pairs $(a,b)$ .

Starting from $n=1$ , we incrementally check if we should merge $u_n$ and $u_{n+1}$ (and thus $v_n$ and $v_{n+1}$ ). To assure that they can be kept separated, we need to check the following conditions. Note that the second condition below is indispensable. Figure 3 illustrates a situation in which the lack of the condition causes a problem.

1. 1. Let $m<n$ be the largest number that is declared as a separated partition (i.e., $u_m$ and $u_{m+1}$ are kept separated and $u_{m+1}\ldots u_{n}$ are all merged). Then $Cl(u_{m+1}\ldots u_{n}) \subseteq Cl(v_{m+1}\ldots v_{n})$ .

2. 2. If a crossing pair $(a_k, b_k)$ belongs to $u_n u_{n+1}$ , then $Cl(b_k)$ appears in $v_{n+1+i}$ for some sufficiently small i.

Figure 3

With the condition 1 only, we may have a problem.

This idea is realized as the following procedure which generates a merging policy $\varphi :\omega \to \{0,1\}$ : here, $\varphi $ indicates that $u_n$ and $u_{n+1}$ should be merged for each $n \in \varphi ^{-1}(0)$ , and should be kept separated for each $n \in \varphi ^{-1}(1)$ . For instance, $\varphi (n)=0$ , $\varphi (n+1)=0$ and $\varphi (n+2)=1$ means that $u_n, u_{n+1}, u_{n+2}$ are merged and $u_{n+2}$ is the last interval merged with $u_n$ .

1. 1. Set $n=1$ , $i=0$ , and let $\varphi :\omega \to \{0,1\}$ be a currently undefined function. Here n and i represent the following situation of the procedure: we have declared that $u_{n-1}$ and $u_n$ should be kept separated, and $u_n,\ldots \hspace {-.04em},u_{n+i}$ should be merged. Formally, through the procedure it always holds that $\varphi (n-1) = 1$ and $\varphi (n) = \ldots = \varphi (n+i-1) = 0$ , and $\varphi $ is defined over $\{1,\ldots \hspace {-.04em} n+i-1\}$ .

2. 2. If no crossing pair exists between $u_{n+j}$ and $u_{n+j+1}$ for some $j\in \{i, \ldots \hspace {-.04em}, i+|\Sigma | \}$ , then let $\varphi (k)=0$ for each k such that $n+i \leqslant k \leqslant n+j-1$ , $\varphi (n+j)=1$ , and $n=n+j+1$ , $i=0$ . In other words, we declare that $u_{n+i},\ldots \hspace {-.04em},u_{n+j}$ should be merged (together with $u_{n},\ldots \hspace {-.04em},u_{n+i-1}$ , which have been already declared to be merged) while $u_{n+j}$ and $u_{n+j+1}$ should be kept separated.

3. 3. Otherwise, we check if

   $$ \begin{align*}Cl(u_n \ldots u_{n+j}) \subseteq Cl(v_n \ldots v_{n+j}) \ \text{for all }j \in \{i, \ldots, i + |\Sigma|\} \ \ (\star). \end{align*} $$

4. 4. If $(\star )$ holds, then find a letter that occurs twice or more in positions $b_{k}, \ldots , b_{k+|\Sigma |}$ , where $b_k$ belongs to $u_{n+i+1}$ . Let $b_{k+\ell }$ be the earliest position among them, and set

   $$ \begin{align*}\varphi (n+i)=\ldots =\varphi (n+i+\ell-1)=0, \ \varphi(n+i+\ell)=1,\end{align*} $$
   and $n= n+i+\ell +1$ , $i=0$ .

5. 5. If $(\star )$ does not hold, then take (say, the largest) $j \in \{i, \ldots , i + |\Sigma |\}$ such that $Cl(u_n \ldots u_{n+j}) \not \subseteq Cl(v_n \ldots v_{n+j})$ , let $\varphi (n+i)=\ldots =\varphi (n+i+j)=0$ and let $i= j+1$ .

6. 6. Go to 2.