Vol. 4, No. 1, 2020

Download this article
Download this article For screen
For printing
Recent Volumes
5: Gauge Theory and Low-Dimensional Topology
4: ANTS XIV
3: Hillman: Poincaré Duality
2: ANTS XIII
1: ANTS X
The Open Book Series
All Volumes
 
About the Series
Ethics Statement
Purchase Printed Copies
Author Index
 
ISSN (electronic): 2329-907X
ISSN (print): 2329-9061
 
MSP Books and Monographs
Other MSP Publications
Reductions between short vector problems and simultaneous approximation

Daniel E. Martin

Vol. 4 (2020), No. 1, 335–351
Abstract

In 1982, Lagarias showed that solving the approximate shortest vector problem also solves the problem of finding good simultaneous Diophantine approximations (SIAM J. Comput., 14(1):196–209, 1985)). Here we provide a deterministic, dimension-preserving reduction in the reverse direction. It has polynomial time and space complexity, and it is gap-preserving under the appropriate norms. We also give an alternative to the Lagarias algorithm by first reducing his version of simultaneous approximation to one with no explicit range in which a solution is sought.

Keywords
lattice reduction, shortest vector problem, simultaneous Diophantine approximation, simultaneous approximation
Mathematical Subject Classification 2010
Primary: 11H06, 52C07, 68W25
Milestones
Received: 28 February 2020
Revised: 1 August 2020
Accepted: 15 August 2020
Published: 29 December 2020
Authors
Daniel E. Martin
Department of Mathematics
University of Colardo
Boulder, CO
United States