Reciprocal shifts and interlacing

The reciprocal shift $x^Dp(1/x)$ inverts the nonzero roots of $p$, and it reverses interlacing of Pólya frequency polynomials.

Results

A real polynomial $p$ is PF if it has nonnegative coefficients and is either zero or splits over $\mathbb R$ with all roots at most $0$. For $D\ge\deg p$ the reciprocal shift is $p_D(x)=x^Dp(1/x)$, the polynomial with coefficients reversed within degree $D$.

Theorem (reversal). Let $p,q$ be PF polynomials of degree at most $D$ with $p\ll q$. Then $q_D\ll p_D$.

Proposition (factorization and roots). For $\deg p\le D$, $$ p_D=x^{D-\deg p}\,p^{\mathrm{rev}}, $$ where $p^{\mathrm{rev}}$ is the reversed polynomial. If $p\ne0$ splits, then the roots of $p_D$, with multiplicity, are $D-\deg p$ zeros together with the inverses of the nonzero roots of $p$. If $p$ is PF, so is $p_D$.

Proof

Let $p\ne0$ split with all roots at most $0$, listed in increasing order. Removing the zeros, reversing the list, inverting each entry and appending $D-\deg p$ zeros gives the roots of $p_D$ in increasing order. Since $t\mapsto1/t$ is order-reversing on the negative reals, inverting and reversing two interleaving lists of negative reals swaps them when they have equal length and keeps their order when the second is one longer, which gives the reversal theorem.

References

[Fis06]

  1. [Fis06] Steve Fisk. Polynomials, roots, and interlacing. arXiv e-prints, 2006.
    BibTeX
    @article{Fisk2006x,
      Author = {Steve Fisk},
      Title = {Polynomials, roots, and interlacing},
      Year = {2006},
      Eprint = {arXiv:math/0612833},
      journal = {arXiv e-prints}
    }

Theorems

  • Reciprocal shifts reverse interlacingMain result

    RealRooted.reciprocalShift_reverses_strictInterlsource
    theorem reciprocalShift_reverses_strictInterl
        {D : ℕ} {p q : ℝ[X]} (hp : IsPFPolynomial p) (hq : IsPFPolynomial q)
        (hpd : p.natDegree ≤ D) (hqd : q.natDegree ≤ D) (hpq : StrictInterl p q) :
        StrictInterl (reciprocalShift D q) (reciprocalShift D p)
  • Roots of a reciprocal shift

    RealRooted.roots_reciprocalShift_eqsource
    theorem roots_reciprocalShift_eq
        {D : ℕ} {p : ℝ[X]} (hp_ne : p ≠ 0) (hp_splits : p.Splits)
        (hdegree : p.natDegree ≤ D) :
        (reciprocalShift D p).roots =
          Multiset.replicate (D - p.natDegree) 0
            + (p.roots.filter fun r ↦ r ≠ 0).map (·⁻¹)
  • PF preservation under reciprocal shifts

    RealRooted.IsPFPolynomial.reciprocalShiftsource
    theorem IsPFPolynomial.reciprocalShift {D : ℕ} {p : ℝ[X]}
        (hp : IsPFPolynomial p) (hdeg : p.natDegree ≤ D) :
        IsPFPolynomial (reciprocalShift D p)
  • Factorization of a reciprocal shift

    RealRooted.reciprocalShift_eq_X_pow_mul_reversesource
    theorem reciprocalShift_eq_X_pow_mul_reverse {D : ℕ} {p : ℝ[X]}
        (hdeg : p.natDegree ≤ D) :
        reciprocalShift D p = X ^ (D - p.natDegree) * p.reverse
  • Inversion of equal-length interleavings

    RealRooted.interleaves_reverse_map_one_div_of_length_eqsource
    theorem interleaves_reverse_map_one_div_of_length_eq
        (A B : List ℝ) (hAneg : ∀ x ∈ A, x < 0) (hBneg : ∀ x ∈ B, x < 0)
        (hlen : A.length = B.length) (h : List.Interleaves (· ≤ ·) A B) :
        List.Interleaves (· ≤ ·) (B.reverse.map (fun x ↦ 1 / x))
          (A.reverse.map (fun x ↦ 1 / x))
  • Inversion of length-shifted interleavings

    RealRooted.interleaves_reverse_map_one_div_of_length_add_one_eqsource
    theorem interleaves_reverse_map_one_div_of_length_add_one_eq
        (A B : List ℝ) (hAneg : ∀ x ∈ A, x < 0) (hBneg : ∀ x ∈ B, x < 0)
        (hlen : A.length + 1 = B.length) (h : List.Interleaves (· ≤ ·) A B) :
        List.Interleaves (· ≤ ·) (A.reverse.map (fun x ↦ 1 / x))
          (B.reverse.map (fun x ↦ 1 / x))
  • List model for reciprocal-shift roots

    RealRooted.reciprocalShift_model_rootssource
    theorem reciprocalShift_model_roots
        {D : ℕ} {p : ℝ[X]} (hp_ne : p ≠ 0) (hp_splits : p.Splits)
        (hdegree : p.natDegree ≤ D) (l : List ℝ) (hl : (l : Multiset ℝ) = p.roots) :
        (((l.filter fun r ↦ decide (r ≠ 0)).reverse.map (fun r ↦ 1 / r)
          ++ List.replicate (D - p.natDegree) 0 : List ℝ) : Multiset ℝ) =
            (reciprocalShift D p).roots
  • Sorted reciprocal-shift root model

    RealRooted.reciprocalShift_model_sortedsource
    theorem reciprocalShift_model_sorted (l : List ℝ) (k : ℕ)
        (hsorted : l.Pairwise (· ≤ ·)) (hnonpos : ∀ x ∈ l, x ≤ 0) :
        ((l.filter fun r ↦ decide (r ≠ 0)).reverse.map (fun r ↦ 1 / r)
          ++ List.replicate k 0).Pairwise (· ≤ ·)
  • Antitonicity of inversion on negative numbers

    RealRooted.one_div_antitone_of_nonpossource
    theorem one_div_antitone_of_nonpos {a b : ℝ}
        (hb : b < 0) (hab : a ≤ b) :
        1 / b ≤ 1 / a

Lean source RealRooted/Challenges/Interlacing/ReciprocalShift.lean at revision d6670742. Formalized 2026-09-26.