Littlewood-Offord problem

From Wikipedia, the free encyclopedia

In mathematics, the Littlewood-Offord problem is the combinatorial question in geometry of describing usefully the distribution of the subsums made out of vectors

v₁, v₂, ..., v_n,

taken from a given Euclidean space of fixed dimension d ≥ 1. The first result on this was given in a paper from 1938 by John Edensor Littlewood and A. Cyril Offord, on random polynomials. This Littlewood-Offord lemma, for d = 1, stated that if the v_i all have absolute value at least one, then an interval of length 1 contains at most C sums, where C is the central binomial coefficient for n. This was strengthened in 1945 by Paul Erdős.

The semi-sum

m = ½Σ v_i

can be subtracted from all the subsums. That is, by change of origin and then scaling by a factor of 2, we may as well consider sums

Σ ε_iv_i

in which ε_i takes the value 1 or −1. This makes the problem into a probabilistic one, in which the question is of the distribution of these random vectors, and what can be said knowing nothing more about the v_i.

Many subsequent results have been found.