{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homophonic quotients of free groups\n",
    "\n",
    "This file contains the GAP input needed to verify the result of the following paper:\n",
    "\n",
    "- Mestre, Jean-François; Schoof, René; Washington, Lawrence; Zagier, Don\n",
    "Quotients homophones des groupes libres. (French) [Homophonic quotients of \n",
    "free groups] Experiment. Math. 2 (1993), no. 3, 153--155 \n",
    "(http://eudml.org/doc/233741)\n",
    "\n",
    "with respect to the English language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That paper proves the triviality of the finitely presented group given by generators being the 26 letters of the English alphabet and relations being formed by the words which are pronounced in the same way but have different spelling."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will validate the proof using GAP. First, we will create a free group $F$ on 26 letters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<group with 26 generators>"
      ]
     },
     "execution_count": 1,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F:=FreeGroup(\"a\",\"b\",\"c\",\"d\",\"e\",\"f\",\"g\",\"h\",\"i\",\"j\",\"k\",\"l\",\"m\",\"n\",\"o\",\"p\",\"q\",\"r\",\"s\",\"t\",\"u\",\"v\",\"w\",\"x\",\"y\",\"z\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we will specify relations. We would like the list of relations to be human readable, and contain them in the same order as in the proof. The comment explains which of generators are eliminated by the corresponding relation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ \"bye=by\", \"lead=led\", \"maid=made\", \"sow=sew\", \"buy=by\", \"sow=so\", \"lye=lie\", \"hour=our\", \"knight=night\", \"damn=dam\", \"psalter=salter\", \"plumb=plum\", \"bass=base\", \"butt=but\", \"tolled=told\", \"barred=bard\", \"dammed=damned\", \"chased=chaste\", \"sign=sine\", \"daze=days\", \"cite=sight\", \"jeans=genes\", \"queue=cue\", \"tax=tacks\", \"phase=faze\", \"chivvy=chivy\" ]"
      ]
     },
     "execution_count": 2,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pairs:=[ \n",
    "\"bye=by\",          # e=1\n",
    "\"lead=led\",        # a=1\n",
    "\"maid=made\",       # mid=md => i=1\n",
    "\"sow=sew\",         # o=e=1\n",
    "\"buy=by\",          # u=1\n",
    "\"sow=so\",          # w=1\n",
    "\"lye=lie\",         # y=1\n",
    "\"hour=our\",        # h=1 \n",
    "\"knight=night\",    # k=1\n",
    "\"damn=dam\",        # n=1\n",
    "\"psalter=salter\",  # p=1\n",
    "\"plumb=plum\",      # b=1\n",
    "\"bass=base\",       # s=1\n",
    "\"butt=but\",        # t=1\n",
    "\"tolled=told\",     # l=1\n",
    "\"barred=bard\",     # r=1\n",
    "\"dammed=damned\",   # m=1\n",
    "\"chased=chaste\",   # d=1\n",
    "\"sign=sine\",       # g=1\n",
    "\"daze=days\",       # z=1\n",
    "\"cite=sight\",      # c=1\n",
    "\"jeans=genes\",     # j=1\n",
    "\"queue=cue\",       # q=1\n",
    "\"tax=tacks\",       # x=1\n",
    "# \"ruff=rough\",    # f=1, we need not this relation used in the paper\n",
    "\"phase=faze\",      # f=1\n",
    "\"chivvy=chivy\"];   # v=1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we use `ParseRelators` (see [GAP reference manual](https://www.gap-system.org/Manuals/doc/ref/chap47.html#X7B3D290B87B6EFE4)) to convert strings to words composed from the generators of $F$: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ b*y*e*y^-1*b^-1, l*e*a*e^-1*l^-1, m*a*d*e*d^-1*i^-1*a^-1*m^-1, s*e*o^-1*s^-1, b*u*b^-1, s*o*w*o^-1*s^-1, l*i*y^-1*l^-1, h, k, d*a*m*n*m^-1*a^-1*d^-1, p, p*l*u*m*b*m^-1*u^-1*l^-1*p^-1, b*a*s*e*s^-2*a^-1*b^-1, b*u*t*u^-1*b^-1, t*o*l^2*e*l^-1*o^-1*t^-1, b*a*r^2*e*r^-1*a^-1*b^-1, d*a*m*n*m^-2*a^-1*d^-1, c*h*a*s*t*e*d^-1*e^-1*s^-1*a^-1*h^-1*c^-1, s*i*n*e*n^-1*g^-1*i^-1*s^-1, d*a*y*s*e^-1*z^-1*a^-1*d^-1, s*i*g*h*t*e^-1*t^-1*i^-1*c^-1, g*e*n*e*n^-1*a^-1*e^-1*j^-1, q*u*e*c^-1, t*a*c*k*s*x^-1*a^-1*t^-1, p*h*a*s*z^-1*a^-1*f^-1, c*h*i*v*i^-1*h^-1*c^-1 ]"
      ]
     },
     "execution_count": 3,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rels:=List( pairs, r -> ParseRelators(GeneratorsOfGroup(F),r)[1]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we check that the group given by the specified presentation is trivial: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<group with 26 generators>"
      ]
     },
     "execution_count": 4,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G:=F/rels;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 5,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(G);"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "GAP 4",
   "language": "gap",
   "name": "gap-4"
  },
  "language_info": {
   "codemirror_mode": "gap",
   "file_extension": ".g",
   "mimetype": "text/x-gap",
   "name": "GAP 4",
   "nbconvert_exporter": "",
   "pygments_lexer": "gap",
   "version": "4.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}