Computing Gröbner bases associated with lattices

Ismara Álvarez-Barrientos; Mijail  Borges-Quintana; Miguel Angel  Borges-Trenard; Daniel Panario

doi:10.3934/amc.2016045

Article Contents

2016, Volume 10, Issue 4: 851-860. Doi: 10.3934/amc.2016045

This issue Previous Article Some new two-weight ternary and quinary codes of lengths six and twelve Next Article Public key protocols over the ring $E_{p}^{(m)}$

Computing Gröbner bases associated with lattices

1.
Departamento de Matemática, Universidad de Oriente, Santiago de Cuba
2.
School of Mathematics and Statistics, Carleton University, Ottawa

Received: March 2015

Published: November 2016

Abstract / Introduction Related Papers Cited by

Abstract

We specialize Möller's algorithm to the computation of Gröbner bases related to lattices. We give the complexity analysis of our algorithm. Then we provide experiments showing that our algorithm is more efficient than Buchberger's algorithm for computing the associated Gröbner bases. Furthermore we show that the binomial ideal associated to the lattice can be constructed from a set of binomials associated with a set of generators of the corresponding label code. This result is presented in a general way by means of three ideal constructions associated with group codes that constitute the same ideal. This generalizes earlier results for specific cases of group codes such as linear codes, codes over ${\mathbb Z}_m$ and label codes of lattices.

Keywords:

Mathematics Subject Classification: Primary: 13P10; Secondary: 14G50.

Citation:

Related Papers

Cited by

References

[1]	W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Amer. Math. Soc., 1994.doi: 10.1090/gsm/003.
[2]	M. Aliasgari, M. R. Sadeghi and D. Panario, Gröbner bases for lattices and an algebraic decoding algorithm, IEEE Trans. Commun., 61 (2013), 1222-1230.
[3]	A. H. Banihashemi and I. F. Blake, Trellis complexity and minimal trellis diagrams of lattices, IEEE Trans. Inform. Theory, 44 (1998), 1829-1847.doi: 10.1109/18.705562.
[4]	A. H. Banihashemi and F. R. Kschischang, Tanner graphs for group block codes and lattices: construction and complexity, IEEE Trans. Inform. Theory, 47 (2001), 822-834.doi: 10.1109/18.910592.
[5]	M. Borges-Quintana, M. A. Borges-Trenard and E. Martínez-Moro, A Gröbner representation for linear codes, in Adv. Coding Theory Crypt., World Scientific, 2007, 17-32.
[6]	M. Borges-Quintana, M. A. Borges-Trenard and E. Martínez-Moro, On a Gröbner bases structure associated to linear codes, J. Discrete Math. Sci. Crypt., 10 (2007), 151-191.doi: 10.1080/09720529.2007.10698114.
[7]	M. Borges-Quintana, M. A. Borges-Trenard, P. Fitzpatrick and E. Martínez-Moro, On Gröbner basis and combinatorics for binary codes, Appl. Algebra Engin. Commun. Comp., 19 (2008), 393-411.doi: 10.1007/s00200-008-0080-2.
[8]	M. A. Borges-Trenard, M. Borges-Quintana and T. Mora, Computing Gröbner bases by FGLM techniques in a non-commutative setting, J. Symb. Comput., 30 (2000), 429-449.doi: 10.1006/jsco.1999.0415.
[9]	B. Buchberger, An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-dimensional Ideal (in German), Ph.D. thesis, Univ. Innsbruck, Austria, 1965.
[10]	B. Buchberger and H. M. Möller, The construction of multivariate polynomials with preassigned zeros, in EUROCAM'82, Marseille, 1982, 24-31.
[11]	J. C. Faugere, P. Gianni, D. Lazard and T. Mora, Efficient computation of zerodimensional Gröbner bases by change of ordering, J. Symb. Comput., 16 (1993), 329-344.doi: 10.1006/jsco.1993.1051.
[12]	The GAP Group, GAP-Groups, Algorithms, and Programming, available online at http://www.gap-system.org
[13]	S. Lundqvist, Complexity of comparing monomials and two improvements of the BM-algorithm, in Math. Methods Computer Science, Springer, Berlin, 2008, 105-125.doi: 10.1007/978-3-540-89994-5_9.
[14]	I. Márquez-Corbella and E. Martínez-Moro, Algebraic structure of the minimal support codewords set of some linear codes, Adv. Math. Commun., 5 (2011), 233-244.doi: 10.3934/amc.2011.5.233.
[15]	T. Mora, Solving Polynomial Equation Systems II: Macaulay's Paradigm and Gröbner Technology, Cambridge Univ. Press, 2005.doi: 10.1017/CBO9781107340954.
[16]	T. Mora, The FGLM problem and Möller's algorithm on zero-dimensional ideals, in Gröbner, Coding, and Cryptography, Springer, 2009, 379-384.