Searching for Disjoint Covering Systems with Precisely One Repeated Modulus

By
Shalosh B. Ekhad, Aviezri S. Fraenkel, and Doron Zeilberger
.pdf   .ps   .tex  

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)

Written: Nov. 12, 2015.

A set of arithmetical sequences

a1 (mod m1)   , a2 (mod m2)  , ...  , ak (mod mk)  

with

m1 ≤ m2 ≤ ... ≤ mk

is called a disjoint covering system (alias exact covering system, used interchangeably) if every positive integer belongs to exactly one of these sequences.

Mirski,Newman, Davenport and Rado, famously proved that the moduli can't be all distinct. In fact the two largest moduli must be equal, i.e.
mk-1=mk
(and Berger-Felzenbaum-Fraenkel and independently, Jamie Simpson, found a much better proof later).

This raises the natural question: How close can you get to getting distinct moduli? Of course, e.g. the system
0 (mod 2)  , 1(mod 4)   , 3 (mod 8)   , 7 (mod 8)
has all distinct moduli except for the last two, and similarly for any power of 2. So there are infinitely many systems where the moduli are all distinct except the largest moduli that is only repeated twice. But these are in some sense trivial.

More generally, for any such beast with distinct moduli, except for the last that is repeated, r times, for some r, one can manufacture infinitely many examples, by the "add-2" process. Multiply all the moduli by 2 and prefix 2 at the beginning.

But if you insist that the smallest modulu is ≥3 then, for any given r, there are (conjecturally, but most probably) only finitely many such systems. This raises the natural question of finding all of them for small r.
In 1988, Berger Felezenbaum and Fraenkel characterized all such systems with up to 9 repeats of the top modulu. This was extended in 1999 by Melkamu Zeleke and Jamie Simpson to 10, 11, and 12 repeats. In this modest article, we extend this to classifying all such non-trivial systems with up to 32 repeats. All the systems that we found are indeed (provably!) correct, but unlike the previous authors, we did not bother to give rigorous proofs that the lists are complete, but we are almost certain that they are!

We provide a Maple program that would enable the interested reader to continue this search beyond. But we have better things to do.

Maple Package

BFF.txt , A Maple program that found all the results in this paper.

Input and Output files

  • If you want to see the list of all such systems up to 32 repeats, the
    input   yields the output

  • If you want to see a fully computer-generated article with the above information, the
    input   yields the output

  • If you want to see a more detailed version with all the implied infinite families (but only up to 24 repeats)
    input   yields the output

  • If you want to see a fully computer-generated article with the above information (with the implied abstract families, for up to 24 repeats), the
    input   yields the output

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page