Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
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
- v1, v2, ..., vn,
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 vi 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 = ½Σ vi
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
- Σ εivi
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 vi.
Many subsequent results have been found.