Finite formal-to-feasible comparison for one response monomial
ProvedQuantumBipartiteTesting.Bipartiteness.sampling_monomial_comparisonFix valid sampling parameters : there are hidden blocks, , and divides . Let be a canonical partial response table, with at most one non-null response at each query address, and assume that the block capacity satisfies
For either signing law , write for the product of the response indicators prescribed by . Then
The feasible expectation uses independent uniform block labels conditioned on no overflow, uniform compatible ambient injections, independent perfect matchings in each block and color, and the specified signing law. The formal term is the published partition-sum topology functional multiplied by its signing probability, and is zero for inconsistent tables.
This finite comparison supplies the monomial-level estimate used to pass from circuit response polynomials to the uniform formal-to-feasible acceptance error. The capacity hypothesis ensures that every placement of the observed pattern itself fits in a block, even when the full input assignment overflows.
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open QuantumBipartiteTesting.Bipartiteness Finset open scoped BigOperators Classical
theorem QuantumBipartiteTesting.Bipartiteness.sampling_monomial_comparison
{N colors : ℕ} (M l : ℕ) (hValid : ValidParameters N M l)
(T : GraphTable N colors) (hsmall : 4*T.val.card ≤ M/l) (s : Signing) :
|FeasibleBase N M l (fun F : Finset (ColoredEdge N colors) =>
SigningAverage s F (fun b =>
∏ az ∈ T.val, Indicators (LiftOracle (SignedResponse F b)) az)) -
FormalMonomial s T M l| ≤ OverflowProbability N M l := by sorry