Luc Miller
email: miller@math.polytechnique.fr

THE CONTROL TRANSMUTATION METHOD AND THE COST OF FAST CONTROLS *

Keywords: Controllability, fast controls, control cost, transmutation, cosine operator function, heat equation, linear Ginzburg-Landau equation AMS subject classifications. 93B05, 93B17, 47D09

) are set in a Banach space, B is an admissible unbounded control operator, and A is a generator of cosine operator function.

The control transmutation method explicits the input function u of (1) in terms of the input function v of (2):

, where the compactly supported kernel k depends on T and L only. It proves roughly that the norm of a u steering the system (1) from an initial state x(0) = x 0 to the final state x(T ) = 0 grows at most like x 0 exp(α * L 2 /T ) as the control time T tends to zero. (The rate α * is characterized independently by a one-dimensional controllability problem.)

In the applications to the cost of fast controls for the heat equation, L is roughly the length of the longest ray of geometric optics which does not intersect the control region.

1. Introduction. This paper concerns the relationship between the null-controllability of the following first and second order controllable systems:

ẋ(t) = e iθ Ax(t) + Bu(t) (t ∈ R + ), x(0) = x 0 , (1.1)
z(t) = Az(t) + Bv(t) (t ∈ R), z(0) = z 0 , ż(0) = 0, (1.2)
where x and z are the systems trajectories in the Banach space X, x 0 and z 0 are initial states, u and v are input functions with values in the Banach space U , A is an unbounded generator, B is an unbounded control operator, θ is a given angle in ] -π/2, π/2[, each dot denotes a derivative with respect to the time t and R + = [0, ∞) (the detailed setting is given in §2). Equation (1.1) with u = 0 describes an irreversible system (always smoothing) and we think of it as a parabolic distributed system with infinite propagation speed. Equation (1.2) with v = 0 describes a reversible system (e.g. conservative) and we think of it as a hyperbolic distributed system with finite propagation speed.

For example, if A is the negative Laplacian on a Euclidean region and the input function is a locally distributed boundary value set by B, then (1.2) is a boundary controlled scalar wave equation and (1.1) with θ = 0 is a boundary controlled heat equation ( §6 elaborates on this example). Thus, this paper applies to the controllability of the diffusion equation that models the propagation of heat in a media at rest when the temperature does not vary too much. This diffusion equation is also a simplified model for various physical phenomena in neutronics, viscous fluids mechanics and electromagnetism when A is a more general coercive symmetric second-order elliptic operator (cf. §I.B.1.1 in [START_REF] Dautray | Mathematical analysis and numerical methods for science and technology[END_REF]). If θ = 0, then (1.1) interpolates between the heat equation and the Schrödinger equation. Thus, this paper applies to the controllability of the linear part of the complex Ginzburg-Landau equation which describes a vast variety of physical phenomena from nonlinear waves to second-order phase transitions, from superconductivity, superfluidity, and Bose-Einstein condensation to liquid crystals and strings in field theory (cf. [START_REF] Aranson | The world of the complex Ginzburg-Landau equation[END_REF]). In particular, the one-dimensional linearized Ginzburg-Landau model considered in [START_REF] Aamo | Boundary control of the linearized Ginzburg-Landau model of vortex shedding[END_REF] enters this setting. If π/2 -θ is a small positive constant, then (1.1) is a viscous perturbation of the Schrödinger equation which appears naturally in the building of stable numerical schemes (cf. [START_REF] Ignat | A two-grid approximation scheme for nonlinear Schrödinger equations: dispersive properties and convergence[END_REF]). Although conservative physical systems (e.g. the linear system of elasticity, Maxwell's equations, cf. §I.B.1.2 in [START_REF] Dautray | Mathematical analysis and numerical methods for science and technology[END_REF]) provide examples of (1.2) for which some controllability results are known, we have not found one yet for which the corresponding first-order system (1.1) is relevant to physics or engineering (besides the scalar wave equation considered in §6).

This paper presents the control transmutation method (cf. [START_REF] Hersh | The method of transmutations[END_REF] for a survey on transmutations in other contexts) which can be seen as a shortcut to Russell's famous harmonic analysis method in [START_REF] Russell | A unified boundary controllability theory for hyperbolic and parabolic partial differential equations[END_REF]. It consists in explicitly constructing controls u in any time T for the heat-like equation (1.1) in terms of controls v in time L for the corresponding wave-like equation (1.2), i.e. u(t) = R k(t, s)v(s) ds, where the compactly supported kernel k depends on T and L 1 . It proves that the exact controllability of (1.2) in some time L implies the null controllability of (1.1) in any time with a relevant upper bound on the cost of controls for (1.1) as T tends to 0, in short the cost of fast controls (as in the title of this paper and [START_REF] Seidman | How violent are fast controls? II[END_REF]). Thanks to the geodesic condition of Bardos-Lebeau-Rauch (cf. [START_REF] Bardos | Sharp sufficient conditions for the observation, control, and stabilization of waves from the boundary[END_REF]) for the controllability of the wave equation, the application of this method to the boundary controllability of the heat equation (cf. §6) yields new geometric bounds on the cost of fast controls, extending the results of [START_REF]Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF] on internal controllability 2 . This method applies as soon as the wave equation is controllable, no matter how singular the coefficients in A are (e.g. discontinuous coefficients in transmission problems in [START_REF] Doubova | Exact controllability to trajectories for semilinear heat equations with discontinuous diffusion coefficients[END_REF], coefficients of bounded variation in [START_REF]On the null controllability of the one-dimensional heat equation with non-smooth coefficients[END_REF]) but it does not seem to adapt to time-dependent coefficients. The companion paper [START_REF]Controllability cost of conservative systems: resolvent condition and transmutation[END_REF] concerns the quite different case |θ| = π/2 (in particular there is no smoothing effect) and applies to the Schrödinger equation, which is the control problem to which a transmutation method was first applied by Phung in [START_REF] Phung | Observability and control of Schrödinger equations[END_REF].

The relationship between first and second order controllable systems has been investigated in previous papers, always with θ = 0 and the additional initial data ż(0) = z 1 in X (i.e. considering trajectories of (1.2) in the state space X × X). In [START_REF] Fattorini | Controllability of higher order linear systems[END_REF], it is proved that the approximate controllability of (1.2) with ż(0) = z 1 in some time implies the approximate controllability of (1.1) for any time (the control transmutation method yields an alternative proof), and proves the converse under 1 N.b. although L denotes a time here, it also denotes a length in the construction of k and in the main application to the wave and heat equations; the notation is meant as a reminder of this key fact of the method.

2 N.b. the controllability of the heat equation holds even if the geometry prevents the controllability of the wave equation but in that case no explicit geometric bound on the cost of fast controls is known. For interior controllability, a bound of the form exp(C β /T β ) for any β > 1 is proved in [START_REF]On the controllability of anomalous diffusions generated by the fractional laplacian[END_REF] but the positive constant C β is not explicit. A better bound of the form exp(C 1 /T ) is proved in [START_REF] Fernández-Cara | The cost of approximate controllability for heat equations: the linear case[END_REF], at least in the Euclidean case (cf. remark 6.4), but the positive constant C 1 is not explicit either. some assumptions on the spectrum of A. The converse is investigated further in [START_REF] Tsujioka | Remarks on controllability of second order evolution equations in Hilbert spaces[END_REF] (in Hilbert spaces) and [START_REF] Triggiani | On the relationship between first and second order controllable systems in Banach spaces[END_REF]. In a restricted setting, the null controllability of (1.1) was deduced from the exact controllability of (1.2) with ż(0) = z 1 in [START_REF] Russell | A unified boundary controllability theory for hyperbolic and parabolic partial differential equations[END_REF] and [START_REF] Seidman | Exact boundary control for some evolution equations[END_REF] by the indirect method of bi-orthogonal bases 3 .

The study of the cost of fast controls was initiated by Seidman in [START_REF]Two results on exact boundary control of parabolic equations[END_REF] with a result on the heat equation obtained by Russell's method. Seidman also obtained results on the Schrödinger equation by working directly on the corresponding window problem for series of complex exponentials (see [START_REF]How violent are fast controls for Schrödinger and plates vibrations ?[END_REF] for improvements and references). With collaborators, he later treated the case of finite dimensional linear systems (cf. [START_REF] Seidman | How violent are fast controls? II[END_REF]) and generalized the window problem to a larger class of complex exponentials (cf. [START_REF] Seidman | The "window problem" for series of complex exponentials[END_REF]). Fernández-Cara and Zuazua obtained results on the cost of fast interior controls for the heat equation discussed in remark 6.4. Since their approach is based on global Carleman estimates (cf. [START_REF] Fursikov | Controllability of evolution equations[END_REF]) it should extend to boundary controllability, and to a very large class of equations with variable coefficients possibly depending on time as-well. The control transmutation method generalizes upper bounds on the cost of fast controls from the one-dimensional setting (which reduces to a window problem) to the general setting which we specify in the next section. Some open problems are stated in remarks 3.3 and 6.4.

2. The setting. We assume that A is the generator of a strongly continuous cosine operator function Cos (i.e. the second-order Cauchy problem for z(t) = A(t)z is well posed and Cos is its propagator). For a textbook presentation of cosine operator functions, we refer to chap. 2 of [START_REF]Second order linear differential equations in Banach spaces[END_REF] or §3.14 of [START_REF] Arendt | Vector-valued Laplace transforms and Cauchy problems[END_REF]. The associated sine operator function is Sin(t) = t 0 Cos(s)ds (with the usual Bochner integral). Cos and Sin are strongly continuous functions on R of bounded operators on X. Moreover A generates a holomorphic semigroup T of angle π/2 (cf. th. 3.14.17 of [START_REF] Arendt | Vector-valued Laplace transforms and Cauchy problems[END_REF]). In particular S(t) = T (e iθ t) defines a strongly continuous semigroup (S(t)) t∈R+ of bounded operators on X. In this setting, for any source term f ∈ L 1 loc (R, X), for any initial data x 0 , z 0 and z 1 in X, the inhomogeneous first and second order Cauchy problems

ẋ(t) = e iθ Ax(t) + f (t) (t ∈ R + ), x(0) = z 0 , (2.1)
z(t) = Az(t) + f (t) (t ∈ R), z(0) = z 0 , ż(0) = z 1 , (2.2)
have unique mild solutions x ∈ C 0 (R + , X) and z ∈ C 0 (R, X) defined by:

x(t) = S(t)x 0 + t 0 S(t -s)f (s)dt, z(t) = Cos(t)z 0 + Sin(t)z 1 + t 0 Sin(t -s)f (s)dt.
Remark 2.1. When A is a negative self-adjoint unbounded operator on a Hilbert space, T , Cos and Sin are simply defined by the functional calculus as

T (t) = exp(tA), Cos(t) = cos(t √ -A) and Sin(t) = ( √ -A) -1 sin(t √ -A).
Following [START_REF] Weiss | Admissibility of unbounded control operators[END_REF], we now make natural assumptions on B for any initial data in the state space X to define a unique continuous trajectory of each system (1.1) and (1.2). Let X -1 be the completion of X with respect to the norm x -1 = (A -β) -1 x for some β ∈ C outside the the spectrum of A. X -1 is also the dual of the space X 1 defined as the domain D(A) with the norm x 1 = (A -β)x . We assume that B ∈ L(U, X -1 ) is an admissible unbounded control operator in the following sense:

∀t > 0, ∀u ∈ L 2 ([0, t]; U ), t 0 S(s)Bu(s)ds ∈ X and t 0 Sin(s)Bu(s)ds ∈ X. (2.3)
In this setting, for any x 0 and z 0 in X, for any u and v in L 2 loc (R + ; U ), the unique solutions x and z in C 0 (R; X) of (1.1) and (1.2) respectively are defined by:

x(t) = S(t)x 0 + t 0 S(t -s)Bu(s)dt, z(t) = Cos(t)z 0 + t 0 Sin(t -s)Bv(s)ds. (2.4)
The natural notions of controllability cost for the linear systems (1.1) and (1.2) are:

Definition 2.2. The system (1.1) is null-controllable in time T if for all x 0 in X, there is a u in L 2 (R + ; U ) such that u(t) = 0 for t > T and x(T ) = 0. The controllability cost for (1.1) in time T is the smallest positive constant κ 1,T such that, for all φ 0 , there is such a u satisfying:

T 0 u(t) 2 dt κ 1,T x 0 2 . The system (1.2) is null-controllable in time T if for all z 0 in X, there is a v in L 2 (R + ; U ) such that v(t) = 0 for t > T and z(T ) = ż(T ) = 0. The controllability cost for (1.
2) in time T is the smallest positive constant κ 2,T such that, for all z 0 , there is such a v satisfying:

T 0 v(t) 2 dt κ 2,T z 0 2 . Remark 2.3.
Equivalently, for all x T in S(T )X, there is a u in L 2 (0, T ; U ) such that x(0) = 0 and x(T ) = x T , and, for all z 0 , z 1 , z 2 and z 3 in X, there is a v in L 2 (0, T ; U ) such that (z(0), ż(0)) = (z 0 , z 1 ) and (z(T ), ż(T )) = (z 2 , z 3 ). This is the usual notion of exact controllability for (1.2) (cf. lemma 2.4).

Although the notion of null-controllability for (1.2) in def. 2.2 seems weaker than usual, the following lemma proves that it is equivalent to the usual notion.

Lemma 2.4. If (1.2) is null-controllable in time T in the sense of def. 2.2 then, for all z 0 and z 1 in X, there is an input v in L 2 (R + ; U ) such that v(t) = 0 for t > T and the solution of z(t) = Az(t)+Bv(t) (t ∈ R) with initial condition (z(0), ż(0)) = (z 0 , z 1 ) satisfies the final condition (z(T ), ż(T )) = (0, 0).

Proof. Assume that the system (1.2) satisfies def. 2.2 and let z 0 and z 1 be in X. We shall build an input w in L 2 (0, T ; U ) such that the solution y of ÿ(t) = Ay(t) + Bw(t) with (y(0), ẏ(0)) = (0, z 1 ) satisfies (y(T ), ẏ(T )) = (y 0 , 0) for some y 0 ∈ X. Let v 1 be the input v in def. 2.2 and let v 2 be the input v in def. 2.2 with z 0 replaced by y 0 . Due to the linearity of the system, the input v 1 (t) -v 2 (T -t) + w(t) steers the system from (z 0 , z 1 ) to (0, 0) as required to complete the proof of the lemma. The rest of the proof builds w and y.

Applying def. 2.2 with z 0 replaced by z 1 , yields an input v and the solution:

z(s) = Cos(s)z 1 + s 0 Sin(r)Bv(s -r)dr, z(T ) = ż(T ) = 0 .
We define w and y by w(t) = The exchange of integrals in the second step is justified since (s, r) → Sin(r)Bv(s-r) is continuous with values in X -1 (Cos and Sin extend by density to strongly continuous functions on R of bounded operators on X -1 since they commute with A -β). This integral formula means that y is the mild solution of ÿ(t) = Ay(t) + Bw(t) with initial condition (y(0), ẏ(0)) = (0, z 1 ).

3. The results and the method. Our estimate of the cost of fast controls for (1.1) builds, through the control transmutation method, on the same estimate for a simple system of type (1.1), i.e. on a segment [0, L] with Dirichlet (N = 0) or Neumann (N = 1) condition at the left end controlled at the right end through a Dirichlet condition:

∂ t φ = e iθ ∂ 2 s φ on ]0, T [ × ]0, L[ , ∂ N s φ s=0 = 0, φ s=L = u, φ t=0 = φ 0 . (3.1)
With the notations of §2,

x = φ, A = ∂ 2 s on X = L 2 (0, L) with D(A) = {f ∈ H 2 (0, L) | ∂ N s f (0) = f (L) = 0}, • 1 with β = 0 is the homogeneous Sobolev Ḣ2 (0, L) norm, and B on U = C is the dual of C ∈ L(X 1 ; U ) defined by Cf = ∂ s f (L).
It is well-known that the controllability of this system reduces by spectral analysis to classical results on nonharmonic Fourier series. The following upper bound for the cost of fast controls, proved in §4, is an application of a refined result of Avdonin-Ivanov-Seidman in [START_REF] Seidman | The "window problem" for series of complex exponentials[END_REF].

Theorem 3.1. There are positive constants α and γ such that, for all N ∈ {0, 1}, L > 0, T ∈ 0, inf(π, L) 2 , the controllability cost κ L,T of the system (3.1) satisfies: κ L,T γ exp(αL 2 /T ).

This theorem leads to a definition of the optimal fast control cost rate for (3.1): Definition 3.2. The rate α * is the smallest positive constant such that for all α > α * there exists γ > 0 satisfying the property stated in theorem 3.1.

Remark 3.3. Computing α * is an interesting open problem and its solution does not have to rely on the analysis of series of complex exponentials. The best estimate so far is α * ∈ [1/2, 4(36/37) 2 ] for θ = 0 (cf. [START_REF]Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF]).

Our main result is a generalization of theorem 3.1 to the first-order system (1.1) under some condition on the second-order system (1.2):

Theorem 3.4. If the system (1.2) is null-controllable for times greater than L * , then the system (1.1) is null-controllable in any time T . Moreover, the controllability cost κ 1,T of (1.1) satisfies the following upper bound (with α * defined above):

lim sup T →0 T ln κ 1,T α * L 2 * . (3.2)
Remark 3.5. The upper bound (3.2) means that the norm of an input function u steering the system (1.1) from an initial state x 0 to zero grows at most like γ x 0 exp(αL 2 /(2T )) as the control time T tends to zero (for any α * and some γ > 0). The falsity of the converse of the first statement in th. 3.4 is well-known, e.g. in the more specific setting of §6.

Remark 3.6. As observed in [START_REF] Cârjȃ | The minimal time function in infinite dimensions[END_REF], (3.2) yields a logarithmic modulus of continuity for the minimal time function T min : X → [0, +∞) of (1.1); i.e. T min (x 0 ), defined as the infimum of the times T > 0 for which there is a u in L 2 (R; Y ) such that T 0 u(t) 2 dt 1, u(t) = 0 for t / ∈ [0, T ] and x(T ) = 0, satisfies: for all α > α * , there is a c > 0 such that, for all x 0 and x 0 in X with x 0 -x 0 small enough,

|T min (x 0 ) -T min (x 0 )| αL 2 * / ln(c/ x 0 -x 0 ).
It is well known that the semigroup T can be expressed as an integral over the cosine operator function Cos (cf. the second proof of th. 3.14.17 in [START_REF] Arendt | Vector-valued Laplace transforms and Cauchy problems[END_REF]):

∀x ∈ X, ∀t ∈ C s.t. |arg t| < π/2, T (t)x = k(t, s) Cos(s)xds , (3.3)
where k(0, s) = δ(s) and k(t, s) = exp(-s 2 /(4t))/ √ πt for Re t > 0. This equation has been referred to as the abstract Poisson or Weierstrass formula. Starting with the observation that k is the fundamental solution of the heat equation on the line, i.e. k is the solution of ∂ t k = ∂ 2 s k with the Dirac measure at the origin as initial condition, the transmutation control method consists in replacing the kernel k in (3.3) by some fundamental controlled solution on the segment [-L, L] controlled at both ends (cf.

(5.8)). The one dimensional th. 3.1 is used to construct this fundamental controlled solution in §4 and the transmutation is performed in §5.

4. The fundamental controlled solution. This section begins with an outline of the standard application of [START_REF] Seidman | The "window problem" for series of complex exponentials[END_REF] to the proof of th.

∂ t k = e -iθ ∂ 2 s k in D (]0, T [×] -L, L[) , (4.1)
k t=0 = δ and k t=T = 0 , (4.2)
k 2 L 2 (]0,T [×]-L,L[) γe αL 2 /T . (4.3)
The operator A defined at the beginning of §3 is negative self-adjoint on the Hilbert space L 2 (0, L). It has a sequence {µ n } n∈N * of negative decreasing eigenvalues and an orthonormal Hilbert basis {e n } n∈N * in L 2 (0, L) of corresponding eigenfunctions. Explicitly: √ -µ n = (n + ν) π/L with ν = 0 for N = 0 (Dirichlet) and ν = 1/2 for N = 1 (Neumann). First note that th. 3.1 can be reduced to the case L = π by the rescaling (t, s) → (σ 2 t, σs) with σ = L/π. In terms of the coordinates c = (c n ) n∈N * of A N/2 f 0 in the Hilbert basis (e n ) n∈N * where f 0 is the initial state of the dual observability problem, th. 3.1 with L = π reduces by duality to the following window problem:

∃α > 0, ∃γ > 0, ∀T ∈ 0, π 2 , ∀c ∈ l 2 (N * ), n∈N * |c n | 2 γe απ 2 /T T 0 |F (t)| 2 dt where F (t) = ∞ n=1
c n e exp(iθ)µnt .

Since this results from th. 1 of [START_REF] Seidman | The "window problem" for series of complex exponentials[END_REF] with λ n ∼ ie iθ n 2 as in §5:2 of [START_REF] Seidman | The "window problem" for series of complex exponentials[END_REF], the proof of th. 3.1 is completed. Now we consider a system governed by the same equation as (3.1) but on the twofold segment [-L, L] controlled at both ends:

∂ t φ -e -iθ ∂ 2 s φ = 0 in ]0, T [×] -L, L[, φ s=±L = u ± , φ t=0 = φ 0 , (4.4)
with initial state φ 0 ∈ L 2 (0, L), input functions u -and u + in L 2 (0, T ). As in proposition 5.1 of [START_REF]Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF], applying th. 3.1 with N = 0 to the odd part of φ 0 and with N = 1 to the even part of φ 0 proves that the controllability cost of (4.4) is not greater than the controllability cost of (3.1) and therefore satisfies the same estimate stated in th. 3.1.

As in proposition 5.2 of [START_REF]Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF], we may now combine successively the smoothing effect of (4.4) with no input (i.e. u + = u -= 0) and this controllability cost estimate (plugged into the integral formula expressing φ in terms of φ 0 and u ± = φ s=±L ) to obtain: Proposition 4.2. For all α > α * , there exists γ > 0 such that for all L > 0 and T ∈ ]0, inf(π/2, L) 2 ] there is a fundamental controlled solution for (4.4) at cost (γ, α) (cf. def. 4.1).

5. The transmutation of second-order controls into first-order controls.

In this section we prove th. 3.4.

Let x 0 ∈ X be an initial state for (1.1) and let L > L * . Let z ∈ C 0 (R + ; X) and v ∈ L 2 (R + ; U ) be the solution and input function obtained by applying the exact controllability of (1.2) in time L to the initial state z 0 = x 0 .

We define z ∈ C 0 (R; X) and v ∈ L 2 (R; U ) as the extensions of ζ and v by reflection with respect to s = 0, i.e. z(s) = ζ(s) = z(-s) and v(s) = v(s) = v(-s) for s 0. They inherit from (2.4):

z(t) = Cos(t)x 0 + t 0 Sin(t -s)Bv(s)ds.
(

Def. 2.2 of κ 2,L implies the following cost estimate for v:

v(s) 2 ds = 2 L 0 v(s) 2 ds 2κ 2,L x 0 2 . (5.2) Since D(A) is dense in X, there is a sequence (x n ) n∈N * in D(A) converging to x 0 in X. Since X 1 is dense in X -1 , there is a sequence (f n ) n∈N * in C 1 (R; X 1 ) converging to Bv in L 2 (R; X -1 )
. For each n ∈ N * , let z n be defined in C 2 (R; X) by:

z n (t) = Cos(t)x n + t 0 Sin(t -s)f n (s)ds,
which converges to z(t) in X for all t due to (5.1). Since z n is a genuine solution of z(t) = Az n (t) + f n (t) (cf. lem. 4.1 of [START_REF]Second order linear differential equations in Banach spaces[END_REF]), we have for all ϕ in D(A ):

s → z n (s), ϕ ∈ H 2 (R) and d 2 ds 2 z n (s), ϕ = z n (s), A ϕ + f n (s), ϕ . Hence, z n (t), ϕ = x n , ϕ + t 0 (t-s) z n (s), A ϕ + t 0 (t-s) f n (s), ϕ . Passing to the limit, yields z(t), ϕ = x 0 , ϕ + t 0 (t -s) z(s), A ϕ + t 0 (t -s) Bv(s), ϕ . Therefore: s → z(s), ϕ ∈ H 2 (R) and d 2 ds 2 z(s), ϕ = z(s), Aϕ + Bv(s), ϕ , (5.3)
z(s), ϕ = 0 and d ds z(s), ϕ = 0 for |s| = L.

(5.4)

Let α > α * and T ∈]0, inf(1, L 2 )[. Let γ > 0 and k ∈ C 0 ([0, T ]; M(] -L, L[))
be the corresponding constant and fundamental controlled solution given by proposition 4.2. We define k ∈ C 0 (R + ; M(R)) as the extension of k by zero, i.e. k(t, s) = k(t, s) on [0, T ]×]-L, L[ and k is zero everywhere else. It inherits from k the following properties

∂ t k = e iθ ∂ 2 s k in D (]0, T [×] -L, L[) , (5.5
) k t=0 = δ and k t=T = 0 , (5.6)

k 2 L 2 (R+×R)
γe αL 2 /T .

(5.7)

The main idea of the proof is to use k as a kernel to transmute z and v into a solution x and a control u for (1.1). The transmutation formulas:

x(t) = k(t, s)z(s) ds and ∀t > 0, u(t) = k(t, s)v(s) ds,

(5.8)

define x ∈ C 0 (R + ; X) and u ∈ L 2 (R + ; U ) since k ∈ C 0 (R + ; M(R)) ∩ L 2 (R + ; L 2 (R)), z ∈ C 0 (R; X) and v ∈ L 2 (R; U ).
The property (5.6) of k implies x(0) = x 0 and x(T ) = 0. Equations (5.3), (5.4) and (5.5) imply, by integrating by parts:

∀ϕ ∈ D(A ), t → x(t), ϕ ∈ H 1 (R + ) and d dt x(t), ϕ = x(t), A ϕ + Bu(t), ϕ .
This characterizes x as the unique solution of (1.1) in the weak sense (cf. [START_REF] Ball | Strongly continuous semigroups, weak solutions, and the variation of constants formula[END_REF]), which implies that x and u satisfy (2.4). Since u(t) 2 dt |k(t, s)| 2 ds dt v(s) 2 ds, (5.7) and (5.2) imply the following cost estimate which completes the proof of th. 3.4:

T 0 u(t) 2 dt 2κ 2,L γe αL 2 /T x 0 2 .
6. Geometric bounds on the cost of fast boundary controls for the heat equation. When the second-order equation (1.2) has a finite propagation speed and is controllable, the control transmutation method yields geometric upper bounds on the cost of fast controls for the first-order equation (1.1). From this point of view, this method is an adaptation of the kernel estimates method of Cheeger-Gromov-Taylor in [START_REF] Cheeger | Finite propagation speed, kernel estimates for functions of the Laplace operator, and the geometry of complete Riemannian manifolds[END_REF]. This was illustrated in [START_REF]Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF] and [START_REF]How violent are fast controls for Schrödinger and plates vibrations ?[END_REF] on the internal controllability of heat and Schrödinger equations on Riemannian manifolds which have the wave equation as corresponding second-order equation. Some similar lower bounds are proved in these papers (without assuming the controllability of the wave equation) which imply that the upper bounds are optimal with respect to time dependence. In this section, we illustrate the control transmutation method on the analogous boundary control problems for the heat equation.

Let (M, g) be a smooth connected compact n-dimensional Riemannian manifold with metric g and smooth boundary ∂M . When ∂M = ∅, M denotes the interior and M = M ∪ ∂M . Let ∆ denote the (negative) Laplacian on (M, g) and ∂ ν denote the exterior Neumann vector field on ∂M . The characteristic function of a set S is denoted by χ S .

Let X = L 2 (M ). Let A be defined by Af = ∆f on

D(A) = H 2 (M ) ∩ H 1 0 (M ). Let C be defined from D(A) to U = L 2 (∂M ) by Cf = ∂ ν f Γ
∂ 2 t z -∆z = 0 on R t × M, z = χ Γ v on R t × ∂M, z(0) = z 0 ∈ L 2 (M ), ż(0) = 0, v ∈ L 2 loc (R; L 2 (∂M )), (6.1)
It is well known that B is an admissible observation operator (cf. cor. 3.9 in [START_REF] Bardos | Sharp sufficient conditions for the observation, control, and stabilization of waves from the boundary[END_REF]). To ensure existence of a null-control for the wave equation we use the geometrical optics condition of Bardos-Lebeau-Rauch (specifically example 1 after cor. 4.10 in [START_REF] Bardos | Sharp sufficient conditions for the observation, control, and stabilization of waves from the boundary[END_REF]):

There is a positive constant L Γ such that every generalized geodesic of length greater than L Γ passes through Γ at a non-diffractive point. (6.2)

Generalized geodesics are the rays of geometrical optics (we refer to [START_REF] Miller | Escape function conditions for the observation, control, and stabilization of the wave equation[END_REF] for a presentation of this condition with a discussion of its significance). We make the additional assumption that they can be uniquely continued at the boundary ∂M . As in [START_REF] Bardos | Sharp sufficient conditions for the observation, control, and stabilization of waves from the boundary[END_REF], to ensure this, we may assume either that ∂M has no contacts of infinite order with its tangents (e.g. ∂M = ∅), or that g and ∂M are real analytic. For instance, we recall that (6.2) holds when Γ contains a closed hemisphere of a Euclidean ball M of diameter L Γ /2, or when Γ = ∂M and M is a strictly convex bounded Euclidean set which does not contain any segment of length L Γ . Theorem 6.1 ([6]). If (6.2) holds then the wave equation (6.1) is null-controllable in any time greater than L Γ .

Thanks to this theorem, th. 3.4 implies: Theorem 6.2. If (6.2) holds then the equation:

∂ t x -e iθ ∆x = 0 on R t × M, x = χ Γ u on R t × ∂M, x(0) = x 0 ∈ H -1 (M ), u ∈ L 2 loc (R; L 2 (∂M )),
is null-controllable in any time T . Moreover, the controllability cost κ T ln κ 1,T α * L 2 Γ . Remark 6.3. Note that theorem 3.2 in [START_REF] Bardos | Sharp sufficient conditions for the observation, control, and stabilization of waves from the boundary[END_REF] almost proves the converse of th. 6.1, thus showing that (6.2) is a sharp condition. Moreover [START_REF] Burq | Contrôlabilité exacte de l'équation des ondes dans des ouverts peu réguliers[END_REF][START_REF] Burq | Condition nécessaire et suffisante pour la contrôlabilité exacte des ondes[END_REF] prove that the full equivalence do hold when χ Γ is replaced by a smooth function with the same zero level set ∂Ω \ Γ (this slight difference of model should not be perceptible in applications). Hence the control transmutation method does not allow to improve L Γ in th. 6.2. Remark 6.4. For more results and references on the cost of fast controls for the heat equation we refer to [START_REF] Fernández-Cara | The cost of approximate controllability for heat equations: the linear case[END_REF][START_REF]Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF]. It is a known fact that the heat equation is null-controllable for any non-empty control region Γ, hence the converse to the first statement of this theorem is not true. When M is a bounded Euclidean set and ∆ has constant coefficients, [START_REF] Fernández-Cara | The cost of approximate controllability for heat equations: the linear case[END_REF] proves that the lim sup in the second statement is finite for any interior control region, but does not give an explicit bound. Motivated by the non-linear heat equation, it considers the heat equation with a time-dependent potential and describes how the cost depends on the norm of this potential, whereas the control transmutation method seems to apply only to time-independent potentials (on which the lim sup above does not depend). As explained in section 2.4 of [START_REF]Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF], in the general case without condition (6.2), one could try to adapt Carleman inequalities with phases φ to obtain a bound in terms of the following distance function d : d(x, y) = sup{φ(y)-φ(x)}, for all x and y in M , where the supremum is taken over all Lipschitz functions φ : M → R with |∇φ| 1 almost everywhere (d also has a geometric characterization in terms of path of least action). Remark 6.5. This paper does not state explicitly a theorem about transmission problems for the linear heat equation because it does not address the main open problem in that context (cf. Open Problem §2.3.4 in [START_REF] Doubova | Exact controllability to trajectories for semilinear heat equations with discontinuous diffusion coefficients[END_REF]). Nonetheless, th. 3.4 provides a proof of some results which are not found in the literature (n.b. they are considered wellknown by some experts). Firstly, it proves that "Russell's principle" (cf. [START_REF] Russell | A unified boundary controllability theory for hyperbolic and parabolic partial differential equations[END_REF]) applies to transmission problems in any dimension (this was explicitely assumed in §2.3.4 in [START_REF] Doubova | Exact controllability to trajectories for semilinear heat equations with discontinuous diffusion coefficients[END_REF] and proved in dimension 1 in [START_REF]On the null controllability of the one-dimensional heat equation with non-smooth coefficients[END_REF], cf. footnote 3). Secondly, th. 3.4 deduces a new result on the boundary controllability of the transmission problems for the heat equation from the boundary controllability of the transmission problem for the wave equation in Tome 1, chap 6 in [START_REF] Lions | Contrôlabilité exacte, perturbations et stabilisation de systèmes distribués[END_REF]. As in remark 6.4, since [START_REF] Doubova | Exact controllability to trajectories for semilinear heat equations with discontinuous diffusion coefficients[END_REF] is based on global Carleman estimates, it should extend from interior to boundary controls, and would yield fast controllability at an exponential rate under a less restrictive geometrical hypothesis than th. 3.4 does, but it would not yield an explicit bound on the rate as th. 3.4 does.

t0

  0 v(s)ds and y(t) = t 0 z(s)ds for t ∈ [0, T ]. The final condition ẏ(T ) = z(T ) = 0 is immediately satisfied. Since Sin(t) = t Cos(s)ds: y(t) -Sin(t)z 1 = Bw(t -r) dr .

3 . 1 .

 31 Following closely §5 of [23], the rest of the section outlines the construction of a "fundamental controlled solution" k in the following sense, where D (O) denotes the space of distributions on the open set O endowed with the weak topology, M(O) denotes the subspace of Radon measures on O, and δ denotes the Dirac measure at the origin: Definition 4.1. The distribution k ∈ C 0 ([0, T ]; M(] -L, L[)) is a fundamental controlled solution for (4.1) at cost (γ, α) if

  where Γ is an open subset of ∂M , and let B be the dual of C. With this setting, (1.1) with θ = 0 and (1.2) are the heat and wave equations controlled by the Dirichlet boundary condition on Γ. In particular (1.2) writes:

N.b. the systematic approach to controllability based on bi-orthogonal bases (cf.[START_REF] Avdonin | Families of exponentials. The method of moments in control lability problems for distributed parameter systems[END_REF]) does not apply in our general setting where A may not have eigenfunctions (e.g. on some unbounded domains). When it does apply, it builds on some knowledge about the eigenvalues and the analysis of some exponential series, whereas the control transmutation method per se does not (cf. remark 3.3). E.g. in the abstract presentation of Russell's method in §2 of[START_REF]On the null controllability of the one-dimensional heat equation with non-smooth coefficients[END_REF], the eigenvalues are assumed to grow quadratically. A more detailed comparison can be found in[START_REF]Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF], in the specific case which lead the author to this new method.

Acknowledgments. References [4,16] were pointed out to me by a referee.

This work was partially supported by the ACI grant " Équation des ondes : oscillations, dispersion et contrôle". 1


I Abdeljaoued-Tej

F Bouazizi
email: faical.bouazizi@lip6.fr

Computing the Lagrange resolvent by effectiveness of Galois Theorem

Keywords: Lagrange resolvent, minimal polynomial, Galois group, galoisian ideal, triangular ideal, 12F10 12Y05 11Y40

In this article, we introduce a new method to calculate Lagrange resolvent. This technique is based on Lagrange's algorithm and it enables to calculate algebraically the resolvent. This algorithm is based on the fundamental theorem of symmetric functions:we generalize the effectivity of this theorem to any surgroup of the Galois's group of the polynomial.

Introduction

The fundamental theorem of symmetric functions has various effective forms (see, for example, [START_REF] Macdonald | Symmetric Functions and Hall Polynomials[END_REF], [START_REF] Lascoux | Formulaire raisonné de fonctions symétriques[END_REF] and [START_REF] Valibouze | Théorie de Galois constructive[END_REF]). The computer algebraic system Maxima has an important library on the subject (see Symmetries in [START_REF] Schelter | Manuel de Maxima[END_REF]). Cauchy's method enables to reduct a symmetric polynomial with respect to the ideal of symmetric relations S generated by the triangular set of Cauchy moduli ( [START_REF] Cauchy | Usage des fonctions interpolaires dans la détermination des fonctions symétriques des racines d'une équation algébrique donnée[END_REF]). The Galois theorem is not formulated in a constructive form but it generalizes the fundamental theorem of symmetric functions. It is stated not rigorously as follows: Any polynomial expression on a field k in the roots of a univariate polynomial f with coefficients in k belongs to k if and only if it is invariant by the Galois group of f on k. Its effective calculation is the stake of the effective Galois theory: let be a polynomial f in k[x], calculate its Galois group G on k as well as the ideal M of its relations (this maximum ideal M contains the ideal of the symmetric relations). In order to have an effective calculation of M, it is necessary to calculate simultaneously the Galois group and thus resolvents ( [START_REF] Valibouze | Étude des relations algébriques entre les racines d'un polynôme d'une variable[END_REF]). The resolvent offers a double advantage. It excludes groups and provides primitive elements of galoisian ideals, these intermediate ideals between S and M. The resolvent is thus a fundamental tool of Galois theory.

When the resolvent is absolute, its coefficients are symmetric in the roots of f and, as a result, the fundamental theorem of symmetric functions can be applied. As the direct calculation of the coefficients being too expensive, Lagrange proposed two algorithms for its calculation. The first uses the technique of elimination, i.e. the resultant without naming it since it does not exist yet as a mathematical object ( [START_REF] Lagrange | Réflexions sur la résolution algébrique des équations[END_REF]). The second fact uses the Newton's functions of the resolvent's roots ( [START_REF] Lagrange | Oeuvres, Tome VIII, Notes sur la théorie des équations algébriques[END_REF], page 237). The resolvent function of Maxima implements this algorithm (see resolvent:general in library Symmetries). In [START_REF] Aubry | Using Galois ideals for computing relative resolvents[END_REF], an algorithm based on triangular ideals and using resultants was worked out for resolvents (absolute ones or not).

We present, in section 3, a new algorithm devoted to the algebraic method which uses the Newton's functions of the resolvent's roots. This algebraic algorithm requires a generalization of the effectivity of the fundamental theorem of the symmetric function. We were inspired by Cauchy's method in order to "evaluate" the multivariate polynomials in the roots of f by using a galoisian ideal (see section 2). In particular, when the galoisian ideal is M, this evaluation produces the effectiveness of Galois theorem. We describe our algorithm in the free mathematics software system SAGEmath (see section 3.2). In order to measure the effectiveness of our algorithm (see section 5), we do not take account of optimizations of section 6. In section 6, we will note that the algorithm is naturally parallelizable and that we can apply to him a method of calculation of products in a ring quotiented by a triangular ideal ( [START_REF] Bostan | Homotopy methods for multiplication modulo triangular sets[END_REF]). It presents other interests like detecting linear factors over k[x] of resolvent while accelerating its calculation.

Reminder

In all this article, f is a univariate polynomial of degree n, with coefficients in a perfect field k, α = (α 1 , ..., α n ) denotes an n-tuple formed by n roots of f supposed distincts (where n > 0). The extension field k(α) of k is the decomposition field of f ; recall that we have k(α) = k[α]. Let x 1 , . . . , x n be algebraically independent variables; we consider that they are ordered by x 1 < x 2 < . . . < x n ; let k[x 1 , . . . , x n ] be the ring of polynomials in these variables and with coefficients in k; k(x 1 , . . . , x n ) is its field of fractions. We adopt the notations and the results of [START_REF] Valibouze | Étude des relations algébriques entre les racines d'un polynôme d'une variable[END_REF] without citing them explicitely.

Orbits and group actions

Let L be a subgroup of the symmetric group S n of degree n and H be a subgroup of L. The symmetric group S n acts naturally on the field k(x 1 , ..., x n ) by:

Sn × k(x1, ..., xn) → k(x1, ..., xn) (σ, P ) → σ.P (x1, ..., xn) = P (x σ(1) , ..., x σ(n) )
Definition 1. The orbit L.P of P under the action of L is defined by:

L.P = {σ.P | σ ∈ L}.
Definition 2. The stabilizer Stab L (P ) of a polynomial P in k[x 1 , ..., x n ] with respect to L is defined by: Stab L (P ) = {σ ∈ L | P = σ.P } and the stabilizer of H with respect to L is defined by:

Stab L (H) = {σ ∈ L | ∀ r ∈ H r = σ.r}. Definition 3. An invariant of L (or an L-invariant) is a polynomial P in k[x 1 , ..., x n ] verifying: L.P = {P }. It is called an L-primitif H-invariant if H = Stab L (P ) = {σ ∈ L | σ.P = P }. When L = S n , the polynomial P is called a primitif H-invariant. Examples 1. -The Vandermonde determinant δ n = 1≤i<j≤n (x i -x j ) is a primitif A n -invariant
where A n is the alternating group of degree n.

-The polynomial x 1 x 2 + x 3 x 4 is a S 4 -primitif D 4 -invariant where [START_REF] Bostan | Homotopy methods for multiplication modulo triangular sets[END_REF][START_REF] Cauchy | Usage des fonctions interpolaires dans la détermination des fonctions symétriques des racines d'une équation algébrique donnée[END_REF], [START_REF] Abdeljaouad | Calculs d'invariants primitifs de groupes finis[END_REF][START_REF] Bostan | Homotopy methods for multiplication modulo triangular sets[END_REF](2, 4) > is the dihedral group -The polynomials x 1 + 2x 2 + ... + (n -1)x n-1 and x 1 x 2 2 ...x n-1 n-1 are primitif I n -invariants where I n is the identity group of degree n. 3 -the Newton's functions p 0 , p 1 , ..., p n , ... in x 1 , ..., x n (also called power functions), are defined by

D 4 =< (1, 2),

Symmetric polynomials

A polynomial s of k[x 1 , ..., x n ] is called symmetric (in x 1 , x 2 , ..., x n ) if s = σ.
p r = n i=1 x r i .
The Girard-Newton formulae ([6]) constitute a triangular system which makes it possible to pass from a basis to another: for all integers r > 0 p r e 0 -p r-1 e 1 + • • • + (-1) r-1 p 1 e r-1 + (-1) r r.e r = 0.

Put a i = (-1) i e i (α) for i = 1, . . . , n. The polynomial f can be written in the form

f = x n + a 1 x n-1 + a 2 x n-2 + • • • + a n
and the Girard-Newton formulae give us:

p r (α) + p r-1 (α)a 1 + • • • + p 1 (α)a r-1 + ra r = 0.
The fundamental theorem of symmetric polynomials say that any symmetric polynomial over k can be expressed as a polynomial over k in elementary symmetric polynomials . Furthermore, by using Girard-Newton formulae, any symmetric polynomial on the roots of a univariate polynomial can be expressed as a polynomial expression over k of the power functions on these roots.

Triangular ideals

Definition 4. A triangular set T is defined by:

T = {f 1 (x 1 ), ..., f n (x 1 , ..., x n )}
where every f i is a monic polynomial on x i and deg

(f i , x i ) > 0. This triangular set T is called separable if any f i verify for all β = (β 1 , ..., β i-1 ) ∈ k i-1 such that f 1 (β 1 ) = f 2 (β 1 , β 2 ) • • • f i-1 (β 1 , ..., β i-1 ) = 0, the univariate polynomial f i (β 1 , ..., β i-1 , x i ) does not admit a multiple root.
Example 1. For n = 8, the following triangular set T is separable:

T = { f1 = x 8 1 + 9x 6 1 + 23x 4 1 + 14x 2 1 + 1, f2 = x2 + x1, f3 = x 3 3 + (x 7 1 + 8x 5 1 + 16x 3 1 + 3x1)x 2 3 +(x 6 1 + 9x 4 1 + 21x 2 1 + 6)x3 + x 7 1 + 9x 5 1 + 23x 3 1 + 14x1, f4 = x 2 4 + (x 7 1 + 8x 5 1 + 16x 3 1 + 3x1)(x4 + x3) + x3x4 + x 2 3 + x 6 1 + 9x 4 1 + 21x 2 1 + 6, f5 = x5 + x4 + x3 + x 7 1 + 8x 5 1 + 16x 3 1 + 3x1, f6 = x6 + x3, f7 = x7 + x4, f8 = x8 + x5 }
In fact: the polynomials f 2 ,f 5 ,f 6 ,f 7 and f 8 satisfies the condition because they are repectively linear on x 2 , x 5 , x 6 , x 7 and x 8 ; the polynomial f 1 is irreductible over the perfect field Q and so separable; the polynomial f 3 (α 1 , x) is a factor of f 1 (x) over Q(α 1 ) what involves its separability; finally,

f 4 (x 1 , x 3 , x 4 ) = 1 x 3 -x 4 (f 3 (x 1 , x 3 ) -f 3 (x 1 , x 4 )),
thus its separability.

Definition 5. The Cauchy moduli of f are polynomials f 1 , ..., f n in k[x 1 , ..., x n ] defined inductively as follows:

-f 1 (x 1 ) = f (x 1 ) and -for i = 2, ..., n:

f i (x i ) = f i-1 (x 1 , x 2 , . . . , x i-2 , x i-1 ) -f i-1 (x 1 , x 2 , . . . , x i-2 , x i ) x i-1 -x i .
The Cauchy moduli form a separable triangular set. Definition 6. An ideal I is said triangular if it is generated by a separable triangular set.

Let I be a triangular ideal generated by the following separable triangular set:

T = {f 1 (x 1 ), f 2 (x 1 , x 2 ), ..., f n (x 1 , ..., x n )}.
The set T forms a minimal Gröbner basis for the lexicographic order (recall that where Reste(p, q, x) is the remainder of euclidean division of p by q regarded as polynomials in x. The ideal of symmetric relations S is triangular and is generated by the Cauchy moduli ( [START_REF] Rennert | Calcul de résolvantes avec les modules de Cauchy[END_REF]). Cauchy proposed in [START_REF] Cauchy | Usage des fonctions interpolaires dans la détermination des fonctions symétriques des racines d'une équation algébrique donnée[END_REF] an effective form of the fundamental theorem of symmetric functions which we rewrite in the following form:

x 1 < x 2 < • • • < x n ).
M = {R ∈ k[x 1 , ..., x n ] | R(α) = 0}
is called the ideal of α-relations.

Definition 10. The Galois group G α of α over k is the stabilizer of M in S n :

G α = {σ ∈ S n | (∀R ∈ M) σ.R ∈ M}. Theorem 11. (Galois, 1897) Let P ∈ k[x 1 , . . . , x n ]. We put σ.P (α) = P (α) for all σ ∈ G α if and only if P (α) ∈ k.
Definition 12. Let L be a subset of S n . The ideal

I L α = {R ∈ k[x 1 , ..., x n ] | (∀σ ∈ L) σ.R(α) = 0}
is called the ideal of α-relations invariant by L. Such an ideal is called a galoisian ideal of f over k. We have the following identities:

Card(V (I)) = Card(Inj(I, M)) = dim k k[x 1 , . . . , x n ]/I (1)
where V (I) is the algebraic variety of I, the set of its zeros. When the injector of I in M is a group, the ideal I is said pure. A galoisian ideal I included in M is pure if and only if its injector in itself (we have Inj(I, I) = Stab Sn (I)) contains the Galois group G α ; which is equivalent to Inj(I, I) = Inj(I, M) ; which is, using (1), still equivalent to

Card(Inj(I, I)) = dim k[x 1 , . . . , x n ]/I .
In [START_REF] Aubry | Using Galois ideals for computing relative resolvents[END_REF], the authors show that a pure galoisian ideal is triangular. For example, the ideals S and M are pure. The galoisian ideals considered are for the majority pure otherwise we obtain this case by permutations of its relations (see [START_REF] Valibouze | Classes doubles, idéaux de Galois et résolvantes[END_REF]). The reduction modulo a pure galoisian ideal consists on n Euclidean divisions with its generators (see section 1.3).

Minimal and characteristic polynomials and Resolvents

We consider I ⊂ M, a galoisian ideal with injector L in M, H a group included in L and P an L-primitif H-invariant.

Let P be the multiplicative endomorphism of k[x 1 , ..., x n ]/I induced by P : The characteristic polynomial of P is an element of k[x] of degree Card(L) given by

χ P ,I = σ∈L (x -σ.P (α)). ( 2
)
This results is easily obtained from Identity (1) and from the Stickelberger's Theorem expressing the characteristic polynomial of such multiplicative endomorphisms (for ideals of finished variety not necessarily radical). We can also affirm that χ P ,S ∈ k[x] by the Galois Theorem since the injector L contains the Galois group. When k is a perfect field, the minimal polynomial of the endomorphism P is the square free factor over k of the characteristic polynomial:

Min P ,I = ψ∈{Q(α) | Q∈L.P } (x -ψ).
The resolvent L-relative of α by P is, by definition, the polynomial

R P,I = Q∈L.P (x -Q(α)). (3)
It belongs to k[x] since its coefficients are invariant by L and since that L contains the Galois group G α . When the resolvent is square free, it is identified with the minimal polynomial. We have the identity:

χ P ,I = R Card(H) P,I . (4)
When L = S n , the resolvent does not depend on the order α 1 , ..., α n of the roots of f . It is said absolute and called resolvent of f by P .

Example 3. Let put n = 3, f = (x -x 1 )(x -x 2 )(x -x 3 ) and P = x 1 x 2 2 . We have R P,S = (x -x 1 x 2 2 )(x -x 1 x 2 3 )(x -x 2 x 2 1 )(x -x 2 x 2 3 )(x -x 3 x 2 1 )(x -x 3 x 2 2
) .

General assumptions

Let us assume that I is a galoisian ideal knowed by a reduced Gröbner basis (this basis is used for performing the reduction modulo I). We denote by L the injector of I in a maximal ideal M containing I. We fix a subgroup H of L and a an L-primitif H-invariant P in k[x 1 , ..., x n ].

Effectiveness of Galois Theorem

We seek to evaluate polynomials which are invariant by any injector in M of a galoisian ideal. As mentioned in Introduction, when the injector L is S n , the considered polynomials are symmetric and there are many methods to evaluate them on the roots of f . They are effective forms of fundamental theorem of symmetric polynomials (voir section 1.2). When L = G α it is about the effective form of Theoroem 11 of Galois. We gather here these two theorems into an effective one (i.e. for any injector L).

Theorem 15. Let I be a galoisian ideal of f included in M, the ideal of α-relations, and L the injector of

I in M. Let R ∈ k[x 1 , ..., x n ] such that σ.R = R for all σ ∈ L. Then R(α) belongs to the field k of coefficients of f and R -R(α) ∈ I.
In other words, R(α) is calculated as the reduction of R modulo I. Proof : Since L is the injector of I in M, the Galois group G α is included in L. Let put λ = R(α). As the polynomial R is invariant by L, it is also invariant by G α . Therefore, by Theorem 11,

λ ∈ k and R -λ ∈ k[x 1 , . . . , x n ]. For any σ ∈ L, we have σ.(R -λ)(α) = σ.R(α) -λ = R(α) -λ = 0 , because R is L-invariant.
So, by definition of galoisian ideals, we obtain the result R -R(α) ∈ I.

Algebraic algorithm for the resolvent

The principle of calculation

From Theorem 15, we can bring out an algorithm to find the resolvent R P,I inspired on Lagrange algorithm ( [START_REF] Lagrange | Oeuvres, Tome VIII, Notes sur la théorie des équations algébriques[END_REF], page 237) restricted to the absolute resolvent (i.e. L = S n and I = S). Its method is to calculate the power functions of the roots of the absolute resolvent based on the effectiveness of the fundamental theorem of symmetric polynomials; then he deduce the coefficients of the resolvent with Girard-Newton formulae. We present a simular algorithm for any L-relative resolvents based on Theorem 15.

First of all, the following well known lemma provides us a way to calculate, without duplication, the orbit L.P of P under the action of L: Lemma 16. Let d be the index of H in L. Then the orbit L.P consists of d distinct polynomials τ.P where τ runs through a left coset of L mod H.

Function ABV Input:

n the degree of the polynomial f on the variable x -I a galoisian ideal given with its reduced Gröbner basis -L the injector of I in a maximal ideal containing I -H a subgroup of L -P an L-primitif H-invariant Output: R P,I , the L-relative resolvent of α by P, for any α ∈ V (I). -The function pui2polynome(p,x) calculates a univariate polynomial of degree d in x from the d + 1 power functions p 0 = d, p 1 , . . . , p d of its roots; the variable p is the list of this power functions:

def pui2polynome(p,x): a=[p[0]] pol=x^a for i in range(1,d+1): ai=p[i]+sum(p[j]*a[i-j] for j in range(1,i)) a=a+[-1/i*ai] return pol=pol+a[i]*x^(d-i)

Time and comparisons with other methods

We will compare our algorithm ABV with two others algebraic methods. The first algorithm, which we call Algo2, is described in [START_REF] Aubry | Using Galois ideals for computing relative resolvents[END_REF] and is based on resultants. It computes the characterisctic polynomial (i.e. a power of the resolvent). Its implementation is available in Maxima with version 2 of the library Symmetries (not yet distributed). The second algorithm, called Algo3, computes on Maple the matrix of the endomorphism P with the function MultiplicationMatrix then Min P ,I with the function MinimalPolynomial.

The following table shows the CPU execution times in seconds with n = deg(f ), c = Card(L), d = deg(R P,I ), D is the total degree of the invariant P , N is the monomial's number of P and r is its arity. The polynomials belongs to Q

[x]. n c (D,N ,r) d ABV Algo2 Algo3 4

Comments

We note that Algo3 is slower than function ABV and Algo2; it tells us nothing about the multiplicities of roots of the resolvent when it is not separable. To determine these multiplicities, we must find the characteristic polynomial in a longer time than that required by the minimal polynomial, and then calculate a c d th root (see Identity ( 4)). In terms of efficiency, this method offers no interest.

We also note that Algo2 is often slower than function ABV. Lagrange already noticed the same thing in his memory [START_REF] Lagrange | Oeuvres, Tome VIII, Notes sur la théorie des équations algébriques[END_REF] by writing on page 240: ". . . mais, comme on ne voit pas de cette manière de quel degré devrait être cette équation finale en x, qu'on pourrait même parvenir à une équation en x d'un degré plus haut qu'elle ne devrait être, ce qui est l'inconvénient ordinaire des méthodes d'élimination, nous avons cru devoir montrer comment on peut trouver cette équation a priori et s'assurer du degré précis auquel elle doit monter * ". What Lagrange expressed and which we translate here is that elimination's methods introduce power parasites and, moreover, these power are unknown; while with the power functions, he found directly the resolvent. Today, we know that this power equals to the order of the stabilizer of the invariant P since he calculated the characteristic polynomial χ P ,S of degree n!.

Remark 20. Note that Algo2 is far more efficient than that proposed by Lagrange. Indeed, the Lagrange's method which is restricted to absolute resolvents (i.e. L = S n ) enables to eliminate the variables x n , . . . , x 1 of the polynomial x -P with respect to polynomials f (x n ), . . . , f (x 1 ); he computes polynomial g of degree n n where χ P ,S is a factor. Next, with division of g by its"parasite's factors", which can be calculated by eliminations too, he extracts the divisor χ P ,S of g. By using Algo2, elimination is achieved with the Cauchy moduli (here L = S n ) of respective degrees n, n -1, . . . , 1 en x n , . . . , x 1 and the result is the polynomial χ P ,S of degree n!.

Our function ABV does not include the optimizations propozed in the following section. Nevertheless, this comparison demonstrates the efficiency of the function ABV.

Further Developpements

Parallelization.

We assume L.P = {P 1 , . . . , P d }. The algorithm ABV is parallelizable as follows:

Step 1 In parallel, for j = 0, ..., d, calculate the list l j of P i j , i = 1, . . . , d:

(a) l j = [P j mod I] (b) For i = 1, . . . , d l j = l j + [ l j [1] * l j [j -1] mod I ].
Step 2 In parallel, for i = 0, ..., d, calculate the ith power function p i by using the function somme mod(ll,I) where ll is the list composed by the ith element of every l j , j = 1, . . . , d.

Efficient method for products under

k[x 1 , . . . , x n ]/I.
When the ideal I is triangular, our algorithm can be greatly improved by optimizing the multiplication of polynomials modulo I. Indeed, we can incorporate the method described in [START_REF] Bostan | Homotopy methods for multiplication modulo triangular sets[END_REF] based on assessment techniques and on interpolation. This optimization is applicable to the function ABV and also in Step 1 of the parallel version. Detecting roots over k. We can lighten the calculations when there is Q ∈ L.P such that λ = Q * ". . . but as we are not able to see the degree of the final equation in x, even more we could reach an equation in x of a degree higher than it should be (and this is the drawback of elimination's methods), we felt obliged to show how this equation can be found in advance and ensure the precise degree to which it must climb." mod I belongs to k. When I = M, by the Galois Theorem and Theorem 15, the resolvent has a root Q(α) in k if and only if Q mod M belongs to k. For any ideal I the resolvent may have a root in k but no polynomial Q of L.P satisfies Q ∈ k . However, the reciprocal of the preceding assertion is true as expressed in the following lemma: Lemma 21. Let Q ∈ L.P and Q = Q mod I. If Q ∈ k then x -Q is a factor over k of the resolvent R P,I ; even more, for any i ≥ 0, p i (L.P \{Q}) mod I is the ith power function s i of the roots of R P,I

x-Q . Proof. We always have Q(α) = Q mod M. Suppose that λ = Q mod I belongs to k. Then Q(α) = Q mod I since I ⊂ M and Q(α) = Q mod M = λ. Therefore x -λ is a factor of the resolvent R P,I . We have s 0 = d -1 and, for i ≥ 1, p i (L.P \{Q}) mod I = (p i (L.P ) -λ i ) mod I = (p i (L.P ) mod I) -λ i = s i . ✷ When λ ∈ k, the polynomial Q is removed from the orbit L.P . These compute s 0 = , s 1 , . . . , s d-1 , the d first power functions of the roots of R P,I

x-λ . According to Lemma 21, this is possible since s 0 = d -1 and, for i = 1, . . . , d -1, we have:

s i = p mod I f or i ∈ [[1, d -1]],
where p = p i (L.P \{Q}). Here, the polynomial p is not invariant by L and Theorem 15 does not apply. But since p -s i is an α-relation invariant by L, we get s i as the reduction of p modulo I.

Conclusion

We have exploited the properties of galoisian ideals to develop our algorithm. For this, we generalized the fundamental theorem of symmetric functions and give an effective form of Galois Theorem. The time comparisons between two others techniques show the effectiveness of our algorithm ABV. Propositions for its optimization will provide significant gains. In the other hand, we are working on an implementation of the parallel version including the results of [START_REF] Bostan | Homotopy methods for multiplication modulo triangular sets[END_REF]. This implementation will be developed on SAGEmath.

References Computer Algebra Systems

  s for all permutations σ ∈ S n . Two important bases of the ring k[x 1 , ..., x n ] Sn of the symmetrical polynomials are pointed out below: -the elementary symmetric fonctions e 0 , e 1 , ..., e n , ... in x 1 , ..., x n , are defined by e 0 = 1, e r = 0 for r > n and for r ∈ [[1, n]] e r = m∈Sn.(x1x2...xr) m ;

Theorem 7 .

 7 [START_REF] Cauchy | Usage des fonctions interpolaires dans la détermination des fonctions symétriques des racines d'une équation algébrique donnée[END_REF] Let s be a symmetric polynomial of k[x 1 , . . . , x n ]. Thus s(α) is the output of the algorithm ReductionTriangulaire(s, S). 1.4. Ideal of α-relations and Galois group Definition 8. A polynomial P of k[x 1 , ..., x n ] is called an α-relation if P (α) = 0. Definition 9. The ideal M of k[x 1 , ..., x n ] defined by

Example 2 .

 2 Remark 13. -The ideal of α-relations M is the ideal of α-relations invariants by G α or by I n , the identity group of S n . -The ideal S = I Sn α is the ideal of symmetric relations between the roots of f . Definition 14. Let I be a galoisian ideal of f (over k). The injector of I in M is given by: Inj(I, M) = {σ ∈ S n | (∀R ∈ I) R(α σ(1) , ..., α σ(n) ) = 0}. Inj(S, M) = S n and Inj(M, M) = G α .

b

  P : k[x1, ..., xn]/I → k[x1, ..., xn]/I

  def ABV(P,L,H,I,n,x): d=gap.Index(L,H) lp=Orbite(P,L,H,n) lp=[s.mod(I) for s in lp] lpp=[1 for i in range(d)] pui=[d] for i in range(d): for j in range(d): lpp[j]=(lp[j]*lpp[j]).mod(I) pui= pui + [somme_mod(lpp,I)] Resolvante=pui2polynome(d,[s for s in pui],x) return Resolvante where: -The function somme mod(lpp,I) returns the sum of the reduced elements of the list lpp modulo l. -The function Orbite(P,L,H,n) calculates the orbit of P under the action of L: def Orbite(P,L,H,n) from sage.groups.perm_gps.permgroup import from_gap_list Sn=SymmetricGroup(n) rc= gap.RightCosets(L,H) rc=gap.List(rc,'i->Representative(i)') LTransv=[s for s in rc] return [P * si for si in from_gap_list(Sn,"%s" % LTransv)]

  Algorithm ABV is based on reductions modulo I, Algo2 computes a characteristic polynomial of degree the dimension over k of R = k[x 1 , . . . , x n ]/I and Algo3 produces a square matrix of dimension dim k (R)2 . Then, in the preceeding table, the value of the order c of the injector L of the ideal I is essential because this value also represents the dimension of R over k.

		4!	(6, 12, 4) 2	0.18	0.6 2.96
	5	5!	(4, 25, 5) 12	2.63	9.04 8.14
	5	5!	(4, 20, 5) 24 15.94	19.58 766.27
	5	5!	(3, 6, 5) 60 88.09	96.60 2361.34
	6	6!	(6, 30, 6) 6	2.52	170.1 318
	6	128	(2, 6, 6) 10	7.97	11.43 18.50
	6	6!	(2, 12, 6) 15	2.60	3.57 860.92
	6	6!	(7, 45, 6) 20	4.22	12079.5 571.97
	6	6!	(3, 18, 6) 30	120	876.22 4212.70
	6	6!	(2, 8, 6) 45 118.15	214.05 1577.51
	8	128 (6, 32, 8) 2	8.15	11.92 14.92
	8 1152	(2, 8, 8) 9	17.56	337.42 994.84
	9	9!	(1, 8, 9) 9	5.16	67.45 867.84
	Remark 19.

•

  SAGE http://www.sagemath.org/ • GAP http://www.gap-system.org/ • PrimitiveInvariant GAP-Package of I. Abdeljaouad http://www-gap.mcs.st-and.ac.uk/Gap3/Contrib3/contrib.html • MAXIMA http://maxima.sourceforge.net • Symmetries in MAXIMA, author A. Valibouze http://maxima.sourceforge.net/docs/manual/en/maxima 32.html#SEC125 • MAPLE http://www.maplesoft.com

We fix i ∈ [ [1, d]]. According to Fomula (3) defining the resolvent R P,I , the ith power function p i (R P,I ) of its roots is given by:

this is the evaluation in α of the polynomial

Let check with the following lemma that p i (L.P ) is an L-invariant: Lemma 17. Let L.P = {P 1 , . . . , P d } and s be a symmetric polynomial in k[x 1 , ..., x d ].

Then, the polynomial s(P 1 , . . . , P d ) is an L-invariant. Proof : For any σ ∈ L σ.s(P 1 , . . . , P d ) = s(σ.P 1 , . . . , σ.P d ) = s(P τ (1) , . . . , P τ (d) )

where τ ∈ S d since σ ∈ L and {P 1 , . . . , P d } is the orbit of P under the action of L. As s is a symmetric polynomial, the lemma is proven. Theorem 18. For each i ∈ N, the value in k of the i-th power function p i (R P,I ) of R P,I is given by p i (R P,I ) =

Proof : In our case, the polynomial s of Lemma 17 is the ith power sum p i . Then p i (L.P ) = Q ∈ L.P Q i is L-invariant. By Theorem 15, its evaluation p i (R P,I ) on the roots of f is given by p i (R P,I ) = Q ∈ L.P Q i mod I. Since it is about finding the values in k of p 1 (R P,I ), . . . , p d (R P,I ) where d, the index of H in L, is the degree of the resolvent, our algorithm avoids to develop each polynomial Q ∈ L.P Q i in order to reduce it modulo I. We explain below the process selected.

We fix R = R mod I, for any R ∈ k[x 1 , . . . , x n ], and p i = p i (R P,I ). We calculate Q, Q ∈ L.P , we keep them in a list lp and we build lpp=(1,. . .,1) of length d. At the ith step, 1 ≤ i ≤ d, we suppose that lpp contains Q i-1 , Q ∈ L.P , of the previous step, and we keep the list lp of the first step. The power function p i is computed as follows:

(a) p i :=0 (b) Browse lists lp and lpp simultaneously in order to replace every polynomial

of lpp by u * Q where Q is the element extracted from lp; this new element is Q i . (c) For any (reduced) polynomial u of lpp Do p i := p i + u.

The algorithm ABV

All functions are described in the SAGEmath's language. For our algorithm called ABV which compute relative resolvents we need tree additional functions: somme mod, Orbite and pui2polynome which are described in the follows of the function ABV.

Example

Take for example the polynomial f = x 6 + 2. Its galoisian ideal I is defined by

, be a subgroup of L of index 10 in L.

The package PrimitiveInvariant of GAP (see [START_REF] Abdeljaouad | Calculs d'invariants primitifs de groupes finis[END_REF]) calculates the following L-primitif H-invariant P = x 3 x 6 + x 1 x 6 + x 4 x 5 + x 2 x 5 + x 1 x 4 + x 2 x 3 . Let L.P = {Q 1 , ..., Q 10 } be the orbit of P under the action of L computed with Orbite(P, L, H, 6) where 6 is the degree of f . The first and second power functions of the roots of the resolvent are computed as follows:

By the same way: p 3 (R P,I ) = -6, p 4 (R P,I ) = 0, p 5 (R P,I ) = 0, p 6 (R P,I ) = 36, p 7 (R P,I ) = 0, p 8 (R P,I ) = 0, p 9 (R P,I ) = -24, p 10 (R P,I ) = 0.

We save these ten values in the variable pui and we deduce the resolvent after executing pui2polynome(pui,10). The function ABV(P, L, H, I, 6, x) returns R P,I = x 10 + 2x 7 -4x 4 -8x.


M Stavinschi

W Thuillot

0 years of the IAU Efforts for Capitalizing the Ground-Based Astrometry

Introduction

In 2000 a new IAU working group was founded (IAU GA, Manchester): Future Development of Ground-Based Astrometry (FDGBA). It was revised in 2003 during the IAU GA in Sydney. A new one replaced it in 2006 (IAU GA, Prague): Astrometry by Small Ground-Based Telescopes (ASGBT). It was renewed for other three years during the IAU GA in Rio de Janeiro.

The main aim of the working groups followed the Newsletter No. 1 of the IAU Commission 8, which says:

The post-Hipparcos era has brought an element of uncertainty as to the goals and future programs for all of ground-based astrometry

The purpose of the WGs was "to update and maintain information on astrometric programmes and activities carried out by small telescopes, to diffuse news through these pages and e-mails, to facilitate the collaborations and to help for the coordination of the activities, when possible, in astrometry from ground-based telescopes"

Main objectives of the WGs

The main objectives of the WGs are:

• to identify programs that could be made on instruments that are either insufficiently used or working on projects that have no significant value for the present day astrometry. • to make assessment of the whole situation including available instrumentation • these instruments can be used as they are or with not too expensive modifications to teach students in astronomy how to use telescopes and, in the same time, to contribute in a significant way to astronomy.

• to update and maintain information on astrometric programmes and activities carried out by small telescopes, • to facilitate the collaborations and to help for the coordination of the activities, when possible, in astrometry from ground-based telescopes.

• to teach the astrometric theory and practice to the next generation

The IAU WG ASGBT encourages astrometric measurements of positions for dynamics, fundamental astronomy or astrophysics, but also photometric observations of events for determination of size and shape, determination of the parameters of rotation can pay benefit from these instruments. This is possible e.g. thanks to observations of mutual events of the natural satellites, stellar occultations, mutual events of binary asteroids.

In this context, the encouraged cooperative projects are:

• Mutual phenomena of natural satellites (PHEMU -PHESAT) & binary asteroids • Ground-based monitoring of astrometric binaries (GMAB) • Dedicated astrometric network for the follow-up of Gaia (http://www.rssd.esa.int/index.php?project=Gaia) • Astrometry of Radiosources optical counterparts for ICRF sources positionning • Astrometry of natural satellites for their ephemerides • Prediction of stellar occultations by specific objects, last minute astrometry (TNOs, Pluto…).

Limitations of the space astrometry missions

Astrometry by small ground-based telescope remains very useful in complement to space astrometry, since there are limitations of the space missions:

• not flexible: observations are either constrained by a scanning law (Gaia) or by overall programming (SIM or HST);

• not designed for monitoring: it is not possible to get long sequences of observation of a single body;

• limited lifetime: many astronomical features must be observed either indefinitely or at least a longer time;

• often need preliminary data: for instance, ephemerides or prediction of magnitudes of irregular variables

• they are risky.

Astrometric activities in complement to Gaia

Gaia will get benefit from a dedicated network for observations on alert and follow-up.

Several observations can be made with small telescopes (e.g. determination of some asteroidal masses, the improvement of orbital models of neglected natural satellites.)

The work of the actual surveys and the advent of new large and fast surveys (e.g. Pan-Starrs, LSST) which store huge amounts of data reinforces the need to have follow-up observations, in particular for the study of the Near-Earth objects and the improvement of their orbits.

A Follow-up program for Gaia relates mainly to the astrometric aspect for solar system objects and intends to call for astrometrists to join a dedicated network to carry out these observations.

Context and problems

To ensure the maximum efficiency of the observations of detection by Gaia, it is needed to organize observations "on alert" to check and follow-up from the ground. Several means make it possible to organize these observations, in particular the diffusion of alarms by Internet on mailing lists (e.g. Minor Planet Mailing List) or the maintenance of an official page of targets. Whichever means used, even if they reach a great number of potential observers, would not ensure that good reactivity to alarms would occur. The constitution of a formalized network of dedicated observers appears necessary.

Constraints

It will be necessary to have a possibility of access to the telescopes "on alert" by a local observer. The process of observation of Gaia will allow that alarm to be given approximately 48 hours after the detection of an uncatalogued target. It will be necessary to have sensitive enough CCD cameras to detect objects as faint as magnitude 20, and pixel sizes corresponding to less than 1" on the sky. During the mission, if a preliminary catalogue from GAIA is available, smaller fields could be usable. It will be desirable that certain sites are of sufficient quality (high altitude) to reach observations with small solar elongation. Gaia will detect objects with a solar elongation down to 45°.

Conclusion

A follow-up program will be necessary to ensure the objects (of stellar, galactic and extragalactic objects; objects of the solar system and numerous new objects) are not lost and to improve their ephemerides. Organizing a network requires time and different steps have to be done. The IAU WG Astrometry by small ground based telescopes encourage observers interested in this network, and particularly astrometric observers, to join the network now to help follow-up Gaia.