<html><head><title>[RDS] 7 Ordered Signatures</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP006.htm">Previous</a>] [<a href ="CHAP008.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>7 Ordered Signatures</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP007.htm#SECT001">Ordered signatures by quotient images</a>
<li> <A HREF="CHAP007.htm#SECT002">Ordered signatures using representations</a>
<li> <A HREF="CHAP007.htm#SECT003">Definition</a>
<li> <A HREF="CHAP007.htm#SECT004">Methods for calculating ordered signatures</a>
</ol><p>
<p>
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.
<p>
The methods introduced here can only be used in some special
cases.
<p>
<p>
<h2><a name="SECT001">7.1 Ordered signatures by quotient images</a></h2>
<p><p>
Let <var>DsubseteqG</var> be a relative difference set with parameters
<var>(v/n,n,k,lambda)</var> and forbidden set <var>NsubseteqG</var>. Let <var>UleqG</var> be
a normal subgroup such that <var>UsubseteqN</var>.
<p>
Then the coset signature <var>(v<sub>1</sub>,...,v<sub>|G:U|</sub>)</var> of <var>D</var> has only the
entries <var>1</var> (<var>k</var>- times) and <var>0</var> (<var>|G:U|-k</var>- times). And as in chapter
<a href="../../rds/htm/CHAP005.htm">RDS:Invariants for Difference Sets</a> we have
<p>
<p><var>
sum<sub>j</sub> v<sub>j</sub> v<sub>ij</sub>=
lambda(|U|-|g<sub>i</sub>U capN|) for g<sub>i</sub>notinU
<p></var>
<p>
where <var>v<sub>ij</sub>=|Dcapg<sub>i</sub>g<sub>j</sub>U|</var>. If the forbidden set <var>N</var> is a
subgroup of <var>G</var> we have <var>|g<sub>i</sub>UcapN|</var> is either <var>0</var> or equal to
<var>|UcapN|=|U|</var>.
<p>
Let <var>phicolonGtoG/U</var> be the canonical epimorphism. Then <var>D^phi</var>
is a relative difference set in <var>G/U</var> with forbidden set <var>N^phi</var> and
parameters <var>(v/n,n/|U|,k,|U|lambda)</var>.
<p>
So the ordered signatures with respect to <var>U</var> are equivalent to the
relative difference sets in <var>G/U</var>. Observe that we may not apply
reduction in <var>G/U</var> using the full automorphismgroup of <var>G/U</var> but only
the group induced by the stabiliser of <var>U</var> in the automorphism group
of <var>G</var>. This is due to the fact that we use an ``induced'' notion of
equivalence in <var>G/U</var> because we are interested in signatures and not
primarily in difference sets in <var>G/U</var>.
<p>
<a name = "SSEC001.1"></a>
<li><code>NormalSgsForQuotientImages( </code><var>forbidden</var><code>, </code><var>Gdata</var><code> ) O</code>
<p>
calculates all normal subgroups of <var>Gdata.G</var> which lie in <var>forbidden</var>.
The returned value is a list of normal subgroups which define pairwise
non-isomorphic factor groups.
<p>
<a name = "SSEC001.2"></a>
<li><code>DataForQuotientImage( </code><var>normal</var><code>, </code><var>forbidden</var><code>, </code><var>k</var><code>, </code><var>lambda</var><code>, </code><var>Gdata</var><code> ) O</code>
<p>
Let <var>Gdata</var> be the usual record for a group <var>G</var>. And let <var>k</var> and <var>lambda</var>
be the parameters of the relative difference set we want to find.
Let then <var>forbidden</var> be the forbidden set (as a group or a list of group
elements or integers) and <var>normal</var> a normal subgroup of <var>G</var> which is
contained in <var>forbidden</var>.
<p>
Then <code>DataForQuotientImage</code> returns a record containing the record
<var>.Gdata</var> of the factor group <var>G/U</var> where the automorphism group is the one
induced by the stabiliser of <var>normal</var> in the automorphism group of <var>G</var>.
Furthermore the returned record contains the forbidden set <var>.forbidden</var> in
<var>G/U</var> and the new parameter <var>.lambda</var> for the difference set in <var>G/U</var>.
<p>
The data returned by <a href="CHAP007.htm#SSEC001.2">DataForQuotientImage</a> can be used to calculate
difference sets in <var>G/U</var> in the way outlined in chapter <a href="../../rds/htm/CHAP003.htm">RDS:A basic example</a>. A quotient image of a relative difference set has a larger
<var>lambda</var> than the initial difference set. So
<a href="CHAP005.htm#SSEC002.1">MultiplicityInvariantLargeLambda</a> can be used as in invariant here
(see <a href="../../rds/htm/CHAP005.htm#SECT002">RDS:An invariant for large lambda</a>)
<p>
After all difference sets are known, they must be converted
into ordered signatures. This is done by the following function:
<p>
<a name = "SSEC001.3"></a>
<li><code>OrderedSigsFromQuotientImages( </code><var>fGroupData</var><code>, </code><var>qimages</var><code>, </code><var>forbidden</var><code>, </code><var>normal</var><code>, </code><var>Gdata</var><code> ) O</code>
<p>
Let <var>Gdata</var> be the usual record for a group <var>G</var> and <var>normal</var> a normal
subgroup of <var>G</var> which lies in the forbidden set <var>forbidden</var>.
Let then <var>fGroupData</var> be the record <var>.Gdata</var> describing <var>G/<var>normal</var></var> as
returned by <a href="CHAP007.htm#SSEC001.2">DataForQuotientImage</a> and <var>qimages</var> a set of difference sets
in <var>G/<var>normal</var></var>.
<p>
Then <code>OrderedSigsFromQuotientImages</code> returns a record containing a list of
ordered signatures <var>.orderedSigs</var> and a list of cosets <var>.cosets</var> as well as
the factor group <var>.fg</var> defined by <var>fGroupData</var> and its full automorphism
group <var>fgaut</var> and the image of <var>forbidden</var> in <var>.fg</var> is returned as <var>.Nfg</var>.
<p>
<a name = "SSEC001.4"></a>
<li><code>MatchingFGDataForOrderedSigs( </code><var>forbidden</var><code>, </code><var>Gdata</var><code>, </code><var>Normalsgs</var><code>, </code><var>fgdata</var><code> ) O</code>
<p>
Let <var>fgdata</var> be a list of records of the form returned by
<a href="CHAP007.htm#SSEC001.3">OrderedSigsFromQuotientImages</a> and <var>Normalsgs</var> a list of normal subgroups
of the group <var>Gdata.G</var>. Furthermore let <var>forbidden</var> be the forbidden set
as a list of group elements or integers or a subgroup of <var>Gdata.G</var>.
<p>
Then <code>MatchingFGDataForOrderedSigs</code> retruns all elements of <var>fgdata</var> which
match a normal subgroup of <var>Normalsgs</var>. The returned value is a record
containing the normal subgroup <var>.normal</var> from <var>Normalsgs</var>, the record
<var>.sigdata</var> from <var>fgdata</var> and a homomorphism <var>.hom</var> which maps <var>Gdata.G</var>
onto <var>.sigdata.Gdata.G</var> and takes <var>forbidden</var> to <var>.sigdata.Nfg</var>.
<p>
<a name = "SSEC001.5"></a>
<li><code>OrderedSigInvariant( </code><var>set</var><code>, </code><var>data</var><code> ) O</code>
<p>
does the same as <a href="CHAP005.htm#SSEC001.7">SigInvariant</a>, but for ordered signatures. Here <var>data</var>
has to be a list of records containing ordered signatures called
<var>.orderedSigs</var> and cosets <var>.cosets</var> just as returned by
<a href="CHAP007.htm#SSEC001.3">OrderedSigsFromQuotientImages</a>.
<p>
Assume we have calculated ordered signatures and have stored them in a
record <var>.osigs</var> and a list <var>normalSubgroupsData</var> as returned by
<a href="CHAP005.htm#SSEC003.1">SignatureData</a> containing the admissible signatures. A function for
partitioning partial relative difference sets as required by
<a href="CHAP005.htm#SSEC001.12">ReducedStartsets</a> can be defined as follows:
<p>
<pre>
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;
</pre>
<p>
<p>
<h2><a name="SECT002">7.2 Ordered signatures using representations</a></h2>
<p><p>
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.
<p>
<p>
<h2><a name="SECT003">7.3 Definition</a></h2>
<p><p>
Let <var>R subseteqG</var> be a (partial) ordinary difference set (for
definition see <a href="../../rds/htm/CHAP004.htm#SECT001">RDS:Introduction</a>). Let <var>UleqG</var> be a normal subgroup and
<var>C={g<sub>1</sub>,..., g<sub>|G:U|</sub>}</var> be a system of representatives of <var>G/U</var>.
<p>
As in <a href="../../rds/htm/CHAP005.htm#SECT001">RDS:The Coset Signature</a> we may define the coset signature of <var>R</var>
relative to <var>U</var>.
<p>
Let <var>U=g<sub>1</sub>,...,g<sub>|G:U|</sub></var> be an enumeration of <var>G/U</var>. An
``admissible ordered signature'' for <var>U</var> is a tuple
<var>(v<sub>1</sub>,...,v<sub>|G:U|</sub>)</var> such that
<p>
<p><var>
matrix
sumv<sub>i</sub>=k<br>
sumv<sub>i</sub><sup>2</sup>=lambda(|U|-1)+k<br>
sum<sub>j</sub> v<sub>j</sub> v<sub>ij</sub>=
lambda(|U|-1)for g<sub>i</sub>notinU
<p></var>
<p>
holds where we index the <var>v<sub>i</sub></var> by elements of <var>G/U</var>, so <var>v<sub>i</sub>=v<sub>g_i</sub></var>
and write <var>v<sub>ij</sub>=v<sub>g_ig_j</sub></var>. Observe that the third equation is a
restriction on the ordering of the tuple <var>(v<sub>1</sub>,...,v<sub>|G:U|</sub>)</var>. If
<var>v</var> is an admissible ordered signature, then the multiset of <var>v</var> is an
unordered signature.
<p>
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 <a href="../../rds/htm/CHAP005.htm#SECT001">RDS:The Coset Signature</a> do this to find out if there is an
ordered signature at all. Except that they stop when they find an
ordered signature).
<p>
For ordinary difference sets in extensions of semidirect products of
cyclic groups, ordered signatures may be calculated a lot easier (see
<a href="biblio.htm#RoederDiss"><cite>RoederDiss</cite></a> for details).
<p>
<p>
<h2><a name="SECT004">7.4 Methods for calculating ordered signatures</a></h2>
<p><p>
<a name = "SSEC004.1"></a>
<li><code>NormalSubgroupsForRep( </code><var>groupdata</var><code>, </code><var>divisor</var><code> ) O</code>
<p>
Let <var>groupdata</var> be the output of <a href="CHAP004.htm#SSEC003.1">PermutationRepForDiffsetCalculations</a> and
<var>divisor</var> an integer. Then <code>NormalSubgroupsForRep</code> calculates all normal
subgroups of <var>groupdata.G</var> such that the size of the factor group is divisible
by <var>divisor</var> and the factor group is a semidirect product of cyclic groups.
<p>
The output is a record consisting of
<dl compact>
<dt>1.<dd>a normal subgroup <var>.Nsg</var> of <var>G</var>
<dt>2.<dd>the factor group <var>.fgrp</var>:=<var>G</var>/<var>Nsg</var>
<dt>3.<dd>the epimorphism <var>.epi</var> from <var>G</var> to <var>.fgrp</var>
<dt>4.<dd>a root of unity <var>.root</var>
<dt>5.<dd>a galois automorphism <var>.alpha</var>
<dt>6.+7.<dd>generators of the factor group <var>G</var>/<var>.Nsg</var> named <var>.a</var> and <var>.b</var>
such that <var>.a</var> is normalized by <var>.b</var>.
<dt>8<dd>a list <var>.int2pairtable</var> such that the <var>i<sup>th</sup></var> entry is the pair
<var>[m,n]</var> with that <var>Glist[i]^epi=a^(m-1)*b^(n-1)</var>
</dl>
<p>
<var>.alpha</var> and <var>.root</var> may be used as input for <a href="CHAP007.htm#SSEC004.2">OrderedSigs</a>
<p>
<a name = "SSEC004.2"></a>
<li><code>OrderedSigs( </code><var>coeffSums</var><code>, </code><var>absSum</var><code>, </code><var>alpha</var><code>, </code><var>root</var><code> ) O</code>
<p>
Let <var>G</var> be group which contains a normal subgroup of index <var>s</var> such that
the coset signature for a difference set for this normal subgroup is
<var>coeffSums</var>. Let <var>N</var> be a normal subgroup of <var>G</var> such that <var>G/N</var> is a
semidirect product of cyclic group of orders <var>s,q</var> and
<var>i</var> divides the order of <var>G/N</var>.
<p>
Then <code>OrderedSigs(</code><var>coeffSums</var><code>,</code><var>absSum</var><code>,</code><var>alpha</var><code>,</code><var>root</var><code>)</code> calculates
all ordered signatures for <var>N</var>. Here <var>root</var> is a primitive <var>q</var>-th root
of unity and <var>alpha</var> is a Galois- automorphism of <var>CS(q)</var> with order
dividing <var>s</var>. <var>absSum</var> is the order of the difference set.
(i.e. <var>order=k-lambda</var>).
<p>
<code>OrderedSigs</code> is based on calculations using an <var>s</var>-dimensional unitary
representation of <var>G/N</var>.
In this representation a subset of <var>G</var> induces a semi-circular matrix.
The returned value is a list of lists <var>s</var>-tuples
The entries of the <var>s</var>-tuples are coefficients of numbers in
<var><font face="helvetica,arial">Z</font>[<var>root</var>]</var> such that the semi-circular matrix defined by these numbers
together with <var>alpha</var> meets necessary conditions for matrices induced
by difference sets.
To gain the algebraic numbers from the <var>s</var>-tuple <var>tup</var>, use
<code>List(</code><var>tup</var><code>,i->CoeffList2CyclotomicList(i,</code><var>root</var><code>))</code>
<p>
Each <var>|<var>coeffSums</var>|</var>-tuple returned defines an ordered signature. The ordering
of <var>G/N</var> is chosen to fit to the data returned by <a href="CHAP007.htm#SSEC004.1">NormalSubgroupsForRep</a>:
<p>
<var>[a<sup>0</sup>,a<sup>1</sup>,...,a<sup>q-1</sup>],[a<sup>0</sup>b,a<sup>1</sup>b,...,a<sup>q-1</sup>b],...,[a<sup>0</sup>b<sup>s-1</sup>,...,a<sup>q-1</sup>b<sup>s-1</sup>]</var>
<p>
So for the calculation of ordered signatures, smaller ordered
signatures <var>coeffSums</var> have to be known. But this is not so bad, as
small signatures are easy to calculate.
The following example shows an application.
<p>
<pre>
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 ] ]
</pre>
<p>
Note that the signature <code>[3, 7, 7]</code> can be assumed to be ordered (by
passing to a suitable translate). So even if we are not interested in
<strong>ordered</strong> signatures, we have found out that there is only one admissible
unordered signature for this normal subgroup. To get this result using
<a href="CHAP005.htm#SSEC001.5">TestedSignatures</a> would have taken a <strong>very</strong> long time.
<p>
Of course, ordered signatures can also be used directly.
<p>
<a name = "SSEC004.3"></a>
<li><code>OrderedSignatureOfSet( set, normal_data ) O</code>
<p>
takes a set <var>set</var> of integers (meant to be a partial difference set) and
a list of records as returned by <a href="CHAP007.htm#SSEC004.1">NormalSubgroupsForRep</a>.
The returned value is a list of lists which is the ordered signature of the
partial difference set <var>set</var> and can be compared to the output of <a href="CHAP007.htm#SSEC004.2">OrderedSigs</a>
<p>
<pre>
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 ] ]
</pre>
<p>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP006.htm">Previous</a>] [<a href ="CHAP008.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>RDS manual<br>December 2008
</address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
2923
