Lemma 3.5 — Lagrange interpolation on integer nodes in and at integers
OpenQMomentMatch.FirstBound.Supplement.lemma_3_5interpolationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomials
Let and be integers and let be integers in . Define the Lagrange basis polynomials
- Every real polynomial of degree at most satisfies for all real .
- At every integer ,
The bound on the Lebesgue function at integer points is the step of Lemma 4.2's proof that produces its factor .
Differences from the source:
- encoding: nodes s_0 < ⋯ < s_d in {0} ∪ [A] → s : Fin (d + 1) → ℕ, StrictMono s, s i ≤ A; reason: same data
- encoding: P(x) = Σ P(s_i) L_i(x) → equality of evaluations at every real x; reason: polynomial identity over ℝ is equality at every real point
Preamble
import Mathlib
Formal statement
namespace QMomentMatch.FirstBound.Supplement
open Polynomial
/-- Lemma 3.5 (Lagrange interpolation), p. 17 (proof: Appendix A, p. 44). Nodes
`s_0 < ⋯ < s_d` in `{0} ∪ [A]` and `L_i(x) = ∏_{h ≠ i} (x − s_h)/(s_i − s_h)`. -/
theorem lemma_3_5 (A d : ℕ) (hA : 2 ≤ A) (hd : d ≤ A) (s : Fin (d + 1) → ℕ)
(hs : StrictMono s) (hsA : ∀ i, s i ≤ A) :
(∀ P : ℝ[X], P.natDegree ≤ d → ∀ x : ℝ,
P.eval x = ∑ i, P.eval (s i : ℝ) *
∏ h ∈ Finset.univ.erase i, (x - (s h : ℝ)) / ((s i : ℝ) - (s h : ℝ))) ∧
(∀ t : ℕ, t ≤ A →
∑ i, |∏ h ∈ Finset.univ.erase i, ((t : ℝ) - (s h : ℝ)) / ((s i : ℝ) - (s h : ℝ))| ≤
(4 : ℝ) ^ (A - 1)) := by sorry
end QMomentMatch.FirstBound.Supplement
Source
Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó, STOC 2027 submission #564 (October 2026), Lemma 3.5, p. 17 (proof: Appendix A, p. 44)