lp_coord_refine
Given 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 after m successive linear programming coordinate-maximization steps on L.
Statement
def lp_coord_refine {n : ℕ} (S : Set (Fin n → ℝ)) (L : List (Fin n)) : ℕ → Set (Fin n → ℝ)- Defined in
- arXiv:2610.40824 Proposition 7 proof
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Used by 1
- forward_biased_selector_dominating_and_computableOn every Markov paging instance with n pages, cache C, fault on page s, and hitting probabilities α, assuming the dominating distribution…
Read back from the Lean
A recursive definition of lp_coord_refine, which takes an implicit dimension n : ℕ, a set S : Set (Fin n → ℝ), a list of coordinate indices L : List (Fin n), and a step count m : ℕ, producing a subset of Fin n → ℝ defined by recursion on m:
- At step 0, it returns S.
- At step m + 1:
- If m < L.length, it returns the set of all μ ∈ lp_coord_refine S L m such that for every ν ∈ lp_coord_refine S L m, ν (L[m]) ≤ μ (L[m]) (that is, the points in the previous set that maximize the L[m]-th coordinate over that set).
- If m ≥ L.length, it returns lp_coord_refine S L m unchanged.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Successive coordinate-maximization steps refining feasible set S along page list L. -/ def lp_coord_refine {n : ℕ} (S : Set (Fin n → ℝ)) (L : List (Fin n)) : ℕ → Set (Fin n → ℝ) | 0 => S | m + 1 => if h : m < L.length then { μ ∈ lp_coord_refine S L m | ∀ ν ∈ lp_coord_refine S L m, ν (L.get ⟨m, h⟩) ≤ μ (L.get ⟨m, h⟩) } else lp_coord_refine S L m