{ "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": [ "" ] }, "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 }