Pierre-Vincent Koseleff
email: koseleff@math.jussieu.fr

Daniel Pecker
email: pecker@math.jussieu.fr

Fabrice Rouillier
email: fabrice.rouillier@inria.fr

Fabrice Rouillier Computing

Computing Chebyshev knot diagrams

Keywords: Zero dimensional systems, Chebyshev curves, Lissajous knots, polynomial knots, factorization of Chebyshev polynomials, minimal polynomial

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

It is known that every knot may be obtained from a polynomial embedding R → R 3 ( [START_REF] Vassiliev | Cohomology of knot spaces, Theory of singularities and its Applications[END_REF][START_REF] Durfee | Polynomial knots[END_REF]).

Chebyshev knots are polynomial analogue to Lissajous knots that have been studied by many authors (see [START_REF] Boocher | Sampling Lissajous and Fourier knots[END_REF][START_REF] Bogle | Lissajous knots Journal of Knot Theory and its Ramifications[END_REF][START_REF] Hoste | Lissajous knots and knots with Lissajous projections[END_REF][START_REF] Jones | Lissajous knots and billiard knots[END_REF][START_REF] Lamm | Cylinder knots and symmetric unions (Zylinder-knoten und symmetrische Vereinigungen)[END_REF]). All knots are not Lissajous (for example the trefoil and the figure-eight knot). In [START_REF] Koseleff | Chebyshev knots[END_REF], it is proved that any knot K ⊂ R 3 is a Chebyshev knot, that is to say there exist positive integers a, b, c and a real ϕ such that K is isotopic to the curve C(a, b, c, ϕ) : x = Ta(t), y = T b (t), z = Tc(t + ϕ),

where Tn is the Chebyshev polynomial of degree n. This is our motivation for the study of curves C(a, b, c, ϕ), ϕ ∈ R.

In [START_REF] Koseleff | Chebyshev knots[END_REF], the proof uses theorems on braids by Hoste, Zirbel and Lamm ([8, 13]), and a density argument (Kronecker theorem).

In [START_REF] Koseleff | The first rational Chebyshev knots[END_REF], we developed an effective method to enumerate all the knots C(a, b, c, ϕ), ϕ ∈ R where a = 3 or a = 4, a and b coprime. This method was based on continued fraction expansion theory in order to get the minimal b, on resultant computations in order to determine the critical values ϕ for which C(a, b, c, ϕ) is singular, and on multiprecision interval arithmetic to determine the knot type of C(a, b, c, ϕ). Our goal was to give an exhaustive list of the minimal parametrizations for the first 95 rational knots with less than 10 crossings. We obtained in [START_REF] Koseleff | The first rational Chebyshev knots[END_REF] almost every minimal parametrizations. For 6 of these knots, we know the minimal b and we know that the corresponding c must be > 300.

In this paper, we develop a more efficient algorithm. It will give the parametrization of the 6 missing knots in [START_REF] Koseleff | The first rational Chebyshev knots[END_REF] and . allows to compute all diagrams corresponding to C(a, b, c, ϕ), ϕ ∈ R. One motivation is first to achieve the exhaustive list of certified minimal Chebyshev parametrizations for the first 95 rational knots. Another is to provide a certified tool for the study of polynomial curves topology.

Let us first recall some basic facts about knots.

Knot diagrams

The projection of the Chebyshev space curve C(a, b, c, ϕ) on the (x, y)-plane is the Chebyshev curve C(a, b) : x = Ta(t), y = T b (t). If a and b are coprime integers, the curve C(a, b, c, ϕ) is singular if and only if it has some double points. It is convenient to consider the polynomials in Q[s, t, ϕ] Pn = Tn(t) -Tn(s) ts , Qn = Tn(t + ϕ) -Tn(s + ϕ) ts .

We see that C(a, b, c, ϕ) is a knot iff {(s, t), Pa(s, t) = P b (s, t) = Qc(s, t, ϕ) = 0} is empty.

We shall study the diagram of the curve C(a, b, c, ϕ), that is to say the plane projection C(a, b) onto the (x, y)-plane and the nature (under/over) of the crossings over the double points of C(a, b). There are two cases of crossing: the right twist and the left twist (see [START_REF] Murasugi | Knot Theory and its Applications[END_REF] and Figure 1)). In [START_REF] Koseleff | The first rational Chebyshev knots[END_REF],

Figure 1: The right twist and the left twist

we showed that the nature of the crossing over the double point A α,β corresponding to parameters (t = cos(α + β), s = cos(αβ), α = iπ a , β = jπ b ), is given by the sign of D(s, t, ϕ) = Qc(s, t, ϕ)P b-a (s, t, ϕ).

(2) D(s, t, ϕ) > 0 if and only if the crossing is a right twist.

Note that the crossing points of the Chebyshev curve C(a, b) :

x = Ta(t), y = T b (t) lie on the (b-1) vertical lines T ′ b (x) = 0 and on the (a -1) horizontal lines T ′ a (y) = 0. We can represent the knot diagram of C(a, b, c, r) by a billiard trajectory (see [START_REF] Koseleff | Chebyshev knots[END_REF]), which is a pure combinatorial object. As an example, consider the knots 52 = C(4, 5, 7, 0), 52 = C(5, 6, 7, 0), 41 = C(3, 5, 7, 0). We can represent their diagrams by the billiard trajectories in Figure 2.

When a = 3 or a = 4, we obtain the diagrams in the Conway normal form. In this case, the knot is rational and can be identified very easily by its Schubert fraction (see [15, 52 52 41

Figure 2: Billiard trajectories 11]
). When b > a ≥ 5, the problem of classification is much more difficult. Nevertheless, the knowledge of the diagrams allows the computation of all the classical invariants, like the Conway, Alexander and Jones polynomials (see [START_REF] Murasugi | Knot Theory and its Applications[END_REF]).

Summary

Our goal is to compute all diagrams of C(a, b, c, ϕ), where a, b, c are given integers and ϕ ∈ R. From the algorithmic point of view, the description of the Chebyshev knots is strongly connected to the resolution of:

V a,b,c = {Pa(s, t) = 0, P b (s, t) = 0, Qc(s, t, ϕ) = 0}. (3)
We first want to determine the set Z a,b,c of critical values ϕ for which the curve C(a, b, c, ϕ) is singular. Because deg ϕ Qn = n -1 and the leading term of Qn is 2 n-1 nϕ n-1 , we showed in [START_REF] Koseleff | The first rational Chebyshev knots[END_REF], that V a,b,c is 0-dimensional and has at most (a -1)(b -1)(c -1) points. We deduced that |Z a,b,c | ≤ We can determine a polynomial R a,b,c ∈ Z[ϕ] such that Z a,b,c = Z(R). It can be defined by R = Pa, P b , Qc Q[ϕ] and may be obtained with Gröbner bases ( [START_REF] Cox | Using Algebraic Geometry[END_REF]). In [START_REF] Koseleff | The first rational Chebyshev knots[END_REF], we optimized the computation by an ad-hoc elimination based on the properties of the curves for a = 3 or a = 4. Gröbner bases could fully be substituted by some resultant computations in Z[X, ϕ], the systems being generic enough. However, this leads to solve systems of very high degree.

In the present paper we decompose the system by working on some (real cyclotomic) extension fields. We show that the system (3) is equivalent to the resolution of 1 2 (a -1)(b -1)⌊ c 2 ⌋ second-degree polynomials with coefficients in Q(cos π a , cos π b , cos π c ). This result is deduced from geometric properties of the implicit Chebyshev curves.

We show some properties of these extensions that allow to simplify the computations. We can represent the coefficients of the polynomials by intervals and certify the resolution. We then easily and independently obtain the roots of the second-order polynomials and the main difficulty becomes to compare them. A formal method would consist in computing their minimal polynomials over Q, which is equivalent to the resolution of (3). We use multi-precision interval arithmetic for coding the algebraic numbers cos kπ n as well as the solutions ϕ we get. If the two intervals are disjoint, the roots are distinct. If not, we can certify whether the resultant of the two second-order polynomials equals 0 or not by Euclidean division.

In section 2, we first describe the Chebyshev polynomials and the link between their factorizations and the minimal polynomials of cos kπ n . This allows us to represent efficiently the elements of Q(cos π a , cos π b , cos π c ). Along the way, we give an explicit factorization of the Chebyshev polynomials.

In section 3, we recall the definition of Lissajous curves and we give their implicit equations. We study the affine implicit Chebyshev curves Tn(x) = Tm(y) and show that they have ⌊ (n,m) 2 ⌋ + 1 irreducible components, ⌊ (n,m)-1 2 ⌋ being Lissajous curves. This allows us to deduce an explicit factorization of R a,b,c as the product of second-degree polynomials P α,β,γ , in section 4.

We show in section 5, how to obtain Z a,b,c , the set of roots of R a,b,c , with their multiplicities. The general algorithm is described in 6. This allows us to sample all Chebyshev knots C(a, b, c, ϕ), ϕ ∈ R, by choosing a rational number r in each component of R -Z a,b,c .

In section 7, we find an exhaustive and complete list of the minimal parametrization for the first 95 rational knots. The worst case appears with the knot 1033 = C(4, 13, 856, 1/328), with deg R a,b,c = 15390. We discuss the efficiency of our algorithms and compare with those of [START_REF] Koseleff | The first rational Chebyshev knots[END_REF].

CHEBYSHEV POLYNOMIALS

Chebyshev polynomials and their algebraic properties play a central role here. The curves we will study are defined by Chebyshev polynomials. The algebraic extensions we will consider are spanned by their roots and we need to know their factors. In this section we recall some classical properties of Chebyshev polynomials. We will also show the link between their effective factorization in Q[t] and the minimal polynomial of cos kπ n .

The Chebyshev polynomials of the first kind are defined by the second-order linear recurrence

T0 = 1, T1 = t, Tn+1 = 2tTn -Tn-1. (4)
Tn ∈ Z[t] and satisfies the identity Tn(cos θ) = cos nθ, and more generally Tn • Tm = Tnm. We have

Tn = 2 n-1 n-1 k=0 (t -cos (2k+1)π 2n
).

Let Vn be the Chebyshev polynomials of the second kind defined by the second-order linear recurrence (the same as in ( 4))

V0 = 0, V1 = 1, Vn+1 = 2tVn -Vn-1.
Vn ∈ Z[t] and satisfies Vn(cos θ) = sin nθ sin θ . We have

Vn = 2 n-1 n-1 k=1 (t -cos kπ n ),
and therefore V d |Vn when d|n. Let us summarize some useful results in the following Lemma 1. We have the following properties:

• T ′ n (t) = 0 ⇒ Tn(t) = ±1 • Tn(t) = ±1 ⇒ T ′ n (t) = 0 or t = ±1. • Tn(t) = y has n real solutions iff |y| < 1. • Tn(t) = 1 has ⌊ n 2 ⌋ real solutions. • Tn(t) = -1 has ⌊ n-1 2 ⌋ real solutions.
Proof. From T ′ n = nVn, we deduce that t → Tn(t) is monotonic when |t| ≥ cos π n , that Tn has n -1 local extrema for t k = cos kπ n and Tn(t k ) = (-1) k .

Minimal Polynomial of cos kπ n

Let ζn = e 2iπ n . It is well known ( [START_REF] Watkins | The minimal polynomial of cos(2π/n)[END_REF]) that the degree of

Q(ζn) is ϕ(n) where ϕ is the Euler function. Q(cos 2π n ) = Q(ζn) R and the minimal polynomial over Q of cos 2π n has degree 1 2 ϕ(n) when n > 1.
Its roots are cos 2kπ n where k is coprime with n. Consequently, the minimal polynomial Mn of cos π n has degree 1 2 ϕ(2n), when n > 1. Its roots are

t k = cos kπ n where (k, n) = 1, and k is odd. Mn(-t) is the minimal polynomial of cos 2π n . The leading coefficient of Mn is 2 ϕ(2n)/2 . Remark. cos kπ n ∈ Q iff 1 2 ϕ(2n) = 1 or n = 1, that is n = 1, 2, 3.
In this case we get 2 cos kπ n ∈ Z. We deduce the following Proposition 2. Let Pn be defined by P0 = 1, P1 = 2t-1, Pn+1 = 2tPn +Pn-1. Then we have (-1) n Pn(-T2) = V2n+1 and

Pn = d|2n+1 M d (5)
Proof. We have P0(-T2) = V1, P1(-T2) = -2T2 -1 = -V3. The sequences V2n+1 and (-1) n Pn(-T2) satisfy the same recurrence formula: V2n+3 = 2T2V2n+1 -V2n-1. Let d = 2m + 1 be a divisor of 2n + 1 and consider t = cos π d = cos 2 mπ 2m+1 . We have (-1) n Pn(t) = V2n+1(cos mπ 2m+1 ) = 0. Thus M d |Pn and we conclude using the fact that

d|2n+1 deg M d = 1 + 1 2 d|2n+1,d>1 ϕ(2d) = n = deg Pn. Lemma 3. We have M 2 k m = Mm(T 2 k ) if m is odd. Proof. We have Mm • T 2 k (cos π 2 k m ) = 0 and (2 k , m) = 1 so M 2 k m |Mm(T 2 k ). We conclude since M 2 k m and Mm(T 2 k ) have same leading term.

The relations between the minimal polynomial of cos 2π

n and the factorization of ([20]). Formula (5) together with Lemma 3 give also an algorithm to compute Mn.

T ⌊ n 2 ⌋+1 -T ⌊ n 2 ⌋ is known
The number of factors of Tn is known ( [START_REF] Hsiao | On factorization of Chebyshev's polynomials of the first kind[END_REF]). We give here the relation between the Chebyshev polynomials Tn and Vn and the polynomials Mn. Proposition 4. Factorization of Tn and Vn. We have the following factorizations in irreducible factors

V 2 k (2m+1) = d|2m+1 k i=1 M d (T 2 i ) • M d (t)M d (-t) T 2 k (2m+1) = 1 2 d|2m+1 M d (T 2 k+1 )
where Mn is the minimal polynomial of cos π n . Proof. The factorization of Vn is obtained by comparing its roots with those of M d (±t), when d|n. Let d be an odd divisor of n. We write

n = 2 k • d1 • d, where d1 is odd. cos d 1 π 2n = cos π 2 k+1 d is a root of Tn so M 2 k+1 d |Tn.
We deduce the factorization by comparing the leading terms.

CHEBYSHEV AND LISSAJOUS CURVES

The following proposition will explain the notions of Lissajous and Chebyshev curves.

Proposition 5. The parametric curve

C : x = cos(at), y = cos(bt + ϕ), t ∈ C,
where a, b are coprime integers (a odd) and ϕ ∈ R admits the equation

T b (x) 2 + Ta(y) 2 -2 cos(aϕ)T b (x)Ta(y) -sin 2 (aϕ) = 0. (6) 1. If aϕ = kπ, this equation is irreducible. C is called a Lissajous curve. Its real part is 1-1 parametrized for t ∈ [0, 2π]. 2. If aϕ = kπ, this equation is equivalent to T b (x) = (-1) k Ta(y). C is called a Chebyshev curve. It can be parametrized by x = Ta(t), y = (-1) k T b (t).
Proof. Let (x, y) ∈ C. We have T b (x) = cos(bat), Ta(y) = cos(bat + aϕ). Let λ = aϕ, θ = abt. We get Ta(y) = cos(θ + λ) so (1cos 2 θ) sin 2 λ = (cos θ cos λ -Ta(y)) 2 , that is (1-Ta(x)) 2 sin 2 λ = (Ta(x) cos λ-Ta(y)) 2 , and we deduce our Equation [START_REF] Fischer | Plane Algebraic Curves[END_REF].

Conversely, suppose that (x, y) satisfies [START_REF] Fischer | Plane Algebraic Curves[END_REF]. Let x = cos(at) where t ∈ C. We also have x = cos a(t + 2kπ a ). We have T b (x) = cos θ. A = Ta(y) is solution of the second-degree equation

A 2 -2 cos(aϕ) cos θA -sin 2 (aϕ) = 0.
Consequently, we get Ta(y) = cos(θ ± aϕ) = Ta(cos(±bt + ϕ)). We deduce that y = cos(±bt + ϕ + 2hπ a ), h ∈ Z. Changing t by -t, we can suppose that x = cos at, y = cos(bt + ϕ + 2hπ a ). By choosing k such that kb + h ≡ 0 (mod a), we get x = cos at ′ , y = cos(bt ′ + ϕ), where t ′ = t + 2kπ a . If aϕ ≡ 0 (mod π). Suppose that Equation ( 6) factors in P (x, y)Q(x, y). We can suppose, for analyticity reasons, that P (cos(at), cos(bt + ϕ)) = 0, for t ∈ C. The curve C intersects the line y = 0 in 2b distinct points so deg x P ≥ 2b. Similarly, deg y P ≥ 2a so that Q is a constant which proves that the equation is irreducible.

If cos aϕ = (-1) k , the equation becomes T b (x)-(-1) k Ta(y) = 0. In this case the curve admits the announced parametrization (see [START_REF] Fischer | Plane Algebraic Curves[END_REF][START_REF] Koseleff | Chebyshev knots[END_REF] for more details).

Remark. If a = b = 1, we obtain the Lissajous ellipses. They are the first curves studied by Lissajous ([14]). Let µ ≡ 0 (mod π). The curve Eµ : x 2 + y 2 -2 cos(µ)xysin 2 (µ) = 0 is an ellipse inscribed in the square [-1, 1] 2 . It admits the parametrization x = cos t, y = cos(t + µ).

The following notation will be useful. Let Eµ(x, y) = x 2 + y 2 -2 cos(µ)xysin 2 (µ) when µ ≡ 0 (mod π) and E0 = xy, Eπ = x + y. The Equation ( 6) is equivalent to Eaϕ(T b (x), Ta(y)) = 0. This shows that the real part of the curve C (Equation ( 6)) is inscribed in the square [-1, 1] 2 . Using Proposition 5 we recover the classical following result. Corollary 6. The Lissajous curve x = cos(at), y = cos(bt + ϕ), (aϕ ≡ 0 (mod π)) has 2abab singular points which are real double points.

Proof. singular points of C satisfy Equation (6) and the system Remark. The study of the double points of Lissajous curves is classical (see [START_REF] Bogle | Lissajous knots Journal of Knot Theory and its Ramifications[END_REF] for their parameters values). The study of the double points of Chebyshev curves is simpler (see [START_REF] Koseleff | Chebyshev knots[END_REF]).

T ′ b (x)(T b (x) -Ta(y) cos aϕ) = 0, T ′ a (y)(Ta(y) -T b (x) cos aϕ) = 0. Suppose that T ′ b (x) = T ′ a (y) = 0 then T 2 a (y) = T 2 b (x) = 1 and
Corollary 7. The affine implicit curve Tn(x) = Tm(y) has ⌊ n-1 2 ⌋⌊ m-1 2 ⌋+⌊ n 2 ⌋⌊ m 2 ⌋ singular points that are real double points.

Proof. The singular points satisfy either Tn(x) = Tm(y) = 1 or Tn(x) = Tm(y) = -1 and we conclude using Lemma 1.

Theorem 8. Factorization of Tn(x) -Tm(y). Let m = ad, n = bd, (a, b) = 1 and a odd. We have the factorization

Tn(x) -Tm(y) = 2 d-1 ⌊ d 2 ⌋ k=0 C k (x, y)
where

C k (x, y) = E 2akπ d (T b (x), Ta(y))
is In this case the curve Tn(x) = Tn(y) is a union of ellipses and some lines. It will be useful for the determination of the double points of Chebyshev space curves. We have

Tn(t) -Tn(s) t -s = 2 n-1 ⌊ n 2 ⌋ k=1 E 2kπ n (s, t). (7)
The curve Tn(t) -Tn(s) ts = 0 has ⌊ n 2 ⌋ irreducible components. Note that E 2kπ n and E 2lπ m intersect at the point (t, s) = (cos( kπ n + lπ m ), cos( kπ n -lπ m )) and its symmetric with respect to the lines s = -t and s = t. We recover the parametrization of the double points of x = Ta(t), y = T b (t) that will be very useful for the description of Chebyshev space curves.

Proposition 10 ( [START_REF] Koseleff | Chebyshev knots[END_REF][START_REF] Koseleff | The first rational Chebyshev knots[END_REF]). Let a and b are nonnegative coprime integers, a being odd. Let the Chebyshev curve C be defined by x = Ta(t), y = T b (t). The pairs (t, s) giving a crossing point are

t = cos( jπ b + iπ a ), s = cos( jπ b -iπ a ) where 1 ≤ i ≤ 1 2 (a -1), 1 ≤ j ≤ b -1.

CRITICAL VALUES

A polynomial R a,b,c ∈ Z[ϕ] for which Z a,b,c = Z(R) can be defined by R = Pa, P b , Qc Q[ϕ] and may be obtained with Gröbner bases ( [START_REF] Cox | Using Algebraic Geometry[END_REF]).

Example. When a = 3, b = 4, c = 5, we find that R a,b,c = 80 ϕ 4 + 60 ϕ 2 -1 • 6400 ϕ 8 -3200 ϕ 6 + 560 ϕ 4 -80 ϕ 2 + 1 . There are exactly 6 critical values that are symmetrical For these values of ϕ, the curve Q5(s, t, ϕ) = 0, which is translated from the curve P5(s, t) = 0 by the vector (ϕ, ϕ), meets the points {P3 = 0, P4 = 0}.

T 5 (t) -T 5 (s) t -s = 0      T 7 (t) -T 7 (s) t -s = 0 T 5 (t) -T 5 (s) t -s = 0
In this part, we use use the properties of Chebyshev curves obtained in section 3. We give an explicit formula for the polynomial R a,b,c as a product of of univariate polynomials of degree 1 or 2 with coefficients in Q(cos π a , cos π b , cos π c ). Proposition 11. Let a, b be nonnegative coprime integers and c be an integer. Suppose that a is odd. Let R a,b,c (ϕ) be the polynomial

a-1 2 i=1 b-1 j=1 Qc(cos( j b + i a )π, cos( j b -i a )π, ϕ). (8) R a,b,c ∈ Z[ϕ] and C(a, b, c, ϕ) is singular iff R a,b,c (ϕ) = 0.
Proof. ϕ ∈ Z a,b,c iff there exists (s, t) such that Pa(s, t) = P b (s, t) = 0 and Qc(s, t, ϕ) = 0. This conditions are equivalent to have t = cos( jπ b + iπ a ) and s = cos( jπ b -iπ a ) and Qc(s, t, ϕ) = 0, for some 1 ≤ i ≤ a-1 Qc(cos(αi + βj ), cos(αiβj ), ϕ)

belongs to Z[ϕ, cos αi] because the cos βj are the roots of

V b ∈ Z[t]. From Qc(-s, -t, ϕ) = Qc(s, t, -ϕ) we deduce that a-1 2 i=1 Ri(-ϕ)Ri(ϕ) = a-1 i=1 Ri(ϕ) ∈ Z[ϕ]. We thus have R 2 a,b,c ∈ Z[ϕ]
and so it is for R a,b,c .

Let s = cos(α + β), t = cos(αβ). Using Theorem 8 and Formula (7), we get

Qc(s, t, ϕ) = 2 c-1 ⌊ c 2 ⌋ k=1 E 2kπ n (s, t).
Let us consider P α,β,γ = 1 sin 2 γ E2γ (s + ϕ, t + ϕ). For γ = π 2 , P α,β,γ is

ϕ 2 + 2ϕ cos α cos β + (cos 2 α -cos 2 γ)(cos 2 β -cos 2 γ) sin 2 γ and P α,β, π 2 = ϕ + cos α cos β.
We therefore obtain

Qc(cos(α + β), cos(α -β), ϕ) = K ⌊ c 2 ⌋ k=1 P α,β, kπ c (ϕ) with K = 2 c-1 c k=1 2 sin kπ c = c2 c-1 . We get therefore R a,b,c (ϕ) = K 1 2 (a-1)(b-1) ⌊ c 2 ⌋ k=1 a-1 2 i=1 b-1 j=1 P iπ a , jπ b , kπ c (ϕ).
We have written R a,b,c as the product of second or firstdegree polynomials P α,β,γ in Q(cos π a , cos π b , cos π c ).

COMPUTING THE CRITICAL VALUES

Our strategy consists in first computing separately the real roots of each P α,β,γ and then combining these roots to get those of R a,b,c . A straightforward approach would be to use interval arithmetic to approximate the various trigonometric expressions, but this would fail when R a,b,c has multiple roots, unless we cannot ensure if some discriminant or some resultant are null.

Real roots of

P α,β,γ Let α = iπ a , β = jπ b and γ = kπ c with 1 ≤ i ≤ a-1 2 , 1 ≤ j ≤ b -1, 1 ≤ k ≤ ⌊ c-1 2 ⌋. If γ = π 2 , the unique root of P α,β, π 2 is -cos α cos β. If γ = π 2 , the discriminant of P α,β,γ is 4 cos 2 γ 1 - sin 2 α sin 2 β sin 2 γ . It
has the same sign as

sin 2 γ -sin 2 α sin 2 β (9)
The knowledge of the sign of ( 9) then gives explicit formulas for the real roots of P α,β,γ .

Multiplicity of 0

Proposition 12. The multiplicity of a,c) -1). Proof. We have to examine whenever ϕ = 0 is a root of P α,β,γ where α = iπ a , β = jπ b and γ = kπ c . Here a is odd so cos α = 0. Thus, ϕ = 0 is a root of P α,β, π 2 if and only if cos α cos β [START_REF] Koseleff | Chebyshev knots[END_REF] is null and when γ = π 2 , ϕ = 0 is a root of P α,β,γ if and only if the following expression is null a,c) -1) + ((b, c) -1)(a -1)/2. We thus obtain the result.

ϕ = 0 in R a,b,c is a-1 2 ((b, c) -1) + ⌊ b 2 ⌋((
(cos 2 α -cos 2 γ)(cos 2 β -cos 2 γ). ( 11
)
• If γ = β = π 2 , ϕ = 0 is a root for i = 1, . . . , a-1 2 . • If γ = π 2 , ϕ = 0 is a root of P α,β,γ if and only if sin 2 γ = sin 2 α or sin 2 γ = sin 2 β, that is ic = ka or jc = kb or (b -j)c = kb. The root ϕ = 0 is obtained for i = λ a (a,c) , k = λ c (a,c) , λ = 1, . . . , (a,c)-1 2 and it is double when β = π 2 . It is also obtained for j = µ b (b,c) , k = µ c (a,c) , µ = 1, . . . , (b, c) -1. We obtain ⌊ b 2 ⌋((
Remark. We find that 0 is not a critical value if and only if a, b and c are pairwise coprime integers. This result was first proved by Comstock ([4], 1897), who found the number of crossing points of the harmonic curve parametrized by x = Ta(t), y = T b (t), z = Tc(t).

Non null multiple roots of R a,b,c

It may happen that R a,b,c has multiple root ϕ. Several cases may occur.

◮ P α,β,γ has a double root if and only if Disc (P α,β,γ ) = 0, that is to say sin 2 γ = sin 2 α sin 2 β. The double root is ϕ =cos α cos β.

◮ P α,β,γ 1 and P α,β,γ 2 have a common root. In this case P α,β,γ 1 = P α,β,γ 2 , that is to say

(sin 2 γ1 -sin 2 γ2)(sin 2 γ1 sin 2 γ2 -sin 2 α sin 2 β) (12)
is null.

◮ P α 1 ,β 1 ,γ 1 and P α 2 ,β 2 ,γ 2 have a common root.
The first two cases are related to the equation sin r1π sin r2π = sin r3π sin r4π

where ri ∈ Q. All the solutions of Equation ( 13) are known (see [START_REF] Myerson | Rational products of sines of rational angles[END_REF]). There is a one-parameter infinite family of solutions corresponding to sin π 6 sin θ = sin θ 2 sin( π 2 -θ 2 ), and a finite number of solutions listed in [START_REF] Myerson | Rational products of sines of rational angles[END_REF]. We deduce from a careful study of the Equation ( 13

= k 1 π c , γ2 = k 2 π
c , where (a, b) = 1 and a is odd. Then P α,β,γ 1 and P α,β,γ 2 have a common root ϕ iff there are equal and 1. sin α = sin γ1, sin β = sin γ2.

In this case, the roots are ϕ = 0 and ϕ = -2 cos α cos β.

2. sin β = 1 2 , sin γ1 = sin 1 2 α, sin γ2 = cos 1 2 α. In this case the common roots are ϕ =cos(α ± π 6 ). 3. sin γ2 = sin γ1.

◮ In case when α1 = α2 or β1 = β2, P α 1 ,β 1 ,γ 1 and P α 2 ,β 2 ,γ 2 have a common root if Res ϕ(Pα 1 ,β 1 ,γ 1 , P α 2 ,β 2 ,γ 2 ) = 0. This resultant can be expanded and its sign is the one of:

(cos 2 α1 -cos 2 γ1)(cos 2 β1 -cos 2 γ1) sin 2 γ2 - (cos 2 α2 -cos 2 γ2)(cos 2 β2 -cos 2 γ2) sin 2 γ1 2 -4(cos α1 cos β1 -cos α2 cos β2) sin 2 γ1 sin 2 γ2× (cos 2 α1 -cos 2 γ1)(cos 2 β1 -cos 2 γ1) cos α2 cos β2 sin 2 γ2 - (cos 2 α2 -cos 2 γ2)(cos 2 β2 -cos 2 γ2) cos α1 cos β1 sin 2 γ1 . (14)
It would be interesting to get an arithmetic condition asserting that this resultant is null.

Computing the diagrams

Let ϕ ∈ R. ϕ may be a rational number r ∈ Q -Z a,b,c or an algebraic number given by a polynomial whom it is a root and an isolating interval. The main step is the computation of the crossing nature at the double point A α,β corresponding to parameters (t = cos α + β, s = cos αβ), where α = iπ a , β = jπ b . There are two cases to consider. 1. We know the roots ϕ1 ≤ • • • ≤ ϕm of Qc(s, t, ϕ).

If ϕ < ϕ1 then n = 0 otherwise let n = max{k, ϕ > ϕ k }. We have sign Qc(s, t, ϕ) = (-1) n .

2. We do not know the roots of Qc(s, t, ϕ).

We compute Qc(s, t, ϕ) using the recurrence formula:

Q0 = 0, Q1 = 1, Q2 = 2S + 4ϕ, Q3 = -4 T + 12 ϕ S + 4 S 2 + 12 ϕ 2 -3. Qn+4 = 2 (S + 2 ϕ) (Qn+3 + Qn+1) -2 2 ϕ 2 + 2 T + 2 ϕ S + 1 Qn+2 -Qn.
where S = s + t = 2 cos α cos β and T = st = cos 2 α + cos 2 β-1 (see [START_REF] Koseleff | The first rational Chebyshev knots[END_REF]). We work formally in Q[u, v]/ M, N where M, N are the minimal polynomials of u = cos α, v = cos β.

The sign of the crossing is

D(s, t, ϕ) = Qc(s, t, ϕ)P b-a (s, t, ϕ) = (-1) i+j sin ibπ a sin jaπ b Qc(s, t, ϕ) = (-1) i+j+⌊ ib a ⌋+⌊ ja b ⌋ Qc(s, t, ϕ).

THE ALGORITHM

We want to compute all the real roots ϕ1 < . . . < ϕn of R a,b,c that factors in 1 2 (a-1)(b-1)⌊ c 2 ⌋ polynomials P α i ,β j ,γ k . We precisely want non overlapping intervals [am, bm] for these roots in order to chose sample rational points r0 < a1, bi < ri < ai+1, bn < rn.

At some stages, one may need to compute the sign of Disc (P α,β,γ ) (expression (9)) or Res (P α 1 ,β 1 ,γ 1 , P α 1 ,β 1 ,γ 1 ) (expressions ( 12) and ( 14)) in order to decide whether two roots are distinct or not. This information is required for two reasons. We first want to be sure that we get all the roots and secondly, we will need to know all the roots of Qc(cos(αi + βj ), cos(αiβj ), ϕ) with their multiplicities in order to determine the nature of the crossing over the corresponding double point in the diagram (section 5.4.

The signs of ( 10) and [START_REF] Koseleff | Chebyshev diagrams for rational knots[END_REF], may be evaluated by simple arithmetic considerations on α, β, γ.

Isolate and Refine.

A very first step is to get accurate isolating intervals with rational bounds for cos αi, cos βj and cos γ k to perform interval arithmetic for the real roots of P α i ,β j ,γ k .

Such intervals can be computed by performing algorithms based on Descarte rule of signs (see for example [START_REF] Rouillier | Efficient Isolation of Polynomial Real Roots[END_REF]) on the used Chebyshev polynomials Vn. Algorithms like in [START_REF] Rouillier | Efficient Isolation of Polynomial Real Roots[END_REF] can easily solve such polynomials for very high degrees (several thousands) with a large accuracy. The computation of the required isolating intervals can then be performed as a preprocessing for the global algorithm.

From now, we denote by Isolate(P ,acc) the function that isolates the roots of a univariate polynomial P with rational coefficients by means of intervals with rational bounds for a given accuracy acc (maximal length of the intervals). This function provides non overlapping intervals that contains a unique real root of P (and such that each real root of P is contained in one of the intervals).

Note that if more accuracy is required for some intervals, it is easy to refine them from the isolating intervals provided by the function Isolate: just evaluating P at some points, without running again the Isolate function with a higher value for acc). We name by Refine(I,P ,acc) the function that decreases the length of the interval I to get an accuracy ≤ acc, knowing that the interval isolates a real root of P .

IsolateP. Thanks to Proposition 13, one can compute the roots of P α,β,γ with an appropriate accuracy, using multiprecision interval arithmetic for the evaluations. We will use the function IsolateP(α, β, γ, acc) that returns a (possibly empty) list of (α, β, γ, [u, v]) corresponding to isolating intervals [u, v] for the roots.

SignTest. When two isolating intervals [u1, v1] and [u2, v2] corresponding to (α1, β1, γ1) and (α2, β2, γ2) are such that [u1, v1] [u2, v2] = ∅, we first use a filter (named SignTest in the sequel) which consists in using multi-precision interval arithmetic for the evaluation of Res ϕ(Pα 1 ,β 1 ,γ 1 , P α 2 ,β 2 ,γ 2 ) (expressions 12) and [START_REF] Lissajous | Sur l'étude optique des mouvements vibratoires[END_REF].

Thanks to Proposition 14, we know by arithmetic considerations when [START_REF] Koseleff | The first rational Chebyshev knots[END_REF] is null. We know also the corresponding common roots and we change [ui, vi]

to [u1, v1] [u2, v2].
Expression ( 14) is

P = (C 2 1 -C 2 5 )(C 2 3 -C 2 5 )(1 -C 2 6 ) - (C 2 2 -C 2 6 )(C 2 4 -C 2 6 )(1 -C 2 5 ) 2 -4 (C1C3 -C2C4)(1 -C 2 5 )(1 -C 2 6 )× (C 2 1 -C 2 5 )(C 2 3 -C 2 5 )C2C4(1 -C 2 6 ) - (C 2 2 -C 2 6 )(C 2 4 -C 2 6 )C1C3(1 -C 2 5
) , where C1 = cos α1, C2 = cos α2, C3 = cos β1, C4 = cos β2, C5 = cos γ1, C6 = cos γ2.

Given isolating intervals with rational bounds that contain the values of the required Ci, i = 1, . . . , 6, the function SignTest(α1, α2, β1, β2, γ1, γ2) straightforwardly evaluates P . If the resulting interval is [0, 0] or do not contains 0, one can decide the sign of the input, otherwise, the function returns FAIL.

FormalNullTest. In case of failure of SignTest, one has to decide if the input is null or not, which is the goal of the function FormalNullTest we now describe.

Let us write α1

= i 1 π a 1 , α2 = i 2 π a 2 , β1 = j 1 π b 1 , β2 = j 2 π b 2 , γ1 = k 1 π c 1 , γ2 = k 2 π c 2 .
Let m be the smallest common multiple of a1, a2, b1, b2, c1 and c2. According to the definitions of Tn, we have Ci = Tn i (cos π m ). Since Mm is the minimal polynomial of cos π m , the expression P (Ci, . . . , C6) is null if and only if P (Tn 1 , . . . , Tn 6 ) = 0 in Q[t]/ Mm(t) . DoubleTest. Our function first performs the SignTest. If it returns an interval with bounds of same sign, then the sign of the tested expression is the sign of the two bounds of the interval. Otherwise, we run the FormalNullTest. If this test returns 0 then the expression is null. Otherwise, we decrease the lengths of the intervals that represent the values of cos kπ m by calling the function Refine until the SignTest does not FAIL (the fact that the sign of the expression to be tested is known not to be 0 ensures that this process will end).

The global algorithm. We proceed in three steps :

(0) We isolate the roots of some Chebyshev polynomials using the Isolate black-box with an arbitrary accuracy.

(1) We compute separately the roots of the P α,β,γ by using IsolateP.

(2) We then consider the list of these roots and observe carefully the overlapping intervals. For any pair of overlapping interval, we decide whether corresponding resultants are null or not using DoubleTest. If the corresponding roots are equal then we change their isolating intervals by taking their intersection.

From these disjoint intervals with rational bounds, we straightforwardly get the roots with their multiplicities. We thus deduce the sample points r0, . . . , rn we need. Furthermore, for each αi = iπ a , βj = jπ b , we know the roots with their multiplicities of Qc(t, s, ϕ), where t = cos(αi + βj ) and s = cos(αiβj ). This information is helpful for knowing the crossing nature at the point A α i ,β j (section 5.4).

EXPERIMENTS

In the appendix of [START_REF] Koseleff | The first rational Chebyshev knots[END_REF], we gave parametrizations of every rational knot as C(3, b, c, ϕ) and C(4, b, c, ϕ) where (b, c) were minimal for the lexicographic order (c ≤ 300). For 6 knots we knew the minimal b and that c > 300. With the method we developed here, we recover all the minimal parametrizations we gave in [START_REF] Koseleff | The first rational Chebyshev knots[END_REF] but also for the 6 missing knots. The following knots admit the parametrizations: For example, one deduces that there is no parametrization of 95 as Chebyshev knots with (a, b, c) < lex [START_REF] Cox | Using Algebraic Geometry[END_REF][START_REF] Lamm | Cylinder knots and symmetric unions (Zylinder-knoten und symmetrische Vereinigungen)[END_REF]326). R3,14,385 has degree 4992. It has 2883 real roots. All are simple roots except 0 that is of multiplicity 6. R4,13,856 has degree 15390 and 9246 real roots (0 has multiplicity 18). We get 2050 non trivial knots, 83 of them are distinct, and 63 have less than 10 crossings. The total running time -critical values with their multiplicities, sampling of 1442 values, computing knot invariant -was 450" (Maple 13, on Laptop, 3Gb of RAM, 3MHz).

Outside the intrinsic combinatorial aspects of the problem, the complexity of our algorithm essentially depends on the FormalNullTest. In the worst case d = abc and deg M d = 1 2 (a-1)(b-1)(c-1), when a, b, c are prime integers, the most difficult computation consists in deciding if the expression 14 is null or not which is equivalent to testing if a univariate polynomial of degree at most 4d is null modulo M d or not.

These computations can be speed up a lot since they can be performed modulo a prime integer: all the considered polynomials have a power of two as leading coefficient and we just need to test if one polynomial is null modulo another one.

In this challenging experiments, we never had to run the FormalNullTest, the SignTest being always sufficient, thanks to the filters given by propositions 13 and 14 and to a good (experimental) choice initial choice of accuracy when computing the prerequisites running the Isolate algorithm.

CONCLUSION

The method we developed in this paper allows us to compute Chebyshev knot diagrams for high values of a, b and c. Our experience with small a and b shows that the difficult cases (multiple roots of R a,b,c we found) were predictable. There are certainly some specific reasons connected with arithmetic properties and the structure of cyclic extensions.

The main difference with the algorithm described in [START_REF] Koseleff | The first rational Chebyshev knots[END_REF] and the computation of R a,b,c as a polynomial of degree 1 2 (a -1)(b -1)(c -1), is that it came as a resultant of a polynomial of degree (c -1) in (X, ϕ) and a polynomial of degree 1 2 (a -1)(b -1) in X with coefficients in a unique field extension. The example described in this section can be considered as the extremal case, in terms of degree, to be solved using methods from the state of the art when running [START_REF] Koseleff | The first rational Chebyshev knots[END_REF] while it can be solved in few minutes with the method proposed in this article.

From the point of view of knot theory, it is proved in [START_REF] Koseleff | Chebyshev diagrams for rational knots[END_REF], that rational knots with N crossings can be parametrized by polynomials of degrees (3, b, c) where b + c ≤ 3N which is far better that the results we obtain here. But we challenged to give, as it was done with Lissajous knots in [START_REF] Boocher | Sampling Lissajous and Fourier knots[END_REF], an exhaustive and certified list of minimal parametrizations. We consider that it might be one step in the computing of polynomial curves topology.

1 2

 1 (a -1)(b -1)(c -1). Let Z a,b,c = {ϕ1, . . . , ϕn}.The type of the knot C(a, b, c, ϕ) is given by its diagram which is constant when ϕ is in (ϕi, ϕi+1), because the crossings do not change in this interval. In order to get all possible knots C(a, b, c, ϕ), we only need sample points ri in each (ϕi, ϕi+1) and to compute the diagram of C(a, b, c, ri).

  Equation 6 is not satisfied. Suppose that T b (x) -Ta(y) cos aϕ = Ta(y) -T b (x) cos aϕ = 0, then T b (x) = Ta(x) = 0 and Equation 6 is not satisfied. We thus have either T ′ b (x) = 0 and Ta(y) -T b (x) cos aϕ = 0 that gives (b -1)×a real points because of the classical properties of Chebyshev polynomials, or T ′ a (y) = 0 and T b (x) -Ta(y) cos aϕ = 0 that gives b × (a -1) real double points.

Corollary 9 .Figure 3 :

 93 Figure 3: Implicit Chebyshev curves Theorem 8 is particularly interesting when m = n = d and a = b = 1.In this case the curve Tn(x) = Tn(y) is a union of ellipses and some lines. It will be useful for the determination of the double points of Chebyshev space curves. We have

Figure 4 :

 4 Figure 4: Double points in the parameters space

Figure 5 :

 5 Figure 5: P3 = 0, P4 = 0, Q5 = 0

2 and 1

 21 ≤ j ≤ b -1, from Proposition 10. Qc(s, t, ϕ) is a symmetric polynomial of Z[ϕ][t, s]. Let αi = iπ a , βj = jπ b and s = cos(αi + βj), t = cos(αiβj ). From s + t = 2 cos αi cos βj and st = cos 2 αi + cos 2 βj -1, we deduce that Qc(s, t, ϕ) belongs to Z[ϕ, cos αi][cos βj].

): Proposition 13 .

 13 Let α = iπ a , β = jπ b and γ = kπ c , where (a, b) = 1 and a is odd. P α,β,γ has a double root iff β = π 2 and sin γ = sin α. In this case, the double root is ϕ = 0. and Proposition 14. Let α = iπ a , β = jπ b and γ1

  95 = C(3, 13, 326, 1/85), 103 = C(4, 13, 348, 1/138), 1030 = C(4, 13, 306, 1/738), 1033 = C(4, 13, 856, 1/328), 1036 = C(3, 14, 385, 1/146), 1039 = C(3, 14, 373, 1/182).


Zhun-Ga Liu
email: liuzhunga@gmail.com

Quan Pan

Yong-Mei Cheng

Jean Dezert
email: jean.dezert@onera.fr

Sequential adaptive combination of unreliable sources of evidence

Keywords: evidence theory, combination rule, evidence distance, conflicting belief

In theories of evidence, several methods have been proposed to combine a group of basic belief assignments altogether at a given time. However, in some applications in defense or in robotics the evidences from different sources are acquired only sequentially and must be processed in real-time and the combination result needs to be updated the most recent information. An approach for combining sequentially unreliable sources of evidence is presented in this paper. The sources of evidence are not considered as equi-reliable in the combination process, and no prior knowledge on their reliability is required. The reliability of each source is evaluated on the fly by a distance measure, which characterizes the variation between one source of evidence with respect to the others. If the source is considered as unreliable, then its evidence is discounted before entering in the fusion process. Dempster's rule of combination and its main alternatives including Yager's rule, Dubois and Prade rule, and PCR5 are adapted to work under different conditions. In this paper, we propose to select the most adapted combination rule according to the value of conflicting belief before combining the evidence. The last part of this paper is devoted to a numerical example to illustrate the interest of this approach.

I. INTRODUCTION

Evidence theories 1 are widely applied in the field of information fusion. A particular attention has been focused on how to efficiently combine sources of evidence altogether at the same time (static approach), and many rules aside Dempster's rule have been proposed [START_REF] Deng | Combining belief functions based on distance of evidence[END_REF], [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF], [START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF], [START_REF] Yager | Hedging in the combination of evidence[END_REF]. In many applications however, the evidences from different sources are acquired sequentially by different sensors or human experts and the belief updating and decision-making need to be taken in realtime which requires a sequential/dynamic approach rather than a static approach of the fusion problem.

Usually the evidences arising from different independent sources are often considered equally reliable in the combination process, when the prior knowledge about the reliability of each source is unknown. However, all the sources of evidence to be combined can have different reliabilities in real applications. If the sources of evidence are considered as equireliable, the unreliable ones may bring a very bad influence on combination result, and even leads to inconsistent results and wrong decisions. Thus, the reliability of each source must be taken account in the fusion process as best as possible to provide a useful and unbiased result. In this work, we propose to evaluate on the fly the relability of the sources to combine based on an evidential distance/reliability measure. From this reliability measure, one can discount accordingly the unreliable sources before applying a rule of combination of basic belief assignments (bba's).

Many rules, like Dempster's rule [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] and its alternatives can be used to combine sources of evidences expressed by bba's and they all have their drawbacks and advantages (see [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF], Vol. 1, for a detailed presentation). Dempster's rule, is usually considered well adapted for combining the evidences in low conflict situations and it requires acceptable complexity when the dimension of the frame of discernment is not too large. Dempster's rule however provides counter-intuitive behaviors when the sources evidences become highly conflicting. To palliate this drawback, several interesting alternatives have been proposed when Dempster's rule doesn't work well, mainly: Yager's rule [START_REF] Yager | Hedging in the combination of evidence[END_REF], Dubois and Prade rule (DP rule) [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF], and PCR5 (proportional conflict redistribution rule no 5) [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF] developed in DSmT framework. The difference among Dempster's rule and its main alternatives mainly lies in the distribution of the conflicting belief m ⊕ (∅) which is generally used to characterize the total amount of conflict [START_REF] Liu | Analyzing the degree of conflict among belief functions[END_REF] between sources. In this paper, we propose to select the proper rule of combination based on the value of the total degree of conflict m ⊕ (∅). The last part of this paper presents a numerical example to show how the approach of sequential adaptive combination of unreliable sources of evidence works.

II. PRELIMINARIES

A. Basics of Dempster-Shafer theory (DST)

DST [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] is developed in Shafer's model. In this model, a fixed set Θ = {θ 1 , θ 2 , . . . , θ n } is called the frame of discernment of fusion problem. All the elements in Θ are mutually exclusive and exhaustive. The set of all subsets of Θ is called the power set of Θ, and it is denoted

2 Θ . For instance, if Θ = {θ 1 , θ 2 , θ 3 }, then 2 Θ = {∅, θ 1 , θ 2 , θ 3 , θ 1 ∪ θ 2 , θ 1 ∪ θ 3 , θ 2 ∪ θ 3 , θ 1 ∪ θ 2 ∪ θ 3 }. A basic belief assignment (bba), also called mass of belief, is a mapping m : 2 Θ → [0, 1] associated to a given body of evidence B such that m(∅) = 0 and A∈2 Θ m(A) = 1. The credibility (also called belief) of A ⊆ Θ is defined by Bel(A) = B∈2 Θ B⊆A m(B).
The commonality function q(.) and the plausibility function P l(.) are also defined by Shafer in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. The functions m(.), Bel(.), q(.) and P l(.) are in one-to-one correspondence.

Let m 1 (.) and m 2 (.) be two bba's provided by two independent bodies of evidence B 1 and B 2 over the frame of discernment Θ. The fusion/combination of m 1 (.) with m 2 (.), denoted m(.) = [m 1 ⊕ m 2 ](.) is obtained in DST with Dempster's rule of combination as follows:

     m(∅) = 0 m(A) = X 1 ∩X 2 =A m1(X1)m2(X2) X 1 ∩X 2 =∅ m1(X1)m2(X2) ∀A = ∅, A ∈ 2 Θ (1)
The degree of conflict between the bodies of evidence B 1 and B 2 is defined by

m ⊕ (∅) = X1,X2∈2 Θ X1∩X2=∅ m 1 (X 1 )m 2 (X 2 ) (2)
Dempster's rule can be directly extended to the combination of S independent and equally reliable sources. It is a commutative and associative rule of combination and it preserves the neutral impact of the vacuous belief assignment defined by m vba (Θ) = 1.

B. Main alternatives to Dempster's rule

Dempster's rule yields counterintuitive results when the evidences highly conflict because of its way of assigning the mass of conflicting belief m ⊕ (∅). Thus, a lot of alternatives to Dempster's rule have been proposed for overcoming limitations of Dempster's rule. The main alternative rules including Yager's rule [START_REF] Yager | Hedging in the combination of evidence[END_REF], DP rule [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF] and PCR5 [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF] are briefly recalled.

• Yager's rule: Yager admits the conflicting belief is not reliable. So m ⊕ (∅) is transferred to the total ignorance in Yager's rule. It is given by m(∅) = 0 and for

A = ∅, A ∈ 2 Θ by      m(A) = X,Y ∈2 Θ X∩Y =A m 1 (X)m 2 (Y ), for A = Θ m(Θ) = m 1 (Θ)m 2 (Θ) + X,Y ∈2 Θ X∩Y =∅ m 1 (X)m 2 (Y ) (3)
• Dubois & Prade rule: This rule assumes that if two sources of evidence are in conflict, one of them is right but we don't know which one. Thus, if X ∩ Y = ∅, then the mass committed to the set X ∩ Y by the conjunctive operator should be transferred to X ∪ Y . According to this principle, DP rule is defined by m(∅) = 0 and for

A = ∅ and A ∈ 2 Θ by m(A) = X,Y ∈2 Θ X∩Y =A m 1 (X)m 2 (Y ) + X,Y ∈2 Θ X∩Y =∅ X∪Y =A m 1 (X)m 2 (Y ) (4)
• PCR5 rule: PCR5 transfers the partial conflicting mass to the elements involved in the conflict, and it is considered as the most mathematically exact redistribution of conflicting mass to nonempty sets following the logic of the conjunctive rule. PCR5 is defined by m(∅) = 0 and

∀A = ∅, A ∈ 2 Θ by m(A) = X1,X2∈2 Θ X1∩X2=A m 1 (X 1 )m 2 (X 2 )+ X2∈2 Θ X2∩A=∅ [ m 1 (A) 2 m 2 (X 2 ) m 1 (A) + m 2 (X 2 ) + m 2 (A) 2 m 1 (X 2 ) m 2 (A) + m 1 (X 2 ) ] (5)
The details, examples and the extension of PCR5 formula (5) for S > 2 sources are given in [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF].

C. Discounting source of evidence

When the sources of evidences are not considered equally reliable, it is reasonable to discount each unreliable source s i , i = 1, 2, . . . , S by a reliability factor α i ∈ [0, 1]. Following the classical discounting method [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], a new discounted bba m (.) is obtained from the initial bba m(.) provided by the unreliable source s i as follows

   m (A) = α i • m(A), A = Θ m (Θ) = 1 -A∈2 Θ A =Θ m (A) (6)
α i = 1 means that the total confidence in the source s i , and the original bba doesn't need to be discounted. α i = 0 means that the source is s i is totally unreliable and its bba is revised as a vacouous bba m (Θ) = 1, which will have a neutral impact in the fusion process. In practice, the discounting method can be used efficiently if one has a good estimation of the reliability factor of each source. We show in the next section how one can evaluate the relability of a source.

III. EVALUATING THE RELIABILITY OF EACH SOURCE

Without prior knowledge on the reliability of the sources of evidence, we propose to evaluate the reliability factors of each source based on the distance between the bba from a given source s i with respect to the others. If the bba of the given source, say s i varies too much with respect to the others, this source of evidence is considered not reliable and it will be discounted before to be combined. We will show further how the discounting/reliability factor can be estimated. We implicitly assume here that the following principle "Truth is reflected by the majority of opinions" holds.

In [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF], Jousselme et al. have proposed the following distance measure d J (m 1 , m 2 ) between two bba's2 m 1 m 1 (.) and m 2 m 2 (.) defined on the same power set 2 Θ :

d J (m 1 , m 2 ) = 1 2 (m 1 -m 2 ) T D(m 1 -m 2 ) (7)
where D is a 2 |Θ| × 2 |Θ| positive matrix whose elements are defined as

D ij |Ai∩Bj | |Ai∪Bj |
where A i and B j are elements of the power set 2 Θ . d J (m 1 , m 2 ) ∈ [0, 1] is a distance which measures the similarity between m 1 and m 2 considering both the values and the relative specificity of focal elements of each bba.

The total degree of conflict m ⊕ (∅) obtained from all focal elements which are incompatible doesn't actually capture the similarity between bba's as shown by Martin et al. in [START_REF] Martin | Conflict measure for the discounting operation on belief functions[END_REF].

If N pieces of evidence m 1 , m 2 , . . . , m N are combined sequentially, two approaches similarly with [START_REF] Martin | Conflict measure for the discounting operation on belief functions[END_REF] could be used to measure the variation between m j and the others. One considers the average value d J between m j and the others which is given by

d j-1 1 (m j ) = 1 j -1 j-1 i=1 d J (m j , m j-i ) (8)
The other one is simply defined as

d j-1 2 (m j ) = d J (m j , m j-1 1 ) (9)
where m j-1

1 m j-1 1 (.) is obtained by the sequential combinination of the bba's m 1 (.), m 2 (.),. . . , m j-1 (.), i.e. m j-1 1 (.) = (((m 1 ⊕ m 2 ) ⊕ m 3 ) • • • ⊕ m j-1 )(.
) with a fusion rule such as Dempster's rule, Yager's rule, DP rule, PCR5, etc. The second measure, d j-1 2 (m j ), reflects only the difference between m j and the combined bba m j-1 1 and thus cannot precisely measure the similarity between m j and the other individual evidences m 1 (.), m 2 (.), . . . , m j-1 (.) because some information on specificities of these individual bba's has been lost forever through the fusion process. The following examples will show the distinction between these two methods. Example 1: Let's consider the frame of discernment Θ = {A, B, C}, Shafer's model and the same following bba's

m 1 (.) : m 1 (A) = 0.5, m 1 (B) = 0.2 m 1 (A ∪ B) = m 1 (C) = m 1 (Θ) = 0.1 m 2 (.) : m 2 (A) = 0.5, m 2 (B) = 0.2 m 2 (A ∪ B) = m 2 (C) = m 2 (Θ) = 0.1 . . . m j (.) : m j (A) = 0.5, m j (B) = 0.2 m j (A ∪ B) = m j (C) = m j (Θ) = 0.1
The difference between m j (.), for j ≥ 2, and all the bba's m i (.), for i < j according to formula (8) gives d j-1 1 (m j ) = 0, which shows correctly that m j (.) is identical to the other bba's m i (.), for i < j. If one uses the measure d j-1 2 (m j ) defined in [START_REF] Yager | Hedging in the combination of evidence[END_REF], one gets the results plotted in Fig. 1. One sees that there exists a variation of the similarity measure using all different fusion rules with a trend to certain values when j increases. This is a bad behavior since we know that m j equals to the others bba's and we would expect to get d j-1 2 (m j ) = 0 which unfortunately is not the case. That is the main reason why we abondon the use of d j-1 2 (m j ) measure in the sequel of this work. . . .

m j-1 (.) : m j-1 (Θ) = 1 m j (.) : m j (A) = 0.6, m j (B) = m j (C) = 1, m j (D) = m j (E) = 0.1
In this example, m j (.) = m 1 (.), but m j (.) is quite different from the others bba's m i (.), i = 1. The similarity measure d j-1 1 (m j ) between m j (.), for j ≥ 3 and the bba's m i (.),

i < j is d j-1 1 (m j ) = 0.2(j-2) j-1
which shows a trend to 0.2 when j increases. However in such case, one always gets using Dempster's rule, Yager's rule, DP rule or PCR5 rule d j-1 2 (m j ) = 0. From such very simple example, one sees that one cannot detect the dissimilarity of m j (.) with a majority of quite distinct bba's when d j-1 2 (m j ) measure is used. This shows again that d j-1 2 (m j ) is actually not very appropriate for measuring the similarity between a given bba m j (.) and a set of bba's. Therefore we will only consider the measure of similarity d j-1 1 (m j ) in the sequel.

For managing the computational burden in applications, a parameter n ≤ j -1 is introduced in the measure d j-1 1 (m j ) and we define the new measure:

d j-1 n (m j ) = 1 min(n, j -1) min(n,j-1) i=1 d J (m j , m j-i ) (10)
The accuracy and the computational complexity of this similarity measure increases when n tends to j -1.

Let 's consider a given discounting tolerance threshold

ω d in [0, 1]. If d j-1 n (m j ) ≥ ω d , it
indicates that the bba m j (.) will be considered as not similar enough with respect to other bba's and therefore the source s j is considered as unreliable and must be discounted before entering in the fusion process. The unreliability of the source s j may be caused by a fault of the sensor or unexpected noises, condition changes, etc. In such case, the bba m j (.) needs to be discounted by formula [START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF]. As proposed by Martin et al. in [START_REF] Martin | Conflict measure for the discounting operation on belief functions[END_REF], the reliability factor of the source s j is chosen as

α j = (1 -d j-1 n (m j ) λ ) 1/λ
where the parameter λ is defined in the easiest way with λ = 1.

The larger dissimilarity leads to the less reliability factor. If d j-1 n (m j ) < w d , it means that the dissimilarity between m j (.) with other bba's is acceptable, and there is no need to revise/discount m j (.) in such case.

IV. SELECTION OF COMBINATION RULES

After evaluating the reliability of the sources, we have to select a suitable combination rule. Dempster's rule is known to offer pretty good performances when the combined bba's are not in too high conflict, otherwise when the conflict becomes too large it is generally considered safer to use alternative rules like Yager's rule, DP rule, and PCR5 rule. The following examples show the difference between the different approaches for the fusion of sources of evidences. Example 3: This is Zadeh's example [START_REF] Zadeh | Review of books: A mathematical theory of evidence[END_REF]. Let's consider Θ = {A, B, C} with Shafer's model and the following bba's m 1 (.) : m 1 (A) = 0.9, m 1 (B) = 0.1 m 2 (.) : m 2 (B) = 0.1, m 2 (C) = 0.9

One sees that the two sources are in very high conflict because the total conflict is m 1,2 ⊕ (∅) = 0.99. Using Dempster's rule, one gets surprisingly m(B) = 1 which is somehow conterintuitive since m 1 and m 2 both believe in B with a little chance, but the fusion result states that B is the only possible solution with certainty, which seems unreasonable 3 . If we use Yager's rule, DP rule, and PCR5, one gets:

• Yager's rule: m(B) = 0.01, m(Θ) = 0.99 • DP rule: m(B) = 0.01, m(A ∪ B) = 0.09, m(A ∪ C) = 0.81, m(B ∪ C) = 0.09 • PCR5: m(A) = 0.486, m(B) = 0.028, m(C) = 0.4860
These results are more reasonable in some sense, but they are not the same. Yager's rule transfers all the conflicting mass to total ignorance and produces the least specific result in the three rules. DP rule distributes the conflicting mass to the union of the involved sets, which makes the uncertainty of the result still very large. DP rule produces a less specific result than PCR5 but DP is a bit more specific than Yager's rule. PCR5 provides the most specific result since A and C share the same bba whereas B keeps a very low belief assignment.

Therefore, in order to avoid to get counterintuitive results, it is reasonable to use Yager's rule, DP rule, or PCR5 than Dempster's rule as soon as the level of conflict becomes large. The choice among Yager's rule, DP rule, and PCR5 depends on the application and the computational resource one has. PCR5 is very appropriate if a decision has to be made because it provides the most specific solution, but PCR5 requires the most computational burden. Sometimes it better to get less specific result if we don't need to take a clear/precise decision in case of high conflict between sources. In such case, Yager's rule and/or DP rule can be used instead. When the level of conflict between two bba's is low Dempster's rule can be used since it offers a good compromise between computational complexity and the specificity of the result. Example 4: Let's consider Θ = {A, B, C} and

m 1 (.) : m 1 (A) = 0.35, m 1 (B) = 0.3, m 1 (A ∪ B) = 0.15, m 1 (C) = 0.2 m 2 (.) : m 2 (A) = 0.35, m 2 (B) = 0.3, m 2 (A ∪ C) = 0.05, m 2 (A ∪ B) = m 2 (C) = m 2 (Θ) = 0.1 m 3 (.) : m 3 (A) = 0.3, m 3 (B) = 0.3, m 3 (A ∪ B) = 0.2, m 3 (C) = m 3 (A ∪ C) = 0.1
The conflicts between each pair of bba's are given by m 1,2 ⊕ (∅) = 0.455, m 1,3 ⊕ (∅) = 0.395, m 2,3 ⊕ (∅) = 0.395. The levels of these conflicts are not too large according and the sequential combination m(.) = [[m 1 ⊕ m 2 ] ⊕ m 3 ](.) using the different rules yields

• Dempster's rule: m(A) = 0.5868, m(B) = 0.3592, m(A ∪ B) = 0.0202, m(C) = 0.0338 • Yager's rule: m(A) = 0.3105, m(B) = 0.243, m(C) = 0.0555, m(A ∪ B) = 0.097, m(A ∪ C) = 0.0455, m(Θ) = 0.2485 • DP rule: m(A) = 0.3255, m(B) = 0.2295, m(C) = 0.0435, m(A ∪ B) = 0.1975, m(A ∪ C) = 0.0575, m(B ∪ C) = 0.0345, m(Θ) = 0.112 • PCR5: m(A) = 0.4889, m(B) = 0.3941, m(C) = 0.0819, m(A ∪ B) = 0.0268, m(A ∪ C) = 0.
0083 All the rules provide reasonable results with assigning the largest belief to A, but Dempster's rule produces the most specific result with a less computational effort. Dempster's rule is thus well appropriate when m ⊕ (∅) is not too large.

V. ADAPTIVE COMBINATION OF SEQUENTIAL EVIDENCE

Here we are concerned with the real-time decision-making problem from the sequential acquisition of bba's m 1 (.), m 2 (.),. . . , m N (.) defined on a same frame Θ without any prior knowledge about reliability of each source. We start with m 1 (.). When m 2 (.) is available, one combines it with m 1 (.) by a suitable rule according to the value of m 1,2 ⊕ (∅) without evaluating the reliability of the two sources. When m j (.), for j ≥ 3 becomes available at the time j, the reliability of the source s j is evaluated and m j (.) is discounted (if necessary) by the approach presented in section III. Before combining the discounted bba m j (.) (or m j (.) when no discounting occurs) with the last updated bba m j-1 1 (.), the combination rule is selected according to the value of the conflict between m j (.) and m j-1 1 (.). We use a threshold ω ∅ . If m ⊕ (∅) < ω ∅ , Dempster's rule is selected because it offers a good compromise between complexity and specificity. Otherwise, Yager's rule, DP rule, or PCR5, are selected upon the actual application to avoid to get counterintuitive results.

The tuning of thresholds ω d and ω ∅ is not easy in general. If the thresholds are too large, one takes the risk to get counterintuitive results, whereas if they are set to too low values the non specificity of the result will become large and even will lead to decision-making under big uncertainty. Therefore, both thresholds ω d and ω ∅ need to be determined by accumulated experience depending on the actual application .

VI. NUMERICAL EXAMPLE

Let us suppose a multisensor-based target identification system. From five independent sensors, the system collects five pieces of evidence sequentially (actually we consider here 2 possible bba's m 5A (.) and m 5B (.) for the fifth source). For decision-making in real-time, the combination result needs to be updated right after the new evidence arrives. The bba's defined on the power set of Θ = {A, B, C} are as follows The five pieces of evidence are combined sequentially, and the results are presented in Table 1. The chosen thresholds are ω d = 0.6, ω ∅ = 0.6 and n = 5.

All the rules provide reasonable results when combining consistent bba's m 1 (.) and m 2 (.). The bba m 3 (.) is highly conflicting with m 1 (.) and m 2 (.). If there is no prior information about the reliability of the sources, we evaluate the reliability of each source according to its variation with respect to the others. The average similarity distance between m 3 and m 1 , m 2 is so large that d j-1 n (m 3 ) > ω d . Thus, m 3 (.) is considered unreliable. If we combine directly (without discounting) m 3 (.) with m 2 1 (.) using Dempster, Yager, DP or PCR5, one gets a high belief in B with all the rules.

With the adaptive rule, the bba of m 3 (.) is discounted with the reliability factor α = 1 -d j-1 n (m 3 ) to get m 3 (.). The combination of m 3 (.) with m 2 1 (.) assigns now the highest belief in A. This adaptive method is helpful to deal with the high conflicts caused by the unreliability of the sources. The difference between m 4 (.) and m 1 (.), m 2 (.), m 3 (.) is below the tolerance threshold, but the value of m ⊕ (∅) between m 4 (.) and m 3 1 (.) is very large, and m ⊕ (∅) = 0.8334 > ω ∅ . The result of Dempster's rule indicates that the most credible hypothesis is B, whereas A is not possible to happen, which is not reasonable. The results produced by Yager's rule and DP rule selected in adaptive rule is full of uncertainty, and we even can't make a clear decision from them because of their ways of distributing the mass of conflicting belief. We can get the specific output that most belief focuses on hypothesis A only if PCR5 is selected in the adaptive rule. As we can see, m 1 (.) and m 2 (.) strongly support the hypothesis A, whereas m 3 (.) and m 4 (.) strongly support B. It is not easy to be sure what is the true hypothesis. The adaptive rule tends to preserve the earlier decision, since it assumes that m 1 (.) and m 2 (.) where totally reliable, and then m 3 (.) is considered unreliable and thus discounted. When m 5 (.) is available, if m 5 (.) strongly supports A as with m 5A (.), the combination results of all the adaptive rules commit their highest belief in A. If m 5 (.) strongly supports B as with m 5B (.), the combination results will change and assign the highest belief in B. The results produced by the adaptive rule with selecting combination rules between Dempster and PCR5 are always most specific, which is very useful and helpful for decisionmaking in real-time. The good performance of adaptive rules lies in the method of evaluating the reliability of sources and the way for automatically selecting suitable combination rules.

VII. CONCLUSIONS

An approach for adaptive combination of unreliable sources of evidence has been proposed in this paper for combining sequentially the sources without prior knowledge on their reliabilities. The reliability of each source is evaluated according to its similarity with respect to the others which is measured by an average distance of similarity. When a source is not reliable enough, its bba is discounted to diminish its influence in the fusion process and on decision-making. Before the fusion of the sources, the suitable combination rule is selected depending on the mass of conflicting belief m ⊕ (∅) and the compromise between the computational burden and the specificity of the result one wants to deal with. Whenever m ⊕ (∅) is below the tolerance threshold, Dempster's rule can be chosen as a good rule of combination for such a compromise. Otherwise, Yager's rule, DP rule, or PCR5 must be selected to avoid to get counterintuitive results. The choice among these three rules depends on the application and the acceptable risk in decision-making errors. PCR5 rule is very appropriate to use in general for decision-making because it provides the most specific fusion results, but it requires more computational resources than other rules. If we want to keep uncertain results and don't necessarily need a very specific decision in case of high conflict between sources, Yager's rule or DP rule can be selected instead. Our numerical example shows the interest of the proposed approach. The main difficulty however lies in the tuning of the thresholds ω d , ω ∅ and the parameter n involved in its implementation. These parameters must be selected by experience depending on the application. This approach was based on Shafer's model, but could be extended to other models proposed in DSmT.

Fig. 1 :

 1 Fig. 1: Variation of the similarity measure d j-1 2 (m j ) based on different fusion rules.

Example 2 :

 2 Let's consider the frame of discernment Θ = {A, B, C, D, E}, Shafer's model, and the following bba's m 1 (.) : m 1 (A) = 0.6, m 1 (B) = m 1 (C) = 0.1 m 1 (D) = m 1 (E) = 0.1 m 2 (.) : m 2 (Θ) = 1 m 3 (.) : m 3 (Θ) = 1

m 1 (

 1 .) : m 1 (A) = 0.8, m 1 (B) = 0.1, m 1 (Θ) = 0.1 m 2 (.) : m 2 (A) = 0.4, m 2 (B) = 0.25, m 2 (C) = 0.2, m 2 (B ∪ C) = 0.15, m 3 (.) : m 3 (B) = 0.9, m 3 (C) = 0.1, m 4 (.) : m 4 (B) = 0.45, m 4 (C) = 0.45, m 4 (B ∪ C) = 0.1, m 5A (.) : m 5A (A) = 0.5, m 5A (A ∪ B) = 0.25, m 5A (C) = 0.1, m 5A (A ∪ C) = 0.15, m 5B (.) : m 5B (B) = 0.5, m 5B (A ∪ B) = 0.25, m 5B (C) = 0.1, m 5B (B ∪ C) = 0.15.

DST (Dempster-Shafer Theory)[START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] or DSmT (Dezert-Smarandache Theory)[START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF].

Here for notation convenience, we use the usual vectorial notation m 1 and m 2 (with boldfaced letter) for representing the entire bba's usually denoted m 1 (.) and m 2 (.). m 1 and m 2 are vectors of dimension 2 |Θ| × 1. We assume that the bba's vectors are both ordered using the same order for their components.

More generally, one can show that Dempster's rule can become insensitive to the variation of input bba's to combine -see[START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF], Vol. 1, Chap. 5, p. 114 for example.

Acknowledgement

This work was supported by a grant from the National Natural Science Foundation of China(NO.60634030,60775012).

Adaptive rule (Dempster&Yager)