cycle_greedy_second_moment_three
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)).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 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.
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.
uses
List.length_replicate,cycle_greedy_moments_fuel.eq_defhave 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
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.
uses
Finset.sum_range_succ,Finset.prod_Icc_succ_tophave 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
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.
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.
- The exact calculation of the second moment expands all recursive gap-merging transitions on 3 vertices into a large rational arithmetic expression, which Lean evaluates via `norm_num`.
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 = 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]