A single exponential time algorithm for homogeneous regular sequence tests (Q6601873)

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.