<p>The <strong class="pkg">DifSets</strong> Package consists of a collection of functions implementing the main algorithm, and some additional functions for experimentation and testing. Several functions not appearing in this documentation are used internally for certain subtasks. See the code itself for details.</p>
<h4>2.1 <span class="Heading">The Main Functions</span></h4>
<p>The purpose of this package is to provide a function that efficiently enumerates all difference sets up to equivalence in a given group. Similarly, we can also enumerate all difference sums up to equivalence. The following are these functions. Their components are described in further sections.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DifferenceSets</code>( <var class="Arg">G</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of all difference sets up to equivalence in the group <var class="Arg">G</var>. Only the smaller of each complementary pair of difference sets is included, and one-element difference sets are ignored.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DifferenceSums</code>( <var class="Arg">G</var>, <var class="Arg">N</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of all difference sums up to equivalence in the group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N</var>. Only the smaller of each complementary pair of difference sums is included, and difference sums of size 1 are ignored.</p>
<p>The first step of the algorithm is to determine what possible sizes of difference sets and sums the group can contain. Each size is then handled individually since different size sets or sums will never be equivalent.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PossibleDifferenceSetSizes</code>( <var class="Arg">G</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of the possible sizes of difference sets in group <var class="Arg">G</var>. Only the smaller of any pair of complementary sizes is returned, and the trivial size 1 is never included. Current implementation simply returns all values of k such that lambda = k(k-1)/(v-1) is an integer, where v is the order of <var class="Arg">G</var>, and the resulting parameters v, k, lambda pass the Bruck-Ryser-Chowla test.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DifferenceSetsOfSizeK</code>( <var class="Arg">G</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of all difference sets up to equivalence in the group <var class="Arg">G</var> that have size <var class="Arg">k</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DifferenceSumsOfSizeK</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of all difference sums up to equivalence in the group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N</var> that have size <var class="Arg">k</var>.</p>
<p>Refining refers to the process of enumerating the preimages of a difference sum and filtering out preimages that are not themselves difference sets or sums. For each size <span class="SimpleMath">\(k\)</span> we know that the only difference sum of size <span class="SimpleMath">\(k\)</span> in <span class="SimpleMath">\(G\)</span> mod <span class="SimpleMath">\(G\)</span> is <code class="code">[k]</code>. Starting with this difference sum, we successivly refine through a series of quotients of <span class="SimpleMath">\(G\)</span> to eventually reach the desired sums or sets. In the algorithm, we use <code class="func">SomeRefinedDifferenceSets</code> (<a href="chap2_mj.html#X7E1012C07FB328B4"><span class="RefLink">2.3-4</span></a>) and <code class="func">SomeRefinedDifferenceSums</code> (<a href="chap2_mj.html#X866272667D6032BA"><span class="RefLink">2.3-8</span></a>) rather than <code class="func">AllRefinedDifferenceSets</code> (<a href="chap2_mj.html#X78CDE421817B50EE"><span class="RefLink">2.3-2</span></a>) and <code class="func">AllRefinedDifferenceSums</code> (<a href="chap2_mj.html#X80BF8487824FA6B1"><span class="RefLink">2.3-6</span></a>) since the former are faster and we only need at least one representative of each equivalence class since additional equivalent sums or sets will just be removed anyway.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RefiningSeries</code>( <var class="Arg">G</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a normal series for group <var class="Arg">G</var>. Current implementation produces a chief series through a nontrivial normal subgroup of smallest possible size in <var class="Arg">G</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AllRefinedDifferenceSets</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of all difference sets that are preimages of difference sums contained in the list <var class="Arg">difsums</var> of difference sums in group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N</var>. Difference sums in <var class="Arg">difsums</var> are all assumed to be the same size.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrAllRefinedSets</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the number of preimages that will need to be checked during a call to <code class="func">AllRefinedDifferenceSets</code> (<a href="chap2_mj.html#X78CDE421817B50EE"><span class="RefLink">2.3-2</span></a>) with the same arguments. This can give a rough estimate of how long the call will take to complete.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SomeRefinedDifferenceSets</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of some difference sets that are preimages of difference sums contained in the list <var class="Arg">difsums</var> of difference sums in group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N</var>. At least one member of each equivalence class that would appear in the set of all preimages will be returned, but all preimage difference sets may not appear. Difference sums in <var class="Arg">difsums</var> are all assumed to be the same size. Current implementation forces the choice of an identity element when possible.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrSomeRefinedSets</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the number of preimages that will need to be checked during a call to <code class="func">SomeRefinedDifferenceSets</code> (<a href="chap2_mj.html#X7E1012C07FB328B4"><span class="RefLink">2.3-4</span></a>) with the same arguments. This can give a rough estimate of how long the call will take to complete.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AllRefinedDifferenceSums</code>( <var class="Arg">G</var>, <var class="Arg">N1</var>, <var class="Arg">N2</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of all difference sums in group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N2</var> that are preimages of difference sums contained in the list <var class="Arg">difsums</var> of difference sums in group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N1</var>. The subgroup <var class="Arg">N2</var> must be contained in <var class="Arg">N1</var>. Difference sums in <var class="Arg">difsums</var> are all assumed to be the same size.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrAllRefinedSums</code>( <var class="Arg">G</var>, <var class="Arg">N1</var>, <var class="Arg">N2</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the number of preimages that will need to be checked during a call to <code class="func">AllRefinedDifferenceSums</code> (<a href="chap2_mj.html#X80BF8487824FA6B1"><span class="RefLink">2.3-6</span></a>) with the same arguments. This can give a rough estimate of how long the call will take to complete.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SomeRefinedDifferenceSums</code>( <var class="Arg">G</var>, <var class="Arg">N1</var>, <var class="Arg">N2</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of some difference sums in group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N2</var> that are preimages of difference sums contained in the list <var class="Arg">difsums</var> of difference sums in group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N1</var>. At least one member of each equivalence class that would appear in the set of all preimages will be returned, but all preimage difference sums may not appear. The subgroup <var class="Arg">N2</var> must be contained in <var class="Arg">N1</var> and difference sums in <var class="Arg">difsums</var> are all assumed to be the same size. Current implementation forces a choice of nonzero identity coefficient when possible.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrSomeRefinedSums</code>( <var class="Arg">G</var>, <var class="Arg">N1</var>, <var class="Arg">N2</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the number of preimages that will need to be checked during a call to <code class="func">SomeRefinedDifferenceSums</code> (<a href="chap2_mj.html#X866272667D6032BA"><span class="RefLink">2.3-8</span></a>) with the same arguments. This can give a rough estimate of how long the call will take to complete.</p>
<p>Since we are searching for all difference sets or sums up to equivalence, at each stage we remove excess equivalent sums or sets from our collection. This can be done with <code class="func">EquivalentFreeListOfDifferenceSets</code> (<a href="chap2_mj.html#X7E4BCB8482E4AE34"><span class="RefLink">2.4-1</span></a>) and <code class="func">EquivalentFreeListOfDifferenceSums</code> (<a href="chap2_mj.html#X8639AB227B0CF9F3"><span class="RefLink">2.4-3</span></a>). The additional functions <code class="func">TranslateFreeListOfDifferenceSets</code> (<a href="chap2_mj.html#X8380F5D37E2D411B"><span class="RefLink">2.4-2</span></a>) and <code class="func">TranslateFreeListOfDifferenceSums</code> (<a href="chap2_mj.html#X7BF295758033DC3B"><span class="RefLink">2.4-4</span></a>) can be used to eliminate translate equivalent sums or sets, but they are not used in the main algorithm. Alternatively, <code class="func">SmallestEquivalentDifferenceSet</code> (<a href="chap2_mj.html#X857A641A7C86EFA3"><span class="RefLink">2.4-5</span></a>) uses the <code class="code">SmallestImageSet</code> function from the <strong class="pkg">GRAPE</strong> package to produce the lexicographically minimal difference set equivalent to a given set. Eliminating equivalent sets can then be done by mapping each set to its minimal representative and then simply eliminating duplicates. This is done automatically by <code class="func">SmallestEquivalentFreeListOfDifferenceSets</code> (<a href="chap2_mj.html#X8741BBF4811F942A"><span class="RefLink">2.4-6</span></a>), which is used in the last stage of the main algorithm instead of <code class="func">EquivalentFreeListOfDifferenceSets</code> (<a href="chap2_mj.html#X7E4BCB8482E4AE34"><span class="RefLink">2.4-1</span></a>). While the full algorithm with <code class="func">SmallestEquivalentFreeListOfDifferenceSets</code> (<a href="chap2_mj.html#X8741BBF4811F942A"><span class="RefLink">2.4-6</span></a>) is roughly 20% slower on average (and is almost 4x as slow on a few groups of order 64), this function is used since it is much faster on large automorphism groups (such as the automorphism group of <code class="code">SmallGroup(64, 267)</code>, which is impossible with <code class="func">EquivalentFreeListOfDifferenceSets</code> (<a href="chap2_mj.html#X7E4BCB8482E4AE34"><span class="RefLink">2.4-1</span></a>)) and provides a unique minimal result at the end of the algorithm.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EquivalentFreeListOfDifferenceSets</code>( <var class="Arg">G</var>, <var class="Arg">difsets</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of inequivalent difference sets in the group <var class="Arg">G</var> that consists of one representative from each equivalence class found in the list <var class="Arg">difsets</var> of arbitrary difference sets in <var class="Arg">G</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TranslateFreeListOfDifferenceSets</code>( <var class="Arg">G</var>, <var class="Arg">difsets</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of translationally inequivalent difference sets in the group <var class="Arg">G</var> that consists of one representative from each translational equivalence class found in the list <var class="Arg">difsets</var> of arbitrary difference sets in <var class="Arg">G</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EquivalentFreeListOfDifferenceSums</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <varclass="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of inequivalent difference sums in the group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N</var> that consists of one representative from each equivalence class found in the list <var class="Arg">difsums</var> of arbitrary difference sums in <var class="Arg">G</var> mod <var class="Arg">N</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TranslateFreeListOfDifferenceSums</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <var class="Arg">difsums</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of translationally inequivalent difference sums in the group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N</var> that consists of one representative from each translational equivalence class found in the list <var class="Arg">difsums</var> of arbitrary difference sums in <var class="Arg">G</var> mod <var class="Arg">N</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallestEquivalentDifferenceSet</code>( <var class="Arg">G</var>, <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the set that is lexicographically smallest among all sets that are equivalent to the difference set <var class="Arg">D</var> in the group <var class="Arg">G</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallestEquivalentFreeListOfDifferenceSets</code>( <var class="Arg">G</var>, <var class="Arg">difsets</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list containing the lexicographically smallest set for each set in the list of difference sets <var class="Arg">difsets</var> in the group <var class="Arg">G</var>. Duplicates are removed, so the returned list contains exactly one representative from each equivalence class found in <var class="Arg">difsets</var>.</p>
<p>These additional functions are provided to check work and perform other experimentation. They are inefficient when used repeatedly. For example, when testing a large number of difference sets in a single group, it is better to precompute the needed group operations and store them in a table for lookup, but <code class="func">IsDifferenceSet</code> (<a href="chap2_mj.html#X8545AC1D7D42A84A"><span class="RefLink">2.5-1</span></a>) simply does the multiplication directly since it is only testing one set.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDifferenceSet</code>( <var class="Arg">G</var>, <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns true if the set <var class="Arg">D</var> is a difference set in the group <var class="Arg">G</var>, and false otherwise.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDifferenceSum</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns true if the sum <var class="Arg">S</var> is a difference sum in the group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N</var>, and false otherwise.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEquivalentDifferenceSet</code>( <var class="Arg">G</var>, <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns true if sets <var class="Arg">D1</var> and <var class="Arg">D2</var> are equivalent in the group <var class="Arg">G</var>, and false otherwise.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEquivalentDifferenceSum</code>( <var class="Arg">G</var>, <var class="Arg">N</var>, <var class="Arg">S1</var>, <var class="Arg">S2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns true if sums <var class="Arg">S1</var> and <var class="Arg">S2</var> are equivalent in the group <var class="Arg">G</var> mod its normal subgroup <var class="Arg">N</var>, and false otherwise.</p>
<p>The <code class="code">data</code> directory of the <strong class="pkg">DifSets</strong> Package contains precomputed results for 1006 of the 1032 groups of order less than 100. The following two functions are the easiest way to access these precomputed lists of difference sets up to equivalence.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanLoadDifferenceSets</code>( <var class="Arg">v</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns true if a precomputed list of all difference sets up to equivalence can be loaded from the package library for the group <code class="code">SmallGroup(<var class="Arg">v</var>, <var class="Arg">n</var>)</code>, and false otherwise.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LoadDifferenceSets</code>( <var class="Arg">v</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the precomputed list of all difference sets up to equivalence for the group <code class="code">SmallGroup(<var class="Arg">v</var>, <var class="Arg">n</var>)</code> stored in the package library. An error is thrown if no precomputed list is available. Note that the listed difference sets are specific to <code class="code">SmallGroup(<var class="Arg">v</var>, <var class="Arg">n</var>)</code>, as <strong class="pkg">GAP</strong> may label entries of other isomorphic versions of the same group differently.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
