Newton polygons of higher order in algebraic number theory

NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY JORDI GU` ARDIA, JES´ US MONTES, AND ENRIC NART Abstract. We develop a theory of arithmetic Newton polygons of higher order, that provides the factorization of a separable polynomial over a p-adic field, together with relevant arithmetic information about the fields generated by the irreducible factors. This carries out a program suggested by Ø. Ore. As an application, we obtain fast algorithms to compute discriminants, prime ideal decomposition and integral bases of number fields. Introduction R. Dedekind based the foundations of algebraic number theory on ideal theory, because the constructive attempts to find a rigorous general definition of the ideal numbers introduced by E. Kummer failed. This failure is due to the existence of inessential discriminant divisors; that is, there are number fields Kand prime numbers p, such that pdivides the index, ind(θ) := (ZK:Z[θ]), for any integral generator θof K, where ZKis the ring of integers. Dedekind gave a criterion to detect when p-ind(θ), and a procedure to construct the prime ideals of Kdividing pin that case, in terms of the factorization of the minimal polynomial of θmodulo p[Ded78]. M. Bauer introduced an arithmetic version of Newton polygons to construct prime ideals in cases where Dedekind’s criterion failed [Bau07]. This theory was developed and extended by Ø. Ore in his 1923 thesis, and a series of papers that followed [Ore23, Ore24, Ore25, Ore26, Ore28]. Let f(x)∈Z[x] be an irreducible polynomial that generates K. After K. Hensel’s work, the prime ideals of Klying above pare in bijection with the irreducible factors of f(x) over Zp[x]. Ore’s work determines three successive factorizations of f(x) in Zp[x], known as the three classical dissections (cf. [Ber27], [Coh95]). The first dissection is determined by Hensel’s lemma: f(x) splits into the product of factors that are congruent to the power of an irreducible polynomial modulo p. The second dissection is a further splitting of each factor, according to the number of sides of certain Newton polygon. The third dissection is a further splitting of each of the late factors, according to the factorization of certain residual polynomial attached to each side of a polygon, which is a polynomial with coefficients in a finite field. Unfortunately, the factors of f(x) obtained after these three dissections are not always irreducible. Ore defined a polynomial to be p-regular when it satisfies a technical condition that ensures that the factorization of f(x) is complete after the three dissections. Also, he proved the existence of a p-regular defining equation for every number field, but the proof is not constructive: it uses the Chinese remainder theorem with respect to the different prime ideals that one wants to construct. Ore Partially supported by MTM2006-15038-C02-02 and MTM2006-11391 from the Spanish MEC. 1 2 GU` ARDIA, MONTES, AND NART himself suggested that it should be possible to introduce Newton polygons of higher order that continue the factorization process till all irreducible factors of f(x) are achieved [Ore23, Ch.4,§8], [Ore28, §5]. Ore’s program was carried out by the second author in his 1999 thesis [Mon99], under the supervision of the third author. For any natural number r≥1, Newton polygons of order rwere constructed, the case r= 1 corresponding to the Newton polygons introduced by Ore. Also, analogous to Ore’s theorems were proved for polygons of order r, providing two more dissections of the factors of f(x), for each order r. The whole process is controled by an invariant defined in terms of higher order indices, that ensures that the process finishes at most in ind(f) := vp(ind(θ)) steps, where θis a root of f(x). Once an irreducible factor of f(x) is detected, the theory determines the ramification index and residual degree of the p-adic field generated by this factor, in terms of combinatorial data attached to the sides of the higher order polygons and the residual polynomials of higher order attached to each side. The process yields a computation of ind(f) as a by-product. An implementation in Mathematica of this factorization algorithm was worked out by the first author [Gua97]. We present these results for the first time in the form of a publication, after a thorough revision and some simplifications. In section 1 we review Ore’s results, with proofs, which otherwise can be found only in the original papers by Ore in the language of “h¨ohere Kongruenzen”. In section 2 we develop the theory of Newton polygons of higher order, based in the concept of a type and its representative, which plays the analogous role in order rto that played by an irreducible polynomial modulo pin order one. In section 3 we prove analogous in order rto Ore’s Theorems of the polygon and of the residual polynomial (Theorems 3.1 and 3.7), that provide two more dissections for each order. In section 4 we introduce resultants and indices of higher order and we prove the Theorem of the index (Theorem 4.18), that relates ind(f) with the higher order indices constructed from the higher order polygons. This result guarantees that the factorization process ends after a finite number of steps. Although the higher order Newton polygons are apparently involved and highly technical objects, they provide fast factorization algorithms, because all computations are mainly based on two reasonably fast operations: division with remainder of monic polynomials with integer coefficients, and factorization of polynomials over finite fields. Thus, from a modern perspective, the main application of these results is the design of fast algorithms to compute discriminants, prime ideal decomposition and integral bases of number fields. However, we present in this paper only the theoretical background of higher order Newton polygons. We shall describe the concrete design of the algorithms and discuss the relevant computational aspects elsewhere [GMN08a, GMN08b]. 1. Newton polygons of the first order 1.1. Abstract polygons. Let λ∈Q−be a negative rational number, expressed in lower terms as λ=−h/e, with h, e positive coprime integers. We denote by S(λ) the set of segments of the Euclidian plane with slope λand end points having nonnegative integer coordinates. The points of (Z≥0)2are also considered to be segments in S(λ), whose initial and final points coincide. The elements of S(λ) will be called sides of slope λ. For any side S∈ S(λ), we define its length,`:= `(S), NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 3 and height,H:= H(S), to be the length of the respective projections of Sto the horizontal and vertical axis. We define the degree of Sto be d:= d(S) := `(S)/e =H(S)/h. Note that any side Sof positive length is divided into dsegments by the points of integer coordinates that lie on S. A side S∈ S(λ) is determined by the initial point (s, u) and the length `, or equivalently, by the initial point and the degree d. The final point is (s+`, u −H) = (s+de, u −dh). For instance, the next figure represents a side of slope −1/2, initial point (s, u), and degree three. • • • • HHHHHHHH H HHHHHHHH H s u u−H s+` S h e The set S(λ) has the structure of an abelian semigroup with the following addition rule: given S, T ∈ S(λ), the sum S+Tis the side of length `(S) + `(T) of S(λ), whose initial point is the sum of the initial points of Sand T. Thus, the addition is geometrically represented by the process of joining the two segments and choosing an apropriate initial point. The addition of a segment Swith a point Pis represented by the translation P+Sof Sby the vector represented by P. The neutral element is the point (0,0). The invariants `(S), H(S), d(S) determine semigroup homomorphisms `, H, d :S(λ)−→ Z≥0. For technical reasons we consider also a set of sides of slope −∞, which is formally defined as S(−∞) := Z>0×(Z≥0)2. If S= (`, (s, u)) is a side of slope minus infinity, we define `(S) := `,H(S) := ∞,d(S) := 1. Also, we take by convention h=∞, e=`. This set has an obvious structure of an abelian monoid, and the length determines a monoid homomorphism, `:S(−∞)−→ Z>0. There is a geometric representation of such an Sas a side whose end points are (s, ∞) and (s+`, u). • 6 s+`s u The set of sides of negative slope is defined as the formal disjoint union S:= S(−∞)a [ λ∈Q− S(λ) . Note that the points of (Z≥0)2belong formally to S(λ) for all finite λ, so that it is not possible (even in a formal sense) to attach a slope to them. 4 GU` ARDIA, MONTES, AND NART We have a natural geometric representation of a side. Let us introduce a geometric representation of a formal sum of sides as an open convex polygon of the plane. Let N=S1+· · · +Stbe a formal sum of sides of negative slope. Let S∞= (`∞, P∞) be the sum of all sides of slope −∞ among the Si. Take P0to be the sum of all initial points of the Sithat don’t belong to S(−∞) (the empty sum is considered to be P0= (0,0)). Let P=P∞+ (`∞,0) + P0. Then, Nis represented as the polygon that starts at Pand is obtained by joining all sides of positive length and finite slope, ordered by increasing slopes. If i1is the abscissa of P, we have to think that the polygon starts at the abscisa i0=i1−`∞, that formally indicates the starting point (at infinity) of a side of slope −∞. The typical shape of this polygon is • • • • Q Q Q Q Q A A A Q Q Q Q Q A A A P P PP P P P P - `∞ P i0i1i0+`(N) Definition 1.1. The semigroup PP of principal polygons is defined to be the set of all these geometric configurations. By definition, every principal polygon represents a formal sum, N=S1+· · ·+St, of sides Si∈ S. This expression is unique in any of the two following situations (1) N=S, with S∈(Z≥0)2, (2) N=S1+· · · +St, with all Siof positive length and pairwise different slopes. It is clear that any N∈ PP can be expressed in one (and only one) of these canonical forms. Usually, when we speak of the sides of a principal polygon, we mean the sides of this canonical expression. If we need to emphasize this we shall use the term canonical sides of N. The finite end points of the canonical sides are called the vertices of the polygon. The addition of polygons is defined in terms of the expression as a formal sum of sides (not necessarily the canonical ones). That is, if N=S1+· · · +Srand N0= S0 1+· · ·+S0 s, then N+N0is the geometric representation of S1+· · ·+Sr+S0 1+· · ·+S0 s. The reader may check easily that this is well-defined and PP has a structure of semigroup with neutral element {(0,0)}. Also, it is clear that this addition is compatible with the sum operations that we had on all S(λ). Note that the addition of N∈ PP with (the polygon represented by) a point P∈(Z≥0)2is the translation P+N. The fact of adding to N(the polygon represented by) a side of slope −∞ is reflected by a horizontal shift of the finite part of N, without changing the starting abscissa i0of N. Definition 1.2. We define the length of a principal polygon N=S1+· · · +Srto be `(N) := `(S1) + · · · +`(Sr). Thus, the length determines a semigroup homomorphism, `:PP −→ Z≥0. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 5 Let N∈ PP. Let i0be the abscissa where the polygon starts and i1the abscissa of the point Pwhere the finite part of Nstarts. For any integer abscissa i0≤i≤ i0+`(N) we denote by hi=hi(N) = ∞,if i0≤i<i1, the ordinate of the point of Nof abscissa i, if i1≤i. For i≥i1these rational numbers form an strictly decreasing sequence. Definition 1.3. Let P= (i, y)be a “point” of the plane, with y∈R∪ {∞} and integer abscissa i0≤i≤i0+`(N). We say that Plies on Nif y=hi. We say that Plies above Nif y≥hi. We say that Plies strictly above Nif y > hi. For any i1< i ≤i0+`(N), let µibe the slope of the side of Nwhose projection to the horizontal axis contains i−1/2, or equivalently, the slope of the segment joining (i−1, hi−1) and (i, hi). The sequence µi1+1 ≤ · · · ≤ µi0+`(N)is an increasing sequence of negative rational numbers. We call these elements the unit slopes of N. Consider the multisets of unit slopes: Ui1(N) := ∅;Ui(N) := {µi1+1, . . . , µi},∀i1< i ≤i0+`(N). Clearly, hi(N) = hi1(N) + Pµ∈Ui(N)µ. Let N0be another principal polygon with starting abscissa j0and starting abscissa for the finite part j1. Consider analogous multisets Uj(N0), for all j1≤ j≤j0+`(N0). By the definition of the addition law of principal polygons, the multiset Uk(N+N0) contains the smallest k−i1−j1unit slopes of the multiset Ui0+`(N)(N)∪Uj0+`(N0)(N0) that contains all unit slopes of both polygons. Thus, hi(N) + hj(N0)≥hi+j(N+N0), and equality holds if and only if Ui(N)∪Uj(N0) = Ui+j(N+N0). Lemma 1.4. Let N, N0∈ PP. Let P= (i, u)be a point lying above the finite part of Nand P0= (j, u0)a point lying above the finite part of N0. Then P+P0lies above the finite part of N+N0and P+P0∈N+N0⇐⇒ P∈N, P0∈N0,and Ui(N)∪Uj(N0) = Ui+j(N+N0). Proof. Clearly, u+u0≥hi(N) + hj(N0)≥hi+j(N+N0) and P+P0∈N+N0if and only if both inequalities are equalities.  Definition 1.5. Let λ∈Q−and N∈ PP. Consider a line of slope λfar below N and let it move upwards till it touches Nfor the first time. Denote by Lλ(N)this line having first contact with N. We define the λ-component of Nto be Sλ(N) := N∩Lλ(N). We obtain in this way a map: Sλ:PP −→ S(λ). If Nhas a canonical side Sof positive length and finite slope λ, we have Sλ(N) = S, otherwise the λ-component Sλ(N) reduces to a point. • •@ @ @ @P P P P A A A A A A H H H H H H H H H H Lλ(N) S Sλ(N) = final point of S • •H H HH H H P P P P A A A A A A H H H H H H H H H H Lλ(N) S Sλ(N) = S 6 GU` ARDIA, MONTES, AND NART Lemma 1.4 shows that Sλis a semigroup homomorphism: (1) Sλ(N+N0) = Sλ(N) + Sλ(N0), for all N, N0∈ PP and all λ∈Q−. 1.2. φ-Newton polygon of a polynomial. Let pbe a prime number and let Qp be a fixed algebraic closure of the field Qpof the p-adic numbers. For any finite extension, Qp⊆L⊆Qp, of Qpwe denote by vLthe p-adic valuation, vL:Qp−→ Q∪{∞}, normalized by vL(L∗) = Z. Also, throughout the paper OLwill denote the ring of integers of L,mLits maximal ideal, and FLthe residue field. The canonical reduction map redL:OL−→ FLwill be usually indicated by a bar: α:= redL(α). We fix a finite extension Kof Qpas a base field, and we denote v:= vK, O:= OK,m:= mK,F:= FK,q:= |F|. We fix also a prime element π∈ O. We extend the valuation vto polynomials with coefficients in Oin a natural way: v:O[x]−→ Z≥0∪ {∞}, v(b0+· · · +brxr) := min{v(bj),0≤j≤r}. Let φ(x)∈ O[x] be a monic polynomial of degree mwhose reduction modulo mis irreducible. We denote by Fφthe finite field O[x]/(π, φ(x)), and by red: O[x]−→ Fφthe canonical homomorphism. We denote also by a bar the reduction of polynomials modulo m, ¯: O[x]−→ F[x]. Any f(x)∈ O[x] admits a unique φ-adic development: f(x) = a0(x) + a1(x)φ(x) + · · · +an(x)φ(x)n, with ai(x)∈ O[x], deg ai(x)< m. For any coefficient ai(x) we let ui:= v(ai(x)) ∈ Z∪ {∞} and we attach to ai(x) the point Pi= (i, ui), which is a point of the plane if uiis finite, and it is thought to be the point at infinity of the vertical line with abscissa i, if ui=∞. Definition 1.6. The φ-Newton polygon of a nonzero polynomial f(x)∈ O[x]is the lower convex envelope of the set of points Pi= (i, ui),ui<∞, in the cartesian plane. We denote this polygon by Nφ(f). The abscissa of the last vertex of Nφ(f) is n=bdeg(f)/mc, and deg f(x) = mn + deg an(x). The typical shape of this polygon is the following • • • •• • • Q Q Q Q Q A A A A A A Q Q Q Q Q A A A A A A •   bdeg(f)/mcordφ(¯ f)ordφ(f) v(f) 0 Remark 1.7. The φ-Newton polygon of f(x)is a side in S(−∞)of length `if and only if f(x) = a(x)φ(x)`, with deg(a)< m. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 7 Definition 1.8. The principal φ-polygon of f(x)is the element N− φ(f)∈ PP determined by the sides of negative slope of Nφ(f), including the side of slope −∞ represented by the length ordφ(f). It always starts at the abscissa i0= 0 and has length ordφ(¯ f). For any λ∈Q−we shall denote by Sλ(f) := Sλ(N− φ(f)) the λ-component of this polygon (cf. Definition 1.5) From now on, we denote N=N− φ(f) for simplicity. The principal polygon N and the set of points Pi= (i, ui) that lie on N, contain the arithmetic information we are interested in. Note that, by construction, the points Pilie all above N. We attach to any abscissa ordφ(f)≤i≤`(N) the following residual coefficient ci∈Fφ: ci=     0,if (i, ui) lies strictly above N, red ai(x) πui,if (i, ui) lies on N. Note that ciis always nonzero in the latter case, because deg ai(x)< m. Let λ=−h/e be a negative rational number, with h, e positive coprime integers. Let S=Sλ(N) be the λ-component of N, (s, u) the initial point of S, and d:= d(S) the degree of S. The points (i, ui) that lie on Scontain important arithmetic information that is kept in the form of two polynomials that are built with the coefficients of the φ-adic development of f(x) to whom these points are attached. Definition 1.9. We define the virtual factor of f(x)attached to S(or to λ) to be the polynomial fS(x) := π−uφ(x)−sf0(x)∈K[x],where f0(x) := X (i,ui)∈S ai(x)φ(x)i. We define the residual polynomial attached to S(or to λ) to be the polynomial: Rλ(f)(y) := cs+cs+ey+· · · +cs+(d−1)eyd−1+cs+de yd∈Fφ[y]. Note that only the points (i, ui) that lie on Syield a nonzero coefficient of Rλ(f)(y). In particular, csand cs+de are always nonzero, so that Rλ(f)(y) has degree dand it is never divisible by y. If π0=ρπ is another prime element of O, and c= ¯ρ∈F∗, the residual coefficients of N− φ(f) with respect to π0satisfy c0 i=cic−ui, so that the corresponding residual polynomial R0 λ(f)(y) is equal to c−uRλ(f)(chy). We can define in a completely analogous way the residual polynomial of f(x) with respect to a side T, which is not necessarily a λ-component of N− φ(f). Definition 1.10. Let T∈ S(λ)be an arbitrary side of slope λ, with abscissas s0≤s1for the end points, and let d0=d(T). We say that the polynomial f(x) lies above Tif all points of N− φ(f)with abscissa s0≤i≤s1lie above T; in this case we define Rλ(f, T)(y) := ˜cs0+ ˜cs0+ey+· · · + ˜cs0+(d0−1)eyd0−1+ ˜cs0+d0eyd0∈Fφ[y], where ˜ci=ciif (i, ui)lies on Tand ˜ci= 0 otherwise. Thus, if all points of Sλ(f) lie strictly above Twe have Rλ(f, T )(y) = 0. Note that deg Rλ(f, T)(y)≤d0and equality holds if and only if the final point of T 8 GU` ARDIA, MONTES, AND NART belongs to Sλ(f). Usually, Twill be an enlargement of Sλ(f) and then, T⊇Sλ(f) =⇒Rλ(f, T)(y) = y(s−s0)/eRλ(f)(y), where sis the abscissa of the initial point of Sλ(f). • • • • H H H H H H H H H H H H H H H H XX X XX X A A A A A A Sλ(f) T s0s s1 The motivation for this more general definition lies in the bad behaviour of the residual polynomial Rλ(f)(y) with respect to sums. Nevertheless, if Tis a fixed side and f(x), g(x) lie both above T, it is clear that (2) Rλ(f+g, T )(y) = Rλ(f, T )(y) + Rλ(g, T)(y). 1.3. Admissible φ-developments and Theorem of the product. Let (3) f(x) = X i≥0 a0 i(x)φ(x)i, a0 i(x)∈ O[x], be a φ-development of f(x), not necessarily the φ-adic one. Take u0 i=v(a0 i(x)), and let N0be the principal polygon of the set of points (i, u0 i). Let i1be the first abscissa with a0 i1(x)6= 0. To any i1≤i≤`(N0) we attach a residual coefficient as before: c0 i=     0,if (i, u0 i) lies strictly above N0, red a0 i(x) πu0 i,if (i, u0 i) lies on N0 For the points (i, u0 i) lying on N0we can have now c0 i= 0; for instance, in the case a0 0(x) = f(x), the Newton polygon has only one point (0, v(f)) and c0 0= 0 if f(x)/πv(f)is divisible by φ(x) modulo m. Finally, for any negative rational number λ, we can define the residual polynomial attached to the λ-component S0=Sλ(N0) to be R0 λ(f)(y) := c0 s0+c0 s0+ey+· · · +c0 s0+(d0−1)eyd0−1+c0 s0+d0eyd0∈Fφ[y], where d0=d(S0) and s0is the abscissa of the initial point of S0. Definition 1.11. We say that the φ-development (3) is admissible if for each abscissa iof a vertex of N0we have c0 i6= 0. Lemma 1.12. If a φ-development is admissible, then N0=N− φ(f)and c0 i=ci for all abscissas iof the finite part of N0. In particular, for any negative rational number λwe have R0 λ(f)(y) = Rλ(f)(y). Proof. Consider the φ-adic developments of f(x) and each a0 i(x): f(x) = X 0≤i ai(x)φ(x)i, a0 i(x) = X 0≤k bi,k(x)φ(x)k. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 9 By the uniqueness of the φ-adic development we have (4) ai(x) = X 0≤k≤i bi−k,k(x). Clearly, wi,k := v(bi,k)≥u0 i, for all 0 ≤k, 0 ≤i≤`(N0). In particular, all points (i, ui) lie above N0; in fact (5) ui=v(ai)≥min 0≤k≤i{wi−k,k}=wi−k0,k0≥u0 i−k0≥hi−k0(N0)≥hi(N0), for some 0 ≤k0≤i. Also, for any abscissa iof the finite part of N0, (6) wi−k,k ≥u0 i−k≥hi−k(N0)> hi(N0),∀k > 0. Hence, for the abscissas with u0 i=hi(N0) we have (7) c0 i= red(a0 i(x)/πu0 i) = red(bi,0(x)/πu0 i). Now, if (i, u0 i) is a vertex of N0we have c0 i6= 0 by hypothesis, and from (7) we get hi(N0) = u0 i=wi,0. By (6) and (4) we have ui=wi,0=u0 i. This shows that N0=N− φ(f). Let us denote this common polygon by N. Finally, let us prove the equality of all residual coefficients. If ci6= 0, then ui=hi(N), and from (5) we get k0= 0 and ui=wi,0=u0 i. By (6), (4) and (7), we get ci= red(ai(x)/πui) = red(bi,0(x)/πui) = c0 i. If ci= 0, then ui> hi(N), and from (4) and (6) we get wi,0> hi(N) too. By (7) we get c0 i= 0.  The construction of the principal part of the φ-Newton polygon of a polynomial can be interpreted as a mapping N− φ:O[x]\ {0} −→ PP, f(x)7→ N− φ(f). Also, for any negative rational number λ, the construction of the residual polynomial attached to λcan be interpreted as a mapping Rλ:O[x]\ {0} −→ Fφ[y]\ {0}, f(x)7→ Rλ(f)(y). The Theorem of the product says that both mappings are semigroup homomorphisms. Theorem 1.13 (Theorem of the product).For any f(x), g(x)∈ O[x]\ {0}and any λ∈Q−we have N− φ(fg) = N− φ(f) + N− φ(g), Rλ(fg)(y) = Rλ(f)(y)Rλ(g)(y). Proof. Consider the respective φ-adic developments f(x) = X 0≤i ai(x)φ(x)i, g(x) = X 0≤j bj(x)φ(x)j, and denote ui=v(ai(x)), vj=v(bj(x)), Nf=N− φ(f), Ng=N− φ(g). Then, (8) f(x)g(x) = X 0≤k Ak(x)φ(x)k, Ak(x) = X i+j=k ai(x)bj(x). Denote by N0the principal part of the Newton polygon of fg, determined by this φ-development. We shall show that N0=Nf+Ng, that this φ-development is admissible, and that R0 λ(fg) = Rλ(f)Rλ(g) for all λ. The theorem will be then a consequence of Lemma 1.12. 16 GU` ARDIA, MONTES, AND NART 2.1. Types of order r−1.Atype of order r−1 is a sequence of data t= (φ1(x); λ1, φ2(x); · · · ;λr−2, φr−1(x); λr−1, ψr−1(y)), where φi(x) are monic polynomials in O[x], λiare negative rational numbers and ψr−1(y) is a monic polynomial over certain finite field (to be specified below), that satisfy the following recursive properties: (1) φ1(x) is irreducible modulo m. We denote by ψ0(y)∈F[y] the polynomial obtained by reduction of φ1(y) modulo m. We define F1:= F[y]/(ψ0(y)). (2) For all 1 ≤i<r−1, the Newton polygon of i-th order, Ni(φi+1), is one-sided, with positive length and slope λi. (3) For all 1 ≤i < r −1, the residual polynomial of i-th order, Ri(φi+1)(y), is an irreducible polynomial in Fi[y]. We denote by ψi(y)∈Fi[y] the monic polynomial determined by Ri(φi+1)(y)≈ψi(y). We define Fi+1 := Fi[y]/(ψi(y)). (4) ψr−1(y)∈Fr−1[y] is a monic irreducible polynomial, ψr−1(y)6=y. We define Fr:= Fr−1[y]/(ψr−1(y)). The type determines a tower F=: F0⊆F1⊆ ·· · ⊆ Frof finite fields. The field Fishould not be confused with the finite field with ielements. By the Theorem of the product in orders 1, . . . , r −1, the polynomials φi(x) are all irreducible over O[x]. Let us be more precise about the meaning of Ni(−), Ri(−), used in item 2. Notation 2.1. For all 1≤i<r, we obtain by truncation of ta type of order i, and a reduced type of order i, defined respectively as: ti:= (φ1(x); λ1, φ2(x); · · · ;λi−1, φi(x); λi, ψi(y)), t0 i:= (φ1(x); λ1, φ2(x); · · · ;λi−1, φi(x); λi). For 1≤i<r−1, we define the extended type of order i−1to be ˜ ti−1:= (φ1(x); λ1, φ2(x); · · · ;λi−1, φi(x)). We have semigroup homomorphisms: N− i:O[x]\{0} → PP, Si:O[x]\{0}→S(λi), Ri:O[x]\{0} → Fi[y]. For any nonzero polynomial P(x)∈ O[x],Ni(P)is the i-th order Newton polygon with respect to the extended type ˜ ti−1,Si(P)is the λi-component of N− i(P), and Ri(P)(y)is the residual polynomial of i-th order. Both Siand Ridepend on the reduced type t0 i. Finally, we denote by si(P)the initial abscissa of Si(P). Other data attached to the type tdeserve an specific notation. For all 1 ≤i<r: •λi=−hi/ei, with ei, hipositive coprime integers, •fi:= deg ψi(y), f0:= deg ψ0(y) = deg φ1(x), •mi:= deg φi(x), and mr:= mr−1er−1fr−1. Note that mi+1 =mieifi= m1e1f1· · · eifi, •`i, `0 i∈Zare fixed integers such that `ihi−`0 iei= 1, •zi:= y(mod ψi(y)) ∈F∗ i+1,z0:= y(mod ψ0(y)) ∈F1. Note that Fi+1 = Fi(zi), NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 17 Also, for all 0 ≤i<rwe have semigroup homomorphisms ωi+1 :O[x]\ {0} −→ Z≥0, P(x)7→ ordψi(Ri(P)), where, by convention: R0(P) = P(y)/πv(P)∈F[y]. Definition 2.2. We say that a monic polynomial P(x)∈ O[x]has type tif, (1) P(x)≡φ1(x)a0(mod m), for some positive integer a0, (2) For all 1≤i < r, the Newton polygon Ni(P)is one-sided, of slope λi, and Ri(P)(y)≈ψi(y)aiin Fi[y], for some positive integer ai. Lemma 2.3. For any nonzero polynomial P(x)∈ O[x]we have ω1(P)≥e1f1ω2(P)≥ · · · ≥ e1f1· · · er−1fr−1ωr(P). If P(x)has type tthen all these inequalities are equalities, and deg P(x) = mrωr(P) = mr−1ωr−1(P) = · · · =m1ω1(P). Proof. eifiωi+1(P)≤eideg Ri(P) = eid(Si(P)) = `(Si(P)) ≤`(N− i(P)) = ωi(P), the last equality by Lemma 2.18 in order i. If P(x) has type t, we have deg P= m1a0=m1ω1(P), and the two inequalities above are equalities.  Definition 2.4. Let P(x)∈ O[x]be a monic polynomial with ωr(P)>0. We denote by Pt(x)the monic factor of P(x)of greatest degree that has type t. By the Theorem of the residual polynomial in order r−1, (11) ωr(Pt) = ωr(P),deg Pt=mrωr(P). Lemma 2.5. Let P(x), Q(x)∈ O[x]be monic polynomials of positive degree. (1) deg P < mr=⇒ωr(P) = 0, (2) P(x)is of type tif and only if deg P=mrωr(P)>0, (3) P(x)Q(x)has type tif and only if P(x)and Q(x)have both type t. Proof. Items 1 and 2 are an immediate consequence of (11). Item 3 follows from the Theorem of the product in orders 1, . . . , r −1.  We fix a type tof order r−1 for the rest of section 2. 2.2. The p-adic valuation of r-th order. In this section we shall attach to t a discrete valuation vr:K(x)∗−→ Z, that restricted to Kextends vwith index e1· · · er−1. We need only to define vron O[x]. Consider the mapping Hr−1:S(λr−1)−→ Z≥0, that assigns to each side S∈ S(λr−1) the non-negative integer obtained as er−1 times the ordinate at the origin of the line Lλr−1of slope λr−1that contains S. If (i, u) is any point of integer coordinates lying on S, then Hr−1(S) = hr−1i+er−1u; thus, Hr−1is a semigroup homomorphism. Definition 2.6. For any polynomial P(x)∈ O[x],P(x)6= 0, we define vr(P) := Hr−1(Sr−1(P)). Note that vrdepends only on the reduced type t0. 18 GU` ARDIA, MONTES, AND NART • •@ @ @ @P P P P A A A A A A H H H H H H H H H H H H Nr−1(P) Lλr−1 vr(P)/er−1 i u Proposition 2.7. The natural extension of vrto K(x)∗is a discrete valuation, whose restriction to K∗extends vwith index e1· · · er−1. Proof. The mapping vrrestricted to O[x]\ {0}is a semigroup homomorphism, because it is the composition of two semigroup homomorphisms; hence, vr:K(x)∗−→ Zis a group homomorphism. Let P(x), Q(x)∈ O[x] be two nonzero polynomials and denote NP=N− r−1(P), NQ=N− r−1(Q), LP=Lλr−1(NP), LQ=Lλr−1(NQ) (cf. Definition 1.5). All points of NPlie above the line LPand all points of NQlie above the line LQ. If vr(P)≤vr(Q), all points of both polygons lie above the line LP. Thus, all points of N− r−1(P+Q) lie above this line too, and this shows that vr(P+Q)≥vr(P). Finally, for any a∈ O, we have vr(a) = er−1vr−1(a) by definition, since the (r−1)-th order Newton polygon of ais the single point (0, vr−1(a)).  This valuation was introduced by S. MacLane without using Newton polygons [McL36a], [McL36b]. In [Mon99, Ch.2,§2], J. Montes computed explicit generators of the residue field of vras a transcendental extension of a finite field. These results lead to a more conceptual and elegant definition of residual polynomials in higher order, as the reductions modulo vrof the virtual factors. However, we shall not follow this approach, in order not to burden the paper with even more technicalities. The main properties we need of this discrete valuation are gathered in the next proposition. Proposition 2.8. Let P(x), Q(x)∈ O[x]be nonzero polynomials. (1) vr(P)≥er−1vr−1(P)and equality holds if and only if ωr−1(P)=0. (2) vr(P)=0if and only if v2(P)=0if and only if red(P)6= 0. (3) vr(φr−1) = er−1vr−1(φr−1) + hr−1. (4) If P(x) = P0≤iai(x)φr−1(x)iis the φr−1-adic development of P(x), then vr(P) = min 0≤i{vr(ai(x)φr−1(x)i)}=er−1min 0≤i{vr−1(ai(x) + i(vr−1(φr−1) + |λr−1|)}. (5) vr(P−Q)> vr(P)if and only if Sr−1(P) = Sr−1(Q)and Rr−1(P) = Rr−1(Q). In this case, ωr(P) = ωr(Q). Proof. We denote throughout the proof, N=N− r−1(P), N0=N− r−1(Q). By (1) of Lemma 2.18 in order r−1, all points of Nlie above the horizontal line with ordinate vr−1(P). Hence, vr(P)≥er−1vr−1(P). Equality holds if and only if the first point of Nis (0, vr−1(P)); this is equivalent to ωr−1(P) = 0, by (2) of Lemma 2.18 in order r−1. This proves item 1. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 19 • •@ @ @ @P P P P A A A A A A H H H H H H H H H H H H Lλr−1 vr(P)/er−1 vr−1(P) By a recurrent aplication of item 1, vr(P) = 0 is equivalent to v1(P) = 0 and ω1(P) = · · · =ωr−1(P) = 0. By Lemma 2.3 this is equivalent to v1(P) = 0 and ω1(P) = 0, which is equivalent to v2(P) = 0, and also to P(x)6∈ (π, φ1(x)). This proves item 2. Item 3 is immediate from the definition. The polygon Nr−1(φr−1) has only two points (0,∞), (1, vr−1(φr−1)); hence it has only one side of length one and slope −∞. The line Lλr−1touches the polygon at the point (1, vr−1(φr−1)), so that vr(φr−1) = hr−1·1 + er−1·vr−1(φr−1). By definition, vr(ai(x)φr−1(x)i) is er−1times the ordinate at the origin of the line Lthat has slope λr−1and passes through (i, vr−1(ai(x)φr−1(x)i)). Since all points of Nlie above the line Lλr−1(N), the line Llies above Lλr−1(N) too, and vr(ai(x)φr−1(x)i)≥vr(P). On the other hand, for the points lying on Sr−1(P) we have L=Lλr−1(N) and vr(ai(x)φr−1(x)i) = vr(P). This proves item 4. @ @ @ @P P P P A A A A A A H H H H H H H H H H H H • •H H H H H H H H H H H H Lλr−1(N) L • i (i, ui) vr(ai(x)φr−1(x)i)/er−1 vr(P)/er−1 Let us prove finally item 5. If vr(P)< vr(Q) the parallel lines Lλr−1(N), Lλr−1(N0) are different and Sr−1(P)6=Sr−1(Q). If vr(P) = vr(Q), the above parallel lines coincide and we can consider the shortest segment Sof Lλr−1(N) that contains Sr−1(P) and Sr−1(Q). By (16) in order r−1, the condition Sr−1(P) = Sr−1(Q), Rr−1(P) = Rr−1(Q), is equivalent to Rr−1(P, S) = Rr−1(Q, S), which is equivalent to Rr−1(P−Q, S) = 0, by Lemma 2.24 in order r−1. This is equivalent to N− r−1(P−Q) lying strictly above Lλr−1(N), which is equivalent in turn to vr(P−Q)> vr(P).  In a natural way, ωrinduces a group homomorphism from K(x)∗to Z, but it is not a discrete valuation of this field. For instance, for t= (x;−1, y + 1) and P(x) = x+p,Q(x) = x+p+p2, we have R1(P) = y+ 1, R1(Q) = y+ 1, R1(P−Q) = 1, ω2(P)=1, ω2(Q)=1, ω2(P−Q)=0. 20 GU` ARDIA, MONTES, AND NART The following proposition stablishes a very particular relationship between vrand ωr. We shall say that ωris a pseudo-valuation with respect to vr. Proposition 2.9. Let P(x), Q(x)∈ O[x]be two nonzero polynomials such that vr(P) = vr(Q)and ωr(P)6=ωr(Q). Then, vr(P+Q) = vr(P) = vr(Q)and ωr(P+Q) = min{ωr(P), ωr(Q)}. Proof. Suppose ωr(P)< ωr(Q). Since ωr(Q) = ωr(−Q), item 5 of the last proposition shows that vr(P−(−Q)) = vr(P). Let N=N− r−1(P) and let Sbe the shortest segment of Lλr−1(N) that contains Sr−1(P) and Sr−1(Q). By Lemma 2.24 in order r−1 we have Rr−1(P+Q, S) = Rr−1(P, S) + Rr−1(Q, S), and by (16) in order r−1 this translates into yaRr−1(P+Q)(y) = ybRr−1(P)(y) + ycRr−1(Q)(y), for certain nonnegative integers a, b, c. Since the residual polynomials are never divisible by y, and ψr−1(y)6=y, from ordψr−1(Rr−1(P)) <ordψr−1(Rr−1(Q)) we deduce ordψr−1(Rr−1(P+Q)) = ordψr−1(Rr−1(P)).  • •@ @ @ @P P P P A A A A A A H H H H H H H H H H H H H H H Lλr−1(N) vr(P)/er−1 • •H H HH H H XX XX @ @ @ @ H H H HY HHHHj S We can reinterpret the computation of v(P(θ)) given in item 5 of Proposition 3.5 in order r−1 (cf. Proposition 1.19 for r= 2), in terms of the pair vr, ωr. Proposition 2.10. Let θ∈Qpbe a root of a polynomial in O[x]of type t. Then, for any nonzero polynomial P(x)∈ O[x], v(P(θ)) ≥vr(P(x))/e1· · · er−1, and equality holds if and only if ωr(P)=0. 2.3. Construction of a representative of t. By Lemma 2.3, a nonconstant polynomial of type thas degree at least mr. In this section we shall show how to construct in a effective (and recursive) way a polynomial φr(x) of type tand minimal degree mr. We first show how to construct a polynomial with prescribed residual polynomial. Proposition 2.11. Let Vbe an integer, V≥er−1fr−1vr(φr−1). Let ϕ(y)∈ Fr−1[y]be a nonzero polynomial of degree less than fr−1, and let ν= ordy(ϕ). Then, we can construct in an effective way a polynomial P(x)∈ O[x]satisfying the following properties deg P(x)< mr, vr(P) = V, yνRr−1(P)(y) = ϕ(y). NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 21 Proof. Let Lbe the line of slope λr−1with ordinate V/er−1at the origin. Let Tbe the greatest side contained in L, whose end points have nonnegative integer coordinates. Let (s, u) be the initial point of Tand denote uj:= u−jhr−1, for all 0≤j < fr−1, so that (s+jer−1, uj) lies on L. Clearly, s < er−1and, for all j, (12) j < fr−1, s < er−1=⇒s+jer−1< er−1fr−1. Let us check that uj≥0, so that (s+jer−1, uj) actually lies on T. In fact, let us prove a stronger inequality; denote Vj:= uj−(s+jer−1)vr−1(φr−1). Since u= (V−shr−1)/er−1, we get Vj=1 er−1 (V−(s+jer−1)(er−1vr−1(φr−1) + hr−1) ( by item 3 of Prop. 2.8 ) =1 er−1 (V−(s+jer−1)vr(φr−1)) ≥( by (12) ) ≥1 er−1 (V−(er−1fr−1−1)vr(φr−1)) ≥( by hypothesis ) ≥1 er−1 vr(φr−1) = vr−1(φr−1) + hr−1 er−1 > vr−1(φr−1) = er−2fr−2vr−1(φr−2), the last equality by (13) below, in order r−1.. Let ϕ(y) = P0≤j<fr−1cjyj, with cj∈Fr−1. Select polynomials cj(y)∈Fr−2[y] of degree less than fr−2, such that cjis the class of cj(y) modulo ψr−2(y), or equivalently, cj(zr−2) = cj. We proceed by induction on r≥2. For r= 2 the polynomials cj(y) belong to F[y]; we abuse of language and denote by cj(x)∈ O[x] the polynomials obtained by choosing arbitrary lifts to Oof the nonzero coefficients of cj(y). The polynomial P(x) = P0≤j<fr−1πu−jh1cj(x)φ1(x)s+je1satisfies the required properties. In fact, by (12), deg(cj(x)φ1(x)s+je1)< m1+ (e1f1−1)m1=m2, for all j. For the coefficients cj= 0 we take cj(x) = 0. For the coefficients cj6= 0, we have cj(y)6= 0 and v(cj(x)) = 0; hence, v(πu−jh1cj(x)) = u−jh1=uj. Thus, the coefficient πu−jh1cj(x) determines a point of N− 1(P) lying on T, and v2(P) = V. Finally, it is clear by construction that ν= (s1(P)−s)/e1and yνR1(P)(y) = R1(P, T)(y) = ϕ(y). Suppose now that the proposition has been proved for orders 2, . . . , r −1. For any 0 ≤j < fr−1we have seen above that Vj> er−2fr−2vr−1(φr−2). Let Ljbe the line of slope λr−2with ordinate at the origin Vj/er−2. Let Tjbe the greatest side contained in Lj, whose end points have nonnegative integer coordinates. Let sjbe the initial abscissa of Tj. Consider the unique polynomial ϕj(y)∈Fr−2[y], of degree less than fr−2, such that ϕj(y)≡y(`r−2uj−sj)/er−2cj(y) (mod ψr−2(y)), and let νj= ordy(ϕj). By induction hypothesis, we are able to construct a polynomial Pj(x) of degree less than mr−1, with vr−1(Pj) = Vj,νj= (sr−2(Pj)−sj)/er−2, and yνjRr−2(Pj)(y) = ϕj(y) in Fr−2[y]. 22 GU` ARDIA, MONTES, AND NART • • ••••• Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q T Sr−1(P) V/er−1 u s sr−1(P) 0 Nr−1(P) H H H H H H H H H H H H H Vj/er−2 • • • • • • • H H H H H H H H H H H Tj Sr−2(Pj) Nr−2(Pj) sjsr−2(Pj) 0 The polynomial P(x) we are looking for is: P(x) = X 0≤j<fr−1 Pj(x)φr−1(x)s+jer−1∈ O[x]. In fact, by (12), deg(Pj(x)φr−1(x)s+jer−1)< mr−1+(er−1fr−1−1)m1=mr, for all j. If Pj(x)6= 0, then vr−1(Pj(x)φr−1(x)s+jer−1) = Vj+(s+jer−1)vr−1(φr−1) = uj, so that all of these coefficients determine points of N− r−1(P) lying on T; this shows that vr(P) = V. For cj= 0 we take Pj(x) = 0; hence, ν= (sr−1(P)−s)/er−1, and by the definition of the residual polynomial in order r−1 (cf. Definition 2.21): yνRr−1(P)(y) = X Pj(x)6=0 (zr−2)tr−2(j)Rr−2(Pj)(zr−2)yj=Rr−1(P, T)(y), where tr−2(j) = (sr−2(Pj)−`r−2uj)/er−2. Finally, (zr−2)tr−2(j)Rr−2(Pj)(zr−2) = (zr−2)tr−2(j)−νjϕj(zr−2) = (zr−2)tr−2(j)−νj+`r−2uj−sj er−2cj(zr−2) = cj, so that yνRr−1(P)(y) = ϕ(y).  Theorem 2.12. We can effectively construct a monic polynomial φr(x)of type t such that Rr−1(φr)(y) = ψr−1(y). This polynomial is irreducible over O[x]and it satisfies (13) deg φr=mr, ωr(φr)=1, vr(φr) = er−1fr−1vr(φr−1). Proof. The polynomial ϕ(y) := ψr−1(y)−yfr−1has degree less than fr−1, and ν= ordy(ϕ) = 0. Let P(x) be the polynomial attached by Proposition 2.11 to ϕ(y) and V=er−1fr−1vr(φr−1). Since deg(P(x)) < mr, the polynomial φr(x) := φr−1(x)er−1fr−1+P(x) is monic and it has degree mr. Let Tbe the auxiliary side used in the construction of P(x); we saw along the proof of Proposition 2.11 that Rr−1(P)(y) = ϕ(y) = Rr−1(P, T)(y). By (16), Sr−1(P) has the same initial point than Tand Rr−1(φr)(y) = Rr−1(φr, T)(y) too. Finally, Rr−1(φr, T)(y) = Rr−1(φer−1fr−1 r−1, T)(y)+Rr−1(P, T)(y) = yfr−1+ϕ(y) = ψr−1(y), and ωr(φr) = 1. The polynomial φr(x) is irreducible over O[x] by the Theorem of the product in order r−1. Finally, it has vr(φr) = Vbecause all points of Nr−1(φr) lie on T. Definition 2.13. Arepresentative of the type tis a monic polynomial φr(x)of type tsuch that Rr−1(φr)(y)≈ψr−1(y). This object plays the analogous role in order r−1to that of an irreducible polynomial modulo min order one. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 23 By Theorem 2.12, we can always find a representative φr(x) of tsuch that Rr−1(φr)(y) = ψr−1(y); however, we do not impose this condition in the definition of a representative, because in some instances we need to work with representatives satisfying some extra conditions that are incompatible with such an equality (cf. Proposition 3.6). From now on, we fix a representative φr(x) of t, without necessarily assuming that it has been constructed by the method of Propositon 2.11. 2.4. Certain rational functions. We introduce in a recursive way several rational functions in K(x). Definition 2.14. We define φ0(x) = x,π0(x) = 1,π1(x) = π, and Φi(x) = φi(x) πi−1(x)fi−1vi(φi−1), γi(x) = Φi(x)ei πi(x)hi, πi+1(x) = Φi(x)`i πi(x)`0 i , for all 1≤i≤r. Each of these rational functions can be written as πn0φ1(x)n1· · · φr(x)nr, for adequate (positive or negative) integers ni. Also, (14) Φi(x) = · · · φi(x), γi(x) = · · · φi(x)ei, πi+1(x) = · · · φi(x)`i, where the dots indicate a product of integral powers of πand φj(x), with j < i. We want to compute the value of vron all these functions. Lemma 2.15. Let 1≤i<j≤r. (1) ωj(φi) = 0, (2) If mi=mjthen vj(φi) = vj(φi−φj)≤vj(φj). Proof. Since Ni(φi) is a side of slope −∞, we have ωi+1(φi) = 0 because Si(φi) reduces to a point. By Lemma 2.3, ωj(φi) = 0 for all j > i. By (13), ωj(φj) = 1; hence, vj(φi−φj) = min{vj(φi), vj(φj)}by item 5 of Proposition 2.8. Now, mi=mjimplies deg(φi−φj)< mj, and ωj(φi−φj) = 0 by Lemma 2.5. Again by item 5 of Proposition 2.8, vj(φi) = min{vj(φi−φj), vj(φj)}. This proves item 2.  Proposition 2.16. For all 1≤i<rwe have (1) vr(φi) = Pi j=1 (ej+1 · · · er−1) (ejfj· · · ei−1fi−1)hj, (2) vr(Φi) = ei+1 · · · er−1hi, (3) vr(πi+1) = ei+1 · · · er−1, (4) vr(γi)=0. (5) ωr(φi) = ωr(Φi) = ωr(γi) = ωr(πi+1) = 0. Moreover, vr(φr) = Pr−1 j=1 (ej+1 · · · er−1) (ejfj· · · ei−1fi−1)hjand vr(Φr)=0. Proof. We proceed by induction on r. For r= 2 all formulas are easily deduced from v2(φ1) = h1, that was proved in Proposition 2.8. Suppose r≥3 and all statements true for r−1. Let us start with item 1. By Proposition 2.8 and (13), vr(φr−1) = hr−1+er−1vr−1(φr−1), vr−1(φr−1) = er−2fr−2vr−1(φr−2). Hence, the formula for i=r−1 follows from the induction hypothesis. Suppose from now on i < r −1. If mi< mr−1, then Nr−1(φi) = (0, vr−1(φi)), so that vr(φi) = er−1vr−1(φi) and the formula follows by induction. Finally, if mi=mr−1, 24 GU` ARDIA, MONTES, AND NART then φi= (φi−φr−1) + φr−1is the φr−1-adic development of φi, and Nr−1(φi) has two points (0, vr−1(φi−φr−1)) and (1, vr−1(φr−1)). By the above lemma, vr−1(φi) = vr−1(φi−φr−1)≤vr−1(φr−1); thus, N− r−1(φi) = (0, vr−1(φi−φr−1)) = (0, vr−1(φi)), and vr(φi) = er−1vr−1(φi). The formula follows by induction as well. Let us prove now simultaneously items 2 and 3 by induction on i. For i= 1 we have by item 1, vr(Φ1) = vr(φ1) = e2· · · er−1h1, vr(π2) = `1vr(Φ1)−`0 1vr(π)=(`1h1−`0 1e1)e2· · · er−1=e2· · · er−1. Suppose now i > 1 and the formulas hold for 1, . . . , i −1. vr(Φi) = vr(φi)−fi−1vi(φi−1)ei−1· · · er−1=ei+1 · · · er−1hi, vr(πi+1) = `ivr(Φi)−`0 ivr(πi)=(`ihi−`0 iei)ei+1 · · · er−1=ei+1 · · · er−1. Item 4 is easily deduced from the previous formulas, and item 5 is an immediate consequence of (14) and item 1 of Lemma 2.15. The last statements follow from (13) and the previous formulas.  Lemma 2.17. For n= (n0, . . . , nr−1)∈Zr, consider the rational function Φ(n) = πn0φ1(x)n1· · · φr−1(x)nr−1∈K(x). Then, if vr(Φ(n)) = 0, there exists a unique sequence i1, . . . , ir−1of integers such that Φ(n) = γ1(x)i1· · · γr−1(x)ir−1. Moreover, isdepends only on ns, . . . , nr−1, for all 1≤s < r. Proof. Since the polynomials φs(x) are irreducible and pairwise different, we have Φ(n) = Φ(n0) if and only if n=n0. By (14), any product γ1(x)i1· · · γr−1(x)ir−1 can be expressed as Φ(j), for a suitable j= (j0, . . . , jr−2, er−1ir−1). Thus, if γ1(x)i1· · · γr−1(x)ir−1= 1 we have necessarily ir−1= 0, and recursively, i1= · · · =ir−2= 0. This proves the unicity of the expression of any Φ(n) as a product of powers of gammas. Let us prove the existence of such an expression by induction on r≥1. For r= 1, let n= (n0); the condition vr(πn0) = 0 implies n0= 0 and Φ(n) = 1. Suppose r≥2 and the lemma proven for all n0∈Zr−1. By item 1 of the last lemma, vr(Φ(n)) ≡ nr−1hr−1(mod er−1); hence, if vr(Φ(n)) = 0 we have necessarily nr−1=er−1ir−1 for some integer ir−1that depends only on nr−1. By (14), γr−1(x)ir−1= Φ(j), for some j= (j0, . . . , jr−2, er−1ir−1); hence, Φ(n)γr−1(x)−ir−1= Φ(n0), with n0= (n0 0, . . . , n0 r−2,0), and each n0 sdepends only on nsand nr−1. By item 4 of the last lemma, we have still vr(Φ(n0)) = 0, and by induction hypothesis we get the desired expression of Φ(n) as a product of powers of gammas.  2.5. Newton polygon and residual polynomials of r-th order. Let f(x)∈ O[x] be a nonzero polynomial, and consider its unique φr-adic development (15) f(x) = X 0≤i≤bdeg(f)/mrc ai(x)φr(x)i,deg ai(x)< mr. We define the Newton polygon Nr(f) of f(x), with respect to the extended type ˜ t:= (φ1(x); λ1, φ2(x); · · · ;λr−2, φr−1(x); λr−1, φr(x)), to be the lower convex envelope of the set of points (i, ui), where ui:= vr(ai(x)φr(x)i) = vr(ai(x)) + ivr(φr(x)). NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 25 Note that we consider the vr-value of the whole monomial ai(x)φr(x)i. Actually, we did the same for the Newton polygons of first order, but in that case v1(ai(x)φ1(x)i) = v1(ai(x)), because v1(φ1(x)) = 0. The principal part N− r(f) is the part of all sides of negative slope, including the side of slope −∞ if f(x) is divisible by φr(x) in O[x]. The typical shape of the polygon is the following • • • •• • • Q Q Q Q Q A A A A A A Q Q Q Q Q A A A A A A •   bdeg(f)/mrcωr(f)ordφr(f) vr(f) 0 Lemma 2.18. (1) min0≤i≤`{ui}=vr(f), (2) The length of N− r(f)is ωr(f), (3) The side of slope −∞ of N− r(f)has length ordφr(f). Proof. The third item is obvious. Let us prove items 1, 2. Let u:= min0≤i≤`{ui}, and consider the polynomial g(x) := X ui=u ai(x)φr(x)i. All monomials of g(x) have the same vr-value and a different ωr-value: ωr(ai(x)φr(x)i) = ωr(ai(x)) + ωr(φr(x)i) = i, because ωr(ai) = 0 by Lemma 2.5. By Proposition 2.9, vr(g) = uand ωr(g) = i0, the least abscissa with ui0=u. Since, vr(f−g)> u, we have vr(f) = vr(g) = u, and this proves item 1. On the other hand, item 5 of Propositon 2.8 shows that R1(f) = R1(g); in particular, ωr(f) = ωr(g) = i0, and this proves item 2.  The following observation is a consequence of Lemmas 2.5 and 2.18. Corollary 2.19. If f(x)has type tthen Nr(f) = N− r(f). From now on let N=N− r(f). As we did in order one, we attach to any abscissa iof Naresidual coefficient ci∈Fr. The natural idea is to consider ci=Rr−1(ai)(zr−1) for the points lying on N. However, this does not lead to the right concept of residual polynomial attached to a side; it is necessary to twist these coefficients by certain powers of zr−1. Definition 2.20. For any nonzero a(x)∈ O[x]and any integer i≥0, we denote tr−1(a)i:= sr−1(a)−`r−1vr(aφi r) er−1 . 32 GU` ARDIA, MONTES, AND NART Let λr=−hr/er, with hr, erpositive coprime integers, be a negative rational number such that S:= Sλr(f) has positive length. Let ft,λr(x) be the factor of f(x), corresponding to the pair ˜ t, λrby the Theorem of the polygon. Choose a root θ∈Qpof ft,λr(x), and let L=K(θ). By item 4 of Proposition 3.5 in orders 1, . . . , r −1, there is a well-defined embedding Fr−→ FL, determined by (24) Fr,→FL, z07→ θ, zr−17→ γ1(θ), . . . , zr−17→ γr−1(θ). This embedding depends on the choice of θ. After this identification of Frwith a subfield of FLwe can think that all residual polynomials of r-th order have coefficients in FL. Corollary 3.2. The residual degree f(L/K)is divisible by f0· · · fr−1, and the ramification index e(L/K)is divisible by e1· · · er. Moreover, the number of irreducible factors of ft,λr(x)is at most d(S); in particular, if d(S)=1the polynomial ft,λr(x) is irreducible in O[x], and f(L/K) = f0· · · fr−1,e(L/K) = e1· · · er. Proof. The statement on the residual degree is a consequence of the embedding (24). Let em=e(L/K), and denote e=e1· · · er−1,f=f0· · · fr−1. By the same result in order r−1, emis divisible by e. Now, by the theorem of the polygon, vL(φr(θ)) = (em/e)vr(φr)+(em/e)(hr/er). Since this is an integer and hr, erare coprime, necessarily erdivides em/e. The upper bound for the number of irreducible factors is a consequence of the Theorem of the product. Finally, if d(S) = 1, we have ef = deg(ft,λr) = f(L/K)e(L/K), and necessarily f(L/K) = fand e(L/K) = e. Let us prove now an identity between the rational functions of Definition 2.14, that plays an essential role in what follows. Lemma 3.3. Let P=P0≤iai(x)φr(x)ibe the φr-adic development of a nonzero polynomial in O[x]. Let λr=−hr/erbe a negative rational number, where hr, er are coprime positive integers. Let S=Sλr(P)be the λr-component of N− r(P), let (s, u)be the initial point of Sand (i, ui)any point lying on S. Let (s(ai), u(ai)) be the initial point of the side Sr−1(ai). Then, the following identity holds in K(x): (25) φr(x)iΦr−1(x)s(ai)πr−1(x)u(ai) Φr(x)sπr(x)u=γr−1(x)tr−1(i)γr(x)i−s er. Proof. If we substitute u=ui+ (i−s)hr erand γr= Φer r/πhr rin (25), we see that the identity is equivalent to: φr(x)iΦr−1(x)s(ai)πr−1(x)u(ai) πr(x)ui=γr−1(x)tr−1(i)Φr(x)i. If we substitute now Φr,πrand γr−1by its defining values and we use er−1tr−1(i) = s(ai)−`r−1ui, we get an equation involving only πr−1, which is equivalent to: u(ai) + `0 r−1ui+hr−1tr−1(i) + ifr−1vr(φr−1)=0. This equality is easy to check by using u(ai) + s(ai)hr−1 er−1=vr(ar) = ui−ivr(φr), vr(φr) = er−1fr−1vr(φr−1), and `r−1hr−1−`0 r−1er−1= 1.  Lemma 3.4. The rational function γr(x)∈K(x)satisfies: v(γr(θ)) = 0. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 33 Proof. It is sufficient to check that (26) v(πr(θ)) = 1/(e1· · · er−1), v(Φr(θ)) = hr/(e1· · · er). The first equality follows from Proposition 2.10, because vr(πr) = 1, ωr(πr) = 0 by Proposition 2.16. The second equality of (26) follows from the Theorem of the polygon and the first equality for v(πr−1)(θ).  Proposition 3.5. We keep the above notations for f(x), λr=−hr/er, θ, L, and the embedding (24). Let P(x)∈ O[x]be a nonzero polynomial, S=Sλr(P),Lλr the line of slope λrthat contains S, and Hthe ordinate at the origin of this line. Denote e=e1· · · er−1. Then, (1) v(PS(θ)) ≥0, PS(θ) = Rλr(P)(γr(θ)), (2) v(P(θ)−P0(θ)) > H/e. (3) v(P(θ)) ≥H/e, and equality holds if and only if Rλr(P)(γr(θ)) 6= 0, (4) Rλr(f)(γr(θ)) = 0. (5) If Rλr(f)(y)≈ψr(y)afor some irreducible ψr(y)∈Fr[y]then v(P(θ)) = H/e if and only if Rλr(P)(y)is not divisible by ψr(y)in Fr[y]. Proof. Let P(x) = P0≤iai(x)φr(x)ibe the φr-adic development of P(x), and denote ui=vr(aiφi r), N=N− r(P), Recall that PS(x)=Φr(x)−sπr(x)−uP0(x), P0(x) = X (i,ui)∈S ai(x)φr(x)i, where (s, u) are the coordinates of the initial point of S. By (26), (27) v(Φr(θ)sπr(θ)u) = 1 eshr er +u=H e. On the other hand, by the Theorem of the polygon, for all i: (28) v(ai(θ)φr(θ)i) = vr(ai) e+i evr(φr) + hr er=1 eui+ihr er≥H e, with equality if and only if (i, ui)∈S. This proves item 2. H H H H H H H H H H H H H • • • H H H H H H H H H H H H XX XX @ @ @ @ N− r(P) (i, ui) s i u Lλr 0 Also, (28) shows that v(PS(θ)) ≥0, so that PS(θ) belongs to OL. Denote for simplicity zr=γr(θ). In order to prove the equality PS(θ) = Rλr(P)(zr), we need to show that for every abscissa iin the projection of Sto the horizontal axis: (29) redLai(θ)φr(θ)i Φr(θ)sπr(θ)u= (zr−1)tr−1(i)Rr−1(ai)(zr−1)(zr)(i−s)/er, 34 GU` ARDIA, MONTES, AND NART if (i, ui)∈S, and redL(ai(θ)φr(θ)i)/(Φr(θ)sπr(θ)u)= 0, if (i, ui)6∈ S. The latter equality is a consequence of (27) and (28). Suppose now (i, ui)∈S. By items 1,2 of the proposition in order r−1, applied to the polynomial ai(x), (ai)Sr−1(ai)(θ) = Rr−1(ai)(zr−1), ai(θ)≡Φr−1(θ)s(ai)πr−1(θ)u(ai)(ai)Sr−1(ai)(θ) (mod mvr(ai/e L)), where (s(ai), u(ai)) is the initial point of Sr−1(ai). Thus, it is sufficient to check the following identity in L, φr(θ)iΦr−1(θ)s(ai)πr−1(θ)u(ai) Φr(θ)sπr(θ)u=γr−1(θ)tr−1(i)γr(θ)i−s er, which is a consequence of Lemma 3.3. This ends the proof of item 1. Also, (28) shows that v(P(θ)) ≥H/e, and v(P(θ)) = H/e ⇐⇒ v(P0(θ)) = H/e (27) ⇐⇒ v(PS(θ)) = 0 ⇐⇒ Rλr(P)(zr)6= 0, the last equivalence by item 1. This proves item 3. The last two items are proved by similar arguments to that of the proof of Proposition 1.19.  3.2. Theorem of the residual polynomial in order r.We discuss now how Newton polygons and residual polynomials are affected by an extension of the base field by an unramified extension. We keep the above notations for f(x), λr= −hr/er, θ, L and the embedding (24). Proposition 3.6. Let K0be the unramified extension of Kof degree f0. . . fr−1, and identify Fr=FK0through the embedding (24). Let G(x)∈ OK0[x]be the minimal polynomial of θover K0Then, there exist a type of order r−1over K0, t0= (φ0 1(x); λ1, φ0 2(x); · · · ;λr−1, ψ0 r−1(y)), and a representative φ0 r(x)of t0, with the following properties (where the superscript 0indicates that the objects are taken with respect to t0): (1) f0 0=· · · =f0 r−1= 1, (2) G(x)is of tytpe t0, (3) For any nonzero polynomial P(x)∈ O[x], (N0)− r(P) = N− r(P), R0 λr(P)(y) = σs rτu rRλr(P)(µry), where (s, u)is the initial point of Sλr(P)and σr, τr, µr∈F∗ K0are constants that depend only on tand θ. Proof. We proceed by induction on r. The case r= 1 is considered in Lemma 1.20; for the constant defined there, we can take σ1=,τ1= 1, and µ1=e1. Let r≥2 and suppose we have already constructed t0 r−2and a representative φ0 r−1(x) satisfying these properties. Let η1, . . . , ηfr−1∈FK0be the roots of ψr−1(y). We have, R0 r−1(φr)(y)≈Rr−1(φr)(µr−1y)≈ψr−1(µr−1y) = Qfr−1 i=1 (µr−1y−ηi), R0 r−1(F)(y)≈Rr−1(F)(µr−1y)≈ψr−1(µr−1y)ar−1=Qfr−1 i=1 (µr−1y−ηi)ar−1. Since G(x) is of type t0 r−2, Lemma 2.5 shows that deg G=m0 r−1ω0 r−1(G). Since (N0)− r−1(F) = N− r−1(F), the Theorem of the product shows that (N0)− r−1(G) is one-sided, with slope λr−1and positive length ω0 r−1(G). By the Theorem of the NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 35 residual polynomial, R0 r−1(G)≈(µr−1y−η)a, for some root η∈FK0of ψ0 r−1(y) and some positive integer a. We take t0= (φ0 1(x); λ1, φ0 2(x); · · · ;λr−2, φ0 r−1(y); λr−1, y −µ−1 r−1η), so that f0 r−1= 1. We have deg G=m0 r−1ω0 r−1(G) = m0 r−1er−1a=m0 ra, and a=ω0 r(G). Thus, G(x) is of type t0, again by Lemma 2.5. The same argument shows that there is a unique irreducible factor φ0 r(x) of φr(x) in OK0[x] such that R0 r−1(φ0 r(x)) ≈(µr−1y−η). We choose φ0 r(x) as a representative of t0. Let ρr(x) = φr(x)/φ0 r(x)∈ OK0[x]. By construction, ω0 r(ρr) = 0, because R0 r−1(ρr)≈ψr−1(µr−1y)/(µr−1y−η). Let P(x)∈ O[x] be a nonzero polynomial. Clearly, (N0)− r−1(P) = N− r−1(P) =⇒v0 r(P) = vr(P), R0 r−1(P)(y)≈Rr−1(P)(µr−1y) =⇒ω0 r(P) = ωr(P). Consider the φr-adic development of P(x): P(x) = φr(x)n+an−1(x)φr(x)n−1+· · · +a0(x) = =ρr(x)nφ0 r(x)n+an−1(x)ρr(x)n−1φ0 r(x)n−1+· · · +a0(x). Since ω0 r(ρr) = 0, this φ0 r-adic development of P(x) is admissible. On the other hand, the tautology vr(ai(x)φr(x)i) = v0 r(ai(x)φr(x)i) = v0 r(ai(x)ρr(x)i(φ0 r)(x)i), shows that (N0)− r(P) = N− r(P). In order to prove the relationship between R0 λr(P)(y) and Rλr(P)(y), we introduce some elements in F∗ K0, constructed in terms of the rational functions of Definition 2.14. By Lemma 3.4, v(γr(θ)) = 0 = v(γ0 r(θ)). By (26), v(πr(θ)) = (e1· · · er−1)−1=v(π0 r(θ)), and v(ρr(θ)) = (vr(φr)−v0 r(φ0 r))/(e1· · · er−1) = v(π0 r−1(θ))(vr(φr)−v0 r(φ0 r))/er−1. We introduce the following elements of F∗ K0: µr:= γr(θ)/γ0 r(θ), τr:= πr(θ)/π0 r(θ), σr:= Φr(θ)/Φ0 r(θ), r:= ρr(θ)/π0 r−1(θ)(vr(φr)−v0 r(φ0 r))/er−1, where we used fr−1vr(φr−1) = vr(φr)/er−1in the last equality. By the recursive definition of the functions of Definition 2.14, we get the following identities: (30) σr=r/(τr−1)vr(φr)/er−1, τr= (σr−1)`r−1/(τr−1)`0 r−1. We need still another interpretation of r. Since (N0)− r−1(φr) = N− r−1(φr), the Theorem of the product shows that (N0)r−1(ρr) is one-sided with slope λr−1; hence, the initial point (s0 r−1(ρr), u0 r−1(ρr)) of S:= S0 r−1(ρr) is given by s0 r−1(ρr) = 0 and (31) u0 r−1(ρr) = v0 r(ρr)/er−1= (v0 r(φr)−v0 r(φ0 r))/er−1= (vr(φr)−v0 r(φ0 r))/er−1. Recall that the virtual factor ρS r(x) is by definition ρr(x)/(π0)u0 r−1(ρr) r−1; therefore, item 1 of Proposition 3.5 shows that, for r≥2: (32) r=R0 r−1(ρr)(z0 r−1). We have seen above that for each integer abscissa i, the i-th terms of the φrand φ0 r-developments of P(x) determine the same point (i, ui) of the plane. Let i= 36 GU` ARDIA, MONTES, AND NART s+jerbe an abscissa such that (i, ui) lies on Sλr(P) = S0 λr(P); the corresponding residual coefficients at this abscissa are respectively ci= (zr−1)tr−1(i)Rr−1(ai)(zr−1), c0 i= (z0 r−1)t0 r−1(i)R0 r−1(aiρi r)(z0 r−1), and Rλr(P)(y) = P0≤j≤dciyj,R0 λr(P)(y) = P0≤j≤dc0 iyj. Hence, the last equality of item 3 is equivalent to c0 i=ciσs rτu rµj r, for all such i. Note that tr−1(i) = (sr−1(ai)−`r−1ui)/er−1=t0 r−1(i), because s0 r−1(aiρi r) = s0 r−1(ai) + is0 r−1(ρr) = s0 r−1(ai) = sr−1(ai), the last equality because N− r−1(ai)=(N0)− r−1(ai). For simplicity we denote by (s(ai), u(ai)) the initial point of Sr−1(ai). By (31), the initial point of S0 r−1(aiρi r) is (s(ai), u(ai) + i(vr(φr)−v0 r(φ0 r))/er−1). Now, by induction, the Theorem of the product, and (32), we have c0 i= (z0 r−1)tr−1(i)R0 r−1(ai)(z0 r−1)i r = (z0 r−1)tr−1(i)(σr−1)s(ai)(τr−1)u(ai)Rr−1(ai)(zr−1)i r =ci(µr−1)−tr−1(i)(σr−1)s(ai)(τr−1)u(ai)i r =ciµj rµ−j r(µr−1)−tr−1(i)(σr−1)s(ai)(τr−1)u(ai)i r By Lemma 3.3, γr(θ)jγr−1(θ)tr−1(i)=φr(θ)iΦr−1(θ)s(ai)πr−1(θ)u(ai)Φr(θ)−sπr(θ)−u =φr(θ)iΦr−1(θ)s(ai)−`r−1uπr−1(θ)u(ai)+`0 r−1uΦr(θ)−s. We get an analogous expression for γ0 r(θ)jγ0 r−1(θ)tr−1(i), just by putting 0everywhere and by substituting u(ai) by u(aiρi r) = u(ai) + i(vr(φr)−v0 r(φ0 r))/er−1. By taking the quotient of both expressions and taking classes modulo mK0we get µj r(µr−1)tr−1(i)=i r(σr−1)s(ai)−`r−1u(τr−1)u(ai)+`0 r−1uσ−s r. Therefore, c0 i=ciµj r(σr−1)`r−1u(τr−1)−`0 r−1uσs r=ciµj rτu rσs r, by (30).  Theorem 3.7 (Theorem of the residual polynomial in order r).Let f(x)∈ O[x] be a monic polynomial with ωr(f)>0, and let Sbe a side of N− r(f), of finite slope λr. Consider the factorization Rλr(f)(y) = ψr,1(y)a1· · · ψr,t(y)at, of the residual polynomial of f(x)into the product of powers of pairwise different irreducible polynomials in Fr[y]. Then, the factor ft,λr(x)of ft(x), corresponding to Sby the Theorem of the polygon, admits a factorization in O[x], ft,λr(x) = G1(x)· · · Gt(x), with all Nr(Gi)one-sided of slope λr, and Rλr(Gi)(y)≈ψr,i(y)aiin Fr[y]. Proof. Let us deal first with the case F(x) := ft,λr(x) irreducible. We need only to prove that Rλr(F)(y) is the power of an irreducible polynomial of Fr[y]. Let θ∈Qp be a root of F(x), let L=K(θ), and fix the embedding Fr−→ FLas in (24). Let K0be the unramified extension of Kof degree f0· · · fr−1, and let G(x)∈ OK0[x] be the minimal polynomial of θover K0, so that F(x) = Qσ∈Gal(K0/K)Gσ(x). Under the embedding Fr−→ FL, the field Fris identified with FK0. By Proposition 3.6, we can construct a type t0of order r−1 over K0such that R0 λr(F)(y)∼Rλr(F)(y). NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 37 By the construction of t0, for any σ6= 1, the polynomial Gσ(x) is not divisible by φ0 1(x) modulo mK0; thus, ωr(Gσ)≤ω1(Gσ) = 0, and R0 λr(Gσ)(y) is a constant. Therefore, by the Theorem of the product, R0 λr(G)(y)≈R0 λr(F)(y)∼Rλr(F)(y), so that Rλr(F)(y) is the power of an irreducible polynomial of Fr[y] if and only if R0 λr(G)(y) has the same property over FK0. In conclusion, by extending the base field, we can suppose that f0=· · · fr−1= 1. Let P(x) = Pk j=0 bjxj∈ O[x] be the minimal polynomial of γr(θ). Let Π(x) := γr(x)/φr(x)er=πr−1(x)−erfr−1vr(φr−1)πr(x)−hr. By (14), Π(x) admits an expression Π(x) = πn0 0φ1(x)n0 1· · · φr−1(x)n0 r−1for some integers n0 1, . . . , n0 r. Take Φ(x) := πn0φ1(x)n1· · · φr−1(x)nr−1with sufficiently large positive integers niso that Π(x)kΦ(x) is a polynomial in O[x]. Then, the following rational function is actually a polynomial in O[x]: g(x) := Φ(x)P(γr(x)) = k X j=0 Bjer(x)φr(x)jer, Bjer(x) = Φ(x)Π(x)jbj. Moreover, by Proposition 2.16, ωr(Bjer) = 0 for all jsuch that Bjer6= 0, so that this φr-development of g(x) is admissible. Our aim is to show that Nr(g) is one-sided with slope λr, and Rλr(g)(y) is equal to P(y) modulo m, which is the power of an irreducible polynomial of Fr[y] because P(x) is irreducible. Since g(θ) = 0, F(x) is a divisor of g(x) and by the Theorem of the product the residual polynomial of F(x) will be the power of an irreducible polynomial too. This will end the proof of the theorem in the irreducible case. Let us bound by below all vr(Bjerφjer r). Denote u:= vr(Φ). By Proposition 2.16 and (13), we get: vr(πr−1) = er−1,vr(πr) = 1, and vr(Π) = −ervr(φr)−hr. Therefore, (33) ujer:= vr(Bjerφjer r) = vr(bj) + u−j(ervr(φr) + hr) + jervr(φr)≥u−jhr. For j= 0, k we have v(b0) = 0 (because v(γr(θ)) = 0) and v(bk) = 0 (because bk= 1). Hence, equality holds in (33) for these two abscissas. This proves that Nr(g) has only one side T, with end points (0, u), (ker, u −khr), and slope λr. Let Rλr(g)(y) = Pk j=0 cjeryj. We want to show that cjer=c¯ bjfor certain constant c∈F∗ rindependent of j. Recall that cjer= 0 if and only if (jer, ujer)6∈ T, and by (33), this is equivalent to ¯ bj= 0. Suppose now (jer, ujer)∈T; by item 1 of Proposition 3.5 (cf. (29)) redLBjer(θ)φr(θ)jer πr(θ)u=cjerγr(θ)j. Hence, we want to check that for all j redLBjer(θ)φr(θ)jer πr(θ)uγr(θ)j=c¯ bj, for some nonzero constant c. Now, by substitution of the defining value of γrit is easily checked that the left hand side is equal to c¯ bj, for c= redL(Φ(θ)/πr(θ)u). This ends the proof of the theorem in the irreducible case. In the general case, consider the decomposition, F(x) = QjPj(x), into a product of monic irreducible factors in O[x]. By Lemma 2.5, each Pj(x) has type t, so that ωr(Pj)>0. By the Theorem of the product, Nr(Pj) is one-sided, of ositive 38 GU` ARDIA, MONTES, AND NART length and slope λr. By the proof in the irreducible case, the residual polynomial Rλr(Pj)(y) is the positive power of an irreducible polynomial, and by the Theorem of the product it must be Rλr(Pj)(y)≈ψr,i(y)bjfor some 1 ≤i≤t. If we group these factors according to the irreducible factor of the residual polynomial, we get the desired factorization.  Corollary 3.8. With the above notations, let θ∈Qpbe a root of Gi(x), and L=K(θ). Let fr= deg ψr,i(y),er=er,i. Then, f(L/K)is divisible by f0f1· · · fr. Moreover, if ai= 1 then Gi(x)is irreducible in O[x]and f(L/K) = f0f1· · · fr, e(L/K) = e1· · · er−1er. Proof. The statement about f(L/K) is a consequence of the extension of the embeding (24) to an embedding (34) Fr[y]/ψr,i(y),→FL, y 7→ γr(θ), which is well-defined by item 4 of Proposition 3.5. The irreducibility of Gi(x) when ai= 1 is a consequence of the Theorem of the product. The computation of f(L/K) and e(L/K) follows from f(L/K)e(L/K) = deg Gi=f0f1· · · fre1· · · er−1er, and the fact that f(L/K) is divisible by f0· · · frand e(L/K) is divisible by e1· · · er (cf. Corollary 3.2).  3.3. Types of order r.Let tbe a type of order r−1, and let f(x)∈ O[x] be a monic separable polynomial. Definition 3.9. We say that tis f-complete, if ωr(f) = 1. In this case, ft(x) is irreducible and the ramification index and residual degree of the extension of Kdetermined by ft(x)can be computed in terms of some data of t, by applying Corollary 3.8 in order r−1. If tis a type of order r−1 and ωr(f)>1, the results of Sect. 3 can be interpreted as the addition of two more dissections, for each order 2, . . . , r, to the three classical ones, in the process of factorization of f(x). The factor ft(x) has experimented further factorizations at two levels: first ft(x) factorizes in as many factors as sides of N− r(f), and then, the factors corresponding to finite slopes split into the product of as many factors of pairwise different irreducible factors of the residual polynomial. We can think that the type thas sprouted to produce several types of order r, t0= (˜ t;λr, ψr(y)), each of them distinguished by the choice of a slope λrof a side of N− r(f), and an irreducible factor ψr(y) of Rλr(f)(y) in Fr[y]. Definition 3.10. In Sect. 1.5, we defined two sets t0(f),t1(f). We recursively define tr(f)to be the set of all types of order rconstructed as above, t0= (˜ t;λr, ψr(y)), from those t∈tr−1(f)that are not f-complete. This set is not an intrinsic invariant of f(x)because it depends on the choices of the representatives φ1(x), . . . , φr(x) of the truncations of t. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 39 We denote by tr(f)compl the subset of the f-complete types of tr(f). We define Tr(f) := tr(f)∪ [ 0≤s<r ts(f)compl . Hensel’s lemma and the theorems of the polygon and of the residual polynomial in orders 1, . . . , r determine a factorization (35) f(x) = fr,∞(x)Y t∈Tr(f) ft(x), where fr,∞(x) is the product of the different representatives φi(x), of the different types, that divide f(x) in O[x]. The following remark is an immediate consequence of the definitions. Lemma 3.11. The following conditions are equivalent: (1) tr+1(f) = ∅, (2) tr(f)compl =tr(f), (3) For all t∈tr−1(f)and all λr∈Q−, the residual polynomial of r-th order, Rλr(f)(y)is separable. If these conditions are satisfied, then (35) is a factorization of f(x) into the product of monic irreducible polynomials in O[x], and we get arithmetic information about each factor by Corollary 3.8. As long as there is some t∈tr(f) which is not f-complete, we must apply the results of this section in order r+ 1 to get further factorizations of ft(x), or to detect that it is irreducible. We need some invariant to control the whole process and ensure that after a finite number of steps we shall have tr(f)compl =tr(f). This is the aim of the next section. We end with a remark about p-adic approximations to the irreducible factors of f(x), that is an immediate consequence of Lemma 2.3, the Theorem of the polygon and Proposition 2.16. Proposition 3.12. Let tbe a type of order rof f(x)that is f-complete. Let φr+1(x)∈ O[x]be a representative of t. Then, deg φr+1(x) = deg ft(x), and φr+1(x)is a p-adic approximation to ft(x)satisfying v(φr+1(θ)) = (vr+1(φr+1) + hr+1)/e(L/K) = r+1 X i=1 eifi· · · erfr hi e1. . . ei , where θ∈Qpis a root of ft(x). 4. Indices and resultants of higher order 4.1. Computation of resultants with Newton polygons. Definition 4.1. Let r≥1be a natural number. Let tbe a type of order r−1 and let φr(x)∈ O[x]be a representative of t. For any pair of monic polynomials P(x), Q(x)∈ O[x]we define Rest(P, Q) := f0· · · fr−1 X i,j min{EiH0 j, E0 jHi} , where Ei=`(Si),Hi=H(Si)are the lengths and heights of the sides of N− r(P), and E0 j=`(S0 j),H0 j=H(S0 j)are the lengths and heights of the sides of N− r(Q). 40 GU` ARDIA, MONTES, AND NART We recall that for a side Sof slope −∞ we took H(S) = ∞by convention. Thus, the part of Rest(P, Q) that involves sides of slope −∞ is always (36) f0· · · fr−1(ordφr(P)H(Q) + ordφr(Q)H(P)), where H(P), H(Q) are the total heights of the finite parts respectively of N− r(P), N− r(Q). Lemma 4.2. Let P(x), P 0(x), Q(x)∈ O[x]be monic polynomials. (1) Rest(P, Q) = 0 if and only if ωr(P)ωr(Q)=0, (2) Rest(P, Q)<∞if and only if ordφr(P) ordφr(Q)=0, (3) Rest(P, Q) = Rest(Q, P), (4) Rest(PP0, Q) = Rest(P, Q) + Rest(P0, Q). Proof. The three first items are an immediate consequence of the definition. Item 4 follows from N− r(PP0) = N− r(P) + N− r(P0).  In the simplest case when N− r(P) and N− r(Q) are both one-sided, Rest(P, Q) represents the area of the rectangle joining the two triangles determined by the sides, if they are ordered by increasing slope. The reader may figure out a similar geometrical interpretation of Rest(P, Q) in the general case, as the area of a union of rectangles below the Newton polygon N− r(PQ) = N− r(P) + N− r(Q). • • • Q Q Q Q Q S S S S S S Q Q Q Q Q S S S S S S N− r(P) N− r(Q) Rest(P, Q) Our aim is to compute v(Res(P, Q)) as a sum of several Rest(P, Q) for an adequate choice of the types t. To this end, we want to compare types attached to P and Q, and this is uneasy because in the definition of the sets tr(P), tr(Q), we had freedom in the choices of the different representatives φi(x). For commodity in the exposition, we shall assume in this section that these polynomials are universally fixed. Convention. We fix from now on a monic lift φ1(x)∈ O[x]of every monic irreducible polynomial ψ0(y)∈F[y]. We proceed now recursively: for any 1≤i<r and any type of order i t= (φ1(x); λ1, φ2(x); · · · ;λi−1, φi(x); λi, ψi(y)), with φ1(x), . . . , φi(x)belonging to the (infinite) family of previously chosen polynomials, we fix a representative φi+1(x)of tsuch that Ri(φi+1) = ψi(y). Also, we assume from now on that all types are made up only with our chosen polynomials φi(x). NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 41 Once these choices are made, the set tr(P) is uniquely determined by rand P(x). More precisely, tr(P) is the set of all types of order rsuch that ωt r+1(P)>0 and the truncation tr−1is not P-complete; in other words, tr(P) = {ttype of order rsuch that ωt r+1(P)>0, ωt r(P)>1}. However, in view of the computation of resultants, we need a broader concept of “type attached to a polynomial”. Definition 4.3. For any monic polynomial P(x)∈ O[x], and any natural number r≥1, we define ˆ tr(P) := {ttype of order rsuch that ωt r+1(P)>0} ⊇ tr(P). The following observation is a consequence of the fact that ωt r+1 is a semigroup homomorphism for every type tof order r. Lemma 4.4. For any two monic polynomials P(x), Q(x)∈ O[x], we have ˆ tr(PQ) = ˆ tr(P)∪ˆ tr(Q). Note that the analogous statement for the sets tr(P) is false. For instance, let P(x), Q(x) be two monic polynomials congruent to the same irreducible polynomial ψ(y) modulo m. We have t0(P) = t0(Q) = {ψ(y)}=t0(PQ), and the type of order zero ψ(y) is P-complete and Q-complete; thus, t1(P) = ∅=t1(Q). However, ψ(y) is not PQ-complete, and t1(PQ)6=∅. We could also build the set ˆ tr(P) in a constructive way analogous to that used in the last section to construct tr(P). The only difference is that the P-complete types are expanded to produce types of order r+ 1 as well. Thanks to our above convention about fixing a universal family of representatives of the types, these expansions are unique. Lemma 4.5. Let r≥1be a natural number. Let P(x)∈ O[x]be a monic polynomial, P(x)6=φr(x). Let tbe a P-complete type of order r−1. Then, Nr(P) is one-sided of length one, and Rλr(P)(y)has degree one, where λr∈Q−is the slope of Nr(P). Moreover, let ψr(y)be the monic polynomial determined by Rλr(P)(y)≈ψr(y). Then, the type t0= (˜ t;λr, ψr(y)) is P-complete, and it is the unique type of order rsuch that t0 r−1=tand ωt0 r+1(P)>0. Proof. By Lemma 2.18 and Corollary 2.19, Nr(P) is one-sided of length one, and deg Rλr(P)(y) = d(Nr(P)) = 1. Clearly, ωt0 r+1(P) = 1. Finally, ωt00 r+1(P) = 0 for any t00 = (˜ t;λ0 r, ψ0 r(y)) 6=t0. In fact, if λ0 r6=λr, then Rλ0 r(P) is a constant; if λ0 r=λr, but ψr(y)6=ψ0 r(y) then ψ0 r(y) cannot divide Rλr(P)(y).  Corollary 4.6. Let P(x)∈ O[x]be a monic polynomial of positive degree. Then, ˆ tr(P) = ∅if and only if all irreducible factors of P(x)belong to {φ1(x), . . . , φr(x)}. Proof. By Lemma 4.4, we can assume that P(x) is irreducible. Since ˆ t0(P)6=∅, by the above lemma, ˆ tr(P)6=∅as long as P(x)6=φi(x) for i= 1, . . . , r. On the other hand, Nr(φr) is one-sided of slope −∞; hence, Rλr(φr) is a constant for every λr∈Q−, and ωt0 r+1(φr) = 0, for every type t0of order ≥r. By the Theorems of the polygon and of the residual polynomial, if P(x) is irreducible and P(x)6=φi(x) for i= 1, . . . , r, then |ˆ tr(P)|= 1. 48 GU` ARDIA, MONTES, AND NART If v(a) = 2 and v(c+ 2a+ 12) = 4, N3(f) is one-sided with slope λ3=−1, and R3(f)(y) = y2+y+1. The type t00 := (x;−1/2, φ2(x); −1, φ3(x); −1, y2+y+1) is fcomplete and t3(f) = {t00}. We have e3= 1, f3= 2. Thus, f(x) is irreducible over Z2[x], and it generates an extension L/Q2with e(L/Q2) = e1e2e3= 2, f(L/Q2) = f0f1f2f3= 2. Also, ind3(f) = 1, so that ind(f) = ind1(f) + ind2(f) + ind3(f) = 4. If v(a) = 2 and v(c+ 2a+ 12) ≥5, N3(f) has two sides with slopes λ3≤ −2, λ0 3=−1, and Rλ3(f)(y) = Rλ0 3(f)(y) = y+ 1. There are two types extending t0: t00 1:= (x;−1/2, φ2(x); −1, φ3(x); λ3, y + 1), t00 2:= (x;−1/2, φ2(x); −1, φ3(x); −1, y + 1). Both types have e3=f3= 1, they are both f-complete and t3(f) = {t00 1,t00 2}. Thus, f(x) has two irreducible factors of degree two over Z2[x], and both generate extensions L/Q2with e(L/Q2) = 2, f(L/Q2) = 1. Finally, ind3(f) = 1, so that ind(f) = ind1(f) + ind2(f) + ind3(f) = 4. In the final design of Montes’ algorithm, this polynomial f(x) is factorized already in order two. In the case v(c+ 2a+ 4) = 3 the algorithm considers φ3(x) = x2−2x−2 as a different representative of the type t, in order to avoid the increase of recursivity caused by the work in a higher order. See [GMN08a] for more details on this optimization. 4.4. Proof of the Theorem of the index. Our first aim is to prove Theorem 4.18 for f(x)∈ O[x] a monic irreducible polynomial of degree n, such that tr−1(f) is non-empty, say tr−1(f) = {t}, and f(x) is not equal to the representative φr(x) of t. Let t= (φ1(x); · · · , φr−1(x); λr−1, ψr−1(y)). For 1 ≤s≤r, let Es, Hs, dsbe the length, height and degree of the unique side of Ns(f). Note that Es>0 (because f(x) is of type t), and 0 < Hs<∞(because f(x) = φs(x) implies ts(f) = ∅, and f(x) = φr(x) is excluded by hypothesis). Let λr=−hr/erbe the slope of Nr(f), where hr, erare positive coprime integers. By the Theorem of the residual polynomial, Rλr(f)≈ψr(y)ar, for some monic irreducible polynomial ψr(y). Let fr:= deg ψr. Let θ∈Qpa root of P(x), L=K(θ), and let us fix an embedding (34). Denote zr=γr(θ). We introduce now some other notations. νs:= v(φs(θ)) = Ps i=1 eifi· · · es−1fs−1 hi e1. . . ei ,for all 1 ≤s≤r, νj:= j1ν1+· · · +jrνr∈Q,for all j= (j0, . . . , jr)∈Nr+1, Φ(j) := θj0φ1(θ)j1. . . φr(θ)jr πbνjc∈ OL,for all j= (j0, . . . , jr)∈Nr+1, b0:= f0;bs:= esfs,for 1 ≤s<r;br:= erfrar, J={j∈Nr+1 |0≤js< bs,0≤s≤r}. Lemma 4.20. Let O0 Lbe the sub-O-module of OLgenerated by {Φ(j)|j∈J}. Then, (1) O0 Lis a free O-module of rank n, with basis {Φ(j)|j∈J}, (2) O[θ]⊆ O0 L, and (O0 L:O[θ]) = qPj∈Jbνjc. Proof. Clearly, |J|=n, and the numerators of Φ(j), for j∈J, are monic polynomials of degree 0,1, . . . , n −1. Thus, the family {Φ(j)|j∈J}is O-linearly NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 49 independent. This proves item 1 and O[θ]⊆Z0 L. Finally, O0 L/O[θ]≃Y j∈J π−bνjcO/O ≃ Y j∈J O/πbνjcO, and since |O/πaO| =qa, we get (O0 L:O[θ]) = qPj∈Jbνjc. Our next step is to prove that O0 Lis actually an order of OL. To this end we need a couple of auxiliary results. Lemma 4.21. Let Q(x) = Pj=(j0,...,jr−1,0)∈Jajxj0φ1(x)j1. . . φr−1(x)jr−1, for some aj∈ O. Then, for all j= (j0, . . . , jr−1,0) ∈J, v(aj) + νj≥v(Q(θ)). Proof. Since deg Q<mr, we have v(Q(θ)) = vr(Q)/e1· · · er−1by Lemma 2.5 and Proposition 2.10. Let us prove v(aj)+νj≥vr(Q)/e1· · · er−1by induction on r≥1. If r= 1 this is obvious because v1(Q) = min{v(aj)}. Let r≥2 and suppose the result is true for r−1. For each 0 ≤jr−1< br−1, consider the polynomial Qjr−1(x) = X (j0,...,jr−2,0,0)∈J ajxj0φ1(x)j1. . . φr−2(x)jr−2, where j= (j0, . . . , jr−2, jr−1,0) in each summand. Clearly, Q(x) = X 0≤jr−1<br−1 Qjr−1(x)φr−1(x)jr−1, is the φr−1-adic development of Q(x). By item 4 of Proposition 2.8, the Theorem of the polygon and the induction hypothesis we get vr(Q)/er−1= min 0≤jr−1<br−1 {vr−1(Qjr−1) + jr−1(vr−1(φr−1) + |λr−1|)} = min 0≤jr−1<br−1 {vr−1(Qjr−1) + jr−1e1· · · er−2νr−1} ≤e1· · · er−2(v(aj) + j1ν1+· · · +jr−2νr−2+jr−1νr−1).  Lemma 4.22. Let j= (j0, . . . , jr)∈Nr+1. (1) For all 0≤s < r, Φ(j0, . . . , js−1, js+bs, js+1, . . . , jr) = πδj,s Φ(j0, . . . , js, js+1 + 1, js+2, . . . , jr) +X j0=(j0 0,...,j0 s,0,...,0)∈J cj,j0Φ(j+j0), for some nonnegative integer δj,s and some cj,j0∈ O. (2) Φ(j0, . . . , jr−1, jr+br) = Pj0∈Jcj,j0Φ(j+j0), for some cj,j0∈ O. Proof. Let 0 ≤s < r. The polynomial Q(x) = φs(x)bs−φs+1(x) has degree less than ms+1 =bsms; hence, it admits a development Q(x) = X j0=(j0 0,...,j0 s,0,...,0)∈J aj0xj0 0φ1(x)j0 1. . . φs(x)j0 s, for some aj0∈ O. If we substitute φs(x)bs=φs+1(x) + Q(x) in Φ(j0, . . . , js−1, js+ bs, js+1, . . . , jr) we get the identity of item 1, with δj,s =bνj+νs+1c−bνj+bsνsc, cj,j0=aj0πbνj+νj0c−bνj+bsνsc. 50 GU` ARDIA, MONTES, AND NART The Theorem of the polygon and the usual relationships vs+1(φs+1) = bsvs+1(φs) = bs(esvs(φs) + hs) (cf. Proposition 2.8 and (13)), show that νs+1 > bsνs. Therefore, v(Q(θ)) = bsνs, and by the above lemma we have v(aj0) + νj0≥bsνs. This shows that δj,s ≥0 and v(cj,j0)≥0. Item 2 follows by identical arguments, starting with Q(x) = φr(x)br−f(x).  Proposition 4.23. The O-module O0 Lis a subring of OL. Proof. For all j,j0∈Jwe have Φ(j)Φ(j0) = πδΦ(j+j0), with δ=bνj+νj0c−bνjc − bνj0c∈{0,1}. Thus, it is sufficient to check that Φ(j)∈ O0 L, for all j∈Nr+1. For any 0 ≤s≤r+1, let Js:= {j= (j0, . . . , jr)∈Nr+1 |0≤jt< bt,for t≥s}. Note that J0=J,Jr+1 =Nr+1. Consider the condition (is) Φ(j)∈ O0 L,for all j∈Js. By the definition of O0 L, the condition (i0) holds, and our aim is to show that (ir+1) holds. Thus, it is sufficient to show that (is) implies (is+1), for all 0 ≤s≤r. Let us prove this implication by induction on js. Take j0= (j0, . . . , jr)∈Js+1. If 0 ≤js< bs, condition (is+1) holds for j0. Let js≥bsand suppose that Φ(j0 0, . . . , j0 s−1, j, j0 s+1, . . . , j0 r)∈ O0 L, for all j0 0, . . . , j0 s−1∈N, all 0 ≤j < js, and all 0≤j0 t< bt, for t>s. By item 2 of the last lemma, applied to j= (j0, . . . , js−1, js−bs,0,...,0): (39) Φ(j0, . . . , js−1, js−bs,0,...,0, br) = X j0∈J cj,j0Φ(j+j0), if s<r, and Φ(j0, . . . , jr) = Pj0∈Jcj,j0Φ(j+j0), if s=r. In both cases, the terms Φ(j+j0) belong to O0 L, because the s-th coordinate of j+j0is js−bs+j0 s< js. In particular, if s=rwe are done. If s < r we apply item 1 of the last lemma to j= (j0, . . . , js−1, js−bs, js+1, . . . , jr) and we get Φ(j0) = πδj,s Φ(j0, . . . , js−bs, js+1 +1, js+2, . . . , jr)+ X j0=(j0 0,...,j0 s,0,...,0)∈J cj,j0Φ(j+j0). The last sum belongs to O0 Lby the same argument as above. Thus, we need only to show that the term Φ(j0, . . . , js−bs, js+1 + 1, js+2, . . . , jr) belongs to O0 Ltoo. If s=r−1 this is clear by (39). If s<r−1, it is also clear if js+1 + 1 < bs+1. Finally, if s<r−1 and js+1 + 1 = bs+1, we can apply item 1 of the last lemma again to see that it is sufficient to check that Φ(j0, . . . , js−bs,0, js+2 + 1, . . . , jr) belongs to O0 L. In this iterative process we conclude either by (39), or because we find some jt+ 1 < bt. We need still some auxiliary lemmas. The first one is an easy remark about integral parts. Lemma 4.24. For all x∈Rand e∈Z>0, we have P0≤k<e jx+k ek=bxc. Proof. The identity is obvious when xis an integer, 0 ≤x<e, because jx+k ek= 1 for the xvalues of ksuch that e−x≤k < e, and it is zero otherwise. Write x=n+, with n=bxcand 0 ≤ < 1; clearly, b(x+k)/ec=b(n+k)/ec, because /e < 1/e. Consider the division with remainder, n=Qe +r, with NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 51 0≤r < e. Then, X 0≤k<e jn+k ek=X 0≤k<e Q+jr+k ek=eQ +r=n.  Lemma 4.25. Take e0= 1,h0= 0 by convention. Every j∈Nr+1 can be written in a unique way: j=j0+j00, with j0,j00 belonging respectively to the two sets: J0:= {j0= (j0 0, . . . , j0 r)∈Nr+1 |0≤j0 s< es,for all 0≤s≤r} ⊆ J, J00 := {j00 = (j00 0, . . . , j00 r)∈Nr+1 |j00 s≡0 (mod es),for all 0≤s≤r}. Then, for any j00 = (k0, e1k1, . . . , erkr)∈J00, there is a unique j0= (j0 0, . . . , j0 r)∈J0 such that v(Φ(j0+j00)) = 0. Moreover, j0 r= 0, and j0 sdepends only on ks+1, . . . , kr, for 0≤s < r. Proof. For any j∈Nr+1 denote by λjthe positive integer λj:= e1· · · erνj= r X i=1 r X t=i jteifi· · · et−1ft−1!ei+1 · · · erhi. Clearly, (40) v(Φ(j)) = νj− bνjc=λj e1· · · er −jλj e1· · · erk. Thus, we are interested in the elements j∈Nr+1 such that λj≡0 (mod e1· · · er). Define now, for each 0 ≤s≤r, λj,s := jshses+1 · · · er+ r X i=s+1 r X t=i jteifi· · · et−1ft−1!ei+1 · · · erhi. Note that λj,s depends only on js, . . . , jr, and λj,0=λj,λj,r =jrhr. Clearly, λj,s −λj,s+1 =jshses+1 · · · er+ r X t=s+2 jtes+1fs+1 · · · et−1ft−1!es+2 · · · erhs+1, for all 0 ≤s≤r. In particular, λj,s ≡λj,s+1 (mod es+1 · · · er), and λj≡0 (mod e1· · · er)⇐⇒ λj,s ≡0 (mod es· · · er),for all 1 ≤s≤r. The condition λj,r ≡0 (mod er) is equivalent to jr≡0 (mod er). On the other hand, for 1 ≤s < r, the condition λj,s ≡0 (mod es· · · er) is equivalent to λj,s+1 ≡0 (mod es+1 · · · er),and jshs+Pr t=s+2 jt(fs+1 · · · ft−1)(es+2 · · · et−1)hs+1 +λj,s+1 es+1 · · · er ≡0 (mod es). Thus, the class of jsmodulo esis uniquely determined, and it depends only on js+1, . . . , jr. Corollary 4.26. Let κ= (k0, . . . , kr)∈Nr+1, and let j=j0+ (k0, e1k1, . . . , erkr), where j0is the unique element in J0such that v(Φ(j)) = 0. Then, Φ(j) = γ0(θ)k0· · · γr(θ)krγ1(θ)i1· · · γr−1(θ)ir−1, for some integers i1, . . . , ir−1. Moreover, each isdepends only on ks+1, . . . , kr. 52 GU` ARDIA, MONTES, AND NART Proof. By Lemma 4.25, j= (k0, j0 1+e1k1, . . . , j0 r−1+er−1kr−1, erkr). By (14), γs(θ)ks=πns,0φ1(θ)ns,1· · · φs(θ)esks, for all 1 ≤s≤r, with integers ns,i that depend only on ks. Hence, Φ(j)γ0(θ)−k0· · · γr(θ)−kr=πn0φ1(θ)n1· · · φr−1(θ)nr−1, for integers nsthat depend only on j0 sand ks+1, . . . , kr; hence they depend only on ks+1, . . . , kr. By Lemma 3.4, v(πn0φ1(θ)n1· · · φr−1(θ)nr−1) = 0, and by Propositions 2.10 and 2.16 we have vr(πn0φ1(x)n1· · · φr−1(x)nr−1) = 0. By Lemma 2.17, this rational function can be expressed as a product γ1(x)i1· · · γr−1(x)ir−1, with integers i1, . . . , ir−1such that each isdepends only on ns, . . . , nr−1, that is, on ks+1, . . . , kr. Corollary 4.27. Let j1=j0 1+j00,j2=j0 2+j00, for some j0 1,j0 2∈J0,j00 ∈J00. Then, v(Φ(j1)) = v(Φ(j2)) if and only if j1=j2. In particular, {v(Φ(j)) |j∈J0}={k/e1· · · er|0≤k < e1· · · er}. Proof. Let j1= (j1,0,...j1,r), j2= (j2,0,...j2,r). With the above notations, v(Φ(j1)) = v(Φ(j2)) ⇐⇒ λj1≡λj2(mod e1· · · er) ⇐⇒ λj1,s ≡λj2,s (mod es· · · er),for all 1 ≤s≤r. For s=rthis is equivalent to j1,r =j2,r. By a recursive argument analogous to the one used in the proof of the lemma, once we know that j1,t =j2,t for all t>s, then λj1,s ≡λj2,s (mod es· · · er) is equivalent to j1,s =j2,s. Finally, it is clear that |J0|=e1· · · er, and we have just shown that the elements v(Φ(j)), j∈J0, take e1· · · erdifferent values, all of them contained in the set {k/e1· · · er|0≤k < e1· · · er}by (40).  Proposition 4.28. Let f(x)∈ O[x]be a monic irreducible polynomial such that tr−1(f) = {t}. Let λrbe the slope of Nr(f), and suppose that Rλr(y)is a separable polynomial. Then, O0 L=OL. Moreover, the family of all Φ(j)Φ(j0), for j∈J0:= {j∈J|v(Φ(j)) = 0}and j0∈J0is an O-basis of OL. Proof. We have ar= 1 by hypothesis, and Corollary 3.8 shows that e(L/K) = e1· · · er,f(L/K) = f0f1· · · fr. By Corollary 4.27, we have {vL(Φ(j)) |j∈J0}= {0,1, . . . , e(L/K)−1}. By Lemma 4.25, |J0|=f0f1· · · fr= dimFKFL, and each j∈ J0is parameterized by a sequence (k0, . . . , kr), with 0 ≤ks< fsfor all 0 ≤s≤r. By item 4 of Proposition 3.5, FL=FK(γ0(θ), . . . , γr(θ)), where γ0(x) := x. Recall that zi=γi(θ) for all 0 ≤i≤r, under our identification of Fr+1 := Fr[y]/ψr(y) with FL. By Corollary 4.26, Φ(j) = zk0 0zk1+i1 1· · · (zr−1)kr−1+ir−1zkr r=zk0 0zk1 1Γ2(k2, . . . , kr)· · · Γr(kr), where Γs(ks, . . . , kr) = zks s(zs−1)is−1, for s≥2. Now, the family of all Φ(j) for j∈J0is an FK-basis of FL. In fact, the set of all Γr(kr) for 0 ≤kr< fr, is aFr-basis of FL=Fr+1, because they are obtained from the basis zkr r, just by multyplying every element by the nonzero scalar zir−1 r−1∈Fr, which depends only on kr. Then, the set of all Γr−1(kr−1, kr)Γr(kr) for 0 ≤kr−1< fr−1, 0 ≤kr< fr, is aFr−1-basis of Fr, because they are obtained from the basis (zr−1)kr−1Γr(kr), just by multyplying every element by the nonzero scalar zir−2 r−2∈Fr−1, which depends only on kr−1, kr, etc. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 53 Therefore, the e(L/K)f(L/K) elements Φ(j)Φ(j0), j∈J0,j0∈J0, are a O-basis of OL. By Proposition 4.23, all these elements are contained in O0 L, and we have necessarily O0 L=OL. Proof of the Theorem of the index. Suppose first that f(x)∈ O[x] is a monic irreducible polynomial, such that tr−1(f) = {t}, and f(x)6=φr(x). In this case we have built an order O[θ]⊆ O0 L⊆ OL, and we have (41) (OL:O[θ]) = qind(f),(O0 L:O[θ]) = qPj∈Jbνjc, the last equality by Lemma 4.20. Therefore, in order to prove item 1 of Theorem 4.18 it is sufficient to show that (42) f0X j=(0,j1,...,jr)∈J bνjc= ind1(f) + · · · + indr(f). Let us prove this identity by induction on r≥1. For r= 1 this was proved already in (38). From now on, let r≥2. Both sides of the identity depend only on arand the vectors e= (e1, . . . , er), f= (f1, . . . , fr−1), h= (h1, . . . , hr). Recall that νs=νs(e,f,h) := s X i=1 eifi· · · es−1fs−1 hi e1. . . ei . If we denote e0= (e2, . . . , er), f0= (f2, . . . , fr−1), h0= (h2, . . . , hr), it is easy to check that, for every 2 ≤s≤r: (43) νs(e,f,h)−ms m2 f1h1=1 e1 νs−1(e0,f0,h0). Let us show that the identity f0X j=(0,j1,...,jr)∈Jjr X s=1 jsνs(e,f,h)k= ind1(f) + · · · + indr(f), holds for any choice of arand e,f,h, under the assumption that this is true for r−1. Write j1=je1+k, with 0 ≤j < f1, 0 ≤k < e1, and let 0 ≤sk< e1be determined by kh1≡sk(mod e−1). Then, by (43), jr X s=1 jsνs(e,f,h)k=jjh1+kh1 e1 + r X s=2 jsνs(e,f,h)k= = r X s=2 js ms m2 f1h1+jh1+jkh1 e1 + r X s=2 jsνs(e,f,h)−ms m2 f1h1k= = r X s=2 js ms m2 f1h1+jh1+jkh1 e1 +1 e1 r X s=2 jsνs−1(e0,f0,h0)k= = r X s=2 js ms m2 f1h1+jh1+jkh1 e1k+jsk e1 +1 e1 r−1 X s=1 js+1νs(e0,f0,h0)k. Therefore, it is sufficient to check the two identities: f0X (0,0, j2,...,jr)∈J 0≤j < f1,0≤k < e1 r X s=2 js ms m2 f1h1+jh1+jkh1 e1k!= ind1(f), 54 GU` ARDIA, MONTES, AND NART f0X (0,0, j2,...,jr)∈J 0≤j < f1,0≤k < e1 jsk e1 +1 e1 r−1 X s=1 js+1νs(e0,f0,h0)k= ind2(f) + · · · + indr(f). The left-hand side of the first identity is equal to f0P0≤i<e1f1a1bih1 e1c. Hence, it has been proved in (38). The second identity follows from the induction hypothesis. In fact, the set {sk|0≤k < e1}coincides with {0,1, . . . , e1−1}, and by Lemma 4.24 the left-hand side of the identity is equal to f0f1X (0,0,j2,...,jr)∈Jjr−1 X s=1 js+1νs(e0,f0,h0)k. Let us prove now the second part of the theorem. If ind(f) = ind1(f) + · · · + indr(f), then indr+1(f) = 0 by item 1 of the theorem in order r+ 1. Conversely, if indr+1(f) = 0, then Lemma 4.16 shows that tr+2(f) = ∅, and by Lemma 3.11, for all t0∈tr(f) and all λr+1, the residual polynomial Rt0,λr+1 (f)(y) is separable. If tis f-complete, we have ar= 1 by Lemma 4.5, and O0 L=OLby Proposition 4.28. By (41) and (42), we get ind(f) = ind1(f)+· · ·+indr(f). If tis not f-complete then tr(f) = {t0}for some type t0of order r. By Proposition 4.28 applied to t0in order r, we get ind(f) = ind1(f) + · · · + indr(f) + indr+1(f) by the same argument in order r. Since indr+1(f) = 0, we have ind(f) = ind1(f) + · · · + indr(f), as desired. This ends the proof of the theorem in the particular case we were dealing with. Let us prove now the theorem in the other instances where f(x) is irreducible. If f(x) = φr(x) we have indr(f) = 0; in this case we can apply the theorem in order r−1, since f(x)6=φr−1(x) and tr−2(f) = {tr−2}is non-empty. Thus, ind(f) = ind1(f)+ · · · +indr−1(f). Finally, suppose that tr−1(f) = ∅and let s < r be maximal with the property ts−1(f)6=∅. We can apply the theorem in order s, and since ts(f) = ∅we have inds+1(f) = 0 and ind(f) = ind1(f) + · · · + inds(f). Since indt(f) = 0 for all t>s, this proves both statements of the theorem. This ends the proof of the theorem when f(x) is irreducible. In the general case, if f(x) = F1(x)· · · Fk(x) is the factorization of f(x) into a product of monic irreducible polynomials, we have by definition ind(f) = k X i=1 ind(Fi) + X 1≤i<j≤k v(Res(Fi, Fj)). By Lemma 4.17, an analogous relationship holds for every inds(f), 1 ≤s≤r. Hence, item 1 of the theorem holds by the theorem applied to each ind(Fi), and by Theorem 4.10. Let us prove now item 2. By Lemma 4.17, indr+1(f)=0 if and only if indr+1(Fi) = 0 and Resr+1(Fi, Fj) = 0, for all iand all j6=i. By the theorem in the irreducible case and Theorem 4.10, this is equivalent to ind(f) = ind1(f) + · · · + indr(f).  References [Bau07] M. Bauer, Zur allgemeinen Theorie der algebraischen Gr¨ossen, Journal f¨ur die reine und angewandte Mathematik 132(1907), pp. 21–32. [Ber27] W.E.H. Berwick, Integral Bases, Cambridge Tracts in Mathematics and Mathematical Physics, nbr. 22, Cambridge University Press, 1927. Repr. Stecher-Hafner, 1964. NEWTON POLYGONS OF HIGHER ORDER IN ALGEBRAIC NUMBER THEORY 55 [Coh95] H. Cohen, A Course in Computational Algebraic Number theory, Graduate Texts in Mathematics 138, Springer-Verlag 1995. [Ded78] R. Dedekind, ¨ Uber den Zusammenhang zwischen der Theorie der Ideale und der Theorie der h¨oheren Kongruenzen, Abhandlungen der K¨oniglichen Gesellschaft der Wissenschaften zu G¨ottingen 23(1878), pp. 1–23. [Gua97] J. Gu`ardia, , Geometria aritm`etica en una fam´ılia de corbes de g`enere tres, Tesi Doctoral, Universitat de Barcelona 1997. [GMN08a] J. Gu`ardia, J. Montes, E. Nart, Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields, in preparation. [GMN08b] J. Gu`ardia, J. Montes, E. Nart, Higher Newton polygons and integral bases, in preparation. [Mon99] J. Montes, Pol´ıgonos de Newton de orden superior y aplicaciones aritm´eticas, Tesi Doctoral, Universitat de Barcelona 1999. [McL36a] S. MacLane, A construction for absolute values in polynomial rings, Transactions of the American Mathematical Society, 40(1936), pp. 363–395. [McL36b] S. MacLane, A construction for prime ideals as absolute values of an algebraic field, Duke Mathematical Journal 2(1936), pp. 492–510. [Ore23] Ø. Ore, Zur Theorie der algebraischen K¨orper, Acta Mathematica 44(1923), pp. 219–314. [Ore24] Ø. Ore, Weitere Untersuchungen zur Theorie der algebraischen K¨orper, Acta Mathematica 45(1924-25), pp. 145–160. [Ore25] Ø. Ore, Bestimmung der Diskriminanten algebraischer K¨orper, Acta Mathematica 45(1925), pp. 303–344. [Ore26] Ø. Ore, ¨ Uber den Zusammenhang zwischen den definierenden Gleichungen und der Idealtheorie in algebraischen K¨orpern, Mathematische Annalen 96(1926), pp. 313–352. [Ore28] Ø. Ore, Newtonsche Polygone in der Theorie der algebraischen K¨orper, Mathematische Annalen 99(1928), pp. 84–117. Departament de Matem` atica Aplicada IV, Escola Polit` ecnica Superior d’Enginyera de Vilanova i la Geltr´ u, Av. V´ ıctor Balaguer s/n. E-08800 Vilanova i la Geltr´ u, Spain E-mail address:[email protected] Departament de Ci` encies Econ` omiques i Socials, Facultat de Ci` encies Socials, Universitat Abat Oliba CEU, Bellesguard 30, E-08022 Barcelona, Spain E-mail address:[email protected] Departament de Matem` atiques, Universitat Aut` onoma de Barcelona, Edifici C, E08193 Bellaterra, Barcelona, Spain. E-mail address:[email protected]