Algorithmic problems in groups with quadratic Dehn function (Q2694791): Difference between revisions

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.