A single exponential time algorithm for homogeneous regular sequence tests

DOI10.1142/S0219498824501457MaRDI QIDQ6601873zbMATH OpenFDO

Authors Amir Hashemi, Benyamin M.-Alizadeh, Hossein Parnian, Werner M. Seiler

Publication date 11 September 2024

Published in Journal of Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0219498824501457

zbMATH Keywords

\(F_5\) algorithmcomplexity analysisdegree upper boundsGröbner basesHilbert serieshomogeneous polynomialspolynomial idealsregular sequences

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Symbolic computation and algebraic computation (68W30)

Review text

Assume that \(R=K[x_1, \ldots, x_n]\) is a polynomial ring over an infinite field \(K\) and \(F :=f_1, \ldots, f_k\) a sequence of homogeneous polynomials of degree at most \(d\). Also, we assume \(I\) is the ideal generated by \(F\). The main aim of this work is to give an effective approach to examine (within the arithmetic complexity \(d^{O(n)}\)) whether \(F\) is regular. Historically, \textit{J.-C. Faugère} [in: Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC 2002, Lille, France, July 07--10, 2002. New York, NY: ACM Press. 75--83 (2002; Zbl 1072.68664)] presented his well-known \(F_5\) algorithm according to an incremental and signature-based structure to compute Gröbner bases. The authors of this paper accomplished their algorithm in Maple and compared its efficiency with the \(F_5\) algorithm by a set of benchmark polynomials. \N\NAfter that, in order to express an application of this result, they proved that (within the complexity \(d^{O(n^2)}\)), one can transform an ideal \(I\) into Noether position (with the complexity \((kd^n)^{O(n)}).\) Ultimately, the authors argued on the degree upper bounds for the reduced Gröbner basis of an ideal generated by a regular sequence such that in the case that \(F\) is a regular sequence and \(n > k\), then the upper bound \(2(d^k/2)^{2^{n-k-1}}\) holds true for the maximum degree of the elements of any reduced Gröbner basis of \(I\), which states that in the special case when \(F\) is a regular sequence, the second term in the Mayr-Ritscher bound can be removed.

Recommendations

• Bounded regularity
• On the existence of homogeneous semi-regular sequences in \(\mathbb{F}_2[X_1,\ldots,X_n]/(X_1^2,\ldots,X_n^2)\)
• scientific article; zbMATH DE number 4214184
• Polynomial complexity for Hilbert series of Borel type ideals
• scientific article; zbMATH DE number 177861

Cites work

• A course in commutative algebra
• A new framework for computing Gröbner bases
• A Singular Introduction to Commutative Algebra
• A survey on signature-based algorithms for computing Gröbner bases
• Algèbre linéaire sur $K[X_1,\dots,X_n]$ et élimination
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Combinatorial dimension theory of algebraic varieties
• Computation of Macaulay constants and degree bounds for Gröbner bases
• Computing the Castelnuovo-Mumford regularity of some subschemes of \(\mathbb{P}_K^n\) using quotients of monomial ideals
• Definability and fast quantifier elimination in algebraically closed fields
• Deterministic genericity for polynomial ideals
• Dimension and depth dependent upper bounds in polynomial ideal theory
• Dimension-dependent bounds for Gröbner bases of polynomial ideals
• Dimension-dependent upper bounds for Gröbner bases
• scientific article; zbMATH DE number 3857249 (Why is no real title available?)
• scientific article; zbMATH DE number 3973001 (Why is no real title available?)
• scientific article; zbMATH DE number 482758 (Why is no real title available?)
• scientific article; zbMATH DE number 503187 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 1131487 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• scientific article; zbMATH DE number 217454 (Why is no real title available?)
• scientific article; zbMATH DE number 806915 (Why is no real title available?)
• scientific article; zbMATH DE number 2206382 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Involution. The formal theory of differential equations and its applications in computer algebra
• On an installation of Buchberger's algorithm
• On the affine Bezout inequality
• On the complexity of the \(F_5\) Gröbner basis algorithm
• Powers of tensors and fast matrix multiplication
• Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving
• Some formulae in eliminations.
• The algebraic theory of modular systems.
• The complexity of the word problems for commutative semigroups and polynomial ideals
• The Projective Noether Maple Package: Computing the dimension of a projective variety
• The Structure of Polynomial Ideals and Gröbner Bases

Cited in

(1)

• Cohen-Macaulay, Gorenstein and complete intersection conditions by marked bases

This page was built for publication: A single exponential time algorithm for homogeneous regular sequence tests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6601873)