×

Minimal resolutions of lattice ideals and integer linear programming. (English) Zbl 1094.13017

Let \({\mathcal L} \subseteq {\mathbb Z}^n\) be a lattice and \(I_{\mathcal L}\) be the lattice ideal associated with \({\mathcal L}\), i.e. the ideal of the polynomial ring \(k[x] = k[x_1, \dots, x_n]\) generated by the binomials \(x^{u^+}-x^{u^-}, \;u \in {\mathcal L}\) (where \(u = {u^+} - {u^-}\), \({u^+}, {u^-} \in {\mathbb N}^n\) with disjoint support). The authors show in which way the construction of the minimal free resolution of \(k[x_1, \dots, x_n]/I_{\mathcal L}\) is connected with integer linear programming. The key point is the computation of the non null reduced homology spaces of some simplicial complexes.
Most of the results of the paper are obtained collecting the results already present in the vast literature on the subject; in this sense the paper is mostly a survey article.

MSC:

13D02 Syzygies, resolutions, complexes and commutative rings
14M25 Toric varieties, Newton polyhedra, Okounkov bodies
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation

Software:

GRIN
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Aramova, A. and Herzog, J.: Free resolution and Koszul homology. J. of Pure Appl. Algebra 105 (1995), no. 1, 1-16. · Zbl 0844.13011
[2] Bayer, D., Peeva, I. and Sturmfels, B.: Monomial resolutions. Math. Res. Lett. 5, (1998), no. 1-2, 31-46. · Zbl 0909.13010
[3] Bayer, D., Popescu, S. and Sturmfels, B.: Syzygies of unimodular Lawrence ideals. J. Reine Angew. Math. 534 (2001), 169-186. · Zbl 1011.13006
[4] Bayer, D. and Stillman, M.: A criterion for detecting m-regularity. Invent. Math. 87 (1987), no. 1, 1-11. · Zbl 0625.13003
[5] Bayer, D. and Sturmfels, B.: Cellular resolutions of monomial mod- ules. J. Reine Angew. Math. 502 (1998), 123-140. · Zbl 0909.13011
[6] Bresinsky, H.: Binomial generating sets for monomial curves, with ap- plications in A4. Rend. Sem. Mat. Univ. Politec. Torino 46 (1998), no. 3, 353-370 (1990). · Zbl 0738.14017
[7] Briales, E., Campillo, A., Marijuán, C. and Pisón, P.: Combina- torics of syzygies for semigroup algebras. Collect. Math. 49, (1998), no. 2-3, 239-256. · Zbl 0929.13007
[8] Briales, E., Campillo, A., Marijuán, C. and Pisón, P.: Minimal systems of generators for ideals of semigroups. J. Pure Appl. Algebra 124 (1998), no. 1-3, 7-30. · Zbl 0913.20036
[9] Briales, E., Campillo, A. and Pisón, P.: On the equations defining toric projective varieties. In Geometric and Combinatorial Aspects of Com- mutative Algebra (Messina, 1999), 57-66. Lecture Notes in Pure and Appl. Math. 217, Dekker, New York, 2001. · Zbl 1044.14027
[10] Briales, E., Campillo, A., Pisón, P. and Vigneron, A.: Simplicial complexes and syzygies of lattice ideals. In Symbolic Computation: Solv- ing Equations in Algebra, Geometry and Engineering, 169-183, Contemp. Math. 286, Amer. Math. Soc., Providence, RI, 2001. · Zbl 1093.13507
[11] Briales, E., Pisón, P. and Vigneron, A.: Cotas para la Regularidad de un Ideal de Retículo. In Actas del Encuentro de Matemáticos Andaluces, 171-178. Servicio de publicaciones de la Univ. de Sevilla, 2002.
[12] Briales, E., Pisón, P. and Vigneron, A.: The Regularity of a Toric Variety. J. Algebra 237 (2001), no. 1, 165-185. · Zbl 1042.14024
[13] Campillo, A. and Giménez, P.: Syzygies of affine toric varieties. J. Al- gebra 225 (2000), no. 1, 142-161. · Zbl 0973.14027
[14] Campillo, A. and Marijuán, C.: Higher order relations for a numerical semigroup. Sém. Théor. Nombres Bordeaux (2) 3 (1991), no. 2, 249-260. · Zbl 0818.20078
[15] Campillo, A. and Pisón, P.: Generators of a monomial curve and graphs for the associated semigroup. Bull. Soc. Math. Belg. Sér. A 45 (1993), no. 1-2, 45-58. · Zbl 0802.14014
[16] Campillo, A. and Pisón, P.: L’idéal d’un semi-groupe de type fini. C. R. Acad. Sci. Paris Sér. I Math. 316 (1993), no. 12, 1303-1306. E. Briales, A. Campillo, P. Pisón and A. Vigneron · Zbl 0816.20050
[17] Campillo, A. and Pisón, P.: Toric Mathematics from semigroup view- point. In Ring Theory and Algebraic Geometry, 95-112. Lectures Notes in Pure and Applied Mathematics 221, Dekker, New York, 2001. · Zbl 1044.20039
[18] Clausen, M. and Fortenbacher, A.: Efficient solution of linear Dio- phantine equations. J. Symbolic Comput. 8 (1989), no. 1-2, 201-216. · Zbl 0674.10011
[19] Conti, P. and Traverso, C.: Buchberger algorithm and integer pro- gramming. In Applied algebra, algebraic algorithms and error-correcting codes, New Orleans, LA, 1991, 130-139. Lecture Notes in Comput. Sci., 539, Springer, Berlin, 1991. · Zbl 0771.13014
[20] Contejean, E. and Devie, H.: An efficient incremental algorithm for solving systems of linear Diophantine equations. Inform. and Comput. 113 (1994), no. 1, 143-172. · Zbl 0809.11015
[21] Cox, D.: Recent developments in toric geometry. In Algebraic geometry (Santa Cruz, 1995), 389-436. Proc. Sympos. Pure Math. 62, Part 2. Amer. Math. Soc., Providence, RI, 1997. · Zbl 0899.14025
[22] Di Biase, F. and Urbanke, R.: An algorithm to calculate the kernel of certain polynomial ring homomorphisms. Experiment. Math. 4 (1995), no. 3, 227-234. · Zbl 0860.68062
[23] Domenjoud, E.: Outils pour la Déduction Automatique dans les Théories Associatives-Commutatives. Thése de doctorat d’Université, Université de Nancy I, 1991.
[24] Eisenbud, D. and Goto, S.: Linear free resolutions and minimal multi- plicity. J. Algebra 88 (1984), no. 1, 89-133. · Zbl 0531.13015
[25] Eisenbud, D. and Sturmfels, B.: Binomial ideals. Duke Math. J. 84 (1996), no. 1, 1-45. · Zbl 0873.13021
[26] Fulton, W.: Introduction to Toric Varieties. Annals of Mathematics Stud- ies 131. Princeton University Press, Princeton, 1993.
[27] Gelfand, I. Kapranov, M. and Zelevinsky, A.: Discriminants, resul- tants, and multidimensional determinants. Mathematics: Theory & Appli- cations, Birkhäuser, Boston, Inc., Boston, MA, 1994.
[28] Graver, J. E.: On the foundations of linear and integer linear program- ming I. Math. Programming 9 (1975), no. 2, 207-226. · Zbl 0323.90035
[29] Herzog, J.: Generators and relations of abelian semigroups and semigroup rings. Manuscripta Math. 3 (1970), 175-193. · Zbl 0211.33801
[30] Hochster, M.: Cohen-Macaulay rings, combinatorics, and simplicial com- plexes. In Ring theory, II (Proc. Second Conf., Univ. Oklahoma, Norman, Okla., 1975), 171-223. Lect. Notes in Pure and Appl. Math. 26, Dekker, New York, 1977. · Zbl 0351.13009
[31] Hosten, S. and Sturmfels, B.: GRIN: an implementation of Gröbner bases for integer programming. In Integer programming and combinatorial optimization (Copenhagen, 1995), 267-276. Lecture Notes in Comput. Sci. 920, Springer, Berlin, 1995. 305
[32] Kunz, E.: The value-semigroup of a one-dimensional Gorenstein ring. Proc. Amer. Math. Soc. 25 (1970), 748-751. · Zbl 0197.31401
[33] La Scala, R. and Stillman, M.: Strategies for computing minimal free resolutions. J. Symbolic Comput. 26 (1998), no. 4, 409-431. · Zbl 1034.68716
[34] Ojeda, I. and Piedra, R.: Cellular binomial ideals. Primary decompo- sition of binomial ideals. J. Symbolic Comput. 30 (2000), no. 4, 383-400. · Zbl 0991.13008
[35] Ojeda, I. and Piedra, R.: Index of nilpotency of binomial ideals. J. Algebra 255 (2002), no. 1, 135-147. · Zbl 1079.13508
[36] Ojeda, I. and Pisón, P.: The hull resolution of a monomial curve in A3(k). Prepublicaciones del Departamento de Álgebra de la Universidad de Sevilla 12, 2001.
[37] Papadimitriou, C. H.: On the complexity of integer programming. J. Assoc. Comput. Mach. 28 (1981), no. 4, 765-768. · Zbl 0468.68050
[38] Peeva, I. and Sturmfels, B.: Generic lattice ideals. J. Amer. Math. Soc. 11 (1998), no. 2, 363-373. · Zbl 0905.13005
[39] Peeva, I. and Sturmfels, B.: Syzygies of codimension 2 lattice ideals. Math. Z. 229 (1998), no. 1, 163-194. · Zbl 0918.13006
[40] Pisón, P.: Métodos combinatorios en Álgebra local y Curvas monomiales en dimensión 4. Doctoral thesis, Universidad de Sevilla, 1991.
[41] Pisón, P.: The short resolution of a lattice ideal. Proc. Amer. Math. Soc., to appear. · Zbl 1038.13009
[42] Pisón-Casares, P. and Vigneron-Tenorio, A.: Computing Toric First Syzygies. International Conference IMACS-ACA, El Escorial, Madrid, Spain, 1999. · Zbl 1082.13510
[43] Pisón-Casares, P. and Vigneron-Tenorio, A.: First syzygies of toric varieties and Diophantine equations in congruence. Comm. Algebra 29 (2001), no. 4, 1445-1466. · Zbl 1082.13510
[44] Pisón-Casares, P. and Vigneron-Tenorio, A.: N-solutions to lin- ear systems over Z. Prepublicación de la Universidad de Sevilla, Sección Álgebra 43, 1998. · Zbl 1126.13020
[45] Pisón-Casares, P. and Vigneron-Tenorio, A.: On the Graver Bases of Semigroup Ideals. Prepublicaciones del Departamento de Álgebra de la Universidad de Sevilla 10 (2001), 1-12, preprint. · Zbl 1082.13510
[46] Pottier, L.: Minimal solutions of linear diophantine systems: bounds and algorithms. In Rewriting techniques and applications (Como, 1991), 162-173. Lectures Notes in Comput. Sci. 488, Springer, Berlin, 1991.
[47] Rosales, J. C.: Semigrupos numéricos. Doctoral thesis, Universidad de Granada, 1991.
[48] Stanley, R.: Combinatorics and commutative algebra, second edition. Progress in Mathematics 41. Birkhäuser, Boston-Basel-Berlin, 1996. · Zbl 0838.13008
[49] Sturmfels, B.: Equations defining toric varieties. In Algebraic geometry (Santa Cruz, 1995), 437-449. Proc. Sympos. Pure Math. 62 Part 2, Amer. Math. Soc., Providence, RI, 1997. E. Briales, A. Campillo, P. Pisón and A. Vigneron · Zbl 0914.14022
[50] Sturmfels, B.: Gröbner Bases and Convex Polytopes. University Lectures Series 8, American Mathematical Society, Providence, RI, 1995. · Zbl 0856.13020
[51] Sturmfels, B.: Gröbner bases of Toric Varieties. Tohoku Math. J. (2) 43 (1991), no. 2, 249-261. · Zbl 0714.14034
[52] Vigneron-Tenorio, A.: Semigroup ideals and linear Diophantine equa- tions. Linear Algebra Appl. 295 (1999), no. 1-3, 133-144. · Zbl 0939.20061
[53] Vigneron-Tenorio, A.: Álgebras de Semigrupos y Aplicaciones. Doc- toral thesis, Universidad de Sevilla, 2000.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.