An exact coefficient cube for the shortest-vector threshold after LLL
ProvedInfoLossLAR.WorstCase.RegevSketch.reduced_basis_gap_box_exactalgorithmslar-regev-bridgelattices
Let , let be a nonsingular integer matrix, and let be rational. Write for the native LLL output basis of the lattice generated by the columns of .
The shortest nonzero vector length satisfies if and only if there is an integer vector such that
The search cube depends only on dimension. It provides the correctness criterion for a finite exact scan using the reduced basis.
Preamble
import Definitions.Def_InfoLossLAR_WorstCase_LatticeProblems import Definitions.Def_LARLLL_CurrentData set_option autoImplicit false open InfoLossLAR.WorstCase open scoped BigOperators
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem reduced_basis_gap_box_exact {n : ℕ} (hn : 0 < n)
(B : Matrix (Fin n) (Fin n) ℤ) (hB : B.det ≠ 0) (δ : ℚ) (hδ : 0 ≤ δ) :
let normSq (z : Fin n → ℤ) : ℚ :=
((∑ i : Fin n, (((NativeLLL.basis B).mulVec z) i)^2 : ℤ) : ℚ)
lam1 B ≤ (δ : ℝ) ↔ ∃ z : Fin n → ℤ,
(∀ i, (z i).natAbs ≤ n * 2^(n-1) * (n+1)^n) ∧
0 < normSq z ∧ normSq z ≤ δ^2 := by sorry
end InfoLossLAR.WorstCase.RegevSketchSource
A.K. Lenstra, H.W. Lenstra Jr. and L. Lovász, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982), §1, https://doi.org/10.1007/BF01457454, reduced-basis inequalities (1.4)–(1.7). The displayed coefficient bound is derived from these inequalities by back substitution for the concrete native basis.