Counting Co-Cyclic Lattices
| Autor: | Phong Q. Nguyen, Igor E. Shparlinski |
|---|---|
| Přispěvatelé: | Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), University of New South Wales [Sydney] (UNSW), Tsinghua University [Beijing], Inria de Paris, Japanese French Laboratory for Informatics (JFLI), National Institute of Informatics (NII)-Université Pierre et Marie Curie - Paris 6 (UPMC)-The University of Tokyo (UTokyo)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2016 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) High Energy Physics::Lattice General Mathematics 0102 computer and information sciences 01 natural sciences Combinatorics [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Integer FOS: Mathematics Natural density Asymptotic formula Number Theory (math.NT) [MATH]Mathematics [math] Mathematics Discrete mathematics homogeneous congruences Mathematics - Number Theory cyclic lattices Group (mathematics) Lattice problem Order (ring theory) [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT] multiplicative functions 010201 computation theory & mathematics Computer Science - Discrete Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (3), pp.1358-1370. ⟨10.1137/15M103950X⟩ SIAM Journal on Discrete Mathematics, 2016, 30 (3), pp.1358-1370. ⟨10.1137/15M103950X⟩ |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/15m103950x |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|