Edward Bierstone
email: bierston@fields.utoronto.ca

Dima Grigoriev
email: dmitry.grigoryev@math.univ-lille1.fr

Pierre D Milman
email: milman@math.toronto.edu

Jaros Law

W Lodarczyk

J Wlodarczyk

EFFECTIVE HIRONAKA RESOLUTION AND ITS COMPLEXITY (WITH APPENDIX ON APPLICATIONS IN POSITIVE CHARACTERISTIC)

Building upon works of Hironaka, Bierstone-Milman, Villamayor and W lodarczyk we give an a priori estimate for the complexity of the simplified Hironaka algorithm. As a consequence of this result we show that there exists a canonical Hironaka embedded desingularization and principalization over the fields of large characteristic (relatively to degree of generating polynomials).

Introduction

In this paper we discuss the complexity of the Hironaka theorem on resolution of singularities of a marked ideal. Recall that approach to the problem of embedded resolution was originated by Hironaka (see [START_REF] Hironaka | Resolution of singularities of an algebraic variety over a field of characteristic zero[END_REF]) and later developed and simplified by Bierstone-Milman (see [START_REF] Bierstone | Semianalytic and subanalytic sets[END_REF], [START_REF] Bierstone | Uniformization of analytic spaces[END_REF], [START_REF] Bierstone | A simple constructive proof of canonical resolution of singularities[END_REF]), Villamayor (see [START_REF] Villamayor | Constructiveness of Hironaka's resolution[END_REF], [START_REF] Villamayor | Patching local uniformizations[END_REF]), and W lodarczyk ( [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF]) and others. In particular, we also use some elements from the recent development by Kollár ([38]).

It seems easier to estimate the complexity of the resolution algorithm from the recursive descriptions in W lodarczyk [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF] or Bierstone-Milman [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] than from the earlier iterative versions. The algorithms in [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF] and [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] (or [START_REF] Bierstone | Canonical desingularization in characteristic zero by blowing up the maximum strata of a local invariant[END_REF]) lead to identical blowing-up sequences; whether one proof is preferable to the other is partly a matter of taste. In this article, we estimate the complexity of the "weak-strong desingularization" algorithm (see Section 1) using the construction of [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF], though [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] could also be used (see Remark in this section below). In a subsequent paper, we plan to use [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] to give a comparable complexity estimate for the algorithm of "strong desingularization" (where the centres of blowing up are smooth subvarieties of the successive strict transforms).

The basic question which arises is in what terms to estimate the complexity a priori ? We recall (see, e. g., [START_REF] Wagner | Computational Complexity[END_REF], [START_REF] Grigoriev | Computational complexity in polynomial algebra[END_REF]) that the complexity is usually measured as a function of the bit-size of the input. In particular, in this paper we study varieties and ideals which are represented by families of polynomials with integer coefficients, and the vector of all these coefficients (for an initial variety and an ideal) is treated as an input. Hironaka's algorithm consists of many steps of elementary calculations, but they are organized in several (nested) recursions where the resolution of an object (a variety or a marked ideal, see below) is reduced to resolutions of suitable objects with smaller values of appropriate parameters (like dimension or multiplicity). It is instructive to represent the Hironaka algorithm as a tree, to each node a of which corresponds a marked ideal. The marked ideals which correspond to child nodes of a have either smaller multiplicity of an ideal or smaller dimension of a variety. An initial marked ideal corresponds to the root of the tree. The depth of the tree is bounded by 2 • m where m denotes the dimension of the initial variety, while the number of the nested recursions does not exceed m + 3. It appears that just the number of nested recursions is the overwhelming contribution to the complexity of the Hironaka's algorithm.

That is why as a relevant language for expressing a complexity bound we have chosen the Grzegorczyk class E l , l ≥ 0 [START_REF] Grzegorczyk | Some classes of recursive functions[END_REF], [START_REF] Wagner | Computational Complexity[END_REF] which consists of (integer) functions whose construction requires l nested primitive recursions. The classes E l , l ≥ 0 provide a hierarchy of the set of all primitive-recursive functions ∪ l<∞ E l . In particular, E 2 contains all (integer) polynomials and E 3 contains all finite compositions of the exponential function.

As an illustration of complexity bounds from small Grzegorczyk classes, we give examples of a few algebraic-geometrical computational problems: Polynomial factoring [START_REF] Grigoriev | Computational complexity in polynomial algebra[END_REF], with polynomial complexity (so in E 2 ); finding irreducible components of a variety, with the exponential complexity (so in E 3 ) [START_REF] Grigoriev | Computational complexity in polynomial algebra[END_REF]; and constructing a Groebner basis of an ideal, with double-exponential complexity (so also in E 3 ) [START_REF] Giusti | Some effectivity problems in polynomial ideal theory[END_REF][START_REF] Möller | Upper and lower bounds for the degree of Groebner bases[END_REF].

The principal complexity result of this paper (Theorem 6.4.2) states that the complexity of resolution of an ideal on an m-dimensional variety is bounded by a function from class E m+3 . We mention also that the complexity of Hilbert's Idealbasissatz for polynomial ideals in n variables (much simpler from a purely mathematical point of view) belongs to class E n+1 (cf. [START_REF] Seidenberg | On the length of a Hilbert ascending chain[END_REF], [START_REF] Simpson | Ordinal numbers and the Hilbert Basis Theorem[END_REF], where the latter was formulated in different languages), and, moreover, the number n + 1 is sharp. This shows that these two quite different algorithmic problems have a common feature in recursion on the dimension which mainly determines their complexities.

Remark. The main differences between the proofs in [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] and [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF] come from the notions of derivative ideal that are used ( [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] uses only derivatives that preserve the ideal of the exceptional divisor) and from passage to a "homogenized ideal" in [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF] (see §2.8). The latter has the advantage that any two maximal contact hypersurfaces for the homogenized ideal are related by an automorphism, while [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] provides a stronger version of functoriality that is needed for strong desingularization. Since [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] does not involve homogenization, certain complexity estimates can be improved (see Remark after Corollary 5.0.10), although the overall Grzegorczyk complexity class E m+3 is unchanged.

We mention that in [START_REF] Tsfasman | Algebraic-geometric codes[END_REF][START_REF] Teitelbaum | On the computational complexity of the resolution of plane curve singularities[END_REF][START_REF] Kozen | Efficient resolution of singularities of plane curves[END_REF] polynomial complexity algorithms for resolution of a curve are presented. Also in [START_REF] Blanco | Complexity of Villamayor's algorithm in the non-exceptional monomial case[END_REF], a complexity estimated in E 3 for an algorithm for resolution of singularities in the non-exceptional monomial case is presented.

In Section 1 below, we formulate the results on canonical principalization of a sheaf of ideals and on embedded desingularization. In Section 2 we give definitions of basic notions like marked ideals, hypersurfaces of maximal contact and coefficient ideals, and we formulate their properties (one can find proofs in [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF]). In Section 3 we describe the resolution algorithm. In Section 4, we provide bounds on the degrees and on the number of polynomials which describe a single blow-up. In Section 5 we give some auxiliary bounds -on the multiplicity of an ideal in terms of degrees of describing polynomials, on the degree of a hypersurface of maximal contact, and on the number of generators of the coefficient ideal and their degrees. Finally in Section 6 we estimate the complexity of the resolution algorithm in terms of Grzegorczyk's classes (their definition is also provided in Section 6).

In the appendix we give some applications of the obtained estimates. We show that resolution of singularities exists in positive characteristic, provided that the characteristic is very large relatively to degree of polynomials describing singularities and their number. 0.1. Acknowledgements. We heartily thank the Max Planck Institut fuer Mathematik, Bonn for its warm hospitality.

Formulation of the Hironaka resolution theorems

All algebraic varieties in this paper are defined over a ground field of characteristic zero. The assumption of characteristic zero is only needed for the local existence of a hypersurface of maximal contact (Lemma 2.6.4).

We give proofs of the following Hironaka Theorems (see [START_REF] Hironaka | Resolution of singularities of an algebraic variety over a field of characteristic zero[END_REF]):

(1) Canonical Principalization.

Theorem 1.0.1. Let I be a sheaf of ideals on a smooth algebraic variety X. There exists a principalization of I; that is, a sequence

X = X 0 σ1 ←-X 1 σ2
←-X 2 ←-. . . ←-X i ←-. . . ←-X r = X of blow-ups σ i : X i-1 ← X i of smooth centers C i-1 ⊂ X i-1 , such that: (a) The exceptional divisor E i of the induced morphism σ i = σ 1 • . . . • σ i : X i → X has only simple normal crossings and C i has simple normal crossings with E i . (b) The total transform σ r * (I) is the ideal of a simple normal crossing divisor E which is a natural combination of the irreducible components of the divisor E r . Moreover, the morphism ( X, I) → (X, I) defined by the above principalization commutes with smooth morphisms and embeddings of ambient varieties. It is equivariant with respect to any group action, not necessarily preserving the ground field K.

(2) Weak-Strong Hironaka Embedded Desingularization. Theorem 1.0.2. Let Y be a subvariety of a smooth variety X over a field of characteristic zero. There exists a sequence Remark. Note that a blow-up of codimension one components is an isomorphism. However it defines a nontrivial transformation of marked ideals. In the actual desingularization process, blow-ups of this kind may occur for some marked ideals induced on subvarieties of ambient varieties. Though they define isomorphisms of those subvarieties they determine blow-ups of ambient varieties which are not isomorphisms.

X 0 = X σ1 ←-X 1 σ2 ←-X 2 ←-. . . ←-X i ←-. . . ←-X r = X of blow-ups σ i : X i-1 ←-X i of smooth centers C i-1 ⊂ X i-1 , such that: (a) The exceptional divisor E i of the induced morphism σ i = σ 1 • . . . • σ i : X i → X

Remarks.

(1) By the exceptional divisor of a blow-up σ : X ′ → X with smooth center C we mean the inverse image E := σ -1 (C) of the center C. By the exceptional divisor of a composite of blow-ups σ i with smooth centers C i-1 we mean the union of the strict transforms of the exceptional divisors of σ i . This definition coincides with the standard definition of the exceptional set of points of the birational morphism in the case when codim(C i ) ≥ 2 (as in Theorem 1.0.2). If codim(C i-1 ) = 1 the blow-up of C i-1 is an identical isomorphism and defines a formal operation of converting a subvariety C i-1 ⊂ X i-1 into a component of the exceptional divisor E i on X i . This formalism is convenient for the proofs. In particular it indicates that C i-1 identified via σ i with a component of E i has simple normal crossings with other components of E i .

(2) In Theorem 1.0.2, we blow up centers of codimension ≥ 2 and both definitions coincide.

Marked ideals, coefficient ideals and hypersurfaces of maximal contact

We shall assume that the ground field is algebraically closed.

2.1. Resolution of marked ideals. For any sheaf of ideals I on a smooth variety X and any point x ∈ X we denote by ord x (I) := max{i | I ⊂ m i x } the order of I at x. (Here m x denotes the maximal ideal of x.) Definition 2.1.1. (Hironaka (see [START_REF] Hironaka | Resolution of singularities of an algebraic variety over a field of characteristic zero[END_REF], [START_REF] Hironaka | Idealistic exponents of singularity[END_REF]), Bierstone-Milman (see [START_REF] Bierstone | Uniformization of analytic spaces[END_REF]),Villamayor (see [START_REF] Villamayor | Constructiveness of Hironaka's resolution[END_REF])) A marked ideal (originally a basic object in Villamayor) is a collection (X, I, E, µ), where X is a smooth variety, I is a sheaf of ideals on X, µ is a nonnegative integer and E is a totally ordered collection of divisors whose irreducible components are pairwise disjoint and all have multiplicity one. Moreover the irreducible components of divisors in E have simultaneously simple normal crossings. Definition 2.1.2. (Hironaka ([32], [START_REF] Hironaka | Idealistic exponents of singularity[END_REF]), Bierstone-Milman (see [START_REF] Bierstone | Uniformization of analytic spaces[END_REF]),Villamayor (see [START_REF] Villamayor | Constructiveness of Hironaka's resolution[END_REF])) By the support (originally singular locus) of (X, I, E, µ) we mean supp(X, I, E, µ) := {x ∈ X | ord x (I) ≥ µ}.

Remarks. (1) Sometimes for simplicity we will represent marked ideals (X, I, E, µ) as couples (I, µ) or even ideals I.

(2) For any sheaf of ideals I on X, we have supp(I, 1) = supp(O X /I).

(3) For any marked ideal (I, µ) on X, supp(I, µ) is a closed subset of X (Lemma 2.5.2).

Definition 2.1.3. (Hironaka (see [START_REF] Hironaka | Resolution of singularities of an algebraic variety over a field of characteristic zero[END_REF], [START_REF] Hironaka | Idealistic exponents of singularity[END_REF]), Bierstone-Milman (see [START_REF] Bierstone | Uniformization of analytic spaces[END_REF]),Villamayor (see [START_REF] Villamayor | Constructiveness of Hironaka's resolution[END_REF])) By a resolution of (X, I, E, µ) we mean a sequence of blow-ups σ i :

X i → X i-1 of smooth centers C i-1 ⊂ X i-1 , X 0 = X σ1 ←-X 1 σ2 ←-X 2 σ3 ←-. . . X i ←-. . . σr ←-X r ,
which defines a sequence of marked ideals (X i , I i , E i , µ) where

(1) C i ⊂ supp(X i , I i , E i , µ). ( 2
) C i has simple normal crossings with E i . ( 3
) I i = I(D i ) -µ σ * i (I i-1 ), where I(D i ) is the ideal of the exceptional divisor D i of σ i . (4) E i = σ c i (E i-1 ) ∪ {D i }, where σ c i (E i-1 ) is the set of strict transforms of divisors in E i-1 . (5) The order on σ c i (E i-1
) is defined by the order on E i-1 , while D i is the maximal element of E i . ( 6) supp(X r , I r , E r , µ) = ∅. Definition 2.1.4. A sequence of morphisms which are either isomorphisms or blow-ups satisfying conditions (1)-( 5) is called a multiple blow-up. The number of morphisms in a multiple blow-up will be called its length. Definition 2.1.5. An extension of a multiple blow-up (or a resolution) (X i ) 0≤i≤m is a sequence (X ′ j ) 0≤j≤m ′ of blow-ups and isomorphisms

X ′ 0 = X ′ j0 = . . . = X ′ j1-1 ← X ′ j1 = . . . = X ′ j2-1 ← . . . X ′ jm = . . . = X ′ m ′ , where X ′ ji = X i . Remarks. (1)
The definition of extension arises naturally when we pass to open subsets of the ambient variety X.

(2) The notion of a multiple blow-up is analogous to the notion of a sequence of admissible blow-ups considered by Hironaka, Bierstone-Milman and Villamayor.

2.2.

Transforms of marked ideal and controlled transforms of functions. In the setting of the above definition we will call

(I i , µ) := σ c i (I i-1 , µ)
the transform of the marked ideal or controlled transform of (I, µ). It makes sense for a single blow-up in a multiple blow-up as well as for a multiple blow-up. Let σ i := σ 1 • . . . • σ i : X i → X be a composition of consecutive morphisms of a multiple blow-up. Then in the above setting

(I i , µ) = σ ic (I, µ).
We will also denote the controlled transform σ ic (I, µ) by (I, µ) i or [I, µ] i .

The controlled transform can also be defined for local sections f ∈ I(U ). Let σ : X ← X ′ be a blow-up of a smooth center C ⊂ supp(I, µ) defining transformation of marked ideals σ c (I, µ) = (I ′ , µ). Let f ∈ I(U ) be a section of I. Let U ′ ⊆ σ -1 (U ) be an open subset for which the sheaf of ideals of the exceptional divisor is generated by a function y. The function

g = y -µ (f • σ) ∈ I(U ′ )
is the controlled transform of f on U ′ (defined up to an invertible function). As before we extend it to any multiple blow-up.

The following lemma shows that the notion of controlled transform is well defined.

Lemma 2.2.1. Let C ⊂ supp(I, µ) be a smooth center of a blow-up σ : X ← X ′ and let D denote the exceptional divisor. Let I C denote the sheaf of ideals defined by C. Then

(1)

I ⊂ I µ C . (2) σ * (I) ⊂ (I D ) µ .
Proof. [START_REF] Abhyankar | Desingularization of plane curves[END_REF] We can assume that the ambient variety X is affine. Let u 1 , . . . , u k be parameters generating I C Suppose f ∈ I \ I µ C . Then we can write f = α c α u α , where either |α| ≥ µ or |α| < µ and c α ∈ I C . By the assumption there is α with |α| < µ such that c α ∈ I C . Take α with the smallest |α|. There is a point x ∈ C for which c α (x) = 0 and in the Taylor expansion of f at x there is a term c α (x)u α . Thus ord x (I) < µ. This contradicts to the assumption C ⊂ supp(I, µ).

(

) σ * (I) ⊂ σ * (I C ) µ = (I D ) µ . 2
2.3. Hironaka resolution principle. Our proof is based on the following principle which can be traced back to Hironaka and was used by Villamayor in his simplification of Hironaka's algorithm:

(Canonical) Resolution of marked ideals (X, I, E, µ) (1) ⇓ (Canonical) Principalization of the sheaves I on X (2) ⇓ (Canonical) Weak Embedded Desingularization of subvarieties Y ⊂ X (3) ⇓ (Canonical) Desingularization (4)
(1)⇒(2). It follows immediately from the definition that a resolution of (X, I, ∅, 1) determines a principalization of I. Denote by σ : X ← X the morphism defined by a resolution of (X, I, ∅, 1). The controlled transform ( I, 1) := σ c (I, 1) has the empty support. Consequently, V ( I) = ∅, and thus I is equal to the structural sheaf O X . This implies that the full transform σ * (I) is principal and generated by the sheaf of ideal of a divisor whose components are the exceptional divisors. The actual process of desingularization is often achieved before (X, I, E, 1) has been resolved (see [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF]).

(2)⇒(3). Let Y ⊂ X be an irreducible subvariety. Assume there is a principalization of sheaves of ideals I Y subject to conditions (a) and (b) of Theorem 1.0.1. Then, in the course of the principalization of I Y , the strict transform Y i of Y in some X i is the center of a blow-up. At this stage Y i is nonsingular and has simple normal crossings with the exceptional divisors.

(3)⇒(4). Every algebraic variety locally admits an embedding into an affine space. Then we can show that the existence of canonical embedded desingularization independent of the embedding defines a canonical desingularization.

For more details, see [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF].

Remark. Resolution scheme and marked ideals. Marked ideals will be understood as objects which carry vital information in the resolution scheme. There are four different types of information that can be associated with marked ideals:

(1) The support supp(I, µ) is the "bad locus" which shall be eliminated. The blow-ups performed should have centers inside of supp(I, µ). (2) The controlled transform σ c (I, µ) = I -µ D σ * (I, µ) is the transform of the marked ideal associated with blow-ups with centers inside supp(I, µ).

(3) The resolution of supp(I, µ) is the sequence of blow-ups and the induced transformations of marked ideals eliminating the support of the resulting marked ideal (I, µ). (4) Canonical resolution is a unique resolution which will be assigned to a marked ideal. Once we assign to a certain class of marked ideals their canonical resolutions they become useful operations to resolve some larger class of marked ideals. In other words, the resolution of a certain marked ideal is always reduced to resolution of some "simpler" marked ideals. The notion of simplicity refers essentially to two very rough invariants : the dimension of the ambient variety, and the order of nonmonomial part.

The algorithm builds upon two different canonical reductions:

• reduction of order by resolving a so called "companion ideal" (see Step 2 in Section 3).

• reduction of dimension of the ambient variety which relies on the two fundamental concepts of hypersurface of maximal contact, and coefficient ideal (see Sections 2.6, 2.9).

2.4.

Equivalence relation for marked ideals. Let us introduce the following equivalence relation for marked ideals:

Definition 2.4.1. Let (X, I, E I , µ I ) and (X, J , E J , µ J ) be two marked ideals on a smooth variety X. Then (X, I, E I , µ I ) ≃ (X, J , E J , µ J ) if:

(1) E I = E J and the orders on E I and on E J coincide.

(2) supp(I, µ I ) = supp(J , µ J ).

(3) The multiple blow-ups (X i ) i=0,...,k are the same for both marked ideals, and supp(I i , µ I ) = supp(J i , µ J ).

Example 2.4.2. For any k ∈ N, (I, µ) ≃ (I k , kµ).

Remark. The marked ideals considered in this paper satisfy a stronger equivalence condition: For any smooth morphism φ : X ′ → X, φ * (I, µ) ≃ φ * (J , µ). This condition will follow and is not added in the definition.

2.5. Ideals of derivatives . Ideals of derivatives were first introduced and studied in the resolution context by Giraud. Villamayor developed and applied this language to his basic objects.

Definition 2.5.1. (Giraud, Villamayor) Let I be a coherent sheaf of ideals on a smooth variety X. By the first derivative (originally extension) D(I) of I we mean the coherent sheaf of ideals generated by all functions f ∈ I together with their first derivatives. Then the i-th derivative D i (I) is defined to be D(D i-1 (I)). If (I, µ) is a marked ideal and i ≤ µ then we define

D i (I, µ) := (D i (I), µ -i).
Recall that on a smooth variety X there is a locally free sheaf of differentials Ω X/K over K generated locally by du 1 , . . . , du n for a set of local parameters u 1 , . . . , u n . The dual sheaf of derivations Der K (O X ) is locally generated by the derivations ∂ ∂ui . Immediately from the definition we observe that D(I) is a coherent sheaf defined locally by generators f j of I and all their partial derivatives ∂fj ∂ui . We see by induction that D i (I) is a coherent sheaf defined locally by the generators f j of I and their derivatives In particular, supp(I, µ) = supp(D µ-1 (I), 1) = V (D µ-1 (I)) is a closed set.

We write (I, µ) ⊂ (J , µ) if I ⊂ J . Lemma 2.5.3. (Giraud,Villamayor) Let (I, µ) be a marked ideal, C ⊂ supp(I, µ) a smooth center, and r ≤ µ. Let σ : X ← X ′ be a blow-up at C. Then

σ c (D r (I, µ)) ⊆ D r (σ c (I, µ)).
Proof. See the simple computations in [START_REF] Villamayor | Introduction to the algorithm of resolution[END_REF], [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF].

2.6. Hypersurfaces of maximal contact. The concept of the hypersurfaces of maximal contact is one of the key points of this proof. It was originated by Hironaka, Abhyankhar and Giraud and developed in the papers of Bierstone-Milman and Villamayor. In our terminology, we are looking for a smooth hypersurface containing the support of a marked ideal and whose strict transforms under multiple blow-ups contain the supports of the induced marked ideals. Existence of such hypersurfaces allows a reduction of the resolution problem to codimension 1.

First we introduce marked ideals which locally admit hypersurfaces of maximal contact.

Definition 2.6.1. (Villamayor (see [START_REF] Villamayor | Constructiveness of Hironaka's resolution[END_REF]) ) We say that a marked ideal (I, µ) is of maximal order (originally

simple basic object) if max{ord x (I) | x ∈ X} ≤ µ or equivalently D µ (I) = O X .
Lemma 2.6.2. (Villamayor (see [START_REF] Villamayor | Constructiveness of Hironaka's resolution[END_REF]) ) Let (I, µ) be a marked ideal of maximal order and let C ⊂ supp(I, µ) be a smooth center. Let σ : X ← X ′ be a blow-up at C. Then σ c (I, µ) is of maximal order.

Proof.

If (I, µ) is a marked ideal of maximal order then D µ (I) = O X . Then, by Lemma 2.5.3, D µ (σ c (I, µ)) ⊃ σ c (D µ (I), 0) = O X .
Lemma 2.6.3. (Villamayor (see [START_REF] Villamayor | Constructiveness of Hironaka's resolution[END_REF]), ) If (I, µ) is a marked ideal of maximal order and 0 ≤ i ≤ µ, then

D i (I, µ) is of maximal order. Proof. D µ-i (D i (I, µ)) = D µ (I, µ) = O X .
Lemma 2.6.4. (Giraud (see [START_REF] Giraud | Sur la theorie du contact maximal[END_REF])) Let (I, µ) be a marked ideal of maximal order. Let σ : X ← X ′ be a blow-up at a smooth center C ⊂ supp(I, µ). Let u ∈ D µ-1 (I, µ)(U ) be a function such that, for any

x ∈ V (u), ord x (u) = 1. Then (1) V (u) is smooth; (2) supp(I, µ) ∩ U ⊂ V (u). Let U ′ ⊂ σ -1 (U ) ⊂ X ′
be an open set where the exceptional divisor is described by y.

Let u ′ := σ c (u) = y -1 σ * (u) be the controlled transform of u. Then (1) u ′ ∈ D µ-1 (σ c (I |U ′ , µ)); (2) V (u ′ ) is smooth; (3) supp(I ′ , µ) ∩ U ′ ⊂ V (u ′ ) (4) V (u ′ ) is the restriction of the strict transform of V (u) to U ′ . Proof. (1) u ′ = σ c (u) = u/y ∈ σ c (D µ-1 (I)) ⊂ D µ-1 (σ c (I)).
(2) Since u is one of the local parameters describing the center of the blow-up, u ′ = u/y is a parameter; that is, a function of order one.

(3) follows from (2).

Definition 2.6.5. We will call a function

u ∈ T (I)(U ) := D µ-1 (I(U ))
of multiplicity one a tangent direction of (I, µ) on U .

As a corollary from the above we obtain the following lemma.

Lemma 2.6.6. (Giraud) Let u ∈ T (I)(U ) be a tangent direction of (I, µ) on U . Then for any multiple blow-up (U i ) of (I |U , µ), all the supports of the induced marked ideals supp(I i , µ) are contained in the strict transforms V (u) i of V (u).

Remarks. (1) Tangent directions are functions locally defining hypersurfaces of maximal contact.

(2) The main problem leading to complexity of the proofs is that of noncanonical choice of the tangent directions. We overcome this difficulty by introducing homogenized ideals.

Arithmetical operations on marked ideals.

In this sections all marked ideals are defined for the smooth variety X and the same set of exceptional divisors E. Define the following operations of addition and multiplication of marked ideals:

(1) (I, µ I ) + (J , µ J ) := (I µI + J µI , µ I µ J ), or, more generally,

(I 1 , µ 1 ) + . . . + (I m , µ m ) := (I µ2•...•µm 1 + I µ1µ3•...•µm 2 + . . . + I µ1...µ k-1 m , µ 1 µ 2 . . . µ m ) (the operation of addition is not associative). (2) (I, µ I ) • (J , µ J ) := (I • J, µ I + µ J ). Lemma 2.7.1. (1) supp((I 1 , µ 1 ) + . . . + (I m , µ m )) = supp(I 1 , µ 1 ) ∩ . . . ∩ supp(I m , µ m ).
Moreover, multiple blow-ups (X k ) of (I 1 , µ 1 ) + . . . + (I m , µ m ) are exactly those which are simultaneous multiple blow-ups for all (I j , µ j ), and, for any k, we have the following equality for the controlled transforms (I j , µ I ) k :

(I 1 , µ 1 ) k + . . . + (I m , µ m ) k = [(I 1 , µ 1 ) + . . . + (I m , µ m )] k .
(2) supp(I, µ I ) ∩ supp(J , µ J ) ⊇ supp((I, µ I ) • (J , µ J )). Moreover, any simultaneous multiple blow-up X i of both ideals (I, µ I ) and (J , µ J ) is a multiple blow-up for (I, µ I ) • (J , µ J ), and for the controlled transforms (I k , µ I ) and (J k , µ J ), we have the equality

(I k , µ I ) • (J k , µ J ) = [(I, µ I ) • (J , µ J )] k .
2.8. Homogenized ideals and tangent directions. Let (I, µ) be a marked ideal of maximal order. Set T (I) := D µ-1 I. By the homogenized ideal we mean

H(I, µ) := (H(I), µ) = (I + DI • T (I) + . . . + D i I • T (I) i + . . . + D µ-1 I • T (I) µ-1 , µ)
Remark. A homogenized ideal has two important properties:

(1) It is equivalent to the given ideal.

(2) It "looks the same" from all possible tangent directions.

By the first property we can use the homogenized ideal to construct resolution via the Giraud Lemma 2.6.6. By the second property such a construction does not depend on the choice of tangent directions. (2) For any multiple blow-up (X k ) of (I, µ),

(H(I), µ) k = (I, µ) k + [D(I, µ)] k • [(T (I), 1)] k + . . . [D µ-1 (I, µ)] k • +[(T (I), 1)] µ-1 k .
Although the following Lemmas 2.8.2 and 2.8.3 are used in this paper only in the case E = ∅, we formulate them in slightly more general versions.

Lemma 2.8.2. Let (X, I, E, µ) be a marked ideal of maximal order. Assume there exist tangent directions u, v ∈ T (I, µ) x = D µ-1 (I, µ) x at x ∈ supp(I, µ) which are transversal to E. Then there exists an automorphism φ uv of the completion

X x := Spec( O x,X ) such that (1) φ * uv (H I) x = (H I) x ; (2) φ * uv (E) = E; (3) φ * uv (u) = v; (4) supp( I, µ) := V (T ( I, µ)) is contained in the fixed point set of φ.
Proof. (0) Construction of the automorphism φ uv . Find parameters u 2 , . . . , u n transversal to u and v such that u = u 1 , u 2 , . . . , u n and v, u 2 , . . . , u n form two sets of parameters at x and divisors in E are described by some parameters u i where i ≥ 2. Set

φ uv (u 1 ) = v, φ uv (u i ) = u i for i > 1. (1) Let h := v -u ∈ T (I). For any f ∈ I, φ * uv (f ) = f (u 1 + h, u 2 , . . . , u n ) = f (u 1 , . . . , u n ) + ∂f ∂u 1 • h + 1 2! ∂ 2 f ∂u 2 1 • h 2 + . . . + 1 i! ∂ i f ∂u i 1 • h i + . . .

The latter element belongs to

I + D I • T (I) + . . . + D i I • T (I) i + . . . + D µ-1 I • T (I) µ-1 = H I. Hence φ * uv ( I) ⊂ H I. (2)(3) follow from the construction. (4) The fixed point set of φ * uv is defined by u i = φ * uv (u i ), i = 1, . . . , n; that is, by h = 0. But h ∈ D µ-1 (I) is 0 on supp(I, µ).
Lemma 2.8.3. Glueing Lemma. Let (X, I, E, µ) be a marked ideal of maximal order for which there exist tangent directions u, v ∈ T (I, µ) at x ∈ supp(I, µ) which are transversal to E. Then there exist étale neighborhoods

φ u , φ v : X → X of x = φ u (x) = φ v (x) ∈ X, where x ∈ X, such that (1) φ * u (H(I)) = φ * v (H(I)); (2) φ * u (E) = φ * v (E); (3) φ * u (u) = φ * v (v). Set (X, I, E, µ) := φ * u (X, H(I), E, µ) = φ * v (X, H(I), E, µ).
(4) For any y ∈ supp(X, I, E, µ), φ u (y) = φ v (y).

(5) For any multiple blow-up (X i ) of (X, I, ∅, µ), the induced multiple blow-ups φ * u (X i ) and φ * v (X i ) of (X, I, E, µ) are the same (defined by the same centers).

Set (X

i ) := φ * u (X i ) = φ * v (X i ). (6) For any y i ∈ supp(X i , I i , E i , µ), φ ui (y i ) = φ vi (y i ), where φ ui , φ vi : X i → X i are the induced morphisms.
Proof. (0) Construction of étale neighborhoods φ u , φ v : U → X. Let U ⊂ X be an open subset for which there exist u 2 , . . . , u n which are transversal to u and v on U such that u = u 1 , u 2 , . . . , u n and v, u 2 , . . . , u n form two sets of parameters on U , and the divisors in E are described by some u i , where i ≥ 2. Let A n be the affine space with coordinates x 1 , . . . , x n . First construct étale morphisms φ 1 , φ 2 :

U → A n with φ * 1 (x i ) = u i for all i and φ * 2 (x 1 ) = v, φ * 2 (x i ) = u i for i > 1. Then X := U × A n
U is a fiber product for the morphisms φ 1 and φ 2 . The morphisms φ u , φ v are defined to be the natural projections

φ u , φ v : X → U such that φ 1 φ u = φ 2 φ v . Set w 1 := φ * u (u) = (φ 1 φ u ) * (x 1 ) = (φ 2 φ v ) * (x 1 ) = φ * v (v), w i := φ * u (u i ) = φ * v (u i ), for i ≥ 2.
(1), ( 2), (3) follow from the construction. (4) Let h := vu. By the above the morphisms φ u and

φ v coincide on φ -1 u (V (h)) = φ -1 v (V (h))
. By (4), a blow-up of a center C ⊂ supp(H(I)) lifts to the blow-ups at the same center φ -1 u (C) = φ -1 v (C). Thus ( 5), ( 6) follow (see [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF] for details).

2.9. Coefficient ideals and Giraud Lemma. The idea of a coefficient ideal was originated by Hironaka and then developed in papers of Villamayor and Bierstone-Milman.

Example 2.9.1. Motivating example. Assume that u = 0 defines locally a hypersurface of maximal contact. Consider a coordinate system u = u 1 , u 2 , . . . , u n . Write any function f ∈ (I, µ) as follows

f := c µ,f • u µ + c µ-1,f (u 2 , . . . , u n )u µ-1 + . . . + c 0,f ((u 2 , . . . , u n )
Then it can be easily seen that

ord x (f ) ≥ µ ⇔ ord x (c µ-i,f ) ≥ µ -i for all i = 1, . . . , µ.
In other words, supp(

I, µ) = supp(Coeff V (u) (I, µ)), where Coeff V (u) (I, µ) := {((c µ-i,f |V (u) ) f ∈I , µ -i)|i = 1, . . . , µ}.
Here Coeff V (u) (I, µ) can be considered as a very first definition of coefficient ideal. It allows one to reduce resolution of (I, µ) to a resolution of Coeff V (u) (I, µ) "living" on a hypersurface of maximal contact. One of the problems here is that this definition depends on a choice of coordinates. That is why we replace it with the definition below.

It is important to observe that the controlled transformed preserves the form above:

σ c (f, µ) := c µ,f • u ′µ + c ′ µ-1,f (u ′ 2 , . . . , u ′ n )u ′µ-1 + . . . + c ′ 0,f ((u ′ 2 , . . . , u ′ n ), where u ′ = σ c (u, 1), c ′ µ-i,f = σ c (c µ-i,f , µ -i). In other words supp(σ c (I, µ)) = supp(σ c (Coeff V (u) (I, µ))).
The following definition modifies and generalizes the definition of Villamayor.

Definition 2.9.2. Let (I, µ) be a marked ideal of maximal order. By the coefficient ideal we mean

C(I, µ) = µ i=1 (D i I, µ -i).
Remark. The coefficient ideal C(I) has two important properties:

(1) C(I) is equivalent to I.

(2) The intersection of the support of (I, µ) with any smooth subvariety S is the support of the restriction of C(I) to S:

supp(I) ∩ S = supp(C(I) |S ).
Moreover this condition is persistent under relevant multiple blow-ups.

These properties allow one to control and modify the part of support of (I, µ) contained in S by applying multiple blow-ups of C(I) |S .

Lemma 2.9.3. C(I, µ) ≃ (I, µ).

Proof. By Lemma 2.7.1, multiple blow-ups of C(I, µ) are simultaneous multiple blow-ups of D i (I, µ) for 0 ≤ i ≤ µ-1. By Lemma 2.5.3, multiple blow-ups of (I, µ) define multiple blow-ups of all D i (I, µ). Thus multiple blow-ups of (I, µ) and C(I, µ) are the same and supp(C(I, µ)

) k = supp(D i I, µ -i) k = supp(I k , µ).
Lemma 2.9.4. Let (X, I, E, µ) be a marked ideal of maximal order. Assume that S has only simple normal crossings with E. Then supp(I, µ) ∩ S = supp(C(I, µ) |S ).

Moreover let (X i ) be a multiple blow-up with centers C i contained in the strict transforms S i ⊂ X i of S.

Then:

(1) The restrictions σ i|Si :

S i → S i-1 of the morphisms σ i : X i → X i-1 define a multiple blow-up (S i ) of C(I, µ) |S . (2) supp(I i , µ) ∩ S i = supp[C(I, µ) |S ] i . (3) Every multiple blow-up (S i ) of C(I, µ) |S defines a multiple blow-up (X i ) of (I, µ) with centers C i contained in the strict transforms S i ⊂ X i of S ⊂ X.
Proof. By Lemma 2.9. The above relation is preserved by multiple blow-ups of (I, µ). For details see [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF].

Lemma 2.9.5. Let φ : X ′ → X be an étale morphism of smooth varieties and let (X, I, ∅, µ) be a marked ideal. Then

(1) φ * (D(I)) = D(φ * (I)); (2) φ * (H(I)) = H(φ * (I)); (3) φ * (C(I)) = C(φ * (I)).
Proof. Note that for any point x ∈ X the completion φ *

x is an isomorphism. Thus φ * x (D(I)) = D((I)) and therefore φ * (D(I)) = D(φ * (I)). ( 2) and (3) follow from (1).

Resolution algorithm

The presentation of the following Hironaka resolution algorithm builds upon Bierstone-Milman's, Villamayor's and Wlodarczyk's algorithms which are simplifications of the original Hironaka proof. We also use Kollár's trick allowing to completely eliminate the use of invariants.

Remarks. (1) Note that a blow-up of codimension one components is an isomorphism. However it defines a nontrivial transformation of marked ideals. The inverse image of the center is still called the exceptional divisor.

(2) In the actual desingularization process, this kind of blow-up may occur for some marked ideals induced on subvarieties of ambient varieties. Though they define isomorphisms of these subvarieties, they determine blow-ups of ambient varieties which are not isomorphisms.

(3) The blow-up of the center C which coincides with the whole variety X is an empty set. The main feature which characterizes the notion of blow-up is the following "restriction property":

If X is a smooth variety containing a smooth subvariety Y ⊂ X, which contains the center C ⊂ Y then the blow-up σ C,Y : Ỹ → Y at C coincides with the strict transform of Y under the blow-up σ C,X : X → X, i.e., Ỹ ≃ σ -1 C,X (Y \ C).
Inductive setup. Let (X, I, E, µ) denote an arbitrary marked ideal. We will present an algorithm which establishes the following assertion, by induction on the dimension of X. Theorem 3.0.6. There is an associated resolution (X i ) 0≤i≤mX , called canonical, satisfying the following conditions:

(1) For any surjective étale morphism φ :

X ′ → X the induced sequence (X ′ i ) = φ * (X i ) is the canonical resolution of (X ′ , I ′ , E ′ , µ) := φ * (X, I, E, µ).
(2) For any étale mophism φ :

M ′ → M the induced sequence (X ′ i ) = φ * (X i ) is an extension of the canonical resolution of (X ′ , I ′ , E ′ , µ) := φ * (X, I, E, µ).
Proof. If I = 0 and µ > 0 then supp(X, I, µ) = X, and the blow-up of X is the empty set and thus it defines a unique resolution. Assume that I = 0.

We will use induction on the dimension of X. If X is 0-dimensional, I = 0 and µ > 0 then supp(X, I, µ) = ∅ and all resolutions are trivial.

Step 1. Resolving a marked ideal (X, I, E, µ) of maximal order. Before performing the resolution algorithm for the marked ideal (I, µ) of maximal order in Step 1 we will replace it with the equivalent homogenized ideal C(H(I, µ)). Resolving the ideal C(H(I, µ)) defines a resolution of (I, µ) at this step. To simplify notation we shall denote C(H(I, µ)) by J = (J , µ(J )).

Step 1a. Reduction to the nonboundary case. Moving supp J and H s α apart . For any multiple blow-up (X i ) of (X, J , E, µ(J )), we will denote (for simplicity) the strict transform of E on any X i also by E.

For any x ∈ X i , let s(x) denote the number of divisors in E through x and set

s i = max{s(x) | x ∈ supp J i )}.
Let s = s 0 . By assumption the intersections of any s > s 0 components of the exceptional divisors are disjoint from supp J . Each intersection of divisors in E is locally defined by the intersection of some irreducible components of these divisors. Find all intersections H s α , α ∈ A, of s irreducible components of divisors E such that supp J ∩ H s α = ∅. By the maximality of s, the supports supp

J |H s α ) ⊂ H s α are disjoint from H s α ′ , where α ′ = α. Set H s := α H s α , U s := X \ H s+1 , H s := H s \ H s+1 . Then H s ⊂ U s is a smooth closed subset U s . Moreover H s ∩ supp(J ) = H s ∩ supp(J ) is closed.
Construct the canonical resolution of J |H s . By Lemma 2.9.4, it defines a multiple blow-up of (J , µ(J )) such that supp J j1 ∩ H s j1 = ∅. In particular the number of the strict tranforms of E passing through a single point of the support drops s j1 < s. Now we put s = s j1 and repeat the procedure. We continue the above process until s j k = s r = 0. Then (X j ) 0≤j≤r is a multiple blow-up of (X, J , E, µ(J )) such that supp J r does not intersect any divisor in E.

Therefore (X j ) 0≤j≤r and further longer multiple blow-ups (X j ) 0≤j≤m for any m ≥ r can be considered as multiple blow-ups of (X, J , ∅, µ(J )) since starting from X r the strict transforms of E play no further role in the resolution process since they do not intersect supp J j for j ≥ r. We reduce the situation to the "nonboundary case" E = ∅.

Step 1b. Nonboundary case. Let (X j ) 0≤j≤r be the multiple blow-up of (X, J , ∅, µ(J )) defined in Step 1a.

For any x ∈ supp J ⊂ X, find a tangent direction u α ∈ D µ(J )-1 (J ) on some neighborhood U α of x. Then V (u α ) ⊂ U α is a hypersurface of maximal contact. By the quasicompactness of X, we can assume that the covering defined by U α is finite. Let U iα ⊂ X i be the inverse image of U α and let

H iα := V (u α ) i ⊂ U iα denote the strict transform of H α := V (u α ).
Set (see also [START_REF] Kollár | Lectures on Resolution of singularities[END_REF])

X := U α H := H α ⊆ X.
The closed embeddings H α ⊆ U α define the closed embedding H ⊂ X of a hypersurface of maximal contact H.

Consider the surjective étale morphism

φ U : X := U α → X.
Denote by J the pull back of the ideal sheaf J via φ U . The multiple blow-up (X i ) 0≤i≤r of J defines a multiple blow-up ( X 0≤i≤r ) of J and a multiple blow-up ( H i ) 0≤i≤r of J |H .

Construct the canonical resolution of ( H i ) r≤i≤m of the marked ideal J r| Hr on H r . It defines, by Lemma 2.9.3, a resolution ( X r≤i≤m ) of J r and thus also a resolution ( X i ) 0≤i≤m of ( X, J , ∅, µ(J )). Moreover both resolutions are related by the property supp( J i ) = supp( J i| Hi ).

Consider a (possible) lifting of φ U :

φ iU : X i := U iα → X i ,
which is a surjective locally étale morphism. The lifting is constructed for 0 ≤ i ≤ r.

For r ≤ i ≤ m the resolution X i is induced by the canonical resolution ( H i ) r≤i≤m of J r| Hr

We show that the resolution ( X i ) r≤i≤m descends to the resolution (X i ) r≤i≤m .

Let C j0 = C j0α be the center of the blow-up σ j0 : X j0+1 → X j0 . The closed subset C j0α ⊂ U j0α defines the center of an extension of the canonical resolution (H jα ) r≤j≤m .

If C j0α ∩ U j0β = ∅, then, by the canonicity and condition (2) of the inductive assumption, the subset C j0αβ := C j0α ∩ U j0β defines the center of an extension of of the canonical resolution H jαβ := ((H jα ∩ U jβ )) r≤j≤m . On the other hand C j0βα := C j0β ∩ U jα defines the center of an extension of the canonical resolution ((

H jβα := H jβ ∩ U jα )) r≤j≤m .
By the Glueing Lemma 2.8.3 for the tangent directions u α and u β , there exist étale neighborhoods

φ uα , φ u β : U αβ → U αβ := U α ∩ U β of x = φ u (x) = φ v (x) ∈ X, where x ∈ X, such that (1) φ * uα (J ) = φ * u β (J ); (2) φ * uα (E) = φ * u β (E); (3) φ -1 uα (H jαβ ) = φ -1 u β (H jβα ); (4) φ uα (x) = φ u β (x) for x ∈ supp(φ * uα (J ))
. Moreover, all the properties lift to the relevant étale morphisms φ uαi , φ u βi : U αβi → U αβi . Consequently, by canonicity, φ -1 uαj0 (C j0αβ ) and φ -1 u β j0 (C j0βα ) both define the next center of the extension of the canonical resolution φ

-1 uα (H j0αβ ) = φ -1 u β (H j0βα ) of φ * uαj0 (J |H αβ ) = φ * u β (J |H βα ). Thus φ -1 uα (C j0αβ ) = φ -1 u β (C j0βα
), and finally, by property (4),

C j0αβ = C j0βα .
Consequently C j0 descends to a smooth closed center C j0 = C j0α ⊂ X j0 and the resolution ( X i ) r≤i≤m descends to a resolution (X i ) r≤i≤m .

Step 2. Resolving marked ideals (X, I, E, µ). For any marked ideal (X, I, E, µ) write

I = M(I)N (I),
where M(I) is the monomial part of I, that is, the product of the principal ideals defining the irreducible components of the divisors in E, and N (I) is the nonmonomial part which is not divisible by any ideal of a divisor in E. Let In particular O(I, µ) = (I, µ) for ideals (I, µ) of maximal order.

Step 2a. Reduction to the monomial case by using companion ideals. By Step 1 we can resolve the marked ideal of maximal order O(I) = O(I, µ) = (O(I), µ(O(I))). By Lemma 2.7.1, for any multiple blow-up of O(I, µ),

supp(O(I, µ)) i = supp[N (I), ord N (I) ] i ∩ supp[M (I), µ -ord N (I) ] i = supp[N (I), ord N (I) ] i ∩ supp(I i , µ).
Consequently, such a resolution leads to an ideal (I r1 , µ) such that ord N (Ir 1 ) < ord N (I) . Then we repeat the procedure for (I r1 , µ). We find marked ideals (I r0 , µ) = (I, µ), (I r1 , µ), . . . , (I rm , µ) such that ord N (I0) > ord N (Ir 1 ) > . . . > ord N (Ir m ) . The procedure terminates after a finite number of steps when we arrive at an ideal (I rm , µ) with ord N (Ir m ) = 0 or with supp(I rm , µ) = ∅. In the second case we get a resolution. In the first case I rm = M(I rm ) is monomial.

Step 2b. Monomial case I = M(I). The collection of divisors E is ordered (see Definitions 2.1.1 and 2.1.3); say E = {D 1 , D 2 , . . .}. Let Sub(E) denote the set of all subsets of E. The ordering of E induces a natural lexicographic order on Sub(E): We can associate to each S ∈ Sub(E) the lexicographic order of the binary sequence (δ 1 , δ 2 , . . .), where δ i = 0 or 1 according as D i / ∈ S or D i ∈ S. (The actual formula for the order is irrelevant as long as it is canonical and linear for the divisors passing through a point.)

Let x 1 , . . . , x k define equations of the components D x 1 , . . . , D x k ∈ E through x ∈ supp(X, I, E, µ) and let I be generated by a monomial x (a1,...,a k ) at x. In particular ord x (I)(x) := a 1 + . . . + a k .

Let ρ(x) := {D i1 , . . . , D i l } ∈ Sub(E) be the maximal (with respect to the order on Sub(E)) subset satisfying the properties (1) a i1 + . . . + a i l ≥ µ.

(2) For any j = 1, . . . , l, a i1 + . . . + ǎij + . . . + a i l < µ.

Let R(x) denote the subsets in Sub(E) satisfying the properties (1) and (2). The maximal irreducible components of the supp(I, µ) through x are described by the intersections D∈A D where A ∈ R(x). In particular supp(I, µ) is a union of components with simple normal crossings.

The maximal locus of ρ determines at most one maximal component of supp(I, µ) through each x. The invariant ρ is introduced to describe the center of the blow-up in a unique way. As we see below to resolve monomial case we can randomly pick any maximal irreducible component of supp(I, µ). The algorithm is controlled by the order and there is no need to introduce additional invariants unless we would like to construct invariants which describe the center and decrease after blow-up. (see [START_REF] Bierstone | Canonical desingularization in characteristic zero by blowing up the maximum strata of a local invariant[END_REF], [START_REF] Encinas | Good points and constructive resolution of singularities[END_REF]) After the blow-up at the maximal locus C = {x i1 = . . . = x i l = 0} of ρ, the ideal I = (x (a1,...,a k ) ) is equal to I ′ = (x ′ (a1,...,ai j -1 ,a,ai j +1 ,...,a k ) ) in the neighborhood corresponding to x ij , where a = a i1 +. . .+a i l -µ < a ij . In particular the invariant ord x (I) drops for all points of some maximal components of supp(I, µ). Thus the maximal value of ord x (I) on the maximal components of supp(I, µ) which were blown up is bigger than the maximal value of ord x (I) on the new maximal components of supp(I, µ). The algorithm terminates after a finite number of steps.

3.1. Summary of the resolution algorithm. The resolution algorithm can be represented by the following scheme.

Step 2. Resolve (I, µ).

Step 2a. Reduce (I, µ) to the monomial marked ideal I = M(I). Step 1a. Move apart all strict transforms of E and supp J .

⇓

Move away all intersections H s α of s divisors in E (where s is the maximal number of divisors in E through points in supp J = supp O(I)).

For any α, resolve J |( α H s α ) .

Step 1b. If the strict transforms of E do not intersect supp J , resolve J .

Simultaneously resolve all J |V (u) , where V (u) is a hypersurface of maximal contact. (Use the property of homogenization ( [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF]), and Kollár's trick ( [START_REF] Kollár | Lectures on Resolution of singularities[END_REF]).

Step 2b. Resolve the monomial marked ideal I = M(I). (2) If µ = 1 the companion ideal is equal to O(I, 1) = (N (I), µ N (I) ) so the general strategy of the resolution of (I, µ) is to decrease the order of the nonmonomial part and then to resolve the monomial part.

(3) In particular, in order to desingularize Y , we put µ = 1 and I = I Y , where I Y is the sheaf of the subvariety Y , and we resolve the marked ideal (X, I, ∅, µ). The nonmonomial part N (I i ) is nothing but the weak transform (σ i ) w (I) of I.

In the next sections, we provide a complexity bound for the algorithm.

Complexity bounds on a blow-up

Our purpose for the rest of the paper is to estimate the complexity of the desingularization algorithm described in the previous sections.

Preliminary setup.

4.1.1. Affine marked ideals. An input of the algorithm is an affine marked ideal; that is, a collection of tuples

T := ({X α,β , I α,β , E α,β , U α,β , (C nα ) α | α ∈ A, β ∈ B α }, µ),
where:

(1) (C nα ) α ≃ C nα . (2) {U α,β | β ∈ B α } is an open cover of (C nα ) α . (3) U α,β ⊂ (C nα ) α is an open subset whose complement is given by f α,β = 0. (4) X α,β ⊂ (C nα ) α is a closed subset such that X α,β ∩ U α,β is a nonsingular m-dimensional variety
(possibly reducible). Moreover there exists a set of parameters (coordinates) on U α,β ,

u α,β,1 , . . . , u α,β,nα ∈ C[x α,1 , . . . , x α,nα ],
such that u α,β,i is a coordinate x α,j describing an exceptional divisor or it is transversal to the exceptional divisors (over U α,β ) , and, moreover,

I X α,β = (u α,β,i1 , . . . , u α,β,i k ) ⊂ C[x α,1 , ..., x α,nα ],
for a certain subset {i 1 , . . . , i k } ⊂ {1, . . . , n α }. (5) I α,β = g α,β,1 , . . . , g α,β,j ⊂ C[x α,1 , . . . , x α,nα ] is an ideal, (6) E α,β is a collection of s ≤ m smooth divisors in (C nα ) α described by some x α,j = 0, where j = n αs + 1, . . . , n α . The divisors in E α,β are either transversal to X α,β or they contain X α,β . The restrictions of the divisors in E α,β that are transversal to X α,β define the exceptional divisors on X α,β . (7) There exist birational maps i α1β1,α2,β2 : X α1,β1 X α2,β2 given by

X α1,β1 ∋ x → i α1β1,α2,β2 (x) = ( v α1β1,α2,β2,1 w α1β1,α2,β2,1 , . . . , v α1β1,α2,β2,nα 2 w α1β1,α2,β2,nα 2 )(x) ∈ X α2,β2
for regular functions v α1β1,α2,β2,1 , . . . , v α1β1,α2,β2,nα 2 , w α1β1,α2,β2,1 , . . . , w α1β1,α2,β2,nα 2 in C[x α1,1 , . . . , x α1,nα 1 ]. [START_REF] Bierstone | Uniformization of analytic spaces[END_REF] The birational maps i αβ,α ′ ,β ′ determine uniquely up to an isomorphism a variety X T in the following sense: There exist open embeddings j α,β : X α,β ∩ U α,β ֒→ X T defining an open cover of X T , and satisfying j -1 α2,β2 j α1,β1 = i α1β1,α2,β2 . (9) µ ≥ 0 is an integer. [START_REF] Bierstone | Canonical desingularization in characteristic zero by blowing up the maximum strata of a local invariant[END_REF]

supp(I α,β , µ) ∩ U α,β ∩ U α,β ′ = supp(I α,β ′ , µ) ∩ U α,β ∩ U α,β ′ .
Remarks. (1) The objects X α,β , E α,β , I α,β , as well as corresponding functions g α,β,i , u α,β,j , x α,i are relevant for the algorithm after they are restricted to U α,β . Their behavior in the complement (C nα ) α \ U α,β has no relevance.

(2) The operation of restricting to maximal contact leads to considering open subsets U α,β ⊂ (C nα ) α .

(3) While studying the complexity of the algorithm we will assume that the coefficients of the input polynomials belong just to Z. All general considerations are given for coefficients from C, and remain valid for any algebraically closed field of zero characteristic.

(

) 4
The open embeddings j α,β can be constructed from i α1β1,α2,β2 after performing the algorithm but we do not dwell on this.

′ := ({X α ′ ,β ′ , I α,β , E α,β , U α,β , (C nα ) α | α ∈ A ′ , β ∈ B ′ α }, µ)
, is defined over T , provided:

(1) There exist maps of index-sets p : A ′ → A , and

p α ′ : B ′ α ′ → B p(α ′ ) . (2)
The canonical projection on the first α = p(α ′ ) components

π ′ α : (C n α ′ ) α ′ → (C nα ) α determine birational morphisms π α ′ ,β ′ := π ′ |X α ′ ,β ′ : X α ′ ,β ′ → X α,β commuting with i α1β1,α2,β2 and i α ′ 1 β ′ 1 ,α ′ 2 ,β ′ 2 .
(3) There exist natural birational morphisms X T ′ → X T commuting with j α,β , and j α ′ ,β ′ .

We introduce the following functions to characterize the affine marked ideal

T := ({X α,β , I α,β , E α,β , U α,β } α,β , (C nα ) α , µ) : (1) m(T ) = dim(X T ), (2) µ(T ) = µ, (3)
d(T ) is the maximal degree of all polynomials in Ψ(T ) := {u α,β,i , g α,β,i , f α,β , v α,β,α2,β2,i , w α,β,α2,β2,j .} (4) n(T ) = max n α , (5) l(T ) is the maximal number of all polynomials in Ψ(T ). ( 6) q(T ) is the number of neighborhoods U α,β in T ( i. e the number of the indices such that α ∈ A, β ∈ B). ( 7) b(T ) the maximum bit size of any (integer) coefficient of each of the polynomials in Ψ(T )

Remark. The function b(T ) is used only for the estimation of the total complexity of the algorithm. In particular it has no relevance for the estimates of the number of blow-ups, the maximal embedding dimension n(T ), or the number of neighborhoods.

Algorithmically the input is represented by the coefficients of polynomials describing an affine marked ideal T 0 . We assume

m(T 0 ) = m, d(T 0 ) ≤ d 0 , n(T 0 ) ≤ n 0 , l(T 0 ) ≤ l 0 , b(T 0 ) ≤ b 0 .
Then in particular, the total bit-size of the input does not exceed b 0

• l 0 • d O(n0) 0 , cf. [27].
4.1.2. Resolution of singularities. For simplicity consider an irreducible affine variety Y ⊂ C n described by some equations. The algorithm resolves Y by the following procedure:

Step A. Find the generators of I Y = g 1 , . . . , g j ⊂ C[x 1 , . . . , x n ] and construct the affine marked ideal

T := (X = C n , I Y , E = ∅, U = C n , C n , µ = 1)
Step B. Start the resolving procedure for the affine marked ideal

({X = C n , I Y , E = ∅, U = C n }, C n , µ = 1) (see below).
Step C. Pick a nonsingular point p ∈ Y ⊂ C n . Stop the resolution procedure when the constructed center of the following blow-up in the algorithm passes through the inverse image of p. As an output of the resolution algorithm we get an affine marked ideal

T ′ := ({X α ′ ,β ′ , I α ′ ,β ′ , E α ′ ,β ′ , U α,β , C n α ′ } α ′ ,β ′ , 1
) over T . In particular we have a collection of projections

π α ′ : (C n α ′ ) α ′ → C n
(projection on the first n coordinates.). (Note that the restriction of π α defines a birational morphism

π α ′ ,β ′ : X α ′ ,β ′ → X which is an isomorphism in a neighborhood of p ∈ X.)
The center of the following blow-up is described on some open subcover 4.1.3. Principalization. Given a smooth affine variety X ⊂ C n , described by equations u X,i = 0, and an ideal I = (g 1 , . . . , g k ) on X and on C n .

{U α ′ ,β ′′ } α ′ ∈A ′ ,β ′′ ∈B ′′ α ′ of {U α ′ ,β ′ } α ′ ∈A ′ ,β ′ ∈B ′ α ′ by C α ′ ,β ′′ ∩U α ′ ,β ′′ , for closed subsets C α ′ ,β ′′ ⊂ (C n α ′ ) α ′ . Consider the unique irreducible component Cα ′ ,β ′′ of C α ′ ,β ′′ containing the inverse image of the point p. Then π α ′ ,β ′′ := π | Cα ′ ,β ′′ ∩U α ′ ,β ′′ : Ỹα ′ ,β ′′ := Cα ′ ,β ′′ ∩ U α ′ ,β ′′ → Y
Step A. First the algorithm finds affine neighbourhoods U α,β in C n each given by an inequality f α,β = 0 in which X is represented by a family of local parameters

u 1 = • • • = u n-m = 0.
Moreover, it finds coordinates x i on C n , such that (up to index permutation)

u 1 , • • • , u n-m , x n-m+1 , . . . , x n is a complete set of parameters.
The local parameters u i are chosen among the input polynomials. To this end the algorithm can for each choice of {i 1 , . . . , i n-m } ⊂ {1, . . . , i} pick an identically non-vanishing minor f α,β of the Jacobian matrix of {u i } i .

We construct an affine marked ideal given by an input tuple by

T := ({X β := X, I β := I, E β = ∅, U β , C n } β , µ = 1).
Step B. The algorithm resolves T = ({X β := X, I β := I, E β = ∅, U β , C n } β , µ = 1). As an output, we get

T ′ := ({X α ′ ,β ′ , I α ′ ,β ′ , E α ′ ,β ′ , U α ′ ,β ′ , (C n α ′ ) α ′ } α ′ ,β ′ , , 1)
, over T .

Step C. The variety

X ′ := X T ′ is described by an open cover {X α ′ ,β ′ ∩ U α ′ ,β ′ } α ′ ,β ′ for closed subsets X α ′ ,β ′ ⊂ C n α ′ , and open subsets U α ′ ,β ′ ⊂ C n α ′ (see (8) from 4.1.

1). Moreover, we have a collection of birational morphisms π

α ′ ,β ′ : X α ′ ,β ′ ∩ U α ′ ,β ′ → X ⊂ C n . The principal ideal on X α ′ ,β ′ is generated by (g 1 • π α ′ ,β ′ . . . , g k • π α ′ ,β ′ ) = (x a1 1 . . . x an α ′ n α ′ ) 4.
2. Description of blow-up. Consider an affine marked ideal

T := ({X α,β , I α,β , E α,β , U α,β , (C nα ) α | α ∈ A, β ∈ B α }, µ)
corresponding to a marked ideal (X, I, E, µ). Let C ⊂ X be a smooth center described as follows:

We assume that there is an open subcover cover

{U α,β ′ } α∈A,β ′ ∈B ′ α ⊂ (C nα ) α ≃ C n of U α,β , together with a map of indices ρ : B ′ α → B α , and a collection of closed subvarieties C α,β ′ ⊂ (C nα ) α (of dimension k αβ ′ ≤ m), such that (1) ρ(β ′ )=β U α,β ′ = U α,β ; (2) C α,β ′ ∩ U α,β ′ ⊂ supp(I α,β ′ ,µ) ∩ U α,β ′ ; (3) C α,β ′ is described on each U α,β ′ by a set of local parameters u α,β ′ ,1 , . . . , u α,β ′ ,nα-m , u αβ ′ ,nα-m+1 , . . . , u α,β ′ ,nα-k αβ ′ ∈ C[x 1 , . . . , x nα ], i.e., u α,β ′ ,1 = . . . = u α,β ′ ,nα-m = u αβ ′ ,nα-m+1 = . . . = u α,β ′ ,nα-k αβ ′ = 0, where X α,β is described on U α,β ⊃ U α,β ′ by u α,β ′ ,1 = . . . = u α,β ′ ,nα-m = 0; (4) u α,β ′ ,1 , . . . , u α,β ′ ,nα-k αβ ′
are transversal to the exceptional divisors (over U α,β ′ ), or coincide with coordinate functions describing the exceptional divisors. The open cover after blow-up. The blow-up creates a new collection of ambient affine spaces (C n α ′ ) α ′ . Namely, we can associate with functions u α,β ′ ,i on (C nα ) α , where i = 1, . . . , n α -

Denote by

T ′ := ({X α ′ ,β ′ , I α ′ ,β ′ , E α ′ ,β ′ , U α ′ ,β ′ , (C n α ′ ) α ′ | α ′ ∈ A ′ , β ′ ∈ B ′ α ′ },
k αβ ′ , the n α -k αβ ′ affine charts (C n α ′ ) α ′ , where α ′ := (α, i), i = 1, . . . , n α -k αβ ′ , n α ′ := 2n α -k αβ ′ We also create a new collection of open subsets U α ′ ,β ′ ⊂ (C n α ′ ) α ′ by taking the inverse images of U α,β ′ ⊂ (C nα ) α under the morphisms (C n α ′ ) α ′ → (C nα ) α .

The birational maps. The natural projection π

α : (C n α ′ ) α ′ → (C nα ) α on the first n α components defines the birational morphism π α ′ ,β ′ = π α|X α ′ ,β ′ : X α ′ ,β ′ → X α,β ′ , for any α, β ′ , such that X α,β ′ = ∅. This defines birational morphisms i α ′ 1 β ′ 1 ,α ′ 2 ,β ′ 2 : X α ′ 1 ,β ′ 1 π α ′ 1 ,β ′ 1 → X α1,β ′ 1 i α 1 β ′ 1 ,α ′ 2 ,β 2 X α2,β ′ 2 π -1 α ′ 2 ,β ′ 2 ← X α ′ 2 ,β ′ 2 . Consider a blow-up X T ′ of C ⊂ X T . There exist open embeddings j α ′ ,β ′ : X α ′ ,β ′ ∩ U α ′ ,β ′ ֒→ X T ′ induced by j α,β : X α,β ′ ∩ U α,β ′ ֒→ X T ,
defining an open cover of X T ′ , and satisfying

j -1 α ′ 2 ,β ′ 2 • j α ′ 1 ,β ′ 1 = i α ′ 1 β ′ 1 ,α ′ 2 ,β ′ 2 .
Equations of blow-up. Without loss of generality the blow-up in each of the n αk αβ ′ affine charts (C n α ′ ) α ′ , where α ′ := (α, i), i = 1, . . . , n αk αβ ′ , can be described as follows: (For simplicity, we drop the α, β indices below.)

Assume that the function u i0 , i 0 ≤ nk, defines the chart of the blow-up. The blow-up of C n is a closed subset bl(C n ) of C 2n-k described by the following equations

u j -u i0 x j+n = 0 for 0 < j ≤ n -k, j = i 0 , u i0 -x i0+n = 0.
The exceptional divisors. The exceptional divisor for this blow-up is given by u i0 = 0 on bl(C n ). Since u i0 = x i0+n we may represent it by the coordinate x i0+n on C 2n-k .

The previous exceptional divisors keep their form x j = 0 if they do not describe C, or they convert to x j+n (= u j /u i0 ) if they were described by the function u j ≡ x j .

The strict transform of X. Recall that X is described by u 1 = . . . = u n-m = 0 on U ⊂ C n . The blow-up of X = X α,β is a closed subset X ′ ⊂ C 2n-k which is described by a new set of equations:

(1) u ju i0 x j+n = 0 for 0 < j ≤ nk, j = i 0 ;

(2) u i0x i0+n = 0;

(3) x j+n = 0 for 0 < j ≤ nm, j = i 0 .

In some situations we consider additionally the induced equation

(4) 1 = 0 if 0 < i 0 ≤ n -m.
(Note that the equations of the first two types describe the blow-up bl(C n ) of C n . The third and the fourth types of the equations x j+n = u j /u i0 = 0, j = i 0 (or 1 = u i0 /u i0 = 0 ) describe the strict transform of X inside bl(C n ). In the latter case if 0 < j = i 0 ≤ nm the strict transform is an empty set in the relevant chart. Still we shall keep the uniform description of the objects and their transformations, and do not eliminate any equations in the description of the empty set.) 4.2.1. The generators of I α,β after blow-up. We will not compute the controlled transforms of the generators of I (= I α,β ) (over U ) directly. Instead we modify them first. The generators g i of I satisfy, by Lemma 2.2.1, the condition

g i • f ri ∈ I µ C + I X , where V (f ) = C n \ U ⊂ C n (we have dropped the indices α, β here).
For any generator g i write

g i • f ri = an-m+1+...+a n-k =µ h (an-m+1,...,a n-k ),i u an-m+1 n-m+1 • . . . • u a n-k n-k + j:=1...,m-n h ij u j .
Set ā := (a n-m+1 , . . . , a n-k ), ūā := u

an-m+1 n-m+1 • . . . • u a n-k n-k .
Then we can rewrite the above as

g i • f ri = |ā|=µ h ā ūā + j:=1...,m-n h ij u j .
To bound r i and deg(h ā,i ), deg(h ij ) we first consider a similar equality,

g i • f Ri = |ā|=µ H ā ūā + j:=1...,m-n H ij u j ,
for certain R i , H ā,i , H ij . We introduce a new variable z and we get an equality

g i = z Ri • ( |ā|=µ H ā ūā + j:=1...,m-n H ij u j ) + g i • ( 0≤j≤r-1 (z • f ) j ) • (1 -z • f ) ;
in other words, g i belongs to the ideal generated by {ū ā}, {u j }, 1z • f . Therefore one can represent g i as

g i = |ā|=µ H ā,i • ūā + j:=1...,m-n H ij • u j + H • (1 -z • f ) ,
for suitable polynomials H ā,i , H ij , H with degrees less than (d • µ) 2 O(n) due to [START_REF] Seidenberg | Constructions in algebra[END_REF], [START_REF] Giusti | Some effectivity problems in polynomial ideal theory[END_REF], [START_REF] Möller | Upper and lower bounds for the degree of Groebner bases[END_REF]. Hence substituting in the latter equality z = 1/f and cleaning the denominator we obtain the bound (d

• µ) 2 O(n) on r i , deg(h ā,i ), deg(h ij ).
The generators after blow-up and their degree. Using the above we can describe the controlled transform of I in terms of the controlled transforms of its modified generators. Define the modified generators of I to be ḡi = |ā|=µ h ā ūā .

Then their controlled transforms are given by

σ c (ḡ i ) = u -µ n-k σ * (h ā,i u ā).
Denote by G(d, n, µ) the bound on the degree of the resulting marked ideal T ′ after a blow up applied to a marked ideal T , provided that d(T ) ≤ d, n(T ) ≤ n. Thus, by the above:

Lemma 4.2.1. G(n, d, µ) < (d • µ) 2 O(n) .
4.3. Elementary operations and elementary auxillary functions. To estimate the complexity of the desingularization algorithm we introduce a few auxiliary functions related to the ingredients of T . It is convenient to associate to T with data (m, d, n, l, q, µ), the vector γ := (r, m, d, n, l, q, µ) ∈ Z 7 ≥0 , where r is the subscript of the element of the resolution (T r ) r=0,1,..., 4.3.1. The effect of a single blow-up. Summarizing the above we get the following:

Lemma 4.3.1. Consider the object T := ({X α,β , I α,β , E α,β , U α,β } α,β , n, µ) with data (m, µ, d, n, l, q). Let T ′ := ({X ′ α ′ ,β ′ , I ′ α ′ ,β ′ , E ′ α ′ ,β ′ , U ′ α ′ ,β ′ } α ′ ,β ′ , n α ′ , µ
) denote the object with data (m, µ, d ′ , n ′ , l ′ , q ′ ) obtained from T by a single blow-up at the center C represented by the collection of closed sets {C αβ ′′ ⊂ (C nα ) α } describing the center in open subsets U αβ ′′ ⊂ U αβ . Assume that the maximal degree of the polynomials describing the center is less than d. Assume that q gives also a bound for the number of open neighborhoods U αβ ′′ . Then

(1) d ′ ≤ G(n, d, µ) < (d • µ) 2 O(n) ; (2) n ′ ≤ 2n; (3) l ′ ≤ l + n; (4) q ′ ≤ n • q;
The effect of the single blow-up can be measured by the function

Bl(r, m, d, n, l, q, µ) := (r + 1, m, G(n, d, µ), 2n, l + n, n • q, µ).
The multiple effect of the t blow-ups can be measured by the recursive function Bl(r, m, d, n, l, q, µ, t) = Bl • Bl(r, m, d, n, l, q, µ, t -1), or, more briefly, Bl(γ, t) = Bl(Bl(γ, t -1)). Note that Bl(r, m, d, n, l, q, µ, t) = (r + t, m, G(n, d, µ, t), 2 t n, l + 2 t-1 n, (2 t+1 -1) • n t q, µ)

for the relevant function G(n, d, µ, t).

5.

Bounds on multiplicities and degrees of coefficient ideals 5.0.2. The maximal multiplicity of I on the subvariety X ⊂ C n . Let d be the maximal degree of (X, I) on C n . Denote by M (d, n) a bound on the multiplicity of the ideal I on X. To estimate M (d, n), we can assume (after a linear transformation of the coordinates) that the order of the polynomial u ijx j is at least 2 for all 1 ≤ j ≤ nm. For any polynomial g ∈ I α,β one can find polynomials

h j ∈ C[x 1 , . . . , x n ], 0 ≤ j ≤ n -m and h ∈ C[x n-m+1 , . . . , x n ] such that h 0 • g + 1≤j≤n-m h j • u ij = h(x n-m+1 , . . . , x n ). (5)
Moreover, we can rewrite the latter equality over the field C(x n-m+1 , . . . , x n ) in the form h0

• g + 1≤j≤n-m hj • u ij = 1, (6)
where hj = hi h ∈ C(x n-m+1 , . . . , x n )[x 1 , . . . , x n-m ], with the common denominator in C[x n-m+1 , . . . , x n ] for 0 ≤ j ≤ nm.

We apply to [START_REF] Aroca | Desingularization theorems[END_REF] the Effective Nullstellensatz (see e.g. [START_REF] Brownawell | Bounds for the degrees in the Nullstellensatz[END_REF], [START_REF] Giusti | On the efficiency of effective Nullstellensaetze[END_REF], [START_REF] Kollár | Sharp effective Nullstellensatz[END_REF], [START_REF] Jelonek | On the effective Nullstellensatz[END_REF]). This gives us the bound d O(n) on the degrees of hi = h i /h with respect to variables x 1 , . . . , x n-m (for certain solutions) . To find h i /h one can solve the latter equality considering it as a linear system over the field C(x n-m+1 , . . . , x n ).

The algorithm can find hj = a I,j x I with indeterminates a I,j ∈ C(x n-m+1 , . . . , x n ), and monomials 6) and solving linear system over the field C(x n-m+1 , . . . , x n ). Clearing the common denominator in [START_REF] Aroca | Desingularization theorems[END_REF] gives [START_REF] Aroca | Theory of maximal contact[END_REF] with

x I = x i1 1 • . . . • x in-m n-m with degrees i 1 + . . . + i n-m ≤ d O(n) substituting hj in (
deg(h), deg(h j ) ≤ d O(n 2 ) , 1 ≤ j ≤ n -m
Now we have to estimate the maximal multiplicity ord x (g |X ) for g ∈ C[x 1 , . . . , x n ], such that deg(g) ≤ d and x ∈ X. We use [START_REF] Aroca | Theory of maximal contact[END_REF]. We get immediately by the above: Lemma 5.0.2. The maximal multiplicity ord x (g |X ) on X for any function g ∈ C[x 1 , . . . , x n ], such that deg(g) ≤ d and x ∈ X, is bounded by the function M (d, n) = d O(n 2 ) constructed as above:

ord x (g |X ) ≤ M (d, n). Proof. ord x (g |X ) ≤ ord x (h 0 • g) |X = ord x h(x n-m+1 , . . . , x n ) |X = ord x h(x n-m+1 , . . . , x n ) ≤ deg(h) ≤ M (d, n) = d O(n 2 ) .
5.0.3. Derivations on the subvariety X ⊂ C n . In order to follow the construction of the algorithm we use the language of derivations Der X on X. Since our X is embedded into C n it is natural to represent all objects on X as the restriction of the relevant objects on C n to X ⊂ C n . Unfortunately the sheaf of derivations on C n does not restrict well to X:

Der C n |X = Der X .

Instead we consider

Der C n ,X := {D ∈ Der C n | D(I X ) ⊂ (I X )}.
Lemma 5.0.3. Let u 1 = 0 . . . , u n-m = 0 describe X ⊂ C n . Then the ring Der C n ,X is generated by

{u i • d uj } 1≤i≤n-m, 1≤j≤n-m ∪ {d uj } n-m<j≤n .
In particular the restriction Der C n ,X|X = Der X is generated by

{d uj } n-m<j≤n .
Proof. This follows from the definition.

Note that since we have

(d uj ) j = ((∂u j /∂x i ) i,j ) -1 • (d xi ) i = 1 det((∂u j /∂x i ) i,j ) adj((∂u j /∂x i ) i,j ) • (d xi ) i
we immediately get the following:

Lemma 5.0.4. Let U := {x ∈ C n | det((∂u j /∂x i ) i,j ) = 0}. The sheaf Der C n ,X is generated over U ⊂ C n by {u i • d ′ uj } 1≤i≤n-m, 1≤j≤n-m ∪ {d ′ uj } n-m<j≤n , (7)
where

(d ′ uj ) j = adj((∂u j /∂x i ) i,j ) • (d xi ) i .
The derivations [START_REF] Bierstone | Semianalytic and subanalytic sets[END_REF] generate a subsheaf Der C n ,X of Der C n ,X over C n . Both sheaves coincide over U . Thus we will replace Der C n ,X with Der C n ,X for our computations over U . Lemma 5.0.5. Let I be any ideal on C n . Assume the maximal degree of some generating set of I is ≤ d 1 , and the maximal degree of u i is less than d 2 . Then the maximal degree of generators of Der C n ,X (I) is bounded by d 1 + nd 2 . 5.0.4. Construction of the coefficient homogenized companion ideal. Recall that in step 2 for the marked ideal (I, µ), we find the maximal multiplicity μ ≤ M (d, n) of the nonmonomial part N (I), and construct the companion ideal O(I), for which we immediately take homogenized coefficient ideal J := C(H(O(I))). In our situation of the set X ⊂ C n defined by set of parameters {u i } 1≤i≤n-m on the open set U ⊂ C n we will use Der C n ,X instead of Der X for the definition above. Immediately from the definition, we get a formula for a bound A(d, n, µ) on the degrees of generators of the marked ideal C(H(I q )). Note first that we have the the following bounds on the multiplicities:

Lemma 5.0.6. µ(N (I)) = μ, µ(O(I)) ≤ µ • μ and µ(J ) ≤ (µ • μ)! ≤ (µ • M (d, n))! .
5.0.7. A bound for the number of maximal contacts and the relevant neighborhoods. We will construct maximal contacts along with the open neighborhoods for which they are defined. Each maximal contact u ∈ Der C n ,X μ-1 (N (I)) that we consider is of the form u = D μ-1 (g i ), where D μ-1 = D a1 1 . . . D an n is a certain composition of μ -1 differential operators (7) (i.e., the D i are of the form in [START_REF] Bierstone | Semianalytic and subanalytic sets[END_REF], and a 1 + . . . + a n = μ -1). Consider all differential operators {D μ r } r∈R , which are certain compositions of μ differential operators [START_REF] Bierstone | Semianalytic and subanalytic sets[END_REF], and take all the corresponding functions f r,i := D μ r (g i ). On the open set U r,i = U \ V (f r,i ), consider the maximal contact u r,i = D μ-1 (g i ), where D μ-1 = D a1 1 . . . D an n is a certain composition of μ -1 differential operators [START_REF] Bierstone | Semianalytic and subanalytic sets[END_REF] as in the Step 1b can be described by the function

∆ 1 (r, m, d, n, l, q, µ) := (r, m -1, A(d, n, µ), n, F (d, n, µ, l), q • l • C(d, n, µ), (µ • M (d, n))!) .
Note that the restriction to the maximal contact does not affect the degree since the function B(d, n, µ) measuring the degree of maximal contact is smaller than A(d, n, µ).

Remark. The particular form of the bounds obtained does not strongly influence Theorem 6.4.2; we need only that the functions belong to the class E 3 . (See the beginning of the next section.) 6. Complexity bound of the resolution algorithm in terms of Grzegorczyk's classes 6.1. Language of Grzegorczyk's classes. The complexity estimate of the desingularization algorithm which we provide in this section is given in terms of Grzegorczyk's classes E l , l ≥ 0 of primitive-recursive functions [START_REF] Grzegorczyk | Some classes of recursive functions[END_REF], [START_REF] Wagner | Computational Complexity[END_REF]. To make the paper self-contained, we provide a definition of E l by induction on l (informally speaking, E l consists of integer functions Z s → Z t whose construction requires l nested primitive recursions).

For the base definition, E 0 contains constant functions x k → c, functions x k → x k + c and projections (x 1 , . . . , x n ) → x k for any variables x 1 , . . . , x n .

The class E 1 contains linear functions

x k → c • x k and (x k1 , x k2 ) → x k1 + x k2 .
The class E 2 contains all polynomials with integer coefficients Let l ≥ 2. For the inductive step of the definition, assume that functions G(x 1 , . . . , x n ), H(x 1 , . . . , x n , y, z) ∈ E l . Then the function F (x 1 , . . . , x n , y) defined by the primitive recursion,

F (x 1 , . . . , x n , 0) = G(x 1 , . . . , x n ), (8)
F (x 1 , . . . , x n , y + 1) = H(x 1 , . . . , x n , y, F (x 1 , . . . , x n , y)), [START_REF] Bierstone | A simple constructive proof of canonical resolution of singularities[END_REF] belongs to E l+1 .

To complete the definition of E l , l ≥ 0, take the closure with respect to composition and the following limited primitive recursion:

Let G(x 1 , . . . , x n ), H(x 1 , . . . , x n , y, z), Q(x 1 , . . . , x n , y) ∈ E l . Then the function F (x 1 , . . . , x n , y) defined by ( 8),( 9) also belongs to E l , provided that F (x 1 , . . . , x n , y) ≤ Q(x 1 , . . . , x n , y).

Clearly, E l+1 ⊃ E l .

Observe that E 3 contains all towers of exponential functions and E 4 contains all tetration functions [START_REF] Grzegorczyk | Some classes of recursive functions[END_REF], [START_REF] Wagner | Computational Complexity[END_REF].

The union ∪ l<∞ E l coincides with the set of all primitive-recursive functions.

6.2. Resolution algorithm as a graph. It is instructive to represent the resolution algorithm in the form of a tree T as in the following Figure. Each node a of T corresponds to an intermediate object T a = ({X α,β , I α,β , E α,β , U α,β } α,β , n, µ). Each node a is labeled either by 1 or 2 depending on whether it corresponds to step 1 or 2 in the description of the algorithm (see the previous sections). An edge from a node labeled by 1 leads to its child node labeled by 2 and the edge is labeled in its turn either by 2a or by 2b depending on the step to which it corresponds. Similarly, an edge from a node labeled by 2 leads to its child node labeled by 1 and is labeled in turn either by 1a or by 1b. In the Figure a child node is always located to the right from a node.

The algorithm yields T by recursion starting with its root. Assume that a and T a are already constructed. The next task of the algorithm is to resolve the object T a . To this end the algorithm first constructs the child nodes a 1 , . . . , a t of a according to the algorithm. The order of producing a 1 , . . . , a t goes from up to down in the Figure . The algorithm resolves the objects T a1 , . . . , T at-1 by recursion on 0 ≤ t ≤ t and in the process modifies T a := T a (0), obtaining the current object T a (t -1). Then the algorithm yields a t , T at , resolves T at and collects all the blow ups produced while resolving T at and applies them (with the same centers) to the current object T a (t -1); the resulting object we denote by T a (t). This allows the algorithm to yield a child node a t+1 and T at+1 following the description from the previous sections.

For the leaves of T there are two possibilities: either a leaf is labeled by 2 or a certain node a labeled by 2 could have a single edge (the lowest in the Figure among the edges originating at a) labeled by 2b which leads to a child node of a being a leaf corresponding to the monomial case (labeled by M ). Note also that if a is labeled by 1 then the top few edges originating at a are labeled by 1a and the remaining bottom ones are labeled by 1b (in the order from up to down in the Figure ).

Observe that the dimension of the varieties X α,β corresponding to a drops while passing to any of its child nodes when a is labeled by 1, and the dimension does not increase when a is labeled by 2. Therefore, the depth of T does not exceed 2m. 6.3. Main recursive functions. Now we proceed to the bounds of some recursive functions related to the ingredients of T . Set γ := (r, m, d, n, l, q, µ) ∈ Z 7 ≥0 . Let T * be the canonical resolution of T . For simpilicity of notation, we introduce the following function defined on Z 7 ≥0 : Γ

(m) (γ) := (r + R (m) (γ), m, D (m) (γ), N (m) (γ), L (m) (γ), Q (m) (γ), µ) ,
where the subscript r can be interpreted as the subscript in the resolution of T , and

(1) R (m) (γ) is the number of blow-ups needed to resolve the initial marked ideal with data bounded by (m, d, n, l, q, µ); (2) D (m) (γ) is a function bounding the maximum of the degrees of all the polynomials which represent T * and all objects constructed along the way (in particular, the centers); (3) N (m) (γ) is a bound for the dimensions of the ambient affine spaces constructed along the way; (4) L (m) (γ) is a bound for the number of polynomials appearing in the description of a single neighborhood U α,β on resolving T ; (5) Q (m) (γ) is the number of neighborhoods in all the auxiliary objects (in particular, the centers) appearing on resolving T .

Remark. The functions R (m) (γ), D (m) (γ), N (m) (γ) do not depend on l, q.

6.3.1. Algorithm revisited. Let (I, µ) be a marked ideal on an m-dimensional smooth variety X. Consider the corresponding object

T (m) = ({X α,β , I α,β , E α,β , U α,β , C n α | α ∈ A, β ∈ B}, µ) with the initial data γ := (0, m, d, n, l, q, µ).
Our next goal is two-fold. We will give recursive formulas for Γ (m) , R (m) , D (m) , N (m) , L (m) , Q (m) and prove by induction on m these functions belong to Grzegorczyk's class E m+3 . In the base of the induction (i.e., for m = 0), the functions

R (0) = 1, D (0) = O(dn), N (0) ≤ 2n, L (0) ≤ l • (dn) O(n) , Q (0) ≤ nq
belong to the class E 3 , as does Γ (0) . Now we proceed to the inductive step. Assume that Γ (m-1) , R (m-1) , D (m-1) , N (m-1) , L (m-1) , Q (m-1) belong to Grzegorczyk's class E m+2 , where m ≥ 1.

If I = 0, then the resolution is done by the single blow-up at the center C = X and the object T (m) is transformed into an object T (m) 1

with X 1 = ∅ and data bounded by Bl(γ) ∈ E 3 (see Lemma 4.3.1). If I = 0, then the resolution algorithm can be represented by the following scheme.

Step 2. Resolve (I, µ) on the m-dimensional smooth variety X. Consider the corresponding object T (m) with initial data γ := (0, m, d, n, l, q, µ). Let μ denote the maximal order of N (I) on X. We have the following estimate for μ:

μ ≤ M (d, n) ∈ E 3 (cf Lemma 5.0.2).
Step 2a. In this Step we are going to decrease the maximal order of the nonmonomial part N (I) by resolving the companion ideal O(I, µ). In fact we perform an additional modification of O(I) and construct the ideal J := C(H(O(I))). This corresponds to the new object T will be then resolved and its resolution will cause the maximal order to decrease. The resolution T (m) 1 is done by performing Step 1.

Step 1. In this step we resolve J , i.e., T (m) 1

. The Step splits into two Steps (1a) and (1b).

Step 1a. Move apart all unions of the intersections H s α ⊂ C n α of s divisors in E, where s is the maximal number of divisors in E through points in supp J = supp(J , µ(J )). For any α, resolve all J |H s α . We construct a new object

T (s) 2 := ({H s α,β , J α,β , E α,β , U α,β , C n α | α ∈ A, β ∈ B}, µ(J )), with initial data bounded by γ (1a) := ∆ 1 (γ) ∈ E 3
with s ≤ m -1 (see Lemma 5.0.13).

By the inductive assumption, the resolution of T (s) 2 , i.e., the sequence T (s) 2 * of the induced intermediate objects determined by the blow-ups, requires at most R (m-1) (γ (1) ) blow ups. The maximal degree of the polynomials of the centers and the objects T (s) 2 * describing the resolution does not exceed D (m-1) (γ (1) ). The dimension n of the objects does not exceed N (m-1) (γ (1) ).

Note that the resolution of T consisting of R (m-1) (γ (1) ) blow-ups. We have a direct correspondence between objects T Step 1b. If the strict transforms of E do not intersect supp J , we resolve J , i.e., the object T (m) 1

. This is achieved by resolving J |V (u) (by induction), where V (u) is a hypersurface of maximal contact. After completing Step 1a, the bound γ (1a) is transformed to

γ (1b) := Γ (m) 1b (γ) = (r (1b) , m, d (1b) , n (1b) , l (1b) , q (1b) , (µ • (M (d, n)))!) (cf. Lemma 5.0.6).
Passing from J to J |V (u) , we adjoin the equations of maximal contact as well as create new neighborhoods. This operation has been reflected in the construction of ∆ 1 (γ). By the construction of Γ (m) 1b (γ) and ∆ 1 (γ), the degree of the maximal contact does not exceed d (1b) , while the number of neighborhoods does not exceed q (1b) . In other words Γ (m) 1b (γ) bounds the initial data for J |V (u) . The resolution process for J |V (u) leads eventually to resolution of the object T 1a (γ, m + 1) = (r (1) , m, d (1) , n (1) , l (1) , q (1) , (µ • (M (d, n)))!), for the relevant r (1) , d (1) , n (1) , l (1) , q (1) . Hence the function Γ The object T (m) corresponding to I with initial data γ is transformed to the new object with the data bounded by Γ (m) 2a (γ) := (r (1) , m, d (1) , n (1) , l (1) , q (1) , μ) with smaller μ -the maximal order of the new N (I). (Note that μ < M (d, n)).

This completes Step 2a. This Step 2a is then repeated at most M (d, n) times until the maximal order drops to zero when we arrived at the monomial case. The final effect of Step 2a is measured then by the recursive function Γ Step 2b. Resolve the monomial marked ideal I = M(I). The marked ideal corresponds to the object T (m) with data (r (2b) , m, d (2b) , n (2b) , l (2b) , q (2b) , µ) =: Γ We summarize the bounds achieved in the following Corollary (recall that the notation can be found in subsection 4.1.1). Corollary 6.3.1. When resolving a marked ideal (X, I, E, µ) on X ⊂ C n by the Hironaka algorithm, the degree d, the number l of the polynomials occurring, the embedding dimension n, the number r of the blow-ups and the number q of the affine neighborhoods satisfy, for fixed m = dim X, the recursive equalities above, and are majorized by a function (r, m, d, n, l, q, µ) := Γ (m) (0, m, d 0 , n 0 , l 0 , q 0 , µ) ∈ E m+3 , for the initial values d = d 0 , n = n 0 , l = l 0 , q = q 0 . 6.4. Complexity of the algorithm. The principal complexity result of the paper is the following assertion. Theorem 6.4.1. When resolving a marked ideal (X, I, E, µ) on X ⊂ C n by the Hironaka algorithm, its complexity can be bounded, for fixed m = dim X, by b O (1) • F (m) (d 0 , n 0 , l 0 , q 0 , µ), for a certain function F (m) (d 0 , n 0 , l 0 , q 0 , µ) ∈ E m+3 .

Proof. Indeed, each step of the algorithm consists of solving a certain subroutine (basically, solving a linear system) over the coefficients of the current polynomials. Therefore, Corollary 6.3.1 provides a bound on the number of arithmetic operations with the coefficients of the current polynomials (providing a function from class E m+3 ). On the other hand, all the coefficients of the polynomials for the next step are obtained as results of these arithmetic operations, so the bit sizes of the coefficients and the complexity grow by at most b • F (m) , for a function F (m) = G(Γ (m) (0, m, d 0 , n 0 , l 0 , q 0 , µ)) ∈ E m+3 with a suitable function G ∈ E 3 . The cost of a single arithmetic operation is obviously polynomial.

As a corollary we obtain the following theorem.

Theorem 6.4.2. When either

(1) resolving singularities of X ⊂ C n0 , or (2) principalizing an ideal sheaf I on a nonsingular X ⊂ C n0 , by the Hironaka algorithm, the degree d, the number l of the polynomials occurring, the embedding dimension n, the number r of the blow-ups, and the number q of the affine neighborhoods satisfy, for fixed m = dim X, the recursive equalities above and are majorized by a function (r, m, d, n, l, q, 1) := Γ (m) (0, m, d 0 , n 0 , l 0 , q 0 , 1) ∈ E m+3 , for the initial values d = d 0 , n = n 0 , l = l 0 , q = q 0 . The complexity of the algorithm is bounded by b O (1) • F (m) (d 0 , n 0 , l 0 , q 0 , µ), for a certain function F (m) (d 0 , n 0 , l 0 , q 0 , µ) ∈ E m+3 .

Remark. In the proof above, we gave a more explicit form of F (m) providing additional information on its dependance on r, d, n, l, q, µ. But the main consequence of the Theorem is that m = dim X provides the most significant contribution to the complexity bound.

7. Appendix. Applications to positive characteristic.

Define D(m, d 0 , n 0 , l 0 , q 0 , µ) , and N (m, d 0 , n 0 , l 0 , q 0 , µ) to be the d-and n-coordinates of Γ (m) (0, m, d 0 , n 0 , l 0 , q 0 , µ) (in future considerations we drop subscripts in the above presentations).

Observe that we can count maximal order of all occuring ideals in single neighborhoods representing our data that is: marked ideal (X, I, E, µ) embedded into the affine space A This gives us some rough control of the algorithm in characteristic p.

We can define M (X, I, E, µ, A n ) := M (m, d, n, l, µ), where (X, I, E, µ) is a marked ideal described in some open subset U of A n by l polynomials of degree less than n.

Set M (X, I, E, µ, x) to be the minimum of M (X ′ , I ′ , E ′ , µ, A n ′ ), over all the affine neighborhoods X ′ ⊂ X of x, embedded into possible affine spaces A n ′ . Note that X ′ is locally closed and can be always shrinked so the data depend only on the stalk of the marked ideal I at x ∈ X. Similarly M (X, I, E, µ, x) is the minimum of all the M (X ′ , I ′ , E ′ , µ, x ′ ), for which there exists (X ′′ , I ′′ , E ′′ , µ, x ′′ ) with étale morphisms (X ′′ , I ′′ , E ′′ , x ′′ ) → (X, I, E, x) and (X ′′ , I ′′ , E ′′ , x ′′ ) → (X ′ , I ′ , E ′ , x ′ ).

Note that the function M (X, I, E, µ, x) is defined in any characteristic. Moreover Lemma 7.0.3. The function M (X, I, E, µ, x) has the following properties

(1) If X ⊂ A n is a locally closed set of A n described in some open subset U of A n by l polynomials of degree less than n, and x ∈ U then M (X, I, x) ≤ M (d, n, l) (2) If (X ′ , I ′ , E ′ , x ′ ) → (X, I, E, x) is étale then M (X, I, E, µ, x) = M (X ′ , I ′ , E ′ , µ, x ′ ). is well defined (4) Consider the canonical Hironaka resolution of (X, I, E, µ). The multiplicities of occuring marked ideals do not exceed M (X, I, E, µ).

Proof. Follows from definition. We use here also canonicity of Hironaka resolution an the fact that étale morphisms preserve multiplicities.

This implies the following Theorem 7.0.4. There exists the canonical Hironaka resolution of marked ideals for which M (X, I, E, µ) < p.

( 3 )

 3 has only simple normal crossings and C i has simple normal crossings with E i . (b) Let Y i ⊂ X i be the strict transform of Y . All centers C i are disjoint from the set Reg(Y ) ⊂ Y i of points where Y (not Y i ) is smooth (and are not necessarily contained in Y i ). (c) The strict transform Y := Y r of Y is smooth and has only simple normal crossings with the exceptional divisor E r . (d) The morphism (X, Y ) ← ( X, Y ) defined by the embedded desingularization commutes with smooth morphisms and embeddings of ambient varieties. It is equivariant with respect to any group action, not necessarily preserving the ground K. Canonical Resolution of Singularities. Theorem 1.0.3. Let Y be an algebraic variety over a field of characteristic zero. Then there exists a canonical desingularization of Y ; that is, a smooth variety Y together with a proper birational morphism res Y : Y → Y such that: (a) res Y : Y → Y is an isomorphism over the nonsingular part of Y . (b) The inverse image res -1 Y (Y sing ) of the singular locus of Y is a simple normal crossings divisor. (c) The morphism res Y is functorial with respect to smooth morphisms. For any smooth morphism φ : Y ′ → Y there is a natural lifting φ : Y ′ → Y which is a smooth morphism. (d) res Y is equivariant with respect to any group action, not necessarily preserving the ground field.

∂

  |α| fj ∂u α for all multiindices α = (α 1 , . . . , α n ), where |α| := α 1 + . . . + α n ≤ i. Lemma 2.5.2. (Giraud, Villamayor) For any i ≤ µ -1, supp(I, µ) = supp(D i (I), µi).

Lemma 2 . 8 . 1 .

 281 Let (I, µ) be a marked ideal of maximal order. Then (1) (I, µ) ≃ (H(I), µ) (see Definition 2.4.1).

  3, supp(I, µ) ∩ S = supp(C(I, µ)) ∩ S ⊆ supp(C(I, µ) |S ). Let x 1 , . . . , x k , y 1 , . . . , y n-k be local parameters at x such that {x 1 = 0, . . . , x k = 0} describes S. Then any function f ∈ I can be written as f = c αf (y)x α , where c αf (y) are formal power series in y i . Now x ∈ supp(I, µ) ∩ S iff ord x (c α ) ≥ µ -|α| for all f ∈ I and |α| ≤ µ. Note that c αf |S = 1 α! ∂ |α| (f ) ∂x α |S ∈ D |α| (I) |S and consequently supp(I, µ) ∩ S = f ∈I,|α|≤µ supp(c αf |S , µ -|α|) ⊃ supp(C(I, µ) |S ).

  ord N (I) := max{ord x (N (I)) | x ∈ supp(I, µ)}. Definition 3.0.7. (Hironaka, Bierstone-Milman,Villamayor, Encinas-Hauser) By the companion ideal of (I, µ) where I = N (I)M(I) we mean the marked ideal of maximal order O(I, µ) = (N (I), ord N (I) ) + (M(I), µord N (I) ) if ord N (I) < µ, (N (I), ord N (I) ) if ord N (I) ≥ µ.

⇓ 1 .

 1 If I = M(I), decrease the maximal order of the nonmonomial part N (I) by resolving the companion ideal O(I) = O(I, µ).Step Resolve the companion ideal O(I):Replace O(I) with J := C(H(O(I))) ≃ O(I). (*)

  Remarks. (1) (*) The ideal O(I) is replaced with H(O(I)) to ensure that the algorithm constructed in Step 1b is independent of the choice of the tangent direction u. We replace H(O(I)) with C(H(O(I))) to ensure the equalities supp(J |S ) = supp(J ) ∩ S, where S = H s α in Step 1a and S = V (u) in Step 1b.

Definition 4 . 1 . 1 .

 411 By the support of T we mean the collection of the sets supp(T ) := {supp(X α,β ∩ U α,β , I α,β , E α,β ∩ U α,β ∩ X α,β , µ)} α∈A,β∈B Definition 4.1.2. Given an affine marked ideal T := ({X α,β , I α,β , E α,β , U α,β , (C nα ) α | α ∈ A, β ∈ B α }, µ), we say that an affine marked ideal T

  is a local resolution of Y . The resolution space Ỹ is described by an open cover { Ỹα ′ ,β ′′ , π α ′ ,β ′′ } α ′ ,β ′′ . The sets Ỹα ′ ,β ′′ are represented as closed subsets of the open subsets U α ′ ,β ′′ ⊂ C n α ′ .

  µ) the resulting affine marked ideal obtained from T by the blow-up with the center C. Below we describe more precisely the ingredients of T ′ .

  obtained from D μ r = D b1 1 . . . D bn n by replacing one of the positive b i with b i -1 (i.e a i := b i -1 for some b i > 0 and a j = b j for j = i.) Lemma 5.0.12. The number of the maximal contacts u r,i ∈ Der C n ,X μ-1 (N (I)) and at the same time the number of neighborhoods U i,r ⊂ U can be bounded by C(d, n, µ) • l(I), where l(I) is the number of generators of I, and C(d, n, µ) := M (d, n) + n n . Proof. The number of the maximal contacts is bounded by μ+n n •l(I) ≤ C(d, n, µ)•l(I), whereC(d, n, µ) := M (d,n)+n n . Summarizing: Lemma 5.0.13. The effect of passing from I to J = C(H(O(I))) and then to J |Hs in Step 1a or to J |V (u)

  Figure 1.

  data γ (2a) := ∆ 2a (γ) ∈ E 3 , (see Lemma 5.0.11). The object T (m) 1

2 *

 2 . The bound Γ (m-1) (∆ 1 (γ)) ∈ E m+2 , for the data for the resolution T (s) 2 * , given by the induction, remains valid for the data for T (m) 1 *as we use the same centers, the same ambient affine spaces, etc., for these multiple blow-ups. Only the strict transforms of the current X are different, and this does not affect the bounds for the data. We have additional equations to describe the current X in T Since the Step 1a is performed at most m times, its final effect after completing Step 1a and passing to Step 1b is measured by the function Γ , m) . Note that for any fixed value of t = t 0 (in particular, for t = m) the functions Γ (m) 1a (γ, t 0 ), belong to the class E m+2 due to the inductive hypothesis and Lemma 4.3.1, Corollary 5.0.10. Therefore, Γ (m) 1b belongs to the class E m+2 . (We use here the property that Grzegorczyk classes are closed under composition.) After performing Step 1a, we have moved apart all strict transforms of E and supp J = supp(J , µ(J )).

  ) := Γ (m-1) (Γ

(m) 1

 1 belongs to class E m+2 by the inductive hypothesis and Lemma 4.3.1, Corollary 5.0.10. This completes Step 1.

  belongs to class E m+3 , by the definition of Grzegorczyk classes (see (8),(9)), and by Lemmas 4.3.1, 5.0.2. Putting t = M (d, n) gives the final effect after completing all necessary Steps 2a and subsequently passing to Step 2b: Γ , M (d, n)); thereby, the function Γ (m) 2b belongs to class E m+3 as well. The procedure eventually reduces (I, µ) to the monomial marked ideal I = M(I).

  The resolution of I = (x α ) consists of blow-ups each of which decreases the multiplicity |x α | ≤ d(2b) . The resolution of I requires at most d (2b) blow-ups. Thus the final solution data can be bounded by the functionΓ (m) (γ) := Bl(Γ (m) 2b (γ), d (2b) ) ∈ E m+3 .

  n = C n . It follows from Lemma 5.0.2 that this order does not exceed M ( D, N ) = M (m, d, n, l, µ), where D(m, d, n, l, µ) := D(n, d, n, l, 1, 1, 1, µ) and N (m, d, n, l, µ) := N (n, d, n, l, 1, 1, 1, µ) are functions in (m, d, n, l, µ). By the construction all the functions above are in E n+3 .

( 3 )

 3 The function M (X, I, E, µ) := max x∈X { M (X, I, E, µ, x)}

(s) 2 * , as compared to those in T (m) 1 * .Step 1a is performed at most s ≤ m times. Introduce the auxillary unknown t = 0, 1, . . . , m, and the function Γ (m) 1a (γ, t) which measures the possible effect after performing Step 1a t times:Γ (m) 1a (γ, 0) := ∆ 1 (γ) ∈ E 3 , Γ (m) 1a (γ, t + 1) := Γ (m-1) (Γ (m)1a (γ, t)).

s and Milman's research was partially supported by NSERC Discovery Grants OGP 0009070 and OGP 008949. W lodarczyk was supported in part by NSF grants DMS-0100598 and DMS-1201502.

As a Corollary, we obtain: Lemma 5.0.7. The maximal degree of generators of J := C(H(O(I))) is bounded by

Proof. This follows from Lemma 5.0.5. 5.0.5. Restriction to hypersurfaces of maximal contact, and to exceptional divisors. In step 1, we restrict I to intersections of the exceptional divisors and maximal contact.

We need to estimate a bound B(d, n, µ) for the degree of the maximal contact u ∈ Der C n ,X μ-1 (N (I)).

The following is an immediate consequence of Lemma 5.0.5:

Lemma 5.0.8. The maximal degree of any maximal contact u ∈ Der C n ,X μ-1 (N (I)) is bounded by

5.0.6. A bound for the number of generators of J. First, we state the basic properties concerning the number of generators of the ideal in the following lemma:

Lemma 5.0.9.

(1) The number of generators of Der C n ,X (I) is given by (n + 1)l(I). (2) The number of generators of Der C n ,X i (I) is given (n + 1) i l(I).

( Proof. Immediate from the definitions.

By the preceding lemma, we get

Thus we get:

Corollary 5.0.10. l(J ) ≤ F (d, n, µ), where

Remark. The algorithm of [START_REF] Bierstone | Functoriality in resolution of singularities[END_REF] does not involve the homogenization step and therefore gives better estimates for the elementary functions introduced. In particular:

( Proof. The algorithm is the same as in characteristic zero. We just need minor modifications of the basic results. We replace the hypothesis of characteristic zero with the one that the multiplicity µ in the relevant marked ideals is less than characteristic p in Lemmas 2.5.2, 2.6.2, 2.6.3, 2.6.4, 2.8.2, 2.8.3, 2.9.4 with unchanged proof. Theorem 6.4.2 is replaced with the following.

Theorem 7.0.5. Assume characteristic of base field is p. For any marked ideal (X, I, E, µ) such that M (X, I, E, µ) < p there is an associated resolution (X i ) 0≤i≤mX , called canonical, satisfying the following conditions:

(1) For any surjective étale morphism φ :

(2) For any étale morphism φ :

Proof. The proof is the same as before. We apply the same algorithm as in characteristic zero. The multiplicities of occuring maked ideals do not exceed M (X, I, E, µ) < p. Indeed it suffices to verify this for a marked ideal in a neighborhood of some point x ∈ X. We can find a marked ideal (X ′ , I ′ , E ′ , µ) which is étale equivalent with (X, I, E, µ) at a neighborhood of x ∈ X, and such that M (X ′ , I, E ′ , µ) = M (X ′ , I, E ′ , µ, x ′ ) = M (X, I, E, µ, x). The algorithm for (X ′ , I, E ′ , µ, x ′ ) is identical as in characteristic zero since we won't create marked ideals of the multiplicities greater than p. The algorithm for (X, I, E, µ, x) by the above modified basic results will create marked ideals with the same multiplicities.

Remark. Note that the resolution is canonical and it is G-equivariant with respect to the action of any group G. Thus existence of resolution over algebraically closed field implies the resolution over any perfect field K. The reasoning is the same as in characteristic zero. Consider the action of the Galois group G := Gal(K/K). By the above all the centers are G-stable so they are defined over K = K G . (see, for instance [START_REF] Lodarczyk | Simple Hironaka resolution in characteristic zero[END_REF] for details.)

Corollary 7.0.6. Assume base field is perfect of charcteristic p. There exists a function M (d, n, l) := M (n, d, n, l, 1) ∈ E n+3 (independent of characteristic) such that for all X ⊂ A n described by l polynomials of degree less than n, for which M (d, n, l) < p there is a canonical resolution of singularities.

Corollary 7.0.7. There is a canonical principlization of ideals I in A n described by l polynomials of degree less than n, for which M (d, n, l) < p.