Polynomial-time proofs that groups are hyperbolic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Polynomial-time proofs that groups are hyperbolic\n",
    "\n",
    "### Derek Holt, Stephen Linton, Max Neunhöffer, Richard Parker, Markus Pfeiffer, and Colva M. Roney-Dougal\n",
    "\n",
    "This notebook demonstrates the capabilities of the GAP implementation of the polynomial-time algorithm to prove hyperbolicity of a finitely presented group described in the paper *Polynomial-time proofs that groups are hyperbolic*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#I  method installed for Size matches more than one declaration\n",
      "#I  method installed for Size matches more than one declaration\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 1,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LoadPackage(\"walrus\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The command `TriangleGroup` takes three parameters and creates a pregroup presentation of the $(p,q,r)-$triangle group\n",
    "\n",
    "$$\n",
    "  \\operatorname{TriangleGroup}(p,q,r) = \\left< x, y ~|~ x^p, y^q, (xy)^r \\right>\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<pregroup presentation with 3 generators and 1 relators>"
      ]
     },
     "execution_count": 2,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "triangle := TriangleGroup(2,3,7);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Whenever $\\frac{1}{p} + \\frac{1}{q} + \\frac{1}{r} < 1$, a triangle group is hyperbolic:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 3,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsHyperbolic(triangle, 1/6);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The command `TriangleCommutatorQuotient(m,n)` creates a quotient of a $(2,3,m)-$triangle group by the commutator of the two generators raised to the $n-$th power, i.e.\n",
    "\n",
    "$$\n",
    "   \\operatorname{TriangleCommutatorQuotient}(m,n) = \\left< x, y ~|~ x^2, y^3, (xy)^m, (xyxy^{-1})^n \\right>\n",
    "$$\n",
    "\n",
    "cf Theorem 9.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "According to Theorem 9.5 for $m=13$ and $n=7$, the `RSymTest` procedure succeeds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 5,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "thm95 := TriangleCommutatorQuotient(13, 7);;\n",
    "IsHyperbolic(thm95, 1/10);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Whereas the current implementation of `RSymTest` in GAP does not succeed for $m=7$ and $n=19$, because it does not implement level 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ fail, [ [ 1, 0, 0, 0 ], [ 1, 4, 1, 31/210 ], [ 3, 7, 2, 2/15 ], [ 2, 6, 2, 23/420 ], [ 1, 8, 2, 31/105 ], [ 1, 6, 2, 29/210 ], [ 2, 8, 2, 19/420 ], [ 1, 10, 3, 2/7 ], [ 3, 9, 3, 13/105 ], [ 3, 11, 3, 59/210 ], [ 2, 10, 3, 17/84 ], [ 1, 12, 3, 31/70 ], [ 2, 12, 3, 27/140 ], [ 3, 13, 4, 19/70 ], [ 1, 14, 4, 13/30 ] ], [ 1, 10, 3, 2/7 ] ]"
      ]
     },
     "execution_count": 7,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "thm95_2 := TriangleCommutatorQuotient(7, 19);;\n",
    "IsHyperbolic(thm95_2, 1/10);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The MAGMA compatible interface"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#I  Assigned the global variables [ x, y ]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[ fail, [ [ 1, 0, 0, 0 ], [ 2, 1, 1, 13/120 ], [ 1, 2, 2, 13/60 ], [ 2, 3, 3, 13/40 ], [ 1, 4, 4, 13/30 ] ], [ 2, 3, 3, 13/40 ] ]"
      ]
     },
     "execution_count": 12,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F := FreeGroup(\"x\", \"y\");;\n",
    "AssignGeneratorVariables(F);;\n",
    "rred := [ y^3 ];;\n",
    "rgreen := [ x^4, (x*y)^4 ];;\n",
    "IsHyperbolic(F, rred, rgreen, 1/10);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#I  Global variable `x' is already defined and will be overwritten\n",
      "#I  Global variable `y' is already defined and will be overwritten\n",
      "#I  Assigned the global variables [ x, y, t ]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 17,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F := FreeGroup(\"x\", \"y\", \"t\");;\n",
    "AssignGeneratorVariables(F);;\n",
    "rred := [y^3, x^2 * t];;\n",
    "rgreen := [t^2, (x*y)^4];;\n",
    "IsHyperbolic(F, rred, rgreen, 1/10);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#I  Assigned the global variables [ a, b, c, d, e ]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Error, PregroupByTable: P5 violated\n"
     ]
    }
   ],
   "source": [
    "F := FreeGroup(\"a\",\"b\",\"c\",\"d\",\"e\");;\n",
    "AssignGeneratorVariables(F);;\n",
    "rred := [ a*b*c^-1, b*c*d^-1, c*d*e^-1, d*e*a^-1, e*a*b^-1 ];;\n",
    "IsHyperbolic(F, rred, [], 1/10);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "GAP 4 (native)",
   "language": "gap",
   "name": "gap-native"
  },
  "language_info": {
   "codemirror_mode": "gap",
   "file_extension": ".g",
   "mimetype": "text/x-gap",
   "name": "GAP 4",
   "nbconvert_exporter": "",
   "pygments_lexer": "gap",
   "version": "4.dev"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}