On the Hardness of Approximating Shortest Integer Relations among Rational Numbers

Carsten R\H{o}ssner
Department of Mathematical Computer Science, University of Frankfurt, P.O. Box 11 19 32, 60054 Frankfurt on the Main, Germany
roessner@cs.uni-frankfurt.de

Jean-Pierre Seifert
Department of Mathematical Computer Science, University of Frankfurt, P.O. Box 11 19 32, 60054 Frankfurt on the Main, Germany
seifert@cs.uni-frankfurt.de

Given $x \in {\Bbb{R}}^n$ an integer relation for $x$ is a non-trivial vector $m \in {\Bbb{Z}}^n$ with inner product < m, x > = 0.

In this paper we prove the following: Unless every NP language is recognizable in deterministic quasi-polynomial time, i.e., in time $O(n^{poly(\log n)})$, the $\ell_{\infty}$-shortest integer relation for a given vector $x \in {\Bbb{Q}}^n$ cannot be approximated in polynomial time within a factor of $2^{\log^{0.5 - \gamma} n}$, where $\gamma$ is an arbitrarily small positive constant.

This result is quasi-complementary to positive results derived from lattice basis reduction. A variant of the well-known $L^3$-algorithm approximates for a vector $x \in {\Bbb{Q}}^n$ the $\ell_{2}$-shortest integer relation within a factor of $2^{n/2}$ in polynomial time.

Our proof relies on recent advances in the theory of probabilistically checkable proofs, in particular on a reduction from 2-prover 1-round interactive proof-systems.

The same inapproximability result is valid for finding the $\ell_{\infty}$-shortest integer solution for a homogeneous linear system of equations over ${\Bbb{Q}}$.