7 Ordered Signatures

calculates all normal subgroups of Gdata.G which lie in forbidden. The returned value is a list of normal subgroups which define pairwise non-isomorphic factor groups.

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:

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.

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.

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;

7.2 Ordered signatures using representations

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 high-level functions. If you need help here, don't hesitate to contact me.

7.3 Definition

Let R ⊆ G be a (partial) ordinary difference set (for definition see RDS:Introduction). Let U ≤ G be a normal subgroup and C={g₁,..., 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₁,...,g_|G:U| be an enumeration of G/U. An ``admissible ordered signature'' for U is a tuple (v₁,...,v_|G:U|) such that

∑ vi=k ∑ vi2=λ(|U|−1)+k ∑ j  vj vij = λ(|U|−1) for  gi ∉ U

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₁,...,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).

7.4 Methods for calculating ordered signatures

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

1.

a normal subgroup .Nsg of G

2.

the factor group .fgrp:=G/Nsg

3.

the epimorphism .epi from G to .fgrp

4.

a root of unity .root

5.

a galois automorphism .alpha

6.+7.

generators of the factor group G/.Nsg named .a and .b such that .a is normalized by .b.

8

a list .int2pairtable such that the i^th entry is the pair [m,n] with that Glist[i]^epi=a^(m-1)*b^(n-1)

.alpha and .root may be used as input for OrderedSigs

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 q-th 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 s-dimensional unitary representation of G/N. In this representation a subset of G induces a semi-circular matrix. The returned value is a list of lists s-tuples The entries of the s-tuples are coefficients of numbers in Z[root ] such that the semi-circular matrix defined by these numbers together with alpha meets necessary conditions for matrices induced by difference sets. To gain the algebraic numbers from the s-tuple 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⁰,a¹,...,a^q−1],[a⁰b,a¹b,...,a^q−1b],...,[a⁰b^s−1,...,a^q−1b^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.

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]