Groebner basis under composition. I (Q1264469)

The paper under review is the first of two papers in which the author investigates the following question. Let \(F\) be a finite set of polynomials in the variables \(x_1,\dots,x_n\) and let \(G\) be a Gröbner basis of the ideal generated by \(F\) under some term ordering \(>\). Let \(\Theta \) be a list of \(n\) polynomials \(\theta_1, \dots, \theta_n\). Let \(F^*\), resp. \(G^*\), be the set of polynomials obtained from \(F\) by replacing the variable \(x_i\) in all polynomials in \(F\), resp. \(G\), by the polynomial \(\theta_i\). When is \(G^*\) a Gröbner basis for the ideal generated by \(F^*\) under the same term ordering? If \(f\) is a polynomial, then denote by \(f(\Theta)\) the polynomial obtained from \(f\) by replacing \(x_i\) with \(\theta_i\) in the terms of \(f\). The main result of the paper is that the answer to this question is affirmative if and only if the following two conditions are satisfied: For all terms \(p,q\) (1) if \(p>q\), the leading term of \(p(\Theta)\) is larger than the leading term of \(q(\Theta)\); (2) if \(p\) does not divide \(q\), then the leading term of \(p(\Theta)\) does not divide the leading term of \(q(\Theta)\). An example for which this phenomenon occurs is when \(\theta_i\) is a power of \(x_i\). [For part II of this paper see: Proc. 1996 int. Symp. symbolic and algebraic computation, ISSAC '96, Zürich 1996, 79-85 (1996; see the following review)].