Minimum Sum and Difference Covers of Abelian Groups

Harri Haanpää^{1} Laboratory for Theoretical Computer Science Department of Computer Science and Engineering Helsinki University of Technology P.O. Box 5400, 02015 HUT Finland

                 Harri.Haanpaa@hut.fi

Abstract

A subset S of a finite Abelian group G is said to be a sum cover of G if every element of G can be expressed as the sum of two not necessarily distinct elements in S, a strict sum cover of G if every element of G can be expressed as the sum of two distinct elements in S, and a difference cover of G if every element of G can be expressed as the difference of two elements in S. For each type of cover, we determine for small k the largest Abelian group for which a k-element cover exists. For this purpose we compute a minimum sum cover, a minimum strict sum cover, and a minimum difference cover for Abelian groups of order up to 85, 90, and 127, respectively, by a backtrack search with isomorph rejection.

1 Introduction

In this article, all groups are finite even when not explicitly mentioned. Let S be a subset of an Abelian group G and let s (S) = {a + b | a, b ∈ S}, ss (S) = {a, b | a, b ∈ S, a ≠ b} and d (S) = {a − b | a, b ∈ S}. Then S is said to be a sum cover of G if s (S) = G, a strict sum cover of G if ss (S) = G, and a difference cover of G if d (S) = G. Conversely, S is a sum packing of G if |s (G)| = \binom{|S|+1}{2}, a strict sum packing of G if |ss (G)| = \binom{|S|}{2} and a difference packing of G if |d (G) \ {0}| = |S| (|S| − 1).

1 This work has been supported by Helsinki Graduate School in Computer Science and Engineering (HeCSE). Additionally, the author has been supported by grants from the Nokia Foundation and from Tekniikan edistämissäätiö.

Graham and Sloane [3] consider, among related problems, packing and covering problems in cyclic groups. They determine the largest cyclic group that has a k-element sum cover for k ≤ 9, the largest cyclic group that has a k-element strict sum cover for k ≤ 10, the smallest cyclic group that admits a k-element sum packing for k ≤ 12 except k = 11, and the smallest cyclic group that admits a k-element strict sum packing for k ≤ 10.

A natural way of determining a maximum packing or a minimum cover of a group is to combine bounds from constructions and counting arguments with the results of a computer search. Swanson [11] gives some constructions and computational results for maximum difference packings of cyclic groups. Haanpää, Huima, and Östergård [4] compute maximum sum and strict sum packings of cyclic groups, and Haanpää and Östergård [5] consider maximum strict sum packings of Abelian groups. Fitch and Jamison [2] give minimum sum and strict sum covers of small cyclic groups, and Wiedemann [12] determines minimum difference covers for cyclic groups of order at most 133.

In Section 2 we present some definitions and bounds concerning sum and difference covers and packings. In Section 3 we describe the equivalence of subsets of Abelian groups and a method for carrying out isomorph rejection. We describe the search algorithm and summarize the results in Sections 4 and 5, respectively.

2 Definitions and bounds

We define n_{ss} (k), n_{s} (k), and n_{d} (k) as the largest n such that an Abelian group of order n has a k-element strict sum cover, sum cover, and difference cover, respectively. Similarly, n′_{ss} (k), n′_{s} (k), and n′_{d} (k) denote the largest n for which ℤ_{n} has a k-element strict sum cover, sum cover, and difference cover, respectively.

We also make the corresponding definitions for packings. We define v_{ss} (k), v_{s} (k), and v_{d} (k) as the least n such that an Abelian group of order n admits a k-element strict sum packing, sum packing, and difference packing, respectively. Also, we define v′_{ss} (k), v′_{s} (k), and v′_{d} (k) as the least n such that ℤ_{n} admits a k-element strict sum packing, sum packing, and difference packing, respectively.

Lemma 2.1 Any sum packing of an Abelian group G is also a difference packing, and conversely.

Proof: Let S be a sum packing of G. By definition, for all {a, b} ≠ {c, d} with a, b, c, d ∈ S we have a + b ≠ c + d. Therefore, for all a − d = c − b with a, b, c, d ∈ S, a ≠ d, and b ≠ c we have {a, b} = {c, d}. As a ≠ d and b ≠ c, we must have a = c and b = d, and (a, d) = (c, b).

Let S be a difference packing of G. For all (a, d) ≠ (c, b) with a, b, c, d ∈ S, a ≠ d and b ≠ c we have a − d ≠ c − b. Thus, for all a + b = c + d with a, b, c, d ∈ S, a ≠ d, and b ≠ c it holds that (a, d) = (c, b), and therefore {a, b} = {c, d}.

Corollary 2.1 By definition, v_{d} (k) = v_{s} (k).

A simple counting argument shows that

n′_{d} (k) ≤ n_{d} (k) ≤ k (k − 1) + 1 ≤ v_{d} (k) ≤ v′_{d} (k) .  (1)

Equality holds in (1) when every nonzero group element can be represented in exactly one way as the difference of two elements in a subset. In such a case we have a difference set; a difference set is obviously both a difference cover and a difference packing. A well known construction by Singer shows that n′_{d} (k) = k (k − 1) + 1 = v′_{d} (k) whenever k − 1 is a prime power. For more information on difference sets we refer the reader to Jungnickel’s survey [7].

Similar counting arguments show that

n′_{s} (k) ≤ n_{s} (k) ≤ \binom{k + 1}{2} ≤ v_{s} (k) ≤ v′_{s} (k)

and that

n′_{ss} (k) ≤ n_{ss} (k) ≤ \binom{k}{2} ≤ v_{ss} (k) ≤ v′_{ss} (k) .

It is impossible for a sum cover or strict sum cover with more than a small number of elements to cover every group element exactly once.

Theorem 2.1 For k ≥ 5, n_{ss} (k) < \binom{k}{2} < v_{ss} (k).

Proof: If equality would hold one one side, it would also hold on the other. Suppose that v_{ss} (k) = \binom{k}{2} for some k. Then there exists a k-element strict sum packing of an Abelian group G of order \binom{k}{2}. Haanpää and Östergård [5] show that for such a packing to exist,

|G| ≥ (1 − \frac{1}{n_{2}(G)+1}) (k^{2} − 3k + 2), where n_{2} (G) is the index of the subgroup of G that is formed by elements of order 2. If n_{2} (G) = 1, then all elements are of order two, 0 cannot be represented as the sum of two distinct elements, and no strict sum cover exists. If n_{2} (G) ≥ 2, we have \frac{1}{2}k (k − 1) = |G| ≥ \frac{2}{3} (k^{2} − 3k + 2), and thus k ≤ 8. The computational results in Section 5 eliminate the cases 5 ≤ k ≤ 8.

Theorem 2.2 For k ≥ 3, n_{s} (k) < \binom{k+1}{2} < v_{s} (k).

Proof: Again, if equality would hold on one side, it would hold on the other. Suppose v_{s} (k) = \binom{k+1}{2} for some k. Since v_{s} (k) = v_{d} (k), we have \binom{k+1}{2} = v_{s}(k) = v_{d}(k) ≥ k (k − 1) + 1, and thus k < 3.

3 Isomorph rejection in Abelian groups

In this section we define the concept of equivalence of subsets of Abelian groups and find that the equivalence mappings form a group. This group partitions subsets into orbits; from each orbit we choose the lexicographic minimum of the orbit as the canonical representative. In the backtrack search of Section 4, where we construct covers by recursively extending subsets by adding an element to them, it suffices to extend only canonical subsets. In order to speed up the search, we describe a test which will recognize some subsets as non-canonical.

3.1 Automorphisms of Abelian groups

It is well known that all finite Abelian groups are isomorphic to a direct product of cyclic groups of prime power order. A primary Abelian group is an Abelian group of prime power order; in such a group all direct factors have orders that are powers of the same prime. Any Abelian group may be expressed as the direct product of primary Abelian groups.

Let x^{ϕ} denote the image of x under ϕ, where x is an element and ϕ an automorphism of an Abelian group. For tuples and sets we use the induced mapping: let (x_{1}, …, x_{k})^{ϕ} = (x_{1}^{ϕ}, …, x_{k}^{ϕ}), and {x_{1}, …, x_{k}}^{ϕ} = {x_{1}^{ϕ}, …, x_{k}^{ϕ}}. Let x^{H} = {x^{h} | h ∈ H}.

An automorphism of an Abelian group G is a bijection ϕ : G ↦ G such that x^{ϕ} + y^{ϕ} = (x + y)^{ϕ}, or x^{ϕ} + y^{ϕ} = z^{ϕ} iff x + y = z. Shoda described the automorphisms of finite Abelian groups in [10]. In particular, a primary Abelian group ℤ_{p^{e_{1}}} × ⋯ × ℤ_{p^{e_{k}}}, where p is a prime, and e_{1} ≥ ⋯ ≥ e_{k}, has automorphisms of the form ϕ : x ↦ Ax, where x is a column vector that represents an element of an Abelian group in the obvious way, and A is a k × k matrix of the form

A = ( \begin{matrix}h_{11} & p^{e_{1}−e_{2}}h_{12} & ⋯ & p^{e_{1}−e_{k}}h_{1k} \\ h_{21} & h_{22} & & p^{e_{2}−e_{k}}h_{2k} \\ ⋮ & & ... & ⋮ \\ h_{k1} & ⋯ & ⋯ & h_{kk} \end{matrix} )

where det (A) ≢ 0 mod p and h_{ij} are integers. In the matrix multiplication the ith element of the resulting vector is calculated modulo p^{e_{i}}, and thus it suffices to consider 0 ≤ h_{ij} < p^{e_{μ}}, where μ = max (i, j). Shoda also showed that when a finite Abelian group is expressed as the direct product of primary Abelian groups whose orders are powers of distinct primes, the automorphism group of the Abelian group is a direct product of the automorphism groups of the primary Abelian direct factors.

3.2 Equivalent sets

We consider two sets S, T ⊆ G equivalent if T = S^{ψ} where ψ : G ↦ G is a bijection that preserves the equality of two-element sums. That is, we must have w + x = y + z iff w^{ψ} + x^{ψ} = y^{ψ} + z^{ψ}.

Letting z = 0 we have w +x = y +0 iff w^{ψ} +x^{ψ} = z^{ψ} +0^{ψ} iff w^{ψ} −0^{ψ} +x^{ψ} −0^{ψ} = z^{ψ} −0^{ψ}. Letting c = 0^{ψ} and substituting x^{ψ} = x^{ϕ} + c we find w + x = y iff w^{ϕ} + x^{ϕ} = y^{ϕ}, so ϕ is an automorphism of G, and ψ must be of the form ψ : x ↦ x^{ϕ} + c, where ϕ is an automorphism of G and c ∈ G. All ψ of the form ψ : x ↦ x^{ϕ} + c preserve the equality of two-element sums; such ψ form a group, which we denote with H. As 0^{ϕ} = 0 for all ϕ ∈ Aut (G) and Aut (G) ⊆ H, we denote H_{0} = Aut (G).

3.3 Canonicity test

For the elements of G we use the usual lexicographic order for tuples except that we choose an element g_{0} ∈ G of maximum order and let g_{0} precede all elements other than 0. The order of the subsets of G is the lexicographical order: for S, T ⊆ G, S < T iff there exists x ∈ G such that x ∈ S, x ∉ T and y ∈ S iff y ∈ T for all y < x in G. When H acts on G, the subsets of G are partitioned into orbits. A subset S ⊆ G is canonical, if it is the minimum of its orbit: S = minS^{H}.

As the simplistic method of testing the canonicity of S by computing S^{ψ} for every ψ ∈ H would be prohibitively laborious for groups with large |H|, we limit the canonicity testing to a left transversal of H. A left transversal of a subgroup contains exactly one representative from each of the left cosets of the subgroup. In particular, we determine a transversal T of the subgroup H_{0,g_{0}} ⊆ H that fixes 0 and g_{0} pointwise. For every (g_{1}, g_{2}) where g_{2} − g_{1} is of maximum order there is a ψ ∈ T such that (g_{1}, g_{2})^{ψ^{−1}} = (0, g_{0}). In testing S ⊆ G for canonicity, we determine all pairs (g_{1}, g_{2}) such that g_{1}, g_{2} ∈ S and g_{2} − g_{1} is an element of maximum order; for each such pair we determine the ψ ∈ T for which (g_{1}, g_{2})^{ψ^{−1}} = (0, g_{0}) and reject S as not canonical if S^{ψ^{−1}} < S. If S ≤ S^{ψ^{−1}} for all ψ tried, we accept S as possibly canonical.

For determining T, we first choose a transversal T_{0} of H_{0} ⊂ H. For convenience, we choose T_{0} to contain the mapping f : x ↦ x + g for every g ∈ G. We also choose a transversal T_{g_{0}} of H_{0,g_{0}} ⊆ H_{0}, so that for every g ∈ g_{0}^{H_{0}} there is a ϕ ∈ T_{g_{0}} for which g_{0}^{ϕ} = g. When mappings compose from left to right, T = T_{g_{0}}T_{0} is the desired transversal.

Let us give an informal justification of this limited canonicity testing. First, we suppose that the vast majority of sets to be tested contain a pair g_{1}, g_{2} such that (g_{1}, g_{2}) ∈ (0, g_{0})^{H} — the sets that do not are always accepted as possibly canonical. With that assumption it clearly suffices to consider only mappings that map a pair to (0, g_{0}), since sets that contain 0 and g_{0} precede those that do not. To somewhat justify that assumption, note that Jamison [6] proves that for n < 2310, every sum cover of ℤ_{n} is equivalent to one that contains 0 and 1.

If G is cyclic, we have H = T, and our canonicity test will only accept canonical subsets. It may be shown that in an Abelian group |g_{0}^{Aut(G)}| ≥ φ (|G|), where φ denotes the Euler totient function, and equality holds for cyclic G. Since |T_{0}| = |G|, we have |T | ≥ |G| φ (|G|). Since T is at least as large for an Abelian group as it is for a cyclic group of the same order, it appears that our canonicity test is of at least comparable efficiency for an Abelian group as it is for a cyclic group of the same order. It would seem, however, that our canonicity test leaves much room for improvement particularly for Abelian groups with several cyclic direct factors whose orders are powers of the same prime.

4 An orderly algorithm

Our search algorithm is a backtrack search with isomorph rejection. It is an orderly algorithm in the style of Faradžev [1] and Read [9]. Let H be a finite group that acts on a finite totally ordered set X; for subsets of X we use the induced action. The order on X induces a lexicographic order on the set of all subsets of X. A subset S ⊆ X is said to be canonical, if S ≤ h (S) for all h ∈ H.

Theorem 4.1 When started on the empty set, the following method visits every canonical subset of X: Upon visiting a canonical subset S ⊆ X, construct each of the subsets S ∪ {x} where x ∈ X and s < x for all s ∈ S, and visit recursively those newly constructed subsets that are canonical.

Proof: Define f (S) = S \ {max S} for ∅ ≠ S ⊆ X. Observe that f is weakly monotonic on k-subsets: for two k-subsets S, T ⊆ X, S < T implies f (S) ≤ f (T). Also, for any h ∈ H, f (h (S)) ≤ h (f (S)), as both may be obtained from h (S) by removing an element – the maximum element in case of f (h (S)). As the induction base, the null set (the only 0-element subset of X) is visited. As the induction step, if all canonical n-subsets of X are visited, then all canonical n + 1-subsets of X will also be: let C be a canonical n + 1-subset of X. As C is canonical, C ≤ h (C) for all h ∈ H. Since f is weakly monotonic, this implies f (C) ≤ f (h (C)) ≤ h (f (C)) for all h ∈ H. Since f (C) ≤ h (f (C)) for all h ∈ H, f (C) is also canonical. By the induction hypothesis, f (C) is visited, and therefore C is also visited.

In our search, X will consist of the elements of the Abelian group G under consideration and H will be the group of equivalence mappings of G. As described in Section 3, our canonicity test may fail to detect that a subset is not canonical, in which case some equivalent subsets may be visited more than once in the search.

Our algorithm receives as parameters an integer k and an Abelian group G. Then, using the isomorph rejection method described above with the canonicity test detailed in Section 3, it searches for a k-element cover of G. Since H preserves the distinctness of sums or differences of two elements of G, we may also prune some branches of the tree by a counting argument. For constructing a strict sum cover, let p (S) = \binom{|S|}{2} − |ss (S)| represent the duplication in the partial strict sum cover S ≠ ∅. Let S′ = S ∪ {s} where s ∉ S. Now p (S′) = \binom{|S′|}{2} − |ss (S) ∪ \{s + t | t ∈ S\}| ≥ \binom{|S|}{2} + |S| − |ss (S)| − |S| = p (S). Thus, as duplication can only increase when elements are added to a partial strict sum cover, and since p (C) = \binom{k}{2}−|G| for a k-element strict sum cover C of G, the branches where p (S) > \binom{k}{2}−|G| may be pruned since such an S cannot be a subset of a k-element strict sum cover of G. The analogous argument may be presented for sum covers with p (S) = \binom{|S|+1}{2} − |s (S)| and for difference covers with p (S) = |S| (|S| − 1) − |d (G)|.

5 Results

We computed the minimum covers with the algorithm described for Abelian groups of small order. The distributed batch system autoson [8] was used for performing the computation on a heterogeneous network of PCs. We computed the minimum sum cover of groups with order up to 85, the minimum strict sum cover up to group order 90 and the minimum difference cover up to group order 127. We did not compute the difference covers for groups of orders between 128 and 132, but we computed a 12-element difference cover of ℤ_{133}, the existence of which is guaranteed by Singer’s theorem. We also checked that no 13-element sum cover exists for groups G with 86 ≤ |G| ≤ 90. From the results of these computations and the bounds from Section 2 we obtain n_{d} (k) and n′_{d} (k) for k ≤ 12, n_{s} (k) and n′_{s} (k) for k ≤ 13, and n_{ss} (k) and n′_{ss} (k) for k ≤ 14. The results are summarized in Tables 1, 2, 3, and 4. The remaining minimum covers computed may be obtained by contacting the author or at

<URL:http://www.tcs.hut.fi/~haha/>.

Given a k-element cover S of an Abelian group G, it is straightforward to verify that it is, indeed, a cover of the required kind. However, it is generally not straightforward to verify that no k − 1-element cover exists, or that no k-element cover of a larger group exists. The most natural way to verify the results would be to check whether an independent implementation gives the same results. For cyclic groups of order up to 54 we obtain minimum sum and strict sum covers of the same cardinality as Fitch and Jamison [2] with one exception: we found a smaller strict sum cover {0, 1, 2, 3, 4, 5, 11, 18, 23, 28, 35} ⊂ ℤ_{41}. For cyclic groups of order up to 127 we obtain minimum difference covers of the same cardinality as Wiedemann [12]. The covers themselves cannot be compared due to a different ordering of the elements of G in the search.

Acknowledgements

The author wishes to thank Petteri Kaski and Patric Östergård for helpful comments and valuable discussions.

Table 1: Values of n_{d} (k), n′_{d} (k), n_{s} (k), n′_{s} (k), n_{ss} (k), and n′_{ss} (k).
k 2 3 4 5 6 7 8 9 10 11 12 13 14
n_{d} (k) 3 7 13 21 31 39 57 73 91 95 133
n′_{d} (k) 3 7 13 21 31 39 57 73 91 95 133
n_{s} (k) 3 5 9 13 19 21 30 36 43 51 64 72
n′_{s} (k) 3 5 9 13 19 21 30 35 43 51 63 67
n_{ss} (k)  3 6 9 13 20 25 30 36 42 56 64 72
n′_{ss} (k)  3 6 9 13 17 24 30 36 42 56 61 72

Table 2: Difference covers that correspond to values of n_{d}(k) and n′_{d}(k).

k G a minimum difference cover
2 ℤ_{3} {0, 1}
3 ℤ_{7} {0, 1, 3}
4 ℤ_{13} {0, 1, 3, 9}
5 ℤ_{21} {0, 1, 6, 8, 18}
6 ℤ_{31} {0, 1, 3, 8, 12, 18}
7 ℤ_{39} {0, 1, 16, 20, 22, 27, 30}
8 ℤ_{57} {0, 1, 9, 11, 14, 35, 39, 51}
9 ℤ_{73} {0, 1, 3, 7, 15, 31, 36, 54, 63}
10 ℤ_{91} {0, 1, 7, 16, 27, 56, 60, 68, 70, 73}
11 ℤ_{95} {0, 1, 5, 8, 18, 20, 29, 31, 45, 61, 67}
12 ℤ_{133} {0, 1, 32, 42, 44, 48, 51, 59, 72, 77, 97, 111}

Table 3: Sum covers that correspond to values of n_{s}(k) or n′_{s}(k).

k |G| G  a minimum sum cover
2 3 ℤ_{3}  {0, 1}
3 5 ℤ_{5}  {0, 1, 2}
4 9 ℤ_{9}  {0, 1, 3, 4}
5 13 ℤ_{13}  {0, 1, 2, 6, 9}
6 19 ℤ_{19}  {0, 1, 3, 12, 14, 15}
7 21 ℤ_{21}  {0, 1, 3, 7, 11, 15, 19}
8 30 ℤ_{30}  {0, 1, 3, 9, 11, 12, 16, 26}
9 35 ℤ_{35}  {0, 1, 3, 13, 15, 17, 27, 29, 30}
9 36 ℤ_{4}×ℤ_{3}^{2}  {\{(0, 0, 0), (1, 0, 1), (0, 0, 1), (0, 0, 2), (1, 1, 0), \atop (1, 2, 0), (3, 0, 2), (3, 1, 0), (3, 2, 0)\}}
10 43 ℤ_{43}  {0, 1, 2, 3, 10, 15, 21, 25, 31, 36}
11 51 ℤ_{51}  {0, 1, 3, 7, 10, 15, 18, 22, 24, 25, 38}
12 63 ℤ_{63}  {0, 1, 3, 8, 12, 18, 22, 27, 29, 30, 43, 50}
12 64 ℤ_{8}^{2}  {\{(0, 0), (0, 1), (0, 4), (1, 0), (1, 2), (2, 1), \atop (2, 2), (2, 6), (4, 5), (5, 0), (5, 2), (6, 5)\}}
13 67 ℤ_{67}  {0, 1, 2, 3, 4, 5, 6, 16, 24, 33, 40, 49, 57}
13 72 ℤ_{2}×ℤ_{4}×ℤ_{9} {(0, 0, 0), (0, 1, 1), (0, 0, 2), (0, 2, 1), (0, 2, 4), ; (0, 2, 7), (0, 3, 1), (1, 0, 3), (1, 0, 8), (1, 1, 1), ; (1, 2, 5), (1, 2, 6), (1, 3, 1)}

Table 4: Strict sum covers that correspond to values of n_{ss}(k) or n′_{ss}(k).

k |G| G  a minimum strict sum cover
3 3 ℤ_{3}  {0, 1, 2}
4 6 ℤ_{6}  {0, 1, 2, 4}
5 9 ℤ_{9}  {0, 1, 2, 3, 6}
6 13 ℤ_{13}  {0, 1, 2, 3, 6, 10}
7 17 ℤ_{17}  {0, 1, 2, 3, 4, 8, 13}
7 20 ℤ_{2}^{2}×ℤ_{5}  {\{(0, 0, 0), (0, 1, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), \atop (1, 0, 1), (1, 1, 1)\}}
8 24 ℤ_{24}  {0, 1, 2, 4, 8, 13, 18, 22}
8 25 ℤ_{5}^{2}  {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (2, 1), (3, 2), (4, 3)}
9 30 ℤ_{30}  {0, 1, 2, 6, 9, 12, 16, 17, 18}
10 36 ℤ_{36}  {0, 1, 4, 5, 7, 13, 18, 23, 28, 34}
11 42 ℤ_{42}  {0, 1, 11, 12, 18, 22, 24, 27, 30, 32, 36}
12 56 ℤ_{56}  {0, 1, 12, 15, 22, 29, 32, 43, 44, 48, 50, 52}
13 61 ℤ_{61}  {0, 1, 2, 3, 4, 7, 13, 21, 29, 36, 44, 52, 58}
13 64 ℤ_{4}×ℤ_{16} {\{(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 7), (0, 13), \atop (1, 0), (1, 8), (2, 2), (2, 10), (3, 4), (3, 12)\}}
14 72 ℤ_{72}  {0, 1, 2, 5, 12, 30, 37, 40, 41, 42, 50, 56, 58, 64}

References

[1] I. A. Faradžev, Constructive enumeration of combinatorial objects. Colloq. Internat. CNRS 260 (1978), 131–135.

[2] M. A. Fitch and R. E. Jamison, Minimum sum covers of small cyclic groups. Congr. Numer. 147 (2000), 65–81.

[3] R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs. Siam J. Alg. Disc. Meth. 1 (1980), 382–404.

[4] H. Haanpää, A. Huima, and P. R. J. Östergård, Sets in ℤ_{n} with distinct sums of pairs. Discrete Appl. Math. 138 (2004), 99–106.

[5] H. Haanpää and P. R. J. Östergård, Sets in Abelian groups with distinct sums of pairs. Research Report A87, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, Feb. 2004.

[6] R. E. Jamison, The Helly bound for singular sums. Discrete Math. 249 (2002), 117–133.

[7] D. Jungnickel, Difference sets, in J. H. Dinitz and D. R. Stinson, eds., Contemporary Design Theory: A Collection of Surveys, Wiley, 1992, pp. 241–324.

[8] B. D. McKay, autoson – a distributed batch system for UNIX workstation networks (version 1.3). Technical Report TR-CS-96-03, Department of Computer Science, The Australian National University, Mar. 1996.

[9] R. C. Read, Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations. Ann. Discrete Math. 2 (1978), 107–120.

[10] K. Shoda, Über die Automorphismen einer endlichen Abelschen Gruppe. Math. Ann. 100 (1928), 674–686.

[11] C. N. Swanson, Planar cyclic difference packings. J. Combin. Des. 8 (2000), 426–434.

[12] D. Wiedemann, Cyclic difference covers through 133. Congr. Numer. 90 (1992), 181– 185.

2000 Mathematics Subject Classification: Primary 05B40; Secondary 20K01. Keywords: Additive base, backtrack search, difference set, covering.

Received June 11 2003; revised versions received July 2 2003; March 16 2004; June 2 2004. Published in Journal of Integer Sequences, June 10 2004.

Return to Journal of Integer Sequences home page.