cycle_greedy_second_moment_two
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)).2of total… - cycle_greedy_second_moment_formulaThe conjectured rational closed-form second moment formula…
- cycle_greedy_moments_fuelA function with signature
(fuel : ℕ) → (n : ℕ) → (g : List ℕ) → ℚ × ℚ. Iffuel = 0, it returns(0, 0). Iffuel = 1or… - cycle_greedy_momentsThe function
cycle_greedy_moments (n : ℕ) (g : List ℕ) : ℚ × ℚdefined ascycle_greedy_moments_fuel g.length n g. - cycle_gap_mergeMerges the adjacent gaps at cyclic index
iof a gap listgrepresenting 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 : ℚ))…
- cycle_greedy_second_momentThe rational exact second moment
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.
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.
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?_conshave 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
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.
uses
cycle_greedy_second_moment_formula,cycle_greedy_s,Finset.sum_range_succhave 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
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.
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
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.
/-- 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]