Problema del solapamiento mínimo

En teoría de números, el problema del solapamiento mínimo (del inglés Minimum overlap problem) es un problema propuesto por el matemático húngaro Paul Erdös en 1955.

Enunciado formal del problema

Sean A={a_i} y B={b_j} dos conjuntos complementarios, divididos del conjunto de números naturales {1,2,…,2n}, de tal manera que ambos posean la misma cardinalidad, o sea, que la cantidad de números de ambos conjuntos sea igual, en este caso, que sea igual a n. Denótese a M_k como el número de soluciones de la ecuación a_i-b_j=k donde k es un número entero que varía entre -2n y 2n. Se define M(n) como:

$M(n)=\underset{A,B}{\min }\underset{k}{\max }{M}_k$

El problema consiste en estimar M(n) cuando n es lo suficientemente grande.

Historia

Entre los problemas planteados por Paul Erdös en teoría combinatoria de números, se encontraba este problema, que se conoce en inglés como The minimum overlap problem (El problema del solapamiento mínimo), formulado por primera vez en 1955 en el artículo, Some remark on number theory, de Riveon Lematematica, y que se ha convertido en uno de los problemas clásicos propuestos por Richard Guy en su libro Unsolved problems in number theory.

Resultados parciales

Desde que fue formulado por primera vez, se ha conseguido avanzar en el establecimiento y sucesivas mejoras del cálculo de las cotas inferiores y superiores de M(n), con los siguientes resultados:

Inferiores

Límite inferior	Autor(es)	Año
$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

Superiores

Límite superior	Autor(es)	Año
$M(n)/n=1/2$	P.Erdös	1955
$M(n)/n<2/5$	T. S. Motzkin, K. E. Ralston and J. L. Selfridge,	1956
$M(n)/n<0,38201$	J. K. Haugland	1996
$M(n)/n<0,38093$	J. K. Haugland	2016

J. K. Haugland demostró que el límite M(n)/n < 0.38569401 incondicionalmente. Por su investigación, le concedieron un premio en el concurso de jóvenes científicos en 1993. En 1996 demostró que el límite superior e inferior de M(n)/n son iguales, con lo cual existe el límite M(n)/n. Este límite ha sido mejorado en 2016 obteniéndose un valor de 0.38093.

Los primeros valores conocidos de M(n)

Los valores de M(n) para los 15 primeros números son los siguientes:

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