Pinsketch decoder: the decoding conjunct of Proposition 2.1
ProvedLinearSetReconciliation327.Main.pinsketch_decoder_conjunctThis is the third conjunct of Proposition 2.1: the explicit decoder exists and is polynomial-time.
For every , every , every field of characteristic two, every with and every basis of over with coordinates, and every injective sequence of nonzero elements of , there are a word width and a field-data table det such that:
WidthOK W N 8 wholds and words fit in memory cells;- for every packed syndrome , the word-RAM program
pinsketchDecoderProgram, started fromdecoderStart W y [], halts within
steps in a state satisfying decoderPost, i.e. it outputs a -light vector with syndrome when one exists, and rejects only when none exists.
This is the whole decoder guarantee of Proposition 2.1, obtained by composing the four stage contracts (read, key solver, root search, verifier) and the glue lemmas that sequence them. It is the node any later result about the Pinsketch decoder can cite.
Formalization Note pinsketchDecoderProgram is a concrete Program (a published definition), not an existentially quantified object; WidthOK and wordsOf are the word-RAM width/space predicates, and the time bound is the paper's with the explicit constant .
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 import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_syndrome_recovery import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_decoder_read import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_decoder_key_solver import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_decoder_root_search import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_decoder_verifier set_option autoImplicit false open Finset
theorem LinearSetReconciliation327.Main.pinsketch_decoder_conjunct
{F : Type} [Field F] [Algebra (ZMod 2) F] {N t w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F)
(hN : 1 ≤ N) (htN : t ≤ N) (h0 : ∀ i < N, ι i ≠ 0) (hinj : Set.InjOn ι (Set.Iio N)) :
∃ (W : ℕ) (det : ℕ → ℕ), WidthOK W N 8 (w : ℝ) ∧ wordsOf W (t * w) ≤ 2 ^ W ∧
∀ y : Fin (t * w) → ZMod 2, ∃ s',
HaltsWithin pinsketchDecoderProgram (detEnv W det) (20000 * ((t : ℝ) + w + 1) ^ 6)
(decoderStart W y []) s' ∧ decoderPost (N := N) b ι y s' := by sorry