CoDiMa visit - Alan Logan in Glasgow
The need for these methods was once more highlighted at the Computation in geometric and combinatorial group theory at the ICMS in Edinburgh in July this year.
We were concentrating on the “Isomorphism Problem”, more specifically, given as input two group presentations H1 = <X|R> and H2 = <Y|S>, decide whether the groups H1 and H2 are isomorphic.
A (final) solution to this problem was given by Dahmani and Guirardel 1, building on previous work by Dahmani and Groves 2, Dahmani 3, Sela 4, and many more. The algorithms presented in these papers are both more general, they work for toral relatively hyperbolic groups, and likely rather impractical.
So, this week we started out exploring practical approaches to the problem.
The Dahmani-Guirardel-Groves-Sela method at a very high level proceeds as follows
- Decompose H1 and H2 into free factors (called Grushko decomposition)
- For every factor compute a graph of groups
- Isomorphism is now decided by deciding isomorphism of the underlying graphs and vertex groups.
- Isomorphism of vertex groups is tested by constructing valid monomorphisms between pairs of them by solving systems of equations.
Finding graph isomorphisms is a problem that we will happily outsource to programs such as nauty.
We quickly decided (helped by the fact that Francois Dahmani suggested this to us as well) that we will look at the solution of the isomorphism problem for the edge groups first, this case is called the “rigid case”.
The problem we homed in on then is the problem of solving equations in free and hyperbolic groups, an area that Ciobanu, Elder, and Diekert recently made progress in 5.
We will now first implement solutions to equations in free groups, and generate the proper systems of equations that come up in the decision procedure, as well as some helping algorithms to estimate the size of some problems.
Sela, Z, The isomorphism problem for hyperbolic groups I, Ann. Math. (2) 141 (1995), 217-283↩