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##