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>