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]
- [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
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
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
theorem IsPFPolynomial.reciprocalShift {D : ℕ} {p : ℝ[X]}
(hp : IsPFPolynomial p) (hdeg : p.natDegree ≤ D) :
IsPFPolynomial (reciprocalShift D p)
Factorization of a reciprocal shift
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
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
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
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
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
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.