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

Понятие покрывающей системы ввёл Пал Эрдёш в начале 1930-х.

Покрывающая система называется дизъюнктной (или точной), если никакие классы вычетов не пересекаются (т.е. число не покрывается различными элементами системы).

Покрывающая система называется определённой (или неконгруэнтной), если все модули различны (и больше 1).

Покрывающая система называется несократимой (или минимальной), если все классы вычетов необходимы для покрытия целых чисел (нельзя исключить какой-либо класс).

Некоторые примеры покрывающих систем:

• ${\displaystyle \{0{\pmod {3}},\ 1{\pmod {3}},\ 2{\pmod {3}}\},}$
• ${\displaystyle \{1{\pmod {2}},\ 2{\pmod {4}},\ 4{\pmod {8}},\ 0{\pmod {8}}\},}$
• ${\displaystyle \{0(\mathrm {mod} \ {2}),\ 0(\mathrm {mod} \ {3}),\ 1(\mathrm {mod} \ {4}),\ 5(\mathrm {mod} \ {6}),\ 7(\mathrm {mod} \ {12})\}.}$

Здесь первые два примера являются дизъюнктными, а третий пример является определённым.

Система (т.е. несортированный набор множеств)

${\displaystyle \{a_{1}{\pmod {n_{1}}},\ \ldots ,\ a_{k}{\pmod {n_{k}}}\}}$

конечного числа классов вычетов называется ${\displaystyle m}$-покрытием, если она покрывает любое число по меньшей мере ${\displaystyle m}$ раз, и точным ${\displaystyle m}$-покрытием, если она покрывает каждое число в точности ${\displaystyle m}$ раз. Известно, что для любого ${\displaystyle m=2,3,\ldots }$ найдётся точное ${\displaystyle m}$-покрытие, которое нельзя записать как объединение двух покрытий. Например,

• ${\displaystyle \{1{\pmod {2}};\ 0{\pmod {3}};\ 2{\pmod {6}};\ 0,\,4,\,6,\,8{\pmod {10}}\};}$
• ${\displaystyle 1,\,2,\,4,\,7,\,10,\,13{\pmod {15}};\ 5,\,11,\,12,\,22,\,23,\,29{\pmod {30}}\}}$

являются точным 2-покрытием, которые не являются объединением двух покрытий. Первый пример также является точным ${\displaystyle 1}$-покрытием (или просто точным покрытием).

Для любого модуля ${\displaystyle m}$ точным покрытием будет система классов вычетов по этому модулю:

${\displaystyle \{0{\pmod {m}},\ 1{\pmod {m}},\ \ldots ,\ {m-1}{\pmod {m}}\}.}$

Теорема Мирского – Ньюмана, частный случай гипотезы Герцога — Шёнхайма, утверждает, что не существует дизъюнктной определённой покрывающей системы. Этот результат был высказан в виде гипотезы в 1950 Палом Эрдёшом и доказан вскоре после этого Леоном Мирским и Дональдом Ньюманом, однако их доказательство не было опубликовано. То же самое доказательство нашли независимо Гарольд Дэвенпорт и Ричард Радо[1].

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

a₁ = 20615674205555510, a₂ = 3794765361567513 (последовательность A083216 в OEIS).

В этой последовательности позиции, в которых числа делятся на простое 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). С. Л. Г. Чой показал[2], что можно построить пример для N = 20, а Пейс П. Нильсен продемонстрировал[3] существование примера для N = 40, состоящего из более чем ${\displaystyle 10^{50}}$ классов вычетов.

На вопрос Эрдёша ответил отрицательно Боб Хаф[4]. Хаф использовал локальную лемму Ловаса, чтобы показать, что существует некоторое максимальное N, которое может быть минимальным модулем покрывающей системы. Доказательство удовлетворяет принципам эффективной вычислимости, но явная граница не приведена.

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

• Китайская теорема об остатках
• Покрывающее множество
• Система остаточных классов

• Zhi-Wei Sun: Problems and Results on Covering Systems (a survey) (PDF)
• Zhi-Wei Sun: Classified Publications on Covering Systems (PDF)