\Chapter{Ordered Signatures} 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. %%%%%%%%%%%%%%%%%%%%%% \Section{Ordered signatures by quotient images} Let $D\subseteq G$ be a relative difference set with parameters $(v/n,n,k,\lambda)$ and forbidden set $N\subseteq G$. Let $U\leq G$ be a normal subgroup such that $U\subseteq N$. Then the coset signature $(v_1,\dots,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 $$ \sum_j v_j v_{ij}= \lambda(|U|-|g_iU \cap N|){\quad\rm for }\ g_i\not\in U $$ where $v_{ij}=|D\cap g_ig_jU|$. If the forbidden set $N$ is a subgroup of $G$ we have $|g_iU\cap N|$ is either $0$ or equal to $|U\cap N|=|U|$. Let $\phi\colon G\to G/U$ be the canonical epimorphism. Then $D^\phi$ is a relative difference set in $G/U$ with forbidden set $N^\phi$ and parameters $(v/n,n/|U|,k,|U|\lambda)$. 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$. \Declaration{NormalSgsForQuotientImages} \Declaration{DataForQuotientImage} 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 $\lambda$ 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: \Declaration{OrderedSigsFromQuotientImages} \Declaration{MatchingFGDataForOrderedSigs} \Declaration{OrderedSigInvariant} 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: \begintt 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; \endtt %%%%%%%%%%%%%%%%%%%%%% \Section{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. %%%%%%%%%%%%%%%%%%%%%%%%% \Section{Definition} Let $R \subseteq G$ be a (partial) ordinary difference set (for definition see "RDS:Introduction"). Let $U\leq G$ be a normal subgroup and $C=\{g_1,\dots, 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,\dots,g_{|G:U|}$ be an enumeration of $G/U$. An ``admissible ordered signature'' for $U$ is a tuple $(v_1,\dots,v_{|G:U|})$ such that $$ \matrix{ \sum v_i=k\cr \sum v_i^2=\lambda(|U|-1)+k\cr \sum_j v_j v_{ij}= \lambda(|U|-1)&{\rm for }\ g_i\not\in U} $$ holds where we index the $v_i$ by elements of $G/U$, so $v_i=v_{g_i}$ and write $v_{ij}=v_{g_ig_j}$. Observe that the third equation is a restriction on the ordering of the tuple $(v_1,\dots,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 \cite{RoederDiss} for details). %%%%%%%%%%%%%%%%%%%%%%%%% \Section{Methods for calculating ordered signatures} \Declaration{NormalSubgroupsForRep} \Declaration{OrderedSigs} 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. \begintt 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 ] ] \endtt 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. \Declaration{OrderedSignatureOfSet} \beginexample 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 ] ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E