Brändén's E transform

The E transform sends $x^n$ to the $n$th ordered Bell polynomial. It maps real-rooted polynomials with all roots in $[-1,0]$ to PF polynomials, and it turns the rootwise order on such polynomials into interlacing.

Results

A polynomial is PF (Pólya frequency) if it is zero or has nonnegative coefficients and only real, nonpositive roots. The ordered Bell polynomials are $$ F_0=1,\qquad F_{n+1}=x\,F_n+x(1+x)\,F_n', $$ so that $F_n=\sum_k k!\,S(n,k)\,x^k$ with $S(n,k)$ the Stirling numbers of the second kind; $F_n(1)$ is the $n$th ordered Bell number. The E transform is the linear map with $E(x^n)=F_n$. It satisfies $E\bigl(x(x-1)\dotsm(x-n+1)\bigr)=n!\,x^n$.

Theorem (Brändén). Let $p$ be a real-rooted polynomial with all roots in $[-1,0]$. Then $E(p)$ is zero or real-rooted with only nonpositive roots. If $p$ has positive leading coefficient, then $E(p)$ is PF.

Theorem (interlacing basis). For $0\le k\le n$ let $b_{n,k}=E\bigl(x^k(x+1)^{n-k}\bigr)$. Then $b_{n,i}\ll b_{n,j}$ for all $0\le i\le j\le n$. In particular $F_n=b_{n,n}$ is PF.

Theorem (rootwise order; Brändén). Let $f,g$ be monic and real-rooted of the same degree $n\ge1$ with all roots in $[-1,0]$, and suppose that their roots, sorted increasingly, satisfy $f\le g$ coordinatewise. Then $E(f)\ll E(g)$ [Bra06, Thm. 4.6]. More precisely, for all real $u\le v$ and every monic real-rooted $h$ with roots in $[-1,0]$, $$ E\bigl((x-u)h\bigr)\ll E\bigl((x-v)h\bigr). $$

Proof

A polynomial with all roots in $[-1,0]$ is a nonnegative combination of the polynomials $x^k(x+1)^{n-k}$. The images $b_{n,k}$ arise by steps $f\mapsto(x+r)f+x(1+x)f'$, which preserve interlacing, and a nonnegative combination of an interlacing sequence is real-rooted. The rootwise statement follows by moving one root at a time.

References

  1. [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

  • Ordered Bell polynomials F_n

    RealRooted.orderedBellPolynomialsource
    def orderedBellPolynomial : ℕ → R[X]
      | 0 => 1
      | n + 1 =>
          X * orderedBellPolynomial n +
            X * (1 + X) * (orderedBellPolynomial n).derivative
  • The E transform x^n ↦ ordered Bell polynomial

    RealRooted.brandenEsource
    def brandenE (p : R[X]) : R[X] :=
      Polynomial.basisTransform (orderedBellPolynomial (R := R)) p
  • Images E(x^k (x + 1)^(n − k))

    RealRooted.brandenBasisImagesource
    def brandenBasisImage (n k : ℕ) : R[X] :=
      brandenE (brandenBinomialBasis n k)

Theorems

  • Positive leading coefficient and roots in [−1, 0] give a PF image

    RealRooted.brandenE_isPFPolynomial_of_roots_mem_Iccsource
    theorem brandenE_isPFPolynomial_of_roots_mem_Icc
        {p : ℝ[X]} (hp : p.Splits) (hlead : HasPosLeadingCoeff p)
        (hroots : ∀ r ∈ p.roots, r ∈ Set.Icc (-1 : ℝ) 0) :
        IsPFPolynomial (brandenE p)
  • Roots in [−1, 0] give zero or a real-rooted image with nonpositive roots

    RealRooted.brandenE_eq_zero_or_splits_and_roots_nonpossource
    theorem brandenE_eq_zero_or_splits_and_roots_nonpos
        {p : ℝ[X]} (hp : p.Splits)
        (hroots : ∀ r ∈ p.roots, r ∈ Set.Icc (-1 : ℝ) 0) :
        brandenE p = 0 ∨
          (brandenE p ≠ 0 ∧ (brandenE p).Splits ∧
            ∀ r ∈ (brandenE p).roots, r ≤ 0)
  • The images of the binomial basis form an interlacing sequence

    RealRooted.brandenBasisImage_strictInterlsource
    theorem brandenBasisImage_strictInterl
        (n i j : ℕ) (hij : i ≤ j) (hj : j ≤ n) :
        StrictInterl (brandenBasisImage (R := ℝ) n i) (brandenBasisImage n j)
  • Ordered Bell polynomials are PF polynomials

    RealRooted.orderedBellPolynomial_isPFPolynomialsource
    theorem orderedBellPolynomial_isPFPolynomial (n : ℕ) :
        IsPFPolynomial (orderedBellPolynomial (R := ℝ) n)
  • E sends x(x − 1)⋯(x − n + 1) to n! xⁿ

    RealRooted.brandenE_descPochhammersource
    theorem brandenE_descPochhammer [CommRing R] :
        ∀ n : ℕ,
          brandenE (descPochhammer R n) = C (n.factorial : R) * X ^ n
  • Rootwise order of polynomials with roots in [-1, 0] gives interlacing E-imagesMain result

    RealRooted.brandenE_strictInterl_of_rootwiseLEsource
    theorem brandenE_strictInterl_of_rootwiseLE
        {f g : ℝ[X]} {n : ℕ}
        (hf_monic : f.Monic) (hg_monic : g.Monic)
        (hf_splits : f.Splits) (hg_splits : g.Splits)
        (hf_degree : f.natDegree = n) (hg_degree : g.natDegree = n)
        (hn : n ≠ 0)
        (hf_roots : ∀ r ∈ f.roots, (-1 : ℝ) ≤ r ∧ r ≤ 0)
        (hg_roots : ∀ r ∈ g.roots, (-1 : ℝ) ≤ r ∧ r ≤ 0)
        (hfg : RootwiseLE f g) :
        StrictInterl (brandenE f) (brandenE g)
  • Moving one root to the right gives interlacing images

    RealRooted.brandenE_strictInterl_one_root_replacementsource
    theorem brandenE_strictInterl_one_root_replacement
        {h : ℝ[X]} {u v : ℝ}
        (hmonic : h.Monic) (hsplits : h.Splits)
        (hroots : ∀ r ∈ h.roots, (-1 : ℝ) ≤ r ∧ r ≤ 0)
        (huv : u ≤ v) :
        StrictInterl (brandenE ((X - C u) * h))
          (brandenE ((X - C v) * h))

Lean source RealRooted/Challenges/Preservers/BrandenETransform.lean at revision d6670742. Formalized 2026-09-14.