Counting lattice vectors

摘要

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 2O(rs+logd), 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.