Minimum overlap problem

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

Formal statement of the problem

Let A={a_i} and B={b_j} be two complementary subsets, splitted of the set of natural numbers {1,2,…,2n}, such that both have the same cardinality, namely the quantity of numbers on both subsets is the same, in this case, same to n. Denote M_k as the number of solutions for the equation a_i-b_j=k where k is a integer number oscillating between -2n and 2n. M(n) is defined as:

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

The problem is to estimate M(n) when n is sufficiently large.^[2]

History

Among the proposed problems by Paul Erdös in combinatorial number theory was found this problem, known for English speakers as Minimum overlap problem, first formulated in 1955 in the article Some remark on number theory of Riveon Lematematica, and has become one of the classic problems proposed by Richard Guy in his book Unsolved problems in number theory.^[1]

Partial results

Since it was first formulated, it has made progress in the development and continuous improvements of the calculation of lower bounds and upper bounds of M(n), with the following results:^[1]^[2]

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

Upper

Limit superior	Author(s)	Year
$M(n)/n=1/2$	P.Erdös	1955
$M(n)/n<2/5$	T. S. Motzkin, K. E. Ralston and J. L. Selfridge,	1956
$M(n)/n<0,38201$	J. K. Haugland	1996

J. K. Haugland showed that the limit of M(n)/n < 0.38569401 unconditionally. For his research, he was awarded a prize in the competition for young scientists in 1993.^[3] In 1996 showed that the superior and inferior limits of M(n)/n are same, thus there exists the limit of M(n)/n.^[2]^[4]

The first known values of M(n)

The values of M(n) for the first 15 numbers are the following:^[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	...

References

^ ^a ^b ^c ^d Guy, Richard K. (2004). "C17". In Bencsáth, Katalin A.; Halmos, Paul R. (eds.). Unsolved Problems in Number Theory. New York: Springer Science+Business Media Inc. pp. 199–200. ISBN 0-387-20860-7. {{cite book}}: |access-date= requires |url= (help)
^ ^a ^b ^c ^d Finch, Steven (2 July 2004). "Erdös' minimum overlap problem" (PDF). Retrieved 15 December 2013.
^ Haugland, Jan Kristian. "The minimum overlap problem". Retrieved 15 December 2013.
^ Haugland, Jan Kristian (1996). "Advances in the Minimum Overlap Problem". The Journal of Number Theory. 58 (1). Ohio (USA): 71–78. doi:10.1006/jnth.1996.0064. ISSN 0022-314X.

[rguy-1] Guy, Richard K. (2004). "C17". In Bencsáth, Katalin A.; Halmos, Paul R. (eds.). Unsolved Problems in Number Theory. New York: Springer Science+Business Media Inc. pp. 199–200. ISBN 0-387-20860-7. {{cite book}}: |access-date= requires |url= (help)

[finch-2] Finch, Steven (2 July 2004). "Erdös' minimum overlap problem" (PDF). Retrieved 15 December 2013.

[3] Haugland, Jan Kristian. "The minimum overlap problem". Retrieved 15 December 2013.

[4] Haugland, Jan Kristian (1996). "Advances in the Minimum Overlap Problem". The Journal of Number Theory. 58 (1). Ohio (USA): 71–78. doi:10.1006/jnth.1996.0064. ISSN 0022-314X.

[1]

[2]

[3]

[4]