Remezの不等式

同義語:Remez inequalityRemez's inequality

概要

Remezの不等式(Remez inequality)とは、次数 $n$ 以下の実多項式 $p$ が、測度 $2-s$ 以上($0< s< 2$)の可測集合 $E\subset[-1,1]$ の上で $\lvert p\rvert\le1$ を満たすなら、$[-1,1]$ 全体で $\lvert p\rvert\le T_n\bigl(\frac{2+s}{2-s}\bigr)$($T_n$ は Chebyshev 多項式)である、という不等式。上界は $E$ の測度で決まり、$E$ が一方の端に詰まった区間で Chebyshev 多項式を移したものが等号を与える。Chebyshev の節点と測度で測った位置が同じ $E$ の点で Lagrange の補間公式を項ごとに比べて示せる。系として、最大値の $\delta$ 倍以下になる集合の測度は $8\delta^{1/n}$ 以下である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Chebyshev多項式, Lagrange補間, Lebesgue測度

Remez の不等式(Remez inequality)は、次数 $n$ 以下の実多項式 $p$ が区間 $[-1,1]$ のある部分集合 $E$ の上で $\lvert p\rvert\le1$ を満たすとき、$E$ の Lebesgue 測度だけから $[-1,1]$ 全体での $\lvert p\rvert$ の大きさを抑える不等式である。$\lvert E\rvert\ge2-s$($0< s< 2$)なら
$$ \max_{-1\le x\le1}\lvert p(x)\rvert\le T_n\Bigl(\frac{2+s}{2-s}\Bigr) $$
であり、右辺の $T_n$ は Chebyshev 多項式である。$E$ が区間なら、これは Chebyshev の古典的な評価(区間の外での多項式の増え方)であるが、Remez の不等式は $E$ がばらばらの小片の集まりでもよい。多項式は「測度が正の集合の上で小さければ全体でも小さい」という剛性をもち、その剛性の正確な量がこの不等式である。
E. J. Remez が 1936 年に示した(Rem36、Erd93 p. 172)。名前の似た Remezアルゴリズム は最良一様近似を求める反復法で、別の対象である。

内容箱
主定理と最良性thm-remez-main、prop-remez-sharp
Chebyshev 多項式の補間の恒等式lem-remez-cheb
端点での評価(証明の芯)lem-remez-endpoint
粗い形・小さい値をとる集合の測度・$L^q$ 版cor-remez-crude、cor-remez-sublevel、cor-remez-lq

主張

以下、$\mathcal P_n$ を次数 $n$ 以下の実係数多項式全体、$\lvert E\rvert$ を可測集合 $E\subset\mathbb R$ の Lebesgue 測度とする。$T_n$ は第 1 種の Chebyshev 多項式で、$-1\le x\le1$ では $T_n(x)=\cos(n\arccos x)$ である(Chebyshev多項式 の定義「Chebyshev 多項式」と定理「余弦の $n$ 倍角の公式」)。

Remez の不等式

$n\ge0$、$0< s< 2$ とし、$p\in\mathcal P_n$ と可測集合 $E\subset[-1,1]$ が $\lvert E\rvert\ge2-s$ と、すべての $x\in E$ での $\lvert p(x)\rvert\le1$ を満たすとする。このとき
$$ \max_{-1\le x\le1}\lvert p(x)\rvert\le T_n\Bigl(\frac{2+s}{2-s}\Bigr) $$
である。

証明の組み立て

証明は次節で与える(prf-thm-remez-main)。評価する点が区間の端にある場合を lem-remez-endpoint で示し、内側の点は区間を 2 つに分けて端の場合に帰着させる。端の場合の道具は Chebyshev 多項式の補間の恒等式(lem-remez-cheb)である。

$E$ の上の $\lvert p\rvert$ の上限で割れば、$\lvert E\rvert>0$ のとき $\max_{[-1,1]}\lvert p\rvert\le T_n\bigl(\frac{4-\lvert E\rvert}{\lvert E\rvert}\bigr)\sup_E\lvert p\rvert$ と書ける($s=2-\lvert E\rvert$)。区間 $I=[a,b]$ と可測集合 $E\subset I$ では、1 次の変数変換で $[-1,1]$ に移すと
$$ \max_{I}\lvert p\rvert\le T_n\Bigl(\frac{2\lvert I\rvert-\lvert E\rvert}{\lvert E\rvert}\Bigr)\sup_E\lvert p\rvert $$
である。右辺は $E$ の測度にしかよらず、$E$ の位置や形にはよらない。

準備:Chebyshev 多項式の補間の恒等式

相異なる $n+1$ 個の点 $x_0,\dots,x_n$ の Lagrange の基本多項式を $\ell_j(y)=\prod_{k\ne j}\frac{y-x_k}{x_j-x_k}$ とすると、すべての $p\in\mathcal P_n$ について $p=\sum_jp(x_j)\ell_j$ である(Lagrange補間)。$\ell_j(y)$ は、節点と $y$ に同じ 1 次の変換 $x\mapsto\alpha x+\beta$($\alpha\ne0$)を施しても変わらない。

Chebyshev 多項式の補間の恒等式

$n\ge1$ とし、$\eta_j:=\cos\frac{j\pi}n$($j=0,\dots,n$)を節点とする Lagrange の基本多項式を $\ell^\eta_j$ とする。

  1. $\lambda\ge1$ なら $T_n(\lambda)=\sum_{j=0}^n\lvert\ell^\eta_j(\lambda)\rvert$ である。
  2. $T_n$ は $[1,\infty)$ で狭義増加で、$T_n(1)=1$ である。
  3. $\lambda\ge1$ について $z:=\lambda+\sqrt{\lambda^2-1}$ とおくと $T_n(\lambda)=\frac12(z^n+z^{-n})\le z^n$ である。
符号を数える

1:Chebyshev多項式 の定理「Chebyshev 多項式の基本性質」の 4 により $T_n(\eta_j)=(-1)^j$ なので、$T_n=\sum_j(-1)^j\ell^\eta_j$ である。$\eta_0>\eta_1>\dots>\eta_n$ で $\lambda\ge1\ge\eta_0$ なので、$\ell^\eta_j(\lambda)$ の分子 $\prod_{k\ne j}(\lambda-\eta_k)$ は $0$ 以上であり、分母 $\prod_{k\ne j}(\eta_j-\eta_k)$ の因子のうち負のものは $k< j$ の $j$ 個である。よって $(-1)^j\ell^\eta_j(\lambda)=\lvert\ell^\eta_j(\lambda)\rvert$ で、1 を得る。
2:同じ定理の 3 により $T_n(x)=2^{n-1}\prod_k(x-x_k)$ で、根 $x_k$ はすべて $(-1,1)$ にある。$x>1$ で各因子は正で狭義増加なので、$T_n$ は $[1,\infty)$ で狭義増加である。$T_n(1)=1$ は同じ定理の 1 である。
3:Laurent 多項式 $T_n\bigl(\frac{w+w^{-1}}2\bigr)$ と $\frac12(w^n+w^{-n})$ は、$w=e^{i\theta}$ では $\frac{w+w^{-1}}2=\cos\theta$ なので Chebyshev多項式 の定理「余弦の $n$ 倍角の公式」により一致する。単位円の上の無限個の点で一致する Laurent 多項式は等しい($w^n$ を掛けると多項式の等式になる)。$w=z$ とおくと $\frac{z+z^{-1}}2=\lambda$ なので等式を得る。$z\ge1$ なので $z^{-n}\le z^n$ である。$\square$

証明

証明の芯は、評価する点が区間の端にある場合である。$E$ の点を、$E$ が区間 $[a,a+\lvert E\rvert]$ に詰まっている場合の Chebyshev の節点と「$E$ の測度で測った位置」が同じになるように選ぶと、Lagrange の公式の各項がその場合の値で抑えられる。

端点での評価

$n\ge1$、$a< b$ とし、$E\subset[a,b]$ をコンパクト集合で $\mu:=\lvert E\rvert>0$ とする。$p\in\mathcal P_n$ がすべての $x\in E$ で $\lvert p(x)\rvert\le1$ を満たすなら
$$ \lvert p(b)\rvert\le T_n\Bigl(\frac{2(b-a)-\mu}{\mu}\Bigr) $$
であり、$\lvert p(a)\rvert$ も同じ値で抑えられる。

測度で測った位置をそろえる

$\lvert p(a)\rvert$ の評価は $x\mapsto a+b-x$ で移した多項式と集合に $\lvert p(b)\rvert$ の評価を使えばよいので、$\lvert p(b)\rvert$ を示す。
比べる配置. $E^\flat:=[a,a+\mu]$ を $[-1,1]$ に移す 1 次関数を $M(x):=\frac{2(x-a)}\mu-1$ とし、$\xi_j:=M^{-1}(\eta_j)=a+\frac\mu2(1+\eta_j)$($\eta_j=\cos\frac{j\pi}n$)とおく。$\lambda:=M(b)=\frac{2(b-a)-\mu}\mu\ge1$ である。$t_j:=(a+\mu)-\xi_j$ とおくと $0=t_0< t_1< \dots< t_n=\mu$ である。
節点の選び方. $\varphi(x):=\lvert E\cap[x,b]\rvert$ は $[a,b]$ の上の連続な非増加関数で、$x< x'$ なら $\varphi(x)-\varphi(x')=\lvert E\cap[x,x')\rvert\le x'-x$ である。各 $t\in[0,\mu]$ について、$\varphi(x)=t$ となる $x\in E$ があることを示す。$t=0$ なら $x=\max E$ でよい。$t>0$ なら、閉集合 $\{x\in[a,b]\mid\varphi(x)\ge t\}$($\varphi(a)=\mu\ge t$ なので空でない)の最大元を $y$ とする。$\varphi(b)=0< t$ なので $y< b$ で、連続性から $\varphi(y)=t$ である。$y$ の最大性から $y< y'\le b$ で $\varphi(y')< t$ なので、$\lvert E\cap[y,y')\rvert>0$ である。よって $y$ のどんな右側の近くにも $E$ の点があり、$E$ は閉集合なので $y\in E$ である。
こうして $x_j\in E$ を $\varphi(x_j)=t_j$ となるように選ぶ。次の 2 つが成り立つ。

  • 離れている. $\lvert x_j-x_k\rvert\ge\lvert\varphi(x_j)-\varphi(x_k)\rvert=\lvert t_j-t_k\rvert=\lvert\xi_j-\xi_k\rvert$。とくに $x_j$ は相異なる。
  • $b$ に近い. $b-x_k=\varphi(x_k)+\lvert[x_k,b]\setminus E\rvert\le t_k+\lvert[a,b]\setminus E\rvert=t_k+(b-a-\mu)=b-\xi_k$。

まとめ. $x_0,\dots,x_n$ を節点とする Lagrange の公式と、$x_j\in E$ での $\lvert p(x_j)\rvert\le1$ から
$$ \lvert p(b)\rvert\le\sum_{j=0}^n\prod_{k\ne j}\frac{\lvert b-x_k\rvert}{\lvert x_j-x_k\rvert}\le\sum_{j=0}^n\prod_{k\ne j}\frac{b-\xi_k}{\lvert\xi_j-\xi_k\rvert}=\sum_{j=0}^n\lvert\ell^\eta_j(\lambda)\rvert=T_n(\lambda) $$
である。第 3 の等号は、基本多項式が 1 次の変換 $M$ で変わらないこと、最後の等号は lem-remez-cheb の 1 である。$\square$

主定理は、評価する点で区間を 2 つに分け、欠けた部分の割合が小さい方の区間にこの補題を使って示す。

欠けた部分の割合が小さい方の区間を使う

thm-remez-main を示す。$n=0$ なら $p$ は定数で、$E$ は空でないので $\lvert p\rvert\le1=T_0$ である。$n\ge1$ とし、$y\in[-1,1]$ を任意にとる。$0< \varepsilon< 2-s$ をとる。Lebesgue 測度の内部正則性から、コンパクト集合 $K\subset E$ で $\lvert K\rvert\ge2-s-\varepsilon$ となるものがある。$s':=2-\lvert K\rvert\le s+\varepsilon< 2$ とおく。
$[-1,y]$ と $[y,1]$ の長さを $L_1:=y+1$、$L_2:=1-y$、その中の $K$ の欠けた部分の測度を $\sigma_1:=L_1-\lvert K\cap[-1,y]\rvert$、$\sigma_2:=L_2-\lvert K\cap[y,1]\rvert$ とすると、$\sigma_1+\sigma_2=s'$、$L_1+L_2=2$ である。$L_i>0$ かつ $\sigma_i\le\frac{s'}2L_i$ となる $i$ がある。実際、$L_1=0$ なら $i=2$($\sigma_2=s'$、$L_2=2$)でよく、$L_2=0$ も同様である。両方が正で、どちらの $i$ でも $\sigma_i>\frac{s'}2L_i$ なら、足して $s'>s'$ となり矛盾する。
この $i$ の区間を $[a',b']$($y$ はその端点)とし、$K_i:=K\cap[a',b']$ とする。$\lvert K_i\rvert=L_i-\sigma_i\ge L_i(1-\frac{s'}2)>0$ なので、lem-remez-endpoint を $K_i$ に使えて、
$$ \lvert p(y)\rvert\le T_n\Bigl(\frac{2L_i-\lvert K_i\rvert}{\lvert K_i\rvert}\Bigr)=T_n\Bigl(\frac{1+r}{1-r}\Bigr),\qquad r:=\frac{\sigma_i}{L_i}\le\frac{s'}2 $$
である。$\frac{1+r}{1-r}$ は $r\in[0,1)$ で増加し、$T_n$ は $[1,\infty)$ で増加する(lem-remez-cheb の 2)ので、$\lvert p(y)\rvert\le T_n\bigl(\frac{2+s'}{2-s'}\bigr)\le T_n\bigl(\frac{2+s+\varepsilon}{2-s-\varepsilon}\bigr)$ である。$\varepsilon\to0$ とすると、$T_n$ の連続性から $\lvert p(y)\rvert\le T_n\bigl(\frac{2+s}{2-s}\bigr)$ を得る。$y$ は任意だった。$\square$

最良性

$n\ge0$、$0< s< 2$ について $p_s(x):=T_n\bigl(\frac{2x+s}{2-s}\bigr)$ とおく。$E=[-1,1-s]$ の上で $\lvert p_s\rvert\le1$ であり、$p_s(1)=T_n\bigl(\frac{2+s}{2-s}\bigr)$ である。したがって thm-remez-main の右辺は、$n$ と $s$ だけの式としてこれより小さくできない。

$x\mapsto\frac{2x+s}{2-s}$ は $[-1,1-s]$ を $[-1,1]$ に写し、$[-1,1]$ では $\lvert T_n\rvert\le1$ である。$x=1$ を代入すれば値を得る。$\lvert E\rvert=2-s$ である。$\square$

等号が成り立つのは、$\pm p_s$ と、それを $x\mapsto-x$ で移した $\pm T_n\bigl(\frac{-2x+s}{2-s}\bigr)$ に限る(Erd93 Theorem 3.1、p. 173)。証明が示すとおり、評価する点から見て $E$ が反対の端に詰まった配置が最も悪い。

位置による違い

$n=2$、$s=1$ とする。定理の上界は $T_2(3)=2\cdot3^2-1=17$ で、$E=[-1,0]$ の上で $\lvert p\rvert\le1$ の $p(x)=T_2(2x+1)=8x^2+8x+1$ は $p(1)=17$ に達する。同じ測度 $1$ でも $E=[-1,-\frac12]\cup[\frac12,1]$ と左右に分かれていると、$q(x)=\frac{8x^2-5}3$ は $E$ の上で $\lvert q\rvert\le1$($x^2\in[\frac14,1]$ で $-1\le q\le1$)を満たし、$[-1,1]$ での最大は $\lvert q(0)\rvert=\frac53$ にとどまる。定理の上界は、$E$ の形にかかわらず最も悪い配置の値である。

系

粗い形

thm-remez-main の仮定のもとで
$$ \max_{[-1,1]}\lvert p\rvert\le\Bigl(\frac{\sqrt2+\sqrt s}{\sqrt2-\sqrt s}\Bigr)^n\le\Bigl(\frac8{2-s}\Bigr)^n $$
であり、$0< s\le1$ なら $\max_{[-1,1]}\lvert p\rvert\le e^{2\sqrt2\,n\sqrt s}$ である。

$\lambda=\frac{2+s}{2-s}$ では $\lambda^2-1=\frac{8s}{(2-s)^2}$ なので、$z=\lambda+\sqrt{\lambda^2-1}=\frac{(\sqrt2+\sqrt s)^2}{2-s}=\frac{\sqrt2+\sqrt s}{\sqrt2-\sqrt s}$ である。lem-remez-cheb の 3 から第 1 の不等式を得る。$s< 2$ なので $(\sqrt2+\sqrt s)^2\le8$ で、第 2 の不等式を得る。$u:=\sqrt{s/2}$ とおくと $\log\frac{1+u}{1-u}=2\sum_{k\ge0}\frac{u^{2k+1}}{2k+1}\le\frac{2u}{1-u^2}$ で、$s\le1$ なら $u^2\le\frac12$ なので右辺は $4u=2\sqrt2\sqrt s$ 以下である。$\square$

Erd93 Corollary 3.2(p. 173)は、同じ形の評価を定数 $5$($0< s\le1$)と $8$($1< s< 2$)で述べている。$s\to0$ で上界が $1$ に近づくことは、$E$ が区間のほとんどを占めれば $p$ は $E$ の外でもほとんど大きくなれないことを表す。

小さい値をとる集合の測度

$p\in\mathcal P_n$($n\ge1$)を $0$ でない多項式とし、$M:=\max_{[-1,1]}\lvert p\rvert$ とする。$0< \delta\le1$ について
$$ \bigl\lvert\{x\in[-1,1]\mid\lvert p(x)\rvert\le\delta M\}\bigr\rvert\le8\,\delta^{1/n} $$
である。

左辺の集合を $E$、$m:=\lvert E\rvert$ とする。$m=0$ なら明らかである。$m\ge2$ なら右辺が $8\ge2$ なので成り立つ。$0< m< 2$ のとき、$q:=p/(\delta M)$ は $E$ の上で $\lvert q\rvert\le1$ なので、thm-remez-main と cor-remez-crude を $s=2-m$ で使うと $\frac1\delta=\max_{[-1,1]}\lvert q\rvert\le(8/m)^n$ であり、$m\le8\delta^{1/n}$ を得る。$\square$

多項式は、$[-1,1]$ の上で最大値の $\delta$ 倍以下になる部分の測度が $\delta^{1/n}$ の程度に限られる。$p(x)=x^n$ では $\{\lvert x\rvert^n\le\delta\}$ の測度が $2\delta^{1/n}$ なので、指数 $1/n$ は改善できない。

$L^q$ ノルムとの比較

$0< q< \infty$ と $p\in\mathcal P_n$ について
$$ \max_{[-1,1]}\lvert p\rvert\le T_n(3)\Bigl(\int_{-1}^1\lvert p(x)\rvert^q\,dx\Bigr)^{1/q} $$
である。$T_n(3)=\frac12\bigl((3+2\sqrt2)^n+(3-2\sqrt2)^n\bigr)$ である。

平均から大きい値の集合を測る

右辺の積分の $1/q$ 乗を $\tau$ とする。$\tau=0$ なら $p=0$ である。$\tau>0$ なら、$\tau^q\lvert\{\lvert p\rvert>\tau\}\rvert\le\int_{\{\lvert p\rvert>\tau\}}\lvert p\rvert^q\le\tau^q$ なので $\lvert\{\lvert p\rvert>\tau\}\rvert\le1$ で、$E:=\{x\in[-1,1]\mid\lvert p(x)\rvert\le\tau\}$ の測度は $1$ 以上である。$p/\tau$ に thm-remez-main を $s=1$ で使えば主張を得る。値は lem-remez-cheb の 3 で $\lambda=3$、$z=3+2\sqrt2$ とおいたものである。$\square$

$p$ の値が平均の程度を大きく超える部分の測度は小さいので、そこを除いた $E$ に Remez の不等式を使う、というのが典型的な使い方である。定数 $T_n(3)$ は $n$ について指数的に増える粗いものだが、$p$ の形によらない評価が一行で得られる。

反例:仮定を外すと成り立たないこと

外した仮定例成り立たなくなる結論
次数が $n$ 以下であること次数 $n+1$ の $T_{n+1}\bigl(\frac{2x+s}{2-s}\bigr)$$\max_{[-1,1]}\lvert p\rvert\le T_n\bigl(\frac{2+s}{2-s}\bigr)$
$E$ の測度が $2-s$ 以上であること(測度を直径に替える)$E_d:=[-1,-1+d]\cup[1-d,1]$、$p_d(x)=\frac{1-x^2}{2d-d^2}$($n=2$)$\max_{[-1,1]}\lvert p\rvert\le T_2\bigl(\frac{2+s}{2-s}\bigr)$($s$ を固定し、$d$ を小さくする)
$E$ の測度が正であること(有限集合に替える)$E=\{-\frac12,\frac12\}$、$p(x)=c\,(4x^2-1)$$\max_{[-1,1]}\lvert p\rvert\le C\sup_E\lvert p\rvert$ がどんな定数 $C$ でも成り立たない
反例の確かめ
3 つの行の確かめを開く

1 行目:$p=T_{n+1}\bigl(\frac{2x+s}{2-s}\bigr)$ は prop-remez-sharp と同じ理由で $E=[-1,1-s]$ の上で $\lvert p\rvert\le1$、$\lvert E\rvert=2-s$ を満たし、$p(1)=T_{n+1}(\lambda)$($\lambda=\frac{2+s}{2-s}>1$)である。lem-remez-cheb の 3 から $T_{n+1}(\lambda)-T_n(\lambda)=\frac12(z^n(z-1)+z^{-n-1}(1-z))=\frac12(z-1)(z^n-z^{-n-1})>0$($z>1$)なので、$p(1)>T_n(\lambda)$ で結論が成り立たない。

2 行目:$0< d\le1$ とする。$E_d$ の上では $1-x^2\in[0,2d-d^2]$ なので $0\le p_d\le1$ であり、$E_d$ の直径は $2$ で、どの $s\in(0,2)$ についても $2-s$ 以上である。一方 $p_d(0)=\frac1{2d-d^2}\ge\frac1{2d}$ は $d\to0$ で $\infty$ に近づくので、$s$ を固定すると、小さい $d$ で $p_d(0)>T_2\bigl(\frac{2+s}{2-s}\bigr)$ となり結論が成り立たない。$\lvert E_d\rvert=2d$ で測った thm-remez-main の上界 $T_2\bigl(\frac{4-2d}{2d}\bigr)$ は $d\to0$ で $\infty$ に近づき、こちらとは矛盾しない。

3 行目:$p(\pm\frac12)=0$ なので $\sup_E\lvert p\rvert=0$ だが、$\max_{[-1,1]}\lvert p\rvert=\lvert c\rvert\cdot3>0$($c\ne0$)である。次数 $n\ge2$ の多項式は $n$ 点で $0$ にできるので、測度 $0$ の有限集合の上の値では抑えられない。

関連する話題

  • Chebyshev の評価との関係. $E$ が区間 $[-1,1-s]$ のとき、thm-remez-main は「$[-1,1-s]$ で $\lvert p\rvert\le1$ なら $p(1)$ は $T_n$ を移したものの値以下」という Chebyshev の古典的な評価に一致する。Erd93 p. 172 は、Chebyshev の零点を数える方法が、$E$ が区間であるという情報なしには働かないことを述べている。上の証明は零点を数えず、Lagrange の公式の項ごとの比較で区間の場合に帰着させている。
  • 三角多項式. 次数 $n$ の三角多項式 $p$ が、$[-\pi,\pi]$ の測度 $2\pi-s$ 以上の部分集合で $\lvert p\rvert\le1$ を満たすなら、$0< s\le\frac\pi2$ で $\max\lvert p\rvert\le e^{c\,ns}$($c$ は絶対定数)である(Erd93 Theorem 3.4、p. 174)。cor-remez-crude の $\sqrt s$ に当たる所が $s$ になっている。
  • 応用. Remez の型の不等式は、直交多項式の Christoffel 関数の評価などの道具として使われる(Erd93 の §1 と §12)。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する