Theorem 6.4 (soundness, main step) — every solution of has weight more than
ProvedLatticePrepro.ObliviousPCP.lt_hammingNorm_stackMap_of_solutionConsider 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 and every solution of , the Hamming weight of satisfies
This is the main step of the soundness proof of Theorem 6.4. A solution defines the lists . By the constraints (27), for every random string some accepting view has a nonzero coefficient, and all its answers lie in the lists. A proof whose entries are independent and uniform in the lists is accepted for with probability at least , so soundness gives (31), and the average list size is at least . By (29) every symbol of a list contributes weight at least in each copy of the block of , which gives .
Formalization Note. The random proof is replaced by a count over all proofs with entries in the lists. 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. The exponent is a real power, ε ^ (-(1 : ℝ) / q). 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_hammingNorm_stackMap_of_solution {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) {v : P.Views → F}
(hv : P.constraintMap F v = P.constraintRhs F x) :
g * P.radius B < hammingNorm (P.stackMap E v) := by sorry