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

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

Формальная постановка задачи

Пусть $A = {a i}$ и $B = {b j}$ — два дополнительных подмножества , расщепление множества натуральных чисел ${1, 2, \dots, 2 n}$ , такие, что оба имеют одинаковую мощность , а именно $n$ . Обозначим через $M k$ количество решений уравнения $a i - b j = k$ , где $k$ — целое число, варьирующееся от $-2 n до 2 n$ . $M (n)$ определяется как:

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

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

История

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

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

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

Ниже

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

Верхний

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Гай, Ричард К. (2004). «С17». В Бенчате, Каталин А.; Халмос, Пол Р. (ред.). Нерешенные проблемы теории чисел . Нью-Йорк: Springer Science+Business Media Inc., стр. 199–200. ISBN 0-387-20860-7 .
^ Jump up to: ^а ^б ^с ^д Финч, Стивен (2 июля 2004 г.). «Проблема минимального перекрытия Эрдеша» (PDF) . Архивировано из оригинала (PDF) 5 апреля 2015 года . Проверено 15 декабря 2013 г.
^ П. Эрдеш: Некоторые замечания по теории чисел (на иврите), Riveon Lematematika 9 (1955), 45-48 MR17,460d.
^ Хогланд, Ян Кристиан. «Задача о минимальном перекрытии» . Проверено 20 сентября 2016 г.
^ Хаугланд, Ян Кристиан (1996). «Достижения в проблеме минимального перекрытия» . Журнал теории чисел . 58 (1). Огайо (США): 71–78. дои : 10.1006/jnth.1996.0064 . ISSN 0022-314X .
^ Хаугланд, Ян Кристиан (2016). «Еще раз к проблеме минимального перекрытия». arXiv : 1609.08000 [ math.GM ].
^ Уайт, Итан Патрик (2022). «Проблема минимального перекрытия Эрдёша». arXiv : 2201.05704 [ math.CO ].

[rguy-1] Jump up to: ^а ^б ^с ^д ^и Гай, Ричард К. (2004). «С17». В Бенчате, Каталин А.; Халмос, Пол Р. (ред.). Нерешенные проблемы теории чисел . Нью-Йорк: Springer Science+Business Media Inc., стр. 199–200. ISBN 0-387-20860-7 .

[finch-2] Jump up to: ^а ^б ^с ^д Финч, Стивен (2 июля 2004 г.). «Проблема минимального перекрытия Эрдеша» (PDF) . Архивировано из оригинала (PDF) 5 апреля 2015 года . Проверено 15 декабря 2013 г.

[minimum_overlap-3] П. Эрдеш: Некоторые замечания по теории чисел (на иврите), Riveon Lematematika 9 (1955), 45-48 MR17,460d.

[4] Хогланд, Ян Кристиан. «Задача о минимальном перекрытии» . Проверено 20 сентября 2016 г.

[5] Хаугланд, Ян Кристиан (1996). «Достижения в проблеме минимального перекрытия» . Журнал теории чисел . 58 (1). Огайо (США): 71–78. дои : 10.1006/jnth.1996.0064 . ISSN 0022-314X .

[6] Хаугланд, Ян Кристиан (2016). «Еще раз к проблеме минимального перекрытия». arXiv : 1609.08000 [ math.GM ].

[7] Уайт, Итан Патрик (2022). «Проблема минимального перекрытия Эрдёша». arXiv : 2201.05704 [ math.CO ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]