Bounds for polynomials on algebraic numbers and application to curve topology
Daouda Niang Diatta Sény Diatta Fabrice Rouillier Marie-Françoise Roy Michael Sagraloff




 

 D. N. Diatta Université Assane Seck de Ziguinchor, Senegal   
           S. Diatta Université Assane Seck de Ziguinchor, Senegal
               F. Rouillier INRIA Paris, IMJ-PRG - Sorbonne Universités, France
           * M.-F. Roy IRMAR, Université de Rennes I, Campus de Beaulieu, 35042 Rennes CEDEX, France, 33(0)223236020

            marie-francoise.roy@univ-rennes1.fr
             M. Sagraloff HAW Landshut, Germany






Bounds for polynomials on algebraic 
numbers and 
application to curve topology
    
Daouda Niang Diatta Sény Diatta Fabrice Rouillier Marie-Françoise RoyMichael Sagraloff

 
    Received: date / Accepted: date
==============================================================================================




Let P ∈ [X, Y] be a given square-free polynomial  of total degree d with integer coefficients of bitsize less than 
 τ, and let 
    V_ℝ
     (P) := { (x,y) ∈ℝ^2, P (x,y)
     = 0 }
 be the real planar algebraic curve implicitly defined as the vanishing set of P. We give a deterministic 
 algorithm to compute the topology of V_ℝ (P) in terms of a 
 simple straight-line planar graph
 𝒢 that is isotopic to V_ℝ (P).
 The upper bound on the bit complexity of our algorithm is in (d^5 τ
 + d^6)[The expression "the complexity is in (f(d,τ))" with f  a polynomial in d,τ is an abbreviation for  the expression "there exists a positive integer c such that the complexity is in O((log d logτ)^c f(d,τ))".] ;
 which matches the current record bound
 for the problem of computing the topology of a planar algebraic curve.
However, compared to existing algorithms with comparable complexity, our method 
 does not consider any change of coordinates, and more importantly the returned 
 simple planar graph 
 𝒢 yields the cylindrical algebraic decomposition information of the curve
 in the original coordinates. 


Our result is based on two main ingredients: First, we 
derive amortized quantitative bounds on the roots of polynomials with algebraic coefficients as well as adaptive methods for computing the roots of 
bivariate polynomial systems
 that actually exploit this amortization. 
 The results we obtain are more general  that the previous literature.
Our second ingredient is a novel approach for the computation of the 
 local topology of the curve in a neighborhood of all 
 singular
 points.



 14P25 68W30 13P15  14Q05 68Q25






§ INTRODUCTION

Let P ∈ [X, Y] be a given square-free polynomial  of total degree d with integer coefficients of bitsize less than 
 τ. 
The problem of computing the topology of the planar algebraic curve

    V_ℝ
     (P) := { (x,y) ∈ℝ^2, P (x,y)
     = 0 },

 that is, the computation of 
a simple  straight-line  planar graph 
isotopic to
V_ℝ (P) inside ℝ^2, is a classical problem in
algorithmic real algebraic geometry with many
applications in Computer Aided Geometric Design. It is extensively studied in
the context of symbolic 
or semi-numerical computation; for instance, see <cit.> for recent references. 

Almost all 
 algorithms are based on some variant of
Cylindrical Algebraic Decomposition (C.A.D.): Decompose the X-axis into a finite number of
open intervals and points above which the curve has a cylindrical structure (i.e. the curve decomposes into disjoint function graphs above each of these intervals).
The special values are the projections of the X-critical  
points and vertical asymptotes
onto the X-axis.
Taking
points between two special values defines 
regular fibers.

   
  
Computing a 
simple planar graph 
isotopic to V_ℝ (P) inside ℝ^2 then
 essentially amounts to connecting the points of a regular fiber to the
points of its neighboring special fibers. 


There are two main difficulties:


  (1) computing the points of the special fibers,
which amounts for computing the real roots of univariate polynomials with real
algebraic coefficients, which are not square-free;

  (2) computing the number 
 curve segments
  that go to each of the
 points of the special fiber, to the left and to the right.


A usual strategy for  dealing with (2)
(see <cit.>),
consists in putting the curve in 
generic position. This is typically achieved by considering a 
shearing that maps X to X+s· Y for some (small) integer s. 
For most values of s,
the sheared curve has no asymptotes and each special fiber contains at most one X-critical or singular point, which considerably eases (2). 
Since a shearing does not change the topology of the curve, the 
simple planar graph 
returned by such algorithms is still isotopic to the curve. However,  
these algorithms do not compute a C.A.D. of the curve itself but only of the sheared curve. This  
is
critical in some applications, for instance, 
when the variables X and Y represent physical values (such as length) that are always positive, or probabilities that are between 0 and 1. The topology of the curve restricted to a quadrant or a square can be easily extracted from our output but would be complicated to recover after a shearing of the form X↦ X+s· Y. Another advantage of keeping the initial variables is that the sparseness of the input equation is preserved.



There exist algorithms <cit.> that go one step further by performing a shearing of the curve in the first step and an inverse shearing in the second step in order to eventually compute an isotopic 
simple planar graph 
whose vertices are located on the curve. Such algorithms compute the C.A.D. of the given curve, however the bit complexity of these methods falls clearly behind the best algorithms <cit.> for computing the topology of a planar algebraic curve, which achieve the complexity bound[The algorithm from <cit.> is deterministic, whereas <cit.> uses randomization. Both algorithm consider a shearing of the original curve and only return the C.A.D. information of the sheared curve.] (d^5τ+d^6). Our algorithm achieves the same complexity bounds, but it never performs any coordinate transformation and yields the C.A.D. information of the original curve. 



 Let P ∈ [X, Y] be a given square-free polynomial of total degree d
and integer coefficients of bitsize bounded by τ. There is a deterministic  
algorithm[We do not only prove existence of such an algorithm, but also present the algorithm in this paper.] that uses (d^5τ+d^6) bit operations to compute the topology of the curve 
    V_ℝ (P)= {(x, y) ∈ℝ^2 | P (x, y) = 0},
 in terms of a 
simple  planar graph 
 𝒢 that is isotopic to V_ℝ(P) inside ℝ^2. In addition, 𝒢 yields the C.A.D. information of the curve V_ℝ(P).[We remark that our algorithm returns a purely combinatorial representation of the C.A.D., however isolating intervals of all points in all special and regular fibers are computed in sub-steps of the algorithm. By refining these intervals, an isotopic 
 simple planar graph
  whose vertices are arbitrarily close to the curve can be 
 obtained.]
 




For our result, we use two main ingredients: The first one is a
new
efficient algorithm for computing the roots of a bivariate system in triangular form. 


Let R∈[X] and F∈[X,Y] be polynomials of total degrees N and n and with integer coefficients of bitsize less than Λ and τ respectively, such that  

    V_ℂ(R,F)={(x,y)∈ℂ^2| R(x)=F(x,y)=0}

is finite. Using a total number of bit operations bounded by

    (N^2Λ+N^3+n^5τ+n^6+n·max(n^2,N)· (Nτ+nΛ+Nn)),

we can compute


  (a) F(x,Y) as well as (F(x,Y),∂_Y F(x,Y)) for all complex roots x of R,

  (b) isolating disks 𝒟_x,y⊂ℂ for all complex roots y of all polynomials F(x,Y) for all complex roots x of R, as well as the corresponding multiplicities 
(y, F(x,Y))

  (b') for a given subset V⊂{(x,y)∈ℂ^2:R(x)=0 and F(x,y)=0} and an L∈ℕ, we can further refine all isolating disks 𝒟_x,y, with (x,y)∈ V, to a size less than 2^-L, in an additional number of bit operations bounded by 

    (N^2Λ+N^3+n·max(n^2,N)·(Nτ+nΛ+Nn)+L·(N·μ+n^2·∑_x ∈π_X(V)μ_x)),

where μ_x:=max_(x,y) ∈ V(y, F(x,Y)), 
π_X(V) is the projection of V on the X-axis and μ=max_x ∈π_X(V)μ_x.




The results in Theorem <ref> are significantly more general than the  results in the existing literature. 
For instance, recent work <cit.> makes two strong assumptions, namely that the degree of the polynomials F(x,Y) stays invariant for all roots x of R and that each F(x,Y) has only simple roots. In <cit.>, the polynomials F(x,Y) are allowed to have multiple roots, but the degree of F(x,Y) is assumed to be the same for all x. In addition, the analysis restricts to the special case, where R is either the resultant polynomial (F,∂_YF,Y) or its derivative.
None of these restrictions are needed in our results.

Using Theorem <ref> as our main tool, we obtain an efficient 
extension of the C.A.D.
for an algebraic curve;  see Theorem  <ref> and Theorem  <ref>.


Our second ingredient is an algorithm for computing the number of branches reaching a singular point inside an adjacency box (see Section <ref> for a precise definition) from information computed on the boundary of the box (see Figure <ref>, Figure <ref> and Algorithm <ref>). In order to achieve the complexity bounds we are aiming at, we need to accept that some of the desired information stays ambiguous[For instance, we aim to compute the location of the intersections of the curve with the four boundary edges of the adjacency box. However, we were not able to show how to distinguish between the special case, where the curve passes exactly the corner of a box, and the generic case, where the curve intersects one of the neighboring edges close to the corner, using only (d^6+d^5τ) bit operations. In such cases, the information at the corner of the box stays ambiguous.], however we will prove 
that these ambiguities do not prevent us from computing the correct connectivity; see Proposition <ref>.



For both of the above ingredients, we make essential use of amortized quantitative bounds for polynomials with algebraic coefficients by considering adaptive algorithms that make it possible to exploit this amortization; see Proposition <ref> and Proposition  <ref>. Finally a precise combinatorial description of the information needed to draw the
simple planar graph 
isotopic to the curve is given.
Since we perform our computations without any change of variables, vertical lines and asymptotes need to be dealt with.







  
Organization of the paper

The detailed description and complexity analysis of each
step of our algorithm  computing the isotopy type is given in Section <ref>.

The two preceding sections are devoted to univariate and bivariate results about roots of polynomials. In each of the two sections, a part is devoted to recalling well known results, but there are also several new results, particularly amortized quantitative bounds about algebraic numbers weighted with multiplicities (see Proposition <ref> and Proposition <ref>) that play a key role in the proof of Theorem <ref> 
 or in the results from Section <ref>.





§ UNIVARIATE RESULTS
 



 §.§ Quantitative geometry of the roots


In our complexity analysis we are going to use some quantitative results related to the geometry of the roots. We first fix some convenient notations and definitions.





  For a polynomial f = ∑^n_i = 0 a_i X^i ∈ℂ [X], with a_n ≠ 0, 
(f)=a_n,
 is the  leading coefficient of f.
   The length of f is defined as
    
    (f) := ∑_i = 0^n | a_i | .

  The following result is straightforward: 
  
    |f (x) | ≤ (f)·max (1, | x |)^n.

    The norm of f is defined as
    
    f  := √(∑_i = 0^n | a_i |^2) .

   Given x ∈ℂ, we denote by
 (x,f) the multiplicity of x as a root of f.
  We denote by  V_ℂ(f)
   the set of the distinct roots of f in ℂ so that
  
    f = (f) ·∏_x∈V_ℂ(f) (X - x)^(x,f).

  

 The square-free part f^⋆_ℂ of f is defined as
    
    f^⋆_ℂ = 
        ∏_x∈V_ℂ(f) (X - x).


  The Mahler measure of f is defined as
      
    (f) := | (f) | ·∏_x∈V_ℂ(f)max (1, | x|)^(x,f).

      Note the multiplicativity of  the Mahler measure 
       
    (f· g)= (f)· (g).


The norm of f, its length and its Mahler measure are related as follows  (see for example <cit.>):
  
    2^-n (f) ⩽ (f) ⩽ f  .

  The separation of f at x is defined as
  
    (x,f):= min_y ∈V_ℂ(f),   y ≠ x |y-x |.

 


Given a domain 𝔻 and  two polynomials f,g in 𝔻[X] of respective degrees n,n', we denote by (f,g) their resultant and by _k(f,g) their k-th subresultant coefficient, with  _0(f,g)=(-1)^n(n-1)/2(f,g) (see for example <cit.>).
If 𝔻=ℂ  it is well known (see for example <cit.>) that
 
    (f,g)=(f)^n'∏_x ∈ V_ℂ(f) g(x)^(x,f).

 The discriminant  (f) is the element of 𝔻 such that 
  
    (f)·(f)=_0(f,f')=(-1)^n(n-1)/2(f,f').

   If 𝔻=ℂ, denoting by x_1,…, x_(f) its complex roots  
    
    (f)=∏_i<j  (x_i-x_j)^2

   (see for example <cit.>).
   
   If φ is a ring homomorphism between  𝔻 and  𝔻', the following properties are  easy to prove
   
   
  * if φ(a_n)≠0, φ((f))=(φ(f)), 
   
  * if φ(a_n)=0, φ((f))=φ(a_n-1)^2 ·(φ(f)), 
  
 

 The k-th subdiscriminant coefficient _k(f) is the element of 𝔻 such that 
   
    (f)·_k(f)=_k(f,f').

If 𝔻=ℂ,  
m is the biggest index such that 
_n-m(f)≠ 0 
if and only if f has
m
 distinct roots in ℂ (see for example <cit.>).


Now we introduce the generalized discriminant which will play a key role in the statement of several of our quantitative results.
 We are not aware of a clear identification of this notion earlier in the literature.
 
  
 Let f  ∈ℂ [X] be a polynomial of degree n.
 Defining

    f^[i]:=f^(i)/i!,

the Taylor formula writes as

    f(α+X)=∑_i=0^n f^[i](α)X^i



   
     Let 𝔻 be a domain, and let f  in 𝔻[X] of degree n.
The generalized discriminant of f,   (f) is the element of 𝔻
such that

    (f)·(f)=(_X(f,∑_k=1^n U^k-1f^[k] ))
  where (g) is the tail coefficient of the polynomial g∈𝔻[U], i.e. the coefficient of its non-zero term of lowest degree in U. 
   
   
   Notice that the  generalized discriminant is never 0.  In the special case where all the roots of f are simple we have:
   
    (f)=(-1)^n(n-1)/2·(f)

  
      
    If 𝔻=ℂ, 
 
    [                                             (f)                                               =         (f)^n-2·∏_x ∈ V_ℂ(f) f^[(x,f)](x)^(x,f);                                                                                               = (f)^2n-2·∏_x,y ∈ V_ℂ(f),x≠ y (x-y)^(x,f) (y,f). ].
 
 
 
 
 The equality 

    (f)^n-2·∏_x ∈ V_ℂ(f) f^[(x,f)](x)^(x,f)=  (f)^2n-2·∏_x,y ∈ V_ℂ(f), x≠ y (x-y)^(x,f) (y,f),
  is clear.
  The equality  
    (f) = (f)^n-2·∏_x ∈ V_ℂ(f) f^[(x,f)](x)^(x,f)

  follows from the fact that
  
    _X(f,∑_k=1^n U^k-1f^[k] )=(f)^n-1·∏_x ∈ V_ℂ(f)∑_k=1^n U^k-1f^[k](x)^(x,f)

  by (<ref>).
 
 




  For a
  non-zero
   polynomial f ∈ℂ [X], we define
 
 
    (f)     :=    log((f))
      ,
     (f)     :=    log(|(f)|)+ ∑_x∈V_ℂ(f)(x,f)·log (max (1, |x|))
      ,
     (f)     :=    ∑_x∈V_ℂ(f)(x,f)· |log ( (x, f))|
     ,
    (f)    :=   ∑_x∈V_ℂ(f)(x,f) ·
     |log (|f^[(x,f)](x)|)|.

 


Notice that while
 
    (f)     =    log((f))
      ,
     (f)     =    log((f))

  we have, because of the absolute values,
 
    (f)    ≥   log((f))
     ,
    (f)    ≥   log((f)).



  As a consequence of (<ref>),

    (f) ≤ (f)+(f).





In the next step, we give a bound for (f) relating it to 
(f),
  and  (f).


Let f∈[X] be a polynomial of degree n.
If |(f)| ≥ 1,


    (f)∈ O(n(n+
    (f))+(f))





For the proof of Proposition <ref>, we need the following lemma:


Let S be a finite subset of ℂ. Consider a mapping ϕ: S↦  S that maps any element  x of S to an arbitrary element y∈ S∖{x} that minimizes the distance to x. Then, each element y∈ S has at most 6 preimages under the mapping ϕ.


As the distance between two preimages must be greater than
 or equal to 
 the distances between y and each of its preimages, the claim follows directly from the fact that if OAB is a triangle and AB≥max(OA,OB), then the angle 
BOA has a measure at least 2π/6. The value 6 is obtained in the case of a regular hexagon and its center.



Suppose that f is  monic.
We first prove that, for any root x of f,
it holds 

    (x,f)^(x,f)>|f^[(y,f)](y)|· 2^-n·max(1,|y|)^-n· (f) ^-1

where y≠ x is an arbitrary root of f that minimizes the distance to x. The inequality 
(<ref>) follows directly from the following computation:

    |f^[(y,f)](y)|   =
    ∏_
    z ∈V_ℂ(f)∖{y}|z-y|^(z,f)
       =(x,f)^(x,f)·∏_
    z ∈V_ℂ(f)∖{x,y}|z-y|^(z,f)
       ≤(x,f)^(x,f)·(f(X+y)).

Using the multiplicativity of the Mahler measure (see <ref>) it is easy to prove that

    (f(X+y))   ≤ 2^n· (f) ·max(1,|y|)^n.

by checking the case of a monic polynomial of degree 1.
Using Lemma <ref> and its notation,
each element y∈V_ℂ(f) has at most 6 preimages under the mapping ϕ. We thus conclude that

    ∏_x ∈V_ℂ(f)
    (x,f)^(x,f)
         >2^-n^2·(f)^-n·∏_x ∈V_ℂ(f)
    max(1,|ϕ(x)|)^-n·∏_x ∈V_ℂ(f)
     |f^[(ϕ(x),f)](ϕ(x))|
         ≥ 2^-n^2·(f)^-n·∏_x ∈V_ℂ(f)max(1,|x|)^-6n·∏_x ∈V_ℂ(f)
    min(1,|
    f^[(ϕ(x),f)](ϕ(x))|)
    
         ≥ 2^-n^2·(f)^-n·(f)^-6n·∏_x ∈V_ℂ(f)min(1,|f^[(x,f)](x)|)^6,

which shows that 

    -∑_x ∈V_ℂ(f)(x,f)<1(x,f)·log ((x,f))∈ O(n(n+
    (f))+(f)).
 
 It remains to estimate 
 
    ∑_x ∈V_ℂ(f)(x,f)≥ 1(x,f)·log ((x,f)).

  It holds that 

    (x,f)=|x-ϕ(x)|≤ 2 ·max(1,|x|)·max(1,|ϕ(x)|).

 Thus, we get 

    ∏_x ∈V_ℂ(f)(x,f)≥ 1(x,f)^(x,f)   ≤ 2^n·(f)^7

and finally

    ∑_x:(x,f)>1(x,f)·log((x,f))∈ O(n + (f)).

For the non-monic case, the claim follows from the result in the monic case and the fact that if |α|≥ 1


  * (f)≤(α f),

  * (f)≤(α f).





 §.§ Quantitative results for univariate polynomials with integer coefficients


For polynomials f with integer coefficients, we introduce the notation of the magnitude of f.


 A polynomial f∈[X] is of magnitude 
 bounded by
  (n,τ) if its degree is bounded by n and its bitsize is bounded by τ, that is, the absolute value of each of its coefficients is bounded by 2^τ.


 If f∈[X] is of magnitude 
 bounded by
 (n,τ),
then
f^[k] is of magnitude
bounded by (n,τ+n) (using Notation <ref>), using that nk<2^n for all k=0,1,…,n.

It is clear that
 
    (f)≤ (n+1)· 2^τ.

 

Moreover, (<ref>) implies

    (f)
      ⩽√(n+1)· 2^τ,

and thus

    (f) ∈O (τ+log (n)).



Our next aim is to give bounds on (f) that depend on the magnitude (n,τ) of f. In Proposition <ref>, we have already derived a bound on (f) that is related to n,
(f)
 and (f).
 Given (<ref>) 
 we are left to bound (f) in terms of n and τ. For this, we first derive a general bound on the product of the absolute values that a sequence of integer polynomials g_1,…,g_m takes at corresponding roots of f. A corresponding bound on  will then follow by applying our result to the sequence 
 of f^[k], k=(f)-1,…, 0.



Let f be a 
non-zero
polynomial in [X]
 of magnitude 
bounded by
(n_1,τ_1) 
 and let (g_i)_1 ≤ i ≤ m be a sequence of 
 non-zero
 polynomials in [X] each
  of magnitude 
bounded by
(n_2,τ_2).


  a)
Let A ⊂V_ℂ(f) be
such that for each x∈ A, there exists i(x)∈{1,…,m}  with g_i(x)(x)≠0. Then, 
it holds
 
    ∑_x∈ A(x,f)
         log (|g_i(x) (x)|) ∈Õ(n_1τ_2+n_2τ_1).

    
    
  b) Suppose moreover that, for every root
 x∈V_ℂ(f),
there exists an i such that g_i(x)≠0. Denoting by i(x) the smallest value of i such 
 that g_i(x)≠0, it holds
 
    ∑_x∈V_ℂ(f)(x,f) |log (|g_i(x)(x)|) | ∈Õ (n_1 τ_2+n_2 τ_1).

    




a) 
 For any x ∈ A, we have

    |g_i(x)(x)|≤2^τ'_2·max(1,|x|)^n_2;

by applying (<ref>) and
(<ref>)
, with τ'_2 defined by  2^τ'_2=(n_2+1)2^τ_2.
Then, 

    [                      ∏_x ∈ A|g_i(x)(x)|^(x,f)                                             ≤      ∏_x∈ A 2^τ'_2 (x,f)·max(1,|x|)^n_2 (x,f);                                                                                           ≤ ∏_x∈V_ℂ(f) 2^τ'_2 (x,f)·max(1,|x|)^n_2 (x,f), ]

using (<ref>).
Finally, we obtain

    [                           ∏_x∈ A|g_i(x)(x)|^(x,f)                                                 ≤                             2^τ'_2 ∑(x,f)(f)
    ^n_2;                                                                                                   ∈ 2^O(n_1 log (n_2)+n_2 τ_1+n_1 τ_2+n_2 log (n_1)), ]


as ∑_x∈ A(x,f)≤ n_1, 
(f) ≤ 2^τ_1+log (n_1+1), and  2^τ'_2=(n_2+1)2^τ_2.

b) We want to prove that 

    ∏_x∈V_ℂ(f)|g_i(x)(x)|^(x,f)∈ 2^-O(τ_1 n_2).

We set 
    g (X,U)= g_1 (X)+ U g_2(X)+⋯ +U^m-1 g_m (X)
 and consider

    _X(f,g)= (f)^n_2·∏_x∈V_ℂ(f)g(x,U)^(x,f).

 The polynomial _X(f, g) is then a polynomial in U with integer coefficients. The coefficient of its term of lowest degree, which is a non-zero  integer
 has absolute value equal to 
    |(f)|^n_2·∏_x∈V_ℂ(f)|g_i(x)(x)|^(x,f).

In particular, this shows that the latter term has absolute value at least 1.
It is further clear that 

    |(f)|^n_2∈ 2^O(τ_1 n_2),

and thus (<ref>) holds.

We now define 
    A:={ x | f(x)=0, |g_i(x)(x)|≥ 1 }.
 
Since for any x ∈ A, |g_i(x)(x)| ≥ 1, it is clear by (<ref>) that



    0≤∑_x ∈ A(x,f)·log (|g_i(x)(x)|)≤ c ∈ O(n_1 τ_2+n_2 τ_1+n_2 log (n_1)+n_1 log (n_2))


It follows by (<ref>)
that 

    ∑_x∈V_ℂ(f)-(x,f) ·log (|g_i(x)(x)|)∈ O(n_2 τ_1).


Hence, 
we obtain

    ∑_x∈V_ℂ(f)(x,f) |log (|g_i(x)(x)|)|∈ O(n_2 τ_1+n_1 τ_2).




The following result has already been proven in <cit.>
 but we give here a
 much
  simpler proof based on Proposition <ref>. 
 
 


Let f∈[X] be a 
non-zero
polynomial of magnitude
bounded by
 (n,τ), then
 (f)∈(nτ+n^2).
 


Using Proposition <ref> b) 
for the sequence f^[k], k=(f)-1,…,0, we obtain

    (f)∈(nτ+n^2).

Since  
(f)∈ O(τ+log (n))
by
 (<ref>), we conclude by 
 Proposition <ref>.




Hereafter, we recall some quantitative and complexity results which will be used in the
complexity analysis of our algorithms.


 (see for example <cit.>) Let 
  f∈[X]
  be a non-zero polynomial
  of magnitude
bounded by
 (n,τ) and g∈[X]
 a non-zero polynomial 
  of degree n_1 dividing f.
 Then, g is of magnitude 
bounded by
(n_1,n_1 + τ + log (n +
 1)).


We need to give details about content and greatest common divisors (gcd) in the ring [X].



Given  a non-zero-polynomial f∈[X]
its
content (f)  is defined as the gcd in  of the coefficients of f.  For every  g∈[X] dividing f, (g) divides (f) in .

If (f)=1, f is content-free. Every  g∈[X] dividing a content-free polynomial is content-free.

Given 
two non-zero polynomials f∈[X] and 
g∈[X]
their gcd (f,g) is defined (up to sign) as the unique polynomial in [X] which is proportional to the gcd of f and g in [X] and is of content 
((f),(g)).
 
 The content of the derivative f' of f is a multiple of the content of f, so ((f,f'))=(f) and f^⋆=f/(f,f') its square-free part is content-free.



 <cit.> Let f, g ∈ [X] be two 
 non-zero 
 polynomials of respective magnitude
bounded by
 (n_1,τ_1) and (n_2,τ_2). Computing
 their gcd has  bit complexity  
    (max(n_1,n_2)· (n_1τ_2+n_2τ_1)).




 <cit.>  Let f∈ [X] 
 be a non-zero
 polynomial of
 magnitude
bounded by
 (n,τ). Given a non-zero polynomial g ∈ [X]
 that divides f, computing the quotient of f divided by g
 has bit complexity of (nτ+n^2).


  
 Let f∈ [X]
 be a non-zero
 polynomial of
 magnitude
bounded by
 (n,τ).  computing the square-free part f^⋆ of f 
 has bit complexity 
 (n^2τ).


 
 
 Let p=r/s a rational number with (r,s)=1.
  We denote by λ(p) its bitsize, defined by the sum of the bitsizes of its numerator r and denominator s.
    For an interval I=[a,b], a<b with rational endpoints, we denote by  |I|=b-a its length and by λ(I) the maximum of λ(a) and λ(b).
   


 <cit.> Let 
 f ∈ [X]
  be a non-zero
 polynomial of magnitude 
bounded by
(n,τ).
 Let r a rational number of bitsize λ(r). Then, the evaluation of f at r
 can be performed using (n (τ + λ(r))) bit operations and the bitsize of
 the output f (r) is (τ + n·λ(r)).




 §.§ Root isolation


We now focus on the problem of computing the roots of a given univariate polynomial. Here, we consider the two different but related problems of the computation of disjoint isolating regions and the approximation of the roots to a certain precision. Notice that isolating regions allow us to distinguish between two distinct roots, and thus also to determine the number of distinct roots. However, in general, isolating regions do not allow us to estimate the actual distance between two distinct roots as such regions might be considerably larger than the actual separation of the isolated root.

In order to overcome this issue, we are aiming for the computation of so called well-isolating regions from which we can derive a good estimate for the separation of a root x or, more generally, for the distance from x to any other root y.  
This good estimate plays a key role in the complexity for refining roots whenever needed.

 Let f ∈ℂ [X] be a polynomial of degree n. Then, we define:
 
  
  (a) A well-isolating interval  ℐ=(a,b) for a real root x of f  contains x, 
  and it holds that 
  32 · n · |b-a|<(x,f).
  
  (b) A well-isolating disk 𝒟_r(m)={x∈ℂ| |x-m|≤ r}  for a complex root x of f contains x,
  and it holds that 
  64 · n · r<(x,f).

As a consequence a well-isolating interval (resp. disk) contains only one real (resp. complex) root of f.



In what follows, we often have to deal with approximations of polynomials and to compute approximations of an exact value that a given polynomial takes at a certain point. The following definitions will turn out to be useful in order to specify these computations.


For a complex number a∈  and an integer L, we say that a dyadic Gaussian number of the form 

    ã=c·2^-L-1
    +i·d·2^-L-1∈+i·,
 
with c,d∈, is an (absolute) L-bit approximation of a if |a-ã|<2^-L.

For a polynomial f=a_0+⋯+ a_n· X^n∈[X] with arbitrary complex coefficients and an integer L, we say that a polynomial f̃=ã_0+⋯ +ã_n· X^n 
is an 
(absolute) L-bit approximation
of f if for every i, ã_i is an (absolute) L-bit approximation of a_i.


The following result is useful.
  
 <cit.> Let 
 f ∈ [X]
  be a
non-zero
 polynomial of magnitude 
bounded by
(n,τ), x ∈ be an arbitrary complex value, and L be a positive integer. 

We can compute
a  dyadic approximation β̃=
 b·2^-L-1 of β:=f(x) , with b∈[i] and |β-β̃|<2^-L, using (n(L+n·log(max(1, |x|))+τ)) bit operations. 
 


The following propositions 
summarize
 the results on root isolation and approximation for a complex polynomials we use in the paper. 



 (<cit.>[See also
 <cit.> for comparable results.]) Let
  f ∈ℂ [X]
  be a
  non-zero polynomial of degree n with 
  1≤ |(f)| ≤ 4. 
  Suppose that the number m of distinct roots of f is given, then it holds:
	
	
  (a) Using a number of bit operations bounded by
	
    (n·(n^2+n(f)
    +(f)))

	we can compute, for all x∈V_ℂ(f),
	the multiplicities (x,f) as well as well-isolating disks 𝒟_r(x)(m(x))⊂  with dyadic centers m(x) and dyadic radii r(x) such that 
 the bitsizes of  all m(x) and r(x) sum up to 
 
    (n+(f)+(f^⋆_ℂ)) .


 
 As input, we need an oracle giving an absolute L'-bit approximation of f, where L' is bounded by 

    (n(f)+(f)+(f)).




  (b) Let V^*⊂V_ℂ(f) be a subset of the roots of f, μ=max_x∈V^*(x,f), and let L be a given positive integer. Then, we can further refine the isolating disks 𝒟_r(x)(m(x)) for all roots x in V^* to a size less than 2^-L using 

    (n·(L·μ+n^2+n(f)
    +(f)))

bit operations.[<cit.> only provides a bound for the refinement of all isolating disks (i.e. for V^*=V_(f)), however, from the proof of <cit.>, the claimed bound directly follows. In addition, in <cit.>, the additive term nL·μ appears in the bound on the needed input precision. We remark that this is a typo and that the actual bound is better by a factor n. The proof of <cit.> clearly shows this fact.] As input, we need an oracle giving an absolute L'-bit approximation of f, where L' is bounded by 

    (L·μ+n(f)+(f)+(f)).





In the literature, the special case of an integer polynomial f with coefficients of bitsize at most τ has attracted a lot of interest.
 The following result, which provides bounds on the  isolation of the roots as well on the problem of further refining the isolating disks, is an almost straight forward consequence of Proposition <ref> (applied to the polynomial f·(f)^-1).


 <cit.> [See also
 <cit.>] Let 
 f ∈ [X]
  be a
  non-zero
  polynomial of magnitude 
bounded by
(n,τ).
 Using (n^2τ+n^3) bit operations, one can compute
 
 
  (a) well-isolating disks 𝒟_r(x)(m(x))⊂ for all complex roots x of f with dyadic centers m(x) and dyadic radii r(x) such that 
 the bitsizes of  all m(x) and r(x) sum up to (n τ), and
 
  (b) the multiplicities (x,f) of each of the roots x.
  
  (c) For an arbitrary positive integer L, one can further refine all isolating disks to a size less than 2^-L using (n^2τ+n^3+nL) bit operations.[Notice that, in contrast to the general case, where the coefficients of f are not necessarily integers, the additional factor max_x∈V_(f)(x,f) is missing. This is due to the fact that, within the given complexity, we can first compute the square-free part f^⋆ of f and then work with f^⋆ to refine the isolating disks.]
 



Finally we can also identify common roots  of a polynomials f with polynomials of a family g_1,…,g_m.


Let 
f,g_1,…,g_m∈ [X]
 be non-zero 
 polynomials of magnitudes
bounded by
 (d,τ), (d_1,τ_1),…,(d_m,τ_m), respectively, and let N,Λ be positive integers such that d+d_1+⋯+d_m<N and τ+τ_1+⋯+τ_m<Λ. Then, 
we can isolate all roots of f and all polynomials g_i, and identify all common roots of each  pair (f,g_i) using no more than 
(N^2Λ+N^3) bit operations.
Within the same complexity, we can also determine the signs (0, 1 or -1) of the g_i at the real zeroes of f.





We 
first compute the square-free part f^⋆
using 

    (d^2 τ)∈(N^2Λ)

 bit operations using 
 Corollary <ref>.
 The magnitude
 of  f^⋆
 is bounded by (d,O(d+τ)).
  Then, we may compute h_i:=(f^⋆,g_i) for all i using 
 
    (∑_i=1^m max(d,d_i)·(dτ_i+d d_i+d_i τ))∈(N(dΛ+Nτ+dN)

bit operations due to Proposition <ref>. In the next step, we compute well-isolating disks for all complex roots of the polynomial f^⋆ as well as for the complex roots of all polynomials h_i. We then refine the isolating disks for the roots of all polynomials h_i to a size less than min_x∈ V_ℂ(f)(x,f)/4. Since (f) is bounded by
 (NΛ+N^2), this can be achieved using (N^2Λ+N^3) bit operations
 according to Proposition <ref>.
 
 Notice that, after this refinement, each isolating disk 𝒟' for a root of h_i intersects exactly one isolating disk 𝒟 for a root of f, and thus 𝒟 and 𝒟' isolate one common root. Hence, in order to identify common roots of f and g_i, we just have to determine all intersections between the isolating disks for the roots of h_i and those for the roots of f. For this, we first compute a lexicographic sorting of all centers of the isolating disks 𝒟 for the roots of f, which uses (d^2 τ) bit operations as we need O(dlog d) many comparisons, each of precision (dτ). Then, for a given isolating disk 𝒟' for a root of h_i, we can determine the unique disk 𝒟 that intersects 𝒟' using 
 (NΛ+N^2) bit operations as the needed precision is bounded by
  (NΛ+N^2) 
  and only O(log d) many comparisons are needed. Hence, the total complexity for this step is also bounded by
   ∑_i=1^m d_i·(NΛ+N^2)∈(N^2Λ+N^3).
 
For the sign determination part, we simply compute sufficiently good L-bit approximations γ_i,x of g_i(x) for all i and all real roots x of f with g_i(x)≠ 0. That is, we have to compute L-bit approximations γ_i,x for L=1,2,4,… such that |γ_i,x|>2^-L, which then implies that sign g_i(x)=signγ_i,x. Obviously, we succeed in doing so as soon as L is larger than |log (|g_i(x)|)|. Hence, for a specific real root x of f_i:=f^⋆/(f^⋆,g_i), the cost for this step is bounded by 
(d_i(|log (|g_i(x)|)|+d_i·log(max(1, |x|))+τ_i)) bit operations using 
 Proposition <ref>. 
The total cost is thus bounded by

    ∑_i=1^m d_i^2·∑_x∈ V_ℝ(f)log(max(1,|x|))  +   N·∑_i=1^m d_iτ_i   +  ∑_i=1^m d_i∑_x∈ V_ℝ(f_i)|log( |g_i(x)|)|

The first term is upper bounded by 
 N^2·(f)∈(N^2Λ)
, and the second term is upper bounded by N·∑_i=1^m d_i·∑_i=1^mτ_i∈ O(N^2Λ). For the last term, we use Proposition <ref> b) to show that ∑_x∈ V_ℝ(f_i)|log (|g_i(x)|)|∈(NΛ+N^2) for all i, and thus also ∑_i=1^m d_i∑_x∈ V_ℝ(f_i)|log (|g_i(x)|)|∈(N^2Λ+N^3).







§ BIVARIATE RESULTS



Similar to our definition of the magnitude of a univariate polynomial, we introduce the following definitions for bivariate polynomials:


 A polynomial F∈[X,Y] is of magnitude
bounded by
 (n,τ) if its
 total
  degree is bounded by n and the 
 bitsize of each of its coefficients is bounded by 
 τ.







 §.§ Amortized bounds for bivariate systems


We consider an arbitrary polynomial R∈[X] of magnitude
bounded by
 (N,Λ). Given
  x∈,
 we denote by μ(x)=(x,R) its multiplicity as a root of R. 
  We further consider a bivariate polynomial

    F(X,Y)=f_n_y(X)· Y^n_y+⋯+f_0(X) ∈[X,Y]
 
of magnitude
bounded by
 (n,τ), such that 

    V_ℂ(R,F)={(x,y)∈ℂ| R(x)=F(x,y)=0}

 is finite.

For a 
root x of R, we denote by n(x) the degree of F(x,Y), which might be smaller than n_y but at least 0, since V_ℂ(R,F) is finite. Notice that, for n(x)≠ n_y, we have f_n(x)(x)≠ 0 and f_n(x)+1(x)=⋯=f_n_y(x)=0.
For a root 
y of F(x,Y), we denote in all Section <ref> , with a slight abuse of notation,

    ν(y)=(y,F(x,Y))

the multiplicity of y as a root of F(x,Y).

The following proposition provides amortized complexity bounds on the sum of lengths and  Mahler measures of the polynomials F(x,Y).


Let R∈[X] and F∈[X,Y] be 
non-zero
polynomials of magnitude
bounded by
 (N,Λ) and  (n,τ) respectively such that V_ℂ(R,F) is finite. Then, it holds that

    ∑_x∈V_ℂ(R)μ(x)·(F(x,Y)) ∈(Nτ+nΛ+n N)


    ∑_x∈V_ℂ(R)μ(x)·(F(x,Y)) ∈(Nτ+nΛ+n N)



For each root x of R in ℂ, we have 

    2^-n(x)·(F(x,Y))≤(F(x,Y))≤ F(x,Y)
 using Definition <ref> and according to (<ref>). 


Since n(x)≤ n and  ∑_x∈V_ℂ(R)μ(x) = N, it holds that 
    ∑_x∈V_ℂ(R)n(x)μ(x) ≤ n N
 and thus 
    2^-n N≤ 2^-∑_x∈V_ℂ(R)n(x)μ(x).

Let ℓ(x) be such that 

    | f_ℓ(x)(x)|=max_j=0,…,n_y | f_j(x)|.

We have 
    |f_n(x)(x)| ≤(F(x,Y))≤ (n_y+1)· | f_ℓ(x)(x)|


    F(x,Y)≤√(n_y+1)· | f_ℓ(x)(x)|,

hence 
denoting by 

    A   =   ∏_x∈V_ℂ(R)
    |f_n(x)(x)|^μ(x)
    
    B   =   ∏_x∈V_ℂ(R) | f_ℓ(x)(x)|^μ(x),


    A
    ≤∏_x∈V_ℂ(R)(F(x,Y))^μ(x)≤ (n_y+1)^N · B

and

    2^-nNA
    ≤∏_x∈V_ℂ(R)(F(x,Y))^μ(x)≤√(n_y+1)^N · B.



The claims (<ref>) and (<ref>) follow by Proposition  <ref>  applied to R and the family f_j.


Our next aim is to prove the following Proposition.



Let 
R(X)∈[X] 
be a non-zero polynomial
of magnitude
bounded by
 (N,Λ) and F(X,Y)∈[X,Y]
be of magnitude 
bounded by
(n_1,τ_1), and suppose that  

    V_ℂ(R,F)={(x,y)∈ℂ^2| R(x)=F(x,y)=0}

is finite.
Let G_1,…,G_m  in ℂ[X,Y] be polynomials of 
magnitude bounded by  (n_2,τ_2).




  (a) Suppose that A⊂ V_ℂ(R,F) and that, for every (x,y)∈ A, 
 i(x,y)∈{1,…,m} is such that G_i(x,y)(x,y)≠0. Then, it holds that:
 
    ∑_(x,y) ∈ Aμ(x)  
      ν(y)
         log (|G_i(x,y) (x, y)|) ∈Õ((τ_2n_1+τ_1n_2)N+(Λ+N) n_1n_2).


  (b)  Suppose that  G_1,…,G_m∈[X,Y] and that, for every  (x,y)∈ V_ℂ(R,F),
there exists i such that G_i(x,y)≠0.
Denoting by i(x,y) the smallest value of i such 
 that G_i(x,y)≠0, we have
 
    ∑_(x,y) ∈ V_ℂ(R,F)μ(x)  
      ν(y)
        | log (|G_i(x,y) (x, y)|) |∈Õ((τ_2n_1+τ_1n_2)N+(Λ+N) n_1n_2).

  where  
    V_ℂ(R,F)_x:={y∈ℂ| F(x,y)=0}.

    


a) 
First note that,

    |G_i(x,y)(x,y)|≤
    2^τ'_2max(1,| x |)^n_2max(1,| y |)^n_2,

where τ'_2:=⌈log( (n_2+1)^2 2^τ_2)⌉∈ O(τ_2+log (n_2)).
Further notice that 

    ∏_(x,y)∈ A 
    2^τ'_2 μ(x)≤∏_x∈V_ℂ(R) 2^τ'_2 n_1 μ(x)∈ 2^ O((τ_2+log (n_2)) n_1N)

and

    |(R)^n_1n_2| ∏_(x,y)∈ Amax(1,| x|)^μ(x)
    ν(y) 
    n_2   ≤   (R)^n_1n_2∈ 2^O((Λ+log( N)) n_1 n_2).


Hence,
since

    ∏_x∈V_ℂ(R) 
    |(F(x,Y))^μ(x)|
    ∏_y| (x,y)∈ Amax(1,| y |)^ν(y)μ(x)≤∏_x∈V_ℂ(R)(F(x,Y))^μ(x)

it follows that

    ∏_(x,y)∈ Amax(1,| y |)^μ(x)ν(y) n_2∈ 2^Õ((τ_1 N+Λ n_1+n_1 N)n_2)

by 
Proposition  <ref> and Proposition <ref>.
We thus conclude that

    ∏_(x,y)∈ A |G_i(x,y)(x,y)|^μ(x)ν(y)∈ 2^Õ((τ_2 n_1+τ_1 n_2)N+(Λ+N) n_1n_2)

and

    ∑_(x,y)∈ Aμ(x) ν(y)  log (|G_i(x,y) (x,y)|) ∈Õ((τ_2 n_1+τ_1 n_2)N+(Λ+N) n_1n_2).

  
b) In the first step, we aim to prove that 

    ∏_(x,y)∈ V_ℂ(R,F) |G_i(x,y)(x,y)|^μ(x)ν(y)≥1/E”

where E” is a natural number of
bitsize O(Λ n_1n_2+τ_1 n_2 N).

Let as before

    F(X,Y):=f_n_y(X)Y^n_y+…+f_0(X),
 with n_y=_Y(F)≤ n_1, and R^⋆ the square-free part of
R which is content-free (cf Definition <ref>).


We define the polynomial sequence (R^⋆_ℓ (X))_ℓ∈[1,n_y]∈[X],
such that

    (F (x, Y)) =ℓ⟺ R^⋆_ℓ (x) = 0,

 as follows.
 We first compute a family of polynomials R^⋆_ℓ whose zeroes characterize
_Y(F(x,Y))=ℓ.
 
    R^⋆_≤ n_y (X) :=R^⋆(X),

 and
  
    R^⋆_≤ℓ-1 (X) :=  ( R^⋆_≤ℓ
     (X), f_ℓ(X)),    R^⋆_ℓ-1 (X) :=  R^⋆_≤ℓ (X)/ R^⋆_≤ℓ-1
     (X).

for all ℓ∈{n_y, …, 1}. 
Notice that

    R^⋆   =   ∏_ℓ∈{0,…,n_y} R^⋆_ℓ (X)




 We further define the following content-free polynomials in [X].
 
    R^⋆_ℓ,>1 (X) :=(R^⋆_ℓ,R'), R^⋆_ℓ,1 (X):=R^⋆_ℓ/R^⋆_ℓ,>1(X)

 and, 
 for all i ∈{1, …, N }, 
    R^⋆_ℓ,>i (X) :=  (R^⋆_ℓ,>i-1
     (X), R^[i](X)),    R^⋆_ℓ,i (X) := R^⋆_ℓ,>i-1 (X)/R^⋆_ℓ,>i
     (X).

It is clear using Equation (<ref>) that
 (F (x, Y)) =ℓ and x is a root of multiplicity μ of R if and only if
R^⋆_ℓ,μ (x) = 0.

Notice that

    R^⋆   =   ∏_ℓ,μ R^⋆_ℓ,μ
    
    R   =   (R) ∏_ℓ,μ (R^⋆_ℓ,μ)^μ


Let 

    F_ℓ(X,Y):=f_ℓ(X)Y^ℓ+…+f_0(X),

and

    G=G_1+U G_2+…+U^m-1G_m.
 
We further define

    Z_ℓ,μ:=V_ℂ(R^⋆_ℓ,μ,F) ⊂ V_ℂ(R,F)

and 

    A_ℓ,μ(U):=_X(_Y(F_ℓ,G),R^⋆_ℓ,μ)∈[U].

Let 
    Q_ℓ(U,X):=_Y(F_ℓ,G)
 and 
notice that

    Q_ℓ(U,x)=f_ℓ(x)^O(n_2)∏_y| (x,y)∈ Z_ℓ,μ G(x,y,U)^ν(y).

Denoting by δ_ℓ≤ n_1n_2 the degree of Q_ℓ (U,X) with respect to X and n_ℓ the degree of f_ℓ with respect to X,

    A_ℓ,μ(U)=(R^⋆_ℓ,μ)^δ_ℓ∏_x| R^⋆_ℓ,μ(x)=0  f_ℓ(x)^O(n_2)∏_(x,y)∈ Z_ℓ,μ G(x,y,U)^ν(y)

The coefficient of the term of smallest degree in U of A_ℓ,μ(U) is a non-zero integer and equal to

    (R^⋆_ℓ,μ)^δ_ℓ-n_2 n_ℓ_X(f_ℓ,R^⋆_ℓ,μ)^n_2∏_(x,y)∈ Z_ℓ,μ G_i(x,y)(x,y)^ν(y).

Since δ_ℓ-n_2 n_ℓ∈ O(n_1n_2), 
(R) ∏_ℓ,μ(R^⋆_ℓ,μ)^μ= (R)∈ 2^O(Λ), and 
    ∏_ℓ,μ_X(f_ℓ,(R^⋆_ℓ,μ)^μ)=_X(f_ℓ,R)∈ 2^O(τ_1 N+Λ n_1),
 
we conclude that

    ∏_(x,y)∈ V_ℂ(R,F) |G_i(x,y)(x,y)|^μ(x)ν(y)≥1/E”

with E”:=|(R)^n_1n_2_X(f_ℓ,R)^n_2|∈ 2^O(Λ n_1n_2+τ_1 n_2 N).

Finally, 
we have
 
    ∑_(x,y)∈V_ℂ(R,F) -μ(x)ν(y)log( |G_i(x,y)(x,y)| ) 
    ∈ O(Λ n_1n_2+τ_1 n_2 N).


Defining  A:={(x,y)∈ V_ℂ(R,F)| |G_i(x,y)|≥ 1},
and using (<ref>), (<ref>) and  (<ref>),
we obtain
finally

    ∑_x∈V_ℂ(R,F)μ(x)ν(y)| log (|G_i(x,y)(x,x)| )|  ∈Õ((τ_2n_1+τ_1n_2)N+(Λ+N) n_1n_2)
 






 The following proposition provides amortized complexity bounds on the sum of the Mahler measures of the polynomials F(x_i,Y), the separators of the roots x_i,j as well as the absolute values of the first non-vanishing derivatives of F(x_i,Y) at the roots x_i,j:


We denote 

    F^[k]=∂_Y^kF/k!.




Let 
R(X)∈[X]
be a non-zero polynomial
of magnitude 
bounded by
(N,Λ) and F(X,Y)∈[X,Y]
be of magnitude 
bounded by
(n,τ), and suppose that  

    V_ℂ(R,F)={(x,y)∈ℂ^2| R(x)=F(x,y)=0}

is finite.
Then, it holds that


  (a) ∑_x∈V_ℂ(R)μ(x)·(F(x,Y))∈(n(Nτ+nΛ+Nn)).

  (b) ∑_x∈V_ℂ(R)μ(x)·(F(x,Y)) ∈(n(Nτ+nΛ+Nn)),





(a) is an immediate consequence of Proposition <ref>
applied to the family F^[k].
(b) follows directly from (a), Proposition <ref> and Proposition <ref>.





 §.§ Fixing the degree and the 
number of distinct roots
in the fibers

We first  give results on the multiplicities of the roots of F(x,Y) at the X-critical points of F. 

Consider a bivariate polynomial

    F(X,Y)=f_n_y(X)· Y^n_y+⋯+f_0(X) ∈ℂ[X,Y].
 
Notice that

    V_ℂ(F)={(x,y)∈ℂ^2| F(x,y)=0 }

 contains no vertical line if and only if the polynomials f_i(X), i=0,…,n_y, do not share a common non-trivial factor.
 In this case, let 
    _X(V_ℂ (F)) := {(x, y) ∈ℂ^2 | F (x, y) =∂_Y F(x,y)= 0}
 
 be the set of X-critical points of F.


    
 Let
  F∈ℂ[X,Y]
   be   such that V_ℂ(F) contains no vertical line.
  Given x∈ℂ,
      
    ∑_x| (x,y)
          ∈_X (V_ℂ (F))  ((y, F_n(x)(x,Y))-1)
      ≤(x,_Y(F_n(x))).
 
  
    The proof of  Proposition <ref>  is based on the following lemma.
  
    
  
  Let F and G be two 
  non-zero
   bivariate polynomials. 
    Given x∈ℂ such that  F(x,Y) and G(x,Y) are non identically zero,
      
    ((F(x,Y),G(x,Y)))
      ≤(x,_Y(F,G)).
 
  

  
The claim follows clearly from the two following 
statements.
  
  
 a) Let f,g be two univariate polynomials of respective degrees 
  p,q.
Let ϕ be the mapping from K_< q [X] × K_< p [X] to K_<
  p+q [X] sending (U, V) to Uf + Vg. Then (ϕ) is the set of multiples of the greatest common divisor h=gcd(f,g) of f and g, and the rank of ϕ is  p+q-(h). It is clear that (m· g/h,-m· f/h) is in the kernel of ϕ for every polynomial m of degree <(h). In the other direction, every (U,V) in the kernel of ϕ is such that there exists m of degree <(h) with U=m· g/h and V=-m· f/h. This implies that the dimension of (ϕ) is equal to (h) and  the dimension of (ϕ) is thus equal to p+q-(h). But every element of (ϕ) is a multiple of h, and the vector space of multiples of h of degree <p+q is also of dimension p+q-(h). It follows that  (ϕ)  coincides with the set of multiple of h, and the rank of ϕ is  p+q-(h).
  
  
b) Let M(X) be an n× n matrix with coefficients in K[X]. If the rank of M(x_0) is equal to n-k, then x_0 is a root of (M(X)) of multiplicity at least k. The proof   is by induction on k.
     
     If k=0 the statement is true.
     
     If k>0, then M(x_0) is not invertible, and
     (M(x_0))=0.
  Denote by   m_i,j(X) the (i,j)-th entry of M(X),  and by M_i,j(X) the (n-1)× (n-1)-matrix obtained by removing thee i-th row and j-th column from M(X).
     The rank of M_i,j(x_0) is
     r(x_0) ≤ n-k, hence by induction hypothesis x_0 is a root of (M_i,j(X)) of multiplicity at least equal to (n-1)-r(x_0) ≥ k-1.
According to Jacobi's formula, we have 
     
    d/dX(M(X))=∑_i,j (-1)^i+j m'_i,j(X) (M_i,j(X)),

and thus the claim follows by induction since x_0 is a root of (M(X)) and a root of
     multiplicity at least k-1 of its derivative.
  
  

  


 Use Lemma  <ref> with F=F_n(x), G=∂_YF_n(x)(X,Y) noting that 
   
    ∑_y | (x,y)
          ∈_X(V_ℂ (F))  ((y, F_n(x)(x,Y))-1)
     =((F_n(x)(x,Y),∂_Y F_n(x)(x,Y))).

  
  
      
      Let F∈[X,Y]
      be a non-zero
       square-free polynomial of magnitude
bounded by
(n,τ) such that V_ℂ(F) has no vertical line.
    There exists a polynomial R_Y∈[Y] of magnitude
bounded by
 (O(n^2),O(nτ+n^2)) such that
   given y∈ℂ
  
    ∑_x | (x,y)
    ∈_X (V_ℂ (F))  ((y
    , F_n(x)(x,Y))-1)≤(y,
    R_Y).

In particular, the zeroes of R_Y contain the projection of _X(V_ℂ (F)) on the Y-axis.
  
  

a)  We suppose first that there is only one x such that (x,y)∈ (V_ℂ (F)), (y
, F_n(x)(x,Y))> 1 and denote μ=(y
, F_n(x)(x,Y)).
Defining

    R_Y(Y):=_X(F,∂_YF)(Y),

there exist U(X,Y), V(X,Y) such that

    R_Y(Y)=U(X,Y)F(X,Y)+V(X,Y)∂_YF(X,Y).

Derivating (<ref>) 1,…,μ-2 times with respect to Y and using that

    F(x,y)=∂_YF(x,y)=…=∂_Y^(μ-1)F(x,y)=0

we obtain

    R_Y(y)= ∂_Y R_Y(y)=…= ∂_Y^(μ-2)R_Y(y)=0.


b) We reduce the general case to the preceding situation by the change of variable
Y← Y+ X where  is a new variable. We use for the proof the field ℝ⟨⟩ of algebraic Puiseux series <cit.>, which is a real closed field containing ℝ(), totally ordered with the order 0_+ making  positive and smaller than any positive element of ℝ. We denote
ℂ⟨⟩ ^2=ℝ⟨⟩ ^2[i].

Notice that each X-critical point
(x,y) of F in ℂ^2 yields a X-critical point (x,y- x) of F̃(X,Y):=F(X,Y+ X) in ℂ⟨⟩ ^2 , and 
that 
the multiplicity of   y- x as a root of F̃(x,Y) 
coincides with the
the multiplicity μ(x,y) of  y as a root of F(x,Y) 
as
∂_Y^(i)F̃(x,y)=∂_Y^(i)F(x,y- x). Moreover there are no two distinct critical points of F̃(x,y) sharing
the same y-coordinate. Hence, it holds by a) that 
y- x is a root of _X(F̃,∂_Y F̃)(Y) of multiplicity at least 
μ(x,y).
Then

    _X(F̃,∂_Y F̃)(Y)=A()R̃(Y,)

with A()∈ℂ(),
 R̃(Y,) monic in Y, 

    R̃(Y,)=∏_(x,y)∈ (V_ℂ (F))(Y-y+ x)^μ(x,y)B(Y,),

with 
  
    (y- x
    , F̃_n(x)(x,Y))-1≤μ(x,y),

  and 
  B(Y,)∈ℂ[X,] such that   B(Y,0)∈[X] is a non-zero polynomial.
  Hence, denoting by 
    ν(y)=∑_x | (x,y)∈ (V_ℂ (F))μ(x,y),

  
    R_Y:=R̃(Y,0)=∏_
     y∈π_Y( (V_ℂ (F))) 
     (Y-y)^ν(y)B(Y,0),

  we have 
    
    ∑_x | (x,y)∈ (V_ℂ (F))  ((y
    , F_n(x)(x,Y))-1)≤ν(y)≤(y,
    R_Y).
 
  Finally, notice that R_Y is of magnitude
bounded by
 (O(n^2),O(nτ+n^2)).



When _X(F)≥_Y(F), it turns out that 
    R_Y(Y)=_X(F,∂_YF)(Y)
 because the Sylvester-matrix of F,∂_YF and F̃,∂_Y F̃ have the same dimension, since _X(F)=_X(F̃).
However, when _X(F)<_Y(F), it 
can
happen that R_Y(Y)≠_X(F,∂_YF)(Y).

This is the case for example if

    F(X,Y)=(X-Y^2+1)(X-Y^2-1)(XY^2-1)
 since we have 
    R_Y(Y)=2048(Y^4 + Y^2 - 1)^2(Y^4 - Y^2 - 1)^2Y^2,
  

    _X(F,∂_YF)(Y)=-32 (Y^4 + Y^2 - 1)^2(Y^4 - Y^2 - 1)^2Y^3.

.


We now give details on how to determine  the degree of F(x,Y) and its number of distinct complex roots
for a root x of R. Our aim is to prove the following proposition:



Let R(X)∈[X]
a non-zero polynomial of magnitude
bounded by
 (N,Λ) and F(X,Y)∈[X,Y]
be of magnitude
bounded by
 (n,τ), and suppose that  

    V_ℂ(R,F)={(x,y)∈ℂ^2| R(x)=F(x,y)=0}

is finite.
  Computing 
    n(x):=(F(x,Y)),k(x):=
      ( (F (x, Y), ∂_Y (F(x, Y))
 for every root x ∈ℂ of R   
  has bit complexity
   
    (nmax(N,n^2)(Nτ+nΛ+N n)+n^5 τ + n^6).



Note that n(x)-k(x) is the number of distinct complex roots of F(x,Y).


We 
start by estimating
 the cost of computing the polynomials R^⋆_ℓ 
defined in Equation (<ref>) and Equation (<ref>).

  
  The computation of all the polynomials 
    ( R^⋆_ℓ (X))_ℓ∈[1,n_y]
 uses 
Õ(max(n,N)( Nτ+n Λ+Nn)+n^3τ+n^4) bit operations.
  
   
Since R^⋆ is of degree at most N and bitsize bounded by Λ+N, and f_n_y(X) is of degree
at most n and bitsize  O(τ), the computation of their gcd needs Õ(max(n,N)(Nτ+nΛ+Nn)) bit operations according to Proposition <ref>.
Since, for all ℓ∈ [0,n_y-1], ( R^⋆_≤ℓ)≤ n and the bitsize of the coefficients of the R^⋆_≤ℓ is at most n+τ,
the complexity of computing all ( R^⋆_≤ℓ)_ℓ∈[0,n_y-1] is in O(n^3τ+n^4).

It remains to compute the  R^⋆_ℓ themselves by performing the exact division of R^⋆_≤ℓ by R^⋆_≤ℓ-1. This takes O(NΛ+N^2) binary operations for ℓ=n_y and 
O(nτ+n^2) binary operations for each ℓ<n_y.


The proof of Proposition <ref> uses a family of polynomials Δ^⋆_ℓ,k
defined as follows.
We further denote 
_ℓ,k (X) the  k-th subdiscriminant of F_ℓ considered as a polynomial in Y.
 We also define the content-free elements of [X] by:
 
    Δ^⋆_ℓ,≥ 0 (X) :=  R^⋆_ℓ ,

 and  for all
 k ∈{ 0, …, ℓ - 1 }, 
  
    Δ^⋆_ℓ,≥ k+1 (X) :=  ( Δ^⋆_ℓ,≥ k
     (X), _ℓ,k (X)),  Δ^⋆_ℓ,k (X) := Δ^⋆_ℓ,≥ k (X)/Δ^⋆_ℓ,≥ k+1
     (X).


Given ℓ∈[1,n_y] and x ∈ℂ such that _Y(F (x, Y)) = ℓ (i.e. R^⋆_ℓ(x)=0), it is clear that, using Notation <ref>,
  
 
    _Y( (F_ℓ (x, Y), ∂_Y F_ℓ (x, Y))) ≥  k
     ⟺Δ^⋆_ℓ,≥ k (x) = 0.

 
    _Y( (F_ℓ(x, Y), ∂_Y F_ℓ (x, Y))) = k
     ⟺Δ^⋆_ℓ,k (x) = 0.
 





 
  The computation of all the polynomials 
    (_ℓ,k (X))_ℓ∈[1,n_y],k ∈ [0, ℓ - 1
      ]
 uses (n^5 τ) bit operations. 
  
  
   The claim follows clearly from
 <cit.>,<cit.> 
  since there are n_y≤ n lists of sudiscriminants (i.e. subresultant coefficients) to compute.



   
The computation of all the polynomials (Δ^⋆_ℓ,k (X))_ℓ∈[1,n_y],k ∈ [0, ℓ - 1] uses a number of bit operations bounded by 
      
    (nmax(N,n^2)(Nτ+nΛ+N n)+n^5 τ + n^6).

  

  
    
   We compute first  all the polynomials 
    (_ℓ,k (X))_ℓ∈[1,n_y],k ∈ [0, ℓ - 1
      ]
 using Lemma <ref>.
   
   Let δ_ℓ,k be the degree of Δ^⋆_ℓ,≥ k, and let τ_ℓ,k be the maximal bitsize of the coefficients of Δ^⋆_ℓ,≥ k.
   
   The roots of Δ^⋆_n_y,0  are exactly the roots x of R with
   
    _Y(F(x,Y))=n_y and _Y( (F(x, Y), ∂_Y F (x, Y))) = 0.

  The computation of Δ^⋆_n_y,0 needs (max(N,n^2)(Nnτ+n^2Λ+N n^2)) bit operations according to Proposition <ref> and  Proposition <ref>.
   
  From Proposition <ref>, we conclude that each root of Δ^⋆_n_y,≥ k for k>0 is also a root of _Y(F) of multiplicity at
  least k. Since Δ^⋆_n_y,≥ k divides R^⋆, it is square-free and (Δ^⋆_n_y,≥ k)^k divides _Y(F), and thus
  
    δ_n_y,k⩽n (2 n - 1)/k,  and ∑_k = 1^n_yδ_n_y,k∈ (n^2) .

  Moreover,
(<ref>) yields that τ_n_y,k⩽ (Δ^⋆_n_y,≥ k) + δ_n_y,k. Since 
   Δ^⋆_n_y,≥ k
   divides
  _Y(F) and since the Mahler measure is multiplicative (see <ref>), we have 
    ∑_k = 1^n_y (Δ^⋆_n_y,≥ k) ⩽ (_Y(F)) ∈ (n
      τ),
 and thus 
  
    ∑_k = 1^n_yτ_n_y, k∈ ( n τ+n^2).

  
   On the other hand, for ℓ∈[1,n_y-1],  Δ^⋆_ℓ,≥ k is a divisor of R^⋆_ℓ, so that
   
    ∑_k = 0^ℓδ_ℓ,k≤ (ℓ+1) ·(R^⋆_ℓ),∑_ℓ=1^n_y-1(R^⋆_ℓ)≤ n_y≤ n,
 
 and
    
    ∑_ℓ=1^n_y-1∑_k = 0^ℓδ_ℓ,k∈ (n^2).

  As above, we use 
  (<ref>) to show that
  τ_ℓ,k⩽ (Δ^⋆_ℓ,≥ k) + δ_ℓ,k. Since Δ^⋆_ℓ,≥ k is a divisor of R^⋆_ℓ, which is a divisor of
  f_ℓ, and 
    ∑_k =0^ℓ (Δ^⋆_ℓ,≥ k) ⩽ (f_ℓ) ∈ (τ),
 we conclude that
  
    ∑_ℓ=1^n_y-1∑_k = 0^ℓτ_ℓ,k∈ (n^2 + n τ).

  
    Finally

    ∑_k = 1^n_yδ_n_y,k+∑_ℓ=1^n_y-1∑_k = 0^ℓδ_ℓ,k∈ (n^2)

  
    ∑_k = 1^n_y-1τ_n_y,k+∑_ℓ=1^n_y-1∑_k= 0^ℓτ_ℓ,k∈ ( n τ+n^2) .

  
  The computation of Δ^⋆_ℓ,≥ k+1 (X)= (Δ^⋆_ℓ,≥ k (X), _ℓ, k (X)) for (ℓ,k)≠(n_y,0) uses
  
    (max (δ_ℓ,k,n^2)(n^2 τ_ℓ,k +δ_ℓ,k n τ))∈ (n^2(n^2 τ_ℓ,k +δ_ℓ,k n τ))
 bit operations
according to Proposition <ref>.
  Finally, the computation of all
  the Δ^⋆_ℓ,≥ k needs 
  
    (max(N,n^2)(Nnτ+n^2Λ+N n^2)+n^5 τ + n^6)
 bit operations using (<ref>) and (<ref>).
  
  It remains to compute  the  Δ^⋆_ℓ,k themselves by performing the exact division of Δ^⋆_ℓ,≥ k by Δ^⋆_ℓ,≥ k+1. This takes O(NΛ+N^2) binary operations for (ℓ,k)=(n_y,0),
O(n^2τ+n^3) binary operations for each (n_y,k), with k ≠0,
and O(nτ+n^2) binary operations for each (ℓ,k), with ℓ <n_y.
 
 
  
 
 
In order to determine n(x) for every x∈ V_ℂ(f), we use
Equation (<ref>),
Lemma <ref> and Proposition  <ref>.

Similarly in order to determine k(x) for every x∈ V_ℂ(f), we use 
Equation (<ref>), Lemma <ref> and   Proposition  <ref>.




 §.§ Bivariate root isolation

 
We now bound the complexity of computing the roots of all polynomials F(x,Y), where x runs over all roots of R, using
Proposition  <ref>.



Let 
R∈[X] be
a non-zero polynomial
 of magnitude 
bounded by
(N,Λ), let F∈[X,Y] be of magnitude 
bounded by
(n,τ), and suppose that  

    V_ℂ(R,F)={(x,y)∈ℂ^2| R(x)=F(x,y)=0}

is finite. 
Then, it holds:


  (a) Using 
    (N^2Λ+N^3+n·max(n^2,N)·(Nτ+nΛ+Nn)+n^5 τ +n^6)

bit operations, we can compute 


  (a.1) well-isolating disks 𝒟_x,y⊂ for all complex roots y of all polynomials F(x,Y), where the sum of the bitsizes of the radii and centers of all disks 𝒟_x,y is bounded by (n(Nτ+nΛ+Nn)),

  (a.2) the corresponding multiplicities 
μ(x,y)
 for each of the complex roots y of all polynomials F(x,Y), and

  (a.3) dyadic approximation σ̃_x,y of the separations (y,F(x,Y)) such that 
    1/2·(y,F(x,Y))<σ̃_x,y<2·(y,F(x,Y))
 for all roots x (resp. y) of R (resp. F(x,Y)).


  (b) Let V⊂{(x,y)∈ℂ^2:R(x)=0 and F(x,y)=0}, and L be a positive integer. Then, we can further refine all isolating disks 𝒟_x,y, with (x,y)∈ V, to a size less than 2^-L, in a number of bit operations bounded by 

    (N^2Λ+N^3+n·max(n^2,N)·(Nτ+nΛ+Nn)+L·(N·μ+n^2·∑_x ∈π_X(V)μ_x)),

where μ_x:=max_(x,y) ∈ Vμ(x,y), and μ=max_x ∈π_X(V)μ_x.

 


First compute  
    n(x):= F(x,Y),k(x):=(F(x,Y),∂_Y F(x,Y))
  
for all roots x of R.
According to Proposition <ref>, this computation needs  
    (nmax(N,n^2)(Nτ+nΛ+N n)+n^5 τ + n^6)
 bit operations. Further notice that F(x,Y) has m(x)=n(x)-k(x) distinct complex roots.

Let x be a fixed complex root of R, τ_x∈ such that 2^-τ_x<(F(x,Y))≤ 2^-τ_x+2, and F_x:=2^τ_x· F(x,Y). Notice that F_x has the same roots as F(x,Y), and the leading coefficient of F_x has absolute value in between 1 and 4. Then according to Proposition <ref>, we can compute well-isolating disks 𝒟_x,y for the roots of F_x (and thus also for the roots of F(x,Y)) as well as the multiplicities 
μ(x,y)
 in a number of bit operations that is bounded by 

    (n(n^2+n·(F_x)
    +(F_x))).

using Proposition <ref>;
For this, we need an approximation of F_x to an absolute precision that is bounded by

    ρ_x
    ∈(n(F_x)+(F_x)).

Using Proposition <ref>, Proposition <ref> now yields 
the bound 

    ∑_x ∈ V_ℂ(R)ρ_x∈(n· (Nτ+nΛ+Nn))

for the sum of the bound (<ref>) for the needed input precision over all x∈ V_ℂ(R).



It remains to show that we can compute sufficiently good approximations of the polynomials F_x in a number of bit operations that is bounded by (n^2·(Nτ+nΛ+Nn)). In order to compute a ρ_x-bit approximation of F _x, we first compute a τ_x with 2^-τ_x-2<(F(x,Y))≤ 2^-τ_x as well as a (ρ_x+τ_x)-bit approximation of F(x,Y) and then shift the coefficients of the latter approximation of F(x,Y) by τ_x bits. We first estimate the cost for the computation of the τ_x's. According to Proposition <ref>, we can compute an approximation c̃_x of c_x:=|(F(x,Y))| with |c_x-c̃_x|<2^-L using (n(L+nlog(max(1,|x|)))+τ) bit operations, and as input we need an (L+nlogmax(1,|x|)+τ)-bit approximation  of x. 
Hence, when choosing L=2,4,8,…, we succeed in computing τ_x for an L_x of size 
    L_x∈ O(|log (|(F(x,Y))|)|+τ+n+nlog(max(1,|x|))),
 and the cost for the evaluation is bounded by 
(nL_x)
bit operations. When summing up the latter bound over all x and using 
Proposition <ref> (b) (with g_i=f_n_y-i, the sequence of coefficients of F∈[X][Y]), we obtain

    ∑_x ∈ V_ℂ(R)(nL_x)   ∈ n·(∑_x ∈ V_ℂ(R) (|log( |(F(x,Y))|)|+τ+n+nlog(max(1,|x|))))
       ∈(n^2(Nτ+nΛ+Nn))

Notice that the above computation further implies that ∑_x∈ V_ℂ(R)τ_x∈(n(Nτ+nΛ+Nn)).

For estimating the cost of computing sufficiently good approximations of F(x,Y), we can again use Proposition <ref>. We conclude that the cost for computing a (ρ_x+τ_x)-bit approximation of F(x,Y) is bounded by (n^2(τ+n+nlog(max(1,|x|))+ρ_x+τ_x)) bit operations and that we need a (τ+n+nlog(max(1,|x|))+ρ_x+τ_x)-bit approximation of x. Summing up the cost over all x then yields

    (n^2N(τ+n)+n^3∑_x ∈ V_ℂ(R)log(max(1,|x|))+n^2∑_x ∈ V_ℂ(R) (ρ_x+τ_x))

which is in

    (n^3·(Nτ+nΛ+Nn)).

Finally, we have to bound the cost for computing sufficiently good approximations of the roots x of R. Notice that each term τ+n+nlog(max(1,|x|))+ρ_x+τ_x is bounded by (n·(Nτ+nΛ+Nn)) for each root x of R; in fact, the latter bound even applies to the sum of all these terms. Hence, it suffices to compute approximations of all roots of R to an absolute precision of size (n· (Nτ+nΛ+Nn)). According to Proposition <ref>, the cost for the computation of well-isolating disks of corresponding size is bounded by (N^2Λ+N^3+Nn(Nτ+nΛ+Nn)). The bound on the sum of the bitsizes of the radii and the centers of the disks 𝒟_x,y follows directly from Proposition <ref> and Proposition <ref>.
This concludes the proof of Parts a) and b).
For Part (c), notice that 
    min_y'≠ y:F(x,y')=0|m_x,y-m_x,y'|/(y,F(x,Y))∈ (1-1/32,1+1/32),
 where m_x,y denotes the center of 𝒟_x,y. Hence, approximations σ̃_x,y with the required properties can directly be obtained from the distances between the centers m_x,y. Since the sum of the bitsizes of all centers m_x,y is bounded by 
(∑_x ∈ V_ℂ(R)(F_x)+(F_x^⋆))∈(n(Nτ+n+Nn)), the claim follows.

It remains to prove the last claim on the cost for refining the disks 𝒟_x,y, with (x,y)∈ V, to a size less than 2^-L. For this, we use Proposition <ref> (c), which shows that, for a fixed x, we can refine all disks 𝒟_x,y using 

    (n(L·μ_x+n^2·(F_x)+n(F_x)+n^3))

bit operations. Now, summing the latter bound over all x yields 
    (n^2(Nτ+nΛ+Nn)+nL·∑_x ∈ V_ℂ(R)μ_x).
 For the input precision ρ_x to which we need to approximate the polynomial F_x, we obtain the bound  

    ρ_x
    ∈(L·μ+n·(F_x)+(F_x)+n^2).

 Again, using the same argument as above, it follows that sufficiently good approximations of the polynomials F_x can be computed using 
 
    (n^3·(Nτ+nΛ+Nn)+L(Nμ+ n^2·∑_x ∈ V_ℂ(R)μ_x))

 bit operations.


Theorem <ref> follows from  
 Proposition <ref>.




Let 
R∈[X]
a non-zero polynomial
 of magnitude 
bounded by
(N,Λ), F,G∈[X,Y] be of magnitude
bounded by
 (n,τ), and H:=F· G. Suppose moreover that

    V_ℂ(R,H)={(x,y)∈ℂ^2| R(x)=H(x,y)=0}

is finite.
Using a number of bit operations bounded by 

    (N^2Λ+N^3+n^5τ+n^6+n·max(n^2,N)· (Nτ+nΛ+Nn))
 
we can can carry out the following computations for all complex roots x of R:


  (a) computing well-isolating disks 𝒟_x,y for all complex roots y of the polynomial H(x,Y) together with the corresponding multiplicities ν(x,y)=(y,H(x,Y)).

  (b) determining for each root y of H(x,Y) whether y is a root of F(x,Y), G(x,Y), or both. If x as well as y are real, we can further determine the sign of F(x,y) and G(x,y).

 


Part (a) already follows from Lemma <ref> and Proposition <ref> as H has magnitude
bounded by
 (O(n),O(log (n)+τ)). We 
may further assume that, for all complex roots x of R, we have already computed


  * well-isolating disks 𝒟^F_x,y' 
and 𝒟^G_x,y” for all complex roots y' and y” of the polynomials F(x,Y) and G(x,Y), respectively, 

  * the corresponding multiplicities (y',F(x,Y)) and (y”,G(x,Y)),

  * the degrees of the polynomials F(x,Y) and G(x,Y), and

  * the signs of the leading coefficients of the polynomials F(x,Y) and G(x,Y) in case that x is a real root of R.


For (b), we now refine each disk 𝒟^F_x,y' such that it intersects with exactly one of the disks 𝒟_x,y. If this is the case, then it holds that y=y'. In addition, y is also a root of G(x,Y) if and only if ν(x,y)>(y',F(x,Y)) as (y,F(x,Y))+(y,G(x,Y))=ν(x,y). Hence, for each root y of H(x,Y), we also know its multiplicity as a root of F(x,Y) and G(x,Y). When restricting to the real roots of R, this implies that we can directly deduce the sign of F(x,y) (resp. G(x,y)) at each real root y of H(x,Y) that is not a root of F(x,Y) (resp. G(x,Y)). Namely, from the sign of the leading coefficient of F(x,Y) (resp. G(x,Y)) and its degree, we know its sign at ±∞, and the polynomial changes signs exactly at those roots of H that are roots of F(x,Y) (resp. G(x,Y)) of odd multiplicity.  

It remains to bound the cost for the refinement of the disks 𝒟^F_x,y'. We proceed in rounds enumerated by ℓ=1,2,3,…: Initially, we set Z^1:=V_ℂ(R,F). In the ℓ-th round, we refine each of the isolating disks 𝒟^F_x,y' for all (x,y')∈ Z^ℓ to a size less than 2^-2^ℓ and check whether it intersects exactly one of the isolating disks 𝒟_x,y for the roots of H(x,Y). If this is the case, we know that y=y'. 

 After having treated all points in Z^ℓ, we set Z^ℓ+1 to be the set of all (x,y') in Z^ℓ_x for which the isolating disk 𝒟^F_x,y' intersects more than one of isolating disks for H(x,Y). That is, Z^ℓ is the set of all (x,y')∈ Z^1 for which we have not determined a corresponding root y of H(x,Y) with y=y' after the ℓ-th round. We then proceed with the (ℓ+1)-st round. We stop as soon as  Z^ℓ becomes empty, in which case, each root of each F(x,Y)=0 is matched to a corresponding root of H(x,Y).
Notice that, for each (x,y'), we must succeed in round ℓ_x,y', for some ℓ_x,y' with

    2^ℓ_x,y'≤ O(|log((y',H(x,Y)))|).
 From the amortized bounds on the separation of the roots  (Proposition <ref>), we have that |log((y',H(x,Y)))|∈(n(Nτ+nΛ+Nn)), thus
we are done after ℓ_max rounds for  

    ℓ_max=max_x,y'ℓ_x,y"+1∈ O(log (n(Nτ+nΛ+Nn))).

According to Proposition <ref>, the cost for refining the disks 𝒟^F_x,y' for all (x,y')∈ Z^ℓ to a size less than 2^-2^ℓ is bounded by 

    ∑_ℓ=1^ℓ_max(N^2Λ+N^3+nmax(n^2,N)(Nτ+nΛ+Nn)+2^ℓ(Nμ^[ℓ]+n^2∑_x∈:R(x)=0μ_x^[ℓ]))

bit operations,
where 

    μ_x^[ℓ]:=
    max_(x,y')∈ Z^ℓ(y',F(x,Y))   if  there exists (x,y')∈ Z^ℓ
    
    0    otherwise.

 and μ^[ℓ]:=max_x:R(x)=0μ^[ℓ]_x.
 Since ℓ_max is bounded by O(log (n(Nτ+nΛ+Nn))), we are left to bound the sum
 
    ∑_ℓ=1^ℓ_max 2^ℓ· (N·μ^[ℓ]+ n^2·∑_x∈:R(x)=0μ_x^[ℓ]).

If, for a fixed root x of R, there exists  a (x,y')∈ Z^ℓ, then let (x,y'_ℓ,x)∈ Z^ℓ be a point in Z^ℓ with (y'_ℓ,F(x_ℓ,Y))=μ^[ℓ]. In other words, y'_ℓ,x  maximizes the multiplicity within the fiber for all roots y' of F(x,Y) with (x,y')∈ Z^ℓ. In addition, let (x_ℓ, y'_ℓ) be a point in Z^ℓ that maximizes the multiplicity over all fibers. Thus, the sum in (<ref>) can be rewritten as

    N·∑_ℓ=1^ℓ_max(y'_ℓ,F(x_ℓ,Y))· 2^ℓ+n^2·∑_ℓ=1^ℓ_max∑_x∈:R(x)=0(y'_ℓ,x,F(x,Y))· 2^ℓ.

Notice that a pair (x,y')∈ Z^ℓ_x can appear at most ℓ_max many times in each of the above sums. In addition, it holds that (x,y')∉ Z^ℓ if ℓ>ℓ_x,y' for some 2^ℓ_x,y'∈ O(|log((y',H(x,Y)))|). Hence, the above sum is upper bounded by

    O(ℓ_max· (n^2+N)·∑_(x,y')∈ Z^1(y',F(x,Y))· |log((y',H(x,Y)))|)

Since (y',F(x,Y))≤(y',H(x,Y)) and ℓ_max∈ O(log (n(Nτ+nΛ+Nn))), we thus conclude from Proposition <ref> that (<ref>) is upper bounded by

    (n·(n^2+N)· (Nτ+nΛ+Nn)).

Finally, the cost of checking whether an isolating disk 𝒟^F_x,y' intersects exactly one of the isolating disks 𝒟_x,y for the roots of H(x,Y) is bounded by 
O(n·((H(x,Y)^⋆)+(H(x,Y))) as there are n comparisons between disks with radii and centers of bitsize 
O((H(x,Y)^⋆)+(H(x,Y)). The total cost for all comparisons is thus bounded by 

    O(κ· n^2·∑_x:R(x)=0 [(H(x,Y)^⋆)+(H(x,Y))]=Õ(n^3(Nτ+nΓ+Nn)),

where the latter inequality follows from Proposition <ref> and Proposition <ref>.
Hence, our claim follows.



We remark that the above considerations immediately yield a
new
 algorithm for solving a bivariate polynomial system that achieves the current record complexity bound for this problem.


Let F,G∈[X,Y] be coprime polynomials of magnitude 
bounded by
(n,τ). Then, we can compute  isolating regions for all complex solutions of the system F=G=0 using (n^5τ+n^6) bit operations.


Let R=_X(F,G) be the resultant polynomial of F and G, which can be computed using (n^4τ+n^5) bit operations. Any common solution (x_0,y_0)∈ℂ of F=G=0 yields a root x_0 of R, and then y_0 is a common root of F(x_0,Y) and G(x_0,Y). Vice versa, any common root y_0 of F(x_0,Y) and G(x_0,Y) yields a solution of F=G=0. According to Proposition <ref>, we can compute all common roots of F(x,Y) and G(x,Y) for all complex roots x of R using (n^5τ+n^6) bit operations. Hence, the claim follows. 





In the proof of Proposition <ref>, we needed to recursively refine the isolating disks for the roots of F(x,Y) until a certain test applies. That is, we needed to check whether a disk intersects exactly one of the isolating  disks of H(x,Y). While this test itself is rather simple (and cheap), its success is directly related to a hidden parameter, which is in this case the separation of some specific (but unknown) root of the polynomial H(x,Y). 

In the worst case, the cost for refining isolating disks for the polynomial F(x,Y) until the test applies is rather large (i.e. it is comparable to our bound for the overall computation), and thus it would be very costly to refine all isolating disks to such a small size. Fortunately, this is not necessary as, for most roots of F(x,Y), the success of the test is related to a root of H(x,Y) with larger separation. In order to exploit this fact, we need to design adaptive algorithms in each of these cases and to use our amortized bounds on the separation of the roots (Proposition <ref> and Proposition <ref>).

Three instances of such a situation appear in this paper, the first in Proposition <ref> and the two others in the proof of Theorem <ref> parts c.1 and c.2.




§ COMPUTATION OF THE TOPOLOGY



 §.§ Preliminary definitions and results






Let P ∈ [X, Y] be a square-free polynomial of magnitude
bounded by
 (d,τ). In addition, let

    V_ℝ (P) = {(x, y) ∈ℝ^2 | P (x, y) = 0}
 be the real
algebraic curve defined by P, and 

    V_ℂ(P) = {(x, y) ∈ℂ^2 | P (x, y) = 0}

be the corresponding complex algebraic curve.


We first decompose

    P(X,Y)=p(X)· Q(X,Y)

 with p(X)∈ [X] and  Q(X,Y)∈ [X, Y] such that Q(x,Y)
never identically vanishes for  any x ∈ℂ. In more geometric terms, we separate the vertical lines contained in V_ℂ (P) from the remaining part V_ℂ (Q) of the curve, which does not contain any vertical lines. 



We can compute p(X) and Q(X,Y) using (d^4+d^3τ) bit operations. 
The polynomial p(X) and Q(X,Y)
 have magnitude bounded by (d,τ+d+log (d+1)).



Let  P(X,Y):=p__Y(P)(X)Y^_Y(P)+…+p_0(X), with _Y(P)≤ d. Let p(X) the gcd of all the coefficients p_i(X). We first compute p(X) then write P(X,Y)= p(X)Q(X,Y).
The claimed bounds on the cost for computing p(X) and Q(X,Y) 
 as well as on the magnitude of these polynomials follow immediately from Propositions <ref> and <ref>.




From now on, we study the zero set of Q(X,Y),  which contains no vertical lines.
We suppose moreover that _X(Q(X,Y))>0 because otherwise V_ℝ (Q) is a finite number of horizontal lines and its topology, very easy to describe, is treated as a special case in the first part of sub-section <ref>.
We also describe in sub-section <ref> how to add back vertical lines contained in  V_ℝ (P) to obtain the topology of V_ℝ (P) from the topology of V_ℝ (Q).

A point (α, β) ∈ V_ℝ (Q) 
 is called:

 
  * an X-critical point if ∂_Y  Q(α, β) = 0,
 
  * a Y-critical point if ∂_X Q (α, β) = 0,
 
  * a singular point if ∂_X Q (α, β) = ∂_Y Q(α, β) = 0,
 
  * a regular point if ∂_Y Q (α, β)≠ 0 and
 ∂_X Q (α, β) ≠ 0.
 
 Notice that a singular point of V_ℝ (Q) is also an X-critical and a Y-critical point.


We define
 
    D_X(X)    := 
        _Y(Q,∂ Y Q)=q_d'(X)_Y (Q) (X)
     ,

 where q_d'(X) is the leading coefficient of Q with respect to Y. 
 
  In geometric terms, the zeroes of D_X are the projections on the X-axis of the 
 X-critical points
 or the values α such that (Q(α,Y))<_Y(Q)=d'.
 
  The special case where D_X(X) has no real root is considered separately in the first part of sub-section <ref>.
 
 

Let
 
    α_1<…<α_N

be  the real roots of D_X(X).

  
 
  For every i=1,…,N, we denote by  m_i the number of roots of Q(α_i,Y) and by 
  β_i,1,…,β_i,m_i, with

    β_i,1<…<β_i,m_i,

 the real roots of Q(α_i,Y).
 
 We denote by
  m'_0 (resp.  m'_i,i=1,…,N ) the number of roots of 
 Q(x,Y) when x∈(-∞,α_1) (resp x∈(α_i,α_i+1), x∈(x_N,+∞)).
 It is clear that the numbers  m'_i,i=1,…,N-1 coincide with the number of roots of Q(α'_i,Y) where α'_i is the smallest root of D'_X bigger than α_i.

 In order to evaluate m'_0 and m'_N, we use the following classical Cauchy bound.
 Let f(X)=a_nX^n+⋯ + a_qX^q, be a univariate polynomial of degree n  with coefficients in ℂ, such that a_q ≠ 0, a_q-1=…,a_0=0.
Denoting

    (f):=∑_q ≤ i≤ n| a_i/a_n|,

the absolute value of any 
root of f in ℂ is 
smaller than (f) (cf. for example <cit.>). The numbers  m'_0 and  m'_N coincide with the number of roots of Q((D_X),Y) and Q(-(D_X),Y).

   For each fixed i, we define the set of indices of X-critical points above i as

    CritInd_i:={j∈{1,…,m_i}:(α_i,β_i,j)∈_X(V_ℝ(Q))}.

with
_X(V_ℝ(Q)) := {(x, y) ∈ℝ^2 | Q(x, y) =∂_Y Q(x,y)= 0} 
and
the set of indices of singular  points above i as

    SingInd_i:={j∈{1,…,m_i}:(α_i,β_i,j)∈(V_ℝ(Q))}.

with
(V_ℝ(Q)) := {(x, y) ∈ℝ^2 | Q(x, y) =∂_Y Q(x,y)=∂_X Q(x,y)= 0}. 


Our aim is to determine the number  Left_i,j of the 
curve segments
ending at 
(α_i,β_i,j) to the left of α_i as well as the number
 Right_i,j of the 
curve segments
 ending at 
(α_i,β_i,j) to the right of α_i.




These numbers   are easy to determine if j∉SingInd_i.
If (α_i,β_i,j) is regular, Left_i,j=Right_i,j=1.
If (α_i,β_i,j) is X-critical but not singular, denoting by μ_i,j  the multiplicity of β_i,j as a root of Q(α_i,Y) 


  * if μ_i,j  is odd, 
 
    Left_i,j=Right_i,j=1

 
  * if μ_i,j  is even and ∂_Y Q^[μ_i,j](α_i,β_i,j)>0,  

    Left_i,j=0,Right_i,j=2


  * if μ_i,j  is even and ∂_Y  Q^[μ_i,j](α_i,β_i,j)<0, 
 
    Left_i,j=2,Right_i,j=0




We now explain how to deal with the vertical asymptotes in the simple case.  We denote by d'=_Y(Q)≤ d and by q_0(X),…, q_d'(X) the coefficients of Q considered as a polynomials in Y. The vertical asymptotes occur at values of α where  (Q(α,Y))<_Y(Q), i.e. at zeroes of q_d'. Our aim is to count the number of asymptotes Left_i,0 and  Right_i,0 tending to -∞ just before α_i and  just after α_i (resp.  Left_i,m_i+1  and Right_i,m_i+1 tending to +∞ just before α_i and  just after α_i).
If (Q(α,Y))=d' there are no asymptotes and

    Left_i,0=Right_i,0=Left_i,m_i+1=Right_i,m_i+1=0.

The asymptote is simple when (Q(α,Y))=d'-1, i.e. when q_d'(α)=0,  q_d'-1(α)≠0, and we have


  * if q_d'-1(α)<0, 
 
    Left_i,0=1,Right_i,0=0,Left_i,m_i+1=0,Right_i,m_i+1=1;


  * if q_d'-1(α)>0
 
    Left_i,0=0,Right_i,0=1,Left_i,m_i+1=1,Right_i,m_i+1=0.



Using the notation above, we can prove the following Theorem.

 Using (d^5 τ + d^6) bit operations, we can compute:
 
 
  * the number N,
 
  * for each i=1,…, N, the numbers m_i,
 
  * for each i=0,…, N, the numbers m'_i,
 
  * for each i=1,…, N, the set CritInd_i,
   
  * for each i=1,…, N, the set SingInd_i,
 
  * for each j∈CritInd_i∖SingInd_i,  the  multiplicity μ_i,j of β_i,j as a root of Q(α_i,Y)
  and the sign (∂_Y^μ_i,j Q(α_i,β_i,j)),
  
  * for each i=1,…, N, the degree (Q(α_i,Y)), 
  
  * for each i=1,…, N such that (Q(α_i,Y))=d'-1, (q_d'-1(α_i)).
  


First note, using Lemma <ref>, that D_X is a polynomial of magnitude
bounded by
 (N,Λ)∈ (O(d^2),(dτ+d^2)).  Hence, by Proposition <ref> and Proposition <ref>, 
we can compute well-isolating intervals for the real roots of D_X in a number of bit operations bounded by (d^5τ+d^6).
 According to 
Proposition <ref> (with R:=D_X and F:=Q(X,Y)), we may further compute (Q(α_i,Y)) and the number of distinct roots of Q(α_i,Y) for all i from 1 to N  using (d^5τ+d^6) bit operations. From Proposition <ref>, we conclude that  using also (d^5τ+d^6) bit operations we can further compute 
well-isolating intervals for all real roots of the 
polynomials Q(α_i,Y) as well as the corresponding multiplicities μ_i,j of β_i,j for all i from 1 to N. Each root β_i,j of multiplicity larger than one then 
corresponds to an X-critical point (α_i,β_i,j), which defines CritInd_i for i=1,…,N.
In order to define SingInd_i for i=1,…,N we compute the sign of ∂_X Q(α_i,β_i,j) for all j∈CritInd_i using Proposition <ref>.
We compute for each j∈CritInd_i∖SingInd_i  the sign (∂_Y^μ_i,j Q(α_i,β_i,j)) using again Proposition <ref>.
We finally compute for each i=1,…, N such that (Q(α_i,Y))=d'-1, (q_d'-1(α_i)) using Proposition  <ref>.
 

As a consequence if it is the case that
  
   
  * for each i=1,…, N, the set  SingInd_i has 0 or 1 element
  
  * for each i=1,…, N, (Q(α_i,Y))=d'  or (Q(α_i,Y))=d'-1
  
  we have all the information needed to compute Left_i,j and Right_i,j for j∉SingInd_i as well as Left_i,0 and Right_i,m_i+1 
 using  Equations ( <ref>), (<ref>),(<ref>),  (<ref>),(<ref>).
 Finally, for each i=1,…, N, j∈SingInd_i


  * Left_i,j=m'_i-1-∑_k=0,…,m_i+1,k≠jLeft_i,k,

  * Right_i,j=m'_i-∑_k=0,…,m_i+1,k≠jRight_i,k.



The more complicated remaining cases when there are several singular points above one α_i or several vertical asymptotes at α_i are discussed in the following sections.
  
  


 §.§ Adjacency boxes and number of left and right curve segments at a singular point


We now deal with the determination of the number  Left  of the  curve segments
ending at  (α,β) to the left of α as well as the number Right of the 
curve segments ending at (α,β) to the right of α at a singular point (α,β)  of V_ℝ (Q).
 

A rectangle
(α,β):=[α^-,α^+]× [γ^-,γ^+]
is an adjacency box associated to a 
singular 
point (α,β)  of V_ℝ (Q)
if the following holds


  * α^-< α < α^+, γ^-< β < γ^+,

  * there is no X-critical point of V_ℝ (Q) inside ([α^-,α)∪ (α,α^+])×ℝ,

  * except points of the horizontal line Y=β when it is included  V_ℝ (Q), there is  no Y-critical point of V_ℝ (Q) inside ([α^-,α)∪ (α,α^+])×ℝ,

  * there is no Y-critical point or X-critical point  of V_ℝ (Q) inside ℝ×([γ^-,β)∪ (β,γ^+]).

It follows clearly from the definition that (α,β) is the only singular point of 
(α,β).





The aim of this subsection is to explain how counting the intersection points of V_ℝ (Q) with some specific parts of the boundary of (α,β), 
and taking into account some sign conditions on the slope of the curve, 
 makes it possible to compute the number  Left and
 Right.


We denote by 


  * (α,β):=
[α^-,α] × [γ^-,  γ^+]∖{(α,β)}  the left-half  of (α,β)

  * (α,β):=
[α,α^+] × [γ^-,  γ^+]∖{(α,β)}
 the right-half of (α,β).
 



 
 We denote by Slope(X,Y) the rational fraction
 
    Slope(X,Y)=-∂_X Q(X,Y)/∂_Y Q(X,Y).
 
 The slope of the
tangent to a level line of Q  at a regular point (x,y) is
given by 
 
    Slope(x,y)=-∂_X Q(x,y)/∂_Y Q(x,y).
 
 Note that at any point (x,y) of (α,β) ∖{(α,β)} intersected with V_ℝ (Q), Slope(x,y) is well defined and not 0, except if y=β and Y=β is a horizontal line contained in  V_ℝ (Q).

 
A boundary point (x, y) of (α,β) (resp.  (α,β)) in V_ℝ (Q)
is exactly of one of the following types

- type 0: there is no curve segment of V_ℝ (Q)
containing (x,y) inside (α,β)  (resp.  (α,β));  this is the case only at some corners, i.e. if
(x,y)=(α_-,γ_+) with Slope(α_-,γ_+)>0 or (x,y)=(α_-,γ_-)  with Slope(α_-,γ_-)<0 (resp. (x,y)=(α_+,γ_+)  with Slope(α_+,γ_+)<0 or (x,y)=(α_+,γ_-)) with Slope(α_+,γ_-)>0).

 - type 1: there is a 
 curve segment of V_ℝ (Q) containing (x,y) which
  ends at another boundary point denoted by (x,y) of (α,β)∩ V_ℝ (Q)  (resp.  (α,β)∩ V_ℝ (Q));

 - type 2: there is a 
 curve segment of V_ℝ (Q) containing (x,y) which
 ends at (x,y)=(α, β).


The following properties are clear from Definition <ref>.
The matching point (x,y)  has the same slope sign as (x,y) for
type 1. If (x,y)≠ (x',y'), (x,y)≠(x',y') except if
(x,y)=(x',y')=(α,β).
A curve segment 
associated to a point of type 1 
does not meet any other 
curve segment, 
and 
a curve segment of type 2
 meets only other 
 curve segments 
 of type 2, at
(α, β).


We denote by 

 
  * ^+(α,β):=
[α^-,α] × (β, γ^+]  the upper left-half  of (α,β)

  * ^+(α,β):=
[α,α^+] × (β,  γ^+]
the upper right-half  of (α,β),
 
  * ^-(α,β):=
[α^-,α] × [γ^-,β)  the lower left-half  of (α,β)

  * ^-(α,β):=
[α,α^+] × [γ^-,  β)
 the lower right-half of (α,β).
 

 We introduce some definitions to describe the intersection of 
 V_ℝ (Q) with the boundaries of (α,β), 
 (α,β), ^+(α,β), ^+(α,β), 
 ^-(α,β) and ^-(α,β).
 


 Denote by 
 
 
  * V_α^-=V_ℝ (Q)∩ ({α^-}× (γ^-,
 γ^+))  and V_α^+=V_ℝ (Q)∩ ({α^+}× (γ^-, γ^+)), ordered by increasing value of y,
 
  * V_α^-^=β=V_ℝ (Q)∩{(α^-,β)}, V_α^-^<β= V_ℝ (Q)∩ ( {α^-}× (γ^-,
 β)),  V_α^-^>β= V_ℝ (Q)∩ ({α^-}× (β,γ^+)), ordered by increasing value of y,
  
  * V_α^+^=β=V_ℝ (Q)∩{(α^+,β)}, V_α^+^<β=V_ℝ (Q)∩ ({α^+}× (γ^-,
 β)),  V_α^+^>β= V_ℝ (Q)∩ ({α^+}× (β,γ^+)), ordered by increasing value of y,

  * V_α^<β=V_ℝ (Q)∩ ({α}× (γ^-,
 β)), V_α^>β=V_ℝ (Q)∩ ({α}× (γ^-,
 β)), ordered by increasing value of y,
  
and 
 
 
  * H_γ^-^= α^-=V_ℝ (Q)∩{(α^-,γ^-)}, H_γ^-^ < α=V_ℝ (Q)∩ ((α^-,α) ×{γ^-}),   H_γ^-^= α=V_ℝ (Q)∩{(α,γ^-)}, H_γ^-^ >α=V_ℝ (Q)∩ ((α,α^+) ×{γ^-}), H_γ^-^= α^+=V_ℝ (Q)∩{(α^+,γ^-)},
 
  * H_γ^+^= α^-=V_ℝ (Q)∩{(α^-,γ^+)}, H_γ^+^ < α=V_ℝ (Q)∩ ((α^-,α) ×{γ^+}),   H_γ^+^= α=V_ℝ (Q)∩{(α,γ^+)}, H_γ^+^ >α=V_ℝ (Q)∩ ((α,α^+) ×{γ^+}), H_γ^+^= α^+=V_ℝ (Q)∩{(α^+,γ^+)}.
  


In summary:
 
 
  * the boundary points of ^+(α,β) in  V_ℝ (Q)
are V_α^-^>β∪ H_γ^+^=α^-∪ H_γ^+^<α∪ H_γ^+^=α∪ V_α^>β,

  * the boundary points of ^+(α,β) in  V_ℝ (Q)
are   V_α^+^>β∪ H_γ^+^=α^+∪ H_γ^+^>α∪ H_γ^+^=α∪ V_α^>β,
 
  * the boundary points of ^-(α,β) in  V_ℝ (Q)
are  V_α^-^<β∪ H_γ^-^=α^-∪ H_γ^-^<α+H_γ^-^=α∪ V_α^<β,

  * the boundary points of ^-(α,β) in  V_ℝ (Q)
are  V_α^+^<β∪ H_γ^+^=α^+∪ H_γ^+^>α∪ H_γ^-^=α∪ V_α^<β.
 





In the case of Figure <ref>,  if  the signs of the slopes are all positive on the 
 boundary points,
the matching process is intuitive and illustrated by Figure <ref>.

   



The aim of the next pages is to transform the intuition used in the example into explicit definitions and an algorithm covering all cases. 



 
It holds
 
 
  a)  
 All the boundary points of  ^+(α,β) in  V_ℝ (Q)  have the same slope sign.
 
  b)
All the boundary points of  ^+(α,β) in  V_ℝ (Q)  have the same slope sign.
  
  c) 
 All the boundary points of  ^-(α,β) in  V_ℝ (Q) have the same slope sign.
 
  d) 
 All the boundary points of  ^-(α,β) in  V_ℝ (Q)  have the same slope sign.
  

 
 
We prove only a), the proofs for b), c) and d) being similar.

Suppose that H_γ^+^=α^-+H_γ^+^<α+H_γ^+^=α has at least two elements, and that ( x_1, γ^+ ) and ( x_2, γ^+ ) x_1<x_2 are two 
 points of H_γ^+^=α^-+H_γ^+^<α+H_γ^+^=α with different slope signs and denote by C_1 and C_2 the connected components of V_ℝ(Q) inside [α^-,α)× such that (x_1,γ^+)∈C̅_1 and 
 (x_2,γ^+)∈C̅_2.
 Since
 (α,β) is an adjacency box (cf Definition <ref>), C_1 and C_2 are the graphs of two monotonous semi-algebraic continuous functions φ_1 and φ_2 defined on [α^-,α). At α, φ_1 and φ_2 have limits of opposite signs, so that the sign of the limit of φ_1-φ_2 is well defined at α.
 The signs of φ_1(x_1)-φ_2(x_1) at x_1 and the sign of the limit of φ_1-φ_2 at x_2 are opposite, so φ_1(x)=φ_2(x) for a value x∈ (x_1,α), which is impossible because such a point would be a singular point of V_ℝ(Q)  inside [α^-,α)×.
 
 Suppose that V_α^>β (resp. V_α^-^>β) has at least two elements, and that (α, y_1) and (α,y_2) 
 (resp.   (α^-, y_1) and (α^-,y_2) ), y_1<y_2, are two
 points of V_α^>β (resp. V_α^>β)  with different slope signs and denote by C'_1 and C'_2 the connected components of V_ℝ(Q) inside × (β,γ^+] containing them.
 Since 
  (α,β) is an adjacency box (cf Definition <ref>),
   C'_1 and C'_2 are the graphs of two monotonous semi-algebraic continuous functions ψ_1 and ψ_2 defined on 
 (β,γ^+].
 The signs of ψ_1-ψ_2 at y_1 and y_2 are opposite, so ψ_1(y)=ψ_2(y) for a value y∈ (y_1,y_2), which is impossible because such a point would be a singular point of V_ℝ(Q)  inside × (β,γ^+].
 
 
Suppose  that H_γ^+^=α^-+H_γ^+^<α+H_γ^+^=α≠∅ and V_α^>β≠∅, and let  (α,y) be the element of V̅_α^>β with highest value of y.

(i) Suppose  that the slope sign of (α,y) is negative 
and the slope sign of the elements of H_γ^+^=α^-+H_γ^+^<α+H_γ^+^=α is positive. Let (x,γ^+) be the element of H_γ^+^<α+H_γ^+^=α with highest value of x. Denote by C'_1 and C'_2 the connected components of V_ℝ(Q) inside × (β,γ^+] such that (α,y)∈C̅_1 and (x,γ^+)∈C̅_2.  
Since  
 (α,β) is an adjacency box (cf Definition <ref>), C'_1 (resp. C'_2) is the graph of an increasing (resp. decreasing) semi-algebraic continuous functions ψ_1 (resp. ψ_2) defined on 
 (β,γ^+].  The matching point of (α,y) is not (x,γ^+) because these two points have opposite slope signs so that the limit of φ_1 at γ^+ is strictly less than  x.
 The signs of  the limit ψ_1-ψ_2 at β  (resp.  γ^+) is positive  (resp. negative) and at y_2  is negative  (resp. positive) , so ψ_1(y)=ψ_2(y) for a value y∈ (β,γ^+), which is impossible because such a point would be a singular point of V_ℝ(Q)  inside × (β,γ^+).

(ii) Suppose  now that the slope sign  of
 (α,y) is positive and the slope sign of the elements of H_γ^+^=α^-+H_γ^+^<α+H_γ^+^=α is negative.
 
If Q(α,γ^+)=0, this is impossible by (i), using the symmetry with respect to the line X=α.

Otherwise there is an element  (x,γ^+) in H_γ^+^=α^-+H_γ^+^<α. Denote by C_1 (resp. C_2) the connected components of V_ℝ(Q) inside [α^-,α)× such that (x,γ^+)∈C̅_1 (resp.
 (α,y)∈C̅_2). 
 Since
  (α,β) is an adjacency box (cf Definition <ref>),
   C_1 (resp. C_2) is the graph of an increasing (resp. decreasing) semi-algebraic continuous functions φ_1 (resp. φ_2) defined on [α^-,α). The matching point of (x,γ^+) is not (α,y) because these two points have opposite slope signs so that the limit of φ_2 at α is strictly less than  y. So the limit of φ_1-φ_2 at α^- (resp. α) is negative (resp. positive). It follows that φ_1(x)=φ_2(x) for a value x∈ (α^-,α), which is impossible because such a point would be a singular point of V_ℝ(Q)  inside [α^-,α)×.
  
   Suppose finally that H_γ^+^=α^-+H_γ^+^<α+H_γ^+^=α≠∅ and  V_α^-^>β≠∅, and let  (α,y) be V_α^-^>β≠∅ with highest value of y.

(i) Suppose  that the slope sign of (α,y) is negative 
and the slope sign of the elements of H_γ^+^=α^-+H_γ^+^<α+H_γ^+^=α is positive. Let (x,γ^+) be the element of H_γ^+^<α+H_γ^+^=α with smallest value of x. Denote by C'_1 and C'_2 the connected components of V_ℝ(Q) inside × (β,γ^+] such that (α,y)∈C̅_1 and (x,γ^+)∈C̅_2.  
Since  
 (α,β) is an adjacency box (cf Definition <ref>), C'_1 (resp.) C'_2 is the graph of an increasing (resp. decreasing) semi-algebraic continuous functions ψ_1 (resp. ψ_2) defined on 
 (β,γ^+] .  The matching point of (α,y) is not (x,γ^+) because these two points have opposite slope signs so that the limit of φ_1 at γ^+ is strictly less than  x.
 The signs of  the limit ψ_1-ψ_2 at β  (resp.  γ^+) is positive  (resp. negative) and at y_2  is negative  (resp. positive) , so ψ_1(y)=ψ_2(y) for a value y∈ (β,γ^+), which is impossible because such a point would be a singular point of V_ℝ(Q)  inside × (β,γ^+).

(ii) Suppose  now that the slope sign  of
 (α,y) is positive and the slope sign of the elements of H_γ^+^=α^-+H_γ^+^<α+H_γ^+^=α is negative.
 
If Q(α^-,γ^+)=0 , this is impossible by (i), using the symmetry with respect to the line X=α.

Otherwise there is an element  (x,γ^+) in H_γ^+^=α^-+H_γ^+^<α. Denote by C_1 (resp. C_2) the connected components of V_ℝ(Q) inside [α^-,α)× such that (x,γ^+)∈C̅_1 (resp.
 (α,y)∈C̅_2). 
 Since
  (α,β) is an adjacency box (cf Definition <ref>),
   C_1 (resp. C_2) is the graph of an increasing (resp. decreasing) semi-algebraic continuous functions φ_1 (resp. φ_2) defined on [α^-,α). The matching point of (x,γ^+) is not (α,y) because these two points have opposite slope signs so that the limit of φ_2 at α is strictly less than  y. So the limit of φ_1-φ_2 at α^- (resp. α) is negative (resp. positive). It follows that φ_1(x)=φ_2(x) for a value x∈ (α^-,α), which is impossible because such a point would be a singular point of V_ℝ(Q)  inside [α^-,α)×.





We denote by σ^+ (resp. σ^-) the slope signs of the boundary points of 
^+(α,β) (resp. ^-(α,β)) in  V_ℝ (Q) 
and by 
τ^+ (resp. τ^-) 
of the boundary points of 
^+(α,β) (resp. ^-(α,β)) in  V_ℝ (Q) 

By convention when
there are no boundary points of 
^+(α,β) (resp. ^-(α,β))  in  V_ℝ (Q) 
 we define σ^+ (resp. τ^-) to be  >0 
 and  when
 there are no boundary points of 
^-(α,β), (resp. ^+(α,β))) in  V_ℝ (Q) 
 we define σ^-, (resp. τ^+) to be  <0.








We denote by Left^+ 
 the number of curve segments arriving at (α,β) inside  ^+(α,β) .

If σ^+>0 and (σ^->0 or Q(α^-,β)=0), there is no matching point of a boundary point of  ^+(α,β) contained in   ^-(α,β) and no curve segment starting from  V_α^-^>β is of type 2, so that 
    Left^+=0.
  This is clear by
Remark <ref> and by the fact that there are no singular point in (α,β).

If σ^+<0  and σ^-<0 and Q(α^-,β)=0, there is no matching point of a boundary point of  ^+(α,β) contained in  ^-(α,β) and 
 
    Left^+=#V_α^-^>β-(#H_γ^+^ < α+#H_γ^+^= α+#V_α^>β).
  This is clear by the fact that there are no singular point in (α,β).
 
 If σ^+<0  and σ^-<0 with Q(α^-,β)≠0, there maybe matching points of a boundary points of  ^+(α,β) contained in  ^-(α,β) and 
 
    Left=#V_α^-+#H_γ^+^= α^- +#H_γ^+^< α-(#H_γ^-^ < α+#H_γ^-^= α)-(#V_α^>β+#V_α^<β).

  This is clear by
Remark <ref> and by the fact that there are no singular point in (α,β).
 
It is easy to prove the statement, using symmetries.



In the case of Figure <ref>,  for the left side we have Q(α^-,β)≠0,
 #V_α^-=7, #H_γ^+^= α^-=0, #H_γ^+^ < α=2, #H_γ^+^= α=0, #H_γ^-^= α^-=0, #H_γ^-^ < α=1, #H_γ^-^= α=0, #V_α^>β=2, #V_α^<β=2. 
  For the right side we have Q(α^+,β)≠0,
#V_α^+=5, #H_γ^+^= α^+=0, #H_γ^+^ > α=1, #H_γ^+^= α=0, #H_γ^-^= α^+=0, #H_γ^-^ > α=0, #H_γ^-^= α=0, #V_α^>β=2, #V_α^<β=0. 
 
 Hence, if  σ^+>0,  σ^->0,  from formula (<ref>) Left= 2. 
If   
τ^+>0, τ^->0. we have 
 from formula (<ref>)
 Right= 2. 
 This is illustrated by 
Figure <ref>.
  
  Always in the case of Figure <ref>,
if we have σ^+>0,  σ^-<0, τ^+>0, τ^-<0
it follows from formula (<ref>) Left= 0 and from formula (<ref>)
 Right= 2. This is illustrated by 
 Figure <ref>.
 
  
 
   



 §.§ Computing 
adjacency boxes at singular points
 


Our aim is now to compute adjacency boxes at singular points.

We need to introduce the following definitions.


In order to distinguish the Y-critical points which belong to a horizontal line contained in the  curve and the other Y-critical points,
we write

    Q(X,Y)=c(Y)·Q̃(X,Y)

 with c(Y)∈ [Y] and  Q̃(X,Y)∈ [X, Y] such that Q̃(X,y)
never identically vanishes for  any y ∈ℂ. In more geometric terms, we separate the horizontal lines contained in V_ℂ (Q) from the remaining part V_ℂ (Q̃) of the curve, which does not contain any horizontal lines. 

This is done as follows. Let  Q(X,Y):=c__X(Q)(Y)X^_X(Q)+…+c_0(X), with _X(Q)≤ d. Let c(X) the gcd of all the coefficients c_i(X). 
We compute c(Y) and Q̃(X,Y) using (d^4+d^3τ) bit operations by Propositions <ref> and <ref>.
The polynomials  
c(Y) and Q̃(X,Y) have magnitude bounded by (d,τ+d+log (d+1)).



We introduce the following definitions
 
    D_Y(Y)    :=    _X (Q) (Y), 
      
    
       S_X(X)    :=    
       D_X(X) ·_Y (Q̃, ∂_X Q̃) (X), 
    
        S_Y(Y)    :=    D_Y(Y)   ·_X (
        Q, 
        ∂_Y 
        Q) (Y), 
    
        T_X(X)   :=    S_X(X)· (S_X^⋆)'(X), 
    
        T_Y(Y)   :=    S_Y(Y)· (S_Y^⋆)'(Y).

 where (S_X^⋆)' and  (S_X^⋆)' are the derivatives of the square-free parts of S_X and S_Y, respectively.
 
 In geometric terms
 
 
  * the zeroes of D_Y are the projections on the Y axis of the  Y-critical points
 or the values γ such that (Q(X,γ))<_X(Q)-1,
 
  * the zeroes of S_X are the zeroes of D_X and the projections on the X-axis of the Y-critical points which do not belong to an horizontal line entirely contained in V_ℝ (Q),
  
  * the zeroes of S_Y are the zeroes of D_Y and the projections on the Y-axis of the X-critical points,
  
  * the zeroes of T_X(X) are the zeroes of S_X and the zeroes of the derivative of its square-free part,
   
  * the zeroes of T_Y(Y) are the zeroes of S_Y and the zeroes of the derivative of its square-free part. 
 
 Note that between α_i and α_i+1 there is always one root of (S_X^⋆)'(X) and that 
 between two roots of D_Y there is always one root of  (S_Y^⋆)'(Y).
 
 
 All the polynomials  D_X,D_Y,S_X,S_Y,T_X,T_Y are of magnitude 
bounded by
(O(d^2), O(dτ+d^2)) and can be all computed with a bit complexity (d^4 τ+d^5).
  
  .
Use Proposition  <ref> and <cit.>,<cit.>
  
 

  We 
   denote by ξ_1,…,ξ_N', with
  
    ξ_1<…<ξ_N',

 the real roots of (S_X^⋆)'(X), and 
 ξ_0=-(T_X), ξ_N'+1=(T_X) using Notation <ref>, such that ξ_0 (resp. 
 ξ_N'+1) is smaller (resp. bigger) than all real roots of S_X and (S_X^⋆)'.  Remark that ξ_0 and ξ_N'+1 are rational numbers of bitsize (dτ+d^2).
 
 For every i=1,…,N, we denote
 α^-_i and α^+_i the two successive elements of 
    {ξ_0,ξ_1,…,ξ_N',ξ_N'+1}

defined by
 α_i∈ (α^-_i,α^+_i). Note that α_i is the
 only root of S_X (hence of D_X)  in (α^-_i,α^+_i). 
 
 In the Y-direction, we denote by γ_1,…,γ_M, with
 
    γ_1<…<γ_M,
 the real roots of S_Y(Y).
   We also denote by 
   
    η_1<…<η_M',

   the real roots of (S_Y^⋆)'(Y), and 
 η_0=-(T_Y), η_M'+1=(T_Y)) using Notation <ref>, such that η_0 (resp. 
 η_M'+1) is smaller (resp. bigger) than all real roots of S_Y and (S_Y^⋆)'. Remark that η_0 and η_M'+1 are rational numbers of bitsize O (dτ+d^2).
 For every k=1,…,M,
 we denote by
 γ^-_k and γ^+_k the two successive elements of 
    {η_0,η_1,…,η_M',η_M'+1}

defined by
  γ_i∈ (γ^-_i,γ^+_i). Note that γ_i is the
 only root of S_Y (hence of D_Y)  in (γ^-_i,γ^+_i).
 
For every singular point (α_i,β_i,j), notice that β_i,j is a root of S_Y. 
We define
k(i,j) 
as
the index such that 
γ_k(i,j)=β_i,j.
 

For each i=1,…,N, we denote by

    η^-_i,1<…<η^-_i,m^-_i (resp. η^+_i,1<…<η^+_i,m^+_i)

 the real roots of Q(α_i^-,Y) (resp. Q(α_i^+,Y)).
  
  For each k=1,…,M, we denote by

    ξ^-_k,1<…<ξ^-_k,n^-_k (resp. ξ^+_k,1<…<ξ^+_k,n^+_k)

 the real roots of Q(X,γ_k^-) (resp.  Q(X,γ_k^+)).
 



We suppose the computations of Theorem <ref> have already been performed and prove the following result. Its 
Corollary <ref> provides adjacency boxes at critical points.




 Using (d^5 τ + d^6) bit operations, we can carry out the following computations:
 
 
  (a.1)
  Dyadic intervals H_i,V_i,j
for 1≤ i ≤ N, 1 ≤ j ≤ m_i
such that
H_i
 is well-isolating for α_i  as a root of T_X,
 and V_i,j
is well-isolating for β_i,j as a root of Q(α_i,Y).
  
  (a.2)
 Dyadic intervals H^-_i, V^-_i,j, (resp. H^+_i, V^+_i,j)
  for 1≤ i ≤ N, 1 ≤ j ≤ m^-_i (resp. j≤  m^+_i)
such that
 H^-_i (resp  H^+_i)
 is well-isolating for α^-_i (resp. α^+_i) as a root of T_X,
and V^-_i,j (resp. V^+_i,j)
 is well-isolating for η^-_i,j (resp. η^+_i,j)  as a root of Q(α^-_i,Y) (resp.  Q(α^+_i,Y)).
 Moreover the signs of ∂_XQ(α^-_i,η^-_i,j) and ∂_YQ(α^-_i,η^-_i,j) (resp. ∂_XQ(α^+_i,η^+_i,j) and 
 ∂_YQ(α^+_i,η^+_i,j) are also part of the output.
 
  (b) Dyadic intervals V^-_k, H^-_k,ℓ (resp. V^+_k, H^+_k,ℓ)
   for 1≤ k ≤ M, 1 ≤ℓ≤ n^-_k (resp. ℓ≤  n^+_k) such that
V^-_k (resp. H^+_k) is well-isolating for γ^-_k (resp. γ^+_k) as a root of 
T_Y 
and H^-_k,ℓ (resp.  H^+_k,ℓ) is well-isolating for ξ^-_k,ℓ (resp. ξ^+_k,ℓ) as a root of 
Q(X,γ^-_k) (resp.  Q(X,γ^+_k)).
 Moreover the signs of ∂_XQ(ξ^-_k,ℓ,γ^-_k) and ∂_YQ(ξ^-_k,ℓ,γ^-_k) (resp. ∂_XQ(ξ^+_k,ℓ,γ^+_k) and 
 ∂_YQ(∂_XQ(ξ^+_k,ℓ,γ^+_k)) are also part of the output.
 
  (c.1)  Dyadic intervals V_k, for  k=1,…,M, that are well-isolating for γ_k  as roots of T_Y and for each 
 i=1,…,N, j∈SingInd_i,
 the index k(i,j) such that β_i,j=γ_k(i,j)
 
  (c.2) For each i=1,…,N, j∈SingInd_i,
the intervals H^-_k(i,j),ℓ for ℓ=1,…,n^-_k(i,j),ℓ  (resp. H^+_k(i,j),ℓ for  ℓ=1,…,n^+_k(i,j),ℓ)
contain at most one of the three points  α^-_i, α_i, α^+_i.

  (c.3) For each i=1,…,N, j∈SingInd_i,
 the intervals V^-_i,j' for j'=1,…,m^-_i  (resp. V^+_i,j' for j'=1,…,m^+_i) contain at most one of the two points   γ^-_k(i,j)  γ^+_k(i,j).
  
Moreover, it holds  that
 
    ∑^N_i = 1λ (H_i) (resp.  ∑^N_i = 1λ (H^-_i),∑^N_i = 1λ (H^+_i))
     ∈Õ (d^3 τ+d^4),
 
 
    ∑^N_i = 1∑^m_i_j = 1λ (V_i, j) (resp. ∑^N_i = 1∑^m^-_i_j = 1λ (V^-_i, j),∑^N_i = 1∑^m^+_i_j = 1λ (V^+_i, j))
    ∈Õ (d^3
     τ+d^4)  .

  
    ∑^M_k = 1λ (V_k)(resp. ∑^M_k = 1λ (V_k^-), ∑^M_k = 1λ (V_k^+))  ∈Õ (d^3
     τ+d^4)  .

 
    ∑^M_k = 1∑^n^-_k_ℓ = 1λ (H^-_k,ℓ)  (resp. ∑^M_k = 1∑^n^+_k_ℓ = 1λ (H^+_k,ℓ)) 
    ∈Õ (d^3
     τ+d^4)  .




Note that  Theorem <ref> (c.2) does not decide whether
ξ^+_k(i,j),ℓ<α_i,
ξ^+_k(i,j),ℓ=α_i or ξ^+_k(i,j),ℓ>α_i
in the case where
H^+_k(i,j),ℓ intersects H_i.
 Indeed, we do not compute the sign of Q(α_i,γ_k(i,j)^+).
It would be of course possible to obtain this information using exact computations, but not within the complexity bounds we are aiming for in this paper: 
to the best of our knowledge, the computation for this decision would exceed (d^5 τ + d^6) bit operations, 
because the distance between α_i and ξ^+_k(i,j),ℓ can be very small and it would be very costly to refine  H^+_k(i,j),ℓ and H_i enough for this decision.

The same remark holds for similar statements covering  the other cases considered in (c.2) and (c.3).





For (a.1) first note, using Lemma <ref>, that T_X is a polynomial of magnitude
bounded by
 (N,Λ)∈ (O(d^2),(dτ+d^2)).  Hence, Proposition <ref> and Proposition <ref>, 
we can compute well-isolating intervals for the real roots of T_X and identify the real roots of D_X in a number of bit operations bounded by (d^5τ+d^6).
 According to 
Proposition <ref> (with R:=D_X and F:=Q(X,Y)), we may further compute 
((Q(α_i,Y),∂_Y Q(α_i,Y))) for all i from 1 to N  using (d^5τ+d^6) bit operations. Now, from Proposition <ref>, we conclude that  using also (d^5τ+d^6) bit operations we can further compute 
well-isolating intervals for all real roots of the 
polynomials Q(α_i,Y).

For (a.2), using Proposition <ref> and Proposition <ref>, 
we can compute well-isolating intervals for the real roots of T_X and identify the real roots of (D_X^⋆)' in a number of bit operations bounded by (d^5τ+d^6).
 According to 
Proposition <ref> (with R:=(T_X^⋆)' and F:=Q(X,Y)), we may further compute Q(ξ_i,Y).
Now, from Proposition <ref>, we conclude that within a number of bit operations bounded by (d^5τ+d^6) we can further compute well-isolating intervals for all real roots of the 
polynomials  

    Q(ξ_i,Y) ·∂_XQ(ξ_i,Y)·∂_YQ(ξ_i,Y),

and identify the roots of Q(ξ_i,Y) for each i=1,…,N' by  Proposition <ref>.
It remains to compute isolating intervals for all the 
 roots of the 
polynomials  

    Q(ξ_0,Y) ·∂_XQ(ξ_0,Y)·∂_YQ(ξ_0,Y),

and

    Q(ξ_N',Y)·∂_XQ(ξ_N',Y)·∂_YQ(ξ_N',Y).

It is then easy to identify α_i^- and α_i^+ as well as H^-_i,V^-_i,j',V^+_i,V^+_i,j' as part of the results of the preceding computations.
 The bound on the sum of the bitsizes of the 
intervals H^-_i,V^-_i,j',H^+_i,V^+_i,j'
follows from Part (a.1) of Proposition <ref> and Proposition <ref>.


Part (b) is entirely similar to Part (a.2), exchanging the role of X and Y.

In Part (c.1), the computation of T_Y takes (d^4 τ+d^5) according to Lemma <ref>, and the computation of the V_k, k=1,…,M uses a number of bit operations bounded by (d^5τ+d^6) from Proposition <ref> and Proposition <ref> since T_Y is of magnitude
bounded by
 (O(d^2),O(dτ+d^2)).
 
 We define I^1_i:=SingInd_i. 
In order to compute the numbers k(i,j) for each 
β_i,j, j ∈SingInd_i, we proceed in rounds enumerated by ℓ=1,2,3,…. In the ℓ-th round, we refine the isolating intervals for all i and all roots β_i,j with j ∈ I^ℓ_i to a size less than 2^-2^ℓ. If the corresponding isolating interval 
V_i,j
 intersects with at most one isolating interval V_k for the roots of 
T_Y, we know that k=k(i,j). After having treated all elements in I^ℓ_i, we set I^ℓ+1_i to be the set of all critical indices in I^ℓ_i for which the isolating interval
 V_i,j for β_i,j intersects more than one of the intervals V_k. That is, I^ℓ_i is the set of all critical indices  for which k(i,j) is not known after the ℓ-th round. We then proceed with the (ℓ+1)-st round. We stop as soon as I^ℓ_i becomes empty for every i=1,…,N, in which case, k(i,j) is determined for all X-critical points.

We use the polynomial R_Y defined in Proposition <ref>, with F=Q, remembering that the roots of R_Y contain the projections of the Y-critical points of Q.
Notice that, for each critical point (α_i,β_i,j), we succeed in round ℓ_i,j, where
2^ℓ_i,j is bounded by O(|log((β_i,j,T_Y R_Y))|). That is, j ∉ I^ℓ_i for any ℓ>ℓ_i,j.

In addition, the cost of the test for checking whether the interval V_i,j intersects with exactly one isolating interval V_k is bounded by (d^3τ+d^4) bit operations in each round. Indeed, 
 we need to consider only O(log (d)) comparisons between corresponding
endpoints of the occurring intervals and each comparison is carried out with a precision bounded by (d^3τ+d^4), using that, from the amortized bounds on the separation of the roots  (Proposition <ref>) 
    O(|log((β_i,j,T_Y R_Y))|)∈ O(d^3τ+d^4).
 Since there are O(d^2) many critical points, the 
total cost for the comparisons is thus bounded by (d^5τ+d^6).

 It remains to estimate the cost for refining the intervals V_i,j to a width less than 2^-2^ℓ_i,j for all i,j.
Using again O(|log((β_i,j,T_Y R_Y))|)∈ O(d^3τ+d^4), 
we are done after κ rounds for  

    κ=max_i,jℓ_i,j+1 ∈ O(log(d^4+d^3 τ)).

 According to Proposition <ref>, this cost is bounded by

    ∑_ℓ=1^κ(d^5τ+d^6+ 2^ℓd^2·∑_i=1^Nμ_i^[ℓ])∈(d^5τ+d^6)+(d^2·∑_ℓ 2^ℓ·∑_i=1^Nμ_i^[ℓ]),

where, denoting μ_i,j=(β_i,j,Q(α_i,Y))

    μ_i^[ℓ]:=
    max_j ∈ I^ℓ_iμ_i,j   if   I^ℓ_x≠∅
    
    0    otherwise.



Hence, it suffices to show that 

    ∑_ℓ=1^κ 2^ℓ·∑_i=1^Nμ_i^[ℓ]∈(d^3τ+d^4).

 If  I^ℓ_i≠∅, let j^[ℓ]_i∈ I^ℓ_i be such that μ_i,j^[ℓ]_i=μ_i^[ℓ]. In other words, j^[ℓ]_i is the critical index I^ℓ_i over α_i which maximizes the multiplicity within the fiber. We may thus write

    ∑_ℓ=1^κ 2^ℓ·∑_i=1^Nμ_i^[ℓ]=∑_ℓ=1^κ 2^ℓ∑_i,I^ℓ_i≠∅μ_i,j^[ℓ]_i

Obviously, each critical index (i,j)
 appears in the latter sum a number of times that is bounded by κ∈ O(log(d^3τ+d^4)). In addition, since (α_i,β_i,j)∉ I_κ 
and 2^ℓ_i,j∈ O(|log((β_i,j,T_Y R_Y))|), it follows that,

    ∑_ℓ=1^κ 2^ℓ∑_i=1^N ∑_j∈ I^ℓ_iμ_i,j∈(∑_i=1^N ∑_j∈SingInd_iμ_i,j·|log((β_i,j,T_Y R_Y))|).

 Since 

    ∑_ℓ=1^κ 2^ℓ∑_i,I^ℓ_i≠∅μ_i^[ℓ]≤∑_ℓ=1^κ 2^ℓ∑_i=1^N ∑_j∈ I^ℓ_iμ_i,j,

we have

    ∑_ℓ=1^κ 2^ℓ∑_i,I^ℓ_i≠∅μ_i^[ℓ]∈(∑_i=1^N ∑_j∈SingInd_iμ_i,j·|log((β_i,j,T_Y R_Y))|).


According to Proposition <ref>, it holds that, for any fixed value β_i,j,

    ∑_(α_i,β_i,j):β_i,j=γ(
    μ_i,j-1)≤(γ,R_Y)).
 
Hence, since 
μ_i,j≤ 2·(μ_i,j-1)
we conclude that

    ∑_(i,j):β_i,j=γμ_i,j≤ 2·(γ,T_Y R_Y).

This shows that

    ∑_ℓ=1^κ 2^ℓ∑_i=1^Nμ_i^[ℓ]∈(
    (T_Y R_Y))
    ∈(d^3τ+d^4).

using
Proposition <ref>.


Part (c.2,c.3) can be proved as  follows.
We treat in details the case of intervals  V^-_i,j which is the first half of c3).

For each fixed k,  we define the set of indices of singular places at level k as

    SingPl_k:={i∈{1,…,N}:(α_i,γ_k)∈(V_ℝ(Q))}.

with, as before,
with
(V_ℝ(Q)) := {(x, y) ∈ℝ^2 | Q(x, y) =∂_Y Q(x,y)=∂_X Q(x,y)= 0}. 
Let V^-_i,j' be the intervals as computed according to
Part (a.2). In what follows, we restrict to the set I^1 of all so-called bad pairs (i,j') of indices such that the  
interval V^-_i,j' intersects two intervals V_k(i,j)^- and V_k(i,j)^+, and define I^1_i as the set of corresponding indices above i.
 We fix a mapping ϕ that maps 
each such bad pair (i,j') to an arbitrary index k(i,j) (there might exist more than one such index)
such that V^-_i,j' intersects the intervals V_k(i,j)^- and V_k(i,j)^+ and moreover γ_k(i,j)^+-γ_k(i,j)^- is minimal with this property. Then, the size of the preimage of each k(i,j) is upper bounded by SingPl_k(i,j). Namely, for a fixed i, there can be at most one interval V_i,j'^- intersecting the two intervals V_k(i,j)^- and V_k(i,j)^+. We thus conclude, using Proposition <ref> and its notation, with F=Q, that 

    |Φ^-1(k(i,j))|≤#SingPl_k(i,j)≤(γ_k(i,j),R_Y) ≤(γ_k(i,j),R_YT_Y),

which further implies that I^1 contains at most O(d^2) many elements. Further notice that a pair (i,j) cannot be bad if the width of the corresponding interval V^-_i,j' is smaller than 1/2·(γ,T_Y) as the distance between  the intervals V_k^- and V_k^+ is at least 1/2·min(|γ_k(i,j)^-γ_k(i,j)^-|)≤1/2·(γ^-_k(i,j),T_Y). Hence, in order to guarantee that the  V^-_i,j' does not intersects two intervals V_k(i,j)^- and V_k(i,j)^+, it is enough to refine the intervals V^-_i,j' with (i,j')∈ I_1 to a width smaller than 1/2·(γ^-_k(i,j),T_Y). 

For this,  we proceed in rounds enumerated by ℓ=1,2,3,…, where, in the ℓ-th round, we refine all intervals V^-_i,j' with (i,j')∈ I^ℓ_i to a width less than 2^-2^ℓ. Then, we remove all pairs j' from I^ℓ_i that are not bad anymore to obtain I^ℓ+1_i. In other words, I^ℓ+1_i is the set of all pairs for which V^-_i,j  intersects  two intervals V_k(i,j)^- and V_k(i,j)^+ after the ℓ-th round. We then proceed with the (ℓ+1)-st round. We stop as soon as all  I^ℓ_i becomes empty, in which case, none of the intervals V^-_i,j' violates the condition.

Notice that an interval V^-_i,j' is removed after ℓ_i,j' rounds, where 2^ℓ_i,j' is bounded by O(|log((γ_ϕ((i,j')),T_Y))|). That is, j∉ I^ℓ_i for any ℓ>ℓ_i,j'. This further implies that each root contained in ϕ(V_ℓ) has separation smaller than 2^1+2^-ℓ. Further notice that,  from the amortized bounds on the separation of the roots  (Proposition <ref>)

    O(|log((γ_ϕ((i,j')),T_Y))|)∈ O(d^3τ+d^4),
 so that the test  checking whether j'∈ I^ℓ_i is bounded by (d^3τ+d^4) bit operations in each round as we need to consider only O(log(d)) comparisons between corresponding
endpoints of the occurring intervals and each comparison is carried out with a precision bounded by (d^3τ+d^4). Since there are O(d^2) many element in each I, the 
total cost for the comparisons is thus bounded by (d^5τ+d^6).

 It remains to estimate the cost for refining the intervals V^-_i,j' to a width less than 2^-2^ℓ_i,j for all (i,j)∈ I.
Using again O(|log((γ_ϕ((i,j')),T_Y))|)∈ O(d^3τ+d^4),

    κ=max_i,j'ℓ_i,j'+1∈ O(log(d^3 τ+d^4)).

 According to Proposition <ref>, this cost is bounded by

    ∑_ℓ=1^κ(d^5τ+d^6+ 2^ℓd^2·λ_ℓ)∈(d^5τ+d^6)+(d^2·∑_ℓ 2^ℓ·|{i| I^ℓ_i≠∅}|,

 Hence, it suffices to show that 

    ∑_ℓ=1^κ 2^ℓ· |{i| I^ℓ_i≠∅}|∈(d^4+d^3τ),

or alternatively that

    ∑_ℓ=1^κ∑_k(i,j):log((γ_k(i,j),R_YT_Y))<2^1-2^ℓ(γ_k(i,j),R_YT_Y)·|log((γ_k(i,j),R_YT_Y))| ∈(d^3τ+d^4).

as each root γ_k(i,j) has at most (γ_k(i,j),R_YT_Y) preimages under the mapping ϕ and ϕ(I^ℓ_i) contains only roots γ_k(i,j) of separation smaller than 2· 2^1-2^ℓ.
Since κ∈ O(log(d^3τ+d^4)) and since ∑_k=1^M (γ_k(i,j),R_YT_Y)·|log((γ_k,R_YT_Y))| ∈(d^3τ+d^4), we conclude that the inequality in (<ref>) holds.

The case of intervals  V^+_i,j' which is the second half of (c.1) is entirely similar.
We also omit the proof of (c.2) which is quite similar, exchanging the role of X and Y and treating first the case α_i^-,α_i and second the case α_i,α_i^+.



 Using the notation of Theorem <ref>, we have

 
For every i and j∈SingInd_i, 
    (α_i,β_i,j)=[α^-_i,α^+_i]×[γ^-_k(i,j),γ^+_k(i,j)]

is an adjacency bor for (α_i,β_i,j).

Moreover if 


  * H_i^- does not  intersect any H_k(i,j),ℓ^- or V_k(i,j)^-  does not  intersect any V_i,ℓ^- 

  * H_i does not  intersect any H_k(i,j),ℓ^- or V_k(i,j)^-  does not  intersect any V_i,ℓ 

  * H_i^+ does not  intersect any H_k(i,j),ℓ^- or V_k(i,j)^-  does not  intersect any V_i,ℓ^- 

  * H_i^- does not  intersect any H_k(i,j),ℓ^+ or V_k(i,j)^+  does not  intersect any V_i,ℓ^- 

  * H_i does not  intersect any H_k(i,j),ℓ^+ or V_k(i,j)^+  does not  intersect any V_i,ℓ 

  * H_i^+ does not  intersect any H_k(i,j),ℓ^+ or V_k(i,j)^+  does not  intersect any V_i,ℓ^+ 

the numbers 
Left_i,j and Right_i,j are known.


The fact that (α_i,β_i,j) satisfies the conditions of Definition <ref> follows clearly from Theorem <ref> (a) and (b) given the definition of T_X and T_Y. 

It is clear that if  H_i^- does not  intersect any H_k(i,j),ℓ^-, H_i^- does not  intersect any H_k(i,j),ℓ^- and H_i^+ does not  intersect any H_k(i,j),ℓ^-, then #H_γ_k(i,j)^-^= α_i^-=#H_γ_k(i,j)^-^= α_i=#H_γ_k(i,j)^-^= α_i^+=0 and the quantities #H_γ_k(i,j)^-^ < α_i and   #H_γ_k(i,j)^-^ > α_i are determined from the output of Theorem <ref>.
Moreover even if V_k(i,j)^-  intersect an interval V_i,ℓ^-  we can compare η_i,ℓ^- and γ_k(i,h)^-, because we know the sign of Q(α_i^-,γ_k(i,h)^-).

Taking into account all the other items, it is easy to see that there is enough information to determine  from the output of Theorem <ref> all the numbers necessary to compute Left_i,j and Right_i,j according to Algorithm <ref>.


 

 §.§ Computing the 
 number of curve segments arriving to the left and to the right of a singular point


Our aim is to 
compute
for all adjacency boxes  (α_i,β_i,j) associated to 
singular points (α_i,β_i,j), the numbers Left_i,j and Right_i,j of 
curve segments
 arriving at
(α_i,β_i,j) to the left and to the right using the formulas in Algorithm <ref>.

Since we concentrate on a fixed singular point, we can forget about the indices in the subsection; Consider 
a 
singular 
point (α,β)=(α_i,β_i,j), and its adjacency box  (α,β) with
α^-=α^-_i,α^+=α^+_i
and
γ^-=γ^-_k(i,j),γ^+=γ^+_k(i,j), where
α^-,α,α^+ and γ^-,γ^+ are given by dyadic intervals (a^-,a'^-),(a,a'),(a^+,a'^+) and (c^-,c'^-),(c^+,c'^+).
Denote Left=Left_i,j and Right=Right_i,j.

The information computed in Theorem <ref> is not always sufficient to determine the quantities involved in  formulas (<ref>, <ref>, <ref>, <ref>, <ref>, <ref>) and (<ref>, <ref>, <ref>, <ref>, <ref>,  <ref>) of Algorithm <ref>. For example,
if at the corner (α^-,γ^+), the interval (x,x')
isolating a root ξ of Q(X,γ^+)  contains 
α^- and   the interval (y,y')
isolating a root η of Q(α^-,Y)  contains 
γ^+,  we do not know the sign Q(α^-,γ^+) so we do not know whether ξ<α^-, ξ=α^- or ξ>α^- (resp. 
η<γ^+, η=γ^+ or η>γ^+)
(see Remark <ref>)
and we cannot determine
 #V_α^-, #H_γ^+^= α^-, #H_γ^+^ < α.

So we introduce the following definition to deal with such situations.


The corner (α^-,γ^+) is
ambiguous
  if there are intervals 
(x,x') and  (y,y') output by Theorem <ref>
such that 
(x,x'), 
isolating a root ξ
 of Q(X,γ^+),
intersects  (a^-,a'^-)
and 
(y,y'),
isolating a root η
 of Q(α^-,Y), 
 intersects  (c^+,c'^+).
 We omit similar definitions for the
three
corners  (α^-,γ^-),
 (α^+,γ^-),  (α^+,γ^+).
 
 Similarly the midpoint (α,γ^+) is
 ambiguous
   if there are intervals 
(x,x') and  (y,y') output by Theorem <ref>
such that 
(x,x'),
isolating a root ξ,
 of Q(X,γ^+)
 contains 
α and 
(y,y'),
isolating a root η
 of Q(α,Y), contains 
γ^+.
We omit a
similar definition for the
other midpoint  (α,γ^-).


At the ambiguous corner (α^-,γ^+), it is not possible to know the cardinals of 
H_γ^+^<α∩ [x,x'], H_γ^+^=α∩ [x,x']  and V_α^-∩ [y,y'] since we do not know whether ξ∈ H_γ^+^<α (resp.  η∈ V_α^-).

However we note that
 

  * If σ^+>0 
(with ∂_XQ(α^-,γ^+)>0 and ∂_YQ(α^-,γ^+)<0) then Q(x,γ^+)<0 and Q(x',γ^+)>0 while 
Q(α^-,y)>0 and Q(α^-,y')<0.


  * If Q(α^-,γ^+)>0, then  ξ<α^- and η>γ^+. 
 So that #H_γ^+^<α∩ [x,x']=#V_α^-∩ [y,y']=0

  * If Q(α^-,γ^+)<0, then   ξ>α^- and η<γ^+. 
 So that #H_γ^+^<α∩ [x,x']=#V_α^-∩ [y,y']=1,

  * If Q(α^-,γ^+)=0,  then  ξ=α^- and η=γ^+. 
 So that #H_γ^+^<α∩ [x,x']=#V_α^-∩ [y,y']=0




 In all cases, when  σ^+>0 (with ∂_XQ(α^-,γ^+)>0 and ∂_YQ(α^-,γ^+)<0)  
 
    #H_γ^+^<α∩ [x,x']-#V_α^-∩ [y,y']=0.


  * If σ^+<0 (with ∂_XQ(α^-,γ^+)>0 and ∂_YQ(α^-,γ^+)>0), then Q(x,γ^+)<0 and Q(x',γ^+)>0 while 
Q(α^-,y)<0 and Q(α^-,y')>0.


  * If Q(α^-,γ^+)>0, then ξ<γ^- and η<α^+.
   So that 
#H_γ^+^<α∩ [x,x']=#H_γ^+^=α^-∩ [x,x']=0,#V_α^-∩ [y,y']=1

  * If Q(α^-,γ^+)<0,
then   ξ>γ^- and  η>α^+. 
 So that 
#H_γ^+^<α∩ [x,x']=1,#V_α^-∩ [y,y']=#H_γ^+^=α^-∩ [x,x']=0

  * If Q(α^-,γ^+)=0 then  ξ=α^- and η=γ^+.
   So that
#H_γ^+^<α∩ [x,x']=#V_α^-∩ [y,y']=0,#H_γ^+^=α^-∩ [x,x']=1





In all cases, when  σ^+<0 (with ∂_XQ(α^-,γ^+)>0 and ∂_YQ(α^-,γ^+)>0)   
    #H_γ^+^<α∩ [x,x']+#V_α^-∩ [y,y']+#V_α^-∩ [y,y']=1.



  * Details for the remaining cases σ^+>0 with  ∂_XQ(α^-,γ^+)<0 and ∂_YQ(α^-,γ^+)>0 (resp. σ^+<0 with ∂_XQ(α^-,γ^+)<0 and ∂_YQ(α^-,γ^+)<0) are entirely similar, and omitted.



Summarizing the situation in  all the cases, the conclusion is as follows


  * If σ^+>0 then

    #V_α^-∩ [y,y']-#H_γ^+^<α∩ [x,x']=0


  * If σ^+<0 then

    #V_α^-∩ [y,y']+#H_γ^+^<α∩ [x,x']+#H_γ^+^=α∩ [x,x']=1



so that the sign of Q(α^-,γ^+) has no influence on Left
given the formulas of Algorithm <ref>.



We now analyze the situation at an ambiguous midpoint (α,γ^+).
 

  * If σ^+>0 with ∂_XQ(α,γ^+)>0 and ∂_YQ(α,γ^+)<0, then Q(x,γ^+)<0 and Q(x',γ^+)>0 while 
Q(α,y)>0 and Q(α,y')<0.


  * If Q(α,γ^+)>0, then   ξ<α and  η>γ^+. So that 

    #H_γ^+^<α∩ [x,x']=1,#H_γ^+^=α∩ [x,x']=#V_α^>β∩ [y,y']=0


  * If Q(α,γ^+)<0, then  ξ>α and η<γ^+. So that 

    #H_γ^+^<α∩ [x,x']=#H_γ^+^=α∩ [x,x']=0,#V_α^>β∩ [y,y']=1


  * If Q(α,γ^+)=0,  then ξ=α and η=γ^+. So that

    #H_γ^+^<α∩ [x,x']=0, #H_γ^+^=α∩ [x,x']=1,#V_α^>β∩ [y,y']=0


In all cases, if σ^+>0 
(with ∂_XQ(α^-,γ^+)>0 and ∂_YQ(α^-,γ^+)<0) then 

    -#H_γ^+^<α∩ [x,x']-#H_γ^+^=α∩ [x,x']-#V_α^>β∩ [y,y']=-1.


  * If σ^+<0 with  ∂_XQ(α,γ^+)>0 and ∂_YQ(α,γ^+)>0, then Q(x,γ^+)<0 and Q(x',γ^+)>0 while 
Q(α,y)<0 and Q(α,y')>0.


  * If Q(α,γ^+)>0, then  the root ξ is to the left of α and the root η is under γ^+. So that 

    #H_γ^+^<α∩ [x,x']=1,#V_α^>β∩ [y,y']=1


  * If Q(α,γ^+)<0,
then  the root ξ is to the right of α and the root η is above γ^+. So that 

    #H_γ^+^<α∩ [x,x']=0,#V_α^>β∩ [y,y']=0


  * If Q(α,γ^+)=0 then ξ=α and η=γ^+. So that

    #H_γ^+^< α∩ [x,x']=#V_α^>β∩ [y,y']=0


In all cases,  when σ^+<0 
 (with ∂_XQ(α^-,γ^+)>0 and ∂_YQ(α^-,γ^+)>0),

    #H_γ^+^<α∩ [x,x']-#V_α^>β∩ [y,y']=0.


  * Details for the remaining cases σ^+>0 with ∂_XQ(α,γ^+)<0 and ∂_YQ(α,γ^+)>0 (resp. σ^+<0 with ∂_XQ(α,γ^+)<0 and ∂_YQ(α,γ^+)<0) are omitted.



Summarizing the situation in all the cases, the conclusion is as follows


  * If σ^+>0 then

    -#H_γ^+^<α∩ [x,x']-#H_γ^+^=α∩ [x,x']-#V_α^>β∩ [y,y']=-1


  * If σ^+<0 then

    #H_γ^+^<α∩ [x,x']-#V_α^>β∩ [y,y']=0


so that the sign of Q(α,γ^+) has no influence on Left 
given the formulas of Algorithm <ref>).


The analysis for the other ambiguous corners and midpoints is similar.

So we can conclude


The sign of  Q at an ambiguous corner or midpoint has no influence on Left and Right.


So we can decide arbitrarily that Q is zero at all ambiguous corners and midpoints. In order to obtain the quantities

    #V_α^-,#H_γ^-^= α^-, #H_γ^-^ < α, #H_γ^-^= α, #H_γ^+^= α^-, #H_γ^+^ < α, #H_γ^+^= α, #V_α^>β, #V_α^<β

we now use the output of Theorem <ref> and the extra information  that Q is zero at all ambiguous corners and midpoints.
Finally, we use these quantities to compute correctly Left 
according to the formulas of Algorithm <ref>. The situation is similar for Right.

All in all, we proved, using  Theorem <ref> and Corollary <ref>:


Using Õ(d^5τ+d^6) bit-operations, we can compute Left_i,j 
and  Right_i,j for every i,j, i=1,…,N, j∈CritInd_i.




 §.§ Vertical asymptotes



We now explain how to deal with the vertical asymptotes.

The vertical asymptotes occur at values of α_i where q(α_i)=0, i.e. (Q(α_i,Y))<_Y(Q).

Our aim is to compute numbers
Left_i,0 and Right_i,0 (resp Left_1,m_i+1 and Right_1,m_i+1) counting the number of asymptotes tending to -∞ just before α_i and  just after α_i (resp. tending to +∞ just before α_i and  just after α_i ).

There are two cases to consider.

As we have seen already in Section <ref>, when (Q(α_i,Y))=_Y(Q)-1,


  * if the degree of the coefficient of degree _Y(Q)-1 evaluated at α_i i is positive, there is only one asymptote going to -∞ just before α_i and to +∞ just  after α_i and we define

    Left_i,0=1,Right_i,0=0, Left_1,m_i+1=0,=Right_1,m_i+1=1.


  * if the degree of the coefficient of degree _Y(Q)-1 evaluated at α_i is negative
there is only one asymptote going to  +∞ before α_i and  -∞ after α_i and we define

    Left_i,0=0,Right_i,0=1, Left_1,m_i+1=1,=Right_1,m_i+1=0.



When (Q(α_i,Y))<_Y(Q)-1, α_i is also a root of D_X. The indices i = 1,…,N such that (Q(α_i,Y))<_Y(Q)-1 are part of the output of Theorem <ref>.


For vertical asymptotes at -∞, we isolate the roots of Q(X,γ^-_1)=0 and decide the sign slope at the roots of
Q(X,γ^-_1)=0. This can be done in (d^4τ+d^5) bit-operations since 
Q(X,γ^-_1) is a polynomial of degree at most d and bit size  O(d^2 τ+d^3).
We also compare the roots of Q(X,γ^-_1) with the roots of D_X. Note first that Q(X,γ^-_1) and D_X  have no roots in common. Since the separators of Q(X,γ^-_1) and D_X are both bounded by 2^Õ(d^3 τ+d^4) this can be done by Proposition
<ref> with complexity  (d^5τ+d^6).

On each open interval (α_i,α_i+1), i=1,…,N delimited by roots of D_X, let Right_i,0 the number of roots of Q(X,γ^-_1)=0  such that the slope sign is >0 and   Left_i+1,0 the number of roots of Q(X,γ^-_1)=0  such that the  slope sign is <0.
We also denote by  let Right_N,0 the number of roots of Q(X,γ^-_1)=0  such that the slope sign is >0 on (α_N,+∞) and   Left_1,0 the number of roots of Q(X,γ^+_M)=0  such that the  slope sign is <0  on (-∞, α_1).

Note that all the roots Q(X,γ^-_1)=0 on (α_i,α_i+1) with positive  slope sign are bigger than all the roots Q(X,γ^-_1)=0 on H_i with negative slope sign. Note also that if α_i is such that (Q(α_i,Y))=_Y(Q), 
Left_i,0=Right_i,0=0.

The situation at +∞ is entirely similar and we define 
 Right_i,m_i+1 the number of roots of Q(X,γ^+_M)=0 on (α_i,α_i+1) such that the slope sign is >0 and   Left_i+1,m_i+1+1 the number of roots of Q(X,γ^+_M)=0 on (α_i,α_i+1) such that the slope sign is <0.
 We also denote by  let Right_N,m_N+1 the number of roots of Q(X,γ^+_M)=0  such that the slope sign is <0 on (α_N,+∞) and   Left_1,m_1+1 the number of roots of Q(X,γ^+_M)=0  such that the  slope sign is >0  on (-∞, α_1).
 
 Finally we have


The number of asymptotic branches tending to -∞ (resp +∞) to the left of α_i is Left_i,0
(resp. Left_i,m_i+1) and the number of asymptotic branches tending to -∞ (resp +∞) to the right of  α_i  is Right_i,0 (resp. Right_i,m_i+1).Moreover the complexity of computing these numbers is  (d^5τ+d^6).



  

 §.§ Final topology

  

 For (α_i,β_i,j) X-critical, i.e. j∈CritInd_i, we denote as before  by Left_i,j (resp. Right_i,j) the number of 
curve segments 
 arriving at (α_i,β_i,j) inside
(α,β) .
  Note that this information has been computed in Proposition <ref> using (d^5τ+d^6) bit operations.
 For j∉CritInd_i, we take Left_i,j=Right_i,j=1. 
  If j CritInd_i∖SingInd_i, denoting by μ_i,j  the multiplicity of β_i,j as a root of Q(α_i,Y) 


  * if μ_i,j  is even and ∂_Y Q^(μ_i,j)(α_i,β_i,j))>0,  Left_i,j=0,Right_i,j=2

  * if μ_i,j  is even and ∂_Y  Q^(μ_i,j)(α_i,β_i,j))<0, Left_i,j=2,Right_i,j=0

  * if μ_i,j  is odd, Left_i,j=Right_i,j=1.

  as discussed  in Section <ref>.
  
 We denote as before  by   Left_i,0  (resp.  Right_i,0) the number 
 of vertical asymptotes tending to -∞ at the left (resp. the right) of α_i and by Left_i,m_i+1  (resp.  Right_i,m_i+1) the number  of vertical asymptotes tending to +∞ at the left (resp. the right) of α_i.  Note that this information has been already determined in Proposition <ref>.
 
 
The topology of V_ℝ(Q) is encoded by the finite list 
    ℒ̃(Q)=[m'_0,L_1,…,L_N ,m'_N]
 where


  - L_i=[m_i,[[Left_i,j,Right_i,j], 0 ≤ j≤ m_i+1]]  for i=1,…,N,


In the special case where  _X(Q(X,Y))=0  and V_ℝ (Q) is a finite number of horizontal lines , we  compute the number m of real roots of Q(X,Y) which is a polynomial in Y.
Similarly in the special case where D_X(X) has no real root, we compute the number m of real roots of Q(0,Y). 

In both special cases, the topology of V_ℝ(Q) is encoded by ℒ̃(Q)=[m].



Now we illustrate the previous result by taking an example, where 

    P(X,Y)= (4X+1)(8X-1)(16X-1)(XY-1)(4Y^2-4X-1)(4Y^2+4X-1),

and

    Q(X,Y)= (XY-1)(4Y^2-4X-1)(4Y^2+4X-1).

 We have 

    D_X=-2^28 X^4 (4 X-1) (1+4 X) (4-
     X^2+4 X^3)^2 (-4+X^2+4 X^3)^2.

 Since
4-
 X^2+4 X^3 (resp. -4+X^2+4 X^3) has one real root on [-1,-1/2] (resp. on [1/2,1]), we have N=5.
 We obtain

    ℒ̃(Q)=[3,L_1,3,L_2,5,L_3,5,L_4,3,L_5 ,3]
 where


  - L_1=[2,[[0,0],[2,2],[1,1],[0,0]]]

  - L_2=[4,[[0,0],[1,1],[1,1],[0,2],[1,1],[0,0]]]

  - L_3=[2,[[1,0],[2,2],[2,2],[0,1]]]

  - L_4=[4,[[0,0],[1,1],[2,0],[1,1],[1,1],[0,0]]]

  - L_5=[2,[[0,0],[1,1],[2,2],[0,0]]]

For example the  list L_3 means that above α_3=0 there is
one asymptote going to -∞ at the left of α_3, then two singular points with two branches to the left and two branches to the right and one asymptote going to +∞ at the right of α_3.




A 
simple planar graph 
Gr(Q)
 can be obtained as follows, 


  * define d'=max(max_i=0,…, N m'_i,max_i=1,…,N m_i),

  * for each i=0,…, N include the points 
    I_i,j=(2i+1,j(d'+1)/m'_i+1)
 for j from 1 to m'_i,

  * for each   i=1,…, N include the points 
    P_i,j=(2i,j(d'+1)/m_i+1)
 for j from 0 to m_j+1,

  * include the points 
    P_-∞,j=(0,j(d'+1)/m'_0+1)
 for j from 1 to m'_0 as well as the points  
    P_+∞,j=(2(N+1),j(d'+1)/m'_N+1)
 for j from 1 to m'_N,

  * for i=1,…,N, add the segment I_i-1,ℓP_i,j (resp. P_i,jI_i,r) if 
    ∑_k=0^j-1Left_i,k<ℓ≤∑_k=0^jLeft_i,k (∑_k=0^j-1Right_i,k<r ≤∑_k=0^jRight_i,k)


  * add the segments P_-∞,jI_0,j for j=1,…, m'_0 and the segments
I_N,j P_∞,j for j=1,…, m'_N

    
It is clear that

Gr(Q)
⊂(0,2 N)× (0,d'+1)
is homemorphic to V_ℝ(Q)⊂ℝ^2.



We finally explain how to add vertical lines back.
We remind that c(X) is the gcd of all the coefficients c_i(X) of P(X,Y) written as an element of [X][Y]
and we consider the  square-free part c^⋆(X) of c(X).
 Define:


  * c_1(X):= gcd (c^⋆(X),D_X(X)) and c_2(X):=quo(c^⋆(X),c_1(X)), 

  * 𝒱_1 := {(x,y)∈ℝ^2 | c_1(x)=0} and 𝒱_2 := {(x,y)∈ℝ^2 | c_2(x)=0}. 

Hence 𝒱_1 is the subset of vertical lines of V_ℝ (P) passing through
zeroes of D_XX 
while 𝒱_2 is the subset of those passing between 
roots of D_X.
The computation of c_1(X) and c_2(X) has respectively bit complexities of (d^4 τ + d^5) and (dτ + d^2) according to Proposition <ref> and  Proposition <ref>.
To add back the lines in 𝒱_1 to V_ℝ (Q), it suffices to identify the real roots of c_1(X) as roots of D_X(X), i.e. to decide whether the vertical line defined by X=α_i belongs to V_ℝ(P). Such identification has bit complexity (d^5 τ + d^6) according to Proposition <ref>. To add back the lines in 𝒱_2 to V_ℝ (Q), it suffices to 
order the roots of c_2 and the roots of D_X. This has bit complexity (d^5 τ + d^6) according to Proposition <ref>.

 Let P ∈ [X, Y] 
 a non-zero
 square-free polynomial of total degree d
 and integer coefficients of bitsize bounded by τ. Adding back the vertical lines of V_ℝ (P) to V_ℝ (Q) has bit complexity (d^5 τ + d^6). 


For a complete combinatorial description of  the topology of V_ℝ(P) we define the  finite list 
    ℒ( P)=[N'_0,L'_1,…,L'_δ ,N'_δ]
 where


  - L'_i=[[m_i,w_i],[[ℓ_i,j,r_i,j], 0 ≤ j≤ m_i+1]]  for i=1,…,δ,

  - N'_i=[m'_i,v_i] for i=0,…,δ,

where w_i=1 if the line X=α_i belongs to  V_ℝ(P) for i=1,…, δ and  w_i=0 otherwise and v_i is the number of distinct vertical lines X=x with α_i<x<α_i+1 for i=1,…,δ-1  and v_0 (resp. v_δ) is the number of distinct vertical lines X=x with x<α_1 (resp. x>α_δ).
Finally the
simple  planar graph 
Gr(P)
is defined as 
    Gr(Q)∪⋃_i=1,…,δ w_i=1 V_i ∪⋃_i=0,…,δℓ=1,…,v_i V_i,ℓ

with V_i the vertical segment defined by X=2i, 0<Y<d'+1 and V_i,ℓ for i=0,…,δ,ℓ=1,…,v_i is the vertical segment  defined by the equation

    X=2i+2ℓ/v_i+1,0<Y<d'+1.



It is clear that

Gr(P)⊂(0,2δ)× (0,d'+1)
is homemorphic to V_ℝ(P)⊂ℝ^2.




Continuing Example <ref>,
we have 
three vertical lines of equation 

    X=-1/4,X=1/8,X=1/16

 We obtain

    ℒ(P)=[N'_0,L'_1,N'_1,L'_2,N'_2,L'_3,N'_3,L'_4,N'_4,L'_5 ,N'_5]
 where


  - N'_0=[3,0]

  - L_1=[[2,0],[[0,0],[2,2],[1,1],[0,0]]]

  - N_1=[3,0]

  - L_2=[[4,1],[[0,0],[1,1],[1,1],[0,2],[1,1],[0,0]]]

  - N_2=[5,0]

  - L_3=[[2,0],[[1,0],[2,2],[2,2],[0,1]]]

  - N_3=[5,2]

  - L_4=[[4,0],[[0,0],[1,1],[2,0],[1,1],[1,1],[0,0]]]

  - N_4=[3,0]

  - L_5=[[2,0],[[0,0],[1,1],[2,2],[0,0]]]

  - N_5=[3,0]





Finally, summarizing our results, we proved Theorem <ref>.



§ ACKNOWLEDGEMENTS

We are grateful to the anonymous referees for their relevant remarks and suggestions.



§ DATA SHARING

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

plain 


