Remez inequality explained

In mathematics, the Remez inequality, discovered by the Soviet mathematician Evgeny Yakovlevich Remez, 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 the nth degree for which

|p(x)| \le 1

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

\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

[ 1 , +inf ty] , hence \|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, thenfor 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's inequality. Let

p(x) = \sum ^{n} _{k =1} a _{k} e ^{λ _{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

max _{x} |p(x)| \leq e ^{max _{k} |\Re λ _{k|} mes J} \left( (C rm{mes)/(J}{ rm{mes} E}) \right) ^{n-1} \sup _{x} |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

L ^{p(T), 0\leq} p\leq 2 in the following way\|p\| _{L ^{p(T)}} \leq e ^{A(n} ( T \setminus E)}\|p\| _{L ^{p(E)}}

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

mes E < 1- (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

E = E _{λ=\{x: |p(x)|\leqλ\}, λ>0} leads tomax _{x} |p(x)| \leq e ^{max _{k} |\Re λ _{k|} mes J} \left( (C rm{mes)/(J}{ rm{mes} E) _{λ}} \right) ^{n-1} \sup _{x \in E _{λ}} |p(x)| \leq e ^{max _{k} |\Re λ _{k|} mes J} \left( (C rm{mes)/(J}{ rm{mes} E) _{λ}} \right) ^{n-1} λ

thus

rm{mes} E _{λ\leq} C rm{mes} J\left( (λ e ^{max _{k} |\Re λ _{k|} mes J})/(max _{x} |p(x)|) \right ) ^{(1)/(n -1)}

Now fix a set

E and choose λ such that rm{mes} E _{λ\leq\tfrac{1}{2}rm{mes}E} , that isλ= \left( (rm{mes)/(E}{ 2 C) mes J}\right) ^{n-1} e ^{-max _{k} |\Re λ _{k|} mes J} max _{x} |p(x)|

Note that this implies:

rm{mes}E\setminus E _{λ} \ge \tfrac{ 1 }{ 2 } rm{mes}E . \forall x \in E \setminus E _{λ} : |p(x)| > λ .

Now

\begin{align} \int _{x\in} |p(x)| ^{pdx} &\geq \int _{x\in E \setminus E _{λ}} |p(x)| ^{pdx} \\[ 6 pt] &\geq λ ^{p (1)/(2)} rm{mes} E \\[ 6 pt] & = (1)/(2) rm{mes} E \left( (rm{mes)/(E}{ 2 C) mes J}\right) ^{p(n-1)} e ^{- p max _{k} |\Re λ _{k|} mes J} max _{x} |p(x)| ^{p} \\[ 6 pt] &\geq (1)/(2) (rm{mes)/(E}{ rm{mes} J}\left( (rm{mes)/(E}{ 2 C)) mes J}\right) ^{p(n-1)} e ^{- p max _{k} |\Re λ _{k|} mes J} \int _{x} |p(x)| ^{pdx, \end{align}}

which completes the proof.

Pólya inequality

One of the corollaries of the R.i. is the Pólya inequality, which was proved by George Pólya, 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:

rm{mes} \left\{ x \in \R : \left|P(x)\right| \leq a \right\} \leq 4 \left( (a)/(2 LC (p)) \right) ^{1/n} , a > 0 ~.

References

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