Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Iid pinched information-spectrum lower tail

Open
QAlgorithms.Papers.Independent.Intakethird100.P05.iid_pinched_lower_tail

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

prove2quantum

Let x↦ρxx\mapsto\rho_xx↦ρx​ be a channel from a finite alphabet X\mathcal XX to density operators on a finite-dimensional complex Hilbert space, and let ppp be any input probability law. Write σ=∑xp(x)ρx\sigma=\sum_xp(x)\rho_xσ=∑x​p(x)ρx​, I(p)=H(σ)−∑xp(x)H(ρx)I(p)=H(\sigma)-\sum_xp(x)H(\rho_x)I(p)=H(σ)−∑x​p(x)H(ρx​) in nats, pn(xn)=∏t=1np(xt)p^n(x^n)=\prod_{t=1}^np(x_t)pn(xn)=∏t=1n​p(xt​), and ρxn=⨂t=1nρxt\rho_{x^n}=\bigotimes_{t=1}^n\rho_{x_t}ρxn​=⨂t=1n​ρxt​​. Let ρˉxn=Eσ⊗n(ρxn)\bar\rho_{x^n}=\mathcal E_{\sigma^{\otimes n}}(\rho_{x^n})ρˉ​xn​=Eσ⊗n​(ρxn​), where pinching preserves the full eigenspaces corresponding to distinct eigenvalues. For every real a<I(p)a<I(p)a<I(p),

lim⁡n→∞∑xn∈Xnpn(xn)Tr⁡ ⁣[ρˉxn{ρˉxn−enaσ⊗n≤0}]=0.\lim_{n\to\infty}\sum_{x^n\in\mathcal X^n}p^n(x^n)\operatorname{Tr}\!\left[\bar\rho_{x^n}\{\bar\rho_{x^n}-e^{na}\sigma^{\otimes n}\le0\}\right]=0.n→∞lim​xn∈Xn∑​pn(xn)Tr[ρˉ​xn​{ρˉ​xn​−enaσ⊗n≤0}]=0.

The braces denote the nonpositive spectral projector, including zero eigenvalues. Both occurrences of the output state inside the trace expression are pinched. Singular output states and zero input weights are allowed. This lower-tail limit links iid information to coding.

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.4, Lemma 1, (16): the iid pinched lower tail, including spectral ties,
tends to zero for every real a < I(p). Singular states and zero input weights
are permitted. The quantity is constructed from W and p, not a free sequence. -/
theorem iid_pinched_lower_tail (W : DensityOutputChannel X I) (p : Distribution X)
    (a : ℝ) (ha : a < channelInformationNats W p) :
    Tendsto (fun k : ℕ => pinchedLowerTail W p (k + 1) a) atTop (𝓝 0) := 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. 4, Lemma 1, (16)
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. Set ρˉ=∑xpxρx\bar\rho=\sum_xp_x\rho_xρˉ​=∑x​px​ρx​ and χ=H(ρˉ)−∑xpxH(ρx)\chi=H(\bar\rho)-\sum_xp_xH(\rho_x)χ=H(ρˉ​)−∑x​px​H(ρx​), where H(A)=−Re⁡Tr⁡(f(A))H(A)=-\operatorname{Re}\operatorname{Tr}(f(A))H(A)=−ReTr(f(A)), f(t)=tlog⁡tf(t)=t\log tf(t)=tlogt, using continuous functional calculus and natural logarithms. For n≥1n\ge1n≥1, 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​), p(u)=∏i=0n−1puip(u)=\prod_{i=0}^{n-1}p_{u_i}p(u)=∏i=0n−1​pui​​, 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​). Let ρ^u=∑ℓPℓρuPℓ\widehat\rho_u=\sum_\ell P_\ell\rho_uP_\ellρ​u​=∑ℓ​Pℓ​ρu​Pℓ​, where the sum ranges over the distinct eigenvalues of ρˉn\bar\rho_nρˉ​n​ and PℓP_\ellPℓ​ is its spectral projection at ℓ\ellℓ. For a Hermitian matrix AAA, let P+(A)P_+(A)P+​(A) be the orthogonal projection onto the range of t↦max⁡(t,0)t\mapsto\max(t,0)t↦max(t,0) applied to AAA. For every real a<χa<\chia<χ,

∑u∈Xk+1p(u) Re⁡Tr⁡ ⁣[ρ^u(1−P+(ρ^u−e(k+1)aρˉk+1))]⟶0(k→∞).\sum_{u\in X^{k+1}}p(u)\, \operatorname{Re}\operatorname{Tr}\!\left[ \widehat\rho_u\bigl(\mathbf1-P_+(\widehat\rho_u-e^{(k+1)a}\bar\rho_{k+1})\bigr) \right]\longrightarrow0 \quad(k\to\infty).u∈Xk+1∑​p(u)ReTr[ρ​u​(1−P+​(ρ​u​−e(k+1)aρˉ​k+1​))]⟶0(k→∞).

Zero eigenvalues are excluded from P+P_+P+​, and aaa may be negative.

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