AFTD Auto-Formalizing Theoretical Domains

petrial_nullity_poly_coeff_eq_petrial_coeff

theoremverified

For every finite graph G on V and every k ≤ |V|, the coefficient of w^(|V| - k) in the nullity generating polynomial equals petrial_coeff G k (the number of vertex subsets F whose partial Petrial matrix has rank k).

Statement

theorem petrial_nullity_poly_coeff_eq_petrial_coeff {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : k ≤ Fintype.card V) :
    (petrial_nullity_poly G).coeff (Fintype.card V - k) = petrial_coeff G k
Source
step towards op_1239_max_degree_three_tree_petrial_log_concave
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • petrial_nullity_polyThe nullity generating polynomial of a finite graph G on V: the sum over all vertex subsets F of w raised to the nullity of the partial…
  • petrial_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…
  • petrial_coeffGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and k : ℕ, petrial_coeff G k is the…
Used by 4

The proof, explained

The nullity polynomial of G is defined as the sum over all vertex subsets F ⊆ V of X^(|V| - rank(M_F)), where M_F is the partial Petrial matrix. Extracting the coefficient of X^(|V| - k) reduces to counting the subsets F for which |V| - k = |V| - rank(M_F). Since rank(M_F) ≤ |V| and k ≤ |V|, this equality holds if and only if rank(M_F) = k, which is precisely the count defining petrial_coeff G k.

  1. Unfolding the definitions, the goal is to show that the (|V| - k)-th coefficient of ∑_F X^(|V| - rank(M_F)) equals the cardinality of {F ⊆ V | rank(M_F) = k}.

    We enable classical reasoning and unfold the definitions of the nullity polynomial petrial_nullity_poly (the sum of X^(|V| - rank(M_F)) over all vertex subsets F) and petrial_coeff (the number of vertex subsets F whose partial Petrial matrix has rank k).

    lines 5–6

      classical
      unfold petrial_nullity_poly petrial_coeff
  2. The coefficient of X^(|V| - k) in the polynomial sum equals the number of vertex subsets F satisfying |V| - k = |V| - rank(M_F).

    Taking the (|V| - k)-th coefficient distributes across the finite sum by Polynomial.finsetSum_coeff. By Polynomial.coeff_X_pow, each monomial X^(|V| - rank(M_F)) contributes 1 when |V| - k = |V| - rank(M_F) and 0 otherwise. Using Finset.sum_filter in reverse, this sum of indicator functions becomes the sum of 1 over the filtered set of vertex subsets satisfying the condition. Evaluating the sum of 1s over this set via Finset.sum_const, nsmul_eq_mul, mul_one, and Nat.cast_id reduces the sum to the cardinality of that filtered set.

    lines 7–9

    uses Polynomial.finsetSum_coeff, Polynomial.coeff_X_pow, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul, mul_one, Nat.cast_id

      simp only [Polynomial.finsetSum_coeff, Polynomial.coeff_X_pow]
      rw [← Finset.sum_filter]
      simp only [Finset.sum_const, nsmul_eq_mul, mul_one, Nat.cast_id]
  3. It suffices to show that for every vertex subset F ⊆ V, |V| - k = |V| - rank(M_F) if and only if rank(M_F) = k.

    To show that the two finite sets have the same cardinality, it suffices by congrArg to show that the sets themselves are equal. By set extensionality (ext F), two sets are equal if they contain the same elements. Simplifying membership in the filtered sub-finsets using Finset.mem_filter, Finset.mem_univ, and true_and reduces the goal to proving that the two rank conditions are logically equivalent for an arbitrary F.

    lines 10–12

    uses congrArg, Finset.mem_filter, Finset.mem_univ, true_and

      apply congrArg Finset.card
      ext F
      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
  4. For every F ⊆ V, |V| - k = |V| - rank(M_F) is equivalent to rank(M_F) = k.

    Because the partial Petrial matrix M_F has dimensions |V| × |V|, its rank is bounded by the number of columns |V| (via rank_le_card_width). Given the theorem hypothesis k ≤ |V| and this upper bound rank(M_F) ≤ |V|, the equality |V| - k = |V| - rank(M_F) holds if and only if rank(M_F) = k. Linear arithmetic over ℕ (omega) closes the goal.

    lines 13–14

    uses rank_le_card_width

      have hle := (petrial_matrix G F).rank_le_card_width
      omega
Polynomial.finsetSum_coeff
The n-th coefficient of a finite sum of polynomials equals the sum of the n-th coefficients of the summands.
Polynomial.coeff_X_pow
The n-th coefficient of the monomial X^k is 1 if n = k and 0 otherwise.
Finset.sum_filter
Summing a function over elements satisfying a predicate equals summing the conditional expression (the function if the predicate holds, and 0 otherwise) over the whole set.
Finset.sum_const
Summing a constant value b over a finite set s equals |s| • b.
nsmul_eq_mul
Natural number scalar multiplication n • a equals the ring product n * a.
mul_one
Multiplying an element by 1 on the right leaves it unchanged.
Nat.cast_id
The canonical coercion from natural numbers to natural numbers is the identity.
congrArg
Applying a function to equal arguments yields equal results.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filter predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset univ.
true_and
The proposition True ∧ p simplifies to p.
rank_le_card_width
The rank of a matrix is bounded by the cardinality of its column index type (its width).

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

/-- For k ≤ |V| the coefficient of w^(|V|-k) in the nullity polynomial is petrial_coeff G k. -/theorem petrial_nullity_poly_coeff_eq_petrial_coeff {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : k ≤ Fintype.card V) :    (petrial_nullity_poly G).coeff (Fintype.card V - k) = petrial_coeff G k := by  classical  unfold petrial_nullity_poly petrial_coeff  simp only [Polynomial.finsetSum_coeff, Polynomial.coeff_X_pow]  rw [← Finset.sum_filter]  simp only [Finset.sum_const, nsmul_eq_mul, mul_one, Nat.cast_id]  apply congrArg Finset.card  ext F  simp only [Finset.mem_filter, Finset.mem_univ, true_and]  have hle := (petrial_matrix G F).rank_le_card_width  omega
See it in the graphDiscuss this resultChallenge it