# Sturm sequences

Sturm sequences for two polynomials are sequences of polynomials defined as follows

such that implies that for the first term such that and , we have , we. One can chose for instance

where is the remainder in the Euclidean division of a polynomial by , and is a positive number.

## The class computing the Sturm sequence

The corresponding class used to store the result is
template<class C, class UPOL=UPolDse<C>, class SEQ=std::vector<UPOL> >
SturmSeq

which is parameterised by

• C, the type of coefficients of the polynomials
• UPOL, the type of univariate polynomials. The default value is UPolDse<C>.
• SEQ, the type of the container used to store the sequence. The default value is std::vector<UPOL>.
Several scheme of construction of such type of sequences are available:

• EUCLIDEAN is the usual Sturm sequence where ,
• HABICHT is the Sturm Habicht sequence, which compute sub-resultants.
Here is an example of construction of a Sturm Habicht sequence of two polynomials:
UPolDse<ZZ> p,q; SturmSeq<ZZ> s(p,q,HABICHT());


• The euclidean construction requires coefficients coefficient in a field.
• The Sturm-Habicht construction can be applied with coefficients in a ring (for instance integers, univariate polynomials,...)
synaps/upol/SturmSeq.h

## Sign variations

int variation(const SturmSeq<C,UPOL,S>& s, const R& x)


• This function computes the number of sign variation of the sequence s at the value x.
• The number type used during this computation is R.
• It is based on the function UPOLDAR::sign_at.

## Example

#include <synaps/arithm/gmp.h>
#include <synaps/upol.h>
#include <synaps/upol/SturmSeq.h>
typedef UPolDse<ZZ> upol_t;

int main(int argc, char** argv)
{
upol_t p("x^3-234234*x^2+32332334554*x-12221118723");
SturmSeq<ZZ> s(p,diff(p),HABICHT());
std::cout<<s<<std::endl;
//| [1*x^3-234234*x^2334554*x-12221118723,3*x^2-468468*x+334554,
//|  109729126188*x+31626146871,-628213673160260696955282507]

std::cout <<"Number of positive root(s): "
<<variation(s,0)-variation(s,Infinity(1))<<std::endl;
//| Number of positive root: 1

std::cout <<"Number of negative root(s): "
<<variation(s,Infinity(-1))-variation(s,0)<<std::endl;
//| Number of negative root: 0
}


SYNAPS DOCUMENTATION