Falling-factorial truncations

A real polynomial is real-rooted exactly when all its falling-factorial truncations are. Each truncation applies a finite multiplier sequence, and together the truncations detect real-rootedness.

Results

For a real polynomial $f(t)=\sum_j c_jt^j$ and $p\in\mathbb N$ let $$ T_p f(t)=\sum_j p^{\underline j}\,c_jt^j, \qquad p^{\underline j}=p(p-1)\dotsm(p-j+1), $$ so that the terms with $j>p$ vanish. Here a polynomial is real-rooted if it is zero or splits over $\mathbb R$.

Theorem. A real polynomial $f$ is real-rooted if and only if $T_pf$ is real-rooted for every $p\ge0$.

The forward direction is due to Pólya and Schur [SP14, §2, p. 97], since $T_pf=\sum_j\binom pj\,j!\,c_jt^j$.

Corollary (big-block rows). Define the two-weight Bell rows by $$ F_0=1,\qquad F_{n+1}=\sum_{r=1}^{n+1}\binom n{r-1}(\alpha_r+t\beta_r)F_{n+1-r}, $$ and let $\mathcal B_m$ be the row with $\alpha_r=[r=1]$ and $\beta_r=2/((r+1)(r+2))$, so that $$ \mathcal B_1=1+t/3,\quad \mathcal B_2=1+5t/6+t^2/9,\quad \mathcal B_3=1+8t/5+t^2/2+t^3/27. $$ Then $\mathcal B_m$ is real-rooted if and only if $R_{m,p}=T_p\mathcal B_m$ is real-rooted for every $p\ge0$.

Up to the factor $2^pp!\,m!/(m+2p)!$, $R_{m,p}$ is the generating polynomial of partitions of an $(m+2p)$-element set with exactly $p$ nonsingleton blocks, with $t$ marking the blocks of size at least three. Whether every $\mathcal B_m$ is real-rooted is open.

Proof

For the forward direction, $T_pf$ is Schur's composition of $f$ with $(1+t)^p$, which is real-rooted by Schur's theorem. Conversely, $T_pf(t/p)$ converges coefficientwise to $f(t)$ as $p\to\infty$ with bounded degree, and real-rootedness passes to the limit.

References

  1. [SP14] J Schur & G Polya. Über zwei Arten von Faktorenfolgen in der Theorie der algebraischen Gleichungen. J. Reine Angew. Math., 1914.
    BibTeX
    @article{SchurPolya1914,
      title={{\"U}ber zwei {A}rten von {F}aktorenfolgen in der {T}heorie der algebraischen {G}leichungen},
      author={Schur, J and Polya, G},
      year={1914},
      journal={J. Reine Angew. Math.},
      publisher={Walter de Gruyter, Berlin/New York Berlin, New York}
    }

Definitions

  • Multiply coefficient j by the falling factorial (p)_j

    RealRooted.fallingSchursource
    def fallingSchur (n : ℕ) (p : ℝ[X]) : ℝ[X] :=
      factorialHadamardProduct p ((X + 1 : ℝ[X]) ^ n)
  • The distinguished-block recurrence with two block weights

    RealRooted.weightedBellsource
    def weightedBell (α β : ℕ → ℝ) : ℕ → ℝ[X]
      | 0 => 1
      | n + 1 => ∑ a ∈ Finset.range (n + 1),
          C (n.choose a : ℝ) * (C (α (a + 1)) + C (β (a + 1)) * X) *
            weightedBell α β (n - a)
  • The big-block row

    RealRooted.bigBlockScalarsource
    def bigBlockScalar (m : ℕ) : ℝ[X] :=
      weightedBell (fun r => if r = 1 then 1 else 0)
        (fun r => 2 / (((r : ℝ) + 1) * ((r : ℝ) + 2))) m
  • The truncated big-block row R(m,p)

    RealRooted.normalizedBigBlocksource
    def normalizedBigBlock (m p : ℕ) : ℝ[X] := fallingSchur p (bigBlockScalar m)

Theorems

  • Falling-factorial truncation preserves real-rootedness

    RealRooted.splits_fallingSchursource
    theorem splits_fallingSchur {f : ℝ[X]} (hf : f.Splits) (p : ℕ) :
        (fallingSchur p f).Splits
  • All falling-factorial truncations are real-rooted exactly when the polynomial isMain result

    RealRooted.forall_splits_fallingSchur_iffsource
    theorem forall_splits_fallingSchur_iff (f : ℝ[X]) :
        (∀ p : ℕ, (fallingSchur p f).Splits) ↔ f.Splits
  • The big-block row is real-rooted exactly when all its truncations are

    RealRooted.forall_splits_normalizedBigBlock_iffsource
    theorem forall_splits_normalizedBigBlock_iff (m : ℕ) :
        (∀ p : ℕ, (normalizedBigBlock m p).Splits) ↔ (bigBlockScalar m).Splits

Lean source RealRooted/Challenges/Preservers/FallingFactorial.lean at revision d6670742. Formalized 2026-11-13.