{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Using GAP Effectively: Some Tips and Pitfalls" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Based on Steve Linton's talk at the Second CoDiMa Training School in Computational Discrete Mathematics (ICMS, Edinburgh, 17-21 October 2016, https://www.codima.ac.uk/school2016/)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Philosophy\n", "\n", "* GAP has two somewhat contradictory design goals\n", " * to allow users to pose questions in a way that seems natural to a working mathematician and get answers\n", " * to allow the expert computational mathematician to implement and apply the most advanced techniques to solve hard problems\n", "* The first is achieved to a limited extent." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Motivating problem:** find an element of $S_9$ which is NOT an involution" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(7,8,9)" ] }, "execution_count": 1, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Filtered(Elements(SymmetricGroup(9)), x-> x*x <> ())[1];" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "* Replace 9 by 10 and it is already visibly longer" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(8,9,10)" ] }, "execution_count": 2, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Filtered(Elements(SymmetricGroup(10)), x-> x*x <> ())[1];" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "* Put n:=15 and you quickly run out of memory: $15!$ is roughly $1.3 \\times 10^{12}$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* Of course GAP is capable of doing the latter calculation\n", "* But you need to acquire certain expertise to ask questions in the right way\n", "* This talk is about how to start thinking like an expert" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## If you don't need it, then don't store it!\n", "\n", "n:=9;; Filtered( Elements(SymmetricGroup(n) ),\n", " x-> x*x <> () )[1];\n", "\n", "* First this computes and stores the full list of elements of $S_n$\n", "* Then it checks each of them to see if it has order 2\n", "* It stores a second list of all of those which don’t\n", "* Finally it returns the first one" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* Instead, we can stop looking when we find one. GAP even provides a built in function to do this:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(7,8,9)" ] }, "execution_count": 3, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "First(Elements(SymmetricGroup(9)), x-> x*x <> ());" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* Stopping things as soon as possible is an important principle\n", "* In this case, however, the real problem is computing and storing all the elements of $S_n$\n", "* Let's explore some other alternatives" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Enumerators" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* Enumerator returns a list of elements of a domain\n", " * this list may be virtual\n", " * also EnumeratorSorted — but only if you need it\n", "* For many objects it is quick to construct, but may be slower to access" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# Do not remove the 2nd semicolon below yet\n", "# See https://github.com/gap-packages/JupyterKernel/issues/72\n", "e := Enumerator(SymmetricGroup(99));;" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000" ] }, "execution_count": 5, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Length(e);" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(2,60,99,55,54,65,7,16,18,32,70,15,5,37,43,97,19,31,66,30,90,17,29,85,28,67,27,62,26,34,52,59)(3,44,73,47,95,45,51,68,50,86,49,83,40,36,81,35,93,12,76,11,75,10,46,9,96,8,53,42,41,22,78,21,38,20,24,63,23,48,39,56,4,6,58,14,80,13,25,33)" ] }, "execution_count": 6, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "e[10^100];" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "See also EnumeratorOfTuples and EnumeratorOfCombinations (both documented) and EnumeratorOfCartesianProduct (currently undocumented)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Iterators" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "* Even an Enumerator can be too heavyweight\n", " * sometimes you don’t need to even number the elements, or know how many there are\n", "* For this GAP has _Iterators_\n", " * IsDoneIterator and NextIterator operations" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "n := 9;; i := Iterator(SymmetricGroup(n));; " ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "while not IsDoneIterator(i) do \n", " x := NextIterator(i); \n", " if x*x <> () then \n", " break; \n", " fi; \n", "od;" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(7,9,8)" ] }, "execution_count": 10, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "x;" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Or more concisely, thanks to some built-in magic:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "n := 9;; \n", "for x in SymmetricGroup(n) do \n", " if x*x <> () then \n", " break; \n", " fi; \n", "od;" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(7,9,8)" ] }, "execution_count": 13, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "x;" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Or even shorter:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(7,9,8)" ] }, "execution_count": 15, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "n := 9;; First(SymmetricGroup(n), x->x*x <> ());" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Randomness" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "* Sometimes you can’t even make an iterator for your group easily, but you know the elements you want exist and are not too rare\n", "* So make pseudo-random elements of the group until you find one" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "SL(10,3)" ] }, "execution_count": 16, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "g := SL(10,3);" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "repeat \n", " x := PseudoRandom(g); \n", "until Order(x) = (3^10-1)/2;" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "[ [ 0*Z(3), Z(3)^0, Z(3), Z(3), Z(3)^0, Z(3)^0, 0*Z(3), Z(3)^0, Z(3), Z(3)^0 ], [ Z(3), Z(3), Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3), Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), Z(3), 0*Z(3), Z(3), 0*Z(3), Z(3), Z(3) ], [ Z(3), 0*Z(3), Z(3), Z(3)^0, Z(3)^0, Z(3), Z(3)^0, Z(3), Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3)^0, Z(3)^0, Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3) ], [ Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3), 0*Z(3), Z(3)^0, Z(3), 0*Z(3), Z(3)^0 ], [ Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3), Z(3)^0, 0*Z(3), 0*Z(3), Z(3), Z(3)^0 ], [ Z(3)^0, Z(3)^0, Z(3), Z(3), Z(3)^0, Z(3), 0*Z(3), Z(3), Z(3), Z(3) ], [ Z(3)^0, Z(3)^0, 0*Z(3), Z(3), Z(3)^0, Z(3), Z(3), Z(3), Z(3), Z(3)^0 ], [ 0*Z(3), Z(3), 0*Z(3), Z(3), Z(3), Z(3)^0, Z(3), Z(3), Z(3)^0, Z(3) ] ]" ] }, "execution_count": 18, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "x;" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " . 1 2 2 1 1 . 1 2 1\n", " 2 2 2 1 . 1 1 2 1 .\n", " . 1 . . 2 . 2 . 2 2\n", " 2 . 2 1 1 2 1 2 1 .\n", " 1 1 1 2 . . . . . 2\n", " 2 1 . 1 2 . 1 2 . 1\n", " 2 1 1 1 2 1 . . 2 1\n", " 1 1 2 2 1 2 . 2 2 2\n", " 1 1 . 2 1 2 2 2 2 1\n", " . 2 . 2 2 1 2 2 1 2\n" ] } ], "source": [ "Display(x);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### But is searching through all the elements the right thing to do in the first place?\n", "* Element order is a conjugacy invariant\n", "* For many groups there are ways of finding conjugacy class representatives that are faster than listing all elements\n", " * or they might be already known and stored" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "(1,2,3)" ] }, "execution_count": 21, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "n := 9;; \n", "Representative(First(ConjugacyClasses(SymmetricGroup(n)),\n", " c->Representative(c)^2 <> ()));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* This is one of the most powerful techniques, especially for non-abelian simple groups and things close to them\n", "* Of course if you are really working in $S_n$ you can simply construct the answer as a permutation" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Narrowing the Search" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "(2,3,5,9,4,7,11)" ] }, "execution_count": 22, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "First(SymmetricGroup(11), \n", " x-> OnTuples([1,2,3,4,5],x) = [1,3,5,7,9] and \n", " Order(x) = 7); " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* For values larger than 12, this gets slow\n", " * because it searches lots of elements that fix 2 before it looks at anything that moves 1 to 2\n", "* Use a bit of maths\n", " * the elements that maps [1,2,3,4,5] to [1,3,5,7,9] lie in a coset of a sequence stabilizer" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "g := SymmetricGroup(12);; s := Stabilizer(g,[1,2,3,4,5],OnTuples);;" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(2,3,5,9,4,7)" ] }, "execution_count": 25, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "r := RepresentativeAction(g,[1,2,3,4,5],[1,3,5,7,9],OnTuples);" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(2,3,5,9,12,4,7)" ] }, "execution_count": 26, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "First(s,x->Order(x*r) = 7)*r;" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## General Principles" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Searching for an element in a group\n", "\n", "* Don’t write down the list of elements first\n", "* Stop when you’ve found it\n", "* Stop looking at other elements as soon as you know they’re not it\n", " * order of a matrix can be large and a bit slow to compute\n", " * if all you care about is whether it is 2, just check for IsOne(x*x) and not IsOne(x)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Searching for an element in a group (2)\n", "\n", "* Try to identify a subgroup, or coset or conjugacy class that it lies in\n", " * remember Sylow subgroups!\n", " * automorphism group sometimes helps too\n", "* Search only in there" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Seaching for a subgroup\n", "\n", "* Even worse — quite small groups can have very many subgroups\n", "* Some kinds that are eas(ier) to find\n", " * Cyclic subgroups (via ConjugacyClasses)\n", " * NormalSubgroups\n", " * Derived, Lower Central etc. series\n", " * Sylow subgroups\n", " * ..." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Seaching for a subgroup (2)\n", "* Some kinds that are eas(ier) to find\n", " * ...\n", " * Maximal subgroups (for some groups)\n", " * MaximalSubgroups will return all subgroups. You are likely to want ony MaximalSubgroupClassReps\n", "* Ask yourself if one of these lists might include the one you want, or at least help you on your way" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Searching for multiple elements" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Conjecture:** $U_3(3)$ cannot be generated by three involutions" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 27, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "g := PSU(3,3);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## So we know some things not to do\n", "* list all 216G triples of elements of $U_3(3)$ and filter out all the ones that generate the group and consist of involutions\n", "* use IteratorOfTuples to run through all 216G ...\n", "* use IteratorOfCombinations to run through 36G of unordered triples\n", "* the same, but test for involutions first\n", " * would take a few hours on a laptop" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## What to do\n", "* find the involutions first (there are just 63 of them) and run over triples" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "invs := Filtered(g, x -> IsOne(x*x) and not IsOne(x));;" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "63" ] }, "execution_count": 29, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Length(invs);" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "iter := IteratorOfCombinations(invs,3);; ct := 0;;\n", "while not IsDoneIterator(iter) do\n", " x := NextIterator(iter);\n", " if Subgroup(g,x) = g then \n", " break; \n", " fi; \n", " ct := ct+1; \n", "od;" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "39711" ] }, "execution_count": 33, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "ct;" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "39711" ] }, "execution_count": 34, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Binomial(63,3);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Searching for multiple elements" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* We still haven’t used conjugacy\n", "* Could choose the 1st involution to be a conjugacy class representative\n", " * there is only one conjugacy class of involutions\n", " * reduce search from Binomial(63,3) to Binomial(62,2)\n", "* The 2nd involution can be chosen up to conjugacy in the centraliser of the first one\n", " * just 4 cases to consider, so the search is now $4 \\times 61$ cases\n", "* Of course the 3rd one can be chosen up to conjugacy in the normaliser of the subgroup generated by the first two\n", "* If the things you are searching for are not all the same, then the order in which you look at them also matters" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Morpheus\n", "\n", "* This type of search for sequences of elements that generate something is nicely implemented by Alexander Hulpke in a part of the GAP library called **Morpheus**\n", "* There are various functions that access morpheus documented in the library under \"Searching for Homomorphisms\"\n", "* Our example is asking whether $U_3(3)$ is a quotient of the free product of three cyclic groups of order 2" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "g:=PSU(3,3);;" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 36, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "F:=FreeGroup(3);" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 37, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "F:=F/[F.1^2,F.2^2,F.3^2];" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[ ]" ] }, "execution_count": 38, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "GQuotients(F,g);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Another Morpheus example" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 39, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "F:=FreeGroup(2);" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 40, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "F:=F/[F.1^2,F.2^6];" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "[ [ f1, f2 ] -> [ (2,4)(5,9)(6,7)(8,10)(11,21)(12,22)(13,20)(14,24)(15,28)(16,27)(17,25)(18,26)(19,23)(38,60)(39,64)(40,59)(41,61)(42,63)(43,58)(44,57)(45,56)(46,62)(47,73)(48,68)(49,69)(50,72)(51,71)(52,65)(53,67)(54,66)(55,70)(74,89)(75,88)(76,90)(77,83)(78,84)(79,87)(80,86)(81,91)(82,85), (1,43,21,15,26,58)(2,91,73)(3,22,89,24,66,25)(4,33)(5,47,13,87,36,12)(6,57,45,78,76,83)(7,17,29,69,16,81)(8,10,77,60,42,50)(9,72,52,51,56,44)(11,48,80,18,67,88)(19,64,46)(20,74,23,54,27,32)(30,59,40,85,86,75)(31,90,62,39,65,34)(35,53,68,70,61,41)(37,82,55)(38,63)(49,84)(71,79) ], [ f1, f2 ] -> [ (2,5)(3,10)(4,6)(7,9)(11,85)(12,83)(13,84)(14,91)(15,86)(16,89)(17,90)(18,88)(19,87)(20,54)(21,53)(22,52)(23,49)(24,47)(25,50)(26,55)(27,51)(28,48)(29,46)(30,41)(31,42)(32,45)(33,44)(34,38)(35,40)(36,39)(37,43)(65,77)(66,78)(67,82)(68,80)(69,79)(70,75)(71,74)(72,76)(73,81), (1,43,21,15,26,58)(2,91,73)(3,22,89,24,66,25)(4,33)(5,47,13,87,36,12)(6,57,45,78,76,83)(7,17,29,69,16,81)(8,10,77,60,42,50)(9,72,52,51,56,44)(11,48,80,18,67,88)(19,64,46)(20,74,23,54,27,32)(30,59,40,85,86,75)(31,90,62,39,65,34)(35,53,68,70,61,41)(37,82,55)(38,63)(49,84)(71,79) ] ]" ] }, "execution_count": 41, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "qs:=GQuotients(F,g);" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 42, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Length(qs);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* So $U_3(3)$ is (2,6)-generated in two distinct ways\n", "* Presented as homomorphisms — easy to recover the generators if you want them\n", "* Other Morpheus functions: AllHomomorphisms, AutomorphismGroup, IsomorphicSubgroups\n", "* A powerful tool for many purposes" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Working in the right Group\n", "* Mathematicians are very sloppy: they constantly identify isomorphic groups\n", "* So $A_5$ \"is\" $PSL(2,5)$ and $SL(2,4)$ and $\\langle a,b \\mid a^2=b^3=(ab)^5=1 \\rangle$ and $\\langle (1,3,6,2,4), (1,2,3)(4,5,6) \\rangle$\n", "* Computationally these are different, so you must choose the right one to work in \n", "* Two tools for moving between them: homomorphisms and straight-line programs" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Finitely Presented Groups\n", "* Lots of functionality in GAP for fp groups — mostly to do with identifying unknown ones \n", "* Lots of textbooks that define groups by presentations, e.g.\n", "$$D_{2n} = \\langle a,b \\mid a^n = (ab)^2 = b^2 = 1 \\rangle$$\n", "* GAP supports some general group theoretic computation with fp groups that turn out to be finite\n", "* But it’s usually the wrong way to do things" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 43, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "f := FreeGroup(\"a\",\"b\");" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "#I Assigned the global variables [ a, b ]\n" ] } ], "source": [ "AssignGeneratorVariables(f);" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 45, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "g := f/[a^2,b^3,(a*b)^7, Comm(a,b)^8];" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "66655" ] }, "execution_count": 46, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Sum(Elements(g), Order);" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "