Covering System - Examples and Definitions

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:

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)

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,

$\{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.

Read more about this topic: Covering System

Famous quotes containing the words examples and/or definitions:

“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)

“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)