On the complexity of computing syzygies
type: Item
instance of: scholarly article
title: On the complexity of computing syzygies
zbMATH Open document ID: 0667.68053
DOI: 10.1016/S0747-7171(88)80039-7
author: Dave Bayer
author: Mike Stillman
published in: Journal of Symbolic Computation
publication date: 1988-01-01T00:00:00Z
review text: \textit{G. Hermann} [Math. Ann. 95, 736-788 (1926)] gave an upper bound, double exponential in the number of variables, for the degrees of polynomials occuring in the minimal syzygies of a polynomial ideal. Here it is shown that this estimate cannot be improved and hence the complexity of computing syzygies is also double exponential. The result is obtained by a construction extending that of \textit{E. W. Mayr} and \textit{A. R. Meyer} [Adv. Math. 46, 305-329 (1982; Zbl 0506.03007)].
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 13B25
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 13F20
zbMATH DE Number: 4092768
zbMATH Keywords: computer algebra exponential complexity
zbMATH Keywords: polynomial ideal
zbMATH Keywords: syzygies
Wikidata QID: Q102119303
reviewed by: S. V. Duzhin
MaRDI profile type: Publication
cites work: Bounds for the degrees in the Nullstellensatz
cites work: Linear free resolutions and minimal multiplicity
cites work: On a theorem of Castelnuovo, and the equations defining space curves
cites work: Fields of large transcendence degree generated by values of elliptic functions
cites work: The complexity of the word problems for commutative semigroups and polynomial ideals
cites work: Lectures on Curves on an Algebraic Surface. (AM-59)
cites work: A Castelnuovo bound for smooth surfaces
cites work: Constructions in Algebra
description: scientific article; zbMATH DE number 4092768