Lesson9-Finite-matrix-groups.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lesson 9 - Matrix Groups \n",
    "\n",
    "## Learning Outcomes\n",
    "\n",
    "- learn different ways of working with matrix groups in SageMath\n",
    "\n",
    "It is possible to work with both finite and infinite groups in SageMath. \n",
    "In number theory we are mainly interested either in matrix groups over finite fields \n",
    "or arithmetic groups like the modular group $\\operatorname{SL}(2,\\mathbb{Z})$ and its subgroups."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SL(2, RR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SL(2, ZZ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Another version of the modular group that is more convenient for number theory. \n",
    "SL2Z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SL2Z.cardinality()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also work with $\\operatorname{SL}(2)$ over a ring or a finite field,\n",
    "in SageMath either given as `SL(2, n)` or more explicitly `SL(2, GF(p))`\n",
    "or `SL(2, Zmod(p))`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SL(2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SL(2, GF(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SL(2, Zmod(3))  # A different representation of the same object"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2 = SL(2, 2); G2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2.list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generators\n",
    "SL(2, 2).gens()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# It is possible to construct matrices over different rings \n",
    "m = matrix(GF(2), 2, 2, [[1, 1], [0, 1]])\n",
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m in G2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m.multiplicative_order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = G2.subgroup([m])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H.cardinality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finite groups can always be given as permutation groups:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2.as_permutation_group()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Interface to GAP\n",
    "Some groups can be converted to corresponding groups in GAP and have associated properties. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GapG2 = G2.gap(); GapG2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GapG2.ConjugacyClassesSubgroups()  # Find conjugacy classes of subgroups"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GapG2.Gap3CatalogueIdGroup()  # Can identify a given group"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that a conjugacy class in a group G is a set of \n",
    "$$\n",
    "[h] = \\{g h g^{-1} \\mid g \\in G\\}\n",
    "$$\n",
    "\n",
    "**Exercise**\n",
    "Write a function to find the number of conjugacy classes in a given finite group\n",
    "(and compare with builtin methods). \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is possible to work with characters of groups. \n",
    "However, these characters are are missing some important functionality (for instance they are not functions so we can't apply them to arbitrary maps)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2 = SL(2, 2)\n",
    "G2.character_table()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = G2.character([2, 0, 2]); x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x.irreducible_constituents()[1].values()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise** \n",
    "Write a class `GroupCharacter` that takes as input a group and a list\n",
    "of values on conjugacy classes and returns a function on the group.\n",
    "\n",
    "E.g. `x = GroupCharacter(SL(2, 2), [1, -1, 1])` should result in\n",
    "a function `x` from $\\operatorname{SL}(2, 2)$ to $\\mathbb{Z}$.\n",
    "To make this ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The characters can be multiplied or added: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = G2.character([1, -1, 1])\n",
    "y = G2.character([1, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x*y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x+y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**\n",
    "Add the magic methods `__add__` and `__mul__` to your class\n",
    "to be able to add and multiply characters as well as multiply\n",
    "characters with integers.\n",
    "\n",
    "E.g. if\n",
    "```\n",
    "x = GroupCharacter(SL(2, 2),[1, -1, 1])\n",
    "y = GroupCharacter(SL(2, 2),[1, 1, 1])\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Subgroups of the modular group\n",
    "\n",
    "\n",
    "Recall that the modular group $\\Gamma = \\operatorname{PSL}(2, \\mathbb{Z})\n",
    "= \\operatorname{SL}(2,\\mathbb{Z})/\\{\\pm I_2 \\}$ (we work with the projective\n",
    "group for simplicity) has an infinite number of subgroups given by congruences,\n",
    "so-called congruence subgroups, determined by the fact that they contain the kernel \n",
    "of a reduction map:\n",
    "$$\n",
    "\\varphi_N : \\operatorname{PSL}(2, \\mathbb{Z}) \\to \\operatorname{PSL}(2,\\mathbb{Z}/N\\mathbb{Z})\n",
    "$$\n",
    "this group is called $\\Gamma(N)$ - the principal congruence subgroup.\n",
    "Another important type of congruence subgroup is \n",
    "$$\n",
    "\\Gamma_{0}(N) = \\left\\{ \n",
    "\\left(\\begin{array}{cc}\n",
    "a & b\\\\\n",
    "c & d\n",
    "\\end{array}\\right)\n",
    "\\in \\Gamma \\mid c \\equiv 0 \\pmod{N} \n",
    "\\right\\}\n",
    "$$\n",
    "It is well-known that the modular group has a presentation as \n",
    "$$\n",
    "\\Gamma = \\langle S, R \\mid S^2=R^3=1 \\rangle\n",
    "$$\n",
    "where \n",
    "$$ S = \\left(\\begin{array}{rr}\n",
    "0 & -1 \\\\\n",
    "1 & 0\n",
    "\\end{array}\\right) \\quad \n",
    "\\text{and}\n",
    "\\quad\n",
    "R = \n",
    "\\left(\\begin{array}{rr}\n",
    "0 & -1 \\\\\n",
    "1 & 1\n",
    "\\end{array}\\right)\n",
    "$$\n",
    "If $G \\leqslant \\Gamma$ then the subgroup $G$ can be described through\n",
    "the action of $S$ and $R$ on the right cosets of $G$ in $\\Gamma$. \n",
    "\n",
    "Let $n$ be a positive integer and let $\\sigma_S, \\sigma_R \\in S_n$ such that \n",
    "$\\sigma_S^2 = \\sigma_R^3 = id$ (the identity in $S_n$ and such that the subgroup \n",
    "$\\langle \\sigma_S,\\sigma_R \\rangle$ acts transitively on the set $\\{1,2,\\ldots,n\\}$.\n",
    "\n",
    "If we now define  a homomorphism \n",
    "$$ h : \\Gamma \\to S_n\n",
    "$$\n",
    "by $h(S)=\\sigma_S$, $h(R)=\\sigma_R$ then \n",
    "$$\n",
    "G = \\{ A \\in \\Gamma \\mid h_G(A)(1)=1 \\}\n",
    "$$\n",
    "is a subgroup of $\\Gamma$, and there is in fact a 1-to-1\n",
    "correspondence between subgroups of index $n$ and \n",
    "conjugacy classes of such pairs by permutations that fixes $1$, i.e. \n",
    "$\\sigma \\sim \\rho \\Leftrightarrow \\sigma = \\pi \\rho \\pi^{-1}$ for some $\\pi$ with $\\pi(1)=1$.\n",
    "\n",
    "Givena subgroup $G$ corresponding to  a pair $(\\sigma_S, \\sigma_R)$\n",
    "in $S_n$ it is possible to obtain a lot of geometric information\n",
    "about $G$ (or rather the orbifold $\\mathcal{M}=G\\backslash \\mathbb{H}$)\n",
    "from the permutations:\n",
    "1. The index of $G$ in $\\Gamma$ is $n$ (so the volume of $\\mathcal{M}$ is $\\frac{n\\pi}{3}$.\n",
    "2. The number of fixed points of $\\sigma_S$ is $e_2$, the number of elliptic points of order $2$.\n",
    "3. The number of fixed points of $\\sigma_R$ is $e_3$, the number of elliptic points of order $3$.\n",
    "4. The number of fixed points of $\\sigma_T = \\sigma_S \\sigma_R$ is $e_{\\infty}$, the number of cusps. \n",
    "5. The genus is then given by \n",
    "$$\n",
    "g = 1 + \\frac{1}{2}\\left( \\frac{n}{6} - e_{\\infty} - \\frac{1}{2}e_2 - \\frac{2}{3} e_3 \\right)\\tag{*}\n",
    "$$\n",
    "\n",
    "It can in fact be shown that the if a tuple $(n;g,e_2,e_3,e_{\\infty})$\n",
    "(we will refer to this as a **signature** although this is not what\n",
    "geometers do) with $n,e_{\\infty}>0$ and $e_2,e_3,g\\ge0$ satisfies $(*)$\n",
    "then there exists a subgroup with these properties."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# One way to use this is to use permutation representation of a given group \n",
    "G = Gamma0(3).as_permutation_group()\n",
    "print(G.permutation_action(S))\n",
    "print(G.permutation_action(R))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But it is also possible to use this to find subgroups.\n",
    "\n",
    "**Exercise**\n",
    "\n",
    "a) Find all valid signatures of index $n=6$.\n",
    "\n",
    "  (Hint: look up the `cartesian_product_iterator` function)\n",
    "\n",
    "b) For each of these signatures, determine the number of\n",
    "subgroups of the modular group with the corresponding signature.\n",
    "\n",
    "c) For each subgroup determine if it is a congruence subgroup or not.\n",
    "  \n",
    "  (Hint: use the builtin constructor `ArithmeticSubgroup_Permutation`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.0",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}