AFTD Auto-Formalizing Theoretical Domains

uniform_kserver_det_schedule_is_schedule

theoremverified

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.

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

    lines 6–7

      dsimp [uniform_kserver_is_schedule, uniform_kserver_det_schedule]
      refine ⟨by simp, ?_⟩
  2. 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.

    lines 8–12

    uses List.mem_iff_getElem, List.getElem_zip

      intro pair hpair
      rw [List.mem_iff_getElem] at hpair
      rcases hpair with ⟨t, ht, rfl⟩
      rw [List.getElem_zip]
      dsimp
  3. 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 < |ρ|.

    lines 13–16

    uses List.length_zip, lt_of_lt_of_le, min_le_right

      have ht_len : t < ρ.length := by
        have := ht
        rw [List.length_zip] at this
        exact lt_of_lt_of_le this (min_le_right _ _)
  4. 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.

    lines 17–19

    uses List.getElem_map, List.getElem_range, List.take_add_one, List.getElem?_eq_getElem

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

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

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