Minimální problém s překrytím - Minimum overlap problem

v teorie čísel a teorie množin, problém minimálního překrytí je problém navržený maďarský matematik Paul Erdős v roce 1955.^[1][2]

Formální prohlášení o problému

Nechat A = {A_i} a B = {b_j} být dva doplňkové podmnožiny, rozdělení sady přirozená čísla {1, 2, …, 2n}, takže oba mají stejné mohutnost, jmenovitě n. Označit podle M_k počet řešení rovnice A_i − b_j = k, kde k je celé číslo lišící se mezi −2n a 2n. M (n) je definován jako:

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

Problém je odhadnout M (n) když n je dostatečně velká.^[2]

Dějiny

Tento problém lze nalézt mezi problémy navrženými Paul Erdős v kombinatorická teorie čísel, anglicky hovořící mluvčí známí jako Minimální problém s překrytím. Poprvé byl formulován v článku 1955 v článku Několik poznámek k teorii čísel Riveon Lematematica a stal se jedním z klasických problémů popsaných Richard K. Guy ve své knize Nevyřešené problémy v teorii čísel.^[1]

Částečné výsledky

Od svého prvního formulace došlo k neustálému pokroku ve výpočtu dolní hranice a horní hranice z M (n), s následujícími výsledky:^[1][2]

Dolní

Limit horší	Autoři	Rok
${ displaystyle M (n)> n / 4}$	P. Erdős	1955
${ displaystyle M (n)> (1-2 ^ {- 1/2}) , n}$	P. Erdős, Scherk	1955
${ displaystyle M (n)> (4-6 ^ {- 1/2}) , n / 5}$	S. Swierczkowski	1958
${ displaystyle M (n)> (4-15 ^ {1/2}) ^ {1/2} , (n-1)}$	L. Moser	1966
${ displaystyle M (n)> (4-15 ^ {1/2}) ^ {1/2} , n}$	J. K. Haugland	1996

Horní

Limit superior	Autoři	Rok
${ displaystyle M (n) <(1 + o (1)) n / 2}$	P. Erdős	1955
${ displaystyle M (n) <(1 + o (1)) 2n / 5}$	T. S. Motzkin, K. E. Ralston a J. L. Selfridge,	1956
${ displaystyle M (n) <(1 + o (1)) 0,382002 ... n}$	J. K. Haugland	1996
${ displaystyle M (n) <(1 + o (1)) 0,380926 ... n}$	J. K. Haugland	2016

J. K. Haugland ukázal, že omezit z M (n) / n existuje a že je menší než 0,385 694. Za svůj výzkum mu byla v roce 1993 udělena cena v soutěži mladých vědců.^[3] V roce 1996 vylepšil horní hranici na 0,38201 s použitím výsledku Peter Swinnerton-Dyer.^[4][2] Toto bylo nyní dále vylepšeno na 0,38093.^[5]

První známé hodnoty M(n)

Hodnoty M (n) pro prvních 15 kladných celých čísel jsou následující:^[1]

${ displaystyle n , !}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
${ displaystyle M (n) , !}$	1	1	2	2	3	3	3	4	4	5	5	5	6	6	6	...

Je to jen Zákon malých čísel že je to ${ displaystyle textstyle lfloor 5 (n + 3) / 13 rfloor}$^[1]

Reference