Counting Co-cyclic lattices

Phong Q. Nguyen; Igor E. Shparlinski

doi:10.1137/15M103950X

Counting Co-cyclic lattices

Phong Q. Nguyen, Igor E. Shparlinski

Research output: Contribution to journal › Article › peer-review

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

Original language	English
Pages (from-to)	1358-1370
Number of pages	13
Journal	SIAM Journal on Discrete Mathematics
Volume	30
Issue number	3
DOIs	https://doi.org/10.1137/15M103950X
Publication status	Published - 2016
Externally published	Yes

Keywords

Cyclic lattices
Homogeneous congruences
Multiplicative functions

Access to Document

10.1137/15M103950X

Cite this

@article{01c83828cd3f490c8b344405c9c256fd,

title = "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 ℤ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.",

keywords = "Cyclic lattices, Homogeneous congruences, Multiplicative functions",

author = "Nguyen, {Phong Q.} and Shparlinski, {Igor E.}",

year = "2016",

doi = "10.1137/15M103950X",

language = "English",

volume = "30",

pages = "1358--1370",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Counting Co-cyclic lattices

AU - Nguyen, Phong Q.

AU - Shparlinski, Igor E.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Cyclic lattices

KW - Homogeneous congruences

KW - Multiplicative functions

UR - http://www.scopus.com/inward/record.url?scp=84990966296&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP130100237

UR - http://purl.org/au-research/grants/arc/DP140100118

U2 - 10.1137/15M103950X

DO - 10.1137/15M103950X

M3 - Article

AN - SCOPUS:84990966296

VL - 30

SP - 1358

EP - 1370

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 3

ER -

Counting Co-cyclic lattices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

New Applications of Additive Combinatorics in Number Theory and Graph Theory

Cite this

Counting Co-cyclic lattices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

New Applications of Additive Combinatorics in Number Theory and Graph Theory

Cite this