The binary-run transformation

For fixed $n$, the linear map binaryRunTransform n sends $1$ to $1$ and sends $X^m$, for $1 \leq m \leq n$, to

\frac{1}{\binom{n}{m}} \sum_k \binom{m-1}{k-1}\binom{n+1-m}{k} X^k.

If the input has degree at most $n$, nonnegative coefficients, and only real nonpositive zeros, then its image has the same properties. If the input has positive constant coefficient, every zero of the image is strictly negative.

The fixed-sum Narayana-type transform is the reweighted version with basis images

T_n(X^m) = \frac{\binom{n}{m}}{m+1}\, \mathtt{binaryRunPolynomial}\ n\ m.

Equivalently, it is binaryRunTransform n after the standard finite Narayana/Schur–Szegő diagonal multiplier. Thus this preservation theorem, together with preservation by that multiplier, gives the corresponding Narayana transformation theorem.

Interlacing

On inputs of degree at most $(n+1)/2$, the transform also preserves interlacing. With $N = n + 1$ and $\Theta = x\, d/dx$, it transports interlacing across lengths: for a PF polynomial $g$ with $g(0) \neq 0$ and $2 \leq \deg g \leq N/2$,

J_n\bigl((N - 2\Theta)\, g\bigr) \ll J_{n+1}(g).

For a PF multiplier sequence $\gamma$ with positive entries, put $G_n^{\gamma}(t) = \sum_m \frac{n!\,\gamma_m}{m!\,(n-2m)!}\, t^m$, a weighted matching polynomial of the complete graph. These satisfy $(N-2\Theta)\, G_N^{\gamma} = N G_n^{\gamma}$, so the rows $R_n^{\gamma} = J_n(G_n^{\gamma})$ form a Sturm chain: $R_n^{\gamma} \ll R_{n+1}^{\gamma}$ for all $n$. This holds in particular for $\gamma_m = 1/(\alpha)_m$ with $\alpha > 0$. The case $\alpha = 2$, where $\gamma_m = 1/(m+1)!$, gives the Motzkin-ascent polynomials (OEIS A114580).

The rows also move monotonically in $\alpha$. Write $P_n^{(\alpha)}$ for the row with $\gamma_m = 1/(\alpha)_m$. Then $P_n^{(\alpha+1)} \ll P_n^{(\alpha)}$ for every $n$ and every $\alpha > 0$. The proof uses the shift identity $\alpha\, G_n^{(\alpha)} = (\Theta + \alpha)\, G_n^{(\alpha+1)}$, which follows from $\alpha\, (\alpha+1)_m = (\alpha+m)(\alpha)_m$. A PF polynomial $g$ of degree at least 2 satisfies $g \ll (\Theta + \alpha)\, g$, and the transform preserves interlacing. The rows with $n \leq 3$ are linear or constant and are checked directly.

Proof idea

After scaling the input factors, a stable pointing construction controls the motion of every critical value of the output. A polarized path-matching polynomial supplies the small-parameter anchor, and the critical-value sign prevents collisions throughout the deformation.

References

The stability-preserving contraction uses the algebraic-symbol machinery of J. Borcea and P. Brändén, “The Lee–Yang and Pólya–Schur programs. I. Linear operators preserving stability,” Inventiones Mathematicae 177 (2009), 541–569. For the related transform, see J. Mao and L. Wang, “The Narayana transformation,” arXiv:2607.01572 (2026).

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

Theorems

The transformation preserves PF polynomials

RealRooted.Challenges.BinaryRunTransformation.preservesPFsource

theorem preservesPF {n : ℕ} {p : ℝ[X]}
    (hp : IsPFPolynomial p) (hpdeg : p.natDegree ≤ n) :
    IsPFPolynomial (binaryRunTransform n p)

Positive constant term gives strictly negative zeros

RealRooted.Challenges.BinaryRunTransformation.preservesStrictlyNegativeRootssource

theorem preservesStrictlyNegativeRoots {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

The transformation preserves interlacing

RealRooted.strictInterl_binaryRunTransformsource

theorem strictInterl_binaryRunTransform
    {n : ℕ} {f g : ℝ[X]}
    (hfg : StrictInterl f g)
    (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g)
    (hfdeg : f.natDegree ≤ (n + 1) / 2)
    (hgdeg : g.natDegree ≤ (n + 1) / 2) :
    StrictInterl (binaryRunTransform n f) (binaryRunTransform n g)

Interlacing across lengths

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)

Motzkin-ascent polynomials (A114580) 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))