gen_k_server_uniform_opt_singleton
For k ≥ 1 and configurations a, r : Fin k → Fin m, the offline optimum of the single request r from a is 0 if a i = r i for some i, and 1 otherwise.
Statement
theorem gen_k_server_uniform_opt_singleton {k m : ℕ} (hk : 0 < k) (a r : Fin k → Fin m) : gen_k_server_uniform_opt a [r] = if ∃ i, a i = r i then 0 else 1
- Source
- Sanity check of gen_k_server_uniform_opt (arXiv:2610.37192, Sec. 2): one request costs 0 if the start serves it and 1 otherwise
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- gen_k_server_uniform_optFor a start configuration a : Fin k → Fin m and a request list ρ, OPT is the infimum (sInf in ℕ) of the natural numbers c such that some…
- gen_k_server_uniform_path_costFor a start configuration x : Fin k → Fin m and a list of configurations, the path cost is defined by recursion on the list: 0 for the…
The proof, explained
The theorem is proved by a case split on whether the initial configuration a already serves the single request r (that is, whether a i = r i for some server i). If so, keeping all servers in place incurs a cost of 0, which is optimal since costs are non-negative. If not, moving server 0 to r(0) yields a configuration serving r at distance 1 from a, establishing an upper bound of 1 on the offline optimum. Conversely, any configuration serving r must differ from a, meaning any valid transition incurs a Hamming cost of at least 1; hence the optimum offline cost is exactly 1.
If some server in configuration a already satisfies request r, the stationary schedule [a] serves r with cost 0.
We branch on whether some server of a matches r (line 4). In the positive branch (hypothesis h), remaining at configuration a throughout the single step serves r via List.Forall₂.cons and List.Forall₂.nil. The transition cost from a to a is hammingDist a a = 0 by hammingDist_self, so the total cost of [a] is 0. This demonstrates that 0 belongs to the set of valid path costs.
uses
List.Forall₂.cons,List.Forall₂.nil,hammingDist_selfopen Finset in split_ifs with h · dsimp [gen_k_server_uniform_opt] have h0 : 0 ∈ {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by refine ⟨[a], ?_, ?_⟩ · exact List.Forall₂.cons h List.Forall₂.nil · simp [gen_k_server_uniform_path_cost, hammingDist_self]
In the first case, the offline optimum cost is 0.
Since 0 is an achievable path cost, Nat.sInf_le implies that the infimum of valid path costs is at most 0. Because path costs are non-negative integers, linear arithmetic (omega) concludes that the infimum equals 0.
uses
Nat.sInf_lehave le : sInf {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} ≤ 0 := Nat.sInf_le h0 omega
When no server in a satisfies r, server 0 has a(0) ≠ r(0), and moving server 0 to r(0) produces a configuration y that serves r.
In the negative branch, no coordinate of a matches r (hypothesis h). Since k > 0, the index 0 exists as ⟨0, hk⟩. If server 0 already matched r(0), that would contradict h, so a(0) ≠ r(0). We define the configuration y by modifying a at server 0 to r(0) using Function.update. By Function.update_self, y matches r at index 0, so y serves r.
uses
Function.update_self· dsimp [gen_k_server_uniform_opt] have hne : a ⟨0, hk⟩ ≠ r ⟨0, hk⟩ := by intro heq apply h exact ⟨⟨0, hk⟩, heq⟩ let y := Function.update a ⟨0, hk⟩ (r ⟨0, hk⟩) have hy_serves : ∃ i, y i = r i := by use ⟨0, hk⟩ dsimp [y] rw [Function.update_self]
The Hamming distance between a and y is 1.
By definition, the Hamming distance is the number of indices where a and y differ. By extensionality and case analysis on whether an index i equals 0, the set of indices where a i ≠ y i is proved to be precisely the singleton {⟨0, hk⟩}, using mem_filter, mem_univ, true_and, mem_singleton, and Function.update_self. The cardinality of this singleton set is 1.
uses
mem_filter,mem_univ,true_and,mem_singleton,Function.update_selfhave hy_dist : hammingDist a y = 1 := by dsimp [hammingDist] have heq : (filter (fun i => a i ≠ y i) univ) = {⟨0, hk⟩} := by ext i simp only [mem_filter, mem_univ, true_and, mem_singleton] by_cases hi : i = ⟨0, hk⟩ · subst hi dsimp [y] simp [Function.update_self, hne] · dsimp [y] simp [hi] rw [heq] simp
The offline optimum cost is at most 1.
The single-step schedule [y] serves r because y serves r (via List.Forall₂.cons and List.Forall₂.nil). The cost of moving from a to y is hammingDist a y = 1. Therefore, 1 is an achievable cost, and Nat.sInf_le shows that the infimum of valid path costs is at most 1.
uses
List.Forall₂.cons,List.Forall₂.nil,Nat.sInf_lehave h1 : 1 ∈ {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by refine ⟨[y], ?_, ?_⟩ · exact List.Forall₂.cons hy_serves List.Forall₂.nil · simp [gen_k_server_uniform_path_cost, hy_dist] have hle : sInf {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} ≤ 1 := Nat.sInf_le h1
Any valid schedule has cost at least 1, so the offline optimum cost is 1.
By le_csInf, to show 1 ≤ sInf, it suffices to show that every valid schedule has cost at least 1. Any schedule serving the single request [r] must be a singleton [y'] where y' serves r. Its path cost is hammingDist a y' + 0 = hammingDist a y' by add_zero. If this cost were strictly less than 1, it would be 0, which by eq_of_hammingDist_eq_zero would force a = y'. But then a would serve r, contradicting the assumption h. Thus every valid schedule has cost at least 1. Combined with the upper bound ≤ 1, linear arithmetic (omega) concludes that the optimum cost is 1.
uses
le_csInf,add_zero,eq_of_hammingDist_eq_zerohave hge : 1 ≤ sInf {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by apply le_csInf ⟨1, h1⟩ rintro c ⟨os, hos, rfl⟩ obtain ⟨y', rfl, hy⟩ : ∃ y', os = [y'] ∧ ∃ i, y' i = r i := by cases hos with | cons hy hnil => cases hnil exact ⟨_, rfl, hy⟩ simp only [gen_k_server_uniform_path_cost, add_zero] by_contra! hc have hc0 : hammingDist a y' = 0 := by omega have heq := eq_of_hammingDist_eq_zero hc0 subst heq exact h hy omega
add_zero- adding zero on the right leaves an element unchanged (a + 0 = a)
eq_of_hammingDist_eq_zero- if two configurations have Hamming distance 0, they are identical
Function.update_self- updating a function at an input to a given value yields that value when evaluated at that input
hammingDist_self- the Hamming distance between any configuration and itself is 0
le_csInf- if a set is nonempty and a is a lower bound for the set, then a ≤ sInf s
List.Forall₂.cons- if a relation holds between heads and elementwise between tails, it holds elementwise between the prepended lists
List.Forall₂.nil- the elementwise relation holds trivially between two empty lists
mem_filter- an element belongs to a filtered sub-finset if and only if it belongs to the finset and satisfies the predicate
mem_singleton- an element belongs to a singleton set {a} if and only if it equals a
mem_univ- every element of a finite type belongs to the universal finset `univ`
Nat.sInf_le- the infimum of a set of natural numbers is at most any member of that set
true_and- the conjunction of True and p is logically equivalent to p
- In Step 6, unpacking the fact that the schedule `os` must be a singleton list `[y']` requires explicit case analysis on the inductive definition `List.Forall₂` (lines 50–54), whereas on paper this is immediate because the request sequence has length 1.
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.
theorem gen_k_server_uniform_opt_singleton {k m : ℕ} (hk : 0 < k) (a r : Fin k → Fin m) : gen_k_server_uniform_opt a [r] = if ∃ i, a i = r i then 0 else 1 := by open Finset in split_ifs with h · dsimp [gen_k_server_uniform_opt] have h0 : 0 ∈ {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by refine ⟨[a], ?_, ?_⟩ · exact List.Forall₂.cons h List.Forall₂.nil · simp [gen_k_server_uniform_path_cost, hammingDist_self] have le : sInf {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} ≤ 0 := Nat.sInf_le h0 omega · dsimp [gen_k_server_uniform_opt] have hne : a ⟨0, hk⟩ ≠ r ⟨0, hk⟩ := by intro heq apply h exact ⟨⟨0, hk⟩, heq⟩ let y := Function.update a ⟨0, hk⟩ (r ⟨0, hk⟩) have hy_serves : ∃ i, y i = r i := by use ⟨0, hk⟩ dsimp [y] rw [Function.update_self] have hy_dist : hammingDist a y = 1 := by dsimp [hammingDist] have heq : (filter (fun i => a i ≠ y i) univ) = {⟨0, hk⟩} := by ext i simp only [mem_filter, mem_univ, true_and, mem_singleton] by_cases hi : i = ⟨0, hk⟩ · subst hi dsimp [y] simp [Function.update_self, hne] · dsimp [y] simp [hi] rw [heq] simp have h1 : 1 ∈ {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by refine ⟨[y], ?_, ?_⟩ · exact List.Forall₂.cons hy_serves List.Forall₂.nil · simp [gen_k_server_uniform_path_cost, hy_dist] have hle : sInf {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} ≤ 1 := Nat.sInf_le h1 have hge : 1 ≤ sInf {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by apply le_csInf ⟨1, h1⟩ rintro c ⟨os, hos, rfl⟩ obtain ⟨y', rfl, hy⟩ : ∃ y', os = [y'] ∧ ∃ i, y' i = r i := by cases hos with | cons hy hnil => cases hnil exact ⟨_, rfl, hy⟩ simp only [gen_k_server_uniform_path_cost, add_zero] by_contra! hc have hc0 : hammingDist a y' = 0 := by omega have heq := eq_of_hammingDist_eq_zero hc0 subst heq exact h hy omega