Covering system

In mathematics, a covering system (also called a complete residue 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.

Unsolved problems in mathematics

For any arbitrarily large natural number N does there exists an incongruent covering system the minimum of whose moduli is at least N?

Examples and definitions

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

The following are examples of covering systems:

$\{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 exact 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; a suitable cover is 0(3), 0(4), 0(5), 1(6), 1(8), 2(10), 11(12), 1(15), 14(20), 5(24), 8(30), 6(40), 58(60), 26(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^[1] that it is possible to give an example for N = 20, and Pace P Nielsen demonstrates^[2] the existence of an example with N = 40, consisting of more than 10⁵⁰ congruences.

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^[3].

See also

• Chinese remainder theorem
• Covering set
• Residue number system
• Herzog–Schönheim conjecture

References

1. ^ S. L. G. Choi (1971). "Covering the set of integers by congruence classes of distinct moduli". Math. Comp. (Mathematics of Computation, Vol. 25, No. 116) 25 (116): 885–895. doi:10.2307/2004353. JSTOR 2004353. 
2. ^ Pace P. Nielsen (2009). "A covering system whose smallest modulus is 40". Journal of Number Theory 129 (3): 640–666. doi:10.1016/j.jnt.2008.09.016. http://www.wiskundemeisjes.nl/wp-content/uploads/2009/02/sdarticle.pdf. 
3. ^ Song Guo; Zhi-Wei Sun (14 September 2005). "On odd covering systems with distinct moduli". Adv. Appl. Math. , --187 35 (182). arXiv:math/0412217. 

• Richard K. Guy (2004). Unsolved Problems in Number Theory. Springer-Verlag. pp. 383–385. ISBN 0-387-20860-7. 

External links

• Zhi-Wei Sun: Problems and Results on Covering Systems (a survey) (PDF)
• Zhi-Wei Sun: Classified Publications on Covering Systems (PDF)