> <\body> <\hide-preamble> \; |<\doc-note> Grégoire Lecerf has been supported by the French NODE project. Joris van der Hoeven has been supported by an ERC-2023-ADG grant for the ODELIX project (number 101142171). <\wide-tabular> ||||||| ||LOGO_ERC-FLAG_FP.png>|61.62pt|28.51pt||>>>>> ||<\author-affiliation> Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) CNRS, École polytechnique, Institut Polytechnique de Paris Bâtiment Alan Turing, CS35003 1, rue Honoré d'Estienne d'Orves 91120 Palaiseau, France |>>||<\author-affiliation> Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) CNRS, École polytechnique, Institut Polytechnique de Paris Bâtiment Alan Turing, CS35003 1, rue Honoré d'Estienne d'Orves 91120 Palaiseau, France |>>|>||<\doc-note> > The irreducible factorization of polynomials over power series is central to several problems in computer algebra: integral bases, genus of a curve, Jacobian of a curve, Riemann\URoch spaces. Well-known applications include cryptography and algebraic geometry errorcorrecting codes. Towards solving these problems with quasi-optimal complexity, recent algorithms make use of the so-called \Pcontact representation\Q. When carrying out the Newton polygon method, this allows intermediate objects to be represented in a compact way with respect to the required relative precision. In this paper, we focus on the complexity of the corresponding \Pcontact arithmetic\Q and present quasi-optimal algorithms for multiplication and division in the contact representation. |> Consider the valued field =\|)>> of Laurent series over an effective field >. Here \Peffective\Q means that algorithms are at our disposal for the arithmetic operations and the zero test in>. We will write \\>\|}>> for the valuation on >, with value group>=\>. Computing the irreducible factorization of polynomials over > is central for several problems in computer algebra: integral bases, genus of a curve, Jacobian of acurve, Riemann\URoch spaces. Well-known applications include cryptography and algebraic geometry errorcorrecting codes. The standard way to factor polynomials over > is to use the Newton\UPuiseux method. The mathematical description of this algorithm goes back to Newton and Puiseux>. Analyzing its computational complexity turns out to be subtle, due to the infinite nature of Laurent series. In particular, we must first decide how to represent and truncate elements in algebraic extensions of >. If \> is an irreducible polynomial, then \\/|)>> is again avalued field and extends uniquely to >. The main goal of this paper is to device efficient algorithms for computations with suitably truncated elements in >. If > has characteristic zero, then the roots of are conjugate Puiseux series whose coefficients lie in an algebraic extension of >. Taking > to be one of these roots, one obvious plan for computations in > is to simply extend > by > and do all our computations with Puiseux series. However, this is non-trivial to implement with good complexity and the restriction to characteristic zero is an important drawback. In order to factor polynomials over > with good complexity, modern algorithms are based on an alternate representation for elements in >. This representation was used by Abhyankar and Moh in and is called the in. The precise definition is somewhat technical and recalled in section below. It has the advantage of providing acompact representation for truncations of elements of>, in particular when the relative precision of such truncations is low. Given an ordinary non-zero Laurent series \>f*z> with \v>, its truncation with relative precision > is simply >*z>+\++\-1>*z+\-1>>>. Truncating elements of > depends on the basis we choose for > as a vector space over >. Consider for instance the case when -3*z|)>-x*z> and the element -3*z\\> with =2033/4>. It is more accurate and compact to represent approximations of with respect to the basis -3*z,x*-3*z|)>> than with respect to the canonical basis ,x>. Although conversions between both bases are possible, such conversions involve a constant loss of precision, which is a problem when working with low relative precision. In a nutshell, the contact representation is both compact and accurate for low relative precisions, whereas the usual representation with respect to the basis ,x> is more straightforward and efficient from a computational point for high precisions. In the recent works, the subtleties of the contact representation were circumvented by keeping the precision sufficiently high; in this way, it remained acceptable to do all actual computations using the classical representation. However, in the case of, this could only be achieved at the price of several convolutions, making part of the algorithms less natural. The present work is inspired by the idea that, in order to design efficient and elegant algorithms for high-level mathematical problems ( factorization over >), it is worthwhile to find the intrinsically best adapted representation for the underlying objects (the contact representation) and then to first develop efficient algorithms in order to work with this representation (contact arithmetic); see also. In this paper, we present quasi-optimal algorithms for basic arithmetic operations when using the contact representation. The contact representation can be regarded as ahybrid one that mixes recursive -adic expansions (at high relative precision) and towers of algebraic extensions (at low relative precision). Our complexity bounds are quasi-optimal, uniformly in the required precision. In order to achieve them, we will borrow techniques from to accelerate computations in towers of algebraic extensions. The contact representation is fairly subtle, which explains the length of this paper. But we believe that this makes it even more worthwhile to separate the \Plow-level\Q contact arithmetic that we develop here from high-level applications to factorization and other problems (which we intend to work out in upcoming work). In order to present our main result we need several definitions for the contact representation of elements of >. <\definition> A > of height consists of: <\itemize> Variables ,\,\>, called contact coordinates; Defining polynomials \\|]>,\,\|]>> for ,t>; Rational numbers ,\,\>, called >. These data are required to satisfy the following properties: <\itemize> Regarded in |]>,\,\|]>|]>>, the polynomial > is monic in > of degree \1>; > \\d>, for ,t> and ,i-1>; \0> and *\\1> for ,t>; We endow ,\,\|]>|]>> with the weighted valuation defined by 1> and \\> for ,t>. We demand that: <\itemize> =d*\>, for ,t>; \d*\>, for ,t>. The tower is said to be > when \2> for ,t>. We write \d*\*d> for ,t>. The above contact tower defines the following sequence of isomorphic |)>>algebras: <\equation*> \\\|)>,\,\|]>/-\,\,\-\|)>,i=1,\,t; see3.15>. Note that defines > over |]>>, but the results from there can naturally be restated over |)>> instead. An element in > admits a unique representative, called , in the form of a polynomial in |)>,\,\|]>> whose partial degree in > is d> for ,i>; see3.5>. We write |)>l>> for the elements of> whose canonical representative has degree l> in >. We let <\equation*> \\\+\*\+\+\*\. Following3.22>, the valuation |)>\\\|}>> extends to a semivaluation ;\|)>:\\\\|}>> defined by ;\|)>\\> for ,i+1>, and such that> inherits the above weighted grading of |)>,\,\|]>|]>>. Most of the valuations considered in this paper will be semivaluations, so we will drop the prefix \Psemi\Q for convenience. The of \> is a homogeneous element \> such that: <\itemize> |)>=-v|)>>, the homogeneous component of valuation of , written |]>>, equals . Note that in4.2 and Lemma4.3> we forced a normalized form to represent initial inverses. This normalization is not needed in this paper because we perform computations in contact towers directly over |)>> instead of |]>>. <\definition> A contact tower |)>t>> as in Definition is said to be > when \|\ \>> is initially invertible in >, for ,s>. It is said to be > if the initial inverse of the \|\ \>> is known for algorithmic purposes, for ,t>. <\definition> With the notation of Definition, a contact tower of height is said to be > when ,\,\,0|)>> has valuation *\> and is initially invertible, for ,s>. It is said to be > if the initial inverse of ,\,\,0|)>> is known for algorithmic purposes, for ,t>. We denote by |]>;\>> the >-vector space of the elements of > having valuation \> and (weighted) degree \+\>. For \>, we also write |]>;\>> for the sum of the terms of that belong to |]>;\>>. For complexity estimates we often use the notation: >(g(n))> means that |)>>>>>; see25, section7> for technical details. An algebraic complexity model ( straight-line programs) will be used for counting operations in>. For ,t+1>, there exists a unique integer \\> such that > equals *\>; see3.1>. The (logarithmic) height of a rational number is defined by <\equation*> ht\log,|)>|)>, where represents the natural logarithm. The number of bits for storing in a dense fashion is asymptotically proportional to >. Elements in a contact tower will be represented by the mixed dense-sparse representation described in section. A contact polynomial \> is said to be if its canonical representative is monic in > of degree 1> (that is \\>) and |)>=l*\>. The definitions of the quotient and remainder of contact polynomials, written >> and >>, are recalled in section. With these conventions, we are now able to state our main result. <\theorem> Let \0> (thought to be arbitrarily small). Given an almost reduced effectively separable and regular contact tower |)>t>> and \R*\0>>, we can compute auxiliary data (that only depend on the tower and >) using <\equation*> R*>*r*R*+ht \|)>|)> operations in >, such that, for any r*\0>>, the following tasks can be performed using <\equation*> R*>*l*R*\|)> operations in >: <\itemize> given |)>l>|]>|)>;\>> and |)>l>|]>|)>;\>>, compute |]>|)>+v|)>;\>>, given |)>2*l>|]>|)>;\>> and |)>l>|]>|)>;\>> clustered of degree , compute > B;\|]>|)>-v|)>;\>> and > B;\|]>|)>;\>>. Theorem contains the first nearly linear complexity bound for computing in contact towers. This result relies on our previous fast algorithms for algebraic towers. We are not aware of any other method with subquadratic complexity. Of course, when the relative precision is sufficiently large, a known fast strategy is to always work with respect to the plain coordinates , modulo appropriate conversions; see3.6>>. Let be irreducible in |)>>. In characteristic zero or deg P>, rational Puiseux expansions can be computed efficiently, hence =\|)>/|)>> becomes explicitly isomorphic to \\|]>|)>/-\*t|)>>, where > is algebraic over > of degree /e>. In this way, arithmetic operations in > can be achieved in softly linear time. The extension of this approach is tedious for small characteristic: Puiseux expansions do not exist any longer and uniformizing parameters are not known to be computable in quasi-linear time so far. Contact towers (a term coined in) constitute an alternate approach, that goes back to Mac Lane and that has been independently popularized by Abhyankar and Moh in the seventies. In fact, the latter authors designed specific contact towers from so-called of , that can be computed easily. Poteaux and Weimann achieved a quasi-linear complexity bound for irreducibility testing. Compared to Puiseux expansions, contact towers yield more convenient algorithmic and geometric views for germs of plane curves (the geometric counterpart of polynomials over power series). Puiseux expansions and contact towers are central tools for computing local irreducible factorizations. Unless the characteristic is too small, fast algorithms have been recently presented in, to which we also refer for further bibliographical references. The paper divides into two parts: up to section we gather definitions and design rather elementary (but new) algorithms for contact towers and sparse arithmetic, and from section we focus on fast operations. More precisely, the next section gathers notations and prerequisites about algorithms for multivariate polynomials and power series that are truncated with respect to a weighted valuation. In section we design elementary algorithms for contact towers. We assume that algorithms are known for some > with t> and we reduce computations in> to operations in >. Overall we achieve a product in > whose cost grows with > times the square of the input of the multiplicands. The goal of the next sections is the construction of another tower that is isomorphic to > but with a sufficiently small height with respect to its degree >. Let |)>> represent the initial form of >, that is its homogenous component of lowest valuation. In section we show how to compute a univariate representation of <\equation*> \|)>,\,\|]>/|)>,\,in|)>|)> over <\equation*> \|)>,\,\|]>/|)>,\,in|)>|)> in terms of an invertible primitive element of valuation>. We will call this a representation in terms of a element<\footnote> Such an element is sometimes called a uniformizing parameter or a local parameter. Our terminology tries to convey the idea that this is a primitive element both for the algebraic and valuative structures. . In section this representation is lifted at a prescribed relative precision > whenever <\equation*> \\min-d*\,\-d*\|)>, in order to obtain a univariate-valued representation of > over > at precision >. We introduce flattenings in section: they consists in replacing consecutive levels of small degrees in a contact tower by a single level in a flattening. The problem is much more intricate than for algebraic towers: a first type of flattening computes a univariate-valued representation, a second type is more straightforward to build but conversions to this representation induce a loss of precision. In addition we will design a specific fast flattened multiplication algorithm based on sparse arithmetic. The different types of flattenings used in this article are presented in section. The first type will handle the case where \\-d*\> and \\-d*\> so =0> and =0> hold at relative precision > in >. We will show that computing in > at relative precision> is equivalent to computing in /|)>>. By means of the univariate-valued representation introduced in section, we will then construct an isomorphism between /|)>> and <\equation*> /|)>|)>|~>|]>/|~>,\,\,|~>|)>|)> where |~>> is primitive-valued for /|)>> over /|)>> and |~>> is its minimal polynomial. It will be sufficient to perform these computations using a number of operations in /|)>> that remains polynomial in *D>. In fact *D> represents the degree of the underlying flattening and it will be chosen of magnitude >|)>>, where> can be fixed arbitrarily small. Conversions between /|)>> and /|)>|)>|~>|]>/|~>,\,\,|~>|)>|)>> will be performed without increasing the current precision>. For the second type of flattening, we will replace > by |]>/|~>-\|)>>, where|~>> is constructed as follows: |~>\\> and <\equation*> |~>,\,\|)>\\,\,\,|~>,\,\|)>,\,|~>,\,\|)>|)>, for ,t>. The conversions between > and |]>/|~>-\|)>> will be done fast, but with a loss of precision of order *D*\>. So, once again, this flattening will be used only when *D=O>|)>>. The special case where was treated before in3.5> and corresponds to conversions between contact and plain coordinates. Finally, the top level algorithms are presented in section, where we describe astrategy to build efficient flattenings. In this section we first gather notations and known facts about weighted multivariate polynomials and series. Then we design fast algorithms for multiplying truncated weighted polynomials. Let > be a commutative ring endowed with a (semi-)valuation , whose valuation group is *\> for some \\0>>. Let ,\,\> be indeterminates. For any positive integers ,\,l>, we define <\equation*> \,\,\|]>,\,l|)>>\\,\,\|]>\deg> P\l,\,deg> P\l|}>. For ,n>, we assign the weight \\0>> to > and write for the corresponding weighted valuation of ,\,\|]>>, that is <\equation*> val>*\*\>|)>=v+e*\+\+e*\, for all \>. As in the above context of contact towers (where =\|)>> and =1>) we define <\equation> R*\\R*\+\*\+\+\*\, with \\>. Since > divides > we can set \R/R\\> for ,n>. Given \\> and \\0>> we write <\equation*> ,\,\|]>|]>;\> for the >-module of polynomials of valuation \> that are defined up to valuation +\>, which means that two polynomials coincide in ,\,\|]>|]>;\>> whenever their difference has valuation \+\>. Since *\\\> for ,t>, we have *\\R*\> and since the denominator of > is > we have <\equation> ht \\ht \. A of a polynomial in ,\,\|]>> is a data structure that only stores the non-zero terms of. The of is the set of its monomials having a nonzero coefficient. Each such term is a pair made of a coefficient and a degree vector. In an algebraic complexity model the bit size of the exponents counts for free, and the relevant size of such a polynomial is the cardinality of its support. Consider two polynomials and of ,\,\|]>> in sparse representation. An extensive literature exists about the general problem of multiplying and ; see for a recent survey. In this paper, a superset > of the support of will always be known and we will rely on the following classical result. <\proposition> Let ,\,l> be positive integers and let \\> be of multiplicative orderl*\*l>. Let > be a subset of ,l-1|}>\\\,l-1|}>>, and let <\equation*> \\,\>,\*l>,\,\*\*l>|)>. <\enumerate> The value of > and the set > of all products >,\*l>,\,\*l*\*l>|)>> for ,\,e|)>\\> can be computed using |\|>*log*\*l|)>|)>> operations in >. Assume that > has been precomputed. Let be in ,\,\|]>,\,l|)>>>, in sparse representation, and with a support included in >. All the values of> at ,\,\,\|\|>-1>|}>> can be computed using |\|>|)>> operations in >. Assume that > has been precomputed. Given ,\,y|\|>-1>> in >, there exists a unique polynomial with support in > such that |)>=y>, for ,|\|>-1>. This polynomial can be computed using |\|>|)>> operations in >. <\proof> The first statement is straightforward by means of binary powering. The second and third ones are adapted from5.2>. As said, handling supports of sparse polynomials does not matter from the algebraic complexity point of view. Nevertheless in the rest of this subsection we provide the reader with a few bit complexity bounds for building prescribed sparse supports but also for computing with sparse polynomials. The bit complexity is estimated for a RAM model over a fixed /N*\>, as in. These analyses aim at showing that the algebraic complexity bounds of this paper might be turned into bit complexity bounds. Yet a complete proof is out of the scope of this paper. We begin with the support of truncated polynomials in one variable. <\lemma> Let \R*\>, \R*\0>> and \r*\0>>. Then there exists a subset <\equation*> \,\,l>\,l-1|}> of cardinality l*min*\,1|)>> such that for all polynomials <\equation*> A=i\l>A*\\|]>l>|]>;\> we have |]>-i*\;\>=0> whenever \,\,l>>. The set ,\,l>> can be computed using <\equation*> +ht \+ht \+ht \|)>+|)>*min*\,1|)> bit operations. <\proof> If *\\1> then we take \,l-1|}>>. Otherwise there exists an integer ,r-1|}>> such that =k/R>. If , that is =1/R>, then |]>-i*\;\>=|]>-i*\>> is zero whenever -i*\\R*\>, or equivalently whenever <\equation> R*\-i*R*\\r*\. By we know that *\> is coprime with >, so the condition is further equivalent to j mod r>, where <\equation*> j\*\|)>*R*\ mod r, so we take <\equation*> \,\,l>\*\|)>\,l-1|}>. Since \r*\> the cardinality of ,\,l>> is /r=R*\*l>. Computing the value of takes +ht \+ht \|)>> bit operations. Then the construction of ,\,l>> takes <\equation*> O/r|)>*log l|)>=|)>*min*\,1|)> additional bit operations. If 2>, then we take <\equation*> \,\,l>\\,1/R,l>\\+1/R,1/R,l>\\\\+/R,1/R,l>, whose cardinality is k*R*l/R=R*\*l>. From the value of computed for >, we deduce the one for +1/R> as *\|)> mod r> using |)>> bit operations, so the total time is as claimed. Here the support of a set of polynomials means the union of the supports of the polynomials in this set. So, Lemma means that the support of |]>l>|]>;\>> is a set of monomials in > of cardinality l*min*\,1|)>>. We extend this result to several variables. Monomials in ,\,\> are represented by vectors in > and supports are sequences of monomials. <\lemma> Let \r*\0>> for ,n>, let \R*\>, and let \R*\0>>. The support of ,\,\|]>,\,l|)>>|]>;\>> has cardinality <\equation*> \l*\*l*min*\,1|)> and can be computed using <\equation*> +n*ht \|)>+*\*l|)>*min*\,1|)> bit operations. <\proof> A homogeneous polynomial in |]>l>> has l/r=l*R*R> non-zero terms by Lemma. A straightforward induction on yields that any homogeneous polynomial in ,\,\|]>,\,l|)>>> has at most l*\*l*R*R> non-zero terms. If the polynomial is not homogeneous and if =k/R\R>, then the number of nonzero terms is l*\*l*R*\>. If *\\1> then the bound on the number of monomials is clear. In order to compute the support of ,\,\|]>,\,l|)>>|]>>> we begin by computing >\R*\ mod R>, \l/r>, and =R*\ mod R>, for ,n> using <\eqnarray*> ||+ht \+\+ht \+n*log R+log*\*l|)>|)>>>|||+n*ht \+n*log R+log*\*l|)>|)>>>>> bit operations, by. Then \val> P> is the smallest nonnegative integer such that -k*\\R*\> or equivalently that -G*k\r*\>. By we know that > is coprime with >, so we obtain <\equation*> k\G*\ mod r in time log R|)>>. Without loss of generality we can replace > by /R> and > by /R> for computing supports. Let us write <\equation*> P=\>*+P*\>+\+P-1>*\-1|)>*r>|)>, where <\equation*> P\,\,\|]>,\,l|)>>|]>-+k|)>*\>. Recursively we compute the support of > for ,s-1>, and deduce the support of in time <\equation*> O*l*\*l*R*R*log*\*l|)>|)>=O*\*s*R*log*\*l|)>|)>. Let > denote the cost for computing the support of a homogeneous polynomial in ,\,\|]>,\,l|)>>>. We have shown that <\equation*> =s*+O*\*s*R*log*\*l|)>|)>. Unrolling this recurrence yields <\equation*> =O*\*s*R*log*\*l|)>|)>=*\*l|)>*R*R. For the next homogeneous component, of valuation +R>, we replace > by +1|)> mod R> and restart the computation of the support. Consequently, for =k/R\R> we need to compute the support of homogeneous polynomials. For a truncated polynomial in |)>,\,\|]>,\,l|)>>|]>;\>> we use a mixed densesparse representation. Precisely, we store > and the sequence of homogeneous components <\equation*> +i/R>|)>,R*\-1>, where each +i/R>> is stored as the sparse representation of its specialization at , that belongs to ,\,\|]>,\,l|)>>>. <\lemma> Let \r*\0>> for ,n>, let \R*\>, and let \R*\0>>. The support with respect to ,\,\> of |)>,\,\|]>,\,l|)>>|]>;\>> has cardinality l*\*l*\> and can be computed using <\equation*> +n*ht \|)>+*\*l|)>*\ bit operations. <\proof> We adapt the proof of Lemma, with =1>. Let |)>,\,\|]>,\,l|)>>|]>;\>>. Each homogeneous component of has l*\*l*R> monomials in ,\,\|]>>. A polynomial with relative precision > has R*\> homogeneous components. Given \R*\> and \R*\0>>, we will use the dense-sparse representation to multiply polynomials <\equation*> A\|)>,\,\|]>,\,l|)>>|]>;\>B\|)>,\,\|]>,\,l|)>>|]>;\> efficiently. Note that |)>,\,\|]>-1,\,2*l-1|)>>|]>+\;2*\>>. <\proposition> Given \r*\0>> for ,n>, two polynomials |)>,\,\|]>,\,l|)>>|]>;\>> and |)>,\,\|]>,\,l|)>>|]>;\>> can be multiplied using <\equation*> R**l*\*l*R*\|)> operations in\> and +ht \+ht \|)>+*l*\*l|)>*\> bit operations. <\proof> Let A*B>, \\+\>, and <\eqnarray*> |>|,\+R,\,\+\-R|}>\,\+R,\,\+\-R|}>>>|||\,\+R,\,\+2*\-R|}>.>>>> For R*\>, we write > for the support of |)>,\,\|]>,\,2*l|)>>|]>> where is specialized at. Since =\>, it suffices to compute the > for I mod 1>. By Lemma, this takes <\eqnarray*> ||+ht \+ht \+\+ht \|)>+*l*\*l|)>*\>>|||+ht \+ht \|)>+*l*\*l|)>*\)>>>>> bit operations, and we have |\|>\2*l*\*l*R>. Assume that we are given an element \\> of multiplicative order 2*l*\*l>, so we apply Proposition with > instead of >. For each I mod 1>, we compute > and the set > corresponding to > using <\equation*> O*l*\*l*R*log*l*\*l|)>|)>+*l*\*l*R|)>=R**l*\*l|)> operations in >. Then we define <\equation*> >,\,\|)>=A>*\,\,t>*\|)>=t>*i\R*\>+i/R>,\,\|)>*t> that belongs to >|)>|)>,\,\|]>>. We define >> similarly. By Proposition we compute >|)>> and >|)>> for ,|\|>-1> using <\equation*> *l*\*l*R|)>*R*\. We compute >|)>=>|)>*>|)>> for ,|\|>-1> at relative precision > using <\equation*> O*l*\*l*R|)>**\|)>=R**l*\*l*R*\|)> operations in >. Then we interpolate from >> using Proposition again. Finally, if we are not given an element \\> of multiplicative order 2*l*\*l>, then we appeal toA.2>: the overhead only induces logarithmic factors in the complexity bound. Given a contact tower as in Definition, we are interested in computing the product of two elements and in > with relative precision \0>. This section is devoted to relatively simple algorithms, on which the faster ones of section will rely. As a first observation, since we are interested in computing with relative precision > in>, we show that the defining polynomial -\> can be replaced by > in the definition of > whenever -d*\\\> holds. For this purpose we introduce integers ,\,\> in > and the <\equation*> \>\\|)>,\,\|]>/-\*\,\,\-\*\|)>,i=1,\,t. Generalized contact towers share many of the properties of contact towers. We gather the results needed in the sequel, along with brief proofs adapted from. <\proposition> For ,t>, any \>> admits a unique representative of the form <\equation*> P=\d,\,k\d,k\\>P,\,k>*\>*\*\>\\|)>,\,\|]>,\,d|)>>|]>, which we call the > of . <\proof> Assume that the polynomial , written as above, belongs to the ideal <\equation*> I>\-\*\,\,\-\*\|)>. If is not identically zero, then its initial form |)>> is non-zero. The proof of3.7> extends to >> and gives us that <\equation*> in>|)>=|)>,\,in|)>|)>. Finally3.4> implies that |)>> must be zero, that is a contradiction. <\proposition> For ,t> the map <\eqnarray*> ;\>|)>:\>>|>|+\*\+\+\*\\|}>>>||>| P,\,k>+k*\+\+k*\\k\d,\,k\d,k\\|}>>>>> is a valuation of >>, that inherits the weighted grading of |)>,\,\|]>|]>>. <\proof> By routine adaptation of the proof of3.22>. The integer \\> defined by <\equation*> R*\=\+\*\+\+\*\ is called the of ;\|)>> and ;\>|)>>, for ,t+1>. From Definition it is clear that > divides *\*d>. By construction, > divides >, and <\equation*> r\R/R, divides >, for ,t>. Elements in >> will be called . Such a polynomial will be usually written <\equation*> P=P*\+\+P*\+P, with \\|)>,\,\|]>,\,d|)>>> and \0>. This is called the of. The integer is called the of in > and is written > P>. We will write >|)>l>> for the set of contact polynomials of >> of degree l> in >. A contact polynomial \>> is said to be if its canonical representative is monic in > of degree 1> (that is \\>) and >|)>=l*\>. Note that > is clustered in >>. Let and be contact polynomials in >>, if is clustered of degree , then there exist unique elements \>|)>n>> such that <\equation*> A=0>Q*B. This decomposition is adapted from3.12> and yields a natural notion of division: there exists unique contact polynomials >|)>n>> and \>> such that <\equation*> A=Q*B+R. The is written > B> and the is written > B>. Now let 0>A*\> and 0>B*\> be contact polynomials in > and let us compute their product 0>C*\>, where <\equation*> C\A*B\|)>2>. Each > writes canonically into =c+c*\> with > and > in >. Now if -d*\\\>, then we have <\equation*> ;\|]>|)>+v|)>-i*\;\>=;\|]>|)>+v|)>-i*\;\>. In other words, computing |]>|)>+v|)>;\>> in > is the same as in >> when =\=\=1> and =0>. By decreasing induction on , it follows that computing |]>|)>+v|)>;\>> in > is the same as in >> where we set \0> when -d*\\\>, and \1> otherwise for ,t>. The rest of this section is devoted to rather elementary algorithms for multiplying elements in a generalized contact tower at a given relative precision >. In order to keep the notation simple, we drop the superscript > for generalized contact towers. So, unless specified, contact towers will be of the generalized kind. Given a clustered contact polynomial \> of degree 1> in >, its will refer to the clustered contact polynomial \> of degree in > such that <\equation*> F*G\\+|)>l>. Since \+|)>l>> holds for all |)>l>>, if a pre-inverse exists, then it is necessarily unique. The existence of pre-inverses is addressed in section. We introduce the following cost functions: <\itemize> ,\,d,l;\|)>> is a function that bounds the cost for adding two elements in > of degreel> in > with relative precision \>. ,\,d,l;\|)>> is a function that bounds the cost for multiplying two elements in > of degree l> in > with relative precision \>. ,\,d,l;\|)>> bounds the cost of a division in > of a contact polynomial of degree2*l> by a clustered contact polynomial of > of degree with relative precision \>. ,\,d,l;\|)>> bounds the cost for computing the pre-inverse of a clustered contact polynomial in > of degree in > with relative precision \>. ,\,d,l;\|)>\2*,\,d,l;\|)>+,\,d,l;\|)>+,\,d,l;\|)>>. <\lemma> Without loss of generality, we may always assume that <\equation*> ,\,d,1;\|)>\,\,d;\|)>+,\,d;\|)>. <\proof> Let and be in |)>1>>. Regarded in |)>d>> their product costs,\,d;\|)>>. We divide by > in > with,\,d;\|)>> operations. Let and denote the resulting quotient and remainder, so +R>. Since has valuation |)>+v|)>-d*\>, and since \d*\>, we have <\equation*> |]>|)>+v|)>;\>=\*|]>|)>+v|)>-\;\>*\+|]>|)>+v|)>;\>. <\lemma> Let be a clustered polynomial in > of degree in >, together with its preinverse. For all |)>l>> at relative precision \0>, there exists a unique |)>l>|]>|)>;\>> such that <\equation> |]>|)>;\>= quo> \;\|]>|)>;\>. It is given by quo> \;\|]>|)>;\>>. <\proof> Equation corresponds to searching for |)>l>|]>|)>;\>> and |)>l>|]>|)>+l*\;\>> such that <\equation*> |]>|)>+l*\;\>=+R;\|]>|)>+l*\;\>, which implies that <\eqnarray*> ||-U*G*F+G*R;\|]>|)>+2*l*\;\>>>||>|-U*+|)>l>|)>+G*R;\|]>|)>+2*l*\;\>,>>>> so quo> \;\|]>|)>;\>> is the unique solution of Equation. The following simple multiplication algorithm in > makes use of operations in >, whose cost functions are assumed to be as in section. <\specified-algorithm> <\description-compact> A*\\|]>;\>> and B*\\|]>;\>> of degree l> in >. |]>+\;\>>. <|specified-algorithm> <\enumerate> For ,2*l-2> compute +H*\\+k=i>>*B>;\|]>+\-i*\;\>>. Return ++L|)>*\+\++L|)>*\+H*\>. <\proposition> Algorithm is correct and performs <\equation*> \2*,\,d;max,\|)>|)>**\,1|)>*l|)> operations in >, whenever \R*\0>> and r*\0>>. <\proof> The correctness is straightforward from the definitions. The number of non-zero terms in is min*\,1|)>*l> by Lemma. The number of non-zero products >*B>> performed in step1 is therefore *\,1|)>*l|)>>, so this step costs <\equation*> \,\,d;\|)>+,\,d;\|)>+,\,d;\|)>|)>**\,1|)>*l|)> thanks to Lemma. Step2 takes <\equation*> \2*,\,d;\|)>*min*\,1|)>*l operations in >. Since r*\0>>, we use *\,1|)>*l\1> in order to simply the final cost bound. Let F*\\\> be a clustered polynomial of degree in > and let |)>l>>. We address the computation of the quotient > F> and the remainder of > F> at relative precision \R*\0>>. We assume that the pre-inverse +g> of +F> is at our disposal at relative precision >. <\specified-algorithm> <\description-compact> A clustered polynomial |]>;\>> of degree in >, |)>2*l>|]>|)>;\>>, and the pre-inverse +g> of +F> at relative precision >. > F;\|]>|)>-l*\;\>> and > F;\|]>|)>;\>>. <|specified-algorithm> <\enumerate> Set P>. For from down to do: <\enumerate> Compute \+g|)>*R|)> quo \;\|]>|)>-i*\;\>>, where > represents the coefficient of > in the contact representation of ; Replace by *\*F;\|]>|)>;\>>. Return Q*\> and . <\proposition> Algorithm is correct and performs <\equation*> \2*,\,d;max,\|)>|)>**\,1|)>*l|)> operations in > whenever \R*\0>> and r*\0>>. <\proof> For a fixed value of in step2, by Lemma, we have <\equation*> R=*+F|)> quo \;\|]>|)>-i*\;\>, so the algorithm finishes with the expected quotient and remainder. The number of nonzero coefficients > encountered during step2 is min*\,1|)>*l> by Lemma. According to Lemma, step2.a costs ,\,d;\|)>>. Step2.b costs <\equation*> \,\,d;\|)>*min*\,1|)>*l. Finally we use *\,1|)>*l\1>. Given F*\\\> clustered of degree in >, we wish to compute its pre-inverse with relative precision >. We adapt the well-known method for power series inversion. The algorithm is recursive on the height . If then the pre-inverse of +F> is -F> because \\|)>>. <\lemma> If is the pre-inverse of +F> regarded as a clustered polynomial in > of degree > in > and at relative precision >, then <\equation*> -*\|)> quo> \>|)>|)> quo> \>;\|]>;\> is the pre-inverse of +F> at relative precision >. <\proof> Since ;\|)>\\\d*\>, +F> is clustered in >, so is well defined. Computing the pre-inverse of +F> means finding |)>1>|]>;\>> such that <\equation*> +u|)>*+F|)>;\|]>;\>\\+|)>1>. This condition is equivalent to <\equation*> *|)>+u*F;\|]>;\>\|)>1>, that is further equivalent to <\equation*> ;\|]>;\>=-|)> quo> \;\|]>;\>, in >, then to <\equation*> *\+u*+F|)>;\|]>+d*\;\>\|)>d>, and finally to <\equation*> *\|)> quo> \>;\|]>;\>=-+F|)>|)> \ quo> \>;\|]>;\>. From Lemma we deduce that *\|)> quo> \>|)>|)> quo> \>;\|]>;\>>. <\lemma> Let ,l-1|}>> and let \+\*|)>k>> be clustered of degree in > such that <\equation*> |]>;\>\\+|)>2*l-k>. There exists a unique >\|)>1>|]>*\;\>> such that <\equation*> >*\>|)>;\|]>;\>\\+|)>2*l->. It is given by <\equation*> >\-+G|)>|)> quo> \;\|]>*\;\>>>, where > is the coefficient of > in and |)>1>> is defined by <\equation*> |]>;\>=\+c*\>+|)>2*l->. <\proof> From <\equation*> F*>*\>|)>=F*G+G>*\>*F, the condition for >> is equivalent to <\equation*> >*+F|)> quo> \|)>;\|]>*\;\>\|)>1>. Since +G> is the pre-inverse of +F> at relative precision >, there exists a unique solution for >> given by Lemma. A straightforward induction based on the two latter lemmas shows that pre-inverses do exist. <\proposition> The pre-inverse of a clustered contact polynomial \> of degree r*\0>> in > can be computed at relative precision \R*\0>> using <\equation*> \4*,\,d;max,\|)>|)>**\,1|)>*l|)>+,\,d;max,\|)>|)> operations in >. <\proof> From Lemmas and we can compute the pre-inverse of <\equation*> F quo> \=\+F at relative precision > using <\equation*> \,\,d;\|)>+2*,\,d;max,\|)>|)> operations in >. By induction on , suppose that the pre-inverse of > \> is known along with the product , for some 1> and still at relative precision >. Thanks to Lemma we deduce the pre-inverse > of > \>> in the form <\equation*> \G*\+G> with a cost ,\,d;\|)>>. The product <\equation*> *F=G*F *\+G>*F at relative precision > costs <\equation*> \,\,d;max,\|)>|)>*min*\,1|)>*l. By taking the sum of these costs for ,l-1> and for when >> is known to be non-zero at relative precision >, we achieve the total bound <\eqnarray*> |>|,\,d;max,\|)>|)>**\,1|)>*l**\,1|)>*l+1|)>+2|)>>>|||+,\,d;max,\|)>|)>>>>> for the pre-inverse of . Finally we use *\,1|)>*l\1> in order to simplify this bound. to > So far we have reduced operations in > to operations in >. Now we proceed by induction in order to reduce operations in > to operations in > for any fixed t>. <\lemma> For all t> and all \0> we have <\equation*> min*\,1|)>*min*max,\|)>,1|)>=min*\,1|)>. <\proof> If \R> then <\equation*> min*\,1|)>*min*max,\|)>*,1|)>=R*\*min*R,1|)>=R*\=min*\,1|)>. Otherwise we have \\>, hence <\equation*> min*\,1|)>*min*max,\|)>,1|)>=min*\,1|)>. <\proposition> Let ,t|}>>, \R*\0>>, r*\0>>, and let \> be a clustered polynomial of degree in >. Let -1>\|)>1>> denote the coefficient of -1>> in >. Then the pre-inverses of +\-1>>,,+\-1>>, +F> can be obtained with a cost <\eqnarray*> |>|*,\,d;max,\|)>|)>**max,\|)>,1|)>*d*\*d|)>>>|||+,\,d;max,\|)>|)>*.>>>> Once these pre-inverses are known, we may compute in > with the cost bound <\equation*> ,\,d,l;\|)>\5*,\,d;max,\|)>|)>**\,1|)>*d*\*d*l|)>, where underlying divisions in > are only allowed by . In addition, given the pre-inverses of +\-1>>,, +\-1>> we have <\eqnarray*> ,\,d,l;\|)>>|>|*,\,d;max,\|)>|)>**\,1|)>*d*\*d*l|)>>>|||+,\,d;max,\|)>|)>.>>>> <\proof> From Proposition we may take <\equation*> ,\,d,l;\|)>\2*,\,d;max,\|)>|)>**\,1|)>*l|)>. Assuming that the pre-inverse of +F> is known, thanks to Proposition, for divisions by , we may take <\equation*> ,\,d,l;\|)>\2*,\,d;max,\|)>|)>**\,1|)>*l|)>. From Lemma we straightforwardly obtain <\equation*> ,\,d,l;\|)>\,\,d;max,\|)>|)>*min*\,1|)>*l. By summing these three inequalities and using *\,1|)>*l\1>, we deduce <\equation*> ,\,d,l;\|)>\5*,\,d;max,\|)>|)>**\,1|)>*l|)>. By unrolling the latter inequality and using Lemma, we obtain that <\eqnarray*> ||,\,d,l;\|)>>>||>|*,\,d;max,\|)>|)>**max,\|)>,1|)>*d*min*\,1|)>*l|)>>>||>|*,\,d;max,\|)>|)>**\,1|)>*d*l|)>>>||>|>||>|*,\,d;max,\|)>|)>**\,1|)>*d*\*d*l|)>,>>>> whenever the pre-inverses of +\-1>>, , +\-1>>, +F> are known.\ From Proposition we know that <\equation*> ,\,d,l;\|)>\4*,\,d;max,\|)>|)>**\,1|)>*l|)>+,\,d;max,\|)>|)>. By using and Lemma we deduce that <\eqnarray*> ||,\,d,l;\|)>>>||>|5*,\,d;max,\|)>|)>**\,1|)>*min*max,\|)>,1|)>*d*\*d*l|)>>>|||+,\,d;max,\|)>|)>>>||>|5*,\,d;max,\|)>|)>**\,1|)>*d*\*d*l|)>>>|||+,\,d;max,\|)>|)>.>>>> Iterating the latter inequality yields <\eqnarray*> ||,\,d,l;\|)>>>||>|,\,d;max,\|)>|)>>>|||\**max,\|)>,1|)>*d*\*d*l|)>+\+5**max,\|)>,1|)>*d|)>|)>>>|||+,\,d;max,\|)>|)>>>||>|,\,d;max,\|)>|)>>>|||\**\,1|)>*d*\*d*l|)>+\+5**\,1|)>*d*\*d*l|)>|)>>>|||+,\,d;max,\|)>|)>>>||>|*,\,d;max,\|)>|)>**\,1|)>*d*\*d*l|)>>>|||+,\,d;max,\|)>|)>.>>>> From Lemmas and the pre-inverse of +F> is obtained at relative precision> using <\equation*> \,\,d;max,\|)>|)>+2*,\,d;max,\|)>|)> operations in >. Consequently, the cost for obtaining the pre-inverses of +\-1>>, , +\-1>>, +F> is <\eqnarray*> |>|,\,d;max,\|)>|)>+\+,\,d;max,\|)>|)>>>|||+2*,\,d;max,\|)>|)>+\+2*,\,d;max,\|)>|)>>>||>|*,\,d;max,\|)>|)>**max,\|)>,1|)>*d*\*d|)>>>|||+,\,d;max,\|)>|)>>>|||>>|||,\,d;max,\|)>|)>**max,\|)>,1|)>*d|)>>>|||+,\,d;max,\|)>|)>)>>>|||,\,d;max,\|)>|)>>>|||5*,\,d;max,\|)>|)>**max,\|)>,1|)>*d*\*d|)>>>|||>>|||5*,\,d;max,\|)>|)>**max,\|)>,1|)>*d|)>>>|||,\,d;max,\|)>|)>)>>>||>|*,\,d;max,\|)>|)>**max,\|)>,1|)>*d*\*d|)>>>|||+,\,d;max,\|)>|)>>>|||>>|||,\,d;max,\|)>|)>**max,\|)>,1|)>*d*\*d|)>>>|||+,\,d;max,\|)>|)>>>|||,\,d;max,\|)>|)>>>|||5*,\,d;max,\|)>|)>**max,\|)>,1|)>*d*\*d|)>>>|||>>|||5*,\,d;max,\|)>|)>**max,\|)>,1|)>*d*\*d|)>>>|||,\,d;max,\|)>|)>>>||>|*,\,d;max,\|)>|)>**max,\|)>,1|)>*d*\*d|)>>>|||+*,\,d;max,\|)>|)>,>>>> which concludes the proof. So far we have designed rather elementary algorithms for contact towers, that will be useful to section. Computing pre-inverses faster will be useful as well. The following lemma is adapted from the usual fast power series inversion method. <\lemma> Let and be clustered monic contact polynomials of > of degree in > and let l> be such that <\equation*> |]>;\>\\+|)>2*l-k>. Then for any k>, > is the pre-inverse of > at precision >. <\proof> Let \F quo> \>, \F rem> \>, \G quo> \>, \G rem> \>. From <\equation*> *\+F|)>**\+G|)>;\|]>;\>\\+|)>2*l-k>, we obtain <\equation*> *G*\>+*G+F*G|)>*\+F*G;\|]>;\>\\+|)>2*l-k>. Since >*G+F*G|)>\l> and >*G|)>\2*>, we deduce that <\equation*> *G;\|]>;\>\\+|)>2*e-k>. The conclusion follows from e>. <\lemma> Let ,l-1|}>>, let min>, and let \> be clustered of degree in> such that <\equation*> ;\|]>;\>\\+|)>2*l-k>. There exists a unique \|)>K-k>|]>;\>> such that <\equation*> *\|)>;\|]>;\>\\+|)>2*l-K>. It is given by <\equation*> => \>|)>*C|)> quo> \;\|]>;\>, where |)>K-k>> is defined by <\equation*> |]>;\>=\+C*\+|)>2*l-K>. <\proof> From <\equation*> F**\|)>=F*G+F**\, the condition for > becomes <\equation*> +F*;\|]>*\;\>\|)>l> and then <\equation*> C=> \>|)>*|)> quo> \;\|]>;\>. By Lemma, > \>> is the pre-inverse of > \>> at relative precision >. There exists a unique solution for > given by Lemma. <\proposition> The pre-inverse of a clustered contact polynomial \> of degree in > can be computed at relative precision \R*\0>> using <\equation*> O,\,d,l;\|)>*log l|)>+,\,d;max,\|)>|)> operations in > whenever r*\0>>. <\proof> From Lemma we can compute the pre-inverse of <\equation*> F quo> \=\+F at relative precision > using <\equation*> \,\,d;max,\|)>|)>+O|,\,d,l;\|)>+,\,d,l;\|)>|)>|\> operations in >. This makes it possible to apply Lemma > times, with >, in order to obtain the pre-inverse of using <\equation*> O,\,d,l;\|)>*log l|)> operations in >. As for usual polynomials, pre-inverses are used to reduce divisions to multiplications. <\lemma> Let be a clustered monic contact polynomials of > of degree in >, let be its pre-inverse, and let |)>2*l>>. The quotient A quo> F> can be computed as <\equation*> Q=G*A quo> \. <\proof> Let G*F-\\|)>l>>, and let A rem> F>, so we have <\equation*> A=Q*F+R. By multiplying both sides of this equality by we obtain <\equation*> G*A=Q*G*F+G*R=Q*+W|)>+G*R=Q*\+Q*W+G*R, whence > \>. <\proposition> Let be a clustered monic contact polynomial of > of degree r*\0>> in > and given at precision \R*\0>>. Given the pre-inverse of at precision >, the division of a contact polynomial of |)>2*l>> at precision > costs <\equation*> O,\,d,l;\|)>+,\,d,l;\|)>|)>. <\proof> This follows from Lemma. Throughout this section, |)>t>> represents a generalized contact tower as in Definition and t> is a fixed integer. We will assume that =\=0> so that |)>\\/|)>\\/|)>> is a tower of algebraic extensions. One important question is how to compute efficiently in /|)>>, provided that we know how to compute efficiently in /|)>>>. We will achieve this by representing elements in /|)>> as follows. <\definition> A > of /|)>> over /|)>> at precision \R*\0>> is made of the following data: <\itemize> a homogeneous primitive element > of /|)>> over /|)>> of valuation >, an initially separable monic polynomial \/|)>|)>> of degree *D>, of valuation *D|)>*R> at relative precision>, where has valuation >, polynomials ,\,w> in /|)>|)>D*D>> of valuations ,\,\> and at relative precision >. These data satisfy the following properties: <\itemize> ,\,\,w,\,w|)>-T|)> rem \|]>;\>=0>, |)>;\|]>*D|)>*R;\>=0>, ,\,\,w,\,w|)>-\*w|)> rem \|]>*\;\>=0>, for ,t>. Any element of /|)>> can uniquely be represented as an element of /|)>/|)>> via the following isomorphism: <\eqnarray*> /|)>/|)>>|>|/|)>>>||>|>>|>|>|i=h+1,\,t.>>>> In this section, we focus on the computation of an , which is simply a univariate-valued representation of minimal precision =R>. For this purpose, we define <\equation*> \\\|)>,\,\|]>/|)>,\,in|)>|)>, for ,t>. Computing an initial univariate-valued representation of /|)>> over /|)>> essentially amounts to computing ahomogeneous element > in > of valuation > such that the map <\eqnarray*> >|>|>>||>|>>>> is surjective. We call such a > a of > over >. Its minimal polynomial > over > is the monic generator of the kernel of this map. It is homogeneous of degree *D>. The surjectivity further implies the existence of homogeneous polynomials ,\,w> in D*D>> such that =w|)>> holds for ,t>. These polynomials are obtained as a byproduct of the computation of > and, together with >, give rise to the desired initial univariate-valued representation. It is classical that > is isomorphic to an algebra of the form |)>/>-\*T|)>>, where > is an algebraic extension of > and \\>; see6>. On the level of coefficients, we are therefore led to compute in so-called algebraic towers |)>t>> over >. Some relevant complexity results for such computations are recalled in section. Now direct computations in |)>/>-\*T|)>> can become expensive for towers of large heights, since every next floor gives rise to a constant overhead. This explains the interest of doing relative computations of > over >: using the univariate-valued representation, this will allow us to bundle all floors between level and into a single univariate extension, for which we can use fast univariate arithmetic, in the same spirit as the accelerated tower arithmetic from. In section, we first construct an isomorphism > of the form \|\>|)>,T|]>>/>-\*z,T*R>-\*T|)>,> where \\> and \|\>>. Here |\>> is a primitive algebraic extension of > that is isomorphic to > (in particular, computations in |\>> will be more efficient than computations in >). A natural candidate for a primitive-valued > for > over > is |)>>. Although this element is not always primitive, as we shall show in section, it turns out that we may always take \*T|)>> for some suitable value of> in|\>>. In section we show how to compute >, ,\,w>, and derive the desired initial primitive-valued representation of /|)>> over /|)>>. <\remark> From a mathematical perspective, it is not essential that > be homogeneous in Definition. Nonetheless, this is naturally the case for initial primitive-valued representations, and this property also simplifies computations. Furthermore, it turns out that we can keep the same primitive-valued element > when lifting our representation to higher precisions, as we will show in section below. A over > is a sequence |)>t>> with \\> and <\equation*> \\\|]>/|)>|)>,i=1,\,t, where the |)>\\|]>> are monic separable polynomials. We write> for the image of> in > and set \deg \> for ,t>. We will write <\equation*> S\s*\*s for the degree of > over >. The tower is said to be when we are further given> and > in |]>> of respective degreedeg \> anddeg \-1> such that the Bézout relation <\equation*> 1=u*\+v*\ holds, for ,t>. Throughout the rest of this paper, without loss of generality, we will freely assume that such towers are simplified so that \2> holds for ,t>. The cardinality of > will be written >. We will rely on the following complexity bound. <\proposition> Let \1/2> be a fixed positive constant, that can be taken arbitrarily close to. Given an explicitly separable tower |)>t>>, one multiplication and one inversion (when the inverse exists) in > costs <\equation*> >|)> operations in >. <\proof> If \|2>>, then the result directly follows from4>. Otherwise, with the notation of7>, we observe that the assumption on > is only needed to build primitive tower representations of degree\=O>|)>>, so it is sufficient to assume \|2>> instead. After that, if \|2>\S>, then we appeal toA.2>: the overhead only induces logarithmic factors in the complexity bound. The next lemma addresses the complexity for obtaining a univariate representation of> over > for a given t>. For the purpose of this paper, this complexity bound does not need to be sharp because *S> will be taken relatively small. <\lemma> Let t> and assume \*S|2>>. There exist ,\,\> in >, \\> separable and monic of degree *S>, and ,\,A\\S*S>> such that <\eqnarray*> >|>||\>\\/|)>>>|>|>|i=h+1,\,t>>>> is an >-algebra isomorphism and that <\equation*> *A+\+\*A-U|)> rem \=0. In addition, if we are given *S|2>> distinct elements in >, then such a > ,\,\>, >, ,\,A> of > over > can be computed using <\equation*> >**S|)>|)> operations in >. One conversion between > and |\>> costs >**S|)>|)>> operations in >. <\proof> If > is a field, then1> allows us to compute the univariate representation |\>> of > over > using *S|)>|)>> operations in >. In general, > is not a field, but panoramic evaluation can be used to simulate field operations in it. Precisely we appeal to1> in order to run the algorithm underlying1>: using <\equation*> >**S|)>|)> operations in >, we obtain a so-called panoramic splitting <\equation*> :\\\\\\\> of > and univariate representations >,\,\>>, >>, >,\,A>> for the restrictions of > over > for ,\>. We further know from1> that one evaluation of > and > takes >|)>> operations in >. Finally, we take \>,\,\|)>>|)>> for ,t>. We extend > to > coefficient-wise, and set \>,\,\|)>>|)>> and \>,\,A|)>>|)>> for ,t>. The cost of the conversions between > and |\>> is addressed in5>, which simplifies to *S|)>|)>> operations in >: these conversions only involve ring operations in >, so5> can be used even if > is not a field. It is known that > decomposes into a separable extension of > followed by purely ramified extensions; see for instance6>. Given t>, we use this decomposition in order to compute a univariate-valued representation of > over >. We let <\equation*> S\D/Rs\S*Si=1,\,t. We begin with a first technical rewriting of >, summarized in the following lemma. <\lemma> Let |)>t>> be an almost reduced, effectively separable and regular contact tower, let t>, and assume that we are given *S|2>> distinct elements in >. Using <\equation*> >**log D+*S|)>*log D|)>|)> operations in >, we can compute the following data: <\itemize> An effectively separable algebraic tower |)>t>> as in section; A univariate representation ,\,\>, >, ,\,A> of > over >, as in Lemma; ,c,\,c> in >, ,c,\,c> in |\>>, ,\,e> in >, ,\,f> in ,R-1|}>> and ,\,g> in ,R-1|}>> such that <\eqnarray*> :\>|>||\>|)>,T|]>/>-\*z,T*R>-\*T|)>,>>|>|>|*z>*T>i=1,\,h>>|>|>|*z>*T>*T>i=h+1,\,t>>>> is a |)>>-algebra isomorphism, that preserves the valuation, when setting |)>\R> and|)>\R>. One evaluation of > and > at a homogeneous element costs <\equation*> >**log D+S*S|)>|)> operations in>. <\proof> By13> we can compute a so-called initial expansion10> of |)>t>>, using <\equation> >*log*\*D|)>*log D|)>=>*ht \*log D|)> operations in >. In particular, combined with12>, we obtain: <\itemize> An effectively separable tower <\equation*> \\\\\\|]>/|)>|)>,i=1,\,t, where > is monic of degree \0> in |]>>. For ,t>, the class > of > in > is invertible and its inverse is known. For ,t>, an invertible \\> and its inverse, along with a |)>>-algebra isomorphism <\eqnarray*> :\>|>||)>|]>/>-\*z|)>>>>> that preserves the valuation for the weight > of > and such that one evaluation of> and > in valuation \R*\> with |\|>\1> costs <\eqnarray*> >*log|\|>+d*\|)>*R|)>*log D|)>>||>*ht \*log D|)>>>|||>*ht \*log D|)>,>>>> by. Note that this complexity bound further holds for any valuation, up to rescaling the arguments of > and > by a suitable power of . Then, we compute \\> invertible such that |)>|)>=\*T*R>> holds, and define the |)>>-algebra isomorphism <\eqnarray*> :\|)>|]>/>-\*z|)>>|>||)>,T|]>/>-\*z,T*R>-\*T|)>>>|>|>|.>>>> Thanks to Lemma, we may compute a univariate representation of > over > using <\equation> >**S|)>|)>=>**S|)>|)> operations in >. Lemma also ensures that one conversion between > and |\>> costs <\equation> >**S|)>|)>=>**S|)>|)>. In particular we compute \|)>> with this cost, and extend > coefficient-wise into |\>>: <\eqnarray*> |||)>,T|]>/>-\*z,T*R>-\*T|)>>>||>||\>|)>,T|]>/>-\*z,T*R>-\*T|)>.>>>> Finally, we set <\equation*> >>\|\>\\. For ,h>, we take \*R|)> quo R>, \*R|)> rem R>, and \\> such that <\equation*> >>|)>=\|)>=c*z>*T>. For ,t>, we compute > invertible in> such that <\equation*> \|)>=\*z>*T>, where \*\|)> quo R> and \*\|)> rem R>. Writing \ quo *R|)>> and \ rem *R|)>>, we obtain that <\eqnarray*> *z>*T>|)>>||*z>**R>|)>>*T> mod *R>-\*T|)>>>|||*\>*z>*T>*T>>>|||*\>*z>**z|)> quo R>*>T rem R>*T>>>|||*\>*\ quo R>*z+e quo R>*T rem R>*T>,>>>> so we take <\equation*> \\\*\>*\ quo R>,e\+e quo R,f\e rem R,g\f. In this way, +ht \|)>> products in > suffice to obtain > from >, that is |)>> products thanks to. The total cost of this construction of > is the sum of, , |)>> evaluations of >, >, > of cost, |)>> conversions from > to |\>> of cost, and |)>> further products in >. When evaluating > (resp. >) at a homogeneous element, the contribution of |\>> (resp. of |\>>) costs, since a homogeneous element of |)>,T|]>/>-\*z,T*R>-\*T|)>> is represented uniquely in the form *T*T>, where \>, \>, f\R>, g\R*R>. For such an element *T*T> we have <\equation*> *T*T|)>=c*\*z*T*R|)>>. Therefore, one evaluation of > or > costs <\equation> >*log R|)>=>*log D|)>. Finally, the cost of one evaluation of > or > at a homogeneous element is bounded by the sum of, , and. <\example> Let us consider the contact tower over \\=\/11*\> defined by 3>, \1/2>, \5/4>, \41/8>, and <\eqnarray*> |)>>|>|-z>>|,\|)>>|>|-z+z>>|,\,\|)>>|>|-z*\.>>>> At the first level of the contact tower, we have =2>, =1>, and we take |)>\x-1>, whence \\>, =1>, and <\equation*> \\\|)>|]>/-z|)>. Since the image > of > in > is primitive-valued, we may define <\eqnarray*> :\>|>||)>|]>/-z|)>>>|>|>|.>>>> At the second level, |)>> is rewritten -\> over >, whence =2> and =2>. We set ,x|)>\x-1>, hence \\|]>/-1|)>>, and obtain <\equation*> \\\|)>,y|]>/-z,y-\*z*y|)>, where > is the image of > in >. Taking the image > of *y> in > for a primitive-valued element, we define <\eqnarray*> :\>|>||)>|]>/-z|)>>>|>|>|*T>>|>|>|.>>>> For the third level of the contact tower, |)>> is rewritten -z*\> over >, whence =2> and =2>. We set ,x,x|)>\x-1> and obtain <\equation*> \\\|)>,y,y|]>/-z,y-\*z*y,y-\*z*y|)>. Taking the image > of *z*y> in > for a primitive-valued element, we define <\eqnarray*> :\>|>||)>|]>/-z|)>>>|>|>|*T>>|>|>|*z*T>>|>|>|*z*T.>>>> Now, let us build the map > of Lemma for 1>. For the univariate representation of> over>, we use the primitive element +2*x>, hence <\equation*> \=***, and obtain <\eqnarray*> :\>|>||\>\\/|)>>>|>|>|\2*U-3*U>>|>|>|\-U+2*U.>>>> We deduce the following expression for >: <\eqnarray*> :\>|>||\>|)>,T|]>/-z,T-A*T|)>,>>|>|>|>>|>|>|*z*T>>|>|>|*z*T.>>>> A natural candidate for a primitive element of minimal valuation for > over > is |)>>. Unfortunately, it is not always primitive, as illustrated by the following example. <\example> (Continued from Example) The minimal polynomial of |)>> over> is |)>=0>-A|)>*T|)>=-T|)>*+T|)>=-z|)>>, which is not separable. So |)>> is not a primitive element of > over >. We will show in the proof of Proposition that *T|)>> is indeed primitive for > over > for suitable values of> in|\>>. We begin with a technical lemma, where > stands for a new polynomial variable: in the context of Lemma, if is a primitive element of > over >, then |)>*R>>*\> is also primitive for almost all \\>. <\lemma> Let the assumptions and the notation be as in Lemma, assume that we are given*D|)>> elements in >, and let <\equation*> \,\|)>\Res,-|)>*R>>*\|)>\\,\|]>, where > represents the pre-image of > in S*S>>. Using <\equation*> >**D|)>|)> operations in >, we can compute \\>, |~>|)>\\,\|)>>, and \|]>S*S>> such that: <\enumerate-roman> > is invertible modulo >, |~>|)>> is separable, >|)>*R>>*\|)>-U=0 mod \>. <\proof> Let us first assume that > is a field. Given \\>, note that |)>> is the minimal polynomial of > in /|)>>. Therefore if > is a root of > in a suitable algebraic closure, then +\> is invertible if and only if |)>> is non-zero. Consequently at most *S> values of > do not satisfy property. Letting <\equation*> \|)>\Disc>,\|)>|)>\\|]>, the multiplicativity of the resultant yields <\eqnarray*> ,\|)>>|||)>=0>-+\|)>*R>*\|)>|)>>>||)>>|||)>=\|)>=0>>|\\>>>>>>\,\>|)>,>>>> where <\equation*> \,\>|)>\+\|)>*R>*\|)>-+\|)>*R>*\|)>. Since > is a separable extension of |)>>, the polynomial >-\*z> is separable in >, and therefore > is invertible in >. Consequently, if |)>=\|)>>, then the leading term of,\>|)>> is <\equation*> R*R*-\|)>*\|)>*\*R-1>. If |)>\\|)>>, then ,\>|)>> clearly has degree *R> in >. It follows that > is not the zero polynomial and that at most *R|)>**S|2>> values of > do not satisfy property.\ Since <\equation*> S*S+*R|)>**S|2>\*D|)> there exists a suitable value for > in any given set > of cardinality *D|)>+1>. In order to find a suitable value, it suffices to evaluate |)>*\|)>> at all the points of >. The polynomial ,\|)>> has degree S*S> in > and degree <\equation*> \R*R*S*S=*D|)> in >. So it can be computed using <\equation*> *D*S*S**S|)>|)>=*D|)>|)> operations in > by means of the Berkowitz algorithm applied to the Sylvester matrix of |)>*R>*\ rem \> and >. Since |)>> has degree <\equation*> \\*R|)>**S|)>=*D|)>|)>, it can be computed using <\equation*> *R|)>**S|)>|]>**S|)>|)>=*D|)>|)> operations in > by means of the Berkowitz algorithm. The evaluation of |)>*\|)>> at all the elements of > takes *D|)>|)>> operations in >; see10> for instance. From Proposition we know that one operation in > reduces to >|)>> operations in >. Consequently we obtain a suitable value for> using a total number of >**D|)>|)>> operations in >. In this way |)>*R>>*\> is a primitive element of |\>>, of minimal polynomial|~>|)>>. Therefore, there exists a unique |)>\\|]>S*S>> satisfying property. If> is a root of |~>|)>>, then > and -|)>*R>>*\> share a proper gcd, that is |)>>. In this case, it is known that this gcd is proportional to the first subresultant of > and -|)>*R>>*\>; see9>. Since the specialization at =\> of the first subresultant |)>*U-S|)>> of > and -|)>*R>>*\> coincides with the first subresultant of > and -|)>*R>>*\>, we deduce that |)>> is invertible modulo |~>|)>>. The polynomials > and > are minors of the Sylvester matrix of > and |)>*R>*\> rem \>; see2.1> for instance. They can thus be computed using *S|)>|)>> operations in >, again by means the Berkowitz algorithm. Computing |)>=S|)>/S|)> mod R,\|)>> further needs *S|)>> operations in >. It remains to handle the case where > is not a field. Panoramic evaluation can perform the above calculations1> still using >**D|)>|)>> operations in>: we obtain a panoramic splitting <\equation*> :\\\\\\\> of > and suitable values >,\,\>> in > for the restrictions of > over > for ,\>>, along with the corresponding |~>>> and >\\|]>S*S>>. We further know from1> that one evaluation of > and > takes >|)>> operations in >. Finally we take \>,\,\|)>>|)>>, |~>\|~>>,\,|~>|)>>|)>>, >,\,V|)>>|)>>, where > is implicitly extended to |]>> coefficient-wise. <\example> (Continued from Example) In Lemma, we can take =4> and <\eqnarray*> |~>|)>>||+5*+3*+4*+9>>||)>>||+10*.>>>> We put Lemmas and together in order to construct an initial primitive-valued element of> over>, written > in the following proposition. <\proposition> Let |)>t>> be an almost reduced effectively separable and regular contact tower, let t>, and assume that we are given *D|)>> distinct elements in >. Using <\equation*> >*+*D|)>|)>|)> operations in>, we can compute: <\itemize> a homogeneous polynomial > in > of valuation >, a monic separable homogeneous polynomial \\> of degree *D>, where has valuation >, homogeneous polynomials ,\,w> in D*D>> of respective valuations ,\,\>, such that <\equation*> ,\,\,w,\,w|)>-T|)> rem \=0, and <\equation*> in|)>,\,\,w,\,w|)> rem \=0,i=h+1,\,t. In other words, the map <\eqnarray*> :\>|>|/|)>>>|>|>|i=h+1,\,n>>>> is an isomorphism of >-algebras. One evaluation of > and > at a homogeneous element costs\ <\equation*> >*+D*D|)>|)> operations in >. <\proof> We set <\equation*> \\\|)>|]>/>-\*z|)>, which is another |)>>-algebra representation of > via the map :\\\> introduced in the proof of Lemma. A homogeneous element of > can be written *T>, where \>, \>, and f\R>. Consequently, the product of two homogeneous elements of > costs 2> operations in >. First, we build the isomorphism > of Lemma using <\equation> >**log D+*S|)>*log D|)>|)> operations in >. Then, we compute \\>, |~>>, and as in Lemma, using <\equation> >**D|)>|)> operations in >. This yields the following isomorphism of >algebras: <\eqnarray*> :\|]>/,T*R>-\*T|)>>|>|,|]>/|~>|)>,*R>-*T|)>>>||>||)>>>|>|>||)>+\|)>*>>||)>*R>>*\>|>|.>>>> From Lemma, we know that |)>> is invertible. Since |)>> is the minimal polynomial of > modulo >, the inverse of > modulo > is given by <\equation*> I\|)>-\|)>|-\|)>*X>|)>|)>, which can be obtained with *S|)>> ring operations in > plus the inversion of|)>>. The inverse of |)>+\> modulo |~>|)>> equals |)>|)> rem |~>|)>>, which can be computed using *S|)>|)>> further operations in >. On the other hand, computing |)>*R>>*\>> modulo > takes *S*log*R>|)>|)>> operations in>. A homogeneous element of |]>/,T*R>-\*T|)>> can be uniquely written *z*T*T>, where \\S*S>>, \>, f\R>, and g\R*R>. Consequently, computing <\equation*> *z*T*T|)>=C|)>|)>*|)>+\|)>*z*T* mod |~>|)> takes <\equation> *S|)>+S*S*log*R|)>|)> operations in >. The same cost bound applies to >.\ The characteristic polynomial of > over > is <\equation*> |~>\Res>|~>|)>,T*R>-*T|)>=T*S>*|~>*T*R>|)>, and its computation takes <\equation> O*S|)> operations in >. As seen in the proof of Lemma, the integer > is invertible in >, so|~>> is separable, and the map <\eqnarray*> :\,|]>/|~>|)>,*R>-*T|)>>|>|/|~>|)>>>|>|>|*T*R>>>|>|>|>>> is a >-algebra isomorphism. Let us consider a homogeneous element of /|~>|)>>, of the form <\equation*> T*i\S*S>c*z>*T>**R>|)>, where e\R*R>, \\>, \\>, f\R>, and e+R*+i|)>> is independent of . The computation of <\eqnarray*> ||*i\S*S>c*z>*T>**R>|)>|)>>>|||*i\S*S>c*z>*T>**R>|)> mod *R>-*T|)>>>|||*i\S*S>c*z>*T+i>*>>|||*i\S*S>c*\+i|)> quo R>*z++i|)> quo R>*T+i|)> rem R>*>>|||i\S*S>c*\+i|)> quo R>*|)>*z|)> quo R>*T|)> rem R>*,>>>> takes <\equation> *S|)> operations in >. By reverting these calculations, the same cost is achieved for one evaluation of>. We extend the map > to > coefficientwise, and compute <\equation*> \\\|~>|)>. Composed with >, we finally obtain the desired initial univariate-valued representation of > over >: <\equation*> \\\\:\\\/|)>. The total cost of the construction of Y, >, >, and > is bounded by the sum of and , that is <\equation*> >*+*D|)>|)>|)> operations in>. The cost of one evaluation of \\\> or \\\|)>> is at most by the sum of, >, and the costs for > and > given in Lemma, that is bounded by <\equation*> >*+D*D|)>|)> operations in >. Finally we take \\\\|)>> and \\\\\|)>>, for ,t>. <\example> (Continued from Example). We calculate the representation of > over> given in Proposition. The initial primitive-valued element is <\eqnarray*> >||*T|)>>>|||*\*\*\+*\*\+z|)>*\>>>> and the corresponding initial univariate-valued representation is <\eqnarray*> >||+3*\*T+6*z*T+2*z*\*T+9*z>>|>||*\*T+8*T+5*\*T+2*z*T>>|>||*\*T+9*z*T+4*z*\*T+z*T.>>>> In this section we consider a generalized contact tower |)>t>> as in section and an index t> such that <\equation*> \=\=0. It follows that /|)>> has dimension *D> over /|)>>, and that /|)>> has dimension > over |)>>. We are interested in computing a primitive-valued element representation of /|)>> over /|)>>. Using Proposition, we first compute an initial univariate-valued representation of =\|)>,\,\|]>/|)>,\,in|)>|)>> over =\|)>,\,\|]>/|)>,\,in|)>|)>>>. This yields a homogeneous polynomial > in > of valuation >, a monic separable homogeneous polynomial \\> of degree *D>, where has valuation >, and homogeneous polynomials ,\,w> in D*D>> of respective valuation ,\,\>, such that <\equation*> ,\,\,w,\,w|)>-T|)> rem \|]>;R>=0, and <\equation*> ,\,\,w,\,w|)>-\*w|)> rem \|]>*\;R>=0,i=h+1,\,t. Then, given a target precision \R*\0>>, we will use a suitable Hensel lifting in order to obtain |}>>\/|)>|)>> monic of degree *D>, and polynomials |}>>,\,w|}>>> in /|)>|)>D*D>> such that: <\itemize> |}>>|)>=\>, and |}>>|)>=in|)>>, for ,t>, ,\,\,w|}>>,\,w|}>>|)>-T|)> rem \|}>>|]>;\>=0,> ,\,\,w|}>>,\,w|}>>|)>-\*w|}>>|)> rem \|}>>|]>*\;\>=0,i=h+1,\,t.> We begin by presenting our lifting strategy, which is naturally based on the Newton operator of the map ,\,\|)>\-\*\,\,\-\*\|)>>. Let > denote a commutative ring, let \,\,x|]>> and let ,\,y> be independent variables. Expanding <\equation*> f,\,x|)>=f+-y|)>,\,y+-y|)>|)> in terms of the powers of -y|)>> in ,\,x,y,\,y|]>> yields <\equation> f,\,x|)>=\0,\,e\0>,\,e|)>> f|)>,\,y|)>*-y|)>>*\*-y|)>>, where ,\,e|)>> f> are polynomials in ,\,y|]>> of total degree deg f-+\+e|)>>. This operator ,\,e|)>>> is usually called the of orders ,\,e|)>>. Applied to a monomial >*\*x>>, where \0,\,k\0>, we have <\equation*> D,\,e|)>>>*\*x>|)>=|e>*\*|e>*x-e>*\*x-e>. Note that <\equation*> e!*\*e!*D,\,e|)>> f=+\+e> f|\ x>*\*\ x>>. For any ,\,a|)>\\>, the following Taylor expansion holds after replacing > by > in: <\equation> f,\,x|)>=\0,\,e\0>,\,e|)>> f|)>,\,a|)>*-a|)>>*\*-a|)>>. Consider the map <\eqnarray*> >\\|)>,\,\|]>>|>||)>,\,\|]>>>|>>|>>|>>|>>>>>>|>||)>-\*\>>|>>|,\,\|)>-\*\>>|,\,\|)>>>>>>,>>>> whose Jacobian matrix is <\equation*> \\|||||||| \|\ \>>|-\>||>|>|>|>|>| \|\ \>>|>| \|\ \>>|>>| \|\ \>>|>|| \|\ \>>>>>>. The corresponding Newton iterator is the map <\equation*> >>|>>|>>>>>\>>|>>|>>>>>-\\>,\,\|)>. In order to quantify the convergence of this operator, we begin by studying the valuations of the determinant and the adjunct matrix of >. <\lemma> For all with k\l\t> we have <\equation*> in|||||||| \|\ \>>|-\>||>|>|>|>|>| \|\ \>>|>| \|\ \>>|>>| \|\ \>>|>|| \|\ \>>>>>>=in \|\ \>*\* \|\ \>|)>. <\proof> For simplicity, the proof is presented for and . The general case only involves syntactic adjustments. The usual expansion of the determinant of > yields <\equation> det \=\\>>*i\t>\>, where > is the permutation group of ,t|}>>, represents the usual signature function, and > stands for the entry > in >. Note that a product \>> vanishes whenever \i+1> for some in ,t-2|}>>, and that the identity permutation > is the only element of > that satisfies \i> for all ,t>. Now let >> denote the subset of permutations > that satisfy \i+1> for all ,t-1> and such that the latter inequality is an equality for exactly values of . The expansion of the determinant rewrites into <\equation*> det \= \|\ \>*\* \|\ \>+k\t>\\>>>*i\t>>|=i+1>>>>>>\*i\t>>|\i>>>>>> \|\ \>>. The valuation of the first term equals -1|)>*\>. For ,t-1|}>> and \\>>, wehave <\eqnarray*> |i\t>>|\i>>>>>> \|\ \>>|)>>|>|i\t>>|\i>>>>>>d*\-i\t>>|\i>>>>>>\>>>|||i\t>d*\-i\t>>|=i+1>>>>>>d*\-i\t>\>+i\t>>|=i+1>>>>>>\>>>|||i\t>-1|)>*\+i\t>>|=i+1>>>>>>-d*\|)>>>||>| \|\ \>*\* \|\ \>|)>,>>>> which concludes the proof. <\lemma> Let > represent the adjunct matrix of >. The entry > of > has valuation <\equation*> \val|)>+\-d*\. <\proof> The entry > of > is > times the >-minor > of >. When k>, we have <\equation> \=||||||||||||||||||||| \|\ \>>|>||||||||>|>|>|>|||||||>| \|\ \>>|>| \|\ \>>|>||||||>| \|\ \>>||>|| \|\ \>>|>||||>|>|||||>|>|||>| \|\ \>>|||>||| \|\ \>>|||>| \|\ \>>|||>||| \|\ \>>|>||>| \|\ \>>|||>|||| \|\ \>>|>|>|>||||||||>|>>| \|\ \>>|||||>|||| \|\ \>>>>>>. Let ,\,\|)>>> denote the set of bijections <\equation*> \:,t|}>\\,t|}>\ such that \i+1>, > (resp. >, >) is the number of indices ,l-1|}>> (resp. ,k-2|}>>, ,t-1|}>>) such that =i+1>. We expand the determinant as follows <\equation*> \=+\+\\t-1>\\,\,\|)>>>|)>>*i\t>>|k,l>>|=i+1>>>>>>\*i\l>>|\i>>>>>> \|\ \>>*i\k>>|\i>>>>>> \|\ \>>*i\t>>|\i>>>>>> \|\ \>>. Then for all \\,\,\|)>>> we verify that <\eqnarray*> ||i\l>>|\i>>>>>> \|\ \>>*i\k>>|\i>>>>>> \|\ \>>*i\t>>|\i>>>>>> \|\ \>>|)>>>||>|i\t>>|l>>|\i>>>>>>d*\-i\t>>|l>>|\i>>>>>>\>>>|||i\t>>|l>>>>>>d*\-i\t>>|l>>|=i+1>>>>>>d*\-i\t>>|l>>>>>>\>+i\t>>|l>>|=i+1>>>>>>\>>>|||i\t>>|l>>>>>>d*\-i\t>>|k>>>>>>\+i\t>>|l>>|=i+1>>>>>>-d*\|)>>>||>|i\t>>|l>>>>>>d*\-i\t>>|k>>>>>>\>>|||i\t>-1|)>*\|)>+\-d*\.>>>> Thanks to Lemma, this concludes the proof of the lemma when k>. If k>, then the determinant <\equation*> \=||||||||||||||||||||||| \|\ \>>|>||||||||>|>|>|>|||||||>| \|\ \>>|>| \|\ \>>|||||||>| \|\ \>>|>| \|\ \>>|>||||||>| \|\ \>>||>| \|\ \>>|>|||||>|>||||>|>||||>| \|\ \>>|||>|| \|\ \>>|>|||>| \|\ \>>|||>|||| \|\ \>>|>|>|>||||||||>|>>| \|\ \>>|||||>|||| \|\ \>>>>>>, is block triangular (with three blocks). Applying Lemma to the first and third blocks, we obtain <\equation*> in|)>=*in \|\ \>*\* \|\ \>* \|\ \>*\* \|\ \>|)>. It follows that <\equation*> val \=i\t>-1|)>*\-i\l>-1|)>*\\i\t>-1|)>*\-d*\+\, since -1|)>*\=d*\--d*\|)>-\--d*\|)>-\\d*\-\>. The above valuation estimates now allow us to study of the behavior of the Newton operator of >> from precision > to >. For this purpose, let > be a valued algebra over |)>>. For ,t>, let \|]>;\>> be such that <\eqnarray*> ,\,a|)>-\*a|]>*\;\>>||,\,a|)>-\*a|]>*\+\>=0>>>> and ,\,a|)>> is invertible of valuation |)>>. Still for ,t>, we are looking for \|]>;2*\>> such that |]>;\>=a> and <\equation> ||,\,|)>-\*|]>*\;2*\>>||,\,|)>-\*|]>*\+2*\>=0>>>>> Setting \-a\|]>+\;\>>, the first order Taylor expansion of > yields <\eqnarray*> ,\,|)>>||,\,a|)>+\,\,a|)>*>>|>>|>>>>>+,|)>>>|>>|,\,a,,\,|)>>>>>>,>>>> where > represents the sum of the terms of order at least : <\equation*> \,\,a,,\,|)>\+\+e\2>,\,e|)>> \|)>,\,a|)>*>*\*>. Since ,\,e|)>> \|)>,\,a|)>|)>\d*\-e*\-\-e*\> and |)>\\+\>, for ,t>, we have <\eqnarray*> ||,\,a,,\,|)>|)>>>||>|+\+e\2>*\-e*\-\-e*\+e*+\|)>+\+e*+\|)>|)>>>|||+\+e\2>*\+e*\+\+e*\|)>>>||>|*\+2*\.>>>> After left multiplying both sides of by ,\,a|)>>, we obtain that <\eqnarray*> ||,\,a|)>*\,\,|)>>>|||,\,a|)>*\,\,a|)>+det \,\,a|)>*>>|>>|>>>>>>>|||+adj \,\,a|)>*,|)>>>|>>|,\,a,,\,|)>>>>>>.>>>> Regarding \P\Q and \P>\Q component-wise, Lemma yields <\equation*> v,\,a|)>*\,\,|)>|)>\|)>+\+2*\>>|>>||)>+\+2*\>>>>>, and <\equation*> v,\,a|)>*,|)>>>|>>|,\,a,,\,|)>>>>>>|)>\|)>+\+2*\>>|>>||)>+\+2*\>>>>>. It follows that <\eqnarray*> ,\,a|)>*\,\,a|)>+det \,\,a|)>*>>|>>|>>>>>|)>>|>||)>+\+2*\>>|>>||)>+\+2*\>>>>>.>>>> Consequently, under the constraints on the valuations of the >, equations are equivalent to <\equation> >>|>>|>>>>>\-,\,a|)>|det \,\,a|)>>*\,\,a|)>. Finally we have shown that the > exist and are uniquely determined by <\equation*> >>|>>|>>>>>=|]>+2*\>>>|>>||]>+2*\>>>>>>=|]>+\;\>>>|>>||]>+\;\>>>>>>. In other words <\equation*> >>|>>|>>>>>=>>|>>|>>>>>+|]>+\;\>>>|>>||]>+\;\>>>>>>. is the unique solution of. We are now ready to extend Proposition for the computation of univariate-valued representations at higher precisions. The following algorithm is adapted from4>. <\specified-algorithm> <\description-compact> An effectively separable and regular contact tower |)>t>>. An integer t>, and a relative precision \R*\0>>. A univariate-valued representation of /|)>> over /|)>> at precision >. =\=0>, and we are given *D|)>> distinct elements in >. <|specified-algorithm> <\enumerate> Compute ,\,w,\,w> as in Proposition and let \R>. While \\> do: <\enumerate> Compute ,\,|)>>> modulo > at relative precision > as ,\,\,w,\,w|)>|det \,\,\,w,\,w|)>>>*\,\,\,w,\,w|)>>. Compute \+|]>;2*\>>, for ,t>. \,\,\,,\,|)>-T|)> rem \|]>;2*\>>. Compute |\>\-*\|)> rem \|]>*D|)>*R;2*\>>. For ,t>, compute >\-*w|)> rem \|]>;2*\>>. Replace > by ,\|)>>, > by |\>> and > by >>, for ,t>. Return ,\,w,\,w>. <\proposition> Algorithm is correct. If > is almost reduced, then it performs <\eqnarray*> ||>**D|)>*ht \|)>>>|||,\,d;max,\|)>|)>**\,1|)>*D*D|)>*D*D*ht \*log D|)>>>>> operations in >. In addition, the polynomials ,w,\,w> of a univariate-valued representation are uniquely determined at precision > by the contact tower > and the choice of >. The constant coefficient > is initially invertible in > of valuation *D|)>*R>. <\proof> Let <\equation*> \\/|)>|)>/|)> and let ;\|)>> be the extension of ;\|)>> to >, so |)>=R>. Proposition gives us aunivariate-valued representation at precision =R>. Note that > is homogeneous, and that> and the > are uniquely determined by the choice of > at this precision. In step2.a, the Newton iteration is applied to <\eqnarray*> >|>|,i=1,\,h>>|>|>|,i=h+1,\,t.>>>> Note that =0>, for ,h>. At the end of step2.b, we obtain |]>;\>=|]>;\>> and <\equation*> ,\,\,,\,|)>-\*|)> rem \|]>*\;2*\>=0, for ,t>. The > are uniquely determined by these properties, under the constraints on the valuation of the >. By construction, > has valuation R+\> and therefore |\>,>,\,>> coincide with ,w,\,w> at precision >. It follows that <\eqnarray*> |\>|)> rem \|]>*D|)>*R;2*\>>|||\>+*|\>|)>|)> rem \|]>*D|)>*R;2*\>>>|||-\*-|\>|)>|)> rem \|]>*D|)>*R;2*\>>>|||>>> and that <\eqnarray*> >|)> rem \|]>;2*\>>||>+*>|)>|)> rem \|]>;2*\>>>|||-\*->|)> rem \|]>;2*\>>>|||,>>>> for ,t>. It follows that <\eqnarray*> ||,\,\,>,\,>|)>-\*>|)> rem |\>|]>*\;2*\>>>|||,\,\,|)>,\,|)>|)>-\*|)>|)> rem \|)>|]>*\;2*\>>>|||,\,\,,\,|)>-\*|)> rem \|)>|)>|]>*\;2*\>>>|||>>> holds for ,t>, and similarly that <\eqnarray*> ||,\,\,>,\,>|)>-T|)> rem |\>|]>;2*\>>>|||,\,\,,\,|)>-|)>|)> rem \|)>|)>|]>;2*\>>>|||>>> This proves that the values for ,\,w,\,w> returned by the algorithm actually constitute a univariate-valued representation of /|)>> over /|)>> at precision >. We are done with the correctness. The latter calculations further show that such a univariate-valued representation |\>,>,\,>> in terms of > is unique. Let us now assess the complexity. By Proposition we compute ,\,w,\,w> at precision > in time <\equation> >**D|)>*ht \|)>. Assuming that operations in /|)>> with relative precision > can be done using ,\,d;max,\|)>|)>>> operations in>, one operation in /,\|)>> at relative precision > does not exceed <\equation*> O,\,d;max,\|)>|)>**\,1|)>**D|)>|)>|)>, by using the schoolbook methods, thanks to Lemma. For ,t>, the evaluation of all the > and of the Jacobian > at ,\,\,w,\,w|)>> modulo > at relative precision > costs <\equation> *\,1|)>*D*D|)>*D*D*t|)> operations in /|)>>. The determinant and the adjunct matrix of ,\,\,w,\,w|)>> modulo> can be obtained using <\equation> *\,1|)>*D*D|)>*t|)> operations in /|)>> by using the Berkowitz algorithm. By Lemma the initial inverse of <\equation*> det,\,\,w,\,w|)>|)> can be computed as the initial of <\equation*> |)>*\*\,\,\,w,\,w|)>|)> rem \, in time bounded by, where > represents the initial inverse of \|\ \>>. The inverse of ,\,\,w,\,w|)>> at precision > can be lifted efficiently via the usual Newton iteration, using *\|)>|)>=O|)>> operations in /,\|)>>. Since > is homogeneous in |)>,\,\|]>,\,d|)>>>, its evaluation in step2.c does not exceed. Computing |\>> and >,\,>> takes *\,1|)>*D*D|)>*t|)>> further operations in/|)>>. We conclude by adding the costs of all these intermediate tasks. <\example> (Continued from Example) We are interested in lifting the univariate-valued representation of Example with =\=0>, =1>, and precision =1/4>. We enter the lifting at precision with <\eqnarray*> >||*\*\*\+*\*\+z|)>*\>>|>||+3*\*T+6*z*T+2*z*\*T+9*z>>|>||*\*T+8*T+5*\*T+2*z*T>>|>||*\*T+9*z*T+4*z*\*T+z*T.>>>> We have <\eqnarray*> ,w|)>-w rem \>||>>|,w,w|)> rem \>||>>> With the notation of Algorithm, we perform following Newton iteration at relative precision =1/4>: <\eqnarray*> >>|>>>>>>||>|>|*w>|>>>>>*,w|)>-w>>|,w,w|)>>>>>> mod \>>|||*\*T+7*T+7*\*T+8*z*T>>|>>>>>.>>>> Then, we obtain <\equation*> \=3*\*T+T+8*\*T+2*T, and deduce the univariate-valued representation at relative precision =1/4>: <\eqnarray*> |\>>||+\*T+3*\*T+7*z*T+6*z*T+2*z*\*T+9*z>>|>>||*\*T+6*z*\*T+8*T+7*\*T+5*\*T+2*z*T+2*z*T>>|>>||*\*T+7*z*\*T+7*z*T+9*z*T+6*z*\*T+4*z*\*T+z*T+z*T.>>>> For this section we are given a generalized contact tower |)>t>>, of the form <\equation*> \\\|)>,\,\|]>/|)>-\*\,\,\|)>-\*\,\,\,\,\|)>-\*\|)>. We wish to compute in > at relative precision \0>, which leads us to assume that =1> if -d*\\\> and =0> otherwise, for ,t>. The complexity bounds of section for computing with contact polynomials grow exponentially with the height of the tower. In order to circumvent this dependency on, we will replace consecutive levels of the tower of low degree by a single level. This tactic was used before in the simpler context of towers of algebraic extension and gave rise to so-called accelerated tower arithmetic. Unfortunately, when compressing several levels in a contact tower, the resulting \Pflattened\Q tower will not be of contact type. There will be two main types of flattenings. The first type introduces an algebraic extension which violates the condition that \d*\> for all . The second type of flattening gives rise to a defining polynomial that is not initially separable and that will necessitate increasing the relative precision. In order to cover these two types of flattenings, plus a trivial third one, we need the following technical definition. For simplicity the tower will be assumed almost reduced, and the first level (that was allowed to be of degree one) is left unchanged. <\definition> Let |)>t>> be an almost reduced generalized contact tower such that \1> if -d*\\\> and \0> otherwise, for ,t>. A tower |~>|)>>> of the form <\equation*> |~>\\|)>|~>,\,|~>|]>/|~>|~>|)>-|~>*|~>,|~>|~>,|~>|)>-|~>*|~>,\,|~>|~>,\,|~>|)>-|~>*|~>|)>, for ,> is a > for |)>t>> at relative precision > if <\enumerate> |~>\\|)>|~>,\,|~>|]>,\,|)>>|~>|]>> is monic of degree in |~>> written >, for,>>, with |~>|~>|)>=\|~>|)>>. There exists an integer sequence <\equation*> 0=i\i\\\i>=t, with =1>, and a sequence of |)>>-algebra isomorphisms <\equation*> \:\>\|~> with the following properties for ,>: <\description> >>>|~>=\>>; >>>The restriction of > to >|)>1>> coincides with >; >>>The projection of |)>|~>,\,|~>|]>,\,|)>>> to |~>> is injective and equals >|)>1>|)>>;\ >>>+1>|)>=|~>>; >>>If > and >=1> then +1>|)>=|~>>; >>>|~>-|~>>|)>;\>|)>\*v|~>|)>;\>|)>> For ,>, there exists |~>\\|)>|~>,\,|~>|]>,\,|)>>|~>|]>> monic of degree > in |~>> such that the image of |~>*|~>> in |~>> belongs to the image of <\equation*> |~>>+\|)>|~>,\,|~>|]>,\,|)>>> in |~>>, and that |~>-|~>>|)>;\>|)>\*v|~>|)>;\>|)>>. Property imposes the natural image +1>|)>=|~>>. If >=|~>=1>, then naturally extends this requirement to >; the image +1>|)>> might have been chosen more arbitrarily if >=|~>=0>. Property ensures that the defining polynomial |~>> is clustered as an element of >>. The polynomial |~>> is required to be the clustered pre-inverse of|~>>in>>. As a consequence of the definition, the pre-image > of an element |~>> can be written <\equation*> \=0>b*\+1>, where \>|)>1>>. The representation of in the form <\equation*> A=0>a*|~>, where =\|)>\\|)>|~>,\,|~>|]>,\,|)>>>, will be said . In particular we note that =d+1>*\*d>>, for ,>, that =d> may be equal to one, and that \2> for ,>. In the rest of the paper, the canonical representation of an element of |~>> will be written A>. We will also write |~>> A|)>> for its degree in|~>> and |~>|)>l>> for the elements whose canonical representative has degree l> in |~>>. For ,>, we endow |)>|~>,\,|~>|]>> with the weighted valuation, written >, defined by <\eqnarray*> |~>>|>|>>| |~>>|>||~>|)>;\>|)>,j=2,\,k+1.>>>> In particular implies |~>=\+1>>. For j\k>, by we have |~>|)>\>|)>1>>, while >> coincides with > on >|)>1>> by. Consequently, <\equation> val> |~>=v>|~>|)>;\|)>=v|~>|)>;\>|)>=val |~>,j\k\. We set |~>\\> and |~>\val |~>> for ,>. If >, note that implies <\equation> |~>=val |~>=v|~>|)>;\>|)>=\+1>,\>=1. Given \\|)>|~>,\,|~>+1>|]>> the notation ;\|)>|~>,\,|~>+1>|]>|]>;\>> will stand for the truncation of > from valuation> and precision > with respect to >>. <\example> Let us consider the following contact tower of height 4> over \\>: <\eqnarray*> |)>>||-1-z>>|,\|)>>||-z>>|,\,\|)>>||-z*\>>|,\,\,\|)>>||-z*\,>>>> with =\=\=\=1>, so =1>, =d=d=2>, =0>, =1/2>, =5/4>, =21/8>, \+\>. By definition, the first level of the flattening is \Ptrivial\Q, with |~>|~>|)>\\|~>|)>>: <\eqnarray*> :\>|>||~>>>|>|>||~>>>|>|>||~>.>>>> Then, we build a second level, that will be called of \Psecond type\Q in section, with =1>, \3>, <\equation*> |~>|~>,|~>|)>\\|~>,|~>,\|~>,|~>|)>|)>, and <\eqnarray*> :\>|>||~>>>|>|>||~>>>|>|>||~>>>|>|>||~>|~>,|~>|)>>>|>|>||~>=\|~>,|~>,\|~>,|~>|)>|)>>>>> The third level of the flattening is \Ptrivial\Q, that is \4>, <\equation*> |~>|~>,|~>,|~>|)>\\|~>,|~>,\|~>,|~>|)>,|~>|)>, and <\eqnarray*> :\>|>||~>>>|>|>||~>>>|>|>||~>>>|>|>||~>|~>,|~>|)>>>|>|>||~>=\|~>,|~>,\|~>,|~>|)>|)>>>|>|>||~>=|~>|~>,|~>,|~>|)>.>>>> We have |~>=\>, |~>=\>, |~>=\>. Assume that |~>|)>>> is a flattening for |)>t>> at precision >. For any ,>, we note that |~>>|)>\j>> is again a flattening for >|)>\i>> at precision >. Flattenings will be built by induction on the height, so it will be useful to keep in mind that <\eqnarray*> >>||>+2>,\,\+1>|]>/+1>,\,\+1>|)>-\+1>*\+2>,\,|\>>>|||>+2>,\,\+1>|]>/>>\>,\,\>|)>-\>*\+1>||)>>>||~>>|||~>|~>|]>/|~>|~>,\,|~>|)>-|~>*|~>|)>.>>>> <\lemma> The canonical representative > of an element of |~>>> satisfies <\equation*> val> \v>|)>;\|)>. <\proof> We first handle the case where \|~>>|)>1>>. Let us write <\equation*> =k\>>*|~>>, where ,\,>-1>> are in |~>-1>|)>1>>. The proof is done by induction on >. The case =0> is clear. Let us assume that the lemma holds for -1\0>. We verify that <\eqnarray*> >|)>;\|)>>||k\>>\-1>|)>*\>|~>>|)>;\|)>)>>>||>|k\>>-1>|)>;\-1>>|)>+v>|~>>|)>;\|)>|)>>>||>|k\>>-1> +k*val> |~>>|)>>>|||k\>>> +k*val> |~>>|)>)>>>|||> .>>>> Now consider a general =0>*|~>+1>>, written canonically: <\eqnarray*> >|)>;\|)>>||0>\>|)>*\;\|)>)>>>||>|0>>|)>;\|)>+k*v;\|)>|)>)>>>||>|0>> +k*val> |~>+1>|)> and)>>>|||> .>>>> We define the following important quantity, called the of >, that measures the loss of precision when converting contact polynomials via >: <\equation> dct \\max>|)>1>>>|)>-val|)>|)>|)>. By Lemma the backward conversion does not cause any precision loss. If is in > and if =0>*|~>+1>> is the canonical representative of >>, then we have <\eqnarray*> > >||0>> +k*\|)>>>||>|0>>|)>;\|)>-dct \>+k*\|)>>>||||)>-dct \>.>>>> In order to multiply two elements of |)>1>>, we shall first convert them into their canonical representations in |~>>|)>1>>, then compute their product in |)>|~>,\,|~>|]>>, next reduce this product into its canonical representative in |~>>>, and finally convert the result back into |)>2>>. The following proposition details the extra precision needed for this approach. <\proposition> Let and be in |)>1>> at relative precision >, let > and > be the canonical representatives of >> and >>, let \*>, and let \dct \>>. Then the product at relative precision> can be computed using <\eqnarray*> |||]>|)>+v|)>;\>>>|||>> ;\|)>|~>,\,|~>+1>|]>|]>|)>+v|)>-\;\+\>|)>|]>|)>+v|)>;\>.>>>> <\proof> By we have > \v|)>-\> and > \v|)>-\>. By Lemma, the terms of > > (resp.of > >) have valuation v|)>+\> (resp.v|)>+\>). In other words, we have <\eqnarray*> >||;\|)>|~>,\,|~>+1>|]>|]>|)>-\;\+\>>>|>||;\|)>|~>,\,|~>+1>|]>|]>|)>-\;\+\>,>>>> hence <\equation*> =;\|)>|~>,\,|~>+1>|]>|]>|)>+v|)>-2*\;2*\+2*\>. Since > equals >> in |~>>>, we have <\equation*> val>> |)>\v|)>-\\v|)>+v|)>-\. On the other hand, from Lemma, we know that if > is the canonical representative of an element of |~>>> of valuation > \v|)>+v|)>+\> then <\equation*> v|)>;\|)>\v|)>+v|)>+\. Consequently, we may recover <\equation*> |]>|)>+v|)>;\>, from > at precision +\>.\ The rest of this section is dedicated to speed up multiplication and Euclidean division using flattenings. Given \\|)>|~>,\,|~>>|]>>, we define its > P> by <\eqnarray*> > P>|>|j\,k,\,k>>,\,k>>|)>;\>|)>+k*val> |~>+\+k>*val> |~>>|)>,>>>> where for every ,>, the ,\,k>>> are the coefficients of the canonical expansion <\equation*> =,\,k>>,\,k>>*|~>>*\*|~>>>>>. If \|~>>|)>1>> is reduced, then we have <\equation*> nval> =v>|)>;\|)>. Using we also note that <\equation*> nval> ,\,k>>\nval> P-k*val> |~>-\-k>*val> |~>>, for all ,\,k>>. <\lemma> Let > and > be the canonical representatives of two elements of |~>>|)>1>>. Then <\equation*> \*\\|)>|~>,\,|~>>|]>-1,\,2*>-1|)>> has nested valuation <\equation*> nval> \nval> +nval> . <\proof> Consider the canonical representations <\eqnarray*> >||\,\,k>\>>,\,k>>*|~>>*\*|~>>>>>>|>||\,\,k>\>>,\,k>>*|~>>*\*|~>>>>>.>>>> Given in ,\,k>>, we have <\equation*> v>,\,k>>|)>;\|)>\v>|)>;\|)>-k*val> |~>-\-k>*val> |~>>. Since ,\,k>>\\|)>|~>,\,|~>|]>,\,|)>>> the pre-image >,\,k>>|)>> belongs to >|)>1>>, so <\equation*> v>,\,k>>|)>;\|)>=v,\,k>>|)>;\>|)>. Similar properties hold for >. From <\equation*> ,\,k>>=+f=k,\,e>+f>=k>>,\,e>>*,\,f>>, we deduce that <\eqnarray*> ||,\,k>>|)>;\>|)>>>||>|+f=k,\,e>+f>=k>>v,\,e>>|)>;\>|)>+v,\,j>>|)>;\>|)>>>||>|>|)>;\|)>+v>|)>;\|)>-k*val> |~>-\-k>*val> |~>>,>>>> which concludes the proof. The goal of this subsection is an algorithm to compute > > efficiently. It is adapted from Lebreton's method for algebraic towers. We say that a flattening |~>|)>>> for |)>t>> is given at relative precision \R*\0>> and defect bound \dct |~>>> when the following data are known: <\itemize> |~>;\|)>|~>,|~>|]>|]>*|~>-\;\+\>,\,|~>>;\|)>|~>,\,|~>+1>|]>|]>>*|~>>-\;\+\>>, |~>;\|)>|~>,|~>|]>|]>*|~>-\;\+\>,\,|~>>;\|)>|~>,\,|~>+1>|]>|]>>*|~>>-\;\+\>>. Since |~>\*|~>-\> we have <\equation*> |~>;\|)>|~>,\,|~>|]>|]>*|~>+\>=|~>;\|)>|~>,\,|~>|]>|]>*|~>-\;\+\>, for ,>. The same property holds for the truncations of the |~>>. <\specified-algorithm> <\description> An almost reduced generalized contact tower |)>t>> at relative precision \R*\0>>, a flattening |~>|)>>> for |)>t>> at relative precision > and defect bound \dct |~>>>, \|)>|~>,\,|~>+1>|]>-1,\,2*>-1,1|)>>|]>-2*\;\+2*\>> with> \\>. > ;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>\\|)>|~>,\,|~>+1>|]>,\,>,2|)>>>. <|specified-algorithm> <\enumerate> If =0> then return ;\|)>|]>-\;\+\>>. Write =+*|~>>+\+>-2>*|~>>>-2>> with <\equation*> ,\,>-2>\\|)>|~>,\,|~>-1>|]>-1,\,2*-1>-1|)>>. For ,>-2>, recursively compute <\equation*> +|~>-1>**|~>>\-1> >+i>;\|)>|~>,\,|~>>|]>|]>->+i|)>*|~>>-\;\+\> and then > as <\equation*> |~>-1>*+|)>+|~>-1>*+|)>*|~>>+\+|~>-1>*>-3>+>-2>|)>*|~>>>-2>+|~>-1>*>-2>*|~>>>-1>. Compute \*|~>>;\|)>|~>,\,|~>+1>|]>|]>>*|~>>-\;\+\>> as <\equation*> *|~>>>>+*|~>>;\|)>|~>,\,|~>+1>|]>|]>>*|~>>-\;\+\>-|~>>>>|)>. \; Write =+*|~>>+\+>-1>*|~>>>-1>> with <\equation*> ,\,>-1>\\|)>|~>,\,|~>-1>|]>-1,\,2*-1>-1|)>>. For ,>-1>, recursively compute <\equation*> +|~>-1>**|~>\-1>>+i>|)>;\|)>|~>,\,|~>>|]>|]>->+i|)>*\>-\;\+\>, and \|)>|~>,\,|~>>|]>,\,>|)>>|]>-*|~>-\;\+\>> as <\equation*> |~>-1>*+|)>+|~>-1>*+|)>*|~>>+\+|~>-1>*>-2>+>-1>|)>*|~>>>-2>+|~>-1>*>-1>*|~>>>-1>. Compute \-*|~>>;\|)>|~>,\,|~>+1>|]>|]>>*|~>>-\;\+\>> as <\equation*> -*|~>>>>-*|~>>;\|)>|~>,\,|~>+1>|]>|]>>*|~>>-\;\+\>-|~>>>>|)>. \; Write =+*|~>>+\+>-1>*|~>>>-1>> with <\equation*> ,\,>-1>\\|)>|~>,\,|~>-1>|]>-1,\,2*-1>-1|)>>. For ,>-1>, recursively compute <\equation*> +|~>-1>**|~>\-1> ;\|)>|~>,\,|~>>|]>|]>-i*|~>-\;\+\>, and \|)>|~>,\,|~>>|]>,\,>|)>>|]>-\;\+\>> as <\equation*> +|~>-1>*+|)>*|~>>+\+|~>-1>*>-2>+>-1>|)>*|~>>>-1>. Return |~>>**|~>+1>+>. <\proposition> Algorithm is correct and performs <\equation*> R*>*D*R*+\|)>|)> operations in >. <\proof> If =0> then \\|)>>, so step1 returns the correct value. Otherwise the nested valuation property ensures that >|)>;\|)>\\>, so yields <\equation*> val>> ||)>|)>\\-\. On the other hand, <\equation*> \|)>|~>,\,|~>>|]>-1,\,2*-1>-1,1|)>>|]>-i*|~>>-2*\;\+2*\> has nested valuation \-i*|~>>>, for ,2*>-2>, so the recursive calls in step2 are valid. It follows that -1>>-1> |)>\\-i*|~>>-\>, and that +|~>-1>**|~>>> approximates -1> > at precision \+\>. If -1>=1> then |~>>=val> |~>>=\-1>+1>=val-1> |~>>> by, whence <\equation*> =-1> quo|~>>> |~>>>>;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>. If -1>=0>, then the latter equality trivially holds. By construction of > there exists <\equation*> \\|)>|~>,\,|~>>|]>,\,>|)>> such that <\equation*> -1> ;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>=+*|~>>>>. In step3, the polynomial > belongs to |)>|~>,\,|~>+1>|]>-1,\,2*>-1,1|)>>|]>-2*\;\+2*\>> and> \\+>*|~>>> by Lemma and Property of Definition. The correctness of step4 is thus similar to step2. There exists \\|)>|~>,\,|~>>|]>,\,>|)>>> such that <\equation*> -1> ;\|)>|~>,\,|~>+1>|]>|]>+>*|~>>-\;\+\>=+*|~>>>>. Using Property3 of Definition, let \\|)>|~>,\,|~>>|]>,\,>|)>>> be such that <\eqnarray*> |||~>>>>+>>|||-1>|~>>*|~>>;\|)>|~>,\,|~>+1>|]>|]>>*|~>>-2*\;2*\+2*\>|)>;\|)>|~>,\,|~>+1>|]>|]>>*|~>>-\;\+\>.>>>> By Lemma we have >-1>*|~>>*|~>>|)>|)>\\+2*>*|~>>>. Then we verify that <\eqnarray*> ||-1>*|~>>|)>*|~>>|)>;\|)>|~>,\,|~>+1>|]>|]>+2*>*|~>>-\;\+\>>>|||-1>*|~>>>>+|)>*|~>>*|~>>>>+*|~>>*|~>>|)>;\|)>|~>,\,|~>+1>|]>|]>+2*>*|~>>-\;\+\>>>|||-1>*|~>>*|~>>>>+*|~>>>>+*|~>>|)>*|~>>|)>;\|)>|~>,\,|~>+1>|]>|]>+2*>*|~>>-\;\+\>>>>> and also that <\eqnarray*> ||-1>*|~>>*|~>>|)>|)>;\|)>|~>,\,|~>+1>|]>|]>+2*>*|~>>-\;\+\>>>|||-1>*|~>>>>+*|)>;\|)>|~>,\,|~>+1>|]>|]>+2*>*|~>>-\;\+\>.>>>> Since |~>>>-1>*|~>>>>+*|~>>|)>*|~>>|)>|)>\3*>>, equating with leads to <\eqnarray*> ||> ;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>>>|||>*|~>>+|)>;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>>>||||~>>**|~>+1>+,>>>> for some \|~>>|)>1>>. From >|~>>*|~>+1>|)>\val>|~>>*|~>>|)>> and >> |)>\\-\>, it follows that the algorithm actually returns > ;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>>. As for the complexity analysis, note that > and *|~>>> belong to <\equation*> \|)>|~>,\,|~>>|]>-1,\,2*-1>-1,2*>|)>>. By Proposition, the products in steps3 and5 take <\equation*> R>>*>*>*R>>*+\|)>|)> operations in >. Let ,\,>;\|)>> denote the cost function of Algorithm. By Lemma, the recursive calls to Algorithm take <\equation*> 3*min-1>>*+2*\|)>,1|)>*>*,\,-1>;max-1>>,\|)>|)> operations in >. It follows that <\eqnarray*> ||,\,>;\|)>>>||>|,\,-1>;max-1>>,\|)>|)>*min-1>>*+2*\|)>,1|)>*>>>|||+R>>*>*>*R>>*max>>,\+\|)>|)>>>||>|*,\,-2>;max-2>>,\|)>|)>>>|||\min-1>>*+2*\|)>,1|)>*min-2>>*max-1>>,2*\+2*\|)>,1|)>*-1>*>>>|||-1>>*+2*\|)>,1|)>*>*R-1>>*-1>*-1>*R-1>>*max-1>>,\+\|)>|)>>>|||>>*>*>*R>>*+\|)>|)>>>||>|*,\,-2>;max-2>>,\|)>|)>*min-2>>*+2*\|)>,1|)>*-1>*>)>>>|||+*R>>*>*>*R>>*+\|)>|)>+R>>*>*>*R>>*+\|)>|)>>>||>|>|||>>*>*>*R>>*+\|)>|)>.>>>> As a direct application of Algorithm, we obtain the following multiplication method, which benefits from flattenings. <\specified-algorithm> <\description-compact> Input>An almost reduced generalized contact tower |)>t>> at relative precision \R*\0>>, a flattening |~>|)>>> for |)>t>> at relative precision > and defect bound \dct |~>>>, =>>|)>;\|)>|~>,\,|~>+1>|]>|]>|)>-\;\+\>>, and =>>;\|)>|~>,\,|~>+1>|]>>|)>|]>|)>-\;\+\>>, where and are in |)>l>>. >*|)>;\|)>|~>,\,|~>+1>|]>|]>|)>+v|)>-\;\+\>>. <|specified-algorithm> <\enumerate> Compute \*> in |)>|~>,\,|~>+1>|]>>. Write =+*|~>+1>+\+*|~>+1>> with ,\,\\|)>|~>,\,|~>>|]>-1,\,2*>-1|)>>>. For ,2*l-2>, compute +\**|~>+1>\>|)>|]>|)>+v|)>-i*|~>+1>-\;\+\>> by using Algorithm. Return +*+|)>*|~>+1>+\+*+|)>*|~>+1>+\**|~>+1>>. <\proposition> Algorithm is correct and performs <\equation*> R*>*D*l*R*+\|)>|)> operations in >, whenever r*\0>>. <\proof> By Lemma, we have > \v|)>+v|)>>. So the correctness follows as in the proof of Proposition. The cost of step1 is given in Proposition, that is <\equation*> R*+1>*D*l*R*+\|)>|)> The cost of step2 follows from Proposition and Lemma: <\eqnarray*> ||*>*D*l*min*\,1|)>*R*max,\+\|)>|)>>>|||*>*D*l*min*+\|)>,1|)>*max*+\|)>,1|)>|)>>>|||*>*D*l*R*+\|)>|)>>>|||*>*D*l*R*+\|)>|)>.>>>> The cost of step3 is negligible. In short, >>|)>> will be called the of \>. Proposition shows that fast products can be achieved using flattened representations, in the sense that >>|)>> is obtained from >>|)>> and >>|)>>. This approach extends to divisions as follows. <\proposition> Let \> be a clustered monic contact polynomial of degree r*\0>> in > and given at precision \R*\0>>. Let be the pre-inverse of at relative precision >, and let be a contact polynomial of |)>2*l>> of valuation \> at precision >. Given >>|)>;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>>, >>|)>;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>>, and >>|)>;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>>, we can compute <\eqnarray*> ||>> F|)>;\|)>|~>,\,|~>+1>|]>|)>|]>-l*\-\;\+\>>>|||>> F|)>|)>;\|)>|~>,\,|~>+1>|]>|]>-\;\+\>>>>> using <\equation*> R*>*D*l*R*+\|)>|)> operations in >. <\proof> This follows from Propositions and. In this section, we present three types of flattening along with conversion algorithms. The given generalized contact tower is still written |)>t>> and is assumed to be almost reduced, effectively separable and regular. The relative precision we want to compute with is \R*\0>>. When a flattening for |)>t>> is given as in Definition, we know from Lemma and Equation that an element \> can be recovered at precision> from <\equation*> >>|)>;\|)>|~>,\,|~>+1>|]>|]>|)>-\;\+\> whenever \dct \>>. In the rest of the paper the notation <\equation*> >,\1;\>\|~>,\1;\+\>|)> will represent a complexity bound for the following tasks: <\itemize> compute >> at relative precision +\>, for any >>|)>1>> given at relative precision>, compute >|)>> at relative precision >, from the canonical representative \|~>>|)>1>> at relative precision +\>. Each type of flattening will involve precomputed for the sake of efficiency. In fact, at level of a flattening, data in >> at precision > shall be converted to |~>> at relative precision \+dct \> in order to benefit from the flattened products and divisions of section. The pre-inverse of +\-1>> in > will be written>. We say that a flattening is at level when =i+1>, |~>=\>|)>>, and >|)>\|~>>. Without loss of generality we may assume that > for the sake of the presentation. <\lemma> Assume that -1>=t-1> and that |~>|)>-1>> is a flattening for |)>i-1>>>. Then there exists a flattening |~>|)>>> \ of |)>i>>>, trivial at level >, with >\i-1>+1=t>, |~>>\\>>>, <\equation*> |~>>|~>,\,|~>>|)>\\-1>>>|)>, <\eqnarray*> >:\>|>||~>>>>|>|>|-1>|)>k=1,\,i>>>|>+1>>|>||~>+1>.>>>> We take |~>>\\-1>|)>>, where > is the pre-inverse of > in >. In addition we have >=dct \-1>>. <\proof> The proof is straightforward from Definition. The next proposition concerns the complexity for building a trivial flattening at level>. We recall that a flattening as in Definition is said to be given at precision > and defect \dct \>> when the |~>> and the |~>> are known at precision +\>, for ,>. <\proposition> Let |)>t>> be an almost reduced, effectively separable and regular contact tower at precision \R*\0>>, and let |~>|)>-1>> be a flattening \ for |)>i-1>>> with -1>=> at precision > and defect \dct \>>. Then we can compute a flattening |~>|)>>> \ of |)>i>>> trivial at level > at precision > and defect > using <\eqnarray*> ||,\,d;\|)>*log d|)>>>|||-1>,\1;\>\|~>-1,\1;\+\>|)>*O*\,1|)>*d|)>>>|||,\,d;max,\|)>|)>>>>> operations in >. <\proof> We compute the pre-inverse > of > at precision > using <\equation*> O,\,d;\|)>*log d|)>+,\,d;max,\|)>|)> operations in > thanks to Proposition. By Lemma we need *\,1|)>*d|)>> evaluations of -1>> at elements of |)>d>> in order to obtain -1>|)>> and -1>|)>> at relative precision +\>. <\proposition> With the notation and assumptions of Proposition, one conversion between |)>1>> at precision \R*\0>> and |~>>|)>1>> at precision +\> costs <\equation*> -1>,\1;\>\|~>-1,\1;\+\>|)>*O*\,1|)>*d|)>. <\proof> For an element in |)>1>>, we consider its contact representation >A*\> and compute |)>>. The number of non-zero > is *\,1|)>,d|)>> by Lemma. We say that the level of a flattening is of whenever <\equation*> \>=\>=0. For the sake of the presentation, as previously we focus on the case where >, that is -1>>=\>>=0>. In other words, -1>>> (resp. >>>) is of the form -1>>-1>+1>|]>> (resp. >>>+1>|]>>) where -1>>\\-1>>/-1>+1>|)>> (resp.>>\\>>>/(>+1>>)) has finite dimension over|)>>. By Proposition (with -1>> and letting > tend to infinity), if \*D|)>>, then there exists a univariate-valued representation <\equation*> \,w-1>+1>,\,w>> of >>> over -1>>> in terms of a primitive-valued >, hence <\equation*> \|)>=0, and =w|)>> for -1>+1,\,i>>. Let \\-1>>> be the quotient in the division of >>> by >, so that <\equation> \*\\T>>+\-1>>>>. In the following lemma, we extend -1>> coefficientwise to -1>>>, and -1>|)>> stands for the application of this extended map to >. <\lemma> Assume that |~>|)>-1>> is a flattening of |)>i-1>>> and that -1>>=\>>=0>. Then there exists a flattening |~>|)>>> \ of |)>i>>> of first type at level >, with >\t>, |~>>\0>, <\equation*> |~>>|~>,\,|~>>|)>\\-1>|)>|~>>|)>, <\eqnarray*> >:\>|>||~>>>>|>|>|-1>|)>k=1,\,i-1>>>|>|>|-1>|)>|~>>|)>k=i-1>+1,\,i>>>|>+1>>|>||~>+1>>>>> and |~>>\\-1>|)>|~>>|)>>. In addition we have >=dct \-1>>. <\proof> By construction, Definition holds. Only a brief explanation is necessary for: the |)>>vector space isomorphism <\eqnarray*> |)>|~>,\,|~>>|]>,\,>|)>>>|>|>>>>|k\>>*|~>>>|>|k\>>\-1>|)>*\>>>>> shows that the projection |)>|~>,\,|~>>|]>,\,>|)>>\|~>>> is injective, with image >|)>1>|)>>. Given \|~>>|)>1>>, let us write <\equation*> \>|)>=k\>>>b*\ canonically in terms of >, where \-1>>|)>1>>. Hence, <\equation*> =k\>>\-1>|)>*|~>>. Definition gives <\equation*> val-1>-1>|)>|)>\v;\-1>>|)>-dct \-1>, hence <\eqnarray*> >|)>>||k\>>|-1>-1>|)>|)>+val>|~>>|)>|)>|\>>>||>|k\>>;\-1>>|)>-dct \-1>+val>|~>>|)>|)>>>|||k\>>;\-1>>|)>+v;\|)>|)>|)>-dct \-1>>>|||>|)>;\|)>-dct \-1>,>>>> and >\dct \-1>>. Let us now investigate flattenings of the first type from a complexity perspective. We still assume that a flattening is already at our disposal for -1>>>. <\proposition> Let |)>t>> be an almost reduced, effectively separable and regular contact tower at precision \R*\0>>, and let |~>|)>-1>> be a flattening for |)>i-1>>> at precision > and defect \>. If we are given >> distinct elements in >, then we can compute a flattening |~>|)>>> of |)>t>> as in Lemma, using <\eqnarray*> ||>*>*ht \|)>>>|||,\,d-1>>;max-1>>,\|)>|)>*-1>>*\,1|)>*>|)>*>*ht \*log D|)>>>|||-1>,\1;\>\|~>-1,\1;\+\>|)>*min-1>>*\,1|)>*>*log D|)>>>>> operations in >. <\proof> This proposition mostly rephrases Proposition for -1>> by taking into account the computation of |~>>>. Let us first describe the computation of > from. Since -1>>> is a finite dimensional vector space over |)>>, a classical Newton iteration can be used as follows. We let <\equation*> |\>=T>>*\|)> and we compute its inverse |\>> of degree >> in -1>>|]>/>+1>|)>>. By Lemma, apolynomial in -1>>|]>/>+1>|)>> has -1>>*\,1|)>*>|)>> non-zero terms. Therefore two such polynomials can be multiplied by the schoolbook method using -1>>*\,1|)>>*deg \|)>|)>> operations in -1>>>. In total the Newton iteration performs >|)>> such products, hence <\equation> ,\,d-1>>;max-1>>,\|)>|)>*-1>>*\,1|)>*deg \|)>*log >|)> operations in >. Then we have <\equation*> |\>*|\>=1+T>+1>*>, for some >\\-1>>>>>, so we define <\equation*> \\T>>*|\>|)>and>Q\T>-1>*>|)>, and obtain <\equation*> \*\=T>>+Q. Deducing |~>>=\-1>|)>>, |~>>=\-1>|)>>, and -1>|)>> for -1>+1,\,i>> costs <\equation> O>-i-1>|)>*-1>,\1;\>\|~>-1,\1;\+\>|)>*min-1>>*\,1|)>*deg \|)>. The total cost is the sum of, , and the cost stated in Proposition for-1>>>. For efficiency reasons, conversions between |)>1>> and |~>>|)>1>> will benefit from precomputations. The precomputed data will be called \Pauxiliary\Q in the sequel. The complexity of the precomputations will be analyzed in section. <\proposition> With the notation of Proposition, assume that the following auxiliary data are given at precision +\>: <\itemize> -1>-1>+1>|)>,\,\-1>|)>>, -1>-1>+1>|)>,\,\-1>|)>>, |~>=\-1>|)>>, |~>\\-1>|)>>, -1>+1>\\-1>-1>+1>|)>>,, >>\\-1>>>|)>>. Then we have <\eqnarray*> ||>,\1;\>\|~>,\1;\+\>|)>>>|||*>*D*R*+\|)>*>|)>+-1>,\1;\>\|~>-1,\1;\+\>|)>*min-1>>*\,1|)>*>.>>>> <\proof> Each polynomial in at precision > of degree>> has at most -1>>*\,1|)>*>> nonzero terms by Lemma. By means of binary powering and schoolbook products and divisions with respect to one sum or product modulo > takes <\equation*> O-1>>*\,1|)>*>|)>|)> operations in -1>>>. Let |)>1>> be written canonically <\equation*> A=-1>+1>\d-1>+1>,\,k>>\d>>>a-1>+1>,\,k>>>*\-1>+1>-1>+1>>*\*\>>>>>. In order to convert into |~>>|)>1>>, we compute -1>+1>-1>+1>>*\*w>>>>> rem \> at precision > for all k-1>+1>\d-1>+1>,\,0\k>>\d>>> with -1>+1>,\,k>>>\0>, via flattened arithmetic. By Lemma, at most -1>>*\,1|)>*>> terms of are non-zero. So we compute the flattened representative -1>+1>,\,k>>>> of the non-zero -1>+1>,\,k>>>>, then -1>+1>-1>+1>>*\*>>>>> rem |~>> at precision +\>, so <\equation*> -1>+1>\d-1>+1>,\,k>>\d>>>-1>+1>,\,k>>>*-1>+1>-1>+1>>*\*>>>>> rem |~> is obtained using <\equation*> O-1>>*+\|)>,1|)>*>|)>*log D|)> flattened operations in -1>>>, which corresponds to <\eqnarray*> ||-1>>*-1>*-1>*R-1>>*max-1>>,\+\|)>|)>*-1>>*+\|)>,1|)>*>|)>*log D>>|||-1>>*>*D*R-1>>*+\|)>*>|)>>>|||*>*D*R*+\|)>*>|)>>>>> operations in >, by Proposition with -1>> and *l=-1>>. Conversely, given <\equation*> =k\>>*|~>> there are min-1>>*+\|)>,1|)>*>> nonzero >, by Lemma, so the computation of <\equation*> k\>>*|~> takes -1>>*+\|)>,1|)>*>*log >|)>> flattened operations in |)>1>>. By taking advantage of the auxiliary data -1>-1>+1>|)>,\,\-1>|)>> and -1>-1>+1>|)>,\,\-1>|)>>, each such flattened operation reduces to <\eqnarray*> ||>-i-1>>*,\,d-1>>;max-1>>,\|)>|)>*-1>>*\,1|)>*d-1>+1>*\*d|)>|)>>>|||>-i-1>>*,\,d-1>>;max-1>>,\|)>|)>*-1>>*\,1|)>*>|)>|)>>>|||,\,d-1>>;max-1>>,\|)>|)>*min-1>>*\,1|)>*>|)>>-i-1>>\>>)>>>>> operations in > by Proposition (with -1>>). Thanks to Proposition (with -1>> and *l=-1>>), and still for the flattened representation, we may take <\equation*> ,\,d-1>>;max-1>>,\+\|)>|)>=R-1>>*-1>*-1>*R-1>>*max-1>>,\+\|)>|)>. Overall, the flattened representation of k\>>*|~>> totalizes <\eqnarray*> ||,\,d-1>>;max-1>>,\|)>|)>*min-1>>*\,1|)>*>*min-1>>*+\|)>,1|)>*>*log >|)>>>|||-1>>*-1>*-1>*R-1>>*max-1>>,\+\|)>|)>*min-1>>*+\|)>,1|)>*>*log >>>|||-1>>*>*>*R-1>>*+\|)>*>|)>>>|||*>*D*R*+\|)>*>|)>>>>> operations in >, which concludes the proof. <\example> (Continued from Example) We take \2>, =1> and =3> and relative precision =1/4> and defect =0>. The first level of the flattening is trivial: <\equation*> |~>|~>|)>\\|~>|)>. For the second level we add the following flattened level of first type: <\equation*> |~>|~>,|~>|)>\|~>+|~>*|~>+3*|~>*|~>+7*z*|~>+6*z*|~>+2*z*|~>*|~>+9*z and <\eqnarray*> |)>>|>||~>>>||)>>|>|*|~>*|~>+6*z*|~>*|~>+8*|~>+7*|~>*|~>+5*|~>*|~>+2*z*|~>+2*z*|~>>>||)>>|>|*|~>*|~>+7*z*|~>*|~>+7*z*|~>+9*z*|~>+6*z*|~>*|~>+4*z*|~>*|~>+z*|~>+z*|~>.>>>> The second type of flattening concerns the case where <\equation> \+1>=\+2>=\=\-2>=\-1>=1. For all l> we define the following polynomials by induction: <\equation*> \l>,\,\|)>\\,\,\,\k>,\,\|)>,\,\l-1>,\,\|)>|)>. Note that k>,\,\|)>=\,\,\|)>>. <\example> 2>|)>=\,\|)>|)>> and 3>|)>=\,\|)>,\2>|)>|)>>. Again, in order to keep the notation simple, and without loss of generality, we focus on the case where >. <\lemma> Let |)>t>> be an almost reduced, effectively separable, and regular contact tower at precision \R*\0>>, let |~>|)>-1>> be a flattening for |)>i-1>>> and assume that -1>+1>=\=\>-1>=1>. Then there exists a flattening |~>|)>>> for |)>i>>> with >\t>, |~>>=\>>>, <\equation*> |~>>|~>,\,|~>>|)>\\-1>-1>+1\i>>|)>, <\eqnarray*> >:\>|>||~>>>>|>|>|-1>|)>k=1,\,i-1>+1>>|>|>|-1>-1>+1\k-1>,\,\-1>+1>|)>|)>k=i-1>+2,\,i>>>|>+1>>|>||~>+1>,>>>> |~>>\\-1>|)>>, where > stands for the pre-inverse of -1>+1\i>>> in -1>>> at precision +\>>, where <\equation*> \>\-1>+1\k\i>>*\*d>>-1|)>*-d*\|)> satisfies <\equation*> dct \>\dct \-1>+\>and>\>\>*\. <\proof> For -1>+2,\,i>> the polynomial -1>+1\k>,\,\-1>+1>|)>> is monic in -1>+1>> and its initial in -1>>> is <\equation*> in-1>+1>-1>+2>*\*d>;\-1>>|)>. It follows that -1>+1\i>>> is clustered in -1>>> and that <\equation*> v-1>+1\i>>;\-1>>|)>=>*\-1>+1>. By15> the map <\eqnarray*> ||)>|~>,\,|~>-1>|]>,\,-1>|)>>|~>>|]>>>>|>||)>1>>>|>-1>*|~>>>|>|>-1>\-1>|)>*\-1>+1>,>>>> where \\|)>|~>,\,|~>-1>|]>,\,-1>|)>>>, is a |)>>vector space isomorphism, so Property of Definition holds. Other properties of Definition hold by construction. For <\equation*> A=-1>+1>\d-1>+1>,\,k>>\d>>>a-1>+1>,\,k>>>*\-1>+1>-1>+1>>*\*\>>>>>\|)>1>, where -1>+1>,\,k>>>\-1>>|)>1>>, we have <\equation*> v|)>=min-1>+1>\d-1>+1>,\,k>>\d>>>-1>+1>,\,k>>>;\-1>>|)>+k-1>+1>*\-1>+1>+\+k>>*\>>|)>>. Since -1>+1\i>>> is clustered in -1>>> of valuation -1>+1>*\*d>>*\-1>+1>>, the contact polynomial -1>+1>-1>+1>>*\-1>+1\i-1>+1>-1>+2>>*\*\-1>+1\i>-1>>>>> is clustered in -1>>> of degree <\equation*> \-1>+1>,\,k>>>\k-1>+1>+d-1>+1>*k-1>+2>+\+d-1>+1>*\*d>-1>*k>> in -1>+1>> and of valuation <\equation*> v-1>+1>-1>+1>>*\-1>+1\i-1>+1>-1>+2>>*\*\-1>+1\i>-1>>>>;\-1>>|)>=\-1>+1>,\,k>>>*\-1>+1>. It follows that <\eqnarray*> ||-1>+1>,\,k>>>*\-1>+1>-1>+1>>*\-1>+1\i-1>+1>-1>+2>>*\*\-1>+1\i>-1>>>>;\-1>>|)>>>||>|-1>+1>,\,k>>>;\-1>>|)>+v-1>+1>-1>+1>>*\-1>+1\i-1>+1>-1>+2>>*\*\-1>+1\i>-1>>>>;\-1>>|)>>>||>|>>|)>--1>+1>*\-1>+1>+\+k>>*\>>|)>+\-1>+1>,\,k>>>*\-1>+1>,>>>> hence <\equation> v-1>>|)>\v>>|)>-\, where <\equation*> \\max-1>+1>\d-1>+1>,\,k>>\d>>>-1>+1>*\-1>+1>+\+k>>*\>>-\-1>+1>,\,k>>>*\-1>+1>|)>. Consequently, the canonical representative of in-1>>> can be written in the canonical form <\equation*> A=-1>+1>\d-1>+1>,\,k>>\d>>>b-1>+1>,\,k>>>*\-1>+1>-1>+1>,\,k>>>>, with <\eqnarray*> -1>+1>,\,k>>>;\-1>>|)>>|>|-1>>|)>-\-1>+1>,\,k>>>*\-1>+1>>>||>|>>|)>-\-\-1>+1>,\,k>>>*\-1>+1>,>>>> using. Therefore <\equation*> \>=-1>+1>\d-1>+1>,\,k>>\d>>>\-1>-1>+1>,\,k>>>|)>*|~>>-1>+1>,\,k>>>>. is the canonical representative of >> and <\equation*> val>>|)>=min-1>+1>\d-1>+1>,\,k>>\d>>>|val-1>-1>-1>+1>,\,k>>>|)>|)>||1>>+\-1>+1>,\,k>>>*\-1>+1>|)>, since -1>+1>=val> |~>>>. Then, combining with <\equation*> v-1>+1>,\,k>>>;\-1>>|)>-dct \-1>\val-1>-1>-1>+1>,\,k>>>|)>|)> yields <\equation*> v>>|)>-\-dct \-1>\val-1>-1>-1>+1>,\,k>>>|)>|)>+\-1>+1>,\,k>>>*\-1>+1>, whence <\equation*> val>>|)>\v>>|)>-\-dct \-1>. Next, we verify that <\eqnarray*> >||-1>+1>\d-1>+1>,\,k>>\d>>>> -1>+1\l\i>>k*-d-1>+1>*\*d*\-1>+1>|)>>>|||-1>+1\l\i>>-1|)>*-d-1>+1>*\*d*\-1>+1>|)>>>|||-1>+1\l\i>>-1|)>*-1>+1\k\l>d*\*d*-d*\|)>>>|||-1>+1\k\i>>-d*\|)>*l\i>>d*\*d*-1|)>>>|||-1>+1\k\i>>*\*d>>-1|)>*-d*\|)>>>|||>.>>>> In our setting, we recall that =1> holds whenever -d*\\\>. Therefore implies that -d*\\\> for all -1>+1\k\i>>. By using \2> for i-1>+1>, we obtain >\2-1>+1|)>>*d*\*d>>>, hence the bound <\eqnarray*> >>|>|-1>+1\k\i>>*\*d>>-1|)>*\>>||>|-1>+1\k\i>>-1>+1|)>>>*>*\>>||>|>*\.>>>> For ,t> we introduce <\eqnarray*> :\>|>|>>||>|,\,\,\|)>.>>>> For \k>, we also define <\equation*> \\k>=\\\\\>. Let us now study flattenings of the second type from a complexity perspective. We will not optimize the complexity of our algorithms as a function >>, because >> will always be taken relatively small in the next section. <\lemma> Let r*\0>>, let |)>l>> be given at relative precision \R*\0>>, and let \*-d*\|)>>. Then <\equation*> ;\|]>|)>-\>;\+\>>=;\|]>|)>+\>> can be computed using <\equation*> O,\,d;max,\+\|)>|)>**+\|)>,1|)>*d*l|)>>*l|)> operations in >. <\proof> Let l>A*\> denote the contact representation of . We obtain <\equation*> *\;\|]>|)>-\>;\+\> for all ,l-1>, using <\equation*> O,\,d;max,\+\|)>|)>**+\|)>,1|)>*d*l|)>*l|)> operations in> by Proposition, whence the claimed cost. <\lemma> Let r*\0>>, let \> be monic of degree in > and given in contact representation l>F*\>, and let +G> denote the pre-inverse of +F>. Then +G|)> quo> \> is the pre-inverse of quo> \> for all 1>. <\proof> Expanding the terms of highest degrees of the product of two monic contact polynomials and yields <\eqnarray*> ||+F*\+F*\+\|)>*+H*\+H*\+\|)>>>|||++H|)>*\+*H+F+H|)>*\+\>>>> Consequently, the sub-dominant coefficient +H+F*H|)> quo> \> in this product only depends on the sub-dominant coefficients > and > of and . In other words, we have <\equation*> quo> \=> \|)>*> \|)>|)> quo> \. From <\equation*> +G|)>*+F|)> quo> \=\, it follows that <\eqnarray*> ||+G|)> quo> \|)>* quo> \|)> quo> \>>|||+G|)> quo> \|)>*+F|)> quo> \|)> quo> \>>|||+G|)>*+F|)>|)> quo> \>>|||+G|)>*+F|)>|)> quo> \|)>*\|\>>>|||>>+G|)>*+F|)> quo> \|)>||]> quo \>>|||+G|)>*+F|)>|)> quo> \>>|||>>|||.>>>> <\lemma> Let r*\0>>, let |)>l>> be of valuation \>, let \R*\0>>, and let \*-d*\|)>>. Given ;\|]>-\>;\+\>> and ;\|]>;\+\>>, we can compute |]>;\>> using <\equation*> O,\,d;max,\+\|)>|)>**+\|)>,1|)>*d*l|)>*l|)> operations in >. <\proof> Let l>A*\> and d*l>B*\> denote the contact representations of and . We compute \;\|]>*\;\+\>> and quo> \;\|]>;\+\>> for ,l-1>, using <\equation*> O,\,d;max,\+\|)>|)>**+\|)>,1|)>*d*l|)>*l|)> operations in> by Proposition. Then, we set \B> and for from down to , we recursively compute <\eqnarray*> >|>| quo> C;\|]>-\-j*d*\;\+\>>>|>|>| rem> C;\|]>-\;\+\>.>>>> In this way, we obtain the following approximation of the >-adic expansion of : <\equation*> B=l>D*\;\|]>-\;\+\>. Since <\equation*> \-\-j*d*\+\+\=\-j*d*\+\\\+\-j*\, we can read off ;\|]>;\>> from >. From Lemma, we know that quo> \> is the pre-inverse of quo> \*j-1>>. Taking advantage of these pre-inverses, this sequence of divisions costs <\equation*> O,\,d;max,\+\|)>|)>**+\|)>,1|)>*d*l|)>*l|)>, in total, thanks to Proposition. <\lemma> Let t>, let \R*\0>>, let <\equation*> \\*-d*\|)>+*l-1|)>*-d*\|)>+\+*\*d*l-1|)>*-d*\|)>, and assume that ,\,\> are known at precision +\>. One evaluation of h+1>> with relative precision > at an element of degreel\r*\0>> in > at precision +\>, and one evaluation of h+1>> with relative precision +\> at a polynomial of degree d*\*d*l> in >, both cost <\equation*> *,\,d;max,\+\|)>|)>*min*+\|)>,1|)>**\*d*l|)>|)> operations in >. <\proof> Recall that h+1>=\\\\\>. We apply Lemma for > (resp. Lemma for >) recursively for from down to . The total cost is <\equation*> Oi\t>,\,d;max,\+\|)>|)>**max,\+\|)>,1|)>*d*\*d*l|)>>*d*\*d*l|)>, which is bounded by <\equation*> Oi\t>,\,d;max,\+\|)>|)>**+\|)>,1|)>*d*\*d*l|)>>**\*d*l|)>|)>, For ,t-1>, Proposition gives us <\eqnarray*> ||,\,d;max,\+\|)>|)>>>||>|*,\,d;max,\+\|)>|)>**max,\+\|)>,1|)>*d*\*d|)>.>>>> Consequently, <\eqnarray*> ||,\,d;max,\+\|)>|)>**+\|)>,1|)>*d*\*d*l|)>>**\*d*l|)>|)>>>||>|*,\,d;max,\+\|)>|)>*min*+\|)>,1|)>>>|||\min*max,\+\|)>,1|)>*\*d*l|)>>>||>|*,\,d;max,\+\|)>|)>*min*+\|)>,1|)>**\*d*l|)>,>>>> using Lemma. The total cost for h+1>> and h+1>> directly follows by taking the sum of the latter bound for ,t-1>. <\proposition> Given an almost reduced effectively separable and regular contact tower |)>t>>, given \R*\0>>, and a flattening |~>|)>-1>> for |)>i-1>>> at precision > and defect\>. Assume that -1>+1>=\=\>-1>=1> and that -1>+1>,\,\> are known at precision+\>>. Then we can compute a flattening |~>|)>>> for |)>t>> of second type at level >, precision >, and defect \\\+\>> using <\eqnarray*> ||-1>>*,\,d-1>>;max-1>>,\+\|)>|)>*min-1>>*+\|)>,1|)>*>|)>>>|||,\,d-1>>;max-1>>,\+\|)>|)>>>|||-1>,\1;\+\>>\|~>-1,\1;\+\>|)>*min-1>>*+\|)>,1|)>*>|)>>>>> operations in >. <\proof> We use Lemma with -1>> in conjunction with Lemma in order to compute -1>+1\k>=\i-1>+1>|)>> at precision +\> for -1>+1,\,i>>. This costs <\equation*> -1>>*,\,d-1>>;max-1>>,\+\|)>|)>*min-1>>*+\|)>,1|)>*>|)>. We compute the pre-inverse >> of -1>+1\i>>> at relative precision +\>>, using <\equation*> O,\,d-1>>,>;max-1>+1>,\+\|)>|)>*log >|)>+,\,d-1>>;max-1>>,\+\|)>|)> operations in >, thanks to Proposition. By Proposition we have <\eqnarray*> ||,\,d-1>>,>;max-1>+1>,\+\|)>|)>>>|||,\,d-1>>;max-1>>,+\|)>|)>|)>*-1>>*max-1>+1>,\+\|)>,1|)>*>|)>|)>>>|||,\,d-1>>;max-1>>,+\|)>|)>|)>*min-1>>*max-1>+1>,\+\|)>,1|)>*>|)>>>|||,\,d-1>>;max-1>>,+\|)>|)>|)>*min-1>>*+\|)>,1|)>*>|)>.>>>> We deduce |~>>> and |~>>> using -1>>*+\|)>,1|)>*>|)>> evaluations of -1>> by Lemma. <\proposition> With the notation of Proposition, assume that the following auxiliary data are given at precision +\>: <\itemize> -1>-1>+1>|)>>,, -1>|)>> (here -1>> is applied coefficient-wise), -1>-1>+1>|)>,\,\-1>|)>>, where > still denotes the pre-inverse of +\-1>> at precision +\>>. Then we have <\eqnarray*> ||>,\1;\>\|~>,\1;\+\>|)>>>|||*>*D*R*+\|)>|)>*>>>|||+-1>,\1;\+\>>\|~>-1,\1;\+\>|)>*min-1>>*+\>|)>,1|)>*>.>>>> <\proof> Let >>|)>1>> be written canonically <\equation*> A=-1>+1>\d-1>+1>,\,k>>\d>>>A-1>+1>,\,k>>>*\-1>+1>-1>+1>>*\*\>>>>>. At relative precision >, the number of non-zero -1>+1>,\,k>>>> is <\equation*> \min-1>>*\,1|)>*> by Lemma. We first convert these non-zero coefficients into |~>-1>|)>1>> at relative precision +\>>. For the arithmetic operations in -1>>|)>1>> we then use the flattened representation, so Proposition allows us to take <\equation*> ,\,d-1>>;max-1>>,\+\>|)>|)>=R-1>>*>*-1>*R-1>>*max-1>>,\+\|)>|)>. Using >-i-1>>\>>, we have >-i-1>>\>>, so the cost bound given in Lemma becomes <\eqnarray*> ||-1>>*>*-1>*R-1>>*max-1>>,\+\|)>*min-1>>*+\|)>,1|)>*>|)>>>|||*>*>*R*+\|)>|)>*>.>>>> For the reverse conversion from |~>>|)>1>> to >>|)>1>> the complexity is the same, again by Lemma. The complexity of the precomputations will be addressed in section. We carry on with the notation of Definition for flattenings and we recall that \d+1>*\*d>>. We aim at constructing flattenings of sufficiently small height in order to obtain a fast product in the given contact tower: this will be achieved by merging consecutive levels of small degree. All contact towers in this section will be almost reduced, effectively separable, and regular. >-flattening> Given \D>, we can construct a sequence |~>> for ,s> with |~>=0>, |~>=1>, and <\equation> s\3*|log \>+2 such that if |~>\|~>1>+1>, then \\>. We originally developed this construction for algebraic towers4.2>. In this section we will refine it for contact towers. For a slice between |~>> and |~>-1>, we will construct at most four consecutive flattening steps, either trivial, or of first or second types. We define |)>,>>> recursively from \0> to >=t>. We recall that the first level must be trivial, so \1>. For 2>, assume that > has been defined and that =|~>> for some ,s|}>>. If |~>=|~>+1> then we set \|~>> and introduce a trivial flattening step at level >. Otherwise, we distinguish the following cases. <\description> 1>If |~>+1>=1>, then we distinguish the following sub-cases. <\description-aligned> If |~>+1>=\=\|~>-1>=1>, then we set \|~>> and introduce a single flattening of second type between > and >. Otherwise, there exists a largest integer \|~>> such that +1>=\=\-1>=1>. By construction \|~>> and >=0>, so we still use a flattening of second type between > and >, but beyond >, we distinguish two cases: <\description> If |~>>=0> then we set \|~>> and a flattening of first type is used between > and>. Otherwise, |~>>=1> and there exists a smallest integer \|~>> such that +1>=\=\|~>>=1>. Between > and > a flattening of first type is used. Between > and \|~>> a flattening of second type is used. 2> If |~>+1>=0>, then we distinguish the following sub-cases. <\description-aligned> If |~>>=0>, then we set > to the largest integer |~>> such that >=0>, so we use a flattening of first type between > and >. If \|~>> then we add another flattening of second type between > and \|~>>. Otherwise |~>>=1>, and we set \i+1=|~>+1>. Then we repeat the construction from case1 at position |~>+1> instead of |~>>. A flattening constructed in this way will be called a >-flattening> for the contact tower|)>t>>. The maximum length of a subsequence of |)>>> between |~>> and |~>> is at most. This maximum is reached in case 2b, when the recursive construction falls in case 1bii, asillustrated below (where '>' stands for or): <\flat-size> <\equation*> |||\|~>>|=i+1>|\i+1>|>|-1>|>|+1>|>|>|+1>|>|=|~>>>|>||||>|||>|>|||>|>>>> <\lemma> There exists a >-flattening with the following properties: <\itemize> \12*|log \>+8>, if \i+1> then \\>, for ,>, \\*\*j>, for ,>. <\proof> The existence of the flattening and the bound on > is a consequence of the above construction, Lemmas,, and. The first bound follows from and\4*s>>. Now we assume that a >-flattening is at our disposal and we study the cost of the conversions between >>|)>1>> and |~>>|)>1>>. By definition of >>, any element in >>|)>1>> can be recovered at precision > from its image >> at relative precision +\> whenever \dct \>>. <\lemma> Given an almost reduced effectively separable and regular contact tower |)>t>>, and <\itemize> \R*\0>>, \\*\*>, a >-flattening |~>|)>>> of |)>t>> at precision >, the auxiliary data of Proposition (resp. and), if the flattening at level is trivial (resp. of first and second type), for ,>. Then we have <\equation*> >,\1;\>\|~>,\1;\+\>|)>=R*>*D*R*+\|)>*\|)>. <\proof> If the flattening at level > is trivial or of first type, then we set >\0>. The upper bound =\*\*> on the defect comes from Lemma. In case of a non-trivial flattening at level >, we have >\\>, and Propositions and yield <\eqnarray*> ||>,\1;\>\|~>,\1;\+\>|)>>>|||*>*D*R*+\|)>*>|)>+-1>,\1;\+\>>\|~>-1,\1;\+\>|)>*min-1>>*+\|)>,1|)>*>>>|||*>*D*R*+\|)>*\|)>+-1>,\1;\+\>>\|~>-1,\1;\+\>|)>*min-1>>*+\|)>,1|)>*>.>>>> Otherwise, in case of a trivial flattening, we have >=i-1>+1> and Proposition gives <\equation*> >,\1;\>\|~>,\1;\+\>|)>=-1>,\1;\>\|~>-1,\1;\+\>|)>*min-1>>*\,1|)>*>. It follows that <\eqnarray*> ||>,\1;\>\|~>,\1;\+\>|)>>>|||*>*D*R*+\|)>*\|)>+-1>,\1;\+\>>\|~>-1,\1;\+\>|)>*min-1>>*\,1|)>*>>>|||*>*D*R*+\|)>*\|)>>>|||+R-1>>*-1>*-1>*R-1>>*max-1>>,\+\|)>*\|)>*min-1>>*\,1|)>*>>>|||+-2>,\1;\+\>+\-1>>\|~>-2,\1;\+\>|)>*min-2>>*max-1>>,\|)>,1|)>*min-1>>*\,1|)>*-1>*>>>|||*>+3-1>|)>*D*R*+\|)>*\|)>>>|||+-2>,\1;\+\>+\-1>>\|~>-2,\1;\+\>|)>*min-2>>*\,1|)>*-1>*>)>>>||\>|>|||*>*>*R*+\|)>*\|)>,>>>> which concludes the proof. We still assume that a >-flattening is at our disposal. Now we assess the cost of the multiplications and divisions in >. <\lemma> Let |)>t>> be an almost reduced effectively separable and regular contact tower. Let \\d>, r*\0>>, \R*\0>>, and \\*\*>. Given a >-flattening for |)>t>> at precision > and defect \>, together with the auxiliary data needed in Lemma, we have <\eqnarray*> *\*d,l;\|)>>||*>*D*l*R*+\|)>*\|)>>>|,\,d,l;\|)>>||*>*D*l*R*+\|)>*\|)>.>>>> <\proof> In order to multiply two elements of |)>t>>, we convert them into the flattened representation, multiply them, and convert them back. The number of the conversions is given by Lemma, their cost by Lemma, whereas the cost of the products is stated in Proposition, whence <\eqnarray*> ||,\,d,l;\|)>>>|||>,\1;\>\|~>,\1;\+\>|)>*min*\,1|)>*l|)>+R*>*D*l*R*+\|)>|)>>>|||*>*D*R*max,\+\|)>*\*min*\,1|)>*l|)>+R*>*D*l*R*+\|)>|)>>>|||*>*D*R*+\|)>*\*l|)>+R*>*D*l*R*+\|)>|)>>>|||*>*D*l*R*+\|)>*\|)>.>>>> For computing a pre-inverse in degree we apply Proposition with the latter bound for > and achieve <\equation*> R*>*D*l*R*+\|)>*\|)>+,\,d;max,\|)>|)>. Thanks to Proposition we deduce <\equation*> ,\,d,l;\|)>=R*>*D*l*R*+\|)>*\|)>+,\,d;max,\|)>|)>. Finally, Proposition leads to <\eqnarray*> ||,\,d,l;\|)>>>|||*>*D*l*R*+\|)>*\|)>+,\,d;max,\|)>|)>>>|||*>*D*l*R*+\|)>*\|)>+R*-1>*D*R*max,\+\|)>*\|)>>>|||+,\,d;max,\|)>|)>>>|||*>*D*l*R*+\|)>*\|)>+R*-1>*D*l*R*+\|)>*\|)>>>|||+,\,d;max,\|)>|)>,\+\|)>\r*+\|)>>)>>>||>|>|||*>*D*l*R*+\|)>*\|)>.>>>> >-flattening> It remains to compute >-flattenings. For level , we recursively use the preceding fast conversions, multiplications and divisions over |~>>. In case of a trivial flattening, or one of first type, at level, recall that we set \0>. For the second type > is defined in Lemma. Let us now show how to compute the auxiliary data for each level.\ <\specified-algorithm> <\description-compact> Input>An almost reduced effectively separable and regular contact tower |)>t>> over |)>> at precision \R*\0>> a positive integer \d>. A >-flattening for |)>t>> at precision > and defect \*\*>, along with the auxiliary data needed in Lemma. We are given \> distinct elements in >. <|specified-algorithm> <\enumerate> Determine the integer sequence \\\i>=t> described before Lemma, along with the flattening types for each level. Let \\*\*>. For ,> do: <\enumerate> According to the type of the flattening at level , use Proposition, , or to increase the flattening for >> over |~>>. Compute +1>,\,\>> at precision +\> for a non-trival flattening. If the flattening at level is of first or second type, then compute the auxiliary data needed in Proposition or. Return |~>|)>>> along with the auxiliary data. <\proposition> Algorithm is correct and performs <\equation*> >*\*ht \|)>+R*>*D*R*\*\|)> operations in >. <\proof> The correctness of Algorithm is ensured by Lemmas, and. We begin with the following technical upper bound: <\eqnarray*> ||>***R>*max>,\+\|)>|)>>>|||>***R>*R>*R*+\|)>|)>>,\+\|)>\R>*R*+\|)>>)>>>|||>**D*R>*+\|)>|)>>>|||**D*R*\*\|)>.>>>> From Lemma and, we obtain <\eqnarray*> ||,\,d>;max>,\+\|)>|)>>>|||>***R>*max>,\+\|)>*\|)>>>|||**D*R*\*\|)>,>>>> and <\equation> ,\,d>;max>,\+\|)>|)>=R**D*R*\*\|)>. For a trivial flattening, Proposition gives the following cost for step2.a: <\eqnarray*> ||,\,d>;max>,\|)>|)>*log d>|)>>>|||+,\1;\>\|~>1;\+\>|)>*O>*max>,\|)>,1|)>*d>|)>>>|||+,\,d>;max>,\|)>|)>>>|||>**D>*R>*max>,\+\|)>*\|)>)>>>|||+R>***R>*max>,\+\|)>*\|)>*O>*max>,\|)>,1|)>*d>|)>>>|||)>>>|||**D*R*\*\|)>.)>>>>> For a flattening of first type, Proposition gives the following cost for step2.a: <\eqnarray*> ||>*\*ht \|)>>>|||+,\,d>;max>,\|)>|)>*>*max>,\|)>,1|)>*\|)>*\*ht \*log D|)>>>|||+O,\1;\>\|~>1;\+\>|)>*min>*max>,\|)>,1|)>*\*log D|)>>>|||>*\*ht \|)>>>|||+R**D*R*\*\|)>)>>>|||+R**D*R*\*\|)>)>>>|||>*\*ht \|)>+R**D*R*\*\|)>.>>>> For a flattening of second type, Proposition gives the following cost for step2.a: <\eqnarray*> ||-i>*,\,d>;max>,\+\|)>|)>*min>*max>,\+\|)>,1|)>*\|)>>>|||+,\,d>;max>,\|)>|)>>>|||+O,\1;\>\|~>1;\+\>|)>*min>*\,1|)>*|)>>>|||**D*R*\*\|)>)>>>|||+R**D*R*\*\|)>)>>>|||+R**D*R*+\|)>*\|)>)>>>|||**D*R*\*\|)>.>>>> If the flattening at level is non-trivial, then Proposition applied to > and > gives the following cost bound for step2.b: <\eqnarray*> |>|-i+1>*,\,d>;max>,\+\|)>|)>*>*max>,\+\|)>,1|)>*\|)>>>|||+,\,d>;max>,\+\|)>|)>*-i|)>>>|||-i+1>*R**D*R*\*\|)> and)>>>|||**D*R*\*\|)>.-i>\\>)>>>>> The rest of step2.b reduces to |)>=|)>> evaluations of >, which totalize <\eqnarray*> ,\1;\>\|~>1;\+\>|)>*|)>>||**D*R*+\|)>*\|)>>>>> by Lemma. We conclude by summing the costs of steps2.a and2.b for ,>, simplifying with. > We finally combine the preceding algorithms in order to prove our main result, first in terms of the parameter >, and then only in terms of >. <\theorem> Let |)>t>> be an almost reduced effectively separable and regular contact tower, r*\0>>, and let \D>. For all \R*\0>>, after precomputations (that only depend on the tower and >) of cost <\equation*> R*>*D*r*R*\*\|)>+>*\*ht \|)>, the following holds: <\itemize> Given l>|]>|)>;\>>, and l>|]>|)>;\>>, we can compute the truncated product |]>|)>+v|)>;\>> using <\equation*> R*>*D*l*R*\*\|)> operations in >. Given 2*l>|]>|)>;\>>, and l>|]>|)>;\>> monic of degree , we can compute the truncated quotient and remainder > B;\|]>|)>-v|)>;\>> and > B;\|]>|)>;\>> using <\equation*> R*>*D*l*R*\*\|)> operations in >. <\proof> First we assume that we are given \> distinct elements in >. The cost for obtaining a >-accelerated tower representation of |)>t>> is given in Proposition. Then in order to multiply two elements in |)>t>>, we convert them into the flattening, multiply them, and convert them back. The cost of the conversions is given in Lemma, and the costs of the product and the division are stated in Propositions and. Finally if we are not given sufficiently many elements in >, we appeal toA.2>: the overhead only induces logarithmic factors in the complexity bound. <\render-proof|Proof of Theorem> It is important to notice that constants hidden in the \P\Q of Theorem are independent of the value for >, so we may freely choose > in terms of>. From Lemma we know that <\equation*> \12*|log \>+8 In order to balance the contributions of >> and > in the complexity bound of Theorem, we take <\eqnarray*> >|>||exp * D>|)>|)>|\>\\>>>>> such that <\equation*> |log \>+8|)>*log 3=6*log \+o, so =O D|)>>, |log D>=O D>|)>>, and =D>>. <\bibliography|bib|tm-plain|> <\bib-list|22> S.S.AbhyankarT.Moh. Newton\UPuiseux expansion and generalized Tschirnhausen transformation. I. Reine Angew. Math.>, 260:47\U83, 1973. S.S.AbhyankarT.Moh. Newton\UPuiseux expansion and generalized Tschrinhausen transformation. II. Reine Angew. Math.>, 261:29\U54, 1973. M.Alberich-Carramiñana, J.Guàrdia, E.Nart, A.Poteaux, J.RoéM.Weimann. Polynomial factorization over Henselian fields. , 25:631\U681, 2025. J.vonzur GathenJ.Gerhard. . Cambridge University Press, New York, 3rd, 2013. M.Giusti, G.LecerfB.Salvy. A Gröbner free alternative for polynomial system solving. , 17(1):154\U211, 2001. J.vander Hoeven. . Scypress, 2020. J.vander Hoeven. On the complexity of symbolic computation. A.Hashemi, , ISSAC'22, 3\U12. New York, NY, USA, 2022. ACM. J.vander HoevenG.Lecerf. On the bit-complexity of sparse polynomial multiplication. , 50:227\U254, 2013. J.vander HoevenG.Lecerf. Accelerated tower arithmetic. Complexity>, 55:101402, 2019. J.vander HoevenG.Lecerf. Directed evaluation. Complexity>, 60:101498, 2020. J.vander HoevenG.Lecerf. Faster multi-point evaluation over any field. , HAL, 2024. . J.vander HoevenG.Lecerf. Plane curve germs and contact factorization. , 36:5\U106, 2025. R.Lebreton. Relaxed Hensel lifting of triangular sets. Symbolic Comput.>, 68(2):230\U258, 2015. G.Lecerf. On the complexity of the Lickteig\URoy subresultant algorithm. Symbolic Comput.>, 92:243\U268, 2019. S.MacLane. A construction for absolute values in polynomial rings. , 40(3):363\U395, 1936. I.Newton. . Manuscript, 1671. A.Perret du Cray. : interpolation, arithmétique, test d'identité>. , Université de Montpellier (France), 2023. A.PoteauxM.Weimann. Computing Puiseux series: a fast divide and conquer algorithm. , 5:1061\U1102, 2021. A.PoteauxM.Weimann. A quasi-linear irreducibility test in |]>>. , 31:6, 2022. A.PoteauxM.Weimann. Local polynomial factorisation: improving the Montes algorithm. A.Hashemi, , ISSAC '22, 149\U157. New York, NY, USA, 2022. ACM. M.V.Puiseux. Recherches sur les fonctions algébriques. , 15:365\U480, 1850. S.J.Berkowitz . On computing the determinant in small parallel time using a small number of processors. , 18:147\U150, 1984. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-bibliography> <\db-entry|+1PlYSeg92FURz2kB|book|TeXmacs:vdH:book> <|db-entry> > <\db-entry|+aqffSU2j7gUFFx|book|New1671> <|db-entry> > <\db-entry|+63PGfIkmrfTqAP|article|Puis1850> <|db-entry> > <\db-entry|+xxaGnrF1ruO5nld|techreport|vdH:pfact> <|db-entry> G. > > <\db-entry|+Z3c2FLs1B4bANv2|article|PoteauxWeimann2021> <|db-entry> M. > <\db-entry|+58kEKjZ1NKEM4eJ|article|PoteauxWeimann2022a> <|db-entry> M. > |]>>> <\db-entry|+58kEKjZ1NKEM4eF|inproceedings|PoteauxWeimann2022> <|db-entry> M. > > <\db-entry|+2DA9SrZp1x7JSbbb|article|AbhyankarMoh1973a> <|db-entry> T. > Reine Angew. Math.> <\db-entry|+2DA9SrZp1x7JSbbc|article|Abhyankar1973b> <|db-entry> T. > Reine Angew. Math.> <\db-entry|+1CA5X1QV108|article|AlGuNaPoRoWe2025> <|db-entry> J. E. A. J. M. > <\db-entry|+b63nLNQRu7|inproceedings|vdH:issac22> <|db-entry> > > '22> <\db-entry|+2EIRPFE3ONuyFfG|article|vdH:tower> <|db-entry> G. > Complexity> <\db-entry|+2WheVMn2twB3YIJ|book|GathenGerhard2013> <|db-entry> J. > <\db-entry|+1VcH6KZo2D1Zrx1G|article|vdH:direval> <|db-entry> G. > Complexity> <\db-entry|+14b0GIt51qPCwASG|article|Maclane1936> <|db-entry> > <\db-entry|+2NThGgQo9xz5mXG|phdthesis|PerretduCray2023> <|db-entry> > : interpolation, arithmétique, test d'identité> <\db-entry|+2DPRky2cs1xL3QZ|article|vdH:sparsemult> <|db-entry> G. > <\db-entry|+Hhx3e9Tk7c|techreport|vdH:bieval> <|db-entry> G. > > <\db-entry|+3E0M5F5LONx|article|Berkowitz1984> <|db-entry> <\db-entry|+TCcKHzBZDj8pPw|article|Lecerf2019> <|db-entry> > Symbolic Comput.> <\db-entry|+2mBymFTkuE|article|GiLeSa2001> <|db-entry> G. B. > <\db-entry|+kpzTLhn2H2Shql2|article|Leb15> <|db-entry> > Symbolic Comput.> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |\>|65>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > ||math-font-series||F>>|40>> ||math-font-series||F>>|40>> ||math-font-series||F>>|40>> ||math-font-series||F>>|40>> ||math-font-series||F>>|40>> ||math-font-series||F>>|40>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> TeXmacs:vdH:book New1671 Puis1850 vdH:pfact PoteauxWeimann2021 PoteauxWeimann2022a PoteauxWeimann2022 AbhyankarMoh1973a Abhyankar1973b vdH:pfact AlGuNaPoRoWe2025 vdH:pfact PoteauxWeimann2021 PoteauxWeimann2022a PoteauxWeimann2022 vdH:pfact vdH:issac22 vdH:tower vdH:pfact vdH:pfact vdH:pfact vdH:pfact vdH:pfact GathenGerhard2013 vdH:pfact vdH:tower vdH:direval vdH:pfact PoteauxWeimann2021 vdH:pfact Maclane1936 AbhyankarMoh1973a Abhyankar1973b PoteauxWeimann2022a AlGuNaPoRoWe2025 vdH:pfact PoteauxWeimann2022a PoteauxWeimann2022 vdH:tower vdH:pfact PerretduCray2023 vdH:sparsemult GathenGerhard2013 vdH:bieval vdH:pfact vdH:pfact vdH:pfact vdH:pfact vdH:pfact vdH:pfact vdH:tower vdH:direval vdH:direval vdH:bieval vdH:tower vdH:direval vdH:tower vdH:direval vdH:tower vdH:tower vdH:pfact vdH:pfact vdH:pfact vdH:pfact Berkowitz1984 GathenGerhard2013 Lecerf2019 Lecerf2019 vdH:direval vdH:direval GiLeSa2001 vdH:tower Leb15 vdH:pfact vdH:tower vdH:bieval vdH:tower <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |1.1.Main result |.>>>>|> > |1.2.Related work |.>>>>|> > |1.3.Overview of the paper |.>>>>|> > |math-font-series||font-shape||2.Weighted polynomials> |.>>>>|> |2.1.Notation |.>>>>|> > |2.2. Sparse representation |.>>>>|> > |2.3.Truncated polynomials |.>>>>|> > |math-font-series||font-shape||3.Elementary contact arithmetic> |.>>>>|> |3.1.Generalized contact towers |.>>>>|> > |3.2.Cost functions |.>>>>|> > |3.3.Multiplication |.>>>>|> > |3.4.Division |.>>>>|> > |3.5.Pre-inverse |.>>>>|> > |3.6.From height |h> to |t> |.>>>>|> > |3.7.Fast division |.>>>>|> > |math-font-series||font-shape||4.Initial primitive-valued representation> |.>>>>|> |4.1.Separable algebraic towers |.>>>>|> > |4.2.Relative ramified and primitive constant extensions |.>>>>|> > |4.3.Construction of primitive-valued elements |.>>>>|> > |4.4.Initial univariate-valued representation |.>>>>|> > |math-font-series||font-shape||5.Primitive-valued representation> |.>>>>|> |5.1.Hasse derivative and Taylor expansion |.>>>>|> > |5.2.Newton operator |.>>>>|> > |5.3.One lifting step |.>>>>|> > |5.4.Complete lifting |.>>>>|> > |math-font-series||font-shape||6.Flattened representation> |.>>>>|> |6.1.Flattenings |.>>>>|> > |6.2.Reduction in the flattened representation |.>>>>|> > |6.3.Flattened multiplication and division |.>>>>|> > |math-font-series||font-shape||7.Three types of flattening> |.>>>>|> |7.1.Trivial flattening |.>>>>|> > |7.2.First type of flattening |.>>>>|> > |7.3.Second type of flattening |.>>>>|> > |math-font-series||font-shape||8.Accelerated tower arithmetic> |.>>>>|> |8.1.|\>-flattening |.>>>>|> > |8.2.Conversion cost |.>>>>|> > |8.3.Fast product and division |.>>>>|> > |8.4.Fast |\>-flattening |.>>>>|> > |8.5.Proof of Theorem |->|-0.3em|>|0em||0em|>> |.>>>>|> > |math-font-series||font-shape||Bibliography> |.>>>>|>