Content from First session with GAP

Last updated on 2024-08-28 | Edit this page

Overview

Questions

  • Working with the GAP command line

Objectives

  • Time-saving tips and tricks
  • Using GAP’s help system
  • Basic objects and constructions in the GAP language

If GAP is installed correctly you should be able to start it. Exactly how you start GAP will depend on your operating system and how you installed GAP. GAP starts with the banner displaying information about the version of the system and loaded components, and then displays the command line prompt gap>, for example:

OUTPUT 

 ┌───────┐   GAP 4.9.2 of 04-Jul-2018
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin16.7.0-default64
 Configuration:  gmp 6.1.2, readline
 Loading the library and packages ...
 Packages:   AClib 1.3, Alnuth 3.1.0, AtlasRep 1.5.1, AutPGrp 1.9,
             Browse 1.8.8, CRISP 1.4.4, Cryst 4.1.17, CrystCat 1.1.8,
             CTblLib 1.2.2, FactInt 1.6.2, FGA 1.4.0, GAPDoc 1.6.1, IO 4.5.1,
             IRREDSOL 1.4, LAGUNA 3.9.0, Polenta 1.3.8, Polycyclic 2.14,
             PrimGrp 3.3.1, RadiRoot 2.8, ResClasses 4.7.1, SmallGrp 1.3,
             Sophus 1.24, SpinSym 1.5, TomLib 1.2.6, TransGrp 2.0.2,
             utils 0.54
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap>

To leave GAP, type quit; at the GAP prompt. Remember that all GAP commands, including this one, must be finished with a semicolon! Practice entering quit; to leave GAP, and then starting a new GAP session. Before continuing, you may wish to enter the following command to display GAP prompts and user inputs in different colours:

GAP 

 ColorPrompt(true);

The easiest way to start trying GAP out is as a calculator:

GAP 

( 1 + 2^32 ) / (1 - 2*3*107 );

OUTPUT 

-6700417

If you want to record what you did in a GAP session, so you can look over it later, you can enable logging with the LogTo function, like this.

GAP 

LogTo("gap-intro.log");

This will create a file file gap-intro.log in the current directory which will contain all subsequent input and output that appears on your terminal. To stop logging, you can call LogTo without arguments, as in LogTo();, or leave GAP. Note that LogTo blanks the file before starting, if it already exists!

It can be useful to leave some comments in the log file in case you return to it in the future. A comment in GAP starts with the symbol # and continues to the end of the line. You can enter the following after the GAP prompt:

GAP 

# GAP Software Carpentry Lesson

then after pressing the Return key, GAP will display a new prompt but the comment will be written to the log file.

The log file records all interaction with GAP that happens after the call to LogTo, but not before. We can repeat our calculation from above if we want to record it as well. Instead of retyping it, we will use the Up and Down arrow keys to scroll the command line history. Repeat this until you see the formula again, then press Return (the location of the cursor in the command line does not matter):

GAP 

( 1 + 2^32 ) / (1 - 2*3*107 );

OUTPUT 

-6700417

You can also edit existing commands. Press Up once more, and then use the Left and Right arrow keys, Delete or Backspace to edit it and replace 32 by 64 (some other useful shortcuts are Ctrl-A and Ctrl-E to move the cursor to the beginning and end of the line, respectively). Now press the Return key (at any position of the cursor in the command line):

GAP 

( 1 + 2^64 ) / (1 - 2*3*107 );

OUTPUT 

-18446744073709551617/641

It is useful to know that if the command line history is long, one could perform a partial search by typing the initial part of the command and using Up and Down arrow keys after that, to scroll only the lines that begin with the same string.

If you want to store a value for later use, you can assign it to a name using :=

GAP 

universe := 6*7;

:=, = and <>

  • In other languages you might be more familiar with using =, to assign variables, but GAP uses :=.

  • GAP uses = to compare if two things are the same (where other languages might use ==).

  • Finally, GAP uses <> to check if two things are not equal (rather than the != you might have seen before).

Whitespace characters (i.e. Spaces, Tabs and Returns) are insignificant in GAP, except if they occur inside a string. For example, the previous input could be typed without spaces:

GAP 

(1+2^64)/(1-2*3*107);

OUTPUT 

-18446744073709551617/641

Whitespace symbols are often used to format more complicated commands for better readability. For example, the following input which creates a 3×3 matrix:

GAP 

m:=[[1,2,3],[4,5,6],[7,8,9]];

OUTPUT 

[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

We can instead write our matrix over 3 lines. In this case, instead of the full prompt gap>, a partial prompt > will be displayed until the user finishes the input with a semicolon:

GAP 

gap> m:=[[ 1, 2, 3 ],
>        [ 4, 5, 6 ],
>        [ 7, 8, 9 ]];

OUTPUT 

[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

You can use Display to pretty-print variables, including this matrix:

GAP 

Display(m);

OUTPUT 

[ [  1,  2,  3 ],
  [  4,  5,  6 ],
  [  7,  8,  9 ] ]

In general GAP functions like LogTo and Display are called using brackets, which contain a (possibly empty) list of arguments.

Functions are also GAP objects

Check what happens if you forget to add brackets, e.g. type LogTo; and Factorial; We will explain the differences in these outputs later.

Here are some examples of calling other GAP functions:

GAP 

Factorial(100);

OUTPUT 

93326215443944152681699238856266700490715968264381621468\
59296389521759999322991560894146397615651828625369792082\
7223758251185210916864000000000000000000000000

(the exact width of output will depend on your terminal settings),

GAP 

Determinant(m);

OUTPUT 

0

and

GAP 

Factors(2^64-1);

OUTPUT 

[ 3, 5, 17, 257, 641, 65537, 6700417 ]

Functions may be combined in various ways, and may be used as arguments of other functions, for example, the Filtered function takes a list and a function, returning all elements of the list which satisfy the function. IsEvenInt, unsurprisingly, checks if an integer is even!

GAP 

Filtered( [2,9,6,3,4,5], IsEvenInt);

OUTPUT 

[ 2, 6, 4 ]

A useful time-saving feature of the GAP command-line interfaces is completion of identifiers when the Tab key is pressed. For example, type Fib and then press the Tab key to complete the input to Fibonacci:

GAP 

Fibonacci(100);

OUTPUT 

354224848179261915075

In the case that a unique completion is not possible, GAP will try to perform partial completion, and pressing the Tab key second time will display all possible completions of the identifier. Try, for example, to enter GroupHomomorphismByImages or NaturalHomomorphismByNormalSubgroup using completion.

The way functions are named in GAP will hopefully help you to memorise or even guess names of library functions. If a variable name consists of several words then the first letter of each word is capitalised (remember that GAP is case-sensitive!). Further details on naming conventions used in GAP are documented in the GAP manual here. Functions with names in ALL_CAPITAL_LETTERS are internal functions not intended for general use. Use them with extreme care!

It is important to remember that GAP is case-sensitive. For example, the following input causes an error:

GAP 

factorial(100);

ERROR 

Error, Variable: 'factorial' must have a value
not in any function at line 14 of *stdin*

because the name of the GAP library function is Factorial. Using lowercase instead of uppercase or vice versa also affects name completion.

Now let’s consider the following problem: for a finite group G, calculate the average order of its elements (that is, the sum of orders of its elements divided by the order of the group). Where to start?

Enter ?Group, and you will see all help entries, starting with Group:

OUTPUT 

┌──────────────────────────────────────────────────────────────────────────────┐
│   Choose an entry to view, 'q' for none (or use ?<nr> later):                │
│[1]    AutoDoc (not loaded): @Group                                           │
│[2]    loops (not loaded): group                                              │
│[3]    polycyclic: Group                                                      │
│[4]    RCWA (not loaded): Group                                               │
│[5]    Tutorial: Groups and Homomorphisms                                     │
│[6]    Tutorial: Group Homomorphisms by Images                                │
│[7]    Tutorial: group general mapping                                        │
│[8]    Tutorial: GroupHomomorphismByImages vs. GroupGeneralMappingByImages    │
│[9]    Tutorial: group general mapping single-valued                          │
│[10]   Tutorial: group general mapping total                                  │
│[11]   Reference: Groups                                                      │
│[12]   Reference: Group Elements                                              │
│[13]   Reference: Group Properties                                            │
│[14]   Reference: Group Homomorphisms                                         │
│[15]   Reference: GroupHomomorphismByFunction                                 │
│[16]   Reference: Group Automorphisms                                         │
│[17]   Reference: Groups of Automorphisms                                     │
│[18]   Reference: Group Actions                                               │
│[19]   Reference: Group Products                                              │
│[20]   Reference: Group Libraries                                             │
│ > > >                                                                        │
└─────────────── [ <Up>/<Down> select, <Return> show, q quit ] ────────────────┘

You may use arrow keys to move up and down the list, and open help pages by pressing Return key. For this exercise, open Tutorial: Groups and Homomorphisms first. Note the navigation instructions at the bottom of the screen. Look at first two pages, then press q to return to the selection menu. Next, navigate to Reference: Groups and open it. Within two first pages you will find the function Group and mentioning of Order.

GAP manual comes in several formats: text is good to view in a terminal, PDF is good for printing and HTML (especially with MathJax support) is very efficient for exploring with a browser. If you are running GAP on your own computer, you can set the help viewer to the default browser. If you are running GAP on a remote machine, this (probably) will not work. (see ?WriteGapIniFile on how to make this setting permanent):

GAP 

SetHelpViewer("browser");

After that, invoke the help again, and see the difference!

Let’s now copy the following input from the first example of the GAP Reference manual chapter on groups. It shows how to create permutations, and assign values to variables. This is Reference: Groups. You can select it by typing ?11, where you replace 11 with whatever number appears before Reference: Groups on your machine.

If you are viewing the GAP documentation in a terminal, you might find it helpful to open two copies of GAP, one for reading documentation and one for writing code!

This guide shows how permutations in GAP are written in cycle notation, and also shows common functions which are used with groups. Also, in some places two semi-colons are used at the end of a line. This stops GAP from showing the result of a computation.

GAP 

a:=(1,2,3);;b:=(2,3,4);;

Next, let G be a group generated by a and b:

GAP 

G:=Group(a,b);

OUTPUT 

Group([ (1,2,3), (2,3,4) ])

We may explore some properties of G and its generators:

GAP 

Size(G); IsAbelian(G); StructureDescription(G); Order(a);

OUTPUT 

12
false
"A4"
3

Our next task is to find out how to obtain a list of G’s elements and their orders. Enter ?elements and explore the list of help topics. After inspection, the entry from the Tutorial does not seem relevant, but the entry from the Reference manual is. It also explains the difference between using AsSSortedList and AsList. So, this is the list of elements of G:

GAP 

AsList(G);

OUTPUT 

[ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2), (1,3,4),
  (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]

The returned object is a list. We would like to assign it to a variable to explore and reuse. We forgot to do it when we were calculating it. Of course, we may use the command line history to restore the last command, edit it and call again. But instead, we will use last which is a special variable holding the last result returned by GAP:

GAP 

elts:=last;

OUTPUT 

[ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2), (1,3,4),
  (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]

This is a list. Lists in GAP are indexed from 1. The following commands are (hopefully!) self-explanatory:

GAP 

gap> elts[1]; elts[3]; Length(elts);

OUTPUT 

()
(2,4,3)
12

Lists are more than arrays

  • May contain holes or be empty

  • May dynamically change their length (with Add, Append or direct assigment)

  • Not required to contain objects of the same type

  • See more in GAP Tutorial: Lists and Records

Many functions in GAP refer to Sets. A set in GAP is just a list that happens to have no repetitions, no holes, and elements in increasing order. Here are some examples:

GAP 

gap> IsSet([1,3,5]); IsSet([1,5,3]); IsSet([1,3,3]);

OUTPUT 

true
false
false

Now let us consider an interesting calculation – the average order of elements of G. There are many different ways to do this, we will consider a few of them here.

A for loop in GAP allows you to do something for every member of a collection. The general form of a for loop is:

GAP 

for val in collection do
  <something with val>
od;

For example, to find the average order of our group G we can do.

GAP 

s:=0;;
for g in elts do
  s := s + Order(g);
od;
s/Length(elts);

OUTPUT 

31/12

Actually, we can just directly loop over the elements of G (in general GAP will let you loop over most types of object). We have to switch to using Size instead of Length, as groups don’t have a length!

GAP 

s:=0;;
for g in G do
  s := s + Order(g);
od;
s/Size(G);

OUTPUT 

31/12

There are other ways of looping. For example, we can instead loop over a range of integers, and accept elts like an array:

GAP 

s:=0;;
for i in [ 1 .. Length(elts) ] do
  s := s + Order( elts[i] );
od;
s/Length(elts);

OUTPUT 

31/12

However, often there are more compact ways of doing things. Here is a very short way:

GAP 

Sum( List( elts, Order ) ) / Length( elts );

OUTPUT 

31/12

Let’s break this last part down:

  • Order finds the order of a single permutation.
  • List(L,F) makes a new list where the function F is applied to each member of the list L.
  • Sum(L) adds up the members of a list L.

Which approach is best?

Compare these approaches. Which one would you prefer to use?

GAP has very helpful list manipulation tools. We will now show a few more examples.

Sometimes, GAP does not have the exact function we want. For example, NrMovedPoints gives the number of moved points of a permutation, but what if we want to find all permutations which move 4 points? This is where GAP’s arrow notation comes in. g -> e makes a new function which takes one argument g, and returns the value of the expression e. Here are some examples:

  • finding all elements of G with no fixed points:

GAP 

Filtered( elts, g -> NrMovedPoints(g) = 4 );

OUTPUT 

[ (1,2)(3,4), (1,3)(2,4), (1,4)(2,3) ]
  • finding a permutation in G that conjugates (1,2) to (2,3)

GAP 

First( elts, g -> (1,2)^g = (2,3) );

OUTPUT 

(1,2,3)

Let’s check this (remember that in GAP permutations are multiplied from left to right!):

GAP 

(1,2,3)^-1*(1,2)*(1,2,3)=(2,3);

OUTPUT 

true
  • checking whether all elements of G move the point 1 to 2:

GAP 

ForAll( elts, g -> 1^g <> 2 );

OUTPUT 

false
  • checking whether there is an element in G which moves exactly two points:

GAP 

ForAny( elts, g -> NrMovedPoints(g) = 2 );

OUTPUT 

false

Use list operations to select from elts the stabiliser of the point 2 and the centraliser of the permutation (1,2)

  • Filtered( elts, g -> 2^g = 2 );

  • Filtered( elts, g -> (1,2)^g = (1,2) );

Key Points

  • Remember that GAP is case-sensitive!
  • Do not panic if you see Error, Variable: 'FuncName' must have a value.
  • Care about names of variables and functions.
  • Use command line editing.
  • Use autocompletion instead of typing names of functions and variables in full.
  • Use ? and ?? to view help pages.
  • Set the default help format to HTML using SetHelpViewer.
  • Use the LogTo function to save all GAP input and output into a text file.
  • If calculation takes too long, press -C to interrupt it.
  • Read ‘A First Session with GAP’ from the GAP Tutorial.

Content from Some more GAP objects

Last updated on 2024-08-28 | Edit this page

Overview

Questions

  • Further examples of objects and operations with them

Objectives

  • See examples of types that are built-in in GAP but may be missing in other systems
  • See examples of list arithmetic

So far we have met three types of GAP types:

  • simple objects such as integers, rationals, booleans, permutations;

  • composite objects such as lists;

  • objects with more complex internal representation, such as groups.

In this section, we will demonstrate some other examples of basic objects that exist in GAP (the system is extendable, so one can introduce new types of objects, but this is beyond the scope of this lesson!).

Some other simple objects are floats, cyclotomics and finite field elements:

GAP 

1.15; Float(1232/3456567);

OUTPUT 

1.15
0.000356423

GAP 

E(4); E(4)^2; E(6);

OUTPUT 

E(4)
-1
-E(3)^2

GAP 

AsList(GF(2)); Z(5); Z(5)^4;

OUTPUT 

[ 0*Z(2), Z(2)^0 ]
Z(5)
Z(5)^0

You already know about lists. Another type of composite objects is records. While a list contains subobjects indexed by their positions in the list, a record contains subobjects, called record components, which are indexed by their names. Elements of a record are accessed with .

GAP 

date:= rec(year:= 2015, month:= "Nov", day:= 17);

OUTPUT 

rec( day := 17, month := "Nov", year := 2015 )

GAP 

date.year;

OUTPUT 

2015

GAP 

date.time:= rec(hour:= 14, minute:= 55, second:= 12);

OUTPUT 

rec( hour := 14, minute := 55, second := 12 )

GAP 

date;

OUTPUT 

rec( day := 17, month := "Nov",
  time := rec( hour := 14, minute := 55, second := 12 ), year := 2015 )

GAP 

RecNames(date);

OUTPUT 

[ "time", "year", "month", "day" ]

Next, there are strings and characters. While strings are printed specially by GAP, a string is really just a list of characters, and any function which takes a list will also take a string. In contrast, characters are simple objects like integers.

GAP 

gap> w:="supercalifragilisticexpialidocious"; Length(w);

OUTPUT 

"supercalifragilisticexpialidocious"
34

Strings are denoted by double quotes, and characters by single ones.

GAP 

gap> "s" in w; 's' in w; IsSubset(w,"s");  IsSubset(w,['s','f']); ['c','a','t'] = "cat";

OUTPUT 

false
true
true
true
true

Note that

GAP 

gap> PositionSublist(w,"sf"); PositionSublist(w,"fr");

OUTPUT 

fail
10

Be careful! Some operations may create a new list, while others are destructive. For example:

GAP 

gap> SortedList(w); w;

OUTPUT 

"aaacccdeefgiiiiiiillloopprrssstuux"
"supercalifragilisticexpialidocious"

but

GAP 

gap> Sort(w); w;

OUTPUT 

"aaacccdeefgiiiiiiillloopprrssstuux"

Which letter occurs in “supercalifragilisticexpialidocious” most often?

GAP 

gap> c := Collected(w);

OUTPUT 

[ [ 'a', 3 ], [ 'c', 3 ], [ 'd', 1 ], [ 'e', 2 ], [ 'f', 1 ], [ 'g', 1 ],
  [ 'i', 7 ], [ 'l', 3 ], [ 'o', 2 ], [ 'p', 2 ], [ 'r', 2 ], [ 's', 3 ],
  [ 't', 1 ], [ 'u', 2 ], [ 'x', 1 ] ]

GAP 

gap> k := Maximum( List( c, v -> v[2] ) ); Filtered( c, v -> v[2] = 7 );

OUTPUT 

7
[ [ 'i', 7 ] ]

Finding the most common letter(s) in a list using only one pass

The command

k := Maximum( List( c, v -> v[2] ) ); Filtered( c, v -> v[2] = 7 );

iterates over the list c twice (in List and in Filtered), and it also iterates over another list of the same length as c in the call to Maximum. If the list is long, this will impose certain performance and memory penalties. Try to write code that finds the letters that occur most in c without producing an intermediate list.

Key Points

  • GAP has a plethora of various immediate, positional and component objects.
  • List arithmetic is very flexible and powerful.
  • Objects like lists and records are good to keep structured and related data.

Content from Functions in GAP

Last updated on 2024-08-28 | Edit this page

Overview

Questions

  • Functions as a way of code re-use

Objectives

  • Using command line for prototyping
  • Creating functions
  • Reading GAP code from a file

Just to remind us of our task: for a finite group G, we would like to calculate the average order of its elements (that is, the sum of the orders of its elements divided by the order of the group).

We begin with a very straightforward approach, iterating over all elements of the group in question:

GAP 

S:=SymmetricGroup(10);

OUTPUT 

Sym( [ 1 .. 10 ] )

GAP 

sum:=0;

OUTPUT 

0

GAP 

for g in S do
  sum := sum + Order(g);
od;
sum/Size(S);

OUTPUT 

39020911/3628800

Now assume that we would like to save this fragment of GAP code and later repeat this calculation for some other groups. We may even reformat it to fit it into one line and use a double semicolon to suppress the output of sum:

GAP 

sum:=0;; for g in S do sum := sum + Order(g); od; sum/Size(S);

OUTPUT 

39020911/3628800

Now we may easily copy and paste it into the GAP session the next time we need it. But here we see the first inconvenience: the code expects that the group in question must be stored in a variable named S, so either we have to reset S each time, or we need to edit the code:

GAP 

S:=AlternatingGroup(10);

OUTPUT 

Alt( [ 1 .. 10 ] )

GAP 

sum:=0;; for g in S do sum := sum + Order(g); od; sum/Size(S);

OUTPUT 

2587393/259200

This works only for rapid prototyping

  • one could accidentally copy and paste only a part of the code, and incomplete input may trigger a break loop;
  • even more dangerous: one could forget to reset sum to zero prior to the new calculation and obtain incorrect results;
  • the group in question may have a different variable name, so the code will have to be changed;
  • last, but not least: when GAP code is pasted into the interpreter, it is evaluated line by line. If you have a long file with many commands, and a syntax error is in line N, this error will be reported only when GAP completes the evaluation of all preceding lines, and that might be quite time-consuming.

That is why we need to give our GAP code more structure by organising it into functions:

  • functions are parsed first and may be called later;
  • any syntax errors will be detected in the parsing stage, and not at the time of the call;
  • functions may have local variables, and this prevents them being accidentally overwritten just because of reusing the same name of the variable to store something else.

The following function takes an argument G and computes the average order of its elements:

GAP 

AvgOrdOfGroup := function(G)
local sum, g;
sum := 0;
for g in G do
  sum := sum + Order(g);
od;
return sum/Size(G);
end;

OUTPUT 

function( G ) ... end

Now we can apply it to another group, passing the group as an argument:

GAP 

A:=AlternatingGroup(10); AvgOrdOfGroup(A); time;

OUTPUT 

Alt( [ 1 .. 10 ] )
2587393/259200
837

The example above also demonstrates time – this is the variable which stores the CPU time in milliseconds spent by the last command.

Thus, we may now create new groups and reuse AvgOrdOfGroup to calculate the average order of their elements in the same GAP session. Our next goal is to make it reusable for calculations in future sessions.

Using a text editor (for example, the one that you may have used for previous Software Carpentry lessons), create a text file called avgord.g containing the following function code and comments (a good chance to practise using them!):

GAP 

#####################################################################
#
# AvgOrdOfGroup(G)
#
# Calculating the average order of an element of G, where G meant to
# be a group but in fact may be any collection of objects having
# multiplicative order
#
AvgOrdOfGroup := function(G)
local sum, g;
sum := 0;
for g in G do
  sum := sum + Order(g);
od;
return sum/Size(G);
end;

Now start a new GAP session and create another group, for example MathieuGroup(11):

GAP 

M11:=MathieuGroup(11);

OUTPUT 

Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) ])

Clearly, AvgOrdOfGroup is not defined in this session, so an attempt to call this function results in an error:

GAP 

AvgOrdOfGroup(M11);

ERROR 

Error, Variable: 'AvgOrdOfGroup' must have a value
not in any function at line 2 of *stdin*

To be available, it should first be loaded using the function Read. Below we assume that the file is in the current directory, so no path is needed.

GAP 

Read("avgord.g");

This loads the file into GAP, and the function AvgOrdOfGroup is now available:

GAP 

AvgOrdOfGroup(M11);

OUTPUT 

53131/7920

In this example of using Read, a new GAP session was started to make it clear that AvgOrdOfGroup did not exist before the call of Read and was loaded from the file. However, a file with a function like this could be read multiple times in the same GAP session (later you will see cases when re-reading a file is more complicated). Calling Read again executes all code in the file being read. This means that if the code of the function has been modified, and it has no errors (but possibly has warnings), the function will be overwritten. Never ignore the warnings!

For example, let us edit the file and replace the line

GAP 

return sum/Size(G);

by the line with a deliberate syntax error:

GAP 

return Float(sum/Size(G);

Now read this file with

GAP 

Read("avgord.g");

and you will see an error message:

ERROR 

Syntax error: ) expected in avgord.g line 7
return Float(sum/Size(G);
                        ^

Since there was an error, the AvgOrdOfGroup function in our session was not redefined, and remains the same as last time it was successfully read:

GAP 

Print(AvgOrdOfGroup);

OUTPUT 

function ( G )
    for g  in G  do
        sum := sum + Order( g );
    od;
    return sum / Size( G );
end

Now correct the error by adding the missing closing bracket, read the file again and recalculate the average order of an element for M11:

GAP 

Read("avgord.g");
AvgOrdOfGroup(M11);

OUTPUT 

6.70846

Now let’s see an example of a warning. Since it is only a warning, it will redefine the function, and this may cause some unexpected result. To see what could happen, first edit the file to roll back the change in the type of the result (so it will return a rational instead of a float), and then comment out two lines as follows:

GAP 

AvgOrdOfGroup := function(G)
# local sum, g;
# sum := 0;
for g in G do
  sum := sum + Order(g);
od;
return sum/Size(G);
end;

Now, when you read the file, you will see warnings:

GAP 

Read("avgord.g");

ERROR 

Syntax error: warning: unbound global variable in avgord.g line 4
for g in G do
       ^
Syntax error: warning: unbound global variable in avgord.g line 5
  sum := sum + Order(g);
       ^
Syntax error: warning: unbound global variable in avgord.g line 5
  sum := sum + Order(g);
             ^
Syntax error: warning: unbound global variable in avgord.g line 7
return sum/Size(G);
          ^

These warnings mean that because g and sum are not declared as local variables, GAP will expect them to be global variables at the time when the function will be called. Because they did not exist when Read was called, a warning was displayed. However, if they happened to exist by that time, there would be no warning, and any call to AvgOrdOfGroup would overwrite them! This shows how important it is to declare local variables. Let us investigate what happened in slightly more detail:

The function is now redefined, as we can see from its output (or can inspect with PageSource(AvgOrdOfGroup) which will also display any comments):

GAP 

Print(AvgOrdOfGroup);

OUTPUT 

function ( G )
    for g in G  do
        sum := sum + Order( g );
    od;
    return sum / Size( G );
end

but an attempt to run it results in a break loop:

GAP 

AvgOrdOfGroup(M11);

ERROR 

Error, Variable: 'sum' must have an assigned value in
  sum := sum + Order( g ); called from
<function "AvgOrdOfGroup">( <arguments> )
 called from read-eval loop at line 24 of *stdin*
you can 'return;' after assigning a value
brk>

which you can exit using quit;.

What happens next demonstrates how things may go wrong:

GAP 

sum:=2^64; g:=[1];

OUTPUT 

18446744073709551616
[ 1 ]

GAP 

AvgOrdOfGroup(M11);

OUTPUT 

18446744073709604747/7920

GAP 

sum; g;

OUTPUT 

18446744073709604747
(1,2)(3,10,5,6,8,9)(4,7,11)

Now, before reading the next part of the lesson, please revert the last change by uncommenting the two commented lines, so that you have initial version of AvgOrdOfGroup in the file avgord.g again:

GAP 

AvgOrdOfGroup := function(G)
local sum, g;
sum := 0;
for g in G do
  sum := sum + Order(g);
od;
return sum/Size(G);
end;

Paths

  • It is important to know how to specify paths to files in all operating systems and where to find your home and current directory.

  • It is useful to know that path and filename completion is activated by pressing Esc two or four times.

Key Points

  • Command line is good for prototyping; functions are good for repeated calculations.
  • Informative function names and comments will make code more readable to your future self and to others.
  • Beware of undeclared local variables!

Content from Using regression tests

Last updated on 2024-08-28 | Edit this page

Overview

Questions

  • Test-driven development

Objectives

  • Be able to create and run test files
  • Understand how test discrepancies and runtime regressions can be identified and interpreted
  • Understand how to adjust tests to check randomised algorithms
  • Learn the ‘Make it right, then make it fast’ concept

The code of AvgOrdOfGroup is very simple, and nothing could possibly go wrong with it. By iterating over the group instead of creating a list of its elements, it avoids running out of memory (calling AsList(SymmetricGroup(11)) already results in exceeding the permitted memory). That said, the computation still takes time, with several minutes needed to calculate the average order of an element of SymmetricGroup(11). But at least we are confident that it is correct.

Now we would like to write a better version of this function using some theoretical facts we know from Group Theory. We may put avgord.g under version control to revert changes if need be; we may create a new function to keep the old one around and compare the results of both; but this could be made even more efficient if we use regression testing: this is the term for testing based on rerunning previously completed tests to check that new changes do not impact their correctness or worsen their performance.

To start with, we need to create a test file. The test file looks exactly like a GAP session, so it is easy to create it by copying and pasting a GAP session with all GAP prompts, inputs and outputs into a text file (a test file could be also created from a log file with a GAP session recorded with the help of LogTo). During the test, GAP will run all inputs from the test file, compare the outputs with those in the test file and report any differences.

GAP test files are just text files, but the common practice is to name them with the extension .tst. Now create the file avgord.tst in the current directory (to avoid typing the full path) with the following content:

GAP 

# tests for average order of a group element

# permutation group
gap> S:=SymmetricGroup(9);
Sym( [ 1 .. 9 ] )
gap> AvgOrdOfGroup(S);
3291487/362880

As you see, the test file may include comments, with certain rules specifying where they may be placed, because one should be able to distinguish comments in the test file from GAP output started with #. For that purpose, lines at the beginning of the test file that start with #, and one empty line together with one or more lines starting with #, are considered as comments. All other lines are interpreted as GAP output from the preceding GAP input.

To run the test, one should use the function Test (see documentation. For example (assuming that the function AvgOrdOfGroup is already loaded):

GAP 

Test("avgord.tst");

OUTPUT 

true

In this case, Test reported no discrepancies and returned true, so we conclude that the test has passed.

We will not cover the topic of writing a good and comprehensive test suite here, nor will we cover the various options of the Test function, allowing us, for example, to ignore differences in the output formatting, or to display the progress of the test, as these are described in its documentation.

Instead, we will now add more groups to avgord.tst, to demonstrate that the code also works with other kinds of groups, and to show various ways of combining commands in the test file:

GAP 

# tests for average order of a group element

# permutation group
gap> S:=SymmetricGroup(9);
Sym( [ 1 .. 9 ] )
gap> AvgOrdOfGroup(S);
3291487/362880

# pc group
gap> D:=DihedralGroup(512);
<pc group of size 512 with 9 generators>
gap> AvgOrdOfGroup(D);
44203/512
gap> G:=TrivialGroup();; # suppress output
gap> AvgOrdOfGroup(G);
1

# fp group
gap> F:=FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> G:=F/ParseRelators(GeneratorsOfGroup(F),"a^8=b^2=1, b^-1ab=a^-1");
<fp group on the generators [ a, b ]>
gap> IsFinite(G);
true
gap> AvgOrdOfGroup(G);
59/16

# finite matrix group over integers
gap> AvgOrdOfGroup( Group( [[0,-1],[1,0]] ) );
11/4

# matrix group over a finite field
gap> AvgOrdOfGroup(SL(2,5));
221/40

Let us test the extended version of the test again and check that it works:

GAP 

Test("avgord.tst");

OUTPUT 

true

Now we will work on a better implementation. Of course, the order of an element is an invariant of a conjugacy class of elements of a group, so we need only to know the orders of conjugacy classes of elements and their representatives. The following code, which we add into avgord.g, reads into GAP and redefines AvgOrdOfGroup without any syntax errors:

GAP 

AvgOrdOfGroup := function(G)
local cc, sum, c;
cc:=ConjugacyClasses(G);
sum:=0;
for c in cc do
  sum := sum + Order( Representative(c) ) * Size(cc);
od;
return sum/Size(G);
end;

but when we run the test, here comes a surprise!

GAP 

Read("avgord.g");
Test("avgord.tst");

OUTPUT 

########> Diff in avgord.tst, line 6:
# Input is:
AvgOrdOfGroup(S);
# Expected output:
3291487/362880
# But found:
11/672
########
########> Diff in avgord.tst, line 12:
# Input is:
AvgOrdOfGroup(D);
# Expected output:
44203/512
# But found:
2862481/512
########
########> Diff in avgord.tst, line 23:
# Input is:
AvgOrdOfGroup(G);
# Expected output:
59/16
# But found:
189/16
########
########> Diff in avgord.tst, line 29:
# Input is:
AvgOrdOfGroup(SL(2,5));
# Expected output:
221/40
# But found:
69/20
########
false

Indeed, we made a typo (deliberately) and replaced Size(c) by Size(cc). The correct version of course should look as follows:

GAP 

AvgOrdOfGroup := function(G)
local cc, sum, c;
cc:=ConjugacyClasses(G);
sum:=0;
for c in cc do
  sum := sum + Order( Representative(c) ) * Size(c);
od;
return sum/Size(G);
end;

Now we will fix this in avgord.g, and read and test it again to check that the tests run correctly.

GAP 

Read("avgord.g");
Test("avgord.tst");

OUTPUT 

true

Thus, the approach ‘Make it right, then make it fast’ helped detect a bug immediately after it has been introduced.

Key Points

  • It is easy to create a test file by copying and pasting a GAP session.
  • Writing a good and comprehensive test suite requires some effort.
  • Make it right, then make it fast!

Content from Small groups search

Last updated on 2024-08-28 | Edit this page

Overview

Questions

  • Modular programming: putting functions together
  • How to check some conjecture for all groups of a given order

Objectives

  • Using the Small Groups Library
  • Designing a system of functions to fit together

In this section, we wish to discover some non-trivial groups with an interesting property: namely, that the average order of their elements is an integer.

The GAP distribution includes a number of data libraries (for example, search for the word “library” in the list of packages distributed with GAP). One of them is the Small Groups Library by Hans Ulrich Besche, Bettina Eick and Eamonn O’Brien.

This library provides various utilities to determine which information is stored there and submit queries to search for groups with desired properties. The key functions are SmallGroup, AllSmallGroups, NrSmallGroups, SmallGroupsInformation and IdGroup. For example:

OUTPUT 

gap> NrSmallGroups(64);
267
gap> SmallGroupsInformation(64);

  There are 267 groups of order 64.
  They are sorted by their ranks.
     1 is cyclic.
     2 - 54 have rank 2.
     55 - 191 have rank 3.
     192 - 259 have rank 4.
     260 - 266 have rank 5.
     267 is elementary abelian.

  For the selection functions the values of the following attributes
  are precomputed and stored:
     IsAbelian, PClassPGroup, RankPGroup, FrattinifactorSize and
     FrattinifactorId.

  This size belongs to layer 2 of the SmallGroups library.
  IdSmallGroup is available for this size.

gap> G:=SmallGroup(64,2);
<pc group of size 64 with 6 generators>
gap> AllSmallGroups(Size,64,NilpotencyClassOfGroup,5);
[ <pc group of size 64 with 6 generators>, <pc group of size 64 with 6 generators>,
  <pc group of size 64 with 6 generators> ]
gap> List(last,IdGroup);
[ [ 64, 52 ], [ 64, 53 ], [ 64, 54 ] ]

We would like to use our own testing function, which we will create here, using inline notation (available for one-argument functions):

GAP 

TestOneGroup := G -> IsInt( AvgOrdOfGroup(G) );

Now try, for example

GAP 

List([TrivialGroup(),Group((1,2))],TestOneGroup);

OUTPUT 

[ true, false ]

GAP 

gap> AllSmallGroups(Size,24,TestOneGroup,true);

OUTPUT 

[ ]

Modular programming begins here

Why is returning booleans a good design decision for such functions, instead of just printing information or returning a string such as "YES" ?

This is a simple example of a function which tests all groups of a given order. It creates one group at a time, checks the desired property, and returns as soon as an example is discovered. Otherwise it returns fail which is a special kind of boolean variable in GAP.

GAP 

TestOneOrderEasy := function(n)
local i;
for i in [1..NrSmallGroups(n)] do
  if TestOneGroup( SmallGroup( n, i ) ) then
    return [n,i];
  fi;
od;
return fail;
end;

For example,

GAP 

TestOneOrderEasy(1);

OUTPUT 

[ 1, 1 ]

GAP 

TestOneOrderEasy(24);

OUTPUT 

fail

AllSmallGroups runs out of memory – what to do?

  • Use iteration over [1..NrSmallGroups(n)] as shown in the function above
  • Use IdsOfAllSmallGroups which accepts same arguments as AllSmallGroups but returns ids instead of groups.

Iterating over [1..NrSmallGroups(n)] gives you more flexibility if you need more control over the progress of calculation. For example, the next version of our testing function prints additional information about the number of the group being tested. It also supplies the testing function as an argument (why do you think this is better?).

GAP 

TestOneOrder := function(f,n)
local i, G;
for i in [1..NrSmallGroups(n)] do
  Print(n, ":", i, "/", NrSmallGroups(n), "\r");
  G := SmallGroup( n, i );
  if f(G) then
    Print("\n");
    return [n,i];
  fi;
od;
Print("\n");
return fail;
end;

For example,

GAP 

TestOneOrder(TestOneGroup,64);

will display a changing counter during calculation and then return fail:

OUTPUT 

64:267/267
fail

The next step is to integrate TestOneOrder into a function which will test all orders from 2 to n and stop as soon as it finds an example of a group with the average order of an element being an integer:

GAP 

TestAllOrders:=function(f,n)
local i, res;
for i in [2..n] do
  res:=TestOneOrder(f,i);
  if res <> fail then
    return res;
  fi;
od;
return fail;
end;

It reports that there is such a group of order 105:

GAP 

TestAllOrders(TestOneGroup,128);

OUTPUT 

2:1/1
3:1/1
4:2/2
5:1/1
6:2/2
7:1/1
8:5/5
...
...
...
100:16/16
101:1/1
102:4/4
103:1/1
104:14/14
105:1/2
[ 105, 1 ]

To explore it further, we can get its StructureDescription (see documentation for the explanation of the notation it uses):

GAP 

G:=SmallGroup(105,1); AvgOrdOfGroup(G); StructureDescription(G);

OUTPUT 

<pc group of size 105 with 3 generators>
17
"C5 x (C7 : C3)"

and then convert it to a finitely presented group to see its generators and relators:

GAP 

H:=SimplifiedFpGroup(Image(IsomorphismFpGroup(G)));
RelatorsOfFpGroup(H);

OUTPUT 

<fp group on the generators [ F1, F2, F3 ]>
[ F1^3, F2^-1*F1^-1*F2*F1, F3^-1*F2^-1*F3*F2, F3^-1*F1^-1*F3*F1*F3^-1, F2^5,
  F3^7 ]

Now we want to try larger groups, starting from order 106 (we check that the other group of order 105 possesses no such property)

GAP 

List(AllSmallGroups(105),AvgOrdOfGroup);

OUTPUT 

[ 17, 301/5 ]

With a little modification, we add an extra argument specifying the order from which to start:

GAP 

TestRangeOfOrders:=function(f,n1,n2)
local n, res;
for n in [n1..n2] do
  res:=TestOneOrder(f,n);
  if res <> fail then
    return res;
  fi;
od;
return fail;
end;

But now we call it with

GAP 

TestRangeOfOrders(TestOneGroup,106,256);

and discover that testing 2328 groups of order 128 and additionally 56092 groups of order 256 already takes too long.

Don’t panic!

You can interrupt GAP by pressing Ctrl-C once. After that, GAP will enter a break loop, designated by the break prompt brk>. You can leave it by typing quit; (beware of pressing Ctrl-C twice within a second – that will terminate GAP session completely).

This is another situation where theoretical knowledge helps much more than the brute-force approach. If the group is a p-group, then the order of each conjugacy class of a non-identity element of the group is divisible by p; therefore, the average order of a group element may not be an integer. Therefore, p-groups can be excluded from calculation. So, the new version of the code is

GAP 

TestRangeOfOrders:=function(f,n1,n2)
local n, res;
for n in [n1..n2] do
  if not IsPrimePowerInt(n) then
     res:=TestOneOrder(f,n);
     if res <> fail then
       return res;
     fi;
   fi;
od;
return fail;
end;

and using it we are able to discover a group of order 357 with the same property:

GAP 

gap> TestRangeOfOrders(TestOneGroup,106,512);

OUTPUT 

106:2/2
108:45/45
...
350:10/10
351:14/14
352:195/195
354:4/4
355:2/2
356:5/5
357:1/2
[ 357, 1 ]

The next function shows even further flexibility: it is variadic, i.e. it may accept two or more arguments, the first two of which will be assigned to the variables f and n, and the rest of which will be available in the list r (this is indicated by ... after r). The first argument is the testing function, the second is the order to check, and the third and the fourth are the numbers of the first and last groups of this order that should be checked. By default, the last two are equal to 1 and NrSmallGroups(n) respectively. This function also shows how to validate the input and produce user-friendly error messages in case of invalid arguments.

In addition, this function demonstrates how to use Info messages that may be switched on and off by setting appropriate Info level. The need we address here is to be able to switch the levels of verbosity of the output without error-prone approach of walking through the code and commenting Print statements in and out. It is achieved by creating an info class:

GAP 

gap> InfoSmallGroupsSearch := NewInfoClass("InfoSmallGroupsSearch");

OUTPUT 

InfoSmallGroupsSearch

Now instead of Print("something"); one could use Info( InfoSmallGroupsSearch, infolevel, "something" ); where infolevel is a positive integer specifying the level of verbosity. This level could be changed to n using the command SetInfoLevel( InfoSmallGroupsSearch, n);. See actual calls of Info in the code below:

GAP 

TestOneOrderVariadic := function(f,n,r...)
local n1, n2, i;

if not Length(r) in [0..2] then
  Error("The number of arguments must be 2,3 or 4\n" );
fi;

if not IsFunction( f ) then
  Error("The first argument must be a function\n" );
fi;

if not IsPosInt( n ) then
  Error("The second argument must be a positive integer\n" );
fi;

if IsBound(r[1]) then
  n1:=r[1];
  if not n1 in [1..NrSmallGroups(n)] then
    Error("The 3rd argument, if present, must belong to ", [1..NrSmallGroups(n)], "\n" );
  fi;
else
  n1:=1;
fi;

if IsBound(r[2]) then
  n2:=r[2];
  if not n2 in [1..NrSmallGroups(n)] then
    Error("The 4th argument, if present, must belong to ", [1..NrSmallGroups(n)], "\n" );
  elif n2 < n1 then
    Error("The 4th argument, if present, must be greater or equal to the 3rd \n" );
  fi;
else
  n2:=NrSmallGroups(n);
fi;

Info( InfoSmallGroupsSearch, 1,
      "Checking groups ", n1, " ... ", n2, " of order ", n );
for i in [n1..n2] do
  if InfoLevel( InfoSmallGroupsSearch ) > 1 then
    Print(i, "/", NrSmallGroups(n), "\r");
  fi;
  if f(SmallGroup(n,i)) then
    Info( InfoSmallGroupsSearch, 1,
          "Discovered counterexample: SmallGroup( ", n, ", ", i, " )" );
    return [n,i];
  fi;
od;
Info( InfoSmallGroupsSearch, 1,
      "Search completed - no counterexample discovered" );
return fail;
end;

The following example demonstrates how the output may now be controlled by switching the info level for InfoSmallGroupsSearch:

OUTPUT 

gap> TestOneOrderVariadic(IsIntegerAverageOrder,24);
fail
gap> SetInfoLevel( InfoSmallGroupsSearch, 1 );
gap> TestOneOrderVariadic(IsIntegerAverageOrder,24);
#I  Checking groups 1 ... 15 of order 24
#I  Search completed - no counterexample discovered
fail
gap> TestOneOrderVariadic(IsIntegerAverageOrder,357);
#I  Checking groups 1 ... 2 of order 357
#I  Discovered counterexample: SmallGroup( 357, 1 )
[ 357, 1 ]
gap> SetInfoLevel( InfoSmallGroupsSearch, 0);
gap> TestOneOrderVariadic(IsIntegerAverageOrder,357);
[ 357, 1 ]

Of course, this now introduces some complication for the test file, which compares the actual output with the reference output. To resolve this problem, we will decide to run the tests at info level 0 to suppress all additional outputs. Because the tests may have been started in the GAP session with a different info level, we will remember that info level to restore it after the test:

OUTPUT 

# Finding groups with integer average order
gap> INFO_SSS:=InfoLevel(InfoSmallGroupsSearch);;
gap> SetInfoLevel( InfoSmallGroupsSearch, 0);
gap> res:=[];;
gap> for n in [1..360] do
>      if not IsPrimePowerInt(n) then
>        t := TestOneOrderVariadic( IsIntegerAverageOrder,n,1,NrSmallGroups(n) );
>        if t <> fail then
>          Add(res,t);
>        fi;
>      fi;
>    od;
gap> res;
[ [ 1, 1 ], [ 105, 1 ], [ 357, 1 ] ]
gap> SetInfoLevel( InfoSmallGroupsSearch, INFO_SSS);

Does the Small Groups Library contain another group with this property?

  • What can you say about the order of the groups with this property?

  • Can you estimate how long it may take to check all 408641062 groups of order 1536?

  • How many groups of order not higher than 2000 might you be able to check, excluding p-groups and those of order 1536?

  • Can you find another group with this property in the Small Groups Library (of order not equal to 1536)?

Key Points

  • Organise the code into functions.
  • Create small groups one by one instead of producing a huge list of them.
  • Using SmallGroupsInformation may help to reduce the search space.
  • GAP is not a magic tool: theoretical knowledge may help much more than the brute-force approach.

Content from Attributes and Methods

Last updated on 2024-08-28 | Edit this page

Overview

Questions

  • How to record information in GAP objects

Objectives

  • Declaring an attribute
  • Installing a method
  • Understanding method selection
  • Using debugging tools

Which function is faster?

Try to repeatedly calculate AvgOrdOfGroup(M11) and AvgOrdOfCollection(M11) and compare runtimes. Do this for a new copy of M11 and for the one for which this parameter has already been observed. What do you observe?

Of course, for any given group the average order of its elements needs to be calculated only once, as the next time it will return the same value. However, as we see from the runtimes below, each new call of AvgOrdOfGroup will repeat the same computation again, with slightly varying runtime:

GAP 

A:=AlternatingGroup(10);

OUTPUT 

Alt( [ 1 .. 10 ] )

GAP 

AvgOrdOfCollection(A); time; AvgOrdOfCollection(A); time;

OUTPUT 

2587393/259200
8226
2587393/259200
8118

In the last example, the group in question was the same – we haven’t constructed another copy of AlternatingGroup(10); however, the result of the calculation was not stored in A.

If you need to reuse this value, one option could be to store it in some variable, but then you should be careful about matching such variables with corresponding groups, and the code could become quite convoluted and unreadable. On the other hand, GAP has the notion of an attribute – a data structure that is used to accumulate information that an object learns about itself during its lifetime. Consider the following example:

GAP 

G:=Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) ]);
gap> NrConjugacyClasses(G);time;NrConjugacyClasses(G);time;

OUTPUT 

Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) ])
10
39
10
0

In this case, the group G has 10 conjugacy classes, and it took 39 ms to establish that in the first call. The second call has zero cost since the result was stored in G, since NrConjugacyClasses is an attribute:

GAP 

NrConjugacyClasses;

OUTPUT 

<Attribute "NrConjugacyClasses">

Our goal is now to learn how to create own attributes.

Since we already have a function AvgOrdOfCollection which does the calculation, the simplest way to turn it into an attribute is as follows:

GAP 

AverageOrder := NewAttribute("AverageOrder", IsCollection);
InstallMethod( AverageOrder, "for a collection", [IsCollection], AvgOrdOfCollection);

In this example, first we declared an attribute AverageOrder for objects in the category IsCollection, and then installed the function AvgOrdOfCollection as a method for this attribute. Instead of calling the function AvgOrdOfCollection, we may now call AverageOrder.

Now we may check that subsequent calls of AverageOrder with the same argument are performed at zero cost. In this example the time is reduced from more than 16 seconds to zero:

GAP 

S:=SymmetricGroup(10);; AverageOrder(S); time; AverageOrder(S); time;

OUTPUT 

39020911/3628800
16445
39020911/3628800
0

You may wonder why we have declared the operation for a collection and not only for a group, and why we have installed the inefficient AvgOrdOfCollection. After all, we have already developed the much more efficient AvgOrdOfGroup.

Imagine that you would like to be able to compute an average order both for a group and for a list which consists of objects having a multiplicative order. You may have a special function for each case, as we have. If it could happen that you don’t know in advance the type of the object in question, you may add checks into the code and dispatch to a suitable function. This could quickly become complicated if you have several different functions for various types of objects. Instead of that, attributes are bunches of functions, called methods, and GAP’s method selection will choose the most efficient method based on the type of all arguments.

To illustrate this, we will now install a method for AverageOrder for a group:

GAP 

InstallMethod( AverageOrder, [IsGroup], AvgOrdOfGroup);

If you apply it to a group whose AverageOrder has already been computed, nothing will happen, since GAP will use the stored value. However, for a newly created group, this new method will be called:

GAP 

S:=SymmetricGroup(10);; AverageOrder(S); time; AverageOrder(S); time;

OUTPUT 

39020911/3628800
26
39020911/3628800
0

Which method is being called

  • Try to call AverageOrder for a collection which is not a group (a list of group elements and/or a conjugacy class of group elements).

  • Debugging tools like TraceMethods may help you see which method is being called.

  • ApplicableMethod in combination with PageSource may point you to the source code with all the comments.

A property is a boolean-valued attribute. It can be created using NewProperty

GAP 

IsIntegerAverageOrder := NewProperty("IsIntegerAverageOrder", IsCollection);

Now we will install a method for IsIntegerAverageOrder for a collection. Observe that it is never necessary to create a function first and then install it as a method. The following method installation instead creates a new function as one of its arguments:

GAP 

InstallMethod( IsIntegerAverageOrder,
  "for a collection",
  [IsCollection],
  coll -> IsInt( AverageOrder( coll ) )
);

Note that because AverageOrder is an attribute it will take care of the selection of the most suitable method.

Does such a method always exist?

No. “No-method-found” is a special kind of error, and there are tools to investigate such errors: see ?ShowArguments, ?ShowDetails, ?ShowMethods and ?ShowOtherMethods.

The following calculation shows that despite our success with calculating the average order for large permutation groups via conjugacy classes of elements, for pc groups from the Small Groups Library it could be faster to iterate over their elements than to calculate conjugacy classes:

GAP 

l:=List([1..1000],i->SmallGroup(1536,i));; List(l,AvgOrdOfGroup);;time;

OUTPUT 

56231

GAP 

l:=List([1..1000],i->SmallGroup(1536,i));; List(l,AvgOrdOfCollection);;time;

OUTPUT 

9141

Don’t panic!

  • Install a method for IsPcGroup that iterates over the group elements instead of calculations its conjugacy classes.

  • Estimate practical boundaries of its feasibility. Can you find an example of a pc group where iterating is slower than calculating conjugacy classes?

Key Points

  • Positional objects may accumulate information about themselves during their lifetime.
  • This means that next time the stored information may be retrieved at zero cost.
  • Methods are bunches of functions; GAP’s method selection will choose the most efficient method based on the type of all arguments.
  • ‘No-method-found’ is a special kind of error with useful debugging tools helping to understand it.