AFTD Auto-Formalizing Theoretical Domains

forward_biased_selector_dominating_and_computable

theoremverifiedformalization

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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.

  1. 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.

    lines 9–14

    uses Finset.length_sort

      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 (· ≤ ·)
  2. 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.

    lines 15–40

    uses isClosed_iInter, isClosed_le, continuous_const, continuous_apply, isClosed_eq, isCompact_stdSimplex, IsCompact.of_isClosed_subset

      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⟩
  3. 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.

    lines 41–62

    uses continuous_apply, isClosed_biInter, isClosed_le, continuous_const, IsCompact.of_isClosed_subset

      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
  4. 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.

    lines 63–110

    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_rfl

      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
  5. 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.

    lines 111–129

    uses dif_pos, le_antisymm, Finset.mem_sort, List.get_eq_getElem

      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]
  6. 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 μ.

    lines 130–192

    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.ext

      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
  7. 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.

    lines 193–214

    uses Set.mem_singleton_iff, forward_biased_selector_output_unique

      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
    
  8. 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.

    lines 215–224

    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.

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

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
See it in the graphDiscuss this resultChallenge it