# Small groups search

## Overview

Teaching:40 min

Exercises:15 minQuestions

Modular programming: putting functions together

How to check some conjecture for all groups of a given order?

Objectives

Using Small Groups Library

Designing a system of functions to fit together

In this section, we are interested in discovering some non-trivial groups having the property that the average order of their elements is an integer.

GAP distribution includes a number of data libraries (see an overview here). One of them is the Small Groups Library by Hans Ulrich Besche, Bettina Eick and Eamonn O’Brien.

This library provides various utilities to determine which information
is stored there and submit queries to search for groups with desired
properties. The key functions are `SmallGroup`

, `AllSmallGroups`

,
`NrSmallGroups`

, `SmallGroupsInformation`

and `IdGroup`

. For example:

```
gap> NrSmallGroups(64);
267
gap> SmallGroupsInformation(64);
There are 267 groups of order 64.
They are sorted by their ranks.
1 is cyclic.
2 - 54 have rank 2.
55 - 191 have rank 3.
192 - 259 have rank 4.
260 - 266 have rank 5.
267 is elementary abelian.
For the selection functions the values of the following attributes
are precomputed and stored:
IsAbelian, PClassPGroup, RankPGroup, FrattinifactorSize and
FrattinifactorId.
This size belongs to layer 2 of the SmallGroups library.
IdSmallGroup is available for this size.
gap> G:=SmallGroup(64,2);
<pc group of size 64 with 6 generators>
gap> AllSmallGroups(Size,64,NilpotencyClassOfGroup,5);
[ <pc group of size 64 with 6 generators>, <pc group of size 64 with 6 generators>,
<pc group of size 64 with 6 generators> ]
gap> List(last,IdGroup);
[ [ 64, 52 ], [ 64, 53 ], [ 64, 54 ] ]
```

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

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

Now try, for example

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

```
[ true, false ]
```

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

```
[ ]
```

## Modular programming begins here

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

`"YES"`

?

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

which is a special kind
of boolean variable in GAP.

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

For example,

```
TestOneOrderEasy(1);
```

```
[ 1, 1 ]
```

```
TestOneOrderEasy(24);
```

```
fail
```

`AllSmallGroups`

runs out of memory - what to do?

- Use iteration over
`[1..NrSmallGroups(n)]`

as shown in the function above- Use
`IdsOfAllSmallGroups`

which accepts same arguments as`AllSmallGroups`

but returns ids instead of groups.

Iterating over `[1..NrSmallGroups(n)]`

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

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

For example,

```
TestOneOrder(TestOneGroup,64);
```

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

:

```
64:267/267
fail
```

The next step is to integrate `TestOneOrder`

into a function which will test
all orders from 2 to `n`

and stop as soon as it finds an example of a
group with the average order of an element being an integer:

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

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

```
TestAllOrders(TestOneGroup,128);
```

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

To explore it further, we can get its `StructureDescription`

(see
here
for the explanation of the notation it uses):

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

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

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

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

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

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

```
List(AllSmallGroups(105),AvgOrdOfGroup);
```

```
[ 17, 301/5 ]
```

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

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

But now we call it with

```
TestRangeOfOrders(TestOneGroup,106,256);
```

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

## Don’t panic!

You can interrupt GAP by pressing Ctrl-C once. After that, GAP will enter a break loop, designated by the break prompt

`brk`

. You can leave it by typing`quit;`

(beware of pressing Ctrl-C twice within a second - that will terminate GAP session completely).

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

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

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

```
gap> TestRangeOfOrders(TestOneGroup,106,512);
```

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

The next function shows even further flexibility: it is variadic, i.e.
it may accept two or more arguments, the first two will be assigned to
variables `f`

and `n`

, and the rest will be available in the list `r`

(this is indicated by `...`

after `r`

). The first argument is the testing
function, the second is the order to check, and the third and the fourth
are the numbers of the first and last groups of this order that should be
checked. By default, the last two are equal to 1 and `NrSmallGroups(n)`

respectively. This function also shows how to validate the input and
produce user-friendly error messages in case of wrong arguments.

In addition, this function demonstrates how to use `Info`

messages that
may be switched on and off by setting appropriate `Info`

level. The need
we address here is to be able to switch the levels of verbosity of the
output without error-prone approach of walking through the code and commenting
`Print`

statements in and out. It is achieved by creating an info class:

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

```
InfoSmallGroupsSearch
```

Now instead of `Print("something");`

one could use
`Info( InfoSmallGroupsSearch, infolevel, "something" );`

where `infolevel`

is a positive integer specifying the level of verbosity.
This level could be changed to `n`

using the command
`SetInfoLevel( InfoSmallGroupsSearch, n);`

. See actual calls of `Info`

in
the code below:

```
TestOneOrderVariadic := function(f,n,r...)
local n1, n2, i;
if not Length(r) in [0..2] then
Error("The number of arguments must be 2,3 or 4\n" );
fi;
if not IsFunction( f ) then
Error("The first argument must be a function\n" );
fi;
if not IsPosInt( n ) then
Error("The second argument must be a positive integer\n" );
fi;
if IsBound(r[1]) then
n1:=r[1];
if not n1 in [1..NrSmallGroups(n)] then
Error("The 3rd argument, if present, must belong to ", [1..NrSmallGroups(n)], "\n" );
fi;
else
n1:=1;
fi;
if IsBound(r[2]) then
n2:=r[2];
if not n2 in [1..NrSmallGroups(n)] then
Error("The 4th argument, if present, must belong to ", [1..NrSmallGroups(n)], "\n" );
elif n2 < n1 then
Error("The 4th argument, if present, must be greater or equal to the 3rd \n" );
fi;
else
n2:=NrSmallGroups(n);
fi;
Info( InfoSmallGroupsSearch, 1,
"Checking groups ", n1, " ... ", n2, " of order ", n );
for i in [n1..n2] do
if InfoLevel( InfoSmallGroupsSearch ) > 1 then
Print(i, "/", NrSmallGroups(n), "\r");
fi;
if f(SmallGroup(n,i)) then
Info( InfoSmallGroupsSearch, 1,
"Discovered counterexample: SmallGroup( ", n, ", ", i, " )" );
return [n,i];
fi;
od;
Info( InfoSmallGroupsSearch, 1,
"Search completed - no counterexample discovered" );
return fail;
end;
```

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

:

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

Of course, this now introduces some complication for the test file,
which compares the actual output with the reference output. To resolve
this problem, we will decide to run the tests at info level 0 to suppress

all additional outputs. Because the tests may have been started in the
GAP session with a different info level, we will remember that info level
to restore it after the test:

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

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

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

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

How many groups of order not higher than 2000 may you be able to check, excluding

p-groups and those of order 1536?Can you find in the Small Groups Library another group (of order not equal to 1536) with this property?

## Key Points

Organise the code into functions.

Create small groups one by one instead of producing a huge list of them.

Using

`SmallGroupsInformation`

may help to reduce the search space.GAP is not a magic tool: theoretical knowledge may help much more than brute-force approach.