I would like to know whether there is some computer algebra software that can be used to verify if a group, given by a finite presentation, is hyperbolic (in the sense that it terminates with "yes" if the group is hyperbolic and otherwise might not terminate). I read that the kbmag software package for GAP could be used for this task. However I did not find any information in the documentation about how this can be accomplished.

I would also be interested to know if there is some software (say a GAP package) to check if a given group presentation satisfies a small cancellation condition (like $C'(\lambda)$).

  • $\begingroup$ No. No such algorithm exists. Do you want a pseudo-algorithm? i.e. one that might not always terminate in a known amount of time? If so there are such. But genuine algorithms, no. If one existed you could use it to solve the "groups is trivial" problem. It's known this is not an algorithmically-solvable problem. $\endgroup$ – Ryan Budney May 13 '16 at 8:38
  • $\begingroup$ @RyanBudney, the OP seems to be aware of this, since they stipulate that the algorithm might not terminate. $\endgroup$ – HJRW May 13 '16 at 8:56
  • $\begingroup$ @RyanBudney: Yes, a pseudo-algorithm is fine. $\endgroup$ – scalar May 13 '16 at 9:03
  • 1
    $\begingroup$ There is a GAP forum mailing list that you use to ask if anyone has written any small cancellation software. It seems quite likely that somebody might have done! $\endgroup$ – Derek Holt May 13 '16 at 10:03

The KBMAG package can be used to verify hyperbolicity of a group defined by a finite presentation. It does it by verifying that geodesic bigons in the Cayley graph are uniformly thin. Then a result of Paposoglu implies that the group is hyperbolic. So it proves hyperbolicity, but it does not provide any useful information aboutn the constant of hyperbolicity.

Unfortunately, whoever designed the GAP interface (well me) did not provide a convenient interface to this functionality. But it is possible to use the GAP Exec command to do this. Here is a simple with the group $\langle x,y \mid x^2=y^3=(xy)^7=1 \rangle$. The KBMAG package needs to be compiled. I am running it on Linux, and I don't know whether it will work properly with other operating systems.

F:=FreeGroup(2);; rels:=[F.1^2, F.2^3, (F.1*F.2)^7];; G:=F/rels;;
progname := Filename(_KBExtDir,"autgroup");;
callstring := Concatenation(progname," 237");;
progname := Filename(_KBExtDir,"gpgeowa");;
callstring := Concatenation(progname," 237");;

If the final command completes successfully then it has succeeded in verifying that geodesic bigons are uniformly thin. The output of the last command should be something like:

#Geodesic word found not accepted by *geowaptr.
#Geodesic word-acceptor with 54 states computed.
#Geodesic pairs machine with 114 states computed.
#Geodesic difference machine with 31 states computed.
  • $\begingroup$ Why didn't you provide a more convenient interface to this functionality -- writing IsHyperbolic(G) would be so much more convenient than the above procedure, wouldn't it? $\endgroup$ – Stefan Kohl May 15 '16 at 10:35
  • $\begingroup$ In case anyone willing to suggest new functionality or submit contributions, KBMAG package is now hosted on GitHub here: github.com/gap-packages/kbmag $\endgroup$ – Alexander Konovalov May 15 '16 at 13:19
  • 3
    $\begingroup$ @StefanKohl I am not really sure why I never did this. Perhaps it is because the program never answers no. It just fails to halt if it doesn't succeed. But I could certainly put in some sort of halting criterion and get it to return fail if that happens. I will make it a priority to do that. $\endgroup$ – Derek Holt May 15 '16 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.