Binomial perturbations and Hurwitz stability

Perturbations of $(1+z)^n$ whose lower coefficients are small in a weighted $\ell^2$ sense have no zero in the open right half-plane. Through the odd and even parts, this gives an explicit family of real-rooted perturbations of the even binomial section with one common interlacer, so any two members of the family are compatible.

Results

Theorem (right-half-plane stability). Let $n\ge0$ and let $c_0,\dots,c_{n-1}$ be complex numbers with $\sum_{k<n}|c_k|^2/\binom nk\le1$. Then $$ q(z)=(1+z)^n+\sum_{k<n}c_kz^k $$ has no zero with $\operatorname{Re}z>0$. If $n\ge1$ and $q$ has a zero with $\operatorname{Re}z\ge0$, then that zero is $0$, $c_0=-1$ and $c_k=0$ for $0<k<n$.

Theorem (common interlacer). Let $n\ge1$, let $E_n(x)=\sum_k\binom{2n}{2k}x^k$ and $O_n(x)=\sum_k\binom{2n}{2k+1}x^k$ be the even and odd binomial sections, so that $x\,O_n(x^2)+E_n(x^2)=(1+x)^{2n}$, and for real $a_j$ put $$ G_a(x)=E_n(x)+\sum_{j=1}^{\lfloor n/2\rfloor}a_j\,x^j(1+x)^{n-2j}, \qquad \sum_{j=1}^{\lfloor n/2\rfloor}\frac{a_j^2}{16^j\binom n{2j}}\le1 . $$ Then $G_a$ is real-rooted with only negative roots and $O_n\ll G_a$. For any two such vectors $a$, $b$, the polynomials $G_a$ and $G_b$ are compatible: every combination $\alpha G_a+\beta G_b$ with $\alpha,\beta\ge0$ is zero or real-rooted.

Theorem (strict form). Call $a$ exceptional if $n=2m$, $a_m=-2^n$ and $a_j=0$ for all other $j\le n/2$. Let $n\ge1$ and let $a$ be non-exceptional with the bound above. Then $x\,O_n(x^2)+G_a(x^2)$ has all zeros in the open left half-plane, the roots of $O_n$ and of $G_a$ are simple, and $O_n$ and $G_a$ have no common root.

Proof

A Joukowski substitution turns $x\,O_n(x^2)+G_a(x^2)$ into a perturbation of $(1+z)^n$ that satisfies the coefficient bound of the first theorem, so it is Hurwitz stable. The Hermite–Biehler theorem for odd and even parts then gives $O_n\ll G_a$, and compatibility follows from the common interlacer $O_n$.

References

For Hurwitz stability and the Hermite–Biehler theorem, see [Hol03].

  1. [Hol03] Olga Holtz. Hermite--Biehler, Routh--Hurwitz, and total positivity. Linear Algebra and its Applications, 372, 105-110, 2003.
    BibTeX
    @article{Holtz2003,
      author = {Holtz, Olga},
      title = {Hermite--{B}iehler, {R}outh--{H}urwitz, and total positivity},
      year = {2003},
      journal = {Linear Algebra and its Applications},
      volume = {372},
      pages = {105--110},
      publisher = {Elsevier BV},
      doi = {10.1016/s0024-3795(03)00501-9},
      url = {http://dx.doi.org/10.1016/S0024-3795(03)00501-9},
      issn = {0024-3795}
    }

Definitions

  • The perturbation of (1 + X)^n with prescribed lower coefficients

    RealRooted.binomialCoefficientPerturbationsource
    @[expose] def binomialCoefficientPerturbation (n : ℕ) (c : ℕ → ℂ) : ℂ[X] :=
      (1 + X) ^ n + ∑ k ∈ Finset.range n, monomial k (c k)
  • The even-binomial section with γ-basis perturbations

    RealRooted.binomialPerturbationFamilysource
    @[expose] def binomialPerturbationFamily (n : ℕ) (a : ℕ → ℝ) : ℝ[X] :=
      evenBinomialSection n +
        ∑ j ∈ Finset.Icc 1 (n / 2),
          C (a j) * X ^ j * (1 + X) ^ (n - 2 * j)

Theorems

  • Weighted coefficient bounds give right-half-plane stability of perturbations of (1 + X)^nRealRooted original

    RealRooted.binomialCoefficientPerturbation_isRightHalfPlaneStablesource
    theorem binomialCoefficientPerturbation_isRightHalfPlaneStable
        (n : ℕ) (c : ℕ → ℂ)
        (hc : ∑ k ∈ Finset.range n, ‖c k‖ ^ 2 / (n.choose k : ℝ) ≤ 1) :
        IsRightHalfPlaneStable (binomialCoefficientPerturbation n c)
  • A zero with nonnegative real part is 0 and forces c₀ = -1 and all other cₖ = 0RealRooted original

    RealRooted.binomialCoefficientPerturbation_boundarysource
    theorem binomialCoefficientPerturbation_boundary
        {n : ℕ} (hn : n ≠ 0) (c : ℕ → ℂ)
        (hc : ∑ k ∈ Finset.range n, ‖c k‖ ^ 2 / (n.choose k : ℝ) ≤ 1)
        {z : ℂ} (hz : 0 ≤ z.re)
        (hzero : (binomialCoefficientPerturbation n c).eval z = 0) :
        z = 0 ∧ ∀ k < n, c k = if k = 0 then -1 else 0
  • The family is real-rooted with negative roots and interlaced by the odd binomial sectionMain resultRealRooted original

    RealRooted.binomialPerturbationFamily_negativeRoots_interlacedsource
    theorem binomialPerturbationFamily_negativeRoots_interlaced
        {n : ℕ} (hn : n ≠ 0) {a : ℕ → ℝ} (ha : BinomialPerturbationBound n a) :
        (binomialPerturbationFamily n a).Splits ∧
          (∀ r ∈ (binomialPerturbationFamily n a).roots, r < 0) ∧
          StrictInterl (oddBinomialSection n) (binomialPerturbationFamily n a)
  • x O_n(x²) + G_a(x²) is strictly Hurwitz stable away from one exceptional parameterRealRooted original

    RealRooted.oddEvenPolynomial_binomialPerturbationFamily_strictlyStablesource
    theorem oddEvenPolynomial_binomialPerturbationFamily_strictlyStable
        {n : ℕ} (hn : 0 < n) {a : ℕ → ℝ} (ha : BinomialPerturbationBound n a)
        (hexception : ¬ IsExceptionalBinomialPerturbation n a) :
        IsStrictlyHurwitzStable (oddEvenPolynomial
          (oddBinomialSection n) (binomialPerturbationFamily n a))
  • Away from the exceptional parameter the roots are simple and disjoint from the odd sectionRealRooted original

    RealRooted.binomialPerturbationFamily_simpleRoots_noCommonRootsource
    theorem binomialPerturbationFamily_simpleRoots_noCommonRoot
        {n : ℕ} (hn : 0 < n) {a : ℕ → ℝ} (ha : BinomialPerturbationBound n a)
        (hexception : ¬ IsExceptionalBinomialPerturbation n a) :
        HasSimpleRoots (oddBinomialSection n) ∧
          HasSimpleRoots (binomialPerturbationFamily n a) ∧
          ∀ r, ¬ ((oddBinomialSection n).IsRoot r ∧
            (binomialPerturbationFamily n a).IsRoot r)
  • Any two members of the family are compatibleRealRooted original

    RealRooted.binomialPerturbationFamily_compatiblesource
    theorem binomialPerturbationFamily_compatible
        {n : ℕ} (hn : n ≠ 0) {a b : ℕ → ℝ}
        (ha : BinomialPerturbationBound n a) (hb : BinomialPerturbationBound n b) :
        Compatible (binomialPerturbationFamily n a) (binomialPerturbationFamily n b)

Lean source RealRooted/Challenges/Roots/BinomialPerturbation.lean at revision d6670742. Formalized 2026-11-01.