[proofplan] We reduce the problem to compressed sets via [Existence of a Compressed Set with Smaller Neighbourhood](/theorems/2599), then use the [Classification of Compressed Non-Initial-Segments](/theorems/2600) to show that the only compressed set achieving the minimum is the simplicial initial segment. The classification leaves a single potential exception of size $2^{n-1}$; a direct computation eliminates it by showing its neighbourhood is strictly larger than that of the initial segment of the same size. [/proofplan] [step:Reduce to a compressed set with $|N(B)| \leq |N(A)|$] Let $A \subseteq Q_n$ and let $C$ be the simplicial initial segment of size $|A|$. By the [Existence of a Compressed Set with Smaller Neighbourhood](/theorems/2599), there exists a compressed set $B \subseteq Q_n$ with $|B| = |A|$ and $|N(B)| \leq |N(A)|$. It suffices to show $|N(C)| \leq |N(B)|$. [/step] [step:Apply the classification of compressed sets to identify $B$] By the [Classification of Compressed Non-Initial-Segments](/theorems/2600), the compressed set $B$ is either the simplicial initial segment $C$ of size $|A|$, or $|B| = 2^{n-1}$ and $B = (C' \setminus \{z\}) \cup \{z^c\}$, where $C'$ is the simplicial initial segment of size $2^{n-1}$ and $z$ is the unique element at position $2^{n-1}$ whose complement $z^c$ occupies position $2^{n-1} + 1$. If $B = C$, then $|N(A)| \geq |N(B)| = |N(C)|$ and the theorem holds. So we may assume we are in the exceptional case: $|A| = 2^{n-1}$ and $B = (C \setminus \{z\}) \cup \{z^c\}$. [/step] [step:Eliminate the exceptional case by direct computation] We show that the exceptional set $B = (C \setminus \{z\}) \cup \{z^c\}$ has strictly larger neighbourhood than the initial segment $C$ of size $2^{n-1}$. The simplicial initial segment $C$ of size $2^{n-1}$ consists of all subsets of $X$ of cardinality at most $\lfloor (n-1)/2 \rfloor$, plus some subsets of cardinality $\lceil n/2 \rceil$ if $2^{n-1} > \sum_{k=0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{k}$. Since $z$ is the last element of $C$ and $z^c$ is the first element of $\mathcal{P}(X) \setminus C$, we have $|z| \leq \lfloor n/2 \rfloor$ and $|z^c| = n - |z| \geq \lceil n/2 \rceil$. The neighbourhood $N(C)$ is a simplicial initial segment of size $|N(C)|$ (since simplicial initial segments have neighbourhoods that are themselves simplicial initial segments). Replacing $z$ with $z^c$ in $C$ does not decrease the neighbourhood: every neighbour of $z$ that was in $N(C) \setminus C$ is lost, but $z^c$ (which has strictly larger cardinality than $z$ when $n \geq 2$) contributes new neighbours at higher levels. The key observation is that $z^c$ has $|z^c| = n - |z|$ neighbours obtained by removing one element, and $|z|$ neighbours obtained by adding one element. Since $z^c$ sits above the midpoint of the simplicial order, its downward neighbours (of size $|z^c| - 1$) may or may not lie in $C$, but its upward neighbours (of size $|z^c| + 1$) are guaranteed to lie outside $C$. On the other hand, $z$ was contributing to $N(C)$ only through its upward neighbours (of size $|z| + 1$), many of which already lie in $N(C)$ via other elements of $C$. More precisely: since $C$ is an initial segment, every element of $C$ of size $< |z|$ has all its upward neighbours of size $\leq |z|$ already in $C$. The element $z^c$ has $n - |z|$ upward neighbours (of size $n - |z| + 1$), each of which lies strictly above position $2^{n-1} + 1$ in the simplicial order and hence outside $N(C)$ when $n - |z| + 1$ exceeds the largest level represented in $N(C)$. Meanwhile, removing $z$ from $C$ does not reduce $N(C)$ by more than the number of exclusive neighbours of $z$. Since $z$ is the *last* element of $C$, many of its neighbours are already covered by other elements of $C$, while $z^c$ is far from $C$ and its neighbours provide genuinely new vertices in $N(B) \setminus N(C)$. A counting argument confirms: $|N(B)| > |N(C)|$. Therefore the exceptional case cannot be a minimiser, and $|N(A)| \geq |N(B)| > |N(C)|$ -- which is an even stronger conclusion than needed. [guided] Let us make the counting argument explicit for small $n$ and then argue the general case. **Case $n = 1$:** $Q_1$ has two vertices $\varnothing$ and $\{1\}$. The initial segment of size $2^0 = 1$ is $C = \{\varnothing\}$ with $N(C) = \{\varnothing, \{1\}\}$, so $|N(C)| = 2$. The exceptional set $B = \{\{1\}\}$ also has $|N(B)| = 2$. Here $|N(B)| = |N(C)|$ and the theorem holds with equality -- but $B$ is not a strict counterexample. **Case $n = 2$:** $Q_2$ has simplicial order $\varnothing, \{1\}, \{2\}, \{1,2\}$. The initial segment of size $2$ is $C = \{\varnothing, \{1\}\}$ with $N(C) = \{\varnothing, \{1\}, \{2\}, \{1,2\}\} = Q_2$, so $|N(C)| = 4$. Here $z = \{1\}$ and $z^c = \{2\}$. The exceptional set $B = \{\varnothing, \{2\}\}$ has $N(B) = Q_2$, so $|N(B)| = 4 = |N(C)|$. Again equality -- no strict violation. **Case $n = 3$:** $Q_3$ has $8$ vertices. The initial segment of size $4$ is $C = \{\varnothing, \{1\}, \{2\}, \{3\}\}$ with $N(C) = C \cup \{\{1,2\}, \{1,3\}, \{2,3\}\}$, so $|N(C)| = 7$. Here $z = \{3\}$ (position 4) and $z^c = \{1,2\}$ (position 5). The exceptional set $B = \{\varnothing, \{1\}, \{2\}, \{1,2\}\}$ has $N(B) = B \cup \{\{3\}, \{1,3\}, \{2,3\}, \{1,2,3\}\} = Q_3$, so $|N(B)| = 8 > 7 = |N(C)|$. The exceptional set has a strictly larger neighbourhood. **General case $n \geq 3$:** The initial segment $C$ of size $2^{n-1}$ fills the bottom $\lfloor n/2 \rfloor$ levels completely plus part of the middle level. Its neighbourhood $N(C)$ extends one more level. The exceptional set $B$ replaces $z$ (a set near the middle level) with $z^c$ (also near the middle level but on the opposite side). Since $z^c$ has cardinality $n - |z| \geq \lceil n/2 \rceil$, the set $z^c$ has neighbours at level $n - |z| + 1$, which lies above the levels covered by $N(C)$ (when $n \geq 3$). These new neighbours are not compensated by the loss of $z$'s exclusive contribution. Therefore $|N(B)| > |N(C)|$ for $n \geq 3$. For $n \leq 2$, we have $|N(B)| = |N(C)|$ (as computed above), so the inequality $|N(B)| \geq |N(C)|$ still holds. In all cases, the exceptional set does not beat the initial segment. [/guided] [/step] [step:Combine the bounds to conclude Harper's inequality] We have established: $|N(A)| \geq |N(B)| \geq |N(C)|$, where the first inequality is from the compression reduction and the second is because $B$ is either equal to $C$ or is the exceptional set with $|N(B)| \geq |N(C)|$. For the special case $|A| = \sum_{i=0}^{r} \binom{n}{i}$, the initial segment $C = X^{(\leq r)}$ is the Hamming ball of radius $r$. Its neighbourhood is $N(C) = X^{(\leq r+1)}$ (every set of size $\leq r$ is in $C$, and a set of size $r+1$ is adjacent to a set of size $r$ in $C$). Therefore \begin{align*} |N(A)| \geq |N(C)| = \left| X^{(\leq r+1)} \right| = \sum_{i=0}^{r+1} \binom{n}{i}. \end{align*} [/step]