Introduction
AI disclaimer. Based on previous tight second-order results for the interconversion of specific channels, the general characterization given here was developed with ChatGPT (5.6 Sol and 6 Astra). The manuscript proposes a solution to an open problem in quantum information theory that we believe is of interest to the community. We also see an urgent need for a community discussion of appropriate formats for the communication of AI-generated scientific content.
Channel coding [1 ] uses a noisy channel to transmit messages reliably. Channel simulation [2 , 3 ] uses noiseless communication to reproduce a noisy channel. Channel interconversion combines these two tasks [4 , 23 ] . Given a resource channel T T T and a target channel W W W , we ask how many uses of W W W can be simulated using n n n uses of T T T , at a prescribed error.
With unlimited shared randomness, a channel code for T T T followed by a simulation protocol for W W W achieves the first-order rate C T / C W C_T/C_W C T / C W [1 , 2 , 3 ] . The reverse conversion has the reciprocal rate. Thus capacity determines reversibility at first order. At finite blocklength, however, optimizing coding and simulation separately need not give the best interconversion protocol. This approach first transmits information reliably and then adds noise. A direct protocol can instead use the noise already present in the resource. For example, a channel simulates itself exactly by direct use. The capacity ratio alone therefore does not determine the second-order correction.
Overview of main results
We characterize this correction under non-signalling superchannels . The assistance is a non-signalling channel N ( x , z ∣ s , y ) N(x,z\mid s,y) N ( x , z ∣ s , y ) , also called a non-signalling box. The sender supplies s s s and receives x x x . The receiver supplies y y y and receives z z z . The distribution of x x x does not depend on y y y , and the distribution of z z z does not depend on s s s . Connecting the resource channel to this box gives
Θ N [ T ] ( z ∣ s ) = ∑ x , y T ( y ∣ x ) N ( x , z ∣ s , y ) . \Theta_N[T](z\mid s)=\sum_{x,y}T(y\mid x)N(x,z\mid s,y). Θ N [ T ] ( z ∣ s ) = x , y ∑ T ( y ∣ x ) N ( x , z ∣ s , y ) .
Non-signalling correlations include those obtainable from shared randomness or shared entanglement. Their optimal performance therefore gives a converse bound for both assistance classes [4 ] . These correlations do not themselves transmit a message: all communication passes through the resource channel. Figure 1 shows the corresponding transformation. The sender’s resource input is chosen without access to the resource output. No feedback is supplied. We measure error by the maximum, over target input words, of the total variation distance between the simulated and target output laws. This ensures that the approximation holds for every target input, without assuming an input distribution.
Figure 1. A non-signalling superchannel. The upper box is one bipartite conditional distribution, not two local maps supplied with a shared classical variable. Its sender marginal is independent of y n y^n y n , and its receiver marginal is independent of s m s^m s m . Connecting its output x n x^n x n to its input y n y^n y n through T ⊗ n T^{\otimes n} T ⊗ n gives the simulated channel. The return wire is not feedback to the sender.
The general result allows all dispersions in [ V min ( K ) , V max ( K ) ] [V_{\min}(K),V_{\max}(K)] [ V m i n ( K ) , V m a x ( K )] , provided C K > 0 C_K>0 C K > 0 and V min ( K ) > 0 V_{\min}(K)>0 V m i n ( K ) > 0 for K = T , W K=T,W K = T , W (Theorem A.1 ), but to keep the main text simple, we assume (the general result and its proof are given in Appendix § 5 )
V min ( T ) = V max ( T ) = V T > 0 , V min ( W ) = V max ( W ) = V W > 0. V_{\min}(T)=V_{\max}(T)=V_T>0,\qquad V_{\min}(W)=V_{\max}(W)=V_W>0. V m i n ( T ) = V m a x ( T ) = V T > 0 , V m i n ( W ) = V m a x ( W ) = V W > 0.
This specialization includes nontrivial binary symmetric and binary erasure channels and does not require a unique capacity-achieving input. Let m N S ∗ ( n , ϵ ; T , W ) m_{\mathrm{NS}}^*(n,\epsilon;T,W) m NS ∗ ( n , ϵ ; T , W ) be the largest target length attainable with error at most ϵ \epsilon ϵ .
Theorem 1.1 (Second-order channel interconversion). Under these assumptions, for every fixed 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 ,
m N S ∗ ( n , ϵ ; T , W ) = r n + d ϵ C W n + O ( log n ) , r = C T C W . (1) m_{\mathrm{NS}}^*(n,\epsilon;T,W)=rn+\frac{d_\epsilon}{C_W}\sqrt{n}+O(\log n),\qquad r=\frac{C_T}{C_W}. \tag*{(1)} m NS ∗ ( n , ϵ ; T , W ) = r n + C W d ϵ n + O ( log n ) , r = C W C T . (1) where the coefficient is the one-dimensional Gaussian optimization
d ϵ = inf ϵ < η < 1 { V T Φ − 1 ( η ) − r V W Φ − 1 ( η − ϵ ) } . (2) d_\epsilon=\inf_{\epsilon<\eta<1}\left\{\sqrt{V_T}\Phi^{-1}(\eta)-\sqrt{rV_W}\Phi^{-1}(\eta-\epsilon)\right\}. \tag*{(2)} d ϵ = ϵ < η < 1 inf { V T Φ − 1 ( η ) − r V W Φ − 1 ( η − ϵ ) } . (2) Here Φ \Phi Φ is the standard normal distribution function.
Equivalently, the optimal rate is r + d ε / ( C W n ) + O ( log n / n ) r + d_{\varepsilon}/(C_{W}\sqrt{n}) + O(\log n/n) r + d ε / ( C W n ) + O ( log n / n ) . The capacities determine the first-order conversion rate. The two total information variances n V T nV_{T} n V T and r n V W rnV_{W} r n V W determine the correction. The formula is a difference of Gaussian quantiles optimized over one parameter, rather than the sum of the separate coding and simulation penalties. Section 4 proves the theorem. Appendix D also gives an exact characterization for additive channels without a positive-dispersion assumption, including their zero-dispersion cases. General channels with V min = 0 V_{\min}=0 V m i n = 0 are not covered by the Gaussian theorem.
Relation to state dichotomies
The comparison of statistical experiments goes back to Blackwell, Sherman, and Stein. Le Cam’s deficiency theory treats approximate comparison [10 , 11 , 12 ] . A classical state dichotomy is a binary experiment, specified by a pair of distributions ( p , q ) (p,q) ( p , q ) . Its conversion to ( p ′ , q ′ ) (p',q') ( p ′ , q ′ ) asks for a stochastic map that approximates p ′ p' p ′ from p p p while mapping q q q to q ′ q' q ′ exactly. Renes’ relative submajorization theorem expresses its optimal error as a gap between testing curves [14 ] . The corresponding second-order conversion law is determined in [6 ] . For channels, the corresponding reference objects are the replacer channels R Q ( y ∣ x ) = Q ( y ) R_{Q}(y\mid x)=Q(y) R Q ( y ∣ x ) = Q ( y ) , which carry no information about their input. A single NS superchannel satisfies
Θ N [ T ] = W ~ ≈ W , Θ N [ R Q ] = R D N Q for every output law Q , (3) \begin{aligned}
\Theta_{N}[T] &= \widetilde{W} \approx W,\\
\Theta_{N}[R_{Q}] &= R_{D_{N}Q} \quad\text{for every output law } Q, \tag*{(3)}
\end{aligned} Θ N [ T ] Θ N [ R Q ] = W ≈ W , = R D N Q for every output law Q , (3)
where D N ( z ∣ y ) = ∑ x N ( x , z ∣ s , y ) D_{N}(z\mid y)=\sum_{x}N(x,z\mid s,y) D N ( z ∣ y ) = ∑ x N ( x , z ∣ s , y ) is a single stochastic map fixed by the protocol. Thus the same transformation maps every input-independent channel to another input-independent channel, rather than preserving just one chosen reference. The output reference D N Q D_{N}Q D N Q is determined by the protocol and is not prescribed independently. This also motivates the choice of NS assistance: among classical superchannels, these are precisely the transformations that preserve the family of channels carrying no information [5 ] . Section 2 proves this directly from the two marginal conditions.
For each target input law P S P_{S} P S , this channel transformation induces a stochastic map between the joint input–output experiments
( P X ( x ) T ( y ∣ x ) , P X ( x ) Q ( y ) ) ⟼ ( P S ( s ) W ~ ( z ∣ s ) , P S ( s ) ( D N Q ) ( z ) ) , \bigl(P_{X}(x)T(y\mid x),P_{X}(x)Q(y)\bigr)
\longmapsto
\bigl(P_{S}(s)\widetilde{W}(z\mid s),P_{S}(s)(D_{N}Q)(z)\bigr), ( P X ( x ) T ( y ∣ x ) , P X ( x ) Q ( y ) ) ⟼ ( P S ( s ) W ( z ∣ s ) , P S ( s ) ( D N Q ) ( z ) ) ,
with P X P_{X} P X induced by the sender marginal. The same induced map works for every Q Q Q (Proposition 3.1 ). The channel problem therefore has two requirements. The approximation must hold for every target input, and the same protocol must map every replacer channel to another replacer channel. A transformation of one chosen binary experiment need not satisfy either condition.
The distinction is operational. A state map can generate the target input label itself and correlate it with the output. A channel protocol must instead respond to an input supplied from outside. For example, a map for one fixed pair can appear to create a noiseless bit from a channel with constant output, while violating the receiver NS condition (§ 3.2 ). Our construction enforces the channel constraints at logarithmic communication cost. This is the sense in which the theory of state dichotomies extends to channels. It does not give a one-shot equivalence with the conversion of a fixed pair. The NS conditions must still be imposed.
From binary experiments to universal channel protocols
Our starting point is the comparison of testing curves in [14 Theorem 2] . Information spectrum estimates and Gaussian limits then suggest the second-order profile [7 , 8 , 6 ] . To prove a channel theorem, we need a protocol attaining that profile and a converse valid for every allowed protocol. Classical comparison theory already treats whole families of distributions. The extra requirement here is that a transformation of joint input–output distributions must respect the separation between sender and receiver. In particular, it must respond to the target input rather than generate that input itself.
Converse. This is more standard and the state map induced by a channel protocol is due to Oufkir, Yao, and Berta [23 Lemma 24] . It works for every resource reference law, but the target reference is fixed by the protocol and cannot be chosen independently. Resource inputs may also be correlated. Appendix § 6 handles these choices using uniform type-class estimates, bounds on output distributions, and Markov’s inequality. Near capacity-achieving inputs, we use the quadratic decay of mutual information [27 ] . A central limit theorem for one fixed iid input would not justify optimization over all these choices.
Achievability. We use the method of types [30 ] . First, restrict the target inputs to one type class. Averaging over target coordinate permutations makes the target input label uniform on that class. This gives the sender marginal needed to turn the state map into a conditional distribution for a channel protocol. The same symmetry makes the error equal for every input in the class. Next, average independently over resource permutations. The receiver marginal is then constant on each output type class. A reference distribution that assigns equal mass to these classes bounds this marginal at every output, up to a polynomial factor. We then enforce the receiver NS condition. The construction extends the diagonal and off-diagonal completion used in NS simulation [3 Proposition 18] , while retaining the noisy resource. When the auxiliary symbols agree, we use the desired conditional distribution. When they differ, we add a nonnegative correction. Both NS conditions then hold for every input to the box. A second auxiliary message identifies the target type. Its mismatched branches must also be completed so that the full protocol remains NS. Ordinary coding below capacity sends both auxiliary messages using O ( log n ) O(\log n) O ( log n ) of the prescribed resource uses, with error at most n − 2 n^{-2} n − 2 . The total error is bounded by the largest typewise error plus the auxiliary coding error. There is no factor equal to the number of types. § 3.2 gives the NS channels. Proposition 3.3 accounts for their communication cost.
Finite-error resonance and short blocklengths
The limiting error at length m = ⌈ r n + ( d / C W ) n ⌉ m=\lceil rn+(d/C_W)\sqrt{n}\rceil m = ⌈ r n + ( d / C W ) n ⌉ is
E ( d ) = sup ξ ∈ R { Φ ( ξ V T ) − Φ ( ξ − d r V W ) } . (4) \mathcal{E}(d)=\sup_{\xi\in\mathbb{R}}\left\{\Phi\left(\frac{\xi}{\sqrt{V_T}}\right)-\Phi\left(\frac{\xi-d}{\sqrt{rV_W}}\right)\right\}. \tag*{(4)} E ( d ) = ξ ∈ R sup { Φ ( V T ξ ) − Φ ( r V W ξ − d ) } . (4)
This is the sesquinormal profile S ν ( d / V T ) S_\nu(d/\sqrt{V_T}) S ν ( d / V T ) of [6 Lemma 1] , with ν = r V W / V T \nu=rV_W/V_T ν = r V W / V T . Here we show that this profile is also attainable by universal channel protocols. The coefficient in Theorem 1.1 is obtained by inverting this limiting error. In particular, define the threshold error
ϵ ∗ : = E ( 0 ) = ∣ Φ ( x ν ) − Φ ( x ν / ν ) ∣ , x ν = ν ln ν ν − 1 , ν = r V W V T . (5) \epsilon_*:=\mathcal{E}(0)=\left|\Phi(x_\nu)-\Phi(x_\nu/\sqrt{\nu})\right|,\qquad x_\nu=\sqrt{\frac{\nu\ln\nu}{\nu-1}},\qquad\nu=\frac{rV_W}{V_T}. \tag*{(5)} ϵ ∗ := E ( 0 ) = Φ ( x ν ) − Φ ( x ν / ν ) , x ν = ν − 1 ν ln ν , ν = V T r V W . (5)
with ϵ ∗ = 0 \epsilon_*=0 ϵ ∗ = 0 at ν = 1 \nu=1 ν = 1 . If ν ≠ 1 \nu\ne1 ν = 1 , then 0 < ϵ ∗ < 1 / 2 0<\epsilon_*<1/2 0 < ϵ ∗ < 1/2 and
d ϵ ∗ = 0 , m N S ∗ ( n , ϵ ∗ ; T , W ) n = r + O ( log n n ) . (6) d_{\epsilon_*}=0,\qquad\frac{m_{\mathrm{NS}}^*(n,\epsilon_*;T,W)}{n}=r+O\left(\frac{\log n}{n}\right). \tag*{(6)} d ϵ ∗ = 0 , n m NS ∗ ( n , ϵ ∗ ; T , W ) = r + O ( n log n ) . (6)
Thus, at a fixed and possibly small error, the n − 1 / 2 n^{-1/2} n − 1/2 rate correction vanishes and only higher-order terms remain. This is a threshold-error interpretation of finite-error resonance illustrated for state dichotomies in Figure 2 of [6 ] . Such a threshold exists for every pair with ν ≠ 1 \nu\ne1 ν = 1 .
Figure 2. Threshold errors at the capacity ratio, analogous to Fig. 2 of [6 ] . (a) NS conversion from a BEC to a BSC. The SR curve is not known. (b) SR conversion from a two-bit packet-erasure channel to a BEC. Here the SR, EA, and NS limits coincide. At the orange points, the second-order coefficient at 1% error vanishes. It is nonnegative in the shaded intervals. At the blue zeros, the error at the capacity ratio tends to zero. These are limiting curves, not finite-blocklength error bounds.
Its size depends on the difference between the two ratios of dispersion to capacity. For ϵ < ϵ ∗ \epsilon< \epsilon_* ϵ < ϵ ∗ the coefficient is negative, and for ϵ > ϵ ∗ \epsilon> \epsilon_* ϵ > ϵ ∗ it is positive. The total information fluctuations match when
V T C T = V W C W . (7) \frac{V_T}{C_T} = \frac{V_W}{C_W}. \tag*{(7)} C T V T = C W V W . (7)
In this case,
E ( d ) = [ 2 Φ ( d 2 V T ) − 1 ] + , d ϵ = 2 V T Φ − 1 ( 1 + ϵ 2 ) . (8) \mathcal{E}(d) = \left[2\Phi\left(\frac{d}{2\sqrt{V_T}}\right)-1\right]_+, \qquad d_\epsilon= 2\sqrt{V_T}\Phi^{-1}\left(\frac{1+\epsilon}{2}\right). \tag*{(8)} E ( d ) = [ 2Φ ( 2 V T d ) − 1 ] + , d ϵ = 2 V T Φ − 1 ( 2 1 + ϵ ) . (8)
Here the error at the capacity-ratio length tends to zero. This zero-threshold resonance is not restricted to identical channels. In this case, d ϵ > 0 d_\epsilon> 0 d ϵ > 0 at every fixed ϵ > 0 \epsilon> 0 ϵ > 0 , so zero-threshold resonance is distinct from cancellation at a positive threshold error.
Non-signalling resonance. Fix W = BSC ( q ) W = \operatorname{BSC}(q) W = BSC ( q ) with q = 0.01 q = 0.01 q = 0.01 and take T = BEC ( δ ) T = \operatorname{BEC}(\delta) T = BEC ( δ ) , where δ \delta δ is the erasure probability. With C q = 1 − h ( q ) C_q = 1 - h(q) C q = 1 − h ( q ) and V q = q ( 1 − q ) log 2 ( ( 1 − q ) / q ) V_q = q(1-q)\log^2((1-q)/q) V q = q ( 1 − q ) log 2 (( 1 − q ) / q ) , resonance occurs at
δ ∗ = V q C q ≃ 0.473 , r = 1 − δ ∗ C q ≃ 0.573. \delta_* = \frac{V_q}{C_q} \simeq0.473, \qquad r = \frac{1-\delta_*}{C_q} \simeq0.573. δ ∗ = C q V q ≃ 0.473 , r = C q 1 − δ ∗ ≃ 0.573.
Figure 2 (a) plots the NS threshold as δ \delta δ varies. The two 1% intersections are approximately δ = 0.436 \delta= 0.436 δ = 0.436 and δ = 0.514 \delta= 0.514 δ = 0.514 : at either endpoint the second-order term vanishes at 1% error, while it is positive between them. The SR threshold curve is not known for this family, unlike the packet example below. The stronger common-encoder converse in Appendix § 7 .§ 3 proves that SR has strictly positive limiting error at the NS zero δ ∗ \delta_* δ ∗ , and a strictly smaller second-order rate at a sufficiently small fixed error (Proposition C.4 ).
The asymptotic remainder alone does not guarantee that the capacity ratio is attainable at a short blocklength. For additive channels, we can check this using an exact finite-blocklength formula. For T = BSC ( 0.1 ) T = \operatorname{BSC}(0.1) T = BSC ( 0.1 ) and W = BSC ( 0.05 ) W = \operatorname{BSC}(0.05) W = BSC ( 0.05 ) ,
r ≃ 0.744 , ϵ ∗ ≃ 0.042 , e N S ( 25 , ⌊ 25 r ⌋ ) = e N S ( 25 , 18 ) < 0.036 < ϵ ∗ . r \simeq0.744, \qquad\epsilon_* \simeq0.042, \qquad e_{\mathrm{NS}}(25,\lfloor25r\rfloor) = e_{\mathrm{NS}}(25,18) < 0.036 < \epsilon_*. r ≃ 0.744 , ϵ ∗ ≃ 0.042 , e NS ( 25 , ⌊ 25 r ⌋) = e NS ( 25 , 18 ) < 0.036 < ϵ ∗ .
Thus the capacity-ratio target length, rounded down, is attainable already with 25 resource uses at the error where the second-order term is exactly zero. Figure 4 compares the finite-blocklength rates with the second-order predictions. Appendix § 8 .§ 2 gives the exact certificate, retaining all higher-order and lattice effects, and an explicit Gaussian upper bound. It also certifies e N S ( 20 , 81 ; BSC ( 0.4 ) , BSC ( 0.45 ) ) < 0.008 e_{\mathrm{NS}}(20,81;\operatorname{BSC}(0.4),\operatorname{BSC}(0.45)) < 0.008 e NS ( 20 , 81 ; BSC ( 0.4 ) , BSC ( 0.45 )) < 0.008 : at 1% error this pair attains a rate 81 / 20 = 4.05 81/20 = 4.05 81/20 = 4.05 above its capacity ratio r ≃ 4.020 r \simeq4.020 r ≃ 4.020 . In the latter example the error exceeds ϵ ∗ ≃ 0.002 \epsilon_* \simeq0.002 ϵ ∗ ≃ 0.002 , so the second-order coefficient is positive, rather than zero.
Figure 4. NS finite-blocklength rates evaluated numerically from the exact formula for BSC(0.1) → \to → BSC(0.05), joined as guides to the eye, and second-order rate approximations. At ϵ ∗ ≃ 0.042 \epsilon_* \simeq0.042 ϵ ∗ ≃ 0.042 , the dashed prediction is the capacity ratio r r r itself. The circled point is the exact n = 25 n=25 n = 25 , m = 18 m=18 m = 18 certificate. Integer and higher-order effects remain visible. The Gaussian approximation is not a bound.
Shared-randomness resonance. Let E 2 ( δ ) E_2(\delta) E 2 ( δ ) transmit a two-bit packet intact with probability 1 − δ 1-\delta 1 − δ , and otherwise erase both bits. Fix the target W = BEC ( 1 / 2 ) W = \operatorname{BEC}(1/2) W = BEC ( 1/2 ) and take T = E 2 ( δ ) T = E_2(\delta) T = E 2 ( δ ) , 0 < δ < 1 / 2 0 < \delta< 1/2 0 < δ < 1/2 . These are fixed memoryless channels. One use of the resource is not equivalent to two independent BEC uses. Their information parameters are
C T = 2 ( 1 − δ ) , V T = 4 δ ( 1 − δ ) , C W = 1 2 , V W = 1 4 , r = 4 ( 1 − δ ) , ν = 1 4 δ . C_T = 2(1-\delta), \qquad V_T = 4\delta(1-\delta), \qquad C_W = \frac{1}{2}, \qquad V_W = \frac{1}{4}, \qquad r = 4(1-\delta), \qquad\nu= \frac{1}{4\delta}. C T = 2 ( 1 − δ ) , V T = 4 δ ( 1 − δ ) , C W = 2 1 , V W = 4 1 , r = 4 ( 1 − δ ) , ν = 4 δ 1 .
Proposition C.1 proves that SR, EA, and NS have the same limiting error profile throughout this family. Consequently Figure 2 (b) is a shared-randomness analogue of the threshold-error plot in Figure 2 of [6 ] . It has an interior zero at δ = 1 / 4 \delta= 1/4 δ = 1/4 , where r = 3 r = 3 r = 3 and V T = r V W = 3 / 4 V_T = rV_W = 3/4 V T = r V W = 3/4 . At the two values
δ ≃ 0.230 , δ ≃ 0.272 , \delta\simeq0.230, \qquad\delta\simeq0.272, δ ≃ 0.230 , δ ≃ 0.272 ,
the threshold is 1%: the second-order coefficient at this error is exactly zero for two distinct channels. Between these values it is positive. At δ = 1 / 4 \delta= 1/4 δ = 1/4 it is the threshold error , not the coefficient at fixed positive error, that vanishes.
The SR construction proceeds by shared random placement of the transmitted packet bits among the target positions. The receiver observes the number of surviving bits and selects a subset of their positions to match the target’s visible-bit count. At resonance, the two counts have matching means and variances, and the coupling failure probability tends to zero. This uses neither feedback nor NS-to-SR rounding. It also gives finite guarantees: at δ = 1 / 4 \delta= 1/4 δ = 1/4 , 250 packet uses simulate 750 target uses with error below 9.719 × 10 − 3 9.719 \times10^{-3} 9.719 × 1 0 − 3 . Already 16 packet uses simulate 47 target uses, just one below the capacity-ratio length 48, with error below 9.971 × 10 − 3 9.971 \times10^{-3} 9.971 × 1 0 − 3 . These statements follow from exact binomial arithmetic, not a prescribed higher-order term (Appendix § 7 .§ 1 ).
Figure 3 shows the corresponding rates as a function of blocklength for both examples. We fix the smaller 1% threshold root in each family and compare errors 1% and 0.1%. Writing b ϵ = d ϵ / C W b_{\epsilon} = d_{\epsilon}/C_W b ϵ = d ϵ / C W , the second-order rate is r + b ϵ / n r + b_{\epsilon}/\sqrt{n} r + b ϵ / n : at 1% it is the constant r r r , whereas at 0.1% the coefficients are approximately − 0.110 -0.110 − 0.110 for the SR packet example and − 0.035 -0.035 − 0.035 for the NS BEC-to-BSC example. The finite curves retain all higher-order and integer effects. They are protocol-achievable rates in the SR panel and optimal rates in the NS panel, computed from the exact formulas in Appendices § 7 .§ 1 and § 9 . In particular, cancellation of the second-order term need not remove the visible finite-blocklength deficit for the near-identity target.
Figure 3. Rates at the smaller 1% threshold roots of Figure 2 . Solid curves evaluate exact finite-blocklength formulas, giving optimal NS rates in (a) and achievable SR rates in (b). Dashed curves show r + b ϵ / n r + b_{\epsilon}/\sqrt{n} r + b ϵ / n , with b 1 % = 0 b_{1\%} = 0 b 1% = 0 . They are not finite-blocklength bounds. The two finite curves in (a) often coincide because lengths and Hamming weights are integers.
Shared randomness and related work
The NS characterization gives a converse bound for shared-randomness assistance, but the NS construction need not be implementable with shared randomness. Appendix § 7 establishes agreement of the second-order coefficients for a direction of erasure-channel conversion, including the nonidentical packet-to-bit resonance in Figure 2 (b), and for BSC self-conversion. It also proves a strict separation for the dispersion-matched BEC-to-BSC pair in panel (a). Shared randomness can therefore exhibit resonance, but (7) is not a sufficient condition in general. In particular, panel (a) is not a shared-randomness formula: the full SR threshold curve for BEC-to-BSC conversion remains open.
Related work and proof ingredients. At the noiseless endpoints, the relevant results are the finite-blocklength coding theorems of Hayashi, and Polyansky, Poor, and Verdú [7 , 8 ] , its NS interpretation due to Matthews [9 ] , and the channel simulation results of Cao et al. [3 ] . Our testing comparison uses Renes’ relative submajorization theorem [14 ] . Its Gaussian profile is the sesquinormal profile derived in [6 ] . The induced state map in the converse is due to Oufkir, Yao, and Berta [23 ] , Lemma 24. The marginal completion extends the NS simulation construction of Cao et al. [3 Proposition 18] . The additional step is to implement these ingredients uniformly over target types, charge all communication to the prescribed resource, and allow every reference law in the converse. The strong converse exponent of channel interconversion [23 ] concerns fixed rates above capacity, where success decays exponentially. It does not determine the fixed-error correction studied here.
At the noiseless endpoints, NS relaxations can already be rounded with a sub-second-order communication cost: for coding by Barman and Fawzi [31 ] , and for simulation by rejection sampling [3 , 32 ] . These results preserve the fixed-error second-order terms at the respective endpoints. They do not, however, provide a rounding of a general conversion protocol that retains a noisy resource. Such a rounding would address the corresponding obstacle for SR interconversion.
There is also a close connection with joint source–channel coding [24 , 25 , 26 ] . In both problems, concatenation through noiseless communication can be suboptimal at second order.
Channel conversion additionally requires reproducing the conditional output distribution uniformly over inputs, rather than satisfying a single decoding or distortion criterion. Source–channel constructions suggest achievable bounds. The binary-source broadcast converse of Kochman, Ordentlich, and Polyanskiy [26 ] supplies the idea of introducing an auxiliary variable for the stronger SR converse in Appendix § 7 .§ 3 . We also condition on success and estimate the probabilities of intervals of counts using Gaussian limits. A matching general characterization has not been established.
Conclusion and further questions
We characterize the second-order interconversion of finite classical channels with positive capacities and positive minimum capacity-achieving dispersions under non-signalling superchannels. The optimal coefficient is governed by Gaussian information fluctuations, with a mixture over resource dispersions and a worst-case target variance in the general case (Theorem A.1 ). When each channel has equal minimum and maximum dispersions, the characterization reduces to the sesquinormal expression for state dichotomies. The channel extension requires uniformity over target inputs and both non-signalling marginal constraints. Our explicit construction enforces these constraints at logarithmic communication cost. For additive channels, the exact finite-blocklength characterization also covers zero-dispersion cases (Appendix § 8 ).
The corresponding problem under shared randomness remains open in general. Appendix § 7 establishes both agreement with the NS coefficient and a strict separation, without determining the separated SR coefficient. Packet-to-bit erasure conversion gives an SR resonance between distinct channels: random placement and local thinning couple the numbers of available and required bits. The BEC-to-BSC separation shows why matching the total information variances at the capacity-ratio length does not give a universal SR resonance criterion. Joint source–channel coding suggests constructions that preserve resource noise, while broadcast converses impose compatibility across different noise realizations. Determining whether these approaches yield a matching characterization is an open problem. Poisson-matching constructions [33 ] offer a possible alternative to separate coding and simulation, but would additionally have to reproduce the conditional output distribution uniformly over inputs.
Entanglement assistance lies between shared randomness and NS assistance. Its coefficient agrees with both whenever their coefficients coincide, but remains undetermined for the separated BEC-to-BSC example. Extending the common-encoder converse to quantum decoders would require a separate argument. Further questions concern general nonadditive zero-dispersion channels, including intervals with V min = 0 < V max V_{\min} = 0 < V_{\max} V m i n = 0 < V m a x , and third-order refinements of the positive-dispersion expansion.
Acknowledgements
We acknowledge discussions with Marco Tomamichel and Rabsan Galib Ahmed. MB acknowledges support from the European Research Council (ERC Grant Agreement No. 948139) and the Excellence Cluster Matter and Light for Quantum Computing (ML4Q-2). This work was supported in part by a grant of access to OpenAI models through the ChatGPT for Academic Researchers program.
Channel interconversion and information parameters
All alphabets are finite. Logarithms are base two, except ln \ln ln . Write P ( A ) \mathcal{P}(\mathcal{A}) P ( A ) for probability laws on A \mathcal{A} A , TV ( P , R ) = 1 2 ∑ a ∣ P ( a ) − R ( a ) ∣ \operatorname{TV}(P,R)=\frac{1}{2}\sum_a\lvert P(a)-R(a)\rvert TV ( P , R ) = 2 1 ∑ a ∣ P ( a ) − R ( a )∣ , and [ u ] + = max ( u , 0 ) [u]_+=\max(u,0) [ u ] + = max ( u , 0 ) . The induced output law is ( P K ) ( b ) = ∑ a P ( a ) K ( b ∣ a ) (PK)(b)=\sum_a P(a)K(b\mid a) ( P K ) ( b ) = ∑ a P ( a ) K ( b ∣ a ) . When P K PK P K denotes a joint law below, this will be stated explicitly. Its value is P ( a ) K ( b ∣ a ) P(a)K(b\mid a) P ( a ) K ( b ∣ a ) . A stochastic matrix acts on column probability vectors and has column sums one. Let Φ , ϕ \Phi,\phi Φ , ϕ denote the standard normal distribution function and density.
Operational task and non-signalling constraints
An NS protocol is described by a bipartite channel N ( x , z ∣ s , y ) N(x,z\mid s,y) N ( x , z ∣ s , y ) satisfying
∑ z N ( x , z ∣ s , y ) = E ( x ∣ s ) , ∑ x N ( x , z ∣ s , y ) = D ( z ∣ y ) . (9) \sum_z N(x,z\mid s,y)=E(x\mid s),\qquad\sum_x N(x,z\mid s,y)=D(z\mid y). \tag*{(9)} z ∑ N ( x , z ∣ s , y ) = E ( x ∣ s ) , x ∑ N ( x , z ∣ s , y ) = D ( z ∣ y ) . (9)
Connecting the resource channel K K K gives the simulated channel
( Θ N [ K ] ) ( z ∣ s ) = ∑ x , y K ( y ∣ x ) N ( x , z ∣ s , y ) . (10) (\Theta_N[K])(z\mid s)=\sum_{x,y}K(y\mid x)N(x,z\mid s,y). \tag*{(10)} ( Θ N [ K ]) ( z ∣ s ) = x , y ∑ K ( y ∣ x ) N ( x , z ∣ s , y ) . (10)
The first constraint ensures normalization for every K K K . The second shows that, for every replacer R R ( y ∣ x ) = R ( y ) \mathcal{R}_R(y\mid x)=R(y) R R ( y ∣ x ) = R ( y ) ,
Θ N [ R R ] ( z ∣ s ) = ∑ y R ( y ) D ( z ∣ y ) , (11) \Theta_N[\mathcal{R}_R](z\mid s)=\sum_y R(y)D(z\mid y), \tag*{(11)} Θ N [ R R ] ( z ∣ s ) = y ∑ R ( y ) D ( z ∣ y ) , (11)
which is independent of s s s .
Conversely, suppose a nonnegative array in (10) gives a valid channel for every inserted channel and preserves every replacer. These properties imply the NS constraints. See also [5 ] . Indeed, set A s ( x , y ) = ∑ z N ( x , z ∣ s , y ) A_s(x,y)=\sum_z N(x,z\mid s,y) A s ( x , y ) = ∑ z N ( x , z ∣ s , y ) . Normalization requires ∑ x , y K ( y ∣ x ) A s ( x , y ) = 1 \sum_{x,y}K(y\mid x)A_s(x,y)=1 ∑ x , y K ( y ∣ x ) A s ( x , y ) = 1 for every K K K . Varying one column K ( ⋅ ∣ x ) K(\cdot\mid x) K ( ⋅ ∣ x ) while holding the others fixed shows that A s ( x , y ) A_s(x,y) A s ( x , y ) is independent of y y y , giving the sender marginal. For each fixed y y y , preservation of the point-mass replacer R δ y \mathcal{R}_{\delta_y} R δ y says that ∑ x N ( x , z ∣ s , y ) \sum_xN(x,z\mid s,y) ∑ x N ( x , z ∣ s , y ) is independent of s s s , giving the receiver marginal. Thus, among valid transformations of this form, preserving the entire family of replacers characterizes NS transformations. Preserving one chosen reference channel is not enough.
Let T : X → Y T:\mathcal{X}\to\mathcal{Y} T : X → Y be the resource channel and W : S → Z W:\mathcal{S}\to\mathcal{Z} W : S → Z the target. Using block alphabets in (9) , define
e N S ( n , m ; T , W ) = min N max s m TV ( Θ N [ T ⊗ n ] ( ⋅ ∣ s m ) , W ⊗ m ( ⋅ ∣ s m ) ) , (12) e_{\mathrm{NS}}(n,m;T,W)=\min_N\max_{s^m}\operatorname{TV}\left(\Theta_N[T^{\otimes n}](\cdot\mid s^m),W^{\otimes m}(\cdot\mid s^m)\right), \tag*{(12)} e NS ( n , m ; T , W ) = N min s m max TV ( Θ N [ T ⊗ n ] ( ⋅ ∣ s m ) , W ⊗ m ( ⋅ ∣ s m ) ) , (12)
m N S ∗ ( n , ϵ ; T , W ) = max { m : e N S ( n , m ; T , W ) ≤ ϵ } . (13) m^*_{\mathrm{NS}}(n,\epsilon;T,W)=\max\{m:e_{\mathrm{NS}}(n,m;T,W)\le\epsilon\}. \tag*{(13)} m NS ∗ ( n , ϵ ; T , W ) = max { m : e NS ( n , m ; T , W ) ≤ ϵ } . (13)
At each fixed pair of blocklengths the NS feasible set is a compact polytope, so the error minimum is attained. Under the hypotheses of Theorem 1.1, the length maximum is finite for large n n n . The bounds below also recover the first-order theorem. We omit T , W T,W T , W when they are fixed. Error is nondecreasing in m m m : fixing unused target input coordinates and discarding the corresponding outputs gives a protocol for any shorter target block. Equivalently, the error is the largest joint-law TV distance over all input laws P S m P_{S^m} P S m . The criterion therefore controls every conditional output distribution, not just an average over a prescribed source.
An SR protocol has N ( x , z ∣ s , y ) = ∑ ρ p ( ρ ) E ρ ( x ∣ s ) D ρ ( z ∣ y ) N(x,z\mid s,y)=\sum_{\rho}p(\rho)E_\rho(x\mid s)D_\rho(z\mid y) N ( x , z ∣ s , y ) = ∑ ρ p ( ρ ) E ρ ( x ∣ s ) D ρ ( z ∣ y ) . EA protocols use local measurements on a preshared quantum state. For A ∈ { S R , E A } A\in\{\mathrm{SR},\mathrm{EA}\} A ∈ { SR , EA } , define e A e_A e A by (12) with an infimum over the corresponding assistance class, and m A ∗ m_A^* m A ∗ by (13) . The infimum convention does not assume that an optimal unrestricted EA protocol is attained. No feedback or additional communication is allowed, and
S R ⊆ E A ⊆ N S , e N S ≤ e E A ≤ e S R . \mathrm{SR}\subseteq\mathrm{EA}\subseteq\mathrm{NS},\qquad e_{\mathrm{NS}}\le e_{\mathrm{EA}}\le e_{\mathrm{SR}}. SR ⊆ EA ⊆ NS , e NS ≤ e EA ≤ e SR .
The resource input coordinates may be correlated. Every auxiliary channel used in a proof will be implemented within the n n n resource uses.
Capacity and a single dispersion
For A ∼ P A \sim P A ∼ P and B ∼ K ( ⋅ ∣ A ) B \sim K(\cdot\mid A) B ∼ K ( ⋅ ∣ A ) define
i P , K ( a ; b ) = log K ( b ∣ a ) ( P K ) ( b ) , I ( P , K ) = E i P , K ( A ; B ) , V ( P , K ) = E Var ( i P , K ( A ; B ) ∣ A ) . i_{P,K}(a;b)=\log\frac{K(b\mid a)}{(PK)(b)},\qquad I(P,K)=\mathbb{E}i_{P,K}(A;B),\qquad V(P,K)=\mathbb{E}\operatorname{Var}(i_{P,K}(A;B)\mid A). i P , K ( a ; b ) = log ( P K ) ( b ) K ( b ∣ a ) , I ( P , K ) = E i P , K ( A ; B ) , V ( P , K ) = E Var ( i P , K ( A ; B ) ∣ A ) .
Define the capacity and the set of capacity-achieving input distributions by C K = max P I ( P , K ) C_K=\max_P I(P,K) C K = max P I ( P , K ) and Π K = { P : I ( P , K ) = C K } \Pi_K=\{P:I(P,K)=C_K\} Π K = { P : I ( P , K ) = C K } . All P ∈ Π K P\in\Pi_K P ∈ Π K induce the same output law P B ∗ ( K ) P_B^*(K) P B ∗ ( K ) , and D ( K ( ⋅ ∣ a ) ∥ P B ∗ ( K ) ) = C K D(K(\cdot\mid a)\mathbin{\|}P_B^*(K))=C_K D ( K ( ⋅ ∣ a ) ∥ P B ∗ ( K )) = C K for a a a in their support. Consequently, on Π K \Pi_K Π K the conditional variance equals the full variance, and
V ( P , K ) = ∑ a , b P ( a ) K ( b ∣ a ) ( log K ( b ∣ a ) P B ∗ ( K ) ( b ) − C K ) 2 . (14) V(P,K)=\sum_{a,b}P(a)K(b\mid a)\left(\log\frac{K(b\mid a)}{P_B^*(K)(b)}-C_K\right)^2. \tag*{(14)} V ( P , K ) = a , b ∑ P ( a ) K ( b ∣ a ) ( log P B ∗ ( K ) ( b ) K ( b ∣ a ) − C K ) 2 . (14)
This expression is affine in P P P on Π K \Pi_K Π K . In the main text we assume that it has one value V K > 0 V_K>0 V K > 0 and that C K > 0 C_K>0 C K > 0 . This assumption allows multiple capacity-achieving inputs, provided their dispersions agree. The interval-valued case is treated in Appendix § 5 .
We use BSC ( q ) \operatorname{BSC}(q) BSC ( q ) for crossover probability q q q and BEC ( δ ) \operatorname{BEC}(\delta) BEC ( δ ) for erasure probability δ \delta δ . Write
h ( x ) = − x log x − ( 1 − x ) log ( 1 − x ) , C x = 1 − h ( x ) , ℓ x = log 1 − x x , V x = x ( 1 − x ) ℓ x 2 . h(x)=-x\log x-(1-x)\log(1-x),\qquad C_x=1-h(x),\qquad\ell_x=\log\frac{1-x}{x},\qquad V_x=x(1-x)\ell_x^2. h ( x ) = − x log x − ( 1 − x ) log ( 1 − x ) , C x = 1 − h ( x ) , ℓ x = log x 1 − x , V x = x ( 1 − x ) ℓ x 2 .
For 0 < q < 1 / 2 0<q<1/2 0 < q < 1/2 and 0 < δ < 1 0<\delta<1 0 < δ < 1 ,
Table 1.
Thus these basic channels satisfy the singleton-dispersion assumption throughout the stated parameter ranges. Noiseless channels have zero dispersion and require separate endpoint results.
A word a k a^k a k has empirical law P a k ( a ) = k − 1 ∣ { i : a i = a } ∣ P_{a^k}(a)=k^{-1}|\{i:a_i=a\}| P a k ( a ) = k − 1 ∣ { i : a i = a } ∣ , called its type. We use the standard type-class estimates of [30 ] . Write P k ( A ) \mathcal{P}_k(A) P k ( A ) for the set of types, T P k T_P^k T P k for a type class, and U T P k U_{T_P^k} U T P k for its uniform law. There are at most ( k + 1 ) ∣ A ∣ (k+1)^{|A|} ( k + 1 ) ∣ A ∣ types. Every permutation-invariant law is a mixture of these uniform laws. We use the following universal output reference:
R B , k u = 1 ∣ P k ( B ) ∣ ∑ P ∈ P k ( B ) U T P k . (15) R_{B,k}^{\mathrm{u}}=\frac{1}{|\mathcal{P}_k(B)|}\sum_{P\in\mathcal{P}_k(B)}U_{T_P^k}. \tag*{(15)} R B , k u = ∣ P k ( B ) ∣ 1 P ∈ P k ( B ) ∑ U T P k . (15)
In particular R ⊗ k ≤ ∣ P k ( B ) ∣ R B , k u R^{\otimes k}\leq|\mathcal{P}_k(B)|R_{B,k}^{\mathrm{u}} R ⊗ k ≤ ∣ P k ( B ) ∣ R B , k u pointwise for every one-letter output law R R R .
Binary experiments and non-signalling interconversion
We first derive a converse from testing curves and then construct non-signalling protocols from transformations of binary experiments. These finite-blocklength statements require no dispersion assumption.
Converse: the induced dichotomy
For probability vectors p p p , q q q , define the testing curve
α y ( p , q ) = max { t ⋅ p : 0 ≤ t ≤ 1 , t ⋅ q ≤ y } , 0 ≤ y ≤ 1 , \alpha_y(p,q)=\max\{t\cdot p:0\le t\le1,\ t\cdot q\le y\},\qquad0\le y\le1, α y ( p , q ) = max { t ⋅ p : 0 ≤ t ≤ 1 , t ⋅ q ≤ y } , 0 ≤ y ≤ 1 ,
and define δ ( p , q ; p ′ , q ′ ) = min M : M q = q ′ TV ( M p , p ′ ) \delta(p,q;p',q')=\min_{M:Mq=q'}\operatorname{TV}(Mp,p') δ ( p , q ; p ′ , q ′ ) = min M : M q = q ′ TV ( M p , p ′ ) , where M M M is stochastic. The comparison theorem for binary experiments is
δ ( p , q ; p ′ , q ′ ) = sup 0 ≤ y ≤ 1 { α y ( p ′ , q ′ ) − α y ( p , q ) } . (16) \delta(p,q;p',q')=\sup_{0\le y\le1}\{\alpha_y(p',q')-\alpha_y(p,q)\}. \tag*{(16)} δ ( p , q ; p ′ , q ′ ) = 0 ≤ y ≤ 1 sup { α y ( p ′ , q ′ ) − α y ( p , q )} . (16)
This is the normalized, exact-reference form of the classical randomization criterion [13 ] . See also [14 Theorem 2 and Proposition 6] . We recall a finite-alphabet proof for completeness. Pulling tests back through M M M gives the lower bound on the left side of (16) . For the reverse bound, minimax expresses that side as max 0 ≤ f ≤ 1 { p ′ ⋅ f − max M : M q = q ′ ( M p ) ⋅ f } \max_{0\le f\le1}\{p'\cdot f-\max_{M:Mq=q'}(Mp)\cdot f\} max 0 ≤ f ≤ 1 { p ′ ⋅ f − max M : M q = q ′ ( M p ) ⋅ f } . Order the source atoms by p / q p/q p / q and the target atoms by f f f . By splitting the reference mass, a monotone transport maximizes the assigned p p p -mass simultaneously for every upper level set of f f f . Integrating over these level sets bounds the expression by the right side of (16) . Atoms with q = 0 q=0 q = 0 can be assigned to a target atom where f f f is maximal.
To pass from testing curves to Gaussian limits, we use the following elementary information-spectrum bounds. For j = log ( p / q ) j=\log(p/q) j = log ( p / q ) , h ≥ 0 h\ge0 h ≥ 0 and γ > 0 \gamma>0 γ > 0 ,
Pr p { j ≥ h } ≤ α 2 − h ( p , q ) ≤ Pr p { j ≥ h − γ } + 2 − γ . (17) \Pr_{p}\{j\ge h\}\le\alpha_{2^{-h}}(p,q)\le\Pr_{p}\{j\ge h-\gamma\}+2^{-\gamma}. \tag*{(17)} p Pr { j ≥ h } ≤ α 2 − h ( p , q ) ≤ p Pr { j ≥ h − γ } + 2 − γ . (17)
The threshold test in the left inequality has q q q -mass at most 2 − h 2^{-h} 2 − h . For the right inequality, the contribution of any feasible test on j < h − γ j<h-\gamma j < h − γ has p p p -mass at most 2 − γ 2^{-\gamma} 2 − γ .
Proposition 3.1 (One-shot converse). Let N N N convert T T T to a channel W ~ \widetilde{W} W whose worst-row error from W W W is at most ϵ \epsilon ϵ . Choose any target input law P S P_S P S and any resource output reference R Y R_Y R Y . Set
P X ( x ) = ∑ s P S ( s ) E ( x ∣ s ) , R Z ( z ) = ∑ y R Y ( y ) D ( z ∣ y ) . P_X(x)=\sum_s P_S(s)E(x\mid s),\qquad R_Z(z)=\sum_y R_Y(y)D(z\mid y). P X ( x ) = s ∑ P S ( s ) E ( x ∣ s ) , R Z ( z ) = y ∑ R Y ( y ) D ( z ∣ y ) . With joint signal laws P X Y = P X T P_{XY}=P_XT P X Y = P X T and P S Z = P S W P_{SZ}=P_SW P S Z = P S W ,
ϵ ≥ δ ( P X Y , P X ⊗ R Y ; P S Z , P S ⊗ R Z ) . (18) \epsilon\ge\delta(P_{XY},P_X\otimes R_Y;P_{SZ},P_S\otimes R_Z). \tag*{(18)} ϵ ≥ δ ( P X Y , P X ⊗ R Y ; P S Z , P S ⊗ R Z ) . (18) The statement applies unchanged to block channels.
Proof. We use the induced stochastic map of [23 Lemma 24] . On columns with P X ( x ) > 0 P_X(x)>0 P X ( x ) > 0 , put M ( s , z ) , ( x , y ) = P S ( s ) N ( x , z ∣ s , y ) / P X ( x ) M_{(s,z),(x,y)}=P_S(s)N(x,z\mid s,y)/P_X(x) M ( s , z ) , ( x , y ) = P S ( s ) N ( x , z ∣ s , y ) / P X ( x ) . The map depends on N N N and P S P_S P S , but not on R Y R_Y R Y . The first NS constraint makes M M M stochastic, and the second gives, simultaneously for every R Y R_Y R Y ,
M ( P X ⊗ R Y ) = P S ⊗ R Z , M P X Y = P S W ~ . M(P_X\otimes R_Y)=P_S\otimes R_Z,\qquad MP_{XY}=P_S\widetilde{W}. M ( P X ⊗ R Y ) = P S ⊗ R Z , M P X Y = P S W .
Columns corresponding to zero-probability inputs can be defined arbitrarily. The last joint law is within ϵ \epsilon ϵ of P S W P_SW P S W in TV.
The reference R Z R_Z R Z is induced by the converter. It cannot be fixed to a convenient product law in the converse.
Construction of non-signalling protocols
We now construct a channel protocol from a state comparison. Two additional requirements must be met: the state map must give an NS channel, and its error must be controlled uniformly over target inputs.
One reference pair is insufficient. Consider a resource with a single input and deterministic output Y = 0 Y=0 Y = 0 , with output alphabet { 0 , 1 } \{0,1\} { 0 , 1 } . Choose the reference U Y U_Y U Y , and let the target be the noiseless binary channel with uniform input U S U_S U S . The stochastic map
M ( s , z ∣ y ) = 1 2 1 { z = s ⊕ y } M(s,z\mid y)=\frac{1}{2}\mathbf{1}_{\{z=s\oplus y\}} M ( s , z ∣ y ) = 2 1 1 { z = s ⊕ y }
satisfies
M δ 0 = U S ( s ) 1 { z = s } , M U Y = U S ⊗ U Z . M\delta_0=U_S(s)\mathbf{1}_{\{z=s\}},\qquad MU_Y=U_S\otimes U_Z. M δ 0 = U S ( s ) 1 { z = s } , M U Y = U S ⊗ U Z .
Thus the two selected state dichotomies convert exactly. Nevertheless, the resource is a replacer, and every NS image of it is a replacer. Its worst-row error from the noiseless bit is at least 1 / 2 1/2 1/2 . The conditional distribution H ( z ∣ s , y ) = 2 M ( s , z ∣ y ) H(z\mid s,y)=2M(s,z\mid y) H ( z ∣ s , y ) = 2 M ( s , z ∣ y ) shows why: its receiver marginal depends on s s s . Preserving the single averaged reference U Y U_Y U Y concealed this dependence. The state map generated the label S S S jointly with Z Z Z . It did not implement a channel for an externally chosen S S S .
More generally, suppose a stochastic map M M M has ∑ z M ( s , z ∣ x , y ) = π ( s ) > 0 \sum_z M(s,z\mid x,y)=\pi(s)>0 ∑ z M ( s , z ∣ x , y ) = π ( s ) > 0 , and define
H ( x , z ∣ s , y ) = P X ( x ) M ( s , z ∣ x , y ) π ( s ) . (19) H(x,z\mid s,y)=\frac{P_X(x)M(s,z\mid x,y)}{\pi(s)}. \tag*{(19)} H ( x , z ∣ s , y ) = π ( s ) P X ( x ) M ( s , z ∣ x , y ) . (19)
It has sender marginal P X P_X P X . Its receiver marginal is independent of s s s if and only if there is one stochastic map D D D such that
M ( P X ⊗ R Y ) = π ⊗ ( D R Y ) for every R Y . (20) M(P_X\otimes R_Y)=\pi\otimes(DR_Y)\qquad\text{for every }R_Y. \tag*{(20)} M ( P X ⊗ R Y ) = π ⊗ ( D R Y ) for every R Y . (20)
Indeed, taking R Y = δ y R_Y=\delta_y R Y = δ y tests the receiver marginal at each y y y . The converse follows by linearity. A single reference-preservation identity is strictly weaker. The completion below obtains this full marginal identity from a pointwise domination bound.
Controlling average error is a separate issue. For any fixed input law,
TV ( P S W ~ , P S W ) = ∑ s P S ( s ) TV ( W ~ ( ⋅ ∣ s ) , W ( ⋅ ∣ s ) ) . \operatorname{TV}(P_S\widetilde{W},P_SW)=\sum_s P_S(s)\operatorname{TV}\bigl(\widetilde{W}(\cdot\mid s),W(\cdot\mid s)\bigr). TV ( P S W , P S W ) = s ∑ P S ( s ) TV ( W ( ⋅ ∣ s ) , W ( ⋅ ∣ s ) ) .
For example, the constant-zero channel is within η \eta η of the noiseless bit under the prior P S ( 1 ) = η P_S(1)=\eta P S ( 1 ) = η , but its worst-row error is one. We will use type-class symmetry and a message identifying the input type to obtain a uniform bound without multiplying the error by the number of inputs.
Completing the receiver marginal. The following lemma extends the diagonal/off-diagonal completion underlying the NS simulation linear program [3 Proposition 18] . Here the construction retains the noisy resource while enforcing both non-signalling marginals.
Lemma 3.2 (Completion). Suppose H ( x , z ∣ s , y ) ≥ 0 H(x,z\mid s,y)\geq0 H ( x , z ∣ s , y ) ≥ 0 has sender marginal ∑ z H ( x , z ∣ s , y ) = P X ( x ) \sum_z H(x,z\mid s,y)=P_X(x) ∑ z H ( x , z ∣ s , y ) = P X ( x ) . Let B s ( z ∣ y ) = ∑ x H ( x , z ∣ s , y ) B_s(z\mid y)=\sum_x H(x,z\mid s,y) B s ( z ∣ y ) = ∑ x H ( x , z ∣ s , y ) and suppose B s ( z ∣ y ) ≤ c R Z ( z ) B_s(z\mid y)\leq cR_Z(z) B s ( z ∣ y ) ≤ c R Z ( z ) for distributions P X , R Z P_X,R_Z P X , R Z and an integer c ≥ 2 c\geq2 c ≥ 2 . Then T ⊗ id [ c ] T\otimes\operatorname{id}_{[c]} T ⊗ id [ c ] can simulate the channel ∑ x , y T ( y ∣ x ) H ( x , z ∣ s , y ) \sum_{x,y}T(y\mid x)H(x,z\mid s,y) ∑ x , y T ( y ∣ x ) H ( x , z ∣ s , y ) with NS assistance.
Proof. For auxiliary input i i i and output j j j in [ c ] [c] [ c ] , define
N ( x , i , z ∣ s , y , j ) = { H ( x , z ∣ s , y ) / c , i = j , P X ( x ) [ c R Z ( z ) − B s ( z ∣ y ) ] c ( c − 1 ) , i ≠ j . (21) N(x,i,z\mid s,y,j)=
\begin{cases}
H(x,z\mid s,y)/c, & i=j,\\
\dfrac{P_X(x)[cR_Z(z)-B_s(z\mid y)]}{c(c-1)}, & i\ne j.
\end{cases} \tag*{(21)} N ( x , i , z ∣ s , y , j ) = ⎩ ⎨ ⎧ H ( x , z ∣ s , y ) / c , c ( c − 1 ) P X ( x ) [ c R Z ( z ) − B s ( z ∣ y )] , i = j , i = j . (21)
The domination assumption makes every entry nonnegative. Since ∑ z B s ( z ∣ y ) = 1 \sum_z B_s(z\mid y)=1 ∑ z B s ( z ∣ y ) = 1 , summing over z z z gives P X ( x ) / c P_X(x)/c P X ( x ) / c on both diagonal and off-diagonal branches. For the other marginal, sum over both sender outputs x , i x,i x , i :
∑ x , i N ( x , i , z ∣ s , y , j ) = B s ( z ∣ y ) c + c R Z ( z ) − B s ( z ∣ y ) c = R Z ( z ) . \sum_{x,i}N(x,i,z\mid s,y,j)=\frac{B_s(z\mid y)}{c}+\frac{cR_Z(z)-B_s(z\mid y)}{c}=R_Z(z). x , i ∑ N ( x , i , z ∣ s , y , j ) = c B s ( z ∣ y ) + c c R Z ( z ) − B s ( z ∣ y ) = R Z ( z ) .
Both identities hold on the entire enlarged input alphabet, including mismatched auxiliary symbols. Hence N N N is NS. Connecting the identity channel leaves only the c c c diagonal terms, whose sum gives exactly the desired channel.
The diagonal entries retain the statistical transformation. The off-diagonal entries correct its marginals without affecting its action on the ideal auxiliary channel. Defining only the diagonal entries would not suffice: an NS box must be valid for all of its inputs before it is connected to a particular channel. This construction need not define an SR protocol. The auxiliary channel will be implemented using the prescribed resource channel.
Obtaining the pointwise bound from a state converter. Fix a target input type τ \tau τ of length m m m and a permutation-invariant resource input law P X k P_{X^k} P X k . Put U τ = U τ T m U_\tau=U_{\tau}^{T^m} U τ = U τ T m and consider the dichotomies
( P X k T ⊗ k , P X k ⊗ R Y , k u ) , ( U τ W ⊗ m , U τ ⊗ ( τ W ) ⊗ m ) . (22) \begin{aligned}
(P_{X^k}T^{\otimes k},\ P_{X^k}\otimes R^u_{Y,k}),\\
(U_\tau W^{\otimes m},\ U_\tau\otimes(\tau W)^{\otimes m}). \tag*{(22)}
\end{aligned} ( P X k T ⊗ k , P X k ⊗ R Y , k u ) , ( U τ W ⊗ m , U τ ⊗ ( τ W ) ⊗ m ) . (22)
Here the first member of each pair denotes its joint input–output law. Choose an optimal stochastic map M M M between these experiments. Its target alphabet is T τ m × Z m T_\tau^m\times Z^m T τ m × Z m on every source column, including zero-probability columns. Average M M M independently over resource and target coordinate permutations, acting simultaneously on the input and output word of each channel. The signal and reference laws are invariant under these permutations. Convexity of TV therefore preserves the error bound, and the reference is still mapped exactly. The two averages serve different purposes.
Write x = x k x=x^k x = x k , y = y k y=y^k y = y k , s = s m s=s^m s = s m , z = z m z=z^m z = z m temporarily. For each fixed ( x , y ) (x,y) ( x , y ) , transitivity on the target type class makes ∑ z M ( s , z ) , ( x , y ) \sum_z M_{(s,z),(x,y)} ∑ z M ( s , z ) , ( x , y ) constant in s s s on T τ m T_\tau^m T τ m . Stochasticity therefore implies ∑ z M ( s , z ) , ( x , y ) = U τ ( s ) \sum_z M_{(s,z),(x,y)}=U_\tau(s) ∑ z M ( s , z ) , ( x , y ) = U τ ( s ) . Consequently
H ( x , z ∣ s , y ) = P X k ( x ) M ( s , z ) , ( x , y ) U τ ( s ) H(x,z\mid s,y)=\frac{P_{X^k}(x)M_{(s,z),(x,y)}}{U_\tau(s)} H ( x , z ∣ s , y ) = U τ ( s ) P X k ( x ) M ( s , z ) , ( x , y )
has sender marginal P X k P_{X^k} P X k . Resource permutation invariance makes B s ( z ∣ y ) B_s(z\mid y) B s ( z ∣ y ) constant on each resource output type class. Let its value on the j j j th class be B s ( j ) ( z ) B_s^{(j)}(z) B s ( j ) ( z ) and let J k = ∣ P k ( Y ) ∣ J_k=|P_k(Y)| J k = ∣ P k ( Y ) ∣ . The universal law R Y , k u R^u_{Y,k} R Y , k u assigns each output type class weight 1 / J k 1/J_k 1/ J k . Exact reference preservation consequently yields, separately for every s s s ,
( τ W ) ⊗ m ( z ) = 1 J k ∑ j = 1 J k B s ( j ) ( z ) , B s ( z ∣ y ) ≤ J k ( τ W ) ⊗ m ( z ) . (23) (\tau W)^{\otimes m}(z)=\frac{1}{J_k}\sum_{j=1}^{J_k}B_s^{(j)}(z),\qquad B_s(z\mid y)\le J_k(\tau W)^{\otimes m}(z). \tag*{(23)} ( τ W ) ⊗ m ( z ) = J k 1 j = 1 ∑ J k B s ( j ) ( z ) , B s ( z ∣ y ) ≤ J k ( τ W ) ⊗ m ( z ) . (23)
Lemma 3.2 applies with c k = max ( 2 , J k ) c_k=\max(2,J_k) c k = max ( 2 , J k ) . The same target symmetry makes all row errors equal, so joint-law TV is precisely the worst-row error on this class. The polynomial factor J k J_k J k appears in the auxiliary alphabet, not as a multiplier of the approximation error. This gives a state conversion that can be completed to a channel protocol while preserving its error bound.
One protocol for all target inputs. The resource law may depend on τ \tau τ . To combine the protocols for different types while preserving the NS constraints, send the type index through an additional identity channel of size h m = ∣ P m ( S ) ∣ h_m=|\mathcal{P}_m(S)| h m = ∣ P m ( S ) ∣ . Simply choosing the box indexed by τ ( s ) \tau(s) τ ( s ) would not work: its receiver marginal could then be R τ ( s ) R_{\tau(s)} R τ ( s ) , which depends on the sender’s input. The receiver marginal must instead be indexed by the received header symbol, even when that symbol is incorrect. If N τ N_\tau N τ has marginals P τ ( x ) / c k P_\tau(x)/c_k P τ ( x ) / c k and R τ ( z ) R_\tau(z) R τ ( z ) , define
N ^ ( x , i , a , z ∣ s , y , j , b ) = 1 { a = τ ( s ) } { N τ ( s ) ( x , i , z ∣ s , y , j ) , b = τ ( s ) , P τ ( s ) ( x ) R b ( z ) / c k , b ≠ τ ( s ) . (24) \widehat{N}(x,i,a,z\mid s,y,j,b)=\mathbf{1}_{\{a=\tau(s)\}}
\begin{cases}
N_{\tau(s)}(x,i,z\mid s,y,j), & b=\tau(s),\\
P_{\tau(s)}(x)R_b(z)/c_k, & b\ne\tau(s).
\end{cases} \tag*{(24)} N ( x , i , a , z ∣ s , y , j , b ) = 1 { a = τ ( s )} { N τ ( s ) ( x , i , z ∣ s , y , j ) , P τ ( s ) ( x ) R b ( z ) / c k , b = τ ( s ) , b = τ ( s ) . (24)
Its sender marginal is 1 { a = τ ( s ) } P τ ( s ) ( x ) / c k \mathbf{1}_{\{a=\tau(s)\}}P_{\tau(s)}(x)/c_k 1 { a = τ ( s )} P τ ( s ) ( x ) / c k , and its receiver marginal is R b ( z ) R_b(z) R b ( z ) . Thus the NS constraints hold even on mismatched header symbols. The combined auxiliary alphabet has size
L k , m = c k h m ≤ 2 ( k + 1 ) ∣ Y ∣ ( m + 1 ) ∣ S ∣ . (25) L_{k,m}=c_k h_m \le2(k+1)^{|\mathcal{Y}|}(m+1)^{|\mathcal{S}|}. \tag*{(25)} L k , m = c k h m ≤ 2 ( k + 1 ) ∣ Y ∣ ( m + 1 ) ∣ S ∣ . (25)
The combined protocol has error equal to the largest typewise error, without a factor equal to the number of types.
Accounting for auxiliary communication
Proposition 3.3 (One-shot achievability with auxiliary cost). If T ⊗ ℓ T^{\otimes\ell} T ⊗ ℓ has a code for L k , m L_{k,m} L k , m messages with maximal error η ℓ \eta_\ell η ℓ , then
e N S ( k + ℓ , m ) ≤ η ℓ + max τ ∈ P m ( S ) inf P X k p e r m u t a t i o n i n v a r i a n t δ ( the two pairs in (22) ) . (26) e_{\mathrm{NS}}(k+\ell,m) \le\eta_\ell+\max_{\tau\in\mathcal{P}_m(\mathcal{S})}\inf_{P_{X^k}\ \mathrm{permutation\ invariant}}\delta(\text{the two pairs in (22)}). \tag*{(26)} e NS ( k + ℓ , m ) ≤ η ℓ + τ ∈ P m ( S ) max P X k permutation invariant inf δ ( the two pairs in (22) ) . (26) If C T > 0 C_T>0 C T > 0 and m = O ( k ) m=O(k) m = O ( k ) , one can take ℓ = O ( log k ) \ell=O(\log k) ℓ = O ( log k ) and η ℓ ≤ k − 2 \eta_\ell\le k^{-2} η ℓ ≤ k − 2 .
Proof. Combine the two auxiliary inputs and outputs into single symbols i , j ∈ [ L k , m ] i,j\in[L_{k,m}] i , j ∈ [ L k , m ] . Compose these ports of N ^ \widehat{N} N with the encoder E C ( v ∣ i ) E_C(v\mid i) E C ( v ∣ i ) and decoder D C ( j ∣ w ) D_C(j\mid w) D C ( j ∣ w ) of the ordinary channel code:
N ‾ ( x , v , z ∣ s , y , w ) = ∑ i , j E C ( v ∣ i ) D C ( j ∣ w ) N ^ ( x , i , z ∣ s , y , j ) . \overline{N}(x,v,z\mid s,y,w)=\sum_{i,j}E_C(v\mid i)D_C(j\mid w)\widehat{N}(x,i,z\mid s,y,j). N ( x , v , z ∣ s , y , w ) = i , j ∑ E C ( v ∣ i ) D C ( j ∣ w ) N ( x , i , z ∣ s , y , j ) .
Summing the composed conditional distribution over either party’s outputs verifies that both NS marginal constraints are preserved. For any NS channel and any two resource channels on the same alphabets,
max s TV ( Θ N [ K ] ( ⋅ ∣ s ) , Θ N [ K ′ ] ( ⋅ ∣ s ) ) ≤ max x TV ( K ( ⋅ ∣ x ) , K ′ ( ⋅ ∣ x ) ) . (27) \max_s\operatorname{TV}\bigl(\Theta_N[K](\cdot\mid s),\Theta_N[K'](\cdot\mid s)\bigr)\le\max_x\operatorname{TV}\bigl(K(\cdot\mid x),K'(\cdot\mid x)\bigr). \tag*{(27)} s max TV ( Θ N [ K ] ( ⋅ ∣ s ) , Θ N [ K ′ ] ( ⋅ ∣ s ) ) ≤ x max TV ( K ( ⋅ ∣ x ) , K ′ ( ⋅ ∣ x ) ) . (27)
because the triangle inequality followed by the sender marginal bounds the left side by max s ∑ x E ( x ∣ s ) TV ( K ( ⋅ ∣ x ) , K ′ ( ⋅ ∣ x ) ) \max_s\sum_x E(x\mid s)\operatorname{TV}(K(\cdot\mid x),K'(\cdot\mid x)) max s ∑ x E ( x ∣ s ) TV ( K ( ⋅ ∣ x ) , K ′ ( ⋅ ∣ x )) . Replacing the auxiliary identity channel by the code therefore adds at most η ℓ \eta_\ell η ℓ to the error.
Finally, ordinary random coding at any fixed rate below C T C_T C T has a strictly positive error exponent [8 ] . Expurgating half the messages gives maximal error at most 2 1 − c ℓ 2^{1-c\ell} 2 1 − c ℓ for a fixed c > 0 c>0 c > 0 . By (25), 2 L k , m 2L_{k,m} 2 L k , m messages and error at most k − 2 k^{-2} k − 2 can both be achieved with ℓ = A log k \ell=A\log k ℓ = A log k uses for a sufficiently large constant A A A .
Second-order characterization
We prove Theorem 1.1 by establishing matching converse and achievability bounds. Let r = C T / C W r=C_T/C_W r = C T / C W and d n = ( m C W − n C T ) / n d_n=(mC_W-nC_T)/\sqrt{n} d n = ( m C W − n C T ) / n .
Proposition 4.1 (Quantitative Gaussian comparison). For every fixed Λ < ∞ \Lambda<\infty Λ < ∞ , uniformly over integer m m m with ∣ d n ∣ ≤ Λ |d_n|\le\Lambda ∣ d n ∣ ≤ Λ ,
∣ e N S ( n , m ) − E ( d n ) ∣ = O ( log n n ) , (28) \left|e_{\mathrm{NS}}(n,m)-\mathcal{E}(d_n)\right|=O\left(\frac{\log n}{\sqrt{n}}\right), \tag*{(28)} ∣ e NS ( n , m ) − E ( d n ) ∣ = O ( n log n ) , (28) where E \mathcal{E} E is given by (4).
The uniform estimates needed below are proved in Appendix § 6 . In the singleton-dispersion case, they give the following bounds at testing budget 2 − k C K − ξ k 2^{-kC_K-\xi\sqrt{k}} 2 − k C K − ξ k :
Every permutation-invariant resource input has testing probability at most 1 − Φ ( ξ / V K ) + O ( log k / k ) 1-\Phi(\xi/\sqrt{V_K})+O(\log k/\sqrt{k}) 1 − Φ ( ξ / V K ) + O ( log k / k ) . An iid capacity-achieving input attains this expression to the same precision.
For every input type, the testing probability against its canonical product output reference is at most the same expression.
For a rounded capacity-achieving type, the testing probability against every output reference is at least the same expression.
All remainders are uniform in the threshold, input types, and references to which they apply. The second statement also applies to types with a capacity deficit. It is an upper bound. It does not assert that all types have the same Gaussian limit.
Converse
Take any NS protocol with error ϵ n \epsilon_n ϵ n . Round a capacity-achieving input of W W W to an m m m -type τ m \tau_m τ m and restrict the target to this class. Average the protocol over resource and target coordinate permutations. The averaged channel is still NS. Memorylessness and convexity of TV ensure that its error does not increase. Under uniform target input U τ m U_{\tau_m} U τ m , the induced resource input P X n P_{X^n} P X n is permutation-invariant, but need not be a product law.
Apply Proposition 3.1 using R Y , n u R^u_{Y,n} R Y , n u . At h = n C T + ξ n ≥ 0 h=nC_T+\xi\sqrt{n}\geq0 h = n C T + ξ n ≥ 0 , Lemmas B.2 and B.3 give
α 2 − h ( resource pair ) ≤ 1 − Φ ( ξ V T ) + O ( log n n ) , \alpha_{2-h}(\text{resource pair})\leq1-\Phi\left(\frac{\xi}{\sqrt{V_T}}\right)+O\left(\frac{\log n}{\sqrt{n}}\right), α 2 − h ( resource pair ) ≤ 1 − Φ ( V T ξ ) + O ( n log n ) ,
α 2 − h ( target pair ) ≥ 1 − Φ ( ξ − d n ( m / n ) V W ) − O ( log n n ) . \alpha_{2-h}(\text{target pair})\geq1-\Phi\left(\frac{\xi-d_n}{\sqrt{(m/n)V_W}}\right)-O\left(\frac{\log n}{\sqrt{n}}\right). α 2 − h ( target pair ) ≥ 1 − Φ ( ( m / n ) V W ξ − d n ) − O ( n log n ) .
The second bound is valid for the protocol’s induced target reference. Since m / n = r + O ( n − 1 / 2 ) m/n=r+O(n^{-1/2}) m / n = r + O ( n − 1/2 ) , the change from ( m / n ) V W (m/n)V_W ( m / n ) V W to r V W rV_W r V W costs O ( n − 1 / 2 ) O(n^{-1/2}) O ( n − 1/2 ) uniformly in ξ \xi ξ . This follows by differentiating the normal CDF with respect to its positive variance. Subtracting the two bounds and taking the supremum proves
ϵ n ≥ E ( d n ) − O ( log n n ) . \epsilon_n\geq\mathcal{E}(d_n)-O\left(\frac{\log n}{\sqrt{n}}\right). ϵ n ≥ E ( d n ) − O ( n log n ) .
The restriction ξ ≥ − C T n \xi\geq-C_T\sqrt{n} ξ ≥ − C T n excludes only an exponentially small Gaussian tail. The bounds are uniform in the protocol. Taking the infimum over protocols therefore proves the converse in (28) .
Achievability
Reserve ℓ = ⌈ A log n ⌉ \ell=\lceil A\log n\rceil ℓ = ⌈ A log n ⌉ of the resource uses for the auxiliary messages, with A A A large enough for Proposition 3.3 , and put k = n − ℓ k=n-\ell k = n − ℓ . The code error is O ( n − 2 ) O(n^{-2}) O ( n − 2 ) . For each target type, use an iid capacity-achieving resource input in (22) . Write
d k = m C W − k C T k = d n + O ( log n n ) , m k = r + O ( n − 1 / 2 ) . d_k=\frac{mC_W-kC_T}{\sqrt{k}}=d_n+O\left(\frac{\log n}{\sqrt{n}}\right),\qquad\frac{m}{k}=r+O(n^{-1/2}). d k = k m C W − k C T = d n + O ( n log n ) , k m = r + O ( n − 1/2 ) .
At h = k C T + ξ k ≥ 0 h=kC_T+\xi\sqrt{k}\geq0 h = k C T + ξ k ≥ 0 , the first two uniform estimates give
α 2 − h ( resource pair ) ≥ 1 − Φ ( ξ V T ) − O ( log n n ) , \alpha_{2-h}(\text{resource pair})\geq1-\Phi\left(\frac{\xi}{\sqrt{V_T}}\right)-O\left(\frac{\log n}{\sqrt{n}}\right), α 2 − h ( resource pair ) ≥ 1 − Φ ( V T ξ ) − O ( n log n ) ,
α 2 − h ( target pair ) ≤ 1 − Φ ( ξ − d k ( m / k ) V W ) + O ( log n n ) . \alpha_{2-h}(\text{target pair})\leq1-\Phi\left(\frac{\xi-d_k}{\sqrt{(m/k)V_W}}\right)+O\left(\frac{\log n}{\sqrt{n}}\right). α 2 − h ( target pair ) ≤ 1 − Φ ( ( m / k ) V W ξ − d k ) + O ( n log n ) .
Normal CDFs are uniformly Lipschitz in their location and in their variance on compact positive variance intervals. The last expression may therefore be replaced by 1 − Φ ( ( ξ − d n ) / r V W ) 1-\Phi\left((\xi-d_n)/\sqrt{rV_W}\right) 1 − Φ ( ( ξ − d n ) / r V W ) at the stated precision. Equation (16) bounds each type’s deficiency by E ( d n ) + O ( log n / n ) \mathcal{E}(d_n)+O(\log n/\sqrt{n}) E ( d n ) + O ( log n / n ) . The testing budget zero causes no extra term: both signal laws are absolutely continuous with respect to their canonical references. The remainder is uniform in the target type, so Proposition 3.3 proves achievability. This proves the achievability bound in Proposition 4.1 .
Inversion and resonance
The function E \mathcal{E} E is continuous and nondecreasing, with limits zero and one at the two ends of the real line. For d d d in a fixed compact interval and E ( d ) \mathcal{E}(d) E ( d ) bounded below by a positive constant, every maximizing threshold in (4) lies in one bounded interval. On that interval the derivative
1 r V W ϕ ( ξ − d r V W ) \frac{1}{\sqrt{rV_W}}\phi\left(\frac{\xi-d}{\sqrt{rV_W}}\right) r V W 1 ϕ ( r V W ξ − d )
has a positive lower bound for d d d in a compact interval. Evaluating the objective at a maximizing threshold for the smaller displacement therefore gives E ( d 2 ) − E ( d 1 ) ≥ c ( d 2 − d 1 ) \mathcal{E}(d_2)-\mathcal{E}(d_1)\ge c(d_2-d_1) E ( d 2 ) − E ( d 1 ) ≥ c ( d 2 − d 1 ) locally at every positive error level. Hence E ( d ϵ ) = ϵ \mathcal{E}(d_\epsilon)=\epsilon E ( d ϵ ) = ϵ has a unique solution, with a locally Lipschitz inverse.
The inequality E ( d ) ≤ ϵ \mathcal{E}(d)\le\epsilon E ( d ) ≤ ϵ is equivalent, after putting η = Φ ( ξ / V T ) \eta=\Phi(\xi/\sqrt{V_T}) η = Φ ( ξ / V T ) , to
d ≤ V T Φ − 1 ( η ) − r V W Φ − 1 ( η − ϵ ) for every ϵ < η < 1. d\le\sqrt{V_T}\Phi^{-1}(\eta)-\sqrt{rV_W}\Phi^{-1}(\eta-\epsilon)\quad\text{for every }\epsilon<\eta<1. d ≤ V T Φ − 1 ( η ) − r V W Φ − 1 ( η − ϵ ) for every ϵ < η < 1.
Taking the infimum over η \eta η gives (2) . Let M n = r n + ( d ϵ / C W ) n M_n=rn+(d_\epsilon/C_W)\sqrt{n} M n = r n + ( d ϵ / C W ) n . For a sufficiently large fixed H H H , (28) and the positive local slope imply
ϵ N S ( n , ⌊ M n − H log n ⌋ ) < ϵ < ϵ N S ( n , ⌊ M n + H log n ⌋ ) . \epsilon_{\mathrm{NS}}(n,\lfloor M_n-H\log n\rfloor)<\epsilon<\epsilon_{\mathrm{NS}}(n,\lfloor M_n+H\log n\rfloor). ϵ NS ( n , ⌊ M n − H log n ⌋) < ϵ < ϵ NS ( n , ⌊ M n + H log n ⌋) .
Monotonicity in target length proves (1) . This argument bounds the remainder. It does not identify a third-order logarithmic coefficient.
For comparison with the state-dichotomy literature, define
S ν ( t ) = sup x { Φ ( x ) − Φ ( ( x − t ) / ν ) } , ν = r V W V T . S_\nu(t)=\sup_{x}\{\Phi(x)-\Phi((x-t)/\sqrt{\nu})\},\qquad\nu=\frac{rV_W}{V_T}. S ν ( t ) = x sup { Φ ( x ) − Φ (( x − t ) / ν )} , ν = V T r V W .
Then E ( d ) = S ν ( d / V T ) \mathcal{E}(d)=S_\nu(d/\sqrt{V_T}) E ( d ) = S ν ( d / V T ) and d ϵ = V T S ν − 1 ( ϵ ) d_\epsilon=\sqrt{V_T}S_\nu^{-1}(\epsilon) d ϵ = V T S ν − 1 ( ϵ ) : this is the sesquinormal form of the result [6 ] . When ν = 1 \nu=1 ν = 1 , the maximizing threshold is ξ = d / 2 \xi=d/2 ξ = d /2 for d > 0 d>0 d > 0 , and the supremum is zero for d ≤ 0 d\le0 d ≤ 0 . This proves (8) . Moreover,
ϵ N S ( n , ⌊ r n ⌋ ) = O ( log n / n ) under xref‘(7)‘ . \epsilon_{\mathrm{NS}}(n,\lfloor rn\rfloor)=O(\log n/\sqrt{n})\quad\text{under {xref}`(7)`}. ϵ NS ( n , ⌊ r n ⌋) = O ( log n / n ) under xref ‘(7)‘ .
This last estimate does not assert exact conversion at finite blocklength.
Nonunique capacity-achieving dispersions
We now allow different capacity-achieving dispersions, while retaining positive capacities and positive minimum dispersions. Thus the equality V min = V max V_{\min}=V_{\max} V m i n = V m a x is no longer assumed. Since (14) is affine on the compact convex set of capacity-achieving inputs, its image is the interval
V K = [ V min ( K ) , V max ( K ) ] . \mathcal{V}_K=[V_{\min}(K),V_{\max}(K)]. V K = [ V m i n ( K ) , V m a x ( K )] .
For a probability measure λ \lambda λ on V T \mathcal{V}_T V T , set F λ ( ξ ) = ∫ Φ ( ξ / v ) λ ( d v ) F_\lambda(\xi)=\int\Phi(\xi/\sqrt{v})\lambda(dv) F λ ( ξ ) = ∫ Φ ( ξ / v ) λ ( d v ) and define
D ( d , w ) = min λ ∈ P ( V T ) sup ξ ∈ R { F λ ( ξ ) − Φ ( ξ − d r w ) } , E g e n ( d ) = max w ∈ V W D ( d , w ) . (29) D(d,w)=\min_{\lambda\in\mathcal{P}(\mathcal{V}_T)}\sup_{\xi\in\mathbb{R}}\left\{F_\lambda(\xi)-\Phi\left(\frac{\xi-d}{\sqrt{rw}}\right)\right\},\qquad\mathcal{E}_{\mathrm{gen}}(d)=\max_{w\in\mathcal{V}_W}D(d,w). \tag*{(29)} D ( d , w ) = λ ∈ P ( V T ) min ξ ∈ R sup { F λ ( ξ ) − Φ ( r w ξ − d ) } , E gen ( d ) = w ∈ V W max D ( d , w ) . (29)
Here probability measures on the compact interval are Borel measures.
Theorem A.1 (General positive-dispersion formula). If C T , C W , V min ( T ) , V min ( W ) > 0 C_T,C_W,V_{\min}(T),V_{\min}(W)>0 C T , C W , V m i n ( T ) , V m i n ( W ) > 0 , then, uniformly for bounded d n = ( m C W − n C T ) / n d_n=(mC_W-nC_T)/\sqrt{n} d n = ( m C W − n C T ) / n ,
ϵ N S ( n , m ) = E g e n ( d n ) + O ( log n / n ) . \epsilon_{\mathrm{NS}}(n,m)=\mathcal{E}_{\mathrm{gen}}(d_n)+O(\log n/\sqrt{n}). ϵ NS ( n , m ) = E gen ( d n ) + O ( log n / n ) . For every 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 there is a unique d ϵ d_\epsilon d ϵ with E g e n ( d ϵ ) = ϵ \mathcal{E}_{\mathrm{gen}}(d_\epsilon)=\epsilon E gen ( d ϵ ) = ϵ , and
m N S ∗ ( n , ϵ ) = r n + d ϵ C W n + O ( log n ) . m_{\mathrm{NS}}^*(n,\epsilon)=rn+\frac{d_\epsilon}{C_W}\sqrt{n}+O(\log n). m NS ∗ ( n , ϵ ) = r n + C W d ϵ n + O ( log n ) .
Proof. We follow the proof in Section 4, now allowing the variance choices to depend on the target type. For achievability, associate each target type τ \tau τ with a closest capacity-achieving input Q τ Q_\tau Q τ and its variance w τ w_\tau w τ . Choose a minimizing λ τ \lambda_\tau λ τ in D ( d n , w τ ) D(d_n,w_\tau) D ( d n , w τ ) . Lemma B.2 realizes it by a mixture of iid capacity-achieving inputs. For a given target type, the same mixture works at every testing threshold. Lemma B.1 bounds the target testing curve using w τ w_\tau w τ . Thus its deficiency is at most D ( d n , w τ ) + O ( log n / n ) D(d_n,w_\tau)+O(\log n/\sqrt{n}) D ( d n , w τ ) + O ( log n / n ) . The type header permits these choices to depend on τ \tau τ . The largest type error is therefore at most E g e n ( d n ) \mathcal{E}_{\mathrm{gen}}(d_n) E gen ( d n ) plus the same remainder.
For the converse, fix w ∈ V W w\in\mathcal{V}_{W} w ∈ V W , round a capacity-achieving input with variance w w w to a target type, and average the protocol as before. Lemma B.2 assigns its correlated resource input one measure λ n \lambda_n λ n independent of the testing threshold. Lemma B.3 bounds the target curve for every induced reference. Consequently its error is at least D ( d n , w ) − O ( log n / n ) D(d_n,w)-O(\log n/\sqrt{n}) D ( d n , w ) − O ( log n / n ) . Taking the maximum over w w w gives the converse bound. All errors are uniform over the compact variance intervals. No exchange of minimum and maximum is used.
It remains to justify inversion of the limiting error profile. For bounded d d d , the difference in braces in (29) tends uniformly to zero as ∣ ξ ∣ → ∞ |\xi|\to\infty ∣ ξ ∣ → ∞ , over all w , λ w,\lambda w , λ . On compact ξ \xi ξ intervals it is continuous in d d d , w w w and in λ \lambda λ for weak convergence. Compactness of probability measures on V T \mathcal{V}_{T} V T therefore gives attainment of the minimum and continuity of D D D and E g e n \mathcal{E}_{\mathrm{gen}} E gen . As d → − ∞ d\to-\infty d → − ∞ , splitting at ξ = d / 2 \xi=d/2 ξ = d /2 bounds the supremum by vanishing Gaussian tails. As d → + ∞ d\to+\infty d → + ∞ , evaluation at ξ = d / 2 \xi=d/2 ξ = d /2 makes the difference tend uniformly to one.
To establish the local inverse bound where E g e n ≥ ϵ 0 > 0 \mathcal{E}_{\mathrm{gen}}\ge\epsilon_0>0 E gen ≥ ϵ 0 > 0 , take a maximizing w ∗ w_* w ∗ at d 1 d_1 d 1 . For every λ \lambda λ , its threshold supremum is at least ϵ 0 \epsilon_0 ϵ 0 and is attained in one common compact interval. Increasing d 1 d_1 d 1 to d 2 d_2 d 2 raises the objective at that maximizing threshold by at least c ( d 2 − d 1 ) c(d_2-d_1) c ( d 2 − d 1 ) , with c > 0 c>0 c > 0 uniform in w ∗ , λ w_*,\lambda w ∗ , λ . Minimize over λ \lambda λ and use the same w ∗ w_* w ∗ at d 2 d_2 d 2 . This proves the local inverse bound. The integer bracketing argument of Section 4 then gives the length expansion.
The optimization order max w min λ sup ξ \max_w\min_\lambda\sup_\xi max w min λ sup ξ has an operational meaning: the target type is known to the encoder and communicated to the decoder, whereas the resource input must be chosen before the testing threshold. The optimization order retains this dependence.
Uniform Gaussian estimates
This appendix proves the uniform estimates used in the converse and achievability arguments. Let K : A → B K:\mathcal{A}\to\mathcal{B} K : A → B be a finite channel with C K > 0 C_K>0 C K > 0 and V min ( K ) > 0 V_{\min}(K)>0 V m i n ( K ) > 0 . Constants below may depend on K K K , but not on input types, testing thresholds, or reference distributions. Products such as P A k K ⊗ k P_{A^k}K^{\otimes k} P A k K ⊗ k in this appendix denote joint input–output laws, not output marginals. For a k k k -type P P P and any a k ∈ T P k a^k\in T_P^k a k ∈ T P k , define
J P , k : = ∑ i = 1 k log K ( B i ∣ a i ) ( P K ) ( B i ) , B k ∼ K ⊗ k ( ⋅ ∣ a k ) . (30) J_{P,k}:=\sum_{i=1}^{k}\log\frac{K(B_i|a_i)}{(PK)(B_i)},\qquad B^k\sim K^{\otimes k}(\cdot|a^k). \tag*{(30)} J P , k := i = 1 ∑ k log ( P K ) ( B i ) K ( B i ∣ a i ) , B k ∼ K ⊗ k ( ⋅ ∣ a k ) . (30)
Its distribution depends only on P P P , not on the chosen word. Its mean and variance are k I ( P , K ) kI(P,K) k I ( P , K ) and k V ( P , K ) kV(P,K) k V ( P , K ) , respectively.
We first establish the moment and regularity bounds needed below. The second and third absolute moments of i P , K ( A ; B ) i_{P,K}(A;B) i P , K ( A ; B ) are bounded uniformly over all P P P . Indeed, if K min K_{\min} K m i n is the smallest positive channel entry, then on events of positive probability
log K min ≤ i P , K ( a ; b ) ≤ log ( 1 / P ( a ) ) , \log K_{\min}\le i_{P,K}(a;b)\le\log(1/P(a)), log K m i n ≤ i P , K ( a ; b ) ≤ log ( 1/ P ( a )) ,
and ∑ a P ( a ) log j ( 1 / P ( a ) ) \sum_a P(a)\log^j(1/P(a)) ∑ a P ( a ) log j ( 1/ P ( a )) is bounded for j = 2 , 3 j=2,3 j = 2 , 3 . Thus V ( P , K ) V(P,K) V ( P , K ) is bounded on the simplex.
The Berry–Esseen theorem applied to the independent summands in (30) gives
sup u ∣ Pr { J P , k ≤ k I ( P , K ) + u k } − Φ ( u V ( P , K ) ) ∣ ≤ c K k V ( P , K ) 3 / 2 (31) \sup_{u}\left|\Pr\{J_{P,k}\le kI(P,K)+u\sqrt{k}\}-\Phi\left(\frac{u}{\sqrt{V(P,K)}}\right)\right|\le\frac{c_K}{\sqrt{k}V(P,K)^{3/2}} \tag*{(31)} u sup Pr { J P , k ≤ k I ( P , K ) + u k } − Φ ( V ( P , K ) u ) ≤ k V ( P , K ) 3/2 c K (31)
whenever V ( P , K ) > 0 V(P,K)>0 V ( P , K ) > 0 . See also [8 Theorem 44 and Lemma 62] . Taking left limits gives the corresponding upper-tail bounds, with equality at the threshold included.
All capacity-achieving inputs have the same output law, which is positive on every output reachable through K K K . After deleting unreachable outputs, this law is strictly positive. Consequently, I ( P , K ) I(P,K) I ( P , K ) and V ( P , K ) V(P,K) V ( P , K ) have bounded derivatives on a fixed neighbourhood of the capacity-achieving set Π K \Pi_K Π K . The variance here is the conditional variance, whose finite-sum formula remains smooth even when some input probabilities vanish. Finally, the quadratic capacity-loss bound of [27 ] gives constants c , L , δ > 0 c,L,\delta>0 c , L , δ > 0 such that, with t = dist 2 ( P , Π K ) t=\operatorname{dist}_2(P,\Pi_K) t = dist 2 ( P , Π K ) and a closest P ∗ ∈ Π K P^*\in\Pi_K P ∗ ∈ Π K ,
C K − I ( P , K ) ≥ c t 2 , ∣ V ( P , K ) − V ( P ∗ , K ) ∣ ≤ L t , V ( P , K ) ≥ V min ( K ) / 2 (32) C_K-I(P,K)\ge ct^2,\qquad|V(P,K)-V(P^*,K)|\le Lt,\qquad V(P,K)\ge V_{\min}(K)/2 \tag*{(32)} C K − I ( P , K ) ≥ c t 2 , ∣ V ( P , K ) − V ( P ∗ , K ) ∣ ≤ L t , V ( P , K ) ≥ V m i n ( K ) /2 (32)
for t ≤ δ t\le\delta t ≤ δ . These estimates provide uniform constants below. The resource converse will not require a product-input assumption.
Lemma B.1 (Uniform conditional-type tail). For each input distribution P P P , choose a closest P ∗ ( P ) ∈ Π K P^*(P)\in\Pi_K P ∗ ( P ) ∈ Π K and put v ( P ) = V ( P ∗ ( P ) , K ) v(P)=V(P^*(P),K) v ( P ) = V ( P ∗ ( P ) , K ) . There is a constant c c c such that, for every k ≥ 2 k\ge2 k ≥ 2 , every k k k -type P P P , and every real ξ \xi ξ ,
Pr { J P , k ≥ k C K + ξ k } ≤ 1 − Φ ( ξ v ( P ) ) + c log k k . (33) \Pr\{J_{P,k}\ge kC_K+\xi\sqrt{k}\}\le1-\Phi\left(\frac{\xi}{\sqrt{v(P)}}\right)+c\frac{\log k}{\sqrt{k}}. \tag*{(33)} Pr { J P , k ≥ k C K + ξ k } ≤ 1 − Φ ( v ( P ) ξ ) + c k log k . (33) Proof. Choose a constant M M M bounding all conditional variances and all capacity-achieving variances, and put H k = 4 M ln k H_k=\sqrt{4M\ln k} H k = 4 M ln k . For t ≤ δ t\le\delta t ≤ δ , the Berry–Esseen remainder in (31) is O ( k − 1 / 2 ) O(k^{-1/2}) O ( k − 1/2 ) uniformly in P P P . Lipschitz continuity of the reciprocal square-root on the positive variance interval and (32) give
ξ + k ( C K − I ( P , K ) ) V ( P , K ) − ξ v ( P ) ≥ c 1 k t 2 − c 2 ∣ ξ ∣ t ≥ − c 3 ξ 2 k . \frac{\xi+\sqrt{k}(C_K-I(P,K))}{\sqrt{V(P,K)}}-\frac{\xi}{\sqrt{v(P)}}\ge c_1\sqrt{k}t^2-c_2|\xi|t\ge-c_3\frac{\xi^2}{\sqrt{k}}. V ( P , K ) ξ + k ( C K − I ( P , K )) − v ( P ) ξ ≥ c 1 k t 2 − c 2 ∣ ξ ∣ t ≥ − c 3 k ξ 2 . For ∣ ξ ∣ ≤ H k |\xi|\le H_k ∣ ξ ∣ ≤ H k , the Lipschitz bound for Φ \Phi Φ therefore proves (33) . For ξ > H k \xi>H_k ξ > H k , the actual mean is at most k C K kC_K k C K , so the probability on the left is at most 1 − Φ ( H k / M ) + O ( k − 1 / 2 ) = O ( k − 1 / 2 ) 1-\Phi(H_k/\sqrt{M})+O(k^{-1/2})=O(k^{-1/2}) 1 − Φ ( H k / M ) + O ( k − 1/2 ) = O ( k − 1/2 ) . For ξ < − H k \xi<-H_k ξ < − H k , the Gaussian tail on the right is at least 1 − k − 2 1-k^{-2} 1 − k − 2 , and the trivial upper bound one suffices.
Outside this neighbourhood, compactness and continuity give a fixed capacity gap C K − I ( P , K ) ≥ g > 0 C_K-I(P,K)\ge g>0 C K − I ( P , K ) ≥ g > 0 . For ξ ≥ − H k \xi\ge-H_k ξ ≥ − H k , the threshold exceeds the mean by at least k g / 2 kg/2 k g /2 once k k k is large. The variance bound and Chebyshev’s inequality give a probability O ( k − 1 ) O(k^{-1}) O ( k − 1 ) . For ξ < − H k \xi<-H_k ξ < − H k , the trivial bound again suffices. Enlarging c c c covers the finitely many smaller blocklengths. □
Lemma B.2 (Resource estimates and realization of Gaussian mixtures). Let k ≥ 2 k\ge2 k ≥ 2 , let P A k P_{A^k} P A k be any permutation-invariant input law, and set
p k = P A k K ⊗ k , q k = P A k ⊗ R B , k u . p_k=P_{A^k}K^{\otimes k},\qquad q_k=P_{A^k}\otimes R^u_{B,k}. p k = P A k K ⊗ k , q k = P A k ⊗ R B , k u . There is a probability measure λ k \lambda_k λ k on V K \mathcal{V}_K V K such that, for all ξ \xi ξ with h = k C K + ξ k ≥ 0 h=kC_K+\xi\sqrt{k}\ge0 h = k C K + ξ k ≥ 0 ,
α 2 − h ( p k , q k ) ≤ 1 − ∫ V K Φ ( ξ / v ) λ k ( d v ) + c log k k . (34) \alpha_{2-h}(p_k,q_k)\le1-\int_{\mathcal{V}_K}\Phi(\xi/\sqrt{v})\,\lambda_k(\mathrm{d}v)+c\frac{\log k}{\sqrt{k}}. \tag*{(34)} α 2 − h ( p k , q k ) ≤ 1 − ∫ V K Φ ( ξ / v ) λ k ( d v ) + c k log k . (34)
One measure works for all thresholds simultaneously. Conversely, for every probability measure λ \lambda λ on V K \mathcal{V}_K V K , there is a permutation-invariant input P A k P_{A^k} P A k for which
∣ α 2 − h ( p k , q k ) − 1 + ∫ V K Φ ( ξ / v ) λ ( d v ) ∣ ≤ c log k k . (35) \left|\alpha_{2-h}(p_k,q_k)-1+\int_{\mathcal{V}_K}\Phi(\xi/\sqrt{v})\lambda(dv)\right|\le c\frac{\log k}{\sqrt{k}}. \tag*{(35)} α 2 − h ( p k , q k ) − 1 + ∫ V K Φ ( ξ / v ) λ ( d v ) ≤ c k log k . (35)
The constant c c c is independent of the input law, λ \lambda λ , and ξ \xi ξ .
Proof. Decompose the permutation-invariant input law into its type classes:
P A k = ∑ P ∈ P k ( A ) θ ( P ) U T P k , θ ( P ) = P A k ( T P k ) . P_{A^k}=\sum_{P\in\mathcal{P}_k(\mathcal{A})}\theta(P)U_{T_P^k},\qquad\theta(P)=P_{A^k}(T_P^k). P A k = P ∈ P k ( A ) ∑ θ ( P ) U T P k , θ ( P ) = P A k ( T P k ) .
Write N k = ∣ P k ( B ) ∣ N_k=|\mathcal{P}_k(\mathcal{B})| N k = ∣ P k ( B ) ∣ . Every product output law is bounded pointwise by N k R B , k u N_kR_{\mathcal{B},k}^{\mathrm{u}} N k R B , k u . Conditional on input type P P P , the log-likelihood-ratio for ( p k , q k ) (p_k,q_k) ( p k , q k ) therefore satisfies
J ~ : = log K ⊗ k ( B k ∣ A k ) R B , k u ( B k ) ≤ J P , k + log N k . \widetilde{J}:=\log\frac{K^{\otimes k}(B^k\mid A^k)}{R_{\mathcal{B},k}^{\mathrm{u}}(B^k)}\le J_{P,k}+\log N_k. J := log R B , k u ( B k ) K ⊗ k ( B k ∣ A k ) ≤ J P , k + log N k .
Use the upper spectrum bound (17) with γ = log k \gamma=\log k γ = log k , then condition its likelihood-ratio event on the input type. This gives
α 2 − h ( p k , q k ) ≤ ∑ P θ ( P ) Pr { J P , k ≥ h − log k − log N k } + k − 1 . \alpha_{2-h}(p_k,q_k)\le\sum_P\theta(P)\Pr\{J_{P,k}\ge h-\log k-\log N_k\}+k^{-1}. α 2 − h ( p k , q k ) ≤ P ∑ θ ( P ) Pr { J P , k ≥ h − log k − log N k } + k − 1 .
Lemma B.1 and the common Lipschitz constant of the Gaussian CDFs, whose variances are at least V min ( K ) V_{\min}(K) V m i n ( K ) , now prove (34) with λ k = ∑ P θ ( P ) δ v ( P ) \lambda_k=\sum_P\theta(P)\delta_{v(P)} λ k = ∑ P θ ( P ) δ v ( P ) . We have used log N k = O ( log k ) \log N_k=O(\log k) log N k = O ( log k ) . Here we condition only the likelihood-ratio event in the spectrum bound. We do not optimize separate tests for different input types.
To realize a prescribed mixture, choose capacity-achieving inputs P − P_- P − , P + P_+ P + attaining the two endpoint variances. Their output laws agree, and the conditional variance is affine on Π K \Pi_K Π K . Linear interpolation therefore supplies a continuous choice P v ∈ Π K P_v\in\Pi_K P v ∈ Π K with V ( P v , K ) = v V(P_v,K)=v V ( P v , K ) = v for every v ∈ V K v\in\mathcal{V}_K v ∈ V K . When the interval is a singleton, use a constant choice. Set
P A k = ∫ V K P v ⊗ k λ ( d v ) . P_{A^k}=\int_{\mathcal{V}_K}P_v^{\otimes k}\lambda(dv). P A k = ∫ V K P v ⊗ k λ ( d v ) .
Its output law is ( P B ∗ ) ⊗ k (P_B^*)^{\otimes k} ( P B ∗ ) ⊗ k , where P B ∗ P_B^* P B ∗ is the common capacity-achieving output law. Conditional on the sampled v v v , the random variable
J = log K ⊗ k ( B k ∣ A k ) ( P B ∗ ) ⊗ k ( B k ) J=\log\frac{K^{\otimes k}(B^k\mid A^k)}{(P_B^*)^{\otimes k}(B^k)} J = log ( P B ∗ ) ⊗ k ( B k ) K ⊗ k ( B k ∣ A k )
is a sum of iid information densities with mean C K C_K C K and variance v v v . Here unconditional and conditional variances coincide: each input symbol used by a capacity-achieving law has row divergence C K C_K C K . The uniform third-moment bound and v ≥ V min ( K ) > 0 v\ge V_{\min}(K)>0 v ≥ V m i n ( K ) > 0 give
sup u ∣ Pr { J ≤ k C K + u k } − ∫ Φ ( u / v ) λ ( d v ) ∣ ≤ c 0 k − 1 / 2 . (36) \sup_u\left|\Pr\{J\le kC_K+u\sqrt{k}\}-\int\Phi(u/\sqrt{v})\lambda(dv)\right|\le c_0k^{-1/2}. \tag*{(36)} u sup Pr { J ≤ k C K + u k } − ∫ Φ ( u / v ) λ ( d v ) ≤ c 0 k − 1/2 . (36)
Apply the Berry–Esseen theorem conditionally on v v v and then integrate. Its constant is uniform in the measure λ \lambda λ .
Product domination gives J ~ ≤ J + log N k \widetilde{J}\le J+\log N_k J ≤ J + log N k . Since the actual output law is ( P B ∗ ) ⊗ k (P_B^*)^{\otimes k} ( P B ∗ ) ⊗ k , Markov’s inequality also gives
Pr { R B , k u ( B k ) ( P B ∗ ) ⊗ k ( B k ) > k } ≤ k − 1 . \Pr\left\{\frac{R_{\mathcal{B},k}^{\mathrm{u}}(B^k)}{(P_B^*)^{\otimes k}(B^k)}>k\right\}\le k^{-1}. Pr { ( P B ∗ ) ⊗ k ( B k ) R B , k u ( B k ) > k } ≤ k − 1 .
Thus J ~ ≥ J − log k \widetilde{J} \ge J-\log k J ≥ J − log k outside an event of probability k − 1 k^{-1} k − 1 . The two spectrum bounds imply
Pr { J ≥ h + log k } − k − 1 ≤ α 2 − h ( p k , q k ) ≤ Pr { J ≥ h − log k − log N k } + k − 1 . \Pr\{J \ge h+\log k\}-k^{-1} \le\alpha_{2-h}(p_k,q_k) \le\Pr\{J \ge h-\log k-\log N_k\}+k^{-1}. Pr { J ≥ h + log k } − k − 1 ≤ α 2 − h ( p k , q k ) ≤ Pr { J ≥ h − log k − log N k } + k − 1 .
Apply (36) to these tails. The Gaussian mixture distribution functions have Lipschitz constant at most ( 2 π V min ( K ) ) − 1 / 2 (2\pi V_{\min}(K))^{-1/2} ( 2 π V m i n ( K ) ) − 1/2 , so the threshold shifts change their values by O ( log k / k ) O(\log k/\sqrt{k}) O ( log k / k ) uniformly in λ \lambda λ and ξ \xi ξ . This proves (35) .
Lemma B.3 (Target estimate for every output reference). Fix η < ∞ \eta< \infty η < ∞ and k ≥ 2 k \ge2 k ≥ 2 . Let P ∗ ∈ Π K P^* \in\Pi_K P ∗ ∈ Π K and let P k P_k P k be a k k k -type with ∥ P k − P ∗ ∥ 2 ≤ η / k \lVert P_k-P^*\rVert_2 \le\eta/k ∥ P k − P ∗ ∥ 2 ≤ η / k . Put
p k = U P k T K ⊗ k , q k = U P k T ⊗ R k , p_k=U_{P_k}^{\mathsf{T}}K^{\otimes k}, \qquad q_k=U_{P_k}^{\mathsf{T}}\otimes R_k, p k = U P k T K ⊗ k , q k = U P k T ⊗ R k , where R k R_k R k is any output distribution. With v = V ( P ∗ , K ) v=V(P^*,K) v = V ( P ∗ , K ) , uniformly for h = k C K + ξ k ≥ 0 h=kC_K+\xi\sqrt{k}\ge0 h = k C K + ξ k ≥ 0 ,
α 2 − h ( p k , q k ) ≥ 1 − Φ ( ξ / v ) − c K , η log k k . (37) \alpha_{2-h}(p_k,q_k) \ge1-\Phi(\xi/\sqrt{v})-c_{K,\eta}\frac{\log k}{\sqrt{k}}. \tag*{(37)} α 2 − h ( p k , q k ) ≥ 1 − Φ ( ξ / v ) − c K , η k log k . (37)
Proof. For any k k k -type P P P , the product law with marginal P P P assigns its type class mass at least ( k + 1 ) − ∣ A ∣ (k+1)^{-|A|} ( k + 1 ) − ∣ A ∣ . Conditioning this law on its type class gives the uniform law. The corresponding channel output marginal therefore satisfies
( U P k T K ⊗ k ) ( b k ) ≤ ( k + 1 ) ∣ A ∣ ( P K ) ⊗ k ( b k ) . \left(U_{P_k}^{\mathsf{T}}K^{\otimes k}\right)(b^k) \le(k+1)^{|A|}(PK)^{\otimes k}(b^k). ( U P k T K ⊗ k ) ( b k ) ≤ ( k + 1 ) ∣ A ∣ ( P K ) ⊗ k ( b k ) .
Write a k = ∣ A ∣ log ( k + 1 ) a_k=|A|\log(k+1) a k = ∣ A ∣ log ( k + 1 ) . For every R k R_k R k and γ > 0 \gamma>0 γ > 0 , summing over the exceptional outputs yields
Pr { log R k ( B k ) ( P K ) ⊗ k ( B k ) > a k + γ } ≤ 2 − γ . (38) \Pr\left\{\log\frac{R_k(B^k)}{(PK)^{\otimes k}(B^k)}>a_k+\gamma\right\}\le2^{-\gamma}. \tag*{(38)} Pr { log ( P K ) ⊗ k ( B k ) R k ( B k ) > a k + γ } ≤ 2 − γ . (38)
Outputs outside the support of ( P K ) ⊗ k (PK)^{\otimes k} ( P K ) ⊗ k have zero actual probability. Where R k ( B k ) = 0 R_k(B^k)=0 R k ( B k ) = 0 , the log-likelihood-ratio for ( p k , q k ) (p_k,q_k) ( p k , q k ) is + ∞ +\infty + ∞ , and the following lower bound still holds. The lower spectrum bound and (38) give
α 2 − h ( p k , q k ) ≥ Pr { J P k , k ≥ h + a k + log k } − k − 1 . \alpha_{2-h}(p_k,q_k)\ge\Pr\{J_{P_k,k}\ge h+a_k+\log k\}-k^{-1}. α 2 − h ( p k , q k ) ≥ Pr { J P k , k ≥ h + a k + log k } − k − 1 .
The derivative bounds near Π K \Pi_K Π K imply, uniformly in P ∗ P^* P ∗ and P k P_k P k ,
k ( C K − I ( P k , K ) ) = O ( 1 ) , V ( P k , K ) = v + O ( k − 1 ) . k(C_K-I(P_k,K))=O(1), \qquad V(P_k,K)=v+O(k^{-1}). k ( C K − I ( P k , K )) = O ( 1 ) , V ( P k , K ) = v + O ( k − 1 ) .
In particular, the actual variance stays bounded away from zero for large k k k . Equation (31) therefore compares the last tail with 1 − Φ ( ( ξ + Δ k ) / V ( P k , K ) ) 1-\Phi((\xi+\Delta_k)/\sqrt{V(P_k,K)}) 1 − Φ (( ξ + Δ k ) / V ( P k , K ) ) , up to O ( k − 1 / 2 ) O(k^{-1/2}) O ( k − 1/2 ) , where 0 ≤ Δ k = O ( log k / k ) 0\le\Delta_k=O(\log k/\sqrt{k}) 0 ≤ Δ k = O ( log k / k ) . This comparison is uniform even for unbounded ξ \xi ξ : for variances s s s in a compact subset of ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , both
∣ ∂ ∂ u Φ ( u / s ) ∣ = ϕ ( u / s ) s , ∣ ∂ ∂ s Φ ( u / s ) ∣ = ∣ u ∣ ϕ ( u / s ) 2 s 3 / 2 \left|\frac{\partial}{\partial u}\Phi(u/\sqrt{s})\right|=\frac{\phi(u/\sqrt{s})}{\sqrt{s}}, \qquad\left|\frac{\partial}{\partial s}\Phi(u/\sqrt{s})\right|=\frac{|u|\phi(u/\sqrt{s})}{2s^{3/2}} ∂ u ∂ Φ ( u / s ) = s ϕ ( u / s ) , ∂ s ∂ Φ ( u / s ) = 2 s 3/2 ∣ u ∣ ϕ ( u / s )
are uniformly bounded over u ∈ R u\in\mathbb{R} u ∈ R . Replacing the location and variance thus costs O ( log k / k ) O(\log k/\sqrt{k}) O ( log k / k ) , proving the claim for large k k k . Increasing the constant covers the finitely many smaller k ≥ 2 k\ge2 k ≥ 2 . Every bound is independent of R k R_k R k , as required for the protocol-dependent reference in the converse.
Shared randomness: agreement and separation
We give examples with positive capacities and dispersions for which the shared-randomness second-order coefficient agrees with the non-signalling value, and prove a strict second-order separation for another pair. The agreement examples also show that resonance is possible with shared randomness. Matching the total information variances, however, does not suffice in general. Whenever the SR and NS values agree, the EA value agrees as well, since SR ⊆ \subseteq ⊆ EA ⊆ \subseteq ⊆ NS.
Shared-randomness resonance for packet-erasure channels
Let E a ( δ ) E_a(\delta) E a ( δ ) be the erasure channel with input alphabet { 0 , 1 } a \{0,1\}^a { 0 , 1 } a : it transmits the entire a a a -bit input with probability 1 − δ 1-\delta 1 − δ and otherwise outputs one erasure symbol. Thus
C E a ( δ ) = a ( 1 − δ ) , V E a ( δ ) = a 2 δ ( 1 − δ ) . C_{E_a(\delta)}=a(1-\delta),\qquad V_{E_a(\delta)}=a^2\delta(1-\delta). C E a ( δ ) = a ( 1 − δ ) , V E a ( δ ) = a 2 δ ( 1 − δ ) .
For a > 1 a>1 a > 1 , the channel erases all a a a bits together, unlike a product of a a a independent binary erasure channels.
Proposition C.1. Fix an integer a ≥ 1 a\ge1 a ≥ 1 and 0 < δ T < δ W < 1 0<\delta_T<\delta_W<1 0 < δ T < δ W < 1 . Let T = E a ( δ T ) T=E_a(\delta_T) T = E a ( δ T ) and W = BEC ( δ W ) W=\operatorname{BEC}(\delta_W) W = BEC ( δ W ) , and set
α = 1 − δ T , β = 1 − δ W , r = a α β , σ T = a α ( 1 − α ) , σ W = a α ( 1 − β ) . \alpha=1-\delta_T,\qquad\beta=1-\delta_W,\qquad r=\frac{a\alpha}{\beta},\qquad\sigma_T=a\sqrt{\alpha(1-\alpha)},\qquad\sigma_W=\sqrt{a\alpha(1-\beta)}. α = 1 − δ T , β = 1 − δ W , r = β a α , σ T = a α ( 1 − α ) , σ W = a α ( 1 − β ) . For A ∈ { S R , E A , N S } A\in\{\mathrm{SR},\mathrm{EA},\mathrm{NS}\} A ∈ { SR , EA , NS } and every fixed 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 ,
m A ∗ ( n , ϵ ; T , W ) = r n + d ϵ β n + o ( n ) , (39) m_A^*(n,\epsilon;T,W)=rn+\frac{d_\epsilon}{\beta}\sqrt{n}+o(\sqrt{n}), \tag*{(39)} m A ∗ ( n , ϵ ; T , W ) = r n + β d ϵ n + o ( n ) , (39) d ϵ = inf ϵ < u < 1 { σ T Φ − 1 ( u ) − σ W Φ − 1 ( u − ϵ ) } . d_\epsilon=\inf_{\epsilon<u<1}\{\sigma_T\Phi^{-1}(u)-\sigma_W\Phi^{-1}(u-\epsilon)\}. d ϵ = ϵ < u < 1 inf { σ T Φ − 1 ( u ) − σ W Φ − 1 ( u − ϵ )} . For every m ≥ a n m\ge an m ≥ an , there is an SR protocol with error exactly
Δ n , m = max t ∈ Z { Pr [ a K ≤ t ] − Pr [ L ≤ t ] } , K ∼ Bin ( n , α ) , L ∼ Bin ( m , β ) . (40) \Delta_{n,m}=\max_{t\in\mathbb{Z}}\{\Pr[aK\le t]-\Pr[L\le t]\},\qquad K\sim\operatorname{Bin}(n,\alpha),\quad L\sim\operatorname{Bin}(m,\beta). \tag*{(40)} Δ n , m = t ∈ Z max { Pr [ a K ≤ t ] − Pr [ L ≤ t ]} , K ∼ Bin ( n , α ) , L ∼ Bin ( m , β ) . (40) The displayed binomial laws specify the two marginal distributions. The protocol couples these counts dependently.
Proof. Using shared randomness, choose a uniform ordered sample of a n an an distinct target positions. Pack their input bits, a a a at a time, into the n n n resource symbols. Conditional on K = k K=k K = k surviving resource packets, the receiver knows the correct bits on a uniform a k ak ak -subset of the m m m target positions. This statement holds for every target input word, since the random injection and the erasure pattern are independent of its values.
Write Q a K , Q L Q_{aK},Q_L Q a K , Q L for generalized quantiles, and put Δ = Δ n , m \Delta=\Delta_{n,m} Δ = Δ n , m . The coupling
a K = Q a K ( U ) , L ′ = Q L ( ( U − Δ ) m o d 1 ) , U uniform on [ 0 , 1 ) , aK=Q_{aK}(U),\qquad L'=Q_L((U-\Delta)\bmod1),\qquad U\ \text{uniform on }[0,1), a K = Q a K ( U ) , L ′ = Q L (( U − Δ ) mod 1 ) , U uniform on [ 0 , 1 ) ,
satisfies Pr { L ′ > a K } = Δ \Pr\{L'>aK\}=\Delta Pr { L ′ > a K } = Δ . Indeed, for U ≥ Δ U\ge\Delta U ≥ Δ , F L ( Q a K ( U ) ) ≥ U − Δ F_L(Q_{aK}(U))\ge U-\Delta F L ( Q a K ( U )) ≥ U − Δ , hence L ′ ≤ a K L'\le aK L ′ ≤ a K . Every coupling has failure probability at least F a K ( t ) − F L ( t ) F_{aK}(t)-F_L(t) F a K ( t ) − F L ( t ) for each t t t . The receiver implements this coupling by sampling U U U uniformly within the quantile interval corresponding to its observed count. It then reveals a uniformly chosen subset of size J = min ( a K , L ′ ) J=\min(aK,L') J = min ( a K , L ′ ) of the received bits. This requires no communication back to the encoder. Conditional on J J J , the revealed set is uniform and all its values are correct, exactly as for the target channel conditional on its visible count. Thus the worst-input channel error equals TV ( L ( J ) , L ( L ) ) = Δ \operatorname{TV}(\mathcal{L}(J),\mathcal{L}(L))=\Delta TV ( L ( J ) , L ( L )) = Δ : the upper bound follows from the coupling, and the reverse bound from J ≤ a K J\le aK J ≤ a K .
Because r > a r>a r > a , the condition m ≥ a n m\ge an m ≥ an holds throughout any fixed second-order window for all sufficiently large n n n . At m = ⌊ r n + d n / β ⌋ m=\lfloor rn+d\sqrt{n}/\beta\rfloor m = ⌊ r n + d n / β ⌋ , uniform Berry–Esseen estimates give
Δ n , m ⟶ D ( d ) : = sup x { Φ ( x / σ T ) − Φ ( ( x − d ) / σ W ) } . (41) \Delta_{n,m}\longrightarrow D(d):=\sup_x\{\Phi(x/\sigma_T)-\Phi((x-d)/\sigma_W)\}. \tag*{(41)} Δ n , m ⟶ D ( d ) := x sup { Φ ( x / σ T ) − Φ (( x − d ) / σ W )} . (41)
Theorem 1.1 gives the same NS converse, since σ T 2 = V T \sigma_T^2=V_T σ T 2 = V T and σ W 2 = r V W \sigma_W^2=rV_W σ W 2 = r V W . The inclusions SR ⊆ \subseteq ⊆ EA ⊆ \subseteq ⊆ NS therefore give the same limiting error for all three assistance classes. The positive branch of D D D is strictly increasing, and inversion gives (39) .
Thus shared randomness attains the threshold error at the capacity ratio. To evaluate this threshold, put
ν = σ W 2 σ T 2 = δ W a δ T , ϵ ∗ = D ( 0 ) = ∣ Φ ( x ν ) − Φ ( x ν / ν ) ∣ , x ν = ν ln ν ν − 1 . (42) \nu=\frac{\sigma_W^2}{\sigma_T^2}=\frac{\delta_W}{a\delta_T},\qquad\epsilon_* =D(0)=\left|\Phi(x_\nu)-\Phi(x_\nu/\sqrt{\nu})\right|,\qquad x_\nu=\sqrt{\frac{\nu\ln\nu}{\nu-1}}. \tag*{(42)} ν = σ T 2 σ W 2 = a δ T δ W , ϵ ∗ = D ( 0 ) = Φ ( x ν ) − Φ ( x ν / ν ) , x ν = ν − 1 ν ln ν . (42)
At ν = 1 \nu=1 ν = 1 set ϵ ∗ = 0 \epsilon_*=0 ϵ ∗ = 0 . If ν ≠ 1 \nu\ne1 ν = 1 , then d ϵ ∗ = 0 d_{\epsilon_*}=0 d ϵ ∗ = 0 , and the optimal rate at this fixed positive threshold satisfies
m A ∗ ( n , ϵ ∗ ) n = r + o ( n − 1 / 2 ) , A ∈ { S R , E A , N S } . \frac{m_A^*(n,\epsilon_*)}{n}=r+o(n^{-1/2}),\qquad A\in\{\mathrm{SR},\mathrm{EA},\mathrm{NS}\}. n m A ∗ ( n , ϵ ∗ ) = r + o ( n − 1/2 ) , A ∈ { SR , EA , NS } .
For a > 1 a>1 a > 1 , the error at m = ⌊ r n ⌋ m=\lfloor rn\rfloor m = ⌊ r n ⌋ tends to zero when δ T = δ W / a \delta_T=\delta_W/a δ T = δ W / a . This gives zero-threshold resonance for two fixed, distinct channels at an interior point of 0 < δ T < δ W 0<\delta_T<\delta_W 0 < δ T < δ W . The statement concerns vanishing asymptotic error. It does not require exact conversion at finite blocklength.
For example, fix W = B E C ( 1 / 2 ) W=\mathrm{BEC}(1/2) W = BEC ( 1/2 ) and let T = E 2 ( δ ) T=E_2(\delta) T = E 2 ( δ ) , 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 . Then
r = 4 ( 1 − δ ) , ν = 1 4 δ . r=4(1-\delta),\qquad\nu=\frac{1}{4\delta}. r = 4 ( 1 − δ ) , ν = 4 δ 1 .
and (42) has its zero at δ = 1 / 4 \delta=1/4 δ = 1/4 . The interval where ϵ ∗ ≤ 0.01 \epsilon_*\le0.01 ϵ ∗ ≤ 0.01 has endpoints approximately 0.230 and 0.272, the solutions of (42) with ϵ ∗ = 0.01 \epsilon_*=0.01 ϵ ∗ = 0.01 . The resulting threshold-error curve is analogous to Figure 2 of [6 ] , with the same value for SR, EA, and NS assistance.
At the resonance point, the resource has capacity 3 / 2 3/2 3/2 and variance 3 / 4 3/4 3/4 , whereas the target has capacity 1 / 2 1/2 1/2 and variance 1 / 4 1/4 1/4 . Thus r = 3 r=3 r = 3 and V T = r V W = 3 / 4 V_T=rV_W=3/4 V T = r V W = 3/4 . In particular,
m A ∗ ( n , ϵ ) = 3 n + 2 3 Φ − 1 ( 1 + ϵ 2 ) n + o ( n ) m_A^*(n,\epsilon)=3n+2\sqrt{3}\,\Phi^{-1}\left(\frac{1+\epsilon}{2}\right)\sqrt{n}+o(\sqrt{n}) m A ∗ ( n , ϵ ) = 3 n + 2 3 Φ − 1 ( 2 1 + ϵ ) n + o ( n )
for every fixed positive ϵ \epsilon ϵ . The finite-blocklength protocol at m = 3 n m=3n m = 3 n uses only random injection and thinning. Its error has the exact expression
Δ n , 3 n = 2 − 3 n max 0 ≤ t ≤ 3 n { 2 n ∑ k = 0 min ( n , ⌊ t / 2 ⌋ ) ( n k ) 3 k − ∑ j = 0 t ( 3 n j ) } . (43) \Delta_{n,3n}=2^{-3n}\max_{0\le t\le3n}\left\{2^n\sum_{k=0}^{\min(n,\lfloor t/2\rfloor)}\binom{n}{k}3^k-\sum_{j=0}^{t}\binom{3n}{j}\right\}. \tag*{(43)} Δ n , 3 n = 2 − 3 n 0 ≤ t ≤ 3 n max ⎩ ⎨ ⎧ 2 n k = 0 ∑ m i n ( n , ⌊ t /2 ⌋) ( k n ) 3 k − j = 0 ∑ t ( j 3 n ) ⎭ ⎬ ⎫ . (43)
All terms in braces are integers. Exact evaluation gives
9.718 × 10 − 3 < Δ 250 , 750 < 9.719 × 10 − 3 < 0.01. 9.718\times10^{-3}<\Delta_{250,750}<9.719\times10^{-3}<0.01. 9.718 × 1 0 − 3 < Δ 250 , 750 < 9.719 × 1 0 − 3 < 0.01.
Thus 250 resource uses simulate 750 target uses at the capacity ratio with error below one percent. At a shorter blocklength, a target length one below the capacity-ratio length also suffices:
Δ 16 , 47 = 701606824869 70368744177664 , \Delta_{16,47}=\frac{701606824869}{70368744177664}, Δ 16 , 47 = 70368744177664 701606824869 ,
9.970 × 10 − 3 < Δ 16 , 47 < 9.971 × 10 − 3 < 0.01. 9.970\times10^{-3}<\Delta_{16,47}<9.971\times10^{-3}<0.01. 9.970 × 1 0 − 3 < Δ 16 , 47 < 9.971 × 1 0 − 3 < 0.01.
The target length is 47 = 3 ⋅ 16 − 1 47=3\cdot16-1 47 = 3 ⋅ 16 − 1 , giving rate 47 / 16 ≃ 2.938 47/16\simeq2.938 47/16 ≃ 2.938 , only 1 / 48 1/48 1/48 below the capacity ratio in relative terms. The script verify_packet_resonance.py verifies both maxima and decimal brackets using rational arithmetic. These are the exact errors of the specified protocol. They give achievable SR bounds. Optimality at finite blocklength is not claimed.
The case a = 1 a=1 a = 1 recovers conversion between distinct binary erasure channels in the direction δ T < δ W \delta_T<\delta_W δ T < δ W . The reverse direction remains outside this packing argument, since the capacity-ratio target length is then smaller than a n an an and the required injection is unavailable.
Binary-symmetric self-conversion
Proposition C.2. For T = W = BSC ( q ) T = W = \operatorname{BSC}(q) T = W = BSC ( q ) , 0 < q < 1 / 2 0 < q < 1/2 0 < q < 1/2 , and fixed b ∈ R b \in\mathbb{R} b ∈ R ,
lim n → ∞ e A ( n , ⌊ n + b n ⌋ ) = [ 2 Φ ( b C q 2 V q ) − 1 ] + , A ∈ { S R , E A , N S } . (44) \lim_{n \to\infty} e_A\left(n,\left\lfloor n+b\sqrt{n}\right\rfloor\right) = \left[2\Phi\left(\frac{bC_q}{2\sqrt{V_q}}\right)-1\right]_{+}, \qquad A \in\{\mathrm{SR},\mathrm{EA},\mathrm{NS}\}. \tag*{(44)} n → ∞ lim e A ( n , ⌊ n + b n ⌋ ) = [ 2Φ ( 2 V q b C q ) − 1 ] + , A ∈ { SR , EA , NS } . (44) Consequently all three assistance classes have the expansion
m A ∗ ( n , ϵ ) = n + 2 V q C q Φ − 1 ( 1 + ϵ 2 ) n + o ( n ) . (45) m_A^*(n,\epsilon) = n + \frac{2\sqrt{V_q}}{C_q}\Phi^{-1}\left(\frac{1+\epsilon}{2}\right)\sqrt{n}+o(\sqrt{n}). \tag*{(45)} m A ∗ ( n , ϵ ) = n + C q 2 V q Φ − 1 ( 2 1 + ϵ ) n + o ( n ) . (45)
Proof. For b ≤ 0 b \le0 b ≤ 0 , discard resource uses. Suppose b > 0 b > 0 b > 0 and fix q < t < 1 / 2 q < t < 1/2 q < t < 1/2 and 1 < ρ < C q / C t 1 < \rho< C_q/C_t 1 < ρ < C q / C t . Channel coding followed by shared-randomness simulation converts N N N uses of BSC ( q ) \operatorname{BSC}(q) BSC ( q ) to ⌊ ρ N ⌋ \lfloor\rho N\rfloor ⌊ ρN ⌋ uses of BSC ( t ) \operatorname{BSC}(t) BSC ( t ) with vanishing worst-input error as N → ∞ N \to\infty N → ∞ [8 , 3 ] . Choose both component rates strictly within their first-order limits. Apply this construction to
N n = b n ρ − 1 + O ( 1 ) , L n = ρ N n + O ( 1 ) N_n = \frac{b\sqrt{n}}{\rho-1}+O(1), \qquad L_n = \rho N_n+O(1) N n = ρ − 1 b n + O ( 1 ) , L n = ρ N n + O ( 1 )
resource and target positions, and use the other n − N n n-N_n n − N n resource coordinates directly. Choose the integer roundings to obtain at least ⌊ n + b n ⌋ \left\lfloor n+b\sqrt{n}\right\rfloor ⌊ n + b n ⌋ target positions, with only O ( 1 ) O(1) O ( 1 ) excess, and discard the excess after a shared uniform permutation.
Up to o ( 1 ) o(1) o ( 1 ) TV error, the simulated noise before discarding is a uniform permutation of independent Bernoulli noise: parameter q q q on n − N n n-N_n n − N n positions and parameter t t t on L n L_n L n positions. Both it and the ideal target noise are uniform conditional on Hamming weight. Their TV distance is therefore the distance between the weight laws. For independent A M ∼ Bin ( M , q ) A_M \sim\operatorname{Bin}(M,q) A M ∼ Bin ( M , q ) , B M ∼ Bin ( L M , t ) B_M \sim\operatorname{Bin}(L_M,t) B M ∼ Bin ( L M , t ) and D M ∼ Bin ( L M , q ) D_M \sim\operatorname{Bin}(L_M,q) D M ∼ Bin ( L M , q ) , with L M / M → a L_M/\sqrt{M} \to a L M / M → a ,
TV ( A M + B M , A M + D M ) ⟶ 2 Φ ( a ∣ t − q ∣ 2 q ( 1 − q ) ) − 1. (46) \operatorname{TV}(A_M+B_M,A_M+D_M)\longrightarrow2\Phi\left(\frac{a\lvert t-q\rvert}{2\sqrt{q(1-q)}}\right)-1. \tag*{(46)} TV ( A M + B M , A M + D M ) ⟶ 2Φ ( 2 q ( 1 − q ) a ∣ t − q ∣ ) − 1. (46)
We justify this total variation limit directly. Binomial unimodality gives
TV ( A M , A M + 1 ) = max j Pr { A M = j } = O ( M − 1 / 2 ) . \operatorname{TV}(A_M,A_M+1)=\max_j\Pr\{A_M=j\}=O(M^{-1/2}). TV ( A M , A M + 1 ) = j max Pr { A M = j } = O ( M − 1/2 ) .
Replacing B M , D M B_M,D_M B M , D M by nearest integers to their means costs O ( ( L M + 1 ) / M ) = o ( 1 ) O(\sqrt{(L_M+1)/M})=o(1) O ( ( L M + 1 ) / M ) = o ( 1 ) in TV. For an integer shift h M / M → a ( t − q ) h_M/\sqrt{M}\to a(t-q) h M / M → a ( t − q ) , write p M p_M p M for the mass function of A M A_M A M . Stirling’s formula on central windows gives
ln p M ( A M − h M ) p M ( A M ) ⟹ N ( − v 2 / 2 , v 2 ) , v = a ( t − q ) q ( 1 − q ) , \ln\frac{p_M(A_M-h_M)}{p_M(A_M)}\Longrightarrow N(-v^2/2,v^2), \qquad v=\frac{a(t-q)}{\sqrt{q(1-q)}}, ln p M ( A M ) p M ( A M − h M ) ⟹ N ( − v 2 /2 , v 2 ) , v = q ( 1 − q ) a ( t − q ) ,
and boundary events vanish. Applying the bounded continuous function x ↦ ( 1 − e x ) + x\mapsto(1-e^x)_+ x ↦ ( 1 − e x ) + proves (46) . Thus the weight comparison holds in total variation, as required for the channel error, rather than only in distribution.
Our protocol thus has limiting error at most
2 Φ ( b ρ ( t − q ) 2 ( ρ − 1 ) q ( 1 − q ) ) − 1. 2\Phi\left(\frac{b\rho(t-q)}{2(\rho-1)\sqrt{q(1-q)}}\right)-1. 2Φ ( 2 ( ρ − 1 ) q ( 1 − q ) b ρ ( t − q ) ) − 1.
First let ρ ↑ C q / C t \rho\uparrow C_q/C_t ρ ↑ C q / C t , then t ↓ q t \downarrow q t ↓ q . Since C q − C t = ℓ q ( t − q ) + O ( ( t − q ) 2 ) C_q-C_t=\ell_q(t-q)+O((t-q)^2) C q − C t = ℓ q ( t − q ) + O (( t − q ) 2 ) , this becomes the right side of (44) . The parameters t t t and ρ \rho ρ remain fixed while n → ∞ n\to\infty n → ∞ , so the argument requires only coding and simulation at fixed rates below their respective first-order limits. The NS converse gives equality, and monotonicity in target length gives (45) .
The construction preserves the resource noise in all but O ( n ) O(\sqrt{n}) O ( n ) coordinates. Coding and simulation are needed only on this smaller block. Direct use supplies the remaining target coordinates.
A tighter shared-randomness converse: BEC-to-BSC
For this final example, let T = BEC ( 1 − α ) T=\operatorname{BEC}(1-\alpha) T = BEC ( 1 − α ) and W = BSC ( q ) W=\operatorname{BSC}(q) W = BSC ( q ) , with 0 < α < 1 0<\alpha<1 0 < α < 1 and 0 < q < 1 / 2 0<q<1/2 0 < q < 1/2 . Thus α \alpha α is the probability that a resource bit is visible. Put r = α / C q r=\alpha/C_q r = α / C q and m n ( d ) = ⌊ r n + d n C q ⌋ m_n(d)=\left\lfloor rn+\frac{d\sqrt{n}}{C_q}\right\rfloor m n ( d ) = ⌊ r n + C q d n ⌋ . An SR protocol uses the same encoder for every erasure pattern. We first derive a constraint that follows from this requirement. The auxiliary-source construction follows the binary-Hamming erasure-broadcast converse of [26 ] . We account explicitly for conditioning on simultaneous success and then average over ranges of erasure counts in the Gaussian limit. The resulting converse is strictly stronger than the NS bound, although it does not determine the optimal SR coefficient.
Lemma C.3 (Conditioned broadcast bound). Let S S S be uniform on { 0 , 1 } m \{0,1\}^{m} { 0 , 1 } m , and let R R R contain all independent protocol seeds, so that X n X^n X n is a deterministic function of ( S , R ) (S,R) ( S , R ) . Choose uniform nested masks A 1 ⊂ A 2 A_1\subset A_2 A 1 ⊂ A 2 , of sizes k 1 < k 2 k_1<k_2 k 1 < k 2 , independently of ( S , R ) (S,R) ( S , R ) . Set B i = X A i B_i=X_{A_i} B i = X A i and C 0 = ( A 1 , A 2 , R ) C_0=(A_1,A_2,R) C 0 = ( A 1 , A 2 , R ) . Suppose the two reconstructions S ^ i ( B i , C 0 ) \widehat{S}_i(B_i,C_0) S i ( B i , C 0 ) obey
G = { d H ( S , S ^ i ) ≤ m d i for i = 1 , 2 } , Pr ( G ) = 1 − η > 0 , G=\{d_H(S,\widehat{S}_i)\le md_i\text{ for }i=1,2\},\qquad\Pr(G)=1-\eta>0, G = { d H ( S , S i ) ≤ m d i for i = 1 , 2 } , Pr ( G ) = 1 − η > 0 , where 0 ≤ d i ≤ 1 / 2 0\le d_i\le1/2 0 ≤ d i ≤ 1/2 . For λ = k 1 / k 2 \lambda=k_1/k_2 λ = k 1 / k 2 , Δ = k 2 − k 1 \Delta=k_2-k_1 Δ = k 2 − k 1 and 0 < θ < 1 / 2 0<\theta<1/2 0 < θ < 1/2 ,
m C θ ⋆ d 1 + λ m { h ( θ ⋆ d 2 ) − h ( d 2 ) } − k 1 ≤ η λ Δ + ( 1 − λ ) h ( η ) 1 − η + ( 1 + λ ) log 1 1 − η , θ ⋆ t = θ + ( 1 − 2 θ ) t . (47) mC_{\theta\star d_1}+\lambda m\{h(\theta\star d_2)-h(d_2)\}-k_1
\le\frac{\eta\lambda\Delta+(1-\lambda)h(\eta)}{1-\eta}+(1+\lambda)\log\frac{1}{1-\eta},
\qquad\theta\star t=\theta+(1-2\theta)t. \tag*{(47)} m C θ ⋆ d 1 + λm { h ( θ ⋆ d 2 ) − h ( d 2 )} − k 1 ≤ 1 − η η λ Δ + ( 1 − λ ) h ( η ) + ( 1 + λ ) log 1 − η 1 , θ ⋆ t = θ + ( 1 − 2 θ ) t . (47) Proof. Write P P P for the original law, Q = P ( ⋅ ∣ G ) Q=P(\mathord{\cdot}\mid G) Q = P ( ⋅ ∣ G ) and D 0 = log ( 1 / ( 1 − η ) ) D_0=\log(1/(1-\eta)) D 0 = log ( 1/ ( 1 − η )) . After conditioning, generate U = S ⊕ N U=S\oplus N U = S ⊕ N with fresh independent N ∼ Ber ( θ ) ⊗ m N\sim\operatorname{Ber}(\theta)^{\otimes m} N ∼ Ber ( θ ) ⊗ m . Since S , U S,U S , U are uniform and independent of C 0 C_0 C 0 under P P P , D ( Q ∥ P ) = D 0 D(Q\|P)=D_0 D ( Q ∥ P ) = D 0 implies H Q ( S ∣ C 0 ) , H Q ( U ∣ C 0 ) ≥ m − D 0 H_Q(S\mid C_0),H_Q(U\mid C_0)\ge m-D_0 H Q ( S ∣ C 0 ) , H Q ( U ∣ C 0 ) ≥ m − D 0 . The binary Fano inequality and conditional vector Mrs. Gerber’s lemma [28 ] give, respectively,
I Q ( U ; B 1 ∣ C 0 ) ≥ m C θ ⋆ d 1 − D 0 , I_Q(U;B_1\mid C_0)\ge mC_{\theta\star d_1}-D_0, I Q ( U ; B 1 ∣ C 0 ) ≥ m C θ ⋆ d 1 − D 0 , I Q ( S ; B 2 ∣ U , C 0 ) ≥ m { h ( θ ⋆ d 2 ) − h ( d 2 ) } − D 0 . I_Q(S;B_2\mid U,C_0)\ge m\{h(\theta\star d_2)-h(d_2)\}-D_0. I Q ( S ; B 2 ∣ U , C 0 ) ≥ m { h ( θ ⋆ d 2 ) − h ( d 2 )} − D 0 . For the second inequality, use H Q ( S ∣ B 2 , C 0 ) ≤ m h ( d 2 ) H_Q(S\mid B_2,C_0)\le mh(d_2) H Q ( S ∣ B 2 , C 0 ) ≤ mh ( d 2 ) and the fact that h ( θ ⋆ h − 1 ( t ) ) − t h(\theta\star h^{-1}(t))-t h ( θ ⋆ h − 1 ( t )) − t is decreasing on [ 0 , 1 ] [0,1] [ 0 , 1 ] . h − 1 h^{-1} h − 1 is taken in [ 0 , 1 / 2 ] [0,1/2] [ 0 , 1/2 ] .
For any law L L L , define D L = H L ( B 1 ∣ U , C 0 ) − λ H L ( B 2 ∣ U , C 0 ) D_L=H_L(B_1\mid U,C_0)-\lambda H_L(B_2\mid U,C_0) D L = H L ( B 1 ∣ U , C 0 ) − λ H L ( B 2 ∣ U , C 0 ) . Under P P P , uniform masks independent of ( X n , U , R ) (X^n,U,R) ( X n , U , R ) give D P ≥ 0 D_P\ge0 D P ≥ 0 : average subset-entropy per coordinate decreases with subset size, by Han’s subset-entropy inequality [34 ] , or directly by the entropy chain rule along a uniform random ordering. For Q − = P ( ⋅ ∣ G c ) Q^-=P(\mathord{\cdot}\mid G^c) Q − = P ( ⋅ ∣ G c ) the exact mixture identity is
D P = ( 1 − η ) D Q + η D Q − + I P ( B 1 ; 1 G ∣ U , C 0 ) − λ I P ( B 2 ; 1 G ∣ U , C 0 ) . D_P=(1-\eta)D_Q+\eta D_{Q^-}
+I_P(B_1;1_G\mid U,C_0)-\lambda I_P(B_2;1_G\mid U,C_0). D P = ( 1 − η ) D Q + η D Q − + I P ( B 1 ; 1 G ∣ U , C 0 ) − λ I P ( B 2 ; 1 G ∣ U , C 0 ) . As B 1 B_1 B 1 is a function of ( B 2 , C 0 ) (B_2,C_0) ( B 2 , C 0 ) , the second line is at most ( 1 − λ ) h ( η ) (1-\lambda)h(\eta) ( 1 − λ ) h ( η ) . Also D Q − ≤ ( 1 − λ ) k 1 = λ Δ D_{Q^-}\le(1-\lambda)k_1=\lambda\Delta D Q − ≤ ( 1 − λ ) k 1 = λ Δ . Thus
D Q ≥ − η λ Δ + ( 1 − λ ) h ( η ) 1 − η . D_Q\ge-\frac{\eta\lambda\Delta+(1-\lambda)h(\eta)}{1-\eta}. D Q ≥ − 1 − η η λ Δ + ( 1 − λ ) h ( η ) . Finally, determinism of B 2 B_2 B 2 given ( S , C 0 ) (S,C_0) ( S , C 0 ) implies
I Q ( U ; B 1 ∣ C 0 ) + λ I Q ( S ; B 2 ∣ U , C 0 ) = H Q ( B 1 ∣ C 0 ) − D Q ≤ k 1 − D Q . I_Q(U;B_1\mid C_0)+\lambda I_Q(S;B_2\mid U,C_0)=H_Q(B_1\mid C_0)-D_Q\le k_1-D_Q. I Q ( U ; B 1 ∣ C 0 ) + λ I Q ( S ; B 2 ∣ U , C 0 ) = H Q ( B 1 ∣ C 0 ) − D Q ≤ k 1 − D Q . Combining these bounds proves the claim. If η = 0 \eta=0 η = 0 , use D P ≥ 0 D_P\ge0 D P ≥ 0 directly. The independence of the masks is used only under the original law P P P . The mixture identity accounts for its loss under conditioning.
Define
f θ = C θ ⋆ q C q , a θ = ( 1 − 2 θ ) ℓ θ ⋆ q ℓ q , κ θ = f θ − a θ > 0. (48) f_\theta=\frac{C_{\theta\star q}}{C_q},\qquad a_\theta=\frac{(1-2\theta)\ell_{\theta\star q}}{\ell_q},\qquad\kappa_\theta=f_\theta-a_\theta>0. \tag*{(48)} f θ = C q C θ ⋆ q , a θ = ℓ q ( 1 − 2 θ ) ℓ θ ⋆ q , κ θ = f θ − a θ > 0. (48)
To prove the strict inequality, use the positive series
A ( t ) = C ( 1 − t ) / 2 = 1 ln 2 ∑ j ≥ 1 t 2 j 2 j ( 2 j − 1 ) . A(t)=C_{(1-t)/2}=\frac{1}{\ln2}\sum_{j\geq1}\frac{t^{2j}}{2j(2j-1)}. A ( t ) = C ( 1 − t ) /2 = ln 2 1 j ≥ 1 ∑ 2 j ( 2 j − 1 ) t 2 j .
For z ∈ ( 0 , 1 ) z\in(0,1) z ∈ ( 0 , 1 ) , A ( z t ) / A ( t ) A(zt)/A(t) A ( z t ) / A ( t ) is a weighted average of z 2 j z^{2j} z 2 j . Its derivative with respect to ln t \ln t ln t is 2 Cov ( j , z 2 j ) < 0 2\operatorname{Cov}(j,z^{2j})<0 2 Cov ( j , z 2 j ) < 0 . Hence f θ f_\theta f θ increases with q q q , and direct differentiation gives f θ ′ ( q ) = ℓ q ( f θ − a θ ) / C q > 0 f'_\theta(q)=\ell_q(f_\theta-a_\theta)/C_q>0 f θ ′ ( q ) = ℓ q ( f θ − a θ ) / C q > 0 . In fact 0 < a θ < f θ < 1 0<a_\theta<f_\theta<1 0 < a θ < f θ < 1 .
Proposition C.4 (Strict separation at resonance). Suppose α ( 1 − α ) = r V q = σ 2 > 0 \alpha(1-\alpha)=rV_q=\sigma^2>0 α ( 1 − α ) = r V q = σ 2 > 0 . Fix 0 < θ < 1 / 2 0<\theta<1/2 0 < θ < 1/2 , write κ = κ θ \kappa=\kappa_\theta κ = κ θ , and put
M = Φ ( 1 + κ / 2 ) − Φ ( 1 − κ / 2 ) , g = κ M 2 ( 2 + κ ) > 0. (49) M=\Phi(1+\kappa/2)-\Phi(1-\kappa/2),\qquad g=\frac{\kappa M}{2(2+\kappa)}>0. \tag*{(49)} M = Φ ( 1 + κ /2 ) − Φ ( 1 − κ /2 ) , g = 2 ( 2 + κ ) κ M > 0. (49) Then, for every fixed real d d d ,
lim inf n e S R ( n , m n ( d ) ) ≥ g − ∣ d ∣ σ 2 π . (50) \liminf_{n} e_{\mathrm{SR}}(n,m_n(d))\geq g-\frac{|d|}{\sigma\sqrt{2\pi}}. \tag*{(50)} n lim inf e SR ( n , m n ( d )) ≥ g − σ 2 π ∣ d ∣ . (50) In particular, for ϵ = g / 4 \epsilon=g/4 ϵ = g /4 ,
lim sup n m S R ∗ ( n , ϵ ) − r n n ≤ − g σ 2 π 2 C q < 0 , \limsup_{n}\frac{m_{\mathrm{SR}}^*(n,\epsilon)-rn}{\sqrt n}\leq-\frac{g\sigma\sqrt{2\pi}}{2C_q}<0, n lim sup n m SR ∗ ( n , ϵ ) − r n ≤ − 2 C q g σ 2 π < 0 , lim n m N S ∗ ( n , ϵ ) − r n n = 2 σ C q Φ − 1 ( 1 + ϵ 2 ) > 0. (51) \lim_{n}\frac{m_{\mathrm{NS}}^*(n,\epsilon)-rn}{\sqrt n}=\frac{2\sigma}{C_q}\Phi^{-1}\left(\frac{1+\epsilon}{2}\right)>0. \tag*{(51)} n lim n m NS ∗ ( n , ϵ ) − r n = C q 2 σ Φ − 1 ( 2 1 + ϵ ) > 0. (51)
Proof. For the visible-bit count K K K and reconstruction Z Z Z , set
J q ( S , Z ) = m C q − ℓ q { d H ( S , Z ) − m q } , X n = K − n α n , Y n = J q ( S , Z ) − n α n . J_q(S,Z)=mC_q-\ell_q\{d_H(S,Z)-mq\},\qquad X_n=\frac{K-n\alpha}{\sqrt n},\qquad Y_n=\frac{J_q(S,Z)-n\alpha}{\sqrt n}. J q ( S , Z ) = m C q − ℓ q { d H ( S , Z ) − m q } , X n = n K − n α , Y n = n J q ( S , Z ) − n α .
Then X n ⇒ N ( 0 , σ 2 ) X_n\Rightarrow N(0,\sigma^2) X n ⇒ N ( 0 , σ 2 ) , whereas the ideal target score converges to Γ d = N ( d , σ 2 ) \Gamma_d=N(d,\sigma^2) Γ d = N ( d , σ 2 ) . For each fixed output z z z , E S 2 J q ( S , z ) = 1 \mathbb{E}_{S}2^{J_q(S,z)}=1 E S 2 J q ( S , z ) = 1 . Given a mask with K = k K=k K = k and the seed, a deterministic decoder has at most 2 k 2^k 2 k reconstruction words. A union bound and Markov’s inequality therefore give
Pr { J q ( S , Z ) > k + u ∣ mask,seed } ≤ 2 − u . \Pr\{J_q(S,Z)>k+u\mid\text{mask,seed}\}\leq2^{-u}. Pr { J q ( S , Z ) > k + u ∣ mask,seed } ≤ 2 − u .
Allowing the score to take values on the extended real line, pass to a subsequential joint limit ( X , Y ) (X,Y) ( X , Y ) . The preceding bound implies X ∼ N ( 0 , σ 2 ) X\sim N(0,\sigma^2) X ∼ N ( 0 , σ 2 ) and Y ≤ X Y\leq X Y ≤ X almost surely. The limit may have mass at Y = − ∞ Y=-\infty Y = − ∞ . Data processing and lower semicontinuity of total variation give
e : = TV ( L ( Y ) , Γ d ) ≤ lim inf { protocol errors on the subsequence } . (52) e:=\operatorname{TV}(\mathcal{L}(Y),\Gamma_d)\leq\liminf\{\text{protocol errors on the subsequence}\}. \tag*{(52)} e := TV ( L ( Y ) , Γ d ) ≤ lim inf { protocol errors on the subsequence } . (52)
We next pass from the finite broadcast bound to a constraint on this joint limit. For counts k i = n α + x i n k_i=n\alpha+x_i\sqrt n k i = n α + x i n and score thresholds y i y_i y i , choose distortion bounds corresponding to J q ≥ n α + y i n J_q\geq n\alpha+y_i\sqrt n J q ≥ n α + y i n . For each mask, use the original protocol’s decoder, ignoring the other mask. Each marginal failure probability then depends only on its own count, as required for the averaging below. Taylor expansion of the left side of (47), divided by n \sqrt n n , gives
A θ = a θ y 1 + ( 1 − a θ ) y 2 − f θ x 1 − ( 1 − f θ ) x 2 . A_\theta=a_\theta y_1+(1-a_\theta)y_2-f_\theta x_1-(1-f_\theta)x_2. A θ = a θ y 1 + ( 1 − a θ ) y 2 − f θ x 1 − ( 1 − f θ ) x 2 .
The terms involving d d d cancel. The right side, divided by n \sqrt{n} n , converges to η ( x 2 − x 1 ) / ( 1 − η ) \eta(x_2-x_1)/(1-\eta) η ( x 2 − x 1 ) / ( 1 − η ) . Consequently the sum of the two marginal failure probabilities is at least
[ A θ ] + x 2 − x 1 + [ A θ ] + . (53) \frac{[A_\theta]_+}{x_2-x_1+[A_\theta]_+}. \tag*{(53)} x 2 − x 1 + [ A θ ] + [ A θ ] + . (53)
We use this bound after averaging over two separated count intervals. No pointwise convergence of conditional laws is needed. If simultaneous success has probability zero at a count pair, the sum of marginal failure probabilities is at least one, and the bound is immediate. For all other count pairs, apply (47) to each finite count pair and invert its increasing right side in η \eta η . The joint failure probability is at most the sum of the two marginal failure probabilities. The inverse converges to (53) uniformly on compact separated intervals, since the Taylor estimates are uniform there and the limiting inverse stays below one. Now average the inequality over the product of the two normalized count distributions. The CLT and Portmanteau theorem pass this averaged bound to the joint limit: write it as an upper bound on the sum of success probabilities, apply Portmanteau to the open events Y > y i Y>y_i Y > y i , and take complements. The count-interval boundaries have zero Gaussian probability. The argument permits the encoder to depend arbitrarily on blocklength.
Now take
y 1 = − σ − κ σ / 2 , y 2 = σ − κ σ / 2 , I i = [ y i , y i + κ σ ] . y_1=-\sigma-\kappa\sigma/2,\qquad y_2=\sigma-\kappa\sigma/2,\qquad I_i=[y_i,y_i+\kappa\sigma]. y 1 = − σ − κσ /2 , y 2 = σ − κσ /2 , I i = [ y i , y i + κσ ] .
Both count intervals have probability M M M in the limit. If x i = y i + δ i ∈ I i x_i=y_i+\delta_i\in I_i x i = y i + δ i ∈ I i , then
A θ − κ 2 ( x 2 − x 1 ) = κ σ − ( a θ + κ / 2 ) δ 1 − ( 1 − a θ − κ / 2 ) δ 2 ≥ 0. A_\theta-\frac{\kappa}{2}(x_2-x_1)=\kappa\sigma-(a_\theta+\kappa/2)\delta_1-(1-a_\theta-\kappa/2)\delta_2\ge0. A θ − 2 κ ( x 2 − x 1 ) = κσ − ( a θ + κ /2 ) δ 1 − ( 1 − a θ − κ /2 ) δ 2 ≥ 0.
The two coefficients are positive and sum to one. The averaged version of (53) therefore gives
Pr { Y ≤ y 1 ∣ X ∈ I 1 } + Pr { Y ≤ y 2 ∣ X ∈ I 2 } ≥ κ 2 + κ . \Pr\{Y\le y_1\mid X\in I_1\}+\Pr\{Y\le y_2\mid X\in I_2\}\ge\frac{\kappa}{2+\kappa}. Pr { Y ≤ y 1 ∣ X ∈ I 1 } + Pr { Y ≤ y 2 ∣ X ∈ I 2 } ≥ 2 + κ κ .
Since Y ≤ X Y\le X Y ≤ X , we have
Pr { Y ≤ y < X } = F Y ( y ) − F X ( y ) ≤ ϵ + sup z ∣ F Γ d ( z ) − F Γ 0 ( z ) ∣ ≤ ϵ + ∣ d ∣ σ 2 π . \Pr\{Y\le y<X\}=F_Y(y)-F_X(y)\le\epsilon+\sup_z\lvert F_{\Gamma_d}(z)-F_{\Gamma_0}(z)\rvert\le\epsilon+\frac{\lvert d\rvert}{\sigma\sqrt{2\pi}}. Pr { Y ≤ y < X } = F Y ( y ) − F X ( y ) ≤ ϵ + z sup ∣ F Γ d ( z ) − F Γ 0 ( z )∣ ≤ ϵ + σ 2 π ∣ d ∣ .
Each conditional failure probability on the preceding two intervals is at most this quantity divided by M M M . This proves (50) , using (52) on a subsequence approaching the liminf. At d = − g σ 2 π / 2 d=-g\sigma\sqrt{2\pi}/2 d = − g σ 2 π /2 , the error lower bound is g / 2 > ϵ g/2>\epsilon g /2 > ϵ . Target marginalization implies the SR limsup bound in (51) . The NS value follows from resonance in Theorem 1.1 . □
For a concrete binary pair, take q = 1 / 100 q=1/100 q = 1/100 , α = 1 − V q / C q \alpha=1-V_q/C_q α = 1 − V q / C q and θ = 1 / 10 \theta=1/10 θ = 1/10 . Then α ( 1 − α ) = r V q \alpha(1-\alpha)=rV_q α ( 1 − α ) = r V q and
T = BEC ( 1 − α ) , W = BSC ( 0.01 ) , 1 − α ≃ 0.473 , r ≃ 0.573 , T=\operatorname{BEC}(1-\alpha),\qquad W=\operatorname{BSC}(0.01),\qquad1-\alpha\simeq0.473,\qquad r\simeq0.573, T = BEC ( 1 − α ) , W = BSC ( 0.01 ) , 1 − α ≃ 0.473 , r ≃ 0.573 ,
with g ≃ 1.857 × 10 − 3 g\simeq1.857\times10^{-3} g ≃ 1.857 × 1 0 − 3 . At ϵ = g / 4 ≃ 4.643 × 10 − 4 \epsilon=g/4\simeq4.643\times10^{-4} ϵ = g /4 ≃ 4.643 × 1 0 − 4 , the SR coefficient is at most − 1.264 × 10 − 3 -1.264\times10^{-3} − 1.264 × 1 0 − 3 , whereas the NS coefficient is approximately 6.321 × 10 − 4 6.321\times10^{-4} 6.321 × 1 0 − 4 . The constants have not been optimized. The result gives a strict second-order separation without assuming that an SR coefficient exists or determining its optimal value. The unrestricted EA coefficient for this pair remains open. The SR converse uses the requirement of one encoder for different noise realizations, as in broadcast converses for source–channel coding [26 ] .
Exact conversion of additive channels
For additive channels, the binary-experiment description is exact at every blocklength and requires no auxiliary communication. Let G , H G,H G , H be finite abelian groups, let P , R P,R P , R be noise distributions on these groups, and define T P ( y ∣ x ) = P ( y − x ) T_P(y \mid x)=P(y-x) T P ( y ∣ x ) = P ( y − x ) and W R ( z ∣ s ) = R ( z − s ) W_R(z \mid s)=R(z-s) W R ( z ∣ s ) = R ( z − s ) . Then
e N S ( n , m ; T P , W R ) = min M : M U G n = U H m TV ( M P ⊗ n , R ⊗ m ) = sup 0 ≤ y ≤ 1 { α y ( R ⊗ m , U H m ) − α y ( P ⊗ n , U G n ) } . (54) e_{\mathrm{NS}}(n,m;T_P,W_R)=\min_{M:MU_{G^n}=U_{H^m}}\operatorname{TV}(MP^{\otimes n},R^{\otimes m})
=\sup_{0\le y\le1}\{\alpha_y(R^{\otimes m},U_{H^m})-\alpha_y(P^{\otimes n},U_{G^n})\}. \tag*{(54)} e NS ( n , m ; T P , W R ) = M : M U G n = U H m min TV ( M P ⊗ n , R ⊗ m ) = 0 ≤ y ≤ 1 sup { α y ( R ⊗ m , U H m ) − α y ( P ⊗ n , U G n )} . (54)
Here the minimum is over stochastic matrices, and U U U denotes the uniform law on the indicated group. This formula applies to every noise distribution, including those with zero dispersion or zero capacity. Positive capacities are needed only when we express the asymptotic rate as a capacity ratio.
To prove the first equality, start with a stochastic map M M M that preserves the uniform reference and set
N ( x , z ∣ s , y ) = ∣ G ∣ − n M z − s , y − x , x , y ∈ G n , s , z ∈ H m . N(x,z\mid s,y)=|G|^{-n}M_{z-s,y-x},\qquad x,y\in G^n,\quad s,z\in H^m. N ( x , z ∣ s , y ) = ∣ G ∣ − n M z − s , y − x , x , y ∈ G n , s , z ∈ H m .
Stochasticity gives the sender marginal ∣ G ∣ − n |G|^{-n} ∣ G ∣ − n , while uniform preservation gives the receiver marginal ∣ H ∣ − m |H|^{-m} ∣ H ∣ − m . Thus N N N is non-signalling. Contracting it with the resource channel gives an additive channel with noise M P ⊗ n MP^{\otimes n} M P ⊗ n . Every row therefore has the same total variation error.
Conversely, average any NS channel independently over simultaneous translations of ( x , y ) (x,y) ( x , y ) and ( s , z ) (s,z) ( s , z ) . The channel laws are invariant under these translations, and convexity of total variation ensures that the error cannot increase. The averaged channel depends only on y − x y-x y − x and z − s z-s z − s , so the NS conditions force both marginals to be uniform. Setting M b , a = ∣ G ∣ n N ( x , z ∣ s , y ) M_{b,a}=|G|^nN(x,z\mid s,y) M b , a = ∣ G ∣ n N ( x , z ∣ s , y ) for a = y − x a=y-x a = y − x , b = z − s b=z-s b = z − s recovers a stochastic map that preserves the uniform reference. This proves the first equality in (54) . The testing-curve identity (16) proves the second.
The uniform input achieves capacity, and
C T P = log ∣ G ∣ − H ( P ) , V T P = Var A ∼ P log ( ∣ G ∣ P ( A ) ) . C_{T_P}=\log|G|-H(P),\qquad V_{T_P}=\operatorname{Var}_{A\sim P}\log(|G|P(A)). C T P = log ∣ G ∣ − H ( P ) , V T P = Var A ∼ P log ( ∣ G ∣ P ( A )) .
Every capacity-achieving input induces a uniform output. The information density in each row consequently has the distribution log ( ∣ G ∣ P ( A ) ) \log(|G|P(A)) log ( ∣ G ∣ P ( A )) for A ∼ P A\sim P A ∼ P . Hence the minimum and maximum dispersions agree, even when the capacity-achieving input is not unique. For BSCs, (54) compares binomial testing curves, which can be evaluated exactly by randomizing at a threshold. When the capacities and dispersions are positive, Theorem 1.1 gives their Gaussian limit.
Zero-dispersion additive channels
The exact characterization (54) does not require positive dispersion. An additive channel has V T = 0 V_T=0 V T = 0 if and only if its noise is uniform on its support S ⊆ G S\subseteq G S ⊆ G . In this case C T = log ( ∣ G ∣ / ∣ S ∣ ) C_T=\log(|G|/|S|) C T = log ( ∣ G ∣/∣ S ∣ ) and
α y ( P ⊗ n , U G n ) = min { 1 , 2 n C T y } , 0 ≤ y ≤ 1. (55) \alpha_y(P^{\otimes n},U_{G^n})=\min\{1,2^{nC_T}y\},\qquad0\le y\le1. \tag*{(55)} α y ( P ⊗ n , U G n ) = min { 1 , 2 n C T y } , 0 ≤ y ≤ 1. (55)
To see this, zero variance means that log ( ∣ G ∣ P ( a ) ) \log(|G|P(a)) log ( ∣ G ∣ P ( a )) is constant on the support of P P P . For the product distribution, the likelihood-ratio is therefore 2 n C T 2^{nC_T} 2 n C T on S n S^n S n and zero elsewhere. This gives (55) . Such channels need not be noiseless: uniform noise on { 0 , 1 } \{0,1\} { 0 , 1 } in Z 3 \mathbb{Z}_3 Z 3 gives capacity log ( 3 / 2 ) > 0 \log(3/2)>0 log ( 3/2 ) > 0 and zero dispersion.
If both additive channels have zero dispersion and positive capacities, substitution in (54) gives the exact formulas
e N S ( n , m ; T , W ) = [ 1 − 2 n C T − m C W ] + , m N S ∗ ( n , ϵ ; T , W ) = ⌈ n C T − log ( 1 − ϵ ) C W ⌉ . (56) e_{\mathrm{NS}}(n,m;T,W)=\left[1-2^{nC_T-mC_W}\right]_+,
\qquad
m_{\mathrm{NS}}^*(n,\epsilon;T,W)=\left\lceil\frac{nC_T-\log(1-\epsilon)}{C_W}\right\rceil. \tag*{(56)} e NS ( n , m ; T , W ) = [ 1 − 2 n C T − m C W ] + , m NS ∗ ( n , ϵ ; T , W ) = ⌈ C W n C T − log ( 1 − ϵ ) ⌉ . (56)
The second-order coefficient is therefore zero.
If one channel is additive with zero dispersion and the other has positive dispersion, we can reduce the problem to coding or simulation through a noiseless channel. Write K K K for the zero-dispersion channel. Comparing (55) with the testing curve of a noiseless alphabet gives the exact NS conversions
id ⌈ 2 k C K ⌉ ⟶ K ⊗ k ⟶ id ⌊ 2 k C K ⌋ . \operatorname{id}_{\lceil2^{kC_K}\rceil}\longrightarrow K^{\otimes k}\longrightarrow\operatorname{id}_{\lfloor2^{kC_K}\rfloor}. id ⌈ 2 k C K ⌉ ⟶ K ⊗ k ⟶ id ⌊ 2 k C K ⌋ .
The logarithms of these two alphabet sizes differ from k C K kC_K k C K by at most O ( 1 ) O(1) O ( 1 ) . The usual coding and simulation expansions [8 , 9 , 3 ] then yield, with r = C T / C W r=C_T/C_W r = C T / C W and C T , C W > 0 C_T,C_W>0 C T , C W > 0 ,
m N S ∗ ( n , ϵ ; T , W ) = r n + { V T C W Φ − 1 ( ϵ ) n + O ( log n ) , V W = 0 < V T , r V W C W Φ − 1 ( ϵ ) n + O ( log n ) , V T = 0 < V W . (57) m_{\mathrm{NS}}^*(n,\epsilon;T,W)=rn+
\begin{cases}
\dfrac{\sqrt{V_T}}{C_W}\Phi^{-1}(\epsilon)\sqrt{n}+O(\log n), & V_W=0<V_T,\\
\dfrac{\sqrt{rV_W}}{C_W}\Phi^{-1}(\epsilon)\sqrt{n}+O(\log n), & V_T=0<V_W.
\end{cases} \tag*{(57)} m NS ∗ ( n , ϵ ; T , W ) = r n + ⎩ ⎨ ⎧ C W V T Φ − 1 ( ϵ ) n + O ( log n ) , C W r V W Φ − 1 ( ϵ ) n + O ( log n ) , V W = 0 < V T , V T = 0 < V W . (57)
The positive-dispersion channel need not be additive, provided its capacity-achieving dispersion is unique. The zero-dispersion channel must be additive. Composing coding or simulation protocols with the displayed exact conversions gives both the upper and lower bounds. We therefore do not need to substitute zero variance into a Gaussian estimate.
When the zero-dispersion channel is id 2 \operatorname{id}_2 id 2 , the coding and simulation theorems give the same second-order expansion for all three assistance classes [8 , 9 , 3 ] under the positive unique-dispersion assumption on the noisy channel: for A ∈ { S R , E A , N S } A\in\{\mathrm{SR},\mathrm{EA},\mathrm{NS}\} A ∈ { SR , EA , NS } ,
m A ∗ ( n , ϵ ; T , id 2 ) = n C T + n V T Φ − 1 ( ϵ ) + O ( log n ) , m_A^*(n,\epsilon;T,\operatorname{id}_2)=nC_T+\sqrt{nV_T}\Phi^{-1}(\epsilon)+O(\log n), m A ∗ ( n , ϵ ; T , id 2 ) = n C T + n V T Φ − 1 ( ϵ ) + O ( log n ) ,
m A ∗ ( n , ϵ ; id 2 , W ) = n C W + V W C W 3 / 2 Φ − 1 ( ϵ ) n + O ( log n ) . m_A^*(n,\epsilon;\operatorname{id}_2,W)=\frac{n}{C_W}+\frac{\sqrt{V_W}}{C_W^{3/2}}\Phi^{-1}(\epsilon)\sqrt{n}+O(\log n). m A ∗ ( n , ϵ ; id 2 , W ) = C W n + C W 3/2 V W Φ − 1 ( ϵ ) n + O ( log n ) .
Together, these statements settle the zero-dispersion cases for additive channels. They do not settle the general nonadditive boundary V min = 0 V_{\min}=0 V m i n = 0 .
Finite-blocklength certificates and explicit remainder bounds
For 0 < p < 1 / 2 0<p<1/2 0 < p < 1/2 , let A n , p ( u ) A_{n,p}(u) A n , p ( u ) be the piecewise-linear curve joining ( 0 , 0 ) (0,0) ( 0 , 0 ) and
u n , j = 2 − n ∑ i = 0 j ( n i ) , A n , p ( u n , j ) = F n , p ( j ) : = ∑ i = 0 j ( n i ) p i ( 1 − p ) n − i , 0 ≤ j ≤ n . u_{n,j}=2^{-n}\sum_{i=0}^{j}\binom{n}{i},
\qquad
A_{n,p}(u_{n,j})=F_{n,p}(j):=\sum_{i=0}^{j}\binom{n}{i}p^i(1-p)^{n-i},
\qquad0\le j\le n. u n , j = 2 − n i = 0 ∑ j ( i n ) , A n , p ( u n , j ) = F n , p ( j ) := i = 0 ∑ j ( i n ) p i ( 1 − p ) n − i , 0 ≤ j ≤ n .
This is the testing curve of ( Ber ( p ) ) ⊗ n , U { 0 , 1 } n (\operatorname{Ber}(p))^{\otimes n},U_{\{0,1\}^n} ( Ber ( p ) ) ⊗ n , U { 0 , 1 } n . Its linear segments correspond to randomization within a Hamming shell. Consequently, (54) gives
e N S ( n , m ; BSC ( p ) , BSC ( q ) ) = max 0 ≤ j ≤ m { F m , q ( j ) − A n , p ( u m , j ) } . (58) e_{\mathrm{NS}}(n,m;\operatorname{BSC}(p),\operatorname{BSC}(q))
=\max_{0\le j\le m}\left\{F_{m,q}(j)-A_{n,p}(u_{m,j})\right\}. \tag*{(58)} e NS ( n , m ; BSC ( p ) , BSC ( q )) = 0 ≤ j ≤ m max { F m , q ( j ) − A n , p ( u m , j ) } . (58)
It suffices to check the target knots. Between two consecutive knots, the target curve is affine and the source curve is concave, so their difference is convex and attains its maximum at an endpoint. For rational p , q p,q p , q , every quantity in (58) is rational. The resulting error bounds are therefore exact finite-blocklength certificates, rather than asymptotic approximations.
For p = 1 / 10 p=1/10 p = 1/10 , q = 1 / 20 q=1/20 q = 1/20 , n = 25 n=25 n = 25 and m = 18 m=18 m = 18 , the maximum occurs at u = 2 − 18 u=2^{-18} u = 2 − 18 . The target test accepts only the zero-error word. The source test accepts shells 0, 1 and 102 / 300 102/300 102/300 of shell 2. Hence
e N S ( 25 , 18 ) = ( 19 20 ) 18 − 102 25 ( 9 10 ) 23 ∈ ( 0.035 , 0.036 ) . (59) e_{\mathrm{NS}}(25,18)=\left(\frac{19}{20}\right)^{18}-\frac{102}{25}\left(\frac{9}{10}\right)^{23}\in(0.035,0.036). \tag*{(59)} e NS ( 25 , 18 ) = ( 20 19 ) 18 − 25 102 ( 10 9 ) 23 ∈ ( 0.035 , 0.036 ) . (59)
Rational bounds on logarithms give 18 < 25 C p / C q < 19 18<25C_p/C_q<19 18 < 25 C p / C q < 19 and V p / ( r V q ) > 1.19 \sqrt{V_p/(rV_q)}>1.19 V p / ( r V q ) > 1.19 . The latter inequality also shows that ϵ ∗ > 0.04 \epsilon_*>0.04 ϵ ∗ > 0.04 : evaluating the Gaussian deficit at ξ = − V p \xi=-\sqrt{V_p} ξ = − V p and using convexity of the normal density ϕ \phi ϕ on [ 1 , 1.19 ] [1,1.19] [ 1 , 1.19 ] gives
ϵ ∗ ≥ ∫ 1 1.19 ϕ ( t ) d t ≥ 0.19 ϕ ( 1.095 ) > 0.04. \epsilon_* \ge\int_{1}^{1.19}\phi(t)\,\mathrm{d}t \ge0.19\phi(1.095)>0.04. ϵ ∗ ≥ ∫ 1 1.19 ϕ ( t ) d t ≥ 0.19 ϕ ( 1.095 ) > 0.04.
Thus the target length m = 18 = ⌊ 25 r ⌋ m=18=\lfloor25r\rfloor m = 18 = ⌊ 25 r ⌋ is achievable at the exact cancellation error ϵ ∗ \epsilon_* ϵ ∗ , without relying on rounded Gaussian probabilities. Integer and higher-order corrections need not have a favourable sign at every blocklength: for the same pair, e N S ( 50 , ⌊ 50 r ⌋ ) = e N S ( 50 , 37 ) > 0.069 e_{\mathrm{NS}}(50,\lfloor50r\rfloor)=e_{\mathrm{NS}}(50,37)>0.069 e NS ( 50 , ⌊ 50 r ⌋) = e NS ( 50 , 37 ) > 0.069 .
For p = 2 / 5 p=2/5 p = 2/5 , q = 9 / 20 q=9/20 q = 9/20 , n = 20 n=20 n = 20 and m = 81 m=81 m = 81 , the maximum in (58) occurs at u = u 81 , 34 u=u_{81,34} u = u 81 , 34 . Put
θ = u 81 , 34 − u 20 , 6 u 20 , 7 − u 20 , 6 . \theta=\frac{u_{81,34}-u_{20,6}}{u_{20,7}-u_{20,6}}. θ = u 20 , 7 − u 20 , 6 u 81 , 34 − u 20 , 6 .
Then
e N S ( 20 , 81 ) = F 81 , 9 / 20 ( 34 ) − F 20 , 2 / 5 ( 6 ) − θ ( 20 7 ) ( 2 / 5 ) 7 ( 3 / 5 ) 13 e_{\mathrm{NS}}(20,81)=F_{81,9/20}(34)-F_{20,2/5}(6)-\theta\binom{20}{7}(2/5)^7(3/5)^{13} e NS ( 20 , 81 ) = F 81 , 9/20 ( 34 ) − F 20 , 2/5 ( 6 ) − θ ( 7 20 ) ( 2/5 ) 7 ( 3/5 ) 13
∈ ( 0.007 , 0.008 ) . \in(0.007,0.008). ∈ ( 0.007 , 0.008 ) .
Since 80 < 20 C p / C q < 81 80<20C_p/C_q<81 80 < 20 C p / C q < 81 , this example achieves the capacity-ratio length rounded up. The accompanying script verify_resonance.py checks both maxima and all displayed rational brackets by exact arithmetic.
For 0 < p , q < 1 / 2 0<p,q<1/2 0 < p , q < 1/2 , we can also obtain a Gaussian upper bound on the finite-blocklength error with explicit constants. Define
Δ = m C q − n C p , B p = 0.4748 p 2 + ( 1 − p ) 2 p ( 1 − p ) , \Delta=mC_q-nC_p,\qquad B_p=0.4748\frac{p^2+(1-p)^2}{\sqrt{p(1-p)}}, Δ = m C q − n C p , B p = 0.4748 p ( 1 − p ) p 2 + ( 1 − p ) 2 ,
G n , m ( a ) = sup t ∈ R { Φ ( t n V p ) − Φ ( t − a m V q ) } . G_{n,m}(a)=\sup_{t\in\mathbb{R}}\left\{\Phi\left(\frac{t}{\sqrt{nV_p}}\right)-\Phi\left(\frac{t-a}{\sqrt{mV_q}}\right)\right\}. G n , m ( a ) = t ∈ R sup { Φ ( n V p t ) − Φ ( m V q t − a ) } .
For every n , m ≥ 1 n,m\ge1 n , m ≥ 1 and γ > 0 \gamma>0 γ > 0 ,
e N S ( n , m ) ≤ min { 1 , G n , m ( Δ + γ ) + B p n + B q m + 2 − γ } . (60) e_{\mathrm{NS}}(n,m)\le\min\left\{1,G_{n,m}(\Delta+\gamma)+\frac{B_p}{\sqrt{n}}+\frac{B_q}{\sqrt{m}}+2^{-\gamma}\right\}. \tag*{(60)} e NS ( n , m ) ≤ min { 1 , G n , m ( Δ + γ ) + n B p + m B q + 2 − γ } . (60)
Indeed, at reference budget u = 2 − h u=2^{-h} u = 2 − h , the spectrum bounds (17) give
A m , q ( u ) − A n , p ( u ) ≤ Pr [ J q ( m ) ≥ h − γ ] − Pr [ J p ( n ) ≥ h ] + 2 − γ , A_{m,q}(u)-A_{n,p}(u)\le\Pr[J_q^{(m)}\ge h-\gamma]-\Pr[J_p^{(n)}\ge h]+2^{-\gamma}, A m , q ( u ) − A n , p ( u ) ≤ Pr [ J q ( m ) ≥ h − γ ] − Pr [ J p ( n ) ≥ h ] + 2 − γ ,
where J p ( n ) J_p^{(n)} J p ( n ) is the sum of n n n independent information densities log ( 2 Ber ( p ) ( X ) ) \log(2\operatorname{Ber}(p)(X)) log ( 2 Ber ( p ) ( X )) . Its mean is n C p nC_p n C p and its variance is n V p nV_p n V p . The standardized third absolute moment of one summand is ( p 2 + ( 1 − p ) 2 ) / p ( 1 − p ) (p^2+(1-p)^2)/\sqrt{p(1-p)} ( p 2 + ( 1 − p ) 2 ) / p ( 1 − p ) . Applying the iid Berry–Esseen bound [29 ] to both tails and setting t = h − n C p t=h-nC_p t = h − n C p proves (60). Using left limits of the distribution functions accounts for the atoms of these lattice laws.
In particular, at m = ⌊ r n ⌋ ≥ 1 m=\lfloor rn\rfloor\ge1 m = ⌊ r n ⌋ ≥ 1 , the bound implies
e N S ( n , m ) ≤ ϵ ∗ + ∣ ln ( m / ( r n ) ) ∣ 2 2 π e + γ 2 π m V q + B p n + B q m + 2 − γ . (61) e_{\mathrm{NS}}(n,m)\le\epsilon_*+\frac{|\ln(m/(rn))|}{2\sqrt{2\pi e}}+\frac{\gamma}{\sqrt{2\pi mV_q}}+\frac{B_p}{\sqrt{n}}+\frac{B_q}{\sqrt{m}}+2^{-\gamma}. \tag*{(61)} e NS ( n , m ) ≤ ϵ ∗ + 2 2 π e ∣ ln ( m / ( r n )) ∣ + 2 π m V q γ + n B p + m B q + 2 − γ . (61)
To obtain this bound, use Δ ≤ 0 \Delta\le0 Δ ≤ 0 , the maximum normal density, and sup x ∣ x ϕ ( x ) ∣ = 1 / 2 π e \sup_x|x\phi(x)|=1/\sqrt{2\pi e} sup x ∣ x ϕ ( x ) ∣ = 1/ 2 π e to control the change from m V q mV_q m V q to r n V q rnV_q r n V q . For n ≥ 2 n\ge2 n ≥ 2 , taking γ = 1 2 log n \gamma=\frac{1}{2}\log n γ = 2 1 log n gives an explicit O ( log n / n ) O(\log n/\sqrt{n}) O ( log n / n ) error remainder. This gives a rigorous asymptotic error bound, but the constants are coarse for the short blocks considered above. For those blocks, the exact testing curves give sharper certificates.
Exact finite-blocklength BEC-to-BSC conversion
We now derive the exact finite-blocklength formula used for the NS curves in Figure 3 (a). The proof characterizes the feasible NS channels themselves, rather than only comparing joint distributions for a prescribed input law. Let K ∼ Bin ( n , 1 − δ ) K\sim\operatorname{Bin}(n,1-\delta) K ∼ Bin ( n , 1 − δ ) be the number of unerased resource symbols, and define
v j = ∑ i = 0 j ( m i ) , F m , q ( j ) = ∑ i = 0 j ( m i ) q i ( 1 − q ) m − i ( 0 ≤ j ≤ m ) . v_j=\sum_{i=0}^{j}\binom{m}{i},\qquad F_{m,q}(j)=\sum_{i=0}^{j}\binom{m}{i}q^i(1-q)^{m-i}\quad(0\le j\le m). v j = i = 0 ∑ j ( i m ) , F m , q ( j ) = i = 0 ∑ j ( i m ) q i ( 1 − q ) m − i ( 0 ≤ j ≤ m ) .
Proposition E.1 (Exact BEC-to-BSC conversion). For n , m ≥ 1 n,m\ge1 n , m ≥ 1 , 0 ≤ δ ≤ 1 0\le\delta\le1 0 ≤ δ ≤ 1 , and 0 ≤ q ≤ 1 / 2 0\le q\le1/2 0 ≤ q ≤ 1/2 ,
e N S ( n , m ; BEC ( δ ) , BSC ( q ) ) = max 0 ≤ j ≤ m { F m , q ( j ) − E min { 1 , v j 2 K − m } } . (62) e_{\mathrm{NS}}(n,m;\operatorname{BEC}(\delta),\operatorname{BSC}(q))=\max_{0\le j\le m}\left\{F_{m,q}(j)-\mathbb{E}\min\{1,v_j2^{K-m}\}\right\}. \tag*{(62)} e NS ( n , m ; BEC ( δ ) , BSC ( q )) = 0 ≤ j ≤ m max { F m , q ( j ) − E min { 1 , v j 2 K − m } } . (62) The j = m j=m j = m term is zero, so the right side is nonnegative. The proof constructs an explicit NS channel for every feasible noise law, without auxiliary communication.
Proof. Write x ∈ { 0 , 1 } n x \in\{0,1\}^{n} x ∈ { 0 , 1 } n for the resource input, s , z ∈ { 0 , 1 } m s,z \in\{0,1\}^{m} s , z ∈ { 0 , 1 } m for the target input and output, and y ∈ { 0 , 1 , e } n y \in\{0,1,e\}^{n} y ∈ { 0 , 1 , e } n for the resource output. Average an NS channel independently over source bit flips ( x , y ) ↦ ( x ⊕ a , a ⋅ y ) (x,y) \mapsto(x \oplus a,a \cdot y) ( x , y ) ↦ ( x ⊕ a , a ⋅ y ) , with erasures unchanged, and target translations ( s , z ) ↦ ( s ⊕ b , z ⊕ b ) (s,z) \mapsto(s \oplus b,z \oplus b) ( s , z ) ↦ ( s ⊕ b , z ⊕ b ) . The channel laws are covariant under these operations. Averaging therefore preserves the NS constraints and, by convexity, cannot increase the worst-row error. If E E E is the erasure set of y y y and k = n − ∣ E ∣ k=n-|E| k = n − ∣ E ∣ , an averaged channel has the form
N ( x , z ∣ s , y ) = 2 − n Q E ( z ⊕ s ∣ u ) , u = ( y i ⊕ x i ) i ∉ E ∈ { 0 , 1 } k . N(x,z \mid s,y)=2^{-n}Q_{E}(z \oplus s \mid u), \qquad u=(y_i \oplus x_i)_{i\notin E}\in\{0,1\}^{k}. N ( x , z ∣ s , y ) = 2 − n Q E ( z ⊕ s ∣ u ) , u = ( y i ⊕ x i ) i ∈ / E ∈ { 0 , 1 } k .
The two NS constraints are equivalent to
∑ w Q E ( w ∣ u ) = 1 , 2 − k ∑ u Q E ( w ∣ u ) = 2 − m . (63) \sum_{w}Q_{E}(w\mid u)=1,\qquad2^{-k}\sum_{u}Q_{E}(w\mid u)=2^{-m}. \tag*{(63)} w ∑ Q E ( w ∣ u ) = 1 , 2 − k u ∑ Q E ( w ∣ u ) = 2 − m . (63)
The first identity gives the sender marginal 2 − n 2^{-n} 2 − n . To check the second, each visible word u u u occurs for exactly 2 n − k 2^{n-k} 2 n − k choices of x x x , so the receiver marginal is 2 − m 2^{-m} 2 − m . Conversely, the symmetries and NS constraints force both marginals to be uniform, which gives the two identities.
On an actual BEC output, every unerased bit agrees with the input. The induced channel therefore uses only the row R E ( w ) = Q E ( w ∣ 0 k ) R_{E}(w)=Q_{E}(w\mid0^{k}) R E ( w ) = Q E ( w ∣ 0 k ) . Equation (63) requires R E ( w ) ≤ 2 k − m R_{E}(w)\le2^{k-m} R E ( w ) ≤ 2 k − m for every w w w . This pointwise bound is also sufficient: for k ≥ 1 k\ge1 k ≥ 1 , set
Q E ( w ∣ 0 k ) = R E ( w ) , Q E ( w ∣ u ) = 2 k − m − R E ( w ) 2 k − 1 ( u ≠ 0 k ) . (64) Q_{E}(w\mid0^{k})=R_{E}(w),\qquad Q_{E}(w\mid u)=\frac{2^{k-m}-R_{E}(w)}{2^{k}-1}\quad(u\ne0^{k}). \tag*{(64)} Q E ( w ∣ 0 k ) = R E ( w ) , Q E ( w ∣ u ) = 2 k − 1 2 k − m − R E ( w ) ( u = 0 k ) . (64)
Each row is a probability distribution, and their uniform average is uniform on the target alphabet. For k = 0 k=0 k = 0 , the bound forces R E = U m R_{E}=U_{m} R E = U m , so no further rows are needed. Thus every family satisfying the pointwise bounds extends to an NS box on all its inputs. The simulated channel is additive, with noise law
R = ∑ E ⊆ [ n ] δ ∣ E ∣ ( 1 − δ ) n − ∣ E ∣ R E . R=\sum_{E\subseteq[n]}\delta^{|E|}(1-\delta)^{n-|E|}R_{E}. R = E ⊆ [ n ] ∑ δ ∣ E ∣ ( 1 − δ ) n − ∣ E ∣ R E .
Patterns with the same number k k k of visible bits have the same pointwise bound. We may average their rows without changing the noise law. Conversely, we may assign the same row to all such patterns. The feasible noise laws are therefore exactly
R = ∑ k = 0 n λ k R k , λ k = Pr { K = k } , R k ∈ P ( { 0 , 1 } m ) , R k ( w ) ≤ c k : = 2 k − m . (65) R=\sum_{k=0}^{n}\lambda_{k}R_{k},\qquad\lambda_{k}=\Pr\{K=k\},\qquad R_{k}\in\mathcal{P}(\{0,1\}^{m}),\qquad R_{k}(w)\le c_{k}:=2^{k-m}. \tag*{(65)} R = k = 0 ∑ n λ k R k , λ k = Pr { K = k } , R k ∈ P ({ 0 , 1 } m ) , R k ( w ) ≤ c k := 2 k − m . (65)
Every row of the simulated channel has error TV ( R , P ) \operatorname{TV}(R,P) TV ( R , P ) , where P ( w ) = q ∣ w ∣ ( 1 − q ) m − ∣ w ∣ P(w)=q^{|w|}(1-q)^{m-|w|} P ( w ) = q ∣ w ∣ ( 1 − q ) m − ∣ w ∣ . It remains to minimize the total variation distance over these mixtures. For this, use the max-flow/min-cut theorem of Ford–Fulkerson [35 ] . Construct a network with a source, one vertex for each k k k , one vertex for each word w w w , and a sink. The edges from the source to k k k , from k k k to w w w , and from w w w to the sink have capacities λ k \lambda_{k} λ k , λ k c k \lambda_{k}c_{k} λ k c k , and P ( w ) P(w) P ( w ) , respectively. The maximum flow equals the largest attainable overlap ∑ w min ( P ( w ) , R ( w ) ) \sum_{w}\min(P(w),R(w)) ∑ w min ( P ( w ) , R ( w )) in (65) . Indeed, any feasible mixture gives a flow by retaining only its overlap with P P P . Conversely, extend the mass leaving each vertex k k k to a total of λ k \lambda_{k} λ k , without exceeding the capacities of its edges to the word vertices. This is possible because 2 m c k = 2 k ≥ 1 2^{m}c_{k}=2^{k}\ge1 2 m c k = 2 k ≥ 1 . The completed rows give a feasible mixture whose overlap with P P P is at least the original flow.
Fix the set A A A of word vertices on the source side of a cut. Minimizing over the side chosen for each k k k vertex gives the cut capacity
P ( A ) + ∑ k λ k min { 1 , c k ∣ A c ∣ } . P(A)+\sum_{k}\lambda_{k}\min\{1,c_{k}|A^{c}|\}. P ( A ) + k ∑ λ k min { 1 , c k ∣ A c ∣ } .
The max-flow/min-cut theorem therefore proves
min R TV ( P , R ) = max B ⊆ { 0 , 1 } m { P ( B ) − G ( ∣ B ∣ ) } , G ( l ) = ∑ k λ k min { 1 , 2 k − m l } . (66) \min_{R} \operatorname{TV}(P,R)=\max_{B\subseteq\{0,1\}^{m}}\{P(B)-G(|B|)\},\qquad G(l)=\sum_{k}\lambda_k\min\{1,2^{k-m}l\}. \tag*{(66)} R min TV ( P , R ) = B ⊆ { 0 , 1 } m max { P ( B ) − G ( ∣ B ∣ )} , G ( l ) = k ∑ λ k min { 1 , 2 k − m l } . (66)
For a fixed cardinality l l l , the largest value of P ( B ) P(B) P ( B ) is the sum of the l l l largest noise probabilities. When q ≤ 1 / 2 q \le1/2 q ≤ 1/2 , these probabilities are ordered by Hamming weight. Between consecutive shell endpoints v j v_j v j , the sum is affine in the integer l l l , whereas G ( l ) G(l) G ( l ) is concave. Their difference therefore attains its maximum at a shell endpoint, or at l = 0 l=0 l = 0 , where it is zero. At l = v j l=v_j l = v j , the two terms are F m , q ( j ) F_{m,q}(j) F m , q ( j ) and E min { 1 , v j 2 K − m } \mathbb{E}\min\{1,v_j2^{K-m}\} E min { 1 , v j 2 K − m } . This proves (62) .
For numerical evaluation, each expectation in (62) needs only a binomial tail and a truncated exponential moment. With a j = m − ⌊ log 2 v j ⌋ a_j=m-\lfloor\log_2 v_j\rfloor a j = m − ⌊ log 2 v j ⌋ ,
E min { 1 , v j 2 K − m } = Pr { K ≥ a j } + v j 2 − m ∑ k < a j 2 k Pr { K = k } . \mathbb{E}\min\{1,v_j2^{K-m}\}=\Pr\{K\geq a_j\}+v_j2^{-m}\sum_{k<a_j}2^k\Pr\{K=k\}. E min { 1 , v j 2 K − m } = Pr { K ≥ a j } + v j 2 − m k < a j ∑ 2 k Pr { K = k } .
Thus each error evaluation requires only m + 1 m+1 m + 1 testing budgets. Since the error is nondecreasing in m m m , the largest admissible target length can be found by binary search. The script plot_resonances.py reproduces Figure 3 and checks selected NS points by exact rational arithmetic at δ = 435775832558017 / 10 15 \delta=435775832558017/10^{15} δ = 435775832558017/1 0 15 . The exact certificates refer to this rounded rational parameter. The threshold root used for the plot is determined numerically.