Search

In this short survey we describe recent advances on word equations with non-rational constraints in groups and monoids, highlighting the important role that formal languages play in this area., Comment: 12 pages, to appear in the proceedings of DLT 2024. arXiv admin note: text overlap with arXiv:2204.13946

Indexed languages are a classical notion in formal language theory. As the language equivalent of second-order pushdown automata, they have received considerable attention in higher-order model checking. Unfortunately, counting properties are notoriously difficult to decide for indexed languages: So far, all results about non-regular counting properties show undecidability. In this paper, we initiate the study of slice closures of (Parikh images of) indexed languages. A slice is a set of vectors of natural numbers such that membership of $u,u+v,u+w$ implies membership of $u+v+w$. Our main result is that given an indexed language $L$, one can compute a semilinear representation of the smallest slice containing $L$'s Parikh image. We present two applications. First, one can compute the set of all affine relations satisfied by the Parikh image of an indexed language. In particular, this answers affirmatively a question by Kobayashi: Is it decidable whether in a given indexed language, every word has the same number of $a$'s as $b$'s. As a second application, we show decidability of (systems of) word equations with rational constraints and a class of counting constraints: These allow us to look for solutions where a counting function (defined by an automaton) is not zero. For example, one can decide whether a word equation with rational constraints has a solution where the number of occurrences of $a$ differs between variables $X$ and $Y$., Comment: 12 pages, accepted for publication at LICS 2024

In this paper we describe conjugacy geodesic representatives in any dihedral Artin group $G(m)$, $m\geq 3$, which we then use to calculate asymptotics for the conjugacy growth of $G(m)$, and show that the conjugacy growth series of $G(m)$ with respect to the `free product' generating set $\{x, y\}$ is transcendental. We prove two additional properties of $G(m)$ that connect to conjugacy, namely that the permutation conjugator length function is constant, and that the falsification by fellow traveler property (FFTP) holds with respect to $\{x, y\}$. These imply that the language of all conjugacy geodesics in $G(m)$ with respect to $\{x, y\}$ is regular.

In this paper we study the satisfiability and solutions of group equations when combinatorial, algebraic and language-theoretic constraints are imposed on the solutions. We show that the solutions to equations with length, lexicographic order, abelianisation or context-free constraints added, can be effectively produced in finitely generated virtually abelian groups. Crucially, we translate each of the constraints above into a rational set in an effective way, and so reduce each problem to solving equations with rational constraints, which is decidable and well understood in virtually abelian groups. A byproduct of our results is that the growth series of a virtually abelian group, with respect to any generating set and any weight, is effectively computable. This series is known to be rational by a result of Benson, but his proof is non-constructive., Comment: 28 pages

The survey provides an overview of the work done in the last 10 years to characterise solutions to equations in groups in terms of formal languages. We begin with the work of Ciobanu, Diekert and Elder, who showed that solutions to systems of equations in free groups in terms of reduced words are expressible as EDT0L languages. We provide a sketch of their algorithm, and describe how the free group results extend to hyperbolic groups. The characterisation of solutions as EDT0L languages is very robust, and many group constructions preserve this, as shown by Levine. The most recent progress in the area has been made for groups without negative curvature, such as virtually abelian, the integral Heisenberg group, or the soluble Baumslag-Solitar groups, where the approaches to describing the solutions are different from the negative curvature groups. In virtually abelian groups the solutions sets are in fact rational, and one can obtain them as $m$-regular sets. In the Heisenberg group producing the solutions to a single equation reduces to understanding the solutions to quadratic Diophantine equations and uses number theoretic techniques. In the Baumslag-Solitar groups the methods are combinatorial, and focus on the interplay of normal forms to solve particular classes of equations. In conclusion, EDT0L languages give an effective and simple combinatorial characterisation of sets of seemingly high complexity in many important classes of groups., Comment: 26 pages

Post's Correspondence Problem (the PCP) is a classical decision problem in theoretical computer science that asks whether for pairs of free monoid morphisms $g, h\colon\Sigma^*\to\Delta^*$ there exists any non-trivial $x\in\Sigma^*$ such that $g(x)=h(x)$. Post's Correspondence Problem for a group $\Gamma$ takes pairs of group homomorphisms $g, h\colon F(\Sigma)\to \Gamma$ instead, and similarly asks whether there exists an $x$ such that $g(x)=h(x)$ holds for non-elementary reasons. The restrictions imposed on $x$ in order to get non-elementary solutions lead to several interpretations of the problem; we consider the natural restriction asking that $x \notin \ker(g) \cap \ker(h)$ and prove that the resulting interpretation of the PCP is undecidable for arbitrary hyperbolic $\Gamma$, but decidable when $\Gamma$ is virtually nilpotent. We also study this problem for group constructions such as subgroups, direct products and finite extensions. This problem is equivalent to an interpretation due to Myasnikov, Nikolev and Ushakov when one map is injective., Comment: 20 pages, v2. Final version

In this paper we generalise and unify the results and methods used by Benson, Liardet, Evetts, and Evetts & Levine, to show that rational sets in a virtually abelian group G have rational (relative) growth series with respect to any generating set for G. We prove equivalences between the structures used in the literature, and establish the rationality of important classes of sets in G: definable sets, algebraic sets, conjugacy representatives and coset representatives (of any fixed subgroup), among others. Furthermore, we show that any rational set, when written as words over the generating set of G, has several EDT0L representations., Comment: 24 pages, 3 figures. To appear in L'Enseignement Mathematique

In this paper we begin the systematic study of group equations with abelian predicates in the main classes of groups where solving equations is possible. We extend the line of work on word equations with length constraints, and more generally, on extensions of the existential theory of semigroups, to the world of groups. We use interpretability by equations to establish model-theoretic and algebraic conditions which are sufficient to get undecidability. We apply our results to (non-abelian) right-angled Artin groups, and show that the problem of solving equations with abelian predicates is undecidable for these. We obtain the same result for hyperbolic groups whose abelianisation has torsion-free rank at least two. By contrast, we prove that in groups with finite abelianisation, the problem can be reduced to solving equations with recognisable constraints, and so this is decidable in right-angled Coxeter groups, or more generally, graph products of finite groups, as well as hyperbolic groups with finite abelianisation.

The Post Correspondence Problem is a classical decision problem about equalisers of free monoid homomorphisms. We prove connections between several variations of this classical problem, but in the setting of free groups and free group homomorphisms. Among other results, and working under certain injectivity assumptions, we prove that computing the rank of the equaliser of a pair of free group homomorphisms can be applied to computing a basis of this equaliser, and also to solve the "generalised" Post Correspondence Problem for free groups., Comment: 14 pages

In this paper we give a recursive formula for the conjugacy growth series of a graph product in terms of the conjugacy growth and standard growth series of subgraph products. We also show that the conjugacy and standard growth rates in a graph product are equal provided that this property holds for each vertex group. All results are obtained for the standard generating set consisting of the union of generating sets of the vertex groups., Comment: 33 pages

We give an algorithm which computes the fixed subgroup and the stable image for any endomorphism of the free group of rank two $F_2$, answering for $F_2$ a question posed by Stallings in 1984 and a question of Ventura., Comment: 34 pages

A marked free monoid morphism is a morphism for which the image of each generator starts with a different letter, and immersions are the analogous maps in free groups. We show that the (simultaneous) PCP is decidable for immersions of free groups, and provide an algorithm to compute bases for the sets, called equalisers, on which the immersions take the same values. We also answer a question of Stallings about the rank of the equaliser. Analogous results are proven for marked morphisms of free monoids., Comment: 16 pages, final version incorporating referees comments

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^2\log n)$ for the torsion-free case and NSPACE$(n^4\log 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., Comment: 33 pages, 3 figures, 1 table. Minor edits made. An extended abstract of a preliminary version of this paper was presented at the conference ICALP 2019 arXiv:1902.07349

In this paper we give asymptotics for the conjugacy growth of the soluble Baumslag-Solitar groups $BS(1,k)$, $k\geq 2$, with respect to the standard generating set, by providing a complete description of geodesic conjugacy representatives. We show that the conjugacy growth series for these groups are transcendental, and give formulas for the series. As a result of our computation we also establish that in each $BS(1,k)$ the conjugacy and standard growth rates are equal., Comment: 18 pages

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^2\log n)$ for the torsion-free case and $\mathsf{NSPACE}(n^4\log 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., Comment: 18 pages, 2 figures

In this note, we show that the satisfiability of equations and inequations with recognisable constraints is decidable in groups that are virtually direct products of finitely many hyperbolic groups., Comment: Dedicated to Charles Sims

In this paper we derive a generating series for the number of cellular complexes known as pavings or three-dimensional maps, on $n$ darts, thus solving an analogue of Tutte's problem in dimension three. The generating series we derive also counts free subgroups of index $n$ in $\Delta^+ = \mathbb{Z}_2*\mathbb{Z}_2*\mathbb{Z}_2$ via a simple bijection between pavings and finite index subgroups which can be deduced from the action of $\Delta^+$ on the cosets of a given subgroup. We then show that this generating series is non-holonomic. Furthermore, we provide and study the generating series for isomorphism classes of pavings, which correspond to conjugacy classes of free subgroups of finite index in $\Delta^+$. Computational experiments performed with software designed by the authors provide some statistics about the topology and combinatorics of pavings on $n\leq 16$ darts., Comment: 17 pages, 6 figures, 1 table; auxiliary files on GitHub: https://github.com/bottine/nem and https://github.com/sashakolpakov/monty-3d

In this paper we introduce and study the conjugacy ratio of a finitely generated group, which is the limit at infinity of the quotient of the conjugacy and standard growth functions. We conjecture that the conjugacy ratio is $0$ for all groups except the virtually abelian ones, and confirm this conjecture for certain residually finite groups of subexponential growth, hyperbolic groups, right-angled Artin groups, and the lamplighter group., Comment: 15 pages

We derive a generating series for the number of free subgroups of finite index in $\Delta^+ = \mathbb{Z}_p*\mathbb{Z}_q$ by using a connection between free subgroups of $\Delta^+$ and certain hypermaps (also known as ribbon graphs or "fat" graphs), and show that this generating series is transcendental. We provide non-linear recurrence relations for the above numbers based on differential equations that are part of the Riccati hierarchy. We also study the generating series for conjugacy classes of free subgroups of finite index in $\Delta^+$, which correspond to isomorphism classes of hypermaps. Asymptotic formulas are provided for the numbers of free subgroups of given finite index, conjugacy classes of such subgroups, or, equivalently, various types of hypermaps and their isomorphism classes., Comment: 27 pages, 3 figures; supplementary SAGE worksheets available at http://sashakolpakov.wordpress.com/list-of-papers/

L systems generalise context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives in the free group on two generators, the Bridson-Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk's group can be generated by L systems. To complement the result on primitives in free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L and ET0L languages of intermediate growth., Comment: Revised following referees suggestions. 21 pages, 2 figures

We prove that, for a finitely generated group hyperbolic relative to virtually abelian subgroups, the generalised word problem for a parabolic subgroup is the language of a real-time Turing machine. Then, for a hyperbolic group, we show that the generalised word problem for a quasiconvex subgroup is a real-time language under either of two additional hypotheses on the subgroup. By extending the Muller-Schupp theorem we show that the generalised word problem for a finitely generated subgroup of a finitely generated virtually free group is context-free. Conversely, we prove that a hyperbolic group must be virtually free if it has a torsion-free quasiconvex subgroup of infinite index with context-free generalised word problem., Comment: This paper includes all the material from the preprint The generalised word problem for subgroups of hyperbolic groups (Derek F Holt and Sarah Rees) previously deposited on the arXiv as arXiv:1505.02397, and citations of that article should be replaced by citations of this current one

Rivin conjectured that the conjugacy growth series of a hyperbolic group is rational if and only if the group is virtually cyclic. Ciobanu, Hermiller, Holt and Rees proved that the conjugacy growth series of a virtually cyclic group is rational. Here we present the proof confirming the other direction of the conjecture, by showing that the conjugacy growth series of a non-elementary hyperbolic group is transcendental. We also present and prove some variations of Rivin's conjecture for commensurability classes and primitive conjugacy classes. We then explore Rivin's conjecture for finitely generated acylindrically hyperbolic groups and prove a formal language version of it, namely that no set of minimal length conjugacy representatives can be unambiguous context-free., Comment: 26 pages, 2 figures. v2 Some typos corrected and section 6 slightly rearranged

We show that, given an equation over a finitely generated free group, the set of all solutions in reduced words forms an effectively constructible EDT0L language. In particular, the set of all solutions in reduced words is an indexed language in the sense of Aho. The language characterization we give, as well as further questions about the existence or finiteness of solutions, follow from our explicit construction of a finite directed graph which encodes all the solutions. Our result incorporates the recently invented recompression technique of Je\.z, and a new way to integrate solutions of linear Diophantine equations into the process. As a byproduct of our techniques, we improve the complexity from quadratic nondeterministic space in previous works to $\mathsf{NSPACE}(n\log n)$ here., Comment: 38 pages, 3 figures. A conference version of this paper was presented at ICALP 2015, Kyoto (Japan), July 4-10, 2015, see http://arxiv.org/abs/1502.03426

In this paper we exhibit two infinite families of trees $\{T^1_n\}_{n \geq 17}$ and $\{T^2_n\}_{n \geq 17}$ on $n$ vertices, such that $T^1_n$ and $T^2_n$ are non-isomorphic, co-spectral, and the right-angled Coxeter groups (RACGs) based on $T^1_n$ and $T^2_n$ have the same geodesic growth with respect to the standard generating set. We then show that the spectrum of a tree does is not sufficient to determine the geodesic growth of the RACG based on that tree, by providing two infinite families of trees $\{S^1_n\}_{n \geq 11}$ and $\{S^2_n\}_{n \geq 11}$, on $n$ vertices, such that $S^1_n$ and $S^2_n$ are non-isomorphic, co-spectral, and the right-angled Coxeter groups (RACGs) based on $S^1_n$ and $S^2_n$ have distinct geodesic growth. Asymptotically, as $n\rightarrow \infty$, each set $T^i_n$, or $S^i_n$, $i=1,2$, has the cardinality of the set of all trees on $n$ vertices. Our proofs are constructive and use two families of trees previously studied by B. McKay and C. Godsil., Comment: 14 pages, 4 figures, a typo in formula (3) corrected; supplementary material and a SAGE worksheet available at http://sashakolpakov.wordpress.com/list-of-papers/

We show that, given a word equation over a finitely generated free group, the set of all solutions in reduced words forms an EDT0L language. In particular, it is an indexed language in the sense of Aho. The question of whether a description of solution sets in reduced words as an indexed language is possible has been been open for some years, apparently without much hope that a positive answer could hold. Nevertheless, our answer goes far beyond: they are EDT0L, which is a proper subclass of indexed languages. We can additionally handle the existential theory of equations with rational constraints in free products $\star_{1 \leq i \leq s}F_i$, where each $F_i$ is either a free or finite group, or a free monoid with involution. In all cases the result is the same: the set of all solutions in reduced words is EDT0L. This was known only for quadratic word equations by Fert\'e, Marin and S\'enizergues (ToCS 2014), which is a very restricted case. Our general result became possible due to the recent recompression technique of Je\.z. In this paper we use a new method to integrate solutions of linear Diophantine equations into the process and obtain more general results than in the related paper (arXiv 1405.5133). For example, we improve the complexity from quadratic nondeterministic space in (arXiv 1405.5133) to quasi-linear nondeterministic space here. This implies an improved complexity for deciding the existential theory of non-abelian free groups: NSPACE($n\log n$). The conjectured complexity is NP, however, we believe that our results are optimal with respect to space complexity, independent of the conjectured NP., Comment: 37 pages, 2 figures

Given a finitely generated relatively hyperbolic group $G$, we construct a finite generating set $X$ of $G$ such that $(G,X)$ has the `falsification by fellow traveler property' provided that the parabolic subgroups $\{H_\omega\}_{\omega\in \Omega}$ have this property with respect to the generating sets $\{X\cap H_\omega\}_{\omega\in \Omega}$. This implies that groups hyperbolic relative to virtually abelian subgroups, which include all limit groups and groups acting freely on $\mathbb{R}^n$-trees, or geometrically finite hyperbolic groups, have generating sets for which the language of geodesics is regular, and the complete growth series and complete geodesic series are rational. As an application of our techniques, we prove that if each $H_\omega$ admits a geodesic biautomatic structure over $X\cap H_\omega$, then $G$ has a geodesic biautomatic structure. Similarly, we construct a finite generating set $X$ of $G$ such that $(G,X)$ has the `bounded conjugacy diagrams' property or the `neighbouring shorter conjugate' property if the parabolic subgroups $\{H_\omega\}_{\omega\in \Omega}$ have this property with respect to the generating sets $\{X\cap H_\omega\}_{\omega\in \Omega}$. This implies that a group hyperbolic relative to abelian subgroups has a generating set for which its Cayley graph has bounded conjugacy diagrams, a fact we use to give a cubic time algorithm to solve the conjugacy problem. Another corollary of our results is that groups hyperbolic relative to virtually abelian subgroups have a regular language of conjugacy geodesics., Comment: 44 pages, 8 figures. Version 3. After comments from the referee added

We study the regularity of several languages derived from conjugacy classes in a finitely generated group G for a variety of examples including word hyperbolic, virtually abelian, Artin, and Garside groups. We also determine the rationality of the growth series of the shortlex conjugacy language in virtually cyclic groups, proving one direction of a conjecture of Rivin., Comment: 29 pages

We prove that graph products of sofic groups are sofic, as are graphs of groups for which vertex groups are sofic and edge groups are amenable.

In [BB] Benjamin Baumslag proved that being fully residually free is equivalent to being residually free and commutative transitive (CT). Gaglione and Spellman [GS] and Remeslennikov [Re] showed that this is also equivalent to being universally free, that is, having the same universal theory as the class of nonabelian free groups. This result is one of the cornerstones of the proof of the Tarksi problems. In this paper we extend the class of groups for which Benjamin Baumslag's theorem is true, that is we consider classes of groups $\X$ for which being fully residually $\X$ is equivalent to being residually $\X$ and commutative transitive. We show that the classes of groups for which this is true is quite extensive and includes free products of cyclics not containing the infinite dihedral group, torsion-free hyperbolic groups (done in [KhM]), and one-relator groups with only odd torsion. Further, the class of groups having this property is closed under certain amalgam constructions, including free products and free products with malnormal amalgamated subgroups. We also consider extensions of these classes to classes where the equivalence with universally $\X$ groups is maintained., Comment: 11 pages

The general {\bf surface group conjecture} asks whether a one-relator group where every subgroup of finite index is again one-relator and every subgroup of infinite index is free (property IF) is a surface group. We resolve several related conjectures given in [FKMRR]. First we obtain the Surface Group Conjecture B for cyclically pinched and conjugacy pinched one-relator groups. That is: if $G$ is a cyclically pinched one-relator group or conjugacy pinched one-relator group satisfying property IF then $G$ is free, a surface group or a solvable Baumslag-Solitar Group. Further combining results in [FKMRR] on Property IF with a theorem of H. Wilton [W] and results of Stallings [St] and Kharlampovich and Myasnikov [KhM4] we show that Surface Group Conjecture C proposed in [FKMRR] is true, namely: If $G$ is a finitely generated nonfree freely indecomposable fully residually free group with property IF, then $G$ is a surface group., Comment: 10 pages

In this paper we introduce the geodesic conjugacy language and geodesic conjugacy growth series for a finitely generated group. We study the effects of various group constructions on rationality of both the geodesic conjugacy growth series and spherical conjugacy growth series, as well as on regularity of the geodesic conjugacy language and spherical conjugacy language. In particular, we show that regularity of the geodesic conjugacy language is preserved by the graph product construction, and rationality of the geodesic conjugacy growth series is preserved by both direct and free products.

The objective of this paper is to detect which combinatorial properties of a regular graph can completely determine the geodesic growth of the right-angled Coxeter or Artin group this graph defines, and to provide the first examples of right-angled and even Coxeter groups with the same geodesic growth series., Comment: 27 pages, 5 figures. Some typos and minor errors were corrected

We prove that many Artin groups of large type satisfy the rapid decay property, including all those of extra-large type. For many of these, including all 3-generator groups of extra-large type, a result of Lafforgue applies to show that the groups satisfy the Baum-Connes conjecture without coefficients. Our proof of rapid decay combines elementary analysis with combinatorial techniques, and relies on properties of geodesic words in Artin groups of large type that were observed in an earlier publication by two of the authors of this current article.

We prove that the rapid decay property (RD) of groups is preserved by graph products defined on finite simplicial graphs., Comment: 13 pages

Let $F$ be a group whose abelianization is $\Z^k$, $k\geq 2.$ An element of $F$ is called visible if its image in the abelianization is visible, that is, the greatest common divisor of its coordinates is 1. In this paper we compute three types of densities, annular, even and odd spherical, of visible elements in surface groups. We then use our results to show that the probability of a homogeneous equation in a surface group to have solutions is neither 0 nor 1, as the lengths of the right- and left-hand side of the equation go to infinity.

Let $F$ be a free group of finite rank. We say that the monomorphism problem in $F$ is decidable if for any two elements $u$ and $v$ in $F$, there is an algorithm that determines whether there exists a monomorphism of $F$ that sends $u$ to $v$. In this paper we show that the monomorphism problem is decidable and we provide an effective algorithm that solves the problem.