Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite-block iid channel coding bounds

Open
QAlgorithms.Papers.Independent.Intakethird100.P05.finite_block_coding

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

For a density-output channel x↦ρxx\mapsto\rho_xx↦ρx​ with finite input alphabet and finite-dimensional output space, fix any input law ppp and let σ=∑xp(x)ρx\sigma=\sum_xp(x)\rho_xσ=∑x​p(x)ρx​. Set ρxn=⨂tρxt\rho_{x^n}=\bigotimes_t\rho_{x_t}ρxn​=⨂t​ρxt​​, pn(xn)=∏tp(xt)p^n(x^n)=\prod_tp(x_t)pn(xn)=∏t​p(xt​), and ρˉxn=Eσ⊗n(ρxn)\bar\rho_{x^n}=\mathcal E_{\sigma^{\otimes n}}(\rho_{x^n})ρˉ​xn​=Eσ⊗n​(ρxn​). For real aaa define

δn(a)=∑xnpn(xn)Tr⁡[ρˉxn{ρˉxn−enaσ⊗n≤0}].\delta_n(a)=\sum_{x^n}p^n(x^n)\operatorname{Tr}[\bar\rho_{x^n}\{\bar\rho_{x^n}-e^{na}\sigma^{\otimes n}\le0\}].δn​(a)=xn∑​pn(xn)Tr[ρˉ​xn​{ρˉ​xn​−enaσ⊗n≤0}].

For every integer n≥1n\ge1n≥1, every real aaa, every λ>0\lambda>0λ>0, and every γn>0\gamma_n>0γn​>0, there is one code of Mn≥1M_n\ge1Mn​≥1 distinct words with positive decoder effects summing to at most identity, satisfying

γnγn+δn(a)min⁡{e−nλ,1−δn(a)−γn−2e−nλ}≤e−naMn,\frac{\gamma_n}{\gamma_n+\delta_n(a)}\min\{e^{-n\lambda},1-\delta_n(a)-\gamma_n-2\sqrt{e^{-n\lambda}}\}\le e^{-na}M_n,γn​+δn​(a)γn​​min{e−nλ,1−δn​(a)−γn​−2e−nλ​}≤e−naMn​, Pe(Cn,Xn)≤δn(a)+γn+2e−nλ.P_e(C^n,X^n)\le\delta_n(a)+\gamma_n+2\sqrt{e^{-n\lambda}}.Pe​(Cn,Xn)≤δn​(a)+γn​+2e−nλ​.

Here PeP_ePe​ is uniform-message average error on the original memoryless output states. This is a finite-block estimate; no mutual-information threshold or convergence assumption is required.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P05
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P05

open scoped Matrix ComplexConjugate ComplexOrder BigOperators

open Filter Topology QAlgorithms

open QAlgorithms.Papers.Independent.Information100.P60 (Mat copies)

open QAlgorithms.Papers.Independent.Information100.P07 (positiveProjection)

open QAlgorithms.Papers.Independent.Dependency50.P28 (tr pinch typeI accept)

open QAlgorithms.Papers.Independent.Claimed50.P45 (pinchedTest)

open QAlgorithms.Papers.Independent.Information100.P58 (Distribution)

open QAlgorithms.Papers.Independent.Information100.P27 (average)

open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)

open QAlgorithms.Papers.Independent.Dependency50.P35 (directSum)

open QAlgorithms.Papers.Independent.Renew46.P44 (wordOutput)

attribute [local instance] Classical.propDecidable Classical.decEq

variable {X I : Type} [Fintype X] [DecidableEq X] [Fintype I] [DecidableEq I]

/-- PDF p.5, Theorem 1, (21)–(23), with substitutions (20) on p.4:
for every positive length and gamma, and every lambda > 0, a code satisfies
the two finite-block bounds. No a < I(p) or convergence premise is imposed. -/
theorem finite_block_coding (W : DensityOutputChannel X I) (p : Distribution X)
    (n : ℕ) (hn : 1 ≤ n) (a lambda gamma : ℝ)
    (hlambda : 0 < lambda) (hgamma : 0 < gamma) :
    ∃ C : DistinctWordCode (Fin n → X) (Fin n → I),
      gamma / (gamma + pinchedLowerTail W p n a) *
        min (Real.exp (-(n : ℝ) * lambda))
          (1 - pinchedLowerTail W p n a - gamma -
            2 * Real.sqrt (Real.exp (-(n : ℝ) * lambda))) ≤
        Real.exp (-(n : ℝ) * a) * (C.size : ℝ) ∧
      uniformMessageError (wordOutput W.state (n := n)) C ≤ pinchedLowerTail W p n a + gamma +
        2 * Real.sqrt (Real.exp (-(n : ℝ) * lambda)) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P05

end
Source
A New Proof of the Channel Coding Theorem via Hypothesis Testing in Quantum Information Theory, arXiv:quant-ph/0208139v1, PDF p. 5, Theorem 1, (21)–(23)
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For finite index types X,IX,IX,I with decidable equality, let ρx=W(x)\rho_x=W(x)ρx​=W(x) be positive semidefinite complex matrices of trace 111, and let px≥0p_x\ge0px​≥0 with ∑xpx=1\sum_xp_x=1∑x​px​=1. Fix a natural number n≥1n\ge1n≥1, arbitrary real aaa, and positive reals λ,γ\lambda,\gammaλ,γ. Put ρˉ=∑xpxρx\bar\rho=\sum_xp_x\rho_xρˉ​=∑x​px​ρx​, define ρu(v,w)=∏i=0n−1ρui(vi,wi)\rho_u(v,w)=\prod_{i=0}^{n-1}\rho_{u_i}(v_i,w_i)ρu​(v,w)=∏i=0n−1​ρui​​(vi​,wi​) and ρˉn(v,w)=∏i=0n−1ρˉ(vi,wi)\bar\rho_n(v,w)=\prod_{i=0}^{n-1}\bar\rho(v_i,w_i)ρˉ​n​(v,w)=∏i=0n−1​ρˉ​(vi​,wi​), and let ρ^u=∑ℓPℓρuPℓ\widehat\rho_u=\sum_\ell P_\ell\rho_uP_\ellρ​u​=∑ℓ​Pℓ​ρu​Pℓ​, using the spectral projections of ρˉn\bar\rho_nρˉ​n​ at its distinct eigenvalues. Let P+(A)P_+(A)P+​(A) be the orthogonal projection onto the range of the positive part of AAA, defined by continuous functional calculus, and set

L=∑u∈Xn(∏ipui)Re⁡Tr⁡[ρ^u(1−P+(ρ^u−enaρˉn))].L=\sum_{u\in X^n}\left(\prod_i p_{u_i}\right) \operatorname{Re}\operatorname{Tr} \left[\widehat\rho_u \bigl(\mathbf1-P_+(\widehat\rho_u-e^{na}\bar\rho_n)\bigr)\right].L=u∈Xn∑​(i∏​pui​​)ReTr[ρ​u​(1−P+​(ρ​u​−enaρˉ​n​))].

There exists a code with positive integer size MMM, an injective list of words uj∈Xnu_j\in X^nuj​∈Xn, and positive semidefinite decoding matrices DjD_jDj​ on InI^nIn with 1−∑jDj≥0\mathbf1-\sum_jD_j\ge01−∑j​Dj​≥0, satisfying

γγ+Lmin⁡ ⁣{e−nλ, 1−L−γ−2e−nλ}≤e−naM,1M∑j=0M−1(1−Re⁡Tr⁡(ρujDj))≤L+γ+2e−nλ.\frac{\gamma}{\gamma+L} \min\!\left\{e^{-n\lambda},\,1-L-\gamma-2\sqrt{e^{-n\lambda}}\right\} \le e^{-na}M, \qquad \frac1M\sum_{j=0}^{M-1} \left(1-\operatorname{Re}\operatorname{Tr}(\rho_{u_j}D_j)\right) \le L+\gamma+2\sqrt{e^{-n\lambda}}.γ+Lγ​min{e−nλ,1−L−γ−2e−nλ​}≤e−naM,M1​j=0∑M−1​(1−ReTr(ρuj​​Dj​))≤L+γ+2e−nλ​.

No bound relating aaa to an information quantity is assumed, and the stated size lower bound may be nonpositive.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me