A \(\langle v, k, \lambda \rangle\)-difference set is a nonempty proper subset \(D\) of a finite group \(G\) such that \(|G| = v\), \(|D| = k\), and each nonidentity element of \(G\) can be written as \(d_id_j^{-1}\) for \(d_i, d_j \in D\) in exactly \(\lambda\) different ways. The standard example is the \(\langle 7, 3, 1\rangle\)-difference set \(\{1, 2, 4\}\) of the group \(\mathbb{Z}/7\mathbb{Z}\) under addition. Additionally, it can easily be shown that every one element subset of a group is a difference set, and the complement of any difference set is also a difference set.
We will often abuse notation and let \(D\) denote both the set \(D\) and the element
\[D = \sum_{d \in D} d\]
of the group ring \(\mathbb{Z}[G]\). Then define
\[gD = \sum_{d \in D} gd,\]
\[D^\phi = \sum_{d \in D} \phi(d),\]
\[D^{(-1)} = \sum_{d \in D} d^{-1},\]
where \(g \in G\) and \(\phi\) is a homomorphism with domain \(G\). Using this notation, a difference set in \(G\) is an element of the group ring \(\mathbb{Z}[G]\) with coefficients from \(\{0, 1\}\) such that \(DD^{(-1)} = (k-\lambda) + \lambda G\), where by convention the isolated coefficients \((k-\lambda)\) are assumed to be coefficients of the identity.
Two difference sets \(D_1, D_2\) are equivalent if both are in the same group \(G\) and \(D_1 = gD_2^\phi\) for some \(g \in G\) and \(\phi \in \mathrm{Aut}(G)\). In other words, \(D_1\) is equivalent to \(D_2\) if \(D_1\) can be mapped to \(D_2\) by translation and automorphism in the group \(G\). We say \(D_1, D_2\) are translationally equivalent if they are equivalent solely by translation, meaning \(D_1 = gD_2\) for some \(g \in G\).
In the package, difference sets are stored as lists of integers that represent the index of the elements in the difference set as found in the list of all elements in the group returned by the GAP function Elements(G). For example, the difference set [1, 3, 6, 9, 11, 13] in SmallGroup(16, 5) really consists of the first, third, sixth, ninth, eleventh, and thirteenth elements of the list returned by Elements(SmallGroup(16, 5)). When given as arguments, difference sets in the package are never assumed to be sorted, but many functions will return difference sets in sorted order since sorting is used internally.
A \(\langle v, k, \lambda \rangle\)-difference sum in a group \(G\) modulo its normal subgroup \(N\) is an element \(S\) of the group ring \(\mathbb{Z}[G/N]\) such that \(SS^{(-1)} = (k - \lambda) + \lambda |N|G/N\) and the coefficients of \(S\) have values in \(\{0, 1, \dots, |N|\}\). Note that the original \(G\) and \(N\) are included in the definition, so it makes no sense to talk about a difference sum in some arbitrary group \(H\). The size of a difference sum is the sum of its coefficients, and by defining the complement of \(S\) to be \(|N|G/N - S\) we can see that, similar to difference sets, size one sums and complements of difference sums are always difference sums.
Two difference sums \(S_1, S_2\) are equivalent if both are in the same group \(G\) mod its normal subgroup \(N\) and \(S_1 = gS_2^\phi\) for some \(g \in G/N\) and \(\phi\) an automorphism of \(G/N\) induced by an automorphism of \(G\). Note that not all automorphisms of \(G/N\) are induced by automorphisms of \(G\), so our definition here is more restrictive than perhaps expected. As with difference sets, the sums \(S_1, S_2\) are translationally equivalent if \(S_1 = gS_2\) for some \(g \in G/N\).
In the package, difference sums are stored as lists of integers that represent the values of the coefficients of the group ring elements, with position in the list given by the position of the coset in the list of elements returned by the GAP function Elements(G/N). For example, the difference sum [2, 4] in G := SmallGroup(16, 5) mod its normal subgroup Subgroup(G, [G.2, G.3, G.4]) has coefficient 2 on the identity coset, and coefficient 4 on the nonidentity coset.
Difference sums can be thought of as a generalization of difference sets. More importantly, however, difference sums can be thought of as images of difference sets in quotients of the original group. In particular, if \(\theta : G \to G/N\) is the natural projection, then for any difference set \(D\) in \(\mathbb{Z}[G]\) we have a difference sum \(D^\theta\) in \(G\) modulo its normal subgroup \(N\). Additionally, difference sums induce other difference sums in any further quotient. The fundamental idea of the algorithm in this package is that we can reverse this process. Starting with \(G\) mod \(G\), where the only difference sum of size \(k\) is [k], we can successively refine this difference sum up a series of quotients of \(G\) until reaching \(G\) itself. In each step we enumerate all preimages of the difference sums and remove preimages that are not difference sums themselves. In the final step we refine to difference sets. Furthermore, since equivalent difference sums will have equivalent collections of difference sets as preimages, in each step we remove all but one representative of each equivalence class from our collection. This method dramatically decreases the search space for an exhaustive enumeration of all difference sets up to equivalence in \(G\).
generated by GAPDoc2HTML