# Logic Blog 2020 (the 10th anniversary blog)

Editor: André Nies<EMAIL_ADDRESS>
###### Contents

  1. I Group theory and its connections to logic
    1. 1 Nies and Stephan: non-word automatic free nil-2 groups
    2. 2 Nies: open questions on classes of closed subgroups of $S_{\infty}$
    3. 3 Ivanov and Majcher: amenable subgroups of $S(\omega)$
    4. 4 Nies: Stone-type duality for totally disconnected locally compact groups
    5. 5 Nies: Closed subgroups of $S(\omega)$ generated by their permutations of finite support
    6. 6 Harrison-Trainor and Nies: $\Pi_{r}$-pseudofinite groups
  2. II Computability theory and randomness
    1. 7 Greenberg, Nies and Turetsky: Characterising SJT reducibility
    2. 8 Nies and Stephan: Update on the SMB theorem for measures
    3. 9 Nies and Tomamichel: the measure associated with an infinite sequence of qubits
  3. III Set theory
    1. 10 Yu: perfect subsets of uncountable sets of reals

The Logic Blog is a shared platform for

  * •

rapidly announcing results and questions related to logic

  * •

putting up results and their proofs for further research

  * •

parking results for later use

  * •

getting feedback before submission to a journal

  * •

foster collaboration.

Each year’s blog is posted on arXiv a 2-3 months after the year has ended.

Logic Blog 2019 | (Link: http://arxiv.org/abs/2003.03361)
---|---
Logic Blog 2018 | (Link: http://arxiv.org/abs/1902.08725)
Logic Blog 2017 | (Link: http://arxiv.org/abs/1804.05331)
Logic Blog 2016 | (Link: http://arxiv.org/abs/1703.01573)
Logic Blog 2015 | (Link: http://arxiv.org/abs/1602.04432)
Logic Blog 2014 | (Link: http://arxiv.org/abs/1504.08163)
Logic Blog 2013 | (Link: http://arxiv.org/abs/1403.5719)
Logic Blog 2012 | (Link: http://arxiv.org/abs/1302.3686)
Logic Blog 2011 | (Link: http://arxiv.org/abs/1403.5721)
Logic Blog 2010 | (Link: http://dx.doi.org/2292/9821)

How does the Logic Blog work?

Writing and editing. The source files are in a shared dropbox. Ask André () in
order to gain access.

Citing. Postings can be cited. An example of a citation is:

H. Towsner, _Computability of Ergodic Convergence_. In André Nies (editor),
Logic Blog, 2012, Part 1, Section 1, available at
http://arxiv.org/abs/1302.3686.

The logic blog, once it is on arXiv, produces citations e.g. on Google
Scholar.

##  Part I Group theory and its connections to logic

###  1\. Nies and Stephan: non-word automatic free nil-2 groups

We follow up on a post on word automaticity of various nilpotent groups by the
same guys last year [10, Section 6]. To be word automatic means that given an
appropriate encoding of the elements by strings, the domain and operations are
recognizable by finite automata. Other terms in use for this notion include
FA-presentable, and even “automatic”.

We supply a proof that examples of the last of three types that were provided
there are not word-automatic. The first two types were shown to be word
automatic there. For an odd prime $p$, let $L_{p}$ be the free nilpotent-2
exponent $p$ group of infinite rank. In the notation of [10, Section 6] one
has $N\cong Q$; let $y_{i,k}$ ($i<k$) be free generators of $N$; then $L_{p}$
is given by the function $\phi(x_{i},x_{k})=y_{i,k}$ if $i<k$. So we have

$L_{p}=\langle x_{i},y_{i,k}\mid
x_{i}^{p},[x_{i},x_{k}]y_{i,k}^{-1},[y_{i,k},x_{r}](i<k)\rangle$

thus the $y_{i,k}$ are actually redundant. This group in a sense generalises
the Heisenberg group over the ring $\mathbb{F}_{p}$, which would be the case
of two generators $x_{0},x_{1}$.

######  Theorem 1.1.

$L_{p}$ is not word automatic.

###### Proof.

Let $\alpha,\beta$ denote strings in the alphabet of digits $0,\ldots,{p-1}$,
which are thought of as extended by $0$’s if necessary. Let
$[\alpha]=\prod_{i<|\alpha|}x_{i}^{\alpha_{i}}$. Each element of $L_{p}$ has a
normal form

$[\alpha]\prod_{s<n}\prod_{r<s}[x_{r},x_{s}]^{\gamma_{r,s}}$

where $|\alpha|=n$ and $0\leq\gamma_{r,s}<p$. By the usual commutator rules in
a group that is nilpotent of class 2, for $|\alpha|=|\beta|=n$ and central
elements $c,d$,

$\big{[}[\alpha]c,[\beta]d\big{]}=\prod_{r<s\leq
n}[x_{r},x_{s}]^{\alpha_{r}\beta_{s}-\alpha_{s}\beta_{r}}.$

This identity will tacitly be used below.

Assume for a contradiction that $L_{p}$ has a finite automata presentation
with domain a regular set $D\subseteq\Sigma^{*}$, and FA-recognizable
operation $\circ$. Denote by $\preceq$ the length-lexicographical ordering on
$D$. Note that $\preceq$ can also be recognized by a finite automaton.

Let $C\subseteq D$ denote the regular set of strings that are in the centre of
$L_{p}$.

######  Claim 1.2.

For each finite set $S\subseteq D$, there is a $\preceq$-least string
$u=u_{S}\in D$ such that

  * (i)

$\forall r[r\in S-C\Rightarrow[r,u]\not\in S]$.

  * (ii)

$\forall v,w\in S([v,u]=[w,u]\to\exists c\in C\,cv=w)$.

To see this, let $k$ be so large that only $x_{i}$ with $i<k$ occur in the
normal form of any element of $S$, and let $u=x_{k}$.

For (i) note that $r$ contains some $x_{i}$ with $i<k$, so the normal form of
$[r,u]$ contains $[x_{i},x_{k}]$, while the normal form of an element of $S$
does not contain such commutators.

For (ii) let $v=[\alpha]c$ with $c$ central. Then the normal form of $[v,u]$
ends in $\prod_{i<k}[x_{i},x_{k}]^{\alpha_{i}}$, which allows us to recover
$\alpha$. This verifies the claim.

We now inductively define sequences
${\left\langle{z_{n}}\right\rangle}_{n\in{\mathbb{N}}}$ and
${\left\langle{u_{n}}\right\rangle}_{n\in{\mathbb{N}}}$ in $D$. Let $z_{0}$ be
the string representing the neutral element. Suppose now that $z_{n}$ has been
defined, and write $V_{n}$ for $\\{v\colon v\preceq z_{n}\\}$. Let $u_{n}$ be
$u_{S}$ for $S={V_{n}}$, where $u_{S}$ is defined in the claim above. Next let
$z_{n+1}$ be the $\preceq$-least string $z$ such that

(1.1) $\forall v,w\in V_{n}\,\bigwedge_{i<p}w\circ
u_{n}^{i}\circ[v,u_{n}]\preceq z.$

Note that $z_{n+1}=G(z_{n})$ for a function $G\colon D\to D$ that is first-
order definable in the structure $(D,\circ,\preceq)$. This implies that the
graph of $G$ can be recognized by a finite automaton in the usual sense of
automatic structures, and hence $|z_{n}|=O(n)$ by the pumping lemma.

In the following we write $u_{i,k}$ for $[u_{i},u_{k}]$ where $i\neq k$.

######  Claim 1.3.

For each $n$, the subgroup $\langle u_{0},\ldots,u_{n}\rangle$ generated by
$u_{0},\ldots,u_{n}$ is contained in $V_{n+1}$.

This is checked by induction on $n$. For $n=0$ we have $\langle
u_{0}\rangle\subseteq V_{1}$ because $w=v=1$ is allowed in (1.1). For the
inductive step, note that by the normal form (and freeness of $L_{p}$) each
element $y$ of $\langle u_{0},\ldots,u_{n}\rangle$ has the form

$\prod_{i\leq n}u_{i}^{\alpha_{i}}\prod_{s\leq
n}\prod_{r<s}[u_{r,s}]^{\gamma_{r,s}}$.

This can be rewritten as $wu_{n}^{\alpha_{n}}[v,u_{n}]$ where

$w=\prod_{i<n}u_{i}^{\alpha_{i}}\prod_{s<n}\prod_{r<s}[u_{r,s}]^{\gamma_{r,s}}$
and $v=\prod_{k<n}u_{k}^{\gamma_{k,n}}$.

By inductive hypothesis $w,v\in V_{n}$. So the element $y$ is in $V_{n+1}$ by
(1.1). This verifies the claim.

In the next claim we view elementary abelian $p$-groups as vector spaces over
the field $\mathbb{F}_{p}$.

######  Claim 1.4.

  * (a)

The elements $Cu_{i}$ are linearly independent in $G/C$.

  * (b)

The elements $u_{i,k}$ are linearly independent in $C$.

We use induction on a bound $n$ for the indices. For (a) note that
$u_{n+1}^{i}\not\in V_{n}C$ for $i<p$, for otherwise $v=u_{n+1}^{i}c\in V_{n}$
for some central $c$, and clearly $[v,u_{n+1}]=1$ contradicting the condition
(i) in Claim 1.2. Therefore $C\langle u_{n+1}\rangle\cap C\langle
u_{0},\ldots,u_{n}\rangle=0$.

For (b), inductively the $u_{i,k}$, $i<k\leq n$ are a basis for a subspace
$T_{0}\leq C$. The linear map given by $Cw\mapsto[w,u_{n+1}]$ is 1-1 by (ii)
of Claim 1.2. So, by (a), the $[u_{i},u_{n+1}]$ are independent, generating a
subspace $T_{1}$. The condition (i) of Claim 1.2 implies that $T_{0}\cap
T_{1}=0$. This concludes the inductive step and verifies the claim.

We now obtain our contradiction. Given $n$, by Claim 1.3 we have

$\prod_{i<k\leq n}u_{i,k}^{\gamma_{i},k}\in V_{n}$

for each double sequence ${\left\langle{\gamma_{i,k}}\right\rangle}_{i<k\leq
n}$ of exponents in $[0,p)$. By Claim 1.4 all these elements are distinct.
Since $V_{n}$ consists of strings of length $O(n)$, we have $p^{n^{2}/2}$
distinct strings of length $O(n)$, which is false for large enough $n$. ∎

###  2\. Nies: open questions on classes of closed subgroups of $S_{\infty}$

The following started in discussions with A. Kechris at Caltech in 2016. It is
well known that the closed subgroups of $S(\omega)$ form a Borel space, and
there is a Borel action of $S(\omega)$ by conjugation (see e.g. [25]). This is
because being a subgroup is a Borel property in the usual Effros space of
closed subsets of $S(\omega)$. A natural class of closed subgroups of
$S(\omega)$ should be closed under conjugation, and often even is closed under
topological isomorphism (an exception being oligomorphicness). Here we ask
which natural classes of closed subgroups of $S(\omega)$ are Borel. It turns
out that even for the simplest classes this can be a hard problem.

Once a class is known to be Borel, one can study the relative complexity of
the topological isomorphism problem for this class with respect to Borel
reducibility $\leq_{B}$. For instance, Kechris et al. [25] showed that for the
Borel properties of compactness, local compactness, and Roelcke
precompactness, the isomorphism relation is Borel equivalent to $\mathrm{GI}$,
the isomorphism of countable graphs. This worked by adapting Mekler’s result
described below.

Before proceeding, we import some preliminaries from [25].

#### Effros structure of a Polish space

Given a Polish space $X$, let $\mathcal{F}(X)$ denote the set of closed
subsets of $X$. The _Effros structure_ on $X$ is the Borel space consisting of
$\mathcal{F}(X)$ together with the $\sigma$-algebra generated by the sets

$\mathcal{C}_{U}=\\{D\in\mathcal{F}(X)\colon D\cap U\neq\emptyset\\}$,

for open $U\subseteq X$. Clearly it suffices to take all the sets $U$ in a
countable basis ${\left\langle{U_{i}}\right\rangle}_{i\in{\mathbb{N}}}$ of
$X$. The inclusion relation on $\mathcal{F}(X)$ is Borel because for
$C,D\in\mathcal{F}(X)$ we have $C\subseteq D\leftrightarrow\forall
i\in{\mathbb{N}}\,[C\cap U_{i}\neq\emptyset\to D\cap U_{i}\neq\emptyset]$.

#### Representing elements of the Effros structure of $S(\omega)$

For a Polish group $G$, we have a Borel actions
$G\curvearrowright\mathcal{F}(G)$ by translation and by conjugation. We will
only consider the case that $G=S(\omega)$. In the following $\sigma,\tau,\rho$
will denote injective maps on initial segments of the integers, that is, on
tuples of integers without repetitions. Let $[\sigma]$ denote the set of
permutations extending $\sigma$:

$\mathcal{[}\sigma]=\\{f\in S(\omega)\colon\sigma\prec f\\}$

(this is often denoted $\mathcal{N}_{\sigma}$ in the literature). The sets
$[\sigma]$ form a base for the topology of pointwise convergence of
$S(\omega)$. For $f\in S(\omega)$ let $f\\!\upharpoonright_{n}$ be the initial
segment of $f$ of length $n$. Note that the $[f\\!\upharpoonright_{n}]$ form a
basis of neighbourhoods of $f$. Given $\sigma,\sigma^{\prime}$ let
$\sigma^{\prime}\circ\sigma$ be the composition as far as it is defined; for
instance, $(7,4,3,1,0)\circ(3,4,6)=(1,0)$. Similarly, let $\sigma^{-1}$ be the
inverse of $\sigma$ as far as it is defined.

######  Definition 2.1.

For $n\geq 0$, let $\tau_{n}$ denote the function $\tau$ defined on
$\\{0,\ldots,n\\}$ such that $\tau(i)=i$ for each $i\leq n$.

######  Definition 2.2.

For $P\in\mathcal{F}(S(\omega))$, by $T_{P}$ we denote the tree describing $P$
as a closed set in the sense that $[T_{P}]\cap S(\omega)=P$. Note that
$T_{P}=\\{\sigma\colon\,P\in\mathcal{C}_{[\sigma]}\\}$.

######  Lemma 2.3.

The closed subgroups of $S(\omega)$ form a Borel set $\mathcal{U}(S(\omega))$
in $\mathcal{F}(S(\omega))$.

###### Proof.

$D\in\mathcal{F}(S(\omega))$ is a subgroup iff the following three conditions
hold:

  * •

$D\in\mathcal{C}_{[(0,1,\ldots,n-1)]}$ for each $n$

  * •

$D\in\mathcal{C}_{[\sigma]}\to D\in\mathcal{C}_{[\sigma^{-1}]}$ for all
$\sigma$

  * •

$D\in\mathcal{C}_{[\sigma]}\cap C_{[\tau]}\to
D\in\mathcal{C}_{[\tau\circ\sigma]}$ for all $\sigma,\tau$.

It now suffices to observe that all three conditions are Borel. ∎

Note that $\mathcal{U}(S(\omega))$ is a standard Borel space. The statement of
the lemma actually holds for each Polish group in place of $S(\omega)$.

So much for the preliminaries. We now note any known results on the complexity
of isomorphism. Let $G$ always denote a closed subgroup of $S(\omega)$
(another, and cumbersome, but persistent, term is non-Archimedean group). By
‘group’ we usually mean such a $G$.

##### The class of all closed subgroups of $S(\omega)$

It is not hard to verify that the isomorphism problem is analytic [25]. It is
Borel above ($\geq_{B}$) graph isomorphism $\mathrm{GI}$. Nothing else appears
to be known on its complexity. The following was asked in Kechris et al. [25].

######  Question 2.4.

Is the isomorphism relation between closed subgroups of $S(\omega)$ analytic
complete?

The isomorphism problem for abelian Polish groups is known to be analytic
complete [11], but the groups used there are not non-Archimedean (are
Archimedean?).

##### Discrete groups

Discreteness is Borel because it is equivalent to saying that the neutral
element is isolated. Note that $G$ is discrete iff $G$ is countable. The
isomorphism relation for discrete groups is Borel equivalent to graph
isomorphism. The upper bound is fairly standard, the lower bound is obtained
by A. Mekler’s technique [31] encoding countable graph isomorphism (for a
sufficiently rich class of graphs) into isomorphism of countable nil-2 groups
of exponent $p^{2}$, where $p$ is some fixed odd prime.

##### Procountable groups

The following are equivalent (see e.g. Malicki [29, Lemma 1]):

  * (i)

$G$ is procountable, i.e., an inverse limit of a chain of countable groups
$G_{n+1}\to G_{n}$

  * (ii)

$G$ is a closed subgroup of a Cartesian product of discrete groups

  * (iii)

there is nbhd base of the neutral element consisting of open normal subgroups.

It is also equivalent to ask that

  * (iv)

$G$ has a compatible bi-invariant metric (such a metric will be necessarily
complete because $G$ is a Polish group).

This class includes the abelian closed subgroups of $S(\omega)$ (see below),
and of course the discrete groups. So graph isomorphism GI can be reduced to
its isomorphism problem.

##### Abelian groups

To be abelian is easily seen to be Borel because

$G$ is abelian iff $\forall\sigma,\tau\in T_{G}\,[\sigma^{-1}\tau^{-1}\
\sigma\tau\prec\text{id}_{\omega}]$.

(In fact any variety of groups is Borel, by a similar argument.) As a
nonlocally compact example, consider ${\mathbb{Z}}^{\omega}$. Also there is a
universal abelian closed subgroup of $S(\omega)$.

Each abelian closed subgroup of $S(\omega)$ has an invariant metric and hence
is pro-countable by Malicki [30, Lemma 2], also Malicki [29, Lemma 1]. Su Gao
(On Automorphism Groups of Countable Structures, JSL, 1998) has proved that if
$\operatorname{Aut}(M)$ is abelian (or merely solvable) for a countable
structure $M$, then the Scott sentence of $M$ has no uncountable model.

##### Topologically finitely generated groups

This property is analytical. The symmetric group $S(\omega)$ is f.g. because
the group of permutations with finite support is dense in $S(\omega)$, and is
contained in a 2-generated group, namely the group generated by the successor
function on ${\mathbb{Z}}$ and the transposition $(0,1)$.

######  Question 2.5.

Is being topologically finitely generated Borel?

Given $k\geq 2$, is being $k$-generated Borel?

We observe that among the compact groups, being $k$-generated is Borel. For in
a Borel way we can represent $G$ as $\projlim_{n\in{\mathbb{N}}}G_{n}$ for
discrete finite groups $G_{n}$ (with some unnamed projections $G_{n+1}\to
G_{n}$). Then $G$ is $k$-generated iff each $G_{n}$ is $k$-generated: for the
nontrivial implication, for each $n$ let $\overline{a}_{n}$ be a $k$-tuple of
generators for $G_{n}$. Now take a converging subsequence of a sequence of
pre-images of the $\overline{a}_{n}$ in $G^{n}$. The limit generates $G$.

Being 1-generated (monothetic) is Borel, because as it is well known, such a
group is either discrete, or an inverse limit of cyclic groups (e.g.
$({\mathbb{Z}}_{p},+)$) and hence compact. See e.g. Malicki [29, Lemma 5].
Hewitt and Ross in their book have a more detailed structure theorem for such
groups.

Among the abelian groups, being f.g. is Borel because such a group is pro-
countable. If it is $k$-generated, it has to be an inverse limit of
$k$-generated countable abelian groups. An onto map
${\mathbb{Z}}^{s}\to{\mathbb{Z}}^{s}$ is of course a bijection. So $G$ is
$k$-generated iff $G$ is of the form ${\mathbb{Z}}^{r}\times H$ where $H$ is a
product of $k-r$ procyclic groups. This condition is Borel.

Outside the abelian, it is easy to provide an example of a complicated pro-
countable 2-generated group. In the free group $F(a,b)$ let
$v_{z}=b^{-z}ab^{z}$ ($z\in{\mathbb{Z}}$). For $k\in{\mathbb{N}}^{+}$ let
$N_{k}\leq F(a,b)$ be the normal subgroup generated by commutators
$[v_{0},v_{r}],r\geq k$. Then $N_{1}>N_{2}>\ldots$ and
$\bigcap_{k}N_{k}=\\{1\\}$. Let $G$ be the inverse limit of the system
${\left\langle{F(a,b)/N_{k}}\right\rangle}_{k\in{\mathbb{N}}}$ with the
natural projections.

##### Compactly generated groups

One says that $G$ is compactly generated if there is a compact subset $S$ that
topologically generates $G$. Note that if $G$ is locally compact, it has a
compact open subgroup $K$ (van Dantzig), so the compact subset $KS$ generates
$G$ algebraically.

######  Fact 2.6.

For locally compact groups $G\leq_{c}S(\omega)$, being compactly generated is
Borel.

To see this, note that if $G$ is c.g. iff it is topologically generated by a
compact open set $C$. Such a set $C$ is given as a finite union of sets
$[T_{G}]\cap[\sigma]$ for strings on $T_{G}$, and we can describe
arithmetically whether a set $[T_{G}]\cap[\sigma]$ is compact. So we have to
express that there is $C$ such that for each $\eta$ on $T_{G}$, there is a
term $t$ and finitely many $\sigma_{i}$ with $[\sigma_{i}]\cap T_{G}\subseteq
C$ so that $t$ applied to the $\sigma_{i}$ yields an extension of $\eta$. This
is arithmetical.

######  Question 2.7.

Is being (topologically) compactly generated Borel?

##### Oligomorphic groups

To be oligomorphic means that for each $n$ there are only finitely many
$n$-orbits. Equivalently the orbit structure $M_{G}$ is $\omega$-categorical.
By Coquand’s work (elaborated in Ahlbrandt and Ziegler [2]) oligomorphic
groups $G,H$ are isomorphic iff $M_{G}$ and $M_{H}$ are bi-interpretable.
Nies, Schlicht and Tent [37] have proved that isomorphism of oligomorphic
groups is $\leq_{B}E_{\infty}$, the universal countable Borel equivalence
relation. So it is way below graph isomorphism. In fact it is unknown to be
nonsmooth. By Harrington-Kechris-Louveau, nonsmoothness is equivalent to an
affirmative answer to the following.

######  Question 2.8.

Is $E_{0}\leq_{B}$ isomorphism of oligomorphic groups?

##### Amenable groups (with A. Iwanow and B. Majcher)

Recall that a Polish group $G$ is amenable if each compact space it acts on
has an invariant probability measure. $G$ is extremely amenable if each such
action has a fixed point (so the point mass on it is the required probability
measure). For discrete groups, this is equivalent to the usual Folner
condition.

Discrete amenable group form a Borel subset. For, applying Kuratowski-Ryll-
Nardzewski selectors the Folner condition can be presented in a Borel form.

Nilpotent groups are amenable. Thus, Mekler’s result can be also applied to
the isomorphism relation of discrete amenable groups, making it equivalent to
GI.

Amenability (without the assumption of discreteness) is Borel by its
characterisation due to Schneider and Thom [43]. The description is more less
in the style of Folner.

For more detail, including extreme amenability, see Section 3.

##### Maximal-closed groups

Fixing some bijection ${\mathbb{Q}}^{n}\leftrightarrow\omega$, the group
AGL(${\mathbb{Q}}^{n})$ of affine linear transformations can be seen as a
closed subgroup of $S(\omega)$. Kaplan and Simon [24] showed that it is a
maximal closed subgroup (that is also countable). Agarwal and Kompatscher [1]
have provided continuum many maximal-closed groups that are not even
algebraically isomorphic, using “Henson digraphs” that were introduced in a
paper of Henson.

Clearly being maximal-closed is $\Pi^{1}_{1}$. It is not known to be Borel.

#### Recursion theoretic view

The Effros space is insufficient here. We need a more concise way to represent
closed subgroups of $S(\omega)$. They are given by trees without dead ends
satisfying a certain $\Pi^{0}_{1}$ condition.

Let $\mathbb{T}$ be the tree of all pairs
$\langle\sigma,\sigma^{\prime}\rangle$ of the same length $n$ such that
$\sigma(i)=k\leftrightarrow\sigma^{\prime}(k)=i$ for each $i,k<n$. In other
words, there is $f\in S(\omega)$ such that $\sigma\prec f$ and
$\sigma^{\prime}\prec f^{-1}$.

If $B$ is a subtree of $\mathbb{T}$ without dead ends, then for each $\langle
f,f^{\prime}\rangle\in[B]$, $f$ is a permutation of $\omega$ with inverse
$f^{\prime}$. We can formulate as a $\Pi^{0}_{1}$ condition on $B$ that
$\\{f\colon\langle f,f^{-1}\rangle\in[B]\\}$ is closed under inverses and
product.

If $B$ is a computable tree we say that the group given by $[B]$ is
computable.

######  Question 2.9.

Are there two compact, computably isomorphic computable subgroups of
$S(\omega)$ such that no computable copies are conjugate via a computable
permutation of $S(\omega)$?.

###  3\. Ivanov and Majcher: amenable subgroups of $S(\omega)$

In this post we show that the properties of being amenable and extremely
amenable for Polish groups are Borel.

Given a Polish space ${\bf Y}$ let $\mathcal{F}({\bf Y})$ denote the set of
closed subsets of ${\bf Y}$. The Effros structure on $\mathcal{F}({\bf Y})$ is
the Borel space with respect to the $\sigma$-algebra generated by the sets

$\mathcal{C}_{U}=\\{D\in\mathcal{F}({\bf Y}):D\cap U\not=\emptyset\\},$

for open $U\subseteq{\bf Y}$. For various ${\bf Y}$ this space serves for
analysis of Borel complexity of families of closed subsets (see [25] for some
recent results). It is convenient to use the fact that there is a sequence of
Kuratowski-Ryll-Nardzewski selectors (selectors, in brief)
$s_{n}:\mathcal{F}({\bf Y})\rightarrow{\bf Y}$, $n\in\omega$, which are Borel
functions such that for every non-empty $F\in\mathcal{F}({\bf Y})$ the set
$\\{s_{n}(F);n\in\omega\\}$ is dense in $F$.

We consider $S(\omega)$ as a complete metric space by defining

$d(g,h)=\sum\\{2^{-n}\mid g(n)\not=h(n)\mbox{ or }g^{-1}(n)\not=h^{-1}(n)\\}.$

Let $S_{<\infty}$ denote the set of all bijections between finite substes of
$\omega$. Let

$S^{+}_{<\infty}=\\{\sigma\in S_{<\infty}\mid\mathsf{dom}[\sigma]\mbox{ is an
initial segment of }\omega\\}.$

The family

$\\{{\mathcal{N}}_{\sigma}\mid\sigma\in S^{+}_{<\infty}\\}$

is a basis of the Polish topology of $S(\omega)$.

We mention here that the set ${\mathcal{U}}(S(\omega))$ of all closed
subgroups of $S(\omega)$ is a Borel subset of ${\mathcal{F}}(S(\omega))$ (see
Lemma 2.5 of [25]).

Since $S(\omega)$ is a Polish group (in particular the multiplication is
continuous) we may extend the set of selectors $s_{n}$, $n\in\omega$, by group
words of the form $w(\bar{s})$ which define Borel maps
${\mathcal{F}}(S(\omega))\rightarrow S(\omega)$ and respectively
${\mathcal{U}}(S(\omega))\rightarrow S(\omega)$. In particular for any closed
$G\leq S(\omega)$ all $w(\bar{s})(G)$ form a dense subgroup. Below for
simplicity we will always assume that already all $s_{n}(G)$, $n\in\omega$,
form a dense subgroup of $G$.

####  3.1. Closed subgroups and amenability

In this section we apply the description of amenable topological groups found
by F.M. Schneider and A. Thom in [44] in order to analyse amenability for
closed subgroups of $S(\omega)$.

Let $G$ be a topological group, $F_{1},F_{2}\subset G$ are finite and $U$ be
an identity neighbourhood. Let $R_{U}$ be a binary relation defined as
follows:

$R_{U}=\\{(x,y)\in F_{1}\times F_{2}:yx^{-1}\in U\\}.$

This relation defines a bipartite graph on $(F_{1},F_{2})$. Let

$\mu(F_{1},F_{2},U)=|F_{1}|-\mathsf{sup}\\{|S|-|N_{R}(S)|:S\subseteq
F_{1}\\},$

where $N_{R}(S)=\\{y\in F_{2}:(\exists x\in S)(x,y)\in R_{U}\\}$. By Hall’s
matching theorem this value is the matching number of the graph
$(F_{1},F_{2},R_{U})$. Theorem 4.5 of [44] gives the following description of
amenable topological groups.

Let $G$ be a Hausdorff topological group. The following are equivalent.
(1) $G$ is amenable.
(2) For every $\theta\in(0,1)$, every finite subset $E\subseteq G$, and every
identity neighbourhood $U$, there is a finite non-empty subset $F\subseteq G$
such that

$\forall g\in E(\mu(F,gF,U)\geq\theta|F|).$

(3) There exists $\theta\in(0,1)$ such that for every finite subset
$E\subseteq G$, and every identity neighbourhood $U$, there is a finite non-
empty subset $F\subseteq G$ such that

$\forall g\in E(\mu(F,gF,U)\geq\theta|F|).$

It is worth noting here that when an open neighbourhood $V$ contains $U$ the
number $\mu(F,gF,U)$ does not exceed $\mu(F,gF,V)$. In particular in the
formulation above we may consider neighbourhoods $U$ from a fixed base of
identity neighbourhoods. For example in the case of a closed $G\leq S(\omega)$
we may take all $U$ in the form of stabilizers $V_{[n]}=\\{f\in G:f(i)=i$ for
$i<n\\}$. It is also clear that we can restrict all $\theta$ by rational
numbers. From now on we work in this case.

######  Theorem 3.1.

The class of all amenable closed subgroups of $S(\omega)$ is Borel.

###### Proof.

Since the family of all closed subgroups of $S(\omega)$ is Borel it suffices
to prove the following claim.

CLAIM. For every basic open neighbourhood $U$ of the unity, any rational
$\theta\in(0,1)$ and any pair of tuples $\bar{s}$ and $\bar{s}^{\prime}$ of
selectors the family of all closed $Z\subseteq S(\omega)$ with the condition

$\forall
g\in\bar{s}(Z)(\mu(\bar{s}^{\prime}(Z),g\bar{s}^{\prime}(Z),U)\geq\theta|\bar{s}^{\prime}(Z)|)$

is Borel.

Indeed, let us denote the condition of the claim by
$F\o(U,\theta,\bar{s},\bar{s}^{\prime})$. Then having Borelness as above we
see that the (countable) intersection by all $U$, $\theta$ and $\bar{s}$ of
the families

$\bigcup\\{\\{G\leq_{c}S(\omega):G\models
F\o(U,\theta,\bar{s},\bar{s}^{\prime})\\}:\bar{s}^{\prime}\mbox{ is a tuple of
}$ $\mbox{ selectors}\\}$

is also Borel. Note that this family exactly consists of closed subgroups $G$
having dense sabgroups satisfying condition (2) of Schneider-Thom’s theorem.
It is well-known that groups having dense amenable subgroups are amenable. In
particular we see that the claim above implies the theorem.

Let us prove the claim. For a closed $Z\subseteq S(\omega)$, $g\in\bar{s}(Z)$
and $F=\\{f_{1},\ldots,f_{k}\\}$ consisting of entries of
$\bar{s}^{\prime}(Z)$ to guarantee the inequality $\mu(F,gF,U)\geq\theta|F|$
we only need to demand that for every $S\subseteq F$ the following inequality
holds:

$|S|-k+\theta\cdot k\leq|N_{R}(S)|,$

where $N_{R}(S)$ is defined with respect to $(F,gF)$ and $U$. To satisfy this
inequality we will use the observation that when $S^{\prime}\subseteq gF$ and
$\rho$ is a function $S^{\prime}\rightarrow S$ such that $gf(\rho(gf))^{-1}\in
U$ for each $gf\in S^{\prime}$ then $|S^{\prime}|\leq|N_{R}(S))|$.

The following condition formalizes $\mu(F,gF,U)\geq\theta|F|$:

$\bigwedge_{S\subseteq F}\bigvee\\{\bigwedge_{gf\in
S^{\prime}}(gf(\rho(gf))^{-1}\in U):S^{\prime}\subseteq gF\mbox{ ,
}\rho:S^{\prime}\rightarrow S\mbox{ , }$ $|S|-k+\theta\cdot
k\leq|S^{\prime}|\\}.$

By the choice of $g$ and $F$ we see that all closed $Z\subseteq S(\omega)$
satisfying it form a Borel family. ∎

Let ${\bf U}$ be the Urysohn space. By [47] every Polish group is realized as
a closed subgroup of $Iso({\bf U})$. Applying the proof given above to
${\mathcal{F}}(Iso({\bf U}))$ we obtain the following corollary.

######  Corollary 3.2.

The class of all amenable closed subgroups of $Iso({\bf U})$ is Borel.

####  3.2. Closed subgroups and extreme amenability

Let $G$ be a topological group. The group $G$ is said to be extremely amenable
if every continuous action of $G$ on a non-empty compact Hausdorff space
admits a fixed point.

We begin by fixing a left-invariant metric $d$ inducing the topology of
$S(\omega)$ (resp. $Iso({\bf U})$). Recall from ([42], Theorem 2.1.11) that
$G\leq_{c}S(\omega)$ is extremely amenable if and only if the left-translation
action of $G$ on $(G,d)$ is finitely oscillation stable. From ([42], Theorem
1.1.18) and ([32], proof of Theorem 3.1) this is equivalent to the following
condition:

> For any $\varepsilon>0$ and a finite $F\subset G$ there exists a finite
> $K\subseteq G$ such that for any function $c:K\rightarrow\\{0,1\\}$ there
> exists $i\in\\{0,1\\}$ and $g\in G$ such that for any $f\in F$ there exists
> $k\in c^{-1}(i)$ with $d(gf,k)<\varepsilon$.

We consider the case when $G$ has a countable base of the topology. By the
definition of extreme amenability if $G$ has a dense subgroup which is
extremely amenable, then $G$ is extremely amenable too. Now it is easy to see
that when $D\subseteq G$ is a countable dense subgroup of $G$ then extreme
amenability of $G$ is equivalent to condition above for the elements taken in
$D$.

We now see that when $G\in{\mathcal{F}}(S(\omega))$ (resp.
${\mathcal{F}}(Iso({\bf U}))$), extreme amenability of $G$ is equivalent to a
countable conjunction of the folowing conditions.

> Let $\bar{s}$ be a tuple of selectors and $\varepsilon\in{\bf Q}^{+}$. Then
> there is a selectors $\bar{t}$ such that for any function
> $c:\bar{t}\rightarrow\\{0,1\\}$ there exists $i\in\\{0,1\\}$ and a selector
> $s^{\prime}$ such that for any $s\in\bar{s}$ there exists $k\in c^{-1}(i)$
> with $d(s^{\prime}(G)s(G),k(G))<\varepsilon$.

We see that extreme amenability is a Borel property.

####  3.3. Comments

1\. The argument given in Section 3.2 is adapted from the proof of Theorem 1.3
in [32]. Originally [32] considers the following situation. Let $G$ be a
Polish group and $\Gamma$ be a countable group. Let us consider the Polish
space $Hom(\Gamma,G)$ of all homomrphisms from $\Gamma$ to $G$. By Theorem 3.1
in [32] the subset of all $\pi\in Hom(\Gamma,G)$ such that
$\overline{\pi(\Gamma)}$ is extremely amenable is a $G_{\delta}$ subset of
$Hom(\Gamma,G)$. By Corollary 18 of [23] the set of all representations from
$Hom(\Gamma,G)$ whose image is an amenable subgroup of $G$ is also
$G_{\delta}$ in $Hom(\Gamma,G)$.
2\. Let ${\mathcal{G}}_{n}$ be the space of all $n$-generated (discrete)
groups with distinguished $n$-tuples of generators $(G,\bar{g})$ (so called
marked groups). This is a compact space under so called Grigorchuk topology.
In papers [3] and [48] descriptive complexity in ${\mathcal{G}}_{n}$ of some
versions of amenability is considered. The authors of [3] show that
amenability is ${\bf\Pi}^{0}_{2}$. They ask if it is
${\bf\Pi}^{0}_{2}$-complete.

A group $G$ is called elementarily amenable if it is in the smallest class of
groups which contains all abelian and finite ones and is closed under
quotients, subgroups, extensions corresponding to exact sequences
$1\rightarrow K\rightarrow G\rightarrow H\rightarrow 1$ and directed unions.
It is proved in [48] that elementary amenability is coanalytic and non-Borel.
3\. Let us fix an indexation of all computably enumerable groups on $\omega$
(i.e. computably presented groups). Under this indexation computable groups
correspond to groups with decidable word problem. It is easy to see that
Følner’s condition of amenability (or the Schneider-Thom’s condition of
Section 3.1 in the case of discrete groups) define a $\Pi^{0}_{2}$ subset of
indices. On the other hand applying Theorem 3 of [21] it is easy to see that
this property is $\Pi^{0}_{2}$-hard (it is a Markov property). Similarly one
easily obtains that extreme amenability is $\Pi^{0}_{2}$-complete.

E-mail: Aleksander.Iwanowpolsl.pl

###  4\. Nies: Stone-type duality for totally disconnected locally compact
groups

In this post all topological groups will be Polish, and they all have a basis
of neighborhoods of $1$ consisting of open subgroups. As is well-known, such a
group is topologically isomorphic to a closed subgroup of the symmetric group
on ${\mathbb{N}}$, denoted $S(\omega)$. A homeomorphic embedding into
$S(\omega)$ is obtained for instance by letting the group act by left
translation on the left cosets of open subgroups in that basis of
neighborhoods of $1$.

Nies, Schlicht and Tent [37] developed the notion of coarse groups for closed
subgroups of $S(\omega)$, which first appeared in [25]. The idea is to do
algebra with approximations of elements, rather than with the elements
themselves. The approximations are all the cosets of open subgroups (left or
right cosets, this makes the same class). Open cosets form the domain of the
coarse group, and the structure is equipped with the ternary relation
$AB\subseteq C$. The authors in [37] apply the notion primarily for the class
of oligomorphic groups, but also the profinite groups. (Ivanov has pointed out
that in that case a closely related structure was studied much earlier by
Chatzidakis [5].)

Here we give a different approach to coarse groups, which is particularly
intended for the setting of totally disconnected locally compact (t.d.l.c.)
groups. General references for t.d.l.c. groups include Willis [49, 50].

In [37] all open cosets of a topological group $G$ were considered, but the
analysis was restricted to classes of groups $G$ which have only countably
many open subgroups. This is e.g. the case for Roelcke precompact groups (for
each open subgroup $U$ there is a finite set $F$ such that $UFU=G$). Such
groups are in a sense opposite to the t.d.l.c. groups: the intersection of
those two ‘large” classes consists merely of the profinite groups. However, a
superclass of both has also been studied: locally Roelcke precompact groups.

The coarse group $\mathcal{M}(G)$ of a t.d.l.c. group $G$ consists of the
_compact_ open cosets of $G$.

####  4.1. Inductive groupoids, and inverse semigroups

A category is small if the objects form a set (rather than a proper class).
Recall that a groupoid is a small category such that each morphism $A$ has an
inverse, denoted $A^{-1}$. A partially ordered groupoid is a groupoid with a
partial order $\sqsubseteq$ on the set of morphisms (and therefore also on the
objects, which are identified with their identity morphisms) where the
functional and the order structure are compatible. An _inductive groupoid_ is
a partially ordered groupoid such that the partial order $\sqsubseteq$
restricted to the set of neutral elements is a semilattice. See Lawson [27,
Section 4.1].

A semigroup is called _regular_ if for each $a$ there is $b$, called the
inverse of $a$, such that $aba=a$ and $bab=b$. Inductive groupoids closely
correspond to _inverse semigroups_. These are regular semigroups where the
idempotents (elements $e$ such that $ee=e$) commute. In particular, the
(large) categories of inductive groupoids and of inverse semigroups are
isomorphic.

For instance, given an inductive groupoid, to define the semigroup operation,
simply let $AB=(A\mid V)(V\mid B)$, where $V$ is the meet of the right domain
of $A$ and the left domain of $B$, and $\mid$ denotes restriction, given by
axiom $A2(a)$ below. See Lawson [27] for detail.

The representation theorem due to Wagner and Preston (both 1954,
independently) realizes every inverse semigroup $S$ as an inverse semigroup of
partial bijections on $S$. An element $a\in S$ becomes the partial bijection
$\tau_{a}\colon a^{-1}S\to S$ given by $t\mapsto at$. Clearly
$\tau_{b}\circ\tau_{a}=\tau_{ba}$. If $S$ is a group this is just the left
Cayley representation. See Lawson [27, Section 4.1 and 4.5].

####  4.2. The coarse groupoid of a topological group

Given a topological group for which the open subgroups form a nbhd basis of
$1$, an inductive groupoid is obtained as follows.

  * •

Objects correspond to open subgroups. In the abstract setting they will be
called ∗subgroups. We use letters $U,V,W$ for them.

  * •

Morphisms correspond to open cosets. Abstractly they are called ∗cosets. We
use letters $A,\ldots,E$ to denote them. $A\colon U\to V$ means that $A$ is a
right coset of $U$ and a left coset of $V$. In brief we often write
${}_{U}A_{V}$ for this. The usual notation in the theory of groupoids is
$U=\mathbf{d}(A)$ (for domain) and $V=\mathbf{r}(A)$ (for range).

We will treat coarse groupoids axiomatically. We begin with the following.

Notation and conventions. An object $U$ will be identified with the neutral
morphism $1_{U}$. So there are only morphisms, and objects merely form a
convenient manner of speaking. We write $RC(U)$ and $LC(U)$ for the sets of
right, resp. left ∗cosets of $U$. In formulas we also write ${}_{U}A$ to mean
that $A\in RC(A)$, and $A_{U}$ to mean that $A\in LC(U)$.

We axiomatically require the usual properties defining groupoids and partial
orders. For ease of language we adjoin a least element $0$ to the partial
order. We require that in the partial order $\sqsubseteq$ on the objects
(i.e., the ∗subgroups), any two elements $U,V$ have an infimum, denoted
$U\wedge V$. By $A\perp B$ denote that $A\wedge B=0$ are incompatible. If
$M=\mathcal{M}(G)$ then $0$ is interpreted as the empty set.

We have the following axioms connecting the groupoid and partial order. (Keep
in mind that we identify $U$ and $1_{U}$.)

######  Axioms 4.1.

  1. (A1)

If $A\sqsubseteq B$ then $A^{-1}\sqsubseteq B^{-1}$.

  2. (A2)

Let $U\sqsubseteq V$.

($\downarrow$) If ${}_{V}B$ then $A\sqsubseteq B$ for some ${}_{U}A$.

($\uparrow$) If ${}_{U}A$ then $A\sqsubseteq B$ for some ${}_{V}B$.

  3. (A3)

if $AB$ and $A^{\prime}B^{\prime}$ are defined and $A\sqsubseteq
A^{\prime},B\sqsubseteq B^{\prime}$, then $AB\sqsubseteq
A^{\prime}B^{\prime}$.

  4. (A4)

If ${}_{U}A$ and ${}_{V}B$ and $U\sqsubseteq V$, then either $A\sqsubseteq B$
or $A\perp B$.

  5. (A5)

If $A\not\sqsubseteq B$ then there is $C\sqsubseteq A$ such that $C\perp B$.

Remarks:

Note that Axioms (A1), (A2$\downarrow$) and (A3) are the usual axioms of
ordered groupoids, OG1, OG3 and OG2 respectively in Lawson [27, Section 4.1],
only the notation there is a bit different.

We have $A_{U}$ iff ${}_{U}A^{-1}$ by the definitions, which implies that the
axioms mentioning right ∗cosets also holds for left ∗cosets. See e.g. [27,
Section 4.1, Prop 3(6)] for a proof of the left coset version of
(A2$\downarrow$) which Lawson calls (OG3∗).

Axiom (A2$\uparrow$) doesn’t seem to occur in the ordered groupoids
literature. Axiom (A4) is special to the applications to topological groups we
have in mind here. It implies that different right ∗cosets of the same
∗subgroup are disjoint. Axiom (A5) essentially says that the topology is
Hausdorff.

#### The axioms are satisfied for structures of suitable open cosets

In the following, $G$ is a topological group as above with countably many open
subgroups, or $G$ is a t.d.l.c. group. Let $\mathcal{M}(G)$ denote the coarse
groupoid: the ∗subgroups are the open subgroups in the former case, and the
compact open subgroups in the t.d.l.c. case. The morphisms are the (compact)
open cosets. We have $A\colon U\to V$ if $A$ is a right coset of $U$ and a
left coset of $V$. Recall that in brief we write ${}_{U}A_{V}$ for this. It is
easily seen that the axioms above hold. To show that $\mathcal{M}(G)$ (with 0
interpreted as the empty set) is a lower semilattice, suppose that $x\in
aU\cap bV$ for subgroups $U,V$, then $xU=aU$ and $xV=bV$. Let $W=U\cap V$.
Then $aU\cap bV=xW$. Claim 4.6 below shows that this argument works in the
general axiomatic setting.

Note that $\exists A\colon U\to V$ iff $U$ and $V$ are conjugate in $G$. In
this case, there is $a\in G$ such that $Ua=A=aV$.

#### Some consequences of the axioms

First we check that the ordering relation of morphisms carries over to their
left and right domains.

######  Claim 4.2.

Suppose $A\colon U_{0}\to U_{1}$, $B\colon V_{0}\to V_{1}$ and $A\sqsubseteq
B$. Then $U_{i}\sqsubseteq V_{i}$ for $i=0,1$.

To verify this: by (A1) we have $A^{-1}\sqsubseteq B^{-1}$. Then by (A3) and
identifying $U$ with $1_{U}$, we have $U_{0}=AA^{-1}\sqsubseteq
BB^{-1}=V_{0}$. Similarly, we’ve got $U_{1}\sqsubseteq V_{1}$.

######  Claim 4.3.

For each $A\in M$ and each ∗subgroup $U$, there are a ∗subgroup $V\sqsubseteq
U$ and a left ∗coset $B$ of $V$ such that $B\sqsubseteq A$. A similar fact
holds for right ∗cosets.

To see this, suppose that $A$ is left ∗coset of $W$. Let $V=W\wedge U$. By
Axiom (A2$\downarrow$) there is $B\sqsubseteq A$ such that $B$ is left ∗coset
of $V$, as required.

The following holds more generally in ordered groupoids.

######  Claim 4.4 ([27], Section 4.1, Prop 3(5)).

If $C\sqsubseteq AB$ then there are $A^{\prime}\sqsubseteq A$ and
$B^{\prime}\sqsubseteq B$ such that $C=A^{\prime}B^{\prime}$.

Next we show that each left ∗coset of a ∗subgroup $V$ is given by the left
∗cosets of a ∗subgroup $U$ it contains. (In a sense it is the “union” of these
cosets.)

######  Claim 4.5.

Suppose $U\sqsubseteq V$. If $B_{V}\neq C_{V}$ then there is $A_{U}\sqsubseteq
B$ such that $A\perp C$.

To verify this, we may suppose that $B\not\sqsubseteq C$. By Axiom (A5) there
a ∗subgroup $W$ and $D_{W}\sqsubseteq B$ such that $D\perp C$. Let
$U^{\prime}=W\wedge U$. Let $E_{U^{\prime}}\sqsubseteq D$ by (A2$\downarrow$).
There is $A_{U}\sqsupseteq E$ by (A2$\uparrow$). Since $A\perp B$ fails
(because of $E$) we have $A\sqsubseteq B$ by (A4). However, $A\sqsubseteq C$
would imply $E\sqsubseteq C$ and hence contradict $D\perp C$. So $A\perp C$ by
(A4) again.

######  Claim 4.6.

Suppose $A_{U}\wedge B_{V}\neq 0$. Let $W=U\cap V$. Then $A\wedge B$ is the
unique left ∗coset of $W$ contained in $A$ and $B$.

If $C_{W^{\prime}}\sqsubseteq A,B$, then $W^{\prime}\sqsubseteq W$ by Claim
4.2 and definition of $W$. So by (A2$\uparrow$) there is $D_{W}$ such that
$C\sqsubseteq D$. Letting $C=A\wedge B$, we see that $A\wedge B$ is a left
∗coset of $W$. If any left ∗coset of $W$ is contained in $A,B$ it equals $C$
by (A4).

#### Normal ∗subgroups

Recall that we write $LC(U)$ and $RC(U)$ for the sets of left, resp. right,
∗cosets of $U$. We say that ∗subgroups $U,V$ are _conjugate_ if $\exists
A\colon U\to V$, or in other words, $RC(U)\cap LC(V)\neq\emptyset$. In
$\mathcal{M}(G)$ this replicates the usual meaning of conjugacy. For the
slightly nontrivial direction, if $A=Ua=bV$ then $a^{-1}Ua=a^{-1}bV$. This is
a subgroup, so $a^{-1}b\in V$, and hence $U^{a}=V$. The axioms of groupoids
imply that conjugacy is an equivalence relation.

Normal ∗subgroups $V$ are the ones only conjugate to themselves: for each
$B\in RC(V)$ we have $B^{-1}VB=V$. This is equivalent to $VB=BV$ for each such
$B$, or equivalently defined by the condition $LC(V)=RC(V)$. In category
language, all morphisms with left domain $V$ also have right domain $V$, and
vice versa. So there is a natural group operation on $RC(V)$.

A rather trivial fact from group theory becomes more demanding in the
axiomatic setting of coarse groupoids.

######  Proposition 4.7.

Suppose that $U$ is a ∗subgroup such that $RC(U)$, or equivalently $LC(U)$, is
finite. Then there is a normal ∗subgroup $N\sqsubseteq U$.

In usual topological group theory, the argument is as follows. Since $U$ is a
subgroup of $G$ of finite index, the conjugacy class of $U$ is finite. Let
$N=\bigcap_{g\in G}U^{g}$. This is a finite intersection and hence defines an
open subgroup, and $N^{h}=\bigcup_{g}U^{gh}=N$ for each $N$. So $N$ is normal.

###### Proof.

Let $\mathcal{D}$ be the “conjugacy class” of $U$, namely

$\mathcal{D}=\\{B^{-1}UB\colon B\in RC(U)\\}$.

The hypothesis implies that $\mathcal{D}$ is finite, so let $N$ be the meet of
all its members. Then $N\sqsubseteq U$. We show that $N$ is normal as
required.

Given $C\in RC(N)$, we will show that $C\in LC(N)$. We define a bijection
$f_{C}\colon\mathcal{D}\to\mathcal{D}$ by

$f_{C}(W)=D^{-1}WD$ where $D\in RC(W)$ and $C\sqsubseteq D$;

note that $D$ exists and is unique because $N\sqsubseteq W$, so $f_{C}$ is
well-defined.

To verify that $f_{C}$ is bijection, since $\mathcal{D}$ is finite it suffices
to show that $f_{C}$ is 1-1. Suppose $f_{C}(W_{0})=f_{C}(W_{1})=:V$. Then
$D_{0}^{-1}W_{0}D_{0}=D_{1}^{-1}W_{1}D_{1}=V$ where $C\sqsubseteq D_{0},D_{1}$
and $D_{i}\in RC(W_{i})$. Since $D_{0},D_{1}\in LC(V)$, and $D_{0},D_{1}$ are
not disjoint, this implies $D_{0}=D_{1}$ and hence $W_{0}=W_{1}$.

We have $N^{\prime}:=C^{-1}NC\sqsubseteq f_{C}(W)$ for each $W\in\mathcal{D}$
using (A1) and (A3). So, since $f_{C}$ is onto, $N^{\prime}\sqsubseteq N$.

Since $C\in LC(N^{\prime})$ and $N^{\prime}\sqsubseteq N$, there is $D\in
LC(N)$ such that $C\sqsubseteq D$ by (A2$\uparrow$). Then
$C^{\prime}:=D^{-1}\in RC(N)$, so $C^{\prime}\sqsubseteq D^{\prime}$ for some
$D^{\prime}\in LC(N)$ by the argument above. Then $D\sqsubseteq
E:=(D^{\prime})^{-1}\in RC(N)$ by (A1). So $C\sqsubseteq E$ and both are in
$RC(N)$. Hence $C=D=E$ by (A4). This shows that $LC(N)\subseteq RC(N)$, hence
also $RC(N)\subseteq LC(N)$ by taking inverses. So $RC(N)=LC(N)$ as required.
∎

#### The filter group associated with a coarse groupoid

We’ve seen how to turn a topological group into a coarse groupoid. Now we go
the opposite way. This is adapted from [37]. An alternative, possibly easier
way to do this is to take the topological group of “left automorphisms” of
$M$, as detailed in Prop. 4.18 below.

Let $M$ be a coarse groupoid. A filter on a p.o. is a proper subset that is
downward directed and upward closed. For $(M,\sqsubseteq)$, a filter is thus a
subset $x$ that is upward closed, and $A\wedge B$ exists and is in $x$, for
any $A,B\in x$.

######  Definition 4.8.

A  _full filter_ is a filter $x$ on the partial order $(M,\sqsubseteq)$ such
that for each ∗subgroup $U\in M$, there is a left ∗coset and a right ∗coset in
$x$. Note that these ∗coset are unique by (A4). $\mathcal{F}(M)$ denotes the
set of full filters. We use variables $x,y,z$ for full filters.

######  Claim 4.9.

For each $A$ there is a full filter $x$ such that $A\in x$.

This follows by iterated applications of Claim 4.3.

We begin with the topology on $\mathcal{F}(M)$.

######  Definition 4.10 (Topology on the set of full filters).

As in [37] we define a topology on $\mathcal{F}(M)$ by declaring as subbasic
the open sets

$\widehat{A}=\\{x\in\mathcal{F}(M)\colon A\in x\\}$

where $A\in M$. These sets form a base since filters are directed.

Suppose $M$ is countable. The following improves [37, Prop 2.5] that
$\mathcal{F}(M)$ a totally disconnected Polish space.

######  Proposition 4.11.

There is a homeomorphic embedding taking $\mathcal{F}(M)$ to a closed subset
of Baire space.

###### Proof.

Let ${\left\langle{U_{n}}\right\rangle}_{n\in{\mathbb{N}}}$ be a descending
sequence of ∗subgroups that is cofinal (every ∗subgroups contains an $U_{n}$).
Fix a bijection $f\colon{\mathbb{N}}\to M$. We define an injection $\Delta$
from $\mathcal{F}(M)$ into Baire space ${}^{\omega}\omega$.

Suppose that $x\in\mathcal{F}(M)$. Let $\Delta(x)(0)$ be the left ∗coset of
$U_{0}$ in $x$.

Suppose $\Delta(x)(2n)$ is defined and a left ∗coset of some $U_{r}$. Let
$\Delta(x)(2n+1)$ be the $k$ such that $A=f(k)\in x$, and $A$ is a right
∗coset of $U_{m}$ where $m>r$ is chosen least possible. This exists by Claim
4.3, since the sequence ${\left\langle{U_{n}}\right\rangle}$ is cofinal, and
(A2).

Similarly, suppose $\Delta(x)(2n+1)$ is defined and a right ∗coset of some
$U_{r}$. Let $\Delta(x)(2n+2)$ be the $k$ such that $A=f(k)\in x$, and $A$ is
a left ∗coset of $U_{m}$ where $m>r$ is chosen least possible.

By the axioms, $\Delta$ is injective because $x$ is the filter generated by
$\Delta(x)$. One checks that it is a homeomorphism because full filters
correspond to the paths on the subtree of the strings given by the possible
next choices at each step. ∎

Next we define the group operations on $\mathcal{F}(M)$. For filters $x,y$ we
let

$\displaystyle x^{-1}$ $\displaystyle=$ $\displaystyle\\{A^{-1}\colon\,A\in
x\\}$ $\displaystyle xy$ $\displaystyle=$ $\displaystyle\\{C\colon\exists
A,B[AB\sqsubseteq C]\\}$

Here writing $AB$ implies that it is defined, i.e. $\exists UA\ _{U}B$.

######  Claim 4.12.

If $x,y$ are full filters, then $x^{-1}$ and $z=xy$ are full filters.

That $x^{-1}$ is a full filter is straightforward. For the second statement,
clearly $z$ is upwards closed. We verify that $z$ is downwards directed.

Always let $i=0,1$. Suppose $C_{i}\in z$. Then there are $A_{i}\in x$,
$B_{i}\in y$ and $U_{i}$ such that ${A_{i}\ }_{U_{i}}B_{i}$ and
$A_{i}B_{i}\sqsubseteq C_{i}$.

Let $U=U_{0}\wedge U_{1}$. By definition of full filters there are $A\in x$
and $B\in y$ such that $A\ _{U}\,B$. Then $C=AB\in z$. By (A4) and since
filters are downwards directed, we have $A\sqsubseteq A_{i}$ and $B\sqsubseteq
B_{i}$. So by (A3) we have $C\sqsubseteq C_{i}$ as required.

The neutral element $e$ is the full filter consisting of all the ∗subgroups.
It is clear from the groupoid axioms that $(\mathcal{F}(M),\cdot)$ is a group
with this neutral element, and the inverse operation above.

That leaves continuity of the group operations. First, as in [37, Claim 2.11]
we need to check that the transfer from formal to semantic concepts works
between ∗cosets $A$ and the corresponding actual open cosets $\widehat{A}$.
Note that we are NOT claiming that these are the only open cosets; this is not
true unless we require further axioms special to the particular class of
groups we are interested in.

######  Claim 4.13.

Let $A,B,C\in M$.

  * (a)

$A\sqsubseteq B\Longleftrightarrow\widehat{A}\subseteq\widehat{B}$.

  * (b)

$\widehat{B^{-1}}=(\widehat{B})^{-1}$.

  * (c)

If $A\cdot B$ is defined then $\widehat{A\cdot B}=\widehat{A}\widehat{B}$.

  * (d)

$\widehat{U}$ is a subgroup of $\mathcal{F}(M)$.

  * (e)

$A\in LC(U)\Longleftrightarrow\widehat{A}$ is a left coset of $\widehat{U}$.

Similarly for right cosets.

###### Proof.

(a) The implication $\Rightarrow$ is upward closure of full filters. For the
implication $\Leftarrow$, suppose that $A\not\sqsubseteq B$. By (A5) there is
$C\sqsubseteq A$ such that $C\perp B$. By Claim 4.9 let $x$ be a full filter
such that $C\in x$. Then $A\in x$ and $B\not\in x$. (b) is immediate. For (c),
$\supseteq$ is by definition, and $\subseteq$ follows from Claim 4.9.

(d) is immediate using $UU=U$.

(e) We follow [37]:

$\Rightarrow$: take any $x\in\widehat{A}$. We show that
$x\widehat{U}=\widehat{A}$.

For $x\widehat{U}\subseteq\widehat{A}$, let $y\in\widehat{U}$. Since $A\in
LC(U)$, we have $AU\sqsubseteq A$. So $x\cdot
y\in\widehat{A}\widehat{U}\subseteq\widehat{A}$ by (c).

For $\widehat{A}\subseteq x\widehat{U}$, let $y\in\widehat{A}$. To show that
$y\in x\widehat{U}$, or equivalently $x^{-1}y\in\widehat{U}$, note that we
have
$x^{-1}y\in\widehat{A}^{-1}\widehat{A}=\widehat{A^{-1}}\widehat{A}\subseteq\widehat{U}$
by (b) and (c).

$\Leftarrow$: Suppose $\widehat{A}=x\widehat{V}$. There is $B\in x$ such that
$B\in LC(V)$. By the forward implication, $\widehat{B}$ is a left coset of
$\widehat{V}$. Also $x\in\widehat{A}\cap\widehat{B}$, so $A\perp B$ fails.
Since $A,B\in LC(V)$ this implies $A=B$ by (A4).

The case of right cosets follows by taking inverses. ∎

Another transfer fact will be useful.

######  Claim 4.14.

The map $x,y\to x\cdot y^{-1}$ is continuous on $\mathcal{F}(M)$.

This follows since the sets of the form $\widehat{D}$ form a basis. If
$xy^{-1}\in\widehat{D}$, i.e., $D\in xy^{-1}$, then by definition there are
$A\in x$ and $B\in y$ such that $AB^{-1}\sqsubseteq D$. Now, by Claim 4.13,
$\widehat{A}\widehat{B}^{-1}\subseteq\widehat{D}$ as required.

######  Claim 4.15.

For any left coset $x\widehat{V}$ in $\mathcal{F}(M)$, there is $A\in LC(V)$
such that $x\widehat{V}=\widehat{A}$.

###### Proof.

Since $x$ is a full filter, there is some left ∗coset $A$ of $V$ in $x$. We
claim that $x\widehat{V}=\widehat{A}$. We have
$x\widehat{V}\subseteq\widehat{A}\widehat{V}=\widehat{V}$, since $A\in x$ and
$\widehat{A}$ is a left coset of $\widehat{V}$ by Claim 4.13. To see that
$\widehat{A}\subseteq x\widehat{V}$, let $y\in\widehat{A}$. Since
$x,y\in\widehat{A}$,
$x^{-1}y\in\widehat{A}^{-1}\widehat{A}=\widehat{A^{-1}}\widehat{A}\sqsubseteq\widehat{V}$
by Claim 4.13. Thus $y\in x\widehat{V}$. ∎

By definition of the topology, the open subgroups of $\mathcal{F}(M)$ form a
nbhd base of $1$. So if $M$ is countable, $\mathcal{F}(M)$ is a non-
Archimedean Polish group.

The operation $\mathcal{F}$ recovers a topological group from its coset
structure when that is countable. It also works in the t.d.l.c. setting where
$\mathcal{M}(G)$ denotes the compact open cosets.

######  Proposition 4.16 (cf. [25], after Claim 3.6, and [37], Prop 2.13).

Suppose that $G$ is a closed subgroup of $S(\omega)$ such that
$\mathcal{M}(G)$ is countable. There is a natural group homeomorphism

$\Phi:G\cong\mathcal{F}(\mathcal{M}(G))$ given by $g\mapsto\\{A\colon A\ni
g\\}$,

with inverse given by $x\mapsto g$ where $\bigcap x=\\{g\\}$.

The inverse map simply sends a full filter $x$ to the point it converges to.
Note that $x$ isn’t really a filter in the sense of topology, only on certain
open sets, but that suffices for the convergence notion.

######  Example 4.17.

For an instructive example of a coarse groupoid, consider the oligomorphic
group $G=\operatorname{Aut}(\mathbb{Q},<)$. The open subgroups of $G$ are the
stabilizers of finite sets. If $U,V$ are stabilizers of sets of the same
finite cardinality, there is a unique morphism $A\colon U\to V$ in the sense
above, corresponding to the order-preserving bijection between the two sets.
The coarse groupoid for $\operatorname{Aut}(\mathbb{Q},<)$ is canonically
isomorphic to the groupoid of finite order-preserving maps on $\mathbb{Q}$,
with the partial order being reverse extension. For compatible maps $A,B$, the
meet $A\wedge B$ is the union of those maps.

A filter $x$ corresponds to an arbitrary order-preserving map $\psi$ on
$\mathbb{Q}$. The filter $x$ contains a right coset of each open subgroup iff
$\psi$ is total, and a left coset of each open subgroup iff $\psi$ is onto. So
the set of full filters corresponds to $\operatorname{Aut}(\mathbb{Q})$ as
expected. (Incidentally, this example shows that in Definition 4.8 we need
both types of cosets, and that not every maximal filter is full.)

#### The filter group as an automorphism group

Let $M$ be a coarse groupoid. By $M_{\text{left}}$ we will denote the
structure with domain $M$ and the operations $\wedge$ and $(r_{B})_{B\in M}$
where $Ar_{B}=AB$ in case $\mathbf{r}(A)=\mathbf{l}(B)$, and $Ar_{B}=0$
otherwise. We show that the left action of $\mathcal{F}(M)$ on $M$ corresponds
to the automorphisms of this “rewrite” of $M$. (This is simlar to showing that
a group is isomorphic to the automorphism group of a Cayley graph given by a
generating set, with edge relations labelled according to the generators.)
Note that for each automorphism $p$ of $M_{\text{left}}$, and each $A$, we
have

$\mathbf{r}(p(A))=\mathbf{r}(A).$

This is because where $U=\mathbf{r}(A)$, we have $p(A)U=p(AU)=p(A)$. Also,
note that $p$ is determined by its restriction to the ∗subgroups, because for
each right ∗coset $B$ of a ∗subgroup $U$ we have $p(B)=p(U)B$.

######  Proposition 4.18.

$\mathcal{F}(M)$ is topologically isomorphic to
$\operatorname{Aut}(M_{\text{left}})$ via a canonical isomorphism $\Theta$.

###### Proof.

For $x\in\mathcal{F}(M)$, the left action ${}_{U}B\mapsto A=x\cdot B$ is given
by $A=CB$ where $C_{U}\in x$. The isomorphism
$\Theta\colon\mathcal{F}(M)\to\operatorname{Aut}(M_{\text{left}})$ maps $x$ to
its left action:

$\Theta(x)(A)=x\cdot A$.

Clearly $\Theta(x)\in\operatorname{Aut}(M_{\text{left}})$, and $\Theta$
preserves the group operations.

Let $s_{M}\in\mathcal{F}(M)$ denote the full filter of ∗subgroups, which is
the neutral element of $\mathcal{F}(M)$. We claim that the inverse $\Phi$ of
$\Theta$ is given by

$\Phi(p)=p(s_{M})$.

Clearly $x=\Phi(p)$ is a filter. To show that $x$ is a _full_ filter, let $U$
be a ∗subgroup in $M$. Since $p$ is an automorphism, firstly, we have
$p(U)U=p(U)$, so $p(U)\in LC(U)$ and $p(U)\in x$. Secondly, there is $B$ such
that $p(B^{-1})=U$. Then $p(B^{-1}B)=UB=B$. So $B\in RC(U)$. Now
$V=B^{-1}B=\mathbf{r}(B)$ is a ∗subgroup. Since $p(V)=B$ we have $B\in x$.

We verify that $\Theta,\Phi$ are inverses of each others. $\Phi(\Theta(x))=x$
because

$A_{U}\in x\leftrightarrow xU=A\leftrightarrow\Theta(x)(U)=A$.

$\Theta(\Phi(p))=p$ because

$p(U)=A\leftrightarrow
A\in\Phi(p)\leftrightarrow\Phi(p)U=A\leftrightarrow\Theta(\Phi(p))(U)=A$.

To show $\Theta$ and $\Phi$ are continuous at $1$, note that if $p=\Theta(x)$,
then $p(U)=U$ is equivalent to $x\in\widehat{U}$.

∎

#### Profinite groups, and ∗compact coarse groupoids

As mentioned, Chatzidakis [5] carried out the first research related to the
application of coarse groupoids to profinite groups. In her version the coarse
groupoid was restricted to normal open ∗subgroups, which suffices in that
case. (Thanks to the Ivanovs for pointing this out.)

We say that a coarse groupoid $M$ is _∗ compact_ if $\forall U\,[LC(U)\text{
is finite}]$. This is, of course, equivalent to requiring that $\forall
U\,[RC(U)\text{ is finite}]$. Clearly $\mathcal{M}(G)$ for profinite $G$ has
this property. By Prop. 4.7, ∗compactness implies that each ∗subgroup $U$
contains a normal ∗subgroup $V$. (This was required separately in [37].)

######  Proposition 4.19.

Let $M$ be a coarse groupoid. Then

$M$ is ∗compact $\Leftrightarrow$ $\mathcal{F}(M)$ is compact.

###### Proof.

$\Leftarrow$: Given $U\in M$, by Claim 4.13(d) $\widehat{U}$ is open in
$\mathcal{F}(M)$. So it has finite index. By (e) of the same claim, this
implies that $LC(U)$ is finite.

$\Rightarrow$: Using Prop. 4.7, let
${\left\langle{N_{k}}\right\rangle}_{k\in{\mathbb{N}}}$ be a descending chain
of normal ∗subgroups such that $\forall U\exists k\,[N_{k}\sqsubseteq U]$. Let
$G_{k}$ be the group induced by $M$ on $LC(N_{k})$. We define an onto map
$p_{k}\colon G_{k+1}\to G_{k}$ as follows: given $A\in LC(N_{k+1})$, using
(A2$\uparrow$) let $p_{k}(A)=B$ where $A\sqsubseteq B\in LC(N_{k})$. Each
$p_{k}$ is a homomorphism by Axioms (A1, A2).

Let $G$ be the inverse limit: $G=\projlim_{k}(G_{k},p_{k})$. Thus

$G=(\\{f\in\prod_{k}G_{k}\colon\forall k\,f(k)=p_{k}(f(k+1))\\},\cdot)$,

which is closed and hence compact group subgroup of the Cartesian product of
the $G_{k}$. We claim that $G\cong(\mathcal{F}(M),\cdot)$ via the map $\Phi$
that sends $f\in G$ to the filter in $\mathcal{F}(M)$ generated by the ∗cosets
$f(k)$, namely

$\Phi(f)=\\{C\in M\colon\,\exists k\,f(k)\sqsubseteq C\\}$.

It is clear that $\Phi$ is a monomorphism. To show $\Phi$ is onto, given a
full filter $x\in\mathcal{F}(M)$, for each $k$ there is $f(k)=B_{k}\in
LC(N_{k})$ such that $B_{k}\in x$. Then $f\in G$, and clearly $\Phi(f)=x$.

Note the $\widehat{N}_{k}$ form a base of nbhds of $1$ in $\mathcal{F}(M)$.
Since $\Phi^{-1}(\widehat{N}_{k})=\\{f\colon f(k)=N_{k}\\}$ and the letter
sets form a base of nbhds of $1$ in $G$, we get that $\Phi$ is a
homeomorphism. Thus $\mathcal{F}(M)$ is compact. ∎

#### Coarse groupoids versus diagrams, for profinite groups

We will characterize the coarse groupoids $\mathcal{M}(G)$ obtained from
profinite groups $G$ by adding an axiom to the ∗compactness condition.

Consider profinite $G=\projlim_{k}(G_{k},p_{k})$ where the $G_{k}$ are finite
groups and each $p_{k}\colon G_{k+1}\to G_{k}$ is an epimorphism. We say that
${\left\langle{G_{k},p_{k}}\right\rangle}$ is a _diagram_ for $G$. By the
proof of Prop. 4.19, each diagram for $G$ can be seen as a coarse groupoid $M$
with $\mathcal{F}(M)\cong G$. So a coarse groupoid for $G$ is not unique.
Intuitively, they may be open subgroups of $\mathcal{F}(M)$ that $M$ is
missing. To avoid this we need another axiom. In the axiom to follow, “CC”
stands for “completeness in case of compactness”. We will see that it implies
in the compact case that each open subgroup of $\mathcal{F}(M)$ has a “name”.

Axiom CC. Let $M$ be a ∗compact coarse groupoid. Let $N$ be a normal ∗subgroup
of $M$.

If a set $\mathcal{S}\subseteq LC(N)$ is closed under products and inverses,
then there is a ∗subgroup $U$ such that $A\sqsubseteq U\leftrightarrow
A\in\mathcal{S}$, for each $A\in LC(N)$.

Clearly $\mathcal{M}(G)$ for profinite $G$ satisfies this axiom. The axiom
implies the dual of Prop. 4.16 in the compact case:

######  Proposition 4.20.

Let $M$ be a ∗compact coarse groupoid satisfying Axiom CC. Then
$M\cong\mathcal{M}(\mathcal{F}(M))$ via the map $A\mapsto\widehat{A}$.

###### Proof.

By Claim 4.13 it suffices to show that the map is onto.

Firstly, let $\mathcal{U}$ be an open subgroup of $\mathcal{F}(M)$. By
definition of the topology and Prop. 4.7, there is a normal ∗subgroup $N$ in
$M$ such that $\widehat{N}\subseteq\mathcal{U}$. By Prop. 4.19,
$\mathcal{F}(M)$ is compact, so $\mathcal{U}$ is the union of finitely many
cosets of $\widehat{N}$. By Claim 4.15 each such coset has the form
$\widehat{A}$ for some $A\in LC(N)$. Let $\mathcal{S}$ be the set of such $A$
in $LC(N)$. The set $\mathcal{S}$ is closed under product and inverses since
$\mathcal{U}$ is a subgroup, using Claim 4.13. So there is a ∗subgroup $U$ as
in Axiom CC. Clearly $\widehat{U}=\mathcal{U}$.

Secondly, given a left coset $\mathcal{B}$ of an open subgroup $\mathcal{U}$
in $\mathcal{F}(M)$, by Claim 4.15 we have $\mathcal{B}=\widehat{B}$ for some
$B\in LC(U)$ as required. ∎

#### T.d.l.c. groups and ∗locally compact coarse groupoids

We say that a coarse groupoid $M$ is _∗ locally compact_ if for each ∗subgroup
$K\in M$ the coarse subgroupoid induced on $\\{A\colon\,A\sqsubseteq K\\}$ is
∗compact. Note that $\mathcal{M}(G)$ for t.d.l.c. $G$ has this property: by
van Dantzig’s theorem (that every t.d.l.c. group has an open compact subgroup)
$\mathcal{M}(G)$ is non-empty, and by definition $\mathcal{M}(G)$ consists of
compact open cosets.

We call $M$ _weakly ∗locally compact_ if for _some_ ∗subgroup $K\in M$ the
inductive subgroupoid on $\\{A\colon\,A\sqsubseteq K\\}$ is ∗compact.

######  Proposition 4.21.

Let $M$ be a coarse groupoid. Then

$M$ is weakly ∗locally compact $\Leftrightarrow$ $\mathcal{F}(M)$ is locally
compact

###### Proof.

$\Leftarrow$: By van Dantzig’s theorem, $\mathcal{F}(M)$ has a compact open
subgroup $\mathcal{L}$. Let $K\in M$ be a ∗subgroup such that
$\widehat{K}\subseteq\mathcal{L}$. As above let $M_{K}$ be the coarse
subgroupoid of $M$ on $\\{A\colon\,A\sqsubseteq K\\}$. Then
$\mathcal{F}(M_{K})\cong\widehat{K}$. So $\mathcal{F}(M_{K})$ is compact.
Hence $M_{K}$ is ∗compact by Prop. 4.19. $\Rightarrow$. Let $M$ be weakly
∗locally compact via $K$. Then $\mathcal{F}(M_{K})\cong\widehat{K}$ is
compact. Since $\widehat{K}$ is an open subgroup of $\mathcal{F}(M)$ this
makes $\mathcal{F}(M)$ locally compact. ∎

######  Example 4.22.

(a) If $G$ is countable discrete group, then $\mathcal{M}(G)$ consists of the
isomorphisms between finite subgroups.

(b) Let $G=(\mathbb{Q}_{p},+)$. The proper open subgroups are compact, and are
all of the form $U_{r}=p^{r}{\mathbb{Z}}_{p}$ for some $r\in{\mathbb{Z}}$. In
this abelian setting each morphism is an endomorphism. The group $G_{r}$ of
endomorphisms $A\colon\,U_{r}\to U_{r}$ has the structure of $C_{p^{\infty}}$
(the direct limit of the cyclic groups $C_{p^{n}}$ with the canonical
embeddings). Let $f(x)=px$ for $x\in C_{p^{\infty}}$ and view $f$ as a map
$G_{r}\to G_{r+1}$. Then for $A\in LC(U_{r}),B\in LC(U_{r+1})$, the ordering
relation $A\sqsubseteq B$ is equivalent to $f(A)=B$. We see that the coarse
groupoid is a bit like a diagram for a profinite group, but goes not only to
closer approximations of elements (backwards), but also to less close ones
(forward).

(c) $G_{d}=\operatorname{Aut}(T_{d})$ for $d\geq 2$. This is the group of
automorphism of the $d$-regular tree $T_{d}$, defined as an undirected graph
without a specified root, first studied by Tits. It is known that each proper
open subgroup is compact. Each compact (open or not) subgroup is contained in
the stabilizers of a vertex, or the stabilizers of an edge (which are compact
open). See [12, p. 12]. It would be interesting to describe more of the
structure of $\mathcal{M}(G_{d})$.

Recall that in the locally compact setting, the coarse groupoid
$\mathcal{M}(G)$ has as a domain the compact open cosets of $G$. We replace
Axiom CC from the compact setting by a variant that works in the more general
setting.

Axiom CLC. Let $M$ be a ∗locally compact coarse groupoid. Let $N$ be a
∗subgroup of a $M$.

If a finite set $\mathcal{S}\subseteq LC(N)$ is closed under products and
inverses, then there is a ∗subgroup $U$ such that $A\sqsubseteq
U\leftrightarrow A\in\mathcal{S}$ for each $A\in LC(N)$.

Clearly, if $G$ is t.d.l.c. then $\mathcal{M}(G)$ satisfies this axiom. We
verify that the axiom characterizes the ∗locally compact coarse groupoids
obtained in this way.

######  Proposition 4.23.

Let $L$ be a ∗locally compact coarse groupoid satisfying Axiom CLC. Then
$L\cong\mathcal{M}(\mathcal{F}(L))$ via the map $A\mapsto\widehat{A}$.

###### Proof.

As in Prop. 4.20, by Claim 4.13 it suffices to show that the map
$A\mapsto\widehat{A}$ is onto.

Firstly let $\mathcal{U}$ be a compact open subgroup of $\mathcal{F}(L)$.
There is $W\in L$ such that $\widehat{W}\subseteq\mathcal{U}$. Let

$L_{\mathcal{U}}=\\{A\in L\colon\,\widehat{A}\sqsubseteq\mathcal{U}\\}$.

Clearly $L_{\mathcal{U}}$ is a coarse subgroupoid of $L$. In
$L_{\mathcal{U}}$, $RC(W)$ is finite, so by Prop. 4.7 there is $N\sqsubseteq
W$ such that $\mathcal{S}:=LC(N)=RC(N)$ in $L_{\mathcal{U}}$. Clearly the
hypothesis of Axiom CLC applies to $\mathcal{S}$, so we get a ∗subgroup $U$.
Then $\widehat{U}=\mathcal{U}$.

Secondly, given a left coset $\mathcal{B}$ of an open subgroup $\mathcal{U}$
in $\mathcal{F}(L)$, by Claim 4.15 we have $\mathcal{B}=\widehat{B}$ for some
$B\in LC(U)$ as above. ∎

####  $\mathcal{M}$ and $\mathcal{F}$ as functors

We will view closed subgroups of $S(\omega)$ (also called non-Archimedean
groups) as a category where the morphisms $f\colon G\to H$ are the continuous
epimorphisms. The kernel of $f$ is a closed normal subgroup. If $G$ is
compact/locally compact then $H$ has the same property.

Covariant functor, for the locally compact case. The open mapping theorem for
Hausdorff topological groups states that a surjective continuous homomorphism
of a $\sigma$-compact group onto a Baire (e.g., a locally compact) group is an
open mapping. (This is proved using Baire category.) Each (separable) t.d.l.c.
group is $\sigma$-compact again by van Dantzig. So if $G$ is locally compact
and $f\colon G\to H$ is onto, then for each compact open $A\subseteq G$, the
image $f(A)$ is open (and of course compact) in $H$.

On t.d.l.c. groups with continuous epimorphisms we can now view the operator
$\mathcal{M}$ as a covariant functor $\mathcal{M}_{+}$. If $f\colon G\to H$
then $\mathcal{M}_{+}(f)\colon\mathcal{M}(G)\to\mathcal{M}(H)$ is given by
$A\mapsto f(A)$. Here we view coarse groupoids as a weak category
$\mathcal{C}_{weak}$ where the morphisms $r\colon\,M\to N$ preserve the
groupoid structure and the partial order in the forward direction only.

Contravariant functor. If $f\colon G\to H$ is an epimorphism of non-
Archimedean groups, then we have a map
$\mathcal{M}_{-}(f)\colon\,\mathcal{M}(H)\to\mathcal{M}(G)$, where
$\mathcal{M}_{-}(f)(A)=f^{-1}(A)$. This clearly preserves the inductive
groupoid structure. We want to identify the right type of morphisms on coarse
groupoids so that $\mathcal{M}$ is a contravariant functor with inverse
$\mathcal{F}$ (suitably extended to morphisms) for the classes of groups of
interest. Consider a map $\mathcal{M}_{-}(f)$ above and let
$R\subseteq\mathcal{M}(G)$ be its range. $R$ consists of all open [compact]
cosets of subgroup of $G$ that contain the kernel of $f$. So,

  * •

$R$ is closed upwards, and

  * •

$R$ is closed under conjugation of subgroups. Thus if $\exists A[_{U}A_{V}]$
and $U\in R$ then $V\in R$.

So we have to take the strong category $\mathcal{C}_{str}$ with objects the
(countable) coarse groupoids and with morphisms $q\colon\,N\to M$ that
preserve the groupoid and the meet semilattice structure (in particular, they
preserve the ordering and hence have to be $1-1$) and have range with the two
properties above. For such an $q\colon\,N\to M$ we can define
$\mathcal{F}(q)\colon\,\mathcal{F}(M)\to\mathcal{F}(N)$ by $x\mapsto
q^{-1}(x)$.

######  Claim 4.24.

Suppose $q\colon N\to M$ is a morphism in $\mathcal{C}_{str}$.

Then $\mathcal{F}(q)\colon\mathcal{F}(M)\to\mathcal{F}(N)$ is a continuous
epimorphism.

###  5\. Nies: Closed subgroups of $S(\omega)$ generated by their permutations
of finite support

Let $SF(\omega)$ denote the groups of permutations of $\omega$ that have
finite support. We note that $SF(\omega)$ plays a role in $S(\omega)$ similar
to the role that $\mathbb{Q}$ plays in ${\mathbb{R}}$. Clearly $SF(\omega)$ is
dense in $S(\omega)$. The inherited topology has as a basis of neighbourhoods
of $1$ the open subgroups $SF(\omega)\cap U_{n}$ of $SF(\omega)$, where
$U_{n}\leq_{o}S(\omega)$ is the pointwise stabilizer of $\\{0,\ldots,n\\}$.
For example the subgroup $T$ algebraically generated by
$\\{(01)(2n\,2n+1)\colon n\geq 1\\}$ of $SF(\omega)$ is not closed; its
closure is $T\cup\\{(01)\\}$.

Given a closed subgroup $G$ of $S(\omega)$, it is of interest to find out how
much of $G$ can be recovered from the closed subgroup $G\cap SF(\omega)$ of
$SF(\omega)$. B. Majcher-Iwanov [28] called $G\cap SF(\omega)$ the _finitary
shadow_ of $G$. Often $G\cap SF(\omega)$ will be trivial, for instance if $G$
is torsion free.

Note that a closed subgroup $G$ of $S(\omega)$ is compact iff each $G$-orbit
is finite. Majcher–Iwanov [28] studied the distribution of finitary shadows of
compact subgroups of $S(\omega)$ within the subgroup lattice of $SF(\omega)$,
and made connections to cardinal characteristics.

One can also start from a subgroup $H$ of $SF(\omega)$ and study how it is
related to its closure $G=\overline{H}$ in $S(\omega)$. (Closures will be
taken in $S(\omega)$ unless otherwise stated.)

Firstly, for each open subgroup $U$ of $H$, its closure $\overline{U}$ is open
in $G$. For, suppose $U_{n}\cap H\leq U$. Since $U_{n}$ is closed we have
$\overline{U_{n}\cap H}=U_{n}\cap\overline{H}$. Hence $U_{n}\cap
G\leq\overline{U}$, so $\overline{U}$ is open in $G$.

Conversely, each open subgroup of $G$ is given as the closure of the open
subgroup $L\cap H$ of $H$:

######  Lemma 5.1.

Let $H\leq SF(\omega)$ and let $G=\overline{H}$ be the closure of $H$ in
$S(\omega)$. Then $L=\overline{L\cap H}$ for each open subgroup $L$ of $G$.

###### Proof.

Since $L$ is closed in $G$, we only need to verify the inclusion $\subseteq$.

Let $g\in L$. Since $L$ is open in $G$, there is $k$ such that for each $v$,
if $gv^{-1}\in U_{k}$ then $v\in L$. Now let $n\geq k$ be arbitrary. Since
$G=\overline{H}$, there is $r\in H$ such that $gr^{-1}\in U_{n}$. So $r\in L$.
This shows $g\in\overline{L\cap H}$. ∎

######  Remark 5.2.

To summarize, there is a natural isomorphisms between the open subgroups $L$
of $G$ and the open subgroups $U$ of $H$, given by $L\to L\cap H$, with
inverse $U\to\overline{U}$.

#### The compact case

The textbook on permutation groups by Dixon and Mortimer [7, Lemma 8.3D]
contains a proof of the following equivalences for a group $H\leq SF(\omega)$:

(i) every $H$-orbit is finite (i.e., $\overline{H}$ is compact)

(ii) $H$ only has finite conjugacy classes (such $H$ is called an FC-group)

(iii) $H$ is residually finite.

The implication (i)$\to$(ii) is pretty elementary: for each $x\in H$ there is
a finite $H$-invariant set $\Delta$ such that the support of $x$ is contained
in $\Delta$. The number of conjugates of $x$ is then bounded by the number of
conjugates of $x\mid\Delta$ (restriction to $\Delta$) in $S_{\Delta}$.
(ii)$\to$(iii) also easy, the remaining implication (iii)$\to$(i) is harder.
It was proved in [33, Thm. 2].

It would be interesting to determine the complexity of the topological
isomorphism relation for closed subgroups $H$ of $SF(\omega)$ that are FC-
groups. Since $H=\overline{H}\cap SF(\omega)$, where the closure is taken in
$S(\omega)$ as usual, it is Borel reducible to topological isomorphism of
profinite groups, which by Kechris et al. [25] is Borel isomorphic to
countable graph isomorphism. However, the groups employed there to reduce
graph isomorphism do not have a finitary shadow satisfying the conditions
above. [25] uses an extension to the topological setting of Mekler’s
construction to code a countable graph into a countable step 2 nilpotent group
of exponent a fixed odd prime. Mekler’s groups being FC would mean that the
coded graph is co-locally finite (each vertex connected to cofinitely many
vertices). But for technical reasons related to the definability of the vertex
set, Mekler’s method only can encode graphs that are triangle and square free,
and such graphs are of course not co-finitary.

#### The oligomorphic case

Recall that a group $H\leq S(\omega)$ is called oligomorphic if for each $r$
its action on $\omega$ has only finitely many $r$-orbits. It is open whether
$E_{0}$ can be Borel reduced to topological isomorphism of closed oligomorphic
subgroups of $S(\omega)$. See Section 2, or [37] for background.

For $H\leq SF(\omega)$, note that $H$ is oligomorphic iff $\overline{H}$ is.
The hope was that one can reduce $E_{0}$ to topological isomorphism of closed
subgroups of $SF(\omega)$, which should be easier to control. To be useful,
this actually assumed an affirmative answer to the following question:

######  Question 5.3.

Is the following true?

Let $H_{0},H_{1}\leq_{c}SF(\omega)$ be oligomorphic. Then

$H_{0},H_{1}$ are homeomorphic $\Leftrightarrow$
$\overline{H}_{0},\overline{H}_{1}$ are homeomorphic.

For the implication $\Rightarrow$, we note that by Remark 5.2 the structures
of open cosets for $\overline{H}_{i}$ and $H_{i}$ are isomorphic for $i=0,1$.
That is $\mathcal{M}(\overline{H}_{i})\cong\mathcal{M}(H_{i})$. By hypothesis
$\mathcal{M}(H_{0})\cong\mathcal{M}(H_{1})$. Since the $\overline{H}_{i}$ are
closed oligomorphic subgroups of $S(\omega)$,
$\mathcal{M}(\overline{H}_{0})\cong\mathcal{M}(\overline{H}_{1})$ implies that
they are topologically isomorphic by [37].

However, the intended application doesn’t not work, because oligomorphic
subgroups $H$ of $SF(\omega)$ are very restricted, and in particular there are
only countably many up to isomorphism.

Some examples of such groups $H$ come to mind. First take permutations of
finite support preserving the evens. This group is topologically isomorphic to
$SF(\omega)\times SF(\omega)$. More generally, take a finite power of
$SF(\omega)$. Another type of example is letting $H$ be the automorphism group
of a countably infinite structure obtained taking a finite structure $M$, and
have an equivalence relation $E$ with a “copy” of $M$ on each class. For
instance, take one unary function symbol $f$, and let $M$ be a finite cycle
given by $f$. If $\phi$ is the permutation that is the union of all these
cycles of fixed length, then $H$ is the centralizer of $\phi$ in $SF(\omega)$.

Let $R$ be the random graph and $Q$ the random linear order. In contrast,
$\operatorname{Aut}(R)$ and $\operatorname{Aut}(Q)$ have no nontrivial members
of finite support at all (not hard to check). Even $G=\operatorname{Aut}(E)$
where $E$ is an equivalence relation with just two infinite classes, is not
the closure of $G\cap SF(\omega)$ because an automorphism of finite support
cannot leave an equivalence class. More generally, if $R$ is a definable
relation and $\phi(a)=b$ where $\phi$ is an automorphism of finite support,
then $R(a)$ almost equals $R(b)$.

Towards a full classification of oligomorphic subgroups $H$ of $SF(\omega)$,
we use some structure theory of subgroups of $SF(\omega)$ developed in the
1970s by Peter Neumann, e.g. [33], and in two short papers by Dan Segal,
independently. Here I’m mostly using the notes on finitary permutation groups
by Chris Pinnock, available at chrispinnock.com/phdpublications/. Unless
otherwise stated references to theorems etc refer to those notes.

Let us begin by assuming that $H\leq SF(\omega)$ is 1-transitive. The Jordan-
Wielandt Theorem says for such a group $H$ that if $H$ is primitive then
$H=SF(\omega)$ or $H$ equals the group of alternating permutations of finite
support (which has index 2 in $SF(\omega)$). So we can assume otherwise. Let
$B$ be a block of imprimitivity. $B$ has to be finite (Lemma 2.2 in Pinnock),
simply because there is a permutation $\tau\in H$ moving $B$ to a disjoint set
$\tau(B)$, so that $B$ is contained in the support of $\tau$. The equivalence
relation $E$ with classes made up of the translates of $B$ is $H$-invariant,
and hence a union of 2-orbits. Since there are only finitely many 2-orbits,
there must be a maximal block of imprimitivity. Then $H$ acts primitively on
$\Omega/E$ and each induced permutation there has finite support. So it acts
highly transitively on it. This is the second type of example above, the same
finite model in each equivalence class of $E$. Note that $H$ is a subgroup of
$G_{0}\wr R$ where $R=SF(\omega)$ or $R$ is the alternating group (Thm 2.3).

If $H$ is not 1-transitive we are in the case of the first example above. It
is known that we get only finite products of 1-transitive groups, and a finite
group.

For a more detailed treatment, see Iwanow [22] who works in the more general
setting of automorphism groups of countable saturated structures. He uses the
concept of cell, a permutation group that preserves an equivalence relation
with all classes finite, and induces the full symmetric group on the
equivalence classes. A 2-cell is permutation group $G\leq_{c}S(\omega)$ such
that there exists a partition $\omega$ into $G$\- invariant classes $Y_{i}$
such that for any infinite $Y_{i}$ the group induced by $G$ on$Y_{i}$ is a
cell and is also induced by the pointwise stabilizer of the complement of
$Y_{i}$. Each oligomorphic 2-cell is a finite product of cells and a finite
algebraic closure of the empty set. Their number is countable as already
mentioned. Each cell is a finite cover of a pure set in the sense of Evans,
Macpherson, Ivanov, Finite covers, 1997. These covers have been classified.

###  6\. Harrison-Trainor and Nies: $\Pi_{r}$-pseudofinite groups

The authors of this post worked at the (now defunct) Research Centre
Coromandel in July. They started from some notes of Dan Segal (2014), which in
turn are based on [20]. The main concept in these notes is this.

######  Definition 6.1.

A group $G$ is called _pseudofinite_ if each first-order sentence true in $G$
also holds in some finite group.

In the first two sections we present a simplified account of some material in
the Segal notes. Our account is somewhat more general than the notes, firstly
as it takes into account the quantifier complexity of the sentences for which
a group needs to be pseudofinite, and secondly because a lot of this work can
be carried out in the setting of an arbitrary finitely axiomatised variety of
algebraic structures.

Throughout, let $G$ be an algebraic structure in a language $L$ with finitely
many function and constant symbols, and no relation symbols besides equality.
The $\Pi_{0}$ and the $\Sigma_{0}$ sentences are the quantifier free ones,
thought of as disjunctions of conjunctions of equalities and inequalities.
Note that satisfaction of $\Pi_{1}$ sentences is closed under taking
substructures.

######  Definition 6.2.

  * (i)

For $r\in{\mathbb{N}}$ we say that an $L$-structure $G$ is _$\Sigma_{r}$
-pseudofinite_ if $G$ is a model of the $\Sigma_{r}$-theory of finite
$L$-structures. Equivalently, each $\Pi_{r}$ sentence that holds in $G$ also
holds in some finite $L$-structure.

  * (ii)

Similarly, we define _$\Pi_{r}$ -pseudofiniteness_ of an $L$-structure $G$.

######  Definition 6.3.

We say that an $L$-structure $G$ has _named generators_ if $G$ is
$d$-generated for some $d\geq 1$, and the language $L$ contains finitely many
constant symbols $\overline{c}=(c_{1},\ldots,c_{d})$ naming such generators of
$G$.

In this case witnesses for outermost existential quantifiers be named by
terms. So we have

######  Fact 6.4.

Let $G$ be an $L$-structure with named generators. Let $\widetilde{G}$ be the
structure with the constants naming the generators omitted. Let $r\geq 1$. The
following are equivalent.

(i) $\widetilde{G}$ is $\Pi_{r+1}$-pseudofinite

(ii) $G$ is $\Pi_{r+1}$-pseudofinite

(iii) $G$ is $\Sigma_{r}$-pseudofinite.

###### Proof.

(ii)$\to$(i) and (i)$\to$(iii) are straightforward, and don’t rely on the fact
that the $c_{i}$ name generators.

For (iii)$\to$(ii), suppose a sentence
$\theta\equiv\exists\overline{x}\,\xi(\overline{x})$ holds in $G$, where
$\overline{x}$ denotes $(x_{1},\ldots,x_{m})$ and $\xi(\overline{x})$ is
$\Pi_{r}$. Since the $c_{i}$ name generators, we can pick $L$-terms $t_{j}$
without free variables as witnesses. The sentence $\xi(t_{1},\ldots,t_{m})$ is
$\Pi_{r}$ and holds in $G$. So it holds in some finite $L$-structure. Hence
$\theta$ holds in that structure. ∎

The $\Sigma_{1}$-theory of finite groups equals the $\Sigma_{1}$-theory of the
trivial group, which is decidable. Every group satisfies the
$\Sigma_{1}$-theory of the trivial group and hence is
$\Sigma_{1}$-pseudofinite. So the notion $\Sigma_{1}$-pseudofiniteness really
only makes sense for groups with named generators.

In contrast, the $\Pi_{1}$-theory of finite groups is hereditarily undecidable
by a result of Slobodskoi [46]. However, it has infinitely many decidable
completions, e.g. the theory of $({\mathbb{Z}}^{n},+)$, for each $n\geq 1$. To
see this, let $H$ be the ultraproduct of all cyclic groups of prime order. $H$
is abelian, torsion free, not f.g. and satisfies the theory of finite groups.
Any subgroup of $H$ satisfies the $\Pi_{1}$-theory of $H$. To see that $H$ has
infinite rank, let $R_{i}$, $i\in{\mathbb{N}}$ be disjoint infinite sets of
primes, let $f_{i}(p)=1$ for $p\in R_{i}$ and $0$ otherwise. Then the
$[f_{i}]$ are linearly independent over ${\mathbb{Z}}$.

####  6.1. $\Sigma_{1}$-embedding of $G$ into an ultraproduct of witness
structures

The following construction is based on Houcine and Point [20]. We fix some
variety $\mathcal{V}$ of $L$-structures, such as groups. Suppose $G$ is as in
Definition 6.3, and $G$ is $\Sigma_{1}$-pseudofinite. Let
${\left\langle{\phi_{i}^{\prime}}\right\rangle}_{i\in{\mathbb{N}}}$ be a list
of the $\Pi_{1}$-sentences that hold in $G$, with $\phi_{0}^{\prime}$ being
the conjunction of the finitely many axioms for $\mathcal{V}$. Let
$\phi_{n}=\bigwedge_{i\leq n}\phi^{\prime}_{i}$. By hypothesis on $G$ there is
a finite $L$-structure $E_{n}$ (called a witness structure) such that
$E_{n}\models\phi_{n}$. Since we are only considering $\Pi_{1}$-sentences, we
may assume that each $E_{n}$ is generated by $\overline{c}^{E_{n}}$.

Let $\mathcal{U}$ be a free ultrafilter on ${\mathbb{N}}$. Let
$E=\prod_{n}E_{n}/\mathcal{U}$ be the corresponding ultraproduct. Define an
embedding $\beta\colon G\to E$ by setting for each $L$-term $s$

$\beta(s(\overline{c}^{G}))=s(\overline{c}^{E})$.

Note that $\beta$ is well-defined and $1-1$: for each terms $s,t$, if
$G\models s(\overline{c})=t(\overline{c})$ then the sentence
$s(\overline{c})=t(\overline{c})$ equals $\phi^{\prime}_{i}$ for some $i$, and
so $E_{n}\models s(\overline{c})=t(\overline{c})$ for each $n\geq i$. One
argues similarly for the case $G\models s(\overline{c})\neq t(\overline{c})$.
So $\beta$ is a monomorphism of $L$-structures.

######  Fact 6.5.

Suppose an $L$-structure $G$ with named generators as in Definition 6.3 is
$\Sigma_{1}$-pseudofinite. The map $\beta\colon G\to E$ preserves satisfaction
of $\Sigma_{1}$-formulas in both directions. Thus, for each
$p_{1},\ldots,p_{k}\in G$ and each quantifier free $L$-formula
$\theta(x_{1},\ldots,x_{k},\tilde{y})$,

$G\models\exists\tilde{y}\ \theta(p_{1},\ldots,p_{k},\tilde{y})\Leftrightarrow
E\models\exists\tilde{y}\ \theta(\beta(p_{1}),\ldots,\beta(p_{k}),\tilde{y})$.

###### Proof.

We may incorporate the parameters into $\theta$, so we may assume that there
are none. Let $\phi\equiv\exists\tilde{y}\ \theta(\tilde{y})$. For the
nontrivial implication suppose that $E\models\phi$. If $G\models\lnot\phi$,
then $E_{n}\models\lnot\phi$ for almost all $n$, contradiction. So
$G\models\phi$. ∎

####  6.2. The number of factors needed for being in a verbal subgroup

In this section we only consider the case that $G$ is a group. We will explain
the result of Segal that if $G$ is $\Pi_{2}$-pseudofinite then the verbal
subgroups $G^{(n)}$ and $\langle G^{q}\rangle$, $n,q\geq 1$, are definable in
$G$ by a positive $\Sigma_{1}$ formula.

Below $G$ satisfies Definition 6.3 where $d$ denotes the number of generators.
The language $L$ consists of symbols for the group operations, the neutral
element, and constants $c_{1},\ldots,c_{d}$ naming the generators.

######  Definition 6.6.

Let $d,r\geq 1$. Let $w$ be a term with free variables $x_{1},\ldots,x_{k}$ in
the language of group theory, identified with an element of the free group
$F_{k}$. We say that $w$ is _$r$ -bounded for $d$_ if for each finite
$d$-generated group $H$, we have

$w(H)=w^{*r}(H)$.

Here for any group $H$, by $w(H)$ one denotes the usual verbal subgroup which
is generated by the values of $w$, and $w^{*r}(H)$ is the set of products of
up to $r$ many values of $w$ or their inverses.

Nikolov and Segal [40, Thm 1.7], or [41, Thm. 1.2], show that this holds for
the terms $x^{q}$, where $q\geq 1$, and iterated commutators such as $[x,y]$
or $[[x,y],[z,w]]$. For such terms, the result below (for pseudofinite groups)
was established in [20, Prop. 3.8], but an additional hypothesis was needed
for the case of terms $x^{q}$.

######  Proposition 6.7.

Suppose a $d$-generated group $G$ with named generators as in Definition 6.3
is $\Sigma_{1}$-pseudofinite w.r.t. the language $L$. Suppose further that $w$
is $r$-bounded for $d$. Then $w(G)=w^{*r}(G)$.

By Fact 6.4 the hypothesis holds if $G$ is $\Pi_{2}$-pseudofinite w.r.t. the
language of group theory. In this case $w(G)$ is $\Sigma_{1}$-definable
without parameters in that language.

###### Proof.

Write $g_{i}=c_{i}^{G}$ and $\overline{g}=(g_{1},\ldots,g_{k})$. Suppose
$t(\overline{g})\in w(G)$ for some term $t$. That is, for some $m$, there are
$k$-tuples $\overline{z}_{j}$ of elements of $G$ and $\epsilon_{j}=-1,1$, for
$1\leq j\leq m$, such that

$t(\overline{g})=\prod_{1\leq j\leq m}w(\overline{z}_{j})^{\epsilon_{j}}$.

Then $E$ satisfies the $\Sigma_{1}$-sentence
$\exists\overline{z}_{1}\ldots\exists\overline{z}_{m}\,[t(\overline{c})=\prod_{1\leq
j\leq m}w(\overline{z}_{j})^{\epsilon_{j}}]$, and hence the ultrafilter
$\mathcal{U}$ contains the set $S$ of those $n$ such that $E_{n}$ satisfies
this sentence. By hypothesis on $w$ and since $E_{n}$ is $d$-generated by the
$c_{i}^{E_{n}}$, for each $n\in S$ there is a choice of $\eta_{\ell}=-1,1$,
for $1\leq\ell\leq r$, such that

$E_{n}\models\exists\overline{y}_{1}\ldots\exists\overline{y}_{m}\,[t(\overline{c})=\prod_{1\leq
j\leq r}w(\overline{y}_{j})^{\eta_{j}}]$.

Since $\mathcal{U}$ is an ultrafilter, there must be one choice
$(\eta_{\ell})_{1\leq\ell\leq r}$ so that the $n$ where this choice applies
form a set in $\mathcal{U}$. Hence for this choice we have

$E\models\exists\overline{y}_{1}\ldots\exists\overline{y}_{m}\,[t(\overline{c})=\prod_{1\leq
j\leq r}w(\overline{y}_{j})^{\eta_{j}}]$.

By Fact 6.5 this implies that $t(\overline{g})\in w^{*r}(G)$ as required. ∎

As Houcine and Point point out [20, Lemma 2.11], parameter definable quotients
and subgroups of pseudofinite groups are again pseudofinite. Also, finitely
generated pseudofinite groups that are of fixed exponent, or soluble, are
finite [20, Prop. 3.9]. So, $G$ is an extension of a pseudofinite group, the
verbal subgroup given by a term as above, by a finite group satisfying the law
given by the term.

####  6.3. Effectiveness considerations

We show that a variant of the basic construction above leading to Fact 6.5 is
effective using the structure $G$ as an oracle.

_Effective ultraproducts._ Given a sequence
${\left\langle{E_{n}}\right\rangle}$ of uniformly computable structures for
the same finite signature, and a non-principal ultrafilter $\mathcal{U}$ for
the Boolean algebra of recursive sets, one can form the structure
$E=\prod_{rec}E_{n}/{\mathcal{U}}$. It consists of
$\sim_{\mathcal{U}}$-equivalence classes of recursive functions $f$ such that
$f(n)\in E_{n}$ for each $n$. Here $f\sim_{\mathcal{U}}g$ denotes that
functions $f,g$ agree on a set in $\mathcal{U}$. We interpret the relation and
functions symbols on $E$ as usual.

A version of Los’ Theorem restricted to existential formulas holds.

######  Fact 6.8.

For each formula
$\theta(x_{1},\ldots,x_{m})\equiv\exists\widetilde{y}\,\xi(x_{1},\ldots,x_{m},\widetilde{y})$
with $\xi$ quantifier free, and each $[f_{1}],\ldots,[f_{m}]\in E$,

$E\models\theta([f_{1}],\ldots[f_{m}])\Leftrightarrow R=\\{n\colon
E_{n}\models\theta(f_{1}(n),\ldots f_{m}(n))\\}\in\mathcal{U}$.

###### Proof.

Note that the set $R$ is computable. For the implication from left to right,
suppose $[h_{1}],\ldots,[h_{k}]$ are witnesses for
$E\models\theta([f_{1}],\ldots[f_{m}])$, for recursive functions
$h_{1},\ldots,h_{k}$.This shows that $R\in\mathcal{U}$ by definition of the
ultraproduct.

For the implication from right to left, note that when $n$ is in the
computable set $R$ one can search for the witnesses $w_{n}$ in $E_{n}$. So one
can define computable witness functions $h_{1},\ldots,h_{k}$ for
$E\models\theta([f_{1}],\ldots[f_{m}])$, assigning a vacuous value in $E_{n}$
in case $n\not\in R$. ∎

To obtain an effective version of Fact 6.5, let $\psi_{i}$ be an effective
list of all the $\Pi_{1}$ sentences in $L$, where $\psi_{0}$ is the
conjunction of the laws of $\mathcal{V}$. We modify the construction of the
$E_{n}$ as follows. Given $n$, look for the least stage $s$ and a finite
$L$-structure, called $E_{n}$, such that $E_{n}$ satisfies each $\psi_{i}$,
$i\leq n$, that has not been shown to fail in $G$ by stage $s$, in the sense
that a counterexample has been found among the first $s$ elements of $G$.

Now define the restricted ultraproduct $E$ as above. The argument for the fact
can be carried out as before: Suppose that $E\models\phi$ for an existential
sentence $\phi$. If $G\models\lnot\phi$, then $E_{n}\models\lnot\phi$ for
almost all $n$. This contradicts the weak version of Los theorem above.

The argument of Prop 6.7 also works with this restricted ultraproduct. Note
that the set $S$ in the proof of Prop 6.7 is computable since the $E_{n}$ are
finite and given by strong indices. The set of $n$ for which a particular
choice of $\eta_{\ell}$ works is also computable.

The upshot: if $G$ is computable, then we have a canonical ultraproduct
version $E$ of $G$, with a $\Sigma_{1}$ elementary embedding, and this version
$E$ is in a sense effective as well, except for the ultrafilter, which is
necessarily high in a sense specified and proved in a 2020 preprint by Lempp,
Miller, Nies and Soskova available at
www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/download.php?selected-
id=769.

##  Part II Computability theory and randomness

###  7\. Greenberg, Nies and Turetsky: Characterising SJT reducibility

####  7.1. The basic concepts

#####  7.1.1. SJT- reducibility and its equivalents

SJT-reducibility was introduced in [35, Exercise 8.4.37].

######  Definition 7.1 (Main: SJT-reducibility).

For an oracle $B$, a $B$–c.e. trace is a u.c.e. in $B$ sequence
${\left\langle{T_{n}}\right\rangle}_{n\in{\mathbb{N}}}$ of finite sets. For a
function $h$, such a trace is $h$-bounded if $|T_{n}|\leq h(n)$ for each $n$.
A set $A$ is jump-traceable if there is a computably bounded $\emptyset$–c.e.
trace ${\left\langle{T_{n}}\right\rangle}_{n\in{\mathbb{N}}}$ such that
$J^{A}(n)$ is in $T_{n}$ if it is defined.

For sets $A,B$, we write $A\leq_{SJR}B$ if for each order function $h$, there
is a $B$–c.e., $h$-bounded trace for $J^{A}$.

This is transitive by argument similar to [34, Theorem 3.3].

(Question: Is “strongly superlow” reducibility equivalent to $\leq_{SJR}$?
This was also mentioned in [35, Exercise 8.4.37], there shown to be at least
as strong.)

######  Proposition 7.2.

For each $K$-trivial set $B$, there is a c.e. $K$-trivial set $A$ such that
$A\not\leq_{SJR}B$.

###### Proof.

For some fixed computable function $h$ there is a functional $\Psi$ and
$K$-trivial set $A$ such that $\Psi^{A}$ has no c.e. trace bounded by $h$, by
a result of [6]. (Also see [35, 8.5.1] where $h(n)=0.5\log\log n$ works.)
Encoding $\Psi$ into $J$, we get a fixed computable function $g$ so that the
statement holds for $J$ and $g$ instead of $\Psi$ and $h$.Relativizing to $B$
we can retain the same $g$, so for each $B$ there is a $K$-trivial in $B$ set
$A$ such that $J^{A\oplus B}$ does not have a $B$-c.e. trace bounded by $g$.
In particular, $A\not\leq_{SJR}B$.

If $B$ is $K$-trivial, it is low for $K$, and hence $A$ is also $K$-trivial.
Finally, there is $K$-trivial c.e. set $\widehat{A}\geq_{T}A$, so we can make
$A$ c.e. ∎

######  Definition 7.3.

Let $c$ be a cost function. For sets $A,B$, we write $A\models_{B}c$ if there
is a $B$-computable enumeration of ${\left\langle{A_{s}}\right\rangle}$
satisfying $c$.

######  Definition 7.4 (Benign cost functions).

A cost function $\mathbf{c}$ is _benign_ [16] if from a rational $\epsilon>0$,
we can compute a bound on the length of any sequence $n_{1}<s_{1}\leq
n_{2}<s_{2}\leq\cdots\leq n_{\ell}<s_{\ell}$ such that
$\mathbf{c}(n_{i},s_{i})\geq\epsilon$ for all $i\leq\ell$. For example,
$\mathbf{c}_{\Omega}$ is benign, with the bound being $1/\epsilon$.

Conjecture that strengthens proposition above: For each benign $c$, for each
$B\models c$, there is a c.e. $A\models c$ such that $A\not\leq_{SJR}B$.

Conjecture for each noncomputable c.e. $E$ there are c.e.
$\leq_{SJR}$-incomparable $A,B\leq_{T}E$.

Fact $\leq_{SJR}$ is $\Sigma^{0}_{3}$ on the $K$-trivials. Density might be
easy on the $K$-trivials using this.

#####  7.1.2. Two relevant randomness notions

######  Definition 7.5 (Demuth randomness).

A _Demuth test_ is a seqence
${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$ of open subsets of
$2^{{\mathbb{N}}}$ such that $\mathbf{\lambda}G_{m}\leq 2^{-m}$ and there is
an $\omega$-c.a. function $p$ such that $G_{m}=[W_{p(m)}]^{\prec}$. Since the
function $p$ is $\omega$-c.a., there are a computable approximation function
$p(m,s)$ and a computable bound $b$ such that $\lim_{s}p(m,s)=p(m)$ and the
number of changes is bounded by $b(m)$. One writes $G_{m}[t]$ for
$[W_{p(m,t),t}]^{\prec}$, the approximation of the $m$-th component at stage
$t$. One may assume that $\mathbf{\lambda}G_{m}[t]\leq 2^{-m}$ for each $t$ by
cutting off the enumeration of $G_{m}$ when it attempts to exceed that
measure. One says that $Z$ is _Demuth random_ if for each such test, one has
$Z\not\in G_{m}$ for almost every $m$.

######  Definition 7.6 (Weak Demuth randomness).

A _nested Demuth test_ is a Demuth test
${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$ such that
$G_{m}\supseteq G_{m+1}$ for each $m$. One says that $Z$ is _weakly Demuth
random_ if $Z\not\in\bigcap_{m}G_{m}$ for each nested Demuth test
${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$. Replacing $G_{m}[t]$
by $\bigcap_{i\leq m}G_{i}[t]$ (and noting that the number of changes remains
computably bounded), one may assume that the approximations are nested at each
stage $t$, i.e., $G_{m}[t]\supseteq G_{m+1}[t]$ for each $m$.

####  7.2. Equvalent characterizations of $\leq_{SJR}$

######  Theorem 7.7.

The following are equivalent for $K$-trivial c.e. sets $A,B$.

  * (a)

$A\leq_{SJR}B$

  * (b)

$A\models_{B}\mathbf{c}$ for every benign cost function $\mathbf{c}$

  * (c)

$A\leq_{T}B\oplus Y$ for each ML-random set $Y$ that is not weakly Demuth
random

  * (d)

$A\leq_{T}B\oplus Y$ for each ML-random set $Y\in\mathcal{C}$, where
$\mathcal{C}$ is the class of the $\omega$-c.a., superlow, or superhigh sets.

We remark that the implication (b) $\Rightarrow$ (a) was essentially obtained
by Greenberg and Nies [16, Prop. 2.1]. They proved the following. Let $A$ be a
c.e., jump-traceable set, and let $h$ be an order function. Then there is a
benign cost function $c$ such that if $A$ obeys $c$, then $J^{A}$ has a c.e.
trace which is bounded by $h$. Suppose now that $A\models_{B}c$. Apply the
argument in the proof of [16, Prop. 2.1] to a $B$-computable enumeration of
$A$ showing this. Then the $h$-bounded trace
${\left\langle{T_{n}}\right\rangle}$ for $J^{A}$ constructed there is c.e.
relative to $B$.

For $\mathcal{C}\subseteq\mbox{\rm{MLR}}$ define $\mathcal{C}^{\diamond}$. By
the implication (a) $\Rightarrow$ (c) we obtain:

######  Corollary 7.8.

Let $\mathcal{C}$ be a nonempty class of ML-randoms that contains no weakly
Demuth random. Then $\mathcal{C}^{\diamond}$ is downward closed under
$\leq_{SJR}$.

For instance, let $\mathcal{C}=\\{\Omega_{R}\\}$ for a co-infinite computable
set $R$. This shows that the subideals of $K$-trivials considered in [14, 15]
are SJT-ideals.

We will prove the implications of the theorem in a cycle, starting from (b).
The implications (b) $\Rightarrow$ (c) and (c) $\Rightarrow$ (d) rely on
literature results, or standard methods from the literature. The implication
(d) $\Rightarrow$ (a) combines methods from [36] and [4]. The implication (a)
$\Rightarrow$ (b) uses the box promotion method; for background see [17, 18].

#####  7.2.1. Proof of (b) $\Rightarrow$ (c)

Hirschfeldt and Miller showed that for each null $\Pi^{0}_{2}$ class
$\mathcal{H}\subseteq 2^{{\mathbb{N}}}$ there is a cost function $\mathbf{c}$
such that $A\models\mathbf{c}$ and $Y\in\mbox{\rm{MLR}}\cap\mathcal{H}$
implies $A\leq_{T}Y$; see [35, proof of 5.3.15] for a proof of this otherwise
unpublished result.

Suppose that a ML-random set $Y$ fails a nested Demuth test
${\left\langle{G_{m}}\right\rangle}$. Then $Y\in\mathcal{H}=\bigcap_{m}G_{m}$
which is a $\Pi^{0}_{2}$ class. We will apply the method of Hirschfeldt and
Miller but incorporating the additional oracle set $B$, and using the
particular representation of the $\Pi^{0}_{2}$ null class by a nested Demuth
test to ensure that the cost function $\mathbf{c}$ is benign. Also see post on
weak Demuth randomness by Kučera and Nies in [8]

Let $p(m)$ and its approximation $p(m,t)$ be as in Definition 7.6 of nested
Demuth tests. We define the benign cost function $\mathbf{c}$ as follows.
Define for $k\leq t$

$\displaystyle r(k,t)$ $\displaystyle=$ $\displaystyle\min\\{m\colon\,\exists
s.k<s\leq t\,[p(m,s-1)\neq p(m,s)]\\}$ $\displaystyle V_{k,t}$
$\displaystyle=$ $\displaystyle\bigcup_{k\leq s\leq t}G_{r(k,s)}[s]$
$\displaystyle\mathbf{c}(k,t)$ $\displaystyle=$
$\displaystyle\mathbf{\lambda}V_{k,t}.$

Clearly $r(k-1,t)\geq r(k,t)$ for $k>0$, hence the $V_{k,t}$ are nested and
$\mathbf{c}(k,t)$ is nonincreasing in $k$. Similarly, $\mathbf{c}(k,t)$ is
nondecreasing in $t$. Note that if $p(m,s)$ has stopped changing by a stage
$k$, then $r(k,t)>m$ for each $t\geq k$, and hence $V_{k,t}$ is contained in
the final version $G_{m}$ of the $m$-th component. By the conventions in
Definition 7.6 above, if $\mathbf{c}(k,t)>2^{-m}$ then $p(m,s-1)\neq p(m,s)$
for some $s$ in the interval $(k,t]$. Since the number of changes of $p(m,s)$
is bounded computably in $m$, this shows that the cost function $\mathbf{c}$
is indeed benign.

Suppose now that $A\models_{B}\mathbf{c}$ via a $B$-computable approximation
${\left\langle{A_{s}}\right\rangle}$. To show $A\leq_{\mathrm{T}}Y\oplus B$
for each ML-random set $Y\in\mathcal{\bigcap}_{m}G_{m}$, we enumerate a
Solovay test $\mathcal{S}$ relative to $B$, i.e., a uniformly $\Sigma^{0}_{1}$
sequence ${\left\langle{\mathcal{S}_{n}}\right\rangle}$ relative to $B$ such
that $\sum_{n}\mathbf{\lambda}\mathcal{S}_{n}<\infty$. At stage $s$, when
$x<s$ is least such that $A_{s}(x)\neq A_{s-1}(x)$, list $V_{x,s}$ in
$\mathcal{S}$. This yields a Solovay test relative $B$ by the hypothesis that
the approximation of $A$ obeys $\mathbf{c}$.

Since $B$ is low for ML-randomness, the set $Y$ is ML-random relative to $B$.
Hence $Y$ passes the Solovay test $\mathcal{S}$. So choose $s_{0}$ such that
$Y\not\in V$ for any $V$ listed in $S$ after stage $s_{0}$. Given an input
$x\geq s_{0}$, using $Y$ as an oracle compute $t>x$ such that
$[Y\\!\upharpoonright_{t}]\subseteq V_{x,t}$. We claim that $A(x)=A_{t}(x)$.
Otherwise $A_{s}(x)\neq A_{s-1}(x)$ for some $s>t$, which would cause
$V_{x,s}$ (or some superset $V_{y,s}$, $y<x$) to be listed in $G$, contrary to
$Y\in V_{x,t}$.

#####  7.2.2. Proof of (c) $\Rightarrow$ (d)

Note that each superlow set is $\omega$-c.a. So it suffices to show that no
$\omega$-c.a. set, and no superhigh set, is weakly Demuth random. For
$\omega$-c.a. sets this is immediate from the definitions. For superhigh sets,
this is a result of Kučera and Nies [26, Cor. 3.6].

#####  7.2.3. Proof of (d) $\Rightarrow$ (a)

For convenience we restate the implication to be shown:

Let $\mathcal{C}$ be the class of superlow, or of superhigh sets. Suppose $A$
and $B$ are $K$-trivial c.e. sets. If $A\leq_{\mathrm{T}}Y\oplus B$ for each
$Y\in\mathcal{C}\cap\mbox{\rm{MLR}}$, then $A\leq_{SJR}B$.

We remark that for this implication, the hypothesis suffices that $A$ is c.e.
and superlow, and $B$ is Demuth traceable as discussed below; in particular,
this holds if $B$ is c.e. and superlow.

As mentioned, the proof of this implication combines methods from Nies [36]
and Bienvenu et al. [4]. Below we will review and use some technical notions
from these articles. First we consider [4, Def. 1.7]. Given an oracle $B$, a
$\textup{Demuth}_{\textup{BLR}}\langle B\rangle$ test generalises a Demuth
test ${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$ in that
$G_{m}\subseteq 2^{{\mathbb{N}}}$ is a $\Sigma^{0}_{1}(B)$ class with
$\mathbf{\lambda}G_{m}\leq 2^{-m}$, and there is a function $f$ taking $m$ to
an index for $G_{m}$ such that $f$ has a $B$-computable approximation $g$,
with $g(m,t)$ having a number of changes that is computably bounded in $m$.
(Here we will only need the case that $f$ is $\omega$-c.a., in which case the
only difference to usual Demuth tests is that the versions of the components
are uniformly $\Sigma^{0}_{1}(B)$, rather than $\Sigma^{0}_{1}$.)

The authors in [4] defined that an oracle $B$ is low for
$\textup{Demuth}_{\textup{BLR}}$ tests if every
$\textup{Demuth}_{\textup{BLR}}\langle B\rangle$ test can be covered by a
Demuth test, in the sense that passing the Demuth test implies passing the
$\textup{Demuth}_{\textup{BLR}}\langle B\rangle$ test. In [4, Thm. 1.8] they
characterized such oracles via a tracing condition called Demuth traceability.
For c.e. sets, this condition is equivalent to being jump traceable, or again
superlow [4, Prop. 4.3].

The following lemma holds for any oracle $B$. We will prove it shortly.

######  Lemma 7.9.

For a given order function $h$ and a superlow c.e. set $A$, one can build a
$\textup{Demuth}_{\textup{BLR}}\langle B\rangle$ test
$(\mathcal{H}_{m})_{m\in{\mathbb{N}}}$ such that, if
$A\leq_{\mathrm{T}}Y\oplus B$ for some ML-random set $Y$ passing this test,
then the function $J^{A}$ has a $B$-c.e. trace with bound $h$.

Nies [36] defined a class $\mathcal{C}\subseteq 2^{\mathbb{N}}$ to be _Demuth
test–compatible_ if each Demuth test is passed by a member of $\mathcal{C}$.
Using some methods from [13], he showed in [36, Section 4] that the superlow
ML-random sets, as well as the superhigh ML-random sets, are Demuth
test–compatible.

If a class $\mathcal{C}$ is Demuth test–compatible and $B$ is Demuth
traceable, then each $\textup{Demuth}_{\textup{BLR}}\langle B\rangle$-test is
passed by a set in $\mathcal{C}$. So the lemma suffices to establish the
implication (d) $\Rightarrow$ (a) in question.

To verify Lemma 7.9, let $\Phi$ be a Turing functional such that
$\Phi(0^{e}1Y\oplus B)=\Phi_{e}(Y\oplus B)$ for each $e,Y$. We reduce the
lemma to the following.

######  Claim 7.10.

There is a $\textup{Demuth}_{\textup{BLR}}\langle B\rangle$ test
$(\mathcal{S}_{m})_{m\in{\mathbb{N}}}$ such that, if $A=\Phi^{Y\oplus B}$ for
some $Y$ passing this test, then $J^{A}$ has a $B$-c.e. trace with bound $h$.

This claim suffices to obtain Lemma 7.9: let
$(\mathcal{H}_{m})_{m\in{\mathbb{N}}}$ be the
$\textup{Demuth}_{\textup{BLR}}\langle B\rangle$ test obtained as in [36,
Lemma 2.6] applied to the test $(\mathcal{S}_{m})_{m\in{\mathbb{N}}}$. Thus,
if a set $Y$ passes $(\mathcal{H}_{m})_{m\in{\mathbb{N}}}$, then $0^{e}1Y$
passes $(\mathcal{S}_{m})_{m\in{\mathbb{N}}}$ for each $e$. By hypothesis of
Lemma 7.9, $A\leq_{\mathrm{T}}Y\oplus B$ for some $Y$ passing
$(\mathcal{H}_{m})_{m\in{\mathbb{N}}}$, so we have $A=\Phi_{e}^{Y\oplus B}$
for some $e$, and hence $A=\Phi({0^{e}1Y}\oplus B)$. Since $0^{e}1Y$ passes
$(\mathcal{S}_{m})_{m\in{\mathbb{N}}}$, we can conclude from the claim that
$J^{A}$ has a $B$-c.e. trace with bound $h$.

It remains to prove Claim 7.10. Write $\mathcal{U}_{e}=[W^{B}_{e}]^{\prec}$.
For the duration of the proof of the claim, a sequence
${\left\langle{G_{m}}\right\rangle}$ of open sets will be called an _$(A,B)$
-special test_ if there is a Turing functional $\Gamma$ such that $G_{m}$ is
the final version of the sets $G_{m}[t]=\mathcal{U}_{\Gamma^{A}(m,t)}$ over
stages $t$, and there is a computable function $g$ such that the number of
changes of $\Gamma^{A}(m,t)$ is bounded by $g(m)$. A set $Y$ passes such a
test in the usual sense of Demuth tests, namely, $Y\not\in G_{m}$ for almost
all $m$.

We first observe that since $A$ is superlow and c.e., there is a
$\textup{Demuth}_{\textup{BLR}}\langle B\rangle$ test
${\left\langle{\mathcal{S}_{m}}\right\rangle}$ that covers
${\left\langle{G_{m}}\right\rangle}$ in the sense that each $Y$ passing
${\left\langle{\mathcal{S}_{m}}\right\rangle}$ passes
${\left\langle{G_{m}}\right\rangle}$. To see this, let $\Theta$ be a Turing
functional such that $\Theta^{X}(m,i)$ is the $i$-th value of
$\Gamma^{X}(m,i)$, for each oracle $X$. Note that by [36, Lemma 2.7] there is
a computable enumeration $(A_{s})_{s\in{\mathbb{N}}}$ of $A$ and a computable
function $f$ such that for at most $f(m,i)$ times a computation
$\Theta^{A_{s}}(m,i)$ is destroyed. At stage $t$, let

$\mathcal{S}_{m}[t]=\mathcal{U}_{\Theta^{A_{t}}(m,i)}$

where $i$ is maximal such that the expression on the right is defined at stage
$t$. Clearly the number of times a version $\mathcal{S}_{m}[t]$ changes is
bounded by $\sum_{i=0}^{g(m)}f(m,i)$. Thus,
$(\mathcal{S}_{m})_{m\in{\mathbb{N}}}$ is a Demuth test. If an oracle $Y$ is
in $G_{m}$ then $Y$ is in the final version $\mathcal{S}_{m}[t]$, so the new
test indeed covers ${\left\langle{G_{m}}\right\rangle}$.

So to establish Claim 7.10 it suffices to build an $(A,B)$-special test
${\left\langle{G_{m}}\right\rangle}$ in place of
${\left\langle{\mathcal{S}_{m}}\right\rangle}$. To do so, we mostly follow
[36, proof of Thm 3.2]. For $m\in{\mathbb{N}}$ let

$I_{m}=\\{x\colon\,2^{m}\leq h(x)<2^{m+1}\\}$.

At stage $t$, let $u$ be the maximum use of the computations $J^{A}(x)$ for
$x\in I_{m}$ that exist. We enumerate into the current version $G_{m}[t]$ all
oracles $Z$ such that $\Phi_{t}^{Z\oplus B}\succeq A\\!\upharpoonright_{u}$,
as long as the measure stays below $2^{-m}$. Whenever a new computation
$J^{A}(x)$ for $x\in I_{m}$ converges at a stage, we start a new version of
$G_{m}$. Clearly, there will be at most $\\#I_{m}$ many versions.

More formally, there is a Turing functional $\Gamma$ such that for each string
$\alpha$ of length $t$,

$\mathcal{U}_{\Gamma^{\alpha}(m,t)}=\\{Z\colon\,\forall x\in I_{m}\
[J^{\alpha}_{t}(x)\downarrow\text{with
use}\,u\Rightarrow\alpha\\!\upharpoonright_{u}\preceq\Phi^{Z\oplus
B}_{t}]\\}.$

Let $G_{m}[t]=\mathcal{U}_{\Gamma^{A}(m,t)}^{(\leq 2^{-m})}$. Here for a
$\Sigma^{0}_{1}(B)$ set $\mathcal{W}$ and rational $\epsilon>0$, as in the
Cut-off Lemma [36, Lemma 2.1] by $\mathcal{W}^{(\leq\epsilon)}$ one denotes
the $\Sigma^{0}_{1}(B)$ set given by the enumeration capped by measure
$\epsilon$. By the uniformity of the Cut-off Lemma, from $m,t$ with the help
of oracle $A$ we can compute an index for this effectively open class. Thus,
the versions $G_{m}[t]$ define an $(A,B)$-special test
$(G_{m})_{m\in{\mathbb{N}}}$.

The $B$-c.e. trace $(T_{x})_{x\in{\mathbb{N}}}$ is defined as follows. At
stage $t$, for each string $\alpha$ of length $t$ such that
$y=J_{t}^{\alpha}(x)$ is defined and the measure of the current approximation
to the c.e. open set $\mathcal{U}_{\Gamma^{\alpha}(m,t)}$ exceeds $2^{-m}$,
put $y$ into $T_{x}$. The idea is that, if $y=J^{A}(x)$, then this must happen
for some $\alpha\prec A$, otherwise $Y$ can be put into $G_{m}$ because there
is no cut-off.

The verification is similar to [36, proof of Thm 3.2] _mutatis mutandis_. We
omit the proofs of the two claims that follow, which are similar to the claims
in the proof of the corresponding result [36, Thm 3.2].

Claim 1. $(T_{x})_{x\in{\mathbb{N}}}$ is a $B$-c.e. trace such that for each
$x$ we have $\\#T_{x}\leq h(x)$.

Claim 2. For almost every $x$, if $y=J^{A}(x)$ is defined, then $y\in T_{x}$.

This completes the proof of Claim 7.10 and hence Lemma 7.9, and hence of the
implication in question.

#####  7.2.4. Proof of (a) $\Rightarrow$ (b)

This implication works in the context of much weaker assumptions on $A$ and
$B$. We state this separately.

######  Proposition 7.11.

If $A\leq_{SJR}B$ and $B$ is jump traceable, then for every benign cost
function $c$, we have $A\models_{B}c$.

First we need another lemma.

######  Lemma 7.12.

Suppose $T$ is a finite tree, and $v_{0},\dots,v_{n-1}\in T$ are pairwise
distinct, such that each $v_{i}$ has at least 2 children in $T$. Then $T$ has
at least $n+1$ leaves.

We omit the proof, which is a simple induction on $n$.

###### Proof of Proposition 7.11.

Fix $c$ a benign cost function and $f$ an $\omega$-c.a. function with
$c(f(n))<2^{-n}$ for all $n$. We also denote by $f$ a computable approximation
to $f$, so that $\lim_{s}f(n,s)=f(n)$ for all $n$, and such that for each $n$,
$|\\{f(n,s):s\in\omega\\}|\leq g(n)$, where $g$ is some total computable
function. We may assume that $f(n,s)$ is non-decreasing in both $n$ and $s$.
Fix $h$ such that $B$ is $h$-JT.

First we employ standard tricks to assume we already have the traces for the
partial functions we intend to build. We define sets $I_{n}^{e}$ and
$J_{n}^{e}$ for $e<n<\omega$:

  * •

For each $e$, the sets $\\{I_{n}^{e}:e<n<\omega\\}$ partition $\omega^{[2e]}$
such that

$|I_{n}^{e}|=g(n)+\sum_{i<n}h({\left\langle{2e,n+1,i}\right\rangle});$

  * •

For each $e$, the sets $\\{J_{n}^{e}:e<n<\omega\\}$ partition
$\omega^{[2e+1]}$ such that

$|J_{n}^{e}|=2^{\sum\\{h({\left\langle{2e+1,x,i}\right\rangle})\ :\ x\in
I_{n}^{e}\ \&\ i<n\\}}.$

We then define $k$ an order function such that for all $e<n$ and all $x\in
I^{e}_{n}\cup J^{e}_{n}$, $k(x)\leq n$.

We will build partial functions $\Phi^{A}$ and $\Psi^{B}$. Fix an effective
listing of all c.e. $h$-traces and all oracle c.e. $k$-traces. For
$e={\left\langle{e_{0},e_{1}}\right\rangle}$, we will construct $\Phi$ and
$\Psi$ on $\omega^{[2e]}\cup\omega^{[2e+1]}$ under the assumption that the
$e_{0}$th element of the first listing traces $\Psi^{B}$ and the $e_{1}$th
element of the second listing traces $\Phi^{A}$ with oracle $B$. For the
remainder of the construction, fix $e$, and let $(V_{y})_{y\in\omega}$ and
$(U_{x}^{-})_{x\in\omega}$ be these elements, respectively. We will drop the
$e$ superscripts on the $I$ and $J$.

Suppose first that $(U_{x})_{x\in\omega}$ were an oracle-free c.e. $k$-trace
of $\Phi^{A}$. We will have a module for each $n>e$. Our module for $n$ seeks
to test $A$ at various lengths, in particular at length $f(n)$. At stage
$s=n$, or at stage $s>n$ with $f(n,s)\neq f(n,s-1)$, the module will test
length $f(n,s)$. It will also test various lengths as they are provided to it
by the $n+1$ module.

For a length $\ell$, it will first test $A\\!\upharpoonright_{\ell}$ in an
element of $x\in I_{n}$ – that is, we define $\Phi^{\sigma}(x)=\sigma$ for all
$\sigma\in 2^{\ell}$, and we monitor the strings enumerated into $U_{x}$. This
will narrow down the possibilities for $A\\!\upharpoonright_{\ell}$ to a set
of at most $n$ strings. The module will then test each of those strings in
$J_{n}$ (we will say more about how testing is done in $J_{n}$ in a moment).
If more than one of those strings were to pass this second test, we would
promote $\ell$, i.e. tell the $n-1$ module that it is responsible for testing
$A\\!\upharpoonright_{\ell}$. We will arrange that the $n$ module promotes at
most $n-1$ lengths, so that the $n-1$ module will need to handle at most
$g(n-1)+n-1$ lengths.

For $n=e+1$, the $n$ module will still declare lengths to be promoted, even
though there is no $n-1$ module to promote them to. This will not affect the
running of the $n$ module, and so it will continue on as if there were an
$n-1$ module.

Of course, $(U_{x})_{x\in\omega}$ only traces $\Phi^{A}$ with oracle $B$, so
we will need to rely on $(V_{y})_{y\in\omega}$ to approximate this. When we
decide to test a length $\ell$ at $x\in I_{n}$, we will simultaneously define
$\Psi^{Y}({\left\langle{2e+1,x,i}\right\rangle})$ for $i<n$ and all oracles
$Y$ to be the $i$th element enumerated into $U_{x}^{Y}$, if such an element
exists. Then

$A\\!\upharpoonright_{\ell}\in U_{x}\subseteq
2^{\ell}\cap\bigcup_{i<n}V_{{\left\langle{2e+1,x,i}\right\rangle}},$

which has size at most $\sum\\{h({\left\langle{2e+1,x,i}\right\rangle})\ :\
i<n\\}$. We will test each of these strings on $J_{n}$. So we will test at
most $\sum\\{h({\left\langle{2e+1,x,i}\right\rangle})\ :\ x\in I_{n}^{e}\ \&\
i<n\\}$ strings on $J_{n}$, which the reader will note is the exponent of the
size of $J_{n}$.

The oracle $B$, using $(U_{x}^{B})_{x\in\omega}$, will have an opinion as to
which lengths should be promoted. Again, we will arrange that $B$ sees at most
$n-1$ lengths which are to be promoted by the $n$ module. We define
$\Psi^{Y}({\left\langle{2e,n,i}\right\rangle})$ for $i<n-1$ and all oracles
$Y$ to be the $i$th length which $Y$ believes the $n$ module should promote.
So the lengths $B$ believes should be promoted by the $n$ module will be
elements of $\bigcup_{i<n-1}V_{{\left\langle{2e,n,i}\right\rangle}}$, which
has size at most $\sum_{i<n-1}h({\left\langle{2e,n,i}\right\rangle})$. Thus
the $n-1$ module will need to handle at most
$g(n-1)+\sum_{i<n-1}h({\left\langle{2e,n,i}\right\rangle})$, which the reader
will note is the size of $I_{n-1}$. So each $I_{n}$ is large enough to test
every length the $n$ module must consider.

We must explain what it means to test a string on $J_{n}$. We identify $J_{n}$
with $2^{\sum\\{h({\left\langle{2e+1,x,i}\right\rangle})\ :\ x\in I_{n}^{e}\
\&\ i<n\\}}$, which we think of as a hypercube of side length 2 and dimension
$\sum\\{h({\left\langle{2e+1,x,i}\right\rangle})\ :\ x\in I_{n}^{e}\ \&\
i<n\\}$. When we seek to test a string $\sigma$ on $J_{n}$, we choose an axis
$d$ of the hypercube, split the hypercube into two pieces orthogonal to this
axis, and define $\Phi^{\sigma}(x)=\sigma$ for all $x$ belonging to one of
these pieces. To that end, for each
$d<\sum\\{h({\left\langle{2e+1,x,i}\right\rangle})\ :\ x\in I_{n}^{e}\ \&\
i<n\\}$, let $J_{n}(d)=\\{\tau\in J_{n}:\tau(d)=0\\}$. For each string
$\sigma$ that we seek to test on $J_{n}$, we will choose a unique $d$ and
define $\Phi^{\sigma}(x)=\sigma$ for each $x\in J_{n}(d)$ with
$\Phi^{\sigma}(x)$ not already defined. Since we will seek to test at most
$\sum\\{h({\left\langle{2e+1,x,i}\right\rangle})\ :\ x\in I_{n}^{e}\ \&\
i<n\\}$ many strings on $J_{n}$, there are sufficient $d$ to give each
$\sigma$ a unique $d$.

Next, we must explain what it means to promote a length. Recall that this is
defined for each oracle $Y$, but we only care about it for oracle $B$. At a
stage $s$, let $\ell$ be the longest length which we have already decided
should be promoted by the $n$ module (or $\ell=0$ if there is no such length).
A string $\sigma$ which has been tested on $J_{n}$ is confirmed at $n$
(relative to $Y$) if $\sigma\in U_{x,s}^{Y}$ for each $x$ with
$\Phi^{\sigma}(x)=\sigma$. If there are distinct $\sigma_{0},\sigma_{1}$ of
the same length which are both confirmed at $n$ at stage $s$, and such that
$\sigma_{0}\\!\upharpoonright_{\ell}=\sigma_{1}\\!\upharpoonright_{\ell}$,
then $|\sigma_{0}|$ is to be promoted by the $n$ module. In particular, it
must be that $|\sigma_{0}|>\ell$.

This completes the description of the original construction.

We must argue that for each $n>e$, $B$ believes at most $n-1$ lengths should
be promoted by the $n$ module. Suppose not, and fix lengths
$0=\ell_{0}<\ell_{1}<\ell_{1}\dots<\ell_{n}$ such that for $i>0$, $B$ believes
$\ell_{i}$ is to be promoted by the $n$ module. For each $i>0$, fix strings
$\sigma_{0}^{i}$ and $\sigma_{1}^{i}$ on the basis of which $B$ decided to
promote $\ell_{i}$.

By construction, $B$ decides $\ell_{i}$ should be promoted before it decides
$\ell_{i+1}$ should be, and thus
$\sigma_{0}^{i+1}\\!\upharpoonright_{\ell_{i}}=\sigma_{1}^{i+1}\\!\upharpoonright_{\ell_{i}}$
for $i>0$. Clearly this also holds for $i=0$. Now define the following
sequence of sets:

  * •

$Z_{n}=\\{\sigma_{0}^{n},\sigma_{1}^{n}\\}$;

  * •

For $0<i<n$,

$Z_{i}=Z_{i+1}\cup(\\{\sigma_{0}^{i},\sigma_{1}^{i}\\}\setminus\\{\sigma\\!\upharpoonright_{\ell_{i}}:\sigma\in
Z_{i+1}\\}).$

Note that each $Z_{i}$ is an antichain, and
$\\{\sigma_{0}^{i},\sigma_{1}^{i}\\}\subseteq\\{\sigma\\!\upharpoonright_{\ell_{i}}:\sigma\in
Z_{i}\\}$ by construction. Let
$T=\\{\sigma\\!\upharpoonright_{\ell_{i}}:\sigma\in Z_{1}\ \&\ i\leq n\\}$,
which we think of as a tree. Note that the leaves of $T$ are precisely
$Z_{1}$.

For $i<n$, let
$v_{i}=\sigma_{0}^{i+1}\\!\upharpoonright_{\ell_{i}}=\sigma_{1}^{i+1}\\!\upharpoonright_{\ell_{i}}$.
Then the $v_{i}$ are pairwise distinct and each has at least 2 children in $T$
(namely, $\sigma_{0}^{i+1}$ and
$\sigma_{1}^{i+1}\\!\upharpoonright_{\ell_{i}}$). Thus $|Z_{1}|\geq n+1$.

Let $D$ be the set of axes chosen for various $\sigma\in Z_{1}$, and define
$\tau\in J_{n}$ by

$\tau(d)=\left\\{\begin{array}[]{cl}0&d\in D,\\\ 1&d\not\in
D.\end{array}\right.$

Observe that $\tau\in J_{n}(d)\iff d\in D$.

######  Claim 7.13.

For each $\sigma\in Z_{1}$, we make the definition
$\Phi^{\sigma}(\tau)=\sigma$.

###### Proof.

By construction, we will make this definition so long as we have not already
defined $\Phi^{\sigma}(\tau)$ to be something else. But our actions for any
string $\sigma^{\prime}\not\in Z_{1}$ will never do this, as such
$\sigma^{\prime}$ will have an axis $d\not\in D$, and so will not seek to make
a definition at $\tau$. And $\sigma^{\prime}\in Z_{1}\setminus\\{\sigma\\}$
will not do this, as they will only seek to make a definition for
$\Phi^{\sigma^{\prime}}(\tau)$, and $\sigma^{\prime}$ and $\sigma$ are
incomparable as $Z_{1}$ is an antichain. ∎

As each of the $\ell_{i}$ is promoted, we have $Z_{1}\subseteq U_{\tau}^{B}$,
contradicting $|U_{\tau}^{B}|\leq h(\tau)=n$.

Thus the construction can proceed. The remainder of the argument is relative
to $B$.

Fix $\widehat{\ell}$ the longest length which $B$ believes the $e+1$ module
should promote. Nonuniformly fix $A\\!\upharpoonright_{\widehat{\ell}}$. Let
$L(n,s)$ be the set of lengths being tested by the $n$ module at stage $s$. At
a stage $s$, define a partial sequence $\sigma_{n}^{s}$ for $e\leq n\leq s$
recursively:

  * •

$\sigma_{e}^{s}=A\\!\upharpoonright_{\widehat{\ell}}$;

  * •

Given $\sigma_{n}^{s}$, define $\sigma_{n+1}^{s}$ to be a string $\tau$
extending $\sigma_{n}^{s}$ with $|\tau|=\max L(n+1,s)$, and such that for each
$\ell\in L(n+1,s)$, $\tau\\!\upharpoonright_{\ell}$ is confirmed at $n+1$ by
stage $s$, if such a string $\tau$ exists.

######  Claim 7.14.

There is at most one possible choice for $\sigma_{n}^{s}$.

###### Proof.

For $n=e$, this is immediate.

For $n>e$, suppose there were two distinct strings $\tau_{0}$ and $\tau_{1}$
which are appropriate to pick for $\sigma_{n}^{s}$. Fix $\ell\in L(n,s)$ least
with $\tau_{0}\\!\upharpoonright_{\ell}\neq\tau_{1}\\!\upharpoonright_{\ell}$.
Then $\tau_{0}\\!\upharpoonright_{\ell},\tau_{1}\\!\upharpoonright_{\ell}$
witness the promotion of $\ell$ at stage $s$, and $\ell>|\sigma_{n-1}^{s}|$,
as $\tau_{0}$ and $\tau_{1}$ both extend $\sigma_{n-1}^{s}$. This contradicts
$|\sigma_{n-1}^{s}|=\max L(n-1,s)$ (or contradicts the definition of
$\widehat{\ell}$ if $n=e+1$). ∎

######  Claim 7.15.

Let $\ell_{n}=\max\bigcup_{s}L(n,s)$ for $n>e$, and $\ell_{e}=\widehat{\ell}$.
Then $A\\!\upharpoonright_{\ell_{n}}=\lim_{s}\sigma_{n}^{s}$ for $n\geq e$.

###### Proof.

Induction on $n$. The case $n=e$ is immediate.

For $n>e$, first observe that $\ell_{n-1}$ is either a length promoted by the
$n$ module (and so eventually an element of $L(n,s)$) or is $f(n-1,s)\leq
f(n,s)$ for some $s$, and so is bounded by an element of $L(n,s)$. Thus
$\ell_{n-1}\leq\ell_{n}$.

Now fix $s_{0}$ sufficiently large such that
$\sigma_{m}^{s}=A\\!\upharpoonright_{\ell_{m}}$ for all $m<n$ and $s\geq
s_{0}$, and such that $L(n,s_{0})=\bigcup_{s}L(n,s)$. As $\Phi^{A}$ is traced
by $(U_{x}^{B})_{x\in\omega}$, there is a stage $s_{1}\geq s_{0}$ such that
each $A\\!\upharpoonright_{\ell}$ for $\ell\in L(n,s_{0})$ is confirmed at
$n$. Then $A\\!\upharpoonright_{\ell_{n}}$ is a possible choice for
$\sigma_{n}^{s}$ for every $s\geq s_{1}$, and thus is $\sigma_{n}^{s}$. ∎

Define a sequence of stages $(s_{t})_{t\in\omega}$ as follows:

  * •

$t_{0}=e$.

  * •

Given $s_{t}$, $s_{t+1}$ is the least $s>s_{t}$ such that for every $n$ with
$e<n\leq t$, $\sigma_{n}^{s}$ exists.

Define $A_{t}=\sigma_{t}^{s_{t}}$.

######  Claim 7.16.

$(A_{t})_{t\in\omega}\models c$

###### Proof.

Suppose $e<n\leq t$ and $A_{t}(z)\neq A_{t}(z+1)$ for some $z$ with
$c(z,t)\geq 2^{-n}$. As $c(z,s_{t})\geq c(z,t)$, $z<f(n,s_{t})\in L(n,s_{t})$.
Thus $\sigma_{n}^{s_{t}}\neq\sigma_{n}^{s_{t+1}}$. Fix $m$ least with
$\sigma_{m}^{s_{t}}\neq\sigma_{m}^{s_{t+1}}$. Fix $\ell\in L(m,s_{t})$ least
with
$\sigma_{m}^{s_{t}}\\!\upharpoonright_{\ell}\neq\sigma_{m}^{s_{t+1}}\\!\upharpoonright_{\ell}$.
If no length less than $\ell$ and greater than $\max L(m-1,s_{t})$ is promoted
by the $m$ module at a stage $s\in(s_{t},s_{t+1}]$, then these witness the
promotion of $\ell$ at stage $s_{t+1}$, and $\ell>\max L(m-1,s_{t})$, as both
$\sigma_{m}^{s_{t}}$ and $\sigma_{m}^{s_{t+1}}$ extend
$\sigma_{m-1}^{s_{t}}=\sigma_{m-1}^{s_{t+1}}$. So whenever there is such a
$z,n$ and $t$, there is a promotion by an $m$ module for $m\leq n$ at a stage
after $s_{t}$.

There can be at most $\sum_{e<m\leq n}m-1<n^{2}$ such promotions over the
entire construction. Thus we can bound

$c((A_{t})_{t\in\omega})<\sum_{n}n^{2}\cdot 2^{-n}<\infty.\qed$

This ends the proof of Proposition 7.11. ∎

###  8\. Nies and Stephan: Update on the SMB theorem for measures

The purpose of this post is to provide an example showing that the boundedness
hypothesis in [39, Prop. 24] is necessary.

We briefly review some background and notation. Let $\mathbb{A}^{\infty}$
denote the topological space of one-sided infinite sequences of symbols in an
alphabet $\mathbb{A}$. Randomness notions etc. carry over from the case that
$\mathbb{A}=\\{0,1\\}$. A measure $\rho$ on $\mathbb{A}^{\infty}$ is called
_shift invariant_ if $\rho(G)=\rho(T^{-1}(G))$ for each open (and hence each
measurable) set $G$. The _empirical entropy_ of a measure $\rho$ along
$Z\in\mathbb{A}^{\infty}$ is given by the sequence of random variables

$h^{\rho}_{n}(Z)=-\frac{1}{n}\log_{|\mathbb{A}|}\rho[Z\\!\upharpoonright_{n}].$

A shift invariant measure $\rho$ on $\mathbb{A}^{\infty}$ is called _ergodic_
if every $\rho$ integrable function $f$ with $f\circ T=f$ is constant
$\rho$-almost surely. The following equivalent condition can be easier to
check: for any strings $u,v\in\mathbb{A}^{*}$,

$\lim_{N}\frac{1}{N}\sum_{k=0}^{n-1}\rho([u]\cap T^{-k}[v])=\rho[u]\rho[v].$

For ergodic $\rho$, the entropy $H(\rho)$ is defined as $\lim_{n}H_{n}(\rho)$,
where

$H_{n}(\rho)=-\frac{1}{n}\sum_{|w|=n}\rho[w]\log\rho[w].$

Thus, $H_{n}(\rho)=\mathbb{E}_{\rho}h^{\rho}_{n}$ is the expected value with
respect to $\rho$. Recall that by concavity of the logarithm function and
subadditivity of the entropy $H(X,Y)\leq H(X)+H(Y)$, the limit exists and
equals the infimum of the sequence. This limit is denoted $H(\rho)$, the
entropy of $\rho$.

######  Theorem 8.1 (SMB theorem, e.g. [45]).

Let $\rho$ be an ergodic measure on the space $\mathbb{A}^{\infty}$. For
$\rho$-almost every $Z$ we have $\lim_{n}h^{\rho}_{n}(Z)=H(\rho)$.

######  Proposition 8.2 ([39], Prop. 7.2).

Let $\rho$ be a computable ergodic measure on the space $\mathbb{A}^{\infty}$
such that for some constant $D$, each $h_{n}^{\rho}$ is bounded above by $D$.
Suppose the measure $\mu$ is Martin-Löf a.c. with respect to $\rho$. Then
$\lim_{n}E_{\mu}|h^{\rho}_{n}-H(\rho)|=0$.

We now given an example showing that the boundedness hypothesis on the
$h_{n}^{\rho}$ is necessary. In fact we provide a computable ergodic measure
$\rho$ such that some finite measure $\mu\ll\rho$ makes the sequence
$E_{\mu}h_{n}^{\rho}$ converge to $\infty$. This condition $\mu\ll\rho$ (every
$\rho$ null set is a $\mu$ null set) is stronger than requiring that $\mu$ is
Martin-Löf a.c. with respect to $\rho$.

######  Example 8.3.

There is an ergodic computable measure $\rho$ (associated to a binary renewal
process) and a computable measure $\mu\ll\rho$ such that
$\lim_{n}\mathbb{E}_{\mu}h^{\rho}_{n}=\infty$. (We can then normalise $\mu$ to
become a probability measure, and still have the same conclusion.)

###### Proof.

Let $k$ range over positive natural numbers. The real $c=\sum_{k}2^{-k^{4}}$
is computable. Let $p_{k}=2^{-k^{4}}/c$ so that $\sum p_{k}=1$. Let
$b=\sum_{k}k\cdot p_{k}$ which is also computable.

Let $\rho$ be the measure associated with the corresponding binary renewal
process, which is given by the conditions

$\rho[Z_{0}=1]=1/b$ and $\rho(10^{k}1\prec Z\mid Z_{0}=1)=p_{k}$.

Informally, the process has initial value $1$ with probability $1/b$, and
after each $1$ with probability $p_{k}$ it takes $k$ many 0s until it reaches
the next 1. See again e.g. [45, Ch. 1] where it is shown that $\rho$ is
ergodic. Write $v_{k}=10^{k}1$. Note that $\rho[v_{k}]=p_{k}/b$.

Define a function $f$ in $L_{1}(\rho)$ by $f(v_{k}\,\widehat{\
}\,Z)=k^{-2}/p_{k}$ and $f(X)=0$ for any $X$ not extending any $v_{k}$. It is