Lemma 2.12 — translated bivariate grid degree bound
ProvedQuantumBipartiteTesting.Bipartiteness.lemma_2_12complexity-theorygraph-property-testingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
For each fixed there is a constant . For every positive integer center , integer radius , and real bivariate polynomial , assume
If , then
The constant precedes and is independent of the center, radius and polynomial. The integer grid includes every integer horizontal coordinate satisfying the displayed conditions. This is the translated degree obstruction invoked after rescaling .
Differences from the source:
- encoding: positive integers C,R and an arithmetic grid with integer X,l → C,R are naturals with explicit positivity/radius conditions; X,l range over integers; reason: preserves the full arithmetic grid, the exact half-width, and the dependence only on gamma
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness
open Finset
theorem lemma_2_12 : ∀ γ : ℝ, 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 1 - Eval Q C 2| → c * Real.sqrt R ≤ (Q.totalDegree : ℝ) := by sorry
end QuantumBipartiteTesting.Bipartiteness
Source
Chandrima Kayal, Sayantan Sen, Dániel Szabó, STOC 2027 submission #878 (October 2026), Lemma 2.12, PDF = printed page 12. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.