AFTD Auto-Formalizing Theoretical Domains

matroid_tau_nonneg

theoremverified

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…

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.

  1. 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.

    lines 3–4

    uses sub_self

      unfold matroid_tau matroid_tutte_eval
      simp only [sub_self]
  2. 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.

    line 5

    uses Finset.sum_nonneg

      apply Finset.sum_nonneg
  3. Each 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.

    lines 6–7

      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

/-- 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
See it in the graphDiscuss this resultChallenge it