Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.10 — Full rational acceptance identity and uniform feasible error with logarithmic colors

Open
QuantumBipartiteTesting.Bipartiteness.Supplement.lemma_4_10

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information

Let ccc be even with 400ln⁡n≤c≤Ccln⁡n400\ln n\le c\le C_c\ln n400lnn≤c≤Cc​lnn, where Cc>0C_c>0Cc​>0 is fixed. There is an absolute degree constant Cdeg>0C_{\rm deg}>0Cdeg​>0. There are C,κ>0C,\kappa>0C,κ>0 and an eventual order threshold depending only on CcC_cCc​, before any circuit or grid point, such that every actual finite complex qqq-query circuit has a bivariate polynomial FFF with

deg⁡F≤Cdeg(1+qln⁡(q+2)),pform(M,ℓ)=F(M,ℓ)Dq(M,ℓ).\deg F\le C_{\rm deg}(1+q\ln(q+2)),\qquad p_{\rm form}(M,\ell)=\frac{F(M,\ell)}{D_q(M,\ell)}.degF≤Cdeg​(1+qln(q+2)),pform​(M,ℓ)=Dq​(M,ℓ)F(M,ℓ)​.

This identity holds for all real ℓ≠0\ell\ne0ℓ=0 away from zeros of the unchanged common denominator. At every feasible integer point of the full grid where this expression is defined,

pfeas(M,ℓ)=F(M,ℓ)Dq(M,ℓ)+η(M,ℓ),∣η(M,ℓ)∣≤exp⁡(Cqln⁡n−κn1/3).p_{\rm feas}(M,\ell)=\frac{F(M,\ell)}{D_q(M,\ell)}+\eta(M,\ell),\qquad |\eta(M,\ell)|\le\exp(Cq\ln n-\kappa n^{1/3}).pfeas​(M,ℓ)=Dq​(M,ℓ)F(M,ℓ)​+η(M,ℓ),∣η(M,ℓ)∣≤exp(Cqlnn−κn1/3).

No small-query or tester-correctness hypothesis is imposed. The polynomial is chosen before all evaluations. Rationality and the formal-to-feasible estimate are conclusions. This supplies the unsigned acceptance bound needed for expansion testing.

Differences from the source:

  • encoding: vertices [n] and asymptotic notation → Fin n, natural logarithms and explicit uniform constants/thresholds; reason: bijective vertex labeling and logarithm-base changes preserve all source instances
  • reading: expected acceptance under the formal hard distribution → the published algebraic topology functional, not an overflow-completed probability law; reason: the inherited reading of equations (A.2)–(A.4) is retained; the comparison remains a theorem conclusion
  • encoding: O(q log q) and a rational expression on its domain → DegreeScale(q)=1+q ln(q+2), with ell nonzero, denominator nonzero, and valid sampling parameters; reason: the scale covers q=0,1 and has the same asymptotic order; the domain excludes only undefined source expressions
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset

theorem lemma_4_10 :
    ∃ Cdeg : ℝ, 0 < Cdeg ∧ ∀ Ccol : ℝ, 0 < Ccol →
      ∃ C κ : ℝ, 0 < C ∧ 0 < κ ∧ ∃ n₀ : ℕ, 2 ≤ n₀ ∧
        ∀ n ≥ n₀, ∀ c : ℕ, Even c →
          400 * Real.log n ≤ (c : ℝ) → (c : ℝ) ≤ Ccol * Real.log n →
          ∀ k w q : ℕ, ∀ E : Encoding (Fin n) k,
          ∀ A : Algorithm (Address n c) k w q,
          ∀ out : (Address n c × Bits k) × Fin w → Bool,
            ∃ F : Bivariate, (F.totalDegree : ℝ) ≤ Cdeg * DegreeScale q ∧
              (∀ M l : ℝ, l ≠ 0 → Eval (Denominator q) M l ≠ 0 →
                UnsignedFormal E A out M l = Eval F M l / Eval (Denominator q) M l) ∧
              (∀ M l : ℕ, Grid n M l → ValidParameters n M l →
                Eval (Denominator q) M l ≠ 0 →
                ∃ η : ℝ, UnsignedFeasible E A out M l =
                    Eval F M l / Eval (Denominator q) M l + η ∧
                  |η| ≤ Real.exp (C * q * Real.log n - κ * (n : ℝ) ^ (1/3 : ℝ))) := by sorry

end QuantumBipartiteTesting.Bipartiteness.Supplement
Source
Chandrima Kayal, Sayantan Sen, Dániel Szabó, STOC 2027 submission #878 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, Lemma 4.10, printed page = PDF page 25; proof p.26

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me