Florence Fauquant-

Polyxeni Lamprou

SLICES FOR MAXIMAL PARABOLIC SUBALGEBRAS OF A SEMISIMPLE LIE ALGEBRA

Keywords: Slices, Truncated Parabolic Subalgebras, Poisson Centre. AMS Classification : 17B35, 16W22

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Throughout this paper, we are working over an algebraically closed field k of characteristic 0.

1.1. Let a be a finite dimensional algebraic Lie algebra, a * its dual space and S(a) the symmetric algebra of a. Then if {x 1 , x 2 , . . . , x n } is a basis of a, S(a) identifies with k[x 1 , x 2 , . . . , x n ], the polynomial algebra with generators x 1 , . . . , x n , and with the algebra of polynomials on a * . For any two polynomials f, g in S(a) we define the Poisson bracket of f and g by the formula :

{f, g} = n i=1 n j=1 ∂f ∂x i ∂g ∂x j [x i , x j ],
where [ , ] is the Lie bracket of a. For any two elements x, y ∈ a we have that {x, y} = [x, y] and each g → {g, f } is a derivation of the associative algebra S(a) for fixed f ∈ S(a).

We denote by ad the adjoint action of a on itself defined by its Lie bracket. Clearly, Y (a) ⊂ Sy(a) and this inclusion is in general strict. We will say that S(a) has no proper semi-invariants when equality holds. It is the case for instance when a is a truncated (bi)parabolic subalgebra of a semisimple Lie algebra, [5, lemme 2.5].

The Poisson centre Y (a) -and in particular whether or not it is a polynomial algebra -has been studied in several cases, for example in the case where a is semisimple, or a centralizer of a nilpotent element of a semisimple Lie algebra [START_REF] Panyushev | On symmetric invariants of centralisers in reductive Lie algebras[END_REF], or a (truncated) (bi)parabolic subalgebra of a semisimple Lie algebra [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF][START_REF] Fauquant-Millet | La somme des faux degrés -un mystère en théorie des invariants[END_REF][START_REF] Joseph | On semi -invariants and index for biparabolic (seaweed) algebras I[END_REF][START_REF] Joseph | On semi -invariants and index for biparabolic (seaweed) algebras II[END_REF].

1.3.

Recall that a acts via the coadjoint action on a * and denote this action still by ad. Set ind a = min ξ∈a * {codim (ad a) ξ} and call an element ξ in a * regular if codim (ad a) ξ = ind a. Denote by a * reg the set of regular elements of a * .

1.4. Assume that Y (a) is a polynomial algebra in := ind a generators. Let {f 1 , f 2 , . . . , f } be a set of homogeneous generators in Y (a) and let deg f i denote the degree of f i for all i, 1 ≤ i ≤ .

In [START_REF] Joseph | Maximal Poisson commutative subalgebras for truncated parabolic subalgebras of maximal index in sl n[END_REF] an adapted pair for a was defined as a pair (h, y) ∈ a × a * such that : (i) h is an ad-semisimple element, y is regular and (ad h) y = -y.

(ii) Let V be an ad h-stable subspace of a * such that (ad a) y ⊕ V = a * . The ad heigenvalues m i , 1 ≤ i ≤ , of an ad h-stable basis of V are all non-negative and satisfy :

ind a i=1 deg f i = ind a i=1
(m i + 1).

1.5. Recall the Slice Theorem [14, Thm 6], which obtains from the analysis of Kostant [16, Thm 5, Thm 7]:

Theorem. Assume that Y (a) is polynomial in ind a generators and let (h, y) be an adapted pair for a in the sense of 1.4. Then :

(1) The map Y (a) -→ R[y + V ] defined by restriction of functions is an isomorphism of algebras, where R[y + V ] denotes the algebra of regular functions on y + V . (2) One has m i + 1 = deg f i , for all i, 1 ≤ i ≤ ind a, up to a permutation of indices.

A linear subvariety y + V satisfying (1) of the above theorem is called a Weierstrass section [START_REF] Fauquant-Millet | Adapted pairs and Weierstrass sections[END_REF] or an algebraic slice [13, 7.6]. When a = g is a finite dimensional semisimple Lie algebra, it is well-known that the Poisson centre Y (g) is polynomial in ind g = rk g generators (for an exposition see [2, 7.3.8]). The above theorem is known as the Kostant Slice Theorem. In this case V = g x , the centralizer of x in g, where {x, h, y} is a principal sl 2 -triple with [h, x] = x, [h, y] = -y and [x, y] = h.

Let G be the adjoint group of g. The affine space y + g x is called a slice for the coadjoint action of g [13, 7.3] since every G -orbit in G(y + g x ) meets transversally y + g x at exactly one point and G(y + g x ) = g * where G(y + g x ) is the Zariski closure of G(y + g x ). Moreover in that particular case, G(y + g x ) = g * reg . (Note that in general, A(y + V ) is a proper subset of a * reg , where A is the adjoint group of a).

1.6. In [START_REF] Joseph | Polynomiality of invariants, unimodularity and adapted pairs[END_REF], under further assumptions on a, namely that a is unimodular and that its fundamental semi-invariant is an invariant, the authors showed that condition (i) of the definition of an adapted pair implies condition (ii) and actually (2) of the Theorem 1.5. Furthermore, as a consequence of [3, Thm. 1.11 (i)], any Lie algebra a such that S(a) has no proper semi-invariants is unimodular. Thus a truncated parabolic subalgebra a of a semisimple Lie algebra g is unimodular and its fundamental semi-invariant is an invariant. Since in this work we are interested precisely in truncated parabolic algebras, we will reformulate the definition of an adapted pair and the Slice Theorem, following [START_REF] Joseph | Polynomiality of invariants, unimodularity and adapted pairs[END_REF].

Definition. An adapted pair for a is a pair (h, y) ∈ a × a * such that h is an adsemisimple element, y is regular and (ad h) y = -y.

Then Theorem 1.5 becomes :

Theorem. [15, Corollary 2.3] Let a be a finite dimensional unimodular Lie algebra whose fundamental semi-invariant is an invariant (for example a is a truncated parabolic) and suppose that a admits an adapted pair (h, y). Let V be a subspace of a * such that (ad a) y ⊕ V = a * and let m i ,

1 ≤ i ≤ := ind a be the ad h-eigenvalues of an ad h-stable basis of V . If Y (a) is polynomial in generators, then (
m i + 1, 1 ≤ i ≤ .
If moreover S(a) has no proper semi-invariants then, after [6, Lemma 3.2] the Weierstrass section y + V is a slice for the coadjoint action of a, in the sense of 1.5. 1.7. Suppose that we have constructed an adapted pair (h, y) for a and retain the notations and hypotheses of Theorem 1.6. By the above, if Y (a) is polynomial, the degrees of a set of generators are {m i + 1 | 1 ≤ i ≤ }. This fact gives us indications for the polynomiality or non-polynomiality of Y (a). If for example m i < 0 for some i, or if we can choose different complements V, V on which ad h has different set of eigenvalues we conclude that Y (a) is not polynomial. For the truncated parabolic subalgebras we know by [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF] that Y (a) is included, up to a double gradation which respects the degrees, in a polynomial algebra whose degrees of generators are known, hence we have some information about the possible degrees of invariants. If this information is contradicted by the set {m i | 1 ≤ i ≤ } again we may conclude that Y (a) is not polynomial. In any case, the existence of an adapted pair restricts us to searching for invariants having a defined set of degrees.

1.8. When a is a truncated parabolic subalgebra of a semisimple Lie algebra g, we know in many cases that Y (a) is polynomial; for example, by [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF] this is always true when g has only components of type A or C and by [START_REF] Panyushev | On symmetric invariants of centralisers in reductive Lie algebras[END_REF], this is also the case when the truncated parabolic is the centralizer of the highest root vector and g is simple not of type E 8 . We will construct an adapted pair for all maximal parabolic subalgebras where we know (by the criterion of [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF], also given in Theorem 2.2.3) that the Poisson centre is polynomial. (This was done already in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF], in the case of the centralizer.)

Acknowledgements. We thank A. Joseph for suggesting this problem to us and in general for introducing us to truncated parabolic subalgebras and adapted pairs many years ago.

2.

The truncated parabolic subalgebra and the centre of its symmetric algebra 2.1. Truncated parabolic subalgebras of g.

2.

1.1. Let g be a finite dimensional semisimple Lie algebra, h a fixed Cartan subalgebra of g, ∆ the root system of g with respect to h and π a chosen set of simple roots. We will adopt the labeling of [1, Planches I-IX] for the simple roots in π.

Let ∆ + (resp. ∆ -) denote the set of positive (resp. negative) roots. One has that ∆ -= -∆ + and ∆ = ∆ + ∆ -. For any α ∈ ∆, let g α denote the corresponding root space of g.

Then g = n ⊕ h ⊕ n -, where n = α∈∆ + g α and n -= α∈∆ - g α . For all α ∈ π, denote by α ∨ the corresponding coroot. One has that h = α∈π k α ∨ .
2.1.2. For any subset π of π, we will denote by ∆ π the set of roots generated by π . We also denote by ∆ + π , ∆ - π the sets of positive and negative roots in ∆ π respectively. One defines the standard parabolic subalgebra p π to be the algebra

p π = n ⊕ h ⊕ n - π where n - π = α∈∆ - π g α . Its opposed algebra then is p - π = n -⊕ h ⊕ n π , with n π defined
similarly. The dual algebra p * π identifies with p - π via the Killing isomorphism ϕ. 2.1.3. For any parabolic subalgebra p π of a simple Lie algebra g such that π π, the Poisson centre of S(p π ) reduces to scalars [8, 7.9]. In [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF] and [START_REF] Fauquant-Millet | La somme des faux degrés -un mystère en théorie des invariants[END_REF], the authors study the Poisson semicentre Sy(p π ) of S(p π ). Since p π is algebraic there exists a canonical truncation p π ,E of p π such that Sy(p π ) = Y (p π ,E ) = Sy(p π ,E ) [5, 2.4, 2.5, B.2]. In [5, Section 5] p π ,E has been described explicitly. It has the form

p π ,E = n ⊕ h E ⊕ n - π ,
where h E is a truncation of h; it is called the truncated Cartan subalgebra. Its description involves some combinatorics of the Dynkin diagram of g, which we describe below.

2.1.4. Define an involution j on π by j = -w 0 , where w 0 denotes the longest element in the Weyl group of ∆. Extend the involution i = -w 0 of π , where w 0 denotes the longest element in the Weyl group of ∆ π , on π \ π as follows. For all α ∈ π \ π , if j(α) ∈ π \ π set i(α) = j(α). If now j(α) ∈ π let r be the smallest integer such that j(ij) r (α) / ∈ π and set i(α) = j(ij) r (α). Let ij denote the group generated by the element ij and E the set of ij -orbits in π.

Set E 1 := {Γ ∈ E | jΓ = Γ} and E 2 := {Γ ∈ E | jΓ = Γ}. One has E = E 1 E 2 .
Notice that an orbit Γ in E is also an i, j (the group generated by i and j) -orbit if and only if Γ ∈ E 2 . The index of p π ,E is equal to the number of the ij -orbits in π, that is ind p π ,E = Card E [8, 7.14].

2.1.5. Denote by the standard length function on the Coxeter group i, j and let { α } α∈π be the set of fundamental weights of g (sometimes we write { i } α i ∈π ). For all Γ ∈ E which does not lie entirely in π , define h Γ = s∈ i, j (-1) (s) ϕ -1 ( sα ) for a choice of α ∈ Γ. For simplicity, we will write h Γ = s∈ i, j (-1) (s) sα . Denote by E 1 the subset of E 1 of orbits which meet π \ π . Define p π to be the derived subalgebra of p π ,

p π = [p π , p π ]. Set h = p π h and h E = h + Γ∈E 1 k h Γ . It turns out that the latter sum is direct. Then p π ,E is the algebra p π ,E = n ⊕ h E ⊕ n - π .
2.1.6. When j = id, which is true in all cases outside type A n , D 2n+1 and E 6 , one has that ij = i, j = i , E 1 = ∅ and E = E 2 . The involution i extends on π \ π by the identity. It then follows that for Γ ∈ E either Γ ⊂ π \ π or Γ ⊂ π . In the former case, Γ is a singleton. Moreover h E = h . 2.1.7. For a truncated maximal parabolic p π ,E associated to π = π \ {α s }, one has always i(α s ) = α s , even when j = id. Thus E 1 = ∅ and then h E = h . 2.2. The Poisson centre of p π ,E . As we already said, the algebra Sy(p π ) = Y (p π ,E ) has been studied in [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF], [START_REF] Fauquant-Millet | La somme des faux degrés -un mystère en théorie des invariants[END_REF]. More precisely, there have been found certain upper and lower bounds for Sy(p π ); when these bounds coincide, the algebra Sy(p π ) is polynomial in ind p π ,E generators. In this case, the weights and the degrees of a set of homogeneous generators have been computed explicitly. In this section, we will briefly describe the criterion of [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF], which implies the polynomiality of Y (p π ,E ). We first need some further background, namely the notion of the Kostant cascade.

2.2.1.

(See also [7, 2.2]). Let g be as in section 2.1.1 and set III] for every simple Lie algebra g. The set β π of strongly orthogonal positive roots for a simple Lie algebra g, which may be also found in [7, Tables I andII], is given for the reader's convenience in Table I where the indexation of the simple roots is as in [1, Planches I-IX].

D = {λ ∈ h * R | (λ, α) ≥ 0, ∀α ∈ π} where h * R is the real subspace of h * generated by π. Given λ ∈ D, define ∆ ± λ = {α ∈ ∆ ± | (λ, α) = 0}, ∆ λ = ∆ + λ ∪ ∆ - λ . Let ∆ = i ∆ i be
If the initial root system ∆ is irreducible of type A, C, E 6 , F 4 , G 2 , the subsystems are also irreducible and hence the Kostant cascade K and the set β π are totally ordered. Thus in these cases, the elements β K , K ∈ K, may be simply indexed by N, and are denoted by β i , 1 ≤ i ≤ card(K). We understand β i < β j if and only if i < j.

In other types, the order ≤ on K is not a total order. For the elements β K , K ∈ K, we use the notations β i , β i , for type B n or D 2n+1 , or β i , β i and β i for type D 2n , E 7 or E 8 with order relation β i < β j if and only if i < j, and β i < β i , β i .

For any rational number r ∈ Q denote by [r] the integer such that, r -1 < [r] ≤ r.

Type The set β π of strongly orthogonal positive roots

A n β i = α i + • • • + α n+1-i ; 1 ≤ i ≤ [(n + 1)/2] with βn+1 2 = α n+1 2 if n is odd B n β i = α 2i-1 + 2α 2i + • • • + 2α n ; 1 ≤ i ≤ [(n + 1)/2] with βn+1 2 = α n if n is odd β i = α 2i -1 ; 1 ≤ i ≤ [n/2] C n β i = 2α i + • • • + 2α n-1 + α n ; 1 ≤ i ≤ n, with β n = α n D n β i = α 2i-1 + 2α 2i + • • • + 2α n-2 + α n-1 + α n ; 1 ≤ i ≤ [n/2] -1 β i = α 2i -1 ; 1 ≤ i ≤ [n/2] -1 and βn-1 2 = α n-2 + α n-1 + α n if n is odd, β n 2 = α n if n is even β ( n-2 2 ) = α n-1 if n is even E 6 β 1 = α 1 + 2α 2 + 2α 3 + 3α 4 + 2α 5 + α 6 β 2 = α 1 + α 3 + α 4 + α 5 + α 6 β 3 = α 3 + α 4 + α 5 β 4 = α 4 E 7 β 1 = 2α 1 + 2α 2 + 3α 3 + 4α 4 + 3α 5 + 2α 6 + α 7 β 2 = α 2 + α 3 + 2α 4 + 2α 5 + 2α 6 + α 7 β 3 = α 2 + α 3 + 2α 4 + α 5 β 4 = α 3 β 2 = α 7 , β 3 = α 5 , β 3 = α 2 E 8 β 1 = 2α 1 + 3α 2 + 4α 3 + 6α 4 + 5α 5 + 4α 6 + 3α 7 + 2α 8 β 2 = 2α 1 + 2α 2 + 3α 3 + 4α 4 + 3α 5 + 2α 6 + α 7 β 3 = α 2 + α 3 + 2α 4 + 2α 5 + 2α 6 + α 7 β 4 = α 2 + α 3 + 2α 4 + α 5 β 5 = α 3 β 3 = α 7 , β 4 = α 5 , β 4 = α 2 F 4 β 1 = 2α 1 + 3α 2 + 4α 3 + 2α 4 β 2 = α 2 + 2α 3 + 2α 4 β 3 = α 2 + 2α 3 β 4 = α 2 G 2 β 1 = 3α 1 + 2α 2 β 2 = α 1 Table I
2.2.2. We will slightly digress in order to introduce the sets H β K , K ∈ K and some of their properties that will be useful in the sequel. For A ⊂ ∆, denote by

-A = {α ∈ ∆ | -α ∈ A}. For all K ∈ K set H β K = {γ ∈ ∆ K | (γ, β K ) > 0} and H -β K = -H β K . By [7, Lemma 2.2],
we have the following :

(1) In this case, Sy(b) is a polynomial algebra in rk g generators [START_REF] Joseph | A preparation theorem for the prime spectrum of a semisimple Lie algebra[END_REF]. The generators of the free semigroup B π may be found in [7, Tables I andII] and in [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF]Table].

H β K = ∆ + K \ (∆ + K ) β K . (2) ∆ + = L∈K H β L and ∆ -= L∈K H -β L . (3) If α ∈ H β K \ {β K }, then β K -α ∈ H β K \ {β K }. (4) Given α, α ∈ H β K , if α + α ∈ ∆, then α + α = β K . (5) If α ∈ H β K , α ∈ H β L are such that α + α ∈ ∆, then K ≤ L (resp. L ≤ K) and α + α ∈ H β K (resp. α + α ∈ H β L ). In particular, if α + α = β K , then K = L and α, α ∈ H β K \ {β K }. (6) |H β K ∩ π| = 1 if ∆ K is not of type A and 2 if it is. In fact, H β i ∩ π =    {α i , α n+1-i }, in type A. {α 2i }, in type BD. {α i }, in type C. 2.2.3. Recall that { α } α∈π is
Set for all Γ ∈ E :

ε Γ = 1/2, if Γ = jΓ, α∈Γ α ∈ B π , α∈Γ∩π α ∈ B π , 1, otherwise. Theorem. [4, Thm. 7.3]. If ε Γ = 1 for all Γ ∈ E, then the algebra Y (p π ,E ) is polynomial in |E| = ind p π ,E generators. In particular, when g is simple of type A or C, then ε Γ = 1, for all Γ ∈ E.
Remarks.

(1) The bounds for Sy(p π ) that we mentioned in the beginning of 2.2 coincide precisely when ε Γ = 1 for all Γ ∈ E. (2) Examples where the bounds do not coincide but Y (p π , E ) is still polynomial are known (see for instance [START_REF] Joseph | A preparation theorem for the prime spectrum of a semisimple Lie algebra[END_REF] for the Borel case or [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF] for the centralizer of the highest root vector, which is a particular truncated parabolic algebra). (3) In [START_REF] Yakimova | A counterexample to Premet's and Joseph's conjectures[END_REF] there has been found an example where Y (p π ,E ) is not polynomial. This is the case of the maximal parabolic subalgebra of g of type E 8 with π = π \ {α 8 } (in the Bourbaki notation [1, Planche VII]). In this case, p π ,E = g x β , where β is the unique highest root of g and x β ∈ g β \ {0}.

The construction of an adapted pair

Recall the definition of an adapted pair of Section 1.6. In [START_REF] Joseph | Slices for biparabolic coadjoint actions in type A[END_REF], an adapted pair is constructed for all truncated (bi)parabolic subalgebras of sl n . In the following sections we will construct an adapted pair -whenever possible -for all maximal truncated parabolic subalgebras in the remaining types when the bounds of [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF] coincide. By a maximal parabolic we mean that π = π \ {α s }.

Remark. The reason that we restrict ourselves to the maximal parabolic case unlike the case of sl n where an adapted pair has been constructed for all parabolic subalgebras is that for sl n the truncated Cartan subalgebra is never too small. By contrast, when j = id and so h E = h , the truncated Cartan subalgebra may be very small or even {0} in the case of the truncated Borel. We will see in Section and then the coadjoint action is computed through commutation in g mod h ⊥ E ⊕ m -. 3.1. Heisenberg sets. For A ⊂ ∆, set g A := α∈A g α , which is a subspace of g and a Lie subalgebra of g if A is additively closed in ∆.

Definition. For any γ ∈ ∆, a subset Γ γ of ∆ is called a Heisenberg set of centre γ if γ ∈ Γ γ and for all α ∈ Γ γ \{γ}, there exists a unique α ∈ Γ γ such that α+α = γ.

Remark. For a fixed γ, there exist several Heisenberg sets Γ γ of centre γ. All of them are included in a maximal one, namely the set of all decompositions of γ into the sum of two roots in ∆. (Note that an ij -orbit in π was also denoted by Γ; we will be very careful not to have any confusion). 3) and actually it is the maximal Heisenberg set of centre β K , which is included in ∆ + . Moreover, by 2.2.2 (4), g H β K is a Heisenberg Lie algebra of centre g β K . For an arbitrary Γ γ it is no longer true that g Γγ is a Heisenberg Lie algebra or even a Lie subalgebra of g; however, inspired by this example, we called the sets Γ γ Heisenberg sets.

Example. Recall the sets

H β K , K ∈ K defined in 2.2.2. One has that H β K is a Heisenberg set of centre β K by 2.2.2 (
If Γ γ is a Heisenberg set of centre γ, then -Γ γ = Γ -γ is a Heisenberg set of centre -γ. We set Γ 0 γ := Γ γ \ {γ}. Similarly, we define H 0 β K .

3.2.

The following lemma can be found in [START_REF] Joseph | Slices for biparabolic coadjoint actions in type A[END_REF]Lemma 8.5]:

Lemma. Let Γ ± be subsets of ∆ ± and suppose there exist subsets S ± of Γ ± such that Γ ± = γ∈S ± Γ γ , where Γ γ is a Heisenberg set of centre γ, for all γ ∈ S ± . Set

S = S + S -and O ± = γ∈S ± Γ 0 γ . Set also o = γ∈S g -Γ 0 γ = g -O + ⊕ g -O -.
Assume further that the elements of S are linearly independent and that if α, β ∈ O ± are such that α

+ β = γ, for some γ ∈ S ± , then α, β ∈ Γ 0 γ . Set f = γ∈S a γ x γ ,
where a γ are non-zero scalars for all γ ∈ S. Then the bilinear form

Φ f : g × g → k defined by Φ f (x, x ) = K(f, [x, x ]
) for all x, x ∈ g, where K is the Killing form on g, is non-degenerate on o × o.

When S + = β π + , S -= -β π -for two subsets π + , π -⊂ π and Γ γ = H γ for all γ ∈ S, the above result follows from [19, Remarque 3.9].

Lemma.

Suppose π ⊂ π is a subset of π and let p π ,E be the corresponding truncated parabolic subalgebra. Let S + , T + ⊂ ∆ + and S -, T -⊂ ∆ - π be such that the following conditions hold :

(1) For all γ ∈ S ± there exist Heisenberg sets Γ γ of centre γ such that,

Γ + := ∆ + \ T + = γ∈S + Γ γ , and
Γ -:= ∆ - π \ T -= γ∈S - Γ γ . Set O ± = γ∈S ± Γ 0 γ .
(

) If α, β ∈ O ± are such that α + β = γ for some γ ∈ S ± then α, β ∈ Γ 0 γ . ( 2
) Set S = S + S -. Then S| h E is a basis of h * E . (4) Set T = T + T -. Then |T | = ind p π ,E . 3
Then the element y := γ∈S x γ is regular and

g T := α∈T g α is a complement of the ad p - π ,E -orbit of y in p π ,E , that is (ad p - π ,E ) y ⊕ g T = p π ,E .
Proof. The proof is similar to that of [START_REF] Joseph | Slices for biparabolic coadjoint actions in type A[END_REF]Theorem 8.6]. We will give it for completeness. Retain the notations of Lemma

E = (ad g -S ) y + o * ⊕ g S ⊕ g T . Hence p π , E = h E ⊕ o * ⊕ g S ⊕ g T ⊂ (ad p - π , E ) y + g T .
Finally, condition (4) forces the latter sum to be direct, since dim g T = ind p π ,E ≤ codim(ad p - π ,E ) y.

3.4.

The corollary below follows from Theorem 1.6 and Lemma 3.3 :

Corollary. Suppose that the hypotheses of the previous lemma hold for p π ,E and define h ∈ h E by setting α(h) = -1 for all α ∈ S. Then (h, y) is an adapted pair for p π ,E . If, in addition, Y (p π ,E ) is polynomial in ind p π ,E generators, then y + g T is a slice for the coadjoint action of p - π ,E .

3.4.1.

In the following sections we construct an adapted pair for maximal parabolic subalgebras for which Y (p π ,E ) is known to be polynomial, that is when Theorem 2.2.3 applies. By the above, it is enough to choose, when possible, two subsets S, T of ∆ + ∆ - π which satisfy the conditions of Lemma 3.3. As we will see, in most cases, we choose sets S + , T + , with T + ⊂ π such that S + T + = β π and S -, T -, with T -⊂ -π such that S -T -= -β π . Then for all β ∈ S, we take Γ β = H β , as defined in 2.2.2. By the easy observation that if β ∈ π, then H β = {β}, we conclude that with these choices condition (1) of Lemma 3.3 is satisfied by 2.2.2 (2). Moreover, condition (2) follows by 2.2.2 [START_REF] Fauquant-Millet | La somme des faux degrés -un mystère en théorie des invariants[END_REF]. Hence in these cases, it only remains to verify conditions (3) and (4).

As adapted pairs were already constructed for all truncated biparabolic subalgebras of sl n [START_REF] Joseph | Slices for biparabolic coadjoint actions in type A[END_REF], we will not consider this case.

Type B

Let g be simple of type B n (n ≥ 2) and π = π \ {α s }, for some 1 ≤ s ≤ n. The truncated parabolic p π ,E is then equal to p π ,E = n ⊕ h ⊕ n - π , where recall that h is the Cartan subalgebra of the derived algebra of p π . Its Levi factor l π is the product of two simple Lie algebras, one of type A s-1 and the other of type B n-s . In particular, if s = 1 one has that l π = so 2n-1 and if s = n, l π = sl n .

4.1. Orbits. Since w 0 = -id one has that j = id and i is as follows :

i(α t ) = α s-t , 1 ≤ t ≤ s -1 α t , s ≤ t ≤ n Hence the ij -orbits of π are Γ t = {α t , α s-t }, 1 ≤ t ≤ [ s 2 ] and Γ t = {α t }, s ≤ t ≤ n. Then | E |= [ s 2 ] + n -s + 1. By Theorem 2.2.3, if s is odd, Y (p π E ) is polynomial, since ε Γ = 1 for all Γ ∈ E.
If s is even the theory of [START_REF] Fauquant-Millet | Semi-centre de l'algèbre enveloppante d'une sous-algèbre parabolique d'une algèbre de Lie semi-simple[END_REF] does not guarantee us that Y (p π ,E ) is polynomial. However, when s = 2, then p π ,E equals the centralizer of the nilpotent element corresponding to a non-zero highest root vector x β 1 , that is p π ,E = g x β 1 , and by [START_REF] Panyushev | On symmetric invariants of centralisers in reductive Lie algebras[END_REF] Y (p π ,E ) is polynomial. Moreover, in this case an adapted pair was constructed in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF].

Below, we will construct an adapted pair when s is odd and will give the adapted pair of [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF] for s = 2.

Construction of an adapted pair.

Here we assume that π = π \ {α s } with s odd. Note that in this case ind p π ,E =| E |= n -s-1 2 . 4.2.1. The sets S and T . Recall the maximal set β π of strongly orthogonal roots we introduced in section 2.2.1 and in particular Table I. Denote by β 0 π the set

β 0 π = β π \ (β π ∩ π).
The subset π is a union of two connected components, π 1 of type A s-1 and π 2 of type B n-s . One has that

β π 1 = {β i := α i + α i+1 + • • • + α s-i | 1 ≤ i ≤ s-1 2 }. In particular, since s is odd β 0 π 1 = β π 1 . Also, β 0 π 2 = {β i := α s+2i-1 + 2α s+2i + . . . + 2α n | 1 ≤ i ≤ [ n-s 2 ]} and β π 2 ∩ π 2 = {α s-1+2i | 1 ≤ i ≤ [ n+1-s 2 ]}.
For S we choose S = S + S -, where S + = β 0 π and S -= (-β π 1 ) ∪ (-β 0 π 2

). For T we choose T = T + T -where T + = β π ∩ π and T -= -(β π 2 ∩ π 2 ).

4.2.2.

Choice of Heisenberg sets. For all β ∈ S we take Γ β = H β , as defined in 2.2.2. Notice that S + T + = β π and S -T -= -β π . By 3.4.1, conditions (1) and (2) of Lemma 3.3 are satisfied. Condition (4) is also satisfied, since | T |= n -s-1 2 = ind p π , E . It remains to verify condition (3).

Lemma. For the above choice of S, one has that

S| h E is a basis for h * E . Proof. Let S = {s j | 1 ≤ j ≤ n -1} and take for a basis of h E the set {α ∨ i | 1 ≤ i ≤ n, i = s}. It is enough to show that the determinant of the matrix (α ∨ i (s j )) i, j is non-zero.
First of all notice that for all i, with 1

≤ i ≤ [n/2], β i = c i 2i -2i-2
, where c n/2 = 2 when n is even and c i = 1 otherwise. (Here we have set 0 = 0.) Similarly,

β i = d i s+2i -s+2i-2 ,
= d [ n-s 2 ] det F . Finally, F = -(α ∨ 2i-1 (β j )) and each of the α 2i-1 , 1 ≤ i ≤ s-1 2
, lies in exactly one H β j by 2.2.2 [START_REF] Fauquant-Millet | Adapted pairs and Weierstrass sections[END_REF]. Recall that

{β i | 1 ≤ i ≤ s-1
2 } is the set β π 1 of strongly orthogonal roots of π 1 , which is of type A s-1 . In particular, they are totally ordered by the order defined in 2.2.1. With the notations of 2.2.1,

∆ + i+1 = ∆ + β i and ∆ + i+1 ⊂ ∆ + i for all i, with 1 ≤ i ≤ s-1
2 (where we set ∆

+ 1 = ∆ + π 1
). Moreover, by 2.2.2 (1) and the above,

H β i ⊂ ∆ + β i-1 = ∆ + i . Let α t j ∈ H β j , with {α t j | 1 ≤ j ≤ s-1 2 } = {α 2i-1 | 1 ≤ i ≤ s-1 2 }.
Then up to a sign, det F = det (α ∨ t i (β j )) and the latter is an upper triangular matrix with 1 on the diagonal. In particular, det F = 0. 4.2.4. Now take π = π \ {α 2 }; as we already said, an adapted pair has been constructed in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF].

The sets S and T are given in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF]Tables] for B n , n ≥ 3 as follows:

S = {α 2 , α 3 , . . . , α n-1 , α 1 + α 2 + . . . + α n } and T = {α i + 2(α i+1 + . . . + α n ), 1 ≤ i ≤ n -1, -α 1 }.

Type D

As expected, type D is almost identical with B. We will give the details for completeness.

Let g be simple of type D n (n ≥ 4) and π = π \ {α s } for some 1 ≤ s ≤ n. If 1 ≤ s ≤ n -3, then the Levi factor l π of the truncated parabolic subalgebra p π , E is the product of two simple Lie algebras, one of type A s-1 and another of type D n-s (in particular, if s = 1, l π is a simple Lie algebra of type D n-1 ).

If s = n -2, then the Levi factor l π is the product of three simple Lie algebras, of types A n-3 , A 1 and A 1 .

Finally, if s = n -1 or s = n, then l π is a simple Lie algebra of type A n-1 .

5.1. Orbits. Recall that j = id if n is even and, if n is odd, j is the involution of π that interchanges α n-1 and α n and fixes the rest of the simple roots. By Theorem 2.2.

3 one can show that Y (p π , E ) is polynomial (that is ε Γ = 1 for all Γ ∈ E) if
s is odd or s = n -1 and s is even. Since the cases s = n, n -1 are symmetric, we may consider that s is odd. Note that then n, n -s have different parity.

We will compute the ij -orbits in π when s is odd. Assume first that 1 ≤ s ≤ n -2. The ij -orbits of π are Γ t = {α t , α s-t },

1 ≤ t ≤ s-1 2 , Γ t = {α t }, s ≤ t ≤ n -2 and Γ n-1 = {α n-1 , α n }. Then |E| = n -s+1 2 . Assume that s = n and is odd. The ij -orbits in π are Γ t = {α t , α n-t }, 2 ≤ t ≤ n-1 2 and Γ 1 = {α 1 , α n-1 , α n }. Then |E| = n-1 2 .
In [START_REF] Panyushev | On symmetric invariants of centralisers in reductive Lie algebras[END_REF], the authors show that for s = 2, Y (p π ,E ) is also polynomial; an adapted pair is constructed in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF] in this case -we give it at the end of this section. I) and β 0 π as defined in 4.2.1. Note in particular that

|β 0 π | = n-1 2 if n odd and |β 0 π | = n 2 -1 if n even and that n, n -s have different parity. Set β 0 π = {β i | 1 ≤ i ≤ n-1 2 } if n is odd and β 0 π = {β i | 1 ≤ i ≤ n 2 -1} if n is even. Then, in the former case, we have β 0 π 2 = {β i | 1 ≤ i ≤ n-s
2 -1} and in the latter

β 0 π 2 = {β i | 1 ≤ i ≤ n-s-1 2 }.
The roots β i are given by the formulae of Table I

for type D by shifting i → s + i. Also β π 1 = β 0 π 1 = {β i | 1 ≤ i ≤ s-1
2 }, where the β i are given by the formulae of Table I for Type A by setting n = s -1.

Set now S + = β 0 π if n is odd and

S + = β 0 π {α n } if n is even. Set also S -= (-β 0 π 1 ) (-β 0 π 2 ) if n is even and S -= (-β 0 π 1 ) (-β 0 π 2 ) {-α n } if n is odd. Set T + = β π ∩ π if n is odd and T + = (β π ∩ π) \ {α n } if n is even. Set also T -= -(β π 2 ∩ π 2 ) \ {-α n } if n is odd and T -= -(β π 2 ∩ π 2 ) if n is even. Take T = T + T -. In both cases, |T | = n -s+1 2 = ind p π ,E . Assume now that s = n and is odd. Then π is of type A n-1 . Let {β i | 1 ≤ i ≤ n-1
2 } be the elements in β π as noted in Table I andβ

π = {β i := α i + . . . + α n-i | 1 ≤ i ≤ n-1 2 }. We choose S + = {β i | 1 ≤ i ≤ n-1 2 } = β 0 π , S -= -β π and S = S + S -. For T ± we choose T + = β π ∩ π = {α 2i-1 , 1 ≤ i ≤ n-1 2 }, T -= ∅ and T = T + . Then | T |= n-1 2 =| E |= ind p π , E .

5.2.3.

Finally take π = π \ {α 2 }, and n ≥ 4, which is the case when the truncated parabolic subalgebra coincides with the centralizer of the highest root vector. An adapted pair has been constructed in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF]. The sets S and T are given in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF]Tables] for D n , n ≥ 4 as follows:

S = {α 2 , α 3 , . . . , α n-2 , α 1 + α 2 + . . . + α n-1 , α 1 + α 2 + . . . + α n-2 + α n }
and

T = {α i + 2α i+1 + . . . + 2α n-2 + α n-1 + α n , 1 ≤ i ≤ n -2, α n , -α 1 }.

Type C

Let g be a simple Lie algebra of type C n (n ≥ 3) and π = π \{α s }, with 1 ≤ s ≤ n. Then π = π 1 ∪ π 2 , where π 1 is of type A s-1 and π 2 is of type C n-s . The Levi factor l π of the truncated parabolic p π , E is the product l π = sl s × sp 2(n-s) . By Theorem 2.2. 3,Y (p π ,E ) is polynomial in ind p π ,E generators for all s, with 1 ≤ s ≤ n.

6.1. Orbits. The involutions of the Dynkin diagram j and i are given by j = id and :

i(α t ) = α s-t , 1 ≤ t ≤ s -1. α t , s ≤ t ≤ n.
Hence the ij = i -orbits of the Dynkin diagram are

Γ t = {α t , α s-t }, 1 ≤ t ≤ [s/2]. {α t }, s ≤ t ≤ n.
S ∪ T = β π ∪ (-β π ).
In type C n such a choice would not work; notice in particular that

β π 2 ⊂ β π . Recall that β 0 π 1 denotes the set β π 1 \ (β π 1 ∩ π 1 )
. Denote by β i the elements in β π , and β i the elements in

β π 1 . For all i with 1 ≤ i ≤ n -1 set γ i = β i -α i .
We will distinguish the following two cases : (i) If s is odd, we choose

S + = {γ 2i-1 ; 1 ≤ i ≤ [n/2]}, S -= {-γ 2j ; (s + 1)/2 ≤ j ≤ [(n -1)/2]} ∪ (-β π 1 )
and

T + = {β 2i-1 ; 1 ≤ i ≤ [(n + 1)/2]}, T -= {-β 2j ; (s + 1)/2 ≤ j ≤ [n/2]}.
(ii) If s is even set t := [s/4] and choose

S + = {γ 2i-1 ; 1 ≤ i ≤ t, β 2t+1 , γ 2j ; t + 1 ≤ j ≤ [(n -1)/2]}, S -= {-γ 2j-1 ; s/2 + 1 ≤ j ≤ [n/2]} ∪ (-β 0 π 1 ) and
T + = {β 2i-1 ; 1 ≤ i ≤ t, β 2j ; t + 1 ≤ j ≤ [n/2]}, T -= {-β 2j-1 ; s/2 + 1 ≤ j ≤ [(n + 1)/2], -β s/2 }.
6.2.2. Choice of Heisenberg sets. Set S = S + S -. For every γ ∈ S, we will define a Heisenberg set of centre γ, Γ γ .

For all γ ∈ S ∩(β π ∪(-β π )), we set Γ γ = H γ . For the rest of the roots in S, namely the γ i , (resp.

-γ i ) we define Γ γ i := H 0 β i H β i+1 (resp. Γ -γ i = H 0 -β i H -β i+1 = -Γ γ i ).
It is better to view these sets schematically, using certain (shifted) Young tableaux that we define right below. These diagrams were used in [START_REF] Shi | The number of -sign types[END_REF] for a different purpose.

We display the positive roots in a shifted diagram T (C n ) of shape (2n -1, 2n -3, . . . , 1), that is we assign to each box (i, j) of T (C n ) the positive root t i, j , where :

t i, j = α i + • • • + 2(α j + • • • + α n-1 ) + α n , i ≤ j ≤ n -1. α i + • • • + α 2n-j , n ≤ j ≤ 2n -i.
For example, the diagram for C 3 is :

2α 1 + 2α 2 + α 3 α 1 + 2α 2 + α 3 α 1 + α 2 + α 3 α 1 + α 2 α 1 2α 2 + α 3 α 2 + α 3 α 2 α 3
Notice that for all i, with 1 ≤ i ≤ n, the i -th line of T (C n ) is the Heisenberg set H β i , with the centre β i lying on the (i, i) box, i.e. H β i = {t i, j | i ≤ j ≤ 2n -i} and t i, i = β i . The right corners of the diagram correspond to the simple roots.

One has that

γ i = β i -α i = t i, i+1 for all i, with 1 ≤ i ≤ n -1. Then Γ γ i is the set Γ γ i = {t , m | ∈ {i, i + 1}, m ≥ i + 1}. We will show that it is a Heisenberg set of centre t i, i+1 . Then of course, Γ -γ i = -Γ γ i will be a Heisenberg set of centre -γ i . Lemma. Let Γ γ i be the set Γ γ i = {t , m | ∈ {i, i + 1}, m ≥ i + 1}. For all j, with i + 1 ≤ j ≤ 2n -i -1, one has : t i+1, j + t i, 2n+1-j = t i, i+1 .
In particular, Γ γ i is a Heisenberg set of centre t i, i+1 (= γ i ).

Proof. For j ≤ n -1 one has :

t i+1, j + t i, 2n+1-j = α i+1 + • • • + 2(α j + • • • + α n-1 ) + α n + α i + • • • + α j-1 = α i + 2(α i+1 + • • • + α n-1 ) + α n = t i, i+1 .
For j = n we have :

t i+1, n + t i, n+1 = (α i+1 + • • • + α n ) + (α i + • • • + α n-1 ) = t i, i+1
.

The cases j = n + 1 and j ≥ n + 2 follow by similar calculations. We conclude that for every t ∈ Γ γ i \ {γ i }, there exists a (unique) t ∈ Γ γ i \ {γ i }, such that t + t = γ i and Γ γ i is a Heisenberg set.

6.2.3. Decomposition into Heisenberg sets. We will show that the sets Γ ± :=

γ∈S ± Γ γ defined in the previous section complement T ± in ∆ + (resp. ∆ - π ), i.e. ∆ + = Γ + T + , ∆ - π = Γ -T -.
This easily follows by the decomposition in 2.2.2 (2). Indeed, take for example the case s odd. Then

Γ + = [n/2] i=1 (H 0 β 2i-1 H β 2i ). Clearly, a complement of this in ∆ + is T + .
Similarly,

Γ -=   (s-1)/2 i=1 H -β i     [(n-1)/2] i=(s+1)/2 (H 0 -β 2i H -β 2i+1 )   .
Again, a complement of this set in ∆ - π is T -. The case s even follows similarly. 6.2.4. We will show that condition (2) of Lemma 3.3 holds.

Set

O ± = γ∈S ± Γ 0 γ .
Lemma. If any two roots α, β ∈ O ± satisfy α + β = γ, for some γ ∈ S ± then α, β ∈ Γ 0 γ . Proof. We will prove the statement for O + . Suppose that α + β = γ and γ ∈ S + . Since Γ γ is a Heisenberg set, it is enough to show that α ∈ Γ 0 γ (or β ∈ Γ 0 γ ). Notice that the elements of S + are all of the form γ i or β i ∈ β π . In the latter case, lemma follows by 2.2.2 [START_REF] Fauquant-Millet | La somme des faux degrés -un mystère en théorie des invariants[END_REF].

Let us suppose that γ = γ i = β i -α i . Then γ ∈ H 0 β i and again by 2.2.2 (5), α ∈ H β i (or β ∈ H β i ). Let us assume the former holds. Since all roots γ, α, β are positive, we have γ > α (here > denotes the usual partial order of the root lattice). Since both γ, α are in

H β i and γ ∈ H 0 β i , one has that α ∈ H 0 β i . But H 0 β i ⊂ Γ γ , hence α ∈ Γ γ and then α ∈ Γ 0 γ .
6.2.5. Lemma. One has that S| h E is a basis for h * E .

Proof. We take for a basis of h E the set

{α ∨ i | 1 ≤ i ≤ n, i = s}. We need to show that if S = {s j | 1 ≤ j ≤ n -1} one has that det (α ∨ i (s j )) i,j = 0.
We may order the s j ∈ S and the α ∨ i ∈ h * E in a way such that the matrix (α ∨ i (s j )) i,j is upper triangular with diagonal elements non-zero. First notice that γ i = i+1i-1 , for all i, with 1 ≤ i ≤ n -1, where we have set 0 = 0.

Assume that s is odd.

By rearranging the rows, we may write the matrix (α ∨ i (s j )) i,j as

A B 0 C by taking A to be the [n/2] × [n/2] matrix A = (α ∨ 2i (γ 2j-1 )) [n/2]
i, j=1 . Then A is upper triangular and has 1 on the diagonal, hence det A = 1 and det(α ∨ i (s j )) i, j = det C. Similarly, we may write

C as C = D 0 0 F , with D the [(n -s)/2] × [(n -s)/2] matrix D = -(α ∨ s+2i (γ s+1+2(j-1) )) [(n-s)/2] i,j=1
. Then det D = (-1)

[(n-s)/2] , hence det C = det F up to a sign. Finally, F = -α ∨ 2i-1 (β j ) (s-1)/2 i, j=1
. By 2.2.2 (6), one observes that each of the simple roots α 2i-1 , 1 ≤ i ≤ (s -1)/2 lies in exactly one H β j . A similar argument as in the end of the proof of Lemma 4.2.3 allows us to conclude that det F = 0.

Assume that s is even and note that β 2t+1 = 2 2t+1 -2 2t . We may again write the matrix as A B 0 C by taking A to be the t × t matrix A = (α ∨ 2i (γ 2j-1 )) t i, j=1 . Then A is upper triangular and has 1 on the diagonal, hence det A = 1 and det(α ∨ i (s j )) i, j = det C . Similarly, we may write C as C = D E 0 F , with

D the matrix D = (α ∨ 2i-1 (γ 2j-2 )) [(n+1)/2] i, j=t+1
, where here we have set γ 2t := β 2t+1 . Then det D = 2 hence det C = 2 det F . Finally, by reasoning as before, we obtain det F = 0. 6.2.6. Finally, one may observe that in both cases, the set T has cardinality equal to

|T | = ind p π ,E = n -s + 1 + [ s 2 ]
. We conclude that all conditions of Lemma 3.3 are satisfied.

Type E 6

Let g be of type E 6 and let π = π \ {α s }, for 1 ≤ s ≤ 6, p π ,E the corresponding truncated parabolic subalgebra. The involution j on π is given as follows:

j(α 1 ) = α 6 , j(α 2 ) = α 2 , j(α 3 ) = α 5 , j(α 4 ) = α 4 .
By Theorem 2.2.3 Y (p π ,E ) is a polynomial algebra for s = 3, 4, 5. By [START_REF] Panyushev | On symmetric invariants of centralisers in reductive Lie algebras[END_REF], Y (p π ,E ) is polynomial for s = 2 -an adapted pair has been constructed in this case in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF]. In the sections below, we construct an adapted pair for all p π ,E , for s = 3, 4, 5 and we give the construction of [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF] for s = 2, for the sake of completeness. Note that cases s = 3 and s = 5 are symmetric, thus it is enough to consider one of them -we treat case s = 3 in Section 7.2.

Recall that we are using the notations of [

i(α 1 ) = α 1 , i(α 2 ) = α 6 , i(α 3 ) = α 3 , i(α 4 ) = α 5 .
The ij -orbits in π are the {α 1 , α 2 , α 6 }, {α 3 , α 4 , α 5 }. In particular, ind p π ,E = 2.

7.2.1.

Recall the set of strongly orthogonal roots β π and Table I. For S ± we choose

S + = β 0 π = {β 1 , β 2 , β 3 } and S -= -β π 2 = {-β 1 := -(α 2 + α 4 + α 5 + α 6 ), -β 2 := -(α 4 + α 5 )}. For T ± we choose T + = β π ∩ π = {β 4 = α 4 } and T -= -β π 1 = {-α 1 }.
One has |T | = ind p π ,E , thus condition (4) of Lemma 3.3 holds.

For every γ ∈ S = S + S -, we choose the Heisenberg set of centre γ, Γ γ = H γ . Note that S + T + = β π and S -T -= -β π . Then by 3.4.1, conditions (1) and (2) of Lemma 3.3 are satisfied. Finally, an easy computation of the determinant det (α ∨ i (s j )), with 1 ≤ i ≤ 6, i = 3 and S = {s j | 1 ≤ j ≤ 5} settles condition (3).

7.3. Finally, let π = π \ {α 4 }. Then π has three connected components, π 1 = {α 1 , α 3 }, π 2 = {α 5 , α 6 } both of type A 2 and π 3 = {α 2 } of type A 1 . The involution i is given by i(α 1 ) = α 3 , i(α 2 ) = α 2 , i(α 5 ) = α 6 , i(α 4 ) = α 4 . Hence there are four ij -orbits in π, namely {α 1 , α 5 }, {α 3 , α 6 }, {α 2 }, {α 4 }. Remark. Recall Section 2.2.1. Note that ∆ β 1 = ∆ \ (H β 1 -H β 1 ) is a root system of type A 5 . The choice of {11110, 01111, -11000, -00011} coincides with the choice of S for π of type A 5 and π is equal to π without its third root as constructed in [START_REF] Joseph | Slices for biparabolic coadjoint actions in type A[END_REF].

1 = α ∨ 1 , h 2 = α ∨ 2 , h 3 = α ∨ 3 , h 4 = α ∨ 5 , h 5 = α ∨ 6 . Then det (h i (s j )) = 0 1 -1 -1 0 1 -1 -1 0 0 0 0 1 -1 0 0 1 0 0 -1 0 -1 1 0 -1 = 3 = 0.
We conclude that S| h E is a basis for h * . Hence all conditions of Lemma 3.3 are satisfied.

Type E 7

Let g be of type E 7 and let π = π \ {α s }, for 1 ≤ s ≤ 7, p π ,E the associated parabolic. By Theorem 2.2.3 Y (p π ,E ) is a polynomial algebra for s = 2, 5. By [START_REF] Panyushev | On symmetric invariants of centralisers in reductive Lie algebras[END_REF], Y (p π ,E ) is polynomial for s = 1 -an adapted pair has been constructed in this case in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF]. In the sections below, we construct an adapted pair for all p π ,E , for s = 2, 5 and we give the construction of [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF] for s = 1.

Again we are using the notations of [1, Planches I-IX] and we denote by acdef g b the root aα 1 + bα 2 + cα 3 + dα 4 + eα 5 + f α 6 + gα 7 . As before, if b = 0, we simply write acdef g instead of acdef g 0 .

Recall that j = id.

8.1. Take π = π \ {α 1 }. By [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF] one may choose

S = -α 2 , -α 4 , -α 6 , 112111
i(α 1 ) = α 7 , i(α 3 ) = α 6 , i(α 4 ) = α 5 , i(α 2 ) = α 2 .
The ij -orbits are {α 1 , α 7 }, {α 2 }, {α 3 , α 6 }, {α 4 , α 5 }, hence ind p π ,E = 4. 2) of Lemma 3.3 hold for these choices. Finally, S| h E is a basis for h * E , by an easy calculation of the determinant.

8.3. Now let π = π\{α 5 }. Then π has two connected components, π 1 = {α 1 , α 2 , α 3 , α 4 } of type A 4 and π 2 = {α 6 , α 7 } of type A 2 . We have that i is the involution given by i

(α 1 ) = α 2 , i(α 3 ) = α 4 , i(α 5 ) = α 5 , i(α 6 ) = α 7 .
Hence there are four ij -orbits in π, namely the {α 1 , α 2 }, {α 3 , α 4 }, {α 5 }, {α 6 , α 7 }.

One has that β

π 1 = {β 1 = α 1 +α 2 +α 3 +α 4 , β 2 = α 3 +α 4 } and β π 2 = {β 1 = α 6 + α 7 }. For S ± we choose S + = β 0 π = {β 1 , β 2 , β 3 } and S -= (-β π 1 ) (-β π 2 ) = -β π . For T ± we choose T = T + = β π ∩ π = {α 2 , α 3 , α 5 , α 7 }. We have |T | = 4 = |E|.
Again S + T + = β π and S -= -β π . By taking Γ γ = H γ for all γ ∈ S, conditions (1)-(4) of Lemma 3.3 follow as in the previous case.

Type E 8

Let g be of type E 8 and let π = π \ {α s }, for 1 ≤ s ≤ 8. By Theorem 2.2.3, Y (p π ,E ) is a polynomial algebra for s = 3. By [START_REF] Yakimova | A counterexample to Premet's and Joseph's conjectures[END_REF], Y (p π ,E ) is not polynomial for s = 8. Below, we construct an adapted pair for p π ,E , for s = 3. 9.1. Let π = π \ {α 3 } -it has two connected components, π 1 = {α 1 } of type A 1 and π 2 = {α 2 , α 4 , α 5 , α 6 , α 7 , α 8 } of type A 6 . Then j = id and i is the involution that fixes α 1 and α 3 and interchanges α 2 and α 8 , α 4 and α 7 , α 5 and α 6 . Thus there are five ij -orbits in π, namely {α 1 }, {α 3 }, {α 2 , α 8 }, {α 4 , α 7 }, {α 5 , α 6 }. One has that ind p π ,E = 5. 9.1.1. For S ± we choose

S + = β 0 π = {β 1 , β 2 , β 3 , β 4 } and S -= -β π 2 = {-β 1 , -β 2 , -β 3 }. For T ± we choose T + = β π ∩ π = {α 2 , α 3 , α 5 , α 7 } and T -= -β π 1 = {-α 1 }.
In particular, |T | = 5 = ind p π ,E . We take Γ γ = H γ for all γ ∈ S and we conclude as in type E 7 .

Type F 4

Let g be of type F 4 , π = π \ {α s }, where 1 ≤ s ≤ 4, p π ,E the corresponding truncated parabolic. Recall that we are using the labeling of [1, Planche VIII]. In particular, we denote by abcd the root aα 1 + bα 2 + cα 3 + dα 4 . Recall also the set of strongly orthogonal roots of g listed in Table I

, β π = {β 1 = 2342, β 2 = 0122, β 3 = 0120, β 4 = 0100}.
By Theorem 2.2.3, Y (p π ,E ) is polynomial for s = 2, 3, 4. This is still true for s = 1 by [START_REF] Panyushev | On symmetric invariants of centralisers in reductive Lie algebras[END_REF]; moreover, in this case, an adapted pair has been constructed in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF]. For the sake of completeness, we give the construction of [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF] in Section 10.1 below. We construct an adapted pair for s = 2, 4. However, we show with the help of a computer that adapted pairs do not exist for s = 3. Indeed, in this case Y (p - π ,E ) is a polynomial algebra on three generators of degrees 3, 4 and 10. If (h, y = s∈S x s ) is an adapted pair for p π ,E , then |S| = 3, h(s) = -1 for all s ∈ S and 2, 3, 9 are the eigenvalues of h on a complement of (ad p - π ,E ) y. For any h = λα ∨ 1 + µα ∨ 2 + να ∨ 4 ∈ h E , its eigenvalues on the 28 root vectors of p π ,E are functions on λ, µ, ν and may be computed by hand. We computed all h having {-1, -1, -1, 2, 3, 9} among their eigenvalues on p π ,E . Then by setting S to be the set of the three eigenvectors of eigenvalue -1, we showed that y fails to be regular, and so adapted pairs do not exist.

Recall that j = id. Remark. Notice that ∆ \ (H β 1 -H β 1 ) (which is equal to ∆ β 1 with the notation of 2.2.1) is a root system of type C 3 (with highest root 0122). The choice of the roots β 2 -α 4 and -(α 3 + α 4 ) coincides with the choice of S for π of type C 3 and π is equal to π without the last root. Lemma. One has that S| h E is a basis for h * E . Proof. Let s 1 = β 1 , s 2 = β 2 -α 4 , s 3 = -β be the elements of S and take {h 1 = α ∨ 1 , h 2 = α ∨ 3 , h 3 = α ∨ 4 } a basis of h E . It is sufficient to check that the determinant of (h i (s j )) i,j is non zero. Indeed, one checks that det (h i (s j )) = 1 -1 0 0 1 -1 0 0 -1 = -1 = 0.

Type G 2

Let g be of type G 2 with π = {α, β} a set of simple roots and α short. Then Y (p π ,E ) is polynomial for both maximal truncated parabolics of g. 11.1. Let π = {α}. An adapted pair has been constructed in [START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF]. The choices for S and T are {α + β} and {3α + 2β, 3α + β} respectively.

1. 2 .

 2 Denote by Y (a) the Poisson centre of S(a), that is the space : Y (a) = {f ∈ S(a) | ∀ g ∈ S(a), {f, g} = 0}. Note that Y (a) = S(a) a := {f ∈ S(a) | ∀ x ∈ a, {x, f } = 0} and that Y (a) is a subalgebra of S(a). We denote by Sy(a) the Poisson semicentre of S(a), Sy(a) := {f ∈ S(a) | ∀ x ∈ a, {x, f } ∈ k f }; it is also a subalgebra of S(a).

1 ) 2 )

 12 The map Y (a) -→ R[y + V ] defined by restriction of functions is an isomorphism of algebras. (The degrees of a set of homogeneous generators of Y (a) are the

  the set of fundamental weights of g and j = -w 0 is the Dynkin diagram involution. Let P + (π) := α∈π N α denote the set of dominant weights of g and set B π := P + (π) ∩ Nβ π . Define P + (π ), B π accordingly. Then B π is the set of weights of the Poisson semicentre Sy(b), where b = n ⊕ h is the Borel subalgebra.

with dn-s 2 = 2

 22 if n is odd and d i = 1 otherwise. Then up to a sign we have: det (α ∨ i (s j )) = detA B 0 C , where A = (α ∨ 2i (β i )) is an upper triangular matrix with c i , 1 ≤ i ≤ [n/2] on the diagonal. Then up to a sign det (α ∨ i (s j )) = c [n/2] det C. On the other hand C = D 0 0 F , where D = (α ∨ s+2i (β j )) is an upper triangular matrix with d i on the diagonal, hence det D

5. 2 . 5 . 2 . 1 .

 2521 Construction of an adapted pair. The sets S and T . Assume first that 1 ≤ s ≤ n 2 and s is odd. Denote by π 1 the connected component of π of type A s-1 and by π 2 the connected component of π of type D n-s . Recall the sets β π of strongly orthogonal positive roots (see Table

5. 2 . 2 .

 22 Choice of Heisenberg sets. For each β ∈ S, set Γ β = H β with the notation of 2.2.2. As in type B, we have that S + T + = β π and S -T -= -β π . Then conditions (1) and (2) of Lemma 3.3 are immediate, condition (4) is verified above. Finally, condition (3) also follows by arguments similar to the proof of Lemma 4.2.3.

7. 3 . 1 .

 31 We choose for S ± the sets S + = {β 1 , 11110, 01111}, S -= -β 0 π = {-β 1 := -(α 1 +α 3 ), -β 1 := -(α 5 +α 6 )} and for T ± the sets T + = {β 2 , β 4 , α 6 }, T -= {-α 2 }. In particular |T | = 4 = |E|.

7. 3 . 2 .

 32 For γ ∈ β π (-β π ) we set Γ γ = H γ . For the rest of the elements of S, namely 11110 and 01111 we choose Γ 11110 = {10000, 11000, 11100, 01110, 00110, 00010, 11110} and Γ 01111 = {01000, 01100, 00111, 00011, 01111}. They are clearly Heisenberg sets of centres 11110 and 01111 respectively. Conditions (1) and (2) of Lemma 3.3 are easily checked by hand. 7.3.3. Set s 1 = β 1 , s 2 = 11110, s 3 = 01111, s 4 = -β 1 , s 5 = -β 1 and h

8. 2 . 1 .

 21 For S ± we chooseS + = β 0 π = {β 1 , β 2 , β 3 } and S -= -β π = {-β 1 , -β 2 , -β 3 }and for T ± we choose T = T + = β π ∩ π = {α 7 , α 2 , α 3 , α 5 }. One has |T | = 4 = ind p π ,E . Then S + T + = β π and S -= -β π . 8.2.2. For γ ∈ S we take Γ γ = H γ ; by 3.4.1 condition (1) and (

10. 1 . 2 . 2 . 1 .

 1221 Let π = {α 2 , α 3 , α 4 }. Then by[START_REF] Joseph | Compatible adapted pairs and a common slice theorem for some centralizers[END_REF], we may choose S = {-0010, 1121, 1220} and T = {2342, 1222, 0122, 0111}.10.Let π = {α 1 , α 3 , α 4 }, so that the Levi factor of p π ,E is the product l π = sl 2 × sl 3 . Equivalently, π consists of two connected components, namely π 1 = {α 1 } of type A 1 and π 2 = {α 3 , α 4 } of type A 2 . We then have three ij = i -orbits in π, namely Γ1 = {α 1 }, Γ 2 = {α 2 }, Γ 3 = {α 3 , α 4 }. Hence ind p π ,E = 3.One has thatβ π = β π 1 β π 2 , with β π 1 = {β := α 1 }, β π 2 = {β := α 3 + α 4 }.10.We choose for S the set S = {β 1 , β 2 -α 4 = β 3 + α 4 Notice that |T | = 3 = ind p π ,E , hence condition (4) of Lemma 3.3 holds.

10. 2 . 3 .

 23 It remains to verify condition (3) of Lemma 3.3.

10. 3 . 2 H β 3 .

 323 Let π = {α 1 , α 2 , α 3 }, so that the Levi factor of p π , E is of type B 3 . Then i = id, hence the ij -orbits of the Dynkin diagram are the singletons, {α i }, 1 ≤ i ≤ 4 and so ind p π ,E = 4.10.3.1. We choose S = {β 1 , β 2 -α 4 = β 3 + α 4Notice that |T | = 4 = ind p π ,E , hence condition (4) of Lemma 3.3 holds.10.3.2. We set Γ β 1 = H β 1 , Γ -β 1 = -H β 1 and Γ β 2 -α 4 = H 0 β It is clear that Γ β 1 Γ β 2 -α 4 (resp. -Γ β 1 ) complements T + (resp. T -) in ∆ + (resp. ∆ - π ). Moreover, as before, these are Heisenberg sets, thus condition (1) of Lemma 3.3 is satisfied. Condition (2) follows as in 6.2.4. Finally, condition (3) follows by an easy computation as in 10.2.3.

11. 2 .

 2 Let π = {β}. Take S = {β 1 = 3α + 2β} and T = {α, -β} and Γ β 1 = H β 1 . It is immediate to verify conditions (1)-(4) of Lemma 3.3.

  a decomposition of ∆ to irreducible root systems. Let β i be the unique highest root in ∆ i . Then β i ∈ D for all i, (∆ i ) β i is a root system and it decomposes into a union of irreducible root systems (∆ i ) β i = ij with β ij the highest root of ∆ ij . This procedure defines a subset K of N * ∪ N * 2 ∪ • • • and a maximal set β π = {β K } K∈K of strongly orthogonal positive roots. The set K can be endowed with a partial order ≤ as follows : for all K, L ∈ K we say that K ≤ L if and only if L = K or L = {K, n 1 , n 2 , . . . , n s }, with n i ∈ N

j

∆ * for all i, 1 ≤ i ≤ s and s ≥ 1. The set K -called the Kostant cascade -is described in

[START_REF] Joseph | A preparation theorem for the prime spectrum of a semisimple Lie algebra[END_REF] Table

  [START_REF] Joseph | Parabolic actions in type A and their eigenslices[END_REF], that even for maximal truncated parabolics with Poisson centre polynomial, adapted pairs may not exist.It is convenient from now on to replace p π ,E with its opposed algebra p -

	π ,E . Identify
	(p -π ,E )

* with p π ,E through the Killing form. Then p - π ,E acts on p π ,E via the coadjoint action. If h ⊥ E is the orthogonal complement of h E in h with respect to the Killing form, then we can identify (p - π ,E ) * with g/(h ⊥ E ⊕ m -), where m -is the nilradical of p - π ,E

  3.2. Note that g O + ⊕ g O -identifies with o * via the Killing isomorphism. Condition (1) implies the equalities p π , E = h E ⊕o * ⊕g S ⊕g T and p - π , E = h E ⊕ o ⊕ g -S ⊕ g -T . Conditions (2) and (3) and the expansion of y imply by Lemma 3.2 that Φ y is non-degenerate on o × o. Then o * ⊂ (ad o) y ⊂ (ad p - π , E ) y. Condition (3) implies that g S = (ad h E ) y and that h

  1, Planches I-IX] and in particular we denote by acdef b the root aα 1 + bα 2 + cα 3 + dα 4 + eα 5 + f α 6 . If b = 0, we simply Let π = π \ {α 3 }. Then π has two connected components π 1 = {α 1 } of type A 1 and π 2 = {α 2 , α 4 , α 5 , α 6 } of type A 4 . The involution i is defined on π by

	write acdef instead of	acdef 0	.
	7.1. Let π = π \ {α 2 }. By [12], we may choose
	S = -α 3 , -α 5 ,	01210 1	,	11110 1	,	01111 1
	and
	T = 11111, 11110, 01100,	12221 1	,	11211 1	,	12321 2	.
	7.2.

  Let π = π \ {α 2 } -then π is of type A 6 . One has that i is the involution defined by

								1	,	112210 1	,	122110 1
	and
	T =	012221 1	,	012210 1	,	123321 2	,	012100 1	,	123221 1	,	122211 1	,	234321 2	.
	8.2.

  10.2.2. Set Γ β 1 = H β 1 , Γ β 2 -α 4 = H 0 β 2 H β 3 and Γ -β = -H β .These are Heisenberg sets (for Γ β 2 -α 4 see Lemma 6.2.2 -one may as well check by hand since the cardinality of this set is only 7). Their union is disjoint since the H β , β ∈ β π , -H β , β ∈ β π are disjoint. Finally, by comparison of Γ ± := γ∈S ± Γ γ and 2.2.2 (2), the complement of Γ ± in ∆ + (resp. ∆ - π ) is T ± and then condition (1) of Lemma 3.3 is satisfied. On the other hand, condition (2) follows as in Lemma 6.2.4.

* This work was supported in part by the Israel Scientific Foundation grant 797/14 and in part by LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

1


Julien Le Maire

Nicolas Brunie Kalray

Jean-Michel Muller

Computing floating-point logarithms with fixed-point operations

Keywords: floating-point, fixed-point, elementary function, logarithm, correct rounding

Elementary functions from the mathematical library input and output floating-point numbers. However it is possible to implement them purely using integer/fixed-point arithmetic. This option was not attractive between 1985 and 2005, because mainstream processor hardware supported 64-bit floating-point, but only 32-bit integers. Besides, conversions between floatingpoint and integer were costly. This has changed in recent years, in particular with the generalization of native 64-bit integer support. The purpose of this article is therefore to reevaluate the relevance of computing floating-point functions in fixed-point. For this, several variants of the double-precision logarithm function are implemented and evaluated.

Formulating the problem as a fixed-point one is easy after the range has been (classically) reduced. Then, 64-bit integers provide slightly more accuracy than 53-bit mantissa, which helps speed up the evaluation. Finally, multi-word arithmetic, critical for accurate implementations, is much faster in fixed-point, and natively supported by recent compilers. Novel techniques of argument reduction and rounding test are introduced in this context.

Thanks to all this, a purely integer implementation of the correctly rounded double-precision logarithm outperforms the previous state of the art, with the worst-case execution time reduced by a factor 5. This work also introduces variants of the logarithm that input a floating-point number and output the result in fixed-point. These are shown to be both more accurate and more efficient than the traditional floating-point functions for some applications.

I. INTRODUCTION

Current processors essentially support two families of native data-types: integer, and floating-point. In each family, several variants are supported.

Integer sizes are typically 8 and 16 bits in low-power controllers such as MSP430, and 8, 16 and 32 bits for middle-range embedded processors such as the ARM family. Workstation processors and high-end embedded ones have recently added native 64-bit integer support, essentially to address memories larger than 2 32 bytes (4Gb).

Floating-point was standardized in 1985 with two sizes, 32 and 64 bits. A 80-bit format is supported in the x86 and IA64 families. The 2008 revision of the IEEE-754 standard [START_REF]IEEE standard for floating-point arithmetic[END_REF] has added a 128-bit format, currently unsupported in hardware.

To compute on reals, floating-point numbers are the preferred format. The main reason for this is their ease of use, but performance is another compelling reason: until recently, native support for floating-point was more accurate (64-bit versus 32). Therefore, to compute on precisions larger than 32 Figure 1: Arithmetic capabilities of mainstream processors bits, using floating-point was faster than using integers (Figure 1). Indeed, the floating-point units and memory subsytems of workstations processors are designed to achieve maximum floating-point performance on essential numerical kernels, such as the vector product around which all linear algebra can be built. At the time of writing this article, it remains true that a high-end processor can achieve more floating-point operations than integer operations per seconds [START_REF] Pernet | Exact linear algebra algorithmic: Theory and practice[END_REF]. This is mainly due to the wide vector units (such as Intel's AVX extensions) not fully supporting 64-bit integer multiplication. However, integer computations are inherently simpler than floating point. For instance, integer addition takes one cycle (actually it more or less defines the processor cycle). Conversely, floating-point addition involves exponent processing, shifts and leading-zero counts: it typically requires 3 to 6 cycles.

Besides, integers may provide more accuracy in situations where the range of the data is well framed: in such cases the exponent is known, and its bits in a floating-point representation are therefore wasted.

One such situation is the the implementation of an elementary function from the standard mathematical library (libm). There, the programmer has a very good understanding of the ranges of all the intermediate data. Nevertheless, almost all the current implementations of elementary function use internal floating-point formats, probably because of the performance gap shown in Figure 1. The objective of the present work is to design an integer-only implementation of an elementary function, and discuss the effort involved and the resulting performance.

The logarithm was chosen for two reasons. The first is that it is one of the easiest functions to implement, with a large body of literature and open-source implementations to build upon, and a reasonably simple range reduction. The second was to study a floating-point-in, fixed-point-out variant that will be motivated and detailed in Section VI.

A remarkable conclusion is that the implementation effort is comparable or lower than for an equivalent floating-point implementation. Once the proper tools are set up (reviewed in Section II), reasoning on integers is actually easier than reasoning on floating-point. Proving code is even easier.

A second remarkable conclusion is that the performance is well on par with floating-point implementations for 64-bit computations. Besides, as soon as intermediate computations require double-word arithmetic, integers offer large speedups over floating-point. This is the case for correctly-rounded functions [START_REF] De Dinechin | Fast and correctly rounded logarithms in double-precision[END_REF]: the present work demonstrates a worst-case performance improvements by a factor 5 over the previous state of the art. This worst-case time is even better than the average time of the default GNU/Linux log function.

The remainder of this article is organized as follows. Section II presents in more details fixed-point arithmetic, the art of representing reals using integers. Section III introduces the variants of the double-precision logarithm that are studied in this work. Section IV presents the algorithm used, with a focus on new techniques in the integer context. Section V presents and analyses performance results. Section VI advocates, with an application case study, a new interface to the 64-bit logarithm, inputting a floating-point number but outputting a fixed-point result. Section VII concludes.

II. FLOATING-POINT VERSUS FIXED-POINT ARITHMETIC

A. IEEE-754 floating-point

Floating-point numbers are commonly used in computer science as an easy-to-use and accurate approximation for real numbers. Binary floating-point computing was first introduced in the Zuse Z2 electro-mechanical computer in the 1940s. A sign bit s, an integer exponent e and a fraction f ∈ ±[1, 2[ are used to represent the number (-1) s • 2 e • f .

In the beginning of the computer era, a lot of different floating-point formats were used in various platforms. This improved in 1985, with the adoption of the IEEE-754 Standard for Floating-Point Arithmetic. This standard defined several floating-point formats, the main ones being a 32-bit format and a 64-bit format respectively called binary32 and binary64 in the following. More importantly, it also precisely defined the behaviour of the basic operations on these formats. The standard mandates that an operation must return floating-point number uniquely defined as the exact result, rounded according to a well-specified rounding mode. The 2008 revision of the standard, among other things, included specifications of the most used elementary functions, such as sin, tan, exp, log, log 10 . . . However, correct rounding is only recommended for them, due to its perceived high performance overhead. A contribution of this article is to reduce this overhead.

B. Generalities on fixed-point arithmetic

In a fixed-point program, each variable is an integer scaled by a constant exponent. This exponent is implicit: it is not stored in the number itself, contrary to the exponent of a floating-point number. Therefore, it has to be managed explicitely. For instance, to add two variables that have different implicit exponents, an explicit shift must be inserted in the program before the integer addition in order to align both fixed points (see Figure 2). Thus, implementing an algorithm in fixed point is more complex and error-prone than implementing the same algorithm in floating point:

• It requires a good understanding of the orders of magnitude of all the variables, in order to decide where their fixed point should be. • There is no representation of infinities as in floating-point.

Possible overflows have to be predicted and explicitely managed.

• Integer numbers may be signed (using two's complement), or not. • The cheapest rounding mode available is truncation (which can be achieved by shifting right or or masking). This corresponds to a rounding toward -∞, both for signed and unsigned arithmetic. Rounding to the nearest is achieved by •(x) = x+1/2 at the cost of an addition. • When multiplying two integers of the same size, the size of the result is twice the size of the inputs. If the inputs were fractional fixed-point numbers, the high part of the product (which holds the most significant bits) is needed, as illustrated by Figure 3.

C. Support of high fixed-point precisions in current hardware and compilers

A limited set of primitives are needed to efficiently implement floating-point elementary functions in fixed-point: addition and multiplication, boolean operations (to implement bit masks, etc), but also leading zero count and shifts (to convert between fixed-point and floating-point). Processor instructions exist to perform most of these tasks. On the x84-64 architecture [START_REF]Intel R 64 and IA-32 Architectures Software Developer's Manual[END_REF], [START_REF]Intel R 64 and IA-32 Architectures Optimization Reference Manual[END_REF], they are available on 64 bits natively, and can be chained efficiently to operate on 128-bit data. For instance, • a 128-bit addition can be performed in two instructions operating on 64-bit data: an add, and an adc (add with carry); • the full multiplication (of two 64-bit values into a 128-bit one) is done with the mulq assembler instruction; • The lzcnt instruction performs leading zero count. What is more, the integer datatypes __int128_t and __uint128_t, while not belonging to standard C, are supported by most mainstream compilers (GCC, ICC, Clang). The addition in C of two __int128_t will generate the sequence of add and adc previously mentioned. A full multiplication of two 64-bit integers can be achieved by casting operands to the types __uint128_t and __uint128_t, similarly to Figure 3. The generated code will only consist of one mulq instruction. We define the macro fullmul for this (it inputs two int64 and returns an int128), and we also define a macro highmul (that returns the high 64 bits only).

Finally, instructions that are not exposed in the C syntax (such as add-with-carry or leading-zero-count) can be accessed thanks to intrinsics which are also de-facto standard. For example, in GCC, ICC and CLang, 128-bit leading zero count can be achieved with the builtin function __builtin_clzll.

To sum up, writing efficient code manipulating 64-bit and 128-bit fixed-precision numbers is possible in a de-facto standard way.

III. VARIANTS OF THE LOG FUNCTION

The logarithm function, along with the exponential, it is one of the most useful elementary functions. It is continuous and monotonically increasing, and also has the following mathematical property:

log (x • y) = log (x) + log (y) .
Its output range is much smaller than the input range: for any binary64 x, |log (x)| < 2 10 ). Therefore, it is easy to define fixed-point formats that capture the whole output range of a logarithm function. Such formats have 11 bits to the left of the fixed-point (including a sign bit).

Therefore, the core of our algorithm will first compute an approximation of log(x) on such a format (with the fraction size depending on the variant studied). It will then round this approximation to the nearest floating-point number.

However, an option is also to skip this final rounding. Section VI shows an application case study where this improves both performance and accuracy.

A. Correctly rounded logarithm

Modern implementation of elementary functions are at least faithful, i.e. they return one of the two floating-point numbers surrounding the exact value log(x) [START_REF] Markstein | IA-64 and Elementary Functions: Speed and Precision[END_REF], [START_REF] Cornea | Scientific Computing on Itanium R -based Systems[END_REF], [START_REF] Muller | Elementary Functions, Algorithms and Implementation[END_REF]. To achieve this, it is enough to compute an approximation with a confidence interval smaller than the difference between two consecutive floating-point numbers (Figure 5). This requires to use an internal format of slightly higher precision than the destination floating-point format.

Correct rounding is more difficult to achieve. In the cases when the confidence interval includes a rounding boundary, the correctly rounded value can not be decided (Figure 5, bottom). To ensure correct rounding, one has to make sure that the exact result y = f (x), which can be anywhere in the confidence interval, is on the same side of the midpoint as the computed approximation.

Ziv's algorithm [START_REF] Ziv | Fast evaluation of elementary mathematical functions with correctly rounded last bit[END_REF] (whose reference implementation forms the core of the libm in the GNU/Linux standard library glibc) recomputes in such cases the function with increasing accuracy, reducing the confidence interval until it is completely one one side of the rounding boundary. As such recomputations are rarely needed, this algorithm is fast in average. However it may take a lot of time in the worst case, when the actual solution is very close to a mid-point between two consecutive floating-point numbers (Figure 5).

Lefèvre and Muller computed the worst-case precision needed for certain functions (including the logarithm) [START_REF] Muller | Handbook of Floating-Point Arithmetic[END_REF]. This allowed the CRLibm implementation to evaluate the function in two steps only: one quick phase, and one slower phase that is always accurate enough for correct rounding.

B. Classical two-phase correctly-rounded logarithm

The present work uses the CRLibm two-phase approach:

• In the first (quick) phase, an approximation is computed (in a 128-bit integer) with an absolute accuracy of 2 -63 . This is enough to return correct rounding in most cases. Otherwise, the second phase is lauched. • The second (accurate) phase computes to an absolute accuracy of 2 -118 which, according to [10, p. 452] is enough to ensure correct rounding for all floating-point inputs.

C. Variants of the binary64 logarithm function

From this two-phase implementations, several variants can be derived. • A floating-point in, fixed-point out log, outputting an int64_t with an absolute accuracy of 2 -52 , essentially consisting of the first phase without the final conversion to floating-point. • A floating-point in, fixed-point out log outputing an int128_t with an absolute accuracy of 2 -116 , essentially consisting of the second phase only without final conversion to floating-point. The last to functions will be justified by an application case study in Section VI.

Easy round case:

All these variants are actually simplifications of the twophase correctly rounded implementation, whose algorithm is presented now.

IV. ALGORITHM AND IMPLEMENTATION

The algorithm can be decomposed into the following steps:

A. Filtering the special cases

The following special cases must be handled following the IEE-754 standard [START_REF]IEEE standard for floating-point arithmetic[END_REF].

• input is negative or zero • input is ±∞ • input is NaN • input
is a subnormal number One test (predicated false) is enough to detect all thoses cases [START_REF] Anderson | Accurate math functions on the Intel IA-32 architecture: A performance-driven design[END_REF]. It correspond to the case where the bit sign is set, or the exponent is either the min or max value it can take.

As this test is performed on the binary representation of the input, the algorithm begins with a copy of the binary representation of x into an int64_t variable.

On all these special cases, the function returns a special value, except for subnormals: these are normalized and the input exponent is initialized accordingly. Then the control flow gets back to the main path, where a normal input is decomposed into its fraction x = 1 + 2 -52 f 52 ∈ [1; 2) and exponent E.

B. Argument range reductions

The first range reduction simply decomposes the elements of the input:

input = 2 E × x log(input) = E × log(2) + log(x)
When computing E × log(2) + log(x), there is a possible catastrophic cancellation when x is close to 2 and E =-1, i.e. when the input is very close to (but smaller than) 1. To avoid it, most floating-point implementations [START_REF] Markstein | IA-64 and Elementary Functions: Speed and Precision[END_REF], [START_REF] De Dinechin | Fast and correctly rounded logarithms in double-precision[END_REF] first re-center the fraction around 1, using a variant of the following test: if x>1.4 then x=x/2 and E=E+1. We currently choose to skip this classical recentering. This saves the cost of this test itself, but also a few additional operations in the subsequent range reductions, where round to nearest would be needed instead of truncation. The trade-off is that the accurate phase will be launched in case of a massive cancellation. This design choice, initially motivated by simplicity, is a posteriori justified by the low overhead of the accurate phase in the present implementation. However its relevance will be discussed in the conclusion.

The constant log(2) can be stored to arbitrary accuracy as several 64-bit chunks. This, as well as the computation of E × log(2), will be detailed in Section IV-D.

Let us now address the computation of log(x) with x ∈ [1, 2). This interval can be further reduced by an algorithm due to Tang [START_REF] Tang | Table-driven implementation of the logarithm function in IEEE floating-point arithmetic[END_REF]. The main idea is to read, from a table addressed by the k most significant bits of x, two values: inv x ≈ 1

x and log(inv x ). Then if we compute y = inv x • x, the logarithm can be computed as log(x) = log(y) -log(inv x ).

The closer inv x is to 1 x , the closer y will be to 1. Indeed, if |inv x -1

x | ≤ then:

|y -1| ≤ |inv x • x -1| ≤ |inv x - 1 x | • x ≤ • x ≤ 2 •
Since the range of y is much smaller than the range of x, computing log(y) will be easier than computing log(x).

In detail, let x 1 the value of x taking only in consideration its k leading bits. The value stored is inv x = 1/x 1 , in order to ensure y ≥ 1. This choice ensures that we can use only unsigned arithmetic in the sequel. However, an alternative using signed arithmetic should be tried in the near future.

It is desirable to compute y = inv x • x exactly. In our case this is easy for two reasons. Firstly x is a binary64 mantissa (53 bits) and we work with 64-bit integers. Therefore, with a value of inv x on 11 bits, the product can be computed exactly 0 -6 -70

x 1.

52 bits x 1 inv x 0. 18 bits y 0 0 ... x 1.

1.

bits

52 bits

x 1 inv x 0. 9 bits y 0 0 ...

1.

55 bits y 1 inv y 0. 15 bits z 0 0 ... in the low part of a 64-bit product. Secondly, the k leading bits of y are known, as illustrated by Figure 6, so their overflow in the high part of the product is harmless: for k = 7, it is actually possible to approximate inv x on 18 bits and still compute y -1 exactly in a 64-bit integer.

1.

bits

Thanks to this, it is possible to do this argument range reduction twice. First, the 7 leading bits of x (excluding the constant 1) are used as an index in a table that provides inv x and log(inv x ). Then, y -1 has its 6 most significants bits being zeros (more precisely y ∈ [0, 2 -6.41504 ]). Its 7 next bits are used as an index in a table that provides inv y as well as log(inv z ). Now z = inv y × y is even closer to 1 than y: z ∈ [1, 1 + 2 -12.6747 ].

This argument reduction is depicted on Figure 7. With a total of 2 8 table entries only, it achieves a similar reduction as the single-step approach would with a 2 13 -entry table. The delay of the second table read is more than compensated by the reduction in polynomial degree (from 7 to 4 in the quick phase and from 13 to 7 in the accurate phase). This is an old idea in a hardware context [START_REF] Ercegovac | Radix-16 evaluation of certain elementary functions[END_REF], [START_REF] Wong | Fast hardware-based algorithms for elementary function computations using rectangular multipliers[END_REF], [START_REF] Detrey | Return of the hardware floatingpoint elementary function[END_REF]. It cannot be used efficiently to implement a binary64 log using binary64 arithmetic, because the latter cannot hold z (nor z-1) exactly. A contribution of this work is to show that this idea is relevant when 64-bit integer arithmetic is used.

Table I shows that other trade-off between table size and polynomial degree would be possible. The proof of these three steps of argument reduction was developed using Gappa [START_REF] De Dinechin | Certifying the floating-point implementation of an elementary function using Gappa[END_REF]. We note t = z -1, and we now address the computation of log(1 + t). uint64_t a4 = UINT64_C(0x0000000003ffc147); uint64_t a3 = UINT64_C(0x0000005555553dc6); uint64_t a2 = UINT64_C(0x0007fffffffffd57); uint64_t a1 = UINT64_C(0xfffffffffffffffa); uint64_t q = a1-highmul(t,a2-highmul(t,a3-highmul(t,a4))); uint128_t p = fullmul(t, q);

C. Polynomial approximation and evaluation

In each phase, the function log(1 + t) may be approximated by a polynomial P (t) of small degree (4 in the quick phase, 7 in the accurate phase). Thanks to the Taylor formula log(1 + t) ≈ t -t 2 /2 • • • , its constant coefficient can be forced to 0: P (t) = tQ(t). This polynomials is computed using the fpminimax command of the Sollya tool [START_REF] Chevillard | Sollya: An environment for the development of numerical codes[END_REF]. At runtime, it is evaluated using Horner's method.

This Horner evaluation can be implemented with no runtime shift, as shown on Figure 8. Instead, the approximation polynomial was constrained to include all the shifts within the coefficients themselves. More precisely, Sollya's fpminimax can be constrained to compute the optimal polynomial among those which will avoid any shift. This lead to coefficients with leading zeroes, which may seem a waste of coefficient bits. However, we observed that this provided almost the same accuracy as a polynomial where each coefficient is stored on exactly 64 bits, in which case shifts are needed during the evaluation. In other words, removing the shifts is for free in terms of approximation accuracy.

In the quick phase, the evaluation of Q(t) is performed completely in 64-bit arithmetic (using the highmul primitive). Only the final multiplication by t needs a full multiplication. As t itself is exact, this last multiplication is exact, and the 128-bit result will therefore always hold almost 64 significant bits after the leading non-zero bit.

In the accurate phase, all the coefficients a i of Q (except a 7 ) must be stored in 128-bit integers. However the evaluation remains quite cheap, because t remains a 64-bit integer. Specifically, Horner step i computes q i = a i + t × q i-1 where the q i and a i are 128-bit. This rectangular multiplication is implemented as q = ai -(fullmul(t,HI(q)) + highmul(t,LO(q)));

Again, there is no shift needed here.

D. Result reconstruction

Finally, the log will be evaluated as

log(input) = E log(2) -log(inv x ) -log(inv y ) + P (t) .
There, -log(inv x ) and -log(inv y ) are precomputed values. Thus, we can choose to decompose and align them the way we want. The best is probably to align them to the format we want for the results, so they can be added without shift (Figure 9).

The value of E log( 2) is computed by multiplying E with slices of the binary writing of log [START_REF] Pernet | Exact linear algebra algorithmic: Theory and practice[END_REF]. These slices are chosen in such a way that the product will be aligned to the format of the result: log( 2) is decomposed into log(2) -1,-53 , log(2) -54,-118 , log(2) -119,+∞ .

The product of log( 2) -1,-53 with E (a 11-bit number) fits on a 64-bit integer: it requires only the low part of a 64-bit multiplication, and will be aligned to the high word of the result format (see figure 9).

The product of log(2) -54,-118 requires a fulmul (it needs more than 64 bits), but the obtained 128-bit result is also aligned. These two first terms are used in the quick phase.

Only 11 more bits of E log(2) are needed for the accurate phase, but the corresponding term needs to be shifted to place. This will be done only in the accurate phase.

The approximation P (t) of log(z) is finally added. Its implicit exponent is fixed by the fact that we want t exact and fitting on one int64: we therefore have to shift tQ(t) before adding it.

One nice thing about fixed-point arithmetic is that this whole summation process is exact, therefore associative. The order in which it is written is not important, and this is a big difference compared to floating-point, where one has to think carefully about the parenthesing of such sums. In principle the compiler also has more freedom to schedule it than in floating-point, but it is not clear that this is exploited.

E. Rounding test

Floating-point-based correctly-rounded functions use a multiplication-based test due to Ziv, but documented much later [START_REF] De Dinechin | On Ziv's rounding test[END_REF]. Considering the previous summation, it is possible here to use a much simpler test. Upper bounds of the errors of each summand are added together to form an upperbound of the distance between our final sum S and the actual value of the logarithm. Then, at runtime, it is enough to check if Sand S + are rounded to two different floating-point numbers or not, as seen in the figure 5.

Figure 9 show in grey the error terms we have to sum to get . Most of this error summation is performed statically, only the error on P (t) uses a dynamic shift, to benefit from the fact that P (t) was evaluated with good relative error.

Since only sharp error bounds are added together, the value is also sharp, and so is the test.

F. Accurate phase

For the last step, the previous sum (before the addition of the polynomial) can be fully reused. The log(inv x ) and log(inv y ) terms were already accurate to 2 -118 The accurate phase therefore only consists of adding the third part of E log(2), and recomputing a more accurate tP (t) of degree 7 as already explained in Section IV-C.

V. RESULTS AND ANALYSIS

A. Experimental protocol

The proposed correctly rounded implementation has been proven in Gappa, tested against the hard to round cases distributed with CRLibm, and against large numbers of random values. It passes all these tests. The performance of this function is reported on two architectures: an Intel(R) Core(TM) i7-4600U CPU, and a Kalray Bostan core. The latter is a 64-bit, 4-way VLIW core with an FMA-based double-precision floating-point unit, several arithmetic and logic units, and a single 32-bits multiplier (no hardware 64-bits multiplier). A recent GCC is used in both cases (version 4.9). Experiments with ICC and CLang show no significant difference.

To mesure the performance of our function, we use standard procedures based on hardware counters (rdtsc on the Core i7, properly serialized). The functions are compiled with gcc -O3 optimization. The test program is compiled with -O0 to avoid unwanted optimizations. It consists of three similar loops that apply the function on an array of random data. the first calls an (externally linked) empty function, to calibrate the loop and function call overhead: all the timings are reported without this overhead. The second loop times the average case execution time of each function. The third calls the function on an array of hard-to-round cases, thus timing the worst-case execution time of the function.

The same test was run with three others implementations:

• glibc (resp newlib): the function of the GNU C standard library distributed with the Linux system on the Core i7 and Bostan respectively. The glibc uses Ziv' algorithm, and is correctly rounded. • cr-td: the function is the CRLibm variant that only uses binary64. • cr-de: a variant of CRLibm that uses the double extended (80 bits, with a fraction on 64 bits) format available on the x86 platform. Comparing to it hints to what depends on having 64 bits instead of 53, and what depends on having faster arithmetic.

Table II presents some parameters of these implementation. It is worth to mention that the proposed implementation has the smallest memory consumption. The glibc is not a twophase algorithm. It also uses a degree 3 polynomial for the case |x -1| < 0.03 (see file u_log.c in the glibc sources). Table II: Implementation parameters of the correctly rounded implementations.

B. Timings of correctly rounded implementations

Table III compares the speed of the available correctly rounded implementations on the Core i7 processor. For an absolute reference, it also shows what is probably the best available faithful scalar implementation of the logarithm for this processor: it is distributed in the Math Kernel Library (MKL) with Intel's own compiler icc. To obtain this measure, the same test was compiled with icc -O0 -fp-model precise -lm. This processor-specific implementation, written by Intel experts, probably uses tricks such as exploiting the hardware reciprocal approximation instead of a table of inverse [START_REF] Cornea | Scientific Computing on Itanium R -based Systems[END_REF], or the FMA available in recent AVX extensions [START_REF]Intel R 64 and IA-32 Architectures Optimization Reference Manual[END_REF].

The main results are the following.

• The average time is on par with the best state of the art: crlibm-de, that uses 80-bit floating-point and larger tables. It is within a factor two of the absolute reference, MKL, which is not correctly rounded. • The worst-case time has been improved by a factor 5, and is now within a factor two of the average time. Table IV compares these timings (broken down in their different steps) on two processors. What is interesting here is that the Bostan performance is respectable, although it only has 32-bit multiplication support.

In Table II, the proposed cr-FixP implementation is the worst on one metric: the percentage of calls to the accurate phase. This is essentially due to the cancellation problem for values slightly smaller than 1 -the random generator used is actually biased towards this case. It would be a bad design choice to always lauch the accurate phase for such central values if the accurate phase was very slow. However, with an accurate phase within a factor two of the quick one, it Table IV: Running times of each step becomes a sensible design choice. We initially felt that this choice allowed us to save a few cycles in the quick phase. This feeling can only be confirmed by the design and test of an implementation including the classical recentering and more signed arithmetic. What is already clear is that the polynomial evaluation schemes we already use will provide the required relative accuracy in this case. Therefore, when this implementation is available, running its first step only will provide a faithful result, which is not the case of the current implementation.

VI. FLOATING-POINT IN, FIXED-POINT OUT VARIANT

Finally, Table V shows the performance of the variant that returns a 64-bit signed integer approximating 2 52 log(x). This variant performs the final summation completely in int64. Therefore it requires even less tables. Moreover, a polynomial of degree 3 is enough to achieve absolute accuracy of 2 -59 which is largely enough in this context. With all this, and with the removal of the final conversion to a binary64 floatingpoint number, this function offers performance on par with the MKL.

However, the main impact of offering this variant may be in applications that compute sums of logs. An archetype of this class of applications is a DNA sequence alignment algorithm known as TKF91 [START_REF] Thorne | An evolutionary model for maximum likelihood alignment of DNA sequences[END_REF]. It is a dynamic programming algorithm that determines an alignment as a path within a 2D array. The borders of an array are initialized with log-likelihoods, then the array is filled using recurrence formulae that involve only max and + operations.

All current implementations of this algorithm use a floatingpoint array. With the proposed logFix64, an int64 array can be used instead. This should lead to an implementation of TKF91 that is both faster and more accurate:

• faster, not only because logFix64 is faster, but also because the core computation can now use int64 addition and max: both are 1-cycle, vectorizable operations; • more accurate, because larger initialization logs impose an absolute error that can be up to 2 -42 , whereas log-Fix64 will have a constant absolute error of 2 -52 . • more accurate, also because the computation of all the additions inside the array become exact operations: they still accumulate the errors due to the initialization logs, but they do not add rounding errors themselves, as floating-point additions do. A quantitative evaluation of these benefits on TKF91 is in progress. Of course, applications that compute exponentials of sums could similarly benefit from a fixed-point in, floatingpoint out exponential. The same also holds for the base-2 and base-10 variants of these functions.

VII. CONCLUSION AND FUTURE WORK

This work studies the implementation of the correctly rounded logarithm using integer operations. The main idea is to use, instead of binary64 (double-precision), the fast 64-bit integer arithmetic that is nowadays mainstream.

The main result is to improve the worst-case time of a correctly-rounded implementation by a factor 5 with respects to the state of the art, using smaller tables. This new worst case time is better than the average time of the default glibc log of Linux systems. It is also within a factor 4 of the best achievable faithful implementation (the MKL).

We believe that this promising result can be generalized in the following claim: as soon as double-word arithmetic is heavily needed in the implementation of an elementary function (and this is always the case for correctly rounded versions), integer arithmetic becomes very relevant, essentially because 128-bit addition is a 2-cycle operation.

Another claim is that working in fixed point is not a problem in this context: efficient elementary function algorithms always reduce their arguments to a small domain. This second claim, however, requires other experiments, with other functions, to support it. For instance, the Payne and Hanek argument reduction for trigonometric functions is a fixed-point algorithm that provides a fixed-point reduced argument.

The main limitation of this work is probably that it can currently not be vectorized: vector units do not currently offer the necessary multiplication operations. It is not unreasonable to expect that they could be added in the future. If this happens, running the accurate phase alone will provide a branchless implementation that we can expect to be within a factor 3 of the faithful vector version. The inherent test in current twophase correct-rounding approaches is a roadblock for their vectorization, and this solution would remove it completely.

Implementing a function using floating point requires acute floating-point expertise, in particular a mastering of the range and accuracy of all intermediate variables. Considering this, we are also inclined to claim that an integer implementation is in many ways simpler, for instance when one has to add many terms. Still, this is another claim that requires more experiments, because the logarithm was chosen as probably the simplest from this point of view.

A last claim of this article is that floating-point-in, fixedpoint out variants of logarithms would make sense in some applications, both from a performance and from an accuracy point of view. This work provides such a variant. It will be interesting to study if this idea may be generalized to other functions.

Several new techniques have been developed in this article. The more generally useful are the rounding test, and the shift-less polynomial evaluation. A new two-step argument reduction is specific to the logarithm. Some short-term questions remain, the main one being the possibility to achieve high relative accuracy around 1 without degrading the performance of the quick phase. Work has begun to integrate this code the Metalibm framework [START_REF] Brunie | Code generators for mathematical functions[END_REF], which will make such experiments easier.

Another observation is that the published table-maker's dilemma worst-case data is not in an ideal format for a fixedpoint implementation: it is currently only given in relative terms on a large range of exponents.

The best-of-class faithful implementation on Intel processors, MKL, still uses floating point. We have shown that the same performance can be achieved using integers only, but then there is an integer/floating-point conversions overhead that cannot be avoided. In this case, maybe the optimal twophase correctly rounded implementations should use floatingpoint in the quick phase, and integers in the accurate phase. This will add new challenges, such as sharing the tables between the phases.

Figure 2 :

 2 Figure 2: Addition of two fixed-point numbers with different implicit exponents.

  uint32_t a = 0x12345678; // 0x0.12345678 uint32_t b = 0x9ABCDEF0; // 0x0.9ABCDEF0 uint64_t r = (uint64_t)a * b;// = 0x0.0B00EA4E242D2080 uint32_t s = (r >> 32); // ˜0x0.0B00EA4E

Figure 3 :

 3 Figure 3: Multiplication of two fixed-point numbers.

Figure 4 :

 4 Figure 4: The natural logarithm function

  reals

Figure 5 :

 5 Figure 5: Rounding to the nearest an accurate approximation.

Figure 6 :

 6 Figure 6: Tang's argument reduction, here for k = 7. The gray boxes are the values represented in the program.

Figure 7 :

 7 Figure 7: Two iterations of Tang's argument reduction.

Figure 8 :

 8 Figure 8: Shift-less polynomial evaluation

Table I :

 I A few Pareto points of the design space

	Table size (bytes) degree 1st degree 2nd
	39,936	3	5
	12,288	3	6
	4,032	4	7
	2,240	4	8
	2,016	4	9
	900	5	10
	594	6	12
	298	7	14

Table V :

 V Performance of floating-point in, fixed-point out functions. Fix64 is the code of the first step only, without the conversion to float. Fix128 is the code of the second step only, without the conversion to float.

	output	absolute	table Core i5 Bostan
	format	accuracy	size	cycles	cycles
	Fix64	2 -52	2304	24	66
	Fix128	2 -116	4032	60	179
	double (libm)	2 -42		90	105

• A single-phase correctly-rounded, IEEE-754-2008 compliant variant, essentially consisting of the accurate phase only.• A single-phase, accurate-faithful variant, essentially consisting of the quick phase only. This version is currently not implemented properly in this work, for reasons discussed in the sequel.

ACKNOWLEDGEMENTS

This work was supported by the French National Research Agency through the INS program MetaLibm.

The authors are thankful to Alexandros Stamatakis for pointing to the TKF91 algorithm, to Sarah Lutteropp and Pierre Barbera for testing logFix64, and to C. Lauter for assistance with the test procedure.