A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910055585021952 |
|---|---|
| author | Kuhlmann, Stefan Weismantel, Robert |
| author_facet | Kuhlmann, Stefan Weismantel, Robert |
| contents | One important question in the theory of lattices is to detect a shortest vector: given a norm and a lattice, what is the smallest norm attained by a non-zero vector contained in the lattice? We focus on the infinity norm and work with lattices of the form $A\mathbb{Z}^n$, where $A$ has integer entries and is of full column rank. Finding a shortest vector is NP-hard. We show that this task is fixed parameter tractable in the parameter $Δ$, the largest absolute value of the determinant of a full rank submatrix of $A$. The algorithm is based on a structural result that can be interpreted as a threshold phenomenon: whenever the dimension $n$ exceeds a certain value determined only by $Δ$, then a shortest lattice vector attains an infinity norm value of one. This threshold phenomenon has several applications. In particular, it reveals that integer optimal solutions lie on faces of the given polyhedron whose dimensions are bounded only in terms of $Δ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02249 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm Kuhlmann, Stefan Weismantel, Robert Optimization and Control Data Structures and Algorithms Combinatorics One important question in the theory of lattices is to detect a shortest vector: given a norm and a lattice, what is the smallest norm attained by a non-zero vector contained in the lattice? We focus on the infinity norm and work with lattices of the form $A\mathbb{Z}^n$, where $A$ has integer entries and is of full column rank. Finding a shortest vector is NP-hard. We show that this task is fixed parameter tractable in the parameter $Δ$, the largest absolute value of the determinant of a full rank submatrix of $A$. The algorithm is based on a structural result that can be interpreted as a threshold phenomenon: whenever the dimension $n$ exceeds a certain value determined only by $Δ$, then a shortest lattice vector attains an infinity norm value of one. This threshold phenomenon has several applications. In particular, it reveals that integer optimal solutions lie on faces of the given polyhedron whose dimensions are bounded only in terms of $Δ$. |
| title | A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm |
| topic | Optimization and Control Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2508.02249 |