Sphere-packing converse above the finite-divergence threshold

The allowed $V$ form a compact product of row simplexes. For fixed $P$, $I_P(V)$ and $D_P(V)$ are continuous in $V$: finite sums use $t\ln t\to 0$ at zero by [F12], and every denominator $W(y\mid x)$ charged by $V$ is a fixed positive transition. Thus $J(P)={\min }_V{I}_P(V)$ exists. The joint map $(P,V)\mapsto I_P(V)$ is continuous on the compact product of the input simplex and the allowed-channel set; [F7] makes it uniformly continuous. Therefore $\mathrm{\mid }J(P)-J(P^{\mathrm{\prime }})\mathrm{\mid }\le {\sup }_V\mathrm{\mid }{I}_P(V)-I_{P^{\mathrm{\prime }}}(V)\mathrm{\mid }\to 0$ as $P^{\mathrm{\prime }}\to P$. The continuous $J$ attains its finite maximum $R_{\mathrm{\infty }}$ by [F7]. Since finite mutual information is nonnegative by [F4], $J(P)\ge 0$ and $R_{\mathrm{\infty }}\ge 0$. Since $R>R_{\mathrm{\infty }}$, for every $P$ its minimizing channel $V_0$ satisfies $I_P(V_0)=J(P)<R$.

Consider any deterministic $M\ge 2$ message code whose every codeword has type $P$, and evaluate its average error $e_V$ through the product channel $V^n$. Let $U$ be its uniform message and $X^n$ its codeword. Since $X^n$ is a function of $U$ and the channel depends on $U$ only through $X^n$, $I(U;Y^n)=H(Y^n)-H(Y^n\mid U)$. The finite entropy chain rule and nonnegative conditional mutual information in [F4] give $H(Y^n)\le {\sum }_{i}H(Y_i)$. The product-channel law in [F1] gives $H(Y^n\mid U)={\sum }_{i}H(Y_i\mid X_i)$, so $I(U;Y^n)\le {\sum }_{i}I(X_i;Y_i)={\sum }_i{I}_{P_i}(V)$, where $P_i$ is the law of $X_i$ under the uniform message. Every codeword has type $P$, hence $n^{-1}{\sum }_i{P}_i=P$. Concavity [F13] and finite Jensen [F10] imply $I(U;Y^n)\le n{I}_P(V)$. Fano's inequality [F3] now yields $e_V\ge 1-\frac{n{I}_P(V)+\ln 2}{\ln M}\mathrm{.}$ The entropy formula [F5] and limit [F12] also show that $P\mapsto I_P(V)$ is continuous, as needed when types vary.

For fixed $P$, the closed feasible set $\{V:I_P(V)\le R\}$ is nonempty and compact, so $S_P(R):={\min }_{I_P(V)\le R}{D}_P(V)$ exists. The open infimum over $I_P(V)<R$ equals this minimum: if $V^{\ast }$ minimizes the closed problem, mix it with the strict witness $V_0$ from step 1.1. Convexity of $I_P$ gives $I_P((1-t)V^{\ast }+t{V}_0)<R$ for $t>0$, while continuity gives $D_P((1-t)V^{\ast }+t{V}_0)\to S_P(R)$. For $D_P$, [F6] gives convexity row by row and then after the finite $P$-weighted sum. For $I_P$, write it as $D(P{V}_{XY}\mathrm{\parallel }P\otimes P{V}_Y)$; both arguments are the same convex mixtures when $V$ is mixed, so [F6] gives convexity. This proves the required convexity and continuity facts.

For each row $x$, under $V(\cdot \mid x)$ the log ratio $\ln [V(Y\mid x)\mathrm{/}W(Y\mid x)]$ has mean $D(V_x\mathrm{\parallel }{W}_x)$ and variance bounded uniformly over allowed $V$: the finite set of positive $W(y\mid x)$ has a positive minimum, and $t(\ln (t\mathrm{/}W(y\mid x)){)}^2$ extends continuously at $t=0$. Thus for some finite $K_W$, a codeword of type $P_n$ has log ratio $L=\ln [V^n(Y^n\mid x^n)\mathrm{/}{W}^n(Y^n\mid x^n)]$ with mean $n{D}_{P_n}(V)$ and variance at most $n{K}_W$. On $L>n(D_{P_n}(V)+\eta )$, the squared centered deviation exceeds $n^2{\eta }^2$, so the event indicator is at most $(L-\mathbb{E}L{)}^2\mathrm{/}(n^2{\eta }^2)$. Taking expectations gives $V^n\{L>n(D_{P_n}(V)+\eta )\}\le K_W\mathrm{/}(n{\eta }^2)$. On its complement $W^n\ge e^{-n(D_{P_n}(V)+\eta )}{V}^n$; integrating over decoder error events gives $e_W\ge e^{-n(D_{P_n}(V)+\eta )}(e_V-\frac{K_W}{n{\eta }^2})\mathrm{.}$

At each $n$, choose a code attaining the finite-block minimum average error. For any such code of size $M_n$, partition its messages into input types; there are at most $(n+1{)}^{\mathrm{\mid }\mathcal{X}\mathrm{\mid }}$ types. Restrict to a largest type class of size $M_n^{\mathrm{\prime }}\ge M_n\mathrm{/}(n+1{)}^{\mathrm{\mid }\mathcal{X}\mathrm{\mid }}$. Reindex the retained messages and map every old decoder output outside the retained class to one fixed retained message. For each retained message this decoder cannot increase its error, so if $e_n$ is the original average error and $e_n^{\mathrm{\prime }}$ the restricted one, then $e_n\ge (M_n^{\mathrm{\prime }}\mathrm{/}{M}_n)e_n^{\mathrm{\prime }}$. Since $M_n=\lceil e^{nR}\rceil$ and $R>0$ by step 1.1, $M_n^{\mathrm{\prime }}$ grows exponentially and $n^{-1}\ln M_n^{\mathrm{\prime }}\to R$ by [F12]. Along any subsequence realizing the limsup exponent, compactness gives a further subsequence of selected types $P_n\to P$. For each allowed $V$ with $I_P(V)<R$, continuity from step 1.2 makes its Fano lower bound bounded away from zero; step 2.2 then gives $\mathrm{lim\hspace{0.17em}sup}-n^{-1}\ln e_n\le D_P(V)+\eta$, since the type-class factor costs only $\mathrm{\mid }\mathcal{X}\mathrm{\mid }\ln (n+1)\mathrm{/}n$. Letting $\eta \downarrow 0$ and taking the infimum over strict-feasible $V$ proves $E_{\mathrm{a}\mathrm{v}}^{+}(R)\le {\sup }_P{\inf }_{V:I_P(V)<R}{D}_P(V)={\sup }_P{S}_P(R),$ where the equality is step 2.1. Since every code's maximal error is at least its average error, $P_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }(n,M_n)\ge P_{\mathrm{a}\mathrm{v}}^{\ast }(n,M_n)$ and the same upper bound holds for $E_{\mathrm{m}\mathrm{a}\mathrm{x}}^{+}$.

Fix $P$. Form the upper image $G=\{(a,b):a\ge I_P(V),b\ge D_P(V)\text{ for some allowed }V\}$ and the open convex set $O=(-\mathrm{\infty },R)\times (-\mathrm{\infty },S_P(R))$. They are nonempty convex sets. If a point lay in both, its witnessing $V$ would satisfy $I_P(V)<R$ and $D_P(V)<S_P(R)$, contradicting the definition of the closed minimum; hence they are disjoint. Convexity of $G$ follows from step 2.1. Apply [F8] under [A1] to obtain a nonzero normal separating $G$ from $O$. Because $G$ is upper in each coordinate, the separating normal in the orientation $a\cdot g\le a\cdot o$ must have nonpositive coordinates (otherwise increasing that coordinate of $g$ violates separation). Reversing its sign gives weights $u,v\ge 0$, not both zero, with $u{I}_P(V)+v{D}_P(V)\ge uR+v{S}_P(R)\text{for every allowed }V\mathrm{.}$ Strict feasibility from step 1.1 forces $v>0$: if $v=0$, then $u>0$ and the inequality contradicts $I_P(V_0)<R$. Normalize $v=1$ and put $\rho =u\mathrm{/}v\ge 0$.

The separator gives ${\inf }_V\{D_P(V)+\rho I_P(V)\}-\rho R\ge S_P(R)$. Conversely, a minimizer $V^{\ast }$ of the closed problem has $I_P(V^{\ast })\le R$ and $D_P(V^{\ast })=S_P(R)$, so for every $\rho \ge 0$, ${\inf }_V\{D_P(V)+\rho I_P(V)\}-\rho R\le S_P(R)\mathrm{.}$ Thus strict feasibility proves the exact dual identity $S_P(R)={\sup }_{\rho \ge 0}\{E_{0,\mathrm{c}\mathrm{c}}(\rho ,P)-\rho R\},$ with $E_{0,\mathrm{c}\mathrm{c}}(0,P)=0$.

Taking suprema over $P$ and $\rho$ in step 4.1, interchanging two suprema, and applying [F9] for $\rho >0$ (at $\rho =0$ both optimized quantities are zero) gives ${\sup }_P{S}_P(R)={\sup }_{\rho \ge 0}\{{\max }_P{E}_0(\rho ,P)-\rho R\}=E_{\mathrm{s}\mathrm{p}}(R)\mathrm{.}$ Combining with step 3.1 proves both stated converses. The strict condition $R>R_{\mathrm{\infty }}$ was used in steps 1.1, 2.1, and 4.1; no endpoint conclusion follows from this proof.