diff options
Diffstat (limited to 'web/reduce/rweb/appl/liesuper.web')
-rw-r--r-- | web/reduce/rweb/appl/liesuper.web | 4287 |
1 files changed, 4287 insertions, 0 deletions
diff --git a/web/reduce/rweb/appl/liesuper.web b/web/reduce/rweb/appl/liesuper.web new file mode 100644 index 0000000000..c760f2da6e --- /dev/null +++ b/web/reduce/rweb/appl/liesuper.web @@ -0,0 +1,4287 @@ +% 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()$@/ +@<Check if the TOOLS package is already loaded@>$ +@<Lisp initializations@>@/ +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. + +@<Check if the TOOLS...@>= +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 @<Simplify commutator |val|@> +else if length val>3 then @<Simplify nested commutator |val|@> +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. + +@<Simplify commutator |val|@>= +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 @<Simplify |bracketname(arg1,arg2)| using the bilinearity@>; +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. + +@<Simplify |bracketname(arg1,arg2)| using the bilinearity@>= +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 @/ + <<resimplify:=t;arg:=bracketname . arguments_of arg>> @; + +@ 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. + +@<Simplify nested commutator |val|@>= +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. + +@<Order |arg1| and |arg2| canonically and possibly set |sign| to |t|@>= +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. + +@<Check if |arg1| and |arg2| are not out of range@>= +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; + @<Order |arg1| ...@>; + @<Check if |arg1| and |arg2|...@>; + @<Get commutator |bracketname(arg1,arg2)| as a canonical standard quotient@>; + 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; + @<Order |arg1| ...@>; + 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; + +@<Lisp ini...@>=@/ +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. + +@<Check if |value| is a valid algebra element@>= +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 @; + +@<Prepare and check |arg1| and |arg2|@>=@/ +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 + +@<Check |arg1| and |arg2| for special or dangerous commutators@>=@/ + 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; + @<Prepare and check |arg1| and |arg2|@>; + @<Order |arg1| and |arg2|...@>; + @<Check |arg1| and |arg2| for special or dangerous commutators@>; + value:=aeval value; + @<Check if |value| is a valid algebra element@>; + if sign then value:=mk!*sq negsq simp value; + @<Store the assignment |bracketname(arg1,arg2):=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. + +@<Store the assignment |brack...@>= +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 + <<if flagp(x := car u,'share) + then if not flagp(x,'reserved) then set(x,x) else rsverr x + else if eqcar(x,'list) + then u := nil . append(cdr x,cdr u) + else if eqcar(x,'replaceby) then rule!-list(list x,nil) + else if smemq('!~,x) + then if eqcar(x,'equal) then rule!-list(list x,nil) + else rule!-list(list list('replaceby,x,nil),nil) + else if (xx:=get(if atom x then x @+else car x,'rtype)) + and (xx:=get(xx,'clearfn)) + then apply1(xx,x) + else @+<<let2(x,nil,nil,nil); let2(x,nil,t,nil)>>; + 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|. + +@<Lisp ini...@>=@/ + 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 @<Remove all properties of liebracket |val|@> +else if length val = 3 then @<Clear commutator |val|@> +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. + +@<Clear commutator |val|@>= +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; + @<Prepare and check |arg1| and |arg2|@>; + if not_ordered_commutator(arg1,arg2) then + begin + h:=arg1;arg1:=arg2;arg2:=h; %Switch |arg1| and |arg2|% + end; + @<Check |arg1| and |arg2| for...@>; + @<Clear commutator |bracketname(arg1,arg2)|@>; +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. + +@<Clear commutator |bra...@>=@/ +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 + +@<Initialize properties for direct access@>=@/ + 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!* + +@<Get all necessary properties for finding commutators@>= + @<Initialize properties for direct access@>; + 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; + @<Get all necessary properties for finding com...@>; + @<Find the |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 @| + @<Mark |bracketname(i,j)| processed, if it is a sum of generators@>; + 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. + +@<Find the |dependent_generators|@>= +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 @+ + <<commutator_list:=list(i,j) . commutator_list; + put(bracketname,'commutator_list,commutator_list)>> @; +@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. + +@<Mark |brac...@>= +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 <0<k$, (3) $i<0<j<k$ and (4) +$0<i<j<k$. Moreover it is easily seen that these conditions are +satisfied if and only if none of the commutators $\lie(i,j)$, +$\lie(i,k)$ and $\lie(j,k)$ is one of the ``special'' commutators +$\lie(p,q)$ with $p=0$ or $q=0$ or $p=q>0$. 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 + +@<Get all necessary properties for finding identities@>= + @<Initialize properties for direct access@>; + 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; + @<Get all necessary properties for finding id...@>; + 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; + @<Find and store all Jacobi identities for |i| and |j|@>; + 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. + +@<Find and store all ...@>=@/ +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; + @<Add all terms of $\lie(i,|comm_j_k|)$ up to |term|@>; + 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. + +@<Add all terms of $\lie(i,|comm_j_k|)$ up to |term|@>= + 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; + @<Initialize prop...@>; + 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); + @<If necessary update |entry_i_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 necessary update |entry_i_j|@>= +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. + +@<Get commutator |bracketname(arg1,arg2)| as...@>=@/ + 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 + @<Solve |relation| for a commutator@> + else @<Solve |relation| for a generator or parameters@>; +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. + +@<Solve |relation| for a com...@>= +begin@/ +solvable_kernels:=skip_list solvable_kernels(independent_part_of + kernel_list,bracketname,parameters); +return +if null solvable_kernels then 'unsolvable +else begin + @<Find the optimal commutator |optimal_kernel| for which to solve@>; + return + if optimal_kernel then@+ + <<linear_solve_and_assign(relation,optimal_kernel);optimal_kernel>> + 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|. + +@<Find the optimal commutator ...@>=@/ + 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. + +@<Solve |relation| for a gen...@>= +begin@/ +solvable_kernels:=skip_list + solvable_kernels(relation,generatorname,parameters); +return +if null solvable_kernels then + @<Solve |relation| by appropiately solving parameters@> +else + begin + @<Find the optimal generator |optimal_kernel| for which to solve@>; + return + if optimal_kernel then@+ + <<linear_solve_and_assign(relation,optimal_kernel);optimal_kernel>> + else 'invalid_generator; + end; +end @; + +@ +@<Find the optimal gene...@>=@/ + 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. + +@<If possible find and solve the list of parameters |clear_list|@>= + 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. + +@<Lisp ini...@>=@/ +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. + +@<Solve |relation| by appr...@>= +if !*solve_parameters then +begin + kernel_list:=kernel_coeff_list_of kernel_list; + @<If possible find and solve the list of parameters |clear_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. + +@<Lisp ini...@>=@/ +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; + @<Prepare next stage@>; + while identity_list do + @<Perform current stage@>;@/ + 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. + +@<Prepare next stage@>= +@<Print starting message for next stage@>; +find_unprocessed_commutators_of bracketname;@/ +@<Report the search for identities@>; +identity_list:=find_Jacobi_identities_of bracketname @; + +@ @<Perform current stage@>= +begin + nr_computed:=0; nr_solved:=0;@/ + @<Report the solving of identities@>; + @<Compute, solve and print all Jacobi identities in |identity_list|@>; + put(bracketname,'identity_list,nil);@/ + @<Print the number of identities solved@>; + @<Prepare next stage@>; +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. + +@<Compute, solve and print all Jacobi identities in |identity_list|@>= +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);@/ + @<If necessary print |identity|@>; + solution:=relation_analysis(identity,bracketname); + @<Take the actions appropriate for |solution|@>; + @<If necessary print |solution|@>; + 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)=@/ + <<indent_according_to_level; prin2!* string>>@; +@d indented_empty_line=@/ + if indentation_level!*=0 then terpri!* t else + @+ <<terpri!* nil; indent_according_to_level; terpri!* nil>> @; + +@<Lisp ini...@>=@/ +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. + +@<Print starting message for next stage@>=@/ +prin2!* "Starting stage "; prin2!* incr(stage); prin2!* ":"; terpri!* nil; +prin2!* "Reordering the commutators..."; terpri!* nil @; + +@ @<Report the search for identities@>=@/ +prin2!* "Searching for identities..."; terpri!* nil @; + +@ @<Report the solving of identities@>=@/ +prin2!* "Solving the identities..."; terpri!* nil; +if !*print_identities then @+ +<<prin2!* "=========================="; + terpri!* nil>> @; + +@ @<If necessary print |identity|@>= +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 necessary print |solution|@>= +if !*print_identities and solution neq 0 then +begin + if member(solution,'(unsolvable nested_commutator invalid_generator)) + then indented_print("Not solved.") + else @+ <<if car solution=generatorname or car solution='list then + indented_print("*** Solved for: ") + else indented_print("Solved for: "); + maprin solution>>;@/ + indented_empty_line; +end @; + +@ @<Print the number of identities solved@>=@/ +indented_print(nr_solved); prin2!* " identities solved of "; +prin2!* nr_computed; indented_empty_line @; + +@ We recall that the procedure |relation_analysis| can only return 0, +|unsolvable|, |nested_commutator|, |invalid_generator| or a list, the +|car| of which is |bracketname|, |generatorname| or |list| (in which +case some parameters of the Lie superalgebra were solved). The second +third and fourth case give rise to an unsolved identity, which has to +be placed on the list of unsolved identities. The last two cases are +important enough to be mentioned even if |print_identities| is turned +\&{off}. + +In the case that we have an unsolved identity we store it together +with its origin in an algebraic list on the |unsolved_identities| list +of the liebracket. + +@d update_unsolved_identities_list=@/ +put(bracketname,'unsolved_identities,@| + list('list,origin,identity) . get(bracketname,'unsolved_identities)) @; + +@<Take the actions appropriate for |solution|@>= +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 + <<indented_print("*** Identity "); maprin origin; + prin2!* " solved for: "; maprin solution; terpri!* nil>> +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:"); + @<Initialize prop...@>; + 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|. + +@<Lisp ini...@>=@/ +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;@/ + @<Check that |val| and |value| are valid for assignment@>; + if used_operator_element(val) then rmsubs();@/ + setk1(val,value,t); %Do the assignment on the kvalue list of |generatorname|% + @<Adjust commutators |bracketname(i,j)| for $j=-n,\dots,1$ and $j=1,\dots,m$@>; +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|. + +@<Check that |val| and |value| are valid for assignment@>=@/ +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. + +@<Adjust commuta...@>=@/ +environment:=!*nat; !*nat:=t; %Force the switch |nat| to be on% +@<Write a message that adjustment of commutators has begun@>; +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);@/ + @<If necessary print |ide...@>; + solution:=relation_analysis(identity,bracketname); + @<Take the actions appr...@>; + @<If necessary print |sol...@>; + end; +@<Print the number of ident...@>; +decr(indentation_level!*);@/ +!*nat:=environment %Restore the original setting of |nat|% @; + +@ @<Write a message that ...@>=@/ +indented_print("Adjusting the commutators of "); @/ maprin val; prin2!* "..."; +terpri!* nil; +if !*print_identities then @+ +<<indented_print("| ========================"); +terpri!* nil;>> @; + +@ 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 @<Check for linear combinations of Lie algebra elements@>; + 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. + +@<Check for linear combinations of Lie algebra elements@>= +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 + @<Check all factors for Lie algebra elements@> + 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 + +@ @<Check all factors for Lie algebra elements@>= + while null bracketname and (check_element:=rest_of check_element) do + <<if not atom first_element_of check_element then + begin + operatorname:=operator_name_of first_element_of check_element; + if get(operatorname,'rtype)='liebracket then bracketname:=operatorname + else if get(operatorname,'rtype)='algebra_generator then @| + bracketname:=get(operatorname,'bracketname) + end; + if bracketname then element:=first_element_of check_element>> + + +@ 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 @; + +@<Check if |degree| is a valid degree@>=@/ +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; + @<Check if |generator| is valid, if so find |bracketname|@>; + @<Check if |degree| is a valid degree@>; + 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). + +@<Check if |generator| is valid, if so find |bracketname|@>= + 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;@/ + @<Adapt the |info_list|@>; + put(bracketname,'degree_length,degree_length); +end$ + +@ @<Adapt the |info_list|@>= + 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. + +@<Lisp ini...@>=@/ +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; + @<Check if |generator| is valid, if so find |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; + @<Check if |generator| is valid, if so find |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); + @<Return the list of generators with right degree@>; +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 the list of generators with right degree@>= + 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:"); + @<Initialize properties for direct access@>; + 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); + @<Return the list of commutators with right degree@>; +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 the list of commutators with right degree@>= + return 'list . + for i:=-n_used:m_used join + <<vector_i:=getv(vector_structure,n+i); + degree_i:=degree_part getv(info_list,n+i);@/ + for j:=i:m_used join + if (null (entry_i_j:=getv(vector_i,m-j)) or + null commutator_part_of(entry_i_j)) and@| + sub_degree(degree,@| + permuted_degree(add_degrees(degree_i, + degree_part getv(info_list,n+j)), + degree_sequence))@/ + then + list list(bracketname,i,j) + >> @; + +@*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 + @<If possible introduce and return a new generator, update |info_list|@> >>; +end$ + +@ It is only possible to introduce new generators for commutators of +two generators which are not out of range. + +@<If possible introduce and return a new generator...@>= +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; + @<Check if new |generator| is possible, if so update |info_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. + +@<Check if new |generator| is possible, if so update |info_list|@>= +if even_element(operatorname,commutator_list) then @| + @<Update |even_used| and |info_list|, if new |generator| is possible@> + else + @<Update |odd_used| and |info_list|, if new |generator| is possible@> + +@ A new generator is possible if index of it (i.e., the number of used +elements plus 1) does not exceed the maximal dimension. + +@<Update |even_used| and |info_list|, if new |generator| is possible@>= +begin + indx:=get(operatorname,'even_used)+1; + if indx<=get(operatorname,'even_dimension) + then@/ + <<put(operatorname,'even_used,indx); + generator:=list(get(operatorname,'generatorname),indx); + @<Update the |info_list|@> >>; +end @; + +@ @<Update |odd_used| and |info_list|, if new |generator| is possible@>= +begin + indx:=get(operatorname,'odd_used)+1; + if indx<=get(operatorname,'odd_dimension) + then@/ + <<put(operatorname,'odd_used,indx); + indx:=-indx; + generator:=list(get(operatorname,'generatorname),indx);@/ + @<Update the |info_list|@> >>; +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. + +@<Update the |info_list|@>= +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; +<<check_if_bracketname_is_a_liebracket_in("LIST_USED:"); + list('list,get(bracketname,'even_used),get(bracketname,'odd_used))>>$ + +@ 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. + +@<Lisp ini...@>= +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);@/ + @<Get |bracketname|, |generatorname|, |m|, |n|, +|algebra_elements| and |parameters|@>; + @<Check the liebracket declaration for its validity@>; + @<Set up the environment for liebracket |bracketname|@>; + 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|. + +@<Get |bracketname|, |generatorname|, |m|, |n|, |algebra_elements| + and |parameters|@>=@/ +bracketname:=car decl; generatorname:=cadr decl;@/ +m:=reval caddr decl; n:=reval cadddr decl;@/ +if decl:=cddddr decl then +<<algebra_elements:=car decl;algebra_elements:=make_oplist(algebra_elements);@/ +if cdr decl then parameters:=cadr decl; parameters:=make_oplist(parameters)>>@; + +@ 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. + +@<Check the liebracket declaration for its validity@>= +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)@; + +@<Set up the environment for liebracket |bracketname|@>= +@<Initialize the vectors |vector_structure| and |info_list|@>; +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. + +@<Remove all prop...@>= +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<j\leq m$) to 0 and mark them as special. +The second field of each special entry is the klist replacement; it +must be initialized to |nil|. + +@<Initialize |vector_structure|@>= +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 + <<putv(getv(vector_structure,n),m-j,'(special) . nil . 0); + putv(getv(vector_structure,n+j),m-j,'(special) . nil . 0)>> @; + +@ The |info_list| has to be initialized as follows: each generator +|y(i)| has initial degree 0, definition |y(i)| and history $i$. + +@<Initialize the vectors |vector...@>= +@<Initialize |vector_...@>; +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)=@/ +<<prin2 "put('"; prin1 bracketname; prin2 ",'"; prin1 property; prin2 ",'"; + prin1 get(bracketname,property); prin2 ")$"; terpri(); terpri()>> @; + +@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();@/ + @<Check if this package has been loaded@>; + 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); + @<Incorporate statements to repair the |vector_structure|@>; + 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|. + +@<Check if this package has been loaded@>=@/ +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; + @<Initialize properties for dir...@>; + !*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$ + +@ @<Incorporate statem...@>=@/ +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:");@/ + @<Initialize properties for dir...@>; + 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); + @<Initialize the vectors |vector...@>; + @<Transfer all known commutators and degrees to the larger vectors@>; + 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); + @<Take care of the eventual linear dependencies and the degree length@>; +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|. + +@<Transfer all known...@>= +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. + +@<Take care of the eventu...@>= +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. + +@<Lisp ini...@>=@/ +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. + +@<Lisp ini...@>=@/ +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|. + +@<Lisp ini...@>=@/ +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. + +@<Lisp ini...@>=@/ +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. + +@<Get |even_bound| and |odd_bound| and initialize the vectors@>= + 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); + @<Get |even_bound|...@>; + @<Extend and compute the basis transformation and its inverse@>; + @<Transform the liebracket |bracketname| into |new_bracketname|@>; +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. + +@<Extend and compute the ...@>= +@<Read in and process |basis_transformation|@>; +@<Compute and store the inverse transformation@>; +@<Extend the transformation to |even_bound| and |odd_bound|@> @; + +@ 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= @/ + <<new_generator:=first_argument_of lhs(transformation_rule); + valid_generator(new_generator)>>@; +@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) @; + +@<Read in and process |bas...@>= +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 + <<if not valid_transformation_rule or not get_new_generator_ok + then @| stop_with_error("TRANSFORM_LIEBRACKET:",lhs(transformation_rule), + "not allowed as a new generator",nil);@/ + transformed_sq:=simp rhs(transformation_rule); + splitted_sf:=split_form(numr transformed_sq,list(generatorname)); + if not valid_transformed_sq then + stop_with_error("TRANSFORM_LIEBRACKET",lhs(transformation_rule), + "must be a sum of generators with right sign",nil);@/ + extend_used_generator_list; + store_transformation_rule(new_generator,transformed_sq . splitted_sf); + return_transformation_as_sf>> @; + +@ 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. + +@<Compute and store the inverse...@>= +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 + <<transformed_sq:=first_element_of basis_transformation; + store_inverse_rule(first_argument_of generator, + transformed_sq . @|split_form(numr transformed_sq,list(new_generatorname))); + @/ basis_transformation:=rest_of basis_transformation>> @; + +@ 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 @+<<exchange_gaps; find_next_x_gap; find_next_y_gap>> @; + +@<Extend the transform...@>= +<<fill_in_the_gaps; new_even_used:=y_gap-1>> where direction=1,bound=even_bound; +<<fill_in_the_gaps; new_odd_used:=-y_gap-1>> 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|. + +@<Transform the liebracket...@>= +@<Save the original data structures of |bracketname|@>; +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); +@<Restore the data structures of |bracketname|@>; +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|. + +@<Save the original...@>= +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))); + @<Redefine the old vector structure@>; + @<Compute and store the new vector structure@>; + @<Construct a grading for |new_bracketname|@>; +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. + +@<Take preparations for temporary simplification@>=@/ +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. + +@<Redefine the old vector...@>= +@<Take preparations for ...@>; +save_vector_structure:=get(bracketname,'save_vector_structure); +m:=get(bracketname,'even_dimension); n:=get(bracketname,'odd_dimension); +@<Initialize |vector_structure|@>; +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) @; + +@<Compute and store the new...@>= +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|. + +@<Construct a grading...@>=@/ +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))) + +@ @<Restore the data stru...@>=@/ +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 <<x := list(u,nil); + y := ordad(x,y); + if atom car u + then <<kprops!* := union(list car u,kprops!*); + put(car u,'klist,y)>> + 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 |