Amandine Escalier

SOfIc APPrOXIMATIONS AND OPTIMAL qUANTITATIVE OrBIT EqUIVALENcE

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 INTrODUcTION 2 1.1 Quantitative measure equivalence . . . . . . . . . . . . . .

1 Introduction to proceed is to quantify how close the two actions are by studying the integrability of the associated cocycles.

Indeed, assume that G and H are two measure equivalent groups over a probability space (X, μ) and denote by X G (resp. X H ) the fundamental domains associated to the actions. The corresponding cocycles α ∶ G × X H → H and β ∶ H × X G → G are defined by α(g, x) = h ⇔ h ⋅ (g ⋅ x) ∈ X H β(h, x) = g ⇔ g ⋅ (h ⋅ x) ∈ X G .

(1.1) When x ↦ α(g, x) and x ↦ β(h, x) are L p for all g ∈ G and h ∈ H, we say that the groups are L p -measure equivalent. This refinement allowed for example Bader, Furman and Sauer [START_REF] Bader | Integrable measure equivalence and rigidity of hyperbolic lattices[END_REF] 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 ≥ 2 is virtually a lattice in SO(n, 1). It also lead Bowen to prove in the appendix of [START_REF] Austin | Integrable measure equivalence for groups of polynomial growth[END_REF] that volume growth was invariant under L 1 -orbit equivalence. Delabie, Koivisto, Le Maître and Tessera offered in [START_REF] Delabie | Quantitative measure equivalence[END_REF] to extend this quantification to a family of functions larger than {x ↦ x p , p ∈ [0, +∞]} (see Definition 1.5). In [START_REF] Delabie | Quantitative measure equivalence[END_REF][START_REF] Carderi | Measure equivalence and sofic approximations[END_REF] 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 φ and a group G, find a group that is measure equivalent to G with this prescribed integrability φ. 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 [START_REF] Brieussel | Speed of random walks, isoperimetry and compression of finitely generated groups[END_REF] of groups with prescribed isoperimetric profile called diagonal products. Using these tools we first exhibit a group that is orbit equivalent to ℤ with a prescribed quantification (see Theorem 1.16). In a second time we construct a measure equivalence coupling between two diagonal products (see Theorem 1.18). 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.

Quantitative measure equivalence

Let us recall some material of [START_REF] Delabie | Quantitative measure equivalence[END_REF]. A measure-preserving action of a discrete countable group G on a measured space (X, μ) is an action of G on X such that the map sending (g, x) to g ⋅ x is a Borel map and μ(E) = μ(g ⋅ E) for all E ⊆ ℬ(X) and all g ∈ G. We will say that a measure-preserving action of G on (X, μ) is free if for almost every x ∈ X we have g ⋅ x = x if and only if g = 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 , μ) such that:

• (X, μ) 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.

Introduction

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, μ) and two measure-preserving free actions of G and H on (X, μ) such that for almost every x ∈ X we have G ⋅ x = H ⋅ x. We call (X, μ) 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 , μ) 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 ℤ.

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 ⋅ x) | s ∈ S K }. This graph is endowed with a natural metric d SG fixing the length of an edge to one. Remark that if S ′ G is another generating set of G then there exists C > 0 such that for all x ∈ X and g ∈ G 1 C d SG (x, g ⋅ x) ≤ d S ′ G (x, g ⋅ x) ≤ Cd SG (x, g ⋅ x).

x H ⋅ x g • x H ⋅ (g ⋅ x) g ⋅ x g g ⋅ x

Elements of XH

Other elements of the corresponding orbit Finally if (X, X G , X H , μ) 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 • where for all x ∈ X H and g ∈ G we define g • x to be the unique element of H ⋅ g ⋅ x contained in X H viz.

{g • x} = (H ⋅ g ⋅ x) ∩ X H .
To formulate this in terms of cocycles, if α ∶ G×X → H is the cocycle introduced in eq. (1.1) then g • x = α(g, x) ⋅ g ⋅ x.

Definition 1.5 ([DKLMT20, Def. 2.20])

Let φ, ψ ∶ ℝ + → ℝ + be two non-decreasing maps. We say that a measure equivalence coupling (X, X G , X H , μ) from G to H is (φ, ψ)-integrable if for all g ∈ G (resp. h ∈ H) there exists c g > 0 (resp. c h > 0) such that both

∫ XH φ ( 1 c g d SH (g ⋅ x, g • x) )
dμ(x) and

∫ XG ψ ( 1 c h d SG (h ⋅ x, h • x) )
dμ(x) are finite. We say that the coupling is L ∞ -integrable if the map x ↦ d SH (s ⋅ x, s • x) is essentially bounded. We say that an orbit equivalence coupling is (φ, ψ)-integrable if it is (φ, ψ)-integrable as a measure equivalence coupling.

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 = ⟨S⟩. An equivalent manner to formulate the above definition using cocycles is to replace d SH (g ⋅ x, g • x) and d SG (h ⋅ x, h • x) in the integrals by |α(g, x)| SH and |β(h, x)| SH respectively.

If φ(x) = x p we will sometimes replace φ by L p and thus talk of (L p , ψ)-integrability instead of (φ, ψ)-integrability. In particular L 0 means that no integrability assumption is made. Finally, note that every (L ∞ , ψ)-integrable coupling is (φ, ψ)-integrable for any increasing map φ ∶ ℝ + → ℝ + . When φ = ψ we will say that the coupling is φ-integrable instead of (φ, φ)-integrable.

Example 1.7. Shalom proved in [START_REF] Shalom | Harmonic analysis, cohomology, and the large-scale geometry of amenable groups[END_REF] that two quasi-isometric amenable groups are L ∞ -measure equivalent.

Example 1.8. Delabie et al. obtained the following examples using a technique of tiling of Følner sequences (see [START_REF] Delabie | Quantitative measure equivalence[END_REF]Section 6]).

1. Let n, m ≥ 1. There exists an orbit equivalence coupling from ℤ m to ℤ n which is (L p , L q )-integrable for all p < n/m and q < m/n. 2. Let m ≥ 2. There exists an orbit equivalence coupling between ℤ and ℤ/mℤ ≀ ℤ that is (exp, φ ε )-integrable for all ε > 0 where φ ε (x) = log(x) log(log(x)) 1+ε .

3. There exists an orbit equivalence coupling between ℤ 4 and the Heisenberg group Heis(ℤ) 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 φ-integrable couplings between two amenable groups, for a given function φ. A first answer -and thus a first obstruction-is given by the isoperimetric profile.

1 Introduction

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. [START_REF] Delabie | Quantitative measure equivalence[END_REF] 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 ≼ g if there exists some constant C > 0 such that f(x) = 𝒪 ( g(Cx) ) as x tends to infinity. We write f ≃ g if f ≼ g and g ≼ f.

Recall that if G is generated by a finite set S, the isoperimetric profile of G is defined as1

I G (n) ∶= sup |A|≤n |A| |∂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 ℤ verifies I ℤ (n) ≃ n. A famous result of Erschler [START_REF] Erschler | On Isoperimetric Profiles of Finitely Generated Groups[END_REF] gives the two following examples.

Examples 1.10.

• Let q ≥ 2 and d ≥ 1. If G ∶= ℤ/qℤ ≀ ℤ d then I G (n) ≃ (log(n)) 1/d . • If G ∶= ℤ ≀ ℤ then I G (n) ≃ log(n)/ log ∘ 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 (φ, L 0 )-integrable measure equivalence coupling. If φ and t/φ(t) are increasing then

φ ∘ I H ≼ I G .
This theorem provides an obstruction for finding φ-integrable couplings with certain functions φ between two amenable groups. For example we can deduce from the preceding examples that there is no L 1 measure equivalence coupling from ℤ ≀ ℤ to ℤ/2ℤ ≀ ℤ.

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 ℤ?

This interrogation contains actually two questions: first it asks whether Theorem 1.11 is optimal when H = ℤ. We answer it positively in Theorem 1.16 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 φ-integrable measure equivalence coupling from G to H such that I G ≃ φ ∘ I H ? As we will see, the couplings obtained with G = ℤ in Theorem 1.16 and the one given by Theorem 1.18 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.

1 Introduction Question 1.14. Given a group H and a function φ does there exist a group G such that there exists a (φ, L 0 )-measure equivalent from G to H? When H = ℤ, we answered this question in [START_REF] Escalier | Building prescribed quantitative orbit equivalence with the group of integers[END_REF] for a large family of maps φ.

Theorem 1.15 ([Esc22, Theorem 1.8])

For all non-decreasing function ρ ∶ [1, +∞[→ [1, +∞[ such that x/ρ(x) is non-decreasing, there exists a group G such that • I G ≃ ρ ∘ log;

• there exists an orbit equivalence coupling from G to ℤ that is (φ ε , exp ∘ρ)-integrable for all ε > 0, where φ ε (x) ∶= ρ ∘ log(x)/ ( log ∘ρ ∘ log(x) ) 1+ε .

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 = ℤ (Theorem 1.16) or H a diagonal product (Theorem 1.18). We also refer to the paragraph named "Couplings building techniques and optimality" (page 9) for a discussion on this optimality.

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 [START_REF] Delabie | Quantitative measure equivalence[END_REF][START_REF] Carderi | Measure equivalence and sofic approximations[END_REF]. First let

𝒞 ∶= { ζ ∶ [1, +∞) → [1, +∞) | ζ continuous, ζ and x ↦ x/ζ(x)non-decreasing } .

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 = ℤ.

Theorem 1.16

Let ρ ∈ 𝒞 and κ ≥ 3. If (ρ(κ m )κ -m ) m∈ℕ is summable, then there exists a group G such that • I G ≃ ρ ∘ log;

• There exists a (ρ ∘ log, L 0 )-integrable orbit equivalence coupling from G to ℤ.

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

Optimality Recall that I ℤ (x) ≃ x. We know by Theorem 1.11 that for a coupling from a group G to ℤ, the best integrability we can hope for is φ ≃ I G . The above theorem thus shows that it is reached for a very large family of maps φ. In particular it answers Question 1.13 about optimality positively.

Remark on the hypothesis

The assumption made on (ρ(κ m )κ -m ) m excludes groups with isoperimetric profile I G ≃ log. In particular Question 1.13 is still open when G is a Lamplighter group and H = ℤ.

Delabie et al. [START_REF] Delabie | Quantitative measure equivalence[END_REF] introduced a way to compose couplings: given a measure equivalence from G to ℤ and one from ℤ 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 ℤ . This is the case when H = ℤ d .

Introduction

Corollary 1.17

Let ρ ∈ 𝒞, let d ∈ ℕ * and κ ≥ 3. If (ρ(κ m )κ -m ) m∈ℕ is summable, then there exists a group G such that • I G ≃ ρ ∘ log;
• There exists a (ρ ∘ log, L 0 )-integrable orbit equivalence coupling from G to ℤ 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.

Theorem 1.18

Let ρ , ρ ∈ 𝒞 with ρ moreover bijective. If • there exits ε > 0 such that ρ ∘ ρ -1 (x) ≼ x 1-ε ; • and if ρ does not grow too slowly; then there exists two groups G and H such that I G ≃ ρ ∘ log and I H ≃ ρ ∘ log and there exists a ( ρ ∘ ρ -1 , L 0 )-integrable measure equivalence coupling from G to H.

Remark on the hypothesis

The assumption that ρ ∘ ρ -1 (x) ≼ x 1-ε 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 ρ 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 ρ(x) = log ∘ ⋯ ∘ log ⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟ r times for r ∈ ℕ. In particular, the above theorem applies to ρ(x) = x and gives the following corollary.

Corollary 1.19

Let ρ ∈ 𝒞. If there exists ε > 0 such that ρ (x) ≼ x 1-ε , then there exists a group G such that • I G ≃ ρ ∘ log ;

• there exists a measure equivalence coupling from G to ℤ/qℤ ≀ ℤ that is ( ρ

, L 0 )- integrable.
We can deduce from the above result two corollaries. First define H ∶= ℤ 2 ⋊ A ℤ where A is the matrix

A ∶= ( 2 1 1 1 ) .

Corollary 1.20

Let ρ ∈ 𝒞. If there exists ε > 0 such that ρ (x) ≼ x 1-ε , then there exists a group G such that • I G ≃ ρ ∘ log;

• there exists a ( ρ , L 0 )-integrable measure equvalence coupling from G to H.

Second consider k ∈ ℕ * and the Baumslag-Solitar group defined by OVErVIEW Figure 2 sums up the known results on the integrability of couplings between the different groups appearing in this article. 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 [START_REF] Delabie | Quantitative measure equivalence[END_REF] 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 [START_REF] Delabie | Quantitative measure equivalence[END_REF], the integrability is always optimal up to a logarithmic error.

BS(1, k) = 〈a, b | a -1 ba = b k 〉 .
ℤ IZ(x) ≃ x ℤ d IZ(x) ≃ x 1/d Δ IΔ ≃ ρ ∘ log Δ I Δ ≃ ρ ∘ log LL ILL ≃ log BS(1, k) ℤ 2 ⋊A ℤ L p L q p < 1/d q < d ρ ∘ log exp log (log ∘ log) 1+ε L ∞
Hence we work here with Sofic approximations and the engineering developped in [START_REF] Carderi | Measure equivalence and sofic approximations[END_REF] instead. It allows us to obtain couplings with optimal integrability. Note however that where Theorem 1.15 does not require any additional conditions on couplings from the Lamplighter group to ℤ. Hence Question 1.14 is still open for φ ≃ log as well as the existence of an optimal coupling from the Lamplighter to ℤ. 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 explicit2 . 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 [START_REF] Carderi | Measure equivalence and sofic approximations[END_REF] 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 Theorem 1.16 in Section 3, while Section 4 is devoted to the proof of Theorem 1.18. The construction of the coupling with ℤ can be seen as in introduction to the quite more technical proof of Theorem 1.18. 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 to 4.

I

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.

SOFIc APPrOXIMATIONS

We start by recalling some results from [START_REF] Carderi | Measure equivalence and sofic approximations[END_REF] 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.

Sofic approximations

We recall here some material from [START_REF] Carderi | Measure equivalence and sofic approximations[END_REF]. In this paragraph G will be a finitely generated group endowed with a finite generating set S G and (𝒢 n ) n∈ℕ will be a sequence of finite, directed graphs labeled by the elements of S G . Let r > 0 and denote by 𝒢 (r) n the set of elements x ∈ 𝒢 n such that B 𝒢n (x, r) is isomorphic to B G (e G , r) seen as directed labeled graphs, viz.

𝒢 (r) n = { x ∈ 𝒢 n | B 𝒢n (x, r) ≃ B G (e G , r) } . Definition 2.1
We say that (𝒢 n ) n∈ℕ is a Sofic approximation if for every r > 0

lim n→∞ | 𝒢 (r) n | |𝒢 n | = 1.
Example 2.2. Any Følner sequence in an amenable group G is a Sofic approximation.

In [START_REF] Carderi | Measure equivalence and sofic approximations[END_REF] Carderi, Delabie, Koivisto and Tessera proved a condition for a measure equivalence to be (φ, L 0 )-integrable using Sofic approximations.

Theorem 2.3 ([CDKT22])

Let φ ∶ ℝ + → ℝ + be a non-decreasing map. Let G and H be two finitely generated groups with Sofic approximations (𝒢 n ) n and (ℋ n ) n and let ι n ∶ 𝒢 n → ℋ n be an injective map such that 1. There exists C > 0 such that the image of ι n is C-dense for all n ∈ ℕ; 2. For every s ∈ S G there exists δ > 0 such that lim

R→∞ sup n R ∑ r=0 φ(δr) | { x ∈ 𝒢 (1) n | d ℋn (ι n (x), ι n (x.s)) = r } | |𝒢 n | < ∞;
(2.1) 3. For every h ∈ H there exists δ > 0 such that lim

R→∞ sup n R ∑ r=0 ψ (δr) | { y ∈ ι n (𝒢 n ) ∩ ℋ (1) n | d ( ι -1 n (y), ι -1 n (y ⋅ h) ) = r } | |𝒢 n | < ∞. (2.2)
then there exists a (φ, ψ)-integrable measure equivalence coupling from G to H. Moreover if the maps ι n are bijective then there is a (φ, ψ)-integrable orbit equivalence coupling from G to H.

In [START_REF] Carderi | Measure equivalence and sofic approximations[END_REF] the authors used this theorem to obtain the following example.

Example 2.4 ([CDKT22, Th. 6.1]). Let k ≥ 3 and let H ∶= ℤ 2 ⋊ A ℤ where A is the matrix

A ∶= ( 2 1 1 1 ) .
There exists a (L ∞ , exp)-integrable measure equivalence coupling from ℤ/kℤ ≀ ℤ to H.

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 Δ a diagonal product as defined in appendix A verifying hypothesis (H) page 51. In particular (k m ) m and (l m ) m denote subsequences of geometric sequences and we let κ such that (k m ) m is a subsequence of (κ m ) m . To condense the proofs to come let

𝒮 1 ∶= {( (a m δ 0 ) m , 0 ) | a m ∈ A m} 𝒮 2 ∶= {( (b m δ km ) m , 0 ) | b m ∈ B m} .
(2.3) Finally, recall that 𝔩(n) denotes the integer such that k 𝔩(n) ≤ n < k 𝔩(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 Δ. We refer to appendix A.2 for details on the range of an element.

F n ∶= { (𝐟, t) ∈ Δ | range(𝐟, t) ∈ [0, n -1] } (2.4)
This sequence will be enough to obtain the integrability of the coupling with ℤ wanted in Theorem 1.16, but not for the one of Theorem 1.18. We thus introduce a finer one.

A rEFINED SEQUENcE To show Theorem 1.18 we will need to control the speed at which the cardinal of the Følner sets grows. More precisely if (ℱ n ) n denotes this sequence, we want it to verify C|ℱ n | ≤ |ℱ n+1 | ≤ C ′ |ℱ n | for some constants C, C ′ > 0. Note that this is not true for (F n ) n defined above. Indeed in F n+1 , unlike in F n , an element (𝐟, t) can take non-trivial values at f ′ m (n) for all m ∈ [0, 𝔩(n)]. This allows for many new elements in F n+1 . To counter this, the idea is thus to allow f ′ m (n) to take non-trivial values for one m at a time. Moreover since |Γ ′ m | can grow fast, we choose for all m a subset series

(Λ m j ) j of Γ ′ m such that C|Λ m j | ≤ |Λ m j+1 | ≤ C ′ |Λ m j |.
This is what we formalize below and sum up in Figure 3.

For all i ∈ ℕ * we define an integer N i > 0 and a sequence (Λ i j ) j∈{0,…,Ni} such that

⎧ ⎨ ⎩ {e} = Λ i 0 ⊂ Λ i 1 ⊂ ⋯ ⊂ Λ i Ni ∶= Γ ′ i 2|Λ i j | ≤ |Λ i j+1 | ≤ 2q|Λ i j | (∀j ∈ {0, … N i -1}).
(2.5)

When i = 0 define N 0 ∶= 1 and let Λ 0 1 ∶= Γ 0 ∼ A × B.
Now for all n ∈ ℕ, all i ∈ {0, … , 𝔩(n -1)} and j ∈ {1, … , N i } we define

F n,i,j ∶= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (𝐟, t) | | | | | | | | | | | | | | | t ∈ [0, n -1] supp(f 0 ), supp(f ′ m ) ⊂ [0, n -1] ∀m ∈ {1, … , i} f ′ i (n -1) ∈ Λ i j supp(f ′ m ) ⊂ [0, n -2] ∀m ∈ {i + 1, … , 𝔩(n -1)} f ′ m ≡ e ∀m > 𝔩(n -1) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (2.6)
For an element (𝐟, t) of F n,2,j , we represent the sets where 𝐟 takes its values in Figure 3.

f ′ 1 k1 f ′ 2 k2 f ′ 3 k3 Λ i j f0 n n -1 0 Values taken in… A0 × B0 Γm Λ i j 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 ∈ ℕ and i ∈ {0, … , 𝔩(n -1)} we define F n,i,Ni+1 = F n,i+1,1 and F n,𝔩(n-1)+1,0 = F n+1,0,1 .

Proposition 2.5

Let (ℱ n ) n∈ℕ be the sequence defined inductively by ℱ 0 ∶= F 1,0,N 0 and for all n ≥ 0 by ℱ n+1 = F m,i,j+1 where m, i and j are such that ℱ n = F m,i,j . Then (ℱ n ) n∈ℕ is a Følner sequence of Δ.

Proof. Let n ∈ ℕ, let i ∈ [0, 𝔩(n -1)] and j ∈ [1, N i ] and take (𝐟, t) in F n,i,j .

If s = (0, 1) then (𝐟, t)s belongs to F n,i,j if and only if t ≠ n -1. Similarly if s = (0, -1) then (𝐟, t)s ∈ F n,i,j if and only if t ≠ 0.

Now let s = ( (a m δ 0 ) m , 0 ) for some a ∈ A. The action of s on (𝐟, t) does not change the value of the cursor, thus there exists some 𝐠 such that (𝐟, t)s = (𝐠, t). For all x ≠ t it verifies g 0 (x) = f 0 (x), moreover g 0 (t) = f 0 (t)a 0 . Thus supp(g 0 ) = supp(f 0 ). Now consider m > 0. Then for all x ≠ t we have g m (x) = f m (x) and in particular g ′ m (x) = f ′ m (x). Furthermore using the decomposition given by Lemma A.6 and the above value of g 0 (t) we get

g m (t) = f m (t)a m = f ′ m (t)θ A m (f 0 (t)) θ B m (f 0 (t -k m ))a m , = f ′ m (t)θ A m (f 0 (t)a m ) θ B m (f 0 (t -k m )), = f ′ m (t)θ A m (g 0 (t)) θ B m (g 0 (t -k m )).
By unicity of the decomposition we thus obtain g ′ m (t) = f ′ m (t). Hence supp(g ′ m ) = supp(f ′ m ) and g ′ m (n -1) = f ′ m (n -1) which belongs to Λ i j . Thus (𝐠, t) belongs to F n,i,j . The case where s ∈ 𝒮 2 is very similar.

Thus ∂F n,i,j = {(𝐟, t) ∈ F n,i,j | t ∈ {0, n-1}} and in particular |∂F n,i,j |/|F n,i,j | ∼ 2/n. Hence (ℱ n ) n is a Følner sequence.

Remark 2.6. Note that (F n ) n∈ℕ defined in eq. (2.4) is a subsequence of (ℱ n ) n∈ℕ . Indeed using [Esc22, Lemma 2.12] we can prove that F n ∶= F n,𝔩(n-1),N 𝔩(n-1) .

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 ∈ ℕ and i ∈ [0, 𝔩(n -1)] and j ∈ [0, N i ] and consider F n,i,j as defined in eq. (2.6). Then

| F n,i,j | = nq n i-1 ∏ m=1 | Γ ′ m | n-km | Λ i j | 𝔩(n-1) ∏ m=i | Γ ′ m | n-km-1 In particular 2|F n,i,j | ≤ |F n,i,j+1 | ≤ 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 Theorem 1.18.

Proof. Let F n,i,j as defined in eq. (2.6) and take (𝐟, t) ∈ F n,i,j , then there are exactly n possible values of t. Moreover 𝐟 is uniquely determined by

f 0 and f ′ 1 , … , f ′ 𝔩(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 ( |A||B| ) n pos- sible values for f 0 . Moreover if 0 < m < i then f ′ m is supported on [k n , n -1] which has n -k m elements
, and on this interval it can take any values in Γ ′ m so there are exactly

| Γ ′ m | n-km possibilities for f ′ m . Similarly for m > i the map f ′ m is supported on [k m , n -2] which contains n -1 -k m elements, thus we have | Γ ′ m | n-km-1 choices for such a map.
Finally when m = i the map

f ′ i is supported on [k i , n -k i ] and • for any x ∈ [k i , n -k i -1] all values of |Γ ′ i | can be taken by f ′ i ; • f ′ i (n -1) can take any value in Λ i j . We thus have | Λ i j | |Γ ′ i | n-ki-1 possibilities for f ′ i .
Hence the first assertion.

Assume first that i < 𝔩(n -1) and j = N i , then F n,i,Ni+1 = F n,i+1,1 and hence using also eq. (2.5)

|F n,i+1,1 |/|F n,i,Ni | = | Λ i+1 1 | ∈ [2, 2q]. Similarly if j < N i then |F n,i,j+1 |/|F n,i,j | = | Λ i j+1| / | Λ i j | which belongs to [2, 2q]. Finally if i = 𝔩(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,Ni | = q(n + 1)/n ∈ [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 Δ such that ln |F n,i,j | ≤ C 2 nl 𝔩(n-1) for all n ∈ ℕ.

Remark 2.9. Let us mention that a similar estimation was done in [START_REF] Escalier | Building prescribed quantitative orbit equivalence with the group of integers[END_REF] for the value of ln |F κ n |. We refer to eq. (2.4) and Remark 2.6 for the definition of (F n ) 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 𝔏(n) ∶= 𝔩(κ n -1) then by [Esc22, Prop. 4.3] there exists two constants C 3 , C 4 > 0 such that for all n ∈ ℕ,

C 3 κ n-1 l 𝔏(n) ≤ ln |F κ n | ≤ C 4 κ n 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 Δ such that for all n ∈ ℕ * , ln

( 𝔩(n-1) ∏ m=1 | Γ ′ m | n-km ) ≤ C 1 nl 𝔩(n-1) .
Proof. By eq. (A.1) there exists c 1 , c 2 > 0 such that ln |Γ m | ≤ c 1 l m + c 2 , for all m. Then, ln

( 𝔩(n-1) ∏ m=1 | Γ ′ m | n-km ) ≤ 𝔩(n-1) ∑ m=1 (n -k m ) ln |Γ ′ m |, ≤ 𝔩(n-1) ∑ m=1 (n -k m ) (c 1 l m + c 2 ) .
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 ∑ 𝔩(n-1) m=1 (c 1 l m + c 2 ) 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

( 𝔩(n-1) ∏ m=1 | Γ ′ m | n-km ) ≤ C 1 nl 𝔩(n-1) .
Proof of Proposition 2.8. Since Λ i j ⊆ Γ ′ i , using Lemma 2.7 and Lemma 2.10 we get

ln |F n,i,j | ≤ ln ( nq n 𝔩(n-1) ∏ m=1 | Γ ′ m | n-km ) ≤ ln (n) + n ln(q) + C 1 nl 𝔩(n-1) .
Thus, there exists C 2 > 0 such that ln |F n,i,j | ≤ C 2 nl 𝔩(n-1) .

cOUPLING WITH 𝕫

This section is devoted to the proof of Theorem 1.16. In the following Δ will be a diagonal product as defined in appendix A and verifying (H) page 51. In particular its isoperimetric profile is of the form I Δ ≃ ρ ∘ log for some ρ ∈ 𝒞. To prove Theorem 1.16 we actually show that the diagonal product obtained from the isoperimetric profile ρ ∘ 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 𝒢 n ⊆ Δ and ℋ n ⊆ ℤ and then define a bijection ι n between them. For this we use the notion of decomposition in variable base of an integer. All necessary material are recalled in appendix B.1. Now let us describe the idea of the bijection. Given (𝐟, t) in 𝒢 n we map 𝐟 to an integer decomposed in some variable base (b i ) i and decompose t is some constant base κ. The image of (𝐟, t) by ι 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 ι n (𝐟, t) under the action of some generator s of Δ on (𝐟, t). Then for some distance r > 0, we compute the proportion of elements (𝐟, t) in 𝒢 n that the action of s sents ι n (𝐟, t) at distance r from ι n( (𝐟, t)s ) . We conclude on the proof of Theorem 1.16 by showing that eq. (2.1) is verified.

Bijection between Sofic approximations

Recall that (F n ) n∈ℕ defined in eq. (2.4) is a Følner sequence (and hence a Sofic approximation) of Δ. Therefore, the following subsequence of (F n ) n∈ℕ provides a Sofic approximation of Δ:

𝒢 n ∶= F κ n = { (𝐟, t) | range (𝐟, t) ⊆ {0, … , κ n -1} } . Let ℋ n ∶= [0, |𝒢 n |-1] ⊆ ℤ and denote by 𝔏(n) the integer verifying k 𝔏(n) ≤ κ n -1 < k 𝔏(n)+1 .
Idea of the bijection Consider (𝐟, t) ∈ 𝒢 n . To construct our bijection we are going to "encode" the information contained in 𝐟 into an integer. We decompose it in some variable base (b i ) i to be precised later and decompose t in base κ. We then intertwine the digits to obtain one integer from the two preceding ones (see Figure 4). 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 ∈ 𝒮 Δ , we need ι n (𝐟, t) to be sent at a reasonable distance from ι n( (𝐟, t)s ) in ℤ.

𝒢 n 𝐟 t ∑ n-1 i=0 t i κ i ∑i x i b i-1 ⋯ b 0 ℋ n ⊆ ℤ z = t 0 + κx 0 +κb 0 t 1 + ⋯
Recall (see Claim A.10) that 𝐟 is uniquely determined by f 0 and (f ′ m ) m . As we will see, the main problem is to number f 0 . So first assume for simplicity that Δ is a lamplighter group and thus 𝐟 = f 0 ∶ ℤ → A × B. A naive way to encode the information contained in f 0 is to map it to the integer ∑ κ n -1 i=0 f 0 (i)q i . But then the action of s ∈ 𝒮 ℤ \{(0, 1)} will change the value of the lamp f 0 (t) and thus the distance between ι n( (𝐟, t)s ) and ι n (𝐟, 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 κ of t. More precisely, if t = ∑ n-1 i=0 t i κ i denotes the decomposition in base κ of t, we define a sequence of nested intervals (ℬ j (t)) j such that the lower and upper bounds of ℬ j (t) depends only on (t i ) i≥j . We then encode the information of f 0 reading first the values taken by f 0 on ℬ 0 (t), then on ℬ 1 (t), etc. (see Figure 5). This way, if t and t + 1 differ only in their first i 0 digits then ℬ j (t) and ℬ 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 (𝐟, t) in a general diagonal product, we start by number f 0 using the foregoing blocs decomposition and then encode (f ′ 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 (𝐟, t) and the injection ι n in Section 3.1.2. We conclude by the proof of the bijectivity of ι n in Section 3.1.3.

Bloc decomposition

Fix (𝐟, t) ∈ 𝒢 n and decompose t in base κ as t = ∑ n-1 i=0 t i κ 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 ℬ i (t) such that if the decomposition in base κ of t and t + 1 differ only in their first i 0 terms, then the corresponding intervals ℬ i (t) and ℬ i (t + 1) are the same for all i > i 0 .

Lemma 3.1

Let t ∈ [0, κ n -1] and i ∈ {0, … , n} and define

ℬ i (t) ∶= [ n-1 ∑ j=i t j κ j , n-1 ∑ j=i t j κ j + κ i -1 ] .
The sequence (ℬ i (t)) 0≤i≤n thus defined verifies ℬ i (t) ⊂ ℬ i+1 (t) for all i ≤ n -1. In particular

{t} = ℬ 0 (t) ⊂ ℬ i (t) ⊆ ℬ n (t) = [0, κ n -1],
and thus t belongs to ℬ i (t) for all i ≤ n.

Remark 3.2. Remark that by definition diam (ℬ i (t)) = κ i -1 ∼ κ i for all i ≤ n.

We represent in Figure 5 such a nesting of intervals for κ = 3, n = 3 and t = 16 whose decomposition is thus given by t = 1 + 2 ⋅ 3 + 1 ⋅ 3 2 . 0 9 15 16 Proof of Lemma 3.1. Let t ∈ [0, κ n -1] and i ∈ {0, … , n -2} and let us prove that ℬ i (t) ⊂ ℬ i+1 (t). Remark that ∑ n-1 j=i t j κ j is greater than ∑ n-1 j=i+1 t j κ j . Moreover, since

t 17 3 3 = 27 26 B 3 (t) = [0, 26] B 2 (t) = [9, 17] B 1 (t) B 0 (t) B 0 (t) B 1 (t)\B 0 (t) B 2 (t)\B 1 (t) B 3 (t)\B 2 (t)
t i κ i ≤ (κ -1)κ i = κ i+1 -κ i ,
we thus have

n-1 ∑ j=i t j κ j + κ i -1 ≤ (κ i+1 -κ i ) + n-1 ∑ j=i+1 t j κ j + κ i -1 = n-1 ∑ j=i+1 t j κ j + κ i+1 -1.
Hence the inclusion.

Remark 3.3. By Remark 3.2 and the above lemma, we have |ℬ i (t)\ℬ i-1 (t)| = κ i -κ i-1 . In particular the number of lamp configurations from ℤ to A × B supported on ℬ i (t)\ℬ i-1 (t) is q κ i -κ i-1 .

Global numbering

By the preceding remark we can define applications

ν 0,t ∶ {ζ ∶ ℬ 0 (t) → A × B} → [ 0, q -1 ] , ∀i ≥ 1 ν i,t ∶ {ζ ∶ ℬ i (t)\ℬ i-1 (t) → A × B} → [ 0, q κ i -κ i-1 -1 ] .
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 ν i instead of ν t,n .

Claim 3.4. There exists a bijection

μ n ∶ { 𝐟 ′ | supp(f ′ m ) ⊆ [k m , κ n -1], ∀m ∈ [0, 𝔏(n)] } → [ 0, |𝒢 n | κ n q κ n -1 ] .
Proof. Recall that 𝒢 n = F κ n . Consider (𝐟, t) ∈ 𝒢 n . The number of such possible 𝐟 is equal to the number of elements of 𝒢 n divided by the number of possible cursor t, that is to say |𝒢 n |/κ n . Recall moreover (see appendix A.1) that in a diagonal product 𝐟 is uniquely determined by f 0 and 𝐟 ′ . Since supp(f 0 ) ⊆ [0, κ n -1] and f 0 can take all possible values on that interval, we have q κ n possible values for f 0 . Similarly, for all m ∈ [0, 𝔏(n)] the support of f ′ m is in [k m , κ n -1] and f ′ m can take all possible values on that interval. Hence

| { 𝐟 ′ | supp(f ′ m ) ⊆ [k m , κ n -1], ∀m ∈ [0, 𝔏(n)] } | = |{𝐟 | ∃t ∶ (𝐟, t) ∈ 𝒢 n }| /q κ n , = |𝒢 n |/(κ n q κ n ).
The information encoded by each of the previous maps is represented in Figure 6.

ν 0 ν 1 ν 2 ν n k 1 f ′ 1 k 2 μ f ′ 2 k 3 f ′ 3 f0 κ n 0 Figure 6: Numbering in Δ
Using the maps defined above we are now able to encode in an integer the information contained in 𝐟. Indeed we can consider the map sending 𝐟 to the number

ν 0 ( f 0|ℬ 0 (t)) + n ∑ i=1 ν i,t ( f 0|ℬi(t)\ℬ i-1 (t)) q κ i-1 + κ n q κ n μ n (𝐟 ′ ).
The above decomposition can be seen as the writing of the corresponding integer in the variable base (q, q κ-1 , … , q κ n -κ n-1 , max μ n + 1). We refer to appendix B.1 for more details on variable base. The digits of the decomposition are given by the values of the ν i,t 's and μ n . Intertwining these digits with the ones of the decomposition of t in base κ we obtain:

ι n (𝐟, t) ∶= ν 0 ( f 0|ℬ 0 (t)) + n-1 ∑ i=0 t i κ i q κ i + n ∑ i=1 ν i,t ( f 0|ℬi(t)\ℬ i-1 (t)) κ i q κ i-1
+κ n q κ n μ n (𝐟 ′ ).

(3.1) It corresponds to the decomposition of ι n (𝐟, t) in the variable base (β i ) i defined below.

β 0 = q ∀i ∈ [1, n] β 2i = q κ i -κ i-1 ∀i ∈ [1, n] β 2i-1 = κ β 2n+1 = max(μ n ) + 1.
Please note that the variable base depends on n but in order to reduce formalism we chose to abuse notations and write β i instead of β n,i .

Bijection

In order to obtain an orbit equivalence using Theorem 2.3 we need to prove that ι n is bijective.

Proposition 3.5

For all n ∈ ℕ, the map ι n defined in eq. (3.1) is a bijection from

𝒢 n = F κ n to ℋ n = [ 0, |𝒢 n | -1 ] .
Proof. Let n ∈ ℕ. By Lemma B.1 on the decomposition in variable base applied to (β i ) i the map ι n defined in eq. (3.1) verifies min ι n = 0 and max ι n = κ n q κ n (max μ n + 1) -1. Since max

μ n + 1 = |𝒢 n |/(κ n q κ n ) we obtain that the image of ι n is included in ℋ n = [0, |𝒢 n | -1].
The injectivity of ι n comes from the unicity of the decomposition in variable base (see Lemma B.1). To prove the surjectivity, consider z ∈ ℋ n then we can decompose it in base

(β i ) i as z = [z 0 , … , z 2n+1 ] β . In particular z 2i-1 ∈ [0, q -1] for all i ∈ [1, n]. Define t = ∑ n i=1 z 2i-1 κ i then t belongs to [0, κ n ].
Moreover since ν i,t and μ n are bijections the others coefficients determine 𝐟 such that (𝐟, t) ∈ 𝒢 n verifies ι n (𝐟, t) = z.

Quantification

Now that we have defined a bijection between our Sofic approximations we need to show that eq. (2.1) is verified. So for (𝐟, t) ∈ 𝒢 (1) n and s ∈ 𝒮 Δ we first bound the distance between ι n (𝐟, t) and ι n( (𝐟, t)s ) . Then for a given r > 0 we provide an estimate of the proportion of elements in 𝒢 n such that ι n (𝐟, t) and ι n( (𝐟, t)s ) are at distance r in ℋ n . Finally we show that the aforementioned equation is verified.

Distance

Consider (𝐟, t) ∈ 𝒢 (1) n . We compare in this section the distance in ℤ between ι n (𝐟, t) and ι n( (𝐟, t)s ) for some s ∈ 𝒮 Δ . We will distinguish two cases depending on s = (0, 1) or not.

If (𝐟, t) belongs to Δ we denote by 𝐟 ′ the sequence (f ′ m ) m=0,…,𝔏(n) .

AcTION ON THE LAMP Let us start by looking at a generator that modifies the lamp configurations. So consider s ∈ 𝒮 1 ∪ 𝒮 2 and let ( f, t) ∶= (𝐟, t)s.

Lemma 3.6

For all s ∈ 𝒮 1 ∪ 𝒮 2 and (𝐟, t) ∈ 𝒢 (1) n we have |ι n (𝐟, t) -ι n( (𝐟, t)s ) | ≤ q.

Proof. First recall that we showed in the proof of Proposition 2.5 that 𝐟 ′ = f′ . Thus μ n (𝐟 ′ ) = μ n( f′ ) . Moreover f0 differs from f 0 only at t. Since the cursors of (𝐟, t)s and (𝐟, t) are the same we obtain

(∀i > 0) ν i,t ( f 0|ℬi(t)\ℬ i-1 (t)) = ν i,t ( f0|ℬi(t)\ℬ i-1 (t)) .
Hence using eq. (3.1) we get

|ι n (𝐟, t) -ι n( (𝐟, t)s ) | = | ν 0,t (f 0 (t)) -ν 0,t ( f0 (t) ) | ≤ q.
AcTION ON THE cUrSOr Now consider s = (0, 1). Let t + 1 ∶= ∑ n-1 i=0 t i κ i be the decomposition in base κ of t + 1. Note that since (𝐟, t) belongs to 𝒢 (1) n , it verifies t < n -1 and thus there exists i ∈ {0, … , n -1} such that t i < κ -1. Therefore, we can define

i 0 (t) ∶= min{i ≤ n | t i < κ -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 (𝐟, t) ∈ 𝒢 (1) n we have |ι n (𝐟, t) -ι n (𝐟, t + 1)| < κ i 0 (t)+1 q κ i 0 (t)+1 .

Let us start by showing the following useful claim.

Claim 3.8. Let t ∈ [0, n -2], then ℬ i (t) = ℬ 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 κ is given by t+1 ∶= (t i 0 (t) +1)+ ∑ n-1 i=i 0 (t)+1 t i κ i . In particular t i = t i for all i > i 0 (t). But ℬ i (t) depends only on the value of (t j ) j≥i (see Lemma 3.1). Hence the claim.

Proof of Lemma 3.7. By the above claim ℬ i (t) = ℬ i (t + 1) for all i > i 0 (t). Hence

(∀i > i 0 (t) + 1) ν i,t ( f 0|ℬi(t)\ℬ i-1 (t)) = ν i,t+1 ( f0|ℬi(t+1)\ℬ i-1 (t+1)) .
Thus by eq. (3.1) we get

| ι n (𝐟, t) -ι n( (𝐟, t)s ) | ≤ | ν 0,t (f 0 (t)) -ν 0,t+1 ( f0 (t + 1) ) | + i 0 (t) ∑ i=0 |t i -t i |κ i q κ i + i 0 (t)+1 ∑ i=1 | ν i,t ( f 0|ℬi(t)\ℬ i-1 (t)) -ν i,t+1 ( f 0|ℬi(t+1)\ℬ i-1 (t+1)) | κ i q κ i-1
Thus by Lemma B.1 we can bound | ι n (𝐟, t) -ι n( (𝐟, t)s ) | by above by κ i 0 (t)+1 q κ i 0 (t)+1 -1. Hence the lemma.

Enumeration

Consider r > 0. We now give an estimate of the number of elements (𝐟, t) ∈ 𝒢 (1) n such that ι n (𝐟, t) and ι n( (𝐟, t)s ) are at distance r in ℤ. With regard to the previous section, it corresponds to determining the number of elements (𝐟, t) ∈ 𝒢 n such that i 0 (t) = m.

Lemma 3.9

Let n ∈ ℕ and (𝐟, t) ∈ 𝒢 (1) n . For

all m ∈ [0, n -1] | { (𝐟, t) ∈ 𝒢 n | κ m q κ m ≤ | ι n (𝐟, t) -ι n( (𝐟, t + 1) ) | < κ m+1 q κ m+1 } | ∼ |𝒢 n |κ -m . Proof. Let m ∈ [0, n -1]. By Lemma 3.7 | { (𝐟, t) ∈ 𝒢 n | κ m q κ m ≤ | ι n (𝐟, t) -ι n( (𝐟, t + 1) ) | < κ m+1 q κ m+1 } | = |{(𝐟, t) ∈ 𝒢 n | i 0 (t) = m}| .
But requiring i 0 (t) = m forces t 0 , … , t m-1 to be equal to κ -1 and t m can only take κ -1 possible values. Thus there are (κ -1)κ n-m-1 possible values of t verifying i 0 (t) = m.

Finally there is no condition on 𝐟 so we have |𝒢 n |/κ n possible values for 𝐟, therefore

| { (𝐟, t) ∈ 𝒢 n | i 0 (t) = m } | = |𝒢 n |(κ -1)κ -(m-1) ∼ |𝒢 n |κ -m .

Integrability

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

Proof of Theorem 1.16. Let ρ ∈ 𝒞 and consider Δ the diagonal product with isoperimetric profile I Δ ∶= ρ ∘ log as defined in appendix A.3.2. Assume moreover that (ρ(κ m )κ -m ) is summable.

Consider 𝒢 n and ℋ n as defined in Section 3.1 above and ι n the bijection defined in eq. (3.1). Before looking at the integrability, note since ι n is bijective Theorem 2.3 gives an orbit equivalence coupling. We need to show that eq. (2.1) is verified for φ = ρ ∘ log.

Fix R > 0 and n ∈ ℕ. For all s ∈ 𝒮 Δ , we need to bound the following sum

Σ R,n ∶= R ∑ r=0 ρ ∘ log (r) | { (𝐟, t) ∈ 𝒢 (1) n | d ℋn (ι n (𝐟, t), ι n ((𝐟, t) ⋅ s)) = r } | |𝒢 n |
First consider s ∈ 𝒮 ℤ \{(0, 1)}. By Lemma 3.6 the distance between ι n (𝐟, t) and ι n ((𝐟, t) ⋅ s) is at most q for all (𝐟, t) ∈ 𝒢 (1) n . Using this last remark and then that for all r ≤ min(R, q) we can bound ρ ∘ log(r) by above by ρ ∘ log(q), we obtain

Σ R,n = min(R,q) ∑ r=0 ρ ∘ log (r) | { (𝐟, t) ∈ 𝒢 (1) n | d ℋn (ι n (𝐟, t), ι n ((𝐟, t) ⋅ s)) = r } | |𝒢 n | ≤ ρ ∘ log(q) | { (𝐟, t) ∈ 𝒢 (1) n | d ℋn (ι n (𝐟, t), ι n ((𝐟, t) ⋅ s)) ≤ q } | |𝒢 n | = ρ ∘ log(q).
If s = (0, 1) then using both Lemmas 3.7 and 3.9 we get that Σ n,R is bounded (up to a multiplicative constant) by ∑ n-1 m=0 ρ ∘ log ( κ m+1 q κ m+1 ) κ -m . But there exists C ≥ 1 such that ρ ∘ log ( κ m+1 q κ m+1 ) = ρ ( κ m+1 log(q) + m log(κ) ) ≤ ρ (Cκ m ) . Since ρ(Cx) ≤ Cρ(x) (see eq. (A.2)) we get that

n-1 ∑ m=0 ρ ∘ log ( κ m+1 q κ m+1 ) κ -m ≤ C n-1 ∑ m=0 ρ (κ m ) κ -m
By hypothesis (ρ (κ m ) κ -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 (ρ ∘ log, L 0 )-integrable orbit equivalence.

Let us now turn to the proof of Corollary 1.17. The idea is to compose the coupling from Δ to ℤ just obtained with the one from ℤ to ℤ 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 , μ 1 ) (resp. (X 2 , μ 2 )
) is a (φ, L 0 )-integrable (resp. (ψ, L 0 )-integrable) measure equivalence coupling from Γ to Λ (resp. Λ to Σ), the composition of couplings gives a (φ ∘ ψ, L 0 )-integrable measure equivalence coupling from Γ to Σ. If both couplings are orbit equivalence couplings, then so is the composition.

We can now use it to prove our corollary on ℤ d .

Proof of Corollary 1.17. Let d ∈ ℕ * . Let ρ ∈ 𝒞 and let Δ be the diagonal product defined in Proposition A.12, in particular it verifies I Δ ≃ ρ ∘ log. Recall that by the first point of Example 1.8 there exists an orbit equivalence from ℤ to ℤ 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 (ρ ∘ log(⋅ p ), L 0 )-integrable orbit equivalence coupling from Δ to ℤ d . Now if d > p ≥ 1 by eq. (A.2)

ρ ∘ log(x) ≤ ρ(p log(x)) ≤ pρ ∘ log(x).
Since ρ(p log(x)) = ρ ∘ log(x p ) we thus have ρ ∘ log(x p ) ≃ ρ ∘ log. When p < 1, using Claim A.18 instead of eq. (A.2) we obtain a similar equivalence. Thus in both cases ρ ∘ log(x p ) ≃ ρ ∘ log(x). Hence the corollary.

cOUPLING BETWEEN DIAGONAL PrODUcTS

Our aim in this section is to show Theorem 1.18. We actually show the more precise version below (Theorem 4.1). In particular the meaning of the assumption that ρ "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 ρ (see Lemma A.16) and a bijective piecewise affine map ρ bij (see Lemma A.19) such that the corresponding diagonal product Δ verifies I Δ ∼ ρ ∘ log ∼ ρ bij ∘ log.

Framework (F)

1. κ ≥ 3; 2. ( k m) m and (k m ) m are subsequences of (κ m ) m ; 3. ( l m ) and (l m ) m are subsequences of a geometric sequence; 4. Δ is the diagonal product determined by the two sequences ( k m ) and ( l m ) and ρ is corresponding the piecewise affine map; 5. Δ is the diagonal product determined by (k m ) m and (l m ) m and ρ bij is the corresponding bijective piecewise affine map.

The following theorem precises the statement of Theorem 1.18.

Theorem 4.1

In the framework (F), if • there exits ε > 0 such that ρ ∘ ρ -1 bij (x) ≼ x 1-ε • and the sequence l m exp(-l m-1 ) is summable then there exists a ( ρ ∘ ρ -1 bij , L 0 ) -integrable measure equivalence coupling from Δ to Δ.

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 ρ(x) = x then k 1 = +∞ and l 1 = 0 and Δ is the usual lamplighter group over A × B. In particular it verifies the second assumption. We will use this to show Corollary 1.19.

Example 4.3. Let ρ(x) ∶= x 1/(1+α) . In this case k m = κ m and l m = κ αm and the sequence (l m exp(-l m-1 )) m is therefore summable. In particualr, if ρ (x) ∶= x 1/(1+ α) with α > α then there exists a (L (1+α)/(1+ α) , L 0 )-coupling from Δ to Δ.

Example 4.4. Similarly if ρ(x) = log(x) 1/α then k m = κ m and l m = exp(κ αm ). Such a sequence (l m ) m verfies the second assumption. More generally if r ≥ 1 and ρ = log ∘ ⋯∘log with r logarithms, then k m = κ m and l m = exp(⋯ exp(κ 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 Theorem 1.16. 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 Δ and Δ. 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 𝒢 n in Δ and ℋ n in Δ being two Sofic approximations and a Cdense injection between 𝒢 n and ℋ 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 𝒢 n in two different integers, that is to say we are going to define an embedding from 𝒢 n to ℤ 2 . This part is the analogue of the encoding described in Sections 3.1.1 and 3.1.2 for the coupling with ℤ. Doing the same thing for elements of ℋ n we will obtain the wanted injection from 𝒢 n to ℋ n (see Figure 7). Then our goal would be to show that the injection ι n thus defined verifies eq. (2.1) with φ ∶= ρ ∘ ρ -1 bij .

𝒢 n ℋ n ℤ 2 (𝐟, t) (𝐠, u) (x, y) ι n
Figure 7: Definition of the injection: first idea This is the general idea, let us now describe the encoding process. An element (𝐟, t) of 𝒢 n or ℋ n is composed of two informations: a lamp configuration 𝐟 and a cursor t. A first "naive" way to proceed to define the injection would be to associate to every lamp configuration 𝐟 appearing in 𝒢 n a lamp configuration 𝐡 that appears in ℋ n , and to each cursor t of an element in 𝒢 n a cursor u appearing in ℋ n . In doing so we would need ℋ n to verify

| { 𝐠 | ∃u ∈ ℤ, (𝐠, u) ∈ ℋ n} | ≥ | { 𝐟 | ∃t ∈ ℤ, (𝐟, t) ∈ 𝒢 n} | . (4.1)
But by assumption on the isoperimetric profile, Δ is the "bigger group" hence for m large enough the number of elements in Γ ′ m is larger than the one of Γ ′ m . Therefore for the same support we have more possible lamp configurations f ′ m ∶ ℤ → Γ ′ m than we have of the form

g ′ m ∶ ℤ → Γ ′ .
In other words, in order for (ℋ n ) n∈ℕ to be a Følner sequence of the form (F dn,in,jn ) n∈ℕ that verifies eq. (4.1) above, we would need the sequence (d n ) n∈ℕ to grow much faster than n. In these conditions the map sending a cursor t ∈ [0, n] to a cursor u ∈ [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 (𝐟, t) in 𝒢 n , we use a part of the information contained in the lamp configuration and the cursor t to define a cursor in Δ. The unused information contained in 𝐟 is then used to define a lamp configuration in ℋ 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 ι n thus defined is a C-dense injection for some constant C.

Finally, the object of Section 4.3 is to prove that ι n verifies eq. (2.1). To do so, we first study the behaviour of ι n under the action of the generators of Δ : for s ∈ S Δ and (𝐟, t) ∈ 𝒢 n , we give an estimate of the distance between ι n (𝐟, t) and ι n( (𝐟, t)s ) . 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 𝒢 n such that ι n (𝐟, t) is at distance r from ι n( (𝐟, t)s ) . 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 ρ ∘ ρ -1 bij . We use it more precisely in the proof of Lemma 4.5 and page 48, when checking the integrability condition.

The condition on (l m ) m∈ℕ is only a technical assumption that could be avoided by considering another numbering process, more complex, subdividing the groups Γ ′ m . However, as Examples 4.3 and 4.4 and Corollary 1.19 show, this summability condition is verified by a large family of diagonal products. Let us describe where we use it. First consider (𝐟, t) ∈ 𝒢 n and (𝐠, u) = ι n (𝐟, t) its image by the built injection. The action of a generator on (𝐟, t) might modify the value of g 0 , g ′ 1 , … , g ′ m in Δ for some m ∈ ℕ (see Section 4.3.1 for more details). Denote D n = range(𝐠, u), we can show that the distance between (𝐠, u) and this modified element is then equivalent to D n l m . Now the proportion of such elements (𝐟, t) in 𝒢 n is asymptotically bounded by |Γ ′ m-1 | -1 q -Dn (see Lemma 4.29). But |Γ ′ m-1 | ∼ exp ( l m-1) . Hence for eq. (2.1) to be verified, we need the sequence ( D n q -Dn l m exp ( l m-1)) m∈ℕ to be summable. The hypothesis made on (l m ) m ensures this integrability. We refer to pages 48 and 49 for the corresponding computations using it.

Definition of the Sofic approximation

Let 𝒢 n ∶= F κ n ⊂ Δ . In this subsection we build an injection from 𝒢 n to ℤ 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 Δ and obtain our injection. Thus when defining 𝒦 n we need to ensure that this last set contains enough possible lamp configurations to encode all possible values of x. The ideal thing to do would be to define an injection from 𝒢 n to F dn,in,jn . As we will see at the end of this section, the numbering process we use requires that we consider F dn,in,jn+1 instead of F dn,in,jn (see page 28 for a discussion of such a necessity). But when i n = 𝔩(d n -1) and j n = N in -1 the Følner we will work with actually verifies F dn,in,jn+1 = F dn+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 = ⎧ ⎨ ⎩ d n if j n < N in -1 and i n < 𝔩d n -1, d n + 1 else. (4.3)
Finally we define I n ∈ [0, 𝔩(D n -1)] and J n ≤ N In such that F Dn,In,Jn = F dn,in,jn+1 .

As explained above we have to extract information from 𝐟 and combine it with t to define the cursor (denoted u) in Δ. Recall that if (𝐟, t) is in 𝒢 n then t belongs to [0, κ n -1]. The idea is thus to split the interval [0, D n ] in subintervals of length κ n plus some remainder interval of length less than κ n . The extracted information from 𝐟 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 𝐟 and then how to define our integer encoding the remaining data of 𝐟.

Let us denote the Euclidean division of D n by κ n by

D n = Q n κ n + R n 0 ≤ R n < κ n .
(4.4)

Lemma 4.5

If ρ ∘ρ -1 bij (x) ≼ x 1-ε for some ε > 0 then the sequence (Q n ) n is unbounded. In particular there exists n 0 ≥ 0 such that for all n ≥ n 0 1. Q n ≥ 3; 2. D n ≥ d n > κ n . So up to consider (𝒢 n ) n≥n 0 instead of (𝒢 n ) n≥0 we can assume without loss of generality that Q n ≥ 3 for all n.

To prove this lemma we rely on the properties of ρ bij and ρ showed in appendix A.3.

Coupling between diagonal products

Proof. By Remark 2.9 and eq. (4.2)

C 3 κ n-1 l 𝔏(n) ≤ ln |𝒢 n | ≤ ln |F dn,in,jn |.
But by Proposition 2.8 there exists some constant C 2 > 0 such that ln |F dn,in,jn | is bounded by above by C 2 d n l 𝔩(dn-1) . Noting that d n is smaller than 2(d n -1) we obtain

κ n l 𝔏(n) ≤ 2κC 2 C 3 (d n -1) l 𝔩(dn-1) .
Now recall that by definition of 𝔩 we have k 𝔩(dn-1) ≤ d n -1 < k 𝔩(dn-1)+1 . Hence by Lemma A.16 we have ρ ( (d n -1)l 𝔩(dn-1)) = d n -1. Thus by Lemma A.19

κ n l 𝔏(n) ≤ 2C 2 κ C 3 ρ -1 bij (2(d n -1)) .
Using first that ρ (κ n l 𝔏(n) ) = κ n and second that ρ ∈ 𝒞 and thus verifies eq. (A.2) we obtain

κ n = ρ (κ n l 𝔏(n) ) ≤ max {1, 2C 2 κ/C 3 } ρ ∘ ρ -1 bij (2(d n -1)) .
But recall that ρ ∘ ρ -1 bij (x) ≼ x 1-ε . Hence κ n ≼ (d n -1) 1-ε and thus using eq. (4.4)

κ n ≼ d 1-ε n ≤ (Q n + 1) 1-ε κ n(1-ε) .
Therefore κ nε ≼ (Q n +1) 1-ε . Since the left term tends to infinity, so does Q n . In particular there exists n 0 such that Q n ≥ 3 for all n ≥ n 0 and

D n ≥ d n ≥ Q n κ n -1 ≥ 3κ n -1 > κ n .

Numbering in

Δ

Consider (𝐟, t) ∈ 𝒢 n and let us describe our encoding process. The first goal is to encode the information contained in 𝐟 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 𝐟 and use it to define the cursor in the second diagonal product Δ.

Recall that (𝐟, t) is uniquely determined by the value of t, of f 0 and (f ′ m ) m≥1 . Similarly as in Section 3.1 let t = ∑ n-1 i=0 t i κ i be the decomposition in base κ of t. Define for t ∈ [0, κ n -1] and i ∈ {0, … , n}:

Bi (t) ∶= [ n-1 ∑ j=i t j κ j , n-1 ∑ j=i t j κ j + κ i -1 ] . (4.5)
The conclusions of Lemma 3.1 apply to ( Bi (t) ) i . In particular we can define as before the following bijections:

ν 0 ∶ { ζ ∶ B0 (t) → A × B } → [ 0, q -1 ] , ∀i ≥ 1 ν i ∶ { ζ ∶ Bi (t)\ Bi-1 (t) → A × B } → [ 0, q κ i -κ i-1 -1 ] μ n ∶ { 𝐟 ′ | supp (f ′ m ) ⊆ [ k m , κ n -1 ] , ∀m ∈ [ 0, 𝔏(n) ]} → [ 0, |𝒢 n | κ n q κ n -1 ] .
Recall that Figure 6 represents the information encoded by each of these maps.

As explained above, we need to extract information from 𝐟 to define our cursor in Δ. To that end we denote the Euclidean division of μ n (𝐟 ′ ) by Q n by

μ n (𝐟 ′ ) = E n (𝐟 ′ )Q n + P n (𝐟 ′ ) 0 ≤ P n (𝐟 ′ ) < 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 ( b i) i and express our numbering in it (see appendix B for details on variable base).

b 0 = q ∀i ∈ [1, n] b i = q κ i -κ i-1 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 b i instead of b n,i . In this base we thus write

θ n (𝐟, t) ∶= ν 0 ( f 0| B0 (t) ) + n ∑ i=1 ν i ( f 0| Bi(t)\ Bi-1 (t) ) b i-1 ⋯ b 0 + E n (𝐟, t) b n ⋯ b 0 .
(4.7) Remark 4.6. Remark that this base differs from (β i ) i defined page 18 only from the last coefficient. In particular b i ⋯ b 0 = q κ i for all i ∈ [0, n]. The difference between the last coefficients comes from the extraction made in eq. (4.4).

We saw in Claim 3.4 that μ n was surjective onto [0, max μ n -1], but it does not necessarily imply that

(E n , P n ) is surjective onto the product [0, max(E n )] × [0, Q n -1]. Indeed unless max μ n equals ( max(E n ) + 1 ) Q n -1, some elements of {max(E n )} × [0, Q n -1]
might not be reached. This is what the next lemma specifies and what will lead to the definition of ℋ n given in eq. (4.17).

Lemma 4.7

The map sending (𝐟, t) to ( t, θ n (𝐟, t), P n (f ′ ) ) is a bijection from 𝒢 n to the set

[0, κ n -1]× ( [ 0, q κ n max(E n ) -1 ] × [ 0, Q n -1 ] ∪ [ q κ n max(E n ), max( θ n ) ] × [ 0, max μ n -Q n max E n] ) .
Proof. Let us first prove the injectivity. If ( t, θ n (𝐟, t), P n (f ′ ) ) equals ( t ′ , θ n (𝐠, t′), P n (g ′ ) ) then P n (f ′ ) = P n (g ′ ) and t = t′. Thus Bi (t) = Bi (t′) for all i and by unicity of the decomposition in variable base (see Lemma B.1)

ν 0 ( f 0| B0 (t) ) = ν 0 ( g 0| B0 (t) ) ν i ( f 0| Bi(t)\ Bi-1 (t) ) = ν i ( g 0| Bi(t)\ Bi-1 (t) )
.

and E n (𝐟) = E n (𝐠′). In particular μ n (𝐟 ′ ) = μ n (𝐠′) and thus 𝐟′ = 𝐠′, by bijectivity of μ n .

Similarly the bijectivity of the ν i 's implies that f 0 coincide with g 0 on

B0 (t) ∪ ∪ i ( Bi (t)\ Bi-1 (t) ) = [0, κ n -1].
Hence 𝐟 = 𝐠 and thus the injectivity. Now let t ∈ [0, κ n -1]. Recall that μ n is bijective onto [0, max μ n ]. Using eq. (4.6) we obtain that Q n E + P is smaller than max μ n for all P < Q n and all E < max(E n ). In particular for all such E and P there exists 𝐟 such that μ n (𝐟′) = EQ n +P. Now if E = max(E n ) then there exists 𝐟 such that μ n (𝐟′) = EQ n + P if and only if P ≤ max ν n -Q n max E n . Now, since the ν t,i and μ m are bijections, Lemma B.1 implies that the image of θ n (⋅, t) is the interval [0, max θ n ]. Consider x in this interval and write [x 0 , … , x n+1 ] b its decomposition in base ( b i ) i . If x < q κ n max(E n ) then x n+1 < max(E n ). In particular by the above study of im( μ n ) for all P ∈ [0, Q n -1] there exists 𝐟 ′ such that μ n (𝐟′) = x n Q n + P, that is to say P n (𝐟 ′ ) = P and E n (𝐟′) = x n . If x ≥ q κ n max(E n ) a similar argument as above gives that for all P smaller than max ν n -Q n max E n there exists 𝐟 ′ such that E n (𝐟′) = E and P n (𝐟 ′ ) = P. Finally, in both cases there exists f 0 such that x i = ν i ( f 0| Bi(t)\ Bi-1 (t) ) for all i. The element (𝐟, t) thus defined verifies θ n (𝐟, t) = x and P n (𝐟 ′ ) = P. Hence the surjectivity.

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

Bounds

In order to obtain the number of lamps in Δ needed to encode the information contained in θ n (𝐟, t), we need to estimate the maximal value taken by θ .

Why such a need? The "ideal" Følner set used to define ℋ n would have been F dn,in,jn but the encoding process we chose does not allow us to work with this set. Indeed assume for example that |F dn,in,jn | = |𝒢 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 𝐟 to define the cursor u in Δ. What we actually do when defining our map θ n is that we take a little "too much" information from the lamp configuration 𝐟 to define the integer θ n (𝐟, t) and thus we left "not enough" information to be used to define the cursor in Δ. Hence when defining our wanted embedding from 𝒢 n to F dn,in,jn , 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 dn,in,jn to encode all the values of θ n . What Lemma 4.8 shows is that F dn,in,jn+1 contains enough lamps configurations to allow us to encode the values of θ n in it.

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

Lemma 4.8

For n large enough

| F dn,in,jn-1 | /D n ≤ max (𝐟,t)∈𝒢n θ n (𝐟, t) + 1 ≤ | F dn,in,jn+1 | /D n .
But before proving the above statement, let us bound the value of b n+1 = max(E n ) + 1.

Lemma 4.9

For n large enough

| F dn,in,jn-1 | D n q κ n ≤ max(E n ) + 1 ≤ | F dn,in,jn+1 | D n q κ n

Coupling between diagonal products

Proof. Let n ∈ ℕ * . By eq. ( 4.6) we have

E n = ⌊ μ n /Q n⌋ , thus E n ≤ μ n /Q n ≤ E n + 1. Since max( μ n ) = |𝒢 n |/(κ n q κ n ) we hence have max(E n ) ≤ |𝒢 n | Q n κ n q κ n ≤ 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,

max(E n ) + 1 ≥ |𝒢 n | Q n κ n q κ n ≥ | F dn,in,jn-1 | Q n κ n q κ n ≥ | F dn,in,jn-1 | D n q κ n .
Now for the upper bound. By eq. ( 4.2) we know that |𝒢 n | ≤ | F dn,in,jn | , hence using the left part of eq. (4.8) we get that max(E n ) + 1 is less or equal to | F dn,in,jn | /(κ n Q n q κ n ) + 1. Now using the euclidean division given by eq. ( 4.4) we get

D n /(Q n κ n ) ≤ 1 + 1/Q n , thus max(E n ) + 1 ≤ | F dn,in,jn | κ n Q n q κ n + 1 ≤ | F dn,in,jn | D n q κ n ( 1 + 1 Q n ) + 1.
Using that Q n is unbounded (Lemma 4.5) we obtain that for n large enough max(E n )+1 ≤ 2 | F dn,in,jn | /(D n q κ n ). So up to consider (𝒢 n ) n≥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 | F dn,in,j n+1 | /D n to encode the information contained in the integer θ n (𝐟, t).

Proof of Lemma 4.8. . By eq. (4.7) and Lemma B.1 we have max( θ n ) + 1 = ∏ n+1 i=0 b i . Now recall (see Remark 4.6) that ∏ n i=0 b i = q κ n . Hence, max( θ n ) + 1 = (max E n + 1) q κ n . We conclude using the bounds given in Lemma 4.9. Now remark that | F dn,in,jn+1 | /D n is exactly the number of possible lamp configurations for elements in F dn,in,jn+1 . Hence by the above lemma we can define an embedding from [0, max θ n ] to the set of lamp configurations of elements in F dn,in,jn+1 .

We define

𝒦 n ∶= F dn,in,jn+1 = F Dn,In,Jn .

(4.9)

and now have to define and injection between 𝒢 n and 𝒦 n . Moreover using twice Lemma 2.7, we obtain

|𝒦 n | ≤ 2q | F dn,in,jn | ≤ 4q 2 | F dn,in,jn-1 | ≤ 4q 2 |𝒢 n |.

Injection between Sofic approximation

Let n ∈ ℕ and recall that 𝒢 n = F κ n and 𝒦 n = F dn,in,jn+1 . The purpose of this section is to define an injection ι n from 𝒢 n to 𝒦 n . Moreover we want that injection to be C-dense for some C > 0. Let (𝐟, t) ∈ 𝒢 n and denote by (𝐠, u) the image of (𝐟, t) by ι n . We first explicit the definition of the cursor u, then turn to the definition of 𝐠 and conclude by showing that ι n thus defined is injective and C-dense.

Cursor

Recall that the Euclidean division of D n by κ n is given by D n = Q n κ n + R n . As explained in the last section, the idea is to split [0, D n -1] in subintervals of length κ n (plus some remainder interval of length less than κ 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(𝐟, t) = P n (𝐟 ′ )κ 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(ι 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 ∈ [0, κ n ] and

P ∈ [0, Q n -1] u ∶= u(P, t) ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ Pκ n + t if P < Q n -1, Pκ n + 2t if P = Q n -1 and t < R n Pκ n + R n + t if P = Q n -1 and t ≥ R n .
(4.10a)

(4.10b) (4.10c)
We represent in Figure 9 the possible values of u when Q n = 4 and R n = 3. Claim 4.11. Let P ∈ [0, Q n -1], let t ∈ [0, κ n -1] and u be as defined in eq. (4.10). Then

κ n R n unreached cursors κ n 2κ n (Qn -1)κ n 4κ n D n Q n κ n reached cursors …
u(P, t) ∈ [0, D n -1].
In particular u (P n (𝐟 ′ ), t) ∈ [0, D n -1] for all (𝐟, t) ∈ 𝒢 n .

Proof. First recall that we always have t < κ n . Now if P < (Q n -1) then

u(P, t) = Pκ n + t ≤ (Q n -1)κ n + κ n -1 ≤ D n If P = Q n -1 and t < R n then u(P, t) = (Q n -1)κ n + 2t < (Q n -1)κ n + R n + κ n -1 = Q n κ n + R n = D n .
Finally in the last case we get u(P, t) = (Q n -1)κ n +R n +t < (Q n -1)κ n +R n +κ n = D n .

Numbering in Δ

For now we have an integer θ n (𝐟, t) and a cursor u ( P n (𝐟 ′ ), t ) defined above. Our goal is to associate to θ n (𝐟, t) a lamp configuration sequence 𝐠 in Δ supported on [0, D n -1]. For each value of u(𝐟, t) we are going to define a map between the set of lamp configurations contained in 𝒦 n and the interval [0, |𝒦 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 ℬ i depending on the cursor u ( P n (𝐟 ′ ), t ) -that is to say depending on P n (𝐟 ′ ) and t-such that |ℬ i | ∼ κ i , the last interval of the sequence is [0, D n -1] and ℬ i verifies Claim 3.8. The idea would thus be similar to the one used in the definition of ( Bi ) 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, κ n -1] so we will need more than n + 1 nested intervals and as we will see in eq. (4.13) we will have to be careful when defining ℬ 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 κ n . Then all cursors in [0, D n -1] are reached by u. We start by defining ∀i ∈ [0, n] ℬ ′ i (P, t) ∶= Pκ n + Bi (t).

(4.11)

That is to say ℬ ′ i (P, t) corresponds to the nested sequence of intervals Bi (t) shifted by Pκ n . In particular ℬ ′ n (P, t) = [Pκ n , (P + 1) κ n -1]. We now have to define the bigger blocs ℬ ′ 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 ℬ ′ n (P, t) would be the interval

[(Q n -1)κ n , Q n κ n -1]. Which can also be written as [D n -κ n , D n -1], since D n = Q n κ n .
To obtain the next terms of the sequence ℬ ′ i (represented in Figure 10a) we could then consider

ℬ ′ i (P, t) = [D n -κ i , D n -1] that is to say [(P + 1)κ n -κ 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 10b). In that case we thus set the lower bound to 0 and the upper bound to κ i -1 (see eq. (4.13)). Now for the formal definition. Let p n ∈ ℕ be such that κ pn-1 < D n ≤ κ pn (4.12) let ℬ ′ pn (P, t) ∶= [0, D n -1] namely ℬ ′ pn (P, t) ∶= [0, Q n κ n -1] and set for all i ∈ [n + 1, p n -1]

ℬ ′ n+2 (t) ℬ ′ n+1 (t) ℬ ′ n(t) 0 (Qn -1)κ n Qnκ n (a) P = Q n -1 ℬ ′ n+2 (t) ℬ ′ n+1 (t) ℬ ′ n(t) 0 (Qn -1)κ n Pn(𝐟 ′ )κ n (Pn (𝐟 ′ ) + 1) κ n Qnκ n (b) P < Q n -1
ℬ ′ i (P, t) = ⎧ ⎨ ⎩ [ (P + 1) κ n -κ i ; (P + 1) κ n -1 ] if P + 1 ≥ κ i-n , [ 0, κ i -1 ]
else. (4.13) Lemma 4.12

The sequence (ℬ ′ i (P, t)) i defined by eqs. (4.11) and (4.13) verifies ℬ ′ i (P, t) ⊂ ℬ ′ i+1 (P, t) for all i < p n . In particular

{Pκ n + t} = ℬ ′ 0 (P, t) ⊂ ℬ ′ i (P, t) ⊆ ℬ ′ pn (P, t) = [0, Q n κ n -1],
Proof. Recall that B0 (t) = {t}. Thus ℬ ′ 0 (𝐟, t) = {Pκ n + t} by eq. (4.11). Since we assumed R n = 0 we get D n = Q n κ n and thus ℬ ′ pn (P, t) = [0, Q n κ n -1]. Let us now prove that

ℬ ′ i (P, t) ⊂ ℬ ′ i+1 (P, t) for all i < p n . • If i < n the inclusion comes Lemma 3.1. • If i = n then ℬ ′ n (P, t) = [Pκ n , (P + 1)κ n -1]. If (P + 1) < κ then in that case ℬ ′ n+1 (P, t) = [0, κ n+1 -1].
Since Pκ n is positive and by the last assumption (P + 1)κ n is smaller than κ n+1 we thus obtain the inclusion. For the second case, first remark that κ n -κ n+1 < 0 and thus (P + 1)κ n -κ n+1 is smaller than Pκ n . Hence when (P + 1) ≥ κ we get ℬ ′ n (P, t) = [ P n κ n , ( P + 1 ) κ n -1 ] ⊆ [( P + 1 ) κ n -κ n+1 , ( P + 1 ) κ n -1 ] = ℬ ′ n+1 (P, t).

• Assume that i > n. If (P + 1) ≥ κ i+1-n then (P + 1) ≥ κ i-n and thus

ℬ ′ i (P, t) = [ Pκ n -κ i , ( P + 1 ) κ n -1 ] ⊆ [( P + 1 ) κ n -κ i+1 , ( P + 1 ) κ n -1 ] = ℬ ′ i+1 (P, t)
.

If (P + 1) < κ i+1-n then ℬ ′ i+1 (P, t) = [0, κ i+1 -1].
Then either (P + 1) < κ i-n thus ℬ ′ i (P, t) = [0, κ i -1] and the inclusion comes immediately, or (P + 1) ≥ κ i-n . In this case (P + 1)κ n -κ i is positive, moreover since (P + 1) is assumed to be smaller than κ i+1-n we have (P + 1)κ n ≤ κ i+1 . That is to say

ℬ ′ i (P, t) = [( P + 1 ) κ n -κ i , ( P + 1 ) κ n -1 ] ⊆ [ 0, κ i+1 -1 ] = ℬ ′ 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 χ from [0, D n -1] to [0, Q n κ n -1] and then use it to define our blocs ℬ i (P, t) in [0, D n -1] as the preimages of the "ideal" blocs ℬ ′ i (P, t).

Figure 11 represents the map χ and Lemma 4.13 formalizes its definition.

Lemma 4.13

Consider v ∈ [0, D n -1]. • If v = u(P, t) for some (P, t) ∈ [0, Q n -1]×[0, κ n -1] then define χ(v) ∶= P n (𝐟 ′ )κ n +t. • If v ∉ im(u) then (v -1) ∈ im(u) and we define χ(v) ∶= χ(v -1). Then χ ∶ [0, D n -1] → [0, Q n κ n -1]
is a well defined surjective map. Moreover for any interval I ⊆ [0, Q n κ n -1] the pre-image χ -1 (I) is also an interval and it verifies

|χ -1 (I)| ≤ 2|I|.
Proof. If v ∈ im(u) there exists a unique (P, t) ∈ [0, Q n -1] × [0, κ n -1] such that u(P, t) = v.Moreover, since P belongs to [0, Q n -1] and t to [0, κ n -1] then Pκ n + t belongs to 4 Coupling between diagonal products

R n unreached cursors 0 κ n 2κ n (Qn -1)κ n 4κ n D n κ n 2κ n (Qn -1)κ n 4κ n χ • • • • • • • • • Figure 11: Map χ [0, Q n κ n -1]. Hence χ is well defined. It is also surjective. Finally consider y ∈ [0, Q n κ n -1] then χ -1 (y) contains either 1 or 2 consecutive elements in [0, D n -1]. Thus |χ -1 (I)| ≤ 2|I|
and χ -1 (I) is an interval, since χ preserves the order.

We now define ℬ i (P, t) as the pre-image of the ideal bloc ℬ ′ i (P, t). The following lemma comes immediately from Lemmas 4.12 and 4.13. Lemma 4.14

Let (P, t) ∈ [0, Q n -1] × [0, κ n -1]
and consider the sequence (ℬ ′ i (P, t)) i as defined by eqs. (4.11) and (4.13). Let ∀i ∈ [0, p n ] ℬ i (P, t) ∶= χ -1 ( ℬ ′ i (P, t) ) .

The sequence (ℬ i (P, t)) i thus defined verifies ℬ i (P, t) ⊂ ℬ i+1 (𝐟, t) for all i < p n . In particular u(P, t) ∈ ℬ 0 (P, t) ⊂ ℬ i (P, t) ⊆ ℬ pn (P, t) = [0, D n -1],

and thus u(P, t) belongs to ℬ i (P, t) for all i ≤ p n .

Remark 4.15. Lemma 4.13 implies that κ i ≤ |ℬ i (P, t)| ≤ 2κ 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 page 17, except that here the variable base used to associate a number to a lamp configuration depends on the value of the cursor u ( P n (𝐟 ′ ), t ) = v. Now consider (𝐠, v) such that v belongs to the image of u and let P ∈ [0, Q n -1] and t ∈ [0, κ n ] such that u(P, t) = v. Remark that for all i ∈ [1, p n + 1], the number of maps of the form ζ ∶ ℤ → A × B supported on ℬ i (P, t)\ℬ i-1 (P, t) is equal to q |ℬi(P,t)\ℬ i-1 (P,t)| . Hence we can define applications

ν 0,P,t ∶ {ζ ∶ ℬ 0 (P, t) → A × B} → [ 0, q -1 ] ,
∀i ∈ [1, p n ] ν i,P,t ∶ {ζ ∶ ℬ i (P, t)\ℬ i-1 (P, t) → A × B} → [ 0, q |ℬi(P,t)\ℬi-1(P,t)| -1 ] ,

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 ν i instead ν i,P,t to simplify the notations. We now have to number (g ′ m ) m∈[1,𝔩(Dn-1)] . Let us first make a general remark on F Dn,In,Jn . We refer to Figure 12 for an illustration. Recall that 𝔩(D n -1) is defined as

𝔩(D n -1) = max{m ∶ k m ≤ D n -1}.
In particular (see Section 4.2.2) if k 𝔩(Dn-1) = D n -1 and

(𝐠, t) belongs to F Dn then g ′ 𝔩(Dn-1) is supported on {k 𝔩(Dn-1) }. Therefore if I n < 𝔩(D n -1), an element (𝐠, t) of F Dn,In,Jn verifies g ′ 𝔩(Dn-1) ≡ e. Thus 𝐠 is only determined by g 0 and

(g ′ m ) m≤𝔩(Dn-1)-1 . We thus define We thus are actually going to number (g ′ m ) m≤Mn . But we will need a more refined numbering than the one defined in Section 4.1.2.

M n ∶= ⎧ ⎨ ⎩ 𝔩(D n -1) -1 if k 𝔩(Dn-1) = D n -
Why refine the numbering? Consider (𝐟, t) in 𝒢 n and denote (𝐠, u) ∶= ι n (𝐟, t). While the action of a generator s on (𝐟, 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 θ n (𝐟, t). Hence it can modify the image (𝐠, u) by the values of 𝐠 ′ and not just g 0 . When it happens, if we encode the information of 𝐠 ′ in one digit as in Section 4.1.2 then the best bound we can obtain on the distance between (𝐠, u) = ι n (𝐟, t) and ι n( (𝐟, t)s ) will be diam (ℋ n ). Furthemore we can show that the proportion of such elements is about q -Dn . Hence when checking the condition given by eq. (2.1) we will obtain an unbounded sum since diam (𝒦 n ) is much bigger than q Dn . To overcome this, we refine the numbering such that the more terms we modify in 𝐠 ′ (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 ∈ [1, I n -1], there exists a bijection

μ m ∶ { h ′ m ∶ ℤ → Γ ′ m | supp(h ′ m ) ⊆ [k m , D n -1] } → [ 0, |Γ ′ m | Dn-km -1 ] .
Similarly for the I n -th element we have a bijection

μ In ∶ { h ′ m ∶ ℤ → Γ ′ m | supp(h ′ In ) ⊆ [k In , D n -1] and h ′ In (D n -1) ∈ Λ In Jn } → [ 0, |Γ ′ m | Dn-kI n -1 | Λ In Jn | -1 ] .
Finally for all m ∈ [I n + 1, M n ], there exists a bijection

μ m ∶ { h ′ m ∶ ℤ → Γ ′ m | supp(h ′ m ) ⊆ [k m , D n -2] } → [ 0, |Γ ′ m | Dn-km-1 -1 ] .
We represent in Figure 13 the numbering defined so far.

Let us now define the variable base (b i,P,t ) i . We reproduce the idea used in the definition of ( b i ) i with two changes: first |ℬ i (P, t)\ℬ i-1 (P, t)| depends on P and t so we cannot replace it by its numerical value as we did for b i , second the numbering of 𝐟 ′ contains here more than one term. Remark that ∏ pn i=0 b i,P,t = q Dn and thus this product does not depend on (P, t). Before defining our map ϑ n let us show some useful result about the base we just introduced.

Lemma 4.16

For all P ∈ im(P n ) and all t ∈ [0, κ n -1] let (b i,P,t ) i be the base defined above.

• For all i < p n it verifies b i,P,t ⋯ b 0,P,t ∈ [q κ i , q 2κ i ]. Moreover for all j ∈ [1, i -1] q κ i -2κ j-1 ≤ i ∏ k=j b k,P,t ≤ q 2κ i -κ j-1 .

• If i = p n then b i,P,t ⋯ b 0,P,t = q Dn and for all j ∈ [1, i -1] we have b i,P,t ⋯ b j,P,t ≥ q Dn-2κ j . • For all i > p n we have b i,P,t ⋯ b 0,P,t ≥ q Dn exp(l i-pn ) and for all j ∈ [1, i -1] have b i,P,t ⋯ b j,P,t ≥ q Dn-2κ j exp(l i-pn ).

Proof. First consider i < p n . By Lemma 4.13 ℬ i (P, t) contains at most 2|ℬ ′ i (P, t)| elements and at least |ℬ ′ i (P, t)| elements. But |ℬ ′ i (P, t)| = κ i , the first assertion of the lemma thus comes by noting that b i,P,t ⋯ b 0,P,t is equal to q |ℬi(P,t)| . For the second assertion, remark that b i,P,t ⋯ b j,P,t equals q |ℬi(P,t)\ℬ j-1 (P,t)| . Moreover by Lemma 4.14 the interval ℬ j-1 (P, t) is included in ℬ i (P, t) thus |ℬ i (P, t)\ℬ j-1 (P, t)| is equal to |ℬ i (P, t)| -|ℬ j-1 (P, t)|. Hence the first point.

If i = p n then |ℬ i (P, t)| = D n and a similar argument as above implies that b i,P,t ⋯ b 0,P,t equals q Dn and b i,P,t ⋯ b j,P,t ≥ q Dn-2κ j for all j ∈ [1, i -1].

Finally if i > p n note that b i,P,t ⋯ b j,P,t is greater than b i,P,t b pn,P,t ⋯ b 0,P,t . But note that by eq. (4.14), for all m ≤ M n we have k m < D n -1. Therefore for all p n < i ≤ p n + M n b i,P,t ≥ |Γ ′ i-pn | Dn-1-ki-p n ≥ |Γ ′ i-pn | ∼ exp(l i-pn ).

Hence b i,P,t b pn,P,t ⋯ b 0,P,t is greater than exp(l i-pn )q Dn . The last assertion is similarly obtained by bounding b pn,P,t ⋯ b i,P,t by below by q Dn-2κ i . Hence 𝔞 n ≤ 4q 2 + 1 ≤ q 3 . Proof of Lemma 4.18. First let 𝔟 n ∶= max(ϑ n ) -𝔞 n max θ n and remark that it belongs to ℕ. Now let

𝔰 n ∶ x ↦ ⎧ ⎨ ⎩ (𝔞 n -1)x if x < -𝔟, 𝔞 n x + 𝔟 n if x ≥ -𝔟.
By definition 𝔰 n is 𝔞 n -Lipschitz and hence by Claim 4.19 it is (q 3 )-Lipschitz. Moreover, since 𝔟 n , 𝔞 n and (𝔞 n -1) are integers then 𝔰 n maps any integer to an integer. Finally we can check easily that 𝔰 n (max θ n ) = max ϑ n .

We can now define the "spreading" version of θ n θn (𝐟, t) ∶= 𝔰 n ∘ θ n (𝐟, t).

(4.16)

Hence (𝐠, u ( P n (𝐟′), t ) ) belongs to ℋ n by eq. (4.17). • Finally if there exists 𝐠 such that θn (𝐟, t) = ϑ n ( 𝐠, u ( P n (𝐟′), t )) then it is unique since ϑ n (⋅, v) is injective for any v in the image of u (see Lemma 4.17). Let us now prove the injectivity of ι n . Let (𝐟, t), (𝐡, v) ∈ 𝒢 n such that ι n (𝐟, t) = ι n (𝐡, v). Then u(𝐟, t) = u(𝐡, v) and if we denote 𝐠 the element such that (𝐠, u(𝐟, t)) = ι n (𝐟, t) we thus get θ(𝐟, t) = ϑ n (𝐠, u(𝐟, t)) = θ(𝐡, v).

• If u(𝐟, t) = u(𝐟, v) then χ ∘ u(𝐟, t) = χ ∘ u(𝐟, v) and thus

(P n (𝐟 ′ ) -P n (𝐡 ′ )) κ n = v -t.
But 0 ≤ t, v < κ n , the above equation thus leads to t = v and P n (𝐟 ′ ) = P n (𝐡′). • Let us now prove that 𝐟 ′ = 𝐡 ′ . Since 𝔰 n is a piecewise affine map then θ(𝐟, t) = θ(𝐡, v)

implies that θ n (𝐟, t) = θ n (𝐡, v). In particular the coefficients of the decomposition of θ n (𝐡, v) in base ( b i) i are equal to the one of the decomposition of θ n (𝐟, t). In other words ν t,i (𝐟, t) = ν v,i (𝐡, v) and E n (𝐟′) = E n (𝐡′).

(4.18)

But by the last claim P n (𝐟 ′ ) = P n (𝐡′) thus μ n (𝐟′) = μ n (𝐡′). Since μ n is bijective it implies that 𝐟 ′ = 𝐡 ′ . • Moreover the fact that t equals v implies that for all i ∈ [0, n]

Bi (t) = Bi (v),
In particular ν t,i is defined on the same set as ν v,i . Combining this with the bijectivity of these maps and eq. (4.18) we thus get that f 0 = h 0 . Since 𝐟 (resp. 𝐡) is uniquely determined by f 0 (resp. h 0 ) and 𝐟 ′ (resp. 𝐡 ′ ) we thus have 𝐟 = 𝐡. Hence the injectivity of ι n . Now let us show the density. Let (𝐡, v) ∈ ℋ n . We need to distinguish two cases depending on whether v belongs to im(u) or not.

• Since v ∈ [0, D n -1] there exists P ∈ [0, Q n -1] and t ∈ [0, κ n -1] such that χ(v) =

Pκ n + t.

• If v ∈ im(u) (resp. v ∉ im(u)) denote by [y 0 , … , y pn+Mn ] 𝐛 the decomposition in base (b i,P,t ) i of ϑ n (𝐡, v) (resp. ϑ n (𝐡, v + 1)). Now by Lemma 4.5 if n is large enough, D n > κ 3 , hence b 0,P,t , b 1,P,t and b 2,P,t are well defined. Moreover q = 6 (see page 51) and κ ≥ 3, hence for all such n we always have b 0,P,t b 1,P,t b 2,P,t = q κ 2 ≥ q 9 > q 3 . So up to consider (𝒢 n 1 +n ) n∈ℕ instead of (𝒢 n ) n for some n 1 ≥ 0, we can assume that the above inequality is true for all n. Now, since 𝔰 n is q 3 -Lipschitz, Lemma B.6 implies that there exists x ∈ im( θn ) such that x j = y j for all j > 2 where x = [x 0 , … , x pn+Mn ] 𝐛 denotes the decomposition of x in base (b i,P,t ) i . • Since (𝐡, v) belongs to ℋ n then by eq. (4.17) the triple ( t, P, 𝔰 -1 n (x) ) belongs to the set defined at the end of Lemma 4.7. The aforementioned lemma thus implies that there exists (𝐟, t) ∈ 𝒢 n such that P n (𝐟 ′ ) = P and θ n (𝐟, t) = 𝔰 -1 n (x) that is to say

ϑ n ∘ ι n (𝐟, t) = x.
• Let (𝐠, u(𝐟, t)) ∶= ι n (𝐟, t) and assume first that v belongs to the image of u. Then u(𝐟, t) = v by definition of χ the first point. Moreover by definition of the numbering ϑ n and since x j = y j for all j > 2, the lamp configuration 𝐡 differs at most from 𝐠 from the values of h 0|ℬ 2 (v) . But ℬ 2 (v) is an interval containing the cursor v and which contains at most 2κ 2 elements. Thus by Proposition A.22 the distance between (𝐠, v) and (𝐡, v) is bounded by 2κ 2 up to some multiplicative constant. Now if v ∉ im(u), by a similar argument we can show that (𝐠, u) and (𝐡, v + 1) are at distance at most 2κ 2 and thus (𝐠, u) and (𝐡, v) are at distance at most 2κ 2 + 1 from one another. This shows that ι n is C-dense for C equals to 2κ 2 + 1. Hence the proposition.

Quantification

Now that we have defined the injection between our Sofic approximations we need to show that eq. (2.1) is verified. Although some technicalities appear in the details of the computations, the strategy is quite similar to the one used in Section 3.2. So for (𝐟, t) ∈ 𝒢 n and s ∈ 𝒮 Δ we first bound the distance between ι n (𝐟, t) and ι n( (𝐟, t)s ) . Then for a given r > 0 we provide an estimate of the proportion of elements in 𝒢 n such that ι n (𝐟, t) and ι n( (𝐟, t)s ) are at distance r in Δ. Finally we show that eq. (2.1) is verified.

Distance

Let s ∈ 𝒮 Δ and (𝐟, t) ∈ 𝒢 (1) n . Our aim in this section is to bound by above the distance between ι n (𝐟, t) and ι n( (𝐟, t)s ) . We will distinguish two cases depending on s = (0, 1) or not. But first let us introduce some notations. As in Section 3 let t = ∑ n-1 i=0 t i κ i be the decomposition in base κ of t. If (𝐟, t) belongs to 𝒢 (1) n then t < n -1 and thus there exists i ∈ {0, … , n -1} such that t i < κ -1. Therefore, as in eq. (3.2) we can define

i 0 (t) ∶= min{i ≤ n | t i < κ -1}. (4.19)
Recall that this index corresponds to the one of the coefficient t i that will absorb the carry when we add one to t. In other words, the decomposition of t + 1 in base κ is given by t + 1 = (t i 0 (t) + 1)κ i 0 (t) + ∑ n-1 i=i 0 (t) t i κ i . In particular we can obtain the following analogue of Claim 3.8.

Lemma 4.22

Let P ∈ [0, Q n -1] and t ∈ [0, κ n -1]. Then Bi (t) = Bi (t + 1) and ℬ i (P, t) = ℬ i (P, t) for all i > i 0 (t).

Proof. The first assertion comes from Claim 3.8. Now for the second one. Since ℬ i (P, t) is the preimage by χ of ℬ ′ i (P, t) we only have to show that ℬ ′ i verifies ℬ ′ i (P, t) = ℬ ′ i (P, t + 1).

This equality is true if i > n, since the definition given in eq. (4.13) of ℬ ′ i (P, t) does not depend on t. When i ∈ [i 0 (t) + 1, n], it is given by the first assertion and eq. (4.11). Hence the lemma.

Now define

x ∶= x(𝐟, t, s) = min { θ(𝐟, t), θ( (𝐟, t)s ) } , y ∶= y(𝐟, t, s) = max { θ(𝐟, t), θ( (𝐟, t)s ) } .

(4.20)

In this section we denote P ∶= P n (𝐟′). Recall that (b i,P,t ) i∈[0,pn+Mn] is the base defined in the box page 34 and denote by (x i ) i (resp. (y i ) i ) the decomposition of x (resp. y) in base (b i,P,t ) i . In other words using the notation introduced in appendix B these sequences verify x = [x 0 , … , x pn+Mn ] 𝐛P,t and y = [y 0 , … , y pn+Mn ] 𝐛P,t . Finally for i in [0, p n + M n ] define j P,t (x, i) ∶= min { j > i | x j < b j,P,t -1 } .

( if s ∈ 𝒮 1 ∪ 𝒮 2 or ( s = (0, 1) and i 0 (t) = 0 ) j P,t (x, i 0 (t) + 1) if s = (0, 1) and i 0 (t) > 0.

If m ≤ p n then d ( ι n (𝐟, t), ι n( (𝐟, t)s )) ≤ 6κ m . If m ≥ p n + 1 then d ( ι n (𝐟, t), ι n( (𝐟, t)s )) ≼ D n l m-pn .

Strategy of the proof

The injection ι n is defined using the two maps θn and ϑ n which transform lamp configurations into integers. In order to estimate the distance between ι n (𝐟, t) and ι n( (𝐟, t)s ) we thus need to understand how the action of s modifies these integers and in particular how it acts on their decompositions in base (b i,P,t ) i . Hence in a first paragraph we bound the difference between the θ(𝐟, t) and θ ((𝐟, t)s) (see Lemma 4.24). In the second one we use this bound to compare the decompositions in base (b i,P,t ) i of these two integers (see Claim 4.27) and conclude with the proof of the above proposition.

FrOM LAMPS TO INTEGErS

For all this section let ( f, t

) ∶= (𝐟, t)s. The aim in this paragraph is to show the lemma below.

Lemma 4.24

Let s ∈ 𝒮 Δ and i 0 (t) as in eq. (3.2). Denote P ∶= P n (𝐟′), then if s ∈ 𝒮 1 ∪ 𝒮 2 or ( s = (0, 1) and i 0 (t) = 0 ) b 0,P,t ⋯ b i 0 (t)+1,P,t else.

Before proving the lemma, let us prove some useful results. Recall that μ m is defined in Claim 3.4 and P n and E n are defined in eq. (4.6).

Claim 4.25. Recall that ( f, t

) ∶= (𝐟, t)s. These elements verify μ n (𝐟 ′ ) = μ n( f′ ) . In particular P n (𝐟 ′ ) = P n( f′ ) and E n (𝐟 ′ ) = E n( f′ ) .

Proof of the claim. If s = (0, 1) then s only modifies the cursor of (𝐟, t). That is to say 𝐟 = f. Hence the first equality.

If s = ( (aδ 0 ) m , 0 ) for some a ∈ A, then fm = f m aδ t for all m > 0. In particular for all

x ≠ t it verifies fm (x) = f m (x). Using Lemma A.6 at x = t we obtain

fm (t) = f m (t)a = f ′ m (t)θ A m( f 0 (t) ) θ B m( f 0 (t -k m ) ) a, = f ′ m (t) ( θ A m (f 0 (t))a ) θ B m( f 0 (t -k m ) ) .
By uniqueness of the decomposition we thus get f′ m (t) = f ′ m (t). Hence f′ m = f ′ m for all m > 0 and thus μ n (𝐟 ′ ) = μ n( f′ ) . Finally the case when s = ( (bδ km ) m , 0 ) for some b ∈ B is identical to the one above. In all cases, the second part of the lemma comes immediatly from eq. (4.6).

Proof of the claim. Recall that by definition of j P,t it verifies j P,t (z, i + 1) > i + 1 for all i. So if m ≤ 2 then i + 1 ≥ m -1 for all i ≥ 0 and therefore Z m,i is empty. Similarly it is also empty for all m > 2 and all i ≥ m -1. Now assume that m > 2 and 0 < i < m -1 (we will treat the case i = 0 separately). Fix P ∈ [0, Q n -1] and t ∈ [0, κ n -1] such that i 0 (t) = i. By a similar argumentation as the one used to prove Lemma 4.28 we get | { (𝐟, t) ∈ 𝒢 n | P n (𝐟 ′ ) = P, j P,t( θn (𝐟, t

), i + 1 ) = m } | ≤ | { z ∈ [0, max ϑ n ] | j P,t( z, i + 1 ) = m } | , ≤ |𝒦 n |/D n (b m-1,P,t ⋯ b i+2,P,t ) -1 .
If m ≤ p n , Lemma 4.16 implies that (b m-1,P,t ⋯ b i+2,P,t ) -1 is less or equal to q 2κ i+1 -κ m-1 . Note furthermore that the number of t in [0, κ n -1] verifying i 0 (t) = i is less than κ n-i . Using these two remarks and then that Q n κ n ≤ D n , we get

|Z m,i | ≤ ∑ P∈[0,Qn-1] ∑ t, i 0 (t)=i | { (𝐟, t) ∈ 𝒢 n | P n (𝐟 ′ ) = P i 0 (t) = i j P,t( θn (𝐟, t), 2 ) = m } | ≤ ∑ P∈[0,Qn-1] ∑ t, i 0 (t)=i |𝒦 n |/D n q 2κ i+1 -κ m-1 ≤ Q n κ n-i |𝒦 n |/D n q 2κ i+1 -κ m-1 ≤ κ -i |𝒦 n |q 2κ i+1 -κ m-1
For the other values of m, replacing q 2κ i+1 -κ m-1 in the above inequalities by the corresponding value of (b m-1,P,t ⋯ b 0,P,t ) -1 we obtain the claim for i > 0.

Finally when i = 0, replacing b i+2,P,t by b 3,P,t in the argument above, we obtain the second part of the claim. Now assume that m ≤ n + 1 then Claim 4.30 implies

|X s m | = m-2 ∑ i=0 |Z n+1,i | ≼ κ -(m-2) |𝒦 n | + m-3 ∑ i=0 |𝒦 n |κ -i q 2κ i+1 -κ m-1 = κ -(m-2) |𝒦 n | + |𝒦 n |q -κ m-1 m-2 ∑ i=0 κ -i q 2κ i+1 .
But the sum on the right is equivalent to its last term, namely κ m-3 q 2κ m-2 . Recall moreover that κ ≥ 3 thus 2κ m-2 is strictly smaller than κ m-1 and hence q 2κ m-2 -κ m-1 ≤ 1. Thus

|X s m | ≼ κ -(m-2) |𝒦 n | + κ m-3 q 2κ m-2 -κ m-1 |𝒦 n |, ≼ κ -(m-2) |𝒦 n | + κ m-3 |𝒦 n | ∼ κ -m |𝒦 n |. Assume now that n + 1 < m ≤ p n . Then any i ∈ [0, n -1] verifies i + 2 < m thus using Claim 4.30 we get |X s m | = n-1 ∑ i=0 |Z m,i | ≼ n-1 ∑ i=0 |𝒦 n |κ -i q 2κ i+1 -κ m-1 .
As before, the sum ∑ n-1 i=0 κ -i q 2κ i+1 being equivalent to its last term we obtain that |X s m | is equivalent to |𝒦 n |κ -n q 2κ n -κ m-1 . Similarly if m = p n + 1 Claim 4.30 implies that

|X s m | ≼ n-1 ∑ i=0 κ -i |𝒦 n |q 2κ i+1 -Dn ∼ κ -n |𝒦 n |q 2κ n -Dn .
Finally if m > p n + 1 a similar proof gives

|X s m | ≼ n-1 ∑ i=0 κ -i |𝒦 n |q 2κ i+1 -Dn exp ( -l m-1-pn ) , ∼ κ -n |𝒦 n |q 2κ n -Dn exp ( -l m-1-pn ) .

Integrability

To goal of this subsection is to prove Theorem 1.18 and its precised version Theorem 4.1. We prove that the sequences (𝒢 n ) n and (ℋ n ) n defined before verify the condition of eq. (2.1) with φ = ρ ∘ ρ -1 bij . To do so we first treat the case when s belongs to 𝒮 1 ∪ 𝒮 2 and then the case when s = (0, 1).

Proof of Theorem 4.1. Consider Δ and Δ verifying the conditions (F) page 22 and assume that the sequence l m exp(-l m-1 ) is summable and that there exists

ε > 0 such that ρ ∘ ρ -1 bij (x) ≼ x 1-ε .
Let (𝒢 n ) n and (ℋ n ) n as defined respectively in Section 4.1 and eq. (4.17 In particular if we denote by r ∶= d ( ι n (𝐟, t), ι n( (𝐟, t)s )) we obtain that φ(r) ≼ φ(κ m ) when m ≤ p n and φ(r) ≼ φ(D n l m-pn ) for m ≥ p n + 1. Hence

R ∑ r=0 φ (r) | { (𝐟, t) ∈ 𝒢 (1) n | d ℋn (ι n (𝐟, t), ι n ((𝐟, t) ⋅ s)) = r } | |𝒢 n | ≼ pn ∑ m=0 φ(κ m ) |X s m | |𝒢 n | + φ(κ pn ) |X s pn+1 | |𝒢 n | + pn+Mn ∑ m=pn+1 φ ( D n l m-pn ) |X s m | |𝒢 n | .
(4.25)

We are going to study two different cases, depending on whether s = (0, 1) or not and study each of the three terms above separately.

FIrST cASE

Let n ∈ ℕ and R > 0 and first assume that s ∈ 𝒮 1 ∪ 𝒮 2 . We use Lemma 4.28 to bound

(κ m ) |X s m | |𝒢 n | ≼ φ(κ m ) |𝒦 n |q -κ m-1 |𝒢 n | ∼ φ(κ m )q -κ m-1 ≼ κ m(1-ε) q -κ m-1 .
Note that this last term is a summable sequence. Moreover if m < 2 then |X s m | is equal to zero, hence |𝒢 n | , ∼ φ(D n l m-pn )q -Dn exp ( -l m-1-pn ) , ≼ D n l m-pn q -Dn exp ( -l m-1-pn ) .

But D n /q Dn ≤ 1 and by assumption the sequence l m-pn exp ( -l m-1-pn ) is summable, hence The right most sum being a constant that does not depend on n nor on R.

If m = p n + 1 then using also eq. (4.12) we get

φ (κ pn ) |X s pn+1 | |𝒢 n |
≼ κ pn(1-ε) q -Dn ≼ κ pn q -κ pn ≼ 1.

Hence all three terms of the left side of eq. (4.25) can be bounded by a constant that does not depend on n nor on R and thus eq. (2.1) is verified for s ∈ 𝒮 1 ∪ 𝒮 2 .

SEcOND cASE

Assume now that s = (0, 1). Using Lemma 4.29 and Remark 4.10 we get

|X s m | |𝒢 n | ≼ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ κ -m
if m ≤ n + 1, κ -n q 2κ n -κ m-1 if n + 1 < m ≤ p n , κ -n q 2κ n -Dn if m = p n + 1. κ -n q 2κ n -Dn exp ( -l m-1-pn ) if m > p n + 1.

Thus for all m ≤ n + 1 we have φ(κ m )|X s m |/|𝒢 n | ≼ κ m(1-ε) κ -m = κ -εm . But (κ -εm ) m is a summable sequence, we can thus bound by above the value of ∑ Now for all n + 1 < m ≤ p n we have φ(κ m )|X s m |/|𝒢 n | ≼ κ m(1-ε) κ -n q 2κ n -κ m-1 . Let us prove that this last term is summable and give a bound which does not depend on n. Note first that κ ≥ 3 and m -n -1 ≥ 1 imply that 2 -κ m-n-1 < 0. Therefore q 2κ n -κ m-1 = ( q κ n ) 2-κ m-1-n ≤ q 2-κ m-1-n ∼ q -κ m-1-n .

(4.26) Thus pn ∑ m=n+2 κ m(1-ε)-n q 2κ n -κ m-1 ≤ pn ∑ m=n+2 κ m-n q -κ m-1-n ≤ +∞ ∑ m=1 κ m+1 q -κ m < +∞.

Note that the right most sum does not depend on n nor on R.

Example A.4. Assume that k m = 2 m and consider first the element (𝐟, 0) of Δ defined by (𝐟, 0) ∶= (0, -k 1 ) ( (a m δ 0 ) m , 0 ) (0, k 1 ). Now define the commutator 1 . In other words g 0 is the identity, thus θ 0 = id. Moreover when m = 1 we have θ 1 = id and the only value of g ′ 1 (x) different from e is g ′ 1 (k 1 ) = a 1 b 1 a -1 1 b -1 1 (on a blue background in Figure 16). Finally if m > 1 then g m is the identity thus θ m = id and g ′ m = id. Combining Lemma 2.7 and Fact 2.9 of [START_REF] Brieussel | Speed of random walks, isoperimetry and compression of finitely generated groups[END_REF], we get the following result.

Lemma A.6

Let (𝐠, t) ∈ Δ. For all m ∈ ℕ and x ∈ ℤ we have g m (x) = g ′ m (x)θ A m (g 0 (x))θ B m (g 0 (x-k m )).

In particular the sequence 𝐠 = (g m ) m∈ℕ is uniquely determined by g 0 and (g ′ m ) m∈ℕ .

In the next subsection we are going to see that we actually need only a finite number of elements of the sequence (g ′ m ) m∈ℕ to characterize 𝐠.

A.2 Range and support

In this subsection we introduce the notion of range of an element (𝐠, t) in Δ. We denote by π 2 ∶ Δ → ℤ the projection on the second factor. • First consider J an interval containing 0 and let (𝐡, 0) ∈ Δ such that h ′ m = id for all m ≥ 1 and h m (x) = 0 for all x ∉ J. Recall that Δ 0 = (A × B) ≀ ℤ thus |(h 0 , 0)| Δ 0 ≤ 3diam (J). Now decompose (h 0 , 0) as a product (h 0 , 0) = s 1 ⋯ s |(h 0 ,0)| with s i ∈ 𝒮 Δ 0 and consider ŝi as defined above. Then (𝐡, 0) = ŝ0 ⋯ ŝ|(h 0 ,0)| by Lemma A.6. Thus |(𝐡, 0)| Δ ≤ |(h 0 , 0)| Δ 0 ≤ 3diam (J).

• Let I be a subinterval of [0, D] containing both t and u and assume that f ′ j = g ′ j for all j ≥ 1 and f 0 (z) = g 0 (z) for all z ∈ ℤ\I. Then (𝐟, t) -1 (𝐠, t) verifies the assumptions of the previous point with J = I -t. In particular J has same diameter as I. We thus obtain the first assertion of the lemma noting that (𝐟, t) -1 (𝐠, u) = (𝐟, t) -1 (𝐠, t)(0, ut) and |u -t| ≤ diam (I). Now for the second assertion.

• Let i ≥ 1 and (𝐡, 0) ∈ Δ such that h ′ j = id for all j > i. Since (l m ) m is a subsequence of a geometric equence this last term is equivalent to Dl i . • Now assume that f ′ j = g ′ j for all j > i. As for the first assertion of the lemma, we apply the result of the last point to (𝐡, 0) = (𝐟, t) -1 (𝐠, t) and conclude noting that |u -v| ≤ D.

B VArIABLE BASE

We compute here some results concerning the decomposition of an integer in some fixed or variable base. We start by showing the existence and uniqueness of such a decomposition, then study the behaviour of this composition under addition and conclude on some counting result.

B.1 Decomposition in variable base

If q ∈ ℕ * , we know that any integer can be uniquely written in base q. We extend here such a definition for a "variable" base. Consider (b i ) i∈ℕ a sequence of integers greater or equal to 2.

Lemma B.1

For all x ∈ ℕ there exists a unique sequence of integers (x i ) i∈ℕ such that Proof. Consider x ∈ ℕ and let us proceed to the euclidean division of x by b 0 : there exist q 0 ∈ ℕ and 0 ≤ x 0 < b 0 such that x = x 0 + b 0 q 0 . Now for all i ∈ ℕ define inductively q i+1 and x i+1 such that 0 ≤ x i+1 < b i+1 and q i = x i+1 + b i+1 q i+1 . Since (q i ) i∈ℕ is a strictly decreasing sequence of integers, there exists n ∈ ℕ such that q i = 0 for all i ≥ n. Thus, by definition of the sequence, we also get x i = 0 for all i > n. Hence, x = x 0 + b 0 q 0 = x 0 + b 0 (x 1 + b 1 q 1 ) = x 0 + b 0 (x 1 + b 1 (⋯ (a n-1 + b n-1 a n ) ⋯)) = ∑ i≤n x i i-1 ∏ j=0 b j Hence the existence. For the uniqueness, consider (x ′ i ) i to be another such sequence, then .

Thus b 0 divides x 0 -x ′ 0 . But x 0 , x ′ 0 ∈ {0, … , b 0 -1} thus x 0 -x ′ 0 = 0. Iterating this process, we show that x i = x ′ i for all i. Hence the unicity. Finally, let M ∈ ℕ and i > M. If x i > 0 then x ≥ ∏ M i=0 b i . On the contrary if x i = 0 for all i ≥ n then Example B.2. If b i = q for all i we obtain the usual decomposition in base q.

Figure 1 :

 1 Figure 1: Definition of g • x

  ℤ/qℤ ≀ ℤ Couplings obtained in this paper Couplings from Delabie et al. Couplings from Carderi et al.

Figure 2 :

 2 Figure 2: Overview of the mentioned couplings

Figure 4 :

 4 Figure 4: Definition of the injection This is the general idea, now let us describe the numbering process of 𝐟.

Figure 5 :

 5 Figure 5: Example of ℬ i (t) for κ = 3, n = 3 and t = 16.

  y) ∈ ℤ 2

Figure

  Figure 8: Numbering in Δ

Remark 4. 10 .

 10 Note that |𝒦 n | ∼ |𝒢 n |. Indeed by eq. (4.2) we have |𝒢 n | ≤ | F dn,in,jn | ≤ |𝒦 n |.

Figure 9 :

 9 Figure 9: Possible values for u when D n = 4κ n + 3.

Figure 10 :

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

  Figure 12: Comparison of F Dn and F Dn,In,Jn when k 𝔩(Dn-1) = D n -1

Figure 13 :

 13 Figure 13: Numbering in Δ

  Figure 14: Affine approximation

  1,P,t b 2,P,t

  Proof of Lemma 4.29. We can now use the above claim to bound ∑ n-1 i=0 |Z m,i |. First if m ≤ 2 then |X s m | = 0 by Claim 4.30.

  ) and consider s ∈ S Δ . Let us show that eq. (2.1) is verified for φ(x) ∶= ρ ∘ ρ -1 bij . Let R > 0 and let n ∈ ℕ and m ∈ [0, p n + M n ]. By Proposition 4.23 if (𝐟, t) belongs to X s m then d ( ι n (𝐟, t), ι n( (𝐟, t)s )) ≼ m-pn if m ≥ p n + 1.

  Remark 4.10 to simplify the quotient |𝒦 n |/|𝒢 n | and the assumption made on φ. If 2 < m ≤ p n we obtain φ

  ε) q -κ m-1 ,where the last term is a constant that does not depend on n nor on R. Similarly for allm ≥ p n + 2 φ ( D n l m-pn ) |X s m | |𝒢 n | ≼ φ(D n l m-pn )|𝒦 n |q -Dn exp ( -l m-1-pn )

  exp (-l m-1 ) < +∞.

  n+1 m=0 φ(κ m )|X s m |/|𝒢 n | by a constant that does not depend on n nor on R.

(

  𝐠, 0) = (𝐟, 0) ⋅ ( (b m δ km ) m , 0 ) ⋅ (𝐟, 0) -1 ⋅ ( (b -1 m δ km ) m , 0 ) and let us describe the values taken by 𝐠 and the induced maps θ m (g m ) and g ′ m (see Figure 16 for a representation of 𝐠). The only non-trivial commutator appearing in the values taken by 𝐠 is g 1 (k 1 ) which is equal to a 1 b 1 a -1 1 b -1

CursorFigure 16 :

 16 Figure 16: Representation of (𝐠, 0) defined in Example A.4Let us study the behaviour of this decomposition under product of lamp configurations.Claim A.5. If g m , f m ∶ ℤ → Γ m then (g m f m ) ′ = g ′ m θ m (g m )f ′ m ( θ m (g m ) ) -1 .Proof. Since g m = θ m (g m )g ′ m and f m = θ m (f m )f ′ m we can writeg m f m = g ′ m θ m (g m ) ⋅ f ′ m θ m (f m ) = g ′ m θ m (g m )f ′ m θ m (g m ) -1 θ m (g m )θ m (f m ).But θ m (g m )θ m (f m ) takes values in A m × B m and Γ ′ m is a normal subgroup of Γ m thus the map g ′ m θ m (g m )f ′ m θ m (g m ) -1 takes values in Γ ′ m . Hence the claim.

Definition A. 7 .

 7 If w = s 1 … s m is a word over S Δ we define its range as range(w) Now let D ≥ 0 and consider (𝐟, t), (𝐠, u) ∈ Δ such that their range is included in [0, D].

  Let us first bound |(h n , 0)| Δm for all m ≤ i. Using Definition A.20 we getE m (h m ) ≤ k m diam (Γ m ) | {j ∶ I m j ∩ range(h m , t) ≠ ∅} |But the range of (h m , t) is contained in [0, D] thus right most set contains at most 2D/k m + 2 elements. Hence, by Proposition A.21|(h m , 0)| Δm ≤ 9 ( range(h m , 0) + E m h m) ≤ 9(D + diam (Γ m ) k m (2D/k m + 2)) ∼ Dl m . Now let (h ′ m 0) = s 1,m ⋯ s Mm be a decomposition of (h ′ m , 0) in a product of minimal lenght of generators s i,m ∈ 𝒮 Δm . Note that Lemma A.6 implies |(h ′ m , 0)| Δm ∼|(h m , 0)| Δm . For each generator s i,m consider the corresponding ŝi,m ∈ 𝒮 Δ and denote (𝐡(m) , 0) = ∏i ŝi,m . Since h ′ m (x) is a product of conjugate of commutators (by definition of Γ ′ m ) the element (h (m) , 0) verifies h (all j ≠ m (see for Figure16for an illustration). Therefore using the hypothesis that h ′ m = id for all m > i and the decomposition given in Lemma A.6 we can show that (𝐡, 0) = ∏m≤i ∏ Mm i=1 ŝi,m . Thus |(𝐡, 0)| Δ ≤ |(h 0 , 0)| Δ 0

(

  ∀i ∈ ℕ ) 0 ≤ x i ≤ b i -1 and x = Moreover x belongs to {0, … , ∏ n i=0 b i -1} if and only if x i = 0 for all i > n.

  Thus x ∈ {0, … , ∏ M i=0 b i -1}.

  Let ρ ∈ 𝒞. If there exists ε > 0 such that ρ (x) ≼ x 1-ε , then there exists a group G such that • I G ≃ ρ ∘ log;• There exists a ( ρ , L 0 )-integrable measure equivalence coupling from G to BS(1, k).

	1 Introduction
	Corollary 1.21

  Let (𝐟, t) ∈ 𝒢 n , let x and j P,t be as above and

		4.21)
	Proposition 4.23
	m ∶=	⎩ ⎨ ⎧ j P,t (x, 2)

We chose to adopt the convention of[START_REF] Delabie | Quantitative measure equivalence[END_REF]. Note that in[START_REF] Brieussel | Speed of random walks, isoperimetry and compression of finitely generated groups[END_REF], the isoperimetric profile is defined as Λ G = 1/I G .

ρ ∈ 𝒞, Theorem 1.16 does. In particular it does not apply to ρ ≃ id, and therefore excludes

We refer to [DKLMT20, Section 6] for the construction of the coupling

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

In the base ( b i,P,t) i=0,…,pn+Mn we thus write ϑ n (𝐠, u(P, t)) ∶=ν 0 ( g 0|ℬ 0 (P,t)) + pn-1 ∑ i=1 ν i ( g 0|ℬi(P,t)\ℬ i-1 (P,t)) b i-1,𝐟,t ⋯ b 0,P,t + Mn ∑ m=1 μ m (g ′ m ) b m+pn,P,t ⋯ b 0,P,t .

(4.15)

Lemma 4.17

Let ϑ n as defined in eq. (4.15). For all v ∈ im(u) the map ϑ n (⋅, v) is injective and its image is exactly the interval [0, max(ϑ n )].

Proof. Assume that there exist 𝐠, 𝐡 such that ϑ n (𝐠, v) = ϑ n (𝐡, v) and let P and t such that v = u(P, t). Then ϑ n (𝐠, v) and ϑ n (𝐡, v) share the same decomposition in base (b i,P,t ) that is to say μ m (g ′ m ) = μ n (h ′ m ) for all m, and ν 0 (g 0|ℬ 0 (P,t) ) = ν(h 0|ℬ 0 (P,t) ) and similarly for the ν i 's. Since all the μ m and ν i 's are bijections we thus get that g 0 = h 0 and 𝐠 ′ = 𝐡 ′ .

Hence 𝐠 = 𝐡. The second part comes from Lemma B.1 applied to the base (b i,P,t ) i .

Injection

So far we can define a map that sends an element (𝐟, t) in Δ to ( θ n (𝐟, t), u(𝐟, t)) in ℤ 2 . For v ∈ im(u) we can also consider the map that sends (𝐠, v) ∈ Δ to (ϑ n (𝐠, v), v) ∈ ℤ 2 . A first idea to define our injection ι n ∶ 𝒢 n → 𝒦 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-Cdense injection. Indeed, the image of θ n is strictly included in the one of ϑ n and more precisely the elements in im(ϑ n ) that are not reached by θ n are the greatest values.That is to say some values of μ n might not be reached. Hence translating θ n into a sequence of lamp configurations 𝐠 in Δ might not give us all the possible values for 𝐠 ′ . But if such a (𝐠, w) ∈ 𝒦 n is not reached then it might differ from the nearest element in im(ι n ) by a value of g ′ Mn . Such an element will be far away from the reached one, since changing a lamp of g ′ Mn requires a lot of multiplications by generators. In order to obtain the density we thus need to spread the unreached values across the interval im(ϑ 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, … , max( θ n )} accross the intervall [0, max(ϑ n )], the ideal map to consider would be the one sending x to max(ϑ n ))/ max( θ n )x (represented in Figure 14a). But we also want the values taken by this spreading map to be integers. Since the quotient max(ϑ n ))/ max( θ n ) is not necessarily an integer, the aforementioned values do not necessarily belong to ℕ. This is why we define 𝔞 n ∶= ⌈ max(ϑ n )/ max( θ n ) ⌉ and consider instead a piecewise affine map that approaches the above linear one and gives integers values (see Figure 14b).

Lemma 4.18

Let n ∈ ℕ. There exists a piecewise affine map 𝔰 n : [0, max θ n ] → [0, max ϑ n ] which is (q 3 )-Lipschitz and verifies

• 𝔰 n (x) ∈ ℕ, for all x ∈ {0, … , max θ n };

• 𝔰 n (max θ n ) = max ϑ n .

The map we are going to construct is the one described in Figure 14b. Before showing the above lemma let us bound the value of 𝔞 n .

INJEcTIVITY AND DENSITY

Let us now define the Sofic approximation we want to work with in Δ. We saw in Lemma 4.7 that the image of the map sending (𝐟, t) to ( t, θ n (𝐟, t), P n (f ′ ) ) was not necessarily the product

It might indeed be smaller. The unreached part of this last product might lead to a large area of unreached elements in 𝒦 n , preventing the injection from 𝒢 n to 𝒦 n to be C-dense.

We consequently define a new sofic approximation ℋ n included in 𝒦 n but not containing the aforementioned unreached elements.

The set ℋ n defined in eq. (4.17) is a Følner set of Δ.

Proof. Using that 𝔰 n is (q 3 )-Lipschitz and that max(

Recall (see eq. (4.9)) that 𝒦 n = F Dn,In,Jn . Using the value of |𝒦 n | given by Lemma 2.7, we get that D n q 3+κ n /|𝒦 n | tends to zero, thus 𝒦 n minus some set of at most D n q 3+κ n elements is still a Følner sequence.

Let us now define the C-dense injection.

Lemma 4.21

Let ι n ∶ 𝒢 n → ℋ n be the map such that ι n (𝐟, t) ∶= (𝐠, u(P n (𝐟′), t)) where u is defined in eq. (4.10) and 𝐠 verifies θn (𝐟, t) = ϑ n ( 𝐠, u ( P n (𝐟′), t )) . Then there exists a constant C > 0 such that ι n is injective and C-dense for n large enough.

Proof. Let us first show that ι n is well defined, that is to say: for all (𝐟, t) ∈ 𝒢 n there exists a unique 𝐠 such that ( 𝐠, u(P n (𝐟′), t) ) belongs to ℋ n and verifies θn (𝐟, t) = ϑ n ( 𝐠, u ( P n (𝐟′), t )) . Recall that θn = 𝔰 n ∘ θ n and that χ is defined in Lemma 4.13.

• Let (𝐟, t) ∈ 𝒢 n . By Lemmas 4.17 and 4.18 θn (𝐟, t) belongs to [0, max ϑ n ]. Thus there exists 𝐠 such that ( g, u(P n (𝐟′), t) ) belongs to 𝒦 n and θn (𝐟, t) = ϑ n ( 𝐠, u ( P n (𝐟′), t )) . • By choice of 𝐠, if θn (𝐟, t) < 𝔰 n ( q κ n max(E n ) ) then ϑ n (𝐠, u ( P n (𝐟′), t ) ) is also strictly smaller than 𝔰 n ( q κ n max(E n ) ) and thus (𝐠, u ( P n (𝐟′), t ) ) belongs to ℋ n . • Recall that 𝔰 n is increasing, thus θ n (𝐟, t) is greater than q κ n max(E n ) if and only if θn (𝐟, t) is greater than 𝔰 n ( q κ n max(E n ) ) . Therefore if θn (𝐟, t) ≥ 𝔰 n ( q κ n max(E n ) ) then Lemma 4.7 implies that P n (𝐟′) equals at most max( μ n ) -Q n max(E n ) and thus

Let us now study the behaviour of the blocs Bi ( t ) and the maps ( ν i ) i . Note that if s = (0, 1) then t = t + 1.

Claim 4.26.

If s = (0, 1) then Bi (t) = Bi (t + 1) for all i > i 0 (t) and thus

Proof of the claim. Let i > 0. If s belongs to 𝒮 1 ∪ 𝒮 2 then t = t. But Bi ( t ) depends only on the value of i and t thus Bi (t) = Bi ( t ). Moreover f0 (x) = f 0 (x) for all x ≠ t. But by Lemma 3.1 the set Bi (t)\ Bi-1 (t) does not contain t, thus f 0 restricted to this last set is equal to f0 restricted to it. Hence the first assertion.

Let us now treat the case when s = (0, 1). By Lemma 4.22 for all i > i 0 (t) we have Bi (t) = Bi (t + 1). Finally, since s = (0, 1) then 𝐟 = f and in particular f0 = f 0 . Hence the second assertion.

We can now prove the first lemma.

Proof of Lemma 4.24. First suppose that s ∈ 𝒮 1 ∪ 𝒮 2 . By Claims 4.25 and 4.26 and using the definition of θ n given in eq. (4.7), we get

Now recall that θn = 𝔰 n ∘ θ n where 𝔰 n is a q 3 -Lipschitz map, thus | θn (𝐟, t) -θn( (f, t)s ) | ≤ q 3 q.

But κ is greater than 3 thus q 4 < q κ 2 . Moreover by Remark 4.15 |ℬ 2 (P, t)| is greater than κ 2 for all P and t, since b 0 b 1,P,t b 2,P,t = q |ℬ 2 (P,t)| we thus obtain | θn (𝐟, t) -θn( (f, t)s ) | < q κ 2 ≤ b 0 b 1,P,t b 2,P,t .

Assume now that s = (0, 1). By Claims 4.25 and 4.26 and definition of

But ν 0 takes its values in [0, q -1], thus | ν 0 ( f0| B0 (t+1) ) -ν 0 ( f0| B0 (t) )| ≤ q -1. Similarly, for all i ∈ [1, i 0 (t)] we have

But θn = 𝔰 n ∘ θ n where 𝔰 n is a q 3 -Lipschitz map thus | θn (𝐟, t) -θn( (f, t)s ) | < q 3 b i 0 (t) ⋯ b 0 .

If i 0 (t) = 0 then q 3 b i 0 (t) ⋯ b 0 = q 3 b 0 = q 3 q. By the same argument as in the above case we obtain that q 3 b 0 ≤ b 0 b 1,P,t b 2,P,t . Hence the result for i 0 (t) = 0.

To prove the case when i 0 (t) > 0 we only have to show that q 3 b i 0 (t) ⋯ b 0 is smaller than b i 0 (t)+1,P,t ⋯ b 0,P,t . First recall (see Remark 4.6) that b i 0 (t) ⋯ b 0 = q κ i 0 (t) . And since i 0 (t) < n ≤ p n we can use Lemma 4.16 and obtain that q κ i 0 (t)+1 ≤ b i 0 (t)+1,P,t ⋯ b 0,P,t . Now remark that since i 0 (t) > 0 and κ ≥ 3 we have κ i 0 (t) + 3 ≤ κ i 0 (t)+1 . Thus | θn (𝐟, t) -θn( (f, t)s ) | < q 3 b i 0 (t) ⋯ b 0 ≤ q 3 q κ i 0 (t) ≤ q κ i 0 (t)+1 ≤ b i 0 (t)+1,P,t ⋯ b 0,P,t .

FrOM INTEGErS TO LAMPS

First, applying Lemma B.5 to the result of Lemma 4.24, we deduce the following assertion.

Claim 4.27. Let x and y as defined by eq. (4.20) and for all i ≥ 0 let j P,t (x, i) as defined in eq. (4.21). Denote P = P n (𝐟′).

If s ∈ 𝒮 1 ∪ 𝒮 2 or if (s = (0, 1) and i 0 (t) = 0) then x j = y j for all j > j P,t (x, 2).

If s = (0, 1) and i 0 (t) > 0 then x j = y j for all j > j P,t (x, i 0 (t) + 1).

We can now bound the distance and prove Proposition 4.23.

Proof of Proposition 4.23. Consider s ∈ 𝒮 Δ and (𝐟, t) ∈ 𝒢 n . Let x as in eq. (4.20) and j P,t as in eq. (4.21) and recall that (𝐠, v) ∶= ι n (𝐟, t) and (𝐡, w) ∶= ι n( (𝐟, t)s ) . Define

if s ∈ 𝒮 1 ∪ 𝒮 2 or (s = (0, 1) and i 0 (t) = 0), j P,t (x, i 0 (t) + 1) else.

Let us first recall that if s ∈ 𝒮 1 ∪𝒮 2 then P = P n (𝐟 ′ ) = P n ( f′ ) and thus ℬ i (P, t) = ℬ i (P n( f′ ) , t

) for all i. If s = (0, 1) then note that m > i 0 (t) by definition of j P,t . Thus i > i 0 (t) for all i > m and by Lemma 4.22 we have ℬ i (P, t) = ℬ i (P n( f′ ) , t ) for all i > m. In particular v and w both belong to ℬ i (P, t). Moreover by Claim 4.27 we know that x j = y j for all j > m.

We distinguish 2 cases depending on the value of m.

• Assume first that m ≤ p n . Since x j = y j for all j > m, using the expression of

In other words 𝐡 and 𝐠 differ at most from the value of g 0 and h 0 on the interval ℬ m (P, t). Hence using Proposition A.22 we obtain d ( (𝐠, u), (𝐡, v) ) ≤ 3diam (ℬ m (P, t)) .

(4.22)

The first part of the proposition then comes from Remark 4.15.

• Now assume that m ≥ p n + 1. By the same argument as above we get that μ i (g ′ i ) = μ i (h ′ i ) for all i > m -p n . Then by the second part of Proposition A.22 we get d Δ( (𝐠, u), (𝐡, v) ) ≤ D n l m-pn .

(4.23) Hence the second part of the lemma.

Enumeration

Let s ∈ 𝒮 Δ. Our goal is now to estimate the number of elements (𝐟, t) in 𝒢 n such that ι n sends (𝐟, t)s at distance r from (𝐟, t) in Δ for a given distance r > 0. As suggested by Proposition 4.23 it depends on the value of the map j P,t . We first study the action of generators in 𝒮 1 ∪ 𝒮 2 and then the action of s = (0, 1). Recall that x(𝐟, t, s) is defined in eq. (4.20) and j P,t in eq. (4.21).

AcTION ON THE LAMP cONFIGUrATION

Let us study the case when s is a generator that modifies a lamp that is to say when s belongs to 𝒮 1 ∪ 𝒮 2 .

Lemma 4.28

Proof. First note that by definition of j P,t we have j P,t (z, 2) > 2 for all z. Thus X s m is empty if m ≤ 2. Now assume that m > 2. Recall that x(f, t, s) belongs to { θn (𝐟, t), θn( (𝐟, t)s ) } by eq. (4.20). Hence Consider t ∈ [0, κ n -1] and P ∈ [0, Q n -1], using first Lemma 4.7 then the fact that

Recalling that max ϑ n = |𝒦 n |/D n and applying Lemma B.7 to the base (b i,P,t ) i we get | { (𝐟, t) ∈ 𝒢 n | P n (𝐟 ′ ) = P and j P,t( θn (𝐟, t

By Lemma 4.16 the product b 2,P,t b 1,P,t b 0 belongs to [q κ 2 , q 2κ 2 ]. Hence b m-1,P,t ⋯ b 3,P,t is equivalent to b m-1,P,t ⋯ b 0,P,t . We thus now need to bound by above the value of |𝒦 n |/D n (b m-1,P,t ⋯ b 0,P,t ) -1 . We apply Lemma 4.16 and distinguish three cases depending on the value of m.

| { (𝐟, t) ∈ 𝒢 n | P n (𝐟 ′ ) = P and j P,t( θn (𝐟, t

Applying the same argument to the right most set of eq. ( 4.24) we can also bound its number of elements by |𝒦 n |q -κ m-1 and thus get

For the other values of m, replacing q -κ m-1 in the above inequalities by the corresponding value of (b m-1,P,t ⋯ b 0,P,t ) -1 we obtain the lemma.

AcTION ON THE cUrSOr

Let us now treat the case when s = (0, 1). Recall that according to Proposition 4.23 the case when i 0 (t) = 0 is slightly different from the one where i 0 (t) > 0. Let us define

Our goal is to give an upper bound to the number of elements in ⊔ n-1 i=0 Z m,i . Lemma 4.29

But first let us bound the number of elements in Z m,i .

Claim 4.30.

Assume that m ≥ p n + 2. Using eq. (4.4) we obtain D n κ -n ≼ Q n . Furthermore recall that Q n ≥ 3 thus 2 -Q n < 0 and hence by a similar argument as in eq. (4.26) we get q 2κ n -Dn ≤ q 2-Qn ∼ q -Qn . Hence D n l m-pn κ -n q 2κ n -Dn exp ( -l m-1-pn )

≼Q n q -Qn pn+Mn ∑ m=pn+2 l m-pn exp ( -l m-1-pn ) .

By Lemma 4.5 (Q n ) n is unbounded thus Q n q -Qn can be bounded uniformly on n by a constant and by assumption l m-pn exp(-l m-1-pn ) is summable. Hence the above last term is bounded by a constant not depending on n nor R.

Finally assume that m = p n +1. Using a similar argument as above to estimate the value of D n q 2κ n -Dn κ -n we obtain

This last term can thus also be bounded by a constant. Hence the three terms in eq. (4.25) are bounded by constants that do not depend on n nor on R. Thus eq. (2.1) is verified for s = (0, 1).

CONcLUSION

By Theorem 2.3 we obtain that their exists a (φ, L 0 )-integrable measure equivalence coupling from Δ to Δ.

Let us conlude by the proofs of our two last corollaries.

Proof of Corollary 1.20. Let ρ ∶ [1, +∞[→ [1, +∞[ such that ρ and x/ ρ (x) are non-decreasing and assume that there exists ε > 0 such that ρ (x) ≼ x 1-ε . Consider G ∶= Δ the associated diagonal product. By Corollary 1.19 there exists a ( ρ , L 0 )-integrable measure equivalence coupling from G to the lamplighter group (A×B)≀ℤ. By Example 2.4 there exists a measure equivalence coupling from (A × B) ≀ ℤ to H that is (L ∞ , exp)-integrable. It is thus (ψ, exp)integrable for all increasing map ψ ∶ ℝ + → ℝ + . In particular if ψ = id we can compose the couplings and obtain by Proposition 3.10 a measure equivalence coupling from G to H that is ( ρ , L 0 )-integrable. Hence the corollary.

We show Corollary 1.21 similarly, composing the coupling from Corollary 1.20 with the one in Theorem 4.31 (see below).

Theorem 4.31 ([DKLMT20, Th. 8.1])

For all k ≥ 2, their exists an orbit equivalence coupling from ℤ/kℤ ≀ ℤ to BS(1, k) that is (L ∞ , exp)-integrable.

Appendices A DIAGONAL PrODUcTS

In order for this article to be self contained, we repeat here the introduction to diagonal product made in [Esc22, Section 2] and complete it with a finer estimate of the metric in Proposition A.22. This section recall necessary material from [START_REF] Brieussel | Speed of random walks, isoperimetry and compression of finitely generated groups[END_REF] concerning the definition of Brieussel-Zheng's diagonal products: we give the definition of such a group, recall and prove some results concerning the range (see Definition A.7) of an element. Finally we present in appendix A.3 the tools needed to recover such a diagonal product starting with a prescribed isoperimetric profile and compute useful estimate on the metric.

A.1 Definition of diagonal products

Recall that the wreath product of a group G with ℤ denoted G ≀ ℤ is defined as G ≀ ℤ ∶= ⊕ m∈ℤ G ⋊ ℤ. An element of G ≀ ℤ is a pair (f, t) where f is a map from ℤ to G with finite support and t belongs to ℤ. We refer to f as the lamp configuration and t as the cursor.

A.1.1 General definition

Let A and B be two finite groups. Let (Γ m ) m∈ℕ be a sequence of finite groups such that each Γ m admits a generating set of the form A m ∪ B m where A m and B m are finite subgroups of Γ m isomorphic respectively to A and B. For a ∈ A we denote a m the copy of a in A m and similarly for B m .

Finally let (k m ) m∈ℕ be a sequence of integers such that k m+1 ≥ 2k m for all m. We define

Definition A.1

The Brieussel-Zheng's diagonal product associated to (Γ m ) m∈ℕ and (k m ) m∈ℕ is the subgroup Δ of (∏ m Γ m) ≀ ℤ generated by

The group Δ is uniquely determined by the sequences (Γ m ) m∈ℕ and (k m ) m∈ℕ . Let us give an illustration of what an element in such a group looks like. We will denote by 𝐠 the sequence (g m ) m∈ℕ .

Example A.2. We represent in Figure 15 the element ( 𝐠, t ) of Δ verifying (𝐠, t) = ( (g m ) m∈ℕ , t ) ∶= ( (a m δ 0 ) m , 0 )( (b m δ km ) m , 0 ) (0, 3), when k m = 2 m . The cursor is represented by the blue arrow at the bottom of the figure. The only value of g 0 different from the identity is g 0 (0) = (a 0 , b 0 ). Now if m > 0 then the only values of g m different from the identity are g m (0) = a m and g m (k m ) = b m .

A.1.2 The expanders case

In this article we will restrict ourselves to a particular familiy of groups (Γ m ) m∈ℕ called expanders. Recall that (Γ m ) m∈ℕ is said to be a sequence of expanders if the sequence of diameters (diam (Γ m )) m∈ℕ is unbounded and if there exists c 0 > 0 such that for all m ∈ ℕ and all n ≤ |Γ m |/2 the isoperimetric profile verifies I Γm (n) ≤ c 0 .

When talking about diagonal products we will always make the following assumptions. We refer to [BZ21, Example 2.3] for an explicit example of diagonal product verifying (H).

Hypothesis (H)

• q ∶= |A × B| = 6;

• (k m ) m and (l m ) m are sub-sequences of geometric sequences.

• k m+1 ≥ 2k m for all m ∈ ℕ;

• (Γ m ) m∈ℕ is a sequence of expanders such that Γ m is a quotient of A * B and there exists c > 0 such that diam (Γ m ) ≤ cl m for all m ∈ ℕ;

Recall (see [BZ21, page 9]) that in this case there exist c 1 , c 2 > 0 such that, for all m

Finally we adopt the convention of [BZ21, Notation 2.2] and allow k m to take the value +∞. In this case Δ m is the trivial group. In particular when k 1 = +∞ the diagonal product Δ corresponds to the usual lamplighter (A × B) ≀ ℤ. Finally for all m we have g ′ m = id since there are no commutators appearing in the decomposition of (𝐠, 0).

A.1.3 Relative commutators subgroups

The range is a finite subinterval of ℤ. It represents the set of sites visited by the cursor.

Definition A.8

The range of an element δ ∈ Δ is defined as the minimal diameter interval obtained as the range of a word over S Δ representing δ.

When there is no ambiguity we will denote range(δ) the diameter of this interval.

Example A.9. Let (𝐠, 0) ∈ Δ such that range(𝐠, 0) = [0, 6], that is to say: the cursor can only visit sites between 0 and 6. Let us now recall a useful fact proved in [START_REF] Brieussel | Speed of random walks, isoperimetry and compression of finitely generated groups[END_REF]. For all n ∈ ℕ we denote by 𝔩(n) the integer such that k 𝔩(n) ≤ n < k 𝔩(n)+1 .

Claim A.10 ([BZ21, Fact 2.9]). An element (𝐠, t) ∈ Δ is uniquely determined by t, g 0 and the sequence (g ′ m ) m≤𝔩(range(𝐠,t)) .

Example A.11. Consider again (𝐠, 0) ∈ Δ such that range(𝐠, 0) = [0, 6], which was illustrated in Figure 17. Since k 3 = 8 > 6, the element (𝐠, 0) is uniquely determined by the data g 0 (that is to say, the values read in the bottom line) and the values of g ′ i for i = 1, 2 (namely, the value taken in the blue area). Figure 18 represents the aforementioned characterizing data.

A.3 From the isoperimetric profile to the group

We saw how to define a diagonal product from two sequences (k m ) m and (l m ). In this section we recall the definition given in [BZ21, Appendice B] of a Brieussel-Zheng's group from its isoperimetric profile. We conclude on some useful results concerning the metric of these groups. Recall that in the particular case of expanders (see appendix A.1.2) a Brieussel-Zheng's group Δ is uniquely determined by the sequences (k m ) m∈ℕ and (l m ) m∈ℕ (where l m corresponds to the diameter of Γ m ). Thus, starting from a prescribed function ρ, we will define sequences (k m ) m∈ℕ and (l m ) m∈ℕ such that the corresponding Δ verifies I Δ ≃ ρ ∘ log. First, let

Equivalently this is the set of functions ρ satisfying

Combining [BZ21, Proposition B.2 and Theorem 4.6] we can show the following result (remember that with our convention the isoperimetric profile considered in [START_REF] Brieussel | Speed of random walks, isoperimetry and compression of finitely generated groups[END_REF] corresponds to 1/I Δ ).

Proposition A.12

Let κ, λ ≥ 2. For any ρ ∈ 𝒞 there exists a subsequence (k m ) m∈ℕ of (κ n ) n∈ℕ and a subsequence (l m ) m∈ℕ of (λ n ) n∈ℕ such that the group Δ defined in appendix A.1.2 verifies

Example A.13 ([BZ21, Example 4.5]). Let α > 0. If ρ(x) ∶= x 1/(1+α) then the diagonal product Δ defined by k m = κ m and l m = κ αm verifies I Δ ≃ ρ ∘ log.

Example A.14. If ρ = log then the diagonal product ℤ defined by k m = κ m and l m = κ κ m verifies I Δ ≃ ρ ∘ log. More generally if r ≥ 1 then the diagonal Δ defined by k m = κ m and

Recall that we allow k m to take the value +∞ (see below eq. (A.1)).

Example A.15. If ρ(x) = x then the diagonal product defined by l m = 1 for all m and k m = +∞ for all m ≥ 1 verifies Δ = (A × B) ≀ ℤ and I Δ ≃ log.

A.3.2 Technical tools

Now let us recall the intermediary functions defined in [BZ21, Appendix B] and some of their properties.

Let ρ ∈ 𝒞 and let f such that ρ(x) = x/f(x). The construction of a group corresponding to the given isoperimetric profile ρ ∘ log is based on the approximation of f by a piecewise linear function f. For the quantification of orbit equivalence, many of our computations will use f and some of its properties. We recall below all the needed results, beginning with the definition of f.

Lemma A.16

Let ρ ∈ 𝒞 and f such that ρ(x) = x/f(x). Let (k m ) and (l m ) given by Proposition A.12 above and Δ the corresponding diagonal product. The function f defined by

(A.3) verifies f ≃ f. In particular the map ρ defined by ρ (x) = x/ f(x) verifies ρ ≃ ρ.

Example A.17. If ρ(x) = x then f(x) = 1 leads to l m = 1 for all m and k m = +∞ for all m ≥ 1. In this case Δ = (A × B) ≀ ℤ.

Remark that both f and ρ belong to 𝒞. In particular they verify eq. (A.2), which is only true when c and x are greater than 1. When c < 1 we get the following inequality. Proof. If 0 < c′ < 1 then 1/c′ > 1, thus we can apply eq. (A.2) with c = 1/c′ and x = c′x to obtain ρ

A.3.3 Inverse map

In order to prove Theorem 1.18 we will need to consider the inverse of a map ρ ∈ 𝒞. But such ρ is not necessarily bijective: for example the map ρ ∈ 𝒞 defined by Lemma A.16 is constant on the intervals [k m+1 l m , k m+1 l m+1 ]. We show here that there exists a bijective map ρ bij ∈ 𝒞 such that ρ bij ∼ ρ.

Lemma A.19

Let 1/2 > δ > 0 and ρ ∈ 𝒞. There exists a bijective piecewise affine map ρ bij such that ρ bij ∼ ρ ∼ ρ. Moreover if ρ (x) = y for some y ≥ 1 then x ≤ ρ -1 bij (2y).

The definition of ρ bij is summed up in Figure 19. Proof. Consider ρ ∈ 𝒞 and ρ the induced piecewise affine map defined in Lemma A.16. In particular ρ ∼ ρ. Define ρ bij such that ρ bij (x) = ρ (x) for all x ∈ [ (k m + δ) l m , (k m+1 -δ) l m] and such that ρ bij coincide on [(k m+1 -δ) l m , (k m+1 + δ) l m+1 ] with the affine map verifying

Then for all

Hence |ρ bij (x) -ρ (x)| ≤ 2δ for all x. Since ρ (x) tends to infinity we thus get ρ bij ∼ ρ . Finally assume that ρ (x) = y ≥ 1. Then by the above estimates ρ bij (x) belongs to [yδ, y + δ]. Since ρ bij is increasing int implies x ≤ ρ -1 bij (y + δ). But y + δ ≤ 2y, hence the last assertion.

A.3.4 Metric

We recall here some useful material about the metric of Δ and refer to [BZ21, Section 2.2] for more details. First, let (x) + ∶= max{x, 0}.

Definition A.20

The following proposition sums up [BZ21, Lemma 2.13, Proposition 2.14].

Proposition A.21

For any δ = (𝐟, t) ∈ Δ we have

For some of the proofs we will need more specific estimates. These needed results are summed up in the following proposition.

Proposition A.22

Let D ≥ 0 and consider (𝐟, t), (𝐠, u) ∈ Δ such that their range is included in [0, D].

• Let I ⊆ [0, D] a subinterval of [0, D] containing t and u. If f ′ j = g ′ j for all j ≥ 1 and f 0 (z) = g 0 (z) for all z ∈ ℤ\I then d Δ ((𝐟, t), (𝐠, u)) ≤ 3diam (I) .

• Let

Proof. Let us first introduce some notations. Recall that Δ j is generated by 𝒮 Δj defined page 50. For an element s ∈ 𝒮 Δj we define

An analogue result can be obtained for a finite sequence (b 0 , … , b M ) by allowing the last coefficient to be greater than b M .

Corollary B.3

Let M ≥ 0 and b 1 , … , b M be integers greater or equal to 2. For all x ∈ ℕ there exists a unique sequence of positive integers (x i ) 0≤i≤M such that x i ≤ b i -1 for all i < M and

sor some m ≤ M if and only if x i = 0 for all i > n.

We will denote [x 0 , … , x M ] 𝐛 the integer x such that x = ∑

B.2 Addition in variable base

Let M > 0 and (b i ) 0≤i≤M be a sequence of positive integers. Our goal in this subsection is to study the behaviour of the decomposition in base (b i ) i under addition.

Let x, y ∈ [0, ∏ M i=0 b i -1] and write their decomposition in base (b i ) 1≤j≤M as x = [x 0 , … , x M ] 𝐛 and y = [y 0 , … , y M ] 𝐛 respectively.

Lemma B.5

Let x and y be as above. Let k ∈ [0, M] and define j 0 (x, k) ∶= min{j > k|x j < b j -1}. Assume that x is smaller than y. If y -x < b 0 ⋯ b k then x j = y j for all j > j 0 (x, k).

Let us describe the idea of this result. First note that the definition of j 0 implies that x i = b i -1 for all k < i < j 0 (x, k). Now if y -x < b 0 ⋯ b k , then there exist z 0 , … , z k such that z i < b i -1 for all i and y -x = [z 0 , … , z k ] 𝐛 . Posing the addition of x with [z 0 , … , z k ] (see Figure 20 below) we see that it can modifiy x 0 , … , x k and create a carry of 1 that can only be absorbed by x j 0 . Indeed for all k < i < j 0 (x, k) the carry of 1 will change x i = b i -1 in 0 and induce a carry of 1 on the next term.

x M + ⋯ + x j 0 +1 + x j 0 + b j 0 -1 -1 + ⋯ + b k+1 -1+ x k + ⋯ + x 0 + z k + ⋯ + z 0 = x M + ⋯ x j 0 +1 + x j 0 + 1+ 0 + ⋯ + 0+ y k + ⋯ + y 0 Let us use this decomposition to prove that y -x ≥ b 0 ⋯ b k . First remark that for all j ∈ ℕ, since x j and y j belong to [0, b j -1] we have y j -x j ≥ -(b j -1). Moreover, by definition of j 0 (x, k) we also have y j 0 (x,k) -x j 0 (x,k) ≥ -(b j 0 (x,k) -2). Thus Moreover we assumed y > x, thus y m 0 -x m 0 ≥ 1 and hence using eq. (B.1) and the above inequality But by definition of j 0 it verifies j 0 (x, k) > k. Since we assumed y -x < b k ⋯ b 0 , we thus obtain the wanted contradiction. Hence x j = y j for all j > j 0 (x, k).

Let us conclude this section on some density result.

Lemma B.6

Let 𝔰 ∶ ℕ → ℕ. Let i ∈ [0, M] and consider 0 < c < b 0 ⋯ b i . If 𝔰 is c-Lipschitz, then for all y in [0, ∏ M j=0 b j -1] there exists x ∈ im(𝔰) such that x j = y j for all j > i.

Proof. Let us assume that there exists y in [0, ∏ M j=0 b j -1] such that for all x ∈ im(𝔰) there exists j > i such that x j is different from y j . Then for such an x ∈ im(𝔰), That is to say for all x ∈ im(𝔰) we have |x -y| > c. In particular, considering x 1 ∶= min{x ∈ im(𝔰) | x 1 ≥ y} and x 2 ∶= max{x ∈ im(𝔰) | x 2 ≤ y} we get that |x 1 -x 2 | = |x 1 -y| + |x 2 -y| > c which contradicts the fact that 𝔰 is c-Lipschitz. Hence the lemma.

B.3 Enumeration

As above, let M > 0 and (b i ) 0≤i≤M be a sequence of integers greater or equal to 2 and denote the decomposition of x in base (b i ) as x = [x 0 , … , x M ] 𝐛 . Recall that j 0 (x, k) ∶= min{j > k|x j < b j -1}. For each integer m we give an estimate of the number of elements Proof. First note that by definition of j 0 it verifies j 0 (x, k) > k. In particular if j 0 (x, k) = m then m > k. Hence the first assertion.