COUNTING LATTICE VECTORS

Abstract. We consider the problem of counting the number of lattice vectors of a given length and prove several results regarding its computational complexity. We show that the problem is ♯Pcomplete resolving an open problem. Furthermore, we show that the problem is at least as hard as integer factorization even for lattices of bounded rank or lattices generated by vectors of bounded norm. Next, we discuss a deterministic algorithm for counting the number of lattice vectors of length d in time 2 O(rs+log d) , where r is the rank of the lattice, s is the number of bits that encode the basis of the lattice. The algorithm is based on the theory of modular forms