7 Entropy and Asymptotic Bounds

7.1 Overview

This chapter develops the asymptotic relationship between Hamming ball sizes and the \(q\)-ary entropy function \(H_q\), and provides the key binomial lower bound used in the Gilbert–Varshamov argument.

7.2 Asymptotic upper bound on ball size

Theorem 7.1 Entropy upper bound on Hamming balls

✓

For \(0\lt p\le 1-1/q\) and \(q=|\alpha |\),

\[ |B_{\lfloor np\rfloor }(c)| \; \le \; q^{H_q(p)\, n}. \]

7.3 Entropy algebra lemmas

Lemma 7.2 Simplifying \(q^{H_q(p)}\)

✓

For \(q\ge 2\) and \(0\lt p\lt 1\),

\[ q^{H_q(p)} \; =\; (q-1)^p\, p^{-p}\, (1-p)^{-(1-p)}. \]

Lemma 7.3 Same identity, alternate exponentiation

✓

Variant using a different exponentiation operator.

7.4 Analytic helpers

Lemma 7.4 Square-root/floor inequality

✓

For \(x\ge 0\),

\[ \sqrt{x} - \sqrt{\lfloor x\rfloor } \; \le \; 1. \]

7.5 Stirling-based binomial lower bound

Lemma 7.5 Asymptotic lower bound on binomial term

✓

For \(0\lt p\lt 1\) and \(q\ge 2\), eventually

\[ \tbinom {n}{\lfloor np\rfloor }(q-1)^{pn} \; \ge \; q^{H_q(p)\, n - \varepsilon (n)}, \quad \varepsilon (n) = o(n). \]

7.6 Positivity of \(q\)-ary entropy

Theorem 7.6 Positivity of \(q\)-ary entropy

✓

For \(q=|\alpha |\) and \(0\lt p\le 1-1/q\),

\[ H_q(p) \; \gt \; 0. \]

7.7 Additional declarations

Lemma 7.7 Expansion of the \(q\)-ary entropy exponent

✓

Algebraic rewrite of the \(q\)-ary entropy exponent: for \(q\in \mathbb {N}\) and \(p\in \mathbb {R}\),

\[ p\, \log _q(q-1) - p\, \log _q p - (1-p)\, \log _q(1-p) = \log _q(q-1)\, p + \log _q p\, (-p) + \log _q(1-p)\, (-(1-p)). \]

Lemma 7.8 AM–GM for two nonnegative reals

✓

For nonnegative reals \(a,b\ge 0\), the geometric mean is at most the arithmetic mean:

\[ \sqrt{ab} \; \le \; \frac{a+b}{2}. \]

Lemma 7.9 A Stirling square-root identity

✓

For \(n\ge 0\),

\[ \sqrt{2\pi n}\, \cdot \, \sqrt{\pi /2}\, \cdot \, \sqrt{n} \; =\; \pi n. \]

Lemma 7.10 Positivity of \(\lfloor np\rfloor \) for large \(n\)

✓

Let \(0\lt p\) and \(0\lt 1-p\), and set \(N_2 = \lceil 2/(p(1-p))\rceil + 1\). If \(N_2 \le n\), then \(\lfloor np\rfloor \gt 0\).

Lemma 7.11 Stirling-based ratio bound for the binomial term

✓

Let \(a,b,n\in \mathbb {N}\) with \(a,b\gt 0\), \(a+b=n\), and let \(c\gt 0\). Suppose the Stirling-type bound

\[ a!\, \cdot \, b! \; \le \; c\cdot \Big(\sqrt{2}\sqrt{a}\sqrt{\pi }\, (a/e)^a\cdot \sqrt{2}\sqrt{b}\sqrt{\pi }\, (b/e)^b\Big) \]

holds. Then

\[ \frac{n^n}{a^a\, b^b}\, \Big/\, \big(c\, \sqrt{\pi /2}\, \sqrt{n}\big) \; \le \; \frac{n!}{a!\, b!}. \]