Counting lattice vectors (Q2643017)

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''.