Minimum overlap problem

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

Let $A = {a i}$ and $B = {b j}$ be two complementary subsets, a splitting of the set of natural numbers ${1, 2, \dots, 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:

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

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

History

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, 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))2n/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
$M(n)<(1+o(1))0.380924...n$	AlphaEvolve (Novikov et al.)	2025
$M(n)<(1+o(1))0.380876...n$	TTT-Discover (Yuksekgonul et al.)	2026

J. K. Haugland showed that the limit of $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.^[4] In 1996, he improved the upper bound to 0.38201 using a result of Peter Swinnerton-Dyer.^[5]^[2] 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] In 2025, the AI system AlphaEvolve improved the upper bound to 0.380924,^[8] and in 2026 TTT-Discover, another AI system, further improved it to 0.380876.^[9]

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

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