# Logic Blog 2022

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

  1. I Group theory and its connections to logic
    1. 1 Gardam’s refutation of the Higman/Kaplansky unit conjecture
    2. 2 Some undecidable properties of computable profinite, and discrete groups
    3. 3 Duality between locally Roelcke precompact groups and meet groupoids
    4. 4 Ferov: A paradigm for computation with symmetries of combinatorial structures, and visualisations thereof
  2. II Nies: Two talks on computably t.d.l.c. groups
    1. 5 Introduction
    2. 6 Computability on paths of rooted trees
    3. 7 Defining computably t.d.l.c. groups via Baire presentations
    4. 8 Defining computably t.d.l.c. groups via meet groupoids
    5. 9 Equivalence of the two types of computable presentations
    6. 10 Algorithmic properties of objects associated with a t.d.l.c. group
    7. 11 Closure properties of the class of computably t.d.l.c. groups
    8. 12 Uniqueness of computable presentation

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

  * •

fostering collaboration.

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

Logic Blog 2021 | (Link: http://arxiv.org/abs/2202.13643)
---|---
Logic Blog 2020 | (Link: http://arxiv.org/abs/2101.09508)
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\. Gardam’s refutation of the Higman/Kaplansky unit conjecture

######  Definition 1.1.

An element $u$ of a ring $R$ with $1$ is called a _unit_ if there exists $w\in
R$ such that $uw=wu=1$. The units of $R$ with the ring multiplication form a
group, which is denoted $R^{\times}$.

Note that if $R$ has no $0$-divisors, then it suffices to require that $uw=1$;
this implies that $u(wu-1)=0$ and hence $wu=1$.

Given a commutative ring $R$ with $1$ and a group $G$, recall that the group
ring $R[G]$ consists of the formal sums $w=\sum_{g\in S}r_{g}g$, where
$S\subseteq G$ is finite, and $r_{g}\in R-\\{0\\}$, with the obvious ring
operations. The empty formal sum denotes the $0$ of the group ring. The set
$S$ is called the support of $w$, and we write $S=\mathit{supp}(w)$. The ring
$R$ embeds into $R[G]$ via $0_{R}\mapsto 0$, $r\mapsto re$ for $r\neq 0$.
Clearly $G$ embeds into $R[G]^{\times}$ via $g\mapsto 1g$.

The unit conjecture stood for 81 years.

######  Conjecture 1.2 (Higman 1940/Kaplansky 1970).

Let $G$ be a torsion free group and $K$ a field. Then the group ring $K[G]$
has only trivial units, namely the ones of the form $kg$, where $k\in
K^{\times}$ and $g\in G$.

The unit conjecture goes back to Higman’s 1940 PhD thesis at the University of
Oxford. He noted that it holds for abelian groups, and proved it more
generally for locally indicable groups (groups such that each nontrivial f.g.
subgroup has a quotient isomorphic to ${\mathbb{Z}}$).

Kaplansky in his 1956 problem list on the occasion of a conference on linear
algebras held at Ram’s Head Inn on Shelter Island, Long Island, conjectured
that $K[G]$ has no zero divisors. In the revised 1970 version, he reviewed
progress on this problem [14, Problem 6], and also added Higman’s unit
conjecture in the discussion thereafter, crediting it to a problem list
written up after a 1968 conference in Kishinev, Moldavia.

The idempotent conjecture states that $K[G]$ has no idempotents other than
$0,1$. It was formulated in the late 1940’s for reduced group
$C^{*}$-algebras, but did not appear in print until sometime later.

####  1.1. Implications of properties of a torsion free group $G$

The property of a torsion free group that it satisfies the unit conjecture for
a field $K$ can be seen in the context of a hierarchy of properties. In the
following list, the first four properties don’t mention a field. Each property
implies the next; trivially (4) also implies (3).

  1. (1)

$G$ is _left orderable_

  2. (2)

$G$ is _diffus_ e (Bowditch [3]): if $C\subseteq G$ is a nonempty finite set,
then there is $c\in C$, called an extremal element, such that

for each $g\in G-\\{1\\}$, one has $gc\not\in C$ or $g^{-1}c\not\in C$.

  3. (3)

$G$ has the _unique product property_ (Kaplansky, Passman): if $A,B\subseteq
G$ are nonempty finite sets, then there is a pair $\langle a,b\rangle\in
A\times B$ that is the only pair in $A\times B$ yielding the product $ab$.

  4. (4)

$G$ has the _two unique products property_ : if in addition to the above, not
both $A$ and $B$ are singletons, then there exist _two_ such pairs.

  5. (5)

$K[G]$ has only the trivial units.

  6. (6)

$K[G]$ has no zero divisors.

  7. (7)

$K[G]$ has no idempotents other than $0,1$.

The implications can be seen as follows:

(1)$\to$(2): let $a=\max A$. If $ga<a$ then $a<g^{-1}a$.

(2)$\to$(3): Let $C=AB$. Let $c\in C$ be extremal. If $c=ab=rs$ where

$a,r\in A$ and $b,s\in B$ and $g=ra^{-1}\neq e$,

then $gab=rb\in C$ and also $g^{-1}ab=as\in C$.

(3)$\leftrightarrow$(4): Due to Strojnowski [37]. He also shows that e in the
definition of the unique product property one can assume that $A=B$. The proof
shows that if the property fails then $A$ can be made arbitrarily large.

(4)$\to$(5): Given two elements of $K[G]$ so that not both have support a
singleton, the two unique products mean that the support of the product also
is not a singleton.

(5)$\to$(6): Recall that a ring $R$ is called _prime_ if $u,v\in R-\\{0\\}$
implies that there is $r\in R$ such that $urv\neq 0$. Every zero divisors free
ring is prime because in that case one can choose $r=1$. It is known that
$K[G]$ is prime (it suffices to assume here that $G$ has no nontrivial finite
normal subgroup); see Passman [27, Th. 2.10].

Suppose that $ab=0$ in $K[G]$ where $a,b\neq 0$, and take $c$ such that
$\alpha:=bca\neq 0$. Then $\alpha^{2}=0$. We have
$(1+\alpha)(1-\alpha)=(1-\alpha)(1+\alpha)=1$, so $1-\alpha$ is a unit. If it
is trivial, then $1-\alpha=kg$, so $\alpha=1-kg\in K[\langle g\rangle]\cong
K[{\mathbb{Z}}]$ is a nonzero element with square 0 in the ring of univariate
Laurent polynomials over $K$, which is contradictory since that ring is a
domain.

(6)$\to$(7) Any nontrivial idempotent $x$ is a zero divisor because
$x(x-1)=0$.

The following nonimplications are known at present:

(2) $\not\to$(1) by a counterexample in the appendix to [31]. This is the
fundamental group of a certain closed orientable hyperbolic 3-manifold.

(6) $\not\to$(5) for the 2-element field, because $\mathbb{F}_{2}[P]$ is known
to be a domain, but has nontrivial units as discussed below. The same works
for other positive characteristics by the work of Alan Murray providing
nontrivial units in such characteristics, arxiv.org/abs/2106.02147.

####  1.2. Can one express these properties in first-order logic?

We consider the question which of the foregoing properties can be expressed by
a computable set $\\{\phi_{n}\colon n\in{\mathbb{N}}\\}$ of first-order
sentences in the language of groups. For the properties involving a field $K$,
we mean the assertion to hold for all fields.

(1) it remains to be settled whether this is expressible. This might well be
someone’s open question.

(2)-(4) are expressible, using one sentence for each size $n$ of a finite set,
respectively sizes of pairs of finite sets. To represent a finite subset $C$
of $G$ of size $n$ using f.o. logic, we use variables $x_{1},\ldots,x_{n}$ and
think of $C$ as being $\\{x_{1},\ldots,x_{n}\\}$. So (2) is expressed by the
collection of sentences

$\phi_{n}=\forall x_{1},\ldots,x_{n}\bigvee_{i\leq n}\forall
y[\bigwedge_{k}yx_{i}\neq x_{k}\lor\bigwedge_{k}y^{-1}x_{i}\neq x_{k}].$

They are easily turned into universal sentences.

For (5)-(7) note that each field is embeddable into an algebraically closed
fields. So to express the versions of (5)-(7) where the quantification is over
all fields, we might as well assume the fields are algebraically closed. We
can also fix a characteristic $d\in{\mathbb{N}}-\\{0\\}$, because then we can
throw the sentences for all $d$ together.

We do (6); (5) and (7) will be similar. For $r,s,\ell\in{\mathbb{N}}^{+}$ and
$\ell\leq rs$, an onto function

$T\colon\\{1,\ldots,r\\}\times\\{1,\ldots,s\\}\to\\{1,\ldots,\ell\\}$

is codes a partial multiplication table of a group $G$. The sentence in the
language of groups $\phi_{T}=\forall x_{1},\ldots,x_{r}\forall
y_{1},\ldots,y_{s}\forall z_{1},\ldots,z_{\ell}$

$\bigvee_{i<j\leq r}x_{i}=x_{j}\lor\bigvee_{i<j\leq
s}y_{i}=y_{j}\lor\bigvee_{i\leq r\land k\leq s}z_{T(i,k)}\neq x_{i}y_{k}$

says that this table cannot be realized by column of pairwise distinct
elements and row of pairwise distinct elements.

For each such $T$ we have a system of equalities and inequalities,

$E_{T}\equiv\bigvee_{i}\alpha_{i}\neq 0\,\land\,\bigvee_{k}\beta_{k}\neq
0\,\land\,\bigwedge_{u\leq\ell}[\sum_{T(i,k)=u}\alpha_{i}\beta_{k}=0],$

where $\alpha_{i},\beta_{k}$ range over a field $K$.

Given a finite function $T$, we put $\phi_{T}$ on the list of sentences
whenever this system has a solution in an algebraically closed field of
characteristic $d$. Then the whole list says that (6) holds for such a field.
Since $ACF_{d}$ is decidable uniformly in $d$ (and the sentences get longer as
the parameters for $T$ increase), the resulting set of all sentences is
computable.

Let $(\phi_{n})$ be the list for (3), and $(\psi_{m})$ be the list for (5). By
the compactness theorem, if (5) implies (3), then each sentence $\phi_{n}$ is
implied by a finite list $\psi_{r}$, $r\leq L(n)$ where $L$ is computable. So
to show that (5) does not imply (3), it would suffice to find an instance
(given by the size of a set $A$) of the unique product property (3) such that
no, however large, instance of the unit conjecture (5) implies it.

####  1.3. Torsion free groups without the unique product property

Rips and Segev [32] used small cancellation theory to provide the first
example of a torsion-free group $G$ that fails to have the unique product
property.

Define a torsion free group by

$P=\langle a,b\mid a^{-1}b^{2}a=b^{-2},b^{-1}a^{2}b=a^{-2}\rangle$.

This group $P$ was first proposed by Passman in connection with the Kaplansky
conjectures, and had appeared in various related investigations. Promislow
[30] showed that there is a 14-element subset $A$ of $P$ such that $P$ fails
to have the unique product property via $A,A$.

$P$ is known as the Passman 4-group, the Hantzsche-Wendt group and also the
Promislov group due to the authors of these papers. Note that $P$ is an
extension of a free abelian group of rank 3, $N=\langle
a^{2},b^{2},(ab)^{2}\rangle$ by the Klein 4 group $P/N=\langle Na,Nb\rangle$.
So $P$ is a crystallographic group; this means that the group is a cocompact
discrete subgroup of the topological group $O(n)\ltimes{\mathbb{R}}^{n}$, for
some $n$. The latter is the group of isometries of ${\mathbb{R}}^{n}$ with the
Euclidean norm.

Let $x=a^{2},y=b^{2}$. One can write $P$ as an amalgam

$\langle x,b\mid x^{b}=x^{-1}\rangle*_{U}\langle y,a\mid y^{a}=y^{-1}\rangle$

where $U=\langle x,b^{2}\rangle\cong\langle a^{2},y\rangle$. This shows that
$P$ is torsion free.

We note that the group can in fact be identified among the crystallographic
groups in dimension 3 as the unique torsion-free example with finite
abelianization. In dimension 2, the only torsion-free ones are free abelian
and Klein bottle group, both locally indicable. It follows that all the other
dimension 3 torsion-free space groups are locally indicable, and so satisfy
the conjecture.

Some more complex variants of $P$ also fail to have the unique product
property. Carter [6] defined for $k>0$ the torsion free group

$P_{k}=\langle a,b\mid
a^{-1}b^{2^{k}}a=b^{-{2^{k}}},b^{-1}a^{2}b=a^{-2}\rangle.$

Thus $P=P_{1}$. Generalising the case of $P_{1}$, each group $P_{k}$ is an
amalgam of two Klein 4 groups along a copy of ${\mathbb{Z}}^{2}$, letting
$y=b^{2^{k}}$. This implies that $P_{k}$ satisfies the 0-divisors conjecture
by a result of Lewin [21]. Carter shows that $P_{k}$ fails the unique product
property for each $k$, that the $P_{k}$ are pairwise non-isomorphic, and that
$P_{k}$ does not contain $P$ as a subgroup for $k>1$. Also each $P_{k}$ for
$k>1$ has a subgroup of finite index of the form ${\mathbb{Z}}^{2}\times F$
where $F$ is a free group of rank $>1$.

Craig and Linnell [7] conjecture that each uniform pro-p group satisfies the
unique product property. They also consider the obvious variants of $P$ with
more than 2 generators, and show that they are torsion free. However, such
variants embed $P$.

####  1.4. A counterexample to the unit conjecture

Gardam [10] published a counterexample to the unit conjecture for $P$ with the
field $\mathbb{F}_{2}$. Each element of $\mathbb{F}_{2}[P]$ has a unique
normal form

$p+qa+rb+sab,$

where the “coefficients” $p,q,r,s$ are in $\mathbb{F}_{2}[N]$, $N=\langle
x,y,z\rangle$.

Gardam’s example is given by $\alpha=p+qa+rb+sab$ where

$\displaystyle p$ $\displaystyle=(1+x)(1+y)(1+z^{-1})$ $\displaystyle q$
$\displaystyle=x^{-1}y^{-1}+x+y^{-1}z+z$ $\displaystyle r$
$\displaystyle=1+x+y^{-1}z+xyz$ $\displaystyle s$
$\displaystyle=1+(x+x^{-1}+y+y^{-1})z^{-1}.$

The inverse is given by
$\beta=p^{\prime}+q^{\prime}a+r^{\prime}b+s^{\prime}ab$ where

$p^{\prime}=x^{-1}p^{a},q^{\prime}=x^{-1}a,r^{\prime}=y^{-1}r,s^{\prime}=z^{-1}s^{a}$.

Murray (arxiv.org/abs/2106.02147, Thm. 3), provides counterexamples to the
unit conjecture for $P$ in any positive characteristic. For characteristic 0
it remains unknown whether the unit conjecture holds. Suppose there is a
finite set $S\subseteq P$ such that for infinitely many primes p, there is a
nontrivial unit in $F_{p}[P]$ with support of the unit and its inverse
contained in $S$. Let $K$ be an ultraproduct of these fields, which has
characteristic 0. Then $K[P]$ has a nontrivial unit with the same support $S$.
However for the examples of Murray, the size of the support depends on the
characteristic.

####  1.5. Conversion to a Boolean satisfiability problem

To find this, Gardam converted the problem into a satisfiability problem and
used a SAT solver to find a satisfying assignment, which yields the unit and
its inverse. If we fix a finite superset $S$ of the supports of $\beta$ and
$\alpha$, then for each word $w$ in $S$ we need only one bit, its coefficient
in $\mathbb{F}_{2}$, So we use variables $\ell_{w}$ and $k_{w}$ to say whether
the corresponding coefficients of $\beta$ and of $\alpha$, respectively, are
$0$ or $1$. We can write that $\alpha$ is nontrivial and that $\beta\alpha=1$
as a Boolean formula:

  * •

Nontriviality of $\alpha$ is expressed by saying that the disjunction of the
$k_{w}$ for $w\in S-\\{1\\}$ is true.

  * •

the parity of $\sum_{g,g^{-1}\in S}(\ell_{g^{-1}}\land k_{g})$ is $1$

  * •

For each $w\in S^{2}-\\{1\\}$ we have a condition that

the parity of $\sum_{h,g\in S\,\land\,hg=w}(\ell_{h}\land k_{g})$ is $0$.

Using standard methods this can be put into 3-conjunctive normal form. For the
given example, one takes $S$ as the ball of radius 5 in the Cayley graph of
$P$ (which has 147 elements). A SAT solver can find the answer in a reasonable
time (hours to days). See the 2021 lecture Giles Gardam: Solving semidecidable
problems in group theory.

####  1.6. The group of units is not finitely generated

Gardam shows that in a sense $\mathbb{F}_{2}[P]^{\times}$ is much larger than
$T$; it is not finitely generated, and contains non-abelian free subgroups.

Gardam [10, Lemma 1] provides a lemma with conditions that imply being a unit,
and these can be checked for the unit in question on about 2 pages. This more
general method allows to prove that the group of units is not finitely
generated. Gardam shows the existence of infinitely many non-trivial units
using this algebraic condition. However, the idea why it works is that the
group $P$ contains many isomorphic copies of itself. This appears to be
necessary for such a trick to work: the multiplication table of the unit and
its inverse determine the subgroup they generate up to isomorphism (in this
case). Also the group $P$ has a finite outer automorphism group [45], so one
cannot prove that the subgroup of the group of units generated by group-
automorphic images of the non-trivial unit is not finitely generated by
looking at the abelianization of the group of units. The result crucially
needs the computation of the group of units for the infinite dihedral group
$\langle a,b\mid b^{2}=1,a^{b}=a^{-1}\rangle$ (a quotient of $P$ via this
presentation) by Mirowicz.

####  1.7. Is the group of trivial units first-order definable in $K[G]$?

During discussions of Nies and Gardam in Münster, the question emerged whether
the group $T$ is first-order definable in the group of units of
$\mathbb{F}_{2}[P]$ (or, at least, in the ring $\mathbb{F}_{2}[P]$).

As is well-known, if $H<G$ are groups and $\alpha\in K[H]$ is a unit in $K[G]$
then it is a unit in $K[H]$ (and conversely). We use this below without
special mention.

If $T$ was definable in $\mathbb{F}_{2}[P]^{\times}$ without parameters, then
$T$ would be invariant under automorphisms of $\mathbb{F}_{2}[P]^{\times}$.
The following fact shows that under a quite general hypothesis on $G$, the
group $T$ is not even closed under conjugation by a nontrivial unit. Since any
automorphism of $G$ extends to an automorphism of $K[G]$, this shows that $T$
is also not definable in $K[G]$ when there are nontrivial units and the
hypothesis on $G$ is satisfied.

######  Proposition 1.3 (Gardam).

Let $K$ be a field. Let $G$ be a torsion free group with no infinite
nonabelian f.g. subgroup $V$ such that $V/Z(V)$ has finite exponent (for
instance, this holds if $G$ is solvable). Let $T=K^{\times}G$ denote the group
of trivial units in $K[G]$.

Then the group $T$ equals its own normaliser in the group of units of $K[G]$.

###### Proof.

Suppose for a contradiction that $u$ is a nontrivial unit in $K[G]$ such that
$T^{u}=T$. Let $S:=\mathit{supp}(u)$. Let $a\in S$; since $a^{-1}u$ is also a
nontrivial unit, we may suppose that $e\in S$. Let $n=|S|!$.

######  Claim 1.4.

Let $g\in G$. Then $g^{n}$ centralises the subgroup $V=\langle S\rangle$ of
$T$.

By hypothesis that $u$ normalises $T$, we have that $h:=ugu^{-1}\in T$. Via
the augmentation map (the ring homomorphism $K[G]\to K$ adding up the
coefficients), we see that $h\in G$. The map $x\mapsto h^{-1}xg$, $x\in K[G]$,
fixes $u$, and hence permutes its support $S$. So the map $x\mapsto
h^{-n}xg^{n}$ fixes $S$ pointwise. Since $e\in S$, $h^{n}=g^{n}$. So
$g^{-n}wg^{n}=w$ for each $w\in V$, as claimed. It follows that the f.g. group
$V/Z(V)$ has exponent $n$. If $V$ is abelian then the group ring $K[V]$ has
only trivial units because $V$ is orderable. So $V$ is nonabelian, contrary to
hypothesis on $G$.

If $G$ is solvable then $V/Z(V)$ is solvable; this implies it is finite (by an
easy induction on its solvability length, and using that $V$ is finitely
generated). By a result of Schur, this implies that $V^{\prime}$ is finite,
and hence trivial because $G$ is torsion-free. So again $V$ is abelian. ∎

######  Remark 1.5.

It is difficult to give examples of non-abelian f.g. groups which are torsion-
free and centre-by-finite exponent, which suggests that Proposition 1.3 holds
for lots of groups. Adjan [1] provided the first example, where the centre is
cyclic (and the quotient by the centre is a free Burnside group).

We next show that the group $K^{\times}P$ of trivial units is parameter
definable in $K[P]^{\times}$, for any field $K$. As before, we use the
notation from Gardam [10]. In particular $a,b$ are generators of $P$, and
$x=a^{2},y=b^{2},z=(ab)^{2}$ are generators of the group
$N\cong{\mathbb{Z}}^{3}$ that has index $4$ in $P$. We use $a,b$ as
parameters. The defining formula is a disjunction of conjunctions of
equations.

######  Proposition 1.6 (Gardam).

Let $u\in K[P]^{\times}$. Then $u\in K^{\times}P$ $\Leftrightarrow$

gy at least one of $u,ua,ub$, $uab$ commutes with $a^{2}$, $b^{2}$, and
$(ab)^{2}$.

###### Proof.

$\Rightarrow:$ Recall that $P/N$ is the Klein 4 group generated by $aN$ and
$bN$. So for each $u\in P$, one of $u,ua,ub,uab$ is in $N$.

$\Leftarrow:$ We may assume w.l.o.g. that it is $u$ that commutes with
$a^{2}$, $b^{2}$ and $(ab)^{2}$. Write it in the “normal form”

$u=p+qa+rb+sab$

where $p,q,r,s\in K[{\mathbb{Z}}^{3}]$. Using that $ba^{2}=a^{-2}b$, one has

$\displaystyle a^{2}u$ $\displaystyle=$ $\displaystyle
pa^{2}+qa^{2}a+ra^{2}b+sa^{2}ab$ $\displaystyle ua^{2}$ $\displaystyle=$
$\displaystyle pa^{2}+qa^{2}a+ra^{-2}b+sa^{-2}ab.$

Since $u$ commutes with $a^{2}$, all the coefficients are equal. So
$r(a^{2}-a^{-2})=0$ and similar for $s$. This implies $r=s=0$ since
$K[{\mathbb{Z}}^{3}]$ is an integral domain. Similarly, since $u$ commutes
with $b^{2}$ we have $q=0$. Since the units in $K[{\mathbb{Z}}^{3}]$ are
trivial, this implies that $u\in K^{\times}P$. ∎

####  1.8. A verification of Gardam’s counterexample in GAP

Gardam verified his counterexample in the computer algebra system GAP, and
this was attached as an ancillary file to the first version on the arXiv of
[10]. There is also a formalized proof by Siddhartha Gadgil and Anand Rao
Tadipatri in the proof assistant system “lean”.

The following GAP interaction was provided by Bettina Eick in Oct. 2022.
Comments added by Andre Nies.

First we find the group $P$ in the catalog. It is a polycyclic group; such
groups are given by polycyclic presentations (pcp).

    Ψgap> gg := List([1..219], x -> SpaceGroupPcpGroup(3,x));;
    Ψgap> gg := Filtered(gg, IsTorsionFree);
    Ψ[ Pcp-group with orders [ 0, 0, 0 ], Pcp-group with orders [ 2, 0, 0, 0 ],
    ΨPcp-group with orders [ 2, 0, 0, 0 ], Pcp-group with orders [ 2, 0, 0, 0 ],
    ΨPcp-group with orders [ 2, 2, 0, 0, 0 ],
    ΨPcp-group with orders [ 2, 2, 0, 0, 0 ],
    ΨPcp-group with orders [ 2, 2, 0, 0, 0 ],
    ΨPcp-group with orders [ 2, 2, 0, 0, 0 ],
    ΨPcp-group with orders [ 3, 0, 0, 0 ],
    ΨPcp-group with orders [ 3, 2, 0, 0, 0 ] ]
    Ψgap> gg := Filtered(gg, x -> IdGroup(x/FittingSubgroup(x))=[4,2]);
    Ψ%code for Klein 4 group
    Ψ[ Pcp-group with orders [ 2, 2, 0, 0, 0 ],
    ΨPcp-group with orders [ 2, 2, 0, 0, 0 ],
    ΨPcp-group with orders [ 2, 2, 0, 0, 0 ] ]
    Ψgap> List(gg, AbelianInvariants);
    Ψ[ [ 4, 4 ], [ 0, 2, 2 ], [ 0, 4 ] ]. %C_4 x C_4,
    Ψgap> P := gg[1];
    ΨPcp-group with orders [ 2, 2, 0, 0, 0 ]

Now we build the group ring $R$.

    Ψgap> R := GroupRing(GF(2), P);
    Ψ<algebra-with-one over GF(2), with 10 generators>. %
    Ψgap> GeneratorsOfRing(R);
    Ψ[ (Z(2)^0)*id, (Z(2)^0)*g1*g5, (Z(2)^0)*g1, (Z(2)^0)*g2*g4, (Z(2)^0)*g2,    (Z(2)^0)*g3, (Z(2)^0)*g4, (Z(2)^0)*g5, (Z(2)^0)*g5^-1, (Z(2)^0)*g4^-1,
    Ψ(Z(2)^0)*g3^-1, (Z(2)^0)*id ]
    Ψ% Z(2)^0 is the 1 of the ring
    Ψ
    Ψgap> P;
    ΨPcp-group with orders [ 2, 2, 0, 0, 0 ]
    Ψgap> g := Igs(P);   %induced  generating system
    Ψ[ g1, g2, g3, g4, g5 ]
    Ψgap> a := g[1];
    Ψg1
    Ψgap> b := g[2];
    Ψg2
    Ψgap> a^2;
    Ψg5^-1
    Ψgap> b^2;
    Ψg4^-1
    Ψgap> (a*b)^2;
    Ψg3^-1
    Ψ

Next identify group elements $a,b,x,y,z$ with their images in $R$, where
$x=a^{2},y=b^{2},z=(ab)^{2}$, and hence the normal abelian subgroup $N$ of $P$
is freely generated by $x,y,z$. Note that

     (Z(2)^0)

is the internal notation for the multiplicative identity of $\mathbb{F}_{2}$.

    Ψ
    Ψgap> a := a*One(R);
    Ψ(Z(2)^0)*g1
    Ψgap> b := b*One(R);
    Ψ(Z(2)^0)*g2
    Ψgap> x := a^2;
    Ψ(Z(2)^0)*g5^-1
    Ψgap> y := b^2;
    Ψ(Z(2)^0)*g4^-1
    Ψgap> z := (a*b)^2;
    Ψ(Z(2)^0)*g3^-1
    Ψ

One writes the unit $w$ in this normal form by declaring these coefficients.

    Ψgap> p := (One(R)+x)*(One(R)+y)*(One(R)+z^-1);
    Ψ(Z(2)^0)*g3+(Z(2)^0)*g3*g5^-1+(Z(2)^0)*g3*g4^-1+(Z(2)^0)*g3*g4^-1*g5^-1+(Z(2)^
    Ψ0)*id+(Z(2)^0)*g5^-1+(Z(2)^0)*g4^-1+(Z(2)^0)*g4^-1*g5^-1
    Ψgap> q := x^-1*y^-1+ x+ y^-1*z + z;
    Ψ(Z(2)^0)*g4*g5+(Z(2)^0)*g5^-1+(Z(2)^0)*g3^-1*g4+(Z(2)^0)*g3^-1
    Ψgap> r := One(R) + x + y^-1*z+ x*y*z;
    Ψ(Z(2)^0)*id+(Z(2)^0)*g5^-1+(Z(2)^0)*g3^-1*g4+(Z(2)^0)*g3^-1*g4^-1*g5^-1
    Ψgap> s := One(R) + (x+x^-1+y+y^-1)*z^-1;
    Ψ(Z(2)^0)*g3*g4+(Z(2)^0)*g3*g5+(Z(2)^0)*g3*g5^-1+(Z(2)^0)*g3*g4^-1+(Z(2)^0)*id
    Ψgap> w := p + q*a + r*b + s*a*b;
    Ψ(Z(2)^0)*g1*g2*g3*g4+(Z(2)^0)*g1*g2*g3*g5+(Z(2)^0)*g1*g2*g3*g5^-1+(Z(2)^
    Ψ0)*g1*g2*g3*g4^-1+(Z(2)^0)*g1*g2+(Z(2)^0)*g1*g3+(Z(2)^0)*g1*g3*g4^-1+(Z(2)^
    Ψ0)*g1*g5^-1+(Z(2)^0)*g1*g4^-1*g5+(Z(2)^0)*g2*g3*g4+(Z(2)^0)*g2*g3*g4^-1*g5+(
    ΨZ(2)^0)*g2*g5+(Z(2)^0)*g2+(Z(2)^0)*g3+(Z(2)^0)*g3*g5^-1+(Z(2)^0)*g3*g4^-1+(
    ΨZ(2)^0)*g3*g4^-1*g5^-1+(Z(2)^0)*id+(Z(2)^0)*g5^-1+(Z(2)^0)*g4^-1+(Z(2)^0)*g4^
    Ψ-1*g5^-1

The expression for the inverse $v$ of $w$, given below, is closely related to
the expression for $w$. We merely need to modify the coefficients. For
instance, the effect of conjugating $p$ by $a$ is flipping the signs of the
exponents of $y$ and $z$.

    Ψgap> v := x^-1 * a^-1*p*a + x^-1*q*a + y^-1*r*b+ z^-1*a^-1*s*a*a*b;
    Ψ(Z(2)^0)*g1*g2*g3+(Z(2)^0)*g1*g2*g4+(Z(2)^0)*g1*g2*g5+(Z(2)^0)*g1*g2*g5^-1+(
    ΨZ(2)^0)*g1*g2*g4^-1+(Z(2)^0)*g1*g3*g5+(Z(2)^0)*g1*g3*g4^-1*g5+(Z(2)^0)*g1+(
    ΨZ(2)^0)*g1*g4^-1*g5^2+(Z(2)^0)*g2*g3*g4^2+(Z(2)^0)*g2*g3*g5+(Z(2)^
    Ψ0)*g2*g4*g5+(Z(2)^0)*g2*g4+(Z(2)^0)*g4*g5+(Z(2)^0)*g4+(Z(2)^0)*g5+(Z(2)^
    Ψ0)*id+(Z(2)^0)*g3^-1*g4*g5+(Z(2)^0)*g3^-1*g4+(Z(2)^0)*g3^-1*g5+(Z(2)^0)*g3^-1

Finally, we are ready to try it out:

    Ψgap> w*v;
    Ψ(Z(2)^0)*id

This says that $wv=1$, and so GAP has verified Gardam’s result refuting the
82-year old conjecture of Higman.

###  2\. Some undecidable properties of computable profinite, and discrete
groups

We show, without any claim of originality, that basic properties of computable
abelian groups are undecidable, both in the profinite and in the discrete
setting. For profinite groups, being pro-$p$ is not decidable, and being
topologically generated by one element is also not decidable. (In fact, this
is already shown by finite groups.)

For infinite discrete groups, being finite is not decidable.

We begin by reviewing the relevant definitions. The following originates in
work of Mal’cev and Rabin (ind.) from the 1960s.

######  Definition 2.1.

A _computable structure_ is a structure such that the domain is a computable
set $D\subseteq{\mathbb{N}}$, and the functions and relations of the structure
are computable.

######  Example 2.2.

(a) For each $k\geq 1$, the group $GL_{k}(\mathbb{Q})$ is computably
presentable. To obtain a computable copy, one fixes an algorithmic encoding of
the rational $k\times k$ matrices by natural numbers, and lets the domain $D$
be the computable set of numbers that encode a matrix with nonzero
determinant. Since the encoding is algorithmic, the domain and the matrix
operations are computable.

(b) It is not hard to verify that an $n$-generated group $G$ has a computable
copy $\Leftrightarrow$ if its word problem is decidable. For the implication
“$\Leftarrow$”, assume some effective bijection
$F_{n}\leftrightarrow{\mathbb{N}}$. Suppose $G=F_{n}/N$ for a computable
normal subgroup $N$. Write $\sim_{N}$ for $uw^{-1}\in N$, and note that
$\sim_{N}$ is a computable equivalence relation. Let $D$ be the set of least
elements in the $\sim_{N}$-classes, which is a computable set. To show the
binary group operation is computable on $D$, given $r,s\in D$, we let $f(r,s)$
be the element $t$ of $D$ such that $rs\sim_{N}t$. Similarly for the inverse.

######  Definition 2.3 (Smith [36] and la Roche [19]).

A profinite group $G$ is computable if $G=\varprojlim_{t}(A_{t},\psi_{t})$ for
a computable diagram $(A_{t},\psi_{t})_{t\in{\mathbb{N}}}$ of finite groups
and epimorphisms $\psi_{t}\colon A_{t}\to A_{t-1}$ ($t>0$).

Let $C_{r}$ denote the cyclic group of size $r$.

######  Proposition 2.4.

For profinite groups,

  * (i)

being pro-$p$ is not decidable

  * (ii)

being topologically generated by one element is not decidable.

###### Proof.

For each $n$ we build a group $G_{n}$ which has the property if $n$ is not in
the halting problem $K$. We have $K=\bigcup_{t}K_{t}$ where $K_{t}$ is the set
of elements enumerated by the end of stage $t$ (we may assume that
$K_{1}=\emptyset$).

Fix $n$. We build a diagram of finite groups $(A_{t})_{t\in{\mathbb{N}}}$ with
natural maps $\phi_{k}\colon A_{t+1}\to A_{t}$ and let $G_{n}$ be the inverse
limit.

(i) Fix a prime $q\neq p$. Let $A_{0}=C_{p}$. If $n\not\in K_{t+1}$ let
$A_{t+1}=A_{t}$ and $\phi_{t}$ the identity. If $n\in K_{t+1}-K_{t}$ let
$A_{t}=C_{pq}$ and $\phi_{t}$ the natural map $C_{pq}\to C_{p}$. If $n\in
K_{t}$ let $A_{t+1}=A_{t}$ and $\phi_{t}$ the identity.

(ii) This is similar, replacing $C_{pq}$ by $C_{p}\times C_{p}$. Also, if
$n\in K_{t+1}-K_{t}$, let $\phi_{t}$ be the addition map on $C_{p}$,
otherwise, take the identity maps as before. ∎

######  Proposition 2.5.

For infinite discrete groups, being finite is not decidable.

###### Proof.

We build a computable presentation of $G_{n}$, for convenience on a computable
set $D\subseteq{\mathbb{Z}}$ (which is an interval of the form $[-n,n]$, or
all of ${\mathbb{Z}}$).

To build $D$, at each stage $t$ we decide whether $t$ and $-t$ are elements.
Similar for the computable operations on elements that have been decided to be
in $D$.

If $n\not\in K_{t+1}$ declare that $-t$ and $t$ are in $D$. Declare addition
and inverse of elements $a,b\in D$ such that $|a|,|b|\leq t/2$ if not already
declared, according to addition on ${\mathbb{Z}}$.

If $n\in K_{t+1}$ then declare that $-t$ and $t$ are not in $D$. If $t$ is
least such, also declare addition of the remaining elements in $D$ so as to
making a computable copy of $C_{2t-1}$ on the final $D=\\{-t+1,\ldots,t-1\\}$.

∎

###  3\. Duality between locally Roelcke precompact groups and meet groupoids

André gave two seminar talks at the Department of Mathematics at the
University of Münster in May/June. They were centred on using countable
“approximation structures” to describe certain uncountable totally
disconnected topological groups. The following notes form a polished version
of the material in the first of these two talks.

All topological groups will be countably based, and all isomorphisms between
them will be topological. One says that a topological group $G$ is _non-
Archimedean_ if the neutral element has a neighbourhood basis consisting of
open subgroups. It is well known [2, Th. 1.5.1] that this property is
equivalent to being isomorphic to a closed subgroup of $S_{\infty}$ (the group
of permutations of ${\mathbb{N}}$), which means the automorphism group of a
structure with domain ${\mathbb{N}}$.

The first talk was on oligomorphic groups, the second on locally compact
groups. In the former, the approximation structures are used to derive an
upper bound on the Borel complexity of the isomorphism relation. The second
uses the approximation structure to study what it means for a t.d.l.c. group
to be computable. This is recorded as an extended version Part II below, based
on a talk series at a Newcastle conference in October.

The following setting has been discussed in detail in Kechris et al. [17]. The
closed subset of a Polish space $X$ form a standard Borel space, called the
Effros space. If $X$ underlies a Polish group, the closed subgroups form a
Borel set in the Effros space (see e.g. [17, Lemma 2.5] for detail). One can
gauge the complexity of the isomorphism relation on subclasses of the closed
subgroups of $S_{\infty}$ via the usual Borel reducibility $\leq_{B}$. The
following classes have been (at least to some degree) studied under this
aspect.

######  Definition 3.1.

A closed subgroup $G$ of $S_{\infty}$ is called

  1. (1)

oligomorphic: for each $n$ only finitely many $n$-orbits

  2. (2)

quasi-oligomorphic: isomorphic to an oligomorphic group (but the canonical
evaluation action on ${\mathbb{N}}$ may fail to be oligomorphic)

  3. (3)

Roelcke pre-compact (R.p): for each open subgroup $U$, there is a finite
subset $\alpha$ such that $G=U\alpha U$; that is, $U$ has finitely many double
cosets

  4. (4)

locally compact (t.d.l.c.): the usual definition for the underlying topology;
equivalently, there is a compact open subgroup (van Dantzig’s theorem)

  5. (5)

locally R.p: there is a R.p. open subgroup.

For background on (locally) Roelcke precompact groups see Rosendal [34] and
also Zielinski [44]. This set of concepts works in fact in a setting much more
general than closed subgroups of $S_{\infty}$. The Roelcke uniformity in a
topological group $G$ is given by the basic entourages $\\{\langle
g,h\rangle\colon g\in VhV\\}$ where $V$ ranges over identity neighbourhoods. A
subset $A$ of a Polish group $G$ is Roelcke precompact if it is totally
bounded in the Roelcke uniformity. That is, for each entourage $V$ there is a
finite set $F$ such that $A\subseteq\bigcup_{x\in F}B_{V}(x)$. And of course
$G$ is locally R.p. if it has a R.p. nbhd of the identity. Even for non-
Archimedean groups, our definition of locally R.p. might be a bit more
restricted than the one given by Rosendal and Zielinski. The two are
equivalent if there is a version, in the more general locally Roelcke
precompact setting, of van Dantzig’s theorem for t.d.l.c. groups. To my
knowledge no-one has obtained this so far.

locally Roelcke precompactRoelcke precompactlocally compactquasi-
oligomorphiccompactdiscreteoligomorphic
Figure 1. Some classes of closed subgroups of $S_{\infty}$, with their
inclusion relations.

Since all classes are Borel, each inclusion in the diagram implies Borel
reducibility between the isomorphism relations. Even for the locally R.p.
case, an upper bound on the complexity of the isomorphism relation is graph
isomorphism GI. This is shown by suitably extending [17, Thm. 3.1]. The idea
is that $G$ acts faithfully from the left on a countable set of open cosets.
For [quasi]-oligomorphic $G$, just take all open cosets; in general, take the
R.p. open cosets.

For all classes $\mathcal{C}$ except [quasi-]oligomorphic, this bound is sharp
by a profinite version ([17], last section) of the Mekler construction, which
codes certain “nice” countable graphs into countable nilpotent-2 groups of
exponent $p$. For [quasi-]oligomorphic, there is a tighter upper bound: the
isomorphism relation is Borel reducible to a Borel equivalence relation with
all classes countable (that is, below the orbit equivalence relation given by
a Borel action of a countable group).

####  3.1. Meet groupoids of locally R.p. groups

Intuitively, the notion of a groupoid generalizes the notion of a group by
allowing that the binary operation is partial. A groupoid is given by a domain
$\mathcal{W}$ on which a unary operation $(.)^{-1}$ and a partial binary
operation, denoted by “$\cdot$”, are defined. These operations satisfy the
following conditions:

  * (a)

associativity $(A\cdot B)\cdot C=A\cdot(B\cdot C)$, with either both sides or
no side defined (and so the parentheses can be omitted in products);

  * (b)

$A\cdot A^{-1}$ and $A^{-1}\cdot A$ are always defined;

  * (c)

if $A\cdot B$ is defined then $A\cdot B\cdot B^{-1}=A$ and $A^{-1}\cdot A\cdot
B=B$.

It follows from (c) that a groupoid satisfies the left and right cancellation
laws. One says that an element $U\in\mathcal{W}$ is _idempotent_ if $U\cdot
U=U$. Clearly this implies that $U=U\cdot U^{-1}=U^{-1}\cdot U$ and so
$U=U^{-1}$ by cancellation. Conversely, by (c) every element of the form
$A\cdot A^{-1}$ or $A^{-1}\cdot A$ is idempotent.

Note that if $A=Ua=aV$ and $B=Vb=bW$ for R.p. open subgroups $U,V,W$ then
$AB=Uab=abW$. Recall that a groupoid is equivalent to a category where each
morphism has an inverse. In category notation, we write this now as

$U\stackrel{{\scriptstyle A}}{{\to}}V\stackrel{{\scriptstyle B}}{{\to}}W$
implies $U\stackrel{{\scriptstyle AB}}{{\to}}W$.

Furthermore, if $C,D$ are left cosets of $U,V$, respectively, and $C\cap
D\neq\emptyset$, then pick $a\in C\cap D$. We have $C\cap D=a(U\cap V)$. This
motivates the next definition.

######  Definition 3.2.

A _meet groupoid_ is a groupoid $(\mathcal{W},\cdot,{(.)}^{-1})$ that is also
a meet semilattice $(\mathcal{W},\cap,\emptyset)$ of which $\emptyset$ is the
least element. It satisfies the conditions that
$\emptyset^{-1}=\emptyset=\emptyset\cdot\emptyset$, that $\emptyset\cdot A$
and $A\cdot\emptyset$ are undefined for each $A\neq\emptyset$, that $U\cap
V\neq\emptyset$ for idempotents $U,V$ such that $U,V\neq\emptyset$, and that
the groupoid operations are monotonic: writing $A\subseteq B\Leftrightarrow
A\cap B=A$,

  * (d)

$A\subseteq B\Leftrightarrow A^{-1}\subseteq B^{-1}$, and

  * (e)

if $A_{i}\cdot B_{i}$ are defined ($i=0,1$) and $A_{0}\cap
A_{1}\neq\emptyset\neq B_{0}\cap B_{1}$, then

$(A_{0}\cap A_{1})\cdot(B_{0}\cap B_{1})=A_{0}\cdot B_{0}\cap A_{1}\cdot
B_{1}$

Monotonicity of $\cdot$ follows from (e): if $A_{i}\cdot B_{i}$ are defined
($i=0,1$) and $A_{0}\subseteq A_{1},B_{0}\subseteq B_{1}$, then $A_{0}\cdot
B_{0}\subseteq A_{1}\cdot B_{1}$.

Note that (e) holds for the R.p. open cosets of a group: Let $A_{i}$ be a
right coset of a subgroup $U_{i}$ and a left coset of subgroup $V_{i}$, so
that $B_{i}$ is a right coset of $V_{i}$ by hypothesis. Then as noted above,
$A_{0}\cap A_{1}$ is a right coset of $U_{0}\cap U_{1}$, and $B_{0}\cap B_{1}$
a right coset of $V_{0}\cap V_{1}$, so the left hand side is defined. Clearly
the left side is contained in the right hand side by monotonicity. The right
hand side is also a right coset of $U_{0}\cap U_{1}$, so they must be equal.

######  Fact 3.3.

If $U$ and $V$ are idempotent, then so is $S:=U\cap V$.

###### Proof.

Just let $U=A_{0}=B_{0}$ and $V=A_{1}=B_{1}$ in (e). In fact this also follows
without (e). Since inversion is an order isomorphism, we have $S=S^{-1}$. In
particular, $S\cdot S$ is defined. Since $S\subseteq U,V$, we have $S\cdot
S\subseteq U\cdot U\cap V\cdot V$ by monotonicity of $\cdot$, and hence
$S\cdot S\subseteq S$. This implies $S\cdot S\cdot S^{-1}\subseteq S\cdot
S^{-1}$ and hence $S\subseteq S\cdot S$. ∎

Given meet groupoids $\mathcal{W}_{0},\mathcal{W}_{1}$, a bijection
$h\colon\mathcal{W}_{0}\to\mathcal{W}_{1}$ is an _isomorphism_ if it preserves
the three operations. Given a meet groupoid $\mathcal{W}$, the letters $A,B,C$
will range over elements of $\mathcal{W}$, and the letters $U,V,W$ will range
over idempotents.

######  Definition 3.4.

Let $G\leq_{c}S_{\infty}$ be locally Roelcke precompact (in the sense that
there is an open Roelcke precompact subgroup). Define a meet groupoid
$\mathcal{W}(G)$ as follows. The domain consists of all R.p. open cosets of
$G$, together with $\emptyset$. The inverse $A\to A^{-1}$ is as usual. For
$A,B\in\mathcal{W}(G)$, let $A\cdot B$ be the usual product in case that $A$
is a left coset of some subgroup $V$, and $B$ is a right coset of $V$ (so that
$AB$ is indeed a R.p. open coset). The operation $\cap$ is the usual
intersection operation.

######  Remark 3.5.

Using the somewhat exotic notion of locally R.p. groups is necessary to define
a common framework for the less exotic classes in Figure 1. For
[quasi]-oligomorphic groups, every open coset is R.p., so one can ignore this
restriction to R.p. For t.d.l.c. groups $G$, R.p. open cosets coincide with
the open compact ones. So $\mathcal{W}(G)$ is simply the meet groupoid on
compact open cosets.

####  3.2. Borel duality

Recall that all classes $\mathcal{C}$ in the diagram are Borel. Using an old
result of Lusin-Novikov one can ensure the meet groupoid has domain
${\mathbb{N}}$ as described in the proof of [17, Thm. 3.1], and then view
$\mathcal{W}$ as a Borel operator from $\mathcal{C}$ to a suitable set of
structures with domain ${\mathbb{N}}$. For all the classes except
oligomorphic, the following map $\mathcal{G}$ is an inverse of $\mathcal{W}$
up to isomorphism. Given a meet groupoid $M$ with domain ${\mathbb{N}}$, let

$\mathcal{G}(M)=\\{p\in S_{\infty}\colon\,p\text{ preserves inclusion }\land$

$p(A\cdot B)=p(A)\cdot B\text{ whenever }A\cdot B\text{ is defined }\\}$.

So we have the duality

a Borel class of groups
$\textstyle{{\mathcal{C}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathcal{W}}$$\textstyle{{\mathcal{D}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathcal{G}}$
a Borel class of meet groupoids on ${\mathbb{N}}$.

Duality means that for each $G\in\mathcal{C}$ and $M\in\mathcal{D}$

$\mathcal{G}(\mathcal{W}(G))\cong G$ and $\mathcal{W}(\mathcal{G}(M))\cong M$.

$\mathcal{D}$ is the closure under isomorphism of the range of
$\mathcal{W}\\!\upharpoonright_{\mathcal{C}}$, which can be shown to be Borel.
This is the domain of $\mathcal{G}$ which is also a Borel map.

To show that $\mathcal{G}(\mathcal{W}(G))\cong G$ for each $G\in\mathcal{C}$
is not hard; essentially this is done already in [17]. That the closure
$\mathcal{D}$ of the range of $\mathcal{W}$ is Borel, and showing the dual
condition $\mathcal{W}(\mathcal{G}(M))\cong M$, is much harder. Given a class
$\mathcal{C}$, for membership of $M$ in $\mathcal{D}$ we need an extra Borel
condition on $M$ that ensures $\mathcal{W}(\mathcal{G}(M))\cong M$. The
problem is that there may be an open subgroup $\mathcal{U}$ in
$\mathcal{G}(M)$ that isn’t “named” by an element of $M$. That is,
$\mathcal{U}$ is not of the form $\\{p\colon\,p(U)=U\\}$ for any $U\in M$. For
an idempotent $U\in M$, let $L(U)=\\{A\in M\colon AU=A\\}$ be the set of left
“cosets”. Similar define $R(U)$, the right cosets. For the compact setting,
say, one requires that $L(U)$ is always finite, and, if $L(U)=R(U)$ (i.e. $U$
is “normal”) and a set $\mathcal{B}\subseteq L(U)$ is closed under the
groupoid operations, then there is an idempotent $W\in M$ such that
$A\in\mathcal{B}\leftrightarrow A\subseteq W$ for each $A\in L(U)$. This is
axiom CC in [8, Section 4]. Similar conditions appear to determine the right
$\mathcal{D}$ for the other classes; see the axiom CLC for t.d.l.c. groups in
[8, Section 4], and [26] for oligomorphic groups; note that for locally R.p.
groups this hasn’t really been carried out in any detail.

####  3.3. Borel complexity of the isomorphism relation in the oligomorphic
case

Now let $\mathcal{C}$ be the class of oligomorphic groups. One can’t use the
map $\mathcal{G}$ as above because the group $\mathcal{G}(M)$ is not
necessarily oligomorphic even if $M=\mathcal{W}(G)$ for an oligomorphic group
$G$. Instead, we define a Borel map $\widetilde{\mathcal{G}}$ which doesn’t
suffer from this flaw. One has to work harder, by only considering the action
on one set $L(V)$ for a particularly nice idempotent $V$; for the detail see
[26], which however works in the setting of “coarse groups” which are
countable structures with only ternary relation, and the map $\mathcal{G}$
yields groups with domain the set of certain filters on these coarse groups.
(We speculate that if that work was recast in the more recent setting of meet
groupoids, it would shed at least 5 pages.) $V$ is given as follows.

######  Lemma 3.6.

Each oligomorphic group $G$ has an open subgroup $V$ such that the natural
left action $G\curvearrowright L(V)$ is oligomorphic and faithful. Thus we get
an homeomorphic embedding of $G$ into the symmetric group on $L(V)$.

###### Sketch of proof.

Let $n_{1},\ldots,n_{k}$ represent the 1-orbits. Let $V$ be the pointwise
stabiliser of $\\{n_{1},\ldots,n_{k}\\}$. ∎

For membership of a meet groupoid $M$ in $\mathcal{D}$, one condition (axiom)
requires the existence of such a $V$. Given $M$ one can pick such a $V$ in a
Borel way. Let $\widetilde{\mathcal{G}}(M)$ be the closed subgroup of
$S_{\infty}$ given by the action on $L(V)$.

We now discuss how to obtain the upper bound on the Borel complexity of
$\cong_{\mathcal{C}}$, the isomorphism relation on $\mathcal{C}$. An
equivalence relation $E$ on a Borel space $X$ is called _essentially
countable_ if $E\leq_{B}F$ for some Borel eqrel $F$ with all classes countable
(for example, isomorphism on f.g. groups).

######  Theorem 3.7 ([26]).

The isomorphism relation between oligomorphic groups is essentially countable.

###### Proof.

By the above $\cong_{\mathcal{C}}$ is $\equiv_{B}$ the isom. relation on an
invariant Borel class $\mathcal{D}$ of countable structures for a finite
signature. We use a result of Hjorth and Kechris [13]: let $\sigma$ be a
finite signature.

Let $F$ be a countable fragment of the infinitary logic
$L_{\omega_{1},\omega}(\sigma)$; this means that $F$ contains f.o. logic, and
is closed under things like substitution and taking subformulas. Let
$\mathcal{D}$ be an $\cong$-invariant Borel class of $\sigma$-structures.
Suppose for each $M\in\mathcal{D}$ there is a tuple $\overline{a}$ in $M$ such
that $\mathrm{Th}_{F}(M,\overline{a})$ (the theory in this fragment) is
$\aleph_{0}$-categorical.

Then (conclusion of the result) $\cong_{\mathcal{D}}$ is essentially
countable.

Let now $\sigma$ be the signature of meet groupoids. By the Lopez-Escobar
theorem, there is a sentence $\phi$ in $L_{\omega_{1},\omega}(\sigma)$
describing $\mathcal{D}$. There also is a formula $\delta(x)$ describing what
a “faithful subgroup” is, i.e., a $V\in M$ as above. Let $F$ be the fragment
generated by $\phi,\delta$.

######  Claim 3.8 ([26], Claim 4.5).

$\mathrm{Th}_{F}(M,\overline{a})$ is $\aleph_{0}$-categorical.

Now we can apply the Hjorth-Kechris result to get the upper bound on the
complexity of $\cong_{\mathcal{C}}$. ∎

###  4\. Ferov: A paradigm for computation with symmetries of combinatorial
structures, and visualisations thereof

####  4.1. Candidate paradigm

Visualisation of a combinatorial object and computation with its symmetries is
a difficult task. The first problem is that the way in which an object is
given can be straightforward to a mathematician with an experience in the
field, but does not have to translate in any obvious way to a computational or
graphical software that is currently available.

We propose a modular approach, where an abstract object, be that a
combinatorial structure or an element of its automorphism group, is considered
in three different ways and there is an algorithm (not necessarily uniformly
given) that provides a transition from one way of representing the object to
another. The paradigm can be summed up by the following diagram.

UserDescr.DataVisual.

The interpretation of the workflow within the diagram should be the following:

  1. (1)

the user provides a formal description of an object;

  2. (2)

based on the description given, an algorithm produces a data structure that
captures the structure of the object, potentially with additional information;

  3. (3)

based on the given data, an algorithm produces a visualisation of the object.

We explain how to interpret the terms used above.

  * •

_Formal description_ : anything that can be passed to a computer. For example,
it could be a finite presentation of a group, a symmetric matrix describing a
Coxeter system, a matrix describing a quasi-label regular tree, etc. This
information should also always go together with a positive integer that
specifies the size of the finite substructure of a possibly infinite object.

  * •

_Data_ : content of an appropriate data structure representing the abstract
object. In case of graphs, the data would capture the incidence structure of
the graph.

  * •

_Visualisation_ : any tool that, when provided with a an incidence structure
of a graph, potentially with additional data such as labels, colouring, etc.,
will produce a graphical output that can be intuitively understood by the
user. The user should have the option of tweaking the output based on their
personal aesthetics and needs.

This modular approach has two advantages. Firstly, the data can be stored and
reused without having to recompute the incidence structure of an object every
time the user wants to slightly modify the visual output, thus speeding up the
process. Secondly, this approach allows us to use tools that are readily
available without having to reinvent the wheel for our own purposes.

####  4.2. Graphs

In the case of visualisation of graphs, the description will depend on the
class of graphs we want to work with. For example, in the case of regular
trees, the description might consist of a pair of integers $(d,R)$, where $d$
denotes the degree of the tree and $R$ denotes the radius, possibly with some
significant vertices.

The two most commonly used data structures to represent graphs are adjacency
matrices and neighbour (or adjacency) lists. The meaning of an adjacency
matrix is clear: is is a square matrix whose rows and columns are indexed by
vertices of the graph. The entry on the position $(i,j)$ is an indicator
whether or not the $i$-th and the $j$-th vertex of the matrix are connected by
an edge. Adjacency matrix has many advantages, for example it allows direct
use of methods from algebraic graph theory, but for large sparse graphs, i.e.
graphs with low number of edges, it is very ineffective in terms of space.
Indeed, the graph has $n$ vertices, then the matrix is of size $n^{2}$. In
case of graphs that have uniform upper bound on the degree of a vertex, say
$d$, we know that the graph will have at most $\frac{d}{2}n$ edges. For large
$n$ this could be extremely ineffective. For this reasons, we propose to use
neighbourhood list, i.e. for each vertex we have a list of its neighbours.
Since we are primarily interested in the study of graphs with uniformly
bounded degree, we believe that list of neighbours is the appropriate data
representation of the graph. For the sake of computability this does not
really make difference, as both of these approaches are equivalent, but if
effectiveness/complexity of the computation is to be considered, the
difference will become significant.

A fairly standard format for representing the incidence structure of a graph,
including labels and colours, is DOT file. The DOT file format is supported by
specialised graph theoretic software such as

  * •

GAP \- a system for computational discrete algebra;

  * •

nauty and Traces \- programs for computing automorphism groups of graphs and
digraphs;

  * •

NetworkX \- a Python package for the creation, manipulation, and study of the
structure, dynamics, and functions of complex networks.

Clearly, this is an advantage as an output of any of the above tools can be
used as an input for any of the above, thus potentially compensating for a
lack of specific functionality within some package. For example, a Python
script could be used build the incidence structure of two graphs by using
NetworkX. The output can then be forwarded to nauty in order to determine
whether the two graphs are isomorphic.

The DOT file format is also supported by most visualisation tools such as

  * •

GraphViz \- an open source graph visualisation software;

  * •

dot2tex \- a tool designed to give graphs generated by Graphviz a more LaTeX
friendly look and feel;

  * •

d3-graphviz \- a JavaScript library that renders DOT graphs and supports
animated transitions between graphs and interactive graph manipulation in a
web browser.

####  4.3. Automorphisms of a tree

In case of computing with automorphism of a regular tree, the user might
present the automorphism in term of local actions. A $d$-regular tree
$\mathcal{T}_{d}$ has a legal edge colouring using $d$-colours, i.e. a
function $c\colon E\mathcal{T}_{d}\to\\{1,\dots,d\\}$ such that $c(e_{1})\neq
c(e_{2})$ whenever the edges $e_{1},e_{2}\in E\mathcal{T}_{d}$ are adjacent.
Clearly, each vertex $v\in V\mathcal{T}_{d}$ then “sees” each colour exactly
once and an automorphism $\alpha\in\mathop{Aut}(\mathcal{T}_{d})$ induces a
permutation $\sigma(\alpha,v)\in\mathop{Sym}(d)$ given by

$\sigma(\alpha,v)(c(e))=c(\alpha(e)),$

where $e\in E\mathcal{T}_{d}$ ranges over edges incident to $v$. If we pick a
vertex $v_{0}\in V\mathcal{T}_{d}$, then every vertex $w$ can be uniquely
identified with a finite sequence $W\in\\{1,\dots,d\\}$. One can easily check
that an each automorphism $\alpha$ is uniquely determined by a pair

$\left(w,(\sigma_{W})_{W\in\\{1,\dots,d\\}^{*}}\right),$

where $w=\alpha(v_{0})$ and $\sigma_{W}=\sigma(\alpha,W)$.

The description of an automorphism $\alpha\in\mathop{Aut}(\mathcal{T}_{d})$
provided by the user can then be the pair $(w,\overline{\sigma})$, where
$w=\alpha(v_{0})$ and $\overline{\sigma}$ is some encoding of a function from
$V\mathcal{T}_{d}$ to $\mathop{Sym}(d)$, possibly together with additional
information, such as a positive integer $R$ denoting the radius around the
vertex $v_{0}$.

The data would then consist of an appropriate data structure for storing the
the local permutations for all the vertices within the distance $R$ from the
vertex $v_{0}$. For example, in our python implementation we used the dict
structure.

In this particular case, the visualisation might not necessarily be a
graphical output, but an answer to a problem, such as the following.

  1. (1)

Does the automorphism fix a vertex? If yes, list all the fixpoints.

  2. (2)

Does the automorphism translate an edge? If yes, list its endpoints.

  3. (3)

Does the automorphism translate along an axis? If yes, compute the translation
length and describe all the vertices on the axis.

  4. (4)

Do two given automorphism “agree” on some vertex? If yes, list all such
vertices.

  5. (5)

Are two given automorphisms conjugate? If yes, specify a conjugating element.

##  Part II Nies: Two talks on computably t.d.l.c. groups

###  5\. Introduction

These notes were used by Andre for two talks at the Newcastle conference
“Computable aspects of t.d.l.c. groups” which took place in October 2022. They
form a short version of [24].

The first talk introduced two notions of computable presentation of a t.d.l.c.
group, and show their equivalence. The first notion relies on standard notions
of computability in the uncountable setting. The second notion restricts
computation to a countable structure of approximations of the elements, the
“meet groupoid” of compact open cosets. Based on this, I obtain various
examples of computably t.d.l.c. groups, such as $\operatorname{Aut}(T_{d})$
and some algebraic groups over the field of p-adic numbers. The first talk
also outlines the computability theoretic notions that are needed.

The second talk showed that given a computable presentation of a t.d.l.c.
group, the modular function and the Cayley-Abels graphs (in the compactly
generated case) are computable. We discuss the open question whether the scale
function can be non-computable. We will give a criterion based on meet
groupoids when the computable presentation is unique up to computable
isomorphism. We explain why the class of computably t.d.l.c. groups is closed
under most of the constructions studied by Wesolek [39, Thm. 1.3].

We thank Stephan Tornier and George Willis for helpful conversations on
t.d.l.c. groups, and for providing references.

The talks are centred on the following questions.

  1. (a)

How can one define a computable presentation of a t.d.l.c. group?

Which t.d.l.c. groups have such a presentation?

  2. (b)

Given a computable presentation of a t.d.l.c. group, are objects such as the
rational valued Haar measures, the modular function, or the scale function
computable?

  3. (c)

Do constructions that lead from t.d.l.c. groups to new t.d.l.c. groups have
algorithmic versions?

  4. (d)

When is a computable presentation of a t.d.l.c. group unique up to computable
isomorphism?

####  5.1. Background on t.d.l.c. groups

Van Dantzig [38] showed that each t.d.l.c. group has a neighbourhood basis of
the identity consisting of compact open subgroups. With Question (a) in mind,
we discuss six well-known examples of t.d.l.c. groups, and indicate a compact
open subgroup when it is not obvious. We will return to them repeatedly during
the course of the paper.

  1. (i)

All countable discrete groups are t.d.l.c.

  2. (ii)

All profinite groups are t.d.l.c.

  3. (iii)

$(\mathbb{Q}_{p},+)$, the additive group of $p$-adic numbers for a prime $p$
is an example of a t.d.l.c. group that is in neither of the two classes above.
The additive group ${\mathbb{Z}}_{p}$ of $p$-adic integers forms a compact
open subgroup.

  4. (iv)

The semidirect product ${\mathbb{Z}}\ltimes{\mathbb{Q}}_{p}$ corresponding to
the automorphism $x\mapsto px$ on ${\mathbb{Q}}_{p}$, and ${\mathbb{Z}}_{p}$
is a compact open subgroup.

  5. (v)

Algebraic groups over local fields, such as
$\operatorname{SL}_{n}({\mathbb{Q}}_{p})$ for $n\geq 2$, are t.d.l.c. Here
$\operatorname{SL}_{n}({\mathbb{Z}}_{p})$ is a compact open subgroup.

  6. (vi)

Given a connected countable undirected graph such that each vertex has finite
degree, its automorphism group is t.d.l.c. The stabiliser of any vertex forms
a compact open subgroup.

By convention, all t.d.l.c. groups will be infinite.

####  5.2. Computable structures: the countable case

Towards defining computable presentations, we first recall the definition of a
computable function on ${\mathbb{N}}$, slightly adapted to our purposes in
that we allow the domain to be any computable set.

######  Definition 5.1.

Given a set $S\subseteq{\mathbb{N}}^{k}$, where $k\geq 1$, a function $f\colon
S\to{\mathbb{N}}$ is called computable if there is a Turing machine that on
inputs $n_{1},\ldots,n_{k}$ decides whether the tuple of inputs
$(n_{1},\ldots,n_{k})$ is in $S$, and if so outputs $f(n_{1},\ldots,n_{k})$.

One version of the Church-Turing thesis states that computability in this
sense is the same as being computable by some algorithm.

A structure in the model theoretic sense consists of a nonempty set $D$,
called the domain, with relations and functions defined on it. The following
definition was first formulated in the 1960s by Mal’cev and Rabin
independently.

######  Definition 5.2.

A _computable structure_ is a structure such that the domain is a computable
set $D\subseteq{\mathbb{N}}$, and the functions and relations of the structure
are computable. A countable structure $S$ is called _computably presentable_
if some computable structure $W$ is isomorphic to it. In this context we call
$W$ a _computable copy_ of $S$.

####  5.3. Computable structures: the uncountable case

In the field of computable analysis (for detail see e.g. Pauly [28] or
Schröder [35]), to define computability for an uncountable structure, one
begins by representing all the elements by “names”, which are infinite objects
simple enough to be accessible to computation of oracle Turing machines. Names
usually are elements of the set $[T]$ of paths on some computable subtree $T$
of ${\mathbb{N}}^{*}$ (the tree of strings with natural number entries). For
instance, a standard name of a real number $r$ is a path coding a sequence of
rationals ${\left\langle{q_{n}}\right\rangle}_{n\in{\mathbb{N}}}$ such that
$|q_{n}-q_{n+1}|\leq 2^{-n}$ and $\lim_{n}q_{n}=r$.

Via Turing machines with tapes that hold the input, one can define
computability of functions and relations on $[T]$. One requires that the
functions and relations of the uncountable structure are computable on the
names. This defines computability on spaces relevant to computable analysis;
for instance, one can define that a function on ${\mathbb{R}}$ is computable.
Since each totally disconnected Polish space is homeomorphic to $[T]$ for some
subtree $T$ of ${\mathbb{N}}^{*}$, there is no need to distinguish between
names and objects in our setting. An _ad hoc_ way to define computability
often works for particular classes of uncountable structures: impose
algorithmic constraints on the definition of the class.

An example is the definition of when a profinite group $G$ is computable due
to Smith [36] and la Roche [19]: $G=\varprojlim_{i}(A_{i},\psi_{i})$ for a
computable diagram $(A_{i},\psi_{i})_{i\in{\mathbb{N}}}$ of finite groups and
epimorphisms $\psi_{i}\colon A_{i}\to A_{i-1}$ ($i>0$).

We now discuss the questions posed at the beginning in more detail.

####  5.4. Computable presentations of t.d.l.c. groups

We aim at a robust definition of the class of t.d.l.c. groups with a
computable presentation. We want this class to have good algorithmic closure
properties, and also ask that our definition extend the existing definitions
for discrete, and for profinite groups. We provide two types of computable
presentations, which will turn out to be equivalent: a t.d.l.c. group has a
computable presentation of one type iff it has one of the other type.

_Computable Baire presentations._ One asks that the domain of $G$ is what we
call an computably locally compact subtree of ${\mathbb{N}}^{*}$ (the tree of
strings with natural number entries), and the operations are computable in the
sense of oracle Turing machines. Baire presentations appear to be the simplest
and most elegant notion of computable presentation for general totally
disconnected Polish groups. However, computable Baire presentations are hard
to study because the domain is usually uncountable.

_Computable presentations via a meet groupoid._ We introduce an algebraic
structure $\mathcal{W}(G)$ on the countable set of compact open cosets in $G$,
together with $\emptyset$. This structure is a partially ordered groupoid,
with the usual set inclusion, and multiplication of a left coset of a subgroup
$U$ with a right coset of $U$ (which is a coset). The intersection of two
compact open cosets is such a coset itself, unless it is empty, so we have a
meet semilattice. A computable presentation of $G$ via meet groupoids is a
computable copy of the meet groupoid of $G$ such that the index function on
compact open subgroups, namely $U,V\mapsto|U\colon U\cap V|$, is also
computable.

####  5.5. Which t.d.l.c. groups $G$ have computable presentations?

Discrete groups, as well as profinite groups, have a computable presentation
as t.d.l.c. groups if and only if they have one in the previously established
sense from the 1960s and 1980s, reviewed in Section 5.2 above. We provide
numerous examples of computable presentations for t.d.l.c. groups outside
these two classes. For $({\mathbb{Q}}_{p},+)$ we use meet groupoid
presentations. For $\operatorname{Aut}(T_{d})$ and
$\operatorname{SL}_{n}({\mathbb{Q}}_{p})$ we use Baire presentations.

It can be difficult to determine whether a particular t.d.l.c. group has a
computable presentation. Nonetheless, our thesis is that _all_ “natural”
groups that are considered in the field of t.d.l.c. groups have computable
presentations. An interesting testing ground for this thesis is given by
Neretin’s groups $\mathcal{N}_{d}$ of almost automorphisms of $T_{d}$, for
$d\geq 3$; see for instance [15].

####  5.6. Associated computable objects

Recall that to a t.d.l.c. group $G$ we associate its meet groupoid
$\mathcal{W}(G)$, an algebraic structure on its compact open cosets. If $G$ is
given by a computable Baire presentation, then we construct a copy
$\mathcal{W}$ of the meet groupoid $\mathcal{W}(G)$ that is computable in a
strong sense, essentially including the condition that some (and hence any)
rational valued Haar measure on $G$ is computable when restricted to a
function $\mathcal{W}\to{\mathbb{R}}$. We will show in 9.9 that the left, and
hence also the right, action of $G$ on $\mathcal{W}$ is computable. We
conclude that the modular function on $G$ is computable. If $G$ is compactly
generated, for each Cayley-Abels graph one can determine a computable copy,
and any two copies of this type are computably quasi-isometric (10.2).
Intuitively, this means that the large-scale structure of $G$ is a computable
invariant.

Assertions that the scale function is computable have been made for particular
t.d.l.c. groups in works such as Glöckner [11] and Willis [42, Section 6]; see
the survey Willis [43]. In these particular cases, it was generally clear what
it means that one can compute the scale $s(g)$: provide an algorithm that
shows it. One has to declare what kind of input the algorithm takes;
necessarily it has to be some approximation to $g$, as $g$ ranges over a
potentially uncountable domain. Our new framework allows us to give a precise
meaning to the question whether the scale function is computable for a
particular computable presentation of a t.d.l.c. group, thus also allowing for
a precise negative answer. This appears reminiscent of the answer to Hilbert’s
10th problem, which asked for an algorithm that decides whether a multivariate
polynomial over ${\mathbb{Z}}$ has a zero. Only after a precise notion of
computable function was introduced in the 1930s, it became possible to assert
rigorously that no such algorithm exists; the final negative answer was given
in 1970 by Y. Matyasevich [22] (also see [23]). In joint work with Willis [24,
Appendix 1] we have shown that there is a computable presentation of a
t.d.l.c. group $G$ such that the scale function noncomputable for this
presentation. One can further ask whether for some computably presented $G$,
the scale is non-computable for _each_ of its computable presentations. An
even stronger negative result would be that such a $G$ can be chosen to have a
unique computable presentation (see the discussion in Section 5.8 below).

####  5.7. Algorithmic versions of constructions that lead from t.d.l.c.
groups to new t.d.l.c. groups

Section 11 shows that the class of computably t.d.l.c. groups is closed under
suitable algorithmic versions of many constructions that have been studied in
the theory of t.d.l.c. groups. In particular, the constructions (1), (2), (3)
and (6) described in Wesolek [39, Thm. 1.3] can be phrased algorithmically in
such a way that they stay within the class of computably t.d.l.c. groups; this
provides further evidence that our class is robust. These constructions are
suitable versions, in our algorithmic topological setting, of

  * •

passing to closed subgroups,

  * •

taking group extensions via continuous actions,

  * •

forming “local” direct products, and

  * •

taking quotients by closed normal subgroups

(see [39, Section 2] for detail on these constructions). The algorithmic
version of taking quotients (11.5) is the most demanding; it uses extra
insights from the proofs that the various forms of computable presentation are
equivalent.

####  5.8. When is a computable presentation unique?

Viewing a computable Baire presentation as a description, we are interested in
the question whether such a description is unique, in the sense that between
any two of them there is a computable isomorphism. Adapting terminology for
countable structures going back to Mal’cev, we will call such a group
_autostable_. If a t.d.l.c. group is autostable, then computation in the group
can be seen as independent of its particular description. 12.2 reduces the
problem of whether a t.d.l.c. group is autostable to the countable setting of
meet groupoids.

###  6\. Computability on paths of rooted trees

####  6.1. Computably locally compact subtrees of ${\mathbb{N}}^{*}$

######  Notation 6.1.

Let ${\mathbb{N}}^{*}$ denote the set of strings with natural numbers as
entries. We use letters $\sigma,\tau,\rho$ etc. for elements of
${\mathbb{N}}^{*}$. The set ${\mathbb{N}}^{*}$ can be seen as a directed tree:
the empty string is the root, and the successor relation is given by appending
a number at the end of a string. We write $\sigma\preceq\tau$ to denote that
$\sigma$ is an initial segment of $\tau$, and $\sigma\prec\tau$ to denote that
$\sigma$ is a proper initial segment. We can also identify finite strings of
length $n$+$1$ with partial functions ${\mathbb{N}}\rightarrow{\mathbb{N}}$
having finite support $\\{0,\ldots,n\\}$. We then write $\tau_{i}$ instead of
$\tau(i)$. By $\max(\tau)$ we denote $\max\\{\tau_{i}\colon\,i\leq n\\}$. Let
$h\colon{\mathbb{N}}^{*}\to{\mathbb{N}}$ be the canonical encoding given by
$h(w)=\prod_{i<|w|}p_{i}^{w_{i}+1}$, where $p_{i}$ is the $i$-th prime number.

######  Definition 6.2 (Strong indices for finite sets of strings).

For a finite set $u\subseteq{\mathbb{N}}^{*}$ let $n_{u}=\sum_{\eta\in
u}2^{h(\eta)}$; one says that $n_{u}$ is the _strong index_ for $u$.

We will usually identify a finite subset of ${\mathbb{N}}^{*}$ with its strong
index. Unless otherwise mentioned, by a (directed) tree we mean a nonempty
subset $T$ of ${\mathbb{N}}^{*}$ such that $\sigma\in T$ and $\rho\prec\sigma$
implies $\rho\in T$. By $[T]$ one denotes the set of paths of a tree $T$. Our
trees usually have no leaves, so $[T]$ is a closed set in Baire space
${\mathbb{N}}^{\mathbb{N}}$ equipped with the usual product topology. Note
that $[T]$ is compact if and only if each level of $T$ is finite, in other
words $T$ is finitely branching. For $\sigma\in T$ let

$[\sigma]_{T}=\\{X\in[T]\colon\sigma\prec X\\}$.

That is, $[\sigma]_{T}$ is the cone of paths on $T$ that extend $\sigma$.

######  Definition 6.3 (computably locally compact trees).

Let $T$ be a computable subtree of ${\mathbb{N}}^{*}$ without leaves such that
only the root can have infinitely many successors. We say that $T$ is
_computably locally compact_ , or c.l.c. for short, if there is a computable
function $H\colon{\mathbb{N}}\times{\mathbb{N}}\to{\mathbb{N}}$ such that, if
$\rho\in T$ is a nonempty string, then $\rho(i)\leq H(\rho(0),i)$ for each
$i<|\rho|$.

We note that in the paper version, the notion of c.l.c. trees is somewhat
broader: for some parameter $k\in{\mathbb{N}}^{+}$, only strings on $T$ of
length $<k$ can have infinitely many successors. This helps but is only of
technical importance.

Given such a tree $T$, the compact open subsets of $[T]$ can be
algorithmically encoded by natural numbers. The notation below will be used
throughout.

######  Definition 6.4 (Code numbers for compact open sets).

Let $T$ be a c.l.c. tree. For a finite set $u\subseteq T-\\{\emptyset\\}$, let

$\mathcal{K}_{u}=\bigcup_{\eta\in u}[\eta]_{T}$,

(note that this set is compact). By a _code number_ for a compact open set
$\mathcal{K}\subseteq[T]$ we mean the strong index for a finite set $u$ of
strings such that $\mathcal{K}=\mathcal{K}_{u}$.

Such a code number is not unique (unless $\mathcal{K}$ is empty). So we will
need to distinguish between the actual compact open set, and any of its code
numbers. So one can decide, given $u\in{\mathbb{N}}$ as an input, whether $u$
is a code number. Clearly, each compact open subset of $[T]$ is of the form
$\mathcal{K}_{u}$ for some $u$.

The following lemma shows that the basic set-theoretic relations and
operations are decidable for sets of the form $\mathcal{K}_{u}$, similar to
the case of finite subsets of ${\mathbb{N}}$.

######  Lemma 6.5.

Let $T$ be a c.l.c. tree. Given code numbers $u,w$,

  * (i)

one can compute code numbers for $\mathcal{K}_{u}\cup\mathcal{K}_{w}$ and
$\mathcal{K}_{u}\cap\mathcal{K}_{w}$;

  * (ii)

one can decide whether $\mathcal{K}_{u}\subseteq\mathcal{K}_{w}$. In
particular, one can, given a code number $u\in{\mathbb{N}}$, compute the
minimal code number $u^{*}\in{\mathbb{N}}$ such that
$\mathcal{K}_{u^{*}}=\mathcal{K}_{u}$.

###### Proof.

(i) The case of union is trivial. For the intersection operation, it suffices
to consider the case that $u$ and $w$ are singletons. For strings
$\alpha,\beta\in T$, one has $[\alpha]_{T}\cap[\beta]_{T}=\emptyset$ if
$\alpha,\beta$ are incompatbile, and otherwise
$[\alpha]_{T}\cap[\beta]_{T}=[\gamma]_{T}$ where $\gamma$ is the longest
common initial segment of $\alpha,\beta$.

(ii) Let $H$ be a computable binary function as in Definition 6.3. It suffices
to consider the case that $u$ is a singleton. Suppose that $\alpha\in
T-\\{\emptyset\\}$. The algorithm to decide whether
$[\alpha]_{T}\subseteq\mathcal{K}_{w}$ is as follows. Let $N$ be the maximum
length of a string in $w$. Answer “yes” if for each $\beta\succeq\alpha$ of
length $N$ such that $\beta(k)\leq H(\alpha,k)$ for each $k<N$, there is
$\gamma\in w$ such that $\gamma\preceq\beta$. Otherwise, answer “no”. ∎

######  Definition 6.6.

Given a c.l.c. tree $T$, let $E_{T}$ denote the set of _minimal_ code numbers
for compact open subsets of $[T]$. By the foregoing lemma, $E_{T}$ is
decidable.

####  6.2. Computable functions on the set of paths of computable trees

Most of the content of this subsection can either be seen as a special case of
known results in abstract computable topology, or can be derived from such
results.

Let $T$ be a computable subtree of ${\mathbb{N}}^{*}$ without leaves. To
define that a function which takes arguments from the potentially uncountable
domain $[T]$ is computable, one descends to the countable domain of strings on
$T$, where the usual computability notions work. The first definition, Def.
6.7 below, will apply when we show in 10.1 that the modular function on a
computable presentation of a t.d.l.c. group is computable.

######  Definition 6.7.

  1. (1)

A function $\Phi:[T]\times{\mathbb{N}}\to{\mathbb{N}}$ is computable if there
is an oracle Turing machine as follows. Given $f\in[T]$ and
$w\in{\mathbb{N}}$, when it has the list of the values $f(0),f(1),f(2),\ldots$
written on the oracle tape, with sufficiently many queries of the type “what
is $f(q)$?” it can determine the value $\Phi(f,w)$.

A function $\Psi:[T]\to{\mathbb{N}}$ is computable if the function
$\Phi(f,n)=\Psi(f)$ (which ignores the number input) is computable in the
sense above.

  2. (2)

A function $\Phi\colon[T]\to[{\mathbb{N}}^{*}]$ is computable if and only if
the function $\widetilde{\Phi}:[T]\times{\mathbb{N}}\to{\mathbb{N}}$ given by
$\widetilde{\Phi}(g,n)=\Phi(g)(n)$ is computable.

  3. (3)

Similarly, one defines that $\Phi\colon[T]\times[S]\to[{\mathbb{N}}^{*}]$ is
computable, using a TM with two oracle tapes.

######  Example 6.8.

Let $T={\mathbb{N}}^{*}$. The function $\Phi(f,n)=\sum_{i=0}^{n}f(i)$ is
computable. The oracle TM with $f$ written on the oracle tape queries the
values of $f(i)$ for $i=0,\ldots,n$ one by one and adds them.

Note that in general our functions will only be defined on $[T]$, not on all
of $[{\mathbb{N}}^{*}]$. Thus, the oracle TM only needs to return an answer if
the oracle $f$ is in $[T]$.

######  Remark 6.9.

If $T$ is c.l.c., then to say that $\Psi:[T]\to{\mathbb{N}}$ is computable
means that there is a computable prefix free set $S$ of nonempty strings on
$T$ and a computable function $\psi\colon S\to{\mathbb{N}}$ such that
$[T]=\bigcup_{\sigma\in S}[\sigma]_{T}$ and $\Psi(f)=\psi(\sigma)$ where
$\sigma$ is the unique string in $S$ such that $\sigma\prec f$. As discussed
at the meeting, this definition has time-bounded versions (assuming that the
string entries are written in their binary expansion). One requires e.g. that
$S$ and $\psi$ are in $P$. Given this one can study whether the scale is
polytime computable for particular presentations of t.d.l.c. groups.

For proofs of the following see [24, Section 6].

######  Lemma 6.10.

Suppose that $K$ and $S$ are computable trees without leaves. Suppose further
that there is a computable function $H$ such that $\sigma(i)<H(i)$ for each
$\sigma\in K$ and $i<|\sigma|$. Let $\Phi\colon[K]\to[S]$ be computable via an
oracle TM $M$.

  * (i)

There is a computable function $\gamma$ as follows: in a computation of
$\Phi(f,n)$, $M$ only needs queries up to $\gamma(n)$. A function
$\Psi:[T]\to{\mathbb{N}}$ is computable if the function $\Phi(f,n)=\Psi(f)$
(which ignores the number input) is computable in the sense above.

  * (ii)

If $\Phi$ is a bijection then $\Phi^{-1}$ is computable, via a partial
computable function that is obtained uniformly in $K,H,S$ and $P_{\Phi}$.

Intuitively, the function $g$ in (i) computes the “$\delta$” in the definition
of uniform continuity from the “$\epsilon$”: if $\delta=1/n$ we have
$\epsilon=1/g(n)$.

######  Lemma 6.11.

Let $T,S$ be c.l.c. trees. Suppose a function $\Phi\colon[T]\to[S]$ is
computable via a partial computable function $P_{\Phi}$. Given code numbers
$u,w$, one can decide whether
$\Phi(\mathcal{K}^{T}_{u})\subseteq\mathcal{K}^{S}_{w}$.

To prove Example 7.2 below, we will need a criterion on whether, given a
computable subtree $S$ of a c.l.c. tree $T$ (where $S$ potentially has
leaves), the maximally pruned subtree of $S$ with the same set of paths is
computable.

######  Proposition 6.12.

Let $T$ be a c.l.c. tree. Let $S$ be a computable subtree of $T$, and suppose
that there is a uniformly computable dense sequence
$(f_{i})_{i\in{\mathbb{N}}}$ in $[S]$. Then the tree
$\widetilde{S}=\\{\sigma\colon[\sigma]_{S}\neq\emptyset\\}$ is decidable. (It
follows that $\widetilde{S}$ is c.l.c. Of course, $[\widetilde{S}]=[S]$.)

###### Proof.

Given a string $\sigma\in T$, if $\sigma=\emptyset$ then
$\sigma\in\widetilde{S}$. Assuming $\sigma\neq\emptyset$, we can compute the
least $t\in{\mathbb{N}}$ such that $\sigma\prec f_{t}$, or $\rho\not\in S$ for
each $\rho\in T$ of length $t$ such that $\rho\succeq\sigma$; the latter
condition can be decided by the hypothesis that $T$ is c.l.c. Clearly
$\sigma\in\widetilde{S}$ iff the former condition holds. ∎

###  7\. Defining computably t.d.l.c. groups via Baire presentations

Each totally disconnected Polish space $X$ is homeomorphic to $[T]$ for some
tree $T\subseteq{\mathbb{N}}^{*}$; see [16, I.7.8]. Clearly $X$ is locally
compact iff for each $f\in[T]$ there is an $n$ such that the tree above
$f\\!\upharpoonright_{n}$ is finitely branching; we can then assume that only
the root can be infinitely branching. This suggests to work, in the
algorithmic setting, with a domain of the presentation that has the form $[T]$
for a computably locally compact tree $T$, and require that the group
operations on $[T]$ be computable according to Definition 6.7. The same
approach would work for other types of algebraic structure defined on $[T]$
for a computably locally compact tree $T$, e.g. computably t.d.l.c. rings.

######  Definition 7.1.

A _computable Baire presentation_ is a topological group of the form
$H=([T],\text{\it Mult},\text{\it Inv})$ such that

  1. (1)

$T$ is computably locally compact as defined in 6.3;

  2. (2)

$\text{\it Mult}\colon[T]\times[T]\to[T]$ and $\text{\it Inv}\colon[T]\to[T]$
are computable.

We say that a t.d.l.c. group $G$ is _computably t.d.l.c._ (via a Baire
presentation) if $G\cong H$ for such a group $H$.

######  Example 7.2.

Let $p$ be a prime, and let $n\geq 2$. Let ${\mathbb{Q}}_{p}$ denote the ring
of $p$-adic numbers. (i) The t.d.l.c. ring ${\mathbb{Q}}_{p}$ has a computable
Baire presentation. (ii) The t.d.l.c. group
$\operatorname{SL}_{n}({\mathbb{Q}}_{p})$ has a computable Baire presentation.

###### Proof.

(i) Let $Q$ be the tree of strings $\sigma\in{\mathbb{N}}^{*}$ such that all
entries, except possibly the first, are among $\\{0,\ldots,p-1\\}$, and
$r0\not\preceq\sigma$ for each $r>0$. We think of a string $r\,\widehat{\
}\,\sigma\in Q$ as denoting the rational
$p^{-r}n_{\sigma}\in{\mathbb{Z}}[1/p]$, where $n_{\sigma}$ is the number which
has $\sigma$ as a $p$-ary expansion, written in reverse order:

$n_{\sigma}=\sum_{i<|\sigma|}p^{i}\sigma(i)$.

We allow the case that $\sigma$ ends in $0$. The condition that
$r0\not\preceq\sigma$ for each $r>0$ says that $p$ does not divide
$n_{\sigma}$.

For instance, let $p=3$; then

$(3,1,0,2)$ denotes the rational $3^{-3}\cdot(1+2\cdot 9)=19/27$.

For the addition operation, consider an oracle Turing machine with two oracle
tapes starting with notations $r\sigma$ and $s\tau$ of numbers $p^{-r}m$ and
$p^{-s}n$. Say $r\leq s$. Then $p^{-r}m+p^{-s}n=p^{-s}(p^{s-r}m+n)$. Clearly
the machine can output a string denoting $p^{-r}m+p^{-s}n$. To continue the
example above, if the machine sees tapes starting with $(3,1,0,2)$ and
$(4,1,2,0,0)$, it will internally replace the first string by $(4,0,1,0,2)$,
and then keep the leading 4 and carry out the addition modulo $3^{4}$ of the
numbers $57$ and $10$ with base 3 expansions $(0,1,0,2)$ and $(1,2,0,0)$
respectively, resulting in $(4,1,0,1,2)$. (This corresponds to
$19/27+10/81=67/81$.)

A similar argument works for multiplication. It is important that we allow
improper expansions i.e. strings ending in zeros as in the example above, so
that the operation of the machines is monotonic.

(ii) We now provide a computable Baire presentation $([T],\text{\it
Mult},\text{\it Inv})$ of $\operatorname{SL}_{n}({\mathbb{Q}}_{p})$. Let $T$
be the computable tree that is an $n^{2}$-fold “power” of $Q$. More precisely,
$T=\\{\sigma\colon\forall i<n^{2}\,[\sigma^{i}\in Q]\\}$, where $\sigma^{i}$
is the string of entries of $\sigma$ in positions of the form $kn^{2}+i$ for
some $k,i\in{\mathbb{N}}$. Note that $T$ itself is not c.l.c. as nodes up to
level $n^{2}-1$ are infinitely branching. However, we can assume it is by
skipping the levels $1,\ldots,n^{2}-1$. Clearly, $[T]$ can be naturally
identified with the matrix algebra $M_{n}({\mathbb{Q}}_{p})$. By the
computability of the ring operations on ${\mathbb{Q}}_{p}$ as verified above,
the matrix product is computable as a function $[T]\times[T]\to[T]$, and the
function $\det\colon[T]\to[Q]$ is computable.

Basic computability theory shows that for any c.l.c. trees $T$ and $R$, any
computable path $f$ of $R$, and any computable function $\Phi\colon[T]\to[R]$,
there is a computable subtree $S$ of $T$ such that $[S]$ equals the pre-image
$\Phi^{-1}(f)$. Applying this to the function $\det\colon[T]\to[Q]$ and the
path $f=01000\ldots$ that denotes $1\in{\mathbb{Q}}_{p}$, we obtain a
computable subtree $S$ of $T$ such that $[S]$ can be identified with
$SL_{n}({\mathbb{Q}}_{p})$. Note that $S$ could have dead ends. We fix this
next:

It is well-known that $SL_{n}({\mathbb{Z}}[1/p])$ is dense in
$SL_{n}({\mathbb{Q}}_{p})$. This is a special case of strong approximation for
algebraic groups (see [29, Ch. 7]), but can also be seen in an elementary way
using Gaussian elimination. The paths on $S$ corresponding to matrices in
$SL_{n}({\mathbb{Z}}[1/p])$ are precisely the ones that are $0$ from some
point on. Clearly there is a computable listing $(f_{i})$ of these paths. So
by 6.12 we can replace $S$ by a c.l.c. tree $\widetilde{S}$ such that
$[\widetilde{S}]=[S]$.

To obtain a computable Baire presentation based on $\widetilde{S}$, note that
matrix multiplication on $[\widetilde{S}]$ is computable as the restriction of
matrix multiplication on $[T]$. To define the matrix inversion operation Inv,
we use the fact that the inverse of a matrix with determinant $1$ equals its
adjugate matrix; the latter can be obtained by computing determinants on
minors. ∎

###  8\. Defining computably t.d.l.c. groups via meet groupoids

This section provides the detail for the second type (Type M) of computable
presentations of t.d.l.c. groups described in Section 5.4.

####  8.1. The meet groupoid of a t.d.l.c. group

Intuitively, the notion of a groupoid generalizes the notion of a group by
allowing that the binary operation is partial. A groupoid is given by a domain
$\mathcal{W}$ on which a unary operation $(.)^{-1}$ and a partial binary
operation, denoted by “$\cdot$”, are defined. These operations satisfy the
following conditions:

  * (a)

associativity in the sense that $(A\cdot B)\cdot C=A\cdot(B\cdot C)$, with
either both sides or no side defined (and so the parentheses can be omitted);

  * (b)

$A\cdot A^{-1}$ and $A^{-1}\cdot A$ are always defined;

  * (c)

if $A\cdot B$ is defined then $A\cdot B\cdot B^{-1}=A$ and $A^{-1}\cdot A\cdot
B=B$.

It follows from (c) that a groupoid satisfies the left and right cancellation
laws. One says that an element $U\in\mathcal{W}$ is _idempotent_ if $U\cdot
U=U$. Clearly this implies that $U=U\cdot U^{-1}=U^{-1}\cdot U$ and so
$U=U^{-1}$ by cancellation. Conversely, by (c) every element of the form
$A\cdot A^{-1}$ or $A^{-1}\cdot A$ is idempotent.

######  Definition 8.1.

A _meet groupoid_ is a groupoid $(\mathcal{W},\cdot,{(.)}^{-1})$ that is also
a meet semilattice $(\mathcal{W},\cap,\emptyset)$ of which $\emptyset$ is the
least element. Writing $A\subseteq B\Leftrightarrow A\cap B=A$ and letting the
operation $\cdot$ have preference over $\cap$, it satisfies the conditions

  * (d)

$\emptyset^{-1}=\emptyset=\emptyset\cdot\emptyset$, and $\emptyset\cdot A$ and
$A\cdot\emptyset$ are undefined for each $A\neq\emptyset$,

  * (e)

if $U,V$ are idempotents such that $U,V\neq\emptyset$, then $U\cap
V\neq\emptyset$,

  * (f)

$A\subseteq B\Leftrightarrow A^{-1}\subseteq B^{-1}$, and

  * (g)

if $A_{i}\cdot B_{i}$ are defined ($i=0,1$) and $A_{0}\cap
A_{1}\neq\emptyset\neq B_{0}\cap B_{1}$, then

$(A_{0}\cap A_{1})\cdot(B_{0}\cap B_{1})=A_{0}\cdot B_{0}\cap A_{1}\cdot
B_{1}$.

From (g) it follows and that the groupoid operations are monotonic: if
$A_{i}\cdot B_{i}$ are defined ($i=0,1$) and $A_{0}\subseteq
A_{1},B_{0}\subseteq B_{1}$, then $A_{0}\cdot B_{0}\subseteq A_{1}\cdot
B_{1}$. Also, if $U$ and $V$ are idempotent, then so is $U\cap V$ (this can
also be verified on the basis of (a)-(f) alone).

For meet groupoids $\mathcal{W}_{0},\mathcal{W}_{1}$, a bijection
$h\colon\mathcal{W}_{0}\to\mathcal{W}_{1}$ is an _isomorphism_ if it preserves
the three operations. Given a meet groupoid $\mathcal{W}$, the letters $A,B,C$
will range over general elements of $\mathcal{W}$, and the letters $U,V,W$
will range over idempotents of $\mathcal{W}$.

We use set theoretic notation for the meet semilattice because for the
motivating examples of meet groupoids the intersection symbol means the usual.
Note that the intersection of two cosets is empty, or again a coset.

######  Definition 8.2.

Let $G$ be a t.d.l.c. group. We define a meet groupoid $\mathcal{W}(G)$. Its
domain consists of the compact open cosets in $G$ (i.e., cosets of compact
open subgroups of $G$), as well as the empty set. We define $A\cdot B$ to be
the usual product $AB$ in case that $A=B=\emptyset$, or $A$ is a left coset of
a subgroup $V$ and $B$ is a right coset of $V$; otherwise $A\cdot B$ is
undefined.

######  Fact 8.3.

$\mathcal{W}(G)$ is a meet groupoid with the groupoid operations $\cdot$ and
$A\to A^{-1}$, and the usual intersection operation $\cap$.

We will use the usual group theoretic terminology for elements of an abstract
meet groupoid $\mathcal{W}$. If $U$ is an idempotent of $\mathcal{W}$ we call
$U$ a _subgroup_ , if $AU=A$ we call $A$ a _left coset_ of $U$, and if $UB=B$
we call $B$ a _right coset_ of $U$. Based on the axioms, one can verify that
if $U\subseteq V$ for subgroups $U,V$, then the map $A\mapsto A^{-1}$ induces
a bijection between the left cosets and the right cosets of $U$ contained in
$V$.

We note that $\mathcal{W}(G)$ satisfies the axioms of inductive groupoids
defined in Lawson [20, page 109]. See [8, Section 4] for more on an axiomatic
approach to meet groupoids.

######  Remark 8.4.

It is well-known [12] that one can view groupoids as small categories in which
every morphism has an inverse. The elements of the groupoid are the morphisms
of the category. The idempotent morphisms correspond to the objects of the
category. One has $A\colon U\to V$ where $U=A\cdot A^{-1}$ and $V=A^{-1}\cdot
A$. Thus, in $\mathcal{W}(G)$, $A\colon U\to V$ means that $A$ is a right
coset of $U$ and a left coset of $V$.

The idea to study appropriate Polish groups via an algebraic structure on
their open cosets is due to Katrin Tent, and first appeared in [17]. This idea
was further elaborated in a paper by Nies, Schlicht and Tent on the complexity
of the isomorphism problem for oligomorphic groups [26]. There, approximation
structures are used that are given by the ternary relation “$AB\subseteq C$”,
where $A,B,C$ are certain open cosets. They are called “coarse groups”. In the
present work, it will be important that we have explicit access to the
combination of the groupoid and the meet semilattice structures (which coarse
groups don’t provide). Coarse groups are too “coarse” an algebraic structure
to analyse algorithmic aspects of t.d.l.c. groups.

The meet groupoid $\mathcal{W}(G)$ might turn out to be a useful tool for
studying $G$, apart from algorithmic considerations. For a locally compact
group $G$, the group $\operatorname{Aut}(G)$ becomes a Polish group via the
Braconnier topology, given by the sub-basis of identity neighbourhoods of the
form

$\mathfrak{A}(K,U)=\\{\alpha\in\operatorname{Aut}(G)\colon\,\forall x\in
K[\alpha(x)\in Ux\,\land\,\alpha^{-1}(x)\in Ux]\\}$,

where $K$ ranges over the compact subsets of $G$, and $U$ over the identity
neighbourhoods of $G$. As noted in [5, Appendix A], $\operatorname{Aut}(G)$
with this topology is Polish (assuming that $G$ is countably based). For a
t.d.l.c. group $G$, the following shows that $\operatorname{Aut}(G)$ can be
viewed as the automorphism group of a countable structure.

######  Proposition 8.5.

Let $G$ be a t.d.l.c. group. The group $\operatorname{Aut}(G)$ with the
Braconnier topology is topologically isomorphic to
$\operatorname{Aut}(\mathcal{W}(G))$, via the map $\Gamma$ that sends
$\alpha\in\operatorname{Aut}(G)$ to its action on $\mathcal{W}(G)$, that is
$B\mapsto\alpha(B)$.

###### Proof.

It is clear that $\Gamma$ is an injective group homomorphism. To show that
$\Gamma$ is continuous, consider an identity neighbourhood of
$\operatorname{Aut}(\mathcal{W}(G))$, which we may assume to have the form
$\\{\beta\colon\,\beta(A_{i})=A_{i},i=1,\ldots,n\\}$ where
$A_{i}\in\mathcal{W}(G)$. Let $U=\bigcap_{i}A_{i}A_{i}^{-1}$ and $K=\bigcup
A_{i}$. Then $\alpha\in\mathfrak{A}(K,U)$ implies $\alpha(A_{i})=A_{i}$ for
each $i$.

To show $\Gamma$ is onto, we explicitly describe its inverse $\Delta$. Recall
our convention that the variable $U$ ranges over the compact open subgroups of
$G$. Note that $\bigcap_{U}gU=\bigcap_{U}Ug=\\{g\\}$. Since $\beta$ is an
automorphism and the $\beta(gU)$ are compact, $L=\bigcap_{U}\beta(gU)$ is non-
empty. If $|L|>1$ then there are $C,D\in\mathcal{W}(G)$ such that $C\cap
D=\emptyset$, and $C\cap L\neq\emptyset\neq D\cap L$. By compactness this
implies $\beta^{-1}(C)\cap\\{g\\}\neq\emptyset\neq\beta^{-1}(D)\cap\\{g\\}$, a
contradiction. So

$\Delta(\beta)(g)=h\Leftrightarrow h\in\bigcap_{U}\beta(gU)$

defines a map $\Delta\colon\operatorname{Aut}(\mathcal{W}(G))\to G^{G}$.

######  Claim 8.6.

Let $\overline{\beta}=\Delta(\beta)$. We have
$\overline{\beta}\in\operatorname{Aut}(G)$.

Clearly $\Delta(\beta^{-1})=\overline{\beta}^{-1}$, so $\overline{\beta}$ is a
permutation of $G$. Ignoring for the moment the difference between group
elements and the singletons containing them, we have

$\overline{\beta}(g^{-1})=\bigcap_{U}\beta(g^{-1}U)=\bigcap_{V}\beta(Vg^{-1})=(\bigcap_{V}\beta(gV))^{-1}=(\overline{\beta}(g))^{-1}$.

Also one can verify that $\beta$ preserves the binary group operation, using
that

$\bigcap_{U}gU\bigcap_{V}hV=\bigcap_{V}ghV=\bigcap_{V}(gV^{h^{-1}}hV)$.

If $g\in V$ then $\overline{\beta}(g)\in\beta(V)$, so $\overline{\beta}$ is
open. Arguing the same for $\beta^{-1}$, we conclude that $\overline{\beta}$
is a homeomorphism of $G$. This shows the claim.

######  Claim 8.7.

If $\beta\in\operatorname{Aut}(\mathcal{W}(G))$ and $B\in\mathcal{W}(G)$, then
$\Gamma(\Delta(\beta))(B)=\beta(B)$.

By the definitions of $\Gamma$ and $\Delta$, we have

$h\in\Gamma(\Delta(\beta))(B)\Leftrightarrow\exists g\in
B[h\in\bigcap_{U}\beta(gU)]$.

Letting $V=B^{-1}B$, we have $B=gU$, so
$\Gamma(\Delta(\beta))(B)\subseteq\beta(B)$. For the converse inclusion,
suppose that $h\not\in\Gamma(\Delta(\beta))(B)$. Then for each $g\in B$ there
is $U_{g}$ such that $h\not\in\beta(gU_{g})$. Since $B$ is compact and
$B\subseteq\bigcup_{g\in B}U_{g}$, there is a finite set $S\subseteq G$ such
that $B\subseteq\bigcup_{g\in S}gU_{g}$. ∎

####  8.2. Second definition of computably t.d.l.c. groups

######  Definition 8.8.

A meet groupoid $\mathcal{W}$ is called _Haar computable_ if

  * (a)

its domain is a computable subset $D$ of ${\mathbb{N}}$;

  * (b)

the groupoid and meet operations are computable in the sense of Definition
5.1; in particular, the relation $\\{\langle x,y\rangle\colon\,x,y\in
S\,\land\,x\cdot y\text{ is defined}\\}$ is computable;

  * (c)

the partial function with domain contained in $D\times D$ sending a pair of
subgroups $U,V\in\mathcal{W}$ to $|U:U\cap V|$ is computable.

Here $|U\colon U\cap V|$ is defined abstractly as the number of left, or
equivalently right, cosets of the nonzero idempotent $U\cap V$ contained in
$U$; we require implicitly that this number is always finite. Note that by
(b), the partial order induced by the meet semilattice structure of
$\mathcal{W}$ is computable. Also, (b) implies that being a subgroup is
decidable when viewed as a property of elements of the domain $S$; this is
used in (c). The condition (c) corresponds to the computable bound $H$
required in Definition 6.3. For ease of reading we will say that $n\in D$
_denotes_ a coset $A$, rather than saying that $n$ “is” a coset.

######  Definition 8.9 (Computably t.d.l.c. groups via meet groupoids).

Let $G$ be a t.d.l.c. group. We say that $G$ is _computably t.d.l.c._ via a
meet groupoid if $\mathcal{W}(G)$ has a Haar computable copy $\mathcal{W}$. In
this context, we call $\mathcal{W}$ a computable presentation of $G$ (in the
sense of meet groupoids).

######  Remark 8.10.

In this setting, Condition (c) of Definition 8.8 is equivalent to saying that
every Haar measure $\mu$ on $G$ that assigns a rational number to some compact
open subgroup (and hence is rational-valued) is computable on $\mathcal{W}$,
in the sense that the function assigning to a compact open coset $A$ the
rational $\mu(A)$ is computable. Consider left Haar measures, say. First
suppose that (c) holds. Given $A$, compute the subgroup $V$ such that
$A=A\cdot V$, i.e., $A$ is a left coset of $V$. Compute $W=U\cap V$. We have
$\mu(A)=\mu(V)=\mu(U)\cdot|V:W|/|U:W|$.

Conversely, if the Haar measure is computable on $\mathcal{W}$, then (c) holds
because $|U\colon V|=\mu(U)/\mu(V)$.

For discrete groups, the condition (c) can be dropped, as the proof of the
following shows.

######  Example 8.11.

A discrete group $G$ is computably t.d.l.c. via a meet groupoid
$\Leftrightarrow$ $G$ has a computable copy in the usual sense of Definition
5.2.

###### Proof.

For the implication $\Leftarrow$, we may assume that $G$ itself is computable;
in particular, we may assume that its domain is a computable subset of
${\mathbb{N}}$. Each compact coset in $G$ is finite, and hence can be
represented by a strong index for a finite set of natural numbers. Since the
group operations are computable on the domain, this implies that the meet
groupoid of $G$ has a computable copy. It is then trivially Haar computable.

For the implication $\Rightarrow$, let $\mathcal{W}$ be a Haar computable copy
of $\mathcal{W}(G)$. Since $G$ is discrete, $\mathcal{W}$ contains a least
subgroup $U$. The set of left cosets of $U$ is computable, and forms a group
with the groupoid and inverse operations. This yields the required computable
copy of $G$. ∎

By $\mathbb{Q}_{p}$ we denote the additive group of the $p$-adics. By the
usual definition of semidirect products ([33, p. 27]),
${\mathbb{Z}}\ltimes{\mathbb{Q}}_{p}$ is the group defined on the Cartesian
product ${\mathbb{Z}}\times{\mathbb{Q}}_{p}$ via the binary operation $\langle
z_{1},\alpha_{1}\rangle\cdot\langle z_{2},\alpha_{2}\rangle=\langle
z_{1}+z_{2},p^{z_{2}}\alpha_{1}+\alpha_{2}\rangle$. This turns
${\mathbb{Z}}\ltimes{\mathbb{Q}}_{p}$ into a topological group with the
product topology.

######  Example 8.12.

For any prime $p$, the additive group ${\mathbb{Q}}_{p}$ and the group
${\mathbb{Z}}\ltimes{\mathbb{Q}}_{p}$ are computably t.d.l.c. via a meet
groupoid.

###### Proof.

We begin with the additive group ${\mathbb{Q}}_{p}$. Note that its open proper
subgroups are of the form $U_{r}:=p^{r}{\mathbb{Z}}_{p}$ for some
$r\in{\mathbb{Z}}$. Let $C_{p^{\infty}}$ denote the Prüfer group
${\mathbb{Z}}[1/p]/{\mathbb{Z}}$, where
${\mathbb{Z}}[1/p]=\\{zp^{-k}\colon\,z\in{\mathbb{Z}}\,\land\,k\in{\mathbb{N}}\\}$.
For each $r$ there is a canonical epimorphism
$\pi_{r}\colon{\mathbb{Q}}_{p}\to C_{p^{\infty}}$ with kernel $U_{r}$: if
$\alpha=\sum_{i=-n}^{\infty}s_{i}p^{i}$ where $0\leq s_{i}<p$,
$n\in{\mathbb{N}}$, we have

$\pi_{r}(\alpha)={\mathbb{Z}}+\sum_{i=-n}^{r-1}s_{i}p^{i-r}$;

here an empty sum is interpreted as $0$. (Informally, $\pi_{r}(\alpha)$ is
obtained by taking the “tail” of $\alpha$ from the position $r-1$ onwards to
the last position, and shifting it in order to represent an element of
$C_{p^{\infty}}$.) So each compact open coset in ${\mathbb{Q}}_{p}$ can be
uniquely written in the form $D_{r,a}=\pi_{r}^{-1}(a)$ for some
$r\in{\mathbb{Z}}$ and $a\in C_{p^{\infty}}$. The domain
$S\subseteq{\mathbb{N}}$ of the Haar computable copy $\mathcal{W}$ of
$\mathcal{W}({\mathbb{Q}}_{p})$ consists of natural numbers canonically
encoding such pairs $\langle r,a\rangle$. They will be identified with the
cosets they denote.

The groupoid operations are computable because we have
$D_{r,a}^{-1}=D_{r,-a}$, and $D_{r,a}\cdot D_{s,b}=D_{r,a+b}$ if $r=s$, and
undefined otherwise. It is easy to check that $D_{r,a}\subseteq D_{s,b}$ iff
$r\geq s$ and $p^{r-s}a=b$. So the inclusion relation is decidable. We have
$D_{r,a}\cap D_{s,b}=\emptyset$ unless one of the sets is contained in the
other, so the meet operation is computable. Finally, for $r\leq s$, we have
$|U_{r}:U_{s}|=p^{s-r}$ which is computable.

Next, let $G={\mathbb{Z}}\ltimes{\mathbb{Q}}_{p}$; we build a Haar computable
copy $\mathcal{V}$ of $\mathcal{W}(G)$. We will extend the listing
$(D_{r,a})_{r\in{\mathbb{Z}},a\in C_{p^{\infty}}}$ of compact open cosets in
${\mathbb{Q}}_{p}$ given above. For each compact open subgroup of $G$, the
projection onto ${\mathbb{Z}}$ is compact open, and hence the trivial group.
So the only compact open subgroups of $G$ are of the form $U_{r}$. Let $g\in
G$ be the generator of ${\mathbb{Z}}$ such that $g^{-1}\alpha g=p\alpha$ for
each $\alpha\in{\mathbb{Q}}_{p}$ (where ${\mathbb{Z}}$ and ${\mathbb{Q}}_{p}$
are thought of as canonically embedded into $G$). Each compact open coset of
$G$ has a unique form $g^{z}D_{r,a}$ for some $z\in{\mathbb{Z}}$. Formally
speaking, the domain of the computable copy of $\mathcal{W}(G)$ consists of
natural numbers encoding the triples $\langle z,r,a\rangle$ corresponding to
such cosets; as before they will be identified with the cosets they denote.

To show that the groupoid and meet operations are computable, note that we
have $gD_{r,a}=D_{r-1,a}g$ for each $r\in{\mathbb{Z}},a\in C_{p^{\infty}}$,
and hence $g^{z}D_{r,a}=D_{r-z,a}g^{z}$ for each $z\in{\mathbb{Z}}$. Given two
cosets $g^{v}D_{r,a}$ and $g^{w}D_{s,b}=D_{s-w,b}g^{w}$, their composition is
defined iff $r=s-w$, in which case the result is $g^{v+w}D_{s,a+b}$. The
inverse of $g^{z}D_{r,a}$ is $D_{r,-a}g^{-z}=g^{-z}D_{r-z,-a}$.

To decide the inclusion relation, note that we have $g^{z}D_{r,a}\subseteq
g^{w}D_{s,b}$ iff $z=w$ and $D_{r,a}\subseteq D_{s,b}$, and otherwise, they
are disjoint. Using this one can show that the meet operation is computable
(by an argument that works in any computable meet groupoid $\mathcal{V}$): if
$A_{0},A_{1}\in\mathcal{V}$, $A_{i}\colon U_{i}\to V_{i}$, and $A_{0},A_{1}$
are not disjoint, then $A_{0}\cap A_{1}$ is the unique $C\in\mathcal{V}$ such
that $C\colon U_{0}\cap U_{1}\to V_{0}\cap V_{1}$ and $C\subseteq
A_{0},A_{1}$. Since $\mathcal{W}$ satisfies Condition (c) in Definition 8.8,
and $\mathcal{V}$ has no subgroups beyond the ones present in $W$, we conclude
that $\mathcal{V}$ is Haar computable. ∎

###  9\. Equivalence of the two types of computable presentations

We show that a t.d.l.c. group $G$ has a computable presentation in the sense
of Def. 7.1 iff $G$ has a computable presentation in the sense of Def. 8.9.

We need some preliminaries. For strings
$\sigma_{0},\sigma_{1}\in{\mathbb{N}}^{*}$ of the same length $n$, let
$\sigma_{0}\otimes\sigma_{1}$ denote the string $\tau$ of that length such
that $\tau(k)=\langle\sigma_{0}(k),\sigma_{1}(k)\rangle$ for each $k<n$ (where
$\langle.,.\rangle$ is a computable pairing function, such as Cantor’s).

######  Lemma 9.1.

Let $G$ be computably t.d.l.c. via a computable Baire presentation
$([T],\text{\it Mult},\text{\it Inv})$. Recall the set $E_{T}$ of minimal code
numbers for compact open sets from Definition 6.6.

(i) There is a computable function $I\colon E_{T}\to E_{T}$ such that for each
$u\in E_{T}$, one has $\mathcal{K}_{I(u)}=(\mathcal{K}_{u})^{-1}$.

(ii) For $u,v,w\in E_{T}$ one can decide whether
$\mathcal{K}_{u}\mathcal{K}_{v}\subseteq\mathcal{K}_{w}$.

###### Proof.

(i) By Lemma 6.11 one can decide whether
$\mathcal{K}_{u}\subseteq(\mathcal{K}_{w})^{-1}$. The equality
$\mathcal{K}_{u}=(\mathcal{K}_{w})^{-1}$ is equivalent to
$\mathcal{K}_{u}\subseteq(\mathcal{K}_{w})^{-1}\,\land\,\mathcal{K}_{w}\subseteq(\mathcal{K}_{u})^{-1}$.
So one lets $I(u)$ be the least index $v$ such that this equality holds.

(ii) Let $\widetilde{T}$ be the tree of initial segments of strings of the
form $\sigma_{0}\otimes\sigma_{1}$, where $\sigma_{0},\sigma_{1}\in T$ have
the same length. Then $\widetilde{T}$ is a c.l.c. tree, $[\widetilde{T}]$ is
naturally homeomorphic to $[T]\times[T]$, and Mult can be seen as a computable
function $[\widetilde{T}]\to[T]$. Now one applies Lemma 6.11. ∎

We will also need a computable presentation of the topological group of
permutations of ${\mathbb{N}}$ based on a subtree of ${\mathbb{N}}^{*}$.
Define a computable tree without leaves by

$\mathit{Tree}(S(\omega))=\\{\sigma\otimes\tau\colon\sigma,\tau\in{\mathbb{N}}^{*}\,\land\,$

$\sigma,\tau\,\text{are
1-1}\,\land\,\sigma(\tau(k))=k\,\land\,\tau(\sigma(i))=i\text{ whenever
defined}\\}$.

A string $\sigma\otimes\tau\in\mathit{Tree}(S(\omega))$ gives rise to a finite
injection $\alpha_{\sigma\otimes\tau}$ on ${\mathbb{N}}$, defined by

(9.1) $\alpha_{\sigma\otimes\tau}(r)=s\text{ iff
}\sigma(r)=s\,\lor\,\tau(s)=r.$

The paths of $\text{Tree}({S(\omega)})$ can be viewed as the permutations of
${\mathbb{N}}$, paired with their inverses:

$[\mathit{Tree}(S(\omega))]=\\{f\otimes f^{-1}\colon\,f\text{ is permutation
of }{\mathbb{N}}\\}$.

The group operations on $\mathit{Tree}(S(\omega))$ are computable: we have

$\displaystyle(f_{0}\otimes f_{1})^{-1}$ $\displaystyle=$ $\displaystyle
f_{1}\otimes f_{0}$ $\displaystyle(f_{0}\otimes f_{1})\cdot(g_{0}\otimes
g_{1})$ $\displaystyle=$ $\displaystyle(f_{0}\circ g_{0})\otimes(g_{1}\circ
f_{1}).$

For a closed subgroup $\widetilde{G}$ of $S(\omega)$, we write

$\mathit{Tree}(\widetilde{G})=\\{\sigma\in\mathit{Tree}(S(\omega))\colon\,[\sigma]_{\mathit{Tree}(S(\omega))}\cap\widetilde{G}\neq\emptyset\\}$.

Note that this is a subtree of $\mathit{Tree}(S(\omega))$ without leaves. We
say that $\widetilde{G}$ is computable if $\mathit{Tree}(\widetilde{G})$ is
computable.

######  Theorem 9.2.

A group $G$ is computably t.d.l.c. via a Baire presentation (Def. 7.1)
$\Leftrightarrow$

$G$ is computably t.d.l.c. via a meet groupoid (Def. 8.9).

From a presentation of $G$ of one type, one can uniformly obtain a
presentation of $G$ of the other type.

###### Proof.

$\Leftarrow:$ (This is the harder implication - if you don’t want to read it
skip to Page 9.)

We begin by defining an operator that, for Haar computable meet groupoids, is
dual to the operation of sending $G$ to a computable copy of $\mathcal{W}(G)$
obtained above.

######  Definition 9.3.

Given a meet groupoid $\mathcal{W}$ with domain ${\mathbb{N}}$, let
$\widetilde{G}=\mathcal{G}_{\text{comp}}(\mathcal{W})$ be the closed subgroup
of $S(\omega)$ consisting of elements $p$ that preserve the meet operation of
$\mathcal{W}$, and satisfy $p(A)\cdot B=p(A\cdot B)$ whenever $A\cdot B$ is
defined.

Recall that the elements of $S(\omega)$ are not actually permutations, but
paths on $\mathit{Tree}(S(\omega))$ encoding pairs consisting of a permutation
and its inverse. However, if $p\in\mathit{Tree}(\widetilde{G})$, and
$A\in\mathcal{W}$ is denoted by $i$, we will suggestively write $p(A)$ for the
element of $\mathcal{W}$ denoted by the first component of the pair of natural
numbers encoded by $p(i)$. We note that for each subgroup
$U\in\mathcal{W}(G)$, the set $B=p(U)$ satisfies $B\cdot U=p(U)\cdot
U=p(U\cdot U)=B$, and hence is a left coset of $U$. The following diagram
displays the condition in the definition above in category terms as a
commutative diagram.

$\textstyle{U\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{A}$$\textstyle{V\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{B}$$\textstyle{W}$$\textstyle{U^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{p(A)}$$\textstyle{p(A\cdot
B)}$

Now suppose that $\mathcal{W}$ is as in Definition 8.9. Recall the convention
that all t.d.l.c. groups are infinite. So the domain of $\mathcal{W}$ equals
${\mathbb{N}}$, and there is an isomorphism of meet groupoids
$\mathcal{W}\to\mathcal{W}(G)$, which below we will use to identify
$\mathcal{W}$ and $\mathcal{W}(G)$. Define a group homomorphism $\Phi\colon
G\to\widetilde{G}$ by letting $\Phi(g)$ be the element of $S(\omega)$
corresponding to the left action of $g$, i.e. $A\mapsto gA$ where
$A\in\mathcal{W}(G)$. Note that $\Phi$ is injective because the compact open
subgroups form a neighbourhood basis of $1$: if $g\neq 1$ then $g\not\in U$
for some compact open subgroup $U$, so that $\Phi(g)(U)\neq U$.

######  Claim 9.4.

$\Phi\colon G\cong\widetilde{G}$.

To show that $\Phi$ is onto, let $p\in\widetilde{G}$. Since

$\\{p(U)\colon U\in\mathcal{W}(G)\text{ is a subgroup}\\}$

is a filter on $\mathcal{W}(G)$ containing a compact set, there is an element
$g$ in its intersection. Then $\Phi(g)=p$: recall that for each subgroup
$U\in\mathcal{W}(G)$, the set $B=p(U)$ is a left coset of $U$, and hence
equals $gU$. So, if $A$ is a right coset of $U$, then $p(A)=p(U\cdot A)=B\cdot
A=gA$.

To show that $\Phi$ is continuous at $1$ (and hence continuous), note that a
basis of neighbourhoods of the identity in $\widetilde{G}$ is given by the
open sets

$\\{p\in\widetilde{G}\colon\forall i\leq n\,[p(A_{i})=A_{i}]\\}$,

where $A_{1},\ldots,A_{n}\in\mathcal{W}(G)$. Given such a set, suppose $A_{i}$
is a right coset of $U_{i}$, and let $U=\bigcap U_{i}$. If $g\in U$ then
$gA_{i}=A_{i}$ for each $i$.

The open mapping theorem for Hausdorff groups says that every surjective
continuous homomorphism from a $\sigma$-compact group (such as a t.d.l.c.
group with a countable basis of the topology) onto a Baire group is open. So
$\Phi$ is open. This verifies the claim.

Using the assumption that $\mathcal{W}$ is Haar computable, we now show that
$\mathit{Tree}(\widetilde{G})$ is c.l.c. as in Definition 6.3. The following
claim will be used to show that $\mathit{Tree}(\widetilde{G})$ is computable.

######  Claim 9.5.

A finite injection $\alpha$ on ${\mathbb{N}}$ can be extended to some
$p\in\widetilde{G}$

$\Leftrightarrow$ $B\cdot A^{-1}$ is defined whenever $\alpha(A)=B$, and

$\bigcap\\{B\cdot A^{-1}\colon\,\alpha(A)=B\\}\neq\emptyset$.

For right to left, let $g$ be an element of the intersection. Then $gA=B\cdot
A^{-1}\cdot A=B=\alpha(A)$ for each $A\in\mathrm{dom}(\alpha)$.

For left to right, suppose $p\in\widetilde{G}$ extends $\alpha$. By 9.4, there
is $g\in G$ such that $p=\Phi(g)$. Then $gA=p(A)=B$ for each $A,B$ such that
$\alpha(A)=B$. Such $A,B$ are right cosets of the same subgroup. Hence $B\cdot
A^{-1}$ is defined, and clearly $g$ is in the intersection. This establishes
the claim.

By (9.1),

$S=\\{\sigma\otimes\tau\colon\,\alpha_{\sigma\otimes\tau}\text{ can be
extended to some }p\in\widetilde{G}\\}$

is a computable subtree of $\mathit{Tree}(S(\omega))$ without leaves, and
$\widetilde{G}=[S]$. Hence $S=\mathit{Tree}(\widetilde{G})$.

Claim 9.7 below will verify that $S=\mathit{Tree}(\widetilde{G})$ is a c.l.c.
tree as defined in 6.3. The following lemma does the main work. Informally it
says that given some subgroup $U\in\mathcal{W}$, if one declares that
$p\in\widetilde{G}$ has a value $L\in\mathcal{W}$ at $U$, then one can compute
for any $F\in\mathcal{W}$ the finite set of possible values of $p$ at $F$.

######  Lemma 9.6 (Effectively finite suborbits).

Suppose that $U\in\mathcal{W}$ is a subgroup and $L$ is a left coset of $U$.
Let $F\in\mathcal{W}$. One can uniformly in $U,L$ and $F$ compute a strong
index for the finite set
$\mathcal{L}=\\{p(F)\colon\,p\in[S]\,\land\,p(U)=L\\}$.

To see this, first one computes $V=F^{-1}\cdot F$, so that $F$ is a right
coset of the subgroup $V$. Next one computes $k=|U\colon U\cap V|$, the number
of left cosets of $U\cap V$ in $U$. Note that

$\mathcal{L}_{0}=\\{p(U\cap V)\colon p\in[S]\,\land\,p(U)=L\\}$

is the set of left cosets of $U\cap V$ contained in $L$. Clearly this set has
size $k$. By searching $\mathcal{W}$ until all of its elements have appeared,
one can compute a strong index for this set. Next one computes a strong index
for the set $\mathcal{L}_{1}$ of left cosets $D$ of $V$ such that $C\subseteq
D$ for some $C\in\mathcal{L}_{0}$ (this uses that given $C$ one can compute
$D$). Finally one outputs a strong index for the set $\\{D\cdot
F\colon\,D\in\mathcal{L}_{1}\\}$, which equals $\mathcal{L}$. This shows the
lemma.

We make the assumption that $0$ denotes a subgroup $U$ in $\mathcal{W}$. This
does not affect the uniformity statement of the theorem: otherwise we can
search $\mathcal{W}$ for the least $n$ such that $n$ is a subgroup, and then
work with a new copy of $\mathcal{W}(G)$ where $0$ and $n$ are swapped.

######  Claim 9.7.

There is a computable binary function $H$ such that, if $\rho\in S$, then
$\rho(i)\leq H(\rho(0),i)$ for each $i<|\rho|$.

Let $F$ be the coset denoted by $k$. Let $\rho(0)=\langle a_{0},a_{1}\rangle$
and let $L_{r}$ be the coset denoted by $a_{r}$, $r=0,1$. Applying Lemma 9.6
to $U,L_{r},F$, one can compute $H(\sigma,i)$ as the greatest pair $\langle
b_{0},b_{1}\rangle$ such that $b_{r}$ denotes an element of
$\\{p(F)\colon\,p\in[S]\,\land\,p(U)=L_{r}\\}$ for $r=0,1$.

$\Rightarrow:$ We build a Haar computable copy $\mathcal{W}$ of the meet
groupoid $\mathcal{W}(G)$ as in Definition 8.9. By Lemma 9.1, one can decide
whether $u\in E_{T}$ is the code number of a subgroup (Definition 6.4).
Furthermore, one can decide whether $B=\mathcal{K}_{v}$ is a left coset of a
subgroup $U=\mathcal{K}_{u}$: this holds iff $BU\subseteq B$ and
$BB^{-1}\subseteq U$, and the latter two conditions are decidable by Lemma
9.1. Similarly, one can decide whether $B$ is a right coset of $U$.

It follows that the set $\\{u\in E_{T}\colon\,\mathcal{K}_{u}\text{ is a
coset}\\}$ can be obtained via an existential quantification over a computable
binary relation (in other words, $V$ is recursively enumerable). Hence, by a
basic fact of computability theory, there is computable 1-1 function $\theta$
defined on an initial segment of ${\mathbb{N}}-\\{0\\}$ such that the range of
$\theta$ equals this set. Write $A_{n}=\mathcal{K}_{\theta(n)}$ for $n>0$, and
$A_{0}=\emptyset$.

The domain of $\mathcal{W}$ is all of ${\mathbb{N}}$. By Lemma 6.5 the
intersection operation on $\mathcal{W}$ is computable, i.e., there is a
computable binary function $c$ on ${\mathbb{N}}$ such that
$A_{c(n,k)}=A_{n}\cap A_{k}$. Next, given $n,k\in{\mathbb{N}}-\\{0\\}$ one can
decide whether $A_{n}$ is a right coset of the same subgroup that $A_{k}$ is a
left coset of. In that case, one can compute the number $r$ such that
$A_{r}=A_{n}\cdot A_{k}$: one uses that $A_{r}$ is the unique coset $C$ such
that

  * (a)

$A_{n}A_{k}\subseteq C$, and

  * (b)

$C$ is a right coset of the same subgroup that $A_{k}$ is a right coset of.

For subgroups $U,V$, one can compute $|U\colon U\cap V|$ by finding in
$\mathcal{W}$ further and further distinct left cosets of $U\cap V$ contained
in $U$, until their union reaches $U$. The latter condition is decidable. ∎

######  Definition 9.8.

Given a computable Baire presentation $G$, by $\mathcal{W}_{\text{comp}}(G)$
we denote the computable copy of $\mathcal{W}(G)$ with domain ${\mathbb{N}}$
obtained in the proof above.

######  Corollary 9.9.

In this context, the left and right actions
$[T]\times{\mathbb{N}}\to{\mathbb{N}}$, given by $(g,A)\mapsto gA$ and
$(g,A)\mapsto Ag$, are computable.

###### Proof.

For the left action, we use an oracle Turing machine that has as an oracle a
path $g$ on $[T]$, and as an input an $A\in\mathcal{W}$. If $A$ is a left
coset of a subgroup $V$, it outputs the left coset $B$ of $V$ such that it can
find a string $\sigma\prec g$ with $[\sigma]_{T}A\subseteq B$.

For the right action use that $Ag=(g^{-1}A^{-1})^{-1}$ and inversion is
computable both in $G$ and in $\mathcal{W}_{\text{comp}}(G)$. ∎

Recall from the introduction that $\mathrm{Aut}(T_{d})$ is the group of
automorphism of the undirected tree $T_{d}$ where each vertex has degree $d$.

######  Example 9.10.

Let $d\geq 3$. The t.d.l.c. group $G=\text{Aut}(T_{d})$ has a computable Baire
presentation.

###### Proof.

Via an effective encoding of the vertices of $T_{d}$ by the natural numbers,
we can view $G$ itself as a closed subgroup of $S(\omega)$. A finite injection
$\alpha$ on $T_{d}$ can be extended to an automorphism of $T_{d}$ iff it
preserves distances, which is a decidable condition. Each
$\eta\in\mathit{Tree}(S(\omega))$ corresponds to an injection on $T_{d}$ via
(9.1). So we can decide whether
$[\eta]_{\mathit{Tree}(G)}=[\eta]_{\mathit{Tree}(S(\omega))}\cap
G\neq\emptyset$. Clearly $[\eta]_{\mathit{Tree}(G)}$ is compact for _every_
such nonempty string $\eta$.

To see that $\mathit{Tree}(G)$ is c.l.c., note that if
$\sigma\in\mathit{Tree}(G)$ maps $x\in T_{d}$ to $y\in T_{d}$, then every
extension $\eta\in\mathit{Tree}(G)$ of $\sigma$ maps elements in $T_{d}$ at
distance $n$ from $x$ to elements in $T_{d}$ at distance $n$ from $y$, and
conversely. This yields a computable bound $H(\sigma,i)$ as required in (3) of
Def. 6.3. ∎

###  10\. Algorithmic properties of objects associated with a t.d.l.c. group

####  10.1. The modular function is computable

In Subsection 5.6 we discussed the modular function $\Delta\colon
G\to{\mathbb{R}}^{+}$. As an application of 9.9, we show that for any
computable presentation, the modular function is computable.

######  Corollary 10.1.

Let $G$ be computably t.d.l.c. via a Baire presentation $([T],\text{\it
Mult},\text{\it Inv})$. Then the modular function
$\Delta\colon[T]\to{\mathbb{Q}}^{+}$ is computable.

###### Proof.

Let $V\in\mathcal{W}$ be any subgroup. Given $g\in[T]$, using 9.9 compute
$A=gV$. Compute $U\in\mathcal{W}$ such that $A$ is a right coset of $U$, and
hence $A=Ug$. For any left Haar measure $\mu$ on $G$, we have

$\Delta(g)=\mu(A)/\mu(U)=\mu(V)/\mu(U)$.

By Remark 8.10 we can choose $\mu$ computable; so this suffices to determine
$\Delta(g)$. ∎

####  10.2. Cayley-Abels graphs are computable

Let $G$ be a t.d.l.c. group that is compactly generated, i.e., algebraically
generated by a compact subset. Then there is a compact open subgroup $U$, and
a set $S=\\{s_{1},\ldots,s_{k}\\}\subseteq G$ such that $S=S^{-1}$ and $U\cup
S$ algebraically generates $G$. The _Cayley-Abels graph_

$\Gamma_{S,U}=(V_{S,U},E_{S,U})$

of $G$ is given as follows. The vertex set $V_{S,U}$ is the set $L(U)$ of left
cosets of $U$, and the edge relation is

$E_{S,U}=\\{\langle gU,gsU\rangle\colon\,g\in G,s\in S\\}$.

Some background and original references are given in Section 5 of [43]. For
more detailed background see Part 4 of [40], or [18, Section 2]. If $G$ is
discrete (and hence finitely generated), then $\Gamma_{S,\\{1\\}}$ is the
usual Cayley graph for the generating set $S$. Any two Cayley-Abels graphs of
$G$ is are quasi-isometric. See [18, Def. 3] or [40] for the formal
definition.

######  Theorem 10.2.

Suppose that $G$ is computably t.d.l.c. and compactly generated.

  * (i)

Each Cayley-Abels graph $\Gamma_{S,U}$ of $G$ has a computable copy
$\mathcal{L}$.

  * (ii)

If $\Gamma_{T,V}$ is another Cayley-Abels graph obtained as above, then
$\Gamma_{S,U}$ and $\Gamma_{T,V}$ are computably quasi-isometric.

###### Proof.

(i) For the domain of the computable copy $\mathcal{L}$, we take the
computable set of left cosets of $U$. We show that the edge relation is first-
order definable from the parameters in such a way that it can be verified to
be computable as well.

Let $V_{i}=C_{i}\cdot C_{i}^{-1}$ so that $C_{i}$ is a right coset of $V_{i}$.
Let $V=U\cap\bigcap_{1\leq i\leq k}V_{i}$. To first-order define $E_{\Gamma}$
in $\mathcal{W}$ with the given parameters, the idea is to replace the
elements $g$ in the definition of $E_{\Gamma}$ by left cosets $P$ of $V$,
since they are sufficiently accurate approximations to $g$. It is easy to
verify that $\langle A,B\rangle\in E_{\Gamma}$ $\Leftrightarrow$

$\exists i\leq k\exists P\in L(V)\exists Q\in L(V_{i})\,[P\subseteq
A\,\land\,P\subseteq Q\,\land\,B=Q\cdot C_{i}]$,

where $L(U)$ denotes the set of left cosets of a subgroup $U$: For the
implication “$\Leftarrow$”, let $g\in P$; then we have $A=gU$ and $B=gs_{i}U$.
For the implication “$\Rightarrow$”, given $A=gU$ and $B=gs_{i}U$, let $P\in
L(V)$ such that $g\in P$.

We verify that the edge relation $E_{\Gamma}$ is computable. Since
$\mathcal{W}$ is Haar computable, by the usual enumeration argument we can
obtain a strong index for the set of left cosets of $V$ contained in $A$.
Given $P$ in this set and $i\leq k$, the left coset $Q=Q_{P,i}$ of $V_{i}$ in
the expression above is unique and can be determined effectively. So we can
test whether $\langle A,B\rangle\in E_{\Gamma}$ by trying all $P$ and all
$i\leq k$ and checking whether $B=Q_{P,i}\cdot C_{i}$.

(ii) (Sketch) First suppose that $V\subseteq U$. There is a computable map
$\psi\colon L(U)\to L(V)$ such that $\psi(A)\subseteq A$. The proof of [18,
Thm. 2+] shows that $\psi\colon\Gamma_{S,U}\to\Gamma_{T,V}$ is a quasi-
isometry. In the general case, let $R\subseteq G$ be a finite symmetric set
such that $(U\cap V)\cup R$ algebraically generates $G$. There are computable
quasi-isometries $\phi\colon\Gamma_{S,U}\to\Gamma_{R,U\cap V}$ and
$\psi\colon\Gamma_{T,V}\to\Gamma_{R,U\cap V}$ as above. There is a computable
quasi-isometry $\theta:\Gamma_{R,U\cap V}\to\Gamma_{T,V}$: given a vertex
$y\in L(U\cap V)$, let $x=\theta(y)$ be a vertex in $L(V)$ such that $\psi(x)$
is at distance at most $c$ from $y$, where $c$ is a constant for $\psi$ as
above. Then $\theta\circ\phi$ is a quasi-isometry as required. ∎

####  10.3. Algorithmic properties of the scale function

The scale function $s\colon G\to{\mathbb{N}}^{+}$ for a t.d.l.c. group $G$ was
introduced by Willis [41]. Recall that for a compact open subgroup $V$ of $G$
and an element $g\in G$ one defines $m(g,V)=|V^{g}\colon V\cap V^{g}|$, and

$s(g)=\min\\{m(g,V)\colon\,V\text{ is a compact open subgroup}\\}$.

Willis proved that the scale function is continuous, where ${\mathbb{N}}^{+}$
carries the discrete topology. He introduced the relation that a compact open
subgroup $V$ is _tidy for $g$_, and showed that this condition is equivalent
to being minimizing for $g$ in the sense that $s(g)=m(g,V)$. Möller [25] used
graph theoretic methods to show that $V$ is minimizing for $g$ if and only if
$m(g^{k},V)=m(g,V)^{k}$ for each $k\in{\mathbb{N}}$. He also derived the
“spectral radius formula”: for any compact open subgroup $U$, one has
$s(g)=\lim_{k}m(g^{k},U)^{1/k}$.

The following example is well-known ([43, Example 2]); we include it to show
that our framework is adequate as a general background for case-based
approaches to computability for t.d.l.c. groups used in earlier works.

######  Example 10.3 (with Stephan Tornier).

For $d\geq 3$, the scale function on $\operatorname{Aut}(T_{d})$ in the
computable presentation of Example 9.10 is computable.

###### Proof.

An automorphism $g$ of $T_{d}$ has exactly one of three types (see [9]):

  1. (1)

$g$ fixes a vertex $v$: then $s(g)=1$ because $g$ preserves the stabilizer of
$v$, which is a compact open subgroup.

  2. (2)

$g$ inverts an edge: then $s(g)=1$ because $g$ preserves the set-wise
stabilizer of the set of endpoints of this edge.

  3. (3)

$g$ translates along a geodesic (a subset of $T_{d}$ that is a homogeneous
tree of degree $2$): then $s(g)=(d-1)^{\ell}$ where $\ell$ is the length. To
see this, for $\ell=1$ one uses as a minimizing subgroup the compact open
subgroup of automorphisms that fix two given adjacent vertices on the axis.
For $\ell>1$ one uses that $s(r^{k})=s(r)^{k}$ for each $k$ and
$r\in\operatorname{Aut}(T_{d})$; see again [41].

The oracle Turing machine, with a path corresponding to
$g\in\operatorname{Aut}(T_{d})$ as an oracle, searches in parallel for a
witness to (1), a witness to (2), and a sufficiently long piece of the axis in
(3) so that the shift becomes “visible”. It then outputs the corresponding
value of the scale. ∎

For the rest of this section, fix a computable Baire presentation
$([T],\text{\it Mult},\text{\it Inv})$ of a t.d.l.c. group $G$ as in Def. 7.1.
Let $\mathcal{W}=\mathcal{W}_{\text{comp}}(G)$ be the Haar computable copy of
$\mathcal{W}(G)$ given by Definition 9.8. Recall that the domain of
$\mathcal{W}$ is ${\mathbb{N}}$. Via $\mathcal{W}$ we can identify compact
open cosets of $G$ with natural numbers. The following is immediate from 9.9.

######  Fact 10.4.

The function $m\colon[T]\times\mathcal{{\mathbb{N}}}\to{\mathbb{N}}$ (defined
to be $0$ if the second argument is not a subgroup) is computable.

It is of interest to study whether the scale function, seen as a function
$s\colon[T]\to{\mathbb{N}}$, is computable in the sense of Definition 6.7. We
note that neither Möller’s spectral radius formula, nor the tidying procedure
of Willis (see again [43]) allow to compute the scale in our sense.

The scale is computable if and only if one can algorithmically decide whether
a subgroup is mimimizing:

######  Fact 10.5.

The scale function on $[T]$ is computable $\Leftrightarrow$ the following
function $\Phi$ is computable in the sense of Def. 6.7: if $g\in[T]$ and $V$
is a compact open subgroup of $G$, then $\Phi(g,V)=1$ if $V$ is minimizing for
$g$; otherwise $\Phi(g,V)=0$.

###### Proof.

$\Rightarrow:$ An oracle Turing machine with oracle $g$ searches for the first
$V$ that is minimizing for $g$, and outputs $m(g,V)$.

$\Leftarrow:$ For oracle $g$, given input $V$ check whether $m(g,V)=s(g)$. If
so output $1$, otherwise $0$. ∎

We next provide a fact restricting the complexity of the scale function. We
say that a function $\Psi:[T]\to{\mathbb{N}}$ is _computably approximable from
above_ if there is a computable function
$\Theta:[T]\times{\mathbb{N}}\to{\mathbb{N}}$ such that
$\Theta(f,r)\geq\Theta(f,r+1)$ for each $f\in[T],r\in{\mathbb{N}}$, and

$\Psi(f)=k$ iff $\lim_{r}\Theta(f,r)=k$.

######  Fact 10.6.

The scale function is computably approximable from above.

###### Proof.

Let $\Theta(f,r)$ be the minimum value of $m(f,s)$ over all $s\leq r$. ∎

###  11\. Closure properties of the class of computably t.d.l.c. groups

All computable presentations in this section will be Baire presentations (see
Definition 7.1), and we will usually view a t.d.l.c. group $G$ concretely as a
computable Baire presentation. Extending the previous notation in the setting
of closed subgroups of $S(\omega)$, by $\mathit{Tree}(G)$ we denote the c.l.c.
tree underlying this computable Baire presentation. The following is
immediate.

######  Fact 11.1 (Computable closed subgroups).

Let $G$ be a computably t.d.l.c. group. Let $H$ be a closed subgroup of $G$
(so that $\mathit{Tree}(H)$ is a subtree of $\mathit{Tree}(G)$). Then $H$ is
computably t.d.l.c. via the Baire presentation based on the $\mathit{Tree}(H)$
(which is c.l.c.), with the operations of $G$ restricted to $H$.

For instance, consider the closed subgroups $U(F)$ of
$\operatorname{Aut}(T_{d})$, where $d\geq 3$ and $F$ is a subgroup of $S_{d}$,
introduced by Burger and Mozes [4]. By Example 9.10 together with the
preceding fact, each group $U(F)$ is computably t.d.l.c.

For another example, consider the computable Baire presentation of
$\operatorname{SL}_{2}({\mathbb{Q}}_{p})$ given by Example 7.2. Let $S$ be the
c.l.c. subtree of $T$ whose paths describe matrices of the form
$\begin{pmatrix}r&0\\\ 0&s\end{pmatrix}$ (so that $s=r^{-1}$). This yields a
computable Baire presentation of the group $({\mathbb{Q}}_{p}^{*},\cdot)$.

######  Example 11.2.

For each prime $p$ and $n\geq 2$, the group
$\operatorname{GL}_{n}({\mathbb{Q}}_{p})$ is computably t.d.l.c.

###### Proof.

We employ the embedding $F\colon GL_{n}({\mathbb{Q}}_{p})\to
SL_{n+1}({\mathbb{Q}}_{p})$ which extends a matrix $A$ to the matrix $B$ where
the new row and new column vanish except for the diagonal element (which
necessarily equals $(\det A)^{-1}$). Clearly there is a c.l.c. subtree $S$ of
the c.l.c. subtree of $T$ in Example 7.2 for $n+1$ such that
$[S]=\mathrm{range}(F)$. Now we apply 11.1. ∎

A further construction staying within the class of t.d.l.c. groups is the
semidirect product based on a continuous action. In the effective setting, we
use actions that are computable in the sense of Section 6.2.

######  Proposition 11.3 (Closure under computable semidirect products).

Let $G,H$ be computably t.d.l.c. groups. Suppose $\Phi\colon G\times H\to H$
is a computable function that specifies an action of $G$ on $H$ via
topological automorphisms. Then the topological semidirect product
$L=G\ltimes_{\Phi}H$ is computably t.d.l.c.

###### Proof.

Let $T$ be the tree obtained by pairing corresponding components of strings of
the same length from the trees of $G$ and $H$, i.e.

$T=\\{\sigma\otimes\tau\colon\,\sigma\in\mathit{Tree}(G)\,\land\,\tau\in\mathit{Tree}(H)\\}$.

It is clear that $T$ is a c.l.c. tree. Via the natural bijection

$[T]\to[\mathit{Tree}(G)]\times[\mathit{Tree}(H)]$,

one can write elements of $L$ in the form $\langle g,h\rangle$ where
$g\in[\mathit{Tree}(G)]$ and $h\in[\mathit{Tree}(H)]$.

By the standard definition of semidirect product ([33, p. 27]), writing the
operations for $G$ and $H$ in the usual group theoretic way, we have

$\displaystyle\text{\it Mult}(\langle g_{1},h_{1}\rangle,\langle
g_{2},h_{2}\rangle)$ $\displaystyle=$ $\displaystyle\langle
g_{1}g_{2},\Phi(g_{2},h_{1})h_{2}\rangle$ $\displaystyle\text{\it Inv}(\langle