×
Böttcher, Albrecht; Fukshansky, Lenny; Garcia, Stephan Ramon; Maharaj, Hiren

On lattices generated by finite abelian groups. (English) Zbl 1328.11077

SIAM J. Discrete Math. 29, No. 1, 382-404 (2015).
Let \(G = \{0,g_1,\dots,g_n\}\) be a finite abelian group. Several authors have previously studied the lattice generated by \(G\), \[ \mathcal{L}(G) = \left\{X = (x_1,\dots,x_n,-x_1-\cdots - x_n) \in \mathbb{Z}^{n+1}: x_1 g_1+\cdots + x_n g_n = 0\right\}. \] In particular, M. Sha [Finite Fields Appl. 31, 84–107 (2015; Zbl 1386.11083)] has shown that when \(G\) is the direct product of two cyclic groups and is not isomorphic to \(\mathbb{Z}/4\mathbb{Z}\), that this lattice has a basis of vectors of minimal length. Sha has also given an upper bound for the covering radius of \(\mathcal{L}(\mathbb{Z}/n\mathbb{Z})\).
The authors of this paper extend this first result on to all finite abelian groups. They find an explicit basis matrix for each cyclic group and then show how these bases can be combined under taking direct products. Several of the proofs rely on computing determinants of particular matrices by applications of the Cauchy-Binet formula. The arguments are very concrete and helpful examples are given.
The authors also improve Sha’s result on the covering radius. The main idea is to first choose a basis matrix and then considering the sublattices spanned by the first \(k\) columns of the matrix. Finally, the authors also express the automorphism group of \(\mathcal{L}(G)\) in terms of the group of automorphisms of \(G\) and give a geometric interpretation of this result.
Reviewer: Nathan Kaplan (Irvine)

Cited in 1 Review
Cited in 6 Documents

MSC:

11H31 Lattice packing and covering (number-theoretic aspects)
11G20 Curves over finite and local fields
11H55 Quadratic forms (reduction theory, extreme forms, etc.)
15A15 Determinants, permanents, traces, other special matrix functions
15B05 Toeplitz, Cauchy, and related matrices
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)

Keywords:

well-rounded lattice; finite abelian group; minimal vector; covering radius; automorphism group; Toeplitz determinant

Citations:

Zbl 1386.11083
PDF BibTeX XML Cite
\textit{A. Böttcher} et al., SIAM J. Discrete Math. 29, No. 1, 382--404 (2015; Zbl 1328.11077)
Full Text: DOI arXiv

References:

[1] E. S. Barnes, {\it The perfect and extreme senary forms}, Canad. J. Math., 9 (1957), pp. 235-242. · Zbl 0078.03704
[2] E. Bayer-Fluckiger, {\it Lattices and number fields}, Contemp. Math., 241 (1999), pp. 69-84. · Zbl 0951.11016
[3] E. Bayer-Fluckiger, {\it Ideal lattices}, in A Panorama of Number Theory or the View from Baker’s Garden (Zürich, 1999), Cambridge University Press, Cambridge, 2002, pp. 168-184. · Zbl 1043.11057
[4] A. Böttcher, L. Fukshansky, S. R. Garcia, and H. Maharaj, {\it Toeplitz determinants with perturbations in the corners}, J. Funct. Anal., 268 (2015), pp. 171-193. · Zbl 1300.15010
[5] A. Böttcher and B. Silbermann, {\it Toeplitz matrices and determinants with Fisher-Hartwig symbols}, J. Funct. Anal., 63 (1985), pp. 178-214. · Zbl 0592.47016
[6] A. Böttcher and B. Silbermann, {\it Analysis of Toeplitz Operators}, 2nd ed., Springer-Verlag, Berlin, 2006. · Zbl 1098.47002
[7] A. Böttcher and H. Widom, {\it Two elementary derivations of the pure Fisher-Hartwig determinant}, Integral Equations Operator Theory, 53 (2005), pp. 593-596. · Zbl 1081.47033
[8] J. H. Conway and N. J. A. Sloane, {\it A lattice without a basis of minimal vectors}, Mathematika, 42 (1995), pp. 175-177. · Zbl 0826.11029
[9] J. H. Conway and N. J. A. Sloane, {\it Sphere Packings, Lattices, and Groups}, 3rd ed., Springer-Verlag, New York, 1999. · Zbl 0915.52003
[10] L. Fukshansky and H. Maharaj, {\it Lattices from elliptic curves over finite fields}, Finite Fields Appl., 28 (2014), pp. 67-78. · Zbl 1296.11086
[11] L. Fukshansky and X. Sun, {\it On the geometry of cyclic lattices}, Discrete Comput. Geom., 52 (2014), pp. 240-259. · Zbl 1310.11071
[12] L. Fukshansky, S. R. Garcia, and X. Sun, {\it Permutation Invariant Lattices}, preprint, arXiv:1409.1491 [math.CO], 2014. · Zbl 1375.11052
[13] P. M. Gruber and C. G. Lekkerkerker, {\it Geometry of Numbers}, 2nd ed., North-Holland, Amsterdam, 1987. · Zbl 0611.10017
[14] C. J. Hillar and D. L. Rhea, {\it Automorphisms of finite Abelian groups}, Amer. Math. Monthly, 114 (2007), pp. 917-923. · Zbl 1156.20046
[15] V. Jarnik, {\it Zwei Bemerkungen zur Geometrie der Zahlen}, Věstnik Královské České Společnosti Nauk, Třida Matemat. Přirodověd., 1941.
[16] V. Lyubashevsky and D. Micciancio, {\it Generalized compact knapsacks are collision resistant}, in Automata, Languages and Programming, Part II, Lecture Notes in Comput. Sci. 4052, Springer-Verlag, Berlin, 2006, pp. 144-155. · Zbl 1133.68353
[17] J. Martinet, {\it Perfect Lattices in Euclidean Spaces}, Springer-Verlag, Berlin, 2003. · Zbl 1017.11031
[18] J. Martinet and A. Schürmann, {\it Bases of minimal vectors in lattices,} III, Internat. J. Number Theory, 8 (2012), pp. 551-567. · Zbl 1292.11078
[19] H.-G. Rück, {\it A note on elliptic curves over finite fields}, Math. Comp., 49 (1987), pp. 301-304. · Zbl 0628.14019
[20] M. Sha, {\it On the lattices from ellptic curves over finite fields}, Finite Fields Appl., 31 (2015), pp. 84-107. · Zbl 1386.11083
[21] A. Schürmann, {\it Computational Geometry of Positive Definite Quadratic Forms, Polyhedral Reduction Theories, Algorithms, and Applications}, AMS, Providence, RI, 2009. · Zbl 1185.52016
[22] M. A. Tsfasman and S. G. Vladut, {\it Algebraic-Geometric Codes}, Kluwer Academic, Dordrecht, 1991. · Zbl 0727.94007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.