Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 11 lower bounds (B6), (B8)

Open
QAlgorithms.Papers.Independent.Intakenext100.P20.schur_block_lower_bounds

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

prove2quantum

Let d,n≥1d,n\ge1d,n≥1 and let ρ\rhoρ be a normalized density matrix with decreasing spectrum a=(a1,…,ad)a=(a_1,\ldots,a_d)a=(a1​,…,ad​), allowing zeros. For a Young index λ∈Yn\lambda\in Y_nλ∈Yn​, let PλP_\lambdaPλ​ be the orthogonal projector onto its full Schur-Weyl isotypic block and let bλ=λ/nb_\lambda=\lambda/nbλ​=λ/n. Write DDD for extended classical relative entropy, and put cd,n=(n+d)−d(d+1)/2c_{d,n}=(n+d)^{-d(d+1)/2}cd,n​=(n+d)−d(d+1)/2. For every λ\lambdaλ,

cd,nexp⁡[−nD(bλ∥a)]≤Tr⁡(Pλρ⊗n).c_{d,n}\exp[-nD(b_\lambda\Vert a)]\le\operatorname{Tr}(P_\lambda\rho^{\otimes n}).cd,n​exp[−nD(bλ​∥a)]≤Tr(Pλ​ρ⊗n).

For any subset AAA of the probability simplex, let TA={λ∈Yn:bλ∈A}T_A=\{\lambda\in Y_n:b_\lambda\in A\}TA​={λ∈Yn​:bλ​∈A} and DA=inf⁡λ∈TAD(bλ∥a)D_A=\inf_{\lambda\in T_A}D(b_\lambda\Vert a)DA​=infλ∈TA​​D(bλ​∥a). Then

cd,nexp⁡(−nDA)≤∑λ∈TATr⁡(Pλρ⊗n).c_{d,n}\exp(-nD_A)\le\sum_{\lambda\in T_A}\operatorname{Tr}(P_\lambda\rho^{\otimes n}).cd,n​exp(−nDA​)≤λ∈TA​∑​Tr(Pλ​ρ⊗n).

If TAT_ATA​ is nonempty, the finite minimum DAD_ADA​ is attained, including when every value is infinite. If TAT_ATA​ is empty, DA=+∞D_A=+\inftyDA​=+∞ and the left side is zero. Positive empirical mass outside the spectral support also gives a zero exponential. These are precisely the lower clauses (B6), (B8), without the defective upper-bound constants.

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

/-- Lemma 11, PDF p.10: lower bounds (B6), (B8), including attainment of
the finite type minimum when nonempty and zero contribution for an empty event. -/
theorem schur_block_lower_bounds {d n : ℕ} (hd : 0 < d) (hn : 0 < n)
    (rho : {M : Matrix (Fin d) (Fin d) ℂ // IsDensityMatrix M})
    (spectral : SpectralData rho.val) (A : Set (Fin d → ℝ))
    (hA : ∀ b ∈ A, IsProbability b) :
    (∀ shape : Schur.Partition d n,
      lowerPrefactor d n * expNegD n
        ((classicalD (.finite 1 (by norm_num)) (Schur.normalizedRows hd hn shape) spectral.value).toENNReal) ≤ blockMass rho.val shape) ∧
    lowerPrefactor d n * expNegD n (eventD hd hn spectral.value A) ≤
      ∑ shape ∈ eventTypes hd hn A, blockMass rho.val shape ∧
    ((eventTypes hd hn A).Nonempty →
      ∃ shape ∈ eventTypes hd hn A,
        (classicalD (.finite 1 (by norm_num)) (Schur.normalizedRows hd hn shape) spectral.value).toENNReal =
          eventD hd hn spectral.value A) := 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. 10, Lemma 11 lower bounds (B6), (B8)
Read-back

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

For all positive integers d,nd,nd,n, let ρ\rhoρ be a positive semidefinite complex d×dd\times dd×d matrix of trace 111, and suppose spectral data are supplied consisting of a nonincreasing real sequence a0,…,ad−1a_0,\ldots,a_{d-1}a0​,…,ad−1​ and an orthonormal basis v0,…,vd−1v_0,\ldots,v_{d-1}v0​,…,vd−1​ of Cd\mathbb C^dCd such that ρ=∑iaivivi∗\rho=\sum_i a_i v_i v_i^\astρ=∑i​ai​vi​vi∗​. Let A⊆RdA\subseteq\mathbb R^dA⊆Rd be any set whose members have nonnegative coordinates summing to 111. The shapes considered are all Young diagrams λ\lambdaλ with exactly nnn cells and at most ddd rows; write bλ,i=λi/nb_{\lambda,i}=\lambda_i/nbλ,i​=λi​/n, where λi\lambda_iλi​ is the length of row iii, including zero lengths. Define D(b∥a)D(b\Vert a)D(b∥a) as the extended nonnegative value obtained from ∑i:bi>0bilog⁡(bi/ai)\sum_{i:b_i>0}b_i\log(b_i/a_i)∑i:bi​>0​bi​log(bi​/ai​) when every positive bib_ibi​ has positive aia_iai​, and as +∞+\infty+∞ otherwise; the conversion to an extended nonnegative value sends negative values to 000. Here log⁡\loglog is the natural logarithm. Put En(D)=e−nDE_n(D)=e^{-nD}En​(D)=e−nD for finite DDD, and En(+∞)=0E_n(+\infty)=0En​(+∞)=0, and put cd,n=(n+d)−d(d+1)/2c_{d,n}=(n+d)^{-d(d+1)/2}cd,n​=(n+d)−d(d+1)/2. Define the mass mρ(λ)=Re⁡tr⁡(Πλρ⊗n)m_\rho(\lambda)=\operatorname{Re}\operatorname{tr}(\Pi_\lambda\rho^{\otimes n})mρ​(λ)=Retr(Πλ​ρ⊗n), where (ρ⊗n)x,y=∏i=0n−1ρxi,yi(\rho^{\otimes n})_{x,y}=\prod_{i=0}^{n-1}\rho_{x_i,y_i}(ρ⊗n)x,y​=∏i=0n−1​ρxi​,yi​​, and Πλ\Pi_\lambdaΠλ​ is the following explicitly specified matrix. Using the fixed numbering of the cells of λ\lambdaλ by 0,…,n−10,\ldots,n-10,…,n−1, let Rλ,Cλ⊆SnR_\lambda,C_\lambda\subseteq S_nRλ​,Cλ​⊆Sn​ consist respectively of permutations preserving each cell’s row and column, let HλH_\lambdaHλ​ have entries (Hλ)g,h=∑r∈Rλ∑c∈Cλsgn⁡(c)1{g=hrc}(H_\lambda)_{g,h}=\sum_{r\in R_\lambda}\sum_{c\in C_\lambda}\operatorname{sgn}(c)\mathbf1_{\{g=hrc\}}(Hλ​)g,h​=∑r∈Rλ​​∑c∈Cλ​​sgn(c)1{g=hrc}​, let Sλ=range⁡(Hλ)S_\lambda=\operatorname{range}(H_\lambda)Sλ​=range(Hλ​), and let QλQ_\lambdaQλ​ be the orthogonal projector onto this range. With (Lπ)g,h=1{g=πh}(L_\pi)_{g,h}=\mathbf1_{\{g=\pi h\}}(Lπ​)g,h​=1{g=πh}​, χλ(π)=tr⁡(LπQλ)\chi_\lambda(\pi)=\operatorname{tr}(L_\pi Q_\lambda)χλ​(π)=tr(Lπ​Qλ​), and (Tπ)y,x=1{y=x∘π−1}(T_\pi)_{y,x}=\mathbf1_{\{y=x\circ\pi^{-1}\}}(Tπ​)y,x​=1{y=x∘π−1}​, set Πλ=(dim⁡CSλ/n!)∑π∈Snχλ(π−1)Tπ\Pi_\lambda=(\dim_{\mathbb C}S_\lambda/n!)\sum_{\pi\in S_n}\chi_\lambda(\pi^{-1})T_\piΠλ​=(dimC​Sλ​/n!)∑π∈Sn​​χλ​(π−1)Tπ​. Finally, let EA={λ:bλ∈A}\mathcal E_A=\{\lambda:b_\lambda\in A\}EA​={λ:bλ​∈A} and DA=inf⁡λ∈EAD(bλ∥a)D_A=\inf_{\lambda\in\mathcal E_A}D(b_\lambda\Vert a)DA​=infλ∈EA​​D(bλ​∥a), with the infimum taken in [0,+∞][0,+\infty][0,+∞]. The declaration asserts all three conclusions:

∀λ,cd,nEn ⁣(D(bλ∥a))≤mρ(λ),cd,nEn(DA)≤∑λ∈EAmρ(λ),\forall\lambda,\qquad c_{d,n}E_n\!\left(D(b_\lambda\Vert a)\right)\le m_\rho(\lambda), \qquad c_{d,n}E_n(D_A)\le\sum_{\lambda\in\mathcal E_A}m_\rho(\lambda),∀λ,cd,n​En​(D(bλ​∥a))≤mρ​(λ),cd,n​En​(DA​)≤λ∈EA​∑​mρ​(λ),

and, if EA≠∅\mathcal E_A\ne\varnothingEA​=∅, there exists λ∈EA\lambda\in\mathcal E_Aλ∈EA​ with D(bλ∥a)=DAD(b_\lambda\Vert a)=D_AD(bλ​∥a)=DA​. Empty event sets are included: their infimum is +∞+\infty+∞, their mass sum is 000, and the attainment conclusion is conditional on nonemptiness.

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