Minimum Sum and Difference Covers of Abelian Groups

Reference:

Harri Haanpää. Minimum sum and difference covers of Abelian groups. Research Report A88, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, February 2004.

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.

Keywords:

additive base, backtrack search, difference set, covering

Suggested BibTeX entry:

@techreport{HUT-TCS-A88,
    address = {Espoo, Finland},
    author = {Harri Haanp{\"a}{\"a}},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {February},
    number = {A88},
    pages = {9},
    title = {Minimum Sum and Difference Covers of {A}belian Groups},
    type = {Research Report},
    year = {2004},
}