
%begin macros
\parskip=8pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
%end macros
\rm

\centerline
{\bf ON A CONJECTURE OF R.J.SIMPSON ABOUT EXACT COVERING CONGRUENCES}
\medskip
\centerline
{\it Doron ZEILBERGER}

Department of Mathematics, Drexel University,Philadelphia, PA19104.

Current Address (1990-): 
Department of Mathematics, Temple University,Philadelphia, PA19122.


{\bf Expanded version of a note that appeared in: 
Amer. Math. Monthly 96 (1989), 243.}

A {\it disjoint covering system} (henceforth, DCS) is a finite set
of ordered pairs of integers

$$
  \{ < a_i , d_i > : i=1,2, ... , t \} 
$$

with the property that every integer n satisfies exactly one
congruence  $ n \equiv a_i ( modd_i ) $.  The integers 
$ d_i $ will be called the moduli of the DCS.  In recent years
DCS's have attracted considerable interest ( see [2], section F14).
Very recently Berger, Felzenbaum, and Fraenkel ([1] and its
references) introduced their powerful  "parallelotope method" that
enabled them to solve many open problems in this field.  

In this note I will give a counter-example to the following
conjecture of R.J.Simpson in [3].  It was concocted by the aid of the
above mentioned Berger-Felzenbaum-Fraenkel parallelotope method .

CONJECTURE: Let D = { $ d_1 , ... , d_t $ } be a sequence of
positive integers with the property that

$$
 \sum_{i=1}^{t} 1/ d_i = 1. 
\eqno(1)
$$          

Then there exists a DCS whose sequence of moduli is D if and only if
for each prime p, and for each positive integer $\alpha$, there
exists a partition of D ,

$$
  D= D_0 \cup D_1 \cup ... \cup D_p 
$$

with the properties

(i) $ d_i  \epsilon  D_0 $ if and if $ ( d_i , p^{\alpha} )$
$< p^{\alpha} $,

(ii) The sum

$$
  \sum_{ d_i  \epsilon  D_j } 1/ d_i  
$$

is constant for $j=1,2, ... , p$.

Consider the set of moduli $D=\{6, 15, 35, 14, 210 ( 140 \,\,times )\}$.
Since 6 and 35 are relatively prime, it can not be the sequence of
moduli of a DCS ( by the Chinese remainder theorem $a ( mod 6 )$ and 
$b (mod 35)$ can never be disjoint, no matter how we choose $a$ and $b$).
However, it is easy to see that both conditions are fulfilled. 
Condition 1 is immediate while for condition 2 we have, for 
$\alpha =1$ :

   p=2 : $ D_0 = \{15,35\}$,$D_1 = \{6, 210 (60 \,\, times)\}$, 
$D_2= \{ 14, 210 ( 80 \,\, times )\}$.

   p=3: $ D_0 $= $\{35, 14\}$, $D_1 $ = $\{6, 210 ( 28 \,\,times)\}$, 
$D_2 $= $\{15, 210 (49 \,\,times )\}$, $ D_3  = \{ 210 ( 63 \,\,times)\}$.

   p=5 : $D_0 =\{6,14\}$, $D_1 =\{15, 210 ( 18 \,\,times)\}$, 
       $D_2 = \{35, 210 ( 26 \,\,times )\}$, 
$D_3 $=$D_4$=$D_5$=$\{210 ( 32 \,\,times)\}$.

   p=7 : $D_0$=$\{6,15\}$, $D_1 $= $\{14, 210 ( 8 \,\,times)\}$, 
$D_2 $=$\{35, 210 ( 17 \,\, times )\}$, 
$D_3 = ... = D_7 $=$\{ 210 ( 23 \,\,times )\}$.

For all other primes, and for $\alpha > 1$, $D_0 =D$, and all the
$D_j $ are empty.

Simpson's conjecture modified an earlier conjecture of Znam[4]. 
Simpson[3] found a counter-example to Znam's conjecture and replaced
it by the above conjecture, that we saw was also false.  The problem
that these conjectures address is that of characterizing sequences
of moduli of DCS, which according to Richard Guy ([1], F14) is "the
main outstanding problem" of the field.  This problem has the
following practical application. t persons: 1,2,$...$,t, share one
job and one office. Each of them has a part time position 
( the $ i^{th} $ has a 1/$d_i$ position), that total one whole
position.  Each of them has to show up at regular intervals ,
(the $ i^{th} $ shows up every $d_i$ days, i=1,..., t).  Find
necessary and sufficient conditions that it would be possible to
schedule them in such a way that every day exactly one person shows
up to work. 

As a closing remark let me mention that the above counter-example
generalizes to D= { $p_1 p_2 $, $p_2 p_3 $, 
$p_3 p_4$, $p_4 p_1$, 
$p_1 p_2 p_3 p_4 $ ( A times)}, where 
$A= p_1 p_2 p_3 p_4 - p_1 p_2 - p_2 p_3 - p_3 p_4 - p_4 p_1$, and 
$p_1 , p_2 , p_3 , p_4 $ are primes.

REFERENCES:

1.Marc A.Berger, Alexander Felzenbaum, and Aviezri S.Fraenkel,
{\it New results for covering systems of residue sets}, Bulletin (
New Series) of the Amer. Math. Soc. {\bf 14}( 1986), 121-125.

2.Richard K.Guy, "Unsolved Problems in Number Theory",
Springer-Verlag, 1980.

3.R.J.Simpson,{\it Disjoint covering systems of congruences}, Amer.
Math. Monthly {\bf 94} (1987), 865-868.

4.S.Znam, {\it A Survey of covering systems of congruences}, Acta.
Math. Univ. Comenian., 40-41 (1982), 59-72.

\end














