On the complexity of computing syzygies (Q1117693)

\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)].