Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Pinsketch recovery: a light vector is determined by its syndrome

Proved
LinearSetReconciliation327.Main.pinsketch_syndrome_recovery

by djwj233 · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

pinsketchset-reconciliationword-ram

Let FFF be a field of characteristic two (a Z2\mathbb{Z}_2Z2​-algebra), let (ι0,…,ιN−1)(\iota_0,\dots,\iota_{N-1})(ι0​,…,ιN−1​) be nonzero elements of FFF that are pairwise distinct, and let ttt be a weight parameter. For a vector x∈Z2Nx \in \mathbb{Z}_2^{N}x∈Z2N​ of Hamming weight at most ttt, the Pinsketch syndrome is

pin⁡ι,t(x)=(∑i: xi=1ιi 2j+1)j=0t−1∈Ft.\operatorname{pin}_{\iota,t}(x) = \Bigl(\sum_{i:\,x_i=1} \iota_i^{\,2j+1}\Bigr)_{j=0}^{t-1} \in F^{t}.pinι,t​(x)=(i:xi​=1∑​ιi2j+1​)j=0t−1​∈Ft.

The theorem asserts that this map is injective on the set of vectors of weight at most ttt: if x,x′∈Z2Nx,x' \in \mathbb{Z}_2^{N}x,x′∈Z2N​ both have Hamming weight at most ttt and pin⁡ι,t(x)=pin⁡ι,t(x′)\operatorname{pin}_{\iota,t}(x)=\operatorname{pin}_{\iota,t}(x')pinι,t​(x)=pinι,t​(x′), then x=x′x=x'x=x′.

Equivalently, a ttt-light vector is fully determined by its ttt odd power sums. This is the recovery (uniqueness) property of the Pinsketch sketch, and it is the fourth conjunct of Proposition 2.1; the decoding program is required to return the light vector whose syndrome it was given, so this uniqueness is what makes "the" answer well defined.

Formalization Note The characteristic-two hypothesis is carried by the typeclass assumption [Algebra (ZMod 2) F]; pin is the power-sum map above and x i = 1 is membership in the support of a Z2\mathbb{Z}_2Z2​-vector.

Preamble
import Definitions.Def_LinearSetReconciliation327_Main_Basic
import Definitions.Def_LinearSetReconciliation327_Main_Pinsketch
import Definitions.Def_LinearSetReconciliation327_Main_DecoderModel
import Definitions.Def_LinearSetReconciliation327_Main_DecoderTables
import Definitions.Def_LinearSetReconciliation327_Main_DecoderProgram

set_option autoImplicit false

open Finset
Formal statement
theorem LinearSetReconciliation327.Main.pinsketch_syndrome_recovery
    {F : Type} [Field F] [Algebra (ZMod 2) F] {N t : ℕ} (ι : ℕ → F)
    (h0 : ∀ v < N, ι v ≠ 0) (hinj : Set.InjOn ι (Set.Iio N)) {x x' : Fin N → ZMod 2}
    (hx : (univ.filter fun i => x i = 1).card ≤ t)
    (hx' : (univ.filter fun i => x' i = 1).card ≤ t)
    (hp : pin ι t x = pin ι t x') : x = x' := by sorry
Source
arXiv:2611.11409, Section 2.2, Proposition 2.1 (recovery conjunct), and Dodis, Ostrovsky, Reyzin, Smith, Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data, SIAM J. Comput. 38(1), 2008, Section 6.3

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