4 Entropy and Asymptotic Bounds
4.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.
4.2 Asymptotic upper bound on ball size
For \(0\lt p\le 1-1/q\) and \(q=|\alpha |\),
\[ |B_{\lfloor np\rfloor }(c)| \; \le \; q^{H_q(p)\, n}. \]
4.3 Entropy algebra lemmas
For \(q\ge 2\) and \(0\lt p\lt 1\),
\[ q^{H_q(p)} \; =\; (q-1)^p\, p^{-p}\, (1-p)^{-(1-p)}. \]
Variant using a different exponentiation operator.
4.4 Analytic helpers
For \(x\ge 0\),
\[ \sqrt{x} - \sqrt{\lfloor x\rfloor } \; \le \; 1. \]
4.5 Stirling-based binomial lower bound
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). \]
4.6 Positivity of \(q\)-ary entropy
For \(q=|\alpha |\) and \(0\lt p\le 1-1/q\),
\[ H_q(p) \; \gt \; 0. \]