cycle_greedy_raw_moment_zero
The zeroth raw moment of the greedy online assignment cost on an n-cycle is identically 1 for all n ≥ 2.
Statement
theorem cycle_greedy_raw_moment_zero (n : ℕ) (hn : 2 ≤ n) : cycle_greedy_raw_moment 0 n = 1- Source
- arXiv:2610.15776
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- cycle_greedy_raw_momentThe exact rational k-th raw moment of total greedy facility assignment cost on a cycle of circumference n, computed via the fuel-bounded…
- cycle_gap_mergeMerges the adjacent gaps at cyclic index
iof a gap listgrepresenting distances between free facilities on a cycle, combining gaps… - cycle_greedy_moments_all_fuelA recursive function with signature
(fuel : ℕ) → (k_max : ℕ) → (n : ℕ) → (g : List ℕ) → List ℚ. Iffuel = 0, it returns the empty…
Read back from the Lean
For every natural number $n$ such that $2 ≤ n$, cycle_greedy_raw_moment 0 n = 1 in the rational numbers $\mathbb{Q}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by first establishing an auxiliary lemma: for any fuel level at least 1 and any list of cycle gaps, the zeroth moment list computed by the greedy assignment algorithm is identically [1]. This holds because for moment order 0, the recurrence either computes [1] directly (when the cycle has at most one gap) or repeatedly folds a constant function returning [1] (when there are multiple gaps), completely bypassing the recursive calls. Because n ≥ 2, running the algorithm with fuel n on an initial cycle of n unit gaps yields [1], whose zeroth component is 1.
When fuel = 1, the zeroth moment list cycle_greedy_moments_all_fuel 1 0 n g evaluates to [1].
Since fuel ≥ 1, fuel is non-zero, so by Nat.exists_eq_succ_of_ne_zero we can write fuel = f + 1 for some natural number f. We split into cases on f. In the base case f = 0 (so fuel = 1), the definition of cycle_greedy_moments_all_fuel for maximum order 0 maps the sole index j = 0 in List.range 1 to (m / 2)^0 / (0 + 1) = 1, simplifying directly to the singleton list [1].
uses
Nat.exists_eq_succ_of_ne_zeroobtain ⟨f, rfl⟩ : ∃ f, fuel = f + 1 := Nat.exists_eq_succ_of_ne_zero (by omega) rcases f with _ | f · simp [cycle_greedy_moments_all_fuel]
When fuel ≥ 2 and the cycle has at most one gap (g.length ≤ 1), the zeroth moment list is [1].
When f is a successor (fuel = f + 2 ≥ 2), we rewrite the goal using the recurrence equation cycle_greedy_moments_all_fuel.eq_3, discharging the requirement that the remaining fuel is non-zero by simplification. We then split on whether g.length ≤ 1. In the affirmative case, the algorithm evaluates (m / 2)^j / (j + 1) for j ∈ List.range 1, which simplifies directly to [1].
uses
cycle_greedy_moments_all_fuel.eq_3· rw [cycle_greedy_moments_all_fuel.eq_3 0 n g (f + 1) (by simp)] split_ifs with h · simp
When fuel ≥ 2 and the cycle has multiple gaps (g.length > 1), the moment fold simplifies to folding a constant function that preserves [1].
When g.length > 1, the recurrence initializes the accumulator to [1] and folds over the gap indices in List.range g.length. Because only the zeroth moment (k = 0) is computed, the moment index m is always 0. The update expression thus takes the branch `if m = 0 then 1`, which ignores both the recursive subproblem and the gap merges, identically returning [1]. By definitional equality (change), the entire fold reduces to List.foldl (fun acc i => [1]) [1] (List.range g.length) = [1]. Generalizing List.range g.length to an arbitrary list l, an induction on l proves that repeatedly applying this constant update on [1] leaves [1] unchanged.
· change List.foldl (fun acc i => [1]) [1] (List.range g.length) = [1] generalize List.range g.length = l induction l with | nil => rfl | cons x xs ih => exact ih
The zeroth raw moment cycle_greedy_raw_moment 0 n is identically 1 for all n ≥ 2.
Unfolding the definition of cycle_greedy_raw_moment, the value is the zeroth entry of cycle_greedy_moments_all_fuel n 0 n (List.replicate n 1). Since n ≥ 2, we have 1 ≤ n by linear integer arithmetic (omega). Rewriting with the auxiliary lemma cycle_greedy_raw_moment_zero_fuel simplifies the moment list to [1]. Finally, extracting the zeroth element from [1] evaluates definitionally to 1.
uses
cycle_greedy_raw_moment_zero_fuelunfold cycle_greedy_raw_moment rw [cycle_greedy_raw_moment_zero_fuel n n (by omega)] rfl
Nat.exists_eq_succ_of_ne_zero- Every non-zero natural number n can be written as k + 1 for some natural number k.
cycle_greedy_moments_all_fuel.eq_3- The recursive unfolding equation for cycle_greedy_moments_all_fuel when fuel is the successor of a positive natural number.
cycle_greedy_raw_moment_zero_fuel- For any fuel ≥ 1, cycle size n, and gap configuration g, the zeroth moment list cycle_greedy_moments_all_fuel fuel 0 n g evaluates to [1].
- The recursive definition cycle_greedy_moments_all_fuel uses an auxiliary fuel parameter to ensure termination when recursively merging cycle gaps. For the zeroth moment (k = 0), however, the recursive subproblem calls and combinatorial formulas are never actually evaluated, because the branch condition m = 0 immediately returns 1 definitionally.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma cycle_greedy_raw_moment_zero_fuel (fuel n : ℕ) (hfuel : 1 ≤ fuel) (g : List ℕ) : cycle_greedy_moments_all_fuel fuel 0 n g = [1] := by obtain ⟨f, rfl⟩ : ∃ f, fuel = f + 1 := Nat.exists_eq_succ_of_ne_zero (by omega) rcases f with _ | f · simp [cycle_greedy_moments_all_fuel] · rw [cycle_greedy_moments_all_fuel.eq_3 0 n g (f + 1) (by simp)] split_ifs with h · simp · change List.foldl (fun acc i => [1]) [1] (List.range g.length) = [1] generalize List.range g.length = l induction l with | nil => rfl | cons x xs ih => exact ih/-- The zeroth raw moment of greedy assignment cost on an n-cycle is identically 1 for all n ≥ 2. -/theorem cycle_greedy_raw_moment_zero (n : ℕ) (hn : 2 ≤ n) : cycle_greedy_raw_moment 0 n = 1 := by unfold cycle_greedy_raw_moment rw [cycle_greedy_raw_moment_zero_fuel n n (by omega)] rfl