lift20_variance_crossover_at_three_fourths
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.
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$.
unfold lift20_poly_variance_per_vertex petersen_poly_variance_per_vertexThe 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.
norm_num
- The arithmetic comparison of the two rational values is discharged by the `norm_num` normalization tactic without generating intermediate proof steps.
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 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