Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Section 7.2: wasting and blocking alone do not suffice

Proved
QAlgorithms.Papers.Independent.Gap20.P07.wastingBlocking_counterexample

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

prove2quantum

There exist positive block lengths NμN_\muNμ​ with Nμ+1/Nμ→∞N_{\mu+1}/N_\mu\to\inftyNμ+1​/Nμ​→∞ and positive errors ϵμ=12Nμ/Nμ+1→0\epsilon_\mu=\tfrac12\sqrt{N_\mu/N_{\mu+1}}\to0ϵμ​=21​Nμ​/Nμ+1​​→0 such that the finite blocking envelope

Δ(n,m)=min⁡{1,inf⁡L finite multisetm≤∑j∈LNj≤n∑j∈Lϵj}\Delta(n,m)=\min\left\{1,\inf_{\substack{L\text{ finite multiset}\\ m\le\sum_{j\in L}N_j\le n}}\sum_{j\in L}\epsilon_j\right\}Δ(n,m)=min⎩⎨⎧​1,L finite multisetm≤∑j∈L​Nj​≤n​inf​j∈L∑​ϵj​⎭⎬⎫​

is monotone under resource wasting and subadditive. The infimum is extended nonnegative; its value for no feasible packing is +∞+\infty+∞, before clipping. Along the specified diagonal blocks Δ(Nμ,Nμ)→0\Delta(N_\mu,N_\mu)\to0Δ(Nμ​,Nμ​)→0, so rate one is sporadically achievable, but the extended supremum of positive rates satisfying the all-sequences definition is zero. Moreover there are positive sequences nν→∞,mνn_\nu\to\infty,m_\nunν​→∞,mν​ for which

mν/nν→0,lim inf⁡νΔ(nν,mν)≥12.m_\nu/n_\nu\to0,\qquad\liminf_\nu\Delta(n_\nu,m_\nu)\ge\tfrac12.mν​/nν​→0,νliminf​Δ(nν​,mν​)≥21​.

This is an abstract error function, not the error of a quantum channel. It shows that wasting and blocking alone do not prove the sporadic-capacity equivalence.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Gap20_P07
Formal statement
noncomputable section

open Filter MeasureTheory

open scoped Topology ENNReal NNReal Matrix ComplexOrder ComplexConjugate

attribute [local instance] Classical.propDecidable

attribute [local instance] Classical.decEq

attribute [local instance] IsStarNormal.instContinuousFunctionalCalculus

namespace QAlgorithms.Papers.Independent.Gap20.P07

open QAlgorithms

open QAlgorithms.RealRegisters (Hilbert)

open QAlgorithms.Papers.Independent.Dependency50.P33
  (State IsTraceClass IsTraceClassChannel traceSize rankOne tensorApply)

open QAlgorithms.Papers.Independent.Frontier30.P14
  (Operation isometryCoeff conjugateKernel)

open QAlgorithms.Papers.Independent.Claimed50.P35
  (stabilizedTraceClassNorm traceClassTensorMap traceClassChannelPower
   transpose transposeBound TraceLinear tracePair MeasurePrepare)

open QAlgorithms.Papers.Independent.Gap48.P29 (fe FiniteCPMap)

/-- PDF p.27, (102)--(103): an abstract clipped blocking envelope, not an error
arising from quantum channels, has sporadic rate one and capacity zero. The
rounding-sensitive bad subsequence is asserted with liminf >=1/2. -/
theorem wastingBlocking_counterexample :
    ∃ (N : ℕ → ℕ+) (epsilon : ℕ → ℝ≥0),
      Tendsto (fun a => (N a : ℕ)) atTop atTop ∧
      Tendsto (fun a => (N (a + 1) : ℝ) / (N a : ℝ)) atTop atTop ∧
      (∀ a, 0 < epsilon a ∧ (epsilon a : ℝ) =
        Real.sqrt ((N a : ℝ) / (N (a + 1) : ℝ)) / 2) ∧
      Tendsto epsilon atTop (𝓝 0) ∧
      ErrorMonotone (blockingEnvelope N epsilon) ∧
      ErrorSubadditive (blockingEnvelope N epsilon) ∧
      Tendsto (fun a => blockingEnvelope N epsilon (N a) (N a)) atTop (𝓝 0) ∧
      Sporadic (blockingEnvelope N epsilon) 1 ∧
      errorCapacity (blockingEnvelope N epsilon) = 0 ∧
      ∃ n m : ℕ → ℕ+, Tendsto (fun a => (n a : ℕ)) atTop atTop ∧
        Tendsto (rateRatio n m) atTop (𝓝 0) ∧
        (1 / 2 : ℝ≥0∞) ≤ Filter.liminf
          (fun a => blockingEnvelope N epsilon (n a) (m a)) atTop := by sorry

end QAlgorithms.Papers.Independent.Gap20.P07

end
Source
Tema Con Variazioni: Quantum Channel Capacity, arXiv:quant-ph/0311037v1, PDF p. 27, Section 7.2: wasting and blocking alone do not suffice
Read-back

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

There exist a sequence of positive integers (Na)a≥0(N_a)_{a\ge0}(Na​)a≥0​ and a sequence of nonnegative real numbers (εa)a≥0(\varepsilon_a)_{a\ge0}(εa​)a≥0​ such that Na→+∞N_a\to+\inftyNa​→+∞, Na+1/Na→+∞N_{a+1}/N_a\to+\inftyNa+1​/Na​→+∞, and, for every aaa, εa>0\varepsilon_a>0εa​>0 and εa=12Na/Na+1\varepsilon_a=\frac12\sqrt{N_a/N_{a+1}}εa​=21​Na​/Na+1​​, with εa→0\varepsilon_a\to0εa​→0. For positive integers n,mn,mn,m, define the extended nonnegative real number

D(n,m)=min⁡{1, inf⁡{∑j∈Lεj:L is a finite list of natural numbers, m≤∑j∈LNj≤n}}.D(n,m)=\min\left\{1,\ \inf\left\{\sum_{j\in L}\varepsilon_j: L\text{ is a finite list of natural numbers},\ m\le\sum_{j\in L}N_j\le n\right\}\right\}.D(n,m)=min⎩⎨⎧​1, inf⎩⎨⎧​j∈L∑​εj​:L is a finite list of natural numbers, m≤j∈L∑​Nj​≤n⎭⎬⎫​⎭⎬⎫​.

List entries may repeat and are counted with multiplicity; the empty list cannot satisfy the constraint because m>0m>0m>0, and an empty feasible set has infimum +∞+\infty+∞, giving D(n,m)=1D(n,m)=1D(n,m)=1. This function satisfies, for all positive integers n,m,k,ℓn,m,k,\elln,m,k,ℓ,

D(n+1,m)≤D(n,m)≤D(n,m+1),D(n+k,m+ℓ)≤D(n,m)+D(k,ℓ).D(n+1,m)\le D(n,m)\le D(n,m+1), \qquad D(n+k,m+\ell)\le D(n,m)+D(k,\ell).D(n+1,m)≤D(n,m)≤D(n,m+1),D(n+k,m+ℓ)≤D(n,m)+D(k,ℓ).

Moreover, D(Na,Na)→0D(N_a,N_a)\to0D(Na​,Na​)→0, and there exist sequences of positive integers (na),(ma)(n_a),(m_a)(na​),(ma​) with na→+∞n_a\to+\inftyna​→+∞, lim sup⁡a(ma/na)=1\limsup_a(m_a/n_a)=1limsupa​(ma​/na​)=1, and D(na,ma)→0D(n_a,m_a)\to0D(na​,ma​)→0, where ratios and their limits are taken in [0,+∞][0,+\infty][0,+∞]. Nevertheless,

sup⁡{max⁡(R,0):R∈R, R>0, for every pair of positive-integer sequences (na),(ma),na→+∞ and lim sup⁡a(ma/na)≤Rimply D(na,ma)→0}=0,\sup\left\{\max(R,0): R\in\mathbb R,\ R>0,\ \begin{array}{l} \text{for every pair of positive-integer sequences }(n_a),(m_a),\\ n_a\to+\infty\text{ and }\limsup_a(m_a/n_a)\le R\\ \text{imply }D(n_a,m_a)\to0 \end{array}\right\}=0,sup⎩⎨⎧​max(R,0):R∈R, R>0, for every pair of positive-integer sequences (na​),(ma​),na​→+∞ and limsupa​(ma​/na​)≤Rimply D(na​,ma​)→0​⎭⎬⎫​=0,

with the supremum taken in [0,+∞][0,+\infty][0,+∞] and hence equal to 000 for an empty set. Finally, there exist positive-integer sequences (na),(ma)(n_a),(m_a)(na​),(ma​) such that na→+∞n_a\to+\inftyna​→+∞, ma/na→0m_a/n_a\to0ma​/na​→0, and lim inf⁡aD(na,ma)≥12\liminf_a D(n_a,m_a)\ge\frac12liminfa​D(na​,ma​)≥21​; no separate requirement that mam_ama​ tend to infinity is imposed.

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