In this chapter, we will discuss two methods to calculate ordered signatures. The first one can be used for relative difference sets with forbidden set, while the second one does only work for ordinary difference sets.
The methods introduced here can only be used in some special cases.
Let D ⊆ G be a relative difference set with parameters (v/n,n,k,λ) and forbidden set N ⊆ G. Let U ≤ G be a normal subgroup such that U ⊆ N.
Then the coset signature (v_{1},...,v_{G:U}) of D has only the entries 1 (k times) and 0 (G:U−k times). And as in chapter RDS:Invariants for Difference Sets we have

where v_{ij}=D∩g_{i}g_{j}U. If the forbidden set N is a subgroup of G we have g_{i}U∩N is either 0 or equal to U∩N=U.
Let ϕ:G→ G/U be the canonical epimorphism. Then D^{ϕ} is a relative difference set in G/U with forbidden set N^{ϕ} and parameters (v/n,n/U,k,Uλ).
So the ordered signatures with respect to U are equivalent to the relative difference sets in G/U. Observe that we may not apply reduction in G/U using the full automorphismgroup of G/U but only the group induced by the stabiliser of U in the automorphism group of G. This is due to the fact that we use an ``induced'' notion of equivalence in G/U because we are interested in signatures and not primarily in difference sets in G/U.
NormalSgsForQuotientImages(
forbidden,
Gdata ) O
calculates all normal subgroups of Gdata.G which lie in forbidden. The returned value is a list of normal subgroups which define pairwise nonisomorphic factor groups.
DataForQuotientImage(
normal,
forbidden,
k,
lambda,
Gdata ) O
Let Gdata be the usual record for a group G. And let k and lambda be the parameters of the relative difference set we want to find. Let then forbidden be the forbidden set (as a group or a list of group elements or integers) and normal a normal subgroup of G which is contained in forbidden.
Then DataForQuotientImage
returns a record containing the record
.Gdata of the factor group G/U where the automorphism group is the one
induced by the stabiliser of normal in the automorphism group of G.
Furthermore the returned record contains the forbidden set .forbidden in
G/U and the new parameter .lambda for the difference set in G/U.
The data returned by DataForQuotientImage can be used to calculate difference sets in G/U in the way outlined in chapter RDS:A basic example. A quotient image of a relative difference set has a larger λ than the initial difference set. So MultiplicityInvariantLargeLambda can be used as in invariant here (see RDS:An invariant for large lambda)
After all difference sets are known, they must be converted into ordered signatures. This is done by the following function:
OrderedSigsFromQuotientImages(
fGroupData,
qimages,
forbidden,
normal,
Gdata ) O
Let Gdata be the usual record for a group G and normal a normal subgroup of G which lies in the forbidden set forbidden. Let then fGroupData be the record .Gdata describing G/normal as returned by DataForQuotientImage and qimages a set of difference sets in G/normal .
Then OrderedSigsFromQuotientImages
returns a record containing a list of
ordered signatures .orderedSigs and a list of cosets .cosets as well as
the factor group .fg defined by fGroupData and its full automorphism
group fgaut and the image of forbidden in .fg is returned as .Nfg.
MatchingFGDataForOrderedSigs(
forbidden,
Gdata,
Normalsgs,
fgdata ) O
Let fgdata be a list of records of the form returned by OrderedSigsFromQuotientImages and Normalsgs a list of normal subgroups of the group Gdata.G. Furthermore let forbidden be the forbidden set as a list of group elements or integers or a subgroup of Gdata.G.
Then MatchingFGDataForOrderedSigs
retruns all elements of fgdata which
match a normal subgroup of Normalsgs. The returned value is a record
containing the normal subgroup .normal from Normalsgs, the record
.sigdata from fgdata and a homomorphism .hom which maps Gdata.G
onto .sigdata.Gdata.G and takes forbidden to .sigdata.Nfg.
OrderedSigInvariant(
set,
data ) O
does the same as SigInvariant, but for ordered signatures. Here data has to be a list of records containing ordered signatures called .orderedSigs and cosets .cosets just as returned by OrderedSigsFromQuotientImages.
Assume we have calculated ordered signatures and have stored them in a record .osigs and a list normalSubgroupsData as returned by SignatureData containing the admissible signatures. A function for partitioning partial relative difference sets as required by ReducedStartsets can be defined as follows:
partitionfunc:=function(list) local si, osi; si:=SigInvariant(Union(list,[1]),normalSubgroupsData); osi:=OrderedSigInvariant(Union(list,[1]),[osigs]); if osi=fail or si=fail then return fail; else return si; fi; end;
This section contains some methods for ordered signatures in ordinary difference sets. Unfortunately, these methods are not as comfortable as those for unordered signatures. The reason for this is simply that I didn't have any time to tie them together to highlevel functions. If you need help here, don't hesitate to contact me.
Let R ⊆ G be a (partial) ordinary difference set (for definition see RDS:Introduction). Let U ≤ G be a normal subgroup and C={g_{1},..., g_{G:U}} be a system of representatives of G/U.
As in RDS:The Coset Signature we may define the coset signature of R relative to U.
Let U=g_{1},...,g_{G:U} be an enumeration of G/U. An ``admissible ordered signature'' for U is a tuple (v_{1},...,v_{G:U}) such that

holds where we index the v_{i} by elements of G/U, so v_{i}=v_{gi} and write v_{ij}=v_{gigj}. Observe that the third equation is a restriction on the ordering of the tuple (v_{1},...,v_{G:U}). If v is an admissible ordered signature, then the multiset of v is an unordered signature.
Getting ordered admissible signatures from unordered ones can be done by taking all permutations of the unordered signature and verifying the above equations. Obviously, this method isn't very satisfying (nevertheless, the methods for testing unordered signatures from section RDS:The Coset Signature do this to find out if there is an ordered signature at all. Except that they stop when they find an ordered signature).
For ordinary difference sets in extensions of semidirect products of cyclic groups, ordered signatures may be calculated a lot easier (see RoederDiss for details).
NormalSubgroupsForRep(
groupdata,
divisor ) O
Let groupdata be the output of PermutationRepForDiffsetCalculations and
divisor an integer. Then NormalSubgroupsForRep
calculates all normal
subgroups of groupdata.G such that the size of the factor group is divisible
by divisor and the factor group is a semidirect product of cyclic groups.
The output is a record consisting of
.alpha and .root may be used as input for OrderedSigs
OrderedSigs(
coeffSums,
absSum,
alpha,
root ) O
Let G be group which contains a normal subgroup of index s such that the coset signature for a difference set for this normal subgroup is coeffSums. Let N be a normal subgroup of G such that G/N is a semidirect product of cyclic group of orders s,q and i divides the order of G/N.
Then OrderedSigs(
coeffSums,
absSum,
alpha,
root)
calculates
all ordered signatures for N. Here root is a primitive qth root
of unity and alpha is a Galois automorphism of CS(q) with order
dividing s. absSum is the order of the difference set.
(i.e. order=k−λ).
OrderedSigs
is based on calculations using an sdimensional unitary
representation of G/N.
In this representation a subset of G induces a semicircular matrix.
The returned value is a list of lists stuples
The entries of the stuples are coefficients of numbers in
Z[root ] such that the semicircular matrix defined by these numbers
together with alpha meets necessary conditions for matrices induced
by difference sets.
To gain the algebraic numbers from the stuple tup, use
List(
tup,i>CoeffList2CyclotomicList(i,
root))
Each coeffSums tuple returned defines an ordered signature. The ordering of G/N is chosen to fit to the data returned by NormalSubgroupsForRep:
[a^{0},a^{1},...,a^{q−1}],[a^{0}b,a^{1}b,...,a^{q−1}b],...,[a^{0}b^{s−1},...,a^{q−1}b^{s−1}]
So for the calculation of ordered signatures, smaller ordered signatures coeffSums have to be known. But this is not so bad, as small signatures are easy to calculate. The following example shows an application.
gap> G:=SmallGroup(273,3); <pc group of size 273 with 3 generators> gap> Gdata:=PermutationRepForDiffsetCalculations(G);; gap> CosetSignatures(273,273/3,16); [ [ 3, 7, 7 ] ] gap> nsgs:=NormalSubgroupsForRep(Gdata,3); [ rec( Nsg := Group([ f2 ]), alpha := ANFAutomorphism( CF(13), 3 ), root := E(13), fgrp := Group([ f1, <identity> of ..., f2 ]), epi := [ f1, f2, f3 ] > [ f1, <identity> of ..., f2 ], a := f2, b := f1, int2pairtable := [ [ 1, 1 ], [ 1, 2 ], [ 1, 1 ], [ 2, 1 ], [ 1, 3 ], ... [ 8, 3 ], [ 11, 3 ], [ 5, 2 ], [ 11, 3 ] ] ), rec( Nsg := Group([ f3 ]), alpha := ANFAutomorphism( CF(7), 2 ), root := E(7), fgrp := Group([ f1, f2, <identity> of ... ]), epi := [ f1, f2, f3 ] > [ f1, f2, <identity> of ... ], a := f2, b := f1, int2pairtable := [ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 1, 1 ], [ 1, 3 ], ... [ 6, 3 ], [ 4, 3 ], [ 4, 2 ], [ 6, 3 ] ] ) ] gap> osigs:=OrderedSigs([3,7,7],16,nsgs[2].alpha,nsgs[2].root); [ [ [ 0, 0, 0, 1, 0, 1, 1 ], [ 0, 0, 1, 2, 2, 0, 2 ], [ 2, 2, 0, 2, 0, 0, 1 ] ], [ [ 0, 0, 0, 1, 0, 1, 1 ], [ 0, 1, 2, 2, 0, 2, 0 ], [ 2, 0, 0, 1, 2, 2, 0 ] ], ... [ [ 1, 1, 0, 1, 0, 0, 0 ], [ 2, 2, 1, 0, 0, 2, 0 ], [ 2, 1, 0, 0, 2, 0, 2 ] ] ] gap> Size(osigs); 98 gap> Set(osigs,g>SortedList(Concatenation(g))); [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2 ] ]
Note that the signature [3, 7, 7]
can be assumed to be ordered (by
passing to a suitable translate). So even if we are not interested in
ordered signatures, we have found out that there is only one admissible
unordered signature for this normal subgroup. To get this result using
TestedSignatures would have taken a very long time.
Of course, ordered signatures can also be used directly.
OrderedSignatureOfSet( set, normal_data ) O
takes a set set of integers (meant to be a partial difference set) and a list of records as returned by NormalSubgroupsForRep. The returned value is a list of lists which is the ordered signature of the partial difference set set and can be compared to the output of OrderedSigs
gap> OrderedSignatureOfSet([2,3,4,5],nsgs[2]); [ [ 1, 1, 1, 0, 0, 0, 0 ], [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0 ] ]
[Up] [Previous] [Next] [Index]
rds manual