Covering system

Last updated

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

Contents

of finitely many residue classes

whose union contains every integer.

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:

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

of finitely many residue classes is called an -cover if it covers every integer at least times, and an exact-cover if it covers each integer exactly times. It is known that for each there are exact -covers which cannot be written as a union of two covers. For example,

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

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

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]

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 [3] that it is possible to give an example for N = 20, and Pace P Nielsen demonstrates [4] the existence of an example with N = 40, consisting of more than congruences. Tyler Owens [5] demonstrates the existence of an example with N = 42.

Erdős's question was resolved in the negative by Bob Hough. [6] 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?

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

See also

Related Research Articles

<span class="mw-page-title-main">Chinese remainder theorem</span> Theorem for solving simultaneous congruences

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

<span class="mw-page-title-main">Modular arithmetic</span> Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence. The conjecture has been shown to hold for all positive integers up to 2.95×1020, but no general proof has been found.

<span class="mw-page-title-main">Gaussian integer</span> Complex number whose real and imaginary parts are both integers

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as or

This article collects together a variety of proofs of Fermat's little theorem, which states that

In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

<span class="mw-page-title-main">Partition function (number theory)</span> The number of partitions of an integer

In number theory, the partition functionp(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie–Hellman key exchange and RSA public/private keys.

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery.

A residue numeral system (RNS) is a numeral system representing integers by their values modulo several pairwise coprime integers called the moduli. This representation is allowed by the Chinese remainder theorem, which asserts that, if M is the product of the moduli, there is, in an interval of length M, exactly one integer having any given set of modular values. Using a residue numeral system for arithmetic operations is also called multi-modular arithmetic.

A divisibility rule is a shorthand and useful way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits. Although there are divisibility tests for numbers in any radix, or base, and they are all different, this article presents rules and examples only for decimal, or base 10, numbers. Martin Gardner explained and popularized these rules in his September 1962 "Mathematical Games" column in Scientific American.

<span class="mw-page-title-main">Carmichael function</span> Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael functionλ(n) of a positive integer n is the smallest member of the set of positive integers m having the property that

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number p, then this root can be lifted to a unique root modulo any higher power of p. More generally, if a polynomial factors modulo p into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of p.

A Giuga number is a composite number n such that for each of its distinct prime factors pi we have , or equivalently such that for each of its distinct prime factors pi we have .

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as

Pocklington's algorithm is a technique for solving a congruence of the form

An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval [0,1) is the Inversive congruential generator with prime modulus. A generalization for arbitrary composite moduli with arbitrary distinct primes will be present here.

In number theory, a kth root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n; that is, a solution x to the equation . If k is the smallest such exponent for x, then x is called a primitive kth root of unity modulo n. See modular arithmetic for notation and terminology.

References

  1. R. D. Hough, P. P. Nielsen (2019). "Covering systems with restricted divisibility". Duke Math. J. 168 (17): 3261–3295. arXiv: 1703.02133 . doi:10.1215/00127094-2019-0058.
  2. Soifer, Alexander (2009). 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. pp. 1–9. doi:10.1007/978-0-387-74642-5. ISBN   978-0-387-74640-1. MR   2458293.
  3. 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 . MR   0297692.
  4. 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 . MR   2488595.
  5. Owens, Tyler (2014-12-01). "A Covering System with Minimum Modulus 42". BYU ScholarsArchive.
  6. Hough, Bob (2015). "Solution of the minimum modulus problem for covering systems". Ann. of Math. 181 (1): 361–382. arXiv: 1307.0874 . doi:10.4007/annals.2015.181.1.6. MR   3272928.
  7. Guo, Song; Sun, Zhi-Wei (2005). "On odd covering systems with distinct moduli". Adv. Appl. Math. 35 (2): 182–187. arXiv: math/0412217 . doi:10.1016/j.aam.2005.01.004. MR   2152886.