path: root/web/reduce/rweb/appl/liesuper.web

% 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