Touchard transform
The Touchard transform $t^n\mapsto\sum_kS(n,k)x^k$ sends every polynomial with roots in a set $J$ to a real-rooted polynomial exactly when $J\subseteq(-\infty,1/4]$. Brändén's ordered Bell transform does so exactly when $J\subseteq[L,U]$, with $L=-\frac{1+\sqrt2}2$ and $U=\frac{\sqrt2-1}2$. Neither transform preserves real-rootedness in general.
Results
The Touchard transform $\mathcal T$ is the linear map with $\mathcal T(t^n)=T_n(x)=\sum_kS(n,k)x^k$, where $S(n,k)$ are the Stirling numbers of the second kind; equivalently $\mathcal T(t^{\underline n})=x^n$, with $t^{\underline n}=t(t-1)\dotsm(t-n+1)$. It turns multiplication into the Poisson product: $$ \mathcal T(pq)=\mathcal T(p)\star\mathcal T(q),\qquad (F\star G)(x)=\sum_{k\ge0}\frac{x^k}{k!}F^{(k)}(x)G^{(k)}(x). $$ Brändén's ordered Bell transform $E$, with $E\binom tn=x^n$, turns multiplication into the diamond product $(F\diamond G)(x)=\sum_{k\ge0}\frac{[x(x+1)]^k}{(k!)^2}F^{(k)}(x)G^{(k)}(x)$. A polynomial is rooted in a set $S$ if it is nonzero, real-rooted and has all its roots in $S$; nonzero constants are rooted in every set.
Theorem (root domains). Let $J\subseteq\mathbb R$.
- $\mathcal T$ sends every polynomial rooted in $J$ to a real-rooted polynomial if and only if $J\subseteq(-\infty,1/4]$.
- $E$ sends every polynomial rooted in $J$ to a real-rooted polynomial if and only if $J\subseteq[L,U]$.
- For $c\in\mathbb R$, $\mathcal T$ maps the polynomials rooted in $(-\infty,c]$ to themselves if and only if $0\le c\le1/4$.
- For $A\le B$, $E$ maps the polynomials rooted in $[A,B]$ to themselves if and only if $L\le A\le-1$ and $0\le B\le U$.
Corollary (recurrences). If $P_0=1$ and $P_{n+1}=(x+a_{n+1})P_n+xP_n'$ with all $a_i\ge-1/4$, then every $P_n$ is rooted in $(-\infty,1/4]$. If $Q_0=1$ and $Q_{n+1}=(x+a_{n+1})Q_n+x(x+1)Q_n'$ with all $\frac{1-\sqrt2}2\le a_i\le\frac{1+\sqrt2}2$, then every $Q_n$ is rooted in $[L,U]$.
Theorem (Brenti–Royle–Wagner, Theorem 4.7). A polynomial is PF if it has nonnegative coefficients and is zero or has only real nonpositive roots. Let $m\ge0$ be an integer and let $f$ be monic with real coefficients. If every real zero $r$ satisfies $r\le m$ and every nonreal zero $s+it$ satisfies $4t^2\le1+4m-4s$, then $\mathcal T(t^{\underline m}f(t))$ is PF. All inequalities include equality.
For $m=2$, the disk $(s-1)^2+t^2\le1$ satisfies these bounds. Consequently $\mathcal T((t-1)^n+(-1)^n(t-1))$ is PF for $n\ge2$. For $n\ge3$ the source is the cycle chromatic polynomial, giving Proposition 4.10.
Theorem (grouped cubics). A monic cubic $x^3+\alpha x^2+\beta x+\gamma$ is PF if and only if $\alpha,\beta,\gamma\ge0$ and its discriminant is nonnegative. For real $a,b,w$, $$ \mathcal T\bigl((t+a)((t+b)^2+w)\bigr)=x^3+(3+a+2b)x^2+(1+a+2b+2ab+b^2+w)x+a(b^2+w), $$ and for $w\ge0$, $$ \mathcal T\bigl((t+b+\tfrac12)((t+b)^2+w)\bigr)\text{ is PF}\iff b\ge-\tfrac12\text{ and }w\le3b+\tfrac94 . $$
For instance $\mathcal T\bigl((t+\tfrac12)(t^2+\tfrac12)\bigr)$ is PF, while $\mathcal T(t^2+\tfrac12)$ is not real-rooted. We also have the inverse relation with the falling factorial transform, the rule $\mathcal T(t^{\underline m}p(t))=x^m\,\mathcal T(p(t+m))$, and closure of PF images under products.
Use
The Touchard polynomials themselves form a Sturm sequence. The ordered Bell transform has its own page, and fixed-factor Poisson multiplication is classified on the Poisson star product page.
Proof
Since $\mathcal T\bigl((t-r)(t-s)\bigr)=x^2+(1-r-s)x+rs$ and $E\bigl((t-r)(t-s)\bigr)=2x^2+(1-r-s)x+rs$, the image of $(t-r)^2$ is real-rooted exactly when $r\le1/4$, respectively $4r^2+4r\le1$; this gives necessity. For sufficiency, we pair the roots of the input so that each pair has an admissible image, and the product rule reduces the claim to Poisson multiplication by a PF polynomial or diamond multiplication by a polynomial rooted in $[-1,0]$, which preserve real-rootedness [Bra06, Theorems 3.11 and 3.13]. For the invariant sets, all summands of the product have the sign of the leading coefficient beyond $c$, respectively outside $[A,B]$.
For the parabolic criterion, factor $f$ into real linear and conjugate-pair quadratic factors and translate by $m$. Each factor has a PF Touchard image: the quadratic image has discriminant $1+4m-4s-4t^2\ge0$ and nonnegative coefficients. The product rule then applies. For cycles, remove $t(t-1)$ and use the disk containing the source roots.
References
- [Bra06, Theorems 3.11 and 3.13]
- F. Brenti, G. F. Royle and D. G. Wagner, Location of zeros of chromatic and related polynomials of graphs, Canad. J. Math. 46 (1994), 55–80, Theorem 4.7 and Proposition 4.10.
- Durán, Generalized Bell polynomials, arXiv:2409.11344, Problem 1 and Theorem 5, for the recurrences with negative parameters.
- [Bra06] 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} }