\documentclass[12pt]{article}
\textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt
\evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt
\parskip=10pt
\font\smallit=cmti10 \font\smalltt=cmtt10
\font\smallrm=cmr9
\usepackage{lscape}
\usepackage{latexsym}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}


\newtheorem{remark}[theorem]{Remark}


%    Absolute value notation
\newcommand{\abs}[1]{\lvert#1\rvert}

%    Blank box placeholder for figures (to avoid requiring any
%    particular graphics capabilities for printing this document).
\newcommand{\blankbox}[2]{%
  \parbox{\columnwidth}{\centering
%    Set fboxsep to 0 so that the actual size of the box will match the
%    given measurements more closely.
    \setlength{\fboxsep}{0pt}%
    \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
  }%
}

\begin{document}

\begin{center}
{\bf COMPOSITE COVERING SYSTEMS OF MINIMUM CARDINALITY} \vskip
20pt
{\bf Scott Jenkin}\\
{\smallit 8 Dargin Street, Mount Helena, WA 6082, Australia.}\\
{\tt coveringsystems@iinet.net.au}\\  \vskip 10pt
{\bf Jamie Simpson}\\
{\smallit Department of Mathematics and Statistics, Curtin
University of
Technology, GPO Box U1987, Perth WA 6001, Australia}\\
{\tt simpson@maths.curtin.edu.au}\\
\end{center}
\vskip 30pt \centerline{\smallit Received:3/17/03, Accepted: 9/23/03,
Published:9/24/03} \vskip 30pt

\centerline{\bf Abstract}

\noindent We write $S(m,a)$ for the congruence class $\{n \in
\mathbf{Z}:n\equiv a \pmod{m} \}$. A covering system of
congruences is a collection
$$\{S(m_{1},a_{1}),S(m_{2},a_{2}),\dots,S(m_{n},a_{n})\}$$ with the
property that $\cup_{i=1}^{n}S(m_{i},a_i)=\mathbf{Z}.$ Such a
system is composite and incongruent if the moduli
$\{m_i:i=1,\dots,n\}$ are composite and distinct.  We describe the
composite incongruent covering systems of minimum cardinality,
thus answering a question asked by Gerry Myerson.

\pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3
(2003), \#A13\hfill}

\thispagestyle{empty} \baselineskip=15pt \vskip 30pt


\section*{\normalsize 1. Introduction}
We write $S(m,a)$ for the congruence class $\{n \in
\mathbf{Z}:n\equiv a \pmod{m} \}$. A \textit{covering system of
congruences} is a collection

\begin{equation}
\label{cs} \{S(m_{1},a_{1}),S(m_{2},a_{2}),\dots,S(m_{n},a_{n})\},
\end{equation}

\noindent with the property that
$$\cup_{i=1}^{n}S(m_{i},a_i)=\mathbf{Z}.$$

Thus, for example, the set $\{S(2,0),S(2,1)\}$ is a covering system. The set of integers $%
\{m_{1},m_{2},\dots m_{t}\}$ is the \textit{set of moduli} of the
system. Strictly this is a multiset, since the moduli may be
repeated but it will be convenient to occasionally abuse notation
in this way. Covering systems were introduced by Erd\"{o}s in 1952
\cite{erdos} and were the subject of some of his favorite
problems.  They have generated a large literature and there are a
number of celebrated open questions concerning them.  See the
surveys \cite{Guy} and \cite{Porub}. We say the covering system
(\ref{cs}) is \textit{irredundant} if it has no proper
subcollection which is a covering system. A covering system is
\textit{incongruent} if all its moduli are distinct, and
\textit{composite} if each modulus is composite. An example of an
incongruent covering system is
$$\{S(2,0),S(3,0),S(4,1),S(6,1),S(12,11)\}.$$
\noindent The main concern of this paper is with systems that are
both composite and incongruent, which henceforth we will call
CICSs.  Examples of these will be given later.

In 1996 Cochrane and Myerson \cite{gerry1} introduced a new type
of system called a homogeneous covering system. To describe this
we write $H(m,a,b)$ for the set
$$\{(x,y) \in \mathbf{Z}^2:ax+by \equiv 0\pmod{m} \}.$$ A \textit{homogeneous covering system}
 is a collection
$\{H(m_i,a_i,b_i):i=1 \dots n\}$ with $m_1<m_2< \dots <m_n$ which
has the property that
$$\cup_{i=1}^{n}H(m_i,a_i,b_i)=\mathbf{Z}^2.$$
They showed how such a system could be constructed from a CICS.
Later Boping Jin and Myerson \cite{gerry2} showed that
\textit{every} homogeneous cover of $\mathbf{Z}^2$ can be obtained
from a CICS using the construction of \cite{gerry1}.

The archetypal example of a homogeneous covering system is
constructed using a CICS devised by John Selfridge which contains
20 moduli. This is shown in Table 1. At a meeting of the
Australian Mathematical Society Gerry Myerson asked whether any
CICS exists with fewer than 20 moduli.  This question was repeated
in \cite{Porub} and \cite{Rocky}.  In this paper we will answer
Gerry's question in the negative, and also show that besides
Selfridge's example there are five other sets of 20 moduli which
can be used to construct a CICS.

The structure of the paper is as follows. We say that a set of
integers that can be the set of moduli of a covering system is
\textit{good}. In Section 2 we describe how any good set can be
reduced to a canonical good set.  We then use known results about
covering systems to show that if a CICS has the minimum
cardinality then its moduli set can be reduced to one of a finite
(but large) collection of candidate sets.

In Section 3 we present an algorithm for testing whether or not a
set of integers is good.  In the final section we present the
results of applying the algorithm to the collection of candidate
sets.

\vskip 30pt

\section*{\normalsize 2. Finding candidate sets}

\begin{lemma} \label{Lemma1} If $\{m_1,m_2,\dots,m_n\}$ is a good set and
$\mu>1$  divides $m_i$ for some $1\le i\le n$, then
$\{m_1,m_2,\dots,m_n,\mu\} \backslash \{m_i \}$ is also good.
\end{lemma}

\noindent \textit{Proof.} Since $\{m_1,m_2,\dots,m_n\}$ is good
there exists a covering system
$$\{S(m_{1},a_{1}),S(m_{2},a_{2}),\dots,S(m_{n},a_{n})\}.$$ But
$S(\mu,a_{i}) \supseteq S(m_{i},a_{i})$ so we get another covering
system by replacing $S(m_{i},a_{i})$ with $S(\mu,a_{i}).$ \hfill $\Box$

We will write LCM for lowest common multiple throughout this
paper.

\begin{lemma} \label{Doron} Let $\{m_1,m_2,\dots,m_n\}$ be a good set
and suppose that the  primes dividing the LCM of
$m_1,m_2,\dots,m_n$ are $q_1<q_2<\dots<q_t$.  For $i=1,\dots,n$
let
$$m_i=\Pi_{j=1}^t q_j^{\alpha_{ij}}.$$ Then, writing
$p_1=2$, $p_2=3$, $p_3=5,\dots$ we get that $$\{\Pi_{j=1}^t
p_j^{\alpha_{ij}}:i=1,\dots,n\}.$$ is also good.
\end{lemma}

We omit the proof which is essentially the same as that of the
first theorem of \cite{Doron} and its corollary.

These lemmas allow us to form a canonical CICS from any CICS by
replacing the prime factors of its moduli with the lowest primes,
and replacing moduli by composite divisors wherever possible. Thus
a canonical CICS has the properties:

(a)  If, for $i\ge2,$ $p_i$ divides a modulus of the CICS then
$p_{i-1}$ divides some modulus.

(b) Any composite divisor of a modulus is also a modulus.

Recall that a covering system is \textit{irredundant} if it ceases
to be a covering system when one of its members is removed.  We
are seeking a CICS of minimum cardinality, which must necessarily
be irredundant.  The following theorem is from \cite{JS}.

\begin{theorem} \label{irredundant} If the LCM of the moduli of
an irredundant covering system has prime factorization
$\Pi_{i=1}^t p_i^{\alpha_{i}}$ then
\begin{equation} \label{regular} n \ge
\sum_{i=1}^t \alpha_i (p_i-1)+1,\end{equation} where $n$ is the
cardinality of the covering system.
\end{theorem}

From this we obtain the following.

\begin{corollary} \label{corollary 1} The LCM of
the moduli of a canonical CICS of minimum cardinality has the form
\begin{equation} \label{primes}
L=2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}
\end{equation}
where
\begin{equation} \label{alphas}{\alpha_1}+2{\alpha_2}+4{\alpha_3}+6{\alpha_4}\le
19.\end{equation}
\end{corollary}

\noindent \textit{Proof.} Suppose that (\ref{primes}) does not
hold, so that the LCM of the moduli is divisible by a prime
greater than or equal to 11. By property (a) of a canonical CICS
the LCM is also divisible by 2, 3, 5, and 7, so by the Theorem its
cardinality is at least $\sum_{i=1}^5 (p_i-1)+1=24.$ However
Selfridge's CICS contains only 20 congruences, so we have a
contradiction and (\ref{primes}) follows. Substituting into
(\ref{regular}) yields (\ref{alphas}).  \hfill $\Box$

Corollary \ref{corollary 1} and property (a) of a canonical CICS
allow us to construct a finite population of candidates for the
LCM of a canonical CICS of minimum cardinality. We simply consider
all sets of non-negative integers
$\{\alpha_1,\alpha_2,\alpha_3,\alpha_4\}$ which satisfy
(\ref{alphas}) and reject those for which one member of the set
equals zero while another with higher subscript is positive.  This
leaves 204 candidates for the LCM. This set of candidates is
reduced further with the following theorem (which will be used
again later).

\begin{theorem} \label{reciprocals} If $\{m_1,m_2,\dots,m_n\}$ is a good set then
$$\sum_{i=1}^n 1/m_i\ge 1.$$
\end{theorem}

This result is well-known (see, eg, \cite{Guy} or \cite{Porub})
and easily proved using density arguments.  From it we get the
following.

\begin{corollary} If $L$ is the LCM of the
moduli of a CICS of minimum cardinality then the sum of the
reciprocals of the 20 smallest composite divisors of $L$ is at
least 1.
\end{corollary}

Using this we reject 86 of our 204 candidates, leaving 118. Having
found a candidate for the LCM of the moduli of a minimum
cardinality canonical CICS we need to determine the sets of moduli
which have this LCM and satisfy requirement (b) of a CICS.  This
gives us 77,196 sets of integers.

\vskip 30pt

\section*{\normalsize 3. An Algorithm for Recognising the Set of Moduli of a Covering System}

In this section we consider the following decision
problem.\medskip

\noindent \textbf{Covering System}

\noindent \textit{Instance: }A multiset of integers
$\{m_{1},m_{2},\dots , m_{n}\} $.

\noindent \textit{Question: }Do there exist integers
$a_{1},a_{2},\dots , a_{n}$ such that
\[
\{S(m_{1},a_{1}),S(m_{2},a_{2}),\dots ,S(m_{n},a_{n})\}
\]
is a covering system?\medskip

We will call a Yes-instance of this question \textit{good }and a
No-instance \textit{bad. }Covering System appears to be a
difficult problem. The
following, apparently easier, problem is known to be NP-complete \cite{GJ},%
\cite{SM}.\medskip

\noindent \textbf{Simultaneous Incongruences}

\noindent \textit{Instance}: Collection $%
\{(m_{1},a_{1}),(m_{2},a_{2}),\dots ,(m_{n},a_{n})\}$ of ordered
pairs of positive integers.

\noindent \textit{Question}: Is there an integer $x$ such that,
for $1\leq
i\leq n,$ there is no $i$ for which $x\equiv a_{i}\pmod{m_{i}}$%
.\medskip

Note that the question is equivalent to asking whether
\[
\{S(m_{1},a_{1}),S(m_{2},a_{2}),\dots ,S(m_{n},a_{n})\}
\]
is \textit{not} a covering system: one can demonstrate this by
finding a single integer not contained in any of the congruence
classes.

We present an algorithm for answering the first of these
questions. Unfortunately this algorithm cannot give a positive
answer to Covering System : its output is either ``No'' or ``Don't
know''. An earlier version of the algorithm was given in
\cite{awoca}. Before presenting it we give some technical results.

Let $M=\{m_{1},m_{2},\dots ,m_{n}\}$. We say that $m_i$ is
\textit{helpful }in $M$ if $M\backslash \{m_{i}\}$ is bad but $M$
is good. Similarly we say that $m_i$ is \textit{unhelpful }in $M$
if either $M\backslash \{m_{i}\}$ is good (in which case\thinspace
$M$ is also good) or $M$ is bad (in which case $M\backslash
\{m_{i}\}$ is also bad). That is, $m_{i}$ is unhelpful if removing
$m_{i}$ from $M$ does not change $M$ from good to bad.

Let $p$ be a prime and $p^{\alpha }$ be the greatest power of $p$
dividing any member of $M$. We partition $M$ as
\[
M=M_{0}\cup M_{1}\cup ...\cup M_{\alpha },
\]
where $m\in M_{j}$ if and only if $p^{j}$ is the greatest power of
$p$ dividing $m$.

\begin{lemma}\label{3.1}
Let $M=\{m_1,\dots,m_n\}.$  Using the notation of the previous
paragraph, if there exists $j$, $0<j\leq \alpha $, such that
\begin{equation}
p^{\alpha -j}|M_{j}|+p^{\alpha -j-1}|M_{j+1}|+...+|M_{\alpha
}|<p^{\alpha -j+1}  \label{2}
\end{equation}


\noindent then each member of $\cup _{i=j}^{\alpha }M_{i}$ is
unhelpful.
\end{lemma}
\noindent \textit{Proof.} If no covering system exists with set of
moduli $M$ then all integers in $M$ are unhelpful and we are done.
So we assume that $M$ is good and let $A$ be a covering system
with set of moduli $M$ . We partition $A$ into $A_{0}\cup
A_{1}\cup ...\cup A_{\alpha }$ where $S(m,a)$ belongs to $A_{i}$
if and only if $m$ belongs to $M_{i}$.

We now prove the contrapositive of the Lemma. That is, we'll
choose an
arbitrary $j$ from $\{1,...,\alpha \}$ and assume that some element of some $%
M_{i}$, $i\geq j$, is helpful and show that (\ref{2}) does not
hold.

We see from this assumption that $A_{0}\cup A_{1}\cup ...\cup
A_{j-1}$is not a covering system. So there exists an integer, say
$x$, that does not belong to any congruence class in this
collection. Set $p^{\alpha }L$ to be the
LCM of the members of $M$ and obtain integers $x_{k}$, $%
k=1,2,...,p^{\alpha -j+1}$ satisfying

\begin{eqnarray}
x_{k} &\equiv &x \pmod{L}  \label{3} \\
x_{k} &\equiv &x+kp^{j-1} \pmod{p^{\alpha }}.  \nonumber
\end{eqnarray}

Each of these integers must belong to a congruence class in $A$.
We'll show first that none can belong to a class in $A_{0}\cup
A_{1}\cup ...\cup A_{j-1},$ then that this implies that (\ref{2})
does not hold.

Suppose $x_{k}\in S(mp^{i},a)$ for some $i\in\{1,2,\dots,\alpha\}$
where $S(mp^{i},a)\in A_{i}$ (so that $p$ does not divide $m$).
Then
\begin{equation}
x_{k}\equiv a \pmod{mp^{i}}  \label{4a}
\end{equation}
which implies $x_{k}\equiv a \pmod{m}$. From  this and (\ref{3})
we have
\[
x\equiv a\pmod{m}.
\]
>From (\ref{4a}) we also have $x_{k}\equiv a \pmod{p^{i}}$, which
by (\ref {3}) implies
\[
x+kp^{j-1}\equiv a \pmod{p^{i}}.
\]
If $i<j$ then the last two displays imply that $x\equiv a \pmod{mp^{i}}$%
, that is, $x\in S(mp^{i},a)$ contradicting the way $x$ was chosen. Thus $%
i\geq j$, and
\begin{equation}
\{x_{k}:k=1,2,...,p^{\alpha -j+1}\}\subseteq  \cup _{i=j}^{\alpha
}A_{i}.  \label{5}
\end{equation}
We now show that if $S(mp^{i},a)\in A_{i}$ then
\[
|\{x_{k}:k=1,2,...,p^{\alpha -j+1}\}\cap S(mp^{i},a)|\leq
p^{\alpha -i}|M_{i}|.
\]
This follows on noting that
\begin{eqnarray*}
S(mp^{i},a) &=&S(m,a)\cap S(p^{i},a) \\
&=&S(m,a)\cap \{\cup _{k=1}^{p^{\alpha -i}}S(p^{\alpha
},a+kp^{i})\}.
\end{eqnarray*}
Since the $x_{k}$'s belong to different congruence classes modulo
$p^{\alpha }$, each $S(p^{\alpha },a+kp^{i})$ contains only one.
Thus $S(mp^{i},a)$ contains at most $p^{\alpha -i}$ of them. This
applies to each congruence class in $A_{i}$ so the number of the
$x_{k}$ covered by congruence classes in $A_{i}$ is at most
\begin{equation}
p^{\alpha -i}|A_{i}|=p^{\alpha -i}|M_{i}|.  \label{6}
\end{equation}
So the number in all congruence classes in $\cup _{i=j}^{\alpha
}A_{i}$ is at most
\[
p^{\alpha -j}|M_{j}|+...+|M_{\alpha }|.
\]
This with (\ref{5}) implies
\[
p^{\alpha -j}|M_{j}|+...+|M_{\alpha }|\geq p^{\alpha -j+1}
\]
which is the negation of (\ref{2}) thus proving the contrapositive
of the
Lemma, and hence the Lemma.%
\hfill $\Box$

\medskip

In the algorithm presented in Section 3 we'll use this lemma to
remove unhelpful members of the set of integers which we are
testing for goodness. The next lemma allows us to apply a
recurrence in our algorithm: we show that $M$ is good if and only
if each set in a collection of smaller sets is good.

\begin{theorem}
Let $p$ be a prime and let $M$ be a good set of moduli. Write
$M=M_{0}\cup M_{1}$ where the members of $M_{1}$ are divisible by
$p$ and those of $M_{0}$ are not. Then there exists a partition of
$M_{1}$,
\[
M_{1}=D_{1}\cup D_{2}\cup ...\cup D_{p}
\]
such that $M_{0}\cup \{d/p:d\in D_{i}\}$ is good for each choice
of $i\in \{1,2,\dots,p\}.$
\end{theorem}

\noindent \textit{Proof.} Since $M$ is good there exists a
covering system $A$ with set of moduli $M.$ Choose $i\in [1,p]$
and set
\begin{eqnarray*}
A_{i} &=&\{S(m,a)\in A:S(m,a)\cap S(p,i)\neq \emptyset \} \\
D_{i} &=&\{m:S(m,a)\in A_{i},m\in M_{1}\}.
\end{eqnarray*}
It is shown in \cite{JS} that a covering system can be constructed
using the set of moduli $M^{*}=\{m/\gcd(m,p):S(m,a)\in A_{i}\}$.
Thus $M^{*}$ is good. Note that whenever $(m,p)=1$ we have
$S(m,a)\cap S(p,i)\neq \emptyset $ (by the Chinese Remainder
Theorem) so $M_{0}\subseteq M^{*}$. The other members of $M^{*}$
have the form $d/p$ where $d\in D_{i}$, thus $M_{0}\cup \{d/p:d\in
D_{i}\}$ is good.

It remains to show that the sets $D_{i}$ are disjoint. This is
obvious when we note that $S(mp,a)\cap S(p,i)\neq \emptyset $
implies $S(mp,a)\subseteq S(p,i)$ for any $m$, $p$, $a$ and $i$,
so each member of $M_{1}$ appears as a modulus of a congruence in
exactly one of the collections $A_{i}$. \hfill $\Box$

In the application we use the contrapositive of this theorem,
which we give as a corollary.

\begin{corollary} \label{3.2} We use the notation of the theorem.  If for some prime $p$ there doesnot
exist a partition for which $M_{0}\cup \{d/p:d\in D_{i}\}$ is good
for each choice of $i\in \{1,2,\dots,p\}$ then $M$ is not
good.\end{corollary}
\medskip
This result allows us to test $M$ for goodness by testing the sets
$M_{0}\cup \{d/p:d\in D_{i}\}$ for goodness which can in turn be
checked recursively. Since all partitions of $M_{1}$ must be
considered this leads to a combinatorial explosion, however one
hopes that many of the candidate sets may be eliminated quickly
using Lemmas 1 and 2. The process will terminate since with each
iteration the lowest common multiple of the moduli is decreasing.
Indeed, once all the moduli are powers of the same prime we can
end the process using the next lemma.

\begin{lemma}\label{3.3}
If $p$ is a prime and $M=\{m_{1},\dots,m_{t}\}$ is a set of (not
necessarily distinct) powers of $p$ then $M$ is good if and only
if
\begin{equation}
\sum_{i=1}^{t}1/m_{i} \geq 1.  \label{7}
\end{equation}
\end{lemma}

\noindent \textit{Proof.} Let $M$ be ordered such that $m_{1}\geq
m_{2}\geq ...\geq m_{t}.$ Note that
if $\alpha \geq \beta $ then the congruence classes $S(p^{\alpha },a)$ and $%
S(p^{\beta },b)$ are either disjoint or $S(p^{\alpha },a)\supseteq
S(p^{\beta },b).$

If (\ref{7}) holds a covering system $%
\{S(m_{1},a_{1}),S(m_{2},a_{2}),...S(m_{t},a_{t})\}$ can be
constructed as follows. Set $a_{1}=0 $, then for $j=2$ to $t$ set
$a_{j}$ to be the least positive integer not included in any of
$S(m_{1},a_{1}),S(m_{2},a_{2}),...S(m_{j-1},a_{j-1}).$ If there is
no such integer we already have a covering system and $M$ is good.
Otherwise $S(m_{j},a_{j})$ will be disjoint from the other
congruence classes. The proportion of integers in $\{1,\dots,M\}$
covered by the system is $ \sum_{i=1}^{j} 1/m_{i}.$ Since
(\ref{7}) holds this will reach $1$ for some $j\leq t$, and so $M$
is good.

If (\ref{7}) does not hold then $M$ is bad by Lemma 1.%
\hfill $\Box$
\medskip

Combining these results we construct an algorithm for testing a
set of integers for goodness.\\

\noindent \textbf{Algorithm Moduli\medskip }
\small
\newline
\hspace*{0.1in}\textbf{input }M:=\{m(1),m(2),...m(t)\};

\noindent \{Apply Theorem \ref{reciprocals}\}

\noindent\hspace*{0.1in}\textbf{If} 1/m(1)+1/m(2)+...+1/m(t) $<$ 1
\textbf{then output} ``No'', \textbf{stop}; \newline
\hspace*{0.1in}\textbf{compute} L:= lcm\{m(1),...m(t)\};
\newline
\hspace*{0.1in}\textbf{compute} prime factorisation of L:=p(1)\symbol{94}a(1)*p(2)\symbol{94%
}a(2)*...*p(s)\symbol{94}a(s);

\noindent \{Apply Lemma \ref{3.3}\}

\noindent \hspace*{0.1in}\textbf{if} s==1 \textbf{then output}
``Don't know'', \hspace*{0.1in}\textbf{stop};

\noindent \{Apply Lemma \ref{3.1}\}

\noindent\hspace*{0.1in}\textbf{for} i=1 to s  \newline
\hspace*{0.1in} \hspace*{0.1in}sum:=0;
\newline \hspace*{0.1in}\hspace*{0.1in} \textbf{for} j = a(i) to 1 step
$-1$\newline
 \hspace*{0.1in}\hspace*{0.1in}\hspace*{0.1in}  \textbf{compute} sum:=sum + p(i)\^{ }(a(i)$ - j) |\{m \in $ M : p(i) \^{ } j $\mid$ m, p(i)\^{ }%
(j+1) $\not{\mid} m \}|$  \newline
\hspace*{0.1in}\hspace*{0.1in}\hspace*{0.1in} \textbf{if }sum $<$
p(i)\^{ }(a - j + 1) \textbf{then} \textbf{call} Moduli(M
$\backslash \{ m \in $ M : p(i)\^{ }j $\mid m \})$, \textbf{stop};
\newline
\hspace*{0.1in} \hspace*{0.1in}\textbf{end};  \newline
\hspace*{0.1in}\textbf{end};

\noindent \{Apply Corollary \ref{3.2}\}

\noindent \hspace*{0.1in}\textbf{for} i:= 1 to s; \newline
 \hspace*{0.1in}\hspace*{0.1in}M0:= \{m $\in $ M : p(i) $\not{\mid} $ m\}
\newline\hspace*{0.1in}\hspace*{0.1in}M1:= \{m $\in $ M : p(i) $\mid $ m\}
\newline\hspace*{0.1in}\hspace*{0.1in}Good\underline{ }Partition\underline{
}Found:=false;
\newline
\hspace*{0.1in}\hspace*{0.1in}\textbf{for} each p(i)-partition
M1:= D(1) $\cup $ D(2) $\cup $ ...$\cup $ D(p(i)) of M1 \newline
\hspace*{0.1in}\hspace*{0.1in}\hspace*{0.1in}\textbf{if} Moduli(M0
$\cup $ \{d/p(i) : d $\in $ D(k)\}) == ``Don't know'' for all k
$\in $ \{1,...p(i)\} \newline\hspace*{0.1in}\hspace*{0.1in}
\hspace*{0.1in} \textbf{then} Good\underline{
}Partition\underline{ }Found:=true;
\newline
\hspace*{0.1in}\hspace*{0.1in}\hspace*{0.1in}\textbf{end};
\newline\hspace*{0.1in}\hspace*{0.1in}\textbf{if} Good\underline{
}Partition\underline{ }Found==false \textbf{then output} ``No'',
\textbf{stop}; \newline\hspace*{0.1in}\textbf{end}; \newline
\hspace*{0.1in}\textbf{output} ``Don't know"; \newline
\noindent\textbf{end};
\newline \normalsize

\noindent The correctness of the algorithm follows easily from the
lemmas.
\section*{\normalsize 4. Results}
The algorithm from the last section was applied to each of the
77,196 candidate sets obtained in Section 2.  It returned ``No"
for all but 6.  These were investigated by hand and it was found
in each case that it was possible to find residues $a_i$ which
produced covering systems.  The sets of moduli and residues are
shown in the following table.
\newpage
%\begin{landscape}

\vspace*{-10pt}

\begin{table} \small \setlength{\tabcolsep}{4.95pt}
\begin{tabular}{lcccccccccccccccccccc}
 \\

\multicolumn{21}{l}{   } \\

\multicolumn{21}{l}{\underline{I Selfridge's CICS has lowest
common multiple 720}} \\

$m_i$&4&8&16&6&12&24&48&9&18&36&72&144&10&20&15&30&60&45&90&180 \\

$a_i$&0&2&6&1&5&14&46&0&15&21&30&78&3&15&11&17&59&39&21&147 \\


\multicolumn{21}{l}{   } \\

\multicolumn{21}{l}{\underline{II has lowest
common multiple 1440}} \\

$m_i$&4&8&16&32&6&12&24&48&96&9&18&36&72&144&288&10&20&15&30&60 \\

$a_i$&0&2&6&14&1&5&21&14&94&0&15&3&57&30&222&3&15&11&17&59 \\


\multicolumn{21}{l}{   } \\

\multicolumn{21}{l}{\underline{III has lowest
common multiple 1440}} \\

$m_i$&4&8&16&32&6&12&24&48&96&9&18&36&10&20&15&30&60&45&90&180 \\

$a_i$&0&2&6&30&1&5&14&46&78&0&15&21&3&15&11&17&59&39&21&147 \\


\multicolumn{21}{l}{   } \\

\multicolumn{21}{l}{\underline{IV has lowest
common multiple 2880}} \\

$m_i$&4&8&16&32&64&6&12&24&48&96&192&9&18&36&72&10&20&15&30&60 \\

$a_i$&0&2&6&14&62&1&5&21&30&94&158&0&15&3&57&3&15&11&17&59 \\


\multicolumn{21}{l}{   } \\

\multicolumn{21}{l}{\underline{V has lowest
common multiple 2160}} \\

$m_i$&4&8&16&6&12&24&48&9&18&36&72&144&27&54&108&10&20&15&30&60 \\

$a_i$&0&2&6&1&5&14&46&0&15&3&30&78&21&3&93&3&15&11&17&59 \\


\multicolumn{21}{l}{   } \\

\multicolumn{21}{l}{\underline{VI has lowest
common multiple 4320}} \\

$m_i$&4&8&16&32&6&12&24&48&96&9&18&36&27&54&108&10&20&15&30&60 \\

$a_i$&0&2&6&30&1&5&14&46&78&0&15&3&21&3&93&3&15&11&17&59 \\

\multicolumn{21}{l}{   } \\


\end{tabular}

\caption{Six composite irredundant covering systems of cardinality
20, $\{S(m_i,a_i):i=1,\dots,20\}$. These have the only  possible
sets of moduli, but for each set of moduli there are many other
possible sets of residues.  The first system was discovered by
John Selfridge, the others are original to this paper.}
\end{table}
%\end{landscape}





Our argument shows these are the only canonical CICS with 20
moduli. Suppose  such a CICS exists which is not canonical, that
is, one which does not satisfy both conditions (a) and (b). Then
we'd be able to obtain a non-canonical CICS by taking one of the
sets of moduli from the table and either (a) replacing the largest
prime divisor of its LCM with the next largest prime from the set
$\{2,3,5,7\}$ or (b) replacing one of the moduli with a proper
multiple of itself.  For (b) we need only consider multiples
formed by multiplying moduli by 2, 3, 5 or 7.

These possibilities were tested on the 6 sets and no other
covering systems were found.

Finally we need to consider the possibility that there exists a
CICS with less than 20 moduli.  Such a CICS could be transformed
into covering system with 20 moduli by adding one or more extra
congruences. This new covering system would produce ``Don't know"
as output from the algorithm and so would have been found. Note
that such a covering system would not be irredundant, but the only
place we used irredundancy was in Theorem \ref{irredundant} and
Corollary \ref{corollary 1}. Inequality (\ref{alphas}) would still
apply in this case since we could remove the redundant congruences
from the covering system to form a CICS and apply Theorem
\ref{irredundant} to this.

We conclude that no composite incongruent covering systems exist
with fewer than 20 moduli, and that the only such covering systems
with 20 moduli use one of the sets in Table 1.



\begin{thebibliography}{9}
\small


\bibitem{gerry2} Boping Jin and Myerson, G., Homogeneous Covering
Congruences and Subgroup Covers, preprint.

\bibitem{gerry1}  Cochrane, T. and Myerson, G., Covering congruences in
higher dimensions, Rocky Mountain J. Math. 26(1996), 77-81.

\bibitem{erdos}  Erd\"{o}s, P., On a problem concerning systems of
congruences, Mat. Lapok 3(1952), 122-128.

\bibitem{GJ}  Garey, M.R., and Johnson, D.S., Computers and Intractability
: A Guide to the Theory of NP-completeness, San Francisco, CA,
Freeman (1979).

\bibitem{Guy}  Guy, R., Unsolved problems in Number Theory, 2nd edition, New
York, Springer-Verlag (1994).

\bibitem{Porub} Porubsk\'{y}, \v{S}. and Sch\"{o}nheim,
J., Covering Systems of Paul Erd\H{o}s Past, Present and Future,
Bolyai Soc. Math. Studies 11, Paul Erd\H{o}s and his Mathematics,
I, Budapest 2002, 581-627.

\bibitem{JS}  Simpson, R.J., Regular coverings of the integers by arithmetic
progressions, Acta Arith. 45(1985), 145-152.

\bibitem{Rocky}  Simpson, R.J., Covering systems of homogeneous congruences,
Rocky Mountain J. Math., 28(1998), 1125-1133.

\bibitem{awoca}  Simpson, R.J., Recognising the set of moduli of a covering
system, in Proc. 9th Australasian Workshop on Combinatorial
Algorithms, (1998), Curtin University of Technology, Australia,
C.S. Iliopoulos (ed), 117-123.

\bibitem{Doron}  Simpson, R.J. and Zeilberger, D., Necessary
conditions for distinct covering systems with square-free moduli,
Acta Arith., 59(1991), 59-70.

\bibitem{SM}  Stockmeyer, L.J., and Meyer, A.R., Word problems requiring
exponential time, Proc. 5th Ann. ACM Symp. on Theory of Computing,
Association for Computing Machinery, New York(1973), 1-9.
\end{thebibliography}

\end{document}
%------------------------------------------------------------------------------
% End of journal.tex
%------------------------------------------------------------------------------