Closure of interlacing under cones, affine combinations and shifts

Interlacing is preserved by nonnegative combinations of an interlacing sequence and by several affine and shift operations, and it gives real-rooted h-polynomials of shellings.

Results

Theorem (affine combinations, Brändén). Let $f,g$ be nonzero with nonnegative coefficients. If $(sx+t)f+g$ is real-rooted for all $s,t>0$, then $f\ll g$.

Theorem (cone lemma, Brändén and Saud Leite). [BL24, Lemma 3.1] Let $f_0,\dots,f_n$ be real-rooted with nonnegative coefficients, and suppose that $f_i\ll f_j$ for all $i<j\le n$. Then for all $\lambda_0,\dots,\lambda_n\ge0$ the combination $F=\sum_i\lambda_if_i$ satisfies $f_0\ll F\ll f_n$, where either side may be zero.

Theorem (affine derivative). Let $f$ be real-rooted of degree $d\ge1$ with positive leading coefficient and only nonpositive roots. If $c>d$, then $cf+(1-x)f'\ll f$.

Theorem (shift lemma). Let $h\ll f$, where both have positive leading coefficients and only nonpositive roots, and suppose that $h(0)\le f(0)$. Then $f\ll f+(x-1)h$.

Theorem (subtracting $xg$). Let $f,g$ be monic with $\deg f=\deg g+1$ and only nonpositive roots, and let $g\ll f$. If $f-xg$ has positive leading coefficient, then $g\ll f-xg\ll f$.

Theorem (shellings, Hlavacek and Solus). Let a finite simplicial complex with a shelling be subdivided. Suppose that, in some order, the h-polynomials of the relative pieces form an interlacing sequence of real-rooted polynomials with nonnegative coefficients, and that the h-polynomial of the subdivision is nonzero. Then the h-polynomial of the subdivision is real-rooted.

Proposition (polytopal shellings). Let a shelling of a graded face set be given by ordered, pairwise disjoint relative pieces that cover all faces. The h-polynomial is the sum of the h-polynomials of the relative pieces. If these, in some order, form a nonnegative interlacing sequence and the sum is nonzero, then the h-polynomial is real-rooted.

Theorem (half-open cubes). For $0\le l\le 2d$, let $h_{d,l}=A^{(2)}_{d,l}$ if $l\le d$ and $h_{d,l}=x\cdot I_dA^{(2)}_{d,2d-l}$ if $d<l$, where $I_d$ is reflection in degree $d$ and $A^{(2)}_{d,l}$ is the refined type-B Eulerian polynomial, defined as the Euler numerator of $t\mapsto(2t)^l(2t+1)^{d-l}$. These are the relative h-polynomials of half-open $d$-cubes. Then $A^{(2)}_{d,l}\ll A^{(2)}_{d,l+1}$ for $l<d$, and $h_{d,0},\dots,h_{d,2d}$ is a nonnegative interlacing sequence. Every sum, with repetitions, of members of a nonnegative interlacing sequence is real-rooted when it is nonzero. Consequently, if the h-polynomial of a polytopal shelling is nonzero and every relative h-polynomial is some $h_{d,l}$, then it is real-rooted.

Use

The cone lemma is the usual way to prove that a nonnegative sum of interlacing polynomials is real-rooted. The shelling theorems apply it to h-polynomials: a shelling splits the h-polynomial into relative pieces, and for cubes these pieces are refined type-B Eulerian polynomials.

Proof

The affine derivative, shift and subtraction statements are sign arguments at the roots of $f$: at such a root $r\le0$, the new polynomial takes the value $(1-r)f'(r)$, $(r-1)h(r)$ or $-r\,g(r)$ respectively, so it alternates in sign and the intermediate value theorem places its roots. The cone lemma follows by applying one-sided cone lemmas for finite sums to the two endpoint relations.

References

[Fis06], [Bra15, Lemma 7.8.4] and [BL24, Lemma 3.1]. See also the interlacing sequences on symmetricfunctions.com. For the shelling criterion, see [HS22, Theorem 3.1].

  1. [Fis06] Steve Fisk. Polynomials, roots, and interlacing. arXiv e-prints, 2006.
    BibTeX
    @article{Fisk2006x,
      Author = {Steve Fisk},
      Title = {Polynomials, roots, and interlacing},
      Year = {2006},
      Eprint = {arXiv:math/0612833},
      journal = {arXiv e-prints}
    }
  2. [Bra15] Petter Brändén. Unimodality, Log-Concavity, Real-Rootedness and Beyond. Handbook of enumerative combinatorics, 437-483, 2015.
    BibTeX
    @incollection{Branden2015,
      doi = {10.1201/b18255-10},
      year = {2015},
      month = mar,
      publisher = {Chapman and Hall/{CRC}},
      pages = {437--483},
      author = {Petter Br{\"{a}}nd{\'{e}}n},
      title = {Unimodality, Log-Concavity, Real-Rootedness and Beyond},
      booktitle = {Handbook of Enumerative Combinatorics}
    }
  3. [BL24] Petter Brändén & Leonardo Saud Maia Leite. Totally nonnegative matrices, chain enumeration and zeros of polynomials. arXiv e-prints, 2024.
    BibTeX
    @article{BrandenLeite2024x,
      author = {Petter Brändén and Leonardo Saud Maia Leite},
      title = {Totally nonnegative matrices, chain enumeration and zeros of polynomials},
      journal = {arXiv e-prints},
      Eprint = {2412.06595},
      url = {https://arxiv.org/abs/2412.06595},
      year = {2024}
    }
  4. [HS22, Theorem 3.1] Max Hlavacek & Liam Solus. Subdivisions of shellable complexes. Journal of Combinatorial Theory, Series A, 186, 105553, 2022.
    BibTeX
    @article{HlavacekSolus2022,
      author = {Max Hlavacek and Liam Solus},
      title = {Subdivisions of shellable complexes},
      year = {2022},
      journal = {Journal of Combinatorial Theory, Series A},
      volume = {186},
      pages = {105553},
      doi = {10.1016/j.jcta.2021.105553},
      eprint = {2003.07328v2}
    }

Definitions

  • The refined type-B Eulerian polynomial A_{d,l}^(2) as an Euler numerator

    RealRooted.HlavacekSolus.cubeColoredEuleriansource
    def cubeColoredEulerian (d l : ℕ) : ℝ[X] :=
      polynomialValueEulerNumerator (cubeValuePolynomial d l)
  • The 2d + 1 relative h-polynomials of the half-open d-cubes

    RealRooted.HlavacekSolus.cubeRelativeHRowsource
    def cubeRelativeHRow (d : ℕ) : List ℝ[X] :=
      List.ofFn fun l : Fin (2 * d + 1) => cubeRelativeHPolynomial d l

Theorems

  • Brändén: real-rooted affine combinations force interlacing

    RealRooted.strictInterl_of_forall_affine_mul_add_splitssource
    theorem strictInterl_of_forall_affine_mul_add_splits {f g : ℝ[X]}
        (hf0 : f ≠ 0) (hg0 : g ≠ 0) (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g)
        (haff : ∀ s t : ℝ, 0 < s → 0 < t → ((C s * X + C t) * f + g).Splits) :
        StrictInterl f g
  • A nonnegative combination of an interlacing sequence lies between its endsMain result

    RealRooted.interl_weightedSum_conesource
    theorem interl_weightedSum_cone {n : ℕ} (f : ℕ → ℝ[X]) (lam : ℕ → ℝ)
        (hstrictInterl : ∀ i j, i < j → j ≤ n → StrictInterl (f i) (f j))
        (hrr : ∀ i, i ≤ n → f i ≠ 0 ∧ (f i).Splits)
        (hnn : ∀ i, i ≤ n → HasNonnegCoeffs (f i))
        (hlam : ∀ i, 0 ≤ lam i) :
        Interl (f 0) (∑ i ∈ Finset.range (n + 1), C (lam i) * f i) ∧
          Interl (∑ i ∈ Finset.range (n + 1), C (lam i) * f i) (f n)
  • c f + (1 − x) f′ ≪ f for c > deg f

    RealRooted.strictInterl_affine_derivative_of_natDegree_ne_zerosource
    theorem strictInterl_affine_derivative_of_natDegree_ne_zero
        {f : ℝ[X]} (hf : f.Splits) (hdeg : f.natDegree ≠ 0)
        (hf_pos : HasPosLeadingCoeff f) (hroots_nonpos : ∀ r ∈ f.roots, r ≤ 0)
        {c : ℝ} (hc : (f.natDegree : ℝ) < c) :
        StrictInterl (C c * f + (1 - X) * f.derivative) f
  • Shift lemma: h ≪ f and h(0) ≤ f(0) give f ≪ f + (x − 1) h

    RealRooted.strictInterl_add_X_sub_one_mulsource
    theorem strictInterl_add_X_sub_one_mul {f h : ℝ[X]} (hhf : StrictInterl h f)
        (hf_pos : HasPosLeadingCoeff f) (hh_pos : HasPosLeadingCoeff h)
        (hf_nonpos : ∀ r ∈ f.roots, r ≤ 0) (hh_nonpos : ∀ r ∈ h.roots, r ≤ 0)
        (heval : h.eval 0 ≤ f.eval 0) :
        StrictInterl f (f + (X - 1) * h)
  • Subtracting x g: g ≪ f − x g ≪ f

    RealRooted.strictInterl_sub_X_mul_pair_of_posLeadingCoeffsource
    theorem strictInterl_sub_X_mul_pair_of_posLeadingCoeff {f g : ℝ[X]}
        (hgf : StrictInterl g f)
        (hf_monic : f.Monic) (hg_monic : g.Monic)
        (hdeg : g.natDegree + 1 = f.natDegree)
        (hf_nonpos : ∀ r ∈ f.roots, r ≤ 0)
        (hg_nonpos : ∀ r ∈ g.roots, r ≤ 0)
        (hsub_pos : HasPosLeadingCoeff (f - X * g)) :
        StrictInterl g (f - X * g) ∧ StrictInterl (f - X * g) f
  • Hlavacek–Solus: interlacing shelling pieces give a real-rooted h-polynomial

    RealRooted.HlavacekSolus.isRealRooted_hPolynomial_of_perm_isInterlacingSeqNonnegsource
    theorem isRealRooted_hPolynomial_of_perm_isInterlacingSeqNonneg
        (sub : Subdivision Base Subdivided) (sh : Shelling Base d)
        {ordered : List ℝ[X]}
        (hperm : ordered.Perm (relativePieceHPolynomials d sub sh))
        (hseq : IsInterlacingSeqNonneg ordered)
        (hpoly_ne : hPolynomial d Subdivided.faces ≠ 0) :
        hPolynomial d Subdivided.faces ≠ 0 ∧
          (hPolynomial d Subdivided.faces).Splits
  • The h-polynomial of a polytopal shelling is the sum of the relative h-polynomials

    RealRooted.HlavacekSolus.polytopalHPolynomial_eq_sum_relativePiecessource
    theorem polytopalHPolynomial_eq_sum_relativePieces
        (d : ℕ) (C : PolytopalFaceData α) (sh : PolytopalShelling C) :
        polytopalHPolynomial d C.rank C.faces =
          (polytopalRelativeHPolynomials d C sh).sum
  • Polytopal shellings with interlacing relative pieces have real-rooted h-polynomial

    RealRooted.HlavacekSolus.isRealRooted_polytopalHPolynomial_of_perm_interlacingNonnegsource
    theorem isRealRooted_polytopalHPolynomial_of_perm_interlacingNonneg
        (d : ℕ) (C : PolytopalFaceData α) (sh : PolytopalShelling C)
        {ordered : List ℝ[X]}
        (hperm : ordered.Perm (polytopalRelativeHPolynomials d C sh))
        (hseq : IsInterlacingSeqNonneg ordered)
        (hpoly_ne : polytopalHPolynomial d C.rank C.faces ≠ 0) :
        polytopalHPolynomial d C.rank C.faces ≠ 0 ∧
          (polytopalHPolynomial d C.rank C.faces).Splits
  • A_{d,l}^(2) interlaces A_{d,l+1}^(2) for l < d

    RealRooted.HlavacekSolus.cubeColoredEulerian_strictInterl_succsource
    theorem cubeColoredEulerian_strictInterl_succ {d l : ℕ} (hl : l + 1 ≤ d) :
        StrictInterl (cubeColoredEulerian d l) (cubeColoredEulerian d (l + 1))
  • Relative h-polynomials of half-open d-cubes form a nonnegative interlacing sequence

    RealRooted.HlavacekSolus.cubeRelativeHRow_isInterlacingSeqNonnegsource
    theorem cubeRelativeHRow_isInterlacingSeqNonneg (d : ℕ) :
        IsInterlacingSeqNonneg (cubeRelativeHRow d)
  • A nonzero sum of members of a nonnegative interlacing sequence is real-rooted

    RealRooted.isRealRooted_sum_of_mem_isInterlacingSeqNonnegsource
    theorem isRealRooted_sum_of_mem_isInterlacingSeqNonneg
        {fs pieces : List ℝ[X]} (hfs : IsInterlacingSeqNonneg fs)
        (hmem : ∀ p ∈ pieces, p ∈ fs) (hsum : pieces.sum ≠ 0) :
        pieces.sum ≠ 0 ∧ pieces.sum.Splits

Lean source RealRooted/Challenges/Interlacing/InterlacingClosure.lean at revision d6670742. Formalized 2026-10-06.