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.

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].

  1. [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

    RealRooted.LiuOppositeSigns.OppositeLeadingSignssource
    def OppositeLeadingSigns (p q : ℝ[X]) : Prop :=
      p.leadingCoeff * q.leadingCoeff < 0
  • Number of roots in [x, ∞)

    RealRooted.LiuOppositeSigns.rootCountAtOrAbovesource
    def rootCountAtOrAbove (p : ℝ[X]) (x : ℝ) : ℕ :=
      (p.roots.filter (fun r => x ≤ r)).card
  • Root counts differing by at most one

    RealRooted.LiuOppositeSigns.RootCountCompatiblesource
    def RootCountCompatible (p q : ℝ[X]) : Prop :=
      ∀ x : ℝ,
        |((rootCountAtOrAbove p x : ℤ) - (rootCountAtOrAbove q x : ℤ))| ≤ 1
  • Root-count condition, deleting the largest root of f

    RealRooted.LiuOppositeSigns.LeftRootCountBranchsource
    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

    RealRooted.LiuOppositeSigns.RightRootCountBranchsource
    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

    RealRooted.LiuOppositeSigns.CommonRootDeletionCompatibleBranchsource
    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

    RealRooted.LiuOppositeSigns.compatible_iff_rootCountBranchesWithCommonsource
    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

    RealRooted.LiuOppositeSigns.compatible_iff_rootCountBranches_of_noCommonRootssource
    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

    RealRooted.LiuOppositeSigns.not_forall_rootCountBranches_of_compatiblesource
    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

    RealRooted.LiuOppositeSigns.natDegree_abs_sub_le_two_of_compatiblesource
    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.