Pinsketch recovery: a light vector is determined by its syndrome
ProvedLinearSetReconciliation327.Main.pinsketch_syndrome_recoveryLet be a field of characteristic two (a -algebra), let be nonzero elements of that are pairwise distinct, and let be a weight parameter. For a vector of Hamming weight at most , the Pinsketch syndrome is
The theorem asserts that this map is injective on the set of vectors of weight at most : if both have Hamming weight at most and , then .
Equivalently, a -light vector is fully determined by its 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 -vector.
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
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