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

Покрывающая система (или полная покрывающая система) — это набор

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

конечного числа классов вычетов $a_{i}{\pmod {n_{i}}}=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \}$, объединение которых покрывает все целые числа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

• Zhi-Wei Sun: Problems and Results on Covering Systems Архивная копия от 3 марта 2016 на Wayback Machine (a survey) (PDF)
• Zhi-Wei Sun: Classified Publications on Covering Systems Архивная копия от 29 сентября 2007 на Wayback Machine (PDF)