Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The 3SAT language SATv\mathrm{SAT}_vSATv​ (Theorem 5.1)

Definition
LatticePrepro_ThreeSAT

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

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

For a number vvv of variables, SATv\mathrm{SAT}_vSATv​ is the set of satisfiable 3SAT instances on vvv variables:

SATv={ x:x is a 3SAT instance on v variables and x is satisfiable }.\mathrm{SAT}_v = \{\, x : x \text{ is a 3SAT instance on } v \text{ variables and } x \text{ is satisfiable} \,\}.SATv​={x:x is a 3SAT instance on v variables and x is satisfiable}.

An instance xxx selects a set of clauses (one bit for each of the (2v)3(2v)^3(2v)3 possible clauses, each clause being an ordered triple of literals), and xxx is satisfiable if some assignment a∈{0,1}va \in \{0,1\}^va∈{0,1}v satisfies every clause present in xxx, i.e. every present clause contains a literal (i,s)(i, s)(i,s) with ai=sa_i = sai​=s.

SATv\mathrm{SAT}_vSATv​ is the language separated by the fixed codes and lattices of Theorem 5.1 in its 3SAT form (ThreeSAT.exists_code_gap, ThreeSAT.exists_lattice_gap): satisfiable instances get targets close to the code or lattice, unsatisfiable ones get targets far from it.

Formalization Note: SAT v : Set (Instance v) is {x | Satisfiable x}, with Instance and Satisfiable from the 3SAT verifier module. The bundle imports the whole development but defines only this set.

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
import Definitions.Def_LatticePrepro_Main
import Definitions.Def_LatticePrepro_Verifier_Gates
import Definitions.Def_LatticePrepro_Verifier_Circuit
import Definitions.Def_LatticePrepro_Verifier_Expr
import Definitions.Def_LatticePrepro_Verifier_ThreeSAT

/-!
# Theorem 5.1 for 3SAT

The main theorems of `Main.lean` are stated for an arbitrary quadratic verifier. Instantiating
them with the verifier circuit of `Verifier/ThreeSAT.lean` (Claim 3.15 and Definition 3.14 turn
it into a quadratic verifier with the same language) gives the paper's Theorem 5.1 for 3SAT:
fixed codes and lattices of dimension `M ≤ n^C`, where `n = (2v)^3` is the instance length of
3SAT on `v` variables, with targets `t_x` such that satisfiable instances have
`dist(t_x, ·) ≤ R` and unsatisfiable ones `dist(t_x, ·) > M^{1/s - ε} · R`.
-/

namespace LatticePrepro

namespace ThreeSAT

/-- The language of satisfiable 3SAT instances on `v` variables. -/
def SAT (v : ℕ) : Set (Instance v) := {x | Satisfiable x}

end ThreeSAT

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 5.1 (\label{thm:approximation-hardness}); Lean: LatticePrepro/ThreeSAT.lean, LatticePrepro.ThreeSAT.SAT
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