AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_raw_moment_zero

theoremverified

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 i of a gap list g representing 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 ℚ. If fuel = 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.

  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].

    lines 3–5

    uses Nat.exists_eq_succ_of_ne_zero

      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]
  2. 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].

    lines 6–8

    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
  3. 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.

    lines 9–13

        · 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
  4. 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.

    lines 17–19

    uses cycle_greedy_raw_moment_zero_fuel

      unfold 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].

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

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
See it in the graphDiscuss this resultChallenge it