Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Appendix A: exact elimination of the auxiliary rates

Proved
QAlgorithms.Papers.Independent.Support50.P26.appendixA_rate_elimination

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

prove2quantum

For any channel, joint auxiliary law, and deterministic map defining a Marton state θ\thetaθ, write a=I(U1;B1)θa=I(U_1;B_1)_\thetaa=I(U1​;B1​)θ​, b=I(U2;B2)θb=I(U_2;B_2)_\thetab=I(U2​;B2​)θ​, and c=I(U1;U2)θc=I(U_1;U_2)_\thetac=I(U1​;U2​)θ​. For every nonnegative rate pair (R1,R2)(R_1,R_2)(R1​,R2​), the existence of real auxiliary rates t1,t2t_1,t_2t1​,t2​ satisfying all seven constraints

R1+R2+c≤t1+t2,2t1+t2≤a+2R1+R2+c,t1≤a,R_1+R_2+c\le t_1+t_2,\quad 2t_1+t_2\le a+2R_1+R_2+c,\quad t_1\le a,R1​+R2​+c≤t1​+t2​,2t1​+t2​≤a+2R1​+R2​+c,t1​≤a, 2t2+t1≤b+2R2+R1+c,t2≤b,R1≤t1,R2≤t22t_2+t_1\le b+2R_2+R_1+c,\quad t_2\le b,\quad R_1\le t_1,\quad R_2\le t_22t2​+t1​≤b+2R2​+R1​+c,t2​≤b,R1​≤t1​,R2​≤t2​

is equivalent to

R1≤a,R2≤b,R1+R2≤a+b−c.R_1\le a,\qquad R_2\le b,\qquad R_1+R_2\le a+b-c.R1​≤a,R2​≤b,R1​+R2​≤a+b−c.

This identifies exactly the projection used in deriving the Marton region and preserves both lower bounds on the eliminated rates.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P26
Formal statement
noncomputable section

open scoped BigOperators Matrix ComplexConjugate ComplexOrder

namespace QAlgorithms.Papers.Independent.Support50.P26

attribute [local instance] Classical.propDecidable Classical.decEq

-- Exact primitives from pinned accepted modules, under the independent-paper override.
-- No coding theorem or other paper's channel model is reused.

open QAlgorithms.Papers.Independent.Information100.P22 (Op quantumMI)

open QAlgorithms.Papers.Independent.Information100.P27 (shannon)

open QAlgorithms.Papers.Independent.Claimed50.P08 (cqBlocks)

open QAlgorithms.Papers.Independent.Dependency50.P47 (Law)

variable {X B1 B2 W U V A B : Type}

variable [Fintype X] [Fintype B1] [Fintype B2] [Fintype W] [Fintype U] [Fintype V]

variable [Fintype A] [Fintype B]

variable [DecidableEq X] [DecidableEq B1] [DecidableEq B2] [DecidableEq W]

variable [DecidableEq U] [DecidableEq V] [DecidableEq A] [DecidableEq B]

/-- Appendix A, PDF pp.14–16: exact projection of the seven constraints for every actual
Marton state and nonnegative target pair. Both auxiliary-rate lower bounds are retained. -/
theorem appendixA_rate_elimination (C : BroadcastChannel X B1 B2) (D : MartonData U V X)
    (r : ℝ × ℝ) (h1 : 0 ≤ r.1) (h2 : 0 ≤ r.2) :
    (∃ t1 t2 : ℝ, auxiliaryRateSystem
      (quantumMI (martonU1B1 C D)) (quantumMI (martonU2B2 C D)) (auxiliaryMI D) r t1 t2) ↔
    r ∈ MartonRegion C D := by sorry

end QAlgorithms.Papers.Independent.Support50.P26

end
Source
Classical codes for quantum broadcast channels, arXiv:1111.3645v4, PDF p. 14, Appendix A: projection of the seven auxiliary-rate inequalities is precisely the Marton region
Read-back

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

Let X,B1,B2,U,VX,B_1,B_2,U,VX,B1​,B2​,U,V be finite index types, with decidable equality where required. Let CCC specify nonempty input and output types and density matrices ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​; let DDD specify a nonnegative, normalized probability mass function ppp on U×VU\times VU×V and a function f:U×V→Xf:U\times V\to Xf:U×V→X. For every real pair (r1,r2)(r_1,r_2)(r1​,r2​) with r1≥0r_1\ge0r1​≥0 and r2≥0r_2\ge0r2​≥0, define

J1=⨁u∑vp(u,v)Tr⁡B2ρf(u,v),J2=⨁v∑up(u,v)Tr⁡B1ρf(u,v),J_1=\bigoplus_u\sum_vp(u,v)\operatorname{Tr}_{B_2}\rho_{f(u,v)},\qquad J_2=\bigoplus_v\sum_up(u,v)\operatorname{Tr}_{B_1}\rho_{f(u,v)},J1​=u⨁​v∑​p(u,v)TrB2​​ρf(u,v)​,J2​=v⨁​u∑​p(u,v)TrB1​​ρf(u,v)​,

and put a=I(J1)a=\mathcal I(J_1)a=I(J1​), b=I(J2)b=\mathcal I(J_2)b=I(J2​), c=H(pU)+H(pV)−H(p)c=H(p_U)+H(p_V)-H(p)c=H(pU​)+H(pV​)−H(p). Here I(J)=S(Tr⁡2J)+S(Tr⁡1J)−S(J)\mathcal I(J)=S(\operatorname{Tr}_2J)+S(\operatorname{Tr}_1J)-S(J)I(J)=S(Tr2​J)+S(Tr1​J)−S(J), H(q)=−∑zq(z)log⁡2q(z)H(q)=-\sum_zq(z)\log_2q(z)H(q)=−∑z​q(z)log2​q(z), and S(A)=−Re⁡Tr⁡(h(A))S(A)=-\operatorname{Re}\operatorname{Tr}(h(A))S(A)=−ReTr(h(A)) uses continuous functional calculus with h(t)=tlog⁡2th(t)=t\log_2th(t)=tlog2​t. The assertion is the equivalence

∃t1,t2∈R:r1+r2+c≤t1+t2,2t1+t2≤a+2r1+r2+c,t1≤a,2t2+t1≤b+2r2+r1+c,t2≤b,r1≤t1,r2≤t2⟺r1≤a,r2≤b,r1+r2≤a+b−c.\begin{gathered} \exists t_1,t_2\in\mathbb R:\quad r_1+r_2+c\le t_1+t_2,\quad 2t_1+t_2\le a+2r_1+r_2+c,\quad t_1\le a,\\ 2t_2+t_1\le b+2r_2+r_1+c,\quad t_2\le b,\quad r_1\le t_1,\quad r_2\le t_2 \end{gathered} \quad\Longleftrightarrow\quad r_1\le a,\quad r_2\le b,\quad r_1+r_2\le a+b-c.∃t1​,t2​∈R:r1​+r2​+c≤t1​+t2​,2t1​+t2​≤a+2r1​+r2​+c,t1​≤a,2t2​+t1​≤b+2r2​+r1​+c,t2​≤b,r1​≤t1​,r2​≤t2​​⟺r1​≤a,r2​≤b,r1​+r2​≤a+b−c.

No additional restrictions on the existential real numbers t1,t2t_1,t_2t1​,t2​ are imposed.

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

    Confirmed by the moderator at approval.

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