# 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* = {*a*_{i}} and *B* = {*b*_{j}} be two complementary subsets, a splitting of the set of natural numbers {1,2,…,2*n*}, such that both have the same cardinality, namely *n*. Denote by *M*_{k} the number of solutions of the equation *a*_{i} − *b*_{j} = *k*, where *k* is an integer varying between −2*n* and 2*n*. *M*(*n*) is defined as:

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 |
---|---|---|

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 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 | 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

- ↑
^{1.0}^{1.1}^{1.2}^{1.3}{{#invoke:citation/CS1|citation |CitationClass=book }} - ↑
^{2.0}^{2.1}^{2.2}^{2.3}Template:Cite web - ↑ Template:Cite web
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}