Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1: four pure-source coding rates equal entropy

Open
QAlgorithms.Papers.Independent.Intakenext100.P20.pure_source_coding_rates

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let pip_ipi​ be a discrete probability law on an arbitrary label set and let ρi\rho_iρi​ be normalized pure states on a nonzero finite-dimensional complex space. Set ρp=∑ipiρi\rho_p=\sum_i p_i\rho_iρp​=∑i​pi​ρi​. At each positive block length use the independent product probabilities and tensor product states. A blind encoder and decoder are CPTP; a visible encoder maps labels to memory density matrices and has a CPTP decoder. Each memory has a positive finite dimension. Define the ordinary blind and visible rates as the infima of lim sup⁡nn−1log⁡dim⁡Kn\limsup_n n^{-1}\log\dim K_nlimsupn​n−1logdimKn​ over code sequences whose average overlap errors tend to zero. Define their converse rates by replacing error convergence with lim inf⁡nϵn<1\liminf_n\epsilon_n<1liminfn​ϵn​<1. Then

RB=RV=RB−=RV−=H(ρp),H(ρ)=−Tr⁡ρlog⁡ρ.R_B=R_V=R_B^-=R_V^-=H(\rho_p),\qquad H(\rho)=-\operatorname{Tr}\rho\log\rho.RB​=RV​=RB−​=RV−​=H(ρp​),H(ρ)=−Trρlogρ.

All logarithms are natural. Infima and memory-rate limits are in the extended reals; no full-rank or finite-label hypothesis is added.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P20
Formal statement
noncomputable section

open scoped Matrix ENNReal ComplexOrder Topology

namespace QAlgorithms.Papers.Independent.Intakenext100.P20

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

open QAlgorithms.Papers.Independent.Information100.P47 (IsProbability)

open QAlgorithms.Papers.Independent.Information100.P53 (SpectralData)

open QAlgorithms.Papers.Independent.Gap48.P19 (shannonNats)

open QAlgorithms.Papers.Independent.Dependency50.P28 (classicalD)

attribute [local instance] Classical.propDecidable

/-- Theorem 1, PDF p.2, (1): all four pure-source rates equal the entropy
of the computed average. This is a statement of Hayashi's cited known result;
no equivalence with a fixed-error library theorem is assumed as a hypothesis. -/
theorem pure_source_coding_rates {L : Type*} {d : ℕ} (S : DiscretePureSource L d) :
    let H := (QAlgorithms.Papers.Independent.Information100.P56.entropy S.average : EReal)
    blindMinimumRate S false = H ∧
    visibleMinimumRate S false = H ∧
    blindMinimumRate S true = H ∧
    visibleMinimumRate S true = H := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P20

end
Source
Exponents of quantum fixed-length pure state source coding, arXiv:quant-ph/0202002v6, PDF p. 2, Theorem 1, (1)
Read-back

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

For every type LLL, natural number ddd, and source SSS having d>0d>0d>0, nonnegative summable weights (pi)i∈L(p_i)_{i\in L}(pi​)i∈L​ totaling 111, and positive semidefinite trace-one matrices ρi∈Cd×d\rho_i\in\mathbb C^{d\times d}ρi​∈Cd×d each equal to vivi†v_iv_i^\daggervi​vi†​ for some unit vector viv_ivi​, form

ρˉ=∑i∈L′piρi,H=−Re⁡Tr⁡ ⁣[f(ρˉ)],f(x)=xlog⁡x,\bar\rho=\sum'_{i\in L}p_i\rho_i,\qquad H=-\operatorname{Re}\operatorname{Tr}\!\left[f(\bar\rho)\right], \quad f(x)=x\log x,ρˉ​=i∈L∑′​pi​ρi​,H=−ReTr[f(ρˉ​)],f(x)=xlogx,

where f(ρˉ)f(\bar\rho)f(ρˉ​) is defined by continuous functional calculus, log⁡\loglog is the natural logarithm with its total-function value log⁡0=0\log0=0log0=0, and the real number HHH is embedded into the extended reals. The assertion is that all four minimum rates—visible or blind, and with either loss criterion below—equal HHH. More explicitly, at each positive block length n=t+1n=t+1n=t+1, a code has a positive memory dimension mtm_tmt​ and a decoding channel DtD_tDt​; a visible encoder assigns a memory density matrix Et(w)E_t(w)Et​(w) to each w∈Lnw\in L^nw∈Ln, whereas a blind encoder is a channel EtE_tEt​ acting on the input matrix ρw\rho_wρw​, where ρw(x,y)=∏j=0n−1ρwj(xj,yj)\rho_w(x,y)=\prod_{j=0}^{n-1}\rho_{w_j}(x_j,y_j)ρw​(x,y)=∏j=0n−1​ρwj​​(xj​,yj​). Density matrices are positive semidefinite with trace 111, and every channel must admit a finite Kraus representation X↦∑jKjXKj†X\mapsto\sum_jK_jXK_j^\daggerX↦∑j​Kj​XKj†​ satisfying ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. With pw=∏j=0n−1pwjp_w=\prod_{j=0}^{n-1}p_{w_j}pw​=∏j=0n−1​pwj​​, the loss is

ℓt=∑w∈Ln′pw(1−Re⁡Tr⁡[ρ^t,wρw]),\ell_t=\sum'_{w\in L^n}p_w \left(1-\operatorname{Re}\operatorname{Tr}[\widehat\rho_{t,w}\rho_w]\right),ℓt​=w∈Ln∑′​pw​(1−ReTr[ρ​t,w​ρw​]),

where ρ^t,w=Dt(Et(w))\widehat\rho_{t,w}=D_t(E_t(w))ρ​t,w​=Dt​(Et​(w)) for visible codes and ρ^t,w=Dt(Et(ρw))\widehat\rho_{t,w}=D_t(E_t(\rho_w))ρ​t,w​=Dt​(Et​(ρw​)) for blind codes. In each case, the minimum rate means the extended-real infimum of lim sup⁡t→∞log⁡(mt)/(t+1)\limsup_{t\to\infty}\log(m_t)/(t+1)limsupt→∞​log(mt​)/(t+1) over all code sequences satisfying the chosen criterion: either ℓt→0\ell_t\to0ℓt​→0, or extended-real lim inf⁡t→∞ℓt<1\liminf_{t\to\infty}\ell_t<1liminft→∞​ℓt​<1. Each of these four infima equals HHH.

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

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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