petrial_nullity_poly_coeff_eq_petrial_coeff
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
- petrial_nullity_poly_leaf_recFor a finite graph G with a degree-one vertex v whose neighbour is u, the nullity generating polynomial of G equals the nullity generating…
- op_1239_candidate36_petrial_coefficientsThe partial Petrial coefficients of op_1239_candidate36 in ranks 27, 28, and 29 are respectively 256, 32640, and 4666944.
- petrial_nullity_poly_mul_of_cutIf no edge of G joins a vertex of s to a vertex outside s, then the nullity generating polynomial of G is the product of the nullity…
- op_1239_candidate31_coefficients_of_polyIf the nullity polynomial of op_1239_candidate31 is the displayed degree-seven polynomial, then its partial Petrial coefficients in ranks…
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.
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).
classical unfold petrial_nullity_poly petrial_coeffThe 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.
uses
Polynomial.finsetSum_coeff,Polynomial.coeff_X_pow,Finset.sum_filter,Finset.sum_const,nsmul_eq_mul,mul_one,Nat.cast_idsimp 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]
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.
uses
congrArg,Finset.mem_filter,Finset.mem_univ,true_andapply congrArg Finset.card ext F simp only [Finset.mem_filter, Finset.mem_univ, true_and]
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.
uses
rank_le_card_widthhave 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).
- In Lean, natural number subtraction is truncating (n - m = 0 whenever n ≤ m), so the arithmetic equivalence |V| - k = |V| - rank(M_F) ↔ rank(M_F) = k strictly requires both bounds k ≤ |V| and rank(M_F) ≤ |V|.
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.
/-- 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