uniform_kserver_det_schedule_is_schedule
For a natural number k, a family of types M indexed by Fin k, an algorithm A : List (∀ i, M i) → (∀ i, M i) satisfying uniform_kserver_det_alg_serves A, and any request sequence ρ : List (∀ i, M i), the schedule uniform_kserver_det_schedule A ρ is a valid schedule for ρ, satisfying uniform_kserver_is_schedule ρ (uniform_kserver_det_schedule A ρ).
Statement
theorem uniform_kserver_det_schedule_is_schedule {k : ℕ} {M : Fin k → Type*} (A : List (∀ i, M i) → (∀ i, M i)) (hA : uniform_kserver_det_alg_serves A) (ρ : List (∀ i, M i)) : uniform_kserver_is_schedule ρ (uniform_kserver_det_schedule A ρ)
- Source
- arXiv:2610.37192 Sec. 6
- Verified
- 31 Oct 2026
- Axioms
Quot.soundpropext- Built on 3
- uniform_kserver_det_alg_servesA deterministic online algorithm A taking a request list to a configuration serves requests if for every list of earlier requests ρ and…
- uniform_kserver_det_scheduleGiven types α and β, a mapping A : List α → β, and an input list ρ : List α, uniform_kserver_det_schedule A ρ is the list of elements of β…
- uniform_kserver_is_scheduleFor a natural number k, a family of spaces M indexed by Fin k, a list of requests ρ, and a list of configurations sched, sched is a valid…
Read back from the Lean
For any natural number k and any family of types M : Fin k → Type*, let A be a function mapping lists of elements in (∀ i, M i) to an element in (∀ i, M i). Assume hA: for every list ρ' and every element r : ∀ i, M i, there exists an index i : Fin k such that (A (ρ' ++ [r])) i = r i. Then, for any list ρ : List (∀ i, M i), the deterministic schedule generated by A on ρ (the list whose t-th element is A (ρ.take (t + 1)) for t from 0 to ρ.length - 1) is a schedule for ρ, meaning: (1) its length equals ρ.length, and (2) for every pair (sched_elem, req_elem) in their zip, there exists an index i : Fin k such that sched_elem i = req_elem i.
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
To show that the deterministic schedule produced by an online algorithm A is valid for a request sequence ρ, we must verify that its length equals |ρ| and that each request ρ[t] is served by the configuration A applied to the prefix up to time t + 1. The length equality is immediate because the schedule is formed by mapping over the indices 0, ..., |ρ| - 1. For each time step t < |ρ|, the prefix of length t + 1 decomposes into the history ρ.take t concatenated with the current request [ρ[t]]. The serving assumption on A then directly guarantees that the configuration at step t agrees with ρ[t] on at least one coordinate.
The theorem reduces to showing that the schedule has length |ρ| and that each request is served by the corresponding configuration in the schedule.
Unfolding the definitions of a valid schedule (uniform_kserver_is_schedule) and the deterministic schedule (uniform_kserver_det_schedule) splits the goal into two conjuncts. The first conjunct, that the schedule has length |ρ|, holds immediately by simplification because the schedule maps over List.range ρ.length, which has length |ρ|. The second conjunct requires that every pair in the zipped schedule and request sequence shares a value at some coordinate i.
dsimp [uniform_kserver_is_schedule, uniform_kserver_det_schedule] refine ⟨by simp, ?_⟩
Any pair in the zipped schedule and request sequence can be written as (schedule[t], ρ[t]) for some index t < |schedule.zip ρ|.
Let pair be an arbitrary element of schedule.zip ρ. By List.mem_iff_getElem, this pair is the t-th element of the zipped list for some valid index t. Rewriting with List.getElem_zip decomposes the pair into (schedule[t], ρ[t]), so it suffices to find a coordinate i where schedule[t] and ρ[t] agree.
uses
List.mem_iff_getElem,List.getElem_zipintro pair hpair rw [List.mem_iff_getElem] at hpair rcases hpair with ⟨t, ht, rfl⟩ rw [List.getElem_zip] dsimp
The index t is strictly less than the length of ρ.
The index t satisfies t < |schedule.zip ρ|. Rewriting the length of the zipped list as min(|schedule|, |ρ|) via List.length_zip and applying min_le_right and lt_of_lt_of_le shows that t < |ρ|.
uses
List.length_zip,lt_of_lt_of_le,min_le_righthave ht_len : t < ρ.length := by have := ht rw [List.length_zip] at this exact lt_of_lt_of_le this (min_le_right _ _)
The t-th configuration in the schedule serves the request ρ[t].
The t-th entry of the schedule simplifies via List.getElem_map and List.getElem_range to A (ρ.take (t + 1)). Using List.take_add_one together with List.getElem?_eq_getElem (justified by t < |ρ|), this prefix decomposes as (ρ.take t) ++ [ρ[t]]. Finally, the serving hypothesis hA applied to history ρ.take t and request ρ[t] guarantees that A serves ρ[t] at some coordinate i, completing the proof.
uses
List.getElem_map,List.getElem_range,List.take_add_one,List.getElem?_eq_getElemsimp only [List.getElem_map, List.getElem_range] rw [List.take_add_one, List.getElem?_eq_getElem ht_len] exact hA (ρ.take t) ρ[t]
List.mem_iff_getElem- An element belongs to a list if and only if it is the element at some valid index strictly less than the list's length.
List.getElem_zip- The i-th element of a zipped list l.zip l' is the pair (l[i], l'[i]).
List.length_zip- The length of l₁.zip l₂ is the minimum of the lengths of l₁ and l₂.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
min_le_right- For any a and b in a linear order, min(a, b) ≤ b.
List.getElem_map- The i-th element of List.map f l is f(l[i]).
List.getElem_range- The j-th element of List.range n is j for any j < n.
List.take_add_one- Taking i + 1 elements from a list yields the first i elements followed by the list representation of the optional element l[i]?.
List.getElem?_eq_getElem- If an index i is strictly less than the length of l, then the optional lookup l[i]? evaluates to some l[i].
- In Lean, decomposing the prefix of length t + 1 into the prefix of length t followed by the single element ρ[t] requires an explicit bound t < |ρ| to convert the optional lookup ρ[t]? into some ρ[t], whereas this decomposition is immediate on paper.
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.
/-- A valid deterministic online algorithm produces a valid schedule on any request sequence. -/theorem uniform_kserver_det_schedule_is_schedule {k : ℕ} {M : Fin k → Type*} (A : List (∀ i, M i) → (∀ i, M i)) (hA : uniform_kserver_det_alg_serves A) (ρ : List (∀ i, M i)) : uniform_kserver_is_schedule ρ (uniform_kserver_det_schedule A ρ) := by dsimp [uniform_kserver_is_schedule, uniform_kserver_det_schedule] refine ⟨by simp, ?_⟩ intro pair hpair rw [List.mem_iff_getElem] at hpair rcases hpair with ⟨t, ht, rfl⟩ rw [List.getElem_zip] dsimp have ht_len : t < ρ.length := by have := ht rw [List.length_zip] at this exact lt_of_lt_of_le this (min_le_right _ _) simp only [List.getElem_map, List.getElem_range] rw [List.take_add_one, List.getElem?_eq_getElem ht_len] exact hA (ρ.take t) ρ[t]