Packed evaluator for the folded Reed–Solomon map
DefinitionTimeSpaceMA_GUVFoldedEvaluatorcomplexity-theorycondensersfinite-fields
The interface fixes the input and output packing for the folded Reed–Solomon map. Its correctness condition relates a uniformly polynomial-time evaluator to polynomial evaluation over a binary field and its quadratic extension, using a primitive element of the smaller field. It imposes no expansion or statistical-distance requirements.
Definition code
import Definitions.Def_TimeSpaceMA_TUZExtractorComponents
import Mathlib.FieldTheory.Finite.GaloisField
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Tactic.Ring
open scoped BigOperators
namespace TimeSpaceMA.GUV
open Polynomial Turing.MultiTapeTM
def halfSeed (a n : ℕ) : ℕ := a*n.size
def symbols (c k : ℕ) : ℕ := (k+c-1)/c
theorem symbols_width {c k : ℕ} : 2*c*(symbols c k+1) ≤ 2*(k+2*c) := by
have h := Nat.mul_div_le (k+c-1) c
change c * symbols c k ≤ _ at h
rw [Nat.mul_add, Nat.mul_one, Nat.mul_assoc]
rw [← Nat.mul_add]
exact Nat.mul_le_mul_left 2 (by omega)
noncomputable def vectorPoly {K : Type} [Field K] {n : ℕ} (a : Fin n → K) : K[X] :=
∑ i : Fin n, monomial i.val (a i)
variable {F : Type*} [Field F] in
noncomputable def fold (z : F) (i : ℕ) (f : F[X]) : F[X] :=
f.comp (C (z ^ i) * X)
noncomputable def inputCode {K : Type} {c n : ℕ} (basis : Fin (2^c) ≃ K)
(hc : 0 < c) (x : Fin (2^n)) (j : Fin n) : K :=
basis ⟨x.val / 2^j.val % 2, (Nat.mod_lt _ (by decide : 0 < 2)).trans_le
(Nat.le_pow hc : 2 ≤ 2^c)⟩
noncomputable def outputCode {F : Type} {c k : ℕ} (basis : Fin (2^(2*c)) ≃ F) :
(F × (Fin (symbols c k) → F)) ↪ Fin (2^(2*(k+2*c))) :=
((basis.symm.prodCongr ((Equiv.piCongrRight (fun _ : Fin (symbols c k) => basis.symm)).trans
finFunctionFinEquiv)).trans (finProdFinEquiv.trans (finCongr (by rw [← pow_succ',
← pow_mul])))).toEmbedding.trans (Fin.castLEEmb
(Nat.pow_le_pow_right (by decide) symbols_width))
/-- An arithmetic implementation of the folded Reed–Solomon evaluator. The chosen
field labels may be any bijective representations. The contract compares exact
numeric outputs, and requires no expansion or probability hypothesis. -/
structure FoldedEvaluator (a : ℕ) (ha : 0 < a) (cond : ExtractorInput → ℕ) where
native : ComputableInPolyTime cond encExtractorInput encNat
K : ℕ → Type
F : ℕ → Type
fieldK (n : ℕ) : Field (K n)
fieldF (n : ℕ) : Field (F n)
charF (n : ℕ) : CharP (F n) 2
codeK (n : ℕ) : Fin (2 ^ halfSeed a n) ≃ K n
codeF (n : ℕ) : Fin (2 ^ (2 * halfSeed a n)) ≃ F n
embed (n : ℕ) : K n →+* F n
primitive (n : ℕ) : K n
primitive_order (n : ℕ) (hn : 1 ≤ n) : orderOf (primitive n) = 2^halfSeed a n - 1
correct (n k : ℕ) (hn : 1 ≤ n) (hk : k ≤ n)
(x : Fin (2^n)) (y : Fin (2^(2*halfSeed a n))) :
cond (n,k,2*halfSeed a n,x.val,y.val) =
(outputCode (k := k) (codeF n) (codeF n y, fun i =>
(fold (embed n (primitive n)) i.val ((vectorPoly (inputCode (codeK n) (show 0 < halfSeed a n from Nat.mul_pos ha (Nat.size_pos.mpr hn)) x)).map (embed n))).eval
(codeF n y))).val
end TimeSpaceMA.GUV