Gregor Kemper

COMPUTING QUOTIENTS BY CONNECTED SOLVABLE GROUPS

Keywords: 2010 Mathematics Subject Classification. 14L24, 13A50, 14L30 Algorithmic invariant theory, solvable groups, geometric invariant theory, geometric quotient. 1. Geometric overture: excellent quotients X

Consider an action of a connected solvable group G on an affine variety X. This paper presents an algorithm that constructs a semi-invariant f ∈ K[X] =: R and computes the invariant ring (R f ) G together with a presentation. The morphism X f → Spec (R f ) G obtained from the algorithm is a universal geometric quotient. In fact, it is even better than that: a so-called excellent quotient. If R is a polynomial ring, the algorithm requires no Gröbner basis computations. If R is a complete intersection, then so is (R f ) G .

Introduction

In the theory of algebraic groups, two cases stand out as being well understood: reductive groups and solvable groups. While the invariant theory of reductive groups is well-behaved and, in many aspects, well understood, this is not the case for solvable and, in particular, unipotent groups. For example, invariant rings of unipotent groups need not be finitely generated, and even if they are, categorical quotients need not exist (see Ferrer Santos and Rittatore [START_REF] Walter | Actions and invariants of algebraic groups[END_REF]Example 4.10]). Notice that if G is a connected linear algebraic group acting on an affine variety X and B is a Borel subgroup, then K[X] G = K[X] B (see Humphreys [START_REF] Humphreys | Linear Algebraic Groups[END_REF]Exercise 21.8]); so computing invariant rings of connected solvable groups would mean computing invariant rings of all connected groups. This goal is still out of reach, but it makes the invariants of connected solvable groups particularly interesting.

There is a sizeable list of papers devoted to the invariant theory of the additive group (e.g. Tan [START_REF] Tan | An algorithm for explicit generators of the invariants of the basic Ga-actions[END_REF], van den Essen [START_REF] Van Den Essen | An Algorithm to Compute the Invariant Ring of a Ga-Action on an Affine Variety[END_REF], Freudenburg [START_REF] Freudenburg | Algebraic theory of locally nilpotent derivations[END_REF], Derksen and Kemper [3, Section 3.1], and Tanimoto [START_REF] Tanimoto | An algorithm for computing the kernel of a locally finite iterative higher derivation[END_REF]), unipotent groups (e.g. Hochschild and Mostow [START_REF] Hochschild | Unipotent groups in invariant theory[END_REF], Grosshans [START_REF] Grosshans | The invariants of unipotent radicals of parabolic subgroups[END_REF], Fauntleroy [START_REF] Fauntleroy | Geometric invariant theory for general algebraic groups[END_REF][START_REF] Fauntleroy | Invariant theory for linear algebraic groups. II. (char k arbitrary)[END_REF], Bérczi et al. [START_REF] Bérczi | Geometric invariant theory for graded unipotent groups and applications[END_REF], Greuel and Pfister [START_REF] Greuel | Geometric quotients of unipotent group actions[END_REF][START_REF] Greuel | Geometric quotients of unipotent group actions II[END_REF], and Sancho de Salas [START_REF] Salas | Invariant theory for unipotent groups and an algorithm for computing invariants[END_REF]), and connected solvable groups (Rosenlicht [19,Section 4] and Popov [START_REF] Vladimir | Birational splitting and algebraic group actions[END_REF]). Most relevant in our context is the recent paper [START_REF] Vladimir | Birational splitting and algebraic group actions[END_REF], in which it is shown that if a connected solvable group G acts on an irreducible variety X over an algebraically closed field K, then X has a G-stable dense open subset U ⊆ X that admits a geometric quotient U → Y such that, in addition, there is an isomorphism U ∼ --→ A r,s ×Y , with A r,s = {(ξ 1 , . . . , ξ r+s )

∈ A r+s | ξ 1 • • • ξ s = 0}, such that the diagram U ∼ E A r,s × Y d d d © pr 2 Y
(with pr 2 the second projection) commutes. This result is nonconstructive, mainly since Rosenlicht's general result [START_REF] Rosenlicht | A Remark on Quotient Spaces[END_REF] about geometric quotients on suitable open subsets is used for obtaining a geometric quotient.

The main goal of this paper is to make Popov's result constructive, and to show that the computations required for this are exceptionally easy. Under the assumption that G is a connected solvable group acting on an irreducible affine variety X, our algorithm constructs a suitable nonzero semi-invariant f in the coordinate ring R := K[X] and computes the invariant ring (R f ) G together with a presentation, such that the induced map from U = X f := {x ∈ X | f (x) = 0} to Y := Spec (R f ) G satisfies Popov's result. All that is required for the algorithm are arithmetic operations and zero recognition in R. So for example if X = A n , the algorithm does not need any Gröbner basis computations. It turns out that U → Y is even a universal geometric quotient. The relations between the generators of (R f ) G computed by the algorithm reveal that (R f ) G is a complete intersection if R is one, for example in the case X = A n . This result seems to be new.

The paper starts by studying quotients of a type modeled after the above-mentioned result by Popov [START_REF] Vladimir | Birational splitting and algebraic group actions[END_REF] (and also the one by Greuel and Pfister [START_REF] Greuel | Geometric quotients of unipotent group actions[END_REF] on unipotent group actions), which we propose to call excellent quotients. Since connected solvable groups are built from copies of additive and multiplicative groups, Sections 2 and 3 treat actions of these groups. The results lead to algorithms for computing excellent quotients, which are then put together in the final section to obtain an algorithm for a connected solvable group. A difficulty with this iterative approach is that when computing the invariant ring (R f ) H of a normal subgroup H ⊆ G, the element f must be chosen as a semi-invariant of G, not just of H, since otherwise G does not act on (R f ) H .

An extended preprint version of this article has appeared in the arXiv [START_REF] Kemper | Quotients by Connected Solvable Groups[END_REF]. In that version, K need not be an algebraically closed field but can be any ring. The irreducibility hypothesis on X is also dropped: it can be any affine K-scheme. The preprint [START_REF] Kemper | Quotients by Connected Solvable Groups[END_REF] is more than twice as long as this paper, and there is no intention of publishing it anywhere else than in the arXiv.

In the following, all varieties and algebraic groups are assumed to be over an algebraically closed field K. Let G be an algebraic group acting morphically on a variety X. We say that a morphism X → Y to another variety is an excellent quotient if (i) X → Y is a universal geometric quotient (see

X ∼ E F × Y d d d © pr 2

Y

(with pr 2 the second projection) commutes. If we wish to be more specific, we will call X → Y an excellent quotient by G with fibers F .

It follows immediately that all G-orbits in X are isomorphic to F . By picking a point from F we obtain a morphism Y → F × Y , and composing this with F × Y ∼ --→ X provides a morphism Y → X, which we call a cross section since the composition Y → X → Y is the identity.

An excellent quotient can be defined for schemes (over an arbitrary ground scheme S instead of an algebraically closed field). In this case the existence of an S-valued point of F is required for obtaining a cross section. Everything in this section carries over to the scheme-theoretic setting (see [START_REF] Kemper | Quotients by Connected Solvable Groups[END_REF]).

Recall that the definition of a geometric quotient in [START_REF] Mumford | Geometric Invariant Theory[END_REF] has four parts and is a bit cumbersome. But as the following result shows, the presence of a cross section makes it much easier to check whether the quotient is (universally) geometric, especially if X and Y are affine. Proposition 1.1. Let G be an algebraic group acting on an affine variety X and let X → Y be a morphism to an affine variety Y with a cross section Y → X. Then X → Y is a universal geometric quotient if and only if (a) the composition

G × Y → G × X act
--→ X (with the last map given by the G-action) is surjective, and (b) for every homomorphism K[Y ] → A of rings we have

(A ⊗ K[Y ] K[X]) G = A (which implies K[X] G = K[Y ]).
Since the image of the cross section meets every fiber of X → Y in precisely one point, (a) says that the fibers of X → Y are precisely the G-orbits.

Proof. Let us first assume that (a) and (b) hold. Then K

[X] G = K[Y ] implies that the diagram G × X act E X pr 2 c c X E Y commutes. Let Y → Y
Y → O X of sheaves, so Γ(V, O Y ) → Γ(U, O X ) is injective.
This means that an f ∈ Γ(U, O X ) has at most one inverse image in Γ(V, O Y ), and such an inverse image can be glued together from inverse images of restrictions of f to preimages of affine open subsets of V . We may therefore assume V to be affine, say

V = Spec(A). Since U = V × Y X, this implies U = Spec A ⊗ K[Y ] K[X] . The map X = Y × Y X → Y
is just the first projection, so U → V is also the first projection, and it follows that

A = Γ(V, O Y ) → Γ(U, O X ) = A ⊗ K[Y ] K[X] maps an a ∈ A to a ⊗ 1. Hence the image is A ⊗ 1, which by (b) is equal to (A ⊗ K[Y ] K[X]) G = Γ(U, O X ) G . This completes the proof that X → Y is a universal geometric quotient.
Conversely, if X → Y is a universal geometric quotient, then (a) follows since the fibers are the orbits, and (b) is true since, as we have seen, it says that for all affine schemes Y with morphisms

Y → Y , the map Γ(Y , O Y ) → Γ(X , O X ) has Γ(X , O X ) G as its image.
We will deal with solvable groups by iterating excellent quotients along a chain of subgroups. This is possible thanks to the following result.

Theorem 1.2. Let G be an algebraic group acting morphically on an affine variety X. Let quo 1 : X → Y be an excellent quotient by a closed normal subgroup H ⊆ G with fibers F 1 , with Y affine. Since G acts on K[X] H = K[Y ], it also acts on Y , with H in the kernel of the action. Assume that Y admits an excellent quotient quo 2 : Y → Z by G with fibers F 2 , again with Z affine. Then the composition quo 2 • quo 1 : X → Z is an excellent quotient by G with fibers

F 1 × F 2 .
Remark. The theorem also holds without assuming that X, Y or Z are affine (see [START_REF] Kemper | Quotients by Connected Solvable Groups[END_REF]). But we only need the affine case here, whose proof is less involved.

Proof of Theorem 1.2. The commutative diagram Z shows that the second property (ii) of an excellent quotient is satisfied. Composing cross sections sect 1 : Y → X and sect 2 : Z → Y gives a cross section sect := sect 1 • sect 2 of X → Z. Since (a) and (b) of Proposition 1.1 hold for the quotients quo 1 and quo 2 , we have to show that they also hold for the composition.

To prove (a), let x ∈ X and set y := quo 1 (x), z := quo 2 (y). We must show that x and x := sect(z) lie in the same G-orbit. There exists g ∈ G such that y = g sect 2 (z) . Since quo 1 is G-equivariant, we obtain quo 1 g(x ) = g quo 1 sect 1 (sect 2 (z)) = g sect 2 (z) = y = quo 1 (x), so g(x ) and x lie in the same H-orbit, and we are done.

To prove (b), let

K[Z] → A be a ring homomorphism. Then (A ⊗ K[Z] K[Y ]) G = A. Moreover, applying (b) to the induced homomorphism K[Y ] → A ⊗ K[Z] K[Y ] yields (A ⊗ K[Z] K[X]) H = (A ⊗ K[Z] K[Y ] ⊗ K[Y ] K[X]) H = A ⊗ K[Z] K[Y ], so (A ⊗ K[Z] K[X]) G = (A ⊗ K[Z] K[Y ]) G = A.

Additive group actions

In this section we consider a nontrivial morphic action of the additive group G a on an irreducible affine variety X. Again, we work over an algebraically closed field K and remark that everything from this section carries over to the situation where X is an integral affine scheme over Spec(K) with K a ring (see [START_REF] Kemper | Quotients by Connected Solvable Groups[END_REF]).

With R := K[X], the action is given by a homomorphism ϕ: R → R[z] of K-algebras, with z an indeterminate. For s ∈ R with ϕ(s)

= d i=0 c i z i with c d = 0, we write deg(s) := d. We have c 0 = s and deg(c i ) d -i (2.1)
(see Tanimoto [START_REF] Tanimoto | An algorithm for computing the kernel of a locally finite iterative higher derivation[END_REF]), and in particular c d ∈ R Ga is an invariant. Following Tanimoto and various other authors, we call s a local slice if it is of minimal positive degree. We call c := c d the denominator of the local slice. This is because we can perform division with remainder by ϕ(s)

over the localization R c := R[c -1 ]: Extending ϕ to R c , for a ∈ R c we have ϕ(a) = g • ϕ(s) + r (2.2) with g, r ∈ R c [z], deg z (r) < d. Crucially, it follows from [24, Lemma 2.2] that deg z (g) = deg g(0) and deg z (r) = deg r(0) , so deg g(0) < deg(a), deg z (r) = 0 and r ∈ R Ga (2.3)
since s is a local slice. Sancho de Salas [22, Section 3] and Tanimoto [24, Section 3] presented essentially identical algorithms for computing a local slice. These use division with remainder as above, and only require addition, multiplication and zero recognition in R; so if R is, for example, a finitely generated subalgebra of a rational function field, a local slice can be computed without any Gröbner basis calculations. A variant of these algorithms that works in a more general situation and is also a bit simpler can be found in [START_REF] Kemper | Quotients by Connected Solvable Groups[END_REF].

The utility of local slices can be seen from the following theorem. For example, by part (b), generators of R Ga c can be determined immediately if a local slice is known. Moreover, together with Proposition 1.1, parts (a), (c), and (d) imply that the map

X c := {x ∈ X | c(x) = 0} → Spec(R Ga c
) is an excellent quotient with fibers A 1 . While parts (a) and (b) are essentially well known, (c) and (d) seem to be new.

- -→ R Ga c [x] x →0 ---→ R Ga c is a homomorphism of R Ga c -algebras with ker(π) = sR c . In particular, π is surjective. For a ∈ R c , π(a) is given by ϕ(a) = g • ϕ(s) + π(a) as in (2.2). (c) The composition R c ϕ -→ R c [z] π -→ R Ga c [z] (with π applied coefficient-wise) is injective and makes R Ga c [z] into an R c -module that is generated by d elements. In particular, if d = 1, then it is an isomorphism. (d) Let A be a ring with a homomorphism R Ga c → A. Then (A ⊗ R Ga c R) Ga = A Proof. (a) To show that the map is injective, let f ∈ R Ga c [x] with f (s) = 0. Since ϕ is a homomorphism of R Ga c -algebras, this implies f (ϕ(s)) = 0, so f = 0. To prove surjectivity, let a ∈ R c . Evaluating (2.2) at z = 0, we get a = g(0)s + r(0), and (2.3) yields r(0) = r ∈ R Ga c . Since also deg g(0) < deg(a)
, the surjectivity follows by induction on deg(a). (b) The first statement follows from (a). For the second statement, observe that the map that is claimed to be equal to π is a homomorphism of R Ga c -algebras, since the remainder of ϕ(a) from division by ϕ(s) has degree 0 by (2.3)

. Since R c = R Ga c [s]
, it suffices to check the equality of the maps for a = s, which is immediate. (c) Let a ∈ R c . By (a) we may write

a = f (s) with f ∈ R Ga c [x]. Writing g := ϕ(s) we obtain π ϕ(a) = π ϕ f (s) = f π(g) = f π(g -s) + π(s) = f (g -s)
since π(s) = 0 and, by (2.1), all coefficients of g -s have degree < d and are therefore invariants in R Ga c . Since g -s ∈ R c [z] is nonconstant, injectivity of π • ϕ follows. For a = s, the above equality shows that g -s lies in the image of π • ϕ. So the polynomial

(g(x) -s) -(g -s) ∈ R Ga c [z][x]
, which is satisfied by z, has coefficients (as a polynomial in x) in the image. This proves the second statement. (d) By (a), the element 1 Ga , then k = 0 and therefore r ∈ A ⊗ 1, which we wrote as A in the statement (d). The reverse inclusion A ⊗ 1 ⊆ (R ) Ga is clear.

⊗ s ∈ A ⊗ R Ga c R := R is algebraically independent over A, and R = A[1 ⊗ s]. By definition, (R ) Ga = ker(ϕ -id) with ϕ : R → R [z] obtained by tensoring ϕ. Let r ∈ R and write r = k i=0 a k (1 ⊗ s) i with a i ∈ A, a k = 0. With the given map η: R Ga c → A applied to R Ga c [z] coefficient-wise, we obtain ϕ (r) = k i=0 a i (1 ⊗ g) i = k i=0 a i η(g -s) ⊗ 1 + 1 ⊗ s i . If k > 0, the coefficient of z kd of this is a k η(c) k ⊗1, which is nonzero since η(c) is invertible in A. So if r ∈ (R )
The aim of the following simple example is to illustrate how Theorem 2.1 can be used to compute the invariant ring R Ga c , providing an excellent quotient. The example will be continued in Section 4.

Example 2.2. SL 2 -actions on binary forms are a staple of classical invariant theory. Here we consider the action of the upper unipotent subgroup G a ⊆ SL 2 (C) on binary forms of degree 2.

Explicitly, α ∈ G a acts on X = C 3 by the matrix

1 α α 2 0 1 2α 0 0 1 . With R = C[a 1 ,
a 2 , a 3 ] the trivariate polynomial ring, the action is given by the homomorphism ϕ:

C[a 1 , a 2 , a 3 ] → C[a 1 , a 2 , a 3 ][z] with ϕ(a 1 ) = a 1 + za 2 + z 2 a 3 , ϕ(a 2 ) = a 2 + 2za 3 , ϕ(a 3 ) = a 3 .
(2.4)

Clearly s = a 2 is a local slice of degree 1 with denominator c = a 3 . We have g = ϕ(s) = 2a 3 z +a 2 , so by the last statement from Theorem 2.1(b), the projection π:

C[a 1 , a 2 , a ±1 3 ] → C[a 1 , a 2 , a ±1 3 ]
Ga is given by first applying ϕ and then substituting z = -a2 2a3 . We obtain

π(a 1 ) = a 1 - a 2 2a 3 a 2 + a 2 2 4a 2 3 a 3 = 4a 1 a 3 -a 2 2 4a 3 , π(a 2 ) = 0, π(a 3 ) = a 3 .
Theorem 2.1 now tells us that

C[a 1 , a 2 , a ±1 3 ] Ga = C[a 2 2 -4a 1 a 3 , a ±1 3 ], (2.5)
and that the morphism

X c = C 2 × C × → C × C ×
given by evaluating the discriminant a 2 2 -4a 1 a 3 and a 3 is an excellent quotient with fibers A 1 . It is elementary to verify that the fibers of this map are indeed the G a -orbits.

In this example, an easy argument infers from (2.5) that the nonlocalized invariant ring is

C[a 1 , a 2 , a 3 ] Ga = C[a 2 2 -4a 1 a 3 , a 3 ]. But the corresponding morphism C 3 → C 2
is not a geometric quotient. In fact, the fiber of a point (δ, 0) ∈ C 2 consists of two orbits if δ = 0, and infinitely many if δ = 0.

Multiplicative group actions

This section deals with an action of the multiplicative group G m on an irreducible affine variety X. With R := K[X] as above, such an action is given by a homomorphism ϕ: R → R[t ±1 ] into the Laurent polynomial ring. An element c ∈ R is called a semi-invariant of weight k if ϕ(c) = t k c. In this case ϕ uniquely extends to a homomorphism R c → R c [t ±1 ], which will also be written as ϕ. For a ∈ R we write deg(a) := max{|k| | t k occurs in ϕ(a)}, with deg(0) := 0. So the invariant ring R Gm consists of the elements of degree 0.

We define the notion of a local slice for the multiplicative group as follows: Let 0 = c ∈ R be a semi-invariant. An element s ∈ R c is called a local slice of degree d > 0 with denominator c if (i) s is a semi-invariant of weight -d, (ii) s is invertible in R c , and (iii) all elements from R c \ R Gm c have degree at least d. In the next section we will present an algorithm for computing a local slice which is additionally a semi-invariant with respect to a torus action. The following theorem is analogous to Theorem 2.1 and shows that X c → Spec(R Gm c ) is an excellent quotient with fibers A 1 \ {0}. Part (a) can also be found in Popov [START_REF] Vladimir | Birational splitting and algebraic group actions[END_REF].

π: R c ψ - -→ (R c ) Gm [y ±1 ] y →1 ---→ (R c ) Gm is a homomorphism of (R c ) Gm -algebras with ker(π) = (s -1)R c . In particular, π is surjective. For a ∈ R c , π(a) is given by substituting t = d √ s in ϕ(a), which makes sense because ϕ(a) ∈ R c [t ±d ]. (c) The composition R c ϕ -→ R c [t ±1 ] π -→ (R c ) Gm [t ±1 ] (with π applied coefficient-wise) is injective and makes (R c ) Gm [t ±1 ] into an R c -module that is generated by d elements. (d) Let A be a ring with a homomorphism (R c ) Gm → A. Then (A ⊗ (Rc) Gm R) Gm = A.

Proof.

(a) To show injectivity, let f

∈ (R c ) Gm [y ±1 ] with f (s) = 0. Then 0 = ϕ f (s) = f ϕ(s) = f (st -d ),
so f = 0. For surjectivity, let a ∈ R c and first assume a to be a semi-invariant of weight k with k ∈ Z. Obtain k = qd + r with q, r ∈ Z, 0 r < d by division with remainder. It follows that s q a is a semi-invariant of degree r and therefore an invariant, so a = s q a • s -q ∈ (R c ) Gm [s ±1 ]. We also obtain r = 0, so k is divisible by d. For a ∈ R c arbitrary write ϕ(a) = k a k t k . Since ϕ defines a G m -action, it follows that each a k is a semi-invariant of weight k and that a = k a k . Since all a k lie in (R c ) Gm [s ±1 ], surjectivity follows. (b) The first claim is clear. Regarding the second claim, we have shown above that ϕ(a) ∈ R c [t ±d ] for a ∈ R c . For showing that the map that is claimed to be equal to π really is π, it suffices to check this for s, which is straightforward.

(c) Let a ∈ R c . By (a) we have a = f (s) with f ∈ (R c ) Gm [y ±1 ]. So π ϕ(a) = π f (ϕ(s)) = π f (st -d ) = f π(s)t -d = f (t -d ), from which (c) follows. (d) By (a), we have R := A ⊗ (Rc) Gm R = A[(1 ⊗ s) ±1 ]. By definition, (R ) Gm = ker(ϕ -id) with ϕ : R → R [t ±1 ] obtained by tensoring ϕ. Let r ∈ R and write r = i∈Z a i (1 ⊗ s) i with a i ∈ A. Then ϕ (r) -r = i a i (1 ⊗ t -d s) i -(1 ⊗ s) i = i a i (1 ⊗ s) i (t -id -1),
which is zero if and only if a i = 0 for i = 0, i.e., r ∈ A.

Again we present a simple example to illustrate the theorem.

Example 3.2. Consider the action of G m on X = C 2 by C × β → β 2 0 0 β 3 . The action is given by ϕ: R = C[a 1 , a 2 ] → C[a 1 , a 2 ][t ±1 ], a 1 → t 2 a 1 , a 2 → t 3 a 2 .
So s = a 1 /a 2 is a local slice of degree 2 with denominator c = a 1 a 2 . (Recall that denominator is a technical term here, given by the definition of a local slice.) By the last statement of Theorem 3.1(b), π: R c = C[a ±1 1 , a ±1 2 ] → (R c ) Gm is given by π(a 1 ) = s 2 a 1 = a 3 1 /a 2 2 and π(a 2 ) = s 3 a 2 = a 3 1 /a 2 2 , which yields the invariant ring

C[a ±1 1 , a ±1 2 ] Gm = C a 3 1 a 2 2 , a 2 2 a 3 1 .
Similarly to Example 2.2, the quotient C × × C × → C × given by the invariant ring is excellent, and it is elementary to check that the fibers are G m -orbits. It is also easy to see that

C[a 1 , a ±1 2 ] Gm = C[a 3 1 /a 2 2 ]
. The corresponding quotient C × C × → C is interesting for the following reason: Every G m -orbit is isomorphic to G m . Having the same dimension, all orbits are closed, so by Mumford et al. [17, Amplification 1.3] the quotient is universally geometric. However, the quotient has no cross section. Indeed, a cross section would correspond to a homomorphism π:

C[a 1 , a ±1 2 ] → C[a 3 1 /a 2 2 ] fixing C[a 3 1 /a 2 2 ]
. Since a 2 is invertible, it would be mapped to some γ ∈ C × , and then

π(a 1 ) 3 = π(a 1 ) 3 γ 2 π(a 2 ) 2 = γ 2 π a 3 1 a 2 2 = γ 2 a 3 1 a 2 2 , which is impossible since a 3 1 /a 2 2 has no third root in C[a 3 1 /a 2 2 ]
. This shows that an excellent quotient is stronger than a universally geometric quotient with isomorphic fibers.

Solvable group actions

In this section G is a connected solvable linear algebraic group over an algebraically closed field K, unless stated otherwise. Let us summarize the relevant facts about its structure (see Humphreys [START_REF] Humphreys | Linear Algebraic Groups[END_REF]Section 19] and Rosenlicht [20, Corollary 2, page 101])): As a variety, we may write G as

G = (ξ 1 , . . . , ξ l , η 1 , . . . , η m ) ∈ K l+m | η 1 • • • η m = 0 such that
(1) for i = 1, . . . , l, the subvariety G i := (ξ 1 , . . . , ξ i , 0, . . . , 0, 1, . . . , 1) ⊆ G is a normal subgroup; (2) the map G i → G a , (ξ 1 , . . . , ξ i , 0, . . . , 0, 1, . . . , 1) → ξ i is a morphism of algebraic groups;

(3) with T the m-dimensional torus, the map G → T , (ξ 1 , . . . , ξ l , η 1 , . . . , η m ) → (η 1 , . . . , η m ) is a morphism of algebraic groups.

It follows that the conjugation action of G on each G i /G i-1 ∼ = G a is given by a character

χ i ∈ K[G]. If K[G] = K[z 1 , . . . , z l , t ±1 1 , . . . , t ±1 m ]
then the χ i are power products of the t ±1 j . Let G act on an irreducible affine variety X. We present an algorithm for producing a local slice s ∈ R := K[X] for the action of the subgroup G 1 ∼ = G a such that the denominator c is a semi-invariant. We assume that it is possible to perform addition, multiplication, and zero testing of elements of R. Notice that the algorithm does not require any Gröbner basis computations and not even linear algebra (unless the underlying computations in R require Gröbner bases).

Algorithm 4.1 (A local slice for the additive group with semi-invariant denominator).

Input: An action of a connected solvable group G on an irreducible affine variety X, given by a homomorphism

ϕ: R → R[z 1 , . . . , z l , t ±1 1 , . . . , t ±1 m ],
where

K[X] = R and K[G] = K[z 1 , . . . , z l , t ±1 1 , . . . , t ±1 m ]. Assume that the character χ 1 ∈ K[t ±1
1 , . . . , t ±1 m ] as above is given, and that the subgroup G 1 ∼ = G a acts nontrivially. Output: A local slice s ∈ R with denominator c for the action of G 1 such that c is a semi-invariant of G.

(1) Compute a local slice s 1 ∈ R for the action of the subgroup G 1 with denominator c 1 ∈ R G1 , using the algorithm of Sancho de Salas [START_REF] Salas | Invariant theory for unipotent groups and an algorithm for computing invariants[END_REF]Section 3] or Tanimoto [24, Section 3]. (2) For i = 2, . . . , l repeat step 3.

(3) With ϕ i : R → R[z 1 , . . . , z i ] corresponding to the action of G i , compute ϕ i (c i-1 ) (which, as we will see, is nonzero and lies in R[z i ]) and let k be its degree. Set c i and s i to be the coefficient of z k i in ϕ i (c i-1 ) and ϕ i (s i-1 ), respectively. We will show that s i is a local slice for the action of G 1 with denominator

c i ∈ R Gi . (4) Compute ϕ(c l ) ∈ R[t ±1
1 , . . . , t ±1 m ] and choose a power product t * of the t ±1 j occurring in it. Since there is some freedom in the choice of t * , this can be used to make the coefficient of t * in ϕ(c l ) as palatable as possible. For example, a constant from K would be very desirable. With d the degree of s 1 , define s to be the coefficient of t * • χ d 1 in ϕ(s l ), and c to be the coefficient of t * in ϕ(c l ). We will show that s is a local slice with denominator c, and c is a semi-invariant.

Proof of correctness of Algorithm 4.1. For i = 1, . . . , l, we claim that s i is a local slice of degree d with denominator c i ∈ R Gi . This is true for i = 1, so let us assume i 2. By induction, 0 = c i-1 ∈ R Gi-1 . Since ϕ i defines a group action, ϕ i (c i-1 ) = 0. More precisely, the action of

G i /G i-1 ∼ = G a on R Gi-1 is given by ϕ i : R Gi-1 → R Gi-1 [z i ]. With (2.1) applied to ϕ i (c i-1 ), this shows that c i , defined in step 3, lies in R Gi . Write ϕ 1 (s i-1 ) = d j=0 r j z j 1 with r j ∈ R, so r d = c i-1 . Applying Lemma 4.2, which is proved below, to G 1 ⊆ G i yields (id K[z1,...,zi] ⊗ϕ 1 ) ϕ i (s i-1 ) = d j=0 ϕ i (r j )z j 1 ,
since the conjugation action of G i on G 1 is trivial. Comparing the coefficients of z j 1 z k i in this equation shows that ϕ 1 (s i ), with s i defined in step 3, equals a polynomial of degree d in R[z 1 ] with highest coefficient c i . This proves our claim.

We now look at step 4. The torus T acts on R G l , to which c l belongs. As for actions of the multiplicative group, it follows that each coefficient of ϕ(c l ) is a semi-invariant, so this is true for c. As above, Lemma 4.2 yields

(id K[z1,...,z l ,t ±1 1 ,...,t ±1 m ] ⊗ϕ 1 ) ϕ(s l ) = d j=0 χ j 1 ϕ(r j )z j 1 with r j ∈ R, r d = c l . Comparing the coefficient of z j 1 • t * • χ d 1 shows that ϕ 1 (s) is a polynomial of degree d with highest coefficient c.
The following lemma was used in the proof: Lemma 4.2. Let G be a linear algebraic group acting on an affine variety X, and let H ⊆ G be a normal subgroup with

H ∼ = G a . With R = K[X] and ϕ G : R → K[G] ⊗ R, ϕ H : R → R[z]
corresponding to the actions of G and H, let s ∈ R and write ϕ H (s) = d i=0 r i z i . Then

(id K[G] ⊗ϕ H ) ϕ G (s) = d i=0 χ i ϕ G (r i )z i ,
where the character χ ∈ K[G] corresponds to the conjugation action of G on H.

Proof. The commutative diagram

G × H × X (id G , act) E G × X d d act (conj, id G , id X ) c X act H × G × X (id H , act) E H × X
gives rise to a commutative diagram of rings, from which the lemma follows. Observe that the conjugation action G × H → H corresponds to the map

K[z] → K[G][z] sending z to χ • z.
We will also need an algorithm that finds a local slice s for an action of a multiplicative group such that its denominator c is a semi-invariant with respect to the action of an ambient torus. So let T be an m-dimensional torus acting on an affine variety X. With K[X] =: R, assume that the action is given by a homomorphism ϕ: R → R[t ±1 1 , . . . , t ±1 m ]. As in Section 3, for a semi-invariant a ∈ R with ϕ(a) = t e1 1 • • • t em m a, the weight is w(a) := e 1 . Algorithm 4.3 (A local slice for the multiplicative group with a semi-invariant denominator).

Input: A torus action on an irreducible affine variety given by a homomorphism ϕ as above.

Assume that generators a 1 , . . . , a n of the K-algebra R are given, and that the first direct component (3) Set c to be the product of all b i with k i = 0 and s :=

T 1 ∼ = G m of
l i=1 b -ki i . Proof of correctness of Algorithm 4.3. It is clear that c is a semi-invariant and that s is invertible of R c and a semi-invariant of weight -d. Since ϕ(a i ) ∈ R c [t ±d 1 , t ±1 2 , . . . , t ±1
m ] for all i, the image ϕ(R c ) lies in that ring. Therefore an element of R c \ R T1 c has degree at least d.

We are now ready to present the centerpiece of this paper: an algorithm that computes the invariant ring (K[X] c ) G of a connected solvable group, with c a semi-invariant. This yields an excellent quotient of X c (see Theorem 4.7(b)). The algorithm has been implemented in the computer algebra system MAGMA [START_REF] Bosma | The Magma Algebra System I: The User Language[END_REF], but the implementation is limited to the case that R is a polynomial ring over a field of characteristic 0. Algorithm 4.4 (Solvable group invariants).

Input:

• The coordinate ring K[G] = K[z 1 , . . . , z l , t ±1 1 , . . . , t ±1 m ] of a connected solvable group, and the characters χ i ∈ K[t ±1 1 , . . . , t ±1 m ] defining the conjugation action on G i /G i-1 (see at the beginning of this section).

• The coordinate ring R := K[X] = K[a 1 , . . . , a n ] of an irreducible affine variety.

Assume that addition, multiplication and zero recognition can be carried out in R.

• An action of G on X, given by a homomorphism ϕ: R → R[z 1 , . . . , z l , t ±1 1 , . . . , t ±1 m ]. Output:

• A nonzero semi-invariant c ∈ R. • Invariants b 0 , . . . , b n ∈ R c such that (R c ) G = K[b 0 , b 1 , . . . , b n ].
Moreover, the homomorphism

π: R c → (R c ) G , c -1 → b 0 , a j → b j (j = 1, . . . , n) satisfies π 2 = π, so it is a projection onto the invariant ring. • Generators u 1 , . . . , u k ∈ R of ker(π), where k = dim(R c ) -dim (R c ) G . (4.1)
(1) Initialization: Set b 0 := c := 1, b j := a j (j = 1, . . . , n), and k := 0.

(2) For i = 1, . . . , l repeat steps 3-7.

(3) If none of the ϕ(b j ) (j = 0, . . . , n) involves z i , skip steps 4-7 and proceed with the next i. Remark 4.5. If the ring R in Algorithm 4.4 is given as a quotient ring of a polynomial ring, R = K[x 1 , . . . , x n ]/I, then the algorithm yields the following presentation of (R c ) G : Let U i ∈ K[x 1 , . . . , x n ] be a preimage of u i ∈ R (i = 1, . . . , k) and let U 0 be a preimage of c. Then it is easy to see that the kernel of the map

T i := (ξ 1 , . . . , ξ l , η 1 , . . . , η i , 1, . . . , 1) ∈ K l+m | η 1 • • • η i = 0 ⊆ G, obtain r j ∈ ( R c ) Ti by substituting t i = d √ s in ψ i (b j ) (j = 1, . . . , n). ( 12
K[x 0 , . . . , x n ] → (R c ) G , x j → b j
is generated by I, U 1 , . . . , U k , and x 0 U 0 -1. Thus the algorithm computes the quotient X c /G as an affine variety in K n+1 .

Proof of correctness of Algorithm 4.4. Using induction on i, we first show that steps 1-7 compute the correct output for the subgroup G i , with 1 i l. By induction, R = (R c ) Gi-1 , on which G i /G i-1 ∼ = G a acts. Step 3 checks if this action is trivial, and if it is not, step 4 computes a local slice with denominator c ∈ R, which is a semi-invariant of G. By Theorem 2.1(b) there is a homomorphism

π i : R c → ( R c ) Gi
of ( R c ) Gi -algebras with kernel s R c , and step 5 computes the images r j = π i (b j ) for 1 j n.

By induction, we also have a homomorphism R c → R of R-algebras mapping the a j to the b j with kernel generated (as an ideal) by u 1 , . . . , u k . This extends to a homomorphism (R c ) c → R c of R c -algebras whose kernel is also generated by u 1 , . . . , u k . Composing this with π i yields a homomorphism (R c ) c → ( R c ) Gi of ( R c ) Gi -algebras sending a j to r j with kernel generated by u 1 , . . . , u k , s.

Step 6 finds a semi-invariant c ∈ R such that (R c ) c = R c and chooses

u k+1 ∈ R such that sR c = u k+1 R c . Moreover, (R c ) Gi = ( R c ) Gi , so dim(R c ) -dim (R c ) Gi = dim (R c ) c -dim R c + dim R c -dim ( R c ) Gi = dim(R c ) -dim (R c ) Gi-1 + dim R c -dim ( R c ) Gi = k + 1,
where the last equality follows by induction and from Theorem 2.1(a). So indeed after step 7, the current c, b j , and u 1 , . . . , u k satisfy all the specifications of the algorithm for the group G i . We now turn our attention to steps 8-13 and show that they compute the correct output for the subgroups T i (1 i m). The proof is almost identical to the one for steps 1-7, using Theorem 3.1 instead of 2.1. Here the kernel of the projection π i : R c → ( R c ) Ti is ( s -1) R c . The only other difference is the computation of r 0 in step 12. For the algorithm to be correct, r 0 needs to be the image of (c ) Example 4.6. Let G ⊂ SL 2 (C) be the subgroup consisting of all upper triangular matrices, which is a Borel subgroup. G acts on binary forms of degree 2 by the matrices

β 2 αβ α 2 0 1 2αβ -1 0 0 β -2 with α, β ∈ C, β = 0.
The action is given by ϕ: R :

= C[a 1 , a 2 , a 3 ] → C[a 1 , a 2 , a 3 ][z, t ±1 ] with ϕ(a 1 ) = t 2 a 1 + zta 2 + z 2 a 3 , ϕ(a 2 ) = a 2 + 2zt -1 a 3 , ϕ(a 3 ) = t -2 a 3 ,
extending (2.4). To run Algorithm 4.4, we first need to choose a local slice for G a ⊂ G, given by t = 1. By Example 2.2, s = a 2 is an obvious choice. Luckily, the denominator c = a 3 already is a semi-invariant. (In fact, running Algorithm 4.1 would leave the initial choice s = a 2 unchanged, since the power product t * in step 4 would be t * = t -2 , while the conjugation in G is given by χ = t 2 .) According to (2.5) in Example 2.2, the first half of Algorithm 4.4 yields the three generators

b 0 = a -1 3 , b 1 = 4a 1 a 3 -a 2 2 4a 3 , and b 3 = a 3 of R = R Ga c = C[a 1 , a 2 , a ±1 3 ] Ga . By an easy computation, we have ϕ(b 0 ) = t 2 b 0 , ϕ(b 1 ) = t 2 b 1 , ϕ(b 3 ) = t -2 b 3 .
So, as predicted by the theory, only the multiplicative group G m acts on R, and we find a local slice s = b 3 = a 3 of degree 2 for this action. Since s is already invertible in R, the denominator can be taken to be c = 1. From this, steps 11 and 12 of Algorithm 4.4 compute generators r 0 = sb 0 = 1, r 1 = sb 1 = a 1 a 3 -a 2 2 /4, and

r 3 = s -1 b 3 = 1 of R Gm = C[a 1 , a 2 , a ±1 3 ] G . So C[a 1 , a 2 , a ±1 3 ] G = R Gm = C[r 0 , r 1 , r 2 ] = C[a 2 2 -4a 1 a 3 ]. (4.2)
This is the final result of Algorithm 4.4, together with the projection

π: C[a 1 , a 2 , a ±1 3 ] → C[a 1 , a 2 , a ±1 3 ] G , a 1 → a 1 a 3 -a 2 2 /4, a 2 → 0, a ±1 3 → 1.
Part (b) of the following theorem says that (R c ) G affords an excellent quotient. Explicitly, the quotient is the map C 2 × C × → C given by evaluating the discriminant. It is straightforward to verify that the fibers of this map are indeed G-orbits.

It follows directly from (4.2) that the nonlocalized invariant ring is

C[a 1 , a 2 , a 3 ] G = C[a 2 2 - 4a 1 a 3 ]
. This makes the business about using a localization look like a diversion. However, the corresponding map C 3 → C is not a geometric quotient. In fact, a short calculation shows that all fibers, except for the zero fiber, contain precisely three G-orbits. But the nonlocalized ring C[a 1 , a 2 , a 3 ] has the advantage that SL 2 acts on it, with G a Borel subgroup. So the result mentioned in the first paragraph of the introduction yields

C[a 1 , a 2 , a 3 ] SL2 = C[a 2
2 -4a 1 a 3 ], so we recover a very well-known result about invariants of binary forms. Notice that this invariant ring was also used in Derksen and Kemper [START_REF] Harm Derksen | Computational Invariant Theory[END_REF]Example 4.1.12] to give an illustrating example of the Derksen algorithm. In that example, a Gröbner basis computation is needed which cannot be shown, whereas here all computations are elementary. However, it was a lucky circumstance in this example that the G-invariants of the nonlocalized ring could easily be determined from the G-invariants of the localized ring.

The following theorem summarizes the results of this paper: Apart from dealing with a more general setting, the preprint [START_REF] Kemper | Quotients by Connected Solvable Groups[END_REF] contains a small number of examples of actions of connected groups where no nonempty open subset exists that admits an excellent quotient. Moreover, actions where a nonempty open subset admits an excellent quotient with fibers A r,s are characterized as "essentially solvable." These results prompt us to conclude the paper with the following rather bold conjecture: Conjecture 4.8. If G is a linear algebraic group such that every irreducible affine G-variety X has a nonempty G-stable subset U that admits an excellent quotient, then G is connected and solvable.

Theorem 2 . 1 .

 21 In the above situation, let s be a local slice of degree d with denominator c ∈ R Ga . (a) The homomorphism R Ga c [x] → R c sending the indeterminate x to s is an isomorphism. We write ψ: R c → R Ga c [x] for the inverse isomorphism. (b) The composition π: R c ψ

Theorem 3 . 1 .

 31 In the above situation, let s be a local slice of degree d with denominator c. (a) The homomorphism (R c ) Gm [y ±1 ] → R c sending the indeterminate y to s is an isomorphism. We write ψ: R c → (R c ) Gm [y ±1 ] for the inverse isomorphism. (b) The composition

  T acts nontrivially. Output: A local slice s ∈ R c with denominator c for the action of T 1 , such that s and c are semi-invariants of T . (1) Collect all coefficients of the ϕ(a i ) into a set {b 1 , . . . , b l }. Thus the b i are semi-invariants. (2) Let d be the gcd of the weights w(b i ) and find integers k 1 , . . . , k l such that d = l i=1 k i w(b i ).

( 4 )

 4 Apply Algorithm 4.1 with the following arguments: the ring R := K[b 0 , . . . , b n ] ⊆ R c , the homomorphism R → R[z i , . . . , z l , t ±1 1 , . . . , t ±1 m ] obtained by extending ϕ to R c and restricting to R, and the character χ i . Let s ∈ R be the resulting local slice with denominator c. (5) With ϕ i : R → R[z i ] corresponding to the action of the subgroup G i , perform division with remainder in R c [z i ]:ϕ i (b j ) = g j • ϕ i ( s) + r j (j = 1, . . . , n). Then r j ∈ ( R c ) Gi . (6) Choose e large enough such that c e c ∈ R and set c := c e+1 c, r 0 := (c ) -1 ∈ R c . Choose ê large enough such that u k+1 := c ê s ∈ R. (7) Replace b j by r j (j = 0, . . . , n), c by c , and k by k + 1. (8) For i = 1, . . . , m repeat steps 9-13. (9) If none of the ϕ(b j ) (j = 0, . . . , n) involves t i , skip steps 10-13 and proceed with the next i. (10) Apply Algorithm 4.3 to the ring R := K[b 0 , . . . , b n ] ⊆ R c and the homomorphism R → R[t ±1 i , . . . , t ±1 m ] obtained by extending ϕ to R c and restricting to R. Let s ∈ R c be the resulting local slice of degree d with denominator c ∈ R. (11) With ψ i : R → R[t ±d i ] corresponding to the action of the subgroup

  ) Choose e large enough such that c e c ∈ R and set c := c e+1 c. Obtainr 0 ∈ R c = R c by substituting t i = d √ s in ψ i (b e+1 0 c -1). Choose ê such that u k+1 := (c ) ê( s-1) ∈ R. (13) Replace b j by r j (j = 0, . . . , n), c by c , and k by k + 1.

  -1 under the composition R c → R c πi --→ ( R c ) Ti . By induction, the first map sends c -1 to b 0 , and it sends c to itself since c ∈ R. So the composition R c → ( R c ) Ti sends (c ) -1 to π i (b e+1 0 c -1 ), which is precisely what step 12 computes. The following simple example, which is a follow-up to Example 2.2, should illustrate Algorithm 4.4.

Theorem 4 . 7 .

 47 Let G be a connected solvable linear algebraic group over an algebraically closed field K, acting on an irreducible affine variety X.(a) Algorithm 4.4 computes a nonzero semi-invariant c ∈ R := K[X], generators of the invariant ring (R c ) G , and the relations between the generators. If no Gröbner bases are required for computing in R, then the algorithm does not require any Gröbner basis computations either. (b) With X c /G is the variety corresponding to (R c ) G , the map X c → X c /G is an excellent quotient with fibers A r,s as defined in the introduction. If G is unipotent, then s = 0. (c) The generators of (R c ) G also generate the invariant field K(X) G as an extension of K.(d) If R is a complete intersection (e.g. if R is a polynomial ring), then so is (R c ) G .Proof.(a) This follows from the proof of correctness of the algorithm, from Remark 4.5, and by verifying that no step in the algorithm requires any Gröbner bases. (b) We have already seen in the proof of correctness of the algorithm that steps 2-7 perform the passage from (R c ) Gi-1 to (R c ) Gi . Now it follows from Theorem 2.1 and the remark preceding it that Spec (R c ) Gi-1 → Spec (R c ) Gi is an excellent quotient with fibers A 1 . Likewise, Theorem 3.1 shows that steps 9-13 yield an excellent quotient Spec (R c ) Ti-1 → Spec (R c ) Ti with fibers A 1 \ {0}. Applying Theorem 1.2 repeatedly to the chain of excellent quotients produced by the algorithm, we obtain the assertion (b). (c) This follows from (b) and the fact that for any geometric quotient X → Y with X an integral scheme, K(Y ) = K(X ) G (see Kemper[START_REF] Kemper | Quotients by Connected Solvable Groups[END_REF] Lemma 2.9]). (d) By hypothesis we have R = K[x 1 , . . . , x n ]/I with I generated by n-dim(R) elements. By Remark 4.5 we have an epimorphism K[x 0 , . . . , x n ] → (R c ) G whose kernel is generated by n -dim(R) + k + 1 = n + 1 -dim(R) + dim(R c ) -dim (R c ) G = n + 1 -dim (R c ) G elements, where (4.1) was used for the second equality. This completes the proof.

Acknowledgements. This article benefited from interesting and helpful conversations with Igor Dolgachev, Hanspeter Kraft, Stephan Neupert, and Vladimir Popov. I also thank the anonymous referees for their helpful comments.


Daniel Perrucci

Marie-Françoise Roy

A new general formula for the Cauchy Index on an interval with Subresultants

Keywords: Cauchy Index, Subresultant Polynomials. AMS subject classifications: 14P99, 13P15, 12D10, 26C15

We present a new formula for the Cauchy index of a rational function on an interval using subresultant polynomials. There is no condition on the endpoints of the interval and the formula also involves in some cases less subresultant polynomials.

Introduction

Let (R, ≤) be a real closed field and P, Q ∈ R[X] with P = 0. Already considered by Sturm and Cauchy ([8,[START_REF] Cauchy | Oeuvres complètes[END_REF]), the Cauchy index of the rational function Q P is the integer number which counts its number of jumps from -∞ to +∞ minus its number of jumps from +∞ to -∞. This value plays an important role in many algorithms in real algebraic geometry ([2, 3, 6]). For instance, the Tarski query of Q for P , defined as

TaQ(Q, P ) = # x ∈ R | P (x) = 0, Q(x) > 0 -# x ∈ R | P (x) = 0, Q(x) < 0 ,
is equal to the Cauchy index of the rational function P Q P (see, for instance, [3, Proposition 2.57]). Tarski queries are used to solve the sign determination problem, which consists in listing the signs of a list of polynomials in R[X] evaluated at the roots in R of another polynomial in R[X] (see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Section 10.3]). In particular, the number of real roots of a polynomial P ∈ R[X] \ {0} coincides with the Tarski query TaQ(1, P ) and is equal to the Cauchy index of the rational function P P . We can also mention the role of the Cauchy index for complex roots counting (see [START_REF] Cauchy | Oeuvres complètes[END_REF][START_REF] Eisermann | The fundamental theorem of algebra made effective: an elementary realalgebraic proof via Sturm chains[END_REF][START_REF] Perrucci | Quantitative Fundamental Theorem of Algebra[END_REF]). For more information and references to the history of the Cauchy index see [START_REF] Eisermann | The fundamental theorem of algebra made effective: an elementary realalgebraic proof via Sturm chains[END_REF].

Cauchy index

Let P, Q ∈ R[X] with P = 0. The usual definition of the Cauchy index of Q P is made directly on intervals whose endpoints are not roots of P . In this paper we use the extended definition of the Cauchy index introduced in [5, Section 3], which is made first locally at elements in R, and then on intervals without restriction.

Definition 1 Let x ∈ R and P, Q ∈ R[X], P = 0.

• If Q = 0, the rational function Q P can be written uniquely as

Q P = (X -x) m Q P with m ∈ Z, P , Q ∈ R[X]
, P monic, P and Q coprime and P (x) = 0, Q(x) = 0. For ε ∈ {+, -}, define

Ind ε x Q P =          1 2 • sign Q(x)
P (x) if ε = + and m < 0, In all other cases, define

Ind ε x Q P = 0
• The Cauchy index of Q P at x is

Ind x Q P = Ind + x Q P -Ind - x Q P .
Said in other terms, when x is a pole of Q P , we have that Ind +

x Q P is one half of the sign of Q P to the right of x, and Ind -

x Q P is one half of the sign of Q P to the left of x. Then, the Cauchy index of Q P at

x, Ind x Q P , is simply the difference between them. We illustrate this notion considering the graph of the function Q P around x in each different case.

x x x x

Ind x Q P = 0 Ind x Q P = 1 Ind x Q P = -1 Ind x Q P = 0 Definition 2 Let a, b ∈ R with a < b and P, Q ∈ R[X] with P = 0. If Q = 0, the Cauchy index of Q P on [a, b] is Ind b a Q P = Ind + a Q P + x∈(a,b) Ind x Q P -Ind - b Q P ,
where the sum is well-defined since only roots

x of P in (a, b) contribute. Similarly, if Q = 0, the Cauchy index of Q P on R is Ind R Q P = x∈R Ind x Q P
where, again, the sum is well-defined since only roots x of P in R contribute.

If Q = 0, both the Cauchy index of Q P on [a, b] and the Cauchy index of Q P on R are defined as 0.

In the following picture we consider again the graph of the function

Q P , this time in [a, b]. a b a b Ind b a Q P = 1 + 0 + 1 = 2 Ind b a Q P = -1 -1 - 1 2 = - 5 2
Note that with this extended definition of the Cauchy index, the Cauchy index of a rational function on an interval belongs to 1 2 Z and it is not necessarily an integer number.

Sturm sequences and Cauchy index

Definition 3 Let P, Q ∈ R[X], P = 0. Define S 0 = P and, if Q = 0,

S 1 = Q, S 2 = -Rem(S 0 , S 1 ), . . . S i+1 = -Rem(S i-1 , S i ), . . . S s+1 = -Rem(S s-1 , S s ) = 0,
with S 1 , S 2 , . . . , S s = 0, where Rem is the remainder in the euclidean division in R[X] of the first polynomial by the second polynomial.

The Sturm sequence of P and Q = 0 is (S 0 , . . . , S s ) and the Sturm sequence of P and 0 is S 0 , with s = 0. We denote by (d 0 , . . . , d s ) the degrees of (S 0 , . . . , S s ).

Example 4 Let α, β ∈ R and P = X 5 + αX + β ∈ R[X]
. If α = 0 and 256α 5 + 3125β 4 = 0, the Sturm sequence of P and P is (S 0 , S 1 , S 2 , S 3 ) with

S 0 = P = X 5 + αX + β, S 1 = P = 5X 4 + α, S 2 = -4α 5 X -β S 3 = -(256α 5 +3125β 4 ) 256α 4
.

In this case,

d 0 = 5, d 1 = 4, d 2 = 1, d 3 = 0.
Extending the classical results by Sturm ([8]) and recent results by [START_REF] Eisermann | The fundamental theorem of algebra made effective: an elementary realalgebraic proof via Sturm chains[END_REF], we now explain that the Sturm sequence of P and Q gives a formula for the general definition of the Cauchy index on an interval [a, b] under no assumptions on a and b. To do so, it is first needed to extend the notion of sign of a rational function to degenerate cases.

Definition 5 Let P, Q ∈ R[X] \ {0}.
Using the same notation as in Definition 1, we define

sign Q P , x =    sign Q(x) P (x) ∈ {-1, 1} if m = 0, 0 otherwise .
We define also sign

Q P , x = 0 if Q = 0.
In other words, if x is a pole of Q P , the sign of Q P at x is 0; otherwise, it is simply the sign of the continuous extension of

Q P at x. Notice that if Q = 0, sign Q P , x = sign P Q , x .
We now state the general result relating the Cauchy index and the Sturm sequence, which will be proved at the end of Section 4.

Theorem 6 Let a, b ∈ R with a < b and P, Q ∈ R[X], P = 0, deg Q = q < deg P = p. If (S 0 , . . . , S s ) is the Sturm sequence of P and Q, then

Ind b a Q P = 1 2 0≤i≤s-1 sign S i+1 S i , b -sign S i+1 S i , a .
Adding the condition that a and b are not common roots of P and Q, from Theorem 6 a sign-variationcounting formula for the Cauchy index is obtained.

Definition 7 Let x ∈ R and P, Q ∈ R[X],
we define the sign variation of (P, Q) at x by

Var x (P, Q) = 1 2 sign(P (x)) -sign(Q(x)) .
If a, b ∈ R with a < b, we denote by Var b a (P, Q) the sign variation of (P, Q) at a minus the sign variation of (P, Q) at b; namely,

Var b a (P, Q) = Var a (P, Q) -Var b (P, Q).
Note that for x ∈ R,

Var x (P, Q) =      0 if P (x)
P , x = 1 -2Var x (P, Q). (1)
The following result then follows clearly from Theorem 6.

Theorem 8 Let a, b ∈ R with a < b and P, Q ∈ R[X], P = 0, deg Q = q < deg P = p.
If a and b are not common roots of P and Q and (S 0 , . . . , S s ) is the Sturm sequence of P and Q, then

Ind b a Q P = 0≤i≤s-1 Var b a (S i , S i+1 ).
Theorem 8 is a generalization of the classical Sturm theorem [START_REF] Sturm | Collected Works[END_REF][START_REF] Basu | Algorithms in real algebraic geometry[END_REF], since a or b can be root of P or Q (but not of both).

Subresultant polynomials

Subresultant polynomials are polynomials which are proportional to the ones in the Sturm sequence, but enjoy better properties since their coefficients belong to the ring generated by the coefficients of P and Q. We include definitions and properties concerning subresultant polynomials. We refer the reader to [START_REF] Basu | Algorithms in real algebraic geometry[END_REF] for proofs and details.

Let D be a domain and let ff(D) be its fraction field.

Definition 9 Let P = a p X p + • • • + a 0 , Q = b q X q + • • • + b 0 ∈ D[X] \ {0} with deg P = p ≥ 1 and deg Q = q < p.
For 0 ≤ j ≤ q, the j-th subresultant polynomial of P and Q, sResP

j (P, Q) ∈ D[X] is det                    a p a p-1 . . . X q-j-1 P 0 a p a p-1 . . . X q-j-2 P . . . . . . . . . . . . 0 a p a p-1 . . . P 0 b q b q-1 . . . Q . . . . . . . . . . . . . . . . . . . . . . . . 0 b q b q-1 . . . X p-j-2 Q b q b q-1 . . . X p-j-1 Q                    ∈ D[X]. p + q -2j
By convention, we extend this definition with

sResP p (P, Q) = P ∈ D[X], sResP p-1 (P, Q) = Q ∈ D[X], sResP j (P, Q) = 0 ∈ D[X] for q < j < p -1.
We also define sResP p (P, 0) = P, sResP j (P, 0) = 0, j = 0, . . . , p -1.

Note that in the matrix above, all the entries in the first p + q -2j -1 columns are elements in D, and all the entries in the last column are elements in D[X]. Doing column operations, it is easy to prove that for 0 ≤ j ≤ p, deg sResP j (P, Q) ≤ j.

Note also that in the case q = p -1, we have given two definitions for sResP q (P, Q), both equal to Q so that there is no ambiguity.

Definition 10 Let P, Q ∈ D[X] \ {0} with deg P = p ≥ 1 and deg Q = q < p.
• For 0 ≤ j ≤ q, the j-th subresultant coefficient of P and Q, sRes j (P, Q) ∈ D is the coefficient of X j in sResP j (P, Q). By convention, we extend this definition with

sRes p (P, Q) = 1 ∈ D (even if P is not monic), sRes j (P, Q) = 0 ∈ D for q < j ≤ p -1.
• For 0 ≤ j ≤ p, sResP j (P, Q) is said to be

-defective if deg sResP j (P, Q) < j or, equivalently, if sRes j (P, Q) = 0, -non-defective if deg sResP j (P, Q) = j or, equivalently, if sRes j (P, Q) = 0.
We refer the reader to [1, Chapitre 9] for another definition of subresultant polynomials and coefficients, which differs possibly in a sign.

We illustrate Definitions 9 and 10 with the following example.

Example 11 Let α, β ∈ R and P = X 5 + αX + β ∈ R[X], then P = 5X 4 + α as in Example 4. We have sResP 5 (P, P ) = P, sResP 4 (P, P ) = P

sResP (P, P ) = det    1 0 X 5 + αX + β 0 5 5X 4 + α 5 0 5X 5 + αX    = -5(4αX + 5β) sResP (P, P ) = det        1 0 0 0 X 6 + αX 2 + βX 1 0 1 0 0 X 5 + αX + β 0 0 5 0 5X 4 + α 0 5 0 0 5X 5 + αX 1 5 0 0 0 5X 6 + αX 2        = 0, sResP (P, P ) = det             1 0 0 0 α β X 7 + αX 3 + βX 2 0 1 0 0 0 α X 6 + αX 2 + βX 1 0 0 1 0 0 0 X 5 + αX + β 0 0 0 5 0 0 5X 4 + α 0 0 5 0 0 0 5X 5 + αX 1 0 5 0 0 0 α 5X 6 + αX 2 5 0 0 0 α 0 5X 7 + αX 3             = 80α 2 (4αX + 5β), sResP (P, P ) = det                 1 0 0 0 α β 0 0 X 8 + αX 4 + βX 3 0 1 0 0 0 α β 0 X 7 + αX 3 + βX 2 0 0 1 0 0 0 α β X 6 + αX 2 + βX 1 0 0 0 1 0 0 0 α X 5 + αX + β 0 0 0 0 5 0 0 0 5X 4 + α 0 0 0 5 0 0 0 α 5X 5 + αX 1 0 0 5 0 0 0 α 0 5X 6 + αX 2 0 5 0 0 0 α 0 0 5X 7 + αX 3 5 0 0 0 α 0 0 0 5X 8 + αX 4                 = 256α 5 + 3125β 4 .
Note that sResP 5 (P, P ) and sResP 4 (P, P ) are non-defective while sResP 3 (P, P ) and sResP 2 (P, P ) are defective. Finally, sResP 1 (P, P ) is defective if and only if α = 0, and sResP 0 (P, P ) is defective if and only if 256α 5 + 3125β 4 = 0.

The following Structure Theorem is a key result in the theory of subresultants, stating the connection between subresultants and remainders. To state it, we need to introduce a notation.

Notation 12 For n ∈ Z, we denote n = (-1)

1 2 n(n-1)
.

Note that n = 1 if the remainder of n in the division by 4 is 0 or 1 and n = -1 if the remainder of n in the division by 4 is 2 or 3; this implies that for k ∈ Z

2k+n = (-1) k n = 2k n . (2)
Theorem 13 (Structure Theorem of Subresultants)

Let P, Q ∈ D[X] \ {0} with deg P = p ≥ 1 and deg Q = q < p.
Let (d 0 , . . . , d s ) be the sequence of degrees of the Sturm sequence of P and Q in decreasing order and let d -1 = p + 1 (note that d 0 = p and d 1 = q).

• For

1 ≤ i ≤ s, sResP d i-1 -2 (P, Q) = • • • = sResP d i +1 (P, Q) = 0 ∈ D[X]
and sResP d i-1 -1 (P, Q) and sResP d i (P, Q) are proportional. More precisely, for 1 ≤ i ≤ s, denote

T i = sResP d i-1 -1 (P, Q) ∈ D[X], t i = lc(T i ) ∈ D
(note that T 1 = Q), and extend this notation with T 0 = P and t 0 = 1 ∈ D (even if P is not monic). Then

sRes d i (P, Q) • T i = t i • sResP d i (P, Q) ∈ D[X]
with

sRes d i (P, Q) = d i-1 -d i • t d i-1 -d i i sRes d i-1 (P, Q) d i-1 -d i -1 ∈ D. (3)
This implies deg

T i = d i ≤ d i-1 -1. • For 1 ≤ i ≤ s -1, t i-1 • sRes d i-1 (P, Q) • T i+1 = -Rem (t i • sRes d i (P, Q) • T i-1 , T i ) ∈ D[X] (4)
(where Rem is the remainder in the euclidean division in ff(D)[X] of the first polynomial by the second polynomial) and the quotient belongs to D[X].

• Both T s ∈ D[X] and sResP ds (P, Q) ∈ D[X] are greatest common divisors of P and Q in ff(D)[X]
and they divide sResP j (P, Q) for 0 ≤ j ≤ p. In addition, if d s > 0 then

sResP ds-1 (P, Q) = • • • = sResP 0 (P, Q) = 0 ∈ D[X]. Proof: See [3, Chapter 8].
Note that Theorem 13 (Structure Theorem of Subresultants) gives a method for computing the subresultant polynomials using remainders which is more efficient than using their definition as determinants. However we are not concerned with subresultant polynomials computations in the current paper. We are only concerned with a formula for the Cauchy index using the subresultant polynomials.

Theorem 13 (Structure Theorem of Subresultants) can be illustrated by the following picture.

T 0 = P = sResP d0 (P, Q) = sResP p (P, Q) T 1 = Q = sResP d0-1 (P, Q) = sResP p-1 (P, Q) 0 . . . 0 sResP d1 (P, Q) = sResP q (P, Q) T 2 = sResP d1-1 (P, Q) = sResP q-1 (P, Q) 0 . . . . . . 0 sResP d2 (P, Q) . . . . . . T s = sResP ds-1-1 (P, Q) 0 . . . . . . 0 sResP ds (P, Q) 0 . . . 0
As a corollary to Theorem 13, all subresultant polynomials are either 0 or proportional to polynomials in the Sturm sequence. More precisely, for 1 ≤ i ≤ s, the subresultant polynomial T i is proportional to S i in the Sturm sequence.

Remark 14 In the case where all the subsresultant polynomials are non-defective, there are no pairs of proportional polynomials in the sequence of subresultant polynomials, the degrees of the polynomials S i in the Sturm sequence decrease one by one, and the coefficient of proportionality between T i and S i is a square (see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Corollary 8.37]).

Main results

In order to state our results we introduce the following notation.

Notation 16 Using the notation from Theorem 13, for 0 ≤ i ≤ s, let

p(i) = max{j | 0 ≤ j ≤ i, d j-1 -d j is odd} (p(i) is well-defined since d -1 -d 0 = (p + 1) -p = 1 is odd).
We are ready now to state our main result, which is a new formula for Ind b a Q P using only the polynomials T i in the sequence of the subresultant polynomials.

Q P = 1 2 0≤i≤s-1 d p(i)-1 -d i • sign(t p(i) ) • sign(t i ) • sign T i+1 T i , b -sign T i+1 T i , a .
As we will see in Section 2, the main advantage of the formula in Theorem 17 in comparison with previously known related formulas is that there is no assumption on the endpoints a and b of the interval, and, more importantly, potentially less subresultant polynomials (i.e. only te T i ) are involved.

If we add the condition that a and b are no roots of P and Q, from Theorem 17 we obtain a signvariation-counting formula.

Theorem 18 Let a, b ∈ R with a < b and

P, Q ∈ R[X] \ {0} with deg P = p ≥ 1 and deg Q = q < p.
If a and b are not common roots of P and Q, then

Ind b a Q P = 0≤i≤s-1 d p(i)-1 -d i • sign(t p(i) ) • sign(t i ) • Var b a (T i , T i+1 ).
Finally, for the Cauchy index on R, we obtain the following result.

Theorem 19 Let P, Q ∈ R[X] \ {0} with deg P = p ≥ 1 and deg Q = q < p. If the leading coefficient of P is positive or if d 0 -d 1 = p -q is even, then Ind R Q P = 0≤i≤s-1, d i -d i+1 odd d p(i)-1 -d i • sign(t p(i) ) • sign(t i+1 ).
If the leading coefficient of P is negative and d 0 -d 1 = p -q is odd, then

Ind R Q P = -sign(t 1 ) + 1≤i≤s-1, d i -d i+1 odd d p(i)-1 -d i • sign(t p(i) ) • sign(t i+1 ).
Example 20 (Continuation of Examples 4, 11 and 15) Following Notation 16, for 0 ≤ i ≤ 3 we have p(i) = i. Therefore, by Theorem 19, when we fix (α, β) ∈ R 2 with α = 0 and 256α 3 +3125β 4 = 0, the number of roots of P in R is given by

Ind R P P = 1 -sign(α) + sign(α) • sign(256α 5 + 3125β 4 ).
The rest of the paper is organized as follows. In Section 2 we comment the differences between our results and previously known related formulas. In Section 3 we review some useful properties of Cauchy index. In Section 4, we recall the notion of (σ, τ )-chain and their connection with Cauchy index. Finally, in Section 5 we prove Theorem 17 using (σ, τ )-chains, and Theorems 18 and 19 as consequences of Theorem 17.

Comparison with previous Cauchy index formulas using subresultants

There is a previously known formula for the Cauchy index Ind with s n = 0 and s a finite sequence of m elements in R with 0 ≤ m ≤ n -1, which is either empty (this is, m = 0) or s = (s m , . . . , s 1 ) with s m = 0. The modified number of sign variations in s is defined inductively as follows

MVar(s) =              0 if s = ∅, MVar(s ) + 1 if s n s m < 0, MVar(s ) + 2 if s n s m > 0 and n -m = 3, MVar(s ) if s n s m > 0 and n -m = 3.
In other words, the usual definition of the number of sign variations is modified by counting two sign variations for the groups: +, 0, 0, + and -, 0, 0, -. If there are no zeros in the sequence s, MVar(s) is just the classical number of sign variations in the sequence.

Let P be a sequence (P 0 , P 1 , . . . , P d ) of polynomials in R[X] and let x be an element of R which is not a root of the gcd of (P 0 , P 1 , . . . , P d ), which we call gcd(P). Then MVar(P; x), the modified number of sign variations of P at x, is the number defined as follows:

-delete from P those polynomials that are identically 0 to obtain the sequence of polynomials

Q = (Q 0 , • • • , Q s ) in D[X],
-define MVar(P; x) as MVar(Q

0 (x), • • • , Q s (x)).
Let a and b be elements of R which are not roots of gcd(P). The difference between the number of modified sign variations in P at a and b is denoted by MVar(P; a, b) = MVar(P; a) -MVar(P; b).

Denoting by SResP(P, Q) the list of subresultant polynomials of P and Q, the following result is known (see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Chapter 9]). a.ii) More importantly, there are cases when less subresultant polynomials are involved in this new formula. The Structure Theorem of Subresultants (Theorem 13 ) states that in the subresultant polynomial sequence, some polynomials appear only once and other polynomials appear exactly twice (up to scalar multiples). In addition, if a polynomial appears twice, its first appearance, T i , is defined as the polynomial determinant of a matrix of smaller size (in comparison with its second appearance), so that it is more suitable in computations. Our formula involves only the T i , i.e. the first appearance( up to scalar multiples) of each polynomial in the subresultant polynomial sequence.

In the special case when a and b are not common roots of P and Q, Theorem 18 gives a sign-variationcounting formula which improves on the one from Proposition 22 since: b.i) Theorem 18 imposes less restrictions on a and b.

b.ii) As in a.ii).

b.iii) The formula is more natural, since the sign-variation counting in Theorem 18 is local and needs only to consider the sign of two consecutive elements, contrarily to the modified number of sign variations which is very counter-intuitive.

Last but not least, the proofs of our results are also less technically involved than the proof of Proposition 22, which is cumbersome (see the proof in [3, Chapter 9]).

Note that, in the particular case where all subresultant polynomials are non-defective, both the formulas in Theorem 18 and in Proposition 22 become

Ind b a Q P = 0≤j≤p-1
Var b a (sResP j , sResP j+1 )

(see [3, Chapters 2 and 9]), but the new formula extends the previous one to the case whera a and b are not common roots of P and Q.

There is also a previously known formula for the Cauchy index Ind R Q P by means of subresultant coefficients which we introduce below (see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Chapter 4]).

Proposition 23 Using the notation from Theorem 13, for 0 ≤ i ≤ s, let s i = sRes d i (P, Q) be the leading coefficient of the non-defective subresultant polynomial sResP d i (P, Q) (which is proportional to T i ). Then

Ind R Q P = 0≤i≤s-1, d i -d i+1 odd d i -d i+1 • sign(s i ) • sign(s i+1 ).
Even in this special case, the new formula for Ind b a Q P given in Theorem 19 improves on the one from Proposition 23. As before, the main difference between the two formulas is that the t i are, in the defective cases, defined as determinants of matrices of smaller sizes than the s i and therefore is more suitable in computations. On the other hand, one advantage of Proposition 23 is that it can be proved directly, using only subresultant coefficients and does not use the definition of the subresultant polynomials and the Structure Theorem of subresultants (see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Chapter 4]).

Properties of Cauchy index

In this section we include some useful properties of Cauchy index.

Lemma 24 Let a, b ∈ R with a < b, P, Q ∈ R[X] \ {0} and c ∈ R \ {0}. Then Ind b a c • Q P = sign(c) • Ind b a Q P .
Proof: Follows immediately from the definition of Cauchy index.

Lemma 25 Let a, b ∈ R with a < b, P, Q, R ∈ R[X] \ {0} and T ∈ R[X] such that Q = P T + R. Then Ind b a Q P = Ind b a R P .
Proof: For each x ∈ [a, b], we first note that if

Q P = (X -x) m Q P with m ∈ Z, P (x) = 0, Q(x) =

(σ, τ )-chains and Cauchy index

The notion of (σ, τ )-chain was introduced in [START_REF] Perrucci | Quantitative Fundamental Theorem of Algebra[END_REF]. Here, we need to introduce a slight variation of this notion.

Definition 27 Let n ∈ Z ≥1 and σ, τ ∈ {-1, 1} n-1 with σ = (σ 1 , . . . , σ n-1 ) and τ = (τ 1 , . . . , τ n-1 ). A sequence of polynomials (P 0 , . . .

, P n ) in R[X] is a special (σ, τ )-chain if for 1 ≤ i ≤ n -1 there exist a i , c i ∈ R \ {0} and B i ∈ R[X] such that 1. a i P i+1 + B i P i + c i P i-1 = 0, 2. sign(a i ) = σ i , 3. sign(c i ) = τ i .
As in [START_REF] Perrucci | Quantitative Fundamental Theorem of Algebra[END_REF], note that for n = 1, taking {-1, 1} 0 = {•}, any sequence (P 0 , P 1 ) in R[X] is a special (•, •)-chain.

Note also that Sturm sequences are always special (1, . . . , 1), (1, . . . , 1) chains.

Example 28 (Continuation of Examples 4, 11, 15 and 20) Taking σ = (1, 1) and τ = (1, 1), then (S 0 , S 1 , S 2 , S 3 ) is a special (σ, τ )-chain, with

a 1 = 1, B 1 = -X 5 , c 1 = 1, a 2 = 1, B 2 = 25(64X 3 α 3 -80X 2 α 2 β+100Xαβ 2 -125β 3 ) 256α 4 , c 2 = 1.
Taking now σ = (1, 1) and τ = (1, -1), then (T 0 , T 1 , T 2 , T 3 ) is a special (σ, τ )-chain, with

a 1 = 1, B 1 = -5X, c 1 = 25, a 2 = 25, B 2 = -25(64X 3 α 3 -80X 2 α 2 β + 100Xαβ 2 -125β 3 ), c 2 = -6400α 4 .
We will see in Section 5 how to produce special (σ, τ )-chains using Theorem 13 (Structure Theorem of Subresultants).

We introduce some more useful definition.

Definition 29 Let a, b ∈ R, n ∈ Z ≥1 , (P 0 , . . . , P n ) in R[X] \ {0} and σ, τ ∈ {-1, 1} n-1 . We define θ(σ, τ ) 0 = 1, for 1 ≤ i ≤ n -1, θ(σ, τ ) i = 1≤j≤i σ j τ j and W (σ, τ ) b a (P 0 , . . . , P n ) = 1 2 0≤i≤n-1 θ(σ, τ ) i • sign P i+1 P i , b -sign P i+1 P i , a .
Using the ideas of the proof of [START_REF] Eisermann | The fundamental theorem of algebra made effective: an elementary realalgebraic proof via Sturm chains[END_REF]Theorem 3.11], we obtain the following result for special (σ, τ )-chains. Note that no assumption on a and b is made.

Proposition 30 Let a, b ∈ R with a < b, n ∈ Z ≥1 and σ, τ ∈ {-1, 1} n-1 . If (P 0 , . . . , P n ) in R[X]\{0} is a special (σ, τ )-chain then Ind b a P 1 P 0 + θ(σ, τ ) n-1 • Ind b a P n-1 P n = W (σ, τ ) b a (P 0 , . . . , P n ).
Proof: We proceed by induction in n. If n = 1, the result follows from Proposition 26 (Inversion Formula).

Suppose now that n ≥ 2. Taking a 1 , B 1 , c 1 as in Definition 27, by Lemmas 24 and 25 we have

Ind b a P 0 P 1 + σ 1 • τ 1 • Ind b a P 2 P 1 = Ind b a -a 1 P 2 -B 1 P 1 c 1 P 1 + σ 1 • τ 1 • Ind b a P 2 P 1 = -sign(a 1 ) • sign(c 1 ) • Ind b a P 2 P 1 + σ 1 • τ 1 • Ind b a P 2 P 1 = 0.
We consider σ = (σ 2 , . . . , σ n-1 ), τ = (τ 2 , . . . , τ n-1 ) and we apply the inductive hypothesis to the special (σ , τ )-chain (P 1 , . . . , P n ). For 1 ≤ i ≤ n -1 we have that θ(σ, τ

) i = σ 1 • τ 1 • θ(σ , τ ) i-1 .
Finally, using Proposition 26 (Inversion Formula) and the inductive hypothesis, Ind b a

P 1 P 0 + θ(σ, τ ) n-1 • Ind b a P n-1 P n = Ind b a P 1 P 0 + Ind b a P 0 P 1 + σ 1 • τ 1 • Ind b a P 2 P 1 + σ 1 • τ 1 • θ(σ , τ ) n-2 • Ind b a P n-1 P n = - 1 2 sign P 1 P 0 , a + 1 2 sign P 1 P 0 , b + σ 1 • τ 1 • W (σ , τ ) b a (P 1 , . . . , P n ) = W (σ, τ ) b
a (P 0 , . . . , P n ) as we wanted to prove.

Corollary 31 Let a, b ∈ R with a < b, n ∈ Z ≥1 and σ, τ ∈ {-1, 1} n-1 . If (P 0 , . . . , P n ) in R[X] \ {0} is a special (σ, τ )-chain and P n divides P n-1 , then Ind b a P 1 P 0 = W (σ, τ ) b a (P 0 , . . . , P n ).
As mentioned in the Introduction, Theorem 6 can be deduced from Corollary 31.

Proof of Theorem 6 : Theorem 6 is a special case of Corollary 31 taking σ = (1, . . . , 1) and τ = (1, . . . , 1), since the Sturm sequence is a special ((1, . . . , 1), (1, . . . , 1))-chain and S s divides S s-1 .

Proof of the main results

We fix the notation we will use from this point.

Notation 32 Let P, Q ∈ R[X] \ {0} with deg P = p ≥ 1 and deg Q = q < p. Let (d 0 , . . . , d s ) be the sequence of degrees of the non-defective subresultant polynomials of P and Q in decreasing order and let d -1 = p + 1.

• Using the notation from Theorem 13, for

1 ≤ i ≤ s -1, let a i = t i-1 • sRes d i-1 (P, Q) ∈ R, B i = -Quot (t i • sRes d i (P, Q) • T i-1 , T i ) ∈ R[X], c i = t i • sRes d i (P, Q) ∈ R. • For 1 ≤ i ≤ s -1, let σ i = sign(a i ) ∈ {-1, 1}, τ i = sign(c i ) ∈ {-1, 1},
and let σ = (σ 1 , . . . , σ s-1 ) and τ = (τ 1 , . . . , τ s-1 ).

Lemma 33 (T 0 , . . . , T s ) is a special (σ, τ )-chain. In addition, T s divides all its elements.

Proof: Recall that T 0 = P and T 1 = Q. Also, by the Structure Theorem of Subresultants (Theorem 13), we have that for 1 ≤ i ≤ s -1,

a i T i+1 + B i T i + c i T i-1 = 0.
The claim follows from the definition of σ, τ .

The following lemma explores the relation between the signs of the leading coefficients of the subresultants polynomials.

Lemma 34 Let P, Q ∈ R[X] \ {0} with deg P = p ≥ 1 and deg Q = q < p. Following Notation 12 and 16, for 0 ≤ i ≤ s, sign(sRes d i (P, Q)) = d p(i)-1 -d i • sign(t p(i) ).

Proof: For i = 0 the result is clear. For 1 ≤ i ≤ s, by the Structure Theorem of Subresultants (Theorem 13), sign(sRes

d i (P, Q)) = d i-1 -d i • sign(t i ) d i-1 -d i • sign(sRes d i-1 (P, Q)) d i-1 -d i -1 .
We proceed then by induction on i -p(i). If i = p(i), then d i-1 -d i is odd and sign(sRes d i (P, Q)) = d p(i)-1 -d i • sign(t p(i) ).

If i > p(i), then d i-1 -d i is even, p(i) = p(i -1) and i -1 -p(i -1) < i -p(i); therefore by the inductive hypothesis, From Theorem 17, we can easily deduce Theorem 18 as follows.

Proof of Theorem 18: Theorem 13 implies that, if for some 0 ≤ i ≤ s -1, two consecutive polynomials T i and T i+1 in the sequence (T 0 , . . . , T s ) have a common root x, then every polynomial in this sequence has x as a root. So, suppose now that a and b are not common roots of T 0 = P and T 1 = Q, therefore they are not common roots of T i and T i+1 for any 0 ≤ i ≤ s -1.

The proof is finished using the formula from Theorem 17 for the Cauchy index Ind b a Q P and the identity (1).

1 2 •

 2 (-1) m • sign Q(x) P (x)if ε = -and m < 0.

Example 15 (

 15 Continuation of Example 4 and Example 11) Let us take as before P = X 5 + αX + β and suppose α = 0 and 256α 5 + 3125β 4 = 0. Looking at Example 11, we observe that, as expected given the Structure Theorem, the degrees of the non-defective subresultant polynomials are d 0 = 5, d 1 = 4, d 2 = 1, d 3 = 0, i.e. the degrees of the polynomials in the Sturm sequence given in Example 4. Moreover sResP 2 (P, P ) = 0, while sResP 3 (P, P ) is proportional to sResP 1 (P, P ) and, also, to S 2 given in Example 4. Using the notation from Theorem 13, we have T 0 = sResP 5 (P, P ) = P = X 5 + αX + β, t 0 = 1, T 1 = sResP 4 (P, P ) = P = 5X 4 + α, t 1 = 5, T 2 = sResP 3 (P, P ) = -20αX -25β, t 2 = -20α, T 3 = sResP 0 (P, P ) = 256α 5 + 3125β 4 , t 3 = 256α 5 + 3125β 4 .

Theorem 17

 17 Let a, b ∈ R with a < b and P, Q ∈ R[X] \ {0} with deg P = p ≥ 1 and deg Q = q < p. Then Ind b a

n-m- 1 ,

 1 subresultant polynomials which is as follows (see [3, Chapter 9]). Definition 21 Let s be a finite sequence of n elements in R of type s = (s n , 0, . . . , 0 0, . . .s 0, . . . m elements , )

Proposition 22

 22 Let a, b ∈ R with a < b and P, Q ∈ R[X]\{0} with deg P = p ≥ 1 and deg Q = q < p. If a and b are not roots of P , then Ind b a Q P = MVar(SResP(P, Q); a, b). Our new formula for Ind b a Q P given in Theorem 17 improves on the one from Proposition 22 in several aspects: a.i) Theorem 17 is general, there are no restrictions on a and b.

  0 and m < 0, then definingR = Q -(X -x) -m P T, we have R P = (X -x) m R P with P (x) = 0 and R(x) = Q(x) = 0. This proves that Ind ε x ε ∈ {-1,1}. The claim follows from the definition of the Cauchy index. The following property is known as the inversion formula. Proposition 26 Let a, b ∈ R with a < b and P, Q ∈ R[X] \ {0}. See [5, Theorem 3.9].

2 0≤i≤s- 1 θ

 21 sign(sResd i (P, Q)) = d i-1 -d i • sign(sRes d i-1 (P, Q)) = d i-1 -d i • d p(i-1)-1 -d i-1 • sign(t p(i-1) ) = = d i-1 -d i • d p(i)-1 -d i-1 • sign(t p(i) ) = d p(i)-1 -d i • sign(t p(i) )using equation[START_REF] Barnett | Polynomials and linear control systems[END_REF]. Now we are ready to prove Theorem 17.Proof of Theorem 17: By Corollary 31, since (T 0 , . . . , T s ) is a special (σ, τ )-chain andT s divides T s-1 , Ind b a Q P = W (σ, τ ) b a (T 0 , . . . , T s ) = 1 (σ, τ ) i • sign T i+1 T i , b -sign T i+1 T i , a .So, we only need to prove that for 0≤ i ≤ s -1, θ(σ, τ ) i = d p(i)-1 -d i • sign(t p(i) ) • sign(t i ).Indeed, using Lemma 34,θ(σ, τ ) i = 1≤j≤i σ j • τ j = 1≤j≤i sign(t j-1 ) • sign(sRes d j-1 (P, Q)) • sign(t j ) • sign(sRes d j (P, Q)) = sign(sRes d i (P, Q)) • sign(t i ) = d p(i)-1 -d i • sign(t p(i) ) • sign(t i )and we are done.

Acknowledgements: We are thankful to the anonymous referees for their helpful remarks and suggestions.

* Partially supported by the Argentinian grants UBACYT 20020160100039BA and PIP 11220130100527CO CONICET

Finally, we prove Theorem 19.

Proof or Theorem 19: We introduce the notation

. Choosing r ∈ R big enough and applying Theorem 18,

From this identity the result can be easily proved, taking into account that for i ≥ 1, t i = lc(T i ), but there is an ad-hoc definition of t 0 = 1 (and not as the leading coefficient of T 0 = P ).