AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_moments

def

The function cycle_greedy_moments (n : ℕ) (g : List ℕ) : ℚ × ℚ defined as cycle_greedy_moments_fuel g.length n g.

Statement

def cycle_greedy_moments (n : ℕ) (g : List ℕ) : ℚ × ℚ
Defined in
arXiv:2610.15776, Corollary 18
Verified
02 Nov 2026
Axioms
none listed
Built on 1
  • cycle_greedy_moments_fuelA function with signature (fuel : ℕ) → (n : ℕ) → (g : List ℕ) → ℚ × ℚ. If fuel = 0, it returns (0, 0). If fuel = 1 or…
Used by 4
  • cycle_greedy_second_momentThe rational exact second moment cycle_greedy_second_moment (n : ℕ) : ℚ := (cycle_greedy_moments n (List.replicate n 1)).2 of total…
  • cycle_greedy_meanThe rational expected assignment cost cycle_greedy_mean (n : ℕ) : ℚ := (cycle_greedy_moments n (List.replicate n 1)).1 under greedy…
  • cycle_greedy_second_moment_twoFor n = 2, the exact rational second moment equals the conjectured formula value:…
  • cycle_greedy_second_moment_threeFor n = 3, the exact rational second moment equals the conjectured formula value:…

Read back from the Lean

cycle_greedy_moments defines a function that takes a natural number n : ℕ and a list of natural numbers g : List ℕ, and returns a pair of rational numbers (M₁, M₂) : ℚ × ℚ. It computes cycle_greedy_moments_fuel g.length n g, which recursively calculates the first two moments of a greedy cycle process on gap lengths g with total length parameter n, using g.length as the recursion fuel: 1. If g is empty (g.length = 0), it returns (0, 0). 2. If g has length 1, letting m : ℚ be the single element (or 0 if empty), it returns (m / 4, m² / 12). 3. If g has length k ≥ 2, it iterates i through 0, 1, ..., k - 1 with an accumulator initially (0, 0): - It reads l : ℚ = g[(i + k - 1) % k] (the cyclic predecessor) and r : ℚ = g[i]. - It computes the merged list next_g = cycle_gap_merge g i, which merges the gap at index i with its predecessor (producing a list of length k - 1): - If i = 0, next_g = g.tail.dropLast ++ [g.getLast + g.head]. - If i > 0, next_g = g.take (i - 1) ++ [g[i - 1] + g[i]] ++ g.drop (i + 1). - It recursively computes (sub₁, sub₂) = cycle_greedy_moments_fuel (fuel - 1) n next_g. - It sets: - p = (l + r) / (2 * n) - c = (l² + r²) / (8 * n) - d = (l³ + r³) / (24 * n) - It updates the accumulator by: - acc.1 := acc.1 + c + p * sub₁ - acc.2 := acc.2 + d + 2 * c * sub₁ + p * sub₂ and returns the final accumulated pair.

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

/-- Computes first and second moments of remaining greedy assignment cost from gap configuration g on an n-cycle. -/
def cycle_greedy_moments (n : ℕ) (g : List ℕ) : ℚ × ℚ := cycle_greedy_moments_fuel g.length n g
See it in the graphDiscuss this resultChallenge it