[proofplan] We work inside the constant-weight layer $\mathcal{W}:=\{v \in \{0,1\}^d : |v|_0=s\}$ consisting of binary vectors with exactly $s$ ones. A maximal subset of $\mathcal{W}$ with mutual Hamming distance at least $s/2$ gives the desired separation, and maximality forces every element of $\mathcal{W}$ to lie within Hamming distance $s/2$ of some selected vector. The proof is therefore reduced to comparing the size of $\mathcal{W}$ with the largest possible number of constant-weight vectors lying within Hamming distance $s/2$ of one fixed constant-weight vector. The key counting estimate is that this local neighbourhood captures only an exponentially small fraction, at scale \begin{align*} \exp\bigl(-c s\log(d/s)\bigr), \end{align*} of the constant-weight layer. [/proofplan]

[step:Count the constant-weight layer and the relevant Hamming balls]Define the constant-weight layer \begin{align*} \mathcal{W} := \{v \in \{0,1\}^d : |v|_0 = s\}. \end{align*} For $v \in \{0,1\}^d$ and $r \geq 0$, define the [Hamming ball](/page/Hamming%20Ball) \begin{align*} B_H(v,r) := \{u \in \{0,1\}^d : d_H(u,v) \leq r\}. \end{align*} Since choosing an element of $\mathcal{W}$ is equivalent to choosing the [support](/page/Support) of its $s$ ones, we have \begin{align*} |\mathcal{W}| = \binom{d}{s}. \end{align*} Fix $v \in \mathcal{W}$, and let \begin{align*} S_v := \{i \in \{1,\dots,d\} : v_i = 1\} \end{align*} be its support. If $u \in \mathcal{W}$ and \begin{align*} k := \#(S_v \setminus S_u), \end{align*} where $S_u := \{i \in \{1,\dots,d\} : u_i = 1\}$ is the [support](/page/Support) of $u$, then also \begin{align*} \#(S_u \setminus S_v) = k, \end{align*} because both $S_u$ and $S_v$ have cardinality $s$. Hence \begin{align*} d_H(u,v) = \#(S_v \setminus S_u) + \#(S_u \setminus S_v) = 2k. \end{align*} Thus $d_H(u,v) \leq s/2$ implies $k \leq s/4$. For each integer $k$ with $0 \leq k \leq \lfloor s/4 \rfloor$, the number of such $u$ is \begin{align*} \binom{s}{k}\binom{d-s}{k}, \end{align*} because one chooses the $k$ coordinates removed from $S_v$ and the $k$ replacement coordinates from $\{1,\dots,d\}\setminus S_v$. Therefore \begin{align*} |B_H(v,s/2)\cap \mathcal{W}| \leq \sum_{k=0}^{\lfloor s/4\rfloor} \binom{s}{k}\binom{d-s}{k}. \end{align*}[/step]

[guided]The constant-weight condition is best understood through supports. For each vector $v \in \mathcal{W}$, define its support \begin{align*} S_v := \{i \in \{1,\dots,d\} : v_i = 1\}. \end{align*} Then $|S_v| = s$, and the map $v \mapsto S_v$ is a bijection from $\mathcal{W}$ to the set of $s$-element subsets of $\{1,\dots,d\}$. Hence \begin{align*} |\mathcal{W}| = \binom{d}{s}. \end{align*} Now fix $v \in \mathcal{W}$ and count how many vectors $u \in \mathcal{W}$ can lie within Hamming distance $s/2$ of $v$. Since both $u$ and $v$ have exactly $s$ ones, changing from $v$ to $u$ must remove the same number of ones from the support of $v$ as it adds outside the support of $v$. Define \begin{align*} k := \#(S_v \setminus S_u). \end{align*} Because $|S_u| = |S_v| = s$, we also have \begin{align*} \#(S_u \setminus S_v) = k. \end{align*} The [Hamming distance](/page/Hamming%20Distance) counts both the coordinates where $v$ has a one and $u$ has a zero, and the coordinates where $u$ has a one and $v$ has a zero. Therefore \begin{align*} d_H(u,v) = \#(S_v \setminus S_u) + \#(S_u \setminus S_v) = 2k. \end{align*} Thus the condition $d_H(u,v) \leq s/2$ forces $k \leq s/4$. For a fixed value of $k$, constructing such a vector $u$ requires two choices: choose the $k$ ones of $v$ to delete, and choose the $k$ new one-coordinates outside $S_v$. These choices give \begin{align*} \binom{s}{k}\binom{d-s}{k} \end{align*} possibilities. Summing over all allowed integers $k$ gives \begin{align*} |B_H(v,s/2)\cap \mathcal{W}| \leq \sum_{k=0}^{\lfloor s/4\rfloor} \binom{s}{k}\binom{d-s}{k}. \end{align*}[/guided]

[step:Bound the relative size of a Hamming ball in the layer]We prove the following uniform estimate. [claim:Constant-weight Hamming balls have exponentially small relative volume] There exists a universal constant $c_0 > 0$ such that for all integers $d,s \in \mathbb{N}$ with $1 \leq s \leq d/2$ and all $v \in \mathcal{W}$, \begin{align*} \frac{|B_H(v,s/2)\cap \mathcal{W}|}{|\mathcal{W}|} \leq \exp\bigl(-c_0 s\log(d/s)\bigr). \end{align*} [/claim] [proof] Let \begin{align*} R := d/s. \end{align*} Then $R \geq 2$. Let $A \subset \{1,\dots,d\}$ be a fixed set with $|A|=s$, and let $S$ be uniformly distributed over all $s$-element subsets of $\{1,\dots,d\}$. For each subset $E \subset \{1,\dots,d\}$, define its indicator vector $\mathbb{1}_E \in \{0,1\}^d$ by $(\mathbb{1}_E)_i=1$ if $i\in E$ and $(\mathbb{1}_E)_i=0$ if $i\notin E$. The ratio in the claim equals \begin{align*} \mathbb{P}\bigl(\#(A\cap S) \geq 3s/4\bigr), \end{align*} because $d_H(\mathbb{1}_A,\mathbb{1}_S) \leq s/2$ is equivalent to replacing at most $s/4$ elements of $A$, or equivalently retaining at least $3s/4$ elements of $A$. First suppose $R \geq 64$. Put \begin{align*} m := \lceil 3s/4\rceil. \end{align*} If $\#(A\cap S) \geq m$, then some $m$-element subset $T \subset A$ is contained in $S$. For a fixed such $T$, \begin{align*} \mathbb{P}(T \subset S) = \frac{\binom{d-m}{s-m}}{\binom{d}{s}} = \prod_{j=0}^{m-1}\frac{s-j}{d-j} \leq \left(\frac{s}{d}\right)^m, \end{align*} where the last inequality follows from $s \leq d$. By the union bound and the estimate $\binom{s}{m} \leq (es/m)^m$, \begin{align*} \mathbb{P}\bigl(\#(A\cap S) \geq m\bigr) \leq \binom{s}{m}\left(\frac{s}{d}\right)^m \leq \left(\frac{es}{m}\cdot\frac{s}{d}\right)^m \leq \left(\frac{4e}{3R}\right)^{3s/4}. \end{align*} Since $R \geq 64$, the last expression is bounded by \begin{align*} \exp\bigl(-\tfrac{1}{4}s\log R\bigr). \end{align*} It remains to treat $2 \leq R < 64$. We give an explicit bound that avoids any unproved entropy-positivity assertion. Since the event $\#(A\cap S)\geq m$ implies that some $m$-element subset $T\subset A$ is contained in $S$, the same union-bound argument gives \begin{align*} \mathbb{P}\bigl(\#(A\cap S) \geq m\bigr) \leq \binom{s}{m}\left(\frac{s}{d}\right)^m. \end{align*} For every integer $s\geq 1$ and $m=\lceil 3s/4\rceil$, we have $m\geq 3s/4$. The elementary binomial estimate $\binom{s}{m}\leq 2^s$ therefore yields \begin{align*} \mathbb{P}\bigl(\#(A\cap S) \geq m\bigr) \leq 2^s R^{-3s/4} = \exp\bigl(s\log 2-\tfrac{3}{4}s\log R\bigr). \end{align*} If $R\geq 16$, then $\log R\geq 4\log 2$, and hence \begin{align*} s\log 2-\frac{3}{4}s\log R \leq -\frac{1}{2}s\log R. \end{align*} Thus, for $16\leq R<64$, \begin{align*} \frac{|B_H(v,s/2)\cap \mathcal{W}|}{|\mathcal{W}|} \leq \exp\bigl(-\tfrac{1}{2}s\log R\bigr). \end{align*} It remains only to handle $2\leq R<16$. Since $2\leq R<16$, the hypergeometric [random variable](/page/Random%20Variable) $\#(A\cap S)$ has mean $s/R\leq s/2$, while the event above requires at least $3s/4$ retained elements. We use the following finite-population form of [Hoeffding's Inequality](/theorems/1962): if $Y$ is the sum of $s$ samples drawn without replacement from a population whose entries lie in $[0,1]$ and if $\mathbb{E}[Y]=\mu$, then for every $t>0$, \begin{align*} \mathbb{P}(Y-\mu\geq t) \leq \exp\left(-\frac{2t^2}{s}\right). \end{align*} Apply this with $Y:=\#(A\cap S)$, $\mu:=s/R$, and $t:=3s/4-s/R$. Since $R\geq 2$, we have $t\geq s/4$, and therefore \begin{align*} \mathbb{P}\bigl(\#(A\cap S) \geq 3s/4\bigr) \leq \exp\left(-\frac{2(s/4)^2}{s}\right) = \exp\bigl(-s/8\bigr). \end{align*} Because $\log R\leq \log 16$, this implies \begin{align*} \frac{|B_H(v,s/2)\cap \mathcal{W}|}{|\mathcal{W}|} \leq \exp\left(-\frac{1}{8\log 16}s\log R\right) \end{align*} for all pairs with $2\leq R<16$. Combining the cases, the claim holds with \begin{align*} c_0 := \min\left\{\frac{1}{4},\frac{1}{2},\frac{1}{8\log 16}\right\} > 0. \end{align*} [/proof][/step]

[guided]The estimate compares a local Hamming neighbourhood inside the constant-weight layer with the whole layer. Let $R:=d/s$, so $R\geq 2$. Fix a set $A\subset\{1,\dots,d\}$ with $|A|=s$, and let $S$ be uniformly distributed over all $s$-element subsets of $\{1,\dots,d\}$. For each subset $E\subset\{1,\dots,d\}$, define its indicator vector $\mathbb{1}_E\in\{0,1\}^d$ by $(\mathbb{1}_E)_i=1$ for $i\in E$ and $(\mathbb{1}_E)_i=0$ for $i\notin E$. Then the relative volume of $B_H(\mathbb{1}_A,s/2)\cap\mathcal{W}$ is \begin{align*} \mathbb{P}\bigl(\#(A\cap S)\geq 3s/4\bigr), \end{align*} because distance at most $s/2$ means that at most $s/4$ elements of $A$ have been replaced. First consider $R\geq64$. Define $m:=\lceil 3s/4\rceil$. If $\#(A\cap S)\geq m$, then there is an $m$-element subset $T\subset A$ with $T\subset S$. For a fixed such $T$, \begin{align*} \mathbb{P}(T\subset S) = \frac{\binom{d-m}{s-m}}{\binom{d}{s}} = \prod_{j=0}^{m-1}\frac{s-j}{d-j} \leq \left(\frac{s}{d}\right)^m. \end{align*} The union bound over all $m$-element subsets of $A$, followed by $\binom{s}{m}\leq (es/m)^m$ and $m\geq 3s/4$, gives \begin{align*} \mathbb{P}\bigl(\#(A\cap S)\geq m\bigr) \leq \left(\frac{4e}{3R}\right)^{3s/4} \leq \exp\bigl(-\tfrac{1}{4}s\log R\bigr). \end{align*} For $16\leq R<64$, the same union-bound estimate with $\binom{s}{m}\leq2^s$ gives \begin{align*} \mathbb{P}\bigl(\#(A\cap S)\geq m\bigr) \leq 2^sR^{-3s/4} = \exp\bigl(s\log2-\tfrac{3}{4}s\log R\bigr) \leq \exp\bigl(-\tfrac{1}{2}s\log R\bigr), \end{align*} since $\log R\geq4\log2$ in this range. It remains to control $2\leq R<16$. Here $Y:=\#(A\cap S)$ is a hypergeometric random variable with mean $\mu:=s/R\leq s/2$. The event $Y\geq3s/4$ is therefore the deviation $Y-\mu\geq t$, where $t:=3s/4-s/R\geq s/4$. Applying the finite-population form of [Hoeffding's Inequality](/theorems/1962) to this sum of $s$ draws without replacement from a $\{0,1\}$-population gives \begin{align*} \mathbb{P}(Y\geq3s/4) \leq \exp\left(-\frac{2(s/4)^2}{s}\right) = \exp(-s/8) \leq \exp\left(-\frac{1}{8\log16}s\log R\right). \end{align*} Combining the three ranges proves the relative-volume estimate with \begin{align*} c_0:=\min\left\{\frac14,\frac12,\frac{1}{8\log16}\right\}>0. \end{align*}[/guided]

[step:Choose a maximal separated subset of the constant-weight layer]Choose $\mathcal{V} \subset \mathcal{W}$ maximal with respect to the property that \begin{align*} d_H(u,v) \geq s/2 \end{align*} for all distinct $u,v \in \mathcal{V}$. Such a maximal set exists because $\mathcal{W}$ is finite. By construction, every $v \in \mathcal{V}$ satisfies $|v|_0=s$, and the required pairwise separation holds. Maximality also implies the covering relation \begin{align*} \mathcal{W} \subset \bigcup_{v\in \mathcal{V}} \bigl(B_H(v,s/2)\cap \mathcal{W}\bigr). \end{align*} Indeed, if some $w \in \mathcal{W}$ were not contained in the right-hand side, then $d_H(w,v)>s/2$ for every $v\in\mathcal{V}$, so $\mathcal{V}\cup\{w\}$ would still have pairwise Hamming distance at least $s/2$, contradicting maximality. Taking cardinalities gives \begin{align*} |\mathcal{W}| \leq |\mathcal{V}|\sup_{v\in\mathcal{W}} |B_H(v,s/2)\cap \mathcal{W}|. \end{align*}[/step]

[guided]The maximal set $\mathcal{V}$ is a packing: no two selected vectors are closer than $s/2$. Because $\mathcal{W}$ is finite, such a maximal packing exists by adding admissible vectors until no further vector can be added. Maximality converts the packing into a covering statement. If $w\in\mathcal{W}$ were outside every set $B_H(v,s/2)\cap\mathcal{W}$ with $v\in\mathcal{V}$, then \begin{align*} d_H(w,v)>s/2 \end{align*} for every $v\in\mathcal{V}$. Hence $\mathcal{V}\cup\{w\}$ would still satisfy the required separation condition, contradicting maximality. Therefore \begin{align*} \mathcal{W} \subset \bigcup_{v\in\mathcal{V}}\bigl(B_H(v,s/2)\cap\mathcal{W}\bigr). \end{align*} Taking cardinalities and bounding the size of each set in the union by the largest possible such size gives \begin{align*} |\mathcal{W}| \leq |\mathcal{V}|\sup_{v\in\mathcal{W}}|B_H(v,s/2)\cap\mathcal{W}|. \end{align*}[/guided]

[step:Compare the covering inequality with the ball-volume estimate] By the ball-volume estimate proved above, \begin{align*} \sup_{v\in\mathcal{W}} \frac{|B_H(v,s/2)\cap \mathcal{W}|}{|\mathcal{W}|} \leq \exp\bigl(-c_0 s\log(d/s)\bigr). \end{align*} Combining this with the covering inequality yields \begin{align*} 1 \leq |\mathcal{V}| \exp\bigl(-c_0 s\log(d/s)\bigr). \end{align*} Taking logarithms gives \begin{align*} \log|\mathcal{V}| \geq c_0 s\log(d/s). \end{align*} Thus the theorem holds with the universal constant $c := c_0>0$. [/step]