Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.13 — every vertex link of a nice FIXF^{\mathcal I}XFIX has h1≥β2h^1\ge\beta_2h1≥β2​ and H1=1H^1=1H1=1

Proved
PolySwap.KMS.proposition_3_13

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,d∈Nr,d\in\mathbb Nr,d∈N, d≥3d\ge3d≥3, and T∈NT\in\mathbb NT∈N, T≥4T\ge4T≥4. There exist β2>0\beta_2>0β2​>0 and q0∈Nq_0\in\mathbb Nq0​∈N such that for all prime powers q=pm≥q0q=p^m\ge q_0q=pm≥q0​, all groups Λ\LambdaΛ without non-trivial elements of order ppp, all irreducible polynomials f∈Fq[t]f\in\mathbb F_q[t]f∈Fq​[t] of degree ≥2\ge2≥2 and all nice sets of TTT disjoint colours I∈([d]r+1)[T]\mathcal I\in\binom{[d]}{r+1}^{[T]}I∈(r+1[d]​)[T], every vertex v∈FIX(0)v\in F^{\mathcal I}X(0)v∈FIX(0) satisfies

h1(FIXv,Λ)≥β2andH1(FIXv,Λ)=1,h^1\big(F^{\mathcal I}X_v,\Lambda\big)\ge\beta_2\quad\text{and}\quad H^1\big(F^{\mathcal I}X_v,\Lambda\big)=1,h1(FIXv​,Λ)≥β2​andH1(FIXv​,Λ)=1,

where X=X(Ad,Fq,f)X=X(A_d,\mathbb F_q,f)X=X(Ad​,Fq​,f).

Differences from the source:

  • encoding: r ∈ ℕ (the paper's ℕ excludes 0: it writes ℕ₀ for {0, 1, …}, p. 9; Definitions 2.11 and 2.14 assume 1 ≤ r) → hypothesis 1 ≤ r; reason: the paper's standing convention made explicit
  • encoding: a prime power q = p^m and the field F_q → a finite field F (Fintype F) with q = Fintype.card F and p = ringChar F; reason: every finite field has prime-power order q and prime characteristic p; same instances
  • encoding: groups Λ without non-trivial elements of order p → any group Λ (Type*) with ∀ g, g ^ ringChar F = 1 → g = 1; reason: p is prime, so g ≠ 1 with g^p = 1 has order exactly p; same groups
  • encoding: X(A_d, F_q, f) = CC(SL_{d+1}(F_q[t]/(f)); (π_f(U_{[d]∖{i}}))_{i∈[d]}) with the uniform top-level distribution → kmsX d F f: cosetComplex over SL (Fin (d+1)) (AdjoinRoot f) of Hf d F f i = (U d F ([d]∖{i})).map (SpecialLinearGroup.map (AdjoinRoot.mk f)), vertices ⟨i, gH^f_i⟩ : Σ i, G ⧸ H^f_i, colour i; reason: Lean convention (0-based matrix indices, F_q[t]/(f) as AdjoinRoot f); the same complex and weights
  • encoding: h¹(Y, Λ) ≥ β with h¹ the minimum ratio ‖d₁ϕ‖ / min_{ψ∈Z¹} dist(ϕ, ψ) over ϕ ∉ Z¹ (Definition 2.8) → HOneGe: every 1-cochain ϕ has a 1-cocycle ψ with β · dist(ϕ, ψ) ≤ ‖d₁ϕ‖; reason: equivalent on a finite complex with positive Garland weights: the minimum distance to Z¹ is attained and positive for ϕ ∉ Z¹, and ϕ ∈ Z¹ takes ψ = ϕ
  • encoding: H¹(Y, Λ) = 1 (every orbit of a cocycle is that of the trivial cocycle, equivalently B¹ = Z¹) → H1Trivial: every 1-cocycle equals d₀g on every ordered edge for some 0-cochain g; reason: the paper's equivalence (p. 12); cochains are total functions and only their values on the complex count
  • 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
  • encoding: β₂ > 0 and q₀ depending on (r, d, T), for all fields, groups and polynomials → ∃ β₂ > 0, ∃ q₀ : ℕ after r, d, T and before F : Type u, Λ : Type v; reason: quantifier order as printed; Lean fixes one universe for F and one for Λ
Preamble
import Mathlib
import Definitions.Def_PolySwap_KMS_Complex
import Definitions.Def_PolySwap_KMS_Cohomology
import Definitions.Def_PolySwap_KMS_Dehn
import Definitions.Def_PolySwap_KMS_KMSComplex

open Polynomial

universe u v
Formal statement
namespace PolySwap.KMS

/-- **Proposition 3.13**, p. 26. Let `r, d ∈ ℕ`, `d ≥ 3`, `T ≥ 4`. There exist `β₂ > 0` and
`q₀ ∈ ℕ` such that for all prime powers `q = p^m ≥ q₀`, all groups `Λ` without non-trivial
elements of order `p`, all irreducible `f ∈ F_q[t]` of degree `≥ 2` and all nice sets `I` of `T`
disjoint colour sets, every vertex `v` of `F^I X`, `X = X(A_d, F_q, f)`, has
`h¹((F^I X)_v, Λ) ≥ β₂` and `H¹((F^I X)_v, Λ) = 1`. -/
theorem proposition_3_13 (r d T : ℕ) (hr : 1 ≤ r) (hd : 3 ≤ d) (hT : 4 ≤ T) :
    ∃ β₂ : ℝ, 0 < β₂ ∧ ∃ q₀ : ℕ, ∀ (F : Type u) [Field F] [Fintype F], q₀ ≤ Fintype.card F →
      ∀ (Λ : Type v) [Group Λ], (∀ g : Λ, g ^ ringChar F = 1 → g = 1) →
      ∀ f : F[X], Irreducible f → 2 ≤ f.natDegree →
      ∀ I ∈ disjointColorSets d r T, IsNice d I →
      ∀ v ∈ (kmsFI d F f I).vertices,
        ((kmsFI d F f I).link {v}).HOneGe Λ β₂ ∧ ((kmsFI d F f I).link {v}).H1Trivial Λ := 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…), Proposition 3.13, p. 26
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