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

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

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.
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.  Google Scholar

[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.   Google Scholar

[3]

A. H. Banihashemi and I. F. Blake, Trellis complexity and minimal trellis diagrams of lattices,, IEEE Trans. Inform. Theory, 44 (1998), 1829.  doi: 10.1109/18.705562.  Google Scholar

[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.  doi: 10.1109/18.910592.  Google Scholar

[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., (2007), 17.   Google Scholar

[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.  doi: 10.1080/09720529.2007.10698114.  Google Scholar

[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.  doi: 10.1007/s00200-008-0080-2.  Google Scholar

[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.  doi: 10.1006/jsco.1999.0415.  Google Scholar

[9]

B. Buchberger, An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-dimensional Ideal (in German),, Ph.D. thesis, (1965).   Google Scholar

[10]

B. Buchberger and H. M. Möller, The construction of multivariate polynomials with preassigned zeros,, in EUROCAM'82, (1982), 24.   Google Scholar

[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.  doi: 10.1006/jsco.1993.1051.  Google Scholar

[12]

The GAP Group, GAP-Groups, Algorithms, and Programming,, available online at , ().   Google Scholar

[13]

S. Lundqvist, Complexity of comparing monomials and two improvements of the BM-algorithm,, in Math. Methods Computer Science, (2008), 105.  doi: 10.1007/978-3-540-89994-5_9.  Google Scholar

[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.  doi: 10.3934/amc.2011.5.233.  Google Scholar

[15]

T. Mora, Solving Polynomial Equation Systems II: Macaulay's Paradigm and Gröbner Technology,, Cambridge Univ. Press, (2005).  doi: 10.1017/CBO9781107340954.  Google Scholar

[16]

T. Mora, The FGLM problem and Möller's algorithm on zero-dimensional ideals,, in Gröbner, (2009), 379.   Google Scholar

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.  Google Scholar

[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.   Google Scholar

[3]

A. H. Banihashemi and I. F. Blake, Trellis complexity and minimal trellis diagrams of lattices,, IEEE Trans. Inform. Theory, 44 (1998), 1829.  doi: 10.1109/18.705562.  Google Scholar

[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.  doi: 10.1109/18.910592.  Google Scholar

[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., (2007), 17.   Google Scholar

[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.  doi: 10.1080/09720529.2007.10698114.  Google Scholar

[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.  doi: 10.1007/s00200-008-0080-2.  Google Scholar

[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.  doi: 10.1006/jsco.1999.0415.  Google Scholar

[9]

B. Buchberger, An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-dimensional Ideal (in German),, Ph.D. thesis, (1965).   Google Scholar

[10]

B. Buchberger and H. M. Möller, The construction of multivariate polynomials with preassigned zeros,, in EUROCAM'82, (1982), 24.   Google Scholar

[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.  doi: 10.1006/jsco.1993.1051.  Google Scholar

[12]

The GAP Group, GAP-Groups, Algorithms, and Programming,, available online at , ().   Google Scholar

[13]

S. Lundqvist, Complexity of comparing monomials and two improvements of the BM-algorithm,, in Math. Methods Computer Science, (2008), 105.  doi: 10.1007/978-3-540-89994-5_9.  Google Scholar

[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.  doi: 10.3934/amc.2011.5.233.  Google Scholar

[15]

T. Mora, Solving Polynomial Equation Systems II: Macaulay's Paradigm and Gröbner Technology,, Cambridge Univ. Press, (2005).  doi: 10.1017/CBO9781107340954.  Google Scholar

[16]

T. Mora, The FGLM problem and Möller's algorithm on zero-dimensional ideals,, in Gröbner, (2009), 379.   Google Scholar

[1]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[2]

Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020464

[3]

Qiao Liu. Local rigidity of certain solvable group actions on tori. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 553-567. doi: 10.3934/dcds.2020269

[4]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[5]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108

[6]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[7]

Chandra Shekhar, Amit Kumar, Shreekant Varshney, Sherif Ibrahim Ammar. $ \bf{M/G/1} $ fault-tolerant machining system with imperfection. Journal of Industrial & Management Optimization, 2021, 17 (1) : 1-28. doi: 10.3934/jimo.2019096

[8]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[9]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

[Back to Top]