<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{{\LARGE\bf 
Minimum Sum and Difference Covers \\
\vskip .15in
of Abelian Groups}
}
\vskip 1cm
\large Harri Haanp\"a\"a\footnote{
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\"amiss\"a\"ati\"o.
}\\
Laboratory for Theoretical Computer Science\\
Department of Computer Science and Engineering\\
Helsinki University of Technology\\
P.O.\  Box 5400, 02015 HUT\\
Finland\\
\href{mailto:Harri.Haanpaa@hut.fi}{\tt Harri.Haanpaa@hut.fi}\\
\end{center}

\vskip .2in

\begin{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.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

%\documentclass[12pt,a4paper,english,american]{article}
%\usepackage[T1]{fontenc}
%\usepackage{amsmath}
%\pagestyle{plain}
%\usepackage{babel}
%\usepackage{amssymb}
%\usepackage{ae}
%
%\makeatletter
%
%\usepackage{amsmath}
%\newtheorem{theorem}{Theorem}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{lemma}{Lemma}
%
%\makeatother
%\begin{document}

\newcommand{\bt}{\begin{theorem}} \newcommand{\et}{\end{theorem}}

\newcommand{\bc}{\begin{corollary}} \newcommand{\ec}{\end{corollary}}

\newcommand{\bl}{\begin{lemma}} \newcommand{\el}{\end{lemma}}

\newcommand{\bp}{\paragraph{Proof:}} \newcommand{\ep}{\bigskip}




\section{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\left( S\right) =\left\{ a+b\mid a,b\in S\right\}  \),
\( ss\left( S\right) =\left\{ a,b\mid a,b\in S,a\neq b\right\}  \)
and \( d\left( S\right) =\left\{ a-b\mid a,b\in S\right\}  \). Then
\( S \) is said to be a \emph{sum cover} of \( G \) if \( s\left( S\right) =G \),
a \emph{strict sum cover} of \( G \) if \( ss\left( S\right) =G \), and
a \emph{difference cover} of \( G \) if \( d\left( S\right) =G \). Conversely,
\( S \) is a \emph{sum packing} of \( G \) if \( \left| s\left( G\right) \right| =\binom{\left| S\right| +1}{2} \),
a \emph{strict sum packing} of \( G \) if \( \left| ss\left( G\right) \right| =\binom{\left| S\right| }{2} \)
and a \emph{difference packing} of \( G \) if \( \left| d\left( G\right) \setminus \left\{ 0\right\} \right| =\left| S\right| \left( \left| S\right| -1\right)  \).

Graham and Sloane \cite{graham.sloane:on} 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\leq 9, \) the largest cyclic group that has a \( k \)-element
strict sum cover for \( k\leq 10 \), the smallest cyclic group that
admits a \( k \)-element sum packing for \( k\leq 12 \) except \( k=11 \),
and the smallest cyclic group that admits a \( k \)-element strict
sum packing for \( k\leq 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 \cite{swanson:planar}
gives some constructions and computational results for maximum
difference packings of cyclic groups. Haanp\"a\"a, Huima, and
\"Osterg\aa rd  \cite{haanpaa.huima.ea:sets} compute maximum sum and
strict sum packings of cyclic groups, and Haanp\"a\"a and \"Osterg\aa
rd \cite{haanpaa.ostergrd:sets} consider maximum strict sum packings
of Abelian groups. Fitch and Jamison \cite{fitch.jamison:minimum} give
minimum sum and strict sum covers of small cyclic groups, and Wiedemann
\cite{wiedemann:cyclic} determines minimum difference covers for cyclic
groups of order at most 133.

In Section \ref{sec:bounds} we present some definitions and bounds concerning
sum and difference covers and packings. In Section \ref{sec:eq}
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
\ref{sec:search} and \ref{sec:results}, respectively.


\section{\label{sec:bounds}Definitions and bounds}

We define \( n_{ss}\left( k\right)  \), \( n_{s}\left( k\right)  \),
and \( n_{d}\left( k\right)  \) 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}\left( k\right)  \),
\( n'_{s}\left( k\right)  \), and \( n'_{d}\left( k\right)  \) denote
the largest \( n \) for which \( \mathbb {Z}_{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}\left( k\right)  \), \( v_{s}\left( k\right)  \), and \( v_{d}\left( k\right)  \)
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}\left( k\right)  \),
\( v'_{s}\left( k\right)  \), and \( v'_{d}\left( k\right)  \) as
the least \( n \) such that \( \mathbb {Z}_{n} \) admits a \( k \)-element
strict sum packing, sum packing, and difference packing, respectively.

\bl

Any sum packing of an Abelian group \( G \) is also a difference
packing, and conversely. 

\el


\paragraph{Proof:}

Let \( S \) be a sum packing of \( G \). By definition, for all
\( \left\{ a,b\right\} \neq \left\{ c,d\right\}  \) with \( a,b,c,d\in S \)
we have \( a+b\neq c+d \). Therefore, for all \( a-d=c-b \) with
\( a,b,c,d\in S \), \( a\neq d \), and \( b\neq c \) we have \( \left\{ a,b\right\} =\left\{ c,d\right\}  \).
As \( a\neq d \) and \( b\neq c \), we must have \( a=c \) and
\( b=d \), and \( \left( a,d\right) =\left( c,b\right)  \).

Let \( S \) be a difference packing of \( G \). For all \( \left( a,d\right) \neq \left( c,b\right)  \)
with \( a,b,c,d\in S \), \( a\neq d \) and \( b\neq c \) we have
\( a-d\neq c-b \). Thus, for all \( a+b=c+d \) with \( a,b,c,d\in S \),
\( a\neq d \), and \( b\neq c \) it holds that \( \left( a,d\right) =\left( c,b\right)  \),
and therefore \( \left\{ a,b\right\} =\left\{ c,d\right\}  \).

\bc

By definition, \( v_{d}\left( k\right) =v_{s}\left( k\right)  \).

\ec

A simple counting argument shows that \begin{equation}
\label{eq:diffs}
n_{d}'\left( k\right) \leq n_{d}\left( k\right) \leq k\left( k-1\right) +1\leq v_{d}\left( k\right) \leq v_{d}'\left( k\right) .
\end{equation}


Equality holds in (\ref{eq:diffs}) 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}'\left( k\right) =k\left( k-1\right) +1=v'_{d}\left( k\right)  \)
whenever \( k-1 \) is a prime power. For more information on difference
sets we refer the reader to Jungnickel's survey \cite{jungnickel:difference}.

Similar counting arguments show that\begin{equation*}
n_{s}'\left( k\right) \leq n_{s}\left( k\right) \leq \binom{k+1}{2}\leq v_{s}\left( k\right) \leq v_{s}'\left( k\right) 
\end{equation*}
 and that \begin{equation*}
n_{ss}'\left( k\right) \leq n_{ss}\left( k\right) \leq \binom{k}{2}\leq v_{ss}\left( k\right) \leq v_{ss}'\left( k\right) .
\end{equation*}


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.

\bt

For \( k\geq 5 \), \( n_{ss}\left( k\right) &lt;\binom{k}{2}&lt;v_{ss}\left( k\right)  \).

\et


\bp

If equality would hold one one side, it would also hold on the
other.  Suppose that \( v_{ss}\left( k\right) =\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\"a\"a and \"Osterg\aa rd \cite{haanpaa.ostergrd:sets} show
that for such a packing to exist, \( \left| G\right| \geq \left(
1-\frac{1}{n_{2}\left( G\right) +1}\right) \left( k^{2}-3k+2\right)
\), where \( n_{2}\left( G\right)  \) is the index of the subgroup
of \( G \) that is formed by elements of order 2. If \( n_{2}\left(
G\right) =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}\left( G\right) \geq 2 \), we have
\( \frac{1}{2}k\left( k-1\right)=\left| G\right|  \geq \frac{2}{3}\left(
k^{2}-3k+2\right)  \), and thus \( k\leq 8 \). The computational
results in Section \ref{sec:results} eliminate the cases \( 5\leq
k\leq 8 \).\ep

\bt

For \( k\geq 3 \), \( n_{s}\left( k\right) &lt;\binom{k+1}{2}&lt;v_{s}\left( k\right)  \).

\et


\bp

Again, if equality would hold on one side, it would hold on the other.
Suppose \( v_{s}\left( k\right) =\binom{k+1}{2} \) for some \( k \).
Since \( v_{s}\left( k\right) =v_{d}\left( k\right)  \), we have
\( \binom{k+1}{2}=v_s(k)=v_d(k)\geq k\left(k-1\right)+1\),
%\( k\left( k-1\right) +1\leq \binom{k+1}{2}=v_{s}\left( k\right) =v_{d}\left( k\right)  \),
and thus \( k&lt;3 \).\ep

\section{\label{sec:eq}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 \ref{sec:search}, 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.


\subsection{Automorphisms of Abelian groups}

%An Abelian group \( G \) is a group where \( a+b=b+a \) for all
%\( a,b\in G \). 
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^{\phi } \) denote the image of \( x \) under \( \phi  \), where
\(x\) is an element and \(\phi\) an automorphism of an Abelian group.
For tuples and sets we use the induced mapping: let \( \left( x_{1},\ldots ,x_{k}\right) ^{\phi }=\left( x_{1}^{\phi },\ldots ,x_{k}^{\phi }\right)  \),
and \( \left\{ x_{1},\ldots ,x_{k}\right\} ^{\phi }=\left\{ x_{1}^{\phi },\ldots ,x_{k}^{\phi }\right\}  \).
Let \( x^{H}=\left\{ x^{h}\mid h\in H\right\}  \).

An automorphism of an Abelian group \( G \) is a bijection \( \phi :G\mapsto G \)
such that \( x^{\phi }+y^{\phi }=\left( x+y\right) ^{\phi } \), or
\( x^{\phi }+y^{\phi }=z^{\phi } \) iff \( x+y=z \). Shoda described
the automorphisms of finite Abelian groups in \cite{shoda:uber}.
In particular, a primary Abelian group \( \mathbb {Z}_{p^{e_{1}}}\times \cdots \times \mathbb {Z}_{p^{e_{k}}} \),
where \( p \) is a prime, and \( e_{1}\geq \cdots \geq e_{k} \),
has automorphisms of the form \( \phi :x\mapsto Ax \), where \( x \)
is a column vector that represents an element of an Abelian group
in the obvious way, and \( A \) is a \( k\times k \) matrix of the
form\[
A=\left( \begin{array}{cccc}
h_{11} &amp; p^{e_{1}-e_{2}}h_{12} &amp; \cdots  &amp; p^{e_{1}-e_{k}}h_{1k}\\
h_{21} &amp; h_{22} &amp;  &amp; p^{e_{2}-e_{k}}h_{2k}\\
\vdots  &amp;  &amp; \ddots  &amp; \vdots \\
h_{k1} &amp; \cdots  &amp; \cdots  &amp; h_{kk}
\end{array}\right) \]
 where \( \det \left( A\right) \not\equiv 0\) mod \(p \) and \( h_{ij} \)
are integers. In the matrix multiplication the \( i \)th element
of the resulting vector is calculated modulo \( p^{e_{i}} \), and
thus it suffices to consider \( 0\leq h_{ij}&lt;p^{e_{\mu }} \), where
\( \mu =\max \left( i,j\right)  \). 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.


\subsection{Equivalent sets}

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

Letting \( z=0 \) we have \( w+x=y+0 \) iff \( w^{\psi }+x^{\psi }=z^{\psi }+0^{\psi } \)
iff \( w^{\psi }-0^{\psi }+x^{\psi }-0^{\psi }=z^{\psi }-0^{\psi } \).
Letting \( c=0^{\psi } \) and substituting \( x^{\psi }=x^{\phi }+c \)
we find \( w+x=y \) iff \( w^{\phi }+x^{\phi }=y^{\phi } \), so
\( \phi  \) is an automorphism of \( G \), and \( \psi  \) must
be of the form \( \psi :x\mapsto x^{\phi }+c \), where \( \phi  \)
is an automorphism of \( G \) and \( c\in G \). All \( \psi  \)
of the form \( \psi :x\mapsto x^{\phi }+c \) preserve the equality
of two-element sums; such \( \psi  \) form a group, which we denote
with \( H \). As \( 0^{\phi }=0 \) for all \( \phi \in \textrm{Aut}\left( G\right)  \)
and \( \textrm{Aut}\left( G\right) \subseteq H \), we denote \( H_{0}=\textrm{Aut}\left( G\right)  \).


\subsection{Canonicity test}

For the elements of \( G \) we use the usual lexicographic order
for tuples except that we choose an element \( g_{0}\in 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\subseteq G \), \( S&lt;T \) iff there exists \( x\in G \)
such that \( x\in S \), \( x\notin T \) and \( y\in S \) iff \( y\in T \)
for all \( y&lt;x \) in \( G \). When \( H \) acts on \( G \), the
subsets of \( G \) are partitioned into orbits. A subset \( S\subseteq G \)
is canonical, if it is the minimum of its orbit: \( S=\textrm{min}S^{H} \).

As the simplistic method of testing the canonicity of \( S \) by computing
\( S^{\psi } \) for every \( \psi \in H \) would be prohibitively
laborious for groups with large \( \left| H\right|  \), we limit the
canonicity testing to a left transversal of \(H\). A \emph{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}}\subseteq H \)
that fixes \( 0 \) and \( g_{0} \) pointwise. For every \( \left( g_{1},g_{2}\right)  \)
where \( g_{2}-g_{1} \) is of maximum order there is a \( \psi \in T \)
such that \( \left( g_{1},g_{2}\right) ^{\psi ^{-1}}=\left( 0,g_{0}\right)  \).
In testing \( S\subseteq G \) for canonicity, we determine all pairs
\( \left( g_{1},g_{2}\right)  \) such that \( g_{1},g_{2}\in S \)
and \( g_{2}-g_{1} \) is an element of maximum order; for each such
pair we determine the \( \psi \in T \) for which \( \left( g_{1},g_{2}\right) ^{\psi ^{-1}}=\left( 0,g_{0}\right)  \)
and reject \( S \) as not canonical if \( S^{\psi ^{-1}}&lt;S \). If
\( S\leq S^{\psi ^{-1}} \) for all \( \psi  \) tried, we accept
\( S \) as possibly canonical.

For determining \( T \), we first choose a transversal \( T_{0} \)
of \( H_{0}\subset H \). For convenience, we choose \( T_{0} \)
to contain the mapping \( f:x\mapsto x+g \) for every \( g\in G \).
We also choose a transversal \( T_{g_{0}} \) of \( H_{0,g_{0}}\subseteq H_{0} \),
so that for every \( g\in g_{0}^{H_{0}} \) there is a \( \phi \in T_{g_{0}} \)
for which \( g_{0}^{\phi }=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 \( \left( g_{1},g_{2}\right) \in \left( 0,g_{0}\right) ^{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 \( \left( 0,g_{0}\right)  \), since sets that
contain \( 0 \) and \( g_{0} \) precede those that do not. To somewhat
justify that assumption, note that Jamison \cite{jamison:helly} proves
that for \( n&lt;2310 \), every sum cover of \( \mathbb {Z}_{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 \( \left| g_{0}^{\textrm{Aut}\left( G\right) }\right| \geq \varphi \left( \left| G\right| \right)  \),
where \( \varphi  \) denotes the Euler totient function, and equality
holds for cyclic \( G \). Since \( \left| T_{0}\right| =\left| G\right|  \),
we have \( \left| T\right| \geq \left| G\right| \varphi \left( \left| G\right| \right)  \).
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.


\section{\label{sec:search}An orderly algorithm}

Our search algorithm is a backtrack search with isomorph rejection.
It is an orderly algorithm in the style of Farad\v{z}ev \cite{faradzev:constructive}
and Read \cite{read:every}. 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 \). %: for \( S,T\subseteq X \)
%we have \( S&lt;T \) iff there exists \( x\in X \) such that \( x\in S \),
%\( x\notin T \) and \( y\in S \) iff \( y\in T \) for all \( y&lt;x \)
%in \( G \). 
A subset \( S\subseteq X \) is said to be canonical,
if \( S\leq h\left( S\right)  \) for all \( h\in H \).

\bt

When started on the empty set, the following method visits every canonical
subset of \( X \): Upon visiting a canonical subset \( S\subseteq X \),
construct each of the subsets \( S\cup \left\{ x\right\}  \) where
\( x\in X \) and \( s&lt;x \) for all \( s\in S \), and visit recursively
those newly constructed subsets that are canonical.

\et

\bp

Define \( f\left( S\right) =S\setminus \left\{ \max S\right\}  \)
for \( \emptyset \neq S\subseteq X \). Observe that \( f \) is weakly
monotonic on \( k \)-subsets: for two \( k \)-subsets \( S,T\subseteq X \),
\( S&lt;T \) implies \( f\left( S\right) \leq f\left( T\right)  \).
Also, for any \( h\in H \), \( f\left( h\left( S\right) \right) \leq h\left( f\left( S\right) \right)  \),
as both may be obtained from \( h\left( S\right)  \) by removing
an element -- the maximum element in case of \( f\left( h\left( S\right) \right)  \).
As the induction base, the null set (the only \(0\)-element subset of \(X \))
is % are
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\leq h\left( C\right)  \)
for all \( h\in H \). Since \( f \) is weakly monotonic, this implies
\( f\left( C\right) \leq f\left( h\left( C\right) \right) \leq h\left( f\left( C\right) \right)  \)
for all \( h\in H \). Since \( f\left( C\right) \leq h\left( f\left( C\right) \right)  \)
for all \( h\in H \), \( f\left( C\right)  \) is also canonical.
By the induction hypothesis, \( f\left( C\right)  \) is visited,
and therefore \( C \) is also visited.\ep

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 \ref{sec:eq},
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 \ref{sec:eq},
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\left( S\right) =\binom{\left| S\right| }{2}-\left| ss\left( S\right) \right|  \)
represent the duplication in the partial strict sum cover \( S\neq \emptyset  \).
Let \( S'=S\cup \left\{ s\right\}  \) where \( s\notin S \). Now
\( p\left( S'\right) =\binom{\left| S'\right| }{2}-\left| ss\left( S\right) \cup \left\{ s+t\mid t\in S\right\} \right| \geq \binom{\left| S\right| }{2}+\left| S\right| -\left| ss\left( S\right) \right| -\left| S\right| =p\left( S\right)  \).
Thus, as duplication can only increase when elements are added to
a partial strict sum cover, and since \( p\left( C\right) =\binom{k}{2}-\left| G\right|  \)
for a \( k \)-element strict sum cover \( C \) of \( G \), the
branches where \( p\left( S\right) &gt;\binom{k}{2}-\left| G\right|  \)
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\left( S\right) =\binom{\left| S\right| +1}{2}-\left| s\left( S\right) \right|  \)
and for difference covers with \( p\left( S\right) =\left| S\right| \left( \left| S\right| -1\right) -\left| d\left( G\right) \right|  \).


\section{\label{sec:results}Results}

We computed the minimum covers with the algorithm described for
Abelian groups of small order. The distributed batch system autoson
\cite{mckay:autoson} 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
\(\mathbb{Z}_{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\leq \left| G\right| \leq 90 \).  From
the results of these
computations and the bounds from Section 2 we obtain
\( n_{d}\left( k\right)  \) and \( n_{d}'\left( k\right)  \) for
\( k\leq 12 \), \( n_{s}\left( k\right)  \) and \( n_{s}'\left(
k\right)  \) for \( k\leq 13 \), and \( n_{ss}\left( k\right)  \)
and \( n_{ss}'\left( k\right)  \) for \( k\leq 14 \). The results
are summarized in Tables \ref{tab:vvals}, \ref{tab:vd}, \ref{tab:vs},
and \ref{tab:vss}. The remaining minimum covers computed may be
obtained by contacting the author or at
\verb+&lt;URL:http://www.tcs.hut.fi/~haha/&gt;+.

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
\cite{fitch.jamison:minimum} with one exception: we found a smaller
strict sum cover \( \left\{ 0,1,2,3,4,5,11,18,23,28,35\right\} \subset \mathbb {Z}_{41} \).
For cyclic groups of order up to 127 we obtain minimum difference
covers of the same cardinality as Wiedemann \cite{wiedemann:cyclic}.
The covers themselves cannot be compared due to a different ordering
of the elements of \( G \) in the search.

\section*{Acknowledgements}

The author wishes to thank Petteri Kaski and Patric \"Osterg\aa rd for
helpful comments and valuable discussions.

\begin{table}[h]
\caption{\label{tab:vvals}Values of \( n_{d}\left( k\right)  \),
\( n'_{d}\left( k\right)  \), \( n_{s}\left( k\right)  \),
\( n_{s}'\left( k\right)  \), \( n_{ss}\left( k\right)  \),
and \( n'_{ss}\left( k\right)  \).}
\medskip
\begin{tabular}{r|rrrrrrrrrrrrr}
\( k \) &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 &amp; 14 \\
\hline
\( n_{d}\left( k\right) \) &amp; 3 &amp; 7 &amp; 13 &amp; 21 &amp; 31 &amp; 39 &amp; 57 &amp; 73 &amp; 91
&amp; 95 &amp; 133 &amp; &amp; \\
\( n'_{d}\left( k\right) \) &amp; 3 &amp; 7 &amp; 13 &amp; 21 &amp; 31 &amp; 39 &amp; 57 &amp; 73 &amp; 91
&amp; 95 &amp; 133 &amp; &amp; \\
\( n_{s}\left( k\right) \) &amp; 3 &amp; 5 &amp; 9 &amp; 13 &amp; 19 &amp; 21 &amp; 30 &amp; 36 &amp; 43 &amp;
51 &amp; 64 &amp; 72 &amp; \\
\( n'_{s}\left( k\right) \) &amp; 3 &amp; 5 &amp; 9 &amp; 13 &amp; 19 &amp; 21 &amp; 30 &amp; 35 &amp; 43
&amp; 51 &amp; 63 &amp; 67 &amp; \\
\( n_{ss}\left( k\right) \) &amp; &amp; 3 &amp; 6 &amp; 9 &amp; 13 &amp; 20 &amp; 25 &amp; 30 &amp; 36 &amp;
42 &amp; 56 &amp; 64 &amp; 72 \\
\( n'_{ss}\left( k\right) \) &amp; &amp; 3 &amp; 6 &amp; 9 &amp; 13 &amp; 17 &amp; 24 &amp; 30 &amp; 36 &amp;
42 &amp; 56 &amp; 61 &amp; 72 \\
\end{tabular}
\end{table}
\begin{table}[p]
\caption{Difference covers that correspond to values of $n_d(k)$ and $n'_d(k)$.}\label{tab:vd}
\medskip
\begin{tabular}{rll}
$k$ &amp; $G$ &amp; a minimum difference cover\\\hline
2 &amp;  $\mathbb{Z}_{3}$ &amp; $\{0, 1\}$ \\
3 &amp;  $\mathbb{Z}_{7}$ &amp; $\{0, 1, 3\}$ \\
4 &amp;  $\mathbb{Z}_{13}$ &amp; $\{0, 1, 3, 9\}$ \\
5 &amp;  $\mathbb{Z}_{21}$ &amp; $\{0, 1, 6, 8, 18\}$ \\
6 &amp;  $\mathbb{Z}_{31}$ &amp; $\{0, 1, 3, 8, 12, 18\}$ \\
7 &amp;  $\mathbb{Z}_{39}$ &amp; $\{0, 1, 16, 20, 22, 27, 30\}$ \\
8 &amp;  $\mathbb{Z}_{57}$ &amp; $\{0, 1, 9, 11, 14, 35, 39, 51\}$ \\
9 &amp;  $\mathbb{Z}_{73}$ &amp; $\{0, 1, 3, 7, 15, 31, 36, 54, 63\}$ \\
10 &amp; $\mathbb{Z}_{91}$ &amp; $\{0, 1, 7, 16, 27, 56, 60, 68, 70, 73\}$ \\
11 &amp; $\mathbb{Z}_{95}$ &amp; $\{0, 1, 5, 8, 18, 20, 29, 31, 45, 61, 67\}$ \\
12 &amp; $\mathbb{Z}_{133}$ &amp; $\{0, 1, 32, 42, 44, 48, 51, 59, 72, 77, 97, 111\}$ \\
\end{tabular}\end{table}
\begin{table}[p]
\caption{Sum covers that correspond to values of $n_s(k)$ or $n'_s(k)$.}\label{tab:vs}
\medskip\begin{tabular}{rrlp{.6\textwidth}}
$k$ &amp; $\left|G\right|$ &amp; $G$ &amp; a minimum sum cover\\\hline
2 &amp; 3 &amp; $\mathbb{Z}_{3}$ &amp; $\{0, 1\}$ \\
3 &amp; 5 &amp; $\mathbb{Z}_{5}$ &amp; $\{0, 1, 2\}$ \\
4 &amp; 9 &amp; $\mathbb{Z}_{9}$ &amp; $\{0, 1, 3, 4\}$\\
5 &amp; 13 &amp; $\mathbb{Z}_{13}$ &amp; $\{0, 1, 2, 6, 9\}$ \\
6 &amp; 19 &amp; $\mathbb{Z}_{19}$ &amp; $\{0, 1, 3, 12, 14, 15\}$ \\
7 &amp; 21 &amp; $\mathbb{Z}_{21}$ &amp; $\{0, 1, 3, 7, 11, 15, 19\}$ \\
8 &amp; 30 &amp; $\mathbb{Z}_{30}$ &amp; $\{0, 1, 3, 9, 11, 12, 16, 26\}$ \\
9 &amp; 35 &amp; $\mathbb{Z}_{35}$ &amp; $\{0, 1, 3, 13, 15, 17, 27, 29, 30\}$ \\
9 &amp; 36 &amp; $\mathbb{Z}_{4}\!\times\!\mathbb{Z}_{3}^{2}$ &amp; $\{(0, 0, 0), (1, 0, 1), (0, 0, 1), (0, 0, 2), (1, 1, 0),$ $(1, 2, 0), (3, 0, 2), (3, 1, 0), (3, 2, 0)\}$ \\
10 &amp; 43 &amp; $\mathbb{Z}_{43}$ &amp; $\{0, 1, 2, 3, 10, 15, 21, 25, 31, 36\}$ \\
11 &amp; 51 &amp; $\mathbb{Z}_{51}$ &amp; $\{0, 1, 3, 7, 10, 15, 18, 22, 24, 25, 38\}$ \\
12 &amp; 63 &amp; $\mathbb{Z}_{63}$ &amp; $\{0, 1, 3, 8, 12, 18, 22, 27, 29, 30, 43, 50\}$ \\
12 &amp; 64 &amp; $\mathbb{Z}_{8}^{2}$ &amp; $\{(0, 0), (0, 1), (0, 4), (1, 0), (1, 2), (2, 1),$ $(2, 2), (2, 6), (4, 5), (5, 0), (5, 2), (6, 5)\}$ \\
13 &amp; 67 &amp; $\mathbb{Z}_{67}$ &amp; $\{0, 1, 2, 3, 4, 5, 6, 16, 24, 33, 40, 49, 57\}$ \\
13 &amp; 72 &amp; $\mathbb{Z}_{2}\!\times\!\mathbb{Z}_{4}\!\times\!\mathbb{Z}_{9}$ &amp; $\{(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)\}$ \\
\end{tabular}\end{table}
\begin{table}[p]
\caption{Strict sum covers that correspond to values of $n_{ss}(k)$ or $n'_{ss}(k)$.}\label{tab:vss}
\medskip
\begin{tabular}{rrlp{.6\textwidth}}
$k$ &amp; $\left|G\right|$ &amp; $G$ &amp; a minimum strict sum cover\\\hline
3 &amp; 3 &amp; $\mathbb{Z}_{3}$ &amp; $\{0, 1, 2\}$ \\
4 &amp; 6 &amp; $\mathbb{Z}_{6}$ &amp; $\{0, 1, 2, 4\}$ \\
5 &amp; 9 &amp; $\mathbb{Z}_{9}$ &amp; $\{0, 1, 2, 3, 6\}$ \\
6 &amp; 13 &amp; $\mathbb{Z}_{13}$ &amp; $\{0, 1, 2, 3, 6, 10\}$ \\
7 &amp; 17 &amp; $\mathbb{Z}_{17}$ &amp; $\{0, 1, 2, 3, 4, 8, 13\}$ \\
7 &amp; 20 &amp; $\mathbb{Z}_{2}^{2}\!\times\!\mathbb{Z}_{5}$ &amp; $\{(0, 0, 0), (0, 1, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4),$ $(1, 0, 1), (1, 1, 1)\}$ \\
8 &amp; 24 &amp; $\mathbb{Z}_{24}$ &amp; $\{0, 1, 2, 4, 8, 13, 18, 22\}$ \\
8 &amp; 25 &amp; $\mathbb{Z}_{5}^{2}$ &amp; $\{(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (2, 1), (3, 2), (4, 3)\}$ \\
9 &amp; 30 &amp; $\mathbb{Z}_{30}$ &amp; $\{0, 1, 2, 6, 9, 12, 16, 17, 18\}$ \\
10 &amp; 36 &amp; $\mathbb{Z}_{36}$ &amp; $\{0, 1, 4, 5, 7, 13, 18, 23, 28, 34\}$ \\
11 &amp; 42 &amp; $\mathbb{Z}_{42}$ &amp; $\{0, 1, 11, 12, 18, 22, 24, 27, 30, 32, 36\}$ \\
12 &amp; 56 &amp; $\mathbb{Z}_{56}$ &amp; $\{0, 1, 12, 15, 22, 29, 32, 43, 44, 48, 50, 52\}$ \\
13 &amp; 61 &amp; $\mathbb{Z}_{61}$ &amp; $\{0, 1, 2, 3, 4, 7, 13, 21, 29, 36, 44, 52, 58\}$ \\
13 &amp; 64 &amp; $\mathbb{Z}_{4}\!\times\!\mathbb{Z}_{16}$ &amp; $\{(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 7), (0, 13),$ $(1, 0), (1, 8), (2, 2), (2, 10), (3, 4), (3, 12)\}$ \\
14 &amp; 72 &amp; $\mathbb{Z}_{72}$ &amp; $\{0, 1, 2, 5, 12, 30, 37, 40, 41, 42, 50, 56, 58, 64\}$ \\
\end{tabular}\end{table}
\clearpage





\begin{thebibliography}{10}

\bibitem{faradzev:constructive}
I.~A. Farad{\v{z}}ev,
\newblock Constructive enumeration of combinatorial objects.
\newblock {\em Colloq. Internat. CNRS} {\bf 260} (1978), 131--135.

\bibitem{fitch.jamison:minimum}
M.~A. Fitch and R.~E. Jamison,
\newblock Minimum sum covers of small cyclic groups.
\newblock {\em Congr. Numer.} {\bf 147} (2000), 65--81.

\bibitem{graham.sloane:on}
R.~L. Graham and N.~J.~A. Sloane,
\newblock On additive bases and harmonious graphs.
\newblock {\em Siam J. Alg. Disc. Meth.} {\bf 1} (1980), 382--404.

\bibitem{haanpaa.huima.ea:sets}
H.~Haanp\"a\"a, A.~Huima, and P.~R.~J. \"Osterg\aa rd,
\newblock Sets in $\mathbb{Z}_n$ with distinct sums of pairs.
\newblock {\em Discrete Appl. Math.} {\bf 138} (2004), 99--106.

\bibitem{haanpaa.ostergrd:sets}
H.~Haanp\"a\"a and P.~R.~J. \"Osterg\aa rd,
\newblock Sets in {A}belian groups with distinct sums of pairs.
\newblock Research Report A87, Helsinki University of Technology, Laboratory
  for Theoretical Computer Science, Espoo, Finland, Feb. 2004.

\bibitem{jamison:helly}
R.~E. Jamison,
\newblock The {H}elly bound for singular sums.
\newblock {\em Discrete Math.} {\bf 249} (2002), 117--133.

\bibitem{jungnickel:difference}
D.~Jungnickel,
\newblock Difference sets,
\newblock in J.~H. Dinitz and D.~R. Stinson, eds., {\em Contemporary Design
  Theory: A Collection of Surveys}, Wiley, 1992, pp. 241--324.

\bibitem{mckay:autoson}
B.~D. McKay,
\newblock {a}utoson -- a distributed batch system for {UNIX} workstation
  networks (version 1.3).
\newblock Technical Report TR-CS-96-03, Department of Computer Science, The
  Australian National University, Mar. 1996.

\bibitem{read:every}
R.~C. Read,
\newblock Every one a winner {\em or} how to avoid isomorphism search when
  cataloguing combinatorial configurations.
\newblock {\em Ann. Discrete Math.} {\bf 2} (1978), 107--120.

\bibitem{shoda:uber}
K.~Shoda,
\newblock {\"U}ber die {A}utomorphismen einer endlichen {A}belschen {G}ruppe.
\newblock {\em Math. Ann.} {\bf 100} (1928), 674--686.

\bibitem{swanson:planar}
C.~N. Swanson,
\newblock Planar cyclic difference packings.
\newblock {\em J. Combin. Des.} {\bf 8} (2000), 426--434.

\bibitem{wiedemann:cyclic}
D.~Wiedemann,
\newblock Cyclic difference covers through 133.
\newblock {\em Congr. Numer.} {\bf 90} (1992), 181--185.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05B40; Secondary 20K01.

\noindent \emph{Keywords: }
Additive base, backtrack search, difference set, covering.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 11 2003;
revised versions received July 2 2003; March 16 2004; June 2 2004.
Published in {\it Journal of Integer Sequences}, June 10 2004.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in

\end{document}

</pre></body></html>