Minimum overlap problem

In number 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 A = {ai} and B = {bj} be two complementary subsets, a splitting of the set of natural numbers {1, 2, …, 2n}, such that both have the same cardinality, namely n. Denote by Mk the number of solutions of the equation ai  bj = k, where k is an integer varying 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

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 1955 in the article Some remark on number theory of Riveon Lematematica, and has become one of the classical problems described by Richard K. Guy in his book Unsolved problems in number theory.[1]

Partial results

Since it was first formulated, there has been continuous progress made in 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, Scherk1955
M(n) > (4 - 6^{-1/2})\, n/5S. Swierczkowski1958
M(n) > (4 - 15^{1/2})^{1/2}\, (n - 1)L. Moser1966
M(n) > (4 - 15^{1/2})^{1/2}\, nJ. K. Haugland 1996

Upper

Limit superior Author(s) Year
M(n) = n/2 P. Erdős 1955
M(n) < 2n/5T. S. Motzkin, K. E. Ralston and J. L. Selfridge,1956
M(n) < 0.38201 nJ. 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 he showed that the superior and inferior limits of M(n)/n are same, thus proving that the limit of M(n)/n exists.[2][4]

The first known values of M(n)

The values of M(n) for the first 15 positive integers are the following:[1]

n\,\! 1 2 3 4 5 6 7 8 9101112131415...
M(n)\,\! 112233344555666...

It's just the Law of Small Numbers that it is \textstyle \lfloor 5(n+3)/13 \rfloor[1]

References

  1. 1 2 3 4 5 Guy, Richard K. (2004). "C17". In Bencsáth, Katalin A.; Halmos, Paul R. Unsolved Problems in Number Theory. New York: Springer Science+Business Media Inc. pp. 199–200. ISBN 0-387-20860-7.
  2. 1 2 3 4 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 (Ohio (USA)) 58 (1): 71–78. doi:10.1006/jnth.1996.0064. ISSN 0022-314X.
This article is issued from Wikipedia - version of the Thursday, December 24, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.