3 6 2 Spreading Points In A Sparse Hypercube

1) Assume that we can find $\displaystyle z \in \{0,1\}_D^p \setminus \bigcup_{\beta \in \mathcal{C}} \{ x \in \{0,1\}_D^p : |x - \beta|_0 \leq D \}$. Then

(1)

\begin{align} \forall \beta \neq \beta' \in \mathcal{C}&, \quad | \beta - \beta'|_0 > D \qquad &\text{by definition of } \mathcal{C} \\ \forall \beta \in \mathcal{C}&, \quad | \beta - z|_0 > D \qquad &\text{by definition of } z \\ \end{align}

hence

(2)

\begin{align} \forall \beta \neq \beta' \in \mathcal{C} \cup \{z\} &, \quad | \beta - \beta'|_0 > D \end{align}

which contradicts the assumption that $\mathcal{C}$ is maximal. Thus,

(3)

\begin{align} \{0,1\}_D^p \subset \left\{ x \in \{0,1\}_D^p : |x - \beta|_0 \leq D \right\} \end{align}

The other inclusion is obvious and proves the expected equality.
Then,

(4)

\begin{align} C^D_p = |\{0,1\}_D^p| &= |\bigcup_{\beta \in \mathcal{C}} \{ x \in \{0,1\}_D^p : |x - \beta|_0 \leq D \}| \\ &= | \bigcup_{\beta \in \mathcal{C}} B(\beta, D)| \\ &\leq \sum_{\beta \in \mathcal{C}} | B(\beta, D)| \\ &\leq \sum_{\beta \in \mathcal{C}} \max_{\beta \in \mathcal{C}}|B(\beta, D)| \\ &= |\mathcal{C}| \max_{\beta \in \mathcal{C}}|B(\beta, D)| \\ \end{align}

which is the expected inequality.

2) Let $\beta \in \{0,1\}^p_D$. Define $k(x) = |\{ i \in \{1, \dots, p\} : \beta_i = 1 \text{ and } x_i = 0 \}|$. Then

(5)

\begin{align} \forall x \in \{0,1\}^p_D, \quad |x -\beta|_0 = 2 k(x) \end{align}

and therefore

(6)

\begin{align} \forall x \in \{0,1\}^p_D, \quad x \in B(\beta, D) \Leftrightarrow k(x) \in \{0, \dots, \lfloor \frac{D}{2} \rfloor\} \end{align}

Let $k \in \{0, \dots, d\}$, we try to construct $x$ such that $k(x)=k$. There are $C^k_D$ ways to choose the $k$ terms of $x$ where $\beta_i = 1$ and $x_i = 0$, and $C^k_{p-D}$ ways to choose the $k$ terms where $\beta_i = 0$ and $x_i = 1$. Hence

(7)

\begin{align} | \{ x \in \{0,1\}^p_D : k(x) = k\} | = C^k_D C^k_{p-D} \end{align}

Finally, we use that

(8)

\begin{align} B(\beta, D) = \bigsqcup_{k = 0}^d \{ x \in \{0,1\}^p_D : k(x) = k\} \end{align}

where $d := \lfloor \frac{D}{2} \rfloor$ to get

(9)

\begin{align} | B(\beta, D) | = \sum_{k = 0}^d C^k_D C^k_{p-D} \end{align}

which proves the first equality.

For the second inequality, note that $C^{k+1}_{p-D} = \frac{p-D-k}{k+1} C^k_{p-D}$. Since here $k+1 \leq d+1 \leq 2D \leq \frac{p-D}{2}$, we deduce that $C^k_{p-D} \leq C^d_{p-D}$ for all $k \in \{0, \dots, d\}$. We can then use that $C^d_{p-D} \leq C^d_p$, which gives:

(10)

\begin{align} \sum_{k = 0}^d C^k_D C^k_{p-D} &\leq \sum_{k = 0}^d C^k_D C^d_p \\ &\leq C^d_p \sum_{k = 0}^D C^k_D \\ &= 2^D C^d_p \end{align}

which proves the second inequality.

Then, we can write

(11)

\begin{align} \frac{C^d_p}{C^D_p} &= \frac{D!(p-D)!}{d!(p-d)!} \\ &= \frac{D\dots(d+1)}{(p-d)\dots(p-D+1)} \\ &\leq \frac{D^{D-d}}{(p-D+1)^{D-d}} \end{align}

which is the third inequality.

Finally,

(12)

\begin{align} 2^D \left( \frac{D}{p-D+1} \right)^{D-d} &= 2^D \left( \frac{D}{p-D+1} \right)^{\lceil D/2 \rceil} \\ &\leq 4^{\lceil D/2 \rceil} \left( \frac{D}{p-D+1} \right)^{\lceil D/2 \rceil} \\ &= \left( \frac{4D}{p-D+1} \right)^{\lceil D/2 \rceil} \end{align}

$p \geq 5D$ implies that $\frac{4D}{p-D} \leq \frac{5D}{p}$ and a fortiori $\frac{4D}{p-D+1} \leq \frac{5D}{p}$, so that

(13)

\begin{align} \left( \frac{4D}{p-D+1} \right)^{\lceil D/2 \rceil} &\leq \left( \frac{5D}{p} \right)^{\lceil D/2 \rceil} \\ &\leq \left( \frac{5D}{p} \right)^{D/2} \end{align}

since $\frac{5D}{p} \leq 1$ and $\lceil D/2 \rceil \geq D/2$.

3) We proved in question 1) that

(14)

\begin{align} \frac{1}{|\mathcal{C}|} \leq \frac{\max_{\beta \in \mathcal{C}} |B(\beta, D)|}{C^D_p} \end{align}

and in question 2) that

(15)

\begin{align} \forall \beta \in \mathcal{C}, \quad \frac{|B(\beta, D)|}{C^D_p} \leq \left( \frac{5D}{p} \right)^{D/2} \end{align}

We deduce that

(16)

\begin{align} \frac{1}{|\mathcal{C}|} \leq \left( \frac{5D}{p} \right)^{D/2} \end{align}