Echelons of power series and Gabrielov’s counterexample to nested linear Artin Approximation

arXiv:1804.08160v1 [math.AG] 22 Apr 2018 Echelons of power series and Gabrielov’s counterexample to nested linear Artin Approximation M.E. ALONSO, F.J. CASTRO-JIM ´ ENEZ, H. HAUSER, C. KOUTSCHAN (1) Abstract : Gabrielov’s famous example for the failure of analytic Artin approximation in the presence of nested subring conditions is shown to be due to a growth phenomenon in standard basis computations for echelons, a generalization of the concept of ideals in power series rings. Introduction In the S´ eminaire Henri Cartan of 1960/61, Grothendieck posed the question whether analytically independent analytic functions are also formally independent [Gr].(2) It came as a surprise when Gabrielov answered the question in 1971 in the negative. He constructed four analytic functions e, f, g, h in three variables admitting one formal relation but no analytic one [Gb1]. To our knowledge, this is essentially the only known counterexample to Grothendieck’s question. In an opposite direction, Pawłucki constructed analytic functions and a subset Zof the reals for which there do exist analytic relations for parameter values outside Zbut there do not exist formal relations for parameters in Z[Pa1]. In a later paper, Gabrielov gave a sufficient condition for a positive answer to Grothendieck’s question in terms of the rank of the Jacobian matrix of the analytic functions [Gb2], see also [Pa2]. Much more generally, Popescu proved in 1985 a difficult approximation theorem which contains as a particular case a positive answer whenever the analytic functions are algebraic power series [Po1, Po2, Sp, Te]. Gabrielov’s counterexample is based on an example of Osgood [Os] from 1916, complemented by a tricky construction and calculation. The deeper reason for the existence of formal divergent relations between analytically independent analytic functions remained mysterious over the years. In this note we explain the genesis of the phenomenon in Gabrielov’s example and provide a systematic way to construct many more counterexamples: It turns out that the existence of formal but not analytic relations is caused by accumulated growth occurrences in standard basis computations for echelons (an echelon is a generalization of an ideal in a power series ring, see below). Such a growth behaviour is well known for standard bases of ideals, but does not do any harm there due to the finiteness of the basis (which is ensured by the Noetherianity of the power series ring.) Standard bases of echelons need no longer be finite, and the iterated growth occurrence in their construction may indeed force divergence. We illustrate in the paper how this phenomenon is related to the presence of sufficiently fast converging coefficients of the (analytic) input series. In the example, the coefficients converge faster than exponentially. For algebraic power series, the phenomenon does not happen. The echelon standard basis may still be infinite, but the convergence of the coefficients of the involved series seems to be sufficiently slow so as to ensure a positive answer to Grothendieck’s question: whenever there is a formal linear relation respecting the scopes, there is also a convergent one (actually, even an algebraic one). The assertion for Mathematics Subject Classification (2010): 32A05, 13F25, 13P10, 16W60, 14QXX, 14B12. (1) This work was done in part during a Research-in-Teams program at the Erwin-Schr¨ odinger Institute at Vienna, and the special semester on Artin approximation within the Chaire Jean Morlet at CIRM, Luminy-Marseille. M.E.A. was supported by MINECO MTM2014-55565 and UCM , IMI and Grupo 910444, F.J.C.-J. by MTM2013-40455-P and MTM201675024-P, H.H. and C.K. by the Austrian Science Fund FWF, within the projects P-25652 and AI-0038211, respectively P29467-N32 and F5011-N15. (2) Artin attributes in [Ar] Grothendieck’s question to Abhyankar. 1 algebraic series follows for instance from Popescu’s approximation theorem (i.e., the fact that nested approximation holds for algebraic power series), whereas a direct explanation in terms of echelons is still lacking. Our explanation of Gabrielov’s example will be embedded in a short description of the division theorem for power series in the setting of echelons and the related notion of echelon standard basis. This is not mandatory to understand the example but should allow the reader to see its construction in a broader context. Gabrielov’s example The first step towards Grothendieck’s question, and this already appears in [Gb1], is to transcribe the existence of formal or analytic relations to a nested linear Artin approximation problem: Let f1(x),...,fm(x)be convergent power series in variables x= (x1,...,xn)and let r(y1,...,ym)be a (formal or analytic) relation between them, say, r(f1(x),...,fm(x)) = 0. This is equivalent to saying that r(y)belongs to the ideal of the formal, respectively convergent, power series ring C[[x, y]], respectively C{x, y}, generated by the series yi−fi(x), for i= 1,...,m. Therefore there exist power series a1(x, y),...,am(x, y)such that r(y) = m X i=1 ai(x, y)·(yi−fi(x)). Here, the series aiare allowed to depend on both xand y, whereas the series rmust be independent of x. This requirement is known in the context of Artin approximation as a “nested subring condition”. Note that the unknown series rand aiappear linearly in the equation. As an extension of Grothendieck’s question one may then ask more generally whether linear nested Artin approximation holds for analytic functions: Given analytic functions eand f1,...,fmin nvariables x1,...,xnsuch that the linear presentation e(x) = m X i=1 bai(x)·fi(x) holds with formal power series bai(x)depending only on the variables x1,...,xsi, for given si≤n, does there exist a presentation e(x) = m X i=1 ai(x)·fi(x) with analytic functions ai(x)depending on the same sets of variables as bai(x)? Gabrielov also gives a counterexample to this case of linear nested analytic approximation: Consider the series f= 1,g=x·(ez−1), and h=yz −xin three variables x, y, z. He then shows that the convergent series e(x, z) = ∞ X i=1 ∞ X j=0 i! (i+j)! ·xizj+1 admits a presentation e=ba·f+bb·g+bc·h, with formal series ba(x, y),bb(x, y),bc(x, y, z)but that there are no convergent series a(x, y),b(x, y), c(x, y, z)representing ein this way. Setting I=C{x, y} · f+C{x, y} · g+C{x, y, z} · h 2 with completion b I=C[[x, y]] ·f+C[[x, y]] ·g+C[[x, y, z]] ·h, one therefore has the strict inclusion of vector subspaces I(b I∩C{x, y, z}. We will investigate in this note the deeper reason behind this fact. To do so, we collect in the next section the basics about echelons, a generalization of the notion of ideals in power series rings. Subspaces as Iabove are echelons, and their understanding is crucial for explaining Gabrielov’s example. This explanation is presented in the section after the section on echelons. Echelons Let x1,...,xnbe variables and K[[x]] = K[[x1,...,xn]] the ring of formal power series in x1,...,xn over a given field K. If Kis a valued field, we may also consider the subring K{x}=K{x1,...,xn} of convergent power series. The next definitions apply always equally to the convergent case. A finitary echelon is a K-subspace of K[[x]] which can be written as a finite sum I= k X i=1 K[[x1,...,xsi]] ·fi, with series fi∈K[[x1, . . . , xn]] and integers 0≤si≤n, called the assigned scope of fi. Sometimes, we also refer to the variables x1, ..., xsithemselves as the scope of fi. Series f1, ..., fkas above with assigned scopes s1, ..., skare called generators of I. When working with finitary echelons, we often tacitly assume that a generator system is already chosen. A linear combination f=Pk i=1 ai·fiis said to respect the scopes if ai∈K[[x1, ..., xsi]] holds for all i. Each element fof Ican be represented in this way. In certain situations, the sum Pk i=1 K[[x1,...,xsi]] ·fiwill be direct, and then the presentation f=Pk i=1 ai·fiof elements f∈Ias a linear combination of f1, ..., fkrespecting the scopes is unique (compare this with the later analysis of Gabrielov’s example where the involved echelon is indeed a direct sum). One could also develop a concept of infinitely generated echelons, but this is not needed for the sequel, and will hence be omitted here. For f∈I, we call s(f) = max{s∈ {0,...,n}, K[[x1,...,xs]] ·f⊂I}the actual scope of fin I. Clearly, the assigned scope sof fis less than or equal to the actual scope s(f). In a theoretical context, we may always assign the actual scope to f, so that s=s(f), and we then just speak of the scope of an element. But for actual computations and a given f∈I, it seems often impossible to determine the actual scope algorithmically, since it would require a constructive echelon membership test for the multiples of f. This aspect will play a role in Thm. 2, where only assigned scopes are considered. The analogous definitions hold for K-subspaces of free modules K[[x]]mof the form I= k X i=1 K[[x1,...,xsi]] ·fi⊂K[[x]]m, with power series vectors fi∈K[[x1,...,xn]]m. We call such subspaces finitary (module) echelons, with generators fiand assigned scopes si. Let now f1, ..., fkwith scopes s1, ..., skbe given generators of a finitary echelon I⊂K[[x]] (or of a finitary module echelon I⊂K[[x]]m). The (module) echelon of (linear) relations between f1, ..., fk is the K-subspace Rel(f1, ..., fk) = {r∈Qk i=1 K[[x1, ..., xsi]],Prifi= 0} of K[[x]]kconsisting of the linear relations between f1, ..., fkrespecting the scopes si. Here, we assign to a relation r= (r1, ..., rk)the scope t:= min{si, ri6= 0}, so that the inclusion K[[x1, ..., xt]] ·r⊂ Rel(f1, ..., fk)is ensured. 3 Assume that a monomial order <on Nnis chosen, i.e., a total ordering compatible with the addition in Nnand so that 0is the smallest element. It induces an ordering, also denoted by <, on the set of monomials xαof K[[x]],α∈Nn. For f∈K[[x]], we denote by in(f) = in(f) = xαthe smallest monomial with respect to <appearing in the expansion of f(we always take the coefficient equal to 1, and agree that in(0) = 0). It is called the initial monomial of fwith respect to <. For a finitary echelon Iin K[[x]], denote by in(I) = in(I)the associated initial echelon of I: this is the K-subspace of K[[x]] of power series whose expansion only involves monomials which are initial monomials in(f)of elements fof I. It is thus the x-adic closure of the subspace of K[[x]] spanned by all initial monomials of elements of I. In general, in(I)will not be a finitary echelon. For later use we restrict to monomial orders which admit no infinite bounded and strictly increasing sequences (thus, (Nn, <)will be order equivalent to Nwith the usual order). We reserve the symbol (#) for this condition; it would not hold for instance for a lexicographic monomial order on Nn. Assume that we are given generators F={f1,...,fk}of Iwith assigned scopes s1,...,sk∈ {0,...,n}, I=Pk i=1 K[[x1,...,xsi]] ·fi. Our goal is to construct an echelon standard basis of Ifrom f1,...,fk. This is a (possibly infinite) set of elements gjof I,j∈N, with assigned scopes tj, whose initial monomials xαj= in(gj)generate in(I)topologically: in(I) = P∗ j∈NK[[x1,...,xtj]] ·xαj. Here, the symbol P∗stands for infinite sums of elements of the summands K[[x1,...,xtj]] ·xαj, say, power series in K[[x]] whose exponents belong to the set Sj∈Nαj+ (Ntj×0n−tj). Such sums converge in the x-adic topology of K[[x]] since the total degree of the monomials xαjtends with jtowards infinity (here, we exclude wlog repetitions among these monomials). By “construction” we understand a possibly infinite algorithm, which “terminates” in the sense that it produces, for each initial monomial xαof in(I), in finitely many steps an element f∈Itogether with an assigned scope ssuch that xα∈K[[x1,...,xs]] ·in(f). Our algorithm mimicks Buchberger’s algorithm for the construction of Gr¨ obner and/or standard bases of ideals of polynomials, respectively power series [Bu, GP]. We do not, however, divide the new elements after each step by the existing ones. The main difference to the case of ideals is that echelon standard bases are not necessarily finite sets of generators, so that the notion of “termination” of the algorithm has to be drafted properly. See Thm. 2 below for details.(3) Denote by xαithe initial monomials of a finite set F={f1,...,fk}of generators fiwith scope siof I. Set A=Sk i=1 αi+ (Nsi×0n−si)and denote by B=Ac=Nn\Aits complement. Write K[[x]]Bfor the space of power series whose expansions involve only monomials with exponent in B. An echelon power series division of a series f∈K[[x]] by Fwith respect to <is a decomposition f=Pk i=1 aifi+b with quotients ai∈K[[x1, . . . , xsi]], remainder b∈K[[x]]B, and so that in(f−b) = min {in(ai)·in(fi), i = 1,...,k}, (*) (3) In the case of ideals of power series rings, standard bases are finite. If the ideals are generated by algebraic power series (and the coordinates are sufficiently generic), the construction of standard bases can be performed by a finite algorithm, see [ACH]. 4 where the minimum refers to the ordering of the monomials of K[[x]] induced by <. This is the analog requirement as for polynomial division in the case where the divisors, say ideal generators, are not yet (or not necessarily) a Gr¨ obner basis. Note that in general the decomposition is not unique. Theorem 1. (Division theorem for echelons) Let F={f1,...,fk}be a finite set of series fiin K[[x1, ..., xn]] with assigned scopes 0≤si≤n. Choose a monomial order <on Nn. For every series fthere exists an echelon power series division (with respect to <) f=Pk i=1 aifi+b of fby f1,...,fkwith respect to <. Remarks. (a) If f1, ..., fkform an echelon standard basis, the remainder bof the division is unique (whereas the coefficients aistill need not be unique). Uniqueness of bdoes not hold for arbitrary f1, ..., fk. Prescribing support conditions on the coefficients aias in the proof below by choosing a partition A=˙ ∪Aiof the set Aand requiring supp(ai·in(fi)) ⊂Aifor all i, both the coefficients ai and the remainder bcan be made unique (though they will depend on the chosen partition of A). (b) If Iis the echelon generated by f1, ..., fkwith scopes s1, ..., sk, and if we assume that also fbelongs to Iand has assigned scope s, there is a natural way to assign to the remainder b, which then again belongs to I, a scope: namely, define it as the minimum of sand the scopes sifor those i= 1, ..., k for which ai6= 0. This value can either be maximized over all presentations f=Pk i=1 aifi+b(finding the maximum value may not be constructive), or it can be made unique by choosing a partition A=˙ ∪Ai and support conditions on the aiso that the presentation is unique. (c) We can check by Thm. 1 effectively whether an element fbelongs to Iup to degree d, since then we only need a finite part of the echelon standard basis, namely those elements whose initial monomials are not larger than all degree dmonomials. (d) With a little more work (using elementary Banach space techniques), the division statement of the theorem can be established for convergent power series, cf. [HM, Thm. 5.1]. It does not hold in general for algebraic series. (e) The division theorem can also be formulated for vectors of power series and finitary module echelons. Proof. We shall show that the K-linear map u:Qk i=1 K[[x1,...,xsi]] ×K[[x]]Ac→K[[x]], (a1,...,ak, b)→Pk i=1 aifi+b is surjective. Along the way, we shall in addition show that every series f∈K[[x]] has a preimage (a, b)so that the condition in(f−b) = min {in(ai)·in(fi), i = 1,...,k}holds. Write u=v+wwhere vis the “monomial approximation” of ugiven by the initial monomials xαiof f1,...,fk, i.e., where vis the linear map v:Qk i=1 K[[x1,...,xsi]] ×K[[x]]Ac→K[[x]], (a1,...,ak, b)→Pk i=1 aixαi+b. By definition of K[[x]]Ac, the map vis surjective. We shall choose a linear subspace Nof the first factor Qk i=1 K[[x1,...,xsi]] so that the restriction vNof vto N×K[[x]]Acbecomes an isomorphism of K-vectorspaces. Using the inverse of vNwe shall then show that also the restriction uNof uis an isomorphism. From this the surjectivity of ufollows. Our choice of Nwill ensure in addition the requirement (*) in the decomposition f=Pk i=1 aifi+b. To construct N, we proceed as in the classical case of Gr¨ obner or standard bases by defining a suitable partition of the set of exponents A=Sk i=1 αi+(Nsi×0n−si)[Gal, GP, HM]. There is no distinguished 5 choice of the partition of A. Typically, one sets A1=α1+ (Ns1×0n−s1), and then defines Ai= [αi+ (Nsi×0n−si)] \Sj<i Aj. Here its is advisable to order the elements f1, ..., fkby decreasing scope, s1≥...≥sk, in order to exhaust Afirst by larger regions. So let us fix a partition A=˙ ∪Aiof the set A. Denote by Ni=K[[x]]Ai⊂K[[x]] the subspace of series with exponents in Ai, and set N=Qk i=1 Ni. It is then clear that the restriction vNof vto N×K[[x]]Acis an isomorphism of K-vectorspaces. Let v−1 Nbe its inverse. We prove that the restriction uNof uto N×K[[x]]Acis also an isomorphism. For this it is sufficient to show that the composition u◦v−1 N= (v+w)◦v−1 N= IdK[[x]] +w◦v−1 Nis an isomorphism of K[[x]]. The “formal inverse” P∞ i=0(−w◦v−1 N)idefines a linear map from K[[x]] to K[[x]] since applying w◦v−1 Nto a power series h increases its initial monomial with respect to the ordering of the monomials induced by <. It is therefore the inverse to u◦v−1 N. This shows that uN◦v−1 Nand hence also uNare isomorphisms. It follows that the map uis surjective as claimed. It remains to show (*). We clearly have in(f−b)≥min {in(ai)·in(fi), i = 1,...,k}. If strict inequality would hold, the equality f=Pk i=1 aifi+bwould imply, because of b∈K[[x]]Ac, that in(ai)·in(fi) = in(aj)·in(fj)for some pair i6=j. This is impossible since Ai∩Aj=∅. The theorem is proven.  We have already mentioned that echelon standard bases of echelons need no longer be finite. However, the ideas of Buchberger’s algorithm apply as well to construct the elements one by one. This goes as follows. Theorem 2. (Echelon standard bases) Let F={f1,...,fk}be a set of power series with assigned scopes 0≤si≤ngenerating a finitary echelon Iin K[[x1, ..., xn]], I=Pk i=1 K[[x1, ..., xsi]] ·fi. Fix a monomial order <on Nnsatisfying condition (#). There exists an algorithm to enlarge Fiteratively so that, for every monomial xαof the initial echelon in(I)of I, one arrives after finitely many enlargements at a set e Fwhich contains an element fof assigned scope sin I with xα∈K[[x1,...,xs]] ·in(f). Remarks. (a) Said differently, the algorithm produces in finitely many steps the elements of an echelon standard basis of Iup to any prescribed degree. An enlargement of Fis defined as a finite set e F containing Fall whose elements belong again to Iand carry an assigned scope. In the proof, the algorithm for constructing these enlargements will be described explicitly. (b) We do not pretend that the algorithm terminates in the sense that, in the construction of the echelon standard basis, after finitely many steps no more enlargements occur (and, in general, this will not happen). Moreover, even in the case where a finite echelon standard basis exists, the algorithm may produce infinitely many elements (most of which will be redundant). This is due to the fact that we do not apply division after each step. Proof. We first explain the algorithm, and then show the required property. It is a variation of Buchberger’s algorithm in the version of power series, with the additional requirement of respecting in each step the scopes of the involved elements. Choose, for every pair i6=j, the canonical minimal relation (mi, mj)∈K[x]2between the initial terms (i.e., initial monomials taken together with their coefficients) ei·xαiand ej·xαjof fiand fj, where eiand ejdenote the respective coefficients in Kand where miand mjare terms with appropriate coefficients so that mi·ei·xαi+mj·ej·xαj= 0. 6 It is clear that the relations are unique up to multiplication by constants in K. Set S(fi, fj) := mifi+mjfj. These linear combinations of fiand fjsatisfy in(S(fi, fj)) >in(mifi) = in(mjfj), i.e., there occurs a cancellation of (monomial multiples of) the initial monomials of fiand fj. In the algorithm, we will only consider linear combinations gij := S(fi, fj)for which both mi∈ K[x1, ..., xsi]and mj∈K[x1, ..., xsj]respect the assigned scopes of fiand fj. The other S(fi, fj) will be discarded. Observe here that if mior mjviolate the scope condition then all monomial relations between ei·xαiand ej·xαjviolate it. We assign to the elements gij thus obtained the scope sij := min{si, sj}and add them to the set F. This will be done with all pairs (i, j)satisfying the scope condition. The resulting set e Ftogether with the assigned scopes of its elements is considered as the first enlargement of F. We then iterate the procedure with e F. This completes the description of the algorithm.(4) We now show that the algorithm fulfills the assertion of the theorem. Let xαbe a monomial of in(I). We have to prove that, after finitely many enlargements of F, there is an element f∈Fwith assigned scope sin Iso that xα∈K[[x1,...,xs]] ·in(f). We may assume that we have already run the algorithm until arriving at a set F={f1,...,fk}for which all subsequent new initial monomials appearing later in the algorithm are larger than xα. Indeed, in(gij )>in(mifi) = in(mjfj)is strictly larger than the maximum of in(fi)and in(fj). As we don’t reconsider combinations S(fi, fj)taken care of in earlier enlargements, it follows that the new initial monomials appearing after an enlargement are all larger than the minimum of the new initial monomials of the preceding enlargement. We conclude that the sequence of new initial monomials is unbounded. Hence, by hypothesis (#) on the monomial order, the sequence must overtake xaeventually. As xα∈in(I)we may write xα= in(Paifi)for some ai∈K[[x1,...,xsi]] and fi∈F. Set M:= min {in(ai·fi), i = 1,...,k}. Clearly, M≤xα. If M=xαwe are done: There is an iso that xα=M= in(ai)·in(fi), hence xα∈K[[x1,...,xsi]] ·in(fi). If M < xα, we will see that the algorithm enlarges Fto a set e F={f1, ..., fk, fk+1, ..., f˜ k} with assigned scopes sifor fi, and we then construct a presentation f=P˜ k i=1 eaifiof fwith coefficients eai∈K[[x1, ..., xsi]] so that f M:= min {in(eai·fi), i = 1,...,˜ k}>min {in(ai·fi), i = 1,...,k}=M. This procedure is then repeated. By hypothesis (#) on the monomial order, the resulting strictly increasing sequence of monomials M,f M, ... must reach xαafter finitely many iterations. That is what we want to prove. To do so, let Cbe the set of indices iwith in(ai)·in(fi) = M. We necessarily have |C| ≥ 2, since, due to the inequality in(Pk i=1 aifi)>min {in(ai·fi), i = 1,...,k}, a cancellation of (monomial multiples of) initial monomials in(fi) = xαimust occur in the sum Pk i=1 aifi. Let ciand eiin Kdenote the coefficients of the monomials in(ai), respectively in(fi), of ai, respectively fi. It follows that the vector r∈K[x]kwith entries ri=ci·in(ai)if i∈Cand (4) Observe here that in the subsequent enlargements one does not need to reconsider combinations S(fi, fj)of elements fi, fj which have been taken care of earlier. 7 ri= 0 otherwise forms a monomial relation in Qk i=1 K[x1, ..., xsi]between the terms ei·in(fi), for i= 1, ..., k, Pk i=1 ri·ei·in(fi) = Pi∈Cciei·in(ai·fi) = (Pi∈Cciei)·M= 0. For each pair j6=ℓin C, denote by mjℓ ∈K[x]kthe relation vector between the monomials ei·in(fi), i= 1, ..., k, whose only non-zero entries occur for indices jand ℓand are the terms mjand mℓappearing in the minimal monomial relation mj·ej·xαj+mℓ·eℓ·xαℓ= 0 defined earlier in the description of the algorithm, mjℓ = (0, ..., 0, mj,0, ..., 0, mℓ,0, ..., 0) ∈K[x]k. In order not to have to exclude the case j=ℓwe may set all mjj equal to 0. We leave it as a (simple) combinatorial exercise to check that the vectors m′ jℓ ∈K[x]|C|obtained from mjℓ by taking only the components with index in Cform a generator system of the module echelon of relations between the terms ei·in(fi), for i∈C, respecting the scopes. The entry of the vector rat index ibelongs to K[x1, ..., xsi], by the choice of aiin K[[x1, ..., xsi]], and the same holds for mi∈K[x1, ..., xsi]. Now notice that if we have a sum h=Phiwith in(hi) = M for all iand so that in(h)> M then h=Pλjℓ ·S(hj, hℓ)for some λjℓ ∈K. Furthermore, we have in(S(hj, hℓ)) > M for all j, ℓ. In view of this we may therefore write r=Pj,ℓ∈Cbjℓ ·mjℓ, for some coefficients bjℓ which are monomials in K[x1, ..., xsjℓ ], with sjℓ = min{sj, sℓ}as above. In the description of the algorithm we defined elements gjℓ =mjℓ ·(f1, ..., fk) = mjfj+mℓfℓwith assigned scope sjℓ = min{sj, sℓ}(the dot represents the scalar product in K[[x]]k). We enlarge now F to a set e Fby adding all gjℓ, for j, ℓ ∈C. Denote by fjℓ =gjℓ ∈e Fthese new elements, and assign to them the scopes sjℓ := min{sj, sℓ}. We get Pk i=1 rifi=Pj,ℓ∈Cbjℓ(mjfj+mℓfℓ) = Pj,ℓ∈Cbjℓgjℓ =Pj,ℓ∈Cbjℓfjℓ. Decompose all aiinto ai=ci·in(ai) + a′ ifor some a′ i∈K[[x1, ..., xsi]] with in(a′ i)>in(ai). Then f=Pk i=1 aifi=Pi6∈Caifi+Pi∈C(ci·in(ai) + a′ i)fi =Pi6∈Caifi+Pi∈Ca′ ifi+Pk i=1 rifi =Pi6∈Caifi+Pi∈Ca′ ifi+Pj,ℓ∈Cbjℓfjℓ =: Pk i=1 eaifi+Pj,ℓ∈Ceajℓfjℓ, with respective coefficients eai∈K[[x1,...,xsi]] and eajℓ ∈K[[x1,...,xsjℓ ]], where eai:= aifor i6∈ C and eai:= a′ ifor i∈C, and where eajℓ := bjℓ. This is a new presentation of fas a linear combination of elements of our enlarged set e F. The scopes are respected. The first summand in the last line satisfies by definition of Cand a′ ithe inequality min {in(eai)·in(fi), i = 1,...,k}> M = min {in(ai)·in(fi), i = 1,...,k}. As for the second summand, recall that in(fjℓ) = in(gjℓ)>in(mjfj) = in(mℓfℓ)and in(mj) = in(aj) for all j, ℓ ∈C. This implies that also min {in(eajℓ)·in(fjℓ), j, ℓ ∈C}> M. We have found, after the enlargement of Fto e F, a presentation f=Pk i=1 eaifi+Pj,ℓ∈Ceajℓfjℓ of fas a linear combination respecting the scopes of the elements of e Fand with larger value 8 f M:= min {in(eai)·in(fi),in(eajℓ)·in(fjℓ); i= 1,...,k;j, ℓ ∈C}. Repeating the construction we produce by successive enlargements of Fa sequence of monomials M < f M < . . . which eventually attains xα. This is what had to be shown.  Pseudo-code of algorithm of Theorem 2 INPUT: f1,...,fk∈K[[x1,...,xn]] with scopes s1,...,sk∈Z,0≤si≤n, monomial order <on Nn, monomial xα∈in(I), where Iis the echelon generated by f1,...,fk. OUTPUT: enlargement F⊇ {f1,...,fk}such that Fgenerates Iand there is an f∈F for which xα∈K[[x1,...,xs]] ·in(f)holds, where sis the scope of f. 01: ℓ:= k 02: ℓ1:= 0 03: F:= {f1,...,fℓ} 04: while ℓ1< ℓ and ¬∃ 1≤i≤ℓ:xα∈K[[x1,...,xsi]] ·in(fi)do 05: P:= {{i, j}: 1 ≤i < j ≤ℓ∧j > ℓ1} 06: ℓ1:= ℓ 07: for {i, j} ∈ Pdo 08: compute minimal monomial relation (mi, mj)of fiand fj 09: if mi∈K[x1,...,xsi]and mj∈K[x1,...,xsj]then 10: gij := mifi+mjfj 11: if gij 6∈ For max{su:fu=gij}<min {si, sj}then 12: ℓ:= ℓ+ 1 13: fℓ:= gij 14: sℓ:= min {si, sj} 15: F:= F∪ {fℓ} 16: end if 17: end if 18: end do 19: end do 20: return F This algorithm, although it follows closely Buchberger’s algorithm, does not reduce the S-polynomials. If we wanted to include division with remainder into the algorithm, its presentation would become much more complicated, which is related to the determination of the scope of newly added elements. Clearly, the scope of the new element should be the minimum of all scopes of elements that were used in the division. But then, we have to record also intermediate elements in the reduction with maximal possible scope. We illustrate the problem with an example: assume that f1, f2, f3have the scopes s1=s2= 2, and s3= 1. Then we assign to g1,2=m1f1+m2f2the scope 2, but after reducing it with f3, we have to assign scope 1. If we only add the final result (with scope 1) to F, we may hence miss an element of the standard basis of I. For actual computations, this conceptual version of the algorithm may be very inefficient, and therefore, in the next section, we will apply division with remainder to the S-polynomials, since the above-mentioned problem does not occur there. Analysis of Gabrielov’s example We now return to the study of Gabrielov’s example, where f= 1 and g=x·(ez−1) have assigned scope x, y, and where h=yz −xhas assigned scope x, y, z (for clarity, we indicate instead of the value 9