CS Paper Radar

Conjugacy problems in higher-dimensional Thompson groups

Ville Salo

cs.FL math.GRmath.DS ·submitted 2026-10-08 02:50 UTC · v1
theory

Abstract

We prove that topological conjugacy of elements of the Brin--Thompson group $nV$ is undecidable for every $n\geq2$. From a Turing machine $T$, the reduction produces two elements of $nV$, which are conjugate by an involution in $nV$ if $T$ halts on the empty tape. If $T$ does not halt on the empty tape, the topological dynamics of the two group elements are distinguished by their visits to minimal subsystems of the set of (germ-)aperiodic points. In these groups, and any finitely-generated supergroups inside the homeomorphism group of Cantor space, we also obtain undecidability of the Whitehead problem (the problem of being in the same automorphism orbit), and undecidability of group-theoretic conjugacy.

Comment
17 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Conjugator Length in Iterated Cyclic Amalgams of Free Groups

cs.DM math.GR ·2026-09-17 ·Conan Gillis
similarity 0.55
Abstract · Includes appendix by author

Let $\mathcal{A}_0$ be the set of finitely generated free groups on some countable alphabet and and define $\mathcal{A}_r$ inductively as the union of $\mathcal{A}_{r-1}$ with the set of amalgamated free products $G_1\ast_{\ZZ}G_2$, where $G_1,G_2\in \mathcal{A}_{r-1}$. We show, for all $r$, that every element of $\mathcal{A}_r$ has linear conjugator length, quantifying a result of Larsen and extending a result of Kharlampovich and Myasnikov. This is achieved by a linear conjugator length bound on a family of iterated HNN extensions of free groups. Also, in an appendix, we adapt a proof of A. Wei$ß$ to show that all Generalized Baumslag-Solitar Groups have linear conjugator length. As a consequence, we obtain that one-relator groups with non-trivial center have linear conjugator length, giving evidence for a conjecture of Bridson, Riley, and Sale.

0.20

Strong Transitivity of Group Cellular Automata: Characterization and Decidability

cs.DM cs.FLmath.DS ·2026-11-17 ·Niccolò Castronuovo, Alberto Dennunzio, Luciano Margara
theory similarity 0.54
Abstract

A discrete-time dynamical system is strongly transitive if every point can be reached, in finitely many steps, from every non-empty open set. We study this property for group cellular automata, \ie cellular automata over a finite group alphabet whose global map is a group endomorphism, in every dimension $d\geq1$. We prove that no group cellular automaton over a non-abelian group is strongly transitive, and we develop a decomposition of group cellular automata over abelian groups, via quotients by power subgroups, which preserves strong transitivity. For linear cellular automata over $(\mathbb Z/p\mathbb Z)^n$ we use Pontryagin duality to characterize strong transitivity in terms of the characteristic polynomial $χ_A$ of the associated matrix $A$ of Laurent polynomials: the automaton is strongly transitive if and only if $\det(A)\neq0$ and no irreducible factor of $χ_A$ has an invertible constant term. Combining these results, we obtain that strong transitivity is decidable for group cellular automata in every dimension. For every fixed dimension $d$, we give an explicit decision procedure whose running time is polynomial in the group size $N$, the number $k$ of neighbours, and the neighbourhood radius $\varrho$.

0.34

A characterization of the reversibility of linear cellular automata

cs.FL math.GRmath.DS ·2026-08-20 ·Alonso Castillo-Ramirez
theoryunusual similarity 0.53
Abstract · 10 pages

Let $G$ be a group, let $\mathbb{K}$ be a field, and let $V$ be a $\mathbb{K}$-vector space. We prove that there exists a bijective linear cellular automaton $V^G\to V^G$ whose inverse is not a cellular automaton if and only if $G$ is not locally finite and $\dim_{\mathbb{K}}V \geq |\mathbb{K}|^{\aleph_0}$. In particular, $|\mathbb{K}|^{\aleph_0}$ is the exact dimension threshold for non-reversibility. This answers an open problem proposed by T. Ceccherini-Silberstein and M. Coornaert.

0.30

Subgroup and Submonoid Membership in the lampshuffler of $\mathbb{Z}$

cs.DM math.GR ·2026-10-05 ·Corentin Bodart, Ruiwen Dong
top venuetheory similarity 0.52
Abstract · appears in SODA'27

The lampshuffler group of $\mathbb{Z}$ is the semidirect product $\operatorname{FSym}(\mathbb{Z}) \rtimes \mathbb{Z}$, which consists of all permutations of $\mathbb{Z}$ that act as a translation outside a finite set. This infinite permutation group naturally contains as subgroups the wreath products $H \wr \mathbb{Z}$ for every finite group $H$. We prove that the Subgroup Membership Problem, and more generally, the Submonoid Membership Problem, are decidable in $\operatorname{FSym}(\mathbb{Z}) \rtimes \mathbb{Z}$. Our proof reduces Subgroup and Submonoid Membership in $\operatorname{FSym}(\mathbb{Z}) \rtimes \mathbb{Z}$ to Subgroup Membership in the wreath products $H \wr \mathbb{Z}$, which was shown to be decidable by Lohrey, Steinberg and Zetzsche (2015).

0.28

Functorial Analysis of Group-Alphabet Cellular Automata

cs.FL math.GRmath.COmath.CT+1 ·2026-10-29 ·François Huard, Nathan Dion Larivière
similarity 0.51
Abstract

Let $G$ be a group and let $n\in\mathbb N$. We consider one-dimensional cellular automata of length $n$ over the alphabet $G$, with periodic boundary conditions and with local rules $φ$ given by words. We construct a functor $F$ from $\mathbf{Grp}$, the category of groups (or any similar algebraic structure), to the category of pointed digraphs, and show its faithfulness. We introduce the image category $\mathcal C_{n,φ}$ of state transition graphs of all such group-alphabet cellular automata, and show $F$ is an equivalence onto this category. Consequently we investigate the translation of categorical structures in $\mathbf{Grp}$ in terms of automata, and give examples of how standard methods of homological algebra may now be applied to automata. Additionally, a graph-theoretical construction of the product in $\mathcal C_{n,φ}$ is given, together with a formula for cycle lengths and multiplicities in this product. When $G$ is abelian, further structural properties of state transition graphs follow, and we contrast these results with non-abelian counterexamples.

0.19

Conjugacy languages in free inverse monoids

cs.FL math.GR ·2026-08-11 ·André Carvalho, Ana-Catarina C. Monteiro
similarity 0.51
Abstract · preliminary version, 24 pages

We initiate the study of conjugacy languages in free inverse monoids. Motivated by the notion of conjugacy languages in groups and the study of conjugacy in semigroups, we introduce the language of shortest representatives of conjugacy classes and study it for free inverse monoids of rank at least $2$ under the natural notion of conjugacy. We show that, contrary to the free group case, where this language is regular, in a free inverse monoid it is neither context-free nor co-context-free. In the monogenic case, this language is context-free. We show that this non-context-freeness comes from elements with nontrivial conjugacy classes. We define an equivalence relation as follows: all elements with a nontrivial conjugacy class are related and elements with trivial conjugacy class are only related to themselves. We call this relation $\mathrm{UConj}$. We show that the language consisting of geodesics representing elements whose conjugacy class is trivial is context-free by providing an explicit context-free grammar generating it. For groups, we show that the language of minimal representatives of $\mathrm{UConj}$ classes is regular if the group is hyperbolic and for right-angled Artin groups with the standard generating set, it is piecewise testable. For virtually abelian groups, we show that there is a generating set for which this language is piecewise excluding and exhibit an example of a virtually abelian group admitting a generating set for which this language is not regular.

0.10

Locally eventually onto cellular automata

cs.FL cs.DMmath.COmath.DS+1 ·2026-10-23 ·Jan Kristian Haugland, Nadia S. Larsen, Tron Omland, Henrikke G. Rustad
similarity 0.51
Abstract · 29 pages

We give a new checkable criterion to ensure that a one-dimensional cellular automaton on a finite alphabet is locally eventually onto. In this setting, openness is equivalent to being n-to-1 for some n and therefore implies surjectivity. Bipermutive cellular automata are known to be locally eventually onto, while open cellular automata that are neither bipermutive nor bijective appear to have received less attention. Building on Sutner's work with de Bruijn graphs, we describe a method for deciding openness and at the same time determining n. We then introduce the notion of block-regularity of local rules as a generalization of bipermutivity and prove that it implies openness. We further identify two conditions that, together with block-regularity, ensure that every nonempty cylinder set is mapped onto the whole configuration space after a finite number of iterations, and hence that the cellular automaton is locally eventually onto. The appendix provides the algorithms that check these finite criteria and then presents examples of locally eventually onto, non-bipermutive cellular automata for small diameters.

0.27

Topological Entropy of Group Cellular Automata is Effectively Computable

cs.CC math.DS ·2026-11-12 ·Niccolò Castronuovo, Alberto Dennunzio, Jarkko Kari, Luciano Margara
theory similarity 0.51
Abstract

Topological entropy is a fundamental invariant of dynamical systems, quantifying their complexity. For cellular automata, however, determining topological entropy is generally algorithmically intractable. We study group cellular automata, namely cellular automata over a finite group alphabet whose global map is a group endomorphism. In dimension one, we decompose topological entropy into two one-sided components describing information propagating from the left and from the right in space--time. We introduce finite families of left and right traces and prove that the entropy is the sum of their growth rates. Hence, the entropy is completely determined by the growth rate of a fixed-width family of space--time patterns. This reduction from arbitrarily large windows to uniformly bounded width yields an effective procedure for computing the entropy. In particular, the entropy of every one-dimensional group cellular automaton is the logarithm of a positive integer. Using Pontryagin duality and the Bridge Theorem between topological and algebraic entropy, we also derive an explicit formula for linear cellular automata over $(\mathbb{Z}/p\mathbb{Z})^n$ in terms of their characteristic polynomial. Moreover, in every dimension $D\geq 2$, a group cellular automaton is either equicontinuous with zero entropy or sensitive to initial conditions with infinite entropy. Combined with decidability of equicontinuity, this implies that topological entropy is effectively computable from the local rule in every dimension. Thus, group cellular automata form a natural nontrivial class in which algebraic structure restores computability of topological entropy.

0.22