Theorem 6.4 (completeness) — for instances in the language
ProvedLatticePrepro.ObliviousPCP.codeDist_le_of_memConsider Construction 6.2 for a query-oblivious PCP with enumerable predicate families (Definition 6.1) with random bits, queries and accepting views, a field , an -linear map and an integer . Let be its code, its targets, and . Suppose that the PCP has perfect completeness for a language : every has a proof that is accepted for every random string. Then for every ,
This is the completeness part of Theorem 6.4. Take a proof that is accepted for every random string, and let be the indicator vector of the accepting views . Then satisfies the constraints (27), so is solvable and is a codeword. The restrictions vanish for , so by the weight formula (29) the vector has weight at most .
Formalization Note. This part needs no hypothesis on , on or on the soundness of the PCP. is CodeFamily.codeDist, the minimum Hamming distance from to a codeword. The Lean names ε, E, g, ρ, q stand for , , , , .
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem
import Definitions.Def_LatticePrepro_Conversions_Codes
import Definitions.Def_LatticePrepro_PCP_Verifier
import Definitions.Def_LatticePrepro_PCP_Code
open LatticePrepro
open LatticePrepro.ObliviousPCP
variable {X : Type} (P : ObliviousPCP X) {F : Type} [Field F] [DecidableEq F] {B : ℕ}theorem LatticePrepro.ObliviousPCP.codeDist_le_of_mem {Lang : Set X} (hc : P.PerfectlyComplete Lang)
(E : (P.Views → F) →ₗ[F] (Fin B → F)) (g : ℕ) {x : X} (hx : x ∈ Lang) :
CodeFamily.codeDist (P.target E g x) (P.code E g) ≤ P.radius B := by sorry