AFTD Auto-Formalizing Theoretical Domains

lift20_variance_exceeds_petersen_at_half

theoremverifiedformalization

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

Statement

theorem lift20_variance_exceeds_petersen_at_half :
    petersen_poly_variance_per_vertex (1/2) < lift20_poly_variance_per_vertex (1/2)
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 petersen_poly_variance_per_vertex (1/2) is strictly less than lift20_poly_variance_per_vertex (1/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 proof proceeds by direct numerical evaluation. Unfolding the definitions of the per-vertex hard-core variance for both the Petersen graph and its 20-vertex 2-lift expresses each quantity as a rational function of the fugacity $x$. At $x = 1/2$, both expressions evaluate to explicit rational numbers, and the strict inequality is verified by rational arithmetic.

  1. The inequality reduces to an explicit comparison between rational expressions evaluated at $x = 1/2$.

    Unfolding the definitions of `petersen_poly_variance_per_vertex` and `lift20_poly_variance_per_vertex` expands both per-vertex variances into explicit formulas $(e_2 - e_1^2) / n$, where the partition function $z$, first moment $e_1$, and second moment $e_2$ are degree-4 (for Petersen, with $n = 10$) and degree-8 (for the 2-lift, with $n = 20$) polynomials evaluated at $x = 1/2$.

    line 4

      unfold petersen_poly_variance_per_vertex lift20_poly_variance_per_vertex
  2. At $x = 1/2$, the per-vertex variance of the Petersen graph is strictly less than that of the 20-vertex lift. automation

    Evaluating the rational expressions gives $6118 / 78961 \approx 0.07748$ for the Petersen graph and $489009680 / 6278502169 \approx 0.07789$ for the 20-vertex lift. Rational arithmetic simplifies and confirms the strict inequality.

    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 1/2, the per-vertex hard-core variance of the Petersen graph is strictly less than that of the 20-vertex lift. -/theorem lift20_variance_exceeds_petersen_at_half :    petersen_poly_variance_per_vertex (1/2) < lift20_poly_variance_per_vertex (1/2) := by  unfold petersen_poly_variance_per_vertex lift20_poly_variance_per_vertex  norm_num
See it in the graphDiscuss this resultChallenge it