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.

Contents

Some unsolved problems

See also

External links

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].

See also

★ Chinese remainder theorem

★ Residue number system

★ Herzog-Schönheim conjecture

External links

★ Zhi-Wei Sun: Classified Publications on Covering Systems (PDF)