uniform_kserver_weight_update
For a natural number k, a family of spaces M indexed by Fin k with decidable equality, a request r, and a finitely supported weight function ϕ on configurations, uniform_kserver_weight_update k r ϕ is the updated finitely supported weight function where configurations serving r retain their weight, and each configuration x failing r retains zero weight at x, discards half of its weight, and distributes a 1/(2k) fraction of its weight to each of its k repairs Function.update x i (r i).
Statement
noncomputable def uniform_kserver_weight_update (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (r : ∀ i, M i) (ϕ : (∀ i, M i) →₀ ℝ) : (∀ i, M i) →₀ ℝ
- Defined in
- arXiv:2610.37192 Section 3.1 (1)
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 1
- uniform_kserver_servesFor a natural number k, a family of uniform metric spaces M indexed by Fin k, and configurations x, r in the product space over Fin k, x…
- Used by 1
- uniform_kserver_expected_costFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of requests…
Read back from the Lean
The definition uniform_kserver_weight_update defines a function taking:
- a natural number k,
- an implicit family of types M : Fin k → Type* equipped with decidable equality for each M i,
- a tuple r : ∀ i : Fin k, M i,
- a finitely supported function ϕ : (∀ i : Fin k, M i) →₀ ℝ,
and returns a finitely supported function (∀ i : Fin k, M i) →₀ ℝ.
The result is obtained by summing over each configuration x in the support of ϕ with coefficient c = ϕ x:
- If uniform_kserver_serves x r holds, it yields the singleton support Finsupp.single x c (keeping configuration x with weight c).
- If uniform_kserver_serves x r does not hold, it yields the sum over all i : Fin k of Finsupp.single (Function.update x i (r i)) (c / (2 * k)), which replaces the coordinate x i with r i and assigns it weight c / (2 * k).
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
/-- Weight update operator for generalized k-server on uniform metrics. -/ noncomputable def uniform_kserver_weight_update (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (r : ∀ i, M i) (ϕ : (∀ i, M i) →₀ ℝ) : (∀ i, M i) →₀ ℝ := by classical exact ϕ.sum fun x c => if uniform_kserver_serves x r then Finsupp.single x c else ∑ i : Fin k, Finsupp.single (Function.update x i (r i)) (c / (2 * (k : ℝ)))