Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Translated arithmetic-grid degree bound with a zero boundary anchor

Proved
QuantumBipartiteTesting.Bipartiteness.zero_anchored_grid_degree

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

approximation-theorypolynomial-methodquantum-query-complexity

Fix γ>0\gamma>0γ>0. There is cγ>0c_\gamma>0cγ​>0 such that the following holds for positive integers CCC and R≥2R\ge2R≥2. Let QQQ be a real bivariate polynomial satisfying

∣Q(X,l)∣≤1|Q(X,l)|\le1∣Q(X,l)∣≤1

at every integer point with 1≤l≤R1\le l\le R1≤l≤R, ∣X−C∣≤R3/2/2|X-C|\le R^{3/2}/2∣X−C∣≤R3/2/2, and l∣Xl\mid Xl∣X. If

Q(C,0)=0,∣Q(C,1)∣≥γ,Q(C,0)=0,\qquad |Q(C,1)|\ge\gamma,Q(C,0)=0,∣Q(C,1)∣≥γ,

then

deg⁡Q≥cγR.\deg Q\ge c_\gamma\sqrt R.degQ≥cγ​R​.

This boundary-anchored variant of the translated arithmetic-grid degree estimate applies directly to polynomials retaining the gap's factor of lll. It replaces the original adjacent-point gap hypothesis by a nonzero value adjacent to a specified zero boundary value.

Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
open QuantumBipartiteTesting.Bipartiteness
open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.zero_anchored_grid_degree : ∀ γ : ℝ, 0 < γ → ∃ c : ℝ, 0 < c ∧
    ∀ C R : ℕ, 0 < C → 2 ≤ R → ∀ Q : Bivariate,
      (∀ X l : ℤ, 1 ≤ l → l ≤ (R:ℤ) →
        |(X:ℝ)-C| ≤ (R:ℝ)^(3/2:ℝ)/2 → l ∣ X → |Eval Q X l| ≤ 1) →
      Eval Q C 0 = 0 → γ ≤ |Eval Q C 1| → c*Real.sqrt R ≤ (Q.totalDegree:ℝ) := by sorry
Source
Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, Lemma 2.12 (translated ACL11 Lemma 4) and §3.5 polynomial argument, pp.11 and 19–20. Boundary-anchored variant derived by the same two-case proof, using the zero factor from Proposition 3.10. Endpoint argument adapted from https://github.com/formalcs/circuit-complexity/releases/tag/release%2F0.2.0, Apache 2.0.

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