The DifSets 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.
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.
‣ DifferenceSets( G ) | ( function ) |
Returns a list of all difference sets up to equivalence in the group G. Only the smaller of each complementary pair of difference sets is included, and one-element difference sets are ignored.
gap> G := SmallGroup(16, 9);; gap> DifferenceSets(G); [ [ 1, 2, 3, 4, 7, 10 ], [ 1, 2, 3, 4, 8, 9 ] ]
‣ DifferenceSums( G, N ) | ( function ) |
Returns a list of all difference sums up to equivalence in the group G mod its normal subgroup N. Only the smaller of each complementary pair of difference sums is included, and difference sums of size 1 are ignored.
gap> G := SmallGroup(16, 8);; gap> N := Subgroup(G, [G.3, G.4]);; gap> DifferenceSums(G, N); [ [ 3, 1, 1, 1 ], [ 2, 2, 2, 0 ] ]
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.
‣ PossibleDifferenceSetSizes( G ) | ( function ) |
Returns a list of the possible sizes of difference sets in group G. 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 G, and the resulting parameters v, k, lambda pass the Bruck-Ryser-Chowla test.
gap> G := SmallGroup(31, 1);; gap> PossibleDifferenceSetSizes(G); [ 6, 10, 15 ]
‣ DifferenceSetsOfSizeK( G, k ) | ( function ) |
Returns a list of all difference sets up to equivalence in the group G that have size k.
gap> G := SmallGroup(16, 9);; gap> DifferenceSetsOfSizeK(G, 1); [ [ 1 ] ]
‣ DifferenceSumsOfSizeK( G, N, k ) | ( function ) |
Returns a list of all difference sums up to equivalence in the group G mod its normal subgroup N that have size k.
gap> G := SmallGroup(16, 8);; gap> N := Subgroup(G, [G.3, G.4]);; gap> DifferenceSumsOfSizeK(G, N, 1); [ [ 1, 0, 0, 0 ] ]
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 \(k\) we know that the only difference sum of size \(k\) in \(G\) mod \(G\) is [k]. Starting with this difference sum, we successivly refine through a series of quotients of \(G\) to eventually reach the desired sums or sets. In the algorithm, we use SomeRefinedDifferenceSets (2.3-4) and SomeRefinedDifferenceSums (2.3-8) rather than AllRefinedDifferenceSets (2.3-2) and AllRefinedDifferenceSums (2.3-6) 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.
‣ RefiningSeries( G ) | ( function ) |
Returns a normal series for group G. Current implementation produces a chief series through a nontrivial normal subgroup of smallest possible size in G.
gap> G := SmallGroup(8, 3);; gap> List(RefiningSeries(G), N -> Size(N)); [ 8, 4, 2, 1 ]
‣ AllRefinedDifferenceSets( G, N, difsums ) | ( function ) |
Returns a list of all difference sets that are preimages of difference sums contained in the list difsums of difference sums in group G mod its normal subgroup N. Difference sums in difsums are all assumed to be the same size.
gap> G := SmallGroup(16, 5);; gap> N := Subgroup(G, [G.2, G.4]);; gap> AllRefinedDifferenceSets(G, N, [[3,1,1,1], [2,2,2,0]]); [ [ 1, 3, 2, 8, 4, 15 ], [ 1, 3, 2, 8, 9, 11 ], [ 1, 3, 2, 13, 4, 11 ], [ 1, 3, 2, 13, 9, 15 ], [ 1, 3, 6, 8, 4, 11 ], [ 1, 3, 6, 8, 9, 15 ], [ 1, 3, 6, 13, 4, 15 ], [ 1, 3, 6, 13, 9, 11 ], [ 1, 5, 2, 6, 4, 15 ], [ 1, 5, 2, 6, 9, 11 ], [ 1, 5, 2, 13, 4, 9 ], [ 1, 5, 2, 13, 11, 15 ], [ 1, 5, 6, 8, 4, 9 ], [ 1, 5, 6, 8, 11, 15 ], [ 1, 5, 8, 13, 4, 15 ], [ 1, 5, 8, 13, 9, 11 ], [ 1, 10, 2, 6, 4, 11 ], [ 1, 10, 2, 6, 9, 15 ], [ 1, 10, 2, 8, 4, 9 ], [ 1, 10, 2, 8, 11, 15 ], [ 1, 10, 6, 13, 4, 9 ], [ 1, 10, 6, 13, 11, 15 ], [ 1, 10, 8, 13, 4, 11 ], [ 1, 10, 8, 13, 9, 15 ], [ 3, 5, 2, 6, 4, 11 ], [ 3, 5, 2, 6, 9, 15 ], [ 3, 5, 2, 8, 4, 9 ], [ 3, 5, 2, 8, 11, 15 ], [ 3, 5, 6, 13, 4, 9 ], [ 3, 5, 6, 13, 11, 15 ], [ 3, 5, 8, 13, 4, 11 ], [ 3, 5, 8, 13, 9, 15 ], [ 3, 10, 2, 6, 4, 15 ], [ 3, 10, 2, 6, 9, 11 ], [ 3, 10, 2, 13, 4, 9 ], [ 3, 10, 2, 13, 11, 15 ], [ 3, 10, 6, 8, 4, 9 ], [ 3, 10, 6, 8, 11, 15 ], [ 3, 10, 8, 13, 4, 15 ], [ 3, 10, 8, 13, 9, 11 ], [ 5, 10, 2, 8, 4, 15 ], [ 5, 10, 2, 8, 9, 11 ], [ 5, 10, 2, 13, 4, 11 ], [ 5, 10, 2, 13, 9, 15 ], [ 5, 10, 6, 8, 4, 11 ], [ 5, 10, 6, 8, 9, 15 ], [ 5, 10, 6, 13, 4, 15 ], [ 5, 10, 6, 13, 9, 11 ] ]
‣ NrAllRefinedSets( G, N, difsums ) | ( function ) |
Returns the number of preimages that will need to be checked during a call to AllRefinedDifferenceSets (2.3-2) with the same arguments. This can give a rough estimate of how long the call will take to complete.
gap> G := SmallGroup(16, 5);; gap> N := Subgroup(G, [G.2, G.4]);; gap> NrAllRefinedSets(G, N, [[3,1,1,1], [2,2,2,0]]); 472
‣ SomeRefinedDifferenceSets( G, N, difsums ) | ( function ) |
Returns a list of some difference sets that are preimages of difference sums contained in the list difsums of difference sums in group G mod its normal subgroup N. 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 difsums are all assumed to be the same size. Current implementation forces the choice of an identity element when possible.
gap> G := SmallGroup(16, 5);; gap> N := Subgroup(G, [G.2, G.4]);; gap> SomeRefinedDifferenceSets(G, N, [[3,1,1,1], [2,2,2,0]]); [ [ 1, 3, 2, 8, 4, 15 ], [ 1, 3, 2, 8, 9, 11 ], [ 1, 3, 2, 13, 4, 11 ], [ 1, 3, 2, 13, 9, 15 ], [ 1, 3, 6, 8, 4, 11 ], [ 1, 3, 6, 8, 9, 15 ], [ 1, 3, 6, 13, 4, 15 ], [ 1, 3, 6, 13, 9, 11 ], [ 1, 5, 2, 6, 4, 15 ], [ 1, 5, 2, 6, 9, 11 ], [ 1, 5, 2, 13, 4, 9 ], [ 1, 5, 2, 13, 11, 15 ], [ 1, 5, 6, 8, 4, 9 ], [ 1, 5, 6, 8, 11, 15 ], [ 1, 5, 8, 13, 4, 15 ], [ 1, 5, 8, 13, 9, 11 ], [ 1, 10, 2, 6, 4, 11 ], [ 1, 10, 2, 6, 9, 15 ], [ 1, 10, 2, 8, 4, 9 ], [ 1, 10, 2, 8, 11, 15 ], [ 1, 10, 6, 13, 4, 9 ], [ 1, 10, 6, 13, 11, 15 ], [ 1, 10, 8, 13, 4, 11 ], [ 1, 10, 8, 13, 9, 15 ] ]
‣ NrSomeRefinedSets( G, N, difsums ) | ( function ) |
Returns the number of preimages that will need to be checked during a call to SomeRefinedDifferenceSets (2.3-4) with the same arguments. This can give a rough estimate of how long the call will take to complete.
gap> G := SmallGroup(16, 5);; gap> N := Subgroup(G, [G.2, G.4]);; gap> NrSomeRefinedSets(G, N, [[3,1,1,1], [2,2,2,0]]); 300
‣ AllRefinedDifferenceSums( G, N1, N2, difsums ) | ( function ) |
Returns a list of all difference sums in group G mod its normal subgroup N2 that are preimages of difference sums contained in the list difsums of difference sums in group G mod its normal subgroup N1. The subgroup N2 must be contained in N1. Difference sums in difsums are all assumed to be the same size.
gap> G := SmallGroup(16, 5);; gap> N1 := Subgroup(G, [G.2, G.4]);; gap> N2 := Subgroup(G, [G.2]);; gap> AllRefinedDifferenceSums(G, N1, N2, [[3,1,1,1], [2,2,2,0]]); [ [ 1, 1, 0, 1, 0, 1, 2, 0 ], [ 1, 1, 2, 1, 0, 1, 0, 0 ], [ 1, 0, 1, 1, 0, 2, 1, 0 ], [ 1, 2, 1, 1, 0, 0, 1, 0 ], [ 0, 1, 1, 2, 0, 1, 1, 0 ], [ 2, 1, 1, 0, 0, 1, 1, 0 ] ]
‣ NrAllRefinedSums( G, N1, N2, difsums ) | ( function ) |
Returns the number of preimages that will need to be checked during a call to AllRefinedDifferenceSums (2.3-6) with the same arguments. This can give a rough estimate of how long the call will take to complete.
gap> G := SmallGroup(16, 5);; gap> N1 := Subgroup(G, [G.2, G.4]);; gap> N2 := Subgroup(G, [G.2]);; gap> NrAllRefinedSums(G, N1, N2, [[3,1,1,1], [2,2,2,0]]); 22
‣ SomeRefinedDifferenceSums( G, N1, N2, difsums ) | ( function ) |
Returns a list of some difference sums in group G mod its normal subgroup N2 that are preimages of difference sums contained in the list difsums of difference sums in group G mod its normal subgroup N1. 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 N2 must be contained in N1 and difference sums in difsums are all assumed to be the same size. Current implementation forces a choice of nonzero identity coefficient when possible.
gap> G := SmallGroup(16, 5);; gap> N1 := Subgroup(G, [G.2, G.4]);; gap> N2 := Subgroup(G, [G.2]);; gap> SomeRefinedDifferenceSums(G, N1, N2, [[3,1,1,1], [2,2,2,0]]); [ [ 1, 1, 0, 1, 0, 1, 2, 0 ], [ 1, 1, 2, 1, 0, 1, 0, 0 ], [ 1, 0, 1, 1, 0, 2, 1, 0 ], [ 1, 2, 1, 1, 0, 0, 1, 0 ], [ 2, 1, 1, 0, 0, 1, 1, 0 ] ]
‣ NrSomeRefinedSums( G, N1, N2, difsums ) | ( function ) |
Returns the number of preimages that will need to be checked during a call to SomeRefinedDifferenceSums (2.3-8) with the same arguments. This can give a rough estimate of how long the call will take to complete.
gap> G := SmallGroup(16, 5);; gap> N1 := Subgroup(G, [G.2, G.4]);; gap> N2 := Subgroup(G, [G.2]);; gap> NrSomeRefinedSums(G, N1, N2, [[3,1,1,1], [2,2,2,0]]); 21
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 EquivalentFreeListOfDifferenceSets (2.4-1) and EquivalentFreeListOfDifferenceSums (2.4-3). The additional functions TranslateFreeListOfDifferenceSets (2.4-2) and TranslateFreeListOfDifferenceSums (2.4-4) can be used to eliminate translate equivalent sums or sets, but they are not used in the main algorithm. Alternatively, SmallestEquivalentDifferenceSet (2.4-5) uses the SmallestImageSet function from the GRAPE 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 SmallestEquivalentFreeListOfDifferenceSets (2.4-6), which is used in the last stage of the main algorithm instead of EquivalentFreeListOfDifferenceSets (2.4-1). While the full algorithm with SmallestEquivalentFreeListOfDifferenceSets (2.4-6) 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 SmallGroup(64, 267), which is impossible with EquivalentFreeListOfDifferenceSets (2.4-1)) and provides a unique minimal result at the end of the algorithm.
‣ EquivalentFreeListOfDifferenceSets( G, difsets ) | ( function ) |
Returns a list of inequivalent difference sets in the group G that consists of one representative from each equivalence class found in the list difsets of arbitrary difference sets in G.
gap> G := SmallGroup(16, 4);; gap> sets := [[8,9,12,13,14,15], [7,8,9,13,15,16], [1,7,10,11,14,15]];; gap> EquivalentFreeListOfDifferenceSets(G, sets); [ [ 8, 9, 12, 13, 14, 15 ] ]
‣ TranslateFreeListOfDifferenceSets( G, difsets ) | ( function ) |
Returns a list of translationally inequivalent difference sets in the group G that consists of one representative from each translational equivalence class found in the list difsets of arbitrary difference sets in G.
gap> G := SmallGroup(16, 4);; gap> sets := [[8,9,12,13,14,15], [7,8,9,13,15,16], [1,7,10,11,14,15]];; gap> TranslateFreeListOfDifferenceSets(G, sets); [ [ 8, 9, 12, 13, 14, 15 ], [ 7, 8, 9, 13, 15, 16 ] ]
‣ EquivalentFreeListOfDifferenceSums( G, N, difsums ) | ( function ) |
Returns a list of inequivalent difference sums in the group G mod its normal subgroup N that consists of one representative from each equivalence class found in the list difsums of arbitrary difference sums in G mod N.
gap> G := SmallGroup(16, 4);; gap> N := Subgroup(G, [G.1 * G.2 * G.3, G.3, G.4]);; gap> EquivalentFreeListOfDifferenceSums(G, N, [[4,2], [2,4]]); [ [ 4, 2 ] ]
‣ TranslateFreeListOfDifferenceSums( G, N, difsums ) | ( function ) |
Returns a list of translationally inequivalent difference sums in the group G mod its normal subgroup N that consists of one representative from each translational equivalence class found in the list difsums of arbitrary difference sums in G mod N.
gap> G := SmallGroup(16, 4);; gap> N := Subgroup(G, [G.1 * G.2 * G.3, G.3, G.4]);; gap> TranslateFreeListOfDifferenceSums(G, N, [[4,2], [2,4]]); [ [ 4, 2 ] ]
‣ SmallestEquivalentDifferenceSet( G, D ) | ( function ) |
Returns the set that is lexicographically smallest among all sets that are equivalent to the difference set D in the group G.
gap> G := SmallGroup(16, 4);; gap> SmallestEquivalentDifferenceSet(G, [8,9,12,13,14,15]); [ 1, 2, 3, 4, 8, 15 ]
‣ SmallestEquivalentFreeListOfDifferenceSets( G, difsets ) | ( function ) |
Returns a list containing the lexicographically smallest set for each set in the list of difference sets difsets in the group G. Duplicates are removed, so the returned list contains exactly one representative from each equivalence class found in difsets.
gap> G := SmallGroup(16, 4);; gap> sets := [[8,9,12,13,14,15], [7,8,9,13,15,16], [1,7,10,11,14,15]];; gap> SmallestEquivalentFreeListOfDifferenceSets(G, sets); [ [ 1, 2, 3, 4, 8, 15 ] ]
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 IsDifferenceSet (2.5-1) simply does the multiplication directly since it is only testing one set.
‣ IsDifferenceSet( G, D ) | ( function ) |
Returns true if the set D is a difference set in the group G, and false otherwise.
gap> G := SmallGroup(16, 4);; gap> IsDifferenceSet(G, [1, 2, 3, 4, 5, 6]); false gap> IsDifferenceSet(G, [1, 2, 8, 10, 11, 15]); true
‣ IsDifferenceSum( G, N, S ) | ( function ) |
Returns true if the sum S is a difference sum in the group G mod its normal subgroup N, and false otherwise.
gap> G := SmallGroup(16, 4);; gap> N := Subgroup(G, [G.1 * G.2 * G.3, G.3, G.4]);; gap> IsDifferenceSum(G, N, [2, 4]); true gap> IsDifferenceSum(G, N, [1, 1]); false
‣ IsEquivalentDifferenceSet( G, D1, D2 ) | ( function ) |
Returns true if sets D1 and D2 are equivalent in the group G, and false otherwise.
gap> G := SmallGroup(16, 4);; gap> IsEquivalentDifferenceSet(G, [1,5,8,9,10,14], [1,5,7,8,10,15]); false
‣ IsEquivalentDifferenceSum( G, N, S1, S2 ) | ( function ) |
Returns true if sums S1 and S2 are equivalent in the group G mod its normal subgroup N, and false otherwise.
gap> G := SmallGroup(16, 4);; gap> N := Subgroup(G, [G.1 * G.2 * G.3, G.3, G.4]);; gap> IsEquivalentDifferenceSum(G, N, [2,4], [4,2]); true
The data directory of the DifSets 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.
‣ CanLoadDifferenceSets( v, n ) | ( function ) |
Returns true if a precomputed list of all difference sets up to equivalence can be loaded from the package library for the group SmallGroup(v, n), and false otherwise.
gap> CanLoadDifferenceSets(36, 9); true gap> CanLoadDifferenceSets(79, 1); false
‣ LoadDifferenceSets( v, n ) | ( function ) |
Returns the precomputed list of all difference sets up to equivalence for the group SmallGroup(v, n) stored in the package library. An error is thrown if no precomputed list is available. Note that the listed difference sets are specific to SmallGroup(v, n), as GAP may label entries of other isomorphic versions of the same group differently.
gap> LoadDifferenceSets(15, 1); [ [ 1, 2, 3, 4, 8, 11, 12 ] ] gap> G := SmallGroup(15, 1);; H := AbelianGroup([15]);; gap> IdGroup(G) = IdGroup(H); true gap> IsDifferenceSet(G, [1, 2, 3, 4, 8, 11, 12]); true gap> IsDifferenceSet(H, [1, 2, 3, 4, 8, 11, 12]); false
generated by GAPDoc2HTML