Counting Lattice Vectors

Abstract

We consider the problem of counting the number of lattice vectors of a given length. We show that problem is #P-complete 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 .Z0(rs+109d) , where 1- 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.