Lemma 3.15 — explicit reciprocal on the whole rectangle
ProvedQuantumBipartiteTesting.Bipartiteness.lemma_3_15complexity-theorygraph-property-testingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let be any natural-valued family with . For the explicit repeated-factor truncation in equation (20), eventually in ,
for every real and . The truncation degrees have a single universal bound, expressed with a globally defined small-query convention. The theorem concerns the constructed polynomial, not a freely chosen approximant, and retains the entire real rectangle.
Differences from the source:
- encoding: degree O(q log q) → a positive universal multiple of 1 + q log(q+2); reason: the two rates agree as q tends to infinity; the globally defined expression also retains q=0 and q=1 without artificial hypotheses
- encoding: suppose q=o(N^(1/3)) → quantify every natural-valued family q(N), using IsLittleO at infinity and one eventual threshold; reason: the source hypothesis is asymptotic, not a property of one isolated pair q,N
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness
open Finset
theorem lemma_3_15 :
(∃ Cdeg : ℝ, 0 < Cdeg ∧ ∀ q : ℕ,
(TruncationDegree q : ℝ) ≤ Cdeg * DegreeScale q) ∧
(∀ q : ℕ → ℕ,
Asymptotics.IsLittleO Filter.atTop (fun N => (q N : ℝ)) (fun N => (N : ℝ)^(1/3 : ℝ)) →
∃ N₀ : ℕ, ∀ N ≥ N₀,
(ReciprocalPolynomial N (q N)).totalDegree ≤ TruncationDegree (q N) ∧
∀ M l : ℝ, Rectangle N M l →
|Eval (Denominator (q N)) M l * Eval (ReciprocalPolynomial N (q N)) M l - 1| ≤ 1/100) := by sorry
end QuantumBipartiteTesting.Bipartiteness
Source
Chandrima Kayal, Sayantan Sen, Dániel Szabó, STOC 2027 submission #878 (October 2026), Lemma 3.15, PDF = printed page 19. 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.