Alain Daurat
email: daurat@unistra.fr

Mohamed Tajine
email: tajine@unistra.fr

Mahdi Zouaoui
email: mzouaoui@unistra.fr

Patterns in discretized parabolas and length estimation (extended version)

Keywords: Digital Curve, Pattern, Multigrid Convergence

We estimate the frequency of the patterns in the discretization of parabolas, when the resolution tends to zero. We deduce that local estimators of length almost never converge to the length for the parabolas.

Introduction

Length estimation is an important domain of Image Analysis (see [START_REF] Coeurjolly | A comparative evaluation of length estimators[END_REF] for a review). In this paper, we will consider the problem of estimating the length of a curve from its discretizations at different resolutions. In particular we are interested in the comportment of estimators when the resolution tends to zero. We also restrict our study to special estimators called "local estimators" which consist in considering patterns which are pieces of fixed length of the discretized curve. Local estimators simply consist to fix a weight to each pattern and summing these weights to obtain the estimation of length (See Fig. 4 for illustration). So, if we want to study the estimated length by local estimators when the resolution tends to zero, we have at first to study the number of occurrences of a pattern of the discretization of digital curves. In fact an asymptotic result about the occurrence number of patterns for discretized general curves looks to be a quite hard problem, because the discretization process is not a continuous process (the integer part function is not continuous), so the estimation of the occurrence number of patterns cannot be deduced from Mathematical Analysis arguments, but by Number Theory arguments. The two first authors of this paper have already made this study for segments in [START_REF] Tajine | On local definitions of length of digital curves[END_REF]. In this paper we continue this work by considering another class of curves, the parabolas.

The paper is organized as follows: Section 2 describes the notations used in this paper, Section 3 will be devoted to the study of the frequency of patterns in parabolas, and finally Section 4 will apply the results of this study to the local estimators of length of parabolas. Appendix A contains the detailed proofs which are not in the main part of this paper.

In this section we precise the notations that will be used in all the paper.

-For x ∈ R we denote by ⌊x⌋ (resp.⌈x⌉) the integer k such that k ≤ x < k + 1 (resp. k -1 < x ≤ k). -The fractional part of x is denoted x and is defined by x = ⌊x⌋ + x .

-For A, B ∈ Z, the discrete interval {A, A+1, . . . , B -1, B} is denoted A, B .

-Let m be a positive integer. A pattern of size m is a function ω from 0, m to Z such that ω(0) = 0 and ω(k + 1) ∈ {ω(k), ω(k) + 1} (see Fig. 1). The set of patterns of size m is denoted P m .

-If X and Y are two real numbers such that Y > 0 then X mod Y is the real number such that 0 ≤ X mod Y < Y and X-X mod Y Y ∈ Z. -For r ∈ R and E ⊂ R 2 , rE = {(rx, ry)|(x, y) ∈ E}.

Frequency of patterns in Discrete Parabolas

Let a, b ∈ R such that a < b and a derivable function g : [a, b] → R which satisfies 0 ≤ g ′ (x) ≤ 1 for all x ∈ [a, b].
In all the following, for any r > 0 we use the notations:

• A r = ⌈ a r ⌉, B r = ⌊ b r ⌋, N r = B r -A r + 1, • C g r = r{(X, Y ) ∈ Z 2 | A r ≤ X ≤ B r and Y = ⌊ g(rX) r ⌋}.
The set C g r is the "naive" discretization of the graph of g at resolution r, and N r is its number of points.

Let m be a positive integer. The pattern at position X ∈ A r , B rm of size m of C g r , denoted ω g X,r,m is defined by:

ω g X,r,m (k) = ⌊ g(r(X + k)) r ⌋ -⌊ g(rX) r ⌋.
The frequency of a pattern ω of size m in C g r is defined by:

F g r (ω) = card{X ∈ A r , B r -m | ω g X,r,m = ω} N r -m .
The aim of this section is the study of F g r (ω) for some functions g. For this we will approximate the curve by its tangents which will also be discretized, so we need some notions about digital straight lines:

For u ∈ [0, 1] and v ∈ [0, 1), let us denote s u,v m the pattern of size m defined by: s u,v m (k) = ⌊uk + v⌋. A pattern of this form is called a digital segment of size m.

For any pattern ω,

P I(ω) = {(u, v) ∈ [0, 1] 2 | ⌊uk + v⌋ = ω(k) for any k ∈ 0, m }, pinf u (ω) = inf{v | (u, v) ∈ P I(ω)}, (1) psup
u (ω) = sup{v | (u, v) ∈ P I(ω)}, (2)
F L u (ω) = 0 if {v | (u, v) ∈ P I(ω)} = ∅ = psup u (ω) -pinf u (ω) otherwise.
P I(ω) is called the preimage of ω, it is nonempty if and only if ω is a digital segment. F L u (ω) is intuitively the frequency of the pattern ω in the discretized straight lines of slope u. (See [START_REF] Tajine | On local definitions of length of digital curves[END_REF][START_REF] Tajine | Digital segments and Hausdorff discretization[END_REF] for more details and [START_REF] Daurat | About the frequencies of some patterns in digital planes. Application to area estimators[END_REF] for the generalization to slopes of planes). In all the paper, the considered curves are parabolas corresponding to the function g(x) = αx 2 . We distinguish two cases: the case α irrational and the case α rational. In Subsection 3.1, we will see that for α irrational, the frequency F g r (ω) converges, when r is rational and tends to zero, to a quantity which can be expressed by using the function x → F L g ′ (x) (ω). In Subsection 3.2, we study the case α rational, but we do not succeed to prove a similar result as in the case α irrational. Nevertheless we obtain a weaker result (The Tangent Lemma).

Parabolas of equation y = αx 2 with α irrational

In this subsection we consider curves C g r for g defined on [a, b] by g(x) = αx 2 with α irrational, and 0 ≤ a < b ≤ 1 2α . This last hypothesis is needed to have 0

≤ g ′ (x) ≤ 1 for x ∈ [a, b].
The main result of this subsection is the following:

Theorem 1. If g(x) = αx 2 with α / ∈ Q then for any pattern ω we have

F g r (ω) ---→ r→0 r∈Q 1 b -a b a F L g ′ (x) (ω)dx (3)
The rest of this subsection is devoted to the proof of this Theorem. The first needed lemma shows that the discretization of a curve and the discretization of its tangent are similar near the origin of the tangent and when the resolution tends to zero:

Lemma 1 (Tangent Lemma). If g is defined on [a, b] by g(x) = αx 2 with α irrational, and 0 ≤ a < b ≤ 1 2α then card{X ∈ A r , B r -m | ω g X,r,m = s g ′ (rX), g(rX) r m } N r -m ---→ r→0 r∈Q 0.
Lemma 1 is illustrated by Fig. 2. In the last lemma we consider r ∈ Q because its proof needs the irrationality of αr. Before starting the proof of Lemma 1 we need one more notation and two other lemmas. For X ∈ A r , B r , we define P r,k (X) by:

P r,k (X) = g(rX) r + g ′ (rX)k = αrX 2 + 2αkrX = αr((X + k) 2 -k 2 ).
This definition is motivated by the following lemma:

Lemma 2. If r < 1 αm 2 , then for any X we have ω g X,r,m = s g ′ (rX), g(rX)
r m if and only if for all k ∈ 0, m we have P r,k (X) < 1αrk 2 .

Proof.

ω g X,r,m (k) = ⌊ g(r(X + k)) r ⌋ -⌊ g(rX) r ⌋ = ⌊ g(rX) r + g ′ (rX)k + αrk 2 ⌋ -⌊ g(rX) r ⌋
We know that ⌊u

+ v⌋ = ⌊u⌋ + ⌊v⌋ iff u + v < 1. So ω g X,r,m (k) = ⌊ g(rX) r +g ′ (rX)k⌋-⌊ g(rX) r ⌋ iff g(rX)
r +g ′ (rX)k + αrk 2 < 1. With the hypothesis r < 1 αm 2 we have αrk 2 = αrk 2 . But:

⌊ g(rX) r +g ′ (rX)k⌋-⌊ g(rX) r ⌋ = ⌊ g(rX) r +g ′ (rX)k⌋-⌊ g(rX) r ⌋ = s g ′ (rX), g(rX) r m (k) So ω g X,r,m = s g ′ (rX), g(rX) r m iff for all k ∈ 0, m we have P r,k (X) < 1-αrk 2 . ⊓ ⊔ Lemma 3. Let I be an interval of [0, 1]. We have T r,k (I) ---→ r→0 r∈Q µ(I) where T r,k (I) = 1 N r card{X ∈ A r , B r | P r,k (X) ∈ I} and µ(I) is the usual length of I.
The proof of this lemma uses Weyl's argument, as in the proof of Theorem 1 of [START_REF] Tajine | On local definitions of length of digital curves[END_REF] or Appendix A.1 of [START_REF] Daurat | About the frequencies of some patterns in digital planes. Application to area estimators[END_REF], but extended to the quadratic case following the same ideas as in [5, p6-7]. It is given in Appendix A.1.

Proof of Lemma 1. We recall that ω g X,r,m = s

g ′ (rX), g(rX) r m iff for all k ∈ 0, m we have P r,k (X) < 1 -αrk 2 so: card{X ∈ A r , B r -m | ω g X,r,m = s g ′ (rX), g(rX) r m } N r -m ≤ N r N r -m m max k=0 T r,k (I r,k ) where I r,k = [1 -αrk 2 , 1), so it is sufficient to show that T r,k (I r,k ) ---→ r→0 r∈Q 0 for any k ∈ 0, m . Let ε > 0, there exists R 1 > 0 such that for any r < R 1 we have αrk 2 < ε 2 .
We know by Lemma 3 that there exists R 2 > 0 such that for any

r < R 2 we have T r,k (I R0,k ) ≤ µ(I R0,k ) + ε 2 . If r is such that r < min(R 1 , R 2 ), we have: S r,k (I r,k ) ≤ S r,k (I R1,k ) ≤ µ(I R1,k ) + ε 2 = αrk 2 + ε 2 ≤ ε 2 + ε 2 = ε
This finishes the proof of Lemma 1.

⊓ ⊔

Sketch of Proof of Theorem 1. We present here the main ideas of the proof of Theorem 1. The detailed proof is in Appendix A.2. By using Lemma 1 we know that F g r (ω) has the same limit as r tends to zero as:

G g r (ω) = card{X ∈ A r , B r -m | s g ′ (rX), g(rX) r m = ω} N r -m .
But s x,y m = ω is equivalent to (x, y ) ∈ P I(ω) so:

G g r (ω) = card{X ∈ A r , B r -m | (g ′ (rX), g(rX) r ) ∈ P I(ω)} N r -m
which has the same limit as H r (P I(ω)) where

H r (E) = card{X ∈ A r , B r | (g ′ (rX), g(rX) r ) ∈ E} B r -A r + 1
.

By applying Lemma 3 with k = 0 to the piece of the curve y = g(x) restricted to the domain g ′-1 (α 1 ) ≤ x ≤ g ′-1 (α 2 ), we can prove:

H r ([α 1 , α 2 ) × I) ---→ r→0 r∈Q g ′-1 (α 2 ) -g ′-1 (α 1 ) b -a µ(I)
So by approximating P I(ω) as the union of rectangles

n i=1 [y i-1 , y i ) × [pinf yi (ω), psup yi (ω))
we approximate H r (P I(ω)) by:

n i=1 g ′-1 (y i ) -g ′-1 (y i-1 ) b -a F L yi (ω) which is a Riemann sum for b a F L g ′ (x) (ω)dx. ⊓ ⊔ Corollary 1. If g(x) = αx 2 with α / ∈ Q, then for any pattern ω which is not a digital segment we have F g r (ω) ---→ r→0 r∈Q 0.
Numerical Application: We illustrate Theorem 1 with an example. Consider the curve

C defined y = g(x) = 1 √ 2 x 2 for x between a = 0 and b = 1 √ 2 ,
and the pattern ω of size m = 3 defined by (ω(0), ω(1), ω(2), ω(3)) = (0, 1, 2, 2). We will compute the limit of the frequency of ω when the resolution tends to zero.

First we can compute easily F L α (ω) because α → F L α (ω) is a continuous function which is affine between two m-Farey numbers (see [START_REF] Tajine | Digital segments and Hausdorff discretization[END_REF]). So we deduce:

F L α (ω) = 0 if α ∈ [0, 1 2 ] = 2α -1 if α ∈ [ 1 2 , 2 3 ] = 1 -α if α ∈ [ 2 3 , 1]
Theorem 1 proves that:

F g r (ω) ---→ r→0 r∈Q 1 b -a b a F L g ′ (x) (ω)dx = √ 2 1 √ 2 0 F L √ 2x (ω)dx = √ 2 2 3 √ 2 1 2 √ 2 (2 √ 2x -1)dx + 1 √ 2 2 3 √ 2 (1 - √ 2x)dx = 1 12
3.2 Parabolas of equation y = αx 2 with α rational Now we are interested in the case where α is rational. Theorem 1 can be generalized to α rational and to the irrational resolutions r because only the irrationality of αr is used in the proof of this theorem. On the contrary, in the case α rational and rational resolutions, the only result we will prove in this subsection is about the Tangent Lemma. Moreover, we must impose some restrictions about the resolution r and the interval [a, b] of definition of the parabola: rα = 1 p where p is a prime number ; a = 0 and b = 1 2α . In all this subsection we suppose that these conditions are satisfied. Actually, we do not succeed to prove the Tangent Lemma in the general case for α rational.

Let P r,k (X) = rα((X +k) 2 -k 2 ). We will prove that for any interval

I ⊂ [0, 1] lim r→0 1 rα is prime card{X ∈ A r , B r -k | P r,k (x) ∈ I} N r -k = µ(I) Definition 1.
Let p be a prime number and a be an integer number, we define the Legendre symbol ( a p ) of a relatively to p by

( a p ) =    0 if p divides a 1 if
( n p )| < √ p log(p) Corollary 2. Let J = M, M + N be an integer interval. Then | card(J) 2 -card{y ∈ I | ( y p ) = 1}| < √ p log(p).
Lemma 4. Let α be a rational number and assume that a = 0 and b = 1 2α . Then, for any interval

I ⊂ [0, 1] lim r→0 card{X ∈ A r , B r -k | P r,k (X) ∈ I} N r -k = µ(I)
where the limit is taken on the r such that r > 0 and rα = 1 p where p is a prime number.

Proof. The function X → X 2 mod p from 1, p-1

2 to {Y | ( Y p ) = 1} is a bijection. Put H r = card{X ∈ A r , B r -k | P r,k (x) ∈ I} N r . Then H r = card{X ∈ k, ⌊ p 2 ⌋ | X 2 -k 2 p ∈ I} N r -k = 2card{X ∈ k, p-1 2 | X 2 mod p-k 2 p ∈ I} p + 1 -2k (4)
Thus

card{X ∈ 1, p -1 2 | X 2 mod p ∈ J} = card{Y ∈ J | ( Y p ) = 1} where J = pI + k 2 . So |card{X ∈ k, p-1 2 | X 2 mod p ∈ J} -card{Y ∈ J | ( Y p ) = 1}| < k.
By using Pólya-Vinogradov inequality we have:

| card(J) 2 -card{X ∈ 1, p -1 2 | X 2 mod p ∈ J}| < √ p log(p) So, | card(J) 2 -card{X ∈ k, p-1 2 | X 2 mod p ∈ J}| < √ p log(p) + k. By (4) we have | 2 p + 1 -2k card(J) 2 - 2 p + 1 -2k card{X ∈ k, p -1 2 | X 2 mod p ∈ J}| < 2 √ p log(p) + 2k p + 1 -2k Thus, lim r→0 card{X ∈ A r , B r -k | P r,k (X) ∈ I} N r -k = µ(I) ⊓ ⊔
Theorem 2 (Tangent Lemma for rational slopes and special rational resolutions). For any rational α > 0 and any a, b such that 0 ≤ a < b ≤ 1 2α we have

card{X ∈ A r , B r -m | ω g X,r,m = s g ′ (rX), g(rX) r m } N r -m --------→ r→0 1 rα is prime 0
Proof. The case where a = 0, b = 1 2α can be proved exactly in the same way as for Lemma 1 by using Lemma 4 instead of Lemma 3. Consider the general case [a, b] ⊂ [0, 1 2α ]. Then we know that:

card{X ∈ A r , B r -m | ω g X,r,m = s g ′ (rX), g(rX) r m } N r -m ≤ ⌊ 1 2αr ⌋ + 1 -m N r -m • card{X ∈ 0, ⌊ b r ⌋ -m | ω g X,r,m = s g ′ (rX), g(rX) r m } ⌊ 1 2αr ⌋ + 1 -m -------→ r→0 1 rα is prime 1 2α b -a • 0 = 0 because of the case a = 0, b = 1 2α
.

⊓ ⊔

Unfortunately we do not successfully generalize Theorem 1 to rational α and some rational resolutions even if experimentally Theorem 1 seems to be true in all the cases. ) converges when the resolution r is rational and tends to zero, to the length of the parabola only for a finite number of irrational numbers α.

Application to local estimators of length

Sketch of proof. For this proof we use the notation

[f (x)] b a = f (b) -f (a). It is easy to see that: l(p, g, r) - (b -a) m ω∈Pm p(ω)F ′ g r (ω) ---→ r→0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 C 1 2 C 1 4 r = 1 2 r = 1 4 C y = g(x) ω 2 ω 4 ω 2 ω 2 ω 1 ω 1 ω 2 ω 4 ω 4 ω 2 ω 2 ω 2 ω 2 ω 1 ω 3 ω 1 ω 1 ω 1 ω 3 b) a) p(ω 4 ) = 2.8 p(ω 2 ) = 2.2 p(ω 3 ) = 2.2 p(ω 1 ) = 2 ω ω ω ω
Fig. 3. Estimation of length of a curve from its discretization for two different resolutions: a) l(p, g, 1 2 ) = 1 2 (2p(ω 1 ) + 3p(ω 2 ) + 1p(ω 4 )) = 6.7, b) l(p, g, 1 4 ) = where

F ′ g r (ω) = card{X ∈ A r , B r -m ∩ (A r + mZ) | ω g X,r,m = ω} ⌊ Br -m-Ar m ⌋ .
Consider again the curve defined by g(x) = αx 2 for α / ∈ Q. The proof of Theorem 1 can be extended to prove that:

F ′ g r (ω) ---→ r→0 r∈Q 1 b -a b a F L g ′ (x) (ω)dx. So, l(p, g, r) ---→ r→0 r∈Q 1 m ω∈Pm p(ω) b a F L g ′ (x) (ω)dx.
(5)

We know that x → F L x (ω) is piecesewisely affine ( [START_REF] Tajine | Digital segments and Hausdorff discretization[END_REF]). From this property we deduce that we can partition the interval [0, 1 2b ] in a finite number of intervals (I k ) 0≤k≤n such that L est (α) = lim r→0 r∈Q l(p, g, r) is of the form A α + Bα + C on each interval I k . (See Appendix A.3 for the details).

Let L real (α) be the length of the parabola {(x, αx 2 ) | x ∈ [a, b]}. We have:

L real (α) = b a 1 + (2αx) 2 dx = x 1 + (2αx) 2 2 + arg sinh(2αx) 4α b a
Suppose that L real (α) = L est (α) for an infinite number of irrational numbers α, then there exists an interval I k of the previous partition of [0,

αL real (α) = A + Bα 2 + Cα for all α ∈ [0, 1 2b ]
We have: 2 ≈ 0.813172, this limit is different from the length of the parabola which is 1 2

∂(αL real (α) ∂α = b 1 + (2αb) 2 -a 1 + (2αa) 2 = b -a + 2(b 3 -a 3 )α 2 + o(α 2 ) when α → 0 But ∂(A+Bα
+ 1 4 √ 2 log(1+ √
2) ≈ 0.811612. Moreover Figure 4 shows how the length given by the estimator converges to its limit when the resolution tends to zero. It seems on this example that l(p, g, r) -L est = O(r).

= 1 √ 2 x 2 , 0 ≤ x ≤ 1 √ 2 .

Conclusion and Perspectives

In this paper, we have proved some local properties of discretizations of parabolas: First we show that locally discretization of parabola and discretization of its tangent often coincide (Tangent Lemma: Lemmas 1 and Theorem 2). In particular, asymptotically, the local patterns of a discretized parabola are digital segments. From this, we also give an explicit formula for the limit of frequency of a pattern of a parabola when the resolution tends to zero (Theorem 1). This has the important consequence that we can know to what tend local estimators of length for the parabolas, moreover it can be proved that this limit is often different from the length of the curve. This work mainly brings two perspectives:

-The extension of Formula (3), which gives the limit of the frequency of pattern when the resolution tends to zero, to more general curves, in particular to the curves y = P (x) when P is a polynomial of degree greater than 2. -The application of this work for recognition of curve by just looking at patterns. For example, if the frequencies of patterns of a curve does not satisfy Theorem 1 then it is not a parabola of equation y = αx 2 .

Granville

A Proofs

Additional notations -The distance between x and Z is denoted x . So x = min( x , 1x ).

-If z is complex number z denotes its conjugate, and Re(z) denotes its real part. -gcd(p, q) denotes the greatest common divisor of p and q.

A.1 Proof of Lemma 3

For any f ∈ L 1 ([0, 1]) we define:

S r,k (f ) = 1 N r Br X=Ar f ( P r,k (X) ).
so we have T r,k (I) = S r,k (χ I ) where χ I is the indicator function of I. We denote e(t) = e 2πit and e c (t) = e(ct).

Sublemma 5 For any c ∈ Z \ {0} we have S r,k (e c ) ---→

r→0 r∈Q 0. Proof. |S r,k (e c )| 2 = S r,k (e c )S r,k (e c ) = 1 N 2 r Ar≤X,Y ≤Br e c (P r,k (X))e c (P r,k (Y )) = 1 N r + 2 N 2 r Re   Ar≤X<Y ≤Br e c (P r,k (Y ) -P r,k (X))   Let us pose Y = X + h, we have P r,k (Y ) -P r,k (X) = rα(X + h) 2 + 2αk(X + H) -αrX 2 -2αkrX = P r,k (h) + 2αrXh So: |S r,k (e c )| 2 = 1 N r + 2 N 2 r Re Br-1 X=Ar Br-X h=1 e c (P r,k (h))e c (2αrXh) = 1 N r + 2 N 2 r Re Nr-1 h=1 Br-h X=Ar e c (P r,k (h))e c (2αrXh) = 1 N r + 2 N 2 r Re Nr-1 h=1 e c (P r,k (h)) Br-h X=Ar e c (2αrXh) Subsublemma 6 For any β ∈ R \ Z, u, v ∈ Z such that u ≤ v we have: v k=u e(βk) ≤ min(v -u + 1, 1 2 β
).

Proof. ⊓ ⊔

v k=u e(βk) = e(βu) 1 -e(β(v -u + 1)) 1 -e(β)
As Re(x) ≤ |x|, Subsublemma 6 shows that:

|S r,k (e c )| 2 ≤ 1 N r + 2 N 2 r Nr-1 h=1 min(N r , 1 2 2αrch ) (6) Subsublemma 7 Let C 0 ≥ 0, u ∈ R \ Q, N, p, q ∈ N which satisfy q ≤ C 0 N , |uq -p| ≤ 1 C0N , gcd(p, q) = 1. We have N -1 h=1 min(N, 1 2 uh ) ≤ 4(1 + C 0 ) N 2 q + N log q .
Proof.

N -1 h=1 min(N, 1 2 uh ) ≤ ⌊ N -1 q ⌋ H=0 qH+q h=qH+1 min(N, 1 2 uh )
But:

qH+q h=qH+1 min(N, 1 2 uh ) = q h=1 min(N, 1 2 u(qH + h) ) u(qH + h) = ( p + ε q )(qH + h) where ε = uq -p = pH + p q h + εH + εh q = p q h + εH + εh q
Let γ = (εH) mod 1 q , and k 0 such that εH = γ + k0 q . We have:

( p q h + εH) mod 1 = γ + i h q where i h = (ph + k 0 q) mod q. As gcd(p, q) = 1, {i h | h ∈ 1, q } = 0, q -1 . If i h < q 2 then u(qH + h) = γ + i h q + εh q ≥ γ + i h q - |ε|h q because x → x is Lipschitz continuous with constant 1 = γ + i h q - |ε|h q ≥ i h q -|ε| as h ≤ q ≥ i h q - 1 C 0 N . (7)
Similarly if i h ≥ q 2 then u(qH + h) ≥ γ + i h q - |ε|h q = 1 -(γ + i h q ) - |ε|h q ≥ q -1 -i h q - 1 C 0 N . ( 8
)
If we use the variable change h → i h for i h < q 2 , h → q -1i h for i h ≥ q 2 , the inequality min(N, 1 2 u(qH+h) ) ≤ N for i h = 0, 1, q -2, q -1, and the inequalities (7),(8) for the other i h , we deduce:

q h=1 min(N, 1 2 u(qH + h) ) ≤ 4N + 2 ⌊ q-1 2 ⌋ i=2 1 2 i q -1 C0N .
But 1 1-x ≤ 1 + 2x for x ∈ (0, 1 2 ]. So for i ≥ 2 we have:

1 i q -1 C0N = q i 1 1 -q iC0N ≤ q i 1 + 2 q iC 0 N because q iC 0 N ∈ (0, 1 2 ] as i ≥ 2 and q ≤ C 0 N ≤ 2 q i So q h=1 min(N, 1 2 u(qH + h) ) ≤ 4N + 2q ⌊ q-1 2 ⌋ i=2 1 i .
But:

⌊ q-1 2 ⌋ i=2 1 i = ⌊ q-1 2 ⌋ i=2 i i-1 1 i dt ≤ ⌊ q-1 2 ⌋ i=2 i i-1 1 t dt = ⌊ q-1 2 ⌋ 1 1 t dt = log(⌊ q -1 2 ⌋) So: N -1 h=1 min(N, 1 2 uh ) ≤ ⌊ N -1 q ⌋ + 1 4N + 2q log(⌊ q -1 2 ⌋) ≤ N q + 1 (4N + 2q log q) ≤ N q + C 0 N q (4N + 2q log q) because q ≤ C 0 N ≤ 4(1 + C 0 )(N 2 + N log q)
This finishes the proof of Subsublemma 7.

⊓ ⊔

In the following we suppose that r is rational. So αr is irrational, so by Dirichlet's principle ([11]) we know that there exist two coprime integers q r ≤ 2Nr αc(b-a) and p r such that |2αrcq rp r | ≤ αc(b-a)

2Nr . By Subsublemma 7 with C 0 = 2 αc(b-a) and Equation (6) we deduce:

|S r,k (e c )| 2 ≤ 1 N r + 8(1 + C 0 ) N 2 r N 2 r q + N r log q r ≤ 1 N r + 8(1 + C 0 ) q r + 8(1 + C 0 ) log q r N r
As N r ---→ r→0 +∞ and log qr Nr ≤ log(C0Nr)

Nr

---→ r→0 0, it remains to prove that q r ---→ r→0 +∞.

We have:

p r q r ≥ 2αrc - αc(b -a) 2N r We have N r ≥ ( b r -1) -( a r + 1) -1 = b-a-r r
. We suppose without loss of generality that r ≤ b-a 2 so N r ≥ b-a 2r , so p r q r ≥ 2αrcαrc > 0, so p r ≥ 1. We deduce: Now let:

1 q r ≤ p r q r ≤ 2αrc + 1 N r q r ≤ 2αrc + 1 N r So q r ≥
G g r (ω) = card{X ∈ A r , B r -m | s g ′ (rX), g(rX) r m = ω} N r -m .
By Lemma 1 we have

F g r (ω) -G g r (ω) ---→ r→0 r∈Q 0. (9)
As y iy i-1 ≤ 1 n and α → pinf α (ω) and α → psup α (ω) are two piecewise affine functions which slope is between -m and 0, we have pinf yi-1 (ω) ≤ pinf yi (ω)+ m n and psup yi-1 (ω) ≤ psup yi (ω) + m n . So:

n i=1 [y i-1 , y i ) × [pinf yi (ω) + m n , psup yi (ω)) ⊂ P I(ω) ⊂ n i=1 [y i-1 , y i ] × [pinf yi (ω), psup yi (ω) + m n ) (12) Let F n,r = H r n i=1 [y i-1 , y i ) × [pinf yi (ω) + m n , psup yi (ω)) , F ′ n,r = H r n i=1 [y i-1 , y i ] × [pinf yi (ω), psup yi (ω) + m n ) .
So by Equation ( 12): F n,r ≤ H r (P I(ω)) ≤ F ′ n,r . By summing equations of the form (11) we obtain:

F n,r ---→ r→0 r∈Q n i=1 g ′-1 (y i ) -g ′-1 (y i-1 ) b -a F L yi (ω) - m n F ′ n,r ---→ r→0 r∈Q n i=1 g ′-1 (y i ) -g ′-1 (y i-1 ) b -a F L yi (ω) + m n Let F ′′ n = n i=1 g ′-1 (y i ) -g ′-1 (y i-1 ) b -a F L yi (ω).
(lim

r→0 r∈Q F n,r ) -F ′′ n = - n i=1 g ′-1 (y i ) -g ′-1 (y i-1 ) b -a m n = - n i=1 1 2α (y i -y i-1 ) b -a m n = - m(α e -α b ) 2α(b -a) 1 n Similarly (lim r→0 r∈Q F ′ n,r ) -F ′′ n = m(α e -α b ) 2α(b -a) 1 n .
Let z i = g ′-1 (y i ), we have

F ′′ n = n i=1 (z i -z i-1 ) F L g ′ (zi) (ω) b -a which is a Riemann sum of x → F L g ′ (x) (ω) b-a , but t → F L t (ω) is continuous ([3]
), so we have by [12, Chap. 5]:

F ′′ n ----→ n→∞ 1 b -a b a F L g ′ (x) (ω)dx
Let ε > 0, there exists N 1 such that for all n > N 1 we have

F ′′ n - 1 b -a b a F L g ′ (x) (ω)dx ≤ ε 3 .
There exists N 2 such that for any n > N 2 we have

m(α e -α b ) 2α(b -a) 1 n < ε 3
Let N = max(N 1 , N 2 ) + 1. There exists R 1 > 0 such that for any rational r < R 1 we have:

|F N,r -(F ′′ N - m(α e -α b ) 2α(b -a) 1 N )| ≤ ε 3 .
There exists R 2 > 0 such that for any rational r < R 2 we have:

|F ′ N,r -(F ′′ N + m(α e -α b ) 2α(b -a) 1 N )| ≤ ε 3 .
Suppose that r < min(R 1 , R 2 ).

We have:

H r (P I(ω)) ≥ F n,r ≥ F ′′ N - m(α e -α b ) 2α(b -a) 1 N - ε 3 ≥ F ′′ N - ε 3 - ε 3 ≥ 1 b -a b a F L g ′ (x) (ω)dx - ε 3 - ε 3 - ε 3 = 1 b -a b a F L g ′ (x) (ω)dx -ε Similarly H r (P I(ω)) ≤ F ′ n,r ≤ 1 b -a b a F L g ′ (x) (ω)dx + ε, so H r (P I(ω)) ---→ r→0 r∈Q 1 b -a b a F L g ′ (x) (ω)dx
With (9) and (10) this proves Theorem 1.

⊓ ⊔

A.3 Proof of Theorem 3

It is easy to see that:

l(p, g, r) - (b -a) m ω∈Pm p(ω)F ′ g r (ω) ---→ r→0 0
where

F ′ g r = card{X ∈ A r , B r -m ∩ (A r + mZ) | ω g X,r,m = ω} ⌊ Br-m-Ar m ⌋ .
Consider again the curve defined by g(x) = αx 2 for α / ∈ Q. The proof of previous section can be extended to prove: (5)

F ′ g r ---→
Let F n the n-th Farey of order m. We know that x → F L x (ω) is affine on the intervals [F i , F i+1 ] ( [START_REF] Tajine | Digital segments and Hausdorff discretization[END_REF]). So for each i there exists u i , v i we have F L x (ω) = u i x + v i .

Let k α the smallest integer k such that 2αa ≤ F k and l α the biggest integer l such that F l ≤ 2αb. We deduce that ⊓ ⊔

Fig. 1 .

 1 Fig. 1. The 16 patterns of size m = 4. Only the encircled one are not digital segments.

Fig. 2 .

 2 Fig. 2. Comparison of the discretization of the curve and the discretization of its tangent : here we have ω g X,r,m = s g ′ (rX), g(rX) r

ATheorem 3 .

 3 local estimator is given by a weight function p from the set P m of patterns of size m to R. The estimated length of the curve y = g(x) where g : [a, b] → R at resolution r is given by: l(p, g, r) = r ⌊ Br -m-Ar m ⌋ k=0 p(ω g Ar+km,r,m ). Let a, b such that 0 ≤ a < b. The length estimated by a local estimator of a parabola y = αx 2 , x ∈ [a, b], (α ≤ 1 2b

1 4 (

 4 4p(ω ) + 5p(ω 2 ) + 2p(ω 3 ) + 2p(ω 4 )) = 7.1

2 Corollary 3 . 1 √ 2 x 2 1 √ 2 .

 2312212 +Cα) ∂α = 2Bα + C, so 2(b 3a 3 ) = 0 which is impossible if b > a. So the hypothesis that L real (α) = L est (α) for an infinite number of irrational α is absurd. ⊓ ⊔ Let a, b such that 0 ≤ a < b. The length estimated by a local estimator of a parabola y = αx 2 , x ∈ [a, b], does not converge when the resolution is rational and tends to zero, to the length of the curve for almost all α ∈ [0, 1 2b ]. Numerical application: Again, we take the curve y = g(x) = for x between a = 0 and b = Suppose that we consider the local estimator Chamfer 5-7-11 ([9]) with m = 2, p(000) = 2, p(001) = p(011) = 22 10 , p(012) = 28 10 . With Equation (13), we can prove that the estimation of the length of the parabola given by this local estimator converges to L est = 23 40 √

Fig. 4 .

 4 Fig. 4. Figure showing Convergence Speed of the Chamfer 5-7-11 to its limits for the parabola y = 1

  But |1e(β)| = |e( β 2 )(e(-β 2 )e( β 2 ))| = 2| sin(πβ)|. Moreover sin(πβ) ≥ 2 β (because sin(πx) ≥ 2x for x ∈ [0, 1 2 ]). So: With the clear inequality | v k=u e(βk)| ≤ vu + 1, it ends the proof of Subsublemma 6.

A. 2

 2 ends the proof of Sublemma 5. ⊓ ⊔ To finish the proof of Lemma 3 we must prove that S r,k (χ I ) ---→ r→0 r∈Q µ(I) where χ I is the indicator function of I. We have S r,k (e 0 ) = 1 and by Sublemma 5 S r,k (e c ) ---→ r→0 r∈Q0 for c = 0, so by Weyl's strategy (see for example[START_REF] Tajine | On local definitions of length of digital curves[END_REF] or[4, Appendix A.1]) we can prove Lemma 3.⊓ ⊔ Proof of Theorem 1

F

  L g ′ (x) (ω)dx.

F+ u lα αx 2 + v lα x b F lα 2α = 1 i=kα u i x 2 + 2 C 1 a 2 =

 22α12212 L g ′ (x) (ω)dx = F kα 2α a (u kα-1 (2αx) + v kα-1 )dx + (2αx) + v i )dx+ b F lα 2α (u lα (2αx) + v lα )dx = u kα-1 αx 2 + v kα-1 x A α,ω α + B α,ω α + C α,ωwhereA α,ω = 1 4 u kα-1 F 2 kα + 2v kα-1 F kα + lα-2v i x Fi+1 Fi u lα F 2 lα -2v lα F lα B α,ω = u lα b 2u kα-1 a α,ω = v lα bv kα-As k α and l α are constant on the intervals which contains no reals Fi 2a and Fi 2b , we can partition the interval [0,1 2b ] in a finite number of intervals (I k ) 0≤k≤n such that the functions α → A α,ω , B α,ω , C α,ω are constant on each interval I k .By (5), we have:lim r→0 r∈Q l(p, g, r) = A α α + B α α + C α (13)whereA α = 1 m ω∈Pm p(ω)A α,ω , B α = 1 m ω∈Pm p(ω)B α,ω , C α = 1 m ω∈Pm p(ω)C α,ω So L est (α) = lim r→0 r∈Q l(p, g, r) is of the form A α + Bα + C on each interval I k . Let L real (α) the true length of the parabola curve {(x, αx 2 ) | x ∈ [a, b]}. We have:Suppose that L real (α) = L est (α) for an infinite number of irrational α then there exists an interval I k of the previous partition of [0,1 2b ] such that L real (α) = L est (α) for an infinite number of irrational α ∈ I k . On I k we know that L est (α) has the form A α + Bα+ C. The functions α → αL real (α) and α → α( A α + Bα+ C) are holomorphic in a open set of C containing [0,1 2b ] and are equal for an infinite number of α ∈ I k ⊂ [0,1 2b ] so by Theorem on the zeros of holomorphic functions [8, Cha. 10] they are equal on [0,1 2b ]. So:αL real (α) = A + Bα 2 + Cα for all α ∈ [0real (α) ∂α = b 1 + (2αb) 2a 1 + (2αa) ba + 2(b 3a 3 )α 2 + o(α 2 ) when α → 0 22But ∂(A+Bα 2 +Cα) ∂α = 2Bα + C, so 2(b 3a 3 ) = 0 which is impossible if b > a. So the hypothesis that L real (α) = L est (α) for an infinite number of irrational α is absurd.

  1 2b ] such that L real (α) = L est (α) for an infinite number of irrational numbers α ∈ I k . On I k we know that L est (α) has the form A α + Bα + C. The functions α → αL real (α) and α → α( A α + Bα + C) are holomorphic in a open set of C containing [0, 1 2b ] and are equal for an infinite number of α ∈ I k ⊂ [0, 1 2b ]. So by Theorem on the zeros of holomorphic functions [8, Cha. 10] they are equal on [0, 1 2b ]. So:

  , A., Rudnick, Z.: Uniform distribution. In Granville, A., Rudnick, Z., eds.: Equidistribution in Number Theory, An Introduction.

	Springer (2007) 1-13
	6. Vinogradov, I.M.: Elements of Number Theory, 5th rev. ed. Dover (1954)
	7. Davenport, H.: Multiplicative Number Theory, 2nd ed. Springer-Verlag, New York
	(1980)
	8. Rudin, W.: Real and complex analysis. McGraw-Hill, New York (1966)
	9. Borgefors, G.: Distance transformations in digital images. Computer Vision,
	Graphics, and Image Processing 34(3) (1986) 344-371
	10. McIlroy, M.D.: A note on discrete representation of lines. ATT Tech. J. 64(2)
	(1985) 481-490
	11. Wikipedia: (2008) http://en.wikipedia.org/wiki/Pigeonhole principle ac-
	cessed 14-November-2008.
	12. Munroe, M.E.: Measure and integration, 2nd ed. Addison-Wesley (1971)

In fact it is proved that P I(ω) is a triangle or a quadrangle.

Formulas (1),(2) do not define pinf and psup for α = α b , αe, we define these values just by continuity.

We have by definition of P I(ω) (and because ⌊ g(rX) r ⌋ = 0):

For any subset E of R 2 , we define:

The function g ′ is linear, so in particular is a bijection, we denote by g ′-1 its reciprocal function. We suppose that α > 0, so that g ′ is an increasing function. (g ′ (rX), g(rX) r

If we apply Lemma 3 with k = 0 to the piece of the curve y = g(x) restricted to the domain g ′-1 (α 1 ) ≤ x ≤ g ′-1 (α 2 ). we find:

N r H r (E)

We deduce that:

In [10] it is shown that

where α → pinf α (ω) and α → psup α (ω) are two piecewise affine functions which slope is between -m and 0.


Gilles Chabert
email: gilles.chabert@ensieta.frluc.jaulin@ensieta.fr

Luc Jaulin

Computing the Pessimism of Inclusion Functions

Computing the pessimism" means bounding the overestimation produced by an inclusion function. There are two important distinctions with classical error analysis. First, we do not consider the image by an inclusion function but the distance between this image and the exact image (in the set-theoretical sense). Second, the bound is computed over a infinite set of intervals. To our knowledge, this issue is not covered in the literature and may have a potential of applications. We first motivate and define the concept of pessimism. An algorithm is then provided for computing the pessimism, in the univariate case. This algorithm is general-purpose and works with any inclusion function. Next, we prove that the algorithm converges to the optimal bound under mild assumptions. Finally, we derive a second algorithm for automatically controlling the pessimism, i.e., determining where an inclusion function is accurate.

Introduction

In this paper, we consider a continuous function f : R → R (the definition domain of f is assumed to be R for simplicity). The radius, the middle, the magnitude and the mignitude of an interval [x] are denoted by rad [x], mid [x], |[x]| and <[x]> respectively.

One fundamental tool that interval analysis provides is the notion of inclusion function (see, e.g., [START_REF] Ratschek | Computer Methods for the Range of Functions[END_REF][START_REF] Jaulin | Applied Interval Analysis[END_REF]). An inclusion function F is a mapping from IR (the set of intervals) to IR such that

∀[x] ∈ IR f ([x]) ⊆ F [x],
where f ([x]) denotes the set-theoretical image of [x] by f . An inclusion function allows to perform a safe evaluation of a function on a whole set of values and this addresses the question of reliability: thanks to inclusion functions, interval methods are robust to round-off errors, imprecision on input data, numerical truncatures, etc. Besides, the question of accuracy, i.e., whether the result is accurate or not, is also a crucial matter for numerical methods. Clearly, if the overestimation produced by the underlying inclusion function is really too large, the method will suffer from a lack of accuracy.

The accuracy issue has led people to design smart inclusion functions using, e.g., multi-precision arithmetic [START_REF] Revol | Motivations for an arbitrary precision interval arithmetic and the MPFI library[END_REF], Taylor models [START_REF] Makino | Taylor Models and Other Validated Functional Inclusion Methods[END_REF] or Bernstein expansions for polynomials [START_REF] Garloff | Lower bound functions for polynomials[END_REF]. See also [START_REF] Ratschek | Computer Methods for the Range of Functions[END_REF] for a survey on inclusion functions.

The purpose of this paper is to evaluate the accuracy of any given (inclusion isotone) inclusion function. This purpose can first be formulated as follows:

Problem 1. Given an inclusion function F and an interval [x], find a bound for

overestim[x] := rad F [x] -rad f ([x]).
If we consider that a sophisticated inclusion function necessarily involves more computations, this problem becomes relevant since it is useful to know whether it is worth the effort or not.

A first approach

A first property of inclusion functions connected to accuracy is called Lipschitzcontinuity [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF]. In particular, this property implies that the radius of F [x] goes to zero with the radius of [x], i.e., that the overestimation can be arbitrarily reduced by conveniently splitting the domains.

Definition 1 (Lipschitz-continuity of an inclusion function). An inclusion function F is said to be Lipschitz-continuous if for all interval [x] (0) ∈ IR, there exists a constant λ F ([x (0) ] such that

∀[x], [y] ⊆ [x] (0) q(F [x], F [y]) ≤ λ F ([x (0) ])q([x], [y])
where q is the Hausdorff distance:

q([x], [y]) = | mid [x] -mid [y]| + | rad [x] -rad [y]|.
The easiest way to bound the overestimation for a given interval [x] is to write:

overestim([x]) ≤ rad F [x].
This approximation makes sense if we assume that [x] is a perturbed value mid [x] by a small uncertainty rad [x] and that f is locally almost flat. In this way, the output error (rad f ([x])) can be neglected so that the overestimation can be identified to the radius of F [x]. Under these conditions, the following proposition (see [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF] Cor. 2.1.2) allows then to bound the overestimation:

Proposition 1. If F is Lipschitz-continuous then ∀[x] ∈ IR rad F [x] ≤ λ F ([x]) rad [x].
However, this estimation is not adapted for set computations, i.e., for situations where [x] does not describe a single perturbed value but a full range of possibilities. Indeed, in the latter case, there may be an important gap between the range of the overestimation and the range of F itself. Furthermore, this estimation is relevant when intervals have an extremely small width (this is why we usually remember a linear rate of improvement from Proposition 1).

A new approach

No theoretical tool seems available for precisely computing the overestimation of an arbitrary inclusion function. This is not a big surprise since this quantity usually strongly depends on both the expression of the function1 and the actual arguments.

We may therefore turn to numerical means. Unfortunately, from the numerical standpoint, Problem 1 has little sense in general, since an accurate computation of overestim[x] is likely to require more computations than an evaluation with the "best" inclusion function at our disposal.

Computing the overestimation can nevertheless be made meaningful with a slightly different point of view. Consider the two following facts:

-Due to the combinatorial effect of any branch & bound algorithm (see e.g., [START_REF] Kearfott | Rigorous Global Search: Continuous Problems[END_REF][START_REF] Van Hentenryck | Numerica: A Modeling Language for Global Optimization[END_REF][START_REF] Jaulin | Applied Interval Analysis[END_REF][START_REF] Benhamou | CLP(intervals) revisited[END_REF]) functions are often repeatedly evaluated with overlapping domains. Therefore, spending some time for analyzing offline the behaviour of a given inclusion function F may pay. -We are more interested by checking that the inclusion function satisfies some precision requirements globally than by determining the overestimation for a specific interval.

Based on these observations, the problem of computing the overestimation of an inclusion function can be reformulated as follows:

Problem 2. Given an inclusion function F and an interval [x] (0) , is the overestimation of F less than a user-defined threshold ε for any

[x] ⊆ [x] (0) ?
Note that the answer is not as simple as computing overestim[x] and checking overestim[x] < ε. The reason is that the overestimation is not inclusion isotonic, i.e.,

[y] ⊆ [x] =⇒ overestim[y] ≤ overestim[x].
This can be shown on a simple counterexample:

Example 1. Let f : x → sin(πx/2) + x and consider the natural extension F of f .

On the one hand, we have

F [-1, 5] = sin([-π/2, 5π/2]) + [-1, 5] = [-2, 6],
which exactly matches f ([-1, 5]) since f (-1) = -2 and f (5) = 6. Hence, overestim[-1, 5] = 0.

On the other hand,

F [1, 2] = sin([π/2, π]) + [1, 2] = [0, 3] whereas f ([1, 2]) ∼ [2.0, 2.2].
Solving Problem 2 requires the ability to calculate the overestimation for a whole set of possible input intervals. For convenience, this maximal overestimation will be called the pessimism of F in the sequel. Hence, the question amounts to : given an inclusion function F and an interval [x], is there an algorithm for computing

pessim[x] := max [y]⊆[x] overestim[y]? (1)
We propose in the two next sections such an algorithm. For the sake of clarity, it is split into two subalgorithms pessim + and pessim -that computes an upper and lower bound of the pessimism respectively; each of them being treated in a separate section. The convergence property of both subalgorithms will be stated.

We will introduce in Section 5 a more high-level algorithm for controlling the pessimism.

Pessimism upper bound

Starting now, we consider a fixed inclusion function F that satisfies inclusion isotonicity, i.e., [x]

⊆ [y] =⇒ F [x] ⊆ F [y].
We present in this section the pessim + algorithm that upwardly bounds (1), i.e., the maximal overestimation produced by F on a given interval [x].

First of all, the pessim + algorithm creates a uniform subdivision of [x] by a sequence of (n + 1) points

x 1 = lb([x]) , . . . , x i = x 1 + i -1 n rad [x] , . . . , x n+1 = ub([x]),
where lb([x]) and ub([x]) stands for the lower and upper bound of [x] respectively. The number n is (besides [x]) a parameter of the pessim + algorithm. We will call a k-block an interval [x i , x i+k ] of the subdivision.

In addition, the pessim + algorithm computes an inner approximation of the image of f on every k-block (1 ≤ k ≤ n). We will denote by range -([x i , x i+k ]) such approximation. In a word:

range -([x i , x i+k ]) ⊆ f ([x i , x i+k ]).
Note that the postscript font is used (range -, pessim + ) to emphasize that the quantity is computed, contrary to overestim which is purely theoretical.

The key idea of the algorithm relies on the following simple observation. Any interval [y] included in [x] satisfies at least one of the three conditions:

1. [y] ⊆ [x 1 , x n ] 2. [y] ⊆ [x 2 , x n+1 ] 3. [x 2 , x n ] ⊆ [y]
Assume by induction that we know how to bound overestim[y] for any [y] that enter in the two first cases, then, only the third case is left to be treated.

Let us now focus on the third case. We have

[x 2 , x n ] ⊆ [y] ⊆ [x 1 , x n+1 ].
On the one hand,

range -([x 2 , x n ]) ⊆ f ([x 2 , x n ]) ⊆ f ([y]).
On the other hand, by inclusion isotonicity,

F [y] ⊆ F [x 1 , x n+1 ].
Note that both inclusions are precise if the subdivision is fine, i.e., if n is large. It follows from the two previous inclusions that

overestim[y] = rad F [y] -rad f ([y]) ≤ rad F [x 1 , x n+1 ] -rad range -([x 2 , x n ]).
Therefore, if we know how to estimate the pessimism for (n-1)-blocks, we know how to estimate the pessimism for n-blocks, i.e., [x]. This recursive property implies a combinatory but, fortunately, this particular type of combinatory can be tackled by dynamic programming (see [START_REF] Cormen | Introduction to Algorithms[END_REF][START_REF] Bellman | Dynamic Programming[END_REF]) in polynomial time. More precisely, the worst-case time complexity is in fact O(n 2 ), and the space complexity is O(n). We just have to start with 1-blocks and 2-blocks, and then proceed to blocks of greater size by applying the idea given above.

Let us now detail the algorithm. We define two n-sized arrays denoted by P + (for Pessimism upper estimation), and R -(for Range inner estimation). P + is an array of reals while R -is an array of intervals.

After the k th turn in the outer loop of pessim + ([x], n):

-P + [i] contains pessim + ([x i , x i+k ], k), -R -[i] contains range -([x i , x i+k-1 ]).
Notice that the block size is shifted by 1 in the invariant related to R -. This explains why 1-blocks does not require an initialization in the algorithm.

function pessim + (interval [x], integer n) for i from 1 to n -1 // Initialization of 2-blocks | R -[i] ← f (mid [x i , x i+1 ]) // will be improved in §2.2 | P + [i] ← rad F [x i , x i+2 ]
// will be improved in §2.2

for k from 3 to n | for i from 1 to n -k + 1 // Initialization of k-blocks | | R -[i] ← R -[i] ∪ R -[i + 1] | | P + [i] ← max P + [i], P + [i + 1], rad F [x i , x i+k ] -rad R -[i + 1] return P + [1] endfunc 2.
⊆ [y] =⇒ F [x] ⊆ F [y]).
The pessimism estimation tends to the actual maximal overestimation when the subdivision size tends to infinity, i.e.,

pessim + ([x], n) ----→ n→∞ max [y]⊆[x] overestim[y].
Proof. We already know that for any n,

pessim + ([x], n) ≥ max [y]⊆[x] overestim[y].
We need to prove that ∀ε > 0, there exists n 0 such that for any n ≥ n 0 ,

pessim + ([x], n) -max [y]⊆[x] overestim[y] < ε,
or, in other words, that

∃[y] ⊆ [x] pessim + ([x], n) -overestim[y] < ε. (2)
Let us fix ε > 0.

First of all, since a continuous function on a closed interval is also uniformly continuous, there exists n 0 such that

∀n ≥ n 0 , ∀x, y ∈ [x], |x -y| ≤ 2/n rad [x] =⇒ |f (x) -f (y)| < ε/2. (3)
Furthermore, we can chose n 0 sufficiently large so that

n 0 ≥ 2λ f ([x])/ε (4)
is also satisfied. We take now n ≥ n 0 , and prove (2) by induction. Base case: ∀i ∈ [1, n -1], Proposition 1 implies

F [x i , x i+2 ] ≤ λ f ([x])2/n < ε so that for every 2-block [x i , x i+2 ] in [x]
we have (by inclusion isotonicity)

∃[y] ⊆ [x i , x i+2 ] pessim + ([x i , x i+2 ], 2) -overestim[y] < ε.
Assume by induction that every k-block in [x] satisfy (2), i.e.,

∃[y] ⊆ [x i , x i+k ] pessim + ([x i , x i+k ], k) -overestim[y] < ε. (5)
We shall prove that the inequality also holds for (k + 1). Consider a (k + 1)-block

[x i , x i+k+1 ] ⊆ [x]. Let us first prove that ∃[y] ⊆ [x i , x i+k+1 ] such that rad F [x i , x i+k+1 ] -rad range -([x i+1 , x i+k ]) -overestim[y] < ε. ( 6
)
To this end, consider an arbitrary interval [y] satisfying

[x i+1 , x i+k ] ⊆ [y] ⊆ [x i , x i+k+1 ].
On the one hand, by Definition 1,

q(F [x i , x i+k+1 ], F [x i+1 , x i+k ]) < λ f ([x]) q([x i , x i+k+1 ], [x i+1 , x i+k ]) =⇒ rad F [x i , x i+k+1 ] -rad F [x i+1 , x i+k ] < λ f ([x])× (rad [x i , x i+k+1 ] -rad [x i+1 , x i+k ]) =⇒ rad F [x i , x i+k+1 ] -rad F [x i+1 , x i+k ] < λ f ([x])/n so that, with (4), rad F [x i , x i+k+1 ] -rad F [x i+1 , x i+k ] < ε/2 (7) which implies rad F [x i , x i+k+1 ] -rad F [y] < ε/2. ( 8
)
On the other hand, let us denote by y + the point where f is maximized in

[y] ⊆ [x i , x i+k+1
]. The distance between y + and the closest point to y + among the midpoints of all 1-blocks included in [x i+1 , x i+k ] is necessarily less than 2/n rad [x]. The same holds for the point y -where f is minimized. Then, thanks to (3), we have

f (y + ) -ub(range -([x i+1 , x i+k ])) < ε/2
(ub stands for "upper bound") and

lb(range -([x i+1 , x i+k ])) -f (y -) < ε/2 (lb stands for "lower bound"), which means that rad f ([y]) -rad range -([x i+1 , x i+k ]) < ε/2. (9) Now, rad F [x i , x i+k+1 ] -rad range -([x i+1 , x i+k ]) -overestim[y] = rad F [x i , x i+k+1 ] -rad range -([x i+1 , x i+k ]) -rad F [y] -rad f ([y]) = rad F [x i , x i+k+1 ] -rad F [y] + rad f ([y]) -rad range -([x i+1 , x i+k ])
< ε (by combining ( 8) and ( 9)), so that ( 6) is proven. Finally, by definition,

pessim + ([x i , x i+k+1 ], k + 1) := max    pessim + ([x i , x i+k ], k) pessim + ([x i+1 , x i+k+1 ], k) rad F [x i , x i+k+1 ] -rad range -([x i+1 , x i+k ])
By applying ( 5) and ( 6), there exist [y] (1) , [y] (2) and [y] (3) in [x i , x i+k+1 ] such that

     pessim + ([x i , x i+k ], k) -overestim[y] (1) < ε pessim + ([x i+1 , x i+k+1 ], k) -overestim[y] (2) < ε rad F [x i , x i+k+1 ] -rad range -([x i+1 , x i+k ]) -overestim[y] (3) < ε Hence, there exists [y] ⊆ [x i , x i+k+1 ] such that pessim + ([x i , x i+k+1 ], k + 1) -overestim[y] < ε.
Therefore, the inequality ( 2) is true for (k+1)-blocks, which completes the proof.

Some improvements

Initializations in the first loop of pessim + can be made more efficient, without however changing the slow (linear) rate of convergence in general.

First, R -[i] was set to the image of the midpoint of [x i , x i+1 ], as an inner approximation of f on this 1-block. Clearly, this approximation is made better (i.e., larger) by introducing more sample points in the corresponding interval. However, the overall accuracy remains linearly dependent of the subdivision size (see the proof of Proposition 2).

Although having an influence on the accuracy, the sampling size is therefore not a decisive parameter. On the contrary, the second improvement we propose can speed up the convergence in some situations. Remember that

P + [i] is set to F [x i , x i+2 ],
as an outer approximation of the pessimism on the i th 2-block.

Assume now that F is defined as the natural extension of some differentiable expression of f . The overestimation on an interval can also be upwardly approximated using the two next formulae. Since both formulae are likely to be precise with small intervals (i.e., 2-blocks) their use may strongly improve the initialization of P + .

First, by Proposition 1,

rad F [x] ≤ λ F ([x]) rad [x].
In the case of the natural inclusion function, the constant λ F ([x]) can be automatically computed (see [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF] Th. 2.1.1). Second, by the mean value theorem,

rad f ([x]) ≥<F ′ [x]> [x],
where <F ′ [x]> denotes the mignitude of an interval evaluation of the derivative. Hence, rad

F [x] ≤ λ F ([x])/ <F ′ [x]> rad f ([x]). ( 10
)
and since rad f

([x]) ≤ rad F [x], rad F [x] -rad f ([x]) ≤ σ[x] rad F [x] with σ[x] := ( λ F ([x]) <F ′ [x]> -1). ( 11
)
It follows that the pessimism on [x] is lower than σ[x] rad F [x] and P + [i] should rather be initialized as follows:

P + [i] ← max(σ[x], 1) × (rad F [x]). (12)
In some cases, this simple trick makes the algorithm behavior more satisfactory. Consider the function f (x) = x and the natural inclusion function

F [x] = [x],
which is minimal. If the pessimism on each 2-block [x i , x i+2 ] is identified to rad F [x i , x i+2 ], the returned value is 2/n. The linear rate of convergence prevents from getting an accurate bound. With the help of ( 12), the best bound (i.e., 0) is immediately obtained since λ F ([x]) =<F ′ [x]>= 1.

Pessimism lower bound

An algorithm for downwardly approximating the pessimism is built with a very similar induction-based reasoning. Consider a subdivision of [x] with the same notations as before. In the case of (n

+ 1)-blocks, if [x 2 , x n ] ⊆ [y] ⊆ [x 1 , x n+1 ] then overestim[y] = rad F [y] -rad f ([y]) ≥ rad F [x 2 , x n ] -rad range + ([x 1 , x n+1 ])
where range + stands for an outer approximation of the range of f .

In the following algorithm, P -[i] is a lower bound of the pessimism of F on the i th k-block [x i , x i+k ], while R + [i] contains an outer approximation of the range of f on the same block.

The base case (2-blocks) is handled as follows.

-R + [i] is initialized with an union of 1-blocks image by F . It could also be initialized with the image of the i th 2-block by any (sharp) inclusion function. -P -[i] is set to the overestimation on one particular interval, which is the i th 2-block itself. Again, this bound could be improved by considering a multiplicity of subintervals instead.

function pessim -(interval [x], integer n) for i from 1 to n -1 | R + [i] ← F [x i , x i+1 ] ∪ F [x i+1 , x i+2 ] | P -[i] ← max 0, rad F [x i , x i+2 ] -rad R + [i] for k from 3 to n | for i from 1 to n -k + 1 | | R + [i] ← R + [i] ∪ R + [i + 1] | | P -[i] ← max P -[i], P -[i + 1], rad F [x i+1 , x i+k-1 ] -rad R + [i] return P -[1] endfunc
3.1 Properties of the pessimism lower bound Proposition 3. Under the assumptions of Proposition 2, we have

pessim -([x], n) ----→ n→∞ max [y]⊆[x] overestim[y].
Proof. The proof being close to Proposition 2's, only a sketch will be given. As before, we prove that ∀ε > 0, there exists n 0 such that ∀n ≥ n 0 and ∀k ≤ n

(k ≥ 2), ∀i ≤ n-k+1 ∃[y] ⊆ [x i , x i+k ] overestim[y]-pessim -([x i , x i+k ], k) < ε. (13)
Let us fix ε > 0 and consider again n ≥ n 0 where n 0 satisfies (3) and (4) except that ε/2 is replaced by ε/3.

Base case (

k = 2). Since ∀i ≤ n -1, 0 ≤ pessim -([x i , x i+2 ], 2) ≤ overestim([x i , x i+2 ]) ≤ rad F ([x i , x i+2 ]) < ε/3 then (13) is verified with [y] := [x i , x i+2 ].
Induction step (k + 1). We consider again an arbitrary interval [y] satisfying

[x i+1 , x i+k ] ⊆ [y] ⊆ [x i , x i+k+1 ].
On the one hand, (7) also implies rad

F [y] -rad F [x i+1 , x i+k ] < ε/3. (14)
On the other hand, the distance between the points y + and x + where f is maximized over [y] and [x i , x i+k+1 ] respectively is necessarily less than 2/n rad [x]. The same distance property holds for the points y -and x -minimizing f . Hence,

rad f ([x i , x i+k+1 ]) -rad f ([y]) < ε/3. (15)
Furthermore,

range + ([x i , x i+k+1 ]) ⊆ i+k j=i F[x j , x j+1 ]. Since ∀j, i ≤ j ≤ i + k, overestim([x j , x j+1 ]) ≤ rad F [x j , x j+1 ] < ε/3 then rad range + ([x i , x i+k+1 ]) -rad f ([x i , x i+k+1 ]) < ε/3. (16)
Now, 14), ( 15) and ( 16))

overestim[y] -rad F [x i+1 , x i+k ] -rad range + ([x i , x i+k+1 ]) = rad F [y] -rad f ([y]) -rad F [x i+1 , x i+k ] -rad f ([x i , x i+k+1 ])+ rad f ([x i , x i+k+1 ]) -rad range + ([x i , x i+k+1 ]) = rad F [y] -rad F [x i+1 , x i+k ] + rad range + ([x i , x i+k+1 ]) -rad f ([x i , x i+k+1 ]) + rad f ([x i , x i+k+1 ]) -rad f ([y]) < ε (by combining (
The end of the proof is left to the reader.

Relative pessimism

One could find more relevant to compute the relative pessimism, i.e., max

[y]⊆[x],rad f ([y]) =0 rad F [y]/ rad f ([y]). ( 17
)
Our approach can be adapted for such a purpose. We shall give a brief overview of this variant. The induction step resorts naturally to the following inequalities:

if [x 2 , x n ] ⊆ [y] ⊆ [x 1 , x n+1 ] then rad F [x 2 , x n ] rad range + (f, [x 1 , x n+1 ]) ≤ rad F [y] rad f ([y]) ≤ rad F [x 1 , x n+1 ] rad range -(f, [x 2 , x n ])
.

Let us focus on the base case. For an upper approximation of the relative pessimism, the base case can be tackled thanks to [START_REF] Ratschek | Computer Methods for the Range of Functions[END_REF]. For the lower approximation, we need to introduce a new formula. Notice that, with Proposition 1 in view, the Lipschitz constant λ F ([x]) can be defined recursively by applying classical formulae like: rad

([x] ± [y]) ≤ rad [x] + rad [y], rad ([x] × [y]) ≤ |[y]| rad [x] + |[x]| rad [y], rad φ([x]) ≤ |φ ′ ([x])| rad [x], . . .
It happens that inequality signs can be reversed by substituting mignitudes to magnitudes:

rad

([x] ± [y]) ≥ rad [x] + rad [y], rad ([x] × [y]) ≥<[y]> rad [x]+ <[x]> rad [y], rad φ([x]) ≥<φ ′ ([x])> rad [x], . . .

Hence, one can also compute for any interval

[x] a constant µ F ([x]) that verifies rad F ([x]) ≥ µ F ([x]) rad [x],
so that the base case can be handled with

µ F ([y]) |F ′ [y]| ≤ rad F [y] rad f ([y]) ≤ λ F ([y]) <F ′ [y]> .

Pessimism control

Now, as we know how to estimate the pessimism, the natural next step is to control the pessimism of an inclusion function over a (possibly large) initial interval [x]. More precisely, the goal is to split [x] into sub-intervals where the pessimism is guaranteed to meet some requirements.

Such a question needs however some precaution, simply because computing the pessimism does not cancel the pessimism. Consider for instance the function f (x) = x -x and the natural inclusion function

F [x] = [x] -[x].
If one requires the pessimism to be lower than 10 -5 in [x] = [0, 1], the best algorithm ever would anyway yield 2 × 10 5 intervals since in this case the overestimation of

F [x] is always 2 × rad [x].
What follows must therefore be applied in situations where the requirements are "compatible" with the inclusion function.

Furthermore, the algorithm should detect blocks (i.e., sub-intervals) for which the pessimism is small enough, instead of returning a single value corresponding to the pessimism for the overall interval. This would avoid redundant computations in a test and bisect strategy.

The goal is to adapt the pessim + algorithm in such a way that a sequence of "accurate" blocks is returned instead of the overall pessimism: each block in this sequence is either "accurate" or a 1-block [x i , x i+1 ] that has to be further analyzed. We must generate a sequence of minimal size and keep the quadratic Let us deal now with a more sophisticated example. Assume f (x) = cos(x) sin(x) + cos(x) exp(-x) + sin(x) exp(-x).

One may wonder which term should be factored out when using interval arithmetic, i.e., which of the following inclusion functions is sharper in general: Of course, computing the pessimism of each inclusion function on [0, 10] is not really relevant. To make a fair comparison between these inclusion functions, we have run the pessim-ctrl algorithm with different (exponentially decreasing) values for ε. If the partition size (i.e., the number of splits necessary to achieve the desired precision) with an inclusion function is always smaller than the partition size with another one, then the first function can be considered (experimentally) as sharper. Of course, this comparison must be interpreted "in average" since for one peculiar interval, we cannot predict which of them entails the biggest overestimation.

Results are depicted in Figure 1.

Conclusion

This paper is a first exploration of a new concept related to inclusion functions, called pessimism computation. We have given algorithms (pessim + and pessim -) for bounding the overestimation over a infinite set of possible input intervals. These algorithms are valid for any type of (inclusion isotone) inclusion functions. If, in addition, the inclusion function is Lipschitz-continuous (which is most of the time true), the algorithms converge to the optimal result (see Proposition 2 and 3). However, the convergence rate is only linear.

F 1

 1 [x] = cos[x] × (sin[x] + exp(-[x])) + sin[x] × exp(-[x]), F 2 [x] = sin[x] × (cos[x] + exp(-[x])) + cos[x] × exp(-[x])), F 3 [x] = exp(-[x]) × (cos[x] + sin([x])) + cos[x] × sin[x].We assume that intervals [x] in argument always satisfy [x] ⊆ [0, 10].

Fig. 1 .

 1 Fig.1. Number of necessary splits to achieve a desired precision. Each curve is associated to an inclusion function. A curve maps (with interpolated values) the partition size obtained with the pessim-ctrl algorithm to the input parameter (of maximal pessimism) ε. The input interval [x] is set to [0, 10]. The inclusion function F1 seems to be more sharp with any value of ε; the ratio between F1's values and the others' even decreases with ε (down to 78% with ε = 2-7 ).

  1 Properties of the pessimism upper bound Proposition 2. Let F be a Lipschitz-continuous inclusion function that satisfies inclusion isotonicity (i.e., [x]

Table 1 .

 1 Let us first illustrate numerically the behavior of pessim + and pessim -(both are merged into a unique algorithm). We have considered f (x) = sin(x) + x andF [x] = sin[x] + [x] with [x] = [0,[START_REF] Ratschek | Computer Methods for the Range of Functions[END_REF]. Results obtained are summed up in the following table. We can check that the precision goes linearly with the subdivision size n while the computation time goes quadratically (notice that n grows exponentially). The program has been run on a standard laptop. The upper and lower approximation seem to converge towards 2.0 which is the actual pessimism of F on [x]: the interval with the maximal overestimation 2.0 being [π/2, 3π/2]. Lower and upper approximation of the pessimism.

	6 First experiments
	n pessim -pessim + time (in sec)
	2 0.	6.	∼0
	4 0.700764 4.2787	∼0
	8 0.799236 3.20395 ∼0
	16 1.27016	2.58151 0.004
	32 1.6413	2.31233 0.004
	64 1.83253	2.15608 0.020001
	128 1.91915	2.07795 0.060004
	256 1.96015	2.039	0.216013
	512 1.98035	2.01951 0.884055
	1024 1.9902	2.00976 3.47222
	2048 1.99511	2.00488 14.0449
	4096 1.99756	2.00244 56.2235
	8192 1.99878	2.00122 223.418

The expression of the function comes into play providing that this expression is somehow involved in the definition of the inclusion function. As an example, consider the mean value form (see[START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF] p.51). If an enclosure of the derivative is computed with automatic differentiation then the overestimation depends on the expression of f .

For simplicity, we store here the partition in a simple list named partition. However, a tree structure might sometimes be more adapted for practical uses.

complexity at the same time. To this end, we introduce an extra array B (for Block) of integers. In return, B[i] shall contain the size k of the largest "accurate" block starting from x i (and 0 if none).

The algorithm pessim + can then be reimplemented as follows:

The pessim-ctrl algorithm can finally be given. This algorithm generates a sequence of consecutive intervals that forms a partition 2 of the input domain [x]. On each interval of this partition, the inclusion function F is proven to be accurate (according to our absolute criterion ε). After a call to pessimblk + , the array B is read forward and pessim-ctrl is only called recursively with 1-blocks where F is not accurate. Hence, no computation is redundant since 1blocks are precisely those which are not subdivided by the pessimblk + function.

We have also provided a variant for computing the relative pessimism. Some work is left to be done in this direction. As an example, the algorithm could be modified to deal with singularities and the convergence issue could be investigated.

In a second part, we have adapted the pessim + algorithm in order to control the pessimism of the inclusion function, i.e., to automatically decompose a domain into sub-intervals where the pessimism is small enough. The efficiency of the analysis is significantly improved by checking at any stage whether the function is accurate or not (block management), avoiding any redundant computation.

We have also shown that the pessim-ctrl algorithm could be used as a way to compare -in average-the accuracy of different inclusion functions.

All the results we have presented in this paper can easily be adapted to vectorvalued functions. However, extending our work to the multi-variable case seems not straightforward. Such extension would probably resort to multidimensional dynamic programming, which is known to have an exponential complexity. This issue might be addressed in future works.


Patrick Bernard
email: patrick.bernard@ceremade.dauphine.fr

Ugo Bessi
email: bessi@matrm3.mat.uniroma3.it

Young measures, Cartesian maps, and polyconvexity

Keywords:

come

Young measures, Cartesian maps, and polyconvexity

Introduction

Let N be a compact Riemannian manifold with boundary of dimension n and M be a complete Riemannian manifold of dimension m. We denote by N the interior of N , and by dt the nonnegative Borel measure on N associated with the metric. It can be defined as the n-Hausdorff measure associated with the Riemannian distance, and it exists also if N is not orientable. This measure is also characterized by the fact that

D dt = D Ω
for each embedded disk D ⊂ M , where Ω is any of the two unitary volume forms on D. We set p = min{m, n}. We want to discuss the classical question of minimizing the quantity N L(t, u(t), du t ) dt on appropriate classes of maps u : N -→ M . We recall some terminology about Lagrangians:

Convexity : Given k ∈ {1, . . . , min(m, n)}, we say that the integrand L(t, x, v) is k-convex if it can be written in the form

L(t, x, v) = L(t, x, v, ∧ 2 v, . . . , ∧ k v) = L t,x (v, ∧ 2 v, . . . , ∧ k v)
with a Borel measurable function L such that

L t,x : L(T t N, T x M ) × L(∧ 2 T t N, ∧ 2 T x M ) • • • × L(∧ k T t N, ∧ k T x M )) -→ R ∪ {+∞}
is convex for each t and x. When k = 1, this just says that L is convex in v; when k = p, this hypothesis is usually called polyconvexity. Let us explain the notations. We denote by L(E, F ) the set of linear maps between E and F . The space ∧ i E is the vector space E ∧ E . . . ∧ E generated by elements of the form e 1 ∧ e 2 . . . ∧ e i , e j ∈ E. Given v ∈ L(E, F ), we denote by ∧ i v ∈ L(∧ i E, ∧ i F ) the linear map such that ∧ i v(e 1 ∧ . . . ∧ e i ) = v(e 1 ) ∧ v(e 2 ) . . . ∧ v(e i ).

If E has dimension n and F has dimension m, the dimension of ∧ i E is C i n (binomial coefficient) and ∧ i v can be represented by a C i n × C i m matrix whose coefficients are the determinants of all i × i sub-matrices that can be extracted from the matrix representing v. Let us denote by J 1 (N, M ) the manifold of 1-jets of maps from N to M . If N is an open subset of R n and M = R m , then

J 1 (N, M ) = N × M × L(R n , R m ).
Regularity : We say that L : J 1 (N, M ) -→ R ∪ {+∞} is a normal integrand if it is a Borel measurable function and if, for almost all t ∈ N , the function (x, v) -→ L(t, x, v) is lower semi-continuous.

Coercivity : We say that L is k-superlinear if there exists a superlinear function l : [0, ∞) -→ R such that L(t, x, v) l( v

+ ∧ 2 v + • • • + ∧ k v )
for all (t, x, v) ∈ J 1 (N, M ).

Our goal is to explain a compact and simple approach to this kind of problems. We do not present real novelties, and much of the techniques we will use can be found in [START_REF]Parametrized Measures and Variational Principles[END_REF] or [START_REF] Giaquinta | Cartesian currents in the calculus of variations I[END_REF][START_REF] Giaquinta | Cartesian currents in the calculus of variations II[END_REF].

Yet we believe it is not useless to present the short path to Theorem 1 that follows. This work started with an attempt to extend the methods of [START_REF] Bernard | Young measures, superposition and transport Indiana[END_REF] to higher dimension.

We will define, by studying relevant sets of Young measures, sets cart k (N, M ) of maps u : N -→ M such that

W 1,n (N, M ) ⊂ cart min{n,m} (N, M ) ⊂ cart k (N, M ) ⊂ cart 1 (N, M ) = W 1,1 (N, M ).
In the case k = min{n, m} the set that we denote cart k (N, M ) is similar to the set denoted cart 1 (N, M ) in [START_REF] Giaquinta | Cartesian currents in the calculus of variations I[END_REF][START_REF] Giaquinta | Cartesian currents in the calculus of variations II[END_REF], but our presentation is quite different.

In order to state appropriately a variational problem, it is useful to specify boundary conditions. We assume that the boundary ∂N of N is not empty and we fix a map u 0 ∈ cart k (N, M ). We denote by cart k (N, M ; u 0 ) the set of maps u in cart k (N, M ) such that the trace of u in L 1 (∂N, M ) is equal to the trace of u 0 . These traces are well defined (at least in the case where M is a Euclidean space) because cart k (N, M ) ⊂ W 1,1 (N, M ), and each element of W 1,1 (N, M ) has a unique boundary trace in L 1 (see for instance [START_REF] Evans | Measure theory and fine properties of functions[END_REF] for the definition); we recall that the integration by parts formula holds for this trace. In the case where M is a manifold, we shall give the precise definition of cart k (N, M ; u 0 ) in Section 3. Our goal is to provide a short and direct proof of the following result:

Theorem 1. Let k ∈ {1, . . . , min(m, n)} be given and let L : J 1 (N, M ) -→ R ∪ {+∞} be a k-convex and k-superlinear normal integrand. Let u 0 ∈ cart k (N, M ) be given, such that N L(t, u 0 (t), du 0 (t))dt < ∞.
Then there exists a map u ∈ cart k (N, M ; u 0 ) which minimizes the integral

N L(t, u(t), du(t))dt in cart k (N, M ; u 0 ).
Note that, in general, we may have

inf u∈W 1,1 (N,M ;u 0 ) N L(t, u(t), du t )dt < min u∈cart k (N,M ;u 0 ) N L(t, u(t), du t )dt and, even if u 0 is smooth, min u∈cart k (N,M ;u 0 ) N L(t, u(t), du t )dt < inf u∈C 1 (N,M ;u 0 ) N L(t, u(t), du t )dt.
The paper [START_REF] Ball | One-dimensional variational problems whose minimizers do not satisfy the Euler-Lagrange equation[END_REF] contains an example in which N has dimension 1 and the minimum on

W 1,1 (N, R n ) = cart 1 (N, R n ; u 0 ) is smaller than the infimum on C 1 .
As for the other strict inequality, we are going to see an example in section 4.2. Theorem 1 is a slight extension on the seminal results of Ball, [START_REF] Ball | Convexity conditions and existence theorems in nonlinear elasticity[END_REF]. Compared to this work and to classical papers on polyconvexity, our proof works under slightly weaker coercivity. Our Theorem reduces to the famous Tonelli theorem in the case n = 1, and to the famous De Giorgi Theorem in the case m = 1. Several extensions are known, which go much beyond what we plan to expose. First, the kind of convexity hypothesis can be relaxed to the so-called quasiconvexity, but then one has to add more stringent growth conditions, see [START_REF] Dacorogna | Direct methods in the calculus of variations (second edition) App[END_REF][START_REF]Parametrized Measures and Variational Principles[END_REF][START_REF] Buttazzo | Semicontinuity and relaxation and integral representation in the calculus of variations[END_REF]. Second, one can, in certain circumstances, relax the coercivity condition to the case when L has only linear growth, by using cartesian currents and functions of bounded variations. Excellent surveys of these methods are in [START_REF] Giaquinta | Cartesian currents in the calculus of variations I[END_REF][START_REF] Giaquinta | Cartesian currents in the calculus of variations II[END_REF][START_REF] Buttazzo | Semicontinuity and relaxation and integral representation in the calculus of variations[END_REF].

Our approach is based on Young measures, also called parametrized measures. A survey on the use of Young measure is the book [START_REF]Parametrized Measures and Variational Principles[END_REF]. Many of our techniques are adapted from this book. In section 2, we define the various sets of Young measures that are useful, in particular the set of Generalized Maps, on which it is appropriate to relax the variational problem. We study the structure of generalized maps and conclude that minimizing generalized maps correspond to minimizing maps. In section 3, we prove a compactness results under boundary conditions. In section 4, we briefly expose how the various tools exposed in sections 2 and 3 lead to a proof of Theorem 1. We also collect various related remarks. Finally, we recall in the Appendix some relevant facts on the topology of some spaces of measures.

We end this introductory section collecting some notation and material on n-vectors and n-forms we shall need in the following.

Some algebra

Let E and F be two Euclidean vector spaces of dimension n and m. It will be convenient to set p := min(m, n). We denote by L(E, F ) the set of linear maps between E and F . Recall that the vector space ∧ l E is endowed with a natural inner product (which is induced from the inner product of E). This inner product can be characterized by the property that

v 1 ∧ . . . ∧ v l , w 1 ∧ . . . ∧ w l = det(G)
where

G ∈ M l,l (R) is the Gram matrix G i,j = v i , w j and det G is the determinant of G. Note that v 1 ∧ . . . ∧ v l := v 1 ∧ . . . ∧ v l , v 1 ∧ . . . ∧ v l 1/2 = 1 if (v 1 , . . . v l ) is orthonormal in E.
Given a ∈ L(E, F ), we denote by a := sup x E 1 a(x) F its norm and by ∧ l a ∈ L(∧ l E, ∧ l F ) the unique linear map which satisfies

∧ k a(v 1 ∧ v 2 . . . ∧ v l ) = a(v 1 ) ∧ a(v 2 ) ∧ . . . ∧ a(v l )
for each v 1 , . . . , v l in E. The map ∧ l a is called the l-adjoint of a. In coordinates, this map is represented by a matrix whose coefficients are the l-minors of a.

If ω is a k-form on E and U is an l-vector, l k, we denote by i U ω the (kl)-form defined by

i U ω • v = ω • (U ∧ v)
for any (kl)-vector v.

Lemma 1.

Let Ω be a volume form on E, let λ be the unique n-vector on E such that Ω • λ = 1, let U be a k-vector on E and let a ∈ L(E, F ). Then, for any k-form χ on F , we have

(i U Ω) ∧ χ • ∧ n (Id ⊕ a) • λ = (-1) k(n-k) χ • ∧ k a • U,
where

Id ⊕ a : E -→ E ⊕ F is the map v -→ (v, a(v)).
Proof. We make a proof in coordinates. Let (e 1 , . . . e n ) be a base of E such that λ = e 1 ∧ e 2 ∧ . . . ∧ e n . If e * j is the dual base of E * , then we have Ω = e * 1 ∧ . . . ∧ e * n . If I is a subset of {1, . . . , n}, we denote by e I the product e α 1 ∧ . . . ∧ e α i , where i is the cardinal of I, and α j , 1 j i are the elements of I in increasing order. We denote by σ(I) the sign such that e I ∧ e I c = σ(I)λ, where I c is the complement of I. Note that Ω = σ(I)e * I ∧ e * I c , so that i e I Ω = σ(I)e * I c . Note that σ(I c ) = (-1) k(n-k) σ(I). It is sufficient to prove the Lemma for U = σ(J c )e J c , where J has cardinal nk, in which case i U Ω = e * J . We have

∧ n (Id ⊕ a) • λ = I σ(I)e I ∧ (∧ |I c | a • e I c )
where the sum is taken on all subsets I of {1, . . . , n} and |I| is the cardinal of I. We get

(i U Ω) ∧ χ • ∧ n (Id ⊕ a) • λ = (e * J ∧ χ) • ∧ n (Id ⊕ a) • λ = σ(J)χ • ∧ k a • e J c = (-1) k(n-k) χ • ∧ k a • U.

Generalized maps

Let us first recall the definitions of the Sobolev space W 1,q (N, M ). We say that u belongs to this space if there exists a v(t) ∈ L(T t N, T u(t) M ), depending measurably on t, such that

N v(t) q t,u(t) dt < ∞ and d(χ • u) t = dχ u(t) • v(t)
in the sense of distributions for all bounded smooth functions χ : M -→ R with bounded derivative. This can be written intrinsically on the manifold N by requiring that, for each smooth vectorfield U (t) on N compactly supported in the interior of N , we have

N dχ u(t) • v(t) • U (t)dt + N χ(u(t)) • divU (t)dt = 0.
It is not hard to see that, if M is a Riemannian submanifold of a Euclidean space E, then W 1,q (N, M ) is just the set of the functions u ∈ W 1,q (N, E) which satisfy u(t) ∈ M for almost every t. We recall that smooth functions are not necessarily dense in these spaces if q < n.

Young measures

Let us denote by J 1 (N, M ) the set of 1-jets of maps u : N -→ M . In many examples, N is an open subset of R n , M is R m , and then

J 1 (N, M ) = N × R m × L(R n , R m ).
We shall usually denote by (t, x, v) the points of J 1 (N, M ). We define the function

r k (t, x, v) = 1 + v + ∧ 2 v + • • • + ∧ k v
and associate to it the complete metric space P r k (J 1 (N, M )) as in the appendix. This is the space of Borel probability measures η on J 1 (N, M ) such that r k dη < ∞. We note that the measure on N induced by the Riemann metric, which we have denoted by dt, is finite, since N is compact; to simplify the following definitions, we shall suppose that the measure of N is 1. Let t : J 1 (N, M ) -→ N denote the natural projection; we denote by Y k (N, M ) the set of non-negative Borel measures η ∈ P r k (J 1 (N, M )) such that t ♯ η coincides with the measure dt. We endow Y k (N, M ) with the topology induced from P r k (J 1 (N, M )).

Proposition 2. Assume that L is a normal integrand which is bounded from below (or more generally such that L/r k is bounded from below), then η -→ Ldη is lower semi-continuous on Y k .

Proof. Assume first that L is continuous and that L/r k is bounded. Then, the functional is continuous by definition of the topology on P r k .

As an intermediate step, assume that L(t, x, v) is a Caratheodory integrand (measurable in t and continuous in (x, v)) and that L/r k is bounded. By the Scorza-Dragoni Theorem, (see [START_REF] Berliocchi | Intégrandes normales et mesures paramétrées en calcul des variations[END_REF], Theorem I.1.1, p 132) there exists an increasing sequence K i of compact subsets on N such that L is continuous on J 1 (N, M ) |K i (the set of points (t, x, v) such that t ∈ K i ) and such that ∪ i (K i ) has full measure in N . Then, there exists a sequence of continuous functions L i such that |L i |/r k is bounded, independently of i, and such that L i = L on J 1 (N, M ) |K i . It follows that the map η -→ Ldη is the uniform limit on Y k (N, M ) of the continuous maps η -→ L i dη, and therefore it is continuous on Y k (N, M ).

In the general case, we first write the integrand L(t, x, v) = r k (t, x, v)g(t, x, v) with a normal integrand g which is bounded from below. Then g is the increasing pointwise limit of a sequence g i of bounded Caratheodory integrands, see [START_REF] Berliocchi | Intégrandes normales et mesures paramétrées en calcul des variations[END_REF], Theorem I.1.2, p 138. Finally, the map η -→ Ldη is the increasing limit of the continuous maps η -→ r k g i dη, and therefore it is lower semi-continuous.

Closed measures

It is a fundamental and well known observation that there exists many null-Lagrangians, that is functions

F (t, x, v) : J 1 (N, M ) -→ R such that N F (t, u(t), du t )dt = 0 for all C 1 maps u : N -→ M . We define N k (N, M ) as the sets of continuous functions F (t, x, v) such that • F/r k is bounded.
• N F (t, u(t), du t )dt = 0 for each C 1 map u.

• There exists a compact K ⊂ N such that F (t, x, v) = 0 if t ∈ K.

• We have F (t, x, v) = F t,x (v, ∧ 2 v, • • • , ∧ k v) = F(t, x, v, ∧ 2 v, • • • , ∧ k v)
, where F is continuous and where the functions

F t,x (v, v 2 , • • • , v k ) are affine (We say that F t,x is k-affine).
By extension, we shall also denote by N k (N, M ) the set of functions

F(t, x, v 1 , • • • , v k ) associated with the elements F ∈ N k (N, M ). Note that the set N k (N, M ) may depend on the metric on M if M is not compact. Definition 3. A Young measure η ∈ Y k is called closed if F dη = 0 for all F ∈ N k . The set C k of closed measures is closed in Y k ,

and contains the Young measures û associated with maps

u ∈ W 1,n (N, M ).
Let us explain how to build null-Lagrangians. Given a field of l-vectors U , we will denote by U (t) the field of (l -1)-vectors which satisfies

d(i U Ω) = (-1) l+1 i U Ω
for any volume form Ω on N which is compatible with the Riemannian metric (meaning that the volume of an orthonormal base is ±1). Notice that there are exactly two such volume forms on N if it is orientable, and that they lead to the same U . If N is not orientable, then no global volume form Ω exists, but we can still define U by using volume forms defined on orientable open subsets of N (for example discs). If l = 1, for example, U is a vector-field, and U = divU . Lemma 4. For each l ∈ 1, . . . , k, each smooth (l -1)-form χ on M such that both χ and dχ are bounded, and each compactly supported smooth field U (t) of l-vectors on N , the function

F (t, x, v) := χ x • ∧ l-1 v • U (t) + dχ x • ∧ l v • U (t)
belongs to N k (N, M ). In the case l = 1, the form χ is just a function χ(x) on M , and the function F can be rewritten more clearly

F (t, x, v) = χ(x) divU (t) + dχ x • v • U (t).
Proof. Let u : N -→ R m be a C 1 function. Let us still denote by i U Ω and χ the pull-backs of i U Ω and χ by the projections N × R m -→ N and N × R m -→ R m respectively. This allows us to define on

N × R m the (n -1)-form ξ = i U Ω ∧ χ. We have 0 = N (Id × u) * dξ = N dξ (t,u(t)) • ∧ n (Id × du t ) • λdt = (-1) l+1 N (i U Ω ∧ χ) • ∧ n (Id × du t ) • λdt + (-1) n-l N (i U Ω ∧ dχ) • ∧ n (Id × du t ) • λdt Using Lemma 1 of section 1.1, we obtain 0 = (-1) (l-1)(n-l) N χ u(t) • ∧ l-1 du t • U (t)dt + (-1) (l+1)(n-l) N dχ u(t) • ∧ l du t • U (t)dt.
After simplifying the signs, we obtain

N χ u(t) • ∧ l-1 du t • U (t)dt + N dχ u(t) • ∧ l du t • U (t)dt = 0.
This is the required equality.

Generalized maps and Cartesian maps

The closed measure η ∈ C k is called a generalized map if there exists a measurable map u : N -→ M such that the marginal of η on N × M is concentrated on the graph of u. We then say that η is a generalized map over u. We denote by G k (N, M ) the set of generalized maps. Definition 5. We denote by cart k (N, M ) the set of measurable maps u such that there exists a generalized map over u. We call these maps cartesian maps. We have a natural projection π from the set G k (N, M ) of generalized maps to the set cart k (N, M ) of cartesian maps.

The generalized maps have a remarkable structure: Theorem 2. Let η be a generalized map over u. Then, there exists a measurable family Γ t of probability measures on L(T t N, T u(t) M ) such that η = dt ⊗ δ u(t) ⊗ Γ t . Setting

g i (t) := L(TtN,T u(t) M ) ∧ j v dΓ t (v),
we have u ∈ W 1,1 (N, M ), g 1 (t) = du t and g i (t) = ∧ i g 1 (t) for almost all t. By Jensen's inequality, we immediately obtain:

Lemma 8. If u ∈ cart k (N, M ), then u ∈ W 1,1 (N, M
) and the first distributional minor g 1 (t) of u(t) is the weak derivative of u.

Proof. This is a direct consequence of (E1).

The following remark can be applied for example when f is an embedding of M into some Euclidean space, and h is a chart of N : Proposition 9. Let Ñ and M be other manifolds and let f : M -→ M and h : Ñ -→ N . Assume that M is endowed with a complete metric. If f is smooth with bounded differential, h is a smooth diffeomorphism onto its image h( Ñ ) ⊂ N , and

u ∈ cart k (N, M ), then f • u • h ∈ cart k ( Ñ , M ). Moreover, the distributional minors gi of f • u • h are : gi ( t) = ∧ i df u(h( t)) • g i (h(t)) • ∧ i dh t
where g i are the distributional minors of u.

Proof. Let us endow Ñ with the metric such that h is an isometry. Let F (t, x, v) be an element of N k ( Ñ , M ). We want to prove that

Ñ F ( t, f • u • h( t), df u(h( t)) • du h( t) • dh t)d t = 0. (1)
Setting

F (t, x, v) := F (h -1 (t), f (x), df x • v • dh t )
when t ∈ h( Ñ ) and F (t, x, v) = 0 when t ∈ h( Ñ ), we observe that ( 1) is equivalent to

N F (t, u(t), du t )dt = 0. (2)
This relation, on the other hand, holds if F ∈ N k (N, M ) by definition of cart k (N, M ). We prove that F ∈ N k (N, M ). We begin to note that there is K ⊂ Ñ , K compact, such that F ( t, x, ṽ) = 0 if t ∈ K; thus, F (t, x, v) = 0 if t does not belong to the compact set h( K). Moreover, (2) holds for all C 1 maps u. This is true because (2) is equivalent to (1), and (1) for C 1 maps follows because F is a null Lagrangian, and thus it sends the C 1 map f • u • h into zero; this amounts to (1) by the chain rule.

In order to prove the equality between distributional minors, we expand (1) to

Ñ F( t, f • u • h( t), . . . , ∧ i df u(h( t)) • gi (h( t)) • ∧ i dh t, . . .)d t = 0
and use lemma 7.

Lemma 10. We have g l (t) = ∧ l g 1 (t) for almost every t ∈ N .

Proof. If M is a Riemannian submanifold of the Euclidean space E, then every map in cart k (N, M ) belongs to cart k (N, E). Therefore, using the embedding theorem of Nash, we can assume for this proof that M is a Euclidean space. The set of points t 0 which are simultaneously Lebesgue points of the function u and of all the functions g l , have total measure. Let t 0 be such a point. By taking a chart in N , we can suppose that N is the ball B of radius one in R n , that t 0 = 0, and that dt is the Lebesgue measure. Translating in R n , we can suppose that u(0) = 0. Let us consider, for s 1 the maps u s (t) := su(t/s), g s l := g l (t/s) on N . By Proposition 9, u s is a cartesian map on Ñ , the ball of radius s, and g s l are its distributional minors. Our hypothesis on the point t 0 can be rephrased by saying that, strongly in L 1 (N ), we have

u s (t) -→ u ∞ (t) = g 1 (0)t, g s l (t) -→ g ∞ l (t) = g l (0) when s -→ ∞.
We can take a subsequence in order that these limits also hold almost everywhere. Let F be a null Lagrangian on the ball of radius 1; in particular, when trivially extended, it is a null Lagrangian on the ball of radius s, so that N F (t, u s (t), du s (t))dt = 0.

Passing to the limit, we obtain

N F(t, u ∞ (t), g ∞ 1 (t), • • • , g ∞ k (t))dt = 0.
In other words, the limit function u ∞ has g ∞ l as distributional minors. On the other hand, since the function u ∞ is smooth, we know that its distributional minors are ∧ l du ∞ (t), which here are just the constant functions ∧ l g 1 (0). Therefore, by uniqueness of the distributional minors, we have proved that ∧ l g 1 (0) = g l (0).

We have proved Theorem 2. We can reformulate it as follows: A function u belongs to cart k (N, M ) if and only if the minors ∧ l du belong to L 1 and are distributional, which means that they satisfy the equation

N F(t, u(t), du t , ∧ 2 du t , • • • , ∧ k du t )dt = 0. for all F ∈ N k . Note that cart 1 (N, M ) = W 1,1 (N, M ).

Topology

The set G k of generalized maps is endowed with the topology of Y k .

Proposition 11. The set G k (N, M ) of generalized maps is closed in Y k (N, M ).
Proof. Let η j be a sequence of generalized maps above u j . Let us assume that the sequence η j is converging to η in C k (N, M ). We have to prove that there exists a map u ∈ W 1,1 (N, M ) such that the marginal of η on N × M is concentrated on the graph of u. It is enough to prove that, for each embedded ball B ⊂ N , the marginal of η |J 1 (B,M ) on B × M is concentrated on the graph of a map u. As a consequence, we can suppose that N is the open unit ball in R n . We consider M as a Riemannian submanifold of a Euclidean space E, so that we see u j as elements of W 1,1 (N, E) with values in M . Let m j ∈ E be the average of u j , m j = N u j (t)dt. Since the sequence η j is r k -tight, see appendix, the derivatives du j are bounded in L 1 . Therefore, by the Poincaré inequality, the sequence (u jm j ) is bounded in W 1,1 . By the compactness of the embedding W 1,1 -→ L 1 , this sequence is strongly compact in L 1 . We assume, taking a subsequence, that it has a limit u ∞ , and that the convergence holds almost everywhere. By Lusin and Egorov Theorems, for all ǫ > 0, there exists a compact subset K ∈ N such that dt(N -K) ǫ and such that u j is continuous on K and (u jm j ) is converging uniformly on K to u ∞ . It is clear at this point that the unboundedness of m j would contradict the tightness of η j , and therefore we can assume that the averages m j have a limit m ∞ . Setting u := u ∞ + m ∞ , we see that u j is converging uniformly to the continuous function u on K. Denoting by µ the marginal of η on N × M , we conclude that the µ-measure of the graph of u is greater that 1ǫ. Since this holds for all ǫ > 0, we conclude that the measure µ is concentrated on the graph of u.

Boundary conditions and compactness

In most applications, the manifold M is not compact, and it is necessary to introduce boundary conditions in order to get compactness. We fix, as explained in the introduction, a map u 0 ∈ cart k (N, M ). We define the set C k (N, M ; u 0 ) ⊂ C k (N, M ) of closed measures with boundary u 0 as the set of measures η ∈ C k (N, M ) such that

J 1 (N,M ) dχ x • v • U (t) + χ(x) • divU (t)dη(t, x, v) = N dχ u 0 (t) • du 0 (t) • U (t) + χ(u 0 (t)) • divU (t)dt.
for each smooth vectorfield U (t) on N (not necessarily supported in a compact set of N ) and each bounded smooth function χ(x) on M with bounded derivative. We can also define the set of generalized maps with boundary value u 0 :

G k (N, M ; u 0 ) := G k (N, M ) ∩ C k (N, M ; u 0 ).
The space cart k (N, M ; u 0 ) is the space of maps u such that there exists a generalized map η ∈ G k (N, M ; u 0 ) above u, or in other words the maps u whose Young measure û belongs to G k (N, M ; u 0 ). In [START_REF] Giaquinta | Cartesian currents in the calculus of variations I[END_REF], the functions in cart k M ; u 0 ) are said to satisfy a weak anchorage condition. In the case where M is a Euclidean space, the functions in cart k (N, M ; u 0 ) are just the functions in cart k (N, M ) which have the same trace on ∂N as u 0 in the W 1,1 sense. Proposition 12. Let L be a k-convex and coercive Lagrangian. For each c > 0, the set of measures η ∈ C k (N, M ; u 0 ) which satisfy

J 1 (N,M ) L(t, x, v)dη(t, x, v) c (3)
; u 0 ), is closed in Y k (N, M ), the set C(c) is closed in Y k (N, M
). So it is enough to prove that it is relatively compact. By the appendix, this follows if we can prove that it is r k -tight. In other words, we have to show that for each ǫ > 0 there exists a compact subset Z ∈ J 1 (N, M ) such that

J 1 (N,M )\Z(R) r k (t, x, v)dη(t, x, v) 2ǫ
for each measure η ∈ C(c). We shall prove that this holds for

Z(R) = {(t, x, v) ∈ J 1 (N, M ) : d(x 0 , x) R, ||v|| R}
when R is large enough (x 0 is a point in M that we have fixed once and for all). At this point it is convenient to assume, without loss of generality, that L 0. We define

Z(R) = {(t, x, v) ∈ J 1 (N, M ) : ||v|| R}
and we see that there exists A(R) > 0 with A(R) → +∞ as R → +∞ such that, for all η ∈ C(c),

c ≥ J 1 (N,M )\ Z(R) L(t, x, v)dη(t, x, v) A(R) J 1 (N,M )\ Z(R) r k (t, x, v)dη(t, x, v).
Taking R sufficiently large, we get from the inequality above that

J 1 (N,M )\ Z(R) r k (t, x, v)dη(t, x, v) ǫ (4)
for each η ∈ C(c). Setting now

Ẑ(R) = {(t, x, v) ∈ J 1 (N, M ) : d(x 0 , x) R}
we see that the desired inequality follows if we prove that

η(J 1 (N, M ) -Ẑ(R)) ǫ(R) ∀η ∈ C(c) (5)
for all R, with ǫ(R) -→ 0 as R -→ ∞. Indeed, taking R 0 such that (4) holds, and then setting S = max Z(R 0 ) r k , we get

J 1 (N,M )\Z(R) r k dη J 1 (N,M )\ Z(R 0 ) r k dη + Sη(J 1 (N, M ) \ Ẑ(R)) ǫ + Sǫ(R).
In order to prove (5), we consider, for each R > 0, a function g ∈ C 1 (M, R) such that

0 g R (x) 1, g(x) = 1 if d(x 0 , x) R, g(x) = 0 if d(x 0 , x) R/2 |dg x | δ(R) ∀x
where δ(R) -→ 0 as R -→ ∞; and a smooth vector-field U (t) on N such that U = 1 on N or equivalently such that div U = 1 on N . The existence of such a vector-field is given by Lemma 13 below. We note that U is bounded, since N is compact. Since C(c) ⊂ C k (N, M ; u 0 ), we have, for η ∈ C(c),

J 1 (N,M ) g(x)dη(t, x, v) = N g(u 0 (t)) + dg u 0 (t) • du 0 (t) • U (t)dt - J 1 (N,M ) dg x • v • U (t)dη(t, x, v).
The last formula and the definition of g imply that there exists C > 0 such that

J 1 (N,M )\Z(R) dη(t, x, v) Cδ(R) + N g(u 0 (t))dt
for all R and all η ∈ C(c). The term on the right converges to zero as R -→ ∞, this ends the proof.

Lemma 13. Let N be a compact Riemannian manifold with a non-empty boundary. There exists a smooth vector-field U (t) on N such that U = 1 on N or equivalently such that div U = 1 on N .

Proof. In the case where N is a ball in R n , this is obvious, just take U (t) = t/n. In general, one can build U as the gradient of a function h which solves ∆h = 1 on N .

Conclusion

We now collect the tools we have introduced to prove Theorem 1. We also add some discussions and variations.

Proof. We consider the Young measures ûi in G k (N, M ) associated with the functions u i . Now weak convergence implies uniform integrability, which translates to the fact that ûi is r ktight, and therefore compact in Y k (N, R m ). We can suppose that it has a limit η, which is a generalized map above u.

If F (t, v) = F(t, v, v 2 , . . . , v k ) is

On Null-Lagrangians

It may seem unnatural in the definitions of the sets N k (N, M ) to require that the null-Lagrangians F (t, x, v) be k-affine functions of v. Indeed, working with a larger set N (N, M ) of null-Lagrangians would make the result stronger, and may allow to relax somewhat the k-convexity hypothesis on L. The following result, however, shows that there is not much hope in that direction:

Proposition 16. Let us assume that N = R n , and that M = R m . If F is a null-Lagrangian such that F/r k is bounded, then F t,x is k-affine for each t and x.

Proof. We just give an idea of the proof. It follows from proposition 9 that, for λ > 0 and (t 0 , x 0 ) ∈ R n × R m , the function F λ (t, x, v) := F (t 0 + λt, x 0 + λx, v) is a null-Lagrangian. But then F 0 is also a null-Lagrangian, which means that F t 0 ,x 0 is quasiaffine in the sense of [START_REF] Dacorogna | Direct methods in the calculus of variations (second edition) App[END_REF], section 4.1; but in the same section of [START_REF] Dacorogna | Direct methods in the calculus of variations (second edition) App[END_REF] it is proven that quasi-affine functions are poly-affine. In other words, there exists an affine function F(v, v 2 , . . . , v p ) such that F t 0 ,x 0 (v) = F(v, ∧ 2 v, . . . , ∧ p v), where p = min{m, n}. But the bound implies that F does not depend on ∧ j v for j > k.

More general setting

The heart of the matters is the Jensen's inequality obtained in Corollary 6. This inequality is the result of an equilibrium between the known properties of the measures Γ t appearing in the disintegration of generalized maps and the convexity assumed on the integrand L.

Let us denote by C r (X) the set of continuous functions f on X such that sup x∈X |f (x)| r(x) < ∞.

There exists a distance d on P r (X) such that d(µ n , µ) -→ 0 if and only if f dµ n -→ f dµ for all f ∈ C r (X). This distance can be chosen such that, in addition, the metric space (P r , d) is a complete and separable metric space.

In order to define such a distance d on P r (X) one can define first the distance on X, which is complete and equivalent to d. Then, we can define the distance d on P r (X) as the Kantorovich-Rubinstein (also called 1-Wasserstein) distance of (X, d r ).

The relatively compact subsets of (P r (X), d) are those which are r-tight:

Definition 17. The subset Y ⊂ P r (X) is called r-tight if one of the following equivalent properties holds:

• For each ǫ > 0, there exists a compact set K ⊂ X such that X-K r(x)dµ ǫ for each µ ∈ Y .

• There exists a function f : X -→ [0, ∞] whose sublevels are compact and a constant C such that X r(x)f (x)dµ C for each µ ∈ Y .

• The family Y is tight and r is Y -uniformly integrable. The first means that, for each ǫ > 0, there exists a compact set K ⊂ X such that µ(X -K) ǫ for each µ ∈ Y . The second means that for each ǫ > 0, there exists a ball B in X such that X-B r(x)dµ ǫ for each µ ∈ Y .

Note that 1-tightness is just tightness if r ≡ 1. If r is proper, then Y is r-tight if and only if there exists a constant C and a superlinear function f : [0, ∞) -→ R such that X f • rdη C for all η ∈ Y .

  Let us denote by C(c) the set of measures η ∈ C k (N, M ; u 0 ) which satisfy (3). Since the functional η -→ Ldη is lower semi-continuous on Y k (N, M ) (by Proposition 2), and since C k (N, M

d

  r (x, y) := min(d(x, y), 1) + |r(y)r(x)|.

  a continuous function which is affine in (v, v 2 , . . . , v k ), then we haveF dû i -→ F dη because ûi -→ η.On the other hand, since F is affine in the minors, and since ∧ j du i -→ g j weakly, we have F(t, du i (t), ∧ 2 du i (t), . . . , ∧ k du i (t))dt -→ F(t, du(t), g 2 (t), . . . g k (t))dt.

	We conclude that
	F dη = F(t, du(t), g 2 (t), . . . g k (t))dt.
	This implies that, for almost all t,
	g

j (t) = ∧ j vdΓ t = ∧ j du(t)

by Theorem 2.

Corollary 6. If η is a generalized map over u, and if L is k-convex, then J 1 (N,M ) Ldη N L(t, u(t), du t )dt.

Proof.

J 1 (N,M ) Ldη = N L(TtN,T u(t) M ) L(t, u(t), v)dΓ t (v)dt But we have, for each t, L(TtN,T u(t) M ) L(t, u(t), v)dΓ t (v) = L(TtN,T u(t) M ) L(t, u(t), v, ∧ 2 v, . . . , ∧ k v)dΓ t (v) L(t, u(t), du(t), ∧ 2 du(t), . . . , ∧ k du(t)) by Jensen's inequality, because L(TtN,T u(t) M ) ∧ j vdΓ t (v) = ∧ j du(t) by Theorem 2.

The proof of Theorem 2 will occupy the end of the present section. The functions g i (t) depend only on the map u, not on η. This is a consequence of the following: Lemma 7. Let u : N -→ M be a given measurable function. Then there exists at most one family of functions g 1 (t), . . . , g k (t) such that N F(t, u(t), g 1 (t), g 2 (t), . . . , g k (t))dt = 0 for each F ∈ N k . We call these functions the distributional minors of u if they exist. The map u belongs to cart k (N, M ) if and only if it admits distributional minors.

Proof. The maps g l satisfy the following equations:

for all smooth vector-field U on N supported in the interior of N , and all smooth function χ : M -→ R, and

for all l ∈ 2, . . . , k, all compactly supported smooth field of l-vectors U (t) on N , and all smooth l -1-form χ on M which is bounded as well as dχ. Now assume that g ′ l (t) are other maps satisfying the same equation. Then, we have

for each l, each χ and each U . We claim that this implies that g l (t)-g ′ l (t) = 0 almost everywhere. Since we have the freedom of choosing U , we conclude easily that dχ u(t) • (g l (t)g ′ l (t)) = 0 for almost all t. If the claim did not hold, we could find a compact set K ⊂ N of positive measure, such that u and g lg ′ l are continuous on K and g lg ′ l does not vanish on K. Let t 0 be a point of density of K, and let χ be a compactly supported (l -1)-form on M such that

Since t 0 is a density point of K, and since all the involved functions are continuous on K, there exists a compact subset K ′ of K of positive measure such that the relation dχ u(t) •(g l (t)-g ′ l (t)) = 0 holds for all t ∈ K ′ . This is a contradiction.

Proof of Theorem 1

By Propositions 11 and 12, there exists a generalized map η over some u ∈ W 1 (N, M ) such that η minimizes Ldη on G k (N, M ; u 0 ). We want to show that u minimizes in cart k (N, M ; u 0 ).

If v ∈ cart k (N, M ; u 0 ) is another map, we have

where the first inequality comes from Corollary 6, and where v ∈ G k (N, M ; u 0 ) is the Young measure associated with v. This proves that u is minimizing in cart k (N, M ; u 0 ).

An example

We consider M = R 2 ; N = B, the unit open ball of R 2 , and the Lagrangian

when ǫ > 0 is small enough. Indeed, taking u(t) = t/|t|, and observing that det du = 0, we get a constant C > 0 such that inf

On the other hand, if u ∈ cart 2 (B, R 2 ; Id) is a minimizer we have

where the last inequality follows from the following Lemma:

Proof. We claim that u(B) ⊂ B. Indeed, let f : If we did not have u(t) ⊂ B for almost every t, the action of f • u would be strictly smaller than the action of u, which would contradict the assumption that u is a minimizer. Let us denote by A the annulus 1/2 < |t| < 1. We have

so that u is continuous on A, and extends by continuity to ∂B, where it takes the value u| ∂B = Id. Finally, recall that u(B) ⊂ B. Define

, and in W 1,4 (A, R). As a consequence, u i | ∂B converges uniformly to the identity; since u i is smooth, this implies

Thus it is enough to prove that

Let r ∈]1/2, 1[ and let φ r ∈ C ∞ 0 (B, R) be such that 0 φ r 1 and φ r = 1 on B(0, r). Since

as r -→ 1, the formula ( 6) follows if we prove

and

Note that (8) follows from the boundedness of det du i in L 2 (A). In order to prove [START_REF] Bernard | Young measures, superposition and transport Indiana[END_REF], we set u i = (u 1 i , u 2 i ) and u = (u 1 , u 2 ), we call (x 1 , x 2 ) the coordinates on the target space R 2 and we assert that

Indeed, this formula is just (El) with l = 2, χ = a(x 1 )dx 2 and U = φ r e 1 ∧ e 2 , where a : R -→ [-3, 3] is a smooth function such that a(x 1 ) = x 1 on [-2, 2]. Here we use that u(B) ⊂ B. Similarly, by Lemma 4,

As a consequence ( 7) is equivalent to

which holds because the integrand is converging almost everywhere and is bounded in L 2 .

Weak continuity of minors

Let us mention the following classical result which follows from our tools (see [START_REF] Giaquinta | Cartesian currents in the calculus of variations I[END_REF], 3.3.1 or [10], 8.3):

Other, but less explicit equilibria might be obtained as follows. Let r(t, x, v) be a continuous function on J 1 (N, M ) such that r(t, x, v) 1 + v . We define the associated Kantorovich-Rubinstein space P r (J 1 (N, M )), which is the set of Borel probabilities η on J 1 (N, M ) such that rdη < ∞. We also define the set Y r (N, M ) of those elements η of P r (J 1 (N, M ))) such that t ♯ η = dt. Now let Ĝr (N, M ) be the closure, in Y r (N, M ) of the set of Young measures associated with smooth maps. We can prove as in Proposition 11 that, to each η ∈ Ĝr (N, M ) is associated a map u ∈ W 1,1 (N, M ) such that η = dt ⊗ δ u(t) ⊗ Γ t [START_REF] Buttazzo | Semicontinuity and relaxation and integral representation in the calculus of variations[END_REF] and such that vdΓ t = du(t) for almost all t. We can define cart r (N, M ) as the set of maps which appear in this way. In this setting, we can fix boundary conditions as before by taking u 0 ∈ cart r (N, M ). If the coercivity condition of the Lagrangian is modified to

with l super-linear, we still have compactness: Proposition 12 still holds, with the same proof. So if L is a normal integrand satisfying the modified coercivity condition, then there exists a Young measure η ∈ Ĝr (N, M ; u 0 ) which minimizes the integral Ldη in this set.

In order to prove the existence of minimizers in cart r ( Ñ , M ; u 0 ), it is enough to adapt the convexity condition, in such a way that Corollary 6 holds for the elements of Ĝr (N, M ).

Let P t,x be the set of Borel probability measures Γ on L(T t N, T x M ) such that r t,x (v)dΓ(v) < ∞. In short, we have P t,x := P rt,x (L(T t N, T x M ))

(see the Appendix below). Let B be a closed ball of volume one in T t N . Let P t,x be the closure, in P t,x of the measures of the form Γ = (du) ♯ (dt |B )

where u : T t N -→ T x M is a smooth map supported in B. Note that if Γ ∈ P t,x , then L(TtN,TxM ) vdΓ = 0. A last notation is necessary: we denote by τ z the translation of vector z. Then, possibly under some mild assumption on the function r, the following result can be proved by a blow-up argument called localisation procedure in [START_REF]Parametrized Measures and Variational Principles[END_REF]:

Structure Theorem: The measures η ∈ Ĝr (N, M ) can be written in the form [START_REF] Buttazzo | Semicontinuity and relaxation and integral representation in the calculus of variations[END_REF], with (τ -dut ) ♯ Γ t ∈ P t,x for almost all t.

As a consequence, the convexity condition that has to be assumed in order that Corollary 6, and then Theorem 1 hold in this more general setting is L(TtN,TxM ) L t,x (a + v)dΓ(v) L(t, x, a) for all (t, x) ∈ N × M , for all a ∈ L(T t N, T x M ) and for all Γ ∈ P t,x . This is not an easy condition to check on examples.

A Kantorovich-Rubinstein space

Let us recall some standard facts on probability measures, see [START_REF] Ambrosio | Gradient flows, Lectures in Math[END_REF][START_REF] Villani | Topics in optimal transportation[END_REF]. Let (X, d) be a complete and separable metric space, and let r : X -→ [1, ∞) be a continuous function. Let P r (X) be the set of Borel probability measures µ on X which satisfy X r(x)dµ(x) < ∞.