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

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

\{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-х годов.

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

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

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

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

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

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

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

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

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

конечного числа классов вычетов называется $m$ -cover, если оно покрывает хотя бы каждое целое число $m$ раз и точное $m$ -cover, если оно точно покрывает каждое целое число $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-покрытие (также называемое точным покрытием ). Другое широко распространенное точное покрытие — это покрытие нечетных и четных чисел , или

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

Это лишь один из случаев следующего факта: для каждого положительного целочисленного модуля $m$ , есть точная обложка:

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

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

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

Последовательности Primefree [ править ]

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

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

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

Системы нечетных модулей [ править ]

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

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

(еще нерешенные задачи по математике)

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

См. также [ править ]

Ссылки [ править ]

^ Р.Д. Хаф, П.П. Нильсен (2019). «Покрывающие системы с ограниченной делимостью». Герцог Мат. Дж . 168 (17): 3261–3295. arXiv : 1703.02133 . дои : 10.1215/00127094-2019-0058 .
^ Сойфер, Александр (2009). Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей . С предисловиями Бранко Грюнбаума, Питера Д. Джонсона-младшего и Сесила Руссо. Нью-Йорк: Спрингер. стр. 1–9. дои : 10.1007/978-0-387-74642-5 . ISBN 978-0-387-74640-1 . МР 2458293 .
^ Чой, SLG (1971). «Покрытие множества целых чисел классами сравнения различных модулей» . Математика. Комп. 25 (116): 885–895. дои : 10.2307/2004353 . МР 0297692 .
^ Нильсен, Пейс П. (2009). «Система покрытия, наименьший модуль которой равен 40» . Журнал теории чисел . 129 (3): 640–666. дои : 10.1016/j.jnt.2008.09.016 . МР 2488595 .
^ Хаф, Боб (2015). «Решение задачи минимального модуля покрытия систем». Энн. математики. 181 (1): 361–382. arXiv : 1307.0874 . дои : 10.4007/анналы.2015.181.1.6 . МР 3272928 .
^ Го, Сун; Сунь, Чжи-Вэй (2005). «О нечетных накрывающих системах с различными модулями». Адв. Прил. Математика . 35 (2): 182–187. arXiv : math/0412217 . дои : 10.1016/j.aam.2005.01.004 . МР 2152886 .

Внешние ссылки [ править ]

Чжи-Вэй Сунь : Проблемы и результаты по накрывающим системам (обзор) ( PDF )
Чжи-Вэй Сунь: Классифицированные публикации по системам прикрытия (PDF), заархивировано 29 сентября 2007 г. в Wayback Machine.

[1] Р.Д. Хаф, П.П. Нильсен (2019). «Покрывающие системы с ограниченной делимостью». Герцог Мат. Дж . 168 (17): 3261–3295. arXiv : 1703.02133 . дои : 10.1215/00127094-2019-0058 .

[soifer-2] Сойфер, Александр (2009). Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей . С предисловиями Бранко Грюнбаума, Питера Д. Джонсона-младшего и Сесила Руссо. Нью-Йорк: Спрингер. стр. 1–9. дои : 10.1007/978-0-387-74642-5 . ISBN 978-0-387-74640-1 . МР 2458293 .

[3] Чой, SLG (1971). «Покрытие множества целых чисел классами сравнения различных модулей» . Математика. Комп. 25 (116): 885–895. дои : 10.2307/2004353 . МР 0297692 .

[4] Нильсен, Пейс П. (2009). «Система покрытия, наименьший модуль которой равен 40» . Журнал теории чисел . 129 (3): 640–666. дои : 10.1016/j.jnt.2008.09.016 . МР 2488595 .

[5] Хаф, Боб (2015). «Решение задачи минимального модуля покрытия систем». Энн. математики. 181 (1): 361–382. arXiv : 1307.0874 . дои : 10.4007/анналы.2015.181.1.6 . МР 3272928 .

[6] Го, Сун; Сунь, Чжи-Вэй (2005). «О нечетных накрывающих системах с различными модулями». Адв. Прил. Математика . 35 (2): 182–187. arXiv : math/0412217 . дои : 10.1016/j.aam.2005.01.004 . МР 2152886 .

[1]

[2]

[3]

[4]

[5]

[6]