Minimum overlap problem explained

In number theory and set theory, the minimum overlap problem is a problem proposed by Hungarian mathematician Paul Erdős in 1955.^{[1] [2]}

Formal statement of the problem

Let and be two complementary subsets, a splitting of the set of natural numbers, such that both have the same cardinality, namely . Denote by the number of solutions of the equation, where is an integer varying between . is defined as:

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

The problem is to estimate when is sufficiently large.

History

This problem can be found amongst the problems proposed by Paul Erdős in combinatorial number theory, known by English speakers as the Minimum overlap problem. It was first formulated in the 1955 article Some remarks on number theory^[3] (in Hebrew) in Riveon Lematematica, and has become one of the classical problems described by Richard K. Guy in his book Unsolved problems in number theory.

Partial results

Since it was first formulated, there has been continuous progress made in the calculation of lower bounds and upper bounds of, with the following results:

Lower

Limit inferior	Author(s)	Year
M(n) > n/ 4	P. Erdős	1955
M(n) > ( 1 - 2 ^{-1/2} ) n	P. Erdős, Scherk	1955
M(n) > ( 4 - 6 ^{1/2} ) n/ 5	S. Swierczkowski	1958
M(n) > ( 4 - 15 ^{1/2} ) ^{1/2} (n - 1 )	L. Moser	1966
M(n) > ( 4 - 15 ^{1/2} ) ^{1/2} n	J. K. Haugland	1996
M(n) > 0 . 379005 { } n	E. P. White	2022

Upper

Limit superior	Author(s)	Year
M(n) < ( 1+ o( 1 )) n/ 2	P. Erdős	1955
M(n) < ( 1+ o( 1 )) 2 n/ 5	T. S. Motzkin, K. E. Ralston and J. L. Selfridge,	1956
M(n) < ( 1+ o( 1 )) 0 . 382002 ... n	J. K. Haugland	1996
M(n) < ( 1+ o( 1 )) 0 . 380926 ... n	J. K. Haugland	2016

J. K. Haugland showed that the limit of exists and that it is less than 0.385694. For his research, he was awarded a prize in a young scientists competition in 1993.^[4] In 1996, he improved the upper bound to 0.38201 using a result of Peter Swinnerton-Dyer.^[5] This has now been further improved to 0.38093.^[6] In 2022, the lower bound was shown to be at least 0.379005 by E. P. White.^[7]

The first known values of

The values of for the first 15 positive integers are the following:

-- style="border: 1px solid #000000;" -->
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	...

It is just the Law of Small Numbers that it is

style \lfloor 5 (n +3 )/ 13 \rfloor

Notes and References

1. Book: Guy . Richard K. . Richard K. Guy . Unsolved Problems in Number Theory . 3rd edition. 2004 . Bencsáth . Katalin A. . Halmos . Paul R. . Springer Science+Business Media Inc.. New York . 0-387-20860-7 . C17 . 199–200.
2. Web site: Erdös' minimum overlap problem . 15 December 2013 . Finch . Steven . 2 July 2004 . dead . https://web.archive.org/web/20150405060955/http://www.people.fas.harvard.edu/~sfinch/csolve/ovr.pdf . 5 April 2015 .
3. P. Erdős: Some remarks on number theory (in Hebrew), Riveon Lematematika 9 (1955), 45-48 MR17,460d.
4. Web site: The minimum overlap problem . 20 September 2016 . Haugland . Jan Kristian.
5. Haugland. Jan Kristian. 1996. Advances in the Minimum Overlap Problem. Journal of Number Theory. 58. 1. Ohio (USA). 71–78. 0022-314X. 10.1006/jnth.1996.0064. free.
6. The minimum overlap problem revisited. Haugland. Jan Kristian. 2016. math.GM. 1609.08000.
7. Erdős' minimum overlap problem. White. Ethan Patrick. 2022. math.CO. 2201.05704.