lift20_variance_exceeds_petersen_at_half
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.
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$.
unfold petersen_poly_variance_per_vertex lift20_poly_variance_per_vertexAt $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.
norm_num
- The proof relies on `norm_num` to evaluate and compare the rational arithmetic expressions resulting from substituting $x = 1/2$ into the polynomials defining the partition functions and moments.
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.
/-- 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