AFTD Auto-Formalizing Theoretical Domains

zero_forcing_poly_ulc_implies_log_concave

theoremverified

For any finite graph, ultra-log-concavity of its zero forcing coefficients implies ordinary log-concavity.

Statement

theorem zero_forcing_poly_ulc_implies_log_concave {V : Type*} [Fintype V] (G : SimpleGraph V) (h : ∀ k : ℕ, k + 2 ≤ Fintype.card V → (zero_forcing_poly G).coeff k * (zero_forcing_poly G).coeff (k + 2) * (Nat.choose (Fintype.card V) (k + 1)) ^ 2 ≤ ((zero_forcing_poly G).coeff (k + 1)) ^ 2 * Nat.choose (Fintype.card V) k * Nat.choose (Fintype.card V) (k + 2)) : ∀ k : ℕ, (zero_forcing_poly G).coeff k * (zero_forcing_poly G).coeff (k + 2) ≤ (zero_forcing_poly G).coeff (k + 1) * (zero_forcing_poly G).coeff (k + 1)
Source
A helper for tree_zero_forcing_poly_unimodal using the proposed ultra-log-concavity route.
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.

The proof, explained

The proof shows that ultra-log-concavity of the zero forcing polynomial coefficients implies ordinary log-concavity by splitting on whether the degree k + 2 exceeds the number of vertices |V|. When k + 2 ≤ |V|, the ultra-log-concavity bound is combined with the log-concavity of binomial coefficients, and the strictly positive factor (choose |V| (k + 1))^2 is cancelled from both sides. When k + 2 > |V|, the coefficient of degree k + 2 vanishes because no vertex subset can exceed |V| in size, making the inequality trivial.

  1. The m-th coefficient of the zero forcing polynomial is the sum over all vertex subsets S of the m-th coefficient of the indicator contribution for S.

    By definition, the zero forcing polynomial is the sum over all subsets S of X^|S| when S is a zero forcing set and 0 otherwise. Taking the m-th coefficient distributes across the finite sum via Polynomial.finsetSum_coeff.

    lines 4–10

    uses Polynomial.finsetSum_coeff

      classical
      have hcoeff : (zero_forcing_poly G).coeff m =
          ∑ S : Finset V,
            (if is_zero_forcing_set G (S : Set V) then Polynomial.X ^ S.card else 0 : Polynomial ℕ).coeff m := by
        rw [zero_forcing_poly]
        simp only [Polynomial.finsetSum_coeff]
      rw [hcoeff]
  2. If m > |V|, the m-th coefficient of the zero forcing polynomial is zero.

    Using Finset.sum_eq_zero, it suffices to show that each term vanishes. If S is not zero forcing, the term is 0 by definition. If S is zero forcing, its term is X^|S|; since |S| ≤ |V| < m by Finset.card_le_univ, m cannot equal |S|, so Polynomial.coeff_X_pow evaluates to 0 via if_neg.

    lines 11–17

    uses Finset.sum_eq_zero, if_pos, Polynomial.coeff_X_pow, if_neg, Finset.card_le_univ

      apply Finset.sum_eq_zero
      intro S _
      by_cases h : is_zero_forcing_set G (S : Set V)
      · rw [if_pos h, Polynomial.coeff_X_pow, if_neg]
        have hS : S.card ≤ Fintype.card V := Finset.card_le_univ S
        omega
      · simp [h]
  3. To show choose n k * choose n (k + 2) ≤ (choose n (k + 1))^2 for k + 2 ≤ n, it suffices to prove the inequality multiplied by (n - k) * (k + 2).

    Applying the absorption recurrence Nat.choose_succ_right_eq at k and k + 1 relates adjacent binomial coefficients. Since k + 2 ≤ n, both factors n - k and k + 2 are strictly positive, making their product positive by Nat.mul_pos. Cancelling this positive factor via Nat.le_of_mul_le_mul_right reduces the desired inequality to the scaled version.

    lines 23–30

    uses Nat.choose_succ_right_eq, Nat.mul_pos, Nat.le_of_mul_le_mul_right

      have hR1 : Nat.choose n (k + 1) * (k + 1) = Nat.choose n k * (n - k) :=
        Nat.choose_succ_right_eq n k
      have hR2 : Nat.choose n (k + 2) * (k + 2) = Nat.choose n (k + 1) * (n - (k + 1)) :=
        Nat.choose_succ_right_eq n (k + 1)
      have hsub : n - (k + 1) = n - k - 1 := by omega
      have hpos : 0 < (n - k) * (k + 2) := by
        apply Nat.mul_pos <;> omega
      refine Nat.le_of_mul_le_mul_right ?_ hpos
  4. Binomial coefficients are log-concave: choose n k * choose n (k + 2) ≤ (choose n (k + 1))^2 for k + 2 ≤ n.

    Multiplying choose n k * choose n (k + 2) by (n - k) * (k + 2) and rewriting with the absorption identities gives (choose n (k + 1))^2 * (k + 1) * (n - k - 1). Because k + 1 ≤ k + 2 and n - k - 1 ≤ n - k, we have (k + 1) * (n - k - 1) ≤ (n - k) * (k + 2). Multiplying by (choose n (k + 1))^2 via Nat.mul_le_mul_left finishes the inequality.

    lines 31–47

    uses Nat.mul_le_mul_left, Nat.mul_le_mul_right

      calc
        (Nat.choose n k * Nat.choose n (k + 2)) * ((n - k) * (k + 2))
            = (Nat.choose n k * (n - k)) * (Nat.choose n (k + 2) * (k + 2)) := by ring
        _ = (Nat.choose n (k + 1) * (k + 1)) * (Nat.choose n (k + 1) * (n - k - 1)) := by
              rw [hR1, hR2, hsub]
        _ = (Nat.choose n (k + 1) * Nat.choose n (k + 1)) * ((k + 1) * (n - k - 1)) := by ring
        _ ≤ (Nat.choose n (k + 1) * Nat.choose n (k + 1)) * ((n - k) * (k + 2)) := by
              apply Nat.mul_le_mul_left
              calc
                (k + 1) * (n - k - 1) ≤ (k + 1) * (n - k) := by
                  apply Nat.mul_le_mul_left
                  omega
                _ ≤ (k + 2) * (n - k) := by
                  apply Nat.mul_le_mul_right
                  omega
                _ = (n - k) * (k + 2) := by ring
        _ = Nat.choose n (k + 1) ^ 2 * ((n - k) * (k + 2)) := by ring
  5. To prove log-concavity at index k, split into cases depending on whether k + 2 ≤ |V|.

    We introduce the index k and perform a case distinction on the inequality k + 2 ≤ |V|.

    lines 50–51

      intro k
      by_cases hk : k + 2 ≤ Fintype.card V
  6. When k + 2 ≤ |V|, log-concavity reduces to cancelling (choose |V| (k + 1))^2 from both sides.

    Under k + 2 ≤ |V|, the ultra-log-concavity hypothesis bounds the product scaled by (choose |V| (k + 1))^2 by the product with binomial coefficients. By log-concavity of binomial coefficients (zero_forcing_poly_ulc_implies_log_concave_choose), this is bounded by (a_{k+1})^2 * (choose |V| (k + 1))^2. Since k + 1 ≤ |V|, choose |V| (k + 1) is positive by Nat.choose_pos, and its square is positive by Nat.pow_pos, justifying cancellation via Nat.le_of_mul_le_mul_right.

    lines 52–62

    uses zero_forcing_poly_ulc_implies_log_concave_choose, Nat.pow_pos, Nat.choose_pos, Nat.mul_le_mul_left, Nat.le_of_mul_le_mul_right

      · have h1 := h k hk
        have hbin := zero_forcing_poly_ulc_implies_log_concave_choose (Fintype.card V) k hk
        have hCpos : 0 < (Nat.choose (Fintype.card V) (k + 1)) ^ 2 := by
          apply Nat.pow_pos
          exact Nat.choose_pos (by omega)
        have h2 : ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *
            (Nat.choose (Fintype.card V) k * Nat.choose (Fintype.card V) (k + 2)) ≤
            ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *
            (Nat.choose (Fintype.card V) (k + 1)) ^ 2 :=
          Nat.mul_le_mul_left _ hbin
        refine Nat.le_of_mul_le_mul_right ?_ hCpos
  7. In the case k + 2 ≤ |V|, the log-concavity inequality a_k * a_{k+2} ≤ (a_{k+1})^2 holds.

    A calculational chain combines the ultra-log-concavity hypothesis and the binomial log-concavity bound to show (a_k * a_{k+2}) * (choose |V| (k + 1))^2 ≤ (a_{k+1})^2 * (choose |V| (k + 1))^2, which completes the case after cancelling the positive square.

    lines 63–75

        calc
          ((zero_forcing_poly G).coeff k * (zero_forcing_poly G).coeff (k + 2)) *
              (Nat.choose (Fintype.card V) (k + 1)) ^ 2
              = (zero_forcing_poly G).coeff k * (zero_forcing_poly G).coeff (k + 2) *
                  (Nat.choose (Fintype.card V) (k + 1)) ^ 2 := by ring
          _ ≤ ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *
                Nat.choose (Fintype.card V) k * Nat.choose (Fintype.card V) (k + 2) := h1
          _ = ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *
                (Nat.choose (Fintype.card V) k * Nat.choose (Fintype.card V) (k + 2)) := by ring
          _ ≤ ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *
                (Nat.choose (Fintype.card V) (k + 1)) ^ 2 := h2
          _ = ((zero_forcing_poly G).coeff (k + 1) * (zero_forcing_poly G).coeff (k + 1)) *
                (Nat.choose (Fintype.card V) (k + 1)) ^ 2 := by ring
  8. In the case k + 2 > |V|, the inequality holds because a_{k+2} = 0.

    When k + 2 > |V|, zero_forcing_poly_ulc_implies_log_concave_coeff_eq_zero shows that the coefficient a_{k+2} is 0. By Nat.mul_zero, the left-hand side evaluates to 0, which is trivially at most (a_{k+1})^2 by Nat.zero_le.

    lines 76–80

    uses zero_forcing_poly_ulc_implies_log_concave_coeff_eq_zero, Nat.mul_zero, Nat.zero_le

      · have hcard : Fintype.card V < k + 2 := by omega
        have hz : (zero_forcing_poly G).coeff (k + 2) = 0 :=
          zero_forcing_poly_ulc_implies_log_concave_coeff_eq_zero G hcard
        rw [hz, Nat.mul_zero]
        exact Nat.zero_le _
Polynomial.finsetSum_coeff
The coefficient of a finite sum of polynomials is the sum of their individual coefficients.
Finset.sum_eq_zero
A finite sum is zero if every term in the sum is zero.
if_pos
An if-then-else expression evaluates to the then-branch when the condition holds.
Polynomial.coeff_X_pow
The n-th coefficient of the monomial X^k is 1 if n = k and 0 otherwise.
if_neg
An if-then-else expression evaluates to the else-branch when the condition is false.
Finset.card_le_univ
The cardinality of any subset of a finite type is at most the total cardinality of the type.
Nat.choose_succ_right_eq
The absorption identity for binomial coefficients: (k + 1) * choose n (k + 1) = (n - k) * choose n k.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
Nat.le_of_mul_le_mul_right
A strictly positive factor can be cancelled from the right of an inequality of natural numbers.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers on the left by a natural number preserves the inequality.
Nat.mul_le_mul_right
Multiplying both sides of an inequality of natural numbers on the right by a natural number preserves the inequality.
zero_forcing_poly_ulc_implies_log_concave_choose
Binomial coefficients are log-concave: choose n k * choose n (k + 2) ≤ (choose n (k + 1))^2 for k + 2 ≤ n.
Nat.pow_pos
A strictly positive natural number raised to any power is strictly positive.
Nat.choose_pos
The binomial coefficient choose n k is strictly positive whenever k ≤ n.
zero_forcing_poly_ulc_implies_log_concave_coeff_eq_zero
The m-th coefficient of the zero forcing polynomial of a finite graph G is zero whenever m > |V|.
Nat.mul_zero
Multiplying any natural number by zero yields zero.
Nat.zero_le
Zero is less than or equal to any natural number.

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

private theorem zero_forcing_poly_ulc_implies_log_concave_coeff_eq_zero    {V : Type*} [Fintype V] (G : SimpleGraph V) {m : ℕ} (hm : Fintype.card V < m) :    (zero_forcing_poly G).coeff m = 0 := by  classical  have hcoeff : (zero_forcing_poly G).coeff m =      ∑ S : Finset V,        (if is_zero_forcing_set G (S : Set V) then Polynomial.X ^ S.card else 0 : Polynomial ℕ).coeff m := by    rw [zero_forcing_poly]    simp only [Polynomial.finsetSum_coeff]  rw [hcoeff]  apply Finset.sum_eq_zero  intro S _  by_cases h : is_zero_forcing_set G (S : Set V)  · rw [if_pos h, Polynomial.coeff_X_pow, if_neg]    have hS : S.card ≤ Fintype.card V := Finset.card_le_univ S    omega  · simp [h]private theorem zero_forcing_poly_ulc_implies_log_concave_choose    (n k : ℕ) (hk : k + 2 ≤ n) :    Nat.choose n k * Nat.choose n (k + 2) ≤      Nat.choose n (k + 1) ^ 2 := by  have hR1 : Nat.choose n (k + 1) * (k + 1) = Nat.choose n k * (n - k) :=    Nat.choose_succ_right_eq n k  have hR2 : Nat.choose n (k + 2) * (k + 2) = Nat.choose n (k + 1) * (n - (k + 1)) :=    Nat.choose_succ_right_eq n (k + 1)  have hsub : n - (k + 1) = n - k - 1 := by omega  have hpos : 0 < (n - k) * (k + 2) := by    apply Nat.mul_pos <;> omega  refine Nat.le_of_mul_le_mul_right ?_ hpos  calc    (Nat.choose n k * Nat.choose n (k + 2)) * ((n - k) * (k + 2))        = (Nat.choose n k * (n - k)) * (Nat.choose n (k + 2) * (k + 2)) := by ring    _ = (Nat.choose n (k + 1) * (k + 1)) * (Nat.choose n (k + 1) * (n - k - 1)) := by          rw [hR1, hR2, hsub]    _ = (Nat.choose n (k + 1) * Nat.choose n (k + 1)) * ((k + 1) * (n - k - 1)) := by ring    _ ≤ (Nat.choose n (k + 1) * Nat.choose n (k + 1)) * ((n - k) * (k + 2)) := by          apply Nat.mul_le_mul_left          calc            (k + 1) * (n - k - 1) ≤ (k + 1) * (n - k) := by              apply Nat.mul_le_mul_left              omega            _ ≤ (k + 2) * (n - k) := by              apply Nat.mul_le_mul_right              omega            _ = (n - k) * (k + 2) := by ring    _ = Nat.choose n (k + 1) ^ 2 * ((n - k) * (k + 2)) := by ringtheorem zero_forcing_poly_ulc_implies_log_concave {V : Type*} [Fintype V] (G : SimpleGraph V) (h : ∀ k : ℕ, k + 2 ≤ Fintype.card V → (zero_forcing_poly G).coeff k * (zero_forcing_poly G).coeff (k + 2) * (Nat.choose (Fintype.card V) (k + 1)) ^ 2 ≤ ((zero_forcing_poly G).coeff (k + 1)) ^ 2 * Nat.choose (Fintype.card V) k * Nat.choose (Fintype.card V) (k + 2)) : ∀ k : ℕ, (zero_forcing_poly G).coeff k * (zero_forcing_poly G).coeff (k + 2) ≤ (zero_forcing_poly G).coeff (k + 1) * (zero_forcing_poly G).coeff (k + 1) := by  intro k  by_cases hk : k + 2 ≤ Fintype.card V  · have h1 := h k hk    have hbin := zero_forcing_poly_ulc_implies_log_concave_choose (Fintype.card V) k hk    have hCpos : 0 < (Nat.choose (Fintype.card V) (k + 1)) ^ 2 := by      apply Nat.pow_pos      exact Nat.choose_pos (by omega)    have h2 : ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *        (Nat.choose (Fintype.card V) k * Nat.choose (Fintype.card V) (k + 2)) ≤        ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *        (Nat.choose (Fintype.card V) (k + 1)) ^ 2 :=      Nat.mul_le_mul_left _ hbin    refine Nat.le_of_mul_le_mul_right ?_ hCpos    calc      ((zero_forcing_poly G).coeff k * (zero_forcing_poly G).coeff (k + 2)) *          (Nat.choose (Fintype.card V) (k + 1)) ^ 2          = (zero_forcing_poly G).coeff k * (zero_forcing_poly G).coeff (k + 2) *              (Nat.choose (Fintype.card V) (k + 1)) ^ 2 := by ring      _ ≤ ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *            Nat.choose (Fintype.card V) k * Nat.choose (Fintype.card V) (k + 2) := h1      _ = ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *            (Nat.choose (Fintype.card V) k * Nat.choose (Fintype.card V) (k + 2)) := by ring      _ ≤ ((zero_forcing_poly G).coeff (k + 1)) ^ 2 *            (Nat.choose (Fintype.card V) (k + 1)) ^ 2 := h2      _ = ((zero_forcing_poly G).coeff (k + 1) * (zero_forcing_poly G).coeff (k + 1)) *            (Nat.choose (Fintype.card V) (k + 1)) ^ 2 := by ring  · have hcard : Fintype.card V < k + 2 := by omega    have hz : (zero_forcing_poly G).coeff (k + 2) = 0 :=      zero_forcing_poly_ulc_implies_log_concave_coeff_eq_zero G hcard    rw [hz, Nat.mul_zero]    exact Nat.zero_le _
See it in the graphDiscuss this resultChallenge it