En el campo matemático de la geometría discreta, el problema de Littlewood-Offord consiste en 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 cuyo sumatorio está en A.
El primer mayorante para este problema fue demostrado (para d = 1 y d = 2) en 1938 por John Edensor Littlewood y por Albert Cyril Offord.[1] Este lema de Littlewood-Offord establece que si S es un conjunto de n números reales o números complejos de valor absoluto al menos uno y A es cualquier disco de radio uno, entonces no más de de las 2n posibles subsumas de S caen en el disco.
En 1945, Paul Erdős mejoró la cota superior para d = 1, fijando el valor
para lo que se valió del teorema de Sperner.[2] Esta cota es precisa; la igualdad se alcanza cuando todos los vectores en S son iguales. En 1966, Kleitman demostró que la misma cota se cumplía para números complejos. En 1970, extendió el concepto al caso de que V sea un espacio vectorial normado.[2]
Considérese que S = {v1, …, vn}. Al restar
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 la cuestión en un problema de probabilidad, en el que la pregunta versa sobre la distribución de estos vectores aleatorios y qué se puede decir sin saber nada más sobre vi.