Liu's opposite-sign compatibility theorem
For real-rooted polynomials with opposite leading signs, compatibility is a root-count condition, with an extra branch for common roots.
Results
Two real polynomials $f$ and $g$ are compatible if every combination $\alpha f+\beta g$ with $\alpha,\beta\ge0$ is zero or real-rooted. For leading coefficients of the same sign, compatibility is governed by common interleavers (Chudnovsky–Seymour). Liu treats the case of opposite leading signs. Write $n_p(x)$ for the number of roots of $p$ in $[x,\infty)$, counted with multiplicity.
Theorem (Liu). [Liu12] Let $f$ and $g$ be nonconstant real-rooted polynomials with opposite leading signs. Then $f$ and $g$ are compatible if and only if one of the following holds.
- Delete the largest root from the polynomial with the larger largest root (from $f$ in case of a tie), and call the resulting pair $(p,q)$. Then $|n_p(x)-n_q(x)|\le1$ for every real $x$.
- $f$ and $g$ share a root $r$, and the cofactors $f/(x-r)$ and $g/(x-r)$ are compatible.
If $f$ and $g$ have no common root, they are compatible if and only if the first condition holds.
Corollary. Compatible real-rooted polynomials with opposite leading signs have degrees differing by at most two.
Liu's published statement has the first condition alone, and its forward direction fails: $x$ and $-x^2$ are compatible, but deleting the largest root $0$ from $x$ leaves a root-count gap of two at every $x\le0$. The common-root condition corrects this.
Proof
For pairs with simple roots, the root-count criterion is proved directly. The general case follows by small derivative shifts, which preserve compatibility and give simple roots, and a limit of root matchings.
References
[Liu12].
- [Liu12] Lily L. Liu. Polynomials with real zeros and compatible sequences. The Electronic Journal of Combinatorics, 19(3), P33, 2012.
BibTeX
@article{Liu2012CompatibleSequences,
author = {Liu, Lily L.},
title = {Polynomials with real zeros and compatible sequences},
year = {2012},
journal = {The Electronic Journal of Combinatorics},
volume = {19},
number = {3},
pages = {P33},
doi = {10.37236/2674}
}
≔ Definitions
Opposite leading signs
def OppositeLeadingSigns (p q : ℝ[X]) : Prop :=
p.leadingCoeff * q.leadingCoeff < 0
Number of roots in [x, ∞)
def rootCountAtOrAbove (p : ℝ[X]) (x : ℝ) : ℕ :=
(p.roots.filter (fun r => x ≤ r)).card
Root counts differing by at most one
def RootCountCompatible (p q : ℝ[X]) : Prop :=
∀ x : ℝ,
|((rootCountAtOrAbove p x : ℤ) - (rootCountAtOrAbove q x : ℤ))| ≤ 1
Root-count condition, deleting the largest root of f
structure LeftRootCountBranch (f g : ℝ[X]) (r s : ℝ) : Prop where
f_largest : IsLargestRoot f r
g_largest : IsLargestRoot g s
largest_ge : s ≤ r
count : RootCountCompatible (deleteRootFactor f r) g
Root-count condition, deleting the largest root of g
structure RightRootCountBranch (f g : ℝ[X]) (r s : ℝ) : Prop where
f_largest : IsLargestRoot f r
g_largest : IsLargestRoot g s
largest_lt : r < s
count : RootCountCompatible f (deleteRootFactor g s)
Common root with compatible cofactors
def CommonRootDeletionCompatibleBranch (f g : ℝ[X]) : Prop :=
∃ r : ℝ, f.IsRoot r ∧ g.IsRoot r ∧
Compatible (deleteRootFactor f r) (deleteRootFactor g r)
⊢ Theorems
Compatibility with opposite leading signs (corrected)Main result
theorem compatible_iff_rootCountBranchesWithCommon
{f g : ℝ[X]} (hf : f.Splits) (hg : g.Splits)
(hsgn : OppositeLeadingSigns f g)
(hf_deg : f.natDegree ≠ 0) (hg_deg : g.natDegree ≠ 0) :
Compatible f g ↔ RootCountBranchesWithCommon f g
Compatibility for pairs without common roots
theorem compatible_iff_rootCountBranches_of_noCommonRoots
{f g : ℝ[X]} (hf : f.Splits) (hg : g.Splits)
(hsgn : OppositeLeadingSigns f g) (hno : NoCommonRoots f g)
(hf_deg : f.natDegree ≠ 0) (hg_deg : g.natDegree ≠ 0) :
Compatible f g ↔ RootCountBranches f g
Without the common-root branch the statement fails
theorem not_forall_rootCountBranches_of_compatible :
¬ ∀ {f g : ℝ[X]},
f.Splits → g.Splits → OppositeLeadingSigns f g →
f.natDegree ≠ 0 → g.natDegree ≠ 0 →
Compatible f g → RootCountBranches f g
Degrees of compatible pairs differ by at most two
theorem natDegree_abs_sub_le_two_of_compatible {f g : ℝ[X]}
(hf : f.Splits) (hg : g.Splits)
(hsgn : OppositeLeadingSigns f g) (hcompat : Compatible f g) :
|((f.natDegree : ℤ) - (g.natDegree : ℤ))| ≤ 2
Lean source RealRooted/Challenges/Interlacing/LiuOppositeSigns.lean at revision d6670742. Formalized 2026-10-02.