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, 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{.}\)