Theorem 24 (Rakhmanov) — polynomials bounded on equidistant points
ProvedMomentSearch.theorem_24approximation-theorymomentsp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomials
For let be the set of equidistant points in . There is an absolute constant with the following property. Let be integers and let be a real polynomial of degree at most with . Let . Then
The paper cites this theorem from Rakhmanov (Ann. Math. 165 (2007), Theorem 1) and uses it to pass from a bound on a grid to a bound on the central part of the interval, without the restriction that Markov's inequality would impose.
Formalization Note The constant is chosen before , , and . The logarithm is base 2.
Differences from the source:
- encoding: κ < N (κ a natural number) → 1 ≤ κ < N; reason: N/κ is undefined at κ = 0 (Lean would read it as 0); the paper applies the theorem only with κ = k ≥ 1, and Rakhmanov's original assumes degree n ≥ 1
- encoding: log (the paper's standing convention: base 2) → Real.logb 2; reason: base 2 per §2.1; since C₀ is existential any fixed base gives an equivalent statement
Preamble
import Mathlib
Formal statement
namespace MomentSearch
/-- **Theorem 24** (Rakhmanov [Rak07, Theorem 1]), as stated in Megow, Stein, Verschae, *Distributionally Robust Search: The Power of Information and the Limits of Moments*, arXiv:2611.04559 (held version, sha256 fbfa4b43…), App. C.1, p.23 (PDF p.25).
Let `E_N = {ζ_j = −1 + (2j − 1)/N : j = 1, …, N}` be the set of `N` equidistant points in
`(−1, 1)`, let `κ < N`, and let `Q` be a polynomial of degree at most `κ` with
`max_{ζ∈E_N} |Q(ζ)| ≤ 1`. Let `r := √(1 − κ²/N²)`. Then there is an absolute constant `C₀` with
`|Q(x)| ≤ C₀ log (π / arctan((N/κ)√(r² − x²)))` for all `x ∈ (−r, r)`.
**Formalization Note.** The constant is absolute: it is chosen before `N`, `κ`, `Q` and `x`.
`κ ≥ 1` is required because `N/κ` is undefined at `κ = 0` (Lean would read it as `0`); the
paper applies the theorem only with `κ = k ≥ 1`. The logarithm is base 2 (the paper's standing
convention, §2.1); since `C₀` is existential any fixed base gives an equivalent statement. -/
theorem theorem_24 :
∃ C₀ : ℝ, ∀ N κ : ℕ, 1 ≤ κ → κ < N →
∀ Q : Polynomial ℝ, Q.natDegree ≤ κ →
(∀ j : ℕ, 1 ≤ j → j ≤ N → |Q.eval (-1 + (2 * (j : ℝ) - 1) / (N : ℝ))| ≤ 1) →
∀ r : ℝ, r = Real.sqrt (1 - (κ : ℝ) ^ 2 / (N : ℝ) ^ 2) →
∀ x : ℝ, -r < x → x < r →
|Q.eval x| ≤
C₀ * Real.logb 2
(Real.pi / Real.arctan ((N : ℝ) / (κ : ℝ) * Real.sqrt (r ^ 2 - x ^ 2))) := by sorry
end MomentSearch
Source
Megow, Stein, Verschae, Distributionally Robust Search: The Power of Information and the Limits of Moments, arXiv:2611.04559 (held version, sha256 fbfa4b43…), App. C.1, Theorem 24 (Rakhmanov [Rak07, Theorem 1]), p.23 (PDF p.25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.