O30 — Polynomial-factor lattice approximation

Definitions and mathematical statement

Let $B$ be a nonsingular $n\times n$ integer matrix, whose columns $b_1,\ldots,b_n$ form a basis of the full-rank lattice \[ L(B)=\{Bz:z\in\mathbb Z^n\}\subset\mathbb R^n. \] Use the Euclidean norm $\|v\|_2=(\sum_i v_i^2)^{1/2}$, and define its first minimum by $\lambda_1(L)=\min\{\|v\|_2:0\ne v\in L\}$. The minimum exists because a lattice is discrete.

Does there exist an absolute constant $c>0$ and a deterministic classical algorithm which, for every such basis, returns a nonzero vector $v\in L(B)$ satisfying \[ \|v\|_2\le n^c\lambda_1(L(B)) \] in time polynomial in the binary encoding length of $B$? The polynomial must be uniform as the dimension and entry sizes vary. One may output either $v$ with a membership certificate or an integer coefficient vector $z\ne0$ with $v=Bz$.

The approximation exponent $c$ must be fixed independently of the input, although its value is part of what a positive answer may establish. It is not enough to obtain a factor exponential in $n$, or a running time polynomial only when $n$ is fixed. The comparison is with the shortest nonzero vector of the lattice itself, which is independent of the supplied basis and need not be a basis column.

Short English statement

Is there a deterministic polynomial-time algorithm approximating a lattice’s shortest nonzero vector within a fixed polynomial factor in its dimension?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400034 (AMR-083-0034), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O30, p20 / LNCS p310. Original source indexed by AMR-083-0034. https://mccurley.org/papers/open.ps.gz.