Newtonの不等式(Newton's inequalities)とは、実数 $x_1,\dots,x_n$ の $k$ 次の基本対称式 $e_k$ を項の数で割った平均 $E_k=e_k/\binom nk$($E_0=1$)について、$1\le k\le n-1$ で $E_k^2\ge E_{k-1}E_{k+1}$ が成り立つという不等式であり、根がすべて実数である実係数多項式の係数 $a_k$ について $a_k/\binom nk$ が対数凹になることと同じである。微分と係数の反転で 2 次式の判別式に帰着させて証明できる。$x_i$ がすべて正なら、等号はすべての $x_i$ が等しいときに限り、Maclaurin の不等式 $E_1\ge E_2^{1/2}\ge\cdots\ge E_n^{1/n}$ が従う。
前提知識: 対称多項式, Rolleの定理, 代数学の基本定理, 相加相乗平均の不等式
2 つの実数 $x_1,x_2$ について、相加平均の平方と積の差は
$$
\Bigl(\frac{x_1+x_2}2\Bigr)^2-x_1x_2=\Bigl(\frac{x_1-x_2}2\Bigr)^2\ge0
$$
である。$n$ 個の実数 $x_1,\dots,x_n$ でも、$k$ 個ずつの積の和(基本対称式)$e_k$ を項の数 $\binom nk$ で割った「$k$ 次の平均」$E_k$ を考えると、隣り合う 3 つの平均の間に
$$
E_k^2\ge E_{k-1}E_{k+1}\qquad(1\le k\le n-1)
$$
が成り立つ。これが Newtonの不等式(Newton's inequalities)である。$n=2$、$k=1$ の場合が上の式である。
Newton の不等式は、平均の列 $E_0=1,E_1,\dots,E_n$ が対数凹(対数凹性)であることを主張している。すべての $x_i$ が正なら、これから
$$
E_1\ge E_2^{1/2}\ge E_3^{1/3}\ge\cdots\ge E_n^{1/n}
$$
という Maclaurin の不等式が従い、両端を比べたものが相加相乗平均の不等式 $\frac{x_1+\cdots+x_n}n\ge\sqrt[n]{x_1\cdots x_n}$ である。同じ不等式は、根がすべて実数である多項式の係数についての不等式としても言える。こちらの形では、組合せ論に現れる数列の対数凹性・単峰性を示す基本的な道具になる。
この記事では、Newton の不等式を、多項式の微分と係数の反転によって 2 次式の判別式に帰着させて証明する(thm-newton-window)。さらに、すべての $x_i$ が正のときの等号条件(thm-newton-equality)と Maclaurin の不等式(cor-newton-maclaurin)を証明する。3 つの数の場合を平方の和で示す高校数学の扱いは 基本対称式の平均の不等式 にある。
実数 $x_1,\dots,x_n$($n\ge1$)について、$k=0,1,\dots,n$ に対し
$$
e_k:=\sum_{1\le i_1< \cdots< i_k\le n}x_{i_1}\cdots x_{i_k},\qquad E_k:=\frac{e_k}{\binom nk}
$$
とおく($e_0=E_0=1$)。$e_k$ は $k$ 次の基本対称式、$E_k$ はその平均($k$ 個ずつの積 $\binom nk$ 個の相加平均)である。
$E_1=\frac{x_1+\cdots+x_n}n$ は相加平均、$E_n=x_1\cdots x_n$ は積である。すべての $x_i$ が同じ値 $a$ なら $E_k=a^k$ である。
$n\ge2$ とし、$x_1,\dots,x_n$ を実数とする。$1\le k\le n-1$ について
$$
E_k^2\ge E_{k-1}E_{k+1}
$$
が成り立つ。
def-newton-means の $e_k$ は、多項式 $\prod_{i=1}^n(t+x_i)=\sum_{k=0}^ne_kt^{n-k}$ の係数である。この多項式の根 $-x_1,\dots,-x_n$ はすべて実数である。逆に、実係数の多項式の根がすべて実数なら、それを $\prod(t+x_i)$ の定数倍と書いて Newton の不等式を当てられる。こうして、主定理は次の thm-newton-poly の形と同じことになる。証明は、両方の形をまとめて節「証明」の prf-newton-main で与える。
$p(t)=\sum_{k=0}^na_kt^k$ を次数 $n\ge2$ の実係数多項式とし、その複素数の根がすべて実数であるとする。$b_k:=a_k/\binom nk$ とおくと、$1\le k\le n-1$ について $b_k^2\ge b_{k-1}b_{k+1}$ である。言い換えると
$$
a_k^2\ge\Bigl(1+\frac1k\Bigr)\Bigl(1+\frac1{n-k}\Bigr)a_{k-1}a_{k+1}
$$
である。
最後の式は $\binom nk^2\big/\bigl(\binom n{k-1}\binom n{k+1}\bigr)=\frac{(k+1)(n-k+1)}{k(n-k)}=\bigl(1+\frac1k\bigr)\bigl(1+\frac1{n-k}\bigr)$ を $b_k^2\ge b_{k-1}b_{k+1}$ に代入したものである。係数 $a_k$ がすべて $0$ 以上で比 $b_k=a_k/\binom nk$ が対数凹であることを、対数凹性 では「超対数凹」と呼ぶ。
$k=1$ の不等式 $E_1^2\ge E_2$ は、$x_i$ の「ばらつき」が $0$ 以上であることにあたる。$\sum_ix_i^2=e_1^2-2e_2$ により
$$
\sum_{i< j}(x_i-x_j)^2=(n-1)\sum_ix_i^2-2e_2=(n-1)e_1^2-2ne_2
$$
であり、$E_1=e_1/n$、$E_2=2e_2/(n(n-1))$ なので
$$
E_1^2-E_2=\frac{(n-1)e_1^2-2ne_2}{n^2(n-1)}=\frac1{n^2(n-1)}\sum_{i< j}(x_i-x_j)^2\ge0
$$
である。等号はすべての $x_i$ が等しいときに限る。$k\ge2$ では、このように差を平方の和で書く方法は $n$ と $k$ によって形が変わり、一般の場合には向かない。そこで次節では、$E_k$ を多項式の係数として扱い、多項式の微分が「平均を 1 つ減らす」操作になることを使う。
証明の道具として、実数の列 $c=(c_0,c_1,\dots,c_n)$($n\ge0$)に対し
$$
F_c(t):=\sum_{j=0}^n\binom njc_jt^{n-j}=c_0t^n+\binom n1c_1t^{n-1}+\cdots+c_n
$$
とおく。$c=(E_0,E_1,\dots,E_n)$ なら $F_c(t)=\sum_ke_kt^{n-k}=\prod_i(t+x_i)$ である。$0$ でない多項式の複素数の根がすべて実数であるとき($0$ でない定数も含める)、その多項式は 実根だけをもつ という。
$c=(c_0,\dots,c_n)$ を実数の列とする。
1:$t^{n-j}$ を微分すると $(n-j)t^{n-1-j}$ であり、$\binom nj(n-j)=n\binom{n-1}j$ なので
$$
F_c'(t)=\sum_{j=0}^{n-1}\binom nj(n-j)c_jt^{n-1-j}=n\sum_{j=0}^{n-1}\binom{n-1}jc_jt^{(n-1)-j}=nF_{(c_0,\dots,c_{n-1})}(t)
$$
である($j=n$ の項は定数なので消える)。
2:$t^nF_c(1/t)=\sum_j\binom njc_jt^j$ であり、$\binom nj=\binom n{n-j}$ なので、$t^j$ の係数は列 $(c_n,\dots,c_0)$ の $n-j$ 番目の項 $c_j$ に $\binom n{n-j}$ を掛けたものである。
3:$F_c$ の次数を $d$、根 $0$ の重複度を $s$ とし、$F_c(t)=a\,t^s\prod_{i=1}^{d-s}(t-\rho_i)$($a\ne0$、$\rho_i$ は $0$ でない実数)と書くと
$$
t^nF_c(1/t)=a\,t^{n-d}\prod_{i=1}^{d-s}(1-\rho_it)=a\prod_i(-\rho_i)\cdot t^{n-d}\prod_{i=1}^{d-s}\Bigl(t-\frac1{\rho_i}\Bigr)
$$
である。根は $0$ と $1/\rho_i$ で、すべて実数である。$\square$
$q$ を次数 $m\ge1$ の実係数多項式で、実根だけをもつとする。
$q$ の相異なる根を $r_1< \cdots< r_s$、重複度を $m_1,\dots,m_s$ とすると、$\sum_im_i=m$ である。$q=(t-r_i)^{m_i}h$ と書けば $q'=(t-r_i)^{m_i-1}\bigl(m_ih+(t-r_i)h'\bigr)$ なので、$r_i$ は $q'$ の重複度 $m_i-1$ 以上の根である。また Rolleの定理 により、各区間 $(r_i,r_{i+1})$ に $q'$ の根 $\xi_i$ があり、これは $r_1,\dots,r_s$ のどれとも異なる。
1:こうして $q'$ の実根を重複度込みで $\sum_i(m_i-1)+(s-1)=m-1$ 個見つけた。$q'$ の次数は $m-1$ なので、代数学の基本定理 により根は重複度込みでちょうど $m-1$ 個であり、すべて実数である。
2:$s\ge2$ とする。$s\ge3$ なら $\xi_1\in(r_1,r_2)$ と $\xi_2\in(r_2,r_3)$ が $q'$ の相異なる根である。$s=2$ なら $m_1+m_2=m\ge3$ なので $m_1\ge2$ または $m_2\ge2$ であり、その $r_i$ と $\xi_1$ が $q'$ の相異なる根である。$\square$
$n\ge2$ とし、$c=(c_0,\dots,c_n)$ を実数の列で、$F_c$ が $0$ でなく実根だけをもつとする。$1\le k\le n-1$ について $c_k^2\ge c_{k-1}c_{k+1}$ である。
$c_{k-1}=c_k=c_{k+1}=0$ なら主張は $0\ge0$ である。以下、この 3 つのどれかは $0$ でないとする。
段 1(後ろを切る).lem-newton-ops の 1 を $n-k-1$ 回使うと、
$$
F_c^{(n-k-1)}=n(n-1)\cdots(k+2)\,F_{(c_0,\dots,c_{k+1})}
$$
である($k=n-1$ なら微分しない)。途中に現れる多項式は $F_{(c_0,\dots,c_j)}$($k+1\le j\le n$)の定数倍で、どれも $c_{k-1},c_k,c_{k+1}$ を係数に含むので $0$ でない。$0$ でない多項式の導関数が $0$ でないなら、その多項式の次数は $1$ 以上である。よって lem-newton-rolle の 1 を順に使えて、$G:=F_{(c_0,\dots,c_{k+1})}$ は実根だけをもつ。
段 2(反転する).lem-newton-ops の 3 により、$\tilde G:=F_{(c_{k+1},c_k,\dots,c_0)}$ は実根だけをもつ。
段 3(もう一度後ろを切る).$\tilde G$ に lem-newton-ops の 1 を $k-1$ 回使うと、段 1 と同じ理由で、
$$
\tilde G^{(k-1)}=(k+1)k\cdots3\,F_{(c_{k+1},c_k,c_{k-1})}=\frac{(k+1)!}2\bigl(c_{k+1}t^2+2c_kt+c_{k-1}\bigr)
$$
は $0$ でなく実根だけをもつ。
段 4(判別式).$c_{k+1}=0$ なら主張は $c_k^2\ge0$ で成り立つ。$c_{k+1}\ne0$ なら $c_{k+1}t^2+2c_kt+c_{k-1}$ は実根だけをもつ 2 次式なので、判別式について $(2c_k)^2-4c_{k+1}c_{k-1}\ge0$、すなわち $c_k^2\ge c_{k-1}c_{k+1}$ である。$\square$
thm-newton-main:$c=(E_0,\dots,E_n)$ とすると $F_c(t)=\prod_i(t+x_i)$ は最高次の係数が $1$ で $0$ でなく、根 $-x_i$ はすべて実数である。thm-newton-window から $E_k^2\ge E_{k-1}E_{k+1}$ を得る。
thm-newton-poly:$c_j:=b_{n-j}$ とおくと $F_c(t)=\sum_j\binom njb_{n-j}t^{n-j}=\sum_k\binom nkb_kt^k=p(t)$ である。thm-newton-window を番号 $n-k$ に当てると $b_k^2\ge b_{k+1}b_{k-1}$ を得る。$\square$
証明の要点は、lem-newton-ops の 1 により、微分が列 $c$ の最後の項を落とす操作になることである。$c=(E_0,\dots,E_n)$ について言えば、$\prod_i(t+x_i)$ の導関数を $n$ で割った多項式の根を $-y_1,\dots,-y_{n-1}$ とすると、$n-1$ 個の実数 $y_j$ の平均は $E_0,\dots,E_{n-1}$ と一致する。こうして変数の個数を減らしても平均は変わらない。反転は列の向きを逆にするので、2 つを組み合わせると、隣り合う 3 項 $(c_{k-1},c_k,c_{k+1})$ だけを残した 2 次式が得られる。
$n\ge2$ とし、$x_1,\dots,x_n$ を正の実数とする。ある $1\le k\le n-1$ で $E_k^2=E_{k-1}E_{k+1}$ となるのは、$x_1=\cdots=x_n$ のときに限る。
すべての $x_i$ が等しい値 $a$ なら $E_j=a^j$ で等号が成り立つ。逆を対偶で示す。$x_i$ がすべては等しくないとし、$1\le k\le n-1$ を固定する。$x_i>0$ なのですべての $E_j$ は正である。
$c=(E_0,\dots,E_n)$ について、prf-newton-window の段 1〜3 の多項式を順に見る。段 1 の $F_{(E_0,\dots,E_j)}$($k+1\le j\le n$)は最高次の係数が $E_0=1$ なので次数がちょうど $j$ であり、段 3 の $F_{(E_{k+1},\dots,E_j)}$($0\le j\le k-1$)は最高次の係数が $E_{k+1}>0$ なので次数がちょうど $k+1-j$ である。
はじめの $F_c=\prod_i(t+x_i)$ は相異なる根を 2 つ以上もつ。段 1 で微分する多項式の次数は $j\ge k+2\ge3$ なので、lem-newton-rolle の 2 により、$G=F_{(E_0,\dots,E_{k+1})}$ も相異なる根を 2 つ以上もつ。$G$ の定数項は $E_{k+1}\ne0$ なので根はどれも $0$ でなく、反転 $\tilde G$ の根はそれらの逆数だけである(lem-newton-ops の 3 の証明で、根 $0$ がなく、次数が $k+1$ に等しい場合)。$\rho\mapsto1/\rho$ は単射なので、$\tilde G$ も相異なる根を 2 つ以上もつ。段 3 で微分する多項式の次数は $k+1-j\ge3$($0\le j\le k-2$)なので、同じく最後の 2 次式 $E_{k+1}t^2+2E_kt+E_{k-1}$ も相異なる 2 つの実根をもつ。よって判別式は正で、$E_k^2>E_{k-1}E_{k+1}$ である。$\square$
$x_i\ge0$ に弱めると、この等号条件は一般には成り立たない。$(x_1,x_2,x_3)=(0,0,1)$ では $E_2=E_3=0$ なので $E_2^2=0=E_1E_3$ だが、$x_i$ は等しくない(反例の表)。証明では、$E_{k+1}\ne0$ を使って $G$ の根が $0$ でないことと反転の次数を保った。
$x_1,\dots,x_n$ を正の実数とすると
$$
E_1\ge E_2^{1/2}\ge E_3^{1/3}\ge\cdots\ge E_n^{1/n}
$$
である。どこか 1 か所で等号が成り立つのは、$x_1=\cdots=x_n$ のときに限る。特に $\frac{x_1+\cdots+x_n}n\ge\sqrt[n]{x_1\cdots x_n}$ である。
すべての $E_j$ は正である。$1\le k\le n-1$ を固定し、thm-newton-main の $j=1,\dots,k$ の不等式 $E_{j-1}E_{j+1}\le E_j^2$ を $j$ 乗して掛け合わせると
$$
\prod_{j=1}^k(E_{j-1}E_{j+1})^j\le\prod_{j=1}^kE_j^{2j}
$$
である(正の数の不等式なので掛け合わせてよい)。左辺で $E_i$ の指数を数えると、$1\le i\le k-1$ では $j=i+1$ から $i+1$、$j=i-1$ から $i-1$ で合わせて $2i$、$E_k$ は $j=k-1$ から $k-1$、$E_{k+1}$ は $j=k$ から $k$ であり、$E_0=1$ である。よって左辺は $\prod_{i=1}^{k-1}E_i^{2i}\cdot E_k^{k-1}E_{k+1}^k$ で、共通の因子を約すと
$$
E_k^{k-1}E_{k+1}^k\le E_k^{2k},\qquad\text{すなわち}\qquad E_{k+1}^k\le E_k^{k+1}
$$
である。両辺の $k(k+1)$ 乗根をとって $E_{k+1}^{1/(k+1)}\le E_k^{1/k}$ を得る。等号が成り立つなら、掛け合わせた不等式がすべて等号であり、とくに $j=1$ の $E_1^2=E_0E_2$ が成り立つので、thm-newton-equality により $x_i$ はすべて等しい。最後の主張は両端 $E_1\ge E_n^{1/n}$ である。$\square$
Maclaurin の不等式は、相加平均 $E_1$ と相乗平均 $E_n^{1/n}$ の間に $E_k^{1/k}$ を順に並べて、相加相乗平均の不等式を細かく分けたものである。
$(x_1,x_2,x_3,x_4)=(1,1,1,4)$ では $e_1=7$、$e_2=3+3\cdot4=15$、$e_3=1+3\cdot4=13$、$e_4=4$ なので
$$
E_1=\frac74,\qquad E_2=\frac{15}6=\frac52,\qquad E_3=\frac{13}4,\qquad E_4=4
$$
である。Newton の不等式は
$$
E_1^2=\frac{49}{16}\ge\frac52=E_0E_2,\qquad E_2^2=\frac{25}4\ge\frac{91}{16}=E_1E_3,\qquad E_3^2=\frac{169}{16}\ge10=E_2E_4
$$
で、どれも等号ではない(thm-newton-equality)。Maclaurin の不等式は $E_1=1.75$、$E_2^{1/2}=1.5811\ldots$、$E_3^{1/3}=1.4812\ldots$、$E_4^{1/4}=1.4142\ldots$ で、この順に減っている。
実係数の 3 次式 $t^3+at^2+bt+c$ の根が(重複度込みで)すべて実数なら、根を $-x_1,-x_2,-x_3$ として $t^3+at^2+bt+c=\prod_i(t+x_i)$ と書けるので、$e_1=a$、$e_2=b$、$e_3=c$、すなわち $E_1=\frac a3$、$E_2=\frac b3$、$E_3=c$ である。Newton の不等式から
$$
a^2\ge3b,\qquad b^2\ge3ac
$$
が従う。対偶により、たとえば $t^3+t^2+t+1$ は $a^2=1< 3=3b$ なので実数でない根をもつ。実際 $t^3+t^2+t+1=(t+1)(t^2+1)$ で、根は $-1,\pm i$ である。この 2 つの不等式は必要条件にすぎず、十分条件ではない(反例の表の 4 行目)。
実対称行列の固有値はすべて実数である(対称行列)。たとえば
$$
A=\begin{pmatrix}2&1&0\\1&2&1\\0&1&2\end{pmatrix}
$$
の特性多項式は、第 1 行で展開すると $\det(tI-A)=(t-2)^3-2(t-2)=t^3-6t^2+10t-4$ であり、固有値 $\lambda_1,\lambda_2,\lambda_3$ は $2-\sqrt2,\ 2,\ 2+\sqrt2$ である。根と係数の関係により $e_1=6$、$e_2=10$、$e_3=4$ なので、固有値の平均は $E_1=2$、$E_2=\frac{10}3$、$E_3=4$ で、$E_1^2=4\ge\frac{10}3$、$E_2^2=\frac{100}9\ge8=E_1E_3$ である。固有値はすべて正なので、Maclaurin の不等式 $2\ge\sqrt{10/3}=1.8257\ldots\ge4^{1/3}=1.5874\ldots$ も成り立つ。固有値を求めなくても、特性多項式の係数($e_1=\operatorname{tr}A$、$e_3=\det A$)だけから同じ不等式が読める。
| 外す条件・替える条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $x_i$ が実数(多項式なら根が実数) | $(x_1,x_2)=(i,-i)$、多項式 $t^2+1$ | $E_1^2=0< 1=E_0E_2$ |
| Maclaurin の不等式の「$x_i$ が正」 | $(x_1,x_2,x_3)=(-1,-1,-1)$ | $E_1=-1< 1=E_2^{1/2}$ |
| 等号条件の「$x_i$ が正」を「$0$ 以上」に | $(x_1,x_2,x_3)=(0,0,1)$ | $E_2^2=E_1E_3$ だが $x_i$ は等しくない |
| 逆向き(不等式をみたす列は実数の平均か) | $(E_0,E_1,E_2,E_3)=(1,1,1,\frac12)$ | Newton の不等式をみたすが、$F_E(t)=t^3+3t^2+3t+\frac12$ は実数でない根をもつ |
表の各行を確かめる。
1 行目:$e_1=i+(-i)=0$、$e_2=i\cdot(-i)=1$ なので $E_1=0$、$E_2=1$ である。複素数を許すと $\prod(t+x_i)=t^2+1$ は実根をもたず、thm-newton-window の仮定が成り立たない。$k=1$ の式 $E_1^2-E_2=\frac1{n^2(n-1)}\sum_{i< j}(x_i-x_j)^2$ は複素数でも成り立つが、$(i-(-i))^2=-4< 0$ で右辺が負になる。
2 行目:$e_1=-3$、$e_2=3$、$e_3=-1$ なので $E_1=-1$、$E_2=1$、$E_3=-1$ である。Newton の不等式 $E_1^2=1\ge1=E_2$、$E_2^2=1\ge1=E_1E_3$ は(等号で)成り立つが、$E_1=-1$ は $E_2^{1/2}=1$ より小さく、$E_3^{1/3}=-1$ は実数の 3 乗根としても $E_2^{1/2}$ より小さい。prf-newton-maclaurin は不等式を掛け合わせるところで $E_j>0$ を使っている。
3 行目:$e_1=1$、$e_2=e_3=0$ なので $E_1=\frac13$、$E_2=E_3=0$ で、$E_2^2=0=E_1E_3$ である。$k=1$ では $E_1^2=\frac19>0=E_2$ で等号でない。
4 行目:Newton の不等式は $1\ge1$、$1\ge\frac12$ でみたされる。一方 $t^3+3t^2+3t+\frac12=(t+1)^3-\frac12$ の根は $t+1$ が $\frac12$ の 3 乗根になる点で、実数の 3 乗根は 1 つだけなので、実根は $t=-1+2^{-1/3}$ だけであり、残り 2 つは実数でない。よって $E_k$ をこの値にもつ実数 $x_1,x_2,x_3$ は存在しない。
thm-newton-poly により、実根だけをもつ多項式の係数の列 $(a_k)$ について $(a_k/\binom nk)$ は対数凹、したがって $a_{k-1}a_{k+1}\ge0$ となる番号で $(a_k)$ も対数凹である。係数がすべて $0$ 以上なら、さらに係数の列は内部に零をもたず、単峰である(対数凹性 の系「非負係数で実根だけをもつ多項式」)。たとえば $t(t+1)(t+2)\cdots(t+n-1)$ の係数(符号なしの第 1 種 Stirling数)や $(1+t)^n$ の係数(二項係数)がこの例である。逆に、係数の比 $a_k/\binom nk$ が対数凹でも、多項式が実根だけをもつとは限らない(反例の表の 4 行目)。
実根だけをもつ多項式 $\sum_i\binom niA_ix^i$ について列 $(A_i)$ が対数凹であることと、係数が $0$ 以上なら内部に零をもたないことは Sta13 の Theorem 5.12 にあり、証明は微分・反転・微分で 2 次式に帰着させるもので、この記事の thm-newton-window と同じ筋である。同書は、内部に零をもたない非負の対数凹列が単峰であること(Proposition 5.11)と、$(1,0,0,1)$ のように内部に零をもつと単峰とは限らないことも述べる。この記事の lem-newton-ops による列 $c$ の切り出しの書き方、thm-newton-equality の証明(相異なる根が 2 つ以上残ることを追う)、cor-newton-maclaurin の掛け合わせの証明は、この記事で書いたものである。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する