Guide to the GAP programs

in “DifSets.txt”

by

Ryan L. Kaliszewski & Ken W. Smith

Created in April 2006,

last modified June 2007.

We describe and demonstrate the programs in the DifSets.txt file. The DifSets.txt file is a compilation of a series of files constructed over four years to examine difference sets and elements of the integer group ring Z[G], where G is a finite group.

At the end of this paper we describe two other programs which use many of these programs to create an exhaustive search for difference sets (and similar objects) in finite groups.

DifSets.txt is a collection of functions that are useful for working with difference sets in GAP. The functions are broken up into ‘sections’ of related functions.

Section 1.1 – Translates

RightTranslates( group, sublist )

LeftTranslates( group, sublist )

ConjugateTranslates( group, sublist )

GroupMatrixRt( rep, group, elements )

If 'sublist' is a difference set in the group, then this procedure will return the design created by all translates of that difference set.

NOTE: Both the input and output of this procedure use a list of group elements of a fixed group.

RightTranslates( group, sublist )

The RightTranslates procedure was made to quickly create a list of right cosets of a given function. Given a group and a sublist of elements, the cosets are created from this information.

group: group is a group, such as might be created by the SmallGroup command.

sublist: sublist is a list containing group elements such as those returned by Elements(group).

LeftTranslates( group, sublist )

LeftTranslates is identical to RightTranslates except that it creates a list of left cosets.

ConjugateTranslates( group, sublist )

ConjugateTranslates is identical to the two previous procedures except that it returns the conjugate translates of the sublist.

GroupMatrixRt( rep, group, elements )

This procedure creates the Cayley table of a group, allowing you to replace group elements with representative symbols. Thus you could create a Cayley table for D4 (the dihedral group on eight elements) with representative symbols: R0, R90, R180, R270, H, V, D, and D’.

rep: This is the list of representative symbols. rep[i] will replace Elements(group)[i] in the Cayley table.

group: This is a group, such as might be created by the SmallGroup command.

elements: This is an ordered list of the elements of the group, commonly generated by Elements(group).

Section 1.2 – Incidence Matrix

PointsToInterval( design )

IncidenceMatrix( design )

CharacteristicFunction( group, subset )

PointsToInterval( design )

Sometimes you will have a design on a collection of symbols (perhaps group elements) and you’d like to have an equivalent design on integral values. PointsToInterval accepts a design (a list of lists) and creates an equivalent design on the integers [1..v].

design: This is a list of the blocks of your initial design. The type of data does not matter. The variable, v, given above is the number of unique points in your design.

IncidenceMatrix( design )

IncidenceMatrix accepts a design (a list of lists) and creates an incidence matrix. The incidence matrix is a matrix of 1’s and 0’s where the rows are the blocks and the columns represent the points. If point i is in block j, then

IncidenceMatrix(design)[j][i] = 1.

design: This is a list of the blocks of your initial design. The type of data does not matter. This procedure calls PointsToInterval before it performs its task. The variable, v, given above is the number of unique points in your design.

CharacteristicFunction( group, subset )

This procedure takes subset of a group and creates from it a (0,1)-list, that is a 1-row incidence matrix. If element i is in the subset, then

CharacteristicFunction( group, subset ) = 1.

group: This is a group, such as might be created by the SmallGroup command.

subset: subset is a list containing group elements such as those returned by Elements(group).

Section 1.3 – ListToInteger

IntegerToList( intIn, length, base )

ListToInteger( vector, length, base )

ListToMultiset( list )

MultisetToList( multiset, listlength )

IntegerToList( intIn, length, base )

IntegerToList accepts an integer, a length, and a base. It will then return a list with given length. Inside the list are the digits of the given integer represented with the given base (read in standard order). For example:

IntegerToList( 14, 4, 3 ) = [0,1,1,2]

IntegerToList( 6, 3, 2 ) = [1,1,0]

So, as you can see, this procedure can generate binary strings, ternary strings, etc.

intIn: This is the integer (in base 10) that you wish to translate to another base.

length: This is the length of the output list. If it is longer than the represented data, it will be padded with 0’s. If it is too short to hold the data, the procedure will truncate the output, producing the least significant values.

base: This is the base that the procedure should process the integer in.

ListToInteger( vector, base )

This procedure undoes the IntegerToList procedure. It takes a string (a list) of integral values that represent the digits in the base given. For example:

ListToInteger( [1,2,3,4], 10 ) = 1234

vector: This is the string (list of integers) in the given base.

base: This is the base that the procedure should process the vector in (e.g. 2 for binary, 3 for ternary, 8 for octal, 10 for decimal, 16 for hexadecimal).

NOTE: All output is in base 10.

ListToMultiset( list )

This procedure turns a list of positive integers [a1, a2, ...] into a set where the element 1 appears a1 times, a2 appears a2 times and so on. A (0,1)-list will be changed into the set of "support" for the 1s. For example:

ListToMultiset( [2, 4, 0, 1] ) = [ 1,1,2,2,2,2,4 ]

list: This is an integral list.

MultisetToList( multiset, listlength )

This procedure turns a multiset of positive integers [b1, b2, ...] into a list where the number of appearances of the element j in the multiset becomes the j-th coordinate of the list. For example:

MultisetToList( [ 1,3,3 ], 5 ) = [ 1,0,2,0,0 ]

MultisetToList( [ 1,2,4 ], 7 ) = [1,1,0,1,0,0,0]

multiset: multiset is a list of integers

listlength: This is the set that multiset is a subset of. Thus it tells the procedure what the maximal element of the set. If listlength isn't long enough to hold the elements of the multiset, the list will be truncated.

Section 2.1 – Convolution

ConvolutionTable_f( group, elements, func )

Convolution_AsList( CL, list1, list2 )

Convolution_AsMultiset( CL, multset1, multset2 )

ConvolutionTable_f( group, elements, func )

ConvolutionTable_f creates a convolution table for a group based on the function given. This is especially useful for difference sets if the function is defined by:

func := x-> x^-1;

group: This is a group, such as might be created by the SmallGroup command.

elements: This is an ordered list of the elements of the group, commonly generated by Elements(group).

func: This is the function used to create the convolution table. The function is used in the following fashion:

ConvolutionTable_f[i][j] = elements[i] * func( elements[j] )

NOTE: The output from ConvolutionTable_f is a matrix (a list of lists) with integral entries replacing the elements of the group in a manner similar to PointsToInterval.

Convolution_AsList( CL, list1, list2 )

This procedure takes a convolution table (created, say, by ConvolutionTable_f) and two lists, list1 and list2. It then uses the convolution list CL to quickly compute list1*list2 in Zg and returns that answer as a list.

CL: This is a convolution table

list1, list2: These are a list of group elements (see below)

Members of the integer group ring Zg here are represented as a list of coefficients, so for example, the set e[1]+2*e[3] in Z(C_5) will appear as [1,0,2,0,0].

Convolution_AsMultiset( CL, multset1, multset2 )

This procedure is identical to Convolution_AsList except that it takes multisets instead of lists. The procedure then uses the convolution list CL to quickly compute multset1*multset2 in Zg and returns that answer as a *multiset*.

Members of the integer group ring Zg here are represented as a multiset, for example the element e[1]+2*e[3] in Z(C_5) will appear as [1,3,3].

Section 2.2 – ImagesOfFixedSize

ImagesOfFixedSize( order, domain, im_order, range, printflag )

This section contains a procedure used to list homomorphic images of finite groups.

ImagesOfFixedSize( order, domain, im_order, range, printflag )

We look at groups of order 'order' with images of order 'im_order'.

We restrict our search to groups [order, j] where j is in 'domain'.

We restrict the image space to groups [im_order, i] where i is in 'range'.

The procedure returns a list, 'solution', containing all j where [order,j] has an image [size, i] where i in 'range'.

If printflag is 0 then no details are printed during the procedure run. Printflag values of 1 and 2 provide more details.

To receive an exhaustive list, merely set the domain (or range) to be empty. This will be interperated as making the search space as large as possible:

Section 2.3 – RightTransversalList

RightTransversalList( group, elements, normal )

TransversalListSpecific( group, elements, normal )

Expand( TL, d )

InverseExpand( TL, d )

RightTransversalList( group, elements, normal )

RightTransversalList takes a group, a sorted list of elements of the group, a normal subgroup, and returns a list of cosets of the normal subgroup in the group. The elements of the cosets are positive integers; if the integer i0 is listed then e[i0] is in that coset.

TransversalListSpecific( group, elements, normal )

TransversalListSpecific takes a group, a sorted list of elements of the group, a normal subgroup, and returns a list of cosets of the normal subgroup in the group. The elements of the cosets are positive integers; if the integer i0 is listed then e[i0] is in that coset.

The program has been written so that the elements of the factor group are specifically tied to the elements of a group in GAP's small group library.

Expand( TL, d )

This procedure takes, TL, a list of lists, and a list d, viewed as a function on TL, and expands it to a list of lists which is constant across the inside lists and when restricted to TL, is consistent with d.

For example, if TL = [ [1,2],[3,4], [5,6] ] and d = [ x,y,z ] then the output is:

[ [x,x], [y,y], [z,z] ]. This is useful when given an element d in Z(g/N) and expanding it in Zg.

InverseExpand( TL, d )

This procedure reverses Expand( TL, d ). It does not check for errors; if two elements of the same coset are assigned a different value, the value assigned to the coset is simply the value of the first element found in its list.

Section 2.4 – Subgroup Chains

SubgroupIncidenceMatrix( order, group_id )

MaxChains( mat )

WARNING! MaxChains has not been thoroughly tested!

SubgroupIncidenceMatrix( order, group_id )

SubgroupIncidenceMatrix creates the poset incidence matrix of the lattice of normal subgroups of the group SmallGroup( order, group_id ).

MaxChains( mat )

MaxChains inputs the incidence matrix of a poset and returns a list of all the maximal chains.

This matrix must be a (0,1) matrix of a poset. (In particular, there cannot be ones on the diagonal.) A matrix created by SubgroupIncidenceMatrix is ideal, here.

Section 2.5 – Partition Functions

PartitionRep( partition )

IndexToRep( partition )

QuotientGroupConvolution( CL, partition )

MapRefinement( partition, refinement )

PartitionRep( partition )

PartitionRep takes a partition on [1..v] and creates a many-to-one map from [1..v] into [1..v] where an element x is mapped to its "representative", the first element in the partition containing x.

The range of this function is returned, as a list.

IndexToRep( partition )

IndexToRep takes a partition on [1..v] and creates a many-to-one map from [1..v] into [1..v] where an element of the i-th partition is mapped to i. (i is the "index" of the partition.

The range of this function is returned, as a list.

QuotientGroupConvolution( CL, partition )

QuotientGroupConvolution takes a partition on [1..v] and a convolution table CL on [1..v] and creates a smaller convolution table on just the representatives (first element of each class) of the partition.

The output is a Cayley table with elements which are representatives; the elements are integers but will not necessarily be 1, 2, 3, ...

If the table CL is the Cayley table of a group G and the partition is the cosets of a normal subgroup N, then the output is a Cayley table for the group G/N.

MapRefinement( partition, refinement )

MapRefinement takes a partition on [1..v] and a refinement of it (another partition on [1..v] with the property that every class of this partition is a subclass of the original.) The output is a list of lists. In the output, each class in the original partition has been replaced by a list of indices corresponding to the classes of the refinement which belong to that partition.

For example, if the output is [[1,3,5], [2,4]] then the original partition had two classes. The first class is the union of classes 1, 3 and 5 of the refinement. The second class (of the original partition) is the union of the second and fourth classes of the refinement.

Section 2.6 - Automorphisms

MaxValueOnSets( right_reg, aut_img, subset )

MaxValueOnTuples( right_reg, aut_img, subset )

For the functions in this section, the definitions of the parameters are given as follows (where group is a group and elements is a list of the elements of the group).

right_reg := Image(ActionHomomorphism( group, elements, OnRight ));

aut_grp := AutomorphismGroup( group );

aut_img := Action( aut_grp, elements );

MaxValueOnSets( right_reg, aut_img, subset )

This procedure takes right_reg and aut_img (defined above), and an integral set representing a subset of the group. It then gives the element which is lexicographically least representative in the equivalence class of the subset.

(Equivalence here involves translation and automorphisms.)

‘subset’ is assumed to be a set, such as a difference set, with no repeated elements.

MaxValueOnTuples( right_reg, aut_img, subset )

This procedure takes right_reg and aut_img (defined above), and a multiset representing a subset of the group. It then gives the element which is lexicographically least representative in the equivalence class of the subset.

(Equivalence here involves translation and automorphisms.)

‘subset’ is assumed to be a multiset

EquivalenceClass( right_reg, aut_img, subset )

This procedure takes right_reg and aut_img (defined above) and then returns the entire equivalence class, along with the element which is lexicographically least representative in the equivalence class of d1.

(Equivalence here involves translation and automorphisms.)

‘subset’ is assumed to be a multiset

Section 3.1 - DifferenceSets

Verify( parameters, group_id, difset )

IncidenceMatrix_Parameters( parameters, group_id, difset )

MultiplierGroup( parameters, group_id, difset)

Verify( [v,k,lambda], group_id, difset )

This procedure takes a group ring element 'difset' with parameters [v,k,lambda], in the group SmallGroup(v,group_id) and verifies that D*D^(-1) only has two values on group elements.

The group ring element 'difset' is given as a list of positive integers {i : e[i] is in the difference set}.

IncidenceMatrix_Parameters( [v,k,lambda], group_id, difset )

This procedure takes a group ring element 'difset' with parameters [v,k,lambda], in the group SmallGroup(v,group_id) and constructs the incidence matrix of the design of right translates.

The group ring element 'difset' is given as a list of positive integers {i : e[i] is in the difference set}.

MultiplierGroup( [v,k,lambda], group_id, difset )

This procedure takes a group ring element 'difset' with parameters [v,k,lambda], in the group SmallGroup(v,group_id) and computes the multiplier group of the difference set. (The multiplier group is the set of automorphisms of the group which map 'difset' to a right translate.)

The group ring element 'difset' is given as a list of positive integers {i : e[i] is in the difference set}.