cycle_greedy_second_moment_formula_eq_mean_form
For every natural number n, cycle_greedy_second_moment_formula n = (5 * (n : ℚ) ^ 3 + (n : ℚ) ^ 2) / 48 - (n : ℚ) * ((n : ℚ) * cycle_greedy_s n / 4) / 6.
Statement
theorem cycle_greedy_second_moment_formula_eq_mean_form (n : ℕ) :
cycle_greedy_second_moment_formula n =
(5 * (n : ℚ) ^ 3 + (n : ℚ) ^ 2) / 48 - (n : ℚ) * ((n : ℚ) * cycle_greedy_s n / 4) / 6- Formalizes
- OP-890
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_greedy_second_moment_formulaThe conjectured rational closed-form second moment formula…
- 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
For every natural number $n$, the value $\mathrm{cycle\_greedy\_second\_moment\_formula}(n)$ is equal to $\frac{5n^3 + n^2}{48} - \frac{n \left(\frac{n \cdot \mathrm{cycle\_greedy\_s}(n)}{4}\right)}{6}$, computed 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 proof establishes the equivalence by expanding the definition of the second moment formula and simplifying the resulting rational expressions. Unfolding `cycle_greedy_second_moment_formula` turns the left-hand side into $\frac{n^2}{48}(5n + 1 - 2 s_n)$, where $s_n = \mathrm{cycle\_greedy\_s}(n)$. Both sides expand to $\frac{5n^3 + n^2}{48} - \frac{n^2 s_n}{24}$, which Lean's `ring` tactic confirms automatically by polynomial arithmetic over $\mathbb{Q}$.
The equality reduces to $\frac{n^2}{48} (5n + 1 - 2 s_n) = \frac{5n^3 + n^2}{48} - \frac{n (n s_n / 4)}{6}$, where $s_n = \mathrm{cycle\_greedy\_s}(n)$.
Unfolding the definition of `cycle_greedy_second_moment_formula` replaces the left-hand side with its explicit definition $\frac{n^2}{48} (5n + 1 - 2 \cdot \mathrm{cycle\_greedy\_s}(n))$.
unfold cycle_greedy_second_moment_formulaThe algebraic identity holds over the rational numbers. automation
Both expressions expand to $\frac{5n^3 + n^2}{48} - \frac{n^2 s_n}{24}$. The `ring` tactic completes the proof by verifying this polynomial equality in $\mathbb{Q}$.
ring
- The `ring` tactic verifies the algebraic identity over the rational numbers automatically, without detailing the intermediate polynomial expansion and fraction simplification.
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.
/-- Algebraic equivalence of the second moment formula to the mean representation (5n^3 + n^2)/48 - n E[C_n]/6. -/theorem cycle_greedy_second_moment_formula_eq_mean_form (n : ℕ) : cycle_greedy_second_moment_formula n = (5 * (n : ℚ) ^ 3 + (n : ℚ) ^ 2) / 48 - (n : ℚ) * ((n : ℚ) * cycle_greedy_s n / 4) / 6 := by unfold cycle_greedy_second_moment_formula ring