gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # gap> # gap> # Using the GAP system and its packages for research gap> # -------------------------------------------------- gap> # in graph theory, design theory, and finite geometry gap> # --------------------------------------------------- gap> # gap> # gap> # gap> # gap> # Leonard Soicher, Queen Mary University of London gap> # gap> # gap> # gap> # gap> # G2G2 Minicourse, Rogla and online, 2021 gap> # gap> # gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The GAP system: gap> # --------------- gap> # gap> # gap> # - is an internationally developed computer system for algebra gap> # and discrete mathematics, with an emphasis on computational gap> # group theory gap> # gap> # gap> # - is Open Source, and freely available from https://www.gap-system.org gap> # gap> # gap> # - has a kernel written in C (maybe with bits of C++) gap> # gap> # gap> # - provides the GAP programming language and a library of thousands of gap> # functions written in this language gap> # gap> # gap> # - provides large data libraries of mathematical objects gap> # gap> # gap> # - is used in research and teaching for studying groups and their gap> # representations, rings, vector spaces, algebras, graphs, designs, gap> # finite geometries, and more. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # GAP Packages: gap> # ------------- gap> # gap> # gap> # - are structured extensions to GAP, usually user-contributed gap> # gap> # gap> # - provide extra functionality or data to GAP gap> # gap> # gap> # - usually have their own separate manual gap> # gap> # gap> # - integrate smoothly with GAP and its help system gap> # gap> # gap> # - are distributed with GAP, but package authors get full credit gap> # and remain responsible for the maintenance of their packages gap> # gap> # gap> # - may be "deposited" and/or submitted for formal refereeing. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # This minicourse will: gap> # --------------------- gap> # gap> # gap> # - introduce you to the GAP system and basic programming in the gap> # GAP language gap> # gap> # gap> # - focus on facilities in GAP for computing with group actions gap> # and permutation groups gap> # gap> # gap> # - help you to be able to use the GRAPE package to contruct and gap> # study graphs related to groups, designs, and finite geometries gap> # gap> # gap> # - exhibit parts of the Digraphs package (for computing with gap> # directed graphs and graph homomorphisms) gap> # gap> # gap> # - help you to be able to use the DESIGN package to contruct, gap> # classify, partition, and study block designs gap> # gap> # gap> # - exhibit parts of the FinInG package (for finite incidence gap> # geometry) gap> # gap> # gap> # - present some research applications using GAP, GRAPE, DESIGN, gap> # and FinInG. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Resources for GAP gap> # ----------------- gap> # gap> # gap> # There is much much more to GAP and its packages than I can possibly gap> # cover in one minicourse. Here are some resources to help you with gap> # the minicourse and to learn more. gap> # gap> # gap> # The main GAP website is gap> # gap> # https://www.gap-system.org gap> # gap> # from which you can download the latest version of GAP to install gap> # on your computer. gap> # gap> # gap> # You'll find extensive documentation, including the GAP reference gap> # manual, and learning resources at gap> # gap> # https://www.gap-system.org/Doc/doc.html gap> # gap> # In particular, you should download and read gap> # gap> # [Tut] GAP -- A Tutorial, Release 4.11.1, 2021-03-02, gap> # https://www.gap-system.org/Manuals/doc/tut/manual.pdf gap> # gap> # gap> # You may also wish to look at the course "Programming with GAP" at gap> # gap> # https://alex-konovalov.github.io/gap-lesson/ gap> # gap> # and the online book: gap> # gap> # [AAG] A. Hulpke (with contributions by K. Monks and E. Ziliak), gap> # "Abstract Algebra in GAP", 2011, gap> # https://www.math.colostate.edu/~hulpke/CGT/howtogap.pdf gap> # gap> # gap> # The reference manuals for the packages GRAPE, DESIGN, Digraphs, gap> # and FinInG included with your GAP installation are available from gap> # their entries in gap> # gap> # https://www.gap-system.org/Packages/packages.html gap> # gap> # and via online help in GAP. gap> # gap> # You should consult these manuals for more complete specifications gap> # of the functionality discussed in this minicourse. For even more gap> # in-depth understanding of GAP and its packages, see also their gap> # (open) source code. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Additional references gap> # --------------------- gap> # gap> # gap> # For a very good overview of FinInG (in 2016), see: gap> # gap> # [FinInG] J. Bamberg, A. Betten, P. Cara, J. De Beule, M. Neunhöffer gap> # and M. Lavrauw, FinInG: a package for Finite Incidence Geometry, gap> # https://arxiv.org/abs/1606.05530, 2016. gap> # gap> # gap> # For the theory of permutation groups, I suggest: gap> # gap> # [PJC] P.J. Cameron, "Permutation Groups", Cambridge University gap> # Press, 1999. gap> # gap> # gap> # For a discussion of some of the methods used in GRAPE, see: gap> # gap> # [CGG] L.H. Soicher, Computing with graphs and groups, in "Topics gap> # in Algebraic Graph Theory", L.W. Beineke and R.J. Wilson (eds), gap> # Cambridge University Press, 2004, pp. 250-266. Preprint at: gap> # http://www.maths.qmul.ac.uk/~lsoicher/compgraph.pdf gap> # gap> # gap> # For more on block designs and the DESIGN paackage, see: gap> # gap> # [DGC] L.H. Soicher, Designs, groups and computing, in "Probabilistic gap> # Group Theory, Combinatorics, and Computing. Lectures from the Fifth de gap> # Brún Workshop", A. Detinko et al. (eds), Lecture Notes in Mathematics gap> # 2070, Springer, 2013, pp. 83-107. Preprint at: gap> # http://www.maths.qmul.ac.uk/~lsoicher/debrun_chapter.pdf gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Starting and leaving GAP gap> # ------------------------ gap> # gap> # gap> # I assume you have installed GAP (version at least 4.11.0) on your gap> # computer, together with its included packages GRAPE, Digraphs, gap> # DESIGN, and FinInG (or later versions of these packages) gap> # fully installed. gap> # gap> # gap> # To start GAP, type gap at your computer's command prompt, or gap> # click on the GAP icon under Windows. gap> # gap> # gap> # To start getting help, type ?tutorial:help at the GAP prompt "gap>". gap> # gap> # gap> # To leave GAP, type quit; at the GAP prompt. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # About this file gap> # --------------- gap> # gap> # gap> # This file is a log-file of a non-interactive GAP 4.11.1 computation, gap> # giving many examples with many comments. gap> # gap> # gap> # Comments (like this) start with a "#" and continue until end-of-line. gap> # gap> # gap> # This file mc1_lectures_1-2.gaplog was created by running gap> # gap> # gap < mc1_lectures_1-2.g gap> # gap> # under Linux, where mc1_lectures_1-2.g contains the GAP code and gap> # comments, with first line being: gap> # gap> # LogTo("mc1_lectures_1-2.gaplog"); gap> # gap> # gap> # One could alternatively run a background job under Linux gap> # (bash shell) as: gap> # gap> # gap < mc1_lectures_1-2.g > mc1_lectures_1-2.out 2> mc1_lectures_1-2.err & gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Getting started gap> # --------------- gap> # gap> # gap> # Now let's get started in GAP. Note that GAP expressions are entered gap> # at the gap prompt, they end with a semicolon, they are evaluated when gap> # you press return, and the result of this evaluation is displayed gap> # (to supress this display, end the expression with ";;" instead of ";"). gap> # gap> # gap> # First off, GAP can be used as a calculator for exact computation with gap> # objects such as integers, rational numbers, finite field elements, gap> # permutations, matrices, and more. gap> # gap> a:=5; 5 gap> # gap> # The variable a is bound to (or is assigned) the value 5. gap> # gap> b:=(a^2+2*a-1)/(a^5+7); 17/1566 gap> # gap> # The variable b is bound to the value of the expression on the gap> # right hand side of the assignment operator ":=". gap> # gap> # Variables in GAP can have long descriptive names (called identifiers), gap> # including letters (at least one), digits, and underscores. gap> # See ?variables and ?identifiers. gap> # gap> # Functions are GAP objects, which may be user-defined. gap> # gap> square := function(x) > return x^2; > end; function( x ) ... end gap> # gap> # Now the value of square is the function definition above. gap> # gap> # Let's apply this function to the argument -3. gap> # gap> square(-3); 9 gap> # gap> # Factorial is one of the very many built-in GAP functions. gap> # gap> # Type ?Factorial at the GAP prompt to get help. gap> # gap> # If n is a positive integer, then Factorial(n) is n! . gap> # gap> Factorial(50); 30414093201713378043612608166064768844377641568960512000000000000 gap> # gap> # What happens if we make a mistake? gap> # gap> Factorial(-5); Error, Factorial: must be a non-negative small integer (not the integer -5) not in any function at *stdin*:316 type 'quit;' to quit to outer loop brk> quit; gap> # gap> # Permutations are entered to GAP using disjoint cycle notation. gap> # In GAP, permutations act "on the right". gap> # gap> g:=(1,2,3)(4,5); (1,2,3)(4,5) gap> Order(g); 6 gap> g^2; (1,3,2) gap> h:=g*(1,4)(2,3); (1,3,4,5) gap> 2^g; 3 gap> 2^h; 2 gap> g^h; (1,5)(2,4,3) gap> h^g; (1,5,4,2) gap> h^g=g^(-1)*h*g; true gap> # gap> # This is a boolean expression, evaluating to true or false. gap> # We are determining whether h^g is equal to g^(-1)*h*g gap> # (which it is). Note that we are using "=", not ":=". gap> # gap> h^g=g^h; false gap> # gap> # The boolean values in GAP are true and false (and for gap> # special purposes, fail). gap> # gap> true or false; true gap> (6 mod 3 = 0) and 5 < 3; false gap> (not 5 > 3) = (5 <= 3); true gap> # gap> # The logical operator or has lower precedence than the operator and, gap> # which has lower precedence than the operator not. gap> # gap> # If in any doubt concerning operator precedence, use parentheses in a gap> # GAP expression to clarify your intention. gap> # gap> # ===================================================================== gap> # gap> # gap> # Data structures in GAP gap> # ---------------------- gap> # gap> # gap> # The two most basic ways to structure data in GAP are lists and records. gap> # gap> # gap> # We start with lists. gap> # gap> L:=[1,2,-5,0,2]; [ 1, 2, -5, 0, 2 ] gap> # gap> # Here the object that L is bound to is the list having gap> # value [1,2,-5,0,2]. gap> # gap> # gap> # In a list, the order of the elements and repeated elements matter. gap> # The element of a list L in position i is obtained as L[i]. gap> # gap> L[4]; 0 gap> M:=L; [ 1, 2, -5, 0, 2 ] gap> # gap> # Now M is bound to the same object as L. gap> # gap> # What happens when we change this object? gap> # Let's assign a new value to the third element of M. gap> # gap> M[3]:=20; 20 gap> M; [ 1, 2, 20, 0, 2 ] gap> L; [ 1, 2, 20, 0, 2 ] gap> M:=[3,6,12]; [ 3, 6, 12 ] gap> # gap> # So now M is bound to a new list object, but L is not. gap> # gap> M[4]; Error, List Element: [4] must have an assigned value not in any function at *stdin*:385 type 'quit;' to quit to outer loop brk> quit; gap> M; [ 3, 6, 12 ] gap> L; [ 1, 2, 20, 0, 2 ] gap> L:=[7,-12,1,12,11,3,-5,0,11]; [ 7, -12, 1, 12, 11, 3, -5, 0, 11 ] gap> # gap> # Now L is bound to a new list object. gap> # gap> # Let's make a new list S, formed by applying our function square gap> # to each element of L. gap> # gap> S:=List(L,square); [ 49, 144, 1, 144, 121, 9, 25, 0, 121 ] gap> # gap> # In GAP, elements of lists can be of any type, such as integers, rationals, gap> # functions, permutations, and lists themselves. gap> # gap> matrix:=[[1,2,3],[-4,-5,-6],[7,8,9]]; [ [ 1, 2, 3 ], [ -4, -5, -6 ], [ 7, 8, 9 ] ] gap> matrix[2]; [ -4, -5, -6 ] gap> matrix[2][3]; -6 gap> matrix^2; [ [ 14, 16, 18 ], [ -26, -31, -36 ], [ 38, 46, 54 ] ] gap> Determinant(matrix); 0 gap> # gap> # GAP contains many operations for lists. See ?Lists gap> # gap> C:=Concatenation([1,2,3],[3,2,1]); [ 1, 2, 3, 3, 2, 1 ] gap> Length(C); 6 gap> Add(C,25); gap> C; [ 1, 2, 3, 3, 2, 1, 25 ] gap> # gap> # In GAP, if L is a list, then Length(L) is the position gap> # of the last bound element of L. gap> # gap> Length(C); 7 gap> Length(matrix); 3 gap> F:=Flat(matrix); [ 1, 2, 3, -4, -5, -6, 7, 8, 9 ] gap> Length(F); 9 gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Sets in GAP gap> # ----------- gap> # gap> # gap> # Many types of GAP objects can be ordered by "<". gap> # gap> # The ordering for rationals is the the usual one, and lists gap> # of objects that can be ordered by < are themselves ordered gap> # lexicographically by <. gap> # gap> 5<3; false gap> [3,0,1,3]<[3,0,2,3]; true gap> Factorial( ) called from read-eval loop at *stdin*:436 type 'quit;' to quit to outer loop brk> quit; gap> # gap> # A *dense* list is a list with no "holes", that is, the list gap> # is empty or has no unbound entries before the last bound entry. gap> # gap> # A (*proper*) *set* in GAP is a dense list that is strictly sorted gap> # w.r.t. <. See ?Sets gap> # gap> IsSet([]); true gap> IsSet([1,2,3]); true gap> IsSet([1,3,2]); false gap> IsSet([1,2,2,3]); false gap> IsSet([1,,2,3]); false gap> Length([1,,2,3]); 4 gap> L; [ 7, -12, 1, 12, 11, 3, -5, 0, 11 ] gap> IsSet(L); false gap> L:=Set(L); [ -12, -5, 0, 1, 3, 7, 11, 12 ] gap> IsSet(L); true gap> M; [ 3, 6, 12 ] gap> IsSet(M); true gap> P:=Set([(1,2,3),(4,5),(),(1,3,2)]); [ (), (4,5), (1,2,3), (1,3,2) ] gap> AddSet(P,(2,3,4,5)); gap> P; [ (), (4,5), (2,3,4,5), (1,2,3), (1,3,2) ] gap> [1..5]=[1,2,3,4,5]; # [1..5] is an example of a "range" in GAP. true gap> # gap> # The most useful type of *range* in GAP is of the form gap> # gap> # [first..last] gap> # gap> # where first and last are integers. gap> # gap> # If first <= last, then [first..last] is the GAP set having gap> # elements first,first+1,...,last. gap> # gap> # If first > last, then [first..last] is the empty list []. gap> # gap> # See ?range. gap> # gap> r:=[-3..2]; [ -3 .. 2 ] gap> Length(r); 6 gap> IsRange(r); true gap> IsSet(r); true gap> r:=[2..-3]; [ ] gap> Length(r); 0 gap> IsRange(r); true gap> IsSet(r); true gap> # gap> # ===================================================================== gap> # gap> # gap> # Set functions gap> # ------------- gap> # gap> # There are certain functions applicable to sets and "collections" gap> # in GAP, which behave how you might expect. gap> # gap> # The most important kinds of *collections* are nonempty homogeneous gap> # lists (see ?IsHomogeneousList ), and "domains", to be discussed later. gap> # gap> L; [ -12, -5, 0, 1, 3, 7, 11, 12 ] gap> M; [ 3, 6, 12 ] gap> IsSubset(L,M); false gap> 1 in L; true gap> 1 in M; false gap> Intersection(L,M); [ 3, 12 ] gap> U:=Union(L,M); [ -12, -5, 0, 1, 3, 6, 7, 11, 12 ] gap> Size(U); 9 gap> IsSubset(U,L); true gap> IsSubset(L,U); false gap> Difference(L,M); [ -12, -5, 0, 1, 7, 11 ] gap> L:=Reversed(L); [ 12, 11, 7, 3, 1, 0, -5, -12 ] gap> Add(M,M[1]); gap> M; [ 3, 6, 12, 3 ] gap> IsSet(L); false gap> IsCollection(L); true gap> IsSet(M); false gap> IsCollection(M); true gap> Intersection(L,M); [ 3, 12 ] gap> Union(L,M); [ -12, -5, 0, 1, 3, 6, 7, 11, 12 ] gap> Difference(L,M); [ -12, -5, 0, 1, 7, 11 ] gap> M[6]:=23; 23 gap> M; [ 3, 6, 12, 3,, 23 ] gap> IsCollection(M); false gap> IsBound(M[5]); false gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Records in GAP gap> # -------------- gap> # gap> # gap> # In a list, the elements are indexed by integers, starting at 1. gap> # gap> # In a record, the elements (called components) are accessed by gap> # identifiers (names). gap> # gap> # gap> minicourse:=rec(teacher:="Soicher", subject:="GAP", lecture_hours:=8); rec( lecture_hours := 8, subject := "GAP", teacher := "Soicher" ) gap> minicourse.teacher; "Soicher" gap> minicourse.lab_hours:=3; 3 gap> minicourse; rec( lab_hours := 3, lecture_hours := 8, subject := "GAP", teacher := "Soicher" ) gap> new_minicourse:=StructuralCopy(minicourse); rec( lab_hours := 3, lecture_hours := 8, subject := "GAP", teacher := "Soicher" ) gap> # gap> # I made a structural copy since I don't want any changes to gap> # new_minicourse to cause changes in minicourse. gap> # See ?ShallowCopy and ?StructuralCopy. gap> # gap> # Also see ?Immutable regarding making lists or records gap> # whose value cannot be changed. gap> # gap> new_minicourse.subject:="Permutation groups"; "Permutation groups" gap> new_minicourse.level:="PhD student"; # new record component "PhD student" gap> new_minicourse; rec( lab_hours := 3, lecture_hours := 8, level := "PhD student", subject := "Permutation groups", teacher := "Soicher" ) gap> minicourse; rec( lab_hours := 3, lecture_hours := 8, subject := "GAP", teacher := "Soicher" ) gap> minicourse:=Immutable(minicourse); rec( lab_hours := 3, lecture_hours := 8, subject := "GAP", teacher := "Soicher" ) gap> minicourse.level:="PhD student"; Error, Record Assignment: must be a mutable record not in any function at *stdin*:552 type 'quit;' to quit to outer loop brk> quit; gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Domains and groups in GAP gap> # ------------------------- gap> # gap> # gap> # In GAP a *domain* is an object having an underlying set with gap> # (algebraic) structure. gap> # gap> # For example, groups, fields, and vector spaces are domains in GAP. gap> # gap> # The underlying set of a domain D is not usually stored explicitly, gap> # but if not too large, may be obtained by applying the function AsSet gap> # to D (to obtain an explicit immutable set). gap> # gap> # Two domains are considered to be equal iff their underlying sets gap> # are equal, and domains can be used as arguments of set functions gap> # such as Intersection and Union, and if possible, GAP tries to gap> # return the result as a domain. gap> # gap> # GAP provides a huge amount of functionality for computing with gap> # groups of different types. In this minicourse, we concentrate gap> # on permutation groups. gap> # gap> G:=Group([(1,2,6), (1,2,3,4,5)]); Group([ (1,2,6), (1,2,3,4,5) ]) gap> # G is now the group generated by (1,2,6) and (1,2,3,4,5) gap> # The domain G is an "attribute storing" object. gap> KnownAttributesOfObject(G); [ "LargestMovedPoint", "GeneratorsOfMagmaWithInverses", "MultiplicativeNeutralElement" ] gap> IsSet(G); false gap> IsDomain(G); true gap> IsCollection(G); true gap> Size(G); 360 gap> KnownAttributesOfObject(G); [ "Size", "OneImmutable", "LargestMovedPoint", "NrMovedPoints", "MovedPoints", "GeneratorsOfMagmaWithInverses", "MultiplicativeNeutralElement", "StabChainMutable", "StabChainOptions" ] gap> C:=Centralizer(G,(1,2)(3,4)); Group([ (1,2)(3,4), (1,2)(5,6), (1,3)(2,4) ]) gap> AsSet(C); [ (), (3,4)(5,6), (1,2)(5,6), (1,2)(3,4), (1,3)(2,4), (1,3,2,4)(5,6), (1,4,2,3)(5,6), (1,4)(2,3) ] gap> DerivedSubgroup(C); Group([ (1,2)(3,4) ]) gap> H:=Subgroup(G,[(1,2,3)]); # the subgroup of G generated by (1,2,3) Group([ (1,2,3) ]) gap> N:=Normalizer(G,H); Group([ (1,2,3), (4,5,6), (2,3)(5,6) ]) gap> K:=Intersection(C,N); Group([ (1,2)(5,6) ]) gap> AsSet(K); [ (), (1,2)(5,6) ] gap> Union(C,N); [ (), (4,5,6), (4,6,5), (3,4)(5,6), (2,3)(5,6), (2,3)(4,5), (2,3)(4,6), (1,2)(5,6), (1,2)(4,5), (1,2)(4,6), (1,2)(3,4), (1,2,3), (1,2,3)(4,5,6), (1,2,3)(4,6,5), (1,3,2), (1,3,2)(4,5,6), (1,3,2)(4,6,5), (1,3)(5,6), (1,3)(4,5), (1,3)(4,6), (1,3)(2,4), (1,3,2,4)(5,6), (1,4,2,3)(5,6), (1,4)(2,3) ] gap> # gap> # gap> # It is possible for users to contruct their own domains in GAP, but gap> # that is beyond the scope of this minicourse. gap> # gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Programming in GAP gap> # ------------------ gap> # gap> # GAP provides a programming language (the GAP language) for gap> # users and developers. gap> # gap> # The main control structures are if-statements, for-loops, gap> # while-loops, and repeat-loops. These control blocks of gap> # statements, called statement-sequences, which are of the form: gap> # gap> # statement {statement} gap> # gap> # that is, a sequence of one or more GAP statements, each terminated gap> # by a semicolon. gap> # gap> # gap> # Note: We use the syntax notation that [thing] means gap> # to repeat a programming element of type thing 0 or 1 times, gap> # and {thing} means to repeat a programming element of type gap> # thing 0 or more times. gap> # gap> # gap> # User-defined functions allow a user to further structure their gap> # programs and to add new features. gap> # gap> # gap> # We shall not cover programming related to the more advanced gap> # concepts in GAP, such as families, categories, representations, gap> # attributes, properties, filters, method selection, file handling, gap> # and streams. See Chapter 8 of [Tut] and the GAP reference manual gap> # for help on these. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # if-statement in GAP gap> # ------------------- gap> # gap> # gap> # In GAP, an if-statement has the form: gap> # gap> # gap> # if boolean-expression then gap> # statement-sequence gap> # { elif boolean-expression then gap> # statement-sequence } gap> # [ else gap> # statement-sequence ] gap> # fi; gap> # gap> # An if-statement is executed as follows. gap> # gap> # First, the boolean expression after the if is evaluated. gap> # If true, then the statement sequence following the then gap> # is executed, and the execution of the if-statement is complete gap> # (and the program continues after the fi; ). gap> # gap> # Otherwise, if there are one or more elif parts, the boolean gap> # expression following each elif is evaluated in turn. gap> # As soon as such an expression evaluates to true the corresponding gap> # statement sequence is executed, and execution of the if-statement gap> # is complete. gap> # gap> # Now suppose the boolean expression after the if evaluates to gap> # false and all, if any, elif boolean expressions evaluate to false. gap> # If there is no else part, then the execution of the if-statement gap> # is complete without executing any of the statement sequences, gap> # but if there is an else part, then the statement squence immediately gap> # following the else is executed, before completing the if-statement. gap> # gap> # gap> # Example gap> # ------- gap> # gap> i := -10;; gap> if i > 0 then > sign := 1; > elif i < 0 then > sign := -1; > else > sign := 0; > fi; gap> sign; # the sign of the integer i -1 gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # for-loop in GAP gap> # ---------------- gap> # gap> # In GAP, the basic form of a for-loop is: gap> # gap> # for var in L do gap> # statement-sequence gap> # od; gap> # gap> # where var is a simple variable (not a list-element selection gap> # or a record-component selection), and L is a list. gap> # gap> # This for-loop executes the statement-sequence for every element of gap> # the list L, first with var bound to the first element of L, gap> # then with var bound to the next element of L, and so on. gap> # gap> # gap> # Example gap> # ------- gap> # gap> # We make a list of the first n Fibonacci numbers. gap> # gap> n:=20; 20 gap> fib:=[]; [ ] gap> for i in [1..n] do > if i <= 2 then > fib[i]:=1; > else > fib[i]:=fib[i-2]+fib[i-1]; > fi; > od; gap> fib; [ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ] gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # while-loop in GAP gap> # ----------------- gap> # gap> # gap> # In GAP, a while-loop has the form: gap> # gap> # while boolean-expression do gap> # statement-sequence gap> # od; gap> # gap> # This while-loop executes the statement sequence while gap> # boolean-expression is true. gap> # gap> # More precisely, the while-loop evaluates the boolean expression. gap> # If false, the while-loop terminates, the statement sequence is not gap> # executed, and the program continues after the od; . If true, the gap> # statement-sequence is executed, and the whole process repeats. gap> # gap> # gap> # Example gap> # ------- gap> # gap> G:=MathieuGroup(24); Group([ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23), (3,17,10,7,9)(4,13,14,19,5)(8,18,11,12,23)(15,20,22,21,16), (1,24)(2,23) (3,12)(4,16)(5,18)(6,10)(7,20)(8,14)(9,21)(11,17)(13,22)(15,19) ]) gap> g:=Random(G);; # a (pseudo-)random element of G gap> count:=1; 1 gap> while Order(g)<>7 do > g:=Random(G); > count:=count+1; > od; gap> g; (1,3,21,13,18,23,2)(4,12,6,15,24,22,5)(7,17,19,10,8,11,9) gap> count; 7 gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # repeat-loop in GAP gap> # ------------------ gap> # gap> # gap> # A repeat-loop in GAP has the form gap> # gap> # repeat gap> # statement-sequence gap> # until boolean-expression; gap> # gap> # The execution of this loop is as follows. First, the statement sequence gap> # is executed. Then the boolean expression is evaluated. If true, then the gap> # repeat-loop terminates, and the program continues immediately after. gap> # If false, the whole process repeats. gap> # gap> # gap> # Note that in a repeat loop, the statement-sequence is executed at gap> # least once. gap> # gap> # gap> # Example gap> # ------- gap> # gap> count:=0; 0 gap> repeat > g:=Random(G); > count:=count+1; > until Order(g)=7; gap> g; (1,20,10,23,22,14,3)(2,24,8,11,17,7,5)(4,6,15,12,18,19,9) gap> count; 6 gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # break and continue statements gap> # ----------------------------- gap> # gap> # gap> # These statements can be used only within a loop in GAP. gap> # gap> # gap> # The statement gap> # gap> # break; gap> # gap> # forces an immediate exit from the innermost loop enclosing it. gap> # gap> # gap> # The statement gap> # gap> # continue; gap> # gap> # causes the rest of the current statement-sequence of the gap> # innermost loop enclosing it to be skipped. gap> # gap> # gap> # Example gap> # ------- gap> # gap> count:=0; 0 gap> repeat > g:=Random(G); > count:=count+1; > if Order(g)=7 then > break; > fi; > until false; gap> g; (1,17,24,19,16,6,22)(2,8,14,7,13,11,18)(4,5,12,21,10,15,9) gap> count; 36 gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # User-defined functions in GAP gap> # ------------------------------ gap> # gap> # gap> # A basic function definition in GAP has the syntax: gap> # gap> # function( formal-parameters ) gap> # gap> # [ local local-identifiers; ] gap> # gap> #    statement-sequence gap> # gap> # end gap> # gap> # The sequence of formal parameters may be empty, or simple variable gap> # names separated by commas. These variables and their names are gap> # local to the function. (See also ?reference:arg ) gap> # gap> # If necessary, the names of further local variables to be used by gap> # the function are given in a comma-separated sequence after gap> # the keyword local, with the sequence terminated by a semi-colon. gap> # gap> # When the function is called (executed), the actual parameters gap> # given in the function call are assigned to (or bound to) the gap> # corresponding formal parameters. gap> # gap> # Then the statement sequence is executed. gap> # gap> # If the statement gap> # gap> # return [expression]; gap> # gap> # is executed, then this terminates the execution of the function, gap> # and control is returned to the calling program (or calling function). gap> # If no expression is given, then no value is returned by the function. gap> # Otherwise the expression is evaluted and its value is returned gap> # by the function. gap> # gap> # gap> # Note: gap> # gap> # x -> expression; gap> # gap> # is a shorthand for gap> # gap> # function(x) return expression; end; gap> # gap> # gap> # Examples gap> # -------- gap> # gap> # gap> increment := i->i+1; function( i ) ... end gap> increment(14); 15 gap> gap> SumOfDivisors := function(n) > # > # For n a positive integer, this function returns > # the sum of the positive divisors of n. > # > local sum,d; > if not IsPosInt(n) then > Error("usage: SumOfDivisors( )"); > fi; > sum:=0; > d:=1; > while d^2 <= n do > if n mod d = 0 then > sum := sum+d; > if d^2 < n then > sum := sum + n/d; > fi; > fi; > d:=d+1; > od; > return sum; > end; function( n ) ... end gap> gap> SumOfDivisors(1); 1 gap> SumOfDivisors(6); 12 gap> SumOfDivisors(20); 42 gap> SumOfDivisors(20+3); 24 gap> SumOfDivisors(49); 57 gap> gap> # gap> # ===================================================================== gap> # gap> # gap> # Group actions in GAP gap> # -------------------- gap> # gap> # gap> # Mathematically, an *action* of a group G on a set S is a function gap> # gap> # mu : S x G --> S, gap> # gap> # such that mu(s,1) = s and mu( mu(s,g), h ) = mu(s, gh), gap> # for all s in S and all g,h in G. gap> # gap> # gap> # GAP has extensive functionality to handle group actions, with gap> # many built-in actions available, as well as the ability to handle gap> # user-defined actions. We look at some of these facilities. gap> # gap> g:=(1,2,3)(4,5); (1,2,3)(4,5) gap> h:=g*(1,4)(2,3); (1,3,4,5) gap> 2^g; 3 gap> OnPoints(2,g); 3 gap> g^h=OnPoints(g,h); true gap> OnSets([1,3,5],g); [ 1, 2, 4 ] gap> OnTuples([1,3,5],g); [ 2, 1, 4 ] gap> OnTuples([5,3,1],g); [ 4, 1, 2 ] gap> OnSetsSets([[1,3,5],[4],[4,5]],g); [ [ 1, 2, 4 ], [ 4, 5 ], [ 5 ] ] gap> OnSetsDisjointSets([[1,3],[2,5],[4]],g); [ [ 1, 2 ], [ 3, 4 ], [ 5 ] ] gap> gap> OnMultisets := function(x,g) > # > # Here we define the action of a permutation group on > # the set of multisets of points, where a multiset is > # represented by a sorted list of points. > # > if not IsSortedList(x) then > Error("multiset must be a sorted list"); > fi; > return SortedList(OnTuples(x,g)); > end; function( x, g ) ... end gap> gap> OnMultisets([1,3,5],g); [ 1, 2, 4 ] gap> OnMultisets([1,3,3,5,5],g); [ 1, 1, 2, 4, 4 ] gap> OnMultisets([3,1,3,5,5],g); Error, multiset must be a sorted list at *stdin*:965 called from ( ) called from read-eval loop at *stdin*:972 you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> quit; gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Orbits and stabilizers gap> # ---------------------- gap> # gap> # gap> # Suppose that mu is an action of a group G on a set S, gap> # and let s in S. gap> # gap> # The *G-orbit* (or simply *orbit*) of s (w.r.t. mu) is gap> # { mu(s,g) | g in G}. gap> # gap> # It is not difficult to see that the set of all G-orbits of gap> # the elements in S forms a partition of S. gap> # gap> # The *G-stabilizer* (or simply *stabilizer*) of s (w.r.t. mu) gap> # is { g in G | mu(s,g)=s }. gap> # gap> # Let H be the G-stabilizer of s. The Orbit-Stabilizer theorem gap> # states that: gap> # gap> # - H is a subgroup of G gap> # gap> # - there is a 1-to-1 correspondence between the set of (right) cosets gap> # of H in G and the G-orbit of s gap> # gap> # - if G is finite then |G| = n|H|, where n is the cardinality gap> # of the G-orbit of s. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Orbits and stabilizers in GAP gap> # ----------------------------- gap> # gap> # gap> G:=Group(g,h); Group([ (1,2,3)(4,5), (1,3,4,5) ]) gap> # gap> # Now G is the (permutation) group generated by g and h. gap> # gap> Size(G); 120 gap> s:=[1,2]; [ 1, 2 ] gap> mu:=OnSets; function( set, elm ) ... end gap> orb:=Orbit(G,s,mu); [ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 2, 4 ], [ 3, 4 ], [ 3, 5 ], [ 2, 5 ], [ 1, 5 ], [ 4, 5 ], [ 1, 4 ] ] gap> n:=Length(orb); 10 gap> H:=Stabilizer(G,s,mu); Group([ (4,5), (3,5), (1,2)(4,5) ]) gap> Size(H); 12 gap> Size(G)=n*Size(H); true gap> # gap> # Note that an orbit is not sorted by GAP automatically, so we gap> # must apply the function Set to an orbit to make it into gap> # a GAP set. gap> # gap> orb:=Set(orb); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ] gap> m:=[1,3,3,5,5];; gap> # gap> # Let's calculate the G-orbit of the multiset m under the gap> # action OnMultisets. gap> # gap> orb:=Orbit(G,m,OnMultisets); [ [ 1, 3, 3, 5, 5 ], [ 1, 1, 2, 4, 4 ], [ 1, 1, 3, 4, 4 ], [ 2, 2, 3, 5, 5 ], [ 2, 3, 3, 5, 5 ], [ 1, 2, 2, 5, 5 ], [ 3, 3, 4, 5, 5 ], [ 1, 3, 3, 4, 4 ], [ 1, 1, 2, 2, 4 ], [ 2, 3, 3, 4, 4 ], [ 1, 1, 2, 2, 3 ], [ 1, 1, 4, 4, 5 ], [ 1, 1, 2, 5, 5 ], [ 3, 4, 4, 5, 5 ], [ 2, 2, 3, 3, 5 ], [ 1, 1, 3, 5, 5 ], [ 2, 4, 4, 5, 5 ], [ 1, 2, 2, 3, 3 ], [ 2, 2, 3, 3, 4 ], [ 2, 2, 4, 5, 5 ], [ 2, 2, 3, 4, 4 ], [ 1, 1, 2, 3, 3 ], [ 1, 4, 4, 5, 5 ], [ 1, 1, 4, 5, 5 ], [ 1, 1, 3, 3, 4 ], [ 1, 2, 2, 4, 4 ], [ 1, 1, 3, 3, 5 ], [ 2, 2, 4, 4, 5 ], [ 3, 3, 4, 4, 5 ], [ 1, 1, 2, 2, 5 ] ] gap> n:=Length(orb); 30 gap> H:=Stabilizer(G,m,OnMultisets); Group([ (2,4)(3,5), (2,4) ]) gap> Size(H); 4 gap> Size(G)=n*Size(H); true gap> gap> omega := Combinations([1,1,2,2,3,3,4,4,5,5],5);; gap> orbs := Orbits(G,omega,OnMultisets); [ [ [ 1, 1, 2, 2, 3 ], [ 1, 2, 2, 3, 3 ], [ 2, 2, 3, 3, 4 ], [ 1, 1, 2, 3, 3 ], [ 2, 2, 3, 4, 4 ], [ 1, 1, 3, 3, 5 ], [ 2, 2, 4, 4, 5 ], [ 2, 3, 3, 4, 4 ], [ 1, 3, 3, 5, 5 ], [ 2, 2, 4, 5, 5 ], [ 1, 1, 2, 2, 4 ], [ 1, 3, 3, 4, 4 ], [ 3, 3, 4, 5, 5 ], [ 1, 2, 2, 5, 5 ], [ 1, 1, 3, 5, 5 ], [ 2, 4, 4, 5, 5 ], [ 1, 1, 2, 4, 4 ], [ 1, 1, 3, 4, 4 ], [ 3, 3, 4, 4, 5 ], [ 1, 1, 2, 2, 5 ], [ 2, 2, 3, 3, 5 ], [ 1, 1, 2, 5, 5 ], [ 3, 4, 4, 5, 5 ], [ 1, 1, 4, 4, 5 ], [ 1, 2, 2, 4, 4 ], [ 1, 1, 3, 3, 4 ], [ 2, 2, 3, 5, 5 ], [ 2, 3, 3, 5, 5 ], [ 1, 1, 4, 5, 5 ], [ 1, 4, 4, 5, 5 ] ], [ [ 1, 1, 2, 3, 4 ], [ 1, 2, 2, 3, 5 ], [ 2, 3, 3, 4, 5 ], [ 1, 2, 3, 3, 4 ], [ 1, 2, 2, 3, 4 ], [ 1, 1, 3, 4, 5 ], [ 1, 2, 4, 4, 5 ], [ 1, 1, 2, 3, 5 ], [ 2, 3, 4, 4, 5 ], [ 1, 2, 3, 3, 5 ], [ 2, 2, 3, 4, 5 ], [ 1, 2, 2, 4, 5 ], [ 1, 3, 3, 4, 5 ], [ 2, 3, 4, 5, 5 ], [ 1, 2, 3, 5, 5 ], [ 1, 3, 4, 5, 5 ], [ 1, 2, 4, 5, 5 ], [ 1, 2, 3, 4, 4 ], [ 1, 1, 2, 4, 5 ], [ 1, 3, 4, 4, 5 ] ], [ [ 1, 2, 3, 4, 5 ] ] ] gap> List(orbs,Length); [ 30, 20, 1 ] gap> # gap> # Note that the list of orbits is not sorted in any way by GAP. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Action homomorphisms gap> # -------------------- gap> # gap> # gap> # An action mu of a group G on a set S determines a homomorphism gap> # from G to a group of permutations of S. If g in G, then the image gap> # pi of g is defined by s^pi = mu(s,g), for all s in S. gap> # gap> # In GAP, where G is a group and L is a G-invariant dense list for gap> # the action mu, the function call gap> # gap> # ActionHomomorphism(G,L,mu) gap> # gap> # returns the homomorphism for the action of G on L via the function gap> # mu. The image of this homomorphism is represented as a subgroup of gap> # SymmetricGroup([1..Length(L)]), with point i corresponding to the gap> # i-th element in the list L. gap> # gap> hom := ActionHomomorphism(G,omega,OnMultisets); gap> Kernel(hom); Group(()) gap> GG := Image(hom); gap> Size(GG); 120 gap> g:=(1,2,3); (1,2,3) gap> gg:=Image(hom,g); (1,17,4)(2,36,10)(3,37,11)(5,18,23)(6,19,24)(7,38,30)(8,39,31)(9,40,32)(12,20, 43)(13,21,44)(14,22,45)(15,41,49)(16,42,50)(28,46,33)(29,47,34)(35,48,51) gap> C:=Centralizer(G,g); Group([ (1,2,3), (4,5), (1,2,3)(4,5) ]) gap> Image(hom,C); gap> orbs:=Orbits(GG,[1..Length(omega)],OnPoints); [ [ 1, 17, 36, 4, 38, 11, 41, 43, 32, 42, 2, 30, 50, 22, 14, 48, 7, 12, 49, 3, 37, 9, 51, 15, 20, 10, 40, 45, 16, 35 ], [ 5, 19, 44, 23, 18, 13, 28, 6, 46, 24, 39, 21, 31, 47, 27, 34, 29, 25, 8, 33 ], [ 26 ] ] gap> List(orbs,Length); [ 30, 20, 1 ] gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The Mathieu group M_{24} gap> # ------------------------ gap> # gap> n:=24; 24 gap> M24:=MathieuGroup(n); Group([ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23), (3,17,10,7,9)(4,13,14,19,5)(8,18,11,12,23)(15,20,22,21,16), (1,24)(2,23) (3,12)(4,16)(5,18)(6,10)(7,20)(8,14)(9,21)(11,17)(13,22)(15,19) ]) gap> # gap> # Now M24 is the sporadic simple Mathieu group M_{24}, the gap> # automorphism group of the (unique up to isomorphism) 5-(24,8,1) gap> # design, whose blocks are a set of 759 8-element subsets gap> # (called *octads*) of the points [1..24], such that gap> # every 5-element subset of these points is contained in exactly gap> # one octad. gap> # gap> # Let's find the octad containing [1,2,3,4,5]. gap> # gap> L:=[1..5]; [ 1 .. 5 ] gap> H:=Stabilizer(M24,L,OnSets); gap> # gap> # Since H fixes L, H must fix the unique octad containing L. gap> # gap> orbs:=Orbits(H,[1..n]); [ [ 1, 2, 3, 4, 5 ], [ 6, 22, 24, 9, 14, 23, 7, 17, 21, 10, 18, 19, 15, 16, 12, 20 ], [ 8, 11, 13 ] ] gap> # gap> # So the octad containing L must be the union of L and gap> # the H-orbit of length 3. gap> # gap> for orb in orbs do > if Length(orb)=3 then > octad1:=Union(L,orb); > break; > fi; > od; gap> octad1; [ 1, 2, 3, 4, 5, 8, 11, 13 ] gap> # gap> # Now we find the stabilizer of our octad. gap> # gap> octad1_stab:=Stabilizer(M24,octad1,OnSets);; gap> # gap> # And the M24-orbit of our octad. gap> # gap> octads:=Set(Orbit(M24,octad1,OnSets));; gap> Length(octads); 759 gap> # gap> # So M24 is transitive in its action on the set of octads, gap> # that is, it has just one orbit on octads. gap> # gap> # Now we consider the homomorphism for the action of gap> # octad1_stab on the points of octad1. gap> # gap> hom:=ActionHomomorphism(octad1_stab,octad1,OnPoints);; gap> im:=Image(hom); Group([ (1,7,2)(3,8)(4,6), (2,4,3), (2,5)(3,4), (6,7,8), (5,7)(6,8), (4,7) (5,8) ]) gap> Size(im); 20160 gap> ker:=Kernel(hom); gap> Size(ker); 16 gap> IsElementaryAbelian(ker); true gap> # gap> # In fact, GAP can compute the composition series of octad1_stab. gap> # gap> DisplayCompositionSeries(octad1_stab); G (8 gens, size 322560) | A(8) ~ A(3,2) = L(4,2) ~ D(3,2) = O+(6,2) S (4 gens, size 16) | Z(2) S (3 gens, size 8) | Z(2) S (2 gens, size 4) | Z(2) S (1 gens, size 2) | Z(2) 1 (0 gens, size 1) gap> # gap> # Finally, we determine the set consisting of the sizes of the gap> # intersections of octad1 with the elements in octads. gap> # gap> octad_intersection_sizes:=[]; [ ] gap> for octad in octads do > AddSet(octad_intersection_sizes,Size(Intersection(octad,octad1))); > od; gap> octad_intersection_sizes; [ 0, 2, 4, 8 ] gap> # gap> # gap> # gap> # ===================================================================== gap> # gap>