Lemma 3.5 — signing probabilities and forest cancellation
ProvedQuantumBipartiteTesting.Bipartiteness.lemma_3_5complexity-theorygraph-property-testingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let be a consistent colored multigraph with incident vertices, distinct edges and connected components, and fix every edge sign. Then
If is a forest, the two probabilities agree for every signing. The probabilities are the finite averages of actual independent edge bits or vertex bits, rather than values stipulated by this formula. This is the cancellation used in the formal acceptance gap.
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
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness
open Finset
attribute [local instance] Classical.propDecidable
theorem lemma_3_5 {N colors : ℕ} (F : Finset (ColoredEdge N colors)) (hF : Consistent F)
(b : ColoredEdge N colors → Bool) :
SignProbNo F b = (2 : ℝ) ^ (-(F.card : ℤ)) ∧
SignProbYes F b = (if Balanced F b then
(2 : ℝ) ^ (-((Vertices F).card : ℤ) + (Components F).card) else 0) ∧
(Forest F → SignProbYes F b = SignProbNo F b) := by sorry
end QuantumBipartiteTesting.Bipartiteness
Source
Chandrima Kayal, Sayantan Sen, Dániel Szabó, STOC 2027 submission #878 (October 2026), Lemma 3.5, PDF = printed page 15. 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.