Raphaël Cerf -

Carlo Mariconda

ON BANG-BANG CONSTRAINED SOLUTIONS OF A CONTROL SYSTEM

Keywords:

there exists a bang-bang solution y to (P) satisfying y ≤ x; moreover there exists a finite union of intervals E such that y

The reachable set of bang-bang constrained solutions is convex; an application to the calculus of variations.

1991 Mathematics Subject Classification. 34H05

Introduction

We consider the family of bidimensional linear control systems (P ) described by a generic second order equation subject to a scalar control:

x + a 1 (t)x + a 0 (t)x ∈ Φ(t) = [φ 1 (t), φ 2 (t)] a.e., (x(0), x (0), x(T ), x (T )) = (x 0 , v 0 , x 1 , v 1 ) where φ 1 ≤ φ 2 ∈ L 1 ([0, T ]) and a 1 , a 0 ∈ C([0, T ]), x 0 , v 0 , x 1 , v 1 ∈ R, x ∈ W 2,1 ([0, T ]). The function y is said to be a bang-bang solution to (P ) if it solves (P ) and moreover y + a 1 (t)y + a 0 (t)y ∈ extr Φ(t) = {φ 1 (t), φ 2 (t)} a.e.

(

) 1
Existence of bang-bang solutions has been proved for instance by Cesari [START_REF] Cesari | Optimization-theory and applications[END_REF]Theorem 16.3]. The purpose of this paper is to prove that given an arbitrary solution x to (P ), there exists a bang-bang solution y such that

∀t ∈ [0, T ] y(t) ≤ x(t) (2)
and in addition y + a 1 y + a 0 y steers from φ 1 to φ 2 only a finite number of times. Motivation of such a problem was to study the reachable set Y c T = {(y(T ), y (T )) : y ≤ c, y + a 1 (t)y + a 0 (t)y ∈ extr Φ(t) a.e., (y(0), y (0)) = (x 0 , v 0 )} where c is an arbitrary function. A consequence of Theorem 3.1 is that Y c T coincides with X c T = {(y(T ), y (T )) : y ≤ c, y + a 1 (t)y + a 0 (t)y ∈ Φ(t) a.e., (y(0), y (0)) = (x 0 , v 0 )}. Notice that X c T is convex so that the above assumption implies that Y c T is convex too. Another motivation arises from non-convex problems of the calculus of variations (see [START_REF] Amar-A | On passing to the limit for non convex variational problems[END_REF]).

A possible approach in order to find bang-bang solutions is to use Lyapunov Theorem on the range of a vector measure [4, §16.1].

Here, the solution of x + a 1 (t)x + a 0 (t)x = ρ(t), x(0) = x (0) = 0 is given by x(t) = t 0 h(t, s)ρ(s) ds where h ∈ C 1 ([0, T ] × [0, T ]) and for each s ∈ [0, T ] the function h s (.) = h(., s) ∈ C 2 ([0, T ]) is the solution to the associated homogeneous differential equation satisfying the initial conditions h s (s) = 0, h s (s) = 1; Lyapunov Theorem yields the existence of a measurable subset E of [0, T ] such that

T 0 h(T, s)ρ(s) ds = T 0 h(T, s)(φ 1 (s)χ E (s) + φ 2 (s)χ [0,T ]\E (s)) ds, (3)
T 0 ∂h ∂t (T, s)ρ(s) ds = T 0 ∂h ∂t (T, s)(φ 1 (s)χ E (s) + φ 2 (s)χ [0,T ]\E (s)) ds. (4) 2
Clearly, by differentiating under the integral sign, the function y defined by

y(t) = t 0 h(t, s)(φ 1 (s)χ E (s) + φ 2 (s)χ [0,T ]\E (s)) ds (5)
is a bang-bang solution. However, this approach does not give any information on the behaviour of y with respect to x on [0, T ].

Here we prove a new Lyapunov's type theorem concerning the range of a two-dimensional vector measure whose densities are such that their quotient is monotone: in this case, the set E can be chosen in the form [α, β]. Remark that this is not true in general; for instance there are no α, β ∈ [0, 3π] satisfying

β α sin t dt = 3π 0 sin tχ [0,π]∪[2π,3π] (t) dt β α 1 dt = 3π 0 1χ [0,π]∪[2π,3π] (t) dt.
In our application the equalities h(s, s) = 0 and ∂h ∂t (s, s) = 1 imply that the monotonicity condition is locally fulfilled; this allows us to build a set E satisfying (3)-( 4) as a finite union of intervals and, in the case where φ 1 < ρ < φ 2 are continuous, to choose E in such a way that neither 0 nor T belong to its closure. These facts, together with a decomposition of the kernel h(t, s) into a linear combination of linearly independent functions are the main tools that we use in order to show that the bang-bang solution y defined by ( 5) satisfies the inequality y ≤ x.

As an application we consider the problem of minimizing the integral functionals

I(x, u) = T 0 f (t, x(t), u(t)) dt where x : [0, T ] → R 2 is such that x(0), x (0), x(T ), x (T ) are fixed and u is a control belonging to U (t, x) ⊂ R 2 .
The classical approach to obtain existence of a minimum is to impose conditions in order to have the lower semicontinuity of I with respect to u (for instance convexity of u → f (t, x, u)).

Recently in an effort to provide existence criteria other than convexity in u some sufficient conditions have been given: for problems of the calculus of variations (x = u in the above setting) and for maps of the form f (t, x, x ) = g(t, x) + h(t, x ), existence of solutions has been obtained by requiring that the real map x → g(t, x) be monotone [START_REF] Marcellini | Alcune osservazioni sull'esistenza del minimo di integrali del calcolo delle variazioni senza ipotesi di convessitá[END_REF] or, for x in R n , that the same function be concave [START_REF] Cellina | On a classical problem of the calculus of variations without convexity assumptions[END_REF]. Optimal control problems escaping to convexity conditions have been handled in [START_REF] Raymond | Existence theorems in optimal control problems without convexity assumptions[END_REF]. It has been proved further in [START_REF] Cellina | The existence question in the calculus of variations: a density result[END_REF] that there exists a dense subset D of C(R) such that, for g in it, the problem minimize

T 0 g(x(t)) dt + T 0 h(x (t)) dt : x(0) = x 0 , x(T ) = x 1
admits a solution for every lower semicontinuous h satisfying growth conditions. Our theorem gives a straightforward generalization of the above result.

Assumptions and Preliminary Results

Let φ 1 , φ 2 ∈ L 1 [0, T ], φ 1 ≤ φ 2 and put Φ(t) = [φ 1 (t), φ 2 (t)] ⊂ R. We are interested in the solutions of the following control problem.

Problem P. a 1 , a 0 ∈ C([0, T ]), x 0 , x 1 , v 0 , v 1 ∈ R, x ∈ W 2,1 [0, T ]
x + a 1 (t)x + a 0 (t)x ∈ Φ(t) a.e.

(P)

x(0) = x 0 , x (0) = v 0 , x(T ) = x 1 , x (T ) = v 1 .
By extr Φ we mean the extreme points of Φ i.e. extr Φ(t) = {φ 1 (t), φ 2 (t)}.

Definition 2.1. A function y ∈ W 2,1 [0, T ] is said to be a bang-bang solution to (P) if y solves (P) and, moreover,

y + a 1 (t)y + a 0 (t)y ∈ extr Φ(t) a.e.
The following representation formula of the solutions to (P) will be used later.

Proposition 2.1. There exists a function h ∈ C 1 ([0, T ] × [0, T ]) satisfying Property (S) below such that, for each function ρ ∈ L 1 ([0, T ]), the solution of

x + a 1 (t)x + a 0 (t)x = ρ(t), x(0) = x (0) = 0 (P ρ )
is given by the formula

x(t) = t 0 h(t, s)ρ(s) ds . (2.1)
Moreover for each s ∈ [0, T ] the function h(., s) is of class C 2 ([0, T ]).

Property S.

1) There exist

w 1 , w 2 ∈ C 2 ([0, T ]) , z 1 , z 2 ∈ C 1 ([0, T ]) such that ∀s, t ∈ [0, T ] h(t, s) = w 1 (t)z 1 (s) + w 2 (t)z 2 (s) (2.2) and W (w 1 , w 2 , t) = det w 1 (t) w 2 (t) w 1 (t) w 2 (t) = 0.
For each t 0 in [0, T ] there exists δ > 0 such that if we set

I δ = [t 0 -δ, t 0 + δ] ∩ [0, T ] then: 2) ∀s, t ∈ I δ h(t, s) > 0 if s < t, h(t, s) < 0 if t < s (whence h(s, s) = 0); 3) ∀s, t ∈ I δ ∂h ∂t (t, s) > 0; 4) ∀t ∈ I δ s → h(t, s)/ ∂h ∂t (t, s) is decreasing on I δ . Proof of Proposition 2.1. For each s ∈ [0, T ], let h s (.) = h(., s) ∈ C 2 ([0, T ]) be the solution to h s (t) + a 1 (t)h s (t) + a 0 (t)h s (t) = 0 h s (s) = 0, h s (s) = 1.
Set z(t) = t 0 h(t, s)ρ(s) ds. Differentiation under the integral sign shows that z is a solution to (P ρ ) whence, by uniqueness, z = x. In order to prove the second part of the claim, let w 1 , w 2 ∈ C 2 ([0, T ]) be two solutions of the differential equation

x + a 1 (t)x + a 0 (t)x = 0 (2.3) such that their wronskian

W (w 1 , w 2 , t) = det w 1 (t) w 2 (t) w 1 (t) w 2 (t)
is non zero for every t. Such functions exist since the set of the solutions of a second order linear differential equation is a two-dimensional vector space. Since for each s ∈ [0, T ], the function h s is a solution to (2.3) then there exist z 1 , z 2 defined on [0, T ] such that

∀s, t ∈ [0, T ] h s (t) = w 1 (t)z 1 (s) + w 2 (t)z 2 (s). ( 2

.4)

Conditions on h s at s and equation (2.4) yield

h s (s) = 0 = w 1 (s)z 1 (s) + w 2 (s)z 2 (s) h s (s) = 1 = w 1 (s)z 1 (s) + w 2 (s)z 2 (s)
Since W (w 1 , w 2 , s) = 0 for each s, we find

z 1 (s) = - w 2 (s) W (w 1 , w 2 , s) , z 2 (s) = w 1 (s) W (w 1 , w 2 , s) so that z 1 , z 2 ∈ C 1 ([0, T ]) hence h(t, s) = h s (t) belongs to C 1 ([0, T ] × [0, T ]). By construction ∀s ∈ [0, T ] h(s, s) = 0 and ∂h ∂t (s, s) = 1 implying ∀s ∈ [0, T ] d ds h(s, s) = 0 ⇔ ∀s ∈ [0, T ] ∂h ∂t (s, s) + ∂h ∂s (s, s) = 0 ⇔ ∀s ∈ [0, T ] ∂h ∂s (s, s) = -1. As a consequence ∀s ∈ [0, T ] ∂ ∂s h ∂h ∂t (s, s) = -1.
By continuity for a fixed t 0 in [0, T ], there exists δ > 0 such that

∀s, t ∈ [t 0 -δ, t 0 + δ] ∩ [0, T ] ∂h ∂t (t, s) > 0 and ∂ ∂s h ∂h ∂t (t, s) < 0;
for this δ properties S 2)3)4) are satisfied.

Assume for instance Φ(t) = [0, φ(t)] and let ρ ∈ L 1 [0, T ] be such that 0 ≤ ρ ≤ φ. For a solution x to (P ρ ) formula (2.1) yields, in particular,

x(T ) = T 0 h(T, s)ρ(s) ds , (2.5
)

x (T ) = T 0 ∂h ∂t (T, s)ρ(s) ds. (2.6)
Let us point out that the classical Lyapunov Theorem on the range of a vector measure [4, §16.1] allows to find a bang-bang solution. In fact its application yields the existence of a measurable subset E of [0, T ] such that

T 0 h(T, s)ρ(s) ds = T 0 h(T, s)φ(s)χ E (s) ds , (2.7)
T 0 ∂h ∂t (T, s)ρ(s) ds = T 0 ∂h ∂t (T, s)φ(s)χ E (s) ds , (2.8)
so that the function x defined by

x(t) = t 0 h(t, s)φ(s)χ E (s) ds
is, by Proposition 2.1, a bang-bang solution to (P) (with φ 1 = 0, φ 2 = φ, x 0 = v 0 = 0). However, for 0 < t < T , the Lyapunov Theorem does not give any information on the relative positions of x and the original solution x. The purpose of Proposition 2.2 below is to show that if s → h/ ∂h ∂t (t, s) is monotone on [0, T ] then the measurable subset E can be chosen to be an interval [α, β] with 0 ≤ α ≤ β ≤ T . This will allow us, taking into account property S 4), to define in §3 a bang-bang solution y satisfying y(t) ≤ x(t) for each t.

In what follows [a, b] is an interval of R, ρ and φ are two functions belonging to L 1 ([a, b]) satisfying 0 ≤ ρ ≤ φ. We say that r ∈ R is positive (resp. negative) if r ≥ 0 (resp. r ≤ 0). We consider the following hypothesis.

Hypothesis H. The functions f, g belong to L ∞ ([a, b]) and are positive almost everywhere. Moreover there exists a strictly monotone positive function k such that

g(t) = k(t)f (t) a.e.
We have the following Lyapunov's type result. Proposition 2.2. Let f, g satisfy hypothesis H. Then there exist α, β ∈ R such that, if we put E = [α, β], we have:

b a ρ(s)f (s) ds = β α φ(s)f (s) ds = b a φ(s)f (s)χ E (s) ds ; (2.9) b a ρ(s)g(s) ds = β α φ(s)g(s) ds = b a φ(s)g(s)χ E (s) ds .
(2.10)

Moreover, α and β are unique if ρ, φ, f, g are continuous, and 0 < ρ < φ, f > 0, g > 0.

In order to prove Proposition 2.2, we need the following fundamental Lemma. Proof of Lemma 2.1. Assume for instance that k is increasing. To prove (2.14) let f φ , f ρ be the monotone functions defined by

f φ (t) = t a φ(s)f (s) ds f ρ (t) = t a ρ(s)f (s) ds.
The Lebesgue-Stieltjes formula for integration by parts yields

b a ρ(s)g(s) ds = b a ρ(s)k(s)f (s) ds = b a k(s) df ρ (s) = k(b)f ρ (b) -k(a)f ρ (a) - b a f ρ (s) dk(s);
analogously we have

β a φ(s)g(s) ds = k(β)f φ (β) -k(a)f φ (a) - β a f φ (s) dk(s).
Taking into account that f φ (a) = f ρ (a) = 0 and that by (2.12)

f ρ (b) = f φ (β), we are thus led to show that b a f ρ (s) dk(s) - β a f φ (s) dk(s) ≤ (k(b) -k(β))f ρ (b).
(2.15)

By our assumptions we have

∀t ∈ [a, b] f φ (t) ≥ f ρ (t); (2.16) therefore b a f ρ (s) dk(s) - β a f φ (s) dk(s) ≤ b β f ρ (s) dk(s).
(2.17) Furthermore the functions f ρ and k being increasing we have

b β f ρ (s) dk(s) ≤ (k(b) -k(β))f ρ (b)
which, together with (2.17), gives (2.15).

To prove the final part of the lemma, it is enough to remark that if f > 0 and ρ > 0 then, by (2.12), β = a; if moreover 0 < ρ < φ a.e. then inequality (2.16) is strict for every t > a so that (2.17) is strict too (k being increasing). Similar arguments prove (2.13).

Proof of Proposition 2.2.

i) Existence. a) Assume first 0 < ρ < φ and f > 0 , g > 0 a.e. Let α 1 , α 2 , β 1 , β 2 ∈ [a, b] be such that b α 1 φ(s)f (s) ds = b a ρ(s)f (s) ds, (2.18) b α 2 φ(s)g(s) ds = b a ρ(s)g(s) ds, (2.19
)

β 1 a φ(s)f (s) ds = b a ρ(s)f (s) ds, (2.20)
β 2 ≤ β 1 α 2 ≤ α 1 . ( 2
∀α ∈ [a, α 1 ] ξ 1 (α) = v -1 (v(α) + m).
By definition, we have

∀α ∈ [a, α 1 ] ξ 1 (α) α φ(s)f (s) ds = v(ξ 1 (α)) -v(α) = m = b a ρ(s)f (s)
ξ 2 • ξ 1 : [a, α 1 ] ξ 1 ----→ [β 2 , b] ξ 2 ----→ [a, α 1 ]
is defined and continuous from [a, α 1 ] into itself and therefore admits a fixed point ᾱ. Thus, if we set β = ξ 1 (ᾱ) we have ᾱ = ξ 2 ( β). Equalities (2.23) and (2.25) with α, β replaced by ᾱ, β yield the conclusion.

b) let

ρ n = ρ + 1 n , φ n = φ + 2 n , f n = f + 1
n so that 0 < ρ n < φ n and f n > 0 a.e. and set g n = kf n so that the monotonicity of k implies that g n > 0 a.e. and f n , g n satisfy H. By a) there exist α n ,

β n such that b a ρ n (s)f n (s) ds = β n α n φ n (s)f n (s) ds; (2.27) b a ρ n (s)g n (s) ds = β n α n φ n (s)g n (s) ds. (2.28)
By compactness we may assume α n → α, β n → β. The conclusion follows by passing through the limit in (2.27) and (2.28).

ii) Uniqueness. Assume that 0 < ρ < φ, f > 0, g > 0 are continuous and that, for instance, k is decreasing. By i)a) the points α such that there exists β satisfying (2.11) and (2.12) are the fixed points of the composed map ξ 2 • ξ 1 . By definition the functions ξ 1 , ξ 2 are differentiable and we have

∀α ∈ [a, α 1 ] ξ 1 (α) = v (α) v (ξ 1 (α)) = φ(α)f (α) φ(ξ 1 (α))f (ξ 1 (α)) ; ∀β ∈ [β 2 , b] ξ 2 (β) = φ(β)g(β) φ(ξ 2 (β))g(ξ 2 (β))
.

In order to prove the claim we notice that if α satisfies

ξ 2 • ξ 1 (α) = α then (ξ 2 • ξ 1 ) (α) = ξ 2 (ξ 1 (α))ξ 1 (α) = k(ξ 1 (α)) k(α) .
(2.29) By (2.23) we have ξ 1 (α) > α so that the strict monotonicity of k implies k(ξ 1 (α)) < k(α) and thus (ξ

2 • ξ 1 ) (α) < 1 whenever ξ 2 • ξ 1 (α) = α. Let S = {α ∈ [a, b] : ξ 2 • ξ 1 (α) = α}.
Clearly, S is compact and non-empty by i); moreover, taking (2.29) into account, for each α ∈ S there exists η such that

∀t ∈]α -η, α[ ξ 2 • ξ 1 (t) > t ∀t ∈]α, α + η[ ξ 2 • ξ 1 (t) < t.
(2.30)

As a consequence, the set S has no accumulation points and is therefore finite. Let α 1 = min S and assume S = {α 1 }; let α 2 = min S \ {α 1 }. Then by (2.30) there exist

t 1 < t 2 ∈ [α 1 , α 2 ] such that ξ 2 • ξ 1 (t 1 ) < t 1 and ξ 2 • ξ 1 (t 2 ) > t 2 . Therefore there exists t ∈ [t 1 , t 2 ] such that ξ 2 • ξ 1 ( t ) = t, a contradiction.

Main Result

Theorem 3.1. Let x ∈ W 2,1 ([0, T ]) be a solution to (P). Then there exists a bang-bang solution y to (P) satisfying ∀t ∈ [0, T ] y(t) ≤ x(t).

Moreover there exists a set E which is a finite union of intervals such that

y + a 1 (t)y + a 0 (t)y = φ 1 (t)χ E (t) + φ 2 (t)χ [0,T ]\E (t) a.e.
Corollary 1. Under the above assumption, there exists a bang-bang solution y satisfying

∀t ∈ [0, T ] y(t) ≥ x(t).
Proof of Corollary 1. Let -Φ be defined by the equality (-Φ)(t) = -Φ(t). Clearly, x = -x solves x + a 1 (t)x + a 0 (t)x ∈ -Φ(t) a.e.

By Theorem 3.1 there exists a bang-bang solution ỹ satisfying the same boundary conditions as x and satisfying ∀t ∈ [0, T ] ỹ(t) ≤ x(t).

Then the function y defined by

∀t ∈ [0, T ] y(t) = -ỹ(t)
is a solution to our problem.

Proof of Theorem 3.1. Let h be the function defined in Proposition 2.1.

i) We show that it is not restrictive to assume

Φ(t) = [0, φ(t)] (φ ∈ L 1 ([0, T ]), φ > 0 a.e.
) and x 0 = v 0 = 0.

In fact, let Φ(t) = [φ 1 (t), φ 2 (t)] and x satisfy

x + a 1 (t)x + a 0 (t)x ∈ Φ(t) a.e.

Then the function x defined by

x(t) = x(t) -x (0)t -x(0) satisfies x(0) = x (0) = 0 and x + a 1 (t)x + a 0 (t)x ∈ [ψ 1 (t), ψ 2 (t)] a.e.
where

ψ 1 (t) = φ 1 (t) -a 0 (t)x (0)t -a 1 (t)x (0) -a 0 (t)x(0), ψ 2 (t) = φ 2 (t) -a 0 (t)x (0)t -a 1 (t)x (0) -a 0 (t)x(0).
Moreover, by Proposition 2.1, the function x defined by

x(t) = x(t) - t 0 h(t, s)ψ 1 (s) ds satisfies x(0) = 0, x (0) = 0 and x + a 1 (t)x + a 0 (t)x ∈ [0, ψ 2 (t) -ψ 1 (t)] a.e.
If we assume that Theorem 3.1 holds for such an interval and initial boundary conditions, there exists a function ȳ satisfying

ȳ(0) = x(0), ȳ (0) = x (0), ȳ(T ) = x(T ), ȳ (T ) = x (T ), ȳ + a 1 (t)ȳ + a 0 (t)ȳ ∈ {0, ψ 2 (t) -ψ 1 (t)} a.e., ∀t ∈ [0, T ] ȳ(t) ≤ x(t).
It is now easy to check that the function y defined by

y(t) = ȳ(t) + t 0 h(t, s)ψ 1 (s) ds + x (0)t + x(0)
is a solution to our problem.

ii) Assume first that δ of property (S) can be chosen in such a way that I δ = [0, T ]. In this case, if we set ρ = x + a 1 x + a 0 x then by Proposition 2.1 we can write

x(t) = t 0 h(t, s)ρ(s) ds, (3.1)
where h satisfies property S 1) and in addition:

∀s, t ∈ [0, T ] h(t, s) > 0 if s < t, h(t, s) < 0 if t < s (3.2) ∀s, t ∈ [0, T ] ∂h ∂t (t, s) > 0, (3.3
) ∀t ∈ [0, T ] s → h(t, s)/ ∂h ∂t (t, s) is decreasing on [0, t]. (3.4)
In particular the functions f and g defined on [0, T ] by

g(s) = h(T, s) f (s) = ∂h ∂t (T, s)
verify hypothesis H with k(.) = h(T, .)/ ∂h ∂t (T, .). By Proposition 2.1, each bang-bang solution y such that x(0) = x (0) = 0 is given by the formula y(t) = t 0 h(t, s)ν(s) ds for some measurable function ν with values in {0, φ(t)}. We are thus led to show that there exists such a ν satisfying For this purpose, we use property S 1). Equalities (3.8) and (3.9) become

         w 1 (T ) T 0 z 1 (s)(ρ(s) -ν(s)) ds + w 2 (T ) T 0 z 2 (s)(ρ(s) -ν(s)) ds = 0 w 1 (T ) T 0 z 1 (s)(ρ(s) -ν(s)) ds + w 2 (T ) T 0 z 2 (s)(ρ(s) -ν(s)) ds = 0
The condition on the wronskian of w 1 , w 2 at T implies iii) In the general case, using property S and the compactness of [a, b], there exists a subdivision a 0 = 0 < a 1 < • • • < a l < T = a l+1 of [0, T ] such that, if we put I j = [a j , a j+1 ], we have • ∀s, t ∈ I j h(t, s) > 0 if s < t, h(t, s) < 0 if t < s ; • ∀s, t ∈ I j ∂h ∂t (t, s) > 0 ;

T 0 z 1 (s)(ρ(s) -ν(s)) ds = 0, (3.18) T 0 z 2 (s)(ρ(s) -ν(s)) ds = 0. ( 3
→ ρ, φ n → φ in L 1 ([0, T ]) (for instance ρ n = ρ + 1 n , φ n = φ + 2 n ). Corresponding to each n, there exist α n , β n ∈ [0, T ] such that, if we set ν n = φ n χ [α n ,β n ] then we have T 0 h(T, s)ρ n (s) ds = T 0 h(T, s)ν n (s) ds, (3.23)
• ∀t ∈ I j s → h(t, s)/ ∂h ∂t (t, s) is decreasing on I j . By ii), on each interval I j there exist α j , β j such that the solution y j to the problem y + a 1 (t)y + a 0 (t)y = φ 1 (t)χ [a j ,α j ]∪[β j ,b j ] (t) + φ 2 (t)χ [α j ,β j ] (t) a.e. on I j with the initial conditions y j (a j ) = x(a j ), y j (a j ) = x (a j ) satisfies the equalities y j (a j+1 ) = x(a j+1 ), y j (a j+1 ) = x (a j+1 ) and moreover y j (t) ≤ x(t) for each t ∈ I j . Clearly the function y ∈ W 2,1 ([0, T ]) obtained by glueing together the functions y j is a solution to our problem. The number δ depending only on the function h, it can happen that δ = +∞. This is the case when a 1 and a 0 are constant and the equation λ 2 + a 1 λ + a 0 = 0 admits two real roots λ 1 , λ 2 . In fact, under this assumption we have either h(t, s) = 1 λ 2 -λ 1 (e λ 2 (t-s) -e λ 1 (t-s) ) if λ 1 = λ 2 , or h(t, s) = (t -s)e λ(t-s) if λ 1 = λ 2 = λ.

Lemma 2 . 1 .

 21 Assume that f, g satisfy hypothesis H and let α, β ∈ [a, b] be such that b α φ(s)f (s) ds = If k is decreasing on [a, b], inequalities (2.13) and (2.14) are reversed. Moreover, inequalities (2.13)-(2.14) are strict if 0 < ρ < φ and f > 0, g > 0 a.e.

  for instance that k is decreasing on [a, b]. In this situation Lemma 2.1 yields

  f (s) ds is continuous and increasing with values in [0, v(b)]: let v -1 denote its inverse function. Set m to be m = b a ρ(s)f (s) ds. Since, by (2.18), v(b) = v(α 1 ) + m then v(α) + m ∈ [0, v(b)] if and only if a ≤ α ≤ α 1 ; this allows us to introduce the continuous function ξ 1 defined by the formula

4 )

 4 , s)ρ(s) ds = T 0 h(T, s)ν(s) ds, s)ρ(s) ds = T 0 ∂h ∂t (T, s)ν(s) ds (3.6) and for each t in [0, T ], 0 < ρ < φ a.e. By Proposition 2.2 there exist α, β ∈ [0, T ] such that s)φ(s). ds (3.9) It is clear that if we set ν(s) = φ(s)χ [α,β] (s) (3.10) then (3.5) and (3.6) are satisfied. In order to prove (3.7) we first show that under our assumptions on ρ and φ we have 0 < α < β < T. (3.11) 14Notice first that the equalities (α, β) = (0, T ) or α = β cannot hold otherwise by (3.8) ρ = φ or ρ = 0 a.e., a contradiction. Assume, for instance, α = 0 and β < T , the case α > 0 and β = T being similar. Under this assumption, equalities (3.8) and (3.9) become and the assumption 0 < ρ < φ a.

  s)ρ n (s) ds = T 0 ∂h ∂t (T, s)ν n (s) ds (3.24)and, for each t in [0, T ],t 0 h(t, s)ρ n (s) ds ≥ t 0 h(t, s)ν n (s) ds.(3.25)The interval [0, T ] being compact, we may assumeα n → α, β n → β for some α ≤ β ∈ [0, T ]. Clearly ν n = φ n χ [α n ,β n ] converges to φχ [α,β] in L 1 ([0, T ]),therefore if we pass through the limit in (3.23), (3.24), (3.25) and we set ν = φχ [α,β] we obtain (3.5), (3.6) and (3.7).

Remark 3 . 1 .Remark 3 . 2 .

 3132 The proof of Theorem 3.1, part ii)a) shows in fact that when 0 < ρ < φ, we have y(t) < x(t) on ]0, T [. With the notations introduced in Proposition 2.1, the proof of Theorem 3.1 (part ii)) shows that if T = δ then, given a solution x to (P), there exists a bang-bang solution y ≤ x satisfying y + a 1 (t)y + a 0 (t)y = min Φ(t) on [0, α] ∪ [β, T ], y + a 1 (t)y + a 0 (t)y = max Φ(t) on [α, β].

  ) and y (T ) = x (T ).Purpose of what follows is to show (3.7), i.e. that y(t) ≤ x(t) for each t. We consider the cases t ∈ [0, α], t ∈ [β, T ], t ∈ [α, β] separately. Inequality (3.7) is trivial if t ≤ α; in fact we have

					e. allow us to apply Lemma 2.1 from
	which we deduce	T	β
			h(T, s)ρ(s) ds <	h(T, s)φ(s) ds,
		0		0
	contradicting (3.12).
	Set y(t) =	t 0 h(t, s)ν(s) ds so that (3.8) and (3.9) become y(T ) = x(T y(t) = 0 ≤ t h(t, s)ρ(s) ds = x(t),
				0
	the inequality being strict for t ∈]0, α]. In particular
				y(α) < x(α).	(3.14)
	Assume t ∈ [β, T ].
	Since, taking (3.2) into account, h(t, s) ≤ 0 whenever s ≥ t, we have
			T		T
		∀t ≥ β	h(t, s)ρ(s) ds ≤ 0 =	h(t, s)ν(s) ds	(3.15)
			t		t
	or equivalently
		T	t	T	t
	∀t ≥ β	h(t, s)ρ(s) ds-	h(t, s)ρ(s) ds ≤	h(t, s)ν(s) ds-	h(t, s)ν(s) ds. (3.16)
	0		0	0		0
	Therefore, in order to prove that y(t) ≤ x(t) for t ∈ [β, T ] it is enough to show that
			T		T
		∀t ∈ [β, T ]	h(t, s)ρ(s) ds =	h(t, s)ν(s) ds.	(3.17)
			0		0

  For each s ∈ [0, t[ let f (s) = h( t, s), g(s) = ∂h ∂t ( t, s) and k = f /g so that by (3.2)-(3.4) the function k is increasing and f > 0, g > 0. If we replace (a, b) by (0, t), Lemma 2.1 together with (3.21) imply that ≤ ρ ≤ φ a.e. and let φ n , ρ n ∈ L 1 ([0, T ]) be such that 0 < ρ n < φ n a.e. and ρ n

	t α	∂h ∂t	( t, s)φ(s) ds >	0	t	∂h ∂t	( t, s)ρ(s) ds
	thus contradicting (3.22).
	b) Assume, in general, 0
				t→ t+	y(t) -x(t) t -t	≤ 0.
	It follows that
		t			t
		h( t, s)φ(s) ds =		h( t, s)ρ(s) ds,	(3.21)
	α			0
	t α	∂h ∂t	( t, s)φ(s) ds ≤	0	t	∂h ∂t	( t, s)ρ(s) ds.	(3.22)

.19) Multiplying

(3.18

) by w 1 (t),

(3.19

) by w 2 (t) and adding the two equations we obtain

T 0 (w 1 (t)z 1 (s) + w 2 (t)z 2 (s))ρ(s) ds = T 0 (w 1 (t)z 1 (s) + w 2 (t)z 2 (s))ν(s)

ds which, together with property S 1), gives (3.17). Moreover remark that since inequality (3.15) is strict for t = T , then y(β) < x(β). (3.20) At this stage, we only need to prove that (3.7) holds for t ∈ [α, β]. Assume by contradiction that there exists t ∈ [α, β] such that x(t) = y(t). Let t = sup{t ∈ [α, β] : x(t) = y(t)}. Then α < t < β and by the very definition of t, x( t ) = y( t ) so that y ( t ) -x ( t ) = lim

Applications

Our first application concerns the reachable set of bang-bang constrained solutions. Let c be an arbitrary function defined on [0, T ] and consider the reachable sets X c T and Y c T associated to (P ) defined by X c T = {(y(T ), y (T )) : y ≤ c, y + a 1 (t)y + a 0 (t)y ∈ Φ(t) a.e., (y(0), y (0

T is convex. Finally, we give an application to the calculus of variations.

x 0 , v 0 , x 1 , v 1 be 4 fixed real numbers. Then there exists a dense subset D of C(R) for the uniform convergence such that for g in D the problem minimize

admits at least one solution for every lower semicontinuous function h satisfying the growth condition h(u) ≥ cψ(|u|), ψ being l.s.c. and convex, lim r→+∞ ψ(r)/r = +∞.

Proof. With our theorem 3.1 and the preceding application, the proof is a direct adaptation of the proof given in [START_REF] Cellina | The existence question in the calculus of variations: a density result[END_REF].


Raphaël Cerf
email: raphael.cerf@math.u-psud.fr--mariconda@pdmat1.math.unipd.it

Raphaël Cerf -

Carlo Mariconda

CHEBYSHEV MEASURES

Keywords: 1991 Mathematics Subject Classification. 41A50, 46G10, 52A20 oriented measure, vector measure, Lyapunov, Chebyshev, T -system

come

Chebyshev measures

Introduction

We are concerned with the problem of representing the values of a vector measure through its restriction to a nice family of sets. This problem has been handled for a vector measure defined on an interval and admitting a continuous density function forming a Chebyshev system (a function f : [START_REF] Karlin -W | Tchebycheff systems: with applications in analysis and statistics, Pure and applied mathematics[END_REF][START_REF] Kreȋn -A | The Markov moment problems and extremal problems[END_REF]. In this case, to each interior point of the range correspond exactly two dual canonical finite unions of intervals. The proof relies on geometrical considerations and on the fact that a linear combination of the components of a n-dimensional vector function which is a T -system has at most n zeroes. T -systems have been traditionally applied to approximation theory and to moment problems in statistics [START_REF] Karlin -W | Tchebycheff systems: with applications in analysis and statistics, Pure and applied mathematics[END_REF][START_REF] Kreȋn -A | The Markov moment problems and extremal problems[END_REF]; here we consider them from the point of view of Measure Theory. In dealing with Lyapunov theorem on the range of vector measures and a bang-bang control problem [START_REF] Cerf | On bang-bang constrained solutions of a control system[END_REF][START_REF] Cerf | Oriented measures with continuous densities and the bang-bang principle[END_REF], we were led incidentally to prove a weaker version of the aforementioned theorem. We thank warmly Fabrice Gamboa for introducing us to the field of Chebyshev systems, especially because their relationship with Lyapunov theorem does not appear at all in control theory literature. Our proofs differed strongly from the previous ones. In the case of continuous densities [START_REF] Cerf | Oriented measures with continuous densities and the bang-bang principle[END_REF], they were based on the differentiability of the measure and on a global inversion argument. We generalized the result to unnecessarily absolutely continuous measures, but still with n determinant conditions (oriented measures) [START_REF] Cerf | Oriented measures[END_REF] which allowed us to prove inductively the representation theorem with the help of an elementary topological argument. The knowledge of the previous works on T -systems suggested us that our result should hold with only one determinant condition. Here we introduce Chebyshev measures: they form a broad class of vector measures (unnecessarily defined on an interval) admitting a representation property through canonical sets and whose range is strictly convex. Our new argument is direct and uses the invariance domain theorem.

[0, 1] → R n is a T -system if det[f (x 1 ), • • • , f (x n )] > 0 when x 1 < • • • < x n )

General framework

Throughout the paper, we deal with the following objects: • a measurable space (X, A), • a non-trivial positive measure ν defined on A, • a vector measure µ

= (µ 1 , • • • , µ n ) defined on A with values in R n , • an increasing family of measurable sets (M i ) i∈[0,1] such that M 0 = ∅, M 1 = X. We suppose that the M i 's are distinct modulo ν i.e. ∀i, j ∈ [0, 1] i < j =⇒ ν(M i ) < ν(M j ).
The total variation |µ| is the scalar measure

|µ| = |µ 1 | + • • • + |µ n |
where the |µ i | are the usual total variations of the scalar measures µ i . We make the following assumption.

Assumption. The measures ν and µ are non-atomic with respect to the family (M i ) i.e.

∀E ∈ A ν(E) = 0 =⇒ ∃ i ∈[0, 1] 0 < ν(E ∩ M i ) < ν(E), ∀E ∈ A |µ|(E) = 0 =⇒ ∃ i ∈[0, 1] 0 < |µ|(E ∩ M i ) < |µ|(E).
Remark. This assumption guarantees that the maps i → ν(M i ) and i → µ(M i ) are continuous. Moreover the measures ν and µ are non-atomic.

Example 2.1. (linear intervals) This general framework stems from the case where X is the interval [0, 1] of R, A is the Lebesgue σ-field, ν is the Lebesgue measure, the M i 's are the intervals [0, i] and µ is a non-atomic vector measure on [0, 1]. In this situation, the previous assumption on µ turns out to be equivalent to the non-atomicity of µ.

Example 2.2. (circular annulus) Let X = B m be the unit ball of R m equipped with the Lebesgue measure (ν, A). We take M i to be the ball of radius i. Finally let µ be any vector measure which is absolutely continuous with respect to ν. The assumption on µ is here equivalent to the fact that the spheres have a zero |µ|-measure.

Chebyshev measures

We denote by S n the symmetric group of order n and, for σ in S n , by (σ) its sign. To the vector measure µ we associate a determinant measure det µ.

Definition 3.1. (determinant measure)

The measure det µ is the measure defined on the product space (X n , A ⊗n ) by

det µ = σ∈S n (σ) µ σ(1) ⊗ • • • ⊗ µ σ(n) .

This is the only measure whose restrictions to the product sets

A 1 × • • • × A n satisfy det µ(A 1 × • • • × A n ) = det[µ(A 1 ), • • • , µ(A n )].
The definition of a Chebyshev measure will involve the following subset of X n :

P = 0≤i 1 ≤•••≤i n-1 ≤1 M i 1 × (M i 2 \ M i 1 ) × • • • × (M i n-1 \ M i n-2 ) × (X \ M i n-1 ).
Obviously P belongs to the product σ-field A ⊗n .

Examples. In the case of the linear intervals (example 2.1) we have

P = { (x 1 , • • • , x n ) ∈ [0, 1] n : 0 ≤ x 1 ≤ • • • ≤ x n ≤ 1 }.
In the case of the circular annulus (example 2.2) we have

P = { (x 1 , • • • , x n ) ∈ (B m ) n : 0 ≤ |x 1 | ≤ • • • ≤ |x n | ≤ 1 }. Definition 3.2. (Chebyshev measure)
The vector measure µ is a T ν -measure if the measure det µ satisfies

∀A ∈ A ⊗n , A ⊂ P, ν ⊗n (A) > 0 =⇒ det µ(A) > 0.
The symbol T ν stands for Chebyshev measure.

Remark. Any non-atomic positive scalar measure µ is a Chebyshev measure with respect to itself. In fact, Lyapunov theorem yields the existence of an increasing family (M i ) such that µ(M i ) = iµ(X) for i in [0, 1]. Using the Hahn decomposition, any non-atomic scalar signed measure is the difference of two Chebyshev measures with respect to its total variation.

If µ is absolutely continuous with respect to ν, this definition might be translated in terms of the density function.

Definition 3.3. Let f = (f 1 , • • • , f n ) be a measurable vector-valued function defined on X. We say that f = (f 1 , • • • , f n ) is a T ν -system if the determinant det[f (x 1 ), • • • , f (x n )] is positive for ν ⊗n almost all (x 1 , • • • , x n ) in P .
This definition is a slight generalization of the classical one which deals only with functions defined on an interval. Theorem 3.4. Suppose µ is absolutely continuous with respect to ν.

Let f = (f 1 , • • • , f n ) be its density function. Then µ is a T ν -measure if and only if f is a T ν -system.
Proof. Remark first that for any measurable set A of X n we have

det µ(A) = A σ∈S n (σ) f σ(1) (x 1 ) • • • f σ(n) (x n ) dν ⊗n (x 1 , • • • , x n ) = A det[f (x 1 ), • • • , f (x n )] dν ⊗n (x 1 , • • • , x n ).
Suppose that f is a T ν -system. Let A be a measurable subset of P of positive ν ⊗n measure. The domain of integration has a positive measure and the integrand is positive ν ⊗n almost everywhere on this domain. It follows that det µ(A) is positive. Conversely, assume that µ is T ν -measure and set

A = { (x 1 , • • • , x n ) ∈ P : det[f (x 1 ), • • • , f (x n )] ≤ 0 }. Clearly A det[f (x 1 ), • • • , f (x n )] dν ⊗n (x 1 , • • • , x n ) ≤ 0. Assume that ν ⊗n (A) > 0.
By the very definition of a T ν -measure, we have det µ(A) > 0. However the initial formula yields

det µ(A) = A det[f (x 1 ), • • • , f (x n )] dν ⊗n (x 1 , • • • , x n ) ≤ 0 , which is absurd. Thus ν ⊗n (A) = 0.
There is a huge literature concerning Chebyshev systems of continuous functions defined on an interval. They were originally introduced in interpolation theory. Their general properties (in the case of continuous functions) have been thoroughly studied [START_REF] Karlin -W | Tchebycheff systems: with applications in analysis and statistics, Pure and applied mathematics[END_REF][START_REF] Kreȋn -A | The Markov moment problems and extremal problems[END_REF].

Example 3.5. (circular annulus) Let f = (f 1 , • • • , f n ) : [0, 1] → R n
be a T -system with respect to the Lebesgue measure on [0, 1] and the family of intervals [0, i]. Then the function g(x) = f (|x|) defined on the unit ball B m is a T -system with respect to the elements defined in example 2.2.

Fundamental properties

Notation. For a k-tuple of measurable sets

A 1 , • • • , A k by A 1 < • • • < A k
we mean that the A i 's are non negligible for ν and that there exists

i 0 < • • • < i k such that A 1 ⊂ M i 1 \ M i 0 , • • • , A k ⊂ M i k \ M i k-1 .
The non-atomicity assumption on ν implies the following result. Proposition 4.1. For each non-negligible set E and for each integer m there exist measurable sets

E 1 , • • • , E m such that E = E 1 ∪ • • • ∪ E m and E 1 < • • • < E m .
In particular P is not ν ⊗n negligible.

Proof. Let E be a set of positive ν measure. The map i ∈ [0, 1] → ν(M i ∩ E) being continuous and increasing, there exist 0

< i 1 < • • • < i m-1 ≤ 1 such that ν(M i l ∩ E) = (l/m) ν(E) for l in {1 • • • m -1}. Then the sets E l = (M i l \ M i l-1 ) ∩ E for l ∈ {1 • • • m -1}, E m = E\M i m-1
, satisfy the required conditions. Applying this result to E = X and m = n, we obtain a subset of P of positive ν ⊗n measure.

If ρ is a measurable function on X, its support is the set supp ρ = { x : ρ(x) = 0 }. If ρ belongs to L 1 µ (X), by µ(ρ) we denote the column vector

µ(ρ) = X ρ dµ = t X ρ dµ 1 , • • • , X ρ dµ n .
A direct consequence of the definitions is that if

A 1 < • • • < A n then the determinant det[µ(A 1 ), • • • , µ(A n )] is positive.
A more important fact concerning T ν -measures is that this characteristic property carries on from sets to positive functions.

Theorem 4.2. Suppose µ is a T ν -measure. If ρ 1 , • • • , ρ n are n µ-integrable non-negative functions such that supp ρ 1 < • • • < supp ρ n then the determinant det[µ(ρ 1 ), • • • , µ(ρ n )] is positive.
Let us first state a preparatory lemma.

Lemma 4.6. (perturbation lemma) Suppose µ is a T ν -measure and let

A 0 < A 1 < • • • < A n be n + 1 measurable sets. Given a positive ε, there exist n + 1 real numbers λ 0 , • • • , λ n such that ∀l ∈ { 0, • • • , n } 0 < λ l < ε and n l=0 (-1) l λ l µ(A l ) = 0.
Proof. Consider the n × n linear system

λ 0 µ(A 0 ) -λ 1 µ(A 1 ) + • • • + (-1) n-1 λ n-1 µ(A n-1 ) = (-1) n-1 λ n µ(A n ).
where λ n is a parameter. The determinant of the system is

ω n = (-1) n(n-1) 2 det [µ(A 0 ), • • • , µ(A n-1 )]. Since µ is a T ν -measure, ω n is not zero. For each i in { 0, • • • , n -1 }, let ω i be µ 1 (A 0 ) • • • (-1) i-2 µ 1 (A i-2 ) (-1) n-1 µ 1 (A n ) (-1) i µ 1 (A i ) • • • (-1) n-1 µ 1 (A n-1 ) µ 2 (A 0 ) • • • (-1) i-2 µ 2 (A i-2 ) (-1) n-1 µ 2 (A n ) (-1) i µ 2 (A i ) • • • (-1) n-1 µ 2 (A n-1 ) . . . . . . . . . . . . . . . . . . . . . µ n (A 0 ) • • • (-1) i-2 µ n (A i-2 ) (-1) n-1 µ n (A n ) (-1) i µ n (A i ) • • • (-1) n-1 µ n (A n-1 ) i.e. ω i = (-1) n(n-1) 2 det [µ(A 0 ), • • • , µ(A i-2 ), µ(A i ), • • • , µ(A n )].
By Cramer formula, λ i equals λ n ω i /ω n . The measure µ being is a T ν -measure, ω i and ω n have the same sign so that λ i is positive whenever λ n is positive. Choosing λ n such that 0 < λ n < min(εω n /ω 0 , • • • , εω n /ω n-1 , ε) we obtain an (n + 1)-tuple which solves the problem.

The representation theorem

We are about to state the main result which allows us to represent the values of a T ν -measure through canonical sets, that we define now.

Notation. (canonical sets) The set Γ is the subset of [0, 1] n defined by

Γ = { (γ 1 , • • • , γ n ) ∈ R n : 0 ≤ γ 1 ≤ • • • ≤ γ n ≤ 1 }. The interior of Γ is int Γ = { (γ 1 , • • • , γ n ) ∈ R n : 0 < γ 1 < • • • < γ n < 1 }. For γ = (γ 1 , • • • , γ n ) in Γ, we use the convention γ 0 = 0, γ n+1 = 1. For each γ = (γ 1 , • • • , γ n ) in Γ, we set E γ = 0≤i≤n i odd M γ i+1 \ M γ i .
Theorem 5.1 below was obtained in [START_REF] Cerf | Oriented measures[END_REF][START_REF] Karlin -W | Tchebycheff systems: with applications in analysis and statistics, Pure and applied mathematics[END_REF] in the case where µ is defined on [0, 1] and ν is the Lebesgue measure under some stronger assumptions: in [START_REF] Karlin -W | Tchebycheff systems: with applications in analysis and statistics, Pure and applied mathematics[END_REF], for classical T -systems, µ is assumed to have a continuous density with respect to ν whereas in [START_REF] Cerf | Oriented measures[END_REF] µ satisfies n determinant conditions (instead of one).

Theorem 5.1. (representation theorem) Suppose µ is a T ν -measure and let ρ be a measurable function such that 0 < ρ < 1 ν-a.e. There exist unique α and β in Γ satisfying

µ(E α ) = X ρ dµ = µ(X \ E β ).
Moreover these α and β belong to the interior of Γ.

Remark. The set X \ E β is dual to the set E β . In fact

X \ E β = 0≤i≤n i even M β i+1 \ M β i .
Proof of theorem 5.1. Assume that the claim concerning the existence and uniqueness of the set E α has been proved. We apply it to the function 1 -ρ. This yields a set E β such that µ(E β ) = µ(1 -ρ), which may be rewritten as µ(X \ E β ) = µ(ρ). We will thus only deal with the sets of the form E α .

Strict inequalities. Let α be a point of Γ such that µ(E α ) = µ(ρ). We show that α belongs to the interior of Γ. We rewrite µ(E α ) = µ(ρ) as

0≤i≤n i odd M α i+1 \M α i (1 -ρ) dµ - 0≤i≤n i even M α i+1 \M α i ρ dµ = 0. If we set λ i = (-1) i+1 , ρ i = ρχ M α i+1 \M α i if i is odd (1 -ρ)χ M α i+1 \M α i if i is even the equation becomes λ 0 X ρ 0 dµ + • • • + λ n X ρ n dµ = 0. Let I = { i : 0 ≤ i ≤ n, α i < α i+1 }; remark that for i in I the function ρ i is strictly positive on M α i+1 \ M α i .
Assume that the n-tuple α does not belong to the interior of Γ. Then |I| ≤ n; if we write Assume for instance that δ 1 ≤ γ 1 ; then E δ ∩ M δ 1 = E γ ∩ M δ 1 so that the equality µ(E δ ) = µ(E γ ) becomes

I = { i 1 , • • • , i p }, where i 1 < • • • < i p , we have 1 ≤ p ≤ n, p j=1 λ i j X ρ i j dµ = 0, supp ρ i 1 < • • • < supp ρ i p , λ i j ∈ {-1, 1}.
X\M δ 1 (χ E δ -χ E γ ) dµ = 0.
The sets (M δ i+1 \M δ i ) 1≤i≤n cover X \M δ 1 ; moreover on M δ i+1 \M δ i we recall that χ E δ = 1 if i is odd and χ E δ = 0 if i is even. The above equality then yields

0≤i≤n i odd M δ i+1 \M δ i (1 -χ E γ ) dµ - 2≤i≤n i even M δ i+1 \M δ i χ E γ dµ = 0
which may be rewritten Now each ρ i is non-negative. If δ = γ there exists j such that ρ j is positive on a nonnegligible set. By corollary 4.5, µ(ρ j ) is non-zero so that the set J = { i : µ(ρ i ) = 0 } is not empty. Writing J = { i 1 , • • • , i p }, where i 1 < • • • < i p , we have

1 ≤ p ≤ n, p k=1 λ i k X ρ i k dµ = 0, supp ρ i 1 < • • • < supp ρ i p , λ i k ∈ {-1, 1}.

Corollary 4 .

 4 4 yields a contradiction. It follows that 0< α 1 < • • • < α n < 1. Uniqueness. Let δ = (δ 1 , • • • , δ n ) and γ = (γ 1 , • • • , γ n ) be two elements of Γ such that µ(E δ ) = µ(ρ) = µ(E γ ). The first part of the proof (strict inequalities) shows that 0 < δ 1 < • • • < δ n < 1 and 0 < γ 1 < • • • < γ n < 1.

ρ

  i dµ = 0 whereλ i = (-1) i+1 , ρ i = |χ E δ -χ E γ |χ M δ i+1 \M δ i .

Corollary 4 .

 4 4 yields a contradiction. It follows that δ = γ.

The second author (C.M.) was supported by a Grant of the Consiglio Nazionale delle Ricerche (Grant 203.01.62).

Lemma 4.3. Let ρ 1 , • • • , ρ n be n µ-integrable functions. Then

Proof of the lemma. The identity is obviously true whenever ρ 1 , • • • , ρ n are characteristic functions. The monotone class theorem yields the result. Another scheme of proof is to develop the determinant and to transform each product of integrals into an n-dimensional integral with respect to a judicious product measure.

Proof of theorem 4.2. We apply the lemma. The domain of integration of the n-fold integral is reduced to supp ρ 1 × • • • × supp ρ n on which the determinant measure det µ is positive (by the definition of a T ν -measure). Hence the n-fold integral is positive.

we have n k=1 λk µ(ρ k ) = 0. Moreover supp ρ1 < • • • < supp ρn ; we are thus led to the previous case and the conclusion follows.

Funny corollary 4.5. Suppose µ is a T ν -measure and let ρ be a non-negative µintegrable function whose support is not negligible. Then µ(ρ) is non-zero. In particular, µ(E) is non-zero whenever ν(E) is non-zero.

Proof. We apply corollary 4.4 with p = 1, λ 1 = 1.

Remark. This assertion sounds trivial; however the point is that µ is a vector measure whose components are scalar signed measures. This makes life more difficult. Instead, in the case of oriented measures, this fact is a direct consequence of the definition (since µ 1 is then positive). A consequence of the funny corollary is that if µ is a T ν -measure, then ν is absolutely continuous with respect to the total variation of µ! Existence. Let θ : Γ → R n be the map defined by θ(α) = µ(E α ). The non-atomicity of µ with respect to the M i 's implies that this map is continuous. Moreover the second part of the proof (uniqueness) shows that the map θ is injective on int Γ. The invariance domain theorem [START_REF] Lloyd | Degree theory[END_REF]

By construction we have 0 < ρ < 1 and µ(ρ) = θ(α) so that θ(α) belongs to C. Now the second part of the proof (uniqueness) shows that θ(Γ) Γ) is open and closed in C. Thus it coincides with the whole set C.

Remark. The map θ was first introduced in [START_REF] Cerf | Oriented measures with continuous densities and the bang-bang principle[END_REF] to prove theorem 5.1 under the stronger assumptions that µ is defined on [0, 1] and admits a continuous density with respect to the Lebesgue measure. In [START_REF] Cerf | Oriented measures with continuous densities and the bang-bang principle[END_REF] however θ is differentiable and a local homeomorphism: Caccioppoli's global inversion theorem yields the injectivity of θ on int Γ and the fact that θ(int Γ) is open; instead here we first prove directly the injectivity of θ (without being differentiable) and then we apply the open mapping theorem.

A simple classical approximation argument yields the following corollary.

Corollary 5.2. Suppose µ is a T ν -measure. Let ρ be a measurable function such that 0 ≤ ρ ≤ 1. There exist α and β in Γ satisfying

We denote by R the range of µ i.e. R = { µ(E) : E ∈ A }.

Remark. The proof of Theorem 5.1 shows that θ(int Γ) is open and convex; by Corollary 5.2 its closure coincides with R. Then by [7, Th. 6.3] we obtain that int R = θ(int Γ). 10

Corollary 5.3. Suppose µ is a T ν -measure. Let ρ be a measurable function such that 0 ≤ ρ ≤ 1 and 0 < ρ < 1 on a ν-non negligible set. Then µ(ρ) belongs to the interior of R; in particular there exist unique α and β in the interior of Γ satisfying

Proof. There exist a ν-non negligible set F and ε > 0 such that ε ≤ ρ ≤ 1 -ε on F . The non-atomicity assumption yields the existence of 0 < δ 1 < • • • < δ n < 1 = δ n+1 such that if for every i we set

The following results have been stated in a less general context in [START_REF] Cerf | Oriented measures[END_REF] but they are still valid in the present framework; Chebyshev measures provide a broad class of measures whose range is strictly convex.

Theorem 5.3. The range R of a T ν -measure is strictly convex. The boundary points of R admit a unique representation modulo µ. Moreover a point µ(E) belongs to the boundary of R if and only if there exists γ in the boundary of Γ such that µ(E∆E γ ) = 0.

Finally, we remark that the same results would hold under a weaker assumption on the measure. Namely, it is enough that for each n-tuple of measurable sets A 1 , • • • , A n such that A 1 < • • • < A n , the determinant det[µ(A 1 ), • • • , µ(A n )] is positive. The delicate point concerns theorem 4.2 which is the key for proving the representation theorem. In this situation, the proof should be done along the lines of theorem 2.2 of [START_REF] Cerf | Oriented measures[END_REF].


Stefano Bianchini

Raphaël Cerf

Carlo Mariconda

Two Dimensional Zonoids And Chebyshev Measures

Keywords: 1991 Mathematics Subject Classification. 46G10, 52A10, 26A51, 41A50 Chebyshev measure, zonoid, Lyapunov, range

come

(bianchin@sissa.it) ( * * ) CNRS, Université de Paris Sud, Mathématique, bât. 425, 91405 Orsay Cedex, France (Raphael.Cerf@math.u-psud.fr) ( * * * ) Università di Padova, Dipartimento di Matematica Pura e Applicata, via Belzoni 7, 35100 Padova, Italy (maricond@math.unipd.it) May 1996, March 1997 (revised version) Abstract. We give an alternative proof to the well known fact that each convex compact centrally symmetric subset of R 2 containing the origin is a zonoid i.e. the range of a two dimensional vector measure and we show that a two dimensional zonoid whose boundary contains the origin is strictly convex if and only if it is the range of a Chebyshev measure. We give a condition under which a two dimensional vector measure admits a decomposition as the difference of two Chebyshev measures, a necessary condition on the density function for the strict convexity of the range of a measure and a characterization of two dimensional Chebyshev measures.

Introduction

A well known Theorem of Lyapunov [START_REF] Liapounoff | Sur les fonctions vecteurs complètement additives[END_REF][START_REF] Rudin | Functional Analysis[END_REF] states that the range of a non-atomic vector measure is compact and convex. Conversely (e.g. [START_REF] Bolker | A class of convex bodies[END_REF]) each compact convex centrally symmetric subset of R 2 containing the origin is the range of a two dimensional measure (such a set is called a zonoid). Some problems related to the bang-bang principle in control theory led us to work with the class of the Chebyshev measures. Our definition of a Chebyshev measure is essentially a linear independence condition on some vectors of its range. In [START_REF] Cerf | Oriented measures[END_REF][START_REF] Cerf | Chebyshev measures[END_REF] we proved that the range of a n-dimensional Chebyshev measure is strictly convex and its boundary contains the origin. Recently Schneider showed in [START_REF] Schneider | Measures in convex geometry[END_REF] that the range of a n-dimensional measure is strictly convex if and only if for every set A with µ(A) = 0 there exist n measurable subsets A 1 , . . . , A n of A such that µ(A 1 ), . . . , µ(A n ) are linearly independent. A result by Neyman [START_REF] Neyman | Decomposition of ranges of vector measures[END_REF] states that if the origin is an extreme point of the boundary of a zonoid Z and µ is a vector measure such that R(µ) = Z then Z determines the m-range of µ i.e. the set of m-uples (µ(A 1 ), . . . , µ(A m )) where A 1 , . . . , A m are a measurable partition of the space. A n-dimensional strictly convex zonoid whose boundary contains the origin is then naturally expected to be the range of a Chebyshev measure.

Here we prove that a strictly convex, centrally symmetric, compact subset of R 2 whose boundary contains the origin is actually the range of a two dimensional Chebyshev measure. We give two different proofs: the first one involves the representation theorem for Chebyshev measures proved in [START_REF] Cerf | Chebyshev measures[END_REF]; the second one is based on a new simple representation result for convex sets in R 2 . Our technique allows also, given an arbitrary convex centrally symmetric compact set, to build explicitly a measure whose range coincides with it. The method of defining the measure through its density with respect to a reference measure was used in [START_REF] Candeloro | Geometric properties of the range of two-dimensional quasi-measures with respect to the Radon-Nikodym property[END_REF] where the authors characterize the range of a couple of positive (quasi-) measures. Moreover, we give a condition under which a two dimensional vector measure admits a decomposition as the difference of two Chebyshev measures. Further, for two dimensional measures, we state a necessary condition on the density function of µ with respect to its total variation for the strict convexity of the range R(µ) of µ; as an application we show that µ is a Chebyshev measure on [0, 1] if and only if the map θ defined by θ(α, β) = µ([α, β]) for 0 < α < β < 1 is a homeomorphism onto int R(µ).

Notation and preliminary results

Let µ = (µ 1 , µ 2 ) be a two dimensional vector measure defined on the interval [0, 1] equipped with a σ-field M and |µ| be its total variation. The determinant measure det µ associated to µ is the two dimensional measure on [0, 1] 2 defined by

det µ = µ 1 ⊗ µ 2 -µ 2 ⊗ µ 1 ; we point out that if A, B are measurable then det µ(A × B) = det(µ(A), µ(B)).
We assume that M contains the Borelians and we set Γ = {(x, y) ∈ R 2 : 0 ≤ x ≤ y ≤ 1}. Definition 1. The measure µ is a Chebyshev measure (or simply T-measure) with respect to the intervals ([0, α]) 0≤α≤1 if it is non-atomic and each |µ| ⊗ |µ|-non negligible measurable subset of Γ has a positive (or negative) det µ measure.

Remark.

In what follows we will always assume det µ to be positive whenever µ is a Chebyshev measure; its properties do not change in the other case. In particular if µ is a Chebyshev measure and A, B are |µ| -non negligible subsets of [0, 1] such that sup A ≤ inf B then det(µ(A), µ(B)) > 0.

For Φ being an endomorphism of R 2 and µ a two dimensional measure on [0, 1] we define the two dimensional measure Φµ by Φµ(A) = Φ(µ(A)) for every measurable A ⊂ [0, 1]. The next proposition is a straightforward consequence of the definitions.

Proposition 1. Let µ be a T-measure and Φ be a rotation; then Φµ is a T-measure.

Definition 2. A function f in L 1 ν ([0, 1], R 2
) is a Chebyshev system (or simply T-system) with respect to a prescribed measure ν whenever the determinant det(f (t 1 ), f (t 2 )) is positive for ν ⊗ ν-almost every (t 1 , t 2 ) in Γ.

Proposition 2. [6, Th. 3.4] A measure µ is a Chebyshev measure if and only if the density of µ with respect to its total variation is a T-system.

For µ = (µ 1 , µ 2 ) being a two dimensional measure on [0, 1] we denote by R(µ) the range of µ defined by R(µ) = {µ(E) = (µ 1 (E), µ 2 (E)) : E ∈ M} and by θ : Γ → R(µ) the map defined by θ(α, β) = µ([α, β]) for every (α, β) in Γ.
We denote by int A the interior of a set A, by cl A its closure, by ∂A its boundary and by co A its convex hull; for L being a convex set in R n we denote by ri L its relative interior. We refer to [START_REF] Rockafellar | Convex Analysis[END_REF] for the definitions of these sets. The peculiar properties of a Chebyshev measure rely on the following result.

Theorem 1. [6] Let µ be a Chebyshev measure on [0, 1]. Then the restriction of θ to int Γ induces a homeomorphism onto int R(µ); in particular R(µ) = {µ([α, β]) : 0 ≤ α ≤ β ≤ 1} and ∂R(µ) = {µ([0, α]) : 0 ≤ α ≤ 1} ∪ {µ([β, 1]) : 0 ≤ β ≤ 1}.

A characterization of planar strictly convex zonoids

Theorem 2. Let K be a subset of R 2 . We have the following equivalence: i) the set K is strictly convex, compact, centrally symmetric and (0, 0) ∈ ∂K; ii) there exists a two-dimensional Chebyshev measure µ such that K = R(µ).

Proof. Assume that i) holds. Let Φ be a rotation such that Φ(K) ⊂ {(x, y) ∈ R 2 : x ≥ 0}; let for simplicity [0, 1] be the projection of Φ(K) on the x-axis. For each x in [0, 1] let

y(x) = inf{y ∈ R : (x, y) ∈ Φ(K)}. Clearly p = 1 2 (1, y(1)
) is the center of Φ(K) and the boundary of Φ(K) is the union of the graph of y and its symmetric with respect to p. Since y is strictly convex and y(0) = 0 there exists a strictly increasing function g such that

∀x ∈ [0, 1] y(x) = x 0 g(t) dt.
Let µ be the two dimensional vector measure on [0, 1] whose density function with respect to the Lebesgue measure is f (t) = (1, g(t)). Since g is strictly increasing, f is a T-system with respect to the Lebesgue measure: Proposition 2 then implies that µ is a T-measure. By Theorem 1 the boundary points of the range of µ are exactly the points µ([0, x]) where x varies in [0, 1] together with their symmetric with respect to 1 2 µ([0, 1]). By the definition of µ we have µ([0, x]) = (x, y(x)); it follows that the boundaries of R(µ) and of Φ(K) coincide: these sets being convex and closed we obtain R(µ) = Φ(K) so that K = R(Φ -1 µ). By Proposition 1, Φ -1 µ is a T-measure, proving ii). The converse is a trivial consequence of the Lyapunov Theorem and of the results stated in [START_REF] Cerf | Oriented measures[END_REF][START_REF] Cerf | Chebyshev measures[END_REF].

Bidimensional zonoids

A point P of a convex set C is said to be exposed (see [START_REF] Rockafellar | Convex Analysis[END_REF]) if there exists an hyperplane whose intersection with C is reduced to P . It is well-known (Straszewicz-Klee Theorem, [START_REF] Klee | Extremal structure of convex sets[END_REF][START_REF] Straszewicz | Über exponierte Punkte abgeschlossener Punktmenge[END_REF]) that a compact subset of a normed space has at least an exposed point. Let C be a compact, convex, centrally symmetric subset of R 2 . We assume here that O is an exposed point of C and that Clearly y is convex, bounded and (thus) continuous on its domain and its graph coincides with

C ⊂ {(x, y) ∈ R 2 : x ≥ 0}, C ∩ {(0, y) : y ∈ R} = {O}. Let L > 0, M in R be such that (L/2, M/2)
∂ -C = ∂C ∩ {(x, y) ∈ R 2 : y ≤ M L x}. Let G : [0, L] → ∂ -C be the map defined by ∀x ∈ [0, L] : G(x) = (x, y(x)).
Remark that for x in [0, L] the symmetric point of G(L -x) with respect to I is the point (x, M -y(L -x)) of the boundary of C. It follows that

∀(x, y) ∈ [0, L] × R : (x, y) ∈ C ⇐⇒ y(x) ≤ y ≤ M -y(L -x). (•)
We will widely use the next representation result.

Proposition 3. The following identity holds:

C = {G(x 2 ) -G(x 1 ) : x 1 , x 2 ∈ [0, L], x 1 ≤ x 2 }. Proof. Let x 1 ≤ x 2 ; if x 1 = x 2 then O = G(x 1 ) -G(x 1 ) ∈ C.
Assume that x 1 < x 2 ; since 0 ≤ x 1 and x 2 -x 1 ≤ x 2 then by convexity we have

y(x 2 -x 1 ) x 2 -x 1 ≤ y(x 2 ) -y(x 1 ) x 2 -x 1 ; similarly since x 1 ≤ L -(x 2 -x 1 ) and x 2 ≤ L then y(x 2 ) -y(x 1 ) x 2 -x 1 ≤ y(L) -y(L -(x 2 -x 1 )) L -(L -(x 2 -x 1 )
) .

It follows that y(

x 2 -x 1 ) ≤ y(x 2 ) -y(x 1 ) ≤ M -y(L -(x 2 -x 1 )); thus by (•) the point (x 2 -x 1 , y(x 2 ) -y(x 1 )) = G(x 2 ) -G(x 1 ) belongs to C. Conversely let z = (a, b) ∈ C. Let ϕ : [0, L -a] → R
x 2 = x 1 + a we obtain y(x 2 ) = b + y(x 1 ) implying that G(x 2 ) = z + G(x 1 )
, which is the desired conclusion.

The construction in Theorem 2 suggests an alternative proof (and an improvement) to the well-known fact that C is the range of a measure (see [START_REF] Bolker | A class of convex bodies[END_REF]). For I, J being intervals in R we write that I < J if both I and J are not trivial and sup I ≤ inf J; we shall denote by λ the Lebesgue measure in R. Theorem 3. Let K be a non empty, compact, centrally symmetric, convex subset of R 2 containing the origin. Then there exists a non-atomic measure µ on the Borelians of [0, 1] such that K = R(µ) and for every x in K there exist α, β, γ, δ in [0, 1] such that x = µ([α, β]) -µ([γ, δ]). Moreover if the origin is an exposed point of K then

R(µ) = {µ([α, β]) : 0 ≤ α ≤ β ≤ 1}.
Proof. Let e be an exposed point of K; such a point exists by the Straszewicz-Klee Theorem. Then O is an exposed point of -e + K. Let T be a rotation such that

T (-e + K) ⊂ {(x, y) ∈ R 2 : x ≥ 0}, T (-e + K) ∩ {(0, y) : y ∈ R} = {O}
and let I = (L/2, M/2) be the center of T (-e + K); we will assume that L = 1 and set C = T (-e + K). Correspondingly let y and G be the functions defined above. By [12, Corollary 24.2.1] there exists an increasing function g : [0, 1] → R such that

∀x 1 , x 2 ∈ [0, 1] : y(x 2 ) -y(x 1 ) = x 2 x 1 g(t) dt.
Let ν be the measure whose density function with respect to the Lebesgue measure is (1, g). Proposition 3 then yields

C = {ν([x 1 , x 2 ]) : x 1 , x 2 ∈ [0, 1], x 1 ≤ x 2 } ( * )
so that, in particular, C ⊂ R(ν). To prove the opposite inclusion let

I 1 < • • • < I m be m disjoint non trivial open intervals and set V = I 1 ∪ • • • ∪ I m . Let 0 = x 0 < x 1 < • • • < x m ≤ 1 and 1 = y 0 > y 1 > • • • > y m ≥ 0
be such that, for i in {1, . . . , m}, the intervals

J i =]x i-1 , x i [ and L i =]y m-i+1
, y m-i [ are translates of I i , so that for each i there exist two positive real numbers a i and b i satisfying

I i = a i + J i and L i = b i + I i . Then J 1 < • • • < J m , L 1 < • • • < L m , x m = λ(V ), y m = 1 -x m .
The function g being increasing we obtain ∀i ∈ {1, . . . , m} :

J i g(t) dt ≤ J i g(a i + t) dt = I i g(t) dt ≤ I i g(b i + t) dt = L i g(t) dt
and thus

x m 0 g(t) dt = m i=1 J i g(t) dt ≤ V g(t) dt ≤ m i=1 L i g(t) dt = 1 y m g(t) dt.

Now by Proposition 3 we have

p = x m , x m 0 g(t) dt = G(x m )-G(0) ∈ C, q = x m , 1 y m g(t) dt = G(1)-G(y m ) ∈ C;
therefore by convexity we obtain

ν(V ) = x m , V g(t) dt ∈ co {p, q} ⊂ C.
Let A be a measurable subset of [0, 1]; the measure ν being regular there exists a G δ subset E such that ν(A) = ν(E). We may write

E = ∩ m V m where (V m ) m is
ν (B) = ν(B \ E) -ν(B ∩ E).
It is well known [1, Lemma 1.3] (and easy to check) that the range of ν is given by

R(ν ) = R(ν) -ν(E) so that R(ν ) = T K and therefore K = T -1 (R(ν )) = R(µ) where µ = T -1 ν . Now let A be a measurable subset of [0, 1]. Then µ(A) = T -1 ν(A \ E) -T -1 ν(A ∩ E);
( * ) and ( * * ) yield the conclusion.

Remark. A generalized version of the integral inequalities that we use to show that R(ν) is contained in C was stated in [START_REF] Cerf | On bang-bang constrained solutions of a control system[END_REF]; their proof in this less general context is simpler and it is given here for the convenience of the reader. The above arguments yield an alternative proof of Theorem 2.

Corollary. Let K be a non empty, compact, centrally symmetric, strictly convex subset of R 2 such that O belongs to ∂K. Then there exists a Chebyshev measure µ on the Borelians of [0, 1] such that K = R(µ).

Proof. Since K is strictly convex and O belongs to ∂K then O is exposed: with the notation of the proof of Theorem 3 we may take e = O and thus no translation is needed.

Then C = T (K) so that by ( * * ) we obtain K = R(T -1 ν) where ν is the measure whose density with respect to λ is the vector (1, g). Since the function y is strictly convex then g is strictly monotonic and therefore (1, g) is a T -system. Proposition 2 then shows that ν is a Chebyshev measure; Proposition 1 yields the result.

Remark. The main difference between the two proofs is that, in Theorem 3, the representation result for convex sets (Proposition 3) is used as a substitute of the representation Theorem 1 for Chebyshev measures.

Decomposition of measures

Let (X, M) be a measurable space and µ be a non-atomic positive measure on X. There exists a family (M i ) i∈[0,1] of sets of M such that µ is a Chebyshev measure with respect to µ and to (M i ) i∈[0,1] (we refer to [START_REF] Cerf | Chebyshev measures[END_REF] for the definition of T-measure in this more general setting). In fact Lyapunov Theorem on the range of measures yields the existence of an increasing family (M i ) i∈[0,1] such that µ(M i ) = iµ(X) for each i in [0, 1]. More generally, if µ is a signed measure on X, by the Hahn decomposition theorem we may decompose X into a disjoint union X -∪ X + such that if we set

µ + (•) = + ∩ •), µ -(•) = -µ(X -∩ •)
then µ = µ + -µ -and µ + , µ -are positive measures. The latter property together with the non-atomicity yield the existence of two increasing families (

M + i ) i∈[0,1] and (M - i ) i∈[0,1] such that µ + (resp. µ -) is a Chebyshev measure with respect to (M + i ) i∈[0,1] (resp. (M - i ) i∈[0,1]
). Thus µ is the difference of two Chebyshev measures. We give now a condition under which the same conclusion holds for two dimensional vector measures. For a vector v of R 2 \ {(0, 0)} we denote by arg v its principal argument in ] -π, π]. Let f be a measurable function with values in R 2 . Theorem 4. Let µ be a two dimensional non-atomic vector measure on (X, M) and let f = (f 1 , f 2 ) be its density function with respect to |µ|. If |µ|({x : arg f (x) = θ}) = 0 for each θ in ] -π, π] then there exist two T-measures µ + and µ -such that µ = µ + -µ -.

Proof. We define

X + = {x ∈ X : arg f (x) ≥ 0}, X -= {x ∈ X : arg f (x) < 0} and ∀i ∈ [0, 1] : M + i = {x ∈ X + : arg f (x) ≤ iπ}, M - i = {x ∈ X -: arg f (x) ≥ -iπ}. Let f + and f -be the functions f + = f 1 X + and f -= f 1 X -. Then f + (resp. f -) is a T-system on X + (resp. X -) with respect to |µ| and (M + i ) i∈[0,1] (resp. (M - i ) i∈[0,1]
). Then setting dµ + = f + d |µ| and dµ -= f -d |µ| we obtain a decomposition of µ as the difference of two Chebyshev measures.

Remark. Under the above assumptions Theorem 5.1 in [START_REF] Cerf | Chebyshev measures[END_REF] then implies that for every A in M there exist i 1 , i 2 , j 1 , j 2 in [0, 1] such that µ(A)

= µ + (M + i 2 \ M + i 1 ) -µ -(M - j 2 \ M - j 1
). This result looks similar to the one stated in Theorem 3; however here the measure µ is imposed whereas in Theorem 3, given a zonoid, the measure is built.

A characterization of two dimensional Chebyshev measures

Let µ be a two dimensional non-atomic vector measure on ([0, 1], M) and let f be its density with respect to the total variation |µ|. We denote by < u : u ∈ E > the vector subspace of R 2 spanned by the vectors u belonging to a set E and by "•" the usual scalar product in R 2 . The next result will be applied later and has an interest in itself.

Theorem 5. If R(µ) is strictly convex then the determinant det(f (x), f (y)) of the vectors f (x), f (y) is not zero |µ| ⊗ |µ|-a.e. on [0, 1] 2 . Proof. Let A, Z, A 1 be the sets defined by

A = {(x, y) : det(f (x), f (y)) = 0}, Z = {x : f (x) = 0} A 1 = {(x, y) : f (x) = 0, f (y) ∈< f (x) >}; clearly we have A = (Z × [0, 1]) ∪ A 1 and (Z × [0, 1]) ∩ A 1 = ∅. Let τ be the map defined by τ (a, b) = (-b, a); then A 1 = {(x, y) : f (x) = 0, f (y)•τ (f (x)) = 0} so that A 1 is measurable. Moreover Fubini's Theorem gives |µ| ⊗ |µ|(A 1 ) = [0,1]\Z D x d|µ|(y) d|µ|(x)
where, for x in [0, 1],

D x = {y : f (y) • τ (f (x)) = 0}. If |µ| ⊗ |µ|(A 1 ) = 0 there exists x in [0, 1] \ Z such that |µ|(D x ) = 0.
The very definition of D x implies that for every measurable subset B of D x we have

µ(B) • τ (f (x)) = B f (y) • τ (f (x)) d|µ|(y) = 0
and thus the vector space < µ(B) : B ∈ M, B ⊂ D x > is at most one dimensional: Theorem 3.1.2 in [START_REF] Schneider | Measures in convex geometry[END_REF] then implies that R(µ) is not strictly convex, a contradiction. Obviously

|µ|(Z) = 0; thus |µ| ⊗ |µ|(A) = |µ| ⊗ |µ|(Z × [0, 1]) + |µ| ⊗ |µ|(A 1 ) = 0, proving the claim.
We will use the following results. For the convenience of the reader, a proof of a more general result is given in the appendix.

Lemma 2. Let A, B be open bounded subsets of R n and ψ : cl A → R n be a continuous map inducing a homeomorphism from A onto B. Then ψ(∂A) = ∂B.

We recall that we denote by λ the Lebesgue measure on [0, 1]; in what follows we assume that there exists a strictly positive function h in L 1 λ ([0, 1]) such that d|µ| = h dλ; in particular |µ| is absolutely continuous with respect to λ. We prove here that Theorem 1 characterizes the Chebyshev measures. Theorem 6. Let θ be the map defined in §2. If θ induces a homeomorphism from int Γ onto int R(µ) then µ is a Chebyshev measure.

Proof. Remark first that int R(µ), being isomorphic to int Γ, is non-empty. Since Γ and R(µ) are convex and closed then Theorem 6.3 in [START_REF] Rockafellar | Convex Analysis[END_REF] yields Γ = cl (int Γ) and R(µ) = cl (int R(µ)): applying Lemma 2 with ψ = θ, A = int Γ, B = int R(µ) we obtain θ(∂Γ) = ∂R(µ); in particular

∂R(µ) = {µ([0, α]) : 0 ≤ α ≤ 1} ∪ {µ([β, 1]) : 0 ≤ β ≤ 1}.
Assume that the boundary of R(µ) contains a non trivial segment L; let (for instance) α in [0, 1] be such that x = µ([0, α]) belongs to the relative interior of L. By Lemma 1 there exists an open neighbourhood V of x such that V ∩ ∂R(µ) = V ∩ ri L. By continuity there exist α 1 , α 2 in ]0, 1[ such that α 1 < α < α

  Stefano Bianchini * -Raphaël Cerf * * -Carlo Mariconda * * * ( * ) S.I.S.S.A. (I.S.A.S.), Via Beirut 2/4, 34013 Trieste, Italy

  are the coordinates of the center I of C; clearly C is contained in [0, L] × R. Let y be the function defined by ∀x ∈ [0, L] : y(x) = min{y ∈ R : (x, y) ∈ C}.

  be the map defined by ∀x ∈ [0, L -a] : ϕ(x) = y(x + a) -y(x) -b. Clearly ϕ is continuous; moreover by (•) we have y(a) ≤ b ≤ M -y(L -a). Therefore ϕ(0) = y(a) -b ≤ 0 and ϕ(L -a) = M -y(L -a) -b ≥ 0: it follows that there exists x 1 such that ϕ(x 1 ) = 0. Then if we put

  a decreasing sequence of countable unions of disjoint open intervals. Since ν(E) = lim m ν(V m ) then the previous remarks and the closure of C imply that ν(A) = ν(E) is in C. It follows that C = R(ν) ( * * ) and therefore K = e + T -1 R(ν) = e + R(T -1 ν). If O is an exposed point of K we may take e = O, proving the claim. Otherwise since O ∈ T K there exists a set E such that ν(E) = -T e; let ν be the measure on the Borelians of [0, 1] defined by

Lemma 1 .

 1 Let A be a non-empty open convex bounded subset of R 2 and assume that ∂A contains a non trivial segment L. Then ri L is open in ∂A.

2

 2 and{µ([0, t]) : t ∈ [α 1 , α 2 ] } ⊂ V ; Lemma 2 then implies that µ([0, t]) ∈ V ∩ ri L for every t ∈]α 1 , α 2 [. Therefore, if p ∈ R 2 \ {O}, c ∈ R are such that L ⊂ {x ∈ R 2 : p • x = c} we have ∀t ∈]α 1 , α 2 [: p • µ([0, t]) = c.Let U be the open subset of int Γ defined byU = {(α, β) ∈ R 2 : α 1 < α < β < α 2 }.Our assumption implies that θ(U ) is an open subset of R 2 ; however we have∀(α, β) ∈ U p • θ(α, β) = p • µ([α, β]) = p • µ([0, β]) -p • µ([0, α]) = 0, a contradiction; it follows that R(µ) is strictly convex. Theorem 5 then implies that det(f (α), f (β)) = 0 |µ| ⊗ |µ|-a.e. in [0, 1] 2 .By[START_REF] Wheeden | Dekken (Pure and Applied Mathematics)[END_REF] Corollary 10.50] we havelim x→0 µ([α, α + x]) |µ|([α, α + x]) = f (α) |µ| -a.e. and lim x→0 |µ|([α, α + x]) λ([α, α + x]) = h(α) λ -a.e. so that lim x→0 µ([α, α + x]) x = f (α)h(α) |µ| -a.e.Therefore the map θ is differentiable |µ| ⊗ |µ|-a.e. on [0, 1] 2 and its Jacobian is given byJac(θ)(α, β) = (-f (α)h(α), f (β)h(β)) |µ| ⊗ |µ|-a.e.so that in particular the determinant of the Jacobian vanishes only on a negligible set. The map θ is a homeomorphism on int Γ and Γ is connected; as a consequence the degree deg(int Γ, θ, p) is constantly equal to 1 or -1 for every p in int R(µ) [8, Theorem 3.35], assume for instance that it equals -1. Then by [8, Lemma 5.9] we have sgn det(-f (α), f (β)) = sgn det Jac(θ)(α, β) = deg(int Γ, θ, p) = -1 |µ| ⊗ |µ|-a.e. in Γ and therefore f is a T-system; Proposition 2 yields the conclusion.

Appendix: faces of codimension 1

The above Lemma 1 can be formulated in a more general setting. Proof (G. De Marco). It is not restrictive to assume that O ∈ A and that L ⊂ H where

Clearly H is a supporting hyperplane so that x n ≤ λ for every x = (x 1 , . . . , x n ) ∈ cl A.

We denote by • the norm of R n defined by (x 1 , . . . , x n ) = max i |x i |; we recall that the map p : x → x x is a homeomorphism from ∂A onto the unit sphere S (in the • -norm) of R n (see for instance [START_REF] Dold | Lectures on Algebraic Geometry[END_REF]). It is not restrictive to assume that

in fact it is enough to transform A and H with the map (x 1 , . . . , x n ) → (x 1 , . . . , x n-1 , rx n ) for a sufficiently large r. Then in particular we have x = λ for every x in L.


Yoan Decoudu

Katell Morin-Allory

Laurent Fesquet

A High-Level Design Flow for Locally Body Biased Asynchronous Circuits

Keywords: FDSOI, Bundled-data Circuits, High-Level Synthesis, Power Management, Fine-grain Body Biasing

Fully Depleted Silicon on Insulator (FDSOI) technologies offer new possibilities for power management, especially with dynamic body biasing. Traditional strategies are based on a large body bias generator, which drives the IP back-gates thanks to a dedicated and often complex power management system. As asynchronous circuits use local synchronizations with handshake components, which activate only the processing parts, it is possible to take advantage of these handshake signals to implement a simple and fine-grain body biasing strategy. Instead of driving IPs with a large body bias generator, we use tiny distributed generators, locally activating small body bias regions when the circuit is processing data. These latter are based on level-shifters and implemented as standard cells. Thus, we propose a high-level design flow associating asynchronous circuits and a local body biasing strategy, which does not require complex body bias management. Indeed, the local handshake signals directly control our dedicated body bias generators. Moreover, Place and Route operations are facilitated by the use of standard cell generators. The simulations show the flow efficiency, a finer grain body biasing and a significant power reduction.

I. INTRODUCTION

With the rising demand for energy-efficient systems, targeting portable applications or the Internet of Things, power consumption has gained an increased consideration for the past years. Traditional techniques to overcome this issue are voltage scaling or power gating. The first method reduces power consumption at the cost of performance degradation. The second one eliminates most of the consumption during the circuit idle period at the expense of a complex implementation and a high latency for its activation and deactivation.

Fortunately, the Fully Depleted Silicon on Insulator (FD-SOI) process [START_REF] Pelloux-Prayer | Planar fully depleted SOI technology: The convergence of high performance and low power towards multimedia mobile applications[END_REF] offers new design possibilities in recent technology nodes. In addition to limiting leakage with its isolation between transistors and the substrate, it allows extensive use of body biasing. The body biasing technique, which changes the transistor threshold voltage (V th ), was marginal due to its limited range in standard bulk CMOS technologies. Nevertheless, FDSOI technology significantly improves the body biasing range and enables its use as a replacement or in addition to conventional techniques.

Many techniques [START_REF] Kulkarni | A Statistical Framework for Post-Silicon Tuning through Body Bias Clustering[END_REF], [START_REF] Xu | Novel Vth Hopping Techniques for Aggressive Runtime Leakage Control[END_REF] have been proposed taking advantage of body biasing capabilities. The circuit is split into distinct large Body Bias Domains (BBD) as IPs have their own body bias voltage. These strategies either compensate circuit variations or address a trade-off between performance and power consumption. All these power management techniques rely on a Body Bias Generator (BBG) [START_REF] Kamae | A body bias generator with wide supply-range down to threshold voltage for within-die variability compensation[END_REF], [START_REF] Blagojevic | A fast, flexible, positive and negative adaptive body-bias generator in 28nm FDSOI[END_REF]. This system can precisely bias the substrate of a large BBD at a given voltage. However, such BBGs are large and complex.

In order to minimize power consumption without loss of performance, it is possible to bias small BBDs based on data activity. Nevertheless, common BBGs and power management units are not well-suited for such a strategy as they are too large, slow and complex. Hence, we propose a simple ON-OFF biasing strategy, also called a V th -Hopping scheme, relying on small BBGs. Moreover, we leverage the robustness of asynchronous circuits to quickly adapt the circuit to the changing gate delays. This idea has been first proposed in [START_REF] Hamon | Automatic Leakage Control for Wide Range Performance QDI Asynchronous Circuits in FD-SOI Technology[END_REF] and investigated in [START_REF] Fesquet | A Distributed Body-Biasing Strategy for Asynchronous Circuits[END_REF], but all these works are based on Quasi-Delay Insensitive (QDI) circuits [START_REF] Martin | Asynchronous techniques for system-onchip design[END_REF]. Although QDI circuits are very robust, they are also very large compared to their synchronous counterparts and not supported by conventional EDA tools.

To solve these issues, we decide to apply this body biasing strategy to another class of asynchronous circuits: bundleddata circuits. These circuits are quite similar to synchronous circuits. It allows us to take advantage of the improved robustness of the asynchronous paradigm with a modest area overhead. Therefore, this paper proposes a complete design flow (from high-level description to the transistor level) to set up our power management method. This flow is entirely compliant with standard commercial EDA tools and eases the critical step as the BBD partition. In addition, since asynchronous design can be challenging for many designers, we use high-level synthesis (HLS) to quickly obtain a bundleddata circuit from a high-level description.

Section II presents the FDSOI technology and one of its main features, the body biasing. Our flow is presented in Section III. Section IV and Section V respectively detail the asynchronous architecture and the body biasing strategy used in our work. Finally, our flow is applied in Section VI. [START_REF] Pelloux-Prayer | Planar fully depleted SOI technology: The convergence of high performance and low power towards multimedia mobile applications[END_REF] differs from classical bulk technology by adding a buried oxide (BOX) between the substrate and the transistor layer. It isolates drain and source pins from the substrate and, thus reduces the transistor leakage. Figure 1 shows the difference between bulk and FDSOI transistors. Moreover, the channel is now undoped, removing the random dopant fluctuation. This structure enables new options for designers [START_REF] Pelloux-Prayer | Fine grain multi-VT co-integration methodology in UTBB FD-SOI technology[END_REF]. For instance, it is possible to flip the well dopant (flip-well configuration) as shown in Fig. 2. In this case, the source, the drain and the substrate have the same type of dopant. In FDSOI technology, conventional wells are usually used with Regular threshold voltage (RVT) transistors and flip-wells with Low threshold voltage (LVT) transistors. RVT transistors normally use typical initial bias: 0V for the NMOS transistor and 1V for the PMOS transistor. On the contrary, LVT transistors use 0V for both transistor types. There are two types of body biasing:

• Reverse Body Biasing (RBB) increases PMOS and decreases NMOS bias voltages from the standard body bias voltage. It results in the decrease of the leakage power while deteriorating the transistor performance. • Forward Body Biasing (FBB) decreases PMOS and increases NMOS bias voltages from the standard body bias voltage. It results in an increase of the circuit speed at the expense of a higher leakage. If these two kinds of body biasing can be applied to both RVT and LVT transistors, the allowed range is different. Indeed, the junction between N-well and P-well substrates limits the body biasing range. Therefore, the FBB (resp. RBB) is for the LVT (resp. RVT) transistors as the body biasing range can go up to 3.3V.

III. PROPOSED FLOW

We set up an entire digital design flow to help designers as much as possible. We leverage HLS to quickly design bundleddata circuits. With these circuits, we implement a fine-grain body biasing strategy without complex power management. This design flow facilitates the Place and Route (PnR) steps thanks to BBG standard cells.

Figure 3 presents our design flow. It is very similar to a standard design flow for a synchronous circuit, with only a few added steps (in red on Fig. 3). The HLS, the synthesis and the PnR use conventional EDA tools.

The HLS step generates several sub-systems. The desynchronization step turns each synchronous sub-system into a bundled-data one (see Section Section IV-B) in which the synchronization is done locally through control signals. The activity detectors are then added to each asynchronous subsystem in the circuit. EDA tools rely on a Static Timing Analysis (STA) to constrain and verify circuits. Notice that the STA in bundleddata circuits can be a real issue due to the multiple local timing assumptions. Gimenez et al. [START_REF] Gimenez | Static Timing Analysis of Asynchronous Bundled-Data Circuits[END_REF] propose a methodology based on clocks and generated clocks to check each local path. We take advantage of this method to define the circuit constraints at a high level during the desynchronization step.

The PnR needs two additional sub-steps. The first one is to partition each sub-system into its own BBD and insert the BBGs in order to locally body bias the BBDs. The second one is the synthesis of local clock trees. It may seem inconsistent as there is no more clock signal in the circuit, but our desynchronized circuit has control signals that activate register banks. These signals are seen as local clock signals and they need to be buffered as any clock signal in a synchronous circuit. This step is not different from a standard clock tree synthesis but it is locally performed.

IV. ASYNCHRONOUS ARCHITECTURE A. Asynchronous Principle

Unlike the synchronous paradigm, there is no global synchronization signal in asynchronous circuits but many local synchronization signals respecting local timing assumptions, which ensure the correct circuit behavior. There are several classes of asynchronous implementations, depending on the timing assumptions made on the circuit model [START_REF]Principles of Asynchronous Circuit Design[END_REF]. In our work, we focus on bundled-data circuits [START_REF] Sutherland | Micropipelines[END_REF], that have an architecture resembling synchronous circuits. The data-path is composed of registers and combinational blocks. The synchronization block is not a clock tree like in synchronous circuits, but a control circuit composed of distributed controllers (see Fig. 4) that locally synchronize the data-path registers. In Figure 4, each controller CTRL i is associated to register bank R i . The controllers communicate together thanks to handshake signals that follow a dedicated communication protocol. The emission of a new data is notified to the circuit through a handshake communication that activates the first controller. When a controller is enabled, it triggers its associated register bank (and stores a data), and it notifies the next controller. The register bank triggering must happen when the incoming data are stable to avoid any timing violation. To ensure the correct behavior of the circuit, there is a delay element inserted in the handshake communication.

Data-path R 0 R 1 Comb R 2 Comb Control Circuit CTRL 0 CTRL 2 CTRL1
Asynchronous design is challenging for most engineers due to (1) a lack of know-how and (2) support from EDA tools. By using HLS [START_REF] Coussy | An Introduction to High-Level Synthesis[END_REF], we go beyond the lack of know-how to automatically generate an asynchronous circuit. The generated circuits can be handled by standard synchronous EDA tools.

The HLS tools synthesize a high-level description, usually in a C-like language, into an RTL description and have gained an increasing popularity in circuit design. Some studies [START_REF] Sparso | Current trends in high-level synthesis of asynchronous circuits[END_REF] have been made in the field of asynchronous HLS, but these solutions rely on specific description languages and tools. Hence, we decided to use a standard synchronous HLS tool and convert its output into an asynchronous circuit.

B. Desynchronization Method

Traditional desynchronization methods [START_REF] Cortadella | Desynchronization: Synthesis of Asynchronous Circuits From Synchronous Specifications[END_REF], [START_REF] Srivastava | Operation-Dependent Frequency Scaling Using Desynchronization[END_REF] only replace the clock signal with a control circuit. However, with these methods we lose some benefits of the asynchronous technology: the power consumption and the speed are very similar to the original synchronous circuit with an area overhead. Furthermore, the synchronization blocks are generated for the data-path and for the control-path. It means that the data-path is controlled by two blocks: the control-path (controlled by a synchronization block) and a synchronization block. There is a redundancy in the control, we propose to merge the controlpath and the synchronization block. Hence, the data-path is controlled solely thanks to an asynchronous control-path.

In practice, a synchronous circuit can be partitioned into two blocks, the control block that implements the Finite State Machine (FSM), and the data-path (see Fig. 5). In our desynchronization method [START_REF] Decoudu | From High-Level Synthesis to Bundled-Data Circuits[END_REF], we desynchronize the FSM, into an Asynchronous FSM (AFSM) (see Fig. 6): each state register is replaced by a controller. The transition function and output function (Λ i comb ) of the FSM remain unchanged. We only add a function that generates the local clock signals (Λ i en ) of the registers in the data-path. This function depends on the enabled states. This desynchronization method is particularly well-suited for circuits generated from HLS tools. Indeed, these circuits use a decomposition between a data-path and a control-path, the latter being an FSM. This method has been successfully applied to the commercial tool Catapult HLS from Siemens EDA [START_REF] Decoudu | From High-Level Synthesis to Bundled-Data Circuits[END_REF].

V. BODY BIASING STRATEGY

A. V th -Hopping Scheme

In order to minimize the biasing control unit complexity, we use a strategy rather simple based on V th -hopping. When there is data activity in a circuit within a BBD, the transistor V th is decreased to enhance the system speed. On the other hand, the transistor leakage is limited when there is no more activity by raising the V th . Thus, we use LVT transistors with an FBB scheme: the body bias voltage is applied when the system computes data and deactivated at idle time, which sets V th to its baseline. With this strategy, each BBD only needs an activity detector and a BBG with an ON-OFF behavior.

Asynchronous circuits have two main advantages for a dynamic body biasing strategy. Firstly, their robustness is enhanced compared to a synchronous circuit. Therefore, it is possible to change the V th parameter of the transistors within the circuit on the fly, without any timing violations. The body biasing activation and deactivation is then straightforward. Secondly, the handshake signals (the request and acknowledge signals) inherently indicate the circuit activity at a pipeline level. It gives ample freedom to choose the appropriate granularity for the BBDs, and it is only necessary to adapt the activity detector.

The combination between asynchronous circuits and a simple V th -hopping body biasing scheme allows us to considerably reduce the power control complexity and the latency of the body bias activation and deactivation. It is then possible to use this dynamic body biasing strategy on smaller and faster blocks than usual.

The study in [START_REF] Fesquet | A Distributed Body-Biasing Strategy for Asynchronous Circuits[END_REF] shows minor gains in consumption when the BBD granularity is at a pipeline level while the area overhead strongly increases. Hence, we decide to define the BBD granularity at a system level where the start of an AFSM operation activates the body bias voltage, as shown in Fig. 7. Notice that this granularity is still much finer than the usual IP biased in conventional power management. The activity detector only corresponds to an OR logical gate between the input state request in the AFSM and the input request ready_req. A simple wire connecting the input state and the BBGs would be enough but taking into account ready_req allows reduction of the latency of the body bias activation when new data arrive.

Asynchronous Finite State Machine

Data

The BBGs, connected to the activity detector output, generate the necessary voltage for the bias of the NMOS and PMOS. As we use a simple V th -hopping strategy, where the polarization is either active or inactive, the BBG can be a simple generator. The BBG is then a level-shifter as proposed in [START_REF] Hamon | Automatic Leakage Control for Wide Range Performance QDI Asynchronous Circuits in FD-SOI Technology[END_REF]. It is designed as a standard cell to ease its integration in the floorplan of digital circuits.

B. Energy Efficiency

The body biasing strategy used in our work is only effective under certain conditions. Indeed, the successive BBD activation produces an energy overhead. Hence, the energy saved during the idle period of the circuit needs to be greater than the activation of the circuit BBDs. Otherwise, there is no improvement compared to a system where the body bias is constantly active.

We analyze a linear system composed of N stages depicted in Fig. 8. The input data, represented in red, is loaded continuously in the circuit. Once data reaches a stage, its body bias voltage is activated and increments the green curve (indicating the number of biased stages). When all the data are in the pipeline, the first stages start entering idle mode. Thus, there are three phases in the scenario: a loading phase, a steady phase and an unloading phase. We define ∆t BB as the period where at least a stage is active and ∆t noBB as the idle time from which there is no more data in the circuit. We denote also ∆t BBi the active period of the i th BBD. The substrate of a BBD is represented as a capacitance C b and is charged once the BBD is activated. For the i th BBD in the system, the energy E bias,i consumed for the body bias activation or deactivation at a voltage V bb is defined as:

Time

E bias,i = C b,i V 2 bb (1)
Hence, the global energy E total consumed by the circuit is:

E total = E BB + E noBB + 2 N -1 i=0 E bias,i (2)
During the period ∆t noBB , there is only circuit static power consumption without body biasing, denoted P 0 l . The energy E noBB is then given in Equation 3. Rigorously, it is necessary to include the power consumption of the activity detector and the BBGs. However, their power consumption, both dynamic and static, are negligible compared to the rest of the system.

E noBB = ∆t noBB P 0 l (3)
Similarly, E BB corresponds to the power consumption P V bb tot with a body bias voltage V bb during ∆t BB . Nevertheless, the loading and unloading phases allow for a reduced power consumption. Indeed, during ∆t BB0 for instance, only the first stage is biased, with a leakage denoted P V bb l,0 . Therefore, the static power consumption of the other stages is reduced to P 0 l,j compared to a circuit completely biased. A similar analysis is done for each stage.

We denote E s,pl the energy saved during the loading phase. If the loading and unloading phases are balanced, both cases save the same amount of energy. It leads to the following definition:

E BB = ∆t BB P V bb tot -2E s,pl where E s,pl = N -1 i=0 ∆t BBi ( N -1 j=i+1 (P V bb l,j -P 0 l,j )) (4)
Thanks to Equations 2, 3 and 4, we precisely know the energy consumption of our method. Compared to a constantly biased circuit, we define the energy overhead E O and the energy savings E S of our strategy:

E O = 2 N -1 i=0 E bias,i E S = ∆t noBB (P V bb l -P 0 l ) + E s,pl (5)
To enhance the power efficiency with the dynamic body biasing, we look for the situation where E S is higher than E O . Finally, we deduce from Equation 5 the minimum idle period ∆t noBB for an effective power reduction:

∆t noBB > 2V 2 bb N -1 i=0 (C b,i -E s,pl ) P V bb l -P 0 l (6)
Equation 6 presents the lower limit of our method. This idle period, also known as the Minimum Idle Time (MIT), allows compensation for the energy overhead induced by this body biasing strategy. Therefore, the power savings strongly depend on the system operation scenarios. For this purpose, we define the activity ratio AR of the circuit:

AR = ∆t BB ∆t BB + ∆t noBB (7)
To compare each scenario used in the simulations, we use the activity ratio AR defined in Equation 7.

VI. TESTCASE

To ease the understanding of the results, we first apply the method on a chain of Advanced Encryption Standard (AES) designed by HLS. This system is complex enough to show the benefits of the method, but small enough to use conventional EDA tools with academic licences that limit their efficiency. The performances of the circuit have been evaluated in FDSOI 28 nm technology from STMicroelectronics.

A. System Presentation

The global circuit is a linear system of AES with a 128-bit key as shown in Fig. 9. It was hierarchically synthesized with Catapult HLS from Siemens EDA. All the synthesized AES have the same architecture. The second step is to desynchronize the circuit. We apply the method presented in Section IV-B on each AES. Since the BBD granularity is defined at the system level, we associate each AES to a specific BBD. We want a body bias activation in the range of 1 ns. We thus assigned 32 BBGs for each BBD.

To have some insight on the strategy benefits, we compare our power management method to a circuit with only one BBD always activated. We apply it on 3 activity ratios (0.5, 0.25 and 0.1). For each scenario, we sent the same input data burst on each circuit and we adapt the idle period ∆t noBB to reach the desired activity ratio. The body bias voltage applied is V bb = 1.1V.

B. Results

The circuit is synthesized thanks to Design Compiler from Synopsys. The PnR phase uses Cadence Innovus. All the results in speed and consumption are given after the place and route. Electrical simulations at the transistor level permit to obtain an accurate power consumption evaluation. Since it is too time-consuming for digital circuits, we define the switching activity from a back-annotated simulation at the gate-level. This analysis, done with PrimeTime, is only an approximation because the energy consumed for the body bias activation is not included, but still gives a good idea of the power consumption in the circuit.

1) Desynchronized AES: We first compare an asynchronous AES to its original synchronous counterpart without any body biasing. Circuits are synthesized with an 800 MHz target frequency at 0.9V. The results are reported in Table I. The last column displays the overhead between the desynchronized circuit and the synchronous one. After synthesis, the area overhead of the desynchronized AES is 0.9% which is negligible. The asynchronous AES has a latency of 39 ns, with a less than 1% difference with the synchronous circuit. The power consumption shows an improvement of 8% after the desynchronization.

We notice that our desynchronization method provides a bundled-data circuit similar to the original circuit with a slight improvement in power consumption. It has its own benefits.

2) Global Circuit: An AES after PnR has an area of 22440 µm 2 . The addition of the BBGs increases the area by 4.8%. Moreover, each BBD needs to be isolated from the rest of the circuit and leads to an additional increase of 12.1%. Finally, an AES with our body biasing strategy reaches an area of 26368 µm 2 . In the chained system, it leads to a global overhead of 17.5%.

A fair comparison with the other biasing strategies is not straightforward. Indeed, the conventional BBGs are larger than ours, but they are also used to bias larger systems with a precise voltage.

Regarding the speed of the system, there is no speed difference in comparison with an always biased circuit, only negligible fluctuations. One AES with an active body bias voltage computes data in 31.9 ns, which is an improvement of about 18% compared to the AES presented before. Table II presents the power consumption of each scenario for our system and the always biased reference. We normalized the results according to the power consumption of the always biased circuit with AR = 0.5 activity ratio.

We observe that the two circuits consume less with the decrease of the activity ratio AR, which was expected since the dynamic power consumption is related to the circuit activity. As expected, the dynamic biasing strategy reduces the consumption compared to the always biased reference. The consumption is divided from 1.7 up to 3.6 according to the activity ratio, i.e. the power savings are from 42% up to 72%. The less active the circuit is, the bigger the gain. This is due to a higher leakage in the always biased circuit, even during the idle period. However, be aware that these results do not take into account the energy consumed during the body bias activation and deactivation.

The gain would even more significant if the body bias voltage was higher. We cannot show these results since the digital library models are only characterized for a few body bias values.

VII. CONCLUSION

In this work, we presented an asynchronous HLS design flow associated to a simple dynamic body biasing strategy. With a simple V th -hopping scheme and the intrinsic robustness of asynchronous circuits, we achieve a very fine-grain body biasing strategy relying on data activity. According to our simulations, we demonstrate power savings from 42% up to 72% for a small data activity compared to always biased circuits.

Moreover, our design flow eases the design of fine-grain body bias asynchronous circuits, thanks to commercial HLS tools, a desynchronization script and tiny body bias generators designed as standard cells. The main design steps are as follows. First, a bundled-data circuit is obtained from a highlevel description in C, which is compiled by Catapult HLS from Siemens EDA. Then, the control part resulting from the HLS is desynchronized and we extract the design constraints (mainly timing constraints). Finally, tiny BBGs, which have been embed in a standard cell format, are inserted in the floorplan during the PnR operations.

The presented simulations are only gate-level estimations. Future works will target transistor-level simulations for better accuracy. A testchip in FDSOI 28 nm from STMicroelectronics has also been designed following this design flow. It must now be tested to validate our design flow and simulation results. We also plan to investigate the power reduction obtained with a lower supply voltage, while compensating the performance drop thanks to the body biasing. As simulations required dedicated models for each supply voltage, the best is to directly obtain these results from the testchip measurements.

Fig. 1 .

 1 Fig. 1. NMOS transistor in classical Bulk (a) and FDSOI Technologies (b).

Fig. 2 .Fig. 3 .

 23 Fig. 2. Transistor with (a) Conventional well and (b) Flip-well configuration.

Fig. 4 .

 4 Fig. 4. Bundled-data circuit architecture.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Synchronous circuit architecture.

Fig. 7 .

 7 Fig. 7. Scheme of dynamic body biasing strategy.

Fig. 8 .

 8 Fig. 8. Variation of the number of body biased BBDs.

Fig. 9 .

 9 Fig. 9. Linear circuit with 5 AES.

ACKNOWLEDGMENT

This work has been supported by the OCEAN12 European Project (Ecsel JU, Grant Agreement N o 783127).