1#############################################################################
2##
3#W lazy.gd 			 RDS Package		 Marc Roeder
4##
5##  Some black-box functions for quick-and-dirty claculations
6##
7##
8#Y	 Copyright (C) 2006-2011 Marc Roeder
9#Y
10#Y This program is free software; you can redistribute it and/or
11#Y modify it under the terms of the GNU General Public License
12#Y as published by the Free Software Foundation; either version 2
13#Y of the License, or (at your option) any later version.
14#Y
15#Y This program is distributed in the hope that it will be useful,
16#Y but WITHOUT ANY WARRANTY; without even the implied warranty of
17#Y MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18#Y GNU General Public License for more details.
19#Y
20#Y You should have received a copy of the GNU General Public License
21#Y along with this program; if not, write to the Free Software
22#Y Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23##
24#############################################################################
25##
26#O IsDiffset(<diffset>,[<forbidden>],<Gdata>,[<lambda>])
27#O IsDiffset(<diffset>,[<forbidden>],<group>,[<lambda>])
28##
29##  This function tests if <diffset> is a relative difference set with
30##  forbidden set <forbidden> and parameter <lambda> in the group <group>.
31##  If <Gdata> is the record calculated by "PermutationRepForDiffsetCalculations",
32##  <diffset> and <forbidden> have to be lists of integers. If a group
33##  <group> is given, <diffset> and <forbidden> must consist of elements
34##  of this group.
35##
36##  If <forbidden> is not given, it is assumed to be trivial. If <lambda>
37##  is not given, it is set to $1$. Note that $1$ (`One(<group>)', repectively)
38##  *must not* be element of <diffset>.
39##
40DeclareOperation("IsDiffset",[IsDenseList,IsRecord]);
41DeclareOperation("IsDiffset",[IsDenseList,IsRecord,IsPosInt]);
42DeclareOperation("IsDiffset",[IsDenseList,IsDenseList,IsRecord]);
43DeclareOperation("IsDiffset",[IsDenseList,IsDenseList,IsRecord,IsPosInt]);
44
45DeclareOperation("IsDiffset",[IsDenseList,IsGroup]);
46DeclareOperation("IsDiffset",[IsDenseList,IsGroup,IsPosInt]);
47DeclareOperation("IsDiffset",[IsDenseList,IsDenseList,IsGroup]);
48DeclareOperation("IsDiffset",[IsDenseList,IsDenseList,IsGroup,IsPosInt]);
49
50#############################################################################
51##
52#O IsPartialDiffset(<diffset>,[<forbidden>],<Gdata>,[<lambda>])
53#O IsPartialDiffset(<diffset>,[<forbidden>],<group>,[<lambda>])
54##
55##  This function tests if <diffset> is a partial relative difference set with
56##  forbidden set <forbidden> and parameter <lambda> in the group <group>.
57##  If <Gdata> is the record calculated by "PermutationRepForDiffsetCalculations",
58##  <diffset> and <forbidden> have to be lists of integers. If a group
59##  <group> is given, <diffset> and <forbidden> must consist of elements
60##  of this group.
61##
62##  If <forbidden> is not given, it is assumed to be trivial. If <lambda>
63##  is not given, it is set to $1$. Note that $1$ (`One(<group>)', repectively)
64##  *must not* be element of <diffset>.
65##
66DeclareOperation("IsPartialDiffset",[IsDenseList,IsRecord]);
67DeclareOperation("IsPartialDiffset",[IsDenseList,IsRecord,IsPosInt]);
68DeclareOperation("IsPartialDiffset",[IsDenseList,IsDenseList,IsRecord]);
69DeclareOperation("IsPartialDiffset",[IsDenseList,IsDenseList,IsRecord,IsPosInt]);
70
71DeclareOperation("IsPartialDiffset",[IsDenseList,IsGroup]);
72DeclareOperation("IsPartialDiffset",[IsDenseList,IsGroup,IsPosInt]);
73DeclareOperation("IsPartialDiffset",[IsDenseList,IsDenseList,IsGroup]);
74DeclareOperation("IsPartialDiffset",[IsDenseList,IsDenseList,IsGroup,IsPosInt]);
75
76
77#############################################################################
78##
79#F StartsetsInCoset(<ssets>,<coset>,<forbiddenSet>,<aim>,<autlist>,<sigdat>,<Gdata>,<lambda>)  generic generator for partial relative difference sets
80##
81##  Assume, we want to generate difference sets ``coset by coset'' modulo some
82##  normal subgroup.
83##  Let <ssets> be a (possibly empty) set of startsets, <coset> the coset from
84##  which to take the elements to append to the startsets from <ssets>.
85##  Furthermore, let <aim> be the size of the generated partial difference sets
86##  (that is, the size of the elements from <ssets> plus the number of elements
87##  to be added from <coset>). Let <autlist> be a list of groups of
88##  automorphisms (in permutation representation) to use with the reduction
89##  algorithm. Here the output from `SuitableAutomorphismsForReduction' can be
90##  used.
91##  And <Gdata> and sigdat are the records as returned by
92##  "PermutationRepForDiffsetCalculations" and
93##  "SignatureDataForNormalSubgroups" (or "SignatureData", alternatively). The
94##  parameter <lambda> is the usual one for difference sets (the number of ways
95##  of expressing elements outside the forbidden set as quotients).
96##
97##  Then `StartsetsInCoset' returns a list of partial difference sets (a list of
98##  lists of integers) of length <aim>.
99##
100##  The list of permutation groups <autlist> is used for equivalence testing.
101##  Each equivalence test is performed calculating equivalence with respect
102##  to the first group, one element per equivalence class is retained and the
103##  equivalence test is repeated using the second group from <autlist>...
104##  Using an ascending list of automorphism groups can speed up the process
105##  of equivalence testing.
106##
107DeclareGlobalFunction("StartsetsInCoset");
108
109#############################################################################
110##
111#F SignatureData(<Gdata>,<forbiddenSet>,<k>,<lambda>,<maxtest>)  quick-and-dirty signature calculation
112##
113##  Let <Gdata> be a record as returned by "PermutationRepForDiffsetCalculations".
114##  Let <forbiddenSet> the forbidden set (as set or group).
115##
116##  <k> is the length of the relative difference set to be constructed and
117##  <lambda> the usual parameter. <maxtest> is the
118##  Then `SignatureData' calls "SignatureDataForNormalSubgroups" for
119##  normal subgroups of order at least `RootInt(Gdata.G)'. Here <maxtest>
120##  is an integer which determines how many permutations of a possible
121##  signature are checked to be a sorted signature. Choose a value of at
122##  least $10^5$. Larger numbers here normaly result in better results
123##  when generating difference sets (making reduction more effective).
124##
125##  `SigntureData' chooses normal subgroups of <Gdata.G> and uses
126##  "SignatureDataForNormalSubgroups" to calculate signature data. The global
127##  data generated by "SignatureDataForNormalSubgroups" is just discarded.
128##
129DeclareGlobalFunction("SignatureData");
130
131
132#############################################################################
133##
134#F NormalSgsHavingAtMostNSigs(<sigdata>,<n>,<lengthlist>)  find normal subgroups with few signatures
135##
136##  Let <sigdata> be a list as returned by "SignatureDataForNormalSubgroups", an
137##  integer <n> and a list of integers <lengthlist>.
138##  `NormalSgsHavingAtMostNSigs' filters <sigdata> and returns
139##  a list of records with components .subgroup and .sigs
140##  is returned, such that for every entry
141##  .subgroup is a normal subgroup of index in <lengthlist> having at most <n>
142##  signatures.
143##
144DeclareGlobalFunction("NormalSgsHavingAtMostNSigs");
145
146
147#############################################################################
148##
149#F SuitableAutomorphismsForReduction(<Gdata>,<normalsg>)  quick-and-dirty calculation of automorphism groups for startset reduction
150##
151##  Given a normal subgroup <normalsg> of <Gdata.G>, the function returns
152##  a list containing the group of automorphisms of <Gdata.G> which
153##  stabilizes all cosets modulo <normalsg>. This group is returned as a
154##  group of permutations on <Gdata.Glist> (which is actually the right
155##  regular representation).
156##  The returned list can be used with "StartsetsInCoset".
157##
158DeclareGlobalFunction("SuitableAutomorphismsForReduction");
159
160
161#############################################################################
162##
163#E  END
164##