Claim 3.15 — quadratic gate equations define the same language as the gates
ProvedLatticePrepro.GateVerifier.language_toQuadraticLet be a prime and a gate verifier with instance length , wires (inputs , output wire ) and gates imposing . Let be its quadratic verifier over , with coordinates (wire becomes coordinate ) and gate equations
where are the coefficients of the multilinear interpolation of , reduced mod . Then the two verifiers have the same language:
That is, for every the following are equivalent:
- there is with , every , for every gate , for and (an accepting assignment of on );
- there is a wire assignment in satisfying every gate constraint of , with input and output wire .
The main results of the formalization are stated for quadratic verifiers; this theorem (with BoolCircuit.language_toGateVerifier) makes them apply to any Boolean circuit, in particular to the 3SAT verifier.
Formalization Note: Claim 3.15 is stated per assignment (a Boolean assignment is valid if and only if all gate equations vanish) and includes the polynomial-time computability of the coefficients; the Lean theorem states the resulting equality of languages, for every prime , and computability is not formalized. Boolean values are identified with .
import Mathlib import Definitions.Def_LatticePrepro_Verifier_Quadratic import Definitions.Def_LatticePrepro_Verifier_Gates open LatticePrepro open LatticePrepro.GateVerifier variable (W : GateVerifier) variable (p : ℕ) variable [Fact p.Prime]
theorem LatticePrepro.GateVerifier.language_toQuadratic : (W.toQuadratic p).Language = W.Language := by sorry
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.