Theorem 1.1 — sparse expanding codes with polynomial stretch and arbitrary near-half errors
ProvedExpandingCodes.PolynomialStretch.expanding_codesThere is an absolute constant such that for every real there are an integer , a deterministic row-count function , a randomized matrix sampler and a deterministic test . For every sufficiently large ,
The sampler runs in time on every unbiased random tape, with exactly the stated output law on binary matrices . Every output has row weight exactly , and
The test runs in deterministic time. For every sampler output, every binary message and every binary error with ,
The error may depend arbitrarily on the message and on the sampled matrix. Constants, programs and the eventual size threshold are fixed before , the matrix and its random bits; does not depend on .
This is the headline existence theorem. The construction milestone supplies its witnesses without restricting 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
import Mathlib import Definitions.Def_ExpandingCodes_PolynomialStretch_OperationalFamily set_option autoImplicit false open scoped Classical
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.