Exact covering system

Ads

Covering system

In mathematics, a covering system is a collection

{a_1(mathrm{mod} {n_1}), ldots, a_k(mathrm{mod} {n_k})}

of finitely many residue classes $a_i(mathrm{mod} {n_i}) = { a_i + n_ix: x in Z }$ whose union covers all the integers.

The notion of covering system was introduced by Paul Erdős in the early 1930s.

For example:

{0(mathrm{mod} {3}), 1(mathrm{mod} {3}), 2(mathrm{mod} {3})},

and

{1(mathrm{mod} {2}), 2(mathrm{mod} {4}), 4(mathrm{mod} {8}), 0(mathrm{mod} {8})},

and

{0(mathrm{mod} {2}), 0(mathrm{mod} {3}), 1(mathrm{mod} {4}),

5(mathrm{mod} {6}), 7(mathrm{mod} {12}) }.

A covering system is called disjoint (or exact) if no two members overlap.

A covering system is called distinct (or incongruent) if all the moduli are different (and bigger than 1).

A covering system is called irredundant (or minimal) if all the residue classes are required to cover the integers.

The first two examples are disjoint.

The third example is distinct.

A system (i.e., an unordered multi-set)

{a_1(mathrm{mod} {n_1}), ldots, a_k(mathrm{mod} {n_k})}

of finitely many residue classes is called an $m$ -cover if it covers every integer at least $m$ times, and an exact $m$ -cover if it covers each integer exactly $m$ times. It is known that for each $m=2,3,ldots$ there are exactly $m$ -covers which cannot be written as a union of two covers. For example,

{1(mathrm{mod} {2}); 0(mathrm{mod} {3}); 2(mathrm{mod} {6}); 0,4,6,8(mathrm{mod} {10});

1,2,4,7,10,13(mathrm{mod} {15}); 5,11,12,22,23,29(mathrm{mod} {30})

is an exact 2-cover which is not a union of two covers.

Some unsolved problems

The following problem from Paul Erdős is unsolved: Whether for any arbitrarily large N there exists an incongruent covering system the minimum of whose moduli is at least N. It is easy to construct examples where the minimum of the moduli in such a system is 2, or 3 (Erdős gave an example where the moduli are in the set of the divisors of 120 ); D. Swift gave an example where the minimum of the moduli is 4 (and the moduli are in the set of the divisors of 2880). S. L. G. Choi proved that it is possible to give an example for N = 20.

In another problem we want that all of the moduli (of an incongruent covering system) be odd. There is a famous unsolved conjecture from Erdős and Selfridge: an incongruent covering system (with the minimum modulus greater than 1) whose moduli are odd, does not exist. It is known that if such a system exists, the overall modulus must have at least 22 prime factors.