matroid_tau_nonneg
For every finite matroid M, the Tutte evaluation T_M(1,1) is non-negative. (This is the number of bases of M, but here it is just the trivial positivity of the defining power sum.)
Statement
theorem matroid_tau_nonneg {α : Type*} (M : Matroid α) [M.Finite] : 0 ≤ matroid_tau M
- Source
- step towards matroid_min_counterexample_parallel_or_series
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- matroid_tauThe real-valued evaluation
matroid_tau M : ℝof the Tutte polynomial of a finite matroid M with instance [M.Finite], defined as… - matroid_tutte_evalThe real-valued evaluation of the Tutte polynomial
matroid_tutte_eval M x y : ℝof a finite matroid M with instance [M.Finite] at real…
- matroid_tauThe real-valued evaluation
The proof, explained
The Tutte evaluation τ(M) = T_M(1, 1) is defined as a sum over all subsets of the ground set of M. Substituting x = 1 and y = 1 simplifies each summand to a product of powers of zero, 0^a * 0^b. Since every summand is non-negative, the total sum is non-negative.
The Tutte evaluation τ(M) is rewritten as a sum over all subsets of the ground set whose terms are of the form 0^a * 0^b.
Unfolding the definitions of `matroid_tau` and `matroid_tutte_eval` expands τ(M) into the powerset sum with factors (1 - 1)^a and (1 - 1)^b. Rewriting with `sub_self` simplifies each base 1 - 1 to 0.
uses
sub_selfunfold matroid_tau matroid_tutte_eval simp only [sub_self]
It suffices to show that every summand in the powerset sum is non-negative.
Applying `Finset.sum_nonneg` reduces the non-negativity of the finite sum to proving that each term is non-negative.
uses
Finset.sum_nonnegapply Finset.sum_nonnegEach term 0^a * 0^b is non-negative. automation
For an arbitrary subset x of the ground set, the summand is a product of powers of 0 with natural-number exponents. The `positivity` tactic verifies that powers of 0 and their products are non-negative.
intro x hx positivity
sub_self- Subtracting an element from itself yields zero (a - a = 0).
Finset.sum_nonneg- A finite sum in an ordered additive commutative monoid is non-negative if each of its terms is non-negative.
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.
/-- The Tutte evaluation T_M(1,1) is non-negative: in its defining powerset sum every summand is (1-1)^a * (1-1)^b = 0^a * 0^b, a product of non-negative reals. -/theorem matroid_tau_nonneg {α : Type*} (M : Matroid α) [M.Finite] : 0 ≤ matroid_tau M := by unfold matroid_tau matroid_tutte_eval simp only [sub_self] apply Finset.sum_nonneg intro x hx positivity