Translated arithmetic-grid degree bound with a zero boundary anchor
ProvedQuantumBipartiteTesting.Bipartiteness.zero_anchored_grid_degreeapproximation-theorypolynomial-methodquantum-query-complexity
Fix . There is such that the following holds for positive integers and . Let be a real bivariate polynomial satisfying
at every integer point with , , and . If
then
This boundary-anchored variant of the translated arithmetic-grid degree estimate applies directly to polynomials retaining the gap's factor of . 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 sorrySource
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.