% Copyright (c) 1991 Marcel Roelofs, University of Twente, Enschede, % The Netherlands. % % $Header: liesuper.web,v 1.5 92/02/26 14:22:25 roelofs Exp $ % \input specification \def\Version$#1Revision: #2 ${Version #2} \def\title{LIESUPER} \font\titlefont=cmcsc10 scaled\magstep3 \font\ttitlefont=cmtt10 scaled\magstep4 \def\topofcontents{\null\vfill \centerline{\titlefont The {\ttitlefont LIESUPER} package for REDUCE} \vskip15pt\centerline{\Version$Revision: 1.5 $} \vskip15pt\centerline{\sc Marcel Roelofs}\vfill} \def\concl{\bigskip\narrower\narrower\narrower\noindent {\bf SPECIFICATIONS}:\hskip1em\ignorespaces} \def\endconcl{\par\leftskip=0pt\rightskip=0pt\noindent\ignorespaces} \def\enditem{\medskip\noindent\ignorespaces} \def\lie{{\it lie}} \def\newpage{\vfill\eject} @*= Introduction. In this \.{WEB} file we will describe a REDUCE package for symbolic computations in (free) Lie (super)algebras. For this purpose we will introduce a new rtype liebracket, which satisfies the bilinearity and the (graded) skew-symmetry of the liebracket. Moreover, we will implement a mechanism to check the (graded) Jacobi identity and add sufficient bells and whistles to facilitate the usage of various kinds of gradings. Although we call it a rtype there is a difference with the usual rtypes in REDUCE like arrays or matrices. Elements of an array or a matrix can be accessed through a get-element-function and always have a value (which can be and actually is simplified before returning it). Elements of a liebracket, however, need not always have a value, in which case the element itself should be returned in a canonical form (in this way it resembles the REDUCE operator |df|). Hence access to elements of a liebracket must necessarily be through a simplification function, in order to avoid infinite loops on simplification. On the other hand a liebracket isn't an algebraic operator in the usual sense either, because we don't want to use the standard mechanism for storing elements of algebraic operators, since this generates a linear list containing all values, which is too time consuming if a large number of values have to be stored. Instead we will use a vector structure which is better suited to the structure of a liebracket. Therefore we are enforced to use a set-element-function to assign values to elements of a liebracket. The only way to accomplish this is to define liebracket to be a rtype. Another bottleneck for operators with a large number of used elements is the use of the so called klist. On this list all operator elements are stored which at least have occured once in an algebraic expression. Therefore we shall extend some standard REDUCE procedures which take care of or use the klist mechanism, in such a way that for liebrackets the klist is replaced by an additional field in the vector structure. It is well known that commutators are normally represented by a pair of square brackets $[\,\ldotp\,,\,\ldotp\,]$ in mathematics. Since we explicitly want to allow more liebrackets at a time, it is impossible for us to denote all commutators in this notation. We will, however, facilitate the use of square brackets for a specific liebracket, which can be used in all cases where one only needs to work with one liebracket. \medskip The ``banner line'' defined here is intended for indentification purposes on loading. It should be changed whenever this file is modified. System dependent changes, however, should be made in a separate change file. @d banner="Lie (super)algebra package for REDUCE 3.4, $Revision: 1.5 $" @ We define the following macros for clarity. @d change_to_symbolic_mode =symbolic @d change_to_algebraic_mode =algebraic @d stop_with_error(string_1,expr_1,string_2,expr_2) = @/ msgpri(string_1,expr_1,string_2,expr_2,t) @; @d message(string_1,expr_1,string_2,expr_2) = @/ msgpri(string_1,expr_1,string_2,expr_2,nil) @; @d operator_name_of=car @d arguments_of=cdr @d first_argument_of=cadr @d second_argument_of=caddr @d first_element_of=car @d second_element_of=cadr @d rest_of=cdr @d skip_list=cdr %Skip the |'list| in front of an algebraic list% @d independent_part_of=cadr %For use with lists returned by |operator_coeff|% @d kernel_coeff_list_of=cddr %For use with lists returned by |operator_coeff|% @d kernel_of=cadr %For use with a kernel-coefficient list% @d coefficient_of=caddr %For use with a kernel-coefficient list% @ The following macros are intended as common programming idioms. @d incr(x) = (x:=x+1)@; @d decr(x) = (x:=x-1)@; @ A new REDUCE switch can be introduced using the following code. @d initialize_global(global_name,value)=@/ global '(global_name)$@/ global_name:=value @d new_switch(switch_name,value)=@/ initialize_global(!* @& switch_name,value)$@/ flag('(switch_name),'switch) @ We do all initializations in the beginning of the package. @u change_to_symbolic_mode$@/ write banner$terpri()$@/ @$ @@/ change_to_algebraic_mode$ @ For a proper function of some procedures of this \.{WEB} file we need a number of procedures from the TOOLS package. Therefore we will check if the TOOLS package has already been loaded. We do this by verifying that |operator_coeff| is defined as function. @= if not getd 'operator_coeff then message("LIESUPER_INIT: load the TOOLS package before continuing",nil,nil,nil) @; @*= Implementing free Lie superalgebras. For $m,n\geq 0$ let ${\sl Lib}={\sl Lib}(x_1,\dots,x_m,\xi_1,\dots,\xi_n)$ be the free algebra on generators $x_1,\dots,x_m,\xi_1,\dots,\xi_n$. We introduce a {\bf Z}$_2$-grading $\vert\,\ldotp\vert$ on {\sl Lib\/} by defining $\vert x_i\vert=0$ $(i=1,\dots,m)$, $\vert \xi_j\vert=1$ $(j=1,\dots,n)$ and $\vert xy\vert=\vert x\vert+\vert y\vert$ for all homogeneous $x,y\in {\sl Lib}$. We define $L=L(x_1,\dots,x_m,\xi_1,\dots,\xi_n)$ to be the quotient algebra ${\sl Lib}/I$ where $I$ is the ideal, which for all homogeneous $x,y,z\in {\sl Lib}$ is generated by the elements $xy+(-1)^{\vert x\vert \cdot\vert y\vert}yx$ and $(-1)^{\vert x\vert\cdot\vert z\vert }x(yz)+ (-1)^{\vert y\vert \cdot\vert x\vert}y(zx)+ (-1)^{\vert z\vert \cdot\vert y\vert }z(xy)$. On $L$ we define a bracket $[x,y]\equiv xy$. Then from the definition above it is clear that this bracket satisfies the graded skew-symmetry $$[x,y]=-(-1)^{\vert x\vert \cdot\vert y\vert}[y,x]$$ and the graded Jacobi identity $$(-1)^{\vert x\vert\cdot\vert z\vert }[x,[y,z]]+ (-1)^{\vert y\vert \cdot\vert x\vert}[y,[z,x]]+ (-1)^{\vert z\vert \cdot\vert y\vert }[z,[x,y]]=0.$$ Moreover it is bilinear because of the bilinearity of the multiplication in {\sl Lib}. Therefore $L$ defines a Lie superalgebra, the so called {\it free Lie superalgebra\/} on even generators $x_1,\dots,x_m$ and odd generators $\xi_1,\dots,\xi_n$. It is obvious that for $m>1$ or $n>1$ $L$ is infinite dimensional. From this free Lie superalgebra we can get some specific Lie (super)algebra by imposing additional relations on top of the graded skew-symmetry and the graded Jacobi identity. For instance, we can get a finite dimensional simple Lie algebra by imposing appropriate Serre relations. As a last point we have to mention gradings of Lie (super)algebras, because these can be very helpful when working on Lie (super)algebras. A Lie (super)algebra can admit more than one grading, for example, the free Lie (super)algebra on $n$ generators admits a {\bf Z}$_2$-grading, but also admits the length of ``words'' as a grading, or a multigrading where the degree of $x_i$ is the $n$-tuple $(0,\dots,1,\dots,0)$ (1 on the $i$-th place). \bigskip There is one fact about free Lie superalgebras which is very useful if we want to implement a free Lie superalgebra in REDUCE. To explain this, let $L_1=L(x_1,\dots,x_n)$ be the free Lie superalgebra on generators $x_1,\dots,x_n$ for some $n>1$. Then it is easy to prove that $L_1$ is isomorphic to $L_2=L(x_1,\dots,x_{n+1})/I(x_{n+1}-[x_1,x_2])$ where $I(x_{n+1}-[x_1,x_2])$ is the ideal in $L_2$ generated by $x_{n+1}-[x_1,x_2]$. This means that we can avoid expressions containing commutators like $[x_1,x_2]$ just by introducing a new generator $x_{n+1}$ and imposing one additional relation $[x_1,x_2]=x_{n+1}$. \newpage @ In the sections that follow we will take some decisions about how we are planning to introduce a structure in REDUCE suitable to deal with free Lie superalgebras. From what we have said in the previous section it is clear that the following points have to be taken into account:\medskip \item{1.} the bilinearity of the bracket. \item{2.} the graded skew-symmetry of the bracket. \item{3.} the number of generators and the possibility to introduce new generators as new names for unknown commutators. \item{4.} the Jacobi identity. \item{5.} the ability to use various kinds of gradings. @*2 Representation of Lie algebras. The first point we have to take care of is how to represent commutators and generators in REDUCE. Generators we want to represent by an algebraic operator. For example, we could represent $x_i$ by an operator $x(i)$. We should, however, be able to discriminate between even and odd generators. There are a few solutions to this problem:\medskip \item{1.} use different operators for even and odd generators. \item{2.} for each generator keep record of its grade. \item{3.} use different ranges for even and odd generators. For instance, use $x(i)$ with $i>0$ for even generators and $x(i)$ with $i<0$ for odd generators. \enditem We have chosen the third solution, since it seems the most practical one. Namely, it offers a very easy way to test whether a generator is odd or even. @ Commutators can simply be represented by an algebraic operator with two arguments. If we use, for example, the operator \lie\ for commutators and $x$ for generators, $[x_i,x_j]$ will be represented by $\lie(x(i),x(j))$. For this kind of expression, however, it seems useful to introduce a shorthand notation $\lie(i,j)$, since these expressions will be playing a very important role. We have found: \concl To each liebracket we assign two algebraic operators to represent the commutators and the generators, respectively. If $x$ is the operator assigned to some liebracket as generator, the elements $x(i)$ for $i<0$ represent the odd generators of the Lie superalgebra, the elements $x(i)$ for $i>0$ represent the even generators. Commutators are represented by an algebraic operator with two arguments. If \lie\ is this operator, $\lie(i,j)$ with $i$ and $j$ integer will be a shorthand notation for $\lie(x(i),x(j))$. \bigskip \endconcl If in the sequel we want to explain things about liebrackets by giving an example, we will always use the pair |@!lie|, |@!x| to represent the commutators and generators, respectively. @ We have seen that we are allowed to set an unknown commutator $\lie(i,j)$ equal to $x(p)$ for some new generator $x(p)$ and still keep the same algebra (up to isomorphism). Hence in ordinary cases we need not assign values to expressions like $\lie(\lie(i,j),q)$, because with the above substitution for $\lie(i,j)$ it can be simplified to $\lie(p,q)$. It seems like a good idea to adopt the introduction of new generators for unknown commutators as a very useful strategy, because it prevents nested commutators to be represented in REDUCE by very lengthy and deeply nested expressions. This may become very important for it takes significantly more time to simplify deeply nested expressions than simple expressions like $\lie(i,j)$ with $i$ and $j$ integer. Moreover, the points raised above make the following simplifications possible:\medskip \item{1.} Using the bilinearity we see that $\lie(10*x(1),x(2)+x(3))$ is equal to $10*\lie(1,2)+10*\lie(1,3)$. This means that there is no need to store commutators of linear combinations of generators. \item{2.} From the graded skew-symmetry we see that $\lie(j,i)$ is equal to $-\lie(i,j)$ if $\vert x_i\vert\cdot\vert x_j\vert=0$ and equal to $\lie(i,j)$ otherwise. So our first observation is that there must be a mechanism to store values of $\lie(i,j)$ for $j\geq i$. \enditem Although most Lie (super)algebras under consideration will be infinite dimensional, it will only be possible to compute a finite dimensional part of it by computer. Following our strategy of introducing new generators for unknown commutors, this boils down to the fact that we can only compute finitely many commutators of two generators. So it's no real restriction to impose upperbounds on the number of generators beforehand. For practical problems, however, these upperbounds may still be rather big, let's say 100 odd and 100 even generators. In principle all commutators of these generators may get a value, but if we assume that only a quarter of all commutators is known, in our example with 200 generators this still means that about 5000 values have to be stored. This already indicates that it isn't a good idea to store the values of commutators of generators on the standard REDUCE kvalue list, which is an association list. Access to an association list is by comparing the |car| of all its elements with the wanted expression until both are equal. Hence it will take more and more time to access an element of an association list as it grows. For practical problems like the example above, access to an association list will already be too time consuming. Therefore we will choose to store values of commutators of generators in a vector structure, a lisp object which is more directly accessible. Because a vector is a static object, we need the upperbounds on the number of generators right at this place. Resuming we have found: \concl We impose upperbounds on the number of even and odd generators (these upperbounds should include the number of generators which we want to introduce as new names for unknown commutators). If these upperbounds are $m$ and $n$, respectively, we store the values of $\lie(i,j)$ for $-n\leq i\leq j\leq m$ in a vector structure. \endconcl @ For some applications we sometimes need to allow more general expressions as element of a Lie (super)algebra than just the generators. For instance, this is the case if we want to do computations in (super)prolongation theory, where we are working with Lie (super)algebra valued functions. Nevertheless we should be able to assign values to commutators containing such expressions or to commutators containing nested commutators, to which we don't want or cannot assign a value, for whatever reason. But this means that we can't just do with the vector structure, because these ``irregular'' commutators don't fit into it. The most appropriate way to store such kind of commutators is to use the standard REDUCE kvalue list. However, we have to impose some restrictions on the kind expressions which we allow to act as algebra elements. We should, for instance, be able to recognize it as an algebra element. In view of the way we will decompose a commutator into its smallest components later on, the first restriction must be that we can only allow operator expressions to act as algebra elements. Therefore the easiest way to allow for more general algebra elements is to add to a liebracket a list of operatornames, elements of which are regarded to be elements of that Lie (super)algebra. There is one more restriction we have to impose, namely for each algebra element we want to know if it is odd or even (nonhomogenous elements we can split up into an odd and an even part). The reason that we want to know this will become clear in the following section. This can also be achieved very easily: if $f(a_1,\dots)$ is some general algebra element, not being a commutator or a generator, we demand its first argument $a_1$ to be a positive or negative integer, indicating if the algebra element is even or odd, respectively. \concl To each liebracket we add a list of operators, elements of which will be regarded to be elements of the Lie (super)algebra. The first argument of such an element should be a positive or negative integer, indicating if it is an even or even algebra element. The values of commutators containing algebra elements, which are not generators, will be stored on the standard REDUCE kvalue list. \endconcl @ Now we know how all possible algebra elements look like, we want to have a canonical representation of all commutators. In this way REDUCE will always correctly recognize sums of commutators to be zero, which otherwise might possibly have slipped through because of the bilinearity or the skew-symmetry of the bracket. To get a commutator in canonical representation we apply the following rules:\medskip \item{1.} decompose the commutator into its smallest components using the bilinearity of the bracket. \item{2.} commutators $\lie(x(i),f(a_1,\dots))$, where $f$ is some operator allowed as algebra element (including generators and nested commutators), are represented by its shorthand notation $\lie(i,f(a_1,\dots))$. The same applies to the second argument. \item{3.} if one of the arguments is 0, the commutator is 0. This follows directly from the bilinearity. From this we see the necessity not to allow $x(0)$ as a generator, because its shorthand notation in a commutator would be 0 and all commutators with $x(0)$ would become 0 applying the rule stated above. \item{4.} using the standard REDUCE procedure |ordp(x,y)|, the arguments $x$ and $y$ of $\lie(x,y)$ are orderded canonically. If we have to switch $x$ and $y$ the result is provided with a minus sign if not both $x$ and $y$ are odd algebra elements. This actually is the reason, why for every algebra element we need to know if it is odd or even. @*1 Jacobi identities. The Jacobi identity expresses the fact that not all commutators are linear independent. To explain this, we look at the Jacobi identity for $x(1)$, $x(2)$ and $x(3)$. It reads $\lie(1,\lie(2,3))-\lie(2,\lie(1,3))+\lie(3,\lie(1,2))=0$, where we have used graded skew-symmetry to get the second term. Further suppose that we have introduced new generators $\lie(1,2)=x(4)$, $\lie(1,3)=x(5)$ and $\lie(2,3)=x(6)$, then this Jacobi identity implies that $\lie(1,6)-\lie(2,5)+\lie(3,4)=0$. But this is nothing else than to say that $\lie(1,6)$, $\lie(2,5)$ and $\lie(3,4)$ are linear dependent. If, moreover, $\lie(1,6)$, $\lie(2,5)$ and $\lie(3,4)$ all are a sum of generators, the Jacobi identity might either be zero or otherwise lead to a linear dependency for some generators of the Lie (super)algebra. It is clear that for each triple of algebra elements the Jacobi identity is either zero or leads to a relation between algebra elements and/or commutators of algebra elements. If we have $N$ linear independent and homogeneous (w.r.t.\ the {\bf Z}$_2$ grading) algebra elements (generators as well as the more general operator expressions allowed as algebra element), the number of Jacobi identities amounts to $N\choose 3$ if all algebra elements are even, and slightly more if some of the elements are odd. Hence we conclude that the number of Jacobi identities grows very fast for increasing $N$. Just if only a small part of the Jacobi identities would lead to new relations this still means that quite a lot of values would have to be stored. If we were to store these values on the kvalue list of the operator representing the commutator, we would be facing an increasing access time for that kvalue list very soon. This indicates that it is only useful to compute and solve those Jacobi identities which don't lead to storing of values on the kvalue list of the commutator. Therefore we should only check those Jacobi identities that (eventually) lead to new relations for commutators of two generators (since these are stored in a vector structure) or to relations between some generators (since this kind of relation cannot be avoided). Hence the first remark that can be made, is that we only have to check Jacobi identities for triples of generators $x(i)$, $x(j)$ and $x(k)$, since these are the only ones to lead without too much difficulty to the desired kind of relation. Furthermore, if we want to satisfy the condition stated above, it is easy to see that all three commutators $\lie(i,j)$, $\lie(j,k)$ and $\lie(i,k)$ are to be entirely expressed in terms of some other generators. Therefore we have found: \concl There must be a mechanism to compute and solve the Jacobi identities for all triples of generators $x(i)$, $x(j)$ and $x(k)$ which satisfy the condition that all three commutators $\lie(i,j)$, $\lie(j,k)$ and $\lie(i,k)$ are a linear combination of generators. \bigskip \endconcl It is well known that one can give a basis of a free Lie (super)algebra seen as a linear space, the so called Hall basis. Consequently, this Hall basis respects the linear dependencies caused by the Jacobi identity and the graded skew-symmetry. Now suppose that we start off with a free Lie (super)algebra on $n$ generators, i.e., a Lie (super)algebra without any additional relations, and suppose that we want to compute a basis of this algebra as a linear space in REDUCE. It is not difficult to see that we can construct this basis upto ``words'' of a certain length $L$ by executing a cycle of introducing new generators for still unknown commutators of length $l$ and trying to solve Jacobi identities for $l=2,\dots,L$. The result in each step of solving the Jacobi identities is that all linear dependencies for commutators of length $l+1$ are found and solved. Hence in the step for $l+1$ only the remaining independent commutators will be renamed. From this we see that solving Jacobi identities the way we are planning to, is a means to get a minimal set of generators of a Lie (super)algebra up to a certain length. @*2 Gradings. The next point we should say something about are gradings. As we have already seen, a Lie (super)algebra can have more than one grading. However, all gradings together constitute a multigrading. Although not all gradings adopt integer values (for example the grading belonging to the root space decomposition of Kac-Moody algebras), we can, at least for finitely generated algebras, represent them by an appropriate multigrading with integer values. If for each generator we store its multigrade, we can retrieve the grade of every commutator (of two generators), since it is the sum of the grades of its arguments. \concl There must be a mechanism to store and retrieve integer valued multigrades of every generator of the Lie (super)algebra. With help of these the multigrade of every commutator can be determined. \endconcl @ Then finally, we want to introduce a shorthand notation to be able to input nested commutators more easily, which can be very useful when actually working on Lie (super)algebras. For this suppose, for example, that we want to compute the commutator $[[x_1,x_2],[x_2,[x_3,x_4]]]$. Using the rules described above, it can be represented by the expression $\lie(\lie(1,2),\lie(2,\lie(3,4)))$ in REDUCE. This is a rather lengthy expression and, moreover, it doesn't express the structure of the commutator very clearly. If we denote the bracket by a $\cdot$, the above commutator reads $(x_1\cdot x_2)\cdot(x_2\cdot(x_3\cdot x_4))$ or $(x_1\cdot x_2)\cdot x_2\cdot x_3\cdot x_4$, if we define $\cdot$ to be right associative (by this we mean that $x_1\cdot x_2\cdot x_3\equiv x_1\cdot(x_2\cdot x_3)$). In our opinion this is the most simple and easy to understand expression representing the above commutator, and we want to introduce a counterpart of this representation in REDUCE. Therefore, let for $N\geq 3$ the expression $\lie(x_1,\dots,x_N)$ be a shorthand notation for $\lie(x_1,\lie(x_2,\dots,\lie(x_{N-1},x_N)\dots))$, where $x_1,\dots,x_N$ are algebra elements. Moreover, to avoid lengthy expressions, we will allow (algebraic) list expression as nested commutators. With these simplifications the above commutator may be represented by the REDUCE expression $\lie(\{1,2\},2,3,4)$. Of course, if one is working with the ``default'' liebracket which may be represented by square brackets (mentioned in the introduction), it may also be represented by $[[1,2],2,3,4]$ or even by $[\{1,2\},2,3,4]$. \concl For $N\geq 3$ the expression $\lie(x_1,\dots,x_N)$ is defined to be a shorthand notation for $\lie(x_1,\lie(x_2,\dots,\lie(x_{N-1},x_N)\dots))$, where $x_1,\dots,x_N$ are algebra elements. Algebraic list expressions are allowed as nested commutators. \endconcl @*= Simplification of commutators. In the introduction we have already explained that the requirements stated above, force us to use a simplification function to retrieve values of commutators. We have gathered enough material now to outline this simplification function. It should be noted that the procedure |simp_liebracket| expects the |car| of its argument to be the name of the liebracket. To achieve this, the liebracket under consideration must be flagged |full|. A simplification function, hence also the procedure |simp_liebracket|, should return the value of its argument as a standard quotient. @u lisp procedure simp_liebracket val; if length val=3 then @ else if length val>3 then @ else rederr("SIMP_LIEBRACKET: wrong number of arguments")$ @ We simplify a commutator as explained in the previous sections. The procedure |simp_liebracket_vector| checks if a commutator with two integer arguments has a value, or otherwise returns it in canonical form. We simplify both arguments before continuing in order to be able to recognize negative integer arguments. It is easily verified that this has almost no influence on the timings. @= begin scalar bracketname,arg1,arg2; bracketname:=operator_name_of val; arg1:=mk!*sq simp!* first_argument_of val; arg2:=mk!*sq simp!* second_argument_of val; return if fixp arg1 and fixp arg2 then simp_liebracket_vector(bracketname,arg1,arg2) else @; end @; @ To decompose a commutator into its smallest components using the bilinearity we will use the procedures of the TOOLS package implemented to deal with operators which are multilinear w.r.t.\ some specified operators. We recall that this implementation consists of a simplification procedure |simp_multilinear| together with a resimplification procedure for the smallest constituent parts of the operator $O$ under consideration, which name is to be found on the property list of $O$ as the property |resimp_fn|. The list of operators w.r.t.\ which $O$ is multilinear has to be stored as the property |oplist|. Hence essentially it suffices to write an appropriate resimplification procedure in our case. There are, however, a few minor points which have to be taken into account. First we allowed sole integers as a shorthand notation for generators. To make |simp_multilinear| work properly we have to undo this simplification temporarily. The name of this generator is stored on the property list of the liebracket as the property |generatorname|. Moreover, we allowed algebraic lists to denote nested commutators. Since algebraic list are represented by the operator |list| internally, this can be dealt with by putting |list| on the |oplist| of a liebracket. @= simp_multilinear list(bracketname, if fixp arg1 and arg1 neq 0 then list(generatorname,arg1) @+else arg1, if fixp arg2 and arg2 neq 0 then list(generatorname,arg2) @+else arg2)@/ where generatorname=get(bracketname,'generatorname) @; @ The resimplification procedure |resimp_liebracket| is rather simple. Each of the arguments can be:\medskip \item{1.} an integer: since the shorthand notation of generators is hidden before simplification, this can only occur if there is an unwanted mixing of the full and the shorthand notation for generators. Hence we must stop with an error message in this case. \item{2.} a generator: we have to strip off the generatorname and represent it by its shorthand notation. \item{3.} an algebraic list representing a nested commutator: we have to replace |list| by the name of the liebracket and simplify the whole commutator again. \item{4.} any other algebra element: nothing special has to be done. \enditem The definition |update_argument| takes care of the necessary actions. The variable |resimplify| indicates the necessity of resimplification due to case 3.\ and should be local to the procedure |resimp_liebracket|. @d update_argument(arg)=@/ if fixp arg then rederr("SIMP_LIEBRACKET: argument contains a non algebra element") else if operator_name_of arg=generatorname then arg:=first_argument_of arg else if operator_name_of arg='list then @/ <> @; @ If both arguments are generators we have to check the vectorstructure for further simplification, otherwise the kvalue list. This is done in the procedures |simp_liebracket_vector| and |simp_liebracket_kvalue|, respectively. @u lisp procedure resimp_liebracket val; begin scalar bracketname,generatorname,arg1,arg2,resimplify; bracketname:=operator_name_of val; generatorname:=get(bracketname,'generatorname); arg1:=first_argument_of val;arg2:=second_argument_of val; update_argument(arg1);update_argument(arg2); return if resimplify then simp_liebracket list(bracketname,arg1,arg2) else if fixp arg1 and fixp arg2 then simp_liebracket_vector(bracketname,arg1,arg2) else simp_liebracket_kvalue(bracketname,arg1,arg2); end$ @ Now we have dealt with ordinary commutators satisfactorily, it's time to aim our attention to the nested commutators. Notice that we have defined an expression like $\lie(\{1,2\},2,3,4)$ to be nothing but the expression $\lie(\lie(1,2),\lie(2,\lie(3,4)))$. Since we have already treated list expressions as part of ordinary commutators, we only have to reverse the list of arguments and compute the commutators repeatedly. @= begin scalar bracketname,arguments,result; bracketname:=operator_name_of val; arguments:=reverse arguments_of val; result:=simp_liebracket list(bracketname,second arguments,first arguments);@/ arguments:=cddr arguments; %Chop first two arguments% for each arg in arguments do result:=simp_liebracket list(bracketname,arg,mk!*sq result); return result; end @; @*= Storing and retrieving values of commutators. In the following sections we will explain how we are planning to store values of commutators exactly. We recall that we have to make a clear distinction between commutators of two generators, in which case we want to store the values in a vector structure, and all other cases, for which we want to store the values on the kvalue list. @ We have seen in one of the previous sections that we have to store $\lie(i,j)$ for $-n\leq i\leq j\leq m$, if $lie$ is a liebracket and $m$ and $n$ the number even and odd generators, respectively. There are a few ways to store the values of these commutators in a vector structure:\medskip \item{1.} put them all together in one vector and supply a procedure to compute the index for a tuple $(i,j)$. \item{2.} make a vector of vectors: put for all $i$ the vectors containing the values of $\lie(i,j)$ for $i\leq j\leq m$ in a vector. \enditem The second alternative has the advantage, that it is rather easy to compute the indices, but we have to access two vectors to get the value of a commutator. For the first alternative the index has a more complex structure, but we have only to access one vector. We have compiled and tested both alternatives in a REDUCE version built on top of Innovus Lisp on a HP9000 series at our site. In this configuration the second alternative has proven to be the fastest. Therefore we will use this one to store the values of commutators of two generators. The indices of a vector of dimension $N$ run from $0,\dots,N$. Hence the dimension of the outer vector structure must be $m+n$, which must have for $-n\leq i\leq m$ as value at index $n+i$ the vector of dimension $m-i$ containing the values of $\lie(i,j)$ for $i\leq j\leq m$. For each $-n\leq i\leq j\leq m$ we can add to the tuple $(i,j)$ a couple of indices $(n+i,m-j)$ for the outer and the inner vector, respectively. Note that we use the inner vector structure in a reverse way to keep the indices as short as possible. @ We will store the vector structure of a liebracket |bracketname| on the property list as the property |vector_structure|. The dimensions $m$ and $n$ of a liebracket are stored on the property list as the properties |even_dimension| and |odd_dimension|, respectively. Access to a vector is through the procedures |getv|, to get a value, and |putv|, to store a value. One should be aware of the fact that |putv| doesn't make a new copy of the vector, but replaces the value at the required index directly in the physical memory. Therefore it is unnecessary to do a |putv| for the outer vector structure when storing a commutator, because a |getv| for the outer vector structure will return a vector, which we can change directly in the physical memory at the right index with a |putv|. There is one point which we haven't explained so far, but which already has to be used here. Namely, to enable the computation of Jacobi identities to be as efficient as possible, it is not enough for each commutator just to store its value, but we have to store some more information. Moreover, as explained in the introduction, we shall also put the information about possible occurences of commutators in the vector structure. For ordinary algebraic operators this kind of information is recorded on the klist. Therefore for each commutator we will store a dotted pair of length 3, the |car| being additional information about the commutator, the |cadr| being the replacement for the klist mechanism, the |cddr| being its value. Although we won't explain the meaning of the two first items right away, it is enough to know here that the additional information must be initialized to |nil|. The part meant as the replacement for the klist mechanism must must be initialized to |nil|, if it is not present, otherwise the old value must be taken. We think that it is convenient to have procedures both to access the entire vector structure as well as just the values of commutators. Access to the vector structure is through the macros |get_vector_structure| and |put_vector_structure|, access to the values of commutators of two generators is through the macros |get_commutator| and |put_commutator|, where the last two simply use the first two. The procedures don't perform range checking on their parameters. @d informative_part_of=car @d k_info_and_commutator_part_of=cdr @d k_info_of=cadr @d commutator_part_of=cddr @d get_vector_structure(bracketname,i,j)=@/ getv(getv(get(bracketname,'vector_structure), get(bracketname,'odd_dimension)+i),@| get(bracketname,'even_dimension)-j) @; @d put_vector_structure(bracketname,i,j,value)=@/ putv(getv(get(bracketname,'vector_structure), get(bracketname,'odd_dimension)+i),@| get(bracketname,'even_dimension)-j,value) @; @d get_commutator(bracketname,i,j)=@/ (if entry then commutator_part_of entry) where entry=get_vector_structure(bracketname,i,j) @; @d put_commutator(bracketname,i,j,value)=@/ (if old_value then put_vector_structure(bracketname,i,j,nil . (k_info_of old_value) . value) else put_vector_structure(bracketname,i,j,nil . nil . value)) where old_value=get_vector_structure(bracketname,i,j) @; @ Before we can write the procedures |simp_liebracket_vector| and |simp_liebracket_kvalue| we have to explain how to get the arguments of a commutator in a canonical order. The macro |not_ordered_commutator| checks whether or not the arguments of a commutator are well ordered. It uses the standard REDUCE procedure |ordp| and is written in such a way that a pair $(i,j)$ for $i$,$j$ integer, $i\leq j$ is well ordered. @d not_ordered_commutator(arg1,arg2)= @/ (if fixp arg1 and fixp arg2 then arg1>arg2 @+else ordp(arg1,arg2) and arg1 neq arg2) @; @ If the two arguments are not well ordered they must be switched. Moreover, if not both arguments are odd a minus sign should be added. Therefore we must have a function |even_element| to check if an argument is even or not. We have explained earlier that an argument of a commutator should be an integer (namely, the number of the generator), a commutator with two arguments, or another algebra element for which we have to check the first parameter. Unfortunately, that is not the whole truth. There is one exceptional situation for some specific application, which should be added: in prolongation theory we will use Lie (super)algebra valued functions. So far no problems, but these functions may also be differentiated, in which case one will get other algebra elements. However, an expression like |df(f(1),x)| doesn't belong in any of the classes stated above. We can test if it is even or odd, by testing the differentiated function. We add this as a special case. @u lisp procedure even_element(bracketname,exprn); if fixp exprn then exprn>0 else if operator_name_of exprn=bracketname then ((b1 and b2) or (not b1 and not b2)) @| where b1=even_element(bracketname,first_argument_of exprn), b2=even_element(bracketname,second_argument_of exprn) else if operator_name_of exprn='df then even_element(bracketname,first_argument_of exprn) else if fixp first_argument_of exprn then first_argument_of exprn>0 else stop_with_error("EVEN_ELEMENT: impossible to determine sign of", exprn,nil,nil)$ @ Both in |simp_liebracket_vector| and |simp_liebracket_kvalue| the arguments must be ordered canonically, hence we make that part a module. Both procedures should have a local variable |sign|, indicating if a sign must be added. @= if not_ordered_commutator(arg1,arg2) then begin scalar h; sign:=(even_element(bracketname,arg1) or even_element(bracketname,arg2));@/ h:=arg1;arg1:=arg2;arg2:=h; %Switch |arg1| and |arg2|% end @; @ Once |arg1| and |arg2| are ordered (i.e., |arg1|${}\leq{}$|arg2|), we still have to check for integer valued |arg1| and |arg2| that $-n\leq{}$|arg1| and |arg2|${}\leq m$, if $m$ and $n$ are the number of even and odd generators, respectively. @= if arg1<-get(bracketname,'odd_dimension) or arg2>get(bracketname,'even_dimension) then stop_with_error("SIMP_LIEBRACKET:",list(bracketname,arg1,arg2),"out of range",nil) @; @ After the preparations above the implementation of the procedure |simp_liebracket_vector| is quite straightforward. If the commutator has a value, this value is simplified and returned as a standard quotient, otherwise the commutator itself is returned as a standard quotient. This last step is done by the standard REDUCE procedure |mksq(kernel,pow)|, which returns |kernel| to the power |pow| as a standard quotient, but also has a side effect that we will explain in due time. There is, however, one thing, which we should be well aware of. Namely, if one of the arguments is zero, the commutator must be zero. This can be achieved by initializing both $\lie(i,0)$ for $i=-n,\dots,-1$ and $\lie(0,i)$ for $i=0,\dots,m$ to zero. Moreover the commutators $\lie(i,i)$ with $i>0$ are zero. Hence these should also be initialized to zero. Moreover, as we will explain later on, in some cases it will be necessary to resimplify the resulting commutator, in order the get a well ordered standard quotient, which will be treated in the right way by REDUCE. This case will be treated in due time. @u lisp procedure simp_liebracket_vector(bracketname,arg1,arg2); begin scalar sign,commutator; @; @; @; return if sign then negsq commutator else commutator; end$ @ The kvalue list of an algebraic operator is an association list, the |car| of an element of which is a kernel of that operator, the |cadr| its value. The kvalue list of an operator is stored on its propery list as the property |kvalue|. As already explained, access to an association list is through the procedure |assoc|. Knowing this, we can write the procedure |simp_liebracket_kvalue| without difficulty. @u lisp procedure simp_liebracket_kvalue(bracketname,arg1,arg2); begin scalar sign,commutator; @; commutator:=assoc(list(bracketname,arg1,arg2),get(bracketname,'kvalue));@/ commutator:= if commutator then simp cadr commutator else mksq(list(bracketname,arg1,arg2),1); return if sign then negsq commutator else commutator; end$ @*= Assignment to commutators. With the simplification procedure written above, we are able to retrieve values of commutators. As we have explained in the introduction, we need a set-element-function |set_liebracket| to assign values to commutators. This seems to be the appropriate moment to explain how one can assign |value| to |kernel|. This is done by calling the procedure |setk(kernel,value)|. If |kernel| is of the form $f(a_1,\dots)$, where $f$ possesses the property |rtype|, which on its turn possesses a property |setelemfn| (the set-element-function for that rtype), the assignment is done by this set-element-function. In all other cases the procedure |setk1| takes care of it. So to make the construction work in our case, we have to declare any liebracket to be of rtype |liebracket| and assign to |liebracket| the property |setelemfn|. @ There is, however, one more thing to explain about rtypes: commutators should not be recognized as objects of rtype |liebracket| since this will lead to type mismatch problems throughout REDUCE. To get the rtype of an object REDUCE almost anywhere uses the procedure |getrtype|, which, if provided, uses a rtypefn, to determine the rtype of an object. Rtypefn's have one argument, which are the arguments of the object, if this is not an atom, |nil| otherwise. So if we do not want commutators to be recognized as objects of rtype |liebracket|, we can simply return |nil| in all cases; @=@/ put('liebracket,'rtypefn,'liebracket_rtypefn)$@/ put('liebracket,'setelemfn,'set_liebracket)$ @ @u lisp procedure liebracket_rtypefn u;@/ nil$ @ There are, however, some points, which should be taken into account, before we can write the procedure. The first of this is, that we want commutators only to adopt values which are actually algebra elements. Hence we should check this condition if an assignment is made. The most convenient way to check if some expression is is an element of the Lie (super)algebra is to use the procedure |independent_part| of the TOOLS package. If the variable |algebra_elements| is the list of all operators allowed as algebra elements, then the result of calling |independent_part(value,algebra_elements)| is the part of |value| independent of operator allowed as algebra element, hence for a {\it valid\/} algebra element |value| 0. @= if independent_part(value,algebra_elements) neq 0 then rederr("SET_LIEBRACKET: assigned value invalid as algebra element") @; @ We have already explained that it is not necessary or even undesirable to assign values to commutators, which can be decomposed into smaller components, using the bilinearity. For such an assignment will never be used, since the simplification procedure of a liebracket actually decomposes a commutator into is smallest components, before trying to find any value. Therefore both arguments of a commutator, which we want to assign a value to, either have to be integer (as a shorthand notation for a generator), or a single algebra element. If they have the form $x(i)$ where |x| is the generatorname of liebracket |bracketname|, we must strip off the generator, in order to get the commutator in a canonical form. Moreover generators should not exceed the maximal number of odd or even generators, respectively. The macro |check_and_strip_argument| checks one argument for its validity, using the conditions stated in the previous section. Because we have to satisfy a lot of conditions and we don't want the procedure merely to exist out of error messages, we use a variable |error| to indicate whether an error has occured or not. In this way we can do with one error message after all tests. The variable |error| has to be local at some higher level. The macro |wrong_atomic_argument| checks an atomic argument is an integer and lies within the ranges of the liebracket. @d wrong_atomic_argument(arg)=@/ ((not fixp arg) or arg<-get(bracketname,'odd_dimension) or @| arg>get(bracketname,'even_dimension)) @; @d check_and_strip_argument(arg)=@/ if atom arg then error:=wrong_atomic_argument(arg) else begin error:=not member(operator_name_of arg,algebra_elements); if not error and operator_name_of arg=generatorname then begin arg:=first_argument_of arg; error:=not atom arg or wrong_atomic_argument(arg); end; end @; @=@/ check_and_strip_argument(arg1); if not error then check_and_strip_argument(arg2); if error then rederr("SET_/CLEAR_LIEBRACKET: argument(s) invalid or out of range") @; @ There are a few ``special'' commutators which are initialized to zero and should never be changed again. If $\lie$ is a liebracket, these commutators are $\lie(i,i)=0$ for all $i>0$ (this follows directly from the (graded) skew-symmetry and the fact that $x(i)$ is even for $i>0$), $\lie(i,0)$ for $i=-n,\dots,-1$ and $\lie(0,i)$ for $i=0,\dots,m$ (this has been explained in one of the previous sections). Moreover, if a commutator has been used to solve other commutators or generators using the Jacobi identity, it may be dangerous to change this commutator. In the first case we must give an error message, in the second case a warning will do. This kind of information is most conveniently recovered from the informative part of the vector structure. Without going into detail right here, the following module will take care of the point raised above. Note that |arg1| and |arg2| need to be we ordered for this check. @d special=s @=@/ error:=@+if fixp arg1 and fixp arg2 then (if entry then informative_part_of entry) where entry=get_vector_structure(bracketname,arg1,arg2); if error then if car error='special then rederr("SET_/CLEAR_LIEBRACKET: commutator can not be changed") else message("SET_/CLEAR_LIEBRACKET: changing", list(bracketname,arg1,arg2),"may lead to errors",nil) @; @ With the modules written above we can implement the procedure |set_liebracket| at once. We |reval| both arguments before continuing. This is useful, because the simplification procedure does the same. Notice that a set-element-function doesn't need to return a value. @u lisp procedure set_liebracket(val,value); if length val neq 3 then rederr("SET_LIEBRACKET: assignment only possible to commutators") else begin scalar bracketname,generatorname,algebra_elements,arg1,arg2, error,sign; bracketname:=operator_name_of val; generatorname:=get(bracketname,'generatorname); algebra_elements:=bracketname . generatorname . get(bracketname,'algebra_elements); arg1:=reval first_argument_of val; arg2:=reval second_argument_of val; @; @; @; value:=aeval value; @; if sign then value:=mk!*sq negsq simp value; @; end$ @ Before we can implement the remaining part of the set-element-function of a liebracket, we have to say something about the mechanism that controls the reevaluation of algebraic expressions in REDUCE, the !*SQ prefixform. An algebraic expression in !*SQ prefixform is a list of the form (|!*sq| {\it standard\_quotient} [|t|$\vert$|nil|]). If the last element is |t|, no assignments have taken place after the last simplification of the expression, which can affect its value. If it is |nil|, the expression may have been affected by some assignment that has taken place, so reevaluation is necessary. If reevalutation is necessary, it is clear that the |t|'s must be replaced by |nil| for all algebraic expressions at a time. At this place it is not necessary to explain how this can be accomplished, but it is sufficient to say that the call |rmsubs()| does the job properly. If a kernel has never been used in any other algebraic expression, it is clear that it is unnecessary to call |rmsubs| if someone assigns a value to this kernel. Therefore, for every kernel REDUCE keeps track if it has been used in some other algebraic expression. For atoms this is done by flagging them |used!*|, for operator elements it is recorded on the so called klist of that operator. Of course the standard REDUCE procedures respect this mechanism. But we took the simplification of and assignment to commutators in our own hands. Did we take enough precautions to respect this mechanism? Well, a few sections ago, when implementing the simplification function of a liebracket, we mentioned, but did not explain a side effect of the procedure |mksq| which we used to convert a kernel to a standard quotient. This seems to be the right moment to explain that this side effect is the recording of the fact that the kernel is used by flagging it |used!*| or putting it on the klist. This partially solves our problem, for if a unknown commutator is used in some other algebraic expression it will be simplified by |simp_liebracket| which makes it a standard quotient by calling |mksq|. On the other hand, as experience showed, for a liebracket of average length, the klist may get a length of about 10000 to 20000 elements and reduce the performance of the entire system in an quite drastic way. Therefore we will partially replace the klist mechanism for a liebracket by storing the klist information as an additional entry in the vector structure, just for those commutators whose value is also stored in the vector structure. In order to make this new construction work it turns out that two standard REDUCE procedures have to be adapted. These changes are explained in the last section of this document. @ If we do an assignment to a commutator we must call |rmsubs| if necessary. Without going into the matter too deep right here, we will simply give a macro definition which checks if an operator element is used. @d used_operator_element(opr_el)=@/ 'used!* memq cddr fkern opr_el@; @ If the two arguments of the commutator which we want to store are integers, we must use the vector structure to store it and eventually call |rmsubs| ourselves, otherwise it must be stored on the kvalue list. In the last case the standard REDUCE procedure |setk1| takes care of everything. @= if fixp arg1 and fixp arg2 then begin if used_operator_element(list(bracketname,arg1,arg2)) then rmsubs(); put_commutator(bracketname,arg1,arg2,value); end else setk1(list(bracketname,arg1,arg2),value,t) @; @*= Clearing liebrackets. There is one aspect of the access to liebrackets and/or commutators which we have left out of sight so far deliberately, namely how to clear these objects. Clearing expressions and/or operators in REDUCE is done by the procedures |clear| and |clear1|, the last one of which does its job by two subsequent calls of the procedure |let2| with different parameters. In earlier versions of this package we used the procedure |clear| to clear commutators, but it seemed impossible to use it to clear an entire liebracket, because a liebracket isn't just an ordinary rtype. The only possibility to let this construction work for commutators, was to jump through some procedures in an obscure and illogical way and finally let the clearing take place in the simplification procedure depending on the flag |subfg!*|. Clearing of an entire liebracket was done by a procedure of itself. In this version we will do the job in a more logical way by changing the standard REDUCE procedure |clear| in such a way that the clearing of both commutators and liebrackets will take place in a procedure of itself. The idea behind this change is quite simple: if the object to be cleared is of some rtype which on its turn possesses the property |clearfn|, then apply |clearfn| to it, otherwise proceed as before. In that way it resembles the procedure |setk|, which uses a set-element-function for rtypes. Note that |clear| has the property |stat='rlis| which means that it can have an arbitrary number of arguments separated by commas, which the parser will pass to it as a list. Hence also |clear1|, which is called by |clear|, will have its argument as one list. Notice that we can't use |getrtype| to get the rtype of an operator element since |getrtype| will, for instance, not recognize a commutator to be an element of the rtype liebracket. @u lisp procedure clear1 u; begin scalar x,xx; while u do <>; u := cdr u>> end$ @ The clearfn of a liebracket will be the procedure |clear_liebracket|. This has to be placed on the property list of |liebracket|. @=@/ put('liebracket,'clearfn,'clear_liebracket)$ @ The procedure |clear_liebracket| is rather simple: if its argument is an atom, we have to clear an entire liebracket by removing all its properties, otherwise the argument should be a commutator. @u lisp procedure clear_liebracket val; if atom val then @ else if length val = 3 then @ else rederr("CLEAR_LIEBRACKET: wrong number of arguments to commutator")$ @ Clearing a commutator is almost the same as assigning |nil| to it. Therefore we have to manipulate the arguments in the same way as in the procedure |set_liebracket|, except that we need not incorporate a possible change of sign. We copy it without comment. @= begin scalar bracketname,generatorname,algebra_elements,arg1,arg2,error,h; bracketname:=operator_name_of val; generatorname:=get(bracketname,'generatorname); algebra_elements:=bracketname . generatorname . get(bracketname,'algebra_elements); arg1:=reval first_argument_of val; arg2:=reval second_argument_of val; @; if not_ordered_commutator(arg1,arg2) then begin h:=arg1;arg1:=arg2;arg2:=h; %Switch |arg1| and |arg2|% end; @; @; end @; @ If |arg1| and |arg2| are integers, we have to clear an entry in the vector structure, otherwise we have to clear the commutator by replacing the kvalue list of |bracketname| by the old kvalue list with one entry removed. Note that there is no need to update the !*SQ prefixforms by calling |rmsubs|, since the calling procedure |clear| has already taken care of that. @=@/ val:=list(bracketname,arg1,arg2); if fixp arg1 and fixp arg2 then if get_commutator(bracketname,arg1,arg2) then @| put_commutator(bracketname,arg1,arg2,nil) else message("CLEAR_LIEBRACKET:",val,"not found",nil) else begin scalar kvalue; kvalue:=get(bracketname,'kvalue); if (h:=assoc(val,kvalue)) then put(bracketname,'kvalue,delete(h,kvalue)) else message("CLEAR_LIEBRACKET:",val,"not found",nil); end @; @*= Tools for solving Jacobi identities. We have gathered enough material now to implement one of the main tasks of this package, namely the computing and solving of Jacobi identities in order to find new relations between commutators and generators. To accomplish this, we have to do the following things in succession: first we have to find all triples $(i,j,k)$ with $i,j,k$ integer that satisfy all conditions such that the Jacobi identity for $x(i)$, $x(j)$ and $x(k)$ may lead to a new relation and secondly, for each triple $(i,j,k)$ found in the first step, we must compute this Jacobi identity and solve it. \bigskip In the sections where we specified the requirements for a liebracket, we found that it is interesting to compute and solve the Jacobi identities for all $x(i)$, $x(j)$ and $x(k)$ such that all three commutators $\lie(i,j)$, $\lie(j,k)$ and $\lie(i,k)$ are a linear combination of generators. For these Jacobi identities (may) lead to new relations between generators and/or commutators of two generators, which are the main object of our interest. How must we proceed to find all triples $(i,j,k)$ that satisfy the conditions stated above? Well, a typical sequence of actions while trying to compute (part of) a Lie (super)algebra could be: introduce some new generators as names for unknown commutators (i.e., assign the generators to these commutators) and try to find new relations implied by Jacobi identities containing these commutators. Hence we could proceed as follows: first find all ``new'' commutators $\lie(i,j)$ which are a linear combination of generators (by ``new'' we mean those commutators which haven't been processed before). Then, if $\lie(i,j)$ is such a commutator, $(i,j,k)$ is a triple for which the Jacobi identity has to be checked, if both $\lie(i,k)$ and $\lie(j,k)$ are linear combinations of generators. It is easily seen that proceeding this way one will find all Jacobi identities solvable until that stage. There is one aspect which we haven't explained yet: how do we recognize commutators which have already been processed. The observant reader will remember that we used the vector structure not only to store values of commutators, but also reserved a part for additional information about the commutator, initialized to |nil|. It is clear that we can use it right here to mark commutators which have already been processed. \bigskip There is, however, another purpose for which we will use the ``informative'' part of the vector structure, namely to indicate if the computation of a Jacobi identity can be done more efficiently, which is very important because of the large amount of Jacobi identities we have to compute. For this look at a characteristic term of a Jacobi identity, say $\lie(i,\lie(j,k))$, and suppose that $\lie(j,k)=\sum_q a_q*x(q)$, a linear combination of generators. Hence we have to compute $\lie(i,\sum_q a_q*x(q))$ or using the bilinearity $\sum_q a_q*\lie(i,q)$. Computing this kind of expression by simply applying |simp_liebracket| to it, we (have to) use the procedure |operator_coeff| to get all $x(q)$'s and $a_q$'s every time we come across $\lie(j,k)$. It would be much more efficient, if the value of $\lie(j,k)$ were stored in such a way, that there is no need to use the procedure |operator_coeff| to get all $x(q)$'s and $a_q$'s. This can indeed be done, if we take advantage of the way how standard forms in REDUCE are build up. Using the procedure |get_all_kernels|, described in the TOOLS package, and the standard REDUCE procedure |reorder|, it is very easy to accomplish that the $x(q)$'s occur as leading variable of (a reduced part of) the value of $\lie(j,k)$ and the $a_q$'s as leading coefficient. If $\lie(j,k)$ is a reordered sum of generators and we want to compute $\lie(i,\lie(j,k))$ using this reordering, we cannot simplify $\lie(j,k)$ during the computation because this would destroy the special ordering we imposed. This implies that we should think about what to do if we find a linear dependency between some generators and solve it for one of them, let's say $x(q)$. For suppose this $x(q)$ occurs in the value of $\lie(j,k)$, then computing $\lie(i,\lie(j,k))$ using the reordering, would lead to a term $\lie(i,q)$ which is not desirable because of the linear dependency found. A solution to this problem would be, if we find a linear dependency and solve it for $x(q)$, to assign to all $\lie(i,q)$'s a value according to this linear dependency. The most convenient way to implement this is by making a Lie (super)algebra generator a rtype of itself, |algebra_generator|, and assigning a set-element-function and a clear function to it, which take care of all the necessary actions. Moreover, this offers us the possibility do some more checks. For instance, in order to keep the solving of Jacobi identities act as we intended, we only want to allow assignments to a generator, which are linear combinations of other generators. For if we would allow this, we would possibly get Jacobi identities, marked as solvable by the process described above, containing commutators with non-integer arguments, for which we certainly don't want to solve. We will write these procedures in a next chapter. @ In the previous sections we have seen to which purposes we can use the informative part of the vector structure. Before describing its contents exactly, we will add one other application. Namely, for whatever reason, we may want to compute all Jacobi identities again, so it must be possible to indicate if all Jacobi identities containing some commutator have to be recomputed. Therefore, we can distinguish the following three conditions for each commutator:\medskip \item{1.} the commutator hasn't been reordered and hence hasn't been checked until now. This is the initial status for every commutator and is indicated by |nil| (we already used this in the procedure |put_commutator|). \item{2.} the commutator has both been reordered and checked. This is indicated by |'(t)|. \item{3.} the commutator has been reordered, but must be checked again. This is indicated by |'(nil)|. \enditem If we want to recompute all Jacobi identities for some liebracket, |'(t)| has to be replaced by |'(nil)| for each commutator in the vector structure of this liebracket, which has already been checked. To accomplish this we will use a mechanism similar to the one used for !*SQ prefixforms. These are constructed by |cons|'ing |'!*sq . @t{\it standard\_quotient}@> . !*sqvar!*|, where |!*sqvar!*| is a list |'(t)|. In doing so, the |t| of !*SQ prefixforms can be replaced by |nil| {\it globally}, by replacing the |car| of |!*sqvar!*| by |nil| with the procedure |rplaca|. This construction works because |rplaca(alist,new_car)| doesn't replace the |car| of |alist| by making a new copy |new_car . cdr alist|, but replaces the |car| in the physical memory. We will also |cons| a variable |!*jacobi_var!*| with value |'(t)| to each reordered commutator in the vectorstructure of a liebracket. However, in our case we don't want to replace the |t| by |nil| globally, but only for one liebracket at a time. Therefore each liebracket should have its own variable |!*jacobi_var!*|. It should be placed on the property list of the liebracket under consideration as the property |!*jacobi_var!*|. The procedure |recompute_jacobi_identities_of| takes care of this replacement and also puts a new copy of |!*jacobi_var!*| on the property list. This procedure should be available in algebraic mode. We foresee that we have to check if |bracketname| is a liebracket in a lot of procedures. In order to be able print an appropriate error message we will make definition to deal with it. For convenience we will also write a definition which checks the validity of a generator. @d check_if_bracketname_is_a_liebracket_in(proc)=@/ if get(bracketname,'rtype) neq 'liebracket then@| stop_with_error(proc,bracketname,"is not a liebracket",nil) @; @d check_if_generatorname_is_a_generator_in(proc)=@/ if get(generatorname,'rtype) neq 'algebra_generator then@| stop_with_error(proc,generatorname,"is not an algebra generator",nil) @; @u lisp operator recompute_jacobi_identities_of; lisp procedure recompute_jacobi_identities_of bracketname; begin scalar !*jacobi_var!*; check_if_bracketname_is_a_liebracket_in("RECOMPUTE_JACOBI_IDENTITIES:"); !*jacobi_var!*:=get(bracketname,'!*jacobi_var!*); rplaca(!*jacobi_var!*,nil); put(bracketname,'!*jacobi_var!*,list t); end$ @*1 Finding the unprocessed commutators. After the introduction above we are able to take care of the first part of finding the solvable Jacobi identities, namely collecting all commutators which are a sum of generators and haven't been processed until now. If we find such a commutator we must (a) reorder it in such a way that all generators occur in it as leading variables, (b) put it on a list of all commutators which have to be processed and (c) mark it processed in the vector structure. These three steps are implemented in the procedure |find_unprocessed_commutators_of|. In |find_unprocessed_commutators_of| we need quite a lot of properties of the liebracket under consideration. Some of them we have already met before, but there are also a few, which need some explanation right now. First of all we will store the list of unprocessed commutators on the property list as the property |commutator_list|, in order to keep the system as fool proof as possible. Namely, if we would keep this list as a local variable in |find_unprocessed_commutators_of| it could be destroyed by some user break, while in the vector structure these commutators were already marked as being processed. In that way we could loose some Jacobi identities. Because of the possibility of an user break we must be aware of the fact that this list may not be empty. Hence in all cases we must |cons| new commutators in front of it. Secondly we should be aware of the fact that not all commutators have to be used. Hence it is useless to check commutators which contain unused commutators. The number of used even and odd generators is stored on the property list of a liebracket as the properties |even_used| and |odd_used| respectively. The following definition sums up all the properties and variables necessary to access the vector structure directly, we can use it in several places. The module following it initializes them. Recall that we used the letter $m$ for the number of even generators and $n$ for odd generators. @d properties_for_direct_access=@/ vector_structure,m,m_used,n,n_used @=@/ vector_structure:=get(bracketname,'vector_structure);@/ m:=get(bracketname,'even_dimension);n:=get(bracketname,'odd_dimension);@/ m_used:=get(bracketname,'even_used);n_used:=get(bracketname,'odd_used) @; @ The properties necessary in the procedure |find_unprocessed_commutators_of| are listed below. The module following it initializes them. The variable |non_generators| represents all operators, except the generator, that are allowed as algebra element. @d necessary_properties_for_finding_commutators=@;@/ properties_for_direct_access,generatorname,non_generators, commutator_list,!*jacobi_var!* @= @; generatorname:=get(bracketname,'generatorname);@/ non_generators:=bracketname . get(bracketname,'algebra_elements);@/ commutator_list:=get(bracketname,'commutator_list);@/ !*jacobi_var!*:=get(bracketname,'!*jacobi_var!*) @; @ The procedure |find_unprocessed_commutators_of| is quite straightforward. Note that we don't make an exception for the ``special'' commutators |bracketname(i,j)| with $i=0$ or $j=0$ or $i=j>0$. Of course we don't want these commutators to be processed any further. This means that they must be initialized as already being processed. Also another category of commutators need not be processed, namely the commutators of generators which have been found linear dependent. Checking of Jacobi identities for linear dependent generators boils down to checking a linear combination of Jacobi identities for linear independent generators. Thus we shouldn't mark commutators of linear dependent generators as processed. Recall that the data of commutator |bracketname(i,j)| are stored in the vector structure at indices $n+i$ and $m-j$ for the outer and inner vector, respectively. @u lisp procedure find_unprocessed_commutators_of bracketname; begin scalar vector_i,entry_i_j,k_info_i_j,commutator,form,kord!*, necessary_properties_for_finding_commutators,comm_list_i, dependent_generators; @; @; for i:=-n_used:m_used do if not memq(i,dependent_generators) then begin vector_i:=getv(vector_structure,n+i); for j:=i:m_used do if not memq(j,dependent_generators) then @| @; end; return commutator_list; end$ @ Finding the dependent generators can be easily done using the kvalue list of |generatorname|. Of course we only need to store the index of each dependent generator. @= dependent_generators:= for each entry in get(generatorname,'kvalue) collect first_argument_of first_element_of entry @ An entry in the vector structure consists of a informative part (the |car|) and the klist and commutator part (the |cdr|). The following definitions translate some conditions of the informative part (which we have defined in one of the previous sections) into their lisp equivalents. @d not_processed=null car @d recomputation_necessary_for=null caar @ A standard form belonging to an algebra element is a sum of generators, if it contains no kernels of all other operators allowed as algebra elements. We can check this most conveniently by using the procedure |get_all_kernels|, which acts on standard forms and is described in the TOOLS package. Recall that the variable |non_generators| is the list of all operators other then the generator, allowed as algebra element. @d sum_of_generators(algebra_element)=@/ null get_all_kernels(algebra_element,non_generators) @; @ If a commutator is a sum of generators the following things should be done:\medskip \item{1.} it has to be reordered in such a way that all generators occur as leading variables of (a reduced part of) it. One should remember that reordering in REDUCE is done by the procedure |reorder|, which works on standard forms (this is described in more detail in the TOOLS package). Note that we rebinded the fluid system variable |kord!*| in the procedure |find_unprocessed_commutators_of|. In doing so the kernel ordering outside this procedure will not be affected. The definition |convert_form_into_reordered_commutator| takes care of the reordering. \item{2.} the commutator list must be updated. We store the indices $i$ and $j$ on it, since these contain all the necessary information. We will, however, use an association list on $i$, i.e., the smallest index, to store $i$ and $j$, because the number of commutators to be processed may be rather big. To keep the system fool proof we put the updated commutator list on the property list of the liebracket for each commutator separately. This part is taken care of by the definition |update_commutator_list|. Notice the use of |rplacd| to replace the |cdr| of nested lists. It is easily checked that this causes no harm. Due to the use of |rplacd| we do not have to store |commutator_list| on the property list of |bracketname|. If there is, however, no entry on |commutator_list| for $i$, we have to extend |commutator_list| with it and do store it. \item{3.} the entry in the vector structure has to marked as checked. This can be done by storing |!*jacobi_var!* . k_info_i_j . commutator| at the right place in the inner vector, where |k_info_i_j| is the |k_info| value of the $(i,j)$-th entry of the vector structure. The definition |mark_entry_as_checked| takes care of it. @d convert_form_into_reordered_commutator=@/ setkorder get_all_kernels(form,generatorname);@/ commutator:=!*ff2a(reorder form,denr commutator) @; @d update_commutator_list=@/ if (comm_list_i:=assoc(i,commutator_list)) then@/ (if not member(j,comm_list_i) then rplacd(comm_list_i,j . cdr comm_list_i)) else @+ <> @; @d mark_entry_as_checked=@/ putv(vector_i,m-j,!*jacobi_var!* . k_info_i_j . commutator) @; @ If a commutator has not been checked so far, we should only process it now, if it is a sum of generators. Commutators, for which recomputation is necessary, don't have to be reordered, since this has already been done the first time they were checked. @= begin entry_i_j:=getv(vector_i,m-j); if entry_i_j and commutator_part_of entry_i_j then if not_processed entry_i_j then begin commutator:=simp!* commutator_part_of entry_i_j; k_info_i_j:=k_info_of entry_i_j; form:=numr commutator; if sum_of_generators(form) then begin convert_form_into_reordered_commutator; update_commutator_list; mark_entry_as_checked; end; end else if recomputation_necessary_for entry_i_j then begin commutator:=commutator_part_of entry_i_j; k_info_i_j:=k_info_of entry_i_j;@/ update_commutator_list; mark_entry_as_checked; end; end @; @*1 Finding the unsolved Jacobi identities. With help of the procedure described above we have found a list of unprocessed commutators and put it on the property list of the liebracket under consideration. Our next task is for each commutator on this list to find the unsolved Jacobi identities belonging to it. If $(i,j)$ is a couple of indices of the commutator list, the solvable Jacobi identities are represented by all triples $(i,j,k)$ for which both |bracketname(i,k)| and |bracketname(j,k)| are a sum of generators, i.e., are marked as processed in the vector structure. It is easy to see that the (graded) Jacobi identity $$(-1)^{\vert x\vert\cdot\vert z\vert }[x,[y,z]]+ (-1)^{\vert y\vert \cdot\vert x\vert}[y,[z,x]]+ (-1)^{\vert z\vert \cdot\vert y\vert }[z,[x,y]]=0$$ in case of equality of some of the elements $x$, $y$ and $z$ sometimes is fulfilled automatically, depending if $x$, $y$ and $z$ are odd or even. If we want to compute Jacobi identities for $x(i)$, $x(j)$ and $x(k)$ with $i\leq j\leq k$ the reader should check that only the following ranges for $i$, $j$ and $k$ give rise to meaningful identities (i.e., identities which are not fulfilled automatically): (1) $i\leq j\leq k < 0$, (2) $i\leq j <00$. We recall that we expected these ``special'' commutators to be initialized to zero and to be marked as processed. Now the condition ``marked as processed'' only means that the informative part of an entry in the vector structure is a list whose |car| is |t| (i.e., has a value) or |nil| (i.e., has no value), indicating whether or not recomputation of Jacobi identities for this commutator is necessary. In the light of what we have said in this section it seems not a bad idea to mark these ``special'' commutators as special. We can do this by initializing the informative part of an entry in the vector structure to |'(special)|. One can easily check that this does not affect the condition ``marked as processed''. Hence if we have to find all meaningful triples $(i,j,k)$ belonging to an unprocessed commutator represented by the couple $(i,j)$ with $i\leq j$, we have to check the commutators (1) |bracketname(k,i)| and |bracketname(k,j)| for $-n_{\rm used}\leq k\leq i-1$, (2) |bracketname(i,k)| and |bracketname(k,j)| for $i\leq k\leq j-1$ and (3) |bracketname(i,k)| and |bracketname(j,k)| for $j\leq k\leq m_{\rm used}$ to be marked as processed, but not special, where $m_{\rm used}$ and $n_{\rm used}$ are the number of even and odd generators which have been used so far. The macro |processed_but_not_special| checks this for an entry of the vectorstructure. @d processed_but_not_special(entry)=@/ (car entry and caar entry neq 'special) @; @ As in the case of finding the unprocessed commutators we will store the list of solvable Jacobi identities on the property list of the liebracket under consideration as the property |identity_list|. In this section we will initialize all necessary properties for finding Jacobi identities. @d necessary_properties_for_finding_identities=@/ properties_for_direct_access,commutator_list,identity_list @= @; commutator_list:=get(bracketname,'commutator_list);@/ identity_list:=get(bracketname,'identity_list) @; @ If a Jacobi identity $(i,j,k)$ is solvable, depends on the $(i,k)$-th and $(j,k)$-th entry of the vector structure and it has only to be stored if it has not been stored before. These conditions are checked by the definition |check_and_store_identity|. Its argument is a triple $i,j,k$ with $i\leq j\leq k$. We will store the Jacobi identities to be solved on a double association list |identity_list|, as the number of them may increase very rapidly, in which case linear search would be too time consuming. Storing a Jacobi identity on |identity_list| is taken care of by the macro |update_identity_list|. @d check_and_store_identity(i,j,k)=@/ if processed_but_not_special(entry_i_k) and processed_but_not_special(entry_j_k) then update_identity_list(i,j,k) @; @d update_identity_list(i,j,k)=@/ if (id_list_i:=assoc(i,identity_list)) then if (id_list_i_j:=assoc(j,cdr id_list_i)) then @/ (if not member(k,cdr id_list_i_j) then rplacd(id_list_i_j,k . cdr id_list_i_j)) else rplacd(id_list_i,list(j,k) . cdr id_list_i) else identity_list:=list(i,list(j,k)) . identity_list @; @ The procedure |find_Jacobi_identities_of| essentially consists of a double |while| loop in which we try to find solvable Jacobi identities for each commutator on the |commutator_list| of a liebracket. Commutators which have been checked may be removed from the |commutator_list|. As in |find_unprocessed_commutators_of| we will use |rplacd| to alter the inner lists of |commutator_list|. @u lisp procedure find_Jacobi_identities_of bracketname; begin scalar comm_list_i,i,j,vector_i,vector_j,vector_k, entry_i_k,entry_j_k, necessary_properties_for_finding_identities, id_list_i,id_list_i_j; @; while commutator_list do begin comm_list_i:=first_element_of commutator_list; i:=car comm_list_i; while cdr comm_list_i do begin j:=cadr comm_list_i; @; rplacd(comm_list_i,cddr comm_list_i); end; commutator_list:=rest_of commutator_list;@/ put(bracketname,'commutator_list,commutator_list); end; return identity_list; end$ @ Finding and storing all Jacobi identity for a couple $i,j$ consists of three phases which differ in the way they get the $(i,k)$-th and $(j,k)$-th entry of the vector structure. After we have found all identities belonging to $i,j$ we must save the updated |identity_list| on the property list of the liebracket under consideration. Saving it once for a commutator pair $i,j$ will do since at this stage the commutator pair has not been removed from the commutator list yet. @=@/ vector_i:=getv(vector_structure,n+i); vector_j:=getv(vector_structure,n+j); for k:=-n_used:i-1 do begin vector_k:=getv(vector_structure,n+k); if (entry_i_k:=getv(vector_k,m-i)) and (entry_j_k:=getv(vector_k,m-j)) then check_and_store_identity(k,i,j); end; for k:=i:j-1 do begin vector_k:=getv(vector_structure,n+k); if (entry_i_k:=getv(vector_i,m-k)) and (entry_j_k:=getv(vector_k,m-j)) then check_and_store_identity(i,k,j); end; for k:=j:m_used do begin if (entry_i_k:=getv(vector_i,m-k)) and (entry_j_k:=getv(vector_j,m-k)) then check_and_store_identity(i,j,k); end;@/ put(bracketname,'identity_list,identity_list) @; @*1 Computing special Jacobi identities. The procedures developed so far supplied us with a list of triples $(i,j,k)$ with $i\leq j\leq k$ such that all three commutators $\lie(i,j)$, $\lie(i,k)$ and $\lie(j,k)$ are linear combinations of generators and are stored in a reordered form, which facilitates a fast computation of the nested commutators of the Jacobi identity for $x(i)$, $x(j)$ and $x(k)$. In the following sections we will write the procedure |special_Jacobi_identity| that performs the next step, namely the actual computation of a Jacobi identity for a triple $(i,j,k)$ satisfying the requirements stated above. To explain the idea behind the calculation of the Jacobi identity, suppose we have a triple $i,j,k$ as stated above. Then by assumption we have $\lie(j,k)=\sum a^l_{jk}x(l)$ so that $\lie(i,\lie(j,k))=\sum a^l_{jk}\lie(i,l)$. Now the right hand side of the last expression can be computed rather easily by using the reordering imposed on the commutator $\lie(j,k)$ as we will see in the sequel. One should be aware that is not possible to simplify the expression for $\lie(j,k)$ before using it, because this will destroy the reordering. Therefore we have to take into account the following points:\medskip \item{1.} In case one of the generators $x(l)$ has been found linear dependent of other generators, we must see to it that $\lie(i,l)$ evaluates to the right value. As we have already explained this will be taken care of by the set-element-function for generators. \item{2.} The coefficient $a^l_{jk}$ must be simplified before usage. \item{3.} $\sum a^l_{jk}\lie(i,l)$ must be evaluated to the right value, i.e., we must take care that substitutions for products and powers take place properly. This can be achieved by calling the standard REDUCE procedure |subs2| on the simplified expression. A search for substitution of powers is only performed if the fluid system variable |!*sub2| is set to |t|. If necessary this is done automatically by low level procedures used during ordinary simplification, depending if a kernel in the simplified expression occurs on the list of power substitutions, |powlis!*|. After a call of |subs2| |!*sub2| will always be |nil|, so that it can be used for the next expression to be simplified. |!*sub2| also occurs on the so called |initl| of REDUCE. Variables occuring on the |initl| are initialized to an initial value before every command. @ The procedure |sub_identity| calculates a general term $(-1)^{\vert x(i)\vert\cdot\vert x(k)\vert}\lie(i,\lie(j,k))$ of the Jacobi identity using the method described above. To achieve this we must use the numerator of $\lie(j,k)$ (which is a standard form) to add up all terms of $\lie(i,\lie(j,k))$. If $\lie(j,k)$ is zero, |sub_identity| also is zero, otherwise by assumption the main variable |mvar| of the numerator of $\lie(j,k)$ is a generator, the leading coefficient |lc| its coefficient. The same applies to the reductum |red| of the standard form. Therefore the summation can simply be performed in a |while| loop. Standard quotients can be added, subtracted, multiplied and divided by the procedures |addsq|, |subtrsq|, |multsq| and |quotsq| respectively. To simplify the coefficients we can use the procedure |subf1| which simplifies a standard form to a standard quotient. Its first argument is the standard form to be simplified, the second argument a list of substitutions to be performed (in our case |nil|). Recall that the commutators are stored as !*SQ prefixforms. To get the unsimplified standard quotient of a !*SQ prefixform we should simply take its |cadr|. @d simp_sf_to_sq(sf)=subf1(sf,nil)@; @d get_sq_of=cadr @u lisp procedure sub_identity(bracketname,i,j,k); begin scalar comm_j_k,denr_j_k,coeff_l,l,comm_i_l,term; comm_j_k:=get_commutator(bracketname,j,k); return if comm_j_k= 0 then nil . 1 else begin comm_j_k:=get_sq_of comm_j_k; denr_j_k:=simp_sf_to_sq(denr comm_j_k); comm_j_k:=numr comm_j_k; @; if i<0 and k<0 then term:=negsq term; @+%Add a sign if $x(i)$ and $x(k)$ are odd% return quotsq(term,denr_j_k); end; end$ @ One should notice that we don't check during the assignment to a commutator if all generators occuring in the assigned value are valid. Since the call of |simp_liebracket_vector| checks the validity of integer arguments of a commutator, we only have to check if the generators occuring have integer arguments here. @= term:=nil . 1; %Initialize |term| as standard quotient% while comm_j_k do begin l:=first_argument_of mvar comm_j_k; coeff_l:=simp_sf_to_sq(lc comm_j_k); if not fixp l then stop_with_error("SOLVE_JACOBI_IDENTITIES:",list(bracketname,j,k), "contains invalid generator",mvar comm_j_k); comm_i_l:=simp_liebracket_vector(bracketname,i,l); term:=addsq(term,multsq(coeff_l,comm_i_l)); comm_j_k:=red comm_j_k; end @; @ The procedure |special_Jacobi_identity| can now be written at once. We add an additional minus sign because in most cases this will neutralize a minus sign in the output. Since |sub_identity| expects its arguments to be ordered, we have to switch |k| and |i| and the second term. This gives an additional sign $(-1)^{1+\vert i\vert\cdot\vert j\vert+ \vert i\vert\cdot\vert k\vert+\vert j\vert\cdot\vert k\vert}$, i.e., if $j>0$ an additional minus has to be added. @u lisp procedure special_Jacobi_identity(bracketname,i,j,k); mk!*sq subs2 negsq addsq(sub_identity(bracketname,i,j,k),@| addsq(multsq((if j>0 then -1 @+else 1) . 1, sub_identity(bracketname,j,i,k)),@| sub_identity(bracketname,k,i,j)))$ @*1 Updating the vector structure. From the last sections it may have become clear that until now it is impossible to update (i.e., store the simplified values of) the entries of the vector structure without deleting all additional information, since the set-element-function of a liebracket initializes the additional information to |nil|. As a consequence of this, updating the vector structure implies recomputation of all Jacobi identities. The procedure |update_vector_structure_of| does a better job. @u lisp operator update_vector_structure_of; lisp procedure update_vector_structure_of bracketname; begin scalar vector_i,entry_i_j, commutator,form,kord!*,generatorname,properties_for_direct_access; @; generatorname:=get(bracketname,'generatorname); for i:=-n_used:m_used do begin vector_i:=getv(vector_structure,n+i); for j:=i:m_used do begin entry_i_j:=getv(vector_i,m-j); @; end; end; end$ @ Updating an entry is necessary if it has a value, if it is not processed or if it is processed but not special. In the last case we must take care of the proper reordering. @= if entry_i_j and commutator_part_of entry_i_j then if not_processed entry_i_j then@| putv(vector_i,m-j,nil . k_info_of(entry_i_j) . aeval commutator_part_of entry_i_j) else if processed_but_not_special(entry_i_j) then begin commutator:=simp!* commutator_part_of entry_i_j;@/ form:=numr commutator; convert_form_into_reordered_commutator; putv(vector_i,m-j,informative_part_of(entry_i_j) . k_info_of(entry_i_j) . commutator); end @; @ As promised in the section where we implemented the simplification procedure of a liebracket, we will now explain how a (known) commutator of two generators has to be simplified exactly. Namely, if the value of a commutator is a sum of generators, the internal ordering of the standard quotient in the vector structure representing the commutator may be different from the default kernel ordering used in REDUCE, because of the reordering we performed intended for the efficient computation of Jacobi identities. Since differences in ordering may lead to unexpected results (e.g. zero expressions which are not represented by 0), we must see to it that we restore the right ordering of the standard quotient before returning any commutator. It is easily checked that reordering is necessary if and only if the condition |processed_but_not_special| is true. The ordinary ordering can be restored by applying |resimp| on the standard quotient part of the commutator. In all other cases if is sufficient just to apply |simp| to the commutator. The difference between both methods is the following: using the second method the standard quotient will be returned unchanged if the |cadr| of the !*SQ prefix form is |t| and simplified if |nil|. The first method, however, will always simplify and hence reorder the standard quotient before returning it. @=@/ commutator:=get_vector_structure(bracketname,arg1,arg2);@/ commutator:= if commutator and commutator_part_of commutator then if processed_but_not_special(commutator) then if commutator_part_of commutator=0 then nil . 1 else resimp get_sq_of commutator_part_of commutator else simp commutator_part_of commutator else mksq(list(bracketname,arg1,arg2),1) @; @*= Analysis of relations in Lie superalgebras. If we have a relation in a Lie superalgebra we have a few possibilities to solve it:\medskip \item{1.} The relation contains a commutator, for which we can solve the relation. \item{2.} The relation contains only generators, we have found a linear dependency which we can solve. \item{3.} The defining relations of the Lie superalgebra contained some parameters, which also occur in the relation to solve. In this case we can proceed as in case 1.\ and 2., but more carefully. For instance, suppose that we have found the relation $a(1)*\lie(1,2)+a(2)*x(1)+x(2)=0$. Then it is dangerous simply to solve for $\lie(1,2)$ because $a(1)$ eventually may become 0, in which case the relation becomes a linear dependency between $x(1)$ and $x(2)$. Also a relation like $(a(1)-1)*x(1)+a(2)*x(2)=0$ can be solved in two ways: we can put $a(1)=1$ and $a(2)=0$ or solve the linear dependency in case $a(1)\neq 1$ or $a(2)\neq 0$. \enditem To be able to recognize these parameters we will add to each liebracket the property |parameters|, which is an operator, elements of which may occur as parameters of the Lie superalgebra. @ To keep the computations as compact as possible we will suppose that any relation $R$ to be solved is a sum of generators and commutators of two generators. Taking into account the points raised above we can deduce the following strategy for finding a solution of a relation: \medskip \item{1.} If the relation contains at least one commutator whose coefficient does not depend on a parameter, choose one and solve for it. \item{2.} If the relation contains commutators, but all possessing coefficients depending on parameters, do not solve the relation. \item{3.} If the relation does not contain commutators, but at least one generator whose coefficient does not depend on a parameter, choose one and solve for it. \item{4.} If the relation does not contain commutators and all generators have coefficients depending on parameters, try solve the relation by solving the set of coefficients regarded as a linear set of equations in an appropriate set of parameters. \enditem These tasks can most conveniently be performed by using the procedures |operator_coeff|, for finding all generators with their corresponding coefficients, and |solvable_kernels| from the TOOLS package. The procedure |operator_coeff| has already been used and described before. The call |solvable_kernels(exprn,k_oplist,c_oplist)| will return an algebraic list of kernels |x| from operators occuring on |k_oplist|, such that |x| occurs linearly in |exprn| and the coefficient of |x| does not depend on any operator occuring on |c_oplist|. From this it is clear that |solvable_kernels| can be fruitfully used in step 1, 2 and 4. The process described above will be performed by the procedure |relation_analysis|. It returns either the kernel for which the relation is solved or |'unsolvable| or |'nested_commutator| if the relation for whatever reason is not solvable or contains nested commutators. @d zero_list= '(list 0)@; %List returned by |operator_coeff| applied to 0% @u lisp operator relation_analysis; lisp procedure relation_analysis(relation,bracketname); begin scalar generatorname,parameters,kernel_list,solvable_kernels, test,kernel,optimal_kernel,coefficient,clear_list; check_if_bracketname_is_a_liebracket_in("RELATION_ANALYSIS:"); generatorname:=get(bracketname,'generatorname); parameters:=get(bracketname,'parameters);@/ kernel_list:=operator_coeff(relation,generatorname); return if kernel_list=zero_list then 0 else if independent_part_of kernel_list neq 0 then @ else @; end$ @*1 Solving relations for a commutator. To solve |relation| for a commutator we must first find out if there are commutators whose coefficients do not contain parameters. This is performed by calling |solvable_kernels|. If there are any we have to choose one and solve for it. @= begin@/ solvable_kernels:=skip_list solvable_kernels(independent_part_of kernel_list,bracketname,parameters); return if null solvable_kernels then 'unsolvable else begin @; return if optimal_kernel then@+ <> else 'nested_commutator; end; end @ The main problem in solving a commutator from a relation, is choosing the most appropriate one to solve. We adopt the idea here that the grading of a liebracket will possess all necessary information. For instance, if one of the components of the grading is the length of the words in the Lie algebra, it is natural to solve for the longest word. In this view, if a Lie algebra only possesses a zero grading it doesn't matter for which commutator to solve. If a liebracket possesses a multigrading we will assume that the first component is the most important one. This means that we will first compare the first components and will only use the further components if these are equal. The basic procedure needed for this purpose is |first_degree_higher| which returns |t| if the first degree is higher than the second one. @u lisp procedure first_degree_higher(degree_1,degree_2); if null degree_1 then nil else if car degree_1>car degree_2 then t else first_degree_higher(cdr degree_1,cdr degree_2)$ @ In case two commutators have the same degree the above procedure will not give a unique choice independent of the ordering currently used in REDUCE. However, in order to guarantee an unique choice, we shall add the indices of the commutator to the degree. @u lisp procedure extended_commutator_degree(commutator,bracketname); nconc(add_degrees(get_permuted_degree(bracketname,i), get_permuted_degree(bracketname,j)),@| list(i,j)) @/ where i=first_argument_of commutator, j=second_argument_of commutator$ @ In case we have to compare two generators we assume the these will both be odd or even. Since in case of solving it is most natural to solve for the generator with the highest number we shall add the absolute value of the generator number to the degree list. @u lisp procedure extended_generator_degree(generator,bracketname); append(get_permuted_degree(bracketname,i),list abs(i)) @/ where i=first_argument_of generator$ @ Getting the highest of two degrees is fairly simple now. We should only be aware that in the application below the second degree may not be a list (if there is no second element for which we have to compare the degrees). In this case we should simply return the first degree. @u lisp procedure highest_degree(degree_1,degree_2); if atom degree_2 then degree_1 else if first_degree_higher(degree_1,degree_2) then degree_1 else degree_2$ @ In the code below the variable |optimal_kernel| will be a dotted pair containing the present highest degree and the present optimal kernel, until the last line. We will not solve the relation if it contains a nested commutator. In this case we set |optimal_kernel| to |nil . nil|. @=@/ optimal_kernel:= 0 . nil; while solvable_kernels and car optimal_kernel do begin kernel:=first_element_of solvable_kernels; if not fixp first_argument_of kernel or not fixp second_argument_of kernel then optimal_kernel:=nil . nil else if not ((test:=highest_degree(extended_commutator_degree(kernel,bracketname), car optimal_kernel)) eq car optimal_kernel) then optimal_kernel:=test . kernel; solvable_kernels:=rest_of solvable_kernels; end;@/ optimal_kernel:=cdr optimal_kernel @; @*1 Solving relations for a generator or parameters. If |relation| does not contain commutators we have to find out if there are generators without parameter coefficients. If so we have a linear dependency to be solved w.r.t. generator which is optimal in some sense, otherwise we may try to solve the relation by appropriately solving parameters. @= begin@/ solvable_kernels:=skip_list solvable_kernels(relation,generatorname,parameters); return if null solvable_kernels then @ else begin @; return if optimal_kernel then@+ <> else 'invalid_generator; end; end @; @ @=@/ optimal_kernel:= 0 . nil; while solvable_kernels and car optimal_kernel do begin kernel:=first_element_of solvable_kernels; if not fixp first_argument_of kernel then optimal_kernel:=nil . nil else if not ((test:=highest_degree(extended_generator_degree(kernel,bracketname), car optimal_kernel)) eq car optimal_kernel) then optimal_kernel:=test . kernel; @/ solvable_kernels:=rest_of solvable_kernels; end;@/ optimal_kernel:=cdr optimal_kernel @; @ Solving parameters boils down to the following actions to be taken for each |coefficient| of a generator occuring on |kernel_list|, the list of generators and their coefficients:\medskip \item{1.} If |coefficient| contains some solvable parameters (i.e., occuring linearly in it), choose the first one, solve |coefficient| w.r.t. this parameter and put it on |clear_list|. Searching for solvable parameters can be performed by applying |solvable_kernels| with appropriate arguments. \item{2.} If a |coefficient| does not contain a solvable parameter, we have to clear all the parameters occuring on |clear_list| (i.e., which had been previously solved) and set |clear_list| equal to |nil|, indicating that |relation| is not solvable. @= repeat begin coefficient:=coefficient_of first_element_of kernel_list; solvable_kernels:=skip_list solvable_kernels(coefficient,parameters,parameters); if null solvable_kernels then begin apply1('clear,clear_list); clear_list:=nil end else begin kernel:=first_element_of solvable_kernels; linear_solve_and_assign(coefficient,kernel); clear_list:=kernel . clear_list; kernel_list:=rest_of kernel_list; end end until null kernel_list or null clear_list @; @ In order to give the user full control over the process of solving parameters we introduce a switch |solve_parameters|, indicating if solving of parameters is allowed. @=@/ new_switch(solve_parameters,nil)$ @ If it is allowed to solve parameters we can do so, otherwise |relation| is not solvable. The reader should verify that we are sure that |relation| contains generators at this stage. @= if !*solve_parameters then begin kernel_list:=kernel_coeff_list_of kernel_list; @; return if clear_list then 'list . clear_list else 'unsolvable; end else 'unsolvable @; @*= Solving Jacobi identities. Now we have written all kinds of tools for solving Jacobi identities and a procedure for analysing Lie algebraic relations, we are able to implement the top level procedure |solve_Jacobi_identities_of| for actually solving Jacobi identities, and some other auxiliary procedures. Using the procedures |find_unprocessed_commutators_of|, |find_Jacobi_identities_of| and |relation_analysis|, solving Jacobi identities is in fact really simple: while there are processable commutators, find the Jacobi identities belonging to them, try to solve and if necessary print these identities. Identities which are not solvable automatically should be stored on the property list of the liebracket for reconsideration by the user. Printing of Jacobi identities is controled by a switch |print_identities|, which is \&{off} by default. If identities are to be printed only the identities not equal to 0 are printed. @=@/ new_switch(print_identities,nil)$ @ The procedure |solve_Jacobi_identities_of| can be written down without much explanation. We declare it a lisp operator. Notice that the property |commutator_list| of a liebracket is cleared by a call of |find_Jacobi_identities_of|. The list of unsolved identities is stored as the property |unsolved_identities|. After storing the unsolved identities, the property |identity_list| can be cleared, since all identities on it have been checked. We want all message in this procedure to appear with the switch |nat| turned on. Therefore we will force this and restore the old environment afterwards. @u lisp operator solve_Jacobi_identities_of; lisp procedure solve_Jacobi_identities_of bracketname; begin scalar generatorname,stage,identity_list,i,j,identity, solution,nr_computed,nr_solved,environment,origin; check_if_bracketname_is_a_liebracket_in("SOLVE_JACOBI_IDENTITIES_OF:");@/ generatorname:=get(bracketname,'generatorname); environment:=!*nat; !*nat:=t; stage:=0; @; while identity_list do @;@/ print_statistics_of bracketname;@/ !*nat:=environment; end$ @ Preparing the next stage of solving Jacobi identities consists of finding the unprocessed commutators and after that finding all Jacobi identities following from them. @= @; find_unprocessed_commutators_of bracketname;@/ @; identity_list:=find_Jacobi_identities_of bracketname @; @ @= begin nr_computed:=0; nr_solved:=0;@/ @; @; put(bracketname,'identity_list,nil);@/ @; @; end @; @ Recall that |identity_list| is a double association list. Hence we must unfold it before usage. Recursive solving of dependencies may occur when we are solve a relation. Therefore we have to in- and decrease |indentation_level!*| beforehand and afterwards. @= for each id_list_i in identity_list do begin i:=car id_list_i; id_list_i:=cdr id_list_i; for each id_list_i_j in id_list_i do begin j:=car id_list_i_j; id_list_i_j:=cdr id_list_i_j; for each k in id_list_i_j do begin incr(nr_computed);@/ identity:=special_Jacobi_identity(bracketname,i,j,k); origin:=list('list,i,j,k);@/ @; solution:=relation_analysis(identity,bracketname); @; @; end; end; end @; @ Due the recursive nature of solving linear dependencies we have to use some indentation to indicate the level of solving dependencies. Therefore we have to precede |prin2!*| by an indentation according to a global variable |indentation_level!*|, which represents the level of indentation necessary, in all messages at the beginning of a line that are also usable when solving dependencies. Messages used only when solving Jacobi identities will only be performed at top level, so no indentation is needed there. The problem with the |indentation_level!*| is that we must be sure that it must be zero at start of any command, i.e., at algebraic level. But how can we be sure this, for something may go wrong at any level, causing a return to algebraic level without properly decreasing |indentation_level!*|. Fortunately, there is the |initl| mechanism of REDUCE, causing global quantities on the (global) list |initl!*| to be initialized to an initial value at algebraic level. Therefore we will make |indentation_level!*| a global variable and put it on |initl!*| with initial value 0. @d indent_according_to_level=@/ for i:=1:indentation_level!* do prin2!* "| " @; @d indented_print(string)=@/ <>@; @d indented_empty_line=@/ if indentation_level!*=0 then terpri!* t else @+ <> @; @=@/ global '(indentation_level!*)$@/ initl!*:='indentation_level!* . initl!*$@/ put('indentation_level!*,'initl,0)$ @ The message are rather straightforward and will not be explained in all detail. @=@/ prin2!* "Starting stage "; prin2!* incr(stage); prin2!* ":"; terpri!* nil; prin2!* "Reordering the commutators..."; terpri!* nil @; @ @=@/ prin2!* "Searching for identities..."; terpri!* nil @; @ @=@/ prin2!* "Solving the identities..."; terpri!* nil; if !*print_identities then @+ <> @; @ @= if !*print_identities and identity neq 0 then begin indent_according_to_level; maprin origin; terpri!* nil; @/ indent_according_to_level; maprin identity; terpri!* nil; end @; @ @= if !*print_identities and solution neq 0 then begin if member(solution,'(unsolvable nested_commutator invalid_generator)) then indented_print("Not solved.") else @+ <= if solution neq 0 then if member(solution,'(unsolvable nested_commutator invalid_generator)) then update_unsolved_identities_list else if car solution=generatorname or car solution='list then begin incr(nr_solved); if not !*print_identities then <> end else incr(nr_solved) @; @*1 Printing unsolved identities and statistics. Users should be able to take a look at the list of unsolved identities. For this purpose we will write a procedure |unsolved_identities_of|, which rebuilds the list of unsolved identities by deleting all entries that have become 0 during the process and returns it as an algebraic list for further examination by the user. Recall that the identities on the unsolved identities list are algebraic lists consisting of the origin of the identity and the identity itself. The procedure has to be available in algebraic mode. @u lisp operator unsolved_identities_of; lisp procedure unsolved_identities_of bracketname; begin scalar unsolved_identities,id;@/ check_if_bracketname_is_a_liebracket_in("UNSOLVED_IDENTITIES_OF:"); unsolved_identities:=get(bracketname,'unsolved_identities);@/ unsolved_identities:=@+ for each identity in unsolved_identities join if (id:=aeval second_argument_of identity) neq 0 then @| list list('list,first_argument_of identity,id); put(bracketname,'unsolved_identities,unsolved_identities); return 'list . unsolved_identities; end$ @ It may be convenient to get track of some statistics concerning a Lie superalgebra, for instance if one wants to know if a Lie superalgebra is solved completely. The procedure |print_statistics_of| prints the number of used generators, the number of commutators, generators and parameters solved and the number of unsolved identities; Of course we don't want to count the {\it special} commutators in the number of solved commutators. We can check this by looking at the informative part of an entry of the vectorstructure. @d not_special(entry)=@/informative_part_of entry neq '(special)@; @u lisp operator print_statistics_of; lisp procedure print_statistics_of bracketname; begin scalar properties_for_direct_access,vector_i,entry_i_j,nr_solved,total; check_if_bracketname_is_a_liebracket_in("PRINTS_STATISTICS_OF:"); @; nr_solved:=0; for i:=-n_used:m_used do begin vector_i:=getv(vector_structure,n+i); for j:=i:m_used do if (entry_i_j:=getv(vector_i,m-j)) and commutator_part_of(entry_i_j) and not_special(entry_i_j) then incr(nr_solved); end; total:=((m_used+n_used)^2-m_used+n_used)/2; if total=0 then rederr("PRINT_STATISTICS_OF: first define used area"); terpri!* t; prin2!* "Statistics for liebracket "; maprin bracketname; terpri!* nil;@/ prin2!* m_used; prin2!* " even and "; prin2!* n_used; prin2!* " odd generators used"; terpri!* nil; prin2!* nr_solved; prin2!* " commutators solved of ";@/ prin2!* total; prin2!* " ("; prin2!* ((nr_solved*100)/total); prin2!* " %)"; terpri!* nil;@/ prin2!* length get(get(bracketname,'generatorname),'kvalue);@/ prin2!* " linear dependencies found"; terpri!* nil;@/ total:=for each parameter in get(bracketname,'parameters) sum length get(parameter,'kvalue);@/ prin2!* total; prin2!* " parameters solved"; terpri!* nil;@/ prin2!* length get(bracketname,'unsolved_identities); prin2!* " unsolved identities"; terpri!* t; end$ @*= Access to generators. In the introduction of the previous chapter we concluded that it was most convenient to control the access to a generator of a Lie (super)algebra by an set-element-function and a clear function. For a detailed description how these procedures should act we refer to the previous chapter. In the following sections we will take care of the set-element-function |set_generator| and the clear function |clear_generator| belonging to the rtype |algebra_generator|. Moreover, to let the clear function work properly, |algebra_generator| must have a rtypefn |generator_rtypefn|. How a set-element-function, a clear function and an rtype function work and cooperate exactly, we have already explained for a liebracket. The names of all three procedures must be put on the property list of |algebra_generator|. @=@/ put('algebra_generator,'setelemfn,'set_generator)$@/ put('algebra_generator,'clearfn,'clear_generator)$@/ put('algebra_generator,'rtypefn,'generator_rtypefn)$ @ The same remarks that were made for the rtypefn |liebracket_rtypefn| apply to the rtypefn for a algebra generator, |generator_rtypefn|, since we don not want particular generators to be recognized as a |algebra_generator|. @u lisp procedure generator_rtypefn u; nil$ @ The set-element-function |set_generator| of an algebra generator should do three things: check if |val| is a valid generator and |value| a sum of generators, do the assignment |val:=value| and adjust all commutators containing |val|. For the last action we need to know the name of the liebracket associated to the algebra generator involved. We expect this name to be stored on the property list of this generator as the property |bracketname|. Since we use the standard REDUCE procedure |setk1| to do the assignment on the kvalue list of the generator we must call |rmsubs()| ourselves, in order to assure proper reevaluation of algebraic expressions. @u lisp procedure set_generator(val,value); if length val neq 2 then rederr("SET_GENERATOR: generator must have one integer argument") else begin scalar generatorname,bracketname,i,valuelist, identity,solution, nr_computed,nr_solved,environment,origin; generatorname:=operator_name_of val; bracketname:=get(generatorname,'bracketname); i:=reval first_argument_of val; value:=aeval value;@/ @; if used_operator_element(val) then rmsubs();@/ setk1(val,value,t); %Do the assignment on the kvalue list of |generatorname|% @; end$ @ We must check that |val| is a valid generator, i.e., $i$ must be integer and not out of range. For this purpose we will use the macro |wrong_atomic_argument| we wrote before. Moreover, we must check that |value| is a sum of valid generators. This can be done most conveniently by using |operator_coeff| and |wrong_atomic_argument|. We will use the variable |valuelist| (local within |set_generator|) to store the list produced by |operator_coeff|. @=@/ if not atom i or wrong_atomic_argument(i) then @| stop_with_error("SET_GENERATOR:",val,"invalid or out of range",nil); valuelist:=operator_coeff(value,generatorname); if independent_part_of valuelist neq 0 then stop_with_error("SET_GENERATOR:",@|independent_part_of valuelist, "not a sum of generators",nil); for each term in kernel_coeff_list_of valuelist do if length(term:=kernel_of term) neq 2 or not atom first_argument_of term or @| wrong_atomic_argument(first_argument_of term) then @| stop_with_error("SET_GENERATOR:",term,"invalid or out of range",nil) @; @*1 Adjusting commutators. After the assignment we have to adjust the values of $\\{bracketname}(i,j)$ for $j=-n,\dots,1$ and $j=1,\dots,m$ according to the assignment made. Hence we have to solve the identities $\\{bracketname}(i,j)=\\{bracketname}(\\{value},j)$. This can be done by using the procedure |relation_analysis|. Recall that we stored the even and odd dimensions $m$ and $n$ on the property list of a liebracket as the properties |even_dimension| and |odd_dimension|. Note that there are some different cases to distinguish: $\lie(i,i)$ may be set for $i<0$, but not for $i>0$. $\lie(i,0)$ may also not be set. These cases are already incorporated in the |repeat| statement. Moreover, note that |value| has been |aeval|'ed, hence is in !*SQ prefixform. To stay in line with the procedure |solve_Jacobi_identities_of| we will take the same actions and print the same kind of information as we did during the solving of Jacobi identities. Recall that all message that may occur recursively at deeper levels of solving linear dependencies are indented according to the global variable |identation_level!*|. Hence this level must be increased before we start adjusting commutators. @=@/ environment:=!*nat; !*nat:=t; %Force the switch |nat| to be on% @; incr(indentation_level!*); nr_computed:=0;nr_solved:=0; for j:=-get(bracketname,'odd_dimension):get(bracketname,'even_dimension) do if j neq 0 and (i neq j or i<0) then begin incr(nr_computed);@/ identity:=@<|bracketname(i,j)-bracketname(value,j)|@>; origin:=list('list,i,j);@/ @; solution:=relation_analysis(identity,bracketname); @; @; end; @; decr(indentation_level!*);@/ !*nat:=environment %Restore the original setting of |nat|% @; @ @=@/ indented_print("Adjusting the commutators of "); @/ maprin val; prin2!* "..."; terpri!* nil; if !*print_identities then @+ <> @; @ To get the difference of |bracketname(i,j)| and |bracketname(value,j)| we use |simp_liebracket| to get both commutators as standard quotients, |subtrsq| to subtract them and |mk!*sq| to convert a standard quotient into a !*SQ prefixform. Because we use the answer to solve an algebra relation we have to make sure that all substitutions are performed, hence we must apply |subs2| to the standard quotient. @<|bracketname(i,j)-bracketname(value,j)|@>=@/ mk!*sq subs2 subtrsq(simp_liebracket(list(bracketname,i,j)),@| simp_liebracket(list(bracketname,value,j))) @; @*1 Clearing generators. The clear function of an algebra generator is much easier than its set-element-function, because it is nearly impossible to backtrace all commutators which have been set by the assignment to this generator. To understand this, one should be aware of the fact that the process of adjusting commutators to linear dependencies of some generators may be recursive, namely if one the relations |bracketname(i,j)-bracketname(i,value)| itself is a linear dependency of some generators. Moreover, the relations caused by this linear dependency may have introduced new solvable Jacobi identities, which may already have been solved. Hence we will only give a warning that things may get messed up. @u lisp procedure clear_generator val; if atom val then rederr("CLEAR_GENERATOR: clear associated liebracket instead") else if length val neq 2 then rederr("CLEAR_GENERATOR: generator must have one integer argument") else begin scalar generatorname,kvalue,h; generatorname:=operator_name_of val; val:=list(generatorname,reval first_argument_of val); kvalue:=get(generatorname,'kvalue); if (h:=assoc(val,kvalue)) then begin put(generatorname,'kvalue,delete(h,kvalue)); message("CLEAR_GENERATOR: clearing",val,"may lead to errors",nil); end else message("CLEAR_GENERATOR:",val,"not found",nil); end$ @*= Multigradings, definitions and introduction of new generators. In the first section we urged the need to store and retrieve integer valued multigrades of all generators of a Lie algebra. In this section we will introduce an environment for these multigrades, implement procedures to find generators and unknown commutators of a certain degree and a procedure to determine the degree of an given expression. Moreover, we will write a procedure to introduce a new generator for a given (unknown) commutator and at the same time determine the degree of it, i.e., the degree of the commutator. Besides a grading it will also be convenient to know the definition and the ``history'' of a newly introduced generator, i.e., what commutator was used at highest level to define this generator and which commutators were recursively used to construct it . This kind of information will also be stored. For each generator we will store this information in a vector of dimension $m+n$ where $m$ and $n$ are the even and odd dimension of the Lie superalgebra, respectively. Each entry of this vector will be a dotted pair, consisting of a degree part, a definition part and a history part. At initialization the entry for a generator |y(i)| ($-n\leq i\leq m$) will be initialized to |'(0) . i . i|, i.e., we initialize the degree of all generators to a multi degree of length 1 with value 0. The vector with degree and history information will be stored on the property list of the liebracket as the property |info_list|. The information of generator |y(i)| will be contained in this vector at index $n+i$. Access to this vector can be obtained by using the macros |get_info| and |put_info|. The length of the multi degrees is stored as the property |degree_length|. As stated above it is initialized to 1. @d degree_part=car @d definition_part=cadr @d history_part=cddr @d get_degree=degree_part get_info @d get_definition=definition_part get_info @d get_history=history_part get_info @d get_info(bracketname,i)=@/ getv(get(bracketname,'info_list),get(bracketname,'odd_dimension)+i) @; @d put_info(bracketname,i,value)=@/ putv(get(bracketname,'info_list),get(bracketname,'odd_dimension)+i,value)@; @ The most important action for manipulating degrees is the possibility to add them. This is done by the recursive procedure |add_degrees|, which expects its arguments to be of identical length and, moreover, expects its arguments to be integer lists. @u lisp procedure add_degrees(degree1,degree2); if degree1 then (car degree1 + car degree2) . add_degrees(cdr degree1,cdr degree2)$ @ From using this package it became apparent that it may be quite convenient to look at gradings in another order, since during the process of computing Lie super algebras, different components of a multigrading may turn out to play an important role. As it is quite bothersome to change the order of gradings by hand, we will offer a mechanism here that selects a subset of an actual multigrading in a prescribed order. The procedure |degree_component_sequence| will assign a prescibed sequence of the multigrading to a liebracket by saving this sequence as the property |degree_sequence|. A degree sequence may be given as an integer or an algebraic or lisp list of integers. This can be transformed into a lisp list using the macro |make_oplist| to be explained below. @u lisp operator degree_component_sequence; lisp procedure degree_component_sequence(bracketname,degree_sequence); begin scalar degree_length; check_if_bracketname_is_a_liebracket_in("DEGREE_COMPONENT_SEQUENCE:"); degree_sequence:=make_oplist(degree_sequence); degree_length:=get(bracketname,'degree_length); degree_sequence:= for each component in degree_sequence collect if fixp component and component >0 and component leq degree_length then component else stop_with_error("DEGREE_COMPONENT_SEQUENCE: multigrading has no component", component,nil,nil); put(bracketname,'degree_sequence,degree_sequence); end$ @ Given a |degree| the procedure |permuted_degree| returns |degree| permuted w.r.t.\ a prescribed |sequence|. If there is no |sequence| degree should be returned without change. @d get_permuted_degree(bracketname,i)= permuted_degree(degree_part get_info(bracketname,i), get(bracketname,'degree_sequence)) @u lisp procedure permuted_degree(degree,sequence); if null sequence then degree else permute_degree(degree,sequence)$ lisp procedure permute_degree(degree,sequence); if sequence then nth(degree,car sequence) . permute_degree(degree,cdr sequence)$ @ If we want to determine the degree of a general Lie algebra element |element| belonging to a liebracket |bracketname|, we have to distinguish three cases:\medskip \item{1.} if |element| is the index number of a generator, we can simply get the information about |element| and return the degree part of it. \item{2.} if |element| is a commutator, we can add the degrees of both components. Because we will use algebraic list to return the definition a some generator, as explained in one of the next sections, we will also consider algebraic lists as commutators, in this case. \item{3.} if |element| is a generator, we can return the degree of the index number of |element|. \enditem The procedure |degree_of1| takes care of these cases. Notice that we expect commutators to have only two arguments. We can achieve this by simplifying |element| before applying |degree_of1|. @u lisp procedure degree_of1(bracketname,element); if atom element then if wrong_atomic_argument(element) then@| stop_with_error("DEGREE_OF: cannot determine degree of",element,nil,nil) else get_permuted_degree(bracketname,element) else if operator_name_of element=bracketname or operator_name_of element='list then add_degrees(degree_of1(bracketname,first_argument_of element),@| degree_of1(bracketname,second_argument_of element)) else if operator_name_of element=get(bracketname,'generatorname) then @| degree_of1(bracketname,first_argument_of element) else stop_with_error("DEGREE_OF: cannot determine degree of",element,nil,nil)$ @ At algebraic level we will return the degree of some Lie algebra element as an algebraic list. This is done by the procedure |degree_of|. In order to avoid difficulties with linear dependencies of some generators, we shall also allow linear combinations of Lie algebra elements and suppose that the sum offered is homogeneous. In this case we return the degree of the first Lie algebra element encountered. Notice that |element| is evaluated specifically as requested in the previous module. @u lisp operator degree_of; lisp procedure degree_of element; begin scalar operatorname,bracketname,check_element; if (element:=reval element)=0 then @+return nil; if not atom element then begin operatorname:=operator_name_of element; if get(operatorname,'rtype)='liebracket then bracketname:=operatorname else if get(operatorname,'rtype)='algebra_generator then @| bracketname:=get(operatorname,'bracketname) end; if null bracketname then @; if null bracketname then @| stop_with_error("DEGREE_OF: cannot determine degree of",element,nil,nil); return 'list . degree_of1(bracketname,element) end$ @ If a linear combination is a sum we can check the first term. If it is a quotient we have to examine the numerator. If it is a product we have to examine the factors until we have encountered a Lie algebra element. @= begin check_element:=element; while not atom check_element and @| member(operator_name_of check_element,'(quotient plus minus difference)) do check_element:=first_argument_of check_element; if not atom check_element then@/ (if operator_name_of check_element='times then @ else begin operatorname:=operator_name_of check_element; if get(operatorname,'rtype)='liebracket then bracketname:=operatorname else if get(operatorname,'rtype)='algebra_generator then @| bracketname:=get(operatorname,'bracketname); if bracketname then element:=check_element end) end @ @= while null bracketname and (check_element:=rest_of check_element) do <> @ The next step towards a useful application of gradings is the availability of a procedure |define_degree| to assign a new value to the degree of some generator (since a grading with all degrees equal to 0 isn't very useful). We impose a few requirements on the degrees to be assigned:\medskip \item{1.} A newly assigned degree should have the proper length, i.e., should have length |degree_length|. \item{2.} All entries of a multi degree should be integer valued. \item{3.} A degree can be entered as an atom, an algebraic list or a lisp list. This is the same syntax for entering ``lists'' of some objects which we used for lists of operatornames for multilinear operatornames, as introduced in the TOOLS package. Hence we copy the definition |make_oplist| which transforms one the alternatives mentioned above in an ordinary lisp list. @d make_oplist(op_list)=@/if null op_list then op_list else if atom op_list then list op_list else if car op_list='list then cdr op_list else op_list @; @=@/ if not integer_valued(degree:=make_oplist(degree)) or length degree neq get(bracketname,'degree_length) then stop_with_error("DEGREE:",'list . degree,"invalid degree",nil) @; @ Checking that a list consists of integers can be done with help of the following recursive procedure. @u lisp procedure integer_valued degree; if null degree then t else if fixp car degree then integer_valued cdr degree$ @ Assigning a new degree to a generator is really simple now: check if the generator is indeed a generator, check the degree for its validity and update the info entry for the generator. @u lisp operator define_degree; lisp procedure define_degree(generator,degree); begin scalar generatorname,bracketname,info; @; @; info:=get_info(bracketname,generator); put_info(bracketname,generator, degree . definition_part info . history_part info); end$ @ A generator is valid, if it is an operator element whose operator is of rtype |algebra_generator| and, moreover, the argument of which is not out of range. Before checking the argument we must |reval| it because this is not necessarily done (for instance in the procedures |definition_of| and |history_of|, which will be explained in a few sections). @= if atom generator then stop_with_error("DEGREE:",generator,"invalid generator",nil); generatorname:=operator_name_of generator; check_if_generatorname_is_a_generator_in("DEGREE:"); bracketname:=get(generatorname,'bracketname); generator:=reval first_argument_of generator; if wrong_atomic_argument(generator) then @| stop_with_error("DEGREE: generator index", generator,"out of range",nil) @; @ Since all procedures concerning degrees check for the proper length of the degrees, there should be a procedure |change_degree_length| to change the length of all degrees. The main part of it consists of adapting the length of all existing degrees. This is necessary because |add_degrees| expects all degrees to be of the same length. If the new length of is larger than the old one we must extend all degrees with an appropriate number of zeros, otherwise we can take the sub degree of appropriate length. @u lisp operator change_degree_length; lisp procedure change_degree_length(bracketname,degree_length); begin scalar m,n,old_length,shortage,extension,info,degree; check_if_bracketname_is_a_liebracket_in("CHANGE_DEGREE_LENGTH:"); if not fixp degree_length or degree_length <= 0 then rederr("CHANGE_DEGREE_LENGTH: degree length should be >= 0");@/ m:=get(bracketname,'even_dimension); n:=get(bracketname,'odd_dimension);@/ old_length:=get(bracketname,'degree_length); shortage:=degree_length-old_length; if shortage>0 then extension:=@+for i:=1:shortage collect 0;@/ @; put(bracketname,'degree_length,degree_length); end$ @ @= for i:=-n:m do begin info:=get_info(bracketname,i); @/ degree:=if extension then append(degree_part info,extension) else sub_list(degree_part info,degree_length); put_info(bracketname,i, degree . definition_part info . history_part info) end @; @ The sub list of a list |l|, consisting of the first $n$ elements, can be collected using the recursive procedure |sub_list|. @u lisp procedure sub_list(l,n); if l and n>0 then car l . sub_list(cdr l,n-1)$ @ Finding the definition or the history of some generator is much easier than the determination of the degree of some Lie algebra element, and is taken care of by the procedure |definition_of| and |history_of|, both to be available in algebraic mode. There is, however, one tricky point which we should take care of in both cases, namely if some generator is found linear independent, we still want to be able to retrieve the definition/history of such a generator. Therefore the arguments of |definition_of| and |history_of| must not be evaluated. This can be achieved by giving |definition_of| and |history_of| the property |psopfn|, i.e., the arguments of these procedures are put on a list and the procedure which name is the value of the property |psopfn| is applied to this list. For this we will use the same convention as in the TOOLS package: the |psopfn| is indicated by a additional 1, the real work, however, is done by a lisp procedure with the same name and syntax as available in algebraic mode. The definition of a generator is either an integer, corresponding to the generator, or an algebraic list with two integer arguments, corresponding to the commutator used to define the generator. We use algebraic lists, because it would be useless to return the commutator self as the definition, since it will be reevaluated to the generator immediately. Recall that for this reason we allowed algebraic lists as a special kind of commutators in |degree_of1|. The history of a generator is either an integer, corresponding to the generator, or an algebraic list of arbitrary length, consisting of possibly nested lists of integers, corresponding to the possibly nested commutator used to define the generator, where all integers recursively occuring in the history have integer histories themselves, in other words the history corresponds to the way a generator was introduced recursively. @=@/ put('definition_of,'psopfn,'definition_of1)$@/ put('history_of,'psopfn,'history_of1)$ @ @u lisp procedure definition_of1 listed_generator; definition_of first_element_of listed_generator$@# lisp procedure definition_of generator; begin scalar generatorname,bracketname; @; return get_definition(bracketname,generator); end$@# lisp procedure history_of1 listed_generator; history_of first_element_of listed_generator$@# lisp procedure history_of generator; begin scalar generatorname,bracketname; @; return get_history(bracketname,generator); end$ @*1 Finding commutators and generators of a given degree. The next important issue is how to get all (independent) generators or unknown commutators of a given degree. The first question that arises is how to define a useful notion of objects ``of a given degree''. A rigid point of view is to allow all objects whose degree is totally equal to the given degree. A more general, and to our opinion very useful, point of view is to allow all objects that have a degree the first part of which matches the given degree, any other elements of it not being relevant. This notion enables us to use subsets of a multigrading for selecting Lie algebra objects. The procedure |sub_degree| takes care of the strategy introduced above, and returns |t| if |degree1| is a subset of |degree2|, |nil| otherwise. @u lisp procedure sub_degree(degree1,degree2); if null degree1 then t else if null degree2 then nil else if car degree1=car degree2 then sub_degree(cdr degree1,cdr degree2)$ @ Finding all generators of a given degree, is very easy now: first check if |degree| is a valid degree (if not searching is useless), then collect all generators whose degree match |degree|. The result is returned a an algebraic list. Of course it is not useful to return generators that are linear dependent of others, therefore we will also check on the kvalue list of the generator if it has a value. @u lisp operator generators_of_degree; lisp procedure generators_of_degree(bracketname,degree); begin scalar even_used,odd_used,generatorname,kvalue; check_if_bracketname_is_a_liebracket_in("GENERATORS_OF_DEGREE:");@/ if not integer_valued(degree:=make_oplist(degree)) then @| stop_with_error("DEGREE:",'list . degree,"invalid degree",nil);@/ even_used:=get(bracketname,'even_used); odd_used:=get(bracketname,'odd_used);@/ generatorname:=get(bracketname,'generatorname); kvalue:=get(generatorname,'kvalue); @; end$ @ We use the |for| \dots |join| construct to get the list of generators with right degree. In this way we can prevent generators with wrong degree to cause empty entries in the result list. Since this construct concatenates lists, we have to surround all entries by an additional list. Recall that we prevented the use of 0 as an index of a generator, so at this place we have to make an exception for it. @= return 'list . for i:=-odd_used:even_used join if i neq 0 and null assoc(list(generatorname,i),kvalue) and @| sub_degree(degree,get_permuted_degree(bracketname,i)) then list list(generatorname,i) @; @ The procedure |commutators_of_degree| returns an algebraic list of all unknown commutators of a given degree. It's action is similar to that of |generators_of_degree|. For efficiency reasons we will access both the |vector_structure| and the |info_list| directly, i.e., without using the macros |get_commutator| and |get_permuted_degree|. Recall that the degrees may be permuted, thus we have to call |permuted_degree| at the proper places. @u lisp operator commutators_of_degree; lisp procedure commutators_of_degree(bracketname,degree); begin scalar properties_for_direct_access,vector_i,entry_i_j,info_list, degree_sequence,degree_i; check_if_bracketname_is_a_liebracket_in("COMMUTATORS_OF_DEGREE:"); @; info_list:=get(bracketname,'info_list); if not integer_valued(degree:=make_oplist(degree)) then @| stop_with_error("DEGREE:",'list . degree,"invalid degree",nil); degree_sequence:=get(bracketname,'degree_sequence); @; end$ @ In this case we need not make exceptions for 0 since all $\lie(i,0)$ are initialized to 0, hence have a value. @= return 'list . for i:=-n_used:m_used join <> @; @*1 Introduction of new generators. In the light of all the tools we made for showing and maintaining the degree, definition and history of a generator, it will be very convenient to have a procedure |new_generators| that introduces a new generator for some unknown commutator and at the same time updates the |info_list|. Recall that associated to a liebracket are the properties |even_used| and |odd_used|, indicating the number of even and odd generators that are actually used, respectively. It will be clear that we can use these properties right here to determine first unused index available for a newly introduced generator, and, moreover, after introducing a new generator, have to update them. Keeping in mind that the procedure |commutators_of_degree| may be used to get a list of unknown commutators, for which new generators may be introduced, it also seems convenient if |new_generators| is able to deal with lists of unknown commutators. This can be done by calling |new_generators| recursively on all elements of the list. In case of a single commutator we will return the newly introduced generator, in case of a list of commutators the corresponding list of newly introduced generators. The second case motivates us not to produce an error message if, for whatever reason, it impossible to create an new generator for some object, but simply return it unchanged, for otherwise it will be impossible to return a list containing the generators which had already been created. Hence we can deduce the following strategy:\medskip \item{1.} if the object is an atom return it unchanged. \item{2.} if the object is an algebraic list apply |new_generators| to all its elements and return the list of results. There is, however, one tricky point: some commutator may occur several times on the list. Since we are working in lisp mode this will not be detected automatically, and thus, for each occurence a new generator would be introduced. Therefore we must |reval| each entry of the list before doing anything. \item{3.} if the object is an other operator element but not a commutator, return it unchanged. \item{4.} if the object is a commutator, check if it is possible to introduce a new generator for it, if so update the |info_list| and return the newly introduced generator, else return the commutator unchanged. @u lisp operator new_generators; lisp procedure new_generators commutator_list; begin scalar operatorname,bracketname,arg1,arg2,indx, generator,degree,definition,history; return if atom commutator_list then commutator_list else @+<< operatorname:=operator_name_of commutator_list; if operatorname='list then 'list . for each commutator in arguments_of commutator_list collect @| new_generators reval commutator else if not get(operatorname,'rtype)='liebracket then commutator_list else @ >>; end$ @ It is only possible to introduce new generators for commutators of two generators which are not out of range. @= begin bracketname:=operatorname;@/ arg1:=first_argument_of commutator_list; arg2:=second_argument_of commutator_list; if wrong_atomic_argument(arg1) or wrong_atomic_argument(arg2) then return commutator_list; @; return if generator then setk(commutator_list,generator) else commutator_list end @; @ Depending if the commutator is even or odd, we must introduce a new even or odd generator, respectively. @= if even_element(operatorname,commutator_list) then @| @ else @ @ A new generator is possible if index of it (i.e., the number of used elements plus 1) does not exceed the maximal dimension. @= begin indx:=get(operatorname,'even_used)+1; if indx<=get(operatorname,'even_dimension) then@/ < >>; end @; @ @= begin indx:=get(operatorname,'odd_used)+1; if indx<=get(operatorname,'odd_dimension) then@/ < >>; end @; @ Before updating the |info_list| at index |indx|, we must compute the degree of the newly introduced generator using |add_degrees|, construct its definition and its history. The last can be done by applying the procedure |add_histories|, to be implemented in the next module. @= degree:=add_degrees(get_degree(operatorname,arg1), get_degree(operatorname,arg2));@/ history:=add_histories(get_history(operatorname,arg1), get_history(operatorname,arg2));@/ definition:=list('list,arg1,arg2); put_info(bracketname,indx,degree . definition . history) @; @ Recall that nested commutators are treated right associative by |simp_liebracket|. Therefore we can append the second history to the first. @u lisp procedure add_histories(history1,history2); if fixp history2 then list('list,history1,history2) else if fixp history1 then 'list . history1 . arguments_of history2 else 'list . append(list history1,arguments_of history2)$ @ Before we can use the procedure |new_generators| we must be able to change the properties |even_used| and |odd_used|, because these are both initialized to 0. For clarity we will in- and output them in the same way, namely as an algebraic list |{even_used,odd_used}|. @u lisp operator list_used; lisp procedure list_used bracketname; <>$ @ Before defining |even_used| and |odd_used| we must check that they are integers and not out of range. @u lisp operator define_used; lisp procedure define_used(bracketname,used_list); begin scalar even_used,odd_used; check_if_bracketname_is_a_liebracket_in("DEFINE_USED:"); if atom(used_list) or operator_name_of(used_list) neq 'list or length(used_list) neq 3 then stop_with_error("DEFINE_USED:",used_list,"invalid list of dimensions",nil); even_used:=first_argument_of used_list; odd_used:=second_argument_of used_list; if even_used>get(bracketname,'even_dimension) or odd_used>get(bracketname,'odd_dimension) then rederr("DEFINE_USED: dimensions out of range");@/ put(bracketname,'even_used,even_used); put(bracketname,'odd_used,odd_used); end$ @*= Declaration and saving of liebrackets. Now we know all ins and outs of liebrackets (especially the list of properties associated to them), we can finally write the procedures for the declaration and saving of liebrackets. Moreover, we will write a procedure for enlarging the dimensions of a liebracket. @ For the declaration of liebrackets we will use the following syntax $$\hbox{liebracket bracketname(generatorname,even dimension,odd dimension[,algebra elements,parameters])}$$ where algebra elements and parameters may be an identifier or an algebraic or lisp list of identifiers. For this purpose we can use the macro definition |make_oplist| defined before. We give the procedure |liebracket| the property |stat| with value |rlis| in order to allow more liebracket declarations at a time. It should be noted that, in doing so, |liebracket| need not be declared a lisp operator anymore to make it available in algebraic mode. Procedures with |stat='rlis| can have an arbirtrary number of arguments which the parser passes to them on a list. In our case this means that |liebracket| is offered a list of liebracket declarations. @= put('liebracket,'stat,'rlis)$ @ The outline of the procedure |liebracket| is real simple: for each declaration offered extract all identifiers and dimensions from it, check if this gives rise to a valid liebracket declaration and finally set up the right environment. @u lisp procedure liebracket decl_list; begin scalar bracketname,generatorname,m,n, algebra_elements,parameters,rtype,vector_structure,info_list; for each decl in decl_list do begin if length decl < 4 then @| stop_with_error("LIEBRACKET:",decl,"invalid liebracket declaration",nil);@/ @; @; @; end; end$ @ Since |decl| is a list of length at least 4 we can retrieve the desired variables and dimensions from it. If there are no algebra elements or parameters specified, |algebra_elements| and |parameters| will become |nil|. We transform them in orderly lisp lists using |make_oplist|. @=@/ bracketname:=car decl; generatorname:=cadr decl;@/ m:=reval caddr decl; n:=reval cadddr decl;@/ if decl:=cddddr decl then <>@; @ For a proper liebracket declaration |bracketname| and |generatorname| must both be identifiers and may not be any other REDUCE structure. Moreover |m| and |n| must both be positive integers. We do not check if all objects offered as algebra elements or parameters are identifiers, since this cannot do any harm. @= if not idp bracketname or not idp generatorname or not fixp m or not fixp n or m<0 or n<0 then @| stop_with_error("LIEBRACKET:",decl,"invalid liebracket declaration",nil); @/ if get(bracketname,'simpfn) then @| stop_with_error("LIEBRACKET: operator",bracketname, "invalid as liebracket",nil);@/ if rtype:=get(bracketname,'rtype) then @| stop_with_error("LIEBRACKET:",rtype,bracketname,"invalid as liebracket");@/ if get(generatorname,'simpfn) then @| stop_with_error("LIEBRACKET: operator",generatorname, "invalid as generator",nil);@/ if rtype:=get(generatorname,'rtype) then @| stop_with_error("LIEBRACKET:",rtype,generatorname,"invalid as generator") @; @ If we have a proper liebracket declaration we have to set up an environment for the liebracket |bracketname|, first by properly initializing the |vector_structure| and secondly by putting all other necessary properties on the property list of |bracketname|. Notice that properties of a liebracket that are lists initially being empty need not be initialized. For convenience we will list here the lists of all properties associated with a liebracket and a Lie algebra generator, which we will use later on. For an explanation of the properties we refer to the sections where they were introduced. We also recall that we have to flag |bracketname| |full| in order to enable simplification in the way we perform it. @d list_of_properties_of_a_liebracket=@/ '(vector_structure info_list !*jacobi_var!* even_dimension odd_dimension even_used odd_used degree_length degree_sequence algebra_elements parameters oplist resimp_fn generatorname rtype simpfn commutator_list identity_list unsolved_identities kvalue)@; @d list_of_properties_of_a_generator=@;@/ '(bracketname rtype simpfn kvalue)@; @= @; put(bracketname,'vector_structure,vector_structure);@/ put(bracketname,'info_list,info_list);@/ put(bracketname,'!*jacobi_var!*,list t);@/ put(bracketname,'even_dimension,m);@/ put(bracketname,'odd_dimension,n);@/ put(bracketname,'even_used,0);@/ put(bracketname,'odd_used,0);@/ put(bracketname,'degree_length,1);@/ put(bracketname,'algebra_elements,algebra_elements);@/ put(bracketname,'parameters,parameters);@/ put(bracketname,'oplist, bracketname . generatorname . 'list . 'df . algebra_elements);@/ put(bracketname,'resimp_fn,'resimp_liebracket);@/ put(bracketname,'generatorname,generatorname);@/ put(bracketname,'rtype,'liebracket);@/ put(bracketname,'simpfn,'simp_liebracket);@/ put(generatorname,'bracketname,bracketname);@/ put(generatorname,'rtype,'algebra_generator);@/ put(generatorname,'simpfn,'simpiden);@/ flag(list bracketname,'full) @; @ Now we know all properties associated to a liebracket we can also write the remaining part of the clear function of a liebracket, namely removing the properties (and flags). Notice that we do not remove the |klist|'s of the liebracket and the generators since the commutators and generators may be used elsewhere. @= begin scalar bracketname,generatorname; bracketname:=val; generatorname:=get(bracketname,'generatorname); for each property in list_of_properties_of_a_liebracket do remprop(bracketname,property); for each property in list_of_properties_of_a_generator do remprop(generatorname,property);@/ remflag(list bracketname,'full); end @; @ Recall that the vector structure containing all commutators is a double vector, the outer of dimension $m+n$, such that for $-n\leq i\leq m$ at index $n+i$ all commutators $\lie(i,j)$ with $i\leq j\leq m$ are stored at index $m-j$ in a vector of dimension $m-i$. Moreover, we have to initialize the ``special'' commutators $\lie(i,0)$ ($-n\leq i\leq 0$) and $\lie(0,j)$ and $\lie(j,j)$ ($0= vector_structure:=mkvect(m+n); for i:=-n:m do putv(vector_structure,n+i,mkvect(m-i)); for i:=-n:0 do putv(getv(vector_structure,n+i),m,'(special) . nil . 0); for j:=1:m do <> @; @ The |info_list| has to be initialized as follows: each generator |y(i)| has initial degree 0, definition |y(i)| and history $i$. @= @; info_list:=mkvect(m+n); for i:=-n:m do putv(info_list,n+i,'(0) . i . i) @; @*1 Saving and printing all values of a liebracket. Saving a liebracket |bracketname| boils down to saving all properties of |bracketname| in a file, this time including the |klist|'s of the liebracket and the generator. Before saving it all we have to call |rmsubs| in order to enable simplification of algebraic expressions after being read in. We print the values of all properties using the procedure |prin1|, which, unlike the procedure |prin2|, prints rereadable expressions. One should be aware of the fact that the standard REDUCE token reader |token1| is not able to recognize and return a vector as a token. However, on our system |token1| has been replaced by a token reader based on the lisp underneath REDUCE, which \`{\i}s able to read vectors. Moreover, on another configuration at our site which did use |token1| as the token reader, we could patch it in such way that it was also able to read vectors without too much difficulty. The implementation of |save_liebracket| beneath explicitly uses the fact that the token reader used is able to read vectors. If this is not the case |save_liebracket| has to be rewritten in such a way that all commutators to be saved are temporarily stored on a list which can be read by |token1|. In that case the vector structure has to be build up again. This case will be dealt with in a separate change file belonging to this package. The procedure |save_liebracket| has to be available in algebraic mode. @d print_this_property_of(bracketname)=@/ <> @; @u lisp operator save_liebracket; lisp procedure save_liebracket(bracketname,savefile); begin scalar generatorname; check_if_bracketname_is_a_liebracket_in("SAVE_LIEBRACKET:");@/ generatorname:=get(bracketname,'generatorname);@/ rmsubs(); out savefile;@/ write "lisp$"; %Reading the properties should be done in symbolic mode% terpri(); terpri();@/ @; for each property in 'klist . list_of_properties_of_a_liebracket do print_this_property_of(bracketname);@/ write "flag('(",bracketname,"),'full)$"; terpri(); terpri(); for each property in 'klist . list_of_properties_of_a_generator do print_this_property_of(generatorname); @; write "algebraic$ end$";@/ shut savefile; end$ @ We can check if this package has been loaded by verifying that the procedure |simp_liebracket| has a definition, using |getd|. @=@/ write "if not getd 'simp_liebracket then";terpri(); write "rederr(", """Load the Lie superalgebra package before reading this file""",")$"; terpri();terpri() @; @ The informative part of some elements in a vector structure may have the value |(t)|, indicating that the commutator belonging to such an element has been reordered and the Jacobi identities with the commutator have been computed. In this case the value of this informative part is not ordinary |(t)| but in fact it is the value of |!*jacobi_var!*| belonging to the liebracket under consideration. After reading the vector structure from file this is not the case anymore, so we have to replace all occurences of |(t)| by |!*jacobi_var!*|. This is done by the procedure |repair_vector_structure_of|. Notice that due to the procedure |find_unprocessed_commutators_of| only commutators with |-n_used|${}\leq i,j \leq{}$|m_used| have been processed, hence these are the only commutators that have to be repaired. @u lisp procedure repair_vector_structure_of bracketname; begin scalar properties_for_direct_access,!*jacobi_var!*,vector_i,entry_i_j; @; !*jacobi_var!*:=get(bracketname,'!*jacobi_var!*); for i:=-n_used:m_used do begin vector_i:=getv(vector_structure,n+i); for j:=i:m_used do if (entry_i_j:=getv(vector_i,m-j)) and informative_part_of(entry_i_j)='(t) then @| putv(vector_i,m-j,!*jacobi_var!* . k_info_and_commutator_part_of entry_i_j); end; end$ @ @=@/ write "repair_vector_structure_of '",bracketname,"$"; terpri(); terpri() @; @ The result of applying the procedure |save_liebracket| is a file, which can only be read using this package. It will also be convenient to have a procedure that lists all known commutators in a rereadable form. A statement |a:=b| can be printed like that by applying |varpri(b,list('setk,mkquote a,mkquote b),'only)|. With this knowledge we can easily implement a procedure |print_liebracket| which print the definitions of all known commutators $\lie(i,j)$ for |-n_used|${}\leq i\leq j\leq{}$|m_used|, which are not special. Printing of the definition of special commutators is not useful since these commutators will allways be 0. @u lisp operator print_liebracket; lisp procedure print_liebracket bracketname; begin scalar properties_for_direct_access,vector_i,commutator_i_j; check_if_bracketname_is_a_liebracket_in("PRINT_LIEBRACKET:");@/ @; for i:=-n_used:m_used do begin vector_i:=getv(vector_structure,n+i); for j:=i:m_used do if (i neq 0) and (j neq 0) and (i neq j or i<0) and @| (commutator_i_j:=getv(vector_i,m-j)) and (commutator_i_j:=aeval commutator_part_of commutator_i_j) then @| varpri(commutator_i_j,@| list('setk,mkquote list(bracketname,i,j),mkquote commutator_i_j), 'only); end; end$ @*1 Changing the dimensions of a liebracket. Until now the dimensions of a liebracket have to be given on declaration and cannot be changed anymore. It would be very inconvenient if the only way to enlarge the dimensions is to declare a larger liebracket and do all computations again. Therefore we will write a procedure |change_dimensions_of| which does a better job. It can be used both to enlarge or diminish the dimensions of the Lie algebra. It should be available in algebraic mode. Essentially the only actions necessary for ``enlarging'' a liebracket are the construction of a larger/smaller |vector_structure|, putting all information from the old to the new vector structure and update the properties containing information about the dimensions. Moreover, if the new dimensions are bigger than the old ones, some of the newly introduced commutators may have to be adjusted according to linear dependencies found before and, moreover, the length of the degrees of the newly introduced generators has to be adapted. @u lisp operator change_dimensions_of; lisp procedure change_dimensions_of(bracketname,m,n); begin scalar old_vector_structure,old_m,old_n,new_m,new_n,old_vector_i,entry_i_j, vector_structure,old_info_list,info_list,vector_i,m_used,n_used, degree_length,kernel_list; check_if_bracketname_is_a_liebracket_in("CHANGE_DIMENSIONS_OF:");@/ old_m:=get(bracketname,'even_dimension); old_n:=get(bracketname,'odd_dimension);@/ new_m:=min(m,old_m);new_n:=min(n,old_n);@/ m_used:=min(new_m,get(bracketname,'even_used)); n_used:=min(new_m,get(bracketname,'odd_used));@/ old_vector_structure:=get(bracketname,'vector_structure); old_info_list:=get(bracketname,'info_list); @; @; put(bracketname,'vector_structure,vector_structure);@/ put(bracketname,'info_list,info_list); put(bracketname,'even_dimension,m); put(bracketname,'odd_dimension,n);@/ put(bracketname,'even_used,m_used); put(bracketname,'odd_used,n_used); @; end$ @ We have to transfer all known commutators |bracketname(i,j)| with |-new_n|${}\leq i,j\leq{}$|new_m| and also all degrees of |generatorname(i)| for |-new_n|${}\leq i\leq{}$|new_m|. @= for i:=-new_n:new_m do begin old_vector_i:=getv(old_vector_structure,old_n+i);@/ vector_i:=getv(vector_structure,n+i); for j:=i:new_m do if (entry_i_j:=getv(old_vector_i,old_m-j)) then putv(vector_i,m-j,entry_i_j);@/ putv(info_list,n+i,getv(old_info_list,old_n+i)); end @; @ We take care of eventual linear dependencies in a very pragmatic way: if the new dimensions are larger than the old ones, we just do the assignments for the generators again. The adjustment of the new commutators will then be taken care of automatically. If |degree_length| is the current degree length, changing the degree length for the newly introduced generators can be taken care of by two subsequent calls of |change_degree_length| with |2*degree_length| and |degree_length|, respectively. Notice that before taking care of the eventual dependencies the degree length has to possess its proper length since |relation_analysis| uses this to decide which kernel to solve for. @= if m>old_m or n>old_n then begin degree_length:=get(bracketname,'degree_length); change_degree_length(bracketname,2*degree_length); change_degree_length(bracketname,degree_length); kernel_list:= for each dependency in get(get(bracketname,'generatorname),'kvalue) collect@| first_element_of dependency; for each kernel in kernel_list do setk(kernel,aeval kernel); end @*= Printing and parsing of commutators. The next subject to be dealt with is the preparation of facilities for a ``default'' liebracket whose commutators can be typed in and will be printed out using square brackets. For this we will introduce a global variable |default_liebracket!*|, which is the name of the liebracket known to REDUCE as the default liebracket. We initialize it to |lie|, since this is the name we usually use. @=@/ initialize_global(default_liebracket!*,'lie)$ @ REDUCE input is parsed by the procedure |xread1|, which converts it to a form that can be translated to lisp by the procedure |form|. If we want REDUCE to translate expressions in square brackets as commutators of the default liebracket |default_liebracket!*|, we can do this by giving the token |![| the property |stat| with value |liebracket_stat|, indicating to the parser |xread1| that expressions in square brackets are to be dealt with by a separate procedure |liebracket_stat|, and flagging |!]| as a delimiter, again indicating to |xread1| that the expression currently being parsed has ended. @=@/ put('![,'stat,'liebracket_stat)$@/ flag(list '!],'delim)$ @ If |xread1| encounters the token |![|, it calls the procedure |liebracket_stat|, which will take control over the parsing of the commutator that follows the opening bracket. The argument(s) of the commutator can be read by recursively calling |xread| which will parse until it encounters the delimiter |!]| and return the parsed arguments. Before returning the list representing the commutator of the default liebracket we must scan another token in order to keep the parsing process in a correct state. @u lisp procedure liebracket_stat; begin scalar arguments; arguments := xread nil;@/ arguments :=@+ if atom arguments or car arguments neq '!*comma!* @| then arguments @+ else cdr arguments;@/ scan(); return default_liebracket!* . arguments; end$ @ If some algebraic operatorname has the property |prifn|, the printing routines of REDUCE will transfer the control over the printing of an element of such operatorname to the procedure which name is the value of the property |prifn|. So by introducing a |prifn| |liebracket_prifn| we can print the commutators of some liebracket using square brackets. If we want to print a commutator using square brackets we can print ``['' and ``]'' and in between the arguments of the commutator separated by commas. @u lisp procedure liebracket_prifn commutator; begin prin2!* "[";@/ inprint('!*comma!*,0,arguments_of commutator);@/ prin2!* "]"; end$ @ The operatorname initially declared default liebracket must have the right |prifn|. @=@/ put(default_liebracket!*,'prifn,'liebracket_prifn)$ @ The default liebracket can be changed by using the procedure |default_liebracket|, which is available in algebraic mode and takes all necessary actions. @u lisp operator default_liebracket; lisp procedure default_liebracket bracketname; begin remprop(default_liebracket!*,'prifn);@/ default_liebracket!*:=bracketname;@/ put(default_liebracket!*,'prifn,'liebracket_prifn); end$ @*= Basis transformations of Lie superalgebras. If one is working with a Lie superalgebra, the structure of which is partially determined and partially is to be determined, it may be very convenient to perform a basis transformation of this algebra. Proceeding this way the structure of the remaining part might become clearer. Of course if we perform a basis transformation, we also want to have all (known) commutators expressed in elements of the new basis. Hence we have to perform a transformation of the commutator table, i.e., the vectorstructure, too. For this suppose we are given a Lie (super)algebra with basis $x_i$ $(i\in I)$, and furthermore suppose we have a basis transformation given by $y_j=a^i_j x_i$ $(j\in I)$, where we have used the sommation convention. Then in general a commutator $[x_k,x_l]$ $(k,l\in I,k\leq l)$ is given by $$[x_k,x_l]=c^i_{kl}x_i+\sum_{k',l'} [x_{k'},x_{l'}]_u$$ where the subscript $u$ denotes (yet) unknown commutators, i.e., commutators having empty entries in the vectorstructure. Using the basis transformation given above, we are interested in the commutators $$[y_p,y_q]=a^k_p a^l_q [x_k,x_l]$$ with all commutators on the right hand side expressed in terms of the new basis $y_j$. Therefore we can perform the transformation of a Lie product table in two steps:\medskip \item{1.} Express all commutators $[x_k,x_l]$ in terms of the new basis. \item{2.} Express all commutators $[y_p,y_q]$ in terms of the new basis using the result of the first step. \enditem It seems clear that we need the inverse transformation $b^j_i=(a^i_j)^{-1}$ in order to perform the first step. Using the inverse transformation we get $$[x_k,x_l]=c^i_{kl}b^j_i y_j+\sum b^p_{k'}b^q_{l'}[y_p,y_q]$$ For the implementation in REDUCE of this rather simple exercise there are some additional points involved. For instance, the newly created commutators should be stored in another liebracket since the generatorname changed from, let's say, $x$ to $y$. And, how exactly to perform the transformation and the inverse transformation. As we will see later on, we will use some rather tricky temporary demolishing of the old liebracket structure to get everything right. Moreover, for reasons of efficiency, we will temporarily bypass all kinds of checks performed on the assignment of commutators and instead perform one sufficient check for all assignments beforehand. @ The first point to be taken care of is how to deal with the transformation and inverse transformation. Points involved are {\it a\/}) how to represent the transformation, {\it b\/}) how to compute the inverse transformation and finally, in the light of the last remark of the previous section, {\it c\/}) how to see to it that the transformation leaves no elements untransformed. By a basis transformation we understand a (possibly empty) algebraic list of equations of the form $y_j=a^i_j x_j$, where $(a^i_j)$ is invertible. Notice that we do not require a basis transformation to comprise all old generators $x_i$, but also a subset is allowed. Nevertheless if we are transforming commutators to a new basis, such non occuring generators may appear in the computation of some commutators. Hence, in order to get a correct new commutator table, we must find the remaining non transformed generators and transform them into new generators. In ordinary cases it will be sufficient only to transform the used generators, by which we mean generators in one of the ranges $1,\dots,$|even_used| or $-1,\dots,$|odd_used|. However, for whatever reason, some generator outside these ranges may also be used, in which case transforming the used generators will not be sufficient. Therefore we will introduce a switch |full_transformation| indicating if transformation of the used generators is sufficient or if transformation of the whole algebra is necessary. We put |full_transformation| \&{off} be default. @=@/ new_switch(full_transformation,nil)$ @ Depending on the switch |full_transformation| we have different upperbounds for the even and odd generators to be transformed, namely the properties |even_used| and |odd_used| if |full_transformation| is \&{off}, or |even_dimension| and |odd_dimension| if |full_transformation| is \&{on}, of the liebracket under consideration. In both cases we will use vectors |transform_vector| and |inverse_vector| to store the basis transformation and its inverse. @= if null !*full_transformation then begin even_bound:=get(bracketname,'even_used); odd_bound:=get(bracketname,'odd_used); end else begin even_bound:=get(bracketname,'even_dimension); odd_bound:=get(bracketname,'odd_dimension); end;@/ transform_vector:=mkvect(even_bound+odd_bound); inverse_vector:=mkvect(even_bound+odd_bound) @; @ The outline of the top level transformation procedure |transform_liebracket| is very easy: extend and process the basis transformation, compute the inverse transformation, and transform the commutator table using these transformations. @u lisp operator transform_liebracket; lisp procedure transform_liebracket(bracketname,new_bracketname, new_generatorname,basis_transformation); begin scalar generatorname,even_bound,odd_bound,transform_vector,inverse_vector, new_generator,transformed_sq,splitted_sf,generator_list,x_gap,y_gap, new_even_used,new_odd_used,result; check_if_bracketname_is_a_liebracket_in("TRANSFORM_LIEBRACKET:"); generatorname:=get(bracketname,'generatorname); @; @; @; end$ @*1 Storage and extension of the transformation. Given the algebraic list |basis_transformation| representing the basis transformation we have to fill the vectors |transform_vector| and |inverse_vector|. Processing the transformation essentially consists of three steps: read in and process |basis_transformation|, compute the inverse transformation and extend the transformation to the whole range of generators that must be transformed. @= @; @; @ @; @ A basis transformation consists of a number of transformation rules of the form $y_j=a^i_jx_i$, which we have to check for their validity and store in the vector |transform_vector|. These checks consist of: \medskip \item{1.} checking if the transformation rule is of the proper form. \item{2.} checking that the new generator $y_j$ lies within the proper range. \item{3.} checking that the right hand side of the transformation rule is indeed a sum of generators. This can for instance be done using the procedure |operator_coeff|. We will, however, use the low level procedure |split_form|, which underlies the procedure |operator_coeff| and acts on standard forms, since we can use the splitted forms returned by |split_form|, as we will see further on. The right hand side of the transformation rule is a sum of generators if the independent part, i.e., the |car|, of the result of |split_form| is |nil|. \item{4.} checking that the sign of the generators on the right hand side of the tranformation rules is the same as on the left hand side. \enditem Moreover, in order to know for which old generators we have to solve the set of transformation rules we store all occuring generators on |generator_list|. For each transformation rule we will store the right hand side as a standard quotient |transformed_sq| as well as the splitted list returned by |split_form|, |splitted_sf|. @d lhs=cadr @d rhs=caddr @d valid_transformation_rule = @/ (eqexpr transformation_rule and not atom lhs transformation_rule and @| operator_name_of lhs transformation_rule = new_generatorname) @; @d valid_generator(generator) = @/ (fixp generator and generator neq 0 and generator <= even_bound and generator >= -odd_bound)@; @d get_new_generator_ok= @/ <>@; @d sign_and_bound_check= @/ for each generator in cdr splitted_sf product if (generator:=first_argument_of car generator)*new_generator>0 and @| valid_generator(generator) then 1 @+else 0 @; @d valid_transformed_sq = @/ null car splitted_sf and sign_and_bound_check=1 @; @d extend_used_generator_list= @/ for each generator in cdr splitted_sf do if not member(generator:=car generator,generator_list) then generator_list:=generator . generator_list @; @d store_transformation_rule(i,value)=@/putv(transform_vector,odd_bound+i,value)@; @d store_inverse_rule(i,value)=@/putv(inverse_vector,odd_bound+i,value)@; @d get_transform(i)=@/getv(transform_vector,odd_bound+i) @; @d get_inverse(i)=@/getv(inverse_vector,odd_bound+i) @; @ Given |basis_transformation| we need to process all transformation rules in order to get all generators to solve for. Solving the resulting system can be done by applying |solve|, but since our checks computed the transformations in quite a lot of ways and ensure us that we have a linear system of equations (due to the use of |split_form| which checks for linearity), we can also use the underlying solver for systems of linear equations |solvesys|. The arguments of |solvsys| are a list of standard forms to be solved and a list of kernels to solve for. Hence we have to generate a list of standard forms representing the transformation rules. Recall that the second argument of |split_form| is the list of operators with respect to which to split. Moreover, notice that the arguments of |transform_liebracket| are already simplified, since it is a lisp operator. Therefore, we can use |simp| without harm. @d return_transformation_as_sf=@/ numr subtrsq(!*k2q lhs(transformation_rule),transformed_sq) @; @= if atom basis_transformation or operator_name_of basis_transformation neq 'list then stop_with_error("TRANSFORM_LIEBRACKET",basis_transformation, "not valid as a basis transformation",nil); @/ basis_transformation:= for each transformation_rule in arguments_of basis_transformation collect <> @; @ The result of |solvesys| is a list of a list of standard quotients being the solutions of the system for the list of kernels given as its second argument preceded by |t| if the system is found to be linear. If the system is inconsistent |solvesys| will return with an error. For the inverse transformation we will also store the standard quotient as well as the list of splitted standard forms returned by |split_form|. If the number of dependent variables of the system does not equal the number of equations, the system is not consistent and we can stop without trying to solve it. @= if length generator_list neq length basis_transformation then rederr "TRANSFORM_LIEBRACKET: inconsistent transformation"; if basis_transformation then basis_transformation:=caadr solvesys(basis_transformation,generator_list); for each generator in generator_list do <> @; @ After the preceding steps we are left with two (possibly partially filled) vectors |transform_vector| and |inverse_vector| representing the basis transformation and its inverse. For a proper transformation of the commutator tables, however, we must be sure that both vectors are filled completely, as far as some old generators are not already found to be linear dependent. In other words, we have to extend the basis transformation to the full range $1,\dots,|even_bound|$ and $-1,\dots,-|odd_bound|$ of generators. Since we didn't require that the generators of the preceding steps be successive in any way, this boils down to filling in the gaps in both |transform_vector| and |inverse_vector|. Since we want to fill in the gaps from low to high for both even and odd generators, we have to deal with even and odd generators separately, that is to say we will use an additional variable |direction| to indicate whether we look at even or odd gaps and a variable |bound| being |even_bound| or |odd_bound|, respectively. So it is our task to go through both positive and negative ranges of generators and check if there is a gap, i.e., there is no transformation rule associated to a generator or there is a linear dependency for a generator (since these generators will never occur again). If we have found a gap |x_gap| in the transformation for the old generators, then there must also be a gap |y_gap| for the new generators, and we can extend the transformation by transforming |x_gap| into |y_gap| and vice versa. @d find_next_x_gap=@/ repeat x_gap:=x_gap+direction until abs(x_gap)>bound or @|(null getv(inverse_vector,odd_bound+x_gap) and @| null assoc(list(generatorname,x_gap),get(generatorname,'kvalue))); if abs(x_gap)>bound then x_gap:=nil @; @d find_next_y_gap=@/ repeat y_gap:=y_gap+direction until abs(y_gap)>bound or null getv(transform_vector,odd_bound+y_gap) @; @d exchange_gaps=@/ store_inverse_rule(x_gap, mksq(list(new_generatorname,y_gap),1) . @| list(nil,list(new_generatorname,y_gap) . 1));@/ store_transformation_rule(y_gap, mksq(list(generatorname,x_gap),1) . @| list(nil,list(generatorname,x_gap) . 1)) @; @d fill_in_the_gaps=@/ x_gap:=y_gap:=0; find_next_x_gap; find_next_y_gap; while x_gap do @+<> @; @= <> where direction=1,bound=even_bound; <> where direction=-1,bound=odd_bound @; @*1 Transformation of the Lie product table. Now we have dealt with the most intricate part of the transformation, we can start earning from our efforts, since the remaining work merely consists of simplifying expressions. However, in order to save work as much as possible we will temporarily redefine some of the simplification functions and data structures associated to the old liebracket |bracketname|. Since we want to be sure to restore these changes afterwards, we will perform this part in a procedure |transform_table| and surround it by |errorset| in order to keep full control over |transform_table| in case of errors, i.e., if an error occurs |errorset| will return control to the calling procedure. In this way we can be sure that the original data structures can be restored. The result of |errorset| is a list containing the result of the procedure called by |errorset|. @= @; result:=errorset(list('transform_table,mkquote bracketname,mkquote generatorname, mkquote new_bracketname,mkquote new_generatorname, mkquote even_bound,mkquote odd_bound, mkquote new_even_used,mkquote new_odd_used, mkquote transform_vector,mkquote inverse_vector),t,t); @; if result then return list('list, @|('list . @+for i:=1:new_even_used collect mk!*sq car get_transform(i)), @|('list . @+for i:=1:new_odd_used collect mk!*sq car get_transform(-i))) @; @ In particular, the vector structure of the old liebracket must be saved. We save it as the property |save_vector_structure|. @= put(bracketname,'save_vector_structure,get(bracketname,'vector_structure)) @; @ Transforming the commutator table can be done in two steps: first we have to express all old commutators in terms of the new generators, after that the new commutators can be expressed in terms of the old ones and then simplified to expressions in new generators. However, before that we have to declare |new_bracketname| a Lie (super)algebra. Notice that we have to take the same set of operators as |algebra_elements| and |parameters|, respectively. Since a liebracket declaration checks if its generator isn't already an algebraic operator and if so, returns with an error message, we have to remove the property |simpfn| for |new_generatorname|. Finally we will construct a grading for |new_bracketname|, using the grading of |bracketname|. Notice that this is only useful when all the transformation rules are homogeneous. @u lisp procedure transform_table(bracketname,generatorname, new_bracketname,new_generatorname,even_bound,odd_bound, new_even_used,new_odd_used, transform_vector,inverse_vector); begin scalar m,n,vector_structure,vector_i, save_vector_structure,save_vector_i,save_entry_i_j,arg_i,arg_j,degree_length; remprop(new_generatorname,'simpfn); apply1('liebracket,list list(new_bracketname,new_generatorname, even_bound,odd_bound, get(bracketname,'algebra_elements),get(bracketname,'parameters))); @; @; @; end$ @ An entry of the vector structure may or may not have a value. If it has a value we have to simplify it in such a way that all occurences of old generators are replaced by new generators. It is clear that we can use |inverse_vector| to this purpose. More specifically, we will replace the original |simpfn| |simpiden| by |simp_transform_vector| that takes it values from |inverse_vector|. Since we have to be sure that the generators to be simplified lie within the range covered by |inverse_vector|, we check for this. Moreover, we need to know where to get |inverse_vector|. For this purpose we will flag |generatorname| |full|, in which way the generatorname will be added to the arguments of its simplication function. We store |inverse_vector| on the property list of |generatorname|, as well as |bounds|, i.e. the even and odd bound of before, as we need these quantities to access |inverse_vector|. Notice that |inverse_vector| may contain empty entries, namely for those entries that correspond to linear dependent generators. For these generators, we may simply apply |simpiden| for further simplification. @u lisp procedure simp_transform_vector generator; begin scalar generatorname,i,bounds,inverse_vector,value; generatorname:=car generator; i:=cadr generator; bounds:=get(generatorname,'bounds); inverse_vector:=get(generatorname,'inverse_vector); if i<-car bounds or i>cdr bounds then stop_with_error("TRANSFORM_LIEBRACKET:",generator, "out of the transformation range. Use 'on fulltransformation;'.",nil); return if value:=getv(inverse_vector,car bounds+i) then car value else simpiden generator end$ @ Of course we have to put some additional properties on the property list of |generatorname|. Moreover we have to apply |rmsubs| so that we can be sure that the result of |simpiden| will be resimplified. @=@/ put(generatorname,'inverse_vector,inverse_vector);@/ put(generatorname,'bounds,odd_bound . even_bound);@/ put(generatorname,'simpfn,'simp_transform_vector);@/ flag(list generatorname,'full); rmsubs() @; @ If an entry of |vector_structure| has no value, i.e., the commutator corresponding to it is not known, we have to express it in terms of the new liebracket and generators. To this purpose we will write a procedure |transform_commutator|, which computes, given two entries of |transform_vector| or |inverse_vector|, the commutator $[y_i,y_j]$ expressed in old generators or $[x_i,x_j]$ expressed in new generators, respectively. The entries of both of the vectors mentioned above contain a dotted pair, the |car| of which is the generator as standard quotient, the |cdr| a list applicable by the procedure |build_sum| of the TOOLS package, used to compute the outcome of a multilinear operator applied to the numerators of its arguments, as a standard quotient. Therefore, we have to divide the result by the denominators of the standard quotients. Notice that the second argument of |build_sum| is a stack of splitted arguments, hence we have to reverse the arguments. @u lisp procedure transform_commutator(bracketname,transformed_i,transformed_j); quotsq(build_sum(bracketname,list(cdr transformed_j,cdr transformed_i)),@| !*f2q multf(denr car transformed_i,denr car transformed_j))$ @ With the above preparations redefining the |vector_structure| is utterly simple. Recall that entries of a vector structure are dotted pairs, the |car| of which is the informative part, to be initialized to |nil|, the |cadr| the klist info part, which for the temporary vector structure may be also be set to |nil|. Moreover, recall that |vector_structure| entries whose informative part is |'(special)| should not be changed. The reader should be aware that a |arg_i| in the code below will only be used if has a value, namely all commutators containing linear dependent generators have a value according to this dependency, so will be dealt with in the ``known part''. The same applies to the call of |get_inverse(j)|. After installing the temporary vector structure, we have to call |rmsubs| again, in order effectuate the resubstitution of the unknown commutators into commutators of the new liebracket. @= @; save_vector_structure:=get(bracketname,'save_vector_structure); m:=get(bracketname,'even_dimension); n:=get(bracketname,'odd_dimension); @; for i:=-odd_bound:even_bound do begin save_vector_i:=getv(save_vector_structure,n+i); vector_i:=getv(vector_structure,n+i); arg_i:=get_inverse(i); for j:=i:even_bound do if (save_entry_i_j:=getv(save_vector_i,m-j)) and commutator_part_of(save_entry_i_j) then @/ (if not_special(save_entry_i_j) then @| putv(vector_i,m-j,nil . nil . aeval commutator_part_of save_entry_i_j)) else putv(vector_i,m-j,@| nil . nil . mk!*sq transform_commutator(new_bracketname,arg_i,get_inverse(j))) end; put(bracketname,'vector_structure,vector_structure); rmsubs() @; @ After the redefinition of the vector structure of |bracketname| any commutator of |bracketname| will be automatically simplified to an expression in commutators and generators of the new liebracket. Hence a commutator $[y_i,y_j]$ of the transformed liebracket can be computed in two ways: using the transformation it can be expressed in terms of the old generators, which will be simplified to an expression in the new generators, or just as |new_bracketname(i,j)|. This gives rise to relation for |new_bracketname| which can be solved and stored using |relation_analysis|. As we will use !*SQ prefix forms, which will not be simplified again, to represent the relation, we must be sure that full simplication has taken place, i.e., we have to apply |subs2| or |simp!*| at the right places. Notice that due to linear dependencies of the old generators the vector |transform_vector| need not be filled entirely. Due to |fill_in_the_gaps| we know, however, that with the exception of 0 |transform_vector| is exactly filled from |-new_odd_used| to |new_even_used|. Of course we don't have to compute commutators outside of this range. ``Special'' commutators need to be solved neither. Since we don't use the vector structure here to see if a commutator is special we will check using |i| and |j| directly. Finally we will set |even_used| and |odd_used| to |new_even_used| and |new_odd_used|, respectively, for the newly created liebracket, as these are the actual numbers of used even and odd generators. @d no_special_pair_i_j= @/ i neq 0 and j neq 0 and (i neq j or i<0) @; @= for i:=-new_odd_used:new_even_used do if (arg_i:=get_transform(i)) then for j:=i:new_even_used do if (arg_j:=get_transform(j)) and no_special_pair_i_j then @| relation_analysis(mk!*sq subtrsq(simp!* list(new_bracketname,i,j),@| subs2 transform_commutator(bracketname,arg_i,arg_j)), new_bracketname); put(new_bracketname,'even_used,new_even_used); put(new_bracketname,'odd_used,new_odd_used)@; @ Using |transform_vector| and the procedure |degree_of| and |define_degree| it is not very hard to construct a grading for |new_bracketname|, under the assumption that the transformation is homogeneous w.r.t.\ this grading. Notice that all elements of |transform_vector| are filled consecutively from |-new_odd_used| to |new_even_used|, with the exception of 0. Before doing anything we should, however, change the length of the grading of |new_bracketname| to the length of the grading of |bracketname|, that is, to the length of the list of currently used components of the grading of |bracketname|. @=@/ degree_length:=if get(bracketname,'degree_sequence) then length get(bracketname,'degree_sequence) else get(bracketname,'degree_length); change_degree_length(new_bracketname,degree_length); for i:=-new_odd_used:new_even_used do if i neq 0 then define_degree(list(new_generatorname,i),degree_of(mk!*sq car get_transform(i))) @ @=@/ put(bracketname,'vector_structure,get(bracketname,'save_vector_structure)); remprop(bracketname,'save_vector_structure); put(generatorname,'simpfn,'simpiden); remprop(generatorname,'inverse_vector); remflag(list generatorname,'full); remprop(generatorname,'bounds) @; @*= Necessary changes to the klist mechanism. In one of the previous sections we already explained that the ordinary klist mechanism of REDUCE is not very suited for liebrackets, since all occuring commutators are stored on a linear list, where the number of commutators may be quit big. Moreover we made some preparations in the vector structure of a liebracket, in order to replace the ordinary klist mechanism with an information system which is based on the vector structure. Here, it is our intention to change two basic procedures of the REDUCE source in such a way that the outer appearance of the system remains the same, whereas hidden under the surface for liebrackets the klist mechanism is replaced by a vector structure based counterpart. @ The first procedure to be changed is |fkern|. It is used by |mksq| and checks if there is a klist entry for some kernel, if not, it generates one, and eventually, returns this entry. Changes are obvious: if the operatorname of the kernel is a liebracket and both arguments are integers, not the klist should be used but the vector structure of the concerning liebracket. If not both arguments are integers, we can only use the klist mechanism. @u symbolic procedure fkern u; begin scalar x,y; if atom u then @+return list(u,nil); if get(operator_name_of u,'rtype)='liebracket and @| fixp first_argument_of u and fixp second_argument_of u then @+ return fkern_liebracket u; y := if atom car u then get(car u,'klist) @+else exlist!*; if not (x := assoc(u,y)) then <> else exlist!* := y>>; return x end$ @ The procedure |fkern_liebracket| is fairly simple. If the |k_info_of| the vector structure entry of the considered commutator exists, return it, otherwise construct it and adapt the vector structure accordingly. For the last action we shall use |rplaca|. It is easily seen that the use of |rplaca| causes no harm. Since the |k_info| can be found directly in the vector structure, and doesn't have to be found by association, one would expect that the kernel can be removed from the |k_info| entry. This, however, is not true: the kernel in the |k_info| is used by |mksq| to obtain an identical address for the considered kernel in all standard quotients. Thus a lot of memory can be saved. Notice that the arguments of the considered commutator need not be checked to lie within proper bounds. This is due to the fact that |fkern| (indirectly) only is called from procedures which have already checked the bounds. @u symbolic procedure fkern_liebracket commutator; begin scalar bracketname,i,j,entry_i_j; bracketname:=operator_name_of commutator; i:=first_argument_of commutator; j:=second_argument_of commutator; entry_i_j:=get_vector_structure(bracketname,i,j); if null entry_i_j then @|entry_i_j:= put_vector_structure(bracketname,i,j,nil . list(commutator,nil) . nil) else if null k_info_of entry_i_j then @| rplaca(k_info_and_commutator_part_of entry_i_j,list(commutator,nil)); return k_info_of entry_i_j; end$ @ The procedure |prepsq!*| is used to reorder an algebraic expression for output. After |factor O;| the expression is ordered w.r.t. all kernels of the operator $O$. The order of the kernels of the operator $O$ is governed by its klist. Since the klist of a liebracket is not complete, in fact it only contains info about commutators containing non integer arguments, we have to choose a different method here. We do this as follows: we find all the kernels of the concerning liebracket using the procedure |find_all_kernels| of the TOOLS package and order the thus obtained list of kernels w.r.t.\ the standard kernel ordering of REDUCE, by calling the procedure |ordn|. This list can now be used as a replacement for the klist. @u symbolic procedure prepsq!* u; begin scalar x,!*combinelogs; if null numr u then return 0; x := setkorder append((for each j in factors!* join if not idp j then nil else if get(j,'rtype)='liebracket then ordn get_all_kernels(numr u,j) else for each k in get(j,'klist) collect car k), append(factors!*,ordl!*)); if kord!* neq x or wtl!* then u := formop numr u . formop denr u; u := if !*rat or !*div or upl!* or dnl!* then replus prepsq!*1(numr u,denr u,nil) else sqform(u,function prepsq!*2); setkorder x; return u end$ @ The end of a REDUCE input file must be marked with |end|. @u end@+; @*= Index. This section contains the cross reference index of all identifiers, together with the numbers of the modules in which they are used. Underlined entries correspond to module numbers where the identifier was declared. \bigskip