Explicit total-degree geometric reciprocal truncation
ProvedQuantumBipartiteTesting.Bipartiteness.explicit_reciprocal_truncationgraph-property-testingpolynomial-approximationquantum-information
Let be a finite index set of cardinality , let be real affine polynomials, and let . Write for the complete homogeneous polynomial of degree in the , and define
Then has total degree at most . At every real pair for which all ,
This specifies the polynomial used in the source's reciprocal approximation, allowing its explicit instance in Lemma 3.15 to reuse the geometric truncation estimate. Empty index sets are included.
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open QuantumBipartiteTesting.Bipartiteness Finset
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.explicit_reciprocal_truncation {I : Type} [Fintype I] (z : I → Bivariate)
(haffine : ∀ i, (z i).totalDegree ≤ 1) (C : ℝ) (hC : 0 < C) :
(MvPolynomial.C C⁻¹ * ∑ j ∈ range (4*Fintype.card I+11), Homogeneous z j).totalDegree ≤
4*Fintype.card I+10 ∧
∀ M l : ℝ, (∀ i, |Eval (z i) M l| ≤ 1/4) →
|Eval (MvPolynomial.C C * ∏ i, (1-z i)) M l *
Eval (MvPolynomial.C C⁻¹ * ∑ j ∈ range (4*Fintype.card I+11), Homogeneous z j) M l - 1| ≤ 1/100 := by sorrySource
Kayal, Sen, Szabó, Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model, held October 2026 manuscript, Appendix A.5, PDF/printed pp. 35–36, equations (A.16)–(A.22); specialization in equation (20), p. 19 and Appendix A.6. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf