AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_second_moment_three

theoremverifiedformalization

For n = 3, the exact rational second moment equals the conjectured formula value: cycle_greedy_second_moment 3 = cycle_greedy_second_moment_formula 3.

Statement

theorem cycle_greedy_second_moment_three :
    cycle_greedy_second_moment 3 = cycle_greedy_second_moment_formula 3
Formalizes
OP-890
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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_second_moment_formulaThe conjectured rational closed-form second moment formula…
  • cycle_greedy_moments_fuelA function with signature (fuel : ℕ) → (n : ℕ) → (g : List ℕ) → ℚ × ℚ. If fuel = 0, it returns (0, 0). If fuel = 1 or…
  • cycle_greedy_momentsThe function cycle_greedy_moments (n : ℕ) (g : List ℕ) : ℚ × ℚ defined as cycle_greedy_moments_fuel g.length n g.
  • 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_sThe rational Cayley-tree product sum cycle_greedy_s (n : ℕ) : ℚ := ∑ d ∈ Finset.range n, ∏ j ∈ Finset.Icc 1 d, (1 - (j : ℚ) / (n : ℚ))…

Read back from the Lean

The rational number cycle_greedy_second_moment 3 equals cycle_greedy_second_moment_formula 3. That is, the second component of cycle_greedy_moments 3 [1, 1, 1] (computed by cycle_greedy_moments_fuel 3 3 [1, 1, 1]) equals $(3^2 / 48) \cdot (5 \cdot 3 + 1 - 2 \cdot S(3))$, where $S(3) = \sum_{d=0}^2 \prod_{j=1}^d (1 - j/3) = 17/9$ (evaluating to $55/24$).

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 verifies that the conjectured formula for the second moment of the cycle greedy process holds for n = 3. The proof proceeds by computing both sides of the equation independently and showing that each evaluates to 55/24. For the left-hand side, the algorithm is unrolled across all gap-merging transitions on a 3-cycle and evaluated via rational arithmetic. For the right-hand side, the formula's finite sum and products are expanded and evaluated to the same value. Rewriting both sides with 55/24 concludes the proof.

  1. The algorithmic second moment for n = 3 equals 55/24.

    Unfold the definitions of `cycle_greedy_second_moment` and `cycle_greedy_moments`, which set up the greedy process on a cycle with three unit gaps `[1, 1, 1]`. The initial length is simplified to 3 using `List.length_replicate`. Then, using `cycle_greedy_moments_fuel.eq_def`, the recursive gap-merging transitions are fully unrolled across all possible merge choices, producing an explicit rational arithmetic expression. Finally, `norm_num` evaluates this arithmetic to 55/24.

    lines 4–9

    uses List.length_replicate, cycle_greedy_moments_fuel.eq_def

      have h1 : cycle_greedy_second_moment 3 = 55/24 := by
        unfold cycle_greedy_second_moment cycle_greedy_moments
        simp only [List.length_replicate]
        simp [cycle_greedy_moments_fuel.eq_def, cycle_gap_merge,
          show List.range 3 = [0,1,2] from rfl, show List.range 2 = [0,1] from rfl]
        norm_num
  2. The conjectured formula evaluated at n = 3 equals 55/24.

    Unfold the definitions of the second moment formula and the auxiliary sum S(n) at n = 3. Using `Finset.sum_range_succ` and `Finset.prod_Icc_succ_top`, the finite sum over d < 3 and the finite products are expanded into an explicit rational expression: (3^2 / 48) * (5 * 3 + 1 - 2 * (1 + (1 - 1/3) + (1 - 1/3) * (1 - 2/3))). Finally, `norm_num` evaluates this rational expression to 55/24.

    lines 10–13

    uses Finset.sum_range_succ, Finset.prod_Icc_succ_top

      have h2 : cycle_greedy_second_moment_formula 3 = 55/24 := by
        simp [cycle_greedy_second_moment_formula, cycle_greedy_s, Finset.sum_range_succ,
          Finset.prod_Icc_succ_top]
        norm_num
  3. The exact second moment cycle_greedy_second_moment 3 equals the conjectured formula value cycle_greedy_second_moment_formula 3.

    Substitute the common value 55/24 into both sides of the theorem using the two previously established equalities h1 and h2, closing the goal.

    line 14

      rw [h1, h2]
List.length_replicate
A list formed by replicating an element n times has length n.
cycle_greedy_moments_fuel.eq_def
The defining recursive equation of `cycle_greedy_moments_fuel`, which evaluates the first and second moments by branching over all possible gap merges when the number of gaps exceeds 1.
Finset.sum_range_succ
The sum of a function over the range {0, ..., n} equals the sum over {0, ..., n - 1} plus the term at index n.
Finset.prod_Icc_succ_top
The product of a function over the integer interval [a, b + 1] equals the product over [a, b] multiplied by the term at b + 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

/-- For n = 3, the exact second moment equals the conjectured formula value. -/theorem cycle_greedy_second_moment_three :    cycle_greedy_second_moment 3 = cycle_greedy_second_moment_formula 3 := by  have h1 : cycle_greedy_second_moment 3 = 55/24 := by    unfold cycle_greedy_second_moment cycle_greedy_moments    simp only [List.length_replicate]    simp [cycle_greedy_moments_fuel.eq_def, cycle_gap_merge,      show List.range 3 = [0,1,2] from rfl, show List.range 2 = [0,1] from rfl]    norm_num  have h2 : cycle_greedy_second_moment_formula 3 = 55/24 := by    simp [cycle_greedy_second_moment_formula, cycle_greedy_s, Finset.sum_range_succ,      Finset.prod_Icc_succ_top]    norm_num  rw [h1, h2]
See it in the graphDiscuss this resultChallenge it