Optimal Sample Exponents for Direct Discrete-Gaussian SVP Search on Haar Random Lattices
Abstract
We determine the optimal sample exponent for direct discrete Gaussian SVP search on Haar random unimodular lattices, counting zero outputs. The output is one sampled vector, optionally divided by the greatest common divisor of its lattice coordinates. For every fixed approximation factor 1≤γ<√e, the exponent is γ2/(2e)−logγ in natural logarithmic units; it is zero for γ≥√e. For exact SVP this gives 0.2653689… in base two. The converse permits arbitrary positive widths chosen from the lattice and all previous outputs, and a fixed width attains every exponent above the threshold. Aggarwal, Dadush, Regev, and Stephens-Davidowitz already give a width within a factor two of optimal for exact SVP on each lattice. We determine the explicit Haar typical rate and show that primitive reduction preserves it. An explicit finite dimensional converse controls all widths simultaneously, including recovery from long multiples; together with finite attainment bounds, it yields query guarantees in both directions. The proof uses random lattice moments and a pointwise Gaussian bound optimized over the width. We account for sampling error and separate sample requirements from generation costs in comparisons with the random lattice search of Pouly and Shen and later algorithms.
Related
- PDE-Based Bounds on Optimal Exponents in Active Simple Hypothesis Testing
- Optimal Decay Exponents for Fractional Burgers Rarefaction Waves
- Algebraic Structure and Orthogonality Properties of Rational Polynomial Phase Rings on Discrete Lattices
- Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy
- Optimal Lojasiewicz-Simon Exponents and the Intrinsic Singularities of Analytic Functionals
BibTeX
@misc{kaminaga2026optimal,
title = {{Optimal Sample Exponents for Direct Discrete-Gaussian SVP Search on Haar Random Lattices}},
author = {Masahiro Kaminaga},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30808},
eprint = {2609.30808},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30808},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Sample Exponents for Direct Discrete-Gaussian SVP Search on Haar Random Lattices
AU - Masahiro Kaminaga
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.30808
UR - https://arxiv.org/abs/2609.30808
AB - We determine the optimal sample exponent for direct discrete Gaussian SVP search on Haar random unimodular lattices, counting zero outputs. The output is one sampled vector, optionally divided by the greatest common divisor of its lattice coordinates. For every fixed approximation factor 1≤γ<√e, the exponent is γ^2/(2e)−logγ in natural logarithmic units; it is zero for γ≥√e. For exact SVP this gives 0.2653689… in base two. The converse permits arbitrary positive widths chosen from the lattice and all previous outputs, and a fixed width attains every exponent above the threshold. Aggarwal, Dadush, Regev, and Stephens-Davidowitz already give a width within a factor two of optimal for exact SVP on each lattice. We determine the explicit Haar typical rate and show that primitive reduction preserves it. An explicit finite dimensional converse controls all widths simultaneously, including recovery from long multiples; together with finite attainment bounds, it yields query guarantees in both directions. The proof uses random lattice moments and a pointwise Gaussian bound optimized over the width. We account for sampling error and separate sample requirements from generation costs in comparisons with the random lattice search of Pouly and Shen and later algorithms.
ER -