Lemma 2.4 — exact limiting rate and half-erasure ambiguity
ProvedExpandingCodes.PolynomialStretch.auxiliary_ratecoding-theoryexpanding-codesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix and the parameter . For the auxiliary code in equation (5), put and . Along the construction as ,
where the are independent uniform variables on . If each coordinate is erased independently with probability , then
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.