The f-polynomial transform

The f-polynomial transform converts derivative recurrences into derivative recurrences, preserves and reflects real-rootedness, and transfers interlacing of rows with half-growth degrees.

Results

For $d\ge0$ and a polynomial $h$ of degree at most $d$ with coefficients $h_k$, the f-polynomial transform is $$ f_d(h)=\sum_{k=0}^{d}h_k\,x^k(x+1)^{d-k}. $$ It is the substitution $x\mapsto x/(x+1)$ homogenized to degree $d$.

Theorem (derivative rule). If $\deg p\le d$, then $$ (x+1)^2\,f_d(p)'=d\,(x+1)\,f_d(p)+f_d(p'). $$

Theorem (recurrences). Let $a,b,q$ be polynomials with $\deg a\le2$, $\deg b\le1$, $\deg q\le d$ and $\deg(aq'+bq)\le d+1$. Then $$ f_{d+1}(aq'+bq)=(x+1)\,f_2(a)\,f_d(q)'+\bigl(f_1(b)-d\,f_2(a)\bigr)f_d(q). $$ Consequently, let $Q_{n+1}=a_nQ_n'+b_nQ_n$ with $\deg a_n\le2$, $\deg b_n\le1$ and $\deg Q_n\le n$, and let $P_0=f_0(Q_0)$ and $$ P_{n+1}=(x+1)\,f_2(a_n)\,P_n'+\bigl(f_1(b_n)-n\,f_2(a_n)\bigr)P_n. $$ Then $P_n=f_n(Q_n)$ for all $n$. The degree bound $\deg Q_n\le n$ holds if $Q_0$ is constant.

Theorem (real roots). Let $\deg p\le d$. Then $f_d(p)$ is real-rooted if and only if $p$ is real-rooted. In particular, if $P_n=f_n(Q_n)$ with $\deg Q_n\le n$ and every $Q_n$ real-rooted, then every $P_n$ is real-rooted.

Theorem (roots and interlacing). Let $p\ne0$ be real-rooted with $p(1)\ne0$. Then the roots of $f_{\deg p}(p)$ are the numbers $r/(1-r)$ for the roots $r$ of $p$. If $f\ll g$ and all roots of $f$ and $g$ are below $1$, or all are above $1$, then $f_{\deg f}(f)\ll f_{\deg g}(g)$.

Theorem (half-growth sequences). Let $Q_j$ be nonzero real-rooted polynomials with nonnegative coefficients, $\deg Q_j=\lfloor (j+1)/2\rfloor$ and $Q_j\ll Q_{j+1}$ for all $j$. Then $f_n(Q_n)\ll f_{n+1}(Q_{n+1})$ for all $n\ge1$.

Theorem (Euler shifts). Let $\theta=x\,d/dx$. If $\deg p\le n$ and $a\in\mathbb R$, then $$ f_n\bigl(\theta p+ap\bigr)=(a-nx)\,f_n(p)+x(1+x)\,f_n(p)'. $$ Let $F$ be real-rooted of degree $n$ with positive leading coefficient and all roots in $[-1,0]$, and let $a\in\mathbb R$. Then $(a-nx)F+x(1+x)F'$ is real-rooted. If $a>0$, it has degree $n$ and positive leading coefficient, and $F\ll(a-nx)F+x(1+x)F'$. For $n\ge1$, all real-rooted $F$ of degree $n$ with positive leading coefficient and roots in $[-1,0]$ are mapped to polynomials with roots in $[-1,0]$ if and only if $a\ge0$ or $a\le-n$.

Use

The alternating-runs polynomials are f-transforms of peak polynomials, and the peak polynomials have the half-growth degree pattern. Real-rootedness and interlacing of the peak polynomials therefore pass to the alternating-runs polynomials, for example the rows of OEIS A008970, A059427 and A186370.

Proof

The derivative rule is a direct computation. For the Euler shifts, every real-rooted $F$ of degree $n$ with positive leading coefficient and roots in $[-1,0]$ is $f_n(q)$ for a Pólya frequency polynomial $q$ of degree at most $n$, and $q\mapsto\theta q+aq$ preserves real-rootedness of such polynomials.

References

See [BS19] and the symmetric-decomposition overview on symmetricfunctions.com.

  1. [BS19] Petter Brändén & Liam Solus. Symmetric Decompositions and Real-Rootedness. International Mathematics Research Notices, 2021(10), 7764-7798, 2019.
    BibTeX
    @article{BrandenSolus2019,
      title = {Symmetric Decompositions and Real-Rootedness},
      volume = {2021},
      ISSN = {1687-0247},
      url = {http://dx.doi.org/10.1093/imrn/rnz059},
      DOI = {10.1093/imrn/rnz059},
      number = {10},
      journal = {International Mathematics Research Notices},
      publisher = {Oxford University Press (OUP)},
      author = {Br\"{a}ndén, Petter and Solus, Liam},
      year = {2019},
      month = apr,
      pages = {7764--7798}
    }

Theorems

  • The derivative rule for the f-polynomial transform

    RealRooted.fPolynomial_derivativesource
    theorem fPolynomial_derivative {d : ℕ} {p : ℝ[X]} (hp : p.natDegree ≤ d) :
        (X + 1) ^ 2 * (fPolynomial d p).derivative =
          C (d : ℝ) * (X + 1) * fPolynomial d p + fPolynomial d p.derivative
  • One transformed derivative-recurrence step

    RealRooted.fPolynomial_derivativeRecurrence_stepsource
    theorem fPolynomial_derivativeRecurrence_step {d : ℕ} {a b q : ℝ[X]} (ha : a.natDegree ≤ 2)
        (hb : b.natDegree ≤ 1) (hq : q.natDegree ≤ d)
        (hstep : (a * q.derivative + b * q).natDegree ≤ d + 1) :
        fPolynomial (d + 1) (a * q.derivative + b * q) =
          (X + 1) * fPolynomial 2 a * (fPolynomial d q).derivative +
            (fPolynomial 1 b - C (d : ℝ) * fPolynomial 2 a) * fPolynomial d q
  • A transformed recurrence identifies every row

    RealRooted.eq_fPolynomial_of_derivRecsource
    theorem eq_fPolynomial_of_derivRec {P Q a b : ℕ → ℝ[X]}
        (ha : ∀ n, (a n).natDegree ≤ 2) (hb : ∀ n, (b n).natDegree ≤ 1)
        (hQ : ∀ n, Q (n + 1) = a n * (Q n).derivative + b n * Q n)
        (hQdeg : ∀ n, (Q n).natDegree ≤ n)
        (hP : ∀ n, P (n + 1) = (X + 1) * fPolynomial 2 (a n) * (P n).derivative +
          (fPolynomial 1 (b n) - C (n : ℝ) * fPolynomial 2 (a n)) * P n)
        (h0 : P 0 = fPolynomial 0 (Q 0)) (n : ℕ) :
        P n = fPolynomial n (Q n)
  • Quadratic-linear derivative recurrences have at most linear degree growth

    RealRooted.natDegree_le_of_derivRecsource
    theorem natDegree_le_of_derivRec {Q a b : ℕ → ℝ[X]} (ha : ∀ n, (a n).natDegree ≤ 2)
        (hb : ∀ n, (b n).natDegree ≤ 1)
        (hQ : ∀ n, Q (n + 1) = a n * (Q n).derivative + b n * Q n)
        (h0 : (Q 0).natDegree = 0) (n : ℕ) : (Q n).natDegree ≤ n
  • A constant initial row gives the transformed recurrence identity

    RealRooted.eq_fPolynomial_of_derivativeRecurrence_of_natDegree_zerosource
    theorem eq_fPolynomial_of_derivativeRecurrence_of_natDegree_zero {P Q a b : ℕ → ℝ[X]}
        (ha : ∀ n, (a n).natDegree ≤ 2) (hb : ∀ n, (b n).natDegree ≤ 1)
        (hQ : ∀ n, Q (n + 1) = a n * (Q n).derivative + b n * Q n)
        (h0deg : (Q 0).natDegree = 0)
        (hP : ∀ n, P (n + 1) = (X + 1) * fPolynomial 2 (a n) * (P n).derivative +
          (fPolynomial 1 (b n) - C (n : ℝ) * fPolynomial 2 (a n)) * P n)
        (h0 : P 0 = fPolynomial 0 (Q 0)) (n : ℕ) :
        P n = fPolynomial n (Q n)
  • The f-polynomial transform preserves splitting

    RealRooted.splits_fPolynomialsource
    theorem splits_fPolynomial {d : ℕ} {p : ℝ[X]} (hpdeg : p.natDegree ≤ d) (hp : p.Splits) :
        (fPolynomial d p).Splits
  • The f-transform maps the roots r to r / (1 - r)

    RealRooted.roots_fPolynomial_natDegree_eq_mapsource
    theorem roots_fPolynomial_natDegree_eq_map {p : ℝ[X]} (hp : p ≠ 0) (hs : p.Splits)
        (h1 : ¬ p.IsRoot 1) :
        (fPolynomial p.natDegree p).roots = p.roots.map (fun r => r / (1 - r))
  • The f-transform preserves interlacing of polynomials with roots below one

    RealRooted.StrictInterl.fPolynomial_natDegree_of_roots_lt_onesource
    theorem StrictInterl.fPolynomial_natDegree_of_roots_lt_one {f g : ℝ[X]}
        (h : StrictInterl f g) (hf : ∀ r ∈ f.roots, r < 1) (hg : ∀ r ∈ g.roots, r < 1) :
        StrictInterl (fPolynomial f.natDegree f) (fPolynomial g.natDegree g)
  • The f-transform preserves interlacing of polynomials with roots above one

    RealRooted.StrictInterl.fPolynomial_natDegree_of_one_lt_rootssource
    theorem StrictInterl.fPolynomial_natDegree_of_one_lt_roots {f g : ℝ[X]}
        (h : StrictInterl f g) (hf : ∀ r ∈ f.roots, 1 < r) (hg : ∀ r ∈ g.roots, 1 < r) :
        StrictInterl (fPolynomial f.natDegree f) (fPolynomial g.natDegree g)
  • Rows that are f-transforms of real-rooted rows are real-rooted

    RealRooted.splits_of_eq_fPolynomialsource
    theorem splits_of_eq_fPolynomial {P Q : ℕ → ℝ[X]}
        (hPQ : ∀ n, P n = fPolynomial n (Q n))
        (hdeg : ∀ n, (Q n).natDegree ≤ n) (hs : ∀ n, (Q n).Splits) (n : ℕ) :
        (P n).Splits
  • (x - r)f ≪ g gives f ≪ g if the roots of f exceed r and deg g = deg f + 1

    RealRooted.StrictInterl.of_mul_X_sub_C_left_of_roots_gtsource
    lemma StrictInterl.of_mul_X_sub_C_left_of_roots_gt
        {f g : ℝ[X]} {r : ℝ}
        (hf : f ≠ 0 ∧ f.Splits) (hg : g ≠ 0 ∧ g.Splits)
        (hdegf : 0 < f.natDegree)
        (hroot : ∀ s ∈ f.roots, r < s)
        (hdeg : f.natDegree + 1 = g.natDegree)
        (h : StrictInterl ((X - C r) * f) g) : StrictInterl f g
  • f ≪ g gives f ≪ (x - r)g for equal degrees and all roots at least r

    RealRooted.StrictInterl.of_mul_X_sub_C_right_of_roots_gesource
    lemma StrictInterl.of_mul_X_sub_C_right_of_roots_ge
        {f g : ℝ[X]} {r : ℝ}
        (hf : f ≠ 0 ∧ f.Splits) (hg : g ≠ 0 ∧ g.Splits)
        (hdeg : f.natDegree = g.natDegree)
        (hrootf : ∀ s ∈ f.roots, r ≤ s)
        (hrootg : ∀ s ∈ g.roots, r ≤ s)
        (h : StrictInterl f g) : StrictInterl f ((X - C r) * g)
  • f_m(u) ≪ (x + 1) f_m(v) gives f_k(u) ≪ f_{k+1}(v) for k ≥ m

    RealRooted.StrictInterl.fPolynomial_pad_of_mul_X_add_onesource
    lemma StrictInterl.fPolynomial_pad_of_mul_X_add_one
        {u v : ℝ[X]} {m k : ℕ}
        (hu_deg : u.natDegree ≤ m) (hv_deg : v.natDegree ≤ m)
        (hmk : m ≤ k)
        (huv : StrictInterl (fPolynomial m u) ((X + 1) * fPolynomial m v)) :
        StrictInterl (fPolynomial k u) (fPolynomial (k + 1) v)
  • Half-growth sequences transfer consecutive interlacing

    RealRooted.StrictInterl.fPolynomial_sequencesource
    theorem StrictInterl.fPolynomial_sequence
        (q : ℕ → ℝ[X])
        (hq_nonneg : ∀ j, HasNonnegCoeffs (q j))
        (hq_ne : ∀ j, q j ≠ 0)
        (hq_splits : ∀ j, (q j).Splits)
        (hq_deg : ∀ j, (q j).natDegree = (j + 1) / 2)
        (hq_interl : ∀ j, StrictInterl (q j) (q (j + 1)))
        {n : ℕ} (hn : 1 ≤ n) :
        StrictInterl (fPolynomial n (q n)) (fPolynomial (n + 1) (q (n + 1)))
  • For deg p ≤ d the f-transform splits exactly when p splitsMain result

    RealRooted.splits_fPolynomial_iffsource
    theorem splits_fPolynomial_iff {d : ℕ} {p : ℝ[X]} (hdeg : p.natDegree ≤ d) :
        (fPolynomial d p).Splits ↔ p.Splits
  • The Euler shift θ + a becomes (a - nX) F + X (1 + X) F' under the f-transform

    RealRooted.fPolynomial_theta_add_C_mulsource
    theorem fPolynomial_theta_add_C_mul {p : ℝ[X]} {n : ℕ}
        (hdeg : p.natDegree ≤ n) (a : ℝ) :
        fPolynomial n (theta p + C a * p) =
          (C a - C (n : ℝ) * X) * fPolynomial n p +
            X * (1 + X) * (fPolynomial n p).derivative
  • The interval Euler operator preserves splitting for roots in [-1, 0]

    RealRooted.intervalEulerOperator_splitssource
    theorem intervalEulerOperator_splits {p : ℝ[X]} {n : ℕ}
        (hp : p.Splits) (hdeg : p.natDegree = n)
        (hpos : HasPosLeadingCoeff p)
        (hroots : ∀ r ∈ p.roots, r ∈ Icc (-1 : ℝ) 0) (a : ℝ) :
        ((C a - C (n : ℝ) * X) * p + X * (1 + X) * p.derivative).Splits
  • For a > 0 the image keeps the degree n and the input interlaces it

    RealRooted.intervalEulerOperator_degree_pos_strictInterlsource
    theorem intervalEulerOperator_degree_pos_strictInterl
        {p : ℝ[X]} {n : ℕ}
        (hp : p.Splits) (hdeg : p.natDegree = n)
        (hpos : HasPosLeadingCoeff p)
        (hroots : ∀ r ∈ p.roots, r ∈ Icc (-1 : ℝ) 0)
        {a : ℝ} (ha : 0 < a) :
        let F
  • The window [-1, 0] is preserved exactly when a ≥ 0 or a ≤ -n

    RealRooted.forall_intervalEulerOperator_roots_mem_Icc_iffsource
    theorem forall_intervalEulerOperator_roots_mem_Icc_iff
        {n : ℕ} (hn : 1 ≤ n) (a : ℝ) :
        (∀ p : ℝ[X], p.Splits → p.natDegree = n →
          HasPosLeadingCoeff p →
          (∀ r ∈ p.roots, r ∈ Icc (-1 : ℝ) 0) →
          ∀ r ∈ ((C a - C (n : ℝ) * X) * p +
            X * (1 + X) * p.derivative).roots, r ∈ Icc (-1 : ℝ) 0) ↔
          0 ≤ a ∨ a ≤ -(n : ℝ)

Lean source RealRooted/Challenges/Interlacing/FPolynomialRecurrences.lean at revision d6670742. Formalized 2026-10-11.