Skip to main content

Section 2.4 The Littlewood–Offord Problem

To close this chapter, we present an unexpected application of the ideas used in the proof of Sperner’s Theorem. In a paper on the roots of random polynomials from 1943, Littlewood and Offord [194] posed the following question.
described in detail following the image
“Unit vectors, roughly.”

Problem 2.4.1. Littlewood Offord Problem [194].

Given \(z_1,\dots,z_n\in \mathbb{C}\) and \(A\subseteq [n]\text{,}\) let
\begin{equation} z_A:=\sum_{i\in A}z_i\text{.}\tag{2.4.1} \end{equation}
What is the largest cardinality of a collection \(\mathcal{F}\subseteq 2^{[n]}\) for which there exists complex numbers \(z_1,\dots,z_n\) such that \(|z_i|\geq 1\) for all \(1\leq i\leq n\) and
\begin{equation*} \left|z_A-z_B\right|\lt 1 \end{equation*}
for all \(A,B\in\mathcal{F}\text{?}\)
A couple of years later, Erdős [85] noticed a link to Sperner’s Theorem in the special case that \(z_1,\dots,z_n\) are real numbers. First of all, if \(z_1=z_2=\cdots =z_n=1\text{,}\) then \(\mathcal{F}\subseteq 2^{[n]}\) satisfies the condition in Problem 2.4.1 if and only if all sets in \(\mathcal{F}\) have the same size. Therefore, by taking \(\mathcal{F}\) to be \(\binom{[n]}{\lfloor n/2\rfloor}\text{,}\) we have a lower bound of \(\binom{n}{\lfloor n/2\rfloor}\text{.}\)
Now, let us prove a matching upper bound (in the real case). Suppose that all of \(z_1,\dots,z_n\) are real numbers of absolute value at least one and let \(\mathcal{F}\) be a collection satisfying the property in Problem 2.4.1. Note that \(\mathcal{F}\) has that property if and only if there is a point \(z\in \mathbb{R}\) such that
\begin{equation*} \left|z_A-z\right|\lt 1/2 \end{equation*}
for all \(A\in\mathcal{F}\text{.}\) If one of the \(z_i\) is negative, we replace \(z_i\) by \(-z_i\text{,}\) replace each element \(A\) of \(\mathcal{F}\) with \(A\triangle \{i\}\) (where \(\triangle\) denotes the symmetric difference) and replace \(z\) by \(z-z_i\text{.}\) So, we can assume that all of the \(z_i\) are real numbers bounded below by \(1\text{.}\) To finish the argument, we claim that \(\mathcal{F}\) is an antichain. This is because, for \(A\subseteq B\text{,}\) we have
\begin{equation*} 1 \leq z_A-z_B = \left|z_A-z_B\right|\leq \left|z_A-z\right| + \left|z_B-z\right| \end{equation*}
and so one of the terms on the right side must be at least \(1/2\text{.}\) Thus, \(\mathcal{F}\) is an antichain and, by Sperner’s Theorem, it has at most \(\binom{n}{\lfloor n/2\rfloor}\) elements.
This short and sweet argument settles the case of real numbers, but the original question of Littlewood and Offord for complex numbers remained unsolved until Kleitman [169] and Katona [160] showed that the answer was \(\binom{n}{\lfloor n/2\rfloor}\) in the mid-1960s. Later, Kleitman [170] gave a short and sweet proof that \(\binom{n}{\lfloor n/2\rfloor}\) remains the answer even when \(z_1,\dots,z_n\) are chosen from any normed space, which we present next. We assume that the definition of \(z_A\) in (2.4.1) is extended to the case where the points \(z_i\) are in any vector space (not just \(\mathbb{C}\)).

Proof.

Rather than applying Sperner’s Theorem, as is done in Erdős’ proof for real numbers, let us instead mimic the proof of Sperner’s Theorem given earlier in the notes, except with a more flexible type of structure taking the place of a symmetric chain decomposition.
First, let us modify the notion of a “chain” to fit our needs. Say that a family \(\mathcal{D}\subseteq 2^{[n]}\) is separated if
\begin{equation*} \left\|z_A -z_B\right\|\geq1 \end{equation*}
for all distinct \(A,B\in\mathcal{D}\text{.}\) This is the antithesis of a family satisfying the property described in the theorem, in the same way that a chain is the antithesis of an antichain.
Next, we loosen the notion of symmetric. Say that a partition \(\mathcal{D}_1,\dots,\mathcal{D}_s\) of \(2^{[n]}\) is appropriately sized if, for \(0\leq i\leq \lfloor n/2\rfloor\text{,}\) the number of indices \(j\) such that \(|\mathcal{D}_j| = n+1-2i\) is precisely \(\binom{n}{i}-\binom{n}{i-1}\text{;}\) note that, here, we view \(\binom{n}{-1}\) as being equal to zero. Our aim is to show that \(2^{[n]}\) has an appropriately sized partition \(\mathcal{D}_1,\dots,\mathcal{D}_s\) such that each of the sets \(\mathcal{D}_j\) is separated by induction on \(n\text{.}\)
The base case \(n=1\) is easy, and so consider \(n\geq2\text{.}\) Let \(\mathcal{D}_1,\dots,\mathcal{D}_s\) be an appropriately sized partition of \(2^{[n-1]}\) into separated families. Let \(f:V\to \mathbb{R}\) be a linear map such that \(f(z_n)=\|z_n\|\) and \(f(x)\leq \|x\|\) for all \(x\in V\text{.}\) For example, if \(V\) is a real vector space, then we can let \(\pi\) be the linear projection of \(V\) onto \(\text{ span } (\{z_n\})\text{,}\) let \(\ell\) map \(\alpha z_n\) to \(\alpha\|z_n\|\) for all \(\alpha\in \mathbb{R}\text{,}\) and then take \(f\) to be the composition of \(\pi\) and \(\ell\text{.}\) The complex case isn’t much harder. For each \(j\) with \(1\leq j\leq s\text{,}\) let \(A_j\) be a set such that \(A_j\in \mathcal{D}_j\) and, subject to this, the value of
\begin{equation*} f\left(z_{A_j}\right) \end{equation*}
is maximized. Let
\begin{equation*} \mathcal{D}_j':=\mathcal{D}_j\cup\{A_j\cup \{n\}\} \end{equation*}
and
\begin{equation*} \mathcal{D}_j'':=\{B\cup \{n\}: B\in \mathcal{D}_j \text{ and } B\neq A_j\}\text{.} \end{equation*}
By construction, the collections \(\mathcal{D}_1',\dots,\mathcal{D}_s',\mathcal{D}_1'',\dots,\mathcal{D}_s''\) are disjoint and union to \(2^{[n]}\text{.}\) Now, how many of the families in \(\mathcal{D}_1',\dots,\mathcal{D}_s',\mathcal{D}_1'',\dots,\mathcal{D}_s''\) have cardinality \(n-2i+1\text{?}\) We have that \(\mathcal{D}_j'\) has this size if and only if \(\mathcal{D}_j\) had size \(n-2i\text{;}\) there are \(\binom{n-1}{i}-\binom{n-1}{i-1}\) such indices \(j\text{.}\) If \(\mathcal{D}_j''\) has size \(n-2i+1\text{,}\) then the size of \(\mathcal{D}_j\) was \(n-2i+2\text{;}\) the number of indices for which this is the case is \(\binom{n-1}{i-1}-\binom{n-1}{i-2}\text{.}\) Thus, by Pascal’s Formula,
 1 
See the notes of Math 422 at UVic \cite[p. 6]{422}.
we have constructed an appropriately sized partition.
Now, it is easy to see that the collection \(\mathcal{D}_j''\) is separated, as it is simply a translation of a subset of \(\mathcal{D}_j\text{.}\) As for \(\mathcal{D}_j'\text{,}\) all of its elements apart from \(A_j\cup\{n\}\) were in \(\mathcal{D}_j\text{.}\) So, to check that it is separated, we let \(B\) be any set in \(\mathcal{D}_j\) and observe that, by definition of \(f\text{,}\)
\begin{equation*} \left\|z_{A_j\cup\{n\}} - z_{B}\right\|\geq f\left(z_{A_j\cup\{n\}} - z_B\right) \end{equation*}
\begin{equation*} =f\left(z_{A_j}\right)-f\left(z_B\right) + f(z_n)\geq f(z_n)=\|z_n\|\geq1 \end{equation*}
where, here, we used the specific choice of the set \(A_j\text{.}\)
Let \(\mathcal{D}_1^*,\dots,\mathcal{D}_t^*\) be the non-empty families among \(\mathcal{D}_1',\dots,\mathcal{D}_s',\mathcal{D}_1'',\dots,\mathcal{D}_s''\text{.}\) By assumption, \(\mathcal{F}\) cannot intersect any of \(\mathcal{D}_1^*,\dots,\mathcal{D}_t^*\) in more than one element. Thus,
\begin{equation*} |\mathcal{F}|=\sum_{j=1}^t|\mathcal{F}\cap \mathcal{D}_j^*| \leq t\text{.} \end{equation*}
To conclude, we upper bound \(t\) as follows:
\begin{equation*} t\leq \sum_{i=0}^{\lfloor n/2\rfloor} |\{j: |\mathcal{D}_j^*|=n-2i+1\}| = \sum_{i=0}^{\lfloor n/2\rfloor}\binom{n}{i}-\binom{n}{i-1} = \binom{n}{\lfloor n/2\rfloor} \end{equation*}
since this sum is telescoping and \(\binom{n}{-1}=0\text{.}\)
Here is a YouTube video related to the Littlewood–Offord Problem: