2
$\begingroup$

Looking for a simple upper-bound for the packing number of hamming cube, I'm led to consider the following. Fix $p \in (0,1/2]$. For a positive integer $n$, define $S_n(p) := \sum_{i=1}^{\lfloor np\rfloor}{n\choose i}$, and $M_n(p) := 1-\dfrac{1}{n}\log_2S_n(p)$. Note that $B_n(p):=2^n/S_n(p)$ is a well-known $np$-packing number of $\{0,1\}^n$. For example, see https://mathoverflow.net/a/283202/78539.

I've empirically observed that

Empirical observation. $M_n(p) \le 1-H_2(p)$ for every $n$, where $H_2:[0,1] \to [0,1]$ is the binary entropy function. See figure below.

enter image description here

Question. Is there a simple proof for the above observation ?

$\endgroup$
5
  • $\begingroup$ This is true, see e.g. Lemma 3.6 in Robert M. Gray's book "Entropy and Information Theory". $\endgroup$ Commented Mar 22, 2021 at 10:33
  • $\begingroup$ @OfirGorodetsky Thanks for the input. Which edition of the book are you referring to ? I've managed to get hold of this free pdf version ee.stanford.edu/~gray/it.pdf, but no Lemma 3.6. Also note the non-asymptotic (i.e any $n$) aspect of my question. $\endgroup$
    – dohmatob
    Commented Mar 22, 2021 at 10:47
  • 1
    $\begingroup$ I should have specified. I refer to the second edition, available on google books, see page 74: books.google.co.il/…. Gray does not give an attribution, but this result is certainly was known before the publication of the book. $\endgroup$ Commented Mar 22, 2021 at 12:24
  • 1
    $\begingroup$ Galvin provides a conceptual proof in Theorem 3.1 here: arxiv.org/abs/1406.7872 . $\endgroup$ Commented Mar 22, 2021 at 12:28
  • $\begingroup$ Great, thanks for the refs. $\endgroup$
    – dohmatob
    Commented Mar 22, 2021 at 12:42

1 Answer 1

1
$\begingroup$

Based on comments and references from user Ofir Gorodetsky, we can prove the following

Proposition. $M_n(p) \le 1-H_2(p)$ for every positive integer $n$ and every $p \in (0,1/2)$.

Proof. As $p \in (0,1/2)$, we from Theorem 3.1 of this tutorial that

$$ S_n(p):= \sum_{1 \le i \le np}{n \choose i} \le 2^{nH_2(p)}. $$

Thus, $M_n(p) := 1-(1/n)\log_2 S_n(p) \le 1-H_2(p)$, which concludes the proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .