Local Newton defects and roots

For a polynomial with only negative roots, the ratio $a_i/a_{i+1}$ of consecutive coefficients approximates the modulus of the $(i+1)$st root closest to the origin. Explicit bounds hold when the local Newton defects $a_{k-1}a_{k+1}/a_k^2$ at $k=i,i+1$ are small, and the approximation becomes asymptotically exact as these defects tend to $0$.

Results

Let $x_0\ge x_1\ge\dots>0$, let $e_k$ be the $k$th elementary symmetric polynomial of $x_0,\dots,x_{n-1}$, and let $L_k=x_0\cdots x_{k-1}$. Put $\eta_i=x_i^{-1}$ and $\rho_i=e_i/e_{i+1}$, so the roots of $\prod_{i<n}(1+x_iX)$ are $-\eta_0,\dots,-\eta_{n-1}$ with $\eta_0\le\dots\le\eta_{n-1}$. The local Newton defect is $\delta_k=e_{k-1}e_{k+1}/e_k^2$ for $0<k<n$ and $\delta_k=0$ otherwise. Put $C(u)=(1+\sqrt{1-4u})/2$.

Theorem (off-diagonal estimate). For nonnegative $x_i$ and all $n,k$, $$e_k^2-\sum_{|S|=k}\prod_{i\in S}x_i^2\le2\,e_{k-1}e_{k+1}.$$

Theorem (leading subset). For $k\le n$, $$1-2\delta_k\le\frac{L_k}{e_k}\le1.$$ If $\delta_k\le\frac14$, then $C(\delta_k)\le L_k/e_k$.

Theorem (root parameters). Let $i<n$. If $1-2\delta_{i+1}>0$, then $$(1-2\delta_i)\,\rho_i\le\eta_i\le\frac{\rho_i}{1-2\delta_{i+1}}.$$ If $\delta_i,\delta_{i+1}\le\frac14$, then $$C(\delta_i)\,\rho_i\le\eta_i\le\frac{\rho_i}{C(\delta_{i+1})}.$$ If $i+1<n$ and $\delta_{i+1}\le\frac14$, then $$\frac{\eta_i}{\eta_{i+1}}\le\frac{1-C(\delta_{i+1})}{C(\delta_{i+1})}.$$

Theorem (polynomial form). Let $a_0>0$ and $p=a_0\prod_{i<n}(1+x_iX)$ with coefficients $a_k$. The two-sided bounds for $\eta_i$ above hold with $\rho_i$ replaced by $a_i/a_{i+1}$ and $\delta_k$ by $a_{k-1}a_{k+1}/a_k^2$ (and $0$ for $k=0$ or $k\ge n$).

Theorem (asymptotics). Fix $i$. Let $p^{(a)}=a_0^{(a)}\prod_{j<n_a}(1+x^{(a)}_jX)$ be a family indexed along a filter, for example a sequence, with $a_0^{(a)}>0$, each $x^{(a)}$ positive and decreasing, and eventually $i<n_a$. If the defects of $p^{(a)}$ at $i$ and $i+1$ tend to $0$, then $\eta^{(a)}_i\sim a^{(a)}_i/a^{(a)}_{i+1}$.

References

  1. [KV17] Irina Karpenko & Anna M. Vishnyakova. On sufficient conditions for a polynomial to be sign-independently hyperbolic or to have real separated zeros. Mathematical Inequalities &amp; Applications, (1), 237-245, 2017.
    BibTeX
    @article{KarpenkoVishnyakova2017,
      author = {Karpenko, Irina and Vishnyakova, Anna M.},
      title = {On sufficient conditions for a polynomial to be sign-independently hyperbolic or to have real separated zeros},
      year = {2017},
      journal = {Mathematical Inequalities &amp; Applications},
      number = {1},
      pages = {237--245},
      doi = {10.7153/mia-20-18},
      url = {https://doi.org/10.7153/mia-20-18}
    }
  2. [AGS17] Marianne Akian, Stéphane Gaubert, & Meisam Sharify. Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots. Linear Algebra and its Applications, 528, 394-435, 2017.
    BibTeX
    @article{AkianGaubertSharify2017,
      author = {Akian, Marianne and Gaubert, Stéphane and Sharify, Meisam},
      title = {Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots},
      year = {2017},
      journal = {Linear Algebra and its Applications},
      volume = {528},
      pages = {394--435},
      doi = {10.1016/j.laa.2016.11.004},
      url = {https://doi.org/10.1016/j.laa.2016.11.004}
    }

Theorems

  • Off-diagonal elementary-symmetric bound

    RealRooted.NewtonDefectRoots.esym_sq_sub_sq_esym_lesource
    theorem esym_sq_sub_sq_esym_le (x : ℕ → ℝ) (hx : ∀ i, 0 ≤ x i) (n k : ℕ) :
        esym x n k ^ 2 - esym (fun i => x i ^ 2) n k ≤
          2 * esym x n (k - 1) * esym x n (k + 1)
  • Linear box for the leading-subset ratio

    RealRooted.NewtonDefectRoots.leadingRatio_mem_linear_boxsource
    theorem leadingRatio_mem_linear_box
        (x : ℕ → ℝ) (hpos : ∀ i, 0 < x i) (hanti : Antitone x)
        {n k : ℕ} (hkn : k ≤ n) :
        1 - 2 * localDefect x n k ≤ leadingRatio x n k ∧
          leadingRatio x n k ≤ 1
  • Quadratic lower bound for the leading-subset ratio

    RealRooted.NewtonDefectRoots.defectConstant_le_leadingRatiosource
    theorem defectConstant_le_leadingRatio
        (x : ℕ → ℝ) (hpos : ∀ i, 0 < x i) (hanti : Antitone x)
        {n k : ℕ} (hkn : k ≤ n) (hquarter : localDefect x n k ≤ 1 / 4) :
        defectConstant (localDefect x n k) ≤ leadingRatio x n k
  • Linear local-defect box for a root parameter

    RealRooted.NewtonDefectRoots.rootParameter_mem_linear_boxsource
    theorem rootParameter_mem_linear_box
        (x : ℕ → ℝ) (hpos : ∀ i, 0 < x i) (hanti : Antitone x)
        {n i : ℕ} (hi : i < n)
        (hright : 0 < 1 - 2 * localDefect x n (i + 1)) :
        (1 - 2 * localDefect x n i) * coefficientRatio x n i ≤
            rootParameter x i ∧
          rootParameter x i ≤ coefficientRatio x n i /
            (1 - 2 * localDefect x n (i + 1))
  • Quadratic local-defect box for a root parameter

    RealRooted.NewtonDefectRoots.rootParameter_mem_quadratic_boxsource
    theorem rootParameter_mem_quadratic_box
        (x : ℕ → ℝ) (hpos : ∀ i, 0 < x i) (hanti : Antitone x)
        {n i : ℕ} (hi : i < n)
        (hleftQuarter : localDefect x n i ≤ 1 / 4)
        (hrightQuarter : localDefect x n (i + 1) ≤ 1 / 4) :
        defectConstant (localDefect x n i) * coefficientRatio x n i ≤
            rootParameter x i ∧
          rootParameter x i ≤ coefficientRatio x n i /
            defectConstant (localDefect x n (i + 1))
  • Adjacent root-parameter separation

    RealRooted.NewtonDefectRoots.rootParameter_div_succ_lesource
    theorem rootParameter_div_succ_le
        (x : ℕ → ℝ) (hpos : ∀ i, 0 < x i) (hanti : Antitone x)
        {n i : ℕ} (hi : i + 1 < n)
        (hquarter : localDefect x n (i + 1) ≤ 1 / 4) :
        rootParameter x i / rootParameter x (i + 1) ≤
          (1 - defectConstant (localDefect x n (i + 1))) /
            defectConstant (localDefect x n (i + 1))
  • Linear box in polynomial coefficients

    RealRooted.NewtonDefectRoots.factorPolynomial_rootParameter_mem_linear_boxsource
    theorem factorPolynomial_rootParameter_mem_linear_box
        (a₀ : ℝ) (ha₀ : 0 < a₀) (x : ℕ → ℝ)
        (hpos : ∀ i, 0 < x i) (hanti : Antitone x)
        {n i : ℕ} (hi : i < n)
        (hright : 0 < 1 - 2 * polynomialLocalDefect
          (factorPolynomial a₀ x n) n (i + 1)) :
        (1 - 2 * polynomialLocalDefect (factorPolynomial a₀ x n) n i) *
            polynomialCoefficientRatio (factorPolynomial a₀ x n) i ≤
            rootParameter x i ∧
          rootParameter x i ≤
            polynomialCoefficientRatio (factorPolynomial a₀ x n) i /
              (1 - 2 * polynomialLocalDefect
                (factorPolynomial a₀ x n) n (i + 1))
  • Quadratic box in polynomial coefficients

    RealRooted.NewtonDefectRoots.factorPolynomial_rootParameter_mem_quadratic_boxsource
    theorem factorPolynomial_rootParameter_mem_quadratic_box
        (a₀ : ℝ) (ha₀ : 0 < a₀) (x : ℕ → ℝ)
        (hpos : ∀ i, 0 < x i) (hanti : Antitone x)
        {n i : ℕ} (hi : i < n)
        (hleftQuarter : polynomialLocalDefect (factorPolynomial a₀ x n) n i ≤ 1 / 4)
        (hrightQuarter : polynomialLocalDefect
          (factorPolynomial a₀ x n) n (i + 1) ≤ 1 / 4) :
        defectConstant (polynomialLocalDefect (factorPolynomial a₀ x n) n i) *
            polynomialCoefficientRatio (factorPolynomial a₀ x n) i ≤
            rootParameter x i ∧
          rootParameter x i ≤
            polynomialCoefficientRatio (factorPolynomial a₀ x n) i /
              defectConstant (polynomialLocalDefect
                (factorPolynomial a₀ x n) n (i + 1))
  • Root parameters asymptotic to coefficient ratiosMain result

    RealRooted.NewtonDefectRoots.factorPolynomial_rootParameter_isEquivalent_coefficientRatiosource
    theorem factorPolynomial_rootParameter_isEquivalent_coefficientRatio
        {α : Type*} {l : Filter α} (a₀ : α → ℝ) (x : α → ℕ → ℝ)
        (n : α → ℕ) (i : ℕ) (ha₀ : ∀ a, 0 < a₀ a)
        (hpos : ∀ a j, 0 < x a j) (hanti : ∀ a, Antitone (x a))
        (hi : ∀ᶠ a in l, i < n a)
        (hleft : Filter.Tendsto
          (fun a => polynomialLocalDefect (factorPolynomial (a₀ a) (x a) (n a)) (n a) i)
          l (𝓝 0))
        (hright : Filter.Tendsto
          (fun a => polynomialLocalDefect
            (factorPolynomial (a₀ a) (x a) (n a)) (n a) (i + 1)) l (𝓝 0)) :
        (fun a => rootParameter (x a) i) ~[l]
          (fun a => polynomialCoefficientRatio
            (factorPolynomial (a₀ a) (x a) (n a)) i)

Lean source RealRooted/Challenges/Roots/NewtonDefectRoots.lean at revision d6670742. Formalized 2026-10-11.