Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem II.16: Uniformly for finite W and positive n: N(n,lambda)≥2^(nC(W)−K(a,d,lambda)sqrt(n)), 0<lambda<1.

Open
QAlgorithms.Papers.Independent.Renew46.P43.finiteChannelCoding

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.

N(n,λ)≥2nC(W)−K(a,d,λ)n.N(n,\lambda)\ge2^{nC(W)-K(a,d,\lambda)\sqrt n}.N(n,λ)≥2nC(W)−K(a,d,λ)n​.

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.16, PDF pp.32-33: finite-block square-root correction, uniformly
over all channels and positive lengths at fixed alphabet and output dimensions. -/
theorem finiteChannelCoding (a d : ℕ) (ha : 0 < a) (hd : 0 < d)
    (lambda : ℝ) (hlambda : 0 < lambda) (hsmall : lambda < 1) :
    ∃ K : ℝ, ∀ W : FiniteChannel a (fullAlgebra d hd), ∀ n : ℕ, 0 < n →
      (finiteN W n lambda : ℝ) ≥ exp2 (n * W.capacity - 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. 32, Theorem II.16
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, that works simultaneously for all families W=(Wx)x∈{0,…,a−1}W=(W_x)_{x\in\{0,\ldots,a-1\}}W=(Wx​)x∈{0,…,a−1}​ of d×dd\times dd×d positive semidefinite complex matrices of trace 111, and all positive integers nnn, such that

NW(n,λ)≥2 nC(W)−Kn.N_W(n,\lambda)\ge 2^{\,nC(W)-K\sqrt n}.NW​(n,λ)≥2nC(W)−Kn​.

Here C(W)C(W)C(W) is the real supremum, over all probability mass functions PPP on the aaa input letters, of

IW(P)=S ⁣(∑xpxWx)−∑xpxS(Wx),px=P(x),I_W(P)=S\!\left(\sum_x p_xW_x\right)-\sum_xp_xS(W_x), \qquad p_x=P(x),IW​(P)=S(x∑​px​Wx​)−x∑​px​S(Wx​),px​=P(x),

where S(X)=−Re⁡tr⁡[f(X)]S(X)=-\operatorname{Re}\operatorname{tr}[f(X)]S(X)=−Retr[f(X)], f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t, using continuous functional calculus and the total convention log⁡20=0\log_2 0=0log2​0=0. The quantity NW(n,λ)N_W(n,\lambda)NW​(n,λ) is the supremum in the natural numbers of the positive message counts MMM for which there exist 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 a measurement (D⊥,D0,…,DM−1)(D_\bot,D_0,\ldots,D_{M-1})(D⊥​,D0​,…,DM−1​), each matrix positive semidefinite and their sum the identity, satisfying

max⁡μ<M[1−Re⁡tr⁡ ⁣((⨂t=0n−1Ww(μ)t)Dμ)]≤λ.\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]\le\lambda.μ<Mmax​[1−Retr((t=0⨂n−1​Ww(μ)t​​)Dμ​)]≤λ.

The outcome ⊥\bot⊥ is an additional measurement outcome. The encoding need not be injective. The specified block label for the output algebra is constant, so its block restrictions impose no additional constraints. A natural-number supremum is 000 for an empty or unbounded set; thus the definition of NWN_WNW​ uses that convention rather than an extended-real supremum. The constant KKK may depend on a,d,λa,d,\lambdaa,d,λ, but is chosen before WWW and nnn.

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