One-sided smoothed polynomial step on a finite grid
ProvedMomentSearch.Supplement.smoothed_step_certificatemomentspolynomial-approximation
Let and be integers, and let be nonnegative integers with
There exists a real polynomial of degree at most such that, at every grid point ,
and moreover
This is the one-sided smoothed-step certificate underlying Theorem 18. It is independent of distributions and of the moment constraints.
The source states the bounds on real intervals and uses the weaker width threshold . Here only the integer grid is retained and the threshold uses , which is at least . Thus this is a specialization of the source lemma. The intended construction squares a shifted Chebyshev polynomial, integrates and normalizes the resulting nonnegative bump, and rescales to majorize the prefix indicator. The certificate's construction remains to be formalized.
Preamble
import Mathlib
Formal statement
namespace MomentSearch.Supplement
theorem smoothed_step_certificate (n k M W : ℕ) (hn : 3 ≤ n) (hk : 16 ≤ k)
(hW : 96 * ((n : ℝ) / k) * Real.logb 2 n ≤ (W : ℝ))
(hhalf : 2 * W ≤ n - 1) (hMW : M + W ≤ n - 1) :
∃ q : Polynomial ℝ, q.natDegree ≤ k ∧
(∀ t : Fin n, 0 ≤ q.eval (t.val : ℝ)) ∧
(∀ t : Fin n, t.val ≤ M → 1 ≤ q.eval (t.val : ℝ)) ∧
(∀ t : Fin n, q.eval (t.val : ℝ) ≤ 1 + 1 / (n : ℝ)^2) ∧
(∀ t : Fin n, M + W ≤ t.val → q.eval (t.val : ℝ) ≤ 1 / (n : ℝ)^2) := by sorry
end MomentSearch.Supplement
Source
Megow, Stein, Verschae, Distributionally Robust Search: The Power of Information and the Limits of Moments, arXiv:2611.04559, held version used by this mission; one-sided smoothed-step lemma (label lem:cert) and its proof in the appendix on moment recovery, immediately before Theorem 18. Grid restriction with the stronger base-2-log width hypothesis.