\magnification = 1200

\font\gordo=cmbx10 scaled \magstep2
\font\gordit=cmsl10 scaled \magstep2

\font\ninerm=cmr9
\font\nineit=cmti9
\font\ninebf=cmbx9
\font\ninesl=cmsl9

\def \chico {\let \bf=\ninebf
		\let \rm=\ninerm
		\let \it=\nineit
		\let \sl=\ninesl}


\font\sevenbf=cmbx7
\def \chico {\let \bf=\sevenbf}

\def \R{I\!\!R}
\def \Z{Z\!\!\!Z}
\def \N{I\!\!N}
\def \fin {\vrule height4pt width3pt depth2pt}
\overfullrule 0pt

{\obeyspaces \gdef {\ }}
\def\begintt{\begingroup \obeylines 
	    \obeyspaces \catcode`\^=12
             \baselineskip=0.8\baselineskip
             \ttraggedright }
\def\endtt{\endgroup}

\def \reng {\vskip0.5\baselineskip}
\def \rreng {\vskip\baselineskip}
\def \CS {{\it CALLING SEQUENCE:\ \ }}
\def \P {{\it PARAMETERS:\ \ }}
\def \EX {{\it EXAMPLES:\vskip0.5\baselineskip}}
\def \B {\itemitem{$\bullet\ \ $}}

\headline={\vbox{\leftline{\nineit IF \ninerm version 0.2 (january 1990)}
\hrule}}

\centerline {\bf A handout of \it IF}

\rreng
{\noindent \bf 1. An overview.}

\reng

{\it IF} is a package of MAPLE procedures designed for working with 
real algebraic numbers and solving systems of equations and inequalities.
 The general problem it solves is a certain kind of system of polynomial 
equations.

Let $P,Q_1,\ldots ,Q_k\in\Z[X]$. We shall call {\sl sign condition} over 
$Q_1,\ldots ,Q_k$ every $k$-tuple over $\{0,1,-1\}$. If $\epsilon =
(\sigma_1,\ldots ,\sigma_k)$ is a sign condition, we shall say it is 
{\sl satisfied} (w.r.t $P$) if the system

\reng

\hskip2cm $P(X)=0$

\hskip2cm $Q_1(X)\ \sigma_1$

\hskip2cm $\vdots$ \hskip8cm $(*)$

\hskip2cm $Q_k(X)\ \sigma_k$

\reng

\noindent has some solution. Moreover we shall denote by 
$c_\epsilon$ the number of solutions of $(*)$.

A very special case of system is the one given by 
the sequence $P,P^{(n-1)},\ldots ,
P'',P'$ where $n=$degree$_x(P)$. In this case it is a theorem that the 
number of satisfied sign conditions coincides with the number of real roots 
of $P$. So, each root of $P$ can be characterized by the signs it gives 
to the derivatives of $P$.
This fact is used to code (and further work with) real algebraic 
numbers.

The general purpose of {\it IF} is to solve systems like $(*)$ in the sense 
of computing the number of satisfied sign conditions and their corresponding 
$c_\epsilon$'s. In particular it codes real algebraic numbers. This purpose 
is achieved by succesive solving of linear equations and, since further work 
with a given result can be more quickly done if this linear algebraic 
information is provided (to avoid recomputations), we shall introduce a 
new data type that will be used as input and/or output in our procedures.

A {\sl Tarski data type} for $P,Q_1,\ldots ,Q_k$ 
is a list with the following form

$$[P,[R_1,\ldots ,R_r],[\epsilon_1,\ldots ,\epsilon_r],
[c_1,\ldots ,c_r],[v_1,\ldots ,v_r],A]$$
 where 
\reng

$P$ is a polynomial (called principal polynomial of the data),

$R_j$ are polynomials, 

$\epsilon_j$ are k-letters words over $\{$-1,0,1$\}$,
 
$c_j$ are in $\N$ 

$v_j$ are in $\N$ and $[v_1,\ldots ,v_r]$ is 
 an array, and 

$A$ is an $r\times r$ matrix over $\{0,-1,1\}$ such that
 $A\cdot c=v$.
 
\noindent Moreover $v_j=ss(P,P'*Rj)$ for each $j\leq r$
(see 2.12. below for the meaning of $ss$), the $\epsilon_j$ 
are the satisfied sign conditions for $Q_1,\ldots ,Q_k$ with respect to 
$P$ and the $c_j$ are the previously defined $c_{\epsilon _j}$.

\reng

When coding the roots of $P$ we are not interested in the sign conditions 
over ${\underline {\rm all}}$ the derivatives of $P$. We are just interested in 
separating these roots and in fact, the lesser derivatives we need the 
faster the algorithm will run. So, we will stop the computations  
once we have the roots separated in groups of at most two of them, and we 
shall use the first derivative to finish the task. In order to indicate it, 
a sign condition of the form

$$[\sigma_1,\ldots ,\sigma_r,HASH,\sigma']$$
will denote signs $\sigma_j$ for $P^{(n-j)},$ $1\leq j\leq r$ 
and $\sigma'$ for $P'$. So, for instance, the three roots of $x^5-
2x^4-x+2$ are coded by $[[1,HASH,1],[-1,HASH,1],[1,HASH,-1]]$ and the two 
of $x^4-1$ by $[[HASH,1],[HASH,-1]]$.

As an application of these ground procedures, the {\tt cad} procedure 
computes a cylindrical algebraic decomposition of a plane algebraic 
curve.
\rreng

{\noindent\bf 2. The instructions.}

\reng

The statements in {\it IF} have the general

{\it SYNTAX:} $<$function$>$(args)

\reng

\B 
The functions available are:

\begingroup
\settabs 4 \columns


\+cad
&difvar 
&mark
&nroots\cr
\+position
&ran
&ransi
&ransort\cr
\+SI
&sqfran
&sqfree
&ss\cr
\+sth
&unmark
&var\cr

\endgroup

\rreng

{\noindent\bf 2.1. cad - computes a cylindrification of a real algebraic 
plane curve.}
\reng

\CS cad($F$);

\P $F$ - a bivariate polynomial with integer coefficients.

\B cad($F$) returns a list of the form $[\{b_1\},p_1,\{b_2\},\ldots,
p_n,\{b_{n+1}\}]$ that represents a cylindrification of the curve.

\B the procedure choices a projection direction looking for a variable 
with respect to which the leading coefficient is constant; in case this is 
not possible an error message is returned, otherwise a message with the 
choosen direction is printed.

\EX
\begintt
\catcode`\{=12
\catcode`\}=12

cad((x^2+y^2)*(x^2+y^2-1)); \qquad \bgroup\rm yields\egroup
\hbox\bgroup\egroup
\hbox\bgroup\egroup
                         the projection direction is, y
\hbox\bgroup\egroup
\hbox\bgroup\egroup
                         [{0}, 1, {2}, 3, {2}, 1, {0}]
\hbox\bgroup\egroup
\hbox\bgroup\egroup
\hbox\bgroup\egroup
cad(y^2-x^3+x^2); \qquad \bgroup\rm yields\egroup
\hbox\bgroup\egroup
\hbox\bgroup\egroup
                         the projection direction is, y
\hbox\bgroup\egroup
\hbox\bgroup\egroup
                             [{0}, 1, {0}, 1, {2}]
\endtt
\rreng

{\noindent\bf 2.2. difvar - calculates de difference of sign variations in 
$-\infty$ and
 $+\infty$ of a sequence  of polynomials.}

\reng

\CS difvar($x,s$);

\P $x$ - a variable

\hskip3cm $s$ - a sequence of polynomials in $x$ with integer coefficients

\B difvar($x,s$) returns the difference of sign variations in $-\infty$ and
 $+\infty$ of the sequence $s$ of polynomials.

\EX 

\begintt 

difvar(x,x^4-4*x^3-12*x^2+7*x-8,2*x^3-16*x^2+7*x-5,
\hbox{}
\hbox{}
     -11*x^2+3*x-2,-43*x+5,-122); \qquad {\rm yields}        2
\endtt

\rreng

{\noindent\bf 2.3. mark - mark a Tarski data type.}
\reng

\CS mark($T$);

\P $T$ - a Tarski data type.

\B mark($T$) returns a new Tarski data type that coincides with 
the input but whose signs tuples are numbered.

\EX
Let $T$ be the output of the exemple given in 2.9.

\begintt
\hbox{}
mark(T); \qquad {\rm yields}
\hbox{}
      5      4    3      2               3      2         5    3   
  [2 x  + 2 x  - x  + 3 x  - 6 x, [1, 3 x  - 5 x  + 1, 2 x  - x ], 
\hbox{}
\hbox{}
   [[1, 1, 0, -1], [2, -1, 1, -1], [3, -1, -1, -1]], [1, 1, 1], VF, C]
\hbox{}
\endtt
\rreng

{\noindent\bf 2.4. nroots -  computes the number of different real roots of 
a polynomial.}

\reng

\CS nroots($p$);

\P $p$ - a univariated polinomial with integer coefficients

\B nroots($p$) returns the number of different real roots of the 
polynomial $p$.

\EX
\begintt 

nroots(x^2-1); \qquad {\rm yields}    2\endtt

\begintt 
\hbox{}
nroots((x^2-1)*(x^2-3*x+2)); \qquad {\rm yields}    3\endtt
\rreng

{\noindent\bf 2.5. position - find the position of sign tuple in a 
Tarski data type.}

\reng

\CS position($t,T$);

\P $t$ - a sign tuple.

\hskip 2.8cm $T$ - a Tarski data type.

\B position($t,T$) returns the position the tuple $t$ has in the list 
of sign tuples of $T$. In case $t$ is not found in $T$, the procedure 
returns 0.

\EX
Let $T$ the output of the first example given in 2.10

\begintt
\hbox{}
position([-1,HASH,1],T); \qquad {\rm yields}          2
\endtt
\rreng

{\noindent\bf 2.6. ran - codes the roots of a polynomial.}

\reng

\CS ran($p,nder$);

\P $p$ - a polynomial with integer coefficients.

\hskip2.8cm nder - (optional) unevaluated name

\B ran($p$) returns a Tarski data type that codes the roots of $p$  
 following the signs given  by those roots to the derivatives of $p$.

\B the third element of the output contains the coding of the roots:
if it is equal to $[[]]$ the polynomial has just one root and no sign 
on the derivatives is needed to separate it from the others, if it is 
equal to $[]$ the polynomial has no root.

\B if a second argument is present, it will be assigned the number 
of derivatives used in the coding.

\EX
\begintt 
ran(2*x^5-2*x+x^4-1,nder); \qquad {\rm yields}
\hbox{}
      5          4                       4          3   
  [2 x  - 2 x + x  - 1, [1, 10 x + 1, 5 x  - 1 + 2 x ], 
\hbox{}
\hbox{}
   [[1, 1, 1, 1], [-1, 1, -1, 1], [-1, 1, -1, -1]], [1, 1, 1], VF, C]
\hbox{}
\hbox{}
\hskip1cm {\rm where}
\hbox{}
  VF=array ( 1 .. 3, 

\hskip2cm                               [3, -1, 1]

\hskip4cm )

  C=array ( 1 .. 3, 1 .. 3, 

\hskip2cm                               [1, 1, 1]

\hskip2cm                              [1, -1, -1]

\hskip2cm                               [1, 1, -1]

  )
\hbox{}
nder; \qquad {\rm yields}      4
\endtt
\rreng

{\noindent\bf 2.7. ransi - computes the sign of given polynomials over 
the roots of another one.}

\reng

\CS ransi($T,s$);

\P $T$ - a Tarski data type obtained as an output of ran, sqfran or SI.

\hskip2.8cm $s$ - a sequence of polynomials with integer coefficients

\B ransi($T,s$) returns a Tarski data type with the information 
about the signs taken by the polynomials of $s$ over the roots coded 
by $T$.

\B an error can occurs if $T$ is not the output of ran, sqfran or SI, 
i.e. if $T$ is not a Tarski data type corresponding to the coding 
of the roots of a polynomial.

\EX
Let $T$ be the output of the first example given in 2.10.,

\begintt 
\hbox{}
ransi(T,2*x^2-1,1-3*x); \qquad {\rm yields}
\hbox{}
      5          4                        4          3   
  [2 x  - 2 x + x  - 1, [1, 10 x + 1, 10 x  - 2 + 4 x ], 
\hbox{}
\hbox{}
   [[1, HASH, 1, 1, -1], [-1, HASH, 1, 1, 1], [-1, HASH, -1, -1, 1]], 
\hbox{}
\hbox{}
   [1, 1, 1], VF, NA]
\hbox{}
\endtt

where {\tt VF} and {\tt NA} coincide with those of $T$.
\rreng

{\noindent\bf 2.8. ransort - sorts the real roots of a polynomial.}

\reng

\CS ransort($T$);

\P $T$ - a Tarski data type obtained as an output of ran or sqfran.

\B ransort($T$) sorts the real roots of the main polynomial of $T$.

\B an error can occurs if $T$ is not the output of ran, i.e. if $T$ 
is not a Tarski data type corresponding to the coding of the roots of 
a polynomial.

\EX

Let $T$ be the output of the second example given in 2.10.,

\begintt
\hbox{} 
ransort(T); \qquad {\rm yields}
\hbox{}
\hbox{}
  [[-1, 1, 0, -1, -1, HASH, -1], [0, -1, 0, 0, -1, HASH, 1], 
\hbox{}
\hbox{}
   [1, 1, 0, -1, -1, HASH, -1], [1, 1, 1, 1, -1, HASH, 1], 
\hbox{}
\hbox{}
   [1, 1, 1, 1, 1, HASH, -1], [1, 1, 1, 1, 1, HASH, 1]]
\hbox{}
\endtt

\rreng


{\noindent \bf 2.9. SI - solves systems of simultaneous equations and 
inequalities.}

\reng

\CS SI($p,s$); 

\P $p$ - a polinomial with integer coefficients

\hskip2.8cm $s$ - a sequence of polynomials with integer coefficients

\B SI($p,s$) returns a Tarski data type with the satisfied sign 
 conditions for the elements of $s$ on the roots of $p$.

\EX

\begintt 
SI(2*x^5+2*x^4-x^3+3*x^2-6*x,3*x^3-5*x^2+1,2*x^5-x^3,2*x^3-4*x^2+x-2);
\hbox{}
\hbox{}
        \qquad {\rm yields}
\hbox{}
\hbox{}
      5      4    3      2               3      2         5    3   
  [2 x  + 2 x  - x  + 3 x  - 6 x, [1, 3 x  - 5 x  + 1, 2 x  - x ], 
\hbox{}
\hbox{}
   [[1, 0, -1], [-1, 1, -1], [-1, -1, -1]], [1, 1, 1], VF, C]
\hbox{}
\hbox{}
\qquad {\rm where} 
\hbox{}
VF=array ( 1 .. 3, 

\hskip2cm                                   [3, -1, 0]

\hskip4cm)

C=array ( 1 .. 3, 1 .. 3, 

\hskip2cm                                   [1, 1, 1]

\hskip2cm                                  [1, -1, -1]

\hskip2cm                                   [0, 1, -1]

  )
\endtt


\rreng

{\noindent\bf 2.10. sqfran - codes the roots of a square--free polynomial.}

\reng

\CS sqfran($p$,nder);

\P $p$ - a polynomial with integer coefficients.

\hskip2.8cm nder - an unevaluated name.

\B ran($p$) returns a Tarski data type that codes the roots of $p$  
 following the signs given  by those roots to the derivatives of $p$.

\B the procedure makes $p$ square--free in case $p$ is not. Moreover, 
once the roots are separated in groups of at most two roots, the 
first derivative is used (maybe skipping some others) to finish the task.

\B if a second argument is present, it will be assigned the number 
of derivatives used in the coding.

\EX
\begintt
sqfran(2*x^5-2*x+x^4-1,nder); \qquad {\rm yields}
\hbox{}
\hbox{}
       5          4                        4          3   
   [2 x  - 2 x + x  - 1, [1, 10 x + 1, 10 x  - 2 + 4 x ], 
\hbox{}
\hbox{}
      [[1, HASH, 1], [-1, HASH, 1], [-1, HASH, -1]], [1, 1, 1], VF, C]
\hbox{}
{\rm where}
\hbox{}
  VF=array ( 1 .. 3, 

\hskip2cm                                   [3, -1, 0]

\hskip4cm)

  C=array ( 1 .. 3, 1 .. 3, 

\hskip2cm                                   [1, 1, 1]

\hskip2cm                                  [1, -1, -1]

\hskip2cm                                   [0, 1, -1]

  )
\hbox{}
nder; \qquad {\rm yields}        2
\hbox{}
\hbox{}
sqfran(x*(x^9-15*x^7-1953*x^4+10940*x^3-11655*x^2-10926*x+13608));
\hbox{}
\hbox{}
      \qquad {\rm yields}
\hbox{}
\hbox{}
     9       7         4          3          2                     
[x (x  - 15 x  - 1953 x  + 10940 x  - 11655 x  - 10926 x + 13608), 
\hbox{}
\hbox{}
           2   3          5       3       
   [1, x, x , x  - x, 12 x  - 40 x  - 93, 
\hbox{}
\hbox{}
       9       7         4          3          2                  
      x  - 15 x  - 1953 x  + 10940 x  - 11655 x  - 10926 x + 13608
\hbox{}
\hbox{}
                 8        6         3          2                     
         + x (9 x  - 105 x  - 7812 x  + 32820 x  - 23310 x - 10926)],
\hbox{}
\hbox{}
   [[1, 1, 1, 1, 1, HASH, 1], [0, -1, 0, 0, -1, HASH, 1], 
\hbox{}
\hbox{}
      [1, 1, 1, 1, -1, HASH, 1], [1, 1, 1, 1, 1, HASH, -1], 
\hbox{}
\hbox{}
      [1, 1, 0, -1, -1, HASH, -1], [-1, 1, 0, -1, -1, HASH, -1]],
\hbox{}
\hbox{}
   [1, 1, 1, 1, 1, 1], VF, C]
\hbox{}
  {\rm where}
\hbox{}
  VF=array ( 1 .. 6, 

\hskip2cm                                   [6, 3, 5, 3, -2, 0]

\hskip4cm)

  C=array ( 1 .. 6, 1 .. 6, 

\hskip2cm                                   [1, 1, 1, 1, 1, 1]

\hskip2cm                                   [1, 0, 1, 1, 1, -1]

\hskip2cm                                   [1, 0, 1, 1, 1, 1]

\hskip2cm                                   [1, 0, 1, 1, 0, 0]

\hskip2cm                                   [1, -1, -1, 1, -1, -1]

\hskip2cm                                   [1, 1, 1, -1, -1, -1]

  )
\endtt
\rreng

{\noindent\bf 2.11. sqfree - computes the square--free part of a polynomial.}

\reng

\CS sqfree($p$);

\P $p$ - a polynomial with integer coefficients.

\B sqfree($p$) returns the square--free part of $p$.

\EX
\begintt
sqfree(x^3-x^2-x+1,x); \qquad {\rm yields}
\hbox{}
\hbox{}
                                      2    
                                     x  - 1

\endtt
\rreng
  
{\noindent\bf 2.12. ss - calculates the difference of sign variation in 
$-\infty$ and
 $+\infty$ of the Sturm-Habicht sequence of two polynomials.}

\reng

\CS ss($p,q$);

\P $p,q$  - polynomials in one indeterminate

\B This function computes the difference of sign variation in $-\infty$ and
 $+\infty$ of the Sturm-Habicht sequence associated to $p$ and $q$ 

\EX 
\begintt 
\hbox{}
ss(x^4+3*x^3-12*x^2+5*x-8,2*x^3-6*x^2+7*x-5);\qquad {\rm yields} 
\hbox{}
                              2
\endtt

\rreng 

{\noindent\bf 2.13. sth -  computes the Sturm-Habicht sequence associated 
to two polynomials p and q with respect to the variable x.}

\reng

\CS sth($p,q,x$);

\P $p,q$ - polynomials

\hskip3cm $x$ - main variable

\B The call to sth computes the Sturm-Habicht sequence (excluding 
the eventually null polynomials) associated to p and q with respect 
to the variable x.

\EX
\begintt
\hbox{} 
sth(x^4+3*x^3-12*x^2+5*x-8,2*x^3-6*x^2+7*x-5,x); \qquad {\rm yields}
\hbox{}
   4      3       2               3      2                  2              
  x  + 3 x  - 12 x  + 5 x - 8, 2 x  - 6 x  + 7 x - 5, - 10 x  + 54 x 
\hbox{}
\hbox{}
  - 28, - 683 x + 461, -18157
\endtt
\rreng

{\noindent\bf 2.14. unmark - unmark a Tarski data type.}

\reng

\CS unmark($T$);

\P $T$ - a marked Tarski data type.

\B unmark($T$) undoes the work of mark, taking away the numbers 
that number the sign tuples of $T$.

\B an ERROR occurs if $T$ is not marked.

\EX
Let $T$ the marked Tarski data type obtained in example 2.3.

\begintt
\hbox{}
unmark(T) \qquad {\rm yields}
\hbox{}
\hbox{}
      5      4    3      2               3      2         5    3   
  [2 x  + 2 x  - x  + 3 x  - 6 x, [1, 3 x  - 5 x  + 1, 2 x  - x ], 
\hbox{}
\hbox{}
   [[1, 0, -1], [-1, 1, -1], [-1, -1, -1]], [1, 1, 1], VF, C]
\hbox{}
\endtt
\rreng

{\noindent\bf 2.15. var -  returns the number of sign variations of a sequence.}

\reng

\CS var($s$);

\P $s$ - a sequence of integer numbers

\B var($s$) returns the number of sign variations of the sequence resulting 
of throwing away the zeroes of $s$.

\EX
\begintt 
\hbox{}
var(1,3,-2,0,2,-1); \qquad {\rm yields}         3
\endtt

\bye
