Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.1 — sparse expanding codes with polynomial stretch and arbitrary near-half errors

Proved
ExpandingCodes.PolynomialStretch.expanding_codes

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

coding-theoryexpanding-codesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

There is an absolute constant C>0C>0C>0 such that for every real 0<ε<1/20<\varepsilon<1/20<ε<1/2 there are an integer k≤Cε−6k\le C\varepsilon^{-6}k≤Cε−6, a deterministic row-count function m(n)m(n)m(n), a randomized matrix sampler and a deterministic test DDD. For every sufficiently large nnn,

n<m(n)<nk,m(n)=nOε(1).n<m(n)<n^k,\qquad m(n)=n^{O_\varepsilon(1)}.n<m(n)<nk,m(n)=nOε​(1).

The sampler runs in poly⁡ε(n)\operatorname{poly}_\varepsilon(n)polyε​(n) time on every unbiased random tape, with exactly the stated output law on binary matrices G∈F2m(n)×nG\in\mathbb F_2^{m(n)\times n}G∈F2m(n)×n​. Every output has row weight exactly kkk, and

Pr⁡[G is (1−ε,k,n1−ε)-expanding]≥1−n−1/ε.\Pr[G\text{ is }(1-\varepsilon,k,n^{1-\varepsilon})\text{-expanding}]\ge1-n^{-1/\varepsilon}.Pr[G is (1−ε,k,n1−ε)-expanding]≥1−n−1/ε.

The test runs in deterministic poly⁡ε(m,n)\operatorname{poly}_\varepsilon(m,n)polyε​(m,n) time. For every sampler output, every binary message xxx and every binary error eee with ∣supp⁡(e)∣≤(1/2−ε)m|\operatorname{supp}(e)|\le(1/2-\varepsilon)m∣supp(e)∣≤(1/2−ε)m,

D(Gx+e)=1,Pr⁡[D(Um)=1]≤exp⁡(−ε2m/128).D(Gx+e)=1,\qquad\Pr[D(U_m)=1]\le\exp(-\varepsilon^2m/128).D(Gx+e)=1,Pr[D(Um​)=1]≤exp(−ε2m/128).

The error may depend arbitrarily on the message and on the sampled matrix. Constants, programs and the eventual size threshold are fixed before nnn, the matrix and its random bits; kkk does not depend on nnn.

This is the headline existence theorem. The construction milestone supplies its witnesses without restricting ε\varepsilonε to rational values or assuming successful expansion.

Differences from the source:

  • encoding: randomized polynomial-time sampler and deterministic polynomial-time test → fixed finite transition tables, a polynomial-length unbiased tape, exact output law, and worst-case transition bounds; reason: this spells out the algorithmic existence clauses with no advice, runtime annotation or correctness assumption
  • encoding: m=n^{O_ε(1)}>n depending only on n,ε and m<n^k → a deterministic function m with n<m(n)<n^k eventually; reason: k is fixed before n, so the same displayed bound already gives polynomial growth
  • encoding: exp(−Ω_ε(m)) → exp(−ε²m/128) eventually; reason: the construction uses a fixed rational θ between ε/2 and ε; the source proof rate θ²/32 gives the displayed ε-rate
Preamble
import Mathlib
import Definitions.Def_ExpandingCodes_PolynomialStretch_OperationalFamily
set_option autoImplicit false
open scoped Classical
Formal statement
namespace ExpandingCodes.PolynomialStretch

/-- Theorem 1.1: constant arity, polynomial stretch and runtime, and the unconditional
near-half arbitrary-error test. The absolute arity constant precedes ε. -/
theorem expanding_codes :
    ∃ C : ℝ, 0 < C ∧ ∀ ε : ℝ, 0 < ε → ε < 1 / 2 →
      ∃ (k : ℕ) (m : ℕ → ℕ) (P : ∀ n, PMF (Generator (m n) n))
        (D : ∀ n, Word (m n) → Bool),
        (k : ℝ) ≤ C * ε⁻¹ ^ 6 ∧ EfficientFamily ε k m P D := by sorry

end ExpandingCodes.PolynomialStretch
Source
Isaac M Hair, Amit Sahai, Expanding Codes with Polynomial Stretch, STOC 2027 submission #824 (October 2026), printed p. 2 / PDF p. 3, Theorem 1.1.
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 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