AFTD Auto-Formalizing Theoretical Domains

gen_k_server_uniform_is_rand_alg

def

Generalized k-server where each of the k servers moves in its own copy of the uniform metric on m points: configurations and requests are functions Fin k → Fin m. A real function P(past, r, x, y), taking a list past of earlier requests, the current request r, the current configuration x and a next configuration y, is a randomized online algorithm (in behavioural form) if for every past, r and x: P(past, r, x, y) ≥ 0 for every y, the sum over all y in Fin k → Fin m of P(past, r, x, y) is 1, and every y with P(past, r, x, y) ≠ 0 serves r, i.e. y i = r i for some i : Fin k. P(past, r, x, y) is the probability of moving from x to y when request r arrives after the requests past.

Statement

def gen_k_server_uniform_is_rand_alg {k m : ℕ}
    (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) : Prop
Defined in
arXiv:2610.37192, Sec. 2 (Preliminaries): randomized online algorithm for generalized k-server; here every space is the uniform metric Fin m and the algorithm is given in behavioural form by transition probabilities
Verified
28 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

Given natural numbers k and m, a function P (which takes a history past : List (Fin k → Fin m), two configurations/states r, x : Fin k → Fin m, and a candidate next configuration y : Fin k → Fin m, and outputs a real number) satisfies gen_k_server_uniform_is_rand_alg if and only if: for all histories past and all r, x : Fin k → Fin m, the following three conditions hold: 1. For every y : Fin k → Fin m, P(past, r, x, y) ≥ 0; 2. The sum of P(past, r, x, y) over all y : Fin k → Fin m equals 1; 3. For every y : Fin k → Fin m, if P(past, r, x, y) ≠ 0, then there exists an index i : Fin k such that y(i) = r(i).

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

/-- Randomized online algorithm for generalized k-server on k uniform metrics `Fin m`, given by transition probabilities `P past r x y` (earlier requests, current request, current configuration, next configuration); the next configuration must serve the request. -/
def gen_k_server_uniform_is_rand_alg {k m : ℕ}
    (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) : Prop :=
  ∀ (past : List (Fin k → Fin m)) (r x : Fin k → Fin m),
    (∀ y, 0 ≤ P past r x y) ∧ (∑ y, P past r x y) = 1 ∧ (∀ y, P past r x y ≠ 0 → ∃ i, y i = r i)
See it in the graphDiscuss this resultChallenge it