Counting Co-cyclic lattices

Phong Q. Nguyen, Igor E. Shparlinski

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

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 ℤn. This set of lattices L can naturally be partitioned with respect to the factor group ℤn/L. Accordingly, we count the number of full-rank integer lattices L ⊆ ℤn such that ℤ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 (ς(6)IInk=4 ς(k))-1≈85%. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.

Original languageEnglish
Pages (from-to)1358-1370
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Volume30
Issue number3
DOIs
Publication statusPublished - 2016
Externally publishedYes

Keywords

  • Cyclic lattices
  • Homogeneous congruences
  • Multiplicative functions

Fingerprint

Dive into the research topics of 'Counting Co-cyclic lattices'. Together they form a unique fingerprint.

Cite this