Dimension-dependent bounds for Gröbner bases of polynomial ideals
type: Item
instance of: scholarly article
title: Dimension-dependent bounds for Gröbner bases of polynomial ideals
zbMATH Open document ID: 1258.13032
author: Ernst W. Mayr
author: Stephan Ritscher
published in: Journal of Symbolic Computation
publication date: 2013-01-10T00:00:00Z
review text: Let \(\mathbb{K}\) be an infinite field, \(\mathbb{K}[x_{1},\dots, x_{n}]\) an algebra of polynomials in \(n\) indeterminates over \(\mathbb{K}\), and \(I\) a proper ideal of \(\mathbb{K}[x_{1},\dots, x_{n}]\) of dimension \(r\) generated by a set of polynomials \(F = \{f_{1},\dots, f_{s}\}\) of degrees \(d_{1}\geq\dots\geq d_{s}\). The authors obtain the following bounds for the degree \(\deg(G)\) of the reduced Gröbner basis \(G\) of \(I\): 1) If the polynomials \(f_{1},\dots, f_{s}\) are homogeneous, then for any monomial ordering, \(\deg(G)\leq 2\left[\frac{1}{2}(d_{1}\dots d_{n-r} + d_{1})\right]^{2^{r-1}}\) (Theorem 33). 2) If \(f_{1},\dots, f_{s}\) are arbitrary polynomials, then for any monomial ordering, \[ \deg(G)\leq 2\left[{\frac{1}{2}}(d_{1}\dots d_{n-r})^{2(n-r)} + d_{1})\right]^{2^{r}} \text{ (Theorem 36).} \] Considering the problem of the lower degree bound, the authors prove that there are a monomial ordering and a family of ideals \(I_{r,n}\subseteq \mathbb{K}[x_{1},\dots, x_{n}]\) of dimension at most \(r\) for \(r, n\in \mathbb{N}\) with \(r\leq n\), which are generated by \(O(n)\) polynomials \(F_{r,n}\) of degrees bounded by \(d\) such that the degrees of the corresponding Gröbner bases \(G_{r,n}\) satisfy the condition \(\deg(G_{r,n})\geq d^{(n-r)2^{(1/2 - \epsilon)r}}\) for any \(\epsilon > 0\) and sufficiently large \(d, r\in \mathbb{N}\) (Theorem 38).
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 13M10
Mathematics Subject Classification ID: 13F20
Mathematics Subject Classification ID: 13C15
zbMATH DE Number: 6124215
zbMATH Keywords: Gröbner basis
zbMATH Keywords: degree bound
zbMATH Keywords: cone decomposition
zbMATH Keywords: polynomial ideal
zbMATH Keywords: ideal dimension
zbMATH Keywords: regular sequence
reviewed by: Alexander B. Levin
MaRDI profile type: Publication
full work available at URL: j.jsc.2011.12.018
OpenAlex ID: W2025513431
DOI: 10.1016/J.JSC.2011.12.018
Recommended article: Degree bounds for Gröbner bases of low-dimensional polynomial ideals
Recommended article: Dimension-Dependent Upper Bounds for Gröbner Bases
Recommended article: Dimension and depth dependent upper bounds in polynomial ideal theory
Recommended article: The Structure of Polynomial Ideals and Gröbner Bases
Recommended article: Q4295434
Recommended article: The Gröbner basis of the ideal of vanishing polynomials
Recommended article: Gröbner bases of certain determinantal ideals
Recommended article: Q4440634
Recommended article: Q3568025
description: scientific article; zbMATH DE number 6124215