Approximate contact factorization of germs of plane curves Joris van der Hoevena, Grégoire Lecerfb CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) Bâtiment Alan Turing, CS35003 1, rue Honoré d'Estienne d'Orves 91120 Palaiseau, France a. Email: vdhoeven@lix.polytechnique.fr b. Email: lecerf@lix.polytechnique.fr Preliminary version of November 4, 2023

1.Introduction

1.1.Motivation

Algebraic curves play a central role in algebraic geometry and various applications in effective algebra. In particular, efficient algorithms are needed to compute topological or analytic invariants, arithmetic genus, desingularized models, integral closures, Riemann–Roch spaces, etc. Usual applications in computer algebra concern the irreducible factorization of multivariate polynomials, the integration of rational functions, the construction of algebraic geometry error correcting codes, the bi-linear complexity of polynomial multiplication, etc. In the present paper, we are interested in computing the irreducible factorization of any given polynomial , where denotes an effective field. Here “effective” means that algorithms are at our disposal for the arithmetic operations and the zero test in .

Let denote the fraction field of of Laurent series in . The field

of power series with fractional exponents is called the field of Puiseux series (or Puiseux expansions) over . Let denote the algebraic closure of . If has characteristic zero, then is the algebraic closure of . In other words, any polynomial in splits into linear factors in .

Computations of Puiseux expansions of roots of go back to Newton [62], and were rediscovered by Puiseux [75]; see [5, p. 198] and [82, 86]. The well known Newton polygon method turns out to be effective whenever is effective. When adopting a suitable algebraic complexity model (in which running times are measured in terms of the required number of arithmetic operations in or ), the complexity is easily seen to be polynomial in the degree of and in the required precision. However, at present time, we are not aware of an algorithm with a softly linear cost for any precision (especially below the valuation of discriminant of ).

For the design of such a quasi-optimal algorithm, it is important to carefully state the problem that needs to be solved. In particular, one has to pay attention to the ways in which algebraic numbers and fractional power series are represented. It turns out that the computation of Puiseux expansions is closely related to the computation of irreducible factorizations in and that representation issues are more straightforward for the latter problem.

In this paper, we therefore focus on the computation of irreducible factorizations. Our main goal is the design of an efficient algorithm for factoring a polynomial that is given modulo for a finite precision , assuming that we already have an algorithm for decomposing polynomials in into irreducible factors.

1.2.Notations and assumptions

For complexity analyses, we consider algebraic complexity models (such as computation trees). In other words we simply count numbers of arithmetic operations and zero tests in specified algebraic structures.

Until the end of the paper, is a fixed rational number that can be taken arbitrarily close to zero. For complexity estimates we often use the soft-Oh notation: means that ; see [26, chapter 25, section 7] for technical details. The least integer larger or equal to is written ; the largest one smaller or equal to is written .

For randomized algorithms over a finite effective ring , we assume a special instruction that uniformly generates random elements in with constant cost. For a given input, the cost of a randomized algorithm is thus a random variable. The expected cost for input size is defined as the maximum of the averages of these random variables over all possible inputs of size .

For a finite field of characteristic and with elements, the usual primitive element representation will be used, so elements in will be regarded in where is an irreducible polynomial of degree .

Polynomials

We use as a notation for the cost of multiplying two polynomials of degree , in terms of the number of operations in the coefficient ring. We assume that is a non-decreasing function in . It is known [11, 77] that one can take . For rings of positive characteristic, one even has , modulo a plausible number-theoretic conjecture [34]. We will also denote

Algebraic towers

A tower of algebraic extensions of of height is a sequence with and

for a separable irreducible monic polynomial and . We set

Products and inversions in take operations in . This was first proved in [45] in the case when is a field and . The result was extended to more general algebraic towers in [46]. Whenever , we may work in an algebraic extension of degree such that . The computation of such an extension can be done using operations in the prime subfield of , thanks to [79, Theorem 4.1]. For a fixed field , this can be regarded as a precomputation, whereas computations with elements in instead of induce only a logarithmic overhead .

Factorization

We define to be an upper bound for the cost (expected or not) of irreducible factorization of a polynomial in . It is convenient to introduce

so is a non-decreasing function in .

For example, if is the finite field , then a well known probabilistic algorithm due to Cantor and Zassenhaus [12] factors univariate polynomials in using an expected number of bit operations.

The currently best known algorithm is obtained as a combination of results due to von zur Gathen, Kaltofen and Shoup [27, 48, 49], and Kedlaya and Umans [51]: it takes an expected number of

bit operations; see [47, Corollary 5.1].

The case of a tower over (with the above notation) reduces to the case of by means of the fast change of representation of [70, Theorem 1.2], that applies whenever

(1.1)

In terms of bit complexity, and for a “random access memory” computational model, this yields

Details can be found in [47, Corollary 5.3]. Whenever condition (1.1) is satisfied, we may then use the expected bit complexity bound

When the tower has small degrees , optimized factorization procedures can be found in [44, 47, 48]. In particular, if is smooth, then polynomials of small degree can even be factored in quasi-optimal time. Note that these optimizations do not depend on Kedlaya–Umans' algorithm for modular composition.

For an abstract effective field , there does not exist a general algorithm to factor polynomials in into irreducible ones [24, 25]. Throughout this paper, we will therefore need to assume that such an algorithm is provided by the computational model:

K

Irreducible factorization in is available within the computational model.

In practice, this property holds whenever is effectively finitely generated over its prime subfield. Once factorization is available in , it is also available in , with a complexity that depends on those of resultants and gcds [81].

1.3.Related work

Let still denote an effective field, let be monic as a polynomial in , and assume that . So defines a germ of curve at the origin. In practice, we always truncate at a finite order in . For the discussion in the following paragraphs, we therefore take and assume that is monic, primitive, and separable in , of total degree , and of partial degrees in and in .

Puiseux expansions

If the characteristic of is zero or sufficiently large, then Puiseux expansions to any given precision can be computed in polynomial time when considering an algebraic complexity model over —this result belongs to the folklore.

Consider a Puiseux series that is a root of . The shortest truncation of this series which is different from any truncation of a distinct Puiseux series root of is called the singular part of . In 1978, Kung and Traub [52] showed that the Puiseux expansion of can be computed efficiently using Newton's method, once its singular part is known.

The complexity of the computation of singular parts started to be studied in the eighties. In [35], Henry and Merle showed that the embedded resolution of an irreducible germ of curve defined by at the origin can be computed with operations in . In [19], Duval introduced the notion of rational Puiseux expansions, that allowed computations over to be replaced by computations over . She adapted the usual Newton polygon algorithm to such a rational representation, and made use of dynamic evaluation to handle algebraic extensions without polynomial factorization. She achieved a total cost of operations in , whenever the characteristic is zero or sufficiently large. This analysis was based on slow arithmetic for polynomials and series.

In his PhD thesis [68], Poteaux showed that Duval's algorithm takes at most operations in in order to obtain all the singular parts of the Puiseux expansions. In [69], Poteaux and Rybowicz also proved that the singular parts of the rational Puiseux expansions centered at a single point can be computed using operations in , in the case when ; this bound relies on fast polynomial arithmetic. In [72], Poteaux and Weimann finally gave a probabilistic algorithm that allows singular parts to be computed with operations in , assuming that the characteristic of is zero or sufficiently large. This bound is quasi-optimal in worst cases, when we need order about before root separation takes place [72, Example 8.1]. Their algorithm makes use of dynamic evaluation and the singular parts are represented by truncations of rational Puiseux expansions. These algorithms by Poteaux et al. also extend efficiently to obtain the collection of all singular parts at each of the singularities of the algebraic curve defined by . As a byproduct, Poteaux and Weimann proved the expected complexity bound for the irreducible factors of at precision , still under the assumption that the characteristic of is ; see [72, Theorem 1.6].

When , a polynomial bit complexity for Puiseux series was first achieved by Chistov [13]. The complexity bound for this case was subsequently detailed and improved by Walsh [83, 84]. Since the complexity exponents are rather large, multi-modular approaches turn out to be of practical interest [68].

Once singular parts are known, we have already mentioned that Puiseux expansions can be extended by means of the Newton operator, as described in [52]; see also [39] for recent optimizations. For small and moderate expansion orders, it is often more efficient to use lazy or relaxed arithmetic to expand algebraic power series [38, 85]. For very large expansion orders, yet another method is to compute a differential operator that annihilates the expansions [15, 16]; see [8] for complexity bounds. It is also worth mentioning that individual terms of algebraic Puiseux series over a finite field can be computed even faster than with the Newton iteration [7].

Approximate roots

In positive characteristic, the field of Puiseux series no longer coincides with the algebraic closure of ; see for instance [50]. Hamburger–Noether expansions constitute a natural extension of Puiseux series in positive characteristic [9].

In his 1989 article [1], Abhyankar addressed a question from Kuo about an algorithm to decide the irreducibility of a germ of curve, without using blowups or Puiseux series. In characteristic zero, Abhyankar gave a positive answer to this question, by using expansions of the defining polynomial of the germ with respect to so-called approximate roots. These approximate roots can be determined recursively by means of a generalized Newton polygon, previously introduced in [2, 3]. They generalize Tschirnhaus transforms [80]. Complexity analyses can be found in [71, 73]: in favorable cases irreducibility tests take softly linear time (plus a justifiable amount of irreducibility tests in ).

Abhyankar's work has been completed and extended to arbitrary characteristic by Cossart and Moreno-Socías in [18], where they present an alternative construction based on valuation theory. The mathematical relationship between approximate roots, Puiseux expansions, and Hamburger–Noether expansions can be found in [73, 76].

Local factorizations

Whenever is a local ring different from , factorization in is a more difficult problem, for which Puiseux expansions cannot be used. The first interesting case is when is the field of the -adic numbers. Let be a monic primitive square-free polynomial in . A first series of contributions concern the Round Four algorithm due to Zassenhaus, and dedicated to the construction of integral bases modulo ; see [17, 21, 22] for instance. The first polynomial time algorithm for factoring over was given by Chistov [14], and then improved by Cantor and Gordon in [10].

After that, Pauli [67] designed a factorization algorithm over an algebraic extension of degree of with bit complexity

(1.2)

Since 1999, Montes has been designing different algorithms; his irreducibility test of [57] has been shown in [23] to have a complexity similar to (1.2).

The next improvements are due to Guàrdia, Montes, and Nart [29, 30]. They exploit previous ideas by MacLane and Okutsu in order to compute so-called OM factorizations (as a shorthand for “Okutsu–Montes factorizations”); see [61] for a survey. In [6], Bauch, Nart, and Stainsby proved the bit complexity bound

for an algebraic extension of degree of . Further refinements and applications, including the computation of integral closures, can be found in [20, 31, 32].

In [74] Poteaux and Weimann recently improved the latter complexity bound to

(discarding factorization costs in ) whenever : they made use of the natural “divide and conquer” extension of the generalized Hensel lifting of [33] and also applied the same “increase of precision” strategy as in [72].

Non-archimedean value groups

Various other generalizations of Puiseux expansions have been investigated by van der Hoeven, starting in 1997 with his PhD thesis [37]. First of all, he developed a framework for the resolution of algebraic equations over a field of generalized power series instead of . One natural example is to take , where is an effective subfield of another field of Laurent series . In this case, the underlying value group of becomes non-archimedean, and the issue arises how to conduct exact computations with truncated power series. This is easy if , but less trivial if contains transcendental power series such as , because of the required zero test. We refer to [41, 42] for some recent perspectives on this type of computations.

The resolution of algebraic equations over fields of generalized power series is still based on the Newton polygon method. However, the complexity can no longer be analyzed in terms of the truncation order in a non-archimedean context. Instead, one may consider the resolution of equations in Hensel position as a natural building block. In [37], van der Hoeven showed how to reduce the resolution of a general algebraic equation of degree to at most applications of Hensel's lemma. It would be interesting to analyze the complexity of this algorithm in the special cases that were considered above.

Non-archimedean value groups are not merely a theoretical curiosity. Until recently, effective counterparts of Hironaka's theory of standard bases for power series were only known in the case of algebraic power series [4, 58]. In [42], generalized Puiseux series have been put to develop elimination theories for more general power series, such as differentially algebraic power series. Non-archimedean value groups actually arise in a natural way when studying algebraic differential equations, and the Newton polygon method can be generalized to this context; see [5] for recent progress and further references.

1.4.Outline of the paper

The main purpose of this paper is to present a self-contained and quasi-optimal algorithm for approximate factorization over rings of formal power series. We show how to efficiently factor into irreducible polynomials, and for each irreducible factor we construct generators of the valuation group of in a form of a contact tower; see Definition 3.1. An irreducible factorization of modulo is a list of factors of modulo , along with their associated multiplicity and contact tower; see Definition 7.6. In particular the are irreducible, pairwise coprime, and we have

for some integers . The contact tower associated to allows the computation of the valuation in in softly linear time. The following main result will be proved at the end of section 8.2:

Theorem 1.1. Let be a fixed positive value, and assume K. Let be monic of degree in , known modulo , and such that the characteristic of is zero or . Then, an irreducible factorization of modulo can be computed using

operations in .

Example 1.2. Take , , and . Then , , and is an irreducible factorization of modulo . Taking , , , , we obtain another such factorization. This shows that approximate factorizations are not unique in general.

Note that the term is negligible with respect to as soon as the precision is sufficiently large. By using our approximate factorization algorithm with a sufficiently large precision, we deduce the following complexity bound for the actual irreducible factorization of ; see section 9.5.

Theorem 1.3. Let be a fixed positive value, and assume K. Let be monic and separable of degree in and known at precision in with . Assume that the characteristic of is zero or . Then, the irreducible factors of can be computed modulo using

operations in .

Theorem 1.3 considers as part of the input. This is not very restrictive in characteristic zero or thanks to [60, Theorem 1]. On the other hand, if belongs then can be computed with operations in . Theorem 1.3 can be regarded as a deterministic counterpart of [72, Theorem 1.6] and is also similar to [74, Theorem 4], although the underlying algorithms are notably different. Our proofs are elaborated from scratch by taking special care of the precisions and the cost of all factorizations in . We rely neither on Puiseux expansions (contrary to [72]), nor on OM factorizations, nor on approximate roots, nor on the “divide and conquer” strategy from [72, 74] on the precision. Instead, our algorithm is based on a natural cascade of factorizations driven by Newton polytopes and a new method to balance the depth of the recursive calls: namely our central shift algorithm of section 7.7. Note that approximate factorizations in the sense of Theorem 1.1 (especially below the valuation of the discriminant) are not assessed in [72, 74].

The algorithm behind Theorem 1.1 decomposes into several subtasks for which we design efficient solutions. The first subtask concerns the computation of so-called distinct-slope and equal-slope factorizations; see section 7. Distinct-slope factorizations separate the factors of according to the slopes of its Newton polygons. Equal-slope factorizations serve a similar purpose for polynomials with a single slope. We achieve these computations in softly linear time by means of a generalized Hensel lifting, as explained in section 4.

The contact factorization algorithm performs a cascade of distinct-slope and equal-slope factorizations over increasing contact towers. When the tree modeling the successive splittings of is not sufficiently well balanced, the total complexity moves away from quasi-linearity. Our central shift algorithm of section 7.7 circumvents this issue through tree-balancing. The top level algorithm is described in section 8.

Computing over contact towers involves two difficulties. First, as for towers of algebraic field extensions, we do not know how to perform arithmetic operations in softly linear time. We overcome this difficulty by doing most of the operations within the original ring using a sufficiently high precision. The second difficulty concerns zero tests and inversions in towers. In section 6, we introduce initial expansions, that can be computed fast thanks to accelerated tower arithmetic [45].

As said, the power series setting from this paper is simpler than the one of general local fields studied by Montes et al. Nevertheless, the main mathematical ideas are roughly the same and go back to the work of MacLane [55, 56] on augmented valuations: approximate roots, OM-factorizations, and contact towers share the same philosophy.

Compared to [55, 56], our contact towers represent a kind of a more general “augmented semi-valuations“. Approximate roots can indeed be regarded as special cases of contact towers but also of so-called “tipos” in [57]. Our contact factorization algorithm does not rely on approximate roots: as explained in section 8.3, such roots may be useful in practice, but it is a drawback that they are not preserved during factorizations. In fact, our new central shift strategy behaves as an algorithmic improvement with respect to approximate roots; see section 2.6. While MacLane, and later Montes, focused on constructing augmented (semi-)valuations over polynomial rings, our down-to-earth and self-contained approach begins with designing efficient data structures in the vein of triangular sets and Hironaka's standard bases [36]. In addition, let us mention that, compared to [74], our multi-factor Hensel lifting of section 4 is based on a faster multi-remaindering strategy.

We would also like to insist on our novel strategy for approximate factorizations, that is behind Theorem 1.1. Roughly speaking, the problem here is similar to approximate factorization in . The first quasi-optimal algorithms for the computation of the distinct roots were designed for the case when the required precision is sufficiently high [66, 78]; more recently, a different algorithm was proposed for small precisions [59]. Detailed comparisons between all known algorithms for local factorization would be too long and technical to be discussed here. Instead, we dedicate our next section to introductory examples that illustrate the computational difficulties that are common to all known approaches.

At the end of the paper, a glossary is dedicated to the specific mathematical notations, and an index gathers references to the main definitions.

2.Introductory examples

Before we give the formal definition of a contact factorization, we review a few motivating examples from the complexity perspective.

2.1.Graded rings and Newton polygons

Let be a totally ordered abelian group and let be a monoid embedded in . A graded ring with respect to the grading is a direct sum

where the are abelian groups such that for all and in . An element of is said to be homogeneous if it belongs to one of the . Any element in can be uniquely written , where is called the homogeneous component of degree of . If and , then we also denote

The initial form of a non-zero element , written , is the non-zero homogeneous component with the smallest index . By convention we set .

An ideal of is said to be homogeneous whenever it can be generated by homogeneous elements, or equivalently whenever the homogenous components of any element of also belong to .

To each non-zero element we may associate the smallest index such that ; we set . The map is a semi-valuation , which means that it satisfies and for all . Given , we call the truncation of at relative precision .

Figure 2.1. The Newton polygon of . Each dot represents a monomial in .

The Newton polygon of a non-zero polynomial

of degree is the lower border of the convex hull in of the set of points

Figure 2.1 illustrates this definition with and . The Newton polygon is thus a broken line with edges , with , such that:

• ,

• for ,

• , for all and with ,

• , for all and or with .

Intuitively speaking, these conditions mean that lies on or above the Newton polygon. If , then we have and . Any determines an edge with vertices and . The Newton polynomial associated to is

Whenever , the slope of is . The first slope is whenever . Two consecutive edges have different slopes.

2.2.Explicit solutions versus factorization

In order to illustrate computations in algebraic extensions of or , let us first consider applying the Newton polygon method to an input polynomial of the form

where is a monic separable irreducible polynomial of degree and has degree in . We then consider

(2.1)

as a polynomial equation in . The Newton polygon of consists of a single edge starting at and ending at ; its slope is .

Equation (2.1) has a solution in , where . Indeed, let be the class of in . Replacing by in (2.1), we obtain the new equivalent equation

(2.2)

The separability of implies , which allows us to apply Hensel's lemma: there exists a unique solution with valuation in . This is the point of view of factoring in terms of Puiseux expansions.

In terms of space complexity, we note that computations in typically require times more space than in . Fortunately, this is compensated by the fact that the “unique” solution to (2.2) actually describes all solutions to (2.1) in . Indeed, any solution in is obtained by substituting a root of for in the expression of .

From a time complexity point of view, the resolution of (2.2) can be done efficiently by using Newton's method. However, this involves truncated power series evaluations of expressions such as , where . These give in turn rise to modular compositions (with modulus ). Over general coefficient fields , no quasi-optimal algorithm (of complexity ) is currently known for this task, so it is preferable to avoid such operations whenever possible. In particular, it is better to avoid working over algebraic extensions of the field of coefficients.

In order to avoid modular compositions, one idea is to consider that equation (2.1) does not require any explicit resolution. In other words, it is already in such a simple form that we may essentially consider it as “solved”. More generally, later in this paper, we will consider an equation as “solved” if and only if the Newton polygon of with respect to suitable “contact coordinates” has a single slope for which the associated Newton polynomial is separable (and technically, irreducible).

The problem of solving a general equation with then reduces to the problem of factoring as a product of “solved” polynomials. From this perspective, expressing the solutions of as Puiseux series becomes a rewriting problem for “solved” polynomials, which is independent from the main resolution of the equation itself.

2.3.Contact coordinates

Consider the polynomial equation in over given by

(2.3)

When solving this equation by means of the Newton polygon method, we see that the Newton polygon of has a single slope with associated Newton polynomial

In other words, all solutions of (2.3) are of the form , where . Usually, the Newton polygon method proceeds by performing a change of variable

while imposing the constraint . So we are reduced to solving

The Newton polygon has two edges: and . Therefore and we have , so , where . We proceed with the change of variable

while imposing the constraint . So we are now led to solving

The unique value of can therefore be computed efficiently by means of the Newton iteration as a regular root of . However, this means that we have to work over the algebraic extension .

The idea behind contact calculus is to avoid computing over this type of algebraic extensions, by working with respect to so-called contact coordinates instead. In the present example, the idea is to rewrite (2.3) as

We next reinterpret this equation as

(2.4)

where and are two new variables that are subject to the following constraints:

• , ,

• and .

The variables and can be regarded as unknowns, with values in the ring of Puiseux series in . These unknowns satisfy the system of equations

In other words, computing Puiseux expansions of solutions to is equivalent to computing Puiseux expansions of solutions to the latter system. We note that is separable in and that the solutions for begin with . Then is separable in for each solution , so the system admits the following solutions:

After the change of variable , these solutions are regular roots of the following map modulo :

By means of the Newton iteration, these roots may be lifted efficiently to any required precision, and so may the corresponding solutions of .

The variables and are called contact coordinates. Note that

so the germ of the curve defined by approximates the one defined by . From a geometric point of view, the two germs are “in contact”.

Informally speaking, the Newton polygon of equation (2.4) in has a single edge of vertices and , with associated Newton polynomial , whence . The precise meaning of this “generalized Newton polygon” will be the purpose of section 7. Since the polynomial is separable in , we consider the polynomial to be “solved”.

Working with contact coordinates is a little bit tricky, since and are related by the equation . Basic arithmetic operations and the Newton polygon method therefore have to be adapted with care. It turns out that “contact calculus” with respect to contact coordinates has a double flavor. At small orders in , it boils down to working in towers of algebraic extensions of . At large orders in , we may convert between polynomials in and through the mechanism of -adic expansions.

In this paper, we have chosen to do most actual computations in , since fast algorithms for basic arithmetic operations in this ring are well known. However, conversions between the “plain coordinates” and the “contact coordinates” incur some precision loss. Fortunately, this precision loss can be controlled for the applications in this paper. Of course, it would be interesting to design a genuine fast arithmetic for contact coordinates without precision loss.

2.4.Towards general contact coordinates

Example (2.3) has several variants that motivate the general definition of contact coordinates in the next section. First of all, consider the equation

(2.5)

In that case, the contact coordinates would rather be and . This illustrates that we do not systematically take , although we always do have when working over .

Let us next consider the equation

(2.6)

In this case, we start with the same contact coordinates and as for (2.3), but also need to introduce a third one , subject to . In general, we may need to introduce as many as contact coordinates.

Yet another variant of (2.3) is the equation

(2.7)

We again use the same contact coordinates and as for (2.3), but this time rewrites into , that can be factored:

In general, these types of factorizations can be expensive to compute with respect to the original coordinates and become more transparent for the contact coordinates.

2.5.Tschirnhaus transforms and approximate roots

Let us first consider the equation

(2.8)

When solving this equation using the usual Newton polygon method, we find that there is a single slope , with , for which the associated Newton polynomial has a single root of multiplicity . This means that the leading terms of the Puiseux expansions are and that the remaining terms can be found by performing the change of variable and solving the resulting equation for :

In a similar way, we find the leading term of , which has again multiplicity . We have to go on like this for steps until reaching the equation

At this point there are two possible dominant terms for (namely and ), each of multiplicity one, and we consider that we essentially solved the equation (more terms can be obtained efficiently using Newton's method).

From the complexity point of view, the problem is that we need to recompute a new equation at every step where we discover one more term of the expansion, which is quite expensive. A well known trick to replace the 50 steps by a single one is to compute the solution to the derivative of the equation, that is

and directly set instead of . The new equation in then becomes

after which the resolution process directly splits into two branches and . In general, for a -fold leading term, we need to consider a solution to the -fold derivative of the equation. In that case, the change of variables is called a Tschirnhaus transform.

For general contact coordinates, things become more technical, but similar strategies apply. In general, if is a ring with unity, if is a monic polynomial of degree in , if divides , and if is invertible in , then there exists a unique monic polynomial of degree such that has degree ; see section 8.3. The polynomial is called the -th approximate root of . If , then the -th approximate root corresponds to the Tschirnhaus transform . In general, the -adic expansion of writes as where the are polynomials in of degree , so is the -th approximate root of if and only if .

2.6.Central shifts

Let us now consider yet another type of equation with an almost -fold multiple solution

(2.9)

When solving the equation naively with the Newton polygon method, we obtain a -fold branch at the first step, a single branch and a -fold branch at the second step, a single branch and a -fold branch at the third step, and so on. From the complexity point of view, factoring out a single branch at every step leads to a cost

as a function of , which is not quasi-linear in .

Using Tschirnhaus transforms is not really of any help. For instance, the -fold derivative of the equation yields

with solution . After the change of variable , we still obtain one single branch and one -fold branch.

What really helps in this situation is a way to determine the series

(2.10)

This series has the property that, after the change of variable , we obtain the equivalent equation

whose Newton polygon has edges. In particular, the resolution process now branches into distinct parts of multiplicity one.

Computing the series (2.10) is equivalent to “solving” . But instead of peeling off factors of degree one from the left-hand side of (2.9), we rather compute with precision about in a recursive manner. This allows to factor as the product of two polynomials of degree close to , and to repeat this process in a recursive manner. Series such as (2.10) will be called central shifts. For a general polynomial equation , even within contact coordinates, the central shift will allow us to guarantee a suitably balanced factorization for which and can recursively be factored with good complexity.

3.Contact calculus

This section formalizes the concept of contact towers. The effective ground field is written and the contact coordinates will be denoted by .

3.1.Weighted valuations

We endow with the weighted valuation, simply written “”, defined by and for . With

this valuation induces a grading

where is the set of polynomials made only of terms of valuation ; notice that . When no confusion is possible, we drop “weighted”.

Let be the least common multiple of the denominators of . Then, the Chinese remainder theorem implies the following identity for the group completion of :

The integer is called the ramification index of the valuation.

3.2.Contact towers

The following definition is central for the rest of this paper.

The weights will also be called the contact slopes, in reference to the slopes of the corresponding Newton polygons; see section 7.3. When a contact tower is almost reduced then holds. The degree of the tower is .

Example 3.2. , , form a contact tower of height .

Example 3.3. Consider the example (2.6). It turns out that , and form a contact tower with contact slopes , . Here we got and from and .

We introduce another independent variable of weight and subject to the constraint . We also define the ideal

and the corresponding quotient ring

3.3.Canonical representation

In the following paragraphs, we show that is effective for computations with finite truncation orders in and . For this, we adopt the point of view of standard bases, while doing the proofs from scratch for completeness. We recall that the lexicographic ordering on is defined as follows:

We also introduce a total ordering with

on the group by

The ordering is a monomial ordering in the sense that

implies

for all . The leading monomial of with respect to this ordering is defined to be the largest monomial with a non-zero coefficient in . The set of monomials spanned by the leading monomials of the elements of an ideal is written . Note that . With the terminology of [28], the ordering is called a negative weighted degree lexicographic local ordering.

A standard basis of an ideal with respect to the monomial ordering is a set of generators such that the leading monomial of any polynomial in is a multiple of the leading monomial of at least one of the . In other words, is generated by . A standard basis is said to be reduced whenever none of the non-leading monomials in the belong to .

For the completeness, we now prove two well known lemmas from the theory of standard bases.

Proof. Since are independent of , it suffices to prove the lemma in . According to the assumptions, is monic of degree in , and for all and . Therefore,

for . The lemma follows from general standard basis theory since the leading monomials of the share no variable. For completeness, we give a dedicated proof.

Let us prove by induction on that is a standard basis for the ideal in . This clearly holds for . Let us assume that the induction hypothesis holds for some and consider . If , then is a multiple of . Otherwise, we write

with and . Then

so belongs to the ideal of . By the induction hypothesis, is a multiple of for some , whence so is . It follows that is a standard basis. The fact that it is reduced is clear from degree considerations.

For , we define

where stands at position and at position . Note that the dot product is identically zero. For , the initial form of , still written , is defined as .

Lemma 3.5. If for homogeneous , then

(3.1)

Proof. We prove the lemma by induction on . For , we have nothing to prove, so assume that . Extracting homogeneous components, we may assume without loss of generality that

whenever and . By the induction hypothesis, we may also assume that . Long division of by yields

for homogeneous polynomials with , for .

Reducing the relation modulo , we obtain

Since is monic in , it follows that , and thus that . Consequently, we obtain

which implies

Let . If , then is homogeneous. Otherwise, we have

so is also homogeneous. Each can be expanded with respect to :

with . Then we have

which implies for all . We conclude by applying the induction hypothesis.

Proof. We expand each with respect to the variable :

For all , we get

so Lemma 3.5 ensures the existence of homogeneous polynomials in such that

Letting , we deduce that

Since the are homogeneous, up to replacing the by their homogeneous components of suitable valuation, we may assume that

• the are homogeneous,

• holds for all with and ,

• holds for all with and .

For , we introduce the vectors

where stands at position and at position , so the dot product is identically zero. We set

Using the fact that , we conclude that

Proof. Let , so there exist with

We repeat the following operations:

1. Let . Since , we always have . If , then we obtain a relation

   

   where is the non-empty subset of indices such that , so we are done.

2. Otherwise , hence . The latter relation can be lifted to with for , by Lemma 3.6.

3. Replace the vector by , and go to step 1.

Thanks again to the assumption , the relation holds after each iteration. Furthermore, the value of strictly increases, so the process converges. We conclude that .

Proof. Assume that belongs to . Then , so Lemma 3.7 implies that for some .

From Proposition 3.8, we know that an element of can be uniquely represented by a polynomial of partial degree in for . We call the canonical representative of .

We introduce contact towers as a tool for the local resolution of polynomial equations. For this, we will often reduce to the case when all the roots of the polynomial are in the local region of interest. Such polynomials are said to be “clustered”:

Example 3.10. For the contact tower of Definition 3.1, the polynomial is a clustered polynomial regarded in for .

3.4.Arithmetic in contact towers

The theory of standard bases comes with algorithms to compute modulo ideals given by standard bases. We now detail how to perform such computations in the case of .

Additions, subtractions and scalar multiplications are straightforward, but other operations require an appropriate treatment of “carries” within -adic expansions. For the contact coordinates of Example 3.3, let us briefly illustrate how carries occur during multiplications.

Example 3.11. In Example 3.3 the polynomials and form a contact tower with contact slopes , .

Let us first illustrate the computation of a product modulo :

Doing a direct polynomial multiplication, we obtain

which is not in canonical representation since the degrees in and are too high. We thus have to rewrite

and

At the end, this leads to the following canonical representation for modulo :

The canonical representative of an element in can uniquely be written as

where satisfies for . Similarly, the canonical representative of another element can be written as

Now assume that for sufficiently large values of . Then we may regard as a univariate polynomial in : the “degree of in ”, written , is defined as the largest integer such that . We say that is “monic of degree in ” when and for .

Now we ask whether we can define and compute a generalized Euclidean division of by . The answer is “yes” under suitable assumptions. More generally, the following lemma shows that there exists a unique -adic expansion of .

Lemma 3.12. With the above notation let us assume that is clustered at and has degree in . Then, there exist unique elements in satisfying

and such that for all .

Proof. This lemma is a reformulation of what we have already proved with contact coordinates. In fact, it suffices to increase the height of the tower by one, to set

, and to assign any weight to the new variable . Therefore, the canonical representative of the image of in is given by

where for . Consequently the above -adic expansion of exists with .

As for uniqueness, let the be as in the statement of the lemma, and let us write them

with . The must satisfy

that implies

It follows that the do exist and are uniquely determined by the canonical representative of in .

Example 3.14. With the contact coordinates of Example 3.11, take

We have

Therefore the division of by writes with and .

3.5.Plain coordinates

In what follows, we will restrict ourselves to computations with “polynomials” in

instead of “series” in . Elements in can be represented canonically by polynomials of partial degrees in for . In order to alleviate terminology, we call elements in contact polynomials, in which case we always assume that is represented canonically as a polynomial in with ; we will also call this the contact representation. At the same time, we will keep the terminology of “canonical representatives” whenever we need to carefully distinguish between and its actual polynomial representative .

By what precedes, we may recursively expand elements in with respect to until . However, from a computational point of view such recursive -adic expansions are expensive. Indeed such expansions are reminiscent of computations modulo triangular sets, so it would be interesting to examine whether the algorithms of [45] could be adapted or not. In this subsection we follow another direction that leads to efficient algorithms. The key idea is to rewrite elements in with respect to the plain coordinates and . For this purpose, we introduce the following polynomials:

Note that is monic of degree . The change of representation is presented in the following lemma:

Lemma 3.15. The following map is a -algebra isomorphism:

			(3.2)

Proof. We introduce the following auxiliary evaluation morphism over :

For , we have

so and is well defined.

Let us prove by induction on that is bijective. This is clear when , so assume that . Let be of degree for some integer . The -adic expansion of yields a polynomial

such that and for . Next we recursively compute for . This yields

with . This proves that is surjective.

Now let be non-zero. Since , we must have , that is . The induction hypothesis implies that .

3.6.Conversion costs

As seen in the proof of Lemma 3.15, the isomorphism corresponds to a cascade of -adic expansions for . We begin with recalling known costs for univariate expansions over an effective ring .

Proof. Without loss of generality, we may assume that for some integer . We compute using operations in . We divide by , so with and . Then we compute the -adic expansion of and in a recursive manner so the expansion of is obtained by merging those of and . The depth of the recursive calls is . The sum of the costs of the operations at depth is , whence the claimed bound.

Proof. Without loss of generality, we may assume that for some integer . We compute with operations in . In a recursive manner we compute and , and finally we compute with operations in . The rest of the complexity analysis follows as in the proof of Lemma 3.16.

Remark 3.18. When univariate polynomial multiplication is done using FFT techniques, we note that it is possible to save a factor in Lemmas 3.16 and 3.17; see [40].

Proof. Let be of degree . Its -adic expansion takes operations in by Lemma 3.16. Then, we perform calls to in degree . A straightforward induction gives a total complexity bound

The backward conversion makes use of Lemma 3.17, and the complexity analysis is similar.

Proof. The product is computed via the following formula:

By Proposition 3.19 the cost of the conversions amounts to . Multiplying and modulo incurs .

For actual machine computations, we only work with truncated power series. The decision of whether it is more efficient to use contact representations or the plain representations in depends on the truncation order. For sufficiently small orders, the “carries” can be neglected, which makes it more efficient to conduct computations directly in the contact representation. For large orders, and thus for asymptotic complexity analyses, the overhead of the conversions using isomorphism (3.2) becomes small, and it is more efficient to perform arithmetic operations in . Until the end of the paper we perform most of the computations directly in , and thereby minimize the number of conversions.

The isomorphism (3.2) also allows for efficient Euclidean divisions in with respect to , in the sense of Lemma 3.12. In fact, let and be as in the lemma, and compute the division of by :

where . The degree in of the canonical representative of is therefore . It follows that equals the remainder of Definition 3.13. Since both and have finite degree in , we note that this also yields an easier way to define the division in comparison to Lemma 3.12. In particular, the assumption that is not needed.

Proof. The division is computed as above via

By Proposition 3.19 the conversions take . Dividing by modulo incurs .

3.7.Semi-valuations in contact towers

Recall that represents the valuation semi-group of the contact tower

Proof. For of canonical representative , we set

We need to verify that actually defines a semi-valuation in .

If is another element of of canonical representative , then it is straightforward to verify that . As for the product, we compute the long division by the standard basis thanks to Proposition 3.8:

where is the canonical representative of , so . The latter long division begins with setting and then it successively subtracts polynomials of the form from where , , , and . Since the monomials in have valuation , it follows that

This shows that . Since , we deduce that .

We write for the partial valuation in of . The valuation in of an element of will be the valuation in of its canonical representative. In the canonical representation, the degrees of the being bounded, the valuation in of an element in can be related to in terms of the . The following bounds will be useful when converting between the canonical and plain representations.

Lemma 3.23. Let be of canonical representative for some . Then we have

Proof. Assume . There exists a monomial of the form in . Using and for , we verify that

			(3.3)

and then that

The following lemma asserts that preserves the valuation in .

Proof. For any element , the inequality clearly holds. Conversely, for any , we have . It follows that

whence the first assertion. The second assertion is a consequence of the fact that is a -isomorphism; see Lemma 3.15.

The next lemma relates valuations and precisions of approximations of and .

Lemma 3.25. Let and be rational numbers. For all we have

For all we have

Proof. Lemmas 3.23 and 3.24 give us

(3.4)

In particular, if then . As for the second assertion, the inequalities (3.4) are equivalent to

In particular, if then .

Remark 3.26. Lemma 3.25 can be refined into

For simplicity we will not use this refinement in the sequel.

4.Contact Hensel lifting

The usual Hensel lemma asserts that if a monic polynomial factors into two monic coprime polynomials and modulo , then there exist unique monic polynomials and in such that , , and . In addition, and can be obtained with a softly linear cost in the output size.

A variant of Hensel lifting is the Weierstraß preparation theorem, in which case and are no longer monic, but is invertible as a power series in . We will generalize these two kinds of lifting to the contact coordinate framework.

Throughout this section, , are elements in , regarded informally as “polynomials” in the main variable . We will assume that holds for a “sufficient” initial precision, and that are “pairwise coprime”. We want to lift into so that holds up to a required precision. The case when is monic and

corresponds to the multi-factor Hensel lifting. The case when and

is called the Weierstraß normalization of .

Let be the canonical representative of . We recall that , , and is the image of in . If is a non-zero element in that is monic in , then represents the remainder in the division of by , as specified in Definition 3.13.

4.1.Normalized inverses

Let be clustered (see Definition 3.9) at and of degree in . Given with , its inverse modulo , whenever it exists, belongs to for some . In order to determine a bound for , consider satisfying

• ,

• is an integer ,

• .

Lemma 3.23 yields

If , then setting leads to

So we may divide by and subtract from in order to get a “simplified” modular inverse of that satisfies

(4.1)

If , so that , then multiplication of by also reduces to the case when (4.1) holds. In general, this shows that modular inverses can always be normalized in the sense of the following definition:

The existence and the computation of such inverses are postponed in section 7.1. The next definition concerns the special case when belongs to .

Proof. We have . Definition 4.2 also yields

Concerning the uniqueness, if represents a normalized initial inverse of then

and therefore , whence .

Proof. We extend the contact tower with and apply Lemma 4.3 in order to obtain the equality for the valuation. As for the uniqueness let represent another normalized inverse modulo . We have and thus , whence .

4.2.Lifting modular inverses

We explain how to increase the relative precision of a normalized modular inverse, in terms of the contact coordinates.

Proposition 4.5. Let , and , be such that

• is clustered at of degree in ,

• ,

• is a normalized inverse of modulo with relative precision .

Then, there exists a unique normalized modular inverse of with relative precision such that . More precisely, with and

we have and

Proof. Let represent an unknown in with , and which satisfies

(4.2)

This equation is equivalent to

and, by Lemma 4.4, to

Hence

We have , and therefore . Lemma 3.23 implies that

so can actually be divided by . We conclude that is the unique solution of (4.2), whence fulfills all requirements.

Proof. Thanks to repeated applications of Proposition 4.5 we can construct the initial inverse of modulo with any finite relative precision. The existence of follows from the completeness of .

The next corollary addresses the precision loss of the initial inverse of modulo when and are truncated modulo .

Proof. Let

represent the truncations of of and modulo , and let be the smallest element of larger or equal to . Thanks to repeated applications of Proposition 4.5 we can compute the initial inverse of modulo with relative precision .

Since and , we have and therefore . From

we deduce that

It follows that and then that

Using , we obtain that

hence

Lemma 3.23 implies that

Thanks to the value taken for it follows that

whence .

4.3.Weierstraß normalization

We now turn to the Weierstraß normalization of an element . The following definition gathers the necessary technical conditions and data structures.

The Weierstraß lifting step summarizes as follows.

Proposition 4.9. Let be monic of degree in and let denote a Weierstraß context for with relative precision . Then, there exists a unique Weierstraß context for with relative precision such that , , and . More precisely, with

we have and

Letting

we also have and

Proof. Consider the unknowns and such that and

It follows that

Lemma 4.4 and the constraints on valuations and precisions equivalently yield

whence

Then Lemma 3.23 gives

This shows that exists and is uniquely determined by

The formula for is straightforward and the one for follows from Proposition 4.5.

Proof. This follows from Proposition 4.9 and the completeness of .

Proof. We introduce the truncation of modulo , and set to the smallest element of larger or equal to . The quadruple , , , is an initial Weierstraß context for . From Proposition 4.9 we know that we can compute the Weierstraß context , , , for with relative precision , so that and

According to Corollary 4.6 we may consider the modular inverse of modulo , so that . Hence

and

Lemma 3.23 implies that

Since and are monic of the same degree in we deduce that .

4.4.Weierstraß normalization via plain coordinates

The above formulas for the Weierstraß lifting can be applied directly in , but for the sake of efficiency it is worth using plain coordinates. As a technical complication, conversions between contact and plain coordinates result in precision loss. Fortunately, this loss is sufficiently small so that it has no serious impact on the complexity of our top-level factorization algorithm. In the following algorithm, the input and output polynomials use plain coordinates. However, the relative precision , to be doubled during a lifting step, refers to the contact coordinates.

Proposition 4.12. Algorithm 4.1 is correct and takes

operations in , where .

Proof. The hypotheses of Proposition 4.9 are satisfied. We let

Lemma 3.25 implies

We have seen in Proposition 4.9 that , whence by Lemma 3.24. Consequently is well defined. With the notation of Proposition 4.9 we verify that

and

By Proposition 4.9, properties W₁, W₂, and W₃ of Definition 4.8 thus hold for , and relative precision .

In a similar fashion we verify that

so we have

By Proposition 4.5, property W₄ holds. We are done with the correctness. The cost analysis is obtained routinely by using .

Applying successively Algorithm 4.1 several times enables us to lift any such initial context to any requested precision. The cost is summarized in the following corollaries.

Corollary 4.13. Let be of degree in and let be an initial Weierstraß context for . Then, given , we may compute a Weierstraß context for with relative precision using

operations in , where and is the degree of the contact tower.

Proof. We convert the input data into the plain representation modulo using Proposition 3.19, with operations in .

We successively apply Algorithm 4.1 to increase the relative precision from to , for . By Proposition 4.12, the total cost of the lifting contributes to

At the end of the lifting, we convert the polynomials to contact coordinates modulo via Proposition 3.19, again with operations in .

Corollary 4.14. Let be of degree in and let form an initial Weierstraß context for . Then, given with precision with , we can compute its Weierstraß part (as defined in Corollary 4.10) with precision using

operations in , where is the degree of the contact tower.

Proof. The truncation of at precision does not depend on , as long as the initial Weierstraß context properties are preserved. In particular we may set to the largest slope of (which is if is a power of ), so we have where , whence

(4.3)

We use Corollary 4.13 with relative precision , as in the proof of Corollary 4.11. The running time is

which yields the claimed bound thanks to inequality (4.3) and

4.5.Hensel lifting step

We now turn to the lifting of a factorization of an element , assuming that suitable approximate modular inverses are known. The following definition gathers the necessary technical conditions and data structures.

Informally speaking, the assumption that admits a normalized initial inverse modulo for corresponds to the idea that are “initially coprime”. We revisit the classical Chinese theorem in this context.

Lemma 4.16. Given a Hensel context as in Definition 4.15, the following formula holds in :

Proof. Let us write

By construction this yields

(4.4)

for . Assume by induction that there exists such that

(4.5)

holds for some , which is indeed the case for by (4.4). Combined with (4.4) for , there exists such that

(4.6)

Since is initially invertible modulo , Corollary 4.6 yields the existence of the initial inverse of modulo , so there exists such that

Combining the latter equality to (4.6) gives

thanks to Lemma 4.4 and H₄. In this way, equality (4.5) holds for with . At the end of the induction equality (4.5) holds for , and since , we finally deduce that .

Given clustered at , we can increase with and . The contact tower obtained in this way corresponds to the quotient ring : in the sequel is endowed with the semi-valuation induced by .

Proposition 4.17. Given a Hensel context as in Definition 4.15, the map

is a -linear isomorphism and we have , where

Proof. It is clear from the assumptions that the map is well defined and -linear. Let

From Lemma 4.4 we have

so Lemma 3.23 implies

If follows that belongs to and that . By construction we have

that proves that is surjective.

Let be in the kernel of . There exists such that for . By Lemma 4.16 we deduce that

whence . Consequently is injective.

The Hensel lifting step goes as follows.

Proposition 4.18. Let be clustered at of degree in . Let represent a Hensel context for with relative precision . Then, there exists a unique Hensel context for with relative precision such that and for . More precisely, letting

for , we have ,

Letting and

we also have and

Proof. For , let us consider unknowns in such that and

After expanding the right-hand side of the latter equation, we obtain equivalently that

(4.7)

By Proposition 4.17, equality (4.7) is in turn equivalent to

For , Lemma 4.4 and the constraints on valuations and precisions then yield

whence

Then Lemma 3.23 gives

For , this shows that is uniquely determined by

whence satisfy the required properties. We finally remark that

for , so the formulas for the follow from Proposition 4.5.

Proof. This follows from a repeated use of Proposition 4.18 with increasing precision.

Proof. We introduce the truncation of modulo and let be the smallest element of larger or equal to . By assumption, form an initial Hensel context for . From Proposition 4.18 we know that we can compute the Hensel context for with relative precision , so that and

Since is the initial inverse of modulo , Corollary 4.6 ensures the existence of the modular inverse of modulo , which satisfies

It follows that

whence

Lemma 3.23 implies that

Since and are monic of the same degree in we deduce that .

4.6.Hensel lifting via plain coordinates

Hensel lifting is performed by the following algorithm that is dedicated to doubling the relative precision of a Hensel context.

Proposition 4.21. Algorithm 4.2 is correct and takes

operations in , where .

Proof. The hypotheses of Proposition 4.18 are satisfied. We let

Lemma 3.25 implies

We have seen in Proposition 4.18 that , whence by Lemma 3.24. Consequently is well defined for . With the notation of Proposition 4.18 we verify that

By Proposition 4.18, properties H₁, H₂, and H₃ of Definition 4.15 thus hold for and relative precision .

In a similar fashion we verify that

From Proposition 4.18 we know that divides , so it divides . Consequently is well defined for , and we have

By Proposition 4.5, property H₄ holds. We are done with the correctness.

Concerning complexities, from Definition 4.2 we first observe that

for . Consequently steps 2, 4, and 5 take

operations in using the sub-product tree technique; see [26, chapter 10, Theorems 10.6 and 10.10], for instance. The other steps require further operations in .

Applying successively Algorithm 4.2 several times enables us to lift an initial Hensel context to any requested precision. The cost is summarized in the following corollary.

Corollary 4.22. Let be clustered at of degree in , and let be an initial Hensel context for . Then, given and , we may compute a Hensel context for with relative precision using

operations in , where is the degree of the contact tower.

Proof. We convert the input data into the plain representation modulo using Proposition 3.19, with operations in .

We successively apply Algorithm 4.2 to increase the relative precision from to , for . By Proposition 4.21, the total cost of the lifting contributes to

At the end of the lifting, we convert the polynomials to contact coordinates modulo using Proposition 3.19, again with operations in .

Corollary 4.23. Let be clustered at of degree in , and let be an initial Hensel context for . Then, given at precision we can compute (as defined in Corollary 4.20) at precision for , using

operations in , where is the degree of the contact tower.

Proof. We use Corollary 4.22 with the relative precision as in the proof of Corollary 4.20. The running time is

Then we verify that

Using the cost of the lifting simplifies to .

5.Separable towers

In this section we introduce the notion of “separability” for contact towers. This will allow the construction of derivations on contact towers, which will be the key ingredient of the central shift algorithm in section 7.7.

5.1.Definition

Informally speaking, a contact tower is said to be separable when the initial forms of the its defining polynomials are separable. The precise definition is as follows.

Throughout this section, we assume that is effectively separable. For , represents the initial inverse of modulo . More precisely, we assume that is homogeneous and satisfies , where . From Definition 4.1 we know that

since .

Example 5.2. We define an effectively separable contact tower of height by taking , , , , and . Indeed,

where stands for remainder with respect to the variable .

Example 5.3. Consider Example (2.6): and form a contact tower of height with contact slopes , . We get and from and . As for the modular inverses we may take , ,

Indeed, we verify that

5.2.First derivatives

Since the map is a -isomorphism, from Lemma 3.15, the derivation on induces a derivation on (that is still denoted by for simplicity):

The separability assumption ensures that this derivation satisfies several convenient properties.

Lemma 5.4. Let be a separable contact tower. For we have

and

Proof. We prove the result by induction on . For we have

and

For we have

By Lemma 4.3, the separability assumption yields

Combined with the induction hypothesis we deduce

On the other hand, for we have

and therefore

5.3.Higher derivatives

We now study the effect of several consecutive differentiations in .

Lemma 5.5. Let be a separable contact tower. For any we have

Proof. The inequality follows from

Lemma 5.4, and the inequality

for .

Lemma 5.6. Let be a separable contact tower and let be such that

Then we have

Proof. Writing , we have

Then, for , we have so Lemma 5.5 yields

On the other hand,

(5.1)

so Lemma 5.4 implies

and

Lemma 5.7. Let be a separable contact tower. Given and such that

we have

Proof. First note that

holds for all . We prove the lemma by induction on . The result is clear for , so assume that . The induction hypothesis implies that

(5.2)

for some such that

Differentiating (5.2) with respect to yields

(5.3)

Since does not depend on , the initial form of also does not depend on . It follows that

whence

(5.4)

Equation (5.2), the assumption on , and the definition of imply that

(5.5)

By combining (5.3), (5.4), and (5.5) we deduce

(5.6)

On the other hand Lemma 5.6 gives us

(5.7)

We conclude the proof by combining equations (5.6) and (5.7).

6.Initial expansions

Canonical representations are not always the most efficient ones for computations with initial forms. This can be already observed in the case when . Indeed, let us write

with and for . Let and be coprime integers such that

Then, the coefficient is zero whenever is not a multiple of . This shows that is sparse in the sense that it contains at most non-zero terms besides . In particular, computations that use the dense representation are deemed to be suboptimal.

Assume for instance that we need to compute the valuation and the initial inverse of . We first extract the initial part of its canonical representative ; there exist and such that

where . Note that is again sparse. We now have to compute the Bézout relation of the specializations at of and in . Without exploiting the sparsity, this computation takes operations in . In this particular case, the remedy is to compute with respect to instead of , while exploiting the fact that and are dense polynomials in .

In order to generalize this remedy to the case when , we show in this section how to rewrite sparse homogeneous polynomials in into suitable products of coefficients in “algebraic towers” over and “monomials”.

In all computations below, will be an effectively separable contact tower (as in Definition 5.1) that satisfies the following additional property.

This regularity assumption implies that is determined by

6.1.Definition

An algebraic tower over is a sequence with and , for and monic polynomials . We will write for the image of in and set for . The tower is said to be effectively separable when we are given and in of respective degree and such that the Bézout relation

holds, for . The next definition concerns the alternative representation of homogeneous polynomials modulo .

6.2.Initial expansions for towers of height

The construction of an initial expansion associated to a contact tower is achieved by induction on . This subsection is devoted to the case when . As in the introduction of this section, we write

with and for . Note that because the tower is regular. As before, we let and be coprime integers such that

We define

where . Note that whenever is not a multiple of . The inverse of is:

With and , the map

is well defined because

Let us now show how to compute conversions via . Let be homogeneous of valuation and write

with . Then the formula

allows for the computation of without any arithmetic operations or zero tests. This also shows that is an isomorphism.

Assume that two elements and in with have the same valuation, that is

If (that corresponds to ), then so and therefore . Otherwise we have

and and are coprime. So divides , whence and . In other words, any homogeneous element in can be written in a unique way as with , , and .

Now consider the Bézout relation between and , with and . The element

has valuation . From

and

we obtain formulas to rewrite and in terms of :

Consequently is a uniformizing parameter of , whose valuation group is

and . In particular, is a purely ramified extension of . It remains to make effectively separable. To this end, we first compute

Let and be such that and let be such that . Then we have

Necessarily and is the inverse of . From this inverse we easily recover the Bézout relation of and , that makes the tower effectively separable.

6.3.Initial expansions for towers of height

The next lemma deals with the construction of an initial expansion associated to a contact tower. We extend the above construction for .

Lemma 6.3. Given an effectively separable and regular contact tower , there exists an initial expansion such that each divides , and

			(6.1)

is a -algebra isomorphism, for . We set . In addition, with , has valuation group

The algebra inherits the grading of . We still write for the semi-valuation induced over , so and for . Any homogeneous element of can uniquely be written as , where and

Proof. We prove the lemma by induction on The case has been addressed in the previous subsection, so we assume that and recall that is a uniformizing parameter of . We write

where is homogeneous for . Then we define

where and , for . We introduce

so we have

(6.2)

Since the tower is regular, is invertible. Since is homogeneous, we have whenever is not a multiple of and

for . The latter equation is equivalent to

We define as

and

(6.3)

The inverse of is then given by

(6.4)

From the induction hypothesis, can uniquely be rewritten as

where is invertible in and . We also have

so Lemma 3.23 further yields

Inside , the following equalities hold:

which shows that is well defined.

Let be homogeneous of valuation , such that for , and let us write it in the form

with homogeneous in and . Then

shows that it is straightforward to compute recursively, and that is a -algebra isomorphism; an explicit recursive formula for will be given in the proof of Proposition 6.4 below.

Now assume that two elements and , with , have the same valuation, that is

or, equivalently

Since , from Definition 3.1, , and since and are coprime, divides , whence and . In other words, any homogeneous element in can be uniquely written with , and .

Let

be the Bézout relation of and , with and . The element

has valuation

On the other hand we verify that

(6.5)

and

(6.6)

Consequently, the valuation group of is

and is a uniformizing parameter. In addition we have

whence

(6.7)

In order to show that is separable, we verify that

Let and be such that and let be such that . Then we have

It follows that and

whence

(6.8)

From this inverse we easily recover the Bézout relation of and so the tower is effectively separable.

6.4.Conversion costs

Before turning the above construction of the initial expansion into an algorithm, we study the costs of the conversions and . We recall from section 1.2 that products in take operations in .

Proposition 6.4. Assume that we are given an initial expansion of a contact tower, and let be homogeneous of valuation in . Recall that . Then we can compute in the form with using

operations in . Conversely, given with , we can compute

with the same cost bound. In addition, if has degree in and if divides , then we can compute using

operations in .

Proof. Let denote the canonical representative of . There exists such that and

For we recursively compute with . Then we verify

			(using (6.3))
			(using (6.2))
			(using (6.2), (6.5), and (6.6))

Recall that the inverse of is at our disposal and that the belong to . So we need to compute using binary powering and fast tower arithmetic. Then, we multiply this quantity by . These products require

operations in . Since and , we may simplify

Let be the cost of evaluating at any valuation . We have shown that

whence

The above formulas can be read in reverse order for performing a backward conversion , with a similar cost; note that .

The second assertion of the proposition corresponds to the special case where , which leads to the cost via the following formulas:

6.5.Cost of initial expansions

Having shown how the conversions and can be computed efficiently, let us now turn to the incremental construction of an initial expansion. We keep the same notation as in section 6.3.

Proposition 6.5. Given the initial forms of an effectively separable and regular contact tower, an initial expansion can be computed using

operations in .

Proof. The case has been detailed in section 6.1: it takes

arithmetic operations in . By induction on we may assume that the initial expansion has been computed up to height . We write

with the homogeneous in . Since and , Proposition 6.4 allows us to compute for using

(6.9)

operations in . This is sufficient to obtain .

If stands for the normalized initial inverse of , then we can compute . Hence

so the computation of the inverse of requires one evaluation of at and products in . The inverse of is then obtained via (6.4) with operations in . The cost of these two tasks does not exceed the bound (6.9).

The computation of the inverse of modulo then requires one evaluation of at the initial inverse of , then products in , and products in , by using formula (6.8). The second cofactor of the Bézout relation of and , namely , requires further operations in .

By using formula (6.7), the computation of from takes

operations in , that is operations in . The sum of the costs for all levels of the tower is bounded by

7.Newton factorizations

In this section we apply the lifting algorithms of section 4 in order to compute so-called Newton factorizations of a polynomial that is clustered at (Definition 3.9). These are partial factorizations that are related to the contact Newton polygon of with respect to the current contact coordinates (Definition 7.7).

Until the end of the paper, contact towers will be effectively separable (Definition 5.1) and regular (Definition 6.1). Since we occasionally will have to manipulate multiple contact towers at multiple levels, it is convenient to

• regard an element as an element in any other via the natural isomorphism ;

• write

  

  for the initial form, the valuation, and the truncation of , when regarded as an element in ;

• given , write

  

  for the initial form and the valuation of in .

7.1.Irreducible contact towers

Since we assumed from the outset that we have an algorithm or oracle for factoring univariate polynomials over , we are interested in factoring elements of into irreducible factors. There is a corresponding notion of irreducible contact towers and, thanks to our oracle, all contact towers that we will need for our main factoring algorithm can be forced to be of this type.

In view of the initial expansion and of a contact tower , we observe from Lemma 6.3 that is irreducible if and only if is a field. Equivalently, is a tower of field extensions. In this case, any non-zero element in admits a unique normalized initial inverse.

Proof. If is reducible then their exists a smallest index such that admits an initial factorization regarded in . This initial factorization yields an initial Hensel context that can be lifted into a non trivial factorization of by Corollary 4.19.

Conversely assume that is irreducible and let be a factor of . Then, initially divides , hence cannot be a non trivial factor of .

The next lemmas are devoted to the complexity of initial inversions.

Lemma 7.3. Let be an effectively separable, regular, and irreducible contact tower, and assume that its initial expansion has been precomputed. Let be homogeneous and of valuation in . Then, admits a unique normalized initial inverse, that can be computed with

operations in .

Proof. From Lemma 3.23 we know that . The computation of

takes

operations in by Proposition 6.4. Then we compute in time

Proposition 6.4 allows us to obtain

with further operations. Since , Lemma 3.23 implies . We verify that

by using identity stated in Definition 6.2. It follows that . After multiplying or dividing by a suitable power of we obtain the normalized initial inverse of .

Proof. We increment the tower with . The extended tower is not necessarily separable or irreducible because of its top level, but this does not prevent from building the corresponding incremented initial expansion with the difference that is not a field extension of , that is not even necessarily separable. By Proposition 6.5 this “almost initial expansion” incurs operations in . The conclusion follows from Lemma 7.3: still writing , the required initial modular inverse exists if and only if is invertible in .

7.2.Contact factors

The following lemma asserts that is clustered at any for as soon as it is clustered at .

Proof. Note that is monic in of degree . Therefore is monic in of degree when regarded in , for . The rest of the proof is done by induction on from down to . The case corresponds to the hypothesis of the lemma. Now let us assume that holds for some , and consider the contact representation

in , with

for . It follows that

where the second inequality is strict for . Consequently, .

7.3.Contact Newton polygons

Consider a contact polynomial

with for and . The Newton polygon of is the lower border of the convex hull of the set of pairs with and . More precisely, is a broken line with vertices , where

• ,

• for ,

• for all such that , the point is on or above the Newton polygon.

Any determines an edge between the vertices and , of slope . The set of points above the Newton polygon is convex. When we have , so the slope of the first edge is . In order to establish the usual relationship between and the Newton polygons of the factors of , we introduce the following definition.

The following lemma extends a special case of a classical result about Minkowski sums of polytopes due to Ostrowski [63] (translated in [65], and revisited later in [64]). In our variant we need to take care of “carries” involved by the contact arithmetic.

Lemma 7.8. Let and be contact polynomials in . Their respective Newton polygons and are assumed to be regular, the slopes of are strictly smaller than the ones of , and all slopes are . If , , , and , then the Newton polygon of equals

In addition, the contact polynomial

satisfies for and for .

Proof. First of all, note that the hypothesis on the slopes guarantees that the region of the plane above the Newton polygon

is actually convex.

Let be a point above . For all , we have

(7.1)

Similarly, for any point above and for all we have

(7.2)

Since the slope of the edge is smaller than the slope of , for , we obtain

Combining the latter inequality with (7.1) leads to

which means that is above the line spanned by and . Similarly, since and since the slope of the edge is smaller than the one of , we obtain

for . In combination with (7.2), this yields

so is above the line spanned by and . So far, we have proved that is above , for all and .

Since and are invertible, for in , Lemma 4.3 yields

Now consider the contact polynomial with , so we have and . Because the slopes of are , the point is strictly above .

Let us fix to a value different from the slopes of and . Let us assume first that is less than the smallest slope of . If is less than the largest slope of we let to be the largest integer such that is less than the slope of , otherwise we let . Let be the corresponding valuation induced in : for and ; we write for the corresponding initial part. We verify that

Consequently, Lemma 4.3 implies

belongs to the Newton polygon of , and .

Assume now that is greater than the smallest slope of then we let to be the first integer such that is greater than the slope of . Using a similar argument as above, we may prove that

(7.3)

belongs to the Newton polygon of , and that . This concludes the proof.

Lemma 7.9. Let be an effectively separable, regular, and irreducible contact tower and let

be a contact polynomial with the and truncated modulo with . Then, the effectively regular Newton polygon of can be computed using

operations in .

Proof. We first compute the initial expansion of , that contributes to from Proposition 6.5. Set in . In order to compute the valuation of we run over all its homogeneous components in in increasing valuation order. Up to precision , the number of such components is . Each such component has terms. Overall the number of zero tests in is .

From the valuations of the , the computation of the Newton polygon does not involve arithmetic operations in , but bit operations (with the usual “divide and conquer” algorithm). Finally, for a vertex of abscissa of the Newton polygon we need to compute the initial inverse of . For this purpose we extract and appeal to Lemma 7.3.

7.4.Distinct-slope factorization

Let be clustered at given with its effectively regular Newton polygon . We are to show that each edge of gives rise to a factor of .

Proposition 7.10. Algorithm 7.1 is correct and takes

operations in .

Proof. If then the algorithm is clearly correct. From now assume . By definition of the effectively regular Newton polygon, the value of occurring in step 3 writes as

From and for , Lemma 4.3 yields

Then Lemma 3.23 implies , hence step 3 computes an initial Weierstraß context for .

Let and be as in Corollary 4.14: , , and hold in step 4. From Lemma 7.8 we know that the Newton polygon of a is the Minkowski sum of those of and (up to the occasional vertex at infinity of and ). Since the vertices of the Newton polygon of have valuation in (or infinity), so are those of the polygons of and .

Let be the first index such that . From , Lemma 3.23 implies , whence

(7.4)

It follows that the Newton polygon of coincides with the one of for , and that these polygons are effectively regular, with the initial inverses as in steps 4 and 5.

In step 3, for , we compute with operations in thanks to Proposition 3.20. The same cost applies to the computation of in step 5. By Corollary 4.14, and since , the cost of the lifting in step 4 is

The depth of the recursive calls is , so the complexity bound follows from a standard induction.

Proof. Since the tower is irreducible, the Newton polygon of can be made effectively regular, thanks to Lemma 7.3. Consequently the existence of the distinct-slope factorization of follows from Proposition 7.10.

Given a distinct-slope factorization , by Lemma 7.8 the slopes of the are those of the Newton polygon of . If is set to the opposite of the slope of then is a Newton polynomial of of slope (up to a power of and up to a factor in ). The uniqueness of the thus follows from the uniqueness of the lifting of the distinct slope factors.

7.5.Equal-slope factorization

Consider the factorization of an element whose Newton polygon has a single edge with finite slope. We have already seen that an initial factorization into pairwise coprime factors of lifts into a factorization of . We now explain how to obtain this initial factorization. The contact polynomial is assumed to be truncated modulo with .

We assume that the initial expansion of the contact tower has already been computed. We extend the map (defined in Lemma 6.3) as follows:

We set to be the opposite of the unique slope of the Newton polygon of

Note that . Let

(7.5)

with prime to and let . Note that is an integer. In the next subsection we shall see that the notation is consistent since will be the “next ramification index”.

We compute with , for , and construct

so we have

(7.6)

We factor

where each is a power of a monic irreducible factor and the are pairwise coprime. For , we let and

(7.7)

We compute using

where stands for the coefficient of in .

Lemma 7.13. For , the polynomial defined in (7.7) is homogeneous, monic in , and of valuation . In addition, we have

Proof. The first assertion is clear by construction. The second assertion follows from the fact that is a ring isomorphism that preserves the valuation.

We next compute the modular inverses

for . Let us write the expansion of as follows

let be the smallest integer such that is a multiple of and set

From (7.5), we deduce

Recall from Definition 6.2 that . We further set

			(7.8)

so we have

From

we deduce that

whence

After a division by a suitable power of , we deduce the normalized initial inverse of modulo for .

The following algorithm makes use of the separable factorization of univariate polynomials: see [54]. In the case of characteristic zero or sufficiently large, that holds in the present paper, the separable factorization coincides with the squarefree factorization.

Proposition 7.14. Assume that K holds. Algorithm 7.2 is correct and takes

operations in , where is the degree of the separable part of .

Proof. From the above discussion the required initial Hensel context is known when entering step 6, so lifting is possible thanks to Corollary 4.23. Using Lemma 3.23 we verify that

			(7.9)

It follows that the Newton polygon of modulo has a single edge of slope . We are done with the correctness of the algorithm.

Let . Steps 1, 4, and 5 take

by Proposition 6.4. For the factorization of in step 2, as indicated we first compute the separable factorization using operations in by [54], and then factor (which are pairwise coprime). Consequently the cost of factoring over is

Step 3 contributes to

operations in : this includes the computation of via [26, chapter 10, Theorem 10.10], the remainders by the via [26, chapter 10, Theorem 10.6], and modular inversions. Finally, the cost of step 6 follows from Corollary 4.23 and .

Proof. The existence follows from Proposition 7.14. As for the uniqueness, assume that is an equal-slope factorization of . In the same way as we constructed from in equation (7.6), we define the polynomial of degree by

for . The are powers of pairwise distinct irreducible polynomials, so they coincide with those computed in Algorithm 7.2.

7.6.Incrementing the contact tower

After distinct-slope and equal-slope factorizations, we have reduced the general situation to the case where the Newton polygon of has a single edge and the associated Newton polynomial is an initial power of an irreducible homogeneous polynomial. This allows us to increment the underlying contact tower with a new contact coordinate at level and then to pursue the factorization of with respect to the extended tower. In order to ensure that the extended contact tower is separable, we assume from now on that the characteristic of is zero or sufficiently large.

Proposition 7.17. Algorithm 7.3 is correct and takes

operations in .

Proof. By construction, is homogeneous of valuation in , and satisfies all the requirements of Definition 3.1. The incremented tower remains effectively regular, since the known initial inverse of straightforwardly yields an initial inverse of . We extend the initial expansion at level accordingly. The initial inverse in step 5 does exist because is separable.

Steps 1 and 3 contribute to

by Proposition 6.4. Step 2 takes operations in by [54]. The cost of step 5 is by Lemma 7.4. Finally, is initially equal to whenever , which means that is clustered at .

7.7.The central shift algorithm

In principle, Algorithm 7.3 might introduce a new contact coordinate of degree one in . For complexity reasons it is better to avoid this from happening. As outlined in the introductory sections 2.5 and 2.6, we now work out the central shift algorithm.

Let be an effectively separable, regular, and irreducible contact tower. Let be clustered at . An initial root of is an element such that

If is a Newton polynomial of , then an initial root of is an initial root of regarded with set to the opposite of the slope of . One key idea behind the central shift algorithm is the following lemma, that will be used in a “divide and conquer” fashion in the subsequent algorithm.

Proof. Set . Lemma 5.7 implies

(7.10)

Since the tower is separable, we know from Lemma 5.4 that is initially invertible, hence is an initial root of of multiplicity .

Proposition 7.19. Algorithm 7.4 is correct and takes

operations in .

Proof. If the algorithm exits at step 1, then when regarded in the returned tower. Since the initial form of the returned is the same as the initial form of the input value of , hence the returned tower is effectively separable, regular, and irreducible. The Newton polynomial of cannot have non-zero initial roots with respect to the returned contact tower, so the output is correct.

The initial Weierstraß context in step 2 follows from equation (7.10). If the algorithm exits at step 6, then the output is clearly correct. Let us now examine the situation when the algorithm does not exit at step 6.

In step 7, Lemma 7.18 ensures that is a non-zero initial root of a Newton polynomial of of multiplicity , regarded in . Since , is a non-zero initial root of a Newton polynomial of of multiplicity . As a non-zero initial root of a Newton polynomial of modulo we necessarily have , hence

by Lemma 3.23. From Lemma 4.3, we deduce that

and consequently that

It follows that is a non-zero initial root of a Newton polynomial of of multiplicity modulo , hence that . Consequently,

(7.11)

We verify that , so . In step 8, the contact polynomial has degree in . By Lemma 7.18, inequality (7.11), and by following the same reasoning as for , a non-zero initial root of a Newton polynomial of in has multiplicity

Let us now examine the Newton polynomials of in . For this purpose, by means of Corollaries 7.12 and 7.16, we may decompose into

where has Newton polynomials with slopes , where has Newton polynomials with slope , and where has a single Newton polynomial of slope but that does not admit for initial root.

The initial of is , so its valuation is . Therefore the Newton polygon of in has a single edge of slope . We also verify that the Newton polygon of in admits a single edge of slope . Then, the Newton polygon of in is the same as in . Finally the Newton polygon of in has slopes . Consequently the non-zero initial roots of the Newton polynomials of in cannot have multiplicities . We are done with the proof of the correctness.

From Lemma 5.4 we have

Therefore, by using Proposition 3.20, the initial inverse of can be obtained with operations in from the precomputations attached to . The needed initial Weierstraß contexts in steps 2 and 8 can be obtained with operations in thanks to Proposition 3.20 again. The corresponding Weierstraß normalizations take further operations in by Corollary 4.14.

Let represent the cost of the algorithm with input of degree . In step 1, the cost is . In step 4 the effectively regular Newton polygon can be determined with cost by Lemma 7.9. Step 5 amounts to by using distinct-slope factorization and Proposition 7.10. In step 6, we appeal to the equal-slope factorization but discarding the irreducible factorizations: in fact, having a root of multiplicity is equivalent to having a separable factor of multiplicity , that can thus be read off from the separable factorization. So Proposition 7.14 provides us with a cost for steps 6 and 7. Consequently the cost of the algorithm in degree in satisfies

We conclude by a standard induction.

8.Contact factorization

We are now in a position to present our top level algorithm for contact factorization. The distinct-slope and equal-slope factorizations are intertwined in order to increase the current contact tower and split the input polynomials. The process finishes once the polynomial to be factored is a power of the top level contact coordinate, up to the input precision. The central shift algorithm ensures that the “divide and conquer” approach only incurs a logarithmic complexity overhead.

8.1.Recentered Newton steps

The main step of the contact factorization is summarized in the following algorithm.