Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Interior bound for a polynomial on an integer grid

Proved
QuantumBipartiteTesting.Bipartiteness.interior_integer_grid_bound

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-theorypolynomial-method

Let mmm be a positive integer and let ppp be a real univariate polynomial of degree less than 2m+22m+22m+2. Suppose

∣p(x)∣≤1for every integer −16m≤x≤16m+1.|p(x)|\le 1\qquad\text{for every integer }-16m\le x\le16m+1.∣p(x)∣≤1for every integer −16m≤x≤16m+1.

Then

∣p(z)∣≤43for every real 0≤z≤1.|p(z)|\le\frac43\qquad\text{for every real }0\le z\le1.∣p(z)∣≤34​for every real 0≤z≤1.

This quantitative interior estimate bounds the growth between adjacent grid points when the degree is small compared with their distance from the ends of the integer interval. It supplies the interior case of the translated arithmetic-grid degree argument.

Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.interior_integer_grid_bound
    (m : ℕ) (hm : 0 < m) (p : Polynomial ℝ) (hp : p.natDegree < 2*m+2)
    (hb : ∀ x : ℤ, -(16*(m:ℤ)) ≤ x → x ≤ 16*(m:ℤ)+1 → |p.eval (x:ℝ)| ≤ 1) :
    ∀ z : ℝ, 0 ≤ z → z ≤ 1 → |p.eval z| ≤ 4/3 := by sorry
Source
Auxiliary interior estimate for Lemma 2.12 of Kayal–Sen–Szabó, held October 2026 manuscript, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf; compare Ambainis–Childs–Liu 2011, https://arxiv.org/pdf/1012.3174, §C.3 Theorem 18 and Lemma 4. Symmetric finite-difference weights adapted from Saint Wesonga, https://github.com/formalcs/circuit-complexity/tree/release/0.2.0/Majority/ApproximateDegree, LowerBoundGrid.lean and MajorityWitness.lean (Apache 2.0); the fractional divided-difference estimate gives the explicit mesh sixteen and bound four-thirds.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me