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:

“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)

“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)