Counting Co-Cyclic Lattices

Abstract

There is a well-known asymptotic formula, due to W. M. Schmidt (1968) for the number of full-rank integer lattices of index at most $V$ in ${\mathbb{Z}}^n$. This set of lattices $L$ can naturally be partitioned with respect to the factor group ${\mathbb{Z}}^n/L$. Accordingly, we count the number of full-rank integer lattices $L\subseteq {\mathbb{Z}}^n$ such that ${\mathbb{Z}}^n/L$ is cyclic and of order at most $V$, and deduce that these co-cyclic lattices are dominant among all integer lattices: their natural density is ${\left(\zeta (6){\prod }_{k=4}^n\zeta (k)\right)}^{-1}\approx 85\%$. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.