Counting lattice vectors

DOI10.1016/J.JCSS.2007.03.014MaRDI QIDQ2643017zbMATH OpenOpenAlexFDO

Publication date 23 August 2007

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2007.03.014

\(\#\)P-complete algorithms complexity lattices modular forms theta functions

Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

In an integral lattice counting the number of vectors of (Euclidean) length \(d\) is \(\#\)P-complete [see \textit{L. G. Valiant}, Theor. Comput. Sci. 8, 189--201 (1979; Zbl 0415.68008)] and at least as hard as integer factorization. For lattice rank \(r\) and a basis of \(s\) bits a deterministic algorithm is presented with time \(2^{O(rs+\log d)}\). The length is a quadratic form corresponding to a theta function and the vector count is essentially the \(d\)th coefficient of its Fourier expansion. Since the theta function is a modular form, a basis of (say) Eisenstein series can be constructed. There are painful details involving the fact that unimodular forms do not have even diagonal except for special cases (e.g., of rank 8) so that the dimension has to be augmented to a multiple of 8 to remain in the modular group. The reversion of this complexity problem to its classical theory is in the author's words ``long overdue.

Recommendations

Cites work

Cited in

(3)

Describes a project that uses

Uses Software

ecdata

This page was built for publication: Counting lattice vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643017)