summaryrefslogtreecommitdiff
path: root/web/reduce/rweb/appl/liesuper.web
diff options
context:
space:
mode:
Diffstat (limited to 'web/reduce/rweb/appl/liesuper.web')
-rw-r--r--web/reduce/rweb/appl/liesuper.web4287
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