[proofplan] We identify binary vectors of weight $k$ with $k$-element subsets of $\{1,\dots,d\}$. We first choose a maximal separated family and use maximality to cover the whole weight-$k$ layer by small Hamming balls. The ball size estimate gives the desired lower bound when $\log(d/k)$ is large, and a separate binary-cube packing inside $k$ disjoint coordinate pairs handles the bounded-ratio regime. Finally we translate the selected supports back into binary vectors. [/proofplan]

[step:Represent weight-$k$ binary vectors by their supports] For a vector $v \in \{0,1\}^d$, define its support \begin{align*} \operatorname{supp}(v) := \{i \in \{1,\dots,d\} : v_i = 1\}. \end{align*} Let \begin{align*} \mathcal{S}_k := \{A \subset \{1,\dots,d\} : |A| = k\} \end{align*} be the family of all $k$-element subsets of $\{1,\dots,d\}$. Let $\Phi: \{v \in \{0,1\}^d : |\operatorname{supp}(v)| = k\} \to \mathcal{S}_k$ be the map defined by \begin{align*} \Phi(v) := \operatorname{supp}(v). \end{align*} Then $\Phi$ is a bijection. For two vectors $v,w \in \{0,1\}^d$ of weight $k$, set $A := \operatorname{supp}(v)$ and $B := \operatorname{supp}(w)$. Since $|A|=|B|=k$, the coordinates where $v$ and $w$ differ are precisely $(A \setminus B) \cup (B \setminus A)$, and \begin{align*} d_H(v,w) = |A \setminus B| + |B \setminus A| = 2|A \setminus B|. \end{align*} Thus it is enough to construct a large family $\mathcal{A}_*\subset\mathcal{S}_k$ satisfying $|A\triangle B|\geq k/2$ for all distinct $A,B\in\mathcal{A}_*$. [/step]

[step:Choose a maximal separated family in the weight layer]Choose a family $\mathcal{A} \subset \mathcal{S}_k$ that is maximal, with respect to inclusion, among all families satisfying \begin{align*} |A \triangle B| \geq \frac{k}{2} \end{align*} for every pair of distinct sets $A,B \in \mathcal{A}$, where \begin{align*} A \triangle B := (A \setminus B) \cup (B \setminus A) \end{align*} denotes the symmetric difference. Such a maximal family exists because $\mathcal{S}_k$ is finite. By maximality, for every $E \in \mathcal{S}_k$ there exists $A \in \mathcal{A}$ such that \begin{align*} |E \triangle A| < \frac{k}{2}. \end{align*} Indeed, if no such $A$ existed, then $|E \triangle A| \geq k/2$ for every $A \in \mathcal{A}$, and $\mathcal{A} \cup \{E\}$ would still satisfy the separation condition, contradicting maximality unless $E \in \mathcal{A}$.[/step]

[guided]The maximal family is chosen greedily, but we only need its defining consequence. We first require separation: \begin{align*} |A \triangle B| \geq \frac{k}{2} \end{align*} whenever $A,B \in \mathcal{A}$ are distinct. Since $\mathcal{S}_k$ is finite, one can keep adding admissible sets until no more can be added; the resulting family is maximal. What does maximality buy us? It converts packing into covering. Fix any $E \in \mathcal{S}_k$. If $E$ were at symmetric-difference distance at least $k/2$ from every member of $\mathcal{A}$, then adding $E$ to $\mathcal{A}$ would preserve the same separation condition. That is forbidden by maximality. Therefore some $A \in \mathcal{A}$ satisfies \begin{align*} |E \triangle A| < \frac{k}{2}. \end{align*} So the balls of radius strictly less than $k/2$ around the selected sets cover the entire layer $\mathcal{S}_k$.[/guided]

[step:Bound the number of weight-$k$ sets close to one selected support]Fix $A \in \mathcal{S}_k$. Define the removed-coordinate count map $j_A: \mathcal{S}_k \to \{0,1,\dots,k\}$ by \begin{align*} j_A(E) := |A \setminus E| \quad \text{for } E \in \mathcal{S}_k. \end{align*} For $E \in \mathcal{S}_k$, write $j(E,A):=j_A(E)$. Since $|A|=|E|=k$, one also has $|E \setminus A| = j(E,A)$, and hence \begin{align*} |E \triangle A| = 2j(E,A). \end{align*} Thus the condition $|E \triangle A| < k/2$ implies $j(E,A) < k/4$. For each integer $j$ with $0 \leq j < k/4$, the number of sets $E \in \mathcal{S}_k$ satisfying $j(E,A)=j$ is \begin{align*} \binom{k}{j}\binom{d-k}{j}, \end{align*} because one chooses $j$ elements of $A$ to remove and $j$ elements of $\{1,\dots,d\}\setminus A$ to insert. Therefore the strict ball $B_A \subset \mathcal{S}_k$ defined by \begin{align*} B_A := \{E \in \mathcal{S}_k : |E \triangle A| < k/2\} \end{align*} satisfies \begin{align*} |B_A| \leq \sum_{0 \leq j < k/4} \binom{k}{j}\binom{d-k}{j}. \end{align*} Let $L := \log(d/k)$. For $j=0$ the summand is $1$. For $1 \leq j < k/4$, set $x_j := j/k$. Using $j!\geq (j/e)^j$, we have $\binom{n}{j}\leq n^j/j!\leq (en/j)^j$. Applying this first with $n=k$ and then with $n=d-k\leq d$ gives \begin{align*} \binom{k}{j}\binom{d-k}{j} \leq \left(\frac{ek}{j}\right)^j\left(\frac{ed}{j}\right)^j = \exp\left(kx_j\left(L+2-2\log x_j\right)\right). \end{align*} Since $0 < x_j \leq 1/4$, we have $x_jL \leq L/4$ and $x_j(2-2\log x_j) \leq 2$. Hence every summand is bounded by \begin{align*} \exp\left(\frac{k}{4}L+2k\right). \end{align*} There are at most $k+1$ summands, and $k+1 \leq e^k$ for $k \geq 1$. Therefore \begin{align*} |B_A| \leq \exp\left(\frac{k}{4}\log\left(\frac{d}{k}\right)+3k\right). \end{align*}[/step]

[guided]We are estimating how many weight-$k$ supports can lie within symmetric-difference distance strictly less than $k/2$ from a fixed support $A$. Define the removed-coordinate count map $j_A: \mathcal{S}_k \to \{0,1,\dots,k\}$ by \begin{align*} j_A(E) := |A \setminus E| \quad \text{for } E\in\mathcal{S}_k. \end{align*} For $E\in\mathcal{S}_k$, write $j(E,A):=j_A(E)$. This number records how many elements of $A$ must be removed to obtain $E$. Because both $A$ and $E$ have cardinality $k$, the same number of new elements must be inserted from the complement of $A$, so $|E \setminus A|=j(E,A)$. Therefore \begin{align*} |E \triangle A| = |A \setminus E|+|E \setminus A| = 2j(E,A). \end{align*} Thus $|E \triangle A|<k/2$ forces $j(E,A)<k/4$. Now fix an integer $j$ with $0\leq j<k/4$. To construct such an $E$, choose the $j$ elements removed from $A$ and choose the $j$ replacement elements from $\{1,\dots,d\}\setminus A$. This gives exactly \begin{align*} \binom{k}{j}\binom{d-k}{j} \end{align*} choices. Hence the ball \begin{align*} B_A := \{E \in \mathcal{S}_k : |E \triangle A| < k/2\} \end{align*} satisfies \begin{align*} |B_A| \leq \sum_{0 \leq j < k/4} \binom{k}{j}\binom{d-k}{j}. \end{align*} Let $L := \log(d/k)$. The summand for $j=0$ equals $1$. For $1\leq j<k/4$, define $x_j:=j/k$. Using $j!\geq (j/e)^j$, we obtain $\binom{n}{j}\leq n^j/j!\leq (en/j)^j$. Applying this first with $n=k$ and then with $n=d-k\leq d$, we obtain \begin{align*} \binom{k}{j}\binom{d-k}{j} \leq \left(\frac{ek}{j}\right)^j\left(\frac{ed}{j}\right)^j = \exp\left(kx_j\left(L+2-2\log x_j\right)\right). \end{align*} Because $0<x_j\leq 1/4$, the coefficient of $L$ is at most $1/4$, and the remaining term satisfies $x_j(2-2\log x_j)\leq 2$. Therefore \begin{align*} \binom{k}{j}\binom{d-k}{j} \leq \exp\left(\frac{k}{4}L+2k\right). \end{align*} There are at most $k+1$ possible values of $j$, and $k+1\leq e^k$ for every $k\geq 1$. Multiplying the largest summand bound by this number gives \begin{align*} |B_A| \leq \exp\left(\frac{k}{4}\log\left(\frac{d}{k}\right)+3k\right). \end{align*}[/guided]

[step:Construct a large separated support family in both ratio regimes]Let $L := \log(d/k)$. The covering property from maximality gives \begin{align*} \mathcal{S}_k \subset \bigcup_{A \in \mathcal{A}} B_A. \end{align*} Hence \begin{align*} \binom{d}{k} = |\mathcal{S}_k| \leq |\mathcal{A}| \sup_{A \in \mathcal{A}} |B_A|. \end{align*} We justify the binomial lower bound used below. Since $d\geq k$ and $1\leq r\leq k$, one has \begin{align*} \frac{d-k+r}{r} \geq \frac{d}{k}, \end{align*} because $k(d-k+r) - dr = (k-r)(d-k) \geq 0$. Therefore \begin{align*} \binom{d}{k}=\prod_{r=1}^{k}\frac{d-k+r}{r}\geq \left(\frac{d}{k}\right)^k. \end{align*} Taking logarithms and using the ball estimate from the previous step, we obtain \begin{align*} \log |\mathcal{A}| \geq \frac{3k}{4}\log\left(\frac{d}{k}\right)-3k. \end{align*} If $L\geq 8$, then \begin{align*} \log |\mathcal{A}| \geq \frac{3k}{8}\log\left(\frac{d}{k}\right). \end{align*} In this case set $\mathcal{A}_* := \mathcal{A}$. It remains to handle $L<8$. Define the binary entropy constant \begin{align*} H_0 := -\frac{1}{4}\log\left(\frac{1}{4}\right)-\frac{3}{4}\log\left(\frac{3}{4}\right) \end{align*} and define $\gamma := \log 2-H_0$. Since \begin{align*} H_0 = 2\log 2-\frac{3}{4}\log 3, \end{align*} we have \begin{align*} \gamma = \frac{3}{4}\log 3-\log 2. \end{align*} The elementary estimates $\log 3\geq 1.09$ and $\log 2\leq 0.7$ give \begin{align*} \gamma \geq \frac{3}{4}\cdot 1.09-0.7=0.1175\geq \frac{1}{9}. \end{align*} A greedy packing argument in $\{0,1\}^k$ gives a set $\mathcal{C}\subset\{0,1\}^k$ such that $d_H(u,u')\geq k/4$ for distinct $u,u'\in\mathcal{C}$ and \begin{align*} \log |\mathcal{C}| \geq \gamma k. \end{align*} Indeed, a maximal such $\mathcal{C}$ has Hamming balls of radius strictly less than $k/4$ covering $\{0,1\}^k$. For $0<p\leq 1/2$, the binomial entropy estimate follows as follows. Set $t:=p/(1-p)\in(0,1]$. Since $m\leq pk$ implies $t^{-m}\leq t^{-pk}$, the [binomial theorem](/theorems/750) gives \begin{align*} \sum_{0\leq m\leq pk}\binom{k}{m}\leq t^{-pk}\sum_{m=0}^k\binom{k}{m}t^m=t^{-pk}(1+t)^k=\exp(kH(p)), \end{align*} where $H(p):=-p\log p-(1-p)\log(1-p)$. Applying this with $p=1/4$ shows that each strict-radius ball has at most $\exp(H_0k)$ points, since the sum over integers $m<k/4$ is bounded by the sum over $m\leq k/4$. Therefore $2^k\leq |\mathcal{C}|\exp(H_0k)$. Since $d\geq 2k$, define disjoint coordinate pairs $P_i:=\{2i-1,2i\}\subset\{1,\dots,d\}$ for $1\leq i\leq k$. For $u\in\mathcal{C}$, define $A_u\in\mathcal{S}_k$ by including $2i-1$ when $u_i=0$ and including $2i$ when $u_i=1$. Set \begin{align*} \mathcal{A}_* := \{A_u : u\in\mathcal{C}\}. \end{align*} If $u,u'\in\mathcal{C}$ are distinct, then each coordinate where $u$ and $u'$ differ changes exactly one selected element inside the corresponding pair, so \begin{align*} |A_u\triangle A_{u'}| = 2d_H(u,u') \geq \frac{k}{2}. \end{align*} Moreover, because $L<8$, \begin{align*} \log |\mathcal{A}_*| = \log |\mathcal{C}| \geq \gamma k \geq \frac{\gamma}{8}k\log\left(\frac{d}{k}\right). \end{align*} Combining the two regimes with the explicit constant \begin{align*} c := \frac{1}{72} \end{align*} gives a family $\mathcal{A}_*\subset\mathcal{S}_k$ satisfying $|A\triangle B|\geq k/2$ for distinct $A,B\in\mathcal{A}_*$ and \begin{align*} \log |\mathcal{A}_*| \geq c k\log\left(\frac{d}{k}\right), \end{align*} because $1/72\leq 3/8$ and $1/72\leq \gamma/8$ follows from $\gamma\geq 1/9$.[/step]

[guided]The covering estimate gives a lower bound for the maximal family when $d/k$ is large. Let $L:=\log(d/k)$. Since maximality gives \begin{align*} \mathcal{S}_k \subset \bigcup_{A\in\mathcal{A}}B_A, \end{align*} we have \begin{align*} \binom{d}{k}=|\mathcal{S}_k|\leq |\mathcal{A}|\sup_{A\in\mathcal{A}}|B_A|. \end{align*} The previous step proved $|B_A|\leq \exp(kL/4+3k)$. We also need the lower bound $\binom{d}{k}\geq (d/k)^k$, so we prove it here. Since $d\geq k$ and $1\leq r\leq k$, \begin{align*} \frac{d-k+r}{r} \geq \frac{d}{k}, \end{align*} because $k(d-k+r)-dr=(k-r)(d-k)\geq 0$. Multiplying this inequality over $1\leq r\leq k$ gives \begin{align*} \binom{d}{k}=\prod_{r=1}^{k}\frac{d-k+r}{r}\geq \left(\frac{d}{k}\right)^k. \end{align*} Combining these two estimates gives \begin{align*} \log |\mathcal{A}|\geq kL-\frac{kL}{4}-3k=\frac{3kL}{4}-3k. \end{align*} When $L\geq 8$, the error term $3k$ is absorbed by the main term, so \begin{align*} \log |\mathcal{A}|\geq \frac{3k}{8}\log\left(\frac{d}{k}\right). \end{align*} In that regime we take $\mathcal{A}_*:=\mathcal{A}$. When $L<8$, the preceding absorption is unavailable, so we build a separated family directly. Define \begin{align*} H_0 := -\frac{1}{4}\log\left(\frac{1}{4}\right)-\frac{3}{4}\log\left(\frac{3}{4}\right) \end{align*} and set $\gamma:=\log 2-H_0$. Since $H_0=2\log 2-(3/4)\log 3$, the estimates $\log 3\geq 1.09$ and $\log 2\leq 0.7$ give \begin{align*} \gamma=\frac{3}{4}\log 3-\log 2\geq \frac{1}{9}. \end{align*} A maximal subset $\mathcal{C}\subset\{0,1\}^k$ with pairwise Hamming distance at least $k/4$ has balls of radius strictly less than $k/4$ covering the whole cube. For $0<p\leq 1/2$, we prove the entropy estimate directly. Set $t:=p/(1-p)\in(0,1]$. If $m\leq pk$, then $t^{-m}\leq t^{-pk}$, and hence the binomial theorem gives \begin{align*} \sum_{0\leq m\leq pk}\binom{k}{m}\leq t^{-pk}\sum_{m=0}^k\binom{k}{m}t^m=t^{-pk}(1+t)^k=\exp(kH(p)), \end{align*} where $H(p):=-p\log p-(1-p)\log(1-p)$. With $p=1/4$, the strict-radius sum is included in the sum over $m\leq k/4$, so each ball has at most $\exp(H_0k)$ points. Hence \begin{align*} 2^k\leq |\mathcal{C}|\exp(H_0k). \end{align*} Taking logarithms yields \begin{align*} \log |\mathcal{C}|\geq \gamma k. \end{align*} Now use the assumption $d\geq 2k$. For each $1\leq i\leq k$, define $P_i:=\{2i-1,2i\}$. For $u\in\mathcal{C}$, define $A_u$ by selecting exactly one element from each pair $P_i$: select $2i-1$ if $u_i=0$, and select $2i$ if $u_i=1$. Then $A_u\in\mathcal{S}_k$. If $u$ and $u'$ differ in one coordinate, the corresponding supports differ in both elements of that pair and agree on that pair otherwise. Therefore \begin{align*} |A_u\triangle A_{u'}|=2d_H(u,u')\geq \frac{k}{2}. \end{align*} Set $\mathcal{A}_*:=\{A_u:u\in\mathcal{C}\}$. Since $L<8$, \begin{align*} \log |\mathcal{A}_*|=\log |\mathcal{C}|\geq \gamma k\geq \frac{\gamma}{8}k\log\left(\frac{d}{k}\right). \end{align*} Thus both regimes are covered by the explicit universal constant \begin{align*} c:=\frac{1}{72}, \end{align*} since $1/72\leq 3/8$ in the large-ratio regime and $1/72\leq \gamma/8$ in the bounded-ratio regime by $\gamma\geq 1/9$.[/guided]

[step:Return from supports to binary vectors]For each $A\in\mathcal{A}_*$, let $v_A\in\{0,1\}^d$ be the binary vector whose $i$th coordinate is $1$ when $i\in A$ and $0$ when $i\notin A$. Define \begin{align*} \mathcal{V} := \{v_A \in \{0,1\}^d : A \in \mathcal{A}_*\}. \end{align*} Each $v_A$ has exactly $k$ nonzero coordinates. If $A,B \in \mathcal{A}_*$ are distinct, then \begin{align*} d_H(v_A,v_B)=|A \triangle B| \geq \frac{k}{2}. \end{align*} Finally, since the map $A \mapsto v_A$ is injective, \begin{align*} |\mathcal{V}| = |\mathcal{A}_*|, \end{align*} and the preceding step gives \begin{align*} \log |\mathcal{V}| \geq c k\log\left(\frac{d}{k}\right). \end{align*} This proves all three asserted properties of $\mathcal{V}$.[/step]

[guided]The family $\mathcal{A}_*$ consists of supports, while the theorem asks for binary vectors. For each $A\in\mathcal{A}_*$, define $v_A\in\{0,1\}^d$ by setting the $i$th coordinate equal to $1$ if $i\in A$ and equal to $0$ if $i\notin A$. Because every $A\in\mathcal{A}_*$ belongs to $\mathcal{S}_k$, each vector $v_A$ has exactly $k$ nonzero coordinates. Now define \begin{align*} \mathcal{V}:=\{v_A\in\{0,1\}^d:A\in\mathcal{A}_*\}. \end{align*} If $A,B\in\mathcal{A}_*$ are distinct, then the coordinates where $v_A$ and $v_B$ differ are precisely the elements of $A\triangle B$. Therefore \begin{align*} d_H(v_A,v_B)=|A\triangle B|\geq \frac{k}{2}. \end{align*} The map $A\mapsto v_A$ is injective because the support of $v_A$ is exactly $A$, so \begin{align*} |\mathcal{V}|=|\mathcal{A}_*|. \end{align*} Using the lower bound from the previous step, with the explicit universal constant $c=1/72$, gives \begin{align*} \log |\mathcal{V}|\geq c k\log\left(\frac{d}{k}\right). \end{align*} Thus $\mathcal{V}$ has constant weight $k$, pairwise Hamming distance at least $k/2$, and the required logarithmic cardinality lower bound.[/guided]