Littlewood–Offord Problem

Let $a = (a_1, a_2, ..., a_n) \in \mathbb{R}^n$ with $|a_i| \ge 1$. Let $p(a)$ be the number of vectors $c = (c_1, c_2, ..., c_n) \in \mathbb{R}^n$ where $c_i = \pm 1, \forall i \in [n]$, such that

1. Prove that $p(a) \le \binom{n}{\lfloor n / 2 \rfloor }$.

2. Find an $a \in \mathbb{R}^n$ with $p(a) = \binom{n}{\lfloor n / 2 \rfloor }$.

Proof. By symmetry, we can assume that $a > 0$ without lose of generality. Define

Let $[n]$ be the set of integers from $1$ to $n$, and $\mathscr{P}([n])$ be the power set of $[n]$, i.e., the set of all subsets of $[n]$. For any subset $s \subset [n]$, we can associate to $s$ a vector in $C$, which is denoted as

where

It remains to show the set

has size at most $\binom{n}{\lfloor n / 2 \rfloor }$. The key observation is that

We call $S(a)$ an antichain. To show this, suppose thta $s'$ contains at least one element that is not in $s$. Denote this element as $j$. It follows that $c(s')_j = 1$ and $c(s')_j = -1$ and that

We conclude that $\left< a, c(s') \right> \ge \left< a, c(s) \right> + 2 \ge 1$, a contradiction.

Now, consider an increasing sequence of $n$ subsets of $[n]$ of the form:

where $x_1, ..., x_n$ are different integers in $[n]$. Each such sequence induces a permutation of integers in $[n]$. As a result, the total number of such sequence equals $n!$. The relation between $S(a)$ and such sequence is established as follows:

1. For each such sequence, there can be at most one set in $S(a)$, because $S(a)$ is a antichain.

2. For each $s = \{x_1, x_2, ..., x_k \} \in S(a)$, where $k = |s| \ge 1$ is the size of $s$, the number of sequences it appears in is given by

   $$|s| ! (n - |s|)! \ge \lfloor n / 2 \rfloor ! (n - \lfloor n / 2 \rfloor)!$$

We obtain

and

This finishes the proof for problem 1.

Finally, $a_i = 1, \forall i \in [n]$ gives a tight example to problem 2.

$\blacksquare$

Reference

[1] J. Matoušek and J. Nešetřil, Invitation to discrete mathematics, 2nd ed. Oxford ; New York: Oxford University Press, 2009.