Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.7 — colour sampling: a uniformly random set of T≥r10T\ge r^{10}T≥r10 disjoint colour sets is nice with probability ≥0.9\ge0.9≥0.9

Proved
PolySwap.KMS.lemma_3_7

by Shuze Chen · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

high-dimensional-expandersp2o-gran-per-chapterp2o-plan-paperp2o-v1swap-coboundary-expansion

Let r≥104r\ge10^4r≥104, T≥r10T\ge r^{10}T≥r10 and d≥100(r+1)2T2d\ge100(r+1)^2T^2d≥100(r+1)2T2. Then a uniformly random set I∈([d]r+1)[T]\mathcal I\in\binom{[d]}{r+1}^{[T]}I∈(r+1[d]​)[T] of TTT pairwise disjoint colour sets of size r+1r+1r+1 in [d]={0,…,d}[d]=\{0,\dots,d\}[d]={0,…,d} is nice with probability at least 0.90.90.9:

#{I∈([d]r+1)[T]:I nice} ≥ 0.9⋅#([d]r+1)[T].\#\{\mathcal I\in\tbinom{[d]}{r+1}^{[T]}:\mathcal I\text{ nice}\}\ \ge\ 0.9\cdot\#\tbinom{[d]}{r+1}^{[T]}.#{I∈(r+1[d]​)[T]:I nice} ≥ 0.9⋅#(r+1[d]​)[T].

Differences from the source:

  • encoding: with probability ≥ 0.9 over a uniformly random I ∈ ([d] choose r+1)^[T] → 0.9 · card (disjointColorSets d r T) ≤ niceCount d r T; reason: the uniform probability of a finite set as a ratio of cardinalities
  • reading: condition (e) of Definition 3.6: 'for every pair of J-bins B, B′' → IsNice quantifies (e) over every pair (ℓ, ℓ′) of nonempty bins, B = B′ included; empty bins are omitted, as the definition says; reason: a pair is an arbitrary pair, as the proof of Lemma 3.7 counts it (p. 34: 'This count allows the two bins to belong to arbitrary color sets, as in the definition'); reading it as two different bins would weaken Lemma 3.7
  • reading: niceness evaluated in each J's own cyclic path order with a chosen j₀ ∈ J → IsNice with j₀ = min J (base J); reason: Definition 3.6 states the choice of j₀ does not matter
Preamble
import Mathlib
import Definitions.Def_PolySwap_KMS_Complex
import Definitions.Def_PolySwap_KMS_Dehn
import Definitions.Def_PolySwap_KMS_KMSComplex
Formal statement
namespace PolySwap.KMS

/-- **Lemma 3.7** (colour sampling), p. 24. Let `r ≥ 10⁴`, `T ≥ r¹⁰` and
`d ≥ 100(r + 1)²T²`. Then a uniformly random set `I ∈ ([d] choose r+1)^[T]` of `T` disjoint
colour sets is nice with probability `≥ 0.9`. -/
theorem lemma_3_7 (r T d : ℕ) (hr : 10 ^ 4 ≤ r) (hT : r ^ 10 ≤ T)
    (hd : 100 * (r + 1) ^ 2 * T ^ 2 ≤ d) :
    (0.9 : ℝ) * (disjointColorSets d r T).card ≤ niceCount d r T := by sorry

end PolySwap.KMS
Source
Dikstein, Oppenheim, Valentiner-Branth, Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs, STOC 2027 submission (manuscript sha256 b9cb2095…), Lemma 3.7, p. 24 (proof §4, pp. 31–35)
Human review
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

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