markov_unit
Provedalgebraanalysisgraph-theorynumber-theoryopen-problem
Classical Markov brothers inequality (A. Markov 1889), unit form: if a real polynomial Q of degree <= d satisfies |Q(x)| <= 1 for all x in [-1,1], then |Q'(c)| <= d^2 for all c in [-1,1]. Equality for the Chebyshev polynomial T_d. Standard proof routes: (1) Bernstein |Q'(x)| <= d/sqrt(1-x^2) on (-1,1), plus a Chebyshev-comparison argument |Q'(x)| <= T'_d(x) for |x| >= cos(pi/(2d)) via root counting at the zeros of T_d, then T'_d <= d^2 on [-1,1]. (2) Duffin-Schaeffer via Gauss-Lucas. (3) Zolotarev variational. NOT in Mathlib; needs Chebyshev T_d machinery (in Mathlib.RingTheory.Polynomial.Chebyshev / Mathlib.Analysis.SpecialFunctions.Trigonometric.Chebyshev).
Preamble
import Mathlib.Algebra.Polynomial.Basic import Mathlib.Algebra.Polynomial.Degree.Defs import Mathlib.Algebra.Polynomial.Derivative import Mathlib.Algebra.Polynomial.Eval.Defs import Mathlib.Data.Real.Basic
Formal statement
theorem markov_unit (Q : Polynomial ℝ) {d : ℕ} (hd : Q.natDegree ≤ d)
(h : ∀ x : ℝ, -1 ≤ x → x ≤ 1 → |Q.eval x| ≤ 1) :
∀ c : ℝ, -1 ≤ c → c ≤ 1 → |Q.derivative.eval c| ≤ (d : ℝ)^2 := by sorrySource
Nisan, Noam, and Mario Szegedy. "On the degree of Boolean functions as real polynomials." Computational Complexity 4.4 (1994): 301-313. (Bound used in Huang, Hao. "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture." Annals of Mathematics 190.3 (2019): 949-955.)