ENCODING ALGEBRAIC POWER SERIES

arXiv:1403.4104v1 [math.AC] 17 Mar 2014

M.E. ALONSO, F.J. CASTRO-JIMÉNEZ, H. HAUSER

Abstract: The division algorithm for ideals of algebraic power series
satisfying Hironaka’s box condition is shown to be finite when expressed
suitably in terms of the defining polynomial codes of the series. In
particular, the codes of the reduced standard basis of the ideal can be
constructed effectively.

1. Introduction
Let H : An+p
→ ApK be a polynomial map between affine spaces over a field K. Assume
K
that H satisfies at 0 the assumption of the implicit function theorem,
∂y H(0, 0) ∈ Glp (K) and H(0, 0) = 0,

where y = (y1 , . . . , yp ) denote coordinates on ApK . Then there is a unique formal power
series solution h = (h1 , . . . , hp ) of the system H(x, y) = 0 at 0, say
H(x, h(x)) = 0 and h(0) = 0.
Actually, the components hi are algebraic power series in the sense that each hi satisfies
a univariate polynomial equation over the polynomial ring K[x1 , . . . , xn ]. Conversely, any
algebraic power series h1 arises in this way: There is a system of polynomial equations
H(x, y) = 0 satisfying the assumption of the implicit function theorem so that the unique
solution h has first component h1 . This is known as the Artin-Mazur theorem [AM, AMR,
BCR]. The characterization allows one to encode algebraic power series by a polynomial
vector H ∈ K[x, y]p as above. The advantage of this code in comparison with taking the
minimal polynomial lies in the fact that the latter determines the algebraic series only up to
conjugation, so that extra information is necessary to specify the series, typically a sufficiently
high truncation of the Taylor expansion. In contrast, the polynomial code H determines the
series h1 completely and is easy to handle algebraically.
Phrased more abstractly, the henselization of the localization of K[x1 , . . . , xn ] at the maximal
ideal (x1 , . . . , xn ) can be realized as the direct limit of finite étale extensions [Ar1, Na1, BCR,
BrK]. Any element h of the henselization, i.e., any algebraic power series, therefore belongs
to such an extension – which, by definition, can be described by a code as above.
It is then natural to ask to what extent operations with algebraic power series can be expressed
in terms of their code; and, if this is the case for a certain operation, what will be the respective
formulation of the operation in terms of the code.
In the present article we answer this question for the division of algebraic power series and for
the construction of reduced standard bases of ideals. When just considered for formal power
series, the division is an infinite algorithm in the infinitely many coefficients of the series. If
the involved series are algebraic and satisfy Hironaka’s box condition (to be defined below,
see section 3), Lafon in the principal ideal case and Hironaka in general have shown that the
remainder of the division is again an algebraic series [Lf, Hi1], cf. also [BCR, Thm. 8.2.9, p.
169]. As a consequence, the reduced standard basis of the ideal is also formed by algebraic
series. This fact was used for instance by Hironaka in order to construct idealistic exponents
M.A. acknowledges support from MEC, 2011-22435, and UCM, Grupo 910444; F.C.-J. from MTM2010-19336 and Feder; H.H. from the Austrian Science Fund FWF, projects P-21461 and P-25652.

1

of singularities on étale neighborhoods and to control the behaviour of the local resolution
invariant ν ∗ under blowup [Hi1, Hi2, chap. III].
The beforementioned box condition is the natural extension to the case of ideals of the notion
of xn -regularity of a series. It postulates the existence of a specific Rees decomposition –
namely one which is generated by monomials in an appropriate coordinate system – of the
quotient module of the power series ring factored by the given ideal, cf. [Re] and section 2.
Algorithms to determine Rees decompositions have been proposed by Sturmfels-White [SW].
They rely on the construction of (not necessarily reduced) standard bases.
Starting with a system of algebraic generators of an ideal with box condition it is not at all
clear how to construct, from the polynomial codes of the generators, the codes of the algebraic
series defining the reduced standard basis, or, respectively, the codes of the quotients and the
remainder of the division of a given algebraic series by the ideal. This question will be the
subject of the article.
We prove that there does exist a finite algorithm which computes the codes of the reduced
standard basis, respectively of the quotient and the remainder series of a division, from the
codes of the algebraic input series. For the principal ideal case, i.e., the Weierstrass division,
such an algorithm has been proposed and proven to work by Alonso-Mora-Raimondo [AMR].
This algorithm is already quite complicated. The general case, i.e., the division of one series
by several series, is substantially more intricate and resisted for a long time.
In this paper we will present a complete answer to the problem, describing explicitly how to
manipulate the codes of algebraic power series in order to perform the division in general.
This, of course, reproves Lafon’s and Hironaka’s existential results on division, but it goes
far beyond: It provides a quite precise manual of how to express algebraic operations with
algebraic power series in terms of their codes. This is by no means trivial, and the resulting
algorithm, when carried out in a concrete example, turns out to have high complexity (we
give one explicit computation in the appendix). So for practical purposes the algorithm is of
no big use.
But taken from a logical or operational point of view, the algorithm is very interesting. It is
built on two simultaneous inductions, both on the number of variables, which resemble the
induction which appears in the proof of the Artin approximation theorem [Ar2]. Coordinates
in the affine space and generators of the ideals have to be chosen very carefully so as to make
the argument work. But once this is done appropriately, the proofs develop quite naturally and
are almost straightforward. In this sense, we are not only able to codify algebraic power series
– we know and understand how this codification mimics their manipulation in the division
process.
Behind the curtain, there resides a finiteness principle which is ubiquituous in algebraic geometry and commutative algebra: The Noether normalization lemma, or, phrased differently,
the finiteness of certain morphisms. In our context, this finiteness is first met in the notion
of xn -regularity of power series in the Weierstrass division, and then also in Hironaka’s box
condition and our concept of echelon (which is a Rees decomposition of a prescribed combinatorial type). It is the prerequisite for a subtle induction on the number of variables, but has
the drawback that in the induction step one has to consider modules instead of ideals. This
aggravates the notation, though modules are the natural context to work with.
The nicest part of our algorithm is what we call virtual division, a trick which has already
appeared in various disguises in the literature, e.g. in the work of Artin, Malgrange, Mora,
Pfister-Popescu and Alonso-Mora-Raimondo: When dividing formal power series expand
them with respect to one variable and write the coefficient series in the remaining variables as
new unknown variables. If this is done with the necessary caution, the successive operations
2

in the division of the formal power series can be carried out in terms of these virtual series and
will then be finite processes. To make this approach work in reality, a precise understanding
of the structure of the division algorithm is mandatory.
To resume and rephrase the above, our division algorithm for the codes of algebraic power
series shows that the division is a finite process once you succeed to interpret certain packages
of infinitely many data (i.e., coefficient series) as single objects which undergo a uniform
transformation under division. The complexity of the algorithm shows that this encryption is
by no means obvious. But it does exist and work.
The emphasis of the paper is theoretical – actual computations become quickly unfeasable.
We rather provide insight and methods of how to manipulate algebraic power series abstractly
within finite algorithms. This may turn out to be useful in other situations where one aims at
or needs finiteness assertions: passage to étale neighborhoods, noetherianity, semicontinuity
of invariants of complete local rings, recursion theory for generating series, ...
Example. Let us briefly explain the method in the special case of the construction of the
code of the Weierstrass normal form of an xn -regular power series g(x) of order d. Assume
for simplicity that g is actually a polynomial, say g(x) = G(x) ∈ K[x] (capital letters will
be reserved throughout for polynomials). Introduce new variables u0 , . . . , ud−1 and define
Pd−1
a polynomial B ∈ K[xn , u] as B(xn , u) = xdn + j=0 uj · xjn . This is our candidate
presentation for the Weierstrass normal form of G. It then suffices to determine (algebraic)
series u0 (x′ ), . . . , ud−1 (x′ ) ∈ K[[x′ ]] = K[[x1 , . . . , xn−1 ]] such that the series b(x) obtained
from B by substitution of uj by uj (x′ ), say
P
′
j
b(x) = B(xn , u(x′ )) = xdn + d−1
j=0 uj (x ) · xn ,
equals the Weierstrass normal form of G. Instead of constructing the series uj (x′ ) directly, we
shall develop a procedure to determine their code (in the sense described above, see section
6 for details). To do this, observe first that xdn is the initial monomial of G with respect to
the lexicographic order <lex on Nn for which (1, 0, . . . , 0) > . . . > (0, . . . , 0, 1), i.e., the
exponent of xdn is the smallest element with respect to <lex of the support of G (this uses
that uj (0) = 0 since b has order d at 0). The usual power series division of the monomial
xdn by G with respect to this initial monomial then yields a formal power series remainder
Pd−1
r(x) = j=0 uj (x′ ) · xjn such that xdn − r(x) is the Weierstrass normal form of G. This
division is in general an infinite process.
The key point now is to view xdn alternatively as the leading monomial of the polynomial B
with respect to a suitable monomial order <ω on N × Nd , i.e., the exponent of xdn becomes
the largest element with respect to <ω of the support of B. Indeed, just take for <ω an order
such that uj << xn for j = 0, . . . , d − 1. Then uj · xjn < xdn for j < d and hence xdn will
be the largest monomial of G with respect to <ω . This now allows us to divide G by B
polynomially with respect to the leading monomial xdn , say
G = Q · B + R,
with quotient a polynomial Q in K[x, u] and with remainder a polynomial R in K[x, u]
Pd−1
′
j
′
of the form R =
j=0 Uj (x , u) · xn for some polynomial coefficients Uj ∈ K[x , u].
If g were not a polynomial but just an algebraic series, one would have to take for G the
polynomial code of it, see section 13 for the precise procedure. This polynomial division
is, of course, a finite process. A rather tedious computation then shows that the jacobian
matrix ∂u U of the vector U = (U0 , . . . , Ud−1 ) ∈ K[x′ , u]d with respect to the u-variables
is invertible when evaluated at 0. It thus defines, by the implicit function theorem, a unique
vector u(x′ ) = (u0 (x′ ), . . . , ud−1 (x′ )) of algebraic series uj (x′ ) such that U (x′ , u(x′ )) = 0.
This just means that U is a code for u(x′ ). But, by construction, R(x, u(x′ )) = 0, so that
G(x) = Q(x, u(x′ )) · B(x, u(x′ )). By comparison of the initial monomials it follows that
3

Q(x, u(x′ )) is invertible as a power series, hence b(x) = B(x, u(x′ )) is indeed the Weierstrass
normal form of G as required.
This example gives an idea of how the codes of reduced standard bases and of the quotients
and the remainder of a division can be constructed. In practice and for the required generality
the technicalities become unfortunately much more involved.
At the same time, there remain puzzling mysteries when the involved algebraic series are
no longer xn -regular (in which case the Weierstrass normal form has to be defined as the
reduced standard basis of the ideal). For instance, the polynomial xy − z(x + y + x2 y 2 ) with
initial monomial xy has an algebraic series as its normal form, whereas the normal form of
xy − z(x2 + y 2 + x2 y 2 ) is a transcendent series (over a ground field of characteristic zero; it
is a so called Mahler series). Both facts are easy to prove by direct computation. In contrast,
the normal form of xy − z(1 + y)(1 + x2 y), a polynomial which appears in the counting of
Gessel walks, is again an algebraic series, but this seems to be very intricate to prove. The
algebraicity of the normal form was eventually shown by Bostan-Kauers – a substantial part
of their proof relies on heavy computer machinery [BK]. No conceptual systematic proof
of the algebraicity seems to be known for this example. However, modifying slightly the
input polynomial, taking now xy − z(1 + y)(1 + xy 2 ), it is almost immediate to detect the
algebraicity using a suitable division.
These examples suggest that there are hidden structural patterns which cause the phenomena
to happen and which should explain the occurrence of algebraic or transcendent normal forms.
Little seems to be known in this respect. For instance, the classification of the generating
functions of lattice walks in the first quadrant, studied among others by Bousquet-Mélou,
Mishna and Petkovšek, does not seem to reveal a systematic background [BM, BP2, Mi].
Organization of the paper. After some preliminary recalls on the formal power series and
polynomial division covering sections 2 to 5, we introduce and study in sections 6 to 8 codes
of algebraic series and of the ideals generated by them. These are polynomial data which
completely determine the series and ideals they encode. For later purposes the codification is
carried out from the beginning for vectors of algebraic series and the modules they generate.
Section 9 describes how to compute the codes of standard bases of ideals and modules from
a given (arbitrary) generator system (Theorem 9.1). This is straightforward, and based on
Lazard’s homogenization method, respectively Mora’s tangent cone algorithm. Both were
refined and extended by Gräbe and Greuel-Pfister. Our two main results (sections 10 and
11) concern the construction – in terms of the defining codes – of reduced standard bases
of modules of algebraic power series vectors (Theorem 10.1), and of the quotients and the
remainder of an algebraic power series division (Theorem 11.1).
The proofs of these two theorems are mutually interwoven (sections 12 to 15). First, the
construction of the reduced standard basis is performed in the xn -regular case (i.e., in the case
where the initial module of the given module of algebraic power series vectors is generated by
monomial vectors depending only on the last variable xn ). This is by far the most complicated
step. It clearly shows how important it is to codify the series in a very systematic manner.
Otherwise it would be hopeless to prove that the resulting polynomial vectors represent again
codes (i.e., satisfy the assumption of the implicit function theorem). In the case of principal
ideals, the proof provides the code of the Weierstrass normal form of the given series, cf.
[AMR].
The preceding construction of the codes of the reduced standard basis in the xn -regular case
is then used to establish the division of algebraic series on the level of codes in the xn regular case. This is not too difficult. It relies on the effectivity of the division algorithm in
localizations of polynomial rings, proven by Lazard, Mora, Gräbe and Greuel-Pfister.
4

Once the two theorems are established in the xn -regular case, the general case is carried out
by induction on the number of variables. It is here that Hironaka’s box condition comes into
play. One key feature is its persistence under taking hyperplane sections (in a well defined
sense), and this is used to know that the associated modules in n − 1 variables satisfy again
the box condition. So induction applies to prove both theorems simultaneously.
In the last section, we illustrate the instances and the complexity of the two algorithms in the
computation of a concrete example.
Acknowledgements. The authors are very indebted to T. Mora, W. Seiler, G.-M. Greuel, G.
Rond and O. Villamayor for many valuable comments and helpful suggestions during the
preparation of this article. W. Seiler pointed out an inaccuracy in an earlier version of the
manuscript, indicated the relation of echelons and Janet bases with his notion of δ-regularity
and Pommaret division, and provided several important references. Part of this work has
been done during visits of the first two authors to the University of Vienna and the Erwin
Schrödinger Institute.

2. Monomial modules
The letters n, p, r, s are reserved for fixed integers in N. The letters i, k and ℓ will generally
vary in the ranges 1 ≤ i ≤ p, 1 ≤ k ≤ r and 1 ≤ ℓ ≤ s.
We denote by K[x1 , . . . , xn ] = K[x] and K[[x1 , . . . , xn ]] = K[[x]] the polynomial, respectively formal power series ring in n variables x = (x1 , . . . , xn ) over a field K. Elements
of K[x]s and K[[x]]s will be called polynomial respectively formal power series vectors.
Capital letters will be reserved for polynomials, lower case letters for power series. We set
x′ = (x1 , . . . , xn−1 ) and denote by y = (y1 , . . . , yp ) additional variables.
P
α
Vectors g ∈ K[[x]]s will be expanded into g =
αℓ cαℓ x eℓ with cαℓ ∈ K and eℓ =
s
(0, . . . , 0, 1, 0, . . . , 0) the canonical K-basis of K . The vectors xα eℓ are called monomial
vectors. Note that all their entries but one are zero: a vector all whose entries are monomials
will not be considered here as a monomial vector. The support of g is the set supp(g) =
{(α, ℓ) ∈ Nn × {1, . . . , s}, cαℓ 6= 0}. We sometimes abbreviate pairs (α, ℓ) by αℓ.

Brackets hg1 , . . . , gr i denote submodules of K[[x]]s generated by power series vectors
g1 , . . . , gr ∈ K[[x]]s . We abbreviate this by hgk i if the range of k is clear from the context.
A monomial submodule of K[[x]]s is a submodule M of K[[x]]s generated by monomial vectors. It is a cartesian product M = Πsℓ=1 Mℓ of monomial ideals Mℓ in K[[x]].
The elements of M are the power series vectors with support in Σ = {(α, ℓ) ∈ Nn ×
{1, . . . , s}, xα eℓ ∈ M }. The canonical direct monomial complement of a monomial submodule M of K[[x]]s is the subvectorspace co(M ) of K[[x]]s of power series vectors with
support in Σ′ = (Nn × {1, . . . , s}) \ Σ. This provides the direct sum decomposition of
K-vectorspaces M ⊕ co(M ) = K[[x]]s .

We say that a monomial submodule M of K[[x]]s is xn -regular if it is generated by monomial
vectors in K[[xn ]]s , say M = hM ∩ K[[xn ]]s i. We shall then always assume for simplicity
– applying if necessary a permutation of the components of K[[x]]s – that M is generated by
vectors of the form xdnk · ek with dk ≥ 0 and 1 ≤ k ≤ r for some r ≤ s. In this case the
complement co(M ) is a cartesian product
Qr
dk −1
K[[x′ ]] · xjn ) × K[[x]]s−r
co(M ) = k=1 (⊕j=0

of a finitely generated free K[[x′ ]]-module with a finitely generated free K[[x]]-module. We
say that M satisfies Hironaka’s box condition if co(M ) can be written as a cartesian product
of direct sums of finite free monomial K[[x1 , . . . , xj ]]-modules
Qs
co(M ) = ℓ=1 ⊕nj=0 ⊕γ∈Γℓj K[[x1 , . . . , xj ]] · xγ
5

with finite sets Γℓj ⊂ Nn . Being xn -regular is a special case of the box condition. For cyclic
submodules of K[[x]]s , both notions coincide. They obviously depend on the numbering of
the variables x1 , . . . , xn . Notice that for s = 1 and 0 6= M ( K[[x]] a non trivial ideal,
the indices of the boxes Fj run from 1 to n − 1. Also notice that the box condition for a
monomial submodule M ⊂ K[[x]]s is equivalent to the box condition for each of the factors
of M (which are monomial ideals in K[[x]]).
W. Seiler informed us that in the case of ideals the box condition is equivalent to his notion of
δ-regular coordinates [Se3]. We say that a monomial submodule M of K[[x]]s is an echelon
if it can be written as
Qs
M = ℓ=1 ⊕nj=0 ⊕δ∈∆ℓj K[[x1 , . . . , xj ]] · xδ
with finite sets ∆ℓj ⊂ Nn . This can be rewritten as
M = ⊕sℓ=1 ⊕δ∈∆ℓ K[[x1 , . . . , xnδ ]] · xδ · eℓ

S
where ∆ℓ = j ∆ℓj and where, for each δ, the index nδ takes a value between 0 and n.
This notion is a special case of a Rees decomposition of M [Re]. We call the collection
of monomial vectors xδ · eℓ with δ ∈ ∆ℓ and 1 ≤ ℓ ≤ s a Janet basis of the echelon M
with scopes nδ (also known as levels or classes). Our definition differs slightly from Janet’s
original definition in the sense that we only allow nested groups of variables in the coefficients
[Ja1, Ja2], cf. also [Ri]. We refer to the related notions of Pommaret bases and involutive
bases [GB, Se1, Se2], and the more general concepts of Rees and Stanley decompositions of
rings [Re, SW, Am, BG].
For the following result, see also Janet [Ja1, Ja2] and Seiler [Se2].
Theorem 2.1. Monomial submodules of K[[x]]s satisfying Hironaka’s box conditon are
echelons.
Proof. Let M be such a module, and let Mn = hM ∩ K[[xn ]]s i be the submodule of K[[x]]s
generated by the xn -pure monomial vectors of M . By definition, Mn is xn -regular. Let
xdnk · ek with 1 ≤ k ≤ r be a minimal generator system of Mn (after possibly permuting the
components of K[[x]]s ). Then Mn = ⊕rk=1 K[[x]] · xdnk · ek , which shows that the monomial
vectors xdnk · ek form a Janet basis of Mn with scopes nk = n. The direct sum decomposition
m −1
K[[x′ ]] · xjn · em ) ⊕ ⊕sm=r+1 K[[x]] · em
K[[x]]s = Mn ⊕ (⊕rm=1 ⊕dj=0

yields a decomposition M = Mn ⊕ M ′ where M ′ is now a K[[x′ ]]-submodule of the finitely
m −1
generated free K[[x′ ]]-module ⊕rm=1 ⊕dj=0
K[[x′ ]] · xjn · em . We use here that, because of
the box condition, M has zero intersection with ⊕sm=r+1 K[[x]] · em .
It is checked that the box condition persists under the above decomposition, i.e., that M ′
satisfies it again. By induction on the number of variables, M ′ is an echelon. Its Janet basis
has scopes ≤ n − 1. From M = Mn ⊕ M ′ now follows that also M is an echelon.
Example. The assertion of the theorem does not hold for arbitrary modules as was pointed
out by W. Seiler. Take the ideal I of K[x, y, z] generated by the three monomials xy, xz and
yz. It is easy to see that it does not satisfy the box condition. And it is not an echelon, since,
for instance, among the monomials of I which are not multiples of xy one has monomials
xd z and y d z of arbitrary degree d in x and y. As the situation is symmetric with respect to
any permutation of the variables, I does not admit the required decomposition of an echelon.

3. Monomial orders and initial modules
Division theorems are based on ordering the summands cαℓ xα eℓ of the expansion of a power
P
α
n
series vector g =
αℓ cαℓ x eℓ according to the indices (α, ℓ) ∈ N × {1, . . . , s} with
6

non-zero coefficients cαℓ : A monomial order on Nn × {1, . . . , s} is a total order <η on
Nn × {1, . . . , s} which is compatible with the semi-group structure of Nn , having 0 as
its smallest element, and which is noetherian. This means that if (α, ℓ) <η (β, m) then
(α + γ, ℓ) <η (β + γ, m) for any γ ∈ Nn , and, secondly, that any decreasing sequence
becomes stationary. The order is degree compatible if |α| < |β| implies (α, ℓ) <η (β, m),
where |α| denotes the sum of the components of α. An extension of <η is a monomial order
<ε on Nn+p × {1, . . . , s} whose restrictions to Nn × {δ} × {1, . . . , s} coincide for all δ ∈ Np
with the order induced by <η on Nn × {δ} × {1, . . . , s}. We will always identify monomial
orders on Nn × {1, . . . , s} with the induded ordering of the monomial vectors in K[[x]]s .
P
The initial monomial vector in(g) of g =
cαℓ xα eℓ ∈ K[[x]]s with respect to <η is the
α
vector x · eℓ of the expansion of g for which (α, ℓ) is minimal with respect to <η . We shall
assume that xα · eℓ has coefficient 1 in the expansion of g. We then write g = xα · eℓ − g and
call g the tail of g.
For a submodule I of K[[x]]s , the initial module of I with respect to <η is the monomial
submodule in(I) of K[[x]]s generated by all initial monomial vectors of elements of I. This
is a monomial submodule which depends on the choice of <η . We denote by co(I) the
canonical direct monomial complement of in(I) in K[[x]]s . Elements g1 , . . . , gr of K[[x]]s
form a standard basis w.r.t. <η if their initial monomial vectors generate the initial module
in(I) of the module I generated by g1 , . . . , gr . They are a reduced standard basis if the tails
g k belong to co(I). We do not require that a reduced standard basis is minimal.
We say that a submodule I of K[[x]]s is xn -regular, respectively satisfies Hironaka’s box
condition, or is an echelon with respect to the monomial order <η on Nn × {1, . . . , s}, if its
initial module in(I) is xn -regular, respectively satisfies the box condition, or is an echelon.
A Janet basis of a submodule I of K[[x]]s which is an echelon w.r.t. <η is a generator system
g1 , . . . , gr of I whose initial monomial vectors in(gk ) form a Janet basis of in(I).
For a polynomial vector G ∈ K[x]s , define the leading monomial vector lm(G) as the
monomial vector xα eℓ of the expansion of G which is maximal with respect to the chosen
monomial order. Similarly as for initial modules, one obtains now the leading module lm(I)
of a submodule I of K[x]s .

4. Division of formal power series and polynomials
We recall the division theorem for modules of formal power series of Grauert, Hironaka and
Galligo [AHV, Gra, Hi1, Ga, HM]. For extensions of this result to more general settings see
[Am, BG, GB, Se2].
Theorem 4.1. Let I be a submodule of K[[x]]s with initial module in(I) with respect to
a monomial order <η on Nn × {1, . . . , s}. Let co(I) be the canonical direct monomial
complement of in(I) in K[[x]]s . Then I ⊕ co(I) = K[[x]]s .
Sketch of proof. The sum I ⊕ co(I) is direct by definition of co(I). To see that it equals
K[[x]]s , choose a standard basis g1 , . . . , gr of I. It suffices to show that the linear map
P
u : K[[x]]r × co(I) → K[[x]]s , (a1 , . . . , ar , b) →
ak gk + b is surjective. By definition of
P
standard bases, the map v : K[[x]]r × co(I) → K[[x]]s , (a1 , . . . , ar , b) → ak · in(gk ) + b
is surjective. Writing u = v + w, the assertion follows by restricting v to a direct complement
L of its kernel and by showing that u|L = v|L + w|L is an isomorphism with inverse the
P∞
geometric series (v|L )−1 j=0 ((v|L )−1 w|L )j . This series then induces the required linear
map K[[x]]s → L inverse to u|L , see [HM, Thm. 5.1] for details.
The division theorem can be formulated more explicitly as follows: If g1 , . . . , gr generate I,
P
each vector f ∈ K[[x]]s has a decomposition f = k ak gk + h with unique h ∈ co(I). The
power series expansions of the quotients ak and the remainder h can be computed up to any
7

given degree by a finite algorithm (take the expansion of the geometric series above up to the
respective degree). The requirement that h belongs to co(I) makes the remainder independent
of the choice of g1 , . . . , gr (but it depends on the monomial order <η ). If g1 , . . . , gr form a
standard basis, the quotients ak can be made unique by imposing suitable support conditions
on them [Ga]. A reduced standard basis of I is given as xα · eℓ − hαℓ with (α, ℓ) varying in
some finite subset V ⊂ Nn × {1, . . . , s}, where the vectors xα · eℓ are generators of in(I)
and the vectors hαℓ denote the remainder of the division of xα · eℓ by I.
For modules which are echelons one can formulate a more precise statement:
Theorem 4.2. Let I be a submodule of K[[x]]s with initial module in(I) w.r.t. a monomial
order <η on Nn × {1, . . . , s}. Assume that I is an echelon, and let xα · eℓ be a Janet basis
of in(I) with scopes nαℓ , (α, ℓ) varying in some finite set V ⊂ Nn × {1, . . . , s}. Choose any
elements gαℓ of I with initial monomial vectors xα · eℓ . Then
I ⊕ co(I) = ⊕αℓ∈V K[[x1 , . . . , xnαℓ ]] · gαℓ ⊕ co(I) = K[[x]]s .
Proof. First notice that in(I) = ⊕αℓ∈V K[[x1 , . . . , xnαℓ ]] · xα · eℓ by definition of echelons.
This allows us to modify the map u from the proof of the division theorem by restricting it to
the K-subspace
⊕αℓ∈V K[[x1 , . . . , xnαℓ ]] · xα · eℓ × co(I).
The map v is then by construction an isomorphism, and the same reasoning as before shows
that this holds also for u. This proves the claim.
In the polynomial case, the division admits an analogous formulation. The same proof as
P∞
above applies, because the evaluation of the geometric series (v|L )−1 j=0 ((v|L )−1 w|L )j
on a polynomial vector (a1 , . . . , ar , b) ∈ K[x]r × co(I) terminates at sufficiently large j.
Theorem 4.3. Let I be a submodule of K[x]s with leading module lm(I) with respect to
a monomial order <η on Nn × {1, . . . , s}. Let co(I) be the canonical direct monomial
complement of lm(I) in K[x]s . Then I ⊕ co(I) = K[x]s .
Again, there is a more precise version in case the leading module lm(I) is an echelon.
Theorem 4.4. Let I be a submodule of K[x]s with leading monomial module lm(I) with
respect to a monomial order <η on Nn × {1, . . . , s}. Assume that lm(I) is an echelon. Let
Gk be a polynomial Janet basis of I with leading monomial vectors lm(Gk ) of scope nk .
Then any F ∈ K[x]s admits a unique division
P
F = k Ak Gk + C
with Ak ∈ K[x1 , . . . , xnk ] and C ∈ co(I). The decomposition can be obtained from the
polynomial vectors F and Gk by a finite algorithm.

5. Algebraic power series
P
Algebraic power series are formal power series h(x) = α∈Nn cα xα in several variables
x = (x1 , . . . , xn ) with coefficients in a field K which satisfy an algebraic relation of the form
P (x, h(x)) = pd hd + pd−1 hd−1 + . . . + p1 h + p0 = 0,
where the coefficients pi = pi (x) are polynomials. We refer to [Ar2, BCR, BrK, KPR, Lf,
Na1, Na2, Ra, Ru, Wi] for the respective background. An algebraic power series vector is a
vector in K[[x]]s whose components are algebraic series.
Typical
algebraic series are rational functions as x · (1 + x)−1 , roots of polynomials as
p
2
1 + x y, inverses f −1 of polynomial mappings f : K n → K n satisfying at a point p
8

the assumption of the Inverse Function Theorem as f (x, y) = (x + x3 , y − xy 2 ) at 0, or
solutions y(x) of polynomial equations f (x, y) = 0 satisfying at a point p the assumption of
the implicit function theorem with respect to the variables y as f (x, y) = y + xy + x3 y 2 at 0.
The ring of algebraic series in n variables is thus the algebraic closure of the polynomial ring
K[x1 , . . . , xn ] inside the formal power series ring K[[x1 , . . . , xn ]]. It can equivalently be
interpreted as the henselization of the polynomial ring at 0.
Note that the minimal polynomial of an algebraic series h determines h only up to conjugacy:
there may be other power series solutions to the equation, the conjugates of h, and h can be
distinguished from these for instance by a sufficiently high truncation of its Taylor expansion.
The simplest example thereof is the equation y 2 − 2y + x = 0 with algebraic solutions
√
h± = 1 ± 1 − x.
Lafon proved in 1965 that the Weierstrass division preserves the algebraicity of the involved
series [Lf], see also [BCR]. This was reproven in 2000 by Bousquet-Mélou and Petkovšek
working with the recursions defining the coefficients of the series [BP1]. The result of Lafon
was extended by Hironaka in 1977 to the division by ideals with several generators satisfying
the box condition [Hi1]. We formulate here the division directly for modules.
Theorem 5.1. Let I be a submodule of K[[x]]s generated by algebraic power series vectors.
Assume that I satisfies Hironaka’s box condition with respect to a monomial order <η on
Nn × {1, . . . , s}. For any algebraic power series vector f ∈ K[[x]]s the remainder c of the
formal power series division of f by I with respect to <η is an algebraic power series vector.
The theorem implies in particular that any submodule of K[[x]]s with box condition which
is generated by algebraic power series vectors admits a reduced standard basis consisting of
algebraic power series vectors. Without box condition the remainder of the division need not
be algebraic. In [Hi1, p. 75], Hironaka cites the following example of Gabber and Kashiwara,
which was rediscovered by Bousquet-Mélou and Petkovs̆ek in combinatorics when counting
lattice paths [BP1, BP2].
Example 5.2. Divide xy by g = (x − y 2 )(y − x2 ) = xy − x3 − y 3 + x2 y 2 as formal
power series with respect to the initial monomial xy. The remainder of the division lies in
P
P
k
k
co(xy) = K[[x]] + K[[y]] and equals the lacunary series b = k≥0 x3·2 + k≥0 y 3·2
which is transcendent . Alternatively, we may write xy = a · g + r(x) + s(y) with series
a ∈ K[[x, y]], r ∈ K[[x]], s ∈ K[[y]]. The symmetry between x and y in this expression
yields r(x) = s(x). Substituting y by x2 produces x3 = a · 0 + r(x) + r(x2 ) which also
gives the expansion of r.

6. Codes of algebraic power series
In this section we introduce the necessary terminology for working effectively with algebraic
power series. The variables x = (x1 , . . . , xn ) and y = (y1 , . . . , yp ) are fixed throughout.
A mother code (over x and y) is a polynomial row vector H = (H1 , . . . , Hp ) ∈ K[x, y]p
with H(0, 0) = 0 whose Jacobian matrix Dy H with respect to y is invertible at 0,
Dy H(0, 0) ∈ Glp (K).
The invertibility of Dy H(0, 0) can be rephrased by saying that for any degree compatible
monomial order on Np the initial ideal of the ideal hH1 (0, y), . . . , Hp (0, y)i of K[[y]] is
generated by y1 , . . . , yp . There then exists a linear coordinate change in the yi ’s so that the
initial monomials in(Hi (0, y)) of Hi (0, y) equal yi . For any degree compatible monomial
order on Nn+p so that yi < xj for all i and j it then follows that the initial monomials in(Hi )
of Hi equal yi . Instead of changing the yi ’s one could also change H by multiplying it from
the right with a suitable matrix in Glp (K) making Dy H(0, 0) unipotent upper triangular. In
9

the sequel we shall always assume that in(Hi ) = yi with respect to the chosen monomial
order on Nn+p .
The baby series vector of a mother code H ∈ K[x, y]p is the formal power series vector
h = (h1 , . . . , hp ) ∈ K[[x]]p vanishing at 0 which is the unique solution of H(x, h(x)) = 0.
The existence and uniqueness of h are ensured by the implicit function theorem for formal
power series. The components hi of the baby series vector h are algebraic series. This can
be seen by the algebraic implicit function theorem [KPR, p. 91], or Artin’s Approximation
Theorem [Ar2], or by the following argument: Consider the system H(x, y) = 0 as equations
for the last variable yp . After a renumeration of the components of H, the last derivative
∂yp Hp (0, 0) does not vanish. There then exists a unique solution hp (x, y1 , . . . , yp−1 ) of
Hp (x, y1 , . . . , yp−1 , yp ) = 0 vanishing at 0, and hp is algebraic over K[x, y1 , . . . , yp−1 ].
By induction on n and the transitivity of algebraicity we conclude that h = (h1 , . . . , hp ) is
algebraic.
An algebraic power series vector h = (h1 , . . . , hp ) ∈ K[[x]]p is a baby series vector if it
admits a mother code H ∈ K[x, y]p defining it.
A father code is a vector G = (G1 , . . . , Gr ) of polynomial vectors Gi ∈ K[x, y]s (there are
no further conditions on the Gi ). We consider G as a row vector with entries the column
vectors Gi , say as a matrix in K[x, y]s×r .
A family code is a pair (H, G) where H ∈ K[x, y]p is a mother code and G ∈ K[x, y]s×r a
father code, both carrying on the same sets of variables. We say that algebraic power series
vectors g1 , . . . , gr ∈ K[[x]]s have family code (H, G) ∈ K[x, y]p × K[x, y]s×r if
gk = Gk (x, h(x))
for 1 ≤ k ≤ r, where h ∈ K[[x]]p is the baby series vector of the mother code H. The
vectors gk hence belong to K[x, h]s ⊂ K[[x]]s . We call h the baby series vector underlying
g1 , . . . , gr , or, the other way round, g1 , . . . , gr the algebraic power series vectors produced
from h by the father code G.
√
Example 6.1. Take g1 = z 3 + z 2 h, g2 = xz 2 + xzh with baby series h = 1 − 1 − x2 ,
mother code H = 2y − y 2 − x2√and father code G1 = z 3 + z 2 y, G2 = xz 2 + xzy. Notice that
the second series solution 1 + 1 − x2 of H = 0 has non-zero constant term and is therefore
not considered as a baby series of H.
Example 6.2. Let H be the vector (H1 , H2 ) with H1 = y12 − 2y1 − y2 − x2 and H2 =
x2 y22 −2y2 −y1 −x1 . The vector H is the mother code of the baby series
p vector (h1 , h2 ) where
√
h1 and h2 are related by h1 = 1 − 1 + x2 + h2 and h2 = (1 − 1 + x2 (x1 + h1 ))/x2 .
The mother code H defines the same baby series vector as the mother code H ′ = (H1′ , H2′ )
given by
H1′ = −x1 + x32 + 2x2 − 4x2 y13 + (3 + 4x22 )y1 + (−2x22 − 2 + 4x2 )y12 + x2 y14 ,
H2′ = −y12 + 2y1 + y2 + x2 .
Now, Dy H ′ (0, 0) is unipotent upper triangular and H1′ does not depend on y2 . Hence, the
expansion of the series h1 can be computed up to a any order from the equation H1′ = 0.
From H2′ = 0 we get h2 = −x2 − 2h1 + h21 .

10

7. Construction of codes
Codes of algebraic power series as above were introduced by Alonso, Mora and Raimondo.
Their construction is based on an effective version of the Artin-Mazur theorem [AM, p. 88,
AMR, appendix, BCR, Thm. 8.4.4, p. 173].
Theorem 7.1. For any algebraic series g ∈ K[[x]] there is a finite algorithm to construct
from an algebraic relation P (x, t) = 0 satisfied by g and the Taylor expansion of g up to
sufficiently high degree a family code (H, G) ∈ K[x, y]p × K[x, y] of g, for some p.
Proof. Let P (x, g(x)) = 0 be a minimal hence irreducible algebraic relation for g. Denote by
X ⊆ An+1
the zero-set of P in affine (n + 1)-space An+1
over K. We assume that g(0) = 0
K
K
so that (0, 0) ∈ X. Let Y be the normalization of X. Choose an embedding Y ⊂ An+p
so that the normalization map π : Y → X is induced by the projection An+p → An+1 ,
(x, y) → (x, y1 ) on the first n + 1 components.
The Taylor expansion of g specifies a unique point b ∈ Y which maps to 0 ∈ X and through
which, by the universal property of normalization, passes a lifting (x, ge(x)) of (x, g(x)).
From Zariski’s Main Theorem [Za, Mu, p. 209] we know that Y is analytically irrreducible
at b. But as Y contains the graph of e
g and has dimension n, it is smooth at b. By the Jacobian
criterion it is therefore possible to choose polynomial equations H1 , . . . , Hp defining Y in a
Zariski neighborhood of b in An+p and satisfying at b the assumption of the implicit function
theorem, i.e., of a mother code. Let (h1 , . . . , hp ) be the associated baby series vector. By the
special choice of π we get g = h1 , say g = G(h1 , . . . , hp ) with father code G = y1 . This
proves the theorem.
The construction of the normalization is effective [dJP] and implemented for instance in the
computer-algebra program Singular [GPS].
When handling several algebraic power series it is more economic to work with one mother
code and several father codes instead of choosing separate mother codes for each series. This
goes as follows.
Let be given mother codes H j ∈ K[x, y j ]pj for j = 1, . . . , r in distinct sets of variables y j =
(y1j , . . . , ypj j ) defining baby series vector hj = (hj1 , . . . , hjpj ) ∈ K[[x]]pj . The direct sum H
of the H j ’s is given as the row vector H = (H 1 , . . . , H r ) ∈ Πrj=1 K[x, y]pj ∼
= K[x, y]p ,
P
j
where y denotes the collection of all y and p =
pj . This H is again a mother code,
because the Jacobian matrix Dy H(0, 0) of H with respect to y at 0 has block diagonal form
with invertible blocks equal to Dyj H j (0, 0) on the diagonal. The vector h = (h1 , . . . , hr )
obtained by listing all baby series vectors hj of the mother codes H j in a row is the baby series
vector of H. This passage to direct sums of mother codes allows us to treat several baby series
vectors hj simultaneously as one baby series vector h (with many components). Accordingly,
finitely many algebraic series can always be considered as produced by certain father codes
from the same baby series vector h = (h1 , . . . , hp ) of one mother code H ∈ K[x, y]p . This
allows us to work throughout with vectors in K[x, h1 , . . . , hp ]s .
Note that mother codes as defined above may require large sets of variables and are thus
computationally very expensive.

8. Codes for modules of algebraic series
Let be given algebraic power series vectors g1 , . . . , gr ∈ K[[x]]s vanishing at 0 with mother
code H ∈ K[x, y]p , baby series vector h ∈ K[[x]]p and father code G ∈ K[x, y]s×r so that
gk = Gk (x, h(x)). The submodule hgk i of K[[x]]s generated by the series gk admits the
following polynomial description.
11

Lemma 8.1. Let h(yi −hi )·eℓ , gk i and hHi ·eℓ , Gk i be the submodules of K[[x, y]]s generated
by the vectors (yi − hi ) · eℓ and gk , respectively Hi · eℓ and Gk , for 1 ≤ i ≤ p, 1 ≤ ℓ ≤ s,
1 ≤ k ≤ r. Then
h(yi − hi ) · eℓ , gk i = hHi · eℓ , Gk i.
Proof. We fix a monomial order <η on Nn × {1, . . . , s} and choose an extension <ε of <η to
Nn+p ×{1, . . . , s} which is degree compatible with respect to Np and satisfies yi ·eℓ <ε xj ·eℓ
for all 1 ≤ i ≤ p, 1 ≤ j ≤ n and 1 ≤ ℓ ≤ s. After a suitable multiplication of H with a
constant matrix in GLp (K) we may assume that in(Hi · eℓ ) = yi · eℓ .
The ideal hHi i of K[[x, y]] generated by H1 , . . . , Hp is contained in the ideal hyi − hi i
because of H(x, h(x)) = 0. Take a monomial order <δ on Nn+p so that yi <δ xj for all
1 ≤ i ≤ p and 1 ≤ j ≤ n. The initial ideals of hHi i and hyi − hi i coincide because, by
the choice of <δ , they are both generated by y1 , . . . , yp . By the Division Theorem for formal
power series, the two ideals coincide. As gk is obtained from Gk by replacing yi by hi ,
the submodules of K[[x, y]]s generated by g1 , . . . , gr , respectively G1 , . . . , Gr are congruent
modulo hyi − hi i = hHi i. This proves the lemma.
We call Ie = hHi · eℓ , Gk i ⊂ K[[x, y]]s , or, more accurately, its polynomial generators Hi · eℓ
and Gk , the family code of the submodule I = hgk i of K[[x]]s . Observe that Ie∩ K[[x]]s = I.

Lemma 8.2. Let be given a monomial order <η on Nn × {1, . . . , s} and an extension <ε
of <η to Nn+p × {1, . . . , s} which is degree compatible with respect to Np and satisfies
yi · eℓ <ε xj · eℓ for all 1 ≤ i ≤ p, 1 ≤ j ≤ n and 1 ≤ ℓ ≤ s. Let Ie = hHi · eℓ , Gk i and
I = hgk i be the respective submodules of K[[x, y]]s and K[[x]]s . Then
e ∩ K[[x]]s = in(I).
in(I)

e Let e
Proof. We may choose a minimal reduced standard basis of I.
gk be an element of this
basis which does not have an initial monomial vector of the form yi · eℓ . From reducedness
it follows that e
gk is independent of y1 , . . . , yp , say gek ∈ Ie ∩ K[[x]]s = I. In particular, the
e ∩ K[[x]]s = in(I).
vectors gek form a standard basis of I and hence in(I)

9. Construction of standard basis
The first construction we need is a direct consequence of Mora’s tangent cone algorithm [Mo],
respectively Lazard’s homogenization method [Lz], cf. also with [AMR, Thm. 1.3, CLO, p.
202, Gr1, Gr2, GP, Thm. 6.4.3]. It provides an algorithm to construct the family code of a
(not necessarily reduced) standard basis of a module of algebraic power series vectors.
Theorem 9.1. Let I be a submodule of K[[x]]s generated by algebraic power series vectors
g1 , . . . , gr ∈ K[[x]]s which are given by their family code. Let be chosen a monomial order
<η on Nn ×{1, . . . , s}. There is a finite algorithm to compute the family codes of the elements
of a standard basis of I with respect to <η from the family codes of g1 , . . . , gr . In particular,
it is possible to compute the initial module in(I) of I.
Proof. Let g1 , . . . , gr have mother code H ∈ K[x, y]p , baby series vector h ∈ K[[x]]p and
father code G ∈ K[x, y]s×r . Extend <η to a monomial order <ε on Nn+p × {1, . . . , s}
which is degree compatible with respect to Np and satisfies yi · eℓ <ε xj · eℓ for all i, j and ℓ.
We assume w.l.o.g. that the initial monomial vectors of Hi · eℓ with respect to <ε are yi · eℓ .

As Ie = hHi · eℓ , Gk i is generated by polynomial vectors, Mora’s tangent cone algorithm or
Lazard’s homogenization method apply to construct a polynomial standard basis for it. This
basis is in general not reduced. We may choose a minimal basis consisting of the vectors
e1 , . . . , G
er′ ∈ K[x, y]s
Hi · eℓ with in(Hi · eℓ ) = yi · eℓ and of other polynomial vectors G
s
with initial monomial vectors in K[[x]] . The latter form the father code of algebraic power
12

ek (x, h). Note that G
e k is congruent to gk
series vectors ge1 , . . . , e
gr′ ∈ K[[x]]s , say gek = G
s
modulo the submodule hHi · eℓ i of K[[x]] . By Lemma 8.2, the gek form a standard basis of
I. This proves the theorem.

10. Construction of reduced standard basis
The central part in establishing the division algorithm for modules of algebraic power series
vectors is the construction of a reduced standard basis. The mere existence follows from
Hironaka’s theorem. The effective part in the special case of principal ideals, i.e., the
construction of the code of the Weierstrass form of an xn -regular algebraic power series, has
been established by Alonso, Mora and Raimondo [AMR, Thm. 5.5]. The general statement
is as follows:
Theorem 10.1. Let I be a submodule of K[[x]]s generated by algebraic power series
vectors. Assume that I satisfies Hironaka’s box condition with respect to a monomial order
<η on Nn × {1, . . . , s}. Then the family codes of a reduced standard basis of I can be
computed by a finite algorithm from the family codes of any algebraic power series vectors
g1 , . . . , gr ∈ K[[x]]s generating I.
The proof of this result is given in sections 13 to 15. In the formal power series case, a reduced
standard basis can be constructed up to any given degree by dividing monomial generators of
the initial module by the module itself. For algebraic series, this construction would require
to dispose already of an effective division algorithm. To avoid this logical cycle, reduced
standard bases have to be constructed in a different way.
The clue relies in the concept of a virtual reduced standard basis. Such a basis consists
of polynomial vectors whose coefficients are unknown and written as new variables. Upon
replacing the variables by suitable series in x, the virtual reduced standard basis will transform
into an actual reduced standard basis of the module. The resulting coefficient series of the
actual reduced standard basis – more precisely, their codes – are computed by dividing the
polynomial generators of the module h(yi − hi ) · eℓ , gk i = hHi · eℓ , Gk i by the virtual basis
using the polynomial division algorithm. The definition requires that both the generators and
the virtual basis are polynomial vectors, and that the initial monomial vectors of the virtual
reduced standard basis can be interpreted as the leading (i.e., maximal) monomial vectors
w.r.t. another, suitably chosen monomial order. The choice of this order is rather subtle, see
section 13. The remainders of the division then allow us to extract the codes of the required
coefficients series.

11. Effective division for algebraic power series
Our main result asserts that the division by modules of algebraic power series vectors with box
condition can be made effective, i.e., can be performed by applying finitely many operations
to the codes. The case of principal ideals I, say the effective Weierstrass Division Theorem
for algebraic power series, is due to Alonso, Mora and Raimondo in [AMR, Thm. 5.6].
Theorem 11.1. Let I be a submodule of K[[x]]s generated by algebraic power series
vectors. Assume that I satisfies Hironaka’s box condition with respect to a monomial order
<η on Nn × {1, . . . , s}. Let be given the family codes of algebraic power series vectors
g1 , . . . , gr ∈ K[[x]]s generating I. There exists a finite algorithm which computes, for
any algebraic power series vector f ∈ K[[x]]s , from the family code of f the family codes
of algebraic power series a1 , . . . , ar in K[[x]] and of an algebraic power series vector
c ∈ co(I) ⊂ K[[x]]s so that
Pr
f = k=1 ak gk + c
13

is a formal power series division of f by g1 , . . . , gr .
The algorithm produces quotients ak which are algebraic series but which in general need not
satisfy the support conditions of the formal power series division as in [Ga]. The remainder
c, of course, is unique and only depends on the chosen monomial order <η .
We shall prove Theorem 11.1 by first constructing from g1 , . . . , gr via Theorems 9.1 and
10.1 the family codes of a reduced standard basis of I. The division algorithm for a reduced
standard basis will then be established by induction on the number of variables.

12. Logical structure of the proofs of Theorems 10.1 and 11.1
Both theorems will be established independently of Hironaka’s existential division theorem.
We start with establishing Theorem 10.1, the construction of the codes of a reduced standard
basis, in the special case of xn -regular modules. This is the hardest part of the whole story.
It relies on introducing the virtual reduced standard basis of the module, which allows us to
perform polynomial divisions for constructing the required codes. This section is inspired by
Mora’s tangent cone algorithm and the techniques of Alonso, Mora and Raimondo in [AMR].
Extracting from the virtual reduced standard basis the actual reduced standard basis uses in
an essential way the assumption of xn -regularity.
From Theorem 10.1 for xn -regular modules we deduce the division algorithm of Theorem
11.1 for xn -regular modules. The algorithm uses again a polynomial division, this time by
the codes of the reduced standard basis. For its termination it is necessary that the basis is
already reduced.
The general cases of Theorems 10.1 and 11.1 are then deduced simultaneously from the
special cases by induction on the number of variables and using Hironaka’s box condition
together with the notion of Janet basis. One selects from the given (not yet reduced) standard
basis of the module those elements which are xn -regular. Such elements exist because of the
box condition. Considering the module generated by these elements, one may construct the
codes of its reduced standard basis via Theorem 10.1 in the special case. Then Theorem 11.1
allows us to reduce effectively the remaining elements with respect to the first set of elements.
By induction on the number of variables, the tails of the first elements can now be divided
conversely by the remaining elements, yielding eventually the codes of the whole reduced
standard basis of the module. Once this is achieved, it is relatively simple to establish also
the division of Theorem 11.1 in the general case.

13. Proof of Theorem 10.1 for xn -regular modules
In the situation of Theorem 10.1, we first treat the case where I is xn -regular with respect to
<η . As seen in Lemmata 8.1 and 8.2, it suffices to construct the family code of a reduced
standard basis of the submodule Ie = hHi · eℓ , Gk i = h(yi − hi ) · eℓ , gk i of K[[x, y]]s with
respect to the chosen extension <ε of <η . Note here that Ie is not xn -regular, since also the
yi · eℓ appear in the initial module. This is, however, not a serious drawback. The proof is
somewhat involved and goes in several steps. Let us first specify the setting.
(a) We suppose that the generators gk of I vanish at 0 for all 1 ≤ k ≤ r. Hence this
also holds for all Hi · eℓ and Gk . We may assume by Theorem 9.1 and its proof that the
e As I is xn -regular
polynomial vectors Hi · eℓ and Gk form a minimal standard basis of I.
e is generated by yi · eℓ and monomial vectors
and in(Hi · eℓ ) = yi · eℓ , the initial module in(I)
dk
xn · emk for some dk > 0, 1 ≤ mk ≤ s and 1 ≤ k ≤ r. Hence r ≤ s. After a suitable
permutation of the components of K[[x]]s and a renumeration of G1 , . . . , Gr we may assume
that mk = k, say in(Gk ) = xdnk · ek for all k. The permutation of the components is only for
14

notational convenience. It will not affect the induction we shall apply later on when proving
Theorems 10.1 and 11.1 in the general case.
e of in(I)
e in K[[x, y]]s is of form
The canonical direct monomial complement co(I)
e = ⊕rm=1 ⊕dm −1 K[[x′ ]] · xjn · em ⊕ ⊕sm=r+1 K[[x]] · em .
co(I)
j=0

Write a reduced standard basis of Ie as
Pr
Pdm −1
Ps
biℓ = yi · eℓ − b◦iℓ − m=1 j=0
uiℓmj (x′ ) · xjn · em − m=r+1 viℓm (x) · em ,
bk = xdnk · ek − b◦k −

Pr

m=1

Pdm −1
j=0

ukmj (x′ ) · xjn · em −

Ps

m=r+1 vkm (x)

· em ,

with polynomial vectors b◦iℓ and b◦k in
m −1
⊕rm=1 ⊕dj=0
Kxjn · em ⊕ ⊕sm=r+1 K · em

and power series uiℓmj (x′ ), viℓm (x), ukmj (x′ ) and vkm (x) vanishing at 0. It is necessary
here to split off b◦iℓ and b◦k because the mother codes of algebraic power series are only defined
for series vanishing at 0. Note that uiℓmj (x′ ) and ukmj (x′ ) do not depend on xn , and that
b◦iℓ and b◦k vanish at 0 because the Hi · eℓ and Gk do. In particular, these vectors have zero
entries in the last s − r components. Since inε (biℓ ) = yi · eℓ and inε (bk ) = xdnk · ek the ℓ-th
component of b◦iℓ and the k-th component of b◦k are both zero.
The series biℓ have different shapes according to whether 1 ≤ ℓ ≤ r or r + 1 ≤ ℓ ≤ s.
Namely, for r + 1 ≤ ℓ ≤ s, it follows from the xn -regularity of I that the vectors (yi − hi ) · eℓ
are already reduced. Hence we have biℓ = (yi − hi ) · eℓ for r + 1 ≤ ℓ ≤ s. This will be used
later on. We are grateful to D. Wagner for specifying an inaccuracy which appeared at this
place in an earlier draft of the paper.
In a first step, we determine the vectors b◦iℓ and b◦k . Afterwards, the family codes of the
coefficient series uiℓmj (x′ ), viℓm (x), ukmj (x′ ) and vkm (x) will be constructed. This will
show in particular that they are algebraic series.
(b) In order to compute b◦iℓ and b◦k , one can construct the reduced standard basis of Ie up to a
sufficiently high degree by applying its formal power series construction modulo a sufficiently
high power of the maximal ideal of K[[x, y]].
(c) The series uiℓmj (x′ ), viℓm (x), ukmj (x′ ) and vkm (x) will be determined by a trick which
has already appeared in the literature, see e.g. [AMR]: Define the virtual reduced standard
basis of Ie as the polynomial vectors
Ps
Pdm −1
Pr
uiℓmj · xjn · em − m=r+1 viℓm · em ,
Biℓ = yi · eℓ − b◦iℓ − m=1 j=0
Bk = xdnk · ek − b◦k −

Pr

m=1

Pdm −1
j=0

ukmj · xjn · em −

Ps

m=r+1 vkm

· em ,

where uiℓmj , viℓm , ukmj and vkm are now new variables (to be abbreviated by u and v). From
these we shall construct certain polynomials Uiℓmj , Viℓm , Ukmj and Vkm in K[x, y, u, v]. All
these together will constitute the mother code (U, V ) of the baby series vector (u(x′ ), v(x))
of components uiℓmj (x′ ), ukmj (x′ ), respectively viℓm (x), vkm (x). And, consequently, Biℓ
and Bk will be the father codes of the series vectors biℓ and bk we were looking for, with
biℓ , bk ∈ K[x, y, u(x′ ), v(x)]s .
We have noticed above that, for r + 1 ≤ ℓ ≤ s, the vectors biℓ equal (yi − hi ) · eℓ . As the
polynomial vectors Biℓ are the father codes of biℓ they will therefore have, for r + 1 ≤ ℓ ≤ s,
only one non-zero entry, namely in the ℓ’s component. Hence we may set all variables uiℓmj ,
viℓm for r + 1 ≤ m ≤ s and m 6= ℓ equal to 0. This will be used below when proving the
independence of Uiℓmj and Ukmj on v.
15

(d) The construction of the codes U and V uses the polynomial division algorithm with
respect to a suitably chosen monomial order. Compare monomial vectors uγ v δ xα y β · em by
considering the integer vector
(β, αn − dm , α′ , −m, γ, δ)
lexicographically. Here, the tuples γ and δ are taken as ordered vectors, e.g. by choosing
some ordering of their indices. It is easily checked that this defines a monomial order <ω
on Nq+n+p , where q is the number of u and v variables, and that the leading (= maximal)
monomial vectors of Biℓ and Bk w.r.t. <ω are yi · eℓ and xdnk · ek .
We now divide Hi · eℓ and Gk polynomially by Bιλ and Bκ with respect to this monomial
order, say with leading monomial vectors yι · eλ and xdnκ · eκ and the scopes nιλ = q + n + ι
and nκ = q + n (with 1 ≤ ι ≤ p, 1 ≤ λ ≤ s and 1 ≤ κ ≤ r). The division yields in finitely
many steps remainders Riℓ and Rk in the canonical direct monomial complement
e = ⊕rm=1 (⊕dm −1 K[u, v][[x′ ]] · xjn ) · em ⊕ ⊕sm=r+1 K[u, v][[x]] · em
K[u, v] ⊗ co(I)
j=0

e in K[u, v][[x, y]]s . Expanding these remainders as polynomial vectors in
of K[u, v] ⊗ in(I)
xn yields
Pr
Pdm −1
Ps
Riℓ = m=1 j=0
Uiℓmj · xjn · em + m=r+1 Viℓm · em ,
Pr
Pdm −1
Ps
Rk = m=1 j=0
Ukmj · xjn · em + m=r+1 Vkm · em ,
with polynomials Uiℓmj , Ukmj in K[u, x′ ] and Viℓm , Vkm in K[u, v, x]. Note here that Uiℓmj
and Ukmj do not depend on v because viℓm and vkm only appear in the last s − r components
of Biℓ and Bk and because uiℓmj and viℓm can a priori be set equal to 0 for m 6= ℓ.
(e) We show that U and V have no constant terms. Replacing in Riℓ and Rk the variables u
and v by the series u(x′ ) and v(x) produces power series vectors riℓ and rk which belong to
e because u(x′ ) does not depend on xn and U does not depend on v. But by construction,
co(I)
e From the formal power series division follows that both riℓ and
riℓ and rk also belong to I.
e that
rk are identically zero. This in turn implies by the direct sum decomposition of co(I)
′
′
replacing in U and V the variables u and v by u(x ) and v(x) gives zero. As u(x ) and v(x)
have no constant term, also U and V have no constant term.
(f) We show that U and V form a mother code of certain baby series. By the description
of mother codes it suffices to find a monomial order <ξ on Nq+n+p × {1, . . . , s} such that
the respective initial monomials of Uiℓmj (0, 0, u, v), Viℓm (0, 0, u, v), Ukmj (0, 0, u, v) and
Vkm (0, 0, u, v) are uiℓmj , viℓm , ukmj and vkm . By taking an order which is compatible
with the degree in the u and v variables it suffices to prove the above for the linear parts of
Uiℓmj (0, 0, u, v), Viℓm (0, 0, u, v), Ukmj (0, 0, u, v) and Vkm (0, 0, u, v).
These linear parts are given by the first substitution step of the polynomial division as
the coefficients of xjn · em (with 1 ≤ j ≤ dm − 1, 1 ≤ m ≤ r) respectively em (with
r + 1 ≤ m ≤ s), when dividing Hi · eℓ and Gk by the vectors Bιλ and Bκ (1 ≤ ι ≤ p,
1 ≤ λ ≤ s, 1 ≤ κ ≤ r) with leading monomial vectors yι · eλ and xdnκ · eκ and scopes
q + n + ι, respectively q + n. Here, the y variables are ordered naturally y1 , . . . , yp , so that
the scope q + n + ι of yι · eλ allows multiplication of Bιλ with polynomials in x1 , . . . , xn ,
y1 , . . . , yι and all u and v variables.
Note that the polynomial vectors b◦ιλ and b◦κ of K[x]s appearing in Bιλ and Bκ vanish at
zero and hence do not contribute to the linear terms of Uiℓmj (0, 0, u, v), Viℓm (0, 0, u, v),
Ukmj (0, 0, u, v) and Vkm (0, 0, u, v).
The construction of the monomial order <ξ on Nq+n+p × {1, . . . , s} involves a monomial
order <ζ on Nq (recall that q is the number of u and v variables) whose choice is motivated by
16

the following computations (where we shall assume throughout w.l.o.g. that in(Hi ·eℓ ) = yi ·eℓ
and in(Gk ) = xdnk · ek ).
Linear terms of Uiℓmj (0, 0, u, v): These occur after the first substitution step of the polynomial
division as the coefficients of xjn ·em (with 1 ≤ i ≤ p, 1 ≤ ℓ ≤ s, 1 ≤ m ≤ r, 1 ≤ j ≤ dm −1)
when dividing Hi · eℓ by the vectors Bιλ and Bκ with leading monomial vectors yι · eλ and
xdnκ ·eκ and scopes q +n+ι, respectively q +n (where ι, λ and κ vary in the ranges 1 ≤ ι ≤ p,
1 ≤ λ ≤ s, 1 ≤ κ ≤ r). Notice that the polynomials Uiℓmj do not depend on y and v.
Let xρ y σ · eℓ be a monomial vector of the expansion of Hi · eℓ , with ρ ∈ Nn , σ ∈ Np . If it is
a multiple of the leading monomial vectors yι · eλ , respectively xdnκ · eκ , of Bιλ , respectively
Bκ , subject to the correct scope conditions, it will be replaced in the polynomial division by
the according multiple of the tails B ιλ , respectively B κ . After the substitution we have to
look at the coefficient of xjn · em and set x = 0 and y = 0. We distinguish three cases.
(i) The substitution of the monomial vector yi · eℓ of Hi · eℓ by B iℓ produces in the coefficient
of xjn · em the summand uiℓmj . The order <ζ has to be chosen so that this monomial is the
smallest one among the monomials of this coefficient (after having set x = 0 and y = 0).
(ii) A general monomial vector xρ y σ · eℓ of Hi · eℓ is a multiple of the leading monomial
vector yι · eλ of Bιλ with scope q + n + ι and contributes to the coefficient of xjn · em (for
some 1 ≤ m ≤ r and 0 ≤ j ≤ dm − 1, and after having set x = 0 and y = 0) if and only
if λ = ℓ, ρ = (0, . . . , 0, ρn ) with ρn ≤ j and σ = eι , say xρ y σ · eλ = xρnn yι · eλ . The only
contributions can be constant multiples of uιλmj ′ with j ′ + ρn = j. Note then that for this to
happen we must have xρnn yι · eλ >ε in(Hi · eλ ) (otherwise this monomial does not appear in
Hi · eλ ). Therefore <ζ should satisfy
for j ′ ≤ j and xρnn yι · eλ >ε yi · eλ ,

uιλmj ′ >ζ uiλmj

′

say j ′ ≤ j and xjn · in(Hι · eλ ) >ε xjn · in(Hi · eλ ).
(iii) A general monomial vector xρ y σ · eℓ of Hi · eℓ is a multiple of the leading monomial
vector xdnκ ·eκ of Bκ with scope q +n and contributes to the coefficient of xjn ·em (after having
set x = 0 and y = 0) if and only if κ = ℓ, ρ = (0, . . . , 0, ρn ) with ρn = dκ + t for some t ≥ 0
and σ = (0, . . . , 0), say xρ y σ ·eλ = xρnn ·eκ . The only contributions can be constant multiples
of uκmj ′ with t + j ′ = j. Note then that we must have xρnn · eκ >ε in(Hi · eκ ) = yi · eκ and
therefore <ζ should satisfy
for j ′ ≤ j and xρnn · eκ >ε yi · eκ ,

uκmj ′ >ζ uiκmj

′

say j ′ ≤ j and xjn · in(Gκ ) >ε xjn · in(Hi · eκ ).
Linear terms of Viℓm (0, 0, u, v): These occur after the first substitution step of the polynomial
division as the coefficients of em (with 1 ≤ i ≤ p, 1 ≤ ℓ ≤ s, r + 1 ≤ m ≤ s) when dividing
Hi · eℓ by the vectors Bιλ and Bκ with leading monomial vectors yι · eλ and xdnκ · eκ and
scopes q + n+ ι, respectively q + n (where ι, λ and κ vary in the ranges 1 ≤ ι ≤ p, 1 ≤ λ ≤ s,
1 ≤ κ ≤ r).
Let xρ y σ · eℓ be a monomial vector of the expansion of Hi · eℓ , with ρ ∈ Nn , σ ∈ Np . If it is
a multiple of the leading monomial vectors yι · eλ , respectively xdnκ · eκ , of Bιλ , respectively
Bκ , subject to the correct scope conditions, it will be replaced in the polynomial division by
the according multiple of the tails B ιλ , respectively B κ . After the substitution we have to
look at the coefficient of em and set x = 0 and y = 0. We distinguish three cases.
(i) The substitution of the monomial vector yi · eℓ of Hi · eℓ by B iℓ produces in the coefficient
of em the summand viℓm . The order <ζ has to be chosen so that this monomial is the smallest
one among the monomials of this coefficient (after having set x = 0 and y = 0).
17

(ii) A general monomial vector xρ y σ · eℓ of Hi · eℓ is a multiple of the leading monomial
vector yι · eλ of Bιλ with scope q + n + ι and contributes to the coefficient of em (after having
set x = 0 and y = 0) if and only if ℓ = λ, ρ = (0, . . . , 0) and σ = eι , say xρ y σ · eλ = yι · eλ .
The only contributions can be constant multiples of vιλm . For this to happen we must have
yι · eλ >ε in(Hi · eλ ) (otherwise this monomial does not appear in Hi · eλ ). Therefore <ζ
should satisfy
vιλm >ζ viλm

for yι · eλ >ε yi · eλ ,
say in(Hι · eλ ) >ε in(Hi · eλ ).

(iii) A general monomial vector xρ y σ · eℓ of Hi · eℓ is a multiple of the leading monomial
vector xdnκ · eκ of Bκ with scope q + n and contributes to the coefficient of em (after having set
x = 0 and y = 0) if and only if κ = ℓ, ρ = (0, . . . , 0, ρn ) with ρn = dκ and σ = (0, . . . , 0),
say xρ y σ · eλ = xdnκ · eκ . The only contributions can be constant multiples of vκm . Note then
that we must have xdnκ · eκ >ε in(Hi · eκ ) and therefore <ζ should satisfy
for xdnκ · eκ >ε in(Hi · eκ ),

vκm >ζ viκm

say in(Gκ ) >ε in(Hi · eκ ).
Linear terms of Ukmj (0, 0, u, v): These occur after the first substitution step of the polynomial
division as the coefficients of xjn · em (with 1 ≤ k ≤ r, 1 ≤ m ≤ r, 0 ≤ j ≤ dm − 1) when
dividing Gk by the vectors Bιλ and Bκ with leading monomial vectors yι · eλ and xdnκ · eκ
and scopes q + n + ι, respectively q + n (where ι, λ and κ vary in the ranges 1 ≤ ι ≤ p,
1 ≤ λ ≤ s, 1 ≤ κ ≤ r).
Let xρ y σ · eλ be a monomial vector of the expansion of Gk , with ρ ∈ Nn , σ ∈ Np . If it is a
multiple of the leading monomial vectors yι · eλ , respectively xdnκ · eκ , of Bιλ , respectively
Bκ , subject to the correct scope conditions, it will be replaced in the polynomial division by
the according multiple of the tails B ιλ , respectively B κ . After the substitution we have to
look at the coefficient of xjn · em and set x = 0 and y = 0. We distinguish three cases.
(i) The substitution of the monomial vector xdnk · ek of Gk by B k produces in the coefficient
of xjn · em the summand ukmj . The order <ζ has to be chosen so that this monomial is the
smallest one among the monomials of this coefficient (after having set x = 0 and y = 0).
(ii) A general monomial vector xρ y σ · eκ of Gk is a multiple of the leading monomial vector
yι · eλ of Bιλ with scope q + n + ι and contributes to the coefficient of xjn · em (after
having set x = 0 and y = 0) if and only if κ = λ, ρ = (0, . . . , 0, ρn ) and σ = eι , say
xρ y σ · eλ = xρnn yι · eλ . The only contributions can be constant multiples of uιλmj ′ with
ρn + j ′ = j, say ρn = j − j ′ . For this to happen we must have xρnn yι · eλ >ε in(Gk )
(otherwise this monomial does not appear in Gk ). Therefore <ζ should satisfy
for j ′ ≤ j and xρnn yι · eλ >ε xdnk · ek ,

uιλmj ′ >ζ ukmj

′

say j ′ ≤ j and xjn · in(Hι · eλ ) >ε xjn · in(Gk ).
(iii) A general monomial vector xρ y σ · eκ of Gk is a multiple of the leading monomial vector
xdnκ · eκ of Bκ with scope q + n and contributes to the coefficient of xjn · em (after having set
x = 0 and y = 0) if and only if ρ = (0, . . . , 0, ρn ) with ρn ≥ dκ and σ = (0, . . . , 0), say
xρ y σ · eλ = xρnn · eκ with ρn = dκ + t for some t ≥ 0. The only contributions can be constant
multiples of uκmj ′ with t + j ′ = j. Note then that we must have xndκ +t · eκ >ε in(Gk ) and
therefore <ζ should satisfy
for j ′ ≤ j and xndκ +t · eκ >ε in(Gk ),

uκmj ′ >ζ ukmj

′

say j ′ ≤ j and xjn · in(Gκ ) >ε xjn · in(Gk ).
18

Linear terms of Vkm (0, 0, u, v): These occur after the first substitution step of the polynomial
division as the coefficients of em (with 1 ≤ k ≤ r, r + 1 ≤ m ≤ s) when dividing Gk by the
vectors Bιλ and Bκ with leading monomial vectors yι · eλ and xdnκ · eκ and scopes q + n + ι,
respectively q + n (where ι, λ and κ vary in the ranges 1 ≤ ι ≤ p, 1 ≤ λ ≤ s, 1 ≤ κ ≤ r).
Let xρ y σ · eκ be a monomial vector of the expansion of Gk , with ρ ∈ Nn , σ ∈ Np . If it is a
multiple of the leading monomial vectors yι · eλ , respectively xdnκ · eκ , of Bιλ , respectively
Bκ , subject to the correct scope conditions, it will be replaced in the polynomial division by
the according multiple of the tails B ιλ , respectively B κ . After the substitution we have to
look at the coefficient of em and set x = 0 and y = 0. We distinguish three cases.
(i) The substitution of the monomial vector xdnk · ek of Gk by B k produces in the coefficient
of em the summand vkm . The order <ζ has to be chosen so that this monomial is the smallest
one among the monomials of this coefficient (after having set x = 0 and y = 0).
(ii) A general monomial vector xρ y σ · eκ of Gk is a multiple of the leading monomial vector
yι · eλ of Bιλ with scope q + n + ι and contributes to the coefficient of em (after having set
x = 0 and y = 0) if and only if κ = λ, ρ = (0, . . . , 0) and σ = eι , say xρ y σ · eλ = yι · eλ .
The only contributions can be constant multiples of vιλm . For this to happen we must have
yι · eλ >ε in(Gk ) (otherwise this monomial does not appear in Gk ). Therefore <ζ should
satisfy
vιλm >ζ vkm

for yι · eλ >ε in(Gk ),
say in(Hι · eλ ) >ε in(Gk ).

(iii) A general monomial vector xρ y σ · eκ of Gk is a multiple of the leading monomial vector
xdnκ · eκ of Bκ with scope q + n and contributes to the coefficient of em (after having set
x = 0 and y = 0) if and only if ρ = (0, . . . , 0, ρn ) with ρn = dκ and σ = (0, . . . , 0), say
xρ y σ · eκ = xdnκ · eκ . The only contributions can be constant multiples of vκm . Note then
that we must have xdnκ · eκ >ε in(Gk ) and therefore <ζ should satisfy
for xdnκ · eκ >ε in(Gk ),

vκm >ζ vkm

say in(Gκ ) >ε in(Gk ).
This concludes the computation of the required inequalities for the order <ζ on Nq . It will be
a monomial order on Nq , where q is the number of the variables u and v, and has to be graded
lexicographic subject to the following relations
′

uιℓmj ′ >ζ uiℓmj

if j ′ ≤ j and xjn · in(Hι · eℓ ) >ε xjn · in(Hi · eℓ ),

uiℓmj ′ >ζ ukmj

if j ′ ≤ j and xjn · in(Hi · eℓ ) >ε xjn · in(Gk ),

uikmj ′ <ζ ukmj

if j ′ ≥ j and xjn · in(Hi · ek ) <ε xjn · in(Gk ),

uκmj ′ >ζ ukmj

if j ′ ≤ j and xjn · in(Gκ ) >ε xjn · in(Gk ),

′

′

′

vιℓm >ζ viℓm

if in(Hι · eℓ ) >ε in(Hi · eℓ ),

viℓm >ζ vkm

if in(Hi · eℓ ) >ε in(Gk ),

vikm <ζ vkm

if in(Hi · ek ) <ε in(Gk ),

vκm >ζ vkm

if in(Gκ ) >ε in(Gk ).

The indices vary in the regions
1 ≤ i, ι ≤ p,
1 ≤ ℓ ≤ s,
1 ≤ m ≤ r,
19

1 ≤ j, j ′ ≤ dm − 1 and
1 ≤ k, κ ≤ r
for the u variables, respectively in the regions
1 ≤ i, ι ≤ p,
1 ≤ ℓ ≤ s,
r + 1 ≤ m ≤ s and
1 ≤ k, κ ≤ r
for the v variables. It is checked that the inequalities for <ζ do not contradict each other, i.e.,
that there actually does exist a monomial order <ζ fulfilling the eight conditions.
We now extend <ε to a monomial order <ξ on Nq+n+p × {1, . . . , s} defined by
(γ, α, β, ℓ) <ξ (γ ′ , α′ , β ′ , ℓ′ )

if

(|γ|, (α, β, ℓ), γ) <lex (|γ ′ |, (α′ , β ′ , ℓ′ ), γ ′ ).

Here, <lex denotes the lexicographic order on N × (Nn+p × {1, . . . , s}) × Nq , where |γ| and
|γ ′ | are compared as elements of N with the natural order, (α, β, ℓ) and (α′ , β ′ , ℓ′ ) as elements
of Nn+p × {1, . . . , s} with the order <ε , and γ and γ ′ as elements of Nq with respect to the
order <ζ . The inequalities which were imposed on <ζ ensure that – as shown above – the
initial monomials with respect to <ξ of the linear terms of Uiℓmj (0, 0, u, v), Viℓm (0, 0, u, v),
Ukmj (0, 0, u, v) and Vkm (0, 0, u, v) are uiℓmj , viℓm , ukmj and vkm . This was needed to
show that U and V satisfy the properties of a mother code.
(g) We show that u(x′ ) and v(x) are the baby series of U and V . By definition, u(x′ ) and
v(x) vanish at zero. We have already seen in part (d) above that riℓ = Riℓ (x, u(x′ ), v(x)) and
rk = Rk (x, u(x′ ), v(x)) are zero. As u(x′ ) does not depend on xn and U does not depend on
e that U (x, u(x′ )) and V (x, u(x′ ), v(x)) are zero.
v it follows from the decomposition of co(I)
This is what had to be shown and concludes the proof of Theorem 10.1 in the xn -regular case.

14. Proof of Theorem 11.1 for xn -regular modules
By Theorem 9.1 we may assume that the module I is given by a minimal standard basis
g1 , . . . , gr ∈ K[[x]]s with initial monomial vectors xdnk · ek . Let (H, G) ∈ K[x, y]p ×
K[x, y]s×r be the family code of g1 , . . . , gr and let h = (h1 , . . . , hp ) be the baby series
vector of the mother code H = (H1 , . . . , Hp ) ∈ K[x, y]p , so that gk = Gk (x, h(x)).

By Lemma 8.1 the submodule Ie = h(yi − hi ) · eℓ , gk i of K[[x, y]]s equals hHi · eℓ , Gk i.
Let <ε be an extension of <η to Nn+p × {1, . . . , s} with yi · eℓ <ε xj · eℓ for all i, j and ℓ
as defined in Lemma 8.2. By Theorem 10.1 in the xn -regular case we may assume that we
already dispose of a reduced standard basis biℓ , bk of Ie with initial monomial vectors yi · eℓ
and xdnk · ek with respect to <ε . The father code of biℓ , bk is given by the virtual reduced
e the mother code is the vector (U, V ) of components Uiℓmj , Viℓm ,
standard basis Biℓ , Bk of I,
Ukmj and Vkm . We denote by (u(x′ ), v(x)) with components uiℓmj (x′ ), viℓm (x), ukmj (x′ )
and vkm (x) the corresponding baby series vector.
We wish to divide an algebraic power series vector f ∈ K[[x]]s by the submodule I = hgk i
of K[[x]]s . We may assume that f has the same baby series vector h as g1 , . . . , gr . Write
f = F (x, h(x)) ∈ K[x, h]s with father code F ∈ K[x, y]s . We divide F by the polynomial
vectors Biℓ and Bk according to the polynomial division algorithm (Theorem 4.4) with leading
monomial vectors yi · eℓ and xdnk · ek and scopes q + n + i, respectively q + n (we recall that n
is the number of x-variables, q is the number of u- and v-variables). We get a decomposition
P e
P e
F = A
Ak · Bk + C
iℓ · Biℓ +
20

eiℓ in K[u, v, x, y], A
ek in K[u, v, x], and a polynomial vector
with some polynomials A
e Replacing in this equation y by h(x), u by u(x′ ) and v by v(x) yields
C ∈ K[u, v] ⊗ co(I).
a decomposition
P
P
f = ãiℓ · b̃iℓ + ãk · bk + c
for some algebraic power series ãiℓ , ãk ∈ K[[x]] and an algebraic power series vector c ∈
K[[x]]s . The vectors b̃iℓ and bk are obtained from Biℓ and Bk by substitution of the variables.
(a) The vector c has mother code H, U and V and father code C. Expand C into
Pr
Pdm −1
Ps
C = m=1 j=0
Cmj (u, x′ ) · xjn · em + m=r+1 Cm (u, v, x) · em ,

with polynomials Cmj (u, x′ ) and Cm (u, v, x). Observe that, similarly as in section 13, part
(c), the polynomials Cmj (u, x′ ) will not depend on v. Substituting in C the variables u and
v by u(x′ ) and v(x) we obtain for c the decomposition
Pr
Pdm −1
Ps
c = m=1 j=0
Cmj (u(x′ ), x′ ) · xjn · em + m=r+1 Cm (u(x′ ), v(x), x) · em .
Therefore c ∈ co(I) as required.
(b) We will show that the vectors b̃iℓ belong to the module hbk i, thus getting a decomposition
P
f = ak · b k + c
for some power series ak ∈ K[[x]]. To this end, recall that h(yi − hi ) · eℓ , gk i = hbiℓ , bk i (as
submodules of K[[x, y]]s ) and that the vectors bk do not depend on yi . Thus the replacement
of yi by hi does not affect them and gives hbk i ⊂ hgk i. As the initial modules of these
two modules are equal (being generated by xdnk · ek for 1 ≤ k ≤ r), the Division Theorem
for power formal series yields equality hgk i = hbk i. This shows that the biℓ belong to
the submodule h(yi − hi ) · eℓ , bk i of K[[x, y]]s . Therefore, replacing yi by hi in biℓ yields
b̃iℓ ∈ hbk i ⊂ K[[x]]s .
(c) We finally show that the power series ak ∈ K[[x]] are algebraic and that their codes can
be computed algorithmically. For this we will express constructively the father codes Biℓ of
b̃iℓ in terms of Bk and Hi · eℓ .
The problem which we have to solve here is the following: Assume given a submodule J of
K[[x]]s generated by polynomial vectors P1, . . . , Pr , and let Q be a polynomial vector. We use
Algorithm 1.7.6 of [GP] computing the polynomial weak normal form of a polynomial with
respect to a polynomially generated ideal in a power series ring, together with the comment at
the bottom of page 58. By definition of the polynomial weak normal form [GP, def. 1.6.5], we
P
get the construction of a decomposition SQ =
Wk Pk + R with polynomials S, Wk and
R such that S(0) 6= 0, where R equals the remainder of the formal power series division of
SQ by P1 , . . . , Pr . In case that Q already belongs to the ideal generated by P1 , . . . , Pr in the
P
fk Pk with rational coefficients
W
power series ring, this decomposition specializes to Q =
f
Wk = Wk /S in the localization of the polynomial ring at 0.

Apply this technique to the polynomial vectors Biℓ and the submodule J = hBk , Hi · eℓ , U ·
eℓ , V · eℓ i of K[[x, y, u, v]]s (with the obvious abbreviations for U and V ). By definition,
J is generated by polynomial vectors. We have to check that Biℓ ∈ J. For this, recall that
Ie = hHi · eℓ , Gk i = hbiℓ , bk i as submodules of K[[x, y]]s and that b̃iℓ ∈ hbk i in K[[x]]s .
Then, by construction of U and V , we get the equalities
hBiℓ , Bk , Hi · eℓ , U · eℓ , V · eℓ i = hb̃iℓ , bk , Hi · eℓ , U · eℓ , V · eℓ i
= hbk , Hi · eℓ , U · eℓ , V · eℓ i
= hBk , Hi · eℓ , U · eℓ , V · eℓ i
= J.
21

We conclude that Biℓ ∈ J. This shows that we can write Biℓ as a linear combination of the
Bk , Hι · eλ , U · eλ , V · eλ with constructible rational power series coefficients, say
P
modulo H, U and V ,
Biℓ = iℓk Wiℓk Bk

where Wiℓk ∈ K[[x, y, u, v]] are rational functions. Upon replacing yi by hi , u by u(x′ ) and
v by v(x) only the Bk will subsist (the evaluations of the other polynomial vectors Hι · eλ ,
U · eλ , V · eλ vanish). This shows that the Wiℓk are the father codes of the coefficients wiℓk in
P
the linear combinations b̃iℓ = iℓk wiℓk bk expressing b̃iℓ in terms of bk . The mother codes
are the components of the polynomial vectors H, U and V .
By definition of ak in terms of ãiℓ and ãk it now follows that the series ak are algebraic and
that their family codes can be constructed by a finite algorithm. This establishes Theorem
11.1 for xn -regular modules.

15. Proofs of Theorems 10.1 and 11.1 in the general case
The idea for proving both theorems in the general case is to split a given minimal standard
basis of I into two groups specified by the variables appearing in their initial monomial
vectors. The first group consists of generators whose initial monomial vectors are pure xn powers. The remaining generators have initial monomial vectors which involve also some
other variable.
So let be given, by Theorem 9.1, vectors g1 , . . . , gr which form a minimal standard basis
of I. Adding suitable monomial multiples of the gk we may assume that g1 , . . . , gr form
a minimal Janet basis of I with scopes n1 , . . . , nr . We order g1 , . . . , gr and permute the
components of K[[x]]s so that, for some 1 ≤ t ≤ r, the vectors g1 , . . . , gt are xn -regular with
initial monomial vectors xdnk · ek , and so that the initial monomial vectors of the remaining
gt+1 , . . . , gr involve at least one of the variables x1 , . . . , xn−1 . It is easy to see that the scopes
nt+1 , . . . , nr of gt+1 , . . . , gr are all < n. This implies that
P
P
I = tk=1 K[[x]] · gk + rk=t+1 K[[x′ ]] · gk .
Therefore no gt+1 , . . . , gr need to be multiplied in the subsequent divisions by xn .
By Theorem 10.1 in the xn -regular case we may assume that g1 , . . . , gt form already a reduced
standard basis of the submodule I0 = hg1 , . . . , gt i of K[[x]]s . By Theorem 11.1 in the xn regular case we know how to divide gt+1 , . . . , gr by g1 , . . . , gt through a finite algorithm for
the respective family codes. This allows us to assume that gt+1 , . . . , gr belong to
Pt
Pdm −1
Ps
M = co(I0 ) = m=1 j=0
K[[x′ ]] · xjn · em + m=t+1 K[[x]] · em .
It follows from the box condition that the initial monomial vectors of gt+1 , . . . , gr have their
non-zero entry in the first summand
Pt
Pdm −1
M1 = m=1 j=0
K[[x′ ]] · xjn · em
Pr
of M . Setting I ′ = k=t+1 K[[x′ ]] · gk we have I ′ ⊂ M and in(I ′ ) ⊂ M1 . The monomial
order on Nn × {1, . . . , s} induces via the inclusion M ⊂ K[[x]]s in a natural way an ordering
of the monomial vectors in M .
We may now apply induction on n as follows.
First notice that in(I ′ ), as a submodule of the free finite K[[x′ ]]-module M1 , satisfies again
Hironaka’s box condition with respect to the induced ordering of the variables. Secondly, no
P
division occurs in the second summand M2 = sm=t+1 K[[x]] · em of M . Therefore, by
induction on the number of variables and discarding the (irrelevant) fact that the summand
M2 is not finitely generated as K[[x′ ]]-module, we may assume to know how to construct the
reduced standard basis of the K[[x′ ]]-submodule I ′ of M by a finite algorithm on the level
22

of codes. Notice that this basis, when considered as vectors in K[[x]]s , remains reduced with
respect to g1 , . . . , gt because its elements belong to M = co(I0 ).
So we may assume that gt+1 , . . . , gr already form a reduced standard basis of I ′ . By induction
on n we may apply the division algorithm of Theorem 11.1 to I ′ as a submodule of M . Thus
we know how to divide effectively algebraic power series vectors in M by I ′ .
Apply this to the tails g k = xdnk · ek − gk of g1 , . . . , gt . They belong to M since g1 , . . . , gt are
a reduced standard basis of I0 and M = co(I0 ). We divide these gk by I ′ . This allows us to
assume from the beginning that g1 , . . . , gt are reduced with respect to gt+1 , . . . , gr , i.e., that
g k ∈ co(I ′ ) for 1 ≤ k ≤ t. As I ′ ⊂ M = co(I0 ), the new g1 , . . . , gt form again a reduced
standard basis (the module they generate may be different from I0 , but its initial module is
the same). In total, we have found the reduced standard basis g1 , . . . , gr of I. This proves
Theorem 10.1.
As for Theorem 11.1, any algebraic power series vector f ∈ K[[x]]s we wish to divide
by I = hg1 , . . . , gr i can first be divided by I0 = hg1 , . . . , gt i using Theorem 11.1 in the
xn -regular case. It thus yields a remainder in M = co(I0 ). Then, using induction on n and
that I ′ satisfies the box condition in M , we may divide this remainder as vector in M by I ′ .
The resulting remainder can be interpreted, via the inclusion of M in K[[x]]s , as a vector in
co(I) ⊂ K[[x]]s . It will coincide with the remainder of the formal power series division of
P
f by I in K[[x]]s . It does not matter here that the second summand sm=t+1 K[[x]] · em of
M is not finitely generated as K[[x′ ]]-module, because no division occurs in the last s − r
components of f .
This establishes the division algorithm for algebraic power series vectors f in K[[x]]s by
submodules I with box condition. Theorem 11.1 is proven.

16. Example
In this section we show in a concrete situation how the algorithms of Theorem 10.1 and 11.1
work in practice (for more examples, see [Wa]). We will consider an ideal in three variables
generated by algebraic power series involving a single baby series. Our objective will be
the computation of the codes of the reduced standard basis of the ideal. As it will turn out,
the reduced standard basis will consist of polynomials, so that, at the end, there will be no
mother codes needed and the father codes of the basis coincide with the elements of the basis.
Nevertheless, the example is significant, since it is not at all clear how to construct the codes
of the reduced standard basis without using the techniques developed in the paper.
The example is chosen so as to illustrate the various aspects of the algorithm (reduction,
division, passage to vectors, induction on the number of variables). Some steps could also be
performed directly using some ad hoc tricks due to the simplicity of some of the generators
of the ideals and modules involved. This will be indicated correspondingly. Nevertherless,
all portions of the algorithm will show off at least once.
As a general rule, each step in the computations below will be followed by a renaming of the
involved objects so as to keep the presentation as systematic as possible. In the subsequent
step, letters will always refer to this renamed object and not to the original object defined at
earlier stages of the exposition.
The initial variables will be denoted x, y and z, corresponding to x1 , x2 and x3 in the text,
with this ordering. This will affect xn -regularity, being here first z-regularity, then, later,
y-regularity and finally x-regularity. Also, the involved polynomial divisions will use this
ordering of the variables.
23

The additional auxiliary variables appearing in the mother codes will be denoted by t1 , t2 , . . .
(instead of y1 , y2 , . . . as in the text). The respective baby series will be h1 , h2 , . . .
We consider the ideal I in K[[x, y, z]] generated by three power series g1 , g2 , g3 given as
g1 = z 2 + xyz + 14 xyz 2 + . . . =
= z 2 + xyh(z),
g2 = yz + x2 z + y 2 z,
g3 = y 2 + xyz.
Here,
h(z) = 1 −

√
1 − z = 12 z + 18 z 2 + . . .

is the only involved baby series. Its mother code H is taken as
H = 2t − t2 + z
(so that h = h(z) is the unique formal power series solution of H(z, t) = 0 satisfying
h(0) = 0.) Later on, when other mother codes will appear, we shall set t = t1 , h = h1 and
H = H1 . The father codes of g1 , g2 , g3 are
G1 = z 2 + xyt
G2 = yz + x2 z + y 2 z,
G3 = y 2 + xyz.
The last two G2 and G3 do not involve t because g2 and g3 are polynomials and hence
G2 = g2 and G3 = g3 . For our purposes it will be sufficient to have just one generator which
is a true series.
We wish to compute the family codes of the reduced standard basis of I = hg1 , g2 , g3 i ⊂
K[[x, y, z]] with respect to a given monomial order on N3 . We shall choose the graded
lexicographical order <η on N3 with x > y > z. This yields the initial monomials
in(g1 ) = z 2
in(g2 ) = yz,
in(g3 ) = y 2 .
It will turn out these do not yet generate the initial ideal in(I) of I. The missing monomial is
x4 z, which is the initial monomial of the element
g4 = x4 z − x3 yz 2 + x4 yh(z)
of I with father code
G4 = x4 z − x3 yz 2 + x4 yt.
Actually, g1 , . . . , g4 form a standard basis of I with respect to <η . This basis is obviously
not reduced.
Overview: For the convenience of the reader, let us list the various steps which will appear
in the calculations (below, “computation of ...” will always mean “computation of the code
of ...”.)
Step 1: Computation of a standard basis of I. In addition to g1 , g2 , g3 we will get a fourth
generator g4 of I, the one from above.
Step 2: Specification of all xn -regular elements of this basis and computation of the reduced
standard basis of the ideal I1 generated by them. Here, xn is z; as only g1 is z-regular,
24

I1 = hg1 i is principal and its reduced standard basis can be computed with the algorithm of
[AMR, Thm. 5.5] or, equivalently, as described in Theorem 10.1 above in the xn -regular case
for principal ideals. The reduced standard basis of I1 will again be denoted by g1 . Its tail
belongs to co(I1 ) ∼
= K[[x, y]]2 , where co(I1 ) = K[[x, y]] ⊕ K[[x, y]]z denotes the canonical
monomial direct complement of I1 in K[[x, y, z]] with respect to the chosen monomial order.
Step 3: Reduction of g2 , g3 , g4 by I1 = hg1 i. This is the division of g2 , g3 , g4 by g1 with
the algorithm of [AMR, Thm. 5.6] or, equivalently, as described in Theorem 11.1 above in
the xn -regular case for principal ideals, xn being here z. The reduced series will again be
denoted by g2 , g3 , g4 .
Step 4: Interpretation of g2 , g3 , g4 as vectors in co(I1 ) ∼
= K[[x, y]]2 and computation of the
reduced standard basis of the submodule I2 = hg2 , g3 , g4 i of K[[x, y]]2 generated by them.
By Step 1, the vectors g2 , g3 , g4 already form a standard basis of I2 , so they need not be
completed again. Step 4 consists of four substeps.
Substep 4A: Specification of all y-regular elements among g2 , g3 , g4 and computation
of the reduced standard basis of the submodule I3 of K[[x, y]]2 generated by these as
described in Theorem 10.1 for the xn -regular case (only g2 and g3 will be y-regular, so
that I3 = hg2 , g3 i.) The reduced standard basis of I3 will again be denoted by g2 , g3 . Its
tails belong to co(I3 ) ∼
= K[[x]]3 , where co(I3 ) = (K[[x]] ⊕ K[[x]]y) × K[[x]] denotes
the canonical monomial direct complement of I3 in K[[x, y]]2 with respect to the chosen
monomial order.
Substep 4B: Reduction of g4 by I3 = hg2 , g3 i. This is the division of g4 by g2 , g3 in
K[[x, y]]2 as described in Theorem 11.1 above in the xn -regular case, xn being now y.
The reduced vector will again be denoted by g4 .
Substep 4C: Interpretation of g4 as a vector in co(I3 ) ∼
= K[[x]]3 and computation of
the reduced standard basis of the submodule I4 of K[[x]]3 generated by it as described
in Theorem 10.1 in the xn -regular case, xn being here x. The situation will be so simple
that the reduced standard basis of I4 can be read off directly without using Theorem
10.1. It will again be denoted by g4 .
Substep 4D: Reduction of g2 , g3 by I4 = hg4 i. This is the division of the tails g2 , g3 of
g2 , g3 by g4 in K[[x]]3 as described in Theorem 11.1 in the xn -regular case, xn being
here x. Again, the situation will be so simple that the reduction can be read off without
using Theorem 11.1. The reduced vectors will again be denoted by g2 , g3 .
The reduced standard basis of I2 obtained in step 4 is thus g2 , g3 , g4 .
Step 5: Reduction of g1 by I2 = hg2 , g3 , g4 i. This is the division of the tail g1 of g1 by g2 ,
g3 , g4 in K[[x, y]]2 as described in Theorem 11.1 in the general case. This step consists of 2
substeps.
Substep 5A: Reduction of g1 by I3 = hg2 , g3 i. This is the division of the tail g 1 of g1 by
g2 , g3 in K[[x, y]]2 as described in Theorem 11.1 in the xn -regular case, xn being here
y. The reduced vector will again be denoted by g1 . Its tail belongs to co(I3 ) ∼
= K[[x]]3 .
Substep 5B: Reduction of g1 by I4 = hg4 i. This is the division of the tail g1 of g1 by
g4 in K[[x]]3 as described in Theorem 11.1 in the xn -regular case, xn being here x. The
reduced vector will again be denoted by g1 .
Conclusion: The vectors g1 , g2 , g3 , g4 obtained after step 5 now have to be reinterpreted
as power series in K[[x, y, z]]. By construction, they form the reduced standard basis of the
ideal I we started with.
Computations: We start now with the explicit description of the various stages of the
construction of the reduced standard basis of the ideal I.
25

Step 1: Computation of a minimal standard basis of I.
Let Ie = hH, Gk i = ht − h, gk i be the ideal of K[[x, y, z, t]] associated to I as in Lemma 8.1
(here, no eℓ ’s appear, since we work with ideals instead of modules; the index k varies between
1 and 3). We may apply Mora’s tangent cone algorithm or Lazard’s homogenization method.
Let u be a homogenizing variable, and denote by H h , Ghk the homogenized polynomials of
H and Gk in K[x, y, z, t, u].
We extend the monomial order <η on N3 first to an order <ǫ on N4 (the set of exponents of
series in K[[x, y, z, t]]) such that inε H = t and inε Gk = inη gk , and than <ε to an order <h
on N5 (the set of exponents of series in K[[x, y, z, t, u]]) such that π(lmh (H h )) = inε (H)
and π(lmh (Ghk ) = inε (Gk ), where lmh denotes the leading monomial of a polynomial with
respect to <h and π : N4 × N → N4 .
A polynomial Gröbner basis with respect to <h on N5 of the ideal J ⊂ K[x, y, z, t, u]
generated by H h , Gh1 , Gh2 and Gh3 is given by
ut − 12 uz − 21 t2 , uy 2 + zyx, uzy + zy 2 + zx2 , uz 2 + tyx,
zy 3 − z 2 yx + zyx2 , t2 y 2 + 2tzyx − z 2 yx, z 2 y 2 − ty 2 x + z 2 x2 ,
t2 zy + 2tzy 2 − ty 2 x + 2tzx2 , t2 z 2 + 2t2 yx − tzyx,
z 3 yx − tzyx2 + tyx3 ,zy 2 x2 − z 2 x3 + zx4 , ty 3 x − tzyx2 + tyx3 ,
z 3 x3 − ty 2 x3 , t2 yx3 + 2tzx4 − z 2 x4 , uzx4 − z 2 yx3 + tyx4 ,
tz 2 yx3 − 21 t2 zx4 + 2tzx5 − z 2 x5 + 21 tyx5 ,
t3 zx4 − 4t2 zx5 − 8tzyx5 + 4z 2 yx5 + 4tzx6 − z 2 x6 .
Now substitute u by 1 and t by h(z) to get a standard basis of I. It is given by g1 , g2 and g3
as above and the series g4 , with
g4 = x4 z − x3 yz 2 + x4 yh(z) =
= x4 z − x3 yz 2 + x4 y( 12 z + 18 z 2 + . . .)
and initial monomial x4 z. This series has as father code the polynomial
G4 = x4 z − x3 yz 2 + x4 yt.
The standard basis shows that the ideal I satisfies Hironaka’s box condition with respect to a
monomial order such that x < y < z. The initial ideal is generated by z 2 , yz, y 2 and x4 z.
Moreover, it can be seen that the series g1 , g2 , g3 , g4 form a Janet basis of I with scopes 3, 2,
2 and 1 respectively.
Step 2: Computation of the reduced standard basis of the ideal I1 = hg1 i.
Clearly, g1 = z 2 + xyh is the only z-regular series among g1 , . . . , g4 . We set I1 = hg1 i ⊂
K[[x, y, z]]. The monomials xyz m appearing in xyh(z) are multiples of the initial monomial
z 2 of g1 , therefore g1 is not reduced (or in Weierstrass form). Let us apply the algorithm
described in Theorem 10.1 for xn -regular series in order to find a reduced standard basis of
the ideal I1 . This algorithm coincides with the algorithm in [AMR, Thm. 5.5]. The minimal
reduced standard basis b11 , b1 of the ideal Ie1 = hH, G1 i ⊂ K[[x, y, z, t]] has the following
form (with the notation of the proof of Theorem 10.1).
b11 = t − b◦11 − u1110 (x′ ) − u1111 (x′ )z,
b1 = z 2 − b◦1 − u110 (x′ ) − u111 (x′ )z,
where b◦11 , b◦1 belong to K ⊕ Kz, the letter x′ stands for the variables (x, y), and u1110 (x′ ),
u1111 (x′ ), u110 (x′ ), u111 (x′ ) are power series vanishing at 0. To simplify let us write
26

b = t − b◦ − u0 (x′ ) − u1 (x′ )z,
c = z 2 − c◦ − w0 (x′ ) − w1 (x′ )z.

We first compute b◦ and c◦ by setting x and y equal to 0 in the ideal I˜1 . We get the ideal
hH(0, 0, z, t), G1 (0, 0, z, t)i = hH, z 2 i = ht − h, z 2 i ⊂ K[[t, z]].
From the mother code of h(z) we can compute its Taylor expansion up to any given degree.
In this case we have h = 12 z + 81 z 2 + · · ·. It follows that the (minimal) reduced standard basis
of the ideal ht − h, z 2 i is t − 12 z and z 2 . This implies that b◦ = 21 z and c◦ = 0.
Next we have to find the family code for the series u0 (x, y), u1 (x, y), w0 (x, y), w1 (x, y).
We will divide – using the polynomial division – the polynomials H and G1 by the virtual
reduced standard basis
B = t − b◦ − u0 − u1 z = t − 12 z − u0 − u1 z,
C = z 2 − c◦ − w0 − w1 z = z 2 − w0 − w1 z

of the ideal Ie1 with initial monomials t and z 2 , where u0 , u1 , w0 , w1 are now just unknowns.
The remainders R, S of these divisions are
R = (−2u1 + u0 + 2u0 u1 + 41 w1 + u1 w1 + u21 w1 )z − 2u0 + u20 + 14 w0 + u1 w0 + u21 w0 ,
S = ( 21 xy + xyu1 + w1 )z + xyu0 + w0 .
Let U1 , U2 , respectively W1 , W2 , be the coefficients of z and 1 in R and S. It is easy
to prove that they form a mother code with baby series u0 (x, y), u1 (x, y), w0 (x, y) and
w1 (x, y). In the present example the solutions vanishing at 0 of this mother code can
be described in an equivalent and more explicit way as follows. From the four equations
U1 = U2 = W1 = W2 = 0 we get
u0 (x, y) = w0 (x, y) = 0,
w1 (x, y) = − 21 xy − xyu1 (x, y),
1
u1 (x, y) = − 16
xy +

1 2 2
16 x y

−

67
3 3
1024 x y

+ O(x4 y 4 ),

where the last series is the unique solution vanishing at 0 of the equation
H2 (x, y, z, t2 ) = 8xyt32 + 12xyt22 + 16(1 + xy)t2 + xy = 0
in a new variable t2 . In this way, H2 becomes the mother code of the algebraic series u1 (x, y),
its father code being the polynomial t2 . The father code of w1 (x, y) is − 21 xy − xyt2 .
The reduced standard basis of the ideal I1 = hg1 i is given by substituting in the polynomial
C = z 2 − w0 − w1 z the variables w0 and w1 by the series w0 (x, y) = 0 and w1 (x, y) =
− 12 xy − xyu1 (x, y). We get the algebraic series z 2 + ( 21 xy + xyu1 (x, y))z with father code
C(0, − 21 xy − xyt2 , x, y, z) = z 2 + ( 12 xy + xyt2 )z. We denote this series in the sequel again
by g1 , and call its father code G1 . The corresponding baby series u1 (x, y) is denoted by
h2 (x, y) with mother code H2 (x, y, z, t2 ) from above. For later reference we collect the new
data in a table.
g1 = z 2 + ( 12 xy + xyh2 (x, y))z,
G1 = z 2 + ( 21 xy + xyt2 )z,
1
h2 (x, y) = − 16
xy +

1 2 2
16 x y

−

67
3 3
1024 x y

+ . . .,

H2 (x, y, z, t2 ) = 8xyt32 + 12xyt22 + 16(1 + xy)t2 + xy.
Note here that the original baby series h = h1 has been eliminated.
Step 3: Reduction of g2 , g3 , g4 by I1 = hg1 i.
27

We will apply the algorithm described in the proof of Theorem 11.1 for xn -regular series to
divide g2 , g3 , g4 by g1 . It will be useful to add a new variable t3 and define
H3 (x, y, z, t1 , t2 , t3 ) = t3 + 12 xy + xyt2 .
In this setting (H1 , H2 , H3 ) is the mother code of the baby series (h1, h2 , h3 ) where h1 = h(z)
and h2 = u1 (x, y) have been previously defined and where h3 equals w1 (x, y) from above. It
is clear from in(I1 ) = hz 2 i that g2 = yz + x2 z + y 2 z and g3 = y 2 + xyz are already reduced
with respect to I1 . Let us reduce g4 . We shall use polynomial division. Let Ie1 = hB, Ci be
the ideal in K[[x, y, z, t1 , t2 , t3 ]] associated to I1 as in Lemma 8.1 (it is checked that this is
exactly the ideal of the lemma), with virtual reduced standard basis
B = t1 − 12 z − t2 z,
C = z 2 − t3 z.
Dividing the father code G1 of g1 by B and C with initial monomials t1 and z 2 we get
G4 = x4 z − x3 yz 2 + t1 x4 y =
= x4 yB − x3 yC + D4 ,
where D4 = ( 21 yx4 + yx4 t2 + x4 − yx3 t3 )z. Let us replace G4 by D4 and call it again
G4 . It is the father code of a new algebraic series, denoted again by g4 , and defined by
g4 = G4 (x, y, z, h1 , h2 , h3 ). We have
g4 = ( 12 yx4 + yx4 h2 + x4 − yx3 h3 )z.
The series g2 , g3 , g4 are now reduced with respect to I1 = hg1 i. For later reference we collect
the actual data in a table.
g1 = z 2 + ( 12 xy + xyh2 (x, y))z,
G1 = z 2 + ( 21 xy + xyt2 )z,
g2 = G2 = yz + x2 z + y 2 z,
g3 = G3 = y 2 + xyz,
g4 = ( 12 yx4 + yx4 h2 + x4 − yx3 h3 )z,
G4 = ( 12 yx4 + yx4 t2 + x4 − yx3 t3 )z,
h1 = 12 z + 18 z 2 + . . .,
1
h2 = − 16
xy +

1 2 2
16 x y

−

67
3 3
1024 x y

+ . . .,

h3 = − 21 xy − xyh2 ,
H1 = 2t1 − t21 + z,
H2 = 8xyt32 + 12xyt22 + 16(1 + xy)t2 + xy,
H3 = t3 + 21 xy + xyt2 .
Step 4: Computation of the reduced standard basis of the submodule I2 = hg2 , g3 , g4 i of
co(I1 ) ∼
= K[[x, y]]2 .
The canonical direct monomial complement co(I2 ) equals K[[x, y]] ⊕ K[[x, y]]z and is
therefore isomorphic to K[[x, y]]2 as K[[x, y]]-module. The three series g2 , g3 , g4 are
mapped under this isomorphism onto the vectors
g2 = (0, y + x2 + y 2 ),
g3 = (y 2 , xy),
28

g4 = (0, x4 + 21 x4 y + x4 yh2 − x3 yh3 ).
The monomial order <η on N3 induces via the inclusion K[[x, y]] ⊕ K[[x, y]]z ⊂ K[[x, y, z]]
a monomial order, also denoted by <η , on N2 × {1, 2}. The respective initial monomial
vectors are
in(g2 ) = (0, y),
in(g3 ) = (y 2 , 0),
in(g4 ) = (0, x4 ).
We see that g2 and g3 are y-regular, whereas g3 is not. By the proof of Theorem 10.1 we first
treat the submodule generated by g2 and g3 .
Substep 4A: Computing the reduced standard basis of the submodule I3 = hg2 , g3 i of
K[[x, y]]2 .
The vectors g2 , g3 are not the reduced standard basis of I3 but form at least a minimal standard
basis. The father codes of g2 and g3 are G2 = (0, y +x2 +y 2 ) and G3 = (y 2 , xy) respectively.
They do not depend on the variables ti . From the proofs of Thms. 2 and 3 follows that we
have to consider the virtual reduced standard basis of Ie3 = I3 . Said differently, we do not
need to consider the vectors Biℓ . Thus
P
P m −1
B2 = y 2 · e1 − b◦2 − 2m=1 dj=0
u2mj y j em ,
P2
Pdm −1
B3 = y · e2 − b◦3 − m=1 j=0
u3mj y j em ,
where d1 = 2, d2 = 1 and the vectors b◦2 , b◦3 belong to (K × K) ⊕ (Ky × (0)). The vectors
b◦2 , b◦3 are obtained by specializing x to 0 in G2 and G3 . From G2 (0, y) = (y 2 , 0), G3 (0, y) =
(0, y + y 2 ) we conclude that b◦2 = b◦3 = (0, 0).

We then apply the polynomial division to reduce G2 and G3 by the virtual reduced standard
basis B2 and B3 of I3 with initial monomial vectors y 2 · e1 and y · e2 . The corresponding
remainders are
((u311 u211 + u211 u220 + u211 + u210 )y + u210 u220 + u210 + u310 u211 ,
u320 u211 +u2220 +u220 +x2 ),
((u211 x + u311 )y + u210 x + u310 , u220 x + u320 ).
Therefore, the system
u311 u211 + u211 u220 + u211 + u210 = 0,
u210 u220 + u210 + u310 u211 = 0,
u320 u211 + u2220 + u220 + x2 = 0,
u211 x + u311 = 0,
u210 x + u310 = 0,
u220 x + u320 = 0
is the mother code for the series u210 (x), u211 (x), u220 (x), u310 (x), u311 (x), u320 (x). From
this system we get
u210 (x) = u211 (x) = u310 (x) = u311 (x) = 0,
u220 (x) = h4 (x),
u320 (x) = −h4 (x)x,
where
29

h4 (x) = − 21 +

q

1
4

− x2 = −x2 − x4 − 2x6 − 5x8 + O(x10 )

is the unique solution vanishing at 0 of the equation
H4 = t24 + t4 + x2 = 0.
The reduced standard basis of the submodule I3 = hg2 , g3 i of K[[x, y]]2 is
(0, y − h4 (x)),
(y 2 , xh4 (x)).
We denote these vectors again by g2 and g3 . For later reference we collect the actual data in
a table.
g1 = z 2 + ( 12 xy + xyh2 (x, y))z,
G1 = z 2 + ( 21 xy + xyt2 )z,
g2 = G2 = yz + x2 z + y 2 z,
g3 = G3 = y 2 + xyz,
g4 = ( 12 yx4 + yx4 h2 + x4 − yx3 h3 )z,
G4 = ( 12 yx4 + yx4 t2 + x4 − yx3 t3 )z,
h1 = 12 z + 18 z 2 + . . .,
1
xy +
h2 = − 16

1 2 2
16 x y

−

67
3 3
1024 x y

+ . . .,

h3 = − 21 xy − xyh2 ,
h4 = −x2 − x4 − 2x6 − 5x8 + . . .,
H1 = 2t1 − t21 + z,
H2 = 8xyt32 + 12xyt22 + 16(1 + xy)t2 + xy,
H3 = t3 + 21 xy + xyt2 ,
H4 = t24 + t4 + x2 = 0.
Substep 4B: Reduction of g4 by the submodule I3 = hg2 , g3 i of K[[x, y]]2 .
We reduce the vector g4 = (0, 12 yx4 + yx4 h2 + x4 − yx3 h3 ) by I3 = hg2 , g3 i. We point out
that it is not enough – as the special shape of g2 = (0, y − h4 (x)) may suggest – to replace y
by h4 (x) in g4 because the power series h2 (x, y) and h3 (x, y) depend on x, y.
The virtual reduced standard basis Biℓ , B2 , B3 with i = 2, 3, 4, ℓ = 1, 2, of the submodule
Ie3 = hHi · eℓ , G2 , G3 i of K[[x, y, z, t2 , t3 , t4 ]] as in Lemma 8.1 is
Biℓ = ti · eℓ − b◦iℓ −

P2

m=1

B2 = (0, y − h4 (x)),
B3 = (y 2 , xh4 (x)),

30

Pdm −1
j=0

uiℓmj · y j · em ,

using here the computation we made in Substep 4A. To calculate the reduced standard basis
of Ie3 we use polynomial division: We divide Hiℓ , i = 2, 3, 4, ℓ = 1, 2, and G2 and G3 by

Bιλ , ι = 2, 3, 4, λ = 1, 2, and B2 , B3 with leading monomial vectors tι · eλ , y · e2 , y 2 · e1
respectively. From the remainders of these divisions we get – by a rather tedious computation
– a system defining the mother code for the series uiℓmj (x). Another, more direct computation
then shows that this system can be transformed into an equivalent system of form H5 = H6 =
0 where
H5 = 8xt4 t35 + 16xt4 t25 + (16 + 16xt4 )t5 + xt4 ,
H6 = (16 + 12t4 t5 x + 8t4 t25 x + 16xt4 +

1 3 3
32 t4 x

− 43 t24 x2 − 12 t24 t5 x2 )t6 +

+x3 t4 +

1 3 5
512 t4 x

−

3 2 4
64 t4 x ,

and where we have set t5 = u2220 , t6 = u2120 . The baby series vector of the mother code
(H5 , H6 ) will be denoted by (h5 , h6 ).
Now we can apply polynomial division to reduce G4 with respect to the virtual reduced
standard basis Biℓ , B2 , B3 of Ie3 . The division gives
P e
e2 B2 + A
e3 B3 + C4 ,
G4 =
Aiℓ Biℓ + A
C4 = (0, ((t4 + t24 )t5 + 1 + 21 t24 + 21 t4 )x4 ),

where C4 is the father code of the reduction of g4 by g2 , g3 . We denote this reduction again
by g4 . It is the vector obtained from C4 by substituting the variables t4 , t5 by the power series
h4 and h5 .
Substep 4C: Computation of the reduced standard basis of the submodule I4 = hg4 i of
co(I3 ) ∼
= K[[x]]3 .
By Substep 4B we have achieved that g4 belongs to the canonical direct monomial complement
co(I3 ) = (K[[x]] ⊕ K[[x]]y) × K[[x]]
2

of I3 in K[[x, y]] . We will identify co(I3 ) with K[[x]]3 as K[[x]]-modules. Thus
g4 = (0, 0, ((h4 + h24 )(h5 + 21 ) + 1)x4 ).
The reduced standard basis of I4 is (0, 0, x4 ) since h4 (0) = 0 implies that ((h4 + h24 )(h5 +
1
2 ) + 1) is invertible in K[[x]]. Here we could also apply the algorithm of Theorem 10.1 to
compute the reduced standard basis of I4 . In this case the computations are trivial because
the base ring is the principal ideal domain K[[x]]. We set again g4 = (0, 0, x4 ) with father
code G4 = (0, 0, x4 ).
Substep 4D: Reduction of g2 , g3 by I4 = hg4 i.
We apply the division algorithm of Theorem 11.1 in order to divide the tails g 2 and g 3 of g2
and g3 by g4 (this is sufficient since in(g2 ) and in(g3 ) do not contribute to the remainders.) As
g 2 , g 3 and g4 belong to co(I3 ) = (K[[x]] ⊕ K[[x]]y) × K[[x]] we may treat them as vectors
in K[[x]]3 . We thus have
g2 = (0, 0, h4 ),
g3 = (0, 0, −xh4 ),
g4 = (0, 0, x4 ).
Using that h4 = −x2 − x4 − 2x6 − · · · it can be seen by inspection that the remainders of
the division of g2 and g3 by g4 are (0, 0, −x2 ) and (0, 0, x3 ).
This can also be seen alternatively by applying the polynomial division. Namely, as g2 , g 3
as well as g4 belong to (0) × (0) × K[[x]] we can work with the respective last components
31

in K[[x]]. Let us consider the polynomials G2 = t4 , G3 = −xt4 and G4 = x4 as the father
codes of the last components of g 2 , g 3 and g4 respectively.
Since the only baby series appearing in g2 , g3 , g4 is h4 we have to consider the virtual reduced
standard basis B41 , B4 of the ideal Ie5 ⊂ K[[x, t4 ]] generated by H4 = t24 + t4 + x2 and
G4 = x4 . One has
B41 = t4 − u4110 − u4111 x + u4112 x2 + u4113 x3 ,
B4 = x4 − u410 − u411 x + u412 x2 + u413 x3 .
We get u410 = u411 = u412 = u413 = 0 since the initial monomial of the baby series b4 of
B4 should be x4 . On the other hand, the remainder of the polynomial division of H4 by B41
and B4 is
(u4113 + 2u4111 u4112 )x3 + (1 + u4112 + u4111 )x2 + u4111 x,
which implies u4111 = u4113 = 0 and u4112 = −1. The reduced standard basis of Ie5 is
b41 = t4 + x2 and b4 = x4 . Finally, we have to divide G2 and G3 by B41 and B4 using the
polynomial division with leading monomial vectors t4 and x4 . One has
G2 = t4 = B41 − x2 ,
G3 = −xt4 = −xB41 + x3 .
Rephrasing everything as vectors in K[[x, y]]2 , the reductions of g2 , g3 by g4 are
(0, y + x2 ),
(y 2 , −x3 ).
We set again g2 = (0, y + x2 ), g3 = (y 2 , −x3 ), rewrite g4 as g4 = (0, x4 ), together with
their father codes G2 = (0, y + x2 ), G3 = (y 2 , −x3 ) and G4 = (0, x4 ). This is the reduced
standard basis of I3 ; it coincides with what we have got at the beginning of this substep.
Conclusion of Step 4: To finish Step 4 we have to rewrite the preceding vectors as algebraic power series in x, y, z in order to obtain the reduced standard basis of the ideal
I2 = hg2 , g3 , g4 i of K[[x, y, z]]. The corresponding reduced standard basis is given by the
polynomials (we write again g1 , g2 and g3 )
g2 = yz + x2 z,
g3 = y 2 − x3 z,
g4 = x4 z.
They coincide with their father codes.
Step 5: Reduction of g1 by the submodule I2 = hg2 , g3 , g4 i of K[[x, y]]2 .
Recall that g1 = z 2 +( 21 xy +xyh2 )z. It suffices to divide the tail g 1 = −( 21 xy +xyh2 )z of g1
by I2 = hg2 , g3 , g4 i. We consider g 1 and g2 , g3 , g4 as vectors in co(I1 ) ∼
= K[[x, y]]2 . Their
father codes are G1 = (0, −xyt2 − 12 xy), G2 = (0, y + x2 ), G3 = (y 2 , −x3 ), G4 = (0, x4 )
respectively. The computation splits into two parts. Following Theorem 11.1 we will divide
first g 1 by I3 = hg2 , g3 i as vectors in K[[x, y]]2 because g2 , g3 are the y-regular power series
among g2, g3 , g4 . Afterwards, g1 will be divided by I4 = hg4 i as a vector in co(I3 ) ∼
= K[[x]]3 .
Notice here that it is necessary to work with power series vectors in the canonical direct
monomial complements co(I1 ) and co(I3 ). This is possible because, by the preceding steps,
g1 is reduced with respect to itself (hence g1 belongs to co(I1 )), g2 , g3 and g4 are reduced
with respect to g1 (hence also belong to co(I1 )), and g4 is reduced with respect to g2 and g3
(hence belongs to co(I3 ) ⊂ co(I1 )).
32

Substep 5A: Reduction of g1 by I3 = hg2 , g3 i.
We have to divide g1 by g2 and g3 as described in Theorem 11.1. We will use the polynomial
division to divide the father code G1 of g 1 by the virtual reduced standard basis B21 , B22 ,
B2 , B3 of Ie3 = hH2 · e1 , H2 · e2 , G2 , G3 i in K[[x, y, t2 ]]2 . Notice that the only baby series
appearing in g1 , g2 , g3 is h2 . Therefore, the only mother code appearing in Ie1 is H2 . We have
B21 = (t2 − u2110 − u2111 y, −u2120 ),
B22 = (−u2210 − u2211 y, t2 − u2220 ),
B2 = (0, y − u220 ),
B3 = (y 2 , −u320 ),
where the form of B2 and B3 follows from the computation made in Substep 4D. The
remainder of this polynomial division is R = (0, x3 (u2220 + 12 )). The algebraic series
u2220 (x) is defined by the mother code
H7 = 8x3 t37 + 12x3 t27 − (16 − 16x3 )t7 + x3 ,
where we have set t7 = u2220 . This mother code H7 results from the division of H2 · eℓ and
G2 , G3 by Biλ , B2 , B3 and an appropriate simplification. Let us write h7 for the baby series
u2220 (x) with mother code H7 . It then follows that the reduction of g 1 = (0, − 21 xy − xyt2 )
with respect to I3 is (0, x3 (h7 + 21 )). We write this reduction again as g1 = (0, x3 (h7 + 12 )).
Note that it belongs to co(I3 ).
Substep 5B: Reduction of g1 by I4 = hg4 i.
We have to divide the tail g1 of g1 by g4 as described in Theorem 11.1. For this we will
consider g 1 and g4 as vectors in co(I3 ) ∼
= K[[x]]3 . We have g 1 = (0, 0, x3 (h7 + 21 )) and
4
g4 = (0, 0, x ). Since h7 (0) = 0 the reduction of g 1 with respect to g4 is (0, 0, 21 x3 ). As in
Substep 4D this reduction can be also computed by using the polynomial division. We omit
the details.
Conclusion of example: Starting with the family code H1 = t21 − 2t1 + z, G1 = z 2 + xyt1 ,
G2 = yz + x2 z + y 2 z, G3 = y 2 + xyz of the generators g1 , g2 and g3 of the ideal
√
I ⊂ K[[x, y, z]] with baby series h = 1 − 1 − z = 12 z + 18 z 2 + . . . we have found the
reduced standard basis of I with respect to <η as the polynomials (denoted again by g1 , g2 ,
g3 and g4 )
g1 = z 2 − 21 x3 z,
g2 = yz + x2 z,
g3 = y 2 − x3 z,
g4 = x4 z.
They coincide with their father codes, and all baby series and mother codes have disappeared.
We leave it as a challenge to the interested reader to find this basis of I directly without using
the algorithms of the paper.

33

References
[AHV] Aroca, J.-M., Hironaka, H., Vicente, J.-L.: The theory of the maximal contact. Memorias Mat. Inst. Jorge Juan Madrid 29 (1975).
[Am] Amasaki, M.: Applications of the generalized Weierstrass preparation theorem to the
study of homogeneous ideals. Trans. Amer. Math. Soc. 317 (1990), 1-43.
[AMR] Alonso, M.E., Mora, T., Raimondo, M.: A computational model for algebraic power
series. J. Pure Appl. Alg. 77 (1992), 1-38.
[Ar1] Artin, M.: Grothendieck topologies. Mimeographed notes, Harvard University 1962.
[Ar2] Artin, M.: Algebraic approximations of structures over complete local rings. Publ.
Math. I.H.E.S. 36 (1969), 23-58.
[AM] Artin, M., Mazur, B.: On periodic points. Ann. Math. 81 (1965), 82-99.
[BCR] Bochnak, J., Coste, M., Roy, M.-F.: Géométrie Algébrique Réelle. Springer 1987.
[BG] Baclawski, K., Garsia, A.: Combinatorial decomposition of a class of rings. Adv.
Math. 39 (1981), 155-184.
[BK] Bostan, A., Kauers, M.: The complete generating function for Gessel walks is algebraic. With an appendix by Mark van Hoeij. Proc. Amer. Math. Soc. 138 (2010), no.
9, 3063-3078.
[BM] Bousquet-Mélou, M., Mishna, M.: Walks with small steps in the quarter plane.
Contemp. Math. 520 (2010), 1-39.
[BP1] Bousquet-Mélou, M., Petkovšek, M.: Linear recurrences with constant coefficients.
Discrete Math. 225 (2000), 51-75.
[BP2] Bousquet-Mélou, M., Petkovšek, M.: Walks confined in a quadrant are not always
D-finite. Theor. Comp. Sci. 307 (2003), 257-276.
[BrK] Brieskorn, E., Knörrer, H.: Plane Algebriac Curves. Birkhäuser 1986.
[CLO] Cox, D., Little, J., O’Shea, D.: Using Algebraic Geometry. Springer 1998.
[dJP] De Jong, T., Pfister, G.: Local Analytic Geometry. Springer 2000.
[Ga] Galligo, A.: A propos du Théorème de Préparation de Weierstrass. Lecture Notes in
Math. 409, 543-579. Springer 1973.
[GB] Gerdt, V., Blinkov, Y.: Involutive bases of polynomial ideals. Simplification of
systems of algebraic and differential equations with applications. Math. Comput.
Simulation 45 no. 5-6 (1998), 519-541.
[Gr1] Gräbe, H.-G.: The tangent cone algorithm and homogenization. J. Pure Appl. Algebra
97 (1994), 303-312.
[Gr2] Gräbe, H.-G.: Algorithms in local algebra. J. Symb. Comp. 19 (1995), 545-557.
[Gra] Grauert, H.: Über die Deformation isolierter Singularitäten analytischer Mengen.
Invent. Math. 15 (1972), 171-198.
[GP] Greuel, G.M., Pfister, G.: A Singular Introduction to Commutative Algebra. Springer,
2nd edition 2007.
[GPS] Greuel, G.M., Pfister, G., Schönemann, H.: Singular. A Computer Algebra System
for Polynomial Computations. Universität Kaiserslautern, www.singular.uni-kl.de.
[Hi1] Hironaka, H.: Idealistic exponents of singularity. In: Algebraic Geometry, The Johns
Hopkins Centennial Lectures. Johns Hopkins University Press 1977.
[Hi2] Hironaka, H.: Resolution of singularities of an algebraic variety over a field of
characteristic zero. Ann. Math. 79 (1964), 109-326.
[HM] Hauser, H., Müller, G.: A rank theorem for analytic maps between power series
spaces. Publ. Math. I.H.E.S. 80 (1995), 95-115.
[Ja1] Janet, M.: Sur les systèmes d’équations aux dérivées partielles. J. Math. 8e sér., III
(1920), 65-151.
[Ja2] Janet, M.: Leçons sur les systèmes d’équations aux dérivées partielles. GauthiersVillars 1929.
34

[KPR] Kurke, H., Pfister, G., Rozcen, M.: Henselsche Ringe und algebraische Geometrie.
Dt. Verlag der Wissenschaften, Berlin 1975.
[Lf]
Lafon, J.-P.: Séries formelles algébriques. C. R. Acad. Sci. Paris 260 (1965), 32383241.
[Lz] Lazard, D.: Gröbner bases, Gaussian elimination and resolutions of systems of algebraic equations. Computer algebra (London 1983). Lecture Notes Comp. Sci. 162,
146-156. Springer 1983.
[Mi] Mishna, M.: Classifying lattice walks restricted to the quarter plane. J. Combin.
Theory Ser. A 116 (2009), no. 2, 460-477.
[Mu] Mumford, D.: The Red Book of Varietes and Schemes. Springer, 2nd edition 1999.
[Mo] Mora, T.: An algorithm to compute the equations of tangent cones. Proceedings
Eurocam 82. Lecture Notes Comp. Sci. 144, 158-165. Springer 1982.
[Na1] Nagata, M.: On the theory of henselian rings. Nagoya Math. Journ. 5 (1953), 5-57,
and 7 (1954), 1-19.
[Na2] Nagata, M.: Local rings. Interscience 1962.
[Ra] Raynaud, M.: Anneaux locaux henséliens. Lecture Notes Math. 169. Springer 1970.
[Re] Rees, D.: A basis theorem for polynomial modules. Proc. Cambridge Phil. Soc. 52
(1956), 12-16.
[Ri]
Riquier, C.: Les Syst`èmes d’Équations aux Dériv´ées Partielles. Gauthier-Villars
1910.
[Ru] Ruiz, J.: The basic theory of power series. Vieweg 1993.
[Se1] Seiler, W.: A combinatorial approach to involution and δ-regularity I: Involutive bases
in polynomial algebras of solvable type. Appl. Algebra Engrg. Comm. Comput. 20,
no. 3-4 (2009), 207-259.
[Se2] Seiler, W.: A combinatorial approach to involution and δ-regularity II: Structure
analysis of polynomial modules with Pommaret bases. Appl. Algebra Engrg. Comm.
Comput. 20, no. 3-4 (2009), 261-338.
[Se3] Seiler, W.: Spencer cohomology, differential equations, and Pommaret bases. In:
Gröbner Bases in Symbolic Analysis, 169-216. Radon Ser. Comput. Appl. Math. 2.
De Gruyter 2007.
[SW] Sturmfels, B., White, N.: Computing combinatorial decompositions of rings. Combinatorica 11 (1991), 275-293.
[Wa] Wagner, D.: Algebraische Potenzreihen. Diploma Thesis, Univ. Innsbruck 2005.
[Wi] Wilczynski, E.J.: On the form of the power series for an algebraic function. Amer.
Math. Monthly 26 (1919), 9-12.
[Za] Zariski, O.: Analytical irreducibility of normal varieties. Ann. Math. 49 (1948),
352-361.

M.E.A.: Departamento de Álgebra,
Universidad Complutense de Madrid,
mariemi@mat.ucm.es
F.J.C.J.: Departamento de Álgebra,
Universidad de Sevilla,
castro@us.es
H.H.: Fakultät für Mathematik, Universität Wien,
Institut für Mathematik, Universität Innsbruck,
herwig.hauser@univie.ac.at

35

