Definitions
Nearby Words

# Covering system

In mathematics, a covering system is a collection

$\left\{a_1\left(mathrm\left\{mod\right\} \left\{n_1\right\}\right), ldots, a_k\left(mathrm\left\{mod\right\} \left\{n_k\right\}\right)\right\}$

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

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

For example:

$\left\{0\left(mathrm\left\{mod\right\} \left\{3\right\}\right), 1\left(mathrm\left\{mod\right\} \left\{3\right\}\right), 2\left(mathrm\left\{mod\right\} \left\{3\right\}\right)\right\},$

and

$\left\{1\left(mathrm\left\{mod\right\} \left\{2\right\}\right), 2\left(mathrm\left\{mod\right\} \left\{4\right\}\right), 4\left(mathrm\left\{mod\right\} \left\{8\right\}\right), 0\left(mathrm\left\{mod\right\} \left\{8\right\}\right)\right\},$

and

$\left\{0\left(mathrm\left\{mod\right\} \left\{2\right\}\right), 0\left(mathrm\left\{mod\right\} \left\{3\right\}\right), 1\left(mathrm\left\{mod\right\} \left\{4\right\}\right),$
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)

$\left\{a_1\left(mathrm\left\{mod\right\} \left\{n_1\right\}\right), ldots, a_k\left(mathrm\left\{mod\right\} \left\{n_k\right\}\right)\right\}$

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,

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

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

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.