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$.

  1. $\mathcal T$ sends every polynomial rooted in $J$ to a real-rooted polynomial if and only if $J\subseteq(-\infty,1/4]$.
  2. $E$ sends every polynomial rooted in $J$ to a real-rooted polynomial if and only if $J\subseteq[L,U]$.
  3. 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$.
  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

  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}
    }

Theorems

  • The Touchard transform of every polynomial rooted in J is real-rooted iff J ⊆ (−∞, 1/4]Main resultRealRooted original

    RealRooted.forall_splits_basisTransform_touchard_iffsource
    theorem forall_splits_basisTransform_touchard_iff (J : Set ℝ) :
        (∀ p : ℝ[X], IsRealRootedIn J p → (basisTransform touchard p).Splits) ↔ J ⊆ Iic (1 / 4)
  • The upper ray (−∞, c] is invariant under the Touchard transform iff 0 ≤ c ≤ 1/4RealRooted original

    RealRooted.forall_isRealRootedIn_Iic_basisTransform_touchard_iffsource
    theorem forall_isRealRootedIn_Iic_basisTransform_touchard_iff (c : ℝ) :
        (∀ p : ℝ[X], IsRealRootedIn (Iic c) p → IsRealRootedIn (Iic c) (basisTransform touchard p)) ↔
          0 ≤ c ∧ c ≤ 1 / 4
  • The E transform of every polynomial rooted in J is real-rooted iff J ⊆ [L, U]RealRooted original

    RealRooted.forall_splits_brandenE_iffsource
    theorem forall_splits_brandenE_iff (J : Set ℝ) :
        (∀ p : ℝ[X], IsRealRootedIn J p → (brandenE p).Splits) ↔
          J ⊆ Icc (-(1 + √2) / 2) ((√2 - 1) / 2)
  • The interval [A, B] is invariant under the E transform iff L ≤ A ≤ −1 and 0 ≤ B ≤ URealRooted original

    RealRooted.forall_isRealRootedIn_Icc_brandenE_iffsource
    theorem forall_isRealRootedIn_Icc_brandenE_iff {A B : ℝ} (hAB : A ≤ B) :
        (∀ p : ℝ[X], IsRealRootedIn (Icc A B) p → IsRealRootedIn (Icc A B) (brandenE p)) ↔
          -(1 + √2) / 2 ≤ A ∧ A ≤ -1 ∧ 0 ≤ B ∧ B ≤ (√2 - 1) / 2
  • Rows of the recurrence P_{n+1} = (x + a) P_n + x P_n′ with a ≥ −1/4 have roots ≤ 1/4RealRooted original

    RealRooted.isRealRootedIn_Iic_quarter_of_touchard_recurrencesource
    theorem isRealRootedIn_Iic_quarter_of_touchard_recurrence {a : ℕ → ℝ} (ha : ∀ n, -(1 / 4) ≤ a n)
        {P : ℕ → ℝ[X]} (h0 : P 0 = 1)
        (hP : ∀ n, P (n + 1) = (X + C (a (n + 1))) * P n + X * derivative (P n)) (n : ℕ) :
        IsRealRootedIn (Iic (1 / 4)) (P n)
  • Rows of the Euler type recurrence with (1 − √2)/2 ≤ a ≤ (1 + √2)/2 are rooted in [L, U]RealRooted original

    RealRooted.isRealRootedIn_Icc_of_brandenE_recurrencesource
    theorem isRealRootedIn_Icc_of_brandenE_recurrence {a : ℕ → ℝ}
        (ha : ∀ n, (1 - √2) / 2 ≤ a n ∧ a n ≤ (1 + √2) / 2) {P : ℕ → ℝ[X]} (h0 : P 0 = 1)
        (hP : ∀ n, P (n + 1) = (X + C (a (n + 1))) * P n + X * (X + 1) * derivative (P n)) (n : ℕ) :
        IsRealRootedIn (Icc (-(1 + √2) / 2) ((√2 - 1) / 2)) (P n)
  • The Touchard transform is inverse to the step-one falling factorial transformRealRooted original

    RealRooted.Poisson.fallingFactorialTransform_touchardsource
    theorem Poisson.fallingFactorialTransform_touchard (p : ℝ[X]) :
        Poisson.fallingFactorialTransform 1 (basisTransform touchard p) = p
  • The Touchard transform turns products into the parameter-one Poisson productRealRooted original

    RealRooted.basisTransform_touchard_mulsource
    theorem basisTransform_touchard_mul (p q : ℝ[X]) :
        basisTransform touchard (p * q) =
          Poisson.starC 1 (basisTransform touchard p) (basisTransform touchard q)
  • Products of polynomials with PF Touchard transforms again have PF Touchard transformsRealRooted original

    RealRooted.isPFPolynomial_basisTransform_touchard_prodsource
    theorem isPFPolynomial_basisTransform_touchard_prod
        {ι : Type*} (s : Finset ι) (f : ι → ℝ[X])
        (hf : ∀ i ∈ s, IsPFPolynomial (basisTransform touchard (f i))) :
        IsPFPolynomial (basisTransform touchard (∏ i ∈ s, f i))
  • A falling factorial prefix becomes X^m times a shift of the transformRealRooted original

    RealRooted.basisTransform_touchard_fallingFactorialPolynomial_mulsource
    theorem basisTransform_touchard_fallingFactorialPolynomial_mul
        (m : ℕ) (p : ℝ[X]) :
        basisTransform touchard (fallingFactorialPolynomial m * p) =
          X ^ m * basisTransform touchard (p.comp (X + C (m : ℝ)))
  • PF criterion for a falling factorial times a nonnegative multiple of a productRealRooted original

    RealRooted.isPFPolynomial_touchard_fallingFactorial_C_mul_prodsource
    theorem isPFPolynomial_touchard_fallingFactorial_C_mul_prod
        {ι : Type*} (m : ℕ) (s : Finset ι) (f : ι → ℝ[X]) {c : ℝ}
        (hc : 0 ≤ c)
        (hf : ∀ i ∈ s, IsPFPolynomial
          (basisTransform touchard ((f i).comp (X + C (m : ℝ))))) :
        IsPFPolynomial
          (basisTransform touchard
            (fallingFactorialPolynomial m * (C c * ∏ i ∈ s, f i)))
  • Brenti–Royle–Wagner: the closed parabolic root criterion gives a PF Stirling transformRealRooted original

    RealRooted.StirlingRootRegion.isPFPolynomial_fallingFactorial_mulsource
    theorem isPFPolynomial_fallingFactorial_mul (m : ℕ) {p : ℝ[X]} (hp : p.Monic)
        (hr : ∀ r : ℝ, p.IsRoot r → r ≤ (m : ℝ))
        (hz : ∀ z : ℂ, aeval z p = 0 → z.im ≠ 0 →
          4 * z.im ^ 2 ≤ 1 + 4 * (m : ℝ) - 4 * z.re) :
        IsPFPolynomial (basisTransform touchard (fallingFactorialPolynomial m * p))
  • Roots in the closed disk about one give a PF transform with a falling factorial prefixRealRooted original

    RealRooted.StirlingRootRegion.isPFPolynomial_fallingFactorial_two_mulsource
    theorem isPFPolynomial_fallingFactorial_two_mul {p : ℝ[X]} (hp : p.Monic)
        (hroot : ∀ z : ℂ, aeval z p = 0 → (z.re - 1) ^ 2 + z.im ^ 2 ≤ 1) :
        IsPFPolynomial (basisTransform touchard (fallingFactorialPolynomial 2 * p))
  • Brenti–Royle–Wagner: the Stirling transform of the cycle chromatic polynomial is PFRealRooted original

    RealRooted.StirlingRootRegion.isPFPolynomial_cyclesource
    theorem isPFPolynomial_cycle (n : ℕ) (hn : 2 ≤ n) :
        IsPFPolynomial (basisTransform touchard
          ((X - C 1) ^ n + C ((-1 : ℝ) ^ n) * (X - C 1)))
  • A monic cubic is PF exactly when its coefficients and discriminant are nonnegativeRealRooted original

    RealRooted.isPFPolynomial_monic_cubic_iffsource
    theorem isPFPolynomial_monic_cubic_iff (A B C₀ : ℝ) :
        IsPFPolynomial
            (X ^ 3 + C A * X ^ 2 + C B * X + C C₀) ↔
          0 ≤ A ∧ 0 ≤ B ∧ 0 ≤ C₀ ∧
            0 ≤ A ^ 2 * B ^ 2 - 4 * B ^ 3 - 4 * A ^ 3 * C₀ -
              27 * C₀ ^ 2 + 18 * A * B * C₀
  • Exact coefficient and discriminant criterion for the grouped cubic (X + a)((X + b)² + w)RealRooted original

    RealRooted.isPFPolynomial_touchard_linear_mul_quadratic_iffsource
    theorem isPFPolynomial_touchard_linear_mul_quadratic_iff
        (a b w : ℝ) :
        IsPFPolynomial
            (basisTransform touchard ((X + C a) * ((X + C b) ^ 2 + C w))) ↔
          let A
  • Sharp region b ≥ -1/2 and w ≤ 3b + 9/4 for the half-shifted grouped cubicRealRooted original

    RealRooted.isPFPolynomial_touchard_half_shifted_cubic_iffsource
    theorem isPFPolynomial_touchard_half_shifted_cubic_iff
        {b w : ℝ} (hw : 0 ≤ w) :
        IsPFPolynomial
            (basisTransform touchard
              ((X + C (b + 1 / 2)) * ((X + C b) ^ 2 + C w))) ↔
          -(1 / 2 : ℝ) ≤ b ∧ w ≤ 3 * b + 9 / 4
  • The Touchard transform of X² + 1/2 is not real-rootedRealRooted original

    RealRooted.not_splits_basisTransform_touchard_y_sq_add_halfsource
    theorem not_splits_basisTransform_touchard_y_sq_add_half :
        ¬(basisTransform touchard (X ^ 2 + C (1 / 2))).Splits
  • The diamond product of a [−1, 0]-rooted and a [A, B]-rooted polynomial is [A, B]-rootedRealRooted original

    RealRooted.betaProduct_one_isRealRootedIn_Iccsource
    theorem betaProduct_one_isRealRootedIn_Icc {A B : ℝ} (hA : A ≤ -1) (hB : 0 ≤ B) {G R : ℝ[X]}
        (hG : IsRealRootedIn (Icc (-1) 0) G) (hR : IsRealRootedIn (Icc A B) R) :
        IsRealRootedIn (Icc A B) (betaProduct 1 G R)
  • The Touchard transform of a polynomial rooted in (−∞, 1/4] is real-rootedRealRooted original

    RealRooted.IsRealRootedIn.basisTransform_touchardsource
    theorem IsRealRootedIn.basisTransform_touchard {p : ℝ[X]} (hp : IsRealRootedIn (Iic (1 / 4)) p) :
        IsRealRootedIn univ (basisTransform touchard p)
  • The Touchard transform preserves root location in (−∞, c] for 0 ≤ c ≤ 1/4RealRooted original

    RealRooted.IsRealRootedIn.basisTransform_touchard_Iicsource
    theorem IsRealRootedIn.basisTransform_touchard_Iic {c : ℝ} (hc0 : 0 ≤ c) (hc : c ≤ 1 / 4)
        {p : ℝ[X]} (hp : IsRealRootedIn (Iic c) p) :
        IsRealRootedIn (Iic c) (basisTransform touchard p)
  • Pairing of positive roots: all but at most one factor has a PF Touchard imageRealRooted original

    RealRooted.exists_eq_C_mul_mul_of_isRealRootedIn_Iic_quartersource
    theorem exists_eq_C_mul_mul_of_isRealRootedIn_Iic_quarter {p : ℝ[X]}
        (hp : IsRealRootedIn (Iic (1 / 4)) p) :
        ∃ (a : ℝ) (F R : ℝ[X]), a ≠ 0 ∧ p = C a * (F * R) ∧ F ≠ 0 ∧
          IsPFPolynomial (basisTransform touchard F) ∧
          (R = 1 ∨ ∃ r ∈ p.roots, 0 < r ∧ R = X - C r)
  • The Touchard transform of (X − r)² is not real-rooted for r > 1/4RealRooted original

    RealRooted.not_splits_basisTransform_touchard_X_sub_C_sqsource
    theorem not_splits_basisTransform_touchard_X_sub_C_sq {r : ℝ} (hr : 1 / 4 < r) :
        ¬ (basisTransform touchard ((X - C r) ^ 2)).Splits
  • The E transform preserves root location in [A, B] for L ≤ A ≤ −1 and 0 ≤ B ≤ URealRooted original

    RealRooted.IsRealRootedIn.brandenE_Iccsource
    theorem IsRealRootedIn.brandenE_Icc {A B : ℝ} (hL : -(1 + √2) / 2 ≤ A) (hA : A ≤ -1)
        (hB : 0 ≤ B) (hU : B ≤ (√2 - 1) / 2) {p : ℝ[X]} (hp : IsRealRootedIn (Icc A B) p) :
        IsRealRootedIn (Icc A B) (brandenE p)
  • Pairing of roots: all but at most one positive and one negative factor are admissibleRealRooted original

    RealRooted.exists_eq_C_mul_mul_of_isRealRootedIn_Iccsource
    theorem exists_eq_C_mul_mul_of_isRealRootedIn_Icc {p : ℝ[X]}
        (hp : IsRealRootedIn (Icc (-(1 + √2) / 2) ((√2 - 1) / 2)) p) :
        ∃ (a : ℝ) (F Rp Rn : ℝ[X]), a ≠ 0 ∧ p = C a * (F * (Rp * Rn)) ∧ F ≠ 0 ∧
          IsRealRootedIn (Icc (-1) 0) (brandenE F) ∧
          (Rp = 1 ∨ ∃ r ∈ p.roots, 0 < r ∧ Rp = X - C r) ∧
          (Rn = 1 ∨ ∃ r ∈ p.roots, r < -1 ∧ Rn = X - C r)
  • The E transform of (X − r)² is real-rooted iff r ∈ [L, U]RealRooted original

    RealRooted.splits_brandenE_X_sub_C_sq_iffsource
    theorem splits_brandenE_X_sub_C_sq_iff (r : ℝ) :
        (brandenE ((X - C r) ^ 2)).Splits ↔ r ∈ Icc (-(1 + √2) / 2) ((√2 - 1) / 2)
  • Pairing the linear factors of a root polynomial inside a multiplicative classRealRooted original

    RealRooted.exists_rootPolynomial_eq_mul_of_pairssource
    theorem exists_rootPolynomial_eq_mul_of_pairs {K : Set ℝ[X]} {S : Set ℝ}
        (h1 : (1 : ℝ[X]) ∈ K) (hmul : ∀ f ∈ K, ∀ g ∈ K, f * g ∈ K)
        (hpair : ∀ r ∈ S, ∀ s ∈ S, (X - C r) * (X - C s) ∈ K) (m : Multiset ℝ)
        (hm : ∀ r ∈ m, r ∈ S) :
        ∃ F R : ℝ[X], rootPolynomial m = F * R ∧ F ∈ K ∧ (R = 1 ∨ ∃ r ∈ m, R = X - C r)
  • Derivatives to the right of all roots have the sign of the leading coefficientRealRooted original

    RealRooted.IsRealRootedIn.leadingCoeff_mul_eval_iterate_derivative_nonnegsource
    theorem IsRealRootedIn.leadingCoeff_mul_eval_iterate_derivative_nonneg {q : ℝ[X]} {x : ℝ}
        (hq : IsRealRootedIn (Iic x) q) (k : ℕ) :
        0 ≤ q.leadingCoeff * ((derivative^[k]) q).eval x

Lean source RealRooted/Challenges/Preservers/TouchardTransform.lean at revision d6670742. Formalized 2026-11-09.