Computing bases of complete intersection rings in Noether position (Q5946450)

Assume that \(k\) is an effective infinite perfect field. The aim of the paper is to compute bases of certain free modules over the ring of polynomials \(k[x_1,\dots, x_n]\) and to give a uniform setting to the solution of the problems (which, in some cases, can already be found in the literature). Among the results of the paper we have: Let \(F\) be an \(M \times M\) matrix with polynomial entries such that \(F^2=F\) (i.e. \(F\) is a linear projection), assume that the degrees of the entries of \(F\) are bounded by an integer \(D\) and are given by a straight-line program of size \(L\). Then there exists a well parallelizable algorithm which computes (in sequential time \((nL)^{O(1)}(MD)^{O(n)})\) two subsets of \(k[x_1,\dots,x_n]^M\): \(\{v_1,\dots,v_s\}\) and \(\{v_{s+1}, \dots,v_M\}\) such that: (1) \(\{v_1,\dots,v_M\}\) is a basis of \(k[x_1,\dots,x_n]^M\); (2) \(\{v_1,\dots,v_s\}\) is a basis of \(\text{Im}(F)\) and \(\{v_{s+1},\dots,v_M\}\) is a basis of \(\text{Ker}(F)\). Moreover the entries of \(v_1,\dots,v_M\) are bounded in degree by \((MD)^{O(n)}\). Furthermore, given a finitely generated module \(P\) over the polynomial ring, the authors show that there exists a single exponential algorithm which decides if \(P\) is free and in the affirmative case, computes a free basis of it. The above result can be used to compute bases for complete intersection rings in Noether position. More precisely: Let \(f_1,\dots, f_{n-r} \in k[x_1,\dots,x_n]\) be a regular sequence of polynomials of degrees bounded by an integer \(d\) and given by a straight-line program of size \(l\), such that the canonical morphism \( k[x_1,\dots,x_r] \rightarrow S:=k[x_1,\dots,x_n]/( f_1,\dots,f_{n-r})\) is injective and integral, then there exists a single exponential algorithm which computes a basis of \(S\) as a free \( k[x_1,\dots,x_r]\)-module. The proposed algorithm is well parallelizable.