Problema de Littlewood-Offord

En el camp matemàtic de la geometria discreta, el problema de Littlewood-Offord consistix en determinar el número de subsumas d'un conjunt de vectores que cauen en un conjunt convexo donat. Més formalment, si V és un espai vectorial de dimensió d, el problema consistix en determinar, donat un subconjunt finito de vectores S i un subconjunt convexo A, el número de subconjunts de S que el seu sumatorio està en A.

El primer mayorante per a este problema va ser demostrat (per a d = 1 i d = 2) en 1938 per John Edensor Littlewood i per Albert Cyril Offord. Este lema de Littlewood-Offord establix que si S és un conjunt de n número real o número complejo de valor absolut a lo manco un i A és qualsevol disc de ràdio un, llavors no més de $(c\log n/\sqrt{n})2^n$ de les 2ⁿ possibles subsumas de S cauen en el disc.

En 1945, Paul Erdős va millorar la cota superior per a d = 1, fixant el valor

$(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })\approx 2^n\frac{1}{\sqrt{n}}$

per a lo que es va valdre del teorema de Sperner. Esta cota és precisa; l'igualtat s'alcança quan tots els vectores en S són iguals. En 1966, Kleitman va demostrar que la mateixa cota es complia per a número complejo. En 1970, va estendre el concepte al cas de que V siga un espai vectorial normado.

Considere's que S = {v₁, …, v_n}. En restar

$\frac{1}{2}\sum _{i=1}^n{v}_i$

de cada subsuma possible (és dir, canviant l'orige i després escalant per un factor de 2), el problema de Littlewood-Offord és equivalent al problema de determinar el número de sumes de la forma

$\sum _{i=1}^n{\epsilon }_i{v}_i$

que cauen en el conjunt objectiu A, a on ${\epsilon }_i$ pren el valor 1 o ≤ 1. Açò convertix la qüestió en un problema de provabilitat, en el que la pregunta versa sobre la distribució d'estos vectores aleatoris i qué es pot dir sense saber res més sobre v_i.