AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_second_moment_two

theoremverifiedformalization

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

Statement

theorem cycle_greedy_second_moment_two :
    cycle_greedy_second_moment 2 = cycle_greedy_second_moment_formula 2
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 theorem asserts that cycle_greedy_second_moment 2 equals cycle_greedy_second_moment_formula 2; that is, the second moment of the greedy cycle process for n = 2 (initialized with gap list List.replicate 2 1 = [1, 1]) equals the value computed by the closed formula cycle_greedy_second_moment_formula evaluated at 2.

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 the conjectured formula for the second moment in the case n = 2 by computing both sides independently. First, the exact second moment is calculated from its recursive definition on a 2-cycle with two unit gaps, evaluating the gap-merging fold to obtain 2/3. Second, the conjectured closed-form formula is evaluated for n = 2 by expanding the finite sum defining s_2, which also yields 2/3. Equating both values establishes the theorem.

  1. cycle_greedy_second_moment 2 = 2 / 3

    Compute the exact second moment for n = 2 directly from its recursive definition. Unfolding cycle_greedy_second_moment and cycle_greedy_moments sets up the calculation of cycle_greedy_moments_fuel on a cycle of two unit gaps [1, 1] with fuel 2. Rewriting with the recursive equation cycle_greedy_moments_fuel.eq_def and evaluating the list operations (the fold over the two gap indices, gap merges, and list lookups) reduces the second moment component to a concrete rational arithmetic expression, which norm_num evaluates to 2/3.

    lines 4–11

    uses List.length_replicate, cycle_greedy_moments_fuel.eq_def, cycle_gap_merge, List.range_succ, List.foldl_append, List.foldl_cons, List.foldl_nil, List.replicate_succ, List.replicate_zero, List.length_cons, List.length_nil, List.getElem?_cons_zero, List.getElem?_cons_succ, List.head?_cons, List.getLast?_cons

      have h1 : cycle_greedy_second_moment 2 = 2/3 := by
        unfold cycle_greedy_second_moment cycle_greedy_moments
        simp only [List.length_replicate]
        simp only [cycle_greedy_moments_fuel.eq_def]
        simp only [cycle_gap_merge, List.range_succ, List.foldl_append, List.foldl_cons,
          List.foldl_nil, List.replicate_succ, List.replicate_zero, List.length_cons, List.length_nil,
          List.getElem?_cons_zero, List.getElem?_cons_succ, List.head?_cons, List.getLast?_cons]
        norm_num
  2. cycle_greedy_second_moment_formula 2 = 2 / 3

    Evaluate the conjectured formula for n = 2. Unfolding cycle_greedy_second_moment_formula and the auxiliary sum cycle_greedy_s, and splitting the sum over the range {0, 1} with Finset.sum_range_succ, reduces the formula to (2^2 / 48) * (5 * 2 + 1 - 2 * (1 + (1 - 1/2))). Numerical calculation by norm_num evaluates this to 2/3.

    lines 12–14

    uses cycle_greedy_second_moment_formula, cycle_greedy_s, Finset.sum_range_succ

      have h2 : cycle_greedy_second_moment_formula 2 = 2/3 := by
        simp [cycle_greedy_second_moment_formula, cycle_greedy_s, Finset.sum_range_succ]
        norm_num
  3. cycle_greedy_second_moment 2 = cycle_greedy_second_moment_formula 2

    Substitute the two established identities h1 and h2 (both evaluating to 2/3) into the goal, concluding that the exact second moment and the formula value coincide for n = 2.

    line 15

      rw [h1, h2]
List.length_replicate
The length of a list formed by replicating an element n times is n: (List.replicate n a).length = n.
cycle_greedy_moments_fuel.eq_def
The unfolding/definitional equation of cycle_greedy_moments_fuel across its base cases and recursive fold.
cycle_gap_merge
The operation that merges the two adjacent gaps at index i in a cycle of gaps.
List.range_succ
The range of numbers up to n + 1 equals the range up to n appended with [n]: List.range (n + 1) = List.range n ++ [n].
List.foldl_append
Folding over an appended list l ++ l' equals folding over l' starting from the fold over l.
List.foldl_cons
Folding over a cons list a :: l with accumulator b equals folding over l with updated accumulator f b a.
List.foldl_nil
Folding over the empty list returns the accumulator unchanged: List.foldl f b [] = b.
List.replicate_succ
Replicating an element n + 1 times equals consing the element onto the replication of length n: List.replicate (n + 1) a = a :: List.replicate n a.
List.replicate_zero
Replicating an element 0 times yields the empty list: List.replicate 0 a = [].
List.length_cons
The length of a cons list a :: as is as.length + 1.
List.length_nil
The length of the empty list is 0.
List.getElem?_cons_zero
Accessing the 0-th element of a cons list a :: l returns some a.
List.getElem?_cons_succ
Accessing element i + 1 of a cons list a :: l equals accessing element i of l.
List.head?_cons
The optional head of a cons list a :: l is some a.
List.getLast?_cons
The optional last element of a cons list a :: l is the last element of l if non-empty, or a if l is empty.
cycle_greedy_second_moment_formula
The conjectured closed-form formula for the second moment at n: (n^2 / 48) * (5n + 1 - 2 * cycle_greedy_s n).
cycle_greedy_s
The auxiliary sum s_n = ∑_{d=0}^{n-1} ∏_{j=1}^d (1 - j/n).
Finset.sum_range_succ
Separating the last term from a finite sum: ∑_{x ∈ range (n + 1)} f(x) = (∑_{x ∈ range n} f(x)) + f(n).

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 = 2, the exact second moment equals the conjectured formula value. -/theorem cycle_greedy_second_moment_two :    cycle_greedy_second_moment 2 = cycle_greedy_second_moment_formula 2 := by  have h1 : cycle_greedy_second_moment 2 = 2/3 := by    unfold cycle_greedy_second_moment cycle_greedy_moments    simp only [List.length_replicate]    simp only [cycle_greedy_moments_fuel.eq_def]    simp only [cycle_gap_merge, List.range_succ, List.foldl_append, List.foldl_cons,      List.foldl_nil, List.replicate_succ, List.replicate_zero, List.length_cons, List.length_nil,      List.getElem?_cons_zero, List.getElem?_cons_succ, List.head?_cons, List.getLast?_cons]    norm_num  have h2 : cycle_greedy_second_moment_formula 2 = 2/3 := by    simp [cycle_greedy_second_moment_formula, cycle_greedy_s, Finset.sum_range_succ]    norm_num  rw [h1, h2]
See it in the graphDiscuss this resultChallenge it