Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.2 — a binary word of weight at most (δ−1)/2(\delta-1)/2(δ−1)/2 is determined by its BCH syndrome

Proved
FuzzyExtractors.EditSketch.lemma_6_2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

bch-codesdecodingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1syndrome

Let KKK be a finite field of characteristic 222 and δ≥0\delta \ge 0δ≥0. Let M,M′⊆K∗M, M' \subseteq K^*M,M′⊆K∗ be the supports of two binary words of weight at most (δ−1)/2(\delta - 1)/2(δ−1)/2. If their syndromes with respect to the binary BCH code of designed distance δ\deltaδ agree, i.e.

∑x∈Mxi=∑x∈M′xifor i=1,…,δ−1,\sum_{x \in M} x^i = \sum_{x \in M'} x^i \qquad \text{for } i = 1, \dots, \delta - 1,x∈M∑​xi=x∈M′∑​xifor i=1,…,δ−1,

then M=M′M = M'M=M′.

This is the information-theoretic content of the second bullet of Lemma 6.2 (equivalently Lemma E.1(2)): supp(x)\mathrm{supp}(x)supp(x) can be computed from syn(x)\mathrm{syn}(x)syn(x) when xxx has weight at most (δ−1)/2(\delta - 1)/2(δ−1)/2. PinSketch's recovery procedure (Construction 6, step 3) depends on it.

Formalization Note. Both running-time claims of Lemma 6.2 are dropped, since Mathlib has no complexity substrate. The first bullet (computing syn(x)\mathrm{syn}(x)syn(x) from supp(x)\mathrm{supp}(x)supp(x)) is pure computation and has no other content, so it is not stated. The second bullet is stated as injectivity of the syndrome map on light words, which is exactly the existence of a decoder. Only the binary case is stated; the qqq-ary generality of Lemma E.1 is not formalized. The BCH code of length n=2μ−1n = 2^\mu - 1n=2μ−1 is the primitive one, indexed by K∗K^*K∗.

Preamble
import Mathlib
import Definitions.Def_FuzzyExtractors_EditSketch_Basic
Formal statement
namespace FuzzyExtractors.EditSketch

theorem lemma_6_2 {K : Type} [Field K] [Fintype K] [DecidableEq K] [CharP K 2]
    (δ : ℕ) (M M' : Finset Kˣ) (hM : M.card ≤ (δ - 1) / 2) (hM' : M'.card ≤ (δ - 1) / 2)
    (hsyn : ∀ i : ℕ, 1 ≤ i → i ≤ δ - 1 → syn i M = syn i M') :
    M = M' := by sorry

end FuzzyExtractors.EditSketch
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Lemma 6.2 (second bullet), p. 23; Lemma E.1(2), p. 43
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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