AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_second_moment_formula_eq_mean_form

theoremverifiedformalization

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}$.

  1. 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))$.

    line 5

      unfold cycle_greedy_second_moment_formula
  2. The 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}$.

    line 6

      ring

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

/-- 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
See it in the graphDiscuss this resultChallenge it