# Sofic approximations and optimal quantitative orbit equivalence

Amandine Escalier Partially funded by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) – Project-ID 427320536 – SFB 1442, as well
as under Germany’s Excellence Strategy EXC 2044 –390685587, Mathematics
Münster: Dynamics–Geometry–Structure.

###### Abstract

We say that two groups are _orbit equivalent_ if they both admit an action on
a same probability space that share the same orbits. In particular the
Ornstein-Weiss theorem implies that all infinite amenable groups are orbit
equivalent to the group of integers. To refine this notion Delabie, Koivisto,
Le Maître and Tessera introduced a quantitative version of orbit equivalence
and of its measure theoretic counterpart called _measure equivalence_. They
furthermore obtained an upper bound to the possible quantification between two
given groups.
In this article we offer to answer the inverse problem (find a group being
orbit or measure equivalent to a prescribed group with prescribed
quantification) in the case of the group of integers, the lamplighter group
and Brieussel-Zheng’s diagonal products. These results moreover show that the
upper bound given by Delabie et al. is optimal: the orbit and measure
equivalences we obtain all realize the aforementioned upper bound.

###### Contents

  1. 1 Introduction
    1. 1.1 Quantitative measure equivalence
    2. 1.2 From the isoperimetric profile to the inverse problem
    3. 1.3 Main results
  2. 2 Sofic approximations
    1. 2.1 Sofic approximations
    2. 2.2 Sofic approximation of diagonal product
    3. 2.3 Growth and diameter
  3. 3 Coupling with $\mathbb{Z}$
    1. 3.1 Bijection between Sofic approximations
    2. 3.2 Quantification
  4. 4 Coupling between diagonal products
    1. 4.1 Definition of the Sofic approximation
    2. 4.2 Injection between Sofic approximation
    3. 4.3 Quantification
  5. A Diagonal products
    1. A.1 Definition of diagonal products
    2. A.2 Range and support
    3. A.3 From the isoperimetric profile to the group
  6. B Variable base
    1. B.1 Decomposition in variable base
    2. B.2 Addition in variable base
    3. B.3 Enumeration
  7. Notations Index

##  1 Introduction

A recurring theme in group theory is the description of large-scale behaviour
of groups and their geometry. A well known example is the study of groups up
to quasi-isometry: it describes the large-scale (or “coarse”) geometry from
the _metric_ point of view. A _measure_ analogue of quasi-isometry was
introduced by Gromov in [GNR93] and is called measure equivalence. A first
elementary illustration of measure equivalent groups is given by lattices in a
common locally compact group. In parallel with this measure theoretic point of
view and under the impulsion of works of Dye [Dye59, Dye63] emerged the
_ergodic_ counterpart of measure equivalence, called orbit equivalence: two
groups are orbit equivalent if they admit free measure-preserving actions on a
same standard probability space $(X,\mu)$ which share the same orbits. This
notion can be seen as a strenghtening of the previous one. Indeed orbit
equivalence implies measure equivalence, altough the converse is not
necessarily always true.

However, even without using this strenghtened version, measure equivalence
itself can show remarkable rigidity properties. For instance Furman proved
[Fur99] that any countable group which is measure equivalent to a lattice in a
simple Lie group $G$ of higher rank, is commensurable (up to finite kernel) to
a lattice in $G$. In the same vein Kida [Kid06] showed that every group which
is measure equivalent to a mapping class group is actually commensurable (up
to finite kernel) to it. More recently Guirardel and Horbez [GH21] showed that
for $n\geq 3$, any countable group that is measure equivalent to
$\mathrm{Out}(F_{n})$ is virtually isomorphic to $\mathrm{Out}(F_{n})$. On the
contrary, completely opposite to the aforementioned results, a famous theorem
of Ornstein and Weiss [OW80] implies that all amenable groups are measure
equivalent. In particular —unlike quasi-isometry— measure equivalence does
_not_ preserve coarse geometric invariants.

To overcome this issue it is therefore natural to look for some refinements of
this equivalence notion. For example Kerr and Li [KL21] offer to sharpen it by
considering the Shannon entropy of partitions associated to the actions of the
two groups. A second way to proceed is to quantify how close the two actions
are by studying the _integrability_ of the associated cocycles.

To do so, assume that $G$ and $H$ are two measure equivalent groups over a
probability space $(X,\mu)$ and denote by $X_{G}$ (resp. $X_{H}$) the
fundamental domains associated to the actions. The corresponding cocycles
$\alpha:G\times X_{H}\rightarrow H$ and $\beta:H\times X_{G}\rightarrow G$ are
defined by

$\alpha(g,x)=h\Leftrightarrow h\cdot(g\cdot x)\in
X_{H}\quad\beta(h,x)=g\Leftrightarrow g\cdot(h\cdot x)\in X_{G}.$ (1.1)

When $x\mapsto\alpha(g,x)$ and $x\mapsto\beta(h,x)$ are $L^{p}$ for all $g\in
G$ and $h\in H$, we say that the groups are $L^{p}$-measure equivalent. This
refinement allowed for example Bader, Furman and Sauer [BFS13] to obtain a new
rigidity result: they showed that any group $L^{1}$-measure equivalent to a
lattice in $SO(n,1)$ for some $n\geq 2$ is virtually a lattice in $SO(n,1)$.
It also lead Bowen to prove in the appendix of [Aus16] that volume growth was
invariant under $L^{1}$-orbit equivalence. Delabie, Koivisto, Le Maître and
Tessera offered in [DKLMT20] to extend this quantification to a family of
functions larger than $\\{x\mapsto x^{p},\ p\in[0,+\infty]\\}$ (see Definition
1.5). In [DKLMT20, CDKT22] the authors also present tools to build
equivalences and quantify them using respectively tilings of Følner sequences
and Sofic approximations.

But instead of trying to determine the integrability of a given measure
equivalence, one can also look at the inverse problem, _viz._ given a
quantification $\varphi$ and a group $G$, find a group that is measure
equivalent to $G$ with this prescribed integrability $\varphi$.

This is the problem we address in this article. To tackle this question we
rely on the monotonicity of the isoperimetric profile under quantitative
measure equivalence (see Theorem 1.11) and on the construction made by
Brieussel and Zheng [BZ21] of groups with prescribed isoperimetric profile
called _diagonal products_. Using these tools we first exhibit a group that is
orbit equivalent to $\mathbb{Z}$ with a prescribed quantification (see Section
1.3). In a second time we construct a measure equivalence coupling between two
diagonal products (see Section 1.3). In both cases we compare the obtained
couplings to the constraints given by Theorem 1.11 and show that our couplings
are optimal as precised in Section 1.2. Before looking at these results, we
recall some material about quantitative measure equivalence couplings in
Section 1.1 and connect it with the isoperimetric profile in Section 1.2.

###  1.1 Quantitative measure equivalence

Let us recall some material of [DKLMT20]. A _measure-preserving action_ of a
discrete countable group $G$ on a measured space $(X,\mu)$ is an action of $G$
on $X$ such that the map sending $(g,x)$ to $g\cdot x$ is a Borel map and
$\mu(E)=\mu(g\cdot E)$ for all $E\subseteq\mathcal{B}(X)$ and all $g\in G$. We
will say that a measure-preserving action of $G$ on $(X,\mu)$ is _free_ if for
almost every $x\in X$ we have $g\cdot x=x$ if and only if $g=\mathbf{e}_{G}$.

######  Definition 1.1 ([DKLMT20, Def. 2.3]).

Let $G$ and $H$ be two countable groups. A _measure equivalence coupling_ from
$G$ to $H$ is a quadruple $(X,X_{G},X_{H},\mu)$ such that:

  * •

$(X,\mu)$ is a standard measure space equipped with measure-preserving,
commuting, smooth, free actions of $G$ and $H$,

  * •

$X_{G}$ (resp. $X_{H}$) is a fundamental domain of finite measure for the
action of $G$ (resp. $H$) on $X$.

We say that $G$ and $H$ are _measure equivalent_ if there exists a measure
equivalence coupling from $G$ to $H$.

As mentioned earlier, two lattices in the same locally compact group are
measure equivalent. Remark that our definition is asymmetric, we talk indeed
of a coupling _from_ one group _to_ another. This asymmetry might be
unsettling for now since it is called measure _equivalence_ but it will make
sense when we will define the quantification of the coupling (see Definition
1.5). Let us now introduce a stronger equivalence relation between groups
which comes from ergodic theory.

######  Definition 1.2.

Let $G$ and $H$ be two finitely generated groups. We say that $G$ and $H$ are
_orbit equivalent_ if there exists a probability space $(X,\mu)$ and two
measure-preserving free actions of $G$ and $H$ on $(X,\mu)$ such that for
almost every $x\in X$ we have $G\cdot x=H\cdot x$. We call $(X,\mu)$ an _orbit
equivalence coupling_ from $G$ to $H$.

We called this equivalence relation stronger than measure equivalence because
orbit equivalence _implies_ measure equivalence. But the converse is not
always true. To ensure that two measure equivalent groups are orbit equivalent
we need the two fundamental domains $X_{G}$ and $X_{H}$ to be equal. This is
what we formalise below.

######  Proposition 1.3.

Two countable groups $G$ and $H$ are orbit equivalent if and only if there
exists a measure equivalence coupling $(X,X_{G},X_{H},\mu)$ from $G$ to $H$
such that $X_{H}=X_{G}$.

Although this orbit equivalence relation is stronger than measure equivalence,
it does not distinguish amenable groups. Indeed by the Ornstein Weiss theorem
[OW80, Th. 6] below, all infinite amenable groups are in the same equivalence
class.

######  Theorem 1.4 ([OW80]).

All infinite amenable groups are orbit equivalent to $\mathbb{Z}$.

To refine this equivalence relation and “distinguish” amenable groups we
introduce a quantified version of orbit and measure equivalence.

Recall that if a finitely generated group $G$ acts on a space $X$ and if
$S_{G}$ is a finite generating set of $G$, we can define the Schreier graph
associated to this action as being the graph whose set of vertices is $X$ and
set of edges is $\\{(x,s\cdot x)\,|\,s\in S_{K}\\}$. This graph is endowed
with a natural metric $d_{S_{G}}$ fixing the length of an edge to one. Remark
that if $S^{\prime}_{G}$ is another generating set of $G$ then there exists
$C>0$ such that for all $x\in X$ and $g\in G$

$\frac{1}{C}d_{S_{G}}(x,g\cdot x)\leq d_{S^{\prime}_{G}}(x,g\cdot x)\leq
Cd_{S_{G}}(x,g\cdot x).$

Finally if $(X,X_{G},X_{H},\mu)$ is a measure equivalence coupling from $G$ to
$H$ we have a natural action of $G$ on $X_{H}$ (see Figure 1 for an
illustration) denoted by $\bullet$ where for all $x\in X_{H}$ and $g\in G$ we
define $g\bullet x$ to be the unique element of $H\cdot g\cdot x$ contained in
$X_{H}$ _viz._

$\\{g\bullet x\\}=\left(H\cdot g\cdot x\right)\cap X_{H}.$

To formulate this in terms of cocycles, if $\alpha:G\times X\rightarrow H$ is
the cocycle introduced in eq. 1.1 then $g\bullet x=\alpha(g,x)\cdot g\cdot x$.

######  Definition 1.5 ([DKLMT20, Def. 2.20]).

Let $\varphi,\psi:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ be two non-
decreasing maps. We say that a measure equivalence coupling
$(X,X_{G},X_{H},\mu)$ from $G$ to $H$ is _$(\varphi,\psi)$ -integrable_ if for
all $g\in G$ (resp. $h\in H$) there exists $c_{g}>0$ (resp. $c_{h}>0$) such
that both

$\int_{X_{H}}\varphi\left(\frac{1}{c_{g}}d_{S_{H}}(g\cdot x,g\bullet
x)\right)\mathrm{d}\mu(x)\quad\text{and}\quad\int_{X_{G}}\psi\left(\frac{1}{c_{h}}d_{S_{G}}(h\cdot
x,h\bullet x)\right)\mathrm{d}\mu(x)$

are finite. We say that the coupling is _$L^{\infty}$ -integrable_ if the map
$x\mapsto d_{S_{H}}(s\cdot x,s\bullet x)$ is essentially bounded. We say that
an orbit equivalence coupling is _$(\varphi,\psi)$ -integrable_ if it is
$(\varphi,\psi)$-integrable as a measure equivalence coupling.

Figure 1: Definition of $g\bullet x$

We introduce the constants $c_{g}$ and $c_{h}$ in the definition for the
integrability to be independent of the choice of generating sets $S_{G}$ and
$S_{H}$.

######  Remark 1.6.

Denote by $|g|_{S}$ the length of $g$ in $G=\langle{S}\rangle$. An equivalent
manner to formulate the above definition using cocycles is to replace
$d_{S_{H}}(g\cdot x,g\bullet x)$ and $d_{S_{G}}(h\cdot x,h\bullet x)$ in the
integrals by $|\alpha(g,x)|_{S_{H}}$ and $|\beta(h,x)|_{S_{H}}$ respectively.

If $\varphi(x)=x^{p}$ we will sometimes replace $\varphi$ by $L^{p}$ and thus
talk of $(L^{p},\psi)$-integrability instead of
$(\varphi,\psi)$-integrability. In particular $L^{0}$ means that no
integrability assumption is made. Finally, note that every
$(L^{\infty},\psi)$-integrable coupling is $(\varphi,\psi)$-integrable for any
increasing map $\varphi:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$. When
$\varphi=\psi$ we will say that the coupling is $\varphi$-integrable instead
of $(\varphi,\varphi)$-integrable.

######  Example 1.7.

Shalom proved in [Sha04] that two quasi-isometric amenable groups are
$L^{\infty}$-measure equivalent.

######  Example 1.8.

Delabie et al. obtained the following examples using a technique of tiling of
Følner sequences (see [DKLMT20, Section 6]).

  1. 1.

Let $n,m\geq 1$. There exists an orbit equivalence coupling from
$\mathbb{Z}^{m}$ to $\mathbb{Z}^{n}$ which is $(L^{p},L^{q})$-integrable for
all $p<n/m$ and $q<m/n$.

  2. 2.

Let $m\geq 2$. There exists an orbit equivalence coupling between $\mathbb{Z}$
and $\mathbb{Z}/m\mathbb{Z}\wr\mathbb{Z}$ that is
$(\exp,\varphi_{\varepsilon})$-integrable for all $\varepsilon>0$ where

$\varphi_{\varepsilon}(x)=\frac{\log(x)}{\log(\log(x))^{1+\varepsilon}}.$

  3. 3.

There exists an orbit equivalence coupling between $\mathbb{Z}^{4}$ and the
Heisenberg group $\mathrm{Heis}(\mathbb{Z})$ that is $L^{p}$-integrable for
all $p<1$.

In the light of these last examples, a natural question to ask is whether
there exists obstructions for finding $\varphi$-integrable couplings between
two amenable groups, for a given function $\varphi$. A first answer —and thus
a first obstruction— is given by the isoperimetric profile.

###  1.2 From the isoperimetric profile to the inverse problem

We saw that these equivalence notions do not preserve coarse geometric
invariants. However the quantified version defined above allowed Delabie et
al. [DKLMT20] to get a relation between the isoperimetric profiles of two
measure equivalent groups which we describe below. But first let us introduce
some notations.

######  Notation 1.9.

If $f$ and $g$ are two real functions we denote $f\preccurlyeq g$ if there
exists some constant $C>0$ such that $f(x)=\mathcal{O}\big{(}g(Cx)\big{)}$ as
$x$ tends to infinity. We write $f\simeq g$ if $f\preccurlyeq g$ and
$g\preccurlyeq f$.

Recall that if $G$ is generated by a finite set $S$, the _isoperimetric
profile_ of $G$ is defined as111We chose to adopt the convention of [DKLMT20].
Note that in [BZ21], the isoperimetric profile is defined as
$\Lambda_{G}=1/I_{G}$.

$I_{G}(n):=\sup_{|A|\leq n}\frac{|A|}{|\partial A|}.$

Remark that due to Følner criterion, a group is amenable if and only if its
isoperimetric profile is unbounded. Hence we can see the isoperimetric profile
as a way to measure the amenability of a group: the faster $I_{G}$ tends to
infinity, the more amenable $G$ is. For example the isoperimetric profile of
$\mathbb{Z}$ verifies $I_{\mathbb{Z}}(n)\simeq n$. A famous result of Erschler
[Ers03] gives the two following examples.

######  Examples 1.10.

  * •

Let $q\geq 2$ and $d\geq 1$. If $G:=\mathbb{Z}/q\mathbb{Z}\wr\mathbb{Z}^{d}$
then $I_{G}(n)\simeq(\log(n))^{1/d}$.

  * •

If $G:=\mathbb{Z}\wr\mathbb{Z}$ then $I_{G}(n)\simeq\log(n)/\log\circ\log(n)$.

The following theorem shows the monotonicity of the isoperimetric profile
under measure equivalence.

######  Theorem 1.11 ([DKLMT20, Th.1]).

Let $G$ and $H$ be two finitely generated groups admitting a
$(\varphi,L^{0})$-integrable measure equivalence coupling. If $\varphi$ and
$t/\varphi(t)$ are increasing then

$\varphi\circ I_{H}\preccurlyeq I_{G}.$

This theorem provides an obstruction for finding $\varphi$-integrable
couplings with certain functions $\varphi$ between two amenable groups. For
example we can deduce from the preceding examples that there is no $L^{1}$
measure equivalence coupling from $\mathbb{Z}\wr\mathbb{Z}$ to
$\mathbb{Z}/2\mathbb{Z}\wr\mathbb{Z}$.

The above theorem lead Delabie et al. to ask the following question.

######  Question 1.12 ([DKLMT20, Question 1.2]).

Given an amenable finitely generated group $G$, does there exist a
$(I_{G},L^{0})$-integrable orbit equivalence coupling from $G$ to
$\mathbb{Z}$?

This interrogation contains actually two questions: first it asks whether
Theorem 1.11 is optimal when $H=\mathbb{Z}$. We answer it positively in
Section 1.3 for a large family of $G$ and investigate its generalisation to
any group $H$.

######  Question 1.13.

Given two groups $G$ and $H$ is there a $\varphi$-integrable measure
equivalence coupling from $G$ to $H$ such that $I_{G}\simeq\varphi\circ
I_{H}$?

As we will see, the couplings obtained with $G=\mathbb{Z}$ in Section 1.3 and
the one given by Section 1.3 answer the above Question 1.13 positively.

Second, the question of Delabie et al. raises the matter of the “inverse
problem” —stated here for any group $G$.

######  Question 1.14.

Given a group $H$ and a function $\varphi$ does there exist a group $G$ such
that there exists a $(\varphi,L^{0})$-measure equivalent from $G$ to $H$?

When $H=\mathbb{Z}$, we answered this question in [Esc22] for a large family
of maps $\varphi$.

######  Theorem 1.15 ([Esc22, Theorem 1.8]).

For all non-decreasing function $\rho:[1,+\infty[\rightarrow[1,+\infty[$ such
that $x/\rho(x)$ is non-decreasing, there exists a group $G$ such that

  * •

$I_{G}\simeq\rho\circ\log$;

  * •

there exists an orbit equivalence coupling from $G$ to $\mathbb{Z}$ that is
$(\varphi_{\varepsilon},\exp\circ\rho)$-inte- grable for all $\varepsilon>0$,
where

$\varphi_{\varepsilon}(x):={\rho\circ\log(x)}/{\left(\log\circ\rho\circ\log(x)\right)^{1+\varepsilon}}.$

This coupling however is only optimal up to a logarithmic error. Changing of
quantification technique, we propose here an answer with optimal integrability
both for $H=\mathbb{Z}$ (Section 1.3) or $H$ a diagonal product (Section 1.3).
We also refer to the paragraph named “Couplings building techniques and
optimality” (Section 1.3) for a discussion on this optimality.

###  1.3 Main results

In this article we show the two main theorems below and their following
corollaries. Figure 2 sums up these results and provides an overview of the
couplings known so far, including the ones from [DKLMT20, CDKT22]. First let

$\mathcal{C}:=\left\\{\zeta:[1,+\infty)\rightarrow[1,+\infty)\
\left|\begin{matrix}\zeta\ \text{continuous},\\\ \zeta\ \text{and}\ x\mapsto
x/\zeta(x)\text{non-decreasing}\end{matrix}\right.\right\\}.$

##### Coupling with the integers

The first result we prove provides an optimal coupling with the group of
integers with prescribed integrability. It therefore answers Question 1.14 for
$H=\mathbb{Z}$.

ThCouplingwithZ Let $\rho\in\mathcal{C}$ and $\kappa\geq 3$. If
$\left(\rho(\kappa^{m})\kappa^{-m}\right)_{m\in\mathbb{N}}$ is summable, then
there exists a group $G$ such that

  * •

$I_{G}\simeq{\rho}\circ\log$;

  * •

There exists a $({\rho}\circ\log,L^{0})$-integrable orbit equivalence coupling
from $G$ to $\mathbb{Z}$.

We compare this result with Theorem 1.15 stated above and discuss advantages
and disadvantages of each construction on Section 1.3.

Optimality Recall that $I_{\mathbb{Z}}(x)\simeq x$. We know by Theorem 1.11
that for a coupling from a group $G$ to $\mathbb{Z}$, the best integrability
we can hope for is $\varphi\simeq I_{G}$. The above theorem thus shows that it
is reached for a very large family of maps $\varphi$. In particular it answers
Question 1.13 about optimality positively.

Remark on the hypothesis The assumption made on
$\left(\rho(\kappa^{m})\kappa^{-m}\right)_{m}$ excludes groups with
isoperimetric profile $I_{G}\simeq\log$. In particular Question 1.13 is still
open when $G$ is a Lamplighter group and $H=\mathbb{Z}$.

Delabie et al. [DKLMT20] introduced a way to compose couplings: given a
measure equivalence from $G$ to $\mathbb{Z}$ and one from $\mathbb{Z}$ to some
other group $H$ we can construct a measure equivalence from $G$ to $H$.
Moreover, its integrability will be close to the optimal one suggested by
Theorem 1.11 if the growth of $I_{H}$ is close to the one of $I_{\mathbb{Z}}$.
This is the case when $H=\mathbb{Z}^{d}$.

######  Corollary 1.15.

Let $\rho\in\mathcal{C}$, let $d\in\mathbb{N}^{*}$ and $\kappa\geq 3$. If
$\left(\rho(\kappa^{m})\kappa^{-m}\right)_{m\in\mathbb{N}}$ is summable, then
there exists a group $G$ such that

  * •

$I_{G}\simeq{\rho}\circ\log$;

  * •

There exists a $({\rho}\circ\log,L^{0})$-integrable orbit equivalence coupling
from $G$ to $\mathbb{Z}^{d}$.

##### A general prescribed coupling

Our second main theorem concerns the existence of an optimal coupling between
two groups whose isoperimetric profile is prescribed. We first state the
theorem in a deliberately vague way. Its formulation will be precised in
Theorem 4.1.

ThDeltaDelta Let $\tilde{\rho},\rho\in\mathcal{C}$ with $\rho$ moreover
bijective. If

  * •

there exits $\varepsilon>0$ such that
$\tilde{\rho}\circ\rho^{-1}(x)\preccurlyeq x^{1-\varepsilon}$;

  * •

and if $\rho$ does not grow too slowly;

then there exists two groups $G$ and $H$ such that
$I_{G}\simeq\tilde{\rho}\circ\log$ and $I_{H}\simeq{\rho}\circ\log$ and there
exists a $(\tilde{\rho}\circ\rho^{-1},L^{0})$-integrable measure equivalence
coupling from $G$ to $H$.

Remark on the hypothesis The assumption that
$\tilde{\rho}\circ\rho^{-1}(x)\preccurlyeq x^{1-\varepsilon}$ guaranties that
the coupling goes _from the bigger_ group _to the smaller_ one. Since our aim
is to check the optimality of the inequality in Theorem 1.11 and since this
inequality is true for concave maps, it makes sense to work from the bigger
group to the smaller one and not the other way round. The hypothesis on the
growth of $\rho$ will be precised in Theorem 4.1. As we will see, it will not
be that restrictive and it is verified by maps as slow as
$\rho(x)=\underbrace{\log\circ\cdots\circ\log}_{r\leavevmode\nobreak\
\text{times}}$ for $r\in\mathbb{N}$. In particular, the above theorem applies
to $\rho(x)=x$ and gives the following corollary.

CorDeltaLq Let $\tilde{\rho}\in\mathcal{C}$. If there exists $\varepsilon>0$
such that $\tilde{\rho}(x)\preccurlyeq x^{1-\varepsilon}$, then there exists a
group $G$ such that

  * •

$I_{G}\simeq\tilde{\rho}\circ\log$ ;

  * •

there exists a measure equivalence coupling from $G$ to
$\mathbb{Z}/q\mathbb{Z}\wr\mathbb{Z}$ that is
$(\tilde{\rho},L^{0})$-integrable.

We can deduce from the above result two corollaries. First define
$H:=\mathbb{Z}^{2}\rtimes_{A}\mathbb{Z}$ where $A$ is the matrix

$A:=\begin{pmatrix}2&1\\\ 1&1\end{pmatrix}.$

######  Corollary 1.15.

Let $\tilde{\rho}\in\mathcal{C}$. If there exists $\varepsilon>0$ such that
$\tilde{\rho}(x)\preccurlyeq x^{1-\varepsilon}$, then there exists a group $G$
such that

  * •

$I_{G}\simeq\rho\circ\log$;

  * •

there exists a $(\tilde{\rho},L^{0})$-integrable measure equvalence coupling
from $G$ to $H$.

Second consider $k\in\mathbb{N}^{*}$ and the Baumslag-Solitar group defined by

$BS(1,k)=\left\langle{a,b\ |\ a^{-1}ba=b^{k}}\right\rangle.$

######  Corollary 1.15.

Let $\tilde{\rho}\in\mathcal{C}$. If there exists $\varepsilon>0$ such that
$\tilde{\rho}(x)\preccurlyeq x^{1-\varepsilon}$, then there exists a group $G$
such that

  * •

$I_{G}\simeq\tilde{\rho}\circ\log$;

  * •

There exists a $(\tilde{\rho},L^{0})$-integrable measure equivalence coupling
from $G$ to $BS(1,k)$.

##### Overview

Figure 2 sums up the known results on the integrability of couplings between
the different groups appearing in this article.

Figure 2: Overview of the mentioned couplings

##### Couplings building techniques and optimality

We state in this article two results giving couplings with $\mathbb{Z}$ with
prescribed integrability: Theorem 1.15 from [Esc22] and Section 1.3. Each of
them has in fact its own interest; this what discuss here.

Theorem 1.15 was obtained using a coupling building technique called “Følner
tiling shifts”. Instead of using sofic approximations it relies on Følner
sequences defined recursively: the $n$-th term is tiled by the $(n-1)$-th term
(see [DKLMT20] for more details). This tiling technique —though inspiring— is
not always usable to get orbit or measure equivalence couplings. Indeed it
requires that the two sequences must have at each step the same cardinality,
which is possible to achieve for a coupling with the integers but not
necessarily for other groups. It was, for example, not possible to use it to
obtain our coupling between diagonal products (Theorem 4.1). Furthemore this
technique does not seem to produce couplings with optimal integrability.
Whether it is our Theorem 1.15 or Example 1.8 from [DKLMT20], the
integrability is always optimal _up to a logarithmic error_. Hence we work
here with Sofic approximations and the engineering developped in [CDKT22]
instead. It allows us to obtain couplings with optimal integrability.

Note however that where Theorem 1.15 does not require any additional
conditions on $\rho\in\mathcal{C}$, Section 1.3 does. In particular it does
not apply to $\rho\simeq\mathrm{id}$, and therefore excludes couplings from
the Lamplighter group to $\mathbb{Z}$. Hence Question 1.14 is still open for
$\varphi\simeq\log$ as well as the existence of an optimal coupling from the
Lamplighter to $\mathbb{Z}$.

So both techniques have their own advantages. Although the tiling process does
not produce optimal couplings, the proofs are technically simpler and —in
contrast to the Sofic constructions— the coupling is _explicit_ 222We refer to
[DKLMT20, Section 6] for the construction of the coupling. While at the cost
of more intricate demonstrations, the Sofic technique we used here provides
couplings with _optimal_ integrability.

##### Structure of the paper

The tools we use to build and quantify couplings are presented in Section 2.
We start by recalling material from [CDKT22] about Sofic approximations and
introduce the corresponding integrability criterion. In a second time we
construct useful Sofic approximations of Brieussel-Zheng’s diagonal products.
We use this machinerie to show Section 1.3 in Section 3, while Section 4 is
devoted to the proof of Section 1.3. The construction of the coupling with
$\mathbb{Z}$ can be seen as in introduction to the quite more technical proof
of Section 1.3. Finally an appendix sums up necessary material about diagonal
products (appendix A) and decomposition in variable base (appendix B). We
_strongly encourage_ readers unfamiliar with diagonal products _to read the
aforementioned appendix A before reading Sections 2, 3 and 4_.

24

##### Acknowledgements

I would like to thank Romain Tessera and Jérémie Brieussel, under whose
supervision the work presented in this article was carried out. I thank them
for suggesting the topic, sharing their precious insights and for their many
useful advices.

##  2 Sofic approximations

We start by recalling some results from [CDKT22] about Sofic approximations.
These are the tools needed to build couplings and quantify their
integrability. Then we construct Sofic approximations for diagonal products
and compute some useful estimates of their growth and diameter. We refer to
appendix A for the definition and properties of diagonal product.

###  2.1 Sofic approximations

We recall here some material from [CDKT22]. In this paragraph $G$ will be a
finitely generated group endowed with a finite generating set $S_{G}$ and
$(\mathcal{G}_{n})_{n\in\mathbb{N}}$ will be a sequence of finite, directed
graphs labeled by the elements of $S_{G}$. Let $r>0$ and denote by
$\mathcal{G}_{n}^{(r)}$ the set of elements $x\in\mathcal{G}_{n}$ such that
$B_{\mathcal{G}_{n}}(x,r)$ is isomorphic to $B_{G}(e_{G},r)$ seen as directed
labeled graphs, viz. $\mathcal{G}_{n}^{(r)}=\left\\{x\in\mathcal{G}_{n}\ |\
B_{\mathcal{G}_{n}}(x,r)\simeq B_{G}(e_{G},r)\right\\}$.

######  Definition 2.1.

We say that $(\mathcal{G}_{n})_{n\in\mathbb{N}}$ is a _Sofic approximation_ if
for every $r>0$

$\lim_{n\rightarrow\infty}\frac{\left|\mathcal{G}_{n}^{(r)}\right|}{\left|{\mathcal{G}_{n}}\right|}=1.$

######  Example 2.2.

Any Følner sequence in an amenable group $G$ is a Sofic approximation.

In [CDKT22] Carderi, Delabie, Koivisto and Tessera proved a condition for a
measure equivalence to be $(\varphi,L^{0})$-integrable using Sofic
approximations.

######  Theorem 2.3 ([CDKT22]).

Let $\varphi\colon\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$ be a non-decreasing
map. Let $G$ and $H$ be two finitely generated groups with Sofic
approximations $(\mathcal{G}_{n})_{n}$ and $(\mathcal{H}_{n})_{n}$ and let
$\iota_{n}\colon\mathcal{G}_{n}\rightarrow\mathcal{H}_{n}$ be an injective map
such that

  1. 1.

There exists $C>0$ such that the image of $\iota_{n}$ is $C$-dense for all
$n\in\mathbb{N}$;

  2. 2.

For every $s\in S_{G}$ there exists $\delta>0$ such that

$\lim_{R\to\infty}\sup_{n}\sum_{r=0}^{R}\varphi\\!\left(\delta
r\right)\frac{\left|\left\\{x\in\mathcal{G}_{n}^{(1)}\mid
d_{\mathcal{H}_{n}}(\iota_{n}(x),\iota_{n}(x.s))=r\right\\}\right|}{\left|\mathcal{G}_{n}\right|}<\infty;$
(2.1)

  3. 3.

For every $h\in H$ there exists $\delta>0$ such that

$\lim_{R\to\infty}\sup_{n}\sum_{r=0}^{R}\psi\left(\delta
r\right)\frac{\left|\left\\{y\in\iota_{n}(\mathcal{G}_{n})\cap\mathcal{H}_{n}^{(1)}\mid
d\left({\iota^{-1}_{n}}(y),{\iota^{{-1}}_{n}}(y\cdot
h)\right)=r\right\\}\right|}{\left|\mathcal{G}_{n}\right|}<\infty.$ (2.2)

then there exists a $(\varphi,\psi)$-integrable measure equivalence coupling
from $G$ to $H$. Moreover if the maps $\iota_{n}$ are bijective then there is
a $(\varphi,\psi)$-integrable orbit equivalence coupling from $G$ to $H$.

In [CDKT22] the authors used this theorem to obtain the following example.

######  Example 2.4 ([CDKT22, Th. 6.1]).

Let $k\geq 3$ and let $H:=\mathbb{Z}^{2}\rtimes_{A}\mathbb{Z}$ where $A$ is
the matrix

$A:=\begin{pmatrix}2&1\\\ 1&1\end{pmatrix}.$

There exists a $(L^{\infty},\exp)$-integrable measure equivalence coupling
from $\mathbb{Z}/k\mathbb{Z}\wr\mathbb{Z}$ to $H$.

###  2.2 Sofic approximation of diagonal product

In this subsection we describe Sofic approximations of diagonal products. As
we will see, these approximations are actually Følner sequences.

In the following we denote by $\Delta$ a diagonal product as defined in
appendix A verifying hypothesis (H) Section A.1.2. In particular $(k_{m})_{m}$
and $(l_{m})_{m}$ denote subsequences of geometric sequences and we let
$\kappa$ such that $(k_{m})_{m}$ is a subsequence of $(\kappa^{m})_{m}$. To
condense the proofs to come let

$\mathcal{S}_{1}:=\left\\{\big{(}(a_{m}\delta_{0})_{m},0\big{)}\ |\ a_{m}\in
A_{m}\right\\}\quad\mathcal{S}_{2}:=\left\\{\big{(}(b_{m}\delta_{k_{m}})_{m},0\big{)}\
|\ b_{m}\in B_{m}\right\\}.$ (2.3)

Finally, recall that $\mathfrak{l}(n)$ denotes the integer such that
$k_{\mathfrak{l}(n)}\leq n<k_{\mathfrak{l}(n)+1}$.

##### A first sequence

In [Esc22, Prop. 2.13] we showed that $(F_{n})_{n}$ defined in eq. 2.4 below,
is a Følner sequence for $\Delta$. We refer to Section A.2 for details on the
range of an element.

$F_{n}:=\left\\{(\bm{f},t)\in\Delta\ |\
\mathrm{range}(\bm{f},t)\in[0,n-1]\right\\}$ (2.4)

This sequence will be enough to obtain the integrability of the coupling with
$\mathbb{Z}$ wanted in Section 1.3, but not for the one of Section 1.3. We
thus introduce a finer one.

##### A refined sequence

To show Section 1.3 we will need to _control_ the speed at which the cardinal
of the Følner sets grows. More precisely if $(\mathcal{F}_{n})_{n}$ denotes
this sequence, we want it to verify
$C|\mathcal{F}_{n}|\leq|\mathcal{F}_{n+1}|\leq C^{\prime}|\mathcal{F}_{n}|$
for some constants $C,C^{\prime}>0$. Note that this is not true for
$(F_{n})_{n}$ defined above. Indeed in $F_{n+1}$, unlike in $F_{n}$, an
element $(\bm{f},t)$ can take non-trivial values at $f^{\prime}_{m}(n)$ for
_all_ $m\in[0,\mathfrak{l}(n)]$. This allows for many new elements in
$F_{n+1}$. To counter this, the idea is thus to allow $f^{\prime}_{m}(n)$ to
take non-trivial values for _one_ $m$ at a time. Moreover since
$|{\Gamma^{\prime}}_{m}|$ can grow fast, we choose for all $m$ a subset series
$(\Lambda^{m}_{j})_{j}$ of ${\Gamma^{\prime}}_{m}$ such that
$C|\Lambda^{m}_{j}|\leq|\Lambda^{m}_{j+1}|\leq C^{\prime}|\Lambda^{m}_{j}|$.
This is what we formalize below and sum up in Figure 3.

For all $i\in\mathbb{N}^{*}$ we define an integer $N_{i}>0$ and a sequence
$(\Lambda^{i}_{j})_{j\in\\{0,\ldots,N_{i}\\}}$ such that

$\begin{cases}\\{e\\}=\Lambda^{i}_{0}\subset\Lambda^{i}_{1}\subset\cdots\subset\Lambda^{i}_{N_{i}}:=\Gamma^{\prime}_{i}\\\
2|\Lambda^{i}_{j}|\leq|\Lambda^{i}_{j+1}|\leq 2q|\Lambda^{i}_{j}|\quad(\forall
j\in\\{0,\ldots N_{i}-1\\}).\end{cases}$ (2.5)

When $i=0$ define $N_{0}:=1$ and let $\Lambda^{0}_{1}:=\Gamma_{0}\sim A\times
B$.

Now for all $n\in\mathbb{N}$, all $i\in\\{0,\ldots,\mathfrak{l}(n-1)\\}$ and
$j\in\\{1,\ldots,N_{i}\\}$ we define

$F_{n,i,j}:=\left\\{\left(\bm{f},t\right)\ \left|\
{\begin{matrix}t\in[0,n-1]\\\ \mathrm{supp}(f_{0}),\
\mathrm{supp}(f^{\prime}_{m})\subset[0,n-1]&\forall m\in\\{1,\ldots,i\\}\\\
f^{\prime}_{i}(n-1)\in\Lambda^{i}_{j}\\\
\mathrm{supp}(f^{\prime}_{m})\subset[0,n-2]&\forall
m\in\\{i+1,\ldots,\mathfrak{l}(n-1)\\}\\\ f^{\prime}_{m}\equiv e&\forall
m>\mathfrak{l}(n-1)\end{matrix}}\right.\right\\}$ (2.6)

For an element $(\bm{f},t)$ of $F_{n,2,j}$, we represent the sets where
$\bm{f}$ takes its values in Figure 3.

Figure 3: An element of $F_{n,2,j}$.

Before proving that this sequence provides a Følner sequence, let us state
some conventions. For all $n\in\mathbb{N}$ and
$i\in\\{0,\ldots,\mathfrak{l}(n-1)\\}$ we define

$F_{n,i,N_{i}+1}=F_{n,i+1,1}\quad\text{and}\quad
F_{n,\mathfrak{l}(n-1)+1,0}=F_{n+1,0,1}.$

######  Proposition 2.5.

Let $(\mathcal{F}_{n})_{n\in\mathbb{N}}$ be the sequence defined inductively
by $\mathcal{F}_{0}:=F_{1,0,N_{0}}$ and for all $n\geq 0$ by
$\mathcal{F}_{n+1}=F_{m,i,j+1}$ where $m,i$ and $j$ are such that
$\mathcal{F}_{n}=F_{m,i,j}$. Then $(\mathcal{F}_{n})_{n\in\mathbb{N}}$ is a
Følner sequence of $\Delta$.

###### Proof.

Let $n\in\mathbb{N}$, let $i\in[0,\mathfrak{l}(n-1)]$ and $j\in[1,N_{i}]$ and
take $(\bm{f},t)$ in $F_{n,i,j}$.

If $s=(0,1)$ then $(\bm{f},t)s$ belongs to $F_{n,i,j}$ if and only if $t\neq
n-1$. Similarly if $s=(0,-1)$ then $(\bm{f},t)s\in F_{n,i,j}$ if and only if
$t\neq 0$.

Now let $s=\big{(}(a_{m}\delta_{0})_{m},0\big{)}$ for some $a\in A$. The
action of $s$ on $(\bm{f},t)$ does not change the value of the cursor, thus
there exists some $\bm{g}$ such that $(\bm{f},t)s=(\bm{g},t)$. For all $x\neq
t$ it verifies $g_{0}(x)=f_{0}(x)$, moreover $g_{0}(t)=f_{0}(t)a_{0}$. Thus
$\mathrm{supp}(g_{0})=\mathrm{supp}(f_{0})$. Now consider $m>0$. Then for all
$x\neq t$ we have $g_{m}(x)=f_{m}(x)$ and in particular
$g^{\prime}_{m}(x)=f^{\prime}_{m}(x)$. Furthermore using the decomposition
given by Lemma A.6 and the above value of $g_{0}(t)$ we get

$\displaystyle g_{m}(t)=f_{m}(t)a_{m}$
$\displaystyle=f^{\prime}_{m}(t)\theta^{A}_{m}\left(f_{0}(t)\right)\theta^{B}_{m}(f_{0}(t-k_{m}))a_{m},$
$\displaystyle=f^{\prime}_{m}(t)\theta^{A}_{m}\left(f_{0}(t)a_{m}\right)\theta^{B}_{m}(f_{0}(t-k_{m})),$
$\displaystyle=f^{\prime}_{m}(t)\theta^{A}_{m}\left(g_{0}(t)\right)\theta^{B}_{m}(g_{0}(t-k_{m})).$

By unicity of the decomposition we thus obtain
$g^{\prime}_{m}(t)=f^{\prime}_{m}(t)$. Hence
$\mathrm{supp}(g^{\prime}_{m})=\mathrm{supp}(f^{\prime}_{m})$ and
$g^{\prime}_{m}(n-1)=f^{\prime}_{m}(n-1)$ which belongs to $\Lambda^{i}_{j}$.
Thus $(\bm{g},t)$ belongs to $F_{n,i,j}$. The case where $s\in\mathcal{S}_{2}$
is very similar.

Thus $\partial F_{n,i,j}=\\{(\bm{f},t)\in F_{n,i,j}\ |\ t\in\\{0,n-1\\}\\}$
and in particular $|\partial F_{n,i,j}|/|F_{n,i,j}|\sim 2/n$. Hence
$(\mathcal{F}_{n})_{n}$ is a Følner sequence. ∎

######  Remark 2.6.

Note that $(F_{n})_{n\in\mathbb{N}}$ defined in eq. 2.4 is a subsequence of
$(\mathcal{F}_{n})_{n\in\mathbb{N}}$. Indeed using [Esc22, Lemma 2.12] we can
prove that $F_{n}:=F_{n,\mathfrak{l}(n-1),N_{\mathfrak{l}(n-1)}}$.

###  2.3 Growth and diameter

Let us start by computing the number of elements in $F_{n,i,j}$ and give an
estimate of the growth of this Følner sequence.

######  Lemma 2.7.

Let $n\in\mathbb{N}$ and $i\in[0,\mathfrak{l}(n-1)]$ and $j\in[0,N_{i}]$ and
consider $F_{n,i,j}$ as defined in eq. 2.6. Then

$\left|{F_{n,i,j}}\right|=nq^{n}\prod^{i-1}_{m=1}\left|{\Gamma^{\prime}}_{m}\right|^{n-k_{m}}\left|\Lambda^{i}_{j}\right|\prod^{\mathfrak{l}(n-1)}_{m=i}\left|{\Gamma^{\prime}}_{m}\right|^{n-k_{m}-1}$

In particular $2|F_{n,i,j}|\leq|F_{n,i,j+1}|\leq 2q|F_{n,i,j}|$.

The last assertion precises the control we have on the growth of
$|F_{n,i,j}|$. It will be precious when proving Section 1.3.

###### Proof.

Let $F_{n,i,j}$ as defined in eq. 2.6 and take $(\bm{f},t)\in F_{n,i,j}$, then
there are exactly $n$ possible values of $t$. Moreover $\bm{f}$ is uniquely
determined by $f_{0}$ and
$f^{\prime}_{1},\ldots,f^{\prime}_{\mathfrak{l}(n-1)}$ (see Lemma A.6). But
$f_{0}$ is supported on $[0,n-1]$ which is set of cardinal $n$ so there are
exactly $\big{(}{|A||B|}\big{)}^{n}$ possible values for $f_{0}$. Moreover if
$0<m<i$ then $f^{\prime}_{m}$ is supported on $[k_{n},n-1]$ which has
$n-k_{m}$ elements, and on this interval it can take any values in
${\Gamma^{\prime}}_{m}$ so there are exactly
${\left|{\Gamma^{\prime}}_{m}\right|}^{n-k_{m}}$ possibilities for
$f^{\prime}_{m}$. Similarly for $m>i$ the map $f^{\prime}_{m}$ is supported on
$[k_{m},n-2]$ which contains $n-1-k_{m}$ elements, thus we have
${\left|{\Gamma^{\prime}}_{m}\right|}^{n-k_{m}-1}$ choices for such a map.
Finally when $m=i$ the map $f^{\prime}_{i}$ is supported on $[k_{i},n-k_{i}]$
and

  * •

for any $x\in[k_{i},n-k_{i}-1]$ all values of $|\Gamma^{\prime}_{i}|$ can be
taken by $f^{\prime}_{i}$;

  * •

$f^{\prime}_{i}(n-1)$ can take any value in $\Lambda^{i}_{j}$.

We thus have $\left|\Lambda^{i}_{j}\right||\Gamma^{\prime}_{i}|^{n-k_{i}-1}$
possibilities for $f^{\prime}_{i}$. Hence the first assertion.

Assume first that $i<\mathfrak{l}(n-1)$ and $j=N_{i}$, then
$F_{n,i,N_{i}+1}=F_{n,i+1,1}$ and hence using also eq. 2.5

$|F_{n,i+1,1}|/|F_{n,i,N_{i}}|=\left|\Lambda^{i+1}_{1}\right|\in[2,2q].$

Similarly if $j<N_{i}$ then
$|F_{n,i,j+1}|/|F_{n,i,j}|=\left|\Lambda^{i}_{j+1}\right|/\left|\Lambda^{i}_{j}\right|$
which belongs to $[2,2q]$. Finally if $i=\mathfrak{l}(n-1)$ and $j=N_{i}$ then
$F_{n,i,j+1}=F_{n+1,0,1}$. In that case

$|F_{n,i,j+1}|/|F_{n,i,j}|=|F_{n+1,0,1}|/|F_{n,i,N_{i}}|=q(n+1)/n\in[q,2q].$

Hence the wanted inequalities. ∎

We will use this last lemma to estimate the value of $\ln|F_{n,i,j}|$.

######  Proposition 2.8.

There exists $C_{2}>0$ depending only on $\Delta$ such that
$\ln|F_{n,i,j}|\leq C_{2}nl_{\mathfrak{l}(n-1)}$ for all $n\in\mathbb{N}$.

######  Remark 2.9.

Let us mention that a similar estimation was done in [Esc22] for the value of
$\ln|F_{\kappa^{n}}|$. We refer to eqs. 2.4 and 2.6 for the definition of
$(F_{n})_{n\in\mathbb{N}}$ and its link with the sequence $F_{n,i,j}$. Most
importantly, in the case of this precise subsequence, we were also able to
give a _lower_ bound. Indeed if we define
$\mathfrak{L}(n):=\mathfrak{l}(\kappa^{n}-1)$ then by [Esc22, Prop. 4.3] there
exists two constants $C_{3},C_{4}>0$ such that for all $n\in\mathbb{N}$,

$C_{3}\kappa^{n-1}l_{\mathfrak{L}(n)}\leq\ln\left|F_{\kappa^{n}}\right|\leq
C_{4}\kappa^{n}l_{\mathfrak{L}(n)}.$

We refer to the proof of Lemma 4.5 for a use of this precise lower bound.

Similarly the lemma below generalises [Esc22, Lemma 4.4].

######  Lemma 2.10.

There exists $C_{1}>0$ depending only on $\Delta$ such that for all
$n\in\mathbb{N}^{*}$,

$\ln\left(\prod^{\mathfrak{l}(n-1)}_{m=1}{\left|\Gamma^{\prime}_{m}\right|}^{n-k_{m}}\right)\leq
C_{1}nl_{\mathfrak{l}(n-1)}.$

###### Proof.

By eq. 4.10a there exists $c_{1}$, $c_{2}>0$ such that
$\ln\left|{\Gamma_{m}}\right|\leq c_{1}l_{m}+c_{2}$, for all $m$. Then,

$\displaystyle\ln\left(\prod^{\mathfrak{l}(n-1)}_{m=1}{\left|\Gamma^{\prime}_{m}\right|}^{n-k_{m}}\right)$
$\displaystyle\leq\sum^{\mathfrak{l}(n-1)}_{m=1}\left({n-k_{m}}\right)\ln|{\Gamma^{\prime}}_{m}|,$
$\displaystyle\leq\sum^{\mathfrak{l}(n-1)}_{m=1}\left({n-k_{m}}\right)\left(c_{1}l_{m}+c_{2}\right).$

But we can bound $n-k_{m}$ from above by $n$ and since $(l_{m})_{m}$ is a
subsequence of a geometric sequence the sum
$\sum^{\mathfrak{l}(n-1)}_{m=1}\left(c_{1}l_{m}+c_{2}\right)$ is bounded from
above by its last term up to a multiplicative constant. That is to say: there
exists $C_{1}>0$ such that

$\ln\left(\prod^{\mathfrak{l}(n-1)}_{m=1}{\left|\Gamma^{\prime}_{m}\right|}^{n-k_{m}}\right)\leq
C_{1}nl_{\mathfrak{l}(n-1)}.$

∎

###### Proof of Proposition 2.8.

Since $\Lambda^{i}_{j}\subseteq\Gamma^{\prime}_{i}$, using Lemma 2.7 and Lemma
2.10 we get

$\displaystyle\ln|F_{n,i,j}|$
$\displaystyle\leq\ln\left(nq^{n}\prod^{\mathfrak{l}(n-1)}_{m=1}\left|{\Gamma^{\prime}}_{m}\right|^{n-k_{m}}\right)\leq\ln\left(n\right)+n\ln(q)+C_{1}nl_{\mathfrak{l}(n-1)}.$

Thus, there exists $C_{2}>0$ such that $\ln|F_{n,i,j}|\leq
C_{2}nl_{\mathfrak{l}(n-1)}$. ∎

##  3 Coupling with $\mathbb{Z}$

This section is devoted to the proof of Section 1.3. In the following $\Delta$
will be a diagonal product as defined in appendix A and verifying (H) Section
A.1.2. In particular its isoperimetric profile is of the form
$I_{\Delta}\simeq\rho\circ\log$ for some $\rho\in\mathcal{C}$. To prove
Section 1.3 we actually show that the diagonal product obtained from the
isoperimetric profile $\rho\circ\log$ is the wanted group $G$. The
integrability of the coupling is proved using the criterion of Theorem 2.3. We
thus start by defining Sofic approximations $\mathcal{G}_{n}\subseteq\Delta$
and $\mathcal{H}_{n}\subseteq\mathbb{Z}$ and then define a bijection
$\iota_{n}$ between them. For this we use the notion of _decomposition in
variable base_ of an integer. All necessary material are recalled in Section
B.1.

Now let us describe the idea of the bijection. Given $(\bm{f},t)$ in
$\mathcal{G}_{n}$ we map $\bm{f}$ to an integer decomposed in some variable
base $(b_{i})_{i}$ and decompose $t$ is some constant base $\kappa$. The image
of $(\bm{f},t)$ by $\iota_{n}$ will be the integer produced by intertwining
the digits of these two decomposition. We illustrate this in Figure 4 and
refer to Section 3.1 for more details on this interlacing.

In a second time we study the different components appearing eq. 2.1 giving
the condition for integrability. We thus investigate the behaviour of the
value of $\iota_{n}(\bm{f},t)$ under the action of some generator $s$ of
$\Delta$ on $(\bm{f},t)$. Then for some distance $r>0$, we compute the
proportion of elements $(\bm{f},t)$ in $\mathcal{G}_{n}$ that the action of
$s$ sents $\iota_{n}(\bm{f},t)$ at distance $r$ from
$\iota_{n}\big{(}(\bm{f},t)s\big{)}$. We conclude on the proof of Section 1.3
by showing that eq. 2.1 is verified.

###  3.1 Bijection between Sofic approximations

Recall that $(F_{n})_{n\in\mathbb{N}}$ defined in eq. 2.4 is a Følner sequence
(and hence a Sofic approximation) of $\Delta$. Therefore, the following
subsequence of $(F_{n})_{n\in\mathbb{N}}$ provides a Sofic approximation of
$\Delta$:

$\mathcal{G}_{n}:=F_{\kappa^{n}}=\left\\{\left(\bm{f},t\right)\
|\quad\mathrm{range}\left(\bm{f},t\right)\subseteq\\{0,\ldots,\kappa^{n}-1\\}\right\\}.$

Let $\mathcal{H}_{n}:=[0,|\mathcal{G}_{n}|-1]\subseteq\mathbb{Z}$ and denote
by $\mathfrak{L}(n)$ the integer verifying
$k_{\mathfrak{L}(n)}\leq{\kappa}^{n}-1<k_{\mathfrak{L}(n)+1}$.

Idea of the bijection Consider $(\bm{f},t)\in\mathcal{G}_{n}$. To construct
our bijection we are going to “encode” the information contained in $\bm{f}$
into an integer. We decompose it in some variable base $(b_{i})_{i}$ to be
precised later and decompose $t$ in base $\kappa$. We then intertwine the
digits to obtain one integer from the two preceding ones (see Figure 4).

$\mathcal{G}_{n}$$\bm{f}$$t$$\sum^{n-1}_{i=0}{\color[rgb]{0.8334,0.49,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.8334,0.49,0.15}t_{i}}\kappa^{i}$$\sum_{i}{\color[rgb]{0,.408,.545}\definecolor[named]{pgfstrokecolor}{rgb}{0,.408,.545}x_{i}}b_{i-1}\cdots
b_{0}$$\mathcal{H}_{n}\subseteq\mathbb{Z}$$z={\color[rgb]{0.8334,0.49,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.8334,0.49,0.15}t_{0}}+\kappa$$x_{0}$$+\kappa
b_{0}{\color[rgb]{0.8334,0.49,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.8334,0.49,0.15}t_{1}}+\cdots$
Figure 4: Definition of the injection

This is the general idea, now let us describe the numbering process of
$\bm{f}$.

Numbering process and blocs decompositon For the condition of eq. 2.1 to be
verified, we need the bijection to correspond to the geometry of the groups.
That is to say: for some $s\in\mathcal{S}_{\Delta}$, we need
$\iota_{n}(\bm{f},t)$ to be sent at a reasonable distance from
$\iota_{n}\big{(}(\bm{f},t)s\big{)}$ in $\mathbb{Z}$.

Recall (see Claim A.10) that $\bm{f}$ is uniquely determined by $f_{0}$ and
$(f^{\prime}_{m})_{m}$. As we will see, the main problem is to number $f_{0}$.
So first assume for simplicity that $\Delta$ is a lamplighter group and thus
$\bm{f}=f_{0}:\mathbb{Z}\rightarrow A\times B$. A naive way to encode the
information contained in $f_{0}$ is to map it to the integer
$\sum^{\kappa^{n}-1}_{i=0}f_{0}(i)q^{i}$. But then the action of
$s\in\mathcal{S}_{\mathbb{Z}}\backslash\\{(0,1)\\}$ will change the value of
the lamp $f_{0}(t)$ and thus the distance between
$\iota_{n}\big{(}(\bm{f},t)s\big{)}$ and $\iota_{n}(\bm{f},t)$ might be quite
large. Therefore, when encoding $f_{0}$ in an integer we need to start
numbering it from the cursor $t$ and continue moving away from $t$ (instead of
starting from $0$). This way the action of a generator modifying the lamps
will only change the corresponding integer from a small value (see Lemma 3.6).
Now, the action of $s=(0,1)$ changes the value of the cursor; it thus modifies
the starting point of this numbering and hence disrupts (all) the digits
encoding $f_{0}$. To counter this we define in Section 3.1.1 a numbering that
depends on _the decomposition in base $\kappa$ of $t$_. More precisely, if
$t=\sum^{n-1}_{i=0}t_{i}\kappa^{i}$ denotes the decomposition in base $\kappa$
of $t$, we define a sequence of nested intervals $(\mathcal{B}_{j}(t))_{j}$
such that the lower and upper bounds of $\mathcal{B}_{j}(t)$ depends only on
$(t_{i})_{i\geq j}$. We then encode the information of $f_{0}$ reading first
the values taken by $f_{0}$ on $\mathcal{B}_{0}(t)$, then on
$\mathcal{B}_{1}(t)$, etc. (see Figure 5). This way, if $t$ and $t+1$ differ
only in their first $i_{0}$ digits then $\mathcal{B}_{j}(t)$ and
$\mathcal{B}_{j}(t+1)$ are the same intervals, for all $j>i_{0}$. In other
words: the reading window are the same and the encoded values are consequently
identical.

To obtain the encoding of an element $(\bm{f},t)$ in a general diagonal
product, we start by number $f_{0}$ using the foregoing blocs decomposition
and then encode $(f^{\prime}_{m})_{m}$ in an integer. We refer to Figure 6 for
an illustration.

We start by formalising our blocs decomposition in Section 3.1.1 below. We
then define our numbering of $(\bm{f},t)$ and the injection $\iota_{n}$ in
Section 3.1.2. We conclude by the proof of the bijectivity of $\iota_{n}$ in
Section 3.1.3.

####  3.1.1 Bloc decomposition

Fix $(\bm{f},t)\in\mathcal{G}_{n}$ and decompose $t$ in base $\kappa$ as
$t=\sum^{n-1}_{i=0}t_{i}\kappa^{i}$. In this paragraph we define the blocs or
“reading windows” that will determine the encoding of $f_{0}$. As described
previously, the idea is to define a sequence of nested intervals
$\mathcal{B}_{i}(t)$ such that if the decomposition in base $\kappa$ of $t$
and $t+1$ differ only in their first $i_{0}$ terms, then the corresponding
intervals $\mathcal{B}_{i}(t)$ and $\mathcal{B}_{i}(t+1)$ are the same for all
$i>i_{0}$.

######  Lemma 3.1.

Let $t\in[0,\kappa^{n}-1]$ and $i\in\\{0,\ldots,n\\}$ and define

$\mathcal{B}_{i}(t):=\left[\sum^{n-1}_{j=i}t_{j}\kappa^{j},\sum^{n-1}_{j=i}t_{j}\kappa^{j}+\kappa^{i}-1\right].$

The sequence $(\mathcal{B}_{i}(t))_{0\leq i\leq n}$ thus defined verifies
$\mathcal{B}_{i}(t)\subset\mathcal{B}_{i+1}(t)$ for all $i\leq n-1$. In
particular

$\\{t\\}=\mathcal{B}_{0}(t)\subset\mathcal{B}_{i}(t)\subseteq\mathcal{B}_{n}(t)=[0,\kappa^{n}-1],$

and thus $t$ belongs to $\mathcal{B}_{i}(t)$ for all $i\leq n$.

######  Remark 3.2.

Remark that by definition
$\mathrm{diam}\left({\mathcal{B}_{i}(t)}\right)=\kappa^{i}-1\sim\kappa^{i}$
for all $i\leq n$.

We represent in Figure 5 such a nesting of intervals for $\kappa=3$, $n=3$ and
$t=16$ whose decomposition is thus given by $t=1+2\cdot 3+1\cdot 3^{2}$.

Figure 5: Example of $\mathcal{B}_{i}(t)$ for $\kappa=3$, $n=3$ and $t=16$.

###### Proof of Lemma 3.1.

Let $t\in[0,\kappa^{n}-1]$ and $i\in\\{0,\ldots,n-2\\}$ and let us prove that
$\mathcal{B}_{i}(t)\subset\mathcal{B}_{i+1}(t)$. Remark that
$\sum^{n-1}_{j=i}t_{j}\kappa^{j}$ is greater than
$\sum^{n-1}_{j=i+1}t_{j}\kappa^{j}$. Moreover, since

$t_{i}\kappa^{i}\leq(\kappa-1)\kappa^{i}=\kappa^{i+1}-\kappa^{i},$

we thus have

$\displaystyle\sum^{n-1}_{j=i}t_{j}\kappa^{j}+\kappa^{i}-1$
$\displaystyle\leq(\kappa^{i+1}-\kappa^{i})+\sum^{n-1}_{j=i+1}t_{j}\kappa^{j}+\kappa^{i}-1=\sum^{n-1}_{j=i+1}t_{j}\kappa^{j}+\kappa^{i+1}-1.$

Hence the inclusion. ∎

######  Remark 3.3.

By Remark 3.2 and the above lemma, we have
$|\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)|=\kappa^{i}-\kappa^{i-1}$.
In particular the number of lamp configurations from $\mathbb{Z}$ to $A\times
B$ supported on $\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)$ is
$q^{\kappa^{i}-\kappa^{i-1}}$.

####  3.1.2 Global numbering

By the preceding remark we can define applications

$\displaystyle\nu_{0,t}\,$
$\displaystyle:\,\left\\{\zeta:\,\mathcal{B}_{0}(t)\rightarrow A\times
B\right\\}\rightarrow\left[0,q-1\right],$ $\displaystyle\forall i\geq
1\quad\nu_{i,t}\,$
$\displaystyle:\,\left\\{\zeta:\,\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)\rightarrow
A\times B\right\\}\rightarrow\left[0,q^{\kappa^{i}-\kappa^{i-1}}-1\right].$

such that these maps are bijections. From now on we assume fixed such
bijections. Remark that they actually depend on the value of $t$. When we do
need to keep track of the value of $t$ we will denote $\nu_{i}$ instead of
$\nu_{t,n}$.

######  Claim 3.4.

There exists a bijection

$\mu_{n}:\,\left\\{\bm{f}^{\prime}|\,\mathrm{supp}(f^{\prime}_{m})\subseteq[k_{m},\kappa^{n}-1],\
\forall
m\in[0,\mathfrak{L}(n)]\right\\}\rightarrow\left[0,\,\frac{|\mathcal{G}_{n}|}{\kappa^{n}q^{\kappa^{n}}}-1\right].$

###### Proof.

Recall that $\mathcal{G}_{n}=F_{\kappa^{n}}$. Consider
$(\bm{f},t)\in\mathcal{G}_{n}$. The number of such possible $\bm{f}$ is equal
to the number of elements of $\mathcal{G}_{n}$ divided by the number of
possible cursor $t$, that is to say $|\mathcal{G}_{n}|/\kappa^{n}$. Recall
moreover (see Section A.1) that in a diagonal product $\bm{f}$ is uniquely
determined by $f_{0}$ and $\bm{f}^{\prime}$. Since
$\mathrm{supp}(f_{0})\subseteq[0,\kappa^{n}-1]$ and $f_{0}$ can take all
possible values on that interval, we have $q^{\kappa^{n}}$ possible values for
$f_{0}$. Similarly, for all $m\in[0,\mathfrak{L}(n)]$ the support of
$f^{\prime}_{m}$ is in $[k_{m},\kappa^{n}-1]$ and $f^{\prime}_{m}$ can take
all possible values on that interval. Hence

$\displaystyle\left|\left\\{\bm{f}^{\prime}|\,\mathrm{supp}(f^{\prime}_{m})\subseteq[k_{m},\kappa^{n}-1],\
\forall m\in[0,\mathfrak{L}(n)]\right\\}\right|$
$\displaystyle=\left|\\{\bm{f}\ |\ \exists t\ :\
(\bm{f},t)\in\mathcal{G}_{n}\\}\right|/q^{\kappa^{n}},$
$\displaystyle=|\mathcal{G}_{n}|/(\kappa^{n}q^{\kappa^{n}}).$

∎

The information encoded by each of the previous maps is represented in Figure
6.

Figure 6: Numbering in $\Delta$

Using the maps defined above we are now able to encode in an integer the
information contained in $\bm{f}$. Indeed we can consider the map sending
$\bm{f}$ to the number

$\nu_{0}\left(f_{0|\mathcal{B}_{0}(t)}\right)+\sum^{n}_{i=1}\nu_{i,t}\left(f_{0|\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)}\right)q^{\kappa^{i-1}}+\kappa^{n}q^{\kappa^{n}}\mu_{n}(\bm{f}^{\prime}).$

The above decomposition can be seen as the writing of the corresponding
integer in the variable base
$(q,q^{\kappa-1},\ldots,q^{\kappa^{n}-\kappa^{n-1}},\max\mu_{n}+1)$. We refer
to Section B.1 for more details on variable base. The digits of the
decomposition are given by the values of the $\nu_{i,t}$’s and $\mu_{n}$.
Intertwining these digits with the ones of the decomposition of $t$ in base
$\kappa$ we obtain:

$\begin{split}\iota_{n}(\bm{f},t):=\nu_{0}\left(f_{0|\mathcal{B}_{0}(t)}\right)+\sum^{n-1}_{i=0}t_{i}\kappa^{i}q^{\kappa^{i}}&+\sum^{n}_{i=1}\nu_{i,t}\left(f_{0|\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)}\right)\kappa^{i}q^{\kappa^{i-1}}\\\
+\kappa^{n}q^{\kappa^{n}}\mu_{n}(\bm{f}^{\prime}).\end{split}$ (3.1)

It corresponds to the decomposition of $\iota_{n}(\bm{f},t)$ in the variable
base $(\beta_{i})_{i}$ defined below.

$\displaystyle{\beta}_{0}=q$ $\displaystyle\forall i\in[1,n]\quad$
$\displaystyle{\beta}_{2i}=q^{\kappa^{i}-\kappa^{i-1}}$ $\displaystyle\forall
i\in[1,n]\quad$ $\displaystyle{\beta}_{2i-1}=\kappa$
$\displaystyle{\beta}_{2n+1}=\max(\mu_{n})+1.$

Please note that the variable base depends on $n$ but in order to reduce
formalism we chose to abuse notations and write ${\beta}_{i}$ instead of
${\beta}_{n,i}$.

####  3.1.3 Bijection

In order to get an orbit equivalence using Theorem 2.3 we need to prove that
$\iota_{n}$ is bijective.

######  Proposition 3.5.

For all $n\in\mathbb{N}$, the map $\iota_{n}$ defined in eq. 3.1 is a
bijection from $\mathcal{G}_{n}=F_{\kappa^{n}}$ to
$\mathcal{H}_{n}=\left[0,|\mathcal{G}_{n}|-1\right]$.

###### Proof.

Let $n\in\mathbb{N}$. By Lemma B.1 on the decomposition in variable base
applied to $(\beta_{i})_{i}$ the map $\iota_{n}$ defined in eq. 3.1 verifies
$\min\iota_{n}=0$ and
$\max\iota_{n}=\kappa^{n}q^{\kappa^{n}}(\max\mu_{n}+1)-1$. Since
$\max\mu_{n}+1=|\mathcal{G}_{n}|/(\kappa^{n}q^{\kappa^{n}})$ we obtain that
the image of $\iota_{n}$ is included in
$\mathcal{H}_{n}=[0,|\mathcal{G}_{n}|-1]$.

The injectivity of $\iota_{n}$ comes from the unicity of the decomposition in
variable base (see Lemma B.1). To prove the surjectivity, consider
$z\in\mathcal{H}_{n}$ then we can decompose it in base $(\beta_{i})_{i}$ as
$z=[z_{0},\ldots,z_{2n+1}]_{\beta}$. In particular $z_{2i-1}\in[0,q-1]$ for
all $i\in[1,n]$. Define $t=\sum^{n}_{i=1}z_{2i-1}\kappa^{i}$ then $t$ belongs
to $[0,\kappa^{n}]$. Moreover since $\nu_{i,t}$ and $\mu_{n}$ are bijections
the others coefficients determine $\bm{f}$ such that
$(\bm{f},t)\in\mathcal{G}_{n}$ verifies $\iota_{n}(\bm{f},t)=z$. ∎

###  3.2 Quantification

Now that we have defined a bijection between our Sofic approximations we need
to show that eq. 2.1 is verified. So for $(\bm{f},t)\in\mathcal{G}^{(1)}_{n}$
and $s\in\mathcal{S}_{\Delta}$ we first bound the distance between
$\iota_{n}(\bm{f},t)$ and $\iota_{n}\big{(}(\bm{f},t)s\big{)}$. Then for a
given $r>0$ we provide an estimate of the proportion of elements in
$\mathcal{G}_{n}$ such that $\iota_{n}(\bm{f},t)$ and
$\iota_{n}\big{(}(\bm{f},t)s\big{)}$ are at distance $r$ in $\mathcal{H}_{n}$.
Finally we show that the aforementioned equation is verified.

####  3.2.1 Distance

Consider $(\bm{f},t)\in\mathcal{G}^{(1)}_{n}$. We compare in this section the
distance in $\mathbb{Z}$ between $\iota_{n}(\bm{f},t)$ and
$\iota_{n}\big{(}(\bm{f},t)s\big{)}$ for some $s\in\mathcal{S}_{\Delta}$. We
will distinguish two cases depending on $s=(0,1)$ or not.

If $(\bm{f},t)$ belongs to $\Delta$ we denote by $\bm{f}^{\prime}$ the
sequence $(f^{\prime}_{m})_{m=0,\ldots,\mathfrak{L}(n)}$.

##### Action on the lamp

Let us start by looking at a generator that modifies the lamp configurations.
So consider $s\in\mathcal{S}_{1}\cup\mathcal{S}_{2}$ and let
$(\tilde{\bm{f}},t):=(\bm{f},t)s$.

######  Lemma 3.6.

For all $s\in\mathcal{S}_{1}\cup\mathcal{S}_{2}$ and
$(\bm{f},t)\in\mathcal{G}^{(1)}_{n}$ we have
$|\iota_{n}(\bm{f},t)-\iota_{n}\big{(}(\bm{f},t)s\big{)}|\leq q$.

###### Proof.

First recall that we showed in the proof of Proposition 2.5 that
$\bm{f}^{\prime}=\tilde{\bm{f}}^{\prime}$. Thus
$\mu_{n}(\bm{f}^{\prime})=\mu_{n}\big{(}\tilde{\bm{f}}^{\prime}\big{)}$.
Moreover $\tilde{f}_{0}$ differs from $f_{0}$ only at $t$. Since the cursors
of $(\bm{f},t)s$ and $(\bm{f},t)$ are the same we obtain

$(\forall
i>0)\quad\nu_{i,t}\left(f_{0|\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)}\right)=\nu_{i,t}\left({\tilde{f}}_{0|\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)}\right).$

Hence using eq. 3.1 we get

$|\iota_{n}(\bm{f},t)-\iota_{n}\big{(}(\bm{f},t)s\big{)}|=\left|\nu_{0,t}\left(f_{0}(t)\right)-\nu_{0,t}\left(\tilde{f}_{0}(t)\right)\right|\leq
q.$

∎

##### Action on the cursor

Now consider $s=(0,1)$. Let $t+1:=\sum^{n-1}_{i=0}\tilde{t}_{i}\kappa^{i}$ be
the decomposition in base $\kappa$ of $t+1$. Note that since $(\bm{f},t)$
belongs to $\mathcal{G}^{(1)}_{n}$, it verifies $t<n-1$ and thus there exists
$i\in\\{0,\ldots,n-1\\}$ such that $t_{i}<\kappa-1$. Therefore, we can define

$i_{0}(t):=\min\\{i\leq n\ |\ t_{i}<\kappa-1\\}.$ (3.2)

This index corresponds to the one of the coefficients $t_{i}$ that will absorb
the carry when we add one to $t$.

######  Lemma 3.7.

For all $(\bm{f},t)\in\mathcal{G}^{(1)}_{n}$ we have
$|\iota_{n}(\bm{f},t)-\iota_{n}(\bm{f},t+1)|<\kappa^{i_{0}(t)+1}q^{\kappa^{i_{0}(t)+1}}$.

Let us start by showing the following useful claim.

######  Claim 3.8.

Let $t\in[0,n-2]$, then $\mathcal{B}_{i}(t)=\mathcal{B}_{i}(t+1)$ for all
$i>i_{0}(t)$.

###### Proof of the claim.

By definition of $i_{0}(t)$ the decomposition of $t+1$ in base $\kappa$ is
given by $t+1:=(t_{i_{0}(t)}+1)+\sum^{n-1}_{i=i_{0}(t)+1}{t}_{i}\kappa^{i}$.
In particular $\tilde{t}_{i}=t_{i}$ for all $i>i_{0}(t)$. But
$\mathcal{B}_{i}(t)$ depends only on the value of $(t_{j})_{j\geq i}$ (see
Lemma 3.1). Hence the claim. ∎

###### Proof of Lemma 3.7.

By the above claim $\mathcal{B}_{i}(t)=\mathcal{B}_{i}(t+1)$ for all
$i>i_{0}(t)$. Hence

$(\forall
i>i_{0}(t)+1)\quad\nu_{i,t}\left(f_{0|\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)}\right)=\nu_{i,t+1}\left({\tilde{f}}_{0|\mathcal{B}_{i}(t+1)\backslash\mathcal{B}_{i-1}(t+1)}\right).$

Thus by eq. 3.1 we get

$\displaystyle\left|\iota_{n}(\bm{f},t)-\iota_{n}\big{(}(\bm{f},t)s\big{)}\right|$
$\displaystyle\leq$
$\displaystyle\left|\nu_{0,t}\left(f_{0}(t)\right)-\nu_{0,t+1}\left(\tilde{f}_{0}(t+1)\right)\right|+\sum^{i_{0}(t)}_{i=0}|t_{i}-\tilde{t}_{i}|\kappa^{i}q^{\kappa^{i}}$
$\displaystyle+\sum^{i_{0}(t)+1}_{i=1}\left|\nu_{i,t}\left(f_{0|\mathcal{B}_{i}(t)\backslash\mathcal{B}_{i-1}(t)}\right)-\nu_{i,t+1}\left(f_{0|\mathcal{B}_{i}(t+1)\backslash\mathcal{B}_{i-1}(t+1)}\right)\right|\kappa^{i}q^{\kappa^{i-1}}$

Thus by Lemma B.1 we can bound
$\left|\iota_{n}(\bm{f},t)-\iota_{n}\big{(}(\bm{f},t)s\big{)}\right|$ by above
by $\kappa^{i_{0}(t)+1}q^{\kappa^{i_{0}(t)+1}}-1$. Hence the lemma. ∎

####  3.2.2 Enumeration

Consider $r>0$. We now give an estimate of the number of elements
$(\bm{f},t)\in\mathcal{G}^{(1)}_{n}$ such that $\iota_{n}(\bm{f},t)$ and
$\iota_{n}\big{(}(\bm{f},t)s\big{)}$ are at distance $r$ in $\mathbb{Z}$. With
regard to the previous section, it corresponds to determining the number of
elements $(\bm{f},t)\in\mathcal{G}_{n}$ such that $i_{0}(t)=m$.

######  Lemma 3.9.

Let $n\in\mathbb{N}$ and $(\bm{f},t)\in\mathcal{G}^{(1)}_{n}$. For all
$m\in[0,n-1]$

$\left|\left\\{(\bm{f},t)\in\mathcal{G}_{n}\ |\
\kappa^{m}q^{\kappa^{m}}\leq\left|\iota_{n}(\bm{f},t)-\iota_{n}\big{(}(\bm{f},t+1)\big{)}\right|<\kappa^{m+1}q^{\kappa^{m+1}}\right\\}\right|\sim|\mathcal{G}_{n}|\kappa^{-m}.$

###### Proof.

Let $m\in[0,n-1]$. By Lemma 3.7

$\displaystyle\left|\left\\{(\bm{f},t)\in\mathcal{G}_{n}\ |\
\kappa^{m}q^{\kappa^{m}}\leq\left|\iota_{n}(\bm{f},t)-\iota_{n}\big{(}(\bm{f},t+1)\big{)}\right|<\kappa^{m+1}q^{\kappa^{m+1}}\right\\}\right|$
$\displaystyle=$ $\displaystyle\left|\left\\{(\bm{f},t)\in\mathcal{G}_{n}\ |\
i_{0}(t)=m\right\\}\right|.$

But requiring $i_{0}(t)=m$ forces $t_{0},\ldots,t_{m-1}$ to be equal to
$\kappa-1$ and $t_{m}$ can only take $\kappa-1$ possible values. Thus there
are $(\kappa-1)\kappa^{n-m-1}$ possible values of $t$ verifying $i_{0}(t)=m$.
Finally there is no condition on $\bm{f}$ so we have
$|\mathcal{G}_{n}|/\kappa^{n}$ possible values for $\bm{f}$, therefore

$\left|\big{\\{}(\bm{f},t)\in\mathcal{G}_{n}\ |\
i_{0}(t)=m\big{\\}}\right|=|\mathcal{G}_{n}|(\kappa-1)\kappa^{-(m-1)}\sim|\mathcal{G}_{n}|\kappa^{-m}.$

∎

####  3.2.3 Integrability

We can now prove that the conditions of integrability given by Theorem 2.3 are
verified.

###### Proof of Section 1.3.

Let $\rho\in\mathcal{C}$ and consider $\Delta$ the diagonal product with
isoperimetric profile $I_{\Delta}:=\rho\circ\log$ as defined in Section A.3.2.
Assume moreover that $\left(\rho(\kappa^{m})\kappa^{-m}\right)$ is summable.

Consider $\mathcal{G}_{n}$ and $\mathcal{H}_{n}$ as defined in Section 3.1
above and $\iota_{n}$ the bijection defined in eq. 3.1. Before looking at the
integrability, note since $\iota_{n}$ is bijective Theorem 2.3 gives an
_orbit_ equivalence coupling. We need to show that eq. 2.1 is verified for
$\varphi=\rho\circ\log$.

Fix $R>0$ and $n\in\mathbb{N}$. For all $s\in\mathcal{S}_{\Delta}$, we need to
bound the following sum

$\displaystyle\Sigma_{R,n}:=\sum_{r=0}^{R}\rho\circ\log\left(r\right)\frac{\left|{\left\\{(\bm{f},t)\in\mathcal{G}_{n}^{(1)}\mid
d_{\mathcal{H}_{n}}\left(\iota_{n}(\bm{f},t),\iota_{n}((\bm{f},t)\cdot
s)\right)=r\right\\}}\right|}{\left|{\mathcal{G}_{n}}\right|}$

First consider $s\in\mathcal{S}_{\mathbb{Z}}\backslash\\{(0,1)\\}$. By Lemma
3.6 the distance between $\iota_{n}(\bm{f},t)$ and $\iota_{n}((\bm{f},t)\cdot
s)$ is at most $q$ for all $(\bm{f},t)\in\mathcal{G}^{(1)}_{n}$. Using this
last remark and then that for all $r\leq\min(R,q)$ we can bound
$\rho\circ\log(r)$ by above by $\rho\circ\log(q)$, we obtain

$\displaystyle\Sigma_{R,n}$
$\displaystyle=\sum_{r=0}^{\min(R,q)}\rho\circ\log\left(r\right)\frac{\left|{\left\\{(\bm{f},t)\in\mathcal{G}_{n}^{(1)}\mid
d_{\mathcal{H}_{n}}\left(\iota_{n}(\bm{f},t),\iota_{n}((\bm{f},t)\cdot
s)\right)=r\right\\}}\right|}{\left|{\mathcal{G}_{n}}\right|}$
$\displaystyle\leq\rho\circ\log(q)\frac{\left|{\left\\{(\bm{f},t)\in\mathcal{G}_{n}^{(1)}\mid
d_{\mathcal{H}_{n}}\left(\iota_{n}(\bm{f},t),\iota_{n}((\bm{f},t)\cdot
s)\right)\leq
q\right\\}}\right|}{\left|{\mathcal{G}_{n}}\right|}=\rho\circ\log(q).$

If $s=(0,1)$ then using both Lemmas 3.7 and 3.9 we get that $\Sigma_{n,R}$ is
bounded (up to a multiplicative constant) by
$\sum_{m=0}^{n-1}\rho\circ\log\left(\kappa^{m+1}q^{\kappa^{m+1}}\right)\kappa^{-m}$.
But there exists $C\geq 1$ such that

$\displaystyle\rho\circ\log\left(\kappa^{m+1}q^{\kappa^{m+1}}\right)=\rho\left(\kappa^{m+1}\log(q)+m\log(\kappa)\right)$
$\displaystyle\leq\rho\left(C\kappa^{m}\right).$

Since $\rho(Cx)\leq C\rho(x)$ (see eq. 4.10b) we get that

$\sum_{m=0}^{n-1}\rho\circ\log\left(\kappa^{m+1}q^{\kappa^{m+1}}\right)\kappa^{-m}\leq
C\sum_{m=0}^{n-1}\rho\left(\kappa^{m}\right)\kappa^{-m}$

By hypothesis $(\rho\left(\kappa^{m}\right)\kappa^{-m})_{m}$ is summable, thus
the above sum can be bounded by a constant that does not depend on $R$ nor
$n$. Hence eq. 2.1 is verified. By Theorem 2.3 the coupling is a
$(\rho\circ\log,L^{0})$-integrable orbit equivalence. ∎

Let us now turn to the proof of Section 1.3. The idea is to compose the
coupling from $\Delta$ to $\mathbb{Z}$ just obtained with the one from
$\mathbb{Z}$ to $\mathbb{Z}^{d}$ given by the first point of Example 1.8. We
refer to [DKLMT20, Sections 2.3 and 2.5] for more details on the construction
of this composition and recall below the theorem we will use to obtain its
integrability.

######  Proposition 3.10 ([DKLMT20, Prop. 2.9 and 2.26]).

If $(X_{1},\mu_{1})$ (resp. $(X_{2},\mu_{2})$) is a
$(\varphi,L^{0})$-integrable (resp. $(\psi,L^{0})$-integrable) measure
equivalence coupling from $\Gamma$ to $\Lambda$ (resp. $\Lambda$ to $\Sigma$),
the composition of couplings gives a $(\varphi\circ\psi,L^{0})$-integrable
measure equivalence coupling from $\Gamma$ to $\Sigma$. If both couplings are
orbit equivalence couplings, then so is the composition.

We can now use it to prove our corollary on $\mathbb{Z}^{d}$.

###### Proof of Section 1.3.

Let $d\in\mathbb{N}^{*}$. Let $\rho\in\mathcal{C}$ and let $\Delta$ be the
diagonal product defined in Proposition A.12, in particular it verifies
$I_{\Delta}\simeq\rho\circ\log$. Recall that by the first point of Example 1.8
there exists an orbit equivalence from $\mathbb{Z}$ to $\mathbb{Z}^{d}$ that
is $(L^{p},L^{0})$-integrable for all $p<d$. Using the aforementioned
composition of couplings, we can deduce from Proposition 3.10 above that there
exists a $(\rho\circ\log(\cdot^{p}),L^{0})$-integrable orbit equivalence
coupling from $\Delta$ to $\mathbb{Z}^{d}$. Now if $d>p\geq 1$ by eq. 4.10b

$\rho\circ\log(x)\leq\rho(p\log(x))\leq p\rho\circ\log(x).$

Since $\rho(p\log(x))=\rho\circ\log(x^{p})$ we thus have
$\rho\circ\log(x^{p})\simeq\rho\circ\log$. When $p<1$, using Claim A.18
instead of eq. 4.10b we obtain a similar equivalence. Thus in both cases
$\rho\circ\log(x^{p})\simeq\rho\circ\log(x)$. Hence the corollary. ∎

##  4 Coupling between diagonal products

Our aim in this section is to show Section 1.3. We actually show the more
precise version below (Theorem 4.1). In particular the meaning of the
assumption that $\rho$ “does not grow too slowly” is formalised.

Let us set the framework of this Section 4. Recall that two sequences
$(k_{m})_{m}$ and $(l_{m})_{m}$ induce a piecewise affine map $\bar{\rho}$
(see Lemma A.16) and a bijective piecewise affine map $\rho_{\mathrm{bij}}$
(see Lemma A.19) such that the corresponding diagonal product $\Delta$
verifies $I_{\Delta}\sim\bar{\rho}\circ\log\sim\rho_{\mathrm{bij}}\circ\log$.

Framework (F) 1. $\kappa\geq 3$; 2. $\left(\tilde{k}_{m}\right)_{m}$ and
$(k_{m})_{m}$ are subsequences of $(\kappa^{m})_{m}$; 3. $(\tilde{l}_{m})$ and
$(l_{m})_{m}$ are subsequences of a geometric sequence; 4. $\tilde{\Delta}$ is
the diagonal product determined by the two sequences $(\tilde{k}_{m})$ and
$(\tilde{l}_{m})$ and $\tilde{\rho}$ is corresponding the piecewise affine
map; 5. $\Delta$ is the diagonal product determined by $(k_{m})_{m}$ and
$(l_{m})_{m}$ and $\rho_{\mathrm{bij}}$ is the corresponding _bijective_
piecewise affine map.

The following theorem precises the statement of Section 1.3.

######  Theorem 4.1.

In the framework (F), if

  * •

there exits $\varepsilon>0$ such that
$\tilde{\rho}\circ\rho_{\mathrm{bij}}^{-1}(x)\preccurlyeq x^{1-\varepsilon}$

  * •

and the sequence $l_{m}\exp(-l_{m-1})$ is summable

then there exists a
$\big{(}\tilde{\rho}\circ\rho_{\mathrm{bij}}^{-1},L^{0}\big{)}$-integrable
measure equivalence coupling from $\tilde{\Delta}$ to $\Delta$.

We will discuss the hypothesis and detail the idea of the proof but first let
us give some examples of diagonal products verifying the above conditions.

######  Example 4.2.

If $\rho(x)=x$ then $k_{1}=+\infty$ and $l_{1}=0$ and $\Delta$ is the usual
lamplighter group over $A\times B$. In particular it verifies the second
assumption. We will use this to show Section 1.3.

######  Example 4.3.

Let ${\rho}(x):=x^{1/(1+{\alpha})}$. In this case $k_{m}=\kappa^{m}$ and
$l_{m}=\kappa^{\alpha m}$ and the sequence $(l_{m}\exp(-l_{m-1}))_{m}$ is
therefore summable. In particualr, if
$\tilde{\rho}(x):=x^{1/(1+\tilde{\alpha})}$ with $\tilde{\alpha}>\alpha$ then
there exists a $(L^{(1+\alpha)/(1+\tilde{\alpha})},L^{0})$-coupling from
$\tilde{\Delta}$ to $\Delta$.

######  Example 4.4.

Similarly if $\rho(x)=\log(x)^{1/\alpha}$ then $k_{m}=\kappa^{m}$ and
$l_{m}=\exp(\kappa^{\alpha m})$. Such a sequence $(l_{m})_{m}$ verfies the
second assumption. More generally if $r\geq 1$ and
$\rho=\log\circ\cdots\circ\log$ with $r$ logarithms, then $k_{m}=\kappa^{m}$
and $l_{m}=\exp(\cdots\exp(\kappa^{m}))$ with $r$ exponentials. Again
$(l_{m})_{m}$ verfies the second assumption

We will discuss the hypothesis but first let us give the outline of the proof.
We recall that the idea of the latter — _without_ its technicities— is
contained in the demonstration of Section 1.3. We therefore strongly recommend
to read Section 3 before entering into the details of the present section.

##### Idea of the proof

Similarly as in Section 3, the idea is to use Theorem 2.3. We thus start by
constructing appropriate Sofic approximations for the two diagonal products
$\tilde{\Delta}$ and $\Delta$. In Section 4.2 we define the injection between
the aforementioned approximations and finally show in Section 4.2 that this
map satisfies eq. 2.1. Let us describe the process in more details.

Our goal is to define $\mathcal{G}_{n}$ in $\tilde{\Delta}$ and
$\mathcal{H}_{n}$ in $\Delta$ being two Sofic approximations and a $C$-dense
injection between $\mathcal{G}_{n}$ and $\mathcal{H}_{n}$, where $C$ is a
constant that _does not depend on n_. To construct this injection we are going
to “encode” the information contained in an element of $\mathcal{G}_{n}$ in
two different integers, that is to say we are going to define an embedding
from $\mathcal{G}_{n}$ to $\mathbb{Z}^{2}$. This part is the analogue of the
encoding described in Sections 3.1.1 and 3.1.2 for the coupling with
$\mathbb{Z}$. Doing the same thing for elements of $\mathcal{H}_{n}$ we will
obtain the wanted injection from $\mathcal{G}_{n}$ to $\mathcal{H}_{n}$ (see
Figure 7). Then our goal would be to show that the injection $\iota_{n}$ thus
defined verifies eq. 2.1 with
$\varphi:=\tilde{\rho}\circ\rho_{\mathrm{bij}}^{-1}$.

$\mathcal{G}_{n}$$\mathcal{H}_{n}$$\mathbb{Z}^{2}$$(\bm{f},t)$$(\bm{g},u)$$(x,y)$$\iota_{n}$
Figure 7: Definition of the injection: first idea

This is the general idea, let us now describe the encoding process. An element
$(\bm{f},t)$ of $\mathcal{G}_{n}$ or $\mathcal{H}_{n}$ is composed of two
informations: a lamp configuration $\bm{f}$ and a cursor $t$. A first “naive”
way to proceed to define the injection would be to associate to every lamp
configuration $\bm{f}$ appearing in $\mathcal{G}_{n}$ a lamp configuration
$\bm{h}$ that appears in $\mathcal{H}_{n}$, and to each cursor $t$ of an
element in $\mathcal{G}_{n}$ a cursor $u$ appearing in $\mathcal{H}_{n}$. In
doing so we would need $\mathcal{H}_{n}$ to verify

$\big{|}{\big{\\{}\bm{g}\ |\ \exists
u\in\mathbb{Z},\,(\bm{g},u)\in\mathcal{H}_{n}\big{\\}}}\big{|}\geq\big{|}{\big{\\{}\bm{f}\
|\ \exists t\in\mathbb{Z},\,(\bm{f},t)\in\mathcal{G}_{n}\big{\\}}}\big{|}.$
(4.1)

But by assumption on the isoperimetric profile, $\tilde{\Delta}$ is the
“bigger group” hence for $m$ large enough the number of elements in
$\tilde{\Gamma}^{\prime}_{m}$ is larger than the one of $\Gamma^{\prime}_{m}$.
Therefore for the same support we have more possible lamp configurations
$f^{\prime}_{m}:\mathbb{Z}\rightarrow\tilde{\Gamma}^{\prime}_{m}$ than we have
of the form $g^{\prime}_{m}:\mathbb{Z}\rightarrow{\Gamma}^{\prime}$. In other
words, in order for $(\mathcal{H}_{n})_{n\in\mathbb{N}}$ to be a Følner
sequence of the form $(F_{d_{n},i_{n},j_{n}})_{n\in\mathbb{N}}$ that verifies
eq. 4.1 above, we would need the sequence $(d_{n})_{n\in\mathbb{N}}$ to grow
much faster than $n$. In these conditions the map sending a cursor $t\in[0,n]$
to a cursor $u\in[0,d_{n}-1]$ would only reach a few cursors and the
proportion of unreached cursors would grow with $n$. Hence it would be
impossible to obtain a $C$-dense injection with $C$ not depending on $n$.

This is why we build our injection in the following way: given an element
$(\bm{f},t)$ in $\mathcal{G}_{n}$, we use a part of the information contained
in the lamp configuration and the cursor $t$ to define a cursor in $\Delta$.
The unused information contained in $\bm{f}$ is then used to define a lamp
configuration in $\mathcal{H}_{n}$. See Figure 8 for an illustration. The
encoding process of this lamp configurations into an integer is based on the
same decomposition in nested intervals developped in Section 3.1.1. We
therefore refer to the lead paragraph of Section 3.1 for the strategy of this
”blocs decomposition”. We finally prove that the map $\iota_{n}$ thus defined
is a $C$-dense injection for some constant $C$.

Finally, the object of Section 4.3 is to prove that $\iota_{n}$ verifies eq.
2.1. To do so, we first study the behaviour of $\iota_{n}$ under the action of
the generators of $\tilde{\Delta}$: for $s\in S_{\tilde{\Delta}}$ and
$(\bm{f},t)\in\mathcal{G}_{n}$, we give an estimate of the distance between
$\iota_{n}(\bm{f},t)$ and $\iota_{n}\big{(}(\bm{f},t)s\big{)}$. This section
is the analogue of Section 3.2.1. Then, similarly as in Section 3.2.2, we
compute for a given distance $r$ the proportion of elements in
$\mathcal{G}_{n}$ such that $\iota_{n}(\bm{f},t)$ is at distance $r$ from
$\iota_{n}\big{(}(\bm{f},t)s\big{)}$. We conclude by showing that eq. 2.1 is
verified.

##### Hypothesis

As discussed in the introduction, the construction we make is suitable for a
coupling from the _bigger_ group to the _smaller_ one, that is to say from the
group with slower isoperimetric profile to the one with faster isoperimetric
profile. This is what is reflected in the condition on the growth of
$\tilde{\rho}\circ\rho_{\mathrm{bij}}^{-1}$. We use it more precisely in the
proof of Lemma 4.5 and Section 4.3.3, when checking the integrability
condition.

The condition on $(l_{m})_{m\in\mathbb{N}}$ is only a technical assumption
that could be avoided by considering another numbering process, more complex,
subdividing the groups $\Gamma^{\prime}_{m}$. However, as Examples 4.3, 4.4
and 1.3 show, this summability condition is verified by a large family of
diagonal products. Let us describe where we use it. First consider
$(\bm{f},t)\in\mathcal{G}_{n}$ and $(\bm{g},u)=\iota_{n}(\bm{f},t)$ its image
by the built injection. The action of a generator on $(\bm{f},t)$ might modify
the value of $g_{0},g^{\prime}_{1},\ldots,g^{\prime}_{m}$ in $\Delta$ for some
$m\in\mathbb{N}$ (see Section 4.3.1 for more details). Denote
$D_{n}=\mathrm{range}(\bm{g},u)$, we can show that the distance between
$(\bm{g},u)$ and this modified element is then equivalent to $D_{n}l_{m}$. Now
the proportion of such elements $(\bm{f},t)$ in $\mathcal{G}_{n}$ is
asymptotically bounded by $|\Gamma^{\prime}_{m-1}|^{-1}q^{-D_{n}}$ (see Lemma
4.29). But $|\Gamma^{\prime}_{m-1}|\sim\exp\big{(}l_{m-1}\big{)}$. Hence for
eq. 2.1 to be verified, we need the sequence
$\left(D_{n}q^{-D_{n}}l_{m}\exp\big{(}l_{m-1}\big{)}\right)_{m\in\mathbb{N}}$
to be summable. The hypothesis made on $(l_{m})_{m}$ ensures this
integrability. We refer to Sections 4.3.3 and 4.3.3 for the corresponding
computations using it.

###  4.1 Definition of the Sofic approximation

Let $\mathcal{G}_{n}:=\tilde{F}_{\kappa^{n}}\subset\tilde{\Delta}$. In this
subsection we build an injection from $\mathcal{G}_{n}$ to $\mathbb{Z}^{2}$.

The idea summed up in Figure 8 and described in Section 4.1.2 is the
following: we encode a part of the information contained in the lamp
configuration (in blue) to obtain the first integer $x$ and we use the cursor
and a part of the lamp configuration (represented in grey) to give the second
integer $y$. In Section 4.1.3 we give an estimate of the possible values of
$x$. Indeed, this is the number we will use to define the lamp configuration
in $\Delta$ and obtain our injection. Thus when defining $\mathcal{K}_{n}$ we
need to ensure that this last set contains enough possible lamp configurations
to encode all possible values of $x$.

Figure 8: Numbering in $\tilde{\Delta}$

####  4.1.1 Numbering framework

Let $d_{n}\in\mathbb{N}$ and $i_{n}\in[0,\mathfrak{l}(d_{n}-1)]$ and
$j_{n}\in[0,N_{i_{n}}]$ such that

$\left|{F_{d_{n},i_{n},j_{n}-1}}\right|<\left|{\mathcal{G}_{n}}\right|\leq\left|{F_{d_{n},i_{n},j_{n}}}\right|.$
(4.2)

The ideal thing to do would be to define an injection from $\mathcal{G}_{n}$
to $F_{d_{n},i_{n},j_{n}}$. As we will see at the end of this section, the
numbering process we use requires that we consider $F_{d_{n},i_{n},j_{n}+1}$
instead of $F_{d_{n},i_{n},j_{n}}$ (see Section 4.1.3 for a discussion of such
a necessity). But when $i_{n}=\mathfrak{l}(d_{n}-1)$ and $j_{n}=N_{i_{n}}-1$
the Følner we will work with actually verifies
$F_{d_{n},i_{n},j_{n}+1}=F_{d_{n}+1,0,0}$. In particular there are $d_{n}+1$
possible values for the cursor (and not $d_{n}$). So in order to work with the
right number of cursors we define

$D_{n}=\begin{cases}d_{n}&\text{if}\ j_{n}<N_{i_{n}}-1\ \text{and}\
i_{n}<\mathfrak{l}{d_{n}-1},\\\ d_{n}+1&\text{else}.\end{cases}$ (4.3)

Finally we define $I_{n}\in[0,\mathfrak{l}(D_{n}-1)]$ and $J_{n}\leq
N_{I_{n}}$ such that $F_{D_{n},I_{n},J_{n}}=F_{d_{n},i_{n},j_{n}+1}$.

As explained above we have to extract information from $\bm{f}$ and combine it
with $t$ to define the cursor (denoted $u$) in $\Delta$. Recall that if
$(\bm{f},t)$ is in $\mathcal{G}_{n}$ then $t$ belongs to $[0,\kappa^{n}-1]$.
The idea is thus to split the interval $[0,D_{n}]$ in subintervals of length
$\kappa^{n}$ plus some remainder interval of length less than $\kappa^{n}$.
The extracted information from $\bm{f}$ will define the subinterval in which
our cursor $u$ will be and $t$ will give the position of $u$ inside that
subinterval (see eq. 4.10). Before defining $u$ we explicit how to extract the
wanted information from $\bm{f}$ and then how to define our integer encoding
the remaining data of $\bm{f}$. Let us denote the Euclidean division of
$D_{n}$ by $\kappa^{n}$ by

$D_{n}=Q_{n}\kappa^{n}+R_{n}\qquad 0\leq R_{n}<\kappa^{n}.$ (4.4)

######  Lemma 4.5.

If $\tilde{\rho}\circ\rho_{\mathrm{bij}}^{-1}(x)\preccurlyeq
x^{1-\varepsilon}$ for some $\varepsilon>0$ then the sequence $(Q_{n})_{n}$ is
unbounded. In particular there exists $n_{0}\geq 0$ such that for all $n\geq
n_{0}$

  1. 1.

$Q_{n}\geq 3$;

  2. 2.

$D_{n}\geq d_{n}>\kappa^{n}$.

So up to consider $(\mathcal{G}_{n})_{n\geq n_{0}}$ instead of
$(\mathcal{G}_{n})_{n\geq 0}$ we can assume without loss of generality that
$Q_{n}\geq 3$ for all $n$.

To prove this lemma we rely on the properties of $\rho_{\mathrm{bij}}$ and
$\bar{\rho}$ showed in Section A.3.

###### Proof.

By Remarks 2.9 and 4.2

$C_{3}\kappa^{n-1}\tilde{l}_{\mathfrak{L}(n)}\leq\ln|\mathcal{G}_{n}|\leq\ln|F_{d_{n},i_{n},j_{n}}|.$

But by Proposition 2.8 there exists some constant $C_{2}>0$ such that
$\ln|F_{d_{n},i_{n},j_{n}}|$ is bounded by above by
$C_{2}d_{n}l_{\mathfrak{l}(d_{n}-1)}$. Noting that $d_{n}$ is smaller than
$2(d_{n}-1)$ we obtain

$\kappa^{n}\tilde{l}_{\mathfrak{L}(n)}\leq\frac{2\kappa
C_{2}}{C_{3}}\left(d_{n}-1\right)l_{\mathfrak{l}(d_{n}-1)}.$

Now recall that by definition of $\mathfrak{l}$ we have
$k_{\mathfrak{l}(d_{n}-1)}\leq d_{n}-1<k_{\mathfrak{l}(d_{n}-1)+1}$. Hence by
Lemma A.16 we have
$\bar{\rho}\big{(}(d_{n}-1)l_{\mathfrak{l}(d_{n}-1)}\big{)}=d_{n}-1$. Thus by
Lemma A.19

$\kappa^{n}\tilde{l}_{\mathfrak{L}(n)}\leq\frac{2C_{2}\kappa}{C_{3}}\rho_{\mathrm{bij}}^{-1}\left(2(d_{n}-1)\right).$

Using first that
$\tilde{\rho}(\kappa^{n}\tilde{l}_{\mathfrak{L}(n)})=\kappa^{n}$ and second
that $\tilde{\rho}\in\mathcal{C}$ and thus verifies eq. 4.10b we obtain

$\kappa^{n}=\tilde{\rho}(\kappa^{n}\tilde{l}_{\mathfrak{L}(n)})\leq\max\left\\{1,\,2C_{2}\kappa/C_{3}\right\\}\tilde{\rho}\circ\rho_{\mathrm{bij}}^{-1}\left(2(d_{n}-1)\right).$

But recall that $\tilde{\rho}\circ\rho_{\mathrm{bij}}^{-1}(x)\preccurlyeq
x^{1-\varepsilon}$. Hence $\kappa^{n}\preccurlyeq(d_{n}-1)^{1-\varepsilon}$
and thus using eq. 4.4

$\kappa^{n}\preccurlyeq
d^{1-\varepsilon}_{n}\leq(Q_{n}+1)^{1-\varepsilon}\kappa^{n(1-\varepsilon)}.$

Therefore $\kappa^{n\varepsilon}\preccurlyeq(Q_{n}+1)^{1-\varepsilon}$. Since
the left term tends to infinity, so does $Q_{n}$. In particular there exists
$n_{0}$ such that $Q_{n}\geq 3$ for all $n\geq n_{0}$ and

$D_{n}\geq d_{n}\geq Q_{n}\kappa^{n}-1\geq 3\kappa^{n}-1>\kappa^{n}.$

∎

####  4.1.2 Numbering in $\tilde{\Delta}$

Consider $(\bm{f},t)\in\mathcal{G}_{n}$ and let us describe our encoding
process. The first goal is to encode the information contained in $\bm{f}$ in
an integer. The idea is very similar to the one used in Section 3.1. What
changes here is that we are going to extract some information from $\bm{f}$
and use it to define the cursor in the second diagonal product $\Delta$.

Recall that $(\bm{f},t)$ is uniquely determined by the value of $t$, of
$f_{0}$ and $(f^{\prime}_{m})_{m\geq 1}$. Similarly as in Section 3.1 let
$t=\sum^{n-1}_{i=0}t_{i}\kappa^{i}$ be the decomposition in base $\kappa$ of
$t$. Define for $t\in[0,\kappa^{n}-1]$ and $i\in\\{0,\ldots,n\\}$:

$\tilde{\mathcal{B}}_{i}(t):=\left[\sum^{n-1}_{j=i}t_{j}\kappa^{j},\sum^{n-1}_{j=i}t_{j}\kappa^{j}+\kappa^{i}-1\right].$
(4.5)

The conclusions of Lemma 3.1 apply to
$\big{(}\tilde{\mathcal{B}}_{i}(t)\big{)}_{i}$. In particular we can define as
before the following bijections:

$\displaystyle\tilde{\nu}_{0}\,$
$\displaystyle:\,\left\\{\zeta:\,\tilde{\mathcal{B}}_{0}(t)\rightarrow A\times
B\right\\}\rightarrow\left[0,q-1\right],$ $\displaystyle\forall i\geq
1\quad\tilde{\nu}_{i}\,$
$\displaystyle:\,\left\\{\zeta:\,\tilde{\mathcal{B}}_{i}(t)\backslash\tilde{\mathcal{B}}_{i-1}(t)\rightarrow
A\times B\right\\}\rightarrow\left[0,q^{\kappa^{i}-\kappa^{i-1}}-1\right]$
$\displaystyle\tilde{\mu}_{n}\,$
$\displaystyle:\,\left\\{\bm{f}^{\prime}|\,\mathrm{supp}\left(f^{\prime}_{m}\right)\subseteq\left[\tilde{k}_{m},\kappa^{n}-1\right],\
\forall
m\in\left[0,\mathfrak{L}(n)\right]\right\\}\rightarrow\left[0,\,\frac{|\mathcal{G}_{n}|}{\kappa^{n}q^{\kappa^{n}}}-1\right].$

Recall that Figure 6 represents the information encoded by each of these maps.

As explained above, we need to extract information from $\bm{f}$ to define our
cursor in $\Delta$. To that end we denote the Euclidean division of
$\tilde{\mu}_{n}(\bm{f}^{\prime})$ by $Q_{n}$ by

$\tilde{\mu}_{n}(\bm{f}^{\prime})=E_{n}(\bm{f}^{\prime})Q_{n}+P_{n}(\bm{f}^{\prime})\qquad
0\leq P_{n}(\bm{f}^{\prime})<Q_{n}.$ (4.6)

The value of $P_{n}$ is the part that will be used for the cursor. Let us now
define a variable base $\big{(}\tilde{b}_{i}\big{)}_{i}$ and express our
numbering in it (see appendix B for details on variable base).

$\displaystyle{\tilde{b}}_{0}=q$ $\displaystyle\forall i\in[1,n]\quad$
$\displaystyle{\tilde{b}}_{i}=q^{\kappa^{i}-\kappa^{i-1}}$
$\displaystyle{\tilde{b}}_{n+1}=\max(E_{n})+1.$

Please note that the variable base depends on $n$ but in order to reduce
formalism we chose to abuse notations and write ${\tilde{b}}_{i}$ instead of
${\tilde{b}}_{n,i}$. In this base we thus write

$\begin{split}\tilde{\vartheta}_{n}(\bm{f},t):=&\tilde{\nu}_{0}\left(f_{0|\tilde{\mathcal{B}}_{0}(t)}\right)+\sum^{n}_{i=1}\tilde{\nu}_{i}\left(f_{0|\tilde{\mathcal{B}}_{i}(t)\backslash\tilde{\mathcal{B}}_{i-1}(t)}\right)\tilde{b}_{i-1}\cdots\tilde{b}_{0}\\\
&+E_{n}(\bm{f},t)\tilde{b}_{n}\cdots\tilde{b}_{0}.\end{split}$ (4.7)

######  Remark 4.6.

Remark that this base differs from $(\beta_{i})_{i}$ defined Section 3.1.2
only from the last coefficient. In particular
$\tilde{b}_{i}\cdots\tilde{b}_{0}=q^{\kappa^{i}}$ for all $i\in[0,n]$. The
difference between the last coefficients comes from the extraction made in eq.
4.4.

We saw in Claim 3.4 that $\tilde{\mu}_{n}$ was surjective onto
$[0,\max\tilde{\mu}_{n}-1]$, but it does not necessarily imply that
$(E_{n},P_{n})$ is surjective onto the product
$[0,\max(E_{n})]\times[0,Q_{n}-1]$. Indeed unless $\max\tilde{\mu}_{n}$ equals
$\big{(}\max(E_{n})+1\big{)}Q_{n}-1$, some elements of
$\\{\max(E_{n})\\}\times[0,Q_{n}-1]$ might not be reached. This is what the
next lemma specifies and what will lead to the definition of $\mathcal{H}_{n}$
given in eq. 4.10q.

######  Lemma 4.7.

The map sending $(\bm{f},t)$ to
$\big{(}t,\tilde{\vartheta}_{n}(\bm{f},t),P_{n}(f^{\prime})\big{)}$ is a
bijection from $\mathcal{G}_{n}$ to the set

$\begin{split}[0,\kappa^{n}-1]\times&\Big{(}\left[0,q^{\kappa^{n}}\max(E_{n})-1\right]\times\left[0,Q_{n}-1\right]\\\
&\left.\quad\cup\left[q^{\kappa^{n}}\max(E_{n}),\max(\tilde{\vartheta}_{n})\right]\times\left[0,\max\tilde{\mu}_{n}-Q_{n}\max
E_{n}\right]\right).\end{split}$

###### Proof.

Let us first prove the injectivity. If
$\big{(}t,\tilde{\vartheta}_{n}(\bm{f},t),P_{n}(f^{\prime})\big{)}$ equals
$\big{(}t^{\prime},\tilde{\vartheta}_{n}(\bm{g},t\prime),P_{n}(g^{\prime})\big{)}$
then $P_{n}(f^{\prime})=P_{n}(g^{\prime})$ and $t=t\prime$. Thus
$\tilde{\mathcal{B}}_{i}(t)=\tilde{\mathcal{B}}_{i}(t\prime)$ for all $i$ and
by unicity of the decomposition in variable base (see Lemma B.1)

$\tilde{\nu}_{0}\left(f_{0|\tilde{\mathcal{B}}_{0}(t)}\right)=\tilde{\nu}_{0}\left(g_{0|\tilde{\mathcal{B}}_{0}(t)}\right)\quad\tilde{\nu}_{i}\left(f_{0|\tilde{\mathcal{B}}_{i}(t)\backslash\tilde{\mathcal{B}}_{i-1}(t)}\right)=\tilde{\nu}_{i}\left(g_{0|\tilde{\mathcal{B}}_{i}(t)\backslash\tilde{\mathcal{B}}_{i-1}(t)}\right).$

and $E_{n}(\bm{f})=E_{n}(\bm{g}\prime)$. In particular
$\tilde{\mu}_{n}(\bm{f}^{\prime})=\tilde{\mu}_{n}(\bm{g}\prime)$ and thus
$\bm{f}\prime=\bm{g}\prime$, by bijectivity of $\tilde{\mu}_{n}$. Similarly
the bijectivity of the $\tilde{\nu}_{i}$’s implies that $f_{0}$ coincide with
$g_{0}$ on

$\tilde{\mathcal{B}}_{0}(t)\bigcup\bigcup_{i}\left(\tilde{\mathcal{B}}_{i}(t)\backslash\tilde{\mathcal{B}}_{i-1}(t)\right)=[0,\kappa^{n}-1].$

Hence $\bm{f}=\bm{g}$ and thus the injectivity.

Now let $t\in[0,\kappa^{n}-1]$. Recall that $\tilde{\mu}_{n}$ is bijective
onto $[0,\max\tilde{\mu}_{n}]$. Using eq. 4.6 we obtain that $Q_{n}E+P$ is
smaller than $\max\tilde{\mu}_{n}$ for all $P<Q_{n}$ and all $E<\max(E_{n})$.
In particular for all such $E$ and $P$ there exists $\bm{f}$ such that
$\tilde{\mu}_{n}(\bm{f}\prime)=EQ_{n}+P$. Now if $E=\max(E_{n})$ then there
exists $\bm{f}$ such that $\tilde{\mu}_{n}(\bm{f}\prime)=EQ_{n}+P$ if and only
if $P\leq\max\tilde{\nu}_{n}-Q_{n}\max E_{n}$.

Now, since the $\tilde{\nu}_{t,i}$ and $\tilde{\mu}_{m}$ are bijections, Lemma
B.1 implies that the image of $\tilde{\vartheta}_{n}(\cdot,t)$ is the interval
$[0,\max\tilde{\vartheta}_{n}]$. Consider $x$ in this interval and write
$[x_{0},\ldots,x_{n+1}]_{\tilde{\bm{b}}}$ its decomposition in base
$(\tilde{b}_{i})_{i}$. If $x<q^{\kappa^{n}}\max(E_{n})$ then
$x_{n+1}<\max(E_{n})$. In particular by the above study of
$\mathrm{im}(\tilde{\mu}_{n})$ for all $P\in[0,Q_{n}-1]$ there exists
$\bm{f}^{\prime}$ such that $\tilde{\mu}_{n}(\bm{f}\prime)=x_{n}Q_{n}+P$, that
is to say $P_{n}(\bm{f}^{\prime})=P$ and $E_{n}(\bm{f}\prime)=x_{n}$. If
$x\geq q^{\kappa^{n}}\max(E_{n})$ a similar argument as above gives that for
all $P$ smaller than $\max\tilde{\nu}_{n}-Q_{n}\max E_{n}$ there exists
$\bm{f}^{\prime}$ such that $E_{n}(\bm{f}\prime)=E$ and
$P_{n}(\bm{f}^{\prime})=P$. Finally, in both cases there exists $f_{0}$ such
that
$x_{i}=\tilde{\nu}_{i}\left(f_{0|\tilde{\mathcal{B}}_{i}(t)\backslash\tilde{\mathcal{B}}_{i-1}(t)}\right)$
for all $i$. The element $(\bm{f},t)$ thus defined verifies
$\tilde{\vartheta}_{n}(\bm{f},t)=x$ and $P_{n}(\bm{f}^{\prime})=P$. Hence the
surjectivity. ∎

Now that we encoded the information in a integer we will have to do the
reverse process in $\Delta$, that is to say we will have to convert this
integer into a lamp configuration in $\Delta$. We thus have to give an
estimate of the amount of lamps we need to encode all the possible values of
$\tilde{\vartheta}_{n}$. This is the object of the next paragraph.

####  4.1.3 Bounds

In order to obtain the number of lamps in $\Delta$ needed to encode the
information contained in $\tilde{\vartheta}_{n}(\bm{f},t)$, we need to
estimate the maximal value taken by $\tilde{\vartheta}$.

Why such a need? The “ideal” Følner set used to define $\mathcal{H}_{n}$ would
have been ${F}_{d_{n},i_{n},j_{n}}$ but the encoding process we chose does not
allow us to work with this set. Indeed assume for example that
$|{F}_{d_{n},i_{n},j_{n}}|=|\mathcal{G}_{n}|$. In that case we could
—theoretically speaking— find a bijection between these two sets. But to
obtain such a map we would need to extract the optimal quantity of information
from the lamps $\bm{f}$ to define the cursor $u$ in $\Delta$. What we actually
do when defining our map $\tilde{\vartheta}_{n}$ is that we take a little “too
much” information from the lamp configuration $\bm{f}$ to define the integer
$\tilde{\vartheta}_{n}(\bm{f},t)$ and thus we left “not enough“ information to
be used to define the cursor in $\Delta$. Hence when defining our wanted
embedding from $\mathcal{G}_{n}$ to $F_{d_{n},i_{n},j_{n}}$, not all the
cursors in $[0,d_{n}-1]$ will be reached (see Section 4.2.1) and we will need
a little more lamp configurations than the possible ones in
$F_{d_{n},i_{n},j_{n}}$ to encode all the values of $\tilde{\vartheta}_{n}$.
What Lemma 4.8 shows is that $F_{d_{n},i_{n},j_{n}+1}$ contains enough lamps
configurations to allow us to encode the values of $\tilde{\vartheta}_{n}$ in
it.

Thus our aim in this paragraph is to prove the following lemma.

######  Lemma 4.8.

For $n$ large enough

$\left|{F_{d_{n},i_{n},j_{n}-1}}\right|/D_{n}\,\leq\,\max_{(\bm{f},t)\in\mathcal{G}_{n}}\tilde{\vartheta}_{n}(\bm{f},t)+1\,\leq\,\left|{F_{d_{n},i_{n},j_{n}+1}}\right|/D_{n}.$

But before proving the above statement, let us bound the value of
$\tilde{b}_{n+1}=\max(E_{n})+1$.

######  Lemma 4.9.

For $n$ large enough

$\frac{\left|{F_{d_{n},i_{n},j_{n}-1}}\right|}{D_{n}q^{\kappa^{n}}}\leq\max(E_{n})+1\leq\frac{\left|{F_{d_{n},i_{n},j_{n}+1}}\right|}{D_{n}q^{\kappa^{n}}}$

###### Proof.

Let $n\in\mathbb{N}^{*}$. By eq. 4.6 we have
$E_{n}=\left\lfloor{\tilde{\mu}_{n}/Q_{n}}\right\rfloor$, thus
$E_{n}\leq\tilde{\mu}_{n}/Q_{n}\leq E_{n}+1$. Since
$\max(\tilde{\mu}_{n})={\left|\mathcal{G}_{n}\right|}/(\kappa^{n}q^{\kappa^{n}})$
we hence have

$\max(E_{n})\leq\frac{{\left|\mathcal{G}_{n}\right|}}{Q_{n}\kappa^{n}q^{\kappa^{n}}}\leq\max(E_{n})+1.$
(4.8)

Let us show the left inequality of the lemma. Using the lower bound given by
eq. 4.2 and then eq. 4.4 we get,

$\displaystyle\max(E_{n})+1\geq\frac{|\mathcal{G}_{n}|}{Q_{n}\kappa^{n}q^{\kappa^{n}}}\geq\frac{\left|{F_{d_{n},i_{n},j_{n}-1}}\right|}{Q_{n}\kappa^{n}q^{\kappa^{n}}}\geq\frac{\left|{F_{d_{n},i_{n},j_{n}-1}}\right|}{D_{n}q^{\kappa^{n}}}.$

Now for the upper bound. By eq. 4.2 we know that
$|\mathcal{G}_{n}|\leq\left|{F_{d_{n},i_{n},j_{n}}}\right|$, hence using the
left part of eq. 4.8 we get that $\max(E_{n})+1$ is less or equal to
${\left|{F_{d_{n},i_{n},j_{n}}}\right|}/(\kappa^{n}Q_{n}q^{\kappa^{n}})+1$.
Now using the euclidean division given by eq. 4.4 we get
$D_{n}/(Q_{n}\kappa^{n})\leq 1+1/Q_{n}$, thus

$\max(E_{n})+1\leq\frac{\left|{F_{d_{n},i_{n},j_{n}}}\right|}{\kappa^{n}Q_{n}q^{\kappa^{n}}}+1\leq\frac{\left|{F_{d_{n},i_{n},j_{n}}}\right|}{D_{n}q^{\kappa^{n}}}\left(1+\frac{1}{Q_{n}}\right)+1.$

Using that $Q_{n}$ is unbounded (Lemma 4.5) we obtain that for $n$ large
enough $\max(E_{n})+1\leq
2\left|{F_{d_{n},i_{n},j_{n}}}\right|/(D_{n}q^{\kappa^{n}})$. So up to
consider $(\mathcal{G}_{n})_{n\geq N}$ for some $N>0$, we can assume that this
is true for all $n$. We obtain the lemma using Lemma 2.7. ∎

We can now prove that we need at most
$\left|{F_{d_{n},i_{n},j_{n+1}}}\right|/D_{n}$ to encode the information
contained in the integer $\tilde{\vartheta}_{n}(\bm{f},t)$.

###### Proof of Lemma 4.8.

. By eq. 4.7 and Lemma B.1 we have
$\max(\tilde{\vartheta}_{n})+1\,=\,\prod^{n+1}_{i=0}\tilde{b}_{i}$. Now recall
(see Remark 4.6) that $\prod^{n}_{i=0}\tilde{b}_{i}=q^{\kappa^{n}}$. Hence,
$\max(\tilde{\vartheta}_{n})+1=\left(\max E_{n}+1\right)q^{\kappa^{n}}$. We
conclude using the bounds given in Lemma 4.9. ∎

Now remark that $\left|{F}_{d_{n},i_{n},j_{n}+1}\right|/D_{n}$ is exactly the
number of possible lamp configurations for elements in
${F}_{d_{n},i_{n},j_{n}+1}$. Hence by the above lemma we can define an
embedding from $[0,\max\tilde{\vartheta}_{n}]$ to the set of lamp
configurations of elements in ${F}_{d_{n},i_{n},j_{n}+1}$. We define

$\mathcal{K}_{n}:={F}_{d_{n},i_{n},j_{n}+1}=F_{D_{n},I_{n},J_{n}}.$ (4.9)

and now have to define and injection between $\mathcal{G}_{n}$ and
$\mathcal{K}_{n}$.

######  Remark 4.10.

Note that $|\mathcal{K}_{n}|\sim|\mathcal{G}_{n}|$. Indeed by eq. 4.2 we have
$|\mathcal{G}_{n}|\leq\left|{F}_{d_{n},i_{n},j_{n}}\right|\leq|\mathcal{K}_{n}|$.
Moreover using twice Lemma 2.7, we obtain

$|\mathcal{K}_{n}|\leq 2q\left|{F}_{d_{n},i_{n},j_{n}}\right|\leq
4q^{2}\left|{F}_{d_{n},i_{n},j_{n}-1}\right|\leq 4q^{2}|\mathcal{G}_{n}|.$

###  4.2 Injection between Sofic approximation

Let $n\in\mathbb{N}$ and recall that $\mathcal{G}_{n}=\tilde{F}_{\kappa^{n}}$
and $\mathcal{K}_{n}={F}_{d_{n},i_{n},j_{n}+1}$. The purpose of this section
is to define an injection $\iota_{n}$ from $\mathcal{G}_{n}$ to
$\mathcal{K}_{n}$. Moreover we want that injection to be $C$-dense for some
$C>0$. Let $(\bm{f},t)\in\mathcal{G}_{n}$ and denote by
$\left(\bm{g},u\right)$ the image of $(\bm{f},t)$ by $\iota_{n}$. We first
explicit the definition of the cursor $u$, then turn to the definition of
$\bm{g}$ and conclude by showing that $\iota_{n}$ thus defined is injective
and $C$-dense.

####  4.2.1 Cursor

Recall that the Euclidean division of $D_{n}$ by $\kappa^{n}$ is given by
$D_{n}=Q_{n}\kappa^{n}+R_{n}$. As explained in the last section, the idea is
to split $[0,D_{n}-1]$ in subintervals of length $\kappa^{n}$ (plus some
remainder interval of length less than $\kappa^{n}$) and to use $P_{n}$ to
define the subinterval in which the cursor $u$ will be and use $t$ to give the
position of $u$ inside that subinterval. In other words we would like to set
$u(\bm{f},t)=P_{n}(\bm{f}^{\prime})\kappa^{n}+t$, but such a definition of the
cursor $u$ would leave the $R_{n}$-last cursors of $[0,D_{n}-1]$ out of
$im(\iota_{n})$. The injection would thus not be $C$-dense. To counter this we
distribute the unreached cursors inside the last subinterval (see Figure 9 for
an illustration).

Let $t\in[0,\kappa^{n}]$ and $P\in[0,Q_{n}-1]$

$\displaystyle[left={u:=u(P,t)\empheqlbrace}$ $\displaystyle P\kappa^{n}+t$
$\displaystyle\text{if}\ P<Q_{n}-1,$ (4.10a) $\displaystyle P\kappa^{n}+2t$
$\displaystyle\text{if}\ P=Q_{n}-1\ \text{and}\ t<R_{n}$ (4.10b)
$\displaystyle P\kappa^{n}+R_{n}+t$ $\displaystyle\text{if}\ P=Q_{n}-1\
\text{and}\ t\geq R_{n}.$ (4.10c)

We represent in Figure 9 the possible values of $u$ when $Q_{n}=4$ and
$R_{n}=3$.

Figure 9: Possible values for $u$ when $D_{n}=4\kappa^{n}+3$.

######  Claim 4.11.

Let $P\in[0,Q_{n}-1]$, let $t\in[0,\kappa^{n}-1]$ and $u$ be as defined in eq.
4.10. Then $u(P,t)\in[0,D_{n}-1]$. In particular
$u\left(P_{n}(\bm{f}^{\prime}),t\right)\in[0,D_{n}-1]$ for all
$(\bm{f},t)\in\mathcal{G}_{n}$.

###### Proof.

First recall that we always have $t<\kappa^{n}$. Now if $P<(Q_{n}-1)$ then

$u(P,t)=P\kappa^{n}+t\leq(Q_{n}-1)\kappa^{n}+\kappa^{n}-1\leq D_{n}$

If $P=Q_{n}-1$ and $t<R_{n}$ then

$u(P,t)=(Q_{n}-1)\kappa^{n}+2t<(Q_{n}-1)\kappa^{n}+R_{n}+\kappa^{n}-1=Q_{n}\kappa^{n}+R_{n}=D_{n}.$

Finally in the last case we get
$u(P,t)=(Q_{n}-1)\kappa^{n}+R_{n}+t<(Q_{n}-1)\kappa^{n}+R_{n}+\kappa^{n}=D_{n}$.
∎

####  4.2.2 Numbering in $\Delta$

For now we have an integer $\tilde{\vartheta}_{n}(\bm{f},t)$ and a cursor
$u\big{(}P_{n}(\bm{f}^{\prime}),t\big{)}$ defined above. Our goal is to
associate to $\tilde{\vartheta}_{n}(\bm{f},t)$ a lamp configuration sequence
$\bm{g}$ in $\Delta$ supported on $[0,D_{n}-1]$. For each value of
$u(\bm{f},t)$ we are going to define a map between the set of lamp
configurations contained in $\mathcal{K}_{n}$ and the interval
$[0,|\mathcal{K}_{n}|/D_{n}-1]$.

To do so we will define a numbering based on the same idea as the bloc
decomposition defined in Lemma 3.1. We thus want to define a nested sequence
of intervals $\mathcal{B}_{i}$ depending on the cursor
$u\big{(}P_{n}(\bm{f}^{\prime}),t\big{)}$ —that is to say depending on
$P_{n}(\bm{f}^{\prime})$ and $t$— such that
$\left|\mathcal{B}_{i}\right|\sim\kappa^{i}$, the last interval of the
sequence is $[0,D_{n}-1]$ and $\mathcal{B}_{i}$ verifies Claim 3.8. The idea
would thus be similar to the one used in the definition of
$(\tilde{\mathcal{B}}_{i})$ and presented in Figure 5. However, in this
present case two difficulties arise and lead to a more technical definition.
First the interval $[0,D_{n}-1]$ is bigger than $[0,\kappa^{n}-1]$ so we will
need more than $n+1$ nested intervals and as we will see in eq. 4.10m we will
have to be careful when defining $\mathcal{B}_{i}$ for $i>n$. Second, we will
have to deal with the fact that some of the cursors are not reached by $u$. In
order to first give the idea of the process we thus start by defining the
nested intervals assuming that $R_{n}=0$ (see paragraph below). Then in a
second time (see paragraph “Concrete blocs decomposition”) we detail how to
set these nested intervals in the general case.

##### Ideal blocs decomposition

Let us first assume that $R_{n}=0$ that is to say $D_{n}=Q_{n}\kappa^{n}$.
Then all cursors in $[0,D_{n}-1]$ are reached by $u$. We start by defining

$\forall
i\in[0,n]\quad\mathcal{B}^{\prime}_{i}(P,t):=P\kappa^{n}+\tilde{\mathcal{B}}_{i}(t).$
(4.10k)

That is to say $\mathcal{B}^{\prime}_{i}(P,t)$ corresponds to the nested
sequence of intervals $\tilde{\mathcal{B}}_{i}(t)$ shifted by $P\kappa^{n}$.
In particular
$\mathcal{B}^{\prime}_{n}(P,t)=[P\kappa^{n},\left(P+1\right)\kappa^{n}-1]$. We
now have to define the bigger blocs $\mathcal{B}^{\prime}_{i}$ in order to
cover the entire interval $[0,D_{n}-1]$. Before detailing the definition let
us explain the idea. If $P$ was equal to $Q_{n}-1$ (the biggest possible value
of $P_{n}$) then $\mathcal{B}^{\prime}_{n}(P,t)$ would be the interval
$[(Q_{n}-1)\kappa^{n},Q_{n}\kappa^{n}-1]$. Which can also be written as
$[D_{n}-\kappa^{n},D_{n}-1]$, since $D_{n}=Q_{n}\kappa^{n}$. To obtain the
next terms of the sequence $\mathcal{B}^{\prime}_{i}$ (represented in Figure
10(a)) we could then consider
$\mathcal{B}^{\prime}_{i}(P,t)=[D_{n}-\kappa^{i},D_{n}-1]$ that is to say
$[(P+1)\kappa^{n}-\kappa^{i},D_{n}-1]$. Now if we try to extend this
definition to smaller values of $P$, the left bound of this last interval
might be negative (see illustration in Figure 10(b)). In that case we thus set
the lower bound to $0$ and the upper bound to $\kappa^{i}-1$ (see eq. 4.10m).

Now for the formal definition. Let $p_{n}\in\mathbb{N}$ be such that

$\kappa^{p_{n}-1}<D_{n}\leq\kappa^{p_{n}}$ (4.10l)

let $\mathcal{B}^{\prime}_{p_{n}}(P,t):=[0,D_{n}-1]$ namely
$\mathcal{B}^{\prime}_{p_{n}}(P,t):=[0,Q_{n}\kappa^{n}-1]$ and set for all
$i\in[n+1,p_{n}-1]$

$\mathcal{B}^{\prime}_{i}(P,t)=\begin{cases}\left[\left(P+1\right)\kappa^{n}-\kappa^{i};\left(P+1\right)\kappa^{n}-1\right]&\text{if}\
P+1\geq\kappa^{i-n},\\\ \left[0,\kappa^{i}-1\right]&\text{else}.\end{cases}$
(4.10m)

(a) $P=Q_{n}-1$

(b) $P<Q_{n}-1$

Figure 10: Example of nested intervals for different values of $P$.

######  Lemma 4.12.

The sequence $(\mathcal{B}^{\prime}_{i}(P,t))_{i}$ defined by eqs. 4.10k and
4.10m verifies
$\mathcal{B}^{\prime}_{i}(P,t)\subset\mathcal{B}^{\prime}_{i+1}(P,t)$ for all
$i<p_{n}$. In particular

$\left\\{P\kappa^{n}+t\right\\}=\mathcal{B}^{\prime}_{0}(P,t)\subset\mathcal{B}^{\prime}_{i}(P,t)\subseteq\mathcal{B}^{\prime}_{p_{n}}(P,t)=[0,Q_{n}\kappa^{n}-1],$

###### Proof.

Recall that $\tilde{\mathcal{B}}_{0}(t)=\\{t\\}$. Thus
$\mathcal{B}^{\prime}_{0}(\bm{f},t)=\\{P\kappa^{n}+t\\}$ by eq. 4.10k. Since
we assumed $R_{n}=0$ we get $D_{n}=Q_{n}\kappa^{n}$ and thus
$\mathcal{B}^{\prime}_{p_{n}}(P,t)=[0,Q_{n}\kappa^{n}-1]$. Let us now prove
that $\mathcal{B}^{\prime}_{i}(P,t)\subset\mathcal{B}^{\prime}_{i+1}(P,t)$ for
all $i<p_{n}$.

  * •

If $i<n$ the inclusion comes Lemma 3.1.

  * •

If $i=n$ then $\mathcal{B}^{\prime}_{n}(P,t)=[P\kappa^{n},(P+1)\kappa^{n}-1]$.
If $(P+1)<\kappa$ then in that case
$\mathcal{B}^{\prime}_{n+1}(P,t)=[0,\kappa^{n+1}-1]$. Since $P\kappa^{n}$ is
positive and by the last assumption $(P+1)\kappa^{n}$ is smaller than
$\kappa^{n+1}$ we thus obtain the inclusion.

For the second case, first remark that $\kappa^{n}-\kappa^{n+1}<0$ and thus
$(P+1)\kappa^{n}-\kappa^{n+1}$ is smaller than $P\kappa^{n}$. Hence when
$(P+1)\geq\kappa$ we get

$\displaystyle\mathcal{B}^{\prime}_{n}(P,t)$
$\displaystyle=\left[P_{n}\kappa^{n},\big{(}P+1\big{)}\kappa^{n}-1\right]$
$\displaystyle\subseteq\left[\big{(}P+1\big{)}\kappa^{n}-\kappa^{n+1},\big{(}P+1\big{)}\kappa^{n}-1\right]=\mathcal{B}^{\prime}_{n+1}(P,t).$

  * •

Assume that $i>n$. If $(P+1)\geq\kappa^{i+1-n}$ then $(P+1)\geq\kappa^{i-n}$
and thus

$\displaystyle\mathcal{B}^{\prime}_{i}(P,t)$
$\displaystyle=\left[P\kappa^{n}-\kappa^{i},\big{(}P+1\big{)}\kappa^{n}-1\right]$
$\displaystyle\subseteq\left[\big{(}P+1\big{)}\kappa^{n}-\kappa^{i+1},\big{(}P+1\big{)}\kappa^{n}-1\right]=\mathcal{B}^{\prime}_{i+1}(P,t).$

If $(P+1)<\kappa^{i+1-n}$ then
$\mathcal{B}^{\prime}_{i+1}(P,t)=[0,\kappa^{i+1}-1]$. Then either
$(P+1)<\kappa^{i-n}$ thus $\mathcal{B}^{\prime}_{i}(P,t)=[0,\kappa^{i}-1]$ and
the inclusion comes immediately, or $(P+1)\geq\kappa^{i-n}$. In this case
$(P+1)\kappa^{n}-\kappa^{i}$ is positive, moreover since $(P+1)$ is assumed to
be smaller than $\kappa^{i+1-n}$ we have $(P+1)\kappa^{n}\leq\kappa^{i+1}$.
That is to say

$\displaystyle\mathcal{B}^{\prime}_{i}(P,t)$
$\displaystyle=\left[\big{(}P+1\big{)}\kappa^{n}-\kappa^{i},\big{(}P+1\big{)}\kappa^{n}-1\right]\subseteq\left[0,\kappa^{i+1}-1\right]=\mathcal{B}^{\prime}_{i+1}(P,t).$

∎

##### Concrete blocs decomposition

We turn now to the general case where $R_{n}$ might be greater than zero. We
first define in Lemma 4.13 a surjective map $\chi$ from $[0,D_{n}-1]$ to
$[0,Q_{n}\kappa^{n}-1]$ and then use it to define our blocs
$\mathcal{B}_{i}(P,t)$ in $[0,D_{n}-1]$ as the preimages of the “ideal” blocs
$\mathcal{B}^{\prime}_{i}(P,t)$.

Figure 11 represents the map $\chi$ and Lemma 4.13 formalizes its definition.

Figure 11: Map $\chi$

######  Lemma 4.13.

Consider $v\in[0,D_{n}-1]$.

  * •

If $v=u(P,t)$ for some $(P,t)\in[0,Q_{n}-1]\times[0,\kappa^{n}-1]$ then define
$\chi(v):=P_{n}(\bm{f}^{\prime})\kappa^{n}+t$.

  * •

If $v\notin\mathrm{im}(u)$ then $(v-1)\in\mathrm{im}(u)$ and we define
$\chi(v):=\chi(v-1)$.

Then $\chi:[0,D_{n}-1]\rightarrow[0,Q_{n}\kappa^{n}-1]$ is a well defined
surjective map. Moreover for any interval $I\subseteq[0,Q_{n}\kappa^{n}-1]$
the pre-image $\chi^{-1}(I)$ is also an interval and it verifies
$|\chi^{-1}(I)|\leq 2|I|$.

###### Proof.

If $v\in\mathrm{im}(u)$ there exists a unique
$(P,t)\in[0,Q_{n}-1]\times[0,\kappa^{n}-1]$ such that $u(P,t)=v$.Moreover,
since $P$ belongs to $[0,Q_{n}-1]$ and $t$ to $[0,\kappa^{n}-1]$ then
$P\kappa^{n}+t$ belongs to $[0,Q_{n}\kappa^{n}-1]$. Hence $\chi$ is well
defined. It is also surjective. Finally consider $y\in[0,Q_{n}\kappa^{n}-1]$
then $\chi^{-1}(y)$ contains either $1$ or $2$ consecutive elements in
$[0,D_{n}-1]$. Thus $|\chi^{-1}(I)|\leq 2|I|$ and $\chi^{-1}(I)$ is an
interval, since $\chi$ preserves the order. ∎

We now define $\mathcal{B}_{i}(P,t)$ as the pre-image of the ideal bloc
$\mathcal{B}^{\prime}_{i}(P,t)$. The following lemma comes immediately from
Lemmas 4.12 and 4.13.

######  Lemma 4.14.

Let $(P,t)\in[0,Q_{n}-1]\times[0,\kappa^{n}-1]$ and consider the sequence
$(\mathcal{B}^{\prime}_{i}(P,t))_{i}$ as defined by eqs. 4.10k and 4.10m. Let

$\forall
i\in[0,p_{n}]\quad\mathcal{B}_{i}(P,t):=\chi^{-1}\left(\mathcal{B}^{\prime}_{i}(P,t)\right).$

The sequence $(\mathcal{B}_{i}(P,t))_{i}$ thus defined verifies
$\mathcal{B}_{i}(P,t)\subset\mathcal{B}_{i+1}(\bm{f},t)$ for all $i<p_{n}$. In
particular

$u(P,t)\in\mathcal{B}_{0}(P,t)\subset\mathcal{B}_{i}(P,t)\subseteq\mathcal{B}_{p_{n}}(P,t)=[0,D_{n}-1],$

and thus $u(P,t)$ belongs to $\mathcal{B}_{i}(P,t)$ for all $i\leq p_{n}$.

######  Remark 4.15.

Lemma 4.13 implies that $\kappa^{i}\leq|\mathcal{B}_{i}(P,t)|\leq 2\kappa^{i}$
for all $i$.

##### Numbering

Let us now define our numbering. The strategy is quite similar to the one used
in Section 4.1.2 Section 3.1.2, except that here the variable base used to
associate a number to a lamp configuration depends on the value of the cursor
$u\big{(}P_{n}(\bm{f}^{\prime}),t\big{)}=v$.

Now consider $(\bm{g},v)$ such that $v$ belongs to the image of $u$ and let
$P\in[0,Q_{n}-1]$ and $t\in[0,\kappa^{n}]$ such that $u(P,t)=v$. Remark that
for all $i\in[1,p_{n}+1]$, the number of maps of the form
$\zeta:\mathbb{Z}\rightarrow A\times B$ supported on
$\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{i-1}(P,t)$ is equal to
$q^{|\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{i-1}(P,t)|}$. Hence we can
define applications

$\displaystyle\nu_{0,P,t}\,$
$\displaystyle:\,\left\\{\zeta:\,\mathcal{B}_{0}(P,t)\rightarrow A\times
B\right\\}\rightarrow\left[0,q-1\right],$ $\displaystyle\forall
i\in[1,p_{n}]\quad\nu_{i,P,t}\,$
$\displaystyle:\,\left\\{\zeta:\,\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{i-1}(P,t)\rightarrow
A\times
B\right\\}\rightarrow\left[0,q^{\left|\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{i-1}(P,t)\right|}-1\right],$

such that these maps are bijections. Please note that the above maps depend on
the value of $P$ and $t$, if we do not need to keep track of the values of $P$
and $t$ we will denote $\nu_{i}$ instead $\nu_{i,P,t}$ to simplify the
notations.

We now have to number $(g^{\prime}_{m})_{m\in[1,\mathfrak{l}(D_{n}-1)]}$. Let
us first make a general remark on $F_{D_{n},I_{n},J_{n}}$. We refer to Figure
12 for an illustration. Recall that $\mathfrak{l}(D_{n}-1)$ is defined as
$\mathfrak{l}(D_{n}-1)=\max\\{m\ :\ k_{m}\leq D_{n}-1\\}$. In particular (see
Figure 12(a)) if $k_{\mathfrak{l}(D_{n}-1)}=D_{n}-1$ and $(\bm{g},t)$ belongs
to $F_{D_{n}}$ then $g^{\prime}_{\mathfrak{l}(D_{n}-1)}$ is supported on
$\\{k_{\mathfrak{l}(D_{n}-1)}\\}$. Therefore if $I_{n}<\mathfrak{l}(D_{n}-1)$,
an element $(\bm{g},t)$ of $F_{D_{n},I_{n},J_{n}}$ verifies
$g^{\prime}_{\mathfrak{l}(D_{n}-1)}\equiv e$. Thus $\bm{g}$ is only determined
by $g_{0}$ and $(g^{\prime}_{m})_{m\leq\mathfrak{l}(D_{n}-1)-1}$. We thus
define

$M_{n}:=\begin{cases}\mathfrak{l}(D_{n}-1)-1&\text{if}\
k_{\mathfrak{l}(D_{n}-1)}=D_{n}-1\ \text{and}\ I_{n}<\mathfrak{l}(D_{n}-1),\\\
\mathfrak{l}(D_{n}-1)&\text{else}.\end{cases}$ (4.10n)

(a) $F_{D_{n}}$ for $k_{\mathfrak{l}(D_{n}-1)}=D_{n}-1$

(b) $F_{D_{n},I_{n},J_{n}}$ for $I_{n}<\mathfrak{l}(D_{n}-1)$

Figure 12: Comparison of $F_{D_{n}}$ and $F_{D_{n},I_{n},J_{n}}$ when
$k_{\mathfrak{l}(D_{n}-1)}=D_{n}-1$

We thus are actually going to number $(g^{\prime}_{m})_{m\leq M_{n}}$. But we
will need a more refined numbering than the one defined in Section 4.1.2.

Why refine the numbering? Consider $(\bm{f},t)$ in $\mathcal{G}_{n}$ and
denote $(\bm{g},u):=\iota_{n}(\bm{f},t)$. While the action of a generator $s$
on $(\bm{f},t)$ only changes the value of $f_{0}(t)$ or of the cursor, we will
see in Section 4.3.1 that it can modify numerous digits of
$\tilde{\vartheta}_{n}(\bm{f},t)$. Hence it can modify the image $(\bm{g},u)$
by the values of $\bm{g}^{\prime}$ and not just $g_{0}$. When it happens, if
we encode the information of $\bm{g}^{\prime}$ in one digit as in Section
4.1.2 then the best bound we can obtain on the distance between
$(\bm{g},u)=\iota_{n}(\bm{f},t)$ and $\iota_{n}\big{(}(\bm{f},t)s\big{)}$ will
be $\mathrm{diam}\left({\mathcal{H}_{n}}\right)$. Furthemore we can show that
the _proportion_ of such elements is about $q^{-D_{n}}$. Hence when checking
the condition given by eq. 2.1 we will obtain an unbounded sum since
$\mathrm{diam}\left({\mathcal{K}_{n}}\right)$ is much bigger than $q^{D_{n}}$.
To overcome this, we refine the numbering such that the more terms we modify
in $\bm{g}^{\prime}$ (and thus the more the distance grows), the more the
proportion of such elements decreases.

By a similar proof as the one of Claim 3.4 we can show that for all
$m\in[1,I_{n}-1]$, there exists a bijection

$\mu_{m}:\,\left\\{h^{\prime}_{m}:\,\mathbb{Z}\rightarrow{\Gamma}^{\prime}_{m}\,|\,\mathrm{supp}(h^{\prime}_{m})\subseteq[k_{m},D_{n}-1]\right\\}\rightarrow\left[0,|{\Gamma}^{\prime}_{m}|^{D_{n}-k_{m}}-1\right].$

Similarly for the $I_{n}-th$ element we have a bijection

$\mu_{I_{n}}:\,\left\\{h^{\prime}_{m}:\,\mathbb{Z}\rightarrow{\Gamma}^{\prime}_{m}\,\left|\,\begin{matrix}\mathrm{supp}(h^{\prime}_{I_{n}})\subseteq[k_{I_{n}},D_{n}-1]\\\
\text{and}\
h^{\prime}_{I_{n}}(D_{n}-1)\in\Lambda^{I_{n}}_{J_{n}}\end{matrix}\right.\right\\}\rightarrow\left[0,|{\Gamma}^{\prime}_{m}|^{D_{n}-k_{I_{n}}-1}\left|{\Lambda^{I_{n}}_{J_{n}}}\right|-1\right].$

Finally for all $m\in[I_{n}+1,M_{n}]$, there exists a bijection

$\mu_{m}:\,\left\\{h^{\prime}_{m}:\,\mathbb{Z}\rightarrow{\Gamma}^{\prime}_{m}\,|\,\mathrm{supp}(h^{\prime}_{m})\subseteq[k_{m},D_{n}-2]\right\\}\rightarrow\left[0,|{\Gamma}^{\prime}_{m}|^{D_{n}-k_{m}-1}-1\right].$

We represent in Figure 13 the numbering defined so far.

Figure 13: Numbering in $\Delta$

Let us now define the variable base $(b_{i,P,t})_{i}$. We reproduce the idea
used in the definition of $(\tilde{b}_{i})_{i}$ with two changes: first
$|\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{i-1}(P,t)|$ depends on $P$ and
$t$ so we cannot replace it by its numerical value as we did for
$\tilde{b}_{i}$, second the numbering of $\bm{f}^{\prime}$ contains here more
than one term.

$\displaystyle b_{0,P,t}=b_{0}:=q$ $\displaystyle\forall i\in[1,p_{n}]\quad$
$\displaystyle
b_{i,P,t}=q^{|\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{i-1}(\bm{f},t)|}$
$\displaystyle\forall m\in[1,I_{n}-1]\quad$ $\displaystyle
b_{p_{n}+m,P,t}=b_{p_{n}+m}=|{\Gamma}^{\prime}_{m}|^{D_{n}-k_{m}}$
$\displaystyle
b_{p_{n}+I_{n},P,t}=b_{p_{n}+I_{n}}=|{\Gamma}^{\prime}_{m}|^{D_{n}-1-k_{m}}|\Lambda^{I_{n}}_{J_{n}}|$
$\displaystyle\forall m\in\left[I_{n}+1,M_{n}\right]\quad$ $\displaystyle
b_{p_{n}+m,P,t}=b_{p_{n}+m}=|{\Gamma}^{\prime}_{m}|^{D_{n}-1-k_{m}}$

Remark that $\prod^{p_{n}}_{i=0}b_{i,P,t}=q^{D_{n}}$ and thus this product
does not depend on $(P,t)$. Before defining our map $\vartheta_{n}$ let us
show some useful result about the base we just introduced.

######  Lemma 4.16.

For all $P\in\mathrm{im}(P_{n})$ and all $t\in[0,\kappa^{n}-1]$ let
$(b_{i,P,t})_{i}$ be the base defined above.

  * •

For all $i<p_{n}$ it verifies $b_{i,P,t}\cdots
b_{0,P,t}\in[q^{\kappa^{i}},q^{2\kappa^{i}}]$. Moreover for all $j\in[1,i-1]$

$q^{\kappa^{i}-2\kappa^{j-1}}\leq\prod^{i}_{k=j}b_{k,P,t}\leq
q^{2\kappa^{i}-\kappa^{j-1}}.$

  * •

If $i=p_{n}$ then $b_{i,P,t}\cdots b_{0,P,t}=q^{D_{n}}$ and for all
$j\in[1,i-1]$ we have $b_{i,P,t}\cdots b_{j,P,t}\geq q^{D_{n}-2\kappa^{j}}$.

  * •

For all $i>p_{n}$ we have $b_{i,P,t}\cdots b_{0,P,t}\geq
q^{D_{n}}\exp(l_{i-p_{n}})$ and for all $j\in[1,i-1]$ we have $b_{i,P,t}\cdots
b_{j,P,t}\geq q^{D_{n}-2\kappa^{j}}\exp(l_{i-p_{n}})$.

###### Proof.

First consider $i<p_{n}$. By Lemma 4.13 $\mathcal{B}_{i}(P,t)$ contains at
most $2|\mathcal{B}^{\prime}_{i}(P,t)|$ elements and at least
$|\mathcal{B}^{\prime}_{i}(P,t)|$ elements. But
$|\mathcal{B}^{\prime}_{i}(P,t)|=\kappa^{i}$, the first assertion of the lemma
thus comes by noting that $b_{i,P,t}\cdots b_{0,P,t}$ is equal to
$q^{|\mathcal{B}_{i}(P,t)|}$. For the second assertion, remark that
$b_{i,P,t}\cdots b_{j,P,t}$ equals
$q^{|\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{j-1}(P,t)|}$. Moreover by
Lemma 4.14 the interval $\mathcal{B}_{j-1}(P,t)$ is included in
$\mathcal{B}_{i}(P,t)$ thus
$|\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{j-1}(P,t)|$ is equal to
$|\mathcal{B}_{i}(P,t)|-|\mathcal{B}_{j-1}(P,t)|$. Hence the first point.

If $i=p_{n}$ then $|\mathcal{B}_{i}(P,t)|=D_{n}$ and a similar argument as
above implies that $b_{i,P,t}\cdots b_{0,P,t}$ equals $q^{D_{n}}$ and
$b_{i,P,t}\cdots b_{j,P,t}\geq q^{D_{n}-2\kappa^{j}}$ for all $j\in[1,i-1]$.

Finally if $i>p_{n}$ note that $b_{i,P,t}\cdots b_{j,P,t}$ is greater than
$b_{i,P,t}b_{p_{n},P,t}\cdots b_{0,P,t}$. But note that by eq. 4.10n, for all
$m\leq M_{n}$ we have $k_{m}<D_{n}-1$. Therefore for all $p_{n}<i\leq
p_{n}+M_{n}$

$b_{i,P,t}\geq|{\Gamma}^{\prime}_{i-p_{n}}|^{D_{n}-1-k_{i-p_{n}}}\geq|{\Gamma}^{\prime}_{i-p_{n}}|\sim\exp(l_{i-p_{n}}).$

Hence $b_{i,P,t}b_{p_{n},P,t}\cdots b_{0,P,t}$ is greater than
$\exp(l_{i-p_{n}})q^{D_{n}}$. The last assertion is similarly obtained by
bounding $b_{p_{n},P,t}\cdots b_{i,P,t}$ by below by $q^{D_{n}-2\kappa^{i}}$.
∎

In the base $\big{(}b_{i,P,t}\big{)}_{i=0,\ldots,p_{n}+M_{n}}$ we thus write

$\begin{split}{\vartheta}_{n}(\bm{g},u(P,t)):=&\nu_{0}\left(g_{0|\mathcal{B}_{0}(P,t)}\right)+\sum^{p_{n}-1}_{i=1}\nu_{i}\left(g_{0|\mathcal{B}_{i}(P,t)\backslash\mathcal{B}_{i-1}(P,t)}\right)b_{i-1,\bm{f},t}\cdots
b_{0,P,t}\\\
&+\sum^{M_{n}}_{m=1}\mu_{m}\left(g^{\prime}_{m}\right)b_{m+p_{n},P,t}\cdots
b_{0,P,t}.\end{split}$ (4.10o)

######  Lemma 4.17.

Let $\vartheta_{n}$ as defined in eq. 4.10o. For all $v\in\mathrm{im}(u)$ the
map ${\vartheta}_{n}(\cdot,v)$ is injective and its image is exactly the
interval $[0,\max(\vartheta_{n})]$.

###### Proof.

Assume that there exist $\bm{g},\bm{h}$ such that
${\vartheta}_{n}(\bm{g},v)={\vartheta}_{n}(\bm{h},v)$ and let $P$ and $t$ such
that $v=u(P,t)$. Then ${\vartheta}_{n}(\bm{g},v)$ and
${\vartheta}_{n}(\bm{h},v)$ share the same decomposition in base $(b_{i,P,t})$
that is to say $\mu_{m}(g^{\prime}_{m})=\mu_{n}(h^{\prime}_{m})$ for all $m$,
and $\nu_{0}(g_{0|\mathcal{B}_{0}(P,t)})=\nu(h_{0|\mathcal{B}_{0}(P,t)})$ and
similarly for the $\nu_{i}$’s. Since all the $\mu_{m}$ and $\nu_{i}$’s are
bijections we thus get that $g_{0}=h_{0}$ and
$\bm{g}^{\prime}=\bm{h}^{\prime}$. Hence $\bm{g}=\bm{h}$. The second part
comes from Lemma B.1 applied to the base $(b_{i,P,t})_{i}$. ∎

####  4.2.3 Injection

So far we can define a map that sends an element $(\bm{f},t)$ in
$\tilde{\Delta}$ to $(\tilde{\vartheta}_{n}(\bm{f},t),u(\bm{f},t))$ in
$\mathbb{Z}^{2}$. For $v\in\mathrm{im}(u)$ we can also consider the map that
sends $(\bm{g},v)\in\Delta$ to $(\vartheta_{n}(\bm{g},v),v)\in\mathbb{Z}^{2}$.
A first idea to define our injection
$\iota_{n}:\mathcal{G}_{n}\rightarrow\mathcal{K}_{n}$ would be to compose the
first map with the inverse of the second (see also Figure 7). But doing so
would lead to a non-$C$-dense injection. Indeed, the image of
$\tilde{\vartheta}_{n}$ is strictly included in the one of $\vartheta_{n}$ and
more precisely the elements in $\mathrm{im}(\vartheta_{n})$ that are not
reached by $\tilde{\vartheta}_{n}$ are the greatest values.That is to say some
values of $\mu_{n}$ might not be reached. Hence translating
$\tilde{\vartheta}_{n}$ into a sequence of lamp configurations $\bm{g}$ in
$\Delta$ might not give us all the possible values for $\bm{g}^{\prime}$. But
if such a $(\bm{g},w)\in\mathcal{K}_{n}$ is not reached then it might differ
from the nearest element in $\mathrm{im}(\iota_{n})$ by a value of
$g^{\prime}_{M_{n}}$. Such an element will be far away from the reached one,
since changing a lamp of $g^{\prime}_{M_{n}}$ requires a lot of
multiplications by generators.

In order to obtain the density we thus need to spread the unreached values
across the interval $\mathrm{im}(\vartheta_{n})$. This is the aim of the next
paragraph.

##### Spreading

Let us discuss the idea the definition. Since our goal is to spread the values
of $\\{0,\ldots,\max(\tilde{\vartheta}_{n})\\}$ accross the intervall
$[0,\max(\vartheta_{n})]$, the ideal map to consider would be the one sending
$x$ to $\max(\vartheta_{n}))/\max(\tilde{\vartheta}_{n})x$ (represented in
Figure 14(a)). But we also want the values taken by this spreading map to be
_integers._ Since the quotient
$\max(\vartheta_{n}))/\max(\tilde{\vartheta}_{n})$ is not necessarily an
integer, the aforementioned values do not necessarily belong to $\mathbb{N}$.
This is why we define
$\mathfrak{a}_{n}:=\left\lceil{\max(\vartheta_{n})/\max(\tilde{\vartheta}_{n})}\right\rceil$
and consider instead a piecewise affine map that approaches the above linear
one and gives integers values (see Figure 14(b)).

######  Lemma 4.18.

Let $n\in\mathbb{N}$. There exists a piecewise affine map $\mathfrak{s}_{n}$:
$[0,\max\tilde{\vartheta}_{n}]\rightarrow[0,\max\vartheta_{n}]$ which is
$(q^{3})$-Lipschitz and verifies

  * •

$\mathfrak{s}_{n}(x)\in\mathbb{N}$, for all
$x\in\\{0,\ldots,\max\tilde{\vartheta}_{n}\\}$;

  * •

$\mathfrak{s}_{n}(\max\tilde{\vartheta}_{n})=\max\vartheta_{n}$.

The map we are going to construct is the one described in Figure 14(b).

(a) Linear map for $\max(\vartheta_{n}))/\max(\tilde{\vartheta}_{n})=1.5$

(b) Affine approximation with $\mathfrak{a}=2$

Figure 14: Affine approximation

Before showing the above lemma let us bound the value of $\mathfrak{a}_{n}$.

######  Claim 4.19.

Let $n\in\mathbb{N}$ and
$\mathfrak{a}_{n}:=\left\lceil{\max(\vartheta_{n})/\max(\tilde{\vartheta}_{n})}\right\rceil$.
Then $1\leq\mathfrak{a}_{n}\leq q^{3}$.

###### Proof of the claim.

Using eq. 4.10o which gives the definition of $\vartheta_{n}$ and Lemma B.1 we
obtain $\max(\vartheta_{n})=|\mathcal{K}_{n}|/D_{n}-1$. Since
$|\mathcal{K}_{n}|$ is equal to $|F_{d_{n},i_{n},j_{n}-1}|$, the lower bound
of the claim comes immediately from Lemma 4.8. Moreover by Lemma 4.8

$\max_{(\bm{f},t)\in\mathcal{G}_{n}}\tilde{\vartheta}_{n}(\bm{f},t)\geq\left|{F_{d_{n},i_{n},j_{n}-1}}\right|/D_{n}-1.$

Hence using these two observations, then bounding very roughly
$|{F_{d_{n},i_{n},j_{n}-1}}|-D_{n}$ by below by
$|{F_{d_{n},i_{n},j_{n}-1}}|/2$ and finally using Lemma 2.7, we get

$\displaystyle\frac{\max(\vartheta_{n})}{\max(\tilde{\vartheta}_{n})}\leq\frac{|\mathcal{K}_{n}|}{D_{n}}\frac{D_{n}}{\left|{F_{d_{n},i_{n},j_{n}-1}}\right|-D_{n}}$
$\displaystyle=\frac{\left|{F_{d_{n},i_{n},j_{n}+1}}\right|}{\left|{F_{d_{n},i_{n},j_{n}-1}}\right|-D_{n}},$
$\displaystyle\leq
2{\left|{F_{d_{n},i_{n},j_{n}+1}}\right|}/{\left|{F_{d_{n},i_{n},j_{n}-1}}\right|},$
$\displaystyle\leq 2\times(2q)^{2}.$

Hence $\mathfrak{a}_{n}\leq 4q^{2}+1\leq q^{3}$. ∎

###### Proof of Lemma 4.18.

First let
$\mathfrak{b}_{n}:=\max(\vartheta_{n})-\mathfrak{a}_{n}\max\tilde{\vartheta}_{n}$
and remark that it belongs to $\mathbb{N}$. Now let

$\mathfrak{s}_{n}:x\mapsto\begin{cases}(\mathfrak{a}_{n}-1)x&\text{if}\
x<-\mathfrak{b},\\\ \mathfrak{a}_{n}x+\mathfrak{b}_{n}&\text{if}\
x\geq-\mathfrak{b}.\end{cases}$

By definition $\mathfrak{s}_{n}$ is $\mathfrak{a}_{n}$-Lipschitz and hence by
Claim 4.19 it is $(q^{3})$-Lipschitz. Moreover, since
$\mathfrak{b}_{n},\mathfrak{a}_{n}$ and $(\mathfrak{a}_{n}-1)$ are integers
then $\mathfrak{s}_{n}$ maps any integer to an integer. Finally we can check
easily that $\mathfrak{s}_{n}(\max\tilde{\vartheta}_{n})=\max\vartheta_{n}$. ∎

We can now define the “spreading” version of $\tilde{\vartheta}_{n}$

$\hat{\vartheta}_{n}(\bm{f},t):=\mathfrak{s}_{n}\circ\tilde{\vartheta}_{n}(\bm{f},t).$
(4.10p)

##### Injectivity and density

Let us now define the Sofic approximation we want to work with in $\Delta$. We
saw in Lemma 4.7 that the image of the map sending $(\bm{f},t)$ to
$\big{(}t,\tilde{\vartheta}_{n}(\bm{f},t),P_{n}(f^{\prime})\big{)}$ was not
necessarily the product
$[0,\kappa^{n}-1]\times[0,\max\tilde{\vartheta}_{n}]\times[0,Q_{n}-1]$. It
might indeed be smaller. The unreached part of this last product might lead to
a large area of unreached elements in $\mathcal{K}_{n}$, preventing the
injection from $\mathcal{G}_{n}$ to $\mathcal{K}_{n}$ to be $C$-dense. We
consequently define a new sofic approximation $\mathcal{H}_{n}$ included in
$\mathcal{K}_{n}$ but not containing the aforementioned unreached elements.

$\mathcal{H}_{n}:=\mathcal{K}_{n}\backslash\left\\{(\bm{g},v)\in\mathcal{K}_{n}\
\left|\begin{matrix}\vartheta_{n}(\bm{g})&\geq\mathfrak{s}_{n}\left(q^{\kappa^{n}}\max(E_{n})\right)\\\
\chi(v)&\geq\kappa^{n}\left[\max\left(\tilde{\mu}_{n}\right)-Q_{n}\max\left(E_{n}\right)+1\right]\end{matrix}\right.\right\\}$
(4.10q)

######  Lemma 4.20.

The set $\mathcal{H}_{n}$ defined in eq. 4.10q is a Følner set of $\Delta$.

###### Proof.

Using that $\mathfrak{s}_{n}$ is $(q^{3})$-Lipschitz and that
$\max(\tilde{\vartheta}_{n})\leq q^{\kappa^{n}}\max(E_{n})+q^{\kappa^{n}}-1$
we get

$\left|\left[\mathfrak{s}_{n}\left(q^{\kappa^{n}}\max(E_{n}),\max(\tilde{\vartheta}_{n})\right)\right]\right|\
\leq\
q^{3}\left|\left[q^{\kappa^{n}}\max(E_{n}),\max\left(\tilde{\vartheta}_{n}\right)\right]\right|\
\leq\ q^{3}q^{\kappa^{n}}.$

Hence

$\displaystyle\left|\left\\{(\bm{g},v)\in\mathcal{K}_{n}\
\left|\begin{matrix}\vartheta_{n}(\bm{g})&\geq\mathfrak{s}_{n}\left(q^{\kappa^{n}}\max(E_{n})\right)\\\
\chi(v)&\geq\kappa^{n}\left[\max\left(\tilde{\mu}_{n}\right)-Q_{n}\max\left(E_{n}\right)+1\right]\end{matrix}\right.\right\\}\right|$
$\displaystyle\leq$
$\displaystyle\left|[0,D_{n}-1]\right|\cdot\left|\left[\mathfrak{s}_{n}\left(q^{\kappa^{n}}\max(E_{n}),\max(\tilde{\vartheta}_{n})\right)\right]\right|$
$\displaystyle\leq$ $\displaystyle D_{n}q^{3+\kappa^{n}}.$

Recall (see eq. 4.9) that $\mathcal{K}_{n}=F_{D_{n},I_{n},J_{n}}$. Using the
value of $|\mathcal{K}_{n}|$ given by Lemma 2.7, we get that
$D_{n}q^{3+\kappa^{n}}/|\mathcal{K}_{n}|$ tends to zero, thus
$\mathcal{K}_{n}$ minus some set of at most $D_{n}q^{3+\kappa^{n}}$ elements
is still a Følner sequence. ∎

Let us now define the $C$-dense injection.

######  Lemma 4.21.

Let $\iota_{n}\ :\ \mathcal{G}_{n}\rightarrow\mathcal{H}_{n}$ be the map such
that $\iota_{n}(\bm{f},t):=(\bm{g},u(P_{n}(\bm{f}\prime),t))$ where $u$ is
defined in eq. 4.10 and $\bm{g}$ verifies
$\hat{\vartheta}_{n}(\bm{f},t)=\vartheta_{n}\left(\bm{g},u\big{(}P_{n}(\bm{f}\prime),t\big{)}\right)$.
Then there exists a constant $C>0$ such that $\iota_{n}$ is injective and
$C$-dense for $n$ large enough.

###### Proof.

Let us first show that $\iota_{n}$ is well defined, that is to say: for all
$(\bm{f},t)\in\mathcal{G}_{n}$ there exists a unique $\bm{g}$ such that
$\big{(}\bm{g},u(P_{n}(\bm{f}\prime),t)\big{)}$ belongs to $\mathcal{H}_{n}$
and verifies
$\hat{\vartheta}_{n}(\bm{f},t)=\vartheta_{n}\left(\bm{g},u\big{(}P_{n}(\bm{f}\prime),t\big{)}\right)$.
Recall that $\hat{\vartheta}_{n}=\mathfrak{s}_{n}\circ\tilde{\vartheta}_{n}$
and that $\chi$ is defined in Lemma 4.13.

  * •

Let $(\bm{f},t)\in\mathcal{G}_{n}$. By Lemmas 4.17 and 4.18
$\hat{\vartheta}_{n}(\bm{f},t)$ belongs to $[0,\max\vartheta_{n}]$. Thus there
exists $\bm{g}$ such that $\big{(}g,u(P_{n}(\bm{f}\prime),t)\big{)}$ belongs
to $\mathcal{K}_{n}$ and
$\hat{\vartheta}_{n}(\bm{f},t)=\vartheta_{n}\left(\bm{g},u\big{(}P_{n}(\bm{f}\prime),t\big{)}\right)$.

  * •

By choice of $\bm{g}$, if
$\hat{\vartheta}_{n}(\bm{f},t)<\mathfrak{s}_{n}\left(q^{\kappa^{n}}\max(E_{n})\right)$
then $\vartheta_{n}(\bm{g},u\big{(}P_{n}(\bm{f}\prime),t\big{)})$ is also
strictly smaller than $\mathfrak{s}_{n}\left(q^{\kappa^{n}}\max(E_{n})\right)$
and thus $(\bm{g},u\big{(}P_{n}(\bm{f}\prime),t\big{)})$ belongs to
$\mathcal{H}_{n}$.

  * •

Recall that $\mathfrak{s}_{n}$ is increasing, thus
$\tilde{\vartheta}_{n}(\bm{f},t)$ is greater than $q^{\kappa^{n}}\max(E_{n})$
if and only if $\hat{\vartheta}_{n}(\bm{f},t)$ is greater than
$\mathfrak{s}_{n}\left(q^{\kappa^{n}}\max(E_{n})\right)$. Therefore if
$\hat{\vartheta}_{n}(\bm{f},t)\geq\mathfrak{s}_{n}\left(q^{\kappa^{n}}\max(E_{n})\right)$
then Lemma 4.7 implies that $P_{n}(\bm{f}\prime)$ equals at most
$\max(\tilde{\mu}_{n})-Q_{n}\max(E_{n})$ and thus

$\chi\left(u\left(P_{n}(\bm{f}\prime),t\right)\right)\leq\kappa^{n}\left(\max(\tilde{\mu}_{n})-Q_{n}\max(E_{n})+1\right)-1.$

Hence $(\bm{g},u\left(P_{n}(\bm{f}\prime),t\right))$ belongs to
$\mathcal{H}_{n}$ by eq. 4.10q.

  * •

Finally if there exists $\bm{g}$ such that
$\hat{\vartheta}_{n}(\bm{f},t)=\vartheta_{n}\left(\bm{g},u\big{(}P_{n}(\bm{f}\prime),t\big{)}\right)$
then it is unique since $\vartheta_{n}(\cdot,v)$ is injective for any $v$ in
the image of $u$ (see Lemma 4.17).

Let us now prove the injectivity of $\iota_{n}$. Let
$(\bm{f},t),(\bm{h},v)\in\mathcal{G}_{n}$ such that
$\iota_{n}(\bm{f},t)=\iota_{n}(\bm{h},v)$. Then $u(\bm{f},t)=u(\bm{h},v)$ and
if we denote $\bm{g}$ the element such that
$(\bm{g},u(\bm{f},t))=\iota_{n}(\bm{f},t)$ we thus get
$\hat{\vartheta}(\bm{f},t)=\vartheta_{n}(\bm{g},u(\bm{f},t))=\hat{\vartheta}(\bm{h},v)$.

  * •

If $u(\bm{f},t)=u(\bm{f},v)$ then $\chi\circ u(\bm{f},t)=\chi\circ
u(\bm{f},v)$ and thus

$\left(P_{n}(\bm{f}^{\prime})-P_{n}(\bm{h}^{\prime})\right)\kappa^{n}=v-t.$

But $0\leq t,v<\kappa^{n}$, the above equation thus leads to $t=v$ and
$P_{n}(\bm{f}^{\prime})=P_{n}(\bm{h}\prime)$.

  * •

Let us now prove that $\bm{f}^{\prime}=\bm{h}^{\prime}$. Since
$\mathfrak{s}_{n}$ is a piecewise affine map then
$\hat{\vartheta}(\bm{f},t)=\hat{\vartheta}(\bm{h},v)$ implies that
$\tilde{\vartheta}_{n}(\bm{f},t)=\tilde{\vartheta}_{n}(\bm{h},v)$. In
particular the coefficients of the decomposition of
$\tilde{\vartheta}_{n}(\bm{h},v)$ in base $\big{(}\tilde{b}_{i}\big{)}_{i}$
are equal to the one of the decomposition of
$\tilde{\vartheta}_{n}(\bm{f},t)$. In other words

$\tilde{\nu}_{t,i}(\bm{f},t)=\tilde{\nu}_{v,i}(\bm{h},v)\quad\text{and}\quad
E_{n}(\bm{f}\prime)=E_{n}(\bm{h}\prime).$ (4.10r)

But by the last claim $P_{n}(\bm{f}^{\prime})=P_{n}(\bm{h}\prime)$ thus
$\tilde{\mu}_{n}(\bm{f}\prime)=\tilde{\mu}_{n}(\bm{h}\prime)$. Since
$\tilde{\mu}_{n}$ is bijective it implies that
$\bm{f}^{\prime}=\bm{h}^{\prime}$.

  * •

Moreover the fact that $t$ equals $v$ implies that for all $i\in[0,n]$

$\tilde{\mathcal{B}}_{i}(t)=\tilde{\mathcal{B}}_{i}(v),$

In particular $\tilde{\nu}_{t,i}$ is defined on the same set as
$\tilde{\nu}_{v,i}$. Combining this with the bijectivity of these maps and eq.
4.10r we thus get that $f_{0}=h_{0}$.

Since $\bm{f}$ (resp. $\bm{h}$) is uniquely determined by $f_{0}$ (resp.
$h_{0}$) and $\bm{f}^{\prime}$ (resp. $\bm{h}^{\prime}$) we thus have
$\bm{f}=\bm{h}$. Hence the injectivity of $\iota_{n}$.

Now let us show the density. Let $(\bm{h},v)\in\mathcal{H}_{n}$. We need to
distinguish two cases depending on whether $v$ belongs to $\mathrm{im}(u)$ or
not.

  * •

Since $v\in[0,D_{n}-1]$ there exists $P\in[0,Q_{n}-1]$ and
$t\in[0,\kappa^{n}-1]$ such that $\chi(v)=P\kappa^{n}+t$.

  * •

If $v\in\mathrm{im}(u)$ (resp. $v\notin\mathrm{im}(u)$) denote by
$[y_{0},\ldots,y_{p_{n}+M_{n}}]_{{\bm{b}}}$ the decomposition in base
$({b}_{i,P,t})_{i}$ of $\vartheta_{n}(\bm{h},v)$ (resp.
$\vartheta_{n}(\bm{h},v+1)$). Now by Lemma 4.5 if $n$ is large enough,
$D_{n}>\kappa^{3}$, hence $b_{0,P,t}$, $b_{1,P,t}$ and $b_{2,P,t}$ are well
defined. Moreover $q=6$ (see Section A.1.2) and $\kappa\geq 3$, hence for all
such $n$ we always have

$b_{0,P,t}b_{1,P,t}b_{2,P,t}=q^{\kappa^{2}}\geq q^{9}>q^{3}.$

So up to consider $(\mathcal{G}_{n_{1}+n})_{n\in\mathbb{N}}$ instead of
$(\mathcal{G}_{n})_{n}$ for some $n_{1}\geq 0$, we can assume that the above
inequality is true for all $n$. Now, since $\mathfrak{s}_{n}$ is
$q^{3}$-Lipschitz, Lemma B.5 implies that there exists
$x\in\mathrm{im}(\hat{\vartheta}_{n})$ such that $x_{j}=y_{j}$ for all $j>2$