Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Lemma 10: universal primal upper bound, corrected from its proof

Open
QAlgorithms.Papers.Independent.Intakethird100.P95.lemma10

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

prove2quantum

Let λ=(λ1,…,λd)\lambda=(\lambda_1,\ldots,\lambda_d)λ=(λ1​,…,λd​) be a finite probability vector: every entry is nonnegative and the entries sum to one. Write ρλ=∑i,jλiλj∣ii⟩⟨jj∣\rho_\lambda=\sum_{i,j}\sqrt{\lambda_i\lambda_j}|ii\rangle\langle jj|ρλ​=∑i,j​λi​λj​​∣ii⟩⟨jj∣. All logarithms have base two. A PPT operation is a completely positive, trace-preserving map LLL such that ΓoutLΓin\Gamma_{\rm out}L\Gamma_{\rm in}Γout​LΓin​ is completely positive for arbitrary finite ancillary systems; Γ\GammaΓ transposes Bob in the fixed product basis. Assume in addition that all entries of λ\lambdaλ are strictly positive, so ddd is its Schmidt rank. For K≥2K\ge2K≥2, let T(K;λ)T(K;\lambda)T(K;λ) be the minimum of the Schmidt-coordinate primal SDP (20), defined independently of operational reachability. Its real variables sijs_{ij}sij​ for j≤ij\le ij≤i and aija_{ij}aij​ for j<ij<ij<i obey sij≥λiλj/(K+1)s_{ij}\ge\sqrt{\lambda_i\lambda_j}/(K+1)sij​≥λi​λj​​/(K+1) and aij≥λiλj/(K−1)a_{ij}\ge\sqrt{\lambda_i\lambda_j}/(K-1)aij​≥λi​λj​​/(K−1), and the matrix ∑i≥jsijσijΓ+∑i>jaijαijΓ\sum_{i\ge j}s_{ij}\sigma_{ij}^{\Gamma}+\sum_{i>j}a_{ij}\alpha_{ij}^{\Gamma}∑i≥j​sij​σijΓ​+∑i>j​aij​αijΓ​ is positive semidefinite. The objective is ∑sij+∑aij\sum s_{ij}+\sum a_{ij}∑sij​+∑aij​. Here σii=∣ii⟩⟨ii∣\sigma_{ii}=|ii\rangle\langle ii|σii​=∣ii⟩⟨ii∣, while the off-diagonal symmetric and antisymmetric projectors are (∣ij⟩±∣ji⟩)(⟨ij∣±⟨ji∣)/2(|ij\rangle\pm|ji\rangle)(\langle ij|\pm\langle ji|)/2(∣ij⟩±∣ji⟩)(⟨ij∣±⟨ji∣)/2. For a finite order ttt, StS_tSt​ is the Rényi entropy, with S0S_0S0​ the log support size, S1=−∑iλilog⁡2λiS_1=-\sum_i\lambda_i\log_2\lambda_iS1​=−∑i​λi​log2​λi​ (using 0log⁡20=00\log_2 0=00log2​0=0), and St=(1−t)−1log⁡2∑iλitS_t=(1-t)^{-1}\log_2\sum_i\lambda_i^tSt​=(1−t)−1log2​∑i​λit​ otherwise. The separate infinity order is S∞=−log⁡2max⁡iλiS_\infty=-\log_2\max_i\lambda_iS∞​=−log2​maxi​λi​. The proof-supported universal upper bound is

T(K;λ)≤2S1/2(λ)K−1.T(K;\lambda)\le\frac{2^{S_{1/2}(\lambda)}}{K-1}.T(K;λ)≤K−12S1/2​(λ)​.

This bound controls asymptotic and catalytic preparation costs.

Source correction. Printed equation (25) subtracts one in the numerator. The proof explicitly gives the bound displayed here; the printed stronger bound is false for the allowed scalar spectrum (1)(1)(1).

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P95
Formal statement
noncomputable section

open scoped BigOperators Matrix ComplexOrder

open Filter

namespace QAlgorithms.Papers.Independent.Intakethird100.P95

attribute [local instance] Classical.propDecidable Classical.decEq

-- Exact primitives from the pinned accepted library; no local aliases.

open QAlgorithms.Papers.Independent.Claimed50.P28 (maximallyEntangledDensity)

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

open QAlgorithms.Papers.Independent.Information100.P63 (logTwo)

open QAlgorithms.Papers.Independent.Information100.P19 (outer)

open QAlgorithms.Papers.Independent.Dependency50.P18 (bipartiteTensor)

open QAlgorithms.Papers.Independent.Support50.P11 (Loewner)

/-- PDF p.6, Lemma 10, CORRECTED FROM ITS PROOF. Printed (25) has
(2^{S_{1/2}} - 1)/(K-1); the proof's final sentence gives 2^{S_{1/2}}/(K-1).
The printed stronger bound fails for d=1, lam=(1), where T=1/(K+1)>0. -/
theorem lemma10 {d : ℕ} (K : ℕ) (hK : 2 ≤ K) (lam : Fin d → ℝ)
    (hprob : IsProbability lam) (hpos : ∀ i, 0 < lam i) :
    primalValue K lam ≤ Real.rpow 2 (schmidtRenyi (1 / 2) lam) / ((K : ℝ) - 1) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P95

end
Source
Pure-state transformations and catalysis under operations that completely preserve positivity of partial transpose, arXiv:0801.4322v2, PDF p. 6, Lemma 10: universal primal upper bound, corrected from its proof
Read-back

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

Let d,K∈Nd,K\in\mathbb Nd,K∈N, with K≥2K\ge2K≥2, and let λ=(λi)i=0d−1\lambda=(\lambda_i)_{i=0}^{d-1}λ=(λi​)i=0d−1​ have strictly positive entries summing to one, excluding d=0d=0d=0. Define Sii=∣i,i⟩⟨i,i∣S_{ii}=|i,i\rangle\langle i,i|Sii​=∣i,i⟩⟨i,i∣, Sij=12(∣i,j⟩+∣j,i⟩)(⟨i,j∣+⟨j,i∣)S_{ij}=\tfrac12(|i,j\rangle+|j,i\rangle)(\langle i,j|+\langle j,i|)Sij​=21​(∣i,j⟩+∣j,i⟩)(⟨i,j∣+⟨j,i∣) for j<ij<ij<i, and Aij=12(∣i,j⟩−∣j,i⟩)(⟨i,j∣−⟨j,i∣)A_{ij}=\tfrac12(|i,j\rangle-|j,i\rangle)(\langle i,j|-\langle j,i|)Aij​=21​(∣i,j⟩−∣j,i⟩)(⟨i,j∣−⟨j,i∣) for j<ij<ij<i, and let Γ\GammaΓ transpose the second subsystem. Let pK(λ)p_K(\lambda)pK​(λ) be the real infimum of

∑j≤isij+∑j<iaij\sum_{j\le i}s_{ij}+\sum_{j<i}a_{ij}j≤i∑​sij​+j<i∑​aij​

over real coefficient families satisfying sij≥λiλj/(K+1)s_{ij}\ge\sqrt{\lambda_i\lambda_j}/(K+1)sij​≥λi​λj​​/(K+1), aij≥λiλj/(K−1)a_{ij}\ge\sqrt{\lambda_i\lambda_j}/(K-1)aij​≥λi​λj​​/(K−1), and ∑j≤isijΓSij+∑j<iaijΓAij⪰0\sum_{j\le i}s_{ij}\Gamma S_{ij}+\sum_{j<i}a_{ij}\Gamma A_{ij}\succeq0∑j≤i​sij​ΓSij​+∑j<i​aij​ΓAij​⪰0. Then

pK(λ)≤2 2log⁡2(∑iλi)K−1,p_K(\lambda)\le \frac{2^{\,2\log_2(\sum_i\sqrt{\lambda_i})}}{K-1},pK​(λ)≤K−122log2​(∑i​λi​​)​,

where log⁡2x=log⁡x/log⁡2\log_2x=\log x/\log2log2​x=logx/log2 and the power of 222 is a real power. The denominator is positive under the stated hypothesis; for d=1d=1d=1, all sums over j<ij<ij<i are empty.

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me