Rémy Chevrier
email: remy.chevrier@inrets.fr

Grégory Marlière
email: gregory.marliere@inrets.fr

Bogdan Vulturescu
email: bogdan.vulturescu@inrets.fr

Joaquín Rodriguez
email: joaquin.rodriguez@inrets.fr

Multi-objective Evolutionary Algorithm for Speed Tuning Optimization with Energy Saving in Railway: Application and Case Study

Keywords: Multi-objective, Evolutionary algorithm, Energy saving, Railway management, Optimization

In this paper an approach is proposed for optimization of speed profiles in railway integrating energy saving. This approach deals with a multi-objective problem involving three criteria: reduction of the travel duration, reduction of the delays and minimization of the energy consumption. Based on a state of the art evolutionary algorithm, the proposed approach searches for diversified solutions in a continuous search space. These solutions are evaluated and compared according to the Pareto approach in such a way that the proposed solutions are different and incomparable, in order to help the decision makers. After having reminded railway dynamics elements, the approach is detailed as well as the evolutionary algorithm and its problem-related components. Two case studies (the Gonesse junction and the line Saint-Étienne -Rive de Giers in France) and results are then provided and analyzed.

Introduction

For recent years, the concern due to pollution and global warming led to develop more ecoaware transportation systems. Energy spent in the railway management is used to move the trains and if speed tuning is well suited, the energy consumption will be lower than in other cases. Indeed, since the acceleration phases consume a huge quantity of energy, it is necessary to tune the speeds according to the distances, the slopes and the timetable in order to avoid unnecessary sequence of brake/acceleration phases. Moreover, given that the trains have a big inertia, it is judicious to use this physical property by stopping the engine and letting the train advance just thanks to the initial force [START_REF] Lancien | Calculs de marches de train économisant l'énergie de traction -le programme MARECO[END_REF][START_REF]Handbook of Railway Vehicle Dynamics[END_REF].

The railway management involves multiple objectives which are often antagonist such as the travel duration and the energy consumption. Although the travel duration had often preference of the decision makers, for recent years the criterion of energy consumption is considered from an equivalent point of view. Indeed, global energy saving has become the new challenge of the transportation systems including railway.

Works have been led for analytically computing speed tuning (ST) solutions according to several levels of delay tolerance [START_REF] Albrecht | Computers in Railways VIII, chapter A new integrated approach to dynamic schedule synchronization and energy saving train control[END_REF][START_REF] Liu | Energy-efficient train control[END_REF][START_REF] Albrecht | Railway Timetable & Traffic -Analysis, Modelling, Simulation, chapter Energy-Efficient Operation Train Operation[END_REF]. But to our knowledge, there are few multiobjective approaches yet. These are based on Differential Evolution [START_REF] Storn | Differential evolution -a simple and efficient heuristic for global optimization over continuous spaces[END_REF] for mass transit system [START_REF] Chang | Pareto-optimal set based multiobjective tuning of fuzzy automatic train operation for mass transit system[END_REF] or evolutionary algorithms hybridized or not [START_REF] Fleming | Evolutionary algorithms in control systems engineering: A survey[END_REF]. Nevertheless, to our knowledge few approaches propose to optimize the energy consumption which becomes the new challenge of the decade.

Thus, in this paper we deal with a multi-objective optimization of ST with energy saving. These concurrently optimized criteria are: the minimization of the travel duration; the minimization of the energy consumption and the punctuality (minimization of the delays, which is quite different to reducing the travel duration). According to the timetable, we can work out the delays occurring at stations and use them in a multi-criteria search. Whatever the criteria under consideration, the main goal consists in designing ST solutions diversified enough to help decision makers to choose the solution the most adapted to their needs. In order to solve the problem, we propose an approach based on a Pareto evolutionary algorithm which extends a previous work [5].

After defining the problem we propose to solve in Section 2, we present our model of speed tuning in Section 3. The evolutionary computation principles are presented in Section 4 by explaining also the Indicator-Based Evolutionary Algorithm we use to compute ST solutions. Experimental results based on real data are then provided and discussed in Section 5. These examples are proposed to assess the algorithm with two objectives on the Gonesse junction (France) and with three objectives on the line Saint-Étienne -Rive de Giers (France). Finally Section 6 concludes the paper.

Problem overview

The main goal consists in designing the most suited speed profile over space. The space corresponds to a sequence of intervals I (block sections) in which the speeds can be changed. Figure 1 represents the decomposition of a one-section journey in four steps. A maximum speed v max limits the train speed. According to this limit and the train parameters the speed can be defined in each step. The first step (A) corresponds to the train acceleration when the speed grows from 0 to v max (if the train can reach v max ). Before dealing with the cruising and coasting phases it is necessary to compute the braking phase (B) to be sure that the needed braking distance will not exceed the remaining distance before the end. The cruising phase (Cr) corresponds to the speed maintaining, that is, a null acceleration when the traction effort equals the resistance to the train advance. The coasting phase (Co), depicted by the dashed lines on Figure 1, is engaged when the engine is stopped and the train moves thanks to its inertia. During this phase, no energy is consumed and hence in order to reduce the energy consumption it is interesting to vary the instant (or position) from which the engine is stopped and the coasting phase is started (see points 1, 2, 3 in Fig. 1). The sooner the coasting phase starts the greater the economy but the later the train will arrive. Thus the goal of the problem solving is to determine a good tradeoff between energy consumption, running time and delay occured.

Speed tuning model

Naturally, the four-steps model explained above cannot be applied everywhere and the shape of speed profile depends on the entrance speed v 0 (position 0) and the exit speed v X (po- sition X). Between these two positions 0 and X it is necessary to determine the speeds according to a chosen policy. In this way, we introduce two intermediate speeds v 1 and v 2 which help us to build the speed profile.

A train path is composed of n sections. Therefore, for a section S, we have a set of five speeds:

v S max , v S 0 , v S 1 , v S 2 , v S X .
When the train starts its journey, speed v 1 0 is null for section 1 (v 1 0 = 0), while in the arrival section speed v n X = 0. When the train leaves a section S and enters in the following section (S + 1), the exit speed of section S equals the entrance speed of section S + 1:

v S X = v S+1 0 in such a way that: v S X ≤ min(v S max , v S+1 max ). Speeds v 1 , v 2 to
be determined are limited by the maximum speed of the section S: v S 1 ≤ v S max and v S 2 ≤ v S max . Taking these elements into account, we generalize for a sequence of sections that three speeds have to be determined per section: v 1 , v 2 and v X . These values will be searched by the evolutionary algorithm we propose in Section 4. Speed profile is determined according to a three steps model:

1. the entrance phase tunes speed for accelerating/decelerating from v 0 to v 1 ; 2. the exit phase is assessed before the intermediate phase for varying speed from v 2 to v X ;

3. the intermediate phase tunes the speed from v 1 to v 2 according to our policy depending on v 1 > v 2 or not.

The set of basic definitions useful for the remainder of the paper are summarized in Table 1.

Objectives

The problem can be represented as a set Φ of n ≤ 3 objective functions to be minimized. The first function ϕ 1 represents the minimization of the travel duration whereas the energy consumption reduction is illustrated by function ϕ 2 . Note that this minimization is related to the reduction of the mechanical energy. The amount of durations corresponds to the sum of all durations needed to travel within the sections.

Φ = (ϕ 1 , ..., ϕ n ), n ≤ 3 (1) ϕ 1 = min T (2) ϕ 2 = min E m (3) ϕ 3 = min D (4)
E m = P m (t) dt (5)
P m (t) = F T (t) v(t) (6)
In function of the needs, we can add or remove objectives. The basic objective consists in minimizing the travel duration, hence the minimal formulation of the problem is Φ = (ϕ 1 ) and this formulation will allow to work out reference solutions for fairly evaluating mult-objective solutions. In addition to this basic objective, we can add one or two objectives such that the problem can be formulated as follows: Φ = (ϕ 1 , ϕ 2 ) for optimizing two objectives or Φ = (ϕ 1 , ϕ 2 , ϕ 3 ) for optimizing three objectives.

Elements of railway dynamics

The fundamental equation of dynamics states that the relation between the forces, mass and acceleration:

F T (t) -F R (t) = ρ m a(t)
Note that ρ is a mass correction factor usually set to ρ = 1.04 [START_REF]Handbook of Railway Vehicle Dynamics[END_REF][START_REF] Albrecht | Railway Timetable & Traffic -Analysis, Modelling, Simulation, chapter Energy-Efficient Operation Train Operation[END_REF]. The train data also depict the traction effort profile which indicates effort F T (t) according to a speed v(t). The resistance to the train advance F R (t) corresponds to the sum of the resistances, i.e. the line resistance L R and the braking efforts if the train brakes:

F R (t) = L R (t) + B R (t)
Line resistance L R is defined according to the slope and its angle β:

L R (t) = ρ m g sin β, where g = 9.81m/s 2

The braking effort B R (t) at instant t is depicted by a braking profile related to the train and depending on speed v(t). Thanks to this profile, we can determine the braking a b (t) as follows:

a b (t) = B R (t)
ρ m Now, with these elements we can determine the acceleration, cruising, coasting and braking phases. We note that only acceleration and cruising phases need energy.

Acceleration

This can be defined as follows:

a(t) > 0 ⇔ F T (t) > F R (t) (7)
a(t) = F T (t) -F R (t) ρm (8)
F T (t) and F R (t) are calculated according to speed v(t) as explained before. The acceleration phase from speed

v A to v B (v A < v B
) is iterated each second (instant i) and updates the acceleration a(i), the speed v(i) and the position x(i) (Algorithm 1).

Algorithm 1: Calculation of an acceleration phase

v(i) = v A ; while v(i) < v B do Update position x(i + 1) = 0.5a(i) + v(i) + x(i);
Update acceleration a(i + 1) according to v(i); Update speed:

v(i + 1) = v(i) + a(i); Update energy: E m = E m + E m (i) with E m (i) = F T (i) × v(i); Update duration: T = T + 1 ; i = i + 1 end

Cruising

The cruising phase maintains the train speed v from position x 0 along a distance d without accelerating:

a(t) = 0 ⇔ F T (t) = F R (t)
Algorithm 2 explains the computation of the cruising.

Coasting

During a coasting phase the engine is stopped: F T (t) = 0. If the slope is null or positive β ≥ 0.0, the speed decreases because a(t) < 0. Otherwise the slope is negative (β < 0.0) and the speed will increase. In this latter case, it will be necessary to brake. The calculation of this phase is very close to an acceleration except for the energy consumption which stays null. The coasting between speed v A and v B (v A > v B ) is iterated each second (Algorithm 3) while the crossed distance does not overtake the available distance d for the coasting.

Algorithm 2: Calculation of a cruising phase while x(i) < x 0 + d do Update position:

x(i + 1) = x(i) + v ; Calculate F R (v) according to v and the gradient β ; Set F T (v) = F R (v) ; Update energy: E m = E m + F T (i) × v ; Update duration: T = T + 1 ; i = i + 1 end Algorithm 3: Calculation of a coasting phase v(i) = v A ; while (x(i) < x 0 + d) and (v(i) > v B ) do Update position x(i + 1) = 0.5a(i) + v(i) + x(i); Update acceleration a(i + 1) = -F R (i) ρ×m ; Update speed: v(i + 1) = v(i) + a(i); Update duration: T = T + 1 ; i = i + 1 end

Braking

The braking phase combines two resistance forces: the resistance to the train advance and the service braking force. So the calculation is identical as in a coasting phase except for determining the acceleration:

a(i + 1) = -F R (i)
ρ×m -a b (i) with a b (i) depending on v(i) and F R (i)) subject to the gradient of the slope.

Entrance and exit phases

Before evaluating the intermediate phase it is necessary to determine on the one hand the entrance phase and on the other hand the exit phase. For each one, duration, distance and energy are calculated according to v 0 compared with v 1 and v 2 compared with v X . Figure 2 depicts the possible cases described below.

Entrance

The entrance phase is determined according to v 0 and v 1 . Two cases may arise (Fig. 2(a)):

1. if v 0 < v 1 then an acceleration occurs, increasing speed from v 0 to v 1 ; 2. if v 0 > v 1 then a braking is done, decreasing speed from v 0 to v 1 (illustrated by v 0 and v 1 ).

In all these cases, a distance d 0 is needed to vary the speed during T 0 . The consumed energy E 0 is null if it is a braking phase, otherwise E 0 > 0.

0 0 v' 1 v v 0 v max v x v max v x v v' v 2 2 X X (a) (b)
Figure 2: Scheme of (a) entrance and (b) exit phases

Exit

The exit phase is done in the same way by using v 2 and v X and two cases may also arise (Fig. 2(b)):

1. if v 2 < v X then an acceleration occurs, increasing speed from v 2 to v X ; 2. if v 2 > v X then a braking is done, decreasing speed from v 2 to v X (illustrated by v 2 and v X ).
A distance d X and a duration T X are needed for this phase. The consumed energy E X is positive (E X > 0) if the phase is an acceleration.

Intermediate phase

Once the exit phase is computed, the feasibility of the solution must be checked. Indeed the travelled section has an available distance d S and we must be sure that d 0 + d X < d S in so far as an available distance remains to allow varying the speed from v 1 to v 2 during the intermediate phase.

Let d I = d S -d 0 -d X be the available distance to vary the speed from v 1 to v 2 . Three cases may arise:

1. if v 1 > v 2 and the slope is null or positive, then we try to insert a coasting phase to decrease the speed and to save energy. If it is possible, we insert a cruising phase before the coasting for completing all the distance available (Fig. 3(a), the plain line).

The only consumed energy (E I > 0) is due to the cruising phase. When the distance is not enough to do a complete coasting then a braking phase from v 1 to v 2 must be calculated and we search for intersection of coasting and braking phases (Fig. 3(a), the dashed line) and in this case E I = 0;

2. if v 1 > v 2
and the slope is negative (it is a descent), then train can accelerate without effort. We compute the acceleration on the distance d I and the braking from v max to v 2 . Then the intersection point of acceleration and braking has to be found and the intermediate phase is achieved (Fig. 3(b));

3. if v 1 < v 2 then an acceleration from v 1 to v 2 will be necessary and we insert it halfway through (travelled distance d A ). Cruising phases are added before and after the acceleration, the first at speed v 1 and the second at speed v 2 (Fig. 3(c)). The cruising phases are done on the same distance ((d I -d A )/2). The consumed energy corresponds to the amount of energy required for each phase. Naturally, it is necessary to check whether each phase can be inserted according to the remaining distance or not. If the distances do not allow to insert the chosen phases, the solution is marked as not feasible and penalized during the evaluation in the evolutionary algorithm.

Evolutionary Multi-objective Optimization

An evolutionary algorithm (EA) is an iterative process of exploratory search. Our choice is led by a preference to obtain a set of sufficiently diversified solutions in a single run. Indeed, the evolutionary algorithms with Pareto approach are capable to produce well-spread incomparable solutions along the Pareto front. That could be an advantage to help the decision makers in the case of real-life problems [START_REF] Ghazali | Metaheuristics: from design to implementation[END_REF].

An EA is a nature-inspired metaheuristic gathering a set of solutions (individuals or chromosomes): a population. The latter evolves while recombining pairwise individuals in such a way that new original and improved solutions are produced. A mutation operator allows to diversify the population while randomly modifying solutions. These new solutions are added to a temporary population which will partially or totally constitute the population at the next iteration, depending on the algorithm policy of the population renewal. Algorithm 4 presents the main steps of a general purpose EA.

Multi-objective Optimization

A general Multi-objective Optimization Problem (MOP) can be defined by a set of n objective functions (f 1 , f 2 , . . . , f n ), a set X of feasible solutions in the decision space, and a set Z of feasible points in the objective space. Without loss of generality, we here assume that each objective function is to be minimized. To each solution x ∈ X is assigned an objective vector z ∈ Z on the basis of the vector function f : X → Z with z = f (x) = (f 1 (x), f 2 (x), . . . , f n (x)) as illustrated by Figure 4. An objective vector z ∈ Z is said to dominate1 another objective vector z ∈ Z iff ∀i ∈ {1, 2, . . . , n}, z i ≤ z i and ∃j ∈ {1, 2, . . . , n} such as z j < z j . An objective vector z ∈ Z is said to be nondominated iff there does not exist another objective vector z ∈ Z such that z dominates z. A solution x ∈ X is said to be efficient if its mapping in the objective space results in a nondominated point. The set of all efficient solutions is the efficient set, denoted by X E . The set of all non-dominated vectors is the Pareto front, denoted by Z N . A possible approach in MOP solving is to find the minimal set of efficient solutions, i.e. one solution x ∈ X E for each non-dominated vector z ∈ Z N such as f (x) = z. However, generating the entire efficient set is usually infeasible due to the complexity of the underlying problem. Therefore, the overall goal is often to identify a good approximation of it. EAs are commonly used to this end as they are able to find multiple and well-spread non-dominated solutions in a single simulation run [START_REF] Kalyanmoy | Multi-objective Optimization using Evolutionary Algorithms[END_REF].

Indicator Based Evolutionary Multi-objective Algorithm

Although there exists several state-of-the-art multi-objective EAs (NSGA-II [START_REF] Deb | A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: Nsga-ii[END_REF], SPEA2 [START_REF] Zitzler | SPEA2: Improving the strength pareto evolutionary algorithm[END_REF]), we use Indicator Based Evolutionary Algorithm [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF]. Indeed IBEA is a method more modern than the most widely used EA: NSGA-II. This is a good illustration of the new trend dealing with indicator-based search, and started to become popular for recent years. The main idea behind IBEA is to introduce a total order between solutions by means of a binary quality indicator. Its fitness assignment scheme is based on a pairwise comparison of solutions from the current population with regards to an arbitrary indicator I. To each individual x is assigned a fitness value F (x) measuring the 'loss in quality' if x was removed from the current population P , i.e. F (x) = x ∈P \{x} (-e -I(x ,x)/κ ), where κ > 0 is a user-defined scaling factor. Different indicators can be used for such a purpose, and we here choose to use the binary additive -indicator (I + ) as defined in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF]. I + (x, x ) gives the minimum value by which a solution x ∈ X has to or can be translated in the objective space to weakly dominate another solution x ∈ X. Selection for reproduction consists of a binary tournament between randomly chosen individuals. Selection for replacement consists of iteratively removing the worst solution from the current population until the required population size is reached; fitness information of the remaining individuals is updated each time there is a deletion.

Solution encoding and initialization

A solution is defined by a vector of real values. Each value corresponds to one speed. Given that three speeds are necessary to represent a section, we can state the vector length l equals three times the number of sections (n): l = 3n. Even if the speeds are bounded by maximum entrance, exit and section speeds, three ranges of speeds are defined: slow, middle and high speeds in such a way that one third of the solutions are either slow, middle or high speed tuned. For example, let S 1 , S 2 be two sections with respective maximum speeds: 90 km/h and 120 km/h. Three ranges of values are possible: ([0, 30], [0, 40]), ([30, 60], [40,80]) and ([60, 90], [80,120]). Such a mechanism is useful to bring a good diversity in the initial population by designing more or less fast solution and inversely more or less energy expensive. Then, the initialization is done by randomly assigning speeds.

Section 0 Section n v 0 1 v 0 2 v 0 X ... v n 1 v n 2 v n X

Operators

Evaluation

As we mentioned before, our MOP is composed of two objective functions (Φ = (ϕ 1 , ϕ 2 )).

Objective function ϕ 1 corresponds to the minimization of the amount of the durations T i needed for each section i: ϕ 1 = min T with T = n i=1 T i . Objective function ϕ 2 is in charge of the reduction of the energy consumption: ϕ 2 = min E with E = n i=1 E i . This global consumption equals the amount of energy required for each section i. Each section is evaluated according to the model presented before in such a way that we know pair (T i , E i ) of each section i.

Recombination

The recombination step is done by means of two operators: crossover and mutation. Since we deal with a continuous problem, we use operators specifically designed for this kind of problem: the Simulated Binary crossover (SBX) [START_REF] Deb | Simulated binary crossover for continuous search space[END_REF] and similarly, the mutation is based on a polynomial mutation adapted to search over continuous space.

Experimental results

The results presented in this section concern two locations in France. The first example is based on the Gonesse junction (near Paris) and the second represents the line from Saint-Étienne to Rive de Giers with one stop.

Implementation and Parameter Setting

In order to develop our approach, we use framework ParadisEO in which a lot of metaheuristics are implemented [START_REF] Liefooghe | A unified model for evolutionary multiobjective optimization and its implementation in a general purpose software framework: ParadisEO-MOEO[END_REF]. This tool is a white box in which the different steps of the algorithms have to be defined. In the case of IBEA the user has to implement crossover, mutation and evalutation steps and also the problem-related components.

The population of 50 individuals evolves over 1, 000 generations. Crossover (x r ) and mutation (m r ) rates are respectively set to x r = 0.9 and m r = 0.5.

Case study 1: Gonesse junction Description

Here is proposed a real-life case study: the Gonesse junction is crossed by a train (m = 180, 000kg). Eight sections are used for our example whose results are depicted in Figure 6. The plain line indicates the maximum speeds of the sections. The path has 14,285m of length and eight sections are crossed. Each section is limited by a maximum speed. This case study is interesting because there are two sections with switch points (sections 2 and 5). These sections are very short (resp. 150m and 90m). Furthermore the switch points sections have slow speed limit (60 km/h) whereas the other sections have much higher speed limits (until 200 km/h). So, these sections bring about braking phases to be managed at best. In this example, we assume there is no slope (the gradients are null).

Performance assessment

Here we propose to discuss three solutions obtained by our approach. Let S * be a solution to the mono-objective problem consisting in just minimizing the travel duration. Let S 1 and S 2 be two solutions to the bi-objective problem and compared with S * . The results are provided in Table 2 and the deviation compared with S * is also reported.

Sol.

E Figure 6 illustrates the speed profile of each solution. It is interesting to note that solutions S 1 , S 2 have big coasting phases, that is why these are less energy expensive than S * . Besides, we can see that S * has very long acceleration phases which are very energy expensive. The differences of consumption can also be observed in Figures 7(a,b,c) which depict the produced effort and highlight that Solution S * consumes more energy than the others. If we focus on the energy saving compared with the delay, we can note that with around 5% of time in more, we can save around 25% of energy. Moreover, if we extend the delay to around 15% of time in more, we can save till around more than half of energy. That proves the interest to take some seconds in more to travel for saving a lot of energy.

Furthermore, the algorithm as well as the underlying method have proved their capability to provide a set of diversified and incomparable solutions.

Case study 2: line Saint-Étienne -Rive de Giers Description

In this example, a train travels from Saint-Étienne (SE) to Rive de Giers (RG) by stopping at Saint Chamond (SC) during 1 minute. The train used for the example is an AGC2 which is a light passenger train used for the little regional travels. Data about resistance can be found in [START_REF] Lukaszewicz | Running resistance results and analysis of full-scale tests with passenger and freight trains in sweden[END_REF] and about effort to rim in [START_REF] Kaller | Traction Électrique[END_REF]. A timetable is predefined and depicted on Figure 8. The train starts from SE at 0 and must arrive at SC before h 1 A = 420. After stopping during 60 seconds, the train leaves the station at h 1 D = 480 for arriving at RG before or at h 1 A = 960. The total crossed distance is 20,200m. Moreover, in order to be more accurate in the description of the problem the slopes are taken into account. The gradients over position are depicted on Figure 9(a) and are defined in n meters for 1,000. Indeed, since tan x is very close to sin x for little values of x, it is usual to compute the line resistance by taking n/1000 instead of sin β [START_REF] Brünger | Railway Timetable & Traffic -Analysis[END_REF]. Therefore, the line resistance can be approximated as follows: L R (t) = ρ m g n/1000. Contrary to the previous example in which we assume there is no slope, a coasting could not be a slowdown given that the gradients can be negative (fig. 9(a)). Indeed, it would be interesting to manage at best the descents by properly adjusting the speeds in order to avoid to accelerate unnecessarily when the train can increase just thanks to the slope. By defining timetable constraints, the delays have to be reduced and this reduction can be seen as a third objective which can be integrated in the MOP. Hence the resolution adopted here can involve till three criteria: MOP= (ϕ 1 , ϕ 2 , ϕ 3 ).

Performance assessment

Due to the different number of objectives, three cases of optimization are considered. In the first case, just the travel duration is minimized (Φ = (ϕ 1 )) for obtaining a reference solution as with the previous example. This solution, denoted A*, is the basis of comparison with the other solutions obtained in the other cases with two or three objectives, respectively denoted A i 2 and A i 3 . Table 3 presents the detailed results of the solutions proposed in each case. As we could assume, Solution A* proposes the best performance to minimize the travel duration, but also to minimize the delay. However, the energy consumption is the highest observed among the results as we can expect.

When adding at least one objective, the performance about the travel duration is slightly weaker than for A*. Indeed, with just a few seconds in more (less than 2%), the saved energy can reach till 50% of Solution A* consumption. Such a saving can be explained by the track slope which favours high cruising speeds without strong effort. That is why reducing the duration of some seconds needs a far bigger effort.

In the third case, when optimizing all the objectives, minimizing duration and delay may appear redundant. However, in this example, the delay occurs at station SC and not after. Indeed, the allowed duration for going from station SE to station RG seems to be a little bit too short, whereas the delay may be recovered between SC and RG. The allowed duration between these two latter stations is fully sufficient and such that the train can arrive in advance at the last station. Thus, it is possible to reduce the travel duration while increasing the delay. That is why it is relevant to distinguish travel duration and delay into two separate objectives to be optimized concurrently. Therefore, the results provided by the last optimization (MOP= (ϕ 1 , ϕ 2 , ϕ 3 )) tend to highlight the pressure on the solutions to optimize all the objectives. Indeed, all the solutions have durations less than 1% of time in more and the increase of occurred delays does not exceed 10%. This deviation of the delays is more satisfying than in the case of optimization with two objectives. That shows the relevance to add a third objective to limit the delays. Moreover, by analyzing the results we can observe that the delays occur at station SC (less than one minute) whereas the total travel durations indicate that the train can arrive in advance to its final destination. Even if the timetable constraints are almost respected, the arrival time at SC seems to be a little bit tight while it is slackened at station RG. We can assume the timetable was built for a previous rail engine with different technical data such that the timetable is not completely adapted to the new equipment.

Figures 10 and11 illustrate the distribution of the solutions obtained in three cases (one, two or three objectives). Although the diversity is weak and the fronts are not spread, it is interesting to note that the combination of three objectives allows to find good tradeoff solutions. This fact is very relevant from an operational point of view whenever the decision makers search for a good compromise in order to satisfy both their own needs and the

SE SC RG A h =420 D h =480 D h =0 A h =960

Conclusion and perspectives

In this paper we have dealt with a problem of speed tuning in railway management. The solving goal is to optimize both concurrent objectives: on the one hand by minimizing the travel duration and the delays, and on the other hand by reducing the energy consumption.

To this end we have presented an evolutionary multi-objective approach for tuning speeds in order to minimize the durations while saving energy. This algorithm is based on IBEA and uses specific operators well-known in the literature for searching solutions in continuous space. The speed tuning is achieved by our method of speed profile building which introduces two intermediate speeds between the entrance and exit speeds of a section. This method paired with IBEA for searching in a continuous space brings its efficiency to the light. Furthermore, we have shown the interest of adding a third criterion about the reduction of the delays which is quite different to the reduction of the travel durations, even if However, the lack of diversity in the proposed solutions leads up to consider metaheuristics more adapted to the search of solutions in continuous space such as CMA-ES (Evolution Strategies with Covariance Matrix Adaptation [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF]) and its multiobjective extension [START_REF] Igel | Covariance matrix adaptation for multi-objective optimization[END_REF]. Moreover, in order to integrate this approach in train dispatching model it will be necessary to mix different kinds of variables. That is why our future works will focus on the development of mixed-variables model capable to both deal with continuous variables for defining speed profiles and discrete variables for scheduling the trains according to the timetable. Besides, in order to improve the robustness of the method and its efficiency, the future developments will take uncertainty [START_REF] Jin | Evolutionary optimization in uncertain environments -a survey[END_REF] into account.

Figure 1 :

 1 Figure 1: Speed tuning over space in four steps: acceleration (A), cruising (Cr), coasting (Co) and Braking (B)

Figure 3 :

 3 Figure 3: Three cases of intermediate phase: (a) v 1 > v 2 and β ≥ 0.0, (b) v 1 > v 2 and β < 0.0, (c) v 1 < v 2

Figure 4 :

 4 Figure 4: Representation of a solution (x 1 , x 2 ) in the decision space and the corresponding values in the objective space: (y 1 , y 2 , y 3 ) = f (x 1 , x 2 ).

Figure 5 :

 5 Figure 5: Pattern of a solution: a vector of real values for the speeds

Figure 6 :

 6 Figure 6: Example of speed tuning on several sections near Gonesse junction

  Effort during Solution S 2

Figure 7 :

 7 Figure 7: Train effort according to its position for each solution: S * , S 1 , S 2

Figure 9 :Figure 10 :

 910 Figure 9: Description of the slopes of the line Saint Étienne -Rive de Giers (a) and speed profiles obtained by optimization with one (A*), two (A 2 4 ) and three (A 3 5 ) objectives.

Figure 11 :

 11 Figure 11: Distribution of the obtained solutions (Delay/Energy)

Table 1 :

 1 Definition of the main symbols used in the paper

	The third objective ϕ 3 function aims at

Table 2 :

 2 Energy consumption and duration of solutions S * , S 1 , S 2

		[kJ]	Deviation [%]	T [s]	Deviation [%]
	S * 507,618		484.13
	S 1	378,683	-24.5%	508.79	+4.9%
	S 2	246,245	-51.5%	555.63	+14.7%

Table 3 :

 3 Energy consumption, travel duration and delay of solutions obtained while optimizing one, two and three objectives during the travel on the line Saint Étienne -Rive de Giers customers.

	0		0	1			1
			11300m		9200m
			Stop during 1 minute
	Figure 8: Description of the line Saint Étienne (SE) -Rive de Giers (RG) with one stop at
	Saint Chamond (SC) during one minute.
	Sol. E [kJ] Deviation [%] T [s] Deviation [%] D [s] Deviation [%]
			One objective, ϕ 1
	A* 216031		763		23
			Two objectives, MOP= (ϕ 1 , ϕ 2 )
	A 1 2 A 2 2 A 3 2 A 4 2 A 5 2	125604 121051 117970 104456 101486	-41.8 -43.9 -45.3 -51.6 -53.0	766 767 768 777 792	+0.3 +0.5 +0.65 +1.8 +3.8	25 25 25 32 47	+8.7 +8.7 +8.7 +39.1 +104.3
			Three objectives, MOP= (ϕ 1 , ϕ 2 , ϕ 3 )
	A 1 3 A 2 3 A 3 3 A 4 3 A 5 3 A 6 3	182732 131592 130094 123959 119518 117975	-15.4 -39.0 -39.7 -42.6 -44.6 -45.3	764 765 766 767 769 768	+0.13 +0.26 +0.3 +0.5 +0.78 +0.65	23 24 24 24 24 25	+0.0 +4.3 +4.3 +4.3 +4.3 +8.7

We will also say that a decision vector x ∈ X dominates a decision vector x ∈ X if f (x) dominates f (x ).

Autorail Grande Capacité built by Bombardier.


Alessandro Ruzzi

PROJECTIVE NORMALITY OF COMPLETE TOROIDAL SYMMETRIC VARIETIES

In [CM II] Chirivì and Maffei have proved that the multiplication of sections of any two line bundles generated by global sections on a wonderful symmetric variety is surjective. We prove two criterions that allow us to reduce the same problem on a (smooth) complete toroidal symmetric variety to the analogous problem on the corresponding complete toric variety (respectively on the corresponding open toric variety). We have also studied in details some family of complete toroidal symmetric varieties, in particular those of rank 2.

In this work we study the projective normality of complete toroidal symmetric varieties. Let G be an adjoint semisimple group over C and let θ be an involution of G. We define H as the subgroup of the elements fixed by θ and we say that G/H is a homogeneous symmetric variety. De Concini and Procesi [ CSV I] have defined a wonderful completion X of G/H and this is the unique wonderful completion of G/H. In this work we define a toroidal symmetric variety as a normal G-variety with a dense open orbit isomorphic to G/H and a G-equivariant map Y → X extending the identity of G/H. They have been classified by De Concini and Procesi [CSV II]. In particular they showed that there is an equivalence of categories between the category of complete toroidal symmetric varieties and the category of toric varieties proper over an affine space A l considered as a (C * ) l -variety in the obvious way, where l is the rank of G/H. In this work we say that a toric variety proper over A l (considered as a (C * ) l -variety) is an open toric variety. Moreover there is a one-to-one correspondence between the completions Y of G/H which lie over X and the elements of a special class of complete toric varieties. One can show that the complete toric variety Z c corresponding to a complete toroidal symmetric variety Y is a subvariety of Y and the open toric variety Z corresponding to Y is an open subvariety of Z c .

In this work, unless explicitly stated otherwise, we shall always assume that the complete toroidal symmetric variety Y is smooth. Recall that by [CSV II] then it follows that: 1) any orbit closure in Y is also smooth; 2) the associated toric varieties Z and Z c are both smooth. A complete toroidal symmetric variety is projective if and only if the corresponding complete toric variety is projective. Moreover they are projective if and only if the associated open toric variety is quasi-projective (see Proposition 1.5 and [Br] Corollary 3.3).

Chirivì and Maffei [CM II] have proved the following result which easily implies the projective normality of X with respect to any projective embedding by a complete linear system. Theorem 0.1 Let L 1 and L 2 be any two line bundles generated by global sections on the wonderful symmetric variety X. Then the product of sections

H 0 (X, L 1 ) ⊗ H 0 (X, L 1 ) -→ H 0 (X, L 1 ⊗ L 2 )
is surjective.

We try to generalize this result to any complete toroidal symmetric variety. First we prove that the surjectivity of the product of sections of two ample line bundles on a complete toroidal symmetric variety is equivalent to the surjectivity of the product of sections of the restrictions of the line bundles to the corresponding complete toric variety (see Theorem 2.1). Thus we have reduced the problem to a problem on toric varieties. Unfortunately, it is very difficult to verify the surjectivity of the product of sections of any two ample line bundles on a generic complete toric variety. However, we can simplify the problem for the special class of complete toric varieties which we are considering. Indeed we prove that the surjectivity of the product of sections of two ample line bundles on Z c , say L 1 and L 2 , is equivalent to the surjectivity of the product of sections of the restrictions of the line bundles to Z (see Theorem 3.1 and Theorem 4.1). This problem is much simpler, because H 0 (Z, L 1 |Z) and H 0 (Z, L 2 |Z) are infinite dimensional vector spaces and it is sufficient to prove that a suitable finite dimensional subspace of H 0 (Z, (L 1 ⊗ L 2 )|Z) is contained in the image of the product of sections. Indeed we prove that, given any ample line bundle L on Z c , H 0 (Z, L|Z) is generated by H 0 (Z c , L) as an O Z (Z)-module.

In Section 5 we study the surjectivity of the product of sections of an ample line bundle on a toric variety proper over A l . If the variety has dimension 2, we prove that the product of sections of any two ample line bundles is surjective. If the dimension of the variety is larger than 2, we find a infinite number of varieties proper over A l such that, for any ample line bundle L on such a variety Z, the product of sections of L H 0 (Z, L) ⊗ H 0 (Z, L) -→ H 0 (Z, L ⊗ L) is surjective.

We would like to thank C. De Concini for the continuous help. Moreover we would like to thank W. Fulton for some useful information.

Notations and background

Let G be a semisimple simply connected algebraic group over C and let θ be an involution of G. We define H as the normalizer N G (G θ ) of the subgroup of θ-fixpoints. Let G be the adjoint semisimple group associated to G and let H be the subgroup of the elements fixed by the involution induced by θ, then G/H is isomorphic to G/H through the map induced by the quotient map G → G.

Definition 1.1 We will say that G/H is a homogeneous symmetric variety (of adjoint type).

Given any abelian group A we will denote by A R the corresponding real vector space A ⊗ Z R.

We can associate a not necessarily reduced root system to G/H (see [He] and [T]). Let T 1 be a torus of G such that: 1) θ(t) = t -1 for each t ∈ T 1 ; 2) the dimension l of T 1 is maximal. Let T be a maximal torus which contains T 1 . One can show that T is stabilized by θ, so θ induces an involution on χ(T ) R , which we call again θ. This involution stabilizes the root system R G of G and it is orthogonal with respect to the Killing form. We can choose a Borel subgroup B of G such that the associated set of positive roots R + G has the following property: for each α ∈ R + G either θ(α) is equal to α or θ(α) is a negative root. For each root α we define α s = α -θ(α). The set R G,θ := {α s = 0 : α ∈ R G } is a not necessarily reduced root system of rank l called the restricted root system. We will say that the non-zero α s are restricted roots and that l is the rank of G/H. The restricted roots generate the (-1)eigenspace of χ(T ) R . Let T 0 be the connected component of the subgroup of the invariant of T and let S be the quotient of T 1 by T 1 ∩ T 0 . The linear map χ(S) R G G χ(T 1 ) R induced in an obvious way by the quotient map

T 1 G G G G S is an isomorphism, while the linear map χ(T ) R G G χ(T 1 ) R
induced by the canonical injection T 1 1 G G T is surjective and its restriction to the (-1)-eigenspace is an isomorphism. Thus we can identify χ(S) R with the space generated by the restricted roots. Moreover we can identify χ(S) with the lattice generated by the restricted roots. Now we want to describe the lattice of integral weights of R G,θ . Let Λ be the lattice of integral weights of R G , let Λ + be the set of dominant weights of R G and let Γ be the basis of R G associated to R + G . For each α ∈ Γ, let ω α be the fundamental weight associated to α. For each dominant weight λ, let V λ be the irreducible representation of G of highest weight λ. We will say that a dominant weight λ is spherical if V λ contains a non-zero vector fixed by the Lie algebra h of H. Moreover we will say that a weight µ is special if θ(µ) = -µ. Let Ω be the lattice generated by the spherical weights and let Λ 1 be the lattice of the special weights. One can easily show that 2Λ 1 ⊂ Ω ⊂ Λ 1 . We can describe Ω more explicitly. Let R 0 G be the set of roots fixed by θ and let

R 1 G = R G -R 0 G . We set Γ 0 = Γ ∩ R 0 G and Γ 1 = Γ ∩ R 1 G . The set Γ s = {α s : α ∈ Γ 1 } is a basis of R G,θ .
The map θ induces an involution θ of Γ 1 such that, for each α ∈ Γ 1 , θ(α) = -θ(α) -β α where β α is a linear combination of simple roots in R 0 G . We can order the simple roots α 1 , ..., α l , α l+1 , ..., α l+s , α l+s+1 , ..., α m so that α i is fixed by θ if and only if i > l + s. Moreover we can suppose that α s 1 , ..., α s l are distinct. For each i = 1, ...l we define ω i as follows: if θ(α) = α then ω i = ω αi , otherwise ω i = ω αi -θ(ω αi ) = ω αi -ω θ(αi) . A weight is special if and only if it is a linear combination of the weight ω 1 , ..., ω l , so {ω 1 , ..., ω l } is a basis of Λ 1 . Moreover we can use these weights to give the following explicit description of Ω.

Proposition 1.1 (Lemma 2.1 and Theorem 2.3 in [ CM I]) Let Ω + be the set of spherical weights, then

Ω ∩ Λ + = Ω + . Moreover Ω = l i=1 Za i ω i where a i ∈ {1, 2} for each i. The constant a i is equal to 2 if θ(α i ) = -α i , while it is equal to 1 if θ(α i ) = -α i . In particular a i = 1 if θ(α i ) = α i . For each i and j we have a i ω i , (α s j ) ∨ = b i δ i,j where (α s j ) ∨ is the coroot associated to α s j and b i ∈ {1, 2}. Moreover b i = 2 if and only if 2α s i ∈ R G,θ .
Notice that the proposition implies that the fundamental Weyl chamber C + of R G,θ is the intersection of χ(S) R with the fundamental Weyl chamber of R G . We will say that a special weight n i ω i is regular if n i > 0 for each i. Thus a spherical weight is regular if and only if it is a strongly dominant weight of the restricted root system (with respect to the basis Γ s ). The Weyl group W L,θ of the restricted root system is called the restricted Weyl group and it has the following description.

Proposition 1.2 (See 1.8 in [CS]) One can identify the restricted Weyl group W L,θ with the group {w ∈ W : w • t 1 ⊂ t 1 }/W 0 , where W is the Weyl group of R G and W 0 is the Weyl group of the root system R 0 G .

Let λ be a regular spherical weight and let k λ be a non-zero vector of V λ fixed by h. One can show that k λ is unique up to a non-zero scalar. Let x 0 be the class of k λ in P(V λ ). De Concini and Procesi have defined the wonderful completion X of G/H as the closure of Gx 0 in P(V λ ). Now we want to give a local description of X. Choose a basis of V λ formed by weight vectors and consider the affine open set A of P(V λ ) where the coordinate corresponding to the highest weight v λ is not zero. Notice that A ∩ X is U - stable, where U -is the unipotent group associated to

R 1 G ∩ (-R + G ), namely U -= α∈R 1 G ∩(-R + G )
U α as a variety. One can show that the closure of T x 0 in A is an affine space A l with coordinates -α s 1 , ..., -α s l . Moreover the map ϕ : U -× A l → A ∩ X given by ϕ(g, v) = g • v is an isomorphism. For each i, let X -α s i be the divisor of X whose intersection with U -× A l is the locus of zeroes of -α s i . De Concini and Procesi have proved that X does not depend on λ. Moreover X is wonderful according to the definition of Luna:

Theorem 1.1 (Theorem 3.1 in [ CSV I]) Let X be as before, then:

1. X is a smooth projective G-equivariant embedding of G/H. In particular the stabilizer of x 0 is H;

2. X\ (Gx 0 ) is a divisor with normal crossings. It has irreducible components X -α s 1 , ..., X -α s l and they are smooth subvarieties of X; 3. the G-orbits of X correspond to the subsets of {1, 2, ..., l}, so that the orbit closures are the intersections

X -α s i 1 ∩ ... ∩ X -α s i k
with {i 1 , ..., i k } ⊂ {1, 2, ..., l}; 4. there is an unique closed orbit l i=1 X -α s i and it is isomorphic to G/P , where P is the parabolic subgroup of G associated to Γ 0 , i.e. the Lie algebra of

P is t ⊕ α∈R 1 G ∪R + G ) g α .
We will say that a G-variety Y with a open orbit isomorphic to G/H is a symmetric variety if it is normal. All symmetric varieties are spherical varieties, i.e. they have a dense B-orbit; indeed BH/H is a dense open B-orbit in G/H (see Proposition 1.3 in [ CSV I]). We will say that a symmetric variety Y with an open orbit isomorphic to G/H is toroidal if there is a G-equivariant map π : Y → X extending the identity map of G/H. The toroidal symmetric varieties have been classified by De Concini and Procesi (see [CSV II]). Later on, Luna and Vust have classified the spherical varieties with a fixed open Gorbit (see [LV]); in particular they have classified the symmetric varieties with a fixed open G-orbit (see also [V]). In the literature a spherical variety is called toroidal if every B-stable prime divisor which contains a G-orbit is G-stable. We want to remark that a symmetric variety is toroidal (according to our definition) if and only if it is a toroidal spherical variety (see [LV] and [V]).

Let Z c 0 be the closure of A l in X; it is the complete toric variety whose fan is composed by the Weyl chambers and their faces.

Theorem 1.2 (Theorem 5.2 and 5.3 in [CSV II]) There is an equivalence between the category of complete toroidal symmetric varieties and the category of toric varieties proper over A l . Given a complete toroidal symmetric variety π : Y → X the corresponding open toric variety Z is the inverse image of A l in Y . Moreover there is a one-to-one correspondence between complete toroidal symmetric varieties and complete toric S-varieties over Z c 0 whose fan is W L,θinvariant. The variety Z c corresponding to the symmetric variety Y is the inverse image of Z c 0 , moreover the variety Z c is the closure of Z in Y and the variety Y is smooth if and only if Z (or equivalently Z c ) is smooth.

The inverse image of the open set U

-× A l is isomorphic to U -× π -1 (A l ) in a U -• T equivariant way.
Moreover the G-orbits of Y are in one-to-one correspondence with the S-orbits of Z. In this work, unless explicitly stated otherwise, we shall always assume that the complete toroidal symmetric variety Y is smooth. In this case any orbit closure in Y is also smooth.

Now we want to study the line bundles on a complete toroidal symmetric variety. First of all, we can identify the Picard group of the wonderful symmetric variety X with a subgroup Λ X of the lattice Λ of integral weights of G.

Proposition 1.3 (Proposition 8.1 in [ CSV I]) The map P ic(X) → P ic(G/P ) induced by the canonical inclusion is injective.

Recall that we can identify P ic(G/P ) with a sublattice of the lattice of weights. Moreover P ic(G/P ) ≡ P ic G (G/P ) because G is simply connected. Thus to any linearized line bundle L ∈ P ic G (G/P ) we can associate the opposite λ of the character -λ with which T acts on the fibre over P/P . We denote a line bundle on X by L λ if its image is the weight λ. Let λ be a dominant weight such that P(V λ ) contains a line r fixed by H, for example λ ∈ Ω + . One can show that the map G/H gH → g • r can be extended to a morphism ψ λ : X → P(V λ ). The line bundle ψ * λ O(1) is L λ . Thus, given a line bundle L λ on X such that λ is dominant, there is a sub-representation of H 0 (X, L λ ) isomorphic to V * λ and obtained by pullback of H 0 (P(V λ ), O(1)) to X (this representation is unique because X is a spherical variety).

Definition 1.2 We will say that a root α ∈ Γ 1 is an exceptional root if θ(α) = α and α, θ(α) = 0. Moreover we will say that a normal G-equivariant embedding of G/H is an exceptional symmetric variety if there is an exceptional root.

Theorem 1.3 (Theorem 4.8 in [CS]) P ic(X) is generated by the spherical weights and by the fundamental weights corresponding to the exceptional roots.

Let X be the wonderful symmetric variety and let Y be the complete toroidal symmetric variety over X associated to a toric variety Z. We will denote by ∆ the fan of Z and by ∆ c the fan of Z c . Let o γ be the S-orbit of Z associated to γ ∈ ∆. We will denote by O τ the corresponding G-orbit of Y . We shall denote by Z γ the stable subvariety of Z associated to γ ∈ ∆, by Z c γ the stable subvariety of Z c associated to γ ∈ ∆ c and by Y γ the stable subvariety of Y associated to γ ∈ ∆. We set ∆

(i) = {γ ∈ ∆ : dim γ = i} and ∆ c (i) = {γ ∈ ∆ c : dim γ = i}.
The closed orbits O σ of Y are in one-to-one correspondence with the maximal cones of the fan ∆ associated to Z and they are all isomorphic to the unique closed orbit of X through the restriction of the projection, so we can identify P ic(O σ ) with Λ X for each σ ∈ ∆(l). The group P ic(Z) is freely generated by the line bundles O(Z τ ) where τ varies in the set ∆(1)\∆ 0 (1). Given a cone γ ⊂ (χ(S) * ) R we will call γ ⊥ the subspace of χ(S) R consisting of the vectors which vanishes on γ.

Theorem 1.4 (Theorem 2.4 in [Bi]) Let Y be the complete toroidal symmetric variety associated to Z. Then

1. The maps Z 1 i G G Y π G G X induce the split exact sequence 0 G G P ic(X) π * G G P ic(Y ) i * G G P ic(Z) G G 0, so P ic(Y ) is (not canonically) isomorphic to P ic(X) ⊕ P ic(Z).
2. A section of the previous split short exact sequence is given by sending the free generators

O(Z τ ), with τ ∈ ∆(1)\∆ 0 (1), to O(Y τ ).
3. The morphism given by the restriction to the closed orbits

c G 1 : P ic(Y ) → σ∈∆(l) P ic(O σ )
is injective and its image can be identified with the lattice

Λ Y = {h = (h|σ) ∈ σ∈∆(l) Λ X ⊂ σ∈∆(l) Λ : h|σ -h|σ ∈ χ(S) ∩ (σ ∩ σ ) ⊥ ∀ σ, σ ∈ ∆(l).}
We will indicate with L h the line bundle whose image is h. We know that P ic(Y ) is isomorphic to the group of equivariant line bundles P ic G (Y ) because G is simply connected and Y is complete. Moreover, given a line bundle L h , -h σ is the character of the action of T on the fibre over the T -stable point O σ ∩ Z. In a similar way, we define h c as the set (h|σ) where σ varies in ∆ c (l) and -h σ is the character of the action of T on the fibre over the T -stable point of Z c corresponding to σ. In some case we can give a useful interpretation of h and h c . Let M be a lattice in χ(S) R which contains χ(S).

Definition 1.3 A real valued function h : |∆| → R on the support of ∆ is called a (∆, M )-linear function if h is linear on each σ ∈ ∆.
Let h|σ be the unique linear function which coincide with h on σ. We request moreover that h|σ belongs to M and that h|σ 1 -h|σ 2 belongs to χ(S) for each σ, σ 1 and σ 2 in ∆(l). Let SF (∆, M ) be the additive group of the (M, ∆)-linear functions.

Sometimes we say that an element h of SF (∆, M ) is a ∆-linear function and a ∆-linear function h may be thought of as a function

h : χ * (S) R → R ∪ {-∞}. We say that a ∆-linear function h is convex if h(v + v ) ≥ h(v) + h(v ) for each v, v .
We say that h is strictly convex on ∆ if moreover h|σ = h|σ for each σ, σ . If a torus S is an étale cover of S, then we can identify SF (∆, χ(S )) with the group of S -linearized line bundles on Z. We can suppose that -h|σ is the character of S on the fibre L h (x σ ) over the S -stable point x σ associated to any maximal cone σ of ∆.

Definition 1.4 Let L h be a line bundle on Y . We will say that L h and h are almost spherical if h|σ belongs to the lattice generated by the spherical weights for each σ ∈ ∆(l). Moreover we will say that L h and h are spherical if h|σ is a spherical weight for each σ ∈ ∆(l).

If L h is an almost spherical line bundle, the element h may be thought of as a (∆, Ω)-linear function and, accordingly, the element h c may be thought of as a (∆ c , Ω)-linear function.

Now we want to describe the sections of a line bundle over Y . Observe that the space of sections is multiplicity-free because Y is a spherical variety.

Definition 1.5 Given h ∈ Λ Y let Π(Z, h) = {µ ∈ σ∈∆(l) (h|σ + (χ(S) ∩ σ))}, Π(Y, h) = Π(Z, h) ∩ Λ + ,
and

Π(Z c , h) = {µ ∈ σ∈∆ c (l) (h|σ + (χ(S) ∩ σ)).
Observe that a weight λ in Λ X belongs to Π(Z, h) (respectively to Π(Z c , h)) if and only if λ ≥ h (respectively λ ≥ h c ) as function on χ * (S) R .

Theorem 1.5 (Theorem 3.4 in [Bi]) Let L h be a line bundle on Y . Then

H 0 (Y, L h ) = µ∈Π(Y,h) V * µ .
In particular H 0 (Y, L h ) = 0 if and only if Π(Y, h) is not empty.

We want to give an idea of a possible construction of H 0 (Y, L h ). We will say that a vector v ∈ χ * (S) -{0} is primitive if an equality v = av , where v is a vector in χ * (S) and a is a positive integer, implies a = 1. Given any one-dimensional rational cone τ , we denote by (τ ) the unique primitive vector contained in τ .

Lemma 1.1 (Lemma 2.7 in [Bi]) The line bundle O(Y τ ) is almost spherical and the associated ∆-linear function d τ satisfies the equalities d τ ( (τ )) = -δ τ,τ for each τ ∈ ∆(1). Moreover, if we define s τ ∈ H(Y, L d τ ) as the unique, up to a non-zero scalar, section whose divisor is Y τ , then we have that

s τ is G-invariant. Observe that, given λ ∈ Λ X , then λ ∈ Π(Z, h) if and only if h = λ+ τ ∈∆(1) a τ d τ for appropriate positive integers a τ . Let λ ∈ Π(Y, h) and recall that H 0 (X, L λ ) contains V * λ . We have H 0 (X, L λ ) ⊂ H 0 (Y, π * L λ ), so H 0 (Y, π * L λ ) contains a lowest weight vector v -λ of weight -λ. Making use of the definition of Π(Z, h), we can find positive constants a τ such that h -λ = τ ∈∆(1) a τ d τ . The Lemma 1.1 implies that v -λ • s aτ τ is a non-zero section of H 0 (Y, L h ) with weight -λ. Moreover v -λ • s aτ τ is invariant by the unipotent part of the op- posite B -of the fixed Borel group of G. Thus H 0 (Y, L h ) ⊇ µ∈Π(Y,h) V * µ .
Because of the previous theorem we give the following definition:

Definition 1.6 Given h in Λ Y and λ in Π(Y, h), write h = λ + τ ∈∆(1) a τ d τ for suitable a τ ∈ Z + . We define s h-λ as the section s aτ τ of H 0 (Y, L h-λ ).
We want to describe also the the sections over Z, respectively over Z c .

Proposition 1.4 Let L h be a line bundle on Y . Then

1. H 0 (Z, L h |Z) = µ∈Π(Z,h) Cχ µ ,
where χ µ is a T -seminvariant section of weight -µ.

2.

H 0 (Z c , L h |Z c ) = µ∈Π(Z c ,h) Cχ µ .
Remark. Let π : Y → Y be an G-equivariant morphism between two complete toroidal symmetric varieties and let L h be a line bundle on Y . Then the pullback π * (L h ) is the line bundle on Y associated to h and

H 0 (Y, π * (L h )) = H 0 (Y , L h ).
Now we want to explain some relations between the previous sets.

Corollary 1.1 (Corollary 4.1, Proposition 4.2 and Theorem 4.2 in [Bi])

1. Given h ∈ Λ Y , we have the equality Π(Y, h) = Π(Z c , h) ∩ Λ + . 2. If h ∈ Λ Y is almost spherical, then Π(Z c , h) = w∈W L,θ w • Π(Y, h).
Moreover the restriction map

H 0 (Y, L h ) → H 0 (Z c , L h |Z c ) is surjective.
We want to make some remarks about the case of an almost spherical h. Let

w • µ ∈ Π(Z c , h) with µ ∈ Π(Y, h). Any section s ∈ V * µ ⊂ H 0 (Y, L h ) of weight -w • µ has non-zero restriction to Z c because U -• Z c is dense in Y .
Moreover, up to choose another basis of the root system, we can suppose that it is a lowest weight vector.

Recall that there is a one-to-one correspondence between the convex functions on (χ(S) * ) R with values in R ∪ {-∞} and the convex sets in χ(S) R , which send a convex function h to the convex set

Q h = {m ∈ χ(S) R : m(v) ≥ h(v), ∀ v ∈ (χ(S) * ) R }. Moreover h(v) = inf {m(v); m ∈ Q h } for each v ∈ (χ(S) * ) R .
Recall that a polyhedron is the intersection of a finite number of semispaces.

Definition 1.7 Let Y be a complete toroidal symmetric variety and let L h be an almost spherical line bundle on Y . We define the polytope associated to L h as

P h = {m ∈ χ(S) R : m(v) ≥ h c (v) ∀v ∈ |∆ c |}.
Moreover we define the polyhedron associated to L h as

Q h = {m ∈ χ(S) R : m(v) ≥ h(v) ∀v ∈ |∆|}. Observe that P h = {m ∈ χ(S) R : m( (τ )) ≥ h c ( (τ )) ∀ τ ∈ ∆ c (1)} and Q h = {m ∈ χ(S) R : m( (τ )) ≥ h( (τ )) ∀τ ∈ ∆(1)}.
Brion (see Theorem 3.3 in [Br]) has found a characterization of the ample line bundles (respectively the line bundles generated by global sections) on a spherical variety. Using the previous characterization, one can obtaining the following proposition about the line bundles on a complete toroidal symmetric variety. See Section 7 in [Ru] for a direct proof.

Proposition 1.5 Let L h be a line bundle on Y . Then 1. L h is generated by global sections if and only if h is convex and h|σ is dominant for each σ ∈ ∆(l).

2. L h is ample if and only if h is strictly convex on ∆ and h|σ is a regular weight for each σ ∈ ∆(l).

Remark. 1) One can also prove that L h is ample if and only if it is very ample (see Proposition 7.1 in [Ru]).

2) A complete toroidal symmetric variety Y is projective if and only if Z c is projective. Moreover Y is projective if and only if Z is quasi-projective. Indeed, given h ∈ SF (∆, χ(S)), the associated line bundle on Z is ample if and only if h is strictly convex over ∆ (see Theorem 3.3 in [Br]).

3) One can reformulate the Proposition 1.5 using h c instead of h. Let h be an almost spherical ∆-linear function. One can prove that h c is convex on ∆ c if and only if h is convex on ∆ and h|σ is dominant for each σ ∈ ∆(l). Moreover h c is strictly convex on ∆ c if and only if h is strictly convex on ∆ and h|σ is a regular weight for each σ ∈ ∆(l).

Reduction to the complete toric variety

In the following we will always suppose that L h is an almost spherical line bundle, unless we will explicitly say otherwise.

We start to study the multiplication of sections of two line bundles on Y . First of all, we want to show that this problem is equivalent to the similar problem on the complete toric variety Z c associated to Y . Let L h and L k be any two line bundles on Y generated by global sections. Let

M h,k : H 0 (Y, L h ) ⊗ H 0 (Y, L k ) -→ H 0 (Y, L h+k )
be the product of sections on Y and let

m c h,k : H 0 (Z c , L h |Z c ) ⊗ H 0 (Z c , L k |Z c ) -→ H 0 (Z c , L h+k |Z c )
be the product of sections of the restrictions to Z c of these line bundles.

Theorem 2.1 Let L h and L k be two almost spherical line bundle on Y generated by global sections. Then M h,k is surjective if and only if m c h,k is surjective.

Proof. The necessity of the condition is implied by the Corollary 1.1. Indeed,

if i : Z c → Y is the canonic inclusion, then m c h,k • (i * ⊗ i * ) = i * • M h,k . Now suppose that m c h,
h-w1•λ H 0 (Y, L w1•λ ) ⊂ H 0 (Y, L h ) and s k-w2•µ H 0 (Y, L w2•µ ) ⊂ H 0 (Y, L k ). We know that Im M w1•λ,w2•µ contains a lowest weight vector ϕ ∈ H 0 (Y, L w1•λ+w2•µ ) of weight -ν. Thus s h+k-w1•λ-w2•µ ϕ is contained in s h+k-w1•λ-w2•µ Im M w1•λ,w2•µ ⊂ Im M h,k and it is not zero.
We can prove the following proposition without assuming the surjectivity of m c h,k . Given two convex (Ω, ∆)-linear functions, say h and k, let Π(Y, h, k) be the set of the weights of the lowest weight vectors contained in ImM h,k .

Proposition 2.1 Π(Y, h, k) is saturated with respect to the dominant order of the roots in R G,θ .

Proof. Π(Y, h + k) is saturated because the simple restricted roots have negative values on |∆|. Given ν ∈ Π(Y, h, k) there are two weights λ ∈ Π(Z c , h) and µ ∈ Π(Z c , k) such that ν = λ + µ. Moreover there are elements w 1 , w 2 in the Weyl group W L,θ such that w 1 • λ and

w 2 • µ are dominant weights. Observe that ν ≥ w 1 • λ + w 2 • µ on |∆|, so ν ∈ (Y, w 1 • λ + w 2 • µ). Let ν be a spherical weight dominated by ν, then ν ∈ Π(Y, w 1 • λ + w 2 • µ) because this set is saturated. Let ϕ be a lowest weight vector of weight ν . Making use of the surjectivity of M w1•λ,w2•µ we have ϕ ∈ s h+k-w1•λ-w2•µ ImM w1•λ,w2•µ ⊂ ImM h,k .

Reduction to the open toric variety

In this section we want to show that, given two ample line bundles on Y , the product of their sections on Z c is surjective if and only if the product of sections on Z is surjective. Moreover we will study the relation between the sections of L|Z and the sections of L|Z c for any ample line bundle L on Y .

Let us define some notations. We fix a cone σ ∈ ∆(l) and we set v h = h|σ for each h ∈ SF (∆, Ω), so (Z, h) = Q h ∩ (χ(S) + v h ) and Π(Z c , h) = P h ∩ (χ(S) + v h ). Write Γ s = {f 1 , ..., f l }; observe that it is a basis of χ(S) R and let {e 1 , ..., e l } be the dual basis of (χ(S) * ) R . We have to define a second basis {g 1 , ..., g l } of χ(S) R because the fundamental Weyl chamber C + is more easily defined using the basis of fundamental weights than the basis of the simple roots. The vector g i is a positive multiple of -ω i , more precisely -g i is the i-th fundamental weight of the unique reduced root system contained in R G,θ which share a basis with R G,θ . The vectors g 1 , ..., g l generate a lattice which contains χ(S). Let {ǧ 1 , ..., ǧl } be the dual basis of {g 1 , ..., g l }. Observe that C + = σ(-g 1 , ..., -g l ). Given a point p in χ(S) R we will use the following notations: p = x i f i = ẋi g i , using the "normal" coordinates for the basis {f 1 , ..., f l } and the "dotted" coordinates for the basis {g 1 , ..., g l }. (In the following figures we consider the case where the restricted root system is of type A 2 and Z is A 2 ).

• _ _ _ G G o G o G o G o G o G o G p p Ö p Ö p Ö p Ö p Ö p Ö p M M 8 8 y y g 1 g 2 f 2 f 1 C + • • • • • • • _ _ G G o G o G o G p p Ö p Ö p Ö p Ö p M M 8 8 y y q q q q M M M M M M M M M M M
q q q q q q q q q q q M M M M

P h • • • • • • • _ _ G G o G o G o G p p Ö p Ö p Ö p Ö p M M 8 8 y y q q M M M M M M q q q q q q M M M M M M M M M M M M M Q h Proposition 3.1 Let L h be an ample spherical line bundle on Y . Then Q h ∩ C + = P h ∩ C + and Q h = P h ∩ C + + σ(f 1 , ..., f l ).
Proof. The equations of Q h are of the form b i x i ≥ b for appropriate constants b i . Thus Q h is stable by translation with respect to vectors in σ(f 1 , ..., f l ), i.e.

Q h + R + (f i ) ⊂ Q h .
Let H j be the hyperplane of χ(S) R generated by g 1 , ..., g j , ..., g l and let s j be the orthogonal reflection with respect to H j . Observe that, if P h contains a point p, then it contains all the translates of p by W L,θ , so it contains the orthogonal projections 1 2 (p + s j p) of p to the hyperplane H j . Moreover there is no vertex of P h contained in H j , because h c is strictly convex on ∆ c .

The function h K associated to a polyhedron K has always finite values if and only if K is compact. Moreover, there is a decomposition in convex cones of the convex set {n ∈ (χ(S) * ) R : h K (n) ∈ R} such that there is a one-to-one correspondence between the cones of such decomposition and the faces of K.

Hence there is a one-to-one correspondence between the 1-dimensional cones of such decomposition and the semi-spaces that define K. Given such a cone τ the associated semi-space is {m ∈ χ(S) R : m( (τ )) ≥ h K ( (τ ))}.

Let m be any point in Q h ∩ C + ∩ χ(S) Q . Given any τ ∈ ∆ c (1), there are w ∈ W L,θ and τ ∈ ∆(1) such that (τ ) = w • (τ ), because of the symmetry of ∆ c . Observe that w

-1 • m -m is a linear combination c i f i of the f i with positive coefficients, so m( (τ )) = (w -1 • m)( (τ )) ≥ m( (τ )) ≥ h( (τ )) = h c ( (τ )).
Thus m belongs to P h , hence P h ∩ C + = Q h ∩ C + because P h is closed. The decomposition in cones of (χ(S) * ) R associated to h P h ∩C + has 1-dimensional cones {σ(ǧ 1 ), ..., σ(ǧ l )} ∪ ∆(1). The function h P h ∩C + has finite values on all (χ(S) * ) R , it is equal to h on |∆| and vanishes on the vectors ǧ1 , ..., ǧl . The function associated to σ(f 1 , ..., f l ) vanishes on |∆| and has value -∞ on the complementary set. The sum h P h ∩C + + h σ(f1,...,f l ) is equal to the function h associated to Q h , thus the proposition follows by the fact that h Q +h Q = h Q+Q for each polyhedrons Q and Q .

We can prove a stronger statement on the "rational" points of Q h , respectively of P h . Proposition 3.2 Let L h be an ample spherical line bundle on Y , then

Q h ∩ (v h + χ(S)) = P h ∩ C + ∩ (v h + χ(S)) + l i=1 Z + f i . Remark. Observe that H 0 (Z, L|Z) is a O Z c (Z c )-module through the re- striction map O Z c (Z c ) → O Z (Z) and H 0 (Z c , L|Z c ) is a O Z c (Z c )-submodule of H 0 (Z, L|Z). This proposition implies that H 0 (Z, L|Z) is generated by H 0 (Z c , L|Z c ) as an O Z (Z)-module.
Proof. Observe that f j is orthogonal to H j and the vector f i = 1 2 (f i + s j f i ) belongs to H j for each i = j. The vectors f i with i = j are pairwise distinct and form a basis of H j . Moreover f i = f i + 1 2 d i f j for a suitable positive integer d i , because the -f i are the simple restricted roots. We have the following easy consequence of the Proposition 3.1.

Lemma 3.1 Q h ∩ H j = P h ∩ H j ∩ C + + i =j R + fi . Proof. Given p = p + r i f i ∈ Q h ∩ H j with p ∈ P h ∩ C + and r i positive constants, we have p = 1 2 (p + s j p ) + r i 1 2 (f i + s j f i ). Let R j = {p + af i | p ∈ Q h ∩ H j and -1/2 ≤ a ≤ 1/2}.
First of all we want to describe the conditions for a point p ∈ χ(S) R to belong to R j . Fixed any j, we define another basis {u 1 , ..., u l } of χ(S) R such that u j = f j and u i = g i if i = j. The conditions for a point p = y i u i to belong to Q h ∩ H j are y j = 0 plus conditions of the form i =j n i y i ≥ n. Thus the conditions for a point p = y i u i to belong to R j are the inequalities of the form i =j n i y i ≥ n that define Q h ∩ H j plus the inequalities -1/2 ≤ y j ≤ 1/2. The following fundamental lemma is the unique part of the proof in which we will use the strictly convexity of h c i.e. the ampleness of L h .

Lemma 3.2 R j is contained in Q h for each j. • • • • • • • _ _ G G p p M M 8 8 y y q q q M M M M M M M q q q q q q q M M M M M R 2 • • • • • • • • • • • • • M M M M M M M M M q q q M M M M M M M q q q q q q q P h ∩ H 2 + [-1 2 , 1 2 ]f 2
Proof. Making use of the Lemma 3.1, it is sufficient to show that

P h ∩ H j ∩ C + + [-1/2, 1/2]f j ⊂ Q h . Because of the convexity of Q h , it is sufficient to show that Q h contains the points p ± (1/2)f j for each vertex p of P h ∩ H j .
Given such a vertex p , let p = p + af j be the intersection of p + R >0 f j with the border of P h (p exists because h c is strictly convex). The point p should be a vertex of P h , otherwise p is an interior point of a segment I contained in P h . In this last case the symmetry of P h implies that p is an interior point of the orthogonal projection of I to H j , a contradiction. Since p belongs to χ(S) and s j (p) is equal to p -af j , we have 2a ∈ Z. Observe that p and s j (p) belong to P h , hence also the points p +(1/2)f j and p -(1/2)f j belong to P h by convexity.

. Now we can conclude the proof of the Proposition 3.2 (look to the following figure). Let p =

x i f i = ẋi g i be a point contained in Q h ∩ (M + v h ). If ẋi ≤ 0 for each i, then p ∈ P h ∩ C + . Otherwise there is an index j such that ẋj > 0. We know that p = p + a i f i where p ∈ P ∩ C + and the a i are positive constants. Observe that the point p -

[a j ]f j = p + (a j -[a j ])f j + i =j a i f i belongs to Q h ∩ (M + v h )
and it has j-th coordinate with respect to {g 1 , ..., g l } strictly less than 2 ([a j ] is the integral part of a j ). Moreover, this coordinate can be at most 1 because p -[a j ]f j is a weight. We can suppose that it is exactly 1, so p -[a j ]f j -(1/2)f j belongs to Q h ∩ H j and it is the projection of p -[a j ]f j to H j . Thus p-[a j ]f j belongs to R j , so also p-[a j ]f j -f j belongs to R j and its j-th coordinate with respect to {g 1 , ..., g l } is negative. Moreover p -(p -[a j ]f j -f j ) is a linear combination of the f i with positive integral coefficients. If there is an index k such that p -[a j ]f j -f j has negative k-th coordinate with respect to {g 1 , ..., g l }, then we reiterate the process. This process ends in a finite number of steps because Q h is contained in the semi-space { x i ≥ h(e 1 + ... + e l )}.

• • • • • • M M f f f f _ _ G G o G o G o G p p Ö p Ö p Ö p Ö p 8 8 y y M M M M M M M M p
Now we can prove the most important theorem of this work.

Theorem 3.1 Let L h and L k be two spherical ample line bundles on Y . Then m h,k is surjective if and only if m c h,k is surjective.

Proof. One can easily show that the theorem is equivalent to the following more combinatorial statement:

Q h ∩ (v h + χ(S)) + Q k ∩ (v k + χ(S)) = Q h+k ∩ (v h+k + χ(S))
if and only if

P h ∩ (v h + χ(S)) + P k ∩ (v k + χ(S)) = P h+k ∩ (v h+k + χ(S)).
The sufficiency of the condition is easy to show. Given a point p ∈ Q h+k ∩ (χ(S)+v h+k ) we know that p = p + c i f i where p ∈ P h+k ∩C + ∩(χ(S)+v h+k ) and the c i are positive integers. Moreover there are p h ∈ P h ∩ (χ(S) + v h ) and

p k ∈ P k ∩ (χ(S) + v k ) such that p = p h + p k . Thus p = (p h + c i f i ) + p k and p h + c i f i belongs to Q h ∩ (χ(S) + v h ). Suppose now that Q h ∩(v h +χ(S))+Q k ∩(v k +χ(S)) = Q h+k ∩(v h+k +χ(S)). Let p = z i f i =
żi g i be a point in P h+k ∩(χ(S)+v h+k ). We can suppose that p belongs to C + by the symmetry of the polytopes P h and P k . By hypothesis there are two points p 0 ∈ Q h ∩ (χ(S) + v h ) and q 0 ∈ Q k ∩ (χ(S) + v k ) such that p 0 + q 0 = p. First, we will show that we can choose p 0 and q 0 such that p 0 belongs to P h . Indeed we know that p 0 = p 0 +v where p 0 ∈ P h ∩C + ∩(χ(S)+v h ) and v ∈ Z + f i , so p = p 0 + q 0 where q 0 := q 0 + v belongs to Q k ∩ (χ(S) + v k ). Proceeding as in the Proposition 3.2, we can define a sequence of pairs of points {(p i , q i )} i=0,...,r with the following properties: 1) p i ∈ Q h ∩(χ(S)+v h ) for each i; 2) q i ∈ Q k ∩(χ(S)+v h ) for each i; 3) p = p i +q i for each i; 4) (p 0 , q 0 ) is as before; 5) (p i+1 , q i+1 ) = (p i +f ji , q i -f ji ) for a suitable j i and 6) q r ∈ P k . Indeed we can define the {q i } as in the Proposition 3.2 and then we set p i = p -q i . Now it is sufficient to show by induction that we can choose the indices j i so that p i belongs to P h for each i. We know that p 0 ∈ P h . Now suppose that p n belongs to P h by inductive hypothesis. Suppose that p n =

x i f i = ẋi g i and q n = y i f i = ẏi g i . If q n ∈ P k we define r = n and there is nothing to prove. Otherwise there is an index j n such that ẏjn > 0 and it is sufficient to prove that p n + f jn belongs to P h . Observe that -ẋjn > 0, so -ẋjn ≥ 1 because ẋjn is an integer. Moreover s jn p n = p n -ẋjn f jn belongs to P h . Thus P h contains p n + f jn because it is convex. Thus we can choose p n+1 = p n + f jn .

Remark. 1) The previous theorem is valid with the weaker hypotheses that h, k are convex and that h|σ, k|σ are regular spherical weights for each σ ∈ ∆(l). Indeed these hypotheses imply that no vertex of P h (respectively of P k ) is contained in a Weyl wall.

2) Suppose that h = k is convex and that h|σ is a regular spherical weight for each σ ∈ ∆(l). In this case one can show that L h |Z is the pullback of an ample line bundle on a possibly singular toric variety Z over A l . This suggests to consider only ample line bundles.

Line bundles on an exceptional complete toroidal symmetric variety

Let Y be an exceptional complete toroidal symmetric variety, let Z be the associated open toric variety and let ∆ be the fan of Z. Given an ample spherical line bundle L h over Y , we know that the multiplication M h,h of sections on Y is surjective if and only if the multiplication m h,h of sections on Z is surjective.

In this section we want to generalize this fact to the non spherical line bundles.

Recall that P ic(X) is generated by the spherical weights and by the fundamental weights ω α1 , ..., ω αs corresponding to the exceptional roots α 1 , ..., α s .

Proposition 4.1 Let L h be an ample line bundle on Y such that M h ,h is surjective and let a 1 , ..., a l be positive integers. If we define h = h + a i ω αi then the product M h,h of sections of L h over Y is surjective.

Proof. Observe that L h is an ample bundle on Y . We will prove the proposition by induction on a i . The map M h,h is trivially surjective if a i = 0. We need a lemma on the maps M h,ωα i . Lemma 4.1 Let L h be an ample line bundle on Y and let ω ∈ {ω α1 , ..., ω αs }. Then M h,ω is surjective.

Proof. In the following V * λ is the unique subrepresentation of H 0 (Y, L λ ) which contains a lowest weight vector v λ of weight -λ. We have

H 0 (Y, L h ) = λ∈Π(Y,h) s h-λ V * λ , H 0 (Y, L h+ω ) = λ∈Π(Y,h) s h-λ V * ω+λ and H 0 (Y, L ω ) = V * ω .
The lemma is implied by the fact that, for each λ ∈ Π(Y, h), the vector M h,ω ( s h-λ v λ ⊗v ω ) is a lowest weight vector of weight -λ -ω.

Now we go back to the proposition. Let j be an index such that a j > 0 and define h = h -ω αj . We have the following commutative diagram

H 0 (Y, L h ) ⊗ H 0 (Y, L h ) ⊗ H 0 (Y, L ωα j ) ⊗ H 0 (Y, L ωα j ) G G m1 H 0 (Y, L h ) ⊗ H 0 (Y, L h ) M h,h H 0 (Y, L 2 h ) ⊗ H 0 (Y, L ωα j ) ⊗ H 0 (Y, L ωα j ) m2 H 0 (Y, L 2 h+ωα j ) ⊗ H 0 (Y, L ωα j ) M 2 h+wα j ,wα j G G H 0 (Y, L 2h ),
where m 1 is surjective by induction, m 2 and M 2 h+wα j ,wα j are surjective by the previous lemma; thus M h,h is surjective.

Theorem 4.1 Let L h be an ample line bundle on Y . If m h,h is surjective then M h,h is surjective.
Proof. We know that, up to exchange α i with θ(α i ) for some i in {1, ..., l}, there are positive integers a 1 , ..., a l such that the line bundle L h , with h = ha i w i , is spherical and ample. The restriction of L h to Z is isomorphic to the restriction of L h to Z, so m h ,h is surjective. Thus M h ,h is surjective because of the Theorem 3.1. Hence M h,h is surjective by the previous proposition.

Open projectively normal toric varieties

Now we want to describe some families of open toric varieties such that, if L h is any ample line bundle on such a variety, then the product m h,h of sections is surjective. One family is formed by all the varieties of dimension 2 proper over A 2 . Moreover we will find an infinite number of varieties that have such property for every given dimension. In the following we will identify χ(S) with Z l . Given a real number x, we denote the integral part of x by [x].

Blow-ups of A l

Now we study the class of varieties that are blow-ups of A l along an irreducible stable closed subvariety.

Proposition 5.1 Let Z be the blow-up of A l along the irreducible stable closed subvariety associated to σ(e 1 , ..., e r ). Let L h and L k be two line bundles generated by global sections on Z, then the product of sections m h,k is surjective.

Proof. The inequalities for Q h (respectively for Q k ) are z i ≥ a i for each i = 1, .., l and z 1 + ... + z r ≥ b (respectively z i ≥ c i for each i = 1, .., l and z 1 + ... + z r ≥ d). Here the a i , b, the c i and d are suitable integers. Let m be any point in Q h+k ∩ M , then there are m1 = (x 1 , ..., x l ) in Q h and m2 = (y 1 , ..., y l ) in Q k such that m1 + m2 = m, but they may have non integral coordinates. We want to translate m1 with respect to a "little" vector v so that m1 +v will belongs to Q h ∩Z l and m2 -v will belongs to

Q k ∩Z l . Let i = -[([x i ]-x i )] and observe that i is also equal to -[([y i ] -y i )]. We have [x i ] + i ≥ x i ≥ [x i ] ≥ a i and [y i ] + i ≥ y i ≥ [y i ] ≥ c i

Open toric varieties of dimension 2

Now we consider the family of (smooth) toric varieties proper over A 2 . Theorem 5.1 Let Z be any smooth toric variety proper over A 2 . Let L h1 and L h2 be two linearized line bundles generated by global sections and suppose that h 1 and h 2 are strictly convex on the same fan, then the product of sections m h1,h2 is surjective.

The hypotheses mean that there is a toric variety Z and two ample line bundles L h and L k over Z such that L h is the pullback of L h and L k is the pullback of L k . We want to remark that Z may be singular. In the following figure we consider the case where the fan of Z contains four 1-dimensional cones.

• • • • • • G G G G y y y y G G y y T T T T T
c c t t t t t t X X p 3 1 p 3 2 m Q h3 q 3 I 3 i0 I 3 i0 f 1 f 2 f 1 + f 2 a 1 f 1 + a 2 f 2
Proof. Define a scalar product ( , ) such that {f 1 , f 2 } is a orthonormal basis. Let h 3 = h 1 + h 2 and let ∆ be the fan of Z. It is obviously sufficient to prove that

Q h3 ∩ χ(S) = Q h1 ∩ χ(S) + Q h2 ∩ χ(S)
. We can write the polyhedrons Q hi as unions (I j i + σ(f 1 , f 2 )), where the I j i are rational polytopes of dimension at most equal to one. Moreover we can suppose that: 1) (

I 1 i + σ(f 1 , f 2 )) + (I 2 i + σ(f 1 , f 2 )) = (I 3 i + σ(f 1 , f 2 )); 2) dim I 1 i = dim I 2 i = dim I 3 i . Let m = (x 1 , x 2 ) be any point in Q h3 ∩χ(S) and suppose that m is contained in I 3 i0 + σ(f 1 , f 2 ). If I 3
i0 is a point then we have reduced ourselves to the case of the polyhedrons associated to the pullback of line bundles on A 2 . Thus we can suppose that I 3 i0 is a segment line. Let a 1 f 1 + a 2 f 2 be a vector orthogonal to this segment. We can suppose that it is a primitive vector contained in σ(f 1 , f 2 )) and that a 1 ≥ a 2 (up to exchange f 1 with f 2 ). We want to prove that

(I 1 i0 + σ(f 2 , f 2 )) ∩ χ(S) + (I 2 i0 + σ(f 1 , f 2 )) ∩ χ(S) = (I 3 i0 + σ(f 1 , f 2 )) ∩ χ(S) by induction on a 1 + a 2 .
For each j let p j 1 = (z 1,j 1 , z 1,j 2 ) and p j 2 = (z 2,j 1 , z 2,j 2 ) be the vertices of I j i0 and let q j = (z 2,j 1 , z 1,j 2 + z 1,j 1 -z 2,j 1 ). Let I j i0 be the convex hull of p j 1 and q j . The polyhedron

I j i0 + σ(f 1 , f 2 ) is the union of I j i0 + σ(f 1 + f 2 , f 2 ), I i i0 + σ(f 1 , f 2 ) and p j 2 + σ(f 1 , f 2 ). Moreover ( I 1 i0 + σ(f 1 , f 2 )) ∩ χ(S) + ( I 2 i0 + σ(f 1 , f 2 )) ∩ χ(S) = ( I 3 i0 + σ(f 1 , f 2 )) ∩ χ(S) by the Proposition 5.1. Finally (I 1 i0 + σ(f 1 + f 2 , f 2 )) ∩ χ(S) + (I 2 i0 + σ(f 1 + f 2 , f 2 )) ∩ χ(S) = (I 3 i0 + σ(f 1 + f 2 , f 2 )) ∩ χ(S) because of the inductive hypothesis (indeed {f 1 , f 1 + f 2 } is a basis of χ(S), a 1 f 1 + a 2 f 2 = (a 1 -a 2 )f 1 + a 2 (f 1 + f 2 ) and a 1 < a 1 + a 2 ).

Stable subvarieties

In some case we can reduce the study of the product of sections of two ample line bundles to the study of the product of sections of the restrictions of these line bundles to irreducible stable closed subvarieties. First of all, Brion has proved the following proposition.

Proposition 5.2 (See Theorem 4 in [BrI]) Let L be any line bundle generated by global sections on a smooth quasi-projective toric variety Z. Suppose that either Z is complete or it is proper over A l . Then, given two cones γ ⊂ γ in ∆, the restriction

H 0 (Z γ , L|Z γ ) -→ H 0 (Z γ , L|Z γ ) is surjective.
Proposition 5.3 Let L h and L k be two linearizated line bundles generated by global sections on a smooth quasi-projective toric variety Z. Suppose that either Z is complete or it is proper over A l . Let τ be a cone in ∆(1) and let s be a global section of L h+k which does not vanish on Z τ . If s|Z τ belongs to the image of the product m τ h,k of sections of the restrictions of L h and L k to Z τ , then s belongs to the image of the product m h,k of sections of L h and L k .

Proof. Since there is a basis of semi-invariant sections, we can suppose that s is a semi-invariant section of weight µ, so µ( (τ )) = (h + k)( (τ )). Because of the previous proposition, there are sections

s i ∈ Γ(Z c , L h ) and s i ∈ Γ(Z c , L k ) such that m τ h,k ( s i |Z c τ ⊗ s i |Z c τ ) is s|Z c τ , so m h,k ( s i ⊗ s i ) = s.

Two families of open toric varieties of dimension at least 3

Now we want to show that there is an infinite number of open toric varieties of any fixed dimension (greater than 2) such that the product of sections of any two ample line bundles is surjective. The main tool in what follows is the Proposition 5.3. We will consider a very special class of varieties. Indeed, given any ample line bundle L on a variety of this family, then H 0 (Z, L) is generated as an O Z (Z)-module by the sections which do not vanish on a suitable divisor.

Proposition 5.4 Let Z n be the open toric variety obtained from A l through the sequence of blow-ups along the irreducible stable subvarieties associated respectively to σ(e 1 , ..., e l ), σ(e 1 , ..., e l-1 , ( l-1 i=1 e i ) + e l ), σ(e 1 , ..., e l-1 , 2( l-1 i=1 e i ) + e l ),...,σ(e 1 , ..., e l-1 , i( l-1 i=1 e i ) + e l ),...,σ(e 1 , ..., e l-1 , (n -1)( l-1 i=1 e i ) + e l ). Let L h and L k be any two line bundles generated by global sections on Z n , then the product of sections m h,k is surjective.

Proof. We have already considered the case n = 1 in Proposition 5.1, so we can suppose n ≥ 2. Up to changing the linearizations of the line bundles we can suppose that h(e j ) = k(e j ) = 0 for each j. Observe that, if (Q h ∩M )+(Q k ∩M ) contains a weight p, then it contains any weight p + a i f i where the a i are positive integers. So we can consider only the "minimal" weights.

Lemma 5.1 Let p be any weight in Q h+k ∩ M and suppose that there is not a weight p in Q h+k ∩ M such that p ∈ p + σ(f 1 , ..., f l ). Then there is a cone τ ∈ ∆(1) such that p( (τ )) = (h + k)( (τ )).

Proof. The weight p -f l does not belong to Q h+k , thus there is an index i

such that (p -f l )(i( l-1 i=1 e i ) + e l ) < (h + k)(i( l-1 i=1 e i ) + e l ), so p(i( l-1 i=1 e i ) + e l ) = (h + k)(i( l-1 i=1 e i ) + e l ).
Hence it is sufficient to prove the surjectivity of the product of sections of the restrictions of L h and L k to the divisors Z n i associated to σ(i( l-1 i=j e j ) + e l ) with i = 0, ..., n. Observe that Z 0 is the blow-up of A l-1 in the stable point; Z n n is the projective space of dimension l -1 while the other Z n i are isomorphic to the blow-up of Z n n in a stable point (associated to a cone σ( e 1 , ..., e l-1 )). Since Z n 1 dominates Z n n it is sufficient to study the product of sections of any two line bundles generated by global sections on Z n 1 . We will proceed in a similar way to the proof of Proposition 5.1. Lemma 5.2 Let L h and L k be any two line bundles on Z n 1 generated by global sections. Then the multiplication of sections is surjective.

Proof. We can suppose that h ( e i ) = k ( e i ) = 0 for each i. In the following we identify Z l-1 with l-1 i=1 Z e i . Given any point m = (z 1 , ..., z l-1 ) in Q h +k with integral coordinates, there are m1 = (x 1 , ..., x l-1 ) ∈ Q h and m2 = (y 1 , ..., y l-1 ) ∈ Q k such that m1 + m2 = m. Now we want to simplify the notations. Let

i = -[([x i ]-x i )] and set m 1 = ([x 1 ]+ 1 , ..., [x r ]+ r , [x r+1 ], ..., [x l-1 ]) and m 2 = ([y 1 ], ..., [y r ], [y r+1 ] + r+1 , ..., [y l-1 ] + l-1 ) for a suitable r. Let t = l-1 i=1 i , r = r i=1 i , [x] = l-1 i=1 [x i ], x = l-1 i=1 x i = m 1 ( l-1 i=1 e i ), [y] = l-1 i=1 [y i ], y = l-1 i=1 y i = m 2 ( l-1 i=1 e i ), a = h ( l-1 i=1 e i ), b = -h (- l-1 i=1 e i ), c = k ( l-1 i=1 e i ) and d = -k (- l-1 i=1 e i ). We have m 1 ( l-1 i=1 e i ) = [x] + r, m 2 ( l-1 i=1 e i ) = [y] + t -r and a + c ≤ [x] + [y] + t = x + y ≤ b + d.
Notice that r takes all the values between 0 and t when r varies between 0 and l -1.

1 The varieties Z n have the following remarkable property: the "minimal" weights of (Z n , h + k) come from semi-invariant sections that do not vanish on a suitable divisor. This property allows us to prove the theorem without assuming the ampleness of both L h and L k . Unfortunately this property does not hold if we consider varieties whose fans are a little less symmetric. Notice that the fans of the varieties Z n are invariant for any automorphism of χ(S) * which permutes the vectors of the basis and fixes e l . In the following we define a class of varieties without such symmetry and obtained by blow-up from varieties of the previous family.

) If t + [x] ≤ b we define r as min{[y] + t -c, t}. If [y] ≥ c then r = t, so b ≥ [x] + t = [x] + r ≥ x ≥ a and c ≤ [y] ≤ y ≤ d. If c ≥ [y] then b ≥ [x] +t ≥ [x] +r = [x] +[y] +t-c ≥ a+c-c =
Theorem 5.2 Let Z n be the blow-up of Z n along the stable subvariety associated to σ( l j=1 e j , e 2 , ..., e l ). Let L h be any ample line bundles on Z n , then the product of sections m h,h is surjective.

Proof. We introduce some notations to simplify the counts: w := e 1 + 2 l j=2 e j , v i := i( l-1 i=1 e i )+e l , a i = h(v i ) and b = h(w) for each i. Moreover we suppose that h(e j ) = 0 for each j. In the proof we allow L h to be the pullback of an ample linearized line bundle on Z n , i.e. h(w) = h(v 1 ). We want to prove the proposition by induction on h(w) and on the dimension of Z n . We can suppose that h(w) > h(v 1 ) because of the previous proposition. We want to prove that Q 2h ∩χ(S) = Q h ∩χ(S)+Q h ∩χ(S) in a similar way to the previous proposition. As before, we have Q h ∩ χ(S) + Q h ∩ χ(S) ⊃ Q h ∩ χ(S) + Q h ∩ χ(S) + Z ≥0 f i . Hence we can suppose that m -f l does not belong to Q 2h ∩ χ(S). Thus either there is an i such that m(v i ) = a i or m(w) -2h(w) ∈ {0, 1}.

Either we have to study a divisor or m(w) = 2h(w)+1. One can easily verify that the only divisor that we do not have already considered is Z n σ(v1) . This one can be studied in a very similar way to the divisor Z n σ(v1) of Z n , so we leave the details to the readers. Thus we can suppose that m(w) = 2b + 1. The strictly convexity of h on the fan ∆ implies the following conditions: a i + (i -1)b < (2i -1)a 1 ∀i, b > a 1 > 0, 2a 1 > b and ia 1 > a i .

Let ∆ be the fan of Z n , let ∆ be the fan of Z n and let h be the ∆-linear function such that h (e i ) = 0, h (v i ) = h(v i ) and h (w) = h(w) -1. One can easily prove that h is convex. Moreover h is strictly convex either on ∆ or on ∆ .

By induction we can suppose that m h ,h is surjective, so we can suppose that there are two points m 1 = (x 1 , ..., x l ) ∈ Q h ∩ χ(S) and m 2 = (y 1 , ..., y l ) ∈ Q h ∩ χ(S) such that m 1 + m 2 = m. We can suppose that m 2 does not belong to Q h , thus m 2 (w) = b -1 and m 1 (w) = b + 2.

We can suppose that m 1 -f l ∈ / Q h because m 2 + f l ∈ Q h . Thus there is i such that m 1 (v i ) = a i . Moreover we can suppose that (m 1 +f 1 -f j , m 2 -f 1 +f j ) does not belong to Q h ×Q h for any j = 2, ..., l -1, so x j = 0 or y 1 = 0. If y 1 = 0 then 2a 1 -1 ≥ m 2 (w) = 2m 2 (v 1 ) ≥ 2a 1 , a contradiction. Hence y 1 = 0 and x j = 0 for each j = 2, ..., l -1. If there is i > 1 such that m 1 (v i ) = ix 1 + x l = a i , then (2i -1)a 1 ≤ (2i -1)(x 1 + x l ) = m 1 (v i ) + (i -1)m 1 (w) = = a i + (i -1)(b + 2) ≤ (2i -1)a 1 + 2i -2, so 0 ≤ (2i -1)(x 1 + x l -a 1 ) ≤ 2i -2. We have x 1 + x l = a 1 because x 1 + x l -a 1 is an integer. We have showed that m 1 (v 1 ) = x 1 + x l = a 1 or m 1 (e l ) = x l = 0. In the last case we have x 2 = ... = x l = 0 and x 1 = b + 2. We can suppose that (m 1 -f 1 , m 2 + f 1 ) does not belong to Q h × Q h , so there is s > 0 such that m 1 (v s ) -a s < s. Observe that m 1 (v s ) = sx 1 = sb + 2s, so a s ≤ sb = m 1 (v s ) -2s < a s -s < a s , a contradiction.

Finally suppose that x j = 0 for each j = 2, ..., l -1, x 1 + x l = a 1 and x 1 + 2x l = b + 2, so x 1 = 2a 1 -b -2 and x l = b + 2 -a 1 . We can suppose that (m 1 + f 1 -f l , m 2 -f 1 + f l ) does not belong to Q h × Q h , so there is i > 1 such that ε := m 2 (v i ) -a i < i. We have a i ≤ m 1 (v i ) = (2i -1)a 1 -(i -1)b -2(i -1), so (2i -1)a 1 ≥ a i + (i -1)b + 2(i -1). Finally (2i -1)a 1 ≤ (2i -1)( y j ) ≤ m 2 (v i ) + (i -1)m 2 = (i -1)(b -1) + a i + ε ≤ (2i -1)a 1 -3(i -1) + ε, so 3(i -1) ≤ ε ≤ i -1, a contradiction.

  k is surjective. It is sufficient to show that the image of M h,k contains a basis of semi-invariant sections. If h and k are linear then M h,k is surjective by the Theorem 0.1. In general, given ν ∈ Π(Y, h + k) there are λ ∈ Π(Z c , h) and µ ∈ Π(Z c , k) such that ν = λ+µ. Moreover there are elements w 1 and w 2 of W L,θ such that w 1 • λ and w 2 • µ are dominant weights. Observe that ν ≥ w 1 •λ+w 2 •µ on |∆|. Moreover w 1 •λ ≥ h and w 2 •µ ≥ k because h c and k c are convex and invariant for the action of W L,θ . Thus s

  because the a i and the c i are integers. If ([y 1 ], ..., [y l ]) belongs to Q k , then we define m 1 = ([x 1 ] + 1 , ..., [x l ] + l ) and m 2 = ([y 1 ], ..., [y l ]). In the same way, if ([x 1 ], ..., [x l ]) belongs to Q h , then we define m 1 = ([x 1 ], ..., [x l ]) and m 2 = ([y 1 ] + 1 , ..., [y l ] + l ). Thus we can suppose that r i=1 [x i ] ≤ b and r i=1 [y i ] ≤ d. We define m 1 = ([x 1 ] + 1 , ..., [x s ] + s , [x s+1 ], ..., [x l ]) for an index s less than r and such that h(e 1 + ... + e r ) = r i=1 [x i ] + s i=1 i = m 1 (e 1 + ... + e r ). Finally set m 2 = m -m 1 and notice that m 2 belongs to Q k since (m -m 1 )(e 1 + ... + e r ) ≥ (h + k)(e 1 + ... + e r ) -h(e 1 + ... + e r ).

  a and c = [y] +t-([y] +t-c) = [y] + t -r ≤ d.2) Suppose now that[y] + [x] + t ≤ b + c. If c -[y] is positive then we define r = t + [y] -c, so t -r = c -[y] (t + [y] ≥ y ≥ c so r ≥ 0). In this case c = [y] + t -r ≤ d and a ≤ [x] + [y] + t -c = [x] + r ≤ b. If c -[y] is negative then we define r = t, so c ≤ [y] = [y] + t -r ≤ d and a ≤ x ≤ [x] + t = [x] + r ≤ c + b -[y] ≤ b.3) Finally suppose that t + [x] > b and [y] + [x] + t > b + c. We define r = b -[x] , so a ≤ [x] + r = b and d ≥ [y] + [x] + t -b = [y] + t -r ≥ c.