Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.11 — Subdivided NO instances retain distance α′/12

Open
QuantumBipartiteTesting.Bipartiteness.Supplement.lemma_4_11

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

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

Fix any α′>0\alpha'>0α′>0. For all sufficiently large intermediate orders nnn, let HHH be any graph in the support of the feasible law at (M0,2)(M_0,2)(M0​,2) and let G=RJ(H)G=R_J(H)G=RJ​(H) for any fixed simple cubic cloud with c>0c>0c>0 vertices. Put m=ncm=ncm=nc. For every set TTT of r≤m/4r\le m/4r≤m/4 distinct original edges, subdivide each selected edge exactly once, using a separate fresh vertex, to obtain G′G'G′ on m+rm+rm+r vertices. Then

dist⁡α′(G′)≥(α′/12) 4(m+r).\operatorname{dist}_{\alpha'}(G')\ge (\alpha'/12)\,4(m+r).distα′​(G′)≥(α′/12)4(m+r).

The selection can include external edges; the fresh vertex labeling is arbitrary. This retains the exact NO farness with the new vertex-count normalization, permitting arbitrary-size final instances.

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
  • generalization: logarithmically many colors and an expanding fixed cubic cloud → every positive color count and every simple cubic cloud; reason: the separated-block distance argument uses neither cloud expansion nor logarithmic color growth; it includes every source instance
  • encoding: subdivide r distinct edges once each → a finite selected edge set and arbitrary bijective fresh-vertex labels on Fin (nc+r); reason: no selection is excluded and the distance normalization uses the resulting size
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset

theorem lemma_4_11 (α' : ℝ) (hα : 0 < α') :
    ∃ n₀ : ℕ, 2 ≤ n₀ ∧ ∀ n ≥ n₀, ∀ c : ℕ, 0 < c →
      ∀ e : Fin (n*c) ≃ Fin n × Fin c, ∀ J : Finset (Edge c), Cubic J →
      ∀ H : Finset (ColoredEdge n c), InSupport n (Center n) 2 c H →
      ∀ T : Finset (Edge (n*c)), T ⊆ Replacement e J H → 4*T.card ≤ n*c →
      ∀ idx : {x // x ∈ T} ≃ Fin T.card,
        ExpansionFar 4 (α'/12) α' (Subdivision (Replacement e J H) T idx) := 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.11, printed page = PDF page 26; proof p.39

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