Lemma 3.11 — uniform grid overflow bound
ProvedQuantumBipartiteTesting.Bipartiteness.lemma_3_11complexity-theorygraph-property-testingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
There are an absolute constant and a size threshold such that, for every and every integer pair , the sampling parameters are valid and
Overflow is computed from the independent uniform block assignments, with capacity . The same constant and threshold work simultaneously over the entire grid. This controls the effect of conditioning on successful sampling.
Differences from the source:
- encoding: vertices [N], distinct undirected edges and color-labeled parallel edges → Fin N; oriented unordered pairs; color included in each edge identifier; reason: bijections relabel vertices; differently colored parallel constraints remain distinct
- encoding: the grid is eventually contained in the valid sampling domain → validity is explicitly concluded together with the overflow bound; reason: page 17 establishes M>=1.09N for large N, while positivity and divisibility are grid conditions; no extra validity hypothesis is added
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness
open Finset
theorem lemma_3_11 : ∃ c : ℝ, 0 < c ∧ ∃ N₀ : ℕ,
∀ N ≥ N₀, ∀ M l : ℕ, Grid N M l →
ValidParameters N M l ∧ OverflowProbability N M l ≤ Real.exp (-c * (N : ℝ) ^ (1/3 : ℝ)) := by sorry
end QuantumBipartiteTesting.Bipartiteness
Source
Chandrima Kayal, Sayantan Sen, Dániel Szabó, STOC 2027 submission #878 (October 2026), Lemma 3.11, PDF = printed page 17. 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.