Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2.4 — exact limiting rate and half-erasure ambiguity

Proved
ExpandingCodes.PolynomialStretch.auxiliary_rate

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

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

Fix 0<ε<1/20<\varepsilon<1/20<ε<1/2 and the parameter d=2⌈512ε−2⌉d=2\lceil512\varepsilon^{-2}\rceild=2⌈512ε−2⌉. For the auxiliary code BBB in equation (5), put r=dim⁡FqBr=\dim_{F_q}Br=dimFq​​B and m=qdm=q^dm=qd. Along the construction as n→∞n\to\inftyn→∞,

rm⟶ρd=Pr⁡ ⁣[∑j=1dXj≤(d−3)/2],12−ε8≤ρd<12,\frac r m\longrightarrow\rho_d=\Pr\!\left[\sum_{j=1}^dX_j\le(d-3)/2\right],\qquad \frac12-\frac\varepsilon8\le\rho_d<\frac12,mr​⟶ρd​=Pr[j=1∑d​Xj​≤(d−3)/2],21​−8ε​≤ρd​<21​,

where the XjX_jXj​ are independent uniform variables on [0,1][0,1][0,1]. If each coordinate is erased independently with probability 1/21/21/2, then

Edim⁡FqBEm⟶0.\frac{\mathbb E\dim_{F_q}B_E}{m}\longrightarrow0.mEdimFq​​BE​​⟶0.

These assertions hold for every compatible family of finite fields and public row orders. The rate is computed from the actual evaluation subspace, not fixed by definition to one half.

This result supplies both the exact rate bound and the erasure-dimension estimate needed by the distinguisher.

Differences from the source:

  • encoding: independent continuous uniforms and asymptotic ratios for the code B → Lebesgue volume of a measurable subset of the unit cube and limits along the construction n→∞; reason: the unit cube has product-uniform probability one, and the construction field sizes tend to infinity
  • encoding: r=dim B and E dim B_E → Mathlib finrank of the generalized evaluation span and a finite Bernoulli-weighted sum; reason: these compute the same dimensions and expectation without an integrability premise
Preamble
import Mathlib
import Definitions.Def_ExpandingCodes_PolynomialStretch_ErasureModel
set_option autoImplicit false
open scoped Classical
Formal statement
namespace ExpandingCodes.PolynomialStretch

open Filter
/-- Lemma 2.4: the exact continuous-uniform limiting rate and the half-erasure limit. -/
theorem auxiliary_rate (ε : ℝ) (hε : 0 < ε ∧ ε < 1 / 2)
    (g : ∀ n, Geometry (dimension ε) n) :
    1 / 2 - ε / 8 ≤ limitingRate (dimension ε) ∧
    limitingRate (dimension ε) < 1 / 2 ∧
    Tendsto (fun n => (Module.finrank (g n).F (auxiliaryCode (g n)) : ℝ) /
      rowCount (dimension ε) n) atTop (nhds (limitingRate (dimension ε))) ∧
    Tendsto (fun n => erasureExpectation (auxiliaryCode (g n)) (1 / 2) /
      rowCount (dimension ε) n) atTop (nhds 0) := by sorry

end ExpandingCodes.PolynomialStretch
Source
Isaac M Hair, Amit Sahai, Expanding Codes with Polynomial Stretch, STOC 2027 submission #824 (October 2026), printed p. 10 / PDF p. 11, Lemma 2.4.
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