Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem A.17: For compatible X1,X2,Y1,Y2, I(Y1:X2Y2|X1)=I(Y2:X1Y1|X2)=0 implies I(X1X2:Y1Y2)≤I(X1:Y1)+I(X2:Y2). For n pairs, H(Yk|all X, other Y

Open
QAlgorithms.Papers.Independent.Renew46.P43.conditionallyIndependentInformation

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

prove2quantum

Fix a normalized ambient state and finite families of intrinsic subalgebras Xk,YkX_k,Y_kXk​,Yk​, whose distinct members commute elementwise. Do not assume a product ambient state. The displayed conditional-entropy equations are the source conditional-independence hypotheses; their two-pair specialization is exactly the two conditional-mutual-information-zero hypotheses.

H(Yk∣X1⋯XnY≠k)=H(Yk∣Xk) ∀k⟹I(X1⋯Xn;Y1⋯Yn)≤∑kI(Xk;Yk).H(Y_k\mid X_1\cdots X_nY_{\ne k})=H(Y_k\mid X_k)\ \forall k\Longrightarrow I(X_1\cdots X_n;Y_1\cdots Y_n)\le\sum_k I(X_k;Y_k).H(Yk​∣X1​⋯Xn​Y=k​)=H(Yk​∣Xk​) ∀k⟹I(X1​⋯Xn​;Y1​⋯Yn​)≤k∑​I(Xk​;Yk​).

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 A.17, PDF pp.73-74, including its n-fold continuation. The conditional
independence equation is exactly H(Y_k|all X,other Y)=H(Y_k|X_k); n=2 gives the
two displayed conditional-mutual-information-zero hypotheses. -/
theorem conditionallyIndependentInformation {n : ℕ} {A : Fin n × Bool → IntrinsicSystem} {C : IntrinsicSystem}
    (E : ∀ i, Embedding (A i) C) (rho : Matrix (Fin C.dim) (Fin C.dim) ℂ)
    (hrho : C.IsState rho) (hcompat : ∀ i j, i ≠ j → CommutingImages (E i).map (E j).map)
    (hindependent : ∀ k : Fin n,
      familyEntropy A (fun i => (E i).map) rho Finset.univ -
        familyEntropy A (fun i => (E i).map) rho (Finset.univ.erase (k,true)) =
      familyEntropy A (fun i => (E i).map) rho {(k,false),(k,true)} -
        familyEntropy A (fun i => (E i).map) rho {(k,false)}) :
    familyEntropy A (fun i => (E i).map) rho (xIndices n) +
      familyEntropy A (fun i => (E i).map) rho (yIndices n) -
      familyEntropy A (fun i => (E i).map) rho Finset.univ ≤
    ∑ k, (familyEntropy A (fun i => (E i).map) rho {(k,false)} +
      familyEntropy A (fun i => (E i).map) rho {(k,true)} -
      familyEntropy A (fun i => (E i).map) rho {(k,false),(k,true)}) := by sorry

end QAlgorithms.Papers.Independent.Renew46.P43

end
Source
Coding Theorems of Quantum Information Theory, arXiv:quant-ph/9907077v1, PDF p. 73, Theorem A.17
Read-back

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

Let n≥0n\ge0n≥0, let AiA_iAi​ for i∈{0,…,n−1}×{false,true}i\in\{0,\ldots,n-1\}\times\{\mathrm{false},\mathrm{true}\}i∈{0,…,n−1}×{false,true}, and let CCC, be systems with positive finite dimensions and a natural-number block label on each basis index. For every iii, let EiE_iEi​ be a complex-linear map from matrices on AiA_iAi​ to matrices on CCC that preserves the identity and block-diagonal matrices, preserves multiplication and adjoints on block-diagonal matrices, and is injective on those matrices; at every finite amplification, including amplification dimension zero, it must also preserve positivity of matrices whose entries vanish between different AiA_iAi​-block labels. Let ρ\rhoρ be positive semidefinite with trace 111, with ρab=0\rho_{ab}=0ρab​=0 whenever the CCC-block labels of a,ba,ba,b differ. Assume the images under Ei,EjE_i,E_jEi​,Ej​ of any block-diagonal matrices commute whenever i≠ji\ne ji=j. For a subset JJJ of the paired index set, define σJ\sigma_JσJ​, indexed by tuples of basis indices of the systems in JJJ, by

(σJ)u,v={tr⁡ ⁣(ρ∏i∈JEi(∣vi⟩⟨ui∣)),if the block labels of ui,vi agree for every i∈J,0,otherwise,(\sigma_J)_{u,v}= \begin{cases} \operatorname{tr}\!\left(\rho\displaystyle\prod_{i\in J}E_i(|v_i\rangle\langle u_i|)\right), &\text{if the block labels of }u_i,v_i\text{ agree for every }i\in J,\\ 0,&\text{otherwise}, \end{cases}(σJ​)u,v​=⎩⎨⎧​tr(ρi∈J∏​Ei​(∣vi​⟩⟨ui​∣)),0,​if the block labels of ui​,vi​ agree for every i∈J,otherwise,​

where the product follows the finite-set enumeration used in the definition. Write HJ=−Re⁡tr⁡[f(σJ)]H_J=-\operatorname{Re}\operatorname{tr}[f(\sigma_J)]HJ​=−Retr[f(σJ​)], where f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t is applied by continuous functional calculus. Let UUU be the whole paired index set, X={(k,false):k<n}X=\{(k,\mathrm{false}):k<n\}X={(k,false):k<n}, and Y={(k,true):k<n}Y=\{(k,\mathrm{true}):k<n\}Y={(k,true):k<n}. If, for every k<nk<nk<n,

HU−HU∖{(k,true)}=H{(k,false),(k,true)}−H{(k,false)},H_U-H_{U\setminus\{(k,\mathrm{true})\}} = H_{\{(k,\mathrm{false}),(k,\mathrm{true})\}}-H_{\{(k,\mathrm{false})\}},HU​−HU∖{(k,true)}​=H{(k,false),(k,true)}​−H{(k,false)}​,

then

HX+HY−HU≤∑k<n(H{(k,false)}+H{(k,true)}−H{(k,false),(k,true)}).H_X+H_Y-H_U \le \sum_{k<n}\left( H_{\{(k,\mathrm{false})\}}+H_{\{(k,\mathrm{true})\}} -H_{\{(k,\mathrm{false}),(k,\mathrm{true})\}} \right).HX​+HY​−HU​≤k<n∑​(H{(k,false)}​+H{(k,true)}​−H{(k,false),(k,true)}​).

The case n=0n=0n=0 is included: the independence assumptions are vacuous, the empty-family matrix is the scalar 111, and the inequality is 0≤00\le00≤0.

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