AFTD Auto-Formalizing Theoretical Domains

zero_forcing_poly_coeff

theoremverified

The coefficient of x^k in the zero forcing polynomial of G is the number of k-element vertex subsets that are zero forcing sets.

Statement

theorem zero_forcing_poly_coeff {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k : ℕ) :
    (zero_forcing_poly G).coeff k =
      {S : Finset V | is_zero_forcing_set G (S : Set V) ∧ S.card = k}.ncard
Source
step towards gt_zero_forcing_poly_not_unimodal
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • zero_forcing_polyGiven a finite type V and a simple graph G on V, zero_forcing_poly G is the polynomial in Polynomial ℕ defined as the sum over all subsets…
  • is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
Used by 1

The proof, explained

The theorem equates the k-th coefficient of the zero forcing polynomial of G with the number of zero forcing vertex subsets of size k. By definition, the zero forcing polynomial is the sum over all vertex subsets S of X^{|S|} when S is a zero forcing set and 0 otherwise, so taking the k-th coefficient distributes across this finite sum. Expressing the count of zero forcing sets of size k as a sum of indicator values over all subsets, the identity reduces to verifying term by term that the k-th coefficient of each subset's contribution matches the indicator that the subset is a zero forcing set of size k.

  1. The number of zero forcing subsets of size k is represented as the sum over all vertex subsets S of an indicator: 1 if S is a zero forcing set with |S| = k, and 0 otherwise.

    Using classical logic, the set cardinality (`ncard`) is rewritten as the cardinality of the corresponding finite set (`Set.ncard_eq_toFinset_card'`). This finite set is shown to be the universe of all finite vertex subsets filtered by the property of being a zero forcing set of size k (`hfilter`), and `Finset.card_filter` transforms the cardinality of this filtered set into a sum of indicator values over all subsets.

    lines 4–10

    uses Set.ncard_eq_toFinset_card', Finset.card_filter

      classical
      rw [Set.ncard_eq_toFinset_card']
      have hfilter : ({S : Finset V | is_zero_forcing_set G (S : Set V) ∧ S.card = k} : Set (Finset V)).toFinset =
          Finset.univ.filter (fun S : Finset V => is_zero_forcing_set G (S : Set V) ∧ S.card = k) := by
        ext S
        simp
      rw [hfilter, Finset.card_filter]
  2. It suffices to show that for every vertex subset S, the k-th coefficient of its polynomial contribution equals the indicator that S is a zero forcing set of size k.

    By definition, `zero_forcing_poly G` is the sum over all subsets S of X^{|S|} if S is zero forcing and 0 otherwise. Taking the k-th coefficient distributes over this finite sum via `Polynomial.finsetSum_coeff`. By `Finset.sum_congr`, showing the two sums are equal reduces to proving that their summands agree for each subset S.

    lines 11–13

    uses Polynomial.finsetSum_coeff, Finset.sum_congr

      unfold zero_forcing_poly
      simp only [Polynomial.finsetSum_coeff]
      apply Finset.sum_congr rfl
  3. For every vertex subset S, the k-th coefficient of its term matches the indicator that S is a zero forcing set of size k.

    We introduce an arbitrary subset S and analyze cases on whether S is a zero forcing set: - If S is a zero forcing set, its term is X^{|S|}. We further split on whether |S| = k: if |S| = k, both sides evaluate to 1 since the k-th coefficient of X^k is 1 (`Polynomial.coeff_X_pow`); if |S| ≠ k, both sides evaluate to 0 because the k-th coefficient of X^{|S|} is 0 when |S| ≠ k (`Polynomial.coeff_X_pow`, `Ne.symm`). - If S is not a zero forcing set, its term is the zero polynomial, whose k-th coefficient is 0, matching the indicator value 0 on the right-hand side.

    lines 14–19

    uses Polynomial.coeff_X_pow, Ne.symm

      intro S hS
      by_cases hz : is_zero_forcing_set G (S : Set V)
      · by_cases hk : S.card = k
        · simp [hz, hk, Polynomial.coeff_X_pow]
        · simp [hz, hk, Polynomial.coeff_X_pow, Ne.symm hk]
      · simp [hz]
Set.ncard_eq_toFinset_card'
The cardinality `ncard` of a finite set is equal to the cardinality `card` of its representation as a `Finset`.
Finset.card_filter
The cardinality of a filtered finite set {x ∈ s | p x} equals the sum of indicator values ∑ x ∈ s, (if p x then 1 else 0).
Polynomial.finsetSum_coeff
The coefficient of degree n of a finite sum of polynomials is the sum of the degree-n coefficients of each polynomial.
Finset.sum_congr
Two sums over equal finite sets are equal if their terms agree at each element.
Polynomial.coeff_X_pow
The coefficient of degree n of X^k is 1 if n = k and 0 otherwise.
Ne.symm
Inequality is symmetric: a ≠ b implies b ≠ a.

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

theorem zero_forcing_poly_coeff {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k : ℕ) :    (zero_forcing_poly G).coeff k =      {S : Finset V | is_zero_forcing_set G (S : Set V) ∧ S.card = k}.ncard := by  classical  rw [Set.ncard_eq_toFinset_card']  have hfilter : ({S : Finset V | is_zero_forcing_set G (S : Set V) ∧ S.card = k} : Set (Finset V)).toFinset =      Finset.univ.filter (fun S : Finset V => is_zero_forcing_set G (S : Set V) ∧ S.card = k) := by    ext S    simp  rw [hfilter, Finset.card_filter]  unfold zero_forcing_poly  simp only [Polynomial.finsetSum_coeff]  apply Finset.sum_congr rfl  intro S hS  by_cases hz : is_zero_forcing_set G (S : Set V)  · by_cases hk : S.card = k    · simp [hz, hk, Polynomial.coeff_X_pow]    · simp [hz, hk, Polynomial.coeff_X_pow, Ne.symm hk]  · simp [hz]
See it in the graphDiscuss this resultChallenge it