= Littlewood-Offord inequality
{c}
{title2=$\#\{\epsilon:\|\sum_i\epsilon_ix_i-a\|<1\}\leq\binom n{\lfloor n/2\rfloor}$}
For vectors of norm at least one, the number of signed sums in an open unit ball is at most the central binomial coefficient. In one dimension this follows from the <antichain> bound. In Euclidean spaces a <separated block decomposition for vector subset sums> supplies the same bound without assuming all vectors have positive projection in one common direction. Signed sums are counted with multiplicity, by their sign choices.
Back to article page
