ON A CONJECTURE OF R.J.SIMPSON ABOUT EXACT COVERING CONGRUENCES

Doron ZEILBERGER

Department of Mathematics, Drexel University,Philadelphia, PA19104. Current Address (1990-): Department of Mathematics, Temple University,Philadelphia, PA19122. Expanded version of a note that appeared in: Amer. Math. Monthly 96 (1989), 243. A 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 ≡ 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

∑_{i=1}^{t} 1/d_{i} = 1.  (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 α, there exists a partition of D ,

D = D_{0} ∪ D_{1} ∪ ... ∪ D_{p}

with the properties

(i) d_{i}ϵD_{0} if and if (d_{i}, p^{α}) < p^{α}, (ii) The sum

∑_{d_{i}ϵ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(mod6) and b(mod35) 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 α = 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 α > 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 counterexample 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, New results for covering systems of residue sets, Bulletin ( New Series) of the Amer. Math. Soc. 14( 1986), 121-125.

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

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

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