L Rónyai

A M Cohen

W A Degraaf

Computations in finite-dimensional Lie algebras

Keywords:

  L'archive ouverte pluridisciplinaire

Presentations of Lie Algebras

The three most common ways to present a Lie algebra over a field F are FL by means of generators and relations, GL as a Lie subalgebra of the general linear Lie algebra gl n F ,o r SC by means of an explicit multiplication table.

These three ways will be called the basic presentations. Together they suffice for most applications.

Basic Presentations

To obtain the basic presentations, we start with the following atomic presentations: FL The free Lie algebra L(A) on the alphabet A. Its elements can be presented by sums of terms, where a term is the product of a scalar (from F) with a (square bracketed) monomial in the variables from A. The Lie bracket is (formally) F-bilinear, whence determined by its value on a pair of monomials; the Lie bracket of two monomials s and t is just the bracketed monomial [s; t]. This presentation is not unique as one has to divide out by the anti-symmetry and the Jacobi identities. Normal forms algorithms exist for L(A) -seebelow .

GL The linear Lie algebra gl n (F ) of all n n matrices over F. Here the Lie bracket of the matrices x and y is [x; y]=xy yx,where stands for the usual matrix multiplication.

SC The abstract Lie algebra L with basis f x i j i 2 I g, where the Lie bracket [ ; ] is determined by an explicitly given multiplication table, consisting of the so-called structure constants c k ij (i; j; k 2 I)

which are defined by the relations

[x i ;x j ]= X k 2I c k ij x k :
In view of the bilinearity of the Lie bracket, these are sufficient to calculate the bracket of two arbitrary elements of L.

Starting from an atomic presentation, we can obtain a presentation for a subalgebra or a quotient algebra.

The simplest and most frequently employed constructions of a Lie algebra L make use of one of the following three basic presentations:

FL L = L(A)=I for an ideal I of L(A);
GL L = hXi for a subset X of gl n (F ); SC L givenbyabasisf x i j i 2 I g and structure constants c k ij (i; j; k 2 I). If L is known to be semi-simple or nilpotent, other efficient presentations are known, depending on the structure of L, e.g. the Chevalley generators and Serre relations for semi-simple Lie algebras (cf.

Humphreys [START_REF] Humphreys | Introduction to Lie Algebras and Representation Theory[END_REF]). Here we shall not go into those ramifications.

Example

We give a basic presentation of each kind for the 3-dimensional Heisenberg algebra.ThisisaLiealgebra with basis fx; y; zg whose structure constants are given by the following table :  H x y z x 0 z 0 y z 0 0 z 0 0 0

In matrix form, H can be taken to be generated by the following three matrices corresponding to x, y, z, respectively:

0 ( 0 1 0 0 0 0 0 0 0 1 A 0 ( 0 0 0 0 0 1 0 0 0 1 A 0 ( 0 0 1 0 0 0 0 0 0 1 A
Clearly, H is a quotient of the free Lie algebra on the alphabet fX;Y;g. The relations (corresponding to generators of the ideal that has to be divided out to get H) can be described by first expressing all other basis elements as products of x and y, and subsequently substituting these expressions in the multiplications given by the multiplication table. Thus, one easily finds that H is a quotient of the free Lie algebra on the alphabet fX;Y g with relations

0=[ X;[X;Y ]]; 0=[ Y;[X;Y ]]

Changing Presentations

From a theoretical point of view, it is known that every finite-dimensional Lie algebra can be presented in any of the three basic presentations. However, for performing computations on finite-dimensional Lie algebras, the presentation by means of a commutator table giving the structure constants (SC) seems to be the most suitable. In the implementation of the algorithms we will therefore assume that every finitedimensional Lie algebra is presented in this way. For this, and other reasons, we must be able to compute the transition from the first two presentations to a commutator table (SC) presentation, and vice versa.

The transitions GL ! SC ! FL are straightforward. The first transition can be achieved by using linear algebra for gl n (F ).F i n dab a s i s x 1 ;:::;x n for L, and determine the structure constants c k ij by computing [x i ;x j ] and expressing it as a linear combination of the basis elements x k . For the second transition (SC ! FL) we can take the generators to be the basis elements, and the relations to be all commutation relations.

The reverse arrows are significantly harder.

Todd-Coxeter Type Algorithms

In case L is finite dimensional, the transition FL ! SC can be achieved by applying various kinds of Todd-Coxeter techniques.

The first and perhaps most practical approach is to start with a unique presentation for each element of L(A). This can be done by allowing, in the presentation of a member of L(A), only those monomials to occur that belong to a so-called Hall basis -cf. Reutenauer [START_REF] Reutenauer | Free Lie algebras[END_REF] ) y h)g AbasisofL(A) is obtained from H by interpreting its elements as members of L(A); this is the corresponding Hall basis. Hall bases exist. Thus, L(A) can be viewed as an infinite-dimensional Lie algebra (provided jAj > 1) with an ordered basis. Moreover, given an arbitrary monomial in L(A),byuseofthe Jacobi identity it can easily be rewritten to a normal form: a linear combination of Hall monomials.

Given a finite subset R of L(A), the Todd-Coxeter algorithms search for a (finite) set S of Hall monomials of L(A) such that each element of the quotient Lie algebra L(A)=I,whereI is the ideal generated by R, has an inverse image in the linear span of S. Initially, in the algorithm, the set S is taken to be A.

T hestra te gyistoe xte ndS in such a manner that the multiplication of any two of its members gives an element of the linear span of S. To this end, combinations of the following two steps are taken:

1. Add to S monomials obtained from multiplication of two members of S. Another approach has been chosen by Roelofs in Reduce (cf. Roelofs [START_REF] Roelofs | The LIESUPER package for REDUCE[END_REF] and Gragert [START_REF] Gragert | Lie algebra computations[END_REF]). Its theoretical foundation is explained in van Leeuwen and Roelofs [START_REF] Van Leeuwen | Algorithms for Constructing algebras by generators and Relations[END_REF]. Here, instead of starting with a Hall basis in L(A), the authors work in the universal anti-commutative tensor algebra on the (formal) linear F vector space spanned by A, divide out the relations and subsequently impose instances of the Jacobi identity (instead of the consequences of the relations as in Step 2 above).

It is our intention to have both approaches built into ELIAS.

Ado's Theorem

The remaining transition SC ! GL can be seen as an effective version of Ado's theorem (see Bourbaki [START_REF] Bourbaki | Groupes et Algèbres de Lie[END_REF], Chapt. VI). Up to now, no satisfactory complete solution to this problem is known. For instance, in Bourbaki [START_REF] Bourbaki | Groupes et Algèbres de Lie[END_REF], an effective solution is described, but a simple complexity analysis gives a clear signal not to attempt an implementation of the implicitly given algorithm.

In this section we try to find matrix representations of finite-dimensional Lie algebras defined over a field of characteristic 0, given by structure constants. We shall succeed here only for some special classes of Lie algebra. Throughout L will be a finite-dimensional Lie algebra with basis 1 ;:::;x n g.T h e universal enveloping algebra of L will be denoted by U(L). We first recall some results proved in [START_REF] Jacobson | Lie Algebras[END_REF],

Chapter VI.

Proposition 1.1

The Lie algebra L has a faithful finite-dimensional representation if and only if there is an ideal I of U(L) of finite codimension such that L \ I =0.

Proof. We only prove the if part. For the proof of the other direction we refer to Jacobson [START_REF] Jacobson | Lie Algebras[END_REF]. Suppose that I is an ideal of U(L) of finite codimension such that \ I =0.SetA = U(L)=I,thenA is a finitedimensional associative algebra containing L. This algebra contains an identity element. From this it follows that the regular representation (sending an element x 2 A to the matrix of the right multiplication by x in A) is faithful. By restricting this representation to the subspace L A we obtain a faithful representation of L in gl(A).

2

An element a of an associative algebra A over the field is called

algebraic if there is a nonzero polynomial f 2 F[z] such that f(a)=0.I fI is an ideal of A then a is called algebraic modulo I if f(a) 2 I for some nonzero polynomial f 2 F[z].
Lemma 1.2 Let fx 1 ;:::;x n g be a basis of L. An ideal I of U(L) is of finite codimension if and only if every x i is algebraic modulo I. Proof. (cf. Jacobson [START_REF] Jacobson | Lie Algebras[END_REF]) Let f i 2 F[z] be a nonzero polynomial such that f i (x i ) 2 I.L e tn i be the degree of f i . Then any power of x i is congruent modulo I to a linear combination of the elements 1;x i ;x 2 i ;:::;x ni 1 i . Hence a monomial x k1 1 x kn n is congruent modulo I to a sum of monomials of the form x m1 1 x mn n where 0 m i <n i . Now by the Poincaré-Birkhoff-Witt theorem ( [START_REF] Jacobson | Lie Algebras[END_REF], p. 156), we have U(L)=I is finite dimensional.

This proves the 'if' part. The other implication is trivial.

2 Let N be a nilpotent Lie algebra, and q be the smallest integer such that all q +1 -fold brackets of elements of N are zero. Then q is called the nilpotency class of N. following generalization of Ado's theorem was proved in Block [START_REF] Block | On nilpotency in the Ado-Harish-Chandra Theorem on Lie algebra representations[END_REF]. Theorem 1.3 Let L be a finite-dimensional Lie algebra. Suppose K is a nilpotent ideal of L of nilpotency class q. Then there exists a faithful finite-dimensional representation of L such that (x 1 x q+1 )=0 for all x 1 ;:::;x q+1 2 K.

Proof. See Block [START_REF] Block | On nilpotency in the Ado-Harish-Chandra Theorem on Lie algebra representations[END_REF].

2

We now describe two cases where we can find ideals I of U(L) finite codimension such that = 0. Proposition 1.4 Let L be a nilpotent Lie algebra of nilpotency class q.L e tI k be the ideal of U(L) generated by fx k 1 ;:::;x k n g.T h e nI k has finite codimension and there is an m such that 1 <mq+1 and L \ I m =0 . Proof. The fact that I k has finite codimension follows from Lemma 1.2. By Theorem 1.3 there exists a faithful finite-dimensional representation of L such that all elements of L are mapped to nilpotent linear transformations. Let I be the ideal corresponding to this representation. It follows that there is an m>1 such that x m i 2 I for 1 i n.NowI m I and I \ L =0 ,sothatI m \ L =0 .T a kem minimal such that I m \ L =0 ; clearl m>1. By Theorem 1.3 we infer that there exists a faithful finite-dimensional representation of L such that (x q+1 )=0for all x 2 L. Hence, I q+1 \ L =0 . It follows that 1 <mq+1. 2 Lemma 1.5 Let f 1 ;:::;f n 2 F[z]be polynomials such that f i (ad x i )=0 .L e tI be the ideal of U(L) generated by ff 1 (x 1 );::: ;f n (x n )g.I fx 2 L \ I then x 2 Z(L).

Proof. Let x = n X i=1 g i f i (x i )h i (1)
be an element of L \ I,whereg i and h i are elements of U(L).L e t denote the extension of the map ad : L ! End F (L) to U(L).Wehave

ad x = (x)= n X i=1 (g i )(f i (x i ))(h i )= n X i=1 (g i )f i (ad x i )(h i )=0 (2)
implying that x 2 Z (L).

2

The next statement concerns Lie algebras L for which Z (L) \ [L; L]=0 . Such a Lie algebra has a basis fx 1 ;::: ;x n gover F such that 1. fx 1 ;::: ;x s gis a basis of Z (L) (where 0 s n).

2. The space spanned by fx s+1 ;::: ;x n gis a subalgebra of L.

A basis with these properties is called a good basis of L. Starting from an arbitrary basis of L, it easy to obtain a good basis.

Proposition 1.6 Suppose that Z (L) \ [L; L]=0and let fx 1 ;::: ;x n gbe a good basis basis of L over F . We define the polynomials f i 2 F [z] as follows: if 1 i s,t h e nf i = z 2 .O t h e r w i s e ,i fs< in ,t h e nf i is the minimal polynomial of ad x i over F .L e tI be the ideal of U (L) generated by ff 1 (x 1 );::: ;f n (x n )g.T h e nI is finite codimension and L \ I =0 .

Proof. By Lemma 1.2, I has finite codimension. Let x be an element of U (Z(L)) \ I . We can write

x = s X i=1 e i x 2 i + s X i=1 g i x 2 i + n X i=s+1 p i f i (x i )q i
where the e i are elements of U (Z(L)),t heg i are sums of monomials, each monomial containing at least one x i such that i>sand p i ;q i arbitrary elements of U (L). In the process of straightening monomials in x 1 ;::: ;x n to express them as linear combinations of standard monomials we make substitutions of the form

x i x j = x j x i + n X k=1 c k ij x k
By condition (2) above, we have that c k ij =0for k =1 ;::: ;s. This, together with the fact that the constant term of f i is 0, implies that no monomial of P p i f i (x i )q i lies in U (Z(L)). The same is valid for P g i x 2

i . It follows that P g i x 2

i + P p i f i (x i )q i =0 . The conclusion is that U (Z(L)) \ I is the ideal in U (Z(L)) generated by fx 2 1 ;::: ;x 2 s g.Nowletx 2 I \ L. From Lemma 1.5, we infer that x 2 Z (L). Hence x 2 U (Z(L))\I.B u tU (Z(L)) is the commutative polynomial ring over the variables x 1 ;::: ;x s . From this we see that the ideal I \ U (Z(L)) of U (Z(L)) does not contain linear elements. It follows that x =0 .

2

Remarks.

1. If we have an ideal I of U (L) of finite codimension, then by the algorithm described in Linton [START_REF] Linton | Constructing Matrix Representations of Finitely Presented Groups[END_REF], [START_REF] Linton | On Vector Enumeration[END_REF] (which is implemented in GAP) we can calculate a basis and a multiplication table of U (L)=I.

Hence, we can check whether L \ I =0and we can calculate the matrices corresponding to the representation determined by I .

2. In the case where Z (L) \[L; L]=0(Proposition 1.6), we can calculate a good basis of L.T hefi rs t the action of this subalgebra on the solvable radical R. Hence the importance of being able to calculate a Levi subalgebra. For the algorithm computing a Levi subalgebra we follow Rónyai et al. [START_REF] Rónyai | Computing Levi decompositions[END_REF].

In the sequel R k will denote the ideal

L = R + S 1 = R + R 2 + S = R + S
It that S is a Levi subalgebra of L. 2 Since the radical of S 1 (which is R 2 ) and the radical of L=R 2 (which is abelian) are nilpotent, we can reduce to the case where the solvable radical is nilpotent. Now suppose that the solvable radical

R of L is nilpotent. Let R = R 1 R 2 R m =0
be the lower central series of R. We note that this series can be computed efficiently (see Beck em et al. [START_REF] Beck | Computing the structure of a Lie algebra[END_REF]).

Let fu 1 ;:::;u s gbe a maximal linearly independent set in the complement of R. Then we have the commutation relations:

[u i ;u j ]= s X k=1 k ij u k mod R 1
and the u i span a Levi subalgebra modulo R 1 . We are looking for elements y 1 ;:::;y s of L that span a Levi subalgebra modulo R m =0. To this end, we construct a series y t i for 1 i s and 1 t m such that fy t 1 ;:::;y t s gspans a Levi subalgebra modulo R t ,i.e.

[y t

i ;y t j ]= s X k=1 k ij y t k mod R t

For the initialization we set y 1 i = u i for 1 i s. now describe the iteration step. We define a vector space V t by the formula R t = R t+1 V t This is a system of equations for the v t i . Since the equations are modulo R t+1 , the left-hand as well as the right-hand side can be viewed as elements of V t . By Levi's theorem applied to the Lie algebra L=R t+1 this system has a solution. The conclusion is that after m 1 iteration steps we have found a Levi subalgebra of L.

Remark. The method described here runs in polynomial time. This fact is proved in [START_REF] Rónyai | Computing Levi decompositions[END_REF].

y

  Research supported in part by Hungarian National Foundation for Scientific Research grant T016503 and by the Dutch Technology Foundation STW.

  2. Use linear relations of the form [[[r;t];t 1 ];t n ]for r 2 R and t i 2 A to replace members of S by smaller Hall monomials.Various strategies for applying Steps 1 and 2, etc. are possible, but clearly, such a procedure will only terminate if the Lie algebra L = L(A)=I is finite dimensional. By a result in Ufnarovsky[START_REF] Ufnarovsky | Combinatorial and asymptotic methods in algebra[END_REF], the converse is true, i.e. such a procedure does indeed terminate if dim(L) < 1. This algorithm has been implemented by Gerdt and Kornyak in C code (see Gerdt and Kornyak[START_REF] Gerdt | Construction of finitely presented Lie algebras and superalgebras[END_REF]).

  By the following lemma we can reduce the problem of calculating a Levi subalgebra to the case where the solvable radical is nilpotent. Let S 1 be the inverse image in L of a Levi subalgebra of L=R 2 .I fS is a Levi subalgebra of S 1 ,thenS is a Levi subalgebra of L. Proof. (cf.Jacobson[START_REF] Jacobson | Lie Algebras[END_REF], Sect. It is clear S is a semi-simple subalgebra of L.Furthermore,R 2 is the solvable radical of S 1 . Hence

	Lemma 2.2

[R; [R; [;[R; R] ]]] (k copies of R)

s basis elements form a basis of Z (L). The next basis elements will form a basis of [L; L]. Finally we complete the basis.

The representation obtained by Proposition 1.6 is closely related to the following one. Using a good basis we see that we can write L = Z (L) K where K is an ideal without centre. A faithful representation is given by the direct sum of the adjoint representation of K and a faithful representation of Z (L) (which is easy to construct).

Example. Consider the Heisenberg algebra H of 1.2. A vector space basis of H is fx; y; zg and the Lie bracket is specified by y]=z; [x; z]=[ y; z]=0 . Following Proposition 1.4, we try the ideal I 2 of U (L) generated by fx 2 ;y 2 ;z 2 g. Using the vector enumeration package of GAP,( w h ic hu s e sth e algorithm described in Linton [START_REF] Linton | Constructing Matrix Representations of Finitely Presented Groups[END_REF], [START_REF] Linton | On Vector Enumeration[END_REF]) we find that f1;x;y;z;xygis a basis of U (L)=I 2 . The matrices of the corresponding representation are

which indeed gives a GL presentation of H (different from that given in 1.2).

Levi Decomposition

The algorithm to be discussed in this section is part of a suite of routines built to identify the structure of a Lie algebra given by a table of structure constants. See Cohen and de Graaf [START_REF] Cohen | Lie algebraic computation[END_REF] for more details on other routines, and Rand et al. [START_REF] Rand | On the identification of a Lie algebra given by its structure constants. I. Direct decompositions, Levi decompositions, and nilradicals[END_REF] for earlier versions of the specific algorithm under discussion. Although we have no direct evidence, the fact that the Levi decomposition is used in various proofs of Ado's Theorem might indicate its use in constructing matrix representations.

For the duration of this section, L will be a Lie algebra of dimension over the field of characteristic 0, given in the SC presentation. Thus, L has a basis fx 1 ;::: ;x n gand its Lie multiplication is described by

where c k ij 2 F . This set of structure constants fc k ij g will be the input of our algorithms.

Theorem 2.1 (Levi) If L is not solvable, then there exists a (necessarily semi-simple) subalgebra S of L such that L is the semidirect product of S the solvable radical of L.

Proof. See Jacobson [START_REF] Jacobson | Lie Algebras[END_REF], Section III.9.

2

The subalgebra S in the conclusion of this theorem is called a Levi subalgebra of L. For solvable Lie algebras not much structure theory is known. So the computational analysis of the structure of the Lie algebra is not very promising in this case. On the other hand, for semi-simple Lie algebras a very elaborate theory is available. So the structure of the Levi subalgebra may be analysed in detail as well as


Ufnarovski

S Cojocaru

V Ufnarovski

BERGMAN under MS-DOS and Anick's resolution

Keywords: Gröbner basis, Hilbert series, resolution

Introduction

BERGMAN is an effective program for calculating the Gröbner basis (both for commutative and noncommutative case) and monomial Poincaré series, elaborated at Stockholm University (J. Backelin) for SUN-station (and some other types of computers). In our implementation on an IBM PC, we used the original source of J. Backelin (and his valuable help) [START_REF] Backelin | Calculating Gröbner bases fast[END_REF], and added some new additional functions, especially for the noncommutative algebras. To illustrate them we give all necessary definitions and several examples.

Main Examples

Let A =<X jR>be a finitely presented (noncommutative) associative algebra over field K: Here are the main examples of algebras that will help us to illustrate some following definitions (later we will refer to them as main examples). [START_REF] Anick | Diophantine equations Hilbert series and undecidable spaces[END_REF] A =<e 1 ;e 2 ;e 3 ; :::j[e i ;e j ]=( i j)e i +j >; where char K =0and [a; b]=ab ba: Though the last example does not look as finitely presented, it is evident that e 1 and e 2 generate the algebra (e k+1 = [ek;e1] k 1 for k 2). Slightly less trivial is the fact that it is sufficient to have only two relations: [e 3 ;e 2 ]=e 5 ;[e 4 ;e 3 ]=e 7 (see Ufnarovskij [START_REF] Ufnarovskij | Poincaré series of graded algebras[END_REF]). Nevertheless, we will use this example in this infinite presentation to allow the reader to see how definitions work in the infinite case. This is also an example of an universal enveloping algebra: A = U(L); where L is a Lie algebra with the same sets of generators and relations except that the commutator [a; b] is now interpreted as a Lie product. If we interpret it as a graded commutator [a; b]=ab ( 1) jajjbj ba; the second example can also be considered as an universal enveloping algebra of 4-dimensional Lie superalgebra: L =<x;yj[x; x]= [y; y] >:

Hilbert Series and Global Dimension

Note that all algebras in our examples are graded algebras: A = A n ; where all components A n are finite dimensional and A n A m A m+n : For the last example grading is less trivial: e n 2 A n :

We restrict our attention on graded algebras and introduce the following:

Definition 3.1 The generating function H A = H A (t)= P 1 1 (dimA n )t n is called Hilbert series of an algebra A:
The Hilbert series of a graded algebra is one of our main objects of interest. It is a very useful invariant in the commutative case, but in the noncommutative case it also contains a lot of important information about the algebra. First, it plays the role of generalized dimension of an algebra. For example, it has the following trivial properties:

H AB = H A + H B ; H AB = H A H B ; 1 HAB = 1 HA + 1 HB 1:
If L is a graded Lie algebra (superalgebra), H L = P 1 1 a n t n and A = U(L); then

H A = 1 Y 1 1 (1 t n ) a n H A = 1 Y 1 (1 + t 2n 1 ) a2n 1 (1 t 2n ) a2n :
If L is a Lie algebra from our main Example 4, then

H L = t + t 2 + t 3 + )H A = 1 Y 1 1 1 t n = X p(n)t n
where p(n) is the number of partitions. So it is the example with non-rational Hilbert series. In the second main example we have H L =2t+2t 2 )H A = (1+t) 2

(1 t 2 ) 2 = 1 1 2t+t 2 : In our main Examples 1 and 3, the Hilbert series is equal to (1 2t + t 2 ) 1 : It can be directly checked from the first example, but the last one will be discussed in the sequel.

Secondly, the following two theorems of Anick [START_REF] Anick | Non-commutative graded algebras and their Hilbert series[END_REF][START_REF] Anick | Diophantine equations Hilbert series and undecidable spaces[END_REF] shows non-trivial properties of Hilbert series:

Theorem 3.1 Let H X (H R ) be the generating function of the number of the generators (relations, both minimal) of given degree. Then

gl:dimA 2 , H A =(1 H X +H R ) 1
(inequality for free algebras only).

In our main examples the value of (1 H X + H R ) is equal to Moreover, this algebra is an universal enveloping algebra of a Lie superalgebra, defined by quadratic relations only. This theorem is important.

Corollary 3.1 One cannot

Find an algorithm that takes relations as input and gives the Hilbert series as output. (Furthermore, one cannot detect in general if the Hilbert series of a given algebra is equal to some fixed series.)

Predict the behaviour of a Hilbert series, knowing only a finite number of its coefficients.

Normal Words and Gr öbner Basis

Despite pessimistic conclusions in the end of the previous section, it is possible to find the Hilbert series in important cases. Let us introduce some important definitions.

Let S be the set of all the words in the alphabet X (identifying 1 with the empty word). Consider the following ordering on S : f>gif either the length of word f is greater than that of g or they have the same length, but f is greater then g lexicographically. (More ingenious, the so-called admissible ordering may be considered too, but we restrict our attention only to this case.) Definition 4.1 Awordf 2 S is called normal (for A) if it cannot be written in A as a linear combination of words that are less than f:

In our first main example the words 1;x;y;xy;yx;y 2 are normal, but x 2 ;xy 2 are not. The same is true for the second main example. Why is xy 2 not normal? Because xy 2 = x 3 = y 2 x:

In the last main example the words of the form e k1 1 e k2 2 e km m are normal according the Poincaré- Birkgoff-Witt-theorem, if the alphabet and ordering is e 1 <e 2 <e 3 :It is much more complicated to express normal words in the alphabet e 1 ;e 2 only.

The following evident theorem explains how normal words can be used for the calculation of the Hilbert series. Note that other expressions (such as 'tips', for example) are used instead of 'obstruction'. We denote the set of all obstructions as F: Because obstructions are not normal words, every f i 2 F can be written as a linear combination of normal words: f i = u i : Definition 4. [START_REF] Anick | Non-commutative graded algebras and their Hilbert series[END_REF] The set G = ff i u i g is called a (reduced) Gröbner basis (for A).

In our main examples:

1. G = fx 2 ;xy 2 g(evidently).

2. G = fx 2 y 2 ;xy 2 y 2 xg: 3. G = fxy k xy k+1 jk =0;1;2;:::g: 4. G = fe j e i e i e j (j i)e i+j jj>ig:

All those examples can be easily checked by hand (see [START_REF] Ufnarovski | Combinatorial and asymptotic methods of algebra[END_REF]). BERGMAN is a powerful tool to calculate Gröbner basis in the more complicated cases.

Of course, knowing an obstruction set we can reconstruct normal words: So, the algebra from our first main example is associated with the monomial algebra for our second example. Note also that all universal enveloping algebras for Lie algebras with the same Hilbert series have, according to the PBW-theorem, the same associated monomial algebra (in some alphabets). Note also that definitions depend upon choice of the generator set (alphabet) and ordering.

More generally, a Gröbner basis for any ideal I is its subset G; such that the set of highest terms of elements from G contains the set of obstructions for A = K<X>=I. Note that the reduced Gröbner basis may be easily obtained from an arbitrary Gröbner basis (by self-reducing) and determined uniquely for a given ordering.

n chains and PoincaréSeries

The next step is to introduce some homological algebra. Let us consider a graph =(V;E); where the set of vertex consists of the union of the unit 1; alphabet X and all proper suffixes of the obstructions. Edges E are defined as follows: 1 x for every x 2 X and in other cases f g if and only if the word fg contains the only obstruction and this obstruction is its suffix (maybe coinciding with fg).

In our main examples 1 and 2, the graph looks like 1

( R

x y

( Ryy

In the third example, vertices (except 1 and y) have the form y n x and are connected to each other (including itself). It the fourth main example, vertices are e i and (considering 1 as e 1 ) every e i is connected with every e j with i>j:

In our first two main examples we have H 1 A =1 2t+t 2 +t 3 t 3 t 4 +t 4 +t 5 =1 2t+t 2 In the third one we also have H 1 A =1 2 t+t 2 . The reader can interpret the connections between partitions that we have as a sequence in the last main example.

Anick's Resolution

To calculate the Poincaré series in the general case, we construct Anick's resolution [START_REF] Anick | On the homology of associative algebras[END_REF]:

C n A ! C n 1 A !C 1 A!K !0
i n (u)=û+i n (u d n (û))
where û is the highest term of u and is its coefficient.

Note that: d 0 calculate, for every non-empty word f; its normal form f;i 0 acts identically. d 1 calculate, for any obstruction, f f;i.e. recover the element of Gröbner basis from its obstruction. To apply 1 for arbitrary word of form fsone need to be more careful: d 1 (fs)=R 0 ( fs fs): (in general, use the map R n : C n+1 N ! C n N; the fixed n-chain in the beginning and reduce the remaining part to normal form).

In our main examples:

1. d n (f)=ffor f 2 C n and d n (fs)=R n 1 ( fs) in general (those formulas are valid for every monomial algebra).

2. In tensor language:

d 2 : x 3 ! x 2 y xy 2 1 d 2 : x 2 y 2 1 ! x 2 y 2 xy 2 x

Finite State Automata and Lie Algebras

The main problem in noncommutative cases is that Gröbner basis is usually infinite. However, by using finite state automata we can try to predict the infinity behaviour of our Gröbner basis, or at least the obstruction set on infinity. The main idea of this approach was described in Ufnarovsky [START_REF] Ufnarovski | Calculations of growth and Hilbert Series by Computer[END_REF], and can be illustrated here by our third main example: having sufficient terms from the obstruction set, for example, x 2 ;xyx;xy 2 x; xy 3 x; xy 4 x, one can predict the whole family: xy n x: This kind of prediction can be formalized in terms of regular languages (or equivalently, finite state automata). Quite often, this prediction gives the correct answer that can be proved using other arguments. Nevertheless, the possibility of prediction is restricted. First, it is impossible in general cases, as we have already mentioned. Second, algebras that have a regular obstruction set also have a rational Hilbert series, and either polynomial or exponential growth. So, the Hilbert series for our fourth main example could not be predicted in this manner after a finite number of calculations in terms of only two generators e 1 ;e 2 :But even in a simple class of universal enveloping algebras, these predictions are impossible, as we see: Theorem 7.1 [START_REF] Lichtman | On Growth of Lie Algebras[END_REF] Let L be a free solvable Lie algebra of solvability length k, U(L) be its universal enveloping algebra. If k>2, then the growth of L and U(L) is almost exponential (less than exponential growth [2 m ] but greater than growth [2 m ] for any <1).

Bergman Package under MS-DOS

The BERGMAN package was elaborated by Backelin As to Anick's resolution, it can be calculated both on IBM PC and UNIX-stations (and takes, for example, about 10 minutes to calculate Poincaré series up to degree 12).

Pure commutative Gröbner basis calculations can also be performed quite quickly. For example, the well-known 6-cyclic system of equations takes from 1-3 minutes (depending on ordering), and this calculation cannot be performed on the same computer both by MAPLE and MATHEMATICA).

Theorem 4 . 2

 42 Let B =<Xj F> .T h e na l g e b r a sA and B have the same sets of normal words and, in particular, H A = H B : Definition 4.4 Algebra B from the previous theorem is called the monomial algebra, associated with A:

Example 2.1 A

  =<x ;yjx 2 =0 ;xy 2 =0> Example 2.2 A =<x ;yjx 2 =y 2 > Example 2.3 A =<x ;yjx 2 xy > Example 2.

  + t 3 1 2t + t 2 1 t t 2 + t 5 + t 7 so only the second and third examples are algebras of global dimension 2. For every system of diophantine equations S =0 ;there exists a finitely presented algebra A (which can be constructively expressed in terms of the coefficients of the S) such that A has global dimension 2 if and only if the system S =0has no solutions.

	1 2t + t 2 Theorem 3.2 1	2; 3	4

Theorem 4.1

  The set N; consisting of all normal words, forms a basis for the algebra A: Its Hilbert series can be calculated as H A = P 1 0 d n t n ; where d n is the number of normal words of degree n: Awor df 2 S is called an obstruction if f is not normal itself, but every proper subword is normal.

	Following Anick, let us introduce
	Definition 4.2

  It is sufficient to define module homomorphisms d n : C n A ! C n 1 A only for terms f 1: It is convenient to identify C n N with C n N: Then the map d n is defined as d n+1 (f)=f i n d n ( f) and i n :ker d n 1 ! KC n N is defined recursively:

  (Stockholm University) originally for SUN/Sparc stations, written in PSL (a dialect of LISP, used in REDUCE), it was successfully transfered to an IBM PC at the Institute of Mathematics of Moldova. It can be used both under REDUCE and (more easily) under a specially written shell (implemented by A. Colesnicov and L. Malahova). Main possibilities: commutative Gröbner basis calculations in two different strategies; noncommutative Gröbner basis calculations; calculations of Hilbert series and Poincaré series of the associated monomial algebra; arbitrary long integer or Z p coefficients of relations; input and output both in LISP and Maple notations.From the shell there are several separate programs -specially written for the noncommutative case that allow us (after calculating the Gröbner basis) to:the behaviour of the highest terms of the infinite Gröbner basis using its finite part; calculate growth and Hilbert series; calculate Anick's resolution and Poincaré series up to a given degree (implemented by A. Podoplelov).To estimate the possibilities that BERGMAN gives, let us consider one example.Its Hilbert series can be calculated both from the noncommutative and commutative points of view (considering the homology of the related commutative algebra -see Roos[START_REF] Roos | A computer-aided study of the graded Lie algebra of a local commutative noetherian ring[END_REF] for details). So one can compare this with one of the best commutative programs -MACAULAY (old version). But maybe the best results could be obtained from considering this example from the point of view of Lie superalgebras.

	Deg	Time for	Time for	Time for	Time for
		BERGMAN MACAULAY MACAULAY BERGMAN
		Sparcserver Sparcserver Mac	IBM-PC
		40 MHZ	40 MHZ	16.7 MHZ	25 MHZ
	192 MB 20 . 3 2 30 . 3 7 40 . 4 4	192 MB <1 <11 8 MB <11 4 MB 1 <15 2
	50 . 5 3	1	1 6	3
	60 . 6 1	4	7 5	3
	7	0.73	35	535	4
	8	0.94	372	5020	5
	9	1.21	3416	-	6
	10	1.56	31742	-	8
	11	2.04	259647	-	9
	12	2.84	-	-	12
	13	4.47	-	-	18
	14	7.49	-	-	31
	15	13.9	-	-	116
	16	27.8	-	-	477
	17	59.3	-	-	2443
	18	167	-	-	11601
	19	411	-	-	-
	20	1061	-	-	-
	Sparcserver 690 MP (40 MHZ Cypress Sparc,192 MB int. memory) Macintosh SE/30
	(68030. 16.67MHZ,8M) and 486SX 25 MHz IBM PC compatible computer with 4 MB
	RAM were used.
	Example 8.1
		A =< x;y;z;tjxx xy yx;xz + zx yt ty;
			yz + zy;zt + tz; zz; tt >

Definition 5.1 n-chain is a word, that can be read in graph during a path of length (n +1);starting from 1: Let C n be a set of all n-chains.

So,

The only 1-chain is 1 itself: C 1 =1: The only 0-chains are letters from the alphabet: C 0 = X. The only 1-chains are obstructions: C 1 = F:

Let us enumerate n-chains for n 2 in our examples. In the first two C n = fx n+1 ;x n y 2 g

In the third

C n = fxy k1 xy k2 x xy kn xjk i 0g

In the last main example

C n = fe i1 e i2 :::e in+1 ji 1 >i 2 >i g


Alex J Dragt

A Lie connection between Hamiltonian and Lagrangian optics

Keywords:

It is shown that there is a non-Hamiltonian vector field that provides a Lie algebraic connection between Hamiltonian and Lagrangian optics. With the aid of this connection, geometrical optics can be formulated in such a way that all aberrations are attributed to ray transformations occurring only at lens surfaces. That is, in this formulation there are no aberrations arising from simple transit in a uniform medium. The price to be paid for this formulation is that the Lie algebra of Hamiltonian vector fields must be enlarged to include certain non-Hamiltonian vector fields. It is shown that three such vector fields are required at the level of third-order aberrations, and sufficient machinery is developed to generalize these results to higher order.

Introduction

In Hamiltonian optics rays are described using the Hamiltonian

H = (n 2 p 2 ) 1=2 (1)
The use of a Hamiltonian formulation is advantageous because Hamiltonian flows produce symplectic maps, and there is a well developed calculus, using both characteristic functions and Lie algebraic methods, for handling symplectic maps in an efficient and economical way [START_REF] Dragt | A Lie Algebraic Theory of Geometrical Optics and Optical Aberrations[END_REF][START_REF] Dragt | Foundations of a Lie Algebraic Theory of Geometrical In[END_REF].

However, the use of a Hamiltonian approach has the consequence, perhaps at first surprising, that the map describing simple transit in a uniform medium (free flight in optical parlance, and a drift in accelerator parlance), is nonlinear. Therefore, in a Hamiltonian approach to optics, aberrations (nonlinearities) arise not only from transfer maps associated with lens interfaces, but also from simple transit within and between lenses. This circumstance is perhaps of less consequence in graded index optics, where one expects to have aberration effects associated with transit (at least within lenses), but it might be viewed as a drawback for the use of Hamiltonian methods for optics involving only uniform media.

Let D be the map for transit (drift) over a distance `in a uniform medium having refractive index n.

Then, in Lie algebraic notation and using canonical coordinates, this map may be written in the form D = exp : `(n 2 p 2 ) 1=2 : [START_REF] Dragt | Foundations of a Lie Algebraic Theory of Geometrical In[END_REF] for the action of this map on q and p we find the result

Dq = q + `p=(n 2 p 2 ) 1=2 (3) 1365-8050 c 1997 Chapman & Hall Dp = p (4)
We observe, as advertised, that relation (3) is nonlinear.

Instead of using the canonical coordinates q, p to specify a point in phase (ray) space, as is done in the Hamiltonian formulation, one might instead use the Lagrangian coordinates q, _ q. From (1) we have the result _ q = @H=@p = p=(n 2 p 2 ) 1=2

(5)

Suppose we let the map D act on the pair q, _ q. From (3)-( 5) we find the result Dq = q + `_ q (6)

D _ q = _ q (7)
We see that in Langrangian coordinates, unlike the case of canonical Hamiltonian coordinates, the map for simple transit is completely linear. Consequently, in a Lagrangian formulation of optics and in the case of uniform media, all aberrations arise only from transfer maps associated with lens interfaces. The purpose of this note is to study the relation between Hamiltonian and Lagrangian coordinates and dynamics in more detail.

Transformation between Hamiltonian and Lagrangian Coordinates

To describe the relation between Hamiltonian and Lagrangian optics, introduce the transformation T with the property

T q = q (8) T p = _ q = p=(n 2 p 2 ) 1=2 (9)
Thus, T maps the Hamiltonian variables q, p into the Langrangian variables q, _ q. Note from ( 8) and (9) that T is not symplectic, since it does not preserve the fundamental Poisson brackets between q and p.

Let us employ T to rewrite relations (3), (4), ( 6) and (7). From (6), ( 7), ( 8) and (9), we deduce the relations DT q = Dq = q + `_ q = T q + `T p = T (q + `p) = T exp[( `=2) :p 2 :]q (10)

DT p = D _ q = _ q = T p = T exp[( `=2) :p 2 :]p (11)
Upon comparing (2), ( 10) and (11), we obtain the operator result

T 1 DT = exp[( `=2) : p 2 :] (12)
or, more explicitly,

T 1 exp[: `(n 2 p 2 ) 1=2 :]T = exp[( `=2) :p 2 :] (13)
3 Explicit Form for Transformation It would be useful to have T itself in explicit operator form. Although we know that T is not symplectic, it may still be possible to write T in Lie form with the aid of some non-Hamiltonian vector field. Consider the vector field V defined by the equation

V = p 2 p (@=@p) (14)
Evidently, V has the properties

V q =0 (15) V p = p 2 p (16)
Let us use V to generate an autonomous flow parameterized by an independent variable that we will call t. Doing so gives the differential equations

q 0 = V q =0 (17) p 0 = V p = p 2 p (18)
Here we have used a prime to denote the differentiation (d=dt).

Let us integrate (17) and (18). In doing so, we will find that we are well on our way to discovering an explicit representation for T . From (18) we find the result

p p 0 =( d=dt)(1=2)(p 2 )=( p 2 ) 2 (19) Let denote the quantity p 2 , = p 2 (20)
With this notation, (19) can be written in the forms

0 =2 2 (21)
or

d= 2 =2 dt (22)
Equation ( 22), with the initial condition (0) = 0 , can be integrated by quadrature to give the result

(t)= 0 (1 2t 0 ) 1 (23)
Next substitute (23) into (18). Then, for the components p j of p we find the differential equations p 0 j = 0 (1 2t 0 ) 1 p j (24)

These equations can be rewritten in the form

dp j =p j = 0 (1 2t 0 ) 1 dt (25)
and thus can also be integrated by quadrature. The results, with the initial conditions p j (0) = p 0 j ,arethe relations log(p j =p 0

j )= (1=2) log(1 2t 0 ) (26)
or

p j = p 0 j =(1 2t 0 ) 1=2 (27)
Finally, upon combining (20) and ( 27), we find the result

p(t)=p 0 =[1 2t(p 0 ) 2 ] 1=2 (28)
In terms of vector fields, (28) is equivalent to the result

exp(tV )p = p=[1 2tp 2 ] 1=2 (29)
which has as a special case the result

exp[(1=2)V ]p = p=[1 p 2 ] 1=2 (30)
Note that the left-hand side of (30) resembles the left-hand side of (9). In addition, we immediately have from (15) the result

exp[(1=2)V ]q = q (31)
Next, let W be the vector field defined by the equation

W = p (@=@p) (32)
For this field we have the result

W q =0 (33) W p = p (34)
The vector field W can also be used to generate a flow. For this flow we get the result

exp[ (log n)W ]q = q (35) exp[ (log n)W ]p = exp( log n)p =( 1 =n)p (36)
Now consider the joint effect of exp[ (log n)W ] and exp[(1=2)V ].

From (31) and (35) we find the relation

exp[ (log n)W ] exp[(1=2)V ]q = q (37)
From ( 30) and (36) we find

exp [ (log n)W ] exp[(1=2)V ]p = exp [ (log n)W ]fp=[1 p 2 ] 1=2 g = p =[n 2 p 2 ] 1=2 (38)
Upon comparing (8) and ( 9) with (37) and (38), we conclude that T is given by the operator relation

T = exp[ (log n)W ] exp[(1=2)V ] ( 39
)
4 Variation

Consider the map U defined by writing

U = T exp[(log n)W ] = exp[ (log n)W ] exp[(1=2)V ] exp[(log n)W ] (40)
From ( 35) and (36) we immediately have the relations

exp[(log n)W ]q = q (41) exp[(log n)W ]p = np (42)
Combining ( 8) with (41) gives the result

Uq = q (43)
Combining ( 9) with (42) gives the result

Up = T np = nT p = n _ q (44)
Note that U, like T , is also not symplectic. Suppose we use to rewrite the relations (3), ( 4), ( 6) and ( 7). From ( 6), ( 7), ( 43) and ( 44), we find the results (48)

= Dq = q + `_ q = Uq +(`=n)U p = U[q +(`=n)p] = U expf[ `=(2n)] :p 2 :gq (45)
DUp = Dn_ q = nD _ q = n _ q = Up = U expf [`=(
The relations (47) and (48) are particularly appealing because they relate the exact map for transit to the map for transit in the Gaussian approximation.

According to (40), U can also be written in exponential form. Indeed, we see from (40) that U is written in the form of a similarity transformation of the map exp[(1=2)V ], and therefore it should be particularly easy to combine all exponents into a single exponent. This is indeed the case. One procedure for doing so is to use the commutation rule fW;Vg=WV VW =2 V (49) Note that these modified maps are also entitled to be called surface maps, since they depend only on the shape of the lens surface and the values of the surrounding indices of refraction. With the aid of the definitions (60), we can rewrite (58) to obtain a representation for M of the form

M = U 1 [D g 1 S1 D g 2 S2 D g m 1 Sm 1 D g m ]U 1 m (61)
In this form we see that M, apart from the initial and final maps U 1 and U 1 m , can be viewed as the result of Gaussian transits (which yield linear maps, and thus are not a source of aberrations), and modified surface maps (which, in this representation, are the source of all aberrations). That is, in this form all aberrations arise from surface effects. Note also that if n 1 = n m , as is often the case, then U 1 = U m .

Complications

What are the Lie algebraic generators for the modified surface maps Sj ? Suppose, for the present purposes, we restrict our discussion to Gaussian and third order. We know that the original surface maps S j have (assuming axial symmetry) the Gaussian generator :q 2 : and the third-order aberration generators :(q 2 ) 2 :, :q 2 q p:,and:q 2 p 2 :. [Other Gaussian generators such as :p 2 : and :p q: and other third-order generators such as :(q p) 2 :, :p 2 q p:,and:(p 2 ) 2 : are allowed by axial symmetry and the symplectic condition, but in fact do not occur.] According to (60) and ( 52), if we wish to use the Sj we must add V to the list of generators; and we must also add all the generators that arise from commuting with the generators we already have. Let L denote the Lie operator given by the relation L =:q 2 =2:= q (@=@p)

A simple computation gives the results

;Vg =2 qpp (@=@p)+p 2 q(@=@p)

fL ; fL ;Vgg =2 q 2 p(@=@p)+4qpq (@=@p)

fL ; fL ; fL V ggg =6 q 2 q(@=@p)

We note that V and the generators given by ( 63)-(65) contribute only to third (and higher) order aberrations. Therefore, we need not consider the commutators of them among themselves or with third-order aberration generators of the form :(q 2 ) 2 :, :q 2 q p:, since the Lie operators thereby produced generate even higher order aberrations. Also, we note the relation :(q 2 ) 2 := 4q 2 q (@=@p)

Therefore, the Lie operator given by (65) is not new. Consequently, we conclude that the Sj are generated the Lie operators 2 :, :(q 2 ) 2 :, :q 2 q p:, :q 2 p 2 :, V , and those given by the right-hand sides of (63) and (64).

in the course of calculation, we wish to combine various Sj with various g k .T h e nw e must also consider the Gaussian generator :p 2 : and its commutators with the generators of the previous paragraph. Define two other Gaussian generators L + and L 0 by the relations L + = :p 2 =2:= p (@=@q) (67)

  2n)] :p 2 :gp (46) Consequently, we have the operator relation U 1 DU = expf [`=(2n)] :p 2 :g (47) or, more explicitly, U 1 exp[: `(n 2 p 2 ) 1=2 :]U = exp : [`=(2n)]p 2 :

which is easily checked from the definitions ( 14) and (32). A more direct approach, based on (15) and (29), is to observe the relations expf[1=( 2n2 )]V gq = q (50) expf[1=( 2n2 )]V gp = p=[1 n 2 p 2 ] 1=2

= np=[n 2 p 2 ] 1=2 = n _ q (51)

Upon comparing (43) with ( 50) and ( 44) with (51), we find the immediate result

Here, for future use, we have explicitly noted that depends on n.

Applications

Consider an optical system composed of a collection of drifts and lenses. Also suppose, for simplicity, that the system begins and ends with drifts. Then the map for the complete system is a product of maps of the form

Here, as before, the D j denote drift maps (both between and within lenses), and the S j denote surface transfer maps describing the effects of lens interfaces. For the drift maps we may use the relations ( 12) and (48) to write the representations

Note that the maps on the right-hand sides of ( 12) and (48) are both linear.

For simplicity, we will make use of (55). Let us write (55) in the form

where D g denotes the map for Gaussian drift,

With this representation, the product (53) can be rewritten in the form

Here we have also used the notation

See (52). Next, define modified surface maps Sj 1 by the relations

L 0 =:p q=2:= (1=2)p (@=@p) (1=2)q (@=@q)

(68)

We find the results fL 0 ;Vg=V (69) fL + ;Vg= p 2 p(@=@q)

(70) Also, we note the relation :(p 2 ) 2 := 4p 2 p (@=@q)

(71)

Therefore, the Lie operators given by ( 69) and ( 70) are not new. We conclude that the new operators are V , fL ;Vg,andfL ; fL ;Vgg.

These three new operators, along with those already known from the usual Hamiltonian treatment, can be organized in such a way that they have pleasing transformation properties under the action of L + , L and L 0 . Define the operator R 1 1 by the relation

Then it is easily verified from ( 63)-( 66) and ( 69)-( 72) that R 1 1 has the properties fL 0 ;R 1 1 g=R 1 1

fL ; fL ; fL 1 1 ggg =0

Now define operators R 1 0 and R 1 1 by the relations

From these definitions we find that the R 1 m obey the relations

As the notation is meant to suggest, these relations are analogous to those for a spin 1 object in the Lie algebraic treatment of angular momentum.

Indeed, the connection with spin 1 can also be made in another way. Let L be any Lie operator. For any L define an associated superoperator, denoted by #L#, that acts on any other Lie operator K by the rule #L#K = fL; Kg

The quantity is sometimes called the adjoint of L. Products and powers of superoperators are defined by repeated commutation. For example, (#L#) 2 is defined by

Now consider the 'Casimir' operator C defined by

Then one finds from (78)-(80) the result

Note that the factor (1)(1 + 1) is of the form j(j +1)with j =1.

Finally, for the record, let us list the explicit forms of the R 1 m . We find the results R 1 1 =(3=4)p 2 p (@=@p)+(1=2)(p q)p (@=@q)+(1=4)p 2 q (@=@q)

(85) R 1 0 = (2) 1=2 q pp (@=@p) + (2) 1=2 q pq + (8) 1=2 p 2 q (@=@p) + (8) 1=2 q 2 p (@=@q)

(86)

R 1 1 =(3=4)q 2 q (@=@q)+(1=2)(p q)q (@=@p)+(1=4)q 2 p (@=@p)

We conclude from the work of this section that the Gaussian and third-order treatment of the modified surface maps Sj requires the introduction of the three additional non-Hamiltonian Lie operators R 1 m .T his is the price to be paid at third order for a formalism that attributes all aberrations to (modified) surface maps. Evidently, our discussion can be extended to still higher order, and at these higher orders still more additional non-Hamiltonian Lie operators will be required. Of course, when all these operators (both Hamiltonian and non-Hamiltonian) are combined to compute as in (61), then all the net coefficients of all the non-Hamiltonian operators must vanish identically because we know that M, since it is a symplectic map, is expressible entirely in terms of Hamiltonian Lie operators.

This work was supported in part by Department of Energy grant DEFG0592-ER40748. It was begun at the Netherlands Research Institute for Applications of Computer Algebra, and completed at the Stanford Linear Accelerator Center. The support and hospitality of these two institutions is also gratefully acknowledged.


Vladimir P Gerdt
email: gerdt@jinr.dubna.su

Vladimir V Kornyak

An algorithm for analysis of the structure of finitely presented Lie algebras

Keywords:

We consider the following problem: what is the most general Lie algebra satisfying a given set of Lie polynomial equations? The presentation of Lie algebras by a finite set of generators and defining relations is one of the most general mathematical and algorithmic schemes of their analysis. That problem is of great practical importance, covering applications ranging from mathematical physics to combinatorial algebra. Some particular applications are construction of prolongation algebras in the Wahlquist-Estabrook method for integrability analysis of nonlinear partial differential equations and investigation of Lie algebras arising in different physical models. The finite presentations also indicate a way to q-quantize Lie algebras. To solve this problem, one should perform a large volume of algebraic transformations which is sharply increased with growth of the number of generators and relations. For this reason, in practice one needs to use a computer algebra tool. We describe here an algorithm for constructing the basis of a finitely presented Lie algebra and its commutator table, and its implementation in the C language. Some computer results illustrating our algorithm and its actual implementation are also presented.

Introduction

A Lie algebra L is an algebra over a commutative ring K with a unit. The non-commutative and nonassociative multiplication in a Lie algebra is called the Lie product, and is usually denoted by the commutator [ ; ]. By definition, the Lie product satisfies the following axioms:

[u; v]= [v;u]; skew symmetry [START_REF] Kac | Infinite Dimensional Lie Algebras[END_REF] [u; [v;w]] + [v;[w;u]] + [w;[u; v]] = 0; Jacobi identity [START_REF] Gebert | Beyond Affine Kac-Moody Algebras in String Theory[END_REF] for all u; v; w 2 L.

A finitely presented algebra is determined by a finite number of some of its elements called generators subject to a finite number of relations having the form of polynomials in the algebra. Any finitedimensional algebra is, obviously, a finitely presented one. Nevertheless, the concept of a finite presentation also covers a wide class of infinite-dimensional algebras. Some examples of such algebras having a natural constructive definition in terms of a finite number of generators and relations are:

1. Kac and Kac-Moody algebras [START_REF] Kac | Infinite Dimensional Lie Algebras[END_REF] with their generalization known as Borcherds algebras [START_REF] Gebert | Beyond Affine Kac-Moody Algebras in String Theory[END_REF]. 3. Any simple finite-dimensional Lie algebra can be generated by two elements only with the number and structure of relations independent on the rank of the algebra. This allows one to define such objects as Lie algebras of matrices of a complex size sl(), o() and sp(),w here may be any complex number, or even 1 [START_REF] Grozman | Defining Relations Associated with the Principal sl2subalgebras[END_REF].

The constructions of the last item are of interest in applications to integrable systems, for example, to the Leznov-Saveliev equation [START_REF] Leznov | Group-Theoretical Methods for Integration of Dynamical Systems[END_REF] also known as the two-dimensional Toda lattice or vector-valued Liouville equation. They also give a prescription for q-quantizing the Lie algebras of matrices.

Below we describe an algorithm for determining the explicit structure of a finitely presented Lie algebra from the defining relations, i.e. for constructing its basis and commutator table, and describe its implementation in C. In fact, our algorithm, if it terminates, produces the Gröbner basis [START_REF] Ufnarovsky | Combinatorial and asymptotic methods in algebra[END_REF] for the case of such non-commutative and non-associative objects as Lie algebras. The algorithm and its actual implementation is illustrated by a rather simple example arising in investigation of the Burgers equation. We also present the table containing computational statistics for Serre relations of all simple Lie algebras up to rank 10.

Algorithm

To construct finitely presented Lie algebras, several algorithms were elaborated and implemented in Reduce [START_REF] Gragert | Lie Algebra Computations[END_REF][START_REF] Akselrod | Construction of a Lie Algebra by a Subset of Generators and Commutation Relations[END_REF][START_REF] Gerdt | On Construction of Finitely Presented Lie Algebras[END_REF]. The refinement of Gragert's algorithm with extension to superalgebras was carried out by Roelofs [START_REF] Roelofs | The LIESUPER Package for REDUCE[END_REF].

These algorithms are based on the sequential construction of a subset of Lie monomials of a given length (or weight) together with the relevant consequences of the initial relations. Then all the Jacobi identities are verified to select those Lie monomials which are linearly independent modulo both Jacobi identities and the extended set of relations. The selected monomials form the spanning set of the corresponding homogeneous component of the Lie algebra under construction. If the relations are homogeneous, then all the elements of the set are basis ones. Otherwise, the set could be contracted by further computations with monomials and relations of larger length.

In the present algorithm the construction of basis elements and the relation consequences is done separately. Besides, at each step of the new relation generation we perform a Lie multiplication by a single generator only. This procedure allows one to decrease the number of Jacobi identities to be verified. From our computational experiments (see Sect. 4) this approach seems to be rather efficient. Before a more detailed algorithm description we explain some terms used in the text.

The set X = fx 1 ;x 2 ;:::;x k gofgeneratorsisa set of Lie algebra elements such that any other element may be constructed by their Lie product, addition and multiplication by elements in K (scalars).

A basis B(X) of a Lie algebra is a minimal set of elements such that any other element is their linear combination over the ring K.

A Lie monomial m(X) is an element of L constructed by Lie products of the generators x i .AL i e polynomial P(X) is a linear combination of Lie monomials.

Asetofdefining relations R is a set of Lie polynomial equalities of the form P(X)=0.

A Lie algebra L is called finitely presented if both sets X and R are finite. A finitely presented Lie algebra L F with an empty set of defining relations is called a free Lie algebra.

Any finitely presented Lie algebra can be considered as the quotient algebra of L F by the two-sided ideal generated by relations R. Thus, it makes sense to deal with only those Lie monomials which constitute a basis of the free Lie algebra, i.e. a set of Lie monomials which are not expressible in terms of others by means of (1-2).

It is known that a suitable basis of a free Lie algebra can be formed by regular Lie monomials [START_REF] Bahturin | Infinite dimensional Lie superalgebras[END_REF][START_REF] Mikhalev | Combinatorial Aspects of Lie Superalgebras[END_REF]. where u; v; w are regular and u<v , wuwith respect to some linear ordering of Lie monomials. Depending on the ordering chosen, one obtains a particular basis of a free Lie algebra. Among the whole variety of bases the most often used ones were introduced by Hall and Shirshov (see Bahturin et al. [START_REF] Bahturin | Infinite dimensional Lie superalgebras[END_REF]). Without getting into detail, we note that Shirshov and Hall orderings are analogous, in some sense, to the pure lexicographical and graded lexicographical orderings for associative words.

Monomials
In the present algorithm we use Hall ordering because it is compatible with the natural grading by length or by positive weight. The use of Shirshov ordering may be more convenient for analysis of a Lie monomial structure. However, as in the associative case, this ordering typically decreases the efficiency because a Lie monomial may contain a greater submonomial that complicates the structure of data and algorithm.

The algorithm below, if it terminates, produces the complete set of relations. The left hand sides of the latter form a set of Lie polynomials which is often called a Gröbner basis (see Ufnatovsky [START_REF] Ufnarovsky | Combinatorial and asymptotic methods in algebra[END_REF]).

AsetR of relations generating an ideal I of a free Lie algebra is called complete if (i). All the monomials in R are rewritten in terms of regular ones.

(ii). For each v 2 I also expressed in terms of regular monomials there exists a relation r 2 R such that the leading monomial of r is a submonomial of the leading monomial of v.

The complete set of relations R is called minimal if there is no R 0 R such that R 0 is also complete.

Hereafter, under reduction of a Lie polynomial modulo set of relations R we assume its rewriting in terms of regular monomials with substitutions of their submonomials in accordance with the relations.

In general terms, to rewrite a given set of Lie polynomials to the minimal Gröbner basis one should compute all possible consequences of these polynomials and remove all dependencies among them. The problem is to do that in the most efficient way. There were elaborated a number of optimizing criteria to avoid unnecessary reductions in computation of associative [START_REF] Ufnarovsky | Combinatorial and asymptotic methods in algebra[END_REF] and commutative [START_REF] Buchberger | Gröbner bases: an algorithmic method in polynomial ideal theory[END_REF][START_REF] Becker | Gröbner Bases. A Computational Approach to Commutative Algebra[END_REF] Gröbner bases. Unfortunately, analogous criteria have not been formulated yet for the non-associative case in such a way as to be applied in practice.

Nevertheless, we use some optimizing methods to decrease the volume of computation. The most important of them are the following: 1. To produce new relations, that is, the consequences of a given relation, we multiply it by the generators only. Consider the Jacobi identity (2) for the relation r:

[[u; v];r]= [u; [v;r]] [v;[u; r]] (3)
Here there are three alternatives:

(a) Both the left-and right-hand sides of (3) are reduced to zero. In this case a new relation is not produced.

(b) Both sides of (3) are reduced to nonzero expressions. In this case the new relation is obtained from r by successive multiplications by u and v. By applying the formula (3) recursively, the process of generating new relations is reduced to successive multiplication by generators.

(c) The right-hand side of ( 3) is reduced to zero while the left-hand side is not. In this case the corresponding consequence cannot be derived by successive multiplications by generators.

In our algorithm the latter case is treated separately once the subset of the complete set of relations has been generated in accordance with alternative (b). and modulo the relations treated up to that moment. This allows us to minimize resimplification of the calculated structures, and to keep the system of Lie monomials and relations as compact as possible at all times in the computation.

The input and output data for the algorithm are:

Input. The ordered set of generators X = fx 1 ;x 2 ;::: gwith prescribed positive integer weights w i (=1 by default); the set of scalar parameters P = fp 1 ;p 2 ;::: gif they are present in the relations; the set of defining relations R = fr 1 ;r 2 ;::: g,wherer i are Lie polynomials with coefficients from the commutative ring Z[p 1 ;p 2 ;::: ]of scalar polynomials;

the limiting number of relations to be generated.

Output.

The interreduced set of consequences of the input relations R = fr 1 ; r2 ;::: g; the list E = fe 1 ;e 2 ;::: gof Lie algebra elements linearly independent modulo R; the commutator table [e i ;e j ]=c k ij e k ; the table of scalar polynomials in p i which have been treated as nonzero during computation. Particular values of p i providing vanishing of these polynomials may cause branching of computation and, hence, changes of the algebra structure; dimensions of homogeneous components.

There are three steps in the algorithm:

1. Generation of the relation set R = fr 1 ; r2 ;::: gof the consequences of the initial set R.T h i ss t e p executes the subsequent multiplying of relations by generators adding nonzero results to the set of relations and substituting these new relations into the other ones. The process terminates if either all newly arising relations are reduced to zero or the number of relations goes up to the limit fixed at input. The second case means that either the algebra is infinite-dimensional or the input limiting number of the relations is too small. 2. Completion of the set E = fe 1 ;e 2 ;::: g. Some elements e i are obtained at Step 1 as Lie (sub)monomials of ri . However, generally, the set E produced must be completed by those regular commutators of already existing elements which do not occur in E. In doing so one must verify if new elements are indeed independent. It may happen that there exists a Jacobi identity containing the new element as a term and such that this identity is reduced to a new relation missing in the output of Step 1. If so one should add the new relation to R and go back to Step 1. Besides, in the case of a Lie superalgebra the Lie squares of the odd elements are also to be added.

Construction of the commutator table. At this step the commutators of the elements obtained at

Step 2 are computed directly. The commutators produced are reduced modulo the relation set R.

If the above algorithm terminates due to the input limiting number of relations, then the truncated output makes sense only if all ri 2 R are homogeneous. In this case we obtain a part of the whole Gröbner basis, and the set E forms a subbasis of the Lie algebra under construction.

Otherwise, the algorithm termination means we have a reduced and, hence, minimal finite Gröbner basis. Generally, it does not mean that the algebra is necessarily finite-dimensional. However, if at the last iteration of Step 2 no new elements e i were obtained, then we are done with a finitely-dimensional algebra. In the case of a finite Gröbner basis generating an infinite-dimensional algebra only those additional elements are to be included in set E which are regular Lie pairs of elements e i obtained at Step 2.

Implementation and Sample Session

The algorithm has been implemented in the C language. The source code has a total length of almost 7500 lines and contains about 150 C functions realizing: top level algorithms, Lie algebra operations, manipulation with scalar polynomials, multiprecision integer arithmetic, substitutions, list processing, input and output handling, etc.

The following session file has been produced on a 66 Mhz MS-DOS based AT/486 computer. We use here 32bit GCC compiler and GO32 DOS extender, though for the considered example the 16bit Borland C++ 3.1 environment is quite sufficient (and takes twice smaller space for the internal data structures). That illustrative example, arising in investigation of symmetries of well-known in mathematical physics Burgers equation leads to relatively compact output.

The relations contain three generators X , Y and T and five parameters c 1 ;:::c 5 which allow us to illustrate the classification aspects of the problem.

Note that the program asks for the output form of Lie monomials. In this example we choose the right-normed arrangement for non-associative monomials. It means, for instance, that Lie monomials [x; [x; [y; x]] and [[x; y]; [x; [x; y]]] are presented in the output as x 2 yx and (xy)x 2 y, respectively. Such notations are more compact and expressive especially for high degree Lie monomials, and widely used by algebraists. Otherwise, one can choose the standard output with explicit square brackets printed out. Input data can be entered from either a keyboard or from a separate file.

Enter name of existing or new input file -> burggen.in Input data: Generators: X Y T; Parameters: c_1 c_2 c_3 c_4 c_5;

Relations: 2 [[Y,X],Y] + c_2 [Y, X] + 2 c_5 Y; [[Y,X],X] + c_1 [Y, X] + [T,Y] + c_4 Y; [T,X] +
( Basis elements:

(

1) E = X 1 (2) E = Y 2 (3) E = T 3
Non-zero commutators of basis elements:

( Here E i are basis elements. In the case of an infinite-dimensional algebra the program prints out only those commutators which can be expressed in terms of the basis elements computed.

1 ) [ E,E]=2c/ c E 1 2 522 ( 2 ) [ E,E]=c E 13 3 2 22 2 ( 3 ) [ E,E]=( 4c -2ccc+ cc) / c E 23 5 5
It can easily be seen that for the generic values of parameters we have a three-dimensional nilpotent Lie algebra. The branching of the algebra structure is possible at the values of parameters c 2 =0and c 5 =0 . The computations with these particular values show that the choice (c 2 6 =0 ;c 5 =0 )gives also a three-dimensional algebra, the choice (c 2 =0 ;c 5 6 =0 )gives zero-dimensional algebra, the choice (c 2 =0 ;c 5 =0 )leads to the most interesting case of the infinite-dimensional algebra indicating the complete integrability of the Burgers equation.

Serre Relations for Simple Lie Algebras

Table 1 we present the results of application of the program to Serre relations (see, for example, Mikhalev and Zolotykh [START_REF] Mikhalev | Combinatorial Aspects of Lie Superalgebras[END_REF]) for all simple Lie algebras up to rank 10. The timings are presented for the above mentioned 66 Mhz MS-DOS based AT/486 computer. Any (semi)simple complex Lie algebra L possesses a Gauss decomposition L = E H F ,w he re H is a commutative Cartan subalgebra,a n dE and F are positive and negative nilpotent subalgebras, respectively. This decomposition is compatible with the following relations containing Cartan elements h i and Chevalley generators e i , f i corresponding to positive and negative simple roots of the algebra:

[h i ;h j ]=0 ; (4)
[e i ;f j ]= ij h j ;

(5)

[h i ;e j ]=a ji e j ; [START_REF] Ufnarovsky | Combinatorial and asymptotic methods in algebra[END_REF] [h i ;f j ]= a ji f j ; [START_REF] Gragert | Lie Algebra Computations[END_REF] (ad e i ) 1 aji e j =0 ; [START_REF] Akselrod | Construction of a Lie Algebra by a Subset of Generators and Commutation Relations[END_REF] (ad f i ) 1 aji f j =0 ; [START_REF] Gerdt | On Construction of Finitely Presented Lie Algebras[END_REF] where a ij is the Cartan matrix, i; j =1 ;:::;r = rank L: Note that for Kac-Moody algebras just the same relations hold with slightly different Cartan matrices.

Relations [START_REF] Akselrod | Construction of a Lie Algebra by a Subset of Generators and Commutation Relations[END_REF][START_REF] Gerdt | On Construction of Finitely Presented Lie Algebras[END_REF] include only Chevalley generators corresponding to positive and negative subalgebras E and F containing the principal part of the information about the algebra. These relations taken separately define subalgebras E and F . One can see that calculation of the exceptional algebra E 8 is the most difficult task among those in- Dim the dimension of the algebra, in is the number of input relations, N GB is the number of relations in the Gröbner basis, comm is the number of nonzero commutators, D GB is the maximum degree of the Lie monomials in Gröbner basis, Space is the maximum memory occupied by the computed structures, Time is the running time without expenses for input-output operations.

Conclusion

Unlike commutative algebra, where such a universal tool for analysis of polynomial ideals as Buchberger's algorithm for computing the Gröbner basis has been developed [START_REF] Buchberger | Gröbner bases: an algorithmic method in polynomial ideal theory[END_REF][START_REF] Becker | Gröbner Bases. A Computational Approach to Commutative Algebra[END_REF], its generalizations to non-commutative [START_REF] Ufnarovsky | Combinatorial and asymptotic methods in algebra[END_REF][START_REF] Mora | Seven Variations on Standard Bases[END_REF][START_REF] Kandri-Rody | Non-commutative Gröbner bases in Algebras of Solvable Type[END_REF], and especially to non-associative algebras are still far from being practically useful. Moreover, because of very serious mathematical and algorithmic problems still to be solved, there are only a few packages implementing the non-commutative Gröbner basis technique, and none of them so far is able to deal with non-associative algebras. This justifies the elaboration of other algorithmic techniques. Those described in earlier work [START_REF] Gragert | Lie Algebra Computations[END_REF][START_REF] Akselrod | Construction of a Lie Algebra by a Subset of Generators and Commutation Relations[END_REF][START_REF] Gerdt | On Construction of Finitely Presented Lie Algebras[END_REF][START_REF] Roelofs | The LIESUPER Package for REDUCE[END_REF] have been already applied to a number of problems in mathematical physics. The algorithm presented above reveals some common features with involutive techniques in commuta-tive algebra [START_REF] Gerdt | Involutive Polynomial Bases[END_REF]. Similar to the above consideration, in the involutive approach to Gröbner bases construction only multiplications by independent variables (prolongations) rather than S-polynomials are used. In the noncommutative case an analog of a Buchberger S-polynomial is a composition [START_REF] Ufnarovsky | Combinatorial and asymptotic methods in algebra[END_REF]. Thus, to construct aGröbner basis one can perform all possible compositions and reduce them modulo the current relation set. However, in the nonassociative Lie algebra case such a computational scheme meets very serious combinatorial obstacles. To recognize reducibility of the particular composition one has to do recursive transformations based on Jacobi identities. Our present algorithm, like that in Gerdt and Blinkov [START_REF] Gerdt | Involutive Polynomial Bases[END_REF], successively combines prolongations and reductions preventing massive recursive resimplifications.

Our C code can be easily generalized to handle Lie superalgebras.

  (super)algebras of string theories: Virasoro, Neveu-Schwarz and Ramond algebras[START_REF] Leites | Lie superalgebras[END_REF].

  c_3 Y; Right-normed output for Lie monomials? (y/n) -> y Standard grading assumes unit weight for every generator. Do you want to use a different grading? (y/n) -> y Enter non-zero positive integer weights for generators: Parametric coefficient at leading term of relation: c 2 Non-zero parametric coefficients:

  are called regular if they are either generators or commutators of the form [u; v] or [w;[u; v]],

2 .

 2 There is no need to multiply a relation by a generator which forms a regular monomial with the leading monomial of the relation since all such consequences are automatically reduced to zero. Let the relation have the form u + a =0with leading monomial u,s ot h a ta contains the other terms. Multiplying the relation by a generator x we obtain [x; u]+[ x; a]=0 .I f[x; u] is a regular monomial we must replace u by a. It leads to the identity [x; a]+ [x; a] 0 and, hence, does not produce a new relation. 3. All computations, starting with processing the input relations, are executed modulo identities (1-2)

  cluded in Table1. The number of initial relations here is 290. The program generates the Gröbner basis which contains 23074 relations involving Lie monomials up to degree 58 while the Lie algebra basis elements go up to 29th degree. The task requires 3 min 14 sec of computing time and bytes of memory.Unlike the whole set of Serre relations for E 8 the separate processing of relations (8) (or (9)) gives an example with twelve new relations arising at Step 2 of the algorithm in addition to 5508 relations derived at Step 1. Note that for E 8 one needs only 15 sec and 186096 bytes. Our computational experience shows similar situations with extra relations generated at Step 2 are rather rare. On the other hand Step 2 takes usually much less computing time than Step 1. That is why in pursuit of efficiency we postpone the analysis of those special situations to Step 2.The content of the columns in Table1is as follows:

Table 1

 1 Algebra Dim N in N GB N comm D GB Space, Time,

	bytes seconds

Acknowledgments

We are grateful to A. Cohen, P. Gragert, V. Robuk, M.Roelofs and especially to V. Ufnarovsky for fruitful discussions and useful remarks. This work was supported in part by the INTAS project No. 93-893.


Yuri L Sachkov
email: sachkov@sys.botik.ru

Controllability of affine right-invariant systems on solvable Lie groups

Keywords: controllability, right-invariant system, Lie group

Controllability of affine right-invariant systems on solvable Lie groups

Yuri L.

Introduction

First we recall definitions and state our problem.

Let G be a real connected Lie group, L be its Lie algebra (i.e. the set of all right-invariant vector fields on G). For any A; B 1 ;:::;B m 2Lwe consider the corresponding affine right-invariant system =fA+ m X i=1 u i B i j8iu i 2Rg

The attainable set A for the system is a subsemigroup of G generated by one-parameter semigroups f exp(tX) j X 2 ;t0gThe system is called controllable if A = G.

We seek conditions which characterize controllability of the system in terms of the Lie group G,Lie algebra L and vector fields A, B 1 , ..., B m . Invariant control systems on Lie groups were first considered in 1972 by Brockett [START_REF] Brockett | System theory on group manifolds and coset spaces[END_REF] and Jurdjevic and Sussmann [START_REF] Jurdjevic | Control Systems on Lie Groups[END_REF] for the following reasons: Some mechanical systems evolve naturally on Lie groups, e.g. the group SO(3) is a state space for a rigid body rotating around its centre of mass.

y The author thanks Professor Gérard Jacob and the organizers of the workshop 'Lie Computations' for financial support to enable participation in the workshop. This work was partially supported by the Russian Foundation for Fundamental Research, projects No. 96-01-00805 and No. 97-1-1a/22. The author is a recipient of the Russian State Scientific Stipend for 1997.

1365-8050 c 1997 Chapman & Hall

Invariant systems generate control systems on the homogeneous spaces of Lie groups. If is an invariant system on a Lie group G, G=H is a homogeneous space of G,and : G ! G=H is a natural projection, then we can define ( ) -a control system on G=H which is a projection of . It is well known that controllability of on G implies controllability of ( ) on G=H.

For example, if G GL(n) is a Lie group acting transitively on R n nf 0g, then we can take G=H = R n nf0g,and ( ) is a bilinear system

_ x = Ax + m X i=1 u i B i x; u i 2 R;x2R n nf0g
The structure of this paper is as follows. In Sect. 2 we recall some known results about invariant systems on Lie groups. In Sect. 3 we give a controllability test for the hypersurface invariant systems. And in Sects. 4 and 5 we present and discuss controllability results for invariant systems on solvable Lie groups. The complete proofs of the theorems of Sects. 3-5 are given elsewhere [START_REF] Sachkov | Controllability of hypersurface and solvable invariant sstems[END_REF][START_REF] Sachkov | Controllability of right-invariant systems on solvable Lie groups[END_REF].

Known Results

Rank Condition

The basic properties of attainable sets for invariant systems were studied by Jurdjevic and Sussmann [START_REF] Jurdjevic | Control Systems on Lie Groups[END_REF].

Here we recall some of them.

The system is said to satisfy the rank controllability condition if the Lie algebra generated by the system coincides with L: Lie ( ) = Lie (A; B 1 ;:::;B m )=L

The important role of this condition is established by the following theorem.

Theorem 2.1 (Theorem 7.1 [START_REF] Jurdjevic | Control Systems on Lie Groups[END_REF]) The rank controllability condition is necessary for controllability of .

If G is compact or if is homogeneous (i.e. A =0), this condition is also sufficient.

Unfortunately, in the general case the rank condition is not sufficient for controllability, and substantial work was performed to obtain controllability conditions for invariant systems on various particular classes of Lie groups.

Lie Saturation

In 1981, Jurdjevic and Kupka [START_REF] Jurdjevic | Control systems on semi-simple Lie groups and their homogeneous spaces[END_REF] proposed an efficient method of investigation of controllability, and applied it to invariant systems on simple and semi-simple Lie groups. This method is based on the technique of Lie saturation, which may be stated as follows. Given an invariant system , there is defined a new system LS( ) called Lie saturation of : LS( ) = Lie ( ) \fX 2Ljexp(tX) 2 A 8t 0 g A sufficient controllability condition in terms of Lie saturation was given:

Theorem 2.2 (Proposition 6 [5]) If LS( ) = L,then is controllable.
There is no algorithm to construct LS( ), but several nice properties are established which make it possible to extend and construct a chain of lower estimates of LS( ):

1 ::: N :::LS( ) L These properties are as follows (Proposition 5 [START_REF] Jurdjevic | Control systems on semi-simple Lie groups and their homogeneous spaces[END_REF]):

LS( ) is a convex closed cone in L; if X, Y 2 LS( ),then[X; Y ] 2 LS( ); if X, Y 2 LS( ),thenexp(s ad X)Y 2 LS( ) for all s 2 R; if X 2 LS(
) and one-parameter subgroup fexp(tX) j t 2 Rg is periodic, then X 2 LS( ).

Thus, if we manage to construct an extension N of the system such that N = L, then we can conclude that LS( ) = L,and is controllable.

Extensive controllability conditions for invariant systems on simple and semi-simple Lie groups were obtained with the help of the Lie saturation technique by Jurdjevic and Kupka [START_REF] Jurdjevic | Control systems on semi-simple Lie groups and their homogeneous spaces[END_REF], and in subsequent papers by Gauthier and Bornard [START_REF] Gauthier | Contrôlabilité des systèmes bilinèaires[END_REF], Gauthier et al. [START_REF] Gauthier | Controllability of right-invariant systems on real simple Lie groups[END_REF] and Assoudi and Gauthier [START_REF] El Assoudi | Controllability of right-invariant systems on real simple Lie groups of type F 4 , G 2 , C n ,andB n[END_REF][START_REF] El Assoudi | Controllability of right-invariant systems on semi-simple Lie groups[END_REF].

Systems on Nilpotent Groups

There were almost no results on invariant systems on Lie groups different from simple and semi-simple groups. One of the possible reasons is that there is little known about the structure of Lie algebras except for simple and semi-simple algebras.

Ayala and Vergara [START_REF] Ayala | Co-adjoint representation and controllability[END_REF] introduced the notion of a symplectic vector, and gave a necessary controllability condition in terms of this notion. Ayala Bravo [START_REF] Ayala Bravo | Controllability of nilpotent systems[END_REF] applied this condition and obtained a complete characterization of controllability for affine systems on nilpotent simply connected Lie groups: Theorem 2.3 (Theorem 3.6 [START_REF] Ayala Bravo | Controllability of nilpotent systems[END_REF]) Let G be a nilpotent simply connected Lie group. Then the system is controllable iff Lie (B 1 ;:::;B m )=L.

Hypersurface Systems

The main aim of this paper is to study invariant systems on solvable Lie groups. However, we first consider a particular class of invariant systems -hypersurface systems. Controllability conditions for this class are given in Theorem 3.1; they are important in themselves, and will be applied to obtain necessary controllability conditions for systems on solvable Lie groups (Corollary 3.1). A nonlinear control system on a smooth manifold M :

_ x=A(x)+ m X i=1 u i B i (x);u i 2R ;x2M is called a hypersurface if we have dimLie (B 1 ;:::;B m )(x) = dimM 1 8x 2 M
Roughly speaking, hypersurface systems have (n 1) independent inputs and n-dimensional state space.

Such systems received a substantial attention (see, for example, Bacciotti and Stefani [START_REF] Bacciotti | On the relationship between global and local controllability[END_REF], Hunt [START_REF] Hunt | Global controllability of nonlinear systems in two dimensions[END_REF][START_REF] Hunt | n-Dimensional controllability with n 1 controls[END_REF] and Basto Goncalves [START_REF] Basto Goncalves | Controllability in codimension one[END_REF]). The main idea is that for a hypersurface system the state space M is stratified into codimension one foliation by the maximum integral manifolds of the distribution Lie (B 1 ;:::;B m )(x). Now let us consider a hypersurface invariant system , i.e. we suppose that the Lie algebra L 0 = Lie (B 1 ;:::;B m )is a codimension one subalgebra of L. Denote by G 0 the connected Lie subgroup of G corresponding to L 0 . It follows from the right-invariance of the fields A(x) and B 1 (x);:::;B m (x) that the field A(x) does not intersect G 0 in both directions. This idea makes it possible to obtain a controllability test for hypersurface invariant systems:

Theorem 3.1 Suppose that dimL 0 = dimL 1. 1. If G 0 is closed in G,then is controllable iff A= 2L 0 and G=G 0 = S 1 . 2. If G 0 is not closed in G,then is controllable iff A= 2L 0 .
Remark. This theorem generalizes an analogous result obtained by Ayala Bravo [START_REF] Ayala Bravo | Controllability of nilpotent systems[END_REF] under the additional assumption that L 0 is an ideal of L (Proposition 3.3 [START_REF] Ayala Bravo | Controllability of nilpotent systems[END_REF]).

It easily follows from the above theorem that hypersurface systems cannot be controllable on simply connected Lie groups. The reason is that a simply connected Lie group is separated into two disjoint components by the codimension one layer G 0 . If we take any invariant system on a simply connected Lie group and manage to extend it to a hypersurface system 1 ,then is not controllable. Corollary 3.1 Let G be simply connected. Suppose that there exists a codimension one subalgebra of L containing L 0 . Then the system is not controllable.

The idea of search for a hypersurface extension is a key one in the subsequent necessary conditions for systems on solvable simply connected Lie groups.

Completely Solvable Lie Groups

First we consider invariant systems on a subclass of solvable Lie groups appropriate for generalization of the test of Ayala Bravo [START_REF] Ayala Bravo | Controllability of nilpotent systems[END_REF] for nilpotent groups (Theorem 2.3). The sense of this test is that the drift term A cannot help to control the system =fA+ P m i=1 u i B i g, i.e. the system is controllable if and only if the system without drift term 0 = f P m i=1 u i B i g controllable. The 'if' part is obvious: we can take sufficiently great u i for the system and move almost along the trajectories of the system 0 .S othe nontrivial part of the proof is the 'only if' part.

A (real) Lie algebra L is called completely solvable if for any X 2 L the adjoint operator ad X : L ! L has only real eigenvalues. Any completely solvable Lie algebra is solvable. A Lie group with completely solvable Lie algebra is called completely solvable. The main idea of the proof of this theorem is that in a completely solvable Lie algebra L any proper subalgebra can be extended to a codimension one subalgebra of L. Hence, any affine system can be extended to a hypersurface system (which is noncontrollable by Corollary 3.1).

Example 1. Let T (n) denote the Lie group of n n triangular matrices with positive diagonal entries. T (n) is connected, simply connected, and completely solvable. So Theorem 4.1 applies to invariant systems on T (n) or any connected subgroups of T (n).

Remark. Consider the following increasing of classes of Lie groups:

Commutative Nilpotent Completely solvable Solvable Suppose that Lie group G is connected and simply connected. It is obvious that the property (*) is satisfied for commutative G. Theorem 2.3 establishes that (*) holds for nilpotent G, and Theorem 4.1 states that (*) is true for completely solvable G. The results of the following section (in particular, Example 2) imply that (*) is not valid for general solvable G.

General Solvable Lie Groups

Now we restrict ourselves by the single-input systems =fA+uB j u 2 Rg as the case of general solvable Lie groups is much more complicated. It turns out that there exist strong necessary conditions for the system to be controllable on solvable simply connected Lie groups (see Theorem 5.1 below). And if these necessary conditions are satisfied, there exist generic sufficient conditions which guarantee controllability (Theorem 5.2).

Notation

To state the controllability results precisely we need some notation. Derived subalgebra and the second derived subalgebra:

Necessary Conditions

The necessary controllability conditions are obtained with the help of Corollary 3.1. Solvable Lie algebras possess a great number of codimension one subalgebras, and it is often possible to extend the system to a hypersurface system and show noncontrollability of .

Theorem 5.1 Suppose that G is solvable and simply connected. Let the spectrum Sp1 be simple. If is controllable, then:

1. dimL 1 = dimL 1;

2. B= 2L 1 ;

3. Sp 2 \ R= Sp 1 \ R.

Sufficient Conditions

We obtain sufficient controllabilty conditions with the help of the Lie saturation technique. To show that LS( ) = L we consider the eigenvectors of the operator ad Bj L 1 and construct a chain of these eigenvectors which generate L 1 step-by-step. Theorem 5.2 Suppose that G is solvable. Let the spectrum Sp 1 be simple and all necessary conditions of Theorem 5.1 be satisfied. Suppose also that:

1. vector A has nonzero components in all eigenspaces of ad Bj L 1 ;

2. Sp 1 fRez>0gor Sp 1 fRez<0gor Sp 1 \ R= ;.

Then the system is controllable. where C is the rotation matrix and b is the translation vector. The corresponding matrix Lie algebra L is spanned by the matrices A 1 = E 13 , A 2 = E 23 and A 3 = E 21 E 12 .W eh a v eL 1 = span(A 1 ;A 2 )and L 2 = f0g; therefore, L is solvable.

Consider the system =fA+uB j u 2 Rg on Ẽ(2) -the simply connected covering of E(2).A complete characterization of controllability of on Ẽ(2) with the help of the above results: Proposition 5. [START_REF] Brockett | System theory on group manifolds and coset spaces[END_REF] The system is controllable on Ẽ(2) if and only if vectors A, B are linearly independent and B= 2span(A 1 ;A 2 ).

Really, if B 2 span(A 1 ;A 2 ), then the system can be extended to a hypersurface system B= 2span(A 1 ;A 2 ) and vectors A, B are linearly independent, then all conditions of Theorem 5.2 are satisfied, hence is controllable on Ẽ(2).

It would be interesting to compare controllability conditions for Ẽ(2) with the following conditions for E(2) (these conditions are easily obtained with the help of the controllability test given in Theorem 1 [START_REF] Bonnard | Transitivity of families of invariant vector fields on semi-direct products of Lie groups[END_REF]):

Proposition 5. [START_REF] Jurdjevic | Control Systems on Lie Groups[END_REF] The system is controllable on E(2) if and only if vectors A, B are linearly independent and span(A; B) 6 span(A 1 ;A 2 ).

Final Remarks

In addition to the papers cited in this paper, there are very interesting results controllability of invariant systems on nilpotent and solvable Lie groups obtained via Lie semigroups methods by Hilgert et al. [START_REF] Hilgert | Controllability of systems on a nilpotent Lie group[END_REF] and Lawson [18]. These results cover general systems, but for affine ones they do not imply the detailed theory presented in this work. Recently, the author applied this theory to obtain a classification of controllable systems on small-dimensional simply connected solvable Lie groups [START_REF] Sachkov | Controllability of right-invariant systems on solvable Lie groups: A survey and some new results[END_REF][START_REF] Sachkov | Classification of controllability in small-dimensional solvable Lie algebras[END_REF].

Theorem 4 . 1

 41 Suppose that G is completely solvable and simply connected. Then is controllable on G iff Lie (B 1 ;:::;B m )=L ()

L 1 =

 1 [L; L]; L 2 =[L 1 ;L 1 ] Complexifications of L, L 1 ,andL 2 : L c = L C ; L 1 c = L 1 C ; L 2 c = L 2 C Adjoint representations: ad : L ! End (L); ad c : L c ! End (L c ) Spectrum of ad B in L 1 : Sp 1 = f a 2 C j Ker (ad c Bj L 1 c aId ) 6 = f0gg Spectrum of ad B in L 2 : Sp 2 = f a 2 C j Ker (ad c Bj L

Example 2 .

 2 Let G = E(2) be the Euclidean group of motions of R 2 .E (2) is connected but not simply connected. It can be represented as a group of 3 3 matrices of the form

= f A + v 1 A 1 + v

A 2 j v 1 ;v 2 2Rg so is noncontrollable by Corollary

3.1. If the vectors A and B are linearly dependent, then Lie (A; B) 6 = L, the rank controllability condition is violated, and is noncontrollable by Theorem 2.1. Finally, if