Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Outputs of Theorems 4.8 and 5.1: gap reductions, fixed code and lattice gaps, and the explicit exponents

Definition
LatticePrepro_Main

by WizardOfMenlo · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

This bundle defines the objects produced by the main theorems. Throughout, ppp is a prime and VVV is a quadratic verifier over Fp\mathbb{F}_pFp​ with instance length nnn, SSS assignment coordinates and language L(V)⊆{0,1}nL(V)\subseteq\{0,1\}^nL(V)⊆{0,1}n.

  1. Gap reductions (GapReduction p V g m, the output of Theorem 4.8 for integers g,mg,mg,m). A linear system family L\mathcal{L}L over Fp\mathbb{F}_pFp​ (a fixed linear map AAA, a right-hand side bxb_xbx​ for every x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n, and NcolN_{\mathrm{col}}Ncol​ columns partitioned into DDD blocks of size bbb) such that
    • L\mathcal{L}L is a gap reduction from L(V)L(V)L(V) with gap ggg: for x∈L(V)x\in L(V)x∈L(V) the system Av=bxAv=b_xAv=bx​ has a binary solution with at most one nonzero entry per block, and for x∉L(V)x\notin L(V)x∈/L(V) every solution has Hamming weight >g⋅D>g\cdot D>g⋅D;
    • g<bg<bg<b, and b=peb=p^eb=pe for some e≥0e\ge0e≥0;
    • D≥1D\ge1D≥1;
    • Ncol m≤(8p4m(S+1))(m+7)m⋅gm+1N_{\mathrm{col}}^{\,m}\le\bigl(8p^4m(S+1)\bigr)^{(m+7)m}\cdot g^{m+1}Ncolm​≤(8p4m(S+1))(m+7)m⋅gm+1.
  2. Explicit exponents. For a real δ\deltaδ and natural numbers p,mp,mp,m:
m(δ)=⌈δ1−δ⌉+1,a(p,m)=(8p4m+1)(m+7)m,m(\delta)=\Bigl\lceil\frac{\delta}{1-\delta}\Bigr\rceil+1,\qquad a(p,m)=(8p^4m+1)(m+7)m,m(δ)=⌈1−δδ​⌉+1,a(p,m)=(8p4m+1)(m+7)m, k(p,δ)=⌈6m+am−δ(m+1)⌉+1,C(p,δ)=a+k (m+1)+2,k(p,\delta)=\Bigl\lceil\frac{6m+a}{m-\delta(m+1)}\Bigr\rceil+1,\qquad C(p,\delta)=a+k\,(m+1)+2,k(p,δ)=⌈m−δ(m+1)6m+a​⌉+1,C(p,δ)=a+k(m+1)+2,

where in the last two formulas m=m(δ)m=m(\delta)m=m(δ) and a=a(p,m)a=a(p,m)a=a(p,m) (momentAxes, prefactorExp, gapExp, sizeExp). Theorem 5.1 uses the gap g=(S+1)kg=(S+1)^kg=(S+1)k and the dimension bound (S+1)C(S+1)^C(S+1)C. 3. Fixed code gaps (CodeGap F ε Lang n C, Theorem 5.1 for codes), for a field FFF, a real ε\varepsilonε, a language Lang⊆X\mathrm{Lang}\subseteq XLang⊆X, a size parameter ν∈N\nu\in\mathbb{N}ν∈N (the Lean argument n) and an exponent C∈NC\in\mathbb{N}C∈N. An FFF-linear code C⊆FM\mathcal{C}\subseteq F^MC⊆FM, a target tx∈FMt_x\in F^Mtx​∈FM for every x∈Xx\in Xx∈X, and an integer radius R≥1R\ge1R≥1, with

  • 1≤M≤νC1\le M\le \nu^C1≤M≤νC;
  • x∈Lang⇒dist⁡(tx,C)≤Rx\in\mathrm{Lang}\Rightarrow\operatorname{dist}(t_x,\mathcal{C})\le Rx∈Lang⇒dist(tx​,C)≤R and x∉Lang⇒dist⁡(tx,C)>M1−εRx\notin\mathrm{Lang}\Rightarrow\operatorname{dist}(t_x,\mathcal{C})>M^{1-\varepsilon}Rx∈/Lang⇒dist(tx​,C)>M1−εR, where dist⁡(y,C)=min⁡c∈CdH(y,c)\operatorname{dist}(y,\mathcal{C})=\min_{c\in\mathcal{C}}d_H(y,c)dist(y,C)=minc∈C​dH​(y,c) is the Hamming distance to the code.
  1. Fixed lattice gaps (LatticeGap pn ε Lang n C, Theorem 5.1 for lattices), for a norm exponent 1≤p≤∞1\le p\le\infty1≤p≤∞ with s=min⁡{p,2}s=\min\{p,2\}s=min{p,2}, and Lang,ν,C\mathrm{Lang},\nu,CLang,ν,C as above. A lattice Λ⊆ZM\Lambda\subseteq\mathbb{Z}^MΛ⊆ZM, a target tx∈ZMt_x\in\mathbb{Z}^Mtx​∈ZM for every xxx, an integer radius R≥1R\ge1R≥1 and an integer N≥1N\ge1N≥1, with
    • 1≤M≤νC1\le M\le \nu^C1≤M≤νC and N⋅ZM⊆ΛN\cdot\mathbb{Z}^M\subseteq\LambdaN⋅ZM⊆Λ, so that Λ\LambdaΛ has full rank;
    • x∈Lang⇒dist⁡p(tx,Λ)≤Rx\in\mathrm{Lang}\Rightarrow\operatorname{dist}_p(t_x,\Lambda)\le Rx∈Lang⇒distp​(tx​,Λ)≤R and x∉Lang⇒dist⁡p(tx,Λ)>M1/s−εRx\notin\mathrm{Lang}\Rightarrow\operatorname{dist}_p(t_x,\Lambda)>M^{1/s-\varepsilon}Rx∈/Lang⇒distp​(tx​,Λ)>M1/s−εR, where dist⁡p(t,Λ)=inf⁡v∈Λ∥t−v∥p\operatorname{dist}_p(t,\Lambda)=\inf_{v\in\Lambda}\|t-v\|_pdistp​(t,Λ)=infv∈Λ​∥t−v∥p​.

These structures are the conclusions of exists_gapReduction (Theorem 4.8) and of code_gap, exists_code_gap, lattice_gap, exists_lattice_gap (Theorem 5.1, with ν=S+1\nu=S+1ν=S+1). The exponents implement the parameter choice in the proof of Theorem 5.1, with δ=1−sε\delta=1-s\varepsilonδ=1−sε. The code (resp. lattice) and the radius are fixed; only the target depends on the instance.

Formalization Note The theorems assert Nonempty of these structures. The code distance codeDist is a natural number defined via sInf; the lattice distance latticeDist is a real infimum ⨅ (shown elsewhere to be attained). Ceilings are Nat.ceil; M1−εM^{1-\varepsilon}M1−ε and M1/s−εM^{1/s-\varepsilon}M1/s−ε are real powers (Real.rpow). A norm exponent PNorm is either a real p≥1p\ge1p≥1 or ∞\infty∞, with s=min⁡{p,2}s=\min\{p,2\}s=min{p,2}, resp. s=2s=2s=2. Polynomial-time computability is not formalized. The search test of Lemma 5.2 is not part of these structures: without its running-time bound an abstract test would be satisfied by membership in Lang\mathrm{Lang}Lang itself, so it is stated separately for the paper's concrete tests (CodeFamily.Accepts, LatticeReduction.Accepts).

Definition code
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem
import Definitions.Def_LatticePrepro_Conversions_Codes
import Definitions.Def_LatticePrepro_Conversions_ConstructionA
import Definitions.Def_LatticePrepro_Conversions_Hadamard
import Definitions.Def_LatticePrepro_Conversions_Lattices
import Definitions.Def_LatticePrepro_Lattices_Distance
import Definitions.Def_LatticePrepro_Lattices_Mathlib
import Definitions.Def_LatticePrepro_Moments_Basic
import Definitions.Def_LatticePrepro_Moments_Representation
import Definitions.Def_LatticePrepro_Verifier_Quadratic
import Definitions.Def_LatticePrepro_Reduction_FixedSystem
import Definitions.Def_LatticePrepro_Tables_Digits
import Definitions.Def_LatticePrepro_Tables_FieldSetup
import Definitions.Def_LatticePrepro_Tables_Hankel
import Definitions.Def_LatticePrepro_Tables_Construction
import Definitions.Def_LatticePrepro_Tables_ElementTable
import Definitions.Def_LatticePrepro_Tables_TableSoundness
import Definitions.Def_LatticePrepro_Tables_Explicit

/-!
# Main results

* **Theorem 4.8** (`GapReduction`, `exists_gapReduction`): for every prime `p`, quadratic
  verifier `V` with `S` coordinates, gap `g ≥ 1` and `m ≥ 1`, there is a linear system family
  over `𝔽_p` that is a gap reduction from the language of `V` with gap `g`, with `g < b` and
  `n^m ≤ (8 p^4 m (S+1))^{(m+7) m} · g^{m+1}` columns.
* **Theorem 5.1** (`CodeGap`, `LatticeGap`, `code_gap`, `lattice_gap`, `exists_code_gap`,
  `exists_lattice_gap`): fixed codes over any finite field, and fixed lattices in any `ℓ_p`
  norm, with polynomial dimension `M ≤ (S + 1)^C` and approximation gap `M^{1/s - ε}` measured
  by `dist(t_x, 𝒞)` and `dist_p(t_x, Λ)`. The exponent `C = sizeExp p δ` is explicit
  (`δ = 1 - s ε`).

The polynomial-time computability claims of the paper are not formalized. In particular the
search test of Lemma 5.2 is stated for the concrete tests `CodeFamily.Accepts` and
`LatticeReduction.Accepts` (`Conversions/SearchTest.lean`) rather than as a field of `CodeGap` and
`LatticeGap`: without its running-time bound, an abstract "test" field would be satisfiable by
the membership predicate of `Lang` itself.
-/

namespace LatticePrepro

/-! ### Restricting an encoding tuple to fewer coordinates -/

/-! ### Theorem 4.8 -/

/-- The output of Theorem 4.8 for a verifier `V`, a gap `g` and `m ≥ 1`: a linear system family
`L` over `𝔽_p` that is a gap reduction from `L(V)` with gap `g < b` (`b` a power of `p`), with at
least one block and `n^m ≤ (8 p^4 m (S + 1))^{(m+7) m} · g^{m+1}` columns. -/
structure GapReduction (p : ℕ) [Fact p.Prime] (V : QuadraticVerifier p) (g m : ℕ) where
  /-- The fixed linear system. -/
  L : LinearSystemFamily (ZMod p) (Fin V.n → Bool)
  isGapReduction : L.IsGapReduction V.Language g
  lt_blockSize : g < L.blockSize
  blockSize_eq_pow : ∃ e : ℕ, L.blockSize = p ^ e
  numBlocks_pos : 0 < L.numBlocks
  card_pow_le : (Fintype.card L.ι) ^ m ≤ (8 * p ^ 4 * m * (V.S + 1)) ^ ((m + 7) * m) * g ^ (m + 1)

/-! ### Choice of parameters for Theorem 5.1

For a gap exponent `0 ≤ δ < 1` we choose `m` with `δ (1 + 1/m) < 1`, then the gap `g = (S+1)^k`
with `k` large enough that `64 · n^δ ≤ g`, and the size exponent `C` with `4 n ≤ (S+1)^C`, where
`n^m ≤ (8 p^4 m (S+1))^{(m+7) m} g^{m+1}` is the column bound of Theorem 4.8. All three
constants are explicit functions of `p` and `δ`. -/

/-- The number of moment axes `m = ⌈δ / (1 - δ)⌉ + 1`, so that `δ (m + 1) < m`. -/
noncomputable def momentAxes (δ : ℝ) : ℕ := ⌈δ / (1 - δ)⌉₊ + 1

/-- The exponent `a = (8 p^4 m + 1) (m + 7) m`, with `(8 p^4 m (S+1))^{(m+7) m} ≤ (S+1)^a`. -/
def prefactorExp (p m : ℕ) : ℕ := (8 * p ^ 4 * m + 1) * ((m + 7) * m)

/-- The gap exponent `k`, giving the gap `g = (S+1)^k`. -/
noncomputable def gapExp (p : ℕ) (δ : ℝ) : ℕ :=
  ⌈(6 * momentAxes δ + prefactorExp p (momentAxes δ) : ℝ) /
    (momentAxes δ - δ * (momentAxes δ + 1))⌉₊ + 1

/-- The size exponent `C`, giving `M ≤ (S+1)^C`. -/
noncomputable def sizeExp (p : ℕ) (δ : ℝ) : ℕ :=
  prefactorExp p (momentAxes δ) + gapExp p δ * (momentAxes δ + 1) + 2

/-! ### Theorem 5.1 for codes -/

/-- A fixed code with gap `M^{1 - ε}` for a language `Lang ⊆ X` with size parameter `n` and
exponent `C` (the conclusion of Theorem 5.1 for codes): a code `𝒞 ⊆ F^M` with `1 ≤ M ≤ n^C`,
targets `t_x` and an integer radius `R ≥ 1` such that `x ∈ Lang` implies `dist(t_x, 𝒞) ≤ R` and
`x ∉ Lang` implies `dist(t_x, 𝒞) > M^{1 - ε} · R`. -/
structure CodeGap (F : Type) [Field F] [DecidableEq F] (ε : ℝ) {X : Type} (Lang : Set X)
    (n C : ℕ) where
  /-- The fixed code and the targets. -/
  𝒞 : CodeFamily F X
  /-- The radius. -/
  R : ℕ
  one_le_R : 1 ≤ R
  one_le_card : 1 ≤ Fintype.card 𝒞.M
  card_le : Fintype.card 𝒞.M ≤ n ^ C
  yes : ∀ x ∈ Lang, CodeFamily.codeDist (𝒞.target x) 𝒞.code ≤ R
  no : ∀ x ∉ Lang,
    (Fintype.card 𝒞.M : ℝ) ^ (1 - ε) * R < CodeFamily.codeDist (𝒞.target x) 𝒞.code

/-! ### Theorem 5.1 for lattices -/

/-- A fixed lattice with gap `M^{1/s - ε}` in `ℓ_p` for a language `Lang ⊆ X` with size
parameter `n` and exponent `C` (the conclusion of Theorem 5.1 for lattices): a full-rank lattice
`Λ ⊆ ℤ^M` (containing `N · ℤ^M`) with `1 ≤ M ≤ n^C`, integer targets `t_x` and an integer radius
`R ≥ 1` such that `x ∈ Lang` implies `dist_p(t_x, Λ) ≤ R` and `x ∉ Lang` implies
`dist_p(t_x, Λ) > M^{1/s - ε} · R`. -/
structure LatticeGap (pn : PNorm) (ε : ℝ) {X : Type} (Lang : Set X) (n C : ℕ) where
  /-- The fixed lattice and the targets. -/
  Λ : LatticeFamily X
  /-- The radius. -/
  R : ℕ
  one_le_R : 1 ≤ R
  one_le_card : 1 ≤ Fintype.card Λ.M
  card_le : Fintype.card Λ.M ≤ n ^ C
  /-- The lattice contains `N · ℤ^M`. -/
  N : ℕ
  N_pos : 0 < N
  smul_mem : ∀ v : Λ.M → ℤ, (N : ℤ) • v ∈ Λ.lattice
  yes : ∀ x ∈ Lang, Λ.latticeDist pn x ≤ R
  no : ∀ x ∉ Lang, (Fintype.card Λ.M : ℝ) ^ (1 / pn.s - ε) * R < Λ.latticeDist pn x

end LatticePrepro
Source
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 4.8 (\label{thm:quantitative-affine-gap}) and Theorem 5.1 (\label{thm:approximation-hardness}); Lean: LatticePrepro/Main.lean, LatticePrepro.GapReduction, LatticePrepro.momentAxes, LatticePrepro.prefactorExp, LatticePrepro.gapExp, LatticePrepro.sizeExp, LatticePrepro.CodeGap, LatticePrepro.LatticeGap
Human review
  • Endorsed by Shuze Chen · Nov 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by WizardOfMenlo · Nov 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me