Francesca Chittaro

Gianna Stefani

MINIMUM-TIME STRONG OPTIMALITY OF A SINGULAR ARC: THE MULTI-INPUT NON INVOLUTIVE CASE

We consider the minimum-time problem for a multi-input control-affine system, where we assume that the controlled vector fields generate a non-involutive distribution of constant dimension, and where we do not assume a-priori bounds for the controls. We use Hamiltonian methods to prove that the coercivity of a suitable second variation associated to a Pontryagin singular arc is sufficient to prove its strong-local optimality. We provide an application of the result to a generalization of Dubins problem.

Introduction

In this paper we are concerned with the minimum-time problem associated with a control-affine system with several controls:

(1.1) min T subject to (1.2)    ξ = (f 0 + m i=1 u i f i ) • ξ(t) ξ(0) ∈ N 0 , ξ(T ) ∈ N f u = (u 1 , . . . , u m ) ∈ U ⊂ R m .
The state q belongs to a smooth n-dimensional manifold M , f 0 , f 1 , . . . , f m , are smooth vector fields on M , N 0 and N f are smooth submanifolds of M and the control functions belong to L ∞ ([0, T ], U ). We remark that for smooth we mean C ∞ .

We are interested in sufficient conditions for the strong-local optimality of singular Pontryagin extremals of problem (1.1)-(1.2), were strong means with respect to the C 0 -norm of the trajectories ξ(•), and singular means that u ∈ int U . More precisely, we assume that there exists a candidate Pontryagin extremal λ : [0, T ] → T * M with associated control function u(•) ∈ L ∞ ([0, T ], int U ) that satisfies π λ(0) ∈ N 0 and π λ( T ) ∈ N f , and we look for sufficient conditions that guarantee the strong-local optimality of the trajectory ξ = π λ, according to the following definition: Definition 1.1. The trajectory ξ is a strong-local minimizer of the above considered problem, if there exist a neighborhood V of its graph in R × M and ǫ > 0 such that ξ is a minimizer among the admissible trajectories whose graph is contained in V and whose final time is greater than T -ǫ, independently on the values of the associated controls. This notion has been called time-state-local optimality in [START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF], where also a stronger version of optimality is considered.

The only assumption we do on the control set U is that it has non-empty interior; although by Filippov's Theorem ( [START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF]) we know that the existence of the minimum is guaranteed when U is compact and convex, here the existence of a candidate minimizer is taken as assumption.

A classical approach to sufficient optimality conditions is to consider the second variation (see for instance [START_REF] Agrachev | An invariant second variation in optimal control[END_REF][START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF][START_REF] Aronna | Quadratic conditions for bang-singular extremals[END_REF][START_REF] Dmitruk | Quadratic condition for a weak minimum for singular regimes in optimal control problems[END_REF][START_REF] Gabasov | High order necessary conditions for optimality[END_REF][START_REF] Stefani | Constrained regular LQ-control problems[END_REF] and references therein). In particular, in [START_REF] Agrachev | An invariant second variation in optimal control[END_REF] and [START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF] the authors propose the definitions of an intrinsically defined second variation, which is invariant for coordinate changes, and therefore suitable to study optimal control problems defined on smooth manifolds.

A peculiarity of control-affine minimum-time problems is that the second variation does not contain the Legendre term (that is, the term which is quadratic in the variations of the control), thus turning out to be singular. A tool widely used to overcome this problem is the so-called Goh transformation [START_REF] Goh | The second variation for singular Bolza problems[END_REF]. Thanks to this transformation, performed in a coordinate-free way, we are able to convert the second variation proposed in [START_REF] Agrachev | An invariant second variation in optimal control[END_REF] into another functional which is no more singular, and thus it can be asked to be coercive with respect to the L 2 -norm of the new control variable. This approach, both for classical and intrinsically-defined second variations, has been widely used in the analysis of sufficient optimality conditions (see for instance [START_REF] Aronna | Quadratic conditions for bang-singular extremals[END_REF][START_REF] Dmitruk | Jacobi type conditions for singular extremals[END_REF][START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF][START_REF] Stefani | Strong optimality of singular trajectories[END_REF], and references therein).

In optimal-control problems, a classical method to prove the optimality of a Pontryagin extremal is to cover a neighborhood of the reference trajectory with other admissible trajectories, to lift them to the cotangent bundle, and compare the costs evaluated along each trajectory. In the standard theory, the trajectories to be lifted are obtained by projecting suitable solutions of the Hamiltonian system associated with the maximized Hamiltonian F max , see for example [START_REF] Agrachev | An invariant second variation in optimal control[END_REF][START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF]. This Hamiltonian method is particularly effective, since it allows us to compare trajectories that belong to a C 0 -neighborhood of the reference trajectory, independently on the value of the control.

When the extremal is singular F max cannot be used (see [START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF]), then to construct the lifted trajectories we consider the solutions of a system governed by a Hamiltonian greater than or equal to F max , as suggested by the approach used in [START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF][START_REF] Stefani | Strong optimality of singular trajectories[END_REF].

Ultimately, the paradigm to get sufficient optimality condition for singular extremals combines an approach based on the coercivity of the second variation with the Hamiltonian approach. It relies on the following facts.

• Under some regularity conditions, it is possible to define a smooth super-Hamiltonian whose flow is tangent to all singular extremals. • The derivative of the super-Hamiltonian flow is, up to an isomorphism, the Hamiltonian flow associated to the linear-quadratic problem given by the second variation. • If the second variation is coercive, it is possible to transform the linear-quadratic problem associated with the original one into a problem with free initial point, whose second variation is still coercive. In particular, this implies that the space of initial constraints for the linear-quadratic problem remains horizontal (that is, it projects bijectively on M ) under the action of the associated Hamiltonian flow. • The previous points imply that the projection on M of the super-Hamiltonian flow emanating from the Lagrangian manifold associated with the initial conditions of the new problem is locally invertible. As a result we get that it is possible to lift the trajectories to the cotangent bundle, in order to apply the Hamiltonian method.

In the single-input case, problem (1.1)-(1.2) has already been studied in [START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF], where it has been shown that the coercivity of the second variation is a sufficient condition for the strong-local optimality of singular Pontryagin extremals. In [START_REF] Chittaro | Singular extremals in multi-input time-optimal problem: a sufficient condition[END_REF] the authors studied the multi-input problem under the assumptions that the controlled vector fields generate an involutive distribution. In this paper we relax this condition, that is we allow the controlled vector field to generate a noninvolutive distribution.

We remark that our result remains true even if U = R m , then we need stronger assumptions than the usual ones. In particular, we have to consider High Order Goh condition (Assumption 3), which we prove to be indeed a necessary optimality condition when U = R m . This phenomenon is not pointed out when the Lie algebra generated by the controlled vector fields is involutive, in particular when the system is single-input. Indeed, in these cases High Order Goh condition is automatically satisfied under Goh condition.

We believe that this result, applied to the case where U is an unbounded set, could be of help in the study of the infimum-time problem where the "optimal" trajectories may contain jumps, as in [START_REF] Bressan | Impulsive control systems with commutative vector fields[END_REF][START_REF] Bressan | Impulsive control systems without commutativity assumptions[END_REF][START_REF] Sarychev | Fréchet generalized trajectories and minimizers for variational problems of low coercivity[END_REF], where integral costs are considered.

The structure of the paper is the following: we state the regularity assumptions in Section 2; in Section 3 we define the second variation and investigate the implications of its coercivity; the Hamiltonian method is exposed in Sections 4 and 5, where we state and prove the main result; in Section 6 we provide an example, based on a high dimensional version of Dubins' problem. In the Appendices there are technical details on some results stated in the paper.

Notations and regularity assumptions

In this section we clarify the notation we will use throughout the paper, and we state the regularity assumptions on the system.

Let f be a vector field on the manifold M and ϕ : M → R be a smooth function. The action of f on ϕ (directional derivative or Lie derivative) evaluated on a point q is denoted with the two expressions L f ϕ(q) = dϕ(q), f (q) . The Lie brackets of two vector fields f, g are denoted as commonly with [f, g]. When dealing with vector fields labeled by indexes, we will use the following notations to denote their Lie brackets:

f ij (q) = [f i , f j ](q), f ijk (q) = [f i , [f j , f k ]](q)
. We call f the set of the controlled vector fields of the control system (1.2), that is f = {f 1 , . . . , f m }, and Lie(f) the Lie algebra generated by the set f. We denote Lie q (f) = span{f (q) : f ∈ Lie(f)}. In the following, for every q ∈ M , we call I q the integral manifold of the distribution Lie(f) passing through q. The first assumption of this paper concerns the regularity of Lie(f).

Assumption 1. The controlled vector field f 1 , . . . , f m are linearly independent and the Lie algebra Lie(f) has constant dimension R.

Let us consider the cotangent bundle T * M of M , and let π denote the canonical projection on M . It is well known that T * M possesses a canonically defined symplectic structure, given by the symplectic form σ ℓ = dς(ℓ), where ℓ denotes an element of T * M and ς is the Liouville canonic

1-form ς(ℓ) = ℓ • π * .
We denote with the corresponding capital letter the Hamiltonian function associated with every vector field on M , that is F (ℓ) = ℓ, f (πℓ) . As above, we denote

F ij (ℓ) = {F i , F j }(ℓ) F ijk (ℓ) = {F i , {F j , F k }}(ℓ).
We recall that the symplectic structure allows us to associate, with each Hamiltonian function F , the Hamiltonian vector field F on T * M defined by the action

dF (ℓ), • = σ ℓ (•, F (ℓ)).
In the following, we consider some special Hamiltonian functions associated with the optimal control problem (1.1)-(1.2): the (time-dependent) reference Hamiltonian

(2.1) F t (ℓ) = F 0 (ℓ) + m i=1 u i (t)F i (ℓ),
where u(•) is the reference control, and the maximized Hamiltonian

F max (ℓ) = sup u∈U F 0 (ℓ) + m i=1 u i F i (ℓ) .
The Hamiltonian flow from time 0 to time t associated with the reference Hamiltonian, that is the solution of the equation l = F t (ℓ), is denoted with F t .

Let us consider an admissible triple ( ξ, u, T ) for the problem (1.2), that is a solution of the control system; let us assume that u ∈ int U , and let us set q 0 = ξ(0) and q f = ξ( T ). We study the strong-local optimality of the triple ( ξ, u, T ), that in the following we call reference triple, among all solutions of (1.2) with N 0 ⊂ I q0 and N f ⊂ I q f . In particular, Assumption 1 can be asked to hold only in a neighborhood of the reference trajectory.

A classical necessary condition for the optimality of the reference triple ( ξ, u, T ) is the Pontryagin Maximum Principle (PMP), that we recall here stated in its Hamiltonian form (see [START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF]). PMP states that if a reference trajectory ( ξ, u, T ) satisfying u ∈ int U is time-optimal, then there exist a Lipschitzian curve λ : [0, T ] → T * M and p 0 ∈ {0, 1} that satisfy the following equations:

λ(t) = 0 ∀ t ∈ [0, T ] (2.2) π λ(t) = ξ(t) ∀ t ∈ [0, T ] (2.3) d dt λ(t) = F t ( λ(t)) ∀ t ∈ [0, T ] (2.4) F i ( λ(t)) = 0 ∀ i = 1, . . . , m ∀ t ∈ [0, T ] (2.5) F t ( λ(t)) = F 0 ( λ(t)) = p 0 ∀ t ∈ [0, T ] (2.6) λ(0)| T q 0 N0 = 0 λ( T )| T q f N f = 0. (2.7)
The Lipschitzian curves that satisfy equations (2.2)-(2.7) are called extremals. If p 0 = 1 we say the the extremal λ is normal, while in the other case we say that it is abnormal. Assumption 2. We assume that the reference triple satisfies the PMP in the normal form, and we call the extremal λ reference extremal. By differentiating with respect to time, we obtain the following condition:

(2.8) F 0i ( λ(t)) + m j=1 u j (t)F ji ( λ(t)) = 0 i = 1, . . . , m, a.e. t ∈ [0, T ].
In literature additional necessary conditions for the optimality of a singular extremal are known (see [START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF]). Namely, if the reference triple is optimal, then there exists an extremal λ associated with the reference triple that satisfies the following conditions:

(Goh condition) F ij (λ(t)) = 0 ∀ i, j = 1, . . . , m, t ∈ [0, T ].
(Generalized Legendre Condition) the quadratic form (2.9)

L λ(t) : v → m i,j=1 v i v j F ij0 (λ(t)) + m i,j,k=1 v i v j u k (t)F ijk (λ(t))
is non-positive for any v = (v 1 , . . . , v m ) ∈ R m and for a.e. t ∈ [0, T ].

Remark 2.2. Notice that the matrix L λ(t) is symmetric by (2.8) and Jacobi identity.

We strengthen the two necessary conditions above defined.

Assumption 3. (High Order Goh Condition)

We assume that the reference extremal λ satisfies the following equations

λ(t), f ( ξ(t)) = 0 ∀ f ∈ Lie(f), t ∈ [0, T ].
HOGC is a stronger condition than the usual one, but in our case the optimality of the singular extremal is proved also when U = R m ; in Appendix A we show that, for U = R m , HOGC is a necessary optimality condition. As a matter of fact, if the Lie algebra generated by the controlled vector fields is 2-step bracket generating, then HOGC coincides with Goh condition.

Remark moreover that, under Assumption 3, the quadratic form L λ(t) is given by

(2.10) L λ(t) : v → m i,j=1 v i v j F ij0 ( λ(t)),
so that it is continuous as a function of time.

Assumption 4. (Strengthened Generalized Legendre Condition)

There exists a constant c > 0 such that

(2.11) L λ(t) [v] 2 ≤ -c|v| 2 for any v = (v 1 , . . . , v m ) ∈ R m and for every t ∈ [0, T ].
As a consequence of Assumptions 1-3 and equation (2.8), we get that

λ(t), [f 0 , f ]( ξ(t)) = 0 ∀ f ∈ Lie(f), ∀ t ∈ [0, T ] (2.12) m j=1 (L λ(t) ) ij u j (t) = F 00i ( λ(t)) i = 1, . . . , m a.e. t ∈ [0, T ]. (2.13)
From (2.13) and Assumption 4 we can recover the reference control as feedback on the cotangent bundle and, by induction, we can prove that it is smooth.

From now on we restrict to a (full-measure) neighborhood U of λ([0, T ]) in T * M where SGLC is satisfied, that is, where the quadratic form L ℓ is negative-definite. We define two submanifolds of U which are crucial for our construction:

Σ = {ℓ ∈ U : ℓ, f (πℓ) = 0 ∀ f ∈ Lie(f)} (2.14) S = {ℓ ∈ Σ : ℓ, [f 0 , f ](πℓ) = 0 ∀ f ∈ Lie(f)}. (2.15)
By Assumption 1, possibly restricting U, Σ is an embedded manifold of codimension R. Moreover every singular extremal that satisfies HOGC is contained in S. We set the following regularity assumption on S, which requires that it is a submanifold of maximal dimension (see the arguments below).

Assumption 5 (Regularity of S). The manifold S has constant codimension m in Σ.

Thanks to regularity assumptions, the manifolds Σ and S have the following properties. The proofs can be obtained adapting those in [START_REF] Chittaro | Singular extremals in multi-input time-optimal problem: a sufficient condition[END_REF].

(P1) It is easy to see that the Lie algebra Lie ℓ ( F 1 , . . . , F m ) has dimension R for every ℓ ∈ Σ.

Moreover, every vector field X ∈ Lie ℓ ( F 1 , . . . , F m ) is tangent to Σ. (P2) It is not difficult to prove that SGLC implies that the vector fields f 01 , . . . , f 0m are linearly independent, and their span is transversal to Lie(f). Therefore S has codimension at least m in Σ, and Assumption 5 states then that S has the maximal dimension. The arguments above prove also that S it can be characterized by

S = {ℓ ∈ Σ : F 0i (ℓ) = 0 ∀ i = 1, . . . , m}.
Notice that the existence of a normal singular extremal satisfying HOGC implies that R+m ≤ n -1 and that f 0 is transversal to Lie(f), in a neighborhood of the corresponding trajectory on M . Moreover, Assumption 5 is equivalent to the following one:

[f 0 , f ] ∈ Lie(f) + span({f 01 , . . . , f 0m }) ∀ f ∈ Lie(f).
(P3) Similar arguments show that F 01 , . . . , F 0m are transversal to Σ, and F 1 , . . . , F m are transversal to S. (P4) F 0 is tangent to Σ in S. (P5) Our assumptions guarantee the existence of a Hamiltonian vector field tangent to all singular extremals. Indeed, setting for every ℓ ∈ U

(2.16) ν(ℓ) = L -1 ℓ    F 001 (ℓ) . . . F 00m (ℓ)    ,
we get that the vector field F S = F 0 + m i=1 ν i F i is tangent to S, and the reference extremal λ(•) is an integral curve of F S . Indeed every singular extremal associated with our dynamics is an integral curve of F S .

Second variation

In this section we define the second variation for the problem under study, and we investigate the consequences of the coercivity of the second variation. The computations can be recovered by adapting those present in [START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF][START_REF] Stefani | Strong optimality of singular trajectories[END_REF].

3.1. Construction of the second variation. We consider the second variation associated with the sub-problem of (1.1)-(1.2) with fixed final point, that is we add the constraint ξ(T ) = q f . To compute this second variation, we transform such minimum-time problem into a Mayer problem on the fixed time interval [0, T ] and on the state space R × M . Namely, putting u 0 as a new constant control with positive values, we reparametrize the time as u 0 t, and we set q = (q 0 , q) ∈ R × M , f 0 (q) = f 0 (q) + ∂ ∂q 0 and f i (q) = f i (q), i = 1, . . . , m. Then the minimum-time problem between N 0 and q f is equivalent to the Mayer problem on R × M described below.

(3.1) min ξ 0 ( T ) subject to (3.2)      ξ(t) = u 0 f 0 (ξ(t)) + m i=1 u 0 u i (t)f i (ξ(t)) t ∈ [0, T ] ξ(0) ∈ {0} × N 0 , ξ( T ) ∈ R × { q f } (u 0 , u) ∈ (0, +∞) × L ∞ ([0, T ], U )
where ξ = (ξ 0 , ξ). It is not difficult to see that the trajectory ξ(t) = (t, ξ(t)), associated with the controls u 0 = 1 and u = u, is an extremal with associated adjoint covector λ :

s → ((-1, t), λ(t)) ∈ R * × T * M .
For t ∈ [0, T ], we define the evolution map S t : M → M by its action S t : x 0 → ξ(t), where ξ is the solution of the equation ξ = f 0 (ξ) + m i=1 u i f i (ξ) with initial condition ξ(0) = q 0 . In particular, S t ( q 0 ) = ξ(t). We locally define around q 0 the pull-back vector fields

g i t = S -1 t * f i • S t , i = 0, . . . , m.
Analogously, for the Mayer problem we define the evolution S t : R × M → R × M as S t : (q 0 , q) → (q 0 + t, S t (q)), and the pull-back system of (3.2) corresponding to the reference control u as

η(t) = S -1 t • ξ(t). The Mayer problem (3.1)-(3.
2) is then equivalent to the following one: min η 0 ( T ) subject to the control system

(3.3)      η0 (t) = u 0 -1 η(t) = (u 0 -1)g 0 t (η(t)) + m i=1 (u 0 u i (t) -u i (t))g i t (η(t)) η(0) ∈ {0} × N 0 η( T ) ∈ R × { q 0 }. Let us now consider variations (δu 0 , δx, δu) ∈ R × T q0 N 0 × L ∞ ([0, T ], R m
) around the reference trajectory, and let us evaluate the coordinate-free second variation of the Mayer problem, following [START_REF] Agrachev | An invariant second variation in optimal control[END_REF]. We choose any two smooth functions α, β : R × M → R that satisfy the following constraints: α(q 0 , q) = α(q) -q 0 , α| N0 ≡ 0, dα( q 0 ) = λ(0), (3.4) β(q 0 , q) = q 0 + β(q), dβ( q 0 ) = -λ(0), (3.5) for two suitable smooth functions α, β : M → R. Thanks to High Order Goh Conditions, we can choose the function α in such a way that it satisfies the constraint α| I q 0 ≡ 0, where I q0 is the integral manifold of the distribution Lie(f) passing through q 0 . Moreover, we can choose β = -α, since the second variation does not depend on the particular choice of α and β with the properties (3.4) and (3.5) (see [START_REF] Agrachev | An invariant second variation in optimal control[END_REF]).

The second variation is given by

J ′′ [(δx, δu 0 , δu)] 2 = T 0 δu 0 L δη(t) L g 0 t β( T , q 0 ) + m i=1 (δu 0 u i (t) + δu i (t))L δη(t) L g i t β( T , q 0 ) dt, (3.6)
where δη(t) ∈ R × T q0 M is the linearization of η(t) and satisfies the following system:

(3.7)      δη 0 (t) = δu 0 δη(t) = δu 0 g 0 t ( q 0 ) + m i=1 (δu 0 u i (t) + δu i (t))g i t ( q 0 ) δη(0) = (0, δx) ∈ {0} × T q0 N 0 , δη( T ) ∈ R × {0}.
Remark 3.1. If δη satisfies the system (3.7), then the value of the second variation does not depend on the particular choice of α and β, provided that they satisfy properties (3.4)-(3.5) (see [START_REF] Agrachev | An invariant second variation in optimal control[END_REF]). Then J ′′ is well defined and coordinate free.

Since we are interested only in the so-called time-state local optimality, we restrict us to the subproblem with δu 0 = 0, and, proceeding as in [START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF], we define w(•) and ǫ by

w i (t) = T t δu i (s) ds (3.8) ǫ i = w i (0), (3.9)
for i = 1, . . . , m. In this way, the control variation δu is embedded as the pair (ǫ, w(•)) in the space R m × L 2 ([0, T ], R m ). We remark that this embedding is continuous and it has dense image. Then the second variation defined by (3.6)-(3.7) writes as w i (t) ġi t ( q 0 ), with boundary conditions

J ′′ [(δx, ǫ, w(•))] 2 = 1 2 m i,j=1 L ǫifi L ǫjfj β( q 0 ) + T 0 w i (t)w j (t)L [ ġi t ,g j t ] β( q 0 ) dt + m i=1 L δx L ǫifi β( q 0 ) + T 0 w i (t)L ζ(t) L ġi t β( q 0 ) dt . ( 3
(3.12) ζ(0) = δx + m i=1 ǫ i f i ( q 0 ), ζ( T ) = 0.
Let us observe that the second variation is realized as a linear-quadratic control problem in the state-variable ζ, with control w (see [START_REF] Agrachev | An invariant second variation in optimal control[END_REF][START_REF] Stefani | Strong optimality of singular trajectories[END_REF][START_REF] Stefani | Constrained regular LQ-control problems[END_REF]). Notice moreover that

ġi t ( q 0 ) = S -1 t * [f 0 , f i ] • ξ(t) and L [ ġi t ,g j t ] β( q 0 ) = -F ij0 ( λ(t)
). Finally, thanks to the choice of β, the finite-dimensional term in (3.10) is null.

It is clear that, if T q0 N 0 ∩ span({f 1 ( q 0 ), . . . , f m ( q 0 )}) = 0, then the above defined quadratic form cannot be coercive. On the other hand, the paradigm exposed in the introduction requires that the flow of the super-Hamiltonian emanating from Σ remains contained in Σ, as Theorem 5.1 in Section 5 describes (see also [START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF][START_REF] Stefani | Strong optimality of singular trajectories[END_REF]); in particular, the horizontal Lagrangian sub-manifold of the initial constraints must be contained in Σ. These arguments suggest to require coercivity of (3.10) allowing all vectors in Lie q0 (f) to be initial conditions for the state ζ; see Section 3.2 and the proof of Theorem 5.2 in Section 5. In particular, this means to consider the second variation for the minimum time problem from I q0 to q f . This is not surprising, since our result holds true also for unbounded controls; indeed, if U = R m , for every two points q 1 , q 2 ∈ I q0 , there exist a sequence of times t k → 0 and a sequence of controls u k such that the sequence t k → {ξ k (q 1 , u k , t k )} k of the solutions at time t k of the system (1.2) starting from the point q 1 and relative to the control u k tends to q 2 (see [4, Lemma 4.1, Corollary 4.1, Remark 4.1]). As a consequence, if the controls are not bounded, the infimum of the time for moving inside I q0 is zero, therefore we can think that, in some sense, if T is the minimum time for joining q 0 with q f , then it is also the infimum of the time for reaching q f from I q0 .

This digression suggests us the suitable coercivity assumption for this problem.

Assumption 6. For (ǫ, w(•)) ∈ R R × L 2 ([0, T ], R m ), let ζ(•)
be the solution of the control system

(3.13) ζ(t) = m i=1 w i (t) ġi t ( q 0 ) ζ(0) = R i=1 ǫ i f i ( q 0 ),
where f m+1 , . . . , f R are some locally defined vector fields chosen to complete the basis for Lie(f) in a neighborhood of q 0 . The quadratic form

(3.14) J ′′ [(ǫ, w(•))] 2 = 1 2 m i=1   T 0 2w i (t)L ζ(t) L ġi t β( q 0 ) + m j=1 w i (t)w j (t)L [ ġi t ,g j t ] β( q 0 ) dt   is coercive on the subspace W of R R × L 2 ([0, T ], R m ) defined by the constraint ζ( T ) = 0.
3.2. Consequences of the coercivity assumption. Let us now introduce a special coordinate frame in a neighborhood of q 0 , completing the set {f 1 , . . . , f m } with n -m locally defined vector fields f m+1 , . . . , f n such that {f 1 , . . . , f n } is a basis for T q M , and {f 1 , . . . , f R } is a basis for Lie(f), in a neighborhood of q 0 . The coordinate frame is the inverse of the map Υ : R n → M defined as

(3.15) Υ(x 1 , . . . , x n ) = exp(x 1 f 1 ) • exp(x 2 f 2 ) • • • • • exp(x n f n )( q 0 ).
In particular, Υ -1 ( q 0 ) = (0, . . . , 0), for j = 1, . . . , n we have ∂ ∂x j (0,...,0) = f j ( q 0 ) and

(3.16) L f x i ≡ 0 , ∀f ∈ Lie(f) , i = R + 1, . . . , n.
If we denote with ( p 1 , . . . , p n ) the coefficients of ℓ 0 in this coordinate frame, then it is easy to see that ℓ 0 = n i=R+1 p i dx i . Define the symmetric 2-form

Ω = 1 2 n i=R+1 dx i ⊗ dx i ,
and extend it on the whole

T q0 M × L 2 ([0, T ], R m ) putting Ω[(δx, w(•))] 2 = 1 2 n i=R+1 (δx i ) 2 .
Then, if Assumption 6 holds, we can apply [START_REF] Hestenes | Application of the theory of quadratic forms in Hilbert spaces to the calculus of variations[END_REF]Theorem 13.2] to conclude that there exists a ρ > 0 such that the form (3.17)

J ′′ ρ = J ′′ + ρΩ is coercive on the subspace W ∈ T q0 M × L 2 ([0, T ], R m )
of the variations such that the solutions of the system (3.11) satisfy

(3.18) ζ(0) ∈ T q0 M, ζ( T ) = 0.
Namely, J ′′ ρ represents the second variation of the linear-quadratic problem associated with the variable ζ, with free initial condition and fixed final condition.

The Hamiltonian H ′′ t : T * q0 M × T q0 M → R associated with this linear-quadratic problem is given by

(3.19) H ′′ t (ω, δx) = 1 2 L -1 λ(t)       ω, ġ1 t + L δx L ġ1 t β( q 0 ) . . . ω, ġm t + L δx L ġm t β( q 0 )       2 ,
where and L -1

λ(t)
has to be thought of as a quadratic form on R m , for every t (see [START_REF] Agrachev | An invariant second variation in optimal control[END_REF][START_REF] Chittaro | Singular extremals in multi-input time-optimal problem: a sufficient condition[END_REF]). Set (3.20)

L ′′ = {(-2ρΩ(δx, •), δx) : δx ∈ T q0 M }.
The quadratic form (3.17) is coercive on the space W if and only if (3.21) ker πH ′′ t | L ′′ = {0} for every t ∈ [0, T ] (see [START_REF] Stefani | Constrained regular LQ-control problems[END_REF]).

Geometry near the reference extremal

In this section we state the geometric properties of the vector fields and the Hamiltonians linked to our system and we define the super-Hamiltonian, stating its properties.

In a neighborhood of the reference extremal, Σ can be described as S × [-ǫ, ǫ] m , for some ǫ > 0. Indeed, for t = (t 1 , . . . , t m ) ∈ R m , let us denote with t F the vector field m i=1 t i F i , and let us consider the map ℓ → exp(t F )(ℓ) (that is, the solution at time t = 1 of the equation l = m i=1 t i F i (ℓ)). For a sufficiently small ǫ > 0, the map

ψ : (ℓ, t) ∈ U × [-ǫ, ǫ] m → exp(t F )(ℓ) ∈ T * M
is well defined and it is easy to prove the following: and that for each function F defined on U

(4.2) ∂ 2 titj (F • ψ)(ℓ, 0) = 1 2 L Fi L Fj + L Fj L Fi F (ℓ), i, j = 1, . . . , m.
We remark also that ψ maps Σ × [-ǫ, ǫ] m into Σ.

For singular extremals, the maximized Hamiltonian is well-defined and coincides with F 0 , but its associated Hamiltonian vector field is multi-valued: indeed, all the Hamiltonians of the form F 0 + m i=1 u i F i , u ∈ U , coincide and realize the maximum along any extremal contained in Σ. Moreover, no selection of such multi-valued Hamiltonian vector fields is suitable to construct the field of non-intersecting state-extremals that we will use to compare the costs associated with the candidate trajectories. For an insight in the single-input case, see [START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF]Section 4] . Then, as already done in [START_REF] Chittaro | Singular extremals in multi-input time-optimal problem: a sufficient condition[END_REF][START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF][START_REF] Stefani | Minimum-time optimality of a singular arc: second order sufficient conditions[END_REF], we substitute the maximized Hamiltonian F max with a the time-dependent super-Hamiltonian H t = H 0 + m i=1 u i (t)F i , where H 0 is defined as described below. The first step is to define a suitable map which turns out to project Σ onto S. Lemma 4.1. Possibly restricting U, there exist m smooth functions ϑ i : U → R, i = 1, . . . , m, such that, denoting with ϑ F (ℓ) the vector field

m i=1 ϑ i F i , the map φ : ℓ ∈ U → exp(ϑ F )(ℓ) ∈ U satisfies (4.3) φ(Σ) ⊂ S.
Moreover, for every ℓ ∈ S, δℓ ∈ T ℓ T * M , it holds

(4.4)    dϑ 1 (ℓ), δℓ . . . dϑ m (ℓ), δℓ    = L -1 ℓ    dF 01 (ℓ), δℓ . . . dF 0m (ℓ), δℓ    .
Proof. Let us consider the function Φ :

U × R m → R m defined by Φ(ℓ, t) =    F 01 • ψ(ℓ, t) . . . F 0m • ψ(ℓ, t)    .
Notice that for every ℓ ∈ S we have ψ(ℓ, 0) = ℓ and then Φ(ℓ, 0) = 0. Moreover, using (4.1), it is easy to show that ∂ t Φ(ℓ, 0) = -L ℓ , for all ℓ ∈ S, and then it has rank m. The implicit function theorem and the compactness of the interval [0, T ] ensure the existence of m smooth functions ϑ 1 , . . . , ϑ m , defined in a neighborhood of the reference extremal, such that (4.5)

F 0i • φ(ℓ) ≡ 0 , i = 1, . . . , m .
Without loss of generality, we can assume that this neighborhood is U. Since exp(ϑ F )(ℓ) ∈ Σ for every ℓ ∈ Σ, then (4.5) implies (4.3). Fix ℓ ∈ S; recalling that ϑ(ℓ) = 0, thanks to (4.5) and (4.1), we get for every δℓ ∈ T ℓ T * M and i = 1, . . . , m

0 = dF 0i (φ(ℓ)), ∂ ℓ ψ(ℓ, t)| t=ϑ(ℓ) δℓ + m j=1 dF 0i (φ(ℓ)), ∂ tj ψ(ℓ, t)| t=ϑ(ℓ) dϑ j (ℓ), δℓ = dF 0i (ℓ), δℓ + m j=1 F j0i (ℓ) dϑ j (ℓ), δℓ
and then (4.4). Remark 4.2. It is easy to see that, as a particular case of (4.4), we get

(4.6) dϑ i (ℓ), F j (ℓ) = -δ ij ∀ ℓ ∈ S, i, j = 1, . . . , m.
The Hamiltonian H 0 is defined by means of the map φ, as follows.

Definition 4.1. We define the Hamiltonian function H 0 : U → R as

H 0 (ℓ) = F 0 • φ(ℓ)
and we set χ = H 0 -F 0 .

In order to prove the properties of H 0 , we start by computing the first and second derivatives of χ on S. Proposition 4.2. For every ℓ ∈ S and δℓ ∈ T ℓ T * M , it holds dχ(ℓ), δℓ = 0 and

(4.7) d 2 χ(ℓ)[δℓ] 2 = - m r,s=1
(L -1 ℓ ) rs dF 0r (ℓ), δℓ dF 0s (ℓ), δℓ .

Proof. By definition we get

(4.8) dχ(ℓ) = dF 0 (φ(ℓ))   ∂ ℓ ψ(ℓ, t)| t=ϑ(ℓ) + m j=1 ∂ tj ψ(ℓ, t)| t=ϑ(ℓ) dϑ j (ℓ)   -dF 0 (ℓ) .
For ℓ ∈ S, by (4.1), we obtain dχ(ℓ) = dF 0 (ℓ) id + m i=1 F i (ℓ)dϑ i (ℓ) -dF 0 (ℓ) = 0. Therefore D 2 χ(ℓ) is a well defined quadratic form for every ℓ ∈ S. To prove (4.7), we perform the computations in any chart. Fix ℓ ∈ S and δℓ ∈ T ℓ T * M and recall (4.1), (4.2) and (4.4); from (4.8) it follows

D 2 χ(ℓ)[δℓ] 2 = D 2 F 0 (ℓ)[δℓ + m i=1 F i (ℓ) dϑ i (ℓ), δℓ ] 2 -D 2 F 0 (ℓ)[δℓ] 2 + + dF 0 (ℓ) ∂ 2 ℓ ℓ ψ(ℓ, 0) + m i=1 F i (ℓ)D 2 ϑ i (ℓ) [δℓ] 2 + + dF 0 (ℓ)   2 m i=1 ∂ 2 ℓ ti ψ(ℓ, 0)δℓ dϑ i (ℓ), δℓ + m i,j=1 ∂ 2 tj ti ψ(ℓ, 0) dϑ j (ℓ), δℓ dϑ i (ℓ), δℓ   = 2 m i=1 D 2 F 0 (ℓ)(δℓ, F i (ℓ)) + D F i (ℓ), δℓ dϑ i (ℓ), δℓ + + m i,j=1 D 2 F 0 (ℓ)( F i (ℓ), F j (ℓ)) + dF 0 (ℓ), ∂ 2 tj ti ψ(ℓ, 0) dϑ j (ℓ), δℓ dϑ i (ℓ), δℓ = 2 m i=1 L δℓ L Fi F 0 (ℓ) dϑ i (ℓ), δℓ + m i,j=1 ∂ 2 tj ti (F 0 • ψ)(ℓ, 0) dϑ j (ℓ), δℓ dϑ i (ℓ), δℓ = -2 m i=1 dF 0i (ℓ), δℓ dϑ i (ℓ), δℓ + m i,j=1 F ji0 (ℓ) dϑ j (ℓ), δℓ dϑ i (ℓ), δℓ = - m i,j=1 F ji0 (ℓ) dϑ j (ℓ), δℓ dϑ i (ℓ), δℓ = - m r.s=1 (L -1 ℓ ) rs dF 0r (ℓ), δℓ dF 0s (ℓ), δℓ .
Thanks to its definition, H 0 satisfies the following properties.

Theorem 4.1. The Hamiltonian H 0 has the following properties.

(1) F 0 = H 0 and F 0 = H 0 on S.

(2) The vector field H 0 is tangent to Σ.

(3) F 0 ≤ H 0 on Σ.

Proof. Since φ| S is the identity, then H 0 = F 0 on S. Moreover

dH 0 (ℓ) = dF 0 • ∂ ℓ ψ(ℓ, t)| t=ϑ(ℓ) + m i=1 ∂ ti ψ(ℓ, t)| t=ϑ(ℓ) dϑ i (ℓ) (4.9) = dF 0 • id + m i=1 F i (ℓ)dϑ i (ℓ) = dF 0 (ℓ),
since ϑ(ℓ) = 0 and F 0i (ℓ) = 0 on S. This ends the proof of (1).

To prove (2), fix ℓ ∈ Σ and observe that ∂ ti ψ(ℓ, t) ∈ Lie(f)(ψ(ℓ, t)), i = 1, . . . , m, so that by Assumption 5 we have

dF 0 (φ(ℓ)), ∂ ti ψ(ℓ, t)| t=ϑ(ℓ) = 0.
Therefore (4.9) leads to

dH 0 (ℓ) = dF 0 (φ(ℓ)) • ∂ ℓ ψ(ℓ, t)| t=ϑ(ℓ) , ℓ ∈ Σ,
and then we get easily 3) is a straight consequence of Proposition 4.2, since for all ℓ ∈ S, δℓ ∈ T ℓ S and i, j = 1, . . . , m, one gets

H 0 (ℓ) = ∂ ℓ ψ(ℓ, t)| t=ϑ(ℓ) -1 F 0 (φ(ℓ)). Since φ(ℓ) ∈ S, F 0 (φ(ℓ)) ∈ T φ(ℓ) Σ and ∂ ℓ ψ(ℓ, t)| t=ϑ(ℓ) -1 maps T φ(ℓ) Σ onto T ℓ Σ, then (2) is proved. Statement (
D 2 χ(ℓ)[δℓ] 2 = D 2 χ(ℓ)[δℓ, F i ] = 0 and D 2 χ(ℓ)[ F j , F i ] = -F ij0 .
We finally define the super-maximized Hamiltonian H t as follows. Definition 4.2. We denote with H t the following time-dependent Hamiltonian:

(4.10) H t (ℓ) = H 0 (ℓ) + m i=1 u i (t)F i (ℓ),
and with H t the Hamiltonian flow generated by H t .

Notice that H t is tangent to Σ and to the reference extremal λ(•).

The result

In this section we state and prove our main result. It relies on the following Hamiltonian sufficient conditions, that we state and prove here below.

Theorem 5.1 (Geometric sufficient condition). Let ( ξ, u, T ) be the an admissible triple for the minimum-time problem (1.1)-(1.2) with associate adjoint vector λ, and let Assumptions 1-5 be satisfied. Suppose that there exist a neighborhood V of q 0 and a smooth function a : V → R with the following properties: (i) da( q 0 ) = λ(0) (ii) the Lagrangian submanifold Λ = {da(q) : q ∈ V } is contained in Σ and satisfies

(5.1) ker π * H t * ∩ T λ(0) Λ = {0} ∀ t ∈ [0, T ].
Then ( ξ, u, T ) is a strict strong-local minimizer for the minimum-time problem (1.2) between I q0 and q f (or between q 0 and I q f ) and a strong-local minimizer for the minimum-time problem (1.2) between I q0 and I q f . Proof. Consider the map

id × π • H : (t, ℓ) ∈ [0, T ] × Λ → (t, π • H t (ℓ)) ∈ [0, T ] × M.
Hypothesis (ii) and the compactness of the reference trajectory imply that (possibly restricting V ) there exist a neighborhood O of the graph of ξ(•) in [0, T ] × Λ such that id × π • H is a diffeomorphism between [0, T ] × Λ and O.

Let (ξ, v, T ) be an admissible triple for the control system (1.2) such that its graph is contained in O, ξ(0) ∈ I q0 , ξ(T ) ∈ I q f , and T ≤ T , and denote its lift on Λ with ℓ(t), namely

ℓ(t) = (π • H t ) -1 (ξ(t)).
Let us choose a curve µ 0 : [0, 1] → Λ joining ℓ 0 with ℓ(0) satisfying πµ 0 (t) ∈ I q0 , ∀ t ∈ [0, 1], and a curve

µ f : [T, T ] → Λ joining ℓ 0 with ℓ(T ) satisfying π • H t (µ f (t)) ∈ I q f , ∀ t ∈ [T, T ].
Let us now define the following paths in [0, T ] × Λ:

γ 1 = (t, ℓ 0 ) t ∈ [0, T ] γ 2 = (0, µ 0 (t)) t ∈ [0, 1] γ 3 = (t, ℓ(t)) t ∈ [0, T ] γ 4 = (t, µ f (t)) t ∈ [T, T ],
and

let γ = (-γ 1 ) ∪ γ 2 ∪ γ 3 ∪ γ 4 . Consider the following 1-form on [0, T ] × T * M (5.2) ω(t, ℓ) = H * t ς -H t • H t (ℓ)
dt, where ς is the canonical Liouville form on T * M . It is easy to prove (see [START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF]Proposition 17.1]) that ω is exact on [0, T ] × Λ. In particular, since γ is a closed path contained in [0, T ] × Λ, then γ ω = 0. Let us now evaluate the single components of this integral. It is easy to see that

γ1 ω = γ2 ω = 0. Moreover γ3 ω = T 0 H t (ℓ(t)), ξ(t) -H t • H t (ℓ(t)) dt = m i=1 T 0 H t (ℓ(t)), (v i (t) -u i (t))f i (ξ(t)) dt - T 0 χ • H t (ℓ(t)) dt ≤ 0. Therefore 0 ≤ γ4 ω = T T H t (ℓ(t)), π * • H t * μf (t) dt - T T H t (H t (µ f (t))) dt. The first term is zero, since π * • H t * μf (t) is tangent to I π•Ht(µ f (t))
, by construction, and

H t (ℓ(t)) is contained in Σ. Then 0 ≤ T T H t (H t (µ f (t))) dt = T T 1 + O(t) dt ≤ (T -T ) + o(T -T ),
which is a contradiction, therefore T ≥ T .

If the final point q f is fixed, we claim that the reference extremal is strictly optimal. To prove the claim, we consider an admissible triple (ξ, v, T ) as above, such that T = T and ξ(T ) = q f . In particular, since in this case γ4 ω = 0, we obtain that

0 = γ3 ω = - T 0 χ • H t (ℓ(t)) dt,
which implies that λ(t) = H t (ℓ(t)) ∈ S for every t ∈ [0, T ], then, in particular, that λ(t) ∈ T λ(t) S, that is dF 0j (λ(t)), λ(t) = 0 for j = 1, . . . , m. By computations it is possible to show that

λ(t) = -→ F t (λ(t)) + m i=1 (v i (t) -u i (t)) H t * (π • H t ) -1 * f i (ξ(t)).
Thanks to (5.1), possibly restricting V , we can find a family of smooth functions a t : V t → R, where V t is a neighborhood of ξ(t) and a 0 = a, such that H t (Λ) = {da t (q) : q ∈ V t } for every t ∈ [0, T ]. In particular, for every t ∈ [0, T ] we have that

λ(t) = da t (ξ(t)) H t * (π • H t ) -1 * f i (ξ(t)) = da t * f i (ξ(t)), i = 1, . . . , m. Then dF 0j (λ(t)), H t * (π • H t ) -1 * f i (ξ(t)) = σ(da t * f i (ξ(t)), F 0j (λ(t))) = L fi L f0j a t (ξ(t)) = L f0j L fi a t (ξ(t)) + L fi0j a t (ξ(t)) = λ(t), f i0j (ξ(t)) , since L fi a t (ξ(t)) is identically null, being H t (Λ) = da t (V t
) contained in Σ. This implies that, for every j = 1, . . . , m, it holds

0 = dF 0j (λ(t)), λ(t) = F 00j (λ(t)) + m i=1 v i (t)F i0j (λ(t)),
that is, in particular, that v is a solution of equation (2.16), and therefore λ(t) = F S (λ(t)). Since λ(t) is solution of the same equation, and both λ and λ pass through q f , then they coincide.

The same argument shows that the reference triple is a strict strong-local minimizer for the minimum-time problem (1.2) between q 0 and I q f . Now we state and prove the main result. Theorem 5.2. Let ( ξ, u, T ) be an admissible triple of the minimum-time problem (1.1)-(1.2) with associate adjoint vector λ, and let λ be a normal singular extremal. If Assumptions 1-6 are satisfied, then ξ(•) is a minimum-time trajectory between I q0 and I q f , and hence between N 0 and N f . Moreover, the reference trajectory is strictly optimal among all admissible trajectories between q 0 and I q f and among all admissible trajectories between I q0 and q f . Proof. The thesis comes straightaway once proved that the coercivity assumption (Assumption 6) allows us to define a smooth function α ρ that satisfies the hypotheses of Theorem 5.1. In particular, we define α ρ in the adapted coordinates (3.15) of Section 3.2 as follows:

α ρ (x) = n i=R+1 p i x i + ρ 2 n i=R+1 x 2 i .
It is easy to see that α ρ satisfies property (i) and that (3.16) implies that Λ is a Lagrangian submanifold contained in Σ. To prove (5.1) we need to exploit the links between the flow of the Hamiltonian H ′′ t defined in equation (3.19) and H t * , as done in [START_REF] Chittaro | Singular extremals in multi-input time-optimal problem: a sufficient condition[END_REF][START_REF] Poggiolini | Bang-singular-bang extremals: sufficient optimality conditions[END_REF][START_REF] Stefani | Strong optimality of singular trajectories[END_REF]. It is known that the pull-back flow [START_REF] Marsden | Introduction to Mechanics and Symmetry: A Basic Exposition of Classical Mechanical Systems[END_REF]). Since DG t ( ℓ 0 ) = 0, then

G t = F -1 t • H t is the Hamiltonian flow relative to the Hamiltonian G t : T * M → R defined by G t = H t -F t • F t = χ • F t (see
G ′′ t = 1 2 D 2 G t | ℓ0 is a well defined quadratic form and its associated Hamiltonian flow is G t * : T ℓ0 (T * M ) → T ℓ0 (T * M ). Let β = - n i=R+1 p i x i ; then the linear map ι : T * q0 M × T q0 M → T ℓ0 (T * M ) as follows ι(ω, δx) = -ω + d(-β) * δx
establishes an anti-symplectic isomorphism between T * q0 M × T q0 M and T ℓ0 (T * M ). In particular, it determines an equivalence between the Hamiltonian functions G ′′ t and H ′′ t , i.e. the following identities hold:

H ′′ t = -G ′′ t • ι (5.3) -→ H ′′ t = ι -1 • -→ G ′′ t • ι H ′′ t = ι -1 • G t * • ι. (5.4)
We need to prove only (5.3), since the other two equations are a direct consequence (see [START_REF] Chittaro | Singular extremals in multi-input time-optimal problem: a sufficient condition[END_REF] and references therein for details).

Consider ℓ ∈ S, δℓ ∈ T ℓ (T * M ), and set ℓ t = F t (ℓ). Then, thanks to (4.7), we have that

D 2 G t (ℓ)[δℓ] 2 = D 2 χ(ℓ t ) • F t * ⊗ F t * = - m r.s=1 (L -1 ℓt ) rs dF 0r (ℓ t ), F t * δℓ dF 0s (ℓ t ), F t * δℓ = -( dF 01 (ℓ t ), F t * δℓ , . . . , dF 0m (ℓ t ), F t * δℓ )(L -1 ℓt )    dF 01 (ℓ t ), F t * δℓ . . . dF 0m (ℓ t ), F t * δℓ    = -2H ′′ t • ι -1 δℓ.
By computations, it is easy to see that the space L ′′ defined in equation (3.20) satisfies the equality ιL ′′ = {dα ρ * δx : δx ∈ T q0 M } = L, therefore equations (3.21) and (5.4) imply

ker π * G t * | L = {0} ∀ t ∈ [0, T ].
To end the proof it is sufficient to notice that F t * is an isomorphism on the vertical fibers, since it comes from a lifted Hamiltonian.

Examples

The classical Dubins and dodgem car problems concern the motion of a car on the plane R 2 with constant speed and controlled (bounded) angular velocity (see for instance [START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF][START_REF] Craven | Control and optimization. Chapman & Hall mathematics series[END_REF]). In particular, Dubins problem looks for minimum-time trajectories between fixed initial and final positions and orientations, while in the dodgem car problem the final orientation is free.

As shown in [START_REF] Jurdjevic | Variational problems on Lie groups and their homogeneous spaces: elastic curves, tops, and constrained geodesic problems[END_REF] (see also [START_REF] Chittaro | Minimum-time strong optimality of a singular arc : extended dubins problem[END_REF]), this problem can be reformulated on the manifold R 2 × SO(2), where SO(2) is the group of positively oriented rotations on R 2 . A great advantage of this formulation is that the extension to higher dimensions is straightforward: we denote with (q, R) the elements of R N × SO(N ), where SO(N ) is the group of positively oriented rotations on R N , and we consider the control system (6.1)

q(t) = R(t)e 1 Ṙ(t) = N -1 j=1 u j (t)R(t)A j , |u| ≤ 1,
where e 1 is the first element of the canonical basis of R N , and, for every j = 1, . . . , N -1, A j is the anti-symmetric matrix defined by

(A j ) lm =      -1 if l = 1, m = j + 1 1 if l = j + 1, m = 1 0 otherwise.
This system models the motion of a point in the N -dimensional space with constant speed equal to 1, where we control the orientation velocity. For both Dubins and dodgem car problems, the initial condition consists in fixing the initial point q 0 and the initial (unit length) velocity v 0 of the trajectory on R N . Namely, N 0 = {q 0 } × I v0 , where

I v = {S ∈ SO(N ) : Se 1 = v}. Dubins problem looks for minimum-time trajectories joining N 0 with N f = {q f } × I v f , for some fixed q f ∈ R N , v f ∈ R N with |v f | = 1, while dodgem car problem searches minimum-time trajectories from N 0 to N f = {q f }× SO(N ), for some fixed q f ∈ R N .
The system (6.1) can be embedded in the matrix group GL(N + 1) (non singular (N + 1)dimensional matrices), via the map

(q, R) ∈ R N × SO(N ) → g = 1 0 q R ∈ GL(N + 1).
This formulation is suitable also to consider the Dubins problem on other homogeneous spaces different from R N , that is the N -dimensional sphere S N and the N -dimensional hyperbolic space H N , defined as

H N = {x ∈ R N +1 : -x 2 0 + N i=1 x 2 i = 1, x 0 > 0}.
Briefly, a pair (point,orientation) in S N × SO(N ) can be represented in the group G = SO(N + 1) in the following way: the first column of the matrix g ∈ SO(N + 1) gives the coordinate representation (in R N +1 ) of the point, the other N columns determine an orthonormal frame in the tangent space to the sphere at the point. Analogously, a pair (point,orientation) in H N × SO(N ) can be represented in the group G = SO(1, n), as above: the first column of the matrix g gives the coordinate representation (in R N +1 ) of the point, while the other N columns determine an orthonormal frame in the tangent space. More details on these representations can be found in Appendix B and in [START_REF] Jurdjevic | Geometric Control Theory[END_REF][START_REF] Jurdjevic | Variational problems on Lie groups and their homogeneous spaces: elastic curves, tops, and constrained geodesic problems[END_REF], where the authors study the geodetic problem for curves with bounded curvature.

We can then write Dubins problem on M ∈ {R n , S N , H N } in the following unified way:

(6.2) min T subject to (6.3)          ġ(t) = g(t) 0 -εe T 1 e 1 0 + N -1 i=1 u i (t)g(t) 0 0 0 A i , |u| ≤ 1 g ∈ G g(0) ∈ N 0 , g(T ) ∈ N f ,
where G, ε and the manifolds of the constraints depend on the manifold M as shown below:

M ε G N 0 N f R N ε = 0 R N ⋊ SO(N ) g : ge 1 = 1 q 0 , ge 2 = 0 v 0 g : ge 1 = 1 q f , ge 2 = 0 v f S N ε = 1 SO(N + 1) {g : ge 1 = q 0 , ge 2 = v 0 } {g : ge 1 = q f , ge 2 = v f } H N ε = -1 SO(1, N ) {g : ge 1 = q 0 , ge 2 = v 0 } {g : ge 1 = q f , ge 2 = v f }
where e i denotes the i-th element of the canonical basis of R N +1 . The control system (6.3) is a control-affine system of the form (1.2) with m = N -1 and dim M = N (N + 1)/2, and the corresponding left-invariant vector fields are defined as f i (g) = gA i , i = 0, . . . , N -1. We recall that left invariant vector fields satisfy the following relation:

g[A i , A j ] = [f i , f j ](g)
, where [•, •] denotes also the usual matrix commutator. Thanks to this equation, the commutation properties of the matrices A i extend also to their associated leftinvariant vector fields. In particular, the following properties are easily verified:

(i) Lie({A i : i = 1, . . . , N -1) is 2-step bracket-generating and isomorphic to so(N ) (Lie algebra of antisymmetric N -dimensional matrices); so(N ) has dimension R = N (N -1)/2. (ii) the matrices {[A i , A j ] : i, j = 1, . . . , N -1} generate the derived sub-algebra [so(N ), so(N )],

which is isomorphic to so(N -1) and has dimension (N -1)(N -2)

2

(iii) the matrices {A 0 , [A 0 , A i ], A i , [A i , A j ] : i < j = 1, . . . , N -1} are linearly independent and form a basis for the Lie algebra of G. (iv) for i, j = 1, . . . , N -1 the matrix commutators of the kind [A i , [A j , A 0 ]] satisfy the following relations:

[A i , [A i , A 0 ]] = -A 0 [A i , [A j , A 0 ]] = 0 if i = j.
(v) the matrices {A 0 , A 01 , . . . , A 0m } mutually commute. (vi) A 0 commutes with every element of {[A i , A j ] : i, j = 1, . . . , N -1}.

We notice that the submanifolds N 0 and N f are integral manifolds of the derived sub-algebra {[f i , f j ] : i, j = 1, . . . , m}. Indeed, it is easy to verify that the Lie sub-algebra is contained in the tangent spaces of N 0 and N f ; a dimensional computation proves the claim.

Let us now consider singular extremal for the problem (6.2)- (6.3). First of all, we remark that this problem does not admit abnormal singular extremals, thanks to property (iii). Moreover, thanks to property (v) and from equation (2.13), we get that the reference control u(•) is identically zero, and that the matrix L λ(t) = -F 0 ( λ(t))I n . In particular, singular trajectories are the integral curves of the drift f 0 ; with each of these curves we associate the adjoint vector p(t) that satisfies the differential equation ṗ(t) = -p∂ q f 0 , with initial condition p(0) ∈ {f i , f ij , f 0i : i, j = 1, . . . , n -1} ⊥ and p(0), f 0 = 1 (thanks to (iii), these conditions uniquely define p(0)). It is easy to prove that the pair (p(t), q(t)) is a normal singular extremal for both Dubins and dodgem car problems, and that it satisfies Assumptions 1-5; in particular L λ(t) = -I n . Remark 6.1. We stress that even if in this problem we consider bounded controls, nevertheless we do not need to strengthen the natural optimality conditions. Indeed, High Order Goh condition reduces to Goh condition; moreover, when considering the second variation, the linear quadratic problem (3.10)-(3.11)-(3.12) coincides with (3.14)-(3.13), since the tangent space to N 0 is in direct sum with the linear span of the controlled vector fields and their sum coincides with the Lie algebra of the controlled vector fields.

We now compute explicitly the second variation. First of all, we compute the space W of the admissible variations, that is we shall solve the Cauchy problem for ζ(t), (3.11)-(3.12).

Since the reference controls are null, the reference flow reduces to S t = exp(tf 0 ). The time derivatives of the pull-back vector fields give

ġi t ( q 0 ) = exp (-tf 0 ) * f 0 , f i • exp(tf 0 )( q 0 ) = exp (-tf 0 ) * (f 0i ) • exp(tf 0 )( q 0 ) gi t ( q 0 ) = exp (-tf 0 ) * f 0 , f 0i • exp(tf 0 )( q 0 ) = exp (-tf 0 ) * (f 00i ) • exp(tf 0 )( q 0 ) = 0,
then ġi t ( q 0 ) = ġi 0 ( q 0 ) = f 0i ( q 0 ) for every t ∈ [0, T ] and every i = 1, . . . , N -1, and then g i t ( q 0 ) = f i ( q 0 ) + tf 0i ( q 0 ). The solution of (3.11)-(3.12) is then

ζ(t) = N (N -1)/2 i=1 ǫ i f i ( q 0 ) + N -1 i=1 t 0 w i (s) ds f 0i ( q 0 ).
From the boundary condition ζ( T ) = 0 and from (v) we get that the admissible variations (ǫ, w(•)) ∈ W satisfy the constraints (6.4)

T 0 w i (t) dt = 0 i = 1, . . . , N -1 ǫ j = 0 j = 1, . . . , N (N -1) 2 , then ζ(t) = N -1 i=1 t 0 w i (s) ds f 0i ( q 0 ).
Then the quadratic form (3.14) is given by

J ′′ [(0, w)] 2 = 1 2 N -1 i=1 T 0 w i (t) 2 dt + N -1 i,j=1 T 0 w i (t) t 0 w j (s) ds L f0j L f0i β( x 0 ) dt.
Integrating by parts the second term and thanks to conditions (6.4) we get

J ′′ [(0, w)] 2 = 1 2 w 2 L 2 + 1 2 N -1 i=1 T 0 w i (t) dt 2 = 1 2 w 2 L 2 .
Therefore the second variation is coercive.

Remark 6.2. In this paper we considered the second variation associated with the sub-problem with fixed final point, and we proved that its coercivity is a sufficient condition for the optimality also if the final condition is not fixed. In particular, this implies that sufficient optimality conditions for Dubins' problem are also sufficient for the optimality of the extremal in dodgem car problem. We would like to remark that, in the example considered in this section, the extended second variation associated with the original boundary conditions is not coercive. Indeed, the final constraint g( T ) ∈ N f imposes the constraint ζ( T ) ∈ S -1

T * (T g( T ) N f ). In particular, since N f is an integral manifold of the derived sub-algebra {[f i , f j ] : i, j = 1, . . . , N -1}, then T g( T ) N f = {[f i , f j ](g( T )) : i, j = 1, . . . , N -1} and, by (vi) and the fact that the reference flow is the flow associated with the drift, it turns out that S

-1 T * (T g( T ) N f ) = {[f i , f j ](g(0)) : i, j = 1, . . . , N -1}.
It is easy to prove that any non-zero variation of the form (ǫ, w ≡ 0) with ǫ i = 0 for i ≤ N -1 is admissible for the problem with final constraint N f , but J ′′ [(ǫ, 0)] 2 = 0.

Therefore, W is the maximal subspace of variations where we can require coercivity of the extended second variation.

It is clear that u

t L ∞ is uniformly bounded for t ∈ B δ ( t). Let u 0 ∈ L ∞ ([0, 1], R m ) be the control map which satisfies S(1, 0, q, u 0 )) = exp (-t1 f i1 ) • • • • • exp (-tR f iR ) (q), so that S(1, 0, b, u 0 )) = a and u 0 L ∞ = u t L ∞ . For t ∈ B δ ( t), let us consider the control map ν t ∈ L ∞ ([0, 2], R m ) defined as ν t : s → u t (s) ∀ s ∈ [0, 1] u 0 (s -1) ∀ s ∈ (1, 2].
By definition there exists an M > 0 such that ν t L 1 ([0,2]) ≤ M for every t ∈ B δ ( t); moreover, possibly restricting δ, the map t ∈ B δ ( t) → S(2, 0, a, ν t ) is well defined and covers a compact neighborhood U of a in I a contained in the local coordinate chart.

For ǫ > 0, we define the control variation ν t,ǫ ∈ L 1 ([0, 2], R m ) as

(A.3) ν t,ǫ (s) = ǫ -1 ν t (sǫ -2 ) ∀ s ∈ [0, 2ǫ 2 ] 0 ∀ s ∈ (2ǫ 2 , 2],
and the control function

(A.4) ν t,ǫ (s) = u(s + s) + ν t,ǫ (s) ∀ s ∈ [0, 2ǫ 2 ] u(s + s) ∀ s ∈ [-s, 0) ∪ (2ǫ 2 , T -s]. It is easy to see that ν t,ǫ L 1 = ǫ ν t L 1 ≤ M ǫ and that (A.5) S(2ǫ 2 , 0, a, ν t,ǫ ) = ǫ S(2, 0, a, ν t ).
It is clear that ν t,ǫ satisfies property (1) of Lemma A.1. To prove the other properties, consider the pull-back system η(s) = S -1 s+s,s • S(s + s, s, q, ν t,ǫ ), which is solution of the following Cauchy problem

(A.6) η(s) = m i=1 ν i t,ǫ (s) S -1 s+s,s * f i • S s+s,s (η(s)) η(0) = q,
where ν i t,ǫ denotes the i-component of ν t,ǫ . Since ν t,ǫ L 1 ≤ M ǫ, possibly restricting δ, there exist ǭ ∈ (0, 1) and a neighborhood V of a such that η(2ǫ 2 ) belongs to U , for all q ∈ V , t ∈ B δ ( t) and ǫ ∈ [0, ǭ].

Fix t ∈ B δ ( t). It is not difficult to verify that the map ǫ ∈ [0, ǭ] → ν t,ǫ is strongly continuous in L 1 ([0, 2], R m ); therefore, (2) and (3) of Lemma A.1 are consequences of the properties of system (A.6), see [START_REF] Mcshane | Unified Integration[END_REF].

Finally, to verify property (4), we consider the system (A.6) with initial condition η(0) = a and the system (A.1) with the same initial condition and control map u = ν t,ǫ . We get

d ds |η(s) -ζ(s)| ≤ m i=1 |ν i t,ǫ (s)| |( S -1 s+s,s ) * f i • S(s + s, s, η(s)) -f i (ζ(s))| ≤ m i=1 |ν i t,ǫ (s)| |f i (η(s)) -f i (ζ(s))| + |( S -1 s+s,s ) * f i • S(s + s, s, η(s)) -f i (η(s))|
Possibly restricting ǭ and δ, η(s) and ζ(s) belong to the compact neighborhood U , therefore there exists a constant C > 0 such that Since ζ(2ǫ 2 ) = ǫ S(2, 0, a, ν t ) and S(2, 0, a, ν t ) covers a neighborhood of a in R R , Lemma A.1 is proved.

d ds |η(s) -ζ(s)| ≤ C m i=1 |ν i t,ǫ (
Appendix B. Orthonormal frame bundles on canonical space forms

In this section we give more details about the lifting of Dubins' and dodgem car problem on Lie groups. For details, we refer to [START_REF] Jurdjevic | Geometric Control Theory[END_REF][START_REF] Jurdjevic | Variational problems on Lie groups and their homogeneous spaces: elastic curves, tops, and constrained geodesic problems[END_REF] and references therein.

Let M ∈ {R n , S n , H n }. We recall that the hyperbolic space H n is defined as H n = {x ∈ R n+1 : -x 2 0 + n i=1 x 2 i = 1, x 0 > 0}. The manifolds R n and S n inherit a natural Riemannian structure from R n and R n+1 , respectively. As for H n , its Riemannian metric is given by the Lorentzian quadratic form x, y = -x 0 y 0 + n i=2 x i y i . The Dubins' problem on M can be lifted to a minimum-time problem on the bundle of positiveoriented orthonormal frames on M , denoted with F + (M ), as we show below.

For M = R n , let us fix some positively oriented orthonormal frame {e 1 , . . . , e n } attached at the point q = 0 in R n . Given a point q ∈ R n and a positively oriented orthonormal frame {v 1 , . . . , v n } attached at q, we can associate to them a pair (x, R) ∈ R n × SO(R n ), where x denotes the coordinate representation of q with respect to the basis {e 1 , . . . , e n }, and v i = Re i for every i = 1, . . . , n. In other words, the bundle of positively oriented orthonormal frames can be identified with the orbit through (0, {e 1 , . . . , e n }) of the semi-direct product G = R n ⋊ SO(R n ), that is the group of pairs (x, R) ∈ R n × SO(R n ) equipped with the operation (x, R) • (y, S) = (x + Ry, RS). This construction provides a coordinate system on F + (R n ). Moreover, every element (x, R) ∈ G can be represented by the following matrix g ∈ GL n+1 (R)

g =      1 0 . . . 0 x 1 . . . R x n      .
As the manifolds S n and H n are embedded in R n+1 , we can repeat the same construction and find some group G such that all the elements of F + (M ) are given by the orbit of G through some fixed orthonormal frame {e 1 , . . . , e n+1 } of R n+1 centered at some fixed point x 0 .

Indeed, every point q ∈ S n can be represented with respect to the canonical basis {e 1 , . . . , e n+1 } by a unit vector x ∈ R n+1 . The tangent space to S n at q is given by the span of n unit vectors (v 1 , . . . , v n ) ∈ R n+1 orthogonal to x. A choice of these unit vectors determines an orthonormal frame on the tangent space. Therefore, the bundle F + (S n ) can be regarded as the orbit of SO(n+1) applied to the standard orthonormal frame {e 1 , . . . , e n+1 } of R n+1 , in the following way: to a frame {v 1 , . . . , v n } attached at a point q ∈ S n there corresponds the matrix g ∈ SO(n + 1) such that the coordinates of q are given by x = ge 1 and v i = ge i+1 , i = 1, . . . , n, that is

g =    x 1 v 1 1 . . . v 1 n . . . . . . x n+1 v n+1 1 . . . v n+1 n   
(here x j and v j i denote respectively the j-th component of the vectors x and v i ). For what concerns the hyperboloid H n , we consider the Lorentz group SO(1,n), defined as the group of transformation that preserve the (n + 1)-dimensional matrix

I(1, n) = -1 0 . . . 0 0 I n ,
where I n is the n-dimensional identity matrix. It can be proved as above that the bundle F + (H n ) can be identified with the connected component SO 0 (1,n) of SO(1,n) that contains the group identity.

For any M ∈ {R n , S n , H n }, the tangent vector fields in F + (M ) are identified with the leftinvariant vector fields on the isometry group of M , which is respectively R n ⋊ SO(R n ) for R n , SO(n + 1)/SO(n) for S n and SO(1,n) for H n . Therefore, we can prove that the tangent vectors are of the form where ǫ = 0 for M = R n , ǫ = 1 for M = S n and ǫ = -1 for M = H n , U is an anti-symmetric matrix of dimension n, and g is the element of F + (M ) where the vector is attached.

Let γ be a curve in M . When lifting γ to a curve of orthonormal frames, that is to a curve g(t) ∈ G such that its projection on M coincides with γ, it is possible to choose the lifted curve in such a way that the first element v 1 (t) of the frame attached at γ(t) is equal to γ(t). In particular, this sets a 1 = 1 and a j = 0 for j ≥ 2 in equation (B.1). This kind of lifting is called Darboux frame.

There is still a freedom of choice of the form of the matrix U in equations (B.1). Systems with the form (6.3) are called Serret-Frenet curves (see [START_REF] Jurdjevic | Geometric Control Theory[END_REF][START_REF] Jurdjevic | Variational problems on Lie groups and their homogeneous spaces: elastic curves, tops, and constrained geodesic problems[END_REF] and references therein).

Remark 2 . 1 .

 21 Let us recall that the following relation between the Lie brackets of two vector fields f, g and the Poisson brackets of their associated Hamiltonian functions holds: ℓ, [f, g](πℓ) = {F, G}(ℓ).

  .10) where the function ζ : [0, T ] → T q0 M is the solution of the equation (3.11) ζ(t) = m i=1

Proposition 4 . 1 .Remark 4 . 1 .

 4141 Possibly restricting U, there exists an ǫ > 0 such that ψ :S × [-ǫ, ǫ] m → Σ is a diffeomorphism.Proof. Since the whole Lie algebra generated by the F i is tangent to Σ, then the range of the map ψ restricted to S × [-ǫ, ǫ] is contained in Σ. The thesis follows by compactness of the interval [0, T ], since Dψ(ℓ, 0) = id × ( F 1 (ℓ), . . . , F m (ℓ)) has maximal rank (see property (P3) at the end of Section 2). It is easy to see that (4.1)∂ ti ψ(ℓ, 0) = F i (ℓ), i = 1, . . . , m.

2 0

 2 s)||η(s) -ζ(s)| + Cǫ -1 s. By Gronwall inequality we obtain |η(2ǫ 2 ) -ζ(2ǫ 2 ))| ≤ e CMǫ 2ǫ Cǫ -1 s ds = 4Ce CMǫ ǫ 3 . so that η(2ǫ 2 ) = ζ(2ǫ 2 ) + o(ǫ).

(

This work was supported by Digiteo grant Congeo; by the ANR project GCM, program "Blanche", project number NT09 504490; by the European Research Council, ERC StG 2009 "GeCoMethods", contract number 239748; by PRIN 200894484E 002 ; and by the research fund CARTT, IUT Toulon-La Garde.

Appendix A. Necessity of HOGC This section is devoted to prove that HOGC is a necessary optimality condition. To be more precise we prove the following result.

Theorem A.1. Let U = R m and let ( ξ, u, T ) be an optimal triple for the problem (1.1)- (1.2). Then there exists an adjoint covector λ : [0, T ] → T * M , such that

Francesca Chittaro and Gianna Stefani

This theorem is already known when the reference control is smooth (see [START_REF] Bianchini | A High Order Maximum Principle[END_REF]); here we remove the smoothness hypothesis. The proof follows the outlines of the so called "higher order maximum principles" based on the "good" needle-like control variations; in particular we use the results contained in [START_REF] Bianchini | Good needle-like variations[END_REF][START_REF] Bianchini | Variational cones and high-order maximum principles[END_REF][START_REF] Bianchini | Variational approach to some optimization control problems[END_REF], where most of the other conditions are also analyzed.

A necessary condition for the trajectory ξ to be time optimal is that ξ(t) belongs to boundary of the reachable set from q 0 at each time t ∈ [0, T ] (see for instance [START_REF] Bianchini | Variational approach to some optimization control problems[END_REF]). Therefore, it is not difficult to see that Theorem A.1 follows, if we prove that Lie ξ(t) (f) is a local regular tangent cone to the reachable set at ξ(t), for every t ∈ [0, T ] (see [START_REF] Bianchini | Good needle-like variations[END_REF], [START_REF] Bianchini | Variational approach to some optimization control problems[END_REF]Proposition 3.3] and the references therein). Namely, following [START_REF] Bianchini | Good needle-like variations[END_REF], it is sufficient to prove that, for every Lebesgue point s ∈ [0, T ] of the reference control u, there exists c > 0 such that cf ( ξ(s)) is a g-variations of ( ξ, u) at s, for all f ∈ Lie(f).

We start by fixing some notations. We denote with S(t, t 0 , q 0 , v) the solution at time t of the control problem (1.2) associated with the control function v, with initial condition at t 0 equal to q 0 . Moreover, we use the notation S t,t0 (q 0 ) = S(t, t 0 , q 0 ) = S(t, t 0 , q 0 , u), where u is the reference control.

Applying the results in [START_REF] Bianchini | Good needle-like variations[END_REF] and, in particular, putting together Definition 2.1, Definition 2.3 and Proposition 2.4 therein, it is easy to see that if Lemma A.1 below holds true, then cf ( ξ(s)) is a right g-variation of order 2 of ( ξ, u) at s. As a consequence, Lemma A.1 proves Theorem A.1.

Lemma A.1. Let s ∈ [0, T ] be a Lebesgue point for u. Then there exist positive numbers c, N , ǭ such that for every f ∈ Lie(f) there exists a family of control maps

(2) There exists a neighborhood V of ξ(s) such that the map

Proof. Let us consider the driftless control system

denoting its solutions at time t, relative to the control u, and with initial condition ζ(t 0 ) = ζ 0 , as S(t, t 0 , ζ 0 , u). Set a = ξ(s). We perform the proof in an adapted coordinate frame centered at a, analogous to the frame (3.15) described in Section 3. In this frame a = 0, T a I a = R R and I a is a neighborhood of 0 in R R , that we call I a in what follows.

If t = ( t1 , . . . , tR ) is sufficiently small, there exist a choice of R vector fields {f i1 , . . . , f iR } ∈ {f 1 , . . . , f m } such that the map

has maximal rank at t = t (see [START_REF] Krener | A generalization of Chow's theorem and the bang-bang theorem to nonlinear control problems[END_REF]Theorem 1]). This implies that there exist a δ > 0 and a small neighborhood of

2) is invertible between the ball of radius δ centered in t, denoted as B δ ( t), and the neighborhood of b.

For t ∈ R R , let us rewrite the map (A.2) as S(1, 0, a, u t ), for the piecewise-constant control u t ∈ L ∞ ([0, 1], R m ), defined, for j = 1, . . . , m, by