Lemma 3.14 — reciprocal of bounded affine factors
ProvedQuantumBipartiteTesting.Bipartiteness.lemma_3_14complexity-theorygraph-property-testingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let be arbitrary real affine bivariate polynomials, let , and let be any real region on which every . Set . Then there is one real polynomial satisfying
throughout . The region need not be an integer grid, bounded, closed or nonempty. The number counts factors and is unrelated to graph degree. This gives the uniform reciprocal estimate used by the explicit construction.
Differences from the source:
- encoding: a given polynomial D_q=C product_i(1-z_i) → the product polynomial is written directly inside the conclusion; reason: substituting the source equality recovers exactly its statement, without an unrelated free denominator
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness
open Finset
theorem lemma_3_14 (d : ℕ) (z : Fin d → Bivariate)
(haffine : ∀ i, (z i).totalDegree ≤ 1) (C : ℝ) (hC : 0 < C) (region : Set (ℝ × ℝ))
(hz : ∀ x ∈ region, ∀ i, |Eval (z i) x.1 x.2| ≤ 1/4) :
∃ A : Bivariate, A.totalDegree ≤ 4*d+10 ∧
∀ x ∈ region, |Eval (MvPolynomial.C C * ∏ i, (1-z i)) x.1 x.2 * Eval A x.1 x.2 - 1| ≤ 1/100 := by sorry
end QuantumBipartiteTesting.Bipartiteness
Source
Chandrima Kayal, Sayantan Sen, Dániel Szabó, STOC 2027 submission #878 (October 2026), Lemma 3.14, PDF = printed page 18. 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.