Definition 4.2 — weak designs
DefinitionMatrixQuantumSampler595_Correspondence_Supplement_WeakDesignp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityquantum-informationrandomness-extraction
Let be natural numbers and a real number. An ordered family is an weak design if
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