Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/~litvinov/tropical07/volume1.pdf Äàòà èçìåíåíèÿ: Wed Aug 15 10:52:24 2007 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 13:56:54 2012 Êîäèðîâêà: IBM-866 Ïîèñêîâûå ñëîâà: narrow band filter

Independent University of Moscow FrenchíRussian Laboratory "J.-V. Poncelet"

International Workshop

IDEMPOTENT AND TROPICAL MATHEMATICS AND PROBLEMS OF MATHEMATICAL PHYSICS

G.L. Litvinov, V.P. Maslov, S.N. Sergeev (Eds.)

Organizing committee: G.L. Litvinov, V.P. Maslov, S.N. Sergeev, A.N. Sobolevski i Web-site: http://www.mccme.ru/tropical07 E-mail: tropical07@gmail.com

Moscow, August 25í30, 2007

Volume I

Moscow, 2007


Litvinov G.L., Maslov V.P., Sergeev S.N. (Eds.) Idempotent and tropical mathematics and problems of mathematical physics (Vol. I) í M.: 2007 í 104 pages This volume contains the proceedings of an International Workshop on Idempotent and Tropical Mathematics and Problems of Mathematical Physics, held at the Independent University of Moscow, Russia, on August 25-30, 2007. 2000 Mathematics Subject Classification: 00B10, 81Q20, 06F07, 35Q99, 49L90, 46S99, 81S99, 52B20, 52A41, 14P99

c 2007 by the Independent University of Moscow. All rights reserved.


CONTENTS

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Representation of stationary solutions of Hamilton-JacobiBellman equations: a max-plus point of view

Marianne Akian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
On the assignment problem for a countable state space

M. Akian, S. Gaubert, and V.N. Kolokoltsov . . . . . . . . . . . . . . . . . . . . . . . . . 12
Dequantization of coadjoint orbits: the case of exponential Lie groups

Ali Baklouti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Quantum Pontryagin principle and quantum Hamilton-JacobiBellman equation: a max-plus point of view

Viacheslav P. Belavkin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
è Tropical Plucker functions

V.I. Danilov, A.V. Karzanov, and G.A. Koshevoy . . . . . . . . . . . . . . . . . . . . 29
Degree one homogeneous minplus dynamic systems and traffic applications: Part I

N. Farhi, M. Goursat, and J.-P. Quadrat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Degree one homogeneous minplus dynamic systems and traffic applications: Part II

N. Farhi, M. Goursat, and J.-P. Quadrat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Max-plus cones and semimodules

F. Faye, M. Thiam, L. Truffet, E. Wagneur . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Duality of cluster varieties

V.V. Fock and A.B. Goncharov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
From max-plus algebra to non-linear Perron-Frobenius theory: an approach to zero-sum repeated games

St‡ ephane Gaubert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60


Cyclic projectors and separation theorems in idempotent semimodules

S. Gaubert and S. Sergeev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Pseudo-weak convergence of the random sets defined by a pseudo integral based on non-additive measure

T. Grbi‡ and E. Pap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 c
The stationary phase method and large deviations

Oleg V. Gulinsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Quantization with a deformed trace

Dmitry Gurevich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Transformations preserving matrix invariants over semirings

Alexander E. Guterman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Tropical geometry and enumeration of real rational curves

I. Itenberg, V. Kharlamov, and E. Shustin . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Abstract convexity and cone-vexing abstractions

Semen S. Kutateladze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Interval analysis for algorithms of idempotent and tropical mathematics

Grigory L. Litvinov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Dequantization procedures related to the Maslov dequantization

G.L. Litvinov and G.B. Shpiz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99


PREFACE Idempotent mathematics is a new branch of mathematical sciences, rapidly developing and gaining popularity over the last decade. It is closely related to mathematical physics. Tropical mathematics is a very important part of idempotent mathematics. The literature on the sub ject is vast and includes numerous books and an all but innumerable body of journal papers. An important stage of development of the sub ject was presented in the book Idempotency edited by J. Gunawardena (Publ. of the Newton Institute, vol 11, Cambridge University Press, Cambridge, 1998). This book arose out of the well-known international workshop that was held in Bristol, England, in October 1994. The next stage of development of idempotent and tropical mathematics was presented in the book Idempotent Mathematics and Mathematical Physics edited by G.L. Litvinov and V.P. Maslov (Contemporary Mathematics, vol. 377, American Mathematical Society, Providence, Rhode Island, 2005). The book arose out of the international workshop that was held in Vienna, Austria, in February 2003. The present volumes contain materials presented for the international workshop Idempotent and Tropical Mathematics and Problems of Mathematical Physics (Moscow, Russia, August 25-30, 2007). It is our pleasure to thank the Independent University of Moscow and the Poncelet Laboratory of this university as well as the Russian Fund for Basic Research and CNRS (France) for their important support. We are grateful to a number of colleagues, especially to L. Kryukova and M. Tsfasman of the Poncelet Laboratory, T. Korobkova and Yu. Torkhov of the Independent University of Moscow, and A. Sobolevski of the Moscow i State University, for their great help. We thank all the authors of the volumes and members of our "idempotent/max-plus/tropical community" for their contributions, help, and useful contacts. The editors Moscow, August 2007


6

Marianne Akian

Representation of stationary solutions of Hamilton-Jacobi-Bellman equations: a max-plus p oint of view1 Marianne Akian
This talk gathers two recent works: the first one is a joint work with S. Gaubert and C. Walsh first presented in [5], the second one is a joint work with B. David and S. Gaubert presented in [1]. 1. Nonlinear eigenfunctions and stationary solutions of Hamilton-Jacobi-Bellman equations Let us consider a diffusion control model on a subset X of Rn , that is a stochastic process xt with values in X satisfying the stochastic differential equation (1.1) dxt = g (xt , ut ) dt + (xt , ut ) dbt where (bt ) is a p-dimensional brownian motion, u := (ut )t0 (the control) is a stochastic process with values in a subset U of Rp and adapted to the filtration of (bt ), and the drift g : X ½ U Rn and the standard deviation : X ½ U Mn,p (R) are given. The stochastic control problem with horizon T consists in maximizing over all the controls u the quantity
T

(1.2)

E
0

L(xs , us ) ds + (xT ) ,

where xt is the solution of (1.1) with initial condition x0 = x, L is the Lagrangian and is a final reward. Let us denote by v T (x) the value of this optimization problem, and by S T the map which associates v T to . The familly of operators {S t }t0 is the (non linear) evolution semigroup associated to the control problem. Moreover, each operator S t is additively homogeneous (S t (² + ) = ² + S t (), where (² + )(x) = ² + (x)), and order preserving, thus it is nonexpansive for the sup-norm. If the control problem is purely deterministic then the operators S t are max-plus linear, that is S t ( ) = S t () S t ( ). In general, the operators S t are convex, which means that, for all t 0 and x X , the map S t ()(x) is convex on RX . We say that is an additive eigenvalue of the evolution semigroup if there exists a function : X R such that for all t 0, S t = t + . The
1The present work was partially supp orted by the RFBR/CNRS grant 05-01-02807.


Stationary solutions of HJB equations

7

function is called an additive eigenfunction of the evolution semigroup associated to . If X is compact and we restrict ourselves to continuous eigenfunctions, the semigroup has at most one eigenvalue. Moreover, under some regularity assumptions on L, g , , the eigenfunctions are exactly the viscosity solutions of the ergodic Hamilton-Jacobi-Bellman equation (1.3) - H (x, D(x), D2 (x)) = 0, x X,

where the Hamiltonian of the problem is given by 1 (1.4) H (x, p, A) = max( tr( (x, u) (x, u)T A) + p, g (x, u) + L(x, u)). uU 2 In that case, is the maximal mean reward by unit of time (the ergodic reward). Given an eigenvalue of (S t )t0 , we are interested in characterizing the set E of associated eigenfunctions, or of solutions of (1.3). 2. Related results In the particular deterministic case ( 0), the discrete-time analogue of this problem consists in the characterization of eigenvectors of max-plus linear operators, which has received a considerable amount of attention, see for instance [7, 8, 16, 4, 3]. In the finite dimensional setting, eigenvectors are max-plus linear combinations of extremal generators which are themselves in bijection with the "critical classes" (critical classes can be seen as the max-plus analogue of recurrent classes). The deterministic continuous time problem itself has been studied by Maslov, Kolokoltsov, Samborskii and other members of the "idempotent analysis" school [18, 19], and by Rouy and Tourin [20] in some special cases. More recently, it has been studied as a part of the "weak KAM" theory developped by Fathi [14, 13, 12] and Fathi and Siconolfi [15]. In this setting, it is shown that when X is a Riemannian manifold and the Lagrangian has smoothness and strict-convexity properties, an eigenfunction is uniquely determined by its restriction to the "pro jected Aubry set". This set can be thought of as a continuous analogue of the set of "critical states" of the finite dimensional max-plus spectral theory. The case of a non-compact state space X has been studied in different settings by Contreras [11], and by Ishii and Mitake [17]. In Section 3, we present briefly the results of [5], where we showed that general representation results hold in the continuous-time setting, without any regularity assumption on the Lagrangian. These results were inspired


8

Marianne Akian

by the discrete-time theory developped in [3] and rely on a compactification of the state space X , which is the max-plus analogue of the Martin compactification in potential theory, and is similar to the compactification of metric spaces by horofunctions (generalised Busemann functions). It is natural to ask whether an analogue of the weak KAM theory can be developped for stochastic control problems. Such an analogue does exist in the simpler finite state space and discrete time case. Indeed, it is shown in [2] that the additive eigenvectors are determined by their restriction to a subset of "critical states" obtained by taking exactly one element in each "critical class". Here critical states are defined in terms of subdifferentials, and can be interpreted as follows: a state is critical if there is an optimal stationary randomised strategy for which it is recurrent, and two critical states are in the same critical class if they are in the same recurrence class for an optimal stationary randomised strategy. In the continuous time stochastic case, characterization results were obtained in the uniformly elliptic case and under various settings, by Bensoussan [10], Akian, Sulem and Taksar [6], and Barles and Da Lio [9]: the eigenfunction is then unique up to an additive constant. In Section 4, we present briefly the results of [1] giving a description of the additive eigenspace similar to the one of [2], in the simplest degenerate case in which there is only a finite number of "singular points" x1 , . . . , xk playing the role of critical states and classes. In the deterministic case similar results were obtained in [20, 18]. 3. Hamilton-Jacobi equations on non-compact spaces In [5], we consider general time continuous semigroups (S t )t0 of maxX X plus linear operators with kernel. We assume that S t : R R can be t t written as S g (x) = supyX (S (x, y ) + g (y )). for some function (x, y ) S t (x, y ) R. This includes the case of the evolution semigroup associated to the deterministic optimal control problem with dynamics (1.1) with 0 and criteria (1.2). Without loss of generality, we assume that = 0, in which case an eigenfunction is called a harmonic function. Harmonic functions may take the - value, so that the set E0 of harmonic functions is a semimodule over the max-plus semiring Rmax (recall that this is the set R {-} endowed with max as addition and + as multiplication). We need the following assumptions : (A1) S (x, y ) := supt0 S t (x, y ) is finite for all x and y in X . (A2) For all t 0 and x, y X , S t (x, y ) = sup {I ( )}, where the supremum is taken over all paths : [0, t] X from x to y , and


Stationary solutions of HJB equations where the reward I ( ) is defined as
n-1

9

I ( ) :=

t0 ,...,tn

inf

S
i=0

ti+1 -ti

( (ti ), (t

i+1

)),

with the infimum taken over all finite increasing sequences (ti ), i {0, . . . , n}, in [0, t] with t0 = 0 and tn = t. The (max-plus) Martin kernel of the semigroup (S t )t0 with respect to the basepoint b X is defined by: K (x, y ) = S (x, y ) - S (b, y ) . The (max-plus) Martin space M of (S t )t0 is the closure in the topology of pointwise convergence of the set K := {K (§, y ) | y X } RX . Any element of M is super-harmonic, which means that it satisfies S t . For all functions : X Rmax and for all M , we set: ² ( ) := lim sup (S (b, x) + (x)) ,
K (§,x)

and if M we set: H ( , ) := ² ( ). The kernel H extends the kernel S from X ½ X to M ½ M , up to a normalization, since H (K (§, x), K (§, y )) = S (b, x) + S (x, y ) - S (b, y ) . The minimal boundary M m of (S t )t0 is the set of elements of M that are harmonic and satisfy H ( , ) = 0. Theorem 3.1 ([5, Theorem 3.11]). Under Assumptions (A1)í(A2), a function h : X Rmax is harmonic if and only if it can be written (3.1) h = sup ( (w) + w) ,
wM
m

where is some upper semicontinuous function from M over, ²h is the greatest satisfying this equation.

m

to R

max

. More-

Here, ²h plays the role of the spectral measure in the Martin representation theorem. In [5], we also show that the elements of the minimal Martin boundary are precisely the extremal generators of E0 normalized in such a way that w(b) = 0, and that they are in correspondance with almost-geodesics. 4. A degenerate Hamilton-Jacobi-Bellman equation on the torus In [1], we study a simple degenerate stochastic control model on the torus Tn = Rn /Zn . We consider the stochastic model given by (1.1) with the criteria (1.2) on the set X = Tn . We need the following assumptions:


10 (A1) (A2) (A3) (A4)

Marianne Akian

L is C 2 on Tn ½ U . g and are Lipschitz continuous on Tn ½ U . L takes non-positive values. There exists k distinct points x1 , . . . , xk of Tn such that: (a) i = 1, . . . , k , ui U such that g (xi , ui ) = 0, L(xi , ui ) = 0 and (xi , ui ) = 0. (b) x Tn {x1 , . . . , xk }, u U, at least one of the following properties holds: (i) L(x, u) < 0 or (ii) (x, u) (x, u)T is a positive definite matrix. (A5) For all i = 1, . . . , k , there exists u(i) : Tn U Lipschitz continuous satisfying u(i) (xi ) = ui , and a continuous function W (i) : Tn R which vanishes on xi and is positive elsewhere, and which is a viscosity solution of 1 - tr( (x, u(i) (x)) (x, u(i) (x))T D2 W (i) (x)) (4.1) 2 - g (x, u(i) (x)), W (i) (x) + L(x, u(i) (x)) 0, x Tn . Assumptions (A3)í(A5) ensure that the point xi is stabilized in probability by the control u(i) . Since X is compact, the evolution semigroup has a unique eigenvalue, and the previous assumptions imply that this eigenvalue is 0. The following result shows in particular that the set {x1 , . . . , xk } plays a role analogous to the pro jected Aubry set. Theorem 4.1 ([1]). Under Assumptions (A1)í(A5), the map E0 Rk , v (v (x1 ), ..., v (xk )) is a sup-norm isometry, whose image is a nonempty closed convex subset C of Rk , that is invariant by al l the translations (v1 , . . . , vk ) (² + v1 , . . . , ² + vk ) (² R). A more precise description of the convex set C is given in [1]. Bibliography
[1] M. Akian, B. David, and S. Gaubert, Un th‡ ` eoreme de repr‡ esentation des solutions de viscosit‡ d'une ‡ e equation d'Hamilton-Jacobi-Bel lman ergodique d‡ ‡ ‡ ‡ sur le egeneree tore, Preprint, 2007. [2] M. Akian and S. Gaub ert, Spectral theorem for convex monotone homogeneous maps, and ergodic control, Nonlinear Analysis. Theory, Methods & Applications 52 (2003), no. 2, 637í679. [3] M. Akian, S. Gaubert, and C. Walsh, The max-plus Martin boundary, D‡ 2004, ec. arXiv:math.MG/0412408. [4] , Discrete max-plus spectral theory, Idempotent Mathematics and Mathematical Physics (G. L. Litvinov and V. P. Maslov, eds.), Contemporary Mathematics, American Mathematical Society, 2005, Also ESI Preprint 1485, arXiv:math.SP/0405225, pp. 19í51.


Stationary solutions of HJB equations
[5]

11

[6]

[7] [8] [9]

[10]

[11] [12] [13] [14] [15] [16] [17] [18]

[19] [20]

, How to find horizon-independent optimal strategies leading off to infinity: a max-plus approach, Pro c. of the 45th IEEE Conference on Decision and Control (CDC'06) (San Diego), 2006. M. Akian, A. Sulem, and M. Taksar, Dynamic optimization of long-term growth rate for a portfolio with transaction costs and logarithmic utility, Math. Finance 11 (2001), no. 2, 153í188. F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and linearity : an algebra for discrete events systems, Wiley, New-York, 1992. R. B. Bapat, A max version of the Perron-Frobenius theorem, Linear Algebra Appl. 275/276 (1998), 3í18. G. Barles and F. Da Lio, On the boundary ergodic problem for ful ly nonlinear equations in bounded domains with general nonlinear Neumann boundary conditions, Ann. Inst. H. Poincar‡ Anal. Non Lin‡ e eaire 22 (2005), no. 5, 521í541. A. Bensoussan, Perturbation methods in optimal control, Wiley/Gauthier-Villars Series in Mo dern Applied Mathematics, John Wiley & Sons Ltd., Chichester, 1988, Translated from the French by C. Tomson. G. Contreras, Action potential and weak KAM solutions, Calc. Var. Partial Differential Equations 13 (2001), no. 4, 427í458. A. Fathi, Weak KAM theorem in lagrangian dynamics, Cambridge University Press, to app ear. , Solutions KAM faibles conjugu‡ et barri` es de Peierls, C. R. Acad. Sci. ees er Paris S‡ I Math. 325 (1997), no. 6, 649í652. er. , Th‡ ` eoreme KAM faible et th‡orie de Mather sur les syst` e emes lagrangiens, C. R. Acad. Sci. Paris S‡ I Math. 324 (1997), no. 9, 1043í1046. er. A. Fathi and A. Siconolfi, Existence of C 1 critical subsolutions of the HamiltonJacobi equation, Invent. Math. 155 (2004), no. 2, 363í388. M. Gondran and M. Minoux, Graphes, dioè ides et semi-anneaux, TEC & DOC, Paris, 2002. H. Ishii and H. Mitake, Representation formulas for solutions of Hamilton-Jacobi equations with convex Hamiltonians, Indiana Univ. Math. J. (2007), to app ear. V. N. Kolokoltsov and V. P. Maslov, Idempotent analysis and its applications, Mathematics and its Applications, vol. 401, Kluwer Academic Publishers Group, Dordrecht, 1997. V. P. Maslov and S. N. Samb orski Idempotent analysis, Advances In Soviet Mathi, ematics, vol. 13, Amer. Math. Soc., Providence, 1992. E. Rouy and A. Tourin, A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal. 29 (1992), no. 3, 867í884.


12

M. Akian, S. Gaubert, V.N. Kolokoltsov

On the assignment problem for a countable state space1 M. Akian, S. Gaubert, and V.N. Kolokoltsov
1. Intro duction and formulation of the results. Our main results are formulated below as Theorems 1.1 - 1.3. The first two theorems are proved in Section 2. A proof of Theorem 1.3 will be given elsewhere. Section 3 contains the algebraic interpretation of our results and methods. Let X be either the set of natural numbers N or that of all integer numbers Z. Further we work with infinite matrices B = (bij ), i, j X that will always have entries in R {-} and satisfy the following condition: (C) For any i there is a j such that bij = -, for any j there is an i such that bij = -, and bij - as |i - j | . Any such matrix B defines the mapping B from the space of functions bounded below on X to the set RX of all real valued functions on X , by the formula (1.1)
T

(B f )i = sup{bij - fj }
j

By B we shall denote the transpose matrix of B and the corresponding operator (1.2) (B T g )j = sup{bij - gi }.
i T

A crucial fact about B is that the pair (B , B T ) defines a Galois connection in RX , which means in particular (see [2]) that B T is a generalized inverse to B in the sense that if the equation B f = g with a given g RX ~ has a solution f RX , then necessarily f = B T g is also a solution of this equation. The infinite dimensional theory depends crucially on the class of functions, in which the solutions to the equation B f = g are sought, and on the corresponding definitions of solutions to the assignment problem. Let l ; l1 ; and l0 denote respectively the spaces of functions s = (si ), i X on X such that supi |si | < ; supn |i|n |si | < ; and the (finite) limit lim|n| sn exists. Let l = l(X ) be any of these spaces. Definition 1.1. A matrix B (satisfying (C)) will be called l-strongly regular if there exists a function g l such that (i) f = B T l, (ii) f is the unique solution in RX of the equation B f = g and (iii) g is the unique
1

Partially supported by the joint RFBR/CNRS grant 05-01-02807.


On the assignment problem

13

solution in RX of the equation f = B T g . In this case g (respectively, f ) is said to belong to the l-simple image of B (respectively, of B T ). Of course, it follows from this definition that B is l-strongly regular if and only if B T is strongly regular. Remark 1.1. One can show (though this is not obvious) that in the case of finite X our definition coincides with the standard definition of strong regularity given by P. Butkovi see [5]. In fact, we added a crucial c, additional condition in our definition, which turns out to be automatically fulfilled for finite, but not for infinite X . Definition 1.2. For any two bijections F, G : X X , we define the distance between them by (F, G) = sup |F (n) - G(n)|.
n

The binary relation F G iff (F, G) < is clearly an equivalence relation on the set of bijections defining the decomposition of this set into non-intersecting classes. We shall say that F is local ly bounded if it is equivalent to the identity map. Definition 1.3. A bijection F : X X is called a (global) solution or a strong solution respectively to the assignment problem for a matrix B if (1.3) lim inf
n |i|n

(b

iF (i)

-b

iG(i)

)0

for any other bijection G : X X or if (1.4) lim inf
n |i|n

(b

iF (i)

- biG(i) ) > 0,

respectively. We say that this solution is a local ly bounded l-solution, if F is locally bounded and the "solution sequence" biF (i) belongs to l(X ). We say that F is a local solution if (1.3) (or (1.4) respectively) holds for all G such that the distance between F and G is finite. If a strong solution exists, then the solution to the assignment problem is obviously unique. Definition 1.4. A matrix B is called normal (respectively, strongly normal) if all its non-diagonal entries are non-positive (respectively, negative) and bii = 0 for all i.


14

M. Akian, S. Gaubert, V.N. Kolokoltsov

This definition is literally the same as the usual finite- dimensional one (see [4]). The normal (respectively, strongly normal) matrices present a class of examples, where the identity map is an obvious locally bounded l1 -solution (respectively, unique solution) to the assignment problem. As our first result will show, this class of matrices presents natural "normal forms" for strongly regular matrices. Definition 1.5. Matrices B and C are called (local ly bounded) lsimilar if there exist two locally bounded bijections H : X X , K : X X and two vectors g and f from l(X ) such that (1.5) cij = bH
(i)K (j )

- i - j .

This is also a standard definition in the case of finite X (see e.g. [4] and Section 4 below for an intuitive interpretation). The importance of this notion is basically due to the following result. Proposition 1.1. (i) Conditions (C) and l-strong regularity for matrices with entries in R {-} are al l invariant under l-similarity. (ii) The property to have an l1 - solution (in particular local ly bounded or strong) to the assignment problem for matrices with entries in R {-} is invariant under l1 -similarity. (iii) The property to have a local ly bounded local l0 - solution (in particular strong) to the assignment problem for matrices with entries in R {-} is invariant under l0 -similarity. Proof. (i) The invariance of condition (C) is obvious. The invariance of l-strong regularity follows from the observation that if C and B are related by (1.5) then the equation g = C f is equivalent to the equation (g + )(H
-1

) = B ((f + )(K

-1

)).

(ii) Let a bijection F be a solution to the assignment problem of a matrix C . Notice that (1.6) (ciF (i) - ciG(i) ) = (bH (i)K F (i) - bH (i)K G(i) ) + (G(i) - F (i) ).
|i|n |i|n |i|n

Clearly, the last sum on the r.h.s. tends to zero as n whenever l1 . Hence, F is an l1 -solution (respectively, a strong l1 -solution) to the assignment problem for the matrix C if and only if the mapping K F H -1 is an l1 -solution (respectively, a strong l1 -solution) to the assignment problem for the matrix B . (iii) By the previous discussion, it suffices to show that the sequence bn = (G
|i|
-

F (i)

)


On the assignment problem tends to zero as n if and far from the identity map. To condition, there exists a natural {F (i) : |i| < n} and {G(i) : |i| < Hence bn =
G(i1 )

15 only if both F and G are not infinitely this end, observe that due to the last number p such that for every n the sets n} both contain the set {i : |i| < n - p}. - - ... - G ,

+ G

(i2 )

+ ... +

G(ip )

F (j1 )

(jp )

where ik (respectively jk ) are such that |G(ik )| > n - p (respectively |F (jk )| > n - p). We recall now that the function n has a finite limit as n , which immediately implies that bn tends to zero (the statement that we wanted to prove). This was the crucial application of this assumption, which seems to be the weakest possible to provide a link between the solutions to the assignment problem for similar matrices. Theorem 1.1. A matrix B (satisfying (C)) is l-strongly regular if and only if it is l(X ) similar to a strongly normal matrix. It is of course interesting to know what can be said about the assignment problem for a regular matrix itself (not just for some of its similar matrices). In the analysis of this question (as well as the inverse one), an important role is played by the following functions describing in some sense the size of the problem. Namely, let F be a (possibly local) solution to the assignment problem of a matrix B . Let "the optimal distance" between the points i, j be defined as (1.7) ~ij = sup[b b +b
i
n-1

iF (i1 )

- bi
n

1

F (i1 )

+b

i1 F (i2 )

-b

i2 F (i2 )

+ ...

F (in )

- bi

F (in )

+b

in F ( j )

-b

j F (j )

],

where sup is taken over all n = 1, 2, ... and all collections i1 , i2 , ..., in of points from X , and "the potential" and "the inverse potential" as the functions on X are given respectively by (1.8) i = sup ~ij , b
j

~ b i = sup ~j i .
j

The following simple properties of these functions are crucial: ~ (1) the values of ~, and do no change if one takes the sup b over families i1 , ..., in with pairwise disjoint points (in fact, cycle gives a non-positive contribution due the assumption F is a solution to the assignment problem); ~ (2) ~ii , i and i are nonnegative for all i (in fact, take n = 1 b i1 = i in (1.7));

only any that and


16

M. Akian, S. Gaubert, V.N. Kolokoltsov ~ (3) the functions and - satisfy the equation

(1.9)

fi = sup[b
j

iF (j )

-b

j F (j )

+ fj ],

i X,

or, equivalently, (1.10) f = B , j = b
F
-1

(j )j

-f

F

-1

j

. i X,

~ (4) the functions and - satisfy the equation (1.11) fi = sup[~ij + fj ], b
j

i X.

~ Observe that if B is normal then ~ij 0 and i = i = 0 for all i, j . b Theorem 1.2. (i) If a matrix B (satisfying (C)) is l0 -strongly regular, then it has a (necessarily unique) local ly bounded local strong l0 -solution to its assignment problem such that (1.12) lim sup ~ij 0, b
i,j

~ and that the potentials and are bounded functions. (ii) If B is l1 strongly regular, then this solution is also a global l1 -solution. To prove the converse to Theorem 1.2, we shall use the following additional technical assumption on a solution to the assignment problem: ~ (B(l(X ))) Either the potential or the inverse potential belong to l(X ). Theorem 1.3. If l is either l0 or l1 and if the assignment problem for a matrix B has a (possibly local) local ly bounded strong l-solution satisfying condition (B(l(X ))), then B is strongly l-regular. We have to indicate an unpleasant small gap between the necessary condition and the sufficient condition: from strong l0 -regularity it follows that the potential belongs to l , but in Theorem 1.3 we assume that l0 (which implies (1.12)). However, this discrepancy vanishes when we consider classes of similar matrices, as the following direct corollary of Theorem 1.1 and 1.3 suggests. Corollary 1.1. Let l(X ) be either l0 or l1 . Then a matrix B is strongly l(X )-regular if and only if it is l(X )-similar to a matrix having a strong solution to the assignment problem satisfying condition (B(l(X ))).


On the assignment problem

17

2. Coverings and sub-differentials. Pro ofs of Theorems 1.1 and 1.2. For the analysis of the equation B f = g (also in a more general setting of uncountable X ), an important role belongs to the notion of (abstract) sub-differentials. Definition 2.1. For a matrix B and f , g RX , the abstract subdifferentials (or B -sub-differentials) are defined as follows (see [2] and references therein) f (j ) = {k X : (B f )k = sup{bkl - fl } = bkj - fj },
l

g (i) = {k X : (B g )k = sup{blk - gl } = bik - gi }.
l

T

T

For a given f the sub-differential is a mapping from X to the set P (X ) of subsets of X . For any such mapping G its inverse mapping G-1 : X P (X ) is naturally defined as G-1 (j ) = {i : j G(i)}. We shall start with the following well known basic property of subdifferentials that we prove here for completeness. Proposition 2.1. If g = B B T g RX , then ( T g )-1 = B T g . Proof. ( T g )-1 (j ) = {i : (B T g )j = sup{blj - gl } = bij - gi },
l

which is the same as gi = bij - (B g )j , or equivalently B (B T g )i = bij - (B T g )j , and which means that i (B T g )(j ). Proposition 2.2. from below. Then B T g T g (i) = for al l i or, j X , is a covering of Suppose that functions g , B T g RX are bounded is a solution to the equation B f = g if and only if equivalently, if the family of the sets ( T g )-1 (j ), X.

T

Proof. This is a direct consequence of a more general Theorem 3.5 from [2], where one only has to observe that the assumption that f = B T g is bounded from below ensures that the set {j : bij - fj } is finite for any i X and R, which is the crucial condition for the applicability of this theorem. Definition 2.2. Let G be a mapping from X to the set of its subsets P (X ) and let the family of subsets {G(j )}j X be a covering of X . An element j X is called essential (with respect to this covering) if i X : i k /
X \j

G(k ).


18

M. Akian, S. Gaubert, V.N. Kolokoltsov

The covering is called minimal if all elements of X are essential. Proposition 2.3. Suppose that functions g , B T g RX are bounded from below. Then B T g is the unique solution of equation B f = g in RX if and only if ( T g )-1 (j ), j X , is a minimal covering of X . Proof. This is again a consequence of a more general Theorem 4.7 from [2]. The key point in proving Theorems 1.1 and 1.2 is contained in the following statement. Proposition 2.4. Suppose that from below, and such that f = B T B f = g , and g is the unique solution exists a local ly bounded bijection F : (2.1) In particular, (2.2) k = F (i) k = i b
iF (i) ( i)

functions g , B T g RX are bounded g is the unique solution of equation to the equation B T g = f . Then there X X such that

j = F (i) f (j ) = {i} T g (i) = {j } j = F (i). -f > bik - fk ,
F (i)

F (i)

biF

- gi > bk

- gk .

Remark 2.1. As one easily checks, the inverse statement holds as well: if a locally bounded bijection F and bounded below functions f , g satisfy (2.1), then f = B T g is the unique solution of the equation B f = g , and g is the unique solution of the equation B T g = f . Proof of Prop. 2.4. Applying Proposition 2.3 to the equation B T g = f one concludes that for all i there exists j such that j ( f )-1 (i), but j ( f )-1 (k ) for any k = i. In other words ( f )(j ) = {i}, which by / Proposition 2.1 means that ( T g )-1 (j ) = {i}. Hence, defining the mapping F : X P (X ) by the formula F (i) = {j : ( f )(j ) = {i}} = {j : ( T g )-1 (j ) = {i}}, one deduces that F (i) = for all i and F is injective in the sense that F (i) F (k ) = whenever i = k . Applying now Proposition 2.3 to the equation B f = g , one finds that for all j there exists i such that ( T g )(i) = {j }. From this, one easily concludes that each set F (i) contains precisely one point and that F is surjective, which finally implies that F is a bijection X X such that (2.1) holds. Let us show that F is bounded. In fact, since B satisfies (C) and f is bounded from below, it follows that for any C > 0 there exists N such that bij - fj < -C whenever |i - j | > N . On the other hand, as g is


On the assignment problem

19

bounded from below, biF (i) - fF (i) = gi is bounded from below, and hence |i - F (i)| < N for large enough N and all i. Proof of Theorem 1.1 . Let F be a bijection constructed in Proposition 2.4. From the equation biF (i) - fF (i) = gi it follows that {biF (i) } l(X ) whenever f , g l(X ). Hence the matrix C with entries cij = b
iF (j )

-f

F (j )

- (b

iF (i)

- fF

(i)

)

is strongly normal and is l-similar to B . Proof of Theorem 1.2 . The existence of required solution follows from Proposition 1.1. This solution is actually given by the bijection ~ F constructed in Proposition 2.4. The boundedness of and follows of course from (1.11). To prove the latter, one observes that according to the second inequality of (2.2) ~ij gi - gj , b and the r.h.s. of this inequality tends to 0 as i, j , since g l0 . 3. Algebraic interpretation A natural algebraic language for the analysis of discrete event systems and optimal control is supplied by the so called idempotent algebra, in particular the (max, +)-algebra (see e.g. [6], [8]). The (max, +)-algebra deals with the semiring R {-} equipped with the binary operations = max and = + and with finite-dimensional semimodules over this semiring. The main impetus to the development of this algebra (and further its infinite-dimensional generalizations, see [8], [9]) was a simple observation that the basic Bellman operator (3.1) (B f )i = sup(bij + fj ),
j

iX

of the optimal control theory is linear in this structure, i.e. B (1 f1 2 f2 = 1 B (f1 ) 2 B (f2 ) for 1 , 2 R{-} and f1 , f2 (R{-})X . (Note that previously we denoted by B f the operator which would now be denoted by B (-f ); this was more convenient for the study of the inversion of B .) In fact the operators of type (3.1) are the most natural (max, +)-linear operators, though they do not exhaust all of them (see e.g. [1], [7], [9] and references therein for classical and recent results on this "kernel type" representations). The introduction of main notions and ob jects studied in this article was motivated by the development of the (max, +)-algebra that supplies a clear


20

M. Akian, S. Gaubert, V.N. Kolokoltsov

intuitive interpretation for them. For instance, the strong regularity turns to be a linear algebraic problem connected with the inversion of matrices (or more generally linear operators having kernel representation). Our notion of similarity is obtained by rewriting the classical algebraic notion of similarity of matrices in (max, +). Next, the solution to the assignment problem sup
F iX

b

iF (i)

= F

iX

b

iF (i)

turns out to be the (max, +) analogue of the classical algebraic notion of matrix permanent. Namely, solving the assignment problem means finding the (max, +)- permanent of a matrix (in our case infinite dimensional). If this solution is strong, then one says that this matrix has a strong permanent. An important tool in algebra is given by the so called Kleene star that for a given matrix A is defined by A =
k=0

A

k

(the powers Ak are understood in the operations of a given algebra). In (max, +)-algebra the elements of A clearly define the longest path on the graph associated with A (see details e.g. in [3] for finite and respectively infinite space X ), and its columns are natural candidates for the solution of the eigenvalue - eigenvector equation for A (equation of type (1.9)). Hence the non-surprising appearance of A in our setting (our functions ~ij and b potentials i represent appropriately normalized elements of A ). As was observed in [10], the functions ~ij turn out to be useful also in the analb ysis of the Monge-Kantorovich mass transfer problem, which is a natural analogue of the assignment problem for general measurable (uncountable) state space X . Bibliography
[1] M. Akian. Densities of idempotent measures and large devoations. Trans. Amer. Math. So c. 351:11 (1999), 4515-4543. [2] M. Akian, S. Gaubert, V. Kolokoltsov. Set coverings and invertibility of functional Galois connections. Contemporary Mathematics, v. 377 (2005), 19-51. [3] M. Akian, S. Gaubert and C. Walsh. Discrete max-plus spectral theory. Contemp orary Mathematics, v. 377 (2005), 53-77. [4] P. Butkovi Simple image set of (max,+) linear mappings. Discrete Appl. Math. c. 105 (2000), 73-86. [5] P. Butkovi Max-algebra: linear algebra of combinatorics? Linear Algebra Appl. c, 367 (2003), 313-335. [6] J. Gunawardena (Ed.). Idempotency. Cambridge University Press, 1998.


Dequantization of coadjoint orbits

21

[7] V.N. Kolokoltsov. On linear, additive and homogeneous operators in idemp otent analysis. In: V.P. Masov, S.N. Samborskii (Eds.) Idempotent Analysis. Adv. Sov. Math. 13, AMS Providence (1992), 87-101. [8] V.N. Kolokoltsov and V.P. Maslov. Idempotent analysis and its Applications. Kluwer Academic, 1997. [9] G.L. Litvinov, V.P. Maslov, G.B. Shpiz. Idemp otent functional analysis. An algebraic approach. Mathematical Notes 69: 5 (2001), 696-729, also arXiv:math.FA/0009128 (2000) (http://arXiv.org). [10] L. Ruschendorf. On c-optimal random variables. Statistics and Probability Letters è 27 (1996), 267-270.

Dequantization of coadjoint orbits: the case of exp onential Lie groups1 Ali Baklouti
^ It is well known that the unitary dual G of an exponential solvable Lie group G is homeomorphic to the space of coadjoint orbits. Given a coadjoint orbit O, the orbit method enables us to construct the associated unitary and irreducible representation. The inverse procedure is called Dequantization and it consists in going backwards from an irreducible unitary representation : G - U (H ) to the coadjoint orbit O and its associated geometric ob jects. Here, U (H ) denotes the group of unitary operators on some complex inner product space H . Towards dequantization, we consider the Poisson characteristic variety of some topological unitary modules over a deformed algebra appropriately associated with the representation in question. In the case of nilpotent Lie groups, we showed that the Poisson characteristic variety coincides with the associated coadjoint orbit. For exponential Lie groups, we conjecture that such a variety coincides with the Zariski closure of the orbit. In this work, we prove such a conjecture for some restrictive classes of exponential Lie groups.

1

Partially supported by the D.G.R.S.T Research Unity:00 UR 1501.


22

Viacheslav P. Belavkin

Quantum Pontryagin principle and quantum Hamilton-Jacobi-Bellman equation: a max-plus p oint of view Viacheslav P. Belavkin
We exploit the separation of the filtering and control aspects of quantum feedback control to consider the optimal control as a classical stochastic problem on the space of quantum states. We derive the corresponding Hamilton-Jacobi-Bellman equations using the elementary arguments of classical control theory and show that this is equivalent to a HamiltonPontryagin setup. We show that, for cost functionals that are linear in the state, the theory yields the traditional Bellman equations treated so far in quantum feedback. A controlled qubit with a feedback is considered as example. 1. Intro duction Quantum measurement, by its very nature, leads always to partial information about a system in the sense that some quantities always remain uncertain, and due to this the measurement typically alters the prior to a posterior state in process. The Belavkin nondemolition principle [3, 5] states that this state reduction can be effectively treated within a nondemolition scheme [5],[6] when measuring the system over time. Hence we may apply a quantum filter for either discrete [1] or time-continuous [3] non-demolition state estimation, and then consider feedback control based on the results of this filtering. The general theory of continuoustime nondemolition estimation developed in [6],[8],[9] derives for quantum posterior states a stochastic filtering evolution equation not only for diffusive but also for counting measurements, however we will consider here the special case of Belavkin quantum state filtering equation based on a diffusion model described by a single white noise innovation, see e.g. [7]. Once the filtered dynamics is known, the optimal feedback control of the system may then be formulated as a distinct problem. The separation of the classical world from the quantum world is, of course, the most notoriously troublesome task faced in modern physics. At the very heart of this issue is the very different meanings we attach to the word state. What we want to exploit is the fact that the separation of the control from the filtering problem gives us just the required separation of classical from quantum features. By the quantum state we mean the von Neumann density matrix which yields all the (stochastic) information


Quantum Pontryagin principle

23

available about the system at the current time - this we also take to be the state in the sense used in control engineering. All the quantum features are contained in this state, and the filtering equation it satisfies may then to be understood as classical stochastic differential equation which just happens to have solutions that are von Neumann density matrix valued stochastic processes. The ensuing problem of determining optimal control may then be viewed as a classical problem, albeit on the unfamiliar state space of von Neumann density matrices rather than the Euclidean spaces to which we are usually accustomed. Once we get accustomed to this setting, the problem of dynamical programming, Bellman's optimality principle, etc., can be formulated in much the same spirit as before. 2. Notations and Facts The Hilbert space for our fixed quantum system will be a complex, separable Hilbert space h . We shall use the following spaces of operators: A A S T0 T0 = B (h) = T (h) = S (h) = T0 (h) = T0 (h) the the the the the Banach algebra of bounded operators on h; predual space of trace-class operators on h; positive, unital-trace operators (states) on h; tangent space of zero-trace operators on h; cotangent space (see below).

The space A equipped with the trace norm 1 = tr | | is a complex Banach space, the dual of which is identified with the algebra A with usual operator norm. The natural duality between the spaces A and A is indicated by (2.1) , A := tr { A} ,

for each A , A A. The positive elements, in the sense of positive definiteness 0, form a cone T+ of the real subspace T A of all Hermitian elements = , and the unit trace elements T+ normalized as 1 = 1 are called normal states. Thus S = T+ T1 , where T1 = { T : tr = 1}, and the extremal elements S of the convex set S T+ correspond to pure quantum states. Every state can be parametrized as (q ) = 0 - q by a tangent element q T0 with respect to a given state 0 S . We may use the duality (2.1) to intro duce cotangent elements p T0 . Knowledge of q , p for each q T0 will only serve to determine p A up to an additive constant (as the q 's are trace-free): for this reason we should think of cotangents elements p as equivalence classes (2.2) p [X ] = {A A : A = X + I , for some R} .


24

Viacheslav P. Belavkin

The symmetric tensor power A2 = A sym A of the algebra A is sy m the subalgebra of B h2 of all bounded operators on the Hilbert product space h2 = h h, commuting with the unitary involutive operator S = S of permutations 1 2 2 1 for any i h. A map L (t, §) from A = B (h) to itself is said to be a Lindblad generator if it takes the form (2.3) (2.4) L (t, X ) LR (X ) = i [H (t) , X ] +


L

R



(X ) ,

1 1 = R X R - R RX - X R R 2 2 with H self adjoint, the R A (and the summations in (3) understood to be ultraweakly convergent [27] for an infinite set {R }). The generator is Hamiltonian if it just takes form i [H (t) , §]. The pre-adjoint L = L of a generator L is defined on the pre-adjoint space A through the relation L ( ) , X = , L (X ) . We note that Lindblad generators have the property L (I ) = 0 corresponding to conservation of the identity operator I A or, equivalently, tr {L ( )} = 0 for all A . In quantum control theory it is necessary to consider time-dependent generators L (t), through an integrable time dependence of the controlled Hamiltonian H (t), and, more generally, due to a square-integrable time dependence of the coupling operators R (t). We shall always assume that these integrability conditions, ensuring existence and uniqueness of the solution (t) to the quantum state Master equation (2.5) for all for Let F A ), then function (2.6) d (t) = L (t, (t)) (t, (t)) , dt t t0 with given initial condition (t0 ) = 0 S , are fulfilled. = F [§] be a (nonlinear) functional F [ ] on A (or on S we say it admits a (Frechet) derivative if there exists an A-valued F [§] on A (T0 -valued functional on T0 ) such that
h0

lim

1 {F [§ + h ] - F [§]} = , h

F [§] ,

for each A (for each T0 ). In the same spirit, a Hessian 2 can be defined as a mapping from the functionals on S to the A2 -valued functionals, via sy m
h,h 0

lim

(2.7)

1 {F [§ + h + h ] - F [§ + h ] - F [§ + h ] + F [§]} hh = , F [§] .


Quantum Pontryagin principle

25

and we say that the functional is twice continuously differentiable whenever 2 F [§] exists and is continuous in the trace norm topology. Likewise, a functional f : X f [X ] on A is said to admit an A derivative if there exists an A -valued function X f [§] on A such that 1 (2.8) lim {f [§ + hA] - f [§]} = X f [§] , A h0 h for each A B (h). The derivative X f [§] has zero trace, X f [A] T0 for each A A, if and only if the functional f [X - I ] does not depend on , i.e. is essentially a function f (p) of the class p [X ] T0 . With the customary abuses of differential notation, we have for instance f ( , X ) = f ( , X ) X,
X

f ( ,X ) = f ( ,X ) , , X . Typically, we

for any differentiable function f of the scalar x = shall use more often, and denote it by just . 3. Quantum Optimal Control

From now on we will assume that the Hamiltonian H and therefore (and ) are functions of a controlled parameter u U depending on t such that the time dependence of the generator L is of the form L (u (t)). Moreover, we do not require at this stage the linearity of (u, ) with respect to , as well as the quadratic dependence ( ), which means that what follows below is also applicable to more general quantum stochastic kinetic equations d
§

(t) = (u (t) ,

§

(t)) dt + (

§

(t)) dw (t)

of Vlassov and Boltzmann type, with only the positivity and trace preservation requirements tr { (u, )} = 0 = tr { ( )}. A choice of the control function {u (r) : r [t0 , t]} is required before we can solve the filtering equation (Belavkin equation) at the time t for a given initial state 0 at time t0 . From what we have said above, this is required to be a U -valued function which we take to be continuous for the moment. The cost for a control function {u (r)} over any time-interval [t, T ] is random and taken to have the integral form
T

(3.1)

J [{u (r)} ; t, ] =
t

C (u (r) ,



(r)) dr + G (



(T ))

where { § (r) : r [t, T ]} is the solution to the filtering equation with initial condition § (t) = . We assume that the cost density C and the terminal cost, or bequest function, G will be continuously differentiable


26

Viacheslav P. Belavkin

in each of its arguments. In fact, due to the statistical interpretation of quantum states, we should consider only the linear dependence (3.2) C (u, ) = , C (u) , G ( ) = ,G of C and G on the state as it was already suggested in [4],[6],[10]. We will explicitly consider this case later, but for the moment we will not use the linearity of C and G. We refer to C (u) A as cost observable for u U and G A as the bequest observable. The feedback control u (t) is to be considered a random variable u (t) adapted with respect to the innovation process w (t), in line with our causality requirement, and so we therefore consider the problem of minimizing its average cost value with respect to {u§ (t)}. To this end, we define the optimal average cost on the interval [t, T ] to be (3.3) S (t, ) :=
{u§ (r )}

inf

E [J§ [{u§ (r)} ; t, ]] ,

where the minimum is considered over all measurable adapted control strategies {u§ (r) : r t}. The aim of feedback control theory is then to find an optimal control strategy {u (t)} and evaluate S (t, ) on a fixed § time interval [t0 , T ]. Obviously that the cost S (t, ) of the optimal feedback control is in general smaller than the minimum of E [J§ [{u} ; t, ]] over nonstochastic strategies {u (r)} only, which gives the solution of the open loop (without feedback) quantum control problem. In the case of the linear costs (3.2) this open-loop problem is equivalent to the following quantum deterministic optimization problem which can be tackled by the classical theory of optimal deterministic control in the corresponding Banach spaces. 3.1. Bellman & Hamilton-Pontryagin Optimality. Let us first consider nonstochastic quantum optimal control theory assuming that the state (t) S obeys the master equation (2.5) where (u, ) is the adjoint L (u) of some Lindblad generator for each u with, say, the control being exercised in the Hamiltonian component i [§, H (u)] as before. (More generally, we could equally well consider a nonlinear quantum kinetic equation.) The control strategy {u (t)} will be here non-random, as will be any specific cost J [{u} ; t0 , 0 ]. As for S (t, ) = inf J [{u} ; t, ] at the times t < t + < T , one has S (t, ) =
t+ {u} T

inf

C (u (r) , (r)) dr +
t t+

C (u (r) , (r)) dr + G ( (T )) .


Quantum Pontryagin principle

27

Suppose that {u (r) : r [t, T ]} is an optimal control when starting in state at time t, and denote by { (r) : r [t, T ]} the corresponding state tra jectory starting at state at time t. Bellman's optimality principle observes that the control {u (r) : r [t + , T ]} will then be optimal when starting from (t + ) at the later time t + . It therefore follows that
t+

S (t, ) = inf

{u(r )}

C (u (r) , (r)) dr + S (t + , (t + )) .
t

For small we expect that (t + ) = + (u (t) , ) + o () and provided that S is sufficiently smooth we may make the Taylor expansion (3.4) S (t + , (t + )) = 1 + In addition, we approximate
t+

+ (u (t) , ) , t

S (t, ) + o () .

C (u (r) , (r)) dr = C (u (t) , ) + o ()
t

and conclude that (note the convective derivative!) S (t, ) = inf
u U

1 + C (u, ) +

+ (u, ) , § t

S (t, ) + o ()

where now the infimum is taken over the point-value of u (t) = u U . In the limit 0, one obtains the equation (3.5) where = condition (3.6) - S (t, ) = inf {C (u, ) + (u, ) , S (t, ) } , uU t . The equation is then to be solved sub ject to the terminal S (T , ) = G ( ) .

We may introduce the Pontryagin Hamiltonian function on T0 ½ T0 defined by the Legendre-Fenchel transform (3.7) H (q , p [X ]) := sup { (u, (q )) , I - X - C (u, (q ))} .
uU

Here we use a parametrization (q ) = 0 - q , q T0 and the fact that the supremum does not depend on R since (u, ) , I = 0. Therefore H depends on X only through the equivalence class p [X ] T0 which is referred to as the co-state. It should be emphasized that these Hamiltonians are purely classical devices which may be called super-Hamiltonians


28

Viacheslav P. Belavkin

to be distinguished from H . We may then rewrite (3.5) as the (backward) Hamilton-Jacobi equation (3.8) - S (t, (q )) + H (q , p [ S (t, )] (q )) = 0. t

Applying the derivative q = - to this equation to q = 0 - in the tangent space T0 we obtain the dynamical equation p = - q H (q , p) for the co-state pt = Qt (T , s) of the operatorívalued function X (t, ) = S (t, ), where Qt (T , s) = p [X (t, )] is the solution of this equation satisfying the terminal condition QT (T , s) = s := p [G] with p [G ( )] (q ) = p [G ( (q ))] for G = G. We remark that, if u (q , p (X )) is an optimal control maximizing K (u, q , p (X )) = (u, (q )) , I - X - C (u, (q )) ,
d then the corresponding state dynamical equation dt = (u ( , X ) , ) in terms of its optimal solution qt 0 - t (t0 , 0 ) corresponding to t0 0 can be written as q = p H (q , p), noting that

(3.9)

p

H (q , p) =

p

K (u (q , p) , q , p) = - (u (q , p) , (q )) p) = 0 at u = u . This together with the co-state the canonical Hamiltonian the Hamiltonian boundary

due to the stationarity condition u K (u, q , forward equation with q0 = 0 for (t0 ) = 0 backward equation with pT = p [G] s is system. Thus we may equivalently consider value problem (3.10) qt - pt +
p q

H (qt , pt ) = 0, q0 = 0 H (qt , pt ) = 0, pT = s

which we refer to as the Hamilton-Pontryagin problem, in direct analogy with the classical case. The solution to this problem defines the minimal cost as the path integral
T

S (t0 ,

0

)=
t0

[ qr |p

r

- H (qr , pr )] dr + G ( (qT )) .

Thus the Pontryagin maximum principle for the quantum dynamical system is the observation that the optimal quantum control problem is equivalent to the Hamiltonian problem for state and co-state {q } and {p} respectively, leading to optimality K (u, q , p) H (q , p) with equality for u = u (q , p) maximizing K (u, q , p).


Quantum Pontryagin principle Bibliography

29

[1] V.P. Belavkin. Optimal Quantum Filtration of Markovian Signals. Problems Control Inform. Theory, 7: no. 5, 345í360 (1978) [2] V.P. Belavkin, Optimal Measurement and Control in Quantum Dynamical Systems. Preprint No. 411, Inst. of Phys., Nicolaus Cop ernicus University, Torun', February 1979 [3] V.P. Belavkin, Quantum Filtering of Markov Signals with Wight Quantum Noise. Radiotechnika and Electronika, 25: 1445í1453 (1980). English translation in: Quantum Communications and Measurement. V. P. Belavkin et al, eds., 381í392 (Plenum Press, 1994). [4] V.P. Belavkin, Theory of the control of observable quantum systems. Autom. Remote Control, 44: 178-188, (1983) [5] V.P. Belavkin, Nondemolition measurement and control in quantum dynamical systems. Information complexity and control in quantum physics (Udine, 1985), 311í 329, CISM Courses and Lectures, 294, Springer, Vienna, 1987. [6] V.P. Belavkin, Nondemolition measurements, nonlinear filtering and dynamical programming of quantum stochastic pro cesses. In: Mo delling and Control of Systems (Lecture Notes in Control and Information Sciences), ed A Blaquiere, 121: 381í92 (Berlin: Springer, 1988) [7] V.P. Belavkin, A new wave equation for continuous nondemolition measurement. Phys. Lett. A, 140: 355í8 (1989). [8] V.P. Belavkin, Sto chastic p osterior equations for quantum nonlinear filtering. Probability Theory and Mathematical Statistics, ed B Grigelionis, 1: 91í109 (Vilnius: VSP/Mokslas, 1990). [9] V.P. Belavkin, Quantum sto chastic calculus and quantum nonlinear filtering. Journal of Multivariate Analysis, 42: 171-201, (1992) [10] V. P. Belavkin, Measurement, filtering and control in quantum open dynamical systems. Rep. on Math. Phys.43: no. 3, 405-425 (1999).

Tropical Plucker functions è V.I. Danilov, A.V. Karzanov and G.A. Koshevoy

1. Intro duction Totally positive matrices play an important role in different areas of mathematics, from differential equations to combinatorics. Studying parametrizations of canonical bases, Berenstein, Fomin and Zelevinsky [1] established the so-called Chamber ansatz for flag minors of matrices. This result relies on Plucker relations between flag minors. In this talk, we study è functions which satisfy tropical Plucker relations. We consider two apè proaches to tropicalization of Plucker relations. One approach is based on è


30

V.I. Danilov, A.V. Karzanov, G.A. Koshevoy

tropicalization of the so-called special Plucker relation (3-term relation) è after writing it as a subtraction-free expression. On this way we get the class of TP-functions (on Boolean cube 2N ) which can be seen as the tropicalization of flag minors. We show that such functions are determined by their restrictions to the interval family of subsets of N , and that the class of submodular TP-functions coincides with the class of submodular functions on the interval family. This might be seen as the tropicalization of the Chamber ansatz. Our proof is based on a construction of DMTPfunctions via normal flows in weighted digraphs. A DMTP-function is a function that satisfies tropical Plucker relations, and at this point we conè sider the tropicalization in the sense of the second approach, meaning that we tropicalize an algebraic formula with subtractions in the right hand side as an inequality. 2. Flag minors and Plucker relations è For X an n ½ n matrix and I a subset of N = {1, . . . , n}, denote by I (X ) the determinant of the submatrix located in the intersection of the first |I | rows and the columns indexed by I . These determinants are called flag minors of X . It is known (see Fulton and Harris [3], p.235), that flag minors of a matrix X satisfy the Plucker relations è
AI



AJ

=
iI

(-1)

d(I ,J,i,j )



A(I \i)j



A(J \j )i

,

for any pairwise disjoint A, I , J N , |I | |J |, any fixed j J , and an appropriate function d(I , J, i, j ). The Plucker relations with 2 |I | |J | 1 are of special interest. è They are given by
Aik



Aj

= Aij = Aij

Ak

+

A j k



A i

with any A and i < j < k , and
Aik



Aj l

Akl

+

A j k



Ail

with any A and i < j < k < l. Definition 2.1. A function F : 2N R is said to be P-function if F satisfies the above Plucker relations for all A and i < j < k , that is è (2.1) F (A ik )F (A j ) = F (A ij )F (A k ) + F (A j k )F (A i). Denote by P F the set of P -functions. We collected properties of P -functions in the following


Tropical Plucker functions è

31

Theorem 2.1. a) Any P-function satisfies al l Plucker relations. è b) Let F : 2N R=0 be a P-function. Then there exists a unique upper-triangular N ½ N matrix X such that F (I ) = I (X ). c) Let I 2N denote the interval family constituted from intervals N {i, i + 1, . . . , j }, i j , and let resI : R2 RI denote the restriction map from 2N to I . Then the mapping resI is a bijection N between the subspace P F ( R2 ) and RI . 3. Tropical Plucker functions è We consider two ways of tropicalization of P -functions. Firstly, we can tropicalize (2.1) as follows: (3.1) f (A ik ) + f (A j ) = max(f (A ij ) + f (A k ), f (A j k ) + f (A i)), with any A and i < j < k . Definition 3.1. A function f : 2N R is said to be a TP-function if F satisfies the tropicalization (3.1) of Plucker relations for all A and è i < j < k. Secondly, we can think of tropicalization in the form of inequality: (3.2) f (A I ) + f (A J ) max(f (A (I \ i) j ) + f (A (J \ j ) i)),
iI

for any pairwise disjoint A, I , J , |I | |J |, and any fixed j J . Specializing this to tropicalization of the 3-term Plucker relation given è by (2.1), we have that, for all disjoint A N and {i, j, k } N , the maximum is attained at least twice among the three values (3.3) a = f (A ik ) + f (A j ), b = f (A ij ) + f (A k ), c = f (A j k ) + f (A i). Similarly, for a 4-term Plucker relation, that is, for all disjoint A N è and {i, j, k , l} N , we have that the maximum is attained at least twice among the three values (3.4) x = f (A ik ) + f (A j l), y = f (A ij ) + f (A k l), z = f (A j k ) + f (A il). Definition 3.2. A function f : 2N R is called a DMTP-function if f satisfies (3.3) and (3.4). We will show in the following section that the class of TP-functions is a subclass of DMTP-functions. We have the following property of DMTP-functions, which is closely related to valuated matroids, see Dress and Wenzel [2].


32

V.I. Danilov, A.V. Karzanov, G.A. Koshevoy

Theorem 3.1. A DMTP-function f satisfies al l tropical Plucker reè lations (3.2). 4. Flows in digraphs and DMTP-functions Here we propose a construction of DMTP-functions. We deal with a digraph G = (V , E ), a function c : E R of weights on the edges, and disjoint subsets S, T V . We assume that |S | = |T | and that T is ordered: T = (t1 , t2 , . . . , t|T | ), and denote {t1 , . . . , ti } by Ti . For F E and X V , denote: + the sets of edges in F leaving X and entering X by F (X ) and by - F (X ), respectively; + - the set F (X ) F (X ) by F (X ); + - the number |F (X )| - |F (X )| by divF (X ). if Definition 4.1. Let us say that F E is a normal flow from S S 1 vS, -1 v T|S | , divF (v ) = 0 for the other v V , where div(v ) stands for div({v }). This gives rise to the following important function f = fc on 2S : (4.1) f (S ) := max{c(F ), F is a normal flow from S }, S S. Theorem 4.1. f defined in (4.1) is a DMTP-function. The claim that TP-functions constitute a subslass of DMTP-functions can be obtained as a consequence of the following Theorem 4.2. Let f : 2N R be a TP-function. Then there exists a planar digraph G = (V , E ) and a weight function c : E R, such that f is defined by (4.1). Remark 4.1. For a TP-function on the Boolean 2N , we can take the unique planar of the following from: V := {(i, j ) 1 i, j n}, and two edges emanate from the vertex (i, j ), which terminate either in (i - 1, j ) or in (i, j + 1), respectively, if both terminate points are vertices. The following property is important, see Kamnitzer [4], for applications to crystal bases construction via MV-polytopes: Theorem 4.3. A TP-function f : 2N R is submodular (that is f (A) + f (B ) f (A B ) + f (A B ), A, B N ) if and only if the function resI (f ) is submodular on I .


Tropical Plucker functions è Bibliography

33

[1] Berenstein A., Fomin S. and Zelevinsky A., Parametrizations of canonical bases and totally p ositive matrices, Adv. in Math. 122 (1996), 49í149. [2] Dress A.W.M. and W.Wenzel, Valuated matroids: A new lo ok at the greedy algorithm, Appl. Math. Lett., 4 (1991), 33-35 [3] Fulton W. and J.Harris, Rrepresentation Theory, Graduate Texts in Mathematics, 129, Springer, 1991 [4] Kamnitzer J., The crystal structure on the set of Mirkovic-Vilonen p olytopes, ArXiv, math:QA/0505398

Degree one homogeneous minplus dynamic systems and traffic applications: Part I1 N. Farhi, M. Goursat, and J.-P. Quadrat
We show that car traffic on a town can be modeled using a Petri net extension where arcs have negative weights. The corresponding minplus dynamics is not linear but homogeneous of degree one. Possibly depending on the initial condition, homogeneous of degree 1 minplus systems may be periodic or have a chaotic behavior (to which corresponds a constant throughput) or may explode exponentially. In traffic systems, when this constant throughput exists, it has the interpretation of the average car speed. In this first part we recall the derivation of the 1-homogeneous dynamics of traffic system and show the existence of such systems with chaotic behavior and a constant throughput. 1. Intro duction At macroscopic level, the traffic on a road can be seen from various points of view: § The Lighthill-Whitham-Richards Model [6] is the more standard one t + x q = 0 , q = f (), where q (x, t) = denotes the flow at time t and position x on the road, (x, t) = denotes density, f is a given function, called the fundamental traffic law. For the traffic, it plays the role analogous to that of the perfect gas law in the fluid dynamics.
1Partially supp orted by the joint RFBR/CNRS grant No. 05-01-02807.


34

N. Farhi, M. Goursat, J.-P. Quadrat § The kinetic model (Prigogine-Herman [7]) gives the evolution of the particle density (t, x, v ) as a function of t, x and v , where v is the speed of particle t + v x = C (, ) , with C (, ) an interacting term in general quadratic in .

The second model is more costly in terms of computation time and therefore not used in practice. The first one assumes the knowledge of the function f , which is usually obtained experimentally, or theoretically using a simple microscopic model. Here, we will recall a way to derive a good approximation of this law f from a simple minplus linear system based on a Petri net. The main purpose of this paper is to generalize this fundamental law to the 2D cases where roads have crossings. The original minplus linear model on a unique road cannot be generalized easily in term of Petri nets. We have proposed in a previous paper a way to solve the difficulty by using Petri net with negative weights. The dynamics of this Petri net can be written easily. It is not linear in minplus algebra any more, but it is homogeneous of degree 1. We recall here the derivation of this 1homogeneous dynamics. In the first part of this paper we show that we can compute the eigenvalues for this 1-homogeneous system but that chaotic dynamics may appear. In the second part we discuss the phases appearing in the fundamental diagram, obtained numerically, and describe new situations where we can prove that the system is periodic. 2. Traffic on a circular road Let us recall the simplest model which allows to derive the fundamental traffic law on a single road. The simplest way is to study the stationary regime on a circular road with a given number of vehicles and then to consider that this stationary regime is reached locally when the density is given on a standard road. We present two ways to obtain this law : í by logical deduction from an exclusion process, í by computing the eigenvalue of a minplus system derived from a simple Petri net describing the road with the vehicles. 2.1. Exclusion pro cess mo deling. Following [3] we can consider the dynamic system defined by the rule 10 01 applied to a binary word describing the car positions on a road cut in sections (each bit representing


Degree one homogeneous dynamic systems: Part I
1 10 9 8 7 6 5 1 2 0 3 4 0 1 1

35

I

II
1 1 0 0

0

am
1

x

1

a1 x
2

am

a1

III

Figure 1. A circular road. a section, 1 meaning occupied and 0 meaning free, see II in Figure 1). Let us take an example : m1 = 1101001001, m4 = 1010101010, m2 = 1010100101, m5 = 0101010101, m3 = 0101010011,

Let us define : í the density to be the number of vehicles n divided by the number of places m : = n/m, í the flow q (t) at time t to be the number of vehicles going one step forward at time t divided by the number of places. Then the fundamental traffic law gives the relation between q (t) and d. If 1/2, then all the vehicle groups split off after a transient period, and all the vehicles can move forward without other vehicles in the way, and we have : q (t) = q = n/m = d . If 1/2, then the free place groups split off after a finite time and move backward without other free place in the way. Then m - n vehicles move forward and we have q (t) = q = (m - n)/m = 1 - d . Therefore : T : t T q (t) = q = 1- if 1/2 , if 1/2 .


36

N. Farhi, M. Goursat, J.-P. Quadrat

q 1/2

1/2 1

Figure 2. The fundamental traffic law.

2.2. Event Graph mo deling. Consider the Petri net given in III of Figure 1 which describes in a different way the same dynamics. In fact this Petri net is an event graph and therefore its dynamics is linear in minplus algebra. The number of vehicles entered in the place i before time k is denoted xk . The initial vehicle position is given by the boolean i number ai , which takes the value 1 when the cell contains a vehicle and is 0 otherwise. We use the notation a = 1 - a, then the dynamics is given by : ï x
k+1 i

= min{ai x
k+1 i

-1

+ xk-1 , ai + x ï i ai x ï
k i+1

k i+1

},

which can be written linearly in minplus algebra : = ai
k -1 xi-1

.

This event graph has three kinds of elementary circuits : í the outside circuit with average mean n/m, í the inside circuit with average mean (m - n)/m, í the circuits corresponding to make some step forward and coming back, with average mean 1/2, Therefore its eigenvalue is q = min(n/m, (m - n)/m, 1/2) = min(, 1 - ) , which gives the average speed as a function of the car density. 3. 2D traffic Let us generalize the second approach to derive the fundamental diagram to a regular town described in Figure 3. The complete town can be modeled as a set of subsystems corresponding to a unique crossing and


Degree one homogeneous dynamic systems: Part I

37

BLOC (I,J)

Figure 3. A town. two adjacent roads. To write the dynamics of the town we have first to give the Petri net describing a crossing. A first trial is to consider the Petri net given in Figure 4. This Petri net is not an event graph any more. However, following L. Libeaut[5], it is possible to write the nonlinear implicit minplus equation describing a general Petri net : (3.1)
pxin

min ap +
x x
in

x (k - 1) -
x x
out

x (k ) = 0, x , k .

where x(k ) denotes the firing number of transition x and p is a place of the Petri Net. But this equation does not determine the dynamics completely,
y1 u1

x2

u2 y2 an xn+1 an u3

xn

a 2n-1 x x2n a 2n-1 2n-1

y

4

x1 y

xn+2

u4

3

Figure 4. A simplified crossing.


38

N. Farhi, M. Goursat, J.-P. Quadrat

since solution to the Cauchy problem may be non-unique. Indeed : í at place an we may have a routing policy giving the proportion of cars going towards y2 and the proportion going towards y3 (which is not described by the Petri net 4) í at place an we may follow the first arrived the first ï served rule with the right priority if two cars arrive simultaneously at the crossing (which is also not described by the Petri net 4). Precising the dynamics of Petri net in such a way that the tra jectories are uniquely defined corresponds to giving another Petri net having only one arc leaving each place. Let us discuss more precisely these points on a simple system given in the first picture of Figure 5.
x1 x1

x1
1 1 1
Undefined Dynamics

x3 1

a

x2

x3

a
1

1/2

1/2 1/2

-1

1

1 1 1

a
1

1/2

x2

x3

1

a

-1 1

a

x2

x4

Given Routage

x4

x4
West Priority

Figure 5. Dynamic Completion. The incomplete dynamics of this system can be written in minplus algebra xn xn = axn-1 xn-1 . Clearly x4 and x3 are not defined uniquely. 43 1 2 We can complete the dynamics, for example, in the two following ways useful for the traffic application : í by precising the routing policy xn = xn = 4 3 í by choosing a priority rule xn = ax 3 xn = ax 4
n-1 1 n-1 1

ax

n-1 n-1 x2 1

x x

n-1 2 n-1 2

/xn-1 4 /xn . 3

In these two cases we obtain a degree one homogeneous minplus system. This method can be applied to the crossing and we obtain a Petri net with negative weights which has only one arc leaving each place (that we call deterministic Petri net), see Figure 6.


Degree one homogeneous dynamic systems: Part I

39

y1

u1

x2

y2

u2 a 2n xn+1 u3

1/2 1/2

xn x 2n
1/2

a 2n-1 xn+2

y

4

1/2

an x1 y3

a 2n-1

u4

-1

an a2n

-1

Figure 6. A Complete Crossing. If we neglect the roundings, then the system can be written with minplus notations : xi / = ai-1 xi-1 ai xi+1 , ï xn / = an x1 xn+1 /x2n an-1 xn-1 , ï x2n / = a2n x1 xn+1 /(xn / ) a2n-1 x2n-1 , ï x1 / = an xn x2n a1 x2 , ï x / = a2n xn x2n an+1 xn+2 , ï n+1 where denotes the forward shifting operator acting on sequences. It is a general degree 1 homogeneous minplus system. Simulation of this system starting from 0 shows that lim xk /k = , i . i
k

The constant has the interpretation of the average speed. The fundamental diagram gives the relation between the average speed and the vehicle density of the system. In Figure 7 we give this law in the cases of two circular roads with one crossing for different relative size of the two roads. We see that three phases appear on each fundamental diagram. These phases will be discussed in the second part of this paper. The experimental existence of this motivates the study of the eigenvalue of 1-homogeneous minplus system.


40
f

N. Farhi, M. Goursat, J.-P. Quadrat

0.25

0

d 0 0.5 1

Figure 7. 2D-traffic fundamental diagrams. 4. Eigenvalues of 1-homogeneous minplus systems The eigenvalue problem for 1-homogeneous system f : Rn Rn can min min be formulated as finding x Rn non zero, and Rmin such that : min x = f (x) . Since f is 1-homogeneous, assuming without loss of generality that if x exists then x1 = , the eigenvalue problem becomes : = f1 (x/x1 ) , x /x = (f2 /f1 )(x) , 2 1 § § § = §§§ xn /x1 = (fn /f1 )(x) , Denoting y = (x2 /x1 , § § § , xn /x1 ), the problem is reduced to the computation of the fixed point problem y = g (y ) (with gi-1 (y ) = (fi /f1 )(0, y )). It is a problem of computing a normalized eigenvector, from which the eigenvalue is deduced by : = f1 (0, y ). But now g is a general minplus function. The fixed point problem does not always have a solution. There are cases where we are able to solve the problem í f is affine in standard algebra, í f is minplus linear, í f is a positive power function. In the first case there is a unique eigenvalue as soon as dim(ker(f - I )) = 1. In the two last cases, the problem can be reduced to the minimization of the average cost by time unit using dynamic programming methods. The corresponding fixed points are unique and stable. Moreover, since max(x, y ) = xy /(x y ), games problem are also 1homogeneous minplus systems and the solution to the corresponding eigenvalue problem is known.


Degree one homogeneous dynamic systems: Part I

41

In general, we may have unstable fixed points that, nevertheless, we can compute by Newton method (which is exactly the policy iteration) but which don't give the information about the asymptotic behavior of the system any more. In this case the asymptotics is obtained by an averaging based on invariant measure which may be difficult to compute. Let us give an example of chaotic system which has a 1-homogeneous minplus dynamics. 5. A Chaotic system example Let us consider the 1-homogeneous minplus dynamic system x x
k+1 1 k+1 2

= (xk )2 /xk 2(xk )3 /(xk )2 , 1 2 2 1 = xk . 2 x1 = x2 /x2 2x3 /x2 , 1 2 1 x2 = x2 .

The corresponding eigenvalue problem is

The solutions are = 0 and y = x1 /x2 . They satisfy the equation

4 4' b c 5'

5

M fofof 2' 3'

2 fof a f 1 1'

3

d

6'

6

N

Figure 8. Cycles of tent transformation. y = y 2 2/y 2 , which has solutions y = 0 and y = 2/3. These two solutions are unstable fixed points of the transformation f (y ) = y 2 2/y 2 . But the system yn+1 = f (yn ) is a chaotic system since f is the tent transform (see e.g. [2]


42

N. Farhi, M. Goursat, J.-P. Quadrat

for a comprehensive discussion of this dynamics). In Figure 8 we show graphs of the functions f , f f , f f f , their fixed points and the corresponding periodic tra jectories. In Figure 9 we show a tra jectory for an initial condition chosen randomly with the uniform law on the set {(i - 1)/105 , i = 1, § § § , 105 }. The diagonal line in the picture is a decreasing sort applied to the tra jectory. It shows that the invariant empirical density is uniform. We can prove that

100000 90000 80000 70000 60000 50000 40000 30000 20000 10000 0 0 50 100 150 200 250 300

Figure 9. A tent iteration tra jectory. the tent iteration has a unique invariant measure absolutely continuous with respect to the Lebesgue measure : the uniform law on [0, 1]. More generally, a chaotic 1-homogeneous minplus system will grow linearly with a value given by : = f1 (y )d²(y ) ,

where ² is the invariant probability measure of y depending on the initial value y 0 . For example, according to the initial value y 0 , the tent iterations y k stay in circuits or follow tra jectories without circuit (possibly dense in [0, 1]). Bibliography
[1] F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat : Synchronization and Linearity, Wiley (1992). [2] N. Berglund : Geometrical Theory of Dynamical Systems ArXiv:math (2001). [3] M. Blank : Variational principles in the analysis of traffic flows, Markov Pro cesses and Related Fields, pp.287-305, vol.7, N.3 (2000).


Degree one homogeneous dynamic systems: Part II

43

[4] N. Farhi, M. Goursat, J.-P. Quadrat : Derivation of the fundamental traffic diagram for two circular roads and a crossing using minplus algebra and Petri net modeling, in Pro ceedings IEEE-CDC, 2005, Seville (2005). [5] L. Lib eaut : Sur l'utilisation des dioè ides pour la commande des syst` emes a ` ‡‡ evenements discrets, Th` ese, Lab oratoire d'Automatique de Nantes (1996). [6] J. Lighthill, J. B. Whitham : On kinetic waves: II) A theory of traffic Flow on long crowded roads, Pro c. Royal Society A229 p. 281-345 (1955). [7] I. Prigogine, R. Herman : Kinetic Theory of Vehicular Traffic, Elsevier (1971).

Degree one homogeneous minplus dynamic systems and traffic applications : Part I I1 N. Farhi, M. Goursat, and J.-P. Quadrat
In this second part we discuss the phases appearing in the fundamental diagrams of traffic systems modeled by 1-homogeneous minplus dynamics. We show the improvement obtained by traffic light control. We give a new subclass of 1-homogeneous dynamics having periodic tra jectories. It generalizes the standard cases which need a monotony property. Finally we show that the periodicity of this new, but still restrictive class, has applications to justify the existence of the fundamental diagram for regular town traffic with crossings but without turning possibilities. 1. The traffic fundamental diagram phases. The fundamental diagrams of quite different systems are similar to the one given in part I. We have studied the cases of two circular roads with one crossing and two crossings and the cases of regular towns with various number of roads on a torus. In all these cases we suppose the existence of "right priority". The fundamental diagrams have always three phases corresponding respectively to low, middle and high densities. We see on the fundamental diagram of Part I that : í for low densities the flow increases linearly with the density, í for middle densities the flow is constant, í for high density there are deadlocks and the flows are null. On Figures 1, 2 and 3 we show the typic asymptotic distribution of vehicles in the three phases (see [3, 4]). We see that :
1Partially supp orted by RFBR/CNRS grant 05-01-02807.


44
.......... .............................. . .............. ..................... ........... ....... ........ ...... ....... ...... ...... ..... ..... ..... ..... ..... ..... .... ..... .... ... ... ... .. .. .. .. ... ... ... ... ... ... ... ... ... ... ... .... ... ... .. .. .. .. .. .. .. .. . .. .. . . .. . . . .. . P . . . . . .. . . .. .. . .. . .. .. .. .. ... .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . ...... ...... ... ... ..... ..... ..... ..... ...... ...... ..... ..... ....... ....... ....... ....... ........... ........... .... ... .... ... ............................... ...............................

N. Farhi, M. Goursat, J.-P. Quadrat
...................................... ......... ....... ....... . . ..... ..... ..... ... ..... ... ... ... ... ... ... ... ... ... ... . .. .. .. .. . . . . P . . . . . . .. .. .. .. ... ... ..... ... ... ... . ... ... ... ... .... ..... ..... ..... ...... ...... ....... ....... ........... ................................... .... ................................ .. ....... ........ ... ...... ..... .. ..... ..... .... .... ... . ... ... ... ... ... .. ... ... . .. . .. .. .. .. . . . . . . . . . . .. .. .. .. ... ... ..... ... ... ... . ... ... ... ... ..... .. ..... ..... ... ..... ...... ............. ..... ........ ............. .....................
............................. ................................ . .... .. ........... ....... ......... ....... ....... ...... ...... ...... ... ...... ..... ..... ..... .... ..... .... ... ..... .... ... . .. . ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... . . ... .. .. .. .. .. .. .. .. .. . . .. . . . .. P . . .. . . .. . . ... .. . .. .. .. .. .. .. . .. .. ... ... .... ... ... ... ... ... ... ... ... . . ... ... ... ... ... ... ... ... .... .... . .. ..... ..... ..... ..... ...... .... ..... ..... ....... ...... ...... ............. .......... ........ ..... ........ ............. ........ ...... ..................... .....................

Figure 1. Two circular roads with one crossing case. Car distributions in the low, middle and high density phases.
P .................................. ................................... .......... ....... .................... .. ....... ...... ...... ......... ...... ..... ..... ..... ..... ..... .... .... ..... ..... ... ... .... .... ... ... ... ... ... .. ... ... ... ... .. .. ... ... ... ... .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . . .. .. . . .. .. . . . . . . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... .... ... ... .... . ... ..... ..... ..... ..... ..... ..... ..... ...... ......... ...... ...... ....... ....... .... ............. ............ ........................................... .......... .......................... P

P ..... ....... .... ......... ............................................. ...................... ...... ...... .... ....... ..... ...... .......... ...... ..... ..... ..... ..... .... ..... ..... .... .... .... .... ... ... ... ... ... ... .. .. .. ... ... ... ... ... .. .. ... .. ... .... .. .. .. .. .. . . .. . . . . . . . . . . . . .. .. .. .. . . .. .. . ... .. .. .... ... ... ... ... ... .. .. ... ... ... ... . . ... ... ... ... .... ..... .... ... ...... .... .... ..... ... ..... ..... ...... .................. ...... ...... ......... ....... ... .. ............................................. .................................................... P

P ................................ ................................ . .......... ...... ................ ....... ....... ...... .... .. ...... ..... ..... ...... ..... .. ..... ..... .... ..... ..... .... .. .... . .... ... ... ... ... ... ... . .. ... ... ... . ... ... ... .. .. ... .. ... .... .. .. .. .. .. .. . .. . . . . . . . . . . . . .. .. .. .. . . .. .. . ... .. .. .... ... ... ... ... ... .. .. ... ... ... ... . .. . .... .... ... ... ..... .... ... ....... .... ..... ..... ... ..... . ..... .......... .................. ...... ........ ....... .... ... ..... .......... .................................................. ............................... P

Figure 2. Four roads with two crossings. Car distributions in the low, middle and high density phases.




















Figure 3. A regular town. Car distributions in the low, middle and high density phases. § Low density phase. There are so few vehicles in the network that after a transient regime, they move without obstructing each other on the roads and in the crossings. Thus, the "priority to the right" is not used, the vehicles moves as on a unique circular


Degree one homogeneous dynamic systems: Part II

45

road and the average flow is equal to the vehicle density in the network. This phase corresponds to densities less than 1/4. § Midd le density phase. When the density is between 1/4 and 1/2 (in the symmetric road cases), the vehicles can neither move freely on the roads, nor avoid each other on the crossings. Therefore "priority to the right" happens. The cars on the priority road move freely and the waiting cars are all in the non priority road. The flow reaches the maximum value 1/4 corresponding to the full use of the crossings. § High density phase. When the density exceeds a quantity equal to 1/2 (in the symmetric case), at asymptotic regime, a closed circuit of vehicles on some nonpriority roads appear which creates a complete deadlock of the system.

2. Traffic light control. To avoid the deadlock due to the right priority we can use traffic light controls. A Petri net describing the junction with the traffic light control is shown on Figure 4. The negative weight extension of Petri net is necessary to model the light phases in a time invariant way. The part of the Petri net modeling the traffic light control corresponds to the places ag , ac , ag , ac . ïï As long as ac contains a token (ac = 1) the green light is for the North street, when ac = 1 the green light is for the East street. As long as ac = 1 ï we have ag = 1 and qv is authorized to fire (since thanks to the loop qv , ag , qv as soon as a token is consumed another one is generated in the place ag ). The main point is that when the token in ac goes in ac (phase ï change) the tokens in ag must be removed (this is done by the input arc with weight -1 of the place ag ). More generally without negative weight we cannot model tokens staying less than a prescribed time. In Figure 5, we compare the fundamental diagrams of three crossing policies for a system composed of two circular roads of same size with two junctions. The three policies are : í right priority, í standard given phase duration, í feedback controlled duration (based on the road congestion) computed by LQG method. The control improves the middle and the high density phases, without spoiling the low density one. The improvement given by the feedback control achieves the throughput obtained on a unique circular road without crossing but doubling the time spent in a place representing the crossing place.


46
q a
v-1

N. Farhi, M. Goursat, J.-P. Quadrat
q
v-1 v-1 -1 N

a

a a a
-1
g

c

c

q

E

g

q
1/2

v 1/2

a

1/2

a

2v-1

q

2v-1

q
-1

v+1 v

a

2v

a q
1

1/2 v -1

a

q

2v

a

2v-1

a

2v

Figure 4. Traffic lights modeling. The high density phase for the openloop standard traffic light control is unstable but for the time being we have not been able to find an explanation in terms of chaotic dynamics. It will be the source of future refexions. Furthermore, the feedback control dissolves more efficiently the jams (that can appear locally in transient regimes) than the other policies would do.
0.25

f

0.20

1
0.15

3 1

2

2

3

0.10

0.05

d
0.00 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

Figure 5. Comparison of three crossing policies : í right priority (1), í open loop light control (2), ífeedback light control (3).


Degree one homogeneous dynamic systems: Part II 3. A sub class of triangular homogeneous dynamics

47

In this section we study a subclass of 1-homogeneous minplus linear systems for which we can prove the periodicity. Their dynamics belongs to a subclass of 1-homogeneous triangular systems : (3.1) uk xk
+1 +1

= C uk , = A(uk ) xk B (uk ) uk .

where {uk }kN and {xk }kN are minplus column vectors, C is a minplus square matrix, A(uk ) and B (uk ) are two minplus 0-homegeneous matrices depending of uk . We call this type of systems Triangular 1-Homogeneous (T1H). We call linear periodic dynamic (LP) a dynamic given by : x
k+1

= Ek xk ,

x0 given,

where Ek are minplus matrices periodic in k . We can prove the following theorems (see the proofs in [5]). Theorem 3.1. Every T1H dynamics behaves asymptotical ly as a LP dynamics. R
min

Theorem 3.2. A T1H system with A(u) irreducible for every u satisfies : ï max ²x (u0 ) = max ²x (u),
u0 Rmin uV ï

where (u0 , x0 ) denotes the initial condition of (3.1), -²x (u0 ) is equal to limk xk /k , and V is the set of the minplus eigenvectors of the matrix C. Theorem 3.3. Every LP dynamic yk+1 = Ek yk , such that the matrices Ek have the same support, is realizable by a T1H dynamics. 4. Application to traffic We show that the traffic of regular towns with traffic light, buffered junction but without turning possibilities can be modeled with a T1H dynamics. On the Petri net of Figure 6 the traffic light is modeled by the subsystem corresponding to the transitions u1 , u2 , u3 , u4 , which has no input coming from the rest of the system. The dynamic of this subsystem is minplus linear. If the initial condition u0 = (0, 0, 0, 0) the number of tokens in the places a0 and b0 is boolean and periodic. To a cycle corresponds the four phases given in the Table 1. The junction has a buffer place in each direction (a1 , b1 ) to avoid blocking. The phases 2 and 4 gives the time,


48

N. Farhi, M. Goursat, J.-P. Quadrat

u

1

1



4

xn-

1

an-

1

an-
n

1 -1

u
2

2



u

4

x z
2

u

3

3 -1

a

0

b

1

z1 b

b
m

0

b z

m-1

b

m

a a
n

n 1

m

b

z
m-1

m-1

x

a1
x
2

Figure 6. Traffic light intersection without possibility of turning.

Phase a0 1 1 2 0 3 0 4 0

b0 0 0 1 0

Vertical light color green red red red

Horizontal light color red red green red

Table 1. The phases of the traffic light.

for car entering in the junction, to go in the buffer and then to free the crossing. Indeed, a vehicle entering in the crossing (represented by the two places an and bm ) leaves it surely in one unit of time. The green duration of phase 1 and 3 is the so journ time of tokens in the place i . The phases 2 and 4 have a duration of one unit.


Degree one homogeneous dynamic systems: Part II Proposition dynamics : § § 1 § k+1 u = § 2 § §

49

4.1. The Petri net of Figure 6 has the T1H fol lowing § § § 3 4 § k u , § §

xk+1 A1 (uk ) § xk , k+1 = k z § A2 (u ) zk

where § denotes , with A1 (u) and A2 (u)
i,j i,j

=

a0 u1 /u2 , if (i, j ) = (n, n), independent of u elsewhere. b0 u3 /u4 , if (i, j ) = (m, m), independent of u elsewhere.

=

We are able to explicit the asymptotic flows which are different according the direction followed by the vehicles. Lets us give the result in the particular case where all the phases have a duration of one time unit i = 1 for all i. Theorem 4.1. The average flow on the horizontal (resp. vertical) road is given by /4 where is the unique eigenvalue of the irreducible 3 3 k matrix k=0 A1 (uk ) [resp. k=0 A2 (u )]. Bibliography
[1] F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat : Synchronization and Linearity, Wiley, 1992. [2] M. Gondran, M. Minoux : Graphs and Algorithms, J. Wiley & Sons, 1986. [3] N. Farhi, M. Goursat, and J.P. Quadrat : Derivation of the fundamental traffic diagram for two circular roads and a crossing using minplus algebra and Petri net modeling, In Pro ceedings of the 44th IEEE - CDC-ECC Seville December 2005. [4] N. Farhi, M. Goursat, and J.P. Quadrat: Fundamental Traffic Diagrams of Elementary Road Networks, to app ear in Pro ceedings of ECC Kos July 2007. [5] N. Farhi : A class of periodic degree one homogeneous minplus systems, to appear. [6] G. Cohen, S. Gaubert and J.P. Quadrat : Asymptotic Throughput of Continuous Timed Petri Nets Proceedings of the 34th Conference on Decision and Control, New Orleans, Dec, 1995. [7] S. Gaubert : Th‡ eorie des syst‡ emes lin‡aires dans les dioides, Thesis dissertation, e ‡ Ecole des Mines de Paris, 1992.


50

F. Faye, M. Thiam, L. Truffet, E. Wagneur

Max-plus cones and semimo dules

1

F. Faye, M. Thiam, L. Truffet, and E. Wagneur
The concept of moduloè over a dioè has been introduced in [7]. These id id algebraic structures have been considered in the context of production systems [5], computer systems [9], network systems [4], or more generally for the modeling and analysis of discrete event systems [1], [8]. For G. Gondran and M. Minoux ([7]), a moduloè over a dioè is the algebraic id id structure left invariant under the action of a matrix A with entries in a dioè (the "space" of proper "vectors" of A). This structure is also very id similar to that of band-space over a belt of R.A. Cunninghame-Green [6]. The problem of solving linear equations of the type Ax = B x in the max-algebra has been considered by many authors (cf [4], and [2], where additional references may be found). In [2] the authors show how to compute all solutions to a system of linear equations over a totally ordered idempotent semifield. In [3] the authors consider subsets of the positive cone Rn endowed + with the max operator as the first composition law, together with "+ as the second composition law. They show how to relate subsets of Rn to + the concept of generating vectors and bases defined in [11]. Since the early years, the terminology evolved, and the concept of idempotent semimodule over an idempotent semiring (or semifield) has emerged as the counterpart of that of vector space or, more generally, of module over a ring. The most general definition of a (finite dimensional) idempotent semimodule M is the following one: take two matrices A, B of finite size with coefficients in a semifield S , consider the inequalities Ax B x, and then define M as the set of solutions to this set of inequalities. Another way to define (or to represent) a (finite dimensional) semimodule over S is to give its basis, for example as the (independent) columns of a matrix with coefficients in S , It is then natural to ask how to get from one representation to the other. The aim of this paper is to study n-dimensional semimodules over a completely ordered and complete idempotent semifield defined by a pair (A, B ). Recall that an idempotent semigroup (S, ) is ordered by the relation s, t S , s t s t = t. If (S, , 0) is an idempotent semigroup with the neutral element 0, then 0 is the least element of S , since for
1Research supp orted by NRC grant RGPIN-143068-05.


Max-plus cones and semimodules

51

every s S, s 0 = s. We will assume here that the set of scalars S is an idempotent completely ordered semifield, which is complete, i.e. S is totally ordered and complete, with least element 0, endowed with two composition laws: , and § such that : i) (S, ) is an idempotent commutative monoè with neutral element 0. id, ii) (S \ { 0}, §) is an abelian group -- hence (S \ {0}, §, ) is an -group í, with neutral element written 1. iii) § is distributive over , iv) 0 is absorbent (for every s S, 0 § s = 0). An idempotent semifield is also called a dioè [1]. id Next we give a brief summary of our talk. In Part 1, we state some general results on semimodules defined by a pair (A, B ). In particular, we give an explicit formula for the semimodule of solutions to a single equation ai x bi x in terms of the coefficients aij , and bij of ai and bi (here and in the sequel, scalar product is denoted by concatenation). Take a permutation i from the symmetrical group Sn such that, for j = 1, . . . , k , ai,i (j ) bi,i (j ) , while bi,i (j ) < ai,i (j ) , j = k + 1, . . . n. Let Jk (i) = {j (1 j n)| ai,i (j ) bi,i (j ) }. Clearly for every j Jk (i), ei (j ) is a solution to ai x bi x, where the ej 's are the elements of the canonical basis of S n . Also, for every j Jk (i) , Jk (i), we have: / ai, =b
i

(j )

b

i,i (j ) i,i (j )

= ai, (1 b

i

(j )

ai,i

()

(a-1i i,

( ) bi,i (j )

)= (a-1i i,
( ) bi,i (j )

i,i (j )

=b

-1 i,i ( ) ai,i ( )

)=b

i,i (j )

b

i,i ( )

).

Hence ei (j ) (a-1i ( ) bi,i (j ) )ei ( ) also satisfies ai x bi x. i, We have proved the following statement. Proposition 1. If bi < ai , then the set of solutions to ai x bi x is a semimodule Mi generated by the k (n + 1 - k ) vectors given, for every j Jk (j ), by: ei (j ) , and ei (j ) (a-1i ( ) bi,i (j ) )ei ( ) , Jk (j ). i, The semimodule Mi is generated by the columns of Vi given by the concatenation over Jk (i) of the matrices Vj (i) = [ e e
i (j ) i (j ) (

|e

i (j )

(a-1i i, )e
i (

( )

1

) bi,i (j )
i

)e

i (

1

)

|
n-k

(a-1i i,

2

) bi,i (j )

2

| § § § |e

(j )

(a

-1 i,i (

) bi,i (j )

)e

i (

n-k)

],

where { 1 , 2 , . . . , n-k } = { | Jk (i)}. / In Part 2, we give a geometric interpretation of the results of Part 1. Let Mp stand for the semimodule generated by the solutions to ap x bp x,


52

F. Faye, M. Thiam, L. Truffet, E. Wagneur
(r )

with p Sn , and Jq (p) = {r (1 r n)|ap following statement.

b

p

(r )

}. We have the

Theorem 1. For 1 k n - 1, we have Mi Mp = {0} iff one of the fol lowing conditions holds i) Jk (i) Jq (p) = ii) aip ( ) b-1 p ( ) a-1 i (j ) bi,i (j ) . p, p,
Jq (p) j Jk (i)

In Part 3, we solve the system of inequalities Ax B x using combinatorial decomposition of the inequalities ai x bi x. In particular, we show that ai x bi x is equivalent to a series of inequalities : b-1 ai1 xi1 (ai2 bi2 )x2 . . . (ain bin )xn x1 or i1 b-1 (ai1 bi1 )x1 ai2 x2 (ai3 bi3 )x3 . . . (ain bin )xn x2 or i2 ...... or b-1 (ai1 bi1 )x1 . . . ain xn xn . in The first inequality may be written in matrix form (add the trivial inequalities x2 x2 , . . . , xn xn ) as: Pi1 x x, with -1 bi1 ai1 b-1 (ai2 bi2 ) § § b-1 (ain bin ) i1 i1 0 1 0§ 0 Pi1 = 0 0 1§ 0 § §§§ §§ § 0 § §§ 1 It is well-known that Pi1 x x Pi x = x. This equation has a 1 nontrivial solution iff ai1 bi1 , and in this case the solutions are given by the columns of Pi . 1 Proceeding similarly for each line, we get P2 , . . . , Pn , and all solutions lie in the concatenation [Pi1 |Pi2 | . . . |Pin ]. Then we look at all the intersections of the type Pik Pj , etc. in a combinatorial way, and devise an algorithm for the solution to these systems of inequalities. Finally, we give a complete description, both algebraic and geometric, for cases n = 2, 3. Bibliography
[1] F. Baccelli, G. Cohen, G.J. Olsder, and J-P. Quadrat. Synchronization and Linearity. John Wiley and Sons, 1992. [2] P. Butkovi, and G. Hegedus An Elimination Metho d for Finding All soluc è tions of the System of Linear Equations over an Extremal Algebra, EconomickoMatematick‡ Obzor, 20, 1984, 203-215. y


Max-plus cones and semimodules

53

[3] P. Butkovi H. Schneider, and S. Sergeev, Generators, extremals and bases of c, max-cones, Linear Algebra and its Applications, 421, 2007, 394-406. [4] B. A. Carr‡ An algebra for Networks Routing problems J. Inst. Math Appl.7, 1971, e 273-294. [5] G.Cohen, D. Dubois, J.P. Quadrat, and M. Viot, A Linear System Theoretic View of Discrete-Event Pro cesses and its use for Performance Evaluation in Manufacturing, IEEE Trans. on Automatic Control, ACí30, 1985, 210í220. [6] R.A. Cunninghame-Green, Minimax Algebra , Lecture Notes in Economics and Mathematical Systems, 166, Springer Verlag, 1979. [7] M. Gondran, and M. Minoux Valeurs propres et vecteurs propres dans les dioè ides et leur interpr‡ etation en th‡ eorie des graphes. E.D.F. Bul letin de la Direction des ‡ Etudes et Recherches. S‡ erie C-Math. Info., #2 ,1977, pp. 25í41. [8] V. Kolokoltsov, and V. Maslov, Idempotent Analysis and its Applications, Mathematics and its Applications, Kluwer, 1997. [9] C.E.Leiserson and J.B. Saxe, Optimizing synchronous systems, Journal of VLSI and compiuter systems, 1, 1983, 41-67. ‡ [10] P. Moller, Th‡ eorie alg‡ ebrique des syst` emes a ‡ ‡ ` evenements discrets. Th` ese, Ecole des Mines de Paris, Paris, 1988. [11] E. Wagneur, Mo duloids and Pseudomodules. 1. Dimension theory Discrete ematics, 98, 1991, 57-73. [12] E. Wagneur, Dequantisation: Direct and Semi-direct Sum Decomp osition of p otent Semimo dules. í In: G.L. Litvinov and V.P. Maslov (eds.), Idempotent ematics and Mathematical Physics, Contemporary Mathematics, 377, 2005, 339-352. MathIdemMathpages

Duality of cluster varieties V.V. Fock and A.B. Goncharov
Cluster variety is an algebraic variety (strictly speaking, a scheme) defined by combinatorial data by explicit set of coordinate charts and transition functions. More precisely, for any collection of combinatorial data, called seed one associates three varieties A|I| , X|I| , and D|I| . These varieties possess canonical pre-symplectic, Poisson and symplectic structures, respectively. One defines also a discrete group D|I| acting on all the three types of varieties and preserving the respective structures. The manifolds X|I| and D|I| admit a quantisation (noncommutative deformation of the algebra of functions) which is also D|I| -invariant. Varieties admitting cluster descriptions are simple Lie groups, moduli spaces of Stokes parameters, moduli of flat connections on Riemann surfaces, configuration spaces of flags, Teichmuller spaces and their genè eralisations, the spaces of measured laminations and some others. One of the important features of cluster varieties is that they are defined not only


54

V.V. Fock, A.B. Goncharov

over a field but also over semifields (semigroups w.r.t. addition and groups w.r.t. the multiplication). For example, one can consider Teichmuller è space, space of measured laminations and the space of flat P S L(2, F)connections over a surface as the same cluster manifold but defined over the semifield R>0 of positive real numbers, tropical semifield Rt (which is ordinary R as a set with maximum for the addition operation and ordinary addition for the multiplication), and a field F, respectively. Let us give the precise definitions: A cluster seed, or just seed, I is a quadruple (I , I0 , , d), where i) I is a finite set; ii) I0 I is its subset; iii) is a matrix ij , where i, j I , such that ij Z unless i, j I0 . iv) d = {di }, where i I , is a set of positive integers, such that the matrix ij = ij dj is skew-symmetric. The elements of the set I are called vertices, the elements of I0 are called frozen vertices. The matrix is called exchange matrix, the numbers {di } are called multipliers, and the function d on I whose value at i is di is called multiplier function. We omit {di } if all of them are equal to one, and therefore the matrix is skew-symmetric, and we omit the set I0 if it is empty. An isomorphism between two seeds is a map I = (I , I0 , , d) and I = (I , I0 , , d ) is an isomorphism of finite sets : I I such that (I0 ) = I0 , d(i) = di and i ,j = ij . Observe that the automorphism group of a seed may be nontrivial. For a seed I we associate a torus XI = (F½ )I , called X -torus, another torus AI = (F½ )I , called X -torus and the third one DI = (F½ )I ½I called D-torus or a double torus. We denote the standard coordinates on these tori by {xi |i I }, {ai |i I } and {yi , bi |i I }, respectively. The X -torus is equipped with the Poisson structure (1) {xi , xj } = ij xi x
j

The A-torus is equipped with the pre-symplectic structure (closed 2form possibly degenerate) (2) = 1 2
i,j ij

dai da ai aj

j

The D-torus is equipped with the symplectic form (3) D = 1 2
i,j ij

dbi dbj + bi bj

d- i
i

1

dbi dyi bi yi


Duality of cluster varieties

55

The inverse of this form is a nondegenerate Poisson structure which can be written as (4) {yi , yj } = ij yi yj ,
i {yi , bj } = j di yi bj ,

{bi , bj } = 0

Observe that these sructures are constant in logarithmic coordinates. Isomorphism between two X -tori XI and XI is a map given in coordinates by x(i) = xi , where is an isomorphism of the seeds. Observe that there are much less isomorphisms of X -tori then just isomorphisms of the corresponding Poisson manifolds. Isomorphisms of A- and D-tori are defined analogously. There exist the following maps between the tori: (5) AI XI , xi =
j

aj ij ;




(6)

AI ½ AI DI ,

yi =
j

aj ij ,

bi = ai /ai , ~

Here ai are coordinates on the second AI -factor. ~ (7) and (8) DI XI , xi = yi
j

DI XI ,

xi = yi ,
j

b

ij

.

All the maps are compatible with the respective symplectic, pre-symplectic and Poisson structures. Namely the map (5) is a composition of the quotient by the kernel of the pre-symplectic form and a symplectic map to a symplectic leaf. The map (6) maps the symplectic form to the pre-symplectic one. The map (7) is Poisson, the map (8) is anti-Poisson (Poisson with the opposite Poisson structure on the X -torus). The maps (7) and (8) are dual to each other in the sense on Poisson pairs. Let I = (I , I0 , , d) and I = (I , I0 , , d ) be two seeds, and k I - I0 . A mutation in the vertex k is an isomorphism ²k : I I satisfying the following conditions: § ²k (I0 ) = I0 , § d²k (i) = di , § ²
k

(i)²k (j )

-ij ij = ij + ik |kj |

if i = k or j = k otherwise if ik kj < 0 if ik kj 0


56

V.V. Fock, A.B. Goncharov

Two seeds related by a sequence of mutations are called equivalent. Mutations induce rational maps between the corresponding seed tori, which are denoted by the same symbol ²k and are given by the formulae -1 xk = x (1 + xk )ik i xi (1 + (xk )-1 ) if if if i=k ik 0 . ik 0

x² for the X -torus,

k

(i)



ik

a²

k

(i)

=



a
j |
jk

j

jk

+
j |
jk

aj
<0

-

jk

>0

ak ai

jk

if i = k if i = k
-1 j |
jk

for the A-torus and - (1 + xk ) b²k (i) = y

1 j |
jk

bj
>0

+ (1 + (xk )-1 ) bk b
i

b
<0

- j

jk

if i = k if i = k

²k (i)

-1 yk = y (1 + yk )ik i yi (1 + (yk )-1 )

ik

if if if

i=k ik 0 . ik 0

for the D-torus. Since in the sequel we shall extensively use compositions of mutations called also cluster transformations we would like to introduce a shorthand notation for them. Namely, we denote an expression ²²i (j ) ²i by ²j ²k , ²²²i (j) ²i (k) ²²i (j ) ²i by ²k ²j ²i , and so on. Mutations have the following properties (valid for mutation of seeds as well as for mutations of respective tori): § Every seed I = (I , I0 (I - I0 ) mutations. A1 : ²i ²i = id A1 ½ A1 If ij = j i = 0 then A2 : If ij = -j i = -1 pentagon relation.) B2 : If ij = -2j i = -2 G2 : If ij = -3j i = -3 , , d) seed is related to other seeds by exactly

²i ²j ²j ²i = id. then ²i ²j ²i ²j ²i = id. (This is called the then ²i ²j ²i ²j ²i ²j = id. then ²i ²j ²i ²j ²i ²j ²i = id.


Duality of cluster varieties

57

By id we mean here an isomorphism of the seeds or tori. Conjecturally all relations between mutation follow from these ones. Given a seed one can produce a (I - I0 ) seeds by mutations. Continuing this procedure one obtains a (I - I0 )-valent tree whose vertices are seeds (or seed tori) and edges are pairs of mutually inverse mutations. Obviously if we start from any other seed from the tree we obtain the same tree. Every two tori of the tree are related by exactly one composition of mutations. Call two points of two different tori equivalent if they are related by the composition of mutations. The cluster manifold (denoted by X|I| , A|I| or D|I| depending on which kind of tori are used) is the affine closure of disjoint union of the tori quotiented by the equivalence relation. Each particular seed tori can be considered as a coordinate chart of the corresponding cluster manifolds and compositions of mutations can be considered as transition functions between the charts. Mutations respect the Poisson structure when acting on X tori, presymplectic structure when acting on A-tori and symplectic when acting on D-tori. Thus the cluster manifolds X|I| , A|I| and D|I| acquire the respective structures. (In fact the formula for mutation of the matrix can be considered as a corollary of this property and the mutation formulae for, say, X -tori). Mutations commute with the maps (5),(6),(7) and (8) thus these maps are defined between the respective cluster varieties compatible with presymplectic, symplectic and Poisson structures thereof. Mutations are rational maps with positive integral coefficients and thus the cluster manifold can be defined not only over a field but over any semifield as well. For semifields without -1 (like the semifields of positive real numbers or the tropical semifields) the mutations are isomorphisms and thus the whole manifold is isomorphic to every coordinate torus. The symmetry group D|I| of a cluster manifold permuting the seed tori is called the (generalised) mapping class group of the cluster manifold. The name comes from the case of Teichmuller space, when this group is the acè tual mapping class group. The group depends on the equivalence class of a seed only and is common for cluster manifolds of types X , A and D. Every sequence of mutations together with an isomorphism of the initial and the final seed gives an element of the mapping class group. Conversely, given a seed, every mapping class group element can be presented by a sequence of mutations starting from the given seed together with the isomorphism between the final seed and the initial one. Two sequences of mutations different by the relations A1 íG2 correspond to the same mapping class group elements.


58

V.V. Fock, A.B. Goncharov

Consider the ring of algebraic functions on a cluster manifold in more details. The ring of algebraic functions O(XI ) (resp. O(DI ), O(AI )) on every torus is the ring of Laurent polynomials of cluster variables. This ring contains a subring of Laurent polynomials with integral coefficients OZ and a semiring of Laurent polynomials with positive integral coeffiZ cients O>0 also depending of course of the seed and of the type of the torus. A cluster transformation in general does not presereve the ring O since it is birational. The ring of algebraic functions on the whole cluster manifold is the intersection of inverse images of the rings O under all possible cluster transformations of a seed tori. In other words the ring O consists of Laurent polynomials which stay Laurent under all possible cluster transformations. The celebrated result of Fomin and Zelevinsky called Laurent phenomenon claims that for any cluster variety A|I| of type A the coordinate functions belong to the ring OZ . The ring O contains a subring Z OZ and a subsemiring O>0 . The latter is additively generated by Laurent polynomials from O with positive integral coefficients indecomposable into Z a sum of two such polynomials. Such elements of the semiring O>0 are called irreducibles. The main conjecture, proven for a sufficiently wide class of cluster manifolds describes the structure of the set of irreducible Laurent polynomials: § The set of irreducible Laurent polynomials is O. § The set of irreducible Laurent polynomials for X|J| (resp. A|I| , D|I| ) is canonically isomorphic of the cluster variety A|I| (Zt ) (resp. X|I| (Zt ), a basis in the ring the cluster variety to the set of points D|I| (Zt )).

One can consider this property as a duality between cluster varieties of type X (resp. A, D) and the tropical cluster varieties of type A, X and D, respectively. The correspondence between irreducible Laurent polynomials and points of the dual tropical variety is especially simple for the variety of type X . In this case the coordinates of the corresponding point of the tropical variety are given by multidegree of the highest term of the corresponding Laurent polynomial. Example Let us consider the simplest nontrivial example: the seed I = {I , } with I = {1, 2} and 12 = 1. There are exactly 5 isomorphism classes of seed tori equivalent to a given one, however all the five seeds are isomorphic, thus the mapping class group is Z/5Z.


Duality of cluster varieties

59

The simplest geometric meaning has the space X . It is the space of 5-tuples of points (p1 , . . . , p5 ) on the pro jective line P 1 such that pi = pi+1 (mod 5) and modulo the automorphisms of P 1 . The 5-tuple of coordinate systems on this space is numerated by triangulations of the pentagon with vertices 1, . . . , 5. For every internal diagonal one associates the crossratio of the four points of the quadrilateral which this diagonal cuts into halves. Mutations correspond to removing a diagonal and replacing it by another one of the quadrilateral. The same variety over R>0 is the configuration space of 5-tuples of points on RP 1 with prescribed cyclic order. The A-space is the space of collections of 10 nonvanishing vectors v1 , . . . , v10 in F2 equipped with a nonzero bivector V ol. The collections are considered up to the action of the group S L(2, F) of linear transformations preserving V ol and sub ject to the relations vi = -vi+5 (mod 10) and vi vi+1 (mod 10) = V ol. The map X|I| X|I| is given by the obvious pro jection of F2 - {0} P 1 . For the internal diagonal of the pentagon with ends i and j one associates the coordinate vi vj /V ol. The D variety is the space of flat S L(2, F) connections on a sphere with 5 different points on the equator removed with parabolic monodromy around these points. Consider the associated vector bundle and choose a monodromy invariant section about each singular points. Then trivialise the bundle over the northern hemisphere. The five chosen sections give five vectors v1 , . . . , v5 in F2 . The same procedure over the southern hemisphere gives five vectors w1 , . . . , w5 in another copy of F2 . Given a triangulation of the pentagon we associate to every internal diagonal two coordinates x and b. The coordinate x is just the cross ratio of four points in P 1 defined by the vectors vi standing at the corners of the quadrilateral cut by the diagonal (just like for the X -space). The coordinate b is given by b = (vi vj )/(wi wj ), where i and j are the ends of our diagonal. The two pro jections to the X variety are obviously given by pro jectivising the collections of vectors {vi } and {wi }, respectively. The same manifold over R>0 can be identified with the space of complex structures on a sphere with five punctures on the equator. Given a triangulation of the pentagon one can describe the basis of the ring OZ of the corresponding X -variety explicitly as a set of Laurent polynomials Pa,b (x, y ) of two variables x, y parameterised by two integers a, b as follows:


60

St‡ ephane Gaubert

P

a,b

a xy a xy xa y (x, y ) = a xy a xy

b b b b b

(1 (1 (1 (1

+ + + +

x-1 x-1 y -1 y -1

) -b )-b (1 + y -1 + x-1 y -1 )a ) (1 + y -1 + x-1 y -1 )a-b )a

if if if if if

a a a a b



0, 0, 0, b a

b b b

0 0 0 0 0

One can easily check that this set of Laurent polynomials is invariant under simultaneous mutation of the variables x, y and of the variables a, b. Bibliography
[1] V.V. Fock, A.B. Goncharov Cluster X-varieties, amalgamation and Poisson-Lie groups, n Algebraic Geometry Theory and Number Theory, Birkhè auser, Progress in math. Vol. 253, 2006, arXiv:math.RT/0508408 [2] V.V. Fo ck, A.B. Goncharov The quantum dilogarithm and unitary representations of the cluster mapping class groups, arXiv:math/0702397

From max-plus algebra to non-linear Perron-Frob enius theory: an approach to zero-sum rep eated games1 St‡ ephane Gaubert
This talk is based essentially on two joint works, with Akian and Nussbaum [AGN07], on the one hand, and with Akian and Lemmens [AGL07], on the other hand. 1. Intro duction The analysis of zero-sum repeated games by the dynamic programming method classically leads to studying discrete time dynamical systems of the form (1.1) v (k , §) = f (v (k - 1, §)) where the map f is order preserving. Here, v (k , §) is the value function, which associates to any initial state the value of the corresponding game in horizon k . The map f is the "one day" dynamic programming operator. The case of a finite state space is already interesting. Then, denoting by n the number of states, we may identify the value function to a vector in Rn , and the map f to a self-map of Rn .
1This work was partially supp orted by the joint RFBR/CNRS grant 05-01-02807


Max-plus approach to zero-sum repeated games

61

The explicit form of f depends on the details of the game. However, the map f may be written abstractly as: (1.2) f (v ) = inf sup r


+P



v,

where the infimum is taken over the strategies of the first player and the supremum is taken over the strategies of the second player, r Rn is a vector of payments, and P is a n ½ n nonnegative matrix. In the case of games with undiscounted payoff, the matrices P are stochastic. When there is a positive discount rate, or when the game may halt with a positive probability, the matrices P are substochastic. These (sub)-stochasticity properties imply that f is nonexpansive in the sup-norm, meaning that f (v ) - f (w)


v-w



.

The relevance of the order and nonexpansiveness properties to control and game problems has been brought to light by several authors, see in particular [CT80, Kol92, RS01, Ney03]. The dynamic programming operators (1.2) may be thought of as generalizations of linear positive maps in several different ways. First, linear maps of the form x P x, where P is a (sub)stochastic matrix, correspond to the zero-player case, in which every player has only one possible strategy, if we assume in addition that the payments are zero. Another special situation concerns the deterministic one player case, in which one of the two players has only one possible strategy, and the entries of the matrices P are only 0 or 1. Then, f becomes an affine map over the min-plus or max-plus semiring. Further connections with Perron-Frobenius theory become apparent when using a familiar tropical instrument, the "logarithmic/exponential" glasses or "dequantization", as in [LMS01, Vir01]. This leads us to consider the conjugate map: g = exp f log where log denotes the map from the interior of the standard positive cone Rn := {x Rn | x 0} to Rn which does log entrywise, and exp := log-1 . + Then, the map g is an order preserving self-map of the interior of Rn , and it + is positively homogeneous or subhomogeneous of degree one, meaning that g (tx) = tg (x) or g (tx) tg (x) for all scalars t 1 and for all x int Rn . + Such maps belong to non-linear Perron-Frobenius theory, which deals with the nonlinear extensions of the spectral theory of positive linear maps. We refer the reader to [Nus88] for a general account of this topic and for references. I will present some results concerning zero-sum games, which have been obtained by exploiting methods from non-linear Perron-Frobenius


62

St‡ ephane Gaubert

theory with a max-plus or tropical point of view. The main results are taken from the two joint works [AGN07, AGL07]. 2. Nonlinear sp ectral radius of dynamic programming op erators The classical notion of spectral radius has been extended to nonlinear maps in several ways [MPN02]. We assume here that g is a continuous positively homogeneous of degree one map leaving invariant a (closed, convex, pointed) cone C in a Banach space X , and that g preserves the order induced by C , which is such that x y if y - x C . Bonsal l's cone spectral radius of g is defined by: rC (g ) = lim g ~
k k 1/k C

where, for all continuous, positively homogeneous of degree one self-maps h of C , h(x) . h C := sup x xC \{0} Another natural definition of the spectral radius arises when considering the nonlinear eigenproblem: g (u) = u where the nonlinear eigenvector u belongs to C \ {0}, and the nonlinear eigenvalue is a nonnegative number. The cone eigenvalue spectral radius, rC (g ), is by definition the maximal nonlinear eigenvalue . Under some ^ assumptions involving measures of non-compactness, it has been shown in [MPN02] that rC (g ) = rC (g ). Other useful notions of spectral radius, ~ ^ which coincide with the previous ones under reasonable assumptions, are studied in [MPN02]. We shall discuss here the related notion of Col latz-Wielandt number, which is obtained by considering super-eigenvectors in the interior of the cone instead of eigenvectors in the closed cone: rC (g ) := inf { > 0 | u int C, g (u) u} . ï The term "Collatz-Wielandt number" arises from Wielandt's proof of the finite dimensional Perron-Frobenius theorem, in which the same formula is seen to characterize the Perron root of an irreducible nonnegative matrix. The main result of [AGN07] shows that rC (g ) = rC (g ), when the ~ ï cone C is normal, and when g satisfies some compactness assumptions. We apply these tools to dynamic programming maps of the form (1.2), when the payments r are 0, so that f is positively homogeneous of degree one. Under some standard assumptions (compactness of the action


Max-plus approach to zero-sum repeated games

63

spaces, continuous dependence of the reward and transition probabilities in the actions), which imply that the infimum and supremum are attained in (1.2) for all v , it is shown in [AGN07] that (2.1) rC (f ) = rC (f ) = rC (f ) = inf sup r(P ~ ^ ï


)

where C = Rn , and r(P ) denotes the Perron root of P . + We derive from the previous result an explicit formula for the geometrical convergence rate of the iterates of the dynamic programming map f , this time with nonzero payments r . To this end, we use the notion of subdifferential. Maps of the form (1.2) may not be differentiable, in particular, if the action spaces are finite, f is piecewise affine. However, f may often be assumed to be semidifferentiable, meaning that for all v and h, we can write f (v + h) = f (v ) + fv (h) + o( h ), where fv , the semidifferential of f at point v , is a continuous positively homogeneous of degree one map, which is defined uniquely by the latter property. When f is of the form (1.2), it can be shown that under fairly general assumptions, the semidifferential fv at point v exists, and is given by: fv (h) =
(v ) (v , )

inf

sup

P



h,

where (v ) denote the set of policies and for all , (v , ) denotes the set supremum in the internal term in (1.2). and sup commute.) We show that if f has a fixed point

which attain the infimum in (1.2), of strategies which attain the (We need not assume that the inf v Rn , and if

:= max(rC (fv ), r-C (fv )) < 1 , then any orbit of f converges to v at a geometric rate which is bounded from above by (this bound is tight). We eventually get the following explicit convergence rate: = max( inf
(v ) (v , )

sup

r (P



), sup

(v ) (v , )

inf

r (P



)) .

3. Order preserving convex functions The techniques of the previous section are mostly appropriate when f has a unique fixed point, perhaps up to an additive or multiplicative constant. Therefore, a basic problem is to give a complete description of the fixed point set of the map (1.2). As a partial answer, a precise description of the set of stable fixed points is given in [AGL07], when the map f is


64

St‡ ephane Gaubert

convex (this corresponds to the one player case). This extends our earlier results [AG03] which concerned the undiscounted case. Here, we do not require any more the matrices P in (1.2) to be (sub)stochastic. In other words, we allow the possibility of a negative discount rate. Despite its apparently unphysical nature, negative discount is of practical interest: for instance, the study of static analysis problems by abstract interpretation [GGTZ07] leads to fixed point problems involving maps which are always order preserving but not necessarily nonexpansive in some norm. Another motivation may come for fixed point problems for polynomials with positive coefficients, leading to maps like: fi (v ) = log(
j N
n

aij exp(j § v )),

where for all 1 i n, (aij )j Nn is an almost zero family of real nonnegative numbers. A convenient notion of stability, in the present setting, is the following one: we say that a fixed point v is -stable if every orbit of the semidifferential fv is bounded from above. It can be checked that a Lyapunov stable fixed point is -stable. Recall that a (communication) class of a nonnegative matrix P is by definition a strongly connected component of the digraph of P . We say that a class is critical if the corresponding principal submatrix of P has Perron root 1. The critical graph of P is the union of the subgraphs of the graph of P induced by the critical classes. If v is a -stable fixed point of f , we define the critical graph of f , Gc (f ) to be the union of the critical graphs of the matrices in the subdifferential f (v ) := {P | f (w) - f (v ) P (w - v ), w} . Of course, f (v ) depends on v , but Gc (f ) is independent of the choice of the -stable fixed point v . The critical nodes of f are defined to be the nodes of Gc (f ). We show in [AGL07] that a -stable fixed point is uniquely determined by its restriction to the set of critical nodes. Moreover, the restriction to the critical nodes allows us to identify the set of -stable fixed points of f to a convex inf-subsemilattice of Rp , where p is bounded by the number of critical nodes. Some dynamical information, including a characterization of the possible lengths of " -stable" periodic orbits of f , is also derived in [AGL07]. The results of [AG03, AGL07] concern the one player case but have applications to the two player case. Indeed, the representation of the fixed point set has been used in [CTG06] to design a policy iteration


Max-plus approach to zero-sum repeated games

65

algorithm for zero-sum two player stochastic games. It allows one to handle "degenerate" iterations, in which the policies which are selected yield dynamic programming maps with several fixed points. Some other applications of these ideas, to static analysis of programs, are presented in [CGG+ 05, GGTZ07].

Bibliography
M. Akian and S. Gaub ert. Sp ectral theorem for convex monotone homogeneous maps, and ergo dic control. Nonlinear Anal., 52(2):637í679, 2003. [AGL07] M. Akian, S. Gaubert, and B. Lemmens. Stable perio dic p oints of discrete convex monotone dynamical systems. 2007. preprint. [AGN07] M. Akian, S. Gaubert, and R. Nussbaum. The Collatz-Wielandt theorem for order-preserving homogeneous maps on cones. 2007. preprint. [CGG+ 05] A. Costan, S. Gaubert, E. Goubault, M. Martel, and S. Putot. A policy iteration algorithm for computing fixed p oints in static analysis of programs. In Proceedings of the 17th International Conference on Computer Aided Verification (CAV'05), LNCS, pages 462í475, Edinburgh, July 2005. Springer. doi:10.1007/11513988 46. [CT80] M. G. Crandall and L. Tartar. Some relations between non expansive and order preserving maps. Proceedings of the AMS, 78(3):385í390, 1980. [CTG06] J. Co chet-Terrasson and S. Gaub ert. A p olicy iteration algorithm for zerosum sto chastic games with mean payoff. C. R. Math. Acad. Sci. Paris, 343(5):377í382, 2006. [GGTZ07] S. Gaubert, E. Goubault, A. Taly, and S. Zennou. Static analysis by policy iteration in relational domains. In Proc. of the 16th European Symposium on Programming (ESOP'07). Springer, Octob er 2007. to appear in the LCNS series. [Kol92] V. N. Kolokoltsov. On linear, additive and homogeneous operators in idempotent analysis. In V. P. Maslov and S. N. Samborski editors, Idempotent i, analysis, volume 13 of Advances In Soviet Mathematics. Amer. Math. Soc., Providence, 1992. [LMS01] G. L. Litvinov, V. P. Maslov, and G. B. Shpiz. Idempotent functional analysis: an algebraical approach. Math. Notes, 69(5):696í729, 2001. Also eprint arXiv:math.FA/0009128. [MPN02] J. Mallet-Paret and Roger Nussbaum. Eigenvalues for a class of homogeneous cone maps arising from max-plus operators. Discrete and Continuous Dynamical Systems, 8(3):519í562, July 2002. [Ney03] A. Neyman. Stochastic games and nonexpansive maps. In Stochastic games and applications (Stony Brook, NY, 1999), volume 570 of NATO Sci. Ser. C Math. Phys. Sci., pages 397í415. Kluwer Acad. Publ., Dordrecht, 2003. [Nus88] R. D. Nussbaum. Hilbert's pro jective metric and iterated nonlinear maps. Memoirs of the AMS, 75(391), 1988. [RS01] D. Rosenb erg and S. Sorin. An operator approach to zero-sum rep eated games. Israel J. Math., 121:221í246, 2001. [AG03]


66
[Vir01]

S. Gaubert, S. Sergeev
O. Viro. Dequantization of real algebraic geometry on logarithmic pap er. In European Congress of Mathematics, Vol. I (Barcelona, 2000), volume 201 of Progr. Math., pages 135í146. Birkhè auser, Basel, 2001.

Cyclic pro jectors and separation theorems in idemp otent semimo dules1 St‡ ephane Gaubert and Serge Sergeev i
1. Intro duction In an idempotent semiring, there is a canonical order relation, for which every element is "nonnegative". Therefore, idempotent semimodules have much in common with the semimodules over the semiring of nonnegative numbers, that is, with convex cones [6]. One of the first results based on this idea is the separation theorem for convex sets over "extremal algebras" proved by K. Zimmermann in [8]. Generalizations of this result were obtained in a work by S.N. Samborski and G.B. Shpiz [7] and in works i by G. Cohen, J.-P. Quadrat, I. Singer, and the first author [1], [2]. The main result of this paper, Theorem 4.3, shows that in the setting of finite-dimensional semimodules over max-plus semiring, several closed subsemimodules which do not have common nonzero points can be separated from each other. This means that for each of these subsemimodules, we can select an idempotent halfspace containing it, in such a way that these halfspaces also do not have common nonzero points. Even in the case of two semimodules, this statement has not been proved in the idempotent literature. Indeed, the earlier separation theorems deal with the separation of a point from an (idempotent) convex set or semimodule, rather than with the separation of two convex sets or semimodules. In order to prove the main result, Theorem 4.3, we investigate the spectral properties of idempotent cyclic pro jectors. By idempotent cyclic pro jectors we mean finite compositions of certain nonlinear pro jectors on idempotent semimodules. The continuity and homogeneity of these nonlinear pro jectors enables us to apply to their compositions, i.e. to the cyclic pro jectors, a result of R.D. Nussbaum[5] (non-linear Perron-Frobenius
Supported by the RFBR grant 05-01-00824 and the joint RFBR/CNRS grant 05-01-02807.
1


Cyclic pro jectors and separation theorems

67

theory). We also show that the orbit of an eigenvector of a cyclic projector maximizes a certain ob jective function. We call this maximum the Hilbert value of semimodules, as it is a natural generalization of Hilbert's pro jective metric, and characterize the spectrum of cyclic pro jectors in terms of these Hilbert values (Theorem 4.2). Our main results apply to the finite-dimensional semimodules over max-plus semiring. Some of our results still hold in a more general setting, see Sect. 3. However, the separation of several semimodules in such a generality remains an open question. The results of this paper are presented as follows. Sect. 2 describes the main assumptions, and some preliminary notions and facts that will be used in the paper. Sect. 3 is devoted to the results obtained in the most general setting, with respect to the assumptions of Sect. 2. The main results are obtained in Sect. 4. They include separation of several semimodules and characterization of the spectrum of cyclic pro jectors. The proofs of our results are contained in [3], which is an extended version of this text.

2. Preliminaries We recall that a semiring (essentially, a ring without subtraction) is called idempotent, if its addition is idempotent:a a = a. The order relation mentioned above is given by a b = b a b. An example of idempotent semiring that will be important to us is Rmax,m , it is the set of nonnegative numbers R+ equipped with operations a b := max(a, b) and a b = a ½ b. It is isomorphic to the max-plus semiring (the set R - equipped with a b := max(a, b) and a b = a + b). The "spaces" over semirings are called semimodules. An idempotent semiring or an idempotent semimodule will be called b-complete, following [4], if it is closed under the sum (i.e. the supremum) of any subset bounded from above, and if the multiplication distributes over such sums. We shall consider semirings K and semimodules V over K that satisfy the following assumptions: (A0): the semiring K is a b-complete idempotent semifield, and the semimodule V is a b-complete semimodule over K; (A1): for all elements x and y = 0 from V , the set { K | y x} is bounded from above. Note that both assumptions are true for the semimodules KI of Kvalued functions on a set I , where K is a b-complete semifield.


68

S. Gaubert, S. Sergeev Assumptions (A0, A1) imply that the operation

(2.1)

x/y = max{ K | y x}.

is defined for all elements x and y = 0 from V . Definition 2.1. A subsemimodule V of V is a b-(sub)semimodule, if V is closed under the sum of any of its subsets bounded from above in V . Let V be a b-subsemimodule of the semimodule V . Consider the operator PV defined by (2.2) PV (x) = max{u V | u x},

for every element x V . Here we use "max" to indicate that the least upper bound belongs to the set. The operator PV is a projector onto the subsemimodule V , as PV (x) V for any x V and PV (v ) V for any v V. In idempotent geometry, the role of halfspace is played by the following ob ject. Definition 2.2. A set H given by (2.3) with u, v R
n max,m

H = {x | u/x v /x} {0} , u v , will be called (idempotent) halfspace.

Any halfspace is a semimodule. If V = Kn , an n-dimensional semimodule over K, and all coordinates of u and v are nonzero, then we have that (2.4) H = {x |
{1,...,n}

xi u

-1 i


{1,...,n}

xi v

-1 i

}.

The following theorem is a version of idempotent separation theorems [1, 2], see also [4]. Theorem 2.1. Let V be a b-complete subsemimodule of V and let u V be not in V . Then the set H = {x | PV (u)/x u/x} {0} contains V but not u. For any subsemimodule V and y V , we denote (2.5) V y = {x V | y /x > 0}.

It is a subsemimodule of V .


Cyclic pro jectors and separation theorems

69

Definition 2.3. A vector x is called archimedean, if x/y > 0 for all y V . A subsemimodule of V is called archimedean, if it contains archimedean vectors. A halfspace H defined by (2.3) will be called archimedean if both u and v are archimedean. Obviously, Def. 2.3 makes sense only under (A2): The semimodule V has an archimedean vector. This assumption is true in particular for the semimodules of type Kn . In these semimodules we have that y /x > 0 if and only if the support of x, i.e. the set supp(x) = {i | xi = 0}, is a subset of supp(y ) (the support of y ). In this case V y has the form (2.6) V
M

= {x V | supp(x) M },

for some index set M . A vector in Kn is archimedean if and only if it is positive. Regular halfspaces in this case are given by (2.4). 3. General results We shall study cyclic pro jectors, that is, compositions of pro jectors P
V
k

§ § § PV 1 ,

where V1 , . . . , Vk are b-subsemimodules of V . We assume (A0, A1), which means in particular that K is an idempotent semifield. For the notational convenience, we will write Pt instead of PVt . We will also adopt a convention of cyclic numbering of indices of pro jectors and semimodules, so that Pl+k = Pl and Vl+k = Vl for all l. Definition 3.1. Let x1 , . . . , xk be nonzero elements of V . The value dH (x1 , . . . , xk ) = (x1 /x2 ) (x2 /x3 ) . . . (xk /x1 ). will be called the Hilbert value of x1 , . . . , xk . The Hilbert value of two vectors x1 , x2 was studied in [1]. For two comparable vectors in Rn ,m , that is, for two vectors with common support max M it is given by dH (x1 , x2 ) = min (x1 (x2 )-1 x2 (x1 ) i i j j
i,j M -1

),

so that - log(dH (x1 , x2 )) coincides with Hilbert's pro jective metric H (x1 , x2 ) = log( max (x1 (x2 )-1 x2 (x1 ) i i j j
i,j M -1

)) = - log(dH (x1 , x2 )).


70

S. Gaubert, S. Sergeev

Definition 3.2. The Hilbert value of k subsemimodules V1 , . . . , Vk of V is defined by dH (V1 , . . . , Vk ) = sup
x1 V1 ,...,xk V
k

dH (x1 , . . . , xk )

We establish two results on the spectrum of cyclic pro jectors and on their iterations. Theorem 3.1. Suppose that the operator Pk . . .P1 has an eigenvector y with eigenvalue , and define xi = Pi . . . P1 y . Then ï
y = dH (V1y , . . . , Vk ) = dH (x1 , . . . , xk ). ï ï

Theorem 3.2. For any sequence of nonzero vectors {xi , i = 1, . . .} such that x1 V1 and xi = Pi xi-1 for i = 2, . . ., the Hilbert value dH (xl+1 , . . . , xl+k ) is nondecreasing with l. The following is an extension of Theorem 2.1, under assumptions (A0- A2). Theorem 3.3. Suppose that V1 , . . . , Vk are b-closed semimodules and that Pk . . . P1 has an archimedean eigenvector y with nonzero eigenvalue . The fol lowing are equivalent: (1) there exists an archimedean vector x and a scalar ² < 1 such that Pk . . . P1 x ²x; (2) for al l i = 1, . . . , k there exist regular halfspaces Hi such that Vi Hi and i Hi = {0}; (3) i Vi = {0}; (4) < 1. 4. Pro jectors and separation in max algebra In Rn ,m , it is natural to consider semimodules that are closed in the max Euclidean topology. One can easily show that such semimodules are bsemimodules. Theorem 3.11 of [2] implies that pro jectors onto closed subsemimodules of Rn ,m are continuous. max In order to relax the assumption concerning archimedean vectors in Theorem 3.3, we use some results from nonlinear spectral theory, that we next recall. By Brouwer's fixed point theorem, a continuous homogeneous operator x F x that maps Rn to itself has a nonzero eigenvector. This + allows us to define the nonlinear spectral radius of F , (4.1) (F ) = max{ R+ | x (Rn ) \ 0, F x = x} . +


Cyclic pro jectors and separation theorems

71

Suppose in addition that F is isotone, then the maximum in (4.1) is attained and we can use the following nonlinear generalization of the CollatzWielandt formula for the spectral radius of a nonnegative matrix. Theorem 4.1. (R.D. Nussbaum, Theorem 3.1 of [5]) For any isotone, homogeneous, and continuous map F from Rn to itself, we have: + ( F ) =
x(R+ \{0})n 1in

inf

max [F (x)]i x

-1 i

.

This result implies that the spectral radius of such operators is isotone: if F (x) G(x) for any x Rn , then (F ) (G). + As the pro jectors on subsemimodules of Rn ,m are isotone, homogeneous max and continuous, so are their compositions, i.e. cyclic pro jectors. Consequently, we can apply Theorem 4.1 to them. This allows us to refine the general results from the previous section. The following result refines Theorem 3.1 (the spectrum of cyclic pro jections). Theorem 4.2. Let the Hilbert value of V1 , ery eigenvalue of Pk . Conversely, every such V1 , . . . , . . . , Vk . . P1 Hilbert Vk be closed semimodules in Rn ,m . Then max is the spectral radius of Pk . . . P1 . EvM is equal to dH (V1M , . . . , Vk ) for some M . value is an eigenvalue of Pk . . . P1 .

The following result refines Theorem 3.3 (separation). Theorem 4.3. Suppose that Vi , i = 1, . . . , k are closed semimodules of Rn ,m , and that i Vi = {0}. Then there exist archimedean halfspaces max Hi , i = 1, . . . , k such that Vi Hi , for i = 1, . . . , k , and i Hi = {0}. A particular case of Theorem 4.3 is the following separation theorem for two semimodules. Theorem 4.4. Suppose that U and V are two closed max cones, and that U V = 0. Then there exists an archimedean halfspace HU , which contains U and does not intersect with V , and there exists an archimedean halfspace HV , which contains V and does not intersect with U . Bibliography
[1] G. Cohen, S. Gaubert, and J.P. Quadrat, Duality and separation theorems in idempotent semimodules. Linear Algebra Appl., 379:395í422, 2004. E-print arXiv:math.FA/0212294. [2] G. Cohen, S. Gaubert, J.P. Quadrat, and I. Singer, Max-plus convex sets and functions. In G. Litvinov and V. Maslov, editors, Idempotent Mathematics and Mathematical Physics, volume 377 of Contemporary Mathematics , pages 105í129. AMS, Providence, 2005. E-print arXiv:math.FA/0308166.


72

T. Grbi‡ E. Pap c,

[3] S. Gaub ert and S. Sergeev, Cyclic projectors and separation theorems in idempotent semimodules. E-print arXiv:0706.3347. [4] G.L. Litvinov, V.P. Maslov, and G.B. Shpiz, Idempotent functional analysis. An algebraical approach. Math. Notes, 69(5):696í729, 2001. E-print arXiv:math.FA/0009128. [5] R.D. Nussbaum, Convexity and log convexity for the spectral radius. Linear Algebra Appl., 73:59í122, 1986. [6] R.T. Ro ckafellar, Convex analysis. Princeton Univ. Press, 1970. [7] S.N. Samb orski and G.B. Shpiz, Convex sets in the semimodule of bounded funci tions. In V.P. Maslov and S.N. Samb orski editors, Idempotent analysis, volume 13 i, of Advances in Soviet Math., pages 135í137. American Mathematical So ciety, Providence, 1992. [8] K. Zimmermann, A general separation theorem in extremal algebras. Ekonomickomatematicky obzor, 13(2):179í201, 1977. ‡

Pseudo-weak convergence of the random sets defined by a pseudo integral based on non-additive measure1 T. Grbi‡ and E. Pap c
1. Intro duction The weak convergence of sequence of probability measures is the main sub ject for a large class of limit theorems in the probability theory. In the classical probability theory, it works with -additive measures and the Lebesgue integral ([B]). Several conditions equivalent to the weak convergence are provided by the theorem of Portmanteau ([B]). The main aim of this paper is to prove a Portmanteau-type theorem, with capacity functionals instead of probability measures, and with the general pseudo integral instead of the Lebesgue integral. Since the convergence in distribution of sequence of random closed sets on R can be tricky, it is often more appropriate to study the convergence of the corresponding sequence of capacity functionals. In this paper we study the convergence of sequences of random closed sets on R by looking at the convergence of the corresponding sequence of capacity functionals. Theoretical foundations of the theory of random sets, as generalization of random variables, were layed down by Kendall ([G]) and Matheron ([J]).
1Partially supp orted by the Pro ject MNZZSS 144012, grant of MTA HTMT, French-Serbian pro ject "Pavle Savi‡ and by the pro ject "Mathematical Models for c", Decision Making under Uncertain Conditions and Their Applications" supported by Vo jvodina Provincial Secretariat for Science and Technological Development.


Pseudo-weak convergence of random sets

73

Recall that random closed sets are random elements on the space of closed subsets of R. Our paper is organized as follows. Sect. 2 contains some preliminary notions, such as pseudo-operations and general pseudo integral [A, O, S]. In Sect. 3, we recall some basic notions and definitions from the theory of random sets ([C, G, J, K, L]). The main results of this paper, also contained in Sect. 3, are concerned with the weak convergence of sequence of random closed sets, i.e., of the corresponding sequence of capacity functionals with respect to the general pseudo integral. 2. Preliminary notions Following [A, O, P], we recall the notions of pseudo operations and general pseudo integral. Let be the total order on [0, ]. Definition 2.1. A binary operation : [0, ]2 [0, ] is called pseudo-addition if the following properties are satisfied: (A1) a b = b a (commutativity) (A2) a a b b a b a b (monotonicity) (A3) (a b) c = a (b c) (associativity) (A4) a 0 = a (neutral element) (A5) an a bn b (an bn ) a b (continuity) Example 2.1. The following operations are pseudo-additions ([A, O, P]): (i) x y = g -1 (g (x)) + g (y ), where g : [0, ]2 [0, ] is an increasing bijection; (ii) x y = max(x, y ) (note that this operation is idempotent). Definition 2.2. For a given pseudo-addition pseudo-difference is the binary operation : [0, ]2 [0, ] given by a b = inf {x [0, ] : b x a}. Example 2.2. Obviously, a b = 0 for a b and a b > 0 for a > b, see [A, I]. For pseudo-additions from Example 2.1 and a > b corresponding pseudo-differences are (i) a b = g -1 (g (a) - g (b)); (ii) a b = a. Definition 2.3. For a given pseudo-addition the pseudo-multiplication is a binary operation : [0, ]2 [0, ] such that the following conditions are satisfied (M1) a 0 = 0 b = 0 (zero element) (M2) a a b b a b a b (monotonicity) (M3) (a b) c = (a c) (a c) (right distributivity) (M4) a 1 = 1 a = a (unit element)


74

T. Grbi‡ E. Pap c, (M5) a (b c) = (a b) c (associativity) (M6) an a bn b (an bn ) a b (continuity)

Example 2.3. (i) For the pseudo-addition from Example 2.1 (i), define pseudo-multiplication by a b = g -1 (g (a)g (b)). (ii) For the pseudo-addition from Example 2.1 (ii), one of the possible pseudo-multiplications is a b = a + b, see [E, F]. The algebraic structure ([0, ], , ) is a semiring. Let be an abstract space, A a -algebra of subsets of and m : A R a non-decreasing set function with m() = 0. We consider the space (, A, m) and a family of A-measurable functions f : [0, ], denoted by F . A simple function is a measurable function s : [0, ] whose range is finite. Let Rang (s) = {a1 , a2 , . . . , ak } such that 0 < a1 < a2 < . . . < ak , and Ai Aj = for i = j . The standard -step representation
k

of a simple function s is given by s = a2 a1 , . . . , c = am m (c i am ,
-1 , Ci = i=1 m j =i c , i

b(c , Ci ), where c = a1 , c = 1 2 i

Ai and b : [0, ] is a basic
Ci ,

function of the form b

Ci

)( ) =

0,

Ci . /

Definition 2.4. (i) The general pseudo integral of a simple function s with the standard -step representation is given by
m

s

dm =
i=1

c

i

m(Ci ).

(ii) The general pseudo integral of a measurable function f F is given by f dm = sup{ s dm : s Sf }, where Sf is the family of all simple function s such that s f . integral has the following properties: = c m(C ). dm g dm. characteristic function A : [0, ] of a set 1, x A, A , defined by A (x) = we have 0, x A, / A dm = m(A). The general pseudo b(c, C ) dm (i) (ii) f g f (iii) For the pseudo


Pseudo-weak convergence of random sets 3. Weak convergence of the sequence of capacity functionals

75

3.1. Random closed sets and capacity functionals. We start with a short overview of the theory of random closed sets ([C, G, J, K, L, M, N]). Denote collections of closed, open and compact subsets of R by F , O and K, respectively. A very important role in the theory of random closed sets is played by collections of closed sets F , and its sub-collections FG = {F F : F G = }, G O, and F K = {F F : F K = }, K K. Collections {FG : G O} and {F K : K K} generate a topology (F ) on F . This topology is known as hit-or-miss-topology. The collection F endowed with the hit-or-miss topology is a compact, separable and Hausdorff space ([J]). Taking countable unions and intersections of open sets of the topological space (F , (F )), we obtain a -field (F ). Definition 3.1. A random closed set S is a measurable mapping from the probability space (, A, P) into the measurable space (F , (F )). A random closed set S generates a probability distribution PS in the following way PS (A) = P({ : S( ) A}) = PS (S A), for all A (F ). Definition 3.2. For a random closed set S its capacity functional TS : K [0, 1] for K K is defined by TS (K ) = PS (S FK ) = PS (S K = ). The capacity functional TS is defined on K, and it can be extended onto the family P of all subsets of R. A subset M R is called capacitable if the following equality TS (M ) = sup{TS (K ) : K K, K M } is true. All Borel sets B are capacitable ([L]). For a given random closed set S, and a sequence of random closed sets {Sn } corresponding capacity functionals will be denoted by T and {Tn }, respectively. 3.2. (, )-weak convergence. Definition 3.3. A sequence of capacity functionals {Tn } (, )-weak converges to a capacity functional T (shortly, pseudo-weak converges) if and only if for each continuous, bounded function f : R [0, ] we have that lim f dTn = f d T. We have proved in [D]the following three theorems. Theorem 3.1. If a sequence of capacity functionals {Tn } pseudo-weak converges to capacity functional T, then lim sup Tn (F ) T(F ) for al l
n

n

closed sets F R.


76

T. Grbi‡ E. Pap c,

Theorem 3.2. If a sequence of capacity functionals {Tn } pseudo-weak converges to capacity functional T, then lim inf Tn (G) T(G) for al l n open sets G R. Theorem 3.3. If for a sequence of capacity functionals {Tn } and for al l closed sets F holds (A) lim sup Tn (F) T(F) and for al l open sets
n

G holds (B) lim inf Tn (G) T(G), then {Tn } pseudo-weak converges to n capacity functional T. Corollary 3.1. For a closed sets {Sn }, which are Sn = {Xn }, where X is a random variables, the (, convergence (with respect to random closed set S and a sequence of random defined in the fol lowing way: S = {X} and random variable and {Xn } is a sequence of )-weak convergence is equivalent to the weak continuous, bounded function f : R [0, ]).

Proof. For S = {X} and Sn = {Xn }, we have that T(K ) = P(X K ) and Tn (K ) = P(Xn K ) ([C]), where T and Tn are capacity functionals of random sets S and Sn , respectively. Since for each Borel set B we have that T(B ) = sup{T(K ) : K K, K B }, it follows that T(B ) = P(X B ). For all n N we have that Tn (B ) = P(Xn B ). Suppose that {Sn } (, )-weak converges to S. Then by Theorem 3.1, lim sup P(Xn F )
n

P(X F ) for all closed sets F . From the ([B]) we obtain that f dPn f dP, closed sets {Sn } weak converges to S. The weak convergence of the sequence of set G implies that lim inf P(Xn G)
n n

classical theorem of Portmanteau i.e., that the sequence of random probability measures for any open P(X G), and for any closed set

F it implies that lim inf P(Xn F ) P(X F ). Then, by Theorem 3.3, the sequence of random closed sets {Sn } (, )-weak converges to S. Remark 3.1. (i) For the special case described by corollary 3.1, the capacity functional reduces to the probability measure and then Theorem 3.3 can be proved by taking into the account only one of the assumptions, (A) or (B). (ii) Weak convergence of the sequence of capacity functionals with respect to Choquet integral is investigated in [M]. Some equivalent conditions for the weak convergence of the sequence of probability measures, induced by sequence of random closed sets, are obtained in [N, Q]. (iii) The results obtained in this paper will serve for the investigation of further convergence properties of a sequence of capacity functionals of the sequence of random closed sets, based on the idempotent sup-measure and related integrals, see ([D, R].


Pseudo-weak convergence of random sets Bibliography

77

[A] Benvenuti P., Mesiar R., Vivona D., Monotone Set Functions-Based Integrals, in Handbo ok of Measure Theory (Ed. E. Pap), Volume I I, Elsevier, North-Holland, (2002), 205í232. [B] Billingslay, P., Probability Measures, John Wiley & Sons, Inc., New York, 1968. [C] Goutsias J., Modeling Random Shapes: An Introduction to the Random Closed Set Theory, Technical Rep ort JHU/ECE 90-12, 1990. [D] Grbi‡ T., Pap, E., Generalization of Portmanteau theorem with respect to pseudoc, weak convergence (under preparation). [E] Litvinov, G.L., The Maslov Dequantization, Idempotent and Tropical Mathematics: a very Brief Introduction, Cont. Mathematics 377, AMS, (2005), 1-17. [F] Maslov, V.P., Samoborski S.N., (Eds.), Idempotent analysis, Adv, in Sov. Math., i, Vol. 13, AMS, RI, 1992. [G] Kendall D.G., Fondutations of a theory of random sets, In Stohastic Geometry, E.F. Harding and D.G. Kendall, eds., London, (1974), 322í376. [H] Klein, E., Thompson,A., Theory of Correspondences, John Wiley, 1984. [I] Klement, E. P., Mesiar, R., Pap, E., Triangular Norms. Dordrecht: Kluwer Academic Publishers, 2000. [J] Matheron, G., Random Sets and Integral Geometry, John Wiley, 1975. [K] Molchanov, I., Limit Theorems for Unions of Random Closed Sets, vol. 1561 of Lect. Notes Math., Springer, Berlin, 1993. [L] Molchanov, I., Theory of Random Sets, Springer-Verlag, 2005. [M] Nguyen, H.T., Choquet Weak Convergence of Capacity Functionals of Random Sets, in Soft Metho dology and Random Information Systems, Springer, (2004), 19í31. [N] Nguyen, H.T., Bouchon-Meunier B., Random sets and large deviations principle as a foundation for possibility measures, Soft Computing 8, (2004), 61í70. [O] Pap E., Nul l-Additive Set Functions, Kluwer Academic Publishers, 1995. [P] Pap E., Pseudo-Additive Measures and Their Applications, in Handbo ok of Measure Theory (Ed. E. Pap), Volume II, Elsevier, North-Holland, (2002), 1403í1468. [Q] Pap, E., Grbi‡ T., Nedovi‡ Lj., Ralevi‡ N.M., Weak Convergence of Random c, c, c, Sets, 3rd Serbian-Hungarian Joint Symposium on Intelligent Systems, Subotica, (2005), 73í80. [R] Puhalskii, A., Large deviations and idempotent probability, Chapman & Hall/CRC, 2001. [S] Wang Z., Klir G.J.,Fuzzy measure theory, Plenum Press, New York, 1992.

The stationary phase metho d and large deviations Oleg V. Gulinsky
Let {P } be a family of probability measures on a measurable space (X, F ) and let I be a nonnegative function on X with compact level sets. {P } obeys the large deviation principle with a rate function I if and only


78 if


Oleg V. Gulinsky

lim

(g (x)) P (dx)
X

1/

= sup g (x)e
xX

-I

,

for all bounded continuous nonnegative functions g on X [1], [4]. We say that in this sense {P } converges to an idempotent measure exp{-I }. The r.h.s. of the last display is called a sup - integral or idemp otent integral with respect to the idempotent measure and defines rough logarithmic asymptotics of the Laplace method. In this report we discuss logarithmic asymptotics of the integral J () =
X

exp{iu(x)}(g (x)) P (dx),

where X = Rd (in what follows R1 for the simplicity) and u,g (g 0) are smooth enough real-valued functions. We consider this problem as a natural generalization of the stationary phase method which imbeds the classical one in the context of large deviations. The interest in the problem is motivated by the slicing approximation approach to infinite dimension oscillatory integrals as well (see, for example [2]). Our approach is based on the technique of an almost analytic extension and follows the ideas of [3] where the classical method of stationary phase was extended to the case of complex-valued phase function. The new difficulty in our problem is the following. The function which plays the role corresponding to the imaginary part of the phase function in [3], is just the rate function I defined asymptotically by the large deviation principle. Nevertheless, we consider f (x) = u(x) + iI (x) as complex-valued "phase function" and assume that f (x) is C function in a neighborhood of the origin, which in turn is a non-degenerate stationary point of f with I (0) = 0. We introduce an almost analytic extension of f as follows: f (z ) = [u(x)(y ) - I (x)y (t1 y ) - +i[I (x)(y ) + u (x)y (t1 y ) - 1 u (x)y 2 (t2 y ) + ...] 2!

1 I (x)y 2 (t2 y ) + ...] = 2! u(x, y ) + iv (x, y ),

where (y ) C0 is equal to one in a neighborhood of the origin and vanishes for | y | 1. The numbers tk 1 are chosen sufficiently large so that the series converges.


The stationary phase method and large deviations

79

To examine the asymptotic behavior of the integral J (), we replace the integration along R by the integration along a suitable chain in the complex domain passing through the critical point of f (z ). We show that on this chain the problem is reduced to the standard variational principle of large deviations. To fulfil the program following [3], we first find new coordinates z in C ~ for which f (z ) - f (0) is a quadratic form in z . To this end, using Taylor's ~ formula we write f (z ) - f (0) =< z , R(z )z > /2, where by definition R(z ) is an almost analytic function of z . Since all nondegenerate quadratic forms on C are equivalent, there is a linear transformation A such that AT R(0)A = iI. In turn, the equation iQT (z )QT (z ) = R(z ), Q(0) = A
-1

,

has a C solution Q(z ) defined near the origin, since the map Q iQT Q is analytic with surjective differential at Q = A-1 . Moreover, Q is an analytic function of R(z ) and therefore an almost analytic function of z . The map z z = z (z ) = Q(z )z defines new coordinates in the neigh~~ borhood of the origin and in this coordinates we have f (z ) = f (0) + i < z , z > /2, ~~ where z = x + iy and < z , z >= x2 - y 2 + 2i < x, y >. ~~ ~ ~~ ~ ~ ~~ Since I (x) 0 with I (0) = 0, it follows that x2 - y 2 0 on the ~ ~ tangent space at the origin and so there is a C function , defined in a neighborhood of 0, such that in the new coordinates R is given by the equation y = (x). ~ ~ We are now in a position to define a family of chains s in C and examine the behavior of f on them. Let z z = z (z ) be the inverse of ~ ~ the map z z (z ). For 0 s 1, putting ~ s = {z : z = z (zs ), zs = zs (x) = x + i(x)s, x R} ~~ ~~ ~ ~~ one gets the estimate Imf (z (zs )) C | Imz (zs ) |2 . ~ ~


80

Oleg V. Gulinsky

To replace the integration, we first consider the chain 1 and note that in a small enough neighborhood of z = 0 the integrals J () and exp{if (z )}(g (z )) exp{I (x)(y )}P (dx)dy ,
1

where g (z ) is almost analytic extension of g , are equivalent( we may assume that the support of g w.r.t. z belongs to a small fixed neighborhood of the origin). Finally we have to show that 1 differs from 0 with a very small error. We are able to do that with the help of Stokes's formula by the following arguments: (1)f (z ) and g (z ) are almost analytical functions, (2)Imf (z (zs )) C | Imz (zs ) |2 . ~ ~ Thus, it suffices compute the logarithmic asymptotics of the integral exp{if (z )}(g (z )) exp{I (x)(y )}P (dx)dy = exp{iu(0)} ½
0

exp{-[I (0)+ | x |2 /2]}(g (z (x)) exp{I (x(x))}G(x)P (dx), ~ ~ ~ ~ ~
dz where G(x) = det( dx ). One can easily recognize that the asymptotics of ~ ~ the last integral coincides with the asymptotics of

exp{iu(0)} ½

(g (z (x)) G(x)P (dx). ~ ~ ~

Thus we reduced the initial problem to the problem of large deviations. Bibliography
[1] W. Bryc. Large deviations by the asymptotic value method. in: M. Pynsky (ed.). Diffusion pro cesses and related problems in analysis. B ir khauser, 447-472, 1990. è [2] N.Kumano-go. Feynman path integrals as analysis on path space by time slicing approximation. Bull. Sci. math. 128, 197-251, 2004. [3] A.Melin and J.Sjè ostrand. Fourier integral op erators with complex-valued phase functions. Springer Lecture Notes in Math. 459, 120-223, 1974. [4] A. Puhalskii. Large deviations of semimartingales via convergence of the predictable characteristics. Stochastics. 49, 27-85, 1994.


Quantization with a deformed trace

81

Quantization with a deformed trace Dmitry Gurevich
The standard quantization scheme of a Poisson structure on a variety M consists in the following. First, one looks for an associative -product satisfying the so-called correspondence principle. Existence of such a product is shown by Kontsevich. Second, one represents the constructed associative algebra A in a linear (hopefully, Hilbert) space. However, if the initial Poisson structure is not symplectic, such a representation is usually associated to each symplectic leaf of the bracket. In the 80's the author considered some Poisson pencils whose quantization leads to "braided" algebras (cf. [G1, G2] and the references therein). This means that in a sense they are related to a braiding, i.e. a solution to the Quantum Yang-Baxter equation (YBE) R12 R23 R
12

= R23 R12 R23 , where R

12

= R I, R

23

= I R,

V is a vector space over the ground field K (R or C), and R : V 2 V 2 is a linear operator. Such a braiding plays the role of the usual flip in all related constructions and operations. In particular, generalized Lie algebras and their enveloping algebras were defined in this way. However, braidings entering their definitions were assumed to be involutive (R2 = I ). Semiclassical counterpart of such braiding is a classical r-matrix. Given 2 a Lie algebra g. By a classical r-matrix we mean an element r g satisfying the classical analog of the YBE [r12 , r13 ] + [r12 , r23 ] + [r13 , r23 ] = 0, where r12 = r 1, r23 = 1 r. Let : g Vect (M ) be a representation of the Lie algebra g into the vector fields space on a variety M . It is clear that the operator f g K[M ] {f , g }r = 2 (r)(f g ) where stands for the usual (commutative) product in the coordinate ring K[M ] of the variety M defines a Poisson bracket on it. A typical example is M = g , K[g ] = Sym (g). Given a classical 2 r-matrix r (g) then the bracket { , }r is compatible with the linear Poisson-Lie bracket { , }P L , i.e. these brackets generate a Poisson pencil {, }
a,b

= a{ , }

PL

+ b{ , }r .

Moreover, each of them (and consequently, the whole Poisson pencil) can be restricted to any G-orbit O g . (The restriction of the PL bracket to the orbit O is called Kirillov-Kostant-Souriau bracket.)


82

Dmitry Gurevich

A quantization of the Poisson-Lie bracket can be realized in different ways. We consider the enveloping algebra U (g ) to be quantum counterpart of the bracket { , }P L . Hereafter by g we mean the Lie algebra with the bracket [ , ] where [ , ] is the bracket of the Lie algebra g and is a deformation (quantization) parameter. As for the the KKS bracket its quantization can be realized as an appropriate quotient of the algebra U (g ) and represented in a vector space in the spirit of the Kirillov orbit method. In order to quantize the whole pencil { , }a,b or its restriction to an orbit O we apply the following result of Drinfeld. There exists an element ^ F U (g)U (g) such that F = 1 + r + . . . , F (X + Y , Z ) F (X, Y ) = F (X, Y + Z ) F (Y , Z ), and ( 1)F = (1 )F = 1, where is the counit in U (g). By using this element ("quantor" according to Lychagin's terminology) it is possible to quantize the above Poisson pencil and all other operators. Say, by equipping the algebra A = U (g ) with a new product f
,

g=



2

(F )(f g )

where the representation = ad is naturally extended to the algebra U (g ) and stands for the product in this algebra we get a new associative algebra denoted A , . The aforementioned braiding can be introduced via the element F . - Namely, we put R = F 1 P F where P is the usual flip. It is clear that R is involutive. Moreover, it is sub ject to the quantum YBE, i.e. it is a braiding. By means of the quantor F the category of finite dimensional modules of the algebra A can be converted into that of A , -ones. This category is monoidal tensor rigid. Let us consider an ob ject V of this category and the corresponding ob ject End (V ) V V of internal endomorphisms. = There exists a map TrR : End (V ) K which is a deformation of the usual trace and is morphism in this category. Moreover, it is R-symmetric, i.e. TrR (X Y ) = Tr
R

R(X Y )


Quantization with a deformed trace

83

where stands for the usual product in the algebra End (V ). In a sense it looks like a super-trace for which the role of R is played by a super-flip. So, by quantizing the above Poisson pencil and by considering representations of the quantum algebra we are forced to replace the usual trace by its braided version. According to [G1] the linear term of the deformation of of the trace can be treated as a cocycle on the Lie algebra g. So, the deformation procedure itself can be regarded as a quantization of this cocycle. (Note that the involution operator A A must be also deformed.) Recently it was understood what is an analog of the above algebra A , corresponding to a non-involutive braiding (of Hecke type) and what is its semiclassical counterpart. Let R : V 2 V 2 be a Hecke symmetry, i.e. a braiding which meets the Hecke relation (q I - R)(q
-1

I + R) = 0, q K is generic.

j The algebra generated by the unit and elements li , 1 i, j n = dim V sub ject to the equation

RL1 RL1 - L1 RL1 R = (RL1 - L1 R),
j j where L = (li ) is the matrix with entries li and L1 = L 1 is call modified Reflection Equation Algebra (mREA). If the Hecke symmetry R comes from the quantum group Uq (sl(n)) it is a one parameter deformation of the usual flip. In this case the mREA is two parameter deformation of the commutative algebra Sym (g l(n)) (which is a specialization of the A ,q at = 0, q = 1). Its semiclassical counterpart is a Poisson pencil similar to that above but with the bracket { , }r defined in another way. Namely, it is an extension to the ambient vector space of the so-called Semenov-Tian-Shansky bracket defined on the group S L(n). Similarly to the pencil above the latter one can be also restricted to any GL(n)-orbit in g l(n) . The algebra A ,q possesses a braided bi-algebra structure and has the same category of finite dimensional representations as the quantum group Uq (sl(n)) has. However, in contrast with the above monoidal tensor category this one is quasitensor one. Nevertheless, an intrinsic trace TrR which is a categorical morphism and a deformation of the usual trace is well defined on any ob ject End (V ) of internal endomorphisms. (For simple ob jects V it is unique up to a factor.)


84

Alexander E. Guterman

j j For instance, if V is the basic space then TrR li = i . The defining relations of the algebra A ,q can be rewritten as follows j X Y - Q(X Y ) = [X, Y ], X, Y L = span (li )

where Q : L2 L2 is a braiding and [ , ] : L2 L is a "braided Lie bracket". We would like to emphasize that the latter form of the mREA makes it more similar to an enveloping algebra. It is easy to check that TrR (X Y ) = TrR Q(X Y ) where stands for the usual product in the algebra the space L can be naturally identified with End (V )). such a trace is Q-symmetric. A more detailed presentation of the topic can be [GPS]. In my talk I shall exhibit the role of a deformed "braided geometry". Bibliography
Gourevitch D. Equation de Yang-Baxter et quantification des cocycles, C.R.Acad.Sci. Paris, 310 (1990) 845í848. [G2] Gurevich D. Algebraic aspects of the Yang-Baxter equation, English translation: Leningrad Math. 2 (1991) 801 í 828. [GPS] Gurevich D., Pyatov P., Sap onov P. Representation theory of (modified) Reflection Equation Algebra of GL(m|n) type, math/0612815. [G1]

End (V ) (note that So, we can see that found in the paper (quantum) trace in

Transformations preserving matrix invariants over semirings1 Alexander E. Guterman
The investigations of matrix transformations which leave fixed different matrix properties and invariants is an actively developing part of matrix theory. This research was started in the works by Frobenius, see [6, 9, Theorem 1.1], and Dieudonn‡ see [5, 9, Theorem 1.2], where bijective line, ear transformations on matrices over fields which preserve the determinant and the set of singular matrices, correspondingly, were characterized.
Partially supported by the RFBR grant 05-01-01048 and the grant MK2718.2007.1.
1


Transformations preserving matrix invariants over semirings

85

During the last three decades many authors investigated linear transformations on more general algebraic structures, such as matrices over rings and semirings. In this talk we are going to discuss the corresponding problems on max-algebras and related classes of semirings. Definition 4. A semiring is a set S with two binary operations, addition and multiplication, such that: § S is an abelian monoid under addition (identity denoted by 0); § S is a semigroup under multiplication (identity, if any, denoted by 1); § multiplication is distributive over addition on both sides; § s0 = 0s = 0 for all s S . In this paper we will always assume that there is a multiplicative identity 1 in S which is different from 0. Definition 5. A semiring S is called commutative if the multiplication in S is commutative. Definition 6. A semiring S is called antinegative (or zero-sum-free ) if a + b = 0 implies that a = b = 0. This means that the zero element is the only element with an additive inverse Definition 7. We say that a semiring S has no zero divisors if from ab = 0 in S it follows that either a = 0 or b = 0. Definition 8. A semiring is called a max-algebra if the set S is an ordered group with the multiplication and the order relation , and operations in S are defined as follows: a + b = max{a, b}, a § b = a b for any a, b S . It is straightforward to see that max-algebra is antinegative. Also it does not contain zero divisors, moreover any non-zero element of a maxalgebra has a multiplicative inverse. Let Mm,n (S ) denote the set of m ½ n matrices with entries from the semiring S , Mn (S ) = Mn,n (S ). Under natural definitions of matrix addition and multiplication Mn (S ) is obviously a semiring. Matrix theory over semirings has been an ob ject of intensive study during the last decades, see for example the monograph [7] and references therein. The development of linear algebra over semirings certainly requires such an important matrix invariant as the determinant function. However it turns out that even over commutative semirings without zero divisors the classical determinant can


86

Alexander E. Guterman

not be defined as over fields and commutative rings. The main problem lies in the fact that in semirings which are not rings not all elements possess an additive inverse. A natural replacement of the determinant function for matrices over commutative semirings is the bideterminant known for many years, see [7]. Definition 9. A bideterminant of a matrix A = [ai,j ] Mn (S ) is the pair ( A + , A - ), where A
+

=
A
n

a1,

(1)

§ § § an,

(n)

,A

-

=
Sn \A
n

a1,

(1)

§ § § an,

(n)

,

here Sn denotes the symmetric group on the set {1, . . . , n}, An denotes its subgroup of even permutations. It is known that the bideterminant function possesses some natural properties. Namely it is invariant under transposition, and for any scalar S , ( A + , A - ) = (n A + , n A - ). However, some basic properties of the determinant are no longer true for the bideterminant. For example, if A is invertible then A + = A - but the converse is not always true. Example 1. Let us consider where S = (Q+ , max, § ), namely standard multiplication and the Then ( A + , A - ) = (4, 6) but A = E1,1 + 2E1,2 + 3E2,1 + 4E2,2 M2 (S ), the set of non-negative rationals with the addition defined by a + b = max{a, b}. A is not invertible.

Note that the bideterminant is not multiplicative in general. However, some weaker versions of this property are true, in particular, AB
+

+A

+

B

-

+A

-

B

+

= AB

-

+A

+

B

+

+A

-

B

-

.

We prove the following theorem which is a semiring analog of famous Frobenius theorem, see [6], on linear transformations preserving the determinant of complex matrices. Theorem 1. [2] Let S be a commutative antinegative semiring without zero divisors and T : Mn (S ) Mn (S ) be a surjective linear transformation. Then ( T (X ) + , T (X ) - ) = ( X + , X - ) for al l X Mn (S ) if and only if there exists permutation matrices P, Q and invertible diagonal matrices D, E , satisfying ( P Q + , P Q - ) = ( DE + , DE - ) = (1, 0), such that either T (X ) = P DX E Q for al l X Mn (S ) or T (X ) = P DX t E Q for al l X Mn (S ). Here the matrices P, Q are defined uniquely and the matrices D, E are defined uniquely up to an invertible scalar factor.


Transformations preserving matrix invariants over semirings

87

Definition 10. We say that a transformation T : Mn (S ) Mn (S ) is standard if it is defined by T (X ) = P DX E Q for all X Mn (S ) or T (X ) = P DX t E Q for all X Mn (S ) for certain permutational matrices P, Q and diagonal matrices D, E . The following similar function is widely considered in combinatorial matrix theory: Definition 11. A permanent of a matrix A = [ai,j ] Mn (S ) is per (A) =
Sn

a1,

(1)

§§§a

n, (n)

.

Also the following polynomial is related to this function: Definition 12. The rook polynomial of a matrix A Mm,n (S ) is RA (x) = pj xj , where p0 = 1, pj is the sum of the permanents of all
j 0

j ½ j submatrices of A. Linear transformations preserving the rook polynomial and permanent itself were characterized by Beasley and Pullman. Here we provide more general result, namely, we prove that in order to characterize a transformation, it is enough to know that it preserves any single coefficient of a rook polynomial, namely we prove the following: Theorem 2. [8] Let T : Mn (S ) Mn (S ) be a surjective linear transformation and j , 2 j n, be fixed. Then T preserves the j -th coefficient of the rook polynomial iff T is standard with pj (DE ) = 1. The following notions of singularity are in use while dealing with matrices over semirings, as usual, we separate left and right singularity. Definition 13. A matrix A Mm,n (S ) is said to be S -right singular if Ax = 0 for some nonzero x S n . A Mm,n (S ) is S -left singular if xt A = 0t for some nonzero x S m . A matrix A Mm,n (S ) is S -singular if A is either S -left singular or S -right singular. The next example shows that even over antinegative commutative semirings without zero divisors there exist matrices that are S -left singular and are not S -right singular or vice versa. Example 2. Let (R, +, max) be a max-algebra, A= 0 1 0 1 ,B = 1 1 0 0 M2 (R, +, max).

We have that Ax = 0 forces x = 0 since (R, +, max) is antinegative, but [1, 0]A = [0, 0]. Similar xt B = 0 forces x = 0 while B [0, 1]t = [0, 0]t .


88

Alexander E. Guterman

Definition 14. A matrix A Mm,n (S ) is S -nonsingular if A is not S -singular. Note that if S is commutative and A is an S -singular square matrix then ( A + , A - ) = (0, 0). However the following example shows that there are S -nonsingular matrices with the bideterminant equal to (0, 0). Example 3. Over any commutative antinegative semiring, 0 1 0 0 1 0 1 0 1
+ -

=0=

0 1 0

01 10 01

.

We obtain the following analog of Dieudonn‡ theorem on singularity e preservers, see [5], for matrices over semirings. Theorem 3. [2] Let S be an antinegative semiring without zero divisors and T : Mm,n (S ) Mm,n (S ) be a surjective linear operator. Then the fol lowing statements are equivalent (1) T preserves the set of S -singular matrices; (2) T preserves the set of S -nonsingular matrices; (3) There are permutational matrices P, Q Mn (S ) and a matrix B with al l invertible entries such that either T (X ) = P (X B )Q for al l X Mn (S ) or T (X ) = P (X B )t Q for al l X Mn (S ), here X B is an Hadamard product, i.e., (X B )i,j = xi,j bi,j . If the semiring S is also a subsemiring of an associative ring R without zero divisors we can consider the following notion of singularity as well. Definition 15. We say that a matrix A Mm,n (S ) is lar if Ax = 0 for some nonzero x Rn . A Mm,n (S ) is if xt A = 0 for some nonzero x Rm . A is R-singular if A singular or R-right singular, and R-nonsingular if it is not R-right singuR-left singular is either R-left R-singular.

It is straightforward to see that if a semiring S is a subsemiring of a certain ring R then R-right (left) singularity follows from S -right (left) singularity. However the following example shows that there are S -nonsingular matrices which are R-singular.
n

Example 4. For any n the matrix Jn =
i,j =1

Ei,j Mn (Z+ ) is Z-left

and Z-right singular but Z+ -nonsingular. Note that similarly to the situation over fields all non-square matrices are R-singular, however as the above example shows they may not be S -singular.


Transformations preserving matrix invariants over semirings

89

An analog of Theorem 3 holds for transformations preserving R-singularity. Corresponding transformations appear to be standard. Definition 16. Let S be a max-algebra (operations are denoted by max and +). A matrix A = [aij ] Mn (S ) is said to be tropical ly singular if the maximum in the expression for the permanent per (A) = max{a
Sn 1 (1)

+ ... + a

n (n)

}

is achieved at least twice. It can be generalized to the case of an arbitrary antinegative semiring S in the following way: Definition 17. A matrix A = [aij ] Mn (S ) is said to be tropical ly singular if there exists a subset T Sn such that a1
T (1)

§ § § an

(n)

=
Sn \T

a1

(1)

§ § § an

(n)

.

Our further results include the characterization of linear transformations preserving these and related notions of singularity. Also we obtain several analogs of Markus and Moyls result on linear transformations preserving rank, see [9, Theorems 3.1, 3.2], for several well-known semiring rank functions. Bibliography
[1] L. B. Beasley, N. J. Pullman, Term rank, p ermanent and rook p olynomial preservers, Linear Algebra Appl. 90 (1987) 33-46. [2] L. B. Beasley, A. E. Guterman, S.-G. Lee, S.-Z. Song, Frob enius and Dieudonn‡ e theorems over semirings, Linear and Multilinear Algebra, 55, no. 1, (2007) 19-34. [3] P. Butkovi Max-algebra: the linear algebra of combinatorics? Linear Algebra c, Appl. 367 (2003) 315-335. [4] M. Develin, F. Santos, B. Sturmfels, On the rank of a tropical matrix, In Discrete and Computational Geometry (E. Go odman, J. Pach and E. Welzl, eds.), MSRI Publications, Cambridge Univ. Press, 2005. [5] J. Dieudonn‡ Sur une g‡ ‡ e, eneralisation du groupe orthogonal a quatre variables, Arch. ` Math. 1 (1949) 282-287. è [6] G. Frob enius, Uber die Darstel lung der endlichen Gruppen durch lineare Substitutionen, Sitzungsb er., Preuss. Akad. Wiss (Berlin), Berlin (1897) 994-1015. [7] K. Glazek, A Guide to the Literature on Semirings and their Applications in Mathematics and Information Sciences, Kluwer Academic Publishers, 2002. [8] A. E. Guterman, Transformations of non-negative integer matrices preserving the determinant, Uspehi Mat. Nauk 58, no. 6, (2003) 147-148. [9] C.-K. Li, S. Pierce, Linear preserver problems, Amer. Math. Monthly 108, no. 7, (2001) 591-605.


90

I. Itenberg, V. Kharlamov, E. Shustin

Tropical geometry and enumeration of real rational curves1 I. Itenberg, V. Kharlamov, and E. Shustin
The talk is devoted to applications of tropical geometry in enumerative (complex and real) algebraic geometry. We concentrate ourselves at enumeration of real rational curves interpolating fixed collections of real points in a real algebraic surface , and more precisely, at the following question: given a real divisor D and a generic col lection w of c1 () § D - 1 real points in , how many of the complex rational curves belonging to the linear system |D| and passing through the points of w are real ? By rational curves we mean irreducible genus zero curves and their degenerations, so that they form in |D| a pro jective subvariety S (, D); this subvariety is called the Severi variety. A curve on a real surface is called real, if the curve is invariant under the involution c : defining the real structure of . While, under mild conditions on and D, the number of complex curves in question is the same for all generic collections w (it equals to the degree of S (, D)), it is no more the case for real curves (except few very particular situations). J.-Y. Welschinger [5, 6] discovered a way to attribute weights ‘1 to the real solutions in question so that the number of real solutions counted with weights becomes independent of the choice of a generic collection of real points. As an immediate consequence, the absolute value of the Welschinger invariant W,D provides a lower bound on the number R,D (w) of real solutions: R,D (w) |W,D |. In some cases (for example, in the case of toric Del Pezzo surfaces; recall that there are five toric Del Pezzo surfaces: the pro jective plane P2 , the product P1 ½ P1 of pro jective lines, and P2 blown up at k points in general position, where k = 1, 2 or 3) Welschinger invariants can be calculated using Mikhalkin's approach [3, 4] which deals with a corresponding count of tropical curves. In tropical geometry, complicated non-linear algebrogeometric ob jects are replaced by simpler piecewise-linear ones. For example, tropical plane curves are piecewise-linear graphs whose edges have rational slopes. Tropical curves can be seen as algebraic curves over the tropical semi-field (max, +). Using the tropical approach, we proved (see [1]) the logarithmic equivalence for the Welschinger and Gromov-Witten invariants of any toric Del
1

Partially supported by the joint RFBR/CNRS grant 05-01-02807.


Tropical geometry and enumeration of curves

91

Pezzo surface equipped with its tautological real structure, i.e., the real structure which is provided by the toric structure. Theorem 1. (see [1]) Let be a toric Del Pezzo surface equipped with its tautological real structure, and D an ample divisor on . The sequences log W,nD and log GW,nD , n N, of the Welschinger invariants and the corresponding Gromov-Witten invariants are asymptotical ly equivalent. More precisely, log W,nD = log GW,nD + O(n) and log GW,nD = (c1 () § D) § n log n + O(n). We also defined (see [2]) a series of relative tropical Welschinger-type invariants of real toric surfaces. In the Del Pezzo case, these invariants can be seen as real tropical analogs of relative Gromov-Witten invariants, and are sub ject to recursive formulas of Caporaso-Harris type. In the present talk, we consider generic collections of real points on the pro jective plane blown up at 4 real points in general position and prove that the logarithmic equivalence of the Welschinger and Gromov-Witten invariants holds in this situation as well. Theorem 2. Let be the projective plane P2 blown up at 4 real points in general position, and D an ample divisor on . The sequences log W,nD and log GW,nD , n N, of the Welschinger invariants and the corresponding Gromov-Witten invariants are asymptotical ly equivalent. The proof is based on a new version of the correspondence whose proof in turn uses an appropriate tropical Caporaso-Harris mulas. In particular, we get recursive formulas that allow one to Welschinger invariants of P2 blown up at 4 real points in general Bibliography
[1] I. Itenberg, V. Kharlamov, and E. Shustin, Logarithmic equivalence of Welschinger and Gromov-Witten invariants, Russian Math. Surveys 59 (2004), no. 6, 1093í 1116. [2] I. Itenb erg, V. Kharlamov, and E. Shustin, A Caporaso-Harris type formula for Welschinger invariants of real toric Del Pezzo surfaces. Preprint math.AG/0608549, 2006, 1 - 39 (to appear in Commentarii Math. Helvetici). [3] G. Mikhalkin, Counting curves via the lattice paths in polygons, Comptes Rend. Acad. Sci. Paris, S‡ I, 336 (2003), no. 8, 629í634. er. [4] G. Mikhalkin, Enumerative tropical algebraic geometry in R2 , J. Amer. Math. Soc. 18 (2005), 313í377. [5] J.-Y. Welschinger, Invariants of real rational symplectic 4-manifolds and lower bounds in real enumerative geometry, C. R. Acad. Sci. Paris, S‡ I, 336 (2003), er. 341í344. [6] J.-Y. Welschinger, Invariants of real symplectic 4-manifolds and lower bounds in real enumerative geometry, Invent. Math. 162 (2005), no. 1, 195í234.

theorem, type forcalculate position.


92

Semen S. Kutateladze

Abstract convexity and cone-vexing abstractions Semen S. Kutateladze
This talk is devoted to some origins of abstract convexity and a few vexing limitations on the range of abstraction in convexity. Convexity is a relatively recent sub ject. Although the noble ob jects of Euclidean geometry are mostly convex, the abstract notion of a convex set appears only after the Cantor paradise was founded. The idea of convexity feeds generation, separation, calculus, and approximation. Generation appears as duality; separation, as optimality; calculus, as representation; and approximation, as stability. 1. Generation Let E be a complete lattice E with the adjoint top := + and bottom := -. Unless otherwise stated, Y is usually a Kantorovich space which is a Dedekind complete vector lattice in another terminology. Assume further that H is some subset of E which is by implication a (convex) cone in E , and so the bottom of E lies beyond H . A subset U of H is convex relative to H or H -convex , in symbols U V(H, E ), provided that H U is the H -support set Up := {h H : h p} of some element p of E . Alongside the H -convex sets we consider the so-called H -convex eleH ments. An element p E is H -convex provided that p = sup Up ; i.e., p represents the supremum of the H -support set of p. The H -convex elements comprise the cone which is denoted by C (H, E ). We may omit the references to H when H is clear from the context. It is worth noting that convex elements and sets are "glued together" by the Minkowski diality H : p Up . This duality enables us to study convex elements and sets simultaneously. Since the classical results by Fenchel [1] and Hè mander [2, 3] it has or been well known that the most convenient and conventional classes of convex functions and sets are C (A(X ), RX ) and V(X , RX ). Here X is a locally convex space, X is the dual of X , and A(X ) is the space of affine functions on X (isomorphic with X ½ R). In the first case the Minkowski duality is the mapping f epi(f ) where f (y ) := sup ( y , x - f (x))
x X

is the YoungíFenchel transform of f or the conjugate function of f . In the second case we prefer to write down the inverse of the Minkowski duality


Abstract convexity and cone-vexing abstractions which sends U in V(X , R ) to the standard support function
-1 X

93

(U ) : x sup y , x .
y U

As usual, §, § stands for the canonical pairing of X and X . This idea of abstract convexity lies behind many current ob jects of analysis and geometry. Among them we list the "economical" sets with boundary points meeting the Pareto criterion: capacities, monotone seminorms, various classes of functions convex in some generalized sense, for instance, the Bauer convexity in Choquet theory, etc. It is curious that there are ordered vector spaces consisting of the convex elements with respect to narrow cones with finite generators. Abstract convexity is traced and reflected, for instance, in [4]í[9]. 2. Separation Consider cones K1 and K2 in a topological vector space X and put := (K1 , K2 ). Given a pair define the correspondence from X 2 into X by the formula := {(k1 , k2 , x) X 3 : x = k1 - k2 Ki (i := 1, 2)}. Clearly, is a cone or, in other words, a conic correspondence. The pair is nonoblate whenever is open at the zero. Since (V ) = V K1 - V K2 for every V X , the nonoblateness of means that V := (V K1 - V K2 ) (V K2 - V K1 ) is a zero neighborhood for every zero neighborhood V X . Since V V - V , the nonoblateness of is equivalent to the fact that the system of sets { V } serves as a filterbase of zero neighborhoods while V ranges over some base of the same filter. Let n : x (x, . . . , x) be the embedding of X into the diagonal n (X ) of X n . A pair of cones := (K1 , K2 ) is nonoblate if and only if := (K1 ½ K2 , 2 (X )) is nonoblate in X 2 . Cones K1 and K2 constitute a nonoblate pair if and only if the conic correspondence X ½ X 2 defined as := {(h, x1 , x2 ) X ½ X 2 : xi + h Ki (i := 1, 2)} is open at the zero. Recall that a convex correspondence from X into Y is open at the zero if and only if the Hè ormander transform of X ½ and the cone 2 (X ) ½ {0} ½ R+ constitute a nonoblate pair in X 2 ½ Y ½ R.


94

Semen S. Kutateladze

Cones K1 and K2 in a topological vector space X are in general position provided that (1) the algebraic span of K1 and K2 is some subspace X0 X ; i.e., X0 = K1 - K2 = K2 - K1 ; (2) the subspace X0 is complemented; i.e., there exists a continuous pro jection P : X X such that P (X ) = X0 ; (3) K1 and K2 constitute a nonoblate pair in X0 . Let n stand for the rearrangement of coordinates n : ((x1 , y1 ), . . . , (xn , yn )) ((x1 , . . . , xn ), (y1 , . . . , yn )) which establishes an isomorphism between (X ½ Y )n and X n ½ Y n . Sublinear operators P1 , . . . , Pn : X E {+} are in general position if so are the cones n (X ) ½ E n and n (epi(P1 ) ½ § § § ½ epi(Pn )). A similar terminology applies to convex operators. Given a cone K X , put E (K ) := {T L (X, E ) : T k 0 (k K )}. We readily see that E (K ) is a cone in L (X, E ). Theorem. Let K1 , . . . , Kn be cones in a topological vector space X and let E be a topological Kantorovich space. If K1 , . . . , Kn are in general position then E (K1 § § § Kn ) = E (K1 ) + § § § + E (Kn ). This formula opens a way to various separation results. Sandwich Theorem. Let P, Q : X E {+} be sublinear operators in general position. If P (x) + Q(x) 0 for all x X then there exists a continuous linear operator T : X E such that -Q(x) T x P (x) (x X ).

Many efforts were made to abstract these results to a more general algebraic setting and, primarily, to semigroups. The relevant separation results are collected in [10]. 3. Calculus Consider a Kantorovich space E and an arbitrary nonempty set A. Denote by l (A, E ) the set of all order bounded mappings from A into E ; i.e., f l (A, E ) if and only if f : A E and the set {f () : A} is order bounded in E . It is easy to verify that l (A, E ) becomes a Kantorovich space if endowed with the coordinatewise algebraic operations and order.


Abstract convexity and cone-vexing abstractions The operator
A,E

95

acting from l (A, E ) into E by the rule : f sup{f () : A} (f l (A, E ))

A,E

is called the canonical sublinear operator given A and E . We often write A instead of A,E when it is clear from the context what Kantorovich space is meant. The notation n is used when the cardinality of A equals n and we call the operator n finitely-generated. Let X and E be ordered vector spaces. An operator p : X E is called increasing or isotonic if for all x1 , x2 X from x1 x2 it follows that p(x1 ) p(x2 ). An increasing linear operator is also called positive. As usual, the collection of all positive linear operators in the space L(X, E ) of all linear operators is denoted by L+ (X, E ). Obviously, the positivity of a linear operator T amounts to the inclusion T (X + ) E + , where X + := {x X : x 0} and E + := {e E : e 0} are the positive cones in X and E respectively. Observe that every canonical operator is increasing and sublinear, while every finitely-generated canonical operator is order continuous. Recall that p := p(0) = {T L(X, E ) : (x X ) T x p(x)} is the subdifferential at the zero or support set of a sublinear operator p. Consider a set A of linear operators acting from a vector space X into a Kantorovich space E . The set A is weakly order bounded if the set {x : A} is order bounded for every x X . We denote by A x the mapping that assigns the element x E to each A, i.e. A x : x. If A is weakly order bounded then A x l (A, E ) for every fixed x X . Consequently, we obtain the linear operator A : X l (A, E ) that acts as A : x A x. Associate with A one more operator pA : x sup{x : A} (x X ).

The operator pA is sublinear. The support set pA is denoted by cop(A) and referred to as the support hul l of A. These definitions entail the following Theorem. If p is a sublinear operator with p = cop(A) then P = A A . Assume further that p1 : X E is a sublinear operator and p2 : E F is an increasing sublinear operator. Then (p2 p1 ) = T p1 : T L+ (l ( p1 , E ), F ) T Furthermore, if p1 = cop(A1 ) and p2 = cop(A2 ) then (p2 p1 ) = T A1 : T L+ (l (A1 , E ), F ) A
2

p

1

p2 .

T

A

1

= A2

.


96

Semen S. Kutateladze

More details on subdifferential calculus and applications to optimality are collected in [11]. 4. Approximation Study of stability in abstract convexity is accomplished sometimes by introducing various epsilons in appropriate places. One of the earliest attempts in this direction is connected with the classical HyersíUlam stability theorem for -convex functions. The most recent results are collected in [12]. Exact calculations with epsilons and sharp estimates are sometimes bulky and slightly mysterious. Some alternatives are suggested by actual infinities, which is illustrated with the conception of infinitesimal optimality. Assume given a convex operator f : X E + and a point x in the effective domain dom(f ) := {x X : f (x) < +} of f . Given 0 in the positive cone E+ of E , by the -subdifferential of f at x we mean the set f (x) := T L(X, E ) : (x X )(T x - F x T x - f x + ) , with L(X, E ) standing as usual for the space of linear operators from X to E . Distinguish some downward-filtered subset E of E that is composed of positive elements. Assuming E and E standard, define the monad ²(E ) of E as ²(E ) := {[0, ] : E }. The members of ²(E ) are positive infinitesimals with respect to E . As usual, E denotes the external set of all standard members of E , the standard part of E . We will agree that the monad ²(E ) is an external cone over R and, moreover, ²(E ) E = 0. In application, E is usually the filter of orderunits of E . The relation of infinite proximity or infinite closeness between the members of E is introduced as follows: e1 e2 e1 - e2 ²(E ) e2 - e1 ²(E ). Since f (x) =
E ²(E )

f (x);

therefore, the external set on both sides is the so-called infinitesimal subdifferential of f at x. We denote this set by Df (x). The elements of Df (x) are infinitesimal subgradients of f at x. If the zero oiperator is an infinitesimal subgradient of f at x then x is called an infinitesimal minimum point of f . We abstain from indicating E explicitly since this leads to no confusion.


Interval analysis for algorithms of idempotent mathematics

97

Theorem. Let f1 : X ½ Y E + and f2 : Y ½ Z E + be convex operators. Suppose that the convolution f2 f1 is infinitesimally exact at some point (x, y , z ); i.e., (f2 f1 )(x, y ) f1 (x, y ) + f2 (y , z ). If, moreover, the convex sets epi(f1 , Z ) and epi(X, f2 ) are in general position then D(f2 f1 )(x, y ) = Df2 (y , z ) Df1 (x, y ). Bibliography
[1] Fenchel W. (1953) Convex Cones, Sets, and Functions. Princeton: Princeton Univ. Press. [2] Hè ormander L. (1955) Sur la fonction d'appui des ensembles convexes dans une espace lokalement convexe. Ark. Mat., 3:2, 180í186 [in French]. [3] Hè ormander L. (1994) Notions of Convexity. Boston: Birkhè auser. [4] Kutateladze S. S. and Rubinov A. M. (1972) Minkowski duality and its applications. Russian Math. Surveys, 27:3, 137í191. [5] Kutateladze S. S. and Rubinov A. M. (1976) Minkowski Duality and Its Applications. Novosibirsk: Nauka Publishers [in Russian]. [6] Singer I. (1997) Abstract Convex Analysis. New York: John Wiley & Sons. [7] Pallaschke D. and Rolewicz S. (1998) Foundations of Mathematical Optimization, Convex Analysis Without Linearity. Dordrecht: Kluwer Academic Publishers. [8] Rubinov A. M. (2000) Abstract Convexity and Global Optimization. Dordrecht: Kluwer Academic Publishers. [9] Ioffe A. D. and Rubinov A. M. (2002) Abstract convexity and nonsmooth analysis. Global aspects. Adv. Math. Econom., 4, 1í23. [10] Fuchssteiner B. and Lusky W. (1981) Convex Cones. Amsterdam: North-Holland. [11] Kusraev A. G. and Kutateladze S. S. (2007) Subdifferential Calculus: Theory and Applications. Moscow: Nauka Publishers [in Russian]. [12] Dilworth S. J., Howard R., and Rob erts J. W. (2006) A general theory of almost convex functions. Trans. Amer. Math. So c., 358:8, 3413í3445.

Interval analysis for algorithms of idemp otent and tropical mathematics1 Grigory L. Litvinov
The idempotent interval analysis appears to be best suited for treating problems with order-preserving transformations of input data [1, 2]. It gives exact interval solutions to optimization problems with interval uncertainties in input data without any conditions of smallness on uncertainty intervals. Our aim to generalize results presented in [1, 2] for a very
1The work has b een supp orted by the joint RFBR/CNRS grant 05-01-02807 and by the RFBR grant 05-01-00824.


98

Grigory L. Litvinov

general case of arbitrary algoritms of idempotent mathematics (in particular, tropical mathematics) and algorithms over positive semirings (the semifield of all nonnegative real numbers with usual operations is a typical positive semiring). Algorithms of this type are generated by a collection of basic semiring/semifield operations, the well known star-operations x x = 1 x x2 x3 . . . , and trivial operations. Theorem. Every algorithm of idempotent mathematics (and every algorithm over positive semirings) has an interval version. The complexity of this interval version coincides with the complexity of the initial algorithm. The interval version of the algorithm gives exact interval estimates for the corresponding output data. See [1, 2] for some examples. Note that for the traditional interval analysis the situation is opposite. For example, basic algorithms of the traditional linear algebra are plynomial but the corresponding interval versions are NP-hard and interval estimates are not exact. Bibliography
[1] G.L. Litvinov and A.N. Sobolevski Exact interval solutions of the discrete Bel li, man equation and polynomial complexity of problems in interval idempotent linear algebra, Doklady Mathematics, v. 62, no. 2, 2000, p.199í201. E-print arXiv: math.LA/0101041. [2] G.L. Litvinov and A.N. Sobolevski Idempotent interval analysis and optimizai, tion problems, Reliable Computing, v. 7, no. 5, 2001, p.353í377. E-print arXiv: math.SC/0101080.


Dequantization procedures related to the Maslov dequantization

99

Dequantization pro cedures related to the Maslov dequantization1 G.L. Litvinov and G.B. Shpiz
1. The Maslov dequantization Let R and C be the fields of real and complex numbers. The well-known max-plus algebra Rmax = R {-} is defined by the operations x y = max{x, y } and x y = x + y . The max-plus algebra can be treated as a result of the Maslov dequantization of the semifield R+ of all nonnegative numbers, see, e.g., [1,2]. The change of variables (1.1) x u = h log x, where h > 0, defines a map h : R+ R {-}. Let the addition and multiplication operations be mapped from R+ to R {-} by h , i.e. let u h v = h log(exp(u/h) + exp(v /h)), 0 = - = h (0), u v = u + v, 1 = 0 = h (1).

It can easily be checked that u h v max{u, v } as h 0. Thus we get the semifield Rmax (i.e. the max-plus algebra) with zero 0 = - and unit 1 = 0 as a result of this deformation of the algebraic structure in R+ . The semifield Rmax is a typical example of an idempotent semiring; this is a semiring with idempotent addition, i.e., x x = x for arbitrary element x of this semiring, see, e.g., [3-5]. The analogy with quantization is obvious; the parameter h plays the role of the Planck constant [2]. The map x |x| and the Maslov dequantization for R+ give us a natural passage from the field C (or R) to the maxplus algebra Rmax . Following [4], we wil l also cal l this passage the Maslov dequantization. In fact the Maslov dequantization is the usual Schrè odinger dequantization but for imaginary values of the Planck constant (see, e.g., [4]). The passage from numerical fields to the max-plus algebra Rmax (or similar semifields) in mathematical constructions and results generates the so called tropical mathematics. The so-called idempotent dequantization is a generalization of the Maslov dequantization; idempotent dequantization generates the so-called idempotent mathematics, see, e.g. [4] for details.
1This work has b een supp orted by the RFBR grant 05-01-00824 and the joint

RFBR/CNRS grant 05-01-02807.


100 2. The dequantization transform

G.L. Litvinov, G.B. Shpiz

This transform is defined in [6]. Let X be a topological space. For functions f (x) defined on X we shall say that a certain property is valid almost everywhere (a.e.) if it is valid for all elements x of an open dense subset of X . Suppose X is Cn or Rn ; denote by Rn the set x = { (x1 , . . . , xn ) X | xi 0 for + i = 1, 2, . . . , n. For x = (x1 , . . . , xn ) X we set exp(x) = (exp(x1 ), . . . , exp(xn )); so if x Rn , then exp(x) Rn . + Denote by F (Cn ) the set of all functions defined and continuous on an open dense subset U Cn such that U Rn . It is clear that F (Cn ) + is a ring (and an algebra over C) with respect to the usual addition and multiplications of functions. ^ For f F (Cn ) let us define the function fh by the following formula: (2.1) ^ fh (x) = h log |f (exp(x/h))|, ^ ^ f (x) = lim fh (x),
h+0

where h is a (small) real positive parameter and x Rn . Set (2.2)

if the right-hand part of (2.2) exists almost everywhere. We shall say that ^ the function f (x) is a dequantization of the function f (x) and the map ^(x) is a dequantization transform. By construction, fh (x) and ^ f (x) f ^ f (x) can be treated as functions taking their values in Rmax . Note that ^ ^ in fact fh (x) and f (x) depend on the restriction of f to Rn only; so in + fact the dequantization transform is constructed for functions defined on Rn only. It is clear that the dequantization transform is generated by the + Maslov dequantization and the map x |x|. Of course, similar definitions can be given for functions defined on Rn and Rn . + ^ ^ Denote by f the subdifferential of the function f at the origin. It is well known that all the convex compact subsets in Rn form an idempotent semiring S with respect to the Minkowski operations: for A, B S the sum A B is the convex hull of the union A B ; the product A B is defined in the following way: A B = { x | x = a + b, where a A, b B . In fact S is an idempotent linear space over Rmax (see, e.g., [4]). Of course, the Newton polytopes in V form a subsemiring ^ N in S . If f , g are polynomials, then (f g ) = f g ; moreover, if f and ^ g are "in general position", then (f + g ) = f g . For the semiring of all polynomials with nonnegative coefficients the dequantization transform is a homomorphism of this "traditional" semiring to the idempotent semiring N .


Dequantization procedures related to the Maslov dequantization

101

^ ^ Theorem 2.1. If f is a polynomial, then the subdifferential f of f at the origin coincides with the Newton polytope of f . For the semiring ^ of polynomials with nonnegative coefficients, the transform f f is a homomorphism of this semiring to the semiring of convex polytopes with respect to the wel l-known Minkowski operations. Using the dequantization transform it is possible to generalize this result to a wide class of functions and convex sets, see [6]. Another approach based on complex analysis is due to A. Rashkovskii, see, e.g., [7,8]. 3. Dequantization of linear op erators and semigroups of linear op erators The dequantization transform can be rewritten in the following form: ^ f f (x) = lim h log(| f (exp(x/h) |) = lim (1/s) § log(| f (exp(sx) |),
h+0 s+

where x Rn , and h, s = 1/h are real positive parameters. Our aim is to apply the dequantization transform to matrix elements of operator semigroups generated by linear operators. Suppose that S is a semigroup and s s is a linear representation of S in a complete (or quasicomplete) barreled locally convex space (by continuous operators). Denote by V the dual space to V and by v , v the value of a functional v V on an element v V . If s v ,v (s) = v , s v is a matrix element of , then its dequantization v ,v is defined by the formula:
v ,v

= lims (1/s) § log(| v , s v |).
+

v ,v

We discuss the cases S = R S {}.

or S = Z+ . If v and v are fixed, then

Proposition 3.1. Let A be a linear operator in V , s = exp(sA), and dim V < . Then the set of al l dequantizations {v ,v } coincides with the set of real parts of al l eigenvalues of A. There are generalizations of this result for the case dim V = . Suppose that for every v the set {r-s § (| v , s v |), s number r does not depend on exponential. Note, that if V is then is exponential. In the V there exists a number r > 0 such that S } is bounded for every v V and the v V . Then the representation is called a Banach space and is weakly continuous, general case the spectral radius of is


102 defined by the formula: = inf {r | r
-s

G.L. Litvinov, G.B. Shpiz

s v 0 weakly for every v V as s +}

Proposition 3.2. If A is a bounded linear operator in a Banach space V , S = Z+ , = As , then = (A) = lims As 1/s , i.e. is the traditional spectral radius of A. Theorem 3.1. If is exponential, then log = sup{
v ,v

| v V , v V }.

Theorem 3.2. Suppose that A is a compact operator and s = As , where s S = Z+ . Then the set {v ,v } of al l dequantizations of coincides with the set of al l numbers of the form log(| |), where runs the spectrum of A. 4. Dequantization of set functions on metric spaces Let M be a metric space, S its arbitrary subset with a compact closure. It is well-known that a Euclidean d-dimensional ball B of radius has volume (1/2)d d vold (B ) = , (1 + d/2) where d is a natural parameter. By means of this formula it is possible to define a volume of B for any real d [9]. Cover S by a finite number of balls of radii m . Set vd (S ) := lim inf
0 m <

vold (Bm ).
m

Then there exists a number D such that vd (S ) = 0 for d > D and vd (S ) = for d < D. This number D is called the Hausdorff-Besicovich dimension (or HB-dimension) of S [9]. Note that a set of non-integral HB-dimension is called a fractal in the sense of B. Mandelbrot. Denote by N (S ) the minimal number of balls of radius covering S . Then D(S ) = lim+0 log (N (S )-1 ), where D(S ) is the HB-dimension of S . Set = e D(S ) = lims
+ -s

, then (S ).

(1/s) § log Nexp

(-s)

So the HB-dimension D(S ) can be treated as a result of a dequantization of the set function N (S ).


Dequantization procedures related to the Maslov dequantization

103

Let ² be a set function on M (e.g., a probability measure) and suppose that ²(B ) < for every ball B . Let Bx, be a ball of radius having the point x M as its center. Then define ²x () := ²(Bx, ) and let Dx,² := lims
+

- (1/s) § log(|²x (e

-s

)|).

This number could be treated as a dimension of M at the point x with respect to the set function ². There are many dequantization procedures of this type in different mathematical areas. In particular, V.P. Maslov's negative dimension [10] can be treated similarly. 5. Dequantization of the Fourier-Laplace transform It was noticed by V.P. Maslov (see, e.g., [1-4]) that the Legendre (or Legendre-Fenchel) transform can be treated as an idempotent (or tropical) version of the Fourier-Laplace transform. It seems to be interesting to note that the Legendre transform can be constructed from the FourierLegendre transform directly by means of the Maslov dequantization. 6. Dequantization of geometry An idempotent version of real algebraic geometry was discovered in the report of O. Viro for the Barcelona Congress [11]. Starting from the idempotent correspondence principle [2], O. Viro constructed a piecewise-linear geometry of polyhedra of a special kind in finite dimensional Euclidean spaces as a result of the Maslov dequantization of real algebraic geometry. He indicated important applications in real algebraic geometry (e.g., in the framework of Hilbert's 16th problems) and relations to complex algebraic geometry and amoebas in the sense of I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky. Then complex algebraic geometry was dequantized by G. Mikhalkin and the result turned out to be the same; now the new geometry is called tropical algebraic geometry. In particular, tropical varieties are results of a dequantization procedure (generated by the Maslov dequantization) applied to algebraic varieties. There are many applications, see, e.g., [11-13,5]. 7. Remark It would be nice to find new dequantization procedures related to the Maslov dequantization.


104 Bibliography

G.L. Litvinov, G.B. Shpiz

[1] V. P. Maslov,On a new superposition principle for optimization problems, Usp ekhi Mat. Nauk, [Russian Math. Surveys], 42, no. 3 (1987), 39í48. [2] G. L. Litvinov and V. P. Maslov, Correspondence principle for idempotent calculus and some computer applications, (IHES/M/95/33), Institut des Hautes Etudes Scientifiques, Bures-sur-Yvette, 1995. Also: [3], p. 420 í 443, and arXiv:math.GM/0101021. [3] J. Gunawardena (Ed.), Idempotency, Publ. of the Newton Institute, Vol. 11, Cambridge University Press, Cambridge, 1998. [4] G.L. Litvinov, The Maslov dequantization, idempotent and tropical mathematics: a brief introduction, Journal of Mathematical Sciences, 140 no. 3 (2007) 426í444. E-print: arXiv:math.GM/0507014, 2005 (http://arXiv.org). [5] G. L. Litvinov and V. P. Maslov (Eds.), Idempotent Mathematics and Mathematical Physics, Contemp orary Mathematics, Vol. 377, AMS, Providence, RI, 2005. [6] G. L. Litvinov and G. B. Shpiz, The dequantization transform and generalized Newton polytopes. -- In [5], p. 181í186. [7] A. Rashkovskii, Newton numbers and residual measures of plurisubharmonic functions, Ann. Polon. Math. 75 no. 3 (2000) 213í231. [8] A. Rashkovskii, Tropical analysis on plurisubharmonic singularities. í In this volume (part 2). [9] Yu.I. Manin, The notion of dimension in geometry and algebra. E-print arXiv:math.AG/0502016, 2005. [10] V.P. Maslov, A general notion of topological spaces of negative dimension and quantization of their densities. Math. Notes (Mat. Zametki), 81 no. 1 (2007) 157í 160 (in Russian). [11] O. Viro, Dequantization of real algebraic geometry on a logarithmic paper. -- In: 3rd Europ ean Congress of Mathematics, Barcelona, 2000, vol. I , Birkhèuser, Basel, a 2001, p. 135í146. Also arXiv:math.AG/0005163. [12] G. Mikhalkin, Tropical geometry and its applications. Proceedings of the Madrid ICM, 2006. Also arXiv:math.AG/06011041. [13] I. Itenberg, V. Kharlamov, and E. Shustin, Tropical geometry and enumeration of real rational curves. í In this volume.