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
- [BB09] 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} } - [MW26] 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} }