| Andre Nies: publications |
We prove that the relation of topological isomorphism on procountable groups is not classifiable by countable structures, in the sense of descriptive set theory. In fact, the equivalence relation $\ell_\infty$ that expresses that two sequences of reals have bounded difference is Borel reducible to it. This marks progress on an open problem to determine the exact complexity of isomorphism among all non-archimedean Polish groups.
We prove that the epimorphism relation is a complete analytic quasi-order on the space of countable groups. In the process we obtain a result of independent interest showing that the epimorphism relation on pointed reflexive graphs is complete.
The paper establishes results following two interconnected directions.
[1.] Let $G$ be a Roelcke precompact closed subgroup of the group $\mathrm{Sym}(\omega)$ of permutations of the natural numbers. Then $\mathrm{Inn}(G)$ is closed in $\mathrm{Aut}(G)$, where $\mathrm{Aut}(G)$ carries the topology of pointwise convergence for its (faithful) action on the cosets of open subgroups. Under the stronger hypothesis that $G$ is oligomorphic, $N_G/G$ is profinite, where $N_G$ denotes the normaliser of $G$ in $\mathrm{Sym}(\omega)$, and the topological group $\mathrm{Out}(G)= \mathrm{Aut}(G)/\mathrm{Inn}(G)$ is totally disconnected, locally compact.
[2a.] We provide a general method to show smoothness of the isomorphism relation for appropriate Borel classes of oligomorphic groups. We apply it to two such classes: the oligomorphic groups with no algebraicity, and the oligomorphic groups with finitely many {essential} subgroups up to conjugacy.
[2b.] Using this method we also show that if $G$ is in such a Borel class, then $\mathrm{Aut}(G)$ is topologically isomorphic to an oligomorphic group, and $\mathrm{Out}(G)$ is profinite.
Let $\mathrm{Aut}(G)$ denote the group of (bi-)continuous automorphisms (and $\mathrm{Out}(G)$ the outer automorphism group) of a non-Archimedean Polish group $G$. We show that for any such $G$ with an invariant countable basis of open subgroups, the group $\mathrm{Aut}(G)$ carries a unique Polish topology making its natural action on $G$ continuous. Furthermore, for any class of groups allowing a Borel assignment of such bases, there is a functorial duality to a class of countable groupoids with a meet operation, extending prior work on coarse groups and isomorphism problems. This provides an alternative description of the topology of $\mathrm{Aut}(G)$, and holds for classes including locally Roelcke precompact non-Archimedean groups. We also give a model-theoretic proof that the outer automorphism group $\mathrm{Out}(G)$ of an oligomorphic group $G$ is locally compact.
Given a computably locally compact Polish space $M$, we show that its 1-point compactification $M^*$ is computably compact. Then, for a computably locally compact group $G$, we show that the Chabauty space $\mathcal S(G)$ of closed subgroups of $G$ has a canonical effectively-closed (i.e., $\Pi^0_1$) presentation as a subspace of the hyperspace $\mathcal K(G^*)$ of closed sets of $G^*$. We construct a computable discrete abelian group $H$ such that $\mathcal S(H)$ is not computably closed in $\mathcal K(H^*)$; in fact, the only computable points of $\mathcal S(H)$ are the trivial group and $H$ itself, while $\mathcal S(H)$ is uncountable. In the case that a computably locally compact group $G$ is also totally disconnected, we provide a further algorithmic characterization of $\mathcal S(G)$ in terms of the countable meet groupoid of $G$ introduced recently by the authors (arXiv: 2204.09878). We apply our results and techniques to show that the index set of the computable locally compact abelian groups that contain a closed subgroup isomorphic to $(\mathbb{R},+)$ is arithmetical.
Let $T$ be a finitely branching rooted tree where each node has at least two successors, and let $[T]$ be its path space with the natural ultrametric. For a subtree $S$ of $T$ that is level-wise uniformly branching, the Hausdorff and lower box dimensions of $[S]$ coincide, and so do the packing and upper box dimensions. Geometric proofs are given, as well as ones based on point-to-set principles. These results are applied to rederive a theorem of Barnea and Shalev on the fractal dimensions of closed subgroups of a profinite group $G$, using the canonical path space coming from an inverse system for $G$.
We consider word automaticity for groups that are nilpotent of class $2$ and have exponent a prime $p$. We show that the infinitely generated free group in this variety is not word automatic. In contrast, the infinite extra-special $p$-group $E_p$ is word automatic, as well as an intermediate group $H_p$ which has an infinite centre. In the last section we introduce a method for showing automaticity of central extensions of abelian groups via co-cycles.
We investigate totally disconnected locally compact (t.d.l.c.) groups with a computable presentation. We show how to effectively encode the group structure so that operations and the local compactness topology are algorithmically accessible. In particular, we describe computable analogues of compact open subgroups and show how to uniformly compute the closure of finitely generated subgroups. Applications include algorithmic analysis of group actions on trees and connections to computable profinite groups.
A group is finitely axiomatizable (FA) in a class $\mathcal{C}$ if it can be determined up to isomorphism within $\mathcal{C}$ by a sentence in the first-order language of group theory. We show that profinite groups of various kinds are FA in the class of profinite groups, as well as in the pro-$p$ groups for some prime~$p$. We develop both algebraic and model-theoretic method to show such results. Reasons why certain groups cannot be FA are also discussed.
We examine computable presentations of topological abelian groups. In particular, we focus on countable abelian Polish groups and investigate which subgroup structures, homomorphisms, and topological features can be effectively represented. We establish criteria under which certain operations (like completion or dualization) preserve computability. Applications include $\mathbb{Z}$-modules, profinite abelian groups, and algorithmic treatment of Pontryagin duality.
Let $S_\infty$ denote the topological group of permutations of the natural numbers. A closed subgroup $G$ of $S_\infty$ is called \emph{oligomorphic} if for each $n$, its natural action on $n$-tuples of natural numbers has only finitely many orbits. We study the complexity of the topological isomorphism relation on the oligomorphic subgroups of $S_\infty$ in the setting of Borel reducibility between equivalence relations on Polish spaces.
Given a closed subgroup $G$ of $S_\infty$, the \emph{coarse group} $\mathcal M(G)$ is the structure with domain the cosets of open subgroups of $G$, and a ternary relation $AB \sub C$. This structure derived from $G$ was introduced in \cite[Section 3.3]{Kechris.Nies.etal:18}. % Section 3.3 of Kechris, Nies and Tent, \emph{The complexity of topological group isomorphism}, % Journal of Symbolic Logic, 83 (2018). If $G$ has only countably many open subgroups, then $\mathcal M(G)$ is a countable structure. Coarse groups form our main tool in studying such closed subgroups of $S_\infty$. We axiomatise them abstractly as structures with a ternary relation. For the oligomorphic groups, and also the profinite groups, we set up a Stone-type duality between the groups and the corresponding coarse groups. In particular we can recover an isomorphic copy of~$G$ from its coarse group in a Borel fashion.
We use this duality to show that the isomorphism relation for oligomorphic subgroups of $S_\infty$ is Borel reducible to a Borel equivalence relation with all classes countable. We show that the same upper bound applies to the larger class of closed subgroups of $S_\infty$ that are topologically isomorphic to oligomorphic groups.
We extend Fraïssé theory to relational metric structures, including continuous structures and finite metric spaces. Conditions for existence, uniqueness, and universality of Fraïssé limits are established, along with amalgamation techniques. We provide explicit constructions and analyze automorphism groups of the limits, showing connections to topological and descriptive set-theoretic properties.
We apply methods of computable structure theory to study effectively closed subgroups of $S_\infty$. The main result of the paper says that there exists an effectively closed presentation of $\mathbb{Z}_2$ which is not the automorphism group of any computable structure $M$. In contrast, we show that every effectively closed discrete group is topologically isomorphic to $\Aut(M)$ for some computable structure $M$. We also prove that there exists an effectively closed compact (thus, profinite) subgroup of $S_\infty$ that has no computable Polish presentation. In contrast, every profinite computable Polish group is topologically isomorphic to an effectively closed subgroup of $S_\infty$. We also look at oligomorphic subgroups of $S_\infty$; we construct a $\Sigma^1_1$ closed oligomorphic group in which the orbit equivalence relation is not uniformly HYP. Our proofs rely on methods of computable analysis, techniques of computable structure theory, elements of higher recursion theory, and the priority method.
We study the Borel complexity of the isomorphism relation for various classes of topological groups. In particular, we analyze non-Archimedean Polish groups and oligomorphic groups, showing that the isomorphism problem can be complete at the analytic level. Methods involve descriptive set theory, combinatorial group theory, and connections to automorphism groups of countable structures.