AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_mean

def

The rational expected assignment cost cycle_greedy_mean (n : ℕ) : ℚ := (cycle_greedy_moments n (List.replicate n 1)).1 under greedy online assignment on a cycle of circumference n.

Statement

def cycle_greedy_mean (n : ℕ) : ℚ
Defined in
arXiv:2610.15776, Section 3 and Theorem 9
Verified
02 Nov 2026
Axioms
none listed
Built on 1
  • cycle_greedy_momentsThe function cycle_greedy_moments (n : ℕ) (g : List ℕ) : ℚ × ℚ defined as cycle_greedy_moments_fuel g.length n g.

Read back from the Lean

The definition cycle_greedy_mean takes a natural number n and returns the first component (the mean) of cycle_greedy_moments n (List.replicate n 1), representing the first moment of a greedy process on a cycle initialized with n gaps of size 1.

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

/-- Expected total assignment cost of the greedy online algorithm on a cycle of circumference n. -/
def cycle_greedy_mean (n : ℕ) : ℚ := (cycle_greedy_moments n (List.replicate n 1)).1
See it in the graphDiscuss this resultChallenge it