number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...

and

set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...

, the minimum overlap problem is a problem proposed by Hungarian

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

Paul Erdős in 1955.

Formal statement of the problem

Let and be two complementary subsets, a splitting of the set of

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...

s , such that both have the same

cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

, namely . Denote by the number of solutions of the equation , where is an

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

varying between . is defined as: :

M(n) := \min_ \max_k M_k. \,\!

The problem is to estimate when is sufficiently large.

History

This problem can be found amongst the problems proposed by Paul Erdős in

combinatorial number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathe ...

, known by English speakers as the ''Minimum overlap problem''. It was first formulated in the 1955 article ''Some remarks on number theory''P. Erdős: Some remarks on number theory (in Hebrew), Riveon Lematematika 9 (1955), 45-48 MR17,460d. (in Hebrew) in Riveon Lematematica, and has become one of the classical problems described by

Richard K. Guy Richard Kenneth Guy (30 September 1916 – 9 March 2020) was a British mathematician. He was a professor in the Department of Mathematics at the University of Calgary. He is known for his work in number theory, geometry, recreational mathemat ...

in his book ''Unsolved problems in number theory''.

Partial results

Since it was first formulated, there has been continuous progress made in the calculation of lower bounds and upper bounds of , with the following results:

Lower

Upper

J. K. Haugland showed that the

limit Limit or Limits may refer to: Arts and media * ''Limit'' (manga), a manga by Keiko Suenobu * ''Limit'' (film), a South Korean film * Limit (music), a way to characterize harmony * "Limit" (song), a 2016 single by Luna Sea * "Limits", a 2019 ...

of exists and that it is less than 0.385694. For his research, he was awarded a prize in a young scientists competition in 1993. In 1996, he improved the upper bound to 0.38201 using a result of

Peter Swinnerton-Dyer Sir Henry Peter Francis Swinnerton-Dyer, 16th Baronet, (2 August 1927 – 26 December 2018) was an English mathematician specialising in number theory at the University of Cambridge. As a mathematician he was best known for his part in the ...

. This has now been further improved to 0.38093. In 2022, the lower bound was shown to be at least 0.379005 by E. P. White.

The first known values of

The values of for the first 15 positive integers are the following: It is just the Law of Small Numbers that it is

\textstyle \lfloor 5(n+3)/13 \rfloor

References

{{reflist Additive number theory Unsolved problems in number theory