This chapter introduces you to the GAP system. It describes how to start GAP (you may have to ask your system administrator to install it correctly) and how to leave it. Then a step by step introduction should give you an impression of how the GAP system works. Further sections will give an overview about the features of GAP. After reading this chapter the reader should know what kind of problems can be handled with GAP and how they can be handled.
There is some repetition in this chapter and much of the material is repeated in later chapters in a more compact and precise way. Yes, there are even some little inaccuracies in this chapter simplifying things for better understanding. It should be used as a tutorial introduction while later chapters form the reference manual.
GAP is an interactive system. It continuously executes a read--evaluate--print cycle. Each expression you type at the keyboard is read by GAP, evaluated, and then the result is printed.
The interactive nature of GAP allows you to type an expression at the keyboard and see its value immediately. You can define a function and apply it to arguments to see how it works. You may even write whole programs containing lots of functions and test them without leaving the program.
When your program is large it will be more convenient to write it on a file and then read that file into GAP. Preparing your functions in a file has several advantages. You can compose your functions more carefully in a file (with your favorite text editor), you can correct errors without retyping the whole function and you can keep a copy for later use. Moreover you can write lots of comments into the program text, which are ignored by GAP, but are very useful for human readers of your program text.
GAP treats input from a file in the same way that it treats input from the keyboard.
The printed examples in this first chapter encourage you to try running GAP on your computer. This will support your feeling for GAP as a tool, which is the leading aim of this chapter. Do not believe any statement in this chapter so long as you cannot verify it for your own version of GAP. You will learn to distinguish between small deviations of the behavior of your personal GAP from the printed examples and serious nonsense.
Since the printing routines of GAP are in some sense machine dependent you will for instance encounter a different layout of the printed objects in different environments. But the contents should always be the same.
In case you encounter serious nonsense it is highly recommended that you
send a bug report to gap-forum@samson.math.rwth-aachen.de.
If you read this introduction on-line you should now enter ?> to read
the next section.
Throughout this manual both the input given to GAP and the output that
GAP returns are printed in typewriter font just as if they were
typed at the keyboard.
An italic font is used for keys that have no printed representation, such as e.g. the newline key and the ctl key. This font is also used for the formal parameters of functions that are described in later chapters.
A combination like ctl-P means pressing both keys, that is holding
the control key ctl and pressing the key P while ctl is still
pressed.
New terms are introduced in bold face.
In most places whitespace characters (i.e. spaces, tabs and newlines) are insignificant for the meaning of GAP input. Identifiers and keywords must however not contain any whitespace. On the other hand, sometimes there must be whitespace around identifiers and keywords to separate them from each other and from numbers. We will use whitespace to format more complicated commands for better readability.
A comment in GAP starts with the symbol # and continues to the
end of the line. Comments are treated like whitespace by GAP.
Besides of such comments which are part of the input of a GAP session, we use additional comments which are part of the manual description, but not of the respective GAP session. In the printed version of this manual these comments will be printed in a normal font for better readability, hence they start with the symbol #.
The examples of GAP sessions given in any particular chapter of this manual have been run in one continuous session, starting with the two commands
SizeScreen( [ 72, ] );
LogTo( "erg.log" );
which are used to set the line length to 72 and to save a listing of the session on some file. If you choose any chapter and rerun its examples in the given order, you should be able to reproduce our results except of a few lines of output which we have edited a little bit with respect to blanks or line breaks in order to improve the readability. However, as soon as random processes are involved, you may get different results if you extract single examples and run them separately.
1.2 About Starting and Leaving GAP
If the program is correctly installed then you start GAP by simply
typing gap at the prompt of your operating system followed by the
return or the newline key.
$ gap
GAP answers your request with its beautiful banner (which you can
surpress with the command line option -b) and then it shows its own
prompt gap> asking you for further input.
gap>
The usual way to end a GAP session is to type quit; at the gap>
prompt. Do not omit the semicolon!
gap> quit;
$
On some systems you may as well type ctl-D to yield the same effect.
In any situation GAP is ended by typing ctl-C twice within a
second.
A simple calculation with GAP is as easy as one can imagine. You type
the problem just after the prompt, terminate it with a semicolon and then
pass the problem to the program with the return key. For example, to
multiply the difference between 9 and 7 by the sum of 5 and 6, that is to
calculate (9 - 7) * (5 + 6), you type exactly this last sequence of
symbols followed by ; and return.
gap> (9 - 7) * (5 + 6);
22
gap>
Then GAP echoes the result 22 on the next line and shows with the prompt that it is ready for the next problem.
If you did omit the semicolon at the end of the line but have already
typed return, then GAP has read everything you typed, but does not
know that the command is complete. The program is waiting for further
input and indicates this with a partial prompt >. This little problem
is solved by simply typing the missing semicolon on the next line of
input. Then the result is printed and the normal prompt returns.
gap> (9 - 7) * (5 + 6)
> ;
22
gap>
Whenever you see this partial prompt and you cannot decide what GAP is still waiting for, then you have to type semicolons until the normal prompt returns.
In every situation this is the exact meaning of the prompt gap> : the
program is waiting for a new problem. In the following examples we will
omit this prompt on the line after the result. Considering each example
as a continuation of its predecessor this prompt occurs in the next
example.
In this section you have seen how simple arithmetic problems can be solved by GAP by simply typing them in. You have seen that it doesn't matter whether you complete your input on one line. GAP reads your input line by line and starts evaluating if it has seen the terminating semicolon and return.
It is, however, also possible (and might be advisable for large amounts of input data) to write your input first into a file, and then read this into GAP; see Edit and Read for this.
Also in GAP, there is the possibility to edit the input data, see Line Editing.
The contents of the GAP manual is also available as on-line help, see
Help--Help Index. If you need information about a section of the
manual, just enter a question mark followed by the header of the section.
E.g., entering ?About Help will print the section you are reading now.
??topic will print all entries in GAP's index that contain the
substring topic.
Even if you mistyped the command you do not have to type it all again as GAP permits a lot of command line editing. Maybe you mistyped or forgot the last closing parenthesis. Then your command is syntactically incorrect and GAP will notice it, incapable of computing the desired result.
gap> (9 - 7) * (5 + 6;
Syntax error: ) expected
(9 - 7) * (5 + 6;
^
Instead of the result an error message occurs indicating the place where
an unexpected symbol occurred with an arrow sign ^ under it. As a
computer program cannot know what your intentions really were, this is
only a hint. But in this case GAP is right by claiming that there
should be a closing parenthesis before the semicolon. Now you can type
ctl-P to recover the last line of input. It will be written after
the prompt with the cursor in the first position. Type ctl-E to take
the cursor to the end of the line, then ctl-B to move the cursor one
character back. The cursor is now on the position of the semicolon.
Enter the missing parenthesis by simply typing ). Now the line is
correct and may be passed to GAP by hitting the newline key. Note
that for this action it is not necessary to move the cursor past the last
character of the input line.
Each line of commands you type is sent to GAP for evaluation by pressing newline regardless of the position of the cursor in that line. We will no longer mention the newline key from now on.
Sometimes a syntax error will cause GAP to enter a break loop. This
is indicated by the special prompt brk>. You can leave the break loop
by either typing return; or by hitting ctl-D. Then GAP will
return to its normal state and show its normal prompt again.
In this section you learned that mistyped input will not lead to big confusion. If GAP detects a syntax error it will print an error message and return to its normal state. The command line editing allows you in a comfortable way to manipulate earlier input lines.
For the definition of the GAP syntax see chapter The Programming Language. A complete list of command line editing facilities is found in Line Editing. The break loop is described in Break Loops.
1.6 About Constants and Operators
In an expression like (9 - 7) * (5 + 6) the constants 5, 6, 7, and 9
are being composed by the operators +, * and - to result in a new
value.
There are three kinds of operators in GAP, arithmetical operators, comparison operators, and logical operators. You have already seen that it is possible to form the sum, the difference, and the product of two integer values. There are some more operators applicable to integers in GAP. Of course integers may be divided by each other, possibly resulting in noninteger rational values.
gap> 12345/25;
2469/5
Note that the numerator and denominator are divided by their greatest common divisor and that the result is uniquely represented as a division instruction.
We haven't met negative numbers yet. So consider the following self--explanatory examples.
gap> -3; 17 - 23;
-3
-6
The exponentiation operator is written as ^. This operation in
particular might lead to very large numbers. This is no problem for
GAP as it can handle numbers of (almost) arbitrary size.
gap> 3^132;
955004950796825236893190701774414011919935138974343129836853841
The mod operator allows you to compute one value modulo another.
gap> 17 mod 3;
2
Note that there must be whitespace around the keyword mod in this
example since 17mod3 or 17mod would be interpreted as identifiers.
GAP knows a precedence between operators that may be overridden by parentheses.
gap> (9 - 7) * 5 = 9 - 7 * 5;
false
Besides these arithmetical operators there are comparison operators in
GAP. A comparison results in a boolean value which is another kind
of constant. Every two objects within GAP are comparable via =,
<>, <, <=, > and >=, that is the tests for equality,
inequality, less than, less than or equal, greater than and greater than
or equal. There is an ordering defined on the set of all GAP objects
that respects orders on subsets that one might expect. For example the
integers are ordered in the usual way.
gap> 10^5 < 10^4;
false
The boolean values true and false can be manipulated via logical
operators, i. e., the unary operator not and the binary operators and
and or. Of course boolean values can be compared, too.
gap> not true; true and false; true or false;
false
false
true
gap> 10 > 0 and 10 < 100;
true
Another important type of constants in GAP are permutations. They are written in cycle notation and they can be multiplied.
gap> (1,2,3);
(1,2,3)
gap> (1,2,3) * (1,2);
(2,3)
The inverse of the permutation (1,2,3) is denoted by (1,2,3)^-1.
Moreover the caret operator ^ is used to determine the image of a point
under a permutation and to conjugate one permutation by another.
gap> (1,2,3)^-1;
(1,3,2)
gap> 2^(1,2,3);
3
gap> (1,2,3)^(1,2);
(1,3,2)
The last type of constants we want to introduce here are the
characters, which are simply objects in GAP that represent arbitrary
characters from the character set of the operating system. Character
literals can be entered in GAP by enclosing the character in
singlequotes '.
gap> 'a';
'a'
gap> '*';
'*'
There are no operators defined for characters except that characters can be compared.
In this section you have seen that values may be preceded by unary operators and combined by binary operators placed between the operands. There are rules for precedence which may be overridden by parentheses. It is possible to compare any two objects. A comparison results in a boolean value. Boolean values are combined via logical operators. Moreover you have seen that GAP handles numbers of arbitrary size. Numbers and boolean values are constants. There are other types of constants in GAP like permutations. You are now in a position to use GAP as a simple desktop calculator.
Operators are explained in more detail in Comparisons and Operations. Moreover there are sections about operators and comparisons for special types of objects in almost every chapter of this manual. You will find more information about boolean values in chapters Booleans and Boolean Lists. Permutations are described in chapter Permutations and characters are described in chapter Strings and Characters.
1.7 About Variables and Assignments
Values may be assigned to variables. A variable enables you to refer to
an object via a name. The name of a variable is called an identifier.
The assignment operator is :=. There must be no white space between
the : and the =. Do not confuse the assignment operator := with
the single equality sign = which is in GAP only used for the test of
equality.
gap> a:= (9 - 7) * (5 + 6);
22
gap> a;
22
gap> a * (a + 1);
506
gap> a:= 10;
10
gap> a * (a + 1);
110
After an assignment the assigned value is echoed on the next line. The printing of the value of a statement may be in every case prevented by typing a double semicolon.
gap> w:= 2;;
After the assignment the variable evaluates to that value if evaluated. Thus it is possible to refer to that value by the name of the variable in any situation.
This is in fact the whole secret of an assignment. An identifier is bound to a value and from this moment points to that value. Nothing more. This binding is changed by the next assignment to that identifier. An identifier does not denote a block of memory as in some other programming languages. It simply points to a value, which has been given its place in memory by the GAP storage manager. This place may change during a GAP session, but that doesn't bother the identifier.
The identifier points to the value, not to a place in the memory.
For the same reason it is not the identifier that has a type but the
object. This means on the other hand that the identifier a which now
is bound to an integer value may in the same session point to any other
value regardless of its type.
Identifiers may be sequences of letters and digits containing at least
one letter. For example abc and a0bc1 are valid identifiers. But
also 123a is a valid identifier as it cannot be confused with any
number. Just 1234 indicates the number 1234 and cannot be at the same
time the name of a variable.
Since GAP distinguishes upper and lower case, a1 and A1 are
different identifiers. Keywords such as quit must not be used as
identifiers. You will see more keywords in the following sections.
In the remaining part of this manual we will ignore the difference
between variables, their names (identifiers), and the values they point
at. It may be useful to think from time to time about what is really
meant by terms such as the integer w.
There are some predefined variables coming with GAP. Many of them you will find in the remaining chapters of this manual, since functions are also referred to via identifiers.
This seems to be the right place to state the following rule.
The name of every function in the GAP library starts with a capital letter.
Thus if you choose only names starting with a small letter for your own variables you will not overwrite any predefined function.
But there are some further interesting variables one of which shall be introduced now.
Whenever GAP returns a value by printing it on the next line this
value is assigned to the variable last. So if you computed
gap> (9 - 7) * (5 + 6);
22
and forgot to assign the value to the variable a for further use, you
can still do it by the following assignment.
gap> a:= last;
22
Moreover there are variables last2 and last3, guess their values.
In this section you have seen how to assign values to variables. These
values can later be accessed through the name of the variable, its
identifier. You have also encountered the useful concept of the last
variables storing the latest returned values. And you have learned that
a double semicolon prevents the result of a statement from being printed.
Variables and assignments are described in more detail in Variables and Assignments. A complete list of keywords is contained in Keywords.
A program written in the GAP language is called a function.
Functions are special GAP objects. Most of them behave like
mathematical functions. They are applied to objects and will return a
new object depending on the input. The function Factorial, for
example, can be applied to an integer and will return the factorial of
this integer.
gap> Factorial(17);
355687428096000
Applying a function to arguments means to write the arguments in
parentheses following the function. Several arguments are separated by
commas, as for the function Gcd which computes the greatest common
divisor of two integers.
gap> Gcd(1234, 5678);
2
There are other functions that do not return a value but only produce a
side effect. They change for example one of their arguments. These
functions are sometimes called procedures. The function Print is only
called for the side effect to print something on the screen.
gap> Print(1234, "\n");
1234
In order to be able to compose arbitrary text with Print, this function
itself will not produce a line break after printing. Thus we had another
newline character "\n" printed to start a new line.
Some functions will both change an argument and return a value such as
the function Sortex that sorts a list and returns the permutation of
the list elements that it has performed.
You will not understand right now what it means to change an object. We will return to this subject several times in the next sections.
A comfortable way to define a function is given by the maps--to
operator -> consisting of a minus sign and a greater sign with no
whitespace between them. The function cubed which maps a number to its
cube is defined on the following line.
gap> cubed:= x -> x^3;
function ( x ) ... end
After the function has been defined, it can now be applied.
gap> cubed(5);
125
Not every GAP function can be defined in this way. You will see how to write your own GAP functions in a later section.
In this section you have seen GAP objects of type function. You have learned how to apply a function to arguments. This yields as result a new object or a side effect. A side effect may change an argument of the function. Moreover you have seen an easy way to define a function in GAP with the maps-to operator.
Function calls are described in Function Calls and in Procedure Calls. The functions of the GAP library are described in detail in the remaining chapters of this manual, the Reference Manual.
A list is a collection of objects separated by commas and enclosed in
brackets. Let us for example construct the list primes of the first 10
prime numbers.
gap> primes:= [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]
The next two primes are 31 and 37. They may be appended to the existing
list by the function Append which takes the existing list as its first
and another list as a second argument. The second argument is appended
to the list primes and no value is returned. Note that by appending
another list the object primes is changed.
gap> Append(primes, [31, 37]);
gap> primes;
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ]
You can as well add single new elements to existing lists by the function
Add which takes the existing list as its first argument and a new
element as its second argument. The new element is added to the list
primes and again no value is returned but the list primes is changed.
gap> Add(primes, 41);
gap> primes;
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 ]
Single elements of a list are referred to by their position in the list.
To get the value of the seventh prime, that is the seventh entry in our
list primes, you simply type
gap> primes[7];
17
and you will get the value of the seventh prime. This value can be
handled like any other value, for example multiplied by 2 or assigned to
a variable. On the other hand this mechanism allows to assign a value to
a position in a list. So the next prime 43 may be inserted in the list
directly after the last occupied position of primes. This last
occupied position is returned by the function Length.
gap> Length(primes);
13
gap> primes[14]:= 43;
43
gap> primes;
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 ]
Note that this operation again has changed the object primes. Not only
the next position of a list is capable of taking a new value. If you
know that 71 is the 20th prime, you can as well enter it right now in the
20th position of primes. This will result in a list with holes which
is however still a list and has length 20 now.
gap> primes[20]:= 71;
71
gap> primes;
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,,,,,, 71 ]
gap> Length(primes);
20
The list itself however must exist before a value can be assigned to a
position of the list. This list may be the empty list [ ].
gap> lll[1]:= 2;
Error, Variable: 'lll' must have a value
gap> lll:= [];
[ ]
gap> lll[1]:= 2;
2
Of course existing entries of a list can be changed by this mechanism,
too. We will not do it here because primes then may no longer be a
list of primes. Try for yourself to change the 17 in the list into a 9.
To get the position of 17 in the list primes use the function
Position which takes the list as its first argument and the element as
its second argument and returns the position of the first occurrence of
the element 17 in the list primes. Position will return false if
the element is not contained in the list.
gap> Position(primes, 17);
7
gap> Position(primes, 20);
false
In all of the above changes to the list primes, the list has been
automatically resized. There is no need for you to tell GAP how big
you want a list to be. This is all done dynamically.
It is not necessary for the objects collected in a list to be of the same type.
gap> lll:= [true, "This is a String",,, 3];
[ true, "This is a String",,, 3 ]
In the same way a list may be part of another list. A list may even be part of itself.
gap> lll[3]:= [4,5,6];; lll;
[ true, "This is a String", [ 4, 5, 6 ],, 3 ]
gap> lll[4]:= lll;
[ true, "This is a String", [ 4, 5, 6 ], ~, 3 ]
Now the tilde ~ in the fourth position of lll denotes the object that
is currently printed. Note that the result of the last operation is the
actual value of the object lll on the right hand side of the
assignment. But in fact it is identical to the value of the whole list
lll on the left hand side of the assignment.
A string is a very special type of list, which is printed in a
different way. A string is simply a dense list of characters. Strings
are used mainly in filenames and error messages. A string literal can
either be entered simply as the list of characters or by writing the
characters between doublequotes ". GAP will always output strings
in the latter format.
gap> s1 := ['H','a','l','l','o',' ','w','o','r','l','d','.'];
"Hallo world."
gap> s2 := "Hallo world.";
"Hallo world."
gap> s1 := ['H','a','l','l','o',' ','w','o','r','l','d','.'];
"Hallo world."
gap> s1 = s2;
true
gap> s2[7];
'w'
Sublists of lists can easily be extracted and assigned using the operator
{ }.
gap> sl := lll{ [ 1, 2, 3 ] };
[ true, "This is a String", [ 4, 5, 6 ] ]
gap> sl{ [ 2, 3 ] } := [ "New String", false ];
[ "New String", false ]
gap> sl;
[ true, "New String", false ]
This way you get a new list that contains at position i that element
whose position is the ith entry of the argument of { }.
In this long section you have encountered the fundamental concept of a list. You have seen how to construct lists, how to extend them and how to refer to single elements of a list. Moreover you have seen that lists may contain elements of different types, even holes (unbound entries). But this is still not all we have to tell you about lists.
You will find a discussion about identity and equality of lists in the next section. Moreover you will see special kinds of lists like sets (in About Sets), vectors and matrices (in About Vectors and Matrices) and ranges (in About Ranges). Strings are described in chapter Strings and Characters.
This second section about lists is dedicated to the subtle difference between equality and identity of lists. It is really important to understand this difference in order to understand how complex data structures are realized in GAP. This section applies to all GAP objects that have subobjects, i. e., to lists and to records. After reading the section about records (About Records) you should return to this section and translate it into the record context.
Two lists are equal if all their entries are equal. This means that the
equality operator = returns true for the comparison of two lists if
and only if these two lists are of the same length and for each position
the values in the respective lists are equal.
gap> numbers:= primes;
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,,,,,, 71 ]
gap> numbers = primes;
true
We assigned the list primes to the variable numbers and, of course
they are equal as they have both the same length and the same entries.
Now we will change the third number to 4 and compare the result again
with primes.
gap> numbers[3]:= 4;
4
gap> numbers = primes;
true
You see that numbers and primes are still equal, check this by
printing the value of primes. The list primes is no longer a list of
primes! What has happened? The truth is that the lists primes and
numbers are not only equal but they are identical. primes and
numbers are two variables pointing to the same list. If you change the
value of the subobject numbers[3] of numbers this will also change
primes. Variables do not point to a certain block of storage memory
but they do point to an object that occupies storage memory. So the
assignment numbers:= primes did not create a new list in a different
place of memory but only created the new name numbers for the same old
list of primes.
The same object can have several names.
If you want to change a list with the contents of primes independently
from primes you will have to make a copy of primes by the function
Copy which takes an object as its argument and returns a copy of the
argument. (We will first restore the old value of primes.)
gap> primes[3]:= 5;
5
gap> primes;
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,,,,,, 71 ]
gap> numbers:= Copy(primes);
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,,,,,, 71 ]
gap> numbers = primes;
true
gap> numbers[3]:= 4;
4
gap> numbers = primes;
false
Now numbers is no longer equal to primes and primes still is a list
of primes. Check this by printing the values of numbers and primes.
The only objects that can be changed this way are records and lists, because only GAP objects of these types have subobjects. To clarify this statement consider the following example.
gap> i:= 1;; j:= i;; i:= i+1;;
By adding 1 to i the value of i has changed. What happens to j?
After the second statement j points to the same object as i, namely
to the integer 1. The addition does not change the object 1 but
creates a new object according to the instruction i+1. It is actually
the assignment that changes the value of i. Therefore j still points
to the object 1. Integers (like permutations and booleans) have no
subobjects. Objects of these types cannot be changed but can only be
replaced by other objects. And a replacement does not change the values
of other variables. In the above example an assignment of a new value to
the variable numbers would also not change the value of primes.
Finally try the following examples and explain the results.
gap> l:= [];
[ ]
gap> l:= [l];
[ [ ] ]
gap> l[1]:= l;
[ ~ ]
Now return to the preceding section About Lists and find out whether
the functions Add and Append change their arguments.
In this section you have seen the difference between equal lists and
identical lists. Lists are objects that have subobjects and therefore
can be changed. Changing an object will change the values of all
variables that point to that object. Be careful, since one object can
have several names. The function Copy creates a copy of a list which
is then a new object.
You will find more about lists in chapter Lists, and more about identical lists in Identical Lists.
GAP knows several special kinds of lists. A set in GAP is a special kind of list. A set contains no holes and its elements are sorted according to the GAP ordering of all its objects. Moreover a set contains no object twice.
The function IsSet tests whether an object is a set. It returns a
boolean value. For any list there exists a corresponding set. This set
is constructed by the function Set which takes the list as its argument
and returns a set obtained from this list by ignoring holes and
duplicates and by sorting the elements.
The elements of the sets used in the examples of this section are strings.
gap> fruits:= ["apple", "strawberry", "cherry", "plum"];
[ "apple", "strawberry", "cherry", "plum" ]
gap> IsSet(fruits);
false
gap> fruits:= Set(fruits);
[ "apple", "cherry", "plum", "strawberry" ]
Note that the original list fruits is not changed by the function
Set. We have to make a new assignment to the variable fruits in
order to make it a set.
The in operator is used to test whether an object is an element of a
set. It returns a boolean value true or false.
gap> "apple" in fruits;
true
gap> "banana" in fruits;
false
The in operator may as well be applied to ordinary lists. It is
however much faster to perform a membership test for sets since sets are
always sorted and a binary search can be used instead of a linear search.
New elements may be added to a set by the function AddSet which takes
the set fruits as its first argument and an element as its second
argument and adds the element to the set if it wasn't already there.
Note that the object fruits is changed.
gap> AddSet(fruits, "banana");
gap> fruits; # The banana is inserted in the right place.
[ "apple", "banana", "cherry", "plum", "strawberry" ]
gap> AddSet(fruits, "apple");
gap> fruits; # fruits has not changed.
[ "apple", "banana", "cherry", "plum", "strawberry" ]
Sets can be intersected by the function Intersection and united by the
function Union which both take two sets as their arguments and return
the intersection (union) of the two sets as a new object.
gap> breakfast:= ["tea", "apple", "egg"];
[ "tea", "apple", "egg" ]
gap> Intersection(breakfast, fruits);
[ "apple" ]
It is however not necessary for the objects collected in a set to be of
the same type. You may as well have additional integers and boolean
values for breakfast.
The arguments of the functions Intersection and Union may as well be
ordinary lists, while their result is always a set. Note that in the
preceding example at least one argument of Intersection was not a set.
The functions IntersectSet and UniteSet also form the intersection
resp. union of two sets. They will however not return the result but
change their first argument to be the result. Try them carefully.
In this section you have seen that sets are a special kind of list.
There are functions to expand sets, intersect or unite sets, and there is
the membership test with the in operator.
A more detailed description of strings is contained in chapter Strings and Characters. Sets are described in more detail in chapter Sets.
1.12 About Vectors and Matrices
A vector is a list of elements from a common field. A matrix is a list of vectors of equal length. Vectors and matrices are special kinds of lists without holes.
gap> v:= [3, 6, 2, 5/2];
[ 3, 6, 2, 5/2 ]
gap> IsVector(v);
true
Vectors may be multiplied by scalars from their field. Multiplication of vectors of equal length results in their scalar product.
gap> 2 * v;
[ 6, 12, 4, 5 ]
gap> v * 1/3;
[ 1, 2, 2/3, 5/6 ]
gap> v * v;
221/4 # the scalar product of v with itself
Note that the expression v * 1/3 is actually evaluated by first
multiplying v by 1 (which yields again v) and by then dividing by 3.
This is also an allowed scalar operation. The expression v/3 would
result in the same value.
A matrix is a list of vectors of equal length.
gap> m:= [[1, -1, 1],
> [2, 0, -1],
> [1, 1, 1]];
[ [ 1, -1, 1 ], [ 2, 0, -1 ], [ 1, 1, 1 ] ]
gap> m[2][1];
2
Syntactically a matrix is a list of lists. So the number 2 in the second
row and the first column of the matrix m is referred to as the first
element of the second element of the list m via m[2][1].
A matrix may be multiplied by scalars, vectors and other matrices. The vectors and matrices involved in such a multiplication must however have suitable dimensions.
gap> m:= [[1, 2, 3, 4],
> [5, 6, 7, 8],
> [9,10,11,12]];
[ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ]
gap> PrintArray(m);
[ [ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ] ]
gap> [1, 0, 0, 0] * m;
Error, Vector *: vectors must have the same length
gap> [1, 0, 0] * m;
[ 1, 2, 3, 4 ]
gap> m * [1, 0, 0];
Error, Vector *: vectors must have the same length
gap> m * [1, 0, 0, 0];
[ 1, 5, 9 ]
gap> m * [0, 1, 0, 0];
[ 2, 6, 10 ]
Note that multiplication of a vector with a matrix will result in a linear combination of the rows of the matrix, while multiplication of a matrix with a vector results in a linear combination of the columns of the matrix. In the latter case the vector is considered as a column vector.
Submatrices can easily be extracted and assigned using the { }{ }
operator.
gap> sm := m{ [ 1, 2 ] }{ [ 3, 4 ] };
[ [ 3, 4 ], [ 7, 8 ] ]
gap> sm{ [ 1, 2 ] }{ [2] } := [[1],[-1]];
[ [ 1 ], [ -1 ] ]
gap> sm;
[ [ 3, 1 ], [ 7, -1 ] ]
The first curly brackets contain the selection of rows, the second that of columns.
In this section you have met vectors and matrices as special lists. You have seen how to refer to elements of a matrix and how to multiply scalars, vectors, and matrices.
Fields are described in chapter Fields. The known fields in GAP are described in chapters Rationals, Cyclotomics, Gaussians, Subfields of Cyclotomic Fields and Finite Fields. Vectors and matrices are described in more detail in chapters Vectors and Matrices. Vector spaces are described in chapter Vector Spaces and further matrix related structures are described in chapters Matrix Rings and Matrix Groups.
A record provides another way to build new data structures. Like a list a record is a collection of other objects. In a record the elements are not indexed by numbers but by names (i.e., identifiers). An entry in a record is called a record component (or sometimes also record field).
gap> date:= rec(year:= 1992,
> month:= "Jan",
> day:= 13);
rec(
year := 1992,
month := "Jan",
day := 13 )
Initially a record is defined as a comma separated list of assignments to its record components. Then the value of a record component is accessible by the record name and the record component name separated by one dot as the record component selector.
gap> date.year;
1992
gap> date.time:= rec(hour:= 19, minute:= 23, second:= 12);
rec(
hour := 19,
minute := 23,
second := 12 )
gap> date;
rec(
year := 1992,
month := "Jan",
day := 13,
time := rec(
hour := 19,
minute := 23,
second := 12 ) )
Assignments to new record components are possible in the same way. The record is automatically resized to hold the new component.
Most of the complex structures that are handled by GAP are represented as records, for instance groups and character tables.
Records are objects that may be changed. An assignment to a record
component changes the original object. There are many functions in the
library that will do such assignments to a record component of one of
their arguments. The function Size for example, will compute the size
of its argument which may be a group for instance, and then store the
value in the record component size. The next call of Size for this
object will use this stored value rather than compute it again.
Lists and records are the only types of GAP objects that can be changed.
Sometimes it is interesting to know which components of a certain record
are bound. This information is available from the function RecFields
(yes, this function should be called RecComponentNames), which takes a
record as its argument and returns a list of all bound components of this
record as a list of strings.
gap> RecFields(date);
[ "year", "month", "day", "time" ]
Finally try the following examples and explain the results.
gap> r:= rec();
rec(
)
gap> r:= rec(r:= r);
rec(
r := rec(
) )
gap> r.r:= r;
rec(
r := ~ )
Now return to section About Identical Lists and find out what that section means for records.
In this section you have seen how to define and how to use records. Record objects are changed by assignments to record fields. Lists and records are the only types of objects that can be changed.
Records and functions for records are described in detail in chapter Records. More about identical records is found in Identical Records.
A range is a finite sequence of integers. This is another special kind of list. A range is described by its minimum (the first entry), its second entry and its maximum, separated by a comma resp. two dots and enclosed in brackets. In the usual case of an ascending list of consecutive integers the second entry may be omitted.
gap> [1..999999]; # a range of almost a million numbers
[ 1 .. 999999 ]
gap> [1, 2..999999]; # this is equivalent
[ 1 .. 999999 ]
gap> [1, 3..999999]; # here the step is 2
[ 1, 3 .. 999999 ]
gap> Length( last );
500000
gap> [ 999999, 999997 .. 1 ];
[ 999999, 999997 .. 1 ]
This compact printed representation of a fairly long list corresponds to
a compact internal representation. The function IsRange tests whether
an object is a range. If this is true for a list but the list is not yet
represented in the compact form of a range this will be done then.
gap> a:= [-2,-1,0,1,2,3,4,5];
[ -2, -1, 0, 1, 2, 3, 4, 5 ]
gap> IsRange(a);
true
gap> a;
[ -2 .. 5 ]
gap> a[5];
2
gap> Length(a);
8
Note that this change of representation does not change the value of
the list a. The list a still behaves in any context in the same way
as it would have in the long representation.
In this section you have seen that ascending lists of consecutive integers can be represented in a compact way as ranges.
Chapter Ranges contains a detailed description of ranges. A fundamental application of ranges is introduced in the next section.
Given a list pp of permutations we can form their product by means of a
for loop instead of writing down the product explicitly.
gap> pp:= [ (1,3,2,6,8)(4,5,9), (1,6)(2,7,8)(4,9), (1,5,7)(2,3,8,6),
> (1,8,9)(2,3,5,6,4), (1,9,8,6,3,4,7,2) ];;
gap> prod:= ();
()
gap> for p in pp do
> prod:= prod * p;
> od;
gap> prod;
(1,8,4,2,3,6,5)
First a new variable prod is initialized to the identity permutation
(). Then the loop variable p takes as its value one permutation
after the other from the list pp and is multiplied with the present
value of prod resulting in a new value which is then assigned to
prod.
The for loop has the following syntax.
for var in list do statements od;
The effect of the for loop is to execute the statements for every
element of the list. A for loop is a statement and therefore
terminated by a semicolon. The list of statements is enclosed by the
keywords do and od (reverse do). A for loop returns no value.
Therefore we had to ask explicitly for the value of prod in the
preceding example.
The for loop can loop over any kind of list, even a list with holes.
In many programming languages (and in former versions of GAP, too)
the for loop has the form
for var from first to last do statements od;
But this is merely a special case of the general for loop as defined
above where the list in the loop body is a range.
for var in [first..last] do statements od;
You can for instance loop over a range to compute the factorial 15! of the number 15 in the following way.
gap> ff:= 1;
1
gap> for i in [1..15] do
> ff:= ff * i;
> od;
gap> ff;
1307674368000
The following example introduces the while loop which has the following
syntax.
while condition do statements od;
The while loop loops over the statements as long as the condition
evaluates to true. Like the for loop the while loop is terminated
by the keyword od followed by a semicolon.
We can use our list primes to perform a very simple factorization. We
begin by initializing a list factors to the empty list. In this list
we want to collect the prime factors of the number 1333. Remember that a
list has to exist before any values can be assigned to positions of the
list. Then we will loop over the list primes and test for each prime
whether it divides the number. If it does we will divide the number by
that prime, add it to the list factors and continue.
gap> n:= 1333;
1333
gap> factors:= [];
[ ]
gap> for p in primes do
> while n mod p = 0 do
> n:= n/p;
> Add(factors, p);
> od;
> od;
gap> factors;
[ 31, 43 ]
gap> n;
1
As n now has the value 1 all prime factors of 1333 have been found and
factors contains a complete factorization of 1333. This can of course
be verified by multiplying 31 and 43.
This loop may be applied to arbitrary numbers in order to find prime
factors. But as primes is not a complete list of all primes this loop
may fail to find all prime factors of a number greater than 2000, say.
You can try to improve it in such a way that new primes are added to the
list primes if needed.
You have already seen that list objects may be changed. This holds of
course also for the list in a loop body. In most cases you have to be
careful not to change this list, but there are situations where this is
quite useful. The following example shows a quick way to determine the
primes smaller than 1000 by a sieve method. Here we will make use of the
function Unbind to delete entries from a list.
gap> primes:= [];
[ ]
gap> numbers:= [2..1000];
[ 2 .. 1000 ]
gap> for p in numbers do
> Add(primes, p);
> for n in numbers do
> if n mod p = 0 then
> Unbind(numbers[n-1]);
> fi;
> od;
> od;
The inner loop removes all entries from numbers that are divisible by
the last detected prime p. This is done by the function Unbind which
deletes the binding of the list position numbers[n-1] to the value n
so that afterwards numbers[n-1] no longer has an assigned value. The
next element encountered in numbers by the outer loop necessarily is
the next prime.
In a similar way it is possible to enlarge the list which is looped over. This yields a nice and short orbit algorithm for the action of a group, for example.
In this section you have learned how to loop over a list by the for
loop and how to loop with respect to a logical condition with the while
loop. You have seen that even the list in the loop body can be changed.
The for loop is described in For. The while loop is described in
While.
1.16 About Further List Operations
There is however a more comfortable way to compute the product of a list of numbers or permutations.
gap> Product([1..15]);
1307674368000
gap> Product(pp);
(1,8,4,2,3,6,5)
The function Product takes a list as its argument and computes the
product of the elements of the list. This is possible whenever a
multiplication of the elements of the list is defined. So Product is
just an implementation of the loop in the example above as a function.
There are other often used loops available as functions. Guess what the
function Sum does. The function List may take a list and a function
as its arguments. It will then apply the function to each element of the
list and return the corresponding list of results. A list of cubes is
produced as follows with the function cubed from About Functions.
gap> List([2..10], cubed);
[ 8, 27, 64, 125, 216, 343, 512, 729, 1000 ]
To add all these cubes we might apply the function Sum to the last
list. But we may as well give the function cubed to Sum as an
additional argument.
gap> Sum(last) = Sum([2..10], cubed);
true
The primes less than 30 can be retrieved out of the list primes from
section About Lists by the function Filtered. This function takes
the list primes and a property as its arguments and will return the
list of those elements of primes which have this property. Such a
property will be represented by a function that returns a boolean value.
In this example the property of being less than 30 can be reresented by
the function x-> x < 30 since x < 30 will evaluate to true for
values x less than 30 and to false otherwise.
gap> Filtered(primes, x-> x < 30);
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]
Another useful thing is the operator { } that forms sublists. It takes
a list of positions as its argument and will return the list of elements
from the original list corresponding to these positions.
gap> primes{ [1 .. 10] };
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]
In this section you have seen some functions which implement often used
for loops. There are functions like Product to form the product of
the elements of a list. The function List can apply a function to all
elements of a list and the functions Filtered and Sublist create
sublists of a given list.
You will find more predefined for loops in chapter Lists.
You have already seen how to use the functions of the GAP library, i.e., how to apply them to arguments. This section will show you how to write your own functions.
Writing a function that prints hello, world. on the screen is a simple
exercise in GAP.
gap> sayhello:= function()
> Print("hello, world.\n");
> end;
function ( ) ... end
This function when called will only execute the Print statement in the
second line. This will print the string hello, world. on the screen
followed by a newline character \n that causes the GAP prompt to
appear on the next line rather than immediately following the printed
characters.
The function definition has the following syntax.
function(arguments) statements end
A function definition starts with the keyword function followed by the
formal parameter list arguments enclosed in parenthesis. The formal
parameter list may be empty as in the example. Several parameters are
separated by commas. Note that there must be no semicolon behind the
closing parenthesis. The function definition is terminated by the
keyword end.
A GAP function is an expression like integers, sums and lists. It
therefore may be assigned to a variable. The terminating semicolon in
the example does not belong to the function definition but terminates the
assignment of the function to the name sayhello. Unlike in the case of
integers, sums, and lists the value of the function sayhello is echoed
in the abbreviated fashion function ( ) ... end. This shows the most
interesting part of a function: its formal parameter list (which is
empty in this example). The complete value of sayhello is returned if
you use the function Print.
gap> Print(sayhello, "\n");
function ( )
Print( "hello, world.\n" );
end
Note the additional newline character "\n" in the Print statement.
It is printed after the object sayhello to start a new line.
The newly defined function sayhello is executed by calling sayhello()
with an empty argument list.
gap> sayhello();
hello, world.
This is however not a typical example as no value is returned but only a string is printed.
A more useful function is given in the following example. We define a
function sign which shall determine the sign of a number.
gap> sign:= function(n)
> if n < 0 then
> return -1;
> elif n = 0 then
> return 0;
> else
> return 1;
> fi;
> end;
function ( n ) ... end
gap> sign(0); sign(-99); sign(11);
0
-1
1
gap> sign("abc");
1 # strings are defined to be greater than 0
This example also introduces the if statement which is used to execute
statements depending on a condition. The if statement has the
following syntax.
if condition then statements elif condition then statements else
statements fi;
There may be several elif parts. The elif part as well as the else
part of the if statement may be omitted. An if statement is no
expression and can therefore not be assigned to a variable. Furthermore
an if statement does not return a value.
Fibonacci numbers are defined recursively by f(1) = f(2) = 1 and f(n)
= f(n-1) + f(n-2). Since functions in GAP may call themselves, a
function fib that computes Fibonacci numbers can be implemented
basically by typing the above equations.
gap> fib:= function(n)
> if n in [1, 2] then
> return 1;
> else
> return fib(n-1) + fib(n-2);
> fi;
> end;
function ( n ) ... end
gap> fib(15);
610
There should be additional tests for the argument n being a positive
integer. This function fib might lead to strange results if called
with other arguments. Try to insert the tests in this example.
A function gcd that computes the greatest common divisor of two
integers by Euclid's algorithm will need a variable in addition to the
formal arguments.
gap> gcd:= function(a, b)
> local c;
> while b <> 0 do
> c:= b;
> b:= a mod b;
> a:= c;
> od;
> return c;
> end;
function ( a, b ) ... end
gap> gcd(30, 63);
3
The additional variable c is declared as a local variable in the
local statement of the function definition. The local statement, if
present, must be the first statement of a function definition. When
several local variables are declared in only one local statement they
are separated by commas.
The variable c is indeed a local variable, that is local to the
function gcd. If you try to use the value of c in the main loop you
will see that c has no assigned value unless you have already assigned
a value to the variable c in the main loop. In this case the local
nature of c in the function gcd prevents the value of the c in the
main loop from being overwritten.
We say that in a given scope an identifier identifies a unique variable.
A scope is a lexical part of a program text. There is the global scope
that encloses the entire program text, and there are local scopes that
range from the function keyword, denoting the beginning of a function
definition, to the corresponding end keyword. A local scope introduces
new variables, whose identifiers are given in the formal argument list
and the local declaration of the function. The usage of an identifier in
a program text refers to the variable in the innermost scope that has
this identifier as its name.
We will now write a function to determine the number of partitions of a positive integer. A partition of a positive integer is a descending list of numbers whose sum is the given integer. For example [4,2,1,1] is a partition of 8. The complete set of all partitions of an integer n may be divided into subsets with respect to the largest element. The number of partitions of n therefore equals the sum of the numbers of partitions of n-i with elements less than i for all possible i. More generally the number of partitions of n with elements less than m is the sum of the numbers of partitions of n-i with elements less than i for i less than m and n. This description yields the following function.
gap> nrparts:= function(n)
> local np;
> np:= function(n, m)
> local i, res;
> if n = 0 then
> return 1;
> fi;
> res:= 0;
> for i in [1..Minimum(n,m)] do
> res:= res + np(n-i, i);
> od;
> return res;
> end;
> return np(n,n);
> end;
function ( n ) ... end
We wanted to write a function that takes one argument. We solved the
problem of determining the number of partitions in terms of a recursive
procedure with two arguments. So we had to write in fact two functions.
The function nrparts that can be used to compute the number of
partitions takes indeed only one argument. The function np takes two
arguments and solves the problem in the indicated way. The only task of
the function nrparts is to call np with two equal arguments.
We made np local to nrparts. This illustrates the possibility of
having local functions in GAP. It is however not necessary to put it
there. np could as well be defined on the main level. But then the
identifier np would be bound and could not be used for other purposes.
And if it were used the essential function np would no longer be
available for nrparts.
Now have a look at the function np. It has two local variables res
and i. The variable res is used to collect the sum and i is a loop
variable. In the loop the function np calls itself again with other
arguments. It would be very disturbing if this call of np would use
the same i and res as the calling np. Since the new call of np
creates a new scope with new variables this is fortunately not the case.
The formal parameters n and m are treated like local variables.
It is however cheaper (in terms of computing time) to avoid such a recursive solution if this is possible (and it is possible in this case), because a function call is not very cheap.
In this section you have seen how to write functions in the GAP
language. You have also seen how to use the if statement. Functions
may have local variables which are declared in an initial local
statement in the function definition. Functions may call themselves.
The function syntax is described in Functions. The if statement is
described in more detail in If. More about Fibonacci numbers is found
in Fibonacci and more about partitions in Partitions.
In this section we will show some easy computations with groups. The
example uses permutation groups, but this is visible for the user only
because the output contains permutations. The functions, like Group,
Size or SylowSubgroup (for detailed information, see chapters
Domains, Groups), are the same for all kinds of groups, although the
algorithms which compute the information of course will be different in
most cases.
It is not even necessary to know more about permutations than the two facts that they are elements of permutation groups and that they are written in disjoint cycle notation (see chapter Permutations). So let's construct a permutation group:
gap> s8:= Group( (1,2), (1,2,3,4,5,6,7,8) );
Group( (1,2), (1,2,3,4,5,6,7,8) )
We formed the group generated by the permutations (1,2) and
(1,2,3,4,5,6,7,8), which is well known as the symmetric group on eight
points, and assigned it to the identifier s8. s8 contains the
alternating group on eight points which can be described in several ways,
e.g., as group of all even permutations in s8, or as its commutator
subgroup.
gap> a8:= CommutatorSubgroup( s8, s8 );
Subgroup( Group( (1,2), (1,2,3,4,5,6,7,8) ),
[ (1,3,2), (2,4,3), (2,3)(4,5), (2,4,6,5,3), (2,5,3)(4,7,6),
(2,3)(5,6,8,7) ] )
The alternating group a8 is printed as instruction to compute that
subgroup of the group s8 that is generated by the given six
permutations. This representation is much shorter than the internal
structure, and it is completely self--explanatory; one could, for
example, print such a group to a file and read it into GAP later. But
if one object occurs several times it is useful to refer to this object;
this can be settled by assigning a name to the group.
gap> s8.name:= "s8";
"s8"
gap> a8;
Subgroup( s8, [ (1,3,2), (2,4,3), (2,3)(4,5), (2,4,6,5,3),
(2,5,3)(4,7,6), (2,3)(5,6,8,7) ] )
gap> a8.name:= "a8";
"a8"
gap> a8;
a8
Whenever a group has a component name, GAP prints this name instead
of the group itself. Note that there is no link between the name and the
identifier, but it is of course useful to choose name and identifier
compatible.
gap> copya8:= Copy( a8 );
a8
We examine the group a8. Like all complex GAP structures, it is
represented as a record (see Group Records).
gap> RecFields( a8 );
[ "isDomain", "isGroup", "parent", "identity", "generators",
"operations", "isPermGroup", "1", "2", "3", "4", "5", "6",
"stabChainOptions", "stabChain", "orbit", "transversal",
"stabilizer", "name" ]
Many functions store information about the group in this group record, this avoids duplicate computations. But we are not interested in the organisation of data but in the group, e.g., some of its properties (see chapter Groups, especially Properties and Property Tests):
gap> Size( a8 ); IsAbelian( a8 ); IsPerfect( a8 );
20160
false
true
Some interesting subgroups are the Sylow p subgroups for prime divisors
p of the group order; a call of SylowSubgroup stores the required
subgroup in the group record:
gap> Set( Factors( Size( a8 ) ) );
[ 2, 3, 5, 7 ]
gap> for p in last do
> SylowSubgroup( a8, p );
> od;
gap> a8.sylowSubgroups;
[ , Subgroup( s8, [ (1,5)(7,8), (1,5)(2,6), (3,4)(7,8), (2,3)(4,6),
(1,7)(2,3)(4,6)(5,8), (1,2)(3,7)(4,8)(5,6) ] ),
Subgroup( s8, [ (3,8,7), (2,6,4)(3,7,8) ] ),,
Subgroup( s8, [ (3,7,8,6,4) ] ),,
Subgroup( s8, [ (2,8,4,5,7,3,6) ] ) ]
The record component sylowSubgroups is a list which stores at the
p--th position, if bound, the Sylow p subgroup; in this example this
means that there are holes at positions 1, 4 and 6. Note that a call of
SylowSubgroup for the cyclic group of order 65521 and for the prime
65521 would cause GAP to store the group at the end of a list of
length 65521, so there are special situations where it is possible to
bring GAP and yourselves into troubles.
We now can investigate the Sylow 2 subgroup.
gap> syl2:= last[2];;
gap> Size( syl2 );
64
gap> Normalizer( a8, syl2 );
Subgroup( s8, [ (3,4)(7,8), (2,3)(4,6), (1,2)(3,7)(4,8)(5,6) ] )
gap> last = syl2;
true
gap> Centre( syl2 );
Subgroup( s8, [ ( 1, 5)( 2, 6)( 3, 4)( 7, 8) ] )
gap> cent:= Centralizer( a8, last );
Subgroup( s8, [ ( 1, 5)( 2, 6)( 3, 4)( 7, 8), (3,4)(7,8), (3,7)(4,8),
(2,3)(4,6), (1,2)(5,6) ] )
gap> Size( cent );
192
gap> DerivedSeries( cent );
[ Subgroup( s8, [ ( 1, 5)( 2, 6)( 3, 4)( 7, 8), (3,4)(7,8),
(3,7)(4,8), (2,3)(4,6), (1,2)(5,6) ] ),
Subgroup( s8, [ ( 1, 6, 3)( 2, 4, 5), ( 1, 8, 3)( 4, 5, 7),
( 1, 7)( 2, 3)( 4, 6)( 5, 8), ( 1, 5)( 2, 6) ] ),
Subgroup( s8, [ ( 1, 3)( 2, 7)( 4, 5)( 6, 8),
( 1, 6)( 2, 5)( 3, 8)( 4, 7), ( 1, 5)( 3, 4), ( 1, 5)( 7, 8) ] )
, Subgroup( s8, [ ( 1, 5)( 2, 6)( 3, 4)( 7, 8) ] ),
Subgroup( s8, [ ] ) ]
gap> List( last, Size );
[ 192, 96, 32, 2, 1 ]
gap> low:= LowerCentralSeries( cent );
[ Subgroup( s8, [ ( 1, 5)( 2, 6)( 3, 4)( 7, 8), (3,4)(7,8),
(3,7)(4,8), (2,3)(4,6), (1,2)(5,6) ] ),
Subgroup( s8, [ ( 1, 6, 3)( 2, 4, 5), ( 1, 8, 3)( 4, 5, 7),
( 1, 7)( 2, 3)( 4, 6)( 5, 8), ( 1, 5)( 2, 6) ] ) ]
Another kind of subgroups is given by the point stabilizers.
gap> stab:= Stabilizer( a8, 1 );
Subgroup( s8, [ (2,5,6), (2,5)(3,6), (2,5,6,4,3), (2,5,3)(4,6,8),
(2,5)(3,4,7,8) ] )
gap> Size( stab );
2520
gap> Index( a8, stab );
8
We can fetch an arbitrary group element and look at its centralizer in
a8, and then get other subgroups by conjugation and intersection of
already known subgroups. Note that we form the subgroups inside a8,
but GAP regards these groups as subgroups of s8 because this is the
common ``parent'' group of all these groups and of a8 (for the idea
of parent groups, see More about Groups and Subgroups).
gap> Random( a8 );
(1,6,3,2,7)(4,5,8)
gap> Random( a8 );
(1,3,2,4,7,5,6)
gap> cent:= Centralizer( a8, (1,2)(3,4)(5,8)(6,7) );
Subgroup( s8, [ (1,2)(3,4)(5,8)(6,7), (5,6)(7,8), (5,7)(6,8),
(3,4)(6,7), (3,5)(4,8), (1,3)(2,4) ] )
gap> Size( cent );
192
gap> conj:= ConjugateSubgroup( cent, (2,3,4) );
Subgroup( s8, [ (1,3)(2,4)(5,8)(6,7), (5,6)(7,8), (5,7)(6,8),
(2,4)(6,7), (2,8)(4,5), (1,4)(2,3) ] )
gap> inter:= Intersection( cent, conj );
Subgroup( s8, [ (5,6)(7,8), (5,7)(6,8), (1,2)(3,4), (1,3)(2,4) ] )
gap> Size( inter );
16
gap> IsElementaryAbelian( inter );
true
gap> norm:= Normalizer( a8, inter );
Subgroup( s8, [ (6,7,8), (5,6,8), (3,4)(6,8), (2,3)(6,8), (1,2)(6,8),
(1,5)(2,6,3,7,4,8) ] )
gap> Size( norm );
576
Suppose we do not only look which funny things may appear in our group
but want to construct a subgroup, e.g., a group of structure
23:L3(2) in a8. One idea is to look for an appropriate 23
which is specified by the fact that all its involutions are fixed point
free, and then compute its normalizer in a8:
gap> elab:= Group( (1,2)(3,4)(5,6)(7,8), (1,3)(2,4)(5,7)(6,8),
> (1,5)(2,6)(3,7)(4,8) );;
gap> Size( elab );
8
gap> IsElementaryAbelian( elab );
true
gap> norm:= Normalizer( a8, AsSubgroup( s8, elab ) );
Subgroup( s8, [ (5,6)(7,8), (5,7)(6,8), (3,4)(7,8), (3,5)(4,6),
(2,3)(6,7), (1,2)(7,8) ] )
gap> Size( norm );
1344
Note that elab was defined as separate group, thus we had to call
AsSubgroup to achieve that it has the same parent group as a8.
Let's look at some usual misuses:
Normalizer( a8, elab );
Intuitively, it is clear that here again we wanted to compute the
normalizer of elab in a8, and in fact we would get it by this call.
However, this would be a misuse in the sense that now GAP cannot use
some clever method for the computation of the normalizer. So, for larger
groups, the computation may be very time consuming. That is the reason
why we used the the function AsSubgroup in the preceding example.
Let's have a closer look at that function.
gap> IsSubgroup( a8, AsSubgroup( a8, elab ) );
Error, must be a parent group in
AsSubgroup( a8, elab ) called from
main loop
brk> quit;
gap> IsSubgroup( a8, AsSubgroup( s8, elab ) );
true
What we tried here was not correct. Since all our computations up to now
are done inside s8 which is the parent of a8, it is easy to
understand that IsSubgroup works for two subgroups with this parent.
By the way, you should not try the operator < instead of the function
IsSubgroup. Something like
gap> elab < a8;
false
or
gap> AsSubgroup( s8, elab ) < a8;
false
will not cause an error, but the result does not tell anything about the
inclusion of one group in another; < looks at the element lists for
the two domains which means that it computes them if they are not already
stored --which is not desirable to do for large groups-- and then simply
compares the lists with respect to lexicographical order (see
Comparisons of Domains).
On the other hand, the equality operator = in fact does test the
equality of groups. Thus
gap> elab = AsSubgroup( s8, elab );
true
means that the two groups are equal in the sense that they have the same
elements. Note that they may behave differently since they have
different parent groups. In our example, it is necessary to work with
subgroups of s8:
gap> elab:= AsSubgroup( s8, elab );;
gap> elab.name:= "elab";;
If we are given the subgroup norm of order 1344 and its subgroup
elab, the factor group can be considered.
gap> f:= norm / elab;
(Subgroup( s8, [ (5,6)(7,8), (5,7)(6,8), (3,4)(7,8), (3,5)(4,6),
(2,3)(6,7), (1,2)(7,8) ] ) / elab)
gap> Size( f );
168
As the output shows, this is not a permutation group. The factor group and its elements can, however, be handled in the usual way.
gap> Random( f );
FactorGroupElement( elab, (2,8,7)(3,5,6) )
gap> Order( f, last );
3
The natural link between the group norm and its factor group f is the
natural homomorphism onto f, mapping each element of norm to its
coset modulo the kernel elab. In GAP you can construct the
homomorphism, but note that the images lie in f since they are elements
of the factor group, but the preimage of each such element is only a
coset, not a group element (for cosets, see the relevant sections in
chapter Groups, for homomorphisms see chapters Operations of Groups
and Mappings).
gap> f.name:= "f";;
gap> hom:= NaturalHomomorphism( norm, f );
NaturalHomomorphism( Subgroup( s8,
[ (5,6)(7,8), (5,7)(6,8), (3,4)(7,8), (3,5)(4,6), (2,3)(6,7),
(1,2)(7,8) ] ), (Subgroup( s8,
[ (5,6)(7,8), (5,7)(6,8), (3,4)(7,8), (3,5)(4,6), (2,3)(6,7),
(1,2)(7,8) ] ) / elab) )
gap> Kernel( hom ) = elab;
true
gap> x:= Random( norm );
(1,7,5,8,3,6,2)
gap> Image( hom, x );
FactorGroupElement( elab, (2,7,3,4,6,8,5) )
gap> coset:= PreImages( hom, last );
(elab*(2,7,3,4,6,8,5))
gap> IsCoset( coset );
true
gap> x in coset;
true
gap> coset in f;
false
The group f acts on its elements (not on the cosets) via right
multiplication, yielding the regular permutation representation of f
and thus a new permutation group, namely the linear group L3(2). A
more elaborate discussion of operations of groups can be found in section
About Operations of Groups and chapter Operations of Groups.
gap> op:= Operation( f, Elements( f ), OnRight );;
gap> IsPermGroup( op );
true
gap> Maximum( List( op.generators, LargestMovedPointPerm ) );
168
gap> IsSimple( op );
true
norm acts on the seven nontrivial elements of its normal subgroup
elab by conjugation, yielding a representation of L3(2) on seven
points. We embed this permutation group in norm and deduce that norm
is a split extension of an elementary abelian group 23 with L3(2).
gap> op:= Operation( norm, Elements( elab ), OnPoints );
Group( (5,6)(7,8), (5,7)(6,8), (3,4)(7,8), (3,5)(4,6), (2,3)(6,7),
(3,4)(5,6) )
gap> IsSubgroup( a8, AsSubgroup( s8, op ) );
true
gap> IsSubgroup( norm, AsSubgroup( s8, op ) );
true
gap> Intersection( elab, op );
Group( () )
Yet another kind of information about our a8 concerns its conjugacy
classes.
gap> ccl:= ConjugacyClasses( a8 );
[ ConjugacyClass( a8, () ), ConjugacyClass( a8, (1,3)(2,6)(4,7)(5,8) )
, ConjugacyClass( a8, (1,3)(2,8,5)(6,7) ),
ConjugacyClass( a8, (2,5,8) ), ConjugacyClass( a8, (1,3)(6,7) ),
ConjugacyClass( a8, (1,3,2,5,4,7,8) ),
ConjugacyClass( a8, (1,5,8,2,7,3,4) ),
ConjugacyClass( a8, (1,5)(2,8,7,4,3,6) ),
ConjugacyClass( a8, (2,7,3)(4,6,8) ),
ConjugacyClass( a8, (1,6)(3,8,5,4) ),
ConjugacyClass( a8, (1,3,5,2)(4,6,8,7) ),
ConjugacyClass( a8, (1,8,6,2,5) ),
ConjugacyClass( a8, (1,7,2,4,3)(5,8,6) ),
ConjugacyClass( a8, (1,2,3,7,4)(5,8,6) ) ]
gap> Length( ccl );
14
gap> reps:= List( ccl, Representative );
[ (), (1,3)(2,6)(4,7)(5,8), (1,3)(2,8,5)(6,7), (2,5,8), (1,3)(6,7),
(1,3,2,5,4,7,8), (1,5,8,2,7,3,4), (1,5)(2,8,7,4,3,6),
(2,7,3)(4,6,8), (1,6)(3,8,5,4), (1,3,5,2)(4,6,8,7), (1,8,6,2,5),
(1,7,2,4,3)(5,8,6), (1,2,3,7,4)(5,8,6) ]
gap> List( reps, r -> Order( a8, r ) );
[ 1, 2, 6, 3, 2, 7, 7, 6, 3, 4, 4, 5, 15, 15 ]
gap> List( ccl, Size );
[ 1, 105, 1680, 112, 210, 2880, 2880, 3360, 1120, 2520, 1260, 1344,
1344, 1344 ]
Note the difference between Order (which means the element order),
Size (which means the size of the conjugacy class) and Length (which
means the length of a list).
Having the conjugacy classes, we can consider class functions, i.e., maps
that are defined on the group elements, and that are constant on each
conjugacy class. One nice example is the number of fixed points; here we
use that permutations act on points via ^.
gap> nrfixedpoints:= function( perm, support )
> return Number( [ 1 .. support ], x -> x^perm = x );
> end;
function ( perm, support ) ... end
Note that we must specify the support since a permutation does not know
about the group it is an element of; e.g. the trivial permutation ()
has as many fixed points as the support denotes.
gap> permchar1:= List( reps, x -> nrfixedpoints( x, 8 ) );
[ 8, 0, 1, 5, 4, 1, 1, 0, 2, 2, 0, 3, 0, 0 ]
This is the character of the natural permutation representation of a8
(More about characters can be found in chapters Character Tables ff.).
In order to get another representation of a8, we consider another
action, namely that on the elements of a conjugacy class by conjugation;
note that this is denoted by OnPoints, too.
gap> class := First( ccl, c -> Size(c) = 112 );
ConjugacyClass( a8, (2,5,8) )
gap> op:= Operation( a8, Elements( class ), OnPoints );;
We get a permutation representation op on 112 points. It is more
useful to look for properties than at the permutations.
gap> IsPrimitive( op, [ 1 .. 112 ] );
false
gap> blocks:= Blocks( op, [ 1 .. 112 ] );
[ [ 1, 2 ], [ 6, 8 ], [ 14, 19 ], [ 17, 20 ], [ 36, 40 ], [ 32, 39 ],
[ 3, 5 ], [ 4, 7 ], [ 10, 15 ], [ 65, 70 ], [ 60, 69 ], [ 54, 63 ],
[ 55, 68 ], [ 50, 67 ], [ 13, 16 ], [ 27, 34 ], [ 22, 29 ],
[ 28, 38 ], [ 24, 37 ], [ 31, 35 ], [ 9, 12 ], [ 106, 112 ],
[ 100, 111 ], [ 11, 18 ], [ 93, 104 ], [ 23, 33 ], [ 26, 30 ],
[ 94, 110 ], [ 88, 109 ], [ 49, 62 ], [ 44, 61 ], [ 43, 56 ],
[ 53, 58 ], [ 48, 57 ], [ 45, 66 ], [ 59, 64 ], [ 87, 103 ],
[ 81, 102 ], [ 80, 96 ], [ 92, 98 ], [ 47, 52 ], [ 42, 51 ],
[ 41, 46 ], [ 82, 108 ], [ 99, 105 ], [ 21, 25 ], [ 75, 101 ],
[ 74, 95 ], [ 86, 97 ], [ 76, 107 ], [ 85, 91 ], [ 73, 89 ],
[ 72, 83 ], [ 79, 90 ], [ 78, 84 ], [ 71, 77 ] ]
gap> op2:= Operation( op, blocks, OnSets );;
gap> IsPrimitive( op2, [ 1 .. 56 ] );
true
The action of op on the given block system gave us a new representation
on 56 points which is primitive, i.e., the point stabilizer is a maximal
subgroup. We compute its preimage in the representation on eight points
using homomorphisms (which of course are monomorphisms).
gap> ophom := OperationHomomorphism( a8, op );;
gap> Kernel(ophom);
Subgroup( s8, [ ] )
gap> ophom2:= OperationHomomorphism( op, op2 );;
gap> stab:= Stabilizer( op2, 1 );;
gap> Size( stab );
360
gap> composition:= ophom * ophom2;;
gap> preim:= PreImage( composition, stab );
Subgroup( s8, [ (1,3,2), (2,4,3), (1,3)(7,8), (2,3)(4,5), (6,8,7) ] )
And this is the permutation character (with respect to the succession of
conjugacy classes in ccl):
gap> permchar2:= List( reps, x->nrfixedpoints(x^composition,56) );
[ 56, 0, 3, 11, 12, 0, 0, 0, 2, 2, 0, 1, 1, 1 ]
The normalizer of an element in the conjugacy class class is a group of
order 360, too. In fact, it is essentially the same as the maximal
gap> sgp:= Normalizer( a8,
> Subgroup( s8, [ Representative(class) ] ) );
Subgroup( s8, [ (2,5)(3,4), (1,3,4), (2,5,8), (1,3,7)(2,5,8),
(1,4,7,3,6)(2,5,8) ] )
gap> Size( sgp );
360
gap> IsConjugate( a8, sgp, preim );
true
The scalar product of permutation characters of two subgroups U, V,
say, equals the number of (U,V)--double cosets (again, see chapters
Character Tables ff. for the details). For example, the norm of the
permutation character permchar1 of degree eight is two since the action
of a8 on the cosets of a point stabilizer is at least doubly
transitive:
gap> stab:= Stabilizer( a8, 1 );;
gap> double:= DoubleCosets( a8, stab, stab );
[ DoubleCoset( Subgroup( s8, [ (3,8,7), (3,4)(7,8), (3,5,4,8,7),
(3,6,5)(4,8,7), (2,6,4,5)(7,8) ] ), (), Subgroup( s8,
[ (3,8,7), (3,4)(7,8), (3,5,4,8,7), (3,6,5)(4,8,7),
(2,6,4,5)(7,8) ] ) ),
DoubleCoset( Subgroup( s8, [ (3,8,7), (3,4)(7,8), (3,5,4,8,7),
(3,6,5)(4,8,7), (2,6,4,5)(7,8) ] ), (1,2)(7,8), Subgroup( s8,
[ (3,8,7), (3,4)(7,8), (3,5,4,8,7), (3,6,5)(4,8,7),
(2,6,4,5)(7,8) ] ) ) ]
gap> Length( double );
2
We compute the numbers of (sgp,sgp) and (sgp,stab) double
cosets.
gap> Length( DoubleCosets( a8, sgp, sgp ) );
4
gap> Length( DoubleCosets( a8, sgp, stab ) );
2
Thus both irreducible constituents of permchar1 are also constituents
of permchar2, i.e., the difference of the two permutation characters is
a proper character of a8 of norm two.
gap> permchar2 - permchar1;
[ 48, 0, 2, 6, 8, -1, -1, 0, 0, 0, 0, -2, 1, 1 ]
1.19 About Operations of Groups
One of the most important tools in group theory is the operation or action of a group on a certain set.
We say that a group G operates on a set D if we have a function that takes each pair (d,g) with d ∈ D and g ∈ G to another element dg ∈ D, which we call the image of d under g, such that didentity = d and (dg)h = dgh for each d ∈ D and g,h ∈ G.
This is equivalent to saying that an operation is a homomorphism of the group G into the full symmetric group on D. We usually call D the domain of the operation and its elements points.
In this section we will demonstrate how you can compute with operations of groups. For an example we will use the alternating group on 8 points.
gap> a8 := Group( (1,2,3), (2,3,4,5,6,7,8) );;
gap> a8.name := "a8";;
It is important to note however, that the applicability of the functions from the operation package is not restricted to permutation groups. All the functions mentioned in this section can also be used to compute with the operation of a matrix group on the vectors, etc. We only use a permutation group here because this makes the examples more compact.
The standard operation in GAP is always denoted by the caret (^)
operator. That means that when no other operation is specified (we will
see below how this can be done) all the functions from the operations
package will compute the image of a point p under an element g as
p^g. Note that this can already denote different operations,
depending on the type of points and the type of elements. For example if
the group elements are permutations it can either denote the normal
operation when the points are integers or the conjugation when the points
are permutations themselves (see Operations for Permutations). For
another example if the group elements are matrices it can either denote
the multiplication from the right when the points are vectors or again
the conjugation when the points are matrices (of the same dimension)
themselves (see Operations for Matrices). Which operations are
available through the caret operator for a particular type of group
elements is described in the chapter for this type of group elements.
gap> 2 ^ (1,2,3);
3
gap> 1 ^ a8.2;
1
gap> (2,4) ^ (1,2,3);
(3,4)
The most basic function of the operations package is the function
Orbit, which computes the orbit of a point under the operation of the
group.
gap> Orbit( a8, 2 );
[ 2, 3, 1, 4, 5, 6, 7, 8 ]
Note that the orbit is not a set, because it is not sorted. See Orbit for the definition in which order the points appear in an orbit.
We will try to find several subgroups in a8 using the operations
package. One subgroup is immediately available, namely the stabilizer of
one point. The index of the stabilizer must of course be equal to the
length of the orbit, i.e., 8.
gap> u8 := Stabilizer( a8, 1 );
Subgroup( a8, [ (2,3,4,5,6,7,8), (3,8,7) ] )
gap> Index( a8, u8 );
8
This gives us a hint how to find further subgroups. Each subgroup is the stabilizer of a point of an appropriate transitive operation (namely the operation on the cosets of that subgroup or another operation that is equivalent to this operation).
So the question is how to find other operations. The obvious thing is to
operate on pairs of points. So using the function Tuples (see
Tuples) we first generate a list of all pairs.
gap> pairs := Tuples( [1..8], 2 );
[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ],
[ 1, 7 ], [ 1, 8 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 2, 4 ],
[ 2, 5 ], [ 2, 6 ], [ 2, 7 ], [ 2, 8 ], [ 3, 1 ], [ 3, 2 ],
[ 3, 3 ], [ 3, 4 ], [ 3, 5 ], [ 3, 6 ], [ 3, 7 ], [ 3, 8 ],
[ 4, 1 ], [ 4, 2 ], [ 4, 3 ], [ 4, 4 ], [ 4, 5 ], [ 4, 6 ],
[ 4, 7 ], [ 4, 8 ], [ 5, 1 ], [ 5, 2 ], [ 5, 3 ], [ 5, 4 ],
[ 5, 5 ], [ 5, 6 ], [ 5, 7 ], [ 5, 8 ], [ 6, 1 ], [ 6, 2 ],
[ 6, 3 ], [ 6, 4 ], [ 6, 5 ], [ 6, 6 ], [ 6, 7 ], [ 6, 8 ],
[ 7, 1 ], [ 7, 2 ], [ 7, 3 ], [ 7, 4 ], [ 7, 5 ], [ 7, 6 ],
[ 7, 7 ], [ 7, 8 ], [ 8, 1 ], [ 8, 2 ], [ 8, 3 ], [ 8, 4 ],
[ 8, 5 ], [ 8, 6 ], [ 8, 7 ], [ 8, 8 ] ]
Now we would like to have a8 operate on this domain. But we cannot use
the default operation (denoted by the caret) because list ^ perm
is not defined. So we must tell the functions from the operations
package how the group elements operate on the elements of the domain. In
our example we can do this by simply passing OnPairs as optional last
argument. All functions from the operations package accept such an
optional argument that describes the operation. See Other Operations
for a list of the available nonstandard operations.
Note that those operations are in fact simply functions that take an
element of the domain and an element of the group and return the image of
the element of the domain under the group element. So to compute the
image of the pair [1,2] under the permutation (1,4,5) we can simply
write
gap> OnPairs( [1,2], (1,4,5) );
[ 4, 2 ]
As was mentioned above we have to make sure that the operation is transitive. So we check this.
gap> IsTransitive( a8, pairs, OnPairs );
false
The operation is not transitive, so we want to find out what the orbits
are. The function Orbits does that for you. It returns a list of all
the orbits.
gap> orbs := Orbits( a8, pairs, OnPairs );
[ [ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 4 ], [ 5, 5 ], [ 6, 6 ],
[ 7, 7 ], [ 8, 8 ] ],
[ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 3, 1 ], [ 3, 4 ], [ 2, 1 ],
[ 1, 4 ], [ 4, 1 ], [ 4, 5 ], [ 3, 2 ], [ 2, 4 ], [ 1, 5 ],
[ 4, 2 ], [ 5, 1 ], [ 5, 6 ], [ 4, 3 ], [ 3, 5 ], [ 2, 5 ],
[ 1, 6 ], [ 5, 3 ], [ 5, 2 ], [ 6, 1 ], [ 6, 7 ], [ 5, 4 ],
[ 4, 6 ], [ 3, 6 ], [ 2, 6 ], [ 1, 7 ], [ 6, 4 ], [ 6, 3 ],
[ 6, 2 ], [ 7, 1 ], [ 7, 8 ], [ 6, 5 ], [ 5, 7 ], [ 4, 7 ],
[ 3, 7 ], [ 2, 7 ], [ 1, 8 ], [ 7, 5 ], [ 7, 4 ], [ 7, 3 ],
[ 7, 2 ], [ 8, 1 ], [ 8, 2 ], [ 7, 6 ], [ 6, 8 ], [ 5, 8 ],
[ 4, 8 ], [ 3, 8 ], [ 2, 8 ], [ 8, 6 ], [ 8, 5 ], [ 8, 4 ],
[ 8, 3 ], [ 8, 7 ] ] ]
The operation of a8 on the first orbit is of course equivalent to the
original operation, so we ignore it and work with the second orbit.
gap> u56 := Stabilizer( a8, [1,2], OnPairs );
Subgroup( a8, [ (3,8,7), (3,6)(4,7,5,8), (6,7,8) ] )
gap> Index( a8, u56 );
56
So now we have found a second subgroup. To make the following
computations a little bit easier and more efficient we would now like to
work on the points [1..56] instead of the list of pairs. The function
Operation does what we need. It creates a new group that operates on
[1..56] in the same way that a8 operates on the second orbit.
gap> a8_56 := Operation( a8, orbs[2], OnPairs );
Group( ( 1, 2, 4)( 3, 6,10)( 5, 7,11)( 8,13,16)(12,18,17)(14,21,20)
(19,27,26)(22,31,30)(28,38,37)(32,43,42)(39,51,50)(44,45,55),
( 1, 3, 7,12,19,28,39)( 2, 5, 9,15,23,33,45)( 4, 8,14,22,32,44, 6)
(10,16,24,34,46,56,51)(11,17,25,35,47,43,55)(13,20,29,40,52,38,50)
(18,26,36,48,31,42,54)(21,30,41,53,27,37,49) )
gap> a8_56.name := "a8_56";;
We would now like to know if the subgroup u56 of index 56 that we found
is maximal or not. Again we can make use of a function from the
operations package. Namely a subgroup is maximal if the operation on the
cosets of this subgroup is primitive, i.e., if there is no partition of
the set of cosets into subsets such that the group operates setwise on
those subsets.
gap> IsPrimitive( a8_56, [1..56] );
false
Note that we must specify the domain of the operation. You might think
that in the last example IsPrimitive could use [1..56] as default
domain if no domain was given. But this is not so simple, for example
would the default domain of Group( (2,3,4) ) be [1..4] or [2..4]?
To avoid confusion, all operations package functions require that you
specify the domain of operation.
We see that a8_56 is not primitive. This means of course that the
operation of a8 on orb[2] is not primitive, because those two
operations are equivalent. So the stabilizer u56 is not maximal. Let
us try to find its supergroups. We use the function Blocks to find a
block system. The (optional) third argument in the following example
tells Blocks that we want a block system where 1 and 10 lie in one
block. There are several other block systems, which we could compute by
specifying a different pair, it just turns out that [1,10] makes the
following computation more interesting.
gap> blocks := Blocks( a8_56, [1..56], [1,10] );
[ [ 1, 10, 13, 21, 31, 43, 45 ], [ 2, 3, 16, 20, 30, 42, 55 ],
[ 4, 6, 8, 14, 22, 32, 44 ], [ 5, 7, 11, 24, 29, 41, 54 ],
[ 9, 12, 17, 18, 34, 40, 53 ], [ 15, 19, 25, 26, 27, 46, 52 ],
[ 23, 28, 35, 36, 37, 38, 56 ], [ 33, 39, 47, 48, 49, 50, 51 ] ]
The result is a list of sets, i.e., sorted lists, such that a8_56
operates on those sets. Now we would like the stabilizer of this
operation on the sets. Because we wanted to operate on the sets we have
to pass OnSets as third argument.
gap> u8_56 := Stabilizer( a8_56, blocks[1], OnSets );
Subgroup( a8_56,
[ (15,35,48)(19,28,39)(22,32,44)(23,33,52)(25,36,49)(26,37,50)
(27,38,51)(29,41,54)(30,42,55)(31,43,45)(34,40,53)(46,56,47),
( 9,25)(12,19)(14,22)(15,34)(17,26)(18,27)(20,30)(21,31)(23,48)
(24,29)(28,39)(32,44)(33,56)(35,47)(36,49)(37,50)(38,51)(40,52)
(41,54)(42,55)(43,45)(46,53), ( 5,17)( 7,12)( 8,14)( 9,24)(11,18)
(13,21)(15,25)(16,20)(23,47)(28,39)(29,34)(32,44)(33,56)(35,49)
(36,48)(37,50)(38,51)(40,54)(41,53)(42,55)(43,45)(46,52),
( 2,11)( 3, 7)( 4, 8)( 5,16)( 9,17)(10,13)(20,24)(23,47)(25,26)
(28,39)(29,30)(32,44)(33,56)(35,48)(36,50)(37,49)(38,51)(40,53)
(41,55)(42,54)(43,45)(46,52), ( 1,10)( 2, 6)( 3, 4)( 5, 7)( 8,16)
(12,17)(14,20)(19,26)(22,30)(23,47)(28,50)(32,55)(33,56)(35,48)
(36,49)(37,39)(38,51)(40,53)(41,54)(42,44)(43,45)(46,52) ] )
gap> Index( a8_56, u8_56 );
8
Now we have a problem. We have found a new subgroup, but not as a
subgroup of a8, instead it is a subgroup of a8_56. We know that
a8_56 is isomorphic to a8 (in general the result of Operation is
only isomorphic to a factor group of the original group, but in this case
it must be isomorphic to a8, because a8 is simple and has only the
full group as nontrivial factor group). But we only know that an
isomorphism exists, we do not know it.
Another function comes to our rescue. OperationHomomorphism returns
the homomorphism of a group onto the group that was constructed by
Operation. A later section in this chapter will introduce mappings and
homomorphisms in general, but for the moment we can just regard the
result of OperationHomomorphism as a black box that we can use to
transfer information from a8 to a8_56 and back.
gap> h56 := OperationHomomorphism( a8, a8_56 );
OperationHomomorphism( a8, a8_56 )
gap> u8b := PreImages( h56, u8_56 );
Subgroup( a8, [ (6,7,8), (5,6)(7,8), (4,5)(7,8), (3,4)(7,8),
(1,3)(7,8) ] )
gap> Index( a8, u8b );
8
gap> u8 = u8b;
false
So we have in fact found a new subgroup. However if we look closer we
note that u8b is not totally new. It fixes the point 2, thus it lies
in the stabilizer of 2, and because it has the same index as this
stabilizer it must in fact be the stabilizer. Thus u8b is conjugated
to u8. A nice way to check this is to check that the operation on the
8 blocks is equivalent to the original operation.
gap> IsEquivalentOperation( a8, [1..8], a8_56, blocks, OnSets );
true
Now the choice of the third argument [1,10] of Blocks becomes clear.
Had we not given that argument we would have obtained the block system
that has [1,3,7,12,19,28,39] as first block. The preimage of the
stabilizer of this set would have been u8 itself, and we would not have
been able to introduce IsEquivalentOperation. Of course we could also
use the general function IsConjugate, but we want to demonstrate
IsEquivalentOperation.
Actually there is a third block system of a8_56 that gives rise to a
third subgroup.
gap> blocks := Blocks( a8_56, [1..56], [1,6] );
[ [ 1, 6 ], [ 2, 10 ], [ 3, 4 ], [ 5, 16 ], [ 7, 8 ], [ 9, 24 ],
[ 11, 13 ], [ 12, 14 ], [ 15, 34 ], [ 17, 20 ], [ 18, 21 ],
[ 19, 22 ], [ 23, 46 ], [ 25, 29 ], [ 26, 30 ], [ 27, 31 ],
[ 28, 32 ], [ 33, 56 ], [ 35, 40 ], [ 36, 41 ], [ 37, 42 ],
[ 38, 43 ], [ 39, 44 ], [ 45, 51 ], [ 47, 52 ], [ 48, 53 ],
[ 49, 54 ], [ 50, 55 ] ]
gap> u28_56 := Stabilizer( a8_56, [1,6], OnSets );
Subgroup( a8_56,
[ ( 2,38,51)( 3,28,39)( 4,32,44)( 5,41,54)(10,43,45)(16,36,49)
(17,40,53)(20,35,48)(23,47,30)(26,46,52)(33,55,37)(42,56,50),
( 5,17,26,37,50)( 7,12,19,28,39)( 8,14,22,32,44)( 9,15,23,33,54)
(11,18,27,38,51)(13,21,31,43,45)(16,20,30,42,55)(24,34,46,56,49)
(25,35,47,41,53)(29,40,52,36,48),
( 1, 6)( 2,39,38,19,18, 7)( 3,51,28,27,12,11)( 4,45,32,31,14,13)
( 5,55,33,23,15, 9)( 8,10,44,43,22,21)(16,50,56,46,34,24)
(17,54,42,47,35,25)(20,49,37,52,40,29)(26,53,41,30,48,36) ] )
gap> u28 := PreImages( h56, u28_56 );
Subgroup( a8, [ (3,7,8), (4,5,6,7,8), (1,2)(3,8,7,6,5,4) ] )
gap> Index( a8, u28 );
28
We know that the subgroup u28 of index 28 is maximal, because we know
that a8 has no subgroups of index 2, 4, or 7. However we can also
quickly verify this by checking that a8_56 operates primitively on the
28 blocks.
gap> IsPrimitive( a8_56, blocks, OnSets );
true
There is a different way to obtain u28. Instead of operating on the 56
pairs [ [1,2], [1,3], ..., [8,7] ] we could operate on the 28 sets of
two elements from [1..8]. But suppose we make a small mistake.
gap> OrbitLength( a8, [2,1], OnSets );
Error, OnSets: must be a set
It is your responsibility to make sure that the points that you pass to
functions from the operations package are in normal form. That means
that they must be sets if you operate on sets with OnSets, they must be
lists of length 2 if you operate on pairs with OnPairs, etc. This also
applies to functions that accept a domain of operation, e.g., Operation
and IsPrimitive. All points in such a domain must be in normal form.
It is not guaranteed that a violation of this rule will signal an error,
you may obtain incorrect results.
Note that Stabilizer is not only applicable to groups like a8 but
also to their subgroups like u56. So another method to find a new
subgroup is to compute the stabilizer of another point in u56. Note
that u56 already leaves 1 and 2 fixed.
gap> u336 := Stabilizer( u56, 3 );
Subgroup( a8, [ (4,6,5), (5,6)(7,8), (6,7,8) ] )
gap> Index( a8, u336 );
336
Other functions are also applicable to subgroups. In the following we
show that u336 operates regularly on the 60 triples of [4..8] which
contain no element twice, which means that this operation is equivalent
to the operations of u336 on its 60 elements from the right. Note that
OnTuples is a generalization of OnPairs.
gap> IsRegular( u336, Orbit( u336, [4,5,6], OnTuples ), OnTuples );
true
Just as we did in the case of the operation on the pairs above, we now
construct a new permutation group that operates on [1..336] in the same
way that a8 operates on the cosets of u336. Note that the operation
of a group on the cosets is by multiplication from the right, thus we
have to specify OnRight.
gap> a8_336 := Operation( a8, Cosets( a8, u336 ), OnRight );;
gap> a8_336.name := "a8_336";;
To find subgroups above u336 we again check if the operation is
primitive.
gap> blocks := Blocks( a8_336, [1..336], [1,43] );
[ [ 1, 43, 85 ], [ 2, 102, 205 ], [ 3, 95, 165 ], [ 4, 106, 251 ],
[ 5, 117, 334 ], [ 6, 110, 294 ], [ 7, 122, 127 ], [ 8, 144, 247 ],
[ 9, 137, 207 ], [ 10, 148, 293 ], [ 11, 45, 159 ],
[ 12, 152, 336 ], [ 13, 164, 169 ], [ 14, 186, 289 ],
[ 15, 179, 249 ], [ 16, 190, 335 ], [ 17, 124, 201 ],
[ 18, 44, 194 ], [ 19, 206, 211 ], [ 20, 228, 331 ],
[ 21, 221, 291 ], [ 22, 46, 232 ], [ 23, 166, 243 ],
[ 24, 126, 236 ], [ 25, 248, 253 ], [ 26, 48, 270 ],
[ 27, 263, 333 ], [ 28, 125, 274 ], [ 29, 208, 285 ],
[ 30, 168, 278 ], [ 31, 290, 295 ], [ 32, 121, 312 ],
[ 33, 47, 305 ], [ 34, 167, 316 ], [ 35, 250, 327 ],
[ 36, 210, 320 ], [ 37, 74, 332 ], [ 38, 49, 163 ], [ 39, 81, 123 ],
[ 40, 59, 209 ], [ 41, 70, 292 ], [ 42, 66, 252 ], [ 50, 142, 230 ],
[ 51, 138, 196 ], [ 52, 146, 266 ], [ 53, 87, 131 ],
[ 54, 153, 302 ], [ 55, 160, 174 ], [ 56, 182, 268 ],
[ 57, 178, 234 ], [ 58, 189, 304 ], [ 60, 86, 199 ],
[ 61, 198, 214 ], [ 62, 225, 306 ], [ 63, 218, 269 ],
[ 64, 88, 235 ], [ 65, 162, 245 ], [ 67, 233, 254 ],
[ 68, 90, 271 ], [ 69, 261, 301 ], [ 71, 197, 288 ],
[ 72, 161, 281 ], [ 73, 265, 297 ], [ 75, 89, 307 ],
[ 76, 157, 317 ], [ 77, 229, 328 ], [ 78, 193, 324 ],
[ 79, 116, 303 ], [ 80, 91, 158 ], [ 82, 101, 195 ],
[ 83, 112, 267 ], [ 84, 108, 231 ], [ 92, 143, 237 ],
[ 93, 133, 200 ], [ 94, 150, 273 ], [ 96, 154, 309 ],
[ 97, 129, 173 ], [ 98, 184, 272 ], [ 99, 180, 238 ],
[ 100, 188, 308 ], [ 103, 202, 216 ], [ 104, 224, 310 ],
[ 105, 220, 276 ], [ 107, 128, 241 ], [ 109, 240, 256 ],
[ 111, 260, 311 ], [ 113, 204, 287 ], [ 114, 130, 277 ],
[ 115, 275, 296 ], [ 118, 132, 313 ], [ 119, 239, 330 ],
[ 120, 203, 323 ], [ 134, 185, 279 ], [ 135, 175, 242 ],
[ 136, 192, 315 ], [ 139, 171, 215 ], [ 140, 226, 314 ],
[ 141, 222, 280 ], [ 145, 244, 258 ], [ 147, 262, 318 ],
[ 149, 170, 283 ], [ 151, 282, 298 ], [ 155, 246, 329 ],
[ 156, 172, 319 ], [ 176, 227, 321 ], [ 177, 217, 284 ],
[ 181, 213, 257 ], [ 183, 264, 322 ], [ 187, 286, 300 ],
[ 191, 212, 325 ], [ 219, 259, 326 ], [ 223, 255, 299 ] ]
To find the subgroup of index 112 that belongs to this operation we could
use the same methods as before, but we actually use a different trick.
From the above we see that the subgroup is the union of u336 with its
43rd and its 85th coset. Thus we simply add a representative of the 43rd
coset to the generators of u336.
gap> u112 := Closure( u336, Representative( Cosets(a8,u336)[43] ) );
Subgroup( a8, [ (4,6,5), (5,6)(7,8), (6,7,8), (1,3,2) ] )
gap> Index( a8, u112 );
112
Above this subgroup of index 112 lies a subgroup of index 56, which is
not conjugate to u56. In fact, unlike u56 it is maximal. We obtain
this subgroup in the same way that we obtained u112, this time forcing
two points, namely 39 and 43 into the first block.
gap> blocks := Blocks( a8_336, [1..336], [1,39,43] );;
gap> Length( blocks );
56
gap> u56b := Closure( u112, Representative( Cosets(a8,u336)[39] ) );
Subgroup( a8, [ (4,6,5), (5,6)(7,8), (6,7,8), (1,3,2), (2,3)(7,8) ] )
gap> Index( a8, u56b );
56
gap> IsPrimitive( a8_336, blocks, OnSets );
true
We already mentioned in the beginning that there is another standard
operation of permutations, namely the conjugation. E.g., because no
other operation is specified in the following example OrbitLength
simply operates using the caret operator and because perm1^perm2
is defined as the conjugation of perm2 on perm1 we effectively
compute the length of the conjugacy class of (1,2)(3,4)(5,6)(7,8). (In
fact element1^element2 is always defined as the conjugation if
element1 and element2 are group elements of the same type. So the
length of a conjugacy class of any element elm in an arbitrary group
G can be computed as OrbitLength( G, elm ). In general however
this may not be a good idea, Size( ConjugacyClass( G, elm ) ) is
probably more efficient.)
gap> OrbitLength( a8, (1,2)(3,4)(5,6)(7,8) );
105
gap> orb := Orbit( a8, (1,2)(3,4)(5,6)(7,8) );;
gap> u105 := Stabilizer( a8, (1,2)(3,4)(5,6)(7,8) );
Subgroup( a8, [ (5,6)(7,8), (1,2)(3,4)(5,6)(7,8), (5,7)(6,8),
(3,4)(7,8), (3,5)(4,6), (1,3)(2,4) ] )
gap> Index( a8, u105 );
105
Of course the last stabilizer is in fact the centralizer of the element
(1,2)(3,4)(5,6)(7,8). Stabilizer notices that and computes the
stabilizer using the centralizer algorithm for permutation groups.
In the usual way we now look for the subgroups that lie above u105.
gap> blocks := Blocks( a8, orb );;
gap> Length( blocks );
15
gap> blocks[1];
[ (1,2)(3,4)(5,6)(7,8), (1,3)(2,4)(5,7)(6,8), (1,4)(2,3)(5,8)(6,7),
(1,5)(2,6)(3,7)(4,8), (1,6)(2,5)(3,8)(4,7), (1,7)(2,8)(3,5)(4,6),
(1,8)(2,7)(3,6)(4,5) ]
To find the subgroup of index 15 we again use closure. Now we must be a
little bit careful to avoid confusion. u105 is the stabilizer of
(1,2)(3,4)(5,6)(7,8). We know that there is a correspondence between
the points of the orbit and the cosets of u105. The point
(1,2)(3,4)(5,6)(7,8) corresponds to u105. To get the subgroup of
index 15 we must add to u105 an element of the coset that corresponds
to the point (1,3)(2,4)(5,7)(6,8) (or any other point in the first
block). That means that we must use an element of a8 that maps
(1,2)(3,4)(5,6)(7,8) to (1,3)(2,4)(5,7)(6,8). The important thing is
that (1,3)(2,4)(5,7)(6,8) will not do, in fact (1,3)(2,4)(5,7)(6,8)
lies in u105.
The function RepresentativeOperation does what we need. It takes a
group and two points and returns an element of the group that maps the
first point to the second. In fact it also allows you to specify the
operation as optional fourth argument as usual, but we do not need this
here. If no such element exists in the group, i.e., if the two points do
not lie in one orbit under the group, RepresentativeOperation returns
false.
gap> rep := RepresentativeOperation( a8, (1,2)(3,4)(5,6)(7,8),
> (1,3)(2,4)(5,7)(6,8) );
(2,3)(6,7)
gap> u15 := Closure( u105, rep );
Subgroup( a8, [ (5,6)(7,8), (1,2)(3,4)(5,6)(7,8), (5,7)(6,8),
(3,4)(7,8), (3,5)(4,6), (1,3)(2,4), (2,3)(6,7) ] )
gap> Index( a8, u15 );
15
u15 is of course a maximal subgroup, because a8 has no subgroups of
index 3 or 5.
There is in fact another class of subgroups of index 15 above u105 that
we get by adding (2,3)(6,8) to u105.
gap> u15b := Closure( u105, (2,3)(6,8) );
Subgroup( a8, [ (5,6)(7,8), (1,2)(3,4)(5,6)(7,8), (5,7)(6,8),
(3,4)(7,8), (3,5)(4,6), (1,3)(2,4), (2,3)(6,8) ] )
gap> Index( a8, u15b );
15
We now show that u15 and u15b are not conjugate. We showed that u8
and u8b are conjugate by showing that the operations on the cosets
where equivalent. We could show that u15 and u15b are not conjugate
by showing that the operations on their cosets are not equivalent.
Instead we simply call RepresentativeOperation again.
gap> RepresentativeOperation( a8, u15, u15b );
false
RepresentativeOperation tells us that there is no element g in a8
such that u15^g = u15b. Because ^ also denotes the conjugation
of subgroups this tells us that u15 and u15b are not conjugate. Note
that this operation should only be used rarely, because it is usually not
very efficient. The test in this case is however reasonable efficient,
and is in fact the one employed by IsConjugate (see IsConjugate).
This concludes our example. In this section we demonstrated some
functions from the operations package. There is a whole class of
functions that we did not mention, namely those that take a single
element instead of a whole group as first argument, e.g., Cycle and
Permutation. All functions are described in the chapter Operations of
Groups.
1.20 About Finitely Presented Groups and Presentations
In this section we will show you the investigation of a Coxeter group that is given by its presentation. You will see that finitely presented groups and presentations are different kinds of objects in GAP. While finitely presented groups can never be changed after they have been created as factor groups of free groups, presentations allow manipulations of the generators and relators by Tietze transformations. The investigation of the example will involve methods and algorithms like Todd-Coxeter, Reidemeister-Schreier, Nilpotent Quotient, and Tietze transformations.
We start by defining a Coxeter group c on five generators as a factor
group of the free group of rank 5, whose generators we already call
c.1, ..., c.5.
gap> c := FreeGroup( 5, "c" );;
gap> r := List( c.generators, x -> x^2 );;
gap> Append( r, [ (c.1*c.2)^3, (c.1*c.3)^2, (c.1*c.4)^3,
> (c.1*c.5)^3, (c.2*c.3)^3, (c.2*c.4)^2, (c.2*c.5)^3,
> (c.3*c.4)^3, (c.3*c.5)^3, (c.4*c.5)^3,
> (c.1*c.2*c.5*c.2)^2, (c.3*c.4*c.5*c.4)^2 ] );
gap> c := c / r;
Group( c.1, c.2, c.3, c.4, c.5 )
If we call the function Size for this group GAP will invoke the
Todd-Coxeter method, which however will fail to get a result going up to
the default limit of defining 64000 cosets:
gap> Size(c);
Error, the coset enumeration has defined more than 64000 cosets:
type 'return;' if you want to continue with a new limit of
128000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit,
in
AugmentedCosetTableMtc( G, H, -1, "_x" ) called from
D.operations.Size( D ) called from
Size( c ) called from
main loop
brk> quit;
In fact, as we shall see later, our finitely presented group is infinite and hence we would get the same answer also with larger limits. So we next look for subgroups of small index, in our case limiting the index to four.
gap> lis := LowIndexSubgroupsFpGroup( c, TrivialSubgroup(c), 4 );;
gap> Length(lis);
10
The LowIndexSubgroupsFpGroup function in fact determines generators for
the subgroups, written in terms of the generators of the given group. We
can find the index of these subgroups by the function Index, and the
permutation representation on the cosets of these subgroups by the
function OperationCosetsFpGroup, which use a Todd-Coxeter method. The
size of the image of this permutation representation is found using
Size which in this case uses a Schreier-Sims method for permutation
groups.
gap> List(lis, x -> [Index(c,x),Size(OperationCosetsFpGroup(c,x))]);
[ [ 1, 1 ], [ 4, 24 ], [ 4, 24 ], [ 4, 24 ], [ 4, 24 ], [ 4, 24 ],
[ 4, 24 ], [ 4, 24 ], [ 3, 6 ], [ 2, 2 ] ]
We next determine the commutator factor groups of the kernels of these
permutation representations. Note that here the difference of finitely
presented groups and presentations has to be observed: We first
determine the kernel of the permutation representation by the function
Core as a subgroup of c, then a presentation of this subgroup using
PresentationSubgroup, which has to be converted into a finitely
presented group of its own right using FpGroupPresentation, before its
commutator factor group and the abelian invariants can be found using
integer matrix diagonalisation of the relators matrix by an elementary
divisor algorithm. The conversion is necessary because Core computes a
subgroup given by words in the generators of c but
CommutatorFactorGroup needs a parent group given by generators and
relators.
gap> List( lis, x -> AbelianInvariants( CommutatorFactorGroup(
> FpGroupPresentation( PresentationSubgroup( c, Core(c,x) ) ) ) ) );
[ [ 2 ], [ 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 0, 0, 0, 0, 0, 0 ], [ 2, 2, 2, 2, 2, 2 ], [ 3 ] ]
More clearly arranged, this is
[ [ 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 0, 0, 0, 0, 0, 0 ],
[ 2, 2, 2, 2, 2, 2 ],
[ 3 ] ]
Note that there is another function AbelianInvariantsSubgroupFpGroup
which we could have used to obtain this list which will do an abelianized
Reduced Reidemeister-Schreier. This function is much faster because it
does not compute a complete presentation for the core.
The output obtained shows that the third last of the kernels has a free
abelian commutator factor group of rank 6. We turn our attention to this
kernel which we call n, while we call the associated presentation pr.
gap> lis[8];
Subgroup( Group( c.1, c.2, c.3, c.4, c.5 ),
[ c.1, c.2, c.3*c.2*c.5^-1, c.3*c.4*c.3^-1, c.4*c.1*c.5^-1 ] )
gap> pr := PresentationSubgroup( c, Core( c, lis[8] ) );
<< presentation with 22 gens and 41 rels of total length 156 >>
gap> n := FpGroupPresentation(pr);;
We first determine p-factor groups for primes 2, 3, 5, and 7.
gap> InfoPQ1:= Ignore;;
gap> List( [2,3,5,7], p -> PrimeQuotient(n,p,5).dimensions );
[ [ 6, 10, 18, 30, 54 ], [ 6, 10, 18, 30, 54 ], [ 6, 10, 18, 30, 54 ],
[ 6, 10, 18, 30, 54 ] ]
Observing that the ranks of the lower exponent-p central series are the same for these primes we suspect that the lower central series may have free abelian factors. To investigate this we have to call the package "nq".
gap> RequirePackage("nq");
gap> NilpotentQuotient( n, 5 );
[ [ 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0 ] ]
gap> List( last, Length );
[ 6, 4, 8, 12, 24 ]
The ranks of the factors except the first are divisible by four, and we compare them with the corresponding ranks of a free group on two generators.
gap> f2 := FreeGroup(2);
Group( f.1, f.2 )
gap> PrimeQuotient( f2, 2, 5 ).dimensions;
[ 2, 3, 5, 8, 14 ]
gap> NilpotentQuotient( f2, 5 );
[ [ 0, 0 ], [ 0 ], [ 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0 ] ]
gap> List( last, Length );
[ 2, 1, 2, 3, 6 ]
The result suggests a close relation of our group to the direct product
of four free groups of rank two. In order to study this we want a simple
presentation for our kernel n and obtain this by repeated use of Tietze
transformations, using first the default simplification function TzGoGo
and later specific introduction of new generators that are obtained as
product of two of the existing ones using the function TzSubstitute.
(Of course, this latter sequence of Tietze transformations that we
display here has only been found after some trial and error.)
gap> pr := PresentationSubgroup( c, Core( c, lis[8] ) );
<< presentation with 22 gens and 41 rels of total length 156 >>
gap> TzGoGo(pr);
#I there are 6 generators and 14 relators of total length 74
gap> TzGoGo(pr);
#I there are 6 generators and 13 relators of total length 66
gap> TzGoGo(pr);
gap> TzPrintPairs(pr);
#I 1. 3 occurrences of _x6 * _x11^-1
#I 2. 3 occurrences of _x3 * _x15
#I 3. 2 occurrences of _x11^-1 * _x15^-1
#I 4. 2 occurrences of _x6 * _x15
#I 5. 2 occurrences of _x6^-1 * _x15^-1
#I 6. 2 occurrences of _x4 * _x15
#I 7. 2 occurrences of _x4^-1 * _x15^-1
#I 8. 2 occurrences of _x4^-1 * _x11
#I 9. 2 occurrences of _x4 * _x6
#I 10. 2 occurrences of _x3^-1 * _x11
gap> TzSubstitute(pr,10,2);
#I substituting new generator _x26 defined by _x3^-1*_x11
#I eliminating _x11 = _x3*_x26
#I there are 6 generators and 13 relators of total length 70
gap> TzGoGo(pr);
#I there are 6 generators and 12 relators of total length 62
#I there are 6 generators and 12 relators of total length 60
gap> TzGoGo(pr);
gap> TzSubstitute(pr,9,2);
#I substituting new generator _x27 defined by _x1^-1*_x15
#I eliminating _x15 = _x27*_x1
#I there are 6 generators and 12 relators of total length 64
gap> TzGoGo(pr);
#I there are 6 generators and 11 relators of total length 56
gap> TzGoGo(pr);
gap> p2 := Copy(pr);
<< presentation with 6 gens and 11 rels of total length 56 >>
gap> TzPrint(p2);
#I generators: [ _x1, _x3, _x4, _x6, _x26, _x27 ]
#I relators:
#I 1. 4 [ -6, -1, 6, 1 ]
#I 2. 4 [ 4, 6, -4, -6 ]
#I 3. 4 [ 5, 4, -5, -4 ]
#I 4. 4 [ 4, -2, -4, 2 ]
#I 5. 4 [ -3, 2, 3, -2 ]
#I 6. 4 [ -3, -1, 3, 1 ]
#I 7. 6 [ -4, 3, 4, 6, -3, -6 ]
#I 8. 6 [ -1, -6, -2, 6, 1, 2 ]
#I 9. 6 [ -6, -2, -5, 6, 2, 5 ]
#I 10. 6 [ 2, 5, 1, -5, -2, -1 ]
#I 11. 8 [ -1, -6, -5, 3, 6, 1, 5, -3 ]
gap> TzPrintPairs(p2);
#I 1. 5 occurrences of _x1^-1 * _x27^-1
#I 2. 3 occurrences of _x6 * _x27
#I 3. 3 occurrences of _x3 * _x26
#I 4. 2 occurrences of _x3 * _x27
#I 5. 2 occurrences of _x1 * _x4
#I 6. 2 occurrences of _x1 * _x3
#I 7. 1 occurrence of _x26 * _x27
#I 8. 1 occurrence of _x26 * _x27^-1
#I 9. 1 occurrence of _x26^-1 * _x27
#I 10. 1 occurrence of _x6 * _x27^-1
gap> TzSubstitute(p2,1,2);
#I substituting new generator _x28 defined by _x1^-1*_x27^-1
#I eliminating _x27 = _x1^-1*_x28^-1
#I there are 6 generators and 11 relators of total length 58
gap> TzGoGo(p2);
#I there are 6 generators and 11 relators of total length 54
gap> TzGoGo(p2);
gap> p3 := Copy(p2);
<< presentation with 6 gens and 11 rels of total length 54 >>
gap> TzSubstitute(p3,3,2);
#I substituting new generator _x29 defined by _x3*_x26
#I eliminating _x26 = _x3^-1*_x29
gap> TzGoGo(p3);
#I there are 6 generators and 11 relators of total length 52
gap> TzGoGo(p3);
gap> TzPrint(p3);
#I generators: [ _x1, _x3, _x4, _x6, _x28, _x29 ]
#I relators:
#I 1. 4 [ 6, 4, -6, -4 ]
#I 2. 4 [ 1, -6, -1, 6 ]
#I 3. 4 [ -5, -1, 5, 1 ]
#I 4. 4 [ -2, -5, 2, 5 ]
#I 5. 4 [ 4, -2, -4, 2 ]
#I 6. 4 [ -3, 2, 3, -2 ]
#I 7. 4 [ -3, -1, 3, 1 ]
#I 8. 6 [ -2, 5, -6, 2, -5, 6 ]
#I 9. 6 [ 4, -1, -5, -4, 5, 1 ]
#I 10. 6 [ -6, 3, -5, 6, -3, 5 ]
#I 11. 6 [ 3, -5, 4, -3, -4, 5 ]
The resulting presentation could further be simplified by Tietze
transformations using TzSubstitute and TzGoGo until one reaches
finally a presentation on 6 generators with 11 relators, 9 of which are
commutators of the generators. Working by hand from these, the kernel
can be identified as a particular subgroup of the direct product of four
copies of the free group on two generators.
In this section we will show you some basic computations with fields. GAP supports at present the following fields. The rationals, cyclotomic extensions of rationals and their subfields (which we will refer to as number fields in the following), and finite fields.
Let us first take a look at the infinite fields mentioned above. While
the set of rational numbers is a predefined domain in GAP to which you
may refer by its identifier Rationals, cyclotomic fields are
constructed by using the function CyclotomicField, which may be
abbreviated as CF.
gap> IsField( Rationals );
true
gap> Size( Rationals );
"infinity"
gap> f := CyclotomicField( 8 );
CF(8)
gap> IsSubset( f, Rationals );
true
The integer argument n of the function call to CF specifies that the
cyclotomic field containing all n-th roots of unity should be returned.
Cyclotomic fields are constructed as extensions of the Rationals by
primitive roots of unity. Thus a primitive n-th root of unity is always
an element of CF(n), where n is a natural number. In GAP, one may
construct a primitive n-th root of unity by calling E(n).
gap> (E(8) + E(8)^3)^2;
-2
gap> E(8) in f;
true
For every field extension you can compute the Galois group, i.e., the group of automorphisms that leave the subfield fixed. For an example, cyclotomic fields are an extension of the rationals, so you can compute their Galois group over the rationals.
gap> Galf := GaloisGroup( f );
Group( NFAutomorphism( CF(8) , 7 ), NFAutomorphism( CF(8) , 5 ) )
gap> Size( Galf );
4
The above cyclotomic field is a small example where the Galois group is not cyclic.
gap> IsCyclic( Galf );
false
gap> IsAbelian( Galf );
true
gap> AbelianInvariants( Galf );
[ 2, 2 ]
This shows us that the 8th cyclotomic field has a Galois group which is isomorphic to group V4.
The elements of the Galois group are GAP automorphisms, so they may be applied to the elements of the field in the same way as all mappings are usually applied to objects in GAP.
gap> g := Galf.generators[1];
NFAutomorphism( CF(8) , 7 )
gap> E(8) ^ g;
-E(8)^3
There are two functions, Norm and Trace, which compute the norm and
the trace of elements of the field, respectively. The norm and the trace
of an element a are defined to be the product and the sum of the images
of a under the Galois group. You should usually specify the field as a
first argument. This argument is however optional. If you omit a
default field will be used. For a cyclotomic a this is the smallest
cyclotomic field that contains a (note that this is not the smallest
field that contains a, which may be a number field that is not a
cyclotomic field).
gap> orb := List( Elements( Galf ), x -> E(8) ^ x );
[ E(8), E(8)^3, -E(8), -E(8)^3 ]
gap> Sum( orb ) = Trace( f, E(8) );
true
gap> Product( orb ) = Norm( f, E(8) );
true
gap> Trace( f, 1 );
4
The basic way to construct a finite field is to use the function
GaloisField which may be abbreviated, as usual in algebra, as GF.
Thus
gap> k := GF( 3, 4 );
GF(3^4)
or
gap> k := GaloisField( 81 );
GF(3^4)
will assign the finite field of order 34 to the variable k.
In fact, what GF does is to set up a record which contains all
necessary information, telling that it represents a finite field of
degree 4 over its prime field with 3 elements. Of course, all arguments
to GF others than those which represent a prime power are rejected --
for obvious reasons.
Some of the more important entries of the field record are zero, one
and root, which hold the corresponding elements of the field. All
elements of a finite field are represented as a certain power of an
appropriate primitive root, which is written as Z(q). As can be seen
below the smallest possible primitive root is used.
gap> k.one + k.root + k.root^10 - k.zero;
Z(3^4)^52
gap> k.root;
Z(3^4)
gap> k.root ^ 20;
Z(3^2)^2
gap> k.one;
Z(3)^0
Note that of course elements from fields of different characteristic cannot be combined in operations.
gap> Z(3^2) * k.root + k.zero + Z(3^8);
Z(3^8)^6534
gap> Z(2) * k.one;
Error, Finite field *: operands must have the same characteristic
In this example we tried to multiply a primitive root of the field with
two elements with the identity element of the field k. As the
characteristic of k equals 3, there is no way to perform the
multiplication. The first statement of the example shows, that if all
the elements of the expression belong to fields of the same
characteristic, the result will be computed.
As soon as a primitive root is demanded, GAP internally sets up all relevant data structures that are necessary to compute in the corresponding finite field. Each finite field is constructed as a splitting field of a Conway polynomial. These polynomials, as a set, have special properties that make it easy to embed smaller fields in larger ones and to convert the representation of the elements when doing so. All Conway polynomials for fields up to an order of 65536 have been computed and installed in the GAP kernel.
But now look at the following example.
gap> Z(3^3) * Z(3^4);
Error, Finite field *: smallest common superfield to large
Although both factors are elements of fields of characteristic 3, the product can not be evaluated by GAP. The reason for this is very easy to explain: In order to compute the product, GAP has to find a field in which both of the factors lie. Here in our example the smallest field containing Z(33) and Z(34) is GF(312), the field with 531441 elements. As we have mentioned above that the size of finite fields in GAP is limited at present by 65536 we now see that there is no chance to set up the internal data structures for the common field to perform the computation.
As before with cyclotomic fields, the Galois group of a finite field and the norm and trace of its elements may be computed. The calling conventions are the same as for cyclotomic fields.
gap> Galk := GaloisGroup( k );
Group( FrobeniusAutomorphism( GF(3^4) ) )
gap> Size( Galk );
4
gap> IsCyclic( Galk );
true
gap> Norm( k, k.root ^ 20 );
Z(3)^0
gap> Trace( k, k.root ^ 20 );
0*Z(3)
So far, in our examples, we were always interested in the Galois group of
a field extension k over its prime field. In fact it often will occur
that, given a subfield l of k the Galois group of k over l is
desired. In GAP it is possible to change the structure of a field by
using the / operator. So typing
gap> l := GF(3^2);
GF(3^2)
gap> IsSubset( k, l );
true
gap> k / l;
GF(3^4)/GF(3^2)
changes the representation of k from a field extension of degree 4 over GF(3) to a field given as an extension of degree 2 over GF(32). The actual elements of the fields are still the same, only the structure of the field has changed.
gap> k = k / l;
true
gap> Galkl := GaloisGroup( k / l );
Group( FrobeniusAutomorphism( GF(3^4)/GF(3^2) )^2 )
gap> Size( Galkl );
2
Of course, all the relevant functions behave in a different way when they
refer to k / l instead of k
gap> Norm( k / l, k.root ^ 20 );
Z(3)
gap> Trace( k / l, k.root ^ 20 );
Z(3^2)^6
This feature, to change the structure of the field without changing the underlying set of elements, is also available for cyclotomic fields, which we have seen at the beginning of this chapter.
gap> g := CyclotomicField( 4 );
GaussianRationals
gap> IsSubset( f, g );
true
gap> f / g;
CF(8)/GaussianRationals
gap> Galfg := GaloisGroup( f / g );
Group( NFAutomorphism( CF(8)/GaussianRationals , 5 ) )
gap> Size( Galfg );
2
The examples should have shown that, although the structure of finite fields and cyclotomic fields is rather different, there is a similar interface to them in GAP, which makes it easy to write programs that deal with both types of fields in the same way.
This section intends to show you the things you could do with matrix groups in GAP. In principle all the set theoretic functions mentioned in chapter Domains and all group functions mentioned in chapter Groups can be applied to matrix groups. However, you should note that at present only very few functions can work efficiently with matrix groups. Especially infinite matrix groups (over the rationals or cyclotomic fields) can not be dealt with at all.
Matrix groups are created in the same way as the other types of groups,
by using the function Group. Of course, in this case the arguments
have to be invertable matrices over a field.
gap> m1 := [ [ Z(3)^0, Z(3)^0, Z(3) ],
> [ Z(3), 0*Z(3), Z(3) ],
> [ 0*Z(3), Z(3), 0*Z(3) ] ];;
gap> m2 := [ [ Z(3), Z(3), Z(3)^0 ],
> [ Z(3), 0*Z(3), Z(3) ],
> [ Z(3)^0, 0*Z(3), Z(3) ] ];;
gap> m := Group( m1, m2 );
Group( [ [ Z(3)^0, Z(3)^0, Z(3) ], [ Z(3), 0*Z(3), Z(3) ],
[ 0*Z(3), Z(3), 0*Z(3) ] ],
[ [ Z(3), Z(3), Z(3)^0 ], [ Z(3), 0*Z(3), Z(3) ],
[ Z(3)^0, 0*Z(3), Z(3) ] ] )
As usual for groups, the matrix group that we have constructed is represented by a record with several entries. For matrix groups, there is one additional entry which holds the field over which the matrix group is written.
gap> m.field;
GF(3)
Note that you do not specify the field when you construct the group.
Group automatically takes the smallest field over which all its
arguments can be written.
At this point there is the question what special functions are available
for matrix groups. The size of our group, for example, may be computed
using the function Size.
gap> Size( m );
864
If we now compute the size of the corresponding general linear group
gap> (3^3 - 3^0) * (3^3 - 3^1) * (3^3 - 3^2);
11232
we see that we have constructed a proper subgroup of index 13 of GL(3,3).
Let us now set up a subgroup of m, which is generated by the matrix
m2.
gap> n := Subgroup( m, [ m2 ] );
Subgroup( Group( [ [ Z(3)^0, Z(3)^0, Z(3) ], [ Z(3), 0*Z(3), Z(3) ],
[ 0*Z(3), Z(3), 0*Z(3) ] ],
[ [ Z(3), Z(3), Z(3)^0 ], [ Z(3), 0*Z(3), Z(3) ],
[ Z(3)^0, 0*Z(3), Z(3) ] ] ),
[ [ [ Z(3), Z(3), Z(3)^0 ], [ Z(3), 0*Z(3), Z(3) ],
[ Z(3)^0, 0*Z(3), Z(3) ] ] ] )
gap> Size( n );
6
And to round up this example we now compute the centralizer of this
subgroup in m.
gap> c := Centralizer( m, n );
Subgroup( Group( [ [ Z(3)^0, Z(3)^0, Z(3) ], [ Z(3), 0*Z(3), Z(3) ],
[ 0*Z(3), Z(3), 0*Z(3) ] ],
[ [ Z(3), Z(3), Z(3)^0 ], [ Z(3), 0*Z(3), Z(3) ],
[ Z(3)^0, 0*Z(3), Z(3) ] ] ),
[ [ [ Z(3), Z(3), Z(3)^0 ], [ Z(3), 0*Z(3), Z(3) ],
[ Z(3)^0, 0*Z(3), Z(3) ] ],
[ [ Z(3), 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3), 0*Z(3) ],
[ 0*Z(3), 0*Z(3), Z(3) ] ] ] )
gap> Size( c );
12
In this section you have seen that matrix groups are constructed in the same way that all groups are constructed. You have also been warned that only very few functions can work efficiently with matrix groups. See chapter Matrix Groups to read more about matrix groups.
1.23 About Domains and Categories
Domain is GAP's name for structured sets. We already saw examples
of domains in the previous sections. For example, the groups s8 and
a8 in sections About Groups and About Operations of Groups are
domains. Likewise the fields in section About Fields are domains.
Categories are sets of domains. For example, the set of all groups
forms a category, as does the set of all fields.
In those sections we treated the domains as black boxes. They were
constructed by special functions such as Group and GaloisField, and
they could be passed as arguments to other functions such as Size and
Orbits.
In this section we will also treat domains as black boxes. We will describe how domains are created in general and what functions are applicable to all domains. Next we will show how domains with the same structure are grouped into categories and will give an overview of the categories that are available. Then we will discuss how the organization of the GAP library around the concept of domains and categories is reflected in this manual. In a later section we will open the black boxes and give an overview of the mechanism that makes all this work (see About the Implementation of Domains).
The first thing you must know is how you can obtain domains. You have basically three possibilities. You can use the domains that are predefined in the library, you can create new domains with domain constructors, and you can use the domains returned by many library functions. We will now discuss those three possibilities in turn.
The GAP library predefines some domains. That means that there is a global variable whose value is this domain. The following example shows some of the more important predefined domains.
gap> Integers;
Integers # the ring of all integers
gap> Size( Integers );
"infinity"
gap> GaussianRationals;
GaussianRationals # the field of all Gaussian
gap> (1/2+E(4)) in GaussianRationals;
true # E(4) is GAP's name for the complex root of -1
gap> Permutations;
Permutations # the domain of all permutations
Note that GAP prints those domains using the name of the global variable.
You can create new domains using domain constructors such as Group,
Field, etc. A domain constructor is a function that takes a certain
number of arguments and returns the domain described by those arguments.
For example, Group takes an arbitrary number of group elements (of the
same type) and returns the group generated by those elements.
gap> gf16 := GaloisField( 16 );
GF(2^4) # the finite field with 16 elements
gap> Intersection( gf16, GaloisField( 64 ) );
GF(2^2)
gap> a5 := Group( (1,2,3), (3,4,5) );
Group( (1,2,3), (3,4,5) ) # the alternating group on 5 points
gap> Size( a5 );
60
Again GAP prints those domains using more or less the expression that you entered to obtain the domain.
As with groups (see About Groups) a name can be assigned to an
arbitrary domain D with the assignment D.name := string;, and
GAP will use this name from then on in the output.
Many functions in the GAP library return domains. In the last example
you already saw that Intersection returned a finite field domain.
Below are more examples.
gap> GaloisGroup( gf16 );
Group( FrobeniusAutomorphism( GF(2^4) ) )
gap> SylowSubgroup( a5, 2 );
Subgroup( Group( (1,2,3), (3,4,5) ), [ (2,4)(3,5), (2,3)(4,5) ] )
The distinction between domain constructors and functions that return domains is a little bit arbitrary. It is also not important for the understanding of what follows. If you are nevertheless interested, here are the principal differences. A constructor performs no computation, while a function performs a more or less complicated computation. A constructor creates the representation of the domain, while a function relies on a constructor to create the domain. A constructor knows the dirty details of the domain's representation, while a function may be independent of the domain's representation. A constructor may appear as printed representation of a domain, while a function usually does not.
After showing how domains are created, we will now discuss what you can
do with domains. You can assign a domain to a variable, put a domain
into a list or into a record, pass a domain as argument to a function,
and return a domain as result of a function. In this regard there is no
difference between an integer value such as 17 and a domain such as
Group( (1,2,3), (3,4,5) ). Of course many functions will signal an
error when you call them with domains as arguments. For example, Gcd
does not accept two groups as arguments, because they lie in no Euclidean
ring.
There are some functions that accept domains of any type as their arguments. Those functions are called the set theoretic functions. The full list of set theoretic functions is given in chapter Domains.
Above we already used one of those functions, namely Size. If you look
back you will see that we applied Size to the domain Integers, which
is a ring, and the domain a5, which is a group. Remember that a domain
was a structured set. The size of the domain is the number of elements
in the set. Size returns this number or the string "infinity" if
the domain is infinite. Below are more examples.
gap> Size( GaussianRationals );
"infinity" # this string is returned for infinite domains
gap> Size( SylowSubgroup( a5, 2 ) );
4
IsFinite( D ) returns true if the domain D is finite and false
otherwise. You could also test if a domain is finite using Size( D )
< "infinity" (GAP evaluates n < "infinity" to true for
any number n). IsFinite is more efficient. For example, if D is a
permutation group, IsFinite( D ) can immediately return true, while
Size( D ) may take quite a while to compute the size of D.
The other function that you already saw is Intersection. Above we
computed the intersection of the field with 16 elements and the field
with 64 elements. The following example is similar.
gap> Intersection( a5, Group( (1,2), (1,2,3,4) ) );
Group( (2,3,4), (1,2)(3,4) ) # alternating group on 4 points
In general Intersection tries to return a domain. In general this is
not possible however. Remember that a domain is a structured set. If
the two domain arguments have different structure the intersection may
not have any structure at all. In this case Intersection returns the
result as a proper set, i.e., as a sorted list without holes and
duplicates. The following example shows such a case. ConjugacyClass
returns the conjugacy class of (1,2,3,4,5) in the alternating group on
6 points as a domain. If we intersect this class with the symmetric
group on 5 points we obtain a proper set of 12 permutations, which is
only one half of the conjugacy class of 5 cycles in s5.
gap> a6 := Group( (1,2,3), (2,3,4,5,6) );
Group( (1,2,3), (2,3,4,5,6) )
gap> class := ConjugacyClass( a6, (1,2,3,4,5) );
ConjugacyClass( Group( (1,2,3), (2,3,4,5,6) ), (1,2,3,4,5) )
gap> Size( class );
72
gap> s5 := Group( (1,2), (2,3,4,5) );
Group( (1,2), (2,3,4,5) )
gap> Intersection( class, s5 );
[ (1,2,3,4,5), (1,2,4,5,3), (1,2,5,3,4), (1,3,5,4,2), (1,3,2,5,4),
(1,3,4,2,5), (1,4,3,5,2), (1,4,5,2,3), (1,4,2,3,5), (1,5,4,3,2),
(1,5,2,4,3), (1,5,3,2,4) ]
You can intersect arbitrary domains as the following example shows.
gap> Intersection( Integers, a5 );
[ ] # the empty set
Note that we optimized Intersection for typical cases, e.g., computing
the intersection of two permutation groups, etc. The above computation
is done with a very simple--minded method, all elements of a5 are
listed (with Elements, described below), and for each element
Intersection tests whether it lies in Integers (with in, described
below). So the same computation with the alternating group on 10 points
instead of a5 will probably exhaust your patience.
Just as Intersection returns a proper set occasionally, it also accepts
proper sets as arguments. Intersection also takes an arbitrary number
of arguments. And finally it also accepts a list of domains or sets to
intersect as single argument.
gap> Intersection( a5, [ (1,2), (1,2,3), (1,2,3,4), (1,2,3,4,5) ] );
[ (1,2,3), (1,2,3,4,5) ]
gap> Intersection( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] );
[ ]
gap> Intersection( [ [1,2,4], [2,3,4], [1,3,4] ] );
[ 4 ]
The function Union is the obvious counterpart of Intersection. Note
that Union usually does not return a domain. This is because the
union of two domains, even of the same type, is usually not again a
domain of that type. For example, the union of two subgroups is a
subgroup if and only if one of the subgroups is a subset of the other.
Of course this is exactly the reason why Union is less important than
Intersection in algebra.
Because domains are structured sets there ought to be a membership test
that tests whether an object lies in this domain or not. This is not
implemented by a function, instead the operator in is used. elm in
D returns true if the element elm lies in the domain D and
false otherwise. We already used the in operator above when we
tested whether 1/2 + E(4) lies in the domain of Gaussian integers.
gap> (1,2,3) in a5;
true
gap> (1,2) in a5;
false
gap> (1,2,3,4,5,6,7) in a5;
false
gap> 17 in a5;
false # of course an integer does not lie in a permutation group
gap> a5 in a5;
false
As you can see in the last example, in only implements the membership
test. It does not allow you to test whether a domain is a subset of
another domain. For such tests the function IsSubset is available.
gap> IsSubset( a5, a5 );
true
gap> IsSubset( a5, Group( (1,2,3) ) );
true
gap> IsSubset( Group( (1,2,3) ), a5 );
false
In the above example you can see that IsSubset tests whether the second
argument is a subset of the first argument. As a general rule GAP
library functions take as first arguments those arguments that are in
some sense larger or more structured.
Suppose that you want to loop over all elements of a domain. For
example, suppose that you want to compute the set of element orders of
elements in the group a5. To use the for loop you need a list of
elements in the domain D, because for var in D do statements od
will not work. The function Elements does exactly that. It takes a
domain D and returns the proper set of elements of D.
gap> Elements( Group( (1,2,3), (2,3,4) ) );
[ (), (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) ]
gap> ords := [];;
gap> for elm in Elements( a5 ) do
> Add( ords, Order( a5, elm ) );
> od;
gap> Set( ords );
[ 1, 2, 3, 5 ]
gap> Set( List( Elements( a5 ), elm -> Order( a5, elm ) ) );
[ 1, 2, 3, 5 ] # an easier way to compute the set of orders
Of course, if you apply Elements to an infinite domain, Elements will
signal an error. It is also not a good idea to apply Elements to very
large domains because the list of elements will take much space and
computing this large list will probably exhaust your patience.
gap> Elements( GaussianIntegers );
Error, the ring must be finite to compute its elements in
D.operations.Elements( D ) called from
Elements( GaussianIntegers ) called from
main loop
brk> quit;
There are a few more set theoretic functions. See chapter Domains for a complete list.
All the set theoretic functions treat the domains as if they had no structure. Now a domain is a structured set (excuse us for repeating this again and again, but it is really important to get this across). If the functions ignore the structure than they are effectively viewing a domain only as the set of elements.
In fact all set theoretic functions also accept proper sets, i.e., sorted
lists without holes and duplicates as arguments (we already mentioned
this for Intersection). Also set theoretic functions may occasionally
return proper sets instead of domains as result.
This equivalence of a domain and its set of elements is particularly
important for the definition of equality of domains. Two domains D and
E are equal (in the sense that D = E evaluates to true) if and
only if the set of elements of D is equal to the set of elements of E
(as returned by Elements( D ) and Elements( E )). As a special
case either of the operands of = may also be a proper set, and the
value is true if this set is equal to the set of elements of the
domain.
gap> a4 := Group( (1,2,3), (2,3,4) );
Group( (1,2,3), (2,3,4) )
gap> elms := Elements( a4 );
[ (), (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) ]
gap> elms = a4;
true
However the following example shows that this does not imply that all functions return the same answer for two domains (or a domain and a proper set) that are equal. This is because those function may take the structure into account.
gap> IsGroup( a4 );
true
gap> IsGroup( elms );
false
gap> Intersection( a4, Group( (1,2), (1,2,3) ) );
Group( (1,2,3) )
gap> Intersection( elms, Group( (1,2), (1,2,3) ) );
[ (), (1,2,3), (1,3,2) ] # this is not a group
gap> last = last2;
true # but it is equal to the above result
gap> Centre( a4 );
Subgroup( Group( (1,2,3), (2,3,4) ), [ ] )
gap> Centre( elms );
Error, must be a record in
Centre( elms ) called from
main loop
brk> quit;
Generally three things may happen if you have two domains D and E
that are equal but have different structure (or a domain D and a set
E that are equal). First a function that tests whether a domain has a
certain structure may return true for D and false for E. Second
a function may return a domain for D and a proper set for E. Third a
function may work for D and fail for E, because it requires the
structure.
A slightly more complex example for the second case is the following.
gap> v4 := Subgroup( a4, [ (1,2)(3,4), (1,3)(2,4) ] );
Subgroup( Group( (1,2,3), (2,3,4) ), [ (1,2)(3,4), (1,3)(2,4) ] )
gap> v4.name := "v4";;
gap> rc := v4 * (1,2,3);
(v4*(2,4,3))
gap> lc := (1,2,3) * v4;
((1,2,3)*v4)
gap> rc = lc;
true
gap> rc * (1,3,2);
(v4*())
gap> lc * (1,3,2);
[ (1,3)(2,4), (), (1,2)(3,4), (1,4)(2,3) ]
gap> last = last2;
false
The two domains rc and lc (yes, cosets are domains too) are equal,
because they have the same set of elements. However if we multiply both
with (1,3,2) we obtain the trivial right coset for rc and a list for
lc. The result for lc is not a proper set, because it is not
sorted, therefore = evaluates to false. (For the curious. The
multiplication of a left coset with an element from the right will
generally not yield another coset, i.e., nothing that can easily be
represented as a domain. Thus to multiply lc with (1,3,2) GAP
first converts lc to the set of its elements with Elements. But the
definition of multiplication requires that a list l multiplied by an
element e yields a new list n such that each element n[i] in
the new list is the product of the element l[i] at the same
position of the operand list l with e.)
Note that the above definition only defines what the result of the equality comparison of two domains D and E should be. It does not prescribe that this comparison is actually performed by listing all elements of D and E. For example, if D and E are groups, it is sufficient to check that all generators of D lie in E and that all generators of E lie in D. If GAP would really compute the whole set of elements, the following test could not be performed on any computer.
gap> Group( (1,2), (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) )
> = Group( (17,18), (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) );
true
If we could only apply the set theoretic functions to domains, domains
would be of little use. Luckily this is not so. We already saw that we
could apply GaloisGroup to the finite field with 16 elements, and
SylowSubgroup to the group a5. But those functions are not
applicable to all domains. The argument of GaloisGroup must be a
field, and the argument of SylowSubgroup must be a group.
A category is a set of domains. So we say that the argument of
GaloisGroup must be an element of the category of fields, and the
argument of SylowSubgroup must be an element of the category of groups.
The most important categories are rings, fields, groups, and
vector spaces. Which category a domain belongs to determines which
functions are applicable to this domain and its elements. We want to
emphasize the each domain belongs to one and only one category. This
is necessary because domains in different categories have, sometimes
incompatible, representations.
Note that the categories only exist conceptually. That means that there
is no GAP object for the categories, e.g., there is no object
Groups. For each category there exists a function that tests whether a
domain is an element of this category.
gap> IsRing( gf16 );
false
gap> IsField( gf16 );
true
gap> IsGroup( gf16 );
false
gap> IsVectorSpace( gf16 );
false
Note that of course mathematically the field gf16 is also a ring and a
vector space. However in GAP a domain can only belong to one
category. So a domain is conceptually a set of elements with one
structure, e.g., a field structure. That the same set of elements may
also support a different structure, e.g., a ring or vector space
structure, can not be represented by this domain. So you need a
different domain to represent this different structure. (We are planning
to add functions that changes the structure of a domain, e.g. AsRing(
field ) should return a new domain with the same elements as field
but with a ring structure.)
Domains may have certain properties. For example a ring may be
commutative and a group may be nilpotent. Whether a domain has a certain
property Property can be tested with the function IsProperty.
gap> IsCommutativeRing( GaussianIntegers );
true
gap> IsNilpotent( a5 );
false
There are also similar functions that test whether a domain (especially a
group) is represented in a certain way. For example IsPermGroup tests
whether a group is represented as a permutation group.
gap> IsPermGroup( a5 );
true
gap> IsPermGroup( a4 / v4 );
false # a4 / v4 is represented as a generic factor group
There is a slight difference between a function such as IsNilpotent and
a function such as IsPermGroup. The former tests properties of an
abstract group and its outcome is independent of the representation of
that group. The latter tests whether a group is given in a certain
representation.
This (rather philosophical) issue is further complicated by the fact that
sometimes representations and properties are not independent. This is
especially subtle with IsSolvable (see IsSolvable) and IsAgGroup
(see IsAgGroup). IsSolvable tests whether a group G is solvable.
IsAgGroup tests whether a group G is represented as a finite
polycyclic group, i.e., by a finite presentation that allows to
efficiently compute canonical normal forms of elements (see Finite
Polycyclic Groups). Of course every finite polycyclic group is
solvable, so IsAgGroup( G ) implies IsSolvable( G ). On the
other hand IsSolvable( G ) does not imply IsAgGroup( G ),
because, even though each solvable group can be represented as a finite
polycyclic group, it need not, e.g., it could also be represented as a
permutation group.
The organization of the manual follows the structure of domains and categories.
After the description of the programming language and the environment chapter Domains describes the domains and the functions applicable to all domains.
Next come the chapters that describe the categories rings, fields, groups, and vector spaces.
The remaining chapters describe GAP's data--types and the domains one can make with those elements of those data-types. The order of those chapters roughly follows the order of the categories. The data--types whose elements form rings and fields come first (e.g., integers and finite fields), followed by those whose elements form groups (e.g., permutations), and so on. The data--types whose elements support little or no algebraic structure come last (e.g., booleans). In some cases there may be two chapters for one data--type, one describing the elements and the other describing the domains made with those elements (e.g., permutations and permutation groups).
The GAP manual not only describes what you can do, it also gives some hints how GAP performs its computations. However, it can be tricky to find those hints. The index of this manual can help you.
Suppose that you want to intersect two permutation groups. If you read
the section that describes the function Intersection (see
Intersection) you will see that the last paragraph describes the
default method used by Intersection. Such a last paragraph that
describes the default method is rather typical. In this case it says
that Intersection computes the proper set of elements of both domains
and intersect them. It also says that this method is often overlaid
with a more efficient one. You wonder whether this is the case for
permutation groups. How can you find out? Well you look in the index
under Intersection. There you will find a reference Intersection, for
permutation groups to section Set Functions for Permutation Groups
(see Set Functions for Permutation Groups). This section tells you
that Intersection uses a backtrack for permutation groups (and cites a
book where you can find a description of the backtrack).
Let us now suppose that you intersect two factor groups. There is no
reference in the index for Intersection, for factor groups. But there
is a reference for Intersection, for groups to the section Set
Functions for Groups (see Set Functions for Groups). Since this is
the next best thing, look there. This section further directs you to the
section Intersection for Groups (see Intersection for Groups). This
section finally tells you that Intersection computes the intersection
of two groups G and H as the stabilizer in G of the trivial coset
of H under the operation of G on the right cosets of H.
In this section we introduced domains and categories. You have learned that a domain is a structured set, and that domains are either predefined, created by domain constructors, or returned by library functions. You have seen most functions that are applicable to all domains. Those functions generally ignore the structure and treat a domain as the set of its elements. You have learned that categories are sets of domains, and that the category a domain belongs to determines which functions are applicable to this domain.
More information about domains can be found in chapter Domains. Chapters Rings, Fields, Groups, and Vector Spaces define the categories known to GAP. The section About the Implementation of Domains opens that black boxes and shows how all this works.
1.24 About Mappings and Homomorphisms
A mapping is an object which maps each element of its source to a value in its range. Source and range can be arbitrary sets of elements. But in most applications the source and range are structured sets and the mapping, in such applications called homomorphism, is compatible with this structure.
In the last sections you have already encountered examples of homomorphisms, namely natural homomorphisms of groups onto their factor groups and operation homomorphisms of groups into symmetric groups.
Finite fields also bear a structure and homomorphisms between fields are always bijections. The Galois group of a finite field is generated by the Frobenius automorphism. It is very easy to construct.
gap> f := FrobeniusAutomorphism( GF(81) );
FrobeniusAutomorphism( GF(3^4) )
gap> Image( f, Z(3^4) );
Z(3^4)^3
gap> A := Group( f );
Group( FrobeniusAutomorphism( GF(3^4) ) )
gap> Size( A );
4
gap> IsCyclic( A );
true
gap> Order( Mappings, f );
4
gap> Kernel( f );
[ 0*Z(3) ]
For finite fields and cyclotomic fields the function GaloisGroup is an
easy way to construct the Galois group.
gap> GaloisGroup( GF(81) );
Group( FrobeniusAutomorphism( GF(3^4) ) )
gap> Size( last );
4
gap> GaloisGroup( CyclotomicField( 18 ) );
Group( NFAutomorphism( CF(9) , 2 ) )
gap> Size( last );
6
Not all group homomorphisms are bijections of course, natural homomorphisms do have a kernel in most cases and operation homomorphisms need neither be surjective nor injective.
gap> s4 := Group( (1,2,3,4), (1,2) );
Group( (1,2,3,4), (1,2) )
gap> s4.name := "s4";;
gap> v4 := Subgroup( s4, [ (1,2)(3,4), (1,3)(2,4) ] );
Subgroup( s4, [ (1,2)(3,4), (1,3)(2,4) ] )
gap> v4.name := "v4";;
gap> s3 := s4 / v4;
(s4 / v4)
gap> f := NaturalHomomorphism( s4, s3 );
NaturalHomomorphism( s4, (s4 / v4) )
gap> IsHomomorphism( f );
true
gap> IsEpimorphism( f );
true
gap> Image( f );
(s4 / v4)
gap> IsMonomorphism( f );
false
gap> Kernel( f );
v4
The image of a group homomorphism is always one element of the range but
the preimage can be a coset. In order to get one representative of this
coset you can use the function PreImagesRepresentative.
gap> Image( f, (1,2,3,4) );
FactorGroupElement( v4, (2,4) )
gap> PreImages( f, s3.generators[1] );
(v4*(2,4))
gap> PreImagesRepresentative( f, s3.generators[1] );
(2,4)
But even if the homomorphism is a monomorphism but not surjective you can
use the function PreImagesRepresentative in order to get the preimage
of an element of the range.
gap> A := Z(3) * [ [ 0, 1 ], [ 1, 0 ] ];;
gap> B := Z(3) * [ [ 0, 1 ], [ -1, 0 ] ];;
gap> G := Group( A, B );
Group( [ [ 0*Z(3), Z(3) ], [ Z(3), 0*Z(3) ] ],
[ [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ] ] )
gap> Size( G );
8
gap> G.name := "G";;
gap> d8 := Operation( G, Orbit( G, Z(3)*[1,0] ) );
Group( (1,2)(3,4), (1,2,3,4) )
gap> e := OperationHomomorphism( Subgroup( G, [B] ), d8 );
OperationHomomorphism( Subgroup( G,
[ [ [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ] ] ] ), Group( (1,2)(3,4),
(1,2,3,4) ) )
gap> Kernel( e );
Subgroup( G, [ ] )
gap> IsSurjective( e );
false
gap> PreImages( e, (1,3)(2,4) );
(Subgroup( G, [ ] )*[ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ])
gap> PreImage( e, (1,3)(2,4) );
Error, must be a bijection, not an arbitrary mapping in
bij.operations.PreImageElm( bij, img ) called from
PreImage( e, (1,3)(2,4) ) called from
main loop
brk> quit;
gap> PreImagesRepresentative( e, (1,3)(2,4) );
[ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ]
Only bijections allow PreImage in order to get the preimage of an
element of the range.
gap> Operation( G, Orbit( G, Z(3)*[1,0] ) );
Group( (1,2)(3,4), (1,2,3,4) )
gap> d := OperationHomomorphism( G, last );
OperationHomomorphism( G, Group( (1,2)(3,4), (1,2,3,4) ) )
gap> PreImage( d, (1,3)(2,4) );
[ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ]
Both PreImage and PreImages can also be applied to sets. They return
the complete preimage.
gap> PreImages( d, Group( (1,2)(3,4), (1,3)(2,4) ) );
Subgroup( G, [ [ [ 0*Z(3), Z(3) ], [ Z(3), 0*Z(3) ] ],
[ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ] ] )
gap> Size( last );
4
gap> f := NaturalHomomorphism( s4, s3 );
NaturalHomomorphism( s4, (s4 / v4) )
gap> PreImages( f, s3 );
Subgroup( s4, [ (1,2)(3,4), (1,3)(2,4), (2,4), (3,4) ] )
gap> Size( last );
24
Another way to construct a group automorphism is to use elements in the normalizer of a subgroup and construct the induced automorphism. A special case is the inner automorphism induced by an element of a group, a more general case is a surjective homomorphism induced by arbitrary elements of the parent group.
gap> d12 := Group((1,2,3,4,5,6),(2,6)(3,5));; d12.name := "d12";;
gap> i1 := InnerAutomorphism( d12, (1,2,3,4,5,6) );
InnerAutomorphism( d12, (1,2,3,4,5,6) )
gap> Image( i1, (2,6)(3,5) );
(1,3)(4,6)
gap> IsAutomorphism( i1 );
true
Mappings can also be multiplied, provided that the range of the first
mapping is a subgroup of the source of the second mapping. The
multiplication is of course defined as the composition. Note that, in
line with the fact that mappings operate from the right, Image( map1
* map2, elm ) is defined as Image( map2, Image( map1, elm )
).
gap> i2 := InnerAutomorphism( d12, (2,6)(3,5) );
InnerAutomorphism( d12, (2,6)(3,5) )
gap> i1 * i2;
InnerAutomorphism( d12, (1,6)(2,5)(3,4) )
gap> Image( last, (2,6)(3,5) );
(1,5)(2,4)
Mappings can also be inverted, provided that they are bijections.
gap> i1 ^ -1;
InnerAutomorphism( d12, (1,6,5,4,3,2) )
gap> Image( last, (2,6)(3,5) );
(1,5)(2,4)
Whenever you have a set of bijective mappings on a finite set (or domain)
you can construct the group generated by those mappings. So in the
following example we create the group of inner automorphisms of d12.
gap> autd12 := Group( i1, i2 );
Group( InnerAutomorphism( d12,
(1,2,3,4,5,6) ), InnerAutomorphism( d12, (2,6)(3,5) ) )
gap> Size( autd12 );
6
gap> Index( d12, Centre( d12 ) );
6
Note that the computation with such automorphism groups in their present implementation is not very efficient. For example to compute the size of such an automorphism group all elements are computed. Thus work with such automorphism groups should be restricted to very small examples.
The function ConjugationGroupHomomorphism is a generalization of
InnerAutomorphism. It accepts a source and a range and an element that
conjugates the source into the range. Source and range must lie in a
common parent group, and the conjugating element must also lie in this
parent group.
gap> c2 := Subgroup( d12, [ (2,6)(3,5) ] );
Subgroup( d12, [ (2,6)(3,5) ] )
gap> v4 := Subgroup( d12, [ (1,2)(3,6)(4,5), (1,4)(2,5)(3,6) ] );
Subgroup( d12, [ (1,2)(3,6)(4,5), (1,4)(2,5)(3,6) ] )
gap> x := ConjugationGroupHomomorphism( c2, v4, (1,3,5)(2,4,6) );
ConjugationGroupHomomorphism( Subgroup( d12,
[ (2,6)(3,5) ] ), Subgroup( d12, [ (1,2)(3,6)(4,5), (1,4)(2,5)(3,6)
] ), (1,3,5)(2,4,6) )
gap> IsSurjective( x );
false
gap> Image( x );
Subgroup( d12, [ (1,5)(2,4) ] )
But how can we construct homomorphisms which are not induced by elements of the parent group? The most general way to construct a group homomorphism is to define the source, range and the images of the generators under the homomorphism in mind.
gap> c := GroupHomomorphismByImages( G, s4, [A,B], [(1,2),(3,4)] );
GroupHomomorphismByImages( G, s4,
[ [ [ 0*Z(3), Z(3) ], [ Z(3), 0*Z(3) ] ],
[ [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ] ] ], [ (1,2), (3,4) ] )
gap> Kernel( c );
Subgroup( G, [ [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ] ] )
gap> Image( c );
Subgroup( s4, [ (1,2), (3,4) ] )
gap> IsHomomorphism( c );
true
gap> Image( c, A );
(1,2)
gap> PreImages( c, (1,2) );
(Subgroup( G, [ [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ] ] )*
[ [ 0*Z(3), Z(3) ], [ Z(3), 0*Z(3) ] ])
Note that it is possible to construct a general mapping this way that is
not a homomorphism, because GroupHomomorphismByImages does not check if
the given images fulfill the relations of the generators.
gap> b := GroupHomomorphismByImages( G, s4, [A,B], [(1,2,3),(3,4)] );
GroupHomomorphismByImages( G, s4,
[ [ [ 0*Z(3), Z(3) ], [ Z(3), 0*Z(3) ] ],
[ [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ] ] ], [ (1,2,3), (3,4) ] )
gap> IsHomomorphism( b );
false
gap> Images( b, A );
(Subgroup( s4, [ (1,3,2), (2,3,4), (1,3,4), (1,4)(2,3), (1,4,2)
] )*())
The result is a multi valued mapping, i.e., one that maps each element
of its source to a set of elements in its range. The set of images of
A under b is defined as follows. Take all the words of two letters
w( x, y ) such that w( A, B ) = A, e.g., x and x y x y x. Then
the set of images is the set of elements that you get by inserting the
images of A and B in those words, i.e., w( (1,2,3), (3,4) ), e.g.,
(1,2,3) and (1,4,2). One can show that the set of images of the
identity under a multi valued mapping such as b is a subgroup and that
the set of images of other elements are cosets of this subgroup.
\def\colon\char58
This section contains some examples of the use of GAP in character theory. First a few very simple commands for handling character tables are introduced, and afterwards we will construct the character tables of (A5x 3)\!:\!2 and of A6.22.
GAP has a large library of character tables, so let us look at one of these tables, e.g., the table of the Mathieu group M11:
gap> m11:= CharTable( "M11" );
CharTable( "M11" )
Character tables contain a lot of information. This is not printed in full length since the internal structure is not easy to read. The next statement shows a more comfortable output format.
gap> DisplayCharTable( m11 );
M11
2 4 4 1 3 . 1 3 3 . .
3 2 1 2 . . 1 . . . .
5 1 . . . 1 . . . . .
11 1 . . . . . . . 1 1
1a 2a 3a 4a 5a 6a 8a 8b 11a 11b
2P 1a 1a 3a 2a 5a 3a 4a 4a 11b 11a
3P 1a 2a 1a 4a 5a 2a 8a 8b 11a 11b
5P 1a 2a 3a 4a 1a 6a 8b 8a 11a 11b
11P 1a 2a 3a 4a 5a 6a 8a 8b 1a 1a
X.1 1 1 1 1 1 1 1 1 1 1
X.2 10 2 1 2 . -1 . . -1 -1
X.3 10 -2 1 . . 1 A -A -1 -1
X.4 10 -2 1 . . 1 -A A -1 -1
X.5 11 3 2 -1 1 . -1 -1 . .
X.6 16 . -2 . 1 . . . B /B
X.7 16 . -2 . 1 . . . /B B
X.8 44 4 -1 . -1 1 . . . .
X.9 45 -3 . 1 . . -1 -1 1 1
X.10 55 -1 1 -1 . -1 1 1 . .
A = E(8)+E(8)^3
= ER(-2) = i2
B = E(11)+E(11)^3+E(11)^4+E(11)^5+E(11)^9
= (-1+ER(-11))/2 = b11
We are not too much interested in the internal structure of this
character table (see Character Table Records); but of course we can
access all information about the centralizer orders (first four lines),
element orders (next line), power maps for the prime divisors of the
group order (next four lines), irreducible characters (lines parametrized
by X.1 ... X.10) and irrational character values (last four
lines), see DisplayCharTable for a detailed description of the format
of the displayed table. E.g., the irreducible characters are a list with
name m11.irreducibles, and each character is a list of cyclotomic
integers (see chapter Cyclotomics). There are various ways to describe
the irrationalities; e.g., the square root of -2 can be entered as
E(8) + E(8)^3 or ER(-2), the famous ATLAS of Finite
Groups CCN85 denotes it as i2.
gap> m11.irreducibles[3];
[ 10, -2, 1, 0, 0, 1, E(8)+E(8)^3, -E(8)-E(8)^3, -1, -1 ]
We can for instance form tensor products of this character with all irreducibles, and compute the decomposition into irreducibles.
gap> tens:= Tensored( [ last ], m11.irreducibles );;
gap> MatScalarProducts( m11, m11.irreducibles, tens );
[ [ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 ],
[ 0, 0, 0, 0, 1, 0, 0, 1, 1, 0 ], [ 1, 0, 0, 0, 0, 0, 0, 1, 0, 1 ],
[ 0, 0, 0, 1, 0, 0, 0, 0, 1, 1 ], [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ],
[ 0, 0, 0, 0, 0, 1, 0, 1, 1, 1 ], [ 0, 0, 1, 1, 0, 1, 1, 2, 3, 3 ],
[ 0, 1, 0, 1, 1, 1, 1, 3, 2, 3 ], [ 0, 1, 1, 0, 1, 1, 1, 3, 3, 4 ] ]
The decomposition means for example that the third character in the list
tens is the sum of the irreducible characters at positions 5, 8 and 9.
gap> tens[3];
[ 100, 4, 1, 0, 0, 1, -2, -2, 1, 1 ]
gap> tens[3] = Sum( Sublist( m11.irreducibles, [ 5, 8, 9 ] ) );
true
Or we can compute symmetrizations, e.g., the characters χ2+, defined by χ2+(g) = 1/2 ( χ2(g) + χ(g2) ), for all irreducibles.
gap> sym:= SymmetricParts( m11, m11.irreducibles, 2 );;
gap> MatScalarProducts( m11, m11.irreducibles, sym );
[ [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 1, 1, 0, 0, 0, 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 ],
[ 1, 1, 0, 0, 1, 0, 0, 1, 0, 0 ], [ 0, 1, 0, 0, 1, 0, 1, 1, 0, 1 ],
[ 0, 1, 0, 0, 1, 1, 0, 1, 0, 1 ], [ 1, 3, 0, 0, 3, 2, 2, 8, 4, 6 ],
[ 1, 2, 0, 0, 3, 2, 2, 8, 4, 7 ],
[ 1, 3, 1, 1, 4, 3, 3, 11, 7, 10 ] ]
gap> sym[2];
[ 55, 7, 1, 3, 0, 1, 1, 1, 0, 0 ]
gap> sym[2] = Sum( Sublist( m11.irreducibles, [ 1, 2, 8 ] ) );
true
If the subgroup fusion into a supergroup is known, characters can be induced to this group, e.g., to obtain the permutation character of the action of M12 on the cosets of M11.
gap> m12:= CharTable( "M12" );;
gap> permchar:= Induced( m11, m12, [ m11.irreducibles[1] ] );
[ [ 12, 0, 4, 3, 0, 0, 4, 2, 0, 1, 0, 2, 0, 1, 1 ] ]
gap> MatScalarProducts( m12, m12.irreducibles, last );
[ [ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ]
gap> DisplayCharTable( m12, rec( chars:= permchar ) );
M12
2 6 4 6 1 2 5 5 1 2 1 3 3 1 . .
3 3 1 1 3 2 . . . 1 1 . . . . .
5 1 1 . . . . . 1 . . . . 1 . .
11 1 . . . . . . . . . . . . 1 1
1a 2a 2b 3a 3b 4a 4b 5a 6a 6b 8a 8b 10a 11a 11b
2P 1a 1a 1a 3a 3b 2b 2b 5a 3b 3a 4a 4b 5a 11b 11a
3P 1a 2a 2b 1a 1a 4a 4b 5a 2a 2b 8a 8b 10a 11a 11b
5P 1a 2a 2b 3a 3b 4a 4b 1a 6a 6b 8a 8b 2a 11a 11b
11P 1a 2a 2b 3a 3b 4a 4b 5a 6a 6b 8a 8b 10a 1a 1a
Y.1 12 . 4 3 . . 4 2 . 1 . 2 . 1 1
It should be emphasized that the heart of character theory is dealing
with lists. Characters are lists, and also the maps which occur are
represented as lists. Note that the multiplication of group elements is
not available, so we neither have homomorphisms. All we can talk of are
class functions, and the lists are regarded as such functions, being the
lists of images with respect to a fixed order of conjugacy classes.
Therefore we do not write chi( cl ) or cl^chi for the value of the
character chi on the class cl, but chi[i] where i is the position
of the class cl.
Since the data structures are so basic, most calculations involve compositions of maps; for example, the embedding of a subgroup in a group is described by the so--called subgroup fusion which is a class function that maps each class c of the subgroup to that class of the group that contains c. Consider the symmetric group S5 ≅ A5.2 as subgroup of M11. (Do not worry about the names that are used to get library tables, see CharTable for an overview.)
gap> s5:= CharTable( "A5.2" );;
gap> map:= GetFusionMap( s5, m11 );
[ 1, 2, 3, 5, 2, 4, 6 ]
The subgroup fusion is already stored on the table. We see that class 1
of s5 is mapped to class 1 of m11 (which means that the identity of
S5 maps to the identity of M11), classes 2 and 5 of s5 both map
to class 2 of m11 (which means that all involutions of S5 are
conjugate in M11), and so on.
The restriction of a character of m11 to s5 is just the composition
of this character with the subgroup fusion map. Viewing this map as list
one would call this composition an indirection.
gap> chi:= m11.irreducibles[3];
[ 10, -2, 1, 0, 0, 1, E(8)+E(8)^3, -E(8)-E(8)^3, -1, -1 ]
gap> rest:= List( map, x -> chi[x] );
[ 10, -2, 1, 0, -2, 0, 1 ]
This looks very easy, and many GAP functions in character theory do such simple calculations. But note that it is not always obvious that a list is regarded as a map, where preimages and/or images refer to positions of certain conjugacy classes.
gap> alt:= s5.irreducibles[2];
[ 1, 1, 1, 1, -1, -1, -1 ]
gap> kernel:= KernelChar( last );
[ 1, 2, 3, 4 ]
The kernel of a character is represented as the list of (positions of)
classes lying in the kernel. We know that the kernel of the alternating
character alt of s5 is the alternating group A5. The order of the
kernel can be computed as sum of the lengths of the contained classes
from the character table, using that the classlengths are stored in the
classes component of the table.
gap> s5.classes;
[ 1, 15, 20, 24, 10, 30, 20 ]
gap> last{ kernel };
[ 1, 15, 20, 24 ]
gap> Sum( last );
60
We chose those classlengths of s5 that belong to the S5--classes
contained in the alternating group. The same thing is done in the
following command, reflecting the view of the kernel as map.
gap> List( kernel, x -> s5.classes[x] );
[ 1, 15, 20, 24 ]
gap> Sum( kernel, x -> s5.classes[x] );
60
This small example shows how the functions List and Sum can be used.
These functions as well as Filtered were introduced in About Further
List Operations, and we will make heavy use of them; in many cases such
a command might look very strange, but it is just the translation of a
(hardly less complicated) mathematical formula to character theory.
And now let us construct some small character tables!
\setlength\unitlength0.1cm
beg-minipage[t]70mm
The group G = (A5x 3)\!:\!2 is a maximal subgroup of the
alternating group A8; G extends to S5x S3 in S8. We
want to construct the character table of G.
First the tables of the subgroup A5x 3 and the supergroup
S5x S3 are constructed; the tables of the factors of each direct
product are again got from the table library using admissible names, see
CharTable for this.
end-minipage beg-picture(0,0)
\put(10,-37){\beginpicture(50,45)
\put(25,5){\circle1}
\put(15,15){\circle1}
\put(25,25){\circle1}
\put(25,30){\circle1}
\put(25,35){\circle1}
\put(35,15){\circle1}
\put(10,20){\circle1}
\put(40,20){\circle1}
\put(20,30){\circle1}
\put(30,30){\circle1}
\put(7,20){\makebox(0,0)S5}
\put(12,15){\makebox(0,0)A5}
\put(43,20){\makebox(0,0)S3}
\put(38,15){\makebox(0,0)3}
\put(27,30){\makebox(0,0)G}
\put(25,37){\makebox(0,0)S5x S3}
\put(14,30){\makebox(0,0)S5x 3}
\put(38,30){\makebox(0,0)A5x S3}
\put(25,5){\line(-1,1)15}
\put(25,5){\line(1,1)15}
\put(35,15){\line(-1,1)15}
\put(15,15){\line(1,1)15}
\put(40,20){\line(-1,1)15}
\put(10,20){\line(1,1)15}
\put(25,25){\line(0,1)10}
end-picture}
\endpicture
gap> a5:= CharTable( "A5" );;
gap> c3:= CharTable( "Cyclic", 3 );;
gap> a5xc3:= CharTableDirectProduct( a5, c3 );;
gap> s5:= CharTable( "A5.2" );;
gap> s3:= CharTable( "Symmetric", 3 );;
gap> s3.irreducibles;
[ [ 1, -1, 1 ], [ 2, 0, -1 ], [ 1, 1, 1 ] ]
# The trivial character shall be the first one.
gap> SortCharactersCharTable( s3 ); # returns the applied permutation
(1,2,3)
gap> s5xs3:= CharTableDirectProduct( s5, s3 );;
G is the normal subgroup of index 2 in S5x S3 which contains
neither S5 nor the normal S3. We want to find the classes of
s5xs3 whose union is G. For that, we compute the set of kernels of
irreducibles --remember that they are given simply by lists of numbers of
contained classes-- and then choose those kernels belonging to normal
subgroups of index 2.
gap> kernels:= Set( List( s5xs3.irreducibles, KernelChar ) );
[ [ 1 ], [ 1, 2, 3 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ],
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
19, 20, 21 ], [ 1, 3 ],
[ 1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21 ],
[ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 20 ], [ 1, 4, 7, 10 ],
[ 1, 4, 7, 10, 13, 16, 19 ] ]
gap> sizes:= List( kernels, x -> Sum( Sublist( s5xs3.classes, x ) ) );
[ 1, 6, 360, 720, 3, 360, 360, 60, 120 ]
gap> s5xs3.size;
720
gap> index2:= Sublist( kernels, [ 3, 6, 7 ] );
[ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ],
[ 1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21 ],
[ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 20 ] ]
In order to decide which kernel describes G, we consider the embeddings
of s5 and s3 in s5xs3, given by the subgroup fusions.
gap> s5ins5xs3:= GetFusionMap( s5, s5xs3 );
[ 1, 4, 7, 10, 13, 16, 19 ]
gap> s3ins5xs3:= GetFusionMap( s3, s5xs3 );
[ 1, 2, 3 ]
gap> Filtered( index2, x->Intersection(x,s5ins5xs3)<>s5ins5xs3 and
> Intersection(x,s3ins5xs3)<>s3ins5xs3 );
[ [ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 20 ] ]
gap> nsg:= last[1];
[ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 20 ]
We now construct a first approximation of the character table of this
normal subgroup, namely the restriction of s5xs3 to the classes given
by nsg.
gap> sub:= CharTableNormalSubgroup( s5xs3, nsg );;
#I CharTableNormalSubgroup: classes in [ 8 ] necessarily split
gap> PrintCharTable( sub );
rec( identifier := "Rest(A5.2xS3,[ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 2\
0 ])", size :=
360, name := "Rest(A5.2xS3,[ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 20 ])",\
order := 360, centralizers := [ 360, 180, 24, 12, 18, 9, 15, 15/2,
12, 4, 6 ], orders := [ 1, 3, 2, 6, 3, 3, 5, 15, 2, 4, 6
], powermap := [ , [ 1, 2, 1, 2, 5, 6, 7, 8, 1, 3, 5 ],
[ 1, 1, 3, 3, 1, 1, 7, 7, 9, 10, 9 ],,
[ 1, 2, 3, 4, 5, 6, 1, 2, 9, 10, 11 ] ], classes :=
[ 1, 2, 15, 30, 20, 40, 24, 48, 30, 90, 60
], operations := CharTableOps, irreducibles :=
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1 ],
[ 2, -1, 2, -1, 2, -1, 2, -1, 0, 0, 0 ],
[ 6, 6, -2, -2, 0, 0, 1, 1, 0, 0, 0 ],
[ 4, 4, 0, 0, 1, 1, -1, -1, 2, 0, -1 ],
[ 4, 4, 0, 0, 1, 1, -1, -1, -2, 0, 1 ],
[ 8, -4, 0, 0, 2, -1, -2, 1, 0, 0, 0 ],
[ 5, 5, 1, 1, -1, -1, 0, 0, 1, -1, 1 ],
[ 5, 5, 1, 1, -1, -1, 0, 0, -1, 1, -1 ],
[ 10, -5, 2, -1, -2, 1, 0, 0, 0, 0, 0 ] ], fusions := [ rec(
name := [ 'A', '5', '.', '2', 'x', 'S', '3' ],
map := [ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 20 ] ) ] )
Not all restrictions of irreducible characters of s5xs3 to sub remain
irreducible. We compute those restrictions with norm larger than 1.
gap> red:= Filtered( Restricted( s5xs3, sub, s5xs3.irreducibles ),
> x -> ScalarProduct( sub, x, x ) > 1 );
[ [ 12, -6, -4, 2, 0, 0, 2, -1, 0, 0, 0 ] ]
gap> Filtered( [ 1 .. Length( nsg ) ],
> x -> not IsInt( sub.centralizers[x] ) );
[ 8 ]
Note that sub is not actually a character table in the sense of
mathematics but only a record with components like a character table.
GAP does not know about this subtleties and treats it as a character
table.
As the list centralizers of centralizer orders shows, at least class 8
splits into two conjugacy classes in G, since this is the only
possibility to achieve integral centralizer orders.
Since 10 restrictions of irreducible characters remain irreducible for
G (sub contains 10 irreducibles), only one of the 11 irreducibles of
S5x S3 splits into two irreducibles of G, in other words,
class 8 is the only splitting class.
Thus we create a new approximation of the desired character table (which
we call split) where this class is split; 8th and 9th column of the
known irreducibles are of course equal, and due to the splitting the
second powermap for these columns is ambiguous.
gap> splitting:= [ 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 11 ];;
gap> split:= CharTableSplitClasses( sub, splitting );;
gap> PrintCharTable( split );
rec( identifier := "Split(Rest(A5.2xS3,[ 1, 3, 4, 6, 7, 9, 10, 12, 14,\
17, 20 ]),[ 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 11 ])", size :=
360, order :=
360, name := "Split(Rest(A5.2xS3,[ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 2\
0 ]),[ 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 11 ])", centralizers :=
[ 360, 180, 24, 12, 18, 9, 15, 15, 15, 12, 4, 6 ], classes :=
[ 1, 2, 15, 30, 20, 40, 24, 24, 24, 30, 90, 60 ], orders :=
[ 1, 3, 2, 6, 3, 3, 5, 15, 15, 2, 4, 6 ], powermap :=
[ , [ 1, 2, 1, 2, 5, 6, 7, [ 8, 9 ], [ 8, 9 ], 1, 3, 5 ],
[ 1, 1, 3, 3, 1, 1, 7, 7, 7, 10, 11, 10 ],,
[ 1, 2, 3, 4, 5, 6, 1, 2, 2, 10, 11, 12 ] ], irreducibles :=
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1 ],
[ 2, -1, 2, -1, 2, -1, 2, -1, -1, 0, 0, 0 ],
[ 6, 6, -2, -2, 0, 0, 1, 1, 1, 0, 0, 0 ],
[ 4, 4, 0, 0, 1, 1, -1, -1, -1, 2, 0, -1 ],
[ 4, 4, 0, 0, 1, 1, -1, -1, -1, -2, 0, 1 ],
[ 8, -4, 0, 0, 2, -1, -2, 1, 1, 0, 0, 0 ],
[ 5, 5, 1, 1, -1, -1, 0, 0, 0, 1, -1, 1 ],
[ 5, 5, 1, 1, -1, -1, 0, 0, 0, -1, 1, -1 ],
[ 10, -5, 2, -1, -2, 1, 0, 0, 0, 0, 0, 0 ] ], fusions := [ rec(
name := "Rest(A5.2xS3,[ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 20 ])"
,
map := [ 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 11 ] )
], operations := CharTableOps )
gap> Restricted( sub, split, red );
[ [ 12, -6, -4, 2, 0, 0, 2, -1, -1, 0, 0, 0 ] ]
To complete the table means to find the missing two irreducibles and to complete the powermaps. For this, there are different possibilities. First, one can try to embed G in A8.
gap> a8:= CharTable( "A8" );;
gap> fus:= SubgroupFusions( split, a8 );
[ [ 1, 4, 3, 9, 4, 5, 8, 13, 14, 3, 7, 9 ],
[ 1, 4, 3, 9, 4, 5, 8, 14, 13, 3, 7, 9 ] ]
gap> fus:= RepresentativesFusions( split, fus, a8 );
#I RepresentativesFusions: no subtable automorphisms stored
[ [ 1, 4, 3, 9, 4, 5, 8, 13, 14, 3, 7, 9 ] ]
gap> StoreFusion( split, a8, fus[1] );
The subgroup fusion is unique up to table automorphisms. Now we restrict the irreducibles of A8 to G and reduce.
gap> rest:= Restricted( a8, split, a8.irreducibles );;
gap> red:= Reduced( split, split.irreducibles, rest );
rec(
remainders := [ ],
irreducibles :=
[ [ 6, -3, -2, 1, 0, 0, 1, -E(15)-E(15)^2-E(15)^4-E(15)^8,
-E(15)^7-E(15)^11-E(15)^13-E(15)^14, 0, 0, 0 ],
[ 6, -3, -2, 1, 0, 0, 1, -E(15)^7-E(15)^11-E(15)^13-E(15)^14,
-E(15)-E(15)^2-E(15)^4-E(15)^8, 0, 0, 0 ] ] )
gap> Append( split.irreducibles, red.irreducibles );
The list of irreducibles is now complete, but the powermaps are not yet adjusted. To complete the 2nd powermap, we transfer that of A8 to G using the subgroup fusion.
gap> split.powermap;
[ , [ 1, 2, 1, 2, 5, 6, 7, [ 8, 9 ], [ 8, 9 ], 1, 3, 5 ],
[ 1, 1, 3, 3, 1, 1, 7, 7, 7, 10, 11, 10 ],,
[ 1, 2, 3, 4, 5, 6, 1, 2, 2, 10, 11, 12 ] ]
gap> TransferDiagram( split.powermap[2], fus[1], a8.powermap[2] );;
And this is the complete table.
gap> split.identifier:= "(A5x3):2";;
gap> DisplayCharTable( split );
Split(Rest(A5.2xS3,[ 1, 3, 4, 6, 7, 9, 10, 12, 14, 17, 20 ]),[ 1, 2, 3\
, 4, 5, 6, 7, 8, 8, 9, 10, 11 ])
2 3 2 3 2 1 . . . . 2 2 1
3 2 2 1 1 2 2 1 1 1 1 . 1
5 1 1 . . . . 1 1 1 . . .
1a 3a 2a 6a 3b 3c 5a 15a 15b 2b 4a 6b
2P 1a 3a 1a 3a 3b 3c 5a 15a 15b 1a 2a 3b
3P 1a 1a 2a 2a 1a 1a 5a 5a 5a 2b 4a 2b
5P 1a 3a 2a 6a 3b 3c 1a 3a 3a 2b 4a 6b
X.1 1 1 1 1 1 1 1 1 1 1 1 1
X.2 1 1 1 1 1 1 1 1 1 -1 -1 -1
X.3 2 -1 2 -1 2 -1 2 -1 -1 . . .
X.4 6 6 -2 -2 . . 1 1 1 . . .
X.5 4 4 . . 1 1 -1 -1 -1 2 . -1
X.6 4 4 . . 1 1 -1 -1 -1 -2 . 1
X.7 8 -4 . . 2 -1 -2 1 1 . . .
X.8 5 5 1 1 -1 -1 . . . 1 -1 1
X.9 5 5 1 1 -1 -1 . . . -1 1 -1
X.10 10 -5 2 -1 -2 1 . . . . . .
X.11 6 -3 -2 1 . . 1 A /A . . .
X.12 6 -3 -2 1 . . 1 /A A . . .
A = -E(15)-E(15)^2-E(15)^4-E(15)^8
= (-1-ER(-15))/2 = -1-b15
There are many ways around the block, so two further methods to complete
the table split shall be demonstrated; but we will not go into details.
Without use of GAP one could work as follows:
The irrationalities --and there must be irrational entries in the character table of G, since the outer 2 can conjugate at most two of the four Galois conjugate classes of elements of order 15-- could also have been found from the structure of G and the restriction of the irreducible S5x S3 character of degree 12.
On the classes that did not split the values of this character must just
be divided by 2. Let x be one of the irrationalities. The second
orthogonality relation tells us that x.\overlinex = 4 (at class
15a) and x + x* = -1 (at classes 1a and 15a); here x*
denotes the nontrivial Galois conjugate of x. This has no solution for
x = \overlinex, otherwise it leads to the quadratic equation
x2+x+4 = 0 with solutions b15 = 1/2(-1+√-15) and
-1-b15.
The third possibility to complete the table is to embed A5x 3:
gap> split.irreducibles := split.irreducibles{ [ 1 .. 10 ] };;
gap> SubgroupFusions( a5xc3, split );
[ [ 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, [ 8, 9 ], [ 8, 9 ], 7, [ 8, 9 ],
[ 8, 9 ] ] ]
The images of the four classes of element order 15 are not determined, the returned list parametrizes the 24 possibilities.
gap> fus:= ContainedMaps( last[1] );;
gap> Length( fus );
16
gap> fus[1];
[ 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 7, 8, 8 ]
Most of these 16 possibilities are excluded using scalar products of
induced characters. We take a suitable character chi of a5xc3 and
compute the norm of the induced character with respect to each possible
map.
gap> chi:= a5xc3.irreducibles[5];
[ 3, 3*E(3), 3*E(3)^2, -1, -E(3), -E(3)^2, 0, 0, 0, -E(5)-E(5)^4,
-E(15)^2-E(15)^8, -E(15)^7-E(15)^13, -E(5)^2-E(5)^3,
-E(15)^11-E(15)^14, -E(15)-E(15)^4 ]
gap> List( fus, x -> List( Induced( a5xc3, split, [ chi ], x ),
> y -> ScalarProduct( split, y, y ) )[1] );
[ 8/15, -2/3*E(5)-11/15*E(5)^2-11/15*E(5)^3-2/3*E(5)^4,
-2/3*E(5)-11/15*E(5)^2-11/15*E(5)^3-2/3*E(5)^4, 2/3,
-11/15*E(5)-2/3*E(5)^2-2/3*E(5)^3-11/15*E(5)^4, 3/5, 1,
-11/15*E(5)-2/3*E(5)^2-2/3*E(5)^3-11/15*E(5)^4,
-11/15*E(5)-2/3*E(5)^2-2/3*E(5)^3-11/15*E(5)^4, 1, 3/5,
-11/15*E(5)-2/3*E(5)^2-2/3*E(5)^3-11/15*E(5)^4, 2/3,
-2/3*E(5)-11/15*E(5)^2-11/15*E(5)^3-2/3*E(5)^4,
-2/3*E(5)-11/15*E(5)^2-11/15*E(5)^3-2/3*E(5)^4, 8/15 ]
gap> Filtered( [ 1 .. Length( fus ) ], x -> IsInt( last[x] ) );
[ 7, 10 ]
So only fusions 7 and 10 may be possible. They are equivalent (with respect to table automorphisms), and the list of induced characters contains the missing irreducibles of G:
gap> Sublist( fus, last );
[ [ 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 7, 9, 8 ],
[ 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 9, 8, 7, 8, 9 ] ]
gap> ind:= Induced( a5xc3, split, a5xc3.irreducibles, last[1] );;
gap> Reduced( split, split.irreducibles, ind );
rec(
remainders := [ ],
irreducibles :=
[ [ 6, -3, -2, 1, 0, 0, 1, -E(15)-E(15)^2-E(15)^4-E(15)^8,
-E(15)^7-E(15)^11-E(15)^13-E(15)^14, 0, 0, 0 ],
[ 6, -3, -2, 1, 0, 0, 1, -E(15)^7-E(15)^11-E(15)^13-E(15)^14,
-E(15)-E(15)^2-E(15)^4-E(15)^8, 0, 0, 0 ] ] )
The following example is thought mainly for experts. It shall demonstrate how one can work together with GAP and the ATLAS CCN85, so better leave out the rest of this section if you are not familiar with the ATLAS.
\setlength\unitlength0.1cm
beg-minipage[t]90mm
We shall construct the character table of the group
G = A6.22 ≅ Aut( A6 ) from the tables of the normal subgroups
A6.21 ≅ S6, A6.22 ≅ PGL(2,9) and A6.23 ≅ M10.
We regard G as a downward extension of the Klein fourgroup 22 with A6. The set of classes of all preimages of cyclic subgroups of 22 covers the classes of G, but it may happen that some representatives are conjugate in G, i.e., the classes fuse.
The ATLAS denotes the character tables of G, G.21, G.22 and
G.23 as follows:
end-minipage beg-picture(0,0)
\put(5,-40){\beginpicture(50,45)
\put(25,5){\circle1}
\put(25,20){\makebox(0,0)A6}
\put(25,30){\makebox(0,0)A6.23}
\put(15,30){\makebox(0,0)A6.21}
\put(35,30){\makebox(0,0)A6.22}
\put(25,40){\makebox(0,0)G}
\put(25,5){\line(0,1)12}
\put(23,22){\line(-1,1)6}
\put(27,22){\line(1,1)6}
\put(25,22){\line(0,1)6}
\put(23,38){\line(-1,-1)6}
\put(27,38){\line(1,-1)6}
\put(25,38){\line(0,-1)6}
end-picture}
\endpicture
\vbox{
beg-picture(0,0)\put(69.25,-76.25){\line(0,1)10}end-picture
; @ @ @ @ @ @ @ ; ; @ @ @ @ @
360 8 9 9 4 5 5 24 24 4 3 3
p power A A A A A A A A A AB BC
p
\mbox\char13
part A A A A A A A A A AB BC ind 1A 2A 3A 3B 4A 5A B* fus ind 2B 2C 4B 6A 6Bχ1
+ 1 1 1 1 1 1 1 : ++ 1 1 1 1 1χ2
+ 5 1 2 -1 -1 0 0 : ++ 3 -1 1 0 -1χ3
+ 5 1 -1 2 -1 0 0 : ++ -1 3 1 -1 0χ4
+ 8 0 -1 -1 0 -b5 * . + 0 0 0 0 0χ5
+ 8 0 -1 -1 0 * -b5 .χ6
+ 9 1 0 0 1 -1 -1 : ++ 3 3 -1 0 0χ7
+ 10 -2 1 1 0 0 0 : ++ 2 -2 0 -1 1
}
\vbox{
beg-picture(0,0)
\put(6.5,-52){\line(0,1)8.5}
\put(56.25,-69){\line(0,1)9}
\put(56.25,-52){\line(0,1)8.5}
end-picture
; ; @ @ @ @ @ ; ; @ @ @
10 4 4 5 5 2 4 4
A A A BD AD A A A
A A A AD BD A A A
fus ind 2D 8A B* 10A B* fus ind 4C 8C D**
: ++ 1 1 1 1 1 : ++ 1 1 1 χ1. + 0 0 0 0 0 . + 0 0 0χ2
. .χ3
: ++ 2 0 0 b5 * . + 0 0 0χ4
: ++ 2 0 0 * b5 .χ5
: ++ -1 1 1 -1 -1 : ++ 1 -1 -1χ6
: ++ 0 r2 -r2 0 0 : oo 0 i2 -i2χ7
}
First we construct a table whose classes are those of the three subgroups. Note that the exponent of A6 is 60, so the representative orders could become at most 60 times the value in 22.
gap> s1:= CharTable( "A6.2_1" );;
gap> s2:= CharTable( "A6.2_2" );;
gap> s3:= CharTable( "A6.2_3" );;
gap> c2:= CharTable( "Cyclic", 2 );;
gap> v4:= CharTableDirectProduct( c2, c2 );;
#I CharTableDirectProduct: existing subgroup fusion on replaced
#I by actual one
gap> for tbl in [ s1, s2, s3 ] do
> Print( tbl.irreducibles[2], "\n" );
> od;
[ 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1 ]
[ 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1 ]
[ 1, 1, 1, 1, 1, -1, -1, -1 ]
gap> split:= CharTableSplitClasses( v4,
> [1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4], 60 );;
gap> PrintCharTable( split );
rec( identifier := "Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, \
3, 3, 3, 4, 4, 4 ])", size := 4, order :=
4, name := "Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3,\
4, 4, 4 ])", centralizers := [ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4 ], classes := [ 1/5, 1/5, 1/5, 1/5, 1/5, 1/5, 1/5,
1/5, 1/5, 1/5, 1/5, 1/5, 1/5, 1/5, 1/5, 1/3, 1/3, 1/3 ], orders :=
[ 1, [ 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 ],
[ 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 ],
[ 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 ],
[ 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ],
[ 2, 4, 6, 8, 10, 12, 20, 24, 30, 40, 60, 120 ] ], powermap :=
[ , [ 1, [ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ] ] ], irreducibles :=
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, -1, -1, -1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1 ]
], fusions := [ rec(
name := [ 'C', '2', 'x', 'C', '2' ],
map := [ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4 ]
) ], operations := CharTableOps )
Now we embed the subgroups and adjust the classlengths, order, centralizers, powermaps and thus the representative orders.
gap> StoreFusion( s1, split, [1,2,3,3,4,5,6,7,8,9,10]);
gap> StoreFusion( s2, split, [1,2,3,4,5,5,11,12,13,14,15]);
gap> StoreFusion( s3, split, [1,2,3,4,5,16,17,18]);
gap> for tbl in [ s1, s2, s3 ] do
> fus:= GetFusionMap( tbl, split );
> for class in Difference( [ 1 .. Length( tbl.classes ) ],
> KernelChar(tbl.irreducibles[2]) ) do
> split.classes[ fus[ class ] ]:= tbl.classes[ class ];
> od;
> od;
gap> for class in [ 1 .. 5 ] do
> split.classes[ class ]:= s3.classes[ class ];
> od;
gap> split.classes;
[ 1, 45, 80, 90, 144, 15, 15, 90, 120, 120, 36, 90, 90, 72, 72, 180,
90, 90 ]
gap> split.size:= Sum( last );
1440
gap> split.order:= last;
gap> split.centralizers:= List( split.classes, x -> split.order / x );
[ 1440, 32, 18, 16, 10, 96, 96, 16, 12, 12, 40, 16, 16, 20, 20, 8,
16, 16 ]
gap> split.powermap[3]:= InitPowermap( split, 3 );;
gap> split.powermap[5]:= InitPowermap( split, 5 );;
gap> for tbl in [ s1, s2, s3 ] do
> fus:= GetFusionMap( tbl, split );
> for p in [ 2, 3, 5 ] do
> TransferDiagram( tbl.powermap[p], fus, split.powermap[p] );
> od;
> od;
gap> split.powermap;
[ , [ 1, 1, 3, 2, 5, 1, 1, 2, 3, 3, 1, 4, 4, 5, 5, 2, 4, 4 ],
[ 1, 2, 1, 4, 5, 6, 7, 8, 6, 7, 11, 13, 12, 15, 14, 16, 17, 18 ],,
[ 1, 2, 3, 4, 1, 6, 7, 8, 9, 10, 11, 13, 12, 11, 11, 16, 18, 17 ] ]
gap> split.orders:= ElementOrdersPowermap( split.powermap );
[ 1, 2, 3, 4, 5, 2, 2, 4, 6, 6, 2, 8, 8, 10, 10, 4, 8, 8 ]
In order to decide which classes fuse in G, we look at the norms of suitable induced characters, first the + extension of χ2 to A6.21.
gap> ind:= Induced( s1, split, [ s1.irreducibles[3] ] )[1];
[ 10, 2, 1, -2, 0, 6, -2, 2, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0 ]
gap> ScalarProduct( split, ind, ind );
3/2
The inertia group of this character is A6.21, thus the norm of the
induced character must be 1. If the classes 2B and 2C fuse, the
contribution of these classes is changed from 15. 62+15.(-2)2
to 30 . 22, the difference is 480. But we have to subtract 720
which is half the group order, so also 6A and 6B fuse. This is not
surprising, since it reflects the action of the famous outer automorphism
of S6. Next we examine the + extension of χ4 to A6.22.
gap> ind:= Induced( s2, split, [ s2.irreducibles[4] ] )[1];
[ 16, 0, -2, 0, 1, 0, 0, 0, 0, 0, 4, 0, 0, 2*E(5)+2*E(5)^4,
2*E(5)^2+2*E(5)^3, 0, 0, 0 ]
gap> ScalarProduct( split, ind, ind );
3/2
Again, the norm must be 1, 10A and 10B fuse.
gap> collaps:= CharTableCollapsedClasses( split,
> [1,2,3,4,5,6,6,7,8,8,9,10,11,12,12,13,14,15] );;
gap> PrintCharTable( collaps );
rec( identifier := "Collapsed(Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, 2, 2,\
2, 3, 3, 3, 3, 3, 4, 4, 4 ]),[ 1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 1\
1, 12, 12, 13, 14, 15 ])", size := 1440, order :=
1440, name := "Collapsed(Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3\
, 3, 3, 3, 3, 4, 4, 4 ]),[ 1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 11, 12\
, 12, 13, 14, 15 ])", centralizers := [ 1440, 32, 18, 16, 10, 48, 16,
6, 40, 16, 16, 10, 8, 16, 16 ], orders :=
[ 1, 2, 3, 4, 5, 2, 4, 6, 2, 8, 8, 10, 4, 8, 8 ], powermap :=
[ , [ 1, 1, 3, 2, 5, 1, 2, 3, 1, 4, 4, 5, 2, 4, 4 ],
[ 1, 2, 1, 4, 5, 6, 7, 6, 9, 11, 10, 12, 13, 14, 15 ],,
[ 1, 2, 3, 4, 1, 6, 7, 8, 9, 11, 10, 9, 13, 15, 14 ]
], fusionsource :=
[ "Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4 \
])" ], irreducibles :=
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1 ]
], classes := [ 1, 45, 80, 90, 144, 30, 90, 240, 36, 90, 90, 144,
180, 90, 90 ], operations := CharTableOps )
gap> split.fusions;
[ rec(
name := [ 'C', '2', 'x', 'C', '2' ],
map := [ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4 ]
), rec(
name :=
"Collapsed(Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3,\
3, 3, 4, 4, 4 ]),[ 1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 11, 12, 12, 1\
3, 14, 15 ])",
map := [ 1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 11, 12, 12, 13,
14, 15 ] ) ]
gap> for tbl in [ s1, s2, s3 ] do
> StoreFusion( tbl, collaps,
> CompositionMaps( GetFusionMap( split, collaps ),
> GetFusionMap( tbl, split ) ) );
> od;
gap> ind:= Induced( s1, collaps, [ s1.irreducibles[10] ] )[1];
[ 20, -4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
gap> ScalarProduct( collaps, ind, ind );
1
This character must be equal to any induced character of an irreducible
character of degree 10 of A6.22 and A6.23. That means, 8A
fuses with 8B, and 8C with 8D.
gap> a6v4:= CharTableCollapsedClasses( collaps,
> [1,2,3,4,5,6,7,8,9,10,10,11,12,13,13] );;
gap> PrintCharTable( a6v4 );
rec( identifier := "Collapsed(Collapsed(Split(C2xC2,[ 1, 1, 1, 1, 1, 2\
, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4 ]),[ 1, 2, 3, 4, 5, 6, 6, 7, 8, 8\
, 9, 10, 11, 12, 12, 13, 14, 15 ]),[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10\
, 11, 12, 13, 13 ])", size := 1440, order :=
1440, name := "Collapsed(Collapsed(Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, \
2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4 ]),[ 1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 9, \
10, 11, 12, 12, 13, 14, 15 ]),[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11,\
12, 13, 13 ])", centralizers := [ 1440, 32, 18, 16, 10, 48, 16, 6,
40, 8, 10, 8, 8 ], orders := [ 1, 2, 3, 4, 5, 2, 4, 6, 2, 8, 10, 4,
8 ], powermap := [ , [ 1, 1, 3, 2, 5, 1, 2, 3, 1, 4, 5, 2, 4 ],
[ 1, 2, 1, 4, 5, 6, 7, 6, 9, 10, 11, 12, 13 ],,
[ 1, 2, 3, 4, 1, 6, 7, 8, 9, 10, 9, 12, 13 ] ], fusionsource :=
[ "Collapsed(Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3\
, 4, 4, 4 ]),[ 1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 11, 12, 12, 13, 14\
, 15 ])" ], irreducibles :=
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, 1 ] ], classes :=
[ 1, 45, 80, 90, 144, 30, 90, 240, 36, 180, 144, 180, 180
], operations := CharTableOps )
gap> for tbl in [ s1, s2, s3 ] do
> StoreFusion( tbl, a6v4,
> CompositionMaps( GetFusionMap( collaps, a6v4 ),
> GetFusionMap( tbl, collaps ) ) );
> od;
Now the classes of G are known, the only remaining work is to compute the irreducibles.
gap> a6v4.irreducibles;
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, 1 ] ]
gap> for tbl in [ s1, s2, s3 ] do
> ind:= Set( Induced( tbl, a6v4, tbl.irreducibles ) );
> Append( a6v4.irreducibles,
> Filtered( ind, x -> ScalarProduct( a6v4,x,x ) = 1 ) );
> od;
gap> a6v4.irreducibles:= Set( a6v4.irreducibles );
[ [ 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, 1 ],
[ 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 10, 2, 1, -2, 0, -2, -2, 1, 0, 0, 0, 0, 0 ],
[ 10, 2, 1, -2, 0, 2, 2, -1, 0, 0, 0, 0, 0 ],
[ 16, 0, -2, 0, 1, 0, 0, 0, -4, 0, 1, 0, 0 ],
[ 16, 0, -2, 0, 1, 0, 0, 0, 4, 0, -1, 0, 0 ],
[ 20, -4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ]
gap> sym:= Symmetrizations( a6v4, [ a6v4.irreducibles[5] ], 2 );
[ [ 45, -3, 0, 1, 0, -3, 1, 0, -5, 1, 0, -1, 1 ],
[ 55, 7, 1, 3, 0, 7, 3, 1, 5, -1, 0, 1, -1 ] ]
gap> Reduced( a6v4, a6v4.irreducibles, sym );
rec(
remainders := [ [ 27, 3, 0, 3, -3, 3, -1, 0, 1, -1, 1, 1, -1 ] ],
irreducibles := [ [ 9, 1, 0, 1, -1, -3, 1, 0, -1, 1, -1, -1, 1 ] ] )
gap> Append( a6v4.irreducibles,
> Tensored( last.irreducibles,
> Sublist( a6v4.irreducibles, [ 1 .. 4 ] ) ) );
gap> SortCharactersCharTable( a6v4,
> (1,4)(2,3)(5,6)(7,8)(9,13,10,11,12) );;
gap> a6v4.identifier:= "A6.2^2";;
gap> DisplayCharTable( a6v4 );
Collapsed(Collapsed(Split(C2xC2,[ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, \
3, 3, 3, 4, 4, 4 ]),[ 1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 11, 12, 12,\
13, 14, 15 ]),[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11, 12, 13, 13 ])
2 5 5 1 4 1 4 4 1 3 3 1 3 3
3 2 . 2 . . 1 . 1 . . . . .
5 1 . . . 1 . . . 1 . 1 . .
1a 2a 3a 4a 5a 2b 4b 6a 2c 8a 10a 4c 8b
2P 1a 1a 3a 2a 5a 1a 2a 3a 1a 4a 5a 2a 4a
3P 1a 2a 1a 4a 5a 2b 4b 2b 2c 8a 10a 4c 8b
5P 1a 2a 3a 4a 1a 2b 4b 6a 2c 8a 2c 4c 8b
X.1 1 1 1 1 1 1 1 1 1 1 1 1 1
X.2 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1
X.3 1 1 1 1 1 -1 -1 -1 1 1 1 -1 -1
X.4 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 1
X.5 10 2 1 -2 . 2 2 -1 . . . . .
X.6 10 2 1 -2 . -2 -2 1 . . . . .
X.7 16 . -2 . 1 . . . 4 . -1 . .
X.8 16 . -2 . 1 . . . -4 . 1 . .
X.9 9 1 . 1 -1 -3 1 . 1 -1 1 1 -1
X.10 9 1 . 1 -1 -3 1 . -1 1 -1 -1 1
X.11 9 1 . 1 -1 3 -1 . 1 -1 1 -1 1
X.12 9 1 . 1 -1 3 -1 . -1 1 -1 1 -1
X.13 20 -4 2 . . . . . . . . . .
When you start GAP it already knows several groups. For example, some basic groups such as cyclic groups or symmetric groups, all primitive permutation groups of degree at most 50, and all 2-groups of size at most 256.
Each of the sets above is called a group library. The set of all groups that GAP knows initially is called the collection of group libraries.
In this section we show you how you can access the groups in those libraries and how you can extract groups with certain properties from those libraries.
Let us start with the basic groups, because they are not accessed in the same way as the groups in the other libraries.
To access such a basic group you just call a function with an appropriate
name, such as CyclicGroup or SymmetricGroup.
gap> c13 := CyclicGroup( 13 );
Group( ( 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13) )
gap> Size( c13 );
13
gap> s8 := SymmetricGroup( 8 );
Group( (1,8), (2,8), (3,8), (4,8), (5,8), (6,8), (7,8) )
gap> Size( s8 );
40320
The functions above also accept an optional first argument that describes
the type of group. For example you can pass AgWords to CyclicGroup
to get a cyclic group as a finite polycyclic group (see Finite
Polycyclic Groups).
gap> c13 := CyclicGroup( AgWords, 13 );
Group( c13 )
Of course you cannot pass AgWords to SymmetricGroup, because
symmetric groups are in general not polycyclic.
The default is to construct the groups as permutation groups, but you can
also explicitly pass Permutations. Other possible arguments are
AgWords for finite polycyclic groups, Words for finitely presented
groups, and Matrices for matrix groups (however only Permutations and
AgWords currently work).
Let us now turn to the other libraries. They are all accessed in a uniform way. For a first example we will use the group library of primitive permutation groups.
To extract a group from a group library you generally use the extraction
function. In our example this function is called PrimitiveGroup. It
takes two arguments. The first is the degree of the primitive
permutation group that you want and the second is an integer that
specifies which of the primitive permutation groups of that degree you
want.
gap> g := PrimitiveGroup( 12, 3 );
M(11)
gap> g.generators;
[ ( 2, 6)( 3, 5)( 4, 7)( 9,10), ( 1, 5, 7)( 2, 9, 4)( 3, 8,10),
( 1,11)( 2, 7)( 3, 5)( 4, 6), ( 2, 5)( 3, 6)( 4, 7)(11,12) ]
gap> Size( g );
7920
gap> IsSimple( g );
true
gap> h := PrimitiveGroup( 16, 19 );
2^4.A(7)
gap> Size( h );
40320
The reason for the extraction function is as follows. A group library is usually not stored as a list of groups. Instead a more compact representation for the groups is used. For example the groups in the library of 2-groups are represented by 4 integers. The extraction function hides this representation from you, and allows you to access the group library as if it was a table of groups (two dimensional in the above example).
What arguments the extraction function accepts, and how they are interpreted is described in the sections that describe the individual group libraries in chapter Group Libraries. Those functions will of course signal an error when you pass illegal arguments.
Suppose that you want to get a list of all primitive permutation groups
that have a degree 10 and are simple but not cyclic. It would be very
difficult to use the extraction function to extract all groups in the
group library, and test each of those. It is much simpler to use the
selection function. The name of the selection function always begins
with All and ends with Groups, in our example it is thus called
AllPrimitiveGroups.
gap> AllPrimitiveGroups( DegreeOperation, 10,
> IsSimple, true,
> IsCyclic, false );
[ A(5), PSL(2,9), A(10) ]
AllPrimitiveGroups takes a variable number of argument pairs consisting
of a function (e.g. DegreeOperation) and a value (e.g. 10). To
understand what AllPrimitiveGroups does, imagine that the group library
was stored as a long list of permutation groups. AllPrimitiveGroups
takes all those groups in turn. To each group it applies each function
argument and compares the result with the corresponding value argument.
It selects a group if and only if all the function results are equal to
the corresponding value. So in our example AllPrimitiveGroups selects
those groups g for which DegreeOperation(g) = 10 and
IsSimple(g) = true and IsCyclic(g) = false. Finally
AllPrimitiveGroups returns the list of the selected groups.
Next suppose that you want all the primitive permutation groups that have
degree at most 10, are simple but are not cyclic. You could obtain
such a list with 10 calls to AllPrimitiveGroups (i.e., one call for the
degree 1 groups, another for the degree 2 groups and so on), but there is
a simple way. Instead of specifying a single value that a function must
return you can simply specify a list of such values.
gap> AllPrimitiveGroups( DegreeOperation, [1..10],
> IsSimple, true,
> IsCyclic, false );
[ A(5), PSL(2,5), A(6), PSL(3,2), A(7), PSL(2,7), A(8), PSL(2,8),
A(9), A(5), PSL(2,9), A(10) ]
Note that the list that you get contains A(5) twice, first in its
primitive presentation on 5 points and second in its primitive
presentation on 10 points.
Thus giving several argument pairs to the selection function allows you to express the logical and of properties that a group must have to be selected, and giving a list of values allows you to express a (restricted) logical or of properties that a group must have to be selected.
There is no restriction on the functions that you can use. It is even possible to use functions that you have written yourself. Of course, the functions must be unary, i.e., accept only one argument, and must be able to deal with the groups.
gap> NumberConjugacyClasses := function ( g )
> return Length( ConjugacyClasses( g ) );
> end;
function ( g ) ... end
gap> AllPrimitiveGroups( DegreeOperation, [1..10],
> IsSimple, true,
> IsCyclic, false,
> NumberConjugacyClasses, 9 );
[ A(7), PSL(2,8) ]
Note that in some cases a selection function will issue a warning. For
example if you call AllPrimitiveGroups without specifying the degree,
it will issue such a warning.
gap> AllPrimitiveGroups( Size, [100..400],
> IsSimple, true,
> IsCyclic, false );
#W AllPrimitiveGroups: degree automatically restricted to [1..50]
[ A(6), PSL(3,2), PSL(2,7), PSL(2,9), A(6) ]
If selection functions would really run over the list of all groups in a group library and apply the function arguments to each of those, they would be very inefficient. For example the 2-groups library contains 58760 groups. Simply creating all those groups would take a very long time.
Instead selection functions recognize certain functions and handle them
more efficiently. For example AllPrimitiveGroups recognizes
DegreeOperation. If you pass DegreeOperation to AllPrimitiveGroups
it does not create a group to apply DegreeOperation to it. Instead it
simply consults an index and quickly eliminates all groups that have a
different degree. Other functions recognized by AllPrimitiveGroups are
IsSimple, Size, and Transitivity.
So in our examples AllPrimitiveGroups, recognizing DegreeOperation
and IsSimple, eliminates all but 16 groups. Then it creates those 16
groups and applies IsCyclic to them. This eliminates 4 more groups
(C(2), C(3), C(5), and C(7)). Then in our last example it
applies NumberConjugacyClasses to the remaining 12 groups and
eliminates all but A(7) and PSL(2,8).
The catch is that the selection functions will take a large amount of
time if they cannot recognize any special functions. For example the
following selection will take a large amount of time, because only
IsSimple is recognized, and there are 116 simple groups in the
primitive groups library.
AllPrimitiveGroups( IsSimple, true, NumberConjugacyClasses, 9 );
So you should specify a sufficiently large set of recognizable functions when you call a selection function. It is also advisable to put those functions first (though in some group libraries the selection function will automatically rearrange the argument pairs so that the recognized functions come first). The sections describing the individual group libraries in chapter Group Libraries tell you which functions are recognized by the selection function of that group library.
There is another function, called the example function that behaves
similar to the selection function. Instead of returning a list of all
groups with a certain set of properties it only returns one such group.
The name of the example function is obtained by replacing All by One
and stripping the s at the end of the name of the selection function.
gap> OnePrimitiveGroup( DegreeOperation, [1..10],
> IsSimple, true,
> IsCyclic, false,
> NumberConjugacyClasses, 9 );
A(7)
The example function works just like the selection function. That means that all the above comments about the special functions that are recognized also apply to the example function.
Let us now look at the 2-groups library. It is accessed in the same way
as the primitive groups library. There is an extraction function
TwoGroup, a selection function AllTwoGroups, and an example function
OneTwoGroup.
gap> g := TwoGroup( 128, 5 );
Group( a1, a2, a3, a4, a5, a6, a7 )
gap> Size( g );
128
gap> NumberConjugacyClasses( g );
80
The groups are all displayed as Group( a1, a2, ..., an ), where 2n
is the size of the group.
gap> AllTwoGroups( Size, 256,
> Rank, 3,
> pClass, 2 );
[ Group( a1, a2, a3, a4, a5, a6, a7, a8 ),
Group( a1, a2, a3, a4, a5, a6, a7, a8 ),
Group( a1, a2, a3, a4, a5, a6, a7, a8 ),
Group( a1, a2, a3, a4, a5, a6, a7, a8 ) ]
gap> l := AllTwoGroups( Size, 256,
> Rank, 3,
> pClass, 5,
> g -> Length( DerivedSeries( g ) ), 4 );;
gap> Length( l );
28
The selection and example function of the 2-groups library recognize
Size, Rank, and pClass. Note that Rank and pClass are
functions that can in fact only be used in this context, i.e., they can
not be applied to arbitrary groups.
The following discussion is a bit technical and you can ignore it safely.
For very big group libraries, such as the 2-groups library, the groups (or their compact representations) are not stored on a single file. This is because this file would be very large and loading it would take a long time and a lot of main memory.
Instead the groups are stored on a small number of files (27 in the case of the 2-groups). The selection and example functions are careful to load only those files that may actually contain groups with the specified properties. For example in the above example the files containing the groups of size less than 256 are never loaded. In fact in the above example only one very small file is loaded.
When a file is loaded the selection and example functions also unload the previously loaded file. That means that they forget all the groups in this file again (except those selected of course). Thus even if the selection or example functions have to search through the whole group library, only a small part of the library is held in main memory at any time. In principle it should be possible to search the whole 2-groups library with as little as 2 MByte of main memory.
If you have sufficient main memory available you can explicitly load
files from the 2-groups library with ReadTwo( filename ), e.g.,
Read( "twogp64" ) to load the file with the groups of size 64. Those
files will then not be unloaded again. This will take up more main
memory, but the selection and example function will work faster, because
they do not have to load those files again each time they are needed.
In this section you have seen the basic groups library and the group libraries of primitive groups and 2-groups. You have seen how you can extract a single group from such a library with the extraction function. You have seen how you can select groups with certain properties with the selection and example function. Chapter Group Libraries tells you which other group libraries are available.
1.27 About the Implementation of Domains
In this section we will open the black boxes and describe how all this works. This is complex and you do not need to understand it if you are content to use domains only as black boxes. So you may want to skip this section (and the remainder of this chapter).
Domains are represented by records, which we will call domain records in the following. Which components have to be present, which may, and what those components hold, differs from category to category, and, to a smaller extent, from domain to domain. It is possible, though, to generally distinguish four types of components.
The first type of components are called the category components. They
determine to which category a domain belongs. A domain D in a category
Cat has a component isCat with the value true. For example, each
group has the component isGroup. Also each domain has the component
isDomain (again with the value true). Finally a domain may also have
components that describe the representation of this domain. For example,
each permutation group has a component isPermGroup (again with the
value true). Functions such as IsPermGroup test whether such a
component is present, and whether it has the value true.
The second type of components are called the identification components.
They distinguish the domain from other domains in the same category. The
identification components uniquely identify the domain. For example, for
groups the identification components are generators, which holds a list
of generators of the group, and identity, which holds the identity of
the group (needed for the trivial group, for which the list of generators
is empty).
The third type of components are called knowledge components. They
hold all the knowledge GAP has about the domain. For example the size
of the domain D is stored in the knowledge component D.size, the
commutator subgroup of a group is stored in the knowledge component
D.commutatorSubgroup, etc. Of course, the knowledge about a certain
domain will usually increase as you work with a domain. For example, a
group record may initially hold only the knowledge that the group is
finite, but may later hold all kinds of knowledge, for example the
derived series, the Sylow subgroups, etc.
Finally each domain record contains an operations record. The operations record is discussed below.
We want to emphasize that really all information that GAP has about a domain is stored in the knowledge components. That means that you can access all this information, at least if you know where to look and how to interpret what you see. The chapters describing categories and domains will tell you what knowledge components a domain may have, and how the knowledge is represented in those components.
For an example let us return to the permutation group a5 from section
About Domains and Categories. If we print the record using the
function PrintRec we see all the information. GAP stores the
stabilizer chain of a5 in the components orbit, transversal, and
stabilizer. It is not important that you understand what a stabilizer
chain is (this is discussed in chapter Permutation Groups), the
important point here is that it is the vital information that GAP
needs to work efficiently with a5 and that you can access it.
gap> a5 := Group( (1,2,3), (3,4,5) );
Group( (1,2,3), (3,4,5) )
gap> Size( a5 );
60
gap> PrintRec( a5 ); Print( "\n" );
rec(
isDomain := true,
isGroup := true,
identity := (),
generators := [ (1,2,3), (3,4,5) ],
operations := ...,
isPermGroup := true,
isFinite := true,
1 := (1,2,3),
2 := (3,4,5),
orbit := [ 1, 3, 2, 5, 4 ],
transversal := [ (), (1,2,3), (1,2,3), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ (3,4,5), (2,5,3) ],
orbit := [ 2, 3, 5, 4 ],
transversal := [ , (), (2,5,3), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ (3,4,5) ],
orbit := [ 3, 5, 4 ],
transversal := [ ,, (), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ ],
operations := ... ),
operations := ... ),
operations := ... ),
isParent := true,
stabChainOptions := rec(
random := 1000,
operations := ... ),
stabChain := rec(
generators := [ (1,2,3), (3,4,5) ],
identity := (),
orbit := [ 1, 3, 2, 5, 4 ],
transversal := [ (), (1,2,3), (1,2,3), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ (3,4,5), (2,5,3) ],
orbit := [ 2, 3, 5, 4 ],
transversal := [ , (), (2,5,3), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ (3,4,5) ],
orbit := [ 3, 5, 4 ],
transversal := [ ,, (), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ ],
operations := ... ),
operations := ... ),
operations := ... ),
operations := ... ),
size := 60 )
Note that you can not only read this information, you can also modify it. However, unless you truly understand what you are doing, we discourage you from playing around. All GAP functions assume that the information in the domain record is in a consistent state, and everything will go wrong if it is not.
gap> a5.size := 120;
120
gap> Size( ConjugacyClass( a5, (1,2,3,4,5) ) );
24 # this is of course wrong
As was mentioned above, each domain record has an operations record. We
have already seen that functions such as Size can be applied to various
types of domains. It is clear that there is no general method that will
compute the size of all domains efficiently. So Size must somehow
decide which method to apply to a given domain. The operations record
makes this possible.
The operations record of a domain D is the component with the name
D.operations, its value is a record. For each function that you can
apply to D this record contains a function that will compute the
required information (hopefully in an efficient way).
To understand this let us take a look at what happens when we compute
Size( a5 ). Not much happens. Size simply calls
a5.operations.Size( a5 ). a5.operations.Size is a function written
especially for permutation groups. It computes the size of a5 and
returns it. Then Size returns this value.
Actually Size does a little bit more than that. It first tests whether
a5 has the knowledge component a5.size. If this is the case, Size
simply returns that value. Otherwise it calls a5.operations.Size( a5 )
to compute the size. Size remembers the result in the knowledge
component a5.size so that it is readily available the next time Size(
a5 ) is called. The complete definition of Size is as follows.
gap> Size := function ( D )
> local size;
> if IsSet( D ) then
> size := Length( D );
> elif IsRec( D ) and IsBound( D.size ) then
> size := D.size;
> elif IsDomain( D ) then
> D.size := D.operations.Size( D );
> size := D.size;
> else
> Error( " must be a domain or a set" );
> fi;
> return size;
> end;;
Because functions such as Size only dispatch to the functions in the
operations record, they are called dispatcher functions. Almost all
functions that you call directly are dispatcher functions, and almost all
functions that do the hard work are components in an operations record.
Which function is called by a dispatcher obviously depends on the domain
and its operations record (that is the whole point of having an
operations record). In principle each domain could have its own Size
function. In practice however, this would require too many functions.
So different domains share the functions in their operations records,
usually all domains with the same representation share all their
operations record functions. For example all permutation groups share
the same Size function. Because this shared Size function must be
able to access the information in the domain record to compute the
correct result, the Size dispatcher function (and all other dispatchers
as well) pass the domain as first argument
In fact the domains not only have the same functions in their operations
record, they share the operations record. So for example all permutation
groups share a common operations record, which is called PermGroupOps.
This means that changing a function in the operations record for a domain
D in the following way D.operations.function := new-function;
will also change this function for all domains of the same type, even
those that do not yet exist at the moment of the assignment and will only
be constructed later. This is usually not desirable, since supposedly
new-function uses some special properties of the domain D to work
more efficiently. We suggest therefore that you first make a copy of the
operations record with D.operations := Copy( D.operations ); and
only afterwards do D.operations.function := new-function;.
If a programmer that implements a new domain D, a new type of groups
say, would have to write all functions applicable to D, this would
require a lot of effort. For example, there are about 120 functions
applicable to groups. Luckily many of those functions are independent of
the particular type of groups. For example the following function will
compute the commutator subgroup of any group, assuming that
TrivialSubgroup, Closure, and NormalClosure work. We say that this
function is generic.
gap> GroupOps.CommutatorSubgroup := function ( U, V )
> local C, u, v, c;
> C := TrivialSubgroup( U );
> for u in U.generators do
> for v in V.generators do
> c := Comm( u, v );
> if not c in C then
> C := Closure( C, c );
> fi;
> od;
> od;
> return NormalClosure( Closure( U, V ), C );
> end;;
So it should be possible to use this function for the new type of groups. The mechanism to do this is called inheritance. How it works is described in About Defining New Domains, but basically the programmer just copies the generic functions from the generic group operations record into the operations record for his new type of groups.
The generic functions are also called default functions, because they are used by default, unless the programmer overlaid them for the new type of groups.
There is another mechanism through which work can be simplified. It is
called delegation. Suppose that a generic function works for the new
type of groups, but that some special cases can be handled more
efficiently for the new type of groups. Then it is possible to handle
only those cases and delegate the general cases back to the generic
function. An example of this is the function that computes the orbit of
a point under a permutation group. If the point is an integer then the
generic algorithm can be improved by keeping a second list that remembers
which points have already been seen. The other cases (remember that
Orbit can also be used for other operations, e.g., the operation of a
permutation group on pairs of points or the operations on subgroups by
conjugation) are delegated back to the generic function. How this is
done can be seen in the following definition.
gap> PermGroupOps.Orbit := function ( G, d, opr )
> local orb, # orbit of d under G, result
> max, # largest point moved by the group G
> new, # boolean list indicating if a point is new
> gen, # one generator of the group G
> pnt, # one point in the orbit orb
> img; # image of pnt under gen
>
> # standard operation
> if opr = OnPoints and IsInt(d) then
>
> # get the largest point max moved by the group G
> max := 0;
> for gen in G.generators do
> if max < LargestMovedPointPerm(gen) then
> max := LargestMovedPointPerm(gen);
> fi;
> od;
>
> # handle fixpoints
> if not d in [1..max] then
> return [ d ];
> fi;
>
> # start with the singleton orbit
> orb := [ d ];
> new := BlistList( [1..max], [1..max] );
> new[d] := false;
>
> # loop over all points found
> for pnt in orb do
> for gen in G.generators do
> img := pnt ^ gen;
> if new[img] then
> Add( orb, img );
> new[img] := false;
> fi;
> od;
> od;
>
> # other operation, delegate back on default function
> else
> orb := GroupOps.Orbit( G, d, opr );
> fi;
>
> # return the orbit orb
> return orb;
> end;;
Inheritance and delegation allow the programmer to implement a new type of groups by merely specifying how those groups differ from generic groups. This is far less work than having to implement all possible functions (apart from the problem that in this case it is very likely that the programmer would forget some of the more exotic functions).
To make all this clearer let us look at an extended example to show you
how a computation in a domain may use default and special functions to
achieve its goal. Suppose you defined g, x, and y as follows.
gap> g := SymmetricGroup( 8 );;
gap> x := [ (2,7,4)(3,5), (1,2,6)(4,8) ];;
gap> y := [ (2,5,7)(4,6), (1,5)(3,8,7) ];;
Now you ask for an element of g that conjugates x to y, i.e., a
permutation on 8 points that takes (2,7,4)(3,5) to (2,5,7)(4,6) and
(1,2,6)(4,8) to (1,5)(3,8,7). This is done as follows (see
RepresentativeOperation and Other Operations).
gap> RepresentativeOperation( g, x, y, OnTuples );
(1,8)(2,7)(3,4,5,6)
Now lets look at what happens step for step. First
RepresentativeOperation is called. After checking the arguments it
calls the function g.operations.RepresentativeOperation, which is the
function SymmetricGroupOps.RepresentativeOperation, passing the
arguments g, x, y, and OnTuples.
SymmetricGroupOps.RepresentativeOperation handles a lot of cases
special, but the operation on tuples of permutations is not among them.
Therefore it delegates this problem to the function that it overlays,
which is PermGroupOps.RepresentativeOperation.
PermGroupOps.RepresentativeOperation also does not handle this special
case, and delegates the problem to the function that it overlays, which
is the default function called GroupOps.RepresentativeOperation.
GroupOps.RepresentativeOperation views this problem as a general tuples
problem, i.e., it does not care whether the points in the tuples are
integers or permutations, and decides to solve it one step at a time. So
first it looks for an element taking (2,7,4)(3,5) to (2,5,7)(4,6) by
calling RepresentativeOperation( g, (2,7,4)(3,5), (2,5,7)(4,6) ).
RepresentativeOperation calls g.operations.RepresentativeOperation
next, which is the function SymmetricGroupOps.RepresentativeOperation,
passing the arguments g, (2,7,4)(3,5), and (2,5,7)(4,6).
SymmetricGroupOps.RepresentativeOperation can handle this case. It
knows that g contains every permutation on 8 points, so it contains
(3,4,7,5,6), which obviously does what we want, namely it takes x[1]
to y[1]. We will call this element t.
Now GroupOps.RepresentativeOperation (see above) looks for an s in
the stabilizer of x[1] taking x[2] to y[2]^(t^-1), since then for
r=s*t we have x[1]^r = (x[1]^s)^t = x[1]^t = y[1] and also
x[2]^r = (x[2]^s)^t = (y[2]^(t^-1))^t = y[2]. So the next step
is to compute the stabilizer of x[1] in g. To do this it calls
Stabilizer( g, (2,7,4)(3,5) ).
Stabilizer calls g.operations.Stabilizer, which is
SymmetricGroupOps.Stabilizer, passing the arguments g and
(2,7,4)(3,5). SymmetricGroupOps.Stabilizer detects that the second
argument is a permutation, i.e., an element of the group, and calls
Centralizer( g, (2,7,4)(3,5) ). Centralizer calls the function
g.operations.Centralizer, which is SymmetricGroupOps.Centralizer,
again passing the arguments g, (2,7,4)(3,5).
SymmetricGroupOps.Centralizer again knows how centralizer in
symmetric groups look, and after looking at the permutation
(2,7,4)(3,5) sharply for a short while returns the centralizer as
Subgroup( g, [ (1,6), (6,8), (2,7,4), (3,5) ] ), which we will call
c. Note that c is of course not a symmetric group, therefore
SymmetricGroupOps.Subgroup gives it PermGroupOps as operations record
and not SymmetricGroupOps.
As explained above GroupOps.RepresentativeOperation needs an element of
c taking x[2] ((1,2,6)(4,8)) to y[2]^(t^-1) ((1,7)(4,6,8)).
So RepresentativeOperation( c, (1,2,6)(4,8), (1,7)(4,6,8) ) is called.
RepresentativeOperation in turn calls the function
c.operations.RepresentativeOperation, which is, since c is a
permutation group, the function PermGroupOps.RepresentativeOperation,
passing the arguments c, (1,2,6)(4,8), and (1,7)(4,6,8).
PermGroupOps.RepresentativeOperation detects that the points are
permutations and and performs a backtrack search through c. It finds
and returns (1,8)(2,4,7)(3,5), which we call s.
Then GroupOps.RepresentativeOperation returns r = s*t =
(1,8)(2,7)(3,6)(4,5), and we are done.
In this example you have seen how functions use the structure of their
domain to solve a problem most efficiently, for example
SymmetricGroupOps.RepresentativeOperation but also the backtrack search
in PermGroupOps.RepresentativeOperation, how they use other functions,
for example SymmetricGroupOps.Stabilizer called Centralizer, and how
they delegate cases which they can not handle more efficiently back to
the function they overlaid, for example
SymmetricGroupOps.RepresentativeOperation delegated to
PermGroupOps.RepresentativeOperation, which in turn delegated to to the
function GroupOps.RepresentativeOperation.
If you think this whole mechanism using dispatcher functions and the operations record is overly complex let us look at some of the alternatives. This is even more technical than the previous part of this section so you may want to skip the remainder of this section.
One alternative would be to let the dispatcher know about the various
types of domains, test which category a domain lies in, and dispatch to
an appropriate function. Then we would not need an operations record.
The dispatcher function CommutatorSubgroup would then look as follows.
Note this is not how CommutatorSubgroup is implemented in GAP.
CommutatorSubgroup := function ( G )
local C;
if IsAgGroup( G ) then
C := CommutatorSubgroupAgGroup( G );
elif IsMatGroup( G ) then
C := CommutatorSubgroupMatGroup( G );
elif IsPermGroup( G ) then
C := CommutatorSubgroupPermGroup( G );
elif IsFpGroup( G ) then
C := CommutatorSubgroupFpGroup( G );
elif IsFactorGroup( G ) then
C := CommutatorSubgroupFactorGroup( G );
elif IsDirectProduct( G ) then
C := CommutatorSubgroupDirectProduct( G );
elif IsDirectProductAgGroup( G ) then
C := CommutatorSubgroupDirectProductAgGroup( G );
elif IsSubdirectProduct( G ) then
C := CommutatorSubgroupSubdirectProduct( G );
elif IsSemidirectProduct( G ) then
C := CommutatorSubgroupSemidirectProduct( G );
elif IsWreathProduct( G ) then
C := CommutatorSubgroupWreathProduct( G );
elif IsGroup( G ) then
C := CommutatorSubgroupGroup( G );
else
Error(" must be a group");
fi;
return C;
end;
You already see one problem with this approach. The number of cases that the dispatcher functions would have to test is simply to large. It is even worse for set theoretic functions, because they would have to handle all different types of domains (currently about 30).
The other problem arises when a programmer implements a new domain. Then he would have to rewrite all dispatchers and add a new case to each. Also the probability that the programmer forgets one dispatcher is very high.
Another problem is that inheritance becomes more difficult. Instead of just copying one operations record the programmer would have to copy each function that should be inherited. Again the probability that he forgets one is very high.
Another alternative would be to do completely without dispatchers. In
this case there would be the functions CommutatorSugroupAgGroup,
CommutatorSubgroupPermGroup, etc., and it would be your responsibility
to call the right function. For example to compute the size of a
permutation group you would call SizePermGroup and to compute the size
of a coset you would call SizeCoset (or maybe even
SizeCosetPermGroup).
The most obvious problem with this approach is that it is much more cumbersome. You would always have to know what kind of domain you are working with and which function you would have to call.
Another problem is that writing generic functions would be impossible.
For example the above generic implementation of CommutatorSubgroup
could not work, because for a concrete group it would have to call
ClosurePermGroup or ClosureAgGroup etc.
If generic functions are impossible, inheritance and delegation can not be used. Thus for each type of domain all functions must be implemented. This is clearly a lot of work, more work than we are willing to do.
So we argue that our mechanism is the easiest possible that serves the following two goals. It is reasonably convenient for you to use. It allows us to implement a large (and ever increasing) number of different types of domains.
This may all sound a lot like object oriented programming to you. This is not surprising because we want to solve the same problems that object oriented programming tries to solve. Let us briefly discuss the similarities and differences to object oriented programming, taking C++ as an example (because it is probably the widest known object oriented programming language nowadays). This discussion is very technical and again you may want to skip the remainder of this section.
Let us first recall the problems that the GAP mechanism wants to handle.
For object oriented programming the problems are the same, though the names used are different. We talk about domains, object oriented programming talks about objects, and we talk about categories, object oriented programming talks about classes.
In GAP the first problem is solved by representing all domains using records. Actually because GAP does not perform strong static type checking each variable can hold objects of arbitrary type, so it would even be possible to represent some domains using lists or something else. But then, where would we put the operations record?
C++ does something similar. Objects are represented by struct-s or
pointers to structures. C++ then allows that a pointer to an object of a
base class actually holds a pointer to an object of a derived class.
In GAP the second problem is solved by the dispatchers and the operations record. The operations record of a given domain holds the methods that should be applied to that domain, and the dispatcher does nothing but call this method.
In C++ it is again very similar. The difference is that the dispatcher
only exists conceptually. If the compiler can already decide which
method will be executed by a given call to the dispatcher it directly
calls this function. Otherwise (for virtual functions that may be
overlaid in derived classes) it basically inlines the dispatcher. This
inlined code then dispatches through the so--called virtual method
table (vmt). Note that this virtual method table is the same as the
operations record, except that it is a table and not a record.
In GAP the third problem is solved by inheritance and delegation. To
inherit functions you simply copy them from the operations record of
domains of the old category to the operations record of domains of the
new category. Delegation to a method of a larger category is done by
calling super-category-operations-record.function
C++ also supports inheritance and delegation. If you derive a class from
a base class, you copy the methods from the base class to the derived
class. Again this copying is only done conceptually in C++. Delegation
is done by calling a qualified function base-class::function.
Now that we have seen the similarities, let us discuss the differences.
The first differences is that GAP is not an object oriented programming language. We only programmed the library in an object oriented way using very few features of the language (basically all we need is that GAP has no strong static type checking, that records can hold functions, and that records can grow dynamically). Following Stroustrup's convention we say that the GAP language only enables object oriented programming, but does not support it.
The second difference is that C++ adds a mechanism to support data
hiding. That means that fields of a struct can be private. Those
fields can only be accessed by the functions belonging to this class (and
friend functions). This is not possible in GAP. Every field of
every domain is accessible. This means that you can also modify those
fields, with probably catastrophic results.
The final difference has to do with the relation between categories and their domains and classes and their objects. In GAP a category is a set of domains, thus we say that a domain is an element of a category. In C++ (and most other object oriented programming languages) a class is a prototype for its objects, thus we say that an object is an instance of the class. We believe that GAP's relation better resembles the mathematical model.
In this section you have seen that domains are represented by domain records, and that you can therefore access all information that GAP has about a certain domain. The following sections in this chapter discuss how new domains can be created (see About Defining New Domains, and About Defining New Parametrized Domains) and how you can even define a new type of elements (see About Defining New Group Elements).
1.28 About Defining New Domains
In this section we will show how one can add a new domain to GAP. All domains are implemented in the library in this way. We will use the ring of Gaussian integers as our example.
Note that everything defined here is already in the library file
LIBNAME/"gaussian.g", so there is no need for you to type it in. You
may however like to make a copy of this file and modify it.
The elements of this domain are already available, because Gaussian
integers are just a special case of cyclotomic numbers. As is described
in chapter Cyclotomics E(4) is GAP's name for the complex root of
-1. So all Gaussian integers can be represented as a + b*E(4),
where a and b are ordinary integers.
As was already mentioned each domain is represented by a record. So we
create a record to represent the Gaussian integers, which we call
GaussianIntegers.
gap> GaussianIntegers := rec();;
The first components that this record must have are those that identify this record as a record denoting a ring domain. Those components are called the category components.
gap> GaussianIntegers.isDomain := true;;
gap> GaussianIntegers.isRing := true;;
The next components are those that uniquely identify this ring. For
rings this must be generators, zero, and one. Those components are
called the identification components of the domain record. We also
assign a name component. This name will be printed when the domain is
printed.
gap> GaussianIntegers.generators := [ 1, E(4) ];;
gap> GaussianIntegers.zero := 0;;
gap> GaussianIntegers.one := 1;;
gap> GaussianIntegers.name := "GaussianIntegers";;
Next we enter some components that represent knowledge that we have about
this domain. Those components are called the knowledge components. In
our example we know that the Gaussian integers form a infinite,
commutative, integral, Euclidean ring, which has an unique factorization
property, with the four units 1, -1, E(4), and -E(4).
gap> GaussianIntegers.size := "infinity";;
gap> GaussianIntegers.isFinite := false;;
gap> GaussianIntegers.isCommutativeRing := true;;
gap> GaussianIntegers.isIntegralRing := true;;
gap> GaussianIntegers.isUniqueFactorizationRing := true;;
gap> GaussianIntegers.isEuclideanRing := true;;
gap> GaussianIntegers.units := [1,-1,E(4),-E(4)];;
This was the easy part of this example. Now we have to add an
operations record to the domain record. This operations record
(GaussianIntegers.operations) shall contain functions that implement
all the functions mentioned in chapter Rings, e.g., DefaultRing,
IsCommutativeRing, Gcd, or QuotientRemainder.
Luckily we do not have to implement all this functions. The first class
of functions that we need not implement are those that can simply get the
result from the knowledge components. E.g., IsCommutativeRing looks
for the knowledge component isCommutativeRing, finds it and returns
this value. So GaussianIntegers.operations.IsCommutativeRing is never
called.
gap> IsCommutativeRing( GaussianIntegers );
true
gap> Units( GaussianIntegers );
[ 1, -1, E(4), -E(4) ]
The second class of functions that we need not implement are those for which there is a general algorithm that can be applied for all rings. For example once we can do a division with remainder (which we will have to implement) we can use the general Euclidean algorithm to compute the greatest common divisor of elements.
So the question is, how do we get those general functions into our
operations record. This is very simple, we just initialize the
operations record as a copy of the record RingOps, which contains all
those general functions. We say that GaussianIntegers.operations
inherits the general functions from RingOps.
gap> GaussianIntegersOps := OperationsRecord(
> "GaussianIntegersOps", RingOps );;
gap> GaussianIntegers.operations := GaussianIntegersOps;;
So now we have to add those functions whose result can not (easily) be
derived from the knowledge components and that we can not inherit from
RingOps.
The first such function is the membership test. This function must test
whether an object is an element of the domain GaussianIntegers.
IsCycInt(x) tests whether x is a cyclotomic integer and
NofCyc(x) returns the smallest n such that the cyclotomic x can
be written as a linear combination of powers of the primitive n-th root
of unity E(n). If NofCyc(x) returns 1, x is an ordinary
rational number.
gap> GaussianIntegersOps.\in := function ( x, GaussInt )
> return IsCycInt( x ) and (NofCyc( x ) = 1 or NofCyc( x ) = 4);
> end;;
Note that the second argument GaussInt is not used in the function.
Whenever this function is called, the second argument must be
GaussianIntegers, because GaussianIntegers is the only domain that
has this particular function in its operations record. This also happens
for most other functions that we will write. This argument can not be
dropped though, because there are other domains that share a common in
function, for example all permutation groups have the same in function.
If the operator in would not pass the second argument, this function
could not know for which permutation group it should perform the
membership test.
So now we can test whether a certain object is a Gaussian integer or not.
gap> E(4) in GaussianIntegers;
true
gap> 1/2 in GaussianIntegers;
false
gap> GaussianIntegers in GaussianIntegers;
false
Another function that is just as easy is the function Random that
should return a random Gaussian integer.
gap> GaussianIntegersOps.Random := function ( GaussInt )
> return Random( Integers ) + Random( Integers ) * E( 4 );
> end;;
Note that actually a Random function was inherited from RingOps. But
this function can not be used. It tries to construct the sorted list of
all elements of the domain and then picks a random element from that
list. Therefor this function is only applicable for finite domains, and
can not be used for GaussianIntegers. So we overlay this default
function by simply putting another function in the operations record.
Now we can already test whether a Gaussian integer is a unit or not.
This is because the default function inherited from RingOps tests
whether the knowledge component units is present, and it returns true
if the element is in that list and false otherwise.
gap> IsUnit( GaussianIntegers, E(4) );
true
gap> IsUnit( GaussianIntegers, 1 + E(4) );
false
Now we finally come to more interesting stuff. The function Quotient
should return the quotient of its two arguments x and y. If the
quotient does not exist in the ring (i.e., if it is a proper Gaussian
rational), it must return false. (Without this last requirement we
could do without the Quotient function and always simply use the /
operator.)
gap> GaussianIntegersOps.Quotient := function ( GaussInt, x, y )
> local q;
> q := x / y;
> if not IsCycInt( q ) then
> q := false;
> fi;
> return q;
> end;;
The next function is used to test if two elements are associate in the
ring of Gaussian integers. In fact we need not implement this because
the function that we inherit from RingOps will do fine. The following
function is a little bit faster though that the inherited one.
gap> GaussianIntegersOps.IsAssociated := function ( GaussInt, x, y )
> return x = y or x = -y or x = E(4)*y or x = -E(4)*y;
> end;;
We must however implement the function StandardAssociate. It should
return an associate that is in some way standard. That means, whenever
we apply StandardAssociate to two associated elements we must obtain
the same value. For Gaussian integers we return that associate that lies
in the first quadrant of the complex plane. That is, the result is that
associated element that has positive real part and nonnegative imaginary
part. 0 is its own standard associate of course. Note that this is a
generalization of the absolute value function, which is
StandardAssociate for the integers. The reason that we must implement
StandardAssociate is of course that there is no general way to compute
a standard associate for an arbitrary ring, there is not even a standard
way to define this!
gap> GaussianIntegersOps.StandardAssociate := function ( GaussInt, x )
> if IsRat(x) and 0 <= x then
> return x;
> elif IsRat(x) then
> return -x;
> elif 0 < COEFFSCYC(x)[1] and 0 <= COEFFSCYC(x)[2] then
> return x;
> elif COEFFSCYC(x)[1] <= 0 and 0 < COEFFSCYC(x)[2] then
> return - E(4) * x;
> elif COEFFSCYC(x)[1] < 0 and COEFFSCYC(x)[2] <= 0 then
> return - x;
> else
> return E(4) * x;
> fi;
> end;;
Note that COEFFSCYC is an internal function that returns the
coefficients of a Gaussian integer (actually of an arbitrary cyclotomic)
as a list.
Now we have implemented all functions that are necessary to view the Gaussian integers plainly as a ring. Of course there is not much we can do with such a plain ring, we can compute with its elements and can do a few things that are related to the group of units.
gap> Quotient( GaussianIntegers, 2, 1+E(4) );
1-E(4)
gap> Quotient( GaussianIntegers, 3, 1+E(4) );
false
gap> IsAssociated( GaussianIntegers, 1+E(4), 1-E(4) );
true
gap> StandardAssociate( GaussianIntegers, 3 - E(4) );
1+3*E(4)
The remaining functions are related to the fact that the Gaussian integers are an Euclidean ring (and thus also a unique factorization ring).
The first such function is EuclideanDegree. In our example the
Euclidean degree of a Gaussian integer is of course simply its norm.
Just as with StandardAssociate we must implement this function because
there is no general way to compute the Euclidean degree for an arbitrary
Euclidean ring. The function itself is again very simple. The Euclidean
degree of a Gaussian integer x is the product of x with its complex
conjugate, which is denoted in GAP by GaloisCyc( x, -1 ).
gap> GaussianIntegersOps.EuclideanDegree := function ( GaussInt, x )
> return x * GaloisCyc( x, -1 );
> end;;
Once we have defined the Euclidean degree we want to implement the
QuotientRemainder function that gives us the Euclidean quotient and
remainder of a division.
gap> GaussianIntegersOps.QuotientRemainder := function ( GaussInt, x, y )
> return [ RoundCyc( x/y ), x - RoundCyc( x/y ) * y ];
> end;;
Note that in the definition of QuotientRemainder we must use the
function RoundCyc, which views the Gaussian rational x/y as a
point in the complex plane and returns the point of the lattice spanned
by 1 and E(4) closest to the point x/y. If we would truncate
towards the origin instead (this is done by the function IntCyc) we
could not guarantee that the result of EuclideanRemainder always has
Euclidean degree less than the Euclidean degree of y as the following
example shows.
gap> x := 2 - E(4);; EuclideanDegree( GaussianIntegers, x );
5
gap> y := 2 + E(4);; EuclideanDegree( GaussianIntegers, y );
5
gap> q := x / y; q := IntCyc( q );
3/5-4/5*E(4)
0
gap> EuclideanDegree( GaussianIntegers, x - q * y );
5
Now that we have implemented the QuotientRemainder function we can
compute greatest common divisors in the ring of Gaussian integers. This
is because we have inherited from RingOps the general function Gcd
that computes the greatest common divisor using Euclid's algorithm,
which only uses QuotientRemainder (and StandardAssociate to return
the result in a normal form). Of course we can now also compute least
common multiples, because that only uses Gcd.
gap> Gcd( GaussianIntegers, 2, 5 - E(4) );
1+E(4)
gap> Lcm( GaussianIntegers, 2, 5 - E(4) );
6+4*E(4)
Since the Gaussian integers are a Euclidean ring they are also a unique factorization ring. The next two functions implement the necessary operations. The first is the test for primality. A rational integer is a prime in the ring of Gaussian integers if and only if it is congruent to 3 modulo 4 (the other rational integer primes split into two irreducibles), and a Gaussian integer that is not a rational integer is a prime if its norm is a rational integer prime.
gap> GaussianIntegersOps.IsPrime := function ( GaussInt, x )
> if IsInt( x ) then
> return x mod 4 = 3 and IsPrimeInt( x );
> else
> return IsPrimeInt( x * GaloisCyc( x, -1 ) );
> fi;
> end;;
The factorization is based on the same observation. We compute the
Euclidean degree of the number that we want to factor, and factor this
rational integer. Then for every rational integer prime that is
congruent to 3 modulo 4 we get one factor, and we split the other
rational integer primes using the function TwoSquares and test which
irreducible divides.
gap> GaussianIntegersOps.Factors := function ( GaussInt, x )
> local facs, # factors (result)
> prm, # prime factors of the norm
> tsq; # representation of prm as x^2 + y^2
>
> # handle trivial cases
> if x in [ 0, 1, -1, E(4), -E(4) ] then
> return [ x ];
> fi;
>
> # loop over all factors of the norm of x
> facs := [];
> for prm in Set( FactorsInt( EuclideanDegree( x ) ) ) do
>
> # p = 2 and primes p = 1 mod 4 split according to p = x^2+y^2
> if prm = 2 or prm mod 4 = 1 then
> tsq := TwoSquares( prm );
> while IsCycInt( x / (tsq[1]+tsq[2]*E(4)) ) do
> Add( facs, (tsq[1]+tsq[2]*E(4)) );
> x := x / (tsq[1]+tsq[2]*E(4));
> od;
> while IsCycInt( x / (tsq[2]+tsq[1]*E(4)) ) do
> Add( facs, (tsq[2]+tsq[1]*E(4)) );
> x := x / (tsq[2]+tsq[1]*E(4));
> od;
>
> # primes p = 3 mod 4 stay prime
> else
> while IsCycInt( x / prm ) do
> Add( facs, prm );
> x := x / prm;
> od;
> fi;
>
> od;
>
> # the first factor takes the unit
> facs[1] := x * facs[1];
>
> # return the result
> return facs;
> end;;
So now we can factorize numbers in the ring of Gaussian integers.
gap> Factors( GaussianIntegers, 10 );
[ -1-E(4), 1+E(4), 1+2*E(4), 2+E(4) ]
gap> Factors( GaussianIntegers, 103 );
[ 103 ]
Now we have written all the functions for the operations record that
implement the operations. We would like one more thing however. Namely
that we can simply write Gcd( 2, 5 - E(4) ) without having to specify
GaussianIntegers as first argument. Gcd and the other functions
should be clever enough to find out that the arguments are Gaussian
integers and call GaussianIntegers.operations.Gcd automatically.
To do this we must first understand what happens when Gcd is called
without a ring as first argument. For an example suppose that we have
called Gcd( 66, 123 ) (and want to compute the gcd over the integers).
First Gcd calls DefaultRing( [ 66, 123 ] ), to obtain a ring that
contains 66 and 123. DefaultRing then calls Domain( [ 66, 123 ] ) to
obtain a domain, which need not be a ring, that contains 66 and 123.
Domain is the only function in the whole GAP library that knows
about the various types of elements. So it looks at its argument and
decides to return the domain Integers (which is in fact already a ring,
but it could in principle also return Rationals). DefaultRing now
calls Integers.operations.DefaultRing( [ 66, 123 ] ) and expects a ring
in which the requested gcd computation can be performed.
Integers.operations.DefaultRing( [ 66, 123 ] ) also returns Integers.
So DefaultRing returns Integers to Gcd and Gcd finally calls
Integers.operations.Gcd( Integers, 66, 123 ).
So the first thing we must do is to tell Domain about Gaussian
integers. We do this by extending Domain with the two lines
elif ForAll( elms, IsGaussInt ) then
return GaussianIntegers;
so that it now looks as follows.
gap> Domain := function ( elms )
> local elm;
> if ForAll( elms, IsInt ) then
> return Integers;
> elif ForAll( elms, IsRat ) then
> return Rationals;
> elif ForAll( elms, IsFFE ) then
> return FiniteFieldElements;
> elif ForAll( elms, IsPerm ) then
> return Permutations;
> elif ForAll( elms, IsMat ) then
> return Matrices;
> elif ForAll( elms, IsWord ) then
> return Words;
> elif ForAll( elms, IsAgWord ) then
> return AgWords;
> elif ForAll( elms, IsGaussInt ) then
> return GaussianIntegers;
> elif ForAll( elms, IsCyc ) then
> return Cyclotomics;
> else
> for elm in elms do
> if IsRec(elm) and IsBound(elm.domain)
> and ForAll( elms, l -> l in elm.domain )
> then
> return elm.domain;
> fi;
> od;
> Error("sorry, the elements lie in no common domain");
> fi;
> end;;
Of course we must define a function IsGaussInt, otherwise this could
not possibly work. This function is similar to the membership test we
already defined above.
gap> IsGaussInt := function ( x )
> return IsCycInt( x ) and (NofCyc( x ) = 1 or NofCyc( x ) = 4);
> end;;
Then we must define a function DefaultRing for the Gaussian integers
that does nothing but return GaussianIntegers.
gap> GaussianIntegersOps.DefaultRing := function ( elms )
> return GaussianIntegers;
> end;;
Now we can call Gcd with two Gaussian integers without having to pass
GaussianIntegers as first argument.
gap> Gcd( 2, 5 - E(4) );
1+E(4)
Of course GAP can not read your mind. In the following example it
assumes that you want to factor 10 over the ring of integers, not over
the ring of Gaussian integers (because Integers is the default ring
containing 10). So if you want to factor a rational integer over the
ring of Gaussian integers you must pass GaussianIntegers as first
argument.
gap> Factors( 10 );
[ 2, 5 ]
gap> Factors( GaussianIntegers, 10 );
[ -1-E(4), 1+E(4), 1+2*E(4), 2+E(4) ]
This concludes our example. In the file LIBNAME/"gaussian.g" you
will also find the definition of the field of Gaussian rationals. It is
so similar to the above definition that there is no point in discussing
it here. The next section shows you what further considerations are
necessary when implementing a type of parametrized domains (demonstrated
by implementing full symmetric permutation groups). For further details
see chapter Gaussians for a description of the Gaussian integers and
rationals and chapter Rings for a list of all functions applicable to
rings.
1.29 About Defining New Parametrized Domains
In this section we will show you an example that is slightly more complex than the example in the previous section. Namely we will demonstrate how one can implement parametrized domains. As an example we will implement symmetric permutation groups. This works similar to the implementation of a single domain. Therefore we can be very brief. Of course you should have read the previous section.
Note that everything defined here is already in the file
GRPNAME/"permgrp.grp", so there is no need for you to type it in.
You may however like to make a copy of this file and modify it.
In the example of the previous section we simply had a variable
(GaussianIntegers), whose value was the domain. This can not work in
this example, because there is not one symmetric permutation group.
The solution is obvious. We simply define a function that takes the
degree and returns the symmetric permutation group of this degree (as a
domain).
gap> SymmetricPermGroup := function ( n )
> local G; # symmetric group on points, result
>
> # make the group generated by (1,n), (2,n), .., (n-1,n)
> G := Group( List( [1..n-1], i -> (i,n) ), () );
> G.degree := n;
>
> # give it the correct operations record
> G.operations := SymmetricPermGroupOps;
>
> # return the symmetric group
> return G;
> end;;
The key is of course to give the domains returned by SymmetricPermGroup
a new operations record. This operations record will hold functions that
are written especially for symmetric permutation groups. Note that all
symmetric groups created by SymmetricPermGroup share one operations
record.
Just as we inherited in the example in the previous section from the
operations record RingOps, here we can inherit from the operations
record PermGroupOps (after all, each symmetric permutation group is
also a permutation group).
gap> SymmetricPermGroupOps := Copy( PermGroupOps );
We will now overlay some of the functions in this operations record with new functions that make use of the fact that the domain is a full symmetric permutation group. The first function that does this is the membership test function.
gap> SymmetricPermGroupOps.\in := function ( g, G )
> return IsPerm( g )
> and ( g = ()
> or LargestMovedPointPerm( g ) <= G.degree);
> end;;
The most important knowledge for a permutation group is a base and a strong generating set with respect to that base. It is not important that you understand at this point what this is mathematically. The important point here is that such a strong generating set with respect to an appropriate base is used by many generic permutation group functions, most of which we inherit for symmetric permutation groups. Therefore it is important that we are able to compute a strong generating set as fast as possible. Luckily it is possible to simply write down such a strong generating set for a full symmetric group. This is done by the following function.
gap> SymmetricPermGroupOps.MakeStabChain := function ( G, base )
> local sgs, # strong generating system of G wrt. base
> last; # last point of the base
>
> # remove all unwanted points from the base
> base := Filtered( base, i -> i <= G.degree );
>
> # extend the base with those points not already in the base
> base := Concatenation( base, Difference( [1..G.degree], base ) );
>
> # take the last point
> last := base[ Length(base) ];
>
> # make the strong generating set
> sgs := List( [1..Length(base)-1], i -> ( base[i], last ) );
>
> # make the stabilizer chain
> MakeStabChainStrongGenerators( G, base, sgs );
> end;;
One of the things that are very easy for symmetric groups is the computation of centralizers of elements. The next function does this. Again it is not important that you understand this mathematically. The centralizer of an element g in the symmetric group is generated by the cycles c of g and an element x for each pair of cycles of g of the same length that maps one cycle to the other.
gap> SymmetricPermGroupOps.Centralizer := function ( G, g )
> local C, # centralizer of g in G, result
> sgs, # strong generating set of C
> gen, # one generator in sgs
> cycles, # cycles of g
> cycle, # one cycle from cycles
> lasts, # lasts[l] is the last cycle of length l
> last, # one cycle from lasts
> i; # loop variable
>
> # handle special case
> if IsPerm( g ) and g in G then
>
> # start with the empty strong generating system
> sgs := [];
>
> # compute the cycles and find for each length the last one
> cycles := Cycles( g, [1..G.degree] );
> lasts := [];
> for cycle in cycles do
> lasts[Length(cycle)] := cycle;
> od;
>
> # loop over the cycles
> for cycle in cycles do
>
> # add that cycle itself to the strong generators
> if Length( cycle ) <> 1 then
> gen := [1..G.degree];
> for i in [1..Length(cycle)-1] do
> gen[cycle[i]] := cycle[i+1];
> od;
> gen[cycle[Length(cycle)]] := cycle[1];
> gen := PermList( gen );
> Add( sgs, gen );
> fi;
>
> # and it can be mapped to the last cycle of this length
> if cycle <> lasts[ Length(cycle) ] then
> last := lasts[ Length(cycle) ];
> gen := [1..G.degree];
> for i in [1..Length(cycle)] do
> gen[cycle[i]] := last[i];
> gen[last[i]] := cycle[i];
> od;
> gen := PermList( gen );
> Add( sgs, gen );
> fi;
>
> od;
>
> # make the centralizer
> C := Subgroup( G, sgs );
>
> # make the stabilizer chain
> MakeStabChainStrongGenerators( C, [1..G.degree], sgs );
>
> # delegate general case
> else
> C := PermGroupOps.Centralizer( G, g );
> fi;
>
> # return the centralizer
> return C;
> end;;
Note that the definition C := Subgroup( G, sgs ); defines a subgroup
of a symmetric permutation group. But this subgroup is usually not a
full symmetric permutation group itself. Thus C must not have the
operations record SymmetricPermGroupOps, instead it should have the
operations record PermGroupOps. And indeed C will have this
operations record. This is because Subgroup calls
G.operations.Subgroup, and we inherited this function from
PermGroupOps.
Note also that we only handle one special case in the function above.
Namely the computation of a centralizer of a single element. This
function can also be called to compute the centralizer of a whole
subgroup. In this case SymmetricPermGroupOps.Centralizer simply
delegates the problem by calling PermGroupOps.Centralizer.
The next function computes the conjugacy classes of elements in a symmetric group. This is very easy, because two elements are conjugated in a symmetric group when they have the same cycle structure. Thus we can simply compute the partitions of the degree, and for each degree we get one conjugacy class.
gap> SymmetricPermGroupOps.ConjugacyClasses := function ( G )
> local classes, # conjugacy classes of G, result
> prt, # partition of G
> sum, # partial sum of the entries in prt
> rep, # representative of a conjugacy class of G
> i; # loop variable
>
> # loop over the partitions
> classes := [];
> for prt in Partitions( G.degree ) do
>
> # compute the representative of the conjugacy class
> rep := [2..G.degree];
> sum := 1;
> for i in prt do
> rep[sum+i-1] := sum;
> sum := sum + i;
> od;
> rep := PermList( rep );
>
> # add the new class to the list of classes
> Add( classes, ConjugacyClass( G, rep ) );
>
> od;
>
> # return the classes
> return classes;
> end;;
This concludes this example. You have seen that the implementation of a parametrized domain is not much more difficult than the implementation of a single domain. You have also seen how functions that overlay generic functions may delegate problems back to the generic function. The library file for symmetric permutation groups contain some more functions for symmetric permutation groups.
1.30 About Defining New Group Elements
In this section we will show how one can add a new type of group elements to GAP. A lot of group elements in GAP are implemented this way, for example elements of generic factor groups, or elements of generic direct products.
We will use prime residue classes modulo an integer as our example. They have the advantage that the arithmetic is very simple, so that we can concentrate on the implementation without being carried away by mathematical details.
Note that everything we define is already in the library in the file
LIBNAME/"numtheor.g", so there is no need for you to type it in. You
may however like to make a copy of this file and modify it.
We will represent residue classes by records. This is absolutely typical, all group elements not built into the GAP kernel are realized by records.
To distinguish records representing residue classes from other records we
require that residue class records have a component with the name
isResidueClass and the value true. We also require that they have a
component with the name isGroupElement and again the value true.
Those two components are called the tag components.
Next each residue class record must of course have components that tell
us which residue class this record represents. The component with the
name representative contains the smallest nonnegative element of the
residue class. The component with the name modulus contains the
modulus. Those two components are called the identifying components.
Finally each residue class record must have a component with the name
operations that contains an appropriate operations record (see below).
In this way we can make use of the possibility to define operations for
records (see Comparisons of Records and Operations for Records).
Below is an example of a residue class record.
r13mod43 := rec(
isGroupElement := true,
isResidueClass := true,
representative := 13,
modulus := 43,
domain := GroupElements,
operations := ResidueClassOps );
The first function that we have to write is very simple. Its only task
is to test whether an object is a residue class. It does this by testing
for the tag component isResidueClass.
gap> IsResidueClass := function ( obj )
> return IsRec( obj )
> and IsBound( obj.isResidueClass )
> and obj.isResidueClass;
> end;;
Our next function takes a representative and a modulus and constructs a new residue class. Again this is not very difficult.
gap> ResidueClass := function ( representative, modulus )
> local res;
> res := rec();
> res.isGroupElement := true;
> res.isResidueClass := true;
> res.representative := representative mod modulus;
> res.modulus := modulus;
> res.domain := GroupElements;
> res.operations := ResidueClassOps;
> return res;
> end;;
Now we have to define the operations record for residue classes.
Remember that this record contains a function for each binary operation,
which is called to evaluate such a binary operation (see Comparisons of
Records and Operations for Records). The operations =, <, *,
/, mod, ^, Comm, and Order are the ones that are applicable to
all group elements. The meaning of those operations for group elements
is described in Comparisons of Group Elements and Operations for Group
Elements.
Luckily we do not have to define everything. Instead we can inherit a
lot of those functions from generic group elements. For example, for all
group elements g/h should be equivalent to g*h^-1. So the
function for / could simply be function(g,h) return g*h^-1; end.
Note that this function can be applied to all group elements,
independently of their type, because all the dependencies are in * and
^.
The operations record GroupElementOps contains such functions that can
be used by all types of group elements. Note that there is no element
that has GroupElementsOps as its operations record. This is
impossible, because there is for example no generic method to multiply or
invert group elements. Thus GroupElementsOps is only used to inherit
general methods as is done below.
gap> ResidueClassOps := Copy( GroupElementOps );;
Note that the copy is necessary, otherwise the following assignments
would not only change ResidueClassOps but also GroupElementOps.
The first function we are implementing is the equality comparison. The
required operation is described simply enough. = should evaluate to
true if the operands are equal and false otherwise. Two residue
classes are of course equal if they have the same representative and the
same modulus. One complication is that when this function is called
either operand may not be a residue class. Of course at least one must
be a residue class otherwise this function would not have been called at
all.
gap> ResidueClassOps.\= := function ( l, r )
> local isEql;
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> isEql := l.representative = r.representative
> and l.modulus = r.modulus;
> else
> isEql := false;
> fi;
> else
> if IsResidueClass( r ) then
> isEql := false;
> else
> Error("panic, neither nor is a residue class");
> fi;
> fi;
> return isEql;
> end;;
Note that the quotes around the equal sign = are necessary, otherwise
it would not be taken as a record component name, as required, but as the
symbol for equality, which must not appear at this place.
Note that we do not have to implement a function for the inequality
operator <>, because it is in the GAP kernel implemented by the
equivalence l <> r is not l = r.
The next operation is the comparison. We define that one residue class is smaller than another residue class if either it has a smaller modulus or, if the moduli are equal, it has a smaller representative. We must also implement comparisons with other objects.
gap> ResidueClassOps.\< := function ( l, r )
> local isLess;
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> isLess := l.representative < r.representative
> or (l.representative = r.representative
> and l.modulus < r.modulus);
> else
> isLess := not IsInt( r ) and not IsRat( r )
> and not IsCyc( r ) and not IsPerm( r )
> and not IsWord( r ) and not IsAgWord( r );
> fi;
> else
> if IsResidueClass( r ) then
> isLess := IsInt( l ) or IsRat( l )
> or IsCyc( l ) or IsPerm( l )
> or IsWord( l ) or IsAgWord( l );
> else
> Error("panic, neither nor is a residue class");
> fi;
> fi;
> return isLess;
> end;;
The next operation that we must implement is the multiplication *.
This function is quite complex because it must handle several different
tasks. To make its implementation easier to understand we will start
with a very simple--minded one, which only multiplies residue classes,
and extend it in the following paragraphs.
gap> ResidueClassOps.\* := function ( l, r )
> local prd; # product of l and r, result
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> if l.modulus <> r.modulus then
> Error(" and must have the same modulus");
> fi;
> prd := ResidueClass(
> l.representative * r.representative,
> l.modulus );
> else
> Error("product of and must be defined");
> fi;
> else
> if IsResidueClass( r ) then
> Error("product of and must be defined");
> else
> Error("panic, neither nor is a residue class");
> fi;
> fi;
> return prd;
> end;;
This function correctly multiplies residue classes, but there are other products that must be implemented. First every group element can be multiplied with a list of group elements, and the result shall be the list of products (see Operations for Group Elements and Operations for Lists). In such a case the above function would only signal an error, which is not acceptable. Therefore we must extend this definition.
gap> ResidueClassOps.\* := function ( l, r )
> local prd; # product of l and r, result
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> if l.modulus <> r.modulus then
> Error( " and must have the same modulus" );
> fi;
> prd := ResidueClass(
> l.representative * r.representative,
> l.modulus );
> elif IsList( r ) then
> prd := List( r, x -> l * x );
> else
> Error("product of and must be defined");
> fi;
> elif IsList( l ) then
> if IsResidueClass( r ) then
> prd := List( l, x -> x * r );
> else
> Error("panic: neither nor is a residue class");
> fi;
> else
> if IsResidueClass( r ) then
> Error( "product of and must be defined" );
> else
> Error("panic, neither nor is a residue class");
> fi;
> fi;
> return prd;
> end;;
This function is almost complete. However it is also allowed to multiply
a group element with a subgroup and the result shall be a coset (see
RightCoset). The operations record of subgroups, which are of course
also represented by records (see Group Records), contains a function
that constructs such a coset. The problem is that in an expression like
subgroup * residue-class, this function is not called. This is
because the multiplication function in the operations record of the
right operand is called if both operands have such a function (see
Operations for Records). Now in the above case both operands have such
a function. The left operand subgroup has the operations record
GroupOps (or some refinement thereof), the right operand
residue-class has the operations record ResidueClassOps. Thus
ResidueClassOps.* is called. But it does not and also should not know
how to construct a coset. The solution is simple. The multiplication
function for residue classes detects this special case and simply calls
the multiplication function of the left operand.
gap> ResidueClassOps.\* := function ( l, r )
> local prd; # product of l and r, result
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> if l.modulus <> r.modulus then
> Error( " and must have the same modulus" );
> fi;
> prd := ResidueClass(
> l.representative * r.representative,
> l.modulus );
> elif IsList( r ) then
> prd := List( r, x -> l * x );
> else
> Error("product of and must be defined");
> fi;
> elif IsList( l ) then
> if IsResidueClass( r ) then
> prd := List( l, x -> x * r );
> else
> Error("panic: neither nor is a residue class");
> fi;
> else
> if IsResidueClass( r ) then
> if IsRec( l ) and IsBound( l.operations )
> and IsBound( l.operations.\* )
> and l.operations.\* <> ResidueClassOps.\*
> then
> prd := l.operations.\*( l, r );
> else
> Error("product of and must be defined");
> fi;
> else
> Error("panic, neither nor is a residue class");
> fi;
> fi;
> return prd;
> end;;
Now we are done with the multiplication.
Next is the powering operation ^. It is not very complicated. The
PowerMod function (see PowerMod) does most of what we need,
especially the inversion of elements with the Euclidean algorithm when
the exponent is negative. Note however, that the definition of
operations (see Operations for Group Elements) requires that the
conjugation is available as power of a residue class by another residue
class. This is of course very easy since residue classes form an abelian
group.
gap> ResidueClassOps.\^ := function ( l, r )
> local pow;
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> if l.modulus <> r.modulus then
> Error(" and must have the same modulus");
> fi;
> if GcdInt( r.representative, r.modulus ) <> 1 then
> Error(" must be invertable");
> fi;
> pow := l;
> elif IsInt( r ) then
> pow := ResidueClass(
> PowerMod( l.representative, r, l.modulus ),
> l.modulus );
> else
> Error("power of and must be defined");
> fi;
> else
> if IsResidueClass( r ) then
> Error("power of and must be defined");
> else
> Error("panic, neither nor is a residue class");
> fi;
> fi;
> return pow;
> end;;
The last function that we have to write is the printing function. This
is called to print a residue class. It prints the residue class in the
form ResidueClass( representative, modulus ). It is fairly typical
to print objects in such a form. This form has the advantage that it can
be read back, resulting in exactly the same element, yet it is very
concise.
gap> ResidueClassOps.Print := function ( r )
> Print("ResidueClass( ",r.representative,", ",r.modulus," )");
> end;;
Now we are done with the definition of residue classes as group elements. Try them. We can at this point actually create groups of such elements, and compute in them.
However, we are not yet satisfied. There are two problems with the code we have implemented so far. Different people have different opinions about which of those problems is the graver one, but hopefully all agree that we should try to attack those problems.
The first problem is that it is still possible to define objects via
Group (see Group) that are not actually groups.
gap> G := Group( ResidueClass(13,43), ResidueClass(13,41) );
Group( ResidueClass( 13, 43 ), ResidueClass( 13, 41 ) )
The other problem is that groups of residue classes constructed with the code we have implemented so far are not handled very efficiently. This is because the generic group algorithms are used, since we have not implemented anything else. For example to test whether a residue class lies in a residue class group, all elements of the residue class group are computed by a Dimino algorithm, and then it is tested whether the residue class is an element of this proper set.
To solve the first problem we must first understand what happens with the
above code if we create a group with Group( res1, res2... ).
Group tries to find a domain that contains all the elements res1,
res2, etc. It first calls Domain( [ res1, res2... ] ) (see
Domain). Domain looks at the residue classes and sees that they all
are records and that they all have a component with the name domain.
This is understood to be a domain in which the elements lie. And in fact
res1 in GroupElements is true, because GroupElements accepts all
records with tag isGroupElement. So Domain returns GroupElements.
Group then calls
GroupElements.operations.Group(GroupElements,[res1,res2...],id),
where id is the identity residue class, obtained by res1 ^ 0, and
returns the result.
GroupElementsOps.Group is the function that actually creates the group.
It does this by simply creating a record with its second argument as
generators list, its third argument as identity, and the generic
GroupOps as operations record. It ignores the first argument, which is
passed only because convention dictates that a dispatcher passes the
domain as first argument.
So to solve the first problem we must achieve that another function
instead of the generic function GroupElementsOps.Group is called. This
can be done by persuading Domain to return a different domain. And
this will happen if the residue classes hold this other domain in their
domain component.
The obvious choice for such a domain is the (yet to be written) domain
ResidueClasses. So ResidueClass must be slightly changed.
gap> ResidueClass := function ( representative, modulus )
> local res;
> res := rec();
> res.isGroupElement := true;
> res.isResidueClass := true;
> res.representative := representative mod modulus;
> res.modulus := modulus;
> res.domain := ResidueClasses;
> res.operations := ResidueClassOps;
> return res;
> end;;
The main purpose of the domain ResidueClasses is to construct groups,
so there is very little we have to do. And in fact most of that can be
inherited from GroupElements.
gap> ResidueClasses := Copy( GroupElements );;
gap> ResidueClasses.name := "ResidueClasses";;
gap> ResidueClassesOps := Copy( GroupElementsOps );;
gap> ResidueClasses.operations := ResidueClassesOps;;
So now we must implement ResidueClassesOps.Group, which should check
whether the passed elements do in fact form a group. After checking it
simply delegates to the generic function GroupElementsOps.Group to
create the group as before.
gap> ResidueClassesOps.Group := function ( ResidueClasses, gens, id )
> local g; # one generator from gens
> for g in gens do
> if g.modulus <> id.modulus then
> Error("the generators must all have the same modulus");
> fi;
> if GcdInt( g.representative, g.modulus ) <> 1 then
> Error("the generators must all be prime residue classes");
> fi;
> od;
> return GroupElementOps.Group( ResidueClasses, gens, id );
> end;;
This solves the first problem. To solve the second problem, i.e., to
make operations with residue class groups more efficient, we must extend
the function ResidueClassesOps.Group. It now enters a new operations
record into the group. It also puts the modulus into the group record,
so that it is easier to access.
gap> ResidueClassesOps.Group := function ( ResidueClasses, gens, id )
> local G, # group G, result
> gen; # one generator from gens
> for gen in gens do
> if gen.modulus <> id.modulus then
> Error("the generators must all have the same modulus");
> fi;
> if GcdInt( gen.representative, gen.modulus ) <> 1 then
> Error("the generators must all be prime residue classes");
> fi;
> od;
> G := GroupElementsOps.Group( ResidueClasses, gens, id );
> G.modulus := id.modulus;
> G.operations := ResidueClassGroupOps;
> return G;
> end;;
Of course now we must build such an operations record. Luckily we do not
have to implement all functions, because we can inherit a lot of
functions from GroupOps. This is done by copying GroupOps as we have
done before for ResidueClassOps and ResidueClassesOps.
gap> ResidueClassGroupOps := Copy( GroupOps );;
Now the first function that we must write is the Subgroup function to
ensure that not only groups constructed by Group have the correct
operations record, but also subgroups of those groups created by
Subgroup. As in Group we only check the arguments and then leave the
work to GroupOps.Subgroup.
gap> ResidueClassGroupOps.Subgroup := function ( G, gens )
> local S, # subgroup of G, result
> gen; # one generator from gens
> for gen in gens do
> if gen.modulus <> G.modulus then
> Error("the generators must all have the same modulus");
> fi;
> if GcdInt( gen.representative, gen.modulus ) <> 1 then
> Error("the generators must all be prime residue classes");
> fi;
> od;
> S := GroupOps.Subgroup( G, gens );
> S.modulus := G.modulus;
> S.operations := ResidueClassGroupOps;
> return S;
> end;;
The first function that we write especially for residue class groups is
SylowSubgroup. Since residue class groups are abelian we can compute a
Sylow subgroup of such a group by simply taking appropriate powers of the
generators.
gap> ResidueClassGroupOps.SylowSubgroup := function ( G, p )
> local S, # Sylow subgroup of G, result
> gen, # one generator of G
> ord, # order of gen
> gens; # generators of S
> gens := [];
> for gen in G.generators do
> ord := OrderMod( gen.representative, G.modulus );
> while ord mod p = 0 do ord := ord / p; od;
> Add( gens, gen ^ ord );
> od;
> S := Subgroup( Parent( G ), gens );
> return S;
> end;;
To allow the other functions that are applicable to residue class groups to work efficiently we now want to make use of the fact that residue class groups are direct products of cyclic groups and that we know what those factors are and how we can project onto those factors.
To do this we write ResidueClassGroupOps.MakeFactors that adds the
components facts, roots, sizes, and sgs to the group record G.
This information, detailed below, will enable other functions to work
efficiently with such groups. Creating such information is a fairly
typical thing, for example for permutation groups the corresponding
information is the stabilizer chain computed by MakeStabChain.
G.facts will be the list of prime power factors of G.modulus.
Actually this is a little bit more complicated, because the residue class
group modulo the largest power q of 2 that divides G.modulus need
not be cyclic. So if q is a multiple of 4, G.facts[1] will be 4,
corresponding to the projection of G into (Z / 4 Z)* (of size 2),
furthermore if q is a multiple of 8, G.facts[2] will be q,
corresponding to the projection of G into the subgroup generated by 5
in (Z / q Z)* (of size q/4).
G.roots will be a list of primitive roots, i.e., of generators of the
corresponding factors in G.facts. G.sizes will be a list of the
sizes of the corresponding factors in G.facts, i.e., G.sizes[i]
= Phi( G.facts[i] ). (If G.modulus is a multiple of 8,
G.roots[2] will be 5, and G.sizes[2] will be q/4.)
Now we can represent each element g of the group G by a list e,
called the exponent vector, of the length of G.facts, where
e[i] is the logarithm of g.representative mod G.facts[i]
with respect to G.roots[i]. The multiplication of elements of G
corresponds to the componentwise addition of their exponent vectors,
where we add modulo G.sizes[i] in the i-th component. (Again
special consideration are necessary if G.modulus is divisible by 8.)
Next we compute the exponent vectors of all generators of G, and
represent this information as a matrix. Then we bring this matrix into
upper triangular form, with an algorithm that is very much like the
ordinary Gaussian elimination, modified to account for the different
sizes of the components. This upper triangular matrix of exponent
vectors is the component G.sgs. This new matrix obviously still
contains the exponent vectors of a generating system of G, but a much
nicer one, which allows us to tackle problems one component at a time.
(It is not necessary that you fully check this, the important thing here
is not the mathematical side.)
gap> ResidueClassGroupOps.MakeFactors := function ( G )
> local p, q, # prime factor of modulus and largest power
> r, s, # two rows of the standard generating system
> g, # extended gcd of leading entries in r, s
> x, y, # two entries in r and s
> i, k, l; # loop variables
>
> # find the factors of the direct product
> G.facts := [];
> G.roots := [];
> G.sizes := [];
> for p in Set( Factors( G.modulus ) ) do
> q := p;
> while G.modulus mod (p*q) = 0 do q := p*q; od;
> if q mod 4 = 0 then
> Add( G.facts, 4 );
> Add( G.roots, 3 );
> Add( G.sizes, 2 );
> fi;
> if q mod 8 = 0 then
> Add( G.facts, q );
> Add( G.roots, 5 );
> Add( G.sizes, q/4 );
> fi;
> if p <> 2 then
> Add( G.facts, q );
> Add( G.roots, PrimitiveRootMod( q ) );
> Add( G.sizes, (p-1)*q/p );
> fi;
> od;
>
> # represent each generator in this factorization
> G.sgs := [];
> for k in [ 1 .. Length( G.generators ) ] do
> G.sgs[k] := [];
> for i in [ 1 .. Length( G.facts ) ] do
> if G.facts[i] mod 8 = 0 then
> if G.generators[k].representative mod 4 = 1 then
> G.sgs[k][i] := LogMod(
> G.generators[k].representative,
> G.roots[i], G.facts[i] );
> else
> G.sgs[k][i] := LogMod(
> -G.generators[k].representative,
> G.roots[i], G.facts[i] );
> fi;
> else
> G.sgs[k][i] := LogMod(
> G.generators[k].representative,
> G.roots[i], G.facts[i] );
> fi;
> od;
> od;
> for i in [ Length( G.sgs ) + 1 .. Length( G.facts ) ] do
> G.sgs[i] := 0 * G.facts;
> od;
>
> # bring this matrix to diagonal form
> for i in [ 1 .. Length( G.facts ) ] do
> r := G.sgs[i];
> for k in [ i+1 .. Length( G.sgs ) ] do
> s := G.sgs[k];
> g := Gcdex( r[i], s[i] );
> for l in [ i .. Length( r ) ] do
> x := r[l]; y := s[l];
> r[l] := (g.coeff1 * x + g.coeff2 * y) mod G.sizes[l];
> s[l] := (g.coeff3 * x + g.coeff4 * y) mod G.sizes[l];
> od;
> od;
> s := [];
> x := G.sizes[i] / GcdInt( G.sizes[i], r[i] );
> for l in [ 1 .. Length( r ) ] do
> s[l] := (x * r[l]) mod G.sizes[l];
> od;
> Add( G.sgs, s );
> od;
>
> end;;
With the information computed by MakeFactors it is now of course very
easy to compute the size of a residue class group. We just look at the
G.sgs, and multiply the orders of the leading exponents of the
nonzero exponent vectors.
gap> ResidueClassGroupOps.Size := function ( G )
> local s, # size of G, result
> i; # loop variable
> if not IsBound( G.facts ) then
> G.operations.MakeFactors( G );
> fi;
> s := 1;
> for i in [ 1 .. Length( G.facts ) ] do
> s := s * G.sizes[i] / GcdInt( G.sizes[i], G.sgs[i][i] );
> od;
> return s;
> end;;
The membership test is a little bit more complicated. First we test that
the first argument is really a residue class with the correct modulus.
Then we compute the exponent vector of this residue class and reduce this
exponent vector using the upper triangular matrix G.sgs.
gap> ResidueClassGroupOps.\in := function ( res, G )
> local s, # exponent vector of res
> g, # extended gcd
> x, y, # two entries in s and G.sgs[i]
> i, l; # loop variables
> if not IsResidueClass( res )
> or res.modulus <> G.modulus
> or GcdInt( res.representative, res.modulus ) <> 1
> then
> return false;
> fi;
> if not IsBound( G.facts ) then
> G.operations.MakeFactors( G );
> fi;
> s := [];
> for i in [ 1 .. Length( G.facts ) ] do
> if G.facts[i] mod 8 = 0 then
> if res.representative mod 4 = 1 then
> s[i] := LogMod( res.representative,
> G.roots[i], G.facts[i] );
> else
> s[i] := LogMod( -res.representative,
> G.roots[i], G.facts[i] );
> fi;
> else
> s[i] := LogMod( res.representative,
> G.roots[i], G.facts[i] );
> fi;
> od;
> for i in [ 1 .. Length( G.facts ) ] do
> if s[i] mod GcdInt( G.sizes[i], G.sgs[i][i] ) <> 0 then
> return false;
> fi;
> g := Gcdex( s[i], G.sgs[i][i] );
> for l in [ i .. Length( G.facts ) ] do
> x := s[l]; y := G.sgs[i][l];
> s[l] := (g.coeff3 * x + g.coeff4 * y) mod G.sizes[l];
> od;
> od;
> return true;
> end;;
We also add a function Random that works by creating a random exponent
as a random linear combination of the exponent vectors in G.sgs, and
converts this exponent vector to a residue class. (The main purpose of
this function is to allow you to create random test examples for the
other functions.)
gap> ResidueClassGroupOps.Random := function ( G )
> local s, # exponent vector of random element
> r, # vector of remainders in each factor
> i, k, l; # loop variables
> if not IsBound( G.facts ) then
> G.operations.MakeFactors( G );
> fi;
> s := 0 * G.facts;
> for i in [ 1 .. Length( G.facts ) ] do
> l := G.sizes[i] / GcdInt( G.sizes[i], G.sgs[i][i] );
> k := Random( [ 0 .. l-1 ] );
> for l in [ i .. Length( s ) ] do
> s[l] := (s[l] + k * G.sgs[i][l]) mod G.sizes[l];
> od;
> od;
> r := [];
> for l in [ 1 .. Length( s ) ] do
> r[l] := PowerModInt( G.roots[l], s[l], G.facts[l] );
> if G.facts[l] mod 8 = 0 and r[1] = 3 then
> r[l] := G.facts[l] - r[l];
> fi;
> od;
> return ResidueClass( ChineseRem( G.facts, r ), G.modulus );
> end;;
There are a lot more functions that would benefit from being implemented especially for residue class groups. We do not show them here, because the above functions already displayed how such functions can be written.
To round things up, we finally add a function that constructs the full
residue class group given a modulus m. This function is totally
independent of the implementation of residue classes and residue class
groups. It only has to find a (minimal) system of generators of the full
prime residue classes group, and to call Group to construct this group.
It also adds the information entry size to the group record, of course
with the value φ(n).
gap> PrimeResidueClassGroup := function ( m )
> local G, # group Z/mZ, result
> gens, # generators of G
> p, q, # prime and prime power dividing m
> r, # primitive root modulo q
> g; # is = r mod q and = 1 mod m/q
>
> # add generators for each prime power factor q of m
> gens := [];
> for p in Set( Factors( m ) ) do
> q := p;
> while m mod (q * p) = 0 do q := q * p; od;
>
> # (Z/4Z)^* = < 3 >
> if q = 4 then
> r := 3;
> g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
> Add( gens, ResidueClass( g, m ) );
>
> # (Z/8nZ)^* = < 5, -1 > is not cyclic
> elif q mod 8 = 0 then
> r := q-1;
> g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
> Add( gens, ResidueClass( g, m ) );
> r := 5;
> g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
> Add( gens, ResidueClass( g, m ) );
>
> # for odd q, (Z/qZ)^* is cyclic
> elif q <> 2 then
> r := PrimitiveRootMod( q );
> g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
> Add( gens, ResidueClass( g, m ) );
> fi;
>
> od;
>
> # return the group generated by gens
> G := Group( gens, ResidueClass( 1, m ) );
> G.size := Phi( n );
> return G;
> end;;
There is one more thing that we can learn from this example. Mathematically a residue class is not only a group element, but a set as well. We can reflect this in GAP by turning residue classes into domains (see Domains). Section About Defining New Domains gives an example of how to implement a new domain, so we will here only show the code with few comments.
First we must change the function that constructs a residue class, so that it enters the necessary fields to tag this record as a domain. It also adds the information that residue classes are infinite.
gap> ResidueClass := function ( representative, modulus )
> local res;
> res := rec();
> res.isGroupElement := true;
> res.isDomain := true;
> res.isResidueClass := true;
> res.representative := representative mod modulus;
> res.modulus := modulus;
> res.isFinite := false;
> res.size := "infinity";
> res.domain := ResidueClasses;
> res.operations := ResidueClassOps;
> return res;
> end;;
The initialization of the ResidueClassOps record must be changed too,
because now we want to inherit both from GroupElementsOps and
DomainOps. This is done by the function MergedRecord, which takes
two records and returns a new record that contains all components from
either record.
Note that the record returned by MergedRecord does not have those
components that appear in both arguments. This forces us to explicitly
write down from which record we want to inherit those functions, or to
define them anew. In our example the components common to
GroupElementOps and DomainOps are only the equality and ordering
functions, which we have to define anyhow. (This solution for the
problem of which definition to choose in the case of multiple inheritance
is also taken by C++.)
With this function definition we can now initialize ResidueClassOps.
gap> ResidueClassOps := MergedRecord( GroupElementOps, DomainOps );;
Now we add all functions to this record as described above.
Next we add a function to the operations record that tests whether a certain object is in a residue class.
gap> ResidueClassOps.\in := function ( element, class )
> if IsInt( element ) then
> return (element mod class.modulus = class.representative);
> else
> return false;
> fi;
> end;;
Finally we add a function to compute the intersection of two residue classes.
gap> ResidueClassOps.Intersection := function ( R, S )
> local I, # intersection of R and S, result
> gcd; # gcd of the moduli
> if IsResidueClass( R ) then
> if IsResidueClass( S ) then
> gcd := GcdInt( R.modulus, S.modulus );
> if R.representative mod gcd
> <> S.representative mod gcd
> then
> I := [];
> else
> I := ResidueClass(
> ChineseRem(
> [ R.modulus, S.modulus ] ,
> [ R.representative, S.representative ]),
> Lcm( R.modulus, S.modulus ) );
> fi;
> else
> I := DomainOps.Intersection( R, S );
> fi;
> else
> I := DomainOps.Intersection( R, S );
> fi;
> return I;
> end;;
There is one further thing that we have to do. When Group is called
with a single argument that is a domain, it assumes that you want to
create a new group such that there is a bijection between the original
domain and the new group. This is not what we want here. We want that
in this case we get the cyclic group that is generated by the single
residue class. (This overloading of Group is probably a mistake, but
so is the overloading of residue classes, which are both group elements
and domains.) The following definition solves this problem.
gap> ResidueClassOps.Group := function ( R )
> return ResidueClassesOps.Group( ResidueClasses, [R], R^0 );
> end;;
This concludes our example. There are however several further things
that you could do. One is to add functions for the quotient, the
modulus, etc. Another is to fix the functions so that they do not hang
if asked for the residue class group mod 1. Also you might try to
implement residue class rings analogous to residue class groups. Finally
it might be worthwhile to improve the speed of the multiplication of
prime residue classes. This can be done by doing some precomputation in
ResidueClass and adding some information to the residue class record
for prime residue classes (Mon85).
GAP 3.4.4