petrial_coeff_sum
For any simple graph G on a finite type V with decidable equality and decidable adjacency, the sum of petrial_coeff G k for k in the range from 0 to Fintype.card V + 1 equals 2 ^ (Fintype.card V).
Statement
theorem petrial_coeff_sum {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ∑ k ∈ Finset.range (Fintype.card V + 1), petrial_coeff G k = 2 ^ Fintype.card V
- Source
- arXiv:2611.07503, Section 3
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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,…
Read back from the Lean
For every finite type $V$ with decidable equality and every simple graph $G$ on $V$ with decidable adjacency, the sum over $k \in \{0, 1, \dots, |V|\}$ of petrial_coeff G k equals $2^{|V|}$.
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 proof partitions all subsets of the vertex set V according to the rank of their associated Petrial matrix. Since the Petrial matrix has column dimension |V|, its rank is always at most |V|. Decomposing the collection of all 2^(|V|) subsets into fibers of this rank function shows that 2^(|V|) is the sum over k from 0 to |V| of the fiber cardinalities, which are by definition the coefficients petrial_coeff G k.
The rank of the Petrial matrix of any subset F ⊆ V is strictly less than |V| + 1, so the rank function maps the set of all subsets of V into the range {0, ..., |V|}.
Given any subset F ⊆ V, the rank of the matrix petrial_matrix G F is at most the number of its columns, which is |V|. By Nat.lt_succ_of_le, this rank is strictly less than |V| + 1, which means it belongs to Finset.range (|V| + 1).
uses
Finset.mem_coe,Finset.mem_range,Nat.lt_succ_of_lehave hmaps : Set.MapsTo (fun F : Finset V => (petrial_matrix G F).rank) (↑(Finset.univ : Finset (Finset V))) (↑(Finset.range (Fintype.card V + 1))) := by intro F _ rw [Finset.mem_coe, Finset.mem_range] exact Nat.lt_succ_of_le (petrial_matrix G F).rank_le_card_width
2^(|V|) equals the sum over k ∈ {0, ..., |V|} of the number of subsets F ⊆ V whose Petrial matrix has rank k.
Applying Finset.card_eq_sum_card_fiberwise with the rank mapping shows that the total number of subsets of V equals the sum over k from 0 to |V| of the number of subsets whose Petrial matrix has rank k. Since the total number of subsets of V is 2^(|V|) (by Finset.card_univ and Fintype.card_finset), this equates 2^(|V|) with the fiber sum.
uses
Finset.card_eq_sum_card_fiberwise,Finset.card_univ,Fintype.card_finsethave hfiber := Finset.card_eq_sum_card_fiberwise hmaps rw [Finset.card_univ, Fintype.card_finset] at hfiber rw [hfiber]
The sum of petrial_coeff G k for k from 0 to |V| equals 2^(|V|).
By Finset.sum_congr, it suffices to show that for every k in the range, the summand petrial_coeff G k equals the cardinality of the fiber {F | rank(petrial_matrix G F) = k}. This holds by definition of petrial_coeff.
uses
Finset.sum_congrapply Finset.sum_congr rfl intro k _ rfl
Finset.mem_coe- An element belongs to a coerced finset if and only if it belongs to the finset.
Finset.mem_range- A natural number belongs to Finset.range n if and only if it is strictly less than n.
Nat.lt_succ_of_le- If n ≤ m, then n is strictly less than the successor of m (m + 1).
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set s equals the sum of the cardinalities of the fibers {a ∈ s | f a = b} for all b in a codomain finset t, provided f maps s into t.
Finset.card_univ- The cardinality of Finset.univ for a finite type α equals Fintype.card α.
Fintype.card_finset- The number of finsets of a finite type α is 2^(Fintype.card α).
Finset.sum_congr- Two sums over the same finite set are equal if their summands agree on every element of the set.
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 sum of the partial Petrial coefficients equals 2^|V|. -/theorem petrial_coeff_sum {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ∑ k ∈ Finset.range (Fintype.card V + 1), petrial_coeff G k = 2 ^ Fintype.card V := by have hmaps : Set.MapsTo (fun F : Finset V => (petrial_matrix G F).rank) (↑(Finset.univ : Finset (Finset V))) (↑(Finset.range (Fintype.card V + 1))) := by intro F _ rw [Finset.mem_coe, Finset.mem_range] exact Nat.lt_succ_of_le (petrial_matrix G F).rank_le_card_width have hfiber := Finset.card_eq_sum_card_fiberwise hmaps rw [Finset.card_univ, Fintype.card_finset] at hfiber rw [hfiber] apply Finset.sum_congr rfl intro k _ rfl