Problema de Littlewood-Offord

Summary

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.

Referencias

editar
  1. Littlewood, J.E.; Offord, A.C. (1943). «On the number of real roots of a random algebraic equation (III)». Rec. Math. (Mat. Sbornik). Nouvelle Série 12 (54): 277-286. 
  2. a b Bollobás, Béla (1986). Combinatorics. Cambridge. ISBN 0-521-33703-8. 
  •   Datos: Q6653181