Markov brothers' inequality

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, the Markov brothers' inequality is an inequality proved in the 1890s by Andrey Markov and Vladimir Markov, two Russian mathematicians and brothers. This inequality bounds the maximum of the derivatives of a polynomial on an interval in terms of the maximum of the polynomial.[1] For k = 1 it was proved by Andrey Markov,[2] and for k = 2,3,... by his brother Vladimir Markov.[3]

The statement[edit]

Let P be a polynomial of degree ≤ n. Then

 \max_{-1 \leq x \leq 1} |P^{(k)}(x)| \leq \frac{n^2 (n^2 - 1^2) (n^2 - 2^2) \cdots (n^2 - (k-1)^2)}{1 \cdot 3 \cdot 5 \cdots (2k-1)} \max_{-1 \leq x \leq 1} |P(x)|.

Equality is attained for Chebyshev polynomials of the first kind.

Related inequalities[edit]

Applications[edit]

Markov's inequality is used to obtain lower bounds in computational complexity theory via the so-called "Polynomial Method".

References[edit]

  1. ^ Achiezer, N.I. (1992). Theory of approximation. New York: Dover Publications, Inc. 
  2. ^ Markov, A.A. (1890). "On a question by D. I. Mendeleev". Zap. Imp. Akad. Nauk SPb. 62: 1–24. 
  3. ^ Markov, V.A. (1892). "О функциях, наименее уклоняющихся от нуля в данном промежутке (On Functions of Least Deviation from Zero in a Given Interval)".  Appeared in German with a foreword by Sergei Bernstein as Markov, V.A. (1916). "Über Polynome, die in einem gegebenen Intervalle möglichst wenig von Null abweichen". Math. Ann. 77: 213–258. doi:10.1007/bf01456902.