Problema de superposición mínima

En teoría de números y teoría de conjuntos , el problema de superposición mínima es un problema propuesto por el matemático húngaro Paul Erdős en 1955. ^{[ 1 ] [ 2 ]}

Sean A = { a _i } y B = { b _j } dos subconjuntos complementarios , una descomposición del conjunto de los números naturales {1, 2, …, 2 n } , tales que ambos tienen la misma cardinalidad , es decir , n . Denotemos por M _k el número de soluciones de la ecuación a _i  − b _j = k    , donde k es un entero que varía entre −2 n y 2 n . M ( n ) se define como:

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

El problema consiste en estimar M ( n ) cuando n es suficientemente grande. ^{[ 2 ]}

Este problema se encuentra entre los problemas propuestos por Paul Erdős en teoría combinatoria de números , conocido en inglés como el problema de la superposición mínima . Fue formulado por primera vez en el artículo de 1955 « Algunas observaciones sobre la teoría de números ^{» [ 3 ]} (en hebreo) en Riveon Lematematica, y se ha convertido en uno de los problemas clásicos descritos por Richard K. Guy en su libro «Problemas sin resolver en teoría de números » ^{[ 1 ]} .

Desde su primera formulación, se ha avanzado continuamente en el cálculo de los límites inferiores y superiores de M ( n ) , con los siguientes resultados: ^{[ 1 ] [ 2 ]}