Покрывающая система

Покрывающая система (или полная покрывающая система) — это набор
{a1(mod n1), , ak(mod nk)}

 конечного числа классов вычетов ai(mod ni)={ai+nix: x\Z}, объединение которых покрывает все целые числа.

Примеры и определения


 Понятие покрывающей системы ввёл Пал Эрдёш в начале 1930-х.
 Примеры покрывающих систем:
{0(mod 3), 1(mod 3), 2(mod 3)},

{1(mod 2), 2(mod 4), 4(mod 8), 0(mod 8)},

{0(mod 2), 0(mod 3), 1(mod 4), 5(mod 6), 7(mod 12)}.

 Покрывающая система называется дизьюнктной (или точной), если никакие вычеты не относятся к одному и тому же числу (т.е. число не покрывается различными элементами системы).
 Покрывающая система называется определённой (или неконгруэнтной), если все модули отличаются (и больше 1).
 Покрывающая система называется несократимой (или минимальной), если все классы вычетов необходимы для покрытия целых чисел (нельзя исключить какой-либо класс).
 Первые два примера являются дизьюнктными.
 Третий пример является определённым.
 Система (т.е. несортированный набор множеств)
{a1(mod n1), , ak(mod nk)}

 бесконечного числа классов вычетов называется m-покрытием, если она покрывает любое число по меньшей мере m раз, и точным m-покрытием, если она покрывает каждое число в точности m раз. Известно, что для любых m=2,3, имеется точное m-покрытие, которое нельзя записать как объединение двух покрытий. Например,
{1(mod 2); 0(mod 3); 2(mod 6); 0,4,6,8(mod 10);

1,2,4,7,10,13(mod 15); 5,11,12,22,23,29(mod 30)}

 является точным 2-покрытием, которое не является объединением двух покрытий.

Теорема Мирского–Ньюмана


 Теорема Мирского – Ньюмана, частный случай , утверждает, что не существует дизъюнктной определённой покрывающей системы. Этот результат был высказан в виде гипотезы в 1950 Палом Эрдёшом и доказан вскоре после этого и , однако их доказательство не было опубликовано. То же самое доказательство нашли независимо и .

Свободные от простых чисел последовательности


 Покрывающие системы можно использовать для поиска , последовательностей целых чисел, удовлетворяющих тому же рекуррентному соотношению, которому удовлетворяют числа Фибоначчи, и таких, что соседние числа в последовательности взаимно просты, но все числа в последовательности являются составными. Например, последовательность этого типа, найденная , начинается с

a1 = 20615674205555510, a2 = 3794765361567513 .
  В этой последовательности позиции, в которых числа делятся на простое p, образуют арифметичесую прогрессию. Например, индексы чётных чисел в последовательности сравнимы с 1 по модулю 3. Прогрессии для различных простых чисел образуют покрывающую систему.

Ограничения на минимальный модуль


 Пал Эрёш спрашивал, существует ли для произвольно большого N неконгруэнтная покрывающая система, в которой все модули не меньше N. Достаточно просто построить примеры, в которых минимальный модуль равен 2 или (Эрдёш привёл пример, в котором модули являются делителями числа 120, покрытием будет 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) ). Д. Свифт дал пример, в котором минимальный модуль равен 4 (и модули являются делителями числа 2880). С. Л. Г. Чой показал, что можно построить пример для N = 20, а Пейс П. Нильсен продемонстрировал существование примера для N = 40, состоящего из более чем 1050 классов вычетов.
 На вопрос Эрдёша ответил отрицательно Боб Хаф. Хаф использовал , чтобы показать, что существует некоторое максимальное N, которое может быть минимальным модулем покрывающей системы. Доказательство удовлетворяет принципам эффективной вычислимости, но явная граница не приведена.

Системы нечётных модулей


 Имеется знаменитая нерешённая гипотеза Эрдёша и Селфриджа — не существует определённой покрывающей системы (с минимальным модулем, большим 1), состоящей из нечётных модулей. Известно, что если такая система со свободными от квадратов модулями существует, все модули должны содержать по меньшей мере 22 простых множителя.