forward_biased_selector_dominating_and_computable
On every Markov paging instance with n pages, cache C, fault on page s, and hitting probabilities α, assuming the dominating distribution feasible region is nonempty, the forward-biased selector outputs a unique distribution μ that is dominating, is the unique lexicographically largest optimal solution to the forward-biased linear program maximizing μ ((s + 1) mod n), and is computed by the sequence of |C| + 1 linear programs given by coordinate refinement.
Statement
theorem forward_biased_selector_dominating_and_computable
{n : ℕ} (hn : 0 < n) (C : Finset (Fin n)) (s : Fin n)
(α : Fin n → Fin n → ℝ)
(hfeas : ∃ μ, is_dominating_distribution C α μ) :
∃! μ, is_dominating_distribution C α μ ∧
is_forward_biased_selector_output C α ⟨(s.val + 1) % n, Nat.mod_lt _ hn⟩ μ ∧
lp_coord_refine {ν | is_forward_biased_optimal C α ⟨(s.val + 1) % n, Nat.mod_lt _ hn⟩ ν}
(C.sort (· ≤ ·)) C.card = {μ}- Formalizes
- arXiv:2610.40824 Proposition 7
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- is_dominating_distributionA probability distribution μ on Fin n supported on cache C is dominating with respect to pairwise hitting probabilities α if for every…
- is_forward_biased_optimalA distribution μ is an optimal solution to the forward-biased linear program if μ is a dominating distribution supported on cache C and…
- is_forward_biased_selector_outputA distribution μ is the forward-biased selector output for cache C, hitting probabilities α, and target page e if μ is an optimal solution…
- lp_coord_refineGiven a set S of distributions on Fin n and a list of page coordinates L, lp_coord_refine S L m is the subset of distributions obtained…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - forward_biased_selector_output_uniqueFor any cache C, hitting probabilities α, and target page e, if μ₁ and μ₂ both satisfy is_forward_biased_selector_output C α e, then μ₁ =…
Read back from the Lean
Given:
- a positive integer $n$ (hn : 0 < n),
- a subset $C \subseteq \mathrm{Fin}\; n$ (C : Finset (Fin n)),
- a vertex/element $s \in \mathrm{Fin}\; n$,
- a cost/game matrix $\alpha : \mathrm{Fin}\; n \to \mathrm{Fin}\; n \to \mathbb{R}$, and
- an assumption (hfeas) that there exists at least one dominating distribution for $C$ and $\alpha$,
the theorem asserts that there exists a **unique** distribution $\mu : \mathrm{Fin}\; n \to \mathbb{R}$ such that:
1. $\mu$ is a dominating distribution for $C$ and $\alpha$.
2. $\mu$ is the forward-biased selector output for $C$, $\alpha$, and target index $e = (s.\mathrm{val} + 1) \bmod n$ (meaning $\mu$ is forward-biased optimal with respect to $e$, and every other forward-biased optimal distribution $\nu$ satisfies $\nu <_{\mathrm{lex}} \mu$ in the lexicographical order on $\mathrm{Fin}\; n \to \mathbb{R}$).
3. Performing $|C|$ steps of coordinate-wise linear refinement (lp_coord_refine) starting from the set of all forward-biased optimal distributions for $e$, sequentially maximizing each coordinate in $C$ in ascending order (C.sort (· ≤ ·)), produces the singleton set $\{\mu\}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes that the forward-biased selector output is uniquely determined and computed by a sequence of |C| + 1 linear programs. First, it shows that the feasible region of dominating distributions is a nonempty compact set, so maximizing the target page's probability yields a nonempty compact optimal set. Next, by induction on the sorted cache pages, coordinate refinement successively maximizes each cache coordinate, preserving nonemptiness and compactness at each step. Finally, after all |C| cache coordinates are refined, the feasible region collapses to a unique distribution that is lexicographically maximal over the optimal set, matching the forward-biased selector output.
Define the feasible region D of dominating distributions, the optimal set K maximizing coordinate e over D, the sorted list L of cache pages, and the sequence S(m) of refined LP sets, verifying that L has length |C|.
We define D as the set of dominating distributions, K as the subset of D maximizing coordinate e, L as the sorted list of elements in the cache C, and S(m) as the m-th coordinate refinement starting from K. The list L has length equal to the cardinality of C by Finset.length_sort.
uses
Finset.length_sortclassical set D : Set (Fin n → ℝ) := {μ | is_dominating_distribution C α μ} with hD set K : Set (Fin n → ℝ) := {ν | is_forward_biased_optimal C α e ν} with hK set L : List (Fin n) := C.sort (· ≤ ·) with hL set S : ℕ → Set (Fin n → ℝ) := fun m => lp_coord_refine K L m with hS have hLlen : L.length = C.card := by rw [hL]; exact Finset.length_sort (· ≤ ·)
The feasible region D of dominating distributions is compact.
The set D is defined by four systems of linear constraints: nonnegativity, sum to 1, zero values off the cache C, and the domination constraints. Each condition defines a closed set as an intersection of preimages of closed intervals under continuous linear evaluation maps. Their intersection is closed and contained in the standard probability simplex in ℝ^n, which is compact; hence D is compact.
uses
isClosed_iInter,isClosed_le,continuous_const,continuous_apply,isClosed_eq,isCompact_stdSimplex,IsCompact.of_isClosed_subsethave hDcompact : IsCompact D := by rw [hD] have hclosed : IsClosed {μ : Fin n → ℝ | is_dominating_distribution C α μ} := by have h1 : IsClosed {μ : Fin n → ℝ | ∀ p, 0 ≤ μ p} := by rw [show {μ : Fin n → ℝ | ∀ p, 0 ≤ μ p} = ⋂ p, {μ : Fin n → ℝ | 0 ≤ μ p} by ext μ; simp] exact isClosed_iInter (fun p => isClosed_le continuous_const (continuous_apply p)) have h2 : IsClosed {μ : Fin n → ℝ | ∑ p, μ p = 1} := isClosed_eq (by fun_prop) continuous_const have h3 : IsClosed {μ : Fin n → ℝ | ∀ p ∉ C, μ p = 0} := by rw [show {μ : Fin n → ℝ | ∀ p ∉ C, μ p = 0} = ⋂ p, ⋂ (_ : p ∉ C), {μ : Fin n → ℝ | μ p = 0} by ext μ; simp] exact isClosed_iInter (fun p => isClosed_iInter (fun _ => isClosed_eq (continuous_apply p) continuous_const)) have h4 : IsClosed {μ : Fin n → ℝ | ∀ q ∈ C, ∑ p ∈ C, μ p * α p q ≤ 1/2} := by rw [show {μ : Fin n → ℝ | ∀ q ∈ C, ∑ p ∈ C, μ p * α p q ≤ 1/2} = ⋂ q, ⋂ (_ : q ∈ C), {μ : Fin n → ℝ | ∑ p ∈ C, μ p * α p q ≤ 1/2} by ext μ; simp] exact isClosed_iInter (fun q => isClosed_iInter (fun _ => isClosed_le (by fun_prop) continuous_const)) have hDeq : {μ : Fin n → ℝ | is_dominating_distribution C α μ} = {μ : Fin n → ℝ | ∀ p, 0 ≤ μ p} ∩ ({μ : Fin n → ℝ | ∑ p, μ p = 1} ∩ ({μ : Fin n → ℝ | ∀ p ∉ C, μ p = 0} ∩ {μ : Fin n → ℝ | ∀ q ∈ C, ∑ p ∈ C, μ p * α p q ≤ 1/2})) := by ext μ; simp only [Set.mem_inter_iff, Set.mem_setOf_eq, is_dominating_distribution] rw [hDeq] exact h1.inter (h2.inter (h3.inter h4)) refine IsCompact.of_isClosed_subset (isCompact_stdSimplex ℝ (Fin n)) hclosed ?_ intro μ hμ; exact ⟨hμ.1, hμ.2.1⟩
The set K of optimal distributions maximizing coordinate e is nonempty, compact, and a subset of D.
Since D is nonempty by the feasibility hypothesis and compact, the continuous coordinate projection μ ↦ μ(e) attains its maximum on D by the Extreme Value Theorem, so K is nonempty. Furthermore, K is the intersection of D with the closed half-spaces defined by η(e) ≤ ν(e) for all η ∈ D, so K is a closed subset of the compact set D, making K compact.
uses
continuous_apply,isClosed_biInter,isClosed_le,continuous_const,IsCompact.of_isClosed_subsethave hDne : D.Nonempty := by obtain ⟨μ0, hμ0⟩ := hfeas exact ⟨μ0, by rw [hD]; exact hμ0⟩ have hKne : K.Nonempty := by obtain ⟨x, hx, hmax⟩ := hDcompact.exists_isMaxOn hDne (continuous_apply e).continuousOn rw [hK] refine ⟨x, ?_, ?_⟩ · rw [hD] at hx; exact hx · intro ν hν exact hmax (by rw [hD]; exact hν) have hKD : K ⊆ D := by intro x hx; rw [hK] at hx; rw [hD]; exact hx.1 have hKcompact : IsCompact K := by have hKclosed : IsClosed K := by rw [hK] have hKeq : {ν : Fin n → ℝ | is_forward_biased_optimal C α e ν} = D ∩ (⋂ η ∈ D, {ν : Fin n → ℝ | η e ≤ ν e}) := by rw [hD] ext ν; simp only [Set.mem_inter_iff, Set.mem_setOf_eq, Set.mem_iInter, is_forward_biased_optimal] rw [hKeq] exact hDcompact.isClosed.inter (isClosed_biInter fun η _ => isClosed_le continuous_const (continuous_apply e)) exact IsCompact.of_isClosed_subset hDcompact hKclosed hKD
Each coordinate-refined set S(m) for m ≤ |C| is nonempty, compact, and contained in K. In particular, S(|C|) is nonempty, compact, and contained in D.
Each step S(m+1) either retains S(m) or restricts to maximizers of the coordinate L[m] over S(m), making the sequence nested. By induction on m ≤ |C|, each S(m) is nonempty and compact: at step m, because S(m) is compact and coordinate evaluation is continuous, the maximum is achieved, ensuring S(m+1) is nonempty; it is closed in S(m), hence compact. At m = |C|, S(|C|) is nonempty, compact, and a subset of K ⊆ D.
uses
lp_coord_refine,dif_pos,dif_neg,Nat.eq_or_lt_of_le,continuous_apply,isClosed_biInter,isClosed_le,continuous_const,IsCompact.of_isClosed_subset,le_rflhave hstep : ∀ m, S (m+1) = (if h : m < L.length then {μ | μ ∈ S m ∧ ∀ ν ∈ S m, ν (L.get ⟨m,h⟩) ≤ μ (L.get ⟨m,h⟩)} else S m) := by intro m; rw [hS]; simp [lp_coord_refine] have hstep_sub : ∀ m, S (m+1) ⊆ S m := by intro m rw [hstep m] by_cases h : m < L.length · rw [dif_pos h]; intro x hx; exact hx.1 · rw [dif_neg h] have hmono : ∀ {a b : ℕ}, a ≤ b → S b ⊆ S a := by intro a b hab induction b with | zero => have ha0 : a = 0 := Nat.le_zero.mp hab rw [ha0] | succ b ih => rcases Nat.eq_or_lt_of_le hab with h | h · rw [← h] · exact (hstep_sub b).trans (ih (by omega)) have hind : ∀ m ≤ C.card, (S m).Nonempty ∧ IsCompact (S m) ∧ S m ⊆ K := by intro m induction m with | zero => intro _ refine ⟨?_, ?_, ?_⟩ · simpa [hS, lp_coord_refine] using hKne · simpa [hS, lp_coord_refine] using hKcompact · simp [hS, lp_coord_refine] | succ m ih => intro hm have hmL : m < L.length := by omega obtain ⟨hne, hcomp, hsubK⟩ := ih (by omega) refine ⟨?_, ?_, ?_⟩ · obtain ⟨x, hx, hmax⟩ := hcomp.exists_isMaxOn hne (continuous_apply (L.get ⟨m, hmL⟩)).continuousOn refine ⟨x, ?_⟩ rw [hstep m, dif_pos hmL] exact ⟨hx, fun ν hν => hmax hν⟩ · rw [hstep m, dif_pos hmL] have hclosed : IsClosed {μ : Fin n → ℝ | μ ∈ S m ∧ ∀ ν ∈ S m, ν (L.get ⟨m,hmL⟩) ≤ μ (L.get ⟨m,hmL⟩)} := by have heq : {μ : Fin n → ℝ | μ ∈ S m ∧ ∀ ν ∈ S m, ν (L.get ⟨m,hmL⟩) ≤ μ (L.get ⟨m,hmL⟩)} = S m ∩ (⋂ ν ∈ S m, {μ : Fin n → ℝ | ν (L.get ⟨m,hmL⟩) ≤ μ (L.get ⟨m,hmL⟩)}) := by ext μ; simp rw [heq] exact hcomp.isClosed.inter (isClosed_biInter fun ν _ => isClosed_le continuous_const (continuous_apply _)) exact IsCompact.of_isClosed_subset hcomp hclosed (fun x hx => hx.1) · exact (hstep_sub m).trans hsubK obtain ⟨hSkne, hSkcomp, hSkK⟩ := hind C.card le_rfl have hSD : S C.card ⊆ D := hSkK.trans hKD
Any two distributions in S(|C|) are identical.
At each step j < |C|, any two distributions in S(j+1) achieve the maximum on coordinate L[j] over S(j), so by antisymmetry of ≤ their values on L[j] must be equal. Since every cache page p ∈ C appears in the sorted list L, any μ, ν ∈ S(|C|) agree on all cache pages. Outside C, both distributions vanish because S(|C|) ⊆ D. Hence μ = ν everywhere.
uses
dif_pos,le_antisymm,Finset.mem_sort,List.get_eq_getElemhave hkey : ∀ (j : ℕ) (hj : j < L.length) (a b : Fin n → ℝ), a ∈ S (j+1) → b ∈ S (j+1) → a (L.get ⟨j,hj⟩) = b (L.get ⟨j,hj⟩) := by intro j hj a b ha hb have ha' := ha; have hb' := hb rw [hstep j, dif_pos hj] at ha' hb' exact le_antisymm (hb'.2 a ha'.1) (ha'.2 b hb'.1) have hall_eq : ∀ μ ∈ S C.card, ∀ ν ∈ S C.card, μ = ν := by intro μ hμ ν hν funext p by_cases hp : p ∈ C · have hpL : p ∈ L := by rw [hL]; exact (Finset.mem_sort (· ≤ ·)).mpr hp obtain ⟨j, hj, hjeq⟩ := List.mem_iff_getElem.mp hpL have h := hkey j hj μ ν (hmono (by omega : j+1 ≤ C.card) hμ) (hmono (by omega : j+1 ≤ C.card) hν) rw [List.get_eq_getElem] at h rw [hjeq] at h exact h · have hμD : is_dominating_distribution C α μ := by have := hSD hμ; rw [hD] at this; exact this have hνD : is_dominating_distribution C α ν := by have := hSD hν; rw [hD] at this; exact this rw [hμD.2.2.1 p hp, hνD.2.2.1 p hp]
Any distribution μ ∈ S(|C|) is lexicographically maximal over K: for every ν ∈ K, either ν = μ or ν <_lex μ.
If ν ∈ S(|C|), then ν = μ by uniqueness. Otherwise, let m be the smallest index such that ν ∉ S(m+1). Then ν ∈ S(m), but ν fails to maximize coordinate L[m] on S(m), so ν(L[m]) < μ(L[m]). For every coordinate q < L[m]: if q ∈ C, then q = L[j] for some j < m because L is sorted, so ν(q) = μ(q) as both belong to S(j+1); if q ∉ C, both evaluate to 0. Thus ν matches μ on all coordinates strictly prior to L[m] and is strictly smaller at L[m], proving ν <_lex μ.
uses
Or.inl,lp_coord_refine,Nat.eq_zero_or_pos,Nat.sub_add_cancel,Nat.find,Nat.find_spec,Nat.find_min',Nat.find_min,dif_pos,lt_of_lt_of_le,Finset.mem_sort,Finset.pairwise_sort,lt_or_eq_of_le,List.get_eq_getElem,Fin.exthave hlex : ∀ μ ∈ S C.card, ∀ ν ∈ K, ν = μ ∨ Pi.Lex (fun x1 x2 : Fin n => x1 < x2) (fun {i} x1 x2 => x1 < x2) ν μ := by intro μ hμ ν hνK by_cases hνS : ν ∈ S C.card · exact Or.inl (hall_eq ν hνS μ hμ) · right have hνS0 : ν ∈ S 0 := by rw [hS]; simpa [lp_coord_refine] using hνK have hpos : 0 < C.card := by rcases Nat.eq_zero_or_pos C.card with h | h · rw [h] at hνS; exact absurd hνS0 hνS · exact h have hex : ∃ k, ν ∉ S (k+1) := ⟨C.card - 1, by rw [Nat.sub_add_cancel hpos]; exact hνS⟩ set m := Nat.find hex with hmdef have hm_spec : ν ∉ S (m+1) := by rw [hmdef]; exact Nat.find_spec hex have hm_lt : m < C.card := by have h1 : m ≤ C.card - 1 := by rw [hmdef]; exact Nat.find_min' hex (by rw [Nat.sub_add_cancel hpos]; exact hνS) omega have hmL : m < L.length := by omega have hmin : ∀ j, j < m → ν ∈ S (j+1) := by intro j hj have hh := Nat.find_min hex (show j < Nat.find hex by rw [← hmdef]; exact hj) simpa using hh have hνSm : ν ∈ S m := by rcases Nat.eq_zero_or_pos m with h0 | hpos' · rw [h0]; exact hνS0 · have hh := hmin (m-1) (by omega) rwa [Nat.sub_add_cancel hpos'] at hh have hν_not : ¬ (∀ η ∈ S m, η (L.get ⟨m,hmL⟩) ≤ ν (L.get ⟨m,hmL⟩)) := by intro hcon exact hm_spec (by rw [hstep m, dif_pos hmL]; exact ⟨hνSm, hcon⟩) obtain ⟨η, hηS, hνη⟩ : ∃ η, η ∈ S m ∧ ν (L.get ⟨m,hmL⟩) < η (L.get ⟨m,hmL⟩) := by by_contra hc push Not at hc exact hν_not hc have hμS1 : μ ∈ S (m+1) := hmono (by omega : m+1 ≤ C.card) hμ have hμmax : ∀ η ∈ S m, η (L.get ⟨m,hmL⟩) ≤ μ (L.get ⟨m,hmL⟩) := by have := hμS1; rw [hstep m, dif_pos hmL] at this; exact this.2 have hp_lt : ν (L.get ⟨m,hmL⟩) < μ (L.get ⟨m,hmL⟩) := lt_of_lt_of_le hνη (hμmax η hηS) refine ⟨L.get ⟨m,hmL⟩, ?_, hp_lt⟩ intro q hq by_cases hqC : q ∈ C · have hqL : q ∈ L := by rw [hL]; exact (Finset.mem_sort (· ≤ ·)).mpr hqC obtain ⟨j, hj, hjeq⟩ := List.mem_iff_getElem.mp hqL have hjm : j < m := by by_contra hjm push Not at hjm have hpw : List.Pairwise (· ≤ ·) L := by rw [hL]; exact Finset.pairwise_sort C (· ≤ ·) have hle : L.get ⟨m, hmL⟩ ≤ L.get ⟨j, hj⟩ := by rcases lt_or_eq_of_le hjm with hlt | heq · have := (List.pairwise_iff_getElem.mp hpw) m j hmL hj hlt rwa [List.get_eq_getElem, List.get_eq_getElem] · have h1 : (⟨m, hmL⟩ : Fin L.length) = ⟨j, hj⟩ := Fin.ext heq rw [h1] have hleq : L.get ⟨m, hmL⟩ ≤ q := by rw [← hjeq]; exact hle exact absurd hq (not_lt.mpr hleq) have heqj : L.get ⟨j, hj⟩ = q := by rw [List.get_eq_getElem]; exact hjeq have h := hkey j hj ν μ (hmin j hjm) (hmono (by omega : j+1 ≤ C.card) hμ) rw [heqj] at h exact h · have hμD : is_dominating_distribution C α μ := by have := hSD hμ; rw [hD] at this; exact this have hνD : is_dominating_distribution C α ν := by rw [hK] at hνK; exact hνK.1 rw [hμD.2.2.1 q hqC, hνD.2.2.1 q hqC] obtain ⟨μstar, hμstar⟩ := hSkne
There exists a unique distribution μ* satisfying dominating feasibility, selector output optimality, and refinement computation to {μ*}.
Since S(|C|) is nonempty and all its elements are equal, S(|C|) is a singleton {μ*}. The distribution μ* is dominating, belongs to K, and dominates all other ν ∈ K lexicographically, so it is the forward-biased selector output. Uniqueness follows because any other selector output must equal μ* by forward_biased_selector_output_unique.
uses
Set.mem_singleton_iff,forward_biased_selector_output_uniquehave hSk_eq : S C.card = {μstar} := by ext x constructor · intro hx; exact hall_eq x hx μstar hμstar · intro hx rw [Set.mem_singleton_iff] at hx rw [hx]; exact hμstar have hμstarK : μstar ∈ K := hSkK hμstar have hμstarD : is_dominating_distribution C α μstar := by have := hSD hμstar; rw [hD] at this; exact this have hμstar_opt : is_forward_biased_optimal C α e μstar := by rw [hK] at hμstarK; exact hμstarK have hsel : is_forward_biased_selector_output C α e μstar := by refine ⟨hμstar_opt, ?_⟩ intro ν hν exact hlex μstar hμstar ν (by rw [hK]; exact hν) have hrefine : lp_coord_refine {ν | is_forward_biased_optimal C α e ν} (C.sort (· ≤ ·)) C.card = {μstar} := by rw [← hK, ← hL] simpa [hS] using hSk_eq refine ⟨μstar, ⟨hμstarD, hsel, hrefine⟩, ?_⟩ rintro y ⟨hyD, hySel, hyRef⟩ exact forward_biased_selector_output_unique hySel hsel
The main theorem holds by specializing the auxiliary lemma to the target fault coordinate (s + 1) mod n.
Setting e to (s + 1) mod n in the auxiliary lemma forward_biased_selector_dominating_and_computable_aux immediately yields the theorem statement.
uses
forward_biased_selector_dominating_and_computable_aux/-- Proposition 7: The forward-biased selector outputs a dominating distribution computable by at most |C| + 1 linear programs. -/ theorem forward_biased_selector_dominating_and_computable {n : ℕ} (hn : 0 < n) (C : Finset (Fin n)) (s : Fin n) (α : Fin n → Fin n → ℝ) (hfeas : ∃ μ, is_dominating_distribution C α μ) : ∃! μ, is_dominating_distribution C α μ ∧ is_forward_biased_selector_output C α ⟨(s.val + 1) % n, Nat.mod_lt _ hn⟩ μ ∧ lp_coord_refine {ν | is_forward_biased_optimal C α ⟨(s.val + 1) % n, Nat.mod_lt _ hn⟩ ν} (C.sort (· ≤ ·)) C.card = {μ} := by exact forward_biased_selector_dominating_and_computable_aux C ⟨(s.val + 1) % n, Nat.mod_lt _ hn⟩ α hfeas
Finset.length_sort- Sorting a finite set produces a list whose length equals the cardinality of the set.
isClosed_iInter- An arbitrary intersection of closed sets is closed.
isClosed_le- The sublevel set {x | f(x) ≤ g(x)} is closed for continuous functions f and g into an order-closed topology.
continuous_const- A constant function is continuous.
continuous_apply- The coordinate evaluation map p ↦ p i is continuous in the product topology.
isClosed_eq- The set of points where two continuous functions agree is closed in a Hausdorff space.
isCompact_stdSimplex- The standard probability simplex on a finite type in ℝ is compact.
IsCompact.of_isClosed_subset- A closed subset of a compact space is compact.
isClosed_biInter- A bounded intersection of closed sets indexed over a set is closed.
lp_coord_refine- The recursive definition of coordinate refinement for linear programs, which at step m + 1 restricts to maximizers of the m-th coordinate.
dif_pos- Evaluates a dependent if-then-else to its positive branch when the condition holds.
dif_neg- Evaluates a dependent if-then-else to its negative branch when the condition fails.
Nat.eq_or_lt_of_le- For natural numbers, a ≤ b implies a = b or a < b.
le_rfl- The order relation ≤ is reflexive: a ≤ a.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
Finset.mem_sort- An element belongs to the sorted list of a finite set if and only if it belongs to the finite set.
List.get_eq_getElem- Index access via List.get equals bracket indexing List[i].
Or.inl- Proves a disjunction A ∨ B from a proof of A.
Nat.eq_zero_or_pos- Every natural number is either 0 or strictly positive.
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n.
Nat.find- The least natural number satisfying a decidable predicate.
Nat.find_spec- The value returned by Nat.find satisfies the given predicate.
Nat.find_min'- Any witness for the predicate is at least Nat.find.
Nat.find_min- Any natural number strictly smaller than Nat.find does not satisfy the predicate.
lt_of_lt_of_le- Transitivity of strict and non-strict inequality: a < b ≤ c implies a < c.
Finset.pairwise_sort- The sorted list of a finite set is pairwise ordered under the sorting relation.
lt_or_eq_of_le- For a partial order, a ≤ b implies a < b or a = b.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
forward_biased_selector_output_unique- The forward-biased selector output distribution is unique.
forward_biased_selector_dominating_and_computable_aux- Auxiliary lemma establishing that the forward-biased selector output exists, is unique, dominating, and computed by |C| + 1 linear programs for an arbitrary target coordinate e.
- The tactic omega is used at several points to close arithmetic goals regarding list indices and bounds.
- The tactic fun_prop automatically proves continuity of finite sums and linear combinations of evaluation maps.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Set inprivate lemma forward_biased_selector_dominating_and_computable_aux {n : ℕ} (C : Finset (Fin n)) (e : Fin n) (α : Fin n → Fin n → ℝ) (hfeas : ∃ μ, is_dominating_distribution C α μ) : ∃! μ, is_dominating_distribution C α μ ∧ is_forward_biased_selector_output C α e μ ∧ lp_coord_refine {ν | is_forward_biased_optimal C α e ν} (C.sort (· ≤ ·)) C.card = {μ} := by classical set D : Set (Fin n → ℝ) := {μ | is_dominating_distribution C α μ} with hD set K : Set (Fin n → ℝ) := {ν | is_forward_biased_optimal C α e ν} with hK set L : List (Fin n) := C.sort (· ≤ ·) with hL set S : ℕ → Set (Fin n → ℝ) := fun m => lp_coord_refine K L m with hS have hLlen : L.length = C.card := by rw [hL]; exact Finset.length_sort (· ≤ ·) have hDcompact : IsCompact D := by rw [hD] have hclosed : IsClosed {μ : Fin n → ℝ | is_dominating_distribution C α μ} := by have h1 : IsClosed {μ : Fin n → ℝ | ∀ p, 0 ≤ μ p} := by rw [show {μ : Fin n → ℝ | ∀ p, 0 ≤ μ p} = ⋂ p, {μ : Fin n → ℝ | 0 ≤ μ p} by ext μ; simp] exact isClosed_iInter (fun p => isClosed_le continuous_const (continuous_apply p)) have h2 : IsClosed {μ : Fin n → ℝ | ∑ p, μ p = 1} := isClosed_eq (by fun_prop) continuous_const have h3 : IsClosed {μ : Fin n → ℝ | ∀ p ∉ C, μ p = 0} := by rw [show {μ : Fin n → ℝ | ∀ p ∉ C, μ p = 0} = ⋂ p, ⋂ (_ : p ∉ C), {μ : Fin n → ℝ | μ p = 0} by ext μ; simp] exact isClosed_iInter (fun p => isClosed_iInter (fun _ => isClosed_eq (continuous_apply p) continuous_const)) have h4 : IsClosed {μ : Fin n → ℝ | ∀ q ∈ C, ∑ p ∈ C, μ p * α p q ≤ 1/2} := by rw [show {μ : Fin n → ℝ | ∀ q ∈ C, ∑ p ∈ C, μ p * α p q ≤ 1/2} = ⋂ q, ⋂ (_ : q ∈ C), {μ : Fin n → ℝ | ∑ p ∈ C, μ p * α p q ≤ 1/2} by ext μ; simp] exact isClosed_iInter (fun q => isClosed_iInter (fun _ => isClosed_le (by fun_prop) continuous_const)) have hDeq : {μ : Fin n → ℝ | is_dominating_distribution C α μ} = {μ : Fin n → ℝ | ∀ p, 0 ≤ μ p} ∩ ({μ : Fin n → ℝ | ∑ p, μ p = 1} ∩ ({μ : Fin n → ℝ | ∀ p ∉ C, μ p = 0} ∩ {μ : Fin n → ℝ | ∀ q ∈ C, ∑ p ∈ C, μ p * α p q ≤ 1/2})) := by ext μ; simp only [Set.mem_inter_iff, Set.mem_setOf_eq, is_dominating_distribution] rw [hDeq] exact h1.inter (h2.inter (h3.inter h4)) refine IsCompact.of_isClosed_subset (isCompact_stdSimplex ℝ (Fin n)) hclosed ?_ intro μ hμ; exact ⟨hμ.1, hμ.2.1⟩ have hDne : D.Nonempty := by obtain ⟨μ0, hμ0⟩ := hfeas exact ⟨μ0, by rw [hD]; exact hμ0⟩ have hKne : K.Nonempty := by obtain ⟨x, hx, hmax⟩ := hDcompact.exists_isMaxOn hDne (continuous_apply e).continuousOn rw [hK] refine ⟨x, ?_, ?_⟩ · rw [hD] at hx; exact hx · intro ν hν exact hmax (by rw [hD]; exact hν) have hKD : K ⊆ D := by intro x hx; rw [hK] at hx; rw [hD]; exact hx.1 have hKcompact : IsCompact K := by have hKclosed : IsClosed K := by rw [hK] have hKeq : {ν : Fin n → ℝ | is_forward_biased_optimal C α e ν} = D ∩ (⋂ η ∈ D, {ν : Fin n → ℝ | η e ≤ ν e}) := by rw [hD] ext ν; simp only [Set.mem_inter_iff, Set.mem_setOf_eq, Set.mem_iInter, is_forward_biased_optimal] rw [hKeq] exact hDcompact.isClosed.inter (isClosed_biInter fun η _ => isClosed_le continuous_const (continuous_apply e)) exact IsCompact.of_isClosed_subset hDcompact hKclosed hKD have hstep : ∀ m, S (m+1) = (if h : m < L.length then {μ | μ ∈ S m ∧ ∀ ν ∈ S m, ν (L.get ⟨m,h⟩) ≤ μ (L.get ⟨m,h⟩)} else S m) := by intro m; rw [hS]; simp [lp_coord_refine] have hstep_sub : ∀ m, S (m+1) ⊆ S m := by intro m rw [hstep m] by_cases h : m < L.length · rw [dif_pos h]; intro x hx; exact hx.1 · rw [dif_neg h] have hmono : ∀ {a b : ℕ}, a ≤ b → S b ⊆ S a := by intro a b hab induction b with | zero => have ha0 : a = 0 := Nat.le_zero.mp hab rw [ha0] | succ b ih => rcases Nat.eq_or_lt_of_le hab with h | h · rw [← h] · exact (hstep_sub b).trans (ih (by omega)) have hind : ∀ m ≤ C.card, (S m).Nonempty ∧ IsCompact (S m) ∧ S m ⊆ K := by intro m induction m with | zero => intro _ refine ⟨?_, ?_, ?_⟩ · simpa [hS, lp_coord_refine] using hKne · simpa [hS, lp_coord_refine] using hKcompact · simp [hS, lp_coord_refine] | succ m ih => intro hm have hmL : m < L.length := by omega obtain ⟨hne, hcomp, hsubK⟩ := ih (by omega) refine ⟨?_, ?_, ?_⟩ · obtain ⟨x, hx, hmax⟩ := hcomp.exists_isMaxOn hne (continuous_apply (L.get ⟨m, hmL⟩)).continuousOn refine ⟨x, ?_⟩ rw [hstep m, dif_pos hmL] exact ⟨hx, fun ν hν => hmax hν⟩ · rw [hstep m, dif_pos hmL] have hclosed : IsClosed {μ : Fin n → ℝ | μ ∈ S m ∧ ∀ ν ∈ S m, ν (L.get ⟨m,hmL⟩) ≤ μ (L.get ⟨m,hmL⟩)} := by have heq : {μ : Fin n → ℝ | μ ∈ S m ∧ ∀ ν ∈ S m, ν (L.get ⟨m,hmL⟩) ≤ μ (L.get ⟨m,hmL⟩)} = S m ∩ (⋂ ν ∈ S m, {μ : Fin n → ℝ | ν (L.get ⟨m,hmL⟩) ≤ μ (L.get ⟨m,hmL⟩)}) := by ext μ; simp rw [heq] exact hcomp.isClosed.inter (isClosed_biInter fun ν _ => isClosed_le continuous_const (continuous_apply _)) exact IsCompact.of_isClosed_subset hcomp hclosed (fun x hx => hx.1) · exact (hstep_sub m).trans hsubK obtain ⟨hSkne, hSkcomp, hSkK⟩ := hind C.card le_rfl have hSD : S C.card ⊆ D := hSkK.trans hKD have hkey : ∀ (j : ℕ) (hj : j < L.length) (a b : Fin n → ℝ), a ∈ S (j+1) → b ∈ S (j+1) → a (L.get ⟨j,hj⟩) = b (L.get ⟨j,hj⟩) := by intro j hj a b ha hb have ha' := ha; have hb' := hb rw [hstep j, dif_pos hj] at ha' hb' exact le_antisymm (hb'.2 a ha'.1) (ha'.2 b hb'.1) have hall_eq : ∀ μ ∈ S C.card, ∀ ν ∈ S C.card, μ = ν := by intro μ hμ ν hν funext p by_cases hp : p ∈ C · have hpL : p ∈ L := by rw [hL]; exact (Finset.mem_sort (· ≤ ·)).mpr hp obtain ⟨j, hj, hjeq⟩ := List.mem_iff_getElem.mp hpL have h := hkey j hj μ ν (hmono (by omega : j+1 ≤ C.card) hμ) (hmono (by omega : j+1 ≤ C.card) hν) rw [List.get_eq_getElem] at h rw [hjeq] at h exact h · have hμD : is_dominating_distribution C α μ := by have := hSD hμ; rw [hD] at this; exact this have hνD : is_dominating_distribution C α ν := by have := hSD hν; rw [hD] at this; exact this rw [hμD.2.2.1 p hp, hνD.2.2.1 p hp] have hlex : ∀ μ ∈ S C.card, ∀ ν ∈ K, ν = μ ∨ Pi.Lex (fun x1 x2 : Fin n => x1 < x2) (fun {i} x1 x2 => x1 < x2) ν μ := by intro μ hμ ν hνK by_cases hνS : ν ∈ S C.card · exact Or.inl (hall_eq ν hνS μ hμ) · right have hνS0 : ν ∈ S 0 := by rw [hS]; simpa [lp_coord_refine] using hνK have hpos : 0 < C.card := by rcases Nat.eq_zero_or_pos C.card with h | h · rw [h] at hνS; exact absurd hνS0 hνS · exact h have hex : ∃ k, ν ∉ S (k+1) := ⟨C.card - 1, by rw [Nat.sub_add_cancel hpos]; exact hνS⟩ set m := Nat.find hex with hmdef have hm_spec : ν ∉ S (m+1) := by rw [hmdef]; exact Nat.find_spec hex have hm_lt : m < C.card := by have h1 : m ≤ C.card - 1 := by rw [hmdef]; exact Nat.find_min' hex (by rw [Nat.sub_add_cancel hpos]; exact hνS) omega have hmL : m < L.length := by omega have hmin : ∀ j, j < m → ν ∈ S (j+1) := by intro j hj have hh := Nat.find_min hex (show j < Nat.find hex by rw [← hmdef]; exact hj) simpa using hh have hνSm : ν ∈ S m := by rcases Nat.eq_zero_or_pos m with h0 | hpos' · rw [h0]; exact hνS0 · have hh := hmin (m-1) (by omega) rwa [Nat.sub_add_cancel hpos'] at hh have hν_not : ¬ (∀ η ∈ S m, η (L.get ⟨m,hmL⟩) ≤ ν (L.get ⟨m,hmL⟩)) := by intro hcon exact hm_spec (by rw [hstep m, dif_pos hmL]; exact ⟨hνSm, hcon⟩) obtain ⟨η, hηS, hνη⟩ : ∃ η, η ∈ S m ∧ ν (L.get ⟨m,hmL⟩) < η (L.get ⟨m,hmL⟩) := by by_contra hc push Not at hc exact hν_not hc have hμS1 : μ ∈ S (m+1) := hmono (by omega : m+1 ≤ C.card) hμ have hμmax : ∀ η ∈ S m, η (L.get ⟨m,hmL⟩) ≤ μ (L.get ⟨m,hmL⟩) := by have := hμS1; rw [hstep m, dif_pos hmL] at this; exact this.2 have hp_lt : ν (L.get ⟨m,hmL⟩) < μ (L.get ⟨m,hmL⟩) := lt_of_lt_of_le hνη (hμmax η hηS) refine ⟨L.get ⟨m,hmL⟩, ?_, hp_lt⟩ intro q hq by_cases hqC : q ∈ C · have hqL : q ∈ L := by rw [hL]; exact (Finset.mem_sort (· ≤ ·)).mpr hqC obtain ⟨j, hj, hjeq⟩ := List.mem_iff_getElem.mp hqL have hjm : j < m := by by_contra hjm push Not at hjm have hpw : List.Pairwise (· ≤ ·) L := by rw [hL]; exact Finset.pairwise_sort C (· ≤ ·) have hle : L.get ⟨m, hmL⟩ ≤ L.get ⟨j, hj⟩ := by rcases lt_or_eq_of_le hjm with hlt | heq · have := (List.pairwise_iff_getElem.mp hpw) m j hmL hj hlt rwa [List.get_eq_getElem, List.get_eq_getElem] · have h1 : (⟨m, hmL⟩ : Fin L.length) = ⟨j, hj⟩ := Fin.ext heq rw [h1] have hleq : L.get ⟨m, hmL⟩ ≤ q := by rw [← hjeq]; exact hle exact absurd hq (not_lt.mpr hleq) have heqj : L.get ⟨j, hj⟩ = q := by rw [List.get_eq_getElem]; exact hjeq have h := hkey j hj ν μ (hmin j hjm) (hmono (by omega : j+1 ≤ C.card) hμ) rw [heqj] at h exact h · have hμD : is_dominating_distribution C α μ := by have := hSD hμ; rw [hD] at this; exact this have hνD : is_dominating_distribution C α ν := by rw [hK] at hνK; exact hνK.1 rw [hμD.2.2.1 q hqC, hνD.2.2.1 q hqC] obtain ⟨μstar, hμstar⟩ := hSkne have hSk_eq : S C.card = {μstar} := by ext x constructor · intro hx; exact hall_eq x hx μstar hμstar · intro hx rw [Set.mem_singleton_iff] at hx rw [hx]; exact hμstar have hμstarK : μstar ∈ K := hSkK hμstar have hμstarD : is_dominating_distribution C α μstar := by have := hSD hμstar; rw [hD] at this; exact this have hμstar_opt : is_forward_biased_optimal C α e μstar := by rw [hK] at hμstarK; exact hμstarK have hsel : is_forward_biased_selector_output C α e μstar := by refine ⟨hμstar_opt, ?_⟩ intro ν hν exact hlex μstar hμstar ν (by rw [hK]; exact hν) have hrefine : lp_coord_refine {ν | is_forward_biased_optimal C α e ν} (C.sort (· ≤ ·)) C.card = {μstar} := by rw [← hK, ← hL] simpa [hS] using hSk_eq refine ⟨μstar, ⟨hμstarD, hsel, hrefine⟩, ?_⟩ rintro y ⟨hyD, hySel, hyRef⟩ exact forward_biased_selector_output_unique hySel hsel/-- Proposition 7: The forward-biased selector outputs a dominating distribution computable by at most |C| + 1 linear programs. -/theorem forward_biased_selector_dominating_and_computable {n : ℕ} (hn : 0 < n) (C : Finset (Fin n)) (s : Fin n) (α : Fin n → Fin n → ℝ) (hfeas : ∃ μ, is_dominating_distribution C α μ) : ∃! μ, is_dominating_distribution C α μ ∧ is_forward_biased_selector_output C α ⟨(s.val + 1) % n, Nat.mod_lt _ hn⟩ μ ∧ lp_coord_refine {ν | is_forward_biased_optimal C α ⟨(s.val + 1) % n, Nat.mod_lt _ hn⟩ ν} (C.sort (· ≤ ·)) C.card = {μ} := by exact forward_biased_selector_dominating_and_computable_aux C ⟨(s.val + 1) % n, Nat.mod_lt _ hn⟩ α hfeas