Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 9 — one subset rule for an entire chain

Open
LinMatroidSecretary.Online.Supplement.lemma_9

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

matroidsonline-allocationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problemxos-valuations

Let FFF be a finite field, V=FdV=F^dV=Fd, 0≤α≤10\le\alpha\le10≤α≤1, and let ν\nuν be a subspace probability distribution satisfying

EW∼νdim⁡(W∩L)≤(1−α)dim⁡L(L≤V).\mathbb E_{W\sim\nu}\dim(W\cap L)\le(1-\alpha)\dim L\qquad(L\le V).EW∼ν​dim(W∩L)≤(1−α)dimL(L≤V).

Let BBB be an independent bundle of a finite labelled vector family v:E→Vv:E\to Vv:E→V, and put H=⟨B⟩H=\langle B\rangleH=⟨B⟩. For every finite strictly increasing chain L1<⋯<Ls≤VL_1<\cdots<L_s\le VL1​<⋯<Ls​≤V, there exists one randomized rule, depending on the chain and the observed WWW, selecting T⊆BT\subseteq BT⊆B. Its conditional distributions are nonnegative, have mass one, and are supported on bundles with

dim⁡(W+⟨T⟩)=dim⁡W+∣T∣,Pr⁡[b∈T]=α(b∈B).\dim(W+\langle T\rangle)=\dim W+|T|,\qquad\Pr[b\in T]=\alpha\quad(b\in B).dim(W+⟨T⟩)=dimW+∣T∣,Pr[b∈T]=α(b∈B).

For this same rule all the following inequalities hold simultaneously:

Edim⁡((W+⟨T⟩)∩Lj)≤(1−α)dim⁡Lj+αdim⁡(H∩Lj)(1≤j≤s).\mathbb E\dim((W+\langle T\rangle)\cap L_j)\le(1-\alpha)\dim L_j+\alpha\dim(H\cap L_j)\quad(1\le j\le s).Edim((W+⟨T⟩)∩Lj​)≤(1−α)dimLj​+αdim(H∩Lj​)(1≤j≤s).

All expectations include both random choices. This is the chain-compatible form of bundle selection used in the feasibility argument for Lemma 7.

Differences from the source:

  • encoding: an independent set of vectors in a finite-dimensional space over a finite field → a finite labelled family v : E → F^d, independent on the specified finite bundle, and a finitely supported law on subspaces; reason: independence makes the bundle labels injective on vectors; every finite-dimensional space has coordinates, and over a finite field every subspace law has finite support
  • encoding: a chain L1 < ··· < Ls → a strictly increasing map L : Fin s → Submodule F (Fin d → F); reason: zero-based indexing only relabels the same finite chain; the empty chain leaves the complete selection assertion
Preamble
import Mathlib
import Definitions.Def_LinMatroidSecretary_Online_Supplement_BundleLP
Formal statement
namespace LinMatroidSecretary.Online.Supplement

/-- Lemma 9, STOC 2027 #608, PDF p. 27 (printed p. 25). One rule simultaneously
satisfies the bound at every member of the chain, including the empty-chain case. -/
theorem lemma_9 {F : Type} [Field F] [Fintype F] {d : ℕ}
    (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (ν : Dist F d)
    (hν : IsDistOn ν ⊤) (hDim : DimIneqAlpha ν α)
    {E : Type} [Fintype E] [DecidableEq E] (v : E → Fin d → F)
    (B : Finset E) (hB : LinearIndepOn F v (B : Set E))
    (s : ℕ) (L : Fin s → Submodule F (Fin d → F)) (hL : StrictMono L) :
    ∃ ρ : SelectionRule F d E, SelectionValid v ν B ρ ∧
      (∀ b ∈ B, selectionMarginal ν B ρ b = α) ∧
      ∀ j, selectionExpect ν B ρ (fun W T => dimInter (W ⊔ bundleSpan v T) (L j)) ≤
        (1 - α) * (Module.finrank F (L j) : ℝ) + α * dimInter (bundleSpan v B) (L j) := by sorry

end LinMatroidSecretary.Online.Supplement
Source
Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, Jose Soto, Victor Verdugo, The Strong Secretary Conjecture is True for Linear Matroids, STOC 2027 submission #608 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/608.pdf, Lemma 9, PDF p. 27 (printed p. 25)

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