rubik.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Analyzing Rubik's Cube with Oscar\n",
    "\n",
    "* Authors: Martin Schoenert, Thomas Breuer\n",
    "* Version: OSCAR version 1.0\n",
    "* Last modified: April 11, 2024\n",
    "\n",
    "The following Julia session shows the computations from the [Rubik's Cube example](https://www.gap-system.org/Doc/Examples/rubik.html) from the GAP webpages.\n",
    "A Julia session with equivalent computations using just the GAP interface [GAP.jl](https://github.com/oscar-system/GAP.jl) can be found inside [the documentation of this package](https://oscar-system.github.io/GAP.jl/stable).\n",
    "\n",
    "First we load `Oscar.jl`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  ___   ____   ____    _    ____\n",
      " / _ \\ / ___| / ___|  / \\  |  _ \\   |  Combining ANTIC, GAP, Polymake, Singular\n",
      "| | | |\\___ \\| |     / _ \\ | |_) |  |  Type \"?Oscar\" for more information\n",
      "| |_| | ___) | |___ / ___ \\|  _ <   |  Manual: https://docs.oscar-system.org\n",
      " \\___/ |____/ \\____/_/   \\_\\_| \\_\\  |  Version 1.1.0\n"
     ]
    }
   ],
   "source": [
    "using Oscar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We consider the group of transformations of Rubik's magic cube.\n",
    "If we number the faces of this cube as follows\n",
    "\n",
    "```\n",
    "                     +--------------+\n",
    "                     |              |\n",
    "                     |  1    2    3 |\n",
    "                     |              |\n",
    "                     |  4  top    5 |\n",
    "                     |              |\n",
    "                     |  6    7    8 |\n",
    "                     |              |\n",
    "      +--------------+--------------+--------------+--------------+\n",
    "      |              |              |              |              |\n",
    "      |  9   10   11 | 17   18   19 | 25   26   27 | 33   34   35 |\n",
    "      |              |              |              |              |\n",
    "      | 12  left  13 | 20 front  21 | 28 right  29 | 36  rear  37 |\n",
    "      |              |              |              |              |\n",
    "      | 14   15   16 | 22   23   24 | 30   31   32 | 38   39   40 |\n",
    "      |              |              |              |              |\n",
    "      +--------------+--------------+--------------+--------------+\n",
    "                     |              |\n",
    "                     | 41   42   43 |\n",
    "                     |              |\n",
    "                     | 44 bottom 45 |\n",
    "                     |              |\n",
    "                     | 46   47   48 |\n",
    "                     |              |\n",
    "                     +--------------+\n",
    "```\n",
    "\n",
    "then the group is generated by the following generators, corresponding to the six faces of the cube."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Permutation group of degree 48"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = symmetric_group(48);\n",
    "\n",
    "l = [\n",
    "     [[ 1, 3, 8, 6], [ 2, 5, 7, 4], [ 9,33,25,17], [10,34,26,18], [11,35,27,19]],\n",
    "     [[ 9,11,16,14], [10,13,15,12], [ 1,17,41,40], [ 4,20,44,37], [ 6,22,46,35]],\n",
    "     [[17,19,24,22], [18,21,23,20], [ 6,25,43,16], [ 7,28,42,13], [ 8,30,41,11]],\n",
    "     [[25,27,32,30], [26,29,31,28], [ 3,38,43,19], [ 5,36,45,21], [ 8,33,48,24]],\n",
    "     [[33,35,40,38], [34,37,39,36], [ 3, 9,46,32], [ 2,12,47,29], [ 1,14,48,27]],\n",
    "     [[41,43,48,46], [42,45,47,44], [14,22,30,38], [15,23,31,39], [16,24,32,40]] ];\n",
    "\n",
    "cube = sub(g, [cperm(g, x) for x in l])[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we want to know the order of this group."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43252003274489856000"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cube_size = order(cube)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since this is a little bit unhandy, let us factorize this number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 * 5^3 * 7^2 * 2^27 * 11 * 3^14"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(cube_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(The result tells us that the order is 2<sup>27</sup> 3<sup>14</sup> 5<sup>3</sup> 7<sup>2</sup> 11.)\n",
    "\n",
    "Next let us investigate the operation of the group on the 48 points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Vector{Vector{Int64}}:\n",
       " [1, 3, 17, 14, 8, 38, 9, 41, 19, 48  …  43, 11, 46, 40, 24, 27, 25, 35, 16, 32]\n",
       " [2, 5, 12, 7, 36, 10, 47, 4, 28, 45  …  20, 42, 26, 21, 37, 15, 31, 18, 23, 39]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "orbs = orbits(cube);  map(collect, orbs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first orbit contains the points at the corners, the second those at the edges;\n",
    "clearly the group cannot move a point at a corner onto a point at an edge.\n",
    "\n",
    "So to investigate the cube group we first investigate the operation on the corner points.\n",
    "Note that the constructed group that describes this operation will operate on the set `1:24`, not on the original set `orbs[1]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Permutation group of degree 24"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cube1 = image(action_homomorphism(orbs[1]))[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "degree(cube1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "88179840"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order(cube1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now this group obviously operates transitively, but let us test whether it is also primitive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8-element Vector{Vector{Int64}}:\n",
       " [1, 7, 22]\n",
       " [2, 14, 20]\n",
       " [3, 12, 16]\n",
       " [4, 17, 18]\n",
       " [5, 9, 21]\n",
       " [6, 10, 24]\n",
       " [8, 11, 23]\n",
       " [13, 15, 19]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "corners = blocks(cube1);  collect(corners)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Those eight blocks correspond to the eight corners of the cube; on the one hand the group permutes those and on the other hand it permutes the three points at each corner cyclically."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Permutation group of degree 8"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "blockhom1 = action_homomorphism(corners);  cube1b = image(blockhom1)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40320"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order(cube1b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now a permutation group of degree 8 that has order 40320 must be the full symmetric group `Sym(8)` on eight points.\n",
    "\n",
    "The next thing then is to investigate the kernel of this operation on blocks, i.e., the subgroup of `cube1` of those elements that fix the blocks setwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Permutation group of degree 24 and order 2187"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ker1 = kernel(blockhom1)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 * 3^7"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(order(ker1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_elementary_abelian(ker1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can show that the product of this elementary abelian group ``3^7`` with the `Sym(8)` is semidirect by finding a complement, i.e., a subgroup that has trivial intersection with the kernel and that generates `cube1` together with the kernel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Vector{PermGroup}:\n",
       " Permutation group of degree 24 and order 40320"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmpl1 = complement_class_reps(cube1, ker1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40320"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmpl1 = cmpl1[1]; order(cmpl1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We verify the complement properties:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order(intersect(cmpl1, ker1)[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sub(cube1, vcat(gens(cmpl1), gens(ker1)))[1] == cube1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is even a more elegant way to show that `cmpl1` is a complement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_bijective(restrict_homomorphism(blockhom1, cmpl1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, theoretically it is clear that `cmpl1` must indeed be a complement.\n",
    "\n",
    "In fact we know that `cube1` is a subgroup of index 3 in the wreath product of a cyclic 3 with `Sym(8)`.\n",
    "This missing index 3 tells us that we do not have total freedom in turning the corners.\n",
    "The following tests show that whenever we turn one corner clockwise we must turn another corner counterclockwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cperm(g, [1, 7, 22]) in cube1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cperm(g, [1, 7, 22], [2, 20, 14]) in cube1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More or less the same things happen when we consider the operation of the cube group on the edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Permutation group of degree 24"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cube2 = image(action_homomorphism(cube, orbs[2]))[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "degree(cube2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "980995276800"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order(cube2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = blocks(cube2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12-element Vector{Vector{Int64}}:\n",
       " [1, 11]\n",
       " [2, 17]\n",
       " [3, 19]\n",
       " [4, 22]\n",
       " [5, 13]\n",
       " [6, 8]\n",
       " [7, 24]\n",
       " [9, 18]\n",
       " [10, 21]\n",
       " [12, 15]\n",
       " [14, 20]\n",
       " [16, 23]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "collect(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Group homomorphism\n",
       "  from permutation group of degree 24 and order 980995276800\n",
       "  to Sym(12)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "blockhom2 = action_homomorphism(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Permutation group of degree 12"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cube2b = image(blockhom2)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "479001600"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order(cube2b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Permutation group of degree 24 and order 2048"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ker2 = kernel(blockhom2)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 * 2^11"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(order(ker2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_elementary_abelian(ker2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4-element Vector{PermGroup}:\n",
       " Permutation group of degree 24 and order 479001600\n",
       " Permutation group of degree 24 and order 479001600\n",
       " Permutation group of degree 24 and order 479001600\n",
       " Permutation group of degree 24 and order 479001600"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmpl2 = complement_class_reps(cube2, ker2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So there are even 4 classes of complements here.\n",
    "This time we get a semidirect product of a ``2^11`` with an `Sym(12)`, namely a subgroup of index 2 of the wreath product of a cyclic 2 with `Sym(12)`.\n",
    "Here the missing index 2 tells us again that we do not have total freedom in turning the edges.\n",
    "The following tests show that whenever we flip one edge we must also flip another edge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cperm([1, 11]) in cube2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cperm([1, 11], [2, 17]) in cube2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since `cube1` and `cube2` are the groups describing the actions on the two orbits of `cube`, it is clear that `cube` is a subdirect product of those groups, i.e., a subgroup of the direct product. Comparing the sizes of `cube1`, `cube2`, and `cube` we see that `cube` must be a subgroup of index 2 in the direct product of those two groups."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43252003274489856000"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order(cube)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "86504006548979712000"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order(cube1) * order(cube2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This final missing index 2 tells us that we cannot operate on corners and edges totally independently.\n",
    "The following tests show that whenever we exchange a pair of corners we must also exchange a pair of edges (and vice versa)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cflip = cperm(g, [17, 19], [8, 11], [6, 25]);  cflip in cube"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eflip = cperm(g, [7, 28], [18, 21]);  eflip in cube"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cflip * eflip in cube"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a last part of the structure analysis of the cube group let us compute the center of the cube group, i.e., the subgroup of those operations that can be performed either before or after any other operation with the same result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Permutation group of degree 48 and order 2"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = center(cube)[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that the centre contains one nontrivial element, namely the operation that flips all 12 edges simultaneously.\n",
    "\n",
    "Finally we turn to the original idea connected with the cube, namely to find a sequence of turns of the faces that will transform the cube back into its original state. This amounts to a decomposition of a given element of the cube group into a product of the generators. For this purpose we introduce a free group and a homomorphism of it onto the cube group.\n",
    "\n",
    "(In order to make the results of the decompositions reproducible, we reset the random number generator that is involved in the computations.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "GAP.Globals.Reset(GAP.Globals.GlobalMersenneTwister);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Free group of rank 6"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = free_group([\"t\", \"l\", \"f\", \"r\", \"e\", \"b\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Group homomorphism\n",
       "  from free group of rank 6\n",
       "  to permutation group of degree 48 and order 43252003274489856000"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fhom = hom(f, cube, gens(cube))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using this homomorphism, we can now decompose elements into generators. The method used utilizes a stabilizer chain and does not enumerate all group elements, therefore the words obtained are not the shortest possible, though they are short enough for hand solutions.\n",
    "\n",
    "(In order to make the results of the decompositions reproducible, we reset the random number generator that is involved in the computations.)\n",
    "First we decompose the nonidentity centre element:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "t^-1*l*t*l^-1*e^-1*t*f^-1*e*l*f*(t^-1*l^-1)^2*t*l*f*t*r*t^-1*r^-1*f^-1*l^-1*e^-1*t^-1*e*t*l*t*f*t*r*t^-1*r^-1*f^-1*t^-2*f*t^-1*f^-1*t^2*e*l^-1*e^-1*t^-1*l*t*l*f*t^-1*f^-1*l^-1*t*l*t^2*l^-1*t^-1*l*t^-1*l^-1*t^2*f^-1*l^-1*t^-1*l*t*f*t*l^-1*t*l*f^-1*l*f*l^-1*t^-2*l^-1*f^-1*l*f*l*t*e^-1*t*e*l*t*l^-1*e*l*e^-1*t^-1*f*l*f*l^-1*f^-1*t^-2*f^-1*t*l^-1*f*t^-2*f^-2*b*r^-1*b^-1*t^-2*e^-1*r^-2*e*t^-1*r*b*e^-1*b^-1*l^-1*r^-2*t^-2*l^-1*b^-1*r^-1*e^-1"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zgen = gen(z, 1);  pre1 = haspreimage(fhom, zgen)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "134"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length(pre1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we decompose some element arbitrarily chosen by us:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "l^-1*t^-1*l*f*r*t*r^-1*f^-1*l*t*f*t^-1*f^-1*l^-1*t^2*f*t*l*t*l^-1*f^-1*l*t^-1*l^-1*f*t^-1*f^-1*l*t*l^-1*t*l*t^-2*l^-1*f*(t*r*t^-1*r^-1)^2*f^-1*t*l*f^-1*l^-1*f*l^-1*t^-1*l*t^-2*f*t*(f^-1*l^-1)^2*l^-1*f*l*e^-1*t*e*l*t^-1*e^-1*t^-1*e*l*b*f^-1*b^-1"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pre2 = haspreimage(fhom, cflip * eflip)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "77"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length(pre2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Last we let GAP choose a random element ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,14,9,46,35,40)(2,42,21,36,47,44,18,45,26,13,34,23,28,29,39,15,7,31,5,20)(3,27,33)(6,41,24)(8,19,25)(11,22,43)(12,37)(16,30,17)(32,38,48)"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r = rand(cube)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "l^-1*e^-1*t^-1*e*t*l*t*f*t*r*t^-1*r^-1*f^-1*t*f*t*l*t*l^-1*f^-1*l*t^-1*l^-1*f*t^-1*f^-1*t^2*l*t*l^-1*t^-1*l^-1*e*l*e^-1*l*t*f*t^-1*f^-1*l^-2*t*l*f^-1*l*f*l^-1*t^-2*f*t^-1*f^-1*l^-1*f^-1*l*f*l*e^-1*t^-1*e*t^-1*l^-2*t^-1*f*l*f*l^-1*f^-1*t^-2*r*t*r^-1*f*l^-2*e*b^-1*e^-1*f^-1*r*b"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pre3 = haspreimage(fhom, r)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "85"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length(pre3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... and we verify that the decomposition is correct:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fhom(pre3) == r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This concludes our example."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.8.5",
   "language": "julia",
   "name": "julia-1.8"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}