Newton, Maclaurin and Laguerre–Samuelson inequalities

The elementary symmetric means of real numbers, and the coefficients of a real-rooted polynomial, satisfy Newton's and Maclaurin's inequalities, and the roots satisfy Laguerre's bound.

Results

For real numbers $x_1,\dotsc,x_n$ let $e_k$ be their elementary symmetric functions and $E_k=e_k/\binom nk$.

Newton's inequalities. $E_{k-1}E_{k+1}\le E_k^2$ for $0<k<n$. In polynomial form, for every real-rooted polynomial $p$ of degree $d$, $$(k+1)(d-k+1)\,p_{k-1}p_{k+1}\le k(d-k)\,p_k^2\qquad(0<k<d).$$ The same inequality holds with $d$ replaced by any $n\ge d$. The coefficients of $p$ are also log-concave: $p_{k-1}p_{k+1}\le p_k^2$.

Maclaurin's inequalities. If all $x_i\ge0$, then $$E_1\ge E_2^{1/2}\ge E_3^{1/3}\ge\dotsb\ge E_n^{1/n}.$$

Samuelson's inequality. Every $x_j$ lies within $\sqrt{n-1}\,s$ of the mean $\mu$, where $s^2=\frac1n\sum_i(x_i-\mu)^2$.

Laguerre's root bound. If $n\ge2$ and $x^n+ax^{n-1}+bx^{n-2}+\dotsb$ is real-rooted, every root $r$ satisfies $$\Bigl(r+\frac an\Bigr)^2\le\frac{n-1}n\Bigl(\frac{n-1}na^2-2b\Bigr).$$

Darroch's theorem. Let $p$ be a nonzero real-rooted polynomial with nonnegative coefficients and $\mu=p'(1)/p(1)$ the mean of the distribution $k\mapsto p_k/p(1)$. Every mode $k$ (an index with $p_k$ maximal) satisfies $|k-\mu|<1$.

References

I. Newton, Arithmetica Universalis (1707); C. Maclaurin, “A second letter to Martin Folkes,” Philosophical Transactions 36 (1729); E. Laguerre, “Sur une méthode pour obtenir par approximation les racines d'une équation algébrique qui a toutes ses racines réelles,” Nouvelles Annales de Mathématiques (1880); P. A. Samuelson, “How deviant can you be?”, Journal of the American Statistical Association 63 (1968), 1522–1525; G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, §2.22; J. N. Darroch, “On the distribution of the number of successes in independent trials,” Annals of Mathematical Statistics 35 (1964), 1317–1321.

Theorems

  • Newton's inequalities

    NewtonAux.newton_esymm_ineqsource
    theorem newton_esymm_ineq (t : Multiset ℝ) {n m : ℕ} (hn : Multiset.card t = n)
        (hm0 : 0 < m) (hmn : m < n) :
        t.esymm (m - 1) * t.esymm (m + 1) * ((m + 1 : ℝ) * ((n - m + 1 : ℕ) : ℝ)) ≤
          t.esymm m ^ 2 * ((m : ℝ) * ((n - m : ℕ) : ℝ))
  • Newton's inequalities for every real-rooted polynomial

    RealRooted.hasUltraLogConcaveCoeffs_of_eq_zero_or_splitssource
    theorem hasUltraLogConcaveCoeffs_of_eq_zero_or_splits {p : ℝ[X]} (hrr : p = 0 ∨ p.Splits) :
        HasUltraLogConcaveCoeffs p
  • Newton's inequalities at any level at least the degree

    RealRooted.coeffUltraLogConcaveUpTo_of_natDegree_lesource
    theorem coeffUltraLogConcaveUpTo_of_natDegree_le {p : ℝ[X]} {n : ℕ} (hpn : p.natDegree ≤ n)
        (hrr : p = 0 ∨ p.Splits) : CoeffUltraLogConcaveUpTo n fun k => p.coeff k
  • Real-rooted polynomials have log-concave coefficients

    RealRooted.hasLogConcaveCoeffs_of_eq_zero_or_splitssource
    theorem hasLogConcaveCoeffs_of_eq_zero_or_splits {p : ℝ[X]} (hrr : p = 0 ∨ p.Splits) :
        HasLogConcaveCoeffs p
  • Maclaurin's inequalitiesMain result

    RealRooted.Maclaurin.esymm_div_choose_rpow_lesource
    theorem esymm_div_choose_rpow_le (t : Multiset ℝ) {n k : ℕ} (hn : Multiset.card t = n)
        (ht : ∀ x ∈ t, 0 ≤ x) (hk : 0 < k) (hkn : k < n) :
        (t.esymm (k + 1) / n.choose (k + 1)) ^ ((1 : ℝ) / (k + 1)) ≤
          (t.esymm k / n.choose k) ^ ((1 : ℝ) / k)
  • Laguerre's root bound from the top coefficients

    RealRooted.Samuelson.sq_add_coeff_div_lesource
    theorem sq_add_coeff_div_le {p : ℝ[X]} {n : ℕ} (hmon : p.Monic) (hdeg : p.natDegree = n)
        (hn : 2 ≤ n) (hroots : Multiset.card p.roots = n) {r : ℝ} (hr : r ∈ p.roots) :
        (r + p.coeff (n - 1) / n) ^ 2 ≤
          (n - 1) / n * ((n - 1) / n * p.coeff (n - 1) ^ 2 - 2 * p.coeff (n - 2))
  • Samuelson's inequality

    RealRooted.Samuelson.abs_sub_mean_lesource
    theorem abs_sub_mean_le (t : Multiset ℝ) {r : ℝ} (hr : r ∈ t) :
        |r - t.sum / Multiset.card t| ≤
          √(Multiset.card t - 1) *
            √((t.map fun x => (x - t.sum / Multiset.card t) ^ 2).sum / Multiset.card t)
  • Darroch: the mode is within one of the mean

    Polynomial.abs_sub_lt_one_of_isModesource
    theorem abs_sub_lt_one_of_isMode {p : ℝ[X]} (hp : p ≠ 0) (hsplit : p.Splits)
        (hcoeff : ∀ i, 0 ≤ p.coeff i) {k : ℕ} (hk : ∀ j, p.coeff j ≤ p.coeff k) :
        |(k : ℝ) - (derivative p).eval 1 / p.eval 1| < 1

Lean source RealRooted/Challenges/Roots/NewtonMaclaurin.lean at revision d6670742. Formalized 2026-10-07.