- Formal statement of the problem
- History
- Partial results Lower Upper {{anchor|The first known values of M(n)}} The first known values of {{math|M(n)}}
- References
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 {{math|A {{=}} {ai}}} and {{math|B {{=}} {bj}}} be two complementary subsets, a splitting of the set of natural numbers {{math|{1, 2, …, 2n}}}, such that both have the same cardinality, namely {{math|n}}. Denote by {{math|Mk}} the number of solutions of the equation {{math|ai − bj {{=}} k}}, where {{math|k}} is an integer varying between {{math|−2n and 2n}}. {{math|M (n)}} is defined as:
The problem is to estimate {{math|M (n)}} when {{math|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 {{math|M (n)}}, with the following results:[1][2]
Lower
| Limit inferior | Author(s) | Year |
|---|---|---|
 | P. Erdős | 1955 |
 | P. Erdős, Scherk | 1955 |
 | S. Swierczkowski | 1958 |
 | L. Moser | 1966 |
 | J. K. Haugland | 1996 |
Upper
| Limit superior | Author(s) | Year |
|---|---|---|
 | P. Erdős | 1955 |
 | T. S. Motzkin, K. E. Ralston and J. L. Selfridge, | 1956 |
 | J. K. Haugland | 1996 |
 | J. K. Haugland | 2016 |
J. K. Haugland showed that the limit of {{math|M (n) / n}} exists and that it is less than 0.385694. For his research, he was awarded a prize in a young scientists competition in 1993.[3] In 1996, he improved the upper bound to 0.38201 using a result of Peter Swinnerton-Dyer.[4][2] This has now been further improved to 0.38093.[5]
{{anchor|The first known values of M(n)}} The first known values of {{math|M(n)}}
The values of {{math|M (n)}} for the first 15 positive integers are the following:[1]
 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ... |
 | 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 
[1]
References
2. ^1 2 3 {{cite web |url=http://www.people.fas.harvard.edu/~sfinch/csolve/ovr.pdf |title=Erdös' minimum overlap problem |accessdate=15 December 2013 |last=Finch |first=Steven |authorlink1= |date=2 July 2004 |format=PDF |deadurl=yes |archiveurl=https://web.archive.org/web/20150405060955/http://www.people.fas.harvard.edu/~sfinch/csolve/ovr.pdf |archivedate=5 April 2015 |df= }}
3. ^{{cite web |url=http://www.neutreeko.net/mop/index.htm |title= The minimum overlap problem |accessdate=20 September 2016 |last=Haugland |first= Jan Kristian}}
4. ^{{cite journal| last=Haugland| first=Jan Kristian| year=1996| title=Advances in the Minimum Overlap Problem| journal=Journal of Number Theory| volume=58| issue=1| location= Ohio (USA)| pages= 71–78| issn= 0022-314X| doi=10.1006/jnth.1996.0064}}
5. ^{{cite web|url=https://arxiv.org/pdf/1609.08000|title=The minimum overlap problem revisited|last=Haugland|first=Jan Kristian|year=2016}}
- Cosmic blowout
- Cosmic Break
- Cosmic brownies
- Cosmic catastrophe
- Cosmic caterpillar
- Cosmic Coaster
- Cosmic Coaster (roller coaster)
- Cosmic Connection: An Extraterrestrial Perspective
- Cosmic consciousness
- Cosmic Consciousness (book)
- Cosmic Containment Device
- Cosmic Containment Unit
- Cosmic Cruiser
- Cosmic dancer
- Cosmic Dancer
- Cosmic Dancer (artwork)
- Cosmic disaster
- Cosmic Empire
- Cosmic Encounter: Cosmic Alliance
- Cosmic energy (disambiguation)
- Cosmic Energy (song)
- Cosmic entity (disambiguation)
- Cosmic Evolution (book)
- Cosmic Force
- Cosmic force