Interlacing and real roots under symmetric decompositions

For a polynomial with a symmetric $I_d$-decomposition $p=a+xb$, five interlacing conditions on $a$, $b$, $p$ are equivalent. The derangement transform of nonnegative combinations of $x^k(1+x)^{d-k}$ is real-rooted and lies between two Eulerian-type polynomials.

Results

Put $I_d(p)=x^dp(1/x)$ and $R_d(p)(x)=(-1)^dp(-1-x)$. An $I_d$-decomposition of $p$ is a pair $(a,b)$ with $p=a+xb$, $\deg a\le d$, $\deg b\le d-1$, $I_d(a)=a$ and $I_{d-1}(b)=b$.

Theorem (equivalences). Let $\deg p\le d$, and let $(a,b)$ be an $I_d$-decomposition of $p$ with $a,b\ne0$ and nonnegative coefficients. Put $f=\sum_kp_k\,x^k(1+x)^{d-k}$. Then the following are equivalent: $$ b\ll a,\qquad a\ll p,\qquad b\ll p,\qquad I_d(p)\ll p,\qquad R_d(f)\ll f . $$

Derangement polynomials. Let $d_n(x)=\sum_\sigma x^{\operatorname{exc}\sigma}$, summed over the derangements $\sigma$ of $n$ letters, where $\operatorname{exc}\sigma$ counts the $i$ with $i<\sigma(i)$. For $n\ge2$, $d_n$ is nonzero and real-rooted.

Theorem (derangement transform). Let $D$ be the linear map with $D(x^j)=d_j$, let $d\ge0$ and let $c_0,\dots,c_d\ge0$. Then $D\bigl(\sum_kc_kx^k(1+x)^{d-k}\bigr)$ has nonnegative coefficients and is zero or real-rooted with nonpositive roots. If $d\ge2$ and some $c_k>0$, it is nonzero and $$ D\bigl((1+x)^d\bigr)\ \ll\ D\Bigl(\sum_kc_kx^k(1+x)^{d-k}\Bigr)\ \ll\ d_d $$ [BS19, Cor. 3.7].

Use

The equivalences reduce interlacing of $p$ with its symmetric pieces to interlacing of the simpler pair $b\ll a$. See also the symmetric-decomposition overview on symmetricfunctions.com.

Proof

The derangement transform is the Chow-derangement transform of the Pascal matrix, whose resolving rows are the polynomials $x^k(1+x)^{d-k}$; the theorem is a case of the Brändén–Vecchi Chow-resolution theorem.

References

  1. [BS19] Petter Brändén & Liam Solus. Symmetric Decompositions and Real-Rootedness. International Mathematics Research Notices, 2021(10), 7764-7798, 2019.
    BibTeX
    @article{BrandenSolus2019,
      title = {Symmetric Decompositions and Real-Rootedness},
      volume = {2021},
      ISSN = {1687-0247},
      url = {http://dx.doi.org/10.1093/imrn/rnz059},
      DOI = {10.1093/imrn/rnz059},
      number = {10},
      journal = {International Mathematics Research Notices},
      publisher = {Oxford University Press (OUP)},
      author = {Br\"{a}ndén, Petter and Solus, Liam},
      year = {2019},
      month = apr,
      pages = {7764--7798}
    }

Definitions

  • Symmetric I_d-decomposition

    RealRooted.IsIdDecompositionsource
    def IsIdDecomposition (d : ℕ) (p a b : ℝ[X]) : Prop :=
      p = a + X * b ∧
      a.natDegree ≤ d ∧
      b.natDegree ≤ d - 1 ∧
      idTransform d a = a ∧
      idTransform (d - 1) b = b
  • Derangement transform x^j ↦ d_j

    RealRooted.DerangementTransform.transformsource
    def transform : ℝ[X] →ₗ[ℝ] ℝ[X] :=
      Polynomial.basisTransformₗ polynomial

Theorems

  • Five interlacing conditions on p = a + xb are equivalentMain result

    RealRooted.BrandenSolus.strictInterl_iff_of_isIdDecompositionsource
    theorem BrandenSolus.strictInterl_iff_of_isIdDecomposition :
        ∀ {d : ℕ} {p a b : ℝ[X]},
          p.natDegree ≤ d →
          IsIdDecomposition d p a b →
          HasNonnegCoeffs a →
          HasNonnegCoeffs b →
          a ≠ 0 →
          b ≠ 0 →
          (StrictInterl b a ↔ StrictInterl a p) ∧
          (StrictInterl a p ↔ StrictInterl b p) ∧
          (StrictInterl b p ↔ StrictInterl (idTransform d p) p) ∧
          (StrictInterl (idTransform d p) p ↔
            StrictInterl (rdTransform d (fPolynomial d p)) (fPolynomial d p))
  • The derangement image of a nonnegative magic-basis combination is zero or real-rooted

    RealRooted.DerangementTransform.transform_magicExpansion_isPFsource
    theorem transform_magicExpansion_isPF {d : ℕ} {c : ℕ → ℝ}
        (hc : ∀ k, k ≤ d → 0 ≤ c k) :
        IsPFPolynomial (transform (magicExpansion d c))
  • For d ≥ 2 and a positive coordinate, the image lies between A_d and d_d

    RealRooted.DerangementTransform.transform_magicExpansion_strictInterlsource
    theorem transform_magicExpansion_strictInterl {d : ℕ} (hd : 2 ≤ d) {c : ℕ → ℝ}
        (hc : ∀ k, k ≤ d → 0 ≤ c k) (hpos : ∃ k, k ≤ d ∧ 0 < c k) :
        StrictInterl (transform ((1 + X) ^ d)) (transform (magicExpansion d c)) ∧
          StrictInterl (transform (magicExpansion d c)) (polynomial d)
  • Derangements counted by excedances give the derangement polynomials d_n

    RealRooted.DerangementStatistic.derangementExcGenPoly_eq_polynomialsource
    theorem derangementExcGenPoly_eq_polynomial :
        ∀ n, derangementExcGenPoly n = DerangementTransform.polynomial n
  • The excedance polynomial of derangements is real-rooted for n ≥ 2

    RealRooted.DerangementStatistic.derangementExcGenPoly_isRealRootedsource
    theorem derangementExcGenPoly_isRealRooted {n : ℕ} (hn : 2 ≤ n) :
        derangementExcGenPoly n ≠ 0 ∧ (derangementExcGenPoly n).Splits

Lean source RealRooted/Challenges/Combinatorial/BrandenSolus.lean at revision d6670742. Formalized 2026-10-02.