Computing Gröbner bases associated with lattices

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

November 2016, 10(4): 851-860. doi: 10.3934/amc.2016045

Computing Gröbner bases associated with lattices

Ismara Álvarez-Barrientos ^1, , Mijail Borges-Quintana ^1, , Miguel Angel Borges-Trenard ^1, and Daniel Panario ^2,

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
Related Papers

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: Möller algorithm, group codes., Gröbner bases, label codes, lattices.

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

Citation: Ismara Álvarez-Barrientos, Mijail Borges-Quintana, Miguel Angel Borges-Trenard, Daniel Panario. Computing Gröbner bases associated with lattices. Advances in Mathematics of Communications, 2016, 10 (4) : 851-860. doi: 10.3934/amc.2016045

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.

show all references

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.

[1]	Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046
[2]	Amin Sakzad, Mohammad-Reza Sadeghi. On cycle-free lattices with high rate label codes. Advances in Mathematics of Communications, 2010, 4 (4) : 441-452. doi: 10.3934/amc.2010.4.441
[3]	Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Addendum. Advances in Mathematics of Communications, 2011, 5 (3) : 543-546. doi: 10.3934/amc.2011.5.543
[4]	Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225
[5]	Arnulf Jentzen, Felix Lindner, Primož Pušnik. On the Alekseev-Gröbner formula in Banach spaces. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4475-4511. doi: 10.3934/dcdsb.2019128
[6]	Sergio Estrada, J. R. García-Rozas, Justo Peralta, E. Sánchez-García. Group convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 83-94. doi: 10.3934/amc.2008.2.83
[7]	Adrian Korban, Serap Sahinkaya, Deniz Ustun. New type I binary $[72, 36, 12]$ self-dual codes from $M_6(\mathbb{F}_2)G$ - Group matrix rings by a hybrid search technique based on a neighbourhood-virus optimisation algorithm. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022032
[8]	Somphong Jitman, San Ling, Ekkasit Sangwisut. On self-dual cyclic codes of length $p^a$ over $GR(p^2,s)$. Advances in Mathematics of Communications, 2016, 10 (2) : 255-273. doi: 10.3934/amc.2016004
[9]	Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79
[10]	Steven T. Dougherty, Cristina Fernández-Córdoba, Roger Ten-Valls, Bahattin Yildiz. Quaternary group ring codes: Ranks, kernels and self-dual codes. Advances in Mathematics of Communications, 2020, 14 (2) : 319-332. doi: 10.3934/amc.2020023
[11]	Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385
[12]	Jamshid Moori, Amin Saeidi. Some designs and codes invariant under the Tits group. Advances in Mathematics of Communications, 2017, 11 (1) : 77-82. doi: 10.3934/amc.2017003
[13]	Cristina García Pillado, Santos González, Victor Markov, Consuelo Martínez, Alexandr Nechaev. New examples of non-abelian group codes. Advances in Mathematics of Communications, 2016, 10 (1) : 1-10. doi: 10.3934/amc.2016.10.1
[14]	Habibul Islam, Om Prakash, Ram Krishna Verma. New quantum codes from constacyclic codes over the ring $ R_{k,m} $. Advances in Mathematics of Communications, 2022, 16 (1) : 17-35. doi: 10.3934/amc.2020097
[15]	Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295
[16]	Crnković Dean, Vedrana Mikulić Crnković, Bernardo G. Rodrigues. On self-orthogonal designs and codes related to Held's simple group. Advances in Mathematics of Communications, 2018, 12 (3) : 607-628. doi: 10.3934/amc.2018036
[17]	Axel Kohnert, Johannes Zwanzger. New linear codes with prescribed group of automorphisms found by heuristic search. Advances in Mathematics of Communications, 2009, 3 (2) : 157-166. doi: 10.3934/amc.2009.3.157
[18]	Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419
[19]	Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021031
[20]	Steven T. Dougherty, Joe Gildea, Adrian Korban, Abidin Kaya. Composite constructions of self-dual codes from group rings and new extremal self-dual binary codes of length 68. Advances in Mathematics of Communications, 2020, 14 (4) : 677-702. doi: 10.3934/amc.2020037

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Ismara Álvarez-Barrientos Mijail Borges-Quintana Miguel Angel Borges-Trenard Daniel Panario
on Google Scholar
Ismara Álvarez-Barrientos Mijail Borges-Quintana Miguel Angel Borges-Trenard Daniel Panario

[Back to Top]