{ "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": [ "" ] }, "execution_count": 47, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "x := Random(g);" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "scrolled": true, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(b*a^-1*b^-1*a^-1)^3*b*a^-1*b^-1*(a^-1*b^-1*(a^-1*b^-1*a^-1*b)^3*a^-1*b^-1*a^-\\\n", "1)^2*b^-1*a^-1*(a^-1*b^-1)^2*a^-1" ] } ], "source": [ "Print(x);" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 49, "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": 50, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 50, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "phi := IsomorphismPermGroup(g);" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "GroupHomomorphismByImages( Group( [ a, b ] ), Group( \n", "[ ( 1, 2)( 3, 5)( 4, 6)( 7,11)( 8,12)( 9,13)(10,14)(16,20)(17,21)(18,22)\n", " (19,23)(25,29)(26,27)(28,30)(31,34)(32,35)(33,36)(37,41)(38,42)(39,43)\n", " (40,44)(45,50)(46,51)(48,52)(49,53)(54,56), \n", " ( 2, 3, 4)( 5, 7, 8)( 6, 9,10)(11,15,14)(12,16,17)(13,18,19)(20,24,23)\n", " (21,25,26)(22,27,28)(29,31,32)(30,33,34)(35,37,38)(36,39,40)(41,45,46)\n", " (42,47,43)(44,48,49)(50,53,54)(51,55,52) ] ), [ a, b ], \n", "[ ( 1, 2)( 3, 5)( 4, 6)( 7,11)( 8,12)( 9,13)(10,14)(16,20)(17,21)(18,22)\n", " (19,23)(25,29)(26,27)(28,30)(31,34)(32,35)(33,36)(37,41)(38,42)(39,43)\n", " (40,44)(45,50)(46,51)(48,52)(49,53)(54,56), \n", " ( 2, 3, 4)( 5, 7, 8)( 6, 9,10)(11,15,14)(12,16,17)(13,18,19)(20,24,23)\n", " (21,25,26)(22,27,28)(29,31,32)(30,33,34)(35,37,38)(36,39,40)(41,45,46)\n", " (42,47,43)(44,48,49)(50,53,54)(51,55,52) ] )" ] } ], "source": [ "Print(phi);" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 52, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "h := ImagesSource(phi);" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "66655" ] }, "execution_count": 53, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Sum(Elements(h), Order);" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "(1,9,31)(2,5,39)(3,27,20)(4,35,55)(6,21,25)(7,37,30)(8,24,51)(11,41,47)(12,28,46)(13,43,38)(14,18,22)(15,53,17)(16,40,23)(19,54,45)(26,56,44)(29,49,32)(33,52,36)(34,42,50)" ] }, "execution_count": 54, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "x := Random(h);" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 55, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "y := PreImagesRepresentative(phi,x);" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "b^-1*a^-1*b*((a^-1*b^-1*a^-1*b)^3*a^-1*b^-1)^2*a^-1*(b^-1*(a*b)^2*a)^2*(b^-1*a\\\n", ")^2*b" ] } ], "source": [ "Print(y);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Other Isomorphism Constructors**\n", "* `Isomorphism[Special]PcGroup`\n", " * pcgroups are usually the fastest representation for solvable groups \n", "* `IsomorphismFpGroup`\n", " * basically only if you want a presentation of your group \n", "* `SmallerDegreePermRep`\n", " * heuristic \n", "* GAP will sometimes do this for you \n", " * see `?NiceMonomorphism` or `?NiceObject` \n", " * but it can be better to do it by hand" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## A Few Homomorphism Operations" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* Part of general mapping (relation) machinery \n", "* `Source` and `Range` (domain and codomain) \n", " * given when the morphism is constructed \n", " * morphism does not need to be total or onto, so they may be bigger than you expect \n", " * `ImagesSource` and `PreImagesRange` may be what you want \n", "* `Image` specialised to `ImageElm` and `ImagesSet`\n", " * which don’t check that the input is in the source \n", "* `PreImagesRepresentative` gives just ONE preimage \n", "* `InverseGeneralMapping` \n", "* `CompositionMapping`" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "Group([ (1,2,3,4), (1,2), (5,6,7) ])" ] }, "execution_count": 57, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "g:=Group((1,2,3,4),(1,2),(5,6,7));" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 58, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "iso:=IsomorphismPcGroup(g);" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 59, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "h:=Image(iso);" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 60, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "z:=Centre(h);" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "SetCentre(g,PreImage(iso,z));" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "[ , , , , , , , , , , , , , , ]" ] }, "execution_count": 62, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "cl:=ConjugacyClasses(h);" ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[ ]" ] }, "execution_count": 63, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "ncl:=[];" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "for c in cl do\n", " nc:=ConjugacyClass(g,PreImage(iso,Representative(c)));\n", " SetSize(nc,Size(c));\n", " SetStabilizerOfExternalSet(nc, PreImage(iso,StabilizerOfExternalSet(c)));\n", " Add(ncl,nc);\n", "od; " ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[ 1, 1, 6, 8, 3, 1, 6, 8, 3, 6, 6, 8, 3, 6, 6 ]" ] }, "execution_count": 65, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "List(ncl,Size);" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "SetConjugacyClasses(g,ncl);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Homorphisms in General\n", "\n", "* Even if you can’t find an isomorphism to a nicer group, you may be able to find a homomorphism \n", "* Solve your problem in the image first and refine" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "Group([ (1,2), (3,4), (5,6), (7,8), (9,10,11), (11,12,13) ])" ] }, "execution_count": 67, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "g := Group((1,2),(3,4),(5,6),(7,8),(9,10,11),(11,12,13));" ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "45" ] }, "execution_count": 68, "metadata": { "text/plain": "" }, "output_type": "execute_result" }, { "data": { "text/plain": [ "960" ] }, "execution_count": 69, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Number(g, x-> Order(x) mod 2 = 1); Size(g);" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ], [ 7, 8 ], [ 9, 10, 11, 12, 13 ] ]" ] }, "execution_count": 70, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Orbits(g,MovedPoints(g));" ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 71, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "phi := ActionHomomorphism(g,[1..8]);" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "" ] } ], "source": [ "Print(phi);" ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "Group([ (1,2), (3,4), (5,6), (7,8) ])" ] }, "execution_count": 73, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "h := ImagesSource(phi);" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[ () ]" ] }, "execution_count": 74, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "odds := Filtered(h, x->Order(x) mod 2 = 1);" ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "[ (), (11,12,13), (11,13,12), (10,11)(12,13), (10,11,12), (10,11,13), (10,12,11), (10,12,13), (10,12)(11,13), (10,13,11), (10,13,12), (10,13)(11,12), (9,10)(12,13), (9,10)(11,12), (9,10)(11,13), (9,10,11), (9,10,11,12,13), (9,10,11,13,12), (9,10,12,13,11), (9,10,12), (9,10,12,11,13), (9,10,13,12,11), (9,10,13), (9,10,13,11,12), (9,11,10), (9,11,12,13,10), (9,11,13,12,10), (9,11)(12,13), (9,11,12), (9,11,13), (9,11)(10,12), (9,11,10,12,13), (9,11,13,10,12), (9,11)(10,13), (9,11,10,13,12), (9,11,12,10,13), (9,12,13,11,10), (9,12,10), (9,12,11,13,10), (9,12,11), (9,12,13), (9,12)(11,13), (9,12,13,10,11), (9,12)(10,11), (9,12,10,11,13), (9,12,10,13,11), (9,12,11,10,13), (9,12)(10,13), (9,13,12,11,10), (9,13,10), (9,13,11,12,10), (9,13,11), (9,13,12), (9,13)(11,12), (9,13,12,10,11), (9,13)(10,11), (9,13,10,11,12), (9,13,10,12,11), (9,13,11,10,12), (9,13)(10,12) ]" ] }, "execution_count": 75, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "p := PreImagesSet(phi,odds);" ] }, { "cell_type": "code", "execution_count": 77, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "60" ] }, "execution_count": 76, "metadata": { "text/plain": "" }, "output_type": "execute_result" }, { "data": { "text/plain": [ "45" ] }, "execution_count": 77, "metadata": { "text/plain": "" }, "output_type": "execute_result" } ], "source": [ "Length(p); Number(p, x->Order(x) mod 2 = 1);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Not all homomorphisms are equal\n", "* If you just make a `GroupHomorphismByImages` (by giving images of generators) \n", " * it can be slow to make because it checks (use `GroupHomorphismByImagesNC` if you are sure you are right) \n", " * Image and preimage computation can be slow, or preimages can be “nasty” (long words in FP group) \n", " * essential because factorisation in terms of generators is not always easy \n", "* `ActionHomorphism` is usually good \n", "* So are most things produced by `IsomorphismXXXGroup`" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Random Tips 1\n", "Avoid long lists of mutable objects\n", "* since the objects in the list might change “under its feet” the list can’t remember \n", " * whether it’s sorted \n", " * whether the entries are all from the same family \n", "* so whenever you try and search it or call an operation on it, it has to look at every element \n", " * can become very slow \n", "* lists of immutable objects are much better \n", "* sorted lists of immutable comparable objects can use binary search" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Random Tips 2\n", "* There are space and time efficient representations of vectors and matrices over finite fields \n", " * up to order 256 in the kernel \n", " * bigger fields in package `cvec`\n", "* Vectors and matrices are not always in these representations by default \n", " * among other reasons because deciding whether this vector is “really” over GF(3) or GF(9) requires prescience \n", "* `ConvertToVectorRep(v, q)` and `ConvertToMatrixRep(m,q)` convert in place \n", "* `cvec` has its own functions \n", "* working with large uncompressed vectors or matrices is a bad idea" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Further Reading\n", "* A lot of this talk was taken from Alexander Hulpke’s talk “Using GAP”, especially section 4 \n", "* You can read the original paper by Alexander Hulpke at http://www.math.colostate.edu/~hulpke/paper/gap4tut.pdf\n", "* A lot of similar ideas are found in Steve Linton's paper \"The Art and Science of Computing in Large Groups\" (in \n", "Bosma & van der Poorten: Computational Algebra and Number Theory, 1995, Springer)" ] } ], "metadata": { "celltoolbar": "Slideshow", "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 }