---
abstract: |
    A tiling of ${{\mathbb R}}^d$ is [*repulsive*]{} if no $r$-patch can repeat arbitrarily close to itself, relative to $r$. This is a characteristic property of aperiodic order, for a non repulsive tiling has arbitrarily large local periodic patterns.

    We consider an aperiodic, repetitive tiling $T$ of ${{\mathbb R}}^d$, with finite local complexity. From a spectral triple built on the discrete hull $\Xi$ of $T$, and its Connes distance, we derive two metrics ${d_{\text{\rm sup}}}$ and ${d_{\text{\rm inf}}}$ on $\Xi$. We show that $T$ is repulsive if and only if ${d_{\text{\rm sup}}}$ and ${d_{\text{\rm inf}}}$ are Lipschitz equivalent. This generalises previous works for subshifts by J. Kellendonk, D. Lenz, and the author.
author:
- |
    J. Savinien$^{1,2}$\
    [$^{1}$ UniversitŽ de Lorraine, Institut Elie Cartan de Lorraine, UMR 7502, Metz, F-57045, France.]{}\
    [$^{2}$ CNRS, Institut Elie Cartan de Lorraine, UMR 7502, Metz, F-57045, France.]{}
title: A metric characterisation of repulsive tilings
---

Introduction
============

In two recent articles in collaboration with J. Kellendonk and D. Lenz [@KS10; @KLS11], we used constructions of non commutative geometry [@Co94] to derive a new characterisation of aperiodically ordered $1d$-subshifts. We showed that a minimal and aperiodic subshift $X$ has bounded powers if and only if two metrics derived from the Connes distance of a spectral triple over $X$ are Lipschitz equivalent. An essential ingredient to obtain this result is the notion of [*privileged words*]{} [@KLS11]. In this paper, we generalise this formalism and this results to tilings of ${{\mathbb R}}^d$. The essential ingredient here is the notion of [*privileged patches*]{} of a tiling.

A $1d$-subshift has bounded powers if its language does not contain arbitrarily large powers, [*i.e.*]{} there is an integer $p$ such that $n$-fold repetitions $w^n=w\cdots w$ of a word $w$ cannot occur for $n>p$. Linearly recurrent subshifts, which are usually considered highly ordered, share this property [@LP03; @Dur00; @Dur03]. Loosely speaking, bounded powers means that no factor can repeat too close, or overlap too much, along a sequence in the subshift. Bounded powers is equivalent to the property that a complete first return $u'$ of a word $u$ must be longer than a uniform constant times the length of $u$: $|u'|> C |u|$. The corresponding notion for tilings is [*repulsiveness*]{}: no patch can repeat arbitrarily close to itself relative to its size, see equation . A non repulsive tiling has arbitrarily large local periodic patterns – the analogue of arbitrarily large powers. As for subshifts, linearly repetitive tilings are repulsive [@Pat98; @Len04].

The property of bounded (or unbounded) powers in a subshift is measured by privileged words. Privileged words are iterated complete first returns to letters of the alphabet. Privileged words were introduced in [@KLS11], and have recently encountered a lot of interest in the combinatorics of words [@Pelto13; @FPZ13; @Pelto; @FJS13]. For rich subshifts [@GJWZ09] privileged words coincide exactly with palindromes (see [@KLS11] Section 2.2 for further details).

We generalise this notion to tilings. We define privileged patches: a notion of iterated complete first returns to the prototiles, see Section \[sec-priv\]. For $1d$ subshifts, a privileged patch is a generalisation of a privileged word obtained with bilateral versions of complete first returns. Because of the geometry in ${{\mathbb R}}^d$, the combinatorics of patches is much more involved than that of words. We need a few technical lemmas to deal with this. But the crucial point is the generalisation of privileged words to the tilings setting. Once the right definition of privileged patch is at hand, our formalism for subshifts essentially goes through for tilings of ${{\mathbb R}}^d$. The spectral triple we used in [@KLS11] for subshift is build from the tree of privileged words of the subshift. The spectral triple we use here is the same one built on the tree of privileged patches of the tiling. This allows us to characterise repulsive tilings by Lipschitz equivalence of two metrics derived from the Connes distance of the spectral triple, in complete analogy with the case of subshifts treated in [@KLS11].

Our initial motivation in studying properties of aperiodically ordered subshifts and tilings, came from non commutative geometry (NCG) [@Co94]. Namely we were interested in the construction of non commutative Riemanian structures, [*i.e.*]{} spectral triples, over totally disconnected spaces defined by tilings and subshifts. As it turns out, and as in [@KLS11], the criterium for aperiodic order we derive here can be explained in a rather combinatorial way, without introducing the framework of NCG and giving the details of the construction of the spectral triple. So we follow this line in the paper: we give the criterium [*ad hoc*]{} to state and prove our result. And in the last section we describe briefly the underlying spectral triple.

The paper is organised as follows. In Section \[sec-basics\] we remind the reader of the basic definitions for tilings of ${{\mathbb R}}^d$, and the classical results we need. We introduce privileged patches in Section \[sec-priv\], and state some combinatorial properties, including technical lemmas which allows us to adapt our formalism for subshifts to tilings of ${{\mathbb R}}^d$. In Section \[sec-tree\] we explain the construction of the tree of privileged patches, from which we define the two Connes metrics. In Section \[sec-charact\] we state and prove our main result, namely that a tiling is repulsive if and only if the Connes metrics are Lipschitz equivalent. The construction of the spectral triple, from which the Connes metrics are derived, is given briefly in Section \[sec-ST\].

[**Aknowlegements.**]{} The author would like to thank J. Kellendonk and D. Lenz for useful discussions, and encouragements to publish this work.

Basic definitions {#sec-basics}
=================

A [*tile*]{} of ${{\mathbb R}}^d$ is a subset $t \subset {{\mathbb R}}^d$ which is homeomorphic to a closed ball. A [*tiling*]{} of ${{\mathbb R}}^d$, is a countable family of tiles, $T=\{ t_i\}_{i\in{{\mathbb N}}}$, which have pairwise disjoint interiors and whose union covers ${{\mathbb R}}^d$. Given a tiling $T$, we specify a [*marker*]{} [^1] in each of its tile $t$: a point $x(t)\in {{\mathbb R}}^d$ in its interior.

A [*translate*]{} of a family $F=\{ t_j\}_{j\in J}$ of tiles of $T$, is a family $F+a=\{t_j + a\}_{j\in J}$, for some $a\in{{\mathbb R}}^d$. Let $x$ be the marker of a tile of $T$, and $r>0$. We call an [*$r$-patch*]{}, or a [*patch*]{} of radius $r$, the finite family of tiles of $T-x$ all of whose markers lie inside the open ball $B(0,r)$. In addition, $r$ is maximal with respect to the family of tiles defining the patch. As a consequence, the only $0$-patch is the empty patch. The patches made of a single tile (containing the marker of a single tile), are called [*prototiles*]{}.

Consider an $r$-patch $p$ of $T$. Given a family $F=\{ t_j\}_{j\in J}$ of tiles of $T$, we say that [*$p$ occurs in $F$*]{}, if there is a translate of $p$ which is a subset of $F$: $p+a\subset F$ for some $a \in {{\mathbb R}}^d$. The translate $p+a$ is called an [*occurrence*]{} of $p$ in $F$. Given a subset $U$ of ${{\mathbb R}}^d$, we say that [*$p$ occurs in $U$*]{}, if there is an occurrence of $p$ in $T$, the union of all of whose tiles is a subset of $U$. We mean that a patch $p$ is marked at the origin: $x(p)=0$. And that an occurrence of $p$ in $T$, in a family of tiles $F$, or in a subset of ${{\mathbb R}}^d$, is some translated copy $p+a$ marked at $a$: $x(p+a)=a$.

We will consider tilings satisfying the following three properties.

\[def-hypT\] A tiling $T$ of ${{\mathbb R}}^d$ is called

(i) [*aperiodic*]{} if $T+a=T$ implies $a=0$;

(ii) [*repetitive*]{} if for any $r>0$, and any $r$-patch $p$ of $T$, there exists $R>0$ such that $p$ occurs in any ball of radius $R$;

(iii) [*FLC*]{}, or has [*Finite Local Complexity*]{}, if for any $r>0$ there are finitely many $r$-patches.

Let $T$ be a repetitive and FLC tiling of ${{\mathbb R}}^d$, and $p$ an $r$-patch of $T$. The [*Delone set of occurrences of $p$ in $T$*]{} is the set $L_p$ of markers of all occurrences of $p$ in $T$. This is a Delone set as the distance between nearest points of $L_p$ is uniformly bounded. We let ${r_{\text{\rm pack}}}(L_p)$ (resp. ${r_{\text{\rm cov}}}(L_p)$) be one half of that uniform minimal distance (resp. maximal distance). It is called the [*packing radius*]{} of $L_p$ (resp. [*covering radius*]{}): any ball of radius ${r_{\text{\rm pack}}}(L_p)$ (resp. ${r_{\text{\rm cov}}}(L_p)$) contains at most (resp. at least) one point of $L_p$. A tiling $T$ is said to be [*repulsive*]{} if $$\label{eq-rep}
 \ell = \inf \Bigl\{ \frac{{r_{\text{\rm pack}}}(L_p)}{r} \, : \, \text{\rm $p$ an $r$-patch of $T$}  \Bigr\} > 0.$$ Informally, $\ell>0$ means that patches cannot overlap too much. On the contrary, in a non-repulsive tiling, there are arbitrarily large $r$-patches with arbitrarily close occurrences relative to $r$. Such occurrences overlap over an arbitrarily large proportion of their tiles. This implies that a non-repulsive tiling has arbitrarily large local periodic patterns, see Figure \[fig-nrep\].

We now fix an aperiodic, repetitive, and FLC tiling $T$ of ${{\mathbb R}}^d$ and assume that there is a tile whose marker lies at the origin. We endow the family of all of its translates, $T+{{\mathbb R}}^d$, with the following topology. A base of open sets is given by the acceptance domains of patches: for $p$ an $r$-patch of $T$ $$[p] = \bigl\{ T'\in \ T+{{\mathbb R}}^d \, : \, p \ \text{\rm occurs at the origin in } T' \bigr\}$$ If $q$ is a patch contained in $p$, which we write $q\subseteq p$, then $[p]\subset [q]$. Hence two tilings are close for this topology, if they agree on a large patch around the origin. The [*discrete hull*]{} of a $T$ is the closure of its translates in this topology: $$\Xi = \overline{ \bigl\{ T + a \, :  \, a \in {{\mathbb R}}^d, \, T + a \, \text{\rm has a marker at the origin} \bigr\}}\,.$$ As a consequence of the hypothesis in Definition \[def-hypT\] the following classical results hold:

1.  $\Xi$ is a Cantor set (compact, totally disconnected, with no isolated point);

2.  the family of acceptance domains $[p]$ is a countable base of clopen sets[^2] for $\Xi$;

3.  any $T'\in \Xi$ satisfies the hypothesis of Definition \[def-hypT\], and the closure of $T'+{{\mathbb R}}^d$ is $\Xi$.

The discrete hull is metrizable. Any function $\delta: [0,+\infty) \rightarrow (0,1]$, which decreases and has limit $0$ at $+\infty$, defines a ultra-metric on $\Xi$ as follows: $$\label{eq-ultrametric}
d_\delta (T_1,T_2) = 
\inf \bigl\{ \delta(r) : \text{\rm there is an $r$-patch $p$ occurring in both $T_1$ and $T_2$ at the origin} \bigr\}.$$

Privileged patches {#sec-priv}
==================

Given an $r$-patch $p$, we say that an $r'$-patch $p'$ is [*derived*]{} from $p$ if

(i) $p$ is contained in $p'$;

(ii) $p$ occurs at least twice in $p'$;

(iii) for any ${\widetilde}{r}<r'$, and any ${\widetilde}{r}$-patch $q$ contained in $p'$, $p$ occurs at most once in $q$.

See Figure \[fig-derpatch\] for an illustration. Condition (ii) means that $p'$ contains $p$ as a subpatch (hence with marker at the origin), plus another translate $p+a$ for some $a\neq 0$. Conditions (ii) and (iii) mean that $p'$ is a minimal extension of $p$ containing two occurrences of $p$.

![A patch $p'$ derived from $p$.[]{data-label="fig-derpatch"}](derpatch-0.pdf)

We define [*privileged patches*]{} inductively, as follows:

1.  the empty patch is the only privileged patch of order $0$;

2.  the prototiles of $T$, are the privileged patches of order $1$;

3.  for $n>1$ a privileged patch of order $n$ is an $n$-th iterated derived patch from the empty patch.

For $1d$-subshifts, [*i.e.*]{} symbolic one-dimensional tilings, this is a two-sided version of [*privileged words*]{} introduced in [@KLS11].

Let us state some elementary properties of derived patches. The first two Lemmas are needed to build the tree of privileged patches in the next Section.

\[lem-der\] Let $q$ be a patch derived from some patch, then

(i) there exists a unique patch $p$ such that $p'=q$;

(ii) if $q$ is privileged, then there exists a unique privileged patch $p$ such that $p'=q$;

(iii) if $q$ is privileged, and $p$ is a privileged patch contained in $q$, then there exists $i\ge 0$ such that $q$ is an $i$-th iterated derived patch from $p$, which we write $p^{(i)}=q$.

\(i) Assume that $q=p'_1=p'_2$, for two distincts patches $p_i$ of radius $r_i$, $i=1,2$. We may assume $r_2<r_1$, but then $p_2 \subsetneq p_1$, and this implies $p'_2 \subsetneq p'_1$ a contradiction.

\(ii) If $q$ is privileged, by definition there exists a privileged patch $p$ such that $p'=q$, and by (i) $p$ is unique.

\(iii) We prove this by induction on the radius of $q$. Let $(r_n)_{{\mathbb N}}$ be the non-decreasing sequence of radii of privileged patches of $T$ (which exists by FLC). The property is obvious for privileged patches of radius $r_1$: $q$ is a prototile with smallest radius and is derived for the empty patch. Assume the property holds for all privileged patches of radii less than or equal to $r_{n}$, for some $n>1$. Consider a privileged patch $q$ of radius $r_{n+1}$, and a privileged patch $p\subseteq q$. The case $p=q=p^{(0)}$ is trivial, so assume $p\subsetneq q$. By (ii) there exists a unique privileged patch ${\widetilde}p\subsetneq q$ with ${\widetilde}p^{(1)}=q$. Case $p\subseteq{\widetilde}p$ : by induction ${\widetilde}p = p^{(j)}$ for some $j\ge 0$, and so $q=p^{(j+1)}$. Case ${\widetilde}p\subsetneq p$ : by induction there is a $j>0$ such that $p={\widetilde}p^{(j)} = q^{(j-1)}$, which implies $q\subseteq p$ a contradiction.

\[lem-rder\]

(i) Let $p$ be an $r$-patch, and $p'$ an $r'$-patch derived from $p$, then $$2 {r_{\text{\rm pack}}}( L_p)  + r \le r' \le 2 {r_{\text{\rm cov}}}( L_p)  + r.$$

(ii) Let $(p_n)_{n\ge1}$ be a sequence of $r_n$-patches, such that $p_{n+1}$ is derived from $p_n$ for all $n$. Then $ r_{n+1} \ge 2n \,{r_{\text{min}}}$, where ${r_{\text{min}}}$ is the radius of the smallest prototile. If in addition $T$ is repulsive, then $r_{n+1}\ge (2\ell + 1)^n {r_{\text{min}}}$.

The first claim follows at once from the definition. We use the first inequality in (i) inductively to get $$r_{n+1} \ge 2 {r_{\text{\rm pack}}}( L_{p_{n}}) + r_{n} \ge 2 \, {r_{\text{min}}}+ r_{n} \ge \cdots \ge 2n \, {r_{\text{min}}}.$$ If $T$ is repulsive, then ${r_{\text{\rm pack}}}( L_{p_{j}}) \ge \ell r_j$ for all $j$, see equation , so one gets $$r_{n+1} \ge 2 {r_{\text{\rm pack}}}( L_{p_{n}}) + r_{n} \ge (2 \ell +1 ) r_{n} \ge \cdots \ge (2\ell +1)^n {r_{\text{min}}}.$$

The following technical lemma is analogous to Lemma 3.8 in [@KLS11]. It states that if a tiling is not repulsive, then one can find arbitrary long sequences of derived privileged patches whose radii grow “slowly”.

\[lem-nrep\] If $T$ is not repulsive, then for all $m\in{{\mathbb N}}$, there exists privileged patches $p_0, p_1,\ldots p_m$, of radii $r_0, r_1, \ldots r_m$ respectively, such that

(i) $p_{j}=p_0^{(j)}$, for all $j=1, \ldots, m$,

(ii) $r_m \le 2 r_1$.

Consider a non repulsive tiling $T$, and fix an integer $m>1$. Since the infimum in equation  is zero, for any $0<\epsilon <1/(8m)$, there is an $r_q$-patch $q$ of $T$ for which ${r_{\text{\rm pack}}}(L_q) / r_q < \epsilon$. By FLC there are two copies of $q$ which occur at some markers $x$ and $y$ of tiles in $T$, satisfying $|x-y|=2{r_{\text{\rm pack}}}(L_q)$.

Set $a={r_{\text{\rm pack}}}(L_q)$. Consider the largest privileged patch $p$ contained in $q$, with same marker, and of radius $r\le r_q$. We must have $r\ge r_q/2$ for otherwise, as $p$ occurs both at $x$ and $y$, then one of its derived patches $p'$ would have radius $r' \le r+ 2a < r_q/2 + 2\epsilon r_q < r_q$. Hence $p'$ would be contained in $q$, which contradicts maximality of $p$ in $q$.

Consider the largest privileged patch $p_0\subset p$, with same marker, and radius $r_0 < r/2$. Since $p_0$ occurs both at $x$ and $y$, it has a derived patch $p_1\subset p$, with radius $r_1 \le r_0 + 2a < r/2 + \epsilon r_q<r$, which is thus a proper sub-patch of $p$. By Lemma \[lem-der\] (iii), we have $p=p_1^{(n-1)}=p_0^{(n)}$ for some $n>1$. Again $p_1$ occurs both at $x$ and $y$, so it has a derived patch $p_2=p_0^{(2)} \subsetneq p$ of radius $r_2\le r_1+2a \le r_0 + 4a$. See Figure \[fig-nrep\] for an illustration.

![The dotted circles, in order of decreasing radii, are the translates $p+y$, $p_1+y$, and $p_0+y$. The small circles along the horizontal axis are occurrences of the same patch, and illustrate the local periodic pattern generated by the overlaping of $p+x$ and $p+y$.[]{data-label="fig-nrep"}](nrep-0.pdf)

We iterate this argument to obtain that there is a patch $p_j=p_0^{(j)}$ with radius $r_j \le r_0 + 2ja$, for all $j\le n$. For $j=n$ this last inequality implies $n \ge r/(4a)  \ge r_q /(8a) > 1/ (8\epsilon) > m$. We have thus build a sequence of privileged patches $p_0, p_1, \cdots p_m, \cdots p_n=p$, whose first $m+1$ terms give the sequence in (i). But $p_0$ is the largest privileged patch in $p$ (with same marker and) of radius $r_0< r/2$, hence $p_1=p_0'$ has radius $r_1\ge r/2= r_n/2 \ge r_m/2$, which proves (ii).

The tree of privileged patches and the Connes metrics {#sec-tree}
=====================================================

We build the tree ${{\mathcal T}}$ of privileged patches of $T$ inductively as follows:

1.  [(0)]{} the root of ${{\mathcal T}}$ stands for the empty patch;

2.  [(1)]{} vertices of order $1$ stand for privileged patches of order 1 (prototiles), each of which is linked by one edge to the root;

3.  [(n)]{} vertices of order $n>1$ stand for privileged patches of order $n$, each of which is linked by one edge to the vertex of order $n-1$ corresponding to the patch it is derived from.

The tree ${{\mathcal T}}$ is well-defined by Lemma \[lem-der\] (ii): each vertex of level $n+1$ is linked to a unique vertex of level $n$, for all $n$.

We let $\partial {{\mathcal T}}$ be the set of infinite rooted path in ${{\mathcal T}}$: $\xi =(\xi_n)_{n\ge 0} \in \partial {{\mathcal T}}$ is a sequence of privileged patches, with $\xi_{n+1}$ derived from $\xi_n$ for all $n$. Given a vertex $v\in {{\mathcal T}}$, we let $[v] \subset \partial {{\mathcal T}}$ be the [*cylinder*]{} of $v$, namely the set of all infinite paths through $v$.

\[prop-tree\] The set $\partial {{\mathcal T}}$ of infinite paths in ${{\mathcal T}}$, endowed with the topology of cylinders, is homeomorphic to the discrete hull $\Xi$.

The sets $\partial {{\mathcal T}}$ and $\Xi$ are easily seen to be isomorphic. Given a tiling $T$ in $\Xi$, let $\xi_0$ be the empty patch and $\xi_1$ the prototile occurring in $T$ at the origin. Since $T$ is repetitive, there is a (unique) privileged patch $\xi_2$ derived from $\xi_1$ which occurs in $T$ at the origin. We construct inductively a (unique) sequence of privileged patches occurring at the origin of $T$, which defines an infinite path in ${{\mathcal T}}$. Conversely, by Lemma \[lem-rder\] (ii), a sequence of privileged patches in $\partial {{\mathcal T}}$ defines a unique tiling in $\Xi$.

A basis for the topology of $\Xi$ is given by the acceptance domains $[p]$ of patches. While cylinders correspond to acceptance domains of privileged patches, hence yield a coarser topology on $\Xi$. Given a patch $p$, let $p_0$ is the greatest privileged patch contained in $p$, and $p_1, \ldots p_k$ the patches derived from $p_0$. Then $[p] \subset [p_1] \cup \ldots \cup [p_k]$, so both topologies agree.

A [*weight function*]{} is any function $\delta: [0,+\infty) \rightarrow (0,1]$, which decreases and has limit $0$ at $+\infty$. A weight function allows us to defined a ultra metric on $\Xi$, as in equation , and to build a spectral triple on $C(\Xi)$ as explained in Section \[sec-ST\]. The Connes distance of that spectral triple yields two pseudo-metrics on $\partial {{\mathcal T}}\simeq \Xi$, which we now define.

Given $\xi, \xi'\in \partial {{\mathcal T}}$, we let $\xi {\, {\widetilde}\wedge \,}\xi'$ denote the vertex at which the paths branch in ${{\mathcal T}}$, and ${{\mathcal O}}(\xi {\, {\widetilde}\wedge \,}\xi')$ the order of that vertex. If we identify $\xi,\xi'$ with tilings $T,T'\in\Xi$ by Proposition \[prop-tree\], then $\xi{\, {\widetilde}\wedge \,}\xi'$ is the greatest common privileged patch which occurs in both $T$ and $T'$ at the origin. The following define two metrics[^3] on $\partial {{\mathcal T}}$: $$\label{eq-dinf}
{d_{\text{\rm inf}}}(\xi, \xi') = \left\{ \begin{array}{ll} \delta\bigl( r_{{{\mathcal O}}(\xi {\, {\widetilde}\wedge \,}\xi')}  \bigr)& \text{\rm if } \xi \neq \xi' \\ 0 & \text{\rm if } \xi = \xi' \end{array}\right.,$$ and $$\label{eq-dsup}
{d_{\text{\rm sup}}}(\xi,\xi') = {d_{\text{\rm inf}}}(\xi,\xi') + \sum_{n> {{\mathcal O}}(\xi {\, {\widetilde}\wedge \,}\xi')}  \delta(r_n) + \delta(r'_n) \ ,
$$ where $r^{(')}_n$ is the radius of the patch $\xi^{(')}_n$ (so one has $r_n=r'_n$ for all $n\le {{\mathcal O}}(\xi {\, {\widetilde}\wedge \,}\xi')$).

Clearly ${d_{\text{\rm inf}}}\le {d_{\text{\rm sup}}}$, and one easily sees that ${d_{\text{\rm inf}}}$ and ${d_{\text{\rm sup}}}$ are Lipschitz equivalent if and only if $$\label{eq-Lip}
\exists C>0, \, \forall \xi \in \partial {{\mathcal T}}, \, \forall m\in {{\mathbb N}}, \qquad
\delta(r_m)^{-1} \sum_{k \ge 1}  \delta(r_{m+k}) \le C \,.$$

Characterisation of repulsive tilings {#sec-charact}
=====================================

We state our main result. Let $T$ be an aperiodic, repetitive, and FLC tiling of ${{\mathbb R}}^d$, as in Definition \[def-hypT\]. Consider the tree ${{\mathcal T}}$ of privileged patches of $T$ as in the previous section. Let $\delta: [0,+\infty) \rightarrow (0,1]$ be a weight function as in the previous section (decreasing with limit $0$ at infinity), and assume that there exists $c_1, c_2>0$ such that $$\label{eq-delta}
\delta(ab) \le c_1 \delta(a) \delta(b), \qquad \delta(2a)\ge c_2 \delta(a), \ \forall a,b \ge 0.$$ Consider the metrics ${d_{\text{\rm inf}}}$ and ${d_{\text{\rm sup}}}$ on $\partial {{\mathcal T}}$ given in equations  and .

\[thm-main\] The following are equivalent:

(i) $T$ is repulsive,

(ii) ${d_{\text{\rm inf}}}$ and ${d_{\text{\rm sup}}}$ are Lipschitz equivalent.

Assume $T$ is repulsive, so $\ell>0$ in equation . Upon rescalling $\delta$, we may assume that $c_1=1$ in equation , and $\delta(2\ell +1)<1$. Pick $m\in{{\mathbb N}}$ and $\xi\in\partial {{\mathcal T}}$. Let $r_n$ be the radius of the patch $\xi_n$, $n\ge 0$. By Lemma \[lem-rder\] (ii), for any $k\ge 1$ we have $r_{m+k}\ge (2\ell +1)^k r_m$. Hence $$\delta(r_{m})^{-1} \sum_{k\ge 1 }  \delta(r_{m+k}) \le  
\delta(r_{m})^{-1} \sum_{k\ge 1 }  \delta((2\ell+1)^k) \delta(r_{m}) \le
 \sum_{k\ge 1 }  \delta(2\ell +1)^k\,,$$ where the last two inequalities follows from equation . The converging geometric series on the right hand side gives a uniform bound in equation , which proves that ${d_{\text{\rm inf}}}$ and ${d_{\text{\rm sup}}}$ are Lipschitz equivalent.

Assume that $T$ is not repulsive. Fix an integer $N$ (large), and consider a sequence of privileged patches $p_0, p_1, \ldots p_{m}$, $m>N$, as in Lemma \[lem-nrep\]. Choose an infinite path $\xi\in\partial {{\mathcal T}}$ going through the vertices associated with $p_0, p_1 \ldots p_{m}$. Upon a change of index, we may assume that $\xi_j$ corresponds to $p_j$, for $j=1, \ldots m$. Then $$\delta(r_{1})^{-1} \sum_{k\ge 1}  \delta(r_{1+k}) \ge \frac{1}{\delta(r_{1})} \sum_{j=2}^{m} \delta(r_j) \ge \frac{m-1}{\delta(r_{1})}\delta(r_m) \ge \frac{N}{\delta(r_1)} \delta(2r_1)\ge Nc_2\,,$$ where we used that $\delta$ decreases, and equation . Since $N$ was arbitrary, one cannot bound the series on the left hand side. So there exists no uniform bound in equation , and thus ${d_{\text{\rm inf}}}$ and ${d_{\text{\rm sup}}}$ are not Lipschitz equivalent.

The spectral triple {#sec-ST}
===================

For the sake of completeness, we remind the reader of the spectral triple on $C(\Xi)\cong C(\partial {{\mathcal T}})$ whose Connes distance yields ${d_{\text{\rm inf}}}$ and ${d_{\text{\rm sup}}}$. The construction in [@KS10] is given for any tree, and in [@KLS11] for the tree of privileged words of a $1d$-subshift, which we rewrite here for the tree of privileged patches defined in Section \[sec-tree\]. These constructions are related to other spectral triples build for metric spaces [@Ri99; @Ri04; @CI07] or more specifically fractals [@GI03; @GI05; @CIL08] and ultrametric Cantor sets [@PB09]. We refer the reader to [@KS10] and [@KLS11] for details and proofs.

We consider the tree ${{\mathcal T}}=({{\mathcal T}}^0,{{\mathcal T}}^1)$ of privileged patches, and a weight $\delta$ as in Section \[sec-tree\]. We add [*horizontal edges*]{} ${{\mathcal H}}$ to the graph ${{\mathcal T}}$: ${{\mathcal H}}=\cup_{n\ge 1} {{\mathcal H}}_n$, and ${{\mathcal H}}_n$ is a set of oriented edges between vertices of level $n$ in ${{\mathcal T}}$ defined as follows. If $u_1,u_2\in {{\mathcal T}}$, then there is one horizontal edge $h\in {{\mathcal H}}_n$ with source $s(h)=u_1$ and range $r(h)=u_2$, if and only if $u_1$ and $u_2$ stand for two distinct privileged patches of order $n$ both of which are derived from the same privileged patch of order $n-1$. Given any such $h$, there is then an edge $h^{\text{\rm op}}\in {{\mathcal H}}$ with reverse orientation: $r(h^{\text{\rm op}})=s(h)$ and $s(h^{\text{\rm op}})=r(h)$, and $(h^{\text{\rm op}})^{\text{\rm op}}=h$. We fix an orientation of ${{\mathcal H}}$, and write the decomposition into positively and negatively oriented edges ${{\mathcal H}}={{\mathcal H}}_+ \cup {{\mathcal H}}_- $.

A [*choice*]{} is a map $\tau: {{\mathcal T}}^{0} \rightarrow \partial {{\mathcal T}}$ such that $\tau(v)$ is an infinite path through vertex $v$. The [*approximation graph*]{} $G_\tau=(V,E)$ is defined by $$V= \tau({{\mathcal T}}^0), \qquad E= \tau\times \tau ({{\mathcal H}}).$$ The orientation on ${{\mathcal H}}$ is carried over to $E=E_+ \cup E_-$. We endow $G_\tau$ with the graph metric induced by the weight $\delta$: for $e=\tau\times\tau(h) \in E$ we set the length of $e$ to be $\ell(e) = \delta(r_h)$, where $r_h$ is the radius of the privileged patch from which $s(h)$ and $r(h)$ are derived. The set of vertices $V$ is dense in $\partial {{\mathcal T}}$, and the set of edges $E$ encodes adjacencies according to the choice $\tau$.

We consider the spectral triple associated with the approximation graph $G_\tau=(V,E)$: $\bigl( C(\partial{{\mathcal T}}), \ell^2(E), \pi_\tau, D\bigr)$. The C$^\ast$-algebra $C(\partial {{\mathcal T}})$ of continuous functions over $\partial{{\mathcal T}}$ is faithfully represented on the Hilbert space $\ell^2(E)$ by $$\pi_\tau (f) {\varphi}(e) = f\bigl( s(e) \bigr) {\varphi}(e).$$ The Dirac $D$ is the unbounded operator on $\ell^2(E)$, with compact resolvent, given by $$D{\varphi}(e) = \frac{1}{\ell(e)} {\varphi}( e^{\text{\rm op}}).$$ The “non commutative derivation” is the finite difference operator $$\bigl[ D,\pi_\tau(f) \bigr] {\varphi}(e) = \frac{f(s(e)) - f(r(e))}{\ell(e)} {\varphi}(e^{\text{\rm op}}),$$ which is bounded over the pre-C$\ast$-algebra $C_{Lip}(\partial {{\mathcal T}})$ of Lipschitz continuous functions over $\partial {{\mathcal T}}$. The Connes distance of the spectral triple is a pseudo-metric over $\partial {{\mathcal T}}$ which reads $$\begin{aligned}
d_\tau (\xi, \xi') &=&  \sup_{f\in C(\partial {{\mathcal T}})} \Bigl\{ \bigl| f(\xi) - f(\xi')\bigr| : \| [D, \pi_\tau(f) \| \le 1 \Bigr\}  \\
& = & \sup_{f\in C(\partial {{\mathcal T}})} \Bigl\{ \bigl| f(\xi) - f(\xi') \bigr| : |f(s(e)) - f(r(e))| \le \ell(e), \, \forall e\in E \Bigr\}\end{aligned}$$ where the norm is the operator norm on $\ell^2(E)$. It is an extension of the graph metric of $G_\tau$ to $\partial {{\mathcal T}}$. If it is continuous for the topology of ${{\mathcal T}}$, it reads explicitly: $$d_\tau(\xi, \xi') = {d_{\text{\rm inf}}}(\xi, \xi') + \sum_{n> {{\mathcal O}}(\xi{\, {\widetilde}\wedge \,}\xi')} b_\tau(\xi_n) \delta(r_n) + b_\tau(\xi'_n) \delta(r'_n)\,,$$ where $\xi^{(')}=(\xi^{(')}_n)$, $r^{(')}_n$ is the radius of the patch $\xi^{(')}_n$, and for $\eta\in\partial{{\mathcal T}}$, $b_\tau(\eta_n) = 1$ if $\eta$ and $\tau(\eta_n)$ branch at $\eta_n$, and $b_\tau(\eta_n) = 0$ otherwise. The infimum and supremum of $d_\tau$ over choices $\tau$ yield the metrics ${d_{\text{\rm inf}}}$ of equation  and ${d_{\text{\rm sup}}}$ and  respectively.

[BEL]{}

A. Connes. [*Noncommutative geometry*]{}. Academic Press Inc., San Diego, CA, 1994.

E. Christensen, C. Ivan. “Sums of two-dimensional spectral triples”. [*Math. Scand.*]{} [**100**]{} (2007) 35–60.

E. Christensen, C. Ivan, M.L. Lapidus. “Dirac operators and spectral triples for some fractal sets built on curves”. [*Adv. Math.*]{} [**217**]{} (2008), no. 1, 42–78.

F. Durand. “Linearly recurrent subshifts have a finite number of non-periodic subshift factors”. [*Ergodic Theory Dynam. Systems*]{} [**20**]{} (2000) 1061–1078.

F. Durand. Corrigendum and addendum to [@Dur00]. [*Ergodic Theory Dynam. Systems*]{} [**23**]{} (2003) 663–669.

A. Glen, J. Justin, S. Widmer, L.Q. Zamboni. “Palindromic richness”. [*European J. Combin.*]{} [**30**]{} (2009) 510–531.

D. Guido, T. Isola. “Dimensions and singular traces for spectral triples, with applications for fractals”. [*J. Func. Anal.*]{} [**203**]{} (2003) 362–400.

D. Guido, T. Isola. “Dimension and spectral triples for fractals in ${{\mathbb R}}^n$”. In Advances in Operator Algebras and Mathematical Physics, [*Theta Ser. Adv. Math.*]{} [**5**]{}, Theta, Bucarest (2005), 89–108.

M. Forsyth, A. Jayakumar, J. Shallit. “Remarks on Privileged Words”. [*Eprint*]{} arXiv:1306.6768 (math.CO).

A.E. Frid, S. Puzynina, L. Zamboni. “On palindromic factorization of words”. [*Adv. in Appl. Math.*]{} [**50**]{} (2013) 737-748.

J. Kellendonk, J. Savinien. “Spectral triples and characterization of aperiodic order”. [*Proc. London Math. Soc.*]{} [**104**]{} (2012) 123-157.

J. Kellendonk, D. Lenz, J. Savinien. “A characterisation of subshifts with bounded powers”. [*Discrete Math.*]{} [**313**]{} (2013) 2881-2894.

J. Lagarias, P. Pleasants. “Repetitive Delone sets and quasicrystals”. [*Ergodic Theory Dynam. Systems*]{} [**23**]{} (2003) 831–867.

D. Lenz. “Aperiodic linearly repetitive delone sets are densely repetitive”. [*Discrete Comput. Geom.*]{} [**31**]{} (2004) 323-326.

J. Patera (ed.): [*Quasicrystals and Discrete Geometry*]{}, Toronto, ON, 1995. Fields Inst. Monogr., vol. 10. Am. Math. Soc., Providence (1998)

J. Pearson, J. Bellissard. “Noncommutative Riemannian geometry and diffusion on ultrametric Cantor sets”. [*J. Noncommut. Geom.*]{} [**3**]{} (2009) 447–481.

J. Peltomäki. “Introducing Privileged Words: Privileged Complexity of Sturmian Words”. [*Theoret. Comput. Sci.*]{} [**500**]{} (2013) 57-67.

J. Peltomäki. “Privileged Factors in the Thue-Morse Word - A Comparison of Privileged Words and Palindromes”. [*Eprint*]{} arXiv:1306.6768 (math.CO).

M. Rieffel. “Metrics on state spaces”. [*Doc. Math.*]{} [**4**]{} (1999) 559–600.

M. Rieffel. “Compact Quantum Metric Spaces”. [*Operator algebras, quantization, and noncommutative geometry*]{} 315–330, Contemp. Math. [**365**]{}, Amer. Math. Soc., Providence (2004).

[^1]: sometimes also called a [*puncture*]{}, so that one talks about [*punctured tilings*]{}.

[^2]: closed and open sets

[^3]: ${d_{\text{\rm inf}}}$ is a ultra-metric, ${d_{\text{\rm sup}}}$ is valued in $[0,+\infty]$.
