Rational substitutions

Substituting a rational function $A/B$ into a polynomial $p$ and clearing denominators gives a real-rooted polynomial exactly when $p$ is real-rooted and every fiber $A-rB$ over a root $r$ of $p$ is real-rooted. Two classical cases are the substitution $x/(1+x)^2$ of the gamma transform and the substitution $x+1/x$ for palindromic polynomials.

Results

For polynomials $A,B$ and $p=\sum_kp_kx^k$ of degree $d$ put $$ (A,B)\ast p=\sum_{k=0}^dp_k\,A^kB^{d-k}=B^d\,p(A/B). $$ For $N\ge d$ let $H_N[p]=B^{N-d}\,(A,B)\ast p$ be the version in ambient degree $N$. It is additive in $p$ for $\deg p\le N$, and $H_{M+N}[pq]=H_M[p]\,H_N[q]$ when $\deg p\le M$ and $\deg q\le N$.

Theorem (factorization). If $p$ splits over $\mathbb R$, then $(A,B)\ast p=\operatorname{lc}(p)\prod_r(A-rB)$ over the roots $r$ of $p$ with multiplicity.

Theorem (root descent). Let $p\ne0$ and $B\ne0$ be real polynomials, with $A$ and $B$ coprime and not proportional over $\mathbb C$. Then $$ (A,B)\ast p\text{ splits}\iff p\text{ splits and }A-rB\text{ splits for every root }r\text{ of }p. $$ If moreover $(A,B)\ast p$ splits with all roots in a set $I$, then every root $r$ of $p$ whose fiber $A-rB$ is nonconstant equals $A(x)/B(x)$ for some $x\in I$ with $B(x)\ne0$.

Corollary (quadratic substitution). Let $p\ne0$, $s\in\mathbb R$, $A=x$ and $B=(1+sx)^2$. The fiber $x-r(1+sx)^2$ has discriminant $1-4sr$, and $$ (A,B)\ast p\text{ splits}\iff p\text{ splits and }1-4sr\ge0\text{ for every root }r\text{ of }p . $$ For $s\ge0$, the substitution splits with only nonpositive roots if and only if $p$ splits with only nonpositive roots. For $s<0$, it splits with only nonpositive roots if and only if $p$ splits and all its roots lie in $[1/(4s),0]$. For $s=1$, $H_N[p]$ is the gamma transform $\Gamma_{2N}(p)$.

Corollary (Dickson substitution). Let $p\ne0$, $a\ne0$, $A=x^2+a$ and $B=x$. Then $(A,B)\ast p$ splits if and only if $p$ splits and $4a\le r^2$ for every root $r$ of $p$.

The derivatives of $H=H_N[p]$ are also expressed through those of $p$: with $W=A'B-AB'$, over any commutative ring, $$ B^2H'=N\,BB'\,H+W\,H_N[p'] , $$ and for every $r$ the product $B^{2r}H^{(r)}$ equals $\sum_{j\le r}c_{r,j}\,H_N[p^{(j)}]$ with polynomials $c_{r,j}$ defined by an explicit recursion in $A,B,N$ and $c_{r,r}=W^r$.

Proof

When $p$ splits, the factorization shows that $(A,B)\ast p$ splits exactly when every fiber does. If $p$ has a nonreal root $z$, then every root of $A-zB$ is a nonreal root of $(A,B)\ast p$, because $A$ and $B$ are coprime and $A/B$ is real at real points.

References

Definitions

  • The substitution B^deg(p) p(A/B), cleared of denominators

    RealRooted.rationalSubstitutionsource
    def rationalSubstitution {R : Type*} [CommSemiring R]
        (A B p : R[X]) : R[X] :=
      homogenizedSubstitution p.natDegree A B p
  • The same substitution in a fixed ambient degree N

    RealRooted.homogenizedSubstitutionsource
    def homogenizedSubstitution {R : Type*} [CommSemiring R]
        (N : ℕ) (A B p : R[X]) : R[X] :=
      MvPolynomial.aeval ![A, B] (p.homogenize N)
  • The pair (A, B) is not proportional over the complex numbers

    RealRooted.HasNonconstantRatiosource
    def HasNonconstantRatio (A B : ℝ[X]) : Prop :=
      ∀ z : ℂ,
        A.map Complex.ofRealHom - C z * B.map Complex.ofRealHom ≠ 0
  • The substitution x ↦ x / (1 + s x)²

    RealRooted.quadraticSubstitutionsource
    def quadraticSubstitution (s : ℝ) (p : ℝ[X]) : ℝ[X] :=
      rationalSubstitution X ((1 + C s * X) ^ 2) p
  • The substitution x ↦ (x² + a) / x

    RealRooted.dicksonSubstitutionsource
    def dicksonSubstitution (a : ℝ) (p : ℝ[X]) : ℝ[X] :=
      rationalSubstitution (X ^ 2 + C a) X p

Theorems

  • For a split p, the substitution is lc(p) times the product of A - r B over the roots rRealRooted original

    RealRooted.rationalSubstitution_eq_prod_of_splitssource
    theorem rationalSubstitution_eq_prod_of_splits {A B p : ℝ[X]}
        (hp : p.Splits) :
        rationalSubstitution A B p =
          C p.leadingCoeff * (p.roots.map fun r => A - C r * B).prod
  • The substitution splits exactly when p splits and every fiber A - r B splitsMain resultRealRooted original

    RealRooted.rationalSubstitution_splits_iffsource
    theorem rationalSubstitution_splits_iff {A B p : ℝ[X]}
        (hp : p ≠ 0) (hB : B ≠ 0) (hcop : IsCoprime A B)
        (hratio : HasNonconstantRatio A B) :
        (rationalSubstitution A B p).Splits ↔
          p.Splits ∧ ∀ r ∈ p.roots, (A - C r * B).Splits
  • Every root of p is a value A(x) / B(x) at a root x of the substitutionRealRooted original

    RealRooted.exists_mem_eq_eval_div_of_isRootsource
    theorem exists_mem_eq_eval_div_of_isRoot
        {A B p : ℝ[X]} {I : Set ℝ} {r : ℝ}
        (hp : p ≠ 0) (hB : B ≠ 0) (hcop : IsCoprime A B)
        (hratio : HasNonconstantRatio A B)
        (hH : (rationalSubstitution A B p).Splits)
        (hI : ∀ x ∈ (rationalSubstitution A B p).roots, x ∈ I)
        (hr : p.IsRoot r) (hfiber : (A - C r * B).natDegree ≠ 0) :
        ∃ x ∈ I, B.eval x ≠ 0 ∧ r = A.eval x / B.eval x
  • The quadratic substitution splits iff p splits and 1 - 4 s r ≥ 0 at every root rRealRooted original

    RealRooted.quadraticSubstitution_splits_iffsource
    theorem quadraticSubstitution_splits_iff {s : ℝ} {p : ℝ[X]} (hp : p ≠ 0) :
        (quadraticSubstitution s p).Splits ↔
          p.Splits ∧ ∀ r ∈ p.roots, 0 ≤ 1 - 4 * s * r
  • For s ≥ 0, nonpositive roots are preserved exactly for split p with nonpositive rootsRealRooted original

    RealRooted.quadraticSubstitution_splits_and_roots_nonpos_iff_of_nonnegsource
    theorem quadraticSubstitution_splits_and_roots_nonpos_iff_of_nonneg
        {s : ℝ} (hs : 0 ≤ s) {p : ℝ[X]} (hp : p ≠ 0) :
        ((quadraticSubstitution s p).Splits ∧
            ∀ x ∈ (quadraticSubstitution s p).roots, x ≤ 0) ↔
          (p.Splits ∧ ∀ r ∈ p.roots, r ≤ 0)
  • For s < 0, the exact condition is that the roots of p lie in [1/(4s), 0]RealRooted original

    RealRooted.quadraticSubstitution_splits_and_roots_nonpos_iff_of_negsource
    theorem quadraticSubstitution_splits_and_roots_nonpos_iff_of_neg
        {s : ℝ} (hs : s < 0) {p : ℝ[X]} (hp : p ≠ 0) :
        ((quadraticSubstitution s p).Splits ∧
            ∀ x ∈ (quadraticSubstitution s p).roots, x ≤ 0) ↔
          (p.Splits ∧ ∀ r ∈ p.roots, r ∈ Set.Icc (1 / (4 * s)) 0)
  • The Dickson substitution splits iff p splits and 4a ≤ r² at every root rRealRooted original

    RealRooted.dicksonSubstitution_splits_iffsource
    theorem dicksonSubstitution_splits_iff {a : ℝ} (ha : a ≠ 0)
        {p : ℝ[X]} (hp : p ≠ 0) :
        (dicksonSubstitution a p).Splits ↔
          p.Splits ∧ ∀ r ∈ p.roots, 4 * a ≤ r ^ 2
  • First-derivative transport through a homogeneous substitutionRealRooted original

    RealRooted.homogenizedSubstitution_firstDerivativesource
    theorem homogenizedSubstitution_firstDerivative {R : Type*} [CommRing R]
        {N : ℕ} {A B p : R[X]} (hdeg : p.natDegree ≤ N) :
        B ^ 2 * (homogenizedSubstitution N A B p).derivative =
          C (N : R) * B * B.derivative * homogenizedSubstitution N A B p +
            substitutionWronskian A B *
              homogenizedSubstitution N A B p.derivative
  • Iterated derivatives of the substitution in terms of derivatives of pRealRooted original

    RealRooted.homogenizedSubstitution_iterateDerivativesource
    theorem homogenizedSubstitution_iterateDerivative {R : Type*} [CommRing R]
        {N : ℕ} {A B p : R[X]} (hdeg : p.natDegree ≤ N) (r : ℕ) :
        B ^ (2 * r) * derivative^[r] (homogenizedSubstitution N A B p) =
          ∑ j ∈ Finset.range (r + 1),
            derivativeTransportCoeff N A B r j *
              homogenizedSubstitution N A B (derivative^[j] p)

Lean source RealRooted/Challenges/Preservers/RationalSubstitution.lean at revision d6670742. Formalized 2026-11-01.