Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.6

Minimum Sum and Difference Covers of Abelian Groups

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

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.

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.