Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Explicit padded constant-loss extractor for finite flat sources

Proved
TimeSpaceMA.constantLossFlatExtractor

by bersubs · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryextractorspseudorandomness

Fix an error 0<ε≤1/40<\varepsilon\le 1/40<ε≤1/4. There are fixed constants A>0A>0A>0 and Δ\DeltaΔ and one deterministic polynomial-time evaluator. For every n≥1n\ge1n≥1, threshold 0≤k≤n0\le k\le n0≤k≤n, and seed width t≥A(size⁡(n)+size⁡(k)4)t\ge A(\operatorname{size}(n)+\operatorname{size}(k)^4)t≥A(size(n)+size(k)4) with Δ≤k+t\Delta\le k+tΔ≤k+t, the evaluator maps an nnn-bit input and a uniform ttt-bit seed to k+t−Δk+t-\Deltak+t−Δ bits. Here size⁡\operatorname{size}size is binary length. Its output when the input is uniform on any set of at least 2k2^k2k points has statistical distance at most ε\varepsilonε from uniform.

This is the flat-source specialization of the constant-entropy-loss extractor of Corollary 5.8(2), with the seed width supplied as a parameter. Independent extra seed bits can be carried into the output to preserve the error and realize the specified width. The evaluator runs in polynomial time in the encoded query, which includes the two widths in unary.

Preamble
import Definitions.Def_TimeSpaceMA_TUZExtractor
Formal statement
namespace TimeSpaceMA

open Turing.MultiTapeTM

/-- Corollary 5.8(2) of TUZ, with the seed padded to a supplied width and the
finite statistical-distance property restricted to flat sources. -/
theorem constantLossFlatExtractor (ε : ℝ) (hε : 0 < ε) (hε' : ε ≤ 1/4) :
    ∃ (A Δ : ℕ) (extract : ExtractorInput → ℕ),
      0 < A ∧ ComputableInPolyTime extract encExtractorInput encNat ∧
      ∀ n k t : ℕ, 1 ≤ n → k ≤ n → A*(n.size+k.size^4) ≤ t → Δ ≤ k+t →
        ∀ S : Finset (Fin (2^n)), 2^k ≤ S.card →
          FlatExtractorEvents (extractorEdge extract Δ n k t) S ε := by sorry

end TimeSpaceMA
Source
Ta-Shma, Umans and Zuckerman, Lossless Condensers, Unbalanced Expanders, and Extractors, Combinatorica 27 (2007), Corollary 5.8(2), PDF p. 22, https://www.cs.tau.ac.il/~amnon/Papers/TUZ.C07.pdf

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