Foliations for solving equations in groups: free, virtually free, and hyperbolic groups.

*(English)*Zbl 1217.20021An equation in a group \(G\) is an equality \(w=1\), where \(w\) is a word on a set of variables, and their inverses together with constants taken from \(G\), an inequation is an inequality \(w\neq 1\). The problem of equations and inequations in a group \(G\) consists in deciding algorithmically whether a system of equations and inequations with constants has a solution in \(G\) or not.

The problem of equations and inequations in a free group \(F\) has been solved by G. S. Makanin [in Izv. Akad. Nauk SSSR, Ser. Mat. 46, No. 6, 1199-1273 (1982; Zbl 0511.20019) and ibid. 48, No. 4, 735-749 (1984; Zbl 0578.20001)]. Since then many authors have been inspired by Makanin’s algorithm and problems in group theory are reduced to the solution of systems of equations and inequations in a free group. For example, [in Invent. Math. 120, No. 3, 489-512 (1995; Zbl 0845.57002)], E. Rips and Z. Sela obtained the solution to the equations problem in torsion-free hyperbolic groups by reducing it to the equations problem in a free group.

In the present paper the authors construct an algorithm which decides whether there exists a solution or not for a finite system of equations and inequations in a hyperbolic group (possibly with torsion).

Before quoting the main theorem we need some terminology. In a group \(G\), the class of rational subsets is the smallest class containing finite sets, and closed under finite union \(A\cup B\), product \(A\cdot B\), and semigroup generation \(A^*\). Solving a system of equations with rational constraints consists in solving this system with the requirement that each variable \(x\) lies in a rational subset given in advance.

Theorem: There exists an algorithm which takes the following input:

(i) A presentation of a hyperbolic group \(G\) (possibly with torsion);

(ii) A finite system of equations and inequations with constants in \(G\), and with quasi-isometrically embeddable rational constraints, and which decides whether there exists a solution or not.

For the definition of the quasi-isometrically embeddable rational subsets we refer to the Definition 9.2 in the paper.

Using canonical representatives introduced by Rips and Sela, [loc. cit.] and the machinery there and in [F. Dahmani, Isr. J. Math. 173, 91-124 (2009; Zbl 1189.20034)], the authors reduce the Theorem above to the equations problem in a virtually free group. To give a solution of the equations problem in virtually free groups they reduce it to a problem of twisted equations in a free group (Proposition 2.4 in the paper).

In a group \(G\) a twisted equation is an equation of the form \(\varphi_1(x_1)\cdots\varphi_n(x_n)=1\), where each \(\varphi_i\) is a fixed automorphism of \(G\), and \(x_i\) is a variable or a constant.

Here the authors need only the use of automorphisms of a free group \(F=\langle S\rangle\) which preserve the set \(S\cup S^{-1}\) (see Definition 2.2 in the paper) and prove that this problem of twisted equations is solvable. The solution is obtained approaching Makanin’s algorithm from the point of view of Rips’ theory for foliated band complexes.

The problem of equations and inequations in a free group \(F\) has been solved by G. S. Makanin [in Izv. Akad. Nauk SSSR, Ser. Mat. 46, No. 6, 1199-1273 (1982; Zbl 0511.20019) and ibid. 48, No. 4, 735-749 (1984; Zbl 0578.20001)]. Since then many authors have been inspired by Makanin’s algorithm and problems in group theory are reduced to the solution of systems of equations and inequations in a free group. For example, [in Invent. Math. 120, No. 3, 489-512 (1995; Zbl 0845.57002)], E. Rips and Z. Sela obtained the solution to the equations problem in torsion-free hyperbolic groups by reducing it to the equations problem in a free group.

In the present paper the authors construct an algorithm which decides whether there exists a solution or not for a finite system of equations and inequations in a hyperbolic group (possibly with torsion).

Before quoting the main theorem we need some terminology. In a group \(G\), the class of rational subsets is the smallest class containing finite sets, and closed under finite union \(A\cup B\), product \(A\cdot B\), and semigroup generation \(A^*\). Solving a system of equations with rational constraints consists in solving this system with the requirement that each variable \(x\) lies in a rational subset given in advance.

Theorem: There exists an algorithm which takes the following input:

(i) A presentation of a hyperbolic group \(G\) (possibly with torsion);

(ii) A finite system of equations and inequations with constants in \(G\), and with quasi-isometrically embeddable rational constraints, and which decides whether there exists a solution or not.

For the definition of the quasi-isometrically embeddable rational subsets we refer to the Definition 9.2 in the paper.

Using canonical representatives introduced by Rips and Sela, [loc. cit.] and the machinery there and in [F. Dahmani, Isr. J. Math. 173, 91-124 (2009; Zbl 1189.20034)], the authors reduce the Theorem above to the equations problem in a virtually free group. To give a solution of the equations problem in virtually free groups they reduce it to a problem of twisted equations in a free group (Proposition 2.4 in the paper).

In a group \(G\) a twisted equation is an equation of the form \(\varphi_1(x_1)\cdots\varphi_n(x_n)=1\), where each \(\varphi_i\) is a fixed automorphism of \(G\), and \(x_i\) is a variable or a constant.

Here the authors need only the use of automorphisms of a free group \(F=\langle S\rangle\) which preserve the set \(S\cup S^{-1}\) (see Definition 2.2 in the paper) and prove that this problem of twisted equations is solvable. The solution is obtained approaching Makanin’s algorithm from the point of view of Rips’ theory for foliated band complexes.

Reviewer: Dimitrios Varsos (Athenai)

##### MSC:

20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |

20F70 | Algebraic geometry over groups; equations over groups |

20F67 | Hyperbolic groups and nonpositively curved groups |

57M07 | Topological methods in group theory |

20E05 | Free nonabelian groups |