Theorem 6.4 (size) — the accepting-view code has block length
ProvedLatticePrepro.ObliviousPCP.card_coordcoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
For the accepting-view code of Construction 6.2, built from a query-oblivious PCP with alphabet , random bits and queries, an encoding map into and an integer , the block length is
Here is the number of rows of and is the number of padding coordinates.
This is the block length stated in Theorem 6.4.
Formalization Note. The statement computes the cardinality of the coordinate type P.Coord B ⊕ Fin (g * P.radius B + 1) of the code, where P.Coord B is and P.radius B is . It involves neither the field nor the encoding map. The Lean names g, ρ, 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
import Definitions.Def_LatticePrepro_PCP_Code
open LatticePrepro
open LatticePrepro.ObliviousPCP
variable {X : Type} (P : ObliviousPCP X) (F : Type) [Field F]
variable {F} {B : ℕ}Formal statement
theorem LatticePrepro.ObliviousPCP.card_coord (B g : ℕ) :
Fintype.card (P.Coord B ⊕ Fin (g * P.radius B + 1)) =
(Fintype.card P.Alphabet + g) * P.radius B + 1 := 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), Theorem 6.4 (\label{thm:pcp-reduction}), size, with step 4 of Construction 6.2 (\label{con:pcp-reduction}); Lean: LatticePrepro/PCP/Code.lean, LatticePrepro.ObliviousPCP.card_coord