Asymptotic geometry of lamplighters over one-ended groups

Abstract

This article is dedicated to the asymptotic geometry of wreath products $F\wr H := \left ( \bigoplus _{H} F \right ) \rtimes H$ where $F$ is a finite group and $H$ is a finitely generated group. Our first main result says that a coarse map from a finitely presented one-ended group to $F\wr H$ must land at bounded distance from a left coset of $H$. Our second main result, building on the later, is a very restrictive description of quasi-isometries between two lamplighter groups on finitely presented one-ended groups. Third, we obtain a complete classification of these groups up to quasi-isometry. More precisely, given two finite groups $F_{1}$, $F_{2}$ and two finitely presented one-ended groups $H_{1}$, $H_{2}$, we show that $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are quasi-isometric if and only if either (i) $H_{1}$, $H_{2}$ are non-amenable quasi-isometric groups and $|F_{1}|$, $|F_{2}|$ have the same prime divisors, or (ii) $H_{1}$, $H_{2}$ are amenable, $|F_{1}|=k^{n_{1}}$ and $|F_{2}|=k^{n_{2}}$ for some $k,n_{1},n_{2} \geq 1$, and there exists a quasi-$(n_{2}/n_{1})$-to-one quasi-isometry $H_{1} \to H_{2}$. This can be seen as far reaching extension of a celebrated work of Eskin-Fisher-Whyte who treated the case of $H=\mathbb{Z}$. Our approach is however fundamentally different, as it crucially exploits the assumption that $H$ is one-ended. Our central tool is a new geometric interpretation of lamplighter groups involving natural families of quasi-median spaces.

1 Introduction

One of the central ideas in geometric group theory is that a finitely generated group can be considered itself as a geometric object. This can be done by considering one of its Cayley graphs, or more generally any geodesic metric space on which the group acts properly and cocompactly by isometries. The specific choice of metric space may be important, for instance in the perspective of CAT(0) groups. But since any two such spaces are quasi-isometric, any large scale geometric property is in fact an intrinsic property of the group. Historically, this point of view is motivated by early results exhibiting a tight connection between large scale geometric properties of a group and its algebraic structure, such as Stallings’ theorem about multi-ended groups, Gromov’s theorem about groups of polynomial growth, and Gromov’s theory of hyperbolic groups; even though earlier motivations can be found, including for instance small cancellation groups and Mostow’s rigidity. Nowadays, the program of classifying finitely generated groups up to quasi-isometry, as popularized in [31], is well-established and very active.

In this article, we contribute to this program by considering wreath products of groups. Recall that, given two groups $F$ and $H$, the wreath product $F \wr H$ is defined as the semidirect product $\left ( \bigoplus _{H} F \right ) \rtimes H$ where $H$ acts on the direct sum by permuting the coordinates by left-multiplication. These groups are also called lamplighter groups, a terminology coined by Jim Cannon (see [40]). The family of lamplighter groups is well-known in group theory, and has been studied from various perspectives over the years, including for instance random walks [16, 43, 46], isoperimetric profiles [19], functional analysis [35], subgroup distortion [9], Haagerup property [7, 8, 26, 44], and Hilbert space compression [1, 25, 33, 36]. On the one hand, lamplighter groups have an easy and explicit definition, allowing an easy access to various properties and calculations. On the other hand, these groups are sufficiently exotic, i.e. sufficiently far away from most of the well-understood classes of groups exhibited in the literature, in order to exhibit interesting behaviours. The combination of these two observations probably explains the success of lamplighter groups, and why they are often used to produce counterexamples (see for instance [17, 30]).

The first work dedicated to the classification of wreath products up to quasi-isometry seems to be [17], whose elementary observations lead to non-trivial examples of quasi-isometric groups. More explicitly, given four finitely generated groups $F_{1}$, $F_{2}$, $H_{1}$, $H_{2}$, we know that, if $F_{1}$ (resp. $H_{1}$) is biLipschitz equivalent to $F_{2}$ (resp. $H_{2}$), then $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are biLipschitz equivalent. As a consequence, the wreath products $\mathbb{Z}_{60} \wr \mathbb{Z}$ and $\mathfrak{A}_{5} \wr \mathbb{Z}$, where $\mathfrak{A}_{5}$ and $\mathbb{Z}_{60}$ are the alternating and cyclic groups of order 60, are quasi-isometric while $\mathbb{Z}_{60} \wr \mathbb{Z}$ is solvable but $\mathfrak{A}_{5} \wr \mathbb{Z}$ not virtually solvable (contrasting with Gromov’s theorem about groups of polynomial growth); also, the wreath products $\mathbb{Z} \wr \mathbb{Z}$ and $\mathbb{D}_{\infty }\wr \mathbb{Z}$ are quasi-isometric while $\mathbb{Z} \wr \mathbb{Z}$ is torsion-free but $\mathbb{D}_{\infty }\wr \mathbb{Z}$ not virtually torsion-free. However, a complete classification of wreath products up to quasi-isometry in full generality seems to be out of reach right now. In this article, we focus on the following question:

Question 1.1

Let $F_{1}$, $F_{2}$ be two (non-trivial) finite groups and $H_{1}$, $H_{2}$ two finitely generated groups. When are $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ quasi-isometric?

The same question can be found in [11] for the specific case $H_{1}=H_{2}= \mathbb{Z}$, and has been solved in [20, 21]. A slight modification of the classification they get is the following (see Sect. 7 for more details):

Theorem 1.2

[20, 21]

Let $F_{1}$, $F_{2}$ be two finite groups and $H_{1}$, $H_{2}$ two finitely generated groups. Assume that $H_{1}$ is two-ended. Then $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are quasi-isometric if and only if $H_{1}$, $H_{2}$ are quasi-isometric and $|F_{1}|$, $|F_{2}|$ are powers of a common number.

In [20, 21], the authors focus on the geometry of two specific horospherical products: the product of two hyperbolic planes, which coincides with $\mathrm{SOL}$; and the products of two regular trees, also known as Diestel-Leader graphs, and which turn out to coincide with Cayley graphs of lamplighter groups of the form $\mathbb{Z}_{n} \wr \mathbb{Z}$ when the trees are both $(n+1)$-regular [48]. Inspired by the study of solvable Baumslag-Solitar groups [22, 23] and other finitely presented abelian-by-cyclic groups [24], the strategy followed in [20, 21] is to show that the height function of the horospherical product under consideration (which coincides with the quotient map $\mathbb{Z}_{n} \wr \mathbb{Z} \twoheadrightarrow \mathbb{Z}$ for lamplighter groups) is (quasi-)preserved by quasi-isometries; to deduce that quasi-isometries induce biLipschitz maps between natural boundaries of the horospherical products, hence $\mathrm{QI}(\mathrm{SOL}) = \mathrm{Bilip}(\mathbb{R})^{2} \rtimes \mathbb{Z}_{2}$ and $\mathrm{QI}(\mathbb{Z}_{n} \wr \mathbb{Z}) = \mathrm{Bilip}( \mathbb{Q}_{n})^{2} \rtimes \mathbb{Z}_{2}$; and finally to conclude thanks to general works dedicated to actions on ℝ and $\mathbb{Q}_{n}$. The key step is the proof of the (quasi-)preservation of the height function, which is highly non-trivial and required the introduction of the whole machinery of coarse differentiation.

Thus, the understanding of the geometry of lamplighter groups over ℤ relies on the small miracle that such lamplighters can be described as horospherical products of trees. For lamplighter groups over one-ended groups, for instance $\mathbb{Z}^{2}$, such a structure does not occur any more. One could say that [20, 21] (together with [15, 41, 42]) deals with the family of lamplighter groups of higher rank [3], whose intersection with wreath products only contains lamplighter groups over ℤ. Therefore, in order to study lamplighter groups as a whole, we need a new point of view.

As expressed in [11, Paragraph IV.B.44], it is reasonable to think that the geometry of wreath products such as $\mathbb{Z}_{n} \wr \mathbb{Z}^{2}$ is more complicated than the geometry of $\mathbb{Z}_{n} \wr \mathbb{Z}$ because the solution to the travelling salesman problem (which is closely related to the metrics in wreath products) is more complicated on $\mathbb{Z}^{2}$ than on ℤ, where it is particularly easy. This idea is also motivated by [32], where algebraically simple groups quasi-isometric to lamplighter groups over non-abelian free groups are constructed, which contracts drastically with lamplighters over ℤ. By contrast, we show in this article that lamplighter groups over one-ended finitely presented groups are even more rigid than in the case of ℤ, and exploiting this rigidity allows us to completely classify them up to quasi-isometry.

Before going into the details, let us mention that our techniques apply to a wider class of (non-necessarily vertex-transitive) graphs, defined as follows.

Definition 1.3

Let $X$ be a graph and $n \geq 2$ an integer. The lamplighter graph $\mathcal{L}_{n}(X)$ is the graph

• whose vertices are the pairs $(c,x)$ with $c : V(X) \to \mathbb{Z}_{n}$ a finitely supported colouring taking values in the cyclic group of order $n$ and $x \in V(X)$ a vertex;

• and whose edges connect $(c_{1},x_{1})$ and $(c_{2},x_{2})$ either if $c_{1}=c_{2}$ and $x_{1}$, $x_{2}$ are adjacent, or if $x_{1}=x_{2}$ and $c_{1}$, $c_{2}$ differ only at this vertex.

A leaf is a subgraph $\{(c,x) \mid x \in X\}$ where $c \in \mathbb{Z}_{n}^{(X)}$ is a fixed colouring.

Observe that, given a non-trivial finite group $F$ and a group $H$ with a finite generating set $S$, the Cayley graph $\mathrm{Cayl}(F \wr H, F \cup S)$ coincides with $\mathcal{L}_{|F|}(\mathrm{Cayl}(H,S))$ and its leaves correspond to $H$-cosets, justifying the terminology and the fact that this framework subsumes the geometric study of our wreath products.

The rigidity of lampligther groups over one-ended groups that we have mentioned above is illustrated by the following embedding theorem:

Theorem 1.4

Let $X$, $Z$ be two graphs, $n \geq 2$ an integer, and $\rho : Z \to \mathcal{L}_{n}(X)$ a coarse embedding. If $Z$ is coarsely simply connected and uniformly one-ended, then the image of $\rho$ lies in the neighbourhood of a leaf in $\mathcal{L}_{n}(X)$.

Some explanations are required here. A graph is coarsely simply connected if there exists $R\geq 0$ such that filling in cycles of $Z$ of length $\leq R$ with discs produces a simply connected 2-complex. For Cayley graphs, this is equivalent to the group being finitely presented. A graph $X$ is uniformly one-ended if, for every $R \geq 0$, there exists $D \geq 0$ such that the complement in $X$ of every ball of radius $R$ has one connected component that is unbounded but all the other components have diameter $\leq D$. (Cayley graphs of) finitely generated groups are uniformly one-ended if and only if they are one-ended.

An important consequence of the theorem is that the $H$-cosets of a wreath product $(\text{finite group}) \wr (H \text{ finitely presented one-ended})$ are (quasi-)preserved under quasi-isometries, silimilarly to peripheral subgroups in relatively hyperbolic groups that are also (quasi-)preserved by quasi-isometries [12]. Theorem 1.4 is fundamental in the geometry of lamplighter graphs, and is the core of this article. Building on it, we are able to completely classify lamplighters over finitely presented one-ended groups up to quasi-isometry. Even though Theorem 1.4 appears as an intermediate step of the proof of this classification, we would like to emphasize that the information it provides is much deeper, which will be apparent when quasi-isometric rigidity will be discussed later.

Theorem 1.5

Let $n,m \geq 2$ be two integers and $X$, $Y$ two coarsely simply connected uniformly one-ended graphs of bounded degree.

• If $X$ is amenable, then $\mathcal{L}_{n}(X)$ and $\mathcal{L}_{m}(Y)$ are quasi-isometric if and only if there exist $k,r,s \geq 1$ such that $n=k^{r}$, $m=k^{s}$ and such that there exists a quasi-$(s/r)$-to-one quasi-isometry $X \to Y$.

• If $X$ is non-amenable, then $\mathcal{L}_{n}(X)$ and $\mathcal{L}_{m}(Y)$ are quasi-isometric if and only if $X$, $Y$ are quasi-isometric and $n$, $m$ have the same prime divisors.

We refer to Sect. 2 for the definition of quasi-$\kappa$-to-one maps, and more specifically to Proposition 2.9 when $\kappa$ is rational. The algebraic counterpart of Theorem 1.5 is the following (see Sect. 6.2 for a more general version that deals with permutational wreath products):

Corollary 1.6

Let $F_{1}$, $F_{2}$ be two non-trivial finite groups and $H_{1}$, $H_{2}$ two finitely presented groups. Assume that $H_{1}$ is one-ended.

• If $H_{1}$ is amenable, then $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are quasi-isometric if and only if there exist $k,n_{1},n_{2} \geq 1$ such that $n=k^{n_{1}}$, $m=k^{n_{2}}$ and such that there exists a quasi-$(n_{2}/n_{1})$-to-one quasi-isometry $H_{1} \to H_{2}$.

• If $H_{1}$ is non-amenable, then $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are quasi-isometric if and only if $H_{1}$, $H_{2}$ are quasi-isometric and $n_{1}$, $n_{2}$ have the same prime divisors.

The dichotomy provided by Theorem 1.5 between lamplighters over amenable and non-amenable graphs is twofold. The first difference deals with the indices $n$, $m$. In the amenable case, we recover from Theorem 1.5 a criterion similar to Theorem 1.2. But in the non-amenable case, more lamplighter graphs turn out to be quasi-isometric. We emphasize that this phenomenon is not specific to coarsely simply connected and one-ended graphs:

Proposition 1.7

Let $X$, $Y$ be two arbitrary non-amenable graphs with bounded degree. If $n,m \geq 2$ are two integers having the same prime divisors, then $\mathcal{L}_{n}(X)$ and $\mathcal{L}_{m}(Y)$ are quasi-isometric.

As a particular case, if $\mathbb{F}$ is a free group of finite rank $\geq 2$, then $\mathbb{Z}_{n} \wr \mathbb{F}$ and $\mathbb{Z}_{m} \wr \mathbb{F}$ are quasi-isometric as soon as $n$, $m$ have the same prime divisors. See Proposition 3.13 below for more details. Even though the proof is elementary, up to our knowledge, this fact has not been noticed before. The second difference comes from the fact that every quasi-isometry between two non-amenable graphs of bounded degree is quasi-one-to-one, i.e. it lies at finite distance from a bijective quasi-isometry [37, 47], which may not be the case for amenable graphs of bounded degree [5, 34] or even for finitely generated amenable groups [14]. (More details on this subject are given below.) This leads to a major difference between the amenable and non-amenable cases. As an illustration, because [15] shows that higher rank lamplighter groups may be quasi-isometric without being biLipschitz equivalent, we deduce from Corollary 1.6 the following somehow surprising consequence:

Corollary 1.8

Let $F$ be a non-trivial finite group. There exist two finitely presented one-ended amenable groups $H_{1}$, $H_{2}$ that are quasi-isometric but such that $F \wr H_{1}$, $F\wr H_{2}$ are not quasi-isometric.

This second aspect of the difference between lamplighters over amenable and non-amenable groups is well-illustrated by the particular case $H_{1}=H_{2}$. For every finitely generated group $H$, set

$$ \kappa (H):= \{ \kappa >0 \mid \text{there exists a quasi-$\kappa $-to-one quasi-isometry $H \to H$} \}. $$

(Observe that, since two word metrics (with respect to finite generating sets) are biLipschitz equivalent, the set $\kappa (H)$ does not depend on a particular choice of a finite generating set.) Then we have:

Corollary 1.9

Let $F_{1}$, $F_{2}$ be two finite groups and $H$ a finitely generated amenable group. Then $F_{1}\wr H$ and $F_{2} \wr H$ are quasi-isometric if and only if there exist $k,n_{1},n_{2} \geq 1$ such that $|F_{1}|=k^{n_{1}}$, $|F_{2}|=k^{n_{2}}$, and $n_{1}/n_{2} \in \kappa (H)$.

This leads to the natural problem of investigating the structure of $\kappa (H)$ for a finitely generated amenable $H$. A first observation is that, as a consequence of Proposition 2.8, $\kappa (H)$ turns out to be a subgroup of the multiplicative group $\mathbb{R}_{>0}$. However, it is not clear what possible values can be taken by $\kappa (H)$. One the one hand, using homotheties in Euclidean spaces easily leads to the equality $\kappa (\mathbb{Z}^{n})= \mathbb{R}_{>0}$ for every $n \geq 1$, hence:

Corollary 1.10

Let $F_{1}$, $F_{2}$ be two finite groups and $n \geq 2$ an integer. The wreath products $F_{1} \wr \mathbb{Z}^{n}$ and $F_{2} \wr \mathbb{Z}^{n}$ are quasi-isometric if and only if $|F_{1}|$, $|F_{2}|$ are powers of a common number.

Based on the same idea, it can be shown that $\kappa (H)= \mathbb{R}_{>0}$ for every uniform lattice $H$ in a Carnot group, including the Heisenberg group. On the other hand, as a consequence of Corollary 1.16 mentioned below, $\kappa (F \wr H)= \{1\}$ for every non-trivial finite group $F$ and every finitely presented one-ended amenable group $H$ (e.g. $\mathbb{Z}^{2}$). Intermediate values are also possible: indeed, it follows from [14] that, for every $n \geq 2$, $\kappa (\mathbb{Z}_{n} \wr \mathbb{Z}) = \langle \text{prime factors of $n$} \rangle \subset \mathbb{Q}$. A more detailed discussion about the sets $\kappa (\cdot )$ is available in our work [29].

Let us also mention the following funny characterisation of amenability provided by Theorem 1.5 (even though it is not clear that it can be useful in practice):

Corollary 1.11

Let $X$ be a coarsely simply connected uniformly one-ended graph of bounded degree. Then $X$ is amenable if and only if $\mathcal{L}_{6}(X)$ and $\mathcal{L}_{12}(X)$ are quasi-isometric.

Of course, there is nothing specific about 6 and 12: they can be replaced with any two numbers that have the same prime divisors but that are not powers of a common number.

Finally, removing the one-ended assumption on the graphs, we are still able to show the following result.

Theorem 1.12

Let $F_{1}$, $F_{2}$ be two finite groups and $H_{1}$, $H_{2}$ two finitely presented groups. If $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are quasi-isometric, then so are $H_{1}$ and $H_{2}$.

Quasi-isometry vs. biLipschitz equivalence

An early question in geometric group theory, which can be found in [31, 1.A’], asks to which extend being quasi-isometric and being biLipschitz equivalent are different. For instance, are two quasi-isometric graphs with bounded degree necessarily biLipschitz equivalent? Partial positive answers was obtained for homogeneous trees [38], and next for hyperbolic groups [4], before it was realised that a positive answer holds for every non-amenable graph with bounded degree in a strong way:

Theorem 1.13

[37, 47]

Every quasi-isometry between two non-amenable graphs with bounded degree lies at finite distance from a bijection.

In the opposite direction, counterexamples for amenable graphs with bounded degree was constructed, for instance in [5, 34]. However, such graphs were not Cayley graphs, so it was natural to specify the question to finitely generated groups instead of arbitrary (amenable) graphs with bounded degree: are two quasi-isometric finitely generated groups necessarily biLipschitz equivalent? This question can be found [11, IV.B.46(vi)] for instance. It was first proved that no analogue of Theorem 1.13 holds for amenable groups: If $G$ is a finitely generated amenable group and $H \leq G$ a proper finite-index subgroup, then the inclusion $H \hookrightarrow G$ does not lie at finite distance from a bijection [13]. (This observation is also a consequence of Lemma 2.7 and Proposition 2.8 below.) But this does not show that there does not exist a biLipschitz equivalence $H \to G$ (that would not be at finite distance from the inclusion). The first counterexamples were constructed in [14] by considering lamplighter groups over ℤ.

Theorem 1.14

[14]

If $F_{1}$, $F_{2}$ are two finite groups such that $|F_{2}|=|F_{1}|^{k}$ for some $k \geq 2$ that is not a product of prime factors of $n$, then $F_{2} \wr \mathbb{Z}$ is a finite-index subgroup of $F_{1} \wr \mathbb{Z}$ but the two groups are not biLipschitz equivalent.

The proof of the theorem is fundamentally based on the structure of the quasi-isometry groups of lamplighter groups over ℤ as described in [20, 21]. Later, finitely presented counterexamples were obtained from higher rank lamplighter groups [15], based on the geometric picture of these groups obtained in [41, 42], also based on the heavy machinery of coarse differentiation introduced in [20, 21].

As a consequence of our work, we obtain more elementary examples of quasi-isometric groups that are not biLipschitz equivalent:

Corollary 1.15

Let $F_{1}$, $F_{2}$ be two non-trivial finite groups and $H$ one finitely presented amenable one-ended group. Then $F_{1} \wr H$ and $F_{2}\wr H$ are biLipschitz equivalent if and only if $|F_{1}|=|F_{2}|$.

As a consequence, if we assume that there exist $k$, $n_{1}$, $n_{2}$ such that $|F_{1}|=k^{n_{1}}$, $|F_{2}|=k^{n_{2}}$, and $n_{1}/n_{2} \in \kappa (H)$, then $n_{1} \neq n_{2}$ implies that $F_{1} \wr H$ and $F_{2} \wr H$ are quasi-isometric but they are not biLipschitz equivalent. As an illustration, $\mathbb{Z}_{4} \wr \mathbb{Z}^{2}$ is a finite-index subgroup of $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$ but these two groups are not biLipschitz equivalent. We also show that Theorem 1.13 does not characterise non-amenable groups by constructing the first examples of amenable groups such that every auto-quasi-isometry lies at finite distance from a bijection:

Corollary 1.16

Let $F$ be a non-trivial finite group and $H$ a finitely presented amenable one-ended group. Then every quasi-isometry $F \wr H \to F\wr H$ lies at finite distance from a bijection.

We emphasize that such a property has strong consequences. Loosely speaking, $\kappa$ can be used as an Euler characteristic in this context. For instance:

Corollary 1.17

Let $F$ be a non-trivial finite group and $H$ a finitely presented one-ended amenable group. Fix two finite-index subgroups $K_{1},K_{2} \leq F \wr H$. If $K_{1}$ and $K_{2}$ are biLipschitz equivalent (e.g. isomorphic) then they have the same index in $F \wr H$.

Notice that the algebraic part of this statement cannot be proved by using an actual Euler characteristic as a consequence of [6] (see also [18]). We refer to Proposition 6.5 for a more general statement.

In the rest of the introduction, we give some details about the strategy used in order to prove Theorem 1.5.

Aptolic quasi-isometries

A central idea of the article is that a quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$, where $n,m \geq 2$ where and $X$, $Y$ are coarsely simply connected uniformly one-ended, is compatible with the lamplighter structure in a strong way. We formalise this idea through the following concept:

Definition 1.18

Let $n,m \geq 1$ be two integers and $X$, $Y$ two graphs. A map $q: \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ is of aptolic form¹ if there exist $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and $\beta :X \to Y$ such that $q(c,x)=(\alpha (c),\beta (x))$ for all $(c,x) \in \mathcal{L}_{n}(X)$. A quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ is aptolic if it is of aptolic form and if it admits a quasi-inverse of aptolic form.

The first step towards the proof of Theorem 1.5 is to show that, if there exists an aptolic quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ between two lamplighter graphs, where $X$, $Y$ are not necessarily coarsely simply connected nor one-ended, then $X$, $Y$ must be quasi-isometric and $n$, $m$ must have the same prime divisors. Moreover, if in addition $X$ is amenable, then we obtain a stronger conclusion: $n$, $m$ must be powers of a common number, say $n=k^{r}$, $m=k^{s}$ for some $r,s \geq 1$; and there must exist a quasi-isometry $X \to Y$ that is quasi-$(s/r)$-to-one. This is done by elementary combinatorial arguments in Sect. 3. The hard part is to prove that, if $X$, $Y$ are coarsely simply connected and uniformly one-ended graphs, an arbitrary quasi-isometry between our two graphs always lies at finite distance from an aptolic quasi-isometry, that is:

Theorem 1.19

Let $n,m \geq 2$ be two integers and $X$, $Y$ two coarsely simply connected uniformly one-ended graphs of bounded degree. Then every quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ is at bounded distance from an aptolic quasi-isometry.

Observe that, as a consequence of Proposition 3.8 below, the conclusion always fails outside the one-ended case. Combining this theorem with the previous observations related to aptolic quasi-isometries leads to a proof of Theorem 1.5.

Embedding theorem

Theorem 1.19 is proved in two steps. First, we prove in Sect. 4 that a quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$, where $X$, $Y$ are not necessarily coarsely simply connected nor one-ended, that is leaf-preserving, i.e. that sends every leaf of $\mathcal{L}_{n}(X)$ at finite Hausdorff distance from a leaf of $\mathcal{L}_{n}(X)$, must be at finite distance from an aptolic quasi-isometry. Next, we prove that, if $X$, $Y$ are coarsely simply connected and uniformly one-ended, then any quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ must be leaf-preserving, which is a consequence of the embedding theorem provided by Theorem 1.4.

Let us motivate and illustrate the strategy we follow in order to prove Theorem 1.4 by considering lamplighter groups instead of more general lamplighter graphs. First, assume that there exists a 1-Lipschitz coarse embedding $\rho$ from $\mathbb{Z}^{2}$ (identified with its Cayley graph associated to $S:= \{(0,1),(1,0)\}$) to $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$ (identified with its Cayley graph associated to $\mathbb{Z}_{2} \cup S$). It is an elementary observation that $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$ has no 3-cycle and that every 4-cycle in $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$ lies in a $\mathbb{Z}^{2}$-coset. As a consequence, the image of $\rho$ in the 2-complex $X$ obtained from $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$ by filling in all the 4-cycles with discs is necessarily homotopically trivial. So $\rho$ lifts to the universal cover $\widetilde{X}$, giving a coarse embedding $\widetilde{\rho} : \mathbb{R}^{2} \to \widetilde{X}$. But the geometry of $\widetilde{X}$ is quite specific. Intuitively, we think of $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$ as endowed with a leaf structure induced by the $\mathbb{Z}^{2}$-cosets. In $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$, two leaves do not fellow-travel, i.e. the intersection between the neighbourhoods of two distinct leaves is always bounded. This motivates the idea that $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$ has the local geometry of a tree of flats and that $\widetilde{X}$ should be a tree of flats. An algebraic justification of this picture is that $\widetilde{X}$ coincides with the Cayley 2-complex of the truncated presentation

$$ \langle a,r,s \mid a^{2}=1, [r,s]=1 \rangle \simeq \mathbb{Z}_{2} \ast \mathbb{Z}^{2} $$

obtained from the presentation

$$ \langle a,r,s \mid a^{2}=1, [r,s]=1, \left [ a, r^{m}s^{n}as^{-n}r^{-m} \right ]=1 \ (n,m \in \mathbb{Z}) \rangle $$

of $\mathbb{Z}_{2} \wr \mathbb{Z}^{2}$. Therefore, $\widetilde{X}$ is indeed a tree of flats, which implies that the image of $\widetilde{\rho} : \mathbb{Z}^{2} \to \widetilde{X}$ must lie in the neighbourhood of a flat; and because the covering map $\widetilde{X} \to X$ sends every flat to a $\mathbb{Z}^{2}$-coset (up to finite distance), we conclude that the image of $\rho : \mathbb{Z}^{2} \to \mathbb{Z}_{2} \wr \mathbb{Z}^{2}$ lies in the neighbourhood of $\mathbb{Z}^{2}$-coset.

In the general case of an arbitrary coarse embedding $\rho : Z \to \mathbb{Z}_{2} \wr H$ from a coarsely simply connected uniformly one-ended graph $Z$ (e.g. the Cayley graph of a finitely presented one-ended group like $\mathbb{Z}^{2}$), we follow the same idea. We fix a large $R \geq 0$ and we construct a 2-complex $X$ from $\mathbb{Z}_{2} \wr H$ by filling in with discs all the cycles lying in $H$-cosets and all the cycles of length $\leq R$. If $R$ is well-chosen, the image of any loop of $Z$ by $\rho$ is homotopically trivial in $X$, so $\rho$ lifts to the universal cover $\widetilde{X}$, giving a coarse embedding $\widetilde{\rho} : Z \to \widetilde{X}$. In order to understand the geometry of $\widetilde{X}$, observe that it coincides with the Cayley 2-complex of the truncated presentation

$$ \langle a, H \mid a^{2}=1, [a,hah^{-1}]=1 \ (h \in H) \rangle \text{ for some $S \subset H$ finite} $$

obtained from the presentation

$$ \langle a, H \mid a^{2}=1, [a,hah^{-1}]=1 \ (h \in H) \rangle $$

of $\mathbb{Z}_{2} \wr H$. However, the group $\mathbb{Z}_{2} \square _{S} H$ defined by the former presentation may no longer be a tree of copies of $H$, so it is not immediately obvious that the image of $\widetilde{\rho} : Z \to \mathbb{Z}_{2} \square _{S} H$ has to lie in the neighbourhood of an $H$-coset. Nevertheless, $\mathbb{Z}_{2} \square _{S} H$ turns out to have a remarkable algebraic structure: it splits as a semidirect product $C(\Gamma ) \rtimes H$ where $C(\Gamma )$ denotes the right-angled Coxeter group defined by $\Gamma := \mathrm{Cayl}(H,S)$. The key observation is that the well-known structure of $C(\Gamma )$ as a median graph (i.e. the one-skeleton of a CAT(0) cube complex) induces a wallspace structure on $\mathbb{Z}_{2} \square _{S} H$ with the property that every wall has a bounded image in $\mathbb{Z}_{2} \square _{S} H$ under the covering map $\mathbb{Z}_{2} \square _{S} H \twoheadrightarrow \mathbb{Z}_{2} \wr H$ (which coincides with the quotient map from an algebraic point of view). This implies that the image of $\widetilde{\rho}$ in $\mathbb{Z}_{2} \square _{S} H= C(\Gamma ) \rtimes H$ has to avoid the factor $C(\Gamma )$. Indeed, otherwise it would be possible to separate this image with a wall, and consequently to separate the image of $\rho$ with a bounded set, contradicting the assumption that $Z$ is one-ended. In other words, the image of $\widetilde{\rho}$ in $\mathbb{Z}_{2} \square _{S} H$ must lie in the neighbourhood of an $H$-coset, and we conclude that the image of $\rho$ in $\mathbb{Z}_{2} \wr H$ must lie in the neighbourhood of an $H$-coset, as desired.

The wallspace structure we define on $\mathbb{Z}_{2} \square _{S} H$ follows from a description of the Cayley graph of $\mathbb{Z}_{2} \square _{S} H$ in terms of pointed edges in the median graph associated to $C(\Gamma )$. Indeed, observe that an element of $C(\Gamma ) \rtimes H$ is given by a pair $(g,h)$ where $g \in C(\Gamma )$ can be thought of as a vertex in the median graph $\mathrm{Cayl}(C(\Gamma ),H)$ of $C(\Gamma )$ and where $h \in H$ can be thought of as a direction starting from $g$; in other words, $(g,h)$ naturally corresponds to the edge $(g,gh)$ of $\mathrm{Cayl}(C(\Gamma ),H)$ pointed at $g$.

However, this description is specific to the lamplighters $\mathbb{Z}_{2} \wr H$. When $\mathbb{Z}_{2}$ is replaced with a larger finite group, the right-angled Coxeter group $C(\Gamma )$ has to be replaced with a graph product of finite groups, and median geometry has to be replaced with quasi-median geometry. But the arguments can be adapted with no major modifications. When dealing with lamplighter graphs instead of lamplighter groups, there is no presentation to truncate, but thinking in terms of pointed cliques in quasi-median graphs (generalising our previous pointed edges in median graphs) remains possible. We develop this point of view in Sect. 5.2, and adapt the strategy described above in Sects. 5.3 and 5.4.

A word about rigidity

In view of the classification provided by Corollary 1.6, the natural problem to address next concerns rigidity: what can be said about the algebraic structure of a finitely generated group that is quasi-isometric to a lamplighter group $F \wr H$ where $F$ is a finite group and $H$ a finitely presented one-ended group? Of course, this is a much more difficult problem. Even for lamplighter groups over ℤ, a fully satisfying solution is not known. It is proved in [20, 21] that a group quasi-isometric to such a lamplighter group must act properly and cocompactly on some Diestel-Leader graph, a geometric rigidity which is already rich of information but which does not provide a clear description of the algebraic structure of the group. This problem is addressed in [10], which decomposes uniform lattices in Diestel-Leader graphs as cross-wired lamplighter groups, an algebraic structure reminiscent of the semidirect product decomposition of lamplighter groups. However, as mentioned there, several questions remain open. Despite the fact that we do not study quasi-isometric rigidity here, we emphasize that non-trivial information can be already extracted from our work. In order to keep the article of reasonable size, these results will be described in a forthcoming work.

2 Preliminaries

In this section, we collect some basic definitions and notations that will be used in the rest of the article.

Graphs

In this article, a graph $X$ is a set endowed with a symmetric and antireflective relation. An element of $X$ is a vertex. Two vertices in relations are adjacent, and the data of two adjacent vertices is an edge. In other words, from our perspective, edges are not geometric objects in the sense that they are not isometric copies of $[0,1]$. Thinking of paths as sequences of successively adjacent vertices, notions of distances and connectedness apply as usual.

As mentioned in the introduction, we are particularly interested in coarsely simply connected and uniformly one-ended graphs. We recall their definitions for the reader’s convenience.

Definition 2.1

A graph $X$ is uniformly one-ended if, for every $R \geq 0$, there exists $D \geq 0$ such that the complement in $X$ of every ball of radius $R$ has one connected component that is unbounded but all the other components have diameter $\leq D$.

Notice that locally finite (quasi-)transitive graphs are automatically uniformly one-ended whenever they are one-ended, since the complement of a ball then has finitely many components. This includes (Cayley graphs of) finitely generated groups.

Definition 2.2

A graph $X$ is coarsely simply connected if there exists some $R \geq 0$ such that the 2-complex obtained from $X$ by filling in with discs the cycles of lengths $\leq R$ is simply connected.

It is well-known that a finitely generated group is coarsely simply connected if and only if it admits a finite presentation. Thus, examples of coarsely simply connected uniformly one-ended graphs are given by finitely presented groups. They are the main examples we have in mind.

Lamplighter graphs

Recall from the introduction that, given an integer $n \geq 2$ and a graph $X$, the lamplighter graph $\mathcal{L}_{n}(X)$ is the graph

• whose vertices are the pairs $(c,x)$ with $c : V(X) \to \mathbb{Z}_{n}$ a finitely supported colouring (denoted by $c \in \mathbb{Z}_{n}^{(X)}$, where $\mathbb{Z}_{n}$ is the cyclic group of order $n$) and $x \in V(X)$ a vertex (thought of as an arrow pointing at $x$);

• and whose edges connect $(c_{1},x_{1})$ and $(c_{2},x_{2})$ either if $c_{1}=c_{2}$ and $x_{1}$, $x_{2}$ are adjacent, or if $x_{1}=x_{2}$ and $c_{1}$, $c_{2}$ differ only at this vertex.

Loosely speaking, moving a vertex in $\mathcal{L}_{n}(X)$ amounts to moving an arrow in $X$ that is able to modify a colouring of $X$ where it is. Notice that, given a non-trivial finite group $F$, a group $H$, and a generating set $S$, the Cayley graph $\mathrm{Cayl}(F \wr H,F \cup S)$ coincides with $\mathcal{L}_{|F|} ( \mathrm{Cayl}(H,S))$.

In the sequel, we shall use the following useful notation. Given a subset $A\subset X$, we denote by $\mathcal{L}(A)$ the subgroup $\bigoplus _{a\in A} \mathbb{Z}_{n}$ of $\bigoplus _{X} \mathbb{Z}_{n}$. In other words, $\mathcal{L}(A)$ is the collection of all colourings supported in $A$.

As a graph, $\mathcal{L}_{n}(X)$ has a canonical metric, i.e. the distance between any two vertices corresponds to the minimal length of a path between them (each edge having length one). However, it may be convenient to endow $\mathcal{L}_{n}(X)$ with another metric. These two metrics, referred to as the diligent and lazy metrics, are biLipschitz equivalent so choosing one instead of the other has no consequence on our study of the asymptotic geometry of lamplighter graphs. The convention we follow is that $\mathcal{L}_{n}(X)$ is by default endowed with its graph metric, and the use of the diligent metric will be always explicitly mentioned. Loosely speaking, in order to go from $(c_{1},p_{1})$ to $(c_{2},p_{2})$ in $\mathcal{L}_{n}(X)$ with respect to the lazy metric (i.e. the graph metric), the arrow moves from $p_{1}$ to $p_{2}$ in $X$ and stops at each point where $c_{1}$, $c_{2}$ differ in order to modify the colouring from the value of $c_{1}$ to the value of $c_{2}$; with respect to the diligent metric, the arrow passes through each point where $c_{1}$, $c_{2}$ differ but it does not need to stop in order to modify the colouring.

The lazy metric

We refer to the graph metric of $\mathcal{L}_{n}(X)$ as the lazy metric. Observe that the lazy distance between any two points $(c_{1},p_{1}),(c_{2},p_{2}) \in \mathcal{L}_{n}(X)$ coincides with

$$ d_{\mathrm{dil}}((c_{1},p_{1}),(c_{2},p_{2})) + | \mathrm{supp}(c_{1}-c_{2})| $$

where $d_{\mathrm{dil}}$ denotes the diligent metric. As a consequence, we have $d_{\mathrm{dil}} \leq d_{\mathrm{laz}} \leq 2 d_{\mathrm{dil}}$, so our two metrics are biLipschitz equivalent.

The diligent metric

The graph metric obtained from $\mathcal{L}_{n}(X)$ by adding an edge between any two vertices $(c_{1},p_{1})$, $(c_{2},p_{2})$ such that $p_{1}$, $p_{2}$ are adjacent in $X$ and such that $c_{1}$, $c_{2}$ may only differ at $p_{1}$ is referred to as the diligent metric. With respect to this metric, the distance between any two points $(c_{1},p_{1}),(c_{2},p_{2}) \in \mathcal{L}_{n}(X)$ coincides with the shortest length of a path in $X$ starting from $p_{1}$, visiting all the points where $c_{1}$, $c_{2}$ differ (i.e. all the points in $\mathrm{supp}(c_{1}-c_{2})$), and ending at $p_{2}$.

(For simplicity, here we use the convention that the length of a path reduced to a single point is one. Indeed, observe that, if $\mathrm{supp}(c_{1}-c_{2})=\{p_{1}\}= \{p_{2}\}$, then the distance between $(c_{1},p_{1})$ and $(c_{2},p_{2})$ is 1 while the shortest path starting from $p_{1}$, visiting all the points in $\mathrm{supp}(c_{1}-c_{2})$, and ending at $p_{2}$ is reduced to a single point, namely $p_{1}=p_{2}$.)

Notice that, given a non-trivial finite group $F$ and a group $H$ generating by some $S \subset H$, the diligent metric defined on $\mathrm{Cayl}(F\wr H, F \cup S)$ (through its identification with $\mathcal{L}_{|F|}(\mathrm{Cayl}(H,S))$) coincides with the word metric associated to the generating set $F \cdot (S \cup \{1\})$.

Leaves

The lamplighter graph $\mathcal{L}_{n}(X)$ contains natural copies of $X$, namely the subgraphs

$$ X(c):=\{(c,x) \mid x \in X\} \text{ where $c \in \mathbb{Z}_{n}^{(X)}$ is a fixed colouring.} $$

For convenience, we identify $X(0)$ with $X$. We refer to these subgraphs as the leaves of $\mathcal{L}_{n}(X)$. Observe that, in $\mathcal{L}_{n}(X)$, the leaves do not fellow-travel:

Fact 2.3

For every $K \geq 0$ and for any two distinct leaves $L_{1},L_{2} \subset \mathcal{L}_{n}(X)$, the intersection $L_{1}^{+K} \cap L_{2}^{+K}$ of the $K$-neighbourhoods of $L_{1}$, $L_{2}$ is bounded.

Proof

Fix two distinct colourings $c_{1},c_{2} \in \mathbb{Z}_{n}^{(X)}$ such that $L_{1}=X(c_{1})$ and $L_{2}=X(c_{2})$. If a vertex $(c,p)$ belongs to $L_{1}^{+K}$, then either $c=c_{1}$ or $c$, $c_{1}$ differ in $B(p,K)$; similarly, if $(c,p)$ belongs to $L_{2}^{+K}$ then either $c=c_{2}$ or $c$, $c_{2}$ differ in $B(p,K)$. Because $c_{1}$, $c_{2}$ are distinct, we have

$$ L_{1}^{+K} \cap L_{2}^{+K} \subset \{ (c,p) \in \mathcal{L}_{n}(X) \mid \{p\} \cup \mathrm{supp}(c-c_{1}) \subset \mathrm{supp}(c_{1}-c_{2})^{+K} \}. $$

The subset in the right-hand side being bounded, the desired conclusion follows. □

Finally, observe that $\mathcal{L}_{n}(X)$ naturally projects onto $X$ through $\pi _{X} : (c,p) \mapsto p$. Clearly, $\pi _{X}$ is 1-Lipschitz (with respect to the diligent and lazy metrics). Algebraically speaking, given a non-trivial finite group $F$ and a group $H$ generated by some $S \subset H$, the projection of $\mathrm{Cayl}(F \wr H,F \cup S)$ (when thought of as $\mathcal{L}_{|F|}(\mathrm{Cayl}(H,S))$) onto $\mathrm{Cayl}(H,S)$ as defined above coincides with the quotient map $F \wr H \twoheadrightarrow H$.

Coarse embeddings

A map $f : X \to Y$ between two metric spaces $X$ and $Y$ is a coarse embedding if there exist two functions $\rho _{1},\rho _{2} : [0,+ \infty ) \to [0,+ \infty )$ tending to infinity such that

$$ \rho _{1}(d(x,y)) \leq d(f(x),f(y)) \leq \rho _{2}(d(x,y))) \text{ for all $x,y \in X$.} $$

The functions $\rho _{1}$, $\rho _{2}$ are referred to as the parameters of $f$. A coarse embedding with affine parameters is a quasi-isometric embedding. More precisely, given $A>0$ and $B \geq 0$, a map $f : X \to Y$ is an $(A,B)$-quasi-isometric embedding if

$$ \frac{1}{A} \cdot d(x,y) - B \leq d(f(x),f(y)) \leq A \cdot d(x,y) + B \text{ for all $x,y \in X$}. $$

It is an $(A,B)$-quasi-isometry if in addition every point in $Y$ is within $B$ from $f(X)$. A biLipschitz equivalence is a bijective coarse embedding with linear parameters. Among discrete metric spaces (like graphs), a bijective quasi-isometry is automatically a biLipschitz equivalence.

We record the following statement for future use. In what follows, a covering map $\pi : A \to B$ of cellular complexes means a covering map between the underlying topological spaces, such that the cellular structure on $A$ is induced from that of $B$ via the covering map.

Lemma 2.4

Let $Z$ be a connected graph, $\pi : A \to B$ a covering map of cellular complexes, and $\eta : Z \to B^{(1)}$ a continuous map. Assume that $\eta (Z)$ is simply connected in $B$. Then $\eta$ lifts as $\widetilde{\eta} : Z \to A^{(1)}$ and

$$ d_{A}(\widetilde{\eta}(x),\widetilde{\eta}(y)) = d_{B}(\eta (x),\eta (y)) \textit{ for all vertices $x,y \in Z$} $$

where $d_{A}$, $d_{B}$ refer to the graph metrics in $A^{(1)}$, $B^{(1)}$. As a consequence, if $\eta$ is a coarse embedding then $\widetilde{\eta}$ is a coarse embedding with the same parameters.

Proof

Fix two vertices $x,y \in Z$. Because $\pi$ is 1-Lipschitz, we have

$$ d_{A}(\widetilde{\eta}(x),\widetilde{\eta}(y)) \geq d_{B}(\pi \circ \widetilde{\eta} (x), \pi \circ \widetilde{\eta}(y)) = d_{B}(\eta (x), \eta (y)). $$

Next, let $\zeta$ be a geodesic in $\eta (Z) \subset B^{(1)}$ from $\eta (x)$ to $\eta (y)$ and let $\widetilde{\zeta} \subset A$ denote the lift of $\zeta$ that starts from $\widetilde{\eta}(x)$. Observe that $\widetilde{\zeta}$ ends at $\widetilde{\eta}(y)$. Otherwise, by letting $\widetilde{\xi}$ be a path in $\widetilde{\eta}(Z)$ from $\widetilde{\eta}(x)$ to $\widetilde{\eta}(y)$, the concatenation of $\zeta$ and $\pi (\widetilde{\xi})$ would create a loop in $\eta (Z)$ that is not homotopically trivial in $B$. So $\widetilde{\zeta}$ indeed ends at $\widetilde{\eta}$, hence

$$ d_{A}(\widetilde{\eta}(x),\widetilde{\eta}(y)) \leq \mathrm{length}( \widetilde{\zeta})= \mathrm{length}(\zeta ) = d_{B}(\eta (x),\eta (y)). $$

This completes the proof of our lemma. □

Amenable graphs

Given a locally finite graph $X$, a Følner sequence is a sequence of finite subsets $(A_{n})$ such that $|\partial A_{n}|/ |A_{n}| \to 0$ as $n \to + \infty$, where $|\cdot |$ denotes the cardinality of the subset under consideration and where we denote by $\partial S$ the boundary of a finite subset $S \subset X$ (i.e. the set of vertices not in $S$ that are adjacent to vertices in $S$). A graph is amenable if it admits a Følner sequence. It is well-known that a finitely generated group is amenable if and only if its Cayley graphs (with respect to finite generating sets) are amenable in the above sense.

Scaling quasi-isometries

Let us record from [29] how to define maps that are “coarsely $\kappa$-to-one” (for some real number $\kappa >0$) and a few elementary properties satisfied by such maps. The concept of quasi-$\kappa$-to-one quasi-isometries will be central in Sect. 3.2, dedicated to aptolic quasi-isometries between lamplighters over amenable graphs.

Definition 2.5

Let $f:X\to Y$ be a proper map between two graphs $X$, $Y$ and let $\kappa >0$. Then $f$ is quasi-$\kappa$-to-one if there exists a constant $C>0$ such that

$$ \left | \kappa |A|- |f^{-1}(A)| \right |\leq C|\partial A| $$

for all finite subset $A\subset Y$.

Notice that, for every integer $n \geq 1$, an $n$-to-one map is quasi-$n$-to-one. The terminology used in Definition 2.5 is also justified by the fact that a quasi-isometry that is quasi-one-to-one lies at finite distance from a bijection. Proposition 2.9 below also gives alternative definitions of being quasi-$\kappa$-to-one when $\kappa$ is rational. The former observation is a straightforward consequence of a result of Whyte [47, Theorems A and C] (see also [14, Theorems 5.3 and 5.4]). We refer to [29, Proposition 4.1] for more details.

Proposition 2.6

Let $f:X_{1}\to X_{2}$ be a quasi-isometry between two graphs with bounded degree. Then $f$ is at bounded distance from a bijection if and only if it is quasi-one-to-one.

It is not difficult to show that, given a finitely generated group $G$ and a finite-index subgroup $H \leq G$, the inclusion $H \hookrightarrow G$ is quasi-$(1/[G:H])$-to-one. On the other hand, if $G$ is non-amenable, it follows from Theorem 1.13 that $H \hookrightarrow G$ is also quasi-one-to-one. Therefore, the property of being quasi-$\kappa$-to-one is not quite as informative in the non-amenable case. The next lemma, proved in [29, Lemma 3.5], shows that this phenomenon does not happen in the amenable case.

Lemma 2.7

Let $f : X \to Y$ be a proper map between two graphs. Assume that $X$ is amenable. If $f$ is both quasi-$\kappa _{1}$-to-one and quasi-$\kappa _{2}$-to-one for some $\kappa _{1},\kappa _{2}>0$, then $\kappa _{1}=\kappa _{2}$.

Our next statement, proved in [29, Proposition 3.6], shows how being quasi-$\kappa$-to-one is compatible with composition.

Proposition 2.8

Let $X$, $Y$, $Z$ be three connected graphs with bounded degree, $\kappa _{1},\kappa _{2}>0$ two real numbers, and $f,h:X\to Y$ and $g:Y\to Z$ three quasi-isometries.

• (i) If $f$, $h$ are at bounded distance and if $f$ is quasi-$\kappa _{1}$-to-one, then $h$ is also quasi-$\kappa _{1}$-to-one.

• (ii) If $f$ and $g$ are respectively quasi-$\kappa _{1}$-to-one and quasi-$\kappa _{2}$-to-one, then $g\circ f$ is quasi-$\kappa _{1} \kappa _{2}$-to-one.

• (iii) If $\bar{f}$ is a quasi-inverse of $f$ and if $f$ is quasi-$\kappa _{1}$-to-one, then $\bar{f}$ is quasi-$(1/\kappa _{1})$-to-one.

Finally, in case $\kappa$ is rational, we proved in [29, Proposition 4.2] the following equivalent formulations of Definition 2.5.

Proposition 2.9

Let $m,n \geq 1$ be natural integers and $f:X\to Y$ a quasi-isometry between two graphs with bounded degree. The following statements are equivalent:

• (i) $f$ is quasi-$(m/n)$-to-one;

• (ii) the map $\iota \circ f\circ \pi$ is at bounded distance from a bijection, where $\pi : X\times \mathbb{Z}_{n} \twoheadrightarrow X$ is the canonical embedding and $\iota : Y \hookrightarrow Y\times \mathbb{Z}_{m}$ the canonical projection.

• (iii) there exist a partition $\mathcal{P}_{X}$ (resp. $\mathcal{P}_{Y}$) of $X$ (resp. of $Y$) with uniformly bounded pieces of size $m$ (resp. $n$) and a bijection $\psi :\mathcal{P}_{X}\to \mathcal{P}_{Y}$ such that $f$ is at bounded distance from a map $g : X \to Y$ satisfying $g(P) \subset \psi (P)$ for every $P \in \mathcal{P}_{X}$.

A few facts

We conclude this preliminary section with a few elementary observations about graphs with bounded degree.

Fact 2.10

Let $X$ be a graph with bounded degree. Then $|A^{+K}| \leq N^{K} \cdot |A|$ for every finite subset $A \subset X$ and every constant $K \geq 0$, where $N \geq 3$ is a fixed integer larger than the maximal degree of a vertex in $X$.

Proof

Because every vertex in $X$ has at most $N$ neighbours, it follows that

$$ |A^{+K}| \leq \sum \limits _{i=0}^{K-1} N^{i} \cdot | A| \leq N^{K} \cdot |A| $$

as desired. □

Fact 2.11

Let $X$ be a graph with bounded degree. Then $|A^{+K} \backslash A | \leq N^{K} \cdot |\partial A|$ for every finite subset $A \subset X$ and every constant $K \geq 1$, where $N \geq 3$ is a fixed integer larger than the maximal degree of a vertex in $X$.

Proof

By noticing that $A^{+K} \backslash A \subset (\partial A)^{+(K-1)}$, the desired conclusion follows from Fact 2.10. □

Fact 2.12

Let $X$, $Y$ be two graphs with bounded degree, $\kappa >0$, and $f : X \to Y$ a quasi-isometry. There exists a constant $M \geq 0$ such that $|\partial f^{-1}(A)| \leq M \cdot |\partial A|$ for every finite subset $A \subset Y$.

Proof

Let $Q \geq 0$ be such that $f$ sends two adjacent vertices to two vertices at distance $\leq Q$; and let $P \geq 1$ denote the maximal cardinality of the preimage under $f$ of a point.

Now, fix a finite subset $A \subset Y$. By definition, if $x$ belongs to $\partial f^{-1}(A)$ then it does not belong to $f^{-1}(A)$ and it has a neighbour $y \in f^{-1}(A)$, so $f(x)$ does not belong to $A$ and it is within $Q$ from $f(y) \in A$, i.e. $f(x) \in A^{+Q} \backslash A$. In other words, we have proved that $\partial f^{-1}(A) \subset f^{-1} ( A^{+Q} \backslash A)$. Then

$$ |\partial f^{-1}(A)| \leq \left | f^{-1}(A^{+Q} \backslash A) \right | \leq P \left | A^{+Q} \backslash A \right | \leq PN^{Q} \cdot | \partial A| $$

where the last inequality is justified by Fact 2.11. □

3 Aptolic quasi-isometries

3.1 Generalities

Recall from the introduction that, given two integers $n,m \geq 2$ and two graphs $X$, $Y$, a quasi-isometry $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ is aptolic if it is of aptolic form and if it admits a quasi-inverse of aptolic form, i.e. there exist four maps $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$, $\alpha ' : \mathbb{Z}_{m}^{(Y)} \to \mathbb{Z}_{n}^{(X)}$, $\beta : X \to Y$ and $\beta ' : Y \to X$ such that

$$ q(c,p)= \left ( \alpha (c),\beta (p) \right ) \text{ for all $(c,p) \in \mathcal{L}_{n}(X)$} $$

and such that

$$ (c,p) \mapsto (\alpha '(c), \beta '(p)), \ (c,p) \in \mathcal{L}_{m}(Y) $$

is a quasi-inverse of $q$. In this section, we record a few elementary observations about aptolic quasi-isometries. Regarding the classification of lamplighter groups up to quasi-isometry, our main result states that, if there exists an aptolic quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$, then $n$ and $m$ must have the same prime divisors. See Proposition 3.4. For the remainder of §3, we endow every lamplighter graph with the diligent metric.

We begin by characterising aptolic quasi-isometries among maps of aptolic form.

Proposition 3.1

Let $n,m \geq 2$ be two integers, $X$, $Y$ two unbounded graphs with bounded degree, $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and $\beta : X \to Y$ two maps. Then

$$ q : \left \{ \textstyle\begin{array}{ccc} \mathcal{L}_{n}(X) & \to & \mathcal{L}_{m}(Y) \\ (c,p) & \mapsto & (\alpha (c),\beta (p)) \end{array}\displaystyle \right . $$

is an aptolic quasi-isometry if and only if the following conditions hold:

• (i) $\alpha$ is a bijection;

• (ii) $\beta$ is a quasi-isometry;

• (iii) there exists $Q \geq 0$ such that, for all colourings $c_{1},c_{2} \in \mathbb{Z}_{n}^{(X)}$, the Hausdorff distance between $\beta (\mathrm{supp}(c_{1}-c_{2}))$ and $\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2}))$ is at most $Q$.

If so, every aptolic quasi-inverse of $q$ is of the form

$$ (c,p) \mapsto \left ( \alpha ^{-1}(c), \bar{\beta}(p) \right ), \ (c,p) \in \mathcal{L}_{m}(Y) $$

where $\bar{\beta} : Y \to X$ is a quasi-inverse of $\beta$.

Proof

First, assume that $q$ is an aptolic quasi-isometry. Let $C,K \geq 0$ be two constants and $\bar{\alpha} : \mathbb{Z}_{m}^{(Y)}$, $\bar{\beta} : Y \to X$ two maps such that $q$ is a $(C,K)$-quasi-isometry, such that

$$ \bar{q} : (c,p) \mapsto (\bar{\alpha}(c), \bar{\beta}(p)), \ (c,p) \in \mathcal{L}_{m}(Y) $$

is a quasi-isometry, and such that $q \circ \bar{q}$, $\bar{q} \circ q$ are within $K$ from identities.

We begin by proving $(ii)$. Notice that, for all $a,b \in X$, we have

$$ \textstyle\begin{array}{lcl} d(\beta (a),\beta (b)) & = & d((\alpha (0),\beta (a)),(\alpha (0), \beta (b))) = d(q(0,a),q(0,b)) \\ \\ & \leq & C \cdot d((0,a),(0,b))+K = C \cdot d(a,b)+K, \end{array} $$

and we show similarly that

$$ d(\beta (a),\beta (b)) \geq \frac{1}{C} d(a,b) - K. $$

Thus, $\beta$ defines a $(C,K)$-quasi-isometric embedding. Next, notice that, for every $h \in Y$, there exists some $(c,p) \in \mathcal{L}_{n}(X)$ such that $d(q(c,p),(0,h)) \leq K$. Since

$$ d\left (\beta (p),h \right ) \leq d\left ((\alpha (c),\beta (p)),(0,h) \right ) = d \left ( q(c,p),(0,h) \right ) \leq K, $$

we conclude that $\beta$ is a quasi-isometry. Notice our arguments only use the fact that $q$ is a quasi-isometry. We record this assertion for future use.

Fact 3.2

Given two maps $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and $\beta : X \to Y$, if

$$ (c,p) \mapsto (\alpha (c), \beta (p)), \ (c,p) \in \mathcal{L}_{n}(X) $$

defines a quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$, then $\beta$ defines a quasi-isometry $X \to Y$.

Thus, we have proved $(ii)$. Observe that, by symmetry, we also know that $\bar{\beta}$ is a quasi-isometry.

Now, we want to prove $(i)$. Given $(c,p) \in \mathcal{L}_{m}(Y)$, we have

$$ d((\alpha \circ \bar{\alpha} (c), \beta \circ \bar{\beta}(p)), (c,p)) = d( q \circ \bar{q}(c,p), (c,p)) \leq K. $$

Therefore, we must have $d(\beta \circ \bar{\beta}(p),p) \leq K$ and $c, \alpha \circ \bar{\alpha}(c)$ may only differ in the ball $B(p,K)$. The former observation implies that $\beta \circ \bar{\beta}$ is within $K$ from the identity, and we deduce from the latter observation by letting $p$ go to infinity in $Y$ that $\alpha \circ \bar{\alpha}$ is the identity. By symmetry, we obtain similarly that $\bar{\beta} \circ \beta$ is within $K$ from the identity and that $\bar{\alpha} \circ \alpha$ is the identity. Consequently, $\alpha$ is a bijection and $\bar{\alpha}=\alpha ^{-1}$, proving $(i)$; also, $\bar{\beta}$ must be a quasi-inverse of $\beta$, proving the last assertion of our proposition.

Finally, we want to prove $(iii)$. So let $c_{1},c_{2} \in \mathbb{Z}_{n}^{(X)}$ be two colourings. Fix a sequence

$$ a_{1}=c_{1}, \ a_{2}, \ldots , \ a_{n-1}, \ a_{n}=c_{2} \in \mathbb{Z}_{n}^{(X)} $$

such that, for every $1 \leq i \leq n-1$, $a_{i}$ and $a_{i+1}$ differ at exactly one point $p_{i}$. Observe that, for every $1 \leq i \leq n-1$, we have

$$ \textstyle\begin{array}{lcl} d((\alpha (a_{i}),\beta (p_{i})), (\alpha (a_{i+1}),\beta (p_{i}))) & = & d( q(a_{i},p_{i}),q(a_{i+1},p_{i})) \\ \\ & \leq & C d( (a_{i},p_{i}), (a_{i+1},p_{i})) +K = C+K, \end{array} $$

so $\alpha (a_{i})$ and $\alpha (a_{i+1})$ may only differ in the ball $B(\beta (p_{i}),C+K)$. It follows that $\alpha (a_{1})=\alpha (c_{1})$ and $\alpha (a_{n})=\alpha (c_{2})$ may only differ in

$$ \bigcup \limits _{i=1}^{n-1} B(\beta (p_{i}),C+K) = \beta ( \{p_{1}, \ldots , p_{n-1} \})^{+C+K} = \beta (\mathrm{supp}(c_{1}-c_{2})^{+C+K}. $$

In other words, we have proved that $\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2}))$ lies in the $(C+K)$-neighbourhood of $\beta (\mathrm{supp}(c_{1}-c_{2}))$. The same argument applied to $\bar{q}$ and $\alpha (c_{1})$, $\alpha (c_{2})$ shows that $\mathrm{supp}(c_{1}-c_{2})$ lies in the $(C+K)$-neighbourhood of $\bar{\beta}(\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2})))$. So $\beta (\mathrm{supp}(c_{1}-c_{2}))$ must lie in the $(C(C+K)+K)$-neighbourhood of $\beta \circ \bar{\beta}(\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2})))$, the latter being contained in the $K$-neighbourhood of $\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2}))$. Thus, we know that, conversely, $\beta (\mathrm{supp}(c_{1}-c_{2}))$ lies in the $(C(C+K)+2K)$-neighbourhood of $\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2}))$. This concludes the proof of $(iii)$.

Conversely, assume that $(i)-(iii)$ hold and let us prove that $q$ is an aptolic quasi-isometry. Let $C,K \geq 0$ be such that $\beta$ is a $(C,K)$-quasi-isometry and such that there exists a $(C,K)$-quasi-isometry $\bar{\beta}$ with $\beta \circ \bar{\beta}$, $\bar{\beta} \circ \beta$ within $K$ from identities. Set

$$ \bar{q} : \left \{ \textstyle\begin{array}{ccc} \mathcal{L}_{m}(Y) & \to & \mathcal{L}_{n}(X) \\ (c,p) & \mapsto & \left ( \alpha ^{-1}(c) , \bar{\beta}(p) \right ) \end{array}\displaystyle \right ., $$

and observe that

$$ q \circ \bar{q} : (c,p) \mapsto (c, \beta \circ \bar{\beta}(p)) \text{ and } \bar{q} \circ q : (c,p) \mapsto (c, \bar{\beta}\circ \beta (p)) $$

are at distance $\leq K$ from identities.

Since $Y$ had bounded degree, then so does $\mathcal{L}_{m}(Y)$. This implies that there exists $L\geq 1$ such that there exists a path of length at most $L$ starting and ending at any vertex $x$, and visiting all vertices of $B(x,Q)$.

Let $(c_{1},p_{1}),(c_{2},p_{2}) \in \mathcal{L}_{n}(X)$ be two points. Fix a path $\zeta$ of minimal length that starts from $p_{1}$, visits all the points in $\mathrm{supp}(c_{1}-c_{2})$, and ends at $p_{2}$. Let $\xi \subset \mathcal{L}_{m}(Y)$ denote a concatenation of geodesics connecting any two consecutive points along $\beta (\zeta )$. Notice that $\xi$ has length $\leq (C+K) \mathrm{length}(\zeta )$ according to $(ii)$. By construction, $\xi$ starts from $\beta (p_{1})$, visits all the points in $\beta (\mathrm{supp}(c_{1}-c_{2}))$, and ends at $\beta (p_{2})$. Note that there exists a path $\eta$ of length $\leq L \cdot \mathrm{length}(\xi )$ that starts from $\beta (p_{1})$, visits all the points in the $Q$-neighbourhood of $\beta (\mathrm{supp}(c_{1}-c_{2}))$, and ends at $\beta (p_{2})$. Because $\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2}))$ lies in the $Q$-neighbourhood of $\beta (\mathrm{supp}(c_{1}-c_{2}))$ according to $(iii)$, it follows that

$$ \textstyle\begin{array}{lcl} d(q(c_{1},p_{1}),q(c_{2},p_{2})) & = & d((\alpha (c_{1}),\beta (p_{1})), (\alpha (c_{2}),\beta (p_{2}))) \\ \\ &\leq& \mathrm{length}(\eta ) \leq L \cdot \mathrm{length}(\xi ) \\ \\ & \leq & L(C+K) \cdot \mathrm{length}(\zeta ) = L(C+K) \cdot d((c_{1},p_{1}),(c_{2},p_{2})). \end{array} $$

Observe that $\bar{q}$ also satisfies $(i)-(iii)$. For $(i)$ and $(ii)$, it is clear. For $(iii)$, we know that, for all colourings $c_{1},c_{2} \in \mathbb{Z}_{m}^{(Y)}$, the Hausdorff distance between $\beta (\mathrm{supp}(\alpha ^{-1}(c_{1})-\alpha ^{-1}(c_{2})))$ and $\mathrm{supp}(c_{1}-c_{2})$ is at most $Q$. So the Hausdorff distance between $\bar{\beta} \circ \beta (\mathrm{supp}(\alpha ^{-1}(c_{1})-\alpha ^{-1}(c_{2})))$ and $\bar{\beta}(\mathrm{supp}(c_{1}-c_{2}))$ is at most $(C+K)Q$. But the Hausdorff distance between $\bar{\beta} \circ \beta (\mathrm{supp}(\alpha ^{-1}(c_{1})-\alpha ^{-1}(c_{2})))$ and $\mathrm{supp}(\alpha ^{-1}(c_{1})-\alpha ^{-1}(c_{2}))$ is at most $K$, so we conclude that the Hausdorff distance between $\bar{\beta}(\mathrm{supp}(c_{1}-c_{2}))$ and $\mathrm{supp}(\alpha ^{-1}(c_{1})-\alpha ^{-1}(c_{2}))$ is at most $(C+K)Q+K$, as desired. Therefore, by reproducing the previous argument, we show that

$$ d(\bar{q}(c_{1},p_{1}),\bar{q}(c_{2},p_{2})) \leq M (C+K) \cdot d((c_{1},p_{1}),(c_{2},p_{2})) $$

for all $(c_{1},p_{1}),(c_{2},p_{2}) \in \mathcal{L}_{m}(Y)$, where $M$ denotes the length of one path that visits all the points in a ball of radius $(C+K)Q+K$ in $\mathcal{L}_{n}(X)$ and that both starts and ends at the centre. We deduce from the previous two centred inequalities that

$$ \textstyle\begin{array}{lcl} d(q(c_{1},p_{1}),q(c_{2},p_{2})) & \geq & \displaystyle \frac{1}{M(C+K)} d( \bar{q} \circ q (c_{1},p_{1}), \bar{q}\circ q(c_{2},p_{2})) \\ \\ & \geq & \displaystyle \frac{1}{M(C+K)} d((c_{1},p_{1}),(c_{2},p_{2})) - \frac{2K}{M(C+K)} \end{array} $$

for all $(c_{1},p_{1}),(c_{2},p_{2}) \in \mathcal{L}_{n}(X)$; and that

$$ \textstyle\begin{array}{lcl} d(\bar{q}(c_{1},p_{1}), \bar{q}(c_{2},p_{2})) & \geq & \displaystyle \frac{1}{L(C+K)} d(q \circ \bar{q} (c_{1},p_{1}), q\circ \bar{q}(c_{2},p_{2})) \\ \\ & \geq & \displaystyle \frac{1}{L(C+K)} d((c_{1},p_{1}),(c_{2},p_{2})) - \frac{2K}{L(C+K)}. \end{array} $$

Thus, $q$ is a quasi-isometry with $\bar{q}$ as a quasi-inverse, proving that $q$ is an aptolic quasi-isometry. □

As an easy particular case, which can also be proved directly, we have:

Corollary 3.3

Let $n \geq 2$ be an integer and $X$, $Y$ two graphs with bounded degree. If $X$ and $Y$ are biLipschitz equivalent, then so are the lamplighter graphs $\mathcal{L}_{n}(X)$ and $\mathcal{L}_{n}(Y)$.

Proof

Fix a biLipschitz equivalence $\beta : X \to Y$ and define

$$ q : \left \{ \textstyle\begin{array}{ccc} \mathcal{L}_{n}(X) & \to & \mathcal{L}_{m}(Y) \\ (c,p) & \mapsto & ( c \circ \beta ^{-1}, \beta (p)) \end{array}\displaystyle \right .. $$

Notice that $\mathrm{supp}(c_{1} \circ \beta ^{-1}- c_{2} \circ \beta ^{-1}) = \beta ( \mathrm{supp}(c_{1}-c_{2}))$ for all colourings $c_{1}$, $c_{2}$. Then Proposition 3.1 applies and shows that $q$ is a quasi-isometry. □

Now, we are ready to state the main result of this section. The key point is that it imposes restrictions on the integers $n$, $m$ if there exists an aptolic quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$. Recall that given a subset of vertices $A$ of a graph $X$, we denote by $\mathcal{L}(A)=\mathbb{Z}_{n}^{(A)}$. If $A$ is finite, and if a finite subset of $\mathcal{L}(X)$ is a union of left cosets of $\mathcal{L}(A)$, then its cardinality is a multiple of $n^{|A|}$. This motivates the following proposition.

Proposition 3.4

Let $n,m \geq 2$ be two integers, $X$, $Y$ two unbounded graphs, and $q: \mathcal{L}_{n}(X)\to \mathcal{L}_{m}(Y)$ an aptolic quasi-isometry, i.e. there exist a bijection $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and a quasi-isometry $\beta : X \to Y$ such that $q(c,p)= (\alpha (c),\beta (p))$ for all $(c,p) \in \mathcal{L}_{n}(X)$. For every quasi-inverse $\bar{\beta}$ of $\beta$, there exists a constant $Q \geq 0$ such that:

• For all subset $A_{1}\subset X$ and number $Q' \geq Q$, $\alpha ^{-1}\left ( \mathcal{L}\left ( \beta (A_{1})^{+Q'} \right ) \right )$ is a union of cosets of $\mathcal{L}(A_{1})$; conversely, for all subset $A_{2}\subset Y$ and number $Q' \geq Q$, $\alpha \left ( \mathcal{L} \left ( \bar{\beta}(A_{2})^{+Q'} \right ) \right )$ is a union of cosets of $\mathcal{L}(A_{2})$.

As a consequence, $n$ and $m$ have the same prime divisors.

Our proof relies on the following two preliminary lemmas.

Lemma 3.5

Let $n,m \geq 2$, be two integers and $X$, $Y$ two graphs. Assume that we are given a constant $Q \geq 0$ and two maps $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and $\beta :X \to Y$ such that, for all colourings $a,b \in \mathbb{Z}_{n}^{(X)}$ that satisfy $\mathrm{supp}(a-b)\subset \{p\}$ for some $p \in X$, we have $\mathrm{supp}(\alpha (a)-\alpha (b))\subset B(\beta (p),Q)$. Then, for every subset $A\subset X$ and every colouring $c\in \mathbb{Z}_{n}^{(X)}$, we have

$$ \alpha (c+\mathcal{L}(A))\subset \alpha (c)+ \mathcal{L} \left ( \beta (A)^{+Q} \right ). $$

Proof

Clearly, it is enough to prove the inclusion above for all finite subsets in $A$, so we can assume without loss of generality that $A$ is finite. We argue by induction over the cardinality of $A$. The case $|A|=1$ is covered by the assumption of the lemma. Now, assume that our assertion holds for a given cardinality and for every colouring. Fix an $a\in A$ and observe that, given two colourings $c\in \mathcal{L}(X)$ and $c'\in c+\mathcal{L}(A)$, we have $c'\in c''+\mathcal{L}(\{a\})$ for some $c''\in c+\mathcal{L}(A \backslash \{a\})$ since $c+\mathcal{L}(A)=c+\mathcal{L}(A\backslash \{a\})+\mathcal{L}(\{a\})$. Applying the inductive assumption to $c''$, we deduce that $\alpha (c'')\in \alpha (c)+\mathcal{L}(\beta (A\backslash \{a\})^{+Q})$. And applying our assumption to $c''$ yields $\alpha (c')\in \alpha (c'')+\mathcal{L}(\{\beta (a)\}^{+Q})$. Hence

$$ \begin{aligned} \alpha (c')&\in \alpha (c)+\mathcal{L} \left ( \beta (A \backslash \{a \})^{+Q} \right ) +\mathcal{L} \left ( \{\beta (a)\}^{+Q} \right ) \\ &= \alpha (c)+\mathcal{L} \left ( \beta (A\backslash \{a)\})^{+Q} \cup \{\beta (a)\}^{+Q} \right ). \end{aligned} $$

And we conclude thanks to the general formula $(X \cup Y)^{+Q}=X^{+Q}\cup Y^{+Q}$. □

Lemma 3.6

Under the assumptions of Lemma 3.5, we have that, for every colouring $c\in \mathbb{Z}_{n}^{(X)}$, every subset $A \subset X$, and every $Q'\geq Q$, $\alpha ^{-1}(\alpha (c)+\mathcal{L}(\beta (A)^{+Q'}))$ is a union of cosets of $\mathcal{L}(A)$. In particular, its cardinality is a multiple of $m^{|A|}$.

Proof

We let $c'\in \alpha ^{-1}(\alpha (c)+\mathcal{L}(\beta (A)^{+Q'})$. We deduce from Lemma 3.5 that

$$ \alpha (c'+\mathcal{L}(A))\in \alpha (c')+ \mathcal{L} \left ( \beta (A)^{+Q} \right ) \subset \alpha (c)+\mathcal{L} \left ( \beta (A)^{+Q'} \right ). $$

In other words, $\alpha ^{-1}(\alpha (c)+\mathcal{L}(\beta (A)^{+Q}))$ is stable by multiplication by $\mathcal{L}(A)$, so the desired conclusion follows. □

Proof of Proposition 3.4

As a consequence of Proposition 3.1(iii), Lemmas 3.5 and 3.6 apply. The first assertion of our proposition follows from Lemma 3.6 applied to $c:= \alpha ^{-1}(0)$. Our second assertion is symmetric to the first one. Finally, the conclusion on the cardinalities follows from the fact that $\alpha$ is a bijection. □

As mentioned in the introduction, one of the main results of this article is that, given two integers $n,m \geq 2$ and two coarsely simply connected uniformly one-ended graphs $X$, $Y$, every quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ is at finite distance from an aptolic quasi-isometry. In the next example, we show how to construct (many) quasi-isometries that are not at finite distance from aptolic quasi-isometries as soon as we remove the assumption of being one-ended.

Example 3.7

Let $n \geq 2$ be an integer and $X$ a multi-ended graph. Fix a vertex $x_{0} \in X$ and a ball $B(x_{0},R)$ whose complement in $X$ contains at least two unbounded connected components, say $A,B \subset X$. Let $\delta$ denote the colouring taking the value 1 at $x_{0}$ and 0 elsewhere.

Proposition 3.8

The map $\Phi : \mathcal{L}_{n}(X) \to \mathcal{L}_{n}(X)$ defined by

$$ (c,x) \mapsto \left \{ \textstyle\begin{array}{cl} (c,x) & \textit{if $x \in A$ or $c_{|A} \neq 0$} \\ (c+\delta ,x) & \textit{if $x \notin A$ and $c_{|A}=0$} \end{array}\displaystyle \right . $$

is a surjective $(1,2R)$-quasi-isometry, i.e.

$$ d((c_{1},x_{1}),(c_{2},x_{2}))-2R \leq d(\Phi (c_{1},x_{1}), \Phi (c_{2},x_{2})) \leq d((c_{1},x_{1}),(c_{2},x_{2}))+2R $$

for all $(c_{1},x_{1}),(c_{2},x_{2}) \in \mathcal{L}_{n}(X)$, and it is not at finite distance from an aptolic quasi-isometry.

Indeed, fix two points $(c_{1},x_{1}),(c_{2},x_{2}) \in \mathcal{L}_{n}(X)$. Four cases can happen:

• If $x_{1} \in A$ or $c_{1|A} \neq 0$ and if $x_{2} \in A$ or $c_{2|A} \neq 0$, then $\Phi (c_{1},x_{1})=(c_{1},x_{1})$ and $\Phi (c_{2},x_{2})=(c_{2},x_{2})$, so there is nothing to prove.

• If $x_{1},x_{2} \notin A$ and $c_{1|A}, c_{2|A} = 0$, then

  $$ d(\Phi (c_{1},x_{1}),\Phi (c_{2},x_{2}))=d((c_{1}+\delta ,x_{1}),(c_{2}+ \delta ,x_{2}))=d((c_{1},x_{1}),(c_{2},x_{2})), $$

  which trivially implies our inequality.

• Assume that $x_{1} \in A$ or $c_{1|A} \neq 0$ and that $x_{2} \notin A$ and $c_{2|A} = 0$. Notice that $\Phi (c_{1},x_{1})=(c_{1},x_{1})$ and $\Phi (c_{2},x_{2})= (c_{2}+\delta ,x_{2})$. Let $\gamma$ be a path in $H$ starting at $x_{1}$, visiting all the points in $\mathrm{supp}(c_{1}-c_{2})$, ending at $x_{2}$, and whose length coincides with the distance between $(c_{1},x_{1})$ and $(c_{2},x_{2})$ in $H$. Observe that $\gamma$ ends at a point not in $A$, namely $x_{2}$, and that it intersects $A$, because either $x_{1} \in A$ or $c_{1}$, $c_{2}$ differ at a point in $A$. Therefore, $\gamma$ crosses the ball $B(x_{0},R)$, and we can add to $\gamma$ a loop of length $\leq 2R$ passing through $x_{0}$. If we denote by $\gamma '$ the path thus obtained, we deduce that

  $$ \textstyle\begin{array}{lcl} d(\Phi (c_{1},x_{1}),\Phi (c_{2},x_{2}))& = & d((c_{1}+\delta ,x_{1}),(c_{2},x_{2})) \leq \mathrm{length}(\gamma ') \\ \\ & \leq & \mathrm{length}(\gamma )+2R = d((c_{1},x_{1}),(c_{2},x_{2}))+2R. \end{array} $$

  Similarly, one shows that

  $$ d((c_{1},x_{1}),(c_{2},x_{2}))=d((c_{1}+\delta - \delta ,x_{1}),(c_{2},x_{2})) \leq d((c_{1}+\delta ,x_{1}),(c_{2},x_{2}))+2R $$

  as desired.

• If $x_{2} \in A$ or $c_{2|A} \neq 0$ and if $x_{1} \notin A$ and $c_{1|A} = 0$, then the configuration is symmetric the previous one.

Thus, we have proved that $\Phi$ is a quasi-isometry. Now, we verify that $\Phi$ is not at finite distance from an aptolic quasi-isometry. Indeed, let $\Psi : (c,x) \mapsto (\alpha (c),\beta (x))$ be an aptolic quasi-isometry potentially at finite distance from $\Phi$, where $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{n}^{(X)}$ and $\beta : X \to X$ are two maps. Clearly, if $\beta$ is not at finite distance from the identity, then the distance between $\Phi$ and $\Psi$ is not finite, so from now on we assume that $\beta = \mathrm{Id}_{X}$. Fix two sequences $(a_{k})$ and $(b_{k})$, respectively in $A$ and $B$, that goes to infinity. If $\Phi$ and $\Psi$ are at finite distance, say $C$, then

$$ \left \{ \textstyle\begin{array}{l} C \geq d(\Phi (0,b_{k}),\Psi (0,b_{k})) = d((\delta ,b_{k}),(\alpha (0),b_{k})) \\ C \geq d(\Phi (0,a_{k}),\Psi (0,a_{k})) = d((0,a_{k}),(\alpha (0),a_{k})) \end{array}\displaystyle \right . $$

for every $k \geq 0$. But the first inequality implies that $\alpha (0)=\delta$ while the second inequality implies that $\alpha (0)=0$, a contradiction. Thus, our quasi-isometry $\Phi$ cannot be at finite distance from an aptolic quasi-isometry.

3.2 Lamplighters over amenable groups

We saw in Sect. 3.1 that, if there exists an aptolic quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$, then $n$ and $m$ must have the same prime divisors. In this section, our goal is to show that, under the additional assumption that $X$ is amenable, this observation can be strengthened. Namely:

Theorem 3.9

Let $n,m \geq 2$ be two integers, $X$, $Y$ two unbounded graphs, and $q: \mathcal{L}_{n}(X)\to \mathcal{L}_{m}(Y)$ an aptolic quasi-isometry, i.e. there exist a bijection $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and a quasi-isometry $\beta : X \to Y$ such that $q(c,p)= (\alpha (c),\beta (p))$ for all $(c,p) \in \mathcal{L}_{n}(X)$. If $X$ is amenable, then there exist integers $k,r,s \geq 1$ satisfying $n=k^{r}$ and $m=k^{s}$. Moreover, $\beta$ (and a fortiori $q$) is quasi-$(s/r)$-to-one.

The last assertion of our theorem relies on the following observation:

Lemma 3.10

Let $n,m \geq 2$ be two integers, $X$, $Y$ two graphs, and $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ an aptolic quasi-isometry, i.e. there exist a bijection $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and a quasi-isometry $\beta : X \to Y$ such that $q(c,p)= (\alpha (c),\beta (p))$ for every $(c,p) \in \mathcal{L}_{n}(X)$. If $\beta$ is quasi-$\kappa$-to-one for some $\kappa >0$, then so is $q$.

Proof

Let $A \subset \mathcal{L}_{m}(Y)$ be a finite subset. Let $\mathscr{C}$ denote the set of colourings appearing as first coordinates of elements in $A$, and, for every $c \in \mathscr{C}$, let $A_{c} \subset A$ denote the subset of the elements having $c$ as first coordinate. Notice that

$$ |A|= \sum \limits _{c \in \mathscr{C}} |A_{c}| \text{ and } |q^{-1}(A)| = \sum \limits _{c \in \mathscr{C}} |q^{-1}(A_{c})| = \sum \limits _{c \in \mathscr{C}} | \beta ^{-1}(B_{c})| $$

where $B_{c}$ denotes the projection of $A_{c}$ onto $Y$. Because $\beta$ is quasi-$\kappa$-to-one, we have

$$ \begin{aligned} \left | \kappa |A| - |q^{-1}(A)| \right | &\leq \sum \limits _{c \in \mathscr{C}} \left | \kappa |A_{c}| - |q^{-1}(A_{c})| \right | = \sum \limits _{c \in \mathscr{C}} \left | \kappa |B_{c}| - |q^{-1}(B_{c})| \right | \\ &\leq \sum \limits _{c \in \mathscr{C}} C \cdot |\partial B_{c}| \end{aligned} $$

for some constant $C\geq 0$ that does not depend on $A$. Because $\partial A$ contains the disjoint union $\bigsqcup _{c \in \mathscr{C}} \{c\} \times \partial B_{c}$, we have

$$ \left | \kappa |A| - |q^{-1}(A)| \right | \leq C |\partial A|, $$

proving that $q$ is quasi-$\kappa$-to-one. □

Proof of Theorem 3.9

Let $C,K \geq 0$ be such that $\beta$ is a $(C,K)$-quasi-isometry admitting a quasi-inverse $\bar{\beta}$ that is also a $(C,K)$-quasi-isometry with $\bar{\beta} \circ \beta$, $\beta \circ \bar{\beta}$ within $K$ from identities. Up to increasing $K$, we assume that $K$ is larger than the constant $Q$ given by Proposition 3.4.

Claim 3.11

Fix a prime $p$ and let $p_{1}$ (resp. $p_{2}$) denote the $p$-valuation of $n$ (resp. $m$). There exists a constant $M \geq 1$ such that

$$ \left | |A| - \frac{p_{2}}{p_{1}} | \beta (A)^{+K}| \right | \leq M \cdot | \partial A | $$

for all finite $A \subset X$.

In order to shorten the notation, we set $B:= \bar{\beta}\left ( \beta (A)^{+K} \right )^{+K}$. Observe that

$$ A \subset B \subset A^{+(C+3)K}. $$

The first inclusion is justified by the fact that, for every $a \in A$, we have $d(a, \bar{\beta}(\beta (a))) \leq K$ with $\bar{\beta}(\beta (a)) \in B$. The second inclusion is justified by the fact that, for every $x \in B$, there exist $y \in H_{1}$ and $a \in A$ such that $d(x,\bar{\beta}(y)) \leq K$ and $d(y,\beta (a)) \leq K$, hence

$$ \textstyle\begin{array}{lcl} d(x,a) & \leq & \displaystyle d \left ( x, \bar{\beta}(y) \right ) + d \left ( \bar{\beta}(y), \bar{\beta}(\beta (a)) \right ) + d\left ( \bar{\beta}(\beta (a)), a \right ) \\ \\ & \leq & K + C d(y,\beta (a)) +K +K \leq (C+3)K, \end{array} $$

i.e. $x \in A^{+(C+3)K}$ as desired. By combining these inclusions with Fact 2.11, we have

$$ |A| \leq |B| \leq |A| + N^{(C+3)K} \cdot |\partial A| $$

(1)

where $N \geq 3$ is a fixed integer larger than the maximal degree of a vertex in $X$. Next, notice that Proposition 3.4 implies that $\alpha ^{-1}(\mathcal{L}(\beta (A)^{+K}))$ is a union of cosets of $\mathcal{L}(A)$, so the cardinality of $\alpha ^{-1}(\mathcal{L}(\beta (A)^{+K}))$ must be a multiple of the cardinality of $\mathcal{L}(A)$, hence

$$ p^{p_{2} |\beta (A)^{+K}|} = E \cdot p^{p_{1} |A|} \text{ for some $E\geq 1$}. $$

(2)

Similarly, Proposition 3.4 implies that $\alpha (\mathcal{L}(B))$ is a union of cosets of $\mathcal{L}(\beta (A)^{+K})$, hence

$$ p^{p_{1} |B|} = F \cdot p^{p_{2} |\beta (A)^{+K}|} \text{ for some $F \geq 1$}. $$

(3)

It follows from (3) that

$$ |B| = \frac{1}{p_{1}} \log (F) + \frac{p_{2}}{p_{1}} \cdot \left | \beta (A)^{+K} \right |, $$

and the combination of (1), (2), and (3) implies that

$$ \log (F) \leq \log (EF) = p_{1} \left ( |B|-|A| \right ) \leq p_{1} N^{(C+3)K} \cdot |\partial A|, $$

so we have

$$ \frac{p_{2}}{p_{1}} \left | \beta (A)^{+K} \right | \leq |B| \leq \frac{p_{2}}{p_{1}} \left | \beta (A)^{+K} \right | + N^{(C+3)K} | \partial A|. $$

(4)

The combination of (1) and (4) leads to the desired inequalities, concluding the proof of Claim 3.11.

Now, let us prove that $n$ and $m$ are powers of a common number. Let $(A_{k})$ be a Følner sequence in $X$ and let $p_{1}$, $q_{1}$ (resp. $p_{2}$, $q_{2}$) denote the valuations of $n$ (resp. $m$) with respect to two primes. By applying Claim 3.11 to $p_{1}$, $p_{2}$, we find that $(|\beta (A_{k})^{+K}|/ |A_{k}|)$ converges to $p_{1}/p_{2}$ because $|\partial A_{k}|/ |A_{k}| \to 0$. Similarly, by applying Claim 3.11 to $q_{1}$, $q_{2}$, we find that $(|\beta (A_{k})^{+K}|/ |A_{k}|)$ converges to $q_{1}/q_{2}$. Thus, we have proved that there exists a rational $r/s$ such that, for every prime $p$, the quotient of the $p$-valuations of $n$ and $m$ is $r/s$, which implies that $n=k^{r}$ and $m=k^{s}$ for some $k \geq 1$. This proves the first assertion of our proposition.

From now on, we set $\kappa := s/r$. We want to prove that $\beta$ is quasi-$\kappa$-to-one. So fix a finite $A \subset Y$. By applying Claim 3.11 to $\beta ^{-1}(A)$, we get

$$ \left | \kappa |A^{+K}| - |\beta ^{-1}(A)| \right | = \left | \kappa | \beta (\beta ^{-1}(A))^{+K}| - |\beta ^{-1}(A)| \right | \leq M \cdot |\partial \beta ^{-1}(A)|. $$

According to Facts 2.11 and 2.12, there exists a constant $U \geq 0$ that does not depend on $A$ such that $|\partial \beta ^{-1}(A)| \leq U \cdot |\partial A|$ and $|A^{+K} \backslash A| \leq U \cdot |\partial A|$. Therefore,

$$ \left | \kappa |A| - |\beta ^{-1}(A)| \right | \leq \left | |A^{+K}|-|A| \right |+ \left | \kappa |A^{+K}| - |\beta ^{-1}(A)| \right | \leq U(M+1) \cdot |\partial A|. $$

Thus, we have proved that $\beta$ (and a fortiori $q$ according to Lemma 3.10) is quasi-$\kappa$-to-one, as desired. □

We conclude this section by noticing that the necessary condition provided by Theorem 3.9 for the existence of an aptolic quasi-isometry is also sufficient.

Proposition 3.12

Let $n,m \geq 2$ be two integers and $X$, $Y$ two graphs of bounded degree. Assume that $n=k^{r}$, $m=k^{s}$ for some $k,r,s \geq 1$ and that there exists a quasi-$(s/r)$-to-one quasi-isometry $X \to Y$. Then there exists an aptolic quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$.

Proof

According to Proposition 2.9, there exist a partition $\mathcal{P}$ (resp. $\mathcal{Q}$) of $X$ (resp. of $Y$) with uniformly bounded pieces of size $s$ (resp. $r$), a bijection $\psi :\mathcal{P}\to \mathcal{Q}$, and a quasi-isometry $\beta : X \to Y$ satisfying $\beta (P) \subset \psi (P)$ for every $P \in \mathcal{P}$. Fix a bijection $\sigma : \mathbb{Z}_{n}^{s} \to \mathbb{Z}_{m}^{r}$ satisfying $\sigma (0)=0$, and define a bijection $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ in such a way that $\alpha$ sends $\mathcal{L}(P)$ to $\mathcal{L}(\psi (P))$ through $\sigma$ for every $P \in \mathcal{P}$. We claim that

$$ q : (c,p) \mapsto (\alpha (c), \beta (p)), \ (c,p) \in \mathcal{L}_{n}(X) $$

is the quasi-isometry we are looking for. Let $(c_{1},p_{1}),(c_{2},p_{2}) \in \mathcal{L}_{n}(X)$ be two points. Let $P_{1}, \ldots , P_{\ell}$ denote the pieces of $\mathcal{P}$ containing points in $\mathrm{supp}(c_{1}-c_{2})$. By construction, $\psi (P_{1}),\ldots , \psi (P_{\ell})$ are the pieces of $\mathcal{Q}$ containing points in $\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2}))$. Because the pieces of $\mathcal{Q}$ are uniformly bounded, the Hausdorff distance between $\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2}))$ and $\psi (P_{1}) \cup \cdots \cup \psi (P_{\ell})$ is finite. We also know by construction that $\beta (\mathrm{supp}(c_{1}-c_{2}))$ lies in $\psi (P_{1}) \cup \cdots \cup \psi (P_{\ell})$ and has a point in each $\psi (P_{1}),\ldots , \psi (P_{\ell})$. Once again because the pieces of $\mathcal{Q}$ are uniformly bounded, we deduce that the Hausdorff dimension between $\mathrm{supp}(\alpha (c_{1})-\alpha (c_{2}))$ and $\beta (\mathrm{supp}(c_{1}-c_{2}))$ is bounded (by a bound that does not depend on $c_{1}$, $c_{2}$ but only on $\mathcal{P}$, $\mathcal{Q}$). We conclude from Proposition 3.1 that $q$ is an aptolic quasi-isometry, as desired. □

3.3 Lamplighters over non-amenable groups

We saw in the previous section that, if there exists an aptolic quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ where $X$, $Y$ are amenable, then $n$ and $m$ must be powers of a common number, strengthening the observation made in Sect. 3.1 that $n$ and $m$ must have the same prime divisors. In this section, our goal is to prove that this phenomenon is specific to the amenable case. More precisely, we prove Proposition 1.7 from the introduction, which we restate for convenience:

Proposition 3.13

Let $X$ be a graph of bounded degree and $n,m \geq 2$ two integers. If $X$ is non-amenable and if $n$, $m$ have the same prime divisors, then there exists an aptolic quasi-isometry between $\mathcal{L}_{n}(X)$ and $\mathcal{L}_{m}(X)$.

We emphasize that, in this statement, we do not assume that $X$ is coarsely simply connected or one-ended. For instance, $X$ can be a (bushy) tree.

Let us illustrate the construction we use in order to prove Proposition 3.13 by explaining why the lamplighter groups $\mathbb{Z}_{6} \wr \mathbb{F}_{2}$ and $\mathbb{Z}_{24} \wr \mathbb{F}_{2}$ are quasi-isometric, where the free group $\mathbb{F}_{2}$ will be thought of as the 4-regular tree. The first trick is to replace $\mathbb{Z}_{6} \wr \mathbb{F}_{2}$ (resp. $\mathbb{Z}_{24} \wr \mathbb{F}_{2}$) with $(\mathbb{Z}_{3} \oplus \mathbb{Z}_{2}) \wr \mathbb{F}_{2}$ (resp. $(\mathbb{Z}_{3} \oplus \mathbb{Z}_{2}^{3}) \wr \mathbb{F}_{2}$). Loosely speaking, we split each lamp into two half-lamps. Formally, each colouring $c : \mathbb{F}_{2} \to \mathbb{Z}_{6}$ (resp. $c : \mathbb{F}_{2} \to \mathbb{Z}_{24}$) becomes the sum $c_{1} \oplus c_{2}$ of two colourings $c_{1} : \mathbb{F}_{2} \to \mathbb{Z}_{3}$ and $c_{2} : \mathbb{F}_{2} \to \mathbb{Z}_{2}$ (resp. $c_{2} : \mathbb{F}_{2} \to \mathbb{Z}_{2}^{3}$). The second trick is to notice that, given a point at infinity $\xi \in \partial \mathbb{F}_{2}$, one can associate a colouring $\bar{c} : \mathbb{F}_{2} \to \mathbb{Z}_{2}^{3}$ to any colouring $c : \mathbb{F}_{2} \to \mathbb{Z}_{2}$ in the following way: for every point $p \in \mathbb{F}_{2}$, we define $\bar{c}(p) \in \mathbb{Z}_{2}^{3}$ thanks to the three digits in $\mathbb{Z}_{2}$ provided by the values taken by $c$ at the three points $p_{1},p_{2},p_{3} \in \mathbb{F}_{2}$ that are separated from $\xi$ by $p$, i.e. $\bar{c}(p):= (c(p_{1}),c(p_{2}),c(p_{3}))$. See Fig. 1. Now, we define a map $(\mathbb{Z}_{3} \oplus \mathbb{Z}_{6}) \wr \mathbb{F}_{2} \to ( \mathbb{Z}_{3} \oplus \mathbb{Z}_{2}^{3}) \wr \mathbb{F}_{2}$ by modifying the second halves of the lamps thanks to the previous operation and by leaving the arrow and the first halves as they were, i.e. $(c_{1} \oplus c_{2}, p) \mapsto (c_{1} \oplus \overline{c_{2}},p)$. This map turns out to define a quasi-isometry because the modifications on the colourings are local.

Fig. 1

A quasi-isometry $(\mathbb{Z}_{6} \oplus \mathbb{Z}_{2}) \wr \mathbb{F}_{2} \to ( \mathbb{Z}_{6}\oplus \mathbb{Z}_{2}^{3}) \wr \mathbb{F}_{2}$ (Color figure online)

The key point in the previous construction is that there exists a 3-to-1 map $\mathbb{F}_{2} \to \mathbb{F}_{2}$ that lies at finite distance from the identity, namely the map that sends every vertex to its neighbour towards $\xi$. We generalise this idea for arbitrary non-amenable groups.

Proof of Proposition 3.13

Given two integers $m \geq 1$, $n \geq 2$, and a prime $p$, we prove that $\mathcal{L}_{mp^{n}}(X)$ and $\mathcal{L}_{mp}(X)$ are quasi-isometric (through an aptolic quasi-isometry). This is sufficient to deduce our proposition.

First of all, observe that there exists an $n$-to-1 map $f : X \to X$ at finite distance from the identity, i.e. there exists some $C \geq 0$ such that $d(f(x),x) \leq C$ for every $x \in X$. Indeed, as a consequence of [47], the embedding $\iota : X \hookrightarrow X \oplus \mathbb{Z}_{n}$ is at finite distance, say $C$, from a bijection $g : X \to X \oplus \mathbb{Z}_{n}$. If $p : X \oplus \mathbb{Z}_{n} \to X$ denotes the canonical projection, then $f:=p \circ g$ is $n$-to-1. Moreover,

$$ d(f(x),x)=d(p(g(x)),p(\iota (x))) \leq d(g(x),\iota (x)) \leq C $$

for every $x \in X$. This proves our observation.

From now on, we fix an enumeration of $X$ and we identify $\mathbb{Z}_{mp}$ (resp. $\mathbb{Z}_{mp^{n}}$) with $\mathbb{Z}_{m} \oplus \mathbb{Z}_{p}$ (resp. $\mathbb{Z}_{m} \oplus \mathbb{Z}_{p}^{n}$). Given a finitely supported colouring $c : X \to \mathbb{Z}_{m} \oplus \mathbb{Z}_{p}$, we construct a new finitely supported colouring $\bar{c} : X \to \mathbb{Z}_{m} \oplus \mathbb{Z}_{p}^{n}$ as follows. For convenience, we denote by $\pi _{1}$ and $\pi _{2}$ the projections on the first and second coordinates in both $\mathbb{Z}_{m} \oplus \mathbb{Z}_{p}$ and $\mathbb{Z}_{m} \oplus \mathbb{Z}_{p}^{n}$. Given an $x \in X$,

• set $\pi _{1}(\bar{c}(x)):= \pi _{1}(c(x))$;

• enumerate $f^{-1}(x)$ as $\{x_{1}, \ldots , x_{k}\}$ by following the order of induced by our enumeration of $X$, and set $\pi _{2}(\bar{c}(x))=( \pi _{2}(c(x_{1})), \ldots , \pi _{2}(c(x_{k})))$.

We claim that

$$ \Phi : \left \{ \textstyle\begin{array}{ccc} \mathcal{L}_{mp}(X) & \to \mathcal{L}_{mp^{n}}(X) \\ (c,h) & \mapsto (\bar{c},h) \end{array}\displaystyle \right . $$

is a quasi-isometry. In the rest of the proof, our lamplighter graphs are endowed with diligent metrics. So fix two finitely supported colourings $c_{1},c_{2} : X \to \mathbb{Z}_{m} \oplus \mathbb{Z}_{p}$ and two points $k_{1},k_{2} \in X$.

Notice that, if $\bar{c}_{1}(x) \neq \bar{c}_{2}(x)$ for some $x \in X$, then either $\pi _{1}(c_{1}(x)) \neq \pi _{1}(c_{2}(x))$ (hence $x \in \mathrm{supp}(c_{1}-c_{2})$) or $\pi _{2}(c_{1}(x')) \neq \pi _{2}(c_{2}(x'))$ (hence $x' \in \mathrm{supp}(c_{1}-c_{2})$) for some $x' \in f^{-1}(x)$. Consequently,

$$ \mathrm{supp}(\bar{c}_{1}-\bar{c}_{2}) \subset \mathrm{supp}(c_{1}-c_{2}) \cup f( \mathrm{supp}(c_{1}-c_{2})). $$

(5)

Next, if $c_{1}(x) \neq c_{2}(x)$ for some $x \in X$, then either $\pi _{1}(c_{1}(x)) \neq \pi _{1}(c_{2}(x))$, hence $\bar{c}_{1}(x) \neq \bar{c}_{2}(x)$; or $\pi _{2}(c_{1}(x)) \neq \pi _{2}(c_{2}(x))$, hence $\bar{c}_{1}(f(x)) \neq \bar{c}_{2}(f(x))$. Consequently,

$$ \mathrm{supp}(c_{1}-c_{2}) \subset \mathrm{supp}(\bar{c}_{1}-\bar{c}_{2}) \cup f^{-1}(\mathrm{supp}(\bar{c}_{1}-\bar{c}_{2}) ). $$

(6)

Now, fix a path $\alpha$ in $X$ that starts from $k_{1}$, that visits all the points in $\mathrm{supp}(c_{1}-c_{2})$, that ends at $k_{2}$, and such that the length of $\alpha$ coincides with the distance between $(c_{1},k_{1})$ and $(c_{2},k_{2})$ in $\mathcal{L}_{mp}(X)$. For every point of $x \in \mathrm{supp}(c_{1}-c_{2})$, we add to $\alpha$ a loop of length $\leq 2C$ based at $x$ and passing through $f(x)$. Thus, we obtain a new path $\alpha '$ that visits all the points in $\mathrm{supp}(c_{1}-c_{2}) \cup f( \mathrm{supp}(c_{1}-c_{2}))$ and whose length is at most

$$ \mathrm{length}(\alpha )+2C |\mathrm{supp}(c_{1}-c_{2})| \leq (2C+1) \mathrm{length}(\alpha ). $$

It follows from the inclusion (5) that

$$ d((\bar{c}_{1},k_{1}),(\bar{c}_{2},k_{2})) \leq \mathrm{length}( \alpha ') \leq (2C+1) d((c_{1},k_{1}),(c_{2},k_{2})). $$

Next, fix a path $\beta$ in $X$ that starts from $k_{1}$, that visits all the points in $\mathrm{supp}(\bar{c}_{1}-\bar{c}_{2})$, that ends at $k_{2}$, and such that the length of $\beta$ coincides with the distance between $(\bar{c}_{1},k_{1})$ and $(\bar{c}_{2},k_{2})$ in $\mathcal{L}_{mp^{n}}(X)$. For every point $x \in \mathrm{supp}(\bar{c}_{1}-\bar{c}_{2})$ and every $x' \in f^{-1}(x)$, we add to $\beta$ a loop of length $\leq 2C$ based at $x$ and passing through $x'$. Thus, we obtain a new path $\beta '$ that visits all the points in $\mathrm{supp}(\bar{c}_{1}-\bar{c}_{2}) \cup f^{-1}(\mathrm{supp}( \bar{c}_{1}-\bar{c}_{2}) )$ and whose length is at most

$$ \mathrm{length}(\beta ) + 2nC |\mathrm{supp}(\bar{c}_{1}-\bar{c}_{2})| \leq (2nC+1) \mathrm{length}(\beta ). $$

It follows from the inclusion (6) that

$$ d((c_{1},k_{1}),(c_{2},k_{2})) \leq \mathrm{length}(\beta ') \leq (2nC+1) d((\bar{c}_{1},k_{1}),(\bar{c}_{2},k_{2})). $$

This concludes the proof that $\Phi$ is a quasi-isometry. □

4 Leaf-preserving quasi-isometries are aptolic

In this section, our goal is to characterise quasi-isometries that lie at finite distance from aptolic quasi-isometries. For this purpose, we introduce some terminology.

Definition 4.1

Let $n,m \geq 2$ be two integers, $X$, $Y$ two graphs, $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ a quasi-isometry, and $\bar{q} : \mathcal{L}_{m} (Y) \to \mathcal{L}_{n}(X)$ a quasi-inverse. Then $q$ is leaf-preserving if there exists some $C \geq 0$ such that $q$ (resp. $\bar{q}$) sends every leaf of $\mathcal{L}_{n}(X)$ (resp. of $\mathcal{L}_{m}(Y)$) at Hausdorff distance $\leq C$ from a leaf in $\mathcal{L}_{m}(Y)$ (resp. in $\mathcal{L}_{n}(X)$).

An alternative characterisation of leaf-preserving quasi-isometries is:

Lemma 4.2

Let $n,m \geq 2$ be two integers, $X$, $Y$ two graphs, and $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ a quasi-isometry. Then $q$ is leaf-preserving if and only if there exist a bijection $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and a constant $C \geq 0$ such that, for every $c \in \mathbb{Z}_{n}^{(X)}$, the Hausdorff distance between $q(X(c))$ and $Y(\alpha (c))$ is $\leq C$.

Proof

Fix a quasi-inverse $\bar{q}$ of $q$. If $q$ is leaf-preserving, then there exists some $C \geq 0$ such that, for every $c \in \mathbb{Z}_{n}^{(X)}$, there exists some $\alpha (c) \in \mathbb{Z}_{m}^{(Y)}$ such that the Hausdorff distance between $q(X(c))$ and $Y(\alpha (c))$ is $\leq C$. Similarly, for every $c \in \mathbb{Z}_{m}^{(Y)}$ there exists some $\bar{\alpha}(c) \in \mathbb{Z}_{n}^{(X)}$ such that the Hausdorff distance between $\bar{q}(Y(c))$ and $X(\bar{\alpha}(c))$ is $\leq C$ (up to increasing $C$ if necessary). Because the Hausdorff distance between two distinct leaves in $\mathcal{L}_{n}(X)$ and $\mathcal{L}_{m}(Y)$ is infinite, we must have $\alpha \circ \bar{\alpha} = \mathrm{id}$ and $\bar{\alpha} \circ \alpha = \mathrm{id}$. Thus, we have proved that there exists a bijection $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and a constant $C \geq 0$ such that, for every $c \in \mathbb{Z}_{n}^{(X)}$, the Hausdorff distance between $q(X(c))$ and $Y(\alpha (c))$ is $\leq C$. Conversely, if $q$ satisfies this property, then, for every $c_{1} \in \mathbb{Z}_{n}^{(X)}$ (resp. $c_{2} \in \mathbb{Z}_{m}^{(Y)}$), the Hausdorff distance between $q(X(c_{1}))$ and $Y(\alpha (c_{1}))$ (resp. $\bar{q}(Y(c_{2}))$ and $X(\alpha ^{-1}(c_{2}))$) is $\leq C$. In other words, $q$ is leaf-preserving. □

The objective of this section is to prove the following criterion:

Theorem 4.3

Let $n,m \geq 2$ be two integers, $X$, $Y$ two graphs of bounded degree, and $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ a quasi-isometry. The following statements are equivalent:

• (i) $q$ lies at finite distance from an aptolic quasi-isometry;

• (ii) $q$ is leaf-preserving, i.e. there exists a bijection $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and a constant $C \geq 0$ such that, for every $c \in \mathbb{Z}_{n}^{(X)}$, the Hausdorff distance between $q(X(c))$ and $Y(\alpha (c))$ is $\leq C$.

Moreover, if $(ii)$ holds, then the distance from $q$ to an aptolic quasi-isometry is bounded above by a constant that depends only on the integers $n$, $m$, the graphs $X$, $Y$, the parameters of $q$, and the constant $C$.

The theorem is essentially a straightforward consequence of the following statement. Roughly speaking, Proposition 4.4 shows that leaf-preserving quasi-isometries $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ preserve the projections onto $X$ and $Y$, and the proof below shows that the latter property amounts to being aptolic.

Proposition 4.4

Let $n,m \geq 2$ be two integers, $X$, $Y$ two graphs of bounded degree, and $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ a quasi-isometry. Let $\pi _{X}$ (resp. $\pi _{Y}$) denote the canonical projection $\mathcal{L}_{n}(X) \twoheadrightarrow X$ (resp. $\mathcal{L}_{m}(Y) \twoheadrightarrow Y$). Assume that

($q$ leaf-preserving):

there exists a bijection $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ and a constant $C \geq 0$ such that, for every $c \in \mathbb{Z}_{n}^{(X)}$, the Hausdorff distance between $q(X(c))$ and $Y(\alpha (c))$ is $\leq C$.

Then there exists a constant $Q \geq 0$ such that, for all $x,y \in \mathcal{L}_{n}(X)$, if $\pi _{X}(x)=\pi _{X}(y)$ then $d(\pi _{Y}(q(x)),\pi _{Y}(q(y))) \leq Q$. Moreover, $Q$ depends only on the integers $n$, $m$, the graphs $X$, $Y$, the parameters of $q$, and the constant $C$.

Proof of Theorem 4.3 assuming Proposition 4.4

The implication $(i) \Rightarrow (ii)$ is clear. Conversely, assume that $(ii)$ holds. Up to replacing $q$ with a new quasi-isometry at finite distance, we suppose without loss of generality that $q(c,p) \in Y(\alpha (c))$ for every $(c,p) \in \mathcal{L}_{n}(X)$. For every $p \in X$, let $\beta (p) \in Y$ be such that $q(0,p)=(\alpha (0),\beta (p))$; and set

$$ \tilde{q} : (c,p) \mapsto (\alpha (c),\beta (p)), \ (c,p) \in \mathcal{L}_{n}(X). $$

Observe that, for every $(c,p) \in \mathcal{L}_{n}(X)$, we have

$$ d(q(c,p),\tilde{q}(c,p)) = d \left ( \pi _{Y} (q(c,p)), \beta (p) \right ) = d \left ( \pi _{Y}(q(c,p)), \pi _{Y} (q(0,p)) \right ) \leq Q $$

where the first equality holds because $q(c,p)$, $\tilde{q}(c,p)$ both belong to the same leaf, namely $Y(\alpha (c) )$. Therefore, $\tilde{q}$ lies at finite distance from $q$. Since $\beta$ is a quasi-isometry according to Fact 3.2, it admits a quasi-inverse $\bar{\beta}$, and we can define

$$ Q : (c,p) \mapsto \left ( \alpha ^{-1}(c), \bar{\beta}(p) \right ), \ (c,p) \in \mathcal{L}_{m}(Y). $$

Clearly, $\tilde{q} \circ Q$ and $Q \circ \tilde{q}$ lie at finite distances from identities. Because $\tilde{q}$ is a quasi-isometry, this implies that $Q$ is also a quasi-isometry and a quasi-inverse of $\tilde{q}$. Thus, we have proved that $q$ is at finite distance from $\tilde{q}$, which is an aptolic quasi-isometry. □

The proof of Proposition 4.4, in Sect. 4.2, is rather technical but it relies on a simple idea. Therefore, for the reader’s convenience, we begin with a general discussion in the next section.

4.1 Warm up

Fix an integer $n \geq 2$ and a graph $X$. The geometric trick, in order to prove that two points in $\mathcal{L}_{n}(X)$ have close projections onto $X$, is that, if $X_{0}$, $X_{1}$, $X_{2}$, $X_{3}$ are four leaves such that $d(X_{i},X_{i+1})$ is very small and $d(X_{i},X_{i+2})$ very large ($i \in \mathbb{Z}_{4}$), then a point close to $X_{0}$ and $X_{1}$ must have its projection onto $X$ close to the projection of a point close to $X_{2}$ and $X_{3}$. A justification is the following. Consider a loop as illustrated by Fig. 2. In terms of colourings, travelling along the loop corresponds to the following:

• from $a$ to $a'$, one modifies the colouring of $a$ in a small region $A$ around the arrow;

• from $a'$ to $b$, one moves the arrow far away without modifying the colouring;

• from $b$ to $b'$, one modifies the colouring of $b$ in a small region $B$ around the arrow;

• from $b'$ to $c$, one moves the arrow far away without modifying the colouring;

• from $c$ to $c'$, one modifies the colouring of $c$ in a small region $C$ around the arrow;

• from $c'$ to $d$, one moves the arrow far away without modifying the colouring;

• from $d$ to $d'$, one modifies the colouring of $d$ in a small region $D$ around the arrow;

• from $d'$ to $a$, one moves the arrow far away without modifying the colouring.

Because we are following a loop, at some point we have to undo what we have done on the colouring. But the regions $A$ and $B$ are far away from each other, so we cannot undo anything between $a$ and $c$. Consequently, we have to undo in $C$ what we did in $A$ and undo in $D$ what we did in $B$. Since the regions $A$ and $C$ must be more or less the same, the projections onto $X$ must be approximatively the same between $a$, $a'$ and between $c$, $c'$.

Fig. 2

On the left, the points $a$ and $c$ have close projections; on the right, the points $x$ and $y$ have very different projections

However, considering paths of leaves of length 4 is not sufficient in order to be able to identify any two points with the same projection onto $X$. We want to generalise the previous observation to longer paths. However, a naive extension does not work, as shown by Fig. 2. The point is that the sequence $X_{0}$, $X_{1}$, $X_{2}$, $X_{3}$ corresponds to modifying the colouring in well separated regions $A$, $B$, $C$, but next the sequence $X_{3}$, $X_{4}$, $X_{5}$, $X_{0}$ undo what we did in a different order: $B$, $C$, and finally $A$. The fact that the points $x$, $y$ have very different projections onto $X$ comes from the fact that going from $X_{5}$ to $X_{0}$ corresponds to modifying the colouring inside the region $A$ while going from $X_{2}$ to $X_{3}$ corresponds to modifying the colouring inside a very different region, namely $C$. In order to avoid such a phenomenon, we require that the sequences $X_{0},\ldots , X_{3}$ and $X_{2},\ldots , X_{5}$ cannot be shortened when thought of as path of leaves. In the configuration illustrated by Fig. 2, notice that $X_{2}, \ldots , X_{5}$ can be shortened as $X_{2}$, $X_{5}$.

This is our fundamental tool in order to recognize two points with close projections onto $X$: Let $X_{0}, \ldots , X_{2s-1}$ be a sequence of leaves of $X$ such that $d(X_{i},X_{i+1})$ is very small for every $i \in \mathbb{Z}_{2s}$, such that $d(X_{i},X_{i+2})$ is very large for every $i \in \mathbb{Z}_{2s}$, and such that $X_{0}, \ldots , X_{s}$ and $X_{n-1}, \ldots , X_{2s-1}$ cannot be shortened. Then a point close to $X_{0}$ and $X_{2s}$ must have its projection onto $X$ close to the projection of a point close to $X_{s-1}$ and $X_{n}$. See Lemma 4.7 for a precise statement.

Conversely, it is however not true that, if two points $x,y \in \mathcal{L}_{n}(X)$ have the same projection onto $X$, then there exists such a cycle of leaves $X_{0}, \ldots , X_{2s-1}$ such that $x$ is close to $X_{0}$, $X_{2s-1}$ and $y$ close to $X_{s-1}$, $X_{s}$. But it is almost true. It turns out that there exists a constant $N \geq 1$ such that, for any two points $x,y \in \mathcal{L}_{n}(X)$ with the same projection onto $X$, we can find a sequence of points $x_{1}=x, \ x_{2}, \ldots , \ x_{N-1}, \ x_{N}=y$ such that, for every $1 \leq i \leq N-1$, there exists a cycle of leaves $X_{0}, \ldots , X_{2s-1}$ such that $x_{i}$ is close to $X_{0}$, $X_{2s-1}$ and $x_{i+1}$ close to $X_{s-1}$, $X_{s}$. See Lemma 4.13 for a precise statement.

Thus, we are able to recognize geometrically when two points in $\mathcal{L}_{n}(X)$ have close projections onto $X$.

4.2 Proof of the criterion

Until the proof of Proposition 4.4, we fix an integer $n \geq 2$ and a graph $X$ all of whose vertices have $\leq D$ neighbours. We denote by $\pi$ the canonical projection $\mathcal{L}_{n}(X) \twoheadrightarrow X$ and we endow the lamplighter graph with its diligent metric (see Sect. 2).

Definition 4.5

Let $A,A',B,B' \geq 0$ be four real numbers. An $(A,B)$-line of leaves (of length $k$) is a sequence $X(c_{1}), \ldots , X(c_{k})$ with $c_{1}, \ldots , c_{k} \in \mathbb{Z}_{n}^{(X)}$ such that:

• 1. $d(X(c_{i}),X(c_{i+1})) \leq A$ for every $1 \leq i \leq k-1$;

• 2. $d(X(c_{i}),X(c_{i+2})) \geq B$ for every $1 \leq i \leq k-2$.

It is $(A',B')$-geodesic if, for all $1 \leq i,j \leq k$, every $(A',B')$-line of leaves from $X(c_{i})$ to $X(c_{j})$ has length at least $|i-j|$.

Definition 4.6

Let $A,B \geq 0$ be two real numbers. An $(A,B)$-circle of leaves is a sequence $X(c_{0}), \ldots , X(c_{k-1})$ with $c_{1}, \ldots , c_{k} \in \mathbb{Z}_{n}^{(X)}$ such that:

• 1. $d(X(c_{i}),X(c_{i+1})) \leq A$ for every $i \in \mathbb{Z}_{k}$;

• 2. $d(X(c_{i}),X(c_{i+2})) \geq B$ for every $i \in \mathbb{Z}_{k}$.

Our proof of Proposition 4.4 relies on two preliminary lemmas. The first one is a necessary condition for two points of $\mathcal{L}_{n}(X)$ to have close projections onto $X$.

Lemma 4.7

Let $A,B,A',B' \geq 0$ be four real number satisfying

$$ A< B, \ A' \geq 2D^{3A} \textit{ and } B' \leq B-2D^{A}. $$

Let $X(c_{0}), \ldots , X(c_{2s-1})$ be an $(A,B)$-circle of leaves. Assume that both $X(c_{0}), \ldots , X(c_{s})$ and $X(c_{s-1}), \ldots , X(c_{2s-1})$ are $(A',B')$-geodesic, and fix a point $x$ (resp. $y$) within $A$ to both $X(c_{0})$ and $X(c_{2s-1})$ (resp. $X(c_{s-1})$ and $X(c_{s})$). Then $\pi (x)$ and $\pi (y)$ are within $14A$ in $X$.

Before proving Lemma 4.7, we record two elementary observations. The first one shows that two leaves indexed by two colourings that differ in a small region must be close to each other.

Fact 4.8

If two colourings $c_{1},c_{2} \in \mathbb{Z}_{n}^{(X)}$ only differ in a ball of radius $r$ in $X$, then the inequality $d(X(c_{1}),X(c_{2})) \leq 2 D^{r}$ holds in $\mathcal{L}_{n}(X)$.

Proof

Let $B(x,r)$ be a ball of radius $r$ in $X$ such that $c_{1}$ and $c_{2}$ only differ in $B(x,r)$. Fix a point $p \in B(x,r)$ and a maximal spanning tree $T \subset B(x,r)$. There exists a path $\gamma$ in $T$ that starts from $p$, that visits each vertex in $T$, and that passes through each edge at most twice. Let $q \in B(x,r)$ denote the final vertex of $\gamma$. Notice that

$$ \mathrm{length}(\gamma ) \leq 2 |E(T)| \leq 2|V(T)| = 2 | B(x,r)| \leq 2 D^{r}. $$

One can construct a path from $(c_{1},p)$ to $(c_{2},q)$ by moving the arrow from $p$ to $q$ following $\gamma$, and along the way we modify the colouring at each point where $c_{1}$ and $c_{2}$ differ from the value of $c_{1}$ to the value of $c_{2}$. The length of such a path coincides with $\mathrm{length}(\gamma )$. Thus, we have constructed a path of length $\leq 2D^{r}$ from a point of $X(c_{1})$ to a point of $X(c_{2})$, concluding the proof of our fact. □

Our second observation aims to show that, if a vertex is near to two close leaves, then it must also be close to any two vertices minimising the distance between the leaves.

Fact 4.9

Fix two distinct colourings $c_{1},c_{2} \in \mathbb{Z}_{n}^{(X)}$ and two points $a_{1} \in X(c_{1})$, $a_{2} \in X(c_{2})$. Then the inequality

$$ d(x,a_{1}),d(x,a_{2}) \leq 2(d(x,X(c_{1}))+d(x,X(c_{2}))) + d(a_{1},a_{2})+d(X(c_{1}),X(c_{2})) $$

holds for every $x \in \mathcal{L}_{n}(X)$.

Proof

Fix two points $(c_{1},p)$ and $(c_{2},q)$ such that $d(x,(c_{1},p))=d(x,X(c_{1}))$ and similarly $d(x,(c_{2},q))=d(x,X(c_{2}))$. Also, write $a_{i} = (c_{i},f_{i})$ for some $f_{i} \in X$, $i=1,2$. For convenience, set $\Delta := \mathrm{supp}(c_{2}-c_{1})$. The distance in $\mathcal{L}_{n}(X)$ between $(c_{1},p)$ and $(c_{2},q)$ coincides with the minimal length of a path in $X$ that starts from $p$, ends at $q$, and passes through all the points in $\Delta$. Consequently,

$$ \textstyle\begin{array}{lcl} d(x,X(c_{1}))+d(x,X(c_{2})) & \geq & d((c_{1},p),(c_{2},q)) \geq d(p, \Delta ) \\ \\ & \geq & d(p,f_{1})-d(f_{1},\Delta )- \mathrm{diam}(\Delta ). \end{array} $$

Observe that we also have $d(f_{1},\Delta ) \leq d((c_{1},f_{1}),(c_{2},f_{2}))=d(a_{1},a_{2})$, because the distance in $\mathcal{L}_{n}(X)$ between $(c_{1},f_{1})$ and $(c_{2},f_{2})$ is at least the length of a path in $X$ from $f_{1}$ to $f_{2}$ passing through all the points in $\Delta$; and $\mathrm{diam}(\Delta ) \leq d(X(c_{1}),X(c_{2}))$, because the distance in $\mathcal{L}_{n}(X)$ between $X(c_{1})$ and $X(c_{2})$ is at least the length of a path in $X$ visiting all the points in $\Delta$. Therefore,

$$ \textstyle\begin{array}{lcl} d(x,X(c_{1}))+d(x,X(c_{2})) & \geq & d(p,f_{1})- d(a_{1},a_{2})-d(X(c_{1}),X(c_{2})) \\ \\ & \geq & d(a_{1},(c_{1},p))-d(a_{1},a_{2})-d(X(c_{1}),X(c_{2})). \end{array} $$

Thus, we have proved that

$$ d(a_{1},(c_{1},p)) \leq d(x,X(c_{1}))+d(x,X(c_{2})) + d(a_{1},a_{2})+d(X(c_{1}),X(c_{2})). $$

We conclude that

$$ \textstyle\begin{array}{lcl} d(x,a_{1}) & \leq & d(x,(c_{1},p)) + d((c_{1},p),a_{1}) \\ \\ & \leq & 2d(x,X(c_{1}))+d(x,X(c_{2})) + d(a_{1},a_{2})+d(X(c_{1}),X(c_{2})) \end{array} $$

as desired. The inequality for $d(x,a_{2})$ is obtained similarly. □

Proof of Lemma 4.7

For every $i \in \mathbb{Z}_{2s}$, we fix two points $(c_{i},q_{i}) \in X(c_{i})$ and $(c_{i+1},p_{i+1}) \in X(c_{i+1})$ such that $d((c_{i},q_{i}),(c_{i+1},p_{i+1})) \leq A$; see Figure 3. This inequality implies that $d(q_{i},p_{i+1}) \leq A$ and that the colourings $c_{i}$ and $c_{i+1}$ may only differ in $B(q_{i},A)$, i.e. $c_{i+1}=c_{i}+ L_{i}$ where $L_{i}$ is supported in $B(q_{i},A)$.

Fig. 3

Configuration from the proof of Lemma 4.7

Claim 4.10

For all $0 \leq i < j \leq s-1$, we have $d(q_{i},q_{j}) > 2A$.

Assume towards a contradiction that there exist two indices $0 \leq i< j \leq s-1$ such that $d(q_{i},q_{j}) \leq 2A$. In the sequel, we use the notation $L[a,b]:= L_{a} + L_{a+1}+ \cdots + L_{b}$ for all indices $a \leq b$. Now, observe that $L_{i}+L_{j}$ is supported in the ball $B(q_{i},3A)$, hence

$$ d(X(c_{i}), X(c_{i}+L_{j}+L_{i})) \leq 2 D^{3A} $$

according to Fact 4.8; also, observe that

$$ \textstyle\begin{array}{l} d(X(c_{i}+L_{j}+L[i,k]),X(c_{i}+L_{j}+L[i,k+1])) \\ \hspace{2cm} \textstyle\begin{array}{cl} = & d(X(c_{i}+L[i,k]),X(c_{i}+L[i,k+1])) \\ = & d(X(c_{k}),X(c_{k+1})) \leq A \end{array}\displaystyle \end{array} $$

for every $i \leq k \leq j-1$; next that

$$ \textstyle\begin{array}{l} d(X(c_{i}),X(c_{i}+L_{j}+L_{i}+L_{i+1})) \\ \hspace{1cm} \textstyle\begin{array}{cl} \geq & d(X(c_{i}),X(c_{i}+L_{i}+L_{i+1}))\\ &{}- d(X(c_{i}+L_{i}+L_{i+1}),X(c_{i}+L_{j}+L_{i}+L_{i+1})) \\ \geq & d(X(c_{i}),X(c_{i+2}))- d(X(1), X(L_{j})) \geq B- 2 D^{A} \end{array}\displaystyle \end{array} $$

where the last inequality is justified by Fact 4.8; and finally that

$$ \textstyle\begin{array}{l} d(X(c_{i}+L_{j}+L[i,k]),X(c_{i}+L_{j}+L[i,k+2])) \\ \hspace{2cm} \textstyle\begin{array}{cl} = & d(X(c_{i}+L[i,k]),X(c_{i}+L[i,k+2])) \\ = & d(X(c_{k}),X(c_{k+2})) \geq B \end{array}\displaystyle \end{array} $$

for every $i \leq k \leq j-2$. It follows from all these inequalities that the sequence

$$ X(c_{i}), X(c_{i}+L_{j}+L_{i}), X(c_{i}+L_{j}+L_{i}+L_{i+1}), \ldots , X(c_{i}+L_{j}+ L_{i} + \cdots + L_{j-1}) $$

defines a $\left ( 2D^{3A},B-2D^{A} \right )$-line of leaves from $X(c_{i})$ to $X(c_{j+1})$ of length $j-i$. Since $A' \geq 2D^{3A}$ and $B' \leq B-2D^{A}$, we find a contradiction with the fact that $X(c_{0}), \ldots , X(c_{s})$ is $(A',B')$-geodesic. This completes the proof of Claim 4.10.

Claim 4.11

For all $s-1 \leq i < j \leq 2s-2$, we have $d(q_{i},q_{j}) > 2A$.

Claim 4.11 is symmetric to Claim 4.10 by replacing the sequence $X(c_{0}),\ldots , X(c_{s})$ with the sequence $X(c_{s-1}),\ldots , X(c_{2s-1})$.

Claim 4.12

For every $0 \leq i \leq s-1$, there exists some $s \leq j \leq 2s-1$ such that $d(q_{i},q_{j}) \leq 2A$.

Assume towards a contradiction that there exists some $0 \leq i \leq s-1$ such that, for every $s \leq j \leq 2s-1$, we have $d(q_{i},q_{j})> 2A$. We also know from Claim 4.10 that $d(q_{i},q_{j})>2A$ for every $0 \leq j \leq s-1$ distinct from $i$. Consequently,

$$ \mathrm{supp}(L_{i}) \cap \mathrm{supp}(L_{j}) \subset B(q_{i},A) \cap B(q_{j},A) = \emptyset $$

for every $0 \leq j \leq 2s-1$ distinct from $i$. Necessarily, $c_{0}$ and $c_{0}+L_{0}+ \cdots + L_{2s-1}$ must differ on $\mathrm{supp}(L_{i})$. But, by construction, $c_{0}+L_{0} + \cdots + L_{2s-1}=c_{0}$, hence $\mathrm{supp}(L_{i})= \emptyset$. In other words, we have proved that $c_{i}=c_{i-1}+L_{i}=c_{i-1}$. It follows that

$$ A \geq d(X(c_{i}),X(c_{i+1})) = d(X(c_{i-1}),X(c_{i+1})) \geq B, $$

a contradiction. This complete the proof of Claim 4.12.

We are finally ready to conclude the proof of our lemma. According to Claim 4.12, there exists some $s \leq i \leq 2s-1$ such that $d(q_{s-1},q_{i}) \leq 2A$. Claim 4.11 imposes that $i=2s-1$. So we have $d(q_{s-1},q_{2s-1}) \leq 2A$. We now apply Fact 4.9 with $c_{1}$ and $c_{2}$ being respectively $c_{2s-1}$ and $c_{0}$, and with $a_{1}$ and $a_{2}$ being respectively $(c_{2s-1},q_{2s-1})$ and $(c_{0},p_{0})$. Using that the quantities $d(x,X(c_{2s-1}))$, $d(x,X(c_{0}))$, $d((c_{2s-1},q_{2s-1}),(c_{0},p_{0}))$, and $d(X(c_{2s-1}),X(c_{0}))$ are $\leq A$, we deduce that $d(x,(c_{2s-1},q_{2s-1}))\leq 6A$. Similarly, we have $d(y,(c_{s-1},q_{s-1})) \leq 6A$. Therefore,

$$ \textstyle\begin{array}{lcl} d(\pi (x),\pi (y)) & \leq & d(\pi (x),q_{2s-1}) + d(q_{2s-1},q_{s-1}) + d(q_{s-1},\pi (y)) \\ \\ & \leq & d(x,(c_{2s-1},q_{2s-1})) +2A+ d(y,(c_{s-1},q_{s-1})) \leq 14A, \end{array} $$

concluding the proof of our lemma. □

We are now ready to prove our second preliminary lemma. It essentially states that the sufficient condition provided by Lemma 4.7 is almost necessary.

Lemma 4.13

Fix four integers $A,B,A',B' \geq 2$. There exists an integer $N \geq 1$ such that, for any two points $x,y \in \mathcal{L}_{n}(X)$ satisfying $\pi (x)= \pi (y)$ and $d(x,y) > 2 D^{\max (A',B)}$, there exist $(A,B)$-circles of leaves

$$ \textstyle\begin{array}{c} X(c_{0}^{1}), \ X(c_{1}^{1}), \ldots , \ X(c_{2s_{1}-1}^{1}) \\ X(c_{0}^{2}), \ X(c_{1}^{2}), \ldots , \ X(c_{2s_{2}-1}^{2}) \\ \vdots \\ X(c_{0}^{r}), \ X(c_{1}^{r}), \ldots , \ X(c_{2s_{r}-1}^{r}) \end{array} $$

such that $r \leq N$ and such that

• for every $1 \leq i \leq r$, $X(c_{0}^{i}), \ldots , C(c_{s_{i}}^{i})$ and $X(c_{s_{i}-1}^{i}), \ldots , X(c_{2s_{i}-1}^{i})$ are $(A',B')$-geodesic;

• for every $1 \leq i \leq r-1$, $X(c_{s_{i}-1}^{i})$, $X(c_{s_{i}}^{i})$, $X(c_{0}^{i+1})$, and $X(c_{2s_{i}-1}^{i+1})$ are pairwise at distance $\leq A$;

• $x$ is at distance $\leq A$ to both $X(c_{0}^{1})$ and $X(c_{2s_{1}-1}^{1})$;

• there exists a point $y'$ at distance $\leq 2D^{\max (A',B)}$ from $y$ and at distance $\leq A$ to both $X(c_{s_{r}}^{r})$ and $X(c_{s_{r}-1}^{r})$.

Moreover, $N$ depends only on $X$, $A'$ and $B$.

Proof

For convenience, set $C:=\max (A',B)$.

Claim 4.14

There exists a partition $X=\mathcal{X}_{1} \sqcup \cdots \sqcup \mathcal{X}_{N}$ such that, for every $1 \leq i \leq N$, any two points in $\mathcal{X}_{i}$ are at distance $> C$.

Let $\Xi$ be the graph whose vertex-set is $X$ and such that two elements in $X$ are linked by an edge if and only if they are at distance $\leq C$ in $X$. Because $X$ has bounded degree, so does $\Xi$, i.e. there exists some $N \geq 1$ such that every vertex of $\Xi$ has degree $\leq N-1$. Then one can colour the vertices of $\Xi$ with $N$ colours so that any two adjacent vertices have different colours. The partition of $X$ induced by this colouring is the partition we are looking for. Thus, Claim 4.14 is proved.

Now, fix two points $x,y \in \mathcal{L}_{n}(X)$ satisfying $\pi (x)= \pi (y)$. Without loss of generality, we assume that $x=(0,x_{0})$ for some $x_{0}\in X$. We can write $y$ as $(c,x_{0})$ for some colouring $c \in \mathbb{Z}_{n}^{(X)}$. Up to reindexing our partition $\mathcal{X}_{1} \sqcup \cdots \sqcup \mathcal{X}_{N}$, we can assume that there exists some $0 \leq r \leq N$, such that $\mathrm{supp}(c)$ contains at least one point in each $\mathcal{X}_{1}, \ldots , \mathcal{X}_{r}$ that is at distance $\geq C$ from $x_{0}$ and such that it contains no such point in $\mathcal{X}_{i}$ for $i\geq r+1$.

Notice that, if $r=0$, then $\mathrm{supp}(c) \subset B(x_{0},C)$, which implies that $d(x,y) \leq 2D^{C}$ according to Fact 4.8. This is a contradiction with our assumptions, so we must have $r \geq 1$.

We define inductively a sequence of colourings in $\mathbb{Z}_{n}^{(X)}$ as follows:

• Set $c_{0}=0$.

• For every $1 \leq i \leq r$, $c_{i}$ is a colouring that agrees with $c$ over $(\mathcal{X}_{1} \cup \cdots \cup \mathcal{X}_{i}) \backslash B(x_{0},C)$, that differs from $c_{i-1}$ at $x_{0}$, and that is zero elsewhere.

Notice that $c_{r}$ and $c$ may only disagree in $B(x_{0},C)$, hence $d(y,y') \leq 2D^{C}$ according to Fact 4.8 where $y':=(c_{r},x_{0})$.

To prove our lemma, it suffices to show that, given an index $0 \leq i \leq r-1$, there exists an $(A,B)$-circle of leaves $X(a_{0}),\ldots ,X( a_{2s-1})$ such that:

• $X(a_{0}),\ldots , X(a_{s})$ and $X(a_{s-1}), \ldots , X(a_{2s-1})$ are $(A',B')$-geodesic;

• $(c_{i},x_{0})$ is at distance $\leq A/2$ from both $X(a_{0})$ and $X(a_{2s-1})$;

• $(c_{i+1},x_{0})$ is at distance $\leq A/2$ from both $X(a_{s-1})$ and $X(a_{s})$.

By construction, we can write $c_{i+1}=c_{i}+ \delta (x_{0}) + \delta (x_{1}) + \cdots + \delta (x_{s-1})$ for some $x_{1}, \ldots , x_{s-1} \in X$ such that $x_{0},x_{1}, \ldots , x_{s-1}$ are pairwise at distance $>C$ in $X$, where $\delta (x_{0}),\delta (x_{1}),\ldots , \delta (x_{s-1})$ are respectively supported in $\{x_{0}\},\{x_{1}\},\ldots , \{x_{s-1}\}$. Set

• $a_{0}:= c_{i}+ \delta (x_{0})$ and $a_{j}:= c_{i}+\delta (x_{0})+\delta (x_{1})+ \cdots + \delta (x_{j})$ for every $1 \leq j \leq s-1$;

• $a_{s}:= c_{i}+\delta (x_{1})+ \cdots + \delta (x_{s-1})$ and $a_{s+j}:= c_{i} + \delta (x_{j+1})+ \cdots + \delta (x_{s-1})$ for every $1 \leq j \leq s-1$.

Notice that, for every $0 \leq j \leq 2s-1$, we have

$$ d(X(a_{j}),X(a_{j+1})) = d(X(a_{j}), X(a_{j} + \delta )) =d(X, X( \delta )) \leq 1 $$

where $\pm \delta \in \{\delta (x_{0}),\delta (x_{1}), \ldots , \delta (x_{s-1}) \}$. Also,

$$ \begin{aligned} d(X(a_{j}),X(a_{j+2}))&= d(X(a_{j}),X(a_{j}+\delta _{1}+\delta _{2})) \\ &= d(X,X(\delta _{1}+\delta _{2})) \geq d(g_{1},g_{2}) >C \end{aligned} $$

where $\pm \delta _{1}$, $\pm \delta _{2}$ are two colourings that belong to $\{\delta (x_{0}),\delta (x_{1}), \ldots , \delta (x_{s-1})\}$ and that are supported at two distinct points $g_{1},g_{2} \in \{x_{0},x_{1}, \ldots , x_{s-1}\}$. Consequently, our sequence $X(a_{0}), \ldots , X(a_{2s-1})$ defines an $(A,B)$-circle of leaves. Next, notice that $(c_{i},x_{0})$ is at distance $\leq 1$ from $X(a_{0})=X(c_{i}+\delta (x_{0}))$ and it belongs to $X(a_{2s-1})=X(c_{i})$. Also, $(c_{i+1},x_{0})$ belongs to $X(a_{s-1})=X(c_{i+1})$ and is at distance $\leq 1$ from $X(a_{s})=X(c_{i+1}-\delta (x_{0}))$.

Now, we claim that $X(a_{0}),\ldots , X(a_{s})$ is $(A',B')$-geodesic. So let $X(b_{0}),\ldots , X(b_{t})$ be an $(A',B')$-line of leaves from $X(a_{p})$ to $X(a_{q})$ for some $0 \leq p < q \leq s$. We need to show that $t \geq q-p-1$. For every $0 \leq j \leq t-1$, let $L_{j} \in \mathbb{Z}_{n}^{(X)}$ be such that $b_{j+1}=b_{j}+L_{j}$; we denote by $S_{j}$ the support of $L_{j}$. Notice that

$$ A' \geq d(X(b_{j}),X(b_{j+1})) \geq \mathrm{diam}(S_{j}) $$

for every $0 \leq j \leq t-1$. As a consequence, two distinct elements among $x_{0},x_{1}, \ldots , x_{s-1}$ cannot belong to the same $S_{j}$ since they are at least $C+1$ apart. But $\mathrm{supp}(a_{q}-a_{p}) \cap \{x_{0},x_{1}, \ldots , x_{s-1}\}$ has cardinality $q-p-1$ and

$$ \mathrm{supp}(a_{q}-a_{p}) = \mathrm{supp}(b_{t}-b_{0}) \subset \bigcup \limits _{j=0}^{t-1} S_{j}, $$

so we must have $t \geq p-q-1$, proving our claim.

One can prove similarly that $X(a_{s-1}), \ldots , X(a_{2s-1})$ is $(A',B')$-geodesic, concluding the proof of our lemma. □

Proof of Proposition 4.4

Without loss of generality, we assume that $q$ sends a leaf of $\mathcal{L}_{n}(X)$ to a leaf of $\mathcal{L}_{m}(Y)$. (Notice that, a priori, this increases the parameters of our quasi-isometry, but by an amount controlled by $C$.) Let $C_{1},C_{2} \geq 1$ be such that $q$ is a $(C_{1},C_{2})$-quasi-isometry, i.e.

$$ \frac{1}{C_{1}} d(x,y)-C_{2} \leq d(q(x),q(y)) \leq C_{1} d(x,y)+C_{2} $$

for all $x,y \in \mathcal{L}_{n}(X)$ and every point in $\mathcal{L}_{m}(Y)$ is at distance $\leq C_{2}$ from the image of $q$. Define a quasi-inverse $\bar{q} : \mathcal{L}_{m}(Y) \to \mathcal{L}_{n}(X)$ by fixing, for every $x \in \mathcal{L}_{m}(Y)$, a point $\bar{q}(x)$ in the preimage under $q$ of a point in $q(\mathcal{L}_{n}(X))$ within $C_{2}$ from $x$. A straightforward computation shows that $\bar{q}$ is a $(C_{1},3C_{1}C_{2})$-quasi-isometry. Another straightforward computation shows that:

Claim 4.15

For all integers $A,B,A',B' \geq 0$, $q$ sends an $(A,B)$-line of leaves that is $(A',B')$-geodesic to a $(C_{1}A+C_{2}, \frac{B}{C_{1}}-C_{2})$-line of leaves that is $(\frac{A'}{C_{1}}-3C_{2}, C_{1}B'+3C_{1}^{2}C_{2})$-geodesic.

Define integers $A_{1}$, $B_{1}$, $A_{1}'$, $B_{1}'$, $A_{2}$, $B_{2}$, $A_{2}'$, $B_{2}'$ such that:

• $A_{1},B_{1}' \geq 2$ and $A_{1}'=C_{1}(2+3C_{2})$;

• $B_{1}:= \max \left ( 1+C_{1}(C_{1}A_{1}+2C_{2}), C_{1}(2+C_{2}+2D^{C_{1}A_{1}+C_{2}}) \right )$;

• $A_{2}=C_{1}A_{1}+C_{2}$ and $B_{2}= \frac{B_{1}}{C_{1}}-C_{2}$;

• $A_{2}'= \max \left ( \frac{A_{1}'}{C_{1}}-3C_{2}, 2 D^{3A_{2}} \right )$;

• $B_{2}'= \min \left ( C_{1}B_{1}'+3C_{1}^{2}C_{2}, B_{2}-2D^{A_{2}} \right )$.

Also, set $C_{3}:=14NA_{2}+2C_{1}D^{\max (A_{1}',B_{1})}+C_{2}$ where $N$ is the constant given by Lemma 4.13 applied to $\mathcal{L}_{n}(X)$ with respect to $A_{1}$, $B_{1}$, $A_{1}'$, $B_{1}'$.

Fix two points $x,y \in \mathcal{L}_{n}(X)$ satisfying $\pi _{X}(x)=\pi _{X}(y)$. We want to prove that $d(\pi _{Y}(q(x)),\pi _{Y}(q(y))) \leq C_{3}$. If $d(x,y) \leq 2 D^{\max (A_{1}',B_{1})}$ then

$$ \begin{aligned} d(\pi _{Y}(q(x)),\pi _{Y}(q(y))) &\leq d(q(x),q(y)) \leq C_{1}d(x,y)+C_{2} \\ &\leq 2C_{1}D^{\max (A_{1}',B_{1})} +C_{2} \leq C_{3} \end{aligned} $$

and there is nothing to prove. Therefore, we assume from now on that $d(x,y) > 2 D^{\max (A_{1}',B_{1})}$. According to Lemma 4.13, there exist $(A_{1},B_{1})$-circles of leaves

$$ \textstyle\begin{array}{c} X(c_{0}^{1}), \ X(c_{1}^{1}), \ldots , \ X(c_{2s_{1}-1}^{1}) \\ X(c_{0}^{2}), \ X(c_{1}^{2}), \ldots , \ X(c_{2s_{2}-1}^{2}) \\ \vdots \\ X(c_{0}^{r}), \ X(c_{1}^{r}), \ldots , \ X(c_{2s_{r}-1}^{r}) \end{array} $$

such that $r \leq N$ and such that

• for every $1 \leq i \leq r$, $X(c_{0}^{i}), \ldots , X(c_{s_{i}}^{i})$ and $X(c_{s_{i}-1}^{i}), \ldots , X(c_{2s_{i}-1}^{i})$ are $(A_{1}',B_{1}')$-geodesic;

• for every $1 \leq i \leq r-1$, there exists a point $z_{i}$ in the $A_{1}$-neighbourhood of $X(c_{s_{i}-1}^{i})$, $X(c_{s_{i}}^{i})$, $X(c_{0}^{i+1})$ and $X(c_{2s_{i}-1}^{i+1})$;

• $x$ is at distance $\leq A_{1}$ to both $X(c_{0}^{1})$ and $X(c_{2s_{1}-1}^{1})$;

• there exists a point $y'$ at distance $\leq 2D^{\max (A_{1}',B_{1})}$ from $y$ and at distance $\leq A_{1}$ to both $X(c_{s_{r}}^{r})$ and $X(c_{s_{r}-1}^{r})$.

As a consequence of Claim 4.15,

$$ \textstyle\begin{array}{c} q(X(c_{0}^{1})), \ q(X(c_{1}^{1})), \ldots , \ q(X(c_{2s_{1}-1}^{1})) \\ q(X(c_{0}^{2})), \ q(X(c_{1}^{2})), \ldots , \ q(X(c_{2s_{2}-1}^{2})) \\ \vdots \\ q(X(c_{0}^{r})), \ q(X(c_{1}^{r})), \ldots , \ q(X(c_{2s_{r}-1}^{r})) \end{array} $$

is a sequence of $(A_{2},B_{2})$-circles of leaves such that

• for every $1 \leq i \leq r$, $q(X(c_{0}^{i})), \ldots , q(X(c_{s_{i}}^{i}))$ and $q(X(c_{s_{i}-1}^{i})), \ldots , q(X(c_{2s_{i}-1}^{i}))$ are $(A_{2}',B_{2}')$-geodesic;

• for every $1 \leq i \leq r-1$, $q(z_{i})$ lies in the $A_{2}$-neighbourhood of $q(X(c_{s_{i}-1}^{i}))$, $q(X(c_{s_{i}}^{i}))$, $q(X(c_{0}^{i+1}))$ and $q(X(c_{2s_{i}-1}^{i+1}))$;

• $q(x)$ is at distance $\leq A_{2}$ to both $q(X(c_{0}^{1}))$ and $q(X(c_{2s_{1}-1}^{1}))$;

• $q(y')$ at distance $\leq 2C_{1}D^{\max (A_{1}',B_{1})}+C_{2}$ from $q(y)$ and at distance $\leq A_{2}$ to both $q(X(c_{s_{r}}^{r}))$ and $q(X(c_{s_{r}-1}^{r}))$.

For convenience, set $z_{0}=x$ and $z_{r}=y'$. According to Lemma 4.7, we have

$$ d(\pi _{Y}(q(z_{i})),\pi _{Y}(q(z_{i+1}))) \leq 14 A_{2} \text{ for all } 0 \leq i \leq r-1. $$

Consequently,

$$ d(\pi _{Y}(q(x)),\pi _{Y}(q(y'))) = \sum \limits _{i=0}^{r-1} d(\pi _{Y}(q(z_{i})), \pi _{Y}(q(z_{i+1}))) \leq 14NA_{2}. $$

We conclude that

$$ \textstyle\begin{array}{lcl} d(\pi _{Y}(q(x)),\pi _{Y}(q(y))) & \leq & d(\pi _{Y}(q(x)),\pi _{Y}(q(y'))) + d(\pi _{Y}(q(y')),\pi _{Y}(q(y))) \\ \\ & \leq & 14NA_{2} + d(q(y'),q(y)) \\ \\ & \leq & 14NA_{2} + 2C_{1}D^{\max (A_{1}',B_{1})}+C_{2} \leq C_{3} \end{array} $$

as desired. □

5 An embedding theorem

This section is the core of the article, dedicated to the embedding theorem provided by the following statement:

Theorem 5.1

Let $X$ be a graph of bounded degree, $Z$ a graph that is uniformly one-ended and coarsely simply connected, and $n \geq 2$ an integer. For every coarse embedding $\rho : Z \to \mathcal{L}_{n}(X)$, there exists some $K \geq 0$ such that $\rho (Z)$ lies in the $K$-neighbourhood of a leaf in $\mathcal{L}_{n}(X)$. Moreover, $K$ depends only on $X$, $Z$, and the parameters of $\rho$.

The strategy of the proof of Theorem 5.1 was outlined in the introduction. We now proceed to a more detailed description of its various steps. We refer to Sect. 5.2 for precise definitions.

First of all, we introduce a new geometric interpretation of the lamplighter graph $\mathcal{L}_{n}(X)$. To every prism complex $W$, i.e. to every cellular complex obtained by gluing products of simplices along faces, we associated a complex of pointed simplices $\mathsf{PS}(W)$. Its vertices are pointed simplices in $W$ and two such pointed simplices are adjacent in $\mathsf{PS}(W)$ if one can pass from one to the other by some elementary moves, namely by either sliding the point inside the simplex or by rotating the simplex around its vertex. Then, we construct a prism complex $W(n,X)$ such that the lamplighter graph $\mathcal{L}_{n}(X)$ coincides with the one-skeleton of $\mathsf{PS}(W(n,X))$.

Next, we exhibit some rigid structure on $W(n,X)$: its universal cover $\widetilde{W}(n,X)$ is a quasi-median complex, which can be loosely thought of as the analogue of a CAT(0) cube complex where cubes are replaced with prisms. As a consequence of this structure, the complex $\mathsf{PS}(\widetilde{W}(n,X))$ inherits a structure of space with partitions [25] (i.e. the quasi-median analogue of a space with walls, in which walls delimit at least two components, possibly more).

The third step consists in showing that these walls satisfy nice properties, including the fundamental observation that the image of a wall in $\mathsf{PS}(\widetilde{W}(n,X))$ under the cover $\mathsf{PS}(\widetilde{W}(n,X)) \to \mathsf{PS}(W(n,X))$ induced by $\widetilde{W}(n,X) \to W(n,X)$ is bounded.

The combination of these three steps allows us to conclude as follows. We identify $\mathcal{L}_{n}(X)$ with the one-skeleton of $\mathsf{PS}(W(n,X))$. Using that $Z$ is coarsely simply connected, we show that the image of any loop in $Z$ by $\rho$ is homotopically trivial in $\mathsf{PS}(W(n,X))$. So $\rho$ lifts to a coarse embedding $\widetilde{\rho} : Z \to \mathsf{PS}(\widetilde{W}(n,X))$. A crucial property is that the walls in $\mathsf{PS}(\widetilde{W}(n,X))$ have bounded images in $\mathsf{PS}(W(n,X))$. Now since $Z$ is uniformly one-ended, we know that $\widetilde{\rho}(Z)$ cannot cross a wall of $\mathsf{PS}(\widetilde{W}(n,X))$ in an essential way. As a consequence, up to finite Hausdorff distance $\widetilde{\rho}(Z)$ is confined into a small region of $\mathsf{PS}(\widetilde{W}(n,X))$ that is not crossed by any wall. By construction, the image in $\mathsf{PS}(W(n,X))$ of such a region coincides with a leaf of $\mathcal{L}_{n}(X)$, allowing us to deduce the desired conclusion.

5.1 Preliminaries on quasi-median geometry

Our proof of the embedding theorem provided by Theorem 5.1 relies fundamentally on quasi-median geometry, i.e. the geometry of quasi-median graphs and complexes. In this section, we record all the definitions and properties that will be needed later.

Quasi-median graphs

There exist several equivalent definitions of quasi-median graphs. See for instance [2]. Below, we give the definition used in [25].

Definition 5.2

A connected graph $X$ is quasi-median if it does not contain $K_{4}^{-}$ and $K_{3,2}$ as induced subgraphs, and if it satisfies the following two conditions:

(triangle condition):

for every triplet of vertices $a, x,y \in X$, if $x$ and $y$ are adjacent and if $d(a,x)=d(a,y)$, then there exists a vertex $z \in X$, which is adjacent to both $x$ and $y$, satisfying $d(a,z)=d(a,x)-1$;

(quadrangle condition):

for every quadruplet of vertices $a,x,y,z \in X$, if $z$ is adjacent to both $x$ and $y$ and if $d(a,x)=d(a,y)=d(a,z)-1$, then there exists a vertex $w \in X$ that is adjacent to both $x$, $y$ and that satisfies $d(a,w)=d(a,z)-2$.

The graph $K_{3,2}$ is the bipartite complete graph, corresponding to two squares glued along two adjacent edges; and $K_{4}^{-}$ is the complete graph on four vertices minus an edge, corresponding to two triangles glued along an edge.

However, the definition of quasi-median graphs is only given for completeness. Similarly to median graphs (i.e. one-skeleta of CAT(0) cube complexes), the geometry of quasi-median graphs essentially reduces to the combinatorics of separating subspaces referred to as hyperplanes. Understanding this interaction between hyperplanes and geometry will be sufficient for us.

Definition 5.3

Let $X$ be a quasi-median graph. A hyperplane $J$ is an equivalence class of edges with respect to the transitive closure of the relation that identifies two edges in the same 3-cycle and two opposite edges in the same 4-cycle. The carrier of $J$, denoted by $N(J)$, is the subgraph generated by the edges in $J$. The connected components of the graph $X\backslash \backslash J$ obtained from $X$ by removing the interiors of the edges in $J$ are the sectors delimited by $J$; and the connected components of $N(J) \backslash \backslash J$ are the fibres of $J$. Two distinct hyperplanes $J_{1}$ and $J_{2}$ are transverse if $J_{2}$ contains an edge in $N(J_{1}) \backslash J_{1}$.

See Fig. 4 for a few examples. The role of hyperplanes is highlighted by the following statement. For a self-contained proof, we refer to [25, Propositions 2.15 and 2.30]; see also [27, Theorem 3.19] (or [28, Theorem 2.14] for proofs specific to the quasi-median graphs that will be considered in the next sections).

Fig. 4

Four hyperplanes in a quasi-median graphs. The orange hyperplane is transverse to the red and blue hyperplanes (Color figure online)

Theorem 5.4

Let $X$ be a quasi-median graph. The following assertions hold:

• (i) For every hyperplane $J$, $X\backslash \backslash J$ contains at least two connected components.

• (ii) Sectors, carriers, and fibres of hyperplanes are gated.

• (iii) A path is a geodesic if and only if it crosses each hyperplane at most once.

• (iv) The distance between two vertices coincides with the number of hyperplanes separating them.

Recall that a subgraph $Y \subset X$ is gated if, for every vertex $x \in X$, there exists a vertex $y \in Y$ such that, for every $z \in Y$, there exists a geodesic between $x$ and $z$ passing through $y$. We refer to the vertex $y$ as the projection of $x$ onto $Y$. The property of being gated can be thought of as a strong convexity condition. In particular, being gated implies being convex. Also, observe that the projection $y$ coincides with the unique vertex of $Y$ minimising the distance to $x$. Gated subgraphs also satisfy the Helly property, namely: a finite collection of pairwise intersecting gated subgraphs has a non-empty global intersection.

A useful statement, showing how hyperplanes interact with projections, is the following. We refer to [25, Lemma 2.34] or [27, Corollary 3.20] for a proof.

Lemma 5.5

Let $X$ be a quasi-median graph, $Y \subset X$ a gated subgraph, and $x \in X$ a vertex. If a hyperplane separates $x$ from its projection onto $Y$, then it separates $x$ from $Y$.

Quasi-median graphs are quite similar to median graphs. Essentially, the only differences are that edges are replaced with cliques (i.e. maximal complete subgraphs), that cubes are replaced with prisms (i.e. subgraphs which are products of cliques), and that cutting along a hyperplane may disconnected the graph into more than two connected components (possibly infinitely many).

We conclude this subsection with a few statements that will be needed later.

Lemma 5.6

Let $X$ be a quasi-median graph and $C_{1}$, $C_{2}$ two cliques. If $C_{1} \cap C_{2} \neq \emptyset$ and if the hyperplanes containing $C_{1}$ and $C_{2}$ are transverse, then $C_{1}$ and $C_{2}$ span a prism.

Proof

Fix a vertex $a \in C_{1} \cap C_{2}$ and let $J_{1}$, $J_{2}$ denote the hyperplanes containing respectively $C_{1}$, $C_{2}$. We begin by proving the following observation:

Claim 5.7

For all $b_{1} \in C_{1} \backslash \{a\}$ and $b_{2} \in C_{2} \backslash \{a\}$, the edges $[a,b_{1}]$ and $[a,b_{2}]$ span a square.

Let $F$ denote the fibre of $J_{2}$ that contains $b_{2}$ and let $c$ denote the projection of $b_{1}$ onto $F$. Observe that $[b_{1},a] \cup [a,b_{2}]$ is a geodesic as it crosses only two distinct hyperplanes (namely, $J_{1}$ and $J_{2}$). As a consequence, $b_{1}$ does not belong to $F$, since otherwise the convexity of $F$ would imply that $a \in [b_{1},a] \cup [a,b_{2}] \subset F$. On the other hand, we know that $d(b_{1},c) = d(b_{1},F) \leq d(b_{1},b_{2}) = 2$, so $d(b_{1},c) \in \{1,2\}$. If $d(b_{1},c)=2$ then we must have $c=b_{2}$, which is impossible according to Lemma 5.5 because $J_{1}$ separates $b_{1}$ from $b_{2}$ but not from $F$. Therefore, $d(b_{1},c)=1$; in other words, $c$ is adjacent to $b_{1}$. Because $J_{1}$ contains the edges $[b_{1},c]$, $[a,b_{2}]$ and does not separate $c$, $b_{2}$, necessarily the hyperplanes separating $c$ and $b_{2}$ must separate $a$ and $b_{1}$. In other words, $J_{2}$ is the only hyperplane separating $c$ and $b_{2}$, which implies that $c$ is also adjacent to $b_{2}$. We conclude that $[a,b_{1}]$ and $[a,b_{2}]$ span a square, namely $\{a,b_{1},b_{2},c\}$. This proves Claim 5.7.

For all $b_{1} \in C_{1} \backslash \{a\}$ and $b_{2} \in C_{2} \backslash \{a\}$, we denote by $c(b_{1},b_{2})$ the vertex of the square spanned by $[a,b_{1}]$ and $[a,b_{2}]$ opposite to $a$. Consider the map

$$ \Phi : \left \{ \textstyle\begin{array}{ccc} C_{1} \times C_{2} & \to & X \\ (x,y) & \mapsto & \left \{ \textstyle\begin{array}{cl} c(x,y) & \text{if $x \neq a$ and $y \neq a$} \\ x & \text{if $y=a$} \\ y & \text{if $x=a$} \end{array}\displaystyle \right . \end{array}\displaystyle \right .. $$

We claim that $\Phi$ is a graph embedding with an induced image, which will conclude the proof of our lemma since it will follow that $C_{1}$ and $C_{2}$ span the prism $\Phi (C_{1} \times C_{2})$.

So let $(x_{1},y_{1}),(x_{2},y_{2}) \in C_{1} \times C_{2}$ be two adjacent vertices. Up to symmetry, we assume without loss of generality that $x_{1}$, $x_{2}$ are adjacent in $C_{1}$ and that $y_{1}=y_{2}$ (from now on, we denote by $y$ this common vertex).

• If $y=a$, then $\Phi (x_{1},y)=x_{1}$ and $\Phi (x_{2},y)=x_{2}$ are adjacent in $X$.

• If $y \neq a$ and $x_{1}=a$, then $\Phi (x_{1},y)=y$ and $\Phi (x_{2},y)=c(x_{2},y)$ are adjacent.

• If $y \neq a$ and $x_{2}=a$, then $\Phi (x_{1},y)=c(x_{1},y)$ and $\Phi (x_{2},y)=y$ are adjacent.

• If $y,x_{1},x_{2} \neq a$, then $\Phi (x_{1},y)=c(x_{1},y)$ and $\Phi (x_{2},y)=c(x_{2},y)$ are adjacent since otherwise the two squares $\{a,x_{1},y,c(x_{1},y)\}$ and $\{a,x_{2},y,c(x_{2},y)\}$ would define an induced copy of $K_{3,2}$ in $X$.

Therefore, $\Phi$ sends an edge to an edge. Next, observe that $c : (C_{1} \backslash \{a\} ) \times (C_{2} \backslash \{a\} ) \to X$ is injective since otherwise $X$ would contain an induced copy of $K_{3,2}$. Consequently, $\Phi$ is also injective. Finally, notice that, if $\Phi (C_{1} \times C_{2})$ contains an edge that does not come from $C_{1} \times C_{2}$, then a square in $C_{1} \times C_{2}$ would have a diagonal in $X$, implying that $J_{1}=J_{2}$, a contradiction. This concludes the proof of our lemma. □

For our next lemma, we need the following definition. The cubical dimension of a quasi-median graph $X$, denoted by $\dim _{\square}(X)$, is the maximal size of a collection of pairwise transverse hyperplanes. Although this observation will not be used in the sequel, we know from [25, Proposition 2.79] that the cubical dimension coincides with the maximal number of factors of a prism in $X$.

Lemma 5.8

Let $X$ be a quasi-median graph and $x,y \in X$ two vertices. Let $N$ denote the maximal number of pairwise non-transverse hyperplanes separating $x$ and $y$. Then $d(x,y) \leq \dim _{\square}(X) \cdot N$.

Proof

Let $\mathscr{S}$ denote the collection of the sectors delimited by hyperplanes separating $x$, $y$ that contain $x$, partially ordered by the inclusion. Let $\mathscr{S}= \mathscr{S}_{1} \sqcup \cdots \sqcup \mathscr{S}_{r}$ be a partition with $r$ minimal such that each $\mathscr{S}_{i}$ is totally ordered by the inclusion. Observe that a subcollection of sectors that are pairwise incomparable with respect to the inclusion corresponds to a collection of pairwise transverse hyperplanes, so it must have cardinality $\leq \dim _{\square}(X)$. It follows from Dilworth’s theorem that $r \leq \dim _{\square}(X)$. We conclude that

$$ d(x,y) = | \mathscr{S}| = | \mathscr{S}_{1}| + \cdots + | \mathscr{S}_{r}| \leq \dim _{\square}(X) \cdot N, $$

as desired. □

Lemma 5.9

Let $X$ be a quasi-median graph of finite cubical dimension. For every hyperplane $J$, choose a sector $J^{+}$ delimited by $J$. Assume that

• for any two hyperplanes $J_{1}$ and $J_{2}$, $J_{1}^{+} \cap J_{2}^{+} \neq \emptyset$;

• every non-increasing sequence $J_{1}^{+} \supset J_{2}^{+} \supset \cdots$ is eventually constant.

Then $\bigcap \limits _{\textit{$J$ hyperplane}} J^{+}$ is non-empty and reduced to a single vertex.

Proof

Assume for contradiction that the intersection is empty. We define by induction a sequence $x_{0},x_{1},\ldots$ of vertices and a sequence $J_{1},J_{2},\ldots$ of hyperplanes as follows:

• Fix an arbitrary vertex $x_{0} \in X$.

• Assume that $x_{n}$ and $J_{1},\ldots , J_{n}$ are defined. There must exist some hyperplane $J_{n+1}$ such that $x_{n} \notin J_{n+1}^{+}$. Define $x_{n+1}$ as the projection of $x_{n}$ onto the intersection $I_{n+1}:= \bigcap \limits _{i=1}^{n+1} J_{i}^{+}$ (which is non-empty as a consequence of the gatedness of sectors given by Theorem 5.4).

Observe that $(I_{n})$ defines a decreasing sequence of gated subgraphs such that, for every $n \geq 1$, $x_{n}$ belongs to $I_{n}$ and, according to Lemma 5.5, $J_{n+1}$ separates $x_{n}$ from $I_{n+1}$. As a consequence, $x_{m} \in J_{n}^{+}$ for every $m \geq n$. Because every collection of pairwise transverse hyperplane has cardinality at most $\dim _{\square}(X)<\infty$, it follows from Ramsey’s theorem that there exists a subsequence $(J_{k_{n}})$ of pairwise non-transverse hyperplanes. We deduce from the previous observation that $J_{k_{1}}^{+} \supset J_{k_{2}}^{+} \supset \cdots$, contradicting our assumptions.

Thus, we have proved that $\bigcap \limits _{\text{$J$ hyperplane}} J^{+}$ is non-empty. Fix a vertex $a$ in this intersection and let $b \in X$ be an arbitrary vertex distinct from $a$. Because $a \neq b$, there exists some hyperplane $J$ separating $a$ and $b$; and, because $a \in J^{+}$, necessarily $b \notin J^{+}$, hence $b \notin \bigcap \limits _{\text{$J$ hyperplane}} J^{+}$. Thus, we have proved that $a$ is the unique vertex in $\bigcap \limits _{\text{$J$ hyperplane}} J^{+}$, concluding the proof of our lemma. □

Prism complexes

In the same way that median graphs can be thought of as one-skeleta of cubical complexes, quasi-median graphs are naturally one-skeleta of prism complexes. Here, a prism refers to a product of simplices and a prism complex to a cellular complex obtained by gluing prisms along faces (i.e. products of maximal simplices). We emphasize that, with our definition, gluing two triangles along a common edge does not define a prism complex since the faces of a triangle, when thought of as a prism, are its vertices and itself.

Because two intersecting cliques (i.e. maximal complete subgraphs) in a quasi-median graph either coincide or intersect along a single vertex (see [25, Lemma 2.11]), filling in the prisms of the graph with products of simplices yields a prism complex. We refer to such a prism complex as a quasi-median complex. The only thing we need to know about quasi-median complexes is that they are simply connected. In fact, it is not difficult to deduce from the product structure of hyperplanes that they are contractible. A less straightforward property is that quasi-median complexes can be endowed with CAT(0) metrics [25, Theorem 2.120], which also implies that they are contractible.

Graph products of groups

Given a simplicial graph $\Gamma$ and a collection $\mathcal{G}=\{G_{u} \mid u \in V(\Gamma )\}$ of groups indexed by the vertex-set $V(\Gamma )$ of $\Gamma$, the graph product $\Gamma \mathcal{G}$ is the quotient

$$ \left ( \underset{u \in V(\Gamma )}{\ast} G_{u} \right ) / \langle \langle [g,h]=1 \text{ if $g \in G_{u}$ and $h \in G_{v}$ for some $\{u,v\} \in E(\Gamma )$} \rangle \rangle $$

where $E(\Gamma )$ denotes the edge-set of $\Gamma$. The groups in $\mathcal{G}$ are referred to as vertex-groups. If all the vertex-groups are isomorphic to a single group $G$, we denote the graph product by $\Gamma G$ instead of $\Gamma \mathcal{G}$.

Vertex-groups embed into the graph product. More generally, given an induced subgraph $\Lambda \subset \Gamma$, the subgroup generated by the vertex-groups indexed by the vertices in $\Lambda$, which we denote by $\langle \Lambda \rangle$, is naturally isomorphic to the graph product $\Lambda \mathcal{G}_{|V(\Lambda )}$ where $\mathcal{G}_{|V(\Lambda )}:= \{ G_{u} \mid u \in V(\Lambda ) \} \subset \mathcal{G}$.

As observed in [25], graph products naturally act on quasi-median graphs. More precisely, it acts by left-multiplication on the following Cayley graph:

Proposition 5.10

Given a simplicial graph $\Gamma$ and a collection of groups $\mathcal{G}$ indexed by $V(\Gamma )$, consider the Cayley graph

$$ \mathrm{QM}(\Gamma , \mathcal{G}):= \mathrm{Cayl} \left ( \Gamma \mathcal{G}, \bigcup \limits _{u \in V(\Gamma )} G_{u} \backslash \{1 \} \right ). $$

Then $\mathrm{QM}(\Gamma , \mathcal{G})$ is a quasi-median graph of cubical dimension $\mathrm{clique}(\Gamma )$.

We refer to [25, Proposition 8.2] for a proof. As an easy example, the reader can keep Figure 5 in mind. The cliques, prisms, and hyperplanes of $\mathrm{QM}(\Gamma , \mathcal{G})$ are described as follows (see [25, Lemma 8.6 and Corollaries 8.7 and 8.10] or [28, Lemmas 2.4 and 2.6, and Theorem 2.10]):

Fig. 5

Example of a quasi-median graph $\mathrm{QM}(\Gamma , \mathcal{G})$ (Color figure online)

Lemma 5.11

Let $\Gamma$ be a simplicial graph and $\mathcal{G}$ a collection of groups indexed by $V(\Gamma )$. The cliques of $\mathrm{QM}(\Gamma , \mathcal{G})$ coincide with the cosets of vertex-groups.

Lemma 5.12

Let $\Gamma$ be a simplicial graph and $\mathcal{G}$ a collection of groups indexed by $V(\Gamma )$. The prisms of $\mathrm{QM}(\Gamma , \mathcal{G})$ coincide with the cosets of the $\langle \Lambda \rangle$, where $\Lambda \subset \Gamma$ is a complete subgraph.

Lemma 5.13

Let $\Gamma$ be a simplicial graph and $\mathcal{G}$ a collection of groups indexed by $V(\Gamma )$. Fix a vertex $u \in V(\Gamma )$ and let $J_{u}$ denote the hyperplane containing the clique $G_{u}$. The cliques in $J_{u}$ are the cosets $gG_{u}$ where $g \in \langle \mathrm{star}(u) \rangle$. Consequently, the carrier $N(J_{u})$ coincides with the subgraph $\langle \mathrm{star}(u) \rangle$ and splits at the Cartesian product $G_{u} \times \langle \mathrm{link}(u) \rangle$; and the stabiliser of $J_{u}$ in $\Gamma \mathcal{G}$ coincides with the subgroup $\langle \mathrm{star}(u) \rangle$.

Recall that, given a graph $\Gamma$ and a vertex $u \in V(\Gamma )$, the star (resp. the link) of $u$ is the subgraph induced by $u$ and its neighbours (resp. by its neighbours). We record the following straightforward consequence of Lemma 5.13:

Fact 5.14

Let $\Gamma$ be a simplicial graph and $\mathcal{G}$ a collection of groups indexed by $V(\Gamma )$. Fix a hyperplane $J$, a vertex $x \in N(J)$, and two distinct cliques $C_{1},C_{2} \subset N(J)$ containing $x$. If $C_{1} \subset J$, then $C_{1}$ and $C_{2}$ span a prism.

Proof

Up to translating by $x^{-1}$, we assume that $x=1$. Consequently, there exist two vertices $u,v \in V(\Gamma )$ such that $J=J_{u}$, $C_{1}=G_{u}$, and $C_{2}=G_{v}$. It follows from Lemma 5.13 that $v \in \mathrm{star}(u)$. Since the cliques $C_{1}$ and $C_{2}$ are distinct by assumption, we conclude that $v$ is adjacent to $u$, so $C_{1}$ and $C_{2}$ span the prism $G_{u} \oplus G_{v}$. □

In $\mathrm{QM}(\Gamma , \mathcal{G})$, like in any other Cayley graph, edges are naturally labelled by generators. As a consequence, edges in $\mathrm{QM}(\Gamma , \mathcal{G})$ are naturally labelled by vertices of $\Gamma$, corresponding to the vertex-groups the generators belong to. A direct consequence of Lemma 5.13 is:

Lemma 5.15

Let $\Gamma$ be a simplicial graph and $\mathcal{G}$ a collection of groups indexed by $V(\Gamma )$. In $\mathrm{QM}(\Gamma , \mathcal{G})$, two cliques in the same hyperplane have the same label (in the sense that all their edges have the same label).

5.2 An alternative viewpoint on lamplighter graphs

In this section, we propose an alternative description of lamplighter graphs that will be central in the proof of our embedding theorem.

Definition 5.16

Let $W$ be a finite-dimensional prism complex. The graph of pointed simplices $\mathsf{PS}_{1}(W)$ is the graph whose vertices are the pointed simplices $(S,x)$, where $S$ is a maximal simplex (with respect to the inclusion) and $x \in S$ a vertex, and whose edges link two pointed simplices $(S_{1},x_{1})$, $(S_{2},x_{2})$ if either $S_{1}=S_{2}$ and $x_{1} \neq x_{2}$ or $x_{1}=x_{2}$ and $S_{1}$, $S_{2}$ span a prism in $W$.

The idea to keep in mind is that we are moving a pointed simplex $(S,x)$ in $W$ by applying two elementary moves: either we slide the vertex $x$ to another vertex of $S$, or we rotate the simplex $S$ around the vertex $x$ through a prism. See Fig. 6 for an explicit example.

Fig. 6

A square complex and a piece of its graph of pointed edges (Color figure online)

Now, let us show that any lamplighter graph can be described as the graph of pointed simplices of some prism complex. So let $X$ be a locally finite graph and $n \geq 2$ an integer. Define the prism complex $W(n,X)$ as follows:

• the vertices of $W(n,X)$ are the finitely supported colourings in $\mathbb{Z}_{n}^{(X)}$;

• two colourings are linked by an edge in $W(n,X)$ if they differ at a single vertex of $X$, referred to as the label of the edge;

• for every vertex $v \in X$ and every colouring $\varphi \in \mathbb{Z}_{n}^{(X)}$, the complete subgraph $\{ \psi \in \mathbb{Z}_{n}^{(X)} \mid \mathrm{supp}(\psi - \varphi ) \subset \{v\} \}$ in $W(n,X)$ spans a simplex $S(\varphi ,v)$;

• simplices $S(\varphi , v_{1}), \ldots , S(\varphi ,v_{k})$ span a prism in $W(n,X)$ if $v_{1},\ldots , v_{k}$ are pairwise adjacent in $X$.

Notice that the edges of a simplex in $W(n,X)$ all have the same label, so it makes sense to refer to this common label as the label of the simplex.

The prism complex $W(n,X)$ is a sub-complex of the prism $\bigoplus _{X} \Delta ^{n}$: it has the same underlying simplicial complex, but only contains prisms that are spanned by simplices labelled by pairwise adjacent vertices of $X$. While $\bigoplus _{X} \Delta ^{n}$ has infinite dimension as soon as $X$ is infinite, $W(n,X)$ has finite dimension as soon as $X$ has bounded degree.

We now state our main observation.

Proposition 5.17

The map $(S,x) \mapsto (x, \textit{ vertex of }X\textit{ labelling }S)$ induces a graph isomorphism $\mathsf{PS}_{1}(W(n,X)) \to \mathcal{L}_{n}(X)$. Moreover, it sends a leaf to a leaf.

Here, a leaf of $\mathsf{PS}_{1}(W(n,X))$ refers to a fibre of the canonical projection $\mathsf{PS}_{1}(W) \twoheadrightarrow W$ induced by $(S,x) \mapsto x$. In other words, a leaf is a subgraph spanned by $\{ (S,x) \mid S\text{ maximal simplex}\}$ for some vertex $x$.

Proof of Proposition 5.17

It is clear that our map induces a bijection from the vertices of $\mathsf{PS}_{1}(W(n,X))$ to the vertices of $\mathcal{L}_{n}(X)$. Indeed, if two pointed simplices $(S_{1},x_{1}),(S_{2},x_{2}) \in W(n,X)$ have the same image in $\mathcal{L}_{n}(X)$, then $x_{1}=x_{2}$ and

$$ S_{1}= \{ y \text{ colouring} \mid \mathrm{supp}(x_{1}-y) \subset \{ \ell \} \}=S_{2} $$

where $\ell$ is the common label of $S_{1}$ and $S_{2}$. This proves injectivity. Next, notice that, given a vertex $(x, v) \in \mathcal{L}_{n}(X)$, our map sends

$$ \left ( \{ y \text{ colouring} \mid \mathrm{supp}(x-y) \subset \{v\}\} , \ x \right ) $$

to $(x,v)$, proving surjectivity.

It remains to show that our map preserves (non-)adjacency. Let $(S_{1},x_{1}),(S_{2},x_{2}) \in \mathsf{PS}_{1}(W(n,X))$ be two vertices. Observe that $S_{1}=S_{2}$ and $x_{1} \neq x_{2}$ amounts to saying that the colourings $x_{1}$, $x_{2}$ differ at a single vertex which is also the common label of $S_{1}$, $S_{2}$. Also, $x_{1}=x_{2}$ and $S_{1}$, $S_{2}$ span a prism amounts to saying that the colourings $x_{1}$, $x_{2}$ coincide and that the labels of $S_{1}$, $S_{2}$ are adjacent. Consequently, $(S_{1},x_{1})$ and $(S_{2},x_{2})$ are adjacent in $\mathsf{PS}_{1}(W(n,X))$ if and only if so are their images in $\mathcal{L}_{n}(X)$. □

In the rest of the section, we study in more details graphs of pointed simplices of prism complexes. Our main objective is to realise them as one-skeleta of 2-complexes, in a way that is sufficiently natural so that a covering map between prism complexes will induce a covering map between the corresponding complexes of pointed simplices.

Definition 5.18

Let $W$ be a finite-dimensional prism complex. The complex of pointed simplices $\mathsf{PS}(W)$ is the 2-complex obtained from $\mathsf{PS}_{1}(W)$ by gluing triangles and octagons along the following cycles in $\mathsf{PS}_{1}(W)$ and by identifying two polygons when every they have the same boundary:

• $((S,x_{1}),(S,x_{2}),(S,x_{3}))$ where $x_{1}$, $x_{2}$, $x_{3}$ are pairwise distinct vertices of a maximal simplex $S$;

• $((S_{1},x),(S_{2},x),(S_{3},x))$ where $S_{1}$, $S_{2}$, $S_{3}$ are three pairwise distinct maximal simplices that contain a vertex $x$ and that span a prism;

• $((S_{1},x_{1}), (S_{2},x_{1}), (S_{2},x_{2}), (S_{3},x_{2}), (S_{3},x_{3}), (S_{4},x_{3}), (S_{4},x_{4}), (S_{1},x_{4}))$ where the vertices $x_{1},\ldots , x_{4}$ are pairwise distinct and where $S_{1}$, $S_{2}$ span a prism $S_{1} \times S_{2}$ such that $S_{3} = S_{1} \times \{\mathrm{pt}\}$ and $S_{4}= \{\mathrm{pt}\} \times S_{2}$.

As an illustration, the 3- and 8-cycles in the graphs of pointed simplices given by Figs. 6 and 7 bound polygons.

Fig. 7

The graph of pointed edges of a 3-cube

A natural generalisation would be to investigate the structure of $\mathsf{PS}_{1}(\text{prism})$ in order to define a higher dimensional complex structure on $\mathsf{PS}_{1}(W)$. Figure 7 illustrates $\mathsf{PS}_{1}(3-\text{cube})$, which turns out to coincides with the one-skeleton of a convex polyhedron. More generally, it can be shown that $\mathsf{PS}_{1}(n-\text{cube})$ coincides with the one-skeleton of a convex polytope in $\mathbb{E}^{n}$, namely a truncated $n$-cube. As a consequence, the graph of pointed edges of a cube complex can be naturally endowed with the structure of cellular complex. However, the situation is less clear when triangles are allowed. For instance, observe that the link of a vertex in $\mathsf{PS}(\text{triangle}^{2})$ is a 3-cycle, and not the expected complete graph $K_{4}$ for a convex polytope in $\mathbb{E}^{4}$. Anyway, no higher dimensional structure on $\mathsf{PS}(W)$ is required in the sequel, so we do not pursue further these questions and restrict ourselves to the following observation:

Lemma 5.19

If $W$ is a prism, then $\mathsf{PS}(W)$ is a simply connected 2-complex.

Proof

Because any two intersecting maximal simplices in $W$ span a prism, for every vertex $x \in W$ the subcomplex $\mathsf{PS}_{x}$ spanned by $\{ (S,x) \mid S\text{ maximal simplex}\}$, called leaf below, coincides with the 2-skeleton of a simplex, and so is simply connected. Notice that the subcomplexes $\mathsf{PS}_{x}$ are pairwise disjoint, so we can collapse them without modifying the fundamental group of the space. The complex thus obtained coincides with the 2-skeleton of $W$, which is simply connected. □

Observe that, given a prism complex $W$, the canonical projection $\mathsf{PS}(W) \twoheadrightarrow W$ induced by $(S,x) \mapsto x$ is combinatorial, i.e. it sends a cell to a cell. As shown by Proposition 5.17, a lamplighter graph can be described as a graph of pointed simplices of some prism complex, and, under such an identification, leaves of the lamplighter graph will correspond to the fibres of the previous projection. This motivates the following terminology:

Definition 5.20

Let $W$ be a finite-dimensional prism complex. For every vertex $x \in W$, we refer to the subgraph (resp. the subcomplex) $\mathsf{PS}_{x}$ generated by $\{(S,x) \mid S\text{ simplex}\}$ in $\mathsf{PS}_{1}(W)$ (resp. $\mathsf{PS}(W)$) as a leaf.

Observe that $\mathsf{PS}_{x}$ can be thought of as a link of $x$ in $W$. Indeed, the vertices of $\mathsf{PS}_{x}$ are given by the maximal simplices of $W$ containing $x$ and two such simplices are linked by an edge in $\mathsf{PS}_{x}$ if they span a prism in $W$. In $\mathsf{PS}(W)$, the vertices of a leaf are obtained by only rotating a given pointed simplex around its distinguished vertex.

Next, observe that our construction of complexes of pointed simplices is compatible with covering maps. More precisely:

Lemma 5.21

Let $W_{1}$, $W_{2}$ be two finite-dimensional prism complexes and $\xi : W_{1} \to W_{2}$ a covering map. Then the map $\overline{\xi} : \mathsf{PS}(W_{1}) \to \mathsf{PS}(W_{2})$ induced by $(S,x) \mapsto (\xi (S),\xi (x))$ also defines a covering map. Moreover, it sends a leaf to a leaf.

Proof

It suffices to show that, given an arbitrary pointed simplex $(S,x)$, $\overline{\xi}$ induces an isomorphism from the link of $(S,x)$ to the link of $\xi (S,x)$. The link of $(S,x)$ is the graph whose vertices are $(S,x_{1}), \ldots , (S,x_{p})$, where $x_{1},\ldots , x_{p}$ are the vertices in $S \backslash \{x\}$, and $(S_{1},x), \ldots , (S_{q},x)$, where $S_{1}, \ldots , S_{q}$ are the maximal simplices containing $x$ and spanning prisms with $S$; and whose edges connect $(S,x_{i})$ with $(S,x_{j})$ for all $1 \leq i< j \leq p$, $(S,x_{i})$ with $(S_{j},x)$ for all $1 \leq i \leq p$ and $1 \leq j \leq q$, and $(S_{i},x)$ with $(S_{j},x)$ whenever $S$, $S_{i}$, $S_{j}$ span a prism in $W_{1}$. The link of $\overline{\xi}(S,x)= (\xi (S),\xi (x))$ is described similarly. Because $\xi$ is a covering map, $\xi (x_{1}),\ldots , \xi (x_{p})$ are the vertices in $\xi (S) \backslash \{\xi (x)\}$ and $\xi (S_{1}), \ldots , \xi (S_{q})$ are the maximal simplices containing $\xi (x)$ and spanning prisms with $\xi (S)$. The desired conclusion follows. □

5.3 Proof of the embedding theorem

Recall from Proposition 5.17 that the lamplighter graph $\mathcal{L}_{n}(X)$ can be described as the graph of pointed simplices of some prism complex $W(n,X)$. The first ingredient towards the proof of Theorem 5.1 is that the universal cover $\widetilde{W}(n,X)$ of $W(n,X)$ has a very rigid structure, namely it turns out to be quasi-median complex.

Lemma 5.22

$\widetilde{W}(n,X)$ is a quasi-median complex of cubical dimension $\mathrm{clique}(X)$.

As a consequence, the hyperplanes of $\widetilde{W}(n,X)$ induce a structure of space with partitions [25] (i.e. the quasi-median analogue of a space with walls, in which walls delimit at least two components, possibly more) on the graph $\mathsf{PS}_{1}(\widetilde{W}(n,X))$. The second ingredient towards the proof of Theorem 5.1 is that these walls satisfy convenient properties. First, the walls in $\mathsf{PS}_{1}(\widetilde{W}(n,X))$ have bounded images in $\mathsf{PS}_{1}(W(n,X))$:

Lemma 5.23

For every hyperplane $J$ in $\widetilde{W}(n,X)$, the image of $\{(S,x) \mid S \subset J \} \subset \mathsf{PS}_{1}(\widetilde{W}(n,X))$ in $\mathsf{PS}_{1}(W(n,X))$ has bounded diameter.

And second, along a given wall, the metrics induced by $\widetilde{W}(n,X)$ and $\mathsf{PS}_{1}(\widetilde{W}(n, X))$ turn out to be biLipschitz equivalent:

Lemma 5.24

For every hyperplane $J$ in $\widetilde{W}(n,X)$ and pointed simplices $(S_{1},x_{1}), (S_{2},x_{2}) \in \mathsf{PS}_{1}(\widetilde{W}(n,X))$ satisfying $S_{1},S_{2} \subset J$, the inequalities

$$ d_{\widetilde{W}} (x_{1},x_{2}) \leq d_{\mathsf{PS}}((S_{1},x_{1}),(S_{2},x_{2})) \leq 3 d_{\widetilde{W}}(x_{1},x_{2}) $$

hold.

We postpone the proofs of these three lemmas to the next section, and show how to deduce Theorem 5.1 from them.

Proof of Theorem 5.1

Let $R\geq 0$ be such that filling in the cycles of $Z$ of length $\leq R$ with discs produces a simply connected 2-complex. Let $L \geq 0$ be such that the image under $\rho$ of every cycle of length $\leq R$ in $Z$ has diameter at most $L$ in $\mathcal{L}_{n}(X)$. Observe that $L$ depends only on $R$ and the parameters of $\rho$. Let $X^{+}$ denote the graph obtained from $X$ by adding an edge between any two vertices at distance $\leq L$. The inclusion $X \hookrightarrow X^{+}$ induces an $(L,0)$-quasi-isometry $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{n}(X^{+})$ that sends leaves to leaves. Thus, we have a coarse embedding $q \circ \rho : Z \to \mathcal{L}_{n}(X^{+})$ satisfying:

$(\ast \ast )$:

for every cycle $\gamma \subset Z$ of length $\leq R$, there exist a colouring $\varphi \in \mathbb{Z}_{n}^{(X^{+})}$ and a complete subgraph $Y \subset X^{+}$ such that $q \circ \rho (\gamma ) \subset \{ (\psi ,x) \mid x \in Y, \; \mathrm{supp}(\psi -\varphi ) \subset Y \}$.

According to Proposition 5.17, there exist a prism complex $W(n,X^{+})$ and an isomorphism $\tau : \mathcal{L}_{n}(X^{+}) \to \mathsf{PS}_{1}(W(n,X^{+}))$ that sends leaves to leaves. Set $\eta := \tau \circ (q \circ \rho )$. We think of $\mathsf{PS}_{1}(W(n,X^{+}))$ as the one-skeleton of $\mathsf{PS}(W(n,X^{+}))$.

Let $Z^{+}$ denote the geometric realisation of $Z$, i.e. the one-dimensional simplicial complex obtained from $Z$ by connecting any two adjacent vertices with a copy of $[0,1]$ and endowed with the usual metric length. Then $\eta : Z \to \mathsf{PS}(W(n,X^{+}))$ extends (by sending 1-cells to geodesics) to a continuous coarse embedding $Z^{+} \to \mathsf{PS}(W(n,X^{+}))$ whose parameters only depend on those of $\eta$.

In order to shorten the notation in the sequel, we write $X$, $Z$, and $\rho$ for $X^{+}$, $Z^{+}$, and $q \circ \rho$ respectively. Notice that $(\ast \ast )$ becomes

$(\ast )$:

for every cycle $\gamma \subset Z$ of length $\leq R$, there exist a colouring $\varphi \in \mathbb{Z}_{n}^{(X)}$ and a complete subgraph $Y \subset X$ such that $\rho (\gamma ) \subset \{ (\psi ,x) \mid x \in Y, \; \mathrm{supp}( \psi -\varphi ) \subset Y \}$.

According to Lemma 5.21, the universal cover $\widetilde{W}(n,X) \to W(n,X)$ induces a covering map $\pi : \mathsf{PS}(\widetilde{W}(n,X)) \to \mathsf{PS}(W(n,X))$. As a consequence of $(\ast )$, $\eta$ sends every cycle of length $\leq R$ in $Z$ inside $\mathsf{PS}(P) \subset \mathsf{PS}(W(n,X))$ for some prism $P \subset W(n,X)$. We conclude from Lemma 5.19 that $\eta (Z)$ is simply connected in $\mathsf{PS}(W(n,X))$. Therefore, $\eta : Z \to \mathsf{PS}(W(n,X))$ lifts to $\widetilde{\eta} : Z \to \mathsf{PS}(\widetilde{W}(n,X))$. So we have the following commutative diagram:

where $\iota$ denotes the inclusion map. According to Lemma 2.4, $\widetilde{\eta}$ is a coarse embedding whose parameters depend only on those of $\rho$. (Here, we think of $\mathrm{PS}(\widetilde{W}(n,X))$ as endowed with the metric length obtained by identifying its 2-cells with regular Euclidean triangles and octogons. With respect to this metric, $\iota$ defines a quasi-isometry.) Because the maps $\tau$ and $\pi$ send leaves to leaves, it suffices to show that $\widetilde{\eta}(Z)$ lies in the neighbourhood of a leaf in $\mathsf{PS}(\widetilde{W}(n,X))$ in order to conclude the proof of our theorem. Recall from Lemma 5.22 that $\widetilde{W}(n,X)$ is a quasi-median complex of cubical dimension $\mathrm{clique}(X)$.

Claim 5.25

There exists a constant $B \geq 0$ only depending on $X$, $Z$, and the parameters of $\rho$ such that the following holds. Every hyperplane $J$ in $\widetilde{W}(n,X)$ delimits a sector $H$ such that $\widetilde{\eta}(Z) \cap \{ \textit{pointed simplices in }H \}$ is unbounded and $\widetilde{\eta}(Z) \cap \{ \textit{pointed simplices in }H'\}$ has diameter $\leq B$ for every sector $H' \neq H$ delimited by $J$.

Here, we refer to a pointed simplex as lying in a sector whenever the underlying simplex is contained in this sector.

Notice that $\widetilde{\eta}(Z)$ is contained in the one-skeleton of $\mathsf{PS}(\widetilde{W}(n,X))$. Let ℰ (resp. $\mathcal{E}_{K}$ for a given sector $K$ delimited by $J$) denote the subgraph in the one-skeleton of $\mathsf{PS}(\widetilde{W}(n,X))$ spanned by the set of vertices

$$ \{ (S,p) \in \widetilde{\eta}(Z) \mid S \subset J, p \in S \} $$

(resp.

$$ \{(S,p) \in \widetilde{\eta}(Z) \mid S \subset K, p\in S\}). $$

Because $J$ separates $\widetilde{W}(n,X)$ into sectors, it is clear that ℰ separates in $\tilde{\eta}(Z)$ any two $\mathcal{E}_{K_{1}}$ and $\mathcal{E}_{K_{2}}$ for distinct sectors $K_{1}$, $K_{2}$. Because $\pi$ restricts to a continuous coarse embedding on $\tilde{\eta}(Z)$, the same must be true about $\pi (\mathcal{E})$ and the $\pi (\mathcal{E}_{K})$ in $\pi (\tilde{\eta}(Z))$. Because $\pi (\mathcal{E})$ is bounded, according to Lemma 5.23, and because $Z$ (and a fortiori $\pi (\tilde{\eta}(Z))$) is uniformly one-ended, there must exist a sector $H$ such that $\pi (\mathcal{E}_{H})$ is unbounded and such that the other $\pi (\mathcal{E}_{K})$ are uniformly bounded. Again because $\pi$ restricts to a coarse embedding on $\tilde{\eta}(Z)$, the same must be true about $\mathcal{E}_{H}$ and the other $\mathcal{E}_{K}$, which concludes the proof of Claim 5.25.

For every hyperplane $J$ of $\widetilde{W}(n,X)$, let $J^{+}$ denote the sector given by Claim 5.25.

Claim 5.26

The intersection $\bigcap \limits _{\textit{$J$ hyperplane}} J^{+}$ is reduced to a single vertex.

Our goal is to apply Lemma 5.9.

Let $J_{1}$, $J_{2}$ be two hyperplanes. If $J_{1}$ and $J_{2}$ are transverse, then clearly $J_{1}^{+}$ and $J_{2}^{+}$ intersect. Next, if $J_{1}$ and $J_{2}$ are not transverse and if $J_{1}^{+}$ contains $J_{2}$, then clearly $J_{1}^{+}$ and $J_{2}^{+}$ intersect. Finally, if $J_{1}$ and $J_{2}$ are not transverse and if $J_{1}^{+}$ does not contain $J_{2}$, then $J_{2}^{+}$ must be the sector delimited by $J_{2}$ that contains $J_{1}$ as a direct consequence of Claim 5.25. It follows that $J_{1}^{+}$ and $J_{2}^{+}$ intersect.

Next, assume for contradiction that $J_{1}^{+} \supsetneq J_{2}^{+} \supsetneq \cdots$ for some collection of hyperplanes $J_{1},J_{2}, \ldots$ in $\widetilde{W}(n,X)$. Fix a vertex $(S,x) \in \widetilde{\eta}(Z)$ such that $S \subset J_{1}^{+}$. Because two vertices in $\widetilde{W}(n,X)$ are always separated by only finitely many hyperplanes, there must exist some $r \geq 1$ such that $S$ is disjoint from $J_{r}^{+}$. Next, fix an $s > r+B$ and a vertex $(Q,y) \in \widetilde{\eta}(Z)$ such that $Q \subset J_{s}^{+}$. As before, there exists $t \geq s$ such that $Q$ is disjoint from $J_{t}^{+}$. We conclude that

$$ B< s-r \leq d(x,y) \leq d((S,x),(Q,y)) \leq B, $$

where the second inequality is justified by the fact that there are at least $s-r$ hyperplanes separating $x$ and $y$ (namely, $J_{r}, \ldots , J_{s}$); and where the last inequality is justified by Claim 5.25, which implies that the pointed cliques of $\widetilde{\eta}(Z)$ lying in a in sector delimited by $J_{t}$ that is disjoint from $J_{t}^{+}$ must at most $B$ apart. We get a contradiction.

Lemma 5.9 completes the proof of Claim 5.26.

Let $x$ denote the vertex of $\widetilde{W}(n,X)$ given by Claim 5.26, and consider the corresponding leaf of $\mathsf{PS}_{1}(\widetilde{W}(n,X))$:

$$ \mathcal{H}:=\{(T,x) \mid \text{$T$ maximal simplex containing $x$} \}. $$

In order to conclude the proof of our theorem, it suffices to show that every vertex in $\widetilde{\eta}(Z)$ lies at bounded distance from ℋ.

Let $(S,y)$ be a vertex in $\widetilde{\eta}(Z)$ and pick a geodesic path from $y$ to $x$ in the one-skeleton of $\widetilde{W}(n,X)$. Let $K$ denote the maximal simplex containing the last edge of that geodesic. Note that $(K,x)\in \mathcal{H}$. Because the hyperplane $J$ containing $K$ separates $y$ and $x$, it follows from the definition of $J^{+}$ that $J$ separates $y$ from a pointed simplex $(S',x')\in \widetilde{\eta} (Z)$. Recall that, since $\widetilde{\eta}$ is continuous, $\widetilde{\eta}(Z)$ is connected. Every path in $\widetilde{\eta}(Z)$ joining $(S,y)$ to $(S',x')$ must therefore cross $J$. We let $(Q,z) \in \widetilde{\eta}(Z)$ be the first vertex along that path such that $Q \subset J$. The initial segment of that path that ends just before hitting $J$ is contained in a single sector delimited by $J$. Since this sector is distinct from $J^{+}$, we deduce that $d((S,y),(Q,z)) \leq B+1$. Thanks to Claim 5.27 below, we have

$$ \textstyle\begin{array}{lcl} d((S,y),\mathcal{H}) & \leq & d((S,y),(K,x)) \leq d((S,y),(Q,z))+d((Q,z),(K,x)) \\ \\ & \leq & B+1 + 3d(z,x) \leq 2(B+2) + \mathrm{clique}(X) \cdot (B+3), \end{array} $$

where the penultimate inequality is justified by Lemma 5.24. This concludes the proof of Theorem 5.1.

Claim 5.27

$d(z,x) \leq \mathrm{clique}(X) \cdot (B+1)+B+2$.

We begin by bounding above the distance between $y$ and $x$. Let $J_{1}, \ldots , J_{k}$ be a maximal collection of pairwise non-transverse hyperplanes separating $y$ and $x$. Up to reindexing our collection, we assume that $J_{i}$ separates $J_{i-1}$ and $J_{i+1}$ for every $2 \leq i \leq k-1$ and that $J_{1}$ separates $y$ from $J_{k}$. According ton Lemma 5.8, $d(y,x) \leq \mathrm{clique}(X) \cdot k$. Therefore, it is sufficient to bound $k$. If $k \leq 1$, then $d(y,x) \leq \mathrm{clique}(X)$. From now on, we assume that $k \geq 2$. As a consequence, $S$ is disjoint from $J_{k}^{+}$. But there must exist a pointed simplex of $\tilde{\eta}(Z)$ contained in $J_{k}^{+}$ and $\tilde{\eta}(Z)$ is connected, so, along a path of pointed simplices in $\tilde{\eta}(Z)$ connecting $(S,y)$ to some pointed simplex contained in $J_{k}^{+}$, we can find a $(P_{0},w_{0}) \in \tilde{\eta}(Z)$ with $P_{0} \subset J_{k}$. Take $(P_{0},w)$ as the first such pointed simplex along our path. The previous pointed simplex must be $(P,w)$ for some simplex $P$ contained in the same sector delimited by $J_{k}$ as $S$. We have $k-1 \leq d(y,w) \leq d((P,w),(S,y)) \leq B$ where the first inequality is justified by the fact that $y$ and $w$ are separated by $J_{1}, \ldots , J_{k-1}$ and where the last inequality is justified by Claim 5.25. Therefore,

$$ d(y,x) \leq \mathrm{clique}(X) \cdot k \leq \mathrm{clique}(X) \cdot (B+1). $$

We also have $d(z,y) \leq d((Q,z),(S,y)) \leq B+2$, where the second inequality has been observed earlier. Therefore,

$$ d(z,x) \leq d(z,y)+d(y,x) \leq \mathrm{clique}(X) \cdot (B+1) + B+2 $$

as desired, concluding the proof of Claim 5.27. □

5.4 Proofs of the lemmas

This section is dedicated to the proofs of Lemmas 5.22, 5.23, and 5.24. Given a locally finite graph $X$ and an integer $n \geq 2$, the quasi-median structure claimed by Lemma 5.22 of the universal cover $\widetilde{W}(n,X)$ of $W(n,X)$ can be easily shown by verifying on $W(n,X)$ the local condition given in [25, Sect. 2.12]. However, it will be more convenient to identify $W(n,X)$ with the quotient of the quasi-median complex $\mathrm{QM}(X,\mathbb{Z}_{n})$ by some specific subgroup of the graph product $X \mathbb{Z}_{n}$ in order to deduce easily Lemmas 5.23 and 5.24, thanks to the description of quasi-median complexes given in Sect. 5.1.

Proofs of Lemmas 5.22, 5.23, and 5.24.

Consider the graph product $X\mathbb{Z}_{n}$ and its subgroup $K(X\mathbb{Z}_{n})$ defined as the kernel of the morphism $\dagger : X \mathbb{Z}_{n} \to \bigoplus _{X} \mathbb{Z}_{n}$ (which coincides with the epimorphism from $X\mathbb{Z}_{n}$ to its abelianisation). Observe that, for every complete subgraph $Y \subset X$, † is injective on the subgroup $\langle Y \rangle \leq X \mathbb{Z}_{n}$. Consequently, we deduce from Lemma 5.12 that $K(X \mathbb{Z}_{n})$ intersects trivially the prism stabilisers of the action $X \mathbb{Z}_{n} \curvearrowright \mathrm{QM}(X, \mathbb{Z}_{n})$. In other words, $K(X \mathbb{Z}_{n})$ acts freely on $\mathrm{QM}(X, \mathbb{Z}_{n})$, so the quotient map

$$ \rho : \mathrm{QM}(X, \mathbb{Z}_{n}) \twoheadrightarrow \mathrm{qm}(X, \mathbb{Z}_{n}):= \mathrm{QM}(X, \mathbb{Z}_{n})/ K(X \mathbb{Z}_{n}) $$

is a universal covering map. Let us observe that:

Claim 5.28

The prism complexes $\mathrm{qm}(X,\mathbb{Z}_{n})$ and $W(n,X)$ are isomorphic.

Because † is the quotient map $X\mathbb{Z}_{n} \twoheadrightarrow \bigoplus _{X} \mathbb{Z}_{n}$, quotienting by the kernel yields an isomorphism $X\mathbb{Z}_{n} / K(X\mathbb{Z}_{n}) \to \bigoplus _{X} \mathbb{Z}_{n}$. By identifying $\bigoplus _{X} \mathbb{Z}_{n}$ with $\mathbb{Z}_{n}^{(X)}$, we get a bijection $\ddagger ^{(0)} : \mathrm{qm}(X,\mathbb{Z}_{n})^{(0)} \to W(n,X)^{(0)}$ that induces a bijection between the vertices. Because moving a vertex in $\mathrm{QM}(X,\mathbb{Z}_{n})$ amounts to right-multiplying by a generator, moving a vertex in $\mathrm{qm}(X,\mathbb{Z}_{n})$ amounts to modifying one coordinate in $\bigoplus _{X} \mathbb{Z}_{n}$. Under $\ddagger ^{(0)}$, this operation amounts to modifying a colouring at a single point. It follows that $\ddagger ^{(0)}$ extends to an isomorphism $\ddagger ^{(1)} : \mathrm{qm}(X,\mathbb{Z}_{n})^{(1)} \to W(n,X)^{(1)}$. Finally, spanning a prism in $\mathrm{QM}(X,\mathbb{Z}_{n})$ amounts to right-multiplying by pairwise commuting generators, so spanning a prism in $\mathrm{qm}(X,\mathbb{Z}_{n})$ amounts to modifying coordinates in $\bigoplus _{X} \mathbb{Z}_{n}$ indexed by pairwise adjacent vertices of $X$. Under $\ddagger ^{(1)}$, this operation amounts to modifying a colouring at pairwise adjacent vertices of $X$. We conclude that $\ddagger ^{(1)}$ induces an isomorphism ‡ between the prism complexes $\mathrm{qm}(X,\mathbb{Z}_{n})$ and $W(n,X)$, as desired, concluding the proof of Claim 5.28.

As a consequence of Claim 5.28, we have a commutative diagram

where the top arrow is a lift of ‡ (which exists and is unique since $\mathrm{QM}(X,\mathbb{Z}_{n})$, as a quasi-median complex, is simply connected).

Thus, it suffices to prove Lemmas 5.22, 5.23, and 5.24 for $\mathrm{QM}(X,\mathbb{Z}_{n}) \twoheadrightarrow \mathrm{qm}(X, \mathbb{Z}_{n})$. First, Lemma 5.22 follows from Proposition 5.10. Next, let $J$ be a hyperplane of $\mathrm{QM}(X,\mathbb{Z}_{n})$. It follows from Lemma 5.13 that the image under † of the stabiliser of $J$ in $X\mathbb{Z}_{n}$ is finite, so the stabiliser of $J$ in $K(X \mathbb{Z}_{n})$ has finite index in the stabiliser of $J$ in $X\mathbb{Z}_{n}$. Because the latter acts transitively on the vertices of $J$, Lemma 5.23 follows.

We now turn to the proof of Lemma 5.24. Namely, we want to prove that, given a hyperplane $J$ of $\mathrm{QM}(X,\mathbb{Z}_{n})$ and two pointed simplices $(S_{1},x_{1}),(S_{2},x_{2}) \in \mathrm{PS}_{1}(\mathrm{QM}(X, \mathbb{Z}_{n}))$ satisfying $S_{1},S_{2} \subset J$, the inequalities

$$ d_{\mathrm{QM}}(x_{1},x_{2}) \leq d_{\mathsf{PS}} ((S_{1},x_{1}),(S_{2},x_{2})) \leq 3 d_{\mathrm{QM}}(x_{1},x_{2}) $$

hold. The inequality $d_{\mathsf{PS}}((S_{1},x_{1}),(S_{2},x_{2})) \geq d_{\mathrm{QM}}(x_{1},x_{2})$ is clear, so we focus on the other one. Let $(S_{1},x_{1}),(S_{2},x_{2}) \in \mathsf{PS}_{1}(\mathrm{QM}(X, \mathbb{Z}_{n}))$ be two pointed simplices such that $S_{1}$ and $S_{2}$ are contained in $J$. Fix a geodesic $y_{1}, \ldots , y_{k} \in \mathrm{QM}(X,\mathbb{Z}_{n})$ from $x_{1}$ to $x_{2}$, and, for every $1 \leq i \leq k-1$, let $T_{i}$ denote the unique maximal simplex that contains the edge connecting $y_{i}$ and $y_{i+1}$. As a consequence of Theorem 5.4, our geodesic lies in $N(J)$. So, for every $2 \leq i \leq k-1$, there exists a maximal simplex $U_{i} \subset J$ containing $y_{i}$. Observe that, as a consequence of Fact 5.14, $U_{i}$ spans two prisms with $T_{i-1}$ and $T_{i}$ for every $2 \leq i \leq k-1$, and, similarly, $S_{1}$ and $T_{1}$ (resp. $S_{k}$ and $T_{k-1}$) span a prism. It follows that

$$ \begin{aligned} (S_{1},x_{1})&=(S_{1},y_{1}), (T_{1},y_{1}), (T_{1},y_{2}), (U_{2},y_{2}), (T_{2},y_{2}), \ldots , (T_{k-1},y_{k}), (S_{2},y_{k})\\ &=(S_{2},x_{2}) \end{aligned} $$

defines a path of length $\leq 3(k-1)$ in $\mathsf{PS}_{1}(\mathrm{QM}(X,\mathbb{Z}_{n})$, hence the inequality

$$ d_{\mathsf{PS}}((S_{1},x_{1}),(S_{2},x_{2})) \leq 3 \cdot d_{ \mathrm{QM}}(x_{1},x_{2}). $$

This concludes the proofs of our lemmas. □

6 Theorems of rigidity

In this section, we put together Theorems 5.1 and 4.3 in order to prove that every quasi-isometry between two lamplighter graphs over coarsely simply connected uniformly one-ended graphs of bounded degree lies at finite distance from an aptolic quasi-isometry. See Theorem 6.4. Then, we prove the main theorems mentioned in the introduction as well as their corollaries in Sect. 6.2. Finally, in Sect. 6.3, we apply our results to a family of permutational wreath products of groups (including standard wreath products). See Corollary 6.7.

6.1 Coarse simple connectivity of lamplighters

In this section, our goal is to distinguish geometrically lamplighters over one-ended and multi-ended groups. Our argument is based on the following characterisation of coarsely simply connected lamplighter graphs.

Proposition 6.1

Let $X$ be a graph and $n \geq 2$ an integer. The lamplighter graph $\mathcal{L}_{n}(X)$ is coarsely simply connected if and only if $X$ is bounded.

Proof

First, assume that $X$ is unbounded. So, for every $k \geq 1$, there exist two vertices $a_{k},b_{k} \in X$ satisfying $d(a_{k},b_{k}) \geq k$. Denote by $\alpha _{k}$ (resp. $\beta _{k}$) the colouring that is 1 at $a_{k}$ (resp. $b_{k}$) and 0 elsewhere. Also, denote by $Y_{k} \subset \mathcal{L}_{n}(X)$ the subgraph generated by $X(0) \cup X(\alpha _{k}) \cup X(\beta _{k}) \cup X(\alpha _{k} + \beta _{k})$. Notice that the map

$$ \left \{ \textstyle\begin{array}{ccc} \mathcal{L}_{n}(X) & \to & Y_{k} \\ (c,x) & \mapsto & \left ( c_{k} : p \mapsto \left \{ \textstyle\begin{array}{cl} c(a_{k}) & \text{if $p=a_{k}$} \\ c(b_{k}) & \text{if $p=b_{k}$} \\ 0 & \text{otherwise} \end{array}\displaystyle \right ., \ x \right ) \end{array}\displaystyle \right . $$

is 1-Lipschitz. Therefore, if $\mathcal{L}_{n}(X)$ is coarsely simply connected, then the subgraphs $Y_{k}$ must be uniformly coarsely simply connected, i.e. there exists some $R \geq 0$ such that, for every $k\geq 1$, the 2-complex obtained from $Y_{k}$ by filling in with discs the cycles of lengths $\leq R$ is simply connected. However, $Y_{k}$ is the disjoint union of $X(0)$, $X(\alpha _{k})$, $X(\beta _{k})$ and $X(\alpha _{k}+\beta _{k})$, connected together by four edges: one between $(0,a_{k})$ and $(\alpha _{k},a_{k})$, one between $(0,b_{k})$ and $(\beta _{k},b_{k})$, one between $(\alpha _{k},b_{k})$ and $(\alpha _{k}+\beta _{k},b_{k})$, and one between $(\beta _{k},a_{k})$ and $(\alpha _{k}+\beta _{k},a_{k})$. Clearly, every simple loop of length $<4(d(a_{k},b_{k})+1)$ in $Y_{k}$ must lie inside $X(0)$, $X(\alpha _{k})$, $X(\beta _{k})$ or $X(\alpha _{k}+\beta _{k})$, so $Y_{k}$ is not $(4d(a_{k},b_{k})+3)$-coarsely simply connected, and a fortiori not $(4k+3)$-coarsely simply connected. We conclude that $\mathcal{L}_{n}(X)$ is not coarsely simply connected, as desired.

Now, assume that $X$ is bounded. Let $P(X,n)$ denote the graph whose vertices are the finitely supported colourings $X \to \mathbb{Z}_{n}$ and whose edges connect two colourings if they differ at a single vertex. Notice that the distance between two colourings in $P(X,n)$ coincides with the number of vertices where they differ. The map

$$ \left \{ \textstyle\begin{array}{ccc} \mathcal{L}_{n}(X) & \to & P(X,n) \\ (c,x) & \mapsto & c \end{array}\displaystyle \right . $$

is a quasi-isometry since

$$ d(c_{1},c_{2}) \leq d((c_{1},x_{1}),(c_{2},x_{2})) \leq \mathrm{diam}(X) \left ( 2 d(c_{1},c_{2})+1 \right ) $$

for all $(c_{1},x_{1}),(c_{2},x_{2}) \in \mathcal{L}_{n}(X)$. Therefore, it suffices to show that $P(X,n)$ is coarsely simply connected in order to deduce that $\mathcal{L}_{n}(X)$ is coarsely simply connected. But $P(X,n)$ is just (a connected component of) a product of infinitely many complete graphs (in other words, it is the 1-skeleton of an infinite-dimensional prism), so it is 4-coarsely simply connected. □

Corollary 6.2

Let $F_{1}$, $F_{2}$ be two finite groups and $H_{1}$, $H_{2}$ two finitely presented groups. If $H_{1}$ is one-ended and $H_{2}$ multi-ended, then $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are not quasi-isometric.

Our proof of the corollary is based on the following elementary observation. Here, given a graph $X$ and a collection of subgraphs $\mathcal{P}$, we refer to the cone-off of $X$ over $\mathcal{P}$ as the graph obtained from $X$ by adding an edge between any two vertices that belong to a common subgraph from $\mathcal{P}$.

Lemma 6.3

Let $X$ be a graph and $\mathcal{P}$ a family of subgraphs. For every colouring $c \in \mathbb{Z}_{n}^{(X)}$, let $\mathcal{P}(c)$ denote the copy of $\mathcal{P}$ in the copy $X(c)$ of $X$ in $\mathcal{L}_{n} (X)$. The cone-off $\dot{\mathcal{L}}$ of $\mathcal{L}_{n}(X)$ over $\bigcup _{c \in \mathbb{Z}_{n}^{(X)}} \mathcal{P}(c)$ coincides with the lamplighter graph $\mathcal{L}_{n}(\dot{X})$ over the cone-off of $X$ over $\mathcal{P}$.

Proof

Clearly, $\dot{\mathcal{L}}$ and $\mathcal{L}_{n}(\dot{X})$ have the same vertices, namely the pairs $(c,x)$ where $c \in \mathbb{Z}_{n}^{(X)}$ and $x \in X$. Two pairs $(c_{1},x_{1})$ and $(c_{2},x_{2})$ are adjacent in $\dot{\mathcal{L}}$ if and only if they are adjacent in $\mathcal{L}_{n}(X)$ or if they belong to a common subgraph from $\mathcal{P}(c)$ for some $c \in \mathbb{Z}_{n}^{(X)}$. The latter case happens exactly when $c_{1}=c_{2}$ and $x_{1}$, $x_{2}$ belong to a common subgraph from $\mathcal{P}$. Thus, $(c_{1},x_{1})$ and $(c_{2},x_{2})$ are adjacent in $\dot{\mathcal{L}}$ if and only if either $c_{1}$, $c_{2}$ only differ at $x_{1}=x_{2}$ or $c_{1}=c_{2}$ and $x_{1}$, $x_{2}$ are adjacent in $\dot{X}$. This is exactly the adjaceny relation in $\mathcal{L}_{n}(\dot{X})$. □

Proof of Corollary 6.2

Assume towards a contradiction that there exists a quasi-isometry $q : F_{1} \wr H_{1} \to F_{2} \wr H_{2}$. According to Theorem 1.4, $q(H_{1})$ lies in a neighbourhood of some $H_{2}$-coset, say $H_{2}$ itself. In fact, $q(H_{1})$ must lie in a neighbourhood of some coset of a one-ended factor $M \leq H_{2}$ coming from the Stallings-Dunwoody decomposition of $H_{2}$, say $M$ itself. Notice that, because there exists a Lipschitz quasi-retraction $H_{2} \to M$, $M$ must be finitely presented. By applying Theorem 1.4 once again, it follows that the image of $M$ under a quasi-inverse $\bar{q}$ of $q$ lies in a neighbourhood of some coset $hH_{1}$. Notice that $\bar{q}(q(H_{1}))$ lies in a neighbourhood of both $H_{1}$ and $hH_{1}$. But we know from Fact 2.3 that the intersection in $F_{1} \wr H_{1}$ of two neighbourhoods of distinct $H_{1}$-cosets has finite diameter, so we must have $hH_{1}=H_{1}$. We also deduce that $q$ sends $H_{1}$ at finite Hausdorff distance from $M$.

As a consequence, $q$ induces a quasi-isometry from the space $X$ obtained from $F_{1} \wr H_{1}$ by coning-off the cosets of $H_{1}$ and the space $Y$ obtained from $F_{2} \wr H_{2}$ by coning-off the cosets of $M$ which are at finite Hausdorff distance from the images under $q$ of the cosets of $H_{1}$. According to Lemma 6.3, $X$ coincides with the lamplighter graph over the coning-off of $H_{1}$ over $H_{1}$ (which is bounded), and $Y$ with the lamplighter graph over the coning-off of $H_{2}$ over cosets of $M$ (which is unbounded since $H_{2}$ is multi-ended). Thus, we get a contradiction with Proposition 6.1, proving that $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ cannot be quasi-isometric, as desired. □

6.2 Proofs of the theorems

We are finally ready to prove the main result of this article, namely Theorem 1.5 from the introduction, as well as all its corollaries, by combining the various statements proved in Sects. 3, 4 and 5. We begin by proving a quantitative version of Theorem 1.19.

Theorem 6.4

Let $n,m \geq 2$ be two integers and $X$, $Y$ two coarsely simply connected uniformly one-ended graphs of bounded degree. For all $A,B \geq 0$, there exists a constant $Q \geq 0$ such that every $(A,B)$-quasi-isometry $\mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ lies at distance $\leq Q$ from an aptolic quasi-isometry.

Proof

Fix an $(A,B)$-quasi-isometry $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$ and one of its quasi-inverses $\bar{q} : \mathcal{L}_{m}(Y) \to \mathcal{L}_{n}(X)$ (whose parameters depend only of $A$, $B$). As a consequence of Theorem 5.1, for every leaf $L_{1}$ in $\mathcal{L}_{n}(X)$, the image $q(L_{1})$ lies in $K$-neighbourhood of some leaf $L_{2}$ in $\mathcal{L}_{m}(Y)$ for some constant $K \geq 0$, which only depends on $X$, $Y$, $A$ and $B$. Similarly, $\bar{q}(L_{2})$ lies in the $K$-neighbourhood of some leaf $L_{3}$ in $\mathcal{L}_{n}(X)$ (up to increasing the constant $K$). Consequently, $\bar{q}(q(L_{1}))$ lies in a neighbourhood of both $L_{1}$ and $L_{3}$. But the intersection in $\mathcal{L}_{n}(X)$ of two neighbourhoods of distinct leaves has finite diameter, so we must have $L_{3}=L_{1}$. We conclude that $q$ sends $L_{1}$ at Hausdorff distance at most $C$ from $L_{2}$, for some constant $C\geq 0$, which only depends on $X$, $Y$, $A$ and $B$. Thus, we have proved that $q$ sends every leaf of $\mathcal{L}_{n}(X)$ at Hausdorff distance $\leq C$ from a leaf of $\mathcal{L}_{m}(Y)$. In other words, there exists a map $\alpha : \mathbb{Z}_{n}^{(X)} \to \mathbb{Z}_{m}^{(Y)}$ such that the Hausdorff distance between $q(X(c))$ and $Y(\alpha (c))$ is $\leq C$ for every $c \in \mathbb{Z}_{n}^{(X)}$.

Similarly, there must exist a map $\bar{\alpha} : \mathbb{Z}_{m}^{(Y)} \to \mathbb{Z}_{n}^{(X)}$ such that the Hausdorff distance between $\bar{q}(Y(c))$ and $X(\bar{\alpha}(c))$ is $\leq C$ for every $c \in \mathbb{Z}_{m}^{(Y)}$. For every $c \in \mathbb{Z}_{n}^{(X)}$, the Hausdorff distance between $\bar{\alpha} \circ \alpha (X(c))$ and $Y(c)$ must be finite; and, for every $c \in \mathbb{Z}_{m}^{(Y)}$, the Hausdorff distance between $\alpha \circ \bar{\alpha} (Y(c))$ and $X(c)$ must be finite as well. Hence $\alpha \circ \bar{\alpha}= \mathrm{id}$ and $\bar{\alpha} \circ \alpha = \mathrm{id}$. In other words, $\alpha$ is a bijection.

We conclude from Theorem 4.3 that $q$ lies at finite distance from an aptolic quasi-isometry, as desired, where the constant depends only on $A$, $B$. □

Proof of Theorem 1.5

Assume that there exists a quasi-isometry $q : \mathcal{L}_{n}(X) \to \mathcal{L}_{m}(Y)$. As a consequence of Theorem 1.19, we can suppose without loss of generality that $q$ is aptolic. If $X$ is amenable, then the desired conclusion follows from Theorem 3.9 and Proposition 3.12.

Next, assume that $X$ is non-amenable. If $\mathcal{L}_{n}(X)$ and $\mathcal{L}_{m}(Y)$ are quasi-isometry, then, according to Proposition 3.4, $n$ and $m$ must have the same prime divisors; and, according to Proposition 3.1, $X$ and $Y$ must be quasi-isometric. Conversely, if $X$ and $Y$ are quasi-isometric, then they are biLipschitz equivalent according to Theorem 1.13, so $\mathcal{L}_{n}(X)$ and $\mathcal{L}_{n}(Y)$ are quasi-isometric according to Corollary 3.3; and, if we know that $n$, $m$ have the same prime divisors, then $\mathcal{L}_{n}(Y)$ and $\mathcal{L}_{m}(Y)$ are quasi-isometric according to Proposition 3.13. The desired conclusion follows. □

Proof of Theorem 1.12

If $F_{1}$ is trivial, then $F_{2} \wr H_{2}$ must be finitely presented (because quasi-isometric to the finitely presented group $H_{1}$) which implies that either $F_{2}$ is trivial or $H_{2}$ is finite. In both cases, $H_{1}$ and $H_{2}$ are quasi-isometric. The same conclusion holds if $F_{2}$ is trivial, so from now on we assume that $F_{1}$ and $F_{2}$ are both non-trivial. The conclusion is also clear if $H_{1}$ or $H_{2}$ is finite, so we assume that they are both infinite. We distinguish two cases.

If $H_{1}$ is one-ended, it follows from Corollary 6.2 that $H_{2}$ is one-ended as well. So Theorem 1.19 applies and shows that there exists an aptolic quasi-isometry $F_{1} \wr H_{1} \to F_{2} \wr H_{2}$. We conclude from Proposition 3.1(ii) that $H_{1}$ and $H_{2}$ are quasi-isometric.

Next, assume that $H_{1}$ is multi-ended. According to Corollary 6.2, $H_{2}$ is multi-ended as well. If $H_{1}$ is two-ended (or equivalently if $H_{1}$ is virtually infinite cyclic), then $F_{1} \wr H_{1}$ is amenable and so must be $F_{2} \wr H_{2}$. Since infinitely-ended groups contain non-abelian free subgroups, necessarily $H_{2}$ must be two-ended (or equivalently virtually infinite cyclic). A fortiori, $H_{1}$ and $H_{2}$ are quasi-isometric. The same conclusion holds if $H_{2}$ is two-ended, so from now on we assume that $H_{1}$, $H_{2}$ are both infinitely-ended. According to [39], it suffices to show that $H_{1}$, $H_{2}$ have the same one-ended factors (up to quasi-isometry) in their Stallings-Dunwoody decompositions in order to deduce that they are quasi-isometric. Let $M \leq H_{1}$ be such a factor. Notice that, since there exists a Lipschitz quasi-retraction $H_{1} \to M$, the subgroup $M$ must be finitely presented. Therefore, Theorem 1.4 applies and shows that $q(M)$ lies in a neighbourhood of a coset of $H_{2}$, say $H_{2}$. In fact, $q(M)$ must lie in a neighbourhood of a coset of a one-ended factor $M'$ of $H_{2}$, say $M'$ itself. Similarly, the image of $M'$ under a quasi-inverse $\bar{q}$ lies in a neighbourhood of a coset $hM''$ of some one-ended factor of $H_{1}$. But the intersection in $F_{1} \wr H_{1}$ of two neighbourhoods of distinct $H_{1}$-cosets has finite diameter, and the intersection in $H_{1}$ of two neighbourhoods of distinct cosets of one-ended factors has finite diameter as well, so necessarily $hM''=M$. In other words, $q$ sends $M$ at finite Hausdorff distance from $M'$. Thus, we have proved that every one-ended factor of $H_{1}$ is quasi-isometric to a one-ended factor of $H_{2}$. The converse follows by symmetry, proving that $H_{1}$ and $H_{2}$ are quasi-isometric, as desired. □

Now, we focus on the corollaries mentioned in the introduction.

Proof of Corollary 1.6

Assume that there exists a quasi-isometry $q : F_{1} \wr H_{1} \to F_{2} \wr H_{2}$. Notice that, as a consequence of Theorem 1.12, $H_{2}$ must be one-ended. Therefore, Theorem 1.5 applies and leads to the desired conclusion. □

Proof of Corollary 1.10

According to Corollary 1.9, it suffices to show that, for every $n \geq 1$, the inclusion $\mathbb{Q}_{>0} \subset \kappa (\mathbb{Z}^{n})$ holds. Notice that, for every $k \geq 1$, the embedding $k \mathbb{Z} \oplus \mathbb{Z}^{n-1} \hookrightarrow \mathbb{Z}^{n}$ induces a quasi-isometry $q_{k} : \mathbb{Z}^{n} \to \mathbb{Z}^{n}$ that is quasi-$(1/k)$-to-one (apply for instance Proposition 2.9(iii)); let $\bar{q}_{k}$ denote a quasi-inverse of $q_{k}$. It follows from Proposition 2.8 that, for every $a,b \geq 1$, the quasi-isometry $\bar{q}_{a} \circ q_{b}$ is quasi-$(a/b)$-to-one, concluding the proof. □

Proof of Corollary 1.15

If $|F_{1}|=|F_{1}|$, then $F_{1} \wr H$ and $F_{2} \wr H$ admits isomorphic Cayley graphs, namely $\mathrm{Cayl}(F_{1} \wr H, F_{1} \cup S)$ and $\mathrm{Cayl}(F_{2} \wr H, F_{2} \cup S)$ where $S$ is an arbitrary finite generating set of $H$. A fortiori, these wreath products must be biLipschitz equivalent. Conversely, assume that there exists a biLipschitz equivalence $q : F_{1} \wr H \to F_{2} \wr H$. According to Theorem 1.19, $q$ is at finite distance from an aptolic quasi-isometry $\tilde{q} : F_{1} \wr H \to F_{2} \wr H$; and, according to Theorem 3.9, there exist $k,n_{1},n_{2} \geq 1$ such that $|F_{1}|=k^{n_{1}}$, $|F_{2}|=k^{n_{2}}$, and such that $\tilde{q}$ is quasi-$(n_{2}/n_{1})$-to-one. We conclude from Lemma 2.7 and Proposition 2.8 that $n_{1}=n_{2}$, hence $|F_{1}|=|F_{2}|$ as desired. □

Proof of Corollary 1.16

Let $q : F \wr H \to F\wr H$ be a quasi-isometry. According to Theorem 1.19, $q$ lies at finite distance from an aptolic quasi-isometry $\tilde{q} : F \wr H \to F \wr H$; and it follows from Theorem 3.9 that $\tilde{q}$ is quasi-one-to-one. We conclude from Proposition 2.6 that $\tilde{q}$, and a fortiori $q$, lies at finite distance from a bijection. □

We now turn our attention to Corollary 1.17. Actually, we are going to prove a more general statement, but we need to introduce some vocabulary first. Given two finitely generated groups $A$, $B$, a biLipschitz commensuration is the data of two finite-index subgroups $\dot{A} \leq A$, $\dot{B} \leq B$ and a biLipschitz equivalence $\varphi : \dot{A} \to \dot{B}$. When $\varphi$ is an isomorphism, we recover the usual notion of commensuration. The index of a biLipschitz commensuration is the quotient $[A:\dot{A}]/[B:\dot{B}]$.

Proposition 6.5

Let $F$ be a non-trivial finite group and $H$ a finitely presented one-ended amenable group. Fix two groups $G_{1}$, $G_{2}$ in the biLipschitz commensuration class of $F \wr H$. If $G_{1}$ and $G_{2}$ are biLipschitz equivalent, then every biLipschitz commensuration between $G_{1}$ and $G_{2}$ has index one.

Proof

By assumption, there exist finite-index subgroups $\dot{G}_{1} \leq G_{1}$, $L \leq F\wr H$, $K_{1} \leq G_{1}$, $K_{2} \leq G_{2}$, and biLipschitz equivalences $\varphi : L \to \dot{G}_{1}$, $\phi : K_{1} \to K_{2}$, $\psi : G_{2} \to G_{1}$. For every group $B$ and every finite-index subgroup $A \leq B$, we denote by $\iota _{A,B}$ the inclusion $A \hookrightarrow B$ and we fix a quasi-inverse $\bar{\iota}_{A,B} : B \to A$. Observe that $\iota _{A,B}$ is quasi-$(1/[B:A])$-to-one and $\bar{\iota}_{A,B}$ quasi-$[B:A]$-to-one. (For instance, apply Proposition 2.9(iii).) As a consequence of Proposition 2.8, the quasi-isometry $F\wr H \to F \wr H$ defined by

$$ \Psi := \iota _{L,F\wr H} \circ \varphi ^{-1} \circ \bar{\iota}_{ \dot{G}_{1},G_{1}} \circ \left ( \psi \circ \phi \circ \bar{\iota}_{K_{1},G_{1}} \right ) \circ \iota _{\dot{G}_{1},G_{1}} \circ \varphi \circ \bar{\iota}_{L,F\wr H} $$

is quasi-$([G_{1}:K_{1}]/[G_{2}:K_{2}])$-to-one. The combination of Corollary 1.16 and Lemma 2.7 implies that $[G_{1}:K_{1}]=[G_{2}:K_{2}]$ as desired. □

6.3 Permutational wreath products

It is worth noticing that Theorem 1.5 also applies to another kind of wreath products.

Definition 6.6

Let $F$, $H$ be two groups and $X$ a set on which $H$ acts. The permutational product of $F$, $H$ with respect to $H \curvearrowright X$ is

$$ F \wr _{X} H:= \left ( \bigoplus \limits _{X} F \right ) \rtimes H $$

where $H$ acts on the direct sum by permuting the coordinates through its action on $X$.

Observe that, if $H$ acts freely and transitively on $X$, then $F \wr _{X} H$ coincides with $F \wr H$. Corollary 6.7 below shows that the classification provided by Corollary 1.6 extends to the case where $H$ acts on $X$ transitively and with finite stabilisers, which coincides with a permutational wreath product $F \wr _{H/L} H$ for some finite subgroup $L \leq H$.

Corollary 6.7

Let $F_{1}$, $F_{2}$ be two finite groups, $H_{1}$, $H_{2}$ two finitely presented one-ended groups, and $X_{1}$, $X_{2}$ two sets on which $H_{1}$, $H_{2}$ respectively act with finitely many orbits (say $m_{1}$, $m_{2}$) and with finite stabilisers. For every $1 \leq i \leq m_{1}$ (resp. $1 \leq i \leq m_{2}$), let $p_{i}$ (resp. $q_{i}$) denote the size of point-stabilisers in the $i$th $H_{1}$-orbit of $X_{1}$ (resp. in the $i$th $H_{2}$-orbit of $X_{2}$).

• If $H_{1}$ is amenable, then $F_{1} \wr _{X_{1}} H_{1}$ and $F_{2} \wr _{X_{2}} H_{2}$ are quasi-isometric if and only if $|F_{1}|=k^{n_{1}}$, $|F_{2}|=k^{n_{2}}$ for some $k,n_{1},n_{2} \geq 1$ and if there exists a quasi-$\kappa$-to-one quasi-isometry $H_{1} \to H_{2}$ where $\kappa :=\frac{n_{2}}{n_{1}} \left ( \frac{1}{p_{1}}+ \cdots + \frac{1}{p_{m_{1}}} \right ) \left ( \frac{1}{q_{1}} + \cdots + \frac{1}{q_{m_{2}}} \right )^{-1}$.

• If $H_{1}$ is non-amenable, then $F_{1} \wr _{X_{1}} H_{1}$ and $F_{2} \wr _{X_{2}} H_{2}$ are quasi-isometric if and only if $|F_{1}|$, $|F_{2}|$ have the same prime divisors and $H_{1}$, $H_{2}$ are quasi-isometric.

The assertion will be an easy consequence of the following observation:

Lemma 6.8

Let $F$ be a finite group, $H$ a group generated by a finite set $S$, and $X$ a set on which $H$ acts with finite stabilisers and with finitely many (say $n$) orbits. Then there exist a graph $Y$ and a quasi-$\left ( \sum \limits _{i=1}^{n} \frac{1}{\ell _{i}} \right )$-to-one quasi-isometry $H \to Y$ such that $\mathrm{Cayl}(F \wr _{X} H, F \cup S)$ and $\mathcal{L}_{|F|}( Y)$ are quasi-isometric, where $\ell _{i}$ denotes the size of point-stabilisers in the $i$th $H$-orbit of $X$.

Proof

It is clear that the graphs $\mathrm{Cayl}(F\wr _{X} H, F \cup S)$ and $\mathrm{Cayl}(\mathbb{Z}_{|F|} \wr _{X} H, \mathbb{Z}_{|F|} \cup S)$ are isomorphic. Consequently, from now on we assume that $F$ is a cyclic group, say of order $r$. Let $x_{1}, \ldots , x_{n} \in X$ be representatives modulo the $H$-action. For every $1 \leq i \leq n$, let $L_{i}$ denote $\mathrm{stab}_{H}(x_{i})$. We define $Y$ as the graph

• whose vertex-set is the disjoint union $H/L_{1} \sqcup \cdots \sqcup H/L_{n}$;

• whose edges link $hL_{i}$, $hs^{\pm 1}L_{i}$ for all $1 \leq i \leq n$, $h \in H$, $s \in S$ and $hL_{i}$, $hL_{j}$ for all $h \in H$, $1 \leq i,j \leq n$.

The graph $Y$ is clearly quasi-isometric to $H$. Fix an arbitrary map $\sigma : H/L_{1} \sqcup \cdots \sqcup H/L_{n} \to H$ satisfying $\sigma (hL_{i}) \in hL_{i}$ for all $h \in H$ and $1 \leq i \leq n$. Finally, notice that the map $\beta : Y \to X$ defined by $hL_{i} \mapsto h \cdot x_{i}$ ($h \in H$ and $1 \leq i \leq n$) is clearly a bijection. We claim that

$$ \Phi : \left \{ \textstyle\begin{array}{ccc} \mathcal{L}_{r}(Y) & \to & \mathbb{Z}_{r} \wr _{X} H \\ (c,hL_{i}) & \mapsto & \left ( c \circ \beta ^{-1}, \sigma (hL_{i}) \right ) \end{array}\displaystyle \right . \text{ and } \Psi : \left \{ \textstyle\begin{array}{ccc} \mathbb{Z}_{r} \wr _{X} H & \to & \mathcal{L}_{r}(Y) \\ (c,h) & \mapsto & \left ( c \circ \beta , hL_{1} \right ) \end{array}\displaystyle \right . $$

are quasi-isometries, quasi-inverses of each other. Let $a,b \in \mathbb{Z}_{r} \wr _{X} H$ be two adjacent vertices (in our Cayley graph). Two cases may happen:

• There exist $c \in \mathbb{Z}_{r}^{(X)}$, $h \in H$, $s \in S$ such that $a=(c,h)$ and $b=(c,hs^{\pm 1})$. Then $\Psi (a)=(c \circ \beta ,hL_{1})$ and $\Psi (b)=(c \circ \beta ,hs^{\pm 1}L_{1})$ are either identical or adjacent in $Y$.

• There exist $c \in \mathbb{Z}_{r}^{(X)}$, $h \in H$, $1 \leq i \leq n$ and $d \in \mathbb{Z}_{r}^{(X)}$ supported at $h \cdot x_{i}$ such that $a=(c,h)$ and $b=(c+d,h)$. Then $\Psi (a)=(c \circ \beta , hL_{1})$ and $\Psi (b)=(c \circ \beta + d',hL_{1})$, where $d' \in \mathbb{Z}_{r}^{(Y)}$ is supported at $hL_{i}$, are two adjacent vertices of $Y$.

Thus, we have proved that $\Psi$ sends an edge to either a point or an edge, which implies that it is 1-Lipschitz. Similarly, given two adjacent vertices $a,b \in Y$, three cases may happen:

• There exist $c \in \mathbb{Z}_{r}^{(Y)}$, $h \in H$, $1 \leq i,j \leq n$ such that $a=(c,hL_{i})$ and $b=(c,hL_{j})$. Then $\Phi (a)=(c \circ \beta ^{-1}, \sigma (hL_{i}))$ and $\Phi (b)=(c \circ \beta ^{-1}, \sigma (hL_{j}))$ are at distance at most $\mathrm{diam}_{H}(L_{i} \cup L_{j})$ in $\mathbb{Z}_{r} \wr _{X} H$.

• There exist $c \in \mathbb{Z}_{r}^{(Y)}$, $h \in H$, $1 \leq i \leq n$, $s \in S$ such that $a=(c,hL_{i})$ and $b=(c,hs^{\pm 1}L_{i})$. Then $\Phi (a)=(c \circ \beta ^{-1}, \sigma (hL_{i}))$ and $\Phi (b)=(c \circ \beta ^{-1}, \sigma (hs^{\pm 1}L_{i}))$ are at distance at most $\mathrm{diam}_{H}(L_{i} \cup s^{\pm 1}L_{j})$ in $\mathbb{Z}_{r} \wr _{X} H$.

• There exist $c \in \mathbb{Z}_{r}^{(Y)}$, $h \in H$, $1 \leq i \leq n$ and $d \in \mathbb{Z}_{r}^{(Y)}$ supported at $hL_{i}$ such that $a=(c,hL_{i})$ and $b=(c+d,hL_{i})$. Then $\Phi (a)=(c \circ \beta ^{-1},\sigma (hL_{i}))$ and $\Phi (b)=(c \circ \beta ^{-1} + d', \sigma (hL_{i}))$, where $d' \in \mathbb{Z}_{r}^{(Y)}$ is supported at $h \cdot x_{i}$, are at distance at most $1+ \mathrm{diam}_{H}(L_{i})$ in $\mathbb{Z}_{r} \wr _{X} H$.

Thus, we have also proved that $\Phi$ is Lipschitz. Finally, observe that

$$ \Phi \circ \Psi (c,h)=(c, \sigma (hL_{1})) \text{ for all $(c,h) \in \mathbb{Z}_{r} \wr _{X} H$,} $$

proving that $\Phi \circ \Psi$ lies at distance $\leq \mathrm{diam}_{H}(L_{1})$ from the identity; and that

$$ \Psi \circ \Phi (c,hL_{i}) = (c, \sigma (hL_{i})L_{1}) \text{ for all $c \in \mathbb{Z}_{r}^{(Y)}$, $h \in H$ and $1 \leq i \leq n$,} $$

proving that $\Psi \circ \Phi$ lies at distance $\leq 1+\mathrm{diam}_{H}(L_{1})$ from the identity. We conclude that $\Phi$, $\Psi$ are quasi-isometries and that $\Phi$ is a quasi-inverse of $\Psi$ (and vice-versa).

Now, set $\kappa := (1/|L_{1}| + \cdots + 1/|L_{n}|)^{-1}$. We claim that the map $f : Y \to H$ defined by $hL_{i} \mapsto \sigma (hL_{i})$, which is clearly a quasi-isometry, is quasi-$\kappa$-to-one. As a consequence of Proposition 2.8, this will imply that there exists a quasi-$(1/\kappa )$-to-one quasi-isometry $H \to Y$, as desired.

For every $1 \leq i \leq n$, let $f_{i} : H/L_{i} \to H$ denote the restriction of $f$ to the subgraph $H/L_{i} \subset Y$. Observe that $f_{i}$ is a quasi-inverse of the $|L_{i}|$-to-one projection $H \to H/L_{i}$ (where $H/L_{i}$ is thought of as a subgraph of $Y$), so $f_{i}$ is quasi-$(1/|L_{i}|)$-to-one according to Proposition 2.8; and that, for every finite subset $A \subset H$, $f^{-1}(A)$ coincides with the disjoint union $f^{-1}_{1}(A) \sqcup \cdots \sqcup f^{-1}_{n}(A)$. Therefore,

$$ \textstyle\begin{array}{lcl} \displaystyle \left | \kappa |f^{-1}(A)| - |A| \right | & = & \displaystyle \kappa \left | \sum \limits _{i=1}^{n} |f_{i}^{-1}(A)| - \sum \limits _{i=1}^{n} \frac{|A|}{|L_{i}|} \right | \leq \kappa \sum \limits _{i=1}^{n} \left | |L_{i}| \cdot |f_{i}^{-1}(A) | - |A| \right | \\ \\ & \leq & \displaystyle \kappa \sum \limits _{i=1}^{n} \frac{C_{i}}{|L_{i}|} \cdot | \partial A| \end{array} $$

for some constants $C_{1}, \ldots , C_{n}$ that do not depend on $A$. Thus, we have shown that $f$ is quasi-$\kappa$-to-one, concluding the proof of our lemma. □

Proof of Corollary 6.7

According to Lemma 6.8, there exist a graph $Y_{1}$ and a quasi-$\kappa _{1}$-to-one quasi-isometry $H_{1} \to Y_{1}$, where $\kappa _{1}:= 1/p_{1} + \cdots + 1/p_{m_{1}}$, such that $F_{1} \wr _{X_{1}} H_{1}$ and $\mathcal{L}_{|F_{1}|}(Y_{1})$ are quasi-isometric; and there exist a graph $Y_{2}$ and a quasi-$\kappa _{2}$-to-one quasi-isometry $H_{2} \to Y_{2}$, where $\kappa _{2} := 1/q_{1}+ \cdots +1/q_{m_{2}}$, such that $F_{2} \wr _{X_{2}} H_{2}$ and $\mathcal{L}_{|F_{2}|}(Y_{2})$ are quasi-isometric. Observe that, as a consequence of Proposition 2.8, there exists a quasi-$(n_{2}/n_{1})$-to-one quasi-isometry $Y_{1} \to Y_{2}$ if and only if there exist a quasi-$(n_{2}\kappa _{1}/n_{1} \kappa _{2})$-to-one quasi-isometry $H_{1} \to H_{2}$. The desired conclusion follows from Theorem 1.5. □

Remark 6.9

Let us indicate a further generalisation. Assume that $H$ is a locally compact group and that $X$ is a set on which $H$ acts with open stabilisers. If $F$ is a discrete group, then we observe that $F \wr _{X} H$ is a locally compact group. It turns out that Corollary 6.7 holds under the assumption that $H_{1}$ and $H_{2}$ are locally compact, compactly presented, one-ended, and assuming that the stabilisers are compact open (instead of finite). The statements and proofs are identical, using the definition of quasi-$\kappa$-to-one quasi-isometries between locally compact groups given in [29]. We leave the details to the reader.

7 Concluding remarks and open questions

The main question addressed in the article was the following:

Question 7.1

Let $F_{1}$, $F_{2}$ be two non-trivial finite groups and $H_{1}$, $H_{2}$ two finitely generated groups. When are $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ quasi-isometric?

Let us discuss the state of this problem regarding the results proved in this article and the rest of the literature. We distinguish different cases according to the number of ends of $H_{1}$ and $H_{2}$.

Two-ended case

When $H_{1}$ and $H_{2}$ are both infinite cyclic, the problem was solved by Eskin, Fisher, and Whyte: $F_{1} \wr \mathbb{Z}$ and $F_{2} \wr \mathbb{Z}$ are quasi-isometric if and only if $|F_{1}|$ and $|F_{2}|$ are powers of a common number [20, 21]. In fact, because virtually infinite cyclic groups are always biLipschitz equivalent, their theorem answers Question 7.1 when $H_{1}$ and $H_{2}$ are both two-ended. Moreover, as a consequence of the following observation, assuming that only $H_{1}$ is two-ended suffices.

Proposition 7.2

Let $F$ be a non-trivial finite group and $H$ a finitely generated group. The asymptotic cones of $F \wr H$ have finite topological dimension if and only if $H$ is virtually cyclic.

We were informed by private communication that this phenomenon has been also noticed by Y. Cornulier, independently.

Proof of Proposition 7.2

If $H$ is finite then there is nothing to prove, so from now on we assume that $H$ is infinite. We distinguish two cases. First, assume that $H$ has linear growth. In other words, $H$ is virtually cyclic, and it must be biLipschitz equivalent to ℤ so that $F \wr H$ is quasi-isometric to $F \wr \mathbb{Z}$. It is well-known that $F \wr \mathbb{Z}$ quasi-isometrically embed into a product of two simplicial trees (see e.g. [45, Corollary 10]), so the asymptotic cones of $F \wr \mathbb{Z}$ topologically embed into a product of two real trees. We conclude that the asymptotic cones of $F \wr \mathbb{Z}$ have finite topological dimension.

Next, assume that $H$ has super-linear growth. Fix an ultrafilter $\omega$ over ℕ, a sequence of basepoints $o=(o_{n})$, and a sequence of scaling factors $\lambda =(\lambda _{n})$. Without loss of generality, we assume that $\lambda _{n} \in \mathbb{N}$ for every $n \geq 0$. Given a $k \geq 1$, our goal is to construct a topological embedding of $[0,1]^{k}$ into $\mathrm{Cone}_{\omega}(F\wr H,o,\lambda )$. Taking $k$ arbitrarily large will prove that the topological dimension of the asymptotic cone is infinite.

For every $n \geq 0$, let $R_{n}$ denote the smallest integer such that the ball $B(o_{n},R_{n})$ has cardinality $\geq k \lambda _{n}$. Notice that $(R_{n}/\lambda _{n})$ tends to zero as $n \to + \infty$ because the fact that $H$ has super-linear growth implies that

$$ \frac{R_{n}}{\lambda _{n}}= \frac{R_{n}}{ |B(o_{n},R_{n}-1)|} \cdot \frac{| B(o_{n},R_{n}-1)|}{\lambda _{n}} \leq k \frac{R_{n}}{ |B(o_{n},R_{n}-1)|} \underset{n \to + \infty}{\longrightarrow} 0. $$

Now, fix an index $n \geq 0$. Because $B(o_{n},R_{n})$ has size $\geq k\lambda _{n}$, there exist $k$ pairwise disjoint subsets $L_{n}(1), \ldots , L_{n}(k) \subset B(o_{n},R_{n})$ of size $\lambda _{n}$. For every $1 \leq i \leq k$, we fix an enumeration $L_{n}(i)= \{\ell _{n}^{1}(i), \ldots , \ell _{n}^{\lambda _{n}}(i) \}$. Define

$$ \Psi : \left \{ \textstyle\begin{array}{ccc} [0,\lambda _{n}]^{k} & \to & F\wr H \\ (r_{1},\ldots , r_{k}) & \mapsto & \left ( h \mapsto \left \{ \textstyle\begin{array}{cl} 1& \text{if $h=\ell _{n}^{j}(i)$ for some $1 \leq i \leq k$, $1 \leq j \leq r_{i}$} \\ 0 & \text{otherwise} \end{array}\displaystyle \right ., \ o_{n} \right ) \end{array}\displaystyle \right .. $$

Observe that

$$ \sum \limits _{i=1}^{k} |r_{i}-s_{i}| \leq d \left ( \Psi (r), \Psi (s) \right ) \leq \sum \limits _{k=1}^{k} |r_{i}-s_{i}| + 2kR_{n} $$

for all $r=(r_{i}),s=(s_{i}) \in [0,\lambda _{n}]^{k}$. As a consequence, $\Psi$ induces a biLipschitz embedding

$$ \Psi _{\infty }: \underset{\simeq [0,1]^{k}}{\underbrace{\mathrm{Cone}_{\omega }\left ( [1,\lambda _{n}]^{k}, 0, \lambda \right )}} \hookrightarrow \mathrm{Cone}_{\omega }(F \wr H, o,\lambda ), $$

concluding the proof of our proposition. □

In summary, Question 7.1 is completely solved in the two-ended case:

Theorem 7.3

Let $F_{1}$, $F_{2}$ be two finite groups and $H_{1}$, $H_{2}$ two finitely generated groups. Assume that $H_{1}$ is two-ended. The groups $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are quasi-isometric if and only if $H_{2}$ is two-ended and $|F_{1}|$, $|F_{2}|$ are powers of a common number.

And, according to Theorem 1.12, the number of ends of $H$ can also be detected if we restrict ourselves to finitely presented groups. So a natural question is the following:

Question 7.4

Let $F_{1}$, $F_{2}$ be two non-trivial finite groups and $H_{1}$, $H_{2}$ two finitely generated groups. If $F_{1} \wr H_{1}$ and $F_{2} \wr H_{2}$ are quasi-isometric, do $H_{1}$ and $H_{2}$ have the same number of ends?

One-ended case

For finitely presented groups, Theorem 1.5 provides a complete answer to Question 7.1 in the one-ended case. Now, a natural problem is to determine what happens for infinitely presented groups. For instance, does Theorem 1.12 still holds? More precisely:

Question 7.5

Do there exist finitely generated groups $H_{1}$ and $H_{2}$ that are not quasi-isometric but such that $\mathbb{Z}_{2} \wr H_{1}$ and $\mathbb{Z}_{2} \wr H_{2}$ are quasi-isometric?

In this perspective, iterated wreath products are examples of interest. For instance:

Question 7.6

Let $H$ be a finitely presented group and $n,m,p,q \geq 2$ four integers. When are $\mathbb{Z}_{n} \wr (\mathbb{Z}_{m} \wr H)$ and $\mathbb{Z}_{p} \wr (\mathbb{Z}_{q} \wr H)$ quasi-isometric?

In particular, the cases $H=\mathbb{Z}$ and $H= \mathbb{Z}^{2}$ would be already interesting. Observe that iterated wreath products with different numbers of factors can be often distinguished. For instance, if $A$ is a finitely generated abelian group, then $\mathbb{Z}_{2} \wr ( \mathbb{Z}_{2} \wr A)$ and $\mathbb{Z}_{2} \wr A$ are not quasi-isometric since they have different isoperimetric profiles (see [19] for more information). However, it is not clear that such a distinction is always possible.

Question 7.7

Does there exist a finitely presented group $H$ such that $\mathbb{Z}_{2} \wr (\mathbb{Z}_{2} \wr H)$ and $\mathbb{Z}_{2} \wr H$ are quasi-isometric? $\mathbb{Z}_{2} \wr (\mathbb{Z}_{2} \wr (\mathbb{Z}_{2} \wr H))$ and $\mathbb{Z}_{2} \wr (\mathbb{Z}_{2} \wr H)$?

Infinitely-ended case

We are not aware of any answer, even partial, regarding Question 7.1 in the infinitely-ended case. The situation is different from [20, 21] since, as proved by Proposition 3.13, if $H$ is infinitely-ended and if $F_{1}$, $F_{2}$ are two finite groups whose cardinalities have the same prime divisors, then $F_{1} \wr H$ and $F_{2} \wr H$ are quasi-isometric. But our arguments do not seem to provide any valuable information either. The main reason is that, in the multi-ended case, quasi-isometries may not be at finite distance from aptolic quasi-isometries, as shown by Example 3.7. Even worse, it can be shown thanks to the quasi-isometries given by Proposition 3.8 that there exists a sequence of (uniform) quasi-isometries that are not at finite distance from aptolic quasi-isometries pointwise converging to the identity. As a consequence, quasi-isometries that are not at finite distance from aptolic quasi-isometries define a dense $G_{\delta}$ in the topological space of quasi-isometries (endowed with the topology of pointwise convergence). Loosely speaking, non-aptolic quasi-isometries are generic in the multi-ended case.

The following problem should be the next step towards a full understanding of the asymptotic geometry of lamplighter groups:

Question 7.8

Let $\mathbb{F}$ be a finitely generated free group and $n,m \geq 2$ two integers. When are $\mathbb{Z}_{n} \wr \mathbb{F}$ and $\mathbb{Z}_{m} \wr \mathbb{F}$ quasi-isometric?