Operators preserving interlacing

Every linear operator that maps nonzero real-rooted polynomials to zero or to real-rooted polynomials preserves interlacing up to orientation. The operators $\theta=x\,d/dx$, $N-\theta$ and the reverse-Hermite transform preserve it with its orientation.

Results

A polynomial is PF if it has nonnegative coefficients and is zero or has only real, nonpositive roots. On this page $f\ll g$ also holds when $f$ or $g$ is zero, as in the zero-aware convention.

Theorem (real-rootedness preservers). Let $T$ be a real-linear operator on $\mathbb R[x]$ such that $Tp$ is zero or real-rooted for every nonzero real-rooted $p$. If $f\ll g$ with $f$ and $g$ nonzero, then $Tf\ll Tg$ or $Tg\ll Tf$.

Theorem (concrete operators).

Theorem (reverse-Hermite transform). Let $B_0=1$, $B_1=x$ and $B_{n+2}=x\bigl(B_{n+1}+(n+1)B_n\bigr)$, and let $R$ be the linear map with $R(x^n)=B_n$. Then $R$ maps PF polynomials to PF polynomials, and $p\ll q$ implies $Rp\ll Rq$ for PF $p,q$.

Theorem (from simple roots to PF; Brändén). Let $T$ be a real-linear operator, and suppose $Tq$ is PF for every $q$ with positive leading coefficient and simple, negative roots. Then $Tp$ is PF for every PF polynomial $p$. The same holds degree by degree: if this is assumed only for $q$ of degree at most $d$, then $Tp$ is PF for every PF polynomial $p$ of degree at most $d$.

Corollary (Euler bidiagonal step). If $a,b\ge0$, $ab>0$ and $p$ is PF, then $xp+(\theta+a)(\theta+b)p$ is PF.

Proof

For the transfer from simple roots to PF, a PF polynomial $p$ of degree $d$ is the coefficientwise limit as $\varepsilon\to0^+$ of $(1+\varepsilon D)^dp$, $D=d/dx$. These polynomials have degree $d$, positive leading coefficient and simple negative roots, and the PF cone is closed under coefficientwise limits of bounded degree.

References

  1. [Bra04] Petter Brändén. On Operators on Polynomials Preserving Real-Rootedness and the Neggers-Stanley Conjecture. Journal of Algebraic Combinatorics, 20(2), 119-130, 2004.
    BibTeX
    @article{Branden2004operators,
      title = {On Operators on Polynomials Preserving Real-Rootedness and the {N}eggers-{S}tanley Conjecture},
      volume = {20},
      ISSN = {0925-9899},
      url2 = {http://dx.doi.org/10.1023/B:JACO.0000047295.93525.df},
      DOI = {10.1023/b:jaco.0000047295.93525.df},
      number = {2},
      journal = {Journal of Algebraic Combinatorics},
      publisher = {Springer Science and Business Media LLC},
      author = {Petter Br{\"{a}}nd{\'{e}}n},
      year = {2004},
      month = sep,
      pages = {119–130}
    }
  2. [Bra06] Petter Brändén. On linear transformations preserving the Pólya frequency property. Transactions of the American Mathematical Society, 358(8), 3697-3716, 2006.
    BibTeX
    @article{Branden2006,
      title = {On linear transformations preserving the {P}{\'{o}}lya frequency property},
      volume = {358},
      ISSN = {1088-6850},
      url = {http://dx.doi.org/10.1090/S0002-9947-06-03856-6},
      DOI = {10.1090/s0002-9947-06-03856-6},
      number = {8},
      journal = {Transactions of the American Mathematical Society},
      publisher = {American Mathematical Society (AMS)},
      author = {Br{\"a}nd{\'e}n, Petter},
      year = {2006},
      month = feb,
      pages = {3697--3716}
    }

Definitions

  • Real-rootedness preserver

    RealRooted.PreservesRealRootedOrZerosource
    def PreservesRealRootedOrZero (T : ℝ[X] →ₗ[ℝ] ℝ[X]) : Prop :=
      ∀ p : ℝ[X], (p ≠ 0 ∧ p.Splits) → T p = 0 ∨ (T p).Splits
  • The Euler operator θ = x d/dx

    RealRooted.thetasource
    def theta (p : ℝ[X]) : ℝ[X] :=
      X * p.derivative
  • The polar Euler operator N − θ

    RealRooted.polarThetasource
    def polarTheta (N : ℕ) (p : ℝ[X]) : ℝ[X] :=
      C (N : ℝ) * p - theta p
  • The reciprocal x^D p(1/x)

    RealRooted.reciprocalShiftsource
    def reciprocalShift (D : ℕ) (p : ℝ[X]) : ℝ[X] :=
      p.reflect D

Theorems

  • Real-rootedness preservers preserve interlacingMain result

    RealRooted.PreservesRealRootedOrZero.interl_or_reversesourcestatement on symmetricfunctions.com
    theorem PreservesRealRootedOrZero.interl_or_reverse :
        ∀ T : ℝ[X] →ₗ[ℝ] ℝ[X],
          PreservesRealRootedOrZero T →
          PreservesInterlacingPairsUpToOrder0 T
  • θ preserves interlacing

    RealRooted.Interl.thetasource
    theorem Interl.theta {p q : ℝ[X]} (hpq : Interl p q) :
        Interl (theta p) (theta q)
  • N − θ preserves interlacing of PF polynomials of degree at most N

    RealRooted.Interl.polarThetasource
    theorem Interl.polarTheta {N : ℕ} {p q : ℝ[X]}
        (hp : IsPFPolynomial p) (hq : IsPFPolynomial q)
        (hpd : p.natDegree ≤ N) (hqd : q.natDegree ≤ N) (hpq : Interl p q) :
        Interl (polarTheta N p) (polarTheta N q)
  • The reciprocal reverses interlacing of PF polynomials

    RealRooted.StrictInterl.reciprocalShiftsource
    theorem StrictInterl.reciprocalShift {D : ℕ} {p q : ℝ[X]} (hp : IsPFPolynomial p)
        (hq : IsPFPolynomial q) (hpd : p.natDegree ≤ D) (hqd : q.natDegree ≤ D)
        (hpq : StrictInterl p q) :
        StrictInterl (reciprocalShift D q) (reciprocalShift D p)
  • The reverse-Hermite transform preserves PF polynomials

    RealRooted.IsPFPolynomial.reverseHermiteTransformsource
    theorem IsPFPolynomial.reverseHermiteTransform {p : ℝ[X]}
        (hp : IsPFPolynomial p) :
        IsPFPolynomial (reverseHermiteTransform p)
  • The reverse-Hermite transform preserves interlacing

    RealRooted.Interl.reverseHermiteTransformsource
    theorem Interl.reverseHermiteTransform {f g : ℝ[X]}
        (hf : IsPFPolynomial f) (hg : IsPFPolynomial g)
        (hfg : Interl f g) :
        Interl (reverseHermiteTransform f) (reverseHermiteTransform g)
  • Preserving simple negative-rooted inputs suffices for PF

    RealRooted.isPFPolynomial_map_of_isNegativeSimplesource
    theorem isPFPolynomial_map_of_isNegativeSimple
        (T : ℝ[X] →ₗ[ℝ] ℝ[X])
        (hT : ∀ {q : ℝ[X]}, IsNegativeSimple q → IsPFPolynomial (T q)) {p : ℝ[X]}
        (hp : IsPFPolynomial p) : IsPFPolynomial (T p)
  • The degree-local version of the strict-to-weak transfer

    RealRooted.isPFPolynomial_map_of_isNegativeSimple_of_natDegree_lesource
    theorem isPFPolynomial_map_of_isNegativeSimple_of_natDegree_le
        (T : ℝ[X] →ₗ[ℝ] ℝ[X]) {d : ℕ}
        (hT : ∀ {q : ℝ[X]}, IsNegativeSimple q ->
          q.natDegree ≤ d -> IsPFPolynomial (T q))
        {p : ℝ[X]} (hp : IsPFPolynomial p)
        (hpdeg : p.natDegree ≤ d) :
        IsPFPolynomial (T p)
  • Euler bidiagonal steps preserve PF polynomials

    RealRooted.IsPFPolynomial.eulerBidiagonal_stepsource
    theorem IsPFPolynomial.eulerBidiagonal_step {a b : ℝ}
        (ha : 0 ≤ a) (hb : 0 ≤ b) (hab : 0 < a * b)
        {p : ℝ[X]} (hp : IsPFPolynomial p) :
        IsPFPolynomial (EulerBidiagonal.step a b p)

Lean source RealRooted/Challenges/Preservers/OperatorPreservers.lean at revision d6670742. Formalized 2026-10-05.