Counting Co-Cyclic Lattices

Abstract : There is a well-known asymptotic formula, due to W. M. Schmidt [Duke Math. J., 35 (1968), pp. 327--339], 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 $(\zeta(6) \prod_{k=4}^n \zeta(k))^{-1} \approx 85\%$. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (3), pp.1358-1370. 〈10.1137/15M103950X〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01382385
Contributeur : Phong Q. Nguyen <>
Soumis le : lundi 17 octobre 2016 - 07:01:47
Dernière modification le : mercredi 21 mars 2018 - 18:57:49

Identifiants

Collections

Citation

Phong Q. Nguyen, Igor E. Shparlinski. Counting Co-Cyclic Lattices. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (3), pp.1358-1370. 〈10.1137/15M103950X〉. 〈hal-01382385〉

Partager

Métriques

Consultations de la notice

149