[MathJax on]

3 Results

The DifSets Package was designed with the goal of finding all difference sets up to equivalence in groups of order 64 and 96, a goal which was accomplished. Overall, the algorithm has successfully computed results for 1006 of the 1032 groups of order less than 100. Full results, which include timings, number of sets, and the sets themselves can be found in the data subdirectory of the package, which is organized by group order and contains a single .txt file for each computed group. A list of all timings can also be found in the file groups.csv in the data directory, and the difference sets themselves can be loaded using the function LoadDifferenceSets (2.6-2). All computations were performed using GAP 4.9.1 on a 4.00GHz i7-6700K using 8GB of RAM. Here we give a basic overview of results and comments on timings. Throughout this chapter we will refer to the group returned by the GAP function SmallGroup(v, n) as [v, n].

3.1 Order 16 and 36

Difference sets in groups of order 16 and 36 form the first nontrivial examples of the Hadamard parameters, and exhaustive enumerations are already well known. Still, computation of these sets gives a useful benchmark and check of accuracy.

Almost all groups in these orders take less than a second. The group [36, 9], however, takes several orders of magnitude longer than other groups of order 36. This is because [36, 9] does not have small normal subgroups (in particular, its smallest nontrivial normal subgroup has order 9), and refining across a large gap in sizes, expecially near the end of the algorithm, requires checking significantly more preimages.

3.2 Order 64 and 96

Difference sets in groups of order 64 also satisfy the Hadamard parameters, while difference sets in groups of order 96 satisfy the McFarland parameters. Since there are many groups of both orders, here we just give some examples and summaries. In particular, the tables below list the fastest, slowest, and median five groups of each order, sorted by time.

Groups of order 64 are p-groups, and thus always have enough normal subgroups to form long refining series. This means the refining steps are relatively efficient for all groups in this order. The main difference between groups is the size of the automorphism group, and, in particular, four of the five groups taking the largest amount of time are four of the five groups with the largest automorphism groups in this order. The additional group in the top five, [64, 235], has a relatively large number of difference sets, but is otherwise unremarkable. In general, smaller numbers of difference sets correspond to faster times, and in fact the eight groups with no difference sets were computed the fastest, beating the next fastest groups by an order of magnitude. Overall, the mean computation time for a group of order 64 was 3988.476 seconds, with a median time of 1493.175 seconds. This means that the total computer time to compute all difference sets in groups of order 64 was roughly 12 days.

In groups of order 96 we do not always have large numbers of normal subgroups, and, as with [36, 9], this can substantially slow down computation. In fact, the five groups taking the longest computation time are five of the six groups with fewest normal subgroups in this order. We are helped, however, by the fact that the only valid choice of k is 20, which is relatively small and thus does not lead to large numbers of preimages even across large gaps in the refining series. Many groups in this order have no difference sets, but even for these groups computation can be slow. While the fastest groups contain no difference sets, many groups with no difference sets actually take much longer than other groups that do contain difference sets. Overall, the mean computation time for a group of order 96 was 24447.991 seconds, with a median time of 11278.765 seconds. This means that the total computer time to compute all difference sets in groups of order 96 was roughly 65 days.

3.3 Comments

Overall, the algorithm spends almost all of its time performing four operations: refining sums to sums in several stages using SomeRefinedDifferenceSums (2.3-8), refining sums to sets in the final stage using SomeRefinedDifferenceSets (2.3-4), removing equivalent difference sums in several stages using EquivalentFreeListOfDifferenceSums (2.4-3), and removing equivalent difference sets in the final stage using SmallestEquivalentFreeListOfDifferenceSets (2.4-6). On typical groups of order 16 and order 36 (i.e., not [36, 9]), each of these four operations takes roughly the same time. On groups of order 64, some testing indicates that one or two orders of magnitude more time are spent in the final stage, when the algorithm uses SomeRefinedDifferenceSets (2.3-4) and SmallestEquivalentFreeListOfDifferenceSets (2.4-6). This discrepency is likely to remain or increase for larger order groups, as the number of preimages to check increases exponentially with the number of cosets. For the tested groups of order 64, roughly 60% of the time in the final stage was spent refining, with the remaining 40% spent removing equivalent sets.

Large automorphism groups make removing equivalents time-consuming and large jumps in the size of the normal subgroups used, especially near the end of the algorithm, make refining difficult. So, in general, the algorithm seems to work well when the group has a small automorphism group and many (small) normal subgroups. In addition, the algorithm does better when the values of k that need to be checked are small, as this limits both the number of preimages to check as well as the amount of time required for checking sets and equivalences. It is also generally faster when the final result is a smaller number of difference sets.

There are twenty-six groups of order less than 100 in which the algorithm was not able to complete a search. Fourteen of these groups are prime order cyclic. As simple groups, these groups have no normal subgroups and thus no possibility for refining, which means the algorithm must search every possible subset of size k to find all difference sets of size k. Even for groups of relatively small order, such as order 31, this is infeasible, and with current implementation will overflow memory before even starting the search (one of these groups, [37, 1] is actually feasible to search without this implementation issue, but the others have too many sets to check). The remaining groups have either too few normal subgroups, large jumps in the refining series, large possible values of k, or a combination of these problems.

The next natural cases for exhaustive search are groups of order 100 and order 144, which give the next Hadamard parameters. Unfortunately, preliminary testing indicates that this algorithm is not likely to be able to compute all difference sets for these groups. For example, a typical difference sum in [100, 9] is [5, 4, 3, 3, 0, 3, 2, 3, 2, 2, 2, 2, 2, 1, 2, 1, 1, 2, 2, 3], which has roughly 6 × 10^16 preimage sets to check. In the search for difference sets in [36, 9] the single difference sum [6, 3, 3, 3], with around 3 × 10^7 preimages, takes around 300 seconds to search. Thus even if we could check sets in [100, 9] as fast as in [36, 9], the search would take roughly 20000 years. Some testing suggests that coding pieces of the algorithm in C could give one or two orders of magnitude of speedup, but even further speedup is required to make the search feasible, so some other improvements, either in theory or implementation, are needed as well.

generated by GAPDoc2HTML