Covering system

From Wikipedia, the free encyclopedia

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.

[edit] 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 [1].