A halving window for the width initialized by the native LLL basis
ProvedInfoLossLAR.WorstCase.RegevSearch.native_reduced_basis_halving_windowdiscrete-gaussianslar-regev-bridgelatticeslll
Let be a nonsingular integer basis of dimension and let be a rational width satisfying the discrete Gaussian sampling promise. Compute the native LLL basis of . Let be the larger of and , and set . The first integer for which is at most , and its width lies in .
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS import Definitions.Def_LARLLL_CurrentData set_option autoImplicit false open scoped BigOperators open InfoLossLAR.WorstCase InfoLossLAR.WorstCase.RegevSketch
Formal statement
namespace InfoLossLAR.WorstCase.RegevSearch
theorem native_reduced_basis_halving_window {n : ℕ} (hn : 2 ≤ n) (B : Matrix (Fin n) (Fin n) ℤ)
(hB : B.det ≠ 0) (r : ℚ) (hr : 0 < r) (hp : dgsThreshold B ≤ (r:ℝ)) :
let D:=NativeLLL.basis B
let W : ℝ:=(max (((n+1 : ℕ) : ℚ)*(1+∑ i,∑ j,|(D i j:ℚ)|)) (r*(famσ n:ℚ)) : ℚ)
let w:=(r:ℝ)*(famσ n:ℝ)/(Real.sqrt 2*Real.sqrt n)
∃ k : ℕ, k ≤ 5*n+2 ∧ w/2 ≤ W/2^k ∧ W/2^k ≤ w ∧ ∀ j < k, w < W/2^j := by
sorry
end InfoLossLAR.WorstCase.RegevSearchSource
The actual native LLL initialization and first-crossing estimate in the proof of InfoLossLAR.WorstCase.RegevSearch.reduced_basis_admissible_width_schedule. This version specifies the computed basis and the position of the first crossing, both used by the coherent shared-pool Fourier sampler.