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)|\le1

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

\sup
p\in\pin(\sigma)

\left\|p\right\|infty=\left\|Tn\right\|infty

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

Observe that Tn is increasing on

[1,+infty]

, hence

\|Tn\|infty=Tn(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)=

n
\sum
k=1

ak

λkx
e

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

maxx|p(x)|\leq

maxk|\Reλk|mesJ
e

\left(

Crm{mes
J}{rm{mes}E}

\right)n-1\supx|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

Lp(T), 0\leqp\leq2

in the following way
\|p\|
Lp(T)

\leqeA(n(T\setminus

E)}\|p\|
Lp(E)

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

mesE<1-

logn
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 to

maxx|p(x)|\leq

maxk|\Reλk|mesJ
e

\left(

Crm{mes
J}{rm{mes}E

λ}\right)n-1

\sup
x\inEλ

|p(x)|\leq

maxk|\Reλk|mesJ
e

\left(

Crm{mes
J}{rm{mes}E

λ}\right)n-1λ

thus

rm{mes}Eλ\leqCrm{mes}J\left(

λ
maxk|\Reλk|mesJ
e
maxx|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}{2C

mesJ}\right)n-1

-maxk|\Reλk|mesJ
e

maxx|p(x)|

Note that this implies:

rm{mes}E\setminusEλ\ge\tfrac{1}{2}rm{mes}E.

\forallx\inE\setminusEλ:|p(x)|>λ.

Now

\begin{align} \intx\in|p(x)|pdx&\geq

\int
x\inE\setminusEλ

|p(x)|pdx\\[6pt] &\geq

p1
2
λ

rm{mes}E\\[6pt] &=

1
2

rm{mes}E\left(

rm{mes
E}{2C

mesJ}\right)p(n-1)

-pmaxk|\Reλk|mesJ
e

maxx|p(x)|p\\[6pt] &\geq

1
2
rm{mes
E}{rm{mes}J}\left(rm{mes
E}{2C

mesJ}\right)p(n-1)

-pmaxk|\Reλk|mesJ
e

\intx|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|\leqa\right\}\leq4\left(

a
2LC(p)

\right)1/n,a>0~.

References