Lemma 5.2 (lattices, YES instances) — approximate solutions pass the test
ProvedLatticePrepro.LatticeReduction.accepts_of_isApproxLet be a prime, a linear-system family over with blocks, , and a norm exponent (a real or ) with . Let Red be a lattice reduction for , and (the output of Lemma 3.12): a lattice , targets , a radius and a residual weight . Let be a real number with
If is a YES instance of and is an -approximate solution, that is, and , then is accepted:
Here (Definition 3.1).
This is the YES half of Lemma 5.2 (Testing search outputs) for lattices. In Theorem 5.1 for lattices it is applied with , so that every -approximate solution to a YES instance passes the test.
Formalization Note. Red : LatticeReduction L g pn is an arbitrary lattice reduction; its YES radius bound and weight bound are fields of the structure. The paper assumes and ; Lean needs only and , with a real power. is latticeDist, and the test is the predicate LatticeReduction.Accepts. The polynomial running time of the test is not formalized.
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_Conversions_SearchTest
open LatticePrepro
open LatticePrepro.LatticeReduction
variable {p : ℕ} [Fact p.Prime] {X : Type} {L : LinearSystemFamily (ZMod p) X} {g : ℕ}
{pn : PNorm} (Red : LatticeReduction L g pn)theorem LatticePrepro.LatticeReduction.accepts_of_isApprox {f : ℝ} (hf : 0 ≤ f) (hgf : 16 * f ^ pn.s ≤ g) {x : X}
(hx : L.IsYes x) {v : Red.Λ.M → ℤ} (hv : Red.IsApprox f x v) : Red.Accepts x v := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.