Covering system

Short description: Collection of residue classes

Not to be confused with Cover system.

Not to be confused with Complete residue system modulo m.

In mathematics, a covering system (also called a complete residue system) is a collection

{a1(modn1), …, ak(modnk)}

of finitely many residue classes

ai(modni)={ai+nix: x∈ℤ},

whose union contains every integer.

## Contents

* 1 Examples and definitions
* 2 Mirsky–Newman theorem
* 2.1 Newman-Znám theorem
* 3 Primefree sequences
* 4 Boundedness of the smallest modulus
* 5 Systems of odd moduli
* 6 See also
* 7 References
* 8 External links

## 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:

1. {0(mod3), 1(mod3), 2(mod3)},
2. {1(mod2), 2(mod4), 4(mod8), 0(mod8)},
3. {0(mod2), 0(mod3), 1(mod4), 5(mod6), 7(mod12)}.

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 ni are different (and bigger than 1). Hough and Nielsen (2019)[1] proved that any distinct covering system has a modulus that is divisible by either 2 or 3.

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)

{a1(modn1), …, ak(modnk)}

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,… there are exact m-covers which cannot be written as a union of two covers. For example,

{1(mod2); 0(mod3); 2(mod6); 0,4,6,8(mod10);
1,2,4,7,10,13(mod15); 5,11,12,22,23,29(mod30)}

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

The first example above is an exact 1-cover (also called an exact cover). Another exact cover in common use is that of odd and even numbers, or

{0(mod2), 1(mod2)}.

This is just one case of the following fact: For every positive integer modulus m, there is an exact cover:

{0(modm), 1(modm), …, m−1(modm)}.

## Mirsky–Newman theorem

The Mirsky–Newman theorem, a special case of the Herzog–Schönheim conjecture, states that there is no disjoint distinct covering system. This result was conjectured in 1950 by Paul Erdős and proved soon thereafter by Leon Mirsky and Donald J. Newman. However, Mirsky and Newman never published their proof. The same proof was also found independently by Harold Davenport and Richard Rado.[2] In 1970, the Problem 8 in the Soviet mathematical olympiad for 10th grade was essentially a polygon coloring problem equivalent to the Mirsky–Newman theorem.[3]

### Newman-Znám theorem

Štefan Znám in 1968[4] and subsequently Morris Newman in 1971[5] proved a general form of Mirsky–Newman theorem, namely given a disjoint covering system, suppose the maximum of the moduli n occurs l times, then l≧p, the smallest prime dividing n. Another non-analytic proof of this general result was given in 1986.[6]

## Primefree sequences

Covering systems can be used to find primefree sequences, sequences of integers satisfying the same recurrence relation as the Fibonacci numbers, such that consecutive numbers in the sequence are relatively prime but all numbers in the sequence are composite numbers. For instance, a sequence of this type found by Herbert Wilf has initial terms

a1 = 20615674205555510, a2 = 3794765361567513 (sequence A083216 in the OEIS).

In this sequence, the positions at which the numbers in the sequence are divisible by a prime p form an arithmetic progression; for instance, the even numbers in the sequence are the numbers ai where i is congruent to 1 mod 3. The progressions divisible by different primes form a covering system, showing that every number in the sequence is divisible by at least one prime.

## Boundedness of the smallest modulus

Paul Erdős asked 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[7] that it is possible to give an example for N = 20, and Pace P Nielsen demonstrates[8] the existence of an example with N = 40, consisting of more than 1050 congruences. Tyler Owens[9] demonstrates the existence of an example with N = 42.

Erdős's question was resolved in the negative by Bob Hough.[10] Hough used the Lovász local lemma to show that there is some maximum N<1016 which can be the minimum modulus on a covering system.

## Systems of odd moduli

| Unsolved problem in mathematics:

Does there exist a covering system with odd distinct moduli?

(more unsolved problems in mathematics)

|

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 with square-free moduli, the overall modulus must have at least 22 prime factors.[11]

## See also

* Chinese remainder theorem
* Covering set
* Residue number system

## References

1. ↑ R. D. Hough, P. P. Nielsen (2019). "Covering systems with restricted divisibility". Duke Math. J. 168 (17): 3261–3295. doi:10.1215/00127094-2019-0058.
2. ↑ The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau. New York: Springer. 2009. pp. 1–9. doi:10.1007/978-0-387-74642-5. ISBN 978-0-387-74640-1.
3. ↑ Mathematical Association of America, ed (2016). Soviet Union mathematical olpympiad, grades 8, 9, and 10. Problem Books. Washington, D.C: Mathematical Association of America. ISBN 978-1-61444-408-4.
4. ↑ Combinatorial theory and its applications. 2, Colloquia mathematica Societatis János Bolyai, Amsterdam: North-Holland Publ, 1970, pp. 221-225, ISBN 978-0-7204-2037-1
5. ↑ Newman, Morris (December 1971). "Roots of unity and covering sets" (in en). Mathematische Annalen 191 (4): 279–282. doi:10.1007/BF01350330. ISSN 0025-5831. http://link.springer.com/10.1007/BF01350330.
6. ↑ Berger, M. A.; Felzenbaum, A.; Fraenkel, A. S. (September 1986). "A non-analytic proof of the newman—znám result for disjoint covering systems" (in en). Combinatorica 6 (3): 235–243. doi:10.1007/BF02579384. ISSN 0209-9683. http://link.springer.com/10.1007/BF02579384.
7. ↑ Choi, S. L. G. (1971). "Covering the set of integers by congruence classes of distinct moduli". Math. Comp. 25 (116): 885–895. doi:10.2307/2004353.
8. ↑ Nielsen, Pace P. (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.
9. ↑ Owens, Tyler (2014-12-01). "A Covering System with Minimum Modulus 42". BYU ScholarsArchive. https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=5328&context=etd.
10. ↑ Hough, Bob (2015). "Solution of the minimum modulus problem for covering systems". Ann. of Math. 181 (1): 361–382. doi:10.4007/annals.2015.181.1.6.
11. ↑ Guo, Song; Sun, Zhi-Wei (2005). "On odd covering systems with distinct moduli". Adv. Appl. Math. 35 (2): 182-187. doi:10.1016/j.aam.2005.01.004.

## External links

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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Covering system. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Covering_system&oldid=4529977"