gen_k_server_uniform_log_competitive
For every k ≥ 1, every m and every start configuration a : Fin k → Fin m of generalized k-server on k uniform metrics with m points each (unit distances), there are transition probabilities P with gen_k_server_uniform_is_rand_alg P such that for every finite request list ρ, the expected cost gen_k_server_uniform_expected_cost P a ρ is at most (k + 1) · ln(2k) · gen_k_server_uniform_opt a ρ, with no additive constant.
Statement
theorem gen_k_server_uniform_log_competitive (k m : ℕ) (hk : 1 ≤ k) (a : Fin k → Fin m) :
∃ P, gen_k_server_uniform_is_rand_alg P ∧ ∀ ρ : List (Fin k → Fin m),
gen_k_server_uniform_expected_cost P a ρ ≤
((k : ℝ) + 1) * Real.log (2 * k) * (gen_k_server_uniform_opt a ρ : ℝ)- Formalizes
- arXiv:2610.37192, Theorem 1.1, specialized to k spaces with m points each (the paper allows any uniform spaces, finite or infinite)
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- gen_k_server_uniform_is_rand_algGeneralized k-server where each of the k servers moves in its own copy of the uniform metric on m points: configurations and requests are…
- gen_k_server_uniform_expected_costGeneralized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ…
- 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_expected_cost_fromGeneralized k-server on k uniform metrics with m points each: both configurations and requests are functions Fin k → Fin m (one point per…
- 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…
- weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
Read back from the Lean
The declaration asserts that for any natural numbers k and m with k ≥ 1, and for every initial server configuration a : Fin k → Fin m, there exists a randomized online algorithm P (which may depend on k, m, and a) such that:
1. P is a valid randomized algorithm: for every request history past, current request r : Fin k → Fin m, and current server configuration x : Fin k → Fin m, the function P(past, r, x, ·) defines a probability distribution over next configurations y : Fin k → Fin m (all probabilities are non-negative and sum to 1), and every configuration y with non-zero probability satisfies the request r (there exists some coordinate i : Fin k such that y i = r i).
2. For every sequence of requests ρ : List (Fin k → Fin m), the expected total Hamming distance moved by P starting from configuration a on request sequence ρ is at most ((k : ℝ) + 1) * ln(2k) times the offline optimal cost of serving ρ starting from a (where the optimal cost is the minimum over all sequences of configurations os of length |ρ| satisfying each request at the corresponding step, of the total Hamming distance path cost starting from a).
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 designs an online randomized algorithm for generalized k-server on uniform metrics using a multiplicative weights update. At each step, if a server configuration does not serve the request, its weight decreases and transitions to one of k repairs, with additional probability mass coming from the overall weight decrease. A potential function argument compares the algorithm's expected cost (bounded by the log-ratio of total weights) with the offline optimum (which lower-bounds the final total weight), yielding an O(k log k) competitive ratio.
The main theorem and all helper lemmas hold.
We verify all steps from weight kernel properties to the competitive ratio bound.
unfold gen_k_server_log_K split_ifs · norm_num · norm_num · apply mul_nonneg (by positivity) exact Finset.sum_nonneg fun i _ => by split_ifs <;> norm_num lemma gen_k_server_log_K_sum {k m : ℕ} (hk : 1 ≤ k) (r x : Fin k → Fin m) : ∑ y, gen_k_server_log_K r x y = if ∃ i, x i = r i then 1 else 1 / 2 := by open Finset in unfold gen_k_server_log_K split_ifs with h · simp · rw [← mul_sum, sum_comm] simp only [sum_ite_eq', mem_univ, if_true, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul, mul_one] have : (k : ℝ) ≠ 0 := by have : (1 : ℝ) ≤ k := by exact_mod_cast hk linarith field_simp lemma gen_k_server_log_K_serves {k m : ℕ} (r x y : Fin k → Fin m) (h : gen_k_server_log_K r x y ≠ 0) : ∃ i, y i = r i := by open Finset in unfold gen_k_server_log_K at h split_ifs at h with hx hy · subst hy; exact hx · exact absurd rfl h · by_contra hn push Not at hn apply h rw [sum_eq_zero, mul_zero] intro i _ rw [if_neg] intro he apply hn i rw [he, Function.update_self] lemma gen_k_server_log_hd_update_le {k m : ℕ} (x : Fin k → Fin m) (i : Fin k) (v : Fin m) : hammingDist x (Function.update x i v) ≤ 1 := by open Finset in unfold hammingDist calc _ ≤ ({i} : Finset (Fin k)).card := by apply card_le_card intro j hj simp only [mem_filter, mem_univ, true_and] at hj by_contra hne rw [mem_singleton] at hne exact hj (by rw [Function.update_of_ne hne]) _ = 1 := card_singleton i lemma gen_k_server_log_hd_update_succ {k m : ℕ} (u o : Fin k → Fin m) (i : Fin k) (h : u i ≠ o i) : hammingDist (Function.update u i (o i)) o + 1 = hammingDist u o := by open Finset in unfold hammingDist have : (univ.filter fun j => Function.update u i (o i) j ≠ o j) = (univ.filter fun j => u j ≠ o j).erase i := by ext j by_cases hj : j = i · subst hj; simp · simp [hj] rw [this, card_erase_add_one] simp [h] lemma gen_k_server_log_K_cost {k m : ℕ} (hk : 1 ≤ k) (r x : Fin k → Fin m) : ∑ y, gen_k_server_log_K r x y * (hammingDist x y : ℝ) ≤ if ∃ i, x i = r i then 0 else 1 / 2 := by open Finset in unfold gen_k_server_log_K split_ifs with h · simp · simp_rw [mul_assoc, ← mul_sum, sum_mul] rw [sum_comm] simp only [ite_mul, one_mul, zero_mul, sum_ite_eq', mem_univ, if_true] have hkpos : (0 : ℝ) < k := by exact_mod_cast hk have hle : ∑ i : Fin k, (hammingDist x (Function.update x i (r i)) : ℝ) ≤ k := by calc _ ≤ ∑ _i : Fin k, (1 : ℝ) := sum_le_sum fun i _ => by exact_mod_cast gen_k_server_log_hd_update_le x i (r i) _ = k := by simp rw [inv_mul_le_iff₀ (by positivity)] linarith lemma gen_k_server_log_T_nonneg {k m : ℕ} (r : Fin k → Fin m) (φ : (Fin k → Fin m) → ℝ) (hφ : ∀ x, 0 ≤ φ x) (y : Fin k → Fin m) : 0 ≤ gen_k_server_log_T r φ y := Finset.sum_nonneg fun x _ => mul_nonneg (hφ x) (gen_k_server_log_K_nonneg r x y) lemma gen_k_server_log_T_sum {k m : ℕ} (hk : 1 ≤ k) (r : Fin k → Fin m) (φ : (Fin k → Fin m) → ℝ) : ∑ y, gen_k_server_log_T r φ y = ∑ x, φ x * (if ∃ i, x i = r i then 1 else 1 / 2) := by open Finset in unfold gen_k_server_log_T rw [sum_comm] refine sum_congr rfl fun x _ => ?_ rw [← mul_sum, gen_k_server_log_K_sum hk] lemma gen_k_server_log_T_ge {k m : ℕ} (r : Fin k → Fin m) (φ : (Fin k → Fin m) → ℝ) (hφ : ∀ x, 0 ≤ φ x) (x y : Fin k → Fin m) : φ x * gen_k_server_log_K r x y ≤ gen_k_server_log_T r φ y := Finset.single_le_sum (f := fun x => φ x * gen_k_server_log_K r x y) (fun x _ => mul_nonneg (hφ x) (gen_k_server_log_K_nonneg r x y)) (Finset.mem_univ x) lemma gen_k_server_log_W_append {k m : ℕ} (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (r : Fin k → Fin m) : gen_k_server_log_W a (past ++ [r]) = gen_k_server_log_T r (gen_k_server_log_W a past) := by simp [gen_k_server_log_W, List.foldl_append] lemma gen_k_server_log_foldl_pos {k m : ℕ} (hk : 1 ≤ k) (past : List (Fin k → Fin m)) : ∀ φ : (Fin k → Fin m) → ℝ, (∀ x, 0 ≤ φ x) → 0 < ∑ x, φ x → (∀ x, 0 ≤ past.foldl (fun φ r => gen_k_server_log_T r φ) φ x) ∧ 0 < ∑ x, past.foldl (fun φ r => gen_k_server_log_T r φ) φ x := by open Finset in induction past with | nil => intro φ h1 h2; exact ⟨h1, h2⟩ | cons r rs ih => intro φ h1 h2 apply ih · exact gen_k_server_log_T_nonneg r φ h1 · rw [gen_k_server_log_T_sum hk] calc 0 < ∑ x, φ x * (1 / 2) := by rw [← sum_mul]; positivity _ ≤ _ := sum_le_sum fun x _ => by apply mul_le_mul_of_nonneg_left _ (h1 x) split_ifs <;> norm_num lemma gen_k_server_log_W_nonneg {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (x : Fin k → Fin m) : 0 ≤ gen_k_server_log_W a past x := (gen_k_server_log_foldl_pos hk past _ (fun x => by split_ifs <;> norm_num) (by simp)).1 x lemma gen_k_server_log_W_sum_pos {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) (past : List (Fin k → Fin m)) : 0 < ∑ x, gen_k_server_log_W a past x := (gen_k_server_log_foldl_pos hk past _ (fun x => by split_ifs <;> norm_num) (by simp)).2 lemma gen_k_server_log_is_rand_alg {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) : gen_k_server_uniform_is_rand_alg (gen_k_server_log_P a) := by open Finset in intro past r x have hpos := gen_k_server_log_W_sum_pos hk a (past ++ [r]) refine ⟨fun y => ?_, ?_, fun y hy => ?_⟩ · unfold gen_k_server_log_P have := gen_k_server_log_K_nonneg r x y have := gen_k_server_log_W_nonneg hk a (past ++ [r]) y have : 0 ≤ (if ∃ i, x i = r i then (0 : ℝ) else 1 / 2) := by split_ifs <;> norm_num positivity · unfold gen_k_server_log_P rw [sum_add_distrib, gen_k_server_log_K_sum hk, ← mul_sum, ← sum_div, div_self hpos.ne'] split_ifs <;> norm_num · unfold gen_k_server_log_P at hy by_cases hK : gen_k_server_log_K r x y = 0 · rw [hK, zero_add] at hy have hW : gen_k_server_log_W a (past ++ [r]) y ≠ 0 := by intro h0; apply hy; rw [h0, zero_div, mul_zero] rw [gen_k_server_log_W_append] at hW unfold gen_k_server_log_T at hW obtain ⟨x', _, hx'⟩ := exists_ne_zero_of_sum_ne_zero hW exact gen_k_server_log_K_serves r x' y (right_ne_zero_of_mul hx') · exact gen_k_server_log_K_serves r x y hK /-- The configuration stays distributed as the normalized weights. -/ lemma gen_k_server_log_dist {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (r y : Fin k → Fin m) : ∑ x, gen_k_server_log_W a past x / (∑ z, gen_k_server_log_W a past z) * gen_k_server_log_P a past r x y = gen_k_server_log_W a (past ++ [r]) y / ∑ z, gen_k_server_log_W a (past ++ [r]) z := by open Finset in have hΦ := gen_k_server_log_W_sum_pos hk a past have hΦ' := gen_k_server_log_W_sum_pos hk a (past ++ [r]) set φ := gen_k_server_log_W a past set Φ := ∑ z, φ z set Φ' := ∑ z, gen_k_server_log_W a (past ++ [r]) z with hΦ'def set q := gen_k_server_log_W a (past ++ [r]) y / Φ' have hsplit : ∑ x, φ x / Φ * gen_k_server_log_P a past r x y = (∑ x, φ x * gen_k_server_log_K r x y) / Φ + (∑ x, φ x * (if ∃ i, x i = r i then 0 else 1 / 2)) / Φ * q := by rw [sum_div, sum_div, sum_mul, ← sum_add_distrib] refine sum_congr rfl fun x _ => ?_ unfold gen_k_server_log_P ring have hy : ∑ x, φ x * gen_k_server_log_K r x y = gen_k_server_log_W a (past ++ [r]) y := by rw [gen_k_server_log_W_append]; rfl have hsum : Φ' + ∑ x, φ x * (if ∃ i, x i = r i then (0 : ℝ) else 1 / 2) = Φ := by rw [hΦ'def, gen_k_server_log_W_append, gen_k_server_log_T_sum hk, ← sum_add_distrib] refine sum_congr rfl fun x _ => ?_ split_ifs <;> ring rw [hsplit, hy] simp only [q] field_simp linear_combination (gen_k_server_log_W a (past ++ [r]) y) * hsum /-- Expected movement at one step is at most `(k+1)(1 - Φ'/Φ)`. -/ lemma gen_k_server_log_cost {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (r : Fin k → Fin m) : ∑ x, ∑ y, gen_k_server_log_W a past x / (∑ z, gen_k_server_log_W a past z) * gen_k_server_log_P a past r x y * (hammingDist x y : ℝ) ≤ ((k : ℝ) + 1) * (1 - (∑ z, gen_k_server_log_W a (past ++ [r]) z) / ∑ z, gen_k_server_log_W a past z) := by open Finset in have hΦ := gen_k_server_log_W_sum_pos hk a past have hΦ' := gen_k_server_log_W_sum_pos hk a (past ++ [r]) have hsum : ∑ z, gen_k_server_log_W a (past ++ [r]) z + ∑ x, gen_k_server_log_W a past x * (if ∃ i, x i = r i then (0 : ℝ) else 1 / 2) = ∑ z, gen_k_server_log_W a past z := by rw [gen_k_server_log_W_append, gen_k_server_log_T_sum hk, ← sum_add_distrib] refine sum_congr rfl fun x _ => ?_ split_ifs <;> ring set φ := gen_k_server_log_W a past set Φ := ∑ z, φ z set φ' := gen_k_server_log_W a (past ++ [r]) set Φ' := ∑ z, φ' z with hΦ'def set c : (Fin k → Fin m) → ℝ := fun x => if ∃ i, x i = r i then 0 else 1 / 2 with hc have hper : ∀ x, ∑ y, gen_k_server_log_P a past r x y * (hammingDist x y : ℝ) ≤ ((k : ℝ) + 1) * c x := by intro x have h1 := gen_k_server_log_K_cost hk r x have h2 : ∑ y, φ' y / Φ' * (hammingDist x y : ℝ) ≤ k := by calc _ ≤ ∑ y, φ' y / Φ' * (k : ℝ) := sum_le_sum fun y _ => by apply mul_le_mul_of_nonneg_left _ (div_nonneg (gen_k_server_log_W_nonneg hk a _ y) hΦ'.le) have := hammingDist_le_card_fintype (x := x) (y := y) simp only [Fintype.card_fin] at this exact_mod_cast this _ = k := by rw [← sum_mul, ← sum_div, div_self hΦ'.ne', one_mul] have hc0 : 0 ≤ c x := by simp only [hc]; split_ifs <;> norm_num calc _ = ∑ y, gen_k_server_log_K r x y * (hammingDist x y : ℝ) + c x * ∑ y, φ' y / Φ' * (hammingDist x y : ℝ) := by rw [mul_sum, ← sum_add_distrib] refine sum_congr rfl fun y _ => ?_ unfold gen_k_server_log_P; simp only [hc, φ', Φ']; ring _ ≤ c x + c x * k := by apply add_le_add h1 exact mul_le_mul_of_nonneg_left h2 hc0 _ = _ := by ring calc _ = ∑ x, φ x / Φ * ∑ y, gen_k_server_log_P a past r x y * (hammingDist x y : ℝ) := by refine sum_congr rfl fun x _ => ?_ rw [mul_sum]; refine sum_congr rfl fun y _ => ?_; ring _ ≤ ∑ x, φ x / Φ * (((k : ℝ) + 1) * c x) := sum_le_sum fun x _ => mul_le_mul_of_nonneg_left (hper x) (div_nonneg (gen_k_server_log_W_nonneg hk a past x) hΦ.le) _ = ((k : ℝ) + 1) * (∑ x, φ x * c x) / Φ := by rw [mul_sum, sum_div]; refine sum_congr rfl fun x _ => ?_; ring _ = _ := by have hN : ∑ x, φ x * c x = Φ - Φ' := by linarith rw [hN]; field_simp lemma gen_k_server_log_main {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) : ∀ (rs past : List (Fin k → Fin m)), gen_k_server_uniform_expected_cost_from (gen_k_server_log_P a) past (fun y => gen_k_server_log_W a past y / ∑ z, gen_k_server_log_W a past z) rs ≤ ((k : ℝ) + 1) * (Real.log (∑ z, gen_k_server_log_W a past z) - Real.log (∑ z, gen_k_server_log_W a (past ++ rs) z)) := by intro rs induction rs with | nil => intro past; simp [gen_k_server_uniform_expected_cost_from] | cons r rs ih => intro past simp only [gen_k_server_uniform_expected_cost_from] have hd : (fun y => ∑ x, gen_k_server_log_W a past x / (∑ z, gen_k_server_log_W a past z) * gen_k_server_log_P a past r x y) = fun y => gen_k_server_log_W a (past ++ [r]) y / ∑ z, gen_k_server_log_W a (past ++ [r]) z := funext fun y => gen_k_server_log_dist hk a past r y rw [hd] have h1 := ih (past ++ [r]) rw [List.append_assoc, List.singleton_append] at h1 have h2 := gen_k_server_log_cost hk a past r have hΦ := gen_k_server_log_W_sum_pos hk a past have hΦ' := gen_k_server_log_W_sum_pos hk a (past ++ [r]) have h3 : 1 - (∑ z, gen_k_server_log_W a (past ++ [r]) z) / (∑ z, gen_k_server_log_W a past z) ≤ Real.log (∑ z, gen_k_server_log_W a past z) - Real.log (∑ z, gen_k_server_log_W a (past ++ [r]) z) := by have := Real.log_le_sub_one_of_pos (div_pos hΦ' hΦ) rw [Real.log_div hΦ'.ne' hΦ.ne'] at this linarith have hk1 : (0 : ℝ) ≤ (k : ℝ) + 1 := by positivity nlinarith [mul_le_mul_of_nonneg_left h3 hk1] lemma gen_k_server_log_K_self {k m : ℕ} (r u : Fin k → Fin m) (h : ∃ i, u i = r i) : gen_k_server_log_K r u u = 1 := by unfold gen_k_server_log_K; rw [if_pos h, if_pos rfl] lemma gen_k_server_log_K_repair {k m : ℕ} (r u : Fin k → Fin m) (h : ¬ ∃ i, u i = r i) (i : Fin k) : ((2 * k : ℝ))⁻¹ ≤ gen_k_server_log_K r u (Function.update u i (r i)) := by open Finset in unfold gen_k_server_log_K rw [if_neg h] have : (1 : ℝ) ≤ ∑ j, if Function.update u i (r i) = Function.update u j (r j) then 1 else 0 := by have := single_le_sum (f := fun j => if Function.update u i (r i) = Function.update u j (r j) then (1 : ℝ) else 0) (fun j _ => by split_ifs <;> norm_num) (mem_univ i) simpa using this have h0 : (0 : ℝ) ≤ ((2 * k : ℝ))⁻¹ := by positivity nlinarith lemma gen_k_server_log_offline {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) {os rs : List (Fin k → Fin m)} (h : List.Forall₂ (fun o r => ∃ i, o i = r i) os rs) : ∀ (past : List (Fin k → Fin m)) (u x0 : Fin k → Fin m), gen_k_server_log_W a past u ≤ (∑ z, gen_k_server_log_W a (past ++ rs) z) * ((2 * k : ℝ)) ^ (hammingDist u x0 + gen_k_server_uniform_path_cost x0 os) := by have h2k : (1 : ℝ) ≤ 2 * k := by have : (1 : ℝ) ≤ k := by exact_mod_cast hk linarith induction h with | nil => intro past u x0 simp only [List.append_nil] have h1 : gen_k_server_log_W a past u ≤ ∑ z, gen_k_server_log_W a past z := Finset.single_le_sum (f := gen_k_server_log_W a past) (fun z _ => gen_k_server_log_W_nonneg hk a past z) (Finset.mem_univ u) have h2 : (1 : ℝ) ≤ (2 * k : ℝ) ^ (hammingDist u x0 + gen_k_server_uniform_path_cost x0 []) := one_le_pow₀ h2k have h3 := (gen_k_server_log_W_sum_pos hk a past).le nlinarith | @cons o r os rs ho h ih => intro past u x0 simp only [gen_k_server_uniform_path_cost] have hend := (gen_k_server_log_W_sum_pos hk a (past ++ r :: rs)).le have htri := hammingDist_triangle u x0 o by_cases hs : ∃ i, u i = r i · have hih := ih (past ++ [r]) u o rw [List.append_assoc, List.singleton_append] at hih have hW : gen_k_server_log_W a past u ≤ gen_k_server_log_W a (past ++ [r]) u := by rw [gen_k_server_log_W_append] have := gen_k_server_log_T_ge r (gen_k_server_log_W a past) (gen_k_server_log_W_nonneg hk a past) u u rwa [gen_k_server_log_K_self r u hs, mul_one] at this have hpow : (2 * k : ℝ) ^ (hammingDist u o + gen_k_server_uniform_path_cost o os) ≤ (2 * k : ℝ) ^ (hammingDist u x0 + (hammingDist x0 o + gen_k_server_uniform_path_cost o os)) := pow_le_pow_right₀ h2k (by omega) calc _ ≤ _ := hW _ ≤ _ := hih _ ≤ _ := mul_le_mul_of_nonneg_left hpow hend · obtain ⟨i, hi⟩ := ho have hne : u i ≠ o i := by intro he; exact hs ⟨i, he.trans hi⟩ set u' := Function.update u i (r i) with hu' have hih := ih (past ++ [r]) u' o rw [List.append_assoc, List.singleton_append] at hih have hd : hammingDist u' o + 1 = hammingDist u o := by rw [hu', ← hi]; exact gen_k_server_log_hd_update_succ u o i hne have hW : gen_k_server_log_W a past u * ((2 * k : ℝ))⁻¹ ≤ gen_k_server_log_W a (past ++ [r]) u' := by rw [gen_k_server_log_W_append] have h1 := gen_k_server_log_T_ge r (gen_k_server_log_W a past) (gen_k_server_log_W_nonneg hk a past) u u' have h2 := gen_k_server_log_K_repair r u hs i have h3 := gen_k_server_log_W_nonneg hk a past u nlinarith have hpow : (2 * k : ℝ) ^ (hammingDist u' o + gen_k_server_uniform_path_cost o os) * (2 * k) ≤ (2 * k : ℝ) ^ (hammingDist u x0 + (hammingDist x0 o + gen_k_server_uniform_path_cost o os)) := by rw [← pow_succ] exact pow_le_pow_right₀ h2k (by omega) have h2kpos : (0 : ℝ) < 2 * k := by linarith have hW' : gen_k_server_log_W a past u ≤ gen_k_server_log_W a (past ++ [r]) u' * (2 * k) := by have := mul_le_mul_of_nonneg_right hW h2kpos.le rwa [mul_assoc, inv_mul_cancel₀ h2kpos.ne', mul_one] at this calc _ ≤ _ := hW' _ ≤ (∑ z, gen_k_server_log_W a (past ++ r :: rs) z) * (2 * k : ℝ) ^ (hammingDist u' o + gen_k_server_uniform_path_cost o os) * (2 * k) := mul_le_mul_of_nonneg_right hih h2kpos.le _ ≤ _ := by rw [mul_assoc]; exact mul_le_mul_of_nonneg_left hpow hend lemma gen_k_server_log_forall₂_self {k m : ℕ} (hk : 1 ≤ k) (ρ : List (Fin k → Fin m)) : List.Forall₂ (fun o r => ∃ i, o i = r i) ρ ρ := by induction ρ with | nil => exact List.Forall₂.nil | cons r rs ih => exact List.Forall₂.cons ⟨⟨0, hk⟩, rfl⟩ ih theorem gen_k_server_uniform_log_competitive (k m : ℕ) (hk : 1 ≤ k) (a : Fin k → Fin m) : ∃ P, gen_k_server_uniform_is_rand_alg P ∧ ∀ ρ : List (Fin k → Fin m), gen_k_server_uniform_expected_cost P a ρ ≤ ((k : ℝ) + 1) * Real.log (2 * k) * (gen_k_server_uniform_opt a ρ : ℝ) := by refine ⟨gen_k_server_log_P a, gen_k_server_log_is_rand_alg hk a, fun ρ => ?_⟩ have hW0 : gen_k_server_log_W a [] = fun x => if x = a then 1 else 0 := rfl have hS0 : ∑ z, gen_k_server_log_W a [] z = 1 := by rw [hW0]; simp have hmain := gen_k_server_log_main hk a ρ [] rw [hS0, Real.log_one, List.nil_append] at hmain simp only [div_one] at hmain rw [hW0] at hmain unfold gen_k_server_uniform_expected_cost -- an optimal offline solution have hne : {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ ∧ gen_k_server_uniform_path_cost a os = c}.Nonempty := by exact ⟨_, ρ, gen_k_server_log_forall₂_self hk ρ, rfl⟩ obtain ⟨os, hos, hcost⟩ := Nat.sInf_mem hne have hoff := gen_k_server_log_offline hk a hos [] a a rw [hW0, List.nil_append, hammingDist_self, zero_add, hcost] at hoff simp only [if_true] at hoff set ΦT := ∑ z, gen_k_server_log_W a ρ z have hΦT : 0 < ΦT := gen_k_server_log_W_sum_pos hk a ρ have h2k : (0 : ℝ) < 2 * k := by have : (1 : ℝ) ≤ k := by exact_mod_cast hk linarith have hlog : 0 ≤ Real.log ΦT + (gen_k_server_uniform_opt a ρ : ℝ) * Real.log (2 * k) := by have := Real.log_le_log one_pos hoff rw [Real.log_one, Real.log_mul hΦT.ne' (pow_pos h2k _).ne', Real.log_pow] at this exact this have hk1 : (0 : ℝ) ≤ (k : ℝ) + 1 := by positivity unfold gen_k_server_uniform_opt at hlog ⊢ nlinarith [mul_le_mul_of_nonneg_left hlog hk1]
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.
/-- Sub-stochastic kernel of the weight update: a configuration serving `r` keeps its weight,one failing `r` passes `1/(2k)` of it to each of its `k` repairs. -/noncomputable def gen_k_server_log_K {k m : ℕ} (r x y : Fin k → Fin m) : ℝ := if ∃ i, x i = r i then (if y = x then 1 else 0) else ((2 * k : ℝ))⁻¹ * ∑ i, if y = Function.update x i (r i) then 1 else 0/-- One weight update at request `r`. -/noncomputable def gen_k_server_log_T {k m : ℕ} (r : Fin k → Fin m) (φ : (Fin k → Fin m) → ℝ) (y : Fin k → Fin m) : ℝ := ∑ x, φ x * gen_k_server_log_K r x y/-- The weights after the requests `past`, starting from the point mass at `a`. -/noncomputable def gen_k_server_log_W {k m : ℕ} (a : Fin k → Fin m) (past : List (Fin k → Fin m)) : (Fin k → Fin m) → ℝ := past.foldl (fun φ r => gen_k_server_log_T r φ) (fun x => if x = a then 1 else 0)/-- The algorithm: stay when serving; otherwise with probability 1/2 a uniform repair,with probability 1/2 a fresh sample from the normalized new weights. -/noncomputable def gen_k_server_log_P {k m : ℕ} (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (r x y : Fin k → Fin m) : ℝ := gen_k_server_log_K r x y + (if ∃ i, x i = r i then 0 else 1 / 2) * (gen_k_server_log_W a (past ++ [r]) y / ∑ z, gen_k_server_log_W a (past ++ [r]) z)lemma gen_k_server_log_K_nonneg {k m : ℕ} (r x y : Fin k → Fin m) : 0 ≤ gen_k_server_log_K r x y := by unfold gen_k_server_log_K split_ifs · norm_num · norm_num · apply mul_nonneg (by positivity) exact Finset.sum_nonneg fun i _ => by split_ifs <;> norm_numlemma gen_k_server_log_K_sum {k m : ℕ} (hk : 1 ≤ k) (r x : Fin k → Fin m) : ∑ y, gen_k_server_log_K r x y = if ∃ i, x i = r i then 1 else 1 / 2 := by open Finset in unfold gen_k_server_log_K split_ifs with h · simp · rw [← mul_sum, sum_comm] simp only [sum_ite_eq', mem_univ, if_true, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul, mul_one] have : (k : ℝ) ≠ 0 := by have : (1 : ℝ) ≤ k := by exact_mod_cast hk linarith field_simplemma gen_k_server_log_K_serves {k m : ℕ} (r x y : Fin k → Fin m) (h : gen_k_server_log_K r x y ≠ 0) : ∃ i, y i = r i := by open Finset in unfold gen_k_server_log_K at h split_ifs at h with hx hy · subst hy; exact hx · exact absurd rfl h · by_contra hn push Not at hn apply h rw [sum_eq_zero, mul_zero] intro i _ rw [if_neg] intro he apply hn i rw [he, Function.update_self]lemma gen_k_server_log_hd_update_le {k m : ℕ} (x : Fin k → Fin m) (i : Fin k) (v : Fin m) : hammingDist x (Function.update x i v) ≤ 1 := by open Finset in unfold hammingDist calc _ ≤ ({i} : Finset (Fin k)).card := by apply card_le_card intro j hj simp only [mem_filter, mem_univ, true_and] at hj by_contra hne rw [mem_singleton] at hne exact hj (by rw [Function.update_of_ne hne]) _ = 1 := card_singleton ilemma gen_k_server_log_hd_update_succ {k m : ℕ} (u o : Fin k → Fin m) (i : Fin k) (h : u i ≠ o i) : hammingDist (Function.update u i (o i)) o + 1 = hammingDist u o := by open Finset in unfold hammingDist have : (univ.filter fun j => Function.update u i (o i) j ≠ o j) = (univ.filter fun j => u j ≠ o j).erase i := by ext j by_cases hj : j = i · subst hj; simp · simp [hj] rw [this, card_erase_add_one] simp [h]lemma gen_k_server_log_K_cost {k m : ℕ} (hk : 1 ≤ k) (r x : Fin k → Fin m) : ∑ y, gen_k_server_log_K r x y * (hammingDist x y : ℝ) ≤ if ∃ i, x i = r i then 0 else 1 / 2 := by open Finset in unfold gen_k_server_log_K split_ifs with h · simp · simp_rw [mul_assoc, ← mul_sum, sum_mul] rw [sum_comm] simp only [ite_mul, one_mul, zero_mul, sum_ite_eq', mem_univ, if_true] have hkpos : (0 : ℝ) < k := by exact_mod_cast hk have hle : ∑ i : Fin k, (hammingDist x (Function.update x i (r i)) : ℝ) ≤ k := by calc _ ≤ ∑ _i : Fin k, (1 : ℝ) := sum_le_sum fun i _ => by exact_mod_cast gen_k_server_log_hd_update_le x i (r i) _ = k := by simp rw [inv_mul_le_iff₀ (by positivity)] linarithlemma gen_k_server_log_T_nonneg {k m : ℕ} (r : Fin k → Fin m) (φ : (Fin k → Fin m) → ℝ) (hφ : ∀ x, 0 ≤ φ x) (y : Fin k → Fin m) : 0 ≤ gen_k_server_log_T r φ y := Finset.sum_nonneg fun x _ => mul_nonneg (hφ x) (gen_k_server_log_K_nonneg r x y)lemma gen_k_server_log_T_sum {k m : ℕ} (hk : 1 ≤ k) (r : Fin k → Fin m) (φ : (Fin k → Fin m) → ℝ) : ∑ y, gen_k_server_log_T r φ y = ∑ x, φ x * (if ∃ i, x i = r i then 1 else 1 / 2) := by open Finset in unfold gen_k_server_log_T rw [sum_comm] refine sum_congr rfl fun x _ => ?_ rw [← mul_sum, gen_k_server_log_K_sum hk]lemma gen_k_server_log_T_ge {k m : ℕ} (r : Fin k → Fin m) (φ : (Fin k → Fin m) → ℝ) (hφ : ∀ x, 0 ≤ φ x) (x y : Fin k → Fin m) : φ x * gen_k_server_log_K r x y ≤ gen_k_server_log_T r φ y := Finset.single_le_sum (f := fun x => φ x * gen_k_server_log_K r x y) (fun x _ => mul_nonneg (hφ x) (gen_k_server_log_K_nonneg r x y)) (Finset.mem_univ x)lemma gen_k_server_log_W_append {k m : ℕ} (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (r : Fin k → Fin m) : gen_k_server_log_W a (past ++ [r]) = gen_k_server_log_T r (gen_k_server_log_W a past) := by simp [gen_k_server_log_W, List.foldl_append]lemma gen_k_server_log_foldl_pos {k m : ℕ} (hk : 1 ≤ k) (past : List (Fin k → Fin m)) : ∀ φ : (Fin k → Fin m) → ℝ, (∀ x, 0 ≤ φ x) → 0 < ∑ x, φ x → (∀ x, 0 ≤ past.foldl (fun φ r => gen_k_server_log_T r φ) φ x) ∧ 0 < ∑ x, past.foldl (fun φ r => gen_k_server_log_T r φ) φ x := by open Finset in induction past with | nil => intro φ h1 h2; exact ⟨h1, h2⟩ | cons r rs ih => intro φ h1 h2 apply ih · exact gen_k_server_log_T_nonneg r φ h1 · rw [gen_k_server_log_T_sum hk] calc 0 < ∑ x, φ x * (1 / 2) := by rw [← sum_mul]; positivity _ ≤ _ := sum_le_sum fun x _ => by apply mul_le_mul_of_nonneg_left _ (h1 x) split_ifs <;> norm_numlemma gen_k_server_log_W_nonneg {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (x : Fin k → Fin m) : 0 ≤ gen_k_server_log_W a past x := (gen_k_server_log_foldl_pos hk past _ (fun x => by split_ifs <;> norm_num) (by simp)).1 xlemma gen_k_server_log_W_sum_pos {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) (past : List (Fin k → Fin m)) : 0 < ∑ x, gen_k_server_log_W a past x := (gen_k_server_log_foldl_pos hk past _ (fun x => by split_ifs <;> norm_num) (by simp)).2lemma gen_k_server_log_is_rand_alg {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) : gen_k_server_uniform_is_rand_alg (gen_k_server_log_P a) := by open Finset in intro past r x have hpos := gen_k_server_log_W_sum_pos hk a (past ++ [r]) refine ⟨fun y => ?_, ?_, fun y hy => ?_⟩ · unfold gen_k_server_log_P have := gen_k_server_log_K_nonneg r x y have := gen_k_server_log_W_nonneg hk a (past ++ [r]) y have : 0 ≤ (if ∃ i, x i = r i then (0 : ℝ) else 1 / 2) := by split_ifs <;> norm_num positivity · unfold gen_k_server_log_P rw [sum_add_distrib, gen_k_server_log_K_sum hk, ← mul_sum, ← sum_div, div_self hpos.ne'] split_ifs <;> norm_num · unfold gen_k_server_log_P at hy by_cases hK : gen_k_server_log_K r x y = 0 · rw [hK, zero_add] at hy have hW : gen_k_server_log_W a (past ++ [r]) y ≠ 0 := by intro h0; apply hy; rw [h0, zero_div, mul_zero] rw [gen_k_server_log_W_append] at hW unfold gen_k_server_log_T at hW obtain ⟨x', _, hx'⟩ := exists_ne_zero_of_sum_ne_zero hW exact gen_k_server_log_K_serves r x' y (right_ne_zero_of_mul hx') · exact gen_k_server_log_K_serves r x y hK/-- The configuration stays distributed as the normalized weights. -/lemma gen_k_server_log_dist {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (r y : Fin k → Fin m) : ∑ x, gen_k_server_log_W a past x / (∑ z, gen_k_server_log_W a past z) * gen_k_server_log_P a past r x y = gen_k_server_log_W a (past ++ [r]) y / ∑ z, gen_k_server_log_W a (past ++ [r]) z := by open Finset in have hΦ := gen_k_server_log_W_sum_pos hk a past have hΦ' := gen_k_server_log_W_sum_pos hk a (past ++ [r]) set φ := gen_k_server_log_W a past set Φ := ∑ z, φ z set Φ' := ∑ z, gen_k_server_log_W a (past ++ [r]) z with hΦ'def set q := gen_k_server_log_W a (past ++ [r]) y / Φ' have hsplit : ∑ x, φ x / Φ * gen_k_server_log_P a past r x y = (∑ x, φ x * gen_k_server_log_K r x y) / Φ + (∑ x, φ x * (if ∃ i, x i = r i then 0 else 1 / 2)) / Φ * q := by rw [sum_div, sum_div, sum_mul, ← sum_add_distrib] refine sum_congr rfl fun x _ => ?_ unfold gen_k_server_log_P ring have hy : ∑ x, φ x * gen_k_server_log_K r x y = gen_k_server_log_W a (past ++ [r]) y := by rw [gen_k_server_log_W_append]; rfl have hsum : Φ' + ∑ x, φ x * (if ∃ i, x i = r i then (0 : ℝ) else 1 / 2) = Φ := by rw [hΦ'def, gen_k_server_log_W_append, gen_k_server_log_T_sum hk, ← sum_add_distrib] refine sum_congr rfl fun x _ => ?_ split_ifs <;> ring rw [hsplit, hy] simp only [q] field_simp linear_combination (gen_k_server_log_W a (past ++ [r]) y) * hsum/-- Expected movement at one step is at most `(k+1)(1 - Φ'/Φ)`. -/lemma gen_k_server_log_cost {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) (past : List (Fin k → Fin m)) (r : Fin k → Fin m) : ∑ x, ∑ y, gen_k_server_log_W a past x / (∑ z, gen_k_server_log_W a past z) * gen_k_server_log_P a past r x y * (hammingDist x y : ℝ) ≤ ((k : ℝ) + 1) * (1 - (∑ z, gen_k_server_log_W a (past ++ [r]) z) / ∑ z, gen_k_server_log_W a past z) := by open Finset in have hΦ := gen_k_server_log_W_sum_pos hk a past have hΦ' := gen_k_server_log_W_sum_pos hk a (past ++ [r]) have hsum : ∑ z, gen_k_server_log_W a (past ++ [r]) z + ∑ x, gen_k_server_log_W a past x * (if ∃ i, x i = r i then (0 : ℝ) else 1 / 2) = ∑ z, gen_k_server_log_W a past z := by rw [gen_k_server_log_W_append, gen_k_server_log_T_sum hk, ← sum_add_distrib] refine sum_congr rfl fun x _ => ?_ split_ifs <;> ring set φ := gen_k_server_log_W a past set Φ := ∑ z, φ z set φ' := gen_k_server_log_W a (past ++ [r]) set Φ' := ∑ z, φ' z with hΦ'def set c : (Fin k → Fin m) → ℝ := fun x => if ∃ i, x i = r i then 0 else 1 / 2 with hc have hper : ∀ x, ∑ y, gen_k_server_log_P a past r x y * (hammingDist x y : ℝ) ≤ ((k : ℝ) + 1) * c x := by intro x have h1 := gen_k_server_log_K_cost hk r x have h2 : ∑ y, φ' y / Φ' * (hammingDist x y : ℝ) ≤ k := by calc _ ≤ ∑ y, φ' y / Φ' * (k : ℝ) := sum_le_sum fun y _ => by apply mul_le_mul_of_nonneg_left _ (div_nonneg (gen_k_server_log_W_nonneg hk a _ y) hΦ'.le) have := hammingDist_le_card_fintype (x := x) (y := y) simp only [Fintype.card_fin] at this exact_mod_cast this _ = k := by rw [← sum_mul, ← sum_div, div_self hΦ'.ne', one_mul] have hc0 : 0 ≤ c x := by simp only [hc]; split_ifs <;> norm_num calc _ = ∑ y, gen_k_server_log_K r x y * (hammingDist x y : ℝ) + c x * ∑ y, φ' y / Φ' * (hammingDist x y : ℝ) := by rw [mul_sum, ← sum_add_distrib] refine sum_congr rfl fun y _ => ?_ unfold gen_k_server_log_P; simp only [hc, φ', Φ']; ring _ ≤ c x + c x * k := by apply add_le_add h1 exact mul_le_mul_of_nonneg_left h2 hc0 _ = _ := by ring calc _ = ∑ x, φ x / Φ * ∑ y, gen_k_server_log_P a past r x y * (hammingDist x y : ℝ) := by refine sum_congr rfl fun x _ => ?_ rw [mul_sum]; refine sum_congr rfl fun y _ => ?_; ring _ ≤ ∑ x, φ x / Φ * (((k : ℝ) + 1) * c x) := sum_le_sum fun x _ => mul_le_mul_of_nonneg_left (hper x) (div_nonneg (gen_k_server_log_W_nonneg hk a past x) hΦ.le) _ = ((k : ℝ) + 1) * (∑ x, φ x * c x) / Φ := by rw [mul_sum, sum_div]; refine sum_congr rfl fun x _ => ?_; ring _ = _ := by have hN : ∑ x, φ x * c x = Φ - Φ' := by linarith rw [hN]; field_simplemma gen_k_server_log_main {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) : ∀ (rs past : List (Fin k → Fin m)), gen_k_server_uniform_expected_cost_from (gen_k_server_log_P a) past (fun y => gen_k_server_log_W a past y / ∑ z, gen_k_server_log_W a past z) rs ≤ ((k : ℝ) + 1) * (Real.log (∑ z, gen_k_server_log_W a past z) - Real.log (∑ z, gen_k_server_log_W a (past ++ rs) z)) := by intro rs induction rs with | nil => intro past; simp [gen_k_server_uniform_expected_cost_from] | cons r rs ih => intro past simp only [gen_k_server_uniform_expected_cost_from] have hd : (fun y => ∑ x, gen_k_server_log_W a past x / (∑ z, gen_k_server_log_W a past z) * gen_k_server_log_P a past r x y) = fun y => gen_k_server_log_W a (past ++ [r]) y / ∑ z, gen_k_server_log_W a (past ++ [r]) z := funext fun y => gen_k_server_log_dist hk a past r y rw [hd] have h1 := ih (past ++ [r]) rw [List.append_assoc, List.singleton_append] at h1 have h2 := gen_k_server_log_cost hk a past r have hΦ := gen_k_server_log_W_sum_pos hk a past have hΦ' := gen_k_server_log_W_sum_pos hk a (past ++ [r]) have h3 : 1 - (∑ z, gen_k_server_log_W a (past ++ [r]) z) / (∑ z, gen_k_server_log_W a past z) ≤ Real.log (∑ z, gen_k_server_log_W a past z) - Real.log (∑ z, gen_k_server_log_W a (past ++ [r]) z) := by have := Real.log_le_sub_one_of_pos (div_pos hΦ' hΦ) rw [Real.log_div hΦ'.ne' hΦ.ne'] at this linarith have hk1 : (0 : ℝ) ≤ (k : ℝ) + 1 := by positivity nlinarith [mul_le_mul_of_nonneg_left h3 hk1]lemma gen_k_server_log_K_self {k m : ℕ} (r u : Fin k → Fin m) (h : ∃ i, u i = r i) : gen_k_server_log_K r u u = 1 := by unfold gen_k_server_log_K; rw [if_pos h, if_pos rfl]lemma gen_k_server_log_K_repair {k m : ℕ} (r u : Fin k → Fin m) (h : ¬ ∃ i, u i = r i) (i : Fin k) : ((2 * k : ℝ))⁻¹ ≤ gen_k_server_log_K r u (Function.update u i (r i)) := by open Finset in unfold gen_k_server_log_K rw [if_neg h] have : (1 : ℝ) ≤ ∑ j, if Function.update u i (r i) = Function.update u j (r j) then 1 else 0 := by have := single_le_sum (f := fun j => if Function.update u i (r i) = Function.update u j (r j) then (1 : ℝ) else 0) (fun j _ => by split_ifs <;> norm_num) (mem_univ i) simpa using this have h0 : (0 : ℝ) ≤ ((2 * k : ℝ))⁻¹ := by positivity nlinarithlemma gen_k_server_log_offline {k m : ℕ} (hk : 1 ≤ k) (a : Fin k → Fin m) {os rs : List (Fin k → Fin m)} (h : List.Forall₂ (fun o r => ∃ i, o i = r i) os rs) : ∀ (past : List (Fin k → Fin m)) (u x0 : Fin k → Fin m), gen_k_server_log_W a past u ≤ (∑ z, gen_k_server_log_W a (past ++ rs) z) * ((2 * k : ℝ)) ^ (hammingDist u x0 + gen_k_server_uniform_path_cost x0 os) := by have h2k : (1 : ℝ) ≤ 2 * k := by have : (1 : ℝ) ≤ k := by exact_mod_cast hk linarith induction h with | nil => intro past u x0 simp only [List.append_nil] have h1 : gen_k_server_log_W a past u ≤ ∑ z, gen_k_server_log_W a past z := Finset.single_le_sum (f := gen_k_server_log_W a past) (fun z _ => gen_k_server_log_W_nonneg hk a past z) (Finset.mem_univ u) have h2 : (1 : ℝ) ≤ (2 * k : ℝ) ^ (hammingDist u x0 + gen_k_server_uniform_path_cost x0 []) := one_le_pow₀ h2k have h3 := (gen_k_server_log_W_sum_pos hk a past).le nlinarith | @cons o r os rs ho h ih => intro past u x0 simp only [gen_k_server_uniform_path_cost] have hend := (gen_k_server_log_W_sum_pos hk a (past ++ r :: rs)).le have htri := hammingDist_triangle u x0 o by_cases hs : ∃ i, u i = r i · have hih := ih (past ++ [r]) u o rw [List.append_assoc, List.singleton_append] at hih have hW : gen_k_server_log_W a past u ≤ gen_k_server_log_W a (past ++ [r]) u := by rw [gen_k_server_log_W_append] have := gen_k_server_log_T_ge r (gen_k_server_log_W a past) (gen_k_server_log_W_nonneg hk a past) u u rwa [gen_k_server_log_K_self r u hs, mul_one] at this have hpow : (2 * k : ℝ) ^ (hammingDist u o + gen_k_server_uniform_path_cost o os) ≤ (2 * k : ℝ) ^ (hammingDist u x0 + (hammingDist x0 o + gen_k_server_uniform_path_cost o os)) := pow_le_pow_right₀ h2k (by omega) calc _ ≤ _ := hW _ ≤ _ := hih _ ≤ _ := mul_le_mul_of_nonneg_left hpow hend · obtain ⟨i, hi⟩ := ho have hne : u i ≠ o i := by intro he; exact hs ⟨i, he.trans hi⟩ set u' := Function.update u i (r i) with hu' have hih := ih (past ++ [r]) u' o rw [List.append_assoc, List.singleton_append] at hih have hd : hammingDist u' o + 1 = hammingDist u o := by rw [hu', ← hi]; exact gen_k_server_log_hd_update_succ u o i hne have hW : gen_k_server_log_W a past u * ((2 * k : ℝ))⁻¹ ≤ gen_k_server_log_W a (past ++ [r]) u' := by rw [gen_k_server_log_W_append] have h1 := gen_k_server_log_T_ge r (gen_k_server_log_W a past) (gen_k_server_log_W_nonneg hk a past) u u' have h2 := gen_k_server_log_K_repair r u hs i have h3 := gen_k_server_log_W_nonneg hk a past u nlinarith have hpow : (2 * k : ℝ) ^ (hammingDist u' o + gen_k_server_uniform_path_cost o os) * (2 * k) ≤ (2 * k : ℝ) ^ (hammingDist u x0 + (hammingDist x0 o + gen_k_server_uniform_path_cost o os)) := by rw [← pow_succ] exact pow_le_pow_right₀ h2k (by omega) have h2kpos : (0 : ℝ) < 2 * k := by linarith have hW' : gen_k_server_log_W a past u ≤ gen_k_server_log_W a (past ++ [r]) u' * (2 * k) := by have := mul_le_mul_of_nonneg_right hW h2kpos.le rwa [mul_assoc, inv_mul_cancel₀ h2kpos.ne', mul_one] at this calc _ ≤ _ := hW' _ ≤ (∑ z, gen_k_server_log_W a (past ++ r :: rs) z) * (2 * k : ℝ) ^ (hammingDist u' o + gen_k_server_uniform_path_cost o os) * (2 * k) := mul_le_mul_of_nonneg_right hih h2kpos.le _ ≤ _ := by rw [mul_assoc]; exact mul_le_mul_of_nonneg_left hpow hendlemma gen_k_server_log_forall₂_self {k m : ℕ} (hk : 1 ≤ k) (ρ : List (Fin k → Fin m)) : List.Forall₂ (fun o r => ∃ i, o i = r i) ρ ρ := by induction ρ with | nil => exact List.Forall₂.nil | cons r rs ih => exact List.Forall₂.cons ⟨⟨0, hk⟩, rfl⟩ ihtheorem gen_k_server_uniform_log_competitive (k m : ℕ) (hk : 1 ≤ k) (a : Fin k → Fin m) : ∃ P, gen_k_server_uniform_is_rand_alg P ∧ ∀ ρ : List (Fin k → Fin m), gen_k_server_uniform_expected_cost P a ρ ≤ ((k : ℝ) + 1) * Real.log (2 * k) * (gen_k_server_uniform_opt a ρ : ℝ) := by refine ⟨gen_k_server_log_P a, gen_k_server_log_is_rand_alg hk a, fun ρ => ?_⟩ have hW0 : gen_k_server_log_W a [] = fun x => if x = a then 1 else 0 := rfl have hS0 : ∑ z, gen_k_server_log_W a [] z = 1 := by rw [hW0]; simp have hmain := gen_k_server_log_main hk a ρ [] rw [hS0, Real.log_one, List.nil_append] at hmain simp only [div_one] at hmain rw [hW0] at hmain unfold gen_k_server_uniform_expected_cost -- an optimal offline solution have hne : {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ ∧ gen_k_server_uniform_path_cost a os = c}.Nonempty := by exact ⟨_, ρ, gen_k_server_log_forall₂_self hk ρ, rfl⟩ obtain ⟨os, hos, hcost⟩ := Nat.sInf_mem hne have hoff := gen_k_server_log_offline hk a hos [] a a rw [hW0, List.nil_append, hammingDist_self, zero_add, hcost] at hoff simp only [if_true] at hoff set ΦT := ∑ z, gen_k_server_log_W a ρ z have hΦT : 0 < ΦT := gen_k_server_log_W_sum_pos hk a ρ have h2k : (0 : ℝ) < 2 * k := by have : (1 : ℝ) ≤ k := by exact_mod_cast hk linarith have hlog : 0 ≤ Real.log ΦT + (gen_k_server_uniform_opt a ρ : ℝ) * Real.log (2 * k) := by have := Real.log_le_log one_pos hoff rw [Real.log_one, Real.log_mul hΦT.ne' (pow_pos h2k _).ne', Real.log_pow] at this exact this have hk1 : (0 : ℝ) ≤ (k : ℝ) + 1 := by positivity unfold gen_k_server_uniform_opt at hlog ⊢ nlinarith [mul_le_mul_of_nonneg_left hlog hk1]