Alexandre Janon

Maëlle Nodet

Clémentine Prieur

Uncertainties assessment in global sensitivity indices estimation from metamodels

Global sensitivity analysis is often impracticable for complex and resource intensive numerical models, as it requires a large number of runs. The metamodel approach replaces the original model by an approximated code that is much faster to run. This paper deals with the information loss in the estimation of sensitivity indices due to the metamodel approximation. A method for providing a robust error assessment is presented, hence enabling significant time savings without sacrificing on precision and rigor. The methodology is illustrated on two different types of metamodels: one based on reduced basis, the other one on RKHS interpolation.

Introduction

Many mathematical models use a large number of poorly-known parameters as inputs. The impact of parameter uncertainty on the model output is important for the user of these models. This problem can be tackled by considering the uncertain input parameters as random variables, whose probability distribution reflects the practitioner's belief in the precision of the parameter values. Model output, as function of the model inputs, is then a random variable. Its probability distribution, uniquely determined by the model and the distribution of the inputs, can give detailed and valuable information about the behavior of the output when input parameters vary: range of attained values, mean value and dispersion about the mean, most probable values (modes), etc. Sensitivity analysis aims to identify the sensitive parameters, that is, parameters for which a small variation implies a large variation of the model output. In global sensitivity analysis, one makes use of the probability distribution of the outputs to define (amongst other sensitivity measures) sensitivity indices (also known as Sobol indices). The sensitivity index of an output with respect to an input variable is the fraction of output variance which can be "explained" by the variation of the input variable, either alone (one then speaks about main effect), or in conjunction with other input variables (total effect). This way, input variables can be sorted by the order of importance they have on the output. One can also consider the proportion of variance due to the variation of groups of two or more inputs, although main effects and total effects are generally sufficient to produce a satisfying sensitivity analysis; see, e.g., [START_REF] Helton | Survey of samplingbased methods for uncertainty and sensitivity analysis[END_REF][START_REF] Saltelli | Sensitivity analysis[END_REF] for more information about uncertainty and sensitivity analysis. Once these indices have been defined, the question of their effective calculation remains open. For most models, an exact, analytic computation is not attainable (even expressing an output as an analytic function of the inputs is infeasible) and one has to use numerical approximations. A robust, popular way to obtain such approximations is Monte Carlo estimation. This method simulates randomness in inputs by sampling a large number of parameter values (from the selected input distribution). The model output is then computed for each sampled value of the parameters. This way, one obtains a sample of outputs, under the conjugate action of the model and the input distribution. A suitable statistical estimator can then be applied to form a numerical estimate of the sensitivity index based on the sample of outputs. The Monte Carlo approach to Sobol indices computation is described in [START_REF] Sobol | Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates[END_REF], together with improvements in [START_REF] Homma | Importance measures in global sensitivity analysis of nonlinear models[END_REF][START_REF] Saltelli | Making best use of model evaluations to compute sensitivity indices[END_REF]. A major drawback of the Monte Carlo estimation is that a large number of model outputs have to be evaluated for the resulting approximation of the sensitivity index to be accurate enough to be useful. In complex models, in which a simulation for one single value of the parameters may take several minutes, using these methods "as-is" is impracticable. In those cases, one generally makes use of a surrogate model (also known as reduced model, emulator, metamodel or response surface). The surrogate model has to approximate the original model (called the full model) well, while being many times faster to evaluate. The sensitivity index is then calculated via a sample of outputs, each generated by a call to the surrogate model, thus accelerating the overall computation. The aim of this paper is to quantify accuracy loss due to the use of a metamodel combined to a Monte-Carlo method to compute sensitivity indices. The sensitivity index produced by Monte Carlo estimation with a surrogate model is tainted by a twofold error. Firstly, our Monte-Carlo sampling procedure assimilates the whole (generally infinite) population of possible inputs with the finite, randomly chosen, sample; this produces sampling, or Monte-Carlo error. Secondly, using a surrogate model biases the estimation of the Sobol index, as what is actually estimated is sensitivity of surrogate output, and not the full one; we call this bias the metamodel error. A variation on the bootstrap, which addresses sampling error as well as metamodel error, has been proposed in [START_REF] Storlie | Implementation and evaluation of nonparametric regression procedures for sensitivity analysis of computationally demanding models[END_REF]; in this work, the authors propose to use a bootstrap strategy on the metamodel residuals to estimate metamodel error and Monte-Carlo error simultaneously. In [START_REF] Marrel | Calculations of sobol indices for the gaussian process metamodel[END_REF], confidence intervals for the Sobol index are estimated using the conditional distribution of the Kriging predictor given the learning sample. This approach is limited to Kriging metamodels. Finally, the paper by [START_REF] Boyaval | A reduced basis approach for variational problems with stochastic parameters: Application to heat conduction with variable robin coefficient[END_REF] makes use of the reduced-basis output error bound to certify computation of the expectation and the variance of a model output (and not, as in this paper, the Sobol indices) with neglected sampling error. In this paper, we want to make a rigorous sensitivity analysis, so it is important to assess the magnitude of these two combined errors on the estimated sensitivity indices. We will also use such assessment to help with the choice of correct approximation parameters (Monte-Carlo sample size and metamodel fidelity) to achieve a desired precision in estimated indices. We estimate sampling error by using a classical method, which comes at a moderate numerical cost: bootstrap resampling ( [START_REF] Efron | An introduction to the bootstrap[END_REF][START_REF] Archer | Sensitivity measures, ANOVA-like techniques and the use of bootstrap[END_REF]). Based on statistical estimation theory, the bootstrap technique involves the generation of a sample of sensitivity index estimator replications, whose empirical distribution serves as approximation of the true (unknown) estimator distribution, in order to produce asymptotic confidence intervals that give good results in many practical cases. To estimate metamodel error, we will use the surrogate models coming with error bounds, that is, computable (or at least estimable) upper bounds on the error between the original and the surrogate outputs. The reduced basis (RB) method ( [START_REF] Nguyen | Certified real-time solution of parametrized partial differential equations[END_REF][START_REF] Grepl | A posteriori error bounds for reduced-basis approximations of parametrized parabolic partial differential equations[END_REF][START_REF] Veroy | Certified real-time solution of the parametrized steady incompressible Navier-Stokes equations: Rigorous reduced-basis a posteriori error bounds[END_REF][START_REF] Grepl | Efficient reducedbasis treatment of nonaffine and nonlinear partial differential equations[END_REF]) is a method leading to such rigorously certified metamodels; it is applicable when the original model is a discretization of a partial differential equation (PDE) depending on the input parameters. Kriging ( [START_REF] Santner | The Design and Analysis of Computer Experiments[END_REF]) -also known as Gaussian process metamodelling, which is equivalent to RKHS (reproducing kernel Hilbert space) interpolation ( [START_REF] Schaback | Mathematical results concerning kernel techniques[END_REF])also provides error indicators. In contrast to the RB method, Kriging/RKHS interpolation only requires "blackbox" training data, i.e. a (finite) set of input-output pairs from the original model. This makes it more versatile and easier to use, at the expense of rigor in the error bounds and quality in the approximation. Our new approach is based on the separation of the estimation of the metamodel and the sampling error. The advantages brought by our approach are: its rigorousness (the impact of the use of a surrogate model is provably bounded); its efficiency (our bounds are rather sharp, and go to zero when metamodel errors decrease); its moderate computational requirements (time is better spent on making a precise computation than at measuring precision) and its versatility with respect to metamodel choice (the user can choose any metamodel that comes with computable error bound or error indicator). In other words, our method allows us to estimate sensitivity indices by using a metamodel which greatly speeds up computation times, while rigorously keeping track of the precision of the estimation. The model has to exhibit some regularity which can be captured by a metamodel. Moreover, the metamodel error bound should not be too pessimistic. This paper is organized as follows: in the first part, we describe the prerequisites for our approach: we give the definition of the standard Monte Carlo estimator of the sensitivity indices of interest; in the second part, we present our confidence interval estimation technique for the sensitivity index, which accounts for the two sources of error described earlier (sampling and metamodel). In the third part, we present applications of our method for reduced-basis and RKHS/Kriging interpolation metamodels, and compare our method with the method described in [START_REF] Storlie | Implementation and evaluation of nonparametric regression procedures for sensitivity analysis of computationally demanding models[END_REF]. Notations are gathered in B.

Review of sensitivity indices 2.1 Definition

In order to define sensitivity indices, we choose a probability distribution for the input variables, considering each input variable X i (i = 1, . . . , p) as a random variable with known distribution; the model output Y = f (X 1 , . . . , X p ) (assumed to be square-integrable, non a.s. constant and scalar: multiple outputs can be treated separately) is thus for X = (X 1 , . . . , X p ) a σ(X)measurable random variable (assuming that f is a σ(X)-measurable function). We further assume that the X i 's are mutually independent. We also fix throughout all this paper an input variable of interest 1 ≤ i ≤ p. We define the first-order main effect of X i on Y by:

S i = VarE(Y |X i ) VarY ( 1
)
S i is the sensitivity index in which we are interested in this paper but other indices (total effect, high-order effects) exist and our methodology can readily be extended to these indices.

Monte-Carlo estimator

We are interested in the following Monte-Carlo estimator for S i ( [START_REF] Homma | Importance measures in global sensitivity analysis of nonlinear models[END_REF][START_REF] Saltelli | Making best use of model evaluations to compute sensitivity indices[END_REF]): a sample size N ∈ N being given, let X k k=1,...,N and X ′k k=1,...,N be two random i.i.d. samples of size N each, drawn from the distribution of the input vector X.

For k = 1, . . . , N , we note:

y k = f (X k ) (2)
and:

y ′ k = f (X ′k 1 , . . . , X ′k i-1 , X k i , X ′k i+1 , . . . , X ′k p ) (3)
The Monte-Carlo estimator of S i is then given by:

S i = yy ′ -y × y ′ y 2 -y 2 (4)
where, for any vector

v = (v 1 , . . . , v N ), v = 1 N N k=1 v i
It can be shown that S i is a strongly consistent estimator of S i . Remark: our methodology can be extended to higher order Sobol indices by choosing primed output sample {y ′ k } appropriately. More specifically, for a subset of variables I ⊂ {1, . . . , p}, the closed index with respect to I, defined by:

S I = VarE(Y |(X i ) i∈I )
VarY is estimated by using:

y ′ k = f (X ′k I ), where X ′k I,i = X k i if i ∈ I X ′k i else
.

and standard high-order indices can be treated by subtracting the effects of the proper subsets of I.

Quantification of the two types of error in index estimation

We now present our method for estimating the two types of error that occur in Monte-Carlo sensitivity index estimation on a reduced-basis metamodel. In Sections 3.1 and 3.2, we show two approaches for taking metamodel error in account. In Section 3.3, we review the bootstrap, which we will use for the treatment of sampling error. Section 3.4 shows how to combine metamodel error and Monte-Carlo estimation in order to provide the final index interval estimation.

Metamodel error in index estimation

We now denote by f : P ⊆ R p → R the metamodel output approximating f : P → R, and by ε the pointwise error bound that certifies the metamodel approximation, i.e. we have:

f (x) -f (x) ≤ ε(x) ∀x ∈ P
For a pair of samples {X k } k=1,...,N , {X ′k } k=1,...,N of inputs, we can use our metamodel output f and our metamodel error bound ε to compute, for k = 1, . . . , N :

y k = f (X k ), y ′ k = f (X ′k 1 , . . . , X ′k i-1 , X k i , X ′k i+1 , . . . , X ′k p ) (5)
and:

ε k = ε(X k ), ε ′ k = ε(X ′k 1 , . . . , X ′k i-1 , X k i , X ′k i+1 , . . . , X ′k p ) (6)
In this section, we find accurate, explicitly and efficiently computable bounds S m i and S M i , depending only on y k , y ′ k , ε k and ε ′ k so that:

S m i ≤ S i ≤ S M i ( 7
)
In other words, we want lower and upper bounds on the full model based sensitivity index estimator S i computable from surrogate model calls.

We now define, for any z

= (z 1 , . . . , z N , z ′ 1 , . . . , z ′ N ) ∈ R 2N and any a, t, t ′ ∈ R the R function by: R(a; z, t, t ′ ) = N k=1 z ′ k -(a(z k -t) + t ′ ) 2 .
Let y = (y 1 , . . . , y N , y ′ 1 , . . . , y ′ N ). By setting first derivative of R with respect to a to zero, making use of the convexity of R(•; y, y, y ′ ) and using the definition (4) of S i , one easily shows that:

S i = argmin a∈R R(a; y, y, y ′ ). ( 8
)
In other words, S i is the slope of the linear least squares regression of the

{y ′ k } k on the {y k } k .
The key of our approach is to bound R(a; y, y, y ′ ) between two quantities which are computable without knowing y, nor y and y ′ and by using [START_REF] Efron | An introduction to the bootstrap[END_REF] to deduce bounds for any realization (ie., evaluation on a sample) of S i which depend only on metamodel outputs and error bounds, that is

y k , ε k , y ′ k , ε ′ k , k = 1, . . . , N . Recall that: y k = f (X k ), y ′ k = f (X ′k 1 , . . . , X ′k i-1 , X k i , X ′k i+1 , . . . , X ′k p )
and:

ε k = ε(X k ), ε ′ k = ε(X ′k 1 , . . . , X ′k i-1 , X k i , X ′k i+1 , . . . , X ′k p ). Define: R inf (a; y, ε, t, t ′ ) = N k=1 inf z k ∈[ y k -ε k ; y k +ε k ],z ′ k ∈[ y ′ k -ε ′ k ; y ′ k +ε ′ k ] z ′ k -(a(z k -t) + t ′ ) 2 (9) and
:

R sup (a; y, ε, t, t ′ ) = N k=1    sup z k ∈[ y k -ε k ; y k +ε k ],z ′ k ∈[ y ′ k -ε ′ k ; y ′ k +ε ′ k ] z ′ k -(a(z -t) + t ′ ) 2    (10) where y = ( y 1 , . . . , y N , y ′ 1 , . . . , y ′ N ), ε = (ε 1 , . . . , ε N , ε ′ 1 , . . . , ε ′ N ). It is clear that: R inf (a; y, ε, t, t ′ ) ≤ R(a; y, t, t ′ ) ≤ R sup (a; y, ε, t, t ′ ) ∀a, t, t ′ ∈ R (11)
Note that R, R inf and R sup are quadratic polynomials in a. We name α, β, γ, α inf , β inf , γ inf , α sup , β sup and γ sup their respective coefficients. In other words, we have:

R(a; y, t, t ′ ) = αa 2 + βa + γ R inf (a; y, ε, t, t ′ ) = α inf a 2 + β inf a + γ inf (12) R sup (a; y, ε, t, t ′ ) = α sup a 2 + β sup a + γ sup ( 13
)
These coefficients are computable by evaluating R inf (a; y, ε, t, t ′ ) and R sup (a; y, ε, t, t ′ ) for three different values of a and solve for the interpolating quadratic functions. These coefficients depend on t and t ′ , as well on y (for α, β, γ) and y and ε (for the other coefficients). We do not explicitly write this dependence until the last part of our discussion.

Using [START_REF] Helton | Survey of samplingbased methods for uncertainty and sensitivity analysis[END_REF] we see that the quadratic function of a:

(α inf -α)a 2 + (β inf -β)a + γ inf -γ
is negative or zero; hence it takes a non-positive value for a = 0, and has a non-positive discriminant:

γ inf -γ ≤ 0 (14) (β inf -β) 2 ≤ 4(α inf -α)(γ inf -γ) ( 15
)
As (β infβ) 2 ≥ 0, Equations ( 14) and ( 15) above imply that α infα ≤ 0, and that:

β inf -δ inf ≤ β ≤ β inf + δ inf for δ inf = 2 (α inf -α)(γ inf -γ).
We now suppose that α inf > 0. As α inf is computable from y k , y ′ k , ε k and ε ′ k , one can practically check if this condition is met. If it is not the case, our bound can not be used. We expect that if the metamodel error is not too large, we will have α inf ≈ α and, as α > 0, the hypothesis α inf > 0 is realistic. So, under this supplementary assumption, we have:

argmin a R(a; y, t, t ′ ) = - β 2α ≥ - β inf + δ inf 2α inf
Now using the second part of ( 11) and the same reasoning on the nonpositive quadratic function of a: R(a; y, t, t ′ ) -R sup (a; y, ε, t, t ′ ), we find that: α ≤ α sup , and:

β sup -δ sup ≤ β ≤ β sup + δ sup . Hence, argmin a R(a; y, t, t ′ ) ≤ - β sup -δ sup 2α sup
where δ sup = 2 (αα sup )(γγ sup ). This comes without supplementary assumptions, because α sup ≥ α and α > 0, or else R(•; y, t, t ′ ) would have no minimum (even if the case α = 0 can seldom occur due to sampling fluctuations, the hypothesis Y not constant a.s. ensures that increasing N and/or changing the sample will lead to a case where α > 0).

As we clearly have δ inf and δ sup smaller than (or equal to) δ := 2 (α infα sup )(γ infγ sup ), we deduce that:

-

β inf (t, t ′ ) + δ(t, t ′ ) 2α inf (t, t ′ ) ≤ argmin a R(a; y, t, t ′ ) ≤ - β sup (t, t ′ ) -δ(t, t ′ ) 2α sup (t, t ′ )
where we have made explicit the dependencies in t and t ′ .

To finish, it is easy to see that we have:

P := [ y -ε; y + ε] ∋ y ( 16
)
and:

P ′ := [ y ′ -ε ′ ; y ′ + ε ′ ] ∋ y ′ (17)
(where y, y ′ , ε and ε ′ denote, respectively, the empirical means of (

y k ) k , y ′ k k , (ε k ) k and ε ′ k k ) so that: min t∈P,t ′ ∈P ′ - β inf (t, t ′ ) + δ(t, t ′ ) 2α inf (t, t ′ ) ≤ S i = argmin a R(a; y, t, t ′ ) ≤ max t∈P ,t ′ ∈P ′ - β sup (t, t ′ ) -δ(t, t ′ ) 2α sup (t, t ′ )
Hence, ( 7) is verified with:

S m i = min t∈P,t ′ ∈P ′ - β inf (t, t ′ ) + δ(t, t ′ ) 2α inf (t, t ′ ) , S M i = max t∈P,t ′ ∈P ′ - β sup (t, t ′ ) -δ(t, t ′ ) 2α sup (t, t ′ ) (18) It is clear that S m
i and S M i are computable without knowing the y k s and y ′ k s. In practice, we compute approximate values of S m i and S M i by replacing the min and max over P × P ′ by the min and max over a finite sample Ξ ⊂ P × P ′ .

Metamodel error in index estimation: a smoothed alternative

The bounds we presented in the last section are sometimes uninteresting, as, when ε is large enough with respect to f , the bounds S m i and S M i are not tight enough to be useful: it happens for example that [0

; 1] ⊂ [ S m i ; S M i ]
. Such a case is the RKHS interpolation metamodel example we present in Section 4.2. In this section, we present an alternative to the bound described in the previous section. This alternative is interesting when ε is only moderately small with respect to f . We begin by defining ψ i (z) as the Monte-Carlo sensitivity index estimator for variable i using z = (z 1 , . . . , z N , z ′ 1 , . . . , z ′ N ) as function evaluations sample:

ψ i (z) = zz ′ -zz ′ z 2 -z 2 .
It is clear that:

ψ i (y 1 , . . . , y N , y ′ 1 , . . . , y ′ N ) = S i
, where {y k } and {y ′ k } are defined in ( 2) and (3). Also let:

Z = N k=1 [ y k -ε k ; y k + ε k ] × N k=1 y ′ k -ε ′ k ; y ′ k + ε ′ k .
Now, since:

∀k = 1, . . . , N y k ∈ [ y k -ε k ; y k + ε k ] and y ′ k ∈ [ y ′ k -ε ′ k ; y ′ k + ε ′ k ],
we certainly have (y 1 , . . . , y N , y ′ 1 , . . . , y ′ N ) ∈ Z and hence:

min z∈Z ψ i (z) ≤ S i ≤ max z∈Z ψ i (z). ( 19
)
Minimizers and maximizers of optimization problems in [START_REF] Santner | The Design and Analysis of Computer Experiments[END_REF] often display a very irregular (nonsmooth) behavior (as a function of the sampled inputs {x 1 , . . . , x N , x ′ 1 , . . . , x ′ N }), even for a smooth output f . This leads to overly pessimistic bounds in [START_REF] Santner | The Design and Analysis of Computer Experiments[END_REF]. To overcome this difficulty, we propose to ensure smoothness of the solution by introducing a penalty factor λ ≥ 0 and to take:

S m,λ i = ψ i (z m,λ ) S M,λ i = ψ i (z M,λ )
where:

z m,λ = argmin z∈Z ψ i (z) + λΠ(z) z M,λ = argmax z∈Z ψ i (z) -λΠ(z) ( 20
)
for Π(z) a (non-negative) indicator of the smoothness of the function which take z as values when evaluated on the input sample {x 1 , . . . , x N , x ′ 1 , . . . , x ′ N }. For instance, one may take:

Π(z) = 1 2N 2N k=1 z k -z S k 2 (21)
with {z S k } a kernel-smoothed version of {z k }:

z S k = 2N k ′ =1 K x k ′ -x k h z k ′ 2N k ′ =1 K x k ′ -x k h ( 22
)
for K an appropriate kernel (preferably with compact support, for reasons of efficiency of the implementation), h a suitable bandwidth (in the sum we have set x k+N = x ′ k for k = 1, . . . , N ), and • the Euclidean norm on R p . The main difficulty is that these optimization problems are in potentially large dimension 2N . However, the gradient of the objective functions are analytically available -under ( 21) and ( 22) -and can be cheaply evaluated, so we choose to use a L-BFGS quasi-Newton algorithm, as implemented in L-BFGS-B ( [START_REF] Zhu | Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization[END_REF]), to solve problems [START_REF] Schaback | Mathematical results concerning kernel techniques[END_REF]. Concerning the choice of λ and h, we opt for the following: h should be chosen so as to have a reasonable proportion (say, 1 to 5 percent) of "neighbor" points (that is to say, couples of points in {x k } k=1,...,N having a significantly nonzero value on the kernel K). For the choice of λ: we plot, for a chosen h held fixed, the length S M,λ i -S m,λ i as function of λ, and then choose λ to be the abscissa of the bottom-left corner of the "L-shaped" curve obtained.

Sampling error : bootstrap confidence intervals

Sampling error, due to the Monte-Carlo evaluation of the variances in (1), can be quantified through an approximate confidence interval calculated using bootstrap ( [START_REF] Archer | Sensitivity measures, ANOVA-like techniques and the use of bootstrap[END_REF]). We use the bias-corrected (BC) percentile method presented in [START_REF] Efron | Nonparametric standard errors and confidence intervals[END_REF][START_REF] Efron | Bootstrap methods for standard errors, confidence intervals, and other measures of statistical accuracy[END_REF]. The principle of this method can be summed up the following way: let θ(X 1 , . . . , X n ) be an estimator for an unknown parameter θ in a reference population P. We generate a random i.

. , θ[B]} of replications of θ.

We now show how this sample can be used to estimate a confidence interval for θ. We denote by Φ the standard normal cdf:

Φ(z) = 1 √ 2π z -∞ exp - t 2 2 dt
and by Φ -1 its inverse. Using R and the point estimate θ = θ(x 1 , . . . , x n ), a "bias correction constant" z 0 can be estimated:

z 0 = Φ -1 #{ θ[b] ∈ R s.t. θ[b] ≤ θ} B
where #A denotes the number of elements in the set A. Then, for β ∈]0; 1[, we define the "corrected quantile estimate" q(β):

q(β) = Φ(2 z 0 + z β )
where z β satisfies Φ(z β ) = β. The central BC bootstrap confidence interval of level 1-α is then estimated by the interval whose endpoints are the q(α/2) and q(1α/2) quantiles of R.

The BC bootstrap procedure is known to be robust to non-normality of θ.

The key advantage of bootstrapping our sensitivity estimators is that we do not require supplementary model evaluations to estimate a confidence interval; hence the computational overhead for getting a confidence interval (versus pointwise estimation only) remains quite modest.

Combined confidence intervals

From Section 3.1 to 3.3, we have seen how to separately assess sampling error and metamodel error. To take both sources of error into account simultaneously, we propose using bootstrap confidence intervals (see Section Here the bounds S m i and S M i can be computed using either the method described in Section 3.1, or the one described in Section 3.2. The BC bootstrap confidence interval procedure (see Section 3.3) can then be used to produce (1α)-level confidence intervals [ S m i,α/2 ; S m i,1-α/2 ] for S m i , and [ S M i,α/2 ; S M i,1-α/2 ] for S M i . We then take as combined confidence interval of level 1α for S i the range [ S m i,α/2 ; S M i,1-α/2 ]. This interval accounts for sampling and metamodels error simultaneously: let, for b = 1, . . . , B, S i [b] be the b th bootstrap replication, computed using the true outputs (y k ) k∈L b . As, for each b, we have:

S m i [b] ≤ S i [b] ≤ S M i [b],
it follows that

S m i,α/2 ≤ S i,α/2 , and S i,1-α/2 ≤ S M i,1-α/2 ,
where S i,α/2 and S i,1-α/2 are the endpoints of the (1α) BC-confidence interval computed using ( S i [b]) b as replications. It follows that [ S i,α/2 ; S i,1-α/2 ] is contained in [ S m i,α/2 ; S M i,1-α/2 ] and, hence, the level of the latter interval is greater than the level of the former. As the level of the [ S i,α/2 ; S i,1-α/2 ] is (asymptotically) equal to 1α, the asymptotic level of the combined confidence interval [ S m i,α/2 ; S M i,1-α/2 ] should theoretically be, by design, greater than 1α.

Applications

Application to a reduced basis metamodel

The reduced basis method ( [START_REF] Nguyen | Certified real-time solution of parametrized partial differential equations[END_REF][START_REF] Quarteroni | Certified reduced basis approximation for parametrized partial differential equations and applications[END_REF]) can be applied when the output is a functional of the discretized solution of a partial differential equation (PDE).

In particular cases (for instance [START_REF] Nguyen | Certified real-time solution of parametrized partial differential equations[END_REF] for elliptic equations, [START_REF] Janon | Certified reduced-basis solutions of viscous Burgers equations parametrized by initial and boundary values[END_REF] for viscous Burgers equation, [START_REF] Urban | A new error bound for reduced basis approximation of parabolic partial differential equations[END_REF] for parabolic equations), it has been shown that the reduced basis output error bounds are accurate and useful. Due to the intrusive nature of the reduced basis approach and "problem-dependent" considerations made during the construction of the metamodel, one can expect fastly-convergent, tight and fully justified error bounds for the sensitivity indices.

In this section, we test our combined confidence interval procedure described in Sections 3.1 and 3.4, and compare it with Monte-Carlo estimation on the full model (with bias-corrected bootstrap to assess sampling error). Our criteria for comparison are the CPU times needed to compute the intervals and the lengths of these intervals (the smaller the better). Note that the error bounds given by the reduced basis method are sufficiently small so that the "smoothness" bounds described in Section 3.2 give similar results to the method of Section 3.1. In all our tests we take α = .05 and B = 2000 bootstrap replications. We checked that this value of B is large enough by increasing B (ie., setting B = 4000), and notice that our results remain significantly unchanged.

Model set-up

Let u, a function of space x ∈ [0; 1] (note that space variable x is unrelated to input parameter vector x) and time t ∈ [0, T ] (T > 0 is a fixed (i.e., known) parameter) satisfying the viscous Burgers' equation:

∂u ∂t + 1 2 ∂ ∂x (u 2 ) -ν ∂ 2 u ∂x 2 = ψ ( 23
)
where ν ∈ R + * is the viscosity, and ψ ∈ C 0 [0, T ], L 2 (]0, 1[) is the source term. For u to be well-defined, we also prescribe initial value u 0 ∈ H 1 (]0, 1[) (ie. u 0 is in the Sobolev space of square-integrable functions whose first derivative is square-integrable), and continuous boundary values b 0 , b 1 ∈ C 0 ([0, T ]). The initial u 0 and boundary values b 0 and b 1 are parametrized the following way:

b 0 (t) = (u 0m ) 2 + n(b 0 ) l=1 A b 0 l sin(ω b 0 l t) b 1 (t) = u 0 (1) + n(b 1 ) l=1 A b 1 l sin(ω b 1 l t) ψ(t, x) = ψ m + n T (ψ) l=1 n S (ψ) p=1 A ψ lp sin(ω ψT l t) sin(ω ψS p x) u 0 (x) = (u 0m ) 2 + n(u 0 ) l=1 A u 0 l sin(ω u 0 l x)
The values of the angular frequencies ω b 0 l , ω b 1 l , ω ψT l , ω ψS p and ω u 0 l , as well as their cardinalities n(b 0 ), n(b 1 ), n T (ψ), n S (ψ) and n(u 0 ) are fixed (known), while our uncertain parameters, namely: viscosity ν, coefficients ψ m and u 0m , and amplitudes

A b 0 l l=1,...,n(b 0 ) , A b 1 l l=1,...,n(b 1 )
, A ψ lp l=1,...,n T (ψ);p=1,...,n S (ψ) and A u 0 l l=1,...,n(u 0 ) live in some Cartesian product of intervals P defined by:

P = x = ν, A b 0 1 , . . . , A b 0 n(b 0 ) , A b 1 1 , . . . , A b 0 n(b 1 ) , ψ m , A ψ 11 , A ψ 12 , . . . , A ψ 1,n S (ψ) , A ψ 2,1 , . . . , A ψ 2,n S (ψ) , . . . , A ψ n T (ψ),n S (ψ) , u 0m , A u 0 1 , . . . , A u 0 n(u 0 ) (24)
The solution u = u(x) depends on the parameter vector x above.

The "full" model is obtained by discretizing the initial-boundary value problem, using a discrete time grid {t k = k∆t} k=0,...,T /∆t , where ∆t > 0 is the time step, and, space-wise, using P 1 Lagrange finite elements built upon an uniform subdivision of [0; 1]: {x i = i/N }, for i = 0, . . . , N . Our full output is:

f (x) = f (u(x)) = 1 N N i=0 u(t = T, x = x i )
The reduced basis method is then applied to yield a surrogate solution u of ( 23), as well as an error bound ε u on u. The reader can refer to [START_REF] Janon | Certified reduced-basis solutions of viscous Burgers equations parametrized by initial and boundary values[END_REF] for full details on discretization, reduction and derivation of the RB error bound for this model. The main idea of the reduced basis method is to project u onto a well-chosen subspace of X whose dimension n (the reduced basis size) is smaller than the dimension of the finite element space that can be used to solve (23) numerically.

In our numerical experiments, we take N = 60, ∆t = .01, T = .05, n S (ψ) = n T (ψ) = n(b 0 ) = n(b 1 ) = 0, n(u 0 ) = 1, ω u 0 1 = 0.5, A u 0 1 = 5 and ψ m = 1. The two input parameters are independent and uniformly sampled. The table below contains the ranges for them, and also the "true" values of the sensitivity indices, which have been calculated (in more than 14h CPU time) using a Monte-Carlo simulation with large sample size N = 4 × 10 6 (so as to BC bootstrap confidence intervals of length < 10 -2 ) on the full model: For benchmarking purposes, as they were computed using the true model with a large Monte-Carlo sample size, we can take the following values:

S ν = 0.082 and S u 0m = 0.918 [START_REF] Veroy | Certified real-time solution of the parametrized steady incompressible Navier-Stokes equations: Rigorous reduced-basis a posteriori error bounds[END_REF] as "true" sensitivity indices.

Empirical coverage of combined confidence intervals

We test the performance of our combined confidence intervals by assessing their empirical coverage. This empirical coverage is measured by computing, for each input variable, 100 combined confidence intervals (each time with different input sample), and counting the proportion of intervals containing the true values in [START_REF] Veroy | Certified real-time solution of the parametrized steady incompressible Navier-Stokes equations: Rigorous reduced-basis a posteriori error bounds[END_REF]. The reduced basis size is n = 9; Monte-Carlo sample size is N = 300. Results are gathered in the table below:

Convergence benchmark

Figure 1 shows the lower S m and upper S M bounds (defined in Section 3.1) for different reduced basis sizes (hence different metamodel precisions) but fixed sample of size N = 2000, as well as the bootstrap confidence intervals computed using the procedure presented in Section 3.4. This figure exhibits the fast convergence of our bounds to the true value of the sensitivity index as the reduced basis size increases. We also see that the part of the error due to sampling remains constant, as sample size stays the same. We also notice that the true values lie between S m i,.025 and S M i,1-.025 , and not always between S m i and S M i ; this is due to the Monte-Carlo part of the error, which is not taken into account by the [ S m i ; S M i ] bounds.

Choice of n and N

In practice, one wants to estimate sensitivity indices with a given precision (ie. to produce (1-α)-level confidence intervals with prescribed length), and has no a priori indication on how to choose N and n to do so. Moreover, for one given precision, there may be multiple choices of suitable couples (N, n), balancing between sampling and metamodel error. Increasing N and/or n will increase the overall time for computation and improve the precision of the calculation (thanks to reduction in sampling error for increased N , or reduction in metamodel error for increased n).

We wish to choose the best compromise, that is, the one that gives the smallest computation time; for the reduced basis method, this time is roughly proportional to N × n 3 (as a number proportional to N of linear systems of size n have to be solved). On the other hand, the length of the combined confidence interval can be modelled as the sum of two terms:

Z α √ N + C a n ( 26
)
where Z α , C are positive constants and a > 1 is a constant. The first term accounts for sampling error; its form is heuristically deduced from central limit theorem. The second accounts for metamodel error; its exponential decay is backed up by numerical experiments as well as theoretical works (e.g. [START_REF] Buffa | A priori convergence of the greedy algorithm for the parametrized reduced basis[END_REF]). The parameters Z α , C and a can be found by doing "calibration runs" with a fixed small sample size N and different reduced basis sizes n 1 , . . . , n K , and by regressing the obtained confidence interval lengths using [START_REF] Zhu | Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization[END_REF].

Minimizing the computation time under the constraint that error is equal to a given "target precision" leads to a straightforward constrained optimization problem (P ), which can be solved, after estimation of Z α , C and n, to find (after rounding to the closest integer) the optimal n and N for a desired precision.

The results of the optimization procedure, for two different target precisions, can be found in the table below. We also present the mean confidence interval length:

1 p p i=1 S M i,1-α/2 -S m i,α/2 ,
to check that the obtained confidence intervals (CI) have the desired length. 1. Only the choice in the middle column, in italics, is the result of the optimization procedure described in this paragraph. We show that it leads to better (smaller) confidence intervals than the other choices.

Full-scale example

We now present an example with more parameters. We take N = 300, ∆t = .01, T = .05, n(ψ The bound described in Section 3.1 has been tested on this example but did not give interesting results (ie. the produced intervals satisfied [ S m i ; S M i ][0; 1]). The reason is that the RKHS error estimator remains large, even for the larger n values for which the metamodel construction is practicable. We compared these results with the ones obtained with CompModSA, a software package implementing the methodology described in [START_REF] Storlie | Implementation and evaluation of nonparametric regression procedures for sensitivity analysis of computationally demanding models[END_REF]. We used as parameters: surface='mlegp' (Kriging metamodel), n.mc.T=0 (we do not want any total index computation), n.mc.S=1000 (sample size), n.samples=1 (one run), and n.CI=300 (generate confidence intervals using 300 bootstrap replications). We contributed a patch for CompModSA, available at http://ljk.imag.fr/membres/Alexandre.Janon/compmodsa.php, which adds to sensitivity the option CI.S, set to TRUE to compute bootstrap confidence intervals for the main effect index. The results, for a learning sample of size n = 160, are shown in Table 3. This comparison clearly shows that our method is able to account for metamodel error, so as to keep the actual coverage of the produced confidence interval close to the expected one. We have been unable to fully compare our approach with the one of [START_REF] Marrel | Calculations of sobol indices for the gaussian process metamodel[END_REF], as the lengths of the confidence interval obtained with this approach were not available; however we can state that, in this example, our method produces intervals of correct coverages for every variable and every training set size we have tested.

) = 0, n(u 0 ) = 5, n(b 0 ) = n(b 1 ) = 2, ψ m = 1,

Conclusion and perspectives

We presented a methodology to quantify the impact of the sampling error and the metamodel error on the sensitivity indices computation, when the metamodel provides a pointwise error bound (or, at least, an error indicator) on the output of interest. Sampling error is handled by a classic bootstrap procedure, while metamodel error is managed using bounds on the sensitivity index estimator. Quantification of those two types of errors permits a certification on the performed estimation We applied our method on two types of metamodels: intrusive (reduced basis) and non-intrusive (RKHS interpolation). On the applications we see that our approach performs well both for reduced-basis and RKHS interpolation. Our method can also be applied with other metamodels, as soon as an assessment for pointwise metamodel error exists.

A RKHS interpolation and error bound

We now briefly recall the RKHS (reproducing kernel Hilbert space) interpolation method, and refer to [START_REF] Schaback | Mathematical results concerning kernel techniques[END_REF] for the details. RKHS interpolation is known to be (see [START_REF] Scheuerer | Interpolation of spatial data -a stochastic or a deterministic problem ?[END_REF]) equivalent to interpolation by Kriging, also known as Gaussian process metamodelling. Using n evaluations of f , one can build a training sample consisting of n input-output pairs D = {(x 1 , y 1 ), . . . , (x n , y n )}, where {x 1 , . . . , x n } is the experimental design and y i = f (x i ) for i = 1, . . . , n. Let R(•, •) be a positive definite kernel; the RKHS interpolator of D with respect to R is: f (x) = k(x) T Σ -1 S y S where: If f belongs to the RKHS associated with the R kernel, there exist a constant C, depending only on f and R, so that:

Σ S =       R(x 1 , x 1 ) R(x 1 , x 2 ) . . . R(x 1 , x n ) R(x 2 ,
f (x) -f (x) ≤ C σ 2 Z (x) (28)
where: σ 2 Z (x) = R(x, x)k(x) T Σ -1 S k(x) We propose to estimate the constant C, which is, up to a multiplicative constant, the norm of f in the RKHS associated with R, by:

C = max i=1,...,n τ f (x τ i ) -f (x τ i ) σ 2 Z (x τ i )
where {x τ i } i=1,...,n τ is a "test sample" that does not contain any point of the experimental design (so as to ensure that σ 2 Z (x τ i ) = 0 for all i = 1, . . . , n τ ). For a continuous f , one easily sees that C converges, as {x τ i } fills the parameter set P, to the smallest C so that (28) holds.

B Nomenclature

R

set of all real numbers z for any z ∈ R N , z = 1 N N k=1 z k X = (X 1 , . . . , X p ), X k , X k′ (k = 1, . . . , N ) i.i. Bounds for (1α)-level confidence interval for S i Acknowledgements: We wish to thank Jean-Claude Fort for a suggestion which we exploited to perform our computation of the least square metamodel-induced error bound. We also thank Anestis Antoniadis and Ingrid Van Keilegom for advice on bootstrap methodology, and Robert Miller for language remarks. We finally thank anonymous referees for helpful comments about the

  i.d. n-sample {x 1 , . . . , x n } from P, then we repeatedly, for b = 1, . . . , B, randomly draw {x 1 [b], . . . , x n [b]} with replacement from this sample and get a replication of θ by computing θ[b] = θ(x 1 [b], . . . , x n [b]). This way we obtain a set R = { θ[1], . .

  3.3) by calculating B bootstrap replications of S m i and S M i , where, for b = 1, . . . , B each bootstrap pair S m i [b]; S M i [b] is computed using ( y k ) k∈L b , y ′ k k∈L b as surrogate output samples, and associated error bounds ( ε k ) k∈L b , ε ′ k k∈L b , where L b is a list of N integers sampled with replacement from {1, . . . , N }.

x 1 )

 1 R(x 2 , x 2 ) . . . R(x 2 , x n ) . . . . . . . . . . . . R(x n , x 1 ) R(x n , x 2 ) . . . R(x n , x n ) = (R(x 1 , x), . . . , R(x n , x)) T , y S = (y 1 , . . . , y n ) TIn practice, R is assumed to belong to a parametrized family; for instance, R is a gaussian kernel: θ 1 , . . . , θ p are estimated from D by minimizing some contrast function.

Table 1 :

 1 Mean confidence interval lengths for different choices of n and N .

					lower bound S m i upper bound S M i lower bound, 95% CI S m i,.05/2 upper bound, 95% CI S M i,1-.05/2
		0.22
		0.2
		0.18
		0.16
		0.14
	sensi 0	0.1 0.12
		0.08
		0.06
		0.04
		0.02
		0
		7	8	9	10	11	12	13
					reduced basis size
					lower bound S m i upper bound S M i bound, 95% CI S m i,.05/2 upper bound, 95% CI S M i,1-.05/2
		0.98
		0.96
		0.94
		0.92
	sensi 2	0.88 0.9
		0.86
		0.84
		0.82
		0.8
		7	8	9	10	11	12	13
					reduced basis size
	Figure 1: Convergence benchmark for sensitivity indices estimation in the
	Burgers' model, left: variable ν, right: variable u 0m . We plotted, for a fixed sample size N = 2000, estimator bounds S m i and S M i defined in (3.1), and endpoints S m i,.025 and S M i,1-.025 of the 95% confidence interval, for different
	reduced basis sizes.

  To check for the optimality of the choices of n and N , we ran the estimation procedure for different n and N but (approximately) fixed time budget N × n3 . Results are in Table

		Target precision= 0.04	Target precision= 0.02
	N	8600	22000
	n	11	11
	CI for S ν	[0.0691614 ; 0.119096] [ 0.0659997 ; 0.0937285 ]
	CI for S u 0m	[0.890985 ; 0.919504]	[ 0.914266 ; 0.926452 ]
	Mean CI length	0.0389	0.0199

Table 2 :

 2 Obtained confidence intervals for the RKHS interpolation metamodel.

	Variable (true index) Mean 95% Combined conf. int. Mean length Coverage
	X1 (0.3139)	[0.0164222;0.218084]	0.202	0.02
	X2 (0.4424)	[0.0877679;0.351651]	0.264	0.11
	X3 (0)	[0.00750793;0.173349]	0.166	0.82

Table 3 :

 3 Confidence intervals for the RKHS interpolation metamodel obtained with CompModSA.

  S i (i = 1, . . . , p) true Sobol index with respect to X i (defined at (1)) S i Monte-Carlo estimator of S i (defined at (4))

		d. input parameter samples
	f	model output
	f	metamodel output
	ε	metamodel error bound
	N	Monte-Carlo sample size
	y k , y ′ k (k = 1, . . . , N ) y k , y ′ k (k = 1, . . . , N ) ε k , ε ′ k (k = 1, . . . , N )	output samples (defined at (2) and (3)) metamodel output samples (defined at (5)) metamodel error bound samples (defined at (6))
	S m i , S M i S m i,α/2 , S M i,1-α/2	Bounds for S i

ω u 0 1 = .5, ω u 0 2 = 1, ω u 0 3 = 1.5, ω u 0 4 = 2, ω u 0 5 = 2.5, ω b 0 1 = ω b 1 1 = .3 and ω b 0 2 = ω b 1 2 = .6. Input parameters are assumed independent and uniformly distributed in the ranges below:

We used a reduced basis of size n = 13. The combined confidence intervals obtained, for N = 7000, have mean length ≈ 0.08. Their computation required N × (p + 1) = 91000 calls to the metamodel; these calls took 85 s of CPU time. By extrapolating the time necessary to generate the 200 (full) model evaluations for the choice of the reduced basis, we found that creating bootstrap confidence intervals of length 0.08 using the full model would require approximately 514 s. The use of a metamodel hence enabled a 6x speedup.

Application to a RKHS interpolation metamodel

We test our method using a RKHS interpolation metamodel based on the Ishigami function:

The analytical values of sensitivities are known:

S 1 = 0.3139, S 2 = 0.4424, S 3 = 0.

We refer to A for details on the RKHS methodology and on the method of error estimation. The experimental design D, of size denoted by n, have been generated using maximin latin hypercube samples (using maximinLHS of R lhs package ( [START_REF] Carnell | lhs: Latin Hypercube Samples[END_REF]). The R package mlegp ( [START_REF] Dancik | mlegp: Maximum Likelihood Estimates of Gaussian Processes[END_REF]) is used as our RKHS interpolation/Kriging toolbox.

Smoothing parameters are set to: λ = .6, h = .2. We computed, for different learning sample sizes n, the empirical coverages and mean lengths of the combined confidence intervals (with the "smoothed" alternative described in Section 3.2). Monte-Carlo sample size is N = 1000, and B = 300 bootstrap replicates are computed. Finally, as Sobol indices are always bounded by 0 and 1, the reported confidence interval is the intersection of the computed interval with [0; 1] (note that one can instead shift the interval to be a subset of [0; 1] while maintaining its original length as done in [START_REF] Storlie | Implementation and evaluation of nonparametric regression procedures for sensitivity analysis of computationally demanding models[END_REF]). Results are given in Table 2.


Arno Kret

EXISTENCE OF CUSPIDAL REPRESENTATIONS OF p-ADIC REDUCTIVE GROUPS

We prove that any reductive group G over a non-Archimedean local field has a cuspidal complex representation.

Introduction

We prove the following Theorem: Theorem 1.1. Let G be a reductive group over F . Then G(F ) has a cuspidal complex representation. This theorem is "folklore", but we could not find a proof for it in the literature. After some reduction steps the proof consists of finding certain characters in general position of elliptic maximal tori of G. In case the cardinal of the residue field of F is "large with respect to G", then there are quick arguments to show that characters in general position exist; see for example [2, lemma 8.4.2]. It are the small groups over small fields and big Weyl groups that might cause problems, and in this article we show that such problems do not occur.

Acknowledgements: I wish to thank my thesis adviser Laurent Clozel for helping me putting together this argument and correcting my mistakes. I thank Guy Henniart for explaining me how the problem can be reduced to finding characters in general position of certain maximal tori in finite groups of Lie type, and I thank Francois Digne for explaining me how these characters in general position can be found.

Notations: Throughout, F is a non-Archimedean local field with residue field k which is of cardinality q. Let p be the characteristic of k, and fix an algebraic closure k of k.

Reduction to a problem of classical finite groups of Lie type

Let P ⊂ G(F ) be a maximal proper parahoric subgroup with associated reductive quotient M over k. We claim that M (k) has an irreducible cuspidal representation σ. When σ is proved to exist, then we may construct a cuspidal representation of G as follows, see [START_REF] Morris | Tamely ramified supercuspidal representations[END_REF], [START_REF] Morris | P -cuspidal representations of level one[END_REF] and [START_REF] Morris | Tamely ramified intertwining algebras[END_REF]. Inflate σ to obtain a P -representation. We may compactly induce the P -representation σ to a representation of G(F ). This G(F )-representation need not be irreducible, but its irreducible subquotients are all cuspidal. Therefore Theorem 1.1 reduces to the next proposition. Proposition 2.1. Let G be a reductive group over the finite field k. The group G(k) has a cuspidal complex representation.

Proof. We will first reduce to G simple and adjoint. Consider the morphism G(k) → G ad (k). If π is a irreducible representation of G ad (k), then, when restricted to a representation of G(k) it will decompose as a finite direct sum π = i π i of irreducible representations. Recall that π is cuspidal if and only if H 0 (N (k), V ) = 0 for all rational parabolic subgroups P ⊂ G with Levi decomposition P = M N . The map G → G ad is an isomorphism on its image when restricted to N . For any parabolic subgroup P = M N ⊂ G ad the inverse image of P in G is a parabolic subgroup with the same unipotent part. Thus, if π is cuspidal as G ad (k)-representation, then the π i are cuspidal representations of G(k). Therefore, we may assume that G is adjoint. But then G is a product of k-simple adjoint groups. If the theorem is true for all the factors, then the theorem is true for G. So we may assume that G = Res k ′ /k G ′ where G ′ is (absolutely) simple and defined over some finite extension k ′ of k. We have G(k) = G ′ (k ′ ), and under this equality cuspidal representations correspond to cuspidal representations. Therefore, we may assume that G is simple and adjoint.

The simple reductive groups G over k are classified by their root system. We will distinguish cases between the possible root systems. Let us first assume that the root system of G is exceptional, i.e. of the form 3

D 4 , E 6 , 2 E 6 , E 7 , E 8 , F 4 , 2 F 4 , G 2 or 2 G 2 . In Carter's book [2, §13
.9] one finds for each exceptional group the complete list of its unipotent irreducible complex trace characters. He also mentions for each group how many of these characters are cuspidal. As it turns out, in each of the exceptional cases, this number is > 0 and so in particular all the exceptional groups have a cuspidal representation. Some of the classical groups do not have cuspidal unipotent characters. So unfortunately for those groups we cannot find a cuspidal representation in Carter's list.

It remains to verify Proposition 2.1 for the simple adjoint groups G/k which are classical. Thus if G is split, then it is of type A n , B n , C n or D n , and if it is non-split, then it is of type 2 A n or 2 D n . To do this we will use Deligne-Lusztig theory in Section 3 to reduce the problem to finding characters in general position. In section 4 we will then verify that all split groups have such a character. In sections 5 and 6 we will then find characters in general position for the remaining non-split root systems. The proof Proposition 2.1 will then be complete.

Characters in general position

Let G/k be a reductive group with connected center. We will apply results of Deligne-Lusztig [START_REF] Deligne | Duality for representations of a reductive group over a finite field[END_REF]. Pick ℓ a prime number different from p. Suppose that we are given the following data: T ⊂ G a torus and θ : T (k) → Q × ℓ a rational character. Then, to this data Deligne and Lusztig associate a virtual character R θ T of G(k) with Q ℓ -coefficients [3, p. 114]. Let σ(G) be the k-rank of G and let σ(T ) be the k-rank of T . Proposition [START_REF] Deligne | Duality for representations of a reductive group over a finite field[END_REF]Prop. 7.4] states that the character (-1) σ(G)-σ(T ) R θ T comes from an actual irreducible G(k)representation π θ T if the character θ is in general position, ie if the rational Weyl group of T acts freely on it. Theorem [3, thm 8.3] states that if, additionally, T is elliptic, then π θ T is cuspidal. Assume for the moment that we have such a pair (T, θ). Pick an isomorphism ι : Q ℓ ∼ → C; then the G(k)-representation π θ T ⊗ ι C is complex cuspidal and irreducible. Therefore, the proof of Proposition 2.1 is reduced to Proposition 4.2, Proposition 5.1 and Proposition 6.1.

The split classical groups

Before continuing with the proof, we recall some generalities. Let G/k be a reductive group. Let (T 0 , B 0 ) be a pair consisting of a maximal torus and a Borel subgroup which contains T 0 , both defined over k. Let W 0 /k be the Weyl group of T 0 ⊂ G. The Frobenius Frob q = (x → x q ) ∈ Gal(k/k) acts on the root datum of G by a diagram automorphism. By abuse of notation this diagram automorphism is also denoted Frob q .

We can carry out the following construction. Let χ :

T 0,k → G m,k be a character. Restrict to T 0 (k) to get a morphism T 0 (k) ֒→ T 0 (k) → k × .
From this construction we obtain a map

X * (T 0 ) → Hom(T 0 (k), k × )
, and this map fits in the exact sequence [3, §5]). Here Φ is the relative q-Frobenius of T 0,k over k, i.e. given by f ⊗ λ → f q ⊗ λ on the global sections O T 0 (T 0 ) ⊗ k k of T 0,k . Recall that we write Frob q for the Frobenius

(4.1) 0 -→ X * (T 0 ) Φ-1 -→ X * (T 0 ) -→ Hom(T 0 (k), k × ) -→ 0, of Z[W 0 (k)]-modules (see
f ⊗ λ → f ⊗ λ q on O T 0 (T 0 ) ⊗ k k.
Definition 4.1. Two elements w, w ′ in W 0 (k) are Frobenius conjugate, or Frob q -conjugate, if there exists an x ∈ W 0 (k) such that w ′ = xwFrob q (x) -1 .

The G(k)-conjugacy classes of rational maximal tori in G k are parametrized by the Frobenius conjugacy classes of W 0 (k) in the following manner. Let N 0 be the normalizer of T 0 in G. We have a surjection from G(k) to the set of maximal tori in G k by sending g ∈ G(k) to the torus g T 0 := gT 0 g -1 . The torus g T 0 ⊂ G k is rational (i.e. Gal(k/k)-stable) if and only if g -1 Frob q (g) ∈ N 0 (k).

Assume that we have two elements g, g ′ ∈ G(k) such that the tori g T 0 , g ′ T 0 in G k are rational. Then, g -1 Frob q (g) and g ′-1 Frob q (g ′ ) lie in N 0 (k) so we can map them to elements of the Weyl group W 0 (k) via the canonical surjection π :

N 0 (k) → W 0 (k). The torus g T 0 ⊂ G k is equal to the torus g ′ T 0 ⊂ G k if and only if π(g -1 Frob q (g)) ≡ π(g ′-1 Frob q (g ′ )) ∈ W 0 (k)/ Frobenius conjugacy ,
(for the proof of this fact, see [START_REF] Digne | Representations of finite groups of Lie type[END_REF]III.3.23]). This completes the description how Frobenius conjugacy classes in W 0 (k) parametrize G(k)-conjugacy classes of maximal tori in G k .

Notation. We will write T 0 (w) for the torus g T 0 .

Proposition 4.2. Let G/k be a classical simple adjoint group. Then G has an anisotropic maximal torus T ⊂ G together with a character θ : T (k) → C × in general position.

Proof. To prove this proposition we will translate it to an explicit combinatorial problem on Dynkin diagrams. We will then use the classification of such diagrams and calculate to obtain the desired result.

Let (T 0 , B 0 ) be a pair consisting of a split maximal torus and a Borel subgroup which contains T 0 , both defined over k. Let w ∈ W 0 (k) be a Coxeter element and let T = T 0 (w) ⊂ G be the maximal torus corresponding to the Frobenius conjugacy class w ⊂ W 0 (k) generated by w.

Pick

g ∈ G(k) such that g -1 Frob q (g) ∈ N 0 (k) and π(g -1 Frob q (g)) = w ∈ W 0 (k). The conjugation-by-g-map G k → G k induces an isomorphism from T 0,k to g T 0,k = T k , and in turn an isomorphism X * (T ) ∼ → X * (T 0 )
. Under this isomorphism, the Frobenius Frob q on X * (T ) corresponds to the automorphism wFrob q on X * (T 0 ), and similarly Φ on X * (T ) corresponds to wΦ on X * (T 0 ).

To see that the torus T 0 (w) is anisotropic it suffices to prove that X * (T 0 (w)) Frobq = 0. We will verify this in each individual case below.

The rational Weyl group W T (k) of the torus T is equal to the set of those elements w ∈ W T (k) in the absolute Weyl group whose action on the characters X * (T ) is equivariant for the Frobenius Frob q . Therefore, under the bijection W T (k)

∼ → W 0 (k), the image of W T (k) in W 0 (k) is
equal to the set of all t ∈ W 0 (k) such that t(wFrob q ) = (wFrob q )t. Because T 0 is split, the automorphism Frob q acts trivially on X * (T 0 ). Therefore, the image of W T (k) in W 0 (k) is the centralizer of w ∈ W 0 (k). Because w is a Coxeter element this centralizer is equal to the subgroup generated by w ∈ W 0 (k).

Choose an embedding of groups ι : k × ֒→ C × . Then, using ι, we may identify Hom(T (k), k × ) with Hom(T (k), C × ). The set Hom(T (k), C × ) is the set of characters of T (k).

We are interested in the subset of Hom(T (k), C × ) consisting of those characters which are in general position. Under the bijection

X * (T 0 ) (wΦ-1)X * (T 0 ) ∼ → Hom(T (k), C × )
the action of the group W T (k) on the right corresponds to the action of the subgroup w ⊂ W 0 (k) on the set on the left. The problem of finding an elliptic torus together with a character in general position is thus translated into a problem of the root system of (G, B 0 , T 0 ): Pick any Coxeter element w in the Weyl group of the root system, and find an element v in

X * (T 0 ) (wΦ-1)X * (T 0 ) which is such that w r v = v for all r = 1 . . . h, where h = # w is the Coxeter number of G.
Before starting the computations, let us make the following 3 remarks to clarify. First, the relative q-Frobenius Φ acts on X * (T 0 ) by χ → χ q (T 0 is split). And second, because the group G is adjoint, the root lattice of G is equal to the weight lattice X * (T 0 ). Finally, the facts on Dynkin diagrams that we state below come from Bourbaki [1, chap 6, §4 - §13].

• G is split of type B n with n ∈ Z ≥2 . The root system of G may be described as follows. Let V = R n with its canonical basis e 1 , . . . , e n and the standard inner product. Define α 1 = e 1 -e 2 , α 2 = e 2 -e 3 , . . . , α n-1 = e n-1 -e n , α n = e n . The elements α 1 , . . . , α n ∈ Z n are the simple roots, and the root lattice is equal to

Z n ⊂ R n . The element w = w α 1 w α 2 • • • w αn
is a Coxeter element of the Weyl group; it acts on R n by (x 1 , . . . , x n ) → (-x n , x 1 , . . . , x n-1 ). It is clear that there are no elements in the root lattice invariant under the action of wFrob q . This implies that T 0 (w) is anisotropic.

We claim that the element e 1 ∈ Z n reduces to an element of Z n /(wΦ -1)Z n in general position. The order of w is equal to 2n, so #stab w (v) divides 2n. Therefore, it suffices to check that for all r ∈ {1, . . . , n} we have w r (e 1 ) -e 1 / ∈ (wΦ -1)Z n . We distinguish cases. Assume first r = n. Then w r acts on V by v → -v. We have w n (e 1 )-e 1 = (-2, 0, . . . , 0). Assume that we have an x = (x 1 , . . . , x n ) ∈ Z n with (wΦ-1)x = (-2, 0, 0, . . . , 0). Then

(4.2) -qx n -x 1 = -2, qx 1 -x 2 = 0, qx 2 -x 3 = 0, . . . , qx n-1 -x n = 0.
From this we get x n = q n-1 x 1 , and -2 = -q n x 1 -x 1 = -(1 + q n )x 1 which is not possible. So we have dealt with the case r = n. Now assume that r ∈ {1, . . . , n -1}. Then w r (e 1 ) -e 1 = e r+1 -e 1 . Assume that we have an

x = (x 1 , . . . , x n ) ∈ Z n such that (4.3) -qx n -x 1 = -1, qx r -x r+1 = 1, and qx i-1 -x i = 0 (∀i / ∈ {1, r + 1}).
We find

x n = q n-r-1 x r+1 = q n-r-1 (qx r -1) = q n-r x r -q n-r-1 = q n-1 x 1 -q n-r-1 , and x 1 -1 = -qx n = -q(q n-1 x 1 -q n-r-1 ), which implies

x 1 = q n-r + 1 q n + 1 , but |q n-r -1| ∞ < |q n + 1| ∞ ,
so x 1 is not integral: contradiction. This completes the proof that e 1 ∈ X(T ) is a character in general position in case G is of type B n .

• G is split of type C n with n ∈ Z ≥2 . The root system of G may be described as follows.

Let V = R n with its canonical basis e 1 , . . . , e n and the standard inner product. Define α 1 = e 1 -e 2 , α 2 = e 2 -e 3 , . . . , α n-1 = e n-1 -e n , α n = 2e n . The elements α 1 , . . . , α n ∈ Z n are the simple roots, and the root lattice Λ is equal to the set of (x 1 , . . . ,

x n ) ∈ Z n ⊂ R n with n i=1 x i ≡ 0 mod 2. The element w = w α 1 w α 2 • • • w αn is a
Coxeter element of the Weyl group; it acts on R n by (x 1 , . . . , x n ) → (-x n , x 1 , . . . , x n-1 ). It is clear that there are no elements in the root lattice invariant under the action of wFrob q . This implies that T 0 (w) is anisotropic.

We claim that the element 2e 1 ∈ Λ reduces to an element of Λ/(wΦ -1)Λ in general position. It suffices to verify that w r (2e 1 ) -2e 1 / ∈ (wΦ -1)Λ for all r ∈ {1, . . . , n}. Let x = (x 1 , . . . , x n ) ∈ R n be the vector satisfying the equations in Equation 4.3. Then the vector x ′ := 2x satisfies w r (2e 1 ) -2e 1 = (wΦ -1)x ′ . Therefore,

x ′ 1 = 2 • q n-r + 1 q n + 1 .
For q = 2 we have 2|q n-r + 1| ∞ < |q n + 1| ∞ , and for q = 2 the numerator and denominator are coprime. Therefore x 1 is not integral.

• G is split of type A n with n ∈ Z ≥1 . Consider inside R n+1 the hyperplane V with equation n+1 i=1 ξ i = 0. Define α 1 = e 1 -e 2 , α 2 = e 2 -e 3 , . . . , α n = e n -e n+1 (simple roots), Λ = Z n+1 ∩ V (root lattice), and w = w α 1 w α 2 • • • w αn (Coxeter element). The element w acts on V ⊂ R n+1 by rotation of the coordinates: (x 1 , x 2 , . . . , x n , x n+1 ) → (x n+1 , x 1 , x 2 , . . . , x n ). We have (wΦ -1)(x 1 , . . . , x n+1 ) = (qx n+1 -x 1 , qx 1 -x 2 , qx 2 -x 3 , . . . , qx n -x n+1 ). It is clear that there are no elements in the root lattice invariant under the action of wFrob q . This implies that T 0 (w) is anisotropic.

We claim that the element v := e 1 -e n+1 ∈ Λ reduces to an element of Λ/(wΦ -1)Λ which is in general position. The order of w equals n + 1. Let r ∈ {1, . . . , n}. Suppose for a contradiction that w r (v) -v = (e r+1 -e r ) -(e 1 -e n+1 ) ∈ (wΦ -1)Λ. Then we have an element (x 1 , . . . , x n+1 ) ∈ Λ such that

qx n+1 -x 1 = -1, qx r-1 -x r = -1, qx r -x r+1 = 1, qx n -x n+1 = 1, qx i-1 -x i = 0 (∀i / ∈ {r + 1, r, 1, n + 1}).
By substitution we deduce from this q n+1 x n+1 = x n+1 -q n -q n+1-r + q n-r + 1. But, q n+1 -1 > q n + q n-r+1 -q n-r -1, so x n+1 cannot be integral: contradiction.

• G is split of type D n with n ∈ Z ≥4 . Define α 1 = e 1 -e 2 , α 2 = e 2 -e 3 , . . ., α n-1 = e n-1 -e n , α n = e n-1 + e n (simple roots), Λ the set of (x 1 , . . . , x n ) ∈ Z n such that n i=1 x i ≡ 0 mod 2 (root lattice).

Unfortunately the above procedure to produce anisotropic tori and characters in general position does not work for this group G for the following reason. Let w = w α 1 • • • w αn be the Coxeter element of the Weyl group which is the product of the reflections in the simple roots. Then w acts on V by (x 1 , x 2 , . . . , x n ) → (-x n , x 1 , . . . , x n-2 , -x n-1 ). This implies that the vector (2, . . . , 2, -2) ∈ Λ is stable under the action of Frobenius and thus the corresponding torus is not anisotropic.

Let W 0 be the Weyl group of the system D n . We have a split exact sequence

(4.4) 1 -→ (Z × ) n det=1 -→ W 0 -→ S n -→ 1,
where S n acts on Z n via the natural action and an ε = (ε i ) ∈ (Z × ) n det=1 acts on a vector e i ∈ Z n of the standard basis by εe i = ε i e i .

Write n = m + 1. Let w = (123 . . . m) ∈ S n . Write t k ∈ (Z × ) n for the element with -1 on the k-th coordinate, and with 1 on all other coordinates. Define w ′ = t n t m w ∈ W 0 . We consider the maximal torus T in G of type w ′ . The action of Frob q on the character group of this torus is given by

Z n ∋ (x 1 , . . . , x m , x n ) → (x m , x 1 , . . . , -x m-1 , -x n ).
We see that there are no non-zero vectors in Z n which are invariant under this action. Therefore the torus T is anisotropic.

The rational Weyl group of T is the set of s ∈ W 0 which commute with w ′ . Let us compute this group. Write ϕ : W 0 ։ S n the natural surjection (see Equation 4.4). Let s ∈ W T (k), then w = ϕ(w ′ ) = ϕ(sws -1 ). Therefore ϕ(s) commutes with w. This implies that ϕ(s) is a power of w. Write s = εw k for some ν ∈ (Z × ) n det=1 . We have

st n s -1 = t n , st m s -1 = t w k (m)
, and sws -1 εw k ww -k ε = εwε.

Therefore

s(w ′ )s -1 = s(t n t m w)s -1 = t n t w k (m) εwε,
which is equivalent to

(ε w(i) ε i ) = t w k (m) t m .
A priori there are 4 solutions ε ∈ (Z × ) n of this equation. When we add the condition det(ε) = 1, then precisely 2 of those solutions remain.

Let ε ∈ (Z × ) n det=1 be such that (ε w(i) ε i ) = t w(m) t m .
We have an exact sequence

1 -→ {1, ν} -→ W T (k) -→ εw -→ 1,
where ν ∈ (Z × ) n det=1 is given by ν i = -1 for i ≤ m and ν n = (-1) m . We claim that v = 2e m ∈ Λ reduces to an element of Λ/(w ′ Φ -1)Λ in general position. Assume that

(w ′ Φ -1)(x 1 , . . . , x m , x n ) = (qx m -x 1 , qx 1 -x 2 , . . . , -qx m-1 -x m , -qx n -x n ).
We ignore the last coordinate, and only work with the vector (x 1 , . . . , x m ). By substitution we deduce that q m x m = -2 -x m ± 2q m-r . This implies (4.5)

x m = 2 q m-r ± 1 q m + 1 .

For (q, r) = (2, 1) we have |q m + 1| ∞ > 2|q m-r ± 1| ∞ , and for (q, r) = (2, 1) the numerator and denominator have a gcd which divides 3, so then q m + 1 = 3 and we must have n = 1, but we assumed m ≥ 2. Therefore x n is not integral.

The unitary groups

Proposition 5.1. Let n ≥ 3. The simple adjoint group over k with root system 2 A n-1 has an anisotropic maximal torus T together with a character T (k) → C × in general position.

Proof. Let E ⊂ k be the quadratic extension of k, and let σ : E ∼ → E be the unique non-trivial k-automorphism of E. The unitary group U n over k is the group of matrices g ∈ Res E/k GL n,E such that σ(g) t g = 1. The adjoint group U n,ad of U n is the group PSU n and this group has root system 2 A n-1 .

We will distinguish cases between n odd and n even. Assume first that n is odd. Let T 0 be the torus (U 1 ) n embedded diagonally in U n . Then Frob q acts on X * (T 0 ) by x → -x. We have X * (T 0 ) = Z n and under this equality, the Weyl group W T 0 (k) is identified with S n . Let w = (123 . . . n) ∈ S n = W T 0 (k) and let T be the torus T 0 (w). The relative Frobenius Φ acts on X * (T ) = Z n by (5.1) (x 1 , . . . , x n ) → (-x n , -x 1 , . . . , -x n-1 ).

We claim that the torus T is anisotropic over k. To see this, let x = (x 1 , . . . , x n ) ∈ Z n be wFrob q -invariant. Then (x 1 , . . . , x n ) = (-x n , -x 1 , . . . , -x n-1 ), it follows x 1 = (-1) n x 1 , and because n is odd, this implies x 1 = 0. The same argument applies to the other x i , and therefore x = 0. We proved X * (T ) Frobq = 0, and thus T is anisotropic.

The center of U n is equal to U 1 embedded diagonally. Let T ad be the image of the torus T in the adjoint group of U n . Then Λ = X * (T ad ) is the subset of Z n consisting of those vectors x ∈ Z n such that n i=1 x i = 0. The Weyl group is S n and it acts on Λ via the restriction of the natural action S n Z n to Λ. The rational Weyl group W T ad (k) ⊂ S n is the set of elements w commuting with Frob q . The rational Weyl group is equal to w ⊂ S n because all elements of the Weyl group commute with -1.

To find an element in general position we must find a vector v ∈ Λ which is such that w r (v) -v / ∈ (Φ -1)Λ for all r = 1 . . . n -1. We claim that v = e 1 -e n ∈ Λ is such a vector. Assume for a contradiction that (wΦ -1)x = w r v -v for some x ∈ Λ. Then

(-qx n -x 1 , -qx 1 -x 2 , . . . , -qx n-1 -x n ) = (e r+1 -e r ) -(e 1 -e n ).
By substitution we deduce from this (-q) n x n = x n -(-q) n-1 -(-q) n-r + (-q) n-1-r + 1, and thus

x n = - (-q) n-1 + (-q) n-r -(-q) n-1-r -1 (-q) n -1 ∈ Z.
We show that this is not possible. We will distinguish cases. Assume first that the pair (q, r) is such that the inequality |(-q) r + (-q) + 1| < q r+1 -2 holds. We may then estimate

|(-q) n-1 + (-q) n-r -(-q) n-1-r -1| ∞ = |(-q) n-1-r ((-q) r + (-q) -1) -1| ≤ q n-1-r • |(-q) r + (-q) -1| + 1 < q n -2q n-1-r + 1 ≤ q n -1 ≤ |(-q) n -1| ∞ .
This proves that x n cannot be integral.

Let us determine the pairs (q, r) for which the above inequality is not true. We have |(-q) r + (-q) + 1| ≤ q r + q + 1. The inequality q r + q + 1 < q r+1 -2 does not hold for (q, r) ∈ {(2, 1), (2, 2), (3, 1)}. To see that it holds in all other cases, observe first that if the inequality holds for (q, r) then it holds also for (q, r + 1). By direct verification we see that it holds for (2, 3), [START_REF] Deligne | Duality for representations of a reductive group over a finite field[END_REF][START_REF] Carter | Finite groups of Lie type[END_REF], and for (q, 1) in case q > 3.

For (q, r) ∈ {(2, 2), (3, 1)} we have the inequality |(-q) r + (-q) + 1| < q r+1 -2, so the above proof also applies to these cases. In case (q, r) = (2, 1), then we obtain

x 1 = -1 + (-2) n-2
(-2) n -1 , which is not integral. This completes the proof for n odd. Now assume that n is even. Write n = m + 1, so that m is odd. Let T 0 ⊂ U n be the torus (U 1 ) n embedded on the diagonal of U n . Let w = (123 . . . m) ∈ S n = W T 0 (k), and consider the torus T := T 0 (w). We have X * (T ) = Z n on which the Frobenius acts by -w. The rational Weyl group W T (k) ⊂ S n is the set of s ∈ S n which commute with -w. Therefore W T (k) = w , and in particular W T (k) ⊂ S m . Let T ad be the image of the torus T in the adjoint group of U n . The lattice X * (T ad ) = Λ ⊂ Z n is the set of vectors (x 1 , . . . , x n ) with n i=1 x i = 0. The tori T and T ad are anisotropic. Write T = T m × U 1 , where the torus T m is the maximal torus in the group U m that we considered in the odd case. The rational Weyl group W T (k) preserves this decomposition of T . We have the map X * (T m,ad ) → X * (T ad ), (x 1 , . . . , x m ) → (x 1 , . . . , x m , 0). This map is S m -equivariant, and it induces a map

X * (T m,ad ) (wΦ -1)X * (T m,ad ) X * (T ad ) (wΦ -1)X * (T ad ) ,
which is w-equivariant. Therefore characters in general position are send to characters in general position. By the argument above we know that T m has characters in general position, so this completes the proof for n even.

6. The non-split orthogonal groups Proposition 6.1. Let n ∈ Z ≥4 . The simple adjoint group G over k with root system 2 D n-1 has a maximal torus T ⊂ G with a character T (k) → C × in general position.

Proof.

Let J be the 2n × 2n-matrix consisting of the blocks ( 1 1 ) on the diagonal, and all other entries 0. The group O 2n over k is the set of matrices g ∈ GL 2n,k which are such that g t Jg = J. The group SO 2n is the group of matrices g ∈ O 2n such that det(g) = 1. The non-split form SO ′ 2n over k is obtained from SO 2n by twisting the action of Frob q with the matrix s ∈ GL 2n consisting of the blocks ( 11 ) on the diagonal, except for the last block on the diagonal which is ( 11 ). This corresponds to replacing the matrix J with the matrix sJs -1 = sJs in the definition of the orthogonal group.

In characteristic p = 2, the group SO 2n (resp. SO 2n ) is connected and has root system D n-1 (resp. 2 D n-1 ). For p = 2 it is the connected component of identity, SO • 2n (resp. SO ′• 2n ), that has root system D n-1 (resp. 2 D n-1 ).

The torus (SO • 2 ) n on the diagonal in SO • 2n is a maximal torus, and the torus

T 0 = (SO • 2 ) n-1 × U 1 is a maximal torus of SO ′• 2n .
We have X * (T 0 ) = Z n and Frob q acts on X * (T 0 ) by (x 1 , . . . , x n ) → (x 1 , . . . , x n-1 , -x n ). Let W 0 be the absolute Weyl group of T 0 . We have a split exact sequence (6.1)

1 -→ (Z × ) n det=1 -→ W 0 -→ S n -→ 1, where S n acts on Z n by permuting the standard basis vectors, and where an ε = (ε i ) ∈ (Z × ) n det=1 acts on a vector e i ∈ Z n of the standard basis by εe i = ε i e i . Let w ∈ S n ⊂ W 0 be the n-cycle (123 . . . n) and consider the torus T := T 0 (w). Then X * (T ) ∼ → Z n via which the action Frob q X * (T ) corresponds to the action of wFrob q on Z n . We verify that this torus is anisotropic. Let x = (x 1 , . . . , x n ) ∈ X * (T 0 ) wFrobq . Then (x 1 , . . . , x n ) = wFrob q (x 1 , . . . , x n ) = (-x n , x 1 , . . . , x n-1 ), which implies x = 0. Therefore T is anisotropic.

The rational Weyl group W T (k) ⊂ W 0 is the set of s ∈ W 0 which commute with wFrob q . Let us determine this group. Write ϕ for the map W 0 ։ S n (see Equation 6.1), and write t j ∈ (Z × ) n for the element with -1 on the j-th coordinate, and with 1 on all other coordinates. Then Frob q = t n .

If s ∈ W t (k), then s(wt n )s -1 = wt n . We apply ϕ to this equality to obtain w = ϕ(w) = ϕ(sws -1 ), and thus ϕ(s) ∈ S n commutes with w. This implies that ϕ(s) is a power of w. Write s = εw k where ε ∈ (Z × ) n det=1 . We have

st n s -1 = εw k (t n )w -k ε = t k ,
and sws -1 = εw k ww -k ε = εwε.

Therefore,

wt n = s(wt n )s -1 = εwε • t k .
This is equivalent to, εw -1 εw = t k t n .

Write ε = (ε i ) ∈ (Z × ) n det=1 . Then we have, (6.2)

εw -1 εw = (ε i ) • (ε w(i) ) = (ε i ε i+1 ) = t k t n .
We will now distinguish cases between n is odd and n is even. Assume first that n is odd. Return to Equation 6.2, we have (ε i ε i+1 ) = t k t n . After the choice of ε n , the ε i for i < n are uniquely determined by this equation. If ε is one of the solutions, then -ε is the other solution. We have det(-ε) = (-1) n det(ε) = -det(ε). Therefore, precisely one of the two solutions has determinant 1. We conclude that the rational Weyl group W T (k) is equal to εw , where ε ∈ (Z × ) n det=1 is the unique element such that (ε i ε i+1 ) = t 1 t n . Let SO • 2n,ad be the adjoint group of SO • 2n and let T ad be the image of the torus T in SO • 2n,ad . Then X * (T ad ) ⊂ X * (T ) = Z n is the sublattice of elements (x 1 , . . . , x n ) ∈ Z n such that n i=1 x i = 0.

We claim that the element v = 2e n ∈ Λ reduces to an element v ∈ Λ/(wΦ -1)Λ in general position. We have (εw) r 2e n = ±2e n-r , for all r = 1, . . . , n -1. We left the sign unspecified, but we mention that it depends on r.

Suppose that there exists an x = (x 1 , . . . , x n ) ∈ Λ such that (wΦ -1)(x 1 , . . . , x n ) = (-qx n , qx 1 , . . . , qx n-1 ) -(x 1 , . . . , x n ) = 2e n ± 2e r .

This implies -q n x n = -2q n-r ± 2 + x n , and thus

We have already verified in Equation 4.5 that x n cannot be integral. This completes the proof for n odd. Assume now that n is even. We have -1 ∈ (Z × ) n det=1 in case n is even. In Equation 6.2 we found that (ε i ε i+1 ) = t k t n . We obtain from this,

det=1 only if k is even, and if this is the case, then the equation

We show that 2e n ± 2e n-2r / ∈ (wΦ -1)Λ for all r = 1, . . . , n 2 , and all signs, so that the element 2e n ∈ Λ/(wΦ -1)Λ is in general position. Assume for a contradiction that x ∈ Λ is such that (wΦ -1)(x 1 , . . . , x n ) = 2e n ± 2e 2r .

Then we may proceed as in Equation 4.5 to find that x n is not integral.

All possible cases are now verified and the proof of Theorem 1.1 is completed.


Keywords: interoperability, Engineering Bill Of Material (EBOM), Manufacturing Bill Of Material (MBOM), ontology, Description Logics (DL), Semantic Web Rule Language (SWRL) Lifecycle Management

The lack of interoperability between information systems that support design and manufacturing is known as one of the major open issues in the field of Product Lifecycle Management. Especially, the BOM transfer between PDM and ERP suffers from a lack of consistent model that would enable a conservative propagation of updated information from one system to the other. This paper introduces a minimal model, based upon an ontological description, that aims at linking, in a consitent manner, design and manufacturing views. This model can be represented in a graphical way, using a cone topology to extend the semantics of the dependency links, leading to the so-called Cone-BOM model.

The Cone-BOM model for consistent and minimal product structures representation Virginie Fortineau*, Thomas Paviot, Samir Lamouri and Vincent Cheutet

Introduction

Product Lifecycle Management (PLM) is usually presented as a cross-cutting activity that goes from the design to the maintenance and finally to the product recycling stage [1]. Moreover, the strategic purpose of the PLM is to control the complexity of the dynamic system composed of a high number of interacting Copyright c 2011 Inderscience Enterprises Ltd.

subsystems such as suppliers, customers, employees, factories or heterogeneous informations systems involved in product development [START_REF] Paviot | A Methodology for solving interoperability problems in the field of Product Lifecycle Management[END_REF]. The latter plays a crucial role, since IT systems enable sharing/exchanging/distributing the product related information across the whole company. According to the Metclaf's law,"the value of a network increases exponentially with the number of nodes (participants)" [START_REF] Alberts | Power to the edge : command, control in the information Age[END_REF] under the condition that the level of interoperability increases at the same time. Interoperability is defined here as "the ability of two systems (or more) to communicate, cooperate and exchange services and data, thus despite the differences in languages, implementations, executive environments and abstraction models" [START_REF] Wegner | Interoperability[END_REF]. Interoperability then appears as a major issue in a successful PLM deployment strategy. The litterature shows that this issue is still widely open, and that the lack of interoperability must be overcome [START_REF] Noel | The PPO design model with respect to digital enterprise technologies among product life cycle[END_REF].

According to [START_REF] Eif | European interoperability framework -White paper[END_REF], interoperability must be achieved at three different levels: the technical, semantic and organizational levels. The semantic level, which adresses the meaning of the data, is the focus of the present paper: this research deals with the way to preserve the semantic flow from any information loss during data transfer between design and production information systems, such as Product Data Management (PDM) and Enterprise Resource Planning (ERP) systems. Indeed, Ben Kheder et al. [START_REF] Ben Kheder | An analysis of the interaction among design, industrialization and production[END_REF] state that "the main need today [in the production information systems] is the communication of updated data from engineering to production management".

The focus of this study is the EBOM/MBOM consistency issue for the purpose of sharing and exchange. The paper is structured as follows: section 2 introduces a state-of-the-art related to product models and their limitations and shows the contribution of ontologies in a federative approach of interoperability. Section 3 proposes a new minimal product model, based on an ontological description, suitable for the interoperability in the design/manufacturing interface. This model is illustrated on a case study in section 4, whereas section 5 discusses this model. Finally, section 6 concludes this paper and introduces perspectives for future works.

Product modeling at the design/production interface

The semantic interoperability can be achieved from several approaches [START_REF]Systèmes d'automatisation industrielle -concepts et règles pour modèles d'entreprise[END_REF]: integration (all the participants must use a shared data standard), unification (establishment of mapping rules between participants) and federation (dynamic collaboration of different participants). Many recent works have dealt with the unification approach [START_REF] Tursi | Ontological approach for product-centrics information system interoperability in networked manufacturing enterprises[END_REF] [10] [START_REF] Paviot | A generic multiCAD/multiPDM interoperability framework[END_REF] for semantic interoperabilty, known to be more agile and flexible than integration. Authors use either ad hoc data models or standard data models to perform data mappings that support information flow. Product data models used for unification provide a static description of product structures [START_REF] Paviot | Federate design and logistics through Product Lifecycle Support standard. 6th Int. Conf. Product Lifecycle Management[END_REF]. Additionally, the mappings are built manually, leading to static mapping tables, that are not totally compliant with highly agile and flexible solutions. The federative approach, based upon ontologies and reasonning, then seems interesting to overcome this limitation.

According to [START_REF] Gruber | Towards principles for the design of ontologies used for knowledge sharing[END_REF], ontologies are a "formal, explicit specification of a shared conceptualization". As [START_REF] Lee | Design of product ontology architecture for collaborative enterprises[END_REF] explained, "a conceptualization is the extraction of vocabularies from a domain and is an abstract, simplified view of the world that we wish to represent". The Description Logics (DL) are the best suited languages to express an ontology [START_REF] Baader | Description logics as ontology languages for the semantic web[END_REF], and specifically the OWL languages. Between the three variants of OWL (Lite, DL and Full), we chose OWL-DL because it is the best compromise between expressivness and reasoning [START_REF] Baader | The Description Logics Handbook[END_REF].

Recently, several works in the PLM field are using ontologies [START_REF] Matsokis | An ontology-based approach for product lifecycle management[END_REF] [18] [14] [START_REF] Tursi | Ontological approach for product-centrics information system interoperability in networked manufacturing enterprises[END_REF], concerning product modeling, process modeling and service modeling as well. Based on the literature review, following choices were made for the model we aim to build: a simple and dynamic data model, intended to product structures exchange, must be designed using ontologies and rules in order to perform reasoning and infer suitable mappings between information. The next section introduces this model.

A minimal product model based upon ontologies

The proposed conceptualization aims to extract semantics from the local (design and manufacturing in this case) views and to implement them in a higher-level minimal model, based on the use of ontologies. Then, by reasoning on the model, it is possible to extract inferred data and to resite them into the local views. In this way, the mapping between design and manufacturing element are indirectly but completely achieved. The following subsections present classes, properties and restrictions of this ontology.

EBOM/MBOM similarities and differences analysis

The EBOM and MBOM contain the various entities composing the product structure, but also the parent/child relationships between entities [START_REF] Hernandez Mathias | Automatic generation of a bill of materials based on attribute patterns with variant specfications in a customer-oriented environment[END_REF]. Although both BOMs share a common representation (i.e. a tree-like structure), they deal with very different meanings [START_REF] Stonebraker | Restructuring the bill of material for productivity: A strategic evaluation of product configuration[END_REF]: the EBOM defines the virtual product whereas MBOM describes a process view enabling the Material Requirement Planning [START_REF] Orlicky | Net change material requirements planning[END_REF] required for the manufacturing stage. The first step of the modeling process is to figure out similarities (and differences) between EBOM and MBOM:

• they both present a tree structure composed of nodes (items) and parent/child relationships. These relationships hold a large amount of semantics, but mostly in an implicit way [START_REF] Paviot | Semantic tags for generative multiview product beakdown[END_REF],

• the nodes refer to items of different natures. EBOM items may not be present in the MBOM and vice versa. However, they refer to a specific meaning for the designer or manufacturer. As a consequence, all items have the same existing need and will be treated in the same way in the proposed model,

• in both BOM, the parent/child dependency links express a composition link. The parent is indeed not a new or separated element, but the addition (or union) of all its children,

• in both BOM, it is possible to explicitly state a contact link between the children. If the link between two children is not constant over the time, there do exist indeed a contact loop between all the children. That means that between all children of the same entity, it is always possible to find at least one set of these children that are physically in contact. Moreover, each child is part of at least one of these sets. This contact link will be the model for interactions between both BOMs and is represented as a loop in the graphical representation of the proposed model, section 3.6.

The previous points drive the construction of the ontology: following subsections describe classes, properties, restrictions and domain specific rules of this ontology.

Description of the classes and properties

The ontology is described using the Protégé environnement [START_REF]Protégé ontology[END_REF], that uses OWL-DL language; and is represented on figure 1. The first class we create • the SameElement class corresponds to the items that exist in both BOMs,

• the LinkedElement class corresponds to the items that have a link with the other BOM,

• the NoInterfaceElement class corresponds to the items that refer to no item in the other BOM.

These three classes are subclasses of Interface. One of the queries that the ontology will need to answer is to find the isolated items (i.e. the item that belongs to the NoInterface class and have no children). These items have no reason to exist (the only logical NoInterface items are the phantom items or the design assembly items, that do have children) and need a is linked to property.

The ontology needs a class to express the existence (or not) of a parent/child link between items: the Parent class. Finally, as the model aims at providing all the available information hold by the items, the SemanticInformation class is created. This class may have as many subclasses as needed -like the quantity that repesents the cardinality of the BOM-depending on the application (for instance, a material class in the steel industry, a color class in the jewelry industry, etc.). All the instances of these classes are data type.

Description of the properties

The object properties allow us to characterize and relate the different classes to each other. First of all, the has element property is the expression of the parent/child relation that links items in each BOM. has Eelement refers to the EBOM, as has Melement refers to the MBOM. This property is transitive type and has logically the reverse property is element. The property has element refers to the class Item. In order to link the Eitem and Mitem, two properties are created :

• if the two connected items directly correspond to one another, the is the same property is used,

• if the two connected items are not exactly the same concept but influence one another, the is linked to property is instead used.

As it is more restrictive than the is linked to property, the is the same property is a subproperty thereof. The property has interface expresses that a Item belongs to an Interface class. Finally, the data properties link the SemanticInformation to the corresponding Item instance. has info , that is the generic data property used that for, may have diverse subproperties to link the different kinds of information to the instances, such as has quantity that expresses the cardinality of the BOMs.

Restrictions

To ensure the consistency of the ontology, restrictions are added:

• has element links only two individuals of the same Item subclass,

• is linked to and is the same link two individuals of different Item subclasses,

• individuals of the Item class have at most one is the same property and exactly one has interface property.

Domain specific rules

The OWL-DL reasoning capabilities are not sufficient to express all the requirements of product modeling [START_REF] Fiorentini | An analysis of description logic augmented with domain specific rules for the development of product models[END_REF]. Domain specific rules are added using SWRL language (unification of OWL-DL and RuleML). A way to implement SWRL in the Protégé environment is to use SWRLTab, executed by Jess. To complete product modeling, the following domain specific rules are defined:

• an Item that has the is linked to property also belongs to the LinkedTo class, and an Item that has the is the same property also belongs to the SameElement class.

• An Item that belongs neither to the SameElement nor to the LinkedTo classes belongs to the NoInterface class,

• An Item that have the has element property belongs to the Parent class.

Graphical representation of the model

In order to make this model more understandable, a graphical representation is proposed (see figure 2). The discussion related to EBOM and MBOM suggests that the geometrical representation of an item should have two aspects: one loop and a top. The cone topology thus appears as a relevant choice. A cone i is composed of a top T i , a surface S i and a circular base C i . The top and the surface represent the item i, as the loop C i is the locus of junction with the children. The surface enables to store semantic information about the item. We also define a half cone, that presents an interface surface I i (I i is geometrically a infinite plane). I i is the interface surface between the design and the manufacturing corresponding cones. Thanks to the reasoning, it is possible to edit a design/manufacturing view of the assembly. The different steps to create the graphical view of the assembly from the ontology are as follows:

• the retrieving capabilities of DLs are used to find all instances of the SameElement class: a half-cone is created for each resulting instance. Similarly, a full cone is created for each element of the LinkedTo and NoInterface classes,

• individuals of the Eitem class are colored in blue, whereas individuals of the Mitem classe are green,

• for each cone created, we add geometrical constraints as follows: if i is element of j, then T i ∈ C j . For the LinkedTo individuals, we create the tangence point P ∈ C. If i is linked to j, then P i = P j . For the SameElement individuals, if i is the same j, then I i = I j and T i = T j ,

• the SemanticInformation of each Item i are stored on the surface S i .

4 Case study

Description of the case study

The case study is a simplified view of a car assembly. Two possible EBOM and MBOM for this simple case are presented on figure 3. From the designer viewpoint, the car is composed of an engine, a door, and a chassis. The door is itself composed of a glass and a metal sheet. For the manufacturer, the car is produced by assembling the engine and the chassis to create the assembly 1 item. Then the assembly 1 , the glass and the two metal sheets are assembled together. All the items of the EBOM are declared as individuals of the Eitem class. Similarly, all the item of the MBOM are declared as individuals of the Mitem class. Their names spelling start with "E" or "M".

Ontological description and modelisation of the case study

The following mapping are expressed manually in the ontology: One of the reasoning capabilities of ontologies that can be used for this case study is to find the isolated items defined section 3.2. A first retrieving action shows that the Item Emetalsheet, Msheet1, Msheet2, Edoor and Massembly 1 belong to the NoInterface class. But with a second retrieving action, it appears taht among these items, only Emetalsheet, Msheet1 and Msheet2 are not Parent. There is a lack of mapping on these items revealed, and we declare that the Emetalsheet is linked to the Msheet1 and the Msheet2.

A 3d view of this model is presented on figure 4: it should be read as a 3d dimensional extension to the usual 2d view of EBOM and MBOM as they are presented in figure 3. The figure left side does not take account of the is linked to property added between the isolated items, whereas the figure right side does. Regarding the data extraction, in our study case, the information of the EBOM and MBOM are obtained manually and implemented in the ontology, since it is a very simple case. In more complex cases, the information about the items could be extracted automatically from the design and manufacturing information systems. However, we think that the implementation of the different properties can not be done automatically, as they result from a very complex and company specific workflow. The goal is rather to provide tools to make these manual mappings as easy as possible to the user. In this paper, the graphical representation is obtained thanks to the ontology. However the opposite situation is possible, where the engineer is directly working on the graphic interface. By imposing geometrical constraints, he/she automatically instanciate individuals and properties in the ontological model. The mapping between the design and the manufacturing views -that have to be manual-could also be edited in a simple and visual way. This approach could be extended to other stages of the product lifecycle than design and manufacturing, providing thereby a global modelisation designed to ensure interoperability in PLM.

Conclusion

A new product model was introduced in order to make the Engineering and Manufacturing BOMs consistent. This model was so-called minimal since it was designed with the intent to enable the exchange of BOMs between PDM and ERP systems, while retaining a way to update both BOMs in case of an event occuring in both BOMs. This model uses an ontological representation including specific domain rules. A graphical representation of this model is presented, which is a 3d view of the items and their links, that contains all the information needed. Moreover, this model enables to express local and specific user views, as it contains the design, manufacturing and interface information. Further work will deal with the way to include a temporal (i.e. a process based) description.

Figure 1

 1 Figure 1 Description of the classes and properties of the ontology

Figure 2 A

 2 Figure 2 A graphical 3d view of the model

Figure 3

 3 Figure 3 BOM of the case study

Figure 4

 4 Figure 4 Graphical representation of the use case

•

  Ecar hasEelement Echassis, Eengine and Edoor, Mcar hasMelement Massembly 1 , Mglass, Msheet2 and Msheet1, Edoor hasEelement Eglass and Emetalsheet, Massembly 1 hasMelement Mengine and Mchassis, • Ecar is the same Mcar, Eglass is the same Mglass, Echassis is the same Mchassis, Eengine is the same Mengine.