zero_forcing_poly_ulc_implies_log_concave
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.
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.
uses
Polynomial.finsetSum_coeffclassical 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]
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.
uses
Finset.sum_eq_zero,if_pos,Polynomial.coeff_X_pow,if_neg,Finset.card_le_univapply 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]
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.
uses
Nat.choose_succ_right_eq,Nat.mul_pos,Nat.le_of_mul_le_mul_righthave 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
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.
uses
Nat.mul_le_mul_left,Nat.mul_le_mul_rightcalc (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
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|.
intro k by_cases hk : k + 2 ≤ Fintype.card V
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.
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
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.
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
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.
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.
- In paper proofs, coefficients of the zero forcing polynomial of degree exceeding |V| are vacuously zero since no subset of vertices can have size greater than |V|; in Lean, this is explicitly proved as the private helper lemma zero_forcing_poly_ulc_implies_log_concave_coeff_eq_zero.
- Ultra-log-concavity is stated over ℕ by clearing denominators to avoid division and rational numbers.
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.
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 _