Mohamed Assellaou
email: assel-laou.med@gmail.com

Athena Picarelli
email: a.picarelli@imperial.ac.uk

A Hamilton-Jacobi-Bellman approach for the numerical computation of probabilistic state constrained reachable sets

Aim of this work is to characterise and compute the set of initial conditions for a system of controlled diffusion processes which allow to reach a terminal target satisfying pointwise state constraints with a given probability of success. Defining a suitable auxiliary optimal control problem, the characterization of this set is related to the solution of a particular Hamilton-Jacobi-Bellman equation. A semi-Lagrangian numerical scheme is defined and its convergence to the unique viscosity solution of the equation is proved. The validity of the proposed approach is then tested on some numerical examples.

Introduction

We consider the control of stochastic differential equations in R d of the following form dX(s) = b(s, X(s), u(s))ds + σ (s, X(s), u(s))dB(s), ∀s ∈ [t, T ] X(t) = x .

Given a fixed time horizon T > 0, we aim to characterize the set of initial states from which, with an assigned level of probability, it is possible to reach a target set at time T satisfying some state constraints along the whole interval [t, T ]. More precisely, let C and K be two non-empty subsets of R d representing respectively the target set and the set of state constraints and let ρ ∈ [0, 1). We define the state constrained backward reachable set under probability of success ρ as the set, hereafter denoted by Ω ρ t , of initial points x ∈ R d for which the probability to steer the system (1) towards C maintaining the dynamics in the set K is higher than ρ, i.e.

x ∈ R d : ∃u ∈ U , P X u t,x (θ ) ∈ K , ∀θ ∈ [t, T ] and X u t,x (T ) ∈ C > ρ , where X u t,x (•) represents the strong solution to (1) associated with the control u ∈ U . Assumptions on the coefficients in [START_REF] Abate | Computational approaches to reachability analysis of stochastic hybrid systems[END_REF] and on the set of controls U will be made clear in the next section. Such backward reachable sets play an important role in many applications, as the set Ω ρ t can be interpreted as a "safety region" for reaching C remaining in the set K , with confidence ρ. It turns out that the set Ω ρ t can be characterized by means of the so-called level set approach. At the basis of this approach there is the idea to look at the set of interest, the set Ω ρ t in our case, as the level set of a certain function solution of a suitable partial differential equation (PDE). Such a characterization of the set is particularly useful in view of its numerical approximation, since it opens the way to the use of a wide choice of numerical methods designed for PDEs. Originally introduced in [START_REF] Osher | Fronts propagating with curvature dependent speed: algorithms on Hamilton-Jacobi formulations[END_REF] to model front propagation problems, this approach immediately resulted in a very powerful method for studying backward reachable sets of continuous non-linear dynamical systems under very general conditions. In [START_REF] Falcone | Level sets of viscosity solutions: Some applications to fronts and rendez-vous problems[END_REF][START_REF] Mitchell | A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games[END_REF] this idea is used to describe the reachable sets for deterministic problems. The link between stochastic target problems and level set approach is established in [START_REF] Soner | A stochastic representation for level set equations[END_REF]. More recently, the level set approach has been extended to the case of state-constrained controlled systems [START_REF] Bokanowski | Reachability and minimal times for state constrained nonlinear problems without any controllability assumption[END_REF][START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF] and probabilistic reachability problems [START_REF] Assellaou | Error estimates for second order hamiltonjacobi-bellman equations. approximation of probabilistic reachable sets[END_REF].

In our case, we will show that it is straightforward to see that

Ω ρ t = x ∈ R d : ϑ (t, x) > ρ , ( 2
)
where ϑ is the value function associated to the following optimal control problem:

ϑ (t, x) := sup u∈U E 1 C (X u t,x (T )) min θ ∈[t,T ] 1 K (X u t,x (θ )) , (3)
with the standard notation a ∧ b := min(a, b). In particular, equality (2) characterises the set Ω ρ t for t ∈ [0, T ] by means of the function ϑ . We point out that, in the discrete time setting, a similar approach has been considered in [START_REF] Abate | Computational approaches to reachability analysis of stochastic hybrid systems[END_REF][START_REF] Abate | Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems[END_REF][START_REF] Margellos | Hamilton-Jacobi formulation for Reach-avoid differential games[END_REF]. In this case, the value function is obtained recursively by solving the dynamic programming principle. In the present paper, we are interested in the approximation of the probabilistic backward reachable sets for time-continuous stochastic processes by PDE techniques. In the non controlled framework, an alternative numerical algorithm consist in using Monte Carlo simulations to generate a set of trajectories starting from a given initial position. The percentage of trajectories reaching the target without violation of the state constraints gives an approximation of the probability of success when starting from this position. On the other hand, for linear stochastic systems, a bound for the probability of hitting a target can be obtained by using the enclosing hulls of the probability density function for time intervals, see [START_REF] Althoff | Safety assessment of autonomous cars using verification techniques[END_REF][START_REF] Althoff | Safety assessment for stochastic linear systems using enclosing hulls of probability density functions[END_REF]. However, it is worth noticing that these approaches are used to calculate the probabilities of success but do not allow to define the entire set of points that have the same given probability. In addition, Monte-Carlo based methods often require a large number of simulations to obtain a good accuracy. We will use such simualtions in Section 5 as a comparison to validate our approach. In the context of financial mathematics, the problem of characterizing the backward reachable set with a given probability was first introduced by Föllmer and Leukert [START_REF] Föllmer | Quantile hedging[END_REF]. This problem was also studied and converted into the class of stochastic target problems by Touzi, Bouchard and Elie in [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF]. However in these references the possible presence of state constraints is not taken into account. In order to apply a dynamic programming approach and characterize the value function ϑ as the unique viscosity solution of a Hamilton-Jacobi-Bellman (HJB) equation we face two main difficulties. First, the discontinuous cost functional given by the presence of the indicator functions would require to make use of the notion of discontinuous viscosity solutions. Establish uniqueness results in such a framework is usually a very hard task, so we propose here to work on a regularized version of problem [START_REF] Althoff | Safety assessment of autonomous cars using verification techniques[END_REF]. Second, the non commutativity between expectation and maximum operator makes problem (3) not satisfying the natural "Markovian structure" necessary to apply the dynamic programming arguments. We here follow the ideas in [START_REF] Barron | The Bellman equation for control of the running max of a diffusion and applications to lookback options[END_REF][START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF][START_REF] Grüne | Zubov's method for controlled diffusions with state constraints[END_REF][START_REF] Kröner | Infinite horizon stochastic optimal control problems with running maximum cost[END_REF] and define an auxiliary optimal control problem in an augmented state space and derive the HJB equation for this problem recovering the value function ϑ solution of the original problem at a later stage. The obtained HJB equation is defined in a domain and completed with mixed Dirichlet and oblique derivative boundary conditions. Derivative conditions (to be considered in the viscosity sense, see Definition 1) typically arise dealing with running maxima in the cost functional (see also [START_REF] Barron | The Bellman equation for control of the running max of a diffusion and applications to lookback options[END_REF][START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF]), while the Dirichlet condition will be naturally satisfied pointwise by our value function. We discuss the numerical approximation of the obtained HJB equation. We introduce a semi-Lagrangian (SL) approximation scheme which incorporates the aforementioned boundary conditions and we prove its convergence to the viscosity solution following the framework in [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF]. We recall that SL scheme for second order HJB equations have been introduced by Menaldi in [START_REF] Menaldi | Some estimates for finite difference approximations[END_REF] and then studied by Camilli and Falcone [START_REF] Camilli | An approximation scheme for the optimal control of diffusion processes[END_REF]. We refer to [START_REF] Debrabant | Semi-Lagrangian schemes for linear and fully non-linear diffusion equations[END_REF] and the references therein for an overview. Derivative boundary conditions have been added to the scheme in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF], while the case of mixed Dirichlet-derivative conditions has been recently studied in [START_REF] Kröner | Infinite horizon stochastic optimal control problems with running maximum cost[END_REF].

The paper is organised as follows. In Section 2 we present the problem and give some preliminary results. The regularized problem is introduced in Section 2.2. Section 3 is devoted to the development of the dynamic programming arguments and the HJB characterization. In Section 4 we discuss the numerical aspects and state the main convergence result. Numerical tests are presented in Section 5

2 Formulation of the problem and preliminary results

Problem formulation.

Let {Ω , F t , {F t } t≥0 , P} be a filtered probability space and B(•) a given p-dimensional Brownian motion. Let T > 0. We denote by U the set of all progressively measurable processes valued in U ⊂ R m , U compact set. For any u ∈ U , let us consider the following system of stochastic differencial equations (SDEs) in R d :

dX(s) = b(s, X(s), u(s))ds + σ (s, X(s), u(s))dB(s), ∀s ∈ [t, T ] X(t) = x. (4)
The following classical assumptions will be considered on the coefficients b and σ :

(H1) σ : [0, T ] × R d × U → R d×p and b : [0, T ] × R d × U → R d are
for any t ∈ [0, T ], x, y ∈ R d and u ∈ U.
It is well known that, under assumption (H1), for any u ∈ U there is a unique strong solution to (4) [START_REF] Yong | of Applications of Mathematics[END_REF]p. 42,Thm. 6.3]. We denote by X u t,x (•) such a solution.

Let C and K be nonempty open sets in R d , representing respectively the target set and the set of state constraints. Let ρ ∈ [0, 1) an assigned value of success probability. We define the backward reachable set under probability of success ρ, as the set Ω ρ t of initial points x ∈ R d from which it starts a trajectory X u t,x (•) such that the probability to reach the target C at the final instant T satisfying the constraint K in the interval [t, T ] is grater than ρ, i.e.:

Ω ρ t := x ∈ R d : ∃u ∈ U , P X u t,x (θ ) ∈ K , ∀θ ∈ [t, T ] and X u t,x (T ) ∈ C > ρ .
For a given set O ⊆ R d we will denote by 1 O its indicator function, i.e.

1 O (x) := 1 if x ∈ O 0 otherwise.
One can easily verify that

1 C (X u t,x (T )) min θ ∈[t,T ] 1 K (X u t,x (θ )) = 1 if X u t,x (θ ) ∈ K ∀θ ∈ [t, T ] and X u t,x (T ) ∈ C 0 otherwise, (5)
i.e. the expression on the left hand side is an indicator function for the event

X u t,x (θ ) ∈ K ∀θ ∈ [t, T ] and X u t,x (T ) ∈ C .
It follows that, for any u ∈ U , P X u t,x (θ ) ∈ K , ∀θ ∈ [t, T ] and X u t,x (T ) ∈ C can be expressed by

E 1 C (X u t,x (T )) min θ ∈[t,T ] 1 K (X u t,x (θ )) .
As a consequence, it is possible to describe the set Ω ρ t using optimal control tools just looking at the evolution of the level sets of the following value function:

ϑ (t, x) := sup u∈U E 1 C (X u t,x (T )) min θ ∈[t,T ] 1 K (X u t,x (θ )) . (6)
Proposition 1. Let assumption (H1) be satisfied. Then, for t ∈ [0, T ], we have:

Ω ρ t = {x ∈ R d : ϑ (t, x) > ρ}. Proof. If x ∈ Ω ρ t , thanks to equality (5) E 1 C (X u t,x (T )) min θ ∈[t,T ] 1 K (X u t,x (θ )) > ρ
for some control u ∈ U and it follows ϑ (t, x) > ρ.

Let us now suppose that ϑ (t, x) > ρ. By the definition of the supremum and the fact that U is a non empty set, one has that, for some control ū ∈ U ,

E 1 C (X ū t,x (T )) min θ ∈[t,T ] 1 K (X ū t,x (θ )) > ρ
and then, using again (5), x ∈ Ω ρ t .

Motivated by this result, we are going to focus on the characterization and numerical approximation of the function ϑ . Problem ( 6) is an optimal control problem with a discontinuous cost in a "minimum form". This is not a standard formulation in optimal control theory for two main reasons: first, the discontinuity of the cost functional prevents the characterization of (6) as the unique viscosity solution of a HJB equation, second the loss of Markovian structure in the cost, due to the presence of the minimum operator inside the expectation, makes the dynamic programming arguments not directly applicable. We discuss the first issue in the next section.

Regularized Problem

The discontinuity introduced by the presence of the indicator functions and the consequent necessity of dealing with the notion of discontinuous viscosity solutions (see for instance [START_REF] Fleming | Controlled Markov Processes and Viscosity Solutions[END_REF]Section VII.4] for their definition) pose nontrivial issues when attempting to establish uniqueness results for the associated HJB equation. To overcome this difficulty, from now on we will work with a regularized version of the cost functional in [START_REF] Assellaou | Error estimates for second order hamiltonjacobi-bellman equations. approximation of probabilistic reachable sets[END_REF]. In particular, observing that the indicator functions 1 C and 1 K can be written as

1 C (z) = 1 if d ∂ C (z) < 0 0 if d ∂ C (z)≥0 , 1 K (z) = 1 if d ∂ K (z) < 0 0 if d ∂ K (z)≥0
where d ∂ C and d ∂ K are respectively the signed distance function to ∂ C and ∂ K , we consider the following regularized functions φ ε C and φ ε K (see Figure 1):

φ ε C (x) := min(1, max(0, - 1
ε d ∂ C (x))), φ ε K (x) := min(1, max(0, - 1
ε d ∂ K (x)))
and the optimal control problem

ϑ ε (t, x) := sup u∈U E φ ε C (X u t,x (T )) min θ ∈[t,T ] φ ε K (X u t,x (θ )) . ( 7
) d O (x) 1 -ε φ ε O (x) Fig. 1 Regularization of the indicator function in the case O = (-∞, 0) Remark 1. Note that the choice of φ ε . is such that φ ε . ≤ 1 . which implies ϑ ε (t, x) > ρ ⇒ ϑ (t, x) > ρ.
Hence if we are able to find a numerical approximation

ϑ ε of ϑ ε such that | ϑ ε - ϑ ε | ≤ η for some η ≥ 0, we will have θ ε (t, x) > ρ + η ⇒ ϑ ε (t, x) > ρ ⇒ ϑ (t, x) > ρ.
This regularization allow us to deal with a continuous cost and also to obtain the following regularity result for the associated value function:

Proposition 2.
Let assumption (H1) be satisfied and let ε > 0. The value function ϑ ε is Lipschitz continuous with respect to x and 1 2 -Hölder continuous with respect to t, i.e. there exists a constant L ε > 0 such that

|ϑ ε (t, x) -ϑ ε (s, y)| ≤ L ε |x -y| + |t -s| 1 2 (1 + |x| + |y|) for any t, s ∈ [0, T ], x, y ∈ R d . Proof. Let 0 ≤ t ≤ s ≤ T , x, y ∈ R d . Thanks to the property of minimum operator |(a ∧ b) -(c ∧ d)| ≤ |a -c| ∨ |b -d|, one has: |ϑ ε (t, x) -ϑ ε (t, y)| (8) ≤ sup u∈U E φ ε C (X u t,x (T )) min θ ∈[t,T ] φ ε K (X u t,x (θ )) -φ ε C (X u t,y (T )) min θ ∈[t,T ] φ ε K (X u t,y (θ )) ≤ sup u∈U E φ ε C (X u t,x (T )) -φ ε C (X u t,y (T )) max θ ∈[t,T ] φ ε K (X u t,x (θ )) -φ ε K (X u t,y (θ ))
and

|ϑ ε (t, x) -ϑ ε (s, x)| (9) ≤ sup u∈U E φ ε C (X u s,X u t,x (s) (T )) -φ ε C (X u s,x (T )) max θ ∈[t,s] φ ε K (X u t,x (θ )) -φ ε K (x) max θ ∈[s,T ] φ ε K (X u s,X u t,x (s) (θ )) -φ ε K (X u s,x (θ )) .
It can be easily verified that φ ε C and φ ε K are Lipschitz continuous functions with Lipschitz constant 1/ε. Then by ( 8) and ( 9) we get

|ϑ ε (t, x) -ϑ ε (t, y)| ≤ 1 ε sup u∈U E max θ ∈[t,T ] X u t,x (θ ) -X u t,y (θ )
and

|ϑ ε (t, x) -ϑ ε (s, x)| ≤ 1 ε sup u∈U E max θ ∈[t,s] X u t,x (θ ) -x max θ ∈[s,T ] X u s,X u t,x (s) (θ ) -x .
Under assumption (H1), there exists some constant C > 0 such that for any 0 ≤ t ≤ s ≤ T , x, y ∈ R d the unique strong solution to equation ( 4) satisfies

E sup θ ∈[t,s] X u t,x (θ ) -X u t,y (θ ) 2 ≤ C|x -y| 2 , (10)
E sup θ ∈[t,s] X u t,x (θ ) -X u s,x (θ ) 2 ≤ C(1 + |x| 2 ) |t -s| (11)
(see for instance [START_REF] Yong | of Applications of Mathematics[END_REF]Theorem 6.3]). Hence, the result follows just taking L ε := C/ε. Remark 2. It has been proved in [6, Theorem 3.1] that, if K = R d and C is a non empty, convex set with a C 1 regular boundary, under the uniform ellipticity condition, for some α > 0, ∀(t, x, u)

∈ (0, T ) × R d ×U, σ (t, x, u)σ (t, x, u) T ≥ α1 d . ( 12
)
where 1 d is the identity matrix, the following holds:

|ϑ (t, x) -ϑ ε (t, x)| ≤ C 1 + |x| 2 + | log ε| (T -t) d ε ( 13
)
for some constant C depending only on α and the constants in assumption (H1). We conjecture that analogous estimates can be obtained in the general case K = R d , but a rigorous proof of this fact is still material of ongoing research.

Dynamic programming and Hamilton-Jacobi-Bellman equation

Aim of this section is to characterize the function ϑ ε as a (viscosity) solution to a suitable HJB equation. For doing this, we closely follow the dynamic programming arguments recently developed in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF][START_REF] Grüne | Zubov's method for controlled diffusions with state constraints[END_REF] for optimal control problems with a cost depending on a running maximum. Therefore, in order to directly use those results in our framework, we will rewrite the optimal control problem ( 7) by means of the cost functional

J(t, x, u) := E -φ ε C (X u t,x (T )) max θ ∈[t,T ] -φ ε K (X u t,x (θ )) (14)
such that the following holds

ϑ ε (t, x) = -inf u∈U J(t, x, u).
The presence of the maximum operator inside the expectation, makes the cost in [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] non-Markovian preventing the direct use of the Dynamic Programming Principle (DPP), which is the first fundamental result towards the HJB characterisation. A classical strategy to overcome this difficulty consists in adding an auxiliary variable y that, roughly speaking, gets rid of the non-Markovian component of the cost. This has been originally used in [START_REF] Barron | The Bellman equation for control of the running max of a diffusion and applications to lookback options[END_REF] where an approximation technique of the L ∞ -norm is used, whereas in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF][START_REF] Grüne | Zubov's method for controlled diffusions with state constraints[END_REF] the HJB equation is derived without making use of any approximation.

Let us introduce the following value function:

w ε (t, x, y) := inf u∈U E -φ ε C (X u t,x (T )) max θ ∈[t,T ] -φ ε K (X u t,x (θ )) y . (15)
Defining the process

Y u t,x,y (.) := max s∈[t,.] -φ ε K (X u t,x (s)) y,
the value function [START_REF] Debrabant | Semi-Lagrangian schemes for linear and fully non-linear diffusion equations[END_REF] can also be written as

w ε (t, x, y) = inf u∈U E -φ ε C (X u t,x (T )) Y u t,x,y (T ) .
Observe that the following property holds:

ϑ ε (t, x) = -w ε (t, x, -1), (16)
so from now on only the optimal control problem (15) will be taken into account, since the corresponding value of the function ϑ ε can be derived by the previous equality. The following property is satisfied:

Proposition 3.
Let assumption (H1) be satisfied. Then, there exists a constant C > 0 such that for any ε > 0, t, s ∈ [0, T ], (x, y), (x , y ) ∈ R d+1 one has

|w ε (t, x, y) -w ε (s, x , y )| ≤ C ε |x -x | + |y -y | + |t -s| 1 2 (1 + |x| ∨ |x |) .
Moreover, for any family of stopping times {τ u , u ∈ U } with values in [t, T ] one has

w ε (t, x, y) = inf u∈U E w ε (τ u , X u t,x (τ u ),Y u t,x,y (τ u )) (17)
for any (t, x, y) ∈ [0, T ] × R d+1 .

Proof. The regularity of w ε with respect to t and x can be proved as in Proposition 2, while the Lipschitzianity with respect to y is trivial. Thanks to the regularity of w ε , the DPP [START_REF] Fleming | Controlled Markov Processes and Viscosity Solutions[END_REF] follows by arguments similar to [START_REF] Bouchard | Weak dynamic programming principle for viscosity solutions[END_REF] observing that for the couple of variables (X u t,x (•),Y u t,x,y (•)) the following property holds:

X u t,x (s) Y u t,x,y (s) = X u θ ,X u t,x (θ ) (s) Y u θ ,X u t,x (θ ),Y u t,x,y (θ ) (s) a.s.
for any t ≤ θ ≤ s ≤ T ( with θ possibly a stopping time). We remand to [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF] for a sketch of the proof showing how the arguments in [START_REF] Bouchard | Weak dynamic programming principle for viscosity solutions[END_REF] adapt to our case.

HJB equation

Proposition 3 is the main tool for proving the next result that characterizes w ε as the unique solution, in the viscosity sense, of a suitable HJB equation. In the sequel we will restrict our domain to

D := {(x, y) ∈ R d+1 : -φ ε K (x) < y < 0}.
Indeed, the knowledge of w ε in D is sufficient to characterize it everywhere thanks to the following relation:

w ε (t, x, y) = y for any y ≥ 0 w ε (t, x, y) = w ε (x, -φ ε K (x)) for any y ≤ -φ ε K (x). (18)
Based on this observation, it is sufficient to characterise w ε in the domain D. Letting

Γ 1 := {(x, y) ∈ D : y = 0}; Γ 2 := {(x, y) ∈ D : y = -φ ε K (x)}, (19)
we are going to prove that w ε is the unique solution (in the weak sense specified in Definition 1 below) of the following HJB equation with mixed derivative-Dirichlet boundary conditions:

       -∂ t w + H(t, x, D x w, D 2 x w) = 0 [0, T ) × D w = 0 [0, T ) × Γ 1 -∂ y w = 0 [0, T ) × Γ 2 w(T, x, y) = w 0 (x, y) D (20)
with

H(t, x, p, Q) := sup u∈U -b(t, x, u)p - 1 2 Tr[σ σ T ](t, x, u)Q (21)
and

w 0 (x, y) := -φ ε C (x) -φ ε K (x) y.
We point out that the derivative boundary condition -∂ y w = 0 on Γ 2 is typically obtained in presence of a running maximum cost, see [START_REF] Barron | The Bellman equation for control of the running max of a diffusion and applications to lookback options[END_REF][START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF], while the Dirichlet condition w ε = 0 on Γ 1 is obtained by the very definition of w ε . Observe also that the constant Dirichlet condition on Γ 1 is compatible with the homogeneus derivative condition on Γ 2 . This prevents possible problems related with mixed boundary conditions at the junctions where different components of the boundary cross.

The fully nonlinearity and degeneracy of the equation requires to consider solutions in the viscosity sense (see [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] for an overview on the subject). This notion of solution requires also to specify in which sense boundary conditions are satisfied. In paricular, we ask the Dirichlet conditions on Γ 1 to be satisfied in the strong sense, whereas the derivative conditions on Γ 2 are considered in the (weak) viscosity sense. Definition 1. A USC function w (resp. LSC function w) on [0, T ] × D is a viscosity sub-solution (resp. super-solution) of ( 20), if for every function ϕ ∈ C 1,2 ([0, T ]×D), at each maximum (resp. minimum) point (t, x, y) of w-ϕ (resp. w-ϕ) the following inequality holds

       -∂ t ϕ + H(t, x, D x ϕ, D 2 x ϕ) ≤ 0 [0, T ) × D ϕ ≤ 0 [0, T ) × Γ 1 min -∂ y ϕ, -∂ t ϕ + H(t, x, D x ϕ, D 2 x ϕ) ≤ 0 [0, T ) × Γ 2 ϕ(T, x, y) ≤ w 0 (x, y) D resp.        -∂ t ϕ + H(t, x, D x ϕ, D 2 x ϕ) ≥ 0 [0, T ) × D ϕ ≥ 0 [0, T ) × Γ 1 max -∂ y ϕ, -∂ t ϕ + H(t, x, D x ϕ, D 2 x ϕ) ≥ 0 [0, T ) × Γ 2 ϕ(T, x, y) ≥ w 0 (x, y) D.
A continuous function w on [0, T ] × D is a viscosity solution of (20) if it is both a sub-and super-solution.

Theorem 1. Let assumption (H1) be satisfied. Then, w ε is the unique bounded and continuous viscosity solution of the HJB equation [START_REF] Kloeden | Numerical solution of stochastic differential equations[END_REF].

Proof. The Dirichlet and terminal conditions are ensured by the very definition of w ε and its continuity. In particular, the continuity allows the conditions to be considered in the strong sense. The proof of sub-and supersolution properties in

Numerical Approximation

In this section we discuss an approximation scheme for the unique continuous viscosity solution w ε to the equation

∂ t w + H(t, x, D x w, D 2 x w) = 0 -φ ε K (x) < y < 0, t ∈ (0, T ] (22a) w = 0 y = 0, t ∈ (0, T ] (22b) -∂ y w = 0 y = -φ ε K (x), t ∈ (0, T ] (22c)
with initial data

w(0, x, y) = w ε 0 (x, y) -φ ε K (x) ≤ y ≤ 0 (22d)
(the convenient change of variable t → Tt has been here applied).

In [10, Section 4.1] a general convergence result for numerical schemes approximating HJB equations under oblique derivative boundary conditions as (22c) is provided. Those arguments can be easily modified in order to prove convergence also in presence of the additional Dirichlet boundary condition (22b) (see also [START_REF] Kröner | Infinite horizon stochastic optimal control problems with running maximum cost[END_REF]). Following the ideas introduced in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF], we present here a semi-Lagrangian (SL) scheme for the approximation of [START_REF] Margellos | Hamilton-Jacobi formulation for Reach-avoid differential games[END_REF]. The same scheme will be used in the numerical experiments in Section 5.

Let N ≥ 1 be an integer (number of time steps), and let

h := T N and t n := nh for n = 0, . . . , N. Let ∆ x = (∆ x 1 , . . . , ∆ x d ) ∈ (R * + )
d and ∆ y > 0, and let G ρ (where ρ ≡ (∆ x, ∆ y)) be the space grid

G ρ := (x i , y j ) = (i∆ x, j∆ y), for (i, j) ∈ Z d × Z .
The grid is considered uniform for simplicity of presentation. We also assume that the discretization in the y coordinate is aligned with the boundary of the domain, this allows us to get the Dirichlet condition exactly.

We look for a fully discrete scheme for the viscosity solution of ( 22) on the timespace grid {t 0 , . . . ,t N } × (G ρ ∩ D). Following the ideas in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF][START_REF] Kröner | Infinite horizon stochastic optimal control problems with running maximum cost[END_REF] the numerical scheme is defined starting from a standard scheme for (22a), which is then mixed with a step of "projection" on Γ 2 and the use of the Dirichlet condition on Γ 1 . The approximation of equation (22a) we consider is the SL scheme proposed by Camilli and Falcone [START_REF] Camilli | An approximation scheme for the optimal control of diffusion processes[END_REF] and also used in [START_REF] Debrabant | Semi-Lagrangian schemes for linear and fully non-linear diffusion equations[END_REF]. We recall that first schemes of this type have been introduced by Menaldi in [START_REF] Menaldi | Some estimates for finite difference approximations[END_REF].

Let σ u = σ (•, •, u) and b u = b(•, •, u), and let (σ u k ) k=1,...,p denote the column vectors of σ u . We consider the following operator T :

T (ϕ)(t, x, y) := min u∈U 1 2p ∑ k=1,...,2p ϕ(t, ., y) x + hb u (t, x) + √ h σ u k (t, x) (23)
with the following vector definition in R d :

σ u 2k-j := √ p (-1) j σ u k ( 24
)
for k = 1, . . . , p and j ∈ {0, 1}. Now

[•] ≡ [•]
x stands for a monotone, P 1 interpolation operator on the x-grid (x i ), satisfying in particular:

   (i) [ϕ](x i ) = ϕ(x i ), for any i ∈ Z d , (ii) |[ϕ](x) -ϕ(x)| ≤ C|∆ x| 2 D 2 x ϕ ∞ for any ϕ ∈ C 2 (R d , R), (iii) for any functions ϕ, ψ : R d → R, ϕ ≤ ψ ⇒ [ϕ] ≤ [ψ]. ( 25
)
We point out that [START_REF] Menaldi | Some estimates for finite difference approximations[END_REF], if considered without interpolation, is a discretization in time of the Dynamic Programming Principle. In particular, such an approximation uses an Euler-Maruyama scheme (see [START_REF] Kloeden | Numerical solution of stochastic differential equations[END_REF] for instance) coupled with a finite state discretization of the Gaussian discribution to approximate the dynamics X u t,x (•). The numerical scheme is defined as follows:

Algorithm. Initialization step, for n = 0, for all i, j:

W 0 i, j = w ε 0 (x i , y j ).
Then, for n = 0, . . . , N -1:

Step

1 Compute W n+1 i, j = T (W )(t n , x i , y j ), for all (x i , y j ) ∈ G ρ ∩ D; Step 2 Assign W n+1 i, j = W n+1 i, j x i
, for all (x i , y j ) :

y j ≤ -φ ε K (x i ); W n+1
i, j = y j , for all (x i , y j ) : y j ≥ 0;.

where for every x ∈ R d , j x ∈ Z is defined by

j x := min j ∈ Z : j∆ y ≥ -φ ε K (x)
and we also used the following short notation

W n i, j = W (t n , x i , y j ).
Hereafter we will denote by W = (W n i j ) n=1...N (i, j)∈Z d+1 the solution of the numerical scheme defined by the algorithm above on {t 0 , . . . ,t N } × G ρ . We point out that the necessity of defining W also at mesh points outside D comes from the fact that the SL scheme involves values outside the domain. However, this is not a issue in virtue of (18) (see Step 2 above). We also denote by W ρ,h the continuous extension of W to [0, T ] × R d × R obtained by linear interpolation. Remark 3. The numerical solution W ρ,h is Lipschitz continuous in y with Lipschitz constant independent of ρ and h. This can be derived by the very definition of the operator T in [START_REF] Menaldi | Some estimates for finite difference approximations[END_REF]. Indeed, given W n L-Lipschitz continuous in y one can observe that

|W n+1 i, j -W n+1 i, j | = |T (W )(t n , x i , y j ∨ y j x i ) -T (W )(t n , x i , y j ∨ y j x i )| ≤ L|(y j ∨ y j x i ) -(y j ∨ y j x i )| ≤ L|y j -y j |.
Hence, being W 0 Lipschitz continuous, the same property holds for W n for all n = 1 . . . N. Then, since the linear interpolation (used to pass from W to W ρ,h ) preserve Lipschitz constants, we can obtain the desired property.

Remark 4. The core of the scheme in Step 1 can be written as

S(t, x, y,W n+1 i, j ,W ) := W n+1 i, j -T (W )(t n , x i , y j ) = 0.
It is immediate to verify that S is monotone in the sense of Barles and Souganidis [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF], i.e. for every h, ρ > 0, r ∈ R, for all function φ , ψ such that φ ≥ ψ, inequality S(t, x, y, r, φ ) ≤ S(t, x, y, r, ψ)

holds.

The choice of σ u k in (24) leads to the following consistency estimate, for any ϕ ∈ C 2,4 ((0, T ) × R d × R):

1 h S(t, x, y, ϕ(t, x, y), φ ) -∂ t ϕ + H(t, x, D x ϕ, D 2 x ϕ) ≤ C 1 |b u (t, x)| 2 D 2 x ϕ ∞ + |b u (t, x)||σ u (t, x)| 2 D 3 x ϕ ∞ + |σ u (t, x)| 4 D 4 x ϕ ∞ ∂ 2 tt ϕ ∞ h + C 2 D 2 x ϕ ∞ |∆ x| 2 h .
These are classical properties of SL schemes, see [START_REF] Debrabant | Semi-Lagrangian schemes for linear and fully non-linear diffusion equations[END_REF] for instance. In particular, the error term in |∆ x| 2 /h comes the interpolation error estimate (ii) (observe that we do not need to interpolate with respect to y) and the term in h from classical Taylor expansions. Then, in order to ensure consistency of the scheme, ∆ x and h have to be chosen so that |∆ x| 2 /h → 0 as ∆ x, h → 0. This usually leads to the choice ∆ x ∼ h in numerical simulations. Moreover, it is easy to verify that the scheme admits a bounded solution in {t 0 , . . . ,t N } × (G ρ ∩ D), so that the scheme is also stable.

We recall that monotonicity, consistency and stability are the fundamental properties necessary for proving convergence of numerical schemes in the framework of viscosity solutions, see [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF].

Theorem 2. Let assumption (H1) be satisfied. Let W ρ,h be the solution of the scheme defined by Algorithm 1, where T is the SL scheme (23)- [START_REF] Mitchell | A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games[END_REF]. Then, if

|∆ x| 2 h → 0 as ∆ x, h → 0 (26) W ρ,h converges to w ε in [0, T ] × D as ρ, h → 0.
Proof. The proof follows the strategy in [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF] and [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF]. Let us define for (t, x, y) ∈

[0, T ] × D W (t, x, y) := lim sup [0,T ]×D (s,ξ ,γ)→(t,x,y) ρ,h→0 W ρ,h (s, ξ , γ), W (t, x, y) := lim inf [0,T ]×D (s,ξ ,γ)→(t,x,y) ρ,h→0 W ρ,h (s, ξ , γ).
One clearly has W (t, x, y) ≤ W (t, x, y) for any (t, x, y) ∈ [0, T ] × D. Convergence follows by the comparison principle once shown that W and W are respectively a sub-and supersolution of the HJB equation in the sense of Definition 1.

We sketch the proof of the subsolution property, the supersolution part can be proved in a similar way. Given a smooth test function ϕ, let (t, x, ȳ) be a maximum point for (Wϕ), with (Wϕ)(t, x, ȳ) = 0, and let

(ρ k , h k ,t k , x k , y k ) be such that (t k , x k , y k ) ∈ [0, T ] × D, ρ k , h k → 0, (t k , x k , y k ) → (t, x, ȳ), W ρ k ,h k (t k , x k , y k ) → W (t, x, ȳ) and (W ρ k ,h k -ϕ)(t k , x k , y k ) = max(W ρ k ,h k -ϕ) = δ k → 0
(the existence of such a sequence follows by classical arguments in viscosity theory).

If ( x, ȳ) ∈ D the result follows as in [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF] using the prperties of monotonicity and consistency of the scheme in a sufficiently small neighborhood of ( x, ȳ) still contained in D.

If ( x, ȳ) ∈ Γ 2 one can work under the condition -∂ y ϕ(t, x, ȳ) > 0, otherwise the subsolution property is automatically satisfied. In this case the result follows observing that, by the very definition of the scheme (see Step 2 of the algorithm) and its monotonicity, one can derive

ϕ(t k , x k , y k ) + δ k ≤ T (ϕ)(t k , x k , y k ∨ y j x k ) ≤ T (ϕ)(t k , x k , y k )
so that the subsolution property follows again by the consistency of the scheme. It remains to prove that W satisfies the Dirichlet condition pointwise on Γ 1 . For this purpose it is worth to observe that W ρ,h is Lipschitz continuous in y (see Remark 3), i.e. there exists some constant L > 0 (independent of ρ, h,t, x) such that |W ρ,h (t, x, y) -W ρ,h (t, x, y )| ≤ L|yy | for any t ∈ [0, T ], x ∈ R d , y, y ∈ R. Therefore one has

|W ρ,h (s, ξ , γ) -(-1)| = |W ρ,h (s, ξ , γ) -W ρ,h (s, ξ , 0)| ≤ L|γ| so that on Γ 1 (i.e for ȳ = 0) lim inf [0,T ]×D (s,ξ ,γ)→(t, x, ȳ) ρ,h→0
W ρ,h (s, ξ , γ) = -1.

Numerical tests

In this section we present some numerical tests for probabilistic reachability problems in presence of state constraints. To solve the HJB equation ( 22), we use the fully discrete SL scheme introduced in Section 4 implemented on the ROC-HJ solver available at the link https://uma.ensta-paristech.fr/soft/ROC-HJ/.

The minimum in ( 23) is performed on a subset of control values {u 1 , ..., u N u } that represents a discretization of U with a mesh size ∆ u. In all the simulations the regularization parameter will be chosen to be ε = 1.E -08.

Example 1

We consider the following controlled stochastic system:

dX(s) = -1 -4 4 -1 X(s) + u(s) ds + 0.7 0 0 0.7 dB 1 (s) dB 2 (s) (27)
where u(s) = u 1 (s) u 2 (s) , u i (s) ∈ [-0.1, 0.1], for i = 1, 2 and B 1 , B 2 are two independent Brownian motions.

The linear system [START_REF] Yong | of Applications of Mathematics[END_REF] has been used in [START_REF] Assellaou | Error estimates for second order hamiltonjacobi-bellman equations. approximation of probabilistic reachable sets[END_REF] to validate the HJB approach in the characterization of an approximated probabilistic reachable set without state constraints and in [START_REF] Althoff | Safety assessment for stochastic linear systems using enclosing hulls of probability density functions[END_REF] to illustrate an appoximation of the probability of reaching a target by using enclosing hulls of probability density functions.

We set T = 1.75 and define the target C := (0.5, 1.5) × (-0.5, 0.5) (green square in Figure 2). The constraint is given by the presence of an obstacle, represented in Figure 2 (right) by the red rectangle, i.e. ]). We compute the set Ω ρ t (blue region) for t = 0.75 and ρ = 0.4 in presence (Figure 2, right) or not (Figure 2, left) of the obstacle. To approximate the auxiliary function w ε solution to [START_REF] Margellos | Hamilton-Jacobi formulation for Reach-avoid differential games[END_REF], the numerical simulation is performed on a computational domain [-8, 8] 2 × [-1, 0]. The corresponding values of ϑ ε are then obtained using relation [START_REF] Falcone | Level sets of viscosity solutions: Some applications to fronts and rendez-vous problems[END_REF]. Figure 3 (top) shows the set Ω ρ t for ρ = 0.4 at different time t ∈ {0.25; 0} in presence of the obstacle. Then, in Figure 3 (bottom) we simulate different optimal paths starting from a given point of the backward reachable set using the algorithm described below.

K := R 2 \ ([-6, -2] × [2, 4
Algorithm (trajectory reconstruction) Initialization: Set X 0 = x.

For k = 0 to N -1:

Step 1 Compute optimal control at t = t k :

u k = arg min u∈{u 1 ,...,u Nu } E[W (t k+1 , X u k+1 , -1)]
where for here ξ := (ξ 1 , ξ 2 ) with ξ i (i = 1, 2) random variables following a N(0, 1) distribution.

u i ∈ {u 1 , . . . , u N u } X k+1 := X k + b(t k , X k , u i )h + σ (t k , X k , u i ) √ hξ ,
Step 2 Compute the point of the optimal trajectory:

X k+1 := X k + b(t k , X k , u k )h + σ (t k , X k , u k ) √ hξ
where again ξ i ∼ N(0, 1) for i = 1, 2.

In order to validate our approach, we compare the value of the scheme in a given point with the percentage of trajectories reaching the target without hitting the obstacle. We consider the case t = 0. The results of Monte Carlo simulations are reported in Table 1. One can conlcude that the approximated value of the level set function belongs in each case to the confidence interval.

Example 2.

We now test our method on the same example used in [10, Section 6]. Let us consider the following dynamics: The target set is C = (0, 0.4) × (-0.5, 0.5) (green rectangle in Figure 4) and the state constraint is K = R 2 \ ([-0.4, 0.2] × [-0.1, 0.1]) (i.e. the entire space except the red square obstacle in Figure 4). We fix T = 0.5 and consider the computational domain

[-1, 1] 2 × [-1, 0].
The strong degeneracy of the diffusion term in this example allowed in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF] to obtain the "almost sure" backward reachable set, corresponding here to the case ρ = 1. Figure 4 shows the approximation of Ω ρ t for t = 0 and different levels ρ ∈ [0, 1, 0.9]. The black region corresponds to the exact backward reachable set for ρ = 1. Indeed, due to the simple dynamics considered it is possible for this example to infer the exact set Ω 1 0 , i.e. the set of points from where the target is reached and the constraint satisfied with probability one, see [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF] for a further discussion. One can observe that as ρ approaches the value 1, we recover the results obtained in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF]. A loss of precision appears at corners. This was already noticed in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF] and it is due to the smoothing effects of the diffusion term (see [10, Figure 2, Section 6]) which can be reduced with the refinement of the mesh.

Conclusions

In this paper we have used the HJB theory for characterising the probabilistic backward reachable set for a system of controlled diffusions in presence of state constraints. We have shown that such a set is a level set of the value function associated to a suitable optimal control problem. To deal with the discontinuity of the cost functional associated to this problem, arising from the use of indicator functions for representing probabilities, we have defined a regularised problem. Precise estimates of the error introduced by this regularisation are still object of ongoing research.

Following the approach in [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF][START_REF] Grüne | Zubov's method for controlled diffusions with state constraints[END_REF][START_REF] Kröner | Infinite horizon stochastic optimal control problems with running maximum cost[END_REF], for the regularised problem we have obtained a characterization by a HJB equation with mixed Dirichlet-derivative boundary conditions. We have defined a fully discrete SL approximation scheme and we have proved its convergence to the unique viscosity solution of the equation. Then, we have used such a scheme in order to validate our approach on some numerical tests. We focused on the examples studied in [START_REF] Assellaou | Error estimates for second order hamiltonjacobi-bellman equations. approximation of probabilistic reachable sets[END_REF] and [START_REF] Bokanowski | Dynamic Programming and Error Estimates for Stochastic Control Problems with Maximum Cost[END_REF], adding state constraints to the first one and variable levels of probability to the second one. More complex tests on concrete models are a promising future direction of work.

  [0, T ) × (D ∪ Γ 2 ) follows quite straightforward by the the arguments in [10, Theorem 3.2] and [21, Theorem 4.1]. Uniqueness of the solution relies on comparison results for sub and super solution. The proof can be found in [19, Appendix A]. We point out that the fact of considering Dirichlet conditions in a strong sense is an important requirement for the proof of the comparison principle.

Fig. 2 (

 2 Fig. 2 (Example 1) Backward reachable sets at t = 0.75 for a time horizon T = 1.75 and ρ = 0.4 without (left) and with (right) obstacle. The target set, the obstacle and the backward reachable set Ω 0.4 0.75 are represented respectively by the green square, the red rectangle and the blue region.

  25 and two different starting points x1 := (4.0, 1.0) T and x2 := (3.0, 0.0) T . The approximation of the level-set function obtained by numerically solving the corresponding HJB equation on the grid ∆ x 1 = ∆ x 2 = 0.0125, ∆ y = 0.1, h = 0.025 at points x1 and x2 is respectively -W (t, x1 , -1) 0.459 ± 0.004 and -W (t, x2 , -1) 0.404 ± 0.009.

Fig. 3 (Table 1 (

 31 Fig. 3 (Example 1). Top: backward reachable set (blue region) at times t ∈ {0.25, 0} for a final time horizon T = 1.75 in presence of the obstacle (red rectangle). Bottom: reconstruction of some optimal paths starting from point x = (4, 1) (bottom, left) and x = (3, -4) (bottom, right).

Fig. 4 (

 4 Fig. 4 (Example 2) approximation of Ω ρ t at t = 0 for different levels ρ ∈ [0, 1, 0.9] computed with ∆ x 1 = ∆ x 2 = 0.005, ∆ y = 0.1, h = 0.01 (same mesh parameters used in [10]).

Acknowledgements

The authors are sincerely grateful to Olivier Bokanowski and Hasnaa Zidani for their guidance at the early stage of this paper.


Evelyne Hubert
email: evelyne.hubert@inria.fr

Invariant Algebraic Sets and Symmetrization of Polynomial Systems

Keywords: Rational invariants, Polynomial systems with symmetry, Section in invariant theory

Assuming the variety of a polynomial set is invariant under a group action, we construct a set of invariants that define the same variety. Our construction can be seen as a generalization of the previously known construction for finite groups. The result though has to be understood outside an invariant variety which is independent of the polynomial set considered. We introduce the symmetrizations of a polynomial that are polynomials in a generating set of rational invariants. The generating set of rational invariants and the symmetrizations are constructed w.r.t. a section to the orbits of the group action.

Introduction

Consider the variety F in C n of a finite set of polynomials F in C[z 1 , . . . , z n ]. F can be invariant under the action of a group G without the polynomials in F being themselves invariant. For a given set F of polynomials as above we shall determine a set of invariant functions F such that the zero set of F is equal to the variety of F outside of some proper subvariety W. The elements of F are polynomials in a fixed finite set of generating rational invariants. The restriction to a dense open set is therefore unavoidable for a general statement. Yet this dense open set is independent of F .

When G is a finite group acting regularly, a system of polynomial invariants F that have the same variety as F can be determined explicitely. The construction of F can be found for instance in the proof of [START_REF] Sturmfels | Algorithms in invariant theory[END_REF]Proposition 2.6.4] and this construction also applies for G-invariant semi-algebraic sets [START_REF] Cimprič | Sums of squares and moment problems in equivariant situations[END_REF]. The existence of such a F for a compact group is proved in [START_REF] Bröcker | On symmetric semialgebraic sets and orbit spaces[END_REF]. It was nonetheless an open question in [START_REF] Cimprič | Sums of squares and moment problems in equivariant situations[END_REF] whether there exists a constructive approach. The present article aims to provide such a construction for rational actions of any algebraic group.

A polynomial system that does not exhibit the symmetry of its variety can for instance appear as the result of algebraic computations as these rarely preserve the known symmetry of the problem. Determining an equivalent system in terms of a generating set of invariants allows further qualitative analysis and a simplified resolution. Specific methods address the resolution of a polynomial system given by the components of an equivariant map [START_REF] Gatermann | Computer algebra methods for equivariant dynamical systems[END_REF]. When the group action is given by orthogonal representations one can construct a set of polynomial invariants with the same variety over the reals [START_REF] Gatermann | Semi-invariants, equivariants and algorithms[END_REF][START_REF] Jarić | Zeros of covariant vector fields for the point groups: invariant formulation[END_REF][START_REF] Worfolk | Zeros of equivariant vector fields: algorithms for an invariant approach[END_REF]]. Yet, even in the equivariant case, there is no systematic process to produce a system of invariants with the same set of zeros in general.

The construction of the set F above is based on a concept of symmetrizations of a polynomial. This latter builds on the construction of the field of rational invariants that makes central use of the notion of section to the orbits. The related construction in [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF] was later extended to the construction of the ring of polynomial invariants of some non reductive groups [START_REF] Derksen | Computational invariant theory[END_REF]Section 4.10]. We revisit here this construction with a notion of section less restrictive than the cross section used in [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF]. The geometric interpretation of the constructive definition of symmetrization allows us to use an argument analogous to the finite group case to prove that the zero set of the symmetrizations F of the elements of F is equal to the variety of F . Yet the statement in this case has to be understood outside of a proper invariant subvariety W. The latter depends on the group action and the chosen section but also the term order with which the generating set of invariants is produced.

The symmetrizations we introduce are connected to the concept of algebraic invariantization in [START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]. The latter was introduced as a constructive approach to the local invariantization process associated to the moving frame construction of differential invariants and invariant derivations [START_REF] Fels | Moving coframes. II. Regularization and theoretical foundations[END_REF]. One can also see that the treatment of polynomial systems under a scaling symmetry (in particular multi-homogeneous polynomial systems) in [START_REF] Hubert | Rational invariants of scalings from Hermite normal forms[END_REF] is a special case of symmetrization.

In the next section we define the group actions to be considered as well as the notion of section of degree e to the orbits. We show how to compute a finite set of generating rational invariants. They are the coefficients of a reduced Gröbner basis of the orbit-section ideal. In Section 3 we give a constructive definition of symmetrization w.r.t. a given section to the orbits: to any polynomial f is associated e symmetrizations, where e is the degree of the section to the orbits. These symmetrizations are polynomials in the generating invariants. If F is a set of polynomials whose variety is invariant under the group action then the set F of the symmetrizations of the elements of F have the same zero set. The result has to be understood within a G-invariant open set where the reduced Gröbner basis of the orbit-section ideal specializes well.

Acknowledgments:

The authors is grateful to Guillaume Moroz and Fabrice Rouillier for discussions on the specialisation properties of Gröbner bases.

Construction of rational invariants

We shall first introduce the notions and notations to be used in the article. We then present an algorithm to compute generating sets of invariants endowed with rewrite rules. For that we introduce a definition of section to the orbits of the group action less restritive than the cross section of [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF] and provide a simplified set of proofs. Theorem 2.4 and 2.6 can nonetheless be compared respectively with [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF]Theorem 3.5 and 3.7]. The different notions of sections are discussed in the last subsection.

Rational action of an algebraic group

K is a field of characteristic zero, K is an algebraically closed field extension of K. The groups we consider are affine algebraic groups. They are given by an affine algebraic variety G endowed with a group operation ⋅ ∶ G × G → G and an inverse G → G given by regular maps. To be explicit, we assume that G is embedded in

K l and G ⊂ K[λ 1 , . . . , λ l ] is its defining ideal. The coordinate ring K[G] can be identified with the quotient algebra K[λ 1 , . . . , λ l ] G.
A rational action of G on an affine space Z = K n is defined by a homomorphism ρ from G to the group of birational maps of Z. In practice it is given by a rational map G × Z ⇢ Z, (λ, z) ↦ λ ⋆ z = ρ(λ)(z) defined by quotients of polynomials:

λ ⋆ z = h 1 (λ, z) h 0 (λ, z) , . . . , h n (λ, z) h 0 (λ, z)
where h 0 , h 1 , . . . , h n ∈ K[λ 1 , . . . , λ l , z 1 , . . . , z n ]. When we write ( λ, z) ∈ G × Z we mean that ( λ, z) belongs to the open set of G × Z where λ ⋆ z is well defined.

A rational action of G on Z induces an action on the field of rational functions

K(z) = K(z 1 , . . . , z n ) given by (λ ⋆ f )(z) = f (λ -1 ⋆ z). The set of rational invariants K(z) G is the subfield of K(z) of rational functions f s.t. λ ⋆ f = f , for all λ ∈ G.
As such, K(z) G is finitely generated (cf. for instance [START_REF] Isaacs | Algebra: a graduate course[END_REF]Theorem 24.9]).

The orbit O z of z ∈ Z is the image of the rational map G ⇢ Z, λ ↦ λ ⋆ z. The (Zariski) closure of O z is thus the variety of the elimination ideal (see for instance [START_REF] Becker | Gröbner Bases -A Computational Approach to Commutative Algebra[END_REF]Theorem 7.69], [START_REF] Cox | Using algebraic geometry[END_REF]Chapter 3])

O z = (G + (h 0 (λ, z) z 1 -h 1 (λ, z), . . . , h 0 (λ, z) z n -h n (λ, z)) ∶ h ∞ 0 ∩ K[z, λ].
In the above, we have introduced a new set of variables z = {z 1 , . . . , z n }. A root z ∈ Z of the ideal O z belongs to the closure of the orbit O z of z. We shall pursue with this additional set of variables all along this paper.

We shall work mostly with

K(z)[z] = K(z 1 , . . . , z n )[z 1 , . . . , z n ]. Consider the ideal O of K(z)[z]
defined as the elimination ideal:

O = (G + (h 0 (λ, z) z 1 -h 1 (λ, z), . . . , h 0 (λ, z) z n -h n (λ, z)) ∶ h ∞ 0 ∩ K(z)[z, λ].
For a given term order on z, the reduced Gröbner basis B of O can be computed by elimination [1, Chapter 6.2] [5, Chapter 3]. One proves that the coefficient of B form a generating set of rational invariants [START_REF] Müller-Quade | Calculating generators for invariant fields of linear algebraic groups[END_REF], [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF]Theorem 2.14].

An alternative construction presented in [11, Section 3] produces a more usable output. It makes use of a cross-section to the orbit. We introduce next the less demanding notion of section to the orbits and revise accordingly the construction of a generating set of rational invariants in Section 2.3.

Sections to the orbits

After defining sections to the orbits of a group action, we provide an algebraic characterisation of these. The difference with the cross-sections used in [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF] is discussed in Section 2.4.

Definition 2.1 For a given rational action of G on Z, an irreducible variety P is a section of degree e to the orbits if there exists an open dense subset U of Z such that the orbit of any point z ∈ U intersects P at e points, counted with multiplicities.

Thus a section cannot be contained in a proper G-invariant subvariety of Z. If the generic orbits are of dimension d, a section is of codimension d. One can always choose an affine linear space as a section [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF]Theorem 3.3], or even the level set of some of the coordinate functions [START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]Theorem 1.6]. For generic affine linear space of codimension d the degree of the section it defines is the degree of the orbits. Sections of lower degree can be obtained by taking into consideration the points at infinity or the singular points of the closure of generic orbits, as illustrated in Example 2.3. Section of degree one are of particular interest, as we shall point out at several places.

We shall express the condition for the orbits of an open dense set of points in Z to intersect P in e points. As before, a point z ∈ Z is represented by the variables (z 1 , . . . , z n ). We introduce the variables (z 1 , . . . , z n ) in order to express the condition that a different point z ∈ Z belongs to O z and to P. A section P is determined by a prime ideal P of codimension d that we take in

K[z] = K[z 1 , . . . , z n ].
Proposition 2.2 Assume the generic orbits have dimension d and take P ⊂ K[z 1 , . . . , z n ] as a prime ideal of codimension d. Consider

A = (h 0 (λ, z) z 1 -h 1 (λ, z), . . . , h 0 (λ, z) z n -h n (λ, z)) ⊂ K(z)[z, λ] (1)
Then the variety P of the prime ideal P ⊂ K[z] is a section if the ideal

I P = (G + A + P )∶h ∞ 0 ∩ K(z)[z] (2)
is zero dimensional. The dimension e of the quotient algebra K(z)[z] I P as a K(z)-vector space is the degree of the section.

proof:

Consider A z = (h 0 (λ, z) z 1 -h 1 (λ, z), . . . , h 0 (λ, z) z n -h n (λ, z)) ⊂ K[z, λ]. The ideal I z = (G + A z + P )∶ h ∞ 0 ∩ K[z]
is an ideal whose variety is the Zarisly closure of O z ∩ P. For a given term order on z, the reduced Gröbner basis B for I P can be computed by elimination [1, Chapter 6.2], [START_REF] Cox | Ideals, varieties, and algorithms[END_REF]Chapter 3]. [START_REF] Becker | Gröbner Bases -A Computational Approach to Commutative Algebra[END_REF]Theorem 6.54] or [START_REF] Cox | Ideals, varieties, and algorithms[END_REF]Chapter 5.3 Theorem 6] provide a criterion for I P to be zero dimensional. The dimension e of K(z)[z] I P can be deduced from the leading terms B according to [START_REF] Becker | Gröbner Bases -A Computational Approach to Commutative Algebra[END_REF]Theorem 6.54] or [START_REF] Cox | Ideals, varieties, and algorithms[END_REF]Chapter 5.3 Proposition 4].

One can determine [5, Chapter 6.3 Proposition 1] an hypersurface W such that for any z ∈ Z ∖W the reduced Gröbner basis of I z is obtained by taking the specialization B z of B under z ↦ z. In particular, for z ∈ Z ∖W, B z has the same leading terms as B. Thus I z is zero dimensional if I P is zero dimensional. Furthermore then, the dimension of K[z] I z is e so that the variety of I z consists of e points (counted with multiplicities) [4, Chapter 4.2 Corollary 2.5]. Thus O z ∩ P consists of e points, counted with multiplicity. ◻

The proof above provides an algorithmic characterisation for P to define a section. Let B be the reduced Gröbner basis (according to any term order) of I P . P defines a section of degree e if the normal set of monomials w.r.t. B [1, Chapter 6.3] (i.e. the complementary set to the leading terms of I P [5, Chapter 5.3]) has finite cardinal e. As we shall see in next section, the reduced Gröbner bases of I P also delivers a generating set of rational invariants for the action.

Example 2.3 Scalings in the plane. Consider the action of the multiplicative group K * given by

⋆ ∶ K * × K 2 → K 2 (λ, (x, y)) ↦ (λ a x, λ b y)
where a and b are positive integers that we assume here relatively prime. The ideal of the closure of the orbit of (x, ȳ) ∈ K 2 ∖ {(0, 0)} is then given by

O (x,ȳ) = (x b y a -y a x b ) ⊂ K[x, y].
As a side note we shall observe that the origin is in the closure of all the orbits. There is therefore no non constant polynomial invariant for this action [7, Lemma 2.4.5]. While rational invariants always separate orbits of points outside of a proper closed set (here the variety of the polynomial x y), polynomial invariants provide no separation for the scalings considered here.

A generic affine line in K 2 is a section of degree max(a, b). But P = (x -1) ∈ K[x, y] defines a section of degree a since the ideal of the intersection of the orbit of (x, y) ∈ K 2 ∖ {(0, t) t ∈ K} with the variety P of P is

I P = x -1, y a - y a x b .
Alternatively a section of degree

1 is provided by the Bezout coefficients α, β ∈ Z s.t. α a -β b = 1.
For the purpose of this example we can assume that α, β ∈ N. If we choose P = x αy β then the ideal of the intersection of the orbit of (x, y) ∈ K 2 ∖ {(0, y) y ∈ K} with the variety P of P is

I P = x - y a x b β , y - y a x b α .
This generalizes for scalings in any dimension, i.e. diagonal linear actions of the algebraic torus (K * ) d : we can compute the (binomial) equations of a section of degree one with linear algebra over the integers [START_REF] Hubert | Rational invariants of scalings from Hermite normal forms[END_REF][START_REF] Hubert | Scaling invariants and symmetry reduction of dynamical systems[END_REF].

Generating invariants and rewriting

As can be observed in the examples presented above, the coefficients of the reduced Gröbner basis of the orbit-section ideal I P are rational invariants. The reason is that O z = Oλ ⋆z and therefore O z ∩ P = Oλ ⋆z ∩ P so that a canonical representation of the orbit-section ideal I P must be defined over K(z) G . A reduced Gröbner basis is such a canonical representative. We furthermore show that a reduced Gröbner basis allows to rewrite any invariants in terms of its coefficients.

Theorem 2.4 Consider a term order on the variables z 1 , . . . , z n . The coefficients of the reduced Gröbner basis of the orbit-section ideal

I P in K(z)[z] belong to K(z) G .
proof: For a given term order, the reduced Gröbner basis of an ideal is unique [1, Theorem 5.3], [5, Chapter 2.7 Definition 4 and Theorem 5]. Let B be the reduced Gröbner basis for I P for the given term order on z. As such it consists of monic polynomials in

K(z)[z].
There is a closed proper subset W of Z s.t. for z ∈ Z ∖ W the image B z of B under specialization z ↦ z is the reduced Gröbner basis for the ideal

I z = (G + A z + P ) ∶ h ∞ 0 ∩ K[z] [5, Chapter 6.3 Proposition 1]. As O z ∩ P is zero dimensional, it is the variety of I z .
Since O z = Oλ ⋆z and thus O z ∩ P = Oλ ⋆z ∩ P, for z ∈ Z ∖ W and λ ∈ G, the specializations of B to z and to λ ⋆ z brings the same reduced Gröbner basis. Therefore

B ⊂ K(z) G [z]. ◻
In this construction it is clear that the coefficients of the Gröbner basis of I P separate generic orbits. According to [START_REF] Rosenlicht | Some basic theorems on algebraic groups[END_REF]Theorem 2] or [26, Lemma 2.1], we can deduce that they form a generating set. The alternative proof we give next is constructive. We show how to rewrite any invariant in terms of the coefficients of the reduced Gröbner basis. This is similar to [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF]Theorem 3.7]. The following property of rational invariants is necessary in the proof of Theorem 2.6. Lemma 2.5 If p q is a rational invariant, with p, q ∈ K[z] relatively prime, then the varieties V(p) and V(q) are invariant under the action of G.

proof: By hypothesis p(z) q(λ ⋆ z) = q(z) p(λ ⋆ z) for all (λ, z) ∈ G × Z. Hence p(λ ⋆ z) = 0 for all (λ, z) ∈ G × (V(p) ∖ V(q)). Since p and q are relatively prime, V(p) ∖ V(q) is dense in V(p). Hence p(λ ⋆ z) has to vanish on the whole of G × V(p). ◻ As a side note, we shall remark that when G is connected and acts regularly on Z, one can furthermore conclude that p and q are semi-invariants with the same weight, i.e. p(λ ⋆ z) = χ(λ) p(z) and q(λ ⋆ z) = χ(λ) q(z) where χ ∶ G → K * is a group morphism [26, Theorem 3.1 and 3.3].

Theorem 2.6 Consider a term order on the variables z. Let {r 1 , . . . , r m } ∈ K(z) G be the coefficients of the reduced Gröbner basis B of I P . Then K(z) G = K(r 1 , . . . , r m ) and we can rewrite any rational invariant p q , with p, q ∈ K[z] relatively prime, in terms of those as follows.

Take a new set of indeterminates r 1 , . . . , r m and consider the set

B ⊂ K[r, z] obtained from B by substituting r i by r i . Let a(r, z) = ∑ α∈N n a α (r)z α and b(r, z) = ∑ α∈N n b α (r)z α in K[r,
z] be the normal forms1 of p(z) and q(z) w.r.t. B. There exists α ∈ N m s.t. b α (r) ≠ 0 and for any such α we have p(z) q(z) = aα(r) bα(r) .

proof: We first note that neither q(z), nor p(z), belong to P. Indeed the orbits of the points on P fill an open dense set of Z by hypothesis. Since V(q) invariant (Lemma 2.5), P ⊂ V(q) would imply q = 0.

We now argue that I P ∩ K[z] = P. We obviously have P ⊂ I P ∩ K[z] and therefore the projection of V(I P ∩ K[z, z]) on the z-components is included in P. Conversely, for a generic point z on P, the points

(λ ⋆ z, z), for λ ∈ G lies in V(I P ∩ K[z, z]).
The projection of this latter on the second component is thus dense in P.

E. Hubert

Therefore neither p(z) nor q(z) belong to I P . The normal forms of q(z) and p(z) w.r.t. B are, respectively, b(r, z) and a(r, z) and they are thus both different from zero.

Since p q is invariant, p(z) q(λ ⋆ z) ≡ q(z) p(λ ⋆ z) mod G. Hence p(z)q(z)q(z)p(z) belongs to I P so that its normal form with respect to B must be zero: p(z) b(r, z) = q(z) a(r, z). The conclusion follows. ◻ Theorem 2.6 applies in particular to polynomial invariants. We immediately see that:

Corollary 2.7 Any polynomial invariant can be written as a polynomial in {r 1 , . . . , r m }.

Therefore a case of special interest is when the coefficients of the reduced Gröbner basis have no denominators.

Proposition 2.8 If the coefficients of a reduced Gröbner basis of I P are polynomials, i.e. belong to K[z], then they generate the ring of polynomial invariants

K[z] G .
Example 2.9 Consider the linear action of SO 2 on Z = K 3 acting by rotation on the (x, y)-plane. We have

G = (λ 2 + µ 2 -1) ⊂ K[λ, µ] and A = (x -(λ x -µ y), y -(µ x + λ y), z -z) ⊂ K(x, y, z)[λ, µ, x, y, z].
Choose the section P of degree 2 given by P = ( x ). Then I P = (x, y 2 -(x 2 + y 2 ), zz). Thus r = x 2 + y 2 and z form a generating set for K(x, y, z) G , but also for K[x, y, z] G .

More generally, when the coefficients are the quotients of invariant polynomials, they provide generators for a localization of the invariant ring. The generators of the invariant ring can then be computed following [7, Section 4.1.2].

Section of degree one are of special interest. For these, the reduced Gröbner basis of the orbit-section ideal I P , w.r.t. any term order, is of the form {z 1r 1 (z), . . . , z nr n (z)}, where r i ∈ K(z) G . The rewriting described in Theorem 2.6 is then a simple substitution: if f is a rational invariant then f (z 1 , . . . , z n ) = f (r 1 (z), . . . , r n (z)).

Example 2.10 Following up on Example 2.3, for any invariant f ∈ K(z) G we have f (x, y) = f r β , r α , where r = y a x b .

2.4 Section, quasi-section, cross-section, partial section Different notions of sections to the orbits of a group action appear in invariant theory to show properties of the field of invariants [START_REF] Popov | Sections in invariant theory[END_REF][START_REF] Popov | Invariant theory[END_REF]. The present concept of section of degree e appears as quasi-section in [START_REF] Popov | Invariant theory[END_REF], without specifying the degree. Only section of degree 1 are referred there as section, and sometimes as rational section.

In the course of providing an algebraic formulation of the moving frame construction of differential invariants [START_REF] Fels | Moving coframes. II. Regularization and theoretical foundations[END_REF][START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF], the concept of cross-section of degree e was introduced and applied to compute a generating set of invariants in [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF], providing a more efficient alternative to the ealier constructions (overviewed in [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF]Section 2.3]). As explained next, cross-sections of degree e differ slightly from the present section of degree e

In [11, Definition 3.1] an irreducible ideal P, of complementary dimension to the generic orbits, defines a cross-section if the ideal O + P is zero-dimensional and radical, where

O = (G + A) ∶ h ∞ 0 ∩ K(z)[z]
is the ideal of the generic orbit. The degree of the cross-section is then the dimension of the K(z)-vector space K(z)[z] (O +P ). This is the number of points of intersection of the closure of a generic orbit with the variety P of P. The following example shows how this can differ from the present notion of section.

Example 2.11 Consider the scaling λ ⋆ (x, y) = (λ 2 x, λ 3 y) and P as the variety of P = (yx) ⊂ K[x, y]. On one hand, the orbit-section ideal is

I P = y - x 3 y 2 , x - x 3 y 2
so that P is a section of degree one. On the other hand O = y 2 x 3x 3 y 2 so that

O + P = x -y, y 2 y - x 3 y 2 .
The closure of the generic orbit contains the origin, as does P. P fails to be a cross-section because O + P is not radical.

Both concepts lead to valid constructions for the fields of rational invariants. The present concept of section appears nonetheless as more favorable. For instance, sections of degree one can be obtained for any scaling, i.e. diagonal representation of tori [START_REF] Hubert | Rational invariants of scalings from Hermite normal forms[END_REF][START_REF] Hubert | Scaling invariants and symmetry reduction of dynamical systems[END_REF]. As shown in the previous example, this is no longer true for cross-sections.

Analogues to Theorem 2.4 and 2.6 were proved in [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Müller-Quade | Calculating generators for invariant fields of linear algebraic groups[END_REF] for the orbit ideal O = (G + A) ∶ h ∞ 0 and it is natural to consider intermediate cases where P is of lower dimension than the codimension of the generic orbits. The ideal (G + A + P )∶h ∞ 0 is not zero dimensional then. The proofs of Theorem 2.4 and 2.6 used the following properties:

• P is not contained in any invariant hypersurface

• (G + A + P )∶h ∞ 0 ∩ K[z] = P .
Those properties would be sufficient to define a notion of partial section and this line of ideas was molded in the terminology of extended Derksen ideals in [7, Section 4.10], de-emphasizing the geometrical significance.

Symmetrization

We shall define a concept of symmetrization with respect to a section. The definition is constructive. We then prove that within a G-invariant open set, which depends on the chosen section and a term order, the symmetrization of a polynomial system produces invariants with the same variety. This G-invariant open set is given as the locus of points with good specialisation properties of the reduced Gröbner basis of the orbit-section ideal. We discuss how to determine this locus first.

The singular set W

In Section 2 we have made use of a reduced Gröbner basis B of the orbit-section ideal I P in K(z)[z] to determine a generating set of K(z) G (Theorem 2.6). In the proofs we have used the fact that there exists a variety W such that for z ∈ Z ∖ W the specialisation B z of B is a reduced Gröbner basis of the ideal of O z ∩ P, the intersection of the orbit of z with the section P.

In this section we make more precise how to determine a relevant W. We shall first refine a relatively simple specialisation criterion given as [START_REF] Kapur | An efficient method for computing comprehensive Gröbner bases[END_REF]Theorem 4.3], that can also be found as [

(G + A + P ) ∶ h ∞ 0 where G ⊂ K[λ] is the ideal of the group G, A = ((h 0 (λ, z) z 1 -h 1 (λ, z), . . . , h 0 (λ, z) z n -h n (λ, z)) ⊂ K[z, λ, z]
and P ⊂ K[z] is the ideal of the section.

E. Hubert

B is a Gröbner basis for (G + A + P ) ∶ h ∞ 0 considered in K(z)[z, λ] with the restricted term order on z and λ. Let B be its reduced part and B = B ∩ K(z) [z]. Then B is the reduced Gröbner basis of I P for the term order on z.

Let a ∈ K[z] be the product of the leading coefficients of the elements of B considered as polynomials in z and λ with the restricted term order. Define W to be the maximal G-invariant subset of the variety of a.

For any z ∈ Z ∖ W, the specialisation B z of B at z ↦ z is the Gröbner basis for the ideal of O z ∩ P, the intersection of the orbit of z with the section.

proof: Let U be the variety of a. Then [5, Chapter 5.3 Proposition 1] implies that for z ∈ Z ∖ U, B z is the reduced Gröbner basis of the ideal of O z ∩ P.

If z ∈ U ∖ W there exists λ ∈ G such that λ ⋆ z ∉ U. Hence the specialization Bλ ⋆z is the Gröbner basis of Oλ ⋆z ∩ P = O z ∩ P and we have Bλ ⋆z = B z . ◻ As we shall see in the examples below, the variety W obtained this way is not minimal. To simplify the exposition, we shall speak of the singular set of B to be exact set of points z where the specialisation B z is either ill defined or does not form the reduced Gröbner bases of (G + A z + P ) ∶ h∞ 0 ∩ K[z]. Similarly for B. In [START_REF] Wibmer | Gröbner bases for families of affine or projective schemes[END_REF] it is shown that the set of points z where B specializes well is parametric [19, Definition 4]. In the present case, this means that the singular set of B is an algebraic variety W. The first component of the canonical Gröbner cover, that can be computed thanks to the algorithm presented [START_REF] Montes | Gröbner bases for polynomial systems with parameters[END_REF], provides generators for the ideal W of W. By the argument given in the proof of the proposition above, the singular set for B is G-invariant. It might be a proper subset of the singular set of B, as illustrated in Example 3.4. To obtain the singular set for B, one needs to recombine the components of the canonical Gröbner cover with the subalgorithms LCUnion and Combine presented in [START_REF] Montes | Gröbner bases for polynomial systems with parameters[END_REF].

Example 3.2 Consider the action of G = K

* on the plane given by λ ⋆ (x, y) = λ -1 x, λ y . We have

G = (λ µ -1) in K[λ, µ], A = (x -µ x y -λ y) ⊂ K(x, y)[
x, y, λ, µ] and let us take the section defined by

P = (x -1) ⊂ K[x, y].
The reduced Gröbner basis of (G + A + P ) in K[x, y, x, y, λ, µ] is B = {x -1, yxy, λx, x µ -1} so that a = x. Its variety V(x) is invariant. This corroborates the fact that the orbit of the points (0, ȳ) do not intersect the section defined by P . Hence W = V(x) is the singular set of B = {x -1, y -xy}.

Consider now the action given by λ ⋆ (x, y) = (λ x, λ y). We have

B = {x -1, x y -y, x λ -1, y λ -y, µ -x} so that a = xy. Its variety W = V(x) ∪ V(y) is invariant.
The reduced Gröbner basis of

I P is B = x -1, y -y x .
It is apparent that the specialisation at the points (x, ȳ) = (0, ȳ) is ill defined and indeed the orbits of these points do not intersect the section P. On the other hand the specialisation at (x, 0), with x ≠ 0, does provide the Gröbner basis for the ideal of O (x,0) ∩ P.

When computing the canonical Gröbner cover with the algorithm described in [START_REF] Montes | Gröbner bases for polynomial systems with parameters[END_REF][START_REF] Montes | Software for discussing parametric polynomial systems: the Gröbner cover[END_REF] and implemented in Singular [START_REF] Decker | Singular 4-1-1 -A computer algebra system for polynomial computations[END_REF] one ascertains that the singular set of B is actually V(x).

Example 3.3 Following on Example 2.9. Here B = x, y 2 + 1 -(y 2 + x 2 ), (y 2 + x 2 ) µyy, yµy, y λx µ, x λ + yµy, yλx, λ 2 + µ 2 -1 so that a = xy(x 2 + y 2 ). Yet V(xy) contains only the orbit of the point (0, 0). We can thus consider W = V x 2 + y 2 . The implementation of the Gröbner cover [START_REF] Montes | Gröbner bases for polynomial systems with parameters[END_REF][START_REF] Montes | Software for discussing parametric polynomial systems: the Gröbner cover[END_REF] in Singular [START_REF] Decker | Singular 4-1-1 -A computer algebra system for polynomial computations[END_REF] shows that the singular set of B is precisely

W = V x 2 + y 2 .
Example 3.4 Consider the action of SL 2 on the vector space of 2 × 2 matrices M 2 :

SL 2 × M 2 → M 2 (λ, z) ↦ λ z λ -1
We write so that a = z 12 . The maximal subset of V(z 12 ) that is invariant is W = V(z 12 , z 21 , z 22z 11 ). It corresponds to the matrices that are scalar multiples of the identity. They are invariants so that their orbits have empty intersection with the section.

Computing the canonical Gröbner cover shows that V(z 12 ) is the singular set of B. But the singular set of

B = B ∩ K(z)[z] is the proper invariant subset W of V(z 12
). This is obtained by recombining three components of the canonical Gröbner cover.

At this stage it is not clear if one can bypass the computation of the Gröbner cover to determine the singular set. Yet one might wonder if the geometric interpretations of the singular set for specific term order [START_REF] Lazard | Solving parametric polynomial systems[END_REF][START_REF] Moroz | Complexity of the resolution of parametric systems of polynomial equations and inequations[END_REF][START_REF] Moroz | Properness defects of projection and minimal discriminant variety[END_REF] can bring some light on the matter.

Symmetrizations of a polynomial

In this section we define the symmetrizations of a polynomial. Their definition requires the use of the multiplication map modulo the zero dimensional orbit section ideal. In the next section we shall provide a geometric interpretation for these symmetrizations.

Consider a rational action of G on Z = K n and P a section of degree e defined by a prime ideal P in K[z]. We fix a term order on the variables z = {z 1 , . . . , z n } and consider the reduced Gröbner basis B of the orbit-section ideal

I P in K(z)[z].
The coefficients of B belong to and generate K(z) G (Theorem 2.4 and 2.6). K(z) G is thus the field of definition of the orbit-section ideal I P and we can consider

I G P = I P ∩ K(z) G [z]. It is a zero dimensional ideal in K(z) G [z] and the dimension of K(z) G [z] I G P as a K(z) G -vector space is e. A polynomial f ∈ K(z) G [z] defines an element f in the quotient K(z) G [z] I G P . The multiplication map m f ∶ K(z) G [z] I G P → K(z) G [z] I G P ḡ ↦ f g is a linear mapping [4, Proposition 4.1]. Note that m f g = m f ○m g = m g ○m f . If f is not a zero divisor modulo I P then there exists f 1 ∈ K(z) G [z] s.t. f f 1 ≡ 1 mod I G P .
It follows that det m f ≠ 0 and m f1 = (m f ) -1 . We shall thus define m g f as m g f1 = m g (m f ) -1 when f is not a zero divisor modulo I G P . September 2018 E. Hubert

In the proof of Theorem 2.6 we saw that I P ∩ K[z] = P . Hence no element of K[z] ∖ P are zero divisors modulo I G P . Thus to any element f of the localisation K[z] P of K[z] at the complement of P corresponds a unique element f in K(z) G [z] I G P . The following is thus well defined. Definition 3.5 For f ∈ K[z] P we consider the characteristic polynomial

f P (z, ζ) = ζ e -f (1)
P (z)ζ e-1 + . . . + (-1) j f (j) P (z) ζ e-j + . . . + (-1) e f (e) P (z) of the multiplication map m f by f in K(z) G [z] I G P . The coefficients f (1)
P (z), . . . , f (e)
P (z) ∈ K(z) G are the symmetrizations of f w.r.t. the section P.

Given a reduced Gröbner basis of I P , we can identify a set of monomials that forms a basis of the K(z) Gvector space K(z) G [z] I G P and explicitely write down the matrix of m f in this basis. The symmetrizations of f defined above can thus be computed algorithmically. At no additional cost, the symmetrizations f

(1) P (z), . . . , f (e)
P (z) ∈ K(z) G are written in terms of the generators {r 1 , . . . , r m } of K(z) G that are read from the reduced Gröbner basis of I P according to Theorem 2.6. We formalize these statements. Proposition 3.6 With the hypotheses and notations of Theorem 2.6, consider the finite set A ⊂ N n such that the set of monomials {z α α ∈ A} is the normal set of B.

For f ∈ K[z] P , let {m α,β α, β ∈ A} ⊂ K[r] be such that ∑ α∈A m α,β z α is the normal form of z β f with respect to B. Let f (j) ∈ K[r], 1 ≤ j ≤ e,
be the coefficients of the characteristic polynomial of the matrix (m α,β ) α,β∈A . The symmetrizations of f are

f (j) P (z 1 , . . . , z n ) = f (j) (r 1 (z), . . . , r m (z)) .
The case where P is a section of degree 1 is particularly favorable. Then I P = (z 1r 1 (z), . . . , z nr n (z)) with r 1 , . . . , r n ∈ K(z) G , B = {z 1r 1 , . . . , z nr n } and therefore, for any f ∈ K[z] P , f (1) = f (r). Hence f

(1) P (z 1 , . . . , z n ) = f (r 1 (z), . . . , r n (z)). Example 3.7 Scalings in the plane. We follow up on Example 2.3. We choose P = (x αy β ). It defines a section of degree one and the reduced Gröbner basis of I G P is B = xr β , yr α where r = y a x b . Thus the symmetrization of f is f Example 3.8 Following up on Example 2.9 where we considered a linear action of SO 2 on Z = K 3 and chose the section defined by P = ( x ) so that I P = (x, y 2r, zz) where r = x 2 + y 2 .

Consider the polynomials f 1 = -x x 2 + y 2 -1y z and f 2 = -y x 2 + y 2 -1 + x z. Neither f 1 nor f 2 are invariant.

A basis for K(x, y, z)[x, y, z] I P is given by the set of monomials {1, y}. In this basis, the multiplication matrices of f 1 (x, y, z) and f 2 (x, y, z) are respectively

M 1 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 0 -z r -z 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ and M 2 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 0 r (1 -r) 1 -r 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . Hence f (1) 1 = -Tr(M 1 ) = 0, f (2) 1
= Det(M 1 ) = -z 2 r, and f

(1) 2 = -Tr(M 2 ) = 0, f (2) 2 = Det(M 2 ) = r (1 -r) 2 .
Note that f

P (z) is the trace of m f and the map f ↦ f

(1)

P ∈ K(z) G is a K(z) G -linear map. But in general (λ ⋆ f ) (1)
P ≠ f

Geometric interpretation and connections

We emphasize in this section the geometric interpretation of the symmetrizations introduced in previous section. This shows that symmetrization generalizes a construction that applies to finite groups.

We have fixed a section P and a term order on z so that B is the reduced Gröbner basis of the orbit section ideal I P and W its singular set. For z ∈ Z ∖ W, B z is the Gröbner basis for the ideal of O z ∩ P. Thus (B z ) has e zeros z(1) , . . . , z(e) . They form O z ∩ P, possibly with multiplicities.

P (z) = S j f (z (1) ), . . . , f (z (e) )
where S j is the j-th symmetric polynomial in e variables.

proof: The eigenvalues of m f are the evaluations of f at the roots of (B z ), with matching multiplicities [START_REF] Cox | Using algebraic geometry[END_REF]Theorem 4.5]. Hence

f P (z, ζ) = ∏ e i=1 ζ -f (z (j) ) . ◻ Corollary 3.11 If f ∈ K(z) G then f (j) P = j e f j .
proof: By Proposition 2.5, K(z) G ⊂ K[z] P since P cannot be included in any invariant hypersurface. As an invariant, f is constant on orbits:

f (z) = f (z (1) ) = . . . = f (z (e)
). ◻ Proposition 3.10 shows that symmetrization as introduced above is a generalization of a construction used in the case of finite groups. Indeed, in the case where G is a finite group acting regularly and faithfully, we should consider P = Z as the section and its degree e is the order of group G. where f (j) (z) is simply the i-th symmetric function on {f (λ ⋆ z) λ ∈ G}. The symmetrization f (j) (z), for 1 ≤ j ≤ e, are invariant polynomials. As can be read in [START_REF] Sturmfels | Algorithms in invariant theory[END_REF]Proposition 2.6.4], if the variety V(F ) of a finite set of polynomials F is invariant then

V(F ) = V f (i) f ∈ F, 1 ≤ i ≤ e .
This proves that any variety invariant under the action of a finite group is the variety of a set of invariant polynomials. The notion of symmetrization w.r.t. a section P we introduced allows us to provide an analogous result (Theorem 3.12) for the rational action of an algebraic group of positive dimension.

The characteristic polynomial f P (z, ζ) of the multiplication map m f is a polynomial in the elimination ideal

(I P + (ζ -f (z))) ∩ K(z)[ζ].
Up to the distinction between cross-sections and sections, it corresponds to the invariantization defined in [12, Section 2.6] for algebraic functions. The purpose of this latter was to provide a constructive approach to the local invariantization process that is central in the moving frame construction of differential invariants and invariant derivations in [START_REF] Fels | Moving coframes. II. Regularization and theoretical foundations[END_REF]; [12, Theorem 3.9] makes explicit the connection. The meaning of this theorem in the present context is the following : f P (z, ζ) is the defining polynomial of a smooth algebraic function that is the unique local invariant 2 that agrees with the values of f on the section P in the neighborhood of one of its point. Theorem 3.12 below can be seen as a global analogue of a result known to hold locally. September 2018 E. Hubert

Polynomial systems with symmetry

With the above geometric interpretation of symmetrization we can now prove the main result of the paper : a G-invariant variety F is the zero set of a set of invariant functions, outside of a G-invariant variety W which is independent of F. The result is constructive. For a given set of polynomials F , the set F of the symmetrizations of the elements of F is such that V(F ) ∖ W = V F ∖ W.

The symmetrizations and the singular set W depends on the choice of a section to the orbits and a term order. Indeed the orbits that do not intersect the section are in W. On the other hand, the term order decides of the Gröbner basis B of the orbit section ideal I P . The set W is defined as the maximal set such that for any z ∈ Z ∖ W the specialisation B z of B at z ↦ z is a Gröbner basis for O z ∩ P. In particular W contains the variety of the denominators of the coefficients of B.

It follows from Proposition 3.10 that z ∈ V f

P , . . . , f

P ∖ W ⇔ O z ∩ P ⊂ V(f ) ∖ W. (e)
The proof of the following result is then similar to the proof in the case of finite groups.

Theorem 3.12 Consider a section P of degree e and a term order on z = {z 1 , . . . , z n }. They determine the reduced Gröbner basis B of I P in K(z)[z] and its G-invariant singular set W.

Let F be a set of polynomials in K[z] and assume that its variety

F is G-invariant. Then V f (i) P f ∈ F, 1 ≤ i ≤ e ∖ W = F ∖ W, where f (i)
P (z) ∈ K(z) G , 1 ≤ i ≤ e
, are the symmetrizations of f whose construction is detailed in Proposition 3.6.

Note that the denominators arising in f (j) P are power products of the denominators of the coefficients of B and thus their varieties lies in W. Hence V f (i) P f ∈ F, 1 ≤ i ≤ e is to be understood as the variety of the numerators.

proof: For z ∈ Z ∖ W, we note z(1) , . . . , z(e) the zeros of (B z ). Each z(i) belongs to O z ∩ P. As F is G-invariant we have z ∈ F ∖ W ⇔ z(1) , . . . , z(e) ⊂ F ∖ W.

Since

e j=1 ζ -f (z (j) ) = ζ e -f (1) P (z)ζ e-1 + . . . + (-1) j f (j) P (z) ζ e-j + . . . + (-1) e f (e) P (z) we have f (z (1) ) = 0, . . . , f (z (e) ) = 0 ⇔ f (j) (z) = 0, ∀ 1 ≤ j ≤ e . ◻
Several examples of polynomial systems whose varieties are invariant under a scaling were treated in [START_REF] Hubert | Rational invariants of scalings from Hermite normal forms[END_REF]. These include system of polynomials that are multi-homogeneous according to a set of weights. Indeed [START_REF] Hubert | Rational invariants of scalings from Hermite normal forms[END_REF]Theorem 5.3] can be seen as a special case of the above result.

Example 3.13 Following on Examples 2.9, 3.3 and 3.8, one observes that V(f 1 , f 2 ) is invariant under the action of SO 2 since (f 1 , f 2 ) t is an equivariant map. We determined that outside W = V x 2 + y 2 the reduced Gröbner basis of I P specialises to the reduced Gröbner basis of the intersection of the orbit of that point with the section P. Applying the above construction we obtain

V(f 1 , f 2 ) ∖ W = V f (1) 1 , f (2) 1 , f (1) 2 , f (2) 2
∖ W = V z 2 , (x 2 + y 2 -1) The polynomials are not invariant, except for the first one. Yet, by construction, we know that the variety of F is invariant -F is actually a Gröbner basis for the ideal 8 tr(z 2 ) -9, tr(z 3 ) -1 ). By Proposition 3.12 the variety of F is equal to the variety of In this particular example V(F ) ∩ W = ∅ and V F ∩ V t 2 -4 d = ∅, where V t 2 -4 d ⊃ W. We hence have V F = V(F ). A Gröbner basis for ( F ) considered as an ideal in K[t, d], is given by: ( F ) = 16 -27 t + 8 t 3 , 16 d + 9 -8 t 2 .

F =
Example 3.15 The above example generalizes to SL n acting on the the vector space of n × n matrices M n . The invariants r 1 = -tr(z), . . . , r n = (-1) n det(z) are the coefficients of the characteristic polynomial of z = (z ij ) 1≤i,j≤n . Any polynomial system whose variety is invariant is equivalent to a system of polynomials in r 1 , . . . , r n that is obtained by applying the following substitution:

[z ij ] 1≤i,j≤n → ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 0 0 . . . 0 -r n 1 0 . . . 0 -r n-1 ⋮ ⋱ ⋮ ⋮ ⋱ ⋮ 0 . . . 1 -r 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
.

The right hand side corresponds to the Frobenius normal form of (z ij ) 1≤i,j≤n when the minimal and the characteristic polynomials of z are equal.

As illustrated in the previous example, the symmetrization we introduced is particularly practical when we have a section of degree 1. In this case, the equivalent invariant system is obtained by a simple substitution.

The set F has thus the same number of elements as F and is of similar degree when considered as a system in the generating invariants.

Let us conclude by noting that Theorem 3.12 could be extended to invariant semi-algebraic sets K = {z ∈ R n f 1 (z) ≥ 0, . . . , f m (z) ≥ 0} if we could ensure that the orbits in K ∩ W intersect the section P in e points (counting multiplicities), i.e. the intersection points are not complex. This is the case in the two examples above, or any time we have a section of degree 1 defined over R. The argument of [3, Proposition 3.15] that addresses finite groups would indeed generalize to the present context thanks to the analogy drawn in Section 3.3 between the finite group case and the case of an algebraic group of positive dimension.

P

  (x, y) = f (r β , r α ).

( 1 )P

 1 , contrary to the Reynolds operator.Example 3.9 In the case of Example 3.7, (λ ⋆ f )(1) P (x, y) = f (λ -a r β , λ -b r α ) while f

( 1 )P

 1 (x, y) = f (r β , r α ).

Proposition 3 . 10

 310 Consider f ∈ K[z] P and z ∈ Z ∖W. Let z(1) , . . . , z(e) be the e zeros of B z . For 1 ≤ j ≤ e, f (j)

  For z ∈ Z, z(1) , . . . , z(e) = {λ ⋆ z λ ∈ G}. Thus f P (z, ζ) = ζ ef (1) (z)ζ e-1 + . . . + (-1) j f (j) (z) ζ e-j + . . . + (-1) e f (e) (z) = λ∈G (ζf (λ ⋆ z))

  and consider the section defined P = (z 11 , z 21 -1).It is a section of degree 1 : The Gröbner basis of the orbit-section ideal isB = (z 11 , z 21 -1, z 22t,z 21 + d ) where t = z 11 + z 22 , and d = z 22 z 11z 12 z 21 . One recognizes the invariants to be the trace and the determinant of the matrix z. B∪ z 12 λ 21z 11 λ 22λ 12 , λ 11z 21 λ 22 + z 22 λ 21 , λ 12 2 + t λ 22 λ 12 + d λ 22 2 + z 12 , λ 12 λ 21z 21 λ 22 2 + z 22 λ 21 λ 22 + 1

	λ =	λ 11 λ 12 λ 21 λ 22	, z =	z 11 z 12 z 21 z 22	and z =	z 11 z 12 z 21 z 22
	Here
	B =

2 .

 2 Example 3.14 Following up on Example 3.4. Consider the set F consisting of the three polynomials 16 z 21 z 12 + 8 z 11 2 + 8 z 22 2 -9, 8 z 11 z 12 z 21 -8 + 24 z 22 z 12 z 21 -8 z 22 2 z 11 + 8 z 22 3 + 9 z 11 , 128 z 21 2 z 12 2 -81 + 512 z 22 2 z 21 z 12 -256 z 22 3 z 11 + 128 z 22 4 + 72 z 21 z 12 + 216 z 11 z 22 + 144 z 22 2 + 64 z 11 -192 z 22 .

  8 t 2 -16 d -9, 8 t 3 -8 -24 td, 128 d 2 -81 -512 t 2 d + 128 t 4 -72 d + 144 t 2 -192 t outside of W = V(z 11z 22 , z 12 , z 21 ), the set of matrices that are a scalar multiple of the identity, which are invariant. F is simply obtained from F with the substitution dictated by B, that is z 11 → 0, z 21 → 1, z 22 → t, z 21 → -d.

To appear in the Journal of Symbolic Computation

For the reductions in K[r, z] the term order on z is extended to a block order r ≪ z so that the set of leading terms of B is equal to the set of leading terms of B.

September 2018

See [12, Definition 1.3] for the definitions.


Does a Computer-paced task adjusted to participants capacities reduce strategies and increase prediction of cognitive abilities?

Cognitive abilities: French version of the DAT© (Differential Aptitude Tests) … is to right what Est is to …

Which digit replace the ? in this addition? Counting Task: Report the number of red dots using keyboard.

Sample of the 60 slides 5 red, 10 green 6 red, 12 green 7 red, 14 green 8 red, 16 green 9 red, 18 green

Working Memory span task = memorising items + processing stimuli

St Clair-Thompson (2007): WM span is much more predictive of cognitive abilities with Experimenter-paced than with Participant-paced processing.

(experimenter launch stimuli when participant ended processing)

Lepine, Barrouillet, & Camos (2005): WM span is much more predictive of cognitive abilities with Computer-paced than with Participant-paced processing.

(participant control the presentation rate of stimuli) (stimuli presented at predetermined rate) Conclusion: As Participant-paced leaves additional time to implement strategies, strategies do not contribute to relation between WM and cognitive abilities.

Participants: 38 undergraduate students

Conclusion Results

Material & procedure

For each participant, the average time to count red dots on slides of a kind were calculated.



  Remember consonants (increasing length from 2 to 9 letters)  Count red dots on each slide, 2 conditions (within subject)

Participant

  for each cognitive ability  10 minutes to solve as much as possible

Memory score*

			Participant-paced	Adjusted Computer-paced
	Cognitive abilities mean number of problems solved in 10 min	4.82 (1.07)	4.45 (1.21)
	Verbal	14.39 (4.92)	.43*	.24
	Numerical	8.95 (3.69)	.40*	.29
	Abstract	9.58 (4.25)	.38*	.25


Different accounts of decay and maintenance of verbal information in working memory

Effect of similarity as predicted by phonological loop model and interference model Effect of attentional load as predicted by TBRS 1 2 3 Exp 1 Exp 2

Conclusion

Effect of feature overlapping only with rehearsal instruction and low attentional demanding processing task  feature overwriting involves when both articulatory rehearsal and attentional refreshing are used simultaneously ?

  Similarity effect (p < .05): HS < HO = LO Interaction Task x Similarity (p= .05) In SRT  No similarity effect In CRT  Similarity effect (p< .01) Complex span paradigm • Simple Reaction Task (SRT): Press a key when square appears  Low attentional demanding • Choice Reaction Task (CRT): Press the key that corresponds to the square position (up/down)  High attentional demanding 2 different processing tasks (Within-S):