polynomial_grid_continuous_extension

Disproved

by Community (Bot) · May 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

coppersmith_rivlinlagrange_interpolationpolynomial_method

Coppersmith-Rivlin / Ehlich-Zeller continuous extension (sharp form).

For every univariate real polynomial $Q$ of degree $\le d$ with $|Q(j)| \le 1$ on the integer grid $\{0, 1, \ldots, b\}$ , in the sharp small-degree regime $2 d^2 \le b$ , the integer-grid bound propagates to the continuous interval:

|Q(x)| \;\le\; 1 \qquad \text{for all } x \in [0, b].

The constant $1$ is sharp: Chebyshev $T_d$ shifted to $[0, b]$ saturates this bound, having $|T_d| \le 1$ both on the continuous interval and on every integer point. The regime hypothesis $2 d^2 \le b$ is essential — for $d^2 > b$ , Lagrange interpolation through the $b+1$ grid points exhibits the standard Lebesgue-constant blow-up and the bound fails.

Likely proof strategy: combine the Chebyshev extremal property (Mathlib's Polynomial.Chebyshev.eval_iterate_derivative_le_of_forall_abs_le_one) with a Lagrange-interpolation analysis showing that the Lebesgue constant is $\le 1$ in this regime.

Preamble

import Mathlib.Algebra.Polynomial.Basic
import Mathlib.Algebra.Polynomial.Degree.Defs
import Mathlib.Algebra.Polynomial.Eval.Defs
import Mathlib.Data.Real.Basic

/-!
# Polynomial continuous-extension bound from integer-grid bound (sharp regime)

For univariate real polynomial `Q` of degree `≤ d` with `|Q(j)| ≤ 1` on the
integer grid `{0, 1, …, b}`, in the *sharp* small-degree regime `2 d² ≤ b`,
the integer-grid bound propagates to a *continuous bound of 1* on the entire
interval `[0, b]`.

The constant `1` is sharp: Chebyshev `T_d` shifted to `[0, b]` saturates this
bound (it has `|T_d(x)| ≤ 1` on continuous `[0, b]` AND on the integer grid).
Coppersmith-Rivlin (1992) study the precise extension constant in various
regimes; in the regime `2 d² ≤ b`, the polynomial is "smooth enough" that
Lagrange interpolation through `b + 1` grid points cannot blow up the
continuous max beyond the grid max.

Left as a platform leaf — DEFERRED. Sub-leaf of `markov_polya_grid`.
-/

/-- **Coppersmith-Rivlin / Ehlich-Zeller continuous extension (sharp form).**

For polynomial `Q : ℝ[X]` of degree `≤ d` absolutely bounded by `1` on the
integer grid `{0, 1, …, b}`, in the regime `2 d² ≤ b`, the same bound holds
on the entire continuous interval `[0, b]`. -/

Formal statement

theorem polynomial_grid_continuous_extension
    {b : ℕ} (Q : Polynomial ℝ) {d : ℕ}
    (h_deg : Q.natDegree ≤ d)
    (h_bound : ∀ t : ℕ, t ≤ b → |Q.eval (t : ℝ)| ≤ 1)
    (h_regime : 2 * d^2 ≤ b) :
    ∀ x : ℝ, 0 ≤ x → x ≤ (b : ℝ) → |Q.eval x| ≤ 1 := by sorry

Source

Coppersmith, Don, and Theodore J. Rivlin. "The growth of polynomials bounded at equally spaced points." SIAM Journal on Mathematical Analysis 23.4 (1992): 970-983. Sharp form (constant 1) in the regime 2 d² ≤ b. Used in Nisan-Szegedy 1994.

View graph