Theorem 6.4 (soundness) — for instances outside the language
ProvedLatticePrepro.ObliviousPCP.lt_codeDist_of_not_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 soundness error for a language : for every instance , every proof is accepted for at most random strings;
- is injective, and every nonzero vector of the code has Hamming weight at least , for a real number ;
- , which is condition (28).
Then for every instance ,
This is the soundness part of Theorem 6.4. If has no solution, then and every codeword vanishes on the last coordinates. Otherwise, by (30), the distance from to is the least weight of over the solutions of , and every solution has weight more than .
Formalization Note. The hypotheses are weaker than in the paper: and are not assumed, is only a lower bound on the relative distance of the code , and need not be finite. 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.lt_codeDist_of_not_mem {Lang : Set X} {ε δ : ℝ} (hs : P.SoundnessError Lang ε)
(hε : 0 < ε) {E : (P.Views → F) →ₗ[F] (Fin B → F)} (hE : Function.Injective E)
(hδ : ∀ c ∈ LinearMap.range E, c ≠ 0 → δ * B ≤ hammingNorm c) {g : ℕ}
(hg : (g : ℝ) < δ * ε ^ (-(1 : ℝ) / P.q)) {x : X} (hx : x ∉ Lang) :
g * P.radius B < CodeFamily.codeDist (P.target E g x) (P.code E g) := by sorry