Liggett's theorem

Ultra-log-concavity of coefficient sequences without internal zeros is preserved under products of polynomials. This is the ultra-log-concave analogue of Hoggar's theorem, and real-rooted polynomials with nonnegative coefficients are the basic examples.

Results

We call a nonnegative sequence $a_0,\dotsc,a_d$ ultra-log-concave of order $d$, written ULC($d$), if $a_k/\binom{d}{k}$ is log-concave: $$ k(d-k)\, a_k^2 \geq (k+1)(d-k+1)\, a_{k-1} a_{k+1} \qquad (0 < k < d). $$

Theorem (Liggett). Let $a$ be ULC($m$) and $b$ be ULC($n$), both nonnegative, vanishing beyond their order and without internal zeros. Then the convolution $c_k=\sum_i a_ib_{k-i}$ is ULC($m+n$) and has no internal zeros. Equivalently, for polynomials with nonnegative, ultra-log-concave coefficients without internal zeros, the product has ultra-log-concave coefficients of order its degree.

The hypothesis on internal zeros is needed: the sequence $1,0,0,1$ satisfies the displayed inequalities for $d=3$, but its product with $1+x$ does not satisfy them for $d=4$. By Newton's inequalities, the coefficients of a real-rooted polynomial of degree $d$ with nonnegative coefficients are ULC($d$).

Proof

We argue by induction on $n$, splitting $(n+1)b_j=(n+1-j)b_j+jb_j$ into two ULC($n$) sequences. These are likelihood-ratio ordered, since $b_j\,j!\,(n+1-j)!$ is log-concave. Convolution with the log-concave sequence $a$ preserves the ordering, by a $2\times2$ Cauchy–Binet argument as for Hoggar's theorem, and a real-number inequality combines the two induction hypotheses.

References

  1. [Gur09] Leonid Gurvits. A Short Proof, Based on Mixed Volumes, of Liggett's Theorem on the Convolution of Ultra-Logconcave Sequences. The Electronic Journal of Combinatorics, 16(1), 2009.
    BibTeX
    @article{Gurvits2009,
      author = {Gurvits, Leonid},
      title = {A {S}hort {P}roof, {B}ased on {M}ixed {V}olumes, of {L}iggett's {T}heorem on the {C}onvolution of {U}ltra-{L}ogconcave {S}equences},
      year = {2009},
      journal = {The Electronic Journal of Combinatorics},
      volume = {16},
      number = {1},
      doi = {10.37236/243},
      url = {https://doi.org/10.37236/243}
    }

Definitions

  • Ultra-log-concavity of order d

    RealRooted.CoeffUltraLogConcaveUpTosource
    def CoeffUltraLogConcaveUpTo (d : ℕ) (a : ℕ → ℝ) : Prop :=
      ∀ k, 0 < k → k < d →
        a (k - 1) * a (k + 1) * ((k + 1 : ℝ) * ((d - k + 1 : ℕ) : ℝ)) ≤
          a k ^ 2 * ((k : ℝ) * ((d - k : ℕ) : ℝ))

Theorems

  • Liggett: ultra-log-concavity is closed under productsMain result

    RealRooted.coeffUltraLogConcaveUpTo_mulsource
    theorem coeffUltraLogConcaveUpTo_mul {p q : ℝ[X]} (hp : ∀ k, 0 ≤ p.coeff k)
        (hpulc : CoeffUltraLogConcaveUpTo p.natDegree p.coeff)
        (hpniz : CoeffNoInternalZerosUpTo p.natDegree p.coeff) (hq : ∀ k, 0 ≤ q.coeff k)
        (hqulc : CoeffUltraLogConcaveUpTo q.natDegree q.coeff)
        (hqniz : CoeffNoInternalZerosUpTo q.natDegree q.coeff) :
        CoeffUltraLogConcaveUpTo (p * q).natDegree (p * q).coeff
  • Convolution of ULC(m) and ULC(n) sequences is ULC(m + n)

    RealRooted.coeffUltraLogConcaveUpTo_convsource
    theorem coeffUltraLogConcaveUpTo_conv {m n : ℕ} {a b : ℕ → ℝ} (ha : ∀ k, 0 ≤ a k)
        (has : ∀ k, m < k → a k = 0) (haulc : CoeffUltraLogConcaveUpTo m a)
        (haniz : CoeffNoInternalZerosUpTo m a) (hb : ∀ k, 0 ≤ b k) (hbs : ∀ k, n < k → b k = 0)
        (hbulc : CoeffUltraLogConcaveUpTo n b) (hbniz : CoeffNoInternalZerosUpTo n b) :
        CoeffUltraLogConcaveUpTo (m + n) (fun k => ∑ i ∈ range (k + 1), a i * b (k - i)) ∧
          CoeffNoInternalZerosUpTo (m + n) (fun k => ∑ i ∈ range (k + 1), a i * b (k - i))

Lean source RealRooted/Challenges/Roots/Liggett.lean at revision d6670742. Formalized 2026-10-07.