AFTD Auto-Formalizing Theoretical Domains

petrial_coeff_sum

theoremverified

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.

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

    lines 5–9

    uses Finset.mem_coe, Finset.mem_range, Nat.lt_succ_of_le

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

    lines 10–12

    uses Finset.card_eq_sum_card_fiberwise, Finset.card_univ, Fintype.card_finset

      have hfiber := Finset.card_eq_sum_card_fiberwise hmaps
      rw [Finset.card_univ, Fintype.card_finset] at hfiber
      rw [hfiber]
  3. 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.

    lines 13–15

    uses Finset.sum_congr

      apply 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

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