Binary-run transformation

For each $n$, the binary-run transformation $J_n$ maps PF polynomials of degree at most $n$ to PF polynomials, and preserves interlacing on inputs of degree at most $(n+1)/2$. It yields the Narayana transformation theorem and Sturm sequences of Motzkin-type polynomials.

Results

A polynomial is PF (Pólya frequency) if it is zero or has nonnegative coefficients and only real, nonpositive roots. Let $J_n$ be the linear map with $J_n(1)=1$ and, for $1\le m\le n$, $$ J_n(x^m)=\frac1{\binom nm}\sum_k\binom{m-1}{k-1}\binom{n+1-m}{k}x^k . $$

Theorem (preservation). If $p$ is PF with $\deg p\le n$, then $J_np$ is PF. If moreover $p(0)>0$, then $J_np$ is real-rooted and all its roots are negative.

Theorem (interlacing). If $f\ll g$ have nonnegative coefficients and $\deg g\le\lfloor(n+1)/2\rfloor$, then $J_nf\ll J_ng$.

Theorem (interlacing across lengths). Let $\Theta=x\,d/dx$. If $g$ is PF with $g(0)\ne0$ and $2\le\deg g$ and $2\deg g\le n+1$, then $$ J_n\bigl((n+1)g-2\Theta g\bigr)\ll J_{n+1}(g). $$

Theorem (Motzkin-type rows). Let $\gamma$ be a PF multiplier sequence with $\gamma_m>0$ for all $m$. Put $$ G_n^\gamma(t)=\sum_{0\le m\le n/2}\frac{n!\,\gamma_m}{m!\,(n-2m)!}\,t^m,\qquad R_n^\gamma=J_n\bigl(G_n^\gamma\bigr). $$ Then $R_n^\gamma\ll R_{n+1}^\gamma$ for all $n$. This applies to $\gamma_m=1/(\alpha)_m$ for every $\alpha>0$, where $(\alpha)_m=\alpha(\alpha+1)\dotsm(\alpha+m-1)$. Writing $R_n^{(\alpha)}$ for these rows, $R_n^{(\alpha+1)}\ll R_n^{(\alpha)}$ for all $n$ and $\alpha>0$. The case $\alpha=2$, $\gamma_m=1/(m+1)!$, gives the Motzkin ascent polynomials (OEIS A114580).

Theorem (balanced run transformation). Let $n\ge2$, and let $K_n$ be the linear map with $$ K_n(x^m)=\frac1{\binom nm}\sum_k\binom mk\binom{n-m}{k}x^k . $$ If $p$ is PF and $\deg p\le\lfloor(n+1)/2\rfloor$, then $K_np$ is PF. If $f\ll g$ have nonnegative coefficients and $\deg g\le\lfloor(n+1)/2\rfloor$, then $K_nf\ll K_ng$.

Use

The map $x^m\mapsto\frac1{m+1}\binom nm J_n(x^m)$ is $J_n$ composed with a diagonal multiplier sequence. Combined with the preservation of PF polynomials by that multiplier, the preservation theorem gives the Narayana transformation theorem [MW26].

Proof

For preservation, we scale the input by a parameter. At parameter zero the rescaled image is a Schur–Szegő composition with the path-matching polynomial $\sum_k\binom{n+1-k}kx^k$, and the stability method of [BB09] fixes the sign of every critical value of the image as the parameter grows, so no two roots collide. Interlacing follows from the monomial-chain criterion, and the cross-length and Motzkin theorems from linear identities between $J_n$, $J_{n+1}$ and $K_n$.

References

  1. [BB09] Julius Borcea & Petter Brändén. The Lee–Yang and Pólya–Schur programs. I. Linear operators preserving stability. Inventiones mathematicae, 177(3), 541-569, 2009.
    BibTeX
    @article{BorceaBranden2009I,
      doi = {10.1007/s00222-009-0189-3},
      url2 = {https://doi.org/10.1007/s00222-009-0189-3},
      year = {2009},
      month = mar,
      publisher = {Springer Science and Business Media {LLC}},
      volume = {177},
      number = {3},
      pages = {541--569},
      author = {Julius Borcea and Petter Br{\"{a}}nd{\'{e}}n},
      title = {The {L}ee--{Y}ang and {P}{\'{o}}lya--{S}chur programs. {I}. {L}inear operators preserving stability},
      journal = {Inventiones mathematicae}
    }
  2. [MW26] Jianxi Mao & Lijie Wang. The Narayana transformation. arXiv e-prints, 2026.
    BibTeX
    @article{MaoWang2026x,
      author = {Jianxi Mao and Lijie Wang},
      title = {The {N}arayana transformation},
      year = {2026},
      eprint = {2607.01572},
      url = {https://arxiv.org/abs/2607.01572},
      journal = {arXiv e-prints}
    }

Definitions

  • Binary-run basis polynomials

    RealRooted.binaryRunPolynomialsource
    def binaryRunPolynomial (n m : ℕ) : ℝ[X] :=
      if m = 0 then 1
      else
        ∑ k ∈ Finset.Icc 1 n,
          monomial k
            (((Nat.choose (m - 1) (k - 1) : ℝ) *
                (Nat.choose (n + 1 - m) k : ℝ)) /
              (Nat.choose n m : ℝ))
  • Binary-run transformation

    RealRooted.binaryRunTransformsource
    def binaryRunTransform (n : ℕ) (p : ℝ[X]) : ℝ[X] :=
      Polynomial.basisTransform (binaryRunPolynomial n) p
  • Multiplier-weighted Motzkin rows

    RealRooted.motzkinWeightedRowsource
    def motzkinWeightedRow (γ : ℕ → ℝ) (n : ℕ) : ℝ[X] :=
      binaryRunTransform n (motzkinWeightedInput γ n)
  • Balanced run transformation

    RealRooted.balancedRunTransformsource
    def balancedRunTransform (n : ℕ) (p : ℝ[X]) : ℝ[X] :=
      Polynomial.basisTransform (balancedRunPolynomial n) p

Theorems

  • J_n maps PF polynomials of degree at most n to PF polynomials

    RealRooted.IsPFPolynomial.binaryRunTransformsource
    theorem IsPFPolynomial.binaryRunTransform
        {n : ℕ} {p : ℝ[X]} (hp : IsPFPolynomial p)
        (hpdeg : p.natDegree ≤ n) :
        IsPFPolynomial (binaryRunTransform n p)
  • A PF input with positive constant term has an image with only negative roots

    RealRooted.binaryRunTransform_splits_and_roots_negsource
    theorem binaryRunTransform_splits_and_roots_neg {n : ℕ} {p : ℝ[X]}
        (hp : IsPFPolynomial p) (hpdeg : p.natDegree ≤ n)
        (hconst : 0 < p.coeff 0) :
        (binaryRunTransform n p).Splits ∧
          ∀ r ∈ (binaryRunTransform n p).roots, r < 0
  • J_n preserves interlacing on inputs of degree at most (n+1)/2Main result

    RealRooted.strictInterl_binaryRunTransformsource
    theorem strictInterl_binaryRunTransform
        {n : ℕ} {f g : ℝ[X]}
        (hfg : StrictInterl f g)
        (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g)
        (hgdeg : g.natDegree ≤ (n + 1) / 2) :
        StrictInterl (binaryRunTransform n f) (binaryRunTransform n g)
  • J_n of (n+1)g - 2Θg interlaces J_{n+1} g

    RealRooted.strictInterl_binaryRunTransform_succsource
    theorem strictInterl_binaryRunTransform_succ
        {n : ℕ} {g : ℝ[X]} (hg : IsPFPolynomial g) (hg0 : g.coeff 0 ≠ 0)
        (hdeg2 : 2 ≤ g.natDegree) (hdeg : 2 * g.natDegree ≤ n + 1) :
        StrictInterl (binaryRunTransform n (C ((n : ℝ) + 1) * g - C 2 * theta g))
          (binaryRunTransform (n + 1) g)
  • Weighted Motzkin rows form a Sturm chain

    RealRooted.motzkinWeightedRow_strictInterl_succsource
    theorem motzkinWeightedRow_strictInterl_succ {γ : ℕ → ℝ}
        (hγ : IsPFMultiplierSequence γ) (hpos : ∀ m, 0 < γ m) (n : ℕ) :
        StrictInterl (motzkinWeightedRow γ n) (motzkinWeightedRow γ (n + 1))
  • The Sturm chain for γ_m = 1/(α)_m

    RealRooted.motzkinWeightedRow_inv_ascPochhammer_strictInterl_succsource
    theorem motzkinWeightedRow_inv_ascPochhammer_strictInterl_succ {α : ℝ} (hα : 0 < α)
        (n : ℕ) :
        StrictInterl
          (motzkinWeightedRow (fun m => ((ascPochhammer ℝ m).eval α)⁻¹) n)
          (motzkinWeightedRow (fun m => ((ascPochhammer ℝ m).eval α)⁻¹) (n + 1))
  • Monotonicity in α

    RealRooted.motzkinWeightedRow_inv_ascPochhammer_succ_strictInterlsource
    theorem motzkinWeightedRow_inv_ascPochhammer_succ_strictInterl {α : ℝ} (hα : 0 < α)
        (n : ℕ) :
        StrictInterl
          (motzkinWeightedRow (fun m => ((ascPochhammer ℝ m).eval (α + 1))⁻¹) n)
          (motzkinWeightedRow (fun m => ((ascPochhammer ℝ m).eval α)⁻¹) n)
  • The rows with weights 1/(m+1)! form a Sturm chain

    RealRooted.motzkinAscentRow_strictInterl_succsource
    theorem motzkinAscentRow_strictInterl_succ (n : ℕ) :
        StrictInterl
          (motzkinWeightedRow (fun m => (((m + 1).factorial : ℕ) : ℝ)⁻¹) n)
          (motzkinWeightedRow (fun m => (((m + 1).factorial : ℕ) : ℝ)⁻¹) (n + 1))
  • The balanced run transformation maps PF polynomials of low degree to PF polynomials

    RealRooted.IsPFPolynomial.balancedRunTransformsource
    theorem IsPFPolynomial.balancedRunTransform
        {n : ℕ} (hn : 2 ≤ n) {p : ℝ[X]} (hp : IsPFPolynomial p)
        (hdegree : p.natDegree ≤ (n + 1) / 2) :
        IsPFPolynomial (balancedRunTransform n p)
  • The balanced run transformation preserves interlacing on low-degree inputs

    RealRooted.strictInterl_balancedRunTransformsource
    theorem strictInterl_balancedRunTransform
        {n : ℕ} (hn : 2 ≤ n) {f g : ℝ[X]}
        (hfg : StrictInterl f g)
        (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g)
        (hgdeg : g.natDegree ≤ (n + 1) / 2) :
        StrictInterl (balancedRunTransform n f) (balancedRunTransform n g)

Lean source RealRooted/Challenges/Preservers/BinaryRunTransformation.lean at revision d6670742. Formalized 2026-09-28.