AFTD Auto-Formalizing Theoretical Domains

lift20_variance_crossover_at_three_fourths

theoremverifiedformalization

At activity x = 3/4, the per-vertex hard-core variance of the 20-vertex Petersen 2-lift lift20_poly_variance_per_vertex (3/4) is strictly less than that of the Petersen graph petersen_poly_variance_per_vertex (3/4).

Statement

theorem lift20_variance_crossover_at_three_fourths :
    lift20_poly_variance_per_vertex (3/4) < petersen_poly_variance_per_vertex (3/4)
Formalizes
arXiv:1806.02146
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • petersen_poly_variance_per_vertexFor an activity x, the per-vertex hard-core variance of the Petersen graph computed from its independence polynomial 1 + 10*x + 30*x^2 +…
  • lift20_poly_variance_per_vertexFor an activity x, the per-vertex hard-core variance of the 20-vertex Petersen 2-lift computed from its independence polynomial Q(x) = 1 +…

Read back from the Lean

The value of lift20_poly_variance_per_vertex at the real number 3/4 is strictly less than the value of petersen_poly_variance_per_vertex at 3/4.

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 asserts that at activity $x = 3/4$, the per-vertex hard-core variance of the 20-vertex Petersen 2-lift is strictly smaller than that of the Petersen graph itself. The proof unfolds the definitions of the per-vertex variance for both graphs, expressing each as an explicit rational function of $x$. The resulting inequality between two rational numbers is then verified directly by exact rational arithmetic.

  1. The inequality is reduced to an explicit comparison of rational expressions in the activity x = 3/4.

    Unfolding the definitions of `lift20_poly_variance_per_vertex` and `petersen_poly_variance_per_vertex` replaces the per-vertex variance on both sides with their explicit formulas: the independence polynomial (partition function $z$), its first and second factorial moments ($e_1$ and $e_2$), and the variance formula $(e_2 - e_1^2)/n$, all evaluated at activity $x = 3/4$.

    line 4

      unfold lift20_poly_variance_per_vertex petersen_poly_variance_per_vertex
  2. The per-vertex variance of the 20-vertex lift is strictly less than that of the Petersen graph at activity 3/4. automation

    Both sides are fully evaluated rational expressions: the left-hand side evaluates to $159365329715904 / 2143973997921605 \approx 0.07433$, and the right-hand side evaluates to $7652244 / 102839881 \approx 0.07441$. The `norm_num` tactic performs the exact rational arithmetic to verify that the strict inequality holds.

    line 5

      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

/-- At activity 3/4, the per-vertex hard-core variance of the 20-vertex lift is strictly less than that of the Petersen graph. -/theorem lift20_variance_crossover_at_three_fourths :    lift20_poly_variance_per_vertex (3/4) < petersen_poly_variance_per_vertex (3/4) := by  unfold lift20_poly_variance_per_vertex petersen_poly_variance_per_vertex  norm_num
See it in the graphDiscuss this resultChallenge it