GAP

Main Branches

Downloads  Installation  Overview  Data Libraries  Packages  Documentation  Contacts  FAQ  GAP 3 

Frequently Asked Questions

  1. General Questions

    There is also a Russian version of this set of questions and the answers to them.

  2. Obtaining GAP.

  3. Installation

  4. Problems on Specific Hardware and Operating Systems (i.a. Windows and Macintosh)

  5. Usage hints

  6. Complaints

  7. Computing with GAP

    In addition to the list of frequently asked questions on computing with GAP given below,

    • David Joyner is collecting a list of frequently asked questions about Constructions of various mathematical objects in GAP with fully worked out GAP code answering them. This collection is specially recommended for newcomers to the system .
    • Alexander Hulpke has collected user questions (mostly from the GAP Forum) about mathematical applications of GAP together with the corresponding answers. See Some GAP Questions on his home page.

  8. Programming GAP

1.General Questions

1.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:

  • A reasonable knowledge of English, enough to read this website, the GAP manuals and, if you have questions, to correspond with the GAP support group. Note however that there is some material available in other languages, e. g. Russian and Portuguese. (There are also foreign language links on the teaching webpage.)
  • Basic skills in working with a computer. How much of these will depend on the use you want to make of GAP.

    In any case you should be able to handle a webbrowser. If you just want to use GAP interactively you can do so using the functions of GAP like those of a pocket calculator.

    If you want to write your own programs in the GAP language, you will need a basic idea about what programming is, i.e. you should have an idea what functions, variables and loops are, etc. and you will need some knowledge on how to install programs and to edit text files.

    If you do not have help of a systems administrator, you will have to know how to download and install programs on your computer. We provide helpful instructions how to do this with GAP, see Obtaining GAP and Installation.

  • The necessary knowledge of the part of mathematics you would like to work on. While we try to help with problems occurring in the use of GAP, we regret that unless your work is directly connected with the research of a member of the GAP team we will not have the manpower to help with your mathematical problems.

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.

At the top of the left hand bar of each page you find a link to the Sitemap, further down that left hand bar depicts a part of the navigation tree, showing the branch leading from the Start node to this page as well as the 'brothers' of this page and its 'children' and allowing to link to each of these.

The left hand bar of the Start Page in addition shows some 'Quick Links' to pages that a more experienced user may want to visit immediately.

The top bar lists the main nodes sitting at distance 1 under the Start node hence defining the main branches of the tree.

From the pages of the GAP Web Site proper there are many links to other Web pages, e. g. to home pages of people, home pages of packages, etc. These will not carry the top and left hand bars of the proper GAP Web pages. The bars will also be missing on pages showing parts of the manual, the GAP Forum correspondence, etc.

Of course, web pages of other people may change without our noticing this, so that our links to such pages will not work any longer. If you notice such a case, or have other criticism of the web site or suggestions for its improvement please inform us by a letter to support@gap-system.org.

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 www.gap.org or www.gap.org.uk or www.gap.net or www.gap.uidaho.edu 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 17-Dec-2008, i686-apple-darwin10.4.0-gcc
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 GAP

2.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?

As a comparatively small group of researchers, writing CDs comes at a notable cost in time (for writing the CD, getting blanks, suitable envelopes, shipping and so on). We therefore do not normally produce CDs containing GAP.

If you have a slow modem connection at home, but a faster connection at work/university the easiest solution might be to download GAP there and write it on a USB flash drive or CD yourself and we would encourage you to use this method whenever possible.

Depending on your country, there might also be commercial services that will produce CDs of specified content (search for 'CD writing service' on a search engine such as Google.)

In exceptional cases, when you are unable to get GAP any other way, we can write a CD. This however can take some time, and we may have to charge some costs. Please contact us at support@gap-system.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 SHIFT-Button or APPLE-Button) 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. Installation

3.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 non-english keyboard driver. (For example the keyboard drivers for some non-English 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 paste

By default, using the Paste icon in a GAP window might lock up this window. To change this, right-click the gap.bat icon and select Properties. You'll get a window, which will look like this (of course, your paths might vary):

Windows Preferences Menu

Now click the Misc tab. Select `QuickEdit' in the `Mouse' menu, deselect `Fast pasting' in the `Other' menu. The window should look like this:

Misc Preferences Menu

Then select Apply.

An Alternative Shell

Optional: A nicer user interface to GAP is available by using the rxvt shell via C:\gap4r4\bin\gaprxvt.bat, instead of the DOS-emulation window. (But note that the GAP Group cannot provide any support for this shell.)

Setting an icon

If 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.)

Program Preferences Menu

Click the Change Icon button. Click Browse and select the `gapicon.bmp' file you just downloaded. You should get a window like this:

Program Icon Window

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 X

You 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 machine

Some comments, provided by David Joyner, on running GAP on an AMD64 bit machine:

  • Compiling in SUSE 9.1, AMD64 bit version.

    If you compile using

    ./configure
    make
    
    it compiles as 32 bit. If you use
    ./configure --enable-libsuffix=64
    make
    

    it compiles as 64 bit.

    Redhat's AMD64 bit version is similar. If you have Debian-based 64-bit linux then this still works but the simpler command ./configure compiles the application by default as 64-bit.

    In the case of Debian, another possibility exists: use apt-get to download and install it from the Debian AMD64 development tree. Bill Allombert (allomber@math.u-bordeaux.fr), the gap package maintainer for Debian, is a good contact for this.

  • Performance issues.

    Comments from Frank Luebeck:

    The setting of C_STACK_ALIGN to 1 by the configure script is correct. The AMD 64 architecture has no alignment restrictions, but the access speed may depend on alignment. (Of course the compiler optimization tries to align data for fast access.)

    Performance of a dual Opteron 248, 2.2GHz, 8GB memory:

    Most of GAP is a bit faster in 32 bit mode, compared to 64 bit mode. The speed is similar to a 3 GHz Pentium 4 machine. One can use complete 4 GB of memory in 32 bit mode.

    Most GAP objects need twice as much space in 64 bit mode compared to 32 bit mode. So, using 64 bit mode is only interesting if you have and want to use more than 8 GB of memory.

    The exceptions concerning speed and memory are compacted kernel objects: long integers, compressed finite field matrices, blists. Here computations can go faster and need only little more memory in 64 bit mode (GF(2)-matrices of Baby monster multiply about 30% faster).

    Comments from Bill Allombert:

    On a Opteron at1366MHz I got:

    64 bit build of GAP:
    echo 'ReadTest("tst/combinat.tst");'| bin/*/gap -q | tee debian/gap.tst
    + $Id: combinat.tst,v 4.9.4.3 2005/05/11 14:53:02 gap Exp $
    + GAP4stones: 1317073
    true
    
    32bit build of GAP:
    echo 'ReadTest("tst/combinat.tst");'| bin/*/gap -q | tee debian/gap.tst
    + $Id: combinat.tst,v 4.9.4.3 2005/05/11 14:53:02 gap Exp $
    + GAP4stones: 1560693
    true
    

    A more comprehensive bench (testall.g) in 32 and 64bit variant.

    The bottom line is (first figure is GAPstones, 2nd is seconds):

    i386 :    total   206089   41411
    amd64: total   191640   45861

4.8: Running GAP on an Intel Itanium (IA64) machine

There 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 hints

5.1: How can I customise GAP?

When you start GAP, it looks for files with the names gap.ini and gaprc in its root directories (see GAP Root Directories), and reads the first gap.ini and the first gaprc file it finds. These files may be used for certain customisations, for example, to read a file containing functions or data that you always need, to set your personal preferences, to load certain packages, or to define your personal abbreviations for some names in the library, which seems to be too long for you.

For more details about gap.ini and gaprc files see the section The gap.ini and gaprc files from the GAP Reference Manual.

In former GAP releases prior to GAP 4.5 a filed called .gaprc was used for customisations. If you have used the .gaprc file, see the section The former .gaprc file. from the GAP Reference Manual for the transitional arrangements.

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 'Print("\<\<\<\<\<\<\<");'.

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 Ctrl-C 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 'Print("\<\<\<\<\<\<\<");'.

5.4: How can I save my GAP input and output?

The command LogTo( name-file ) causes the subsequent interaction to be logged to the file with the name name-file, 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. See the reference manual section File Operations for information on this 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.

Further Yevgen Muntyan and David Joyner have written a function which automatically logs all GAP input and output. The log file is named after the time and date. It only works in linux.

The instructions are on a webpage Automatic Logging in GAP, however here are some details.

  • Download logger.gap from the webpage and save in /home/wdj/gapfiles/ (of course, change the path name /home/wdj/gapfiles/ to what you like).
  • Create the directory /home/wdj/gapfiles/log (of course, change the path name /home/wdj/gapfiles/ to what you have in (1))
  • Put the following 2 lines in your .gaprc file:
    Read(/home/wdj/gapfiles/logger.gap);
    autologger();
    where the path name /home/wdj/gapfiles/ is what you have in (1).

That's it! Now every GAP command is automaticaly logged and filed by date and time in the log subdirectory.

5.5: Can I run GAP remotely?

It is possible to run GAP remotely. Usually this can be done via an ssh connection. (On Windows one can use, e.g., PuTTY.)

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 Ctrl-A 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
"has written a very simple python program which takes a file obtained from the GAP LogTo command and converts into a Latex file. You must have the python binary installed in \usr\bin (on a linux/unix setup). However, if you have the windows version of python then it presumably works with some editing. The file with an example in on David Joyner's webpage GAP Stuff, if you are interested."

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:

  • 1. For some calculations, GAP actually uses randomized algorithms (although, unless you choose otherwise, the results produced are always checked). In these cases, the algorithm may be more or less "lucky" and take a shorter or longer time accordingly. You can usually avoid this variation by setting the random seed to a standard value before each test, using RANDOM_SEED(1).
  • 2. Garbage collection. The GAP memory manager runs when the system runs out of free memory and can take significant time. To standardise when this happens, run GASMAN("collect") before each test.
  • 3. The granularity of the underlying OS timing function being used is at best 1ms, sometimes courser, so a test which takes 0,1 or 2 ms per run could represent a calculation that takes about 1ms and may cross anywhere between 0 and 2 clock ticks without more than a small variation in how long it takes.
  • 4. The method cache. The GAP method selection system caches the last few methods that were used for each operation. The cost of a cache miss is considerable.
  • 5. The CPU cache. If the relevant parts of the GAP interpreter and/or of the workspace are in CPU cache when the test starts, this will save some time.

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 run-time of GAP operations which are too fast for the built-in methods of measurement.

6. Complaints

6.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 harmless-looking commands can involve very expensive (in terms of runtime and of memory use) routines. Typical examples are (without any claim towards completeness):

  • Isomorphism tests,
  • Calculation of all subgroups,
  • Calculations with finitely presented structures.

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:

cannot extend the workspace any more
You have hit a hard limit of how much memory is available. This could be due to physical memory in the machine, the operating system used, or the way how GAP was compiled (32 bit versus 64 bit). If you need lots of memory (and have it physically in the machine) you should run a 64 bit binary of GAP (which might require using a 64 bit version of the operating system as well).
exceeded the permitted memory (-o command line option)
This (far more frequent) error is a safety device to stop GAP from allocating so much memory to bring a machine (probably used for other tasks or by other users as well) to its knees. (A typical situation of this might be if GAP cannot do better at some task than enumerating all elements of a huge group, but the user did not realize this.) In this case an error is triggered and the trigger limit increased by a factor of 2. You could either just type return; and restart the calculation, or exit the break loop and restart the calculation anew. In either case more memory is made available. In case of running a batch job (or being irritated by this error message), you can use the -o command line option to set this trigger limit to a higher default level, e.g. the amount of physical memory your machine has. See the section Command Line Options in the Reference Manual for more detail.

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:

  • Is there a better representation? Typically PcGroups (only possible for solvable groups) are more efficient than permutation groups are more efficient than matrix groups are more efficient than Fp groups. Use IsomorphismPermGroup (or similar) to transfer the calculation into a group in a better representation.
  • Is there another operation (probably not as general as the one you are using) whose result would be sufficient? (For example it is sufficient to search for p-subgroups inside a Sylow subgroup.)
  • Is there information you have about the object that GAP will have to find out? Good candidates are the size of a group (use SetSize) or solvability (use SetIsSolvableGroup).
  • Is the amount of data produced by the calculation feasible for the machine you are using?
  • Does your computation use mutable lists when immutable lists might be better?

    In some cases, this can slow down your computation so much that it doesn't finish. Using immutable lists allows computed properties to be cached, so that further checking of the property is instantaneous. In the example below, the comments were introduced after the interaction.

    # create a mutable, sorted list
    gap> a:=List([0..20000],i->WordAlp("a",i));;
    gap> IsSortedList(a);
    true
    gap> time;
    256
    gap> IsSortedList(a);
    true
    gap> time;
    260
    
    # Time to check if it is sorted is about the same every occasion
    gap> KnownPropertiesOfObject(a);
    [ "IsFinite", "IsSmallList" ]
    
    # not much is known about a
    gap> b:=Immutable(a);;
    gap> KnownPropertiesOfObject(b);
    [ "IsFinite", "IsSmallList" ]
    
    # also not much is known about b # check sortedness for the first time
    gap> IsSortedList(b);
    true
    gap> time;
    284
    
    # about the same time it took for a. now, check again
    gap> IsSortedList(b);
    true
    gap> time;
    0
    
    # caching miracle! In this process, a lot was learned about b:
    gap> KnownPropertiesOfObject(b);
    [ "IS_SSORT_LIST", "IsFinite", "IsSmallList", "IsSortedList", "IsDuplicateFree" ]
    

    This example point to an important consequence: lookup in b is much faster than searching in a, since, as b is known to be sorted, binary search is used for the lookup. An amusing instance of a painful learning experience in the subject appears in the Forum thread starting in http://mail.gap-system.org/pipermail/forum/2008/002169.html.

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:

  1. Intermediate results might get transferred back to matrix form and are immediately converted again in a permutation: Because of this it is often quicker to work in the isomorphic permutation group (obtained via `IsomorphismPermGroup', see the section 'Computing a Permutation Representation' of the GAP reference manual) and only to translate the final result back to matrix form, using the same homomorphism.
  2. GAP finds a permutation representation by acting on a set of vectors. There is no optimal heuristics for choosing these vectors (a necessary condition for faithfulness is that the vectors comprise a basis, but there are many choices). Note that `IsomorphismPermGroup' for matrix groups internally already uses 'SmallerDegreePermutationRepresentation' (unless the matrix group is known to contain SL), thus this operation cannot be used to reduce the degree further. If the group is very large, it can be rather beneficial to try to choose such a set of vectors yourself and use `ActionHomomorphism' (see the section 'The Permutation Image of an Action' of the GAP reference manual) to build the permutation representation.

7. Computing with GAP

7.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 -with-zero 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);
<algebra-with-one 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 Q8 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 Q8, 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 pc-group, 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 = C1> C2> ... > Cn> Cn+1 = {1} with cyclic factors, and a polycyclic generating sequence of G is a sequence P : = (g1,..., gn) of elements of G such that Ci = <Ci+1, gi> 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

  • m is a positive integer,
  • h and g are generators,
  • h occurs after g and
  • w is a word in generators coming after g.

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 S3.

Example 1
gap> 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 2
gap>  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 3
gap>  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
  1. If we want to get a pc group from a finitely presented group, the presentation of which is not in the prescribed form, we can use the composite function Image(IsomorphismPcGroup(g)). Note, however, that this function does not work for finitely presented groups g, so that one first has e.g. to find a faithful permutation representation. In Example 3 this has implicitely already been done by calling the function Size(g). So we can continue Example 3:

    gap> phi:=IsomorphismPcGroup(g);
    [ a, b ] -> [ f1, f2^2 ]
    gap> h := Image(phi);
    Group([ f1, f2^2 ])
    gap> IsPcGroup(h);
    true
    gap> Size(h);
    6
    
  2. For many algorithms working with pc groups it is additionally necessary that the above mentioned cyclic factors of the subnormal series are in fact of prime order. The function IsomorphismRefinedPcGroup(G) returns an isomorphism from G onto an isomorphic pc group with that property.

  3. At present in order to print out a pc presentation you can best use a function from the package 'Polycyclic', as we demonstrate, again continuing the last example:

    gap> RequirePackage("polycyclic");
    true
    gap>  DisplayPcpGroup( PcGroupToPcpGroup(h) );
    < g1 g2 | 
    
        g1^2 = id
        g2^3 = id
    
        g2^g1 = g2^2
    

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 104/105, 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 p-subgroups 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 'gap-support' 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 human-readable 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 'cohomology-record' 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 p-subgroup of the group is cyclic - so the multiplier is trivial.
[  ]
gap> chr := CHR(G,7);;    
gap> SchurMultiplier(chr);
#The Sylow p-subgroup 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 built-in 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?"
For example $G=\langle a,b,c| a^{p^5}, b^{p^3}, c^{p^2}, [a,b]=a^{p^3}, [a,c]=c^p, [b,c]=b^{p^2} \rangle $ where $p$ is a prime.
Also how can we determine its automorphism group using GAP?

Answer: The question was asked in this form in a GAP Forum letter on Jan. 27, 2010 and was answered in the Forum by three letters on Jan. 28. The answer given here joins the contents of these.

First please note that the 'example' really is not a presentation of a single group, but a family of presentations parametrized by the primes p. GAP has no methods for handling such a family of presentations in one step. However GAP has methods to investigate each such presentation for any given (not too big) prime p. In her reply Bettina Eick recommends:

you can use GAP to investigate your question for any fixed prime p.

For example, the nilpotent quotient algorithm of the NQ package or the NQL package of GAP allows you to determine the largest class-c quotient of a finitely presented group for any positive integer c or even the largest nilpotent quotient (if this exists).

Further, there are methods available in GAP to determine the automorphism group of a finite p-group. Check the AutPGrp package for this purpose.

In your given example, you can implement your considered group G in GAP as function in p:

G := function(p)
    local F, f, r, a, b, c;
    F := FreeGroup(3);
    f := GeneratorsOfGroup(F); a := f[1]; b := f[2]; c := f[3];
    r := [a^(p^5), b^(p^3), c^(p^2),
          Comm(a,b)/a^(p^3),
          Comm(a,c)/c^p,
          Comm(b,c)/b^(p^2) ];
    return F/r;
end;

Then you load the relevant packages

LoadPackage("nq");
LoadPackage("autpgrp");

And then you can do the following (for example for p=3):

gap> H := G(3);
[fp group on the generators [ f1, f2, f3 ]]
gap> K := NilpotentQuotient(H);
Pcp-group with orders [ 27, 9, 3, 9, 3, 3 ]
gap> Length(LowerCentralSeries(K));
3
gap> A := AutomorphismGroupPGroup(K);;
gap> A.size;
14348907

Hence for p=3 your group has class 2 and you can see the size of its automorphism group. Generators and further information on the automorphisms is also stored in A, but is perhaps too long to be displayed here.

In a second letter Derek Holt recommends:

You can use the GAP package KBMAG to prove nilpotency of finitely presented groups, using the method described by Charles Sims in his book of computing in finitely presented groups. This uses the Knuth-Bendix completion algorithm.

This process is described and illustrated in Example 4 (p. 13) of the KBMAG manual. I have successfully verifed that your group below is nilpotent of order p^10 for p=2,3,5,7,11,13,17, and I am trying to do 19.

Of course, since these groups are (apparently) finite, you could try use coset enumeration. This will work for small primes such as 2 and 3, but for larger primes the group order will probably be too large, and I think the Sims algorithm will work better.

You first run NilpotentQuotient (as described in Bettina Eick's reply) to find the maximal nilpotent quotient of your group. The aim is then to prove that the group is actually isomorphic to this quotient. You do this by introducing new generators in the presentation which correspond to the power-commutator generators in the maximal nilpotent quotient. You order the generators so that those at the bottom of the group come first and then use the so-called recursive ordering on strings to run Knuth-Bendix.

Here is the basic GAP code to do this.

LoadPackage("kbmag");
SetInfoLevel(InfoRWS,2);
F:=FreeGroup("j","i","h","g","f","e","d","c","b","a");;
j:=F.1;; i:=F.2;; h:=F.3;; g:=F.4;; f:=F.5;;
e:=F.6;; d:=F.7;; c:=F.8;; b:=F.9;; a:=F.10;;
p:=3;;
rels := [a^p/e, b^p/f, c^p/d, e^p/g, f^p/h, g^p/i, i^p/j,
        j^p, h^p, d^p, Comm(a,b)/i, Comm(a,c)/d, Comm(b,c)/h ];;
G := F/rels;;
R := KBMAGRewritingSystem(G);;
SetOrderingOfKBMAGRewritingSystem(R, "recursive");
MakeConfluent(R);

If successful it will halt with a confluent presentation containing the relations of the power-commutator presentation of the computed maximal nilpotent quotient. You have then proved that these relations hold in the group itself (not just in the nilptent quotient), so you have proved that the group is nilpotent. This consists of 65 reduction equations (or 62 when p=2).

The above works quickly for p=2,3,5,7. For larger primes, it helps to restrict the length of the stored reduction relations, and then re-run after completion. You have to experiment to find the optimal maximal length to store. So, for example, the following works fast for p=17:

p:=17;;
rels := [a^p/e, b^p/f, c^p/d, e^p/g, f^p/h, g^p/i, i^p/j,
        j^p, h^p, d^p, Comm(a,b)/i, Comm(a,c)/d, Comm(b,c)/h ];;
G := F/rels;;
R := KBMAGRewritingSystem(G);;
SetOrderingOfKBMAGRewritingSystem(R, "recursive");
O := OptionsRecordOfKBMAGRewritingSystem(R);
O.maxstoredlen := [40,40];
MakeConfluent(R);
Unbind(O.maxstoredlen);
MakeConfluent(R);

In a final letter Charles Wright gave an elegant proof 'by hand' that in fact all the groups for arbitrary primes are of nilpotency class 2 and order at most p^10, a proof, the clues for which can perhaps be obtained from the results of the GAP computations (which of course can be applied in similar form also to other presentations). He writes:

If all you want to show is that this particular example is class 2 of order (at most) p^10, though, it's easy to do it by hand. We're given that a^b = a^(1+p^3), c^a = c^(1-p) and b^c = b^(1+p^2). Hence, (a^(p^3))^b = (a^b)^(p^3) = a^((1+p^3)p^3) = a^(p^3) and c^(a^(p^3)) = c^((1-p)^(p^3)) = c [what a mess of superscripts!], so a^(p^3) (i.e., [a,b]) is in Z(G). Similarly, a^(b^(p^2)) = a^((1+p^3)^(p^2)) = a and (b^(p^2))^c = (b^c)^(p^2) = b^((1+p^2)p^2) = b^(p^2), so b^(p^2) (i.e., [b,c]) is central. Finally, (c^p)^a = c^((1-p)p) = c^p and b^(c^p) = b^((1+p^2)^p) = b, so c^p (i.e., [a,c]) is central. Thus G/Z(G) is abelian. Since G' has order (at most) p^4 and G/G' has order (at most) p^6, G has order (at most) p^10. In the spirit of Burnside, I'll leave the elimination of "(at most)" to the reader.

7.11: How do I use GAP to "identify" a given group?

One of the most frequent requests that comes up is for to "identify" a given group. While some functionality for this exists, the problem is basically what "identify" means, or what a user expects from identification:
  • For tiny orders (say up to 15), there are few groups up to isomorphism, and each of the groups has a "natural" name. Furthermore many these names belong into series (symmetric groups, dihedral groups, cyclic groups) and the remaining groups are in obvious ways (direct product or possibly semidirect product) composed from groups named this way.
  • This clean situation breaks down quickly once the order increases: for example there are - up to isomorphism - 14 groups of order 16, 231 of order 96 and over 10 million of order 512. This rapid growth goes beyond any general "naming" or "composition" scheme.
  • A decomposition as semidirect, subdirect or central product is not uniquely defined without some further information, which can be rather extensive to write down.
  • Even if one might hope that a particular group would be composable in a nice way, this does not lead to an "obvious" description, for example the same group of order 16 could be described for example as a semidirekt product of D8 with a cyclic group of order 2 (i.e. D8:C2), or as semidirect product of Q8 with a cyclic group of order 2 (Q8:C2), or as (C2×C4):C2 (and - vice versa - the last name could be given to 4 nonisomorphic groups). In the context of matrix groups in characteristic 2, S3 is better called SL2(2), and so on.
  • There are libraries of different classes of groups (e.g. small order up to isomorphism, or transitive subgroup of Sn (for small n) up to conjugacy); these libraries typically allow to identify a given group, but the identification is just like the library call number of a book and gives little information about the group, it is mainly of use to allow recreation of the group with the identification number given as only information.
With these caveats, the following functions exist to identify groups and give them a name: StructureDescription returns a string describing the isomorphism type of a group . This string is produced recursively, trying to decompose groups as direct or semidirect products. The resulting string does not identify isomorphism types, nor is it neccessarily the most "natural" description of a group.
gap> g:=Group((1,2,3),(2,3,4));;
gap> StructureDescription(g);
"A4"

Group Libraries

contains extensive libraries of "small" groups and many of these libraries allow identificatuion of a group therein. The associated library group then often comes with a name that might be appropriate.

Small Groups

The small groups library contains - amongst others - all groups of order up to 1000, except 512. For such a group IdGroup returns a list such that the group is isomorphic to SmallGroup().
gap> g:=Group((1,2,3),(2,3,4));;
gap> IdGroup(g);
[ 12, 3 ]
gap> SmallGroup(12,3);
<pc group of size 12 with 3 generators>

Transitive Groups

The transitive groups library contains transitive subgroups of Sn of degree at most 31 up to Sn conjugacy. For such a group of degree n, TransitiveIdentification returns a number , such that the group is conjugate in Sn to TransitiveGroup().
gap> g:=Group((1,2,3),(2,3,4));;
gap> TransitiveIdentification(g);
4
gap> TransitiveGroup(NrMovedPoints(g),4);
A4

Primitive Groups

The primitive groups library contains primitive subgroups of Sn (i.e. the group is transitive and affords no nontrivial G-invariant partition of the points) of degree at most 1000 up to Sn conjugacy. For such a group of degree n, PrimitiveIdentification returns a number , such that the group is conjugate in Sn to PrimitiveGroup().
gap> g:=Group((1,2,3),(2,3,4));;
gap> IsPrimitive(g,[1..4]);
true
gap> PrimitiveIdentification(g);
1
gap> PrimitiveGroup(NrMovedPoints(g),1);
A(4)

Simple groups and Composition Series

The one class of groups for which it is unambiguous, and comparatively easy to assign names to is finite simple groups (assuming the classification of finite simple groups). A consequence of the classification is that the order of a simple group determines its isomorphism type, with the exception of two infinite series (which can be distinguished easily otherwise). In GAP, this is achieved by the command IsomorphismTypeInfoFiniteSimpleGroup: For a finite simple group, it returns a record, containing information about the groups structure, as well as some name.
gap> g:=SL(3,5);                          
SL(3,5)
gap> IsomorphismTypeInfoFiniteSimpleGroup(g/Centre(g));
rec( name := "A(2,5) = L(3,5) ", series := "L", parameter := [ 3, 5 ] )
Clearly, this can be applied to the composition series of a finite group, identifying the isomorphism types of all composition factors. (Of course, this information does not identify the isomorphism type of the group, and - in particular for solvable groups - can be rather uninformative.) The command DisplayCompositionSeries will print information about the composition factors of a finite group.
gap> DisplayCompositionSeries(SymmetricGroup(4));
G (4 gens, size 24)
 | Z(2)
S (3 gens, size 12)
 | Z(3)
S (2 gens, size 4)
 | Z(2)
S (1 gens, size 2)
 | Z(2)
1 (0 gens, size 1)
gap> DisplayCompositionSeries(SymmetricGroup(5));
G (2 gens, size 120)
 | Z(2)
S (3 gens, size 60)
 | A(5) ~ A(1,4) = L(2,4) ~ B(1,4) = O(3,4) ~ C(1,4) = S(2,4) ~ 2A(1,4)
   = U(2,4) ~ A(1,5) = L(2,5) ~ B(1,5) = O(3,5) ~ C(1,5)
   = S(2,5) ~ 2A(1,5) = U(2,5)
1 (0 gens, size 1)
gap> DisplayCompositionSeries(GU(6,2));          
G (size 82771476480)
 | Z(3)
S (4 gens, size 27590492160)
 | 2A(5,2) = U(6,2)
S (1 gens, size 3)
 | Z(3)
1 (size 1)

7.12: Can non-isomorphic groups have equal structure descriptions?

Yes, indeed, this can happen. The manual entry for "StructureDescription" says: "The string returned by StructureDescription is NOT an isomorphism invariant: non-isomorphic groups can have the same string value, and two isomorphic groups in different representations can produce different strings."

StructureDescription provides an "informal" overview of the structure of a group, which is a useful first view for small groups. More sophisticated functions in the same area include: IdGroup; the StandardPresentation function of the ANUPQ package and IsomorphismGroups, each of which is described in the appropriate manual.

8. Programming GAP

8.1: Can I call GAP functions from another programme?

The short answer is no. To explain a little more fully, essentially all the algebraic functionality of the GAP system is written in the GAP language, and so needs the GAP interpreter to run. The interpreter is written in C, but does not coexist happily with other code in the same process for a number of reasons, so there is no sensible way to link GAP into a C, Java or other program as a subroutine library.

What you can do is to run GAP in a child process and communicate with it using pipes, pseudo-ttys, UNIX FIFOs or some similar device. We have done this successfully in a number of projects, and you can contact the support list for more detailed advice if you want to go down this route.

Relatively recently, some of the SAGE developers have produced libGAP, which allows the entire GAP system to be embedded as a C library. One still can’t embed individual functions by themselves though and the first call to libGAP still has to invoke the full GAP start-up sequence.

Alternatively, there are a number of ways of running GAP as a server process and calling it from C of C++ programs. See the SCSCP package for the GAP side. There are several C and C++ libraries that implement the client side.

8.2: Can I make a smaller version of GAP containing just the function(s) I need?

It is possible to make a considerably smaller installation of GAP than the standard one, simply by starting with the basic archive found on the Web site and adding other components or packages only if they are needed. You should be aware, however, that some packages and databases may be used silently to improve performance in apparently unrelated functionality, so using such a "cut-down" installation would risk a few unexpected slowdowns.

It is possible, but neither easy nor supported to cut down the installation even further by omitting parts of the GAP library (or even kernel), but there are considerable and sometimes very inobvious interdependencies between different parts of the system, so that, for instance a permutation group computation may identify a solvable subgroup and switch to solvable group algorithms for that section, which reduce many problems to linear algebra, and so call on the code for matrices over finite fields, which in turn reduces some problems to computations with minimal and characteristic polynomials and so on.

An alternative approach is to load GAP, using the -N option to force it to read the libraries in full at start-up, load any packages or other things you need and then save a workspace. A GAP process started from that workspace will not need to read the library files, and should be able to run without most of them even being present. This isn't something we've actually tried, but you should be able to produce a workable GAP installation with not much more than the kernel and the workspace. Some experiment may be needed.

8.3: Where is the GAP file editor? How do I save GAP programs?

GAP programs are simple text files, and you can edit them with any file editor. Under UNIX we would recommend vim, or emacs, for which special GAP modes are available, but pico, gedit and other programs also work fine. Under Windows we would recommend WordPad, or the cygwin ports of vim, pico or emacs, although there are undoubtedly other suitable editors. It is also possible to use a word processor, such as Microsoft Word, so long as you save as ASCII TEXT.

You can call GAP files anything you like, although we generally use names ending .g, .gap, .gd or .gi. It may help Windows users to give them names ending .txt. Once you have written your program, you can execute it using the Read() command in GAP. Note that within GAP the path separator character is always '/', so you might say:

gap> Read("d:/gapfiles/program.g");

to read a file that Windows would call

D:\gapfiles\program.g.