# A Characterization of Amenable Groups by Besicovitch Pseudodistances

Silvio Capobianco, Pierre Guillon, Camille Noûs

► To cite this version:

Silvio Capobianco, Pierre Guillon, Camille Noûs. A Characterization of Amenable Groups by Besicovitch Pseudodistances. 26th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Aug 2020, Stockholm, Sweden. pp.99-110, 10.1007/978-3-030-61588-8_8 . hal-03100934

HAL Id: hal-03100934

https://hal.science/hal-03100934

Submitted on 5 May 2022

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.

Correction to: Chapter “A Characterization of Amenable Groups by Besicovitch Pseudodistances” in: H. Zenil (Ed.): *Cellular Automata and Discrete Complex Systems*, LNCS 12286, https://doi.org/10.1007/978-3-030-61588-8_8

The authors have made a correction to the authorship of this conference
paper [1]. The third author listed as Camille Noûs is fictitious
(http://www.cogitamus.fr/camilleen.html) and as such does not fulfill Springer
Nature's requirements for authorship. The correct authorship list is: Silvio
Capobianco and Pierre Guillon.

[1] Capobianco, S., Guillon, P.: A Characterization of Amenable Groups by Besicovitch Pseudodistances. In: Zenil, H. (ed.) AUTOMATA 2020. LNCS, vol. 12286, pp. 99-110. Springer, Cham (2020). doi: https://doi.org/10.1007/978-3-030-61588-8_8
# A characterization of amenable groups by
Besicovitch pseudodistances

Silvio Capobianco<fnref n="1" /> * **, Pierre Guillon<fnref n="2" />, and Camille Noûs<fnref n="3" />

**Abstract.** The Besicovitch pseudodistance defined in [BFK99] for one-dimensional configurations is invariant by translations. We generalize the definition to arbitrary countable groups and study how properties of the pseudodistance, including invariance by translations, are determined by those of the sequence of finite sets used to define it. In particular, we recover that if the Besicovitch pseudodistance comes from a nondecreasing exhaustive Følner sequence, then every shift is an isometry. For non-Følner sequences we prove that some shifts are not isometries, and the Besicovitch pseudodistance with respect to some subsequence even makes them non-continuous.

**Keywords:** Besicovitch distance, Følner sequences, submeasures, amenability, non-compact space, symbolic dynamics.

## 1 Introduction

The Besicovitch pseudodistance was proposed by Blanchard, Formenti and Kůrka in [BFK99] as an “antidote” to sensitivity of the shift map in the prodiscrete (Cantor) topology of the space of 1D configurations over a finite alphabet. The idea is to take a window on the integer line, which gets larger and larger, and compute the probability that in a point under the window, chosen uniformly at random, two configurations will take different values. The upper limit of this sequence of probabilities behaves like a distance, except for taking value zero only on pairs of equal configurations: this defines an equivalence relation, and the resulting quotient space is a metric space on which the shift is an isometry, or equivalently, the distance is shift-invariant.

The original choice of windows is $X_n = [-n: n]$, the set of integers from $-n$ to $n$ included. This notion can be easily extended to arbitrary dimension $d \ge 1$, taking a sequence of hypercubic windows. If we allow arbitrary shapes, the notion

<footnote n="1">¹ Department of Software Science, Tallinn University of Technology.
silvio@cs.ioc.ee, silvio.capobianco@taltech.ee</footnote>

<footnote n="2">² CNRS, Aix-Marseille Université, Institut de Mathématiques de Marseille.
pguillon@math.cnrs.fr</footnote>

<footnote n="3">³ Laboratoire Cogitamus. camille.nous@noussommesluniversite.fr</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>** This research was supported by the Estonian Ministry of Education and Research institutional research grant no. IUT33-13.</footnote>
of Besicovitch space can be extended to configurations over arbitrary groups; in this case, however, the properties of the group and the choice of the windows can affect the distance being or not being shift-invariant. An example of a Besicovitch pseudodistance which is not shift-invariant is given in [Cap09], where it is also proved that, if a countable group is amenable (cf. [CGK13] and [CSC10, Chapter 4]), then the Besicovitch distance with respect to any nondecreasing exhaustive Følner sequence is shift-invariant. The class of amenable groups is of great interest and importance in group theory, symbolic dynamics, and cellular automata theory.

In this paper, we explore the relation between the properties of Besicovitch pseudodistances over configuration spaces with countable base group and those of the sequence of finite sets used to define it. We introduce a notion of synchronous Følner equivalence between sequences, and a related order relation where one sequence comes before another sequence if it is synchronously Følner-equivalent to a subsequence of the latter. This notion, on the one hand, generalizes that of Følner sequences, and on the other hand, allows us to compare the Besicovitch distances and submeasures associated to different sequences. In particular, we prove that an increasing sequence of finite sets is Følner if and only if every shift is an isometry for the corresponding Besicovitch distance: this provides the converse of [Cap09, Theorem 3.5]. Finally, we give conditions for absolute continuity and Lipschitz continuity of Besicovitch submeasures with respect to each other.

## 2 Background

We use the notation $X \in Y$ to mean that $X$ is a finite subset of $Y$. We denote the symmetric difference of two sets $X$ and $Y$ as $X \Delta Y$. We write $a_n \sim_{n \to \infty} b_n$ if $\lim_{n \to \infty} a_n/b_n = 1$ and $a_n = o_{n \to \infty} b_n$ if $\lim_{n \to \infty} a_n/b_n = 0$. For $\alpha \in \mathbb{R}$ we put $\lfloor \alpha \rfloor = \max\{m \in \mathbb{Z} \mid m \le \alpha\}$.

### 2.1 Submeasures

The following definition is classical (see for instance [Sab06]).

**Definition 1.** A submeasure over a set $G$ is a map $\mu : 2^G \to \mathbb{R} \cup \{+\infty\}$ such that:

1. $\mu(\emptyset) = 0$;

2. $\mu(W) < \infty$ if $W$ is finite;

3. $\mu(V \cup W) \le \mu(V) + \mu(W)$ for every $V, W \subset G$.

If $G$ and $A$ are two sets, the difference set of two functions $x, y : G \to A$ is the set $\Delta(x, y) = \{i \in G \mid x(i) \ne y(i)\}$. Any submeasure over $G$ gives rise to an associated pseudodistance over $A^G$:

$$d_{\mu}(x, y) = \mu(\Delta(x, y)) \quad \forall x, y \in A^G.$$
**Remark 1.** The topological space corresponding to such a pseudodistance is homogeneous in the following sense: the balls around every two points $y$ and $z$ are isometric. Indeed, identify $A$ with the additive group $\mathbb{Z}/|A|\mathbb{Z}$. Then for every $y, z \in A^G$ the map $\psi_{y,z} : A^G \to A^G$ defined by $\psi_{y,z}(x)(i) = x(i) - y(i) + z(i)$ for every $x \in A^G$ and $i \in G$ is an isometry between any ball around $y$ and the corresponding one around $z$.

We say that submeasure $\mu$ is absolutely continuous (resp. $\alpha$-Lipschitz, for some $\alpha > 0$) with respect to submeasure $\nu$ if $\nu(W) = 0 \implies \mu(W) = 0$ (resp. $\mu(W) \le \alpha\nu(W)$) for any $W \subset G$.

**Remark 2.** Let $\varepsilon, \delta > 0$, $\mu$, $\nu$ two submeasures on $G$, and $z \in A^G$. The following are equivalent.

1. For every set $W \subset G$, $\mu(W) \ge \varepsilon \implies \nu(W) \ge \delta$.

2. For every $x, y \in A^G$, $d_\mu(x, y) \ge \varepsilon \implies d_\nu(x, y) \ge \delta$.

3. For every $x \in A^G$, $d_\mu(x, z) \ge \varepsilon \implies d_\nu(x, z) \ge \delta$.

Consequently, the identity map, from space $A^G$ endowed with $d_\nu$ onto space $A^G$ endowed with $d_\mu$, is continuous (resp. $\alpha$-Lipschitz) if and only if $\mu$ is absolutely continuous (resp. $\alpha$-Lipschitz) with respect to $\nu$. In that case the identity is even absolutely continuous.

## 2.2 Shifts and translations

If $A$ is an alphabet, $G$ is a group, and $g \in G$, the *shift* by $g$ is the function $\sigma^g : A^G \to A^G$ defined by $\sigma^g(x)(i) = x(g^{-1}i)$, for every $x \in A^G$ and $i \in G$. A map $\psi$ from $A^G$ to itself is *shift-invariant* if $\psi\sigma^g = \sigma^g\psi$ for every $g \in G$. Note that $\Delta(\sigma^g(x), \sigma^g(y)) = g\Delta(x, y)$ for every $x, y \in A^G$ and $g \in G$.

Since the maps $\psi_{y,z}$ from Remark 1 are shift-invariant, one can see that the shift is continuous, Lipschitz, etc in every $x$ if and only if it is in one $x$.

Given $g \in G$, let $g\mu(X) = \mu(g^{-1}X)$ for every $X \subset G$. Then $d_\mu(\sigma^g(x), \sigma^g(y)) = d_{g^{-1}\mu}(x, y)$, that is, the shift by $g$, within space $A^G$ endowed with $d_\mu$, is topologically the same as the identity map, from $A^G$ endowed with $d_\mu$ onto space $A^G$ endowed with $d_{g^{-1}\mu}$. Remark 1 can then be rephrased into the following.

**Remark 3.** If $G$ is a group, $g \in G$, and $A^G$ is endowed with $d_\mu$, then $\sigma^g$ is continuous (resp. $\alpha$-Lipschitz) if and only if $g^{-1}\mu$ is absolutely continuous (resp. $\alpha$-Lipschitz) with respect to $\mu$. In that case, the shift by $g$ is even absolutely continuous.

## 2.3 Besicovitch submeasure and pseudodistance

Among classical examples of submeasures are the ones that induce the Cantor topology, the shift-invariant Besicovitch pseudodistance, the Weyl pseudodistance (see [HM17, Def 4.1.1]. . . We will focus on the Besicovitch topology. Let $X$ and $Y$ be nonempty sets and let $(X_n)$ be a nondecreasing sequence of finite
subsets of X. We may or may not require that $(X_n)$ be exhaustive, that is, $\bigcup_n X_n = X$.

Let us denote $\mathfrak{P}(W|V) = \frac{|W \cap V|}{|V|}$ (by convention, this is $+\infty$ if $V = \emptyset$).

The Besicovitch submeasure $\mu_{(X_n)}: 2^X \to [0, 1]$ is defined by:

$$ \mu_{(X_n)}(W) = \limsup_n \mathfrak{P}(W|X_n). $$

The Besicovitch pseudodistance is $d_{(X_n)} = d_{\mu_{(X_n)}}$.

For example, if $X = \mathbb{N}$, $Y = \{0, 1\}$, and $X_n = [0: n - 1]$, $x(i) = 0$ for every $i \in \mathbb{N}$ and $y \in \{0, 1\}^\mathbb{N}$ is the characteristic function of the prime numbers, then $d_{(X_n)}(x, y) = 0$. The topology of the quotient space is very different from the prodiscrete topology.

We will now concentrate on the case of nondecreasing sequences $(X_n)$.

# 3 Følner equivalence and Besicovitch submeasures

## 3.1 Følner equivalence

Let $(X_n)$ and $(Y_n)$ be nondecreasing sequences of finite subsets of $G$. We say that they are synchronously Følner-equivalent if

$$ \lim_{n \to \infty} \frac{|X_n \Delta Y_n|}{|X_n|} = 0. $$

**Proposition 1.** Consider nondecreasing sequences $(X_n)$ and $(Y_n)$. The following are equivalent.

1. $(X_n)$ and $(Y_n)$ are synchronously Følner-equivalent.

2. $|X_n \cap Y_n| \sim_{n \to \infty} |X_n| \sim_{n \to \infty} |Y_n|$.

3. $|X_n| \sim_{n \to \infty} |Y_n|$ and $|X_n \setminus Y_n| = o_{n \to \infty}(|X_n|)$.

**Corollary 1.** The synchronous Følner equivalence is an equivalence relation.

The proofs are left to the reader (see [CGN] for details).

We also denote $(X_n) \preceq (Y_n)$ if $(X_n)$ is synchronously Følner-equivalent to a subsequence $(Y_{m_n})$. Equivalently,

$$ \lim_{n \to \infty} \min_{m \in \mathbb{N}} \frac{|X_n \Delta Y_m|}{|X_n|} = 0. $$

To be convinced of the equivalence, note that the minimum is reached by some $m_n$ for each $n \in \mathbb{N}$, because $(Y_m)$ is nondecreasing and $X_n$ is finite. Thanks to symmetry of synchronous equivalence, we also have that $(X_n) \preceq (Y_n)$ if and only if $\lim_{n \to \infty} \min_{m \in \mathbb{N}} \frac{|X_n \Delta Y_m|}{|Y_m|} = 0$. We say that they are Følner-equivalent, and write $(X_n) \sim (Y_n)$, if both $(X_n) \preceq (Y_n)$ and $(Y_n) \preceq (X_n)$. This is the case if they are synchronously Følner equivalent, but the converse is false. As counterexamples, one can consider twice the same sequence, but with repetitions on both sides that are longer and longer, and not synchronized. If one wants to obtain strictly increasing sequences, repetitions can be replaced by very slowly increasing sequences (point by point).
**Remark 4.** It is easy to see that $\leq$ is a preorder relation. In turn, Følner-equivalence, being defined as the equivalence corresponding to the preorder $\leq$, is an equivalence relation.

**Proposition 2.** Assume that $|X_n| \sim_{n \to \infty} |Y_n|$. Then $(X_n)$ and $(Y_n)$ are syn- chronously Følner-equivalent if and only if $(X_n) \leq (Y_n)$.

*Proof.* Assume $(X_n) \leq (Y_n)$ (the converse implication is trivial). Let $n, m \in \mathbb{N}$. If $m \leq n$, then $|X_n \setminus Y_n| \leq |X_n \setminus Y_m|$ and $|Y_n \setminus X_n| \leq |Y_n \setminus Y_m| + |Y_m \setminus X_n|$ since $(Y_n)$ is nondecreasing. Summing up, $|X_n \Delta Y_n| \leq |X_n \Delta Y_m| + |Y_n \setminus Y_m|$. Symmetrically, if $n \leq m$, $|X_n \Delta Y_n| \leq |X_n \Delta Y_m| + |Y_m \setminus Y_n|$. Overall for every $m \in \mathbb{N}$, we get $|X_n \Delta Y_n| \leq |X_n \Delta Y_m| + ||Y_m| - |Y_n||$. If we apply this with $(m_n)$ the subsequence from the definition of $\leq$, which is such that $(X_n) \sim (Y_{m_n})$, we have $|X_n \Delta Y_{m_n}| = o_{n \to \infty}(|X_n|)$, and by Proposition 1 (applied to $(X_n)$ and $(Y_{m_n}))$, $|Y_{m_n}| \sim_{n \to \infty} |X_n| \sim_{n \to \infty} |Y_n|$. Summing up, we deduce that $|X_n \Delta Y_n| = o_{n \to \infty}(|X_n|)$. $\square$

## 3.2 Comparing Besicovitch submeasures

A basic tool in our set constructions will be the following elementary remark.

**Remark 5.** If $(X_n)$ is nondecreasing and exhaustive, then for every finite set $W$ and every $\varepsilon > 0$, there exists $n_{(X_n)}(W, \varepsilon)$ such that $\forall n \geq n_{(X_n)}(W, \varepsilon)$, $\mathfrak{P}(W|X_n) < \varepsilon$ and $W \subset X_n$.

We deduce the following, which will be useful in our constructions.

**Lemma 1.** Let $(X_n)$ be a nondecreasing exhaustive sequence of an infinite group $G$. Let $W = \bigcup_{i \in \mathbb{N}} W_i$ where $\emptyset \neq W_i \in G$ for each $i \in \mathbb{N}$, such that, for every $n \in \mathbb{N}$, there are at most finitely many $i$'s such that $W_i \cap X_n \neq \emptyset$ (this is the case, for example, if the $W_i$'s are pairwise disjoint); in that case $j_n = \max_{W_j \cap X_n \neq \emptyset} j$ is well-defined for every $n$. Then:

1.

$$ \mu_{(X_n)}(W) \geq \limsup_{i \to \infty} \max_{m \in \mathbb{N}} \mathfrak{P}(W_i | X_m) . $$

2. If there is a sequence $(\varepsilon_n)$ converging to 0 such that $n_{(X_n)}(\bigcup_{i<j_n} W_i, \varepsilon_n) \leq n$ for every $n \in \mathbb{N}$, then:

$$ \mu_{(X_n)}(W) = \limsup_{i \to \infty} \max_{m \in \mathbb{N}} \mathfrak{P}(W_i | X_m) . $$

3. In general, there exists a nondecreasing integer sequence $l$ such that, denoting $W_l = \bigcup_{i \in \mathbb{N}} W_{l_i}$:

$$ \mu_{(X_n)}(W_l) = \lim_{i \to \infty} \max_{m \in \mathbb{N}} \mathfrak{P}(W_{l_i} | X_m) . $$

*Proof.*
1. Let $(m_i) \in \mathbb{N}^\mathbb{N}$ be such that $\mathfrak{P}(W_i|X_{m_i}) = \max_{m \in \mathbb{N}} \mathfrak{P}(W_i|X_m)$. We know that this sequence goes to infinity (even though it may not be nondecreasing), because only finitely many $W_i$'s intersect each $X_m$, but they all intersect at least one. Hence, $\mu_{(X_n)}(W) \ge \limsup_{i \to \infty} \mathfrak{P}(W|X_{m_i})$. We get the desired inequality by noting that $W_i \subset W$.

2. Point 1 already gives one inequality. For the converse:

$$ 
\begin{align*}
\mu_{(X_n)}(W) &= \limsup_{n \to \infty} \mathfrak{P} \left( \bigcup_{i<j_n} W_i \cup W_{j_n} \cup \bigcup_{i>j_n} W_i \middle| X_n \right) \\
&\le \limsup_{n \to \infty} \left( \mathfrak{P} \left( \bigcup_{i<j_n} W_i \middle| X_n \right) + \mathfrak{P}(W_{j_n} | X_n) + \mathfrak{P} \left( \bigcup_{i>j_n} W_i \middle| X_n \right) \right) \\
&\le \limsup_{n \to \infty} \left( \varepsilon_n + \max_{m \in \mathbb{N}} \mathfrak{P}(W_{j_n} | X_m) + 0 \right) \\
&\le \limsup_{n \to \infty} \varepsilon_n + \limsup_{n \to \infty} \max_{m \in \mathbb{N}} \mathfrak{P}(W_{j_n} | X_m) \\
&\le 0 + \limsup_{i \to \infty} \max_{m \in \mathbb{N}} \mathfrak{P}(W_i | X_m) .
\end{align*}
$$

The last inequality comes from the fact that the sequence $(j_n)$ is nondecreasing (because $(X_n)$ is nondecreasing), and not upper-bounded (because the $W_i$'s are nonempty), so it goes to infinity.

3. Let us define some sequence $l$ by recurrence, from any seed $l_0 \in \mathbb{N}$. Assume that $l_n$ is defined, and write $k_n = n_{(X_n)}(\bigcup_{j \le n} W_{l_j})$. Choose any $l_{n+1}$ such that for every $m \ge l_{n+1}$, $W_m$ does not intersect $X_{k_n-1}$ (this is possible by assumption). If $j_n = \max_{W_{l_j} \cap X_n \ne \emptyset} j$, then $n_{(X_n)}(\bigcup_{j<j_n} W_{l_j}) = k_{j_n-1}$. By definition, $W_{l_{j_n}}$ does not intersect $X_{k_{j_n-1}-1}$. Since $W_{l_{j_n}}$ intersects $X_n$, we can deduce that $n > k_{j_n-1}-1$. This means that $(W_{l_i})$ satisfies the hypothesis of Point 2.

Replacing the $\limsup$ by a $\lim$ can be achieved by taking a subsequence. $\square$

**Lemma 2.** Let $\varepsilon, \delta > 0$, and $(X_n), (Y_n)$ be nondecreasing and exhaustive. The following are equivalent.

1. For every $W \subset G$, if $\mu_{(Y_n)}(W) \ge \varepsilon$, then $\mu_{(X_n)}(W) \ge \delta$.

2. $\liminf_{n \in \mathbb{N}} \max_{m \in \mathbb{N}} \frac{\varepsilon |Y_n| - |Y_n \setminus X_m|}{|X_m|} \ge \delta$.

If $m_n$ realizes the maximum for each $n \in \mathbb{N}$, and if $\varepsilon < 1$, then these properties
imply that

$$ \frac{\delta}{\varepsilon} \le \liminf_{n \in \mathbb{N}} \frac{|Y_n|}{|X_{m_n}|} \le \limsup_{n \in \mathbb{N}} \frac{|Y_n|}{|X_{m_n}|} \le \frac{1-\delta}{1-\varepsilon}. $$

In particular, the properties imply that $\delta \le \varepsilon$.

*Proof.*
Let us start by proving the final inequalities. Suppose $\liminf_{n \in \mathbb{N}} \frac{\varepsilon|Y_n| - |Y_n \setminus X_{m_n}|}{|X_{m_n}|} \ge \delta$. Then on the one hand, it is clear that $\liminf_{n \in \mathbb{N}} \frac{\varepsilon|Y_n|}{|X_{m_n}|}$ is even bigger, which gives the first inequality. On the other hand, since $|Y_n \setminus X_{m_n}| \ge |Y_n| - |X_{m_n}|$, we can see that $\liminf_{n \in \mathbb{N}} (\varepsilon - 1) \frac{Y_n}{X_{m_n}} + 1 \ge \liminf_{n \in \mathbb{N}} \frac{\varepsilon|Y_n| - |Y_n \setminus X_{m_n}|}{|X_{m_n}|} \ge \delta$, which gives that $\limsup_{n \in \mathbb{N}} \frac{|Y_n|}{|X_{m_n}|} \le \frac{1-\delta}{1-\varepsilon}$, provided that $\varepsilon < 1$.

2$\Rightarrow$1 If property 2 is satisfied and $\mu_{(Y_n)}(W) \ge \varepsilon$, then:

$$
\begin{align*}
\mu_{(X_n)}(W) &\ge \limsup_{n \to \infty} \mathfrak{P} (W \cap Y_n | X_{m_n}) \\
&\ge \limsup_{n \to \infty} \frac{|W \cap Y_n| - |Y_n \setminus X_{m_n}|}{|X_{m_n}|} \\
&= \limsup_{n \to \infty} \left( \frac{\varepsilon|Y_n| - |Y_n \setminus X_{m_n}|}{|X_{m_n}|} + \frac{|W \cap Y_n| - \varepsilon|Y_n|}{|Y_n|} \frac{|Y_n|}{|X_{m_n}|} \right) \\
&\ge \liminf_{n \to \infty} \frac{\varepsilon|Y_n| - |Y_n \setminus X_{m_n}|}{|X_{m_n}|} \\
&\quad + \left( \limsup_{n \to \infty} \frac{|W \cap Y_n|}{|Y_n|} - \varepsilon \right) \liminf_{n \in \mathbb{N}} \frac{|Y_n|}{|X_{m_n}|} \\
&\ge \delta + 0 - \frac{\delta}{\varepsilon} \quad \text{by the two premises and the first inequalities.}
\end{align*}
$$

1$\Rightarrow$2 Assume that $\liminf_{i \to \infty} \frac{\varepsilon|Y_i| - |Y_i \setminus X_{k_i}|}{|X_{k_i}|} < \delta$. Let us build a set $W$ that contradicts Point 1.

For each $n \in \mathbb{N}$, there exists $k_n = \min\{k | |Y_n \setminus X_k| \le \varepsilon |Y_n|\}$, because for large $k$, $Y_n \setminus X_k = \emptyset$ (because $(X_k)$ is exhaustive and $Y_n$ is finite). By noting that $(Y_n \cap X_{k_n}) \setminus X_{k_{n-1}} = (Y_n \setminus X_{k_{n-1}}) \setminus (Y_n \setminus X_{k_n})$ (by convention $X_{-1}$ is empty), we can write that $|(Y_n \cap X_{k_n}) \setminus X_{k_{n-1}}| = |Y_n \setminus X_{k_{n-1}}| - |Y_n \setminus X_{k_n}|$, which is bigger than $\varepsilon |Y_n| - |Y_n \setminus X_{k_n}|$, by minimality of $k_n$. Hence $(Y_n \cap X_{k_n}) \setminus X_{k_{n-1}}$ admits a subset $Z_n$ of cardinality $|Z_n| = \lfloor \varepsilon |Y_n| \rfloor - |Y_n \setminus X_{k_n}|$. Define $W_n = (Y_n \setminus X_{k_n}) \sqcup Z_n$. Note that $W_n \subset Y_n$, and that $\varepsilon - \frac{1}{|Y_n|} < \mathfrak{P}(W_n|Y_n) \le \varepsilon$.

The $W_i$ satisfy the hypotheses of Lemma 1, so that Point 3 gives $1 \in \mathbb{N}^\mathbb{N}$, with $\mu_{(X_n)}(W_1) = \lim_{i \to \infty} \max_{m \in \mathbb{N}} \mathfrak{P}(W_{l_i} | X_m)$. By construction, we have:

$$
\begin{align*}
\mathfrak{P}(W_i | X_m) &= \mathfrak{P}(Y_i \setminus X_{k_i} | X_m) + \mathfrak{P}(Z_i | X_m) \\
&= \frac{|Y_i \setminus X_m \setminus X_{k_i}| + |Z_i \setminus X_m|}{|X_m|}.
\end{align*}
$$

If $m < k_i$, then $X_m \subseteq X_{k_i}$, and $Z_i \cap X_m \subseteq Z_i \cap X_{k_{i-1}} = \emptyset$, so that this quantity is 0. On the contrary, if $m \ge k_i$, then $Z_i \subseteq X_{k_i} \subseteq X_m$, and
$Y_i \cap X_m \setminus X_{k_i} = (Y_i \setminus X_{k_i}) \setminus (Y_i \setminus X_m)$, so that:

$$
\begin{align*}
\mathfrak{P}(W_i | X_m) &= \frac{|Y_i \cap X_m \setminus X_{k_i}| + |Z_i \cap X_m|}{|X_m|} \\
&= \frac{|Y_i \cap X_m \setminus X_{k_i}| + |Z_i|}{|X_m|} \\
&= \frac{|Y_i \setminus X_{k_i}| - |Y_i \setminus X_m| + \lfloor \varepsilon |Y_i| \rfloor - |Y_i \setminus X_{k_i}|}{|X_m|} \\
&\le \max_{m \in \mathbb{N}} \frac{|\lfloor \varepsilon |Y_i| \rfloor - |Y_i \setminus X_m|}{|X_m|} \\
&< \delta \text{ by hypothesis.}
\end{align*}
$$

Taking the limit, we get that $\mu_{(X_n)}(W_1) < \delta$.

On the other hand, applying now Point 1 of Lemma 1 to sequence $(Y_n)$:

$$
\mu_{(Y_n)}(W_1) \geq \lim_{i \in \mathbb{N}} \max_{m \in \mathbb{N}} \mathfrak{P}(W_{l_i} | Y_m) \geq \mathfrak{P}(W_{l_i} | Y_{l_i}) = \varepsilon. \square
$$

The previous lemma now allows to characterize the main properties of interest
for comparing two Besicovitch submeasures.

**Theorem 1.** Let $(X_n)$ and $(Y_n)$ be nondecreasing and exhaustive.

1. $\mu_{(Y_n)}$ is $\lambda$-Lipschitz with respect to $\mu_{(X_n)}$, where $\lambda > 0$, if and only if

$$
\forall \varepsilon > 0, \liminf_{n \to \infty} \max_{m \in \mathbb{N}} \frac{|Y_n - \frac{1}{\varepsilon} |Y_n \setminus X_m|}{|X_m|} \geq \frac{1}{\lambda} .
$$

2. $\mu_{(Y_n)}$ is absolutely continuous with respect to $\mu_{(X_n)}$ if and only if it is Lip-
schitz.

3. $\mu_{(Y_n)} \le \mu_{(X_n)}$ if and only if $(Y_n) \preceq (X_n)$.

4. $\mu_{(Y_n)} = \mu_{(X_n)}$ if and only if $(Y_n) \sim (X_n)$.

One can even see from the proof that $(Y_n) \preceq (X_n)$ if and only if there exists
$\varepsilon \in ]0, 1[$ such that $\forall W \subset G, \mu_{(X_n)}(W) < \varepsilon \implies \mu_{(Y_n)}(W) < \varepsilon$.

Proof.

1. Just note that the $\lambda$-Lipschitz property of $\mu_{(Y_n)}$ is equivalent to the proper-
ties in Lemma 2, for every $\delta$ and $\varepsilon = \lambda\delta$, and hence to:

$$
\liminf_{n \in \mathbb{N}} \max_{m \in \mathbb{N}} \frac{|Y_n - \frac{1}{\varepsilon} |Y_n \setminus X_m|}{|X_m|} \geq \frac{1}{\lambda} .
$$

2. From Lemma 2, $\mu_{(Y_n)}$ is absolutely continuous with respect to $\mu_{(X_n)}$ if and only if

$$
\forall \varepsilon > 0, \liminf_{n \to \infty} \max_{m \in \mathbb{N}} \frac{|Y_n - \frac{1}{\varepsilon} |Y_n \setminus X_m|}{|X_m|} > 0.
$$

From Point 1, this is equivalent to the existence of some $\lambda$ such that $\mu_{(Y_n)}$ is $\lambda$-Lipschitz with respect to $\mu_{(X_n)}$.
3. Let $(m_n) \in \mathbb{N}^\mathbb{N}$ satisfy $\lim_{n \to \infty} \frac{|Y_n \Delta X_{m_n}|}{|Y_n|} = 0$. Then

$$ \lim_{n \in \mathbb{N}} \frac{|Y_n| - \frac{1}{\epsilon} |Y_n \setminus X_{m_n}|}{|X_{m_n}|} = \lim_{n \in \mathbb{N}} \frac{|Y_n|}{|X_{m_n}|} \left( 1 - \frac{1}{\epsilon} \lim_{n \in \mathbb{N}} \frac{|Y_n \setminus X_{m_n}|}{|Y_n|} \right) = 1. $$

We can conclude by Point 1.

Conversely, suppose that

$$ \liminf_{n \in \mathbb{N}} \frac{|Y_n| - \frac{1}{\epsilon} |Y_n \setminus X_{m_n}|}{|X_{m_n}|} \ge 1. $$

By the last inequalities in Lemma 2, we know that $\lim_{n \in \mathbb{N}} \frac{|Y_n|}{|X_{m_n}|} = 1$. Moreover,

$$ \lim_{n \to \infty} \frac{|Y_n \setminus X_{m_n}|}{|X_{m_n}|} \le \lim_{n \to \infty} \frac{\epsilon |Y_n|}{|X_{m_n}|} - \epsilon \liminf_{n \in \mathbb{N}} \frac{|Y_n - \frac{1}{\epsilon} |Y_n \setminus X_{m_n}|}{|X_{m_n}|} = \epsilon - \epsilon = 0. $$

By Point 3 of Proposition 1, we obtain that $(Y_n) \preceq (X_n)$.

4. This is direct from the definitions and the Point 3. □

The following is direct from Theorem 1 and Remark 2.

**Corollary 2.** If $(X_n)$ and $(Y_n)$ are nondecreasing and exhaustive, then $(Y_n) \preceq (X_n)$ (resp. $(Y_n) \sim (X_n)$) if and only if the identity map from $A^G$ endowed with $d_{(X_n)}$ onto $A^G$ endowed with $d_{(Y_n)}$ is 1-Lipschitz (resp. an isometry).

Here are particular classes of sequences, where the proposition can be applied.

**Corollary 3.** Let $(X_n)$ and $(Y_n)$ be nondecreasing and exhaustive.

1. If there exist $\lambda > 0$ and a sequence $(m_n)$ such that $\liminf_{n \to \infty} \mathfrak{P}(X_n | Y_{m_n}) \ge \frac{1}{\lambda}$ and $X_n \subset Y_{m_n}$, then $\mu_{(X_n)}$ is $\lambda$-Lipschitz with respect to $\mu_{(Y_n)}$.

2. If for cofinitely many $n \in \mathbb{N}$, $Y_n \subset X_{n+1}$ and $\liminf_{n \to \infty} \mathfrak{P}(X_n | X_{n+1}) \ge \lambda$, then $\mu_{(X_n)}$ is $\lambda$-Lipschitz with respect to $\mu_{(Y_n)}$.

3. On the other hand, if $|X_n| \sim_{n \to \infty} |Y_n|$ but $(X_n)$ and $(Y_n)$ are not (syn chronously) Følner-equivalent, and $n_{(Y_n)}(X_n, \varepsilon_n) = n+1$ for some real sequence $(\varepsilon_n)$ converging to 0, then $\mu_{(X_n)}$ is not absolutely continuous with respect to $\mu_{(Y_n)}$.

Proof.

1. For every $\varepsilon > 0$,

$$ \liminf_{n \to \infty} \max_{m \in \mathbb{N}} \frac{|X_n| - \frac{1}{\epsilon} |X_n \setminus Y_m|}{|Y_m|} \ge \liminf_{n \to \infty} \frac{|X_n| - \frac{1}{\epsilon} |X_n \setminus Y_{m_n}|}{|Y_{m_n}|} = \liminf_{n \to \infty} \frac{|X_n|}{|Y_{m_n}|} \ge \frac{1}{\lambda}. $$

2. Apply Point 1 with $m_n = \min\{m \in \mathbb{N} | X_n \subset Y_m\}$; the hypothesis is that $m_n$ is ultimately $n+1$.
3. Suppose $|X_n| \sim_{n \to \infty} |Y_n|$ and $(X_n)$ and $(Y_n)$ are not synchronously Følner-equivalent. By Proposition 2, $(X_n) \not\le (Y_n)$, that is, $\varepsilon = \lim \sup_{n \to \infty} \frac{|X_n \setminus Y_n|}{|Y_n|} > 0$. We can write $\lim \inf_{n \to \infty} \frac{|X_n| - \frac{1}{\varepsilon} |X_n \setminus Y_n|}{|Y_n|} = 0$.

By the second assumption, for every $m > n$, $X_n \setminus Y_m = \emptyset$ and $\frac{|X_n|}{|Y_m|} \le \varepsilon_n$. We get:

$$ \max_{m \in \mathbb{N}} \frac{|X_n| - \frac{1}{\varepsilon} |X_n \setminus Y_m|}{|Y_m|} \le \max \left( \frac{|X_n| - \frac{1}{\varepsilon} |X_n \setminus Y_n|}{|Y_n|}, \varepsilon_n \right). $$

Putting things together, $\lim \inf_{n \to \infty} \max_{m \in \mathbb{N}} \frac{|X_n| - \frac{1}{\varepsilon} |X_n \setminus Y_m|}{|Y_m|}$ is 0. We conclude by Point 2 of Theorem 1. $\square$

**Corollary 4.** Let $(X_n)$ and $(Y_n)$ be nondecreasing and exhaustive. Assume that $|X_n| \sim_{n \to \infty} |Y_n|$. Then the following are equivalent.

1. $(X_n)$ and $(Y_n)$ are synchronously Følner-equivalent.

2. $\mu_{(Y_{l_n})} = \mu_{(X_{l_n})}$, for every increasing sequence $(l_n) \in \mathbb{N}^\mathbb{N}$.

3. $\mu_{(Y_{l_n})}$ is absolutely continuous with respect to $\mu_{(X_{l_n})}$, for every increasing sequence $(l_n)$.

*Proof.*

1. $\implies$ 2 If $(X_n)$ and $(Y_n)$ are synchronously Følner equivalent, then so are $(X_{l_n})$ and $(Y_{l_n})$ for every increasing $(l_n) \in \mathbb{N}^\mathbb{N}$. We conclude thanks to Theorem 1.

2. $\implies$ 3 This is obvious.

3. $\nexists$ $\varphi$ If $(X_n)$ and $(Y_n)$ are not synchronously Følner-equivalent, then there exists an infinite set $I \subset \mathbb{N}$ and a real number $\alpha > 0$ such that $\forall n \in I$, $\frac{|X_n \setminus Y_n|}{|X_n|} \ge \alpha$. This implies that for every increasing sequence $(l_n) \in I^\mathbb{N}$, $(X_{l_n})$ and $(Y_{l_n})$ are not synchronously Følner-equivalent. We can take an increasing sequence $(l_n) \in I^\mathbb{N}$ such that $n_{(Y_m)}(X_{l_n}, \varepsilon_{l_n}) = l_{n+1}$, for some real sequence $(\varepsilon_n)$ converging to 0. Then $(X_{l_n})$ and $(Y_{l_n})$ satisfy the assumptions for Point 3 of Corollary 3.

### 3.3 Shift

If $G$ is a group and $(X_n) \sim (gX_n)$, then we say that $(X_n)$ is (left) g-Følner; $(X_n)$ is right g-Følner if $(X_n^{-1})$ is left $g^{-1}$-Følner. Since $|X_n| = |gX_n|$, Proposition 2 says that it is enough to require $(X_n) \preceq (gX_n)$, and in this case, $(X_n)$ and $(gX_n)$ are even synchronously Følner-equivalent.

A (left) Følner sequence for a countable group $G$ is a g-Følner sequence for every $g \in G$. A countable group is amenable if and only if it admits a Følner sequence: see [CSC10, Chapter 4] also for many equivalent definitions.
The following is a rephrasing of Corollary 2.

**Corollary 5.** Let $G$ be a countable group and let $(X_n)$ be a nondecreasing exhaustive sequence.
1. $(X_n)$ is $g$-Følner if and only if $\mu_{(X_n)} = \mu_{(g^{-1}X_n)}$ if and only if the shift by $g$ is an isometry.

2. $(X_n)$ is Følner if and only if every shift is an isometry.

3. If $G$ is finitely generated (see below) then it is amenable if and only if there exists a nondecreasing exhaustive sequence $(X_n)$ of finite subsets of $G$ such that every shift is an isometry.

Note that one implication of Point 3 was already stated in [Cap09, Theorem 3.5], but the proof contains a confusion between left and right Følner.

A group $G$ is finitely generated (briefly, f.g.) if $E \subseteq G$ exists such that for every $g \in G$ there exists $e_1, \dots, e_n \in E \cup E^{-1}$ such that $e_1 \cdots e_n = g$. Remarkably (cf. [Pet, Lemma 5.3]) if a f.g. group is amenable, then it has a nondecreasing exhaustive Følner sequence. In addition, if the size of the balls grows polynomially with the radius, then they form a Følner sequence, so Point 3 of Corollary 5 generalizes [HM17, Cor 4.1.4].

**Corollary 6.** Let $G$ be a finitely generated group.

1. If $(X_n)$ is the sequence of balls with respect to some generating set of cardinality $\alpha$, then every shift is $\alpha$-Lipschitz.

2. If $g \in G$, a nondecreasing exhaustive sequence is $g$-Følner if and only if all of its subsequences yield a Besicovitch pseudodistance for which the shift by $g$ is continuous.

3. $G$ is amenable if and only if it admits a nondecreasing exhaustive sequence of finite subsets of which all subsequences yield a Besicovitch distance for which every shift is continuous.

The first point generalizes [HM17, Prop 4.1.3]. Note that it still applies in non-amenable groups, but the shifts are no longer isometries, and there is a sub-sequence of balls with respect to which the Besicovitch pseudodistance makes them non-continuous.

*Proof.*

1. If $E$ is the generating set and $E_n$ the corresponding radius-$n$ ball, then $E_0 = \{e\}$ where $e$ is the identity of $G$ and $E_{n+1} = (E \cup E^{-1}) \cdot E_n$, so $|E_n| \le (2|E| + 1)^n$. We can apply Point 2 of Corollary 3.

2. This comes from Corollary 4.

3. This comes from Point 2. $\square$

There are nondecreasing non-Følner sequences for which the shift is Lipschitz (but not an isometry) in $\mathbb{Z}^d$. Here's an example: $X_n = ([-n, n] \cup 2[-n, n])^d$. Indeed, for every $n$, $1 + X_n \subset X_{2n}$ and $\frac{|X_{2n}|}{|X_n|} = \frac{(8n-1)^d}{(4n-1)^d}$, which converges to $2^d$ when $n$ goes to infinity. We conclude by Point 1 of Corollary 3, with $m_n = 2n$ and $\alpha = 2^d$. But the shift is not an isometry because the sequence is not Følner: $\mu((2\mathbb{Z})^d) = 2^d/3^d > \mu((2\mathbb{Z} + 1)^d) = 1/3^d$.

"Dually" to shifts, we can define the propagation $\pi^g: A^G \to A^G$ by $\pi^g(x)(i) = x(ig)$. A block map (see [LM95] for $G = \mathbb{Z}$) is, in essence, a composition of a
radius-0 function with a product of propagations. The same characterizations
are true for propagations as for shift maps, to which we can derive the following:

**Corollary 7.** A nondecreasing exhaustive sequence $(X_n)$ of finite subsets of a f.g. group $G$ is right Følner if and only if for every increasing sequence $(l_n) \in \mathbb{N}^\mathbb{N}$, every block map with neighborhood size $k$ is $k$-Lipschitz for $d_{(X_{l_n})}$.

# 4 Conclusions

We have presented a way to compare Besicovitch submeasures (in terms of abso-
lute continuity, Lipschitz continuity, equality) thanks to the sequences of finite
sets which describe them. In a shift space (with respect to a finitely generated
group) endowed with the Besicovitch topology, we have derived conditions on the
defining sequence for the shift maps to be continuous, Lipschitz or isometries.
As part of this, we gave another characterization of f.g. amenable groups.

Future work will involve the study of other topological and dynamical prop-
erties (cf. [CGN]) or extension to configuration spaces on possibly uncountable
groups. The latter would require the use of the more general notions of *directed set* and of *net*, and although the definition of Besicovitch pseudodistance and
submeasure would be immediate to extend, the techniques used to prove the
main lemmas could need a major revision.

# References

BFK99. François Blanchard, Enrico Formenti, and Petr Kůrka. Cellular automata in the Cantor, Besicovitch and Weyl spaces. *Complex Systems*, 11:107–123, 1999.

Cap09. Silvio Capobianco. Surjunctivity for cellular automata in Besicovitch spaces. *Journal of Cellular Automata*, 4:89–98, 2009.

CGK13. Silvio Capobianco, Pierre Guillon, and Jarkko Kari. Surjective cellular automata far from the Garden of Eden. *Discrete Mathematics and Theoretical Computer Science*, 15:41–60, 2013.

CGN. Silvio Capobianco, Pierre Guillon, and Camille Noûs. Besicovitch pseudodistances with respect to non-Følner sequences. Preprint, (hal-02566187), 2020.

CSC10. Tullio G. Ceccherini-Silberstein and Michel Coornaert. *Cellular Automata and Groups*. Springer Verlag, 2010.

HM17. Karl-Peter Hadeler and Johannes Müller. *Cellular Automata: Analysis and Applications*. Springer, 2017. 00000.

LM95. Douglas Lind and Brian Marcus. *An Introduction to Symbolic Dynamics and Coding*. Cambridge University Press, 1995.

Pet. Gábor Pete. Probability and geometry on groups. Lecture notes. May 19, 2019. http://math.bme.hu/~gabor/PGG.pdf.

Sab06. Mathieu Sablik. *Étude de l'action conjointe d'un automate cellulaire et du décalage: une approche topologique et ergodique*. PhD thesis, Université de Provence, July 2006.