En el campo matemático de la geometría combinatoria , el problema de Littlewood–Offord es el problema de determinar el número de subsumas de un conjunto de vectores que caen en un conjunto convexo dado . Más formalmente, si V es un espacio vectorial de dimensión d , el problema consiste en determinar, dado un subconjunto finito de vectores S y un subconjunto convexo A , el número de subconjuntos de S cuya suma está en A.
El primer límite superior para este problema fue demostrado (para d = 1 y d = 2) en 1938 por John Edensor Littlewood y A. Cyril Offord . [1] Este lema de Littlewood-Offord establece que si S es un conjunto de n números reales o complejos de valor absoluto al menos uno y A es cualquier disco de radio uno, entonces no más de las 2 n posibles subsumas de S caen en el disco.
En 1945, Paul Erdős mejoró el límite superior para d = 1 a
utilizando el teorema de Sperner . [2] Este límite es preciso; la igualdad se alcanza cuando todos los vectores en S son iguales. En 1966, Kleitman demostró que el mismo límite se cumplía para los números complejos. En 1970, lo extendió al contexto en el que V es un espacio normado . [2]
Supongamos que S = { v 1 , …, v n }. Restando
a partir de cada subsuma posible (es decir, cambiando el origen y luego escalando por un factor de 2), el problema de Littlewood-Offord es equivalente al problema de determinar el número de sumas de la forma
que caen en el conjunto objetivo A , donde toma el valor 1 o −1. Esto convierte el problema en uno probabilístico , en el que la pregunta es sobre la distribución de estos vectores aleatorios , y qué se puede decir sin saber nada más sobre v i .
