Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definition 4.2 — weak designs

Definition
MatrixQuantumSampler595_Correspondence_Supplement_WeakDesign

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

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

Let v,M,ℓv,M,\ellv,M,ℓ be natural numbers and ϱ\varrhoϱ a real number. An ordered family S1,…,SM⊆[v]S_1,\ldots,S_M\subseteq[v]S1​,…,SM​⊆[v] is an (ℓ,ϱ)(\ell,\varrho)(ℓ,ϱ) weak design if

∣Si∣=ℓand∑j<i2∣Si∩Sj∣≤ϱM(1≤i≤M).|S_i|=\ell\quad\text{and}\quad\sum_{j<i}2^{|S_i\cap S_j|}\le\varrho M\qquad(1\le i\le M).∣Si​∣=ℓandj<i∑​2∣Si​∩Sj​∣≤ϱM(1≤i≤M).

The aggregate overlap budget controls all previous sets in their stated order. This is the design notion used in the multilinear extractor theorem, rather than an individual bound on every pairwise intersection.

Formalization Note Both coordinate and family indices start at zero in Lean. The sum is over the strictly earlier indices; for the first set it is empty.

Definition code
import Mathlib

namespace MatrixQuantumSampler595.Correspondence.Supplement

/-- Definition 4.2 (p.17). No pairwise-intersection bound replaces the ordered sum. -/
def IsWeakDesign {v M : ℕ} (S : Fin M → Finset (Fin v)) (ell : ℕ) (rho : ℝ) : Prop :=
  (∀ i, (S i).card = ell) ∧
  ∀ i, (∑ j ∈ Finset.univ.filter (fun j : Fin M => j < i),
    (2 : ℝ) ^ ((S i ∩ S j).card)) ≤ rho * M

end MatrixQuantumSampler595.Correspondence.Supplement
Source
Kuan Cheng, Ruiyang Wu, STOC 2027 submission #595 (October 2026), canonical held PDF (SHA-256 35e315808fa8dd8704a13971c8ca60bc3f785907b566f8914e4bb929c38b26af), Definition 4.2, p.17

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