Theorem 6.4 (size) — the number of accepting views is at most
ProvedLatticePrepro.ObliviousPCP.card_views_lecoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Consider a query-oblivious PCP as in Definition 6.1, with alphabet , random bits, queries and predicate families , and let be an integer with for every random string . Then the total number of accepting views satisfies
This is the bound on in the proof of Theorem 6.4 (size and time). It holds because for every , and it bounds the number of variables of the accepting-view code of Construction 6.2.
Formalization Note. The paper takes ; the Lean statement allows any upper bound K. The number of views is Fintype.card P.Views, and the Lean field names ρ, q stand for , .
Preamble
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
open LatticePrepro
open LatticePrepro.ObliviousPCP
variable {X : Type} (P : ObliviousPCP X)Formal statement
theorem LatticePrepro.ObliviousPCP.card_views_le {K : ℕ} (hK : ∀ r, Fintype.card (P.Pred r) ≤ K) :
Fintype.card P.Views ≤ 2 ^ P.ρ * K * Fintype.card P.Alphabet ^ P.q := by sorrySource
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634), proof of Theorem 6.4 (\label{thm:pcp-reduction}), size and time; Lean: LatticePrepro/PCP/Verifier.lean, LatticePrepro.ObliviousPCP.card_views_le