GAP

Main BranchesDownloads Installation Overview Data Libraries Packages Documentation Contacts FAQ GAP 3 

Find us on GitHubSitemapNavigation Tree

Frequently Asked Questions
1.General Questions1.1: What is GAP?GAP is a free system for computational discrete mathematics, in particular group theory. The Start Page of this web site explains the philosophy of the system. Further pages give an Overview of the system and its Mathematical Capabilities. 1.2: What are the requirements for running GAP?GAP runs on (almost) any flavour of Unix, on Macintoshes and on Windows (>94) machines. More details are given in a section of the current download page. 1.3: Which skills do I need to use GAP?You basically need:
1.4: Who wrote GAP?You can find an overview on all people involved in the development of GAP. We have kept a few documents marking steps of its development of GAP that you can access via the page Some History of GAP. 1.5: How is the GAP Web Site organized?
The GAP Web Site can be thought of as a graph with the
pages as nodes and the links as directed edges. To give each page a
definite place, a spanning tree (Navigation Tree) for this graph has
been (arbitrarily, but reasonably logically) defined, the main branches
representing different aspects of GAP. The
Sitemap depicts the main branches of that
tree. Note that there are many edges not belonging to the spanning tree.
1.6: Where do I get your clothes, your Genome analysis software, your diving software, information about your irrigation project?We are a group of researchers in computational group theory, a branch of mathematics and for us 'GAP' stands for 'Groups, Algorithms and Programming'. Other people came up with the same abbreviation for different meanings which apparently leads to some confusion. We don't produce clothing etc. and cannot help you with information about these other 'GAP's. A good idea might be to use a search engine to look for other occurrences of 'GAP'. Probably you can also find information at www.gapinc.com or staden.sourceforge.net or www.gap.org.uk or www.gap.gov.tr and so on. 1.7: I wrote to you two days ago and I still have not got an answer.Please bear with us. GAP is distributed freely and all user support is done by the program authors in addition to their usual teaching and administrative duties and programming work. We try to answer requests as fast as possible, but depending on the work load or the difficulty of the question a response might take a week or two. 1.8: How do I cite GAP ?To cite GAP, please see the Citing GAP webpage. 1.9: What does all this information GAP prints at startup mean?For example, in one particular GAP 4.4.12 installation, we have GAP4, Version: 4.4.12 of 17Dec2008, i686appledarwin10.4.0gcc Components: small 2.1, small2 2.0, small3 2.0, small4 1.0, small5 1.0, small6 1.0, small7 1.0, small8 1.0, small9 1.0, small10 0.2, small11 0.1, id2 3.0, id3 2.1, id4 1.0, id5 1.0, id6 1.0, id9 1.0, id10 0.1, trans 1.0, prim 2.1 loaded. where "small..." and "id..." refer to the various components of the GAP Small Groups Library, and those starting from "small" provide group databases (accessible via "AllSmallGroups", "SmallGroup" functions), while ones starting from "id" provide identification of small groups (via "IdGroup" function). Then, "trans" and "prim" are libraries of transitive and primitive permutation groups. Furthermore, this is followed by a list of loaded packages: Packages: AClib 1.1, Polycyclic 2.6, Alnuth 2.2.5, AutPGrp 1.4, nq 2.2, GAPDoc 1.2, IO 3.1, CrystCat 1.1.3, Cryst 4.1.6, Carat 2.1, CRISP 1.3.2, CTblLib 1.1.3, TomLib 1.1.4, FactInt 1.5.2, FGA 1.1.0.1, IRREDSOL 1.1.2, LAGUNA 3.5.0, Sophus 1.23, Polenta 1.2.7, ResClasses 2.5.3 loaded. which may vary from another user's GAP installation. The TomLib standing here is the name for the library of tables of marks. Note that some packages may essentially extend GAP system, so it is recommended to install not only the core GAP system archive, but also a merged archive of all currently redistributed GAP (see packages). Some packages may need additional compilation to get them working, as explained in the Installation Instructions. 2. Obtaining GAP2.1: Where can I download GAP?You can download GAP as described on the page Download GAP. 2.2: I cannot FTP that much data. Can I get a CD?We do not normally produce CDs containing GAP. In the exceptional case when you are unable to get GAP any other way, please contact us at support@gapsystem.org. 2.3: Are there RPMS or DEB files for Linux?We would like to be able to offer source and binary distributions packaged for the popular Linux package formats (Red Hat and Debian mainly) but so far we have not been able to find the manpower to prepare these. Since some time the core system of GAP (without most packages) is contained in the unstable branch of Debian. 2.4: The files do not load properly in my browser.Most likely the browser loads the files as text files (and probably displays the content on the screen as garbage). Use the right mouse button (or SHIFTButton or APPLEButton) to save the files in source format. 2.5: Can I obtain the algorithm and/or code for some function of GAP?The brief answer is: "Yes, GAP is open source." You can use tools such as 'grep' to search for the code. Also the answer to FAQ 2.6 may be helpful. 2.6: How do I find my way through the GAP Library?The following text, adapted from a talk by Alexander Hulpke at a Summer School at Linz in 1999, may be helpful. 3. Installation3.1: How do I install GAP?See the download pages. 3.2: Where do I find a manual?The best way to access the GAP documentation is to use the online help from within GAP using the ? (question mark) operator. The command SetHelpViewer can be used to use nicer display methods for the online help. Once you have unpacked GAP you will find the documentation inside the doc subdirectory. There are dvi and pdf files (depending on the version you installed you might need to get some additional files), the htm subdirectory contains an HTML version. You can also read the manual using the Web page Manuals. If you are a beginner, it might be a good idea to start with the tutorial which you can find in doc/tut. 3.3: The HTML manual does not display properly in my browser.Unfortunately, there is no standard for displaying mathematical formulae on Web pages. The current version of the HTML manual uses unicode characters. You can read them with most sufficiently new browsers, provided you have the necessary fonts installed. (Netscape 4 is not sufficiently new, in some browsers there may be missing characters and you see small boxes instead.) 4. Problems on Specific Hardware and Operating Systems (i.a. Windows and Macintosh)4.1: Some keys (arrow keys, ^) do not work on Windows.What happens is that the Windows keyboard driver (or the keyboard scan routine in the CYGWIN library we use to build the Windows binary) do not send proper keycodes to GAP. (This can depend on the version of Windows you are using.) It also depends on whether you are using a nonenglish keyboard driver. (For example the keyboard drivers for some nonEnglish languages catch the '^' character to produce the French circumflex accent. Switching off the French keyboard driver will resolve the problem.) We unfortunately do not have enough Windows expertise to remedy this. (One can type POW(a,b) for a^b.) 4.2: Cut and Paste do not work on Windows 95.This page explains a few tricks to improve the usability of the Windows version. They are mainly relevant to Windows 95, but parts will apply to other versions. Enabling cut and pasteBy default, using the Paste icon in a GAP window might lock up this window. To change this, rightclick the gap.bat icon and select Properties. You'll get a window, which will look like this (of course, your paths might vary):
Now click the Misc tab. Select `QuickEdit' in the `Mouse' menu, deselect `Fast pasting' in the `Other' menu. The window should look like this:
Then select Apply. An Alternative Shell
Optional:
A nicer user interface to GAP is available by using the
rxvt
shell via Setting an iconIf you are using the gap.pif shortcut in the GAP distribution a proper icon should already have been set up. If you are using the batch file to start GAP or a private shortcut, you can proceed as follows: In the bin subdirectory od the GAP distribution a file gapicon.bmp can be found (this icon was originally drawn by Burkhard Höfling for the Macintosh version). In the Preferences menu (see above) click the Program tab. (You might want to select `Close on Exit' now as well.)
Click the Change Icon button. Click Browse and select the `gapicon.bmp' file you just downloaded. You should get a window like this:
Select OK. Voilá, you're done. 4.3: The 'gap.bat' file does not start GAP.The file assumes that GAP is installed in C:/GAP4Rx/ (where x is the relase number). If it is installed in another place, you need to edit the file gap.bat. If the path name given in gap.bat contains long file names or blanks, you might have to enclose it by apostrophes. 4.4: Windows complains Out of environment space.Click the batch file 'gap.bat' or 'gaprxvt.bat' which caused the problem with the right mouse button and select 'Properties','Memory' and increase the initial environment space to at least 1024. This will create a 'pif' shortcut which should be used to start GAP. 4.5: The zoo files are corrupt  I cannot uncompress them.You probably downloaded the files in text mode. See question 2.4: The files do not load properly in my browser. 4.6: I cannot compile GAP under OS XYou might need to install the Apple developer tools first. See GAP under Mac OS X for details. 4.7: Running GAP on an AMD64 bit machineSome comments, provided by David Joyner, on running GAP on an AMD64 bit machine:
4.8: Running GAP on an Intel Itanium (IA64) machineThere are currently problems running GAP4 on Intel Itanium processors, which can result in system crashes, or possibly other strange behaviour. It may be possible to run GAP correctly, if slowly, by disabling compiler optimisation, but this is not guaranteed. For the technically inclined, the problem is the Itanium stack architecture, which uses a separate stack for register window overflows. The GAP garbage collector does not see that stack, and so may miss references to objects from C variables stored on it, resulting in live objects being incorrectly regarded as garbage and not preserved. New! (Feb. 2008) An experimental patch is available, which appears to solve this problem. Itanium users are encouraged to try this patch and let us know how they get on. 5. Usage hints5.1: How can I customise GAP?
When you start GAP, it looks for files with the names
For more details about
In former GAP releases prior to GAP 4.5
a filed called 5.2: How can I avoid excessive output?If you expect that the output will have too many lines, typing a double semicolon ";;" at the end of the command line will suppress displaying output on the screen. This will allow you to see more history of your session, and also will prevent your network connection from overloading.
Sometimes a strange indentation behaviour can be repaired by issuing one
or several times the command ' 5.3: How can I stop excessive output?In case you did not type the double semicolon ";;", and GAP started to print too many lines on the screen, sometimes CtrlC may break printing. But this may cause some side effects on the style of the further output, so you should use this measure carefully.
Sometimes a strange indentation behaviour can be repaired by issuing one
or several times the command ' 5.4: How can I save my GAP input and output?The command LogTo( namefile ) causes the subsequent interaction to be logged to the file with the name namefile, i.e., everything you see on your terminal will also appear in this file. LogTo may also be used to log to a stream (see LogTo for streams). This file must of course be writable by GAP, otherwise an error is signalled. Note that LogTo will overwrite the previous contents of this file if it already existed. The most convenient way of creating larger pieces of GAP code is to write them to some text file. For this purpose you can simply use your favorite text editor. You can load such a file into GAP using the command Read( namefile ). See the reference manual section File Operations for information on these and related commands. The command SaveWorkspace( filename ) will save a ``snapshot'' image of the current GAP workspace in the file filename. This image then can be loaded by another copy of GAP which then will behave as at the point when SaveWorkspace was called. See the section Saving and Loading a Workspace for information on this and related commands.
5.5: Can I run GAP remotely?
It is possible to run GAP remotely. Usually this can be done via an
Since GAP uses standard text terminals as user interface, the remote usage is very similar to the usage on a local machine. 5.6: Why should I use the "screen" program?If the remote server is operated by a UNIX operating system, it is very convenient to use the 'screen' program  a screen manager with VT100/ANSI terminal emulation. The advantage is that your GAP session will not be lost in case of (unintended) interrupts of your network connection, and that you can close the network connection while GAP is busy with long computations. It is likely that screen is already installed on your server  just type 'screen' to check this. (Otherwise look here to get it, or on Linux install the 'screen' package from your distribution.) If so, it will be launched and you will see its welcome message. Now you are able to work just as usual, but in case of a broken connection your session will not be closed, and your computations will be continued while you are not connected. When you will connect to the server next time, enter 'screen r' to restore your session. To detach your session again (i.e. move it into background) press CtrlA and then D (and you will see the normal command line prompt of your UNIX system) or simply close the connection. For more details about screen, see its documentation (for example, type 'man screen'). 5.7:Can I convert a file obtained from the GAP LogTo command into a Latex file? David Joyner ( wdj@usna.edu) announced in the GAP
Forum that he 5.8: When I use time or Runtime() or the profiler to determine how long a piece of GAP code takes, the answers can vary significantly. Why is this?There are a number of possible reasons for this:
Also note that accessing, especially updating, global variables is significantly slower than local ones. As described on the page Packages/Contrib/contrib.html there are links timers.g and README.timers to files containing and describing simple GAP routines useful for measuring the runtime of GAP operations which are too fast for the builtin methods of measurement. 6. Complaints6.1: I think I found a bug.While we try to check the GAP system as rigorously as we can, such a large system will inevitably contain bugs. We welcome bug reports and regularly issue updates. However since GAP is available free and the GAP authors work on the system as part of their research, we would like to ask you to make sure that the problem that you encountered really is a bug and that you are giving us sufficient information to deal with it: please read the page GAP Trouble before sending us a bug report. 6.2: My calculation does not finish (or GAP runs out of memory).Depending on the size or representation of objects, some harmlesslooking commands can involve very expensive (in terms of runtime and of memory use) routines. Typical examples are (without any claim towards completeness):
In these cases the calculation might seemingly run forever or terminate after a while with an error message that GAP could not get more memory. The first thing to check is the error message you got, as there are two variants:
Assuming that neither of these fixes is available (your job is using all the physical memory you can have), it often is possible to recast the task in a different way to get the result more efficiently: A few approaches for this are:
6.3: My calculation with matrix groups is slow/runs out of memory.GAP currently translates essentially every calculation with matrix groups to an isomorphic permutation group. Two possible bottlenecks are:
7. Computing with GAP7.1: How do I perform binary operations on the elements of a group?The group operation in GAP is always multiplication, written with *. This works e.g. for groups of permutations, of matrices, and for abstract groups given by generators and relations. While you can construct a number of groups of permutations, they all have the same multiplication, in the sense that if two permutations p1 and p2 are both in two permutation groups, their product in each group will be the permutation p1*p2 given by applying p1 followed by p2. In fact, this essentially works the other way round. GAP first defines elements, such as permutations, matrices or words in abstract generators, with their operations such as multiplication and inverse, then it allows you to define groups of such objects, using the objects multiplication as the group operation. All the many algorithms, implemented in GAP for the investigation of the structure of a group, are written using this symbol * for the group multiplication. 7.2: How do I represent my group in GAP?If you can write down permutations or matrix generators, you can use them directly. (Note, however, that GAP will internally compute a faithful permutation representation to work with matrix groups anyhow. However, see below for an example that you should be aware of this, because it can be dangerous.) A group given by a finite presentation can be input as a quotient of a free group. If larger calculations are to be done, it is worthwhile (if it is possible) to either convert it to a PC group (using for example SolvableQuotient  Note that even if the presentation is polycyclic, GAP will not use methods for polycyclic groups, unless the group is also represented as a PC group) or to a permutation group. For groups given by structural information, the construction can be much harder. There are a few general product constructions (direct and semidirect product for example). The Issac 2000 tutorial gives some examples of constructing groups. Here then is the example to which the first paragraph referred: A user had sent the following program run, asking for help: gap> g := GL(3,27); GL(3,27) gap> h := SylowSubgroup(g,2); <group of 3x3 matrices in characteristic 3> gap> Size(h); 32 gap> n := Normalizer(g,h); <group of 3x3 matrices in characteristic 3> gap> Size(n); 5408 gap> l := List(Irr(n), i> i[1]);; exceeded the permitted memory ... brk> quit; Frank Lübeck explained what happened: First you can get the number characters of given degree much easier, using that the group n is solvable, its order being divisible by only two primes. gap> IsSolvable(n); true gap> CharacterDegrees(n); [ [ 1, 1352 ], [ 2, 1014 ] ] gap> h1 := IsomorphismPermGroup(n); <action isomorphism> gap> NrMovedPoints(Image(h1)); 19682 So the user was asking to compute the 2366 irreducible characters of a permutation group of order 5408 of degree 19682 and this would have had to be done by the Dixon/Schneider method using the 2366 conjugacy classes of that group! In such a case one can either try to find a much smaller permutation representation of that group or work with a pc group presentation: gap> h2 := SmallerDegreePermutationRepresentation(Image(h1));; gap> NrMovedPoints(Image(h2)); 130 gap> Size(Image(h2)); 5408 gap> hpc := IsomorphismPcGroup(n);; gap> Image(hpc); Group([ f6, f4*f5*f6, f4, f7, f3, f2^7*f3*f7, f1^7*f4*f5*f6 ]) gap> Size(last); 5408 Results of computations in these image groups can then be translated back into the group n, using the function PreImage. 7.3: Does GAP support additive groups?The answer is a clear 'no and yes'! To understand this 'clear answer' let us consider the integers mod 15. (See section Residue Class Rings in the chapter on integers.) First of all you can simply add and multiply integers mod 15 by gap> (17 + 18) mod 15; 5 gap> (17 * 18) mod 15; 6 You can also form the ring of integers mod 15 by gap> z15 := ZmodnZ(15); (Integers mod 15) and GAP tells you: gap> IsRing(z15); true In fact you can work with its elements : gap> a := ZmodnZObj(17,15); ZmodnZObj( 2, 15 ) gap> b := ZmodnZObj(18,15); ZmodnZObj( 3, 15 ) gap> a+b; ZmodnZObj( 5, 15 ) gap> a*b; ZmodnZObj( 6, 15 ) GAP also tells you gap> IsAdditiveGroup(z15); true But: gap> IsGroup(z15); false The explanation is that in GAP an additive group A (of a ring) is just an additive magma withzero with an operation that maps each element a of A to its additive inverse and that most of the algorithms for groups are not available for these. So you get: gap> Size(z15); 15 gap> SylowSubgroup(z15,3); Error, no method found! On the other hand, using that the additive group of the integers mod 15 is cyclic you can deal with this group in the usual way: gap> c15 := CyclicGroup(15); <pc group of size 15 with 2 generators> gap> Size(c15); 15 gap> s := SylowSubgroup(c15,3); Group([ f1*f2^3 ]) gap> Size(s); 3 7.4: In many algebra books the quaternion group is a group on 8 distinct symbols {i,j,k,1,1,i,j,k}. How can I make GAP use these elements?GAP's group constructors will generally, and by default, construct a group of the specified isomorphism type, in whatever form is most efficient for computation. No specific nomenclature for the elements if guaranteed. So gap> q8 := SmallGroup(8,4); <pc group of size 8 with 3 generators> gap> Elements(q8); [ <identity> of ..., f1, f2, f3, f1*f2, f1*f3, f2*f3, f1*f2*f3 ] gap> is a perfectly good description of a group of order 8 isomorphic to the group generated by the quaternions i and j. We can actually see that by making the group of quaternions: gap> q := QuaternionAlgebra(Rationals); <algebrawithone of dimension 4 over Rationals> gap> gens := GeneratorsOfAlgebraWithOne(q); [ e, i, j, k ] gap> e := gens[1]; i := gens[2]; j := gens[3]; k := gens[4]; e i j k gap> g := Group(i,j); #I default `IsGeneratorsOfMagmaWithInverses' method returns `true' for [ i, j ] <group with 2 generators> gap> Elements(g); [ (1)*e, (1)*i, (1)*j, (1)*k, k, j, i, e ] gap> IsomorphismGroups(q8,g); [ f1, f2, f3 ] > [ j, i, (1)*e ] Here we construct the group Q_{8} that you were expecting, list its elements and, in the last line, demonstrate an isomorphism between the library group SmallGroup(8,4) and the group of quaternions. Using this group g, we can, for instance print the normal subgroups gap> Print(NormalSubgroups(g),"\n");; [ Group( [ i, j ] ), Group( [ (1)*k, (1)*e ]), Group( [ (1)*j, (1)*e ] ), Group( [ i, (1)*e ] ), Group( [(1)*e ] ), Group( e ) ] Each subgroup is still given only in terms of generating elements because as soon as your groups get much larger you almost never actually want the complete list of elements. If you want them in this case, you can do gap> for n in NormalSubgroups(g) do Print(Elements(n),"\n"); od; [ (1)*e, (1)*i, (1)*j, (1)*k, k, j, i, e ] [ (1)*e, (1)*k, k, e ] [ (1)*e, (1)*j, j, e ] [ (1)*e, (1)*i, i, e ] [ (1)*e, e ] [ e ] gap> In general, if you want to see the elements of your group in some particular notation, you need to construct the group from elements of that kind. Then, if you ask for the Elements of a subgroup or coset, you will get what you want. For instance, when you say you want the generating elements for a particular subgroup of Q_{8}, in what form do you want them? The standard representation (because it's the best for computing), is as words in what are called polycylic generators. If you would prefer permutations, you can specify this when constructing the group. 7.5: I have a finite presentation for a finite polycyclic group. When I tried to use PcGroupFpGroup() to convert it to a pcgroup, I received an error message.PcGroupFpGroup() is mainly a conversion routine. The given finite presentation must be a polycyclic presentation for PcGroupFpGroup() to work. PcGroupFpGroup() does not compute a polycyclic presentation for a finite soluble group given by an arbitrary finite presentation.See Constructing Pc Groups. In a polycyclic presentation the generators must occur in the particular order of a 'polycyclic generating sequence': As described in the Reference Manual chapter Polycyclic Groups a group G is polycyclic if there exists a subnormal series G = C_{1}> C_{2}> ... > C_{n}> C_{n+1} = {1} with cyclic factors, and a polycyclic generating sequence of G is a sequence P : = (g_{1},..., g_{n}) of elements of G such that C_{i} = <C_{i+1}, g_{i}> for 1 ≤ i ≤ n. Now for the given presentation the order of the generators is defined by the order in which the generators occur in the FreeGroup() command. This is important because it fixes the way in which commutator or conjugate relations have to be defined. Relations have to be of the form g^m / w Comm( h,g ) / w h^g / w where
Note that you may have to use brackets around w if it is a product of several generators because GAP evaluates the expressions above from left to right. Changing the order of the generators or interchanging g and h in the left hand side of a commutator or conjugate relation can produce an error message as shown by the following three examples of presentations for the symmetric group S_{3}. Example 1gap> f := FreeGroup(IsSyllableWordsFamily, "a","b"); <free group on the generators [ a, b ]> gap> a := f.1;; b := f.2;; gap> rels := [a^2,b^3,b^a/b^2]; [ a^2, b^3, a^1*b*a*b^2 ] gap> g:=f/rels; <fp group on the generators [ a, b ]> gap> Size(g); 6 gap> gpol := PcGroupFpGroup(g); <pc group of size 6 with 2 generators> Here we had started from a presentation that obeys the rules for a polycyclic presentation. Example 2gap> f := FreeGroup(IsSyllableWordsFamily, "b","a"); <free group on the generators [ b, a ]> gap> b := f.1;; a := f.2;; gap> rels := [a^2,b^3,b^a/b^2]; [ a^2, b^3, a^1*b*a*b^2 ] gap> g:=f/rels; <fp group on the generators [ b, a ]> gap> Size(g); 6 gap> gpol := PcGroupFpGroup(g); Error, illegal relator a^1*b*a*b^2 called from ... brk> Here we have just interchanged the sequence of the generators, thus breaking the rules, so that PcGroupFpGroup() does not work. Example 3gap> f := FreeGroup(IsSyllableWordsFamily, "a","b"); <free group on the generators [ a, b ]> gap> a := f.1;; b := f.2;; gap> rels := [a^2,b^3,a^b/(b*a)]; [ a^2, b^3, b^1*a*b*a^1*b^1 ] gap> g:=f/rels; <fp group on the generators [ a, b ]> gap> Size(g); 6 gap> gpol := PcGroupFpGroup(g); Error, relator b^1*a*b*a^1*b^1 is not trivial called from ... brk> Here the sequence of generators is correct, but the relator is not in the prescribed form. Some remarks
7.6: How do I get the elements of my group?There are functions AsList and AsSSortedList that return a (sorted) list of all the group elements. However for bigger groups such lists can take an enormous amount of memory. You might be better off just looking at the ConjugacyClasses. 7.7: How do I get the subgroups of my group?Everything said for elements holds even more so for subgroups: You probably want only representatives of the conjugacy classes or even just of subgroups of a given size. For groups of moderate size (up to 10^{4}/10^{5}, this depends a bit on the group structure) the commands LatticeSubgroups or ConjugacyClassesSubgroups will compute representatives of all subgroups up to conjugacy. If the group gets bigger, however, this will either run out of space or take too long to be feasible. In this case it is likely that you are only interested in certain types of subgroups. Try to use the restricting conditions to reduce the calculation (for example psubgroups can be found inside a Sylow subgroup). GAP commands that might come useful to obtain specific subgroups are for example NormalSubgroups, SylowSubgroup, HallSubgroup, or MaximalSubgroupClassReps. Furthermore, if you actually want to know if the group has a subgroup of a particular isomorphism type, the command you want is IsomorphicSubgroups. This is enormously more efficient than simply listing all [conjugacy classes of] subgroups of the group in most cases. It might also be helpful to first replace the group by an isomorphic permutation group (using IsomorphismPermGroup) or pc group (using IsomorphismPcGroup).7.8: Is GAP suited for studying combinatorial structures and finite permutation groups?GAP is suited very well for computing in combinatorial structures and permutation groups. A small but nevertheless illustrative example given by Stefan Kohl in an answer to a letter to 'gapsupport' is the investigation of the automorphism group of a graph whose vertices are the cards of a card game called Duo with edges between any two cards that 'fit together'. The game `Duo' consists of 4^3 = 64 `normal' cards each showing a triple (colour, shape, number), where there are four possible colours, shapes and numbers (any possible combination occurs exactly once) and 3*4 = 12 jokers each showing either a colour, a shape or a number. Two `normal' cards fit together if and only if they coincide in two of their symbols. E.g. (red, square, 1) and (green, square, 1) fit together, but (red, square, 1) and (red, triangle, 3) do not. A joker fits together with a `normal' card if one of the three symbols of the latter is the joker's, e.g. the (blue) joker fits together with (blue, triangle, 4). Two jokers never fit together. Although this may look a bit complicate, formulating it in the GAP language is quite easy. For constructing the graph we use the GAP package GRAPE by Leonard Soicher: gap> LoadPackage("grape"); # Construct the Duo graph with 4^3 + 12 = 76 vertices: gap> vertices := Concatenation(List(Tuples([0..3],3),t>t+[0,4,8]), > List([0..11],i>[i])); gap> TrivialAction := function ( x, g ) return x; end;; gap> Relation := function ( x, y ) > return Length(Intersection(x,y)) = 2 > or (Length(x) = 1 or Length(y) = 1) > and Length(Intersection(x,y)) = 1 and x <> y; > end;; gap> Gamma := Graph(Group(()),vertices,TrivialAction,Relation,true);; We compute the automorphism group, again using GRAPE: gap> G := AutGroupGraph(Gamma); <permutation group with 9 generators> gap> time; # time in ms 20 gap> DegreeAction(G); # Check: we really have 4^3 + 3*4 = 76 vertices. 76 The automorphism group acts transitively both on the `normal' cards and on the jokers, but a `normal' card cannot be mapped onto a joker or vice versa: gap> orb := Orbits(G,[1..76]); # Compute the orbits on the set of vertices. [ [ 1, 2, 3, 5, 4, 9, 17, 6, 13, 33, 10, 18, 7, 49, 14, 34, 11, 19, 21, 8, 50, 15, 35, 37, 12, 20, 25, 22, 51, 53, 16, 36, 41, 38, 29, 26, 23, 52, 57, 54, 45, 42, 39, 30, 27, 24, 61, 58, 55, 46, 43, 40, 31, 28, 62, 59, 56, 47, 44, 32, 63, 60, 48, 64 ], [ 65, 69, 73, 74, 75, 70, 76, 71, 66, 72, 67, 68 ] ] gap> List(orb,Length); [ 64, 12 ] The action of the automorphism group on the `normal' cards is primitive, but the one on the jokers is not: gap> G1 := Action(G,orb[1]); # The action of G on the first orbit. <permutation group with 9 generators> gap> G2 := Action(G,orb[2]); # The action of G on the second orbit. <permutation group with 9 generators> gap> IsPrimitive(G1,MovedPoints(G1)); true gap> IsPrimitive(G2,MovedPoints(G2)); false Both actions are faithful: gap> Size(G); 82944 gap> List([G1,G2],Size); [ 82944, 82944 ] The automorphim group is solvable, but not nilpotent: gap> Factors(Size(G)); [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3 ] gap> IsSolvable(G); true # Obvious (by Burnside's Theorem). gap> IsNilpotent(G); false gap> List(LowerCentralSeries(G),Size); [ 82944, 20736 ] gap> List(DerivedSeries(G),Size); [ 82944, 20736, 6912, 1728, 64, 1 ] The action of the automorphism group on the jokers is the imprimitive action of the wreath product of the symmetric group of degree 4 and the symmetric group of degree 3 on 3*4 = 12 points, and the action of the automorphism group on the `normal' cards is the primitive action of this wreath product on 4^3 = 64 points: gap> GeneratorsOfGroup(G2); [ (1,2)(6,9)(8,11)(10,12), (2,3)(4,6)(5,8)(7,10), (3,4), (4,5), (5,7), (6,8), (8,10), (9,11), (11,12) ] gap> H := TransitiveGroup(12,TransitiveIdentification(G2)); # Group structure in humanreadable form [S(4)3]S(3)=S(4)wrS(3) gap> Size(H); # A check. 82944 gap> 6*24^3; # dito. 82944 gap> W := WreathProduct(Group((1,2),(1,2,3,4)),Group((1,2),(1,2,3))); <permutation group of size 82944 with 8 generators> gap> phi := IsomorphismGroups(G,W); # A concrete isomorphism. [ (1,21,6,26,11,19)(2,25,7,18,9,23)(3,17,5,22,10,27)(4,29,8,30,12,31)(13,24, 14,28,15,20)(16,32)(33,53,38,58,43,51)(34,57,39,50,41,55)(35,49,37,54,42, 59)(36,61,40,62,44,63)(45,56,46,60,47,52)(48,64)(65,66)(67,68)(69,73,70, 74,71,75)(72,76), (1,46,7,29,35,22)(2,14,15,31,19,18)(3,30)(4,62,11,32,51, 26)(5,45,39,21,33,38)(6,13,47,23,17,34)(8,61,43,24,49,42)(9,48,55,25,36, 54)(10,16,63,27,20,50)(12,64,59,28,52,58)(40,53,41)(44,56,57)(65,72,75,66, 69,74)(67,70,73)(68,71,76) ] > [ (1,2)(3,4)(5,9,8,10,7,12)(6,11), (1,9,5)(2,10,6)(3,11,7,4,12,8) ] 7.9: How can one compute the Schur Multiplier of a finite group by GAP?Derek Holt answered: One possibility is to use the package cohomolo. You first have to follow the instructions in the package directory to compile the external programs. It calculates the Schur multiplier with respect to a given prime, so you need to try all primes dividing the group order. The input group must be a permutation group (the degree of which is presently restricted to at most 4096). Here is an example. gap> G:=PSL(3,4);; gap> chr := CHR(G,2);; # This constructs a 'cohomologyrecord' that is used in all further functions gap> SchurMultiplier(chr); [ 4, 4 ] gap> chr := CHR(G,3);; gap> SchurMultiplier(chr); [ 3 ] gap> chr := CHR(G,5);; gap> SchurMultiplier(chr); #The Sylow psubgroup of the group is cyclic  so the multiplier is trivial. [ ] gap> chr := CHR(G,7);; gap> SchurMultiplier(chr); #The Sylow psubgroup of the group is cyclic  so the multiplier is trivial. [ ] We conclude that the Schur multiplier is a direct product of cyclic groups of order 4, 4 and 3. It is also possible to compute finite presentations of covering groups. Derek Holt gave the warning:"But this package involves external C programs, and it is only possible to use it under Unix or Linux." However in a further letter Dima Pasechnik added: In Fact "cohomolo" also runs seemingly OK on Windows with Cygwin (http://www.cygwin.com). Note however that there are a couple of very minor changes in the installation procedure of the package. Finally Alexander Hulpke added: Let me just add to Derek Holt's response, that GAP also has a builtin routine for multiplier calcultation. The commands are AbelianInvariantsMultiplier (structure of the multiplier) and EpimorphismSchurCover (map from a covering group, represented as finitely presented group, onto original group) gap> AbelianInvariantsMultiplier(SymmetricGroup(6)); [ 2 ] gap> EpimorphismSchurCover(SymmetricGroup(6)); [ f1, f2, f3, f4, f5 ] > [(1,2), (2,3), (3,4), (4,5), (5,6)] The algorithms used are similar to the ones used by the `cohomolo' package, the main advantage of the library implementation is that it does not require an external program and thus can also run under Windows or if the `cohomolo' package is not installed. Comparison of runtimes of the two implementations shows that for 'small' groups (say up to order 20000) there is no significant difference, while for large groups the implementation in the cohomolo package runs faster (e.g. in an experiment by Derek Holt for PSp(6,3) of order 4585351680 the corresponding times were 6 and 80 seconds respectively).
7.10: "Is it possible using GAP to check that a given presentation defines a
nilpotent group of class 2 or not?"


The GAP Group Last updated: Tue Sep 12 11:32:17 2017 