André Nies
YOU?
Author Swipe
View article: Open Problems in Computability Theory and Descriptive Set Theory
Open Problems in Computability Theory and Descriptive Set Theory Open
These open problems were presented in the Problem Sessions held during the Tianyuan Workshop on Computability Theory and Descriptive Set Theory, June 16-20, 2025. The problems are organized into sections named after their contributors, in …
View article: Logic Blog 2023-2024
Logic Blog 2023-2024 Open
The logic blogs 2023 and 2024 have been joined. The present file contains a lot on particular classes of groups and their relationship with logic, as well as entries on ergodic theory and on foundations. There is also a bit on AI proving a…
View article: Fractal dimensions and profinite groups
Fractal dimensions and profinite groups Open
Let $T$ be a finitely branching rooted tree such that any node has at least two successors. The path space $[T]$ is an ultrametric space: for distinct paths $f,g$ let $d(f,g)= 1/|T_n|$, where $T_n$ denotes the $n$-th level of the tree, and…
View article: Oligomorphic groups, their automorphism groups, and the complexity of their isomorphism
Oligomorphic groups, their automorphism groups, and the complexity of their isomorphism Open
The paper follows two interconnected directions. 1. Let $G$ be a Roelcke precompact closed subgroup of the group $\Sym(ω)$ of permutations of the natural numbers. Then $\Inn(G)$ is closed in $\Aut(G)$, where $\Aut(G)$ carries the topology …
View article: Computably locally compact groups and their closed subgroups
Computably locally compact groups and their closed subgroups Open
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 subgrou…
View article: Martin–Löf reducibility and cost functions
Martin–Löf reducibility and cost functions Open
Martin-Löf (ML)-reducibility compares the complexity of K -trivial sets of natural numbers by examining the Martin-Löf random sequences that compute them. One says that a K -trivial set A is ML-reducible to a K -trivial set B if every ML-r…
View article: Word automatic groups of nilpotency class 2
Word automatic groups of nilpotency class 2 Open
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$-gro…
View article: Logic Blog 2022
Logic Blog 2022 Open
The 2022 logic blog has concentrated on the connections of group theory and logic. It discusses Gardam's 2021 refutation of the Higman/ Kaplansky unit conjecture, and its connections to logic and to computation. The rest is about topologic…
View article: Computably totally disconnected locally compact groups
Computably totally disconnected locally compact groups Open
We study totally disconnected, locally compact (t.d.l.c.) groups from an algorithmic perspective. We give various approaches to defining computable presentations of t.d.l.c.\ groups, and show their equivalence. In the process, we obtain an…
View article: Logic Blog 2021
Logic Blog 2021 Open
The blog has several entries on group theory interacting with computability and wider logic, several open questions, and an entry on undecidability in physics.
View article: Finite axiomatizability for profinite groups
Finite axiomatizability for profinite groups Open
A group is $\textit{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 k…
View article: FRAÏSSÉ LIMITS FOR RELATIONAL METRIC STRUCTURES
FRAÏSSÉ LIMITS FOR RELATIONAL METRIC STRUCTURES Open
The general theory developed by Ben Yaacov for metric structures provides Fraïssé limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an ex…
View article: Coarse groups, and the isomorphism problem for oligomorphic groups
Coarse groups, and the isomorphism problem for oligomorphic groups Open
Let [Formula: see text] denote the topological group of permutations of the natural numbers. A closed subgroup G of [Formula: see text] is called oligomorphic if for each n, its natural action on n-tuples of natural numbers has only finite…
View article: Maximal towers and ultrafilter bases in computability
Maximal towers and ultrafilter bases in computability Open
The tower number $\mathfrak t$ and the ultrafilter number $\mathfrak u$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of~$ω$ and the almost inclusion relation $\subseteq^*$ b…
View article: Computable topological abelian groups
Computable topological abelian groups Open
We study the algorithmic content of Pontryagin - van Kampen duality. We prove that the dualization is computable in the important cases of compact and locally compact totally disconnected Polish abelian groups. The applications of our main…
View article: Logic Blog 2020
Logic Blog 2020 Open
This year's blog has focused on the connections of group theory with logic and algorithms. The first post is on automata presentable groups. Then there are several posts related to topological groups, for instance Ivanov and Majcher showin…
View article: Finite axiomatizability for profinite groups
Finite axiomatizability for profinite groups Open
A group is finitely axiomatizable (FA) in a class 𝒞 if it can be determined up to isomorphism within 𝒞 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 profini…
View article: MUCHNIK DEGREES AND CARDINAL CHARACTERISTICS
MUCHNIK DEGREES AND CARDINAL CHARACTERISTICS Open
A mass problem is a set of functions $\omega \to \omega $ . For mass problems ${\mathcal {C}}, {\mathcal {D}}$ , one says that ${\mathcal {C}}$ is Muchnik reducible to ${\mathcal {D}}$ if each function in ${\mathcal {C}}$ is computed by a …
View article: RANDOMNESS NOTIONS AND REVERSE MATHEMATICS
RANDOMNESS NOTIONS AND REVERSE MATHEMATICS Open
We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$ -random relative to Z . We show that the equivalence between 2-randomness an…
View article: Finite axiomatizability for profinite groups I: group theory
Finite axiomatizability for profinite groups I: group theory Open
A group is $\textit{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 k…
View article: Computing from projections of random points
Computing from projections of random points Open
We study the sets that are computable from both halves of some (Martin–Löf) random sequence, which we call [Formula: see text]-bases. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.…
View article: The Scott rank of Polish metric spaces
The Scott rank of Polish metric spaces Open
We study the usual notion of Scott rank but in the setting of Polish metric spaces. The signature consists of distance relations: for each rational $q > 0$, there is a relation $R_{
View article: Oligomorphic groups are essentially countable
Oligomorphic groups are essentially countable Open
We study the complexity of the isomorphism relation on classes of closed subgroups of $S_\infty$, the group of permutations of the natural numbers. We use the setting of Borel reducibility between equivalence relations on Polish spaces.
…
View article: Logic Blog 2018
Logic Blog 2018 Open
Some notions from algorithmic randomness are extended to measures and to quantum states. There is a lot on group theory and its relation to logic. This includes some new results on oligomorphic groups. There's also metric spaces and Scott …
View article: Randomness and initial segment complexity for probability measures
Randomness and initial segment complexity for probability measures Open
We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure $μ$ on the space of infinite bit sequences is ML absolutely continuous if the non-ML-random bit sequences form a null set with respe…
View article: A weak randomness notion for probability measures
A weak randomness notion for probability measures Open
We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure $\mu$ on the space of infinite bit sequences is ML absolutely continuous if the non-ML-random bit sequences form a null set with res…
View article: Logic Blog 2017
Logic Blog 2017 Open
The blog is somewhat shorter than in previous years, It contains new insights in a variety of areas, including computability, quantum algorithmic version of the SMB theorem, descriptions of groups (both discrete and profinite), metric spac…