Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem II.17: Uniformly for all W,n and (n,lambda) codes: |M|≤(n+1)^a 2^(nC(W)+K(a,d,lambda)sqrt(n)); if constant composition P, |M|≤2^(nI(P;W)+

Open
QAlgorithms.Papers.Independent.Renew46.P43.finiteChannelConverse

by Goku · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let a,d>0a,d>0a,d>0 and 0<λ<10<\lambda<10<λ<1. There is one real constant K=K(a,d,λ)K=K(a,d,\lambda)K=K(a,d,λ) before the normalized finite channel WWW and positive block length nnn. Codes have collective POVMs with optional failure and maximum message error at most λ\lambdaλ; N(n,λ)N(n,\lambda)N(n,λ) is their actual optimal message count. A fixed composition PPP is required only for the explicitly strengthened clause.

∣M∣≤(n+1)a2nC(W)+Kn,∣M∣≤2nI(P;W)+Knif the code has composition P.|M|\le(n+1)^a2^{nC(W)+K\sqrt n},\qquad |M|\le2^{nI(P;W)+K\sqrt n}\quad\text{if the code has composition }P.∣M∣≤(n+1)a2nC(W)+Kn​,∣M∣≤2nI(P;W)+Kn​if the code has composition P.

This is the source result with its stated operational or information-theoretic domain.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P43
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Renew46.P43

open scoped BigOperators Matrix ComplexConjugate ComplexOrder ENNReal Matrix.Norms.L2Operator

open Filter MeasureTheory

open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)

open QAlgorithms.Papers.Independent.Information100.P06 (Below)

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

open QAlgorithms.Papers.Independent.Dependency50.P19 (count both)

open QAlgorithms.Papers.Independent.Information100.P22 (coherentInformation)

attribute [local instance] Classical.propDecidable Classical.decEq

open QAlgorithms.Papers.Independent.Claimed50.P40 (InBlocks)

attribute [local instance] QAlgorithms.Papers.Independent.Renew46.P43.matrixMeasurableSpace

/-- Theorem II.17 and its explicit constant-composition strengthening, PDF p.33.
Composition is required only in the second clause. One K works for both clauses. -/
theorem finiteChannelConverse (a d : ℕ) (ha : 0 < a) (hd : 0 < d)
    (lambda : ℝ) (hlambda : 0 < lambda) (hsmall : lambda < 1) :
    ∃ K : ℝ, ∀ (W : FiniteChannel a (fullAlgebra d hd)) (n : ℕ) (c : FiniteCode W n),
      c.error ≤ lambda →
      (c.messages : ℝ) ≤ (n+1 : ℝ)^a * exp2 (n * W.capacity + K * Real.sqrt n) ∧
      ∀ P : PMF (Fin a), c.Composition P →
        (c.messages : ℝ) ≤ exp2 (n * W.information P + K * Real.sqrt n) := by sorry

end QAlgorithms.Papers.Independent.Renew46.P43

end
Source
Coding Theorems of Quantum Information Theory, arXiv:quant-ph/9907077v1, PDF p. 33, Theorem II.17
Read-back

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

For every pair of positive integers a,da,da,d and every real 0<λ<10<\lambda<10<λ<1, there exists a real constant KKK, with no stated sign restriction, such that the following holds for every family W=(Wx)x<aW=(W_x)_{x<a}W=(Wx​)x<a​ of d×dd\times dd×d positive semidefinite complex matrices of trace 111, every natural number nnn, and every finite code ccc of length nnn for this family. Such a code includes proofs that n>0n>0n>0 and its message count M>0M>0M>0, an encoding w:{0,…,M−1}→{0,…,a−1}nw:\{0,\ldots,M-1\}\to\{0,\ldots,a-1\}^nw:{0,…,M−1}→{0,…,a−1}n, and positive semidefinite measurement matrices (D⊥,D0,…,DM−1)(D_\bot,D_0,\ldots,D_{M-1})(D⊥​,D0​,…,DM−1​) summing to the identity; no injectivity of www is required. If its error

e(c)=max⁡μ<M[1−Re⁡tr⁡ ⁣((⨂t=0n−1Ww(μ)t)Dμ)]e(c)=\max_{\mu<M}\left[1-\operatorname{Re}\operatorname{tr}\!\left( \left(\bigotimes_{t=0}^{n-1}W_{w(\mu)_t}\right)D_\mu\right)\right]e(c)=μ<Mmax​[1−Retr((t=0⨂n−1​Ww(μ)t​​)Dμ​)]

is at most λ\lambdaλ, then

M≤(n+1)a 2 nC(W)+Kn,M\le(n+1)^a\,2^{\,nC(W)+K\sqrt n},M≤(n+1)a2nC(W)+Kn​,

and, for every probability mass function PPP on the input letters whose probabilities px=P(x)p_x=P(x)px​=P(x) satisfy

#{t<n:w(μ)t=x}n=pxfor every message μ and every letter x,\frac{\#\{t<n:w(\mu)_t=x\}}{n}=p_x \quad\text{for every message }\mu\text{ and every letter }x,n#{t<n:w(μ)t​=x}​=px​for every message μ and every letter x,

one also has

M≤2 nIW(P)+Kn.M\le2^{\,nI_W(P)+K\sqrt n}.M≤2nIW​(P)+Kn​.

Here IW(P)=S(∑xpxWx)−∑xpxS(Wx)I_W(P)=S(\sum_xp_xW_x)-\sum_xp_xS(W_x)IW​(P)=S(∑x​px​Wx​)−∑x​px​S(Wx​), C(W)C(W)C(W) is its real supremum over all such PPP, and S(X)=−Re⁡tr⁡[f(X)]S(X)=-\operatorname{Re}\operatorname{tr}[f(X)]S(X)=−Retr[f(X)], with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t interpreted by continuous functional calculus and log⁡20=0\log_2 0=0log2​0=0. The output block label is constant and imposes no additional measurement restriction. The same KKK, chosen before the channel and code, applies to both bounds and every qualifying PPP. Although nnn is quantified over all natural numbers, there is no code of the stipulated type when n=0n=0n=0; the composition condition can likewise be unsatisfiable for a particular P,nP,nP,n.

Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 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