Minsta överlappningsproblem

I talteori och mängdteori är det minsta överlappningsproblemet ett problem som föreslagits av den ungerske matematikern Paul Erdős 1955.

Formell redogörelse för problemet

Låt $A = {a i}$ och $B = {b j}$ vara två komplementära delmängder , en uppdelning av mängden naturliga tal ${1, 2, \dots, 2 n}$ , så att båda har samma kardinalitet , nämligen $n$ . Beteckna med $M k$ antalet lösningar av ekvationen $a i - b j = k$ , där $k$ är ett heltal som varierar mellan $-2 n och 2 n$ . $M (n)$ definieras som:

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

Problemet är att uppskatta $M (n)$ när $n$ är tillräckligt stor.

Historia

Detta problem kan hittas bland de problem som föreslås av Paul Erdős i kombinatorisk talteori , känd av engelsktalande som minimum överlappningsproblemet . Det formulerades först i 1955 års artikel Some remarks on number theory (på hebreiska) i Riveon Lematematica, och har blivit ett av de klassiska problemen som beskrivs av Richard K. Guy i sin bok Unsolved problems in number theory .

Delvis resultat

Sedan den först formulerades har det gjorts kontinuerliga framsteg i beräkningen av nedre gränser och övre gränser för $M (n)$ , med följande resultat:

Lägre

Begränsa underlägsen	Författare	År
$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$	JK Haugland	1996
$M(n)>0,379005{\,}n$	EP Vit	2022

Övre

Gräns överlägsen	Författare	År
$M(n)<(1+o(1))n/2$	P. Erdős	1955
$M(n)<(1+o(1))2n/5$	TS Motzkin, KE Ralston och JL Selfridge,	1956
$M(n)<(1+o(1))0,382002...n$	JK Haugland	1996
$M(n)<(1+o(1))0,380926...n$	JK Haugland	2016

JK Haugland visade att gränsen för $M (n) / n$ finns och att den är mindre än 0,385694. För sin forskning belönades han med ett pris i en tävling för unga forskare 1993. 1996 förbättrade han den övre gränsen till 0,38201 med hjälp av ett resultat av Peter Swinnerton-Dyer . Detta har nu förbättrats ytterligare till 0,38093. 2022 visades den nedre gränsen vara minst 0,379005 av EP White.

De första kända värdena på $M (n)$

Värdena på $M (n)$ för de första 15 positiva heltalen är följande:

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

Det är bara lagen om små tal att det är $\textstyle \lfloor 5(n+3)/13\rfloor$