Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe complexity of solution sets to equations in hyperbolic groups
109
0
0.0
(
0
)
Added by
Murray Elder
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), is an EDT0L language whose specification can be computed in NSPACE$(n^2log n)$ for the torsion-free case and NSPACE$(n^4log n)$ in the torsion case. Furthermore, in the presence of quasi-isometrically embeddable rational constraints, we show that the full set of solutions to systems of equations in a hyperbolic group remains EDT0L. Our work combines the geometric results of Rips, Sela, Dahmani and Guirardel on the decidability of the existential theory of hyperbolic groups with the work of computer scientists including Plandowski, Je.z, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.
rate research
Read More
We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language whose specification can be computed in $mathsf{NSPACE}(n^2log n)$ for the torsion-free case and $mathsf{NSPACE}(n^4log n)$ in the torsion case. Our work combines deep geometric results by Rips, Sela, Dahmani and Guirardel on decidability of existential theories of hyperbolic groups, work of computer scientists including Plandowski, Je.z, Diekert and others on $mathsf{PSPACE}$ algorithms to solve equations in free monoids and groups using compression, and an intricate language-theoretic analysis. The present work gives an essentially optimal formal language description for all solutions in all hyperbolic groups, and an explicit and surprising low space complexity to compute them.
We prove that for a one-ended hyperbolic graph $X$, the size of the quotient $X/G$ by a group $G$ acting freely and cocompactly bounds from below the number of simplices in an Eilenberg-MacLane space for $G$. We apply this theorem to show that one-ended hyperbolic cubulated groups (or more generally, one-ended hyperbolic groups with globally stable cylinders `a la Rips-Sela) cannot contain isomorphic finite-index subgroups of different indices.
We study conjugacy classes of solutions to systems of equations and inequations over torsion-free hyperbolic groups, and describe an algorithm to recognize whether or not there are finitely many conjugacy classes of solutions to such a system. The class of immutable subgroups of hyperbolic groups is introduced, which is fundamental to the study of equations in this context. We apply our results to enumerate the immutable subgroups of a torsion-free hyperbolic group.
Let $Gamma$ be a torsion-free hyperbolic group. We show that the set of solutions of any system of equations with one variable in $Gamma$ is a finite union of points and cosets of centralizers if and only if any two-generator subgroup of $Gamma$ is free.
Let $Gamma$ be a torsion-free hyperbolic group. We study $Gamma$--limit groups which, unlike the fundamental case in which $Gamma$ is free, may not be finitely presentable or geometrically tractable. We define model $Gamma$--limit groups, which always have good geometric properties (in particular, they are always relatively hyperbolic). Given a strict resolution of an arbitrary $Gamma$--limit group $L$, we canonically construct a strict resolution of a model $Gamma$--limit group, which encodes all homomorphisms $Lto Gamma$ that factor through the given resolution. We propose this as the correct framework in which to study $Gamma$--limit groups algorithmically. We enumerate all $Gamma$--limit groups in this framework.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
