Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.4 — multilinear weak-design extraction

Open
MatrixQuantumSampler595.Correspondence.Supplement.multilinear_weak_design

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityquantum-informationrandomness-extraction

Let n,λ,ℓ,M,m0≥1n,\lambda,\ell,M,m_0\ge1n,λ,ℓ,M,m0​≥1 be integers with n≤λ2ℓn\le\lambda2^\elln≤λ2ℓ and m0≤λm_0\le\lambdam0​≤λ. Let S1,…,SM⊆[v]S_1,\ldots,S_M\subseteq[v]S1​,…,SM​⊆[v] be an (ℓ,ϱ)(\ell,\varrho)(ℓ,ϱ) weak design, and let real 0≤k≤n0\le k\le n0≤k≤n and η>0\eta>0η>0 satisfy

M22m0(2λϱM−k+ℓ2−λ)≤η.\frac M2\sqrt{2^{m_0}\left(2^{\lambda\varrho M-k}+\ell2^{-\lambda}\right)}\le\eta.2M​2m0​(2λϱM−k+ℓ2−λ)​≤η.

There exists a strong conditional-min-entropy quantum-proof (k,η)(k,\eta)(k,η) extractor

Ext:{0,1}n×{0,1}λ(v+1)⟶{0,1}Mm0.\mathrm{Ext}:\{0,1\}^n\times\{0,1\}^{\lambda(v+1)}\longrightarrow\{0,1\}^{Mm_0}.Ext:{0,1}n×{0,1}λ(v+1)⟶{0,1}Mm0​.

This companion preserves the exact seed/output lengths and the complete error expression for every supplied weak design. The error is not restricted to at most one half. There is no additional polynomial-time assertion in this theorem.

Differences from the source:

  • encoding: binary source, seed and output strings with one-based sample/coordinate labels → Fin-indexed Boolean strings and a uniform Fin(2^d) seed alphabet with zero-based labels; reason: finite relabelling preserves all states, probabilities and maps
Preamble
import Definitions.Def_MatrixQuantumSampler595_Correspondence_Supplement_ConditionalExtractor
import Definitions.Def_MatrixQuantumSampler595_Correspondence_Supplement_UniformConstruction
import Definitions.Def_MatrixQuantumSampler595_Correspondence_Supplement_WeakDesign
Formal statement
namespace MatrixQuantumSampler595.Correspondence.Supplement

/-- Theorem 4.4, p.18. Exact lengths and full hybrid error bound (4.3). -/
theorem multilinear_weak_design
    (n lam ell M m0 v : ℕ) (hn : 1 ≤ n) (hlam : 1 ≤ lam) (hell : 1 ≤ ell)
    (hM : 1 ≤ M) (hm0 : 1 ≤ m0) (hsize : n ≤ lam * 2 ^ ell) (hproj : m0 ≤ lam)
    (rho : ℝ) (S : Fin M → Finset (Fin v)) (hdesign : IsWeakDesign S ell rho)
    (k eta : ℝ) (hk : 0 ≤ k) (hkn : k ≤ n) (heta : 0 < eta)
    (herror : (M : ℝ) / 2 * Real.sqrt ((2 : ℝ) ^ m0 *
      ((2 : ℝ) ^ ((lam : ℝ) * rho * M - k) + (ell : ℝ) * (2 : ℝ) ^ (-(lam : ℝ)))) ≤ eta) :
    ∃ F : BitString n → Fin (2 ^ (lam * (v + 1))) → BitString (M * m0),
      IsStrongConditionalExtractor F k eta := by sorry

end MatrixQuantumSampler595.Correspondence.Supplement
Source
Kuan Cheng, Ruiyang Wu, STOC 2027 submission #595 (October 2026), canonical held PDF (SHA-256 35e315808fa8dd8704a13971c8ca60bc3f785907b566f8914e4bb929c38b26af), Theorem 4.4, printed/PDF p.18; pp.18–20

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