Remez inequality

In mathematics, the Remez inequality, discovered by the Soviet mathematician Evgeny Yakovlevich Remez ( Remez 1936 ), gives a bound on the sup norms of certain polynomials, the bound being attained by the Chebyshev polynomials.

The inequality

Let σ be an arbitrary fixed positive number. Define the class of polynomials π_n(σ) to be those polynomials p of degree n for which

${\displaystyle |p(x)|\leq 1}$

on some set of measure ≥ 2 contained in the closed interval [−1, 1+σ]. Then the Remez inequality states that

${\displaystyle \sup _{p\in \pi _{n}(\sigma )}\left\|p\right\|_{\infty }=\left\|T_{n}\right\|_{\infty }}$

where T_n(x) is the Chebyshev polynomial of degree n, and the supremum norm is taken over the interval [−1, 1+σ].

Observe that T_n is increasing on ${\displaystyle [1,+\infty ]}$, hence

${\displaystyle \|T_{n}\|_{\infty }=T_{n}(1+\sigma ).}$

The R.i., combined with an estimate on Chebyshev polynomials, implies the following corollary: If J ⊂ R is a finite interval, and E ⊂ J is an arbitrary measurable set, then

${\displaystyle \max _{x\in J}|p(x)|\leq \left({\frac {4\,\,\operatorname {mes} J}{\operatorname {mes} E}}\right)^{n}\sup _{x\in E}|p(x)|}$

⁎

for any polynomial p of degree n.

Extensions: Nazarov–Turán lemma

Inequalities similar to ( ⁎ ) have been proved for different classes of functions, and are known as Remez-type inequalities. One important example is Nazarov's inequality for exponential sums ( Nazarov 1993 ):

Nazarov's inequality. Let

${\displaystyle p(x)=\sum _{k=1}^{n}a_{k}e^{\lambda _{k}x}}$

be an exponential sum (with arbitrary λ_k ∈C), and let J ⊂ R be a finite interval, E ⊂ J—an arbitrary measurable set. Then

${\displaystyle \max _{x\in J}|p(x)|\leq e^{\max _{k}|\Re \lambda _{k}|\,\operatorname {mes} J}\left({\frac {C\,\,\operatorname {mes} J}{\operatorname {mes} E}}\right)^{n-1}\sup _{x\in E}|p(x)|~,}$

where C > 0 is a numerical constant.

In the special case when λ_k are pure imaginary and integer, and the subset E is itself an interval, the inequality was proved by Pál Turán and is known as Turán's lemma.

This inequality also extends to ${\displaystyle L^{p}(\mathbb {T} ),\ 0\leq p\leq 2}$ in the following way

${\displaystyle \|p\|_{L^{p}(\mathbb {T} )}\leq e^{A(n-1)\operatorname {mes} (\mathbb {T} \setminus E)}\|p\|_{L^{p}(E)}}$

for some A > 0 independent of p, E, and n. When

${\displaystyle \operatorname {mes} E<1-{\frac {\log n}{n}}}$

a similar inequality holds for p > 2. For p = ∞ there is an extension to multidimensional polynomials.

Proof: Applying Nazarov's lemma to ${\displaystyle E=E_{\lambda }=\{x:|p(x)|\leq \lambda \},\ \lambda >0}$ leads to

${\displaystyle \max _{x\in J}|p(x)|\leq e^{\max _{k}|\Re \lambda _{k}|\,\operatorname {mes} J}\left({\frac {C\,\,\operatorname {mes} J}{\operatorname {mes} E_{\lambda }}}\right)^{n-1}\sup _{x\in E_{\lambda }}|p(x)|\leq e^{\max _{k}|\Re \lambda _{k}|\,\operatorname {mes} J}\left({\frac {C\,\,\operatorname {mes} J}{\operatorname {mes} E_{\lambda }}}\right)^{n-1}\lambda }$

thus

${\displaystyle \operatorname {mes} E_{\lambda }\leq C\,\,\operatorname {mes} J\left({\frac {\lambda e^{\max _{k}|\Re \lambda _{k}|\,\operatorname {mes} J}}{\max _{x\in J}|p(x)|}}\right)^{\frac {1}{n-1}}}$

Now fix a set ${\displaystyle E}$ and choose ${\displaystyle \lambda }$ such that ${\displaystyle \operatorname {mes} E_{\lambda }\leq {\tfrac {1}{2}}\operatorname {mes} E}$, that is

${\displaystyle \lambda =\left({\frac {\operatorname {mes} E}{2C\operatorname {mes} J}}\right)^{n-1}e^{-\max _{k}|\Re \lambda _{k}|\,\operatorname {mes} J}\max _{x\in J}|p(x)|}$

Note that this implies:

1. ${\displaystyle \operatorname {mes} E\setminus E_{\lambda }\geq {\tfrac {1}{2}}\operatorname {mes} E.}$
2. ${\displaystyle \forall x\in E\setminus E_{\lambda }:|p(x)|>\lambda .}$

Now

${\displaystyle {\begin{aligned}\int _{x\in E}|p(x)|^{p}\,{\mbox{d}}x&\geq \int _{x\in E\setminus E_{\lambda }}|p(x)|^{p}\,{\mbox{d}}x\\[6pt]&\geq \lambda ^{p}{\frac {1}{2}}\operatorname {mes} E\\[6pt]&={\frac {1}{2}}\operatorname {mes} E\left({\frac {\operatorname {mes} E}{2C\operatorname {mes} J}}\right)^{p(n-1)}e^{-p\max _{k}|\Re \lambda _{k}|\,\operatorname {mes} J}\max _{x\in J}|p(x)|^{p}\\[6pt]&\geq {\frac {1}{2}}{\frac {\operatorname {mes} E}{\operatorname {mes} J}}\left({\frac {\operatorname {mes} E}{2C\operatorname {mes} J}}\right)^{p(n-1)}e^{-p\max _{k}|\Re \lambda _{k}|\,\operatorname {mes} J}\int _{x\in J}|p(x)|^{p}\,{\mbox{d}}x,\end{aligned}}}$

which completes the proof.

Pólya inequality

One of the corollaries of the Remez inequality is the Pólya inequality, which was proved by George Pólya ( Pólya 1928 ), and states that the Lebesgue measure of a sub-level set of a polynomial p of degree n is bounded in terms of the leading coefficient LC(p) as follows:

${\displaystyle \operatorname {mes} \left\{x\in \mathbb {R}$ :\left|P(x)\right|\leq a\right\}\leq 4\left({\frac {a}{2\mathrm {LC} (p)}}\right)^{1/n},\quad a>0~.}

References

• Remez, E. J. (1936). "Sur une propriété des polynômes de Tchebyscheff". Comm. Inst. Sci. Kharkow. 13: 93–95.
• Bojanov, B. (May 1993). "Elementary Proof of the Remez Inequality". The American Mathematical Monthly. 100 (5). Mathematical Association of America: 483–485. doi:10.2307/2324304. JSTOR   2324304.
• Fontes-Merz, N. (2006). "A multidimensional version of Turan's lemma". Journal of Approximation Theory. 140 (1): 27–30. doi: 10.1016/j.jat.2005.11.012 .
• Nazarov, F. (1993). "Local estimates for exponential polynomials and their applications to inequalities of the uncertainty principle type". Algebra i Analiz. 5 (4): 3–66.
• Nazarov, F. (2000). "Complete Version of Turan's Lemma for Trigonometric Polynomials on the Unit Circumference". Complex Analysis, Operators, and Related Topics. Vol. 113. pp. 239–246. doi:10.1007/978-3-0348-8378-8_20. ISBN   978-3-0348-9541-5.
• Pólya, G. (1928). "Beitrag zur Verallgemeinerung des Verzerrungssatzes auf mehrfach zusammenhängende Gebiete". Sitzungsberichte Akad. Berlin: 280–282.