{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lecture 10: Groups ##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternating Group ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "\n",
    "Now Consider the Alternating Group $A_4$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "*  a b c d e f g h i j k l\n",
       " +------------------------\n",
       "a| a b c d e f g h i j k l\n",
       "b| b f d h g a i c e k l j\n",
       "c| c e g f k j a l h d b i\n",
       "d| d g i a l k b j c h f e\n",
       "e| e j f l a c h g k b i d\n",
       "f| f a h c i b e d g l j k\n",
       "g| g k a j b d c i l f e h\n",
       "h| h i e b j l f k d c a g\n",
       "i| i l b k f h d e j a g c\n",
       "j| j c l g h e k f a i d b\n",
       "k| k d j i c g l a b e h f\n",
       "l| l h k e d i j b f g c a\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A4=AlternatingGroup(4)\n",
    "A4.cayley_table()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SageMath arbitrarily names the elements a,b,c,... so we'll need to ask it what each letter represents. We use the command `.cayley_table().column_keys()`. This returns the elements ordered by their names a,b,c,..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((),\n",
       " (1,2,3),\n",
       " (2,3,4),\n",
       " (1,3)(2,4),\n",
       " (1,2)(3,4),\n",
       " (1,3,2),\n",
       " (2,4,3),\n",
       " (1,4,2),\n",
       " (1,4,3),\n",
       " (1,3,4),\n",
       " (1,2,4),\n",
       " (1,4)(2,3))"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A4.cayley_table().column_keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can tell Sage what names we want it to use for the elements.  First we give it a list of the elements in the order we want it to use them in the Cayley table (we called our list `A4list`, but you can use any name you want for this list), then we give it the corresponding names we want Sage to use (we put them in a list we call `A4names`).\n",
    "\n",
    "We use the optional arguments `names` and `elements` of `.cayley_table` to pass the order and names we want it to use for the elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "  *    1  s1  s2  s3  s4  s5  s6  s7  s8  s9 s10 s11\n",
       "   +------------------------------------------------\n",
       "  1|   1  s1  s2  s3  s4  s5  s6  s7  s8  s9 s10 s11\n",
       " s1|  s1   1  s3  s2  s8 s10  s9 s11  s4  s6  s5  s7\n",
       " s2|  s2  s3   1  s1 s11  s6  s5  s8  s7 s10  s9  s4\n",
       " s3|  s3  s2  s1   1  s7  s9 s10  s4 s11  s5  s6  s8\n",
       " s4|  s4 s11  s7  s8  s5   1  s3 s10  s6  s1  s2  s9\n",
       " s5|  s5  s9 s10  s6   1  s4  s8  s2  s3 s11  s7  s1\n",
       " s6|  s6 s10  s9  s5  s2 s11  s7   1  s1  s4  s8  s3\n",
       " s7|  s7  s8  s4 s11  s9  s3   1  s6 s10  s2  s1  s5\n",
       " s8|  s8  s7 s11  s4 s10  s1  s2  s5  s9   1  s3  s6\n",
       " s9|  s9  s5  s6 s10  s3  s7 s11  s1   1  s8  s4  s2\n",
       "s10| s10  s6  s5  s9  s1  s8  s4  s3  s2  s7 s11   1\n",
       "s11| s11  s4  s8  s7  s6  s2  s1  s9  s5  s3   1 s10\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A4=AlternatingGroup(4)\n",
    "A4list=[\"()\", \"(1,2)(3,4)\", \"(1,3)(2,4)\", \"(1,4)(2,3)\", \"(1,2,3)\", \"(1,3,2)\",\n",
    "\"(1,2,4)\",\"(1,4,2)\", \"(1,3,4)\", \"(1,4,3)\", \"(2,3,4)\", \"(2,4,3)\"]\n",
    "A4names=[\"1\", \"s1\", \"s2\", \"s3\", \"s4\", \"s5\", \"s6\", \"s7\", \"s8\", \"s9\", \"s10\", \"s11\"]\n",
    "A4.cayley_table(names=A4names,elements=A4list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And there we have it!  A multiplication table for $A_4$ with the elements named and ordered how we wanted them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dihedral Group ###\n",
    "\n",
    "Sage has the dihedral group built it. Here we construct the dihedral group of the square."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(), (1,4)(2,3), (1,2,3,4), (1,3)(2,4), (1,3), (2,4), (1,4,3,2), (1,2)(3,4)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D4=DihedralGroup(4)\n",
    "D4.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This shows that Sage represents the dihedral group using permuatations.\n",
    "\n",
    "We can name these elements using `R90`, etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,4)(2,3)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R90=D4(\"(1,2,3,4)\")\n",
    "R180=D4(\"(1,3)(2,4)\")\n",
    "R270=D4(\"(1,4,3,2)\")\n",
    "H=D4(\"(1,4)(2,3)\")\n",
    "V=D4(\"(1,2)(3,4)\")\n",
    "D=D4(\"(2,4)\")\n",
    "Dp=D4(\"(1,3)\")\n",
    "\n",
    "R90*D   # compute the product of R90 and D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Just like we did with the alternating group above we can construct the Cayley Table for the Dihedral group."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       " *  R0 R1 R2 R3  H  V  D D'\n",
       "  +------------------------\n",
       "R0| R0 R1 R2 R3  H  V  D D'\n",
       "R1| R1 R2 R3 R0 D'  D  H  V\n",
       "R2| R2 R3 R0 R1  V  H D'  D\n",
       "R3| R3 R0 R1 R2  D D'  V  H\n",
       " H|  H  D  V D' R0 R2 R1 R3\n",
       " V|  V D'  H  D R2 R0 R3 R1\n",
       " D|  D  V D'  H R3 R1 R0 R2\n",
       "D'| D'  H  D  V R1 R3 R2 R0\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D4=DihedralGroup(4)\n",
    "D4list=[\"()\",\"(1,2,3,4)\",\"(1,3)(2,4)\",\"(1,4,3,2)\",\"(1,4)(2,3)\",\"(1,2)(3,4)\",\"(2,4)\",\"(1,3)\"]\n",
    "D4names=[\"R0\",\"R1\",\"R2\",\"R3\",\"H\",\"V\",\"D\",\"D'\"]\n",
    "D4.cayley_table(names=D4names,elements=D4list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cyclic Group ###\n",
    "\n",
    "$Z_n = \\{0,1,2, \\ldots, n-1\\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The best way to compute with elements in $Z_n$ is to just use the remainder operator `%`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(5+8)%3   # this finds the remainder of 5+8=13 when you divide 3 into it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### U Groups ###\n",
    "\n",
    "$U(n) = \\{ m \\ |\\ 1\\le m \\le n-1 \\text{ and } \\gcd(m,n)=1 \\}$ under multiplication modulo $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Listing the elements of the U group U(28):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U28=[]\n",
    "for x in range(1,28):\n",
    "    if gcd(x,28)==1:\n",
    "        U28.append(x)\n",
    "U28"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way, using list comprehensions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U28=[x for x in range(1,28) if gcd(x,28)==1]\n",
    "U28"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's find the inverse of 9 in U(28) by running through all possibilities:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25\n"
     ]
    }
   ],
   "source": [
    "for x in U28:\n",
    "    if 9*x%28==1:\n",
    "        print x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "check:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "9*25%28"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could also use the command `inverse_mod()` command:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inverse_mod(9,28)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This command uses the extended euclidean algorthim to determine the inverse. \n",
    "(See Appendix B in the notes for a description of the extended euclidean algorthim.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, -3, 1)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xgcd(9,28)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "The number -3 that is returned by the `xgcd` algorithm is the inverse of 9 modulo 28.  Note that -3 is equal to 25 modulo 28."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.3",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}