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

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:

    “Histories are more full of examples of the fidelity of dogs than of friends.”
    —Alexander Pope (1688–1744)

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