Система покрытия

В математике покрывающая система ( также называемая полной системой вычетов ) — это совокупность

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

конечного числа остаточных классов

${\displaystyle a_{i}{\pmod {n_{i}}}=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \},}$

объединение которых содержит все целые числа.

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

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

Ниже приведены примеры систем покрытия:

1. ${\displaystyle \{0{\pmod {3}},\ 1{\pmod {3}},\ 2{\pmod {3}}\},}$
2. ${\displaystyle \{1{\pmod {2}},\ 2{\pmod {4}},\ 4{\pmod {8}},\ 0{\pmod {8}}\},}$
3. ${\displaystyle \{0{\pmod {2}},\ 0{\pmod {3}},\ 1{\pmod {4}},\ 5{\pmod {6}},\ 7{\pmod {12}}\}.}$

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

Система покрытия называется различной (или неконгруэнтной ), если все модули различны (и больше 1). Хаф и Нильсен (2019) ^[1] доказали, что любая различная система покрытия имеет модуль, делящийся либо на 2, либо на 3. ${\displaystyle n_{i}}$

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

Первые два примера не пересекаются.

Третий пример особенный.

Система (т.е. неупорядоченное мультимножество)

${\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-покрытием, которое не является объединением двух покрытий.

Первый пример выше — это точное 1-покрытие (также называемое точным покрытием ). Другое точное покрытие, которое часто используется, — это покрытие нечетных и четных чисел , или

${\displaystyle \{0{\pmod {2}},\ 1{\pmod {2}}\}.}$

Это всего лишь один случай следующего факта: для каждого положительного целого модуля существует точное покрытие: ${\displaystyle m}$

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

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

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

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

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

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

В этой последовательности позиции, в которых числа в последовательности делятся на простое число p, образуют арифметическую прогрессию; например, четные числа в последовательности — это числа a _i, где i сравнимо с 1 по модулю 3. Прогрессии, делящиеся на различные простые числа, образуют покрывающую систему, показывающую, что каждое число в последовательности делится по крайней мере на одно простое число.

Ограниченность наименьшего модуля

Пол Эрдёш задался вопросом, существует ли для любого произвольно большого N неконгруэнтная покрывающая система, минимум модулей которой равен по крайней мере N. Легко построить примеры, где минимум модулей в такой системе равен 2 или 3 (Эрдёш привел пример, где модули находятся во множестве делителей числа 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). SLG Choi доказал ^[3] , что можно привести пример для N = 20, а Pace P Nielsen демонстрирует ^[4] существование примера с N = 40, состоящего из более чем сравнений. Tyler Owens ^[5] демонстрирует существование примера с N = 42 . ${\displaystyle 10^{50}}$

Боб Хоф дал отрицательный ответ на вопрос Эрдёша. ^[6] Хоф использовал локальную лемму Ловаса , чтобы показать, что существует некое максимальное значение N <10 ¹⁶ , которое может быть минимальным модулем на покрывающей системе.

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

Нерешенная задача по математике :

Существует ли система покрытия с нечетными различными модулями?

(еще нерешенные проблемы по математике)

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

Смотрите также

• Китайская теорема об остатках
• Комплект для покрытия
• Система остаточных чисел

Ссылки

1. RD Hough, PP Nielsen (2019). «Покрытие систем с ограниченной делимостью». Duke Math. J . 168 (17): 3261–3295. arXiv : 1703.02133 . doi :10.1215/00127094-2019-0058.
2. Сойфер, Александр (2009). Математическая раскраска: математика раскрашивания и красочная жизнь ее создателей . С предисловиями Бранко Грюнбаума, Питера Д. Джонсона-младшего и Сесила Руссо. Нью-Йорк: Springer. стр. 1–9. doi :10.1007/978-0-387-74642-5. ISBN 978-0-387-74640-1. МР  2458293.
3. Чой, SLG (1971). «Покрытие множества целых чисел классами конгруэнтности различных модулей». Math. Comp. 25 (116): 885–895. doi : 10.2307/2004353 . MR  0297692.
4. Нильсен, Пейс П. (2009). «Покрывающая система, наименьший модуль которой равен 40». Журнал теории чисел . 129 (3): 640–666. doi : 10.1016/j.jnt.2008.09.016 . MR  2488595.
5. Оуэнс, Тайлер (2014-12-01). "Система покрытия с минимальным модулем 42". BYU ScholarsArchive .
6. Хаф, Боб (2015). «Решение проблемы минимального модуля для покрывающих систем». Ann. of Math. 181 (1): 361–382. arXiv : 1307.0874 . doi :10.4007/annals.2015.181.1.6. MR  3272928.
7. Го, Сун; Сан, Чжи-Вэй (2005). «О нечетных системах покрытий с различными модулями». Adv. Appl. Math . 35 (2): 182–187. arXiv : math/0412217 . doi :10.1016/j.aam.2005.01.004. MR  2152886.

Внешние ссылки

• Чжи-Вэй Сан : Проблемы и результаты систем покрытия (обзор) ( PDF )
• Чжи-Вэй Сан: Секретные публикации о системах покрытия (PDF) Архивировано 29.09.2007 на Wayback Machine