Algorithmic problems in groups with quadratic Dehn function

Word problems, etc. in computability and recursion theory (03D40) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65)

Review text

A group given by a presentation \(G=\langle X \mid \mathcal{R} \rangle\) is a factor group \(F/N\) of the free group \(F=F(X)\) with the set of free generators \(X\) over the normal closure \(\langle \mathcal{R} \rangle^{F}\) of the set of relators \(\mathcal{R}\). Therefore every word \(w\) over the alphabet \(X^{\pm 1}\) vanishing in \(G\) represents an element of \(N\), and so in \(F\), \(w\) is a product \(v_{1} \cdot \ldots \cdot v_{m}\) of factors \(v_{i}=u_{i}r_{i}^{\pm 1} u_{i}^{-1}\) which are conjugates of the relators \(r_{i} \in \mathcal{R}\) or their inverses. The minimal number of factors \(m=m(w)\) is called the area of the word \(w\) with respect to the presentation \(G=\langle X \mid \mathcal{R} \rangle\). The Dehn function of a finitely presented group \(G=\langle X \mid \mathcal{R} \rangle\) is the smallest function \(f(n)\) such that for every word \(w\) of length at most \(n\) in the alphabet \(X^{\pm 1}\), which is equal to 1 in \(G\), the area of \(w\) is at most \(f(n)\). A finitely presented group is hyperbolic if and only if it has a subquadratic (hence linear) Dehn function and consequently the conjugacy problem in such groups is decidable [\textit{M. Gromov}, Publ., Math. Sci. Res. Inst. 8, 75--263 (1987; Zbl 0634.20015)]. The affirmative solution of the isomorphism problem was obtained in [\textit{F. Dahmani} and \textit{V. Guirardel}, Geom. Funct. Anal. 21, No. 2, 223--300 (2011; Zbl 1258.20034)] for the class of all hyperbolic groups. This means that there exists an algorithm recognizing whether two hyperbolic groups \(G_{1}\) and \(G_{2}\) are isomorphic or not, provided \(G_{1}\) and \(G_{2}\) are given by their finite presentations. A first important result proved in this paper is Theorem 1.1: In the class \textsf{QD} of finitely presented groups with quadratic Dehn function, the isomorphism problem is undecidable. Moreover, one can select a \textsf{QD}-group \(\overline{G}\) such that there exists no algorithm deciding whether a \textsf{QD}-group \(G\) and \(\overline{G}\) are isomorphic or not. It is known that the Dehn function of a finitely presented subgroup can grow faster than the Dehn function of the entire group. For example, the group \(\mathrm{SL}(5,\mathbb{Z})\) has quadratic Dehn function, but it contains subgroups with exponential Dehn function. The authors prove Theorem 1.2: For every recursive function \(f\), there exists a pair of finitely presented groups \(H \leq G\), such that \(f \preceq d_{H}\), where \(d_{H}\) is the Dehn function of the subgroup \(H\), while the Dehn function of \(G\) is quadratic. Theorem 1.3 contains two extremely interesting results: (1) There is a finitely presented group \(G\) with undecidable conjugacy problem but decidable power conjugacy problem. Moreover, \(G\) has quadratic Dehn function. (2) There is a finitely presented group \(H\) with undecidable power conjugacy problem but decidable conjugacy problem.

Recommendations

Cites work

Cited in

(10)

Describes a project that uses

Uses Software

thompson

This page was built for publication: Algorithmic problems in groups with quadratic Dehn function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2694791)