Проблема минимального перекрытия - Minimum overlap problem

В теория чисел и теория множеств, то проблема минимального перекрытия проблема, предложенная Венгерский математик Пол Эрдёш в 1955 г.^[1][2]

Формальная постановка проблемы

Позволять А = {а_я} и B = {б_j} быть двумя дополнительные подмножества, расщепление множества натуральные числа {1, 2, …, 2п}, так что оба имеют одинаковые мощность, а именно п. Обозначим через M_k количество решений уравнения а_я − б_j = k, куда k является целое число варьируется между −2п и 2п. M (п) определяется как:

${\displaystyle M(n):=\min _{A,B}\max _{k}M_{k}.\,\!}$

Проблема в том, чтобы оценить M (п) когда п достаточно большой.^[2]

История

Эту проблему можно найти среди проблем, предложенных Пол Эрдёш в комбинаторная теория чисел, известный среди англоговорящих людей как Проблема минимального перекрытия. Впервые он был сформулирован в 1955 г. в статье Несколько замечаний по теории чисел из Riveon Lematematica, и стала одной из классических проблем, описанных Ричард К. Гай в его книге Нерешенные проблемы теории чисел.^[1]

Частичные результаты

С тех пор, как она была сформулирована впервые, в расчетах нижняя граница и верхняя граница из M (п), со следующими результатами:^[1][2]

Ниже

Ограничить низшее	Авторы)	Год
${\displaystyle M(n)>n/4}$	П. Эрдёш	1955
${\displaystyle M(n)>(1-2^{-1/2})\,n}$	П. Эрдёш, Шерк	1955
${\displaystyle M(n)>(4-6^{-1/2})\,n/5}$	С. Сверчковски	1958
${\displaystyle M(n)>(4-15^{1/2})^{1/2}\,(n-1)}$	Л. Мозер	1966
${\displaystyle M(n)>(4-15^{1/2})^{1/2}\,n}$	Дж. К. Хаугланд	1996

Верхний

Предел высшего	Авторы)	Год
${\displaystyle M(n)<(1+o(1))n/2}$	П. Эрдёш	1955
${\displaystyle M(n)<(1+o(1))2n/5}$	Т. С. Моцкин, К. Э. Ральстон и Дж. Л. Селфридж,	1956
${\displaystyle M(n)<(1+o(1))0.382002...n}$	Дж. К. Хаугланд	1996
${\displaystyle M(n)<(1+o(1))0.380926...n}$	Дж. К. Хаугланд	2016

Дж. К. Хаугланд показал, что предел из M (п) / п существует и что оно меньше 0,385694. За свои исследования он был удостоен премии конкурса молодых ученых в 1993 году.^[3] В 1996 году он улучшил верхнюю границу до 0,38201, используя результат Питер Суиннертон-Дайер.^[4][2] Теперь он был дополнительно улучшен до 0,38093.^[5]

Первые известные значения M(п)

Ценности M (п) для первых 15 натуральных чисел следующие:^[1]

${\displaystyle n\,\!}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
${\displaystyle M(n)\,\!}$	1	1	2	2	3	3	3	4	4	5	5	5	6	6	6	...

Это просто Закон малых чисел что это ${\displaystyle \textstyle \lfloor 5(n+3)/13\rfloor }$^[1]

Рекомендации

1. Гай, Ричард К. (2004). «C17». В Bencsáth, Katalin A .; Халмос, Пол Р. (ред.). Нерешенные проблемы теории чисел. Нью-Йорк: Springer Science + Business Media Inc., стр. 199–200. ISBN  0-387-20860-7.
2. Финч, Стивен (2 июля 2004 г.). «Проблема минимального перекрытия Эрдеша» (PDF). Архивировано из оригинал (PDF) 5 апреля 2015 г.. Получено 15 декабря 2013.
3. Хаугланд, Ян Кристиан. «Проблема минимального перекрытия». Получено 20 сентября 2016.
4. Хаугланд, Ян Кристиан (1996). «Успехи в решении проблемы минимального перекрытия». Журнал теории чисел. Огайо (США). 58 (1): 71–78. Дои:10.1006 / jnth.1996.0064. ISSN  0022-314X.
5. Хаугланд, Ян Кристиан (2016). «Еще раз о проблеме минимального перекрытия». arXiv:1609.08000 [math.GM ].