Lemma 6.2 — a binary word of weight at most is determined by its BCH syndrome
ProvedFuzzyExtractors.EditSketch.lemma_6_2Let be a finite field of characteristic and . Let be the supports of two binary words of weight at most . If their syndromes with respect to the binary BCH code of designed distance agree, i.e.
then .
This is the information-theoretic content of the second bullet of Lemma 6.2 (equivalently Lemma E.1(2)): can be computed from when has weight at most . 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 from ) 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 -ary generality of Lemma E.1 is not formalized. The BCH code of length is the primitive one, indexed by .
import Mathlib import Definitions.Def_FuzzyExtractors_EditSketch_Basic
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.