cycle_greedy_moments
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 ℕ) → ℚ × ℚ. Iffuel = 0, it returns(0, 0). Iffuel = 1or…
- cycle_greedy_moments_fuelA function with signature
- Used by 4
- cycle_greedy_second_momentThe rational exact second moment
cycle_greedy_second_moment (n : ℕ) : ℚ := (cycle_greedy_moments n (List.replicate n 1)).2of total… - cycle_greedy_meanThe rational expected assignment cost
cycle_greedy_mean (n : ℕ) : ℚ := (cycle_greedy_moments n (List.replicate n 1)).1under 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:…
- cycle_greedy_second_momentThe rational exact second moment
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